2. Формализация задачи кластеризации

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

Состояние исследуемого объекта может быть описано с помощью вектора дескрипторов или многомерного набора зафиксированных на нем

признаков:

^{X x1 , x2 ,..., x p }.

Тогда X_i – результат измерения этих признаков на i-ом объекте. Часть признаков может носить количественный характер и принимать любые действительные значения. Другая часть носит качественный характер и позволяет упорядочивать объекты по степени проявления какого-либо качества (например, бинарный признак, отображающий присутствие или отсутствие данного свойства).

2-й кластер

_x3

X_i

X_j

(X , X )

Очевидно, что любое многомерное наблюдение может быть геометрически интерпретировано в виде точки в p-мерном пространстве (см. рис. 1). Естественно

предположить, что геометрическая близость

i j

двух или нескольких точек в этом

_x¹ 1-й кластер (класс, таксон)

Рис. 1. Геометрическая интерпретация кластеров

_x2

пространстве означает принадлежность этих точек к одному кластеру.

Чтобы решить задачу кластеризации алгоритмически, необходимо количественно

определить понятие сходства и разнородности объектов. Тогда объекты X_i и X_j будем относить к одному кластеру, когда расстояние между этими объектами будет достаточно малым, и к разным – если будет достаточно большим.

Таким образом, для определения «похожести» объектов необходимо ввести меру близости или расстояния между объектами.

Неотрицательная, вещественнозначная функция

функцией расстояния (метрикой), если:

( X _i , X _j )

называется

1. ( X _i , X _j ) 0 для всех X_i и X_j;

2. ( X _i , X _j ) 0 тогда и только тогда, когда X_i=X_j; 3. ( X _i , X _j ) ( X _j , X _i ) ;

4. выполняется неравенство треугольника

где X_i, X_j, X_k – любые 3 объекта.

(X _i , X _j ) (X _i , X _k ) (X _k , X _j ),

Существуют различные способы вычисления расстояний. Наиболее употребительна евклидова метрика, которая связана с интуитивным представлением о расстоянии.

_E ( X _i , X _j ) 

p

i



k 1

(x^k 

_xk ₎2 _.

j

k k

Хеммингово расстояние используется как мера различия объектов, задаваемых дихотомическими (бинарными) признаками. Данная мера равна числу несовпадений значений соответствующих признаков в рассматриваемых i-ом и j-ом объектах:

_X ( X_i , X _j ) 

p



k 1

x_i x _{j .}

i

Существуют и другие более абстрактные меры близости. Если исследуемые признаки смешанные (количественные и качественные), то необходима нормировка по всем значениям ^xk количественных признаков x^k:

которая приводит к общей евклидовой мере близости. При разработке

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