Алгоритмы кластеризации на службе Data Mining. Методы кластерного анализа. Иерархические методы

Мы выпустили новую книгу «Контент-маркетинг в социальных сетях: Как засесть в голову подписчиков и влюбить их в свой бренд».

Кластеризация семантического ядра - это разделение множества разнородных запросов на группы по смыслу.

Больше видео на нашем канале - изучайте интернет-маркетинг с SEMANTICA

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

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

Этапы кластеризации:

Получение выборки объектов для группировки.
Задание перечня критериев оценки объектов в выборке.
Определение степени сходства между анализируемыми объектами.
Проведение кластерного анализа для формирования групп объектов.
Представление результатов кластеризации.

Зачем нужно проводить кластеризацию СЯ

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

Кластеризация семантического ядра позволяет получить:

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

Что происходит, если не проводить кластеризацию

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

Вот перечень проблем, которые возникнут после некорректной группировки ключей:

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

Устранение и предупреждение подобных проблем - это главный ответ на вопрос: "зачем делать кластеризацию ся".

Алгоритмы кластеризации

SEO-специалисты выделяют два типа классификации алгоритмов кластеризации:

Иерархические и плоские

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

Плоские алгоритмы формируют одно разделение объектов на группы.

Четкие и нечеткие

Четкие алгоритмы связывают каждый элемент выборки с номером кластера. Нечеткие алгоритмы связывают каждый элемент выборки с комбинацией вещественных значений, отражающих меру принадлежности элемента к кластерам. Таким образом каждый элемент выборки относится к каждой группе с определенной долей вероятности.

Как провести кластеризацию запросов вручную

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

Представленные инструменты имеют ряд достоинств:

Универсальность - производят группировку с учетом множества разных критериев;
Высокая точность обработки;
LibreOffice, OpenOffice - бесплатные.

В числе их недостатков:

Необходимость периодических бекапов;
Низкая скорость обработки;
Лицензионный Excel - платный.

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

Автоматизированная кластеризация ся

Разделение семантического ядра на группы происходит автоматически.

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

Обойти эту проблему может полуавтоматический способ группировки поисковых запросов. Для этого специалисту необходимо самостоятельно подобрать группы по полученным запросам. А автоматизированная система сама разделит запросы по указанным пользователем группам. Такой подход позволяет существенно минимизировать ошибки машинного алгоритма.

Как провести кластеризацию запросов с помощью Key Collector

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

Схема работы Key Collector достаточно проста. Чтобы разделить все полученные запросы, необходимо воспользоваться опцией «Анализ групп». При этом системе нужно указать режим кластеризации ("по отдельным словам", "по составу фраз", "по поисковой выдаче", "по составу фраз и поисковой выдаче"). Режим "по отдельным словам" группирует поисковые запросы, у которых присутствует совпадение даже по одному слову. Режим "по составу фраз" ориентируется на строение ключевых фраз. Это наиболее подходящий способ разбиения большого количества запросов. Режим "по поисковой выдаче" группирует ключевые фразы по количеству совпавших ссылок в результатах поиска. Режим "по составу фраз и поисковой выдаче" сочетает в себе два предыдущих критерия.

Пример кластеризации семантического ядра в системе Key Collector:

Чтобы оценить группы, которые получились, их можно выгрузить в табличный редактор (например в Excel).

С понятием кластеризации мы познакомились в первом разделе курса. В этой лекции мы опишем понятие " кластер " с математической точки зрения, а также рассмотрим методы решения задач кластеризации - методы кластерного анализа.

Термин кластерный анализ , впервые введенный Трионом (Tryon) в 1939 году, включает в себя более 100 различных алгоритмов.

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

Кластерный анализ позволяет сокращать размерность данных, делать ее наглядной.

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

Кластерный анализ параллельно развивался в нескольких направлениях, таких как биология, психология, др., поэтому у большинства методов существует по два и более названий. Это существенно затрудняет работу при использовании кластерного анализа.

Задачи кластерного анализа можно объединить в следующие группы:

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

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

Рассмотрим пример процедуры кластерного анализа.

Допустим, мы имеем набор данных А, состоящий из 14-ти примеров, у которых имеется по два признака X и Y. Данные по ним приведены в таблице 13.1 .

Таблица 13.1. Набор данных А

№ примера	признак X	признак Y
1	27	19
2	11	46
3	25	15
4	36	27
5	35	25
6	10	43
7	11	44
8	36	24
9	26	14
10	26	14
11	9	45
12	33	23
13	27	16
14	10	47

Данные в табличной форме не носят информативный характер. Представим переменные X и Y в виде диаграммы рассеивания, изображенной на рис. 13.1 .

Рис. 13.1.

На рисунке мы видим несколько групп "похожих" примеров. Примеры (объекты), которые по значениям X и Y "похожи" друг на друга, принадлежат к одной группе (кластеру); объекты из разных кластеров не похожи друг на друга.

Критерием для определения схожести и различия кластеров является расстояние между точками на диаграмме рассеивания. Это сходство можно "измерить", оно равно расстоянию между точками на графике. Способов определения меры расстояния между кластерами, называемой еще мерой близости, существует несколько. Наиболее распространенный способ - вычисление евклидова расстояния между двумя точками i и j на плоскости, когда известны их координаты X и Y:

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

Когда осей больше, чем две, расстояние рассчитывается таким образом: сумма квадратов разницы координат состоит из стольких слагаемых, сколько осей (измерений) присутствует в нашем пространстве. Например, если нам нужно найти расстояние между двумя точками в пространстве трех измерений (такая ситуация представлена на рис. 13.2), формула (13.1) приобретает вид:

Рис. 13.2.

Кластер имеет следующие математические характеристики : центр , радиус , среднеквадратическое отклонение , размер кластера .

Центр кластера - это среднее геометрическое место точек в пространстве переменных.

Радиус кластера - максимальное расстояние точек от центра кластера .

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

Спорный объект - это объект , который по мере сходства может быть отнесен к нескольким кластерам.

Размер кластера может быть определен либо по радиусу кластера , либо по среднеквадратичному отклонению объектов для этого кластера. Объект относится к кластеру, если расстояние от объекта до центра кластера меньше радиуса кластера . Если это условие выполняется для двух и более кластеров, объект является спорным .

Неоднозначность данной задачи может быть устранена экспертом или аналитиком.

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

Выбор масштаба в кластерном анализе имеет большое значение . Рассмотрим пример. Представим себе, что данные признака х в наборе данных А на два порядка больше данных признака у: значения переменной х находятся в диапазоне от 100 до 700, а значения переменной у - в диапазоне от 0 до 1.

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

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

заключается в оптимизации меры близости и количества записей для усреднения на основе генетических алгоритмов. Алгоритм MR используется для предсказания значений числовых переменных и категориальных переменных, включая текстовые (string data type), а также для классификации на два или несколько классов.

Алгоритмы кластеризации

Find Dependencies (FD) - N-мерный анализ распределений

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

Алгоритм работает очень быстро и способен обрабатывать большие объемы данных. Его можно использовать как препроцессор для алгоритмов FL, PN, LR, так как он уменьшает пространство поиска, а также как фильтр отскочивших точек или, в обратной постановке, как детектор исключений. FD создает правило табличного вида, однако, как и все правила PolyAnalyst, оно может быть вычислено для любой записи таблицы.

Find Clusters (FC) - N-мерный кластеризатор

Этот метод применяется тогда, когда надо выделить в некотором множестве данных компактные типичные подгруппы (кластеры), состоящие из близких по своим характеристикам записей. Алгоритм FC сам определяет набор переменных, для которых разбиение наиболее значимо. Результатом работы алгоритма является описание областей (диапазонов значений переменных), характеризующих каждый обнаруженный кластер, и разбиение исследуемой таблицы на подмножества, соответствующие кластерам. Если данные являются достаточно однородными по всем своим переменным и не содержат "сгущений" точек в каких-то областях, этот метод не даст результатов. Надо отметить, что минимальное число обнаруживаемых кластеров равно двум - сгущение точек только в одном месте в данном алгоритме не рассматривается как кластер. Кроме того, этот метод в большей степени, чем остальные, предъявляет требования к наличию достаточного количества записей в исследуемой таблице, а именно: минимальное количество записей в таблице, в которой может быть обнаружено N кластеров, равно (2N-1)4.

Алгоритмы классификации

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

Classify (CL) - классификатор на основе нечеткой логики

Алгоритм CL предназначен для классификации записей на два класса. В основе его работы лежит построение так называемой функции принадлежности и нахождения порога разделения на классы. Функция принадлежности принимает значения от окрестности 0 до окрестности 1. Если возвращаемое значение функции для данной записи больше порога,

то эта запись принадлежит к классу "1", если меньше, то классу "0" соответственно. Целевая переменная для этого модуля должна быть логического типа.

Discriminate (DS) - дискриминация

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

Decision Tree (DT) - дерево решений

В системе PolyAnalyst реализован алгоритм, основанный на критерии максимизации взаимной информации (information gain). То есть для расщепления выбирается независимая переменная, несущая максимальную (в смысле Шеннона) информацию о зависимой переменной. Этот критерий имеет ясную интерпретацию и дает разумные результаты при самых разнообразных статистических параметрах изучаемых данных. Алгоритм DT является одним из самых быстрых в PolyAnalyst.

Decision Forest (DF) - леса решений

В случае, когда зависимая переменная может принимать большое количество разных значений, применение метода деревьев решений становится неэффективным. В такой ситуации в системе PolyAnalyst применяется метод, называемый лесом решений (decision forest). При этом строится совокупность деревьев решений - по одному для каждого различного значения зависимой переменной. Результатом прогноза, основанного на лесе решений, является то значение зависимой переменной, для которой соответствующее дерево дает наиболее вероятную оценку.

Алгоритмы ассоциации

Market Basket Analysis (BA) - метод анализа "корзины покупателя"

Название этого метода происходит от задачи определения вероятности, какие товары покупаются совместно. Однако реальная область его применения значительно шире. Например, продуктами можно считать страницы в Интернете, или те или иные характеристики клиента, или ответы респондентов в социологических и маркетинговых исследованиях и т.д. Алгоритм BA получает на вход бинарную матрицу, в которой строка - это одна корзина (кассовый чек, например), а столбцы заполнены логическими 0 и 1, обозначающими наличие или отсутствие данного признака (товара). На выходе формируются кластеры совместно встречаемых признаков с оценкой их вероятности и достоверности. Кроме этого, формируются ассоциативные направленные правила типа: если признак "А", то с такой-то вероятностью еще и признак "В" и еще признак "С". Алгоритм ВА в PolyAnalyst работает исключительно быстро и способен обрабатывать огромные массивы данных.

Transactional Basket Analysis (TB) - транзакционный анализ "корзины"

Transactional Basket Analysis - это модификация алгоритма BA, применяемый для анализа очень больших данных, что не редкость для этого типа задач. Он предполагает, что каждая запись в базе данных соответствует одной транзакции, а не одной корзине (набору купленных за одну операцию товаров). На основе этого алгоритма компания "Мегапьютер" создала отдельный продукт - X-SellAnalyst, предназначенный для on-line рекомендации продуктов в Интернет-магазинах.

Модули текстового анализа

В системе PolyAnalyst реализована интеграция инструментов Data Mining с методами анализа текстов на естественном языке - алгоритмов Text Mining. Иллюстрация работы модулей текстового анализа показана на рис. 24.3 .

Рис. 24.3. Иллюстрация работы модулей текстового анализа

Text Analysis (ТА) - текстовый анализ

Text Analysis представляет собой средство формализации неструктурированных текстовых полей в базах данных. При этом текстовое поле представляется как набор булевых признаков, основанных на наличии и/или частоте данного слова, устойчивого словосочетания или понятия (с учетом отношений синонимии и "общее-частное") в данном тексте. Тем самым появляется возможность распространить на текстовые поля всю мощь алгоритмов Data Mining, реализованных в системе PolyAnalyst. Кроме того, этот метод может быть использован для лучшего понимания текстовой компоненты данных за счет автоматического выделения наиболее распространенных ключевых понятий.

Text Categorizer (TC) - каталогизатор текстов

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

Link Terms (LT) - связь понятий

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

В PolyAnalyst встроены алгоритмы работы с текстовыми данными двух видов:

1. Алгоритмы, извлекающие ключевые понятия и работающие с ними.

2. Алгоритмы, сортирующие тексты на классы, которые определяются пользователем с помощью языка запросов.

Первый вид алгоритмов работает только с текстами на английском языке - при этом используется специальный словарь понятий английского языка. Алгоритмы второго типа могут работать с текстами и на английском, и на русском языках.

Text OLAP (матрицы измерений) иTaxonomies (таксономии) - это похожие друг на друга методы категоризации текстов. В Text OLAP пользователь создает именованные столбцы (измерения), состоящие из текстовых запросов. Например: "[добыча] и [нефть] и не ([руда] или [уголь] или [газ])". В процессе работы алгоритма PolyAnalyst применяет каждое из условий к каждому документу в базе данных и в случае удовлетворения условия относит этот документ к соответствующей категории. После работы модуля пользователь может выбирать различные элементы матрицы измерений и просматривать на экране тексты, удовлетворяющие выбранным условиям. Найденные слова будут в этих документах подкрашены разным цветом.

Работа с таксономиями очень похожа на работу с Text OLAP, только здесь пользователь строит иерархическую структуру из таких же условий, как и в матрицах измерений. Система пытается соотнести каждый документ с узлами этого дерева. После работы модуля пользователь также может перемещаться по узлам наполненной таксономии, просматривая отфильтрованные документы с подкрашенными словами.

Матрицы измерений и таксономии дают возможность пользователю взглянуть на коллекцию его документов под самыми разными углами. Но это не все: на основе этих объектов можно делать и другие, более сложные методы анализа, (например, анализ связей (Link Analysis), который показывает, насколько связаны друг с другом различные категории текстов, описанные пользователем) или включать тексты как независимые сущности в другие методы линейного и нелинейного анализа. Все это приводит к плотной интеграции подходов Data Mining и Text Mining в единую концепцию анализа информации.

Визуализация

В PolyAnalyst имеется богатый набор инструментов для графического представления и анализа данных и результатов исследований. Данные могут представляться в различных

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

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

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

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

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

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

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

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

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

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

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

Функции расстояния

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

Статистические алгоритмы кластеризации
Иерархическая кластеризация или таксономия

Формальная постановка задачи кластеризации

Пусть - множество объектов, - множество номеров (имён, меток) кластеров. Задана функция расстояния между объектами . Имеется конечная обучающая выборка объектов . Требуется разбить выборку на непересекающиеся подмножества, называемые кластерами , так, чтобы каждый кластер состоял из объектов, близких по метрике , а объекты разных кластеров существенно отличались. При этом каждому объекту приписывается номер кластера .

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

Кластеризация (обучение без учителя) отличается от классификации (обучения с учителем) тем, что метки исходных объектов изначально не заданы, и даже может быть неизвестно само множество .

Решение задачи кластеризации принципиально неоднозначно, и тому есть несколько причин:

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

Ссылки

Воронцов К.В. Математические методы обучения по прецедентам . МФТИ (2004), ВМиК МГУ (2007).
Сергей Николенко. Слайды лекций «Алгоритмы кластеризации 1» и «Алгоритмы кластеризации 2» . Курс «Самообучающиеся системы» .

Литература

Айвазян С. А., Бухштабер В. М., Енюков И. С., Мешалкин Л. Д. Прикладная статистика: классификация и снижение размерности. - М.: Финансы и статистика, 1989.
Журавлев Ю. И., Рязанов В. В., Сенько О. В. «Распознавание». Математические методы. Программная система. Практические применения. - М.: Фазис, 2006. .
Загоруйко Н. Г. Прикладные методы анализа данных и знаний. - Новосибирск: ИМ СО РАН, 1999. .
Мандель И. Д. Кластерный анализ. - М.: Финансы и статистика, 1988. .
Шлезингер М., Главач В. Десять лекций по статистическому и структурному распознаванию. - Киев: Наукова думка, 2004. .
Hastie T., Tibshirani R., Friedman J. The Elements of Statistical Learning. - Springer, 2001. .

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

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

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

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

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

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

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

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

Формальная постановка задачи кластеризации

Литература

Айвазян С. А., Бухштабер В. М., Енюков И. С., Мешалкин Л. Д. Прикладная статистика: классификация и снижение размерности. - М.: Финансы и статистика, 1989.
Журавлев Ю. И., Рязанов В. В., Сенько О. В. «Распознавание». Математические методы. Программная система. Практические применения. - М.: Фазис, 2006. ISBN 5-7036-0108-8.
Загоруйко Н. Г. Прикладные методы анализа данных и знаний. - Новосибирск: ИМ СО РАН, 1999. ISBN 5-86134-060-9.
Мандель И. Д. Кластерный анализ. - М.: Финансы и статистика, 1988. ISBN 5-279-00050-7.
Шлезингер М., Главач В. Десять лекций по статистическому и структурному распознаванию. - Киев: Наукова думка, 2004. ISBN 966-00-0341-2.
Hastie T., Tibshirani R., Friedman J. The Elements of Statistical Learning. - Springer, 2001. ISBN 0-387-95284-5.
Jain, Murty, Flynn Data clustering: a review . // ACM Comput. Surv. 31 (3) , 1999

Внешние ссылки

На русском языке

www.MachineLearning.ru - профессиональный вики-ресурс, посвященный машинному обучению и интеллектуальному анализу данных
С. Николенко. Слайды лекций по алгоритмам кластеризации

На английском языке

COMPACT - Comparative Package for Clustering Assessment . A free Matlab package, 2006.
P. Berkhin, Survey of Clustering Data Mining Techniques , Accrue Software, 2002.
Jain, Murty and Flynn: Data Clustering: A Review , ACM Comp. Surv., 1999.
for another presentation of hierarchical, k-means and fuzzy c-means see this introduction to clustering . Also has an explanation on mixture of Gaussians.
David Dowe, Mixture Modelling page - other clustering and mixture model links.
a tutorial on clustering
The on-line textbook: Information Theory, Inference, and Learning Algorithms , by David J.C. MacKay includes chapters on k-means clustering, soft k-means clustering, and derivations including the E-M algorithm and the variational view of the E-M algorithm.
"The Self-Organized Gene" , tutorial explaining clustering through competitive learning and self-organizing maps.
kernlab - R package for kernel based machine learning (includes spectral clustering implementation)
Tutorial - Tutorial with introduction of Clustering Algorithms (k-means, fuzzy-c-means, hierarchical, mixture of gaussians) + some interactive demos (java applets)
Data Mining Software - Data mining software frequently utilizes clustering techniques.
Java Competitve Learning Application A suite of Unsupervised Neural Networks for clustering. Written in Java. Complete with all source code.