7. Описание метода кластерного анализа

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

,

(1)

где - значение k-го анализируемого признака, характеризующего состояние n-го объекта.

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

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

,

(2)

где - расстояние между i-м и j-м объектами;

- значения р-ой переменной соответственно у i-го и j-го объектов;

Х_i, X_j - векторы значений переменных у i-го и j-го объектов.

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

,

(3)

где - значение j-го признака у i-го объекта;

- среднее арифметическое значение j-го признака;

- среднее квадратическое отклонение j-го признака:

.

(4)

Итеративные процедуры являются распространенными алгоритмами кластерного анализа по их реализации на электронно-вычислительных машинах. Одним из таких методов является, в частности, метод k-средних. Характерная особенность данного метода в том, что кластеры формируются исходя из задаваемых условий разбиения (параметров), которые в процессе работы алгоритма могут быть изменены пользователем для достижения желаемого качества разбиения.

Для использования метода k-средних заранее задается число кластеров k и требуется классифицировать n объектов Х₁, Х₂, …, Х_n. Согласно алгоритму k-средних первоначально k-первых объектов определяются как центры k кластеров, затем определяют расстояние от остальных n - k объектов до этих центров. Для этого используется одна из метрик, например, евклидово расстояние. Наблюдение относится к тому кластеру, расстояние до которого было минимальным. После чего для кластера, в котором увеличилось число наблюдений, рассчитывается новый центр тяжести (как среднее по каждому показателю) по всем включенным в кластер наблюдениям. Процедура продолжается до тех пор, пока вновь образованные центры тяжести кластеров не будут отличаться от предыдущих.

Смысл описываемого алгоритма заключается в последовательном уточнении эталонных точек (Е^()) с соответствующим пересчетом приписываемых им «весов» (^()), которые определяются:

,

(5)

где  = 0, 1, 2,… - номер итерации.

.

(6)

При этом нулевое приближение Е⁽⁰⁾ строится с помощью случайно выбранных первых k точек исследуемой совокупности, то есть:

(7)

Затем на первом этапе «извлекается» точка Х_k+1 и выясняется, к какому из эталонов она оказалась ближе всего. Именно этот, самый близкий к Х_k+1 эталон заменяется эталоном, определяемым как центр тяжести старого эталона и присоединенной к нему точки Х_k+1 (с увеличением соответствующего ему веса), а все другие эталоны остаются неизменными (с прежними весами) и т.д. Таким образом, пересчет эталонов и весов на -том шаге, то есть при извлечении очередной точки Х_k+1, происходит по следующему правилу:

, если ,

(8)

в противном случае:

,

(9)

где i = 1, 2,…, k.

При этом, если обнаруживается несколько (по i) одинаковых минимальных значений , то можно условиться относить точку Х_k+ к эталону с минимальным порядковым номером.

При достаточно большом числе итераций или при достаточно больших объемах классифицируемых совокупностей n и при весьма широких ограничениях на природу исследуемых наблюдений дальнейший пересчет эталонных точек практически не приводит к изменению, то есть имеет место сходимость Е_ к некоторому пределу .

Окончательное разбиение S исследуемой совокупности многомерных наблюдений на k классов производится в соответствии с правилом минимального дистанционного разбиения S(E) относительно центров тяжести (эталонов) E=E^(n-k), то есть:

.

(5.10)

Если оказывается, что , то точку Х относят к тому из классов и , который обладает меньшим порядковым номером.

После завершения процедур классификации необходимо оценить полученные результаты. Для этой цели используется некоторая мера качества классификации, которую обычно называют функционалом или критерием качества. Такими критериями качества выступают:

1) Сумма квадратов расстояний до центров классов. При использовании этого критерия стремятся получить такое разбиение совокупности объектов на k кластеров, при котором значение этого критерия было бы минимальным.

2) Сумма внутриклассовых расстояний между объектами. Наилучшим следует считать такое разбиение, при котором достигается минимальное значение этого критерия.

3) Сумма внутриклассовых дисперсий. Оптимальным следует считать такое разбиение, при котором достигается минимальное значение этого критерия.

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