Задача таксономии и частичного обучения Лекция 6. - презентация

1 Задача таксономии и частичного обучения Лекция 6

2 Что такое таксон? Как измерять близость между объектами? Обычное евклидово расстояние, Обычное евклидово расстояние, Взвешенное евклидово расстояние, Взвешенное евклидово расстояние, Хеммингово расстояние, Хеммингово расстояние, Мера близости, задаваемая с помощью потенциальной функции. Мера близости, задаваемая с помощью потенциальной функции. Функция конкурентного сходства Функция конкурентного сходства

3 Оптимизируемые критерии в таксономии Алгоритмы класса FOREL Алгоритмы класса FOREL F( )= (x i,x j i ), F( )= (x i,x j i ), Алгоритмы класса k-Means Алгоритмы класса k-Means F( )= 2 (x i,x j i ), F( )= 2 (x i,x j i ), Алгоритмы класса KRAB Алгоритмы класса KRAB F=ln(dh)* / F=ln(dh)* / Алгоритмы, основанные на логических решающих функциях Алгоритмы, основанные на логических решающих функциях F( )= = F( )= =

4 Классификация методов таксономии По типу разделения По типу разделения Иерархические Иерархические Иерархическая таксономия Иерархическая таксономия Разделительные Разделительные k-Means k-Means Forel Forel Логические алгоритмы таксономии Логические алгоритмы таксономии По базовой гипотезе По базовой гипотезе Вероятностные Вероятностные ищутся параметры смеси распределений ищутся параметры смеси распределений EM-алгоритм EM-алгоритм Геометрические Геометрические ищутся связные группы объектов ищутся связные группы объектов KRAB KRAB По суперцели По суперцели

5 EM-алгоритм A={x 1,x 2,…x m } A={x 1,x 2,…x m } Восстановление смеси распределений: Восстановление смеси распределений: (x) =w 1 ϕ (x, θ 1 )+…+w k ϕ (x, θ k ), k < m. (x) =w 1 ϕ (x, θ 1 )+…+w k ϕ (x, θ k ), k < m. Вводится дополнительный вектор переменных z ij =p(θ k |x i ). Вводится дополнительный вектор переменных z ij =p(θ k |x i ). Е-Шаг Е-Шаг z ij = w j ϕ (x i, θ j )/ (x) z ij = w j ϕ (x i, θ j )/ (x) М-шаг М-шаг Максимизируется логарифм правдоподобия Максимизируется логарифм правдоподобия ln( (x 1 )*…* (x k ))->max ln( (x 1 )*…* (x k ))->max θ 1,…, θ k θ 1,…, θ k w j = (g 1j +…+g mj ) /m w j = (g 1j +…+g mj ) /m θ j =argmax{g 1j ln ϕ (x 1, θ)+…+g mj ln ϕ (x m, θ)} θ j =argmax{g 1j ln ϕ (x 1, θ)+…+g mj ln ϕ (x m, θ)} θ Останавливается при стабилизации параметров Останавливается при стабилизации параметров

6 Иерархическая таксономия

7 Forel

8 k-Means

9

10 Алгоритм KRAB Кратчайший незамкнутый путь Кратчайший незамкнутый путь Мера близости объектов внутри таксона Мера близости объектов внутри таксона Расстояние между таксонами Расстояние между таксонами Мера локальной неоднородности Мера локальной неоднородности i = / min = i = / min = Однородность таксонов Однородность таксонов h =. h =.

11

12 Определение числа таксонов ЕМ-алгоритм ЕМ-алгоритм добавление компонент для описания объектов, не вписывающихся ни в один из существующих кластеров добавление компонент для описания объектов, не вписывающихся ни в один из существующих кластеров удаление компонент с малым количеством объектов удаление компонент с малым количеством объектов k-means k-means объединяются классы у которых расстояния внутри класса близки к расстояниям между классами объединяются классы у которых расстояния внутри класса близки к расстояниям между классами Forel, KRAB Forel, KRAB ищутся «ступеньки» в динамике изменения функционала качества ищутся «ступеньки» в динамике изменения функционала качества

13 Сравнение различных алгоритмов таксономии Воспроизводимость результатов Воспроизводимость результатов Согласованность результатов на подвыборке с результатами на всей выборке Согласованность результатов на подвыборке с результатами на всей выборке Матрицы смежности Матрицы смежности Проверка на выборках с заданным числом классов Проверка на выборках с заданным числом классов

14 Задача частичного обучения Частичное обучение Классифицированная выборка выборка Таксономия(автоматическаяклассификация) Построение решающего правила (классификация).Неклассифицированная выборка выборка

15 Задача частичного обучения В зависимости от постановки может рассматриваться как задача таксономии с ограничениями В зависимости от постановки может рассматриваться как задача таксономии с ограничениями Основные подходы Основные подходы Основанные на восстановлении смеси распределений Основанные на восстановлении смеси распределений EM-алгоритм EM-алгоритм Два взгляда на выборку Два взгляда на выборку Co-training Co-training Графовые методы с опорой на классифицированные объекты Графовые методы с опорой на классифицированные объекты TDR TDR Частично обученные SVM Частично обученные SVM

16 Таксономические решающие функции