---
title: "Искусственный интеллект (кластеризация)"
description: "Кластерный анализ (англ. cluster analysis) — многомерная статистическая процедура, выполняющая сбор ..."
author: "video_vitalion_kz"
published: "2013-04-12T19:54:52+00:00"
modified: "2013-04-12T20:52:36+00:00"
locale: "ru"
canonical_url: "https://yvision.kz/post/iskusstvennyy-intellekt-klasterizaciya-347225"
markdown_url: "https://yvision.kz/post/iskusstvennyy-intellekt-klasterizaciya-347225/markdown"
site_name: "Yvision.kz"
---

# Искусственный интеллект (кластеризация)

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

**Кластерный анализ** ([англ.](http://ru.wikipedia.org/wiki/%D0%90%D0%BD%D0%B3%D0%BB%D0%B8%D0%B9%D1%81%D0%BA%D0%B8%D0%B9_%D1%8F%D0%B7%D1%8B%D0%BA) *cluster analysis*) — многомерная статистическая процедура, выполняющая сбор данных, содержащих информацию о выборке объектов, и затем упорядочивающая объекты в сравнительно однородные группы[\[1\]](http://ru.wikipedia.org/wiki/%D0%9A%D0%BB%D0%B0%D1%81%D1%82%D0%B5%D1%80%D0%BD%D1%8B%D0%B9_%D0%B0%D0%BD%D0%B0%D0%BB%D0%B8%D0%B7#cite_note-1)[\[2\]](http://ru.wikipedia.org/wiki/%D0%9A%D0%BB%D0%B0%D1%81%D1%82%D0%B5%D1%80%D0%BD%D1%8B%D0%B9_%D0%B0%D0%BD%D0%B0%D0%BB%D0%B8%D0%B7#cite_note-2)[\[3\]](http://ru.wikipedia.org/wiki/%D0%9A%D0%BB%D0%B0%D1%81%D1%82%D0%B5%D1%80%D0%BD%D1%8B%D0%B9_%D0%B0%D0%BD%D0%B0%D0%BB%D0%B8%D0%B7#cite_note-3)[\[4\]](http://ru.wikipedia.org/wiki/%D0%9A%D0%BB%D0%B0%D1%81%D1%82%D0%B5%D1%80%D0%BD%D1%8B%D0%B9_%D0%B0%D0%BD%D0%B0%D0%BB%D0%B8%D0%B7#cite_note-4). Задача кластеризации относится к статистической обработке, а также к широкому классу задач [обучения без учителя](http://ru.wikipedia.org/wiki/%D0%9E%D0%B1%D1%83%D1%87%D0%B5%D0%BD%D0%B8%D0%B5_%D0%B1%D0%B5%D0%B7_%D1%83%D1%87%D0%B8%D1%82%D0%B5%D0%BB%D1%8F).

Большинство исследователей[*[источник?](http://ru.wikipedia.org/wiki/%D0%92%D0%B8%D0%BA%D0%B8%D0%BF%D0%B5%D0%B4%D0%B8%D1%8F:%D0%A1%D1%81%D1%8B%D0%BB%D0%BA%D0%B8_%D0%BD%D0%B0_%D0%B8%D1%81%D1%82%D0%BE%D1%87%D0%BD%D0%B8%D0%BA%D0%B8)*] склоняются к тому, что впервые термин «кластерный анализ» ([англ.](http://ru.wikipedia.org/wiki/%D0%90%D0%BD%D0%B3%D0%BB%D0%B8%D0%B9%D1%81%D0%BA%D0%B8%D0%B9_%D1%8F%D0%B7%D1%8B%D0%BA) *cluster* — гроздь, сгусток, пучок) был предложен математиком Р. Трионом[\[5\]](http://ru.wikipedia.org/wiki/%D0%9A%D0%BB%D0%B0%D1%81%D1%82%D0%B5%D1%80%D0%BD%D1%8B%D0%B9_%D0%B0%D0%BD%D0%B0%D0%BB%D0%B8%D0%B7#cite_note-5). Впоследствии возник ряд терминов, которые в настоящее время принято считать синонимами термина «кластерный анализ»: автоматическая классификация, ботриология.

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

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

- [Матрица расстояний](http://ru.wikipedia.org/wiki/%D0%9C%D0%B0%D1%82%D1%80%D0%B8%D1%86%D0%B0_%D1%80%D0%B0%D1%81%D1%81%D1%82%D0%BE%D1%8F%D0%BD%D0%B8%D0%B9) между объектами. Каждый объект описывается расстояниями до всех остальных объектов [метрического пространства](http://ru.wikipedia.org/wiki/%D0%9C%D0%B5%D1%82%D1%80%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%BE%D0%B5_%D0%BF%D1%80%D0%BE%D1%81%D1%82%D1%80%D0%B0%D0%BD%D1%81%D1%82%D0%B2%D0%BE).

- [Матрица сходства](http://ru.wikipedia.org/wiki/%D0%9C%D0%B0%D1%82%D1%80%D0%B8%D1%86%D0%B0_%D0%BC%D0%B5%D1%80_%D0%BA%D0%BE%D0%BD%D0%B2%D0%B5%D1%80%D0%B3%D0%B5%D0%BD%D1%86%D0%B8%D0%B8#.D0.9C.D0.B0.D1.82.D1.80.D0.B8.D1.86.D0.B0_.D0.BE.D1.82.D0.BD.D0.BE.D1.81.D0.B8.D1.82.D0.B5.D0.BB.D1.8C.D0.BD.D1.8B.D1.85_.D1.81.D0.B8.D0.BC.D0.BC.D0.B5.D1.82.D1.80.D0.B8.D1.87.D0.BD.D1.8B.D1.85_.D0.BC.D0.B5.D1.80_.D0.BA.D0.BE.D0.BD.D0.B2.D0.B5.D1.80.D0.B3.D0.B5.D0.BD.D1.86.D0.B8.D0.B8) между объектами[\[7\]](http://ru.wikipedia.org/wiki/%D0%9A%D0%BB%D0%B0%D1%81%D1%82%D0%B5%D1%80%D0%BD%D1%8B%D0%B9_%D0%B0%D0%BD%D0%B0%D0%BB%D0%B8%D0%B7#cite_note-7). Учитывается степень сходства объекта с другими объектами выборки в метрическом пространстве. Сходство здесь дополняет расстояние (различие) между объектами до 1.

В современной науке применяется несколько алгоритмов обработки входных данных. Анализ путём сравнения объектов, исходя из признаков, (наиболее распространённый в биологических науках) называется *Q*-типом анализа, а в случае сравнения признаков, на основе объектов — *R*-типом анализа. Существуют попытки использования гибридных типов анализа (например, *RQ*-анализ), но данная методология ещё должным образом не разработана.

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

Общепринятой классификации методов кластеризации не существует, но можно выделить ряд групп подходов (некоторые методы можно отнести сразу к нескольким группам и потому предлагается рассматривать данную типизацию как некоторое приближение к реальной классификации методов кластеризации)[\[8\]](http://ru.wikipedia.org/wiki/%D0%9A%D0%BB%D0%B0%D1%81%D1%82%D0%B5%D1%80%D0%BD%D1%8B%D0%B9_%D0%B0%D0%BD%D0%B0%D0%BB%D0%B8%D0%B7#cite_note-8):

- *Вероятностный подход*. Предполагается, что каждый рассматриваемый объект относится к одному из k классов. Некоторые авторы (например, А. И. Орлов) считают, что данная группа вовсе не относится к кластеризации и противопоставляют её под названием «дискриминация», то есть выбор отнесения объектов к одной из известных групп (обучающих выборок). [K-средних](http://ru.wikipedia.org/wiki/K-%D1%81%D1%80%D0%B5%D0%B4%D0%BD%D0%B8%D1%85) ([K-means](http://ru.wikipedia.org/wiki/K-means))

- [K-medians](http://ru.wikipedia.org/wiki/K-medians)

- [EM-алгоритм](http://ru.wikipedia.org/wiki/EM-%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC)

- [Алгоритмы семейства FOREL](http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%8B_%D1%81%D0%B5%D0%BC%D0%B5%D0%B9%D1%81%D1%82%D0%B2%D0%B0_FOREL)

- [Дискриминантный анализ](http://ru.wikipedia.org/wiki/%D0%94%D0%B8%D1%81%D0%BA%D1%80%D0%B8%D0%BC%D0%B8%D0%BD%D0%B0%D0%BD%D1%82%D0%BD%D1%8B%D0%B9_%D0%B0%D0%BD%D0%B0%D0%BB%D0%B8%D0%B7)

- Подходы на основе систем искусственного интеллекта: весьма условная группа, так как методов очень много и методически они весьма различны. [Метод нечеткой кластеризации C-средних](http://ru.wikipedia.org/wiki/%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%BD%D0%B5%D1%87%D0%B5%D1%82%D0%BA%D0%BE%D0%B9_%D0%BA%D0%BB%D0%B0%D1%81%D1%82%D0%B5%D1%80%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D0%B8_C-%D1%81%D1%80%D0%B5%D0%B4%D0%BD%D0%B8%D1%85) ([C-means](http://ru.wikipedia.org/w/index.php?title=C-means&action=edit&redlink=1))

- [Нейронная сеть Кохонена](http://ru.wikipedia.org/wiki/%D0%9D%D0%B5%D0%B9%D1%80%D0%BE%D0%BD%D0%BD%D0%B0%D1%8F_%D1%81%D0%B5%D1%82%D1%8C_%D0%9A%D0%BE%D1%85%D0%BE%D0%BD%D0%B5%D0%BD%D0%B0)

- [Генетический алгоритм](http://ru.wikipedia.org/wiki/%D0%93%D0%B5%D0%BD%D0%B5%D1%82%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B8%D0%B9_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC)

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

- Теоретико-графовый подход. [Графовые алгоритмы кластеризации](http://ru.wikipedia.org/wiki/%D0%93%D1%80%D0%B0%D1%84%D0%BE%D0%B2%D1%8B%D0%B5_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%8B_%D0%BA%D0%BB%D0%B0%D1%81%D1%82%D0%B5%D1%80%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D0%B8)

- Иерархический подход. Предполагается наличие вложенных групп (кластеров различного порядка). Алгоритмы в свою очередь подразделяются на агломеративные (объединительные) и дивизивные (разделяющие). По количеству признаков иногда выделяют монотетические и политетические методы классификации. Иерархическая дивизивная кластеризация или таксономия. Задачи кластеризации рассматриваются в [количественной таксономии](http://ru.wikipedia.org/wiki/%D0%9A%D0%BE%D0%BB%D0%B8%D1%87%D0%B5%D1%81%D1%82%D0%B2%D0%B5%D0%BD%D0%BD%D0%B0%D1%8F_%D1%82%D0%B0%D0%BA%D1%81%D0%BE%D0%BD%D0%BE%D0%BC%D0%B8%D1%8F).

- Другие методы. Не вошедшие в предыдущие группы. [Статистические алгоритмы кластеризации](http://ru.wikipedia.org/w/index.php?title=%D0%A1%D1%82%D0%B0%D1%82%D0%B8%D1%81%D1%82%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B8%D0%B5_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%8B_%D0%BA%D0%BB%D0%B0%D1%81%D1%82%D0%B5%D1%80%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D0%B8&action=edit&redlink=1)

- [Ансамбль кластеризаторов](http://ru.wikipedia.org/w/index.php?title=%D0%90%D0%BD%D1%81%D0%B0%D0%BC%D0%B1%D0%BB%D1%8C_%D0%BA%D0%BB%D0%B0%D1%81%D1%82%D0%B5%D1%80%D0%B8%D0%B7%D0%B0%D1%82%D0%BE%D1%80%D0%BE%D0%B2&action=edit&redlink=1)

- [Алгоритмы семейства KRAB](http://ru.wikipedia.org/w/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%8B_%D1%81%D0%B5%D0%BC%D0%B5%D0%B9%D1%81%D1%82%D0%B2%D0%B0_KRAB&action=edit&redlink=1)

- [Алгоритм, основанный на методе просеивания](http://ru.wikipedia.org/w/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC,_%D0%BE%D1%81%D0%BD%D0%BE%D0%B2%D0%B0%D0%BD%D0%BD%D1%8B%D0%B9_%D0%BD%D0%B0_%D0%BC%D0%B5%D1%82%D0%BE%D0%B4%D0%B5_%D0%BF%D1%80%D0%BE%D1%81%D0%B5%D0%B8%D0%B2%D0%B0%D0%BD%D0%B8%D1%8F&action=edit&redlink=1)

- [DBSCAN](http://ru.wikipedia.org/w/index.php?title=DBSCAN&action=edit&redlink=1) и др.

Подходы 4 и 5 иногда объединяют под названием структурного или геометрического подхода, обладающего большей формализованностью понятия близости[\[9\]](http://ru.wikipedia.org/wiki/%D0%9A%D0%BB%D0%B0%D1%81%D1%82%D0%B5%D1%80%D0%BD%D1%8B%D0%B9_%D0%B0%D0%BD%D0%B0%D0%BB%D0%B8%D0%B7#cite_note-9). Несмотря на значительные различия между перечисленными методами все они опираются на исходную «**гипотезу компактности**»: в пространстве объектов все близкие объекты должны относиться к одному кластеру, а все различные объекты соответственно должны находиться в различных кластерах.

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

Пусть

![X~](http://upload.wikimedia.org/math/2/3/e/23e777609a11eea73fe9bd8a3045320c.png)

— множество объектов,

![Y~](http://upload.wikimedia.org/math/3/e/b/3ebad05fb80ec019e31fc4c22ca77de8.png)

— множество номеров (имён, меток) кластеров. Задана функция расстояния между объектами

![\rho(x,x')~](http://upload.wikimedia.org/math/5/e/2/5e2dc6eab63ab162089b7c2456c20e71.png)

. Имеется конечная обучающая выборка объектов

![X^m = \{ x_1, \dots, x_m \} \subset X](http://upload.wikimedia.org/math/8/0/8/80896076e43945a2ffe3df377407dfc4.png)

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

![\rho~](http://upload.wikimedia.org/math/8/9/f/89f1c26c8d1db74eff4cce179a6fc65d.png)

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

![x_i\in X^m](http://upload.wikimedia.org/math/3/1/8/31825d4addfa0b409c1dbd89f436ffb3.png)

приписывается номер кластера

![y_i~](http://upload.wikimedia.org/math/9/d/5/9d5e3f08fc8e952cfbfeadecb109effb.png)

.

*Алгоритм кластеризации* — это функция

![a\colon X\to Y](http://upload.wikimedia.org/math/2/3/2/2320e91c9ffee3fb0d27c33843eaa25e.png)

, которая любому объекту

![x\in X](http://upload.wikimedia.org/math/7/3/5/735b05e6097f98da56f2ca14b8005d36.png)

ставит в соответствие номер кластера

![y\in Y](http://upload.wikimedia.org/math/4/3/7/437f7046cb463518a28b277a85b47a5c.png)

. Множество

![Y~](http://upload.wikimedia.org/math/3/e/b/3ebad05fb80ec019e31fc4c22ca77de8.png)

в некоторых случаях известно заранее, однако чаще ставится задача определить оптимальное число кластеров, с точки зрения того или иного *критерия качества* кластеризации.

Кластеризация ([обучение без учителя](http://ru.wikipedia.org/wiki/%D0%9E%D0%B1%D1%83%D1%87%D0%B5%D0%BD%D0%B8%D0%B5_%D0%B1%D0%B5%D0%B7_%D1%83%D1%87%D0%B8%D1%82%D0%B5%D0%BB%D1%8F)) отличается от классификации ([обучения с учителем](http://ru.wikipedia.org/wiki/%D0%9E%D0%B1%D1%83%D1%87%D0%B5%D0%BD%D0%B8%D0%B5_%D1%81_%D1%83%D1%87%D0%B8%D1%82%D0%B5%D0%BB%D0%B5%D0%BC)) тем, что метки исходных объектов

![y_i~](http://upload.wikimedia.org/math/9/d/5/9d5e3f08fc8e952cfbfeadecb109effb.png)

изначально не заданы, и даже может быть неизвестно само множество

![Y~](http://upload.wikimedia.org/math/3/e/b/3ebad05fb80ec019e31fc4c22ca77de8.png)

.

Решение задачи кластеризации принципиально неоднозначно, и тому есть несколько причин (как считает ряд авторов):
- не существует однозначно наилучшего критерия качества кластеризации. Известен целый ряд [эвристических](http://ru.wikipedia.org/wiki/%D0%AD%D0%B2%D1%80%D0%B8%D1%81%D1%82%D0%B8%D0%BA%D0%B0) критериев, а также ряд алгоритмов, не имеющих чётко выраженного критерия, но осуществляющих достаточно разумную кластеризацию «по построению». Все они могут давать разные результаты. Следовательно, для определения качества кластеризации требуется эксперт предметной области, который бы мог оценить осмысленность выделения кластеров.

- число кластеров, как правило, неизвестно заранее и устанавливается в соответствии с некоторым субъективным критерием. Это справедливо только для методов дискриминации, так как в методах кластеризации выделение кластеров идёт за счёт формализованного подхода на основе мер близости.

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

---

Source: [https://yvision.kz/post/iskusstvennyy-intellekt-klasterizaciya-347225](https://yvision.kz/post/iskusstvennyy-intellekt-klasterizaciya-347225)