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

Материал из MachineLearning.

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

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

Содержание 1 Типология задач кластеризации 1.1 Типы входных данных 1.2 Цели кластеризации 1.3 Функции расстояния 1.4 Методы кластеризации 2 Формальная постановка задачи кластеризации 3 Ссылки 4 Литература 5 Cсылки

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

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

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

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

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

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

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

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

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

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

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

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

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

• Метрика Хэмминга
• Евклидова метрика
• Взвешенная евклидова метрика
• Метрика Минковского

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

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

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

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

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

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

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

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

Ссылки

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

Литература

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.

Cсылки

• 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 [1]
• 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 EM algorithm and the variational view of the EM 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