Лекция (4), страница 2

Дает компактные сферическиекластеры.Среднее связывание: усредненное попарноерасстояние. Редко используется.Единственное связывание: наименьшеепопарное расстояние. Дает «растянутые»кластеры сложной формы.Центроидное связывание: расстояние междуцентрами (мат. ожидание) кластеров.Другие методы (например метод Ward’а –минимизирует внутрикластерные дисперсии илидругую целевую функцию)Многое зависит от расстоянияA B C D EA 0 1 2 2 3B 1 0 2 4 3C 2 2 0 1 5D 2 4 1 0 3E 3 3 5 3 0Обсуждение иерархической кластеризацииДостоинства:Очень просто и понятно, легко реализовать Наглядные дендрограммы Нет метапараметровНедостатки:не масштабируется: временная сложность O(n2), где n - числокластеризуемых объектов жадный алгоритм - локальная оптимальность с точки зренияминимизации внутриклассовых расстояний и максимизациимежклассовых относительно слабая интерпретируемость поэтому нет компоненты в EM (но есть процедуры которые можновызвать в коде)Кластеризация на основе строгой группировки(partitioning):Основная задача:Найти такое разбиение C исходного множества X из N объектов на Kнепересекающихся подмножеств Ck, покрывающих X, чтобывнутриклассовое расстояние было минимальным:minCi C j  , Ci  XТочное решение – перебор с отсечениемiK1 xCi  xCi d ( x, x)метод «ветвей и границ», но число комбинаций неприемлемо дажедля 100 объектов:Эвристические методы:1 KK i  K NS(N , K ) (1)KiK ! i 1 K-means (прототип кластера – мат.

ожидание m), K-medoids(прототип кластера – средний элемент)minищется локальный минимумCi C j  , Ci  XiK1 xCi d (mi , x )Метод K-Means в enterprise minerШаг 0. Инициализация:Шаг 1. Поиск центров:произвольное разбиение на заданное числокластеров K (где значение K выбирается поССС на основе иерархическойкластеризации)Для всех K кластеровxxCiCiШаг 2. Расчет расстояний до центров:Для всех N объектови K кластеровmi xd (mi , x ) xCiCiШаг 3. Выбор ближайшего кластера:x  Ci  i  min d (m j , x )jЕсли были перестановки, то Шаг 1.Пример101099887766554433221110987654321000001K=2234567891234567891001234567891010101099887766554433221100012345678910012345678910Особенности K-MeansДостаточно быстрыйЛокальный экстремум:Глобальный можно искать «разумным» перебором: имитация отжига,генетические алгоритмы и т.д.В SAS на основе нескольких инициализацийНедостаткиЧисловые данные (иначе как найти центр?) – моды, центр кластера –число (для числовых атрибутов)Необходимо задавать K заранее (есть методы «отбора» K)Чувствительность к шуму и выбросам, кластеры сферической формыИспользование в SAS EMРассмотрим ту же задачу с рекомендательной системой:Представили набор транзакций в виде матрицы частот использованияпродуктов Применили Variable Clustering для удаления зависимых переменных Построили кластерыОт K-Means к K-MedoidsДве главных беды k-means:Чувствительность к выбросам и числовые данныеK-Medoids:Идея: вместо мат.

ожидания кластера ищется представительный(«наиболее центральный») объект – medoid Процесс: случайная инициализация, переход к новому medoid, еслиэто улучшает целевую функцию:minCi C j  , Ci  XiK1 x ,miCi d (mi , x )НО: не масштабируется и вычислительно неэффективный:O(K(N-K)2 ) для каждой итерации101099887766554433221100012345678910012345678910Алгоритм K-Medoids101010999888Случайн. Kmedoids765Каждыйобъект кближ.medoid7657654433222111000123456K=2Пока естьизменения789104300123456789100Если качество кластеризац. улучш.,то переход к нов.

medoid1012345678910Перебор всех кандидатовна замену medoid10Расчетстоимостиперехода(total cost ofswapping)98765439876543221100012345678910012345678910Fuzzy K-meansШаг 0. Инициализация:случайная матрица U (но со всеми нормировками)Шаг 1. Поиск центров: для всех K кластеровc j   (uij )m xiixi  c j2Шаг 3. Перерасчет U*:2Dij *uij  D 2 ik  kiШаг 2.

Расчет расстояний до центров кластеровдля всех объектовDij m(u) ij1m 1*Если матрица сильно изменилась U  U   , то Шаг 1.Определение числа кластеровПо сути – перебор моделей с разным числом кластеров и выбор понекоторому критерию, например Pseudo-F (Calinski and Habarasz,V1974)2W j   || Tvi   Tj ||Q   || Tvi   T ||2iC ji 1N- число объектов,G – число кластеров,W-сумма внутри-кластерных квадратов расстояний,Q – сумма всех кв.

расстоянийдо общего центра G(Q   Wg ) /(G  1)g 1pseudoF  GWg /( N  G)g 1Выбирается вариант с максимальным pseudoFОпределение числа кластеровSAS Cubic Clustering Criterion (CCC) (Sarle, 1983)Основная идея: сравнение R2 (для отображения матрицы данных спомощью индикаторной матрицы в прототипы кластеров) для заданноймодели кластеризации с E(R2) для равномерно распределенногомножества прототипов кластеров (как наихудший возможный вариант)1 − ( 2 )/2 = 1 − 2 (0.001 + ( 2 ))1.2n = число наблюдений, p = число переменных, Y = nxp матрица данных(стандартизованных), M = qxp матрица центров кластеров, X =индикаторная матрица (xik=1 если i принадлежит k)T= Y’Y, B = ’ X’X, W = T-B , R2 = 1 – trace(W)/trace(T)Должно быть больше 2 и выбирается первый локальный максимумОбщая идея статистического подхода вкластеризации (и не только)ВероятностьЭмпирическиеданныеМодельПравдоподобиеМодель описывает процесс порождения эмпирических данных втерминах теории вероятности (например, плотность распределениядля непрерывных данных)Наиболее общий подход оценки параметров модели через функциюправдоподобияФункция правдоподобияФормула БайесаP( Data | Model) P( Model)P( Model | Data) P( Data)Функция правдоподобия – совместное распределение выборки изпараметрического распределения как функция параметра модели.Задача – найти «лучшую» модель, ту, которая наиболее точно описываетэмпирические данные.Функция правдоподобия – функция модели (параметров модели) прификсированных данных.Спецификация модели – «искусство» (не процедура), фиксируется типмодели (например, распределение), а ищутся «лучшие» параметры.Для сложных задач модель = «смесь» (линейная комбинация)распределений.ПримерыИспытания Бернулли:Пусть дана последовательность {0,1}: 0,1,1,0,0,1,1,0 Ищем модель в классе распределений B(p): Задача - найти наилучший параметр p:Смесь нормальных распределений:Пусть дана выборка, например, рост людей:185,140,134,150,170 … Предполагаем нормальное распределение, но в среднем женщиныниже мужчин, а значит – «смесь» распределений:где:Задача - найти параметры смеси:arg max P( Data |  1 ,  2 , 1 , 2 ,  1 ,  2 )1 , 2 , 1 , 2 ,1 , 2Оценка максимального правдоподобияТочечная оценка параметров, которая максимизирует функциюправдоподобия при фиксированной реализации выборки.Если A1,,An независимые одинаково распределенные сл.

вел.:l(Data|Model) = log(P(Data|Model)) - логарифмическая функцияправдоподобия:log – монотонная функция, точки экстремумов совпадают вместо произведения – сумма логарифмовМаксимум функции правдоподобия в нуле производных:Для всех параметров тета:l ( X | 1 ,...,n )0iДля нахождения максимума решаем полученную систему уравненийПример c распределением БернуллиНадо найти p, максимизирующий логарифмическоеправдоподобие l(p)= Log P(Data|B(p))Скрытые (латентные) переменные иEM алгоритмЗадача кластеризации как оценка скрытых (латентных)переменных – «меток» кластеров:Пусть Data = {x(1),x(2),…x(n)} - набор сл.

векторов «наблюдений»Пусть H = {z(1),z(2),..z(n)} - множество значений соответствующихзначений скрытой величины Z, где z(i) соответствует x(i)Считаем, что Z – дискретна.Оценка скрытых (ненаблюдаемых) величин – цель EMПриложения EM:кластеризация заполнение пропущенных значений в выборке поиск скрытых состояний марковской моделиEM АлгоритмЛогарифмическое правдоподобие наблюдаемых данных:Нужно оценить не только параметры  , но и HПусть Q(H) есть распределение вероятности скрытых величинНеравенство Дженсона (для выпуклой функции):F(Q,) - нижняя граница l()l ( )  log p( D |  )  log  p( D, H |  )HEM АлгоритмПроцедура EM (в цикле):максимизация F по Q (тета зафиксированы)максимизация F по тета (Q фиксировано)E-step:M-step:EM алгоритм для смеси нормальныхраспределенийСмесь нормальныхраспределенийE StepM-StepПохоже по сути на k-means, но:Оценка не только мат.

ожидания, но и дисперсии (размер кластера) «перекрывающиеся» кластеры, лучше с выбросамиКластеризация на основесвязностиОсновные свойства:Произвольная форма кластеров Работа в условиях шума Один проход базы Недостаток: нужны параметры для «тонкой настройки»Популярные алгоритмы:DBSCAN: Ester, et al. (KDD’96) OPTICS: Ankerst, et al (SIGMOD’99). DENCLUE: Hinneburg & D.