2.4. Самообучение в интеллектуальных системах. Постановка задачи кластер-анализа. Критерии и метрики кластер-анализа.

Рассмотрим теперь задачи обучения без учителя (или задачи самообучения). Методы самообучения получили широкое распространение в интеллектуальных системах, в частности – в экспертных системах распознавания образов и классификации и т.д.

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

Кластер-анализ. Постановка задачи. Критерии качества и метрики кластер-анализа.

Пусть задано множество наблюдений , где .

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

найти такие .

Возможны различные виды критериев (функционалов) разбиения. Заметим, что эта задача тесно связана с определением некоторой метрики в пространстве признаков.

Рассмотрим наиболее широко используемые функционалы качества разбиения:

Коэффициент разбиения F, который определяется случайным образом:
, (1)

где - некоторая степень принадлежности i-го объекта j-му кластеру. Диапазон изменения , где n - число объектов, k- число кластеров.Ф
Индекс четкости: , (2)
где K – число классов (кластеров); F – коэффициент разбиения.
Энтропия разбиения:
, (3)
Нормализованная энтропия разбиения:
, (4)

где n – число точек.
Модифицированная энтропия:
, (5)
Второй функционал Рубенса:
(6)
Третий функционал Рубенса (второй индекс четкости):

(7)

Поскольку исходная информация задается в виде матрицы Х, то возникает проблема выбора метрики. Выбор метрики – наиболее важный фактор, влияющий на результаты кластер-анализа. В зависимости от типа признаков используются различные меры близости (метрики).

Пусть имеются образцы и в N-мерном пространстве признаков.

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

Таблица 1. Основные типы метрик.

№	Наименование метрики	Тип признаков	Формула для оценки меры близости (метрики)
1	Эвклидово расстояние	Количественные
2	Мера сходства Хэмминга	Номинальные (качественные)	, где- число совпадающих признаков у образцов и
3	Мера сходства Роджерса-Танимото	Номинальные шкалы	где- число совпадающих единичных признаков у образцов и ; , - общее число единичных признаков у образцов и соответственно
4	Манхэттенская метрика	Количественные
5	Расстояние Махалонобиса	Количественные	W – ковариационная матрица выборки
6	Расстояние Журавлева	Смешанные	, где

Существует большое число алгоритмов кластеризации, которые используют различные метрики и критерии разбиения. При этом число классов (кластеров) либо задается априори, либо определяется в процессе работы самого алгоритма.

Одним из первых алгоритмов кластеризации был Дисперсионный алгоритм самопроизвольного разбиения Ю.П.Зайченко (см. журнал "Автоматика" №5, 1966)