Просмотр кода страницы Кластерный анализ

[[Файл:Cluster-2.svg|thumb|Результат кластерного анализа обозначен раскрашиванием точек в соответствии с принадлежностью к одному из трёх кластеров.]]
'''Кластерный анализ''' ({{lang-en|cluster analysis}}) — многомерная статистическая процедура, выполняющая сбор данных, содержащих информацию о выборке объектов, и затем упорядочивающая объекты в сравнительно однородные группы<ref>''Айвазян С. А., Бухштабер В. М., Енюков И. С., Мешалкин Л. Д.'' Прикладная статистика: Классификация и снижение размерности. — М.: Финансы и статистика, 1989. — 607 с.</ref><ref>''Мандель И. Д. '' Кластерный анализ. — М.: Финансы и статистика, 1988. — 176 с.</ref><ref>''Хайдуков Д. С. '' Применение кластерного анализа в государственном управлении// Философия математики: актуальные проблемы. — М.: МАКС Пресс, 2009. — 287 с.</ref><ref>''Классификация и кластер. Под ред. Дж. Вэн Райзина. М.: Мир, 1980. 390 с.</ref>. Задача кластеризации относится к статистической обработке, а также к широкому классу задач [[обучение без учителя|обучения без учителя]].

Большинство исследователей (см., напр.,<ref>''Мандель И. Д. '' Кластерный анализ. — М.: Финансы и статистика, 1988. — С. 10.</ref>) склоняются к тому, что впервые термин «кластерный анализ» ({{lang-en|cluster}} — гроздь, сгусток, пучок) был предложен психологом {{нп4|Трион, Роберт|Р. Трионом||Robert Tryon}}<ref>''Tryon R. C.'' Cluster analysis. — London: Ann Arbor Edwards Bros, 1939. — 139 p.</ref>. Впоследствии возник ряд терминов, которые в настоящее время принято считать синонимами термина «кластерный анализ»: автоматическая классификация, ботриология.

Спектр применений кластерного анализа очень широк: его используют в [[Археология|археологии]], [[Медицина|медицине]], [[Психология|психологии]], [[Химия|химии]], [[Биология|биологии]], [[Государственное управление|государственном управлении]], [[Филология|филологии]], [[Антропология|антропологии]], [[маркетинг]]е, [[Социология|социологии]], [[Геология|геологии]] и других дисциплинах. Однако универсальность применения привела к появлению большого количества несовместимых терминов, методов и подходов, затрудняющих однозначное использование и непротиворечивую интерпретацию кластерного анализа.

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

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

Можно встретить описание двух фундаментальных требований, предъявляемых к данным — однородность и полнота. Однородность требует, чтобы все кластеризуемые сущности были одной природы, описывались сходным набором характеристик<ref>''Жамбю М.'' Иерархический кластер-анализ и соответствия. — М.: Финансы и статистика, 1988. — 345 с.</ref>. Если кластерному анализу предшествует [[факторный анализ]], то [[выборка]] не нуждается в «ремонте» — изложенные требования выполняются автоматически самой процедурой факторного моделирования (есть ещё одно достоинство — z-стандартизация без негативных последствий для выборки; если её проводить непосредственно для кластерного анализа, она может повлечь за собой уменьшение чёткости разделения групп). В противном случае выборку нужно корректировать.

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

=== Типы входных данных ===
* Признаковое описание объектов. Каждый объект описывается набором своих характеристик, называемых ''признаками''. Признаки могут быть числовыми или нечисловыми.
* [[Матрица расстояний]] между объектами. Каждый объект описывается расстояниями до всех остальных объектов [[Метрическое пространство|метрического пространства]].
* [[Матрица мер конвергенции#Матрица относительных симметричных мер конвергенции|Матрица сходства]] между объектами<ref>''Дюран Б., Оделл П.'' Кластерный анализ. — М.: Статистика, 1977. — 128 с.</ref>. Учитывается степень сходства объекта с другими объектами выборки в метрическом пространстве. Сходство здесь дополняет расстояние (различие) между объектами до 1.

В современной науке применяется несколько алгоритмов обработки входных данных. Анализ путём сравнения объектов, исходя из признаков, (наиболее распространённый в биологических науках) называется анализа ''Q''-режима ({{lang-en|Q-mode analysis}}), а в случае сравнения признаков, на основе объектов — анализа ''R''-режима. Существуют попытки использования гибридных режимов анализа (например, ''RQ''-режим), но данная методология ещё должным образом не разработана.{{Нет АИ|29|6|2023}}

=== Цели кластеризации ===
* [[Понимание данных]] путём выявления кластерной структуры. Разбиение выборки на группы схожих объектов позволяет упростить дальнейшую обработку данных и принятия решений, применяя к каждому кластеру свой метод анализа (стратегия «[[Разделяй и властвуй (программирование)|разделяй и властвуй]]»).
* [[Сжатие данных]]. Если исходная выборка избыточно большая, то можно сократить её, оставив по одному наиболее типичному представителю от каждого кластера.
* [[Обнаружение новизны]] ({{lang-en|novelty detection}}). Выделяются нетипичные объекты, которые не удаётся присоединить ни к одному из кластеров.

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

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

=== Методы кластеризации ===
Общепринятой классификации методов кластеризации не существует, но можно выделить ряд групп подходов (некоторые методы можно отнести сразу к нескольким группам и потому предлагается рассматривать данную типизацию как некоторое приближение к реальной классификации методов кластеризации)<ref>''Бериков В. С., Лбов Г. С.'' [http://www.ict.edu.ru/ft/005638/62315e1-st02.pdf Современные тенденции в кластерном анализе] {{Wayback|url=http://www.ict.edu.ru/ft/005638/62315e1-st02.pdf |date=20130810125026 }} // Всероссийский конкурсный отбор обзорно-аналитических статей по приоритетному направлению «Информационно-телекоммуникационные системы», 2008. — 26 с.</ref>:
# ''Вероятностный подход''. Предполагается, что каждый рассматриваемый объект относится к одному из k классов. Некоторые авторы (например, А. И. Орлов) считают, что данная группа вовсе не относится к кластеризации и противопоставляют её под названием «дискриминация», то есть выбор отнесения объектов к одной из известных групп (обучающих выборок).
#* [[K-средних]]
#* [[К-медиан]]
#* [[EM-алгоритм]]
#* [[Алгоритмы семейства FOREL]]
#* [[Дискриминантный анализ]]
# Подходы на основе систем искусственного интеллекта: весьма условная группа, так как методов очень много и методически они весьма различны.
#* [[Метод нечеткой кластеризации C-средних]] ([[C-means]])
#* [[Нейронная сеть Кохонена]]
#* [[Генетический алгоритм]]
# Логический подход. Построение дендрограммы осуществляется с помощью дерева решений.
# Теоретико-графовый подход.
#* [[Графовые алгоритмы кластеризации]]
# Иерархический подход. Предполагается наличие вложенных групп (кластеров различного порядка). Алгоритмы в свою очередь подразделяются на агломеративные (объединительные) и дивизивные (разделяющие). По количеству признаков иногда выделяют монотетические и политетические методы классификации.
#* Иерархическая дивизивная кластеризация или таксономия. Задачи кластеризации рассматриваются в [[количественная таксономия|количественной таксономии]].
# Другие методы. Не вошедшие в предыдущие группы.
#* [[Статистические алгоритмы кластеризации]]
#* [[Ансамбль кластеризаторов]]
#* [[Алгоритмы семейства KRAB]]
#* [[Алгоритм, основанный на методе просеивания]]
#* [[DBSCAN]] и др.

Подходы 4 и 5 иногда объединяют под названием структурного или геометрического подхода, обладающего большей формализованностью понятия близости<ref>''Вятченин Д. А.'' Нечёткие методы автоматической классификации. — Минск: Технопринт, 2004. — 219 с.</ref>. Несмотря на значительные различия между перечисленными методами все они опираются на исходную «'''гипотезу компактности'''»: в пространстве объектов все близкие объекты должны относиться к одному кластеру, а все различные объекты соответственно должны находиться в различных кластерах.

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

Решение задачи кластеризации принципиально неоднозначно, и тому есть несколько причин (как считает ряд авторов):
* не существует однозначно наилучшего критерия качества кластеризации. Известен целый ряд [[эвристика|эвристических]] критериев, а также ряд алгоритмов, не имеющих чётко выраженного критерия, но осуществляющих достаточно разумную кластеризацию «по построению». Все они могут давать разные результаты. Следовательно, для определения качества кластеризации требуется эксперт предметной области, который бы мог оценить осмысленность выделения кластеров.
* число кластеров, как правило, неизвестно заранее и устанавливается в соответствии с некоторым субъективным критерием. Это справедливо только для методов дискриминации, так как в методах кластеризации выделение кластеров идёт за счёт формализованного подхода на основе мер близости.
* результат кластеризации существенно зависит от метрики, выбор которой, как правило, также субъективен и определяется экспертом. Но есть ряд рекомендаций по выбору мер близости для различных задач.

== Применение ==

=== В биологии ===
В биологии кластеризация имеет множество приложений в самых разных областях. Например, в [[биоинформатика|биоинформатике]] с её помощью анализируются сложные сети взаимодействующих генов, состоящие порой из сотен или даже тысяч элементов. Кластерный анализ позволяет выделить подсети, узкие места, концентраторы и другие скрытые свойства изучаемой системы, что позволяет в конечном счете узнать вклад каждого гена в формирование изучаемого феномена.

В области экологии широко применяется для выделения пространственно однородных групп организмов, сообществ и т. п. Реже методы кластерного анализа применяются для исследования сообществ во времени. Гетерогенность структуры сообществ приводит к возникновению нетривиальных методов кластерного анализа (например, [[Графовые алгоритмы кластеризации|метод Чекановского]]).

Исторически сложилось так, что в качестве мер близости в биологии чаще используются [[Коэффициент сходства|меры сходства]], а не меры различия (расстояния).

=== В социологии ===
При анализе результатов социологических исследований рекомендуется осуществлять анализ методами иерархического агломеративного семейства, а именно методом Уорда, при котором внутри кластеров оптимизируется минимальная дисперсия, в итоге создаются кластеры приблизительно равных размеров. Метод Уорда наиболее удачен для анализа социологических данных. В качестве меры различия лучше квадратичное евклидово расстояние, которое способствует увеличению контрастности кластеров.
Главным итогом иерархического кластерного анализа является дендрограмма или «сосульчатая диаграмма». При её интерпретации исследователи сталкиваются с проблемой того же рода, что и толкование результатов факторного анализа — отсутствием однозначных критериев выделения кластеров. В качестве главных рекомендуется использовать два способа — визуальный анализ дендрограммы и сравнение результатов кластеризации, выполненной различными методами.

Визуальный анализ дендрограммы предполагает «обрезание» дерева на оптимальном уровне сходства элементов выборки. «Виноградную ветвь» (терминология Олдендерфера М. С. и Блэшфилда Р. К.<ref>''Олдендерфер М. С., Блэшфилд Р. К.'' Кластерный анализ / Факторный, дискриминантный и кластерный анализ: пер. с англ.; Под. ред. И. С. Енюкова. — М.: Финансы и статистика, 1989—215 с.</ref>) целесообразно «обрезать» на отметке 5 шкалы Rescaled Distance Cluster Combine, таким образом будет достигнут 80 % уровень сходства. Если выделение кластеров по этой метке затруднено (на ней происходит слияние нескольких мелких кластеров в один крупный), то можно выбрать другую метку. Такая методика предлагается Олдендерфером и Блэшфилдом.

Теперь возникает вопрос устойчивости принятого кластерного решения. По сути, проверка устойчивости кластеризации сводится к проверке её достоверности. Здесь существует эмпирическое правило — устойчивая типология сохраняется при изменении методов кластеризации. Результаты иерархического кластерного анализа можно проверять итеративным кластерным анализом по методу k-средних. Если сравниваемые классификации групп респондентов имеют долю совпадений более 70 % (более 2/3 совпадений), то кластерное решение принимается.

Проверить адекватность решения, не прибегая к помощи другого вида анализа, нельзя. По крайней мере, в теоретическом плане эта проблема не решена. В классической работе Олдендерфера и Блэшфилда «Кластерный анализ» подробно рассматриваются и в итоге отвергаются дополнительные пять методов проверки устойчивости:
# [[кофенетическая корреляция]] — не рекомендуется и ограничена в использовании;
# тесты значимости (дисперсионный анализ) — всегда дают значимый результат;
# методика повторных (случайных) выборок, что, тем не менее, не доказывает обоснованность решения;
# тесты значимости для внешних признаков пригодны только для повторных измерений;
# методы Монте-Карло очень сложны и доступны только опытным математикам{{Нет АИ|12|9|2012}}.

=== В информатике ===
* [[Кластеризация результатов поиска]] — используется для «интеллектуальной» группировки результатов при поиске [[файл]]ов, [[веб-сайт]]ов, других [[Объект (программирование)|объектов]], предоставляя [[Пользователь|пользователю]] возможность быстрой навигации, выбора заведомо более [[Релевантность|релевантного]] подмножества и исключения заведомо менее релевантного — что может повысить [[юзабилити]] [[Интерфейс пользователя|интерфейса]] по сравнению с выводом в виде простого сортированного по релевантности [[Список (информатика)|списка]].
** [[Clusty]] — кластеризующая поисковая машина компании [[Vivísimo]]
** [[Nigma]] — российская [[поисковая система]] с автоматической кластеризацией результатов
** [[Quintura]] — визуальная [[Кластеризация ключевых слов|кластеризация в виде]] [[облако ключевых слов|облака ключевых слов]]
* [[Сегментация (обработка изображений)|Сегментация изображений]] ({{lang-en|image segmentation}}) — кластеризация может быть использована для разбиения цифрового изображения на отдельные области с целью [[Выделение границ|обнаружения границ]] ({{lang-en|edge detection}}) или [[Распознавание образов|распознавания объектов]].
* [[Интеллектуальный анализ данных]] ({{lang-en|data mining)}} — кластеризация в Data Mining приобретает ценность тогда, когда она выступает одним из этапов анализа данных, построения законченного аналитического решения. Аналитику часто легче выделить группы схожих объектов, изучить их особенности и построить для каждой группы отдельную модель, чем создавать одну общую модель для всех данных. Таким приемом постоянно пользуются в маркетинге, выделяя группы клиентов, покупателей, товаров и разрабатывая для каждой из них отдельную стратегию.

== См. также ==
* [[Кластеризация документов]]
* [[Классификация документов]]
* [[Искусственная нейронная сеть|Нейронные сети]]
* [[Самоорганизующаяся карта Кохонена]]
* [https://in-trend.biz/instrumenty-analiza-finansovyh-rynkov/klasternyj-grafik-obemov-onlajn/ Кластерный анализ финансовых рынков] {{Wayback|url=https://in-trend.biz/instrumenty-analiza-finansovyh-rynkov/klasternyj-grafik-obemov-onlajn/ |date=20170221011908 }}

== Примечания ==
{{примечания}}

== Ссылки ==
'''На русском языке'''
* [http://www.machinelearning.ru www.MachineLearning.ru] — профессиональный вики-ресурс, посвященный машинному обучению и интеллектуальному анализу данных

'''На английском языке'''
* ''[http://adios.tau.ac.il/compact/ COMPACT — Comparative Package for Clustering Assessment] {{Wayback|url=http://adios.tau.ac.il/compact/ |date=20070226140826 }}''. A free Matlab package, 2006.
* P. Berkhin, ''[http://citeseer.ist.psu.edu/berkhin02survey.html Survey of Clustering Data Mining Techniques] {{Wayback|url=http://citeseer.ist.psu.edu/berkhin02survey.html |date=20070117165907 }}'', Accrue Software, 2002.
* Jain, Murty and Flynn: ''[http://citeseer.ist.psu.edu/jain99data.html Data Clustering: A Review] {{Wayback|url=http://citeseer.ist.psu.edu/jain99data.html |date=20070203074120 }}'', ACM Comp. Surv., 1999.
* for another presentation of hierarchical, k-means and fuzzy c-means see this [http://www.elet.polimi.it/upload/matteucc/Clustering/tutorial_html/index.html introduction to clustering] {{Wayback|url=http://www.elet.polimi.it/upload/matteucc/Clustering/tutorial_html/index.html |date=20070129114215 }}. Also has an explanation on mixture of [[normal distribution|Gaussians]].
* David Dowe, ''[http://www.csse.monash.edu.au/~dld/cluster.html Mixture Modelling page] {{Wayback|url=http://www.csse.monash.edu.au/~dld/cluster.html |date=20070405163728 }}'' — other clustering and mixture model links.
* a tutorial on clustering [https://web.archive.org/web/20070311001002/http://gauss.nmsu.edu/~lludeman/video/ch6pr.html] {{недоступная ссылка|число=13|месяц=05|год=2013|url=http://gauss.nmsu.edu/~lludeman/video/ch6pr.html}}
* [http://www.inference.phy.cam.ac.uk/mackay/itila/ The on-line textbook: Information Theory, Inference, and Learning Algorithms] {{Wayback|url=http://www.inference.phy.cam.ac.uk/mackay/itila/ |date=20150206001819 }}, by [[:en:David J. C. MacKay|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.
* [https://web.archive.org/web/20080113181815/http://www.nerd-cam.com/cluster-results/ An overview of non-parametric clustering and computer vision]
* [https://web.archive.org/web/20071224174301/http://blog.peltarion.com/2007/04/10/the-self-organized-gene-part-1/ «The Self-Organized Gene»], tutorial explaining clustering through competitive learning and self-organizing maps.
* [https://web.archive.org/web/20071226171509/http://cran.r-project.org/src/contrib/Descriptions/kernlab.html  kernlab] {{недоступная ссылка|число=13|месяц=05|год=2013|url=http://cran.r-project.org/src/contrib/Descriptions/kernlab.html}} — R package for kernel based machine learning (includes spectral clustering implementation)
* [http://home.dei.polimi.it/matteucc/Clustering/tutorial_html/ Tutorial] {{Wayback|url=http://home.dei.polimi.it/matteucc/Clustering/tutorial_html/ |date=20071229062606 }} — Tutorial with introduction of Clustering Algorithms (k-means, fuzzy-c-means, hierarchical, mixture of gaussians) + some interactive demos (java applets)
* [http://dmoztools.net/Computers/Software/Databases/Data_Mining/Public_Domain_Software/ Data Mining Software] {{Wayback|url=http://dmoztools.net/Computers/Software/Databases/Data_Mining/Public_Domain_Software/ |date=20170624122813 }} — Data mining software frequently utilizes clustering techniques.
* [https://web.archive.org/web/20071229100713/http://homepages.feis.herts.ac.uk/~nngroup/software.html  Java Competitve Learning Application] {{недоступная ссылка|число=13|месяц=05|год=2013|url=http://homepages.feis.herts.ac.uk/~nngroup/software.html}} A suite of Unsupervised Neural Networks for clustering. Written in Java. Complete with all source code.
* [http://dmoztools.net/Computers/Artificial_Intelligence/Machine_Learning/Software/ Machine Learning Software] {{Wayback|url=http://dmoztools.net/Computers/Artificial_Intelligence/Machine_Learning/Software/ |date=20180403184438 }} — Also contains much clustering software.
* [http://cism.kingston.ac.uk/people/shihab/dissertation.pdf ''Fuzzy Clustering Algorithms and their Application to Medical Image Analysis'' PhD Thesis, 2001, by AI Shihab.] {{Wayback|url=http://cism.kingston.ac.uk/people/shihab/dissertation.pdf |date=20070927153914 }}
* [https://www.youtube.com/watch?v=1ZDybXl212Q Cluster Computing and MapReduce Lecture 4] {{Wayback|url=https://www.youtube.com/watch?v=1ZDybXl212Q |date=20190114101845 }}
* [https://github.com/annoviko/pyclustering PyClustering Library] {{Wayback|url=https://github.com/annoviko/pyclustering |date=20180611025016 }} — Python library contains clustering algorithms (C++ source code can be also used — CCORE part of the library) and collection of neural and oscillatory networks with examples and demos.

{{вс}}
{{Искусственный интеллект}}
{{Машинное обучение}}
{{rq|topic=math|refless}}

[[Категория:Кластерный анализ]]
[[Категория:Применение искусственного интеллекта]]
[[Категория:Машинное обучение]]
[[Категория:Алгоритмы интернет-поиска]]
[[Категория:Математическая статистика]]