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

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

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

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

Содержание

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

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

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

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

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

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

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

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

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

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

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

Пусть 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
    • поисковая система с автоматической кластеризацией результатов
  • Интеллектуальный анализ данных (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

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

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

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




Wikimedia Foundation. 2010.

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

  • кластеризация — — [Интент] Тематики автоматизированные системы EN clustering …   Справочник технического переводчика

  • кластеризация — кластериз ация, и …   Русский орфографический словарь

  • КЛАСТЕРИЗАЦИЯ — выделение различных групп объектов с общими признаками [63, c. 83] …   Современный образовательный процесс: основные понятия и термины

  • кластеризация записей — — [Л.Г.Суменко. Англо русский словарь по информационным технологиям. М.: ГП ЦНИИС, 2003.] Тематики информационные технологии в целом EN record clustering …   Справочник технического переводчика

  • Кластеризация рекламы — подача новостей или рекламной информации блоками, в которых объединяющую роль играет или общая тема, или общая фирма, рекламирующая свои товары …   Реклама и полиграфия

  • Кластеризация генов — * кластарызацыя генаў * gene clustering задача разбиения заданной выборки генов на подмножества, называемые кластерами (), так, чтобы каждый кластер состоял из схожих генов, а гены разных кластеров существенно отличались. Задача К. г. относится к …   Генетика. Энциклопедический словарь

  • Кластеризация результатов поиска — Кластеризация результатов поиска  группировка результатов поиска в поисковой системе по тому или иному признаку с целью сделать результат поиска более удобным. Например, в корпусной лингвистике при поиске по достаточно большому корпусу может …   Википедия

  • кластеризация диполя — dipolio klasterizacija statusas T sritis chemija apibrėžtis Dipolio susiskaidymas į kelis mažesnius dipolius. atitikmenys: angl. dipole clustering rus. кластеризация диполя …   Chemijos terminų aiškinamasis žodynas

  • Кластеризация документов — Для улучшения этой статьи желательно?: Дополнить статью (статья слишком короткая либо содержит лишь словарное определение). Найти и оформить в виде сносок ссылки на авторитетные источники, подтверждаю …   Википедия

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

Книги

Другие книги по запросу «Кластеризация» >>


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»