Кластеризация графов и поиск сообществ. часть 1: введение, обзор инструментов и волосяные шары

Типология задач кластеризации

Типы входных данных

  • Признаковое описание объектов. Каждый объект описывается набором своих характеристик, называемых признаками. Признаки могут быть числовыми или нечисловыми.
  • Матрица расстояний между объектами. Каждый объект описывается расстояниями до всех остальных объектов метрического пространства.
  • между объектами. Учитывается степень сходства объекта с другими объектами выборки в метрическом пространстве. Сходство здесь дополняет расстояние (различие) между объектами до 1.

В современной науке применяется несколько алгоритмов обработки входных данных. Анализ путём сравнения объектов, исходя из признаков, (наиболее распространённый в биологических науках) называется Q-типом анализа, а в случае сравнения признаков, на основе объектов — R-типом анализа. Существуют попытки использования гибридных типов анализа (например, RQ-анализ), но данная методология ещё должным образом не разработана.

Цели кластеризации

  • Понимание данных путём выявления кластерной структуры. Разбиение выборки на группы схожих объектов позволяет упростить дальнейшую обработку данных и принятия решений, применяя к каждому кластеру свой метод анализа (стратегия «разделяй и властвуй»).
  • Сжатие данных. Если исходная выборка избыточно большая, то можно сократить её, оставив по одному наиболее типичному представителю от каждого кластера.
  • Обнаружение новизны (англ. novelty detection). Выделяются нетипичные объекты, которые не удаётся присоединить ни к одному из кластеров.

В первом случае число кластеров стараются сделать поменьше. Во втором случае важнее обеспечить высокую степень сходства объектов внутри каждого кластера, а кластеров может быть сколько угодно.
В третьем случае наибольший интерес представляют отдельные объекты, не вписывающиеся ни в один из кластеров.

Во всех этих случаях может применяться иерархическая кластеризация, когда крупные кластеры дробятся на более мелкие, те в свою очередь дробятся ещё мельче, и т. д. Такие задачи называются задачами таксономии. Результатом таксономии является древообразная иерархическая структура. При этом каждый объект характеризуется перечислением всех кластеров, которым он принадлежит, обычно от крупного к мелкому.

Методы кластеризации

Общепринятой классификации методов кластеризации не существует, но можно выделить ряд групп подходов (некоторые методы можно отнести сразу к нескольким группам и потому предлагается рассматривать данную типизацию как некоторое приближение к реальной классификации методов кластеризации):

  1. Вероятностный подход. Предполагается, что каждый рассматриваемый объект относится к одному из k классов. Некоторые авторы (например, А. И. Орлов) считают, что данная группа вовсе не относится к кластеризации и противопоставляют её под названием «дискриминация», то есть выбор отнесения объектов к одной из известных групп (обучающих выборок).
    • K-средних
    • К-медиан
    • EM-алгоритм
    • Алгоритмы семейства FOREL
    • Дискриминантный анализ
  2. Подходы на основе систем искусственного интеллекта: весьма условная группа, так как методов очень много и методически они весьма различны.
    • Метод нечеткой кластеризации C-средних (C-means)
    • Нейронная сеть Кохонена
    • Генетический алгоритм
  3. Логический подход. Построение дендрограммы осуществляется с помощью дерева решений.
  4. Теоретико-графовый подход.
  5. Иерархический подход. Предполагается наличие вложенных групп (кластеров различного порядка). Алгоритмы в свою очередь подразделяются на агломеративные (объединительные) и дивизивные (разделяющие). По количеству признаков иногда выделяют монотетические и политетические методы классификации.
  6. Другие методы. Не вошедшие в предыдущие группы.
    • Статистические алгоритмы кластеризации
    • Ансамбль кластеризаторов
    • Алгоритмы семейства KRAB
    • Алгоритм, основанный на методе просеивания
    • DBSCAN и др.

Подходы 4 и 5 иногда объединяют под названием структурного или геометрического подхода, обладающего большей формализованностью понятия близости. Несмотря на значительные различия между перечисленными методами все они опираются на исходную «гипотезу компактности»: в пространстве объектов все близкие объекты должны относиться к одному кластеру, а все различные объекты соответственно должны находиться в различных кластерах.

Применение[править]

Биология и биоинформатикаправить

  • В области экологии кластеризация используется для выделения пространственных и временных сообществ организмов в однородных условиях;
  • Кластерный анализ используется для группировки схожих геномных последовательностей в семейство генов, которые являются консервативными структурами для многих организмов и могут выполнять схожие функции;
  • Кластеризация помогает автоматически определять генотипы по различным частям хромосом;
  • Алгоритмы применяются для выделения небольшого числа групп генетических вариации человеческого генома.

Медицинаправить

  • Используется в позитронно-эмиссионной томографии для автоматического выделения различных типов тканей на трехмерном изображении;
  • Применяется для выявления шаблонов устойчивости к антибиотикам; для классификации антибиотиков по типу антибактериальной активности.

Маркетингправить

Кластеризация широко используется при изучении рынка для обработки данных, полученных из различных опросов.
Может применяться для выделения типичных групп покупателей, разделения рынка для создания персонализированных предложений, разработки новых линий продукции.

Компьютерные наукиправить

  • Кластеризация используется в сегментации изображений для определения границ и распознавания объектов;
  • Кластерный анализ применяется для определения образовавшихся популяционных ниш в ходе работы эволюционных алгоритмов для улучшения параметров эволюции;
  • Подбор рекомендаций для пользователя на основе предпочтений других пользователей в данном кластере;
  • Определение аномалий путем построения кластеров и выявления неклассифицированных объектов.

Типология задач кластеризации

Кластеризация графов и поиск сообществ. часть 1: введение, обзор инструментов и волосяные шарыВиды входных данных

  • Признаковое описание объектов. Каждый объект описывают набором собственных характеристик, которые называются признаками. Признаки могут быть нечисловыми или числовыми.
  • Матрица расстояний меж объектами. Каждый объект описывают расстояниями до всех других объектов метрического пространства.
  • Матрица сходства меж объектами. Учитывают степень сходства объекта с прочими объектами выборки в метрическом пространстве. Сходство тут дополняет различие (расстояние) меж объектами до 1.

В современной науке используется несколько алгоритмов обработки для входных данных. Анализ при помощи сравнения объектов, учитывая признаки, (наиболее распространённый в биологических науках) называется Q-видом анализа, а при сравнении признаков, на основании объектов — R-видом анализа. Есть попытки использовать гибридные типы анализа (к примеру, RQ-анализ), но эта методология ещё не разработана должным образом.

Цели кластеризации

  • Понимание данных при помощи выявления кластерной структуры. Разбиение выборки на группы похожих объектов дает возможность упростить обработку данных в дальнейшем и принятие решений, к каждому кластеру применяя собственный метод анализа (стратегия «разделяй и властвуй»).
  • Сжатие данных. Когда исходная выборка сильно большая, то можно её сократить, оставив от каждого кластера по одному самому типичному представителю.
  • Обнаружение новизны (англ. novelty detection). Выделяют нетипичные объекты, которые не получается ни к одному из кластеров присоединить.

Число кластеров в первом случае стараются делать поменьше. Во втором случае более важным будет обеспечить большую степень сходства объектов в каждом кластере, а кластеров может быть сколько угодно. Наибольший интерес в третьем случае представляют отдельные объекты, которые не вписываются ни в один из кластеров.

Во всех данных ситуациях может использоваться иерархическая кластеризация, когда большие кластеры дробят на более мелкие, те дробятся в свою очередь ещё мельче, и так далее. Такие задачи называют задачами таксономии. Итог таксономии — иерархическая древообразная структура. Каждый объект при этом характеризуется перечислением кластеров, которым он принадлежит, от крупного к мелкому.

Способы кластеризации

Общепринятой классификации способов кластеризации нет, однако возможно выделить некоторые группы подходов (некоторые способы возможно отнести сразу к нескольким группам и потому предлагают рассматривать эту типизацию в качестве некоторого приближения к реальной классификации способов кластеризации):

  1. Вероятностный подход. Предполагают, что каждый рассматриваемый объект относят к одному из k классов. Некоторые авторы (к примеру, А. И. Орлов) полагают, что эта группа совсем не относится к кластеризации и противопоставляют её «дискриминации», то есть выбору отнесения объектов к одной известной группе (обучающим выборкам).
    • Дискриминантный анализ
    • K-medians
    • K-средних (K-means)
    • Алгоритмы семейства FOREL
    • EM-алгоритм
  2. Подходы на основании систем искусственного интеллекта: условная группа, так как способов весьма много и они весьма различны методически.
    • Генетический алгоритм
    • Нейронная сеть Кохонена
    • Метод нечеткой кластеризации C-средних
  3. Логический подход. Построение дендрограммы производится при помощи дерева решений.
  4. Теоретико-графовый подход.
  5. Иерархический подход. Предполагают наличие вложенных групп (кластеров разного порядка). В свою очередь алгоритмы подразделяются на объединительные (агломеративные) и разделяющие (дивизивные). По числу признаков порой выделяют политетические и монотетические способы классификации.
  6. Прочие способы, которые не вошли в прошлые группы.
    • Ансамбль кластеризаторов
    • Статистические алгоритмы кластеризации
    • Алгоритм, который основан на способе просеивания
    • Алгоритмы семейства KRAB
    • DBSCAN и др.

Подходы 4 и 5 порой объединяют под названием геометрического или структурного подхода, который обладает большей формализованностью понятия близости. Невзирая на большие различия меж перечисленными способами все они опираются на начальную «гипотезу компактности»: в пространстве объектов все близкие объекты относятся к одному кластеру, а все разные объекты должны соответственно находиться в разных кластерах.

Псевдокод

Основной подход алгоритма OPTICS такой же, как у DBSCAN, но вместо поддержки множества известных, но ещё необработанных членов кластера, используется очередь с приоритетом (т.е. индексированная куча).

 OPTICS(DB, eps, MinPts)
    для каждой точки p из DB
       p.достижимое_расстояние=не_определено
    для каждой необработанной точки p из DB
       N=получитьСоседей (p, eps)
       помечаем p как обработанную
       помещаем p в упорядоченный список
       if (основное_расстояние (p, eps, Minpts) != не_определено)
          Seeds=пустая приоритетная очередь
          обновить(N, p, Seeds, eps, Minpts)
          for each next q in Seeds
             N'=получитьСоседей(q, eps)
             помечаем q как обработанную
             поместить q в упорядоченный список
             if (основное_расстояние(q, eps, Minpts) != не_определено)
                обновить(N', q, Seeds, eps, Minpts)

В процедуре обновить(), приоритетная очередь Seeds обновляется по ε{\displaystyle \varepsilon }-соседям точек p{\displaystyle p} иq{\displaystyle q} соответственно:

 обновить (N, p, Seeds, eps, Minpts)
    coredist=достижимое_расстояние(p, eps, MinPts)
    для каждого o в N
       если (o не обработана)
          основное_расстояние=max(coredist, dist(p,o))
          if (o. достижимое_расстояние == не_определено) // точка o не в Seeds
              o. достижимое_расстояние=новое_дост_раст
              Seeds.вставить(o, новое_дост_раст)
          иначе               // точка o в Seeds, проверить на улучшение
              если (новое_дост_раст < o.достижимое_расстояние)
                 o. достижимое_расстояние=новое_дост_раст
                 Seeds.перенести(o, новое_дост_раст)

OPTICS помещает точки в определённом порядке, помечая их наименьшим достижимым расстоянием (в оригинальном алгоритме основное расстояние также запоминается, но это не требуется для дальнейшей обработки).

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

  1. Жамбю М. Иерархический кластер-анализ и соответствия. — М.: Финансы и статистика, 1988. — 345 с.
  2. Классификация и кластер. Под ред. Дж. Вэн Райзина. М.: Мир, 1980. 390 с.
  3. Sneath P.H.A., Sokal R.R. Numerical taxonomy: The principles and practices of numerical classification. — San-Francisco: Freeman, 1973. — 573 p.
  4. Ward J.H. Hierarchical grouping to optimize an objective function // J. of the American Statistical Association, 1963. — 236 р.
  5. Айвазян С. А., Бухштабер В. М., Енюков И. С., Мешалкин Л. Д. Прикладная статистика: Классификация и снижение размерности. — М.: Финансы и статистика, 1989. — 607 с.
  6. Lance G.N., Willams W.T. A general theory of classification sorting strategies. 1. Hierarchical systems // Comp. J. 1967. № 9. P. 373—380.
  7. Терентьев П. В. Метод корреляционных плеяд // Вестн. ЛГУ. № 9. 1959. С. 35-43.
  8. Терентьев П. В. Дальнейшее развитие метода корреляционных плеяд // Применение математических методов в биологии. Т. 1. Л.: 1960. С. 42-58.
  9. Выханду Л. К. Об исследовании многопризнаковых биологических систем // Применение математических методов в биологии. Л.: вып. 3. 1964. С. 19-22.
  10. Штейнгауз Г. Математический калейдоскоп. — М.: Наука, 1981. — 160 с.
  11. Florek K., Lukaszewicz S., Percal S., Steinhaus H., Zubrzycki S. Taksonomia Wroclawska // Przegl. antropol. 1951. T. 17. S. 193—211.
  12. Czekanowski J. Zur differential Diagnose der Neandertalgruppe // Korrespbl. Dtsch. Ges. Anthropol. 1909. Bd 40. S. 44-47.
  13. Василевич В. И. Статистические методы в геоботанике. — Л.: Наука, 1969. — 232 с.

K-средства кластеризации

Алгоритмы K-Means чрезвычайно просты в реализации и очень эффективны в вычислительном отношении. Это основные причины, объясняющие их популярность. Но они не очень хорошо выделяют классы в группах, которые не являются сферическими.

Алгоритмы K-Means направлены на поиск и группирование в классах точек данных, которые имеют высокое сходство между ними. В терминах алгоритма это сходство понимается как противоположность расстояния между точками данных. Чем ближе точки данных, тем больше они похожи и с большей вероятностью будут принадлежать к одному кластеру.

Ключевые идеи

Квадрат Евклидова Расстояние

Наиболее часто используемое расстояние в K-средних означает квадрат Евклидова расстояния. Пример этого расстояния между двумя точками х и у в т-мерное пространство это:

Кластеризация графов и поиск сообществ. часть 1: введение, обзор инструментов и волосяные шары

Вот, J это -я измерение (или столбец элементов) точек выборки х и у.

Кластерная инерция

Инерция кластера — это имя, данное сумме квадратичных ошибок в контексте кластеризации, и представлено следующим образом:

Кластеризация графов и поиск сообществ. часть 1: введение, обзор инструментов и волосяные шары

куда μ (к) центр тяжести кластера J, а также ш (I, J) 1, если образец х (я) находится в кластере J и 0 в противном случае.

K-средние можно понимать как алгоритм, который попытается минимизировать коэффициент инерции кластера.

Шаги алгоритма

  1. Во-первых, нам нужно выбрать k, количество кластеров, которые мы хотим найти.
  2. Затем алгоритм случайным образом выберет центроиды каждого кластера.
  3. Он будет назначен каждой точке данных ближайшему центроиду (с использованием евклидова расстояния).
  4. Будет вычислена инерция кластера.
  5. Будут вычисляться новые центроиды как среднее значение точек, которые принадлежат центроиду предыдущего шага. Другими словами, вычисляя минимальную квадратичную ошибку точек данных к центру каждого кластера, перемещая центр к этой точке
  6. Вернуться к шагу 3.

Гиперпараметры K-средних

  • Количество кластеров: количество кластеров и центроидов для генерации.
  • Максимум итераций: алгоритма за один прогон.
  • Начальное число: количество раз, когда алгоритм будет работать с разными семенами центроидов. Конечный результат будет наилучшим результатом числа, определенного последовательных прогонов, с точки зрения инерции.

Вызовы K-Means

  • Выходные данные для любого фиксированного обучающего набора не всегда будут одинаковыми, потому что начальные центроиды установлены случайным образом, и это повлияет на весь процесс алгоритма.
  • Как указывалось ранее, из-за характера евклидова расстояния он не подходит для работы с кластерами, которые принимают несферические формы.

Точки, которые следует учитывать при применении K-средних

  • Элементы должны измеряться в одной и той же шкале, поэтому может потребоваться выполнить стандартизацию по z-шкале или максимально-минимальное масштабирование.
  • При работе с категориальными данными мы будем использовать функцию get dummies.
  • Исследовательский анализ данных (EDA) очень полезен для обзора данных и определения того, является ли K-Means наиболее подходящим алгоритмом.
  • Метод мини-пакета очень полезен при большом количестве столбцов, однако он менее точен.

Как правильно выбрать номер K

Выбор правильного количества кластеров является одним из ключевых моментов алгоритма K-Means. Чтобы найти это число есть несколько методов:

  • Полевые знания
  • Решение для бизнеса
  • Метод локтя

Будучи согласованным с мотивацией и природой Data Science, метод локтя является предпочтительным вариантом, так как он принимает аналитический метод, опирающийся на данные, для принятия решения.

Метод локтя

Метод локтя используется для определения правильного количества кластеров в наборе данных. Он работает путем построения графиков возрастающих значений K в сравнении с общей ошибкой, полученной при использовании этого K.

Кластеризация графов и поиск сообществ. часть 1: введение, обзор инструментов и волосяные шары

Цель состоит в том, чтобы найти k, который для каждого кластера не будет значительно увеличивать дисперсию

Кластеризация графов и поиск сообществ. часть 1: введение, обзор инструментов и волосяные шары

В этом случае мы выберем k = 3, где находится колено.

Ограничения K-средних

Хотя K-Means является отличным алгоритмом кластеризации, он наиболее полезен, когда мы заранее знаем точное количество кластеров и когда имеем дело с распределениями сферической формы.

На следующем рисунке показано, что мы получили бы, если бы использовали кластеризацию K-средних в каждом наборе данных, даже если мы заранее знали точное количество кластеров:

Кластеризация графов и поиск сообществ. часть 1: введение, обзор инструментов и волосяные шары

Весьма распространено использовать алгоритм K-Means в качестве эталона для оценки производительности других методов кластеризации.

Кластеризация на основе соединений

Кластеризация графов и поиск сообществ. часть 1: введение, обзор инструментов и волосяные шары

Данное объединение также известно по такому названию, как иерархическая модель. Она основана на типичной идее о том, что объекты в большей степени связаны с соседними частями, чем с теми, которые находятся намного дальше. Эти алгоритмы соединяют предметы, образуя различные кластеры, в зависимости от их расстояния. Группа может быть описана в основном максимальной дистанцией, которая необходима для соединения различных частей кластера. На всевозможных расстояниях будут образовываться другие группы, которые можно представить с помощью дендрограммы. Это объясняет, откуда происходит общее название «иерархическая кластеризация». То есть эти алгоритмы не обеспечивают единого разделения набора данных, а вместо этого предоставляют обширный порядок подчинения. Именно благодаря ему происходит слив друг с другом на определенных расстояниях. В дендрограмме ось Y обозначает дистанцию, на которой кластеры объединяются. А объекты располагаются вдоль прямой X так, что группы не смешиваются.

Кластеризация на основе соединений — это целое семейство методов, которые отличаются способом вычисления расстояний. Помимо обычного выбора функций дистанции пользователю также необходимо определиться с критерием связи. Так как кластер состоит из нескольких объектов, есть множество вариантов для его вычисления. Популярный выбор известен как однорычажная группировка, именно это метод полной связи, который содержит UPGMA или WPGMA (невзвешенный или взвешенный ансамбль пар со средним арифметическим, также известный как кластеризация средней связи). Кроме того, иерархическая система может быть агломерационной (начиная с отдельных элементов и объединяя их в группы) или делительной (начиная с полного набора данных и разбивая его на разделы).

Зачем нужна кластеризация

С помощью автоматических кластеризаторов можно быстро группировать даже самые большие семантические ядра. Если раньше на разборку ядра уходили недели и месяцы, то благодаря кластеризаторам работа сокращается до пары часов. Большим плюсом кластеризации является распределение запросов по страницам таким образом, чтобы их было возможно одновременно продвинуть. Сложно представить ручной аналог кластеризации высокой точности, так как даже опытный оптимизатор совершает до 30% ошибочных распределений. Из этого следует, что кластеризация ключевых слов необходима практически в любом случае.

Когда я был вебмастером-чайником, я делал сайт, где под каждый запрос была отдельная статья. Конечно же, трафика он не получал — получился только фейл. И это проблема реально многих начинающих — неправильные запросы или неправильная кластеризация.

Алгоритм CLOPE

Пусть имеется база транзакций D, состоящая из множества транзакций \{ t_1,t_2,…,t_n \}. Каждая транзакция есть набор объектов \{ i_1,…,i_m \}. Множество кластеров \{ C_1,…,C_k \} есть разбиение множества \{ t_1,…,t_n \}, такое, что C_1…C_k = \{ t_1,…,t_n \} и C_i\neq \varnothing \wedge C_i \bigcap C_j = \varnothing, для 1<=i, j<=k. Каждый элемент C_i называется кластером, n, m, k — количество транзакций, количество объектов в базе транзакций и число кластеров соответственно.

Каждый кластер C имеет следующие характеристики:

  • D(C) — множество уникальных объектов;
  • Occ(i,C) — количество вхождений (частота) объекта i в кластер C;
  • S(C)=\sum_{i\in\ D(C)}\ Occ\ (i, C)=\sum_{t_i\in C}\mid t_i \mid;
  • W (C) = | D (C) |;
  • H(C)=S(C)/W(C).

Гистограммой кластера C называется графическое изображение его расчетных характеристик: по оси OX откладываются объекты кластера в порядке убывания величины Occ(i,C), а сама величина Occ(i,C) — по оси OY (рис. 2).

Рисунок 2. Иллюстрация гистограммы кластера

На рис. 2 S(C)=8, соответствует площади прямоугольника, ограниченного осями координат и пунктирной линией. Очевидно, что чем больше значение H, тем более «похожи» две транзакции. Поэтому алгоритм должен выбирать такие разбиения, которые максимизируют H.

Однако учитывать одно только значение высоты H недостаточно. Возьмем базу, состоящую из 2-х транзакций: \{ abc,def \}. Они не содержат общих объектов, но разбиение \{ \{abc,def \} \} и разбиение \{ \{ abc \}, \{ def \} \} характеризуются одинаковой высотой H=1. Получается, оба варианта разбиения равноценны. Но если для оценки вместо H(C) использовать градиент G(C)=H(C)/W(C)=S(C)/W(C)^2, то разбиение \{ \{ abc \}, \{ def \} \} будет лучше (градиент каждого кластера равен 1/3 против 1/6 у разбиения \{ \{ abc,def \} \}).

Обобщив вышесказанное, запишем формулу для вычисления глобального критерия – функции стоимости Profit(C):

Profit (C) = \frac {\sum_{i=1}^k G(C_i)\times\mid C_i\mid}{\sum_{i=1}^k \mid C_i\mid}=\frac {\sum_{i=1}^k \frac{S(C_i)}{W(C_i)^r}\times\mid C_i\mid}{\sum_{i=1}^k \mid C_i\mid}

где:

  • |Ci| — количество транзакций в i-том кластере
  • k — количество кластеров
  • r — положительное вещественное число большее 1.

С помощью параметра r, названного авторами CLOPE коэффициентом отталкивания (repulsion), регулируется уровень сходства транзакций внутри кластера, и, как следствие, финальное количество кластеров. Этот коэффициент подбирается пользователем. Чем больше r, тем ниже уровень сходства и тем больше кластеров будет сгенерировано.

Формальная постановка задачи кластеризации алгоритмом CLOPE выглядит следующим образом: для заданных D и r найти разбиение C: Profit(C,r) -> max.

Гауссовые модели смесей (GMM)

Модели гауссовой смеси — это вероятностные модели, которые предполагают, что все выборки генерируются из смеси конечного числа гауссовского распределения с неизвестными параметрами.

Он принадлежит к группе мягких алгоритмов кластеризации, в которой каждая точка данных будет принадлежать каждому кластеру, существующему в наборе данных, но с различными уровнями принадлежности к каждому кластеру. Это членство присваивается как вероятность принадлежности к определенному кластеру в диапазоне от 0 до 1.

Например, выделенная точка будет принадлежать кластерам A и B одновременно, но с более высоким членством в группе A из-за ее близости к ней.

Кластеризация графов и поиск сообществ. часть 1: введение, обзор инструментов и волосяные шары

GMM является одним из наиболее продвинутых методов кластеризации, который мы будем изучать в этой серии, он предполагает, что каждый кластер следует вероятностному распределению, которое может быть гауссовым или нормальным. Это обобщение кластеризации K-средних, включающее информацию о ковариационной структуре данных, а также о центрах латентных гауссианов.

Кластеризация графов и поиск сообществ. часть 1: введение, обзор инструментов и волосяные шары

Распределение GMM в одном измерении

GMM будет искать гауссовские распределения в наборе данных и смешивать их.

Кластеризация графов и поиск сообществ. часть 1: введение, обзор инструментов и волосяные шары

GMM в двух измерениях

При наличии многомерного распределения в качестве следующего, средний центр будет µ + σ для каждой оси распределения набора данных.

Алгоритм GMM

Это алгоритм максимизации ожидания, процесс которого можно суммировать следующим образом:

  1. Инициализируйте K гауссовых распределений. Это делается с помощью значений µ (среднее) и σ (стандартное отклонение). Они могут быть взяты из набора данных (наивный метод) или путем применения K-средних.
  2. Мягкая кластеризация данных: это фаза «ожидания», в которой все точки данных будут назначаться каждому кластеру с соответствующим уровнем членства.
  3. Переоцените гауссиан: это фаза «максимизации», в которой проверяются ожидания, и они используются для расчета новых параметров для гауссиан: новые µ и σ.
  4. Оцените логарифмическую вероятность данных для проверки на сходимость. Чем выше логарифмическая правдоподобность, тем более вероятно, что смесь созданной нами модели, вероятно, будет соответствовать нашему набору данных. Итак, это функция максимизировать.
  5. Повторите с шага 2 до сходимости.

Преимущества GMM

  • Это метод мягкой кластеризации, который присваивает выборочные члены для нескольких кластеров. Эта характеристика делает его самым быстрым алгоритмом для изучения моделей смесей
  • Существует высокая гибкость в количестве и форме кластеров.

Недостатки GMM

  • Он очень чувствителен к начальным значениям, что значительно обуславливает его производительность.
  • GMM может сходиться к локальному минимуму, который был бы неоптимальным решением.
  • При недостаточном количестве точек на смесь алгоритм расходится и находит решения с бесконечной вероятностью, если только мы искусственно не упорядочим ковариации между точками данных.

Задачи и условия

Кластерный анализ выполняет следующие основные задачи:

  • Разработка типологии или классификации.
  • Исследование полезных концептуальных схем группирования объектов.
  • Порождение гипотез на основе исследования данных.
  • Проверка гипотез или исследования для определения, действительно ли типы (группы), выделенные тем или иным способом, присутствуют в имеющихся данных.

Независимо от предмета изучения применение кластерного анализа предполагает следующие этапы:

  • Отбор выборки для кластеризации. Подразумевается, что имеет смысл кластеризовать только количественные данные.
  • Определение множества переменных, по которым будут оцениваться объекты в выборке, то есть признакового пространства.
  • Вычисление значений той или иной меры сходства (или различия) между объектами.
  • Применение метода кластерного анализа для создания групп сходных объектов.
  • Проверка достоверности результатов кластерного решения.

Можно встретить описание двух фундаментальных требований, предъявляемых к данным — однородность и полнота. Однородность требует, чтобы все кластеризуемые сущности были одной природы, описывались сходным набором характеристик. Если кластерному анализу предшествует факторный анализ, то выборка не нуждается в «ремонте» — изложенные требования выполняются автоматически самой процедурой факторного моделирования (есть ещё одно достоинство — z-стандартизация без негативных последствий для выборки; если её проводить непосредственно для кластерного анализа, она может повлечь за собой уменьшение чёткости разделения групп). В противном случае выборку нужно корректировать.

Методика сравнения

Суть сравнения сервисов в следующем: выбрать идеально кластеризованный список запросов – эталонное ядро. Сравнить результаты кластеризации каждого сервиса с эталонным.

Важно было хорошо составить такое эталонное ядро. Поскольку у нас контентный проект и большая часть контента – это вопросы и ответы пользователей, то материала для сбора статистики по проекту предостаточно

Было взято ядро на 2500+ ключевых фраз, которое отслеживается уже много месяцев. Из него выбраны только запросы вышедшие в топ-5 Яндекса. И из них взяты только те которые имеют релевантной страницу одного из широких разделов (категория вопроса, тема вопроса, категория документа, страница с формой «задать вопрос»), а не узкую страницу вопроса с ответами. Запросы были сгруппированы по релевантной странице. Оставлены только группы в которых более чем 4 запроса. В итоге получилось 292 запроса разбитых на 22 кластера.

Забегая вперед скажу, что сравнивались результаты кластеризации по Московской выдаче Яндекса и без геопривязки. Региональная московская выдача показала себя лучше, поэтому далее будем говорить про нее.

Михаил Фирсов
Оцените автора
( Пока оценок нет )
Добавить комментарий