Билет 50 – Кластерный анализ

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

Большинство исследователей склоняются к тому, что впервые термин «кластерный анализ» был предложен математиком Р.Трионом. Впоследствии возник ряд терминов, которые в настоящее время принято считать синонимами термина «кластерный анализ»: автоматическая классификация; ботриология.

Кластерный анализ — это многомерная статистическая процедура, выполняющая сбор данных, содержащих информацию о выборке объектов, и затем упорядочивающая объекты в сравнительно однородные группы (кластеры)(Q-кластеризация, или Q-техника, собственно кластерный анализ). Кластер — группа элементов, характеризуемых общим свойством, главная цель кластерного анализа — нахождение групп схожих объектов в выборке. Спектр применений кластерного анализа очень широк: его используют в археологии, медицине, психологии, химии, биологии, государственном управлении, филологии, антропологии, маркетинге, социологии и других дисциплинах. Однако универсальность применения привела к появлению большого количества несовместимых терминов, методов и подходов, затрудняющих однозначное использование и непротиворечивую интерпретацию кластерного анализа. Орлов А. И. предлагает различать следующим образом:

В дискриминантном анализе классы предполагаются заданными — плотностями вероятностей или обучающими выборками. Задача состоит в том, чтобы вновь поступающий объект отнести в один из этих классов. У понятия «дискриминация» имеется много синонимов: диагностика, распознавание образов с учителем, автоматическая классификация с учителем, статистическая классификация и т. д. При кластеризации и группировке целью является выявление и выделение классов. Синонимы: построение классификации, распознавание образов без учителя, автоматическая классификация без учителя, таксономия и др. Задача кластер-анализа состоит в выяснении по эмпирическим данным, насколько элементы «группируются» или распадаются на изолированные «скопления», «кластеры» (от cluster (англ.) — гроздь, скопление). Иными словами, задача — выявление естественного разбиения на классы, свободного от субъективизма исследователя, а цель — выделение групп однородных объектов, сходных между собой, при резком отличии этих групп друг от друга.

Задачи и условия

Кластерный анализ выполняет следующие основные задачи:

· Разработка типологии или классификации.

· Исследование полезных концептуальных схем группирования объектов.

· Порождение гипотез на основе исследования данных.

· Проверка гипотез или исследования для определения, действительно ли типы (группы), выделенные тем или иным способом, присутствуют в имеющихся данных.

Независимо от предмета изучения применение кластерного анализа предполагает следующие этапы:

· Отбор выборки для кластеризации. Подразумевается, что имеет смысл кластеризовать только количественные данные.

· Определение множества переменных, по которым будут оцениваться объекты в выборке, то есть признакового пространства.

· Вычисление значений той или иной меры сходства (или различия) между объектами.

· Применение метода кластерного анализа для создания групп сходных объектов.

· Проверка достоверности результатов кластерного решения.

 

Кластерный анализ предъявляет следующие требования к данным

· показатели не должны коррелировать между собой;

· показатели не должны противоречить теории измерений;

· распределение показателей должно быть близко к нормальному;

· показатели должны отвечать требованию «устойчивости», под которой понимается отсутствие влияния на их значения случайных факторов;

· выборка должна быть однородна, не содержать «выбросов».

Можно встретить описание двух фундаментальных требований предъявляемых к данным — однородность и полнота.

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

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

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

· Матрица сходства между объектами. Учитывается степень сходства объекта с другими объектами выборки в метрическом пространстве. Сходство здесь дополняет расстояние (различие) между объектами до 1.

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

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

· Сжатие данных. Если исходная выборка избыточно большая, то можно сократить её, оставив по одному наиболее типичному представителю от каждого кластера.

· Обнаружение новизны. Выделяются нетипичные объекты, которые не удаётся присоединить ни к одному из кластеров.

·

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

Общепринятой классификации методов кластеризации не существует, но можно отметить солидную попытку В. С. Берикова и Г. С. Лбова. Если обобщить различные классификации методов кластеризации, то можно выделить ряд групп (некоторые методы можно отнести сразу к нескольким группам и потому предлагается рассматривать данную типизацию как некоторое приближение к реальной классификации методов кластеризации):

1. Вероятностный подход. Предполагается, что каждый рассматриваемый объект относится к одному из k классов. Некоторые авторы (например, А. И. Орлов) считают, что данная группа вовсе не относится к кластеризации и противопоставляют её под названием «дискриминация», то есть выбор отнесения объектов к одной из известных групп (обучающих выборок).

a. K-средних (K-means)

b. K-medians

c. EM-алгоритм

d. Алгоритмы семейства FOREL

e. Дискриминантный анализ

2. Подходы на основе систем искусственного интеллекта. Весьма условная группа, так как методов AI очень много и методически они весьма различны.

a. Метод нечеткой кластеризации C-средних (C-means)

b. Нейронная сеть Кохонена

c. Генетический алгоритм

3. Логический подход. Построение дендрограммы осуществляется с помощью дерева решений.

4. Теоретико-графовый подход.

a. Графовые алгоритмы кластеризации

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

a. Иерархическая дивизивная кластеризация или таксономия. Задачи кластеризации рассматриваются в количественной таксономии.

6. Другие методы. Не вошедшие в предыдущие группы.

a. Статистические алгоритмы кластеризации

b. Ансамбль кластеризаторов

c. Алгоритмы семейства KRAB

d. Алгоритм, основанный на методе просеивания

e. DBSCAN и др.

 

Применение

В биологии

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

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

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

 

В социологии

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

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

· Кластеризация результатов поиска — используется для «интеллектуальной» группировки результатов при поиске файлов, веб-сайтов, других объектов, предоставляя пользователю возможность быстрой навигации, выбора заведомо более релевантного подмножества и исключения заведомо менее релевантного — что может повысить юзабилити интерфейса по сравнению с выводом в виде простого сортированного по релевантности списка.

o Clusty — кластеризующая поисковая машина компании Vivísimo

o Nigma — российская поисковая система с автоматической кластеризацией результатов

o Quintura — визуальная кластеризация в виде облака ключевых слов

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

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