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

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

Требования к данным

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

• Однородность требует, чтобы все кластеризуемые сущности были одной природы, описывались сходным набором характеристик. Если кластерному анализу предшествует факторный анализ, то выборка не нуждается в «ремонте» — изложенные требования выполняются автоматически самой процедурой факторного моделирования (есть ещё одно достоинство — z-стандартизация без негативных последствий для выборки; если её проводить непосредственно для кластерного анализа, она может повлечь за собой уменьшение чёткости разделения групп). В противном случае выборку нужно корректировать.
• Полнота.

Цели

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

Задачи

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

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

Этапы

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

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

Методы

Общепринятой классификации методов кластеризации не существует, но можно выделить ряд групп подходов (некоторые методы можно отнести сразу к нескольким группам и потому предлагается рассматривать данную типизацию как некоторое приближение к реальной классификации методов кластеризации):

1. Вероятностный подход. Предполагается, что каждый рассматриваемый объект относится к одному из k классов. Некоторые авторы (например, А. И. Орлов) считают, что данная группа вовсе не относится к кластеризации и противопоставляют её под названием «дискриминация», то есть выбор отнесения объектов к одной из известных групп (обучающих выборок).
   • K-средних (K-means);
   • K-medians;
   • EM-алгоритм;
   • Алгоритмы семейства FOREL;
   • Дискриминантный анализ.
2. Подходы на основе систем искусственного интеллекта: методов очень много и методически они весьма различны.
   • Метод нечеткой кластеризации C-средних (C-means);
   • Нейронная сеть Кохонена;
   • Генетический алгоритм.
3. Логический подход. Построение дендрограммы осуществляется с помощью дерева решений.
4. Теоретико-графовый подход.
   • Графовые алгоритмы кластеризации.
5. Иерархический подход. Предполагается наличие вложенных групп (кластеров различного порядка). Алгоритмы в свою очередь подразделяются на агломеративные (объединительные) и дивизивные (разделяющие). По количеству признаков иногда выделяют монотетические и политетические методы классификации.
   • Иерархическая дивизивная кластеризация или таксономия. Задачи кластеризации рассматриваются в количественной таксономии.
6. Другие методы. Не вошедшие в предыдущие группы.
   • Статистические алгоритмы кластеризации;
   • Ансамбль кластеризаторов;
   • Алгоритмы семейства KRAB;
   • Алгоритм, основанный на методе просеивания;
   • DBSCAN и др.