Разработка алгоритмов на базе FRiS-функции Лекция 6. - презентация

1 Разработка алгоритмов на базе FRiS-функции Лекция 6

2 Функция конкурентного сходства r1 r2 F=0 F=(r2-r1)/(r2+r1) F [-1, 1]

3 Компактность Существует множество нечетких, интуитивных определений. Существует множество нечетких, интуитивных определений. Невычурность границ Невычурность границ Простота форм Простота форм Пример удачной формализации: профиль компактности Пример удачной формализации: профиль компактности

4 Формулировка компактности через FRiS-функцию Среднее значение конкурентного сходства для всех объектов выборки ~ компактность выборки Среднее значение конкурентного сходства для всех объектов выборки ~ компактность выборки F=0.87F=0.38F=0.03 В зависимости от принципов по которым определяются ближайший «свой» и «чужой» представители можно моделировать различные виды компактности Похожесть на ближайшего соседа – локальная компактность Похожесть на типичного представителя – унимодальная и полимодальная компактность

5 Плотность распределения FRiS-функции в статистической постановке задачи распознавания

6 Зависимость ожидаемой величины FRiS-функции от вероятности ошибочного распознавания

7 Функция конкурентного сходства – единый базис для решения различных задач Data Mining Таксономия FRiS-Tax Построение решающего правила FRiS-Stolp Выбор информативной системы признаков FRiS-GRAD Обобщенная классификация FRiS-TDR Прогнозирование FRiS-Pro Комбинированные задачи FRiS-SDX

8 Алгоритм FRiS-Stolp Ищется базовое множество столпов, состоящее из наилучшего кандидата на роль столпа образа А и наилучшего кандидата на роль столпа образа В. Ищется базовое множество столпов, состоящее из наилучшего кандидата на роль столпа образа А и наилучшего кандидата на роль столпа образа В. Считается, что рассматриваемый образ описывается единственным столпом, а в качестве столпа конкурирующего образа берется ближайший объект из этого образа. Считается, что рассматриваемый образ описывается единственным столпом, а в качестве столпа конкурирующего образа берется ближайший объект из этого образа. Происходит наращивание базовой системы столпов до достижения одного из условий остановки Происходит наращивание базовой системы столпов до достижения одного из условий остановки заданный уровень точности распознавания обучающей выборки заданный уровень точности распознавания обучающей выборки максимально допустимое количество столпов в системе максимально допустимое количество столпов в системе

9 Алгоритм FRiS-Stolp r1 r2 r1 r2

10 Алгоритм FRiS-Tax Редуцированная FRiS-функция Редуцированная FRiS-функция Виртуальный конкурент Виртуальный конкурент Работа алгоритма состоит из двух этапов: Работа алгоритма состоит из двух этапов: FRiS-Cluster FRiS-Cluster Отыскиваются центры локальных сгустков объектов (столпы). Отыскиваются центры локальных сгустков объектов (столпы). Выборка распределяется между столпами. Строится кластеризация. Выборка распределяется между столпами. Строится кластеризация. FRiS-Class FRiS-Class Линейно разделимые кластеры объединяются в таксоны сложной формы. Линейно разделимые кластеры объединяются в таксоны сложной формы.

11

12

13 Выбор числа таксонов в алгоритме FRiS-Tax Строятся кластеризации для всех k K, вычисляется их качество F(2),F(3),…,F(k) Строятся кластеризации для всех k K, вычисляется их качество F(2),F(3),…,F(k) Ищутся локальные максимумы качества Ищутся локальные максимумы качества такие k, что F(k-1)

14 Требования к обобщенной классификации Решает задачи распознавания, таксономии и частичного обучения Решает задачи распознавания, таксономии и частичного обучения Смесь классифицированной и неклассифицированной выборок разбивается на таксоны Смесь классифицированной и неклассифицированной выборок разбивается на таксоны алгоритм ТРФ алгоритм ТРФ Геометрическая компактность Геометрическая компактность объекты одного таксона должны быть похожими друг на друга и отличаться от объектов других таксонов объекты одного таксона должны быть похожими друг на друга и отличаться от объектов других таксонов Однородность Однородность в одном таксоне должны преобладать объекты одного и того же образа в одном таксоне должны преобладать объекты одного и того же образа

15 Вычисление FRiS-функции по смешанной выборке r* - расстояние до виртуального конкурента r1 r2r2

16 Вычисление FRiS-функции по смешанной выборке с опорой на столпы

17 Схема алгоритма FRiS-TDR Ищется базовое множество столпов, состоящее из наилучшего кандидата на роль столпа образа А и наилучшего кандидата на роль столпа образа В. Ищется базовое множество столпов, состоящее из наилучшего кандидата на роль столпа образа А и наилучшего кандидата на роль столпа образа В. Считается, что рассматриваемый образ описывается единственным столпом, а в качестве столпа конкурирующего образа берется ближайший объект из этого образа. Считается, что рассматриваемый образ описывается единственным столпом, а в качестве столпа конкурирующего образа берется ближайший объект из этого образа. Объекты неклассифицированной выборки могут быть столпами как образа А, так и образа В. Объекты неклассифицированной выборки могут быть столпами как образа А, так и образа В. Происходит наращивание базовой системы столпов до достижения одного из условий остановки Происходит наращивание базовой системы столпов до достижения одного из условий остановки заданный уровень точности распознавания обучающей выборки заданный уровень точности распознавания обучающей выборки максимально допустимое количество столпов в системе максимально допустимое количество столпов в системе F(i-1)

18 Эффект от использования информации из распознаваемой выборки

19 Примеры работы алгоритма на классифицированной и неклассифицированной выборках

20 Автоматический выбор числа таксонов

21 Задача SDX Необходимо привести неструктурированный массив данных к виду, удобному для восприятия человеком Необходимо привести неструктурированный массив данных к виду, удобному для восприятия человеком Сокращение числа объектов (переход к эталонам) Сокращение числа объектов (переход к эталонам) Сокращение числа признаков (переход к существенным) Сокращение числа признаков (переход к существенным)

22 Обучающая выборка Выбор системы признаков (алгоритм GRAD) Таксономия+ Решающее правило (алгоритм FRiS-Tax) Алгоритм FRiS-SDX Оценка предсказательной способности