1.2. Задача кластерного анализа

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

Решением задачи кластерного анализа является разбиение, удовлетворяющее некоторому критерию оптимальности. Этот критерий может представлять собой некоторый функционал, - выражающий уровни желательности различных разбиений и группировок. Этот функционал часто называют целевой функцией. Например, в качестве целевой функции может быть взята внутригрупповая сумма квадратов отклонений (см. параграф 1.5). В качестве примера рассмотрим объектов, обладающих одной характеристикой (т. е. результаты измерения пусть представляют собой множество Х={3, 4, 7, 4, 3, 3, 4, 4}. Сумма квадратов отклонений вычисляется по формуле

где представляет собой измерение объекта. Для нашего примера, содержащего 8 объектов, получим:

Если множество X разбить на три группы: , то все внутригрупповые суммы квадратов отклонений будут равны нулю:

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

Очевидно, для того чтобы «решить» задачу кластерного анализа, необходимо количественно определить понятия сходства и разнородности. Что означает «два объекта различны»? Задача была бы решена, если бы объекты попадали в один и тот же кластер всякий раз, когда расстояние (отдаленность) между соответствующими точками и было бы «достаточно малым», и, наоборот, попадали в разные кластеры, если бы расстояние между точками было бы, «достаточно большим». Таким образом, для нашей цели следует рассмотреть понятие расстояния между точками из с абстрактных позиций.