Кластерный анализ

Кластерный анализ впервые применил на практике ученый Роберт чоут Трион (1901-1967). В своих исследованиях он, пытаясь объединить те или иные группы по определенным критериям, начал тем самым формировать кластеры. Отсюда следует, что кластер — это группы схожих объектов, объединяющихся по определенным критериям.
Кластеризация – это разбиение элементов некоторого множества на группы на основе их схожести. Задача кластеризации состоит в разбиении объектов из X на несколько подмножеств (кластеров), в которых объекты более схожи между собой, чем с объектами из других кластеров.
Задачу кластеризации можно ставить как задачу дискретной оптимизации: необходимо так приписать номера кластеров yi объектам xi , чтобы значение выбранного функционала качества приняло наилучшее значение. Существует много разновидностей функционалов качества кластеризации, но нет «самого правильного» функционала. По сути дела, каждый метод кластеризации можно рассматривать как точный или приближённый алгоритм поиска оптимума некоторого функционала.
Среднее внутрикластерное расстояние должно быть как можно меньше:
F0=ij[yi=yj]ρ(xi;xj)ij[yi=yj ]→min
Среднее межкластерное расстояние должно быть как можно больше:
F1=ij[yi≠yj]ρ(xi;xj)ij[yi≠yj ]→max
Если алгоритм кластеризации вычисляет центры кластеров µy, y ∈ Y , то можно определить функционалы, вычислительно более эффективные. Сумма средних внутрикластерных расстояний должна быть как можно меньше:
Ф0=y∈Y 1|Ky|i: yi=yρ2xi,μy→min, где Ky={xi∈Xl|yi=y}-кластер с номером y. В этой формуле можно было бы взять не квадраты расстояний, а сами расстояния. Однако, если ρ — евклидова метрика, то внутренняя сумма в Φ0 приобретает физический смысл момента инерции кластера Ky относительно его центра масс, если рассматривать кластер как материальное тело, состоящее из |Ky| точек одинаковой массы. Сумма межкластерных расстояний должна быть как можно больше:
Ф1=y∈Yρ2(μy,μ)→max
Дисперсионный анализ—оценка степени воздействия фактора на измеряемые данные.
Приведем пример кластеризации. Кластеризация в агентстве используется для решения трех основных задач. Все они между собой достаточно связаны, предполагают обобщение клиентов, выделение из общего массива клиентов каких-либо групп клиентов по определенным признакам. Вручную это сделать невозможно, поэтому необходима помощь специальных математических алгоритмов. Три основные задачи, в которых используются алгоритмы кластеризации—это задача кластеризации результатов опросов, затем задача кластеризации клиентов (разделение клиентов на группы в зависимости от их поведения и задача кластеризации, связанная с целью выявления мошенничества или любой подозрительной активности со стороны клиентов, которая не укладывается в шаблон стандартного поведения клиента.
Рассмотрим подробнее, на основе каких данных проводится кластеризация. Для этого возьмем пример обработки опросов (кластеризация опроса).
После того, как опрос завершен, все данные агрегируются и сводятся в таблицу, в которой по строкам находятся клиенты или респонденты, которые прошли опрос, по столбцам-ответы на вопросы. Кластеризация проводится не по всей выборке, а на основе результатов факторов выбора клиентов с целью выявления особенностей поведения клиентов при осуществлении выбора. То есть какие факторы для каких групп клиентов более важны, а какие-менее. Кластеризация в этом случае позволяет объединить клиентов в группы в зависимости от того, как они отвечали на вопросы анкеты. Клиенты с похожими ответами на вопросы окажутся в одной группе.
Для того, чтобы обработать данные и подготовить их для проведения кластеризации, необходимо взять результаты опросов, выделить из них часть, касающуюся проведения опросов по факторам выбора. Здесь клиенты отвечают, насколько важен тот или иной фактор выбора при принятии решения, например об участии в какой-то выставке. Каждый показатель оценивался по десятибалльной шкале. При этом 10 баллов характеризуют наибольшую оценку, а один балл - самую низкую.
Для обработки результатов опроса с помощью кластерного анализа предлагается использовать метод К-средних, который заключается в том, что определяются эталонные кластеры, а далее каждый объект присоединяется к ближайшему эталону

. В качестве критерия используется минимальное расстояние внутри кластера относительно среднего.Фактически, алгоритм заканчивается дерево-подобным визуальным представлением наблюдений, называемым дендрограммой, которая позволяет увидеть разбиения, полученные для каждого возможного числа кластеров, от 1 до n.
Рисунок 1. Дендограмма
По рисунку 1 изначальный поток данных проходит по фильтрам, тем самым отсеивается нужная информация, создается кластер (рисунок 1).
Для выполнения кластеризации сначала нужно определить желаемое число кластеров К, затем алгоритм К-средних будет относить каждое наблюдение в точности к одному из К кластеров.
Рисунок 2. Кластеризация К-средних
Рассмотрим алгоритм K-средних:
1. Произвольным образом присваиваем номер от 1 до К каждому из наблюдений. Это послужит начальным разделением на классы.
2. Повторяем, пока разбиение на классы не перестанет меняться:
(a) Для каждого из К кластеров вычисляем кластерный центроид. Центроид k-го кластера – это вектор средних p характеристик для наблюдений в k-м кластере.
(b) Относим каждое наблюдение к тому кластеру, чей центроид ближайший (где ближайший определяется с использованием Евклидова расстояния).
Рисунок 3. Процесс кластеризации для K=3. В правом
нижнем углу – результат кластеризации после
10 итераций
Потенциальный недостаток кластеризации К-средних – предопределение числа кластеров К. Иерархическая кластеризация – это альтернативный подход, который не требует выбора К.
Возможны различные виды критериев (функционалов) разбиения множества на кластеры. Заметим, что эта задача тесно связана с определением некоторой метрики в пространстве признаков.
Рассмотрим наиболее широко используемые функционалы качества разбиения:
Коэффициент разбиения F, который определяется следующим образом:
F=j=1Ki=1nwij2n (1)
где   wij∈[0,1]— некоторая степень принадлежности i–го объекта j–му кластеру. Диапазон изменения F∈[1 K;1]  , где n — число объектов, K — число кластеров.
Индекс четкости:
NFI=nF-1K-1 ,NFI∈ [0;1] (2),где K — число классов (кластеров); F — коэффициент разбиения.
Энтропия разбиения:
Н=-j=1Ki=1nwij*ln⁡(wij)n (3)
Нормализованная энтропия разбиения
H1∈(0;n*lkKn-K) (4), где n — число точек;
Модифицированная энтропия:
H2=Hlk k, H2∈(0;nn-K) (5)
Второй функционал Рубенса:
F2=12(1ni=1nmaxjwij+minimaxjwij), F2 ∈[0;1] (6)
Третий функционал Рубенса (второй индекс четкости):
NF2I=K*F2-1K-2 , NF2I∈0;1(7)
Поскольку исходная информация задается в виде матрицы Х, то возникает проблема выбора метрики. Выбор метрики — наиболее важный фактор, влияющий на результаты кластер–анализа. В зависимости от типа признаков используются различные меры близости (метрики).
Пусть имеются образцы  и  в N–мерном пространстве признаков.
Основные метрики, используемые при кластеризации, приводятся в таблице 1.
Таблица 1 — Основные типы метрик при кластер-анализе
N Наименование метрики Тип признаков Формула для оценки меры близости (метрики)
1 Эвклидово расстояние Количественные dik=j=1N(xij-xkj)21/2
2 Мера сходства Хэмминга Номинальные (качественные) μijH=nikN, где   — число совпадающих признаков у образцов Xi и Xk
3 Мера сходства Роджерса–Танимото
Номинальные шкалы μijR-T=nik"(ni'+nk'-nik", где  nik" — число совпадающих единичных признаков у образцов Xi и Xk ; ni' , nk'  — общее число единичных признаков у образцов Xiи Xk  соответственно
4 Манхэттенская метрика Количественные dik(1)=j=1N|xij-xkj|
5 Расстояние Махалонобиса
Количественные dikm=xij-xkjTW-1xij-xkj, где W — ковариационная матрица выборки
6 Расстояние Журавлева Смешанные dik=j=1NIikj, где Iikj=1, если xij-xkjε0, иначе
Существует большое число алгоритмов кластеризации, которые используют различные метрики и критерии разбиения. При этом число классов (кластеров) либо задается априори, либо определяется в процессе работы самого алгоритма.
Выбор масштаба в кластерном анализе имеет большое значение. Рассмотрим пример. Представим себе, что данные признака х в наборе данных А на два порядка больше данных признака у: значения переменной х находятся в диапазоне от 100 до 700, а значения переменной у - в диапазоне от 0 до 1