Классификация (стр. 3 )

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

dij > 0 (неотрицательность расстояния) dij = dji (симметрия) dij + djk > dik (неравенство треугольника) Если dij не равно 0, то i не равно j (различимость нетождественных объектов) Если dij = 0, то i = j (неразличимость тождественных объектов)

Меру близости (сходства) объектов удобно представить как обратную величину от расстояния между объектами. В многочисленных изданиях посвященных кластерному анализу описано более 50 различных способов вычисления расстояния между объектами. Кроме термина "расстояние" в литературе часто встречается и другой термин - "метрика", который подразумевает метод вычисления того или иного конкретного расстояния. Наиболее доступно для восприятия и понимания в случае количественных признаков является так называемое "евклидово расстояние" или "евклидова метрика"[9].  Формула для вычисления такого расстояния:

  (1.1)

  В данной формуле использованы следующие обозначения:

dij - расстояние между i-тым и j-тым объектами; xik - численное значение k-той переменной для i-того объекта; xjk - численное значение k-той переменной для j-того объекта; v - количество переменных, которыми описываются объекты.

Нередко вместо обычного евклидового расстояния используют его квадрат d2ij. Кроме того, в ряде случаев используется "взвешенное" евклидово расстояние, при вычислении которого для отдельных слагаемых используются весовые коэффициенты. Для иллюстрации понятия евклидовой метрики используем простой обучающий пример. Матрица данных, приведенная ниже в таблице, состоит из 5 наблюдений и двух переменных.

Матрица данных из пяти наблюдаемых проб и двух переменных представлена в таблице 1.1

  Таблица 1.1

№
1	5,000	1,000
2	6,000	1,000
3	6,000	2,000
4	7,000	4,000
5	8,000	5,000

Используя евклидову метрику, вычислим матрицу межобъектных расстояний, состоящую из величин dij - расстояние между i-тым и j-тым объектами. В нашем случае i и j - номер объекта, наблюдения. Поскольку объем выборки равен 5, то соответственно i и j могут принимать значения от 1 до 5. Очевидно также, что количество всех возможных попарных расстояний будет равно 5*5=25. Действительно, для первого объекта это будут следующие расстояния: 1-1; 1-2; 1-3; 1-4; 1-5. Для объекта 2 также будет 5 возможных расстояний: 2-1; 2-2; 2-3; 2-4; 2-5 и т. д. Однако число различных расстояний будет меньше 25, поскольку необходимо учесть свойство неразличимости тождественных объектов - dij = 0 при i = j. Это означает, что расстояние между объектом №1 и тем же самым объектом №1 будет равно нулю. Такие же нулевые расстояния будут и для всех остальных случаев i = j. Кроме того, из свойства симметрии следует, что dij = dji для любых i и j. Т. е. расстояние между объектами №1 и №2 равно расстоянию между объектами №2 и №1.

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

При р = 2  получаем обычное Евклидово расстояние. Так выражение для обобщенной метрики Минковского имеет вид:

  (1.2)

Выбор конкретного значения степенного показателя "р" производится самим исследователем.

Частным случаем расстояния Минковского является так называемое манхэттенское расстояние, или "расстояние городских кварталов" (city-block), соответствующее р=1:

  (1.3)

Таким образом, манхэттенское расстояние является суммой модулей разностей соответствующих признаков объектов. Устремив p к бесконечности, мы получаем метрику "доминирования", или Sup-метрику:

  (1.4)

которую можно представить также в виде dij = max| xik - xjk|.

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

  (1.5)

Здесь через Xi и Xj обозначены вектор-столбцы значений переменных для i-того и j-того объектов. Символ Т в выражении (Xi - Xj)Т обозначает так называемую операцию транспонирования вектора. Символом S обозначена общая внутригрупповая дисперсионно-ковариационная матрица. А символ -1 над S означает, что необходимо обратить матрицу S. В отличие от метрики Минковского и евклидовой метрики, расстояние Махаланобиса через матрицу дисперсий-ковариаций S связано с корреляциями переменных. Когда корреляции между переменными равны нулю, расстояние Махаланобиса эквивалентно квадрату евклидового расстояния.

В случае использования дихотомических (имеющих всего два значения) качественных признаков широко используется расстояние Хемминга

  (1.6)

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

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

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

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

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

Следующее свойство кластеров - его размеры. Основным показателем размера кластера является его "радиус". Это свойство наиболее полно отображает фактический размер кластера, если рассматриваемый кластер имеет круглую форму и является гиперсферой в многомерном пространстве. Однако если кластеры имеют удлиненные формы, то понятие радиуса или диаметра уже не отображает истинного размера кластера. [10]

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

  Рисунок 1.1

Видно, что минимальный размер имеет кластер 1, а кластеры 2 и 3 имеют примерно равные размеры. В то же время, можно говорить о том, что минимальная плотность, а стало быть, и максимальная дисперсия расстояния, характерна для кластера 3. Кроме того, кластер 1 отделяется достаточно большими участками пустого пространства как от кластера 2, так и от кластера 3. Тогда как кластеры 2 и 3 частично перекрываются друг с другом. Представляет интерес и тот факт, что кластер 1 имеет гораздо большее различие от 2-го и 3-го кластеров по оси 1, нежели по оси 2. Напротив, кластеры 2 и 3 примерно одинаково различаются между собой как по оси 1, так и по оси 2. Очевидно, что для такого визуального анализа необходимо иметь все наблюдения выборки проецировать на специальные оси, в которых проекции элементов кластеров будут видны как отдельные скопления.

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

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