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

Задача кластерного анализа заключается в том, чтобы на основании данных, содержащихся во множестве Х, разбить множество объектов G на m (m – целое) кластеров (подмножеств) Q₁, Q₂, …, Q_m, так, чтобы каждый объект G_j принадлежал одному и только одному подмножеству разбиения и чтобы объекты, принадлежащие одному и тому же кластеру, были сходными, в то время как объекты, принадлежащие разным кластерам были разнородными.

Замечание. Результаты классификации зависят от выбора масштаба и единиц изменения признаков. Чтобы исправить такое положение, прибегают к стандартной нормировке признаков:

где - математическое ожидание выборки по i-му признаку, - СКО, - текущее k-е значение в i-й выборке.

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

Решением задачи кластерного анализа являются разбиения, удовлетворяющие некоторому критерию оптимальности. Этот критерий может представлять собой некоторый функционал, выражающий уровни желательности различных разбиений и группировок, который называют целевой функцией. Например, в качестве целевой функции может быть взята внутригрупповая сумма квадратов отклонения:

где x_j - представляет собой измерения j-го объекта.

Для решения задачи кластерного анализа необходимо определить понятие сходства и разнородности.

Понятно то, что объекты i-ый и j-ый попадали бы в один кластер, когда расстояние (отдаленность) между точками Х_i и Х_j было бы достаточно маленьким и попадали бы в разные кластеры, когда это расстояние было бы достаточно большим. Таким образом, попадание в один или разные кластеры объектов определяется понятием расстояния между Х_i и Х_j из Ер, где Ер - р-мерное евклидово пространство. Неотрицательная функция d(Х_i , Х_j) называется функцией расстояния (метрикой), если:

а) d(Х_i , Х_j) ³ 0, для всех Х_i и Х_j из Ер

б) d(Х_i , Х_j) = 0, тогда и только тогда, когда Х_i = Х_j

в) d(Х_i , Х_j) = d(Х_j, Х_i)

г) d(Х_i , Х_j) £ d(Х_i, Х_k) + d(Х_k, Х_j), где Х_j, Х_i и Х_k - любые три вектора из Ер.

Значение d(Х_i , Х_j) для Х_i и Х_j называется расстоянием между Х_i и Х_j и эквивалентно расстоянию между G_i и G_j соответственно выбранным характеристикам (F1, F2, F3, ..., Fр).

Наиболее часто употребляются следующие функции расстояний:

1. Евклидово расстояние d₂(Х_i , Х_j) =

2. l₁ - норма d₁(Х_i , Х_j) =

3. Сюпремум-норма d_¥ (Х_i , Х_j) = sup

k = 1, 2, ..., р

4. l_p - норма d_р(Х_i , Х_j) =

Евклидова метрика является наиболее популярной. Метрика l₁ наиболее легкая для вычислений. Сюпремум-норма легко считается и включает в себя процедуру упорядочения, а l_p-норма охватывает функции расстояний 1, 2, 3,.

Пусть n измерений Х₁, Х₂,..., Х_n представлены в виде матрицы данных размером p ´ n:

Тогда расстояние между парами векторов d(Х_i, Х_j) могут быть представлены в виде симметричной матрицы расстояний:

Понятием, противоположным расстоянию, является понятие сходства между объектами G_i. и G_j. Неотрицательная вещественная функция S(Х_i , Х_j) = S_ij называется мерой сходства, если:

1) 0£ S(Х_i , Х_j)<1 для Х_i ¹ Х_j

2) S(Х_i , Х_j) = 1

3) S(Х_i, Х_j) = S(Х_j , Х_i)

Пары значений мер сходства можно объединить в матрицу сходства:

Величину S_ij называют коэффициентом сходства.