Кластеризация методом k средних реферат

Обновлено: 04.07.2024

Кластеризация — это не метод, а задача, для решение которой придумано множество алгоритмов. Не существует “правильных”методов кластеризации, так как “clustering is in the eye of the beholder”[Estivill-Castro 2002]. Мы рассмотрим два семейства алгоритмов:

метод k-средних (k-means)
иерархическая кластеризация (hierarchical clustering)

17.1 Метод k-средних (k-means)

Алгоритм k-means был разработан в статье [Lloyd 1982]:

на вход алгоритму подаются данные и k — количество кластеров, на которые эти данные надо поделить;
произвольно выбираются k точек (центроидов) и рассчитываются ближайшие расстояния (евклидово) от данных точек до центроидов, точки которые ближе всего к некоторому центроиду образуют кластер;
на основе точек вошедших в кластер строится новый центроид, так чтобы расстояние от всех точек до нового центроида было минимально;
часть точек становится ближе к новому центроиду и входят в его кластер, а часть от центроида отдаляется и начинают входить в другой/другие кластер/кластеры;
… все это повторяется, пока на некоторой итерации не происходит изменение положения центроидов.

Давайте посмотрим визуализацию алгоритма k-средних, которую сделал Нафтали Харрис.

17.1.1 Пример

Давайте проанализируем данные из датасета iris :

Для того чтобы запустить метод k-средних в R нужно использовать функцию kmeans() , указав количество кластеров в centers :

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

Мы видим, что алгоритм все разбил на три кластера ( 1 , 2 , 3 ), 1 соответствует setosa , 2 соответствует versicolor , 3 соответсвтует virginica (я смотрю с какой группой ассоциировано наибольшое n ). Я использую функцию recode_factor() для того чтобы перекодировать переменную .cluster :

Цветом выделены несовпадения с исходными данными, как видно, таких случаев всего 5: два цветка virginica были отнесены к классу versicolor , три цветка virginica были отнесены к versicolor . Так что в целом, можно сказать, что алгоритм хорошо справился. Черным обозначены центроиды получившихся кластеров.

17.2 Иерархическая кластеризация

Иерархические кластеризации имеют два типа:

снизу вверх (agglomerative): каждое наблюдение в начальной позиции является кластером, дальше два ближних кластера соединяются в один, а дендограмма отображает порядки таких соединений.
сверху вниз (divisive): все наблюдения в начальной позиции являются кластером, который дальше делится на более мелкие, а дендограмма отображает порядки таких разъединений. Алгоритмы иерархической кластеризации требуют на вход матрицы расстояний. Алгоритмов кластерного анализа очень много, так что имеет смысл заглянуть в работу [Gordon 1987] и на страницу CRAN.

17.2.1 Матрица расстояний

Матрица расстояний — это матрица n × n, которая содержит значения меры расстояния/сходства между объектами в метрическом пространстве. Существует уйма мер расстояния/сходства, выбор из которых зависит от типа данных. К сожалению, не существует универсального алгоритма выбора метода, так что это остается на откуп исследователям. Кроме того, схожие методы, зародившиеся в биологии, называют string metric: они определяют расстояния между строками (расстояние Хэмминга, расстояние Левинштейна и т. п.)

17.2.1.1 Бинарные данные

Представим вот такие данные для нескольких языков:

Существует множество мер для анализа бинарных данных. Самый распространенный — коэффициент Жаккара. Для каждой пары идиомов строим вот такую таблицу:

идиом i
1	0
идиом j	1	a	b
0	c	d

А дальше мы считаем меру сходства:

В работе [Gower and Legendre 1986] есть и другие методы (14 шт.). Большинство из них есть в функции dist.binary() пакета ade4 .

Дальше можно использовать функцию dist() с аргументом binary . Я использую функцию tidy() из пакета broom , чтобы получить таблицу:

Можно визуализировать матрицу расстояния:

17.2.1.2 Числовые переменные

Расстояние здесь сложнее интерпретировать, потому что на графике представлено расстояние между 150 цветками.

17.2.2 Расстояние между словами

Мы уже обсуждали расстояние между словами, его тоже можно использовать для кластеризации:

17.2.3 Применение иерархической кластеризации

Объект иерархической кластеризации легко визуализировать:

Также можно выделить какое-то количество кластеров:

Функция cutree() возвращает вектор номеров кластеров в соответсвтии с данными, так что можно строить все предыдущие графики:

Мы видим, что алгоритм все разбил на три кластера ( 1 , 2 , 3 ), 1 соответствует setosa , 2 соответствует virginica и versicolor , 3 соответсвтует versicolor (я смотрю с какой группой ассоциировано наибольшое n ). Я использую функцию recode_factor() для того чтобы перекодировать переменную .cluster :

Мы видим, что ошибки в осовном сгруппированы на границе двух кластеров (видимо, точек меньше, чем 21 потому что они совпадают).

Метод k-средних – это метод кластерного анализа, цель которого является разделение m наблюдений (из пространства ) на k кластеров, при этом каждое наблюдение относится к тому кластеру, к центру (центроиду) которого оно ближе всего.

В качестве меры близости используется Евклидово расстояние:

, где

Итак, рассмотрим ряд наблюдений .

Метод k-средних разделяет m наблюдений на k групп (или кластеров) (k ≤ m) , чтобы минимизировать суммарное квадратичное отклонение точек кластеров от центроидов этих кластеров:

, где

- центроид для кластера .

Алгоритм

Итак, если мера близости до центроида определена, то разбиение объектов на кластеры сводится к определению центроидов этих кластеров. Число кластеров k задается исследователем заранее.

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

Относим наблюдения к тем кластерам, чье среднее (центроид) к ним ближе всего. Каждое наблюдение принадлежит только к одному кластеру, даже если его можно отнести к двум и более кластерам.

Затем центроид каждого i-го кластера перевычисляется по следующему правилу:

Таким образом, алгоритм k-средних заключается в перевычислении на каждом шаге центроида для каждого кластера, полученного на предыдущем шаге.

Алгоритм останавливается, когда значения не меняются:

Важно: Неправильный выбор первоначального числа кластеров k может привести к некорректным результатам. Именно поэтому при использовании метода k-средних важно сначала провести проверку подходящего числа кластеров для данного набора данных.

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

Рассмотрим задачу кластеризации данных. Имеется выборка и функция, отображающая расстояние между объектами Алгоритм кластеризации — это функция которая всем объектам проставляет метку кластера [1].

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

Рассмотрим один из самых популярных и широко используемых методов кластерного анализа — алгоритм k–means (k–средних). В данном методе построение оптимального разбиения объектов на кластеры, определено как требование минимизации среднеквадратического отклонения на точках каждого кластера:

(1)

объект кластеризации (точка);

— центр кластера (центроид),

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

(2)

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

числовое значение й переменной для объекта ;

число переменных, которыми описываются объекты (или количество данных характеристик) [3].

После того как все объекты распределены по кластерам, заново считаются центры масс кластеров по формуле:

(3)

количество набора кластеров в результате кластеризации;

количество начального набора кластеров;

коэффициент принадлежности.

Определения коэффициента принадлежности объекта к определенному кластеру, которая считается по формуле:

(4)

расстояние от объекта до центра кластера;

коэффициент неопределенности,

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

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

Недостатками алгоритма являются зависимость результата от инициализации центров кластеров и неопределенность выбора начального количества точек, играющих роль центров кластеров при первой итерации [2].

Далее вводится метрика, которая позволит оценить качество распределения элементов выборки по кластерам, полученное в результате работы алгоритма, относительно ожидаемого (иначе говоря, правильного) разбиения, задаваемого при проектировании набора данных.

Определим понятия точности и полноты полученного кластера относительно ожидаемого кластера :

;

число элементов в кластере

число общих элементов и

Введем для пары и меру как среднее гармоническое точности и полноты:

(5)

Далее определим меру относительно ожидаемого разбиения как максимальное значение мер относительно кластеров из разбиения :

(6)

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

(7)

где количество кластеров в разбиении ;

число элементов в кластере

общее число элементов в выборке.

Чем больше, тем ближе полученное разбиение к ожидаемому разбиению. В лучшем случае, когда каждому кластеру из отвечает ровно один из обращается в единицу [4].

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

(8)

Одним из подходов определения оптимального количества кластеров является анализ индексов Калинского-Харабаза (Caliński–Harabasz index). Для этого необходимо найти такое количество кластеров, которое максимизировало бы функцию, представленную в формуле:

(9)

количество кластеров;

матрица внутренней дисперсии;

матрица внешней дисперсии.

(10)

количество объектов в изучаемых данных.

Наиболее вероятным количеством кластеров является значение , на котором индекс достигает максимальное значение [4].

Алгоритм k-means является простым итеративным алгоритмом кластеризации, разделяющим множество данных на k кластеров. По своей сути, алгоритм работает с помощью перебора в два этапа: 1) кластеризация всех точек данных в зависимости от расстояния между точкой и ее ближайшим представителем кластера; 2) переоценка представителей кластера. Ограничения алгоритма k-means включает чувствительность k-means к инициализации и определению значения k.

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

1. Кутуков Д. С. Применение методов кластеризации для обработки новостного потока / Д. С. Кутуков // Технические науки: проблемы и перспективы: материалы междунар. науч. конф. (г. Санкт-Петербург, март 2011 г.). — СПб.: Реноме, 2011. — с. 77–83.

3. Баргесян А. А., Куприянов М. С., Степаненко В. В., Холод И. И. Методы и модели анализа данных: OLAP и Data Mining. — СПб.: БХВ-Петербург, 2004. — 336 с.

4. Сокэл Р. Р. Кластерный-анализ и классификация: предпосылки и основные направления. В кн: Классификация и кластер /Под ред. Дж.Вэн Райзина М: Мир, 1980, с.7–19.

Основные термины (генерируются автоматически): кластер, центр кластера, алгоритм, данные, кластеризация, коэффициент принадлежности, расстояние, числовое значение.

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

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

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

Прогресс в отрасли определяется развитием всех видов электрической связи, среди которых наиболее распространенной является телефонная связь.

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

Цель данной курсовой работы - статистическое изучение предоставления услуг связи населению в регионах России в 2008 году и влияние их на доход от услуг связи населению в расчете на одного жителя.

Глава 1. Теоретические аспекты кластерного анализа. Метод k-средних.

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

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

Наряду с иерархическими методами классификации, существует многочисленная группа так называемых итеративных методов кластерного анализа (метод k - средних.).

Сущность их заключается в том, что процесс классификации начинается с задания некоторых начальных условий (количество образуемых кластеров, порог завершения процесса классификации и т.д.). Название метода было предложено Дж. Мак-Куином в 1967 г. В отличие от иерархических процедур метод k - средних не требует вычисления и хранения матрицы расстояний или сходств между объектами. Алгоритм этого метода предполагает использование только исходных значений переменных. Для начала процедуры классификации должны быть заданы k выбранных объектов, которые будут служить эталонами, т.е. центрами кластеров. [1]

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

Математическое описание алгоритма метода k - средних.

Пусть имеется n наблюдений, каждое из которых характеризуется m признаками X1 , X2 , , Xn. Эти наблюдения необходимо разбить на k кластеров.

Для начала из n точек исследуемой совокупности отбираются случайным образом или задаются исследователем исходя из каких-либо априорных соображений k точек (объектов). Эти точки принимаются за эталоны.

Каждому эталону присваивается порядковый номер, который одновременно является и номером кластера.

На первом шаге из оставшихся (n -k) объектов извлекается точка Xi с координатами ( xi1 , xi2 , . , xim ) и проверяется, к какому из эталонов (центров) она находится ближе всего. Для этого используется одна из метрик, например, евклидово расстояние. Проверяемый объект присоединяется к тому центру (эталону), которому соответствует минимальное из расстояний. Эталон заменяется новым, пересчитанным с учетом присоединенной точки, и вес его (количество объектов, входящих в данный кластер) увеличивается на единицу. Если встречаются два или более минимальных расстояния, то i -ый объект присоединяют к центру с наименьшим порядковым номером.

На следующем шаге выбираем точку Xi+1 и для нее повторяются все процедуры. Таким образом, через (n-k) шагов все точки (объекты) совокупности окажутся отнесенными к одному из k кластеров, но на этом процесс разбиения не заканчивается. Для того чтобы добиться устойчивости разбиения по тому же правилу, все точки X1, X2,…, Xn опять подсоединяются к полученным кластером, при этом веса продолжают накапливаться. Новое разбиение сравнивается с предыдущим. Если они совпадают, то работа алгоритма завершается. В противном случае цикл повторяется.

Окончательное разбиение имеет центры тяжести, которые не совпадают с эталонами, их можно обозначить C1 ,C2 , ,Ck. При этом каждая точка Xi будет относиться к такому кластеру (классу) l , для которого расстояние минимально. Возможны две модификации метода k - средних. Первая предполагает пересчет центра тяжести кластера после каждого изменения его состава, а вторая – лишь после того, как будет завершен просмотр всех данных. В обоих случаях итеративный алгоритм этого метода минимизирует дисперсию внутри каждого кластера, хотя в явном виде такой критерий оптимизации не используется.

Достоинства алгоритма k-средних:

• понятность и прозрачность алгоритма.

Недостатки алгоритма k-средних:

• алгоритм слишком чувствителен к выбросам, которые могут искажать среднее. Возможным решением этой проблемы является использование модификации алгоритма - алгоритм k-медианы;

• алгоритм может медленно работать на больших базах данных. Возможным решением данной проблемы является использование выборки данных.

Глава 2. Кластерный анализ регионов России.

Нами исследуется совокупность 62 регионов, каждый из которых характеризуется по 5 замеренным на нем признакам Х. Четыре признака из них характеризуют степень оснащенности населения средствами связи и среднедушевой доход населения, а пятый – показатель дохода от услуг связи, предоставляемых населению. Данные по эти признакам приведены в Приложении 1. Вот эти признаки:

X1 – доходы от услуг связи населению в расчете на одного жителя (рублей);

Х2 – число квартирных телефонных аппаратов сети общего пользования на 1000 человек населения (на конец года; штук);

Х3 – средства связи (пользовательское оборудование) для оказания услуг передачи данных и телематических служб на 1000 человек (на конец года;штук);

Х4 – число абонентских терминалов сотовой связи на 1000 человек населения (на конец года; штук);

Х5 – среднедушевые доходы населения (рублей).

Перед началом работы и анализа данных необходимо выявить наличие выбросов, и если они могут повлиять на результаты анализа, удалить их из таблицы исходных данных. Графики исследования на выбросы по признакам X1 и X2, по признакам X1 и X3, и, наконец, по признакам X4 и X5 приведены на рисунках в Приложении 2. Проведя анализ по этим диаграммам можно сделать следующие выводы.

Камчатская область является выбросом по трем признакам: X1, X2, X5, следовательно, наличие данных по этому региону может повлиять на результаты дальнейшего анализа. Поэтому, Камчатская область будет удалена из массива исходных данных.

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

В результате для дальнейшей работы будут использованы данные, указанные в таблице Приложения 3. . Перед началом исследования и разбиения объектов на кластеры необходимо провести проверку данных на мультиколлинеарность. Парные коэффициенты корреляции приведены в Табл. 1.1.

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

Лучший способ прочувствовать, для чего нужна кластеризация k-средних, и понять, к чему я клоню в этой статье, — взглянуть на рис. 1. Демонстрационная программа начинает с создания фиктивного набора из 20 элементов данных. В терминологии кластеризации элементы данных иногда называют последовательностью из n-чисел (tuples). Здесь каждая такая последовательность представляет некое лицо (person) и имеет два числовых атрибута: рост в дюймах и вес в фунтах. Одно из ограничений алгоритма k-средних в том, что он применяется только в случаях, где последовательности данных полностью числовые.

Рис. 1. Кластеризация с применением k-средних

Фиктивные данные загружаются в память в виде массива. Затем количество кластеров задается равным трем. Хотя существуют более совершенные методы кластеризации, способные предложить оптимальное количество кластеров, в целом, кластеризация данных — процесс исследовательский, и подходящее число кластеров обычно подбирается методом проб и ошибок. Как вы вскоре увидите, кластеризация k-средних — это итеративный процесс. В демонстрационной программе есть переменная maxCount, которая ограничивает количество выполнений основного цикла кластеризации. Здесь это значение произвольно выбрано равным 30.

Далее демонстрационная программа отображает данные, сгруппированные по кластерам. Если вы изучите кластеризованные данные, то заметите, что кластер 0 можно было бы назвать кластером полных людей, кластер 1 — высоких людей, а кластер 2 — низкорослых людей. Анализируя последовательности, назначенные кластеру 0, демонстрационная программа определяет по некоему критерию, что последовательность 5 (67.0, 240.0) является наиболее аномальной.

Алгоритм k-средних

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

А теперь, какая из трех последовательностей ближе всего к (65.0, 130.0)? Есть несколько способов определить ближайшую последовательность. Самый распространенный способ, применяемый в демонстрационной программе, — использование евклидового расстояния, или метрики (Euclidean distance). Если на словах, то евклидово расстояние между двумя последовательностями является корнем квадратным суммы квадратов разностей между соответствующими компонентами каждой последовательности. И вновь это лучше пояснить на примере. Евклидово расстояние между последовательностью (61.0, 100.0) и средней последовательностью (65.0, 130.0) равно:

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

Освоив понятие центра масс кластера, вы довольно легко поймете алгоритм k-средних. В псевдокоде:

Поищите в Интернете — найдете несколько хороших онлайновых анимаций, демонстрирующих алгоритм k-средних в действии. Изображение на рис. 2 показывает, к какой кластеризации приводит демонстрационная программа. Элемент данных, обведенный в кружок в каждом кластере, является центром масс этого кластера.

Рис. 2. Кластерные данные и центры масс

Weight (pounds)	Вес (в фунтах)
Cluster 0	Кластер 0
Cluster 1	Кластер 1
Cluster 2	Кластер 2
Height (inches)	Рост (в дюймах)

Общая структура программы

Рис. 3. Общая структура программы

По крайней мере в принципе, алгоритм k-средних довольно прост. Но, как вы еще увидите, некоторые детали реализации весьма изощренные.

После подготовки исходных данных демонстрационная программа вызывает вспомогательную функцию ShowMatrix для отображения данных. Затем переменным numAttributes, numClusters и maxCount присваиваются значения 2 (height и weight), 3 и 30 соответственно. Вспомните, что maxCount ограничивает число итераций основного цикла обработки алгоритма. Алгоритм k-средних имеет тенденцию к быстрому схождению, но вам может понадобиться немного поэкспериментировать со значением maxCount.

Вся работа по кластеризации выполняется методом Cluster. Этот метод возвращает массив типа int, который определяет, как каждая последовательность назначается одному кластеру. По окончании демонстрационная программа сообщает о кластеризации и отображает исходные данные, сгруппированные по кластерам.

Демонстрационная программа заканчивает анализом кластеризованных данных на выпадающие, возможно, аномальные последовательности, используя метод Outliers. Этот метод принимает идентификатор кластера и возвращает значения из последовательности данных, которые находятся дальше всего (по евклидовой метрике) от центра масс кластера (наиболее репрезентативной последовательности). В данном случае для кластера 0 выпадающей последовательностью является (67.0, 240.0).

Вычисление центров масс кластеров

Вспомните, что центр масс (центроид) кластера — это последовательность, наиболее репрезентативная среди остальных последовательностей, назначенных кластеру, и один из способов определить центр масс кластера — вычисление средней последовательности с поиском последовательности, ближайшей к средней. Среднюю последовательность в каждом кластере вычисляет вспомогательный метод UpdateMeans (рис. 4).

Рис. 4. Метод UpdateMeans

Метод UpdateMeans предполагает, что массив массивов с именем means уже существует, а вовсе не создает его и не возвращает. Так как предполагается, что массив means имеется, вы, вероятно, предпочтете сделать его параметром, передаваемым по ссылке (ref parameter). Массив means создается вспомогательным методом Allocate:

Первый индекс массива means представляет идентификатор кластера, а второй — указывает атрибут. Например, если means[0][1] = 150.33, то среднее значение веса (1) в последовательности в кластере 0 составляет 150.33.

Метод UpdateMeans сначала обнуляет существующие значения в массиве means, затем перебирает каждую последовательность данных, увеличивая их счетчик в каждом кластере, подсчитывает суммы по каждому атрибуту, а затем делит каждую сумму на соответствующее количество последовательностей в кластере. Заметьте, что этот метод сгенерирует исключение, если счетчик какого-либо кластера окажется равным 0, поэтому здесь нужно добавить проверку на ошибку.

Метод ComputeCentroid (рис. 5) определяет значения центра масс, т. е. значения одной последовательности, ближайшей к последовательности с усредненными значениями для данного кластера.

Рис. 5. Метод ComputeCentroid

Метод ComputeCentroid перебирает каждую последовательность в наборе данных, пропуская последовательности, которые не находятся в указанном кластере. Для каждой последовательности в указанном кластере вычисляется евклидово расстояние между ней и средней в кластере, используя вспомогательный метод Distance. Значения последовательности, ближайшие к средним значениям (имеющие наименьшее расстояние), сохраняются и возвращаются.

Метод UpdateCentroids вызывает ComputeCentroid для каждого кластера, чтобы определить центры масс всех кластеров:

Метод UpdateCentroids предполагает, что массив массивов с именем centroids уже существует. Массив centroids очень похож на массив means: первый индекс представляет идентификатор кластера, а второй — указывает атрибут данных.

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

Функция Distance и нормализация данных

Метод ComputeCentroid вызывает метод Distance, чтобы определить, какая последовательность данных ближе всего к центру масс кластера. Как уже описывалось, самый распространенный способ измерить расстояния от последовательностей до средней — использовать евклидову метрику:

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

Другой важный фактор, связанный с выбором функции вычисления метрики в алгоритме кластеризации k-средних, — нормализация данных. Демонстрационная программа использует исходные, ненормализованные данные. Поскольку значения веса в последовательностях — это обычно величины вроде 160.0, а значения роста — на уровне 67.0, разница в значениях веса имеет гораздо большее влияние, чем разница в значениях роста. Во многих ситуациях, исходные данные полезно нормализовать перед кластеризацией. Сделать это можно разными методами. Распространенный способ — вычисление среднего (m) и стандартного отклонения (standard deviation, sd) для каждого атрибута, а затем вычисление для значения каждого атрибута (v) нормализованного значения nv = (v–m)/sd.

Назначение каждой последовательности кластеру

Располагая методом вычисления центроида каждого кластера, можно написать метод для назначения каждой последовательности кластеру. Метод Assign представлен на рис. 6.

Рис. 6. Метод Assign

Метод Assign принимает массив centroids и перебирает каждую последовательность данных. Для каждой из последовательностей вычисляется расстояние до каждого центроида кластера и сохраняется локальный массив с именем distances, индекс которого представляет идентификатор кластера. Затем вспомогательный метод MinIndex определяет индекс в массиве distances, где хранится наименьшее значение метрики, и это соответствует кластеру, центр масс которого находится ближе всего к данной последовательности.

Вот как выглядит вспомогательный метод MinIndex:

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

Эта реализация алгоритма k-средних предполагает, что каждому кластеру всегда назначена хотя бы одна последовательность данных. Как видно на рис. 6, метод Assign не предотвращает ситуации, где кластеру вообще не назначается ни одной последовательности. На практике это обычно не проблема. Предотвратить ошибочную ситуацию не так-то просто. Подход, который я обычно применяю, заключается в создании массива centroidIndexes, работающий в сочетании с массивом centroids. Вспомните, что массив centroids содержит значения центров масс, например (61.0, 120.0) — это центр масс для кластера 2 на рис. 2. Массив centroidIndexes хранит сопоставленный индекс последовательности, скажем [3]. Затем в методе Assign мы первым делом назначаем каждому кластеру последовательность данных, которая содержит значения центра масс, и только после этого метод перебирает остальные последовательности и назначает их кластерам. Такой подход гарантирует, что в каждом кластере будет минимум одна последовательность.

Метод Cluster

Метод Cluster (рис. 7) — высокоуровневая процедура, которая вызывает все вспомогательные методы, выполняющие реальную работу по кластеризации данных.

Рис. 7. Метод Cluster

Основной цикл while повторно назначает каждую последовательность данных кластеру, вычисляет новую последовательность усредненных значений для каждого кластера, а затем использует ее для вычисления новых значений центра масс для каждого кластера. Цикл прекращается, когда не происходит изменений в назначениях кластеров или когда достигается максимальное количество итераций. Поскольку массив means применяется только для вычисления центров масс, вы, возможно, захотите провести рефакторинг Cluster, поместив вызов UpdateMeans внутрь метода UpdateCentroids.

Перед запуском цикла обработки метод InitClustering инициализирует массив clustering:

Метод InitClustering сначала назначает последовательности от 0 до numClusters–1 кластерам от 0 до numClusters–1 соответственно, благодаря чему изначально в каждом кластере будет минимум одна последовательность. Остальные последовательности назначаются случайно выбранным кластерам.

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

Поиск аномальных данных

Один из способов использования кластеризации данных — простой анализ различных кластеров и поиск неожиданных или выпадающих результатов. Другая возможность — поиск необычных последовательностей данных в кластере. Демонстрационная программа проверяет кластер 0, чтобы найти последовательность в этом кластере, находящуюся дальше всего от центра масс кластера, используя метод Outlier, показанный на рис. 8.

Рис. 8. Метод Outlier

После инициализации массивов means и centroids метод Outlier перебирает каждую последовательность в указанном кластере и вычисляет евклидово расстояние (метрику) от текущей последовательности до центра масс (центроида) кластера, а затем возвращает значения последовательности, которая имеет наибольшее расстояние до центроида. В качестве альтернативы можно возвращать индекс самой дальней последовательности данных.

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

Процедуры отображения

Для полноты картины ниже показаны некоторые упрощенные процедуры отображения. В пакете исходного кода эти процедуры посложнее. Если вы используете упрощенные процедуры, то должны будете модифицировать их вызовы в методе Main. Чтобы отобразить исходные данные, средние и центры масс, вы можете применить:

Для вывода массива clustering можно использовать:

Чтобы показать выпадающие данные:

А для отображения исходных данных, сгруппированных по кластерам:

Заключение

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

Выражаю благодарность за рецензирование статьи эксперту Даррену Герингу (Darren Gehring).

Читайте также: