«Кластерный анализ — совокупность математических методов, предназначенных для формирования относительно «отдаленных» друг от друга групп «близких» между собой объектов по информации о расстояниях или связях (мерах близости) между ними. По смыслу аналогичен терминам: автоматическая классификация, таксономия, распознавание образов без учителя.» Такое определение кластерного анализа дано в последнем издании «Статистического словаря». Фактически «кластерный анализ» — это обобщенное название достаточно большого набора алгоритмов, используемых при создании классификации. В ряде изданий используются и такие синонимы кластерного анализа, как классификация и разбиение. Кластерный анализ широко используется в науке как средство типологического анализа. В любой научной деятельности классификация является одной из фундаментальных составляющих, без которой невозможны построение и проверка научных гипотез и теорий. Таким образом, в своей работе своей основной целью я считаю необходимым рассмотреть вопросы кластерного анализа (основы кластерного анализа), а так же рассмотреть его терминологию и привести некоторые примеры использования данного метода с обработкой данных.
1. ИСТОРИЯ «КЛАСТЕРНОГО АНАЛИЗА»
Анализ отечественных и зарубежных публикаций показывает, что кластерный анализ находит применение в самых разнообразных научных направлениях: химия, биология, медицина, археология, история, география, экономика, филология и т.д. В книге В.В.Налимова «Вероятностная модель языка» описано применение кластерного анализа при исследовании 70 аналитических проб. Большая часть литературы по кластерному анализу появилась в течение последних трех десятилетий, хотя первые работы, в которых упоминались кластерные методы, появились достаточно давно. Польский антрополог К.Чекановский выдвинул идею «структурной классификации», содержавшую основную идею кластерного анализа — выделение компактных групп объектов.
В 1925 г. советский гидробиолог П.В. Терентьев разработал так называемый «метод корреляционных плеяд», предназначенный для группировки коррелирующих признаков. Этот метод дал толчок развитию методов группировки с помощью графов. Термин «кластерный анализ» впервые был предложен Трионом. Слово «cluster» переводится с английского языка как «гроздь, кисть, пучок, группа». По этой причине первоначальное время этот вид анализа называли «гроздевым анализом». В начале 50-х годов появились публикации Р.Люиса, Е.Фикса и Дж. Ходжеса по иерархическим алгоритмам кластерного анализа. Заметный толчок развитие работ по кластерному анализу дали работы Р.Розенблатта по распознающему устройству (персептрону), положившие начало развитию теории «распознавания образов без учителя».
Исследования 2. Провести анализ программ для дошкольных образовательных
... работы, тесно связанные между собой и взаимообусловленные друг другом. Развитие элементарных математических представлений связано с математическим развитием детей. Рассмотрим различные подходы к данному понятию. По мнению А. А. Столяра: «Под математическим развитием дошкольников ...
Толчком к разработке методов кластеризации явилась книга «Принципы численной таксономии», опубликованная в 1963г. двумя биологами — Робертом Сокэлом и Питером Снитом. Авторы этой книги исходили из того, что для создания эффективных биологических классификаций процедура кластеризации должна обеспечивать использование всевозможных показателей характеризующих исследуемые организмы, производить оценку степени сходства между этими организмами и обеспечивать размещение схожих организмов в одну и ту же группу. При этом сформированные группы должны быть достаточно «локальны», т.е. сходство объектов (организмов) внутри групп должно превосходить сходство групп между собой. Последующий анализ выделенных группировок, по мнению авторов, может выяснить, отвечают ли эти группы разным биологическим видам. Так, Сокэл и Снит предполагали, что выявление структуры распределения объектов в группы, помогает установить процесс образования этих структур. А различие и сходство организмов разных кластеров (групп) могут служить базой для осмысления происходившего эволюционного процесса и выяснения его механизма.
В эти же годы было предложено множество алгоритмов таких авторов, как Дж. Мак-Кин, Г. Болл и Д. Холл по методам k-средних; Г. Ланса и У. Уильямса, Н. Джардайна и др. — по иерархическим методам. Заметный вклад в развитие методов кластерного анализа внесли и отечественные ученые — Э.М.Браверман, А.А.Дорофеюк, И.Б.Мучник, Л.А,Растригин, Ю.И.Журавлев, И.И.Елисеева и др. В частности, в 60-70 гг. большой популярностью пользовались многочисленные алгоритмы разработанные новосибирскими математиками Н.Г.Загоруйко, В.Н.Елкиной и Г.С.Лбовым. Это такие широко известные алгоритмы, как FOREL, BIGFOR, KRAB, NTTP, DRET, TRF и др. На основе этих пакетов был создан специализированный пакет программ ОТЭКС. Не менее интересные программные продукты ППСА и Класс-Мастер были созданы московскими математиками С.А.Айвазяном, И.С.Енюковым и Б.Г.Миркиным.
В том или ином объеме методы кластерного анализа имеются в большинстве наиболее известных отечественных и зарубежных статистических пакетах: SIGAMD, DataScope, STADIA, СОМИ, ПНП-БИМ, СОРРА-2, СИТО, SAS, SPSS, STATISTICA, BMDP, STATGRAPHICS, GENSTAT, S-PLUS и т.д. Конечно, спустя 10 лет после выхода этого обзора, изменилось достаточно много, появились новые версии многих статистических программ, появились и абсолютно новые программы, использующие как новые алгоритмы, так и сильно возросшие мощности вычислительной техники. Однако большинство статистических пакетов используют алгоритмы предложенные и разработанные в 60-70 гг.
По приблизительным оценкам специалистов число публикаций по кластерному анализу и его приложениям в различных областях знания удваивается каждые три года. Каковы же причины столь бурного интереса к этому виду анализа? Объективно существуют три основные причины этого явления. Это появление мощной вычислительной техники, без которой кластерный анализ реальных данных практически не реализуем. Вторая причина заключается в том, что современная наука все сильнее опирается в своих построениях на классификацию. Причем этот процесс все более углубляется, поскольку параллельно этому идет все большая специализация знания, которая невозможна без достаточно объективной классификации.
Психология малых групп
... малой группы. Ее признаки и границы. Существует бесчисленное количество определений малых групп. К наиболее ... группа»: иногда как группа, противостоящая группе членства, иногда как группа, возникающая внутри группы членства. 4.Проблема развития группы в социальной психологии В динамике малой группы ... процессов». Впервые малая группа стала объектом научного экспериментального исследования в ...
Третья причина — углубление специальных знаний неизбежно приводит к увеличению количества переменных, учитываемых при анализе тех или иных объектов и явлений. Вследствие этого субъективная классификация, которая ранее опиралась на достаточно малое количество учитываемых признаков, часто оказывается уже ненадежной. А объективная классификация, с все возрастающим набором характеристик объекта, требует использования сложных алгоритмов кластеризации, которые могут быть реализованы только на базе современных компьютеров. Именно эти причины и породили «кластерный бум». Однако, в среде медиков и биологов кластерный анализ еще не стал достаточно популярным и обыденным методом исследования.
2 ТЕРМИНОЛОГИЯ
2.1 ОБЪЕКТ И ПРИЗНАК
Введем первоначально такие понятия, как объект и признак. Объект — от латинского objectum — предмет. Применительно к химии и биологии под объектами мы будем подразумевать конкретные предметы исследования, которые изучаются с помощью физических, химических и иных методик. Такими объектами могут быть, например, пробы, растения, животные и т.д. Некоторую совокупность объектов, доступную исследователю для изучения,называют выборкой, или выборочной совокупностью. Количество объектов в такой совокупности принято называть объемом выборки. Обычно объем выборки обозначают латинской буквой «n» или «N» .
Признак (синонимы — свойство, переменная, характеристика; англ. — variable — переменная.) — представляет собой конкретное свойство объекта. Эти свойства могут выражаться как числовыми, так и не числовыми значениями. Например, артериальное давление (систолическое или диастолическое) измеряют в миллиметрах ртутного столба, вес — в килограммах, рост в сантиметрах и т.д. Такие признаки являются количественными. В отличие от этих непрерывных числовых характеристик (шкал), ряд признаков может иметь дискретные, прерывистые значения. В свою очередь такие дискретные признаки принято делить на две группы.
1) Первая группа — ранговые, или как их еще называют порядковые переменные (шкалы).
Таким признакам присуще свойство упорядоченности этих значений. К ним можно отнести стадии того или иного заболевания, возрастные группы, балльные оценки знаний учащихся, 12-балльную шкалу магнитуд землетрясений по Рихтеру и т.д.
2) Вторая же группа дискретных признаков не имеет такой упорядоченности и носит название номинальных (от слова «номинал» — образец ) или классификационных признаков. Примером таких признаков может быть состояние пациента — «здоров» или «болен», пол пациента, период наблюдения — «до лечения» и «после лечения» и т.д. В этих случаях принято говорить, что такие признаки относятся к шкале наименований.
Понятия объекта и признака, принято называть матрицей «Объект-свойство» или «Объект-признак». Матрицей будет прямоугольная таблица, состоящая из значений признаков описывающих свойства исследуемой выборки наблюдений. В данном контексте одно наблюдение будет записываться в виде отдельной строки состоящей из значений используемых признаков. Отдельный же признак в такой матрице данных будет представлен столбцом, состоящим из значений этого признака по всем объектам выборки.
2.2 РАССТОЯНИЕ МЕЖДУ ОБЪЕКТАМИ (МЕТРИКА)
Введём понятие «расстояние между объектами». Данное понятие является интегральной мерой сходства объектов между собой. Расстоянием между объектами в пространстве признаков называется такая величина d ij , которая удовлетворяет следующим аксиомам:
1. d ij > 0 (неотрицательность расстояния)
2. d ij = dji (симметрия)
3. d ij + djk > dik (неравенство треугольника)
4. Если d ij не равно 0, то i не равно j (различимость нетождественных объектов)
5. Если d ij = 0, то i = j (неразличимость тождественных объектов)
Меру близости (сходства) объектов удобно представить как обратную величину от расстояния между объектами. В многочисленных изданиях посвященных кластерному анализу описано более 50 различных способов вычисления расстояния между объектами. Кроме термина «расстояние» в литературе часто встречается и другой термин — «метрика», который подразумевает метод вычисления того или иного конкретного расстояния. Наиболее доступно для восприятия и понимания в случае количественных признаков является так называемое «евклидово расстояние» или «евклидова метрика». Формула для вычисления такого расстояния:
В данной формуле использованы следующие обозначения:
- d ij — расстояние между i-тым и j-тым объектами;
- x ik — численное значение k-той переменной для i-того объекта;
- x jk — численное значение k-той переменной для j-того объекта;
- v — количество переменных, которыми описываются объекты.
Таким образом, для случая v=2, когда мы имеем всего два количественных признака, расстояние d ij будет равно длине гипотенузы прямоугольного треугольника, которая соединяет собой две точки в прямоугольной системе координат. Эти две точки будут отвечать i-тому и j-тому наблюдениям выборки. Нередко вместо обычного евклидового расстояния используют его квадрат d2 ij . Кроме того, в ряде случаев используется «взвешенное» евклидово расстояние, при вычислении которого для отдельных слагаемых используются весовые коэффициенты. Для иллюстрации понятия евклидовой метрики используем простой обучающий пример. Матрица данных, приведенная ниже в таблице, состоит из 5 наблюдений и двух переменных.
Таблица 1, Матрица данных из пяти наблюдаемых проб и двух переменных.
|
№ |
X1 |
X2 |
|
|
1 |
5,000 |
11,000 |
|
|
2 |
6,000 |
11,000 |
|
|
3 |
6,000 |
12,000 |
|
|
4 |
7,000 |
14,000 |
|
|
5 |
8,000 |
15,000 |
|
Используя евклидову метрику, вычислим матрицу межобъектных расстояний, состоящую из величин d ij — расстояние между 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 мы получаем обычное Евклидово расстояния. Так выражение для обобщенной метрики Минковского имеет вид:
Выбор конкретного значения степенного показателя «р» производится самим исследователем.
Частным случаем расстояния Минковского является так называемое манхэттенское расстояние, или «расстояние городских кварталов» (city-block), соответствующее р=1:
Таким образом, манхэттенское расстояние является суммой модулей разностей соответствующих признаков объектов. Устремив p к бесконечности, мы получаем метрику «доминирования», или Sup-метрику:
которую можно представить также в виде d ij = max| xik — xjk |.
Метрика Минковского фактически представляет собой большое семейство метрик, включающее и наиболее популярные метрики. Однако существуют и методы вычисления расстояния между объектами, принципиально отличающиеся от метрик Минковского. Наиболее важное из них так называемое расстояние Махаланобиса, которое имеет достаточно специфические свойства. Выражение для данной метрики:
Здесь через X i и X j обозначены вектор-столбцы значений переменных для i-того и j-того объектов. Символ Т в выражении ( X i — X j ) Т обозначает так называемую операцию транспонирования вектора. Символом S обозначена общая внутригрупповая дисперсионно-ковариационная матрица. А символ -1 над S означает, что необходимо обратить матрицу S . В отличие от метрики Минковского и евклидовой метрики, расстояние Махаланобиса через матрицу дисперсий-ковариаций S связано с корреляциями переменных. Когда корреляции между переменными равны нулю, расстояние Махаланобиса эквивалентно квадрату евклидового расстояния.
В случае использования дихотомических (имеющих всего два значения) качественных признаков широко используется расстояние Хемминга
равное числу несовпадений значений соответствующих признаков для рассматриваемых i-того и j-того объектов.
2.3 ПЛОТНОСТЬ И ЛОКАЛЬНОСТЬ КЛАСТЕРОВ
Главной целью кластерного анализа является нахождение в выборке групп объектов схожих между собой. Предположим, что каким-то из возможных методов мы получили такие группы — кластеры. Следует отметить важные свойства кластеров. Одно из таких свойств — это плотность распределения точек, наблюдений внутри кластера. Это свойство дает нам возможность определить кластер в виде скопления точек в многомерном пространстве, относительно плотное по сравнению с иными областями этого пространства, которые либо вообще не содержат точек, либо содержат малое количество наблюдений. Иными словами, насколько данный кластер является компактным, или же наоборот — достаточно разреженным. Несмотря на достаточную очевидность этого свойства, однозначного способа вычисления такого показателя (плотности) не существует. Наиболее удачным показателем, характеризующим компактность, плотность «упаковки» многомерных наблюдений в данном кластере, является дисперсия расстояния от центра кластера до отдельных точек кластера. Чем меньше дисперсия этого расстояния, тем ближе к центру кластера находятся наблюдения, тем больше плотность кластера. И наоборот, чем больше дисперсия расстояния, тем более разрежен данный кластер, и, следовательно, есть точки находящиеся как вблизи центра кластера, так и достаточно удаленные от центра кластера.
Следующее свойство кластеров — его размеры. Основным показателем размера кластера является его «радиус». Это свойство наиболее полно отображает фактический размер кластера, если рассматриваемый кластер имеет круглую форму и является гиперсферой в многомерном пространстве. Однако если кластеры имеют удлиненные формы, то понятие радиуса или диаметра уже не отображает истинного размера кластера.
Другое важное свойство кластера — их локальность, отделимость. Оно характеризует степень перекрытия и взаимной удаленности кластеров друг от друга в многомерном пространстве. К примеру, рассмотрим распределение трех кластеров в пространстве новых, интегрированных признаков на приведенном ниже рисунке. Оси 1 и 2 были получены специальным методом из 12 признаков отражающих свойств разных форм эритроцитов, изучавшиеся с помощью электронной микроскопии.
Рисунок 1
Мы видим, что минимальный размер имеет кластер 1, а кластеры 2 и 3 имеют примерно равные размеры. В то же время, можно говорить о том, что минимальная плотность, а стало быть, и максимальная дисперсия расстояния, характерна для кластера 3. Кроме того, кластер 1 отделяется достаточно большими участками пустого пространства как от кластера 2, так и от кластера 3. Тогда как кластеры 2 и 3 частично перекрываются друг с другом. Представляет интерес и тот факт, что кластер 1 имеет гораздо большее различие от 2-го и 3-го кластеров по оси 1, нежели по оси 2. Напротив, кластеры 2 и 3 примерно одинаково различаются между собой как по оси 1, так и по оси 2. Очевидно, что для такого визуального анализа необходимо иметь все наблюдения выборки проецировать на специальные оси, в которых проекции элементов кластеров будут видны как отдельные скопления.
2.4 РАССТОЯНИЕ МЕЖДУ КЛАСТЕРАМИ
В более широком смысле под объектами можно понимать не только исходные предметы исследования, представленные в матрице «объект-свойство» в виде отдельной строки, или отдельными точками в многомерном признаковом пространстве, но и отдельные группы таких точек, объединенные тем или иным алгоритмом в кластер. В этом случае возникает вопрос о том, каким образом понимать расстояние между такими скоплениями точек (кластерами) и как его вычислять. В этом случае разнообразных возможностей еще больше, нежели в случае вычисления расстояния между двумя наблюдениями в многомерном пространстве. Эта процедура осложняется тем, что в отличие от точек кластеры занимают определенный объем многомерного пространства и состоят из многих точек. В кластерном анализе широко используются межкластерные расстояния, вычисляемые по принципу ближайшего соседа (nearest neighbour), центра тяжести, дальнего соседа (furthest neighbour), медиан. Наиболее широко используются четыре метода: одиночной связи, полной связи, средней связи и метод Варда. В методе одиночной связи объект будет присоединен к уже существующему кластеру, если хотя бы один из элементов кластера имеет тот же уровень сходства, что и присоединяемый объект. Для метода полных связей присоединение объекта к кластеру производится лишь в том случае, когда сходство между кандидатом на включение и любым из элементов кластера не меньше некоторого порога. Для метода средней связи имеется несколько модификаций, которые являются некоторым компромиссом между одиночной и полной связью. В них вычисляется среднее значение сходства кандидата на включение со всеми объектами существующего кластера. Присоединение производится в том случае, когда найденное среднее значение сходства достигает или превышает некоторый порог. Наиболее часто используют среднее арифметическое сходство между объектами кластера и кандидата на включение в кластер.
Многие из методов кластеризации отличаются между собой тем, что их алгоритмы на каждом шаге вычисляют разнообразные функционалы качества разбиения. Популярный метод Варда построен таким образом, чтобы оптимизировать минимальную дисперсию внутрикластерных расстояний. На первом шаге каждый кластер состоит из одного объекта, в силу чего внутрикластерная дисперсия расстояний равна 0. Объединяются по этому методу те объекты, которые дают минимальное приращение дисперсии, вследствие чего данный метод имеет тенденцию к порождению гиперсферических кластеров.
Многократные попытки классификации методов кластерного анализа приводят к десяткам, а то и сотням разнообразных классов. Такое многообразие порождается большим количеством возможных способов вычисления расстояния между отдельными наблюдениями, не меньшим количеством методов вычисления расстояния между отдельными кластерами в процессе кластеризации и многообразными оценками оптимальности конечной кластерной структуры.
Наибольшее распространение в популярных статистических пакетах получили два группы алгоритмов кластерного анализа: иерархические агломеративные методы и итеративные методы группировки.
3. МЕТОДЫ ГРУППИРОВКИ
3.1 ОСОБЕННОСТИ ИЕРАРХИЧЕСКИХ АГЛОМЕРАТИВНЫХ МЕТОДОВ
В агломеративно-иерархических методах (aglomerative hierarhical algorithms), которые, более часто используются в реальных биомедицинских исследованиях, первоначально все объекты (наблюдения) рассматриваются как отдельные, самостоятельные кластеры, состоящие всего лишь из одного элемента. Без использования мощной вычислительной техники реализация кластерного анализа данных весьма проблематична.
агломерации
- как вычислять координаты такого кластера из двух (а далее и более двух) объектов;
- как вычислять расстояние до таких «полиобъектных» кластеров от «монокластеров» и между «полиобъектными» кластерами.
Эти вопросы, в конечном счете, и определяют окончательную структуру итоговых кластеров (под структурой кластеров подразумевается состав отдельных кластеров и их взаимное расположение в многомерном пространстве).
Разнообразные комбинации метрик и методов вычисления координат и взаимных расстояний кластеров и порождают то многообразие методов кластерного анализа. На втором шаге в зависимости от выбранных методов вычисления координат кластера состоящего из нескольких объектов и способа вычисления межкластерных расстояний возможно либо повторное объединение двух отдельных наблюдений в новый кластер, либо присоединение одного нового наблюдения к кластеру, состоящему из двух объектов. Для удобства большинство программ агломеративно-иерархических методов по окончании работы могут предоставить для просмотра два основных графика. Первый график называется дендрограммой (от греческого dendron — дерево), отражающий процесс агломерации, слияния отдельных наблюдений в единый окончательный кластер. Приведём пример дендрограммы из 5 наблюдений по двум переменным.
График 1
Вертикальная ось такого графика представляет собой ось межкластерного расстояния, а по горизонтальной оси отмечены номера объектов — случаев (cases) использованных в анализе. Из этой дендрограммы видно, что вначале объединяются в один кластер объекты №1 и №2, поскольку расстояние между ними самое минимальное и равно 1. Это слияние отображается на графике горизонтальной линией соединяющей вертикальные отрезки выходящие из точек помеченных как С_1 и С_2. Обратим внимание на то, что сама горизонтальная линия проходит точно на уровне межкластерного расстояния равного 1. Далее на втором шаге к этому кластеру, включающему в себя уже два объекта, присоединяется объект №3, обозначенный как С_3. На следующем шаге происходит объединение объектов №4 и №5, расстояние между которыми равно 1,41. И на последнем шаге происходит объединение кластера из объектов 1, 2 и 3 с кластером из объектов 4 и 5. На графике видно, что расстояние между этими двумя предпоследними кластерами (последний кластер включает в себя все 5 объектов) больше 5, но меньше 6, поскольку верхняя горизонтальная линия соединяющая два предпоследних кластера проходит на уровне примерно равном 7, а уровень соединения объектов 4 и 5 равен 1,41.
Расположенная ниже дендрограмма получена при анализе реального массива данных состоящего из 70 обрабатываемых химических проб, каждый из которых характеризовался 12 признаками.
График 2
Из графика видно, что на последнем шаге, когда произошло слияние двух последних кластеров, расстояние между ними порядка 200 единиц. Видно, что первый кластер включает в себя гораздо меньше объектов, чем второй кластер.Ниже приведен увеличенный участок дендрограммы на котором достаточно отчетливо видны номера наблюдений, обозначаемые как С_65, С_58 и т.д. (слева направо): 65, 58, 59, 64, 63, 57, 60, 62, 56, 44, 94 и т.д.
График 3 Увеличенный участок приведённого выше графика №2
Видно, что объект 44 представляет собой монокластер объединяющийся на предпоследнем шаге с правым кластером и затем уже на последнем шаге все наблюдения объединяются в один кластер.
Другой график, который строится в таких процедурах — это график изменения межкластерных расстояний на каждом шаге объединения. Ниже приведен подобный график для приведенной выше дендрограммы.
График 4
В ряде программ имеется возможность вывести в табличном виде результаты объединения объектов на каждом шаге кластеризации. В большинстве таких таблиц во избежание путаницы используется различная терминология для обозначения исходных наблюдений — монокластеров, и собственно кластеров состоящих из двух и более наблюдений. В англоязычных статистических пакетах исходные наблюдения (строки матрицы данных) обозначаются как «случай» — case. Для того чтобы продемонстрировать зависимость кластерной структуры от выбора метрики и выбора алгоритма объединения кластеров, приведем ниже дендрограмму отвечающую алгоритму полной связи. И здесь мы видим, что объект №44 объединяется со всей остальной выборкой на самом последнем шаге.
График 5
А теперь сравним ее с другой диаграммой, полученной при использовании метода одиночной связи к тем же самым данным. В отличие от метода полной связи, видно, что этот метод порождает длинные цепочки последовательно присоединяемых друг к другу объектов. Однако во всех трех случаях можно говорить о том, что выделяется две основные группировки.
График 6
Обратим также внимание на то, что во всех трех случаях объект №44 присоединяется как монокластер, хотя и на разных шагах процесса кластеризации. Выделение таких монокластеров является неплохим средством обнаружения аномальных наблюдений, называемых выбросами. Удалим этот «подозрительный» объект №44 и вновь проведем кластеризацию. Получим следующую дендрограмму:
График 7
Видно, что «цепочечный» эффект сохранился, как сохранилось и разбиение на две локальные группы наблюдений.
3.2 ОСОБЕННОСТИ ИТЕРАЦИОННЫХ МЕТОДОВ КЛАСТЕРИЗАЦИИ
Среди итерационных методов наиболее популярным методом является метод k-средних Мак-Кина. В отличие от иерархических методов в большинстве реализаций этого метода сам пользователь должен задать искомое число конечных кластеров, которое обычно обозначается как «k». Как и в иерархических методах кластеризации, пользователь при этом может выбрать тот или иной тип метрики. Разные алгоритмы метода k-средних отличаются и способом выбора начальных центров задаваемых кластеров. В некоторых вариантах метода сам пользователь может (или должен) задать такие начальные точки, либо выбрав их из реальных наблюдений, либо задав координаты этих точек по каждой из переменных. В других реализациях этого метода выбор заданного числа k начальных точек производится случайным образом, причем эти начальные точки (зерна кластеров) могут в последующем уточняться в несколько этапов. Можно выделить 4 основных этапа таких методов:
- выбираются или назначаются k наблюдений, которые будут первичными центрами кластеров;
- при необходимости формируются промежуточные кластеры приписыванием каждого наблюдения к ближайшим заданным кластерным центрам;
- после назначения всех наблюдений отдельным кластерам производится замена первичных кластерных центров на кластерные средние;
- предыдущая итерация повторяется до тех пор, пока изменения координат кластерных центров не станут минимальными.
В некоторых вариантах этого метода пользователь может задать числовое значение критерия, трактуемого как минимальное расстояние для отбора новых центров кластеров. Наблюдение не будет рассматриваться как претендент на новый центр кластера, если его расстояние до заменяемого центра кластера превышает заданное число. Такой параметр в ряде программ называется «радиусом». Кроме этого параметра возможно задание и максимального числа итераций либо достижения определенного, обычно достаточно малого, числа, с которым сравнивается изменение расстояния для всех кластерных центров. Этот параметр обычно называется «конвергенцией», т.к. отражает сходимость итерационного процесса кластеризации. Ниже мы приведем часть результатов, которые получены при использовании метода k-средних Мак-Кина к предыдущим данным. Число искомых кластеров задавалось вначале равным 3, а затем — 2. Первая их часть содержит результаты однофакторного дисперсионного анализа, в котором в качестве группирующего фактора выступает номер кластера. В первом столбце — список 12 переменных, далее идут суммы квадратов (SS) и степени свободы (df), затем F-критерий Фишера и в последнем столбце — достигнутый уровень значимости «р».
Таблица 2 Данные полученные методом k-средних Мак-Кина, применимые к 70 исследуемым пробам.
|
Переменные |
SS |
df |
SS |
df |
F |
p |
|
|
Х1 |
1606,203 |
1 |
165,2964 |
68 |
660,7634 |
0,000000 |
|
|
Х2 |
621,964 |
1 |
916,1421 |
68 |
46,1648 |
0,000000 |
|
|
Х3 |
0,305 |
1 |
3,0978 |
68 |
6,6914 |
0,011832 |
|
|
Х4 |
0,146 |
1 |
3,2248 |
68 |
3,0697 |
0,084272 |
|
|
Х5 |
30,464 |
1 |
65,9877 |
68 |
31,3934 |
0,000000 |
|
|
Х6 |
6,936 |
1 |
17,2187 |
68 |
27,3910 |
0,000002 |
|
|
Х7 |
18,213 |
1 |
70,8901 |
68 |
17,4706 |
0,000085 |
|
|
Х8 |
0,160 |
1 |
12,6721 |
68 |
16,1832 |
0,000147 |
|
|
Х9 |
7,981 |
1 |
11,2471 |
68 |
48,2525 |
0,000000 |
|
|
Х10 |
6,943 |
1 |
8,6925 |
68 |
54,3172 |
0,000000 |
|
|
Х11 |
8,598 |
1 |
5,4052 |
68 |
108,1661 |
0,000000 |
|
|
Х12 |
7,673 |
1 |
3,6936 |
68 |
141,2533 |
0,000000 |
|
Как видно из этой таблицы, нулевая гипотеза о равенстве средних значений в трех группах отвергается. Ниже приведен график средних значений всех переменных по отдельным кластерам. Эти же кластерные средние переменных приведены далее в виде таблицы.
Таблица 3. Подробное рассмотрение данных на примере трёх кластеров.
|
Переменная |
Кластер №1 |
Кластер №2 |
Кластер №3 |
|
|
Х1 |
46,62000 |
33,78334 |
48,11867 |
|
|
Х2 |
51,00000 |
89,04000 |
80,62035 |
|
|
Х3 |
1,75000 |
0,37856 |
0,55613 |
|
|
Х4 |
1,25000 |
0,36733 |
0,49113 |
|
|
Х5 |
12,75000 |
3,25667 |
5,10217 |
|
|
Х6 |
5,00000 |
0,83222 |
1,71883 |
|
|
Х7 |
12,25000 |
3,68889 |
5,09550 |
|
|
Х8 |
0,80000 |
0,05556 |
0,18833 |
|
|
Х9 |
4,75000 |
0,82222 |
1,78233 |
|
|
Х10 |
4,50000 |
0,97778 |
1,87567 |
|
|
Х11 |
3,25000 |
0,35444 |
1,37067 |
|
|
Х12 |
2,75000 |
0,22222 |
1,18567 |
|
График 8
Анализ средних значений переменных для каждого кластера позволяет сделать вывод о том, что по признаку Х1 кластеры 1 и 3 имеют близкие значения, тогда как кластер 2 имеет среднее значение гораздо меньшее, чем в остальных двух кластерах. Напротив, по признаку Х2 первый кластер имеет самое минимальное значение, тогда как 2-й и 3-й кластеры имеют более высокие и близкие между собой средние значения. Для признаков Х3-Х12 средние значения в кластере 1 значительно выше, чем в кластерах 2 и 3. Следующая таблица дисперсионного анализа результатов кластеризации на два кластера также показывает необходимость отклонения нулевой гипотезы о равенстве групповых средних почти по всем 12 признакам, за исключением переменной Х4, для которой достигнутый уровень значимости оказался более 5%.
Таблица 4. Таблица дисперсионного анализа результатов кластеризации на два кластера.
|
Переменные |
SS |
Df |
SS |
df |
F |
p |
|
|
Х1 |
1606,203 |
1 |
165,2964 |
68 |
660,7634 |
0,000000 |
|
|
Х2 |
621,964 |
1 |
916,1421 |
68 |
46,1648 |
0,000000 |
|
|
Х3 |
0,305 |
1 |
3,0978 |
68 |
6,6914 |
0,011832 |
|
|
Х4 |
0,146 |
1 |
3,2248 |
68 |
3,0697 |
0,084272 |
|
|
Х5 |
30,464 |
1 |
65,9877 |
68 |
31,3934 |
0,000000 |
|
|
Х6 |
6,936 |
1 |
17,2187 |
68 |
27,3910 |
0,000002 |
|
|
Х7 |
18,213 |
1 |
70,8901 |
68 |
17,4706 |
0,000085 |
|
|
Х8 |
0,160 |
1 |
4,6721 |
68 |
16,1832 |
0,000147 |
|
|
Х9 |
7,981 |
1 |
11,2471 |
68 |
48,2525 |
0,000000 |
|
|
Х10 |
6,943 |
1 |
8,6925 |
68 |
54,3172 |
0,000000 |
|
|
Х11 |
8,598 |
1 |
5,4052 |
68 |
108,1661 |
0,000000 |
|
|
Х12 |
7,673 |
1 |
3,6936 |
68 |
141,2533 |
0,000000 |
|
Ниже приведены график и таблица групповых средних для случая кластеризации на два кластера.
Таблица 5. Таблица для случая кластеризации на два кластера.
|
Переменные |
Кластер №1 |
Кластер №2 |
|
|
Х1 |
33,78334 |
48,09410 |
|
|
Х2 |
89,04000 |
80,13477 |
|
|
Х3 |
0,37856 |
0,57570 |
|
|
Х4 |
0,36733 |
0,50357 |
|
|
Х5 |
3,25667 |
5,22754 |
|
|
Х6 |
0,83222 |
1,77262 |
|
|
Х7 |
3,68889 |
5,21279 |
|
|
Х8 |
0,05556 |
0,19836 |
|
|
Х9 |
0,82222 |
1,83098 |
|
|
Х10 |
0,97778 |
1,91869 |
|
|
Х11 |
0,35444 |
1,40148 |
|
|
Х12 |
0,22222 |
1,21131 |
|
График 9.
В том случае, когда исследователь не имеет возможности заранее определиться с наиболее вероятным числом кластеров, он вынужден повторить расчеты, задавая различное их число, подобно тому, как это было сделано выше. А затем, сравнивая полученные результаты между собой, остановиться на одном из наиболее приемлемых вариантов кластеризации.
4. КЛАСТЕРИЗАЦИЯ ПРИЗНАКОВ
Кроме кластеризации отдельных наблюдений существуют и алгоритмы кластеризации признаков. Одним из первых таких методов яяется метод корреляционных плеяд Терентьева П.В. Примитивные изображения подобных плеяд нередко можно встретить в биомедицинских публикациях в виде окружности испещренной стрелками, соединяющими признаки для которых авторы обнаружили корреляционную зависимость. В ряде программ для кластеризации объектов и признаков имеются отдельные процедуры. Например, в пакете SAS для кластеризации признаков используется процедура VARCLUS (от VARiable — переменная и CLUSter — кластер), тогда как кластерный анализ наблюдений выполняется иными процедурами — FASTCLUS и CLUSTER. Построение дендрограммы в том и другом случае производится с помощью процедуры TREE (дерево).
В других же статистических пакетах выбор элементов для кластеризации — объектов или признаков, производится в одном и том же модуле. В качестве метрики при кластеризации признаков часто используют выражения, включающие в себя значение тех или иных коэффициентов отражающих силу связи для пары признаков. В этом случае очень удобно для признаков имеющих силу связи равную единице (функциональная зависимость) принимать расстояние между признаками равным нулю. Действительно, при функциональной связи по значению одного признака можно точно вычислить значение другого признака. При уменьшении силы связи между признаками расстояние соответственно увеличивается. Ниже приведен график, показывающий дендрограмму объединения 12 признаков, которые были использованы выше при кластеризации 70 аналитических проб.
График 10. Дендрограмма кластеризации 12 признаков.
Как видно из этой дендрограммы, мы имеем дело с двумя локальными группировками признаков: Х1-Х10 и Х11-Х12.Для группы признаков Х1-Х10 характерна достаточно малая величина межкластерных расстояний, не превышающая примерно 100 единиц. Здесь же мы видим и некоторые внутренние парные подгруппы: Х1 и Х2, Х3 и Х4, Х6 и Х7. Очень близкое к нулю расстояние между признаками этих пар говорит об их сильной парной взаимосвязи. Тогда как для пары Х11 и Х12 величина межкластерного расстояния гораздо больше и составляет порядка 300 единиц. Наконец очень большое расстояние между левым (Х1-Х10) и правым (Х11-Х12) кластерами, равное примерно 1150 единицам, говорит о том, что взаимосвязь между этими двумя группировками признаков достаточна минимальна.
5. УСТОЙЧИВОСТЬ И КАЧЕСТВО КЛАСТЕРИЗАЦИИ
Очевидно, что было бы абсурдно ставить вопрос о том, насколько абсолютна та или иная классификация полученная с помощью методов кластерного анализа. При изменении метода кластеризации устойчивость проявляется в том, что на дендрограммах довольно отчетливо просматриваются два кластера.
В качестве одного из возможных способов проверки устойчивости результатов кластерного анализа может быть использован метод сравнения результатов полученных для различных алгоритмов кластеризации. Другие пути, это так называемый бутстреп-метод предложенный Б.Эфроном в 1977г., методы «складного ножа» и «скользящего контроля». Наиболее простое средство проверки устойчивости кластерного решения может заключаться в том, чтобы исходную выборку случайным образом разделить на две примерно равные части, провести кластеризацию обеих частей и затем сравнить полученные результаты. Более трудоемкий путь предполагает последовательное исключение вначале первого объекта и кластеризацию оставшихся (N — 1) объектов. Далее последовательно проводя эту процедуру с исключением второго, третьего и т.д. объектов анализируется структура всех N полученных кластеров. Другой алгоритм проверки устойчивости предполагает многократное размножение, дублирование исходной выборки из N объектов, затем объединение всех дублированных выборок в одну большую выборку (псевдогенеральную совокупность) и случайное извлечение из нее новой выборки из N объектов. После этого проводится кластеризация этой выборки, далее извлекается новая случайная выборка и вновь проводится кластеризация и т.д. Это также достаточно трудоемкий путь.
Не меньше проблем и при оценке качества кластеризации. Известно достаточно много алгоритмов оптимизации кластерных решений. Первые работы которые содержали формулировки критерия минимизации внутрикластерной дисперсии и алгоритм (типа k-средних) поиска оптимального решения появились в 50-х годах. В 1963г. в статье Дж. Уорда также излагался подобный оптимизационный иерархический алгоритм. Универсального критерия оптимизации кластерного решения не существует. Все это затрудняет выбор исследователем оптимального решения. В такой ситуации наилучшим способом утвердиться в том, что найденное кластерное решение является на данном этапе исследования оптимальным, является только согласованность этого решения с выводами, полученными с помощью других методов многомерной статистики.
В пользу вывода об оптимальности кластеризации служат также и положительные результаты проверки предсказывающих моментов полученного решения уже на других объектах исследования. При использовании иерархических методов кластерного анализа можно рекомендовать сравнение между собой нескольких графиков пошагового изменения межкластерного расстояния. При этом предпочтение следует отдать тому варианту, для которого наблюдается плоская линия такого приращения от первого шага до нескольких предпоследних шагов с резким вертикальным подъемом этого графика на последних 1-2 шагах кластеризации.
ВЫВОДЫ
В своей работе я постаралась показать, не только сложность данного вида анализа, но и оптимальные возможности обработки данных, ведь зачастую для точности результатов приходится использовать от десятков до сотен проб. Данный вид анализа помогает классифицировать и обработать результаты. Так же я считаю не маловажным, приемлемость в данном анализе компьютерных технологий, что позволяет сделать менее трудоёмким процесс обработки результатов и тем самым позволяет уделить большее внимание правильности отбора проб для анализа.
В использовании кластерного анализа имеются такие тонкости и детали, которые проявляются в отдельных конкретных случаях и видны не сразу. Например, роль масштаба признаков может быть минимальной, а может быть и доминирующей в ряде случаев. В таких случаях необходимо использовать преобразования переменных. Особенно результативно это при использовании методов, которые производят нелинейные преобразования признаков, повышающие в целом общий уровень корреляций между признаками.
Еще большая специфика в использовании кластерного анализа применительно к объектам, которые описываются только качественными признаками. В этом случае достаточно успешны методы предварительной оцифровки качественных признаков и проведение кластерного анализа с новыми признаками. В своей работе я показала, что кластерный анализ дает много новой и оригинальной информации как в случае его применения в достаточно изученных системах, так и при исследовании систем с неизвестной структурой.
Так же следует отметить, что кластерный анализ стал незаменим в эволюционных исследованиях, позволяя строить филогенетические деревья, показывающие эволюционные пути. Широко применяются эти методы и в программах научных исследований по физической и аналитической химии.
СПИСОК ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ
[Электронный ресурс]//URL: https://psychoexpert.ru/referat/klasternyiy-analiz-v-psihologii/
1) Айвазян С. А., Енюков И. С, Мешалкин Л. Д. О структуре и содержании пакета программ по прикладному статистическому анализу//Алгоритмическое и программное обеспечение прикладного статистического анализа.—М., 1980.
2) Айвазян С. А., Бежаева 3. И., Староверов О. В. Классификация многомерных наблюдений.—М.: Статистика, 1974.
3) Беккер В. А., Лукацкая М. Л. Об анализе структуры матрицы коэффициентов связи//Вопросы экономико-статистического моделирования и прогнозирования в промышленности.— Новосибирск, 1970.
4) Браверман Э. М., Мучник И. Б. Структурные методы обработки данных.—М.: Наука, 1983.
5) Воронин Ю. А. Теория классифицирования и ее приложения.—Новосибирск: Наука, 1987.
6) Гуд И. Дж. Ботриология ботриологии//Классификация и кластер.—М.: Мир,1980.
7) Дубровский С. А. Прикладной многомерный статистический анализ.—М.: Финансы и статистика, 1982.
8) Дюран Н., Оделл П. Кластерный анализ.—М.: Статистика, 1977.
9) Елисеева И. И., Рукавишников В. С. Группировка, корреляция, распознавание образов.—М.: Статистика, 1977.
10) Загоруйко Н. Г. Методы распознавания и их применение.—М.: Советское радио, 1972.
11) Заде Л. А. Размытые множества и их применение в распознавании образов и кластер-анализе//Классификация и кластер.—М.: Мир, 1980.
12) Кильдишев Г. С, Аболенцев Ю. И. Многомерные группировки.—М.: Статистика, 1978.
13) Райская И. И., Гостилин Н. И., Френкель А. А. Об одном способе проверки обоснованности разбиения в кластерном анализе.//Применение многомерного статистического анализа в экономике и оценке качества продукции.—Ч. П.Тарту, 1977.
14) Шурыгин А. М. Распределение межточечных расстояний и разностей// Программно-алгоритмическое обеспечение прикладного многомерного статистического анализа.—М., 1983.
15) Ээремаа Р. Общая теория конструирования кластер-систем и алгоритмы для нахождения их численных представлений: Труды ВЦ ТГУ.—Тарту, 1978.
16) Ястремский Б. С. Избранные труды.—М.: Статистика, 1964.
