Кластеризация. 
Системы поддержки принятия решений

Кластеризация — группировка объектов (наблюдений, событий) на основе данных, описывающих свойства объектов.

Объекты внутри кластера должны быть похожими друг на друга и отличаться от других, которые вошли в другие кластеры. В задачах кластеризации не требуется указание выходной переменной, т. е. имени кластера, а число кластеров, в которые необходимо сгруппировать все множество данных, может быть неизвестным. Выходом кластеризации является не готовый ответ (например, «плохо"/"удовлетворителыю"/"хорошо»), а группы похожих объектов — кластеры. Кластеризация указывает только на схожесть объектов, и не более того. Для объяснения образовавшихся кластеров необходима их дополнительная интерпретация. Кластеризация может использоваться, например, для сегментации и построения профилей клиентов банка, телекоммуникационной или страховой кампаний. Так, в задаче определения групп клиентов при достаточно большом их числе становится трудно подходить к каждому индивидуально, поэтому их удобно объединять в группы — сегменты с однородными признаками. Выделять сегменты можно по нескольким группам признаков, например по сфере деятельности, географическому расположению, статусу и т.и. После кластеризации можно узнать, какие сегменты наиболее активны, какие приносят наибольшую прибыль, выделить характерные для них признаки.

Эффективность работы с клиентами повышается благодаря учету их персональных предпочтений. Задача кластеризации известна давно, и специалисты в различных областях знаний оперируют рядом других терминов — таксономия, сегментация, группировка, автоматическая классификация и др. В Data Mining используется термин «кластеризация». Например, в бизнес-аналитике кластеризация применяется для решения следующих задач.

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

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

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

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

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

Сегодня предложено несколько десятков алгоритмов кластеризации и еще больше их разновидностей. Несмотря на это, в Data Mining применяются в первую очередь понятные и простые в использовании алгоритмы. К таким относится алгоритм k-means — в русскоязычном варианте^{-средних} (от англ, mean — среднее значение). Его основная идея состоит в том, что для выборки данных, содержащей п записей (объектов), задается число кластеров — k_y на которые эта выборка и разбивается. Алгоритм выполняется в четыре шага.

• 1. Задается число кластеров — k, которые должны быть сформированы из объектов исходной выборки.
• 2. Случайным образом выбирается к записей исходной выборки, которые будут служить начальными центрами кластеров. Начальные точки, из которых потом вырастает кластер, часто называют «семенами» (от англ, seeds — семена, посевы). Каждая такая запись представляет собой своего рода «эмбрион» кластера, состоящий только из одного элемента.
• 3. Для каждой записи исходной выборки определяется ближайший к ней центр кластера. Чтобы определить, в сферу влияния какого центра кластера входит та или иная запись, вычисляется расстояние от каждой записи до каждого центра в многомерном пространстве признаков и выбирается то «семя», для которого данное расстояние минимальное.

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

Евклидово расстояние, или метрика L₂, применяется для вычисления расстояний по формуле.

где X = (х_и х₂, х_т), Y = (у_{, у₂, у_т) — векторы значений признаков двух записей.

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

Расстояние Манхэттена, или метрика L_{, вычисляется по формуле.

Фактически расстояние Манхэттена — кратчайшее расстояние между двумя точками, пройденное по линиям, параллельным осям координатой системы. Преимущество метрики L₁ заключается в том, что она позволяет снизить влияние аномальных значений на работу алгоритмов. Кластеры, построенные на основе расстояния Манхэттена, стремятся к кубической форме.

С использованием метрики L_{ или Ь₂ для каждой записи исходной выборки и определяется ближайший к ней центр (центроид) кластера.

Например, если в кластер вошли три записи с наборами признаков (^ху Уi), (х₂, у₂), (х₃, ау₃), то координаты его центроида по метрике Ь_{ будут рассчитываться следующим образом:

4. Старый центр кластера смещается в его центроид.

Таким образом, центроиды становятся новыми центрами кластеров для следующего итерации алгоритма. Шаги 3 и 4 повторяются до тех пор, пока выполнение алгоритма не будет прервано или пока не будет выполнено условие в соответствии с некоторым критерием сходимости.

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

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

где ре С, — произвольная точка данных, принадлежащих кластеру С,; га, — — центроид данного кластера.

Иными словами, алгоритм остановится тогда, когда ошибка? достигнет достаточно малого.

Один из основных недостатков, присущих алгоритму k-means, — отсутствие четких критериев выбора числа кластеров, целевой функции их инициализации и модификации. Кроме того, он очень чувствителен к шумам в данных и аномальным значениям, поскольку они способны существенно повлиять на среднее значение, используемое при вычислении положений центроидов. Чтобы снизить влияние таких факторов, как шумы и аномальные значения, иногда на каждой итерации используют не среднее значение признаков, а их медиану. Данная модификация алгоритма называется k-mediods (^-медиан).

Пример 10.1.

Работа алгоритма k-means

Пусть имеется набор из восьми точек данных в двумерном пространстве, из которого требуется получить два кластера. Значения точек приведены в табл. 10.1 и на рис. 10.4.

Таблица 10.1

Объекты для кластеризации.

Рис. 10.4. Процедура начальной инициализации:

значения буллитов приведены в табл. 10.1.

Шаг 1. Определим число кластеров, на которое требуется разбить исходное множество: к = 2.

Шаг 2. Случайным образом выберем две точки, которые будут начальными центрами кластеров. Пусть это будут точки т_{ = (1; 1) и т₂ = (2; 1). На рис. 10.4 они представлены ромбами.

Шаг 3, проход 1. Для каждой точки определим ближайший к ней центр кластера с помощью евклидова расстояния. В табл. 10.2 представлены вычисленные с помощью формулы d_E(X, Y) =^Х (я', -г/_;)² расстояния между центрами кластеров т_л =.

= (1; 1) и т₂ = (2; 1) и каждой точкой исходного множества и указано, к какому кластеру принадлежит та или иная точка.

Таблица 10.2

Нахождение ближайшего центра для каждой точки (первый проход).

Таким образом, кластер 1 содержит точки Л, Е, G, а кластер 2 — точки В, С, Д F, Н. Как только определятся члены кластеров, может быть рассчитана сумма квадратов ошибок:

Шаг 4, проход 1. Для каждого кластера вычисляется центроид, и в него перемещается центр кластера.

Центроид для кластера 1: [(1 + 1 + 1) / 3, (3 + 2 + 1) / 3] = (1; 2).

Центроид для кластера 2: [(3+ 4 + 5 + 4 +2)/5, (3 + 3 + 3 + 2 + 1)/5] = (3,6; 2,4).

Расположение кластеров и центроидов после первого прохода алгоритма представлено на рис. 10.5.

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

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

Относительно большое изменение т₂ привело к тому, что запись Я оказалась ближе к центру т_{, что автоматически сделало ее членом кластера 1. Все остальные записи остались в тех же кластерах, что и на предыдущем проходе алгоритма. Таким образом, кластер 1 будет содержать точки А, Е, G, Я, а кластер 2 — В, С, Д F. Новая сумма квадратов ошибок составит

Рис. 10.5. Расположение кластеров и центроидов после первого прохода алгоритма Нахождение ближайшего центра для каждой точки (второй проход).

Таблица 103

Вычисление показывает уменьшение ошибки в сравнении с начальным состоянием центров кластеров (на первом проходе она составляла 36). Это говорит об улучшении качества кластеризации, т. е. о более высокой «кучности» объектов относительно центра кластера.

Шаг 4у проход 2. Для каждого кластера вновь вычисляется центроид, и в него перемещается центр кластера.

Новый центроид для кластера 1: [(1 + 1 + 1 + 2) / 4, (3 + 2 + 1 + 1)/4] = (1,25; 1,75).

Новый центроид для кластера 2: [(3 + 4 + 5 + 4) /4, (3 + 3 + 3 + 2) / 4] = (4; 2,75).

Расположение кластеров и центроидов после второго прохода алгоритма представлено па рис. 10.6.

По сравнению с предыдущим проходом центры кластеров изменились незначительно.

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

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

Рис. 10.6. Расположение кластеров и центроидов после второго прохода алгоритма Нахождение ближайшего центра для каждой точки (третий проход).

Таблица 10.4

Таким образом, сумма квадратов ошибок изменилась незначительно по сравнению с предыдущим проходом.

Шаг 4, проход 3. Для каждого кластера вновь вычисляется центроид, и центр кластера в него перемещается. Но поскольку на данном проходе ни одна запись не изменила своего членства в кластерах и положение центроидов не поменялось, алгоритм завершает работу.

Алгоритм k-means приобрел популярность благодаря следующим свойствам. Один из основных недостатков, присущих алгоритму k-means, — отсутствие четких критериев выбора числа кластеров, целевой функции их инициализации и модификации. Кроме того, он очень чувствителен к «шумам» в данных и аномальным значениям, поскольку они способны существенно повлиять на среднее значение, используемое при вычислении положений центроидов. Чтобы снизить влияние таких факторов, как шумы и аномальные значения, иногда на каждой итерации используют не среднее значение признаков, а их медиану. Данная модификация алгоритма называется k-mediods (^-медиан).

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

Карта состоит из сегментов прямоугольной или шестиугольной формы, называемых ячейками. Каждая ячейка связана с определенным выходным нейроном и представляет собой «сферу влияния» данного нейрона. Распределение векторов весов нейронов карты происходит на основе обучения. Объекты, векторы признаков которых оказываются ближе к вектору весов данного нейрона, попадают в ячейку, связанную с ним, и распределение объектов на карте в целом соответствует распределению векторов весов нейронов. Следовательно, если объекты на карте расположены близко друг к другу, то и векторы признаков этих объектов близки, и наоборот: если ячейки с объектами находятся далеко друг от друга, то и векторы их признаков будут существенно различаться. Хотя расстояние между объектами позволяет сделать выводы о степени их сходства или различия, также важна информация о том, в чем проявляется это сходство и различие, но каким признакам объекты различаются в наибольшей степени, а по каким — в наименьшей и т. д. Специальная раскраска помогает получить ответы на эти вопросы, выполняя функцию третьего измерения. Идея состоит в том, что каждой ячейке на карте назначается цвет в соответствии со значениями признаков объектов в ней. Таким образом, важны два фактора: положение объекта на карте (расстояние до других объектов), и цвет ячейки. Ячейки бывают прямоугольной и шестиугольной формы. Шестиугольные ячейки более корректно отражают расстояния между объектами на карте, поскольку в этом случае расстояния между центрами смежных ячеек будут одинаковыми. В случае же прямоугольных ячеек расстояния между центрами смежных ячеек зависят от их взаимного расположения.

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

Задача на построение СКК рассмотрена ниже.