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

Кластеризация (англ. cluster analysis) — задача группировки множества объектов на подмножества (кластеры) таким образом, чтобы объекты из одного кластера были более похожи друг на друга, чем на объекты из других кластеров по какому-либо критерию.

Задача кластеризации относится к классу задач обучения без учителя.

Постановка задачи кластеризации

Пусть [math]X[/math] — множество объектов, [math]Y[/math] — множество идентификаторов (меток) кластеров. На множестве [math]X[/math] задана функция расстояния между объектами [math]\rho(x,x')[/math]. Дана конечная обучающая выборка объектов [math]X^m = \{ x_1, \dots, x_m \} \subset X[/math]. Необходимо разбить выборку на подмножества (кластеры), то есть каждому объекту [math]x_i \in X^m[/math] сопоставить метку [math]y_i \in Y[/math], таким образом чтобы объекты внутри каждого кластера были близки относительно метрики [math]\rho[/math], а объекты из разных кластеров значительно различались.

Определение:

Алгоритм кластеризации — это функция [math]a\colon X\to Y[/math], которая любому объекту [math]x\in X[/math] ставит в соответствие идентификатор кластера [math]y\in Y[/math].

Множество [math]Y[/math] в некоторых случаях известно заранее, однако чаще ставится задача определить оптимальное число кластеров, с точки зрения того или иного критерия качества кластеризации.

Кластеризация (обучение без учителя) отличается от классификации (обучения с учителем) тем, что метки объектов из обучающей выборки [math]y_i[/math] изначально не заданы, и даже может быть неизвестно само множество [math]Y[/math].

Решение задачи кластеризации объективно неоднозначно по ряду причин:

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

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

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

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

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

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

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

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

• Графовые алгоритмы кластеризации. Наиболее примитивный класс алгоритмов. В настоящее время практически не применяется на практике.
• Вероятностные алгоритмы кластеризации. Каждый объект из обучающей выборки относится к каждому из кластеров с определенной степенью вероятности.
  • Алгоритм [math]k-[/math]средних (англ. [math]k-[/math]means)
  • EM-алгоритм
• Иерархические алгоритмы кластеризации. Упорядочивание данных путем создания иерархии вложенных кластеров.

Иерархическая кластеризация

Пример

Дендрограммы кластеризации ирисов Фишера в зависимости от функции расстояния между кластерами
Расстояние минимума	Расстояние максимума	Расстояние среднего	Расстояние Уорда

Лучше всего с задачей справился алгоритм с использованием расстояния Уорда. Он точно выделил класс Iris setosa и заметно отделили вид Iris virginica от Iris versicolor.

Источники информации

• Википедия — Кластерный анализ
• Wikipedia — Cluster analysis
• MachineLearning — Кластеризация
• Википедия — Иерархическая кластеризация
• Scipy Documentation — Hierarchical clustering (scipy.cluster.hierarchy)
• К.В.Воронцов Лекции по алгоритмам кластеризации и многомерного шкалирования