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

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

Задача кластеризации относится к статистической обработке, а также к широкому классу задач обучения без учителя.

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

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

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

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

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

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

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

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

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

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

• K-средних (
• Статистические алгоритмы кластеризации
• Алгоритм ФОРЕЛЬ
• Иерархическая кластеризация или таксономия
• Нейронная сеть Кохонена
• Ансамбль кластеризаторов

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

Пусть $X~$ — множество объектов, $Y~$ — множество номеров (имён, меток) кластеров. Задана функция расстояния между объектами $\rho(x,x')~$. Имеется конечная обучающая выборка объектов $X^m = \{ x_1, \dots, x_m \} \subset X$. Требуется разбить выборку на непересекающиеся подмножества, называемые кластерами, так, чтобы каждый кластер состоял из объектов, близких по метрике $\rho~$, а объекты разных кластеров существенно отличались. При этом каждому объекту $x_i\in X^m$ приписывается номер кластера $y_i~$.

Алгоритм кластеризации — это функция $a\colon X\to Y$, которая любому объекту $x\in X$ ставит в соответствие номер кластера $y\in Y$. Множество $Y~$ в некоторых случаях известно заранее, однако чаще ставится задача определить оптимальное число кластеров, с точки зрения того или иного критерия качества кластеризации.

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

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

• не существует однозначно наилучшего критерия качества кластеризации. Известен целый ряд эвристических критериев,

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

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

Применение

В биологии

В социологии

В информатике

• Группирование результатов поиска: Кластеризация используется для "интеллектуального" группирования результатов при поиске файлов, веб-сайтов, других объектов, предоставляя пользователю возможность быстрой навигации, выбора заведомо более релевантного подмножества и исключения заведомо менее релевантного — что может повысить юзабилити интерфейса по сравнению с выводом в виде простого сортированного по релевантности списка.
  • Clusty[1] - кластеризующая поисковая машина компании Vivísimo
  • поисковая система с автоматической кластеризацией результатов

• Сегментация изображений (image segmentation): Кластеризация может быть использована для разбиения цифрового изображения на отдельные области с целью обнаружения границ (edge detection) или распознавания объектов.

• Интеллектуальный анализ данных (data mining):Кластеризация в Data Mining приобретает ценность тогда, когда она выступает одним из этапов анализа данных, построения законченного аналитического решения. Аналитику часто легче выделить группы схожих объектов, изучить их особенности и построить для каждой группы отдельную модель, чем создавать одну общую модель для всех данных. Таким приемом постоянно пользуются в маркетинге, выделяя группы клиентов, покупателей, товаров и разрабатывая для каждой из них отдельную стратегию.

См. также

• Кластеризация документов
• Классификация документов
• Нейронные сети

Литература

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

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

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

• www.MachineLearning.ru — профессиональный вики-ресурс, посвященный машинному обучению и интеллектуальному анализу данных
• BaseGroup.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 [2]
• 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.
• An overview of non-parametric clustering and computer vision
• "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.
• Machine Learning Software - Also contains much clustering software.
• Fuzzy Clustering Algorithms and their Application to Medical Image Analysis PhD Thesis, 2001, by AI Shihab.
• Cluster Computing and MapReduce Lecture 4