Кластерный анализ как метод многомерной классификации

В статистических исследованиях группировка первичных данных является основным приемом решения задачи классификации, а поэтому и основой всей дальнейшей работы с собранной информацией. Из множества признаков, описывающих объект, отбирается один, наиболее информативный с точки зрения исследователя, и производится группировка в соответствии со значениями данного признака. Рассмотрим следующую задачу. Пусть исследуется совокупность n объектов, каждый из которых характеризуется по k замеренным на нем признакам Х. Требуется разбить эту совокупность на однородные в некотором смысле группы (классы). При этом практически отсутствует априорная информация о характере распределения измерений Х внутри классов. Полученные в результате разбиения группы обычно называются кластерами, методы их нахождения – кластерным анализом.

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

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

Матрица Х не является единственным способом представления данных в задачах кластерного анализа. Иногда исходная информация задана в виде квадратной матрицы

R=(r_ij), i,j=1, 2,..., k, элемент r_ij , который определяет степень близости i-го объекта к j-му.

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

Обычное Евклидово расстояние где х_ie - величина е-ой компоненты у i-го (j-го) объекта (е=1,2,...,к, i,j=1,2,...,n)

Использование этого расстояния оправдано в следующих случаях:

а) наблюдения берутся из генеральной совокупности, имеющей многомерное нормальное распределение с ковариационной матрицей вида σ²Ек, т.е. компоненты Х взаимно независимы и имеют одну и ту же дисперсию, где Ек - единичная матрица;

б) компоненты вектора наблюдений Х однородны по физическому смыслу и одинаково важны для классификации;

в) признаковое пространство совпадает с геометрическим пространством.

“Взвешенное” Евклидово пространство применяется в тех случаях, когда каждой компоненте xl вектора наблюдений X удается приписать некоторый “вес” ωl, пропорционально степени важности признака в задаче классификации. Обычно принимают 0≤ωe≤1, где e=1,2,...k.

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

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

Пусть si- i-я группа (класс, кластер), состоящая из n_i объектов; - среднее арифметическое векторных наблюдений s_i группы, т.е. "центр тяжести" i-й группы; ρ(s_l,s_m) - расстояние между группами s_l и s_m. - расстояние, измеряемое по принципу “ближайшего соседа”

Наиболее употребительными расстояниями и мерами близости между классами объектов являются:

- расстояние, измеряемого по принципу “дальнего соседа”

- расстояние, измеряемое по “центрам тяжести” групп

- расстояние, измеряемое по принципу “средней связи”, определяется как среднее арифметическое всех попарных расстояний между представителями рассматриваемых групп

Академиком А.Н.Колмогоровым было предложено “обобщенное расстояние” между классами, которое включает в себя в качестве частных случаев все рассмотренные выше виды расстояний.

,где ; - расстояния между классами s_e, s_m и s_q;

- α, β, δ и γ - числовые коэффициенты, значения которых определяют специфику процедуры, ее алгоритм.