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

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

Оптимизируемые критерии в таксономии Алгоритмы класса 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( )= =

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

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, θ)} θ Останавливается при стабилизации параметров Останавливается при стабилизации параметров

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

Forel

k-Means

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

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

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

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

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

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