Кластеризация. Типы алгоритмов. Методы и средства анализа данных

Что делать, если нет обучающего материала для построения классификатора? То есть нет учителя, который покажет, как следует классифицировать тот или иной объект?

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

Рассмотрим каждый из этапов более подробно.

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

На втором этапе выбирают, как охарактеризовать сходство объектов. Для этого используются различные меры близости, то есть, фактически, оценки близости двух объектов друг к другу. Меры близости выбирают, исходя из свойств объектов. Так, популярной мерой близости является декартово расстояние (в двумерном случае):

d 2 ( < x 1, y 1 > , < x 2, y 2 > ) = s q r t ((x 1 - x 2) 2 + (y 1 - y 2) 2)

или метрика Минковского в многомерном случае:

d n (x, y) = | | X, Y | |

Это достаточно хорошие меры близости для представимых на координатной плоскости значений. Для нечисленных атрибутов подбирают такие меры близости, которые позволяют свести их к численным и сравнить. Так, основным расстоянием для строк является метрика Левенштейна, которая устанавливает расстояние между двумя строками равным количеству перестановок, которые необходимо совершить, чтобы превратить одну строку в другую. Мера близости подбирается индивидуально для конкретных типов данных. Иногда адекватной меры близости подобрать не удается, и приходится ее придумывать самим.

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

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

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

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

Классификация алгоритмов

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

Иерархические алгоритмы

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

Представление результатов иерархического алгоритма

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

Алгоритм ближайшего соседа

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

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

Кластеризация. Итеративные и плотностные алгоритмы

Итеративные алгоритмы

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

Алгоритм k-means

Общая идея алгоритмов *-means: Минимизация расстояний между объектами в кластерах. Останов происходит, когда минимизировать расстояния больше уже невозможно. Минимизируемая функция в случае k-means такова: $J = \sum_{k=1}^{M} {\sum_{i=1}^{N} d^2(x_{i}, c_{k}) },$ $x_i \in X$ - объект кластеризации (точка) $c_j \in C$ - центр кластера (центроид).

| X | = N, | C | = M

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

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

1. Итеративное перераспределение объектов по кластерам. Объекты распределяются по кластерам путем подсчета расстояния от объекта до центров кластеров и выбора наименьшего.

2. Когда все объекты распределены по кластерам, заново считаются их центры. $c_j = {{\sum_{i=1}^{L} x_i} \over {L}}$ $, x_i \in C_j, |C_{j}|=L$ (можно считать по каждой координате отдельно)

3. Если

c j = c j - 1,

то это означает, что кластерные центры стабилизировались и соответственно распределение закончено. Иначе переходим к шагу 1.

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

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

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

Более строгой интерпретацией этого алгоритма является алгоритм hard c-means. Его отличия - в минимизируемой функции и строгости самого алгоритма:

$J = \sum_{i=1}^{N} {\sum_{k=1}^{M} u_{ij}d^2(x_{i}, c_{k}) },$

u i j = 1,

если $x_i \in C_j$ , и

u i j = 0,

, если нет. То есть минимизируется расстояние от точек до центроида, а не от центроида до точек.

Тогда формула центроида тоже несколько меняется:

Farthest First - еще одна модификация k-means, особенностью его является изначальный выбор центроидов - от 2 и выше они выбираются по принципу удаленности от остальных(центроидом выбирается точка, наиболее отдаленная от остальных центроидов).

Алгоритм Fuzzy C-Means

Нечеткие методы - это методы, основанные не на бинарной логике - где все четко - элемент либо принадлежит одному кластеру, либо другому - а на предположении, что каждый элемент в какой-то степени принадлежит определенному кластеру. m - мера нечеткости, она как раз определяет нечеткость алгоритма. Минимизируемая функция почти аналогична hard c-means:

0. Выбираем число классов M, меру нечеткости $1<m<\infty,$ функцию расстояний d(c,x) (обычно

d (c, x) = | | x - c | | 2

), критерий окончания поиска

0 < ε < 1

. Задаем матрицу $U^{0}=\{{u_{ij}({x_i, c_j}): x_i \in X, c_j \in C}\}$ весов принадлежности точки $x_i \in X$ к кластеру $j \in C$ с центром

c j

для всех точек и кластеров (можно взять принадлежности к кластеру из k-means или просто по рандому, ограничения $0<u_{ij}<1, 0<\sum_{i=1}^{N}u_{ij}<N$ для $\forall { } 0 \le j \le C, \sum_{j=1}^{C}u_{ij}=1$ для $\forall { } 0 \le i \le N$ (вытекают в общем из определения нечеткой принадлежности)).

$u_{ij} = \frac{1}{\sum_{k=1}^{M} \left(\frac{d(c_j,x_i)}{d(c_k,x_i)}\right)^{2/(m-1)}}.$

3. Проверяем

| | U k - U k - 1 | | < ε

(чаще всего достаточно $max_{ij} ||u_{ij}^k - u_{ij}^{k-1}||<\epsilon)$ - если да, то заканчиваем, если нет, то переходим к шагу 1.

Плотностные алгоритмы

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

d (x i, x j) < ε

для некоторого количества j > Minpts.

Алгоритм DBSCAN

Алгоритм DBSCAN обычно проводится над данными, упорядоченными в R-деревья (для удобства выборки окрестных точек). Но в общем случае этого не требует.

0. Выбираем окрестность

ε,

в которой мы будем требовать наличия Minpts объектов, и сам Minpts.

1. Берем произвольный еще не обработанный объект. Проверяем для него, что в эпсилон-окрестности точки есть некоторое минимальное количество других объектов:

d (x i, x j) < ε

для некоторого количества j > Minpts. Если это не так, то очевидно, что эта точка - шум. Берем следующую.

2. Если это не так, то помечаем эту точку как принадлежащую кластеру. Это так называемая корневая точка. Заносим окружающие ее точки в отдельную категорию.

2.1. Для каждой еще не обработанной точки из этой категории сначала помечаем ее как принадлежащую кластеру, а затем проверяем то же самое: что в эпсилон-окрестности точки есть некоторое минимальное количество других объектов:

d (x i, x j) < ε

для некоторого количества j > Minpts. Если это так, то заносим эти точки в эту же категорию.

2.2. После проверки выносим точку из этой временной категории. Очевидно, что рано или поздно точки в данной категории кончатся (мы достигнем границ кластера, где правило кучности не выполняется). Тогда переходим к шагу 1. Иначе возвращаемся к шагу 2.1.

Этот алгоритм имеет сложность O(NlogN). Очевидно, что основным его недостатком является неспособность связывать кластеры через узкие места, где правило плотности не выполняется.

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

Модельные алгоритмы

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

Алгоритм EM

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

Алгоритм использует широко известный метод максимизации ожиданий (Expectation Maximization). В наиболее простом случае предполагается, что кластер - это результаты наблюдений, распределенные нормально. Тогда для их характеристики можно применять многомерную функцию Гаусса (многомерное распределение Гаусса) $N(\mu, {\sigma}^2) = P(x_i | x_i \in w_j, \lambda ), w_j -$ - одно из распределений. И тогда основная задача - это определить, к какому из распределений принадлежит каждая конкретная точка, оценив параметры этих распределений исходя из реального распределения точек.

0. Инициализируем : ${\lambda}^{0} = \{{\mu}_{1}^{0},...,{\mu}_{K}^{0}, {\sigma}_1^,P_{1}^{0}(w_1),...,P_{K}^{0}(w_K) \}$ - среднее отклонение распределений относительно начала координат (т.е. центры кластеров) и вероятности этих распределений для каждой точки. K - число кластеров - задаем.

$P({\omega}_{j} | x_i, {\lambda}^{t}) =\frac {P(x_i | {\omega}_{j}, {\lambda}^{t} ) P({\omega}_{j}| {\lambda}^{t}) } {P (x_i | {\lambda}^{t})} = \frac {P(x_i |{\omega}_{j}, {\mu}_j^{t}, ({\sigma}_j^t)^2)) P_j^{t}}{\sum_{j=1}^K {P(x_i | {\omega}_{j}, {\mu}_j^{t}, ({\sigma}_j^t)^2)) P_j^{t}} }$ ,

где $P(x_i |{\omega}_{j}, {\mu}_j^{t}, ({\sigma}_j^t)^2)$ -функция плотности распределения.

${\mu}_j^{t+1} = \frac {\sum_i { P({\omega}_{j} | x_i, {\lambda}^{t}) x_i}} {\sum_i {P (w_j | x_i, {\lambda}^{t} ) }}$

${\sigma}_j^{t+1} = \frac {\sum_{i=1}^N {P(w_j|x_i, {\lambda}^t)(x_i- {\mu}_j)(x_i- {\mu}_j)^T}} {\sum_{i=1}^N {P(w_j|x_i, {\lambda}^t)}}$

3. Вычисление $P(x_i | {\mu}_j)^{t+1} = \prod_{i=1}^{N} {\sum_{j=1}^{K} {P(w_j)P(x_i|w_j,{\lambda}^{t+1})}}$ и сравнение с

P (x i | μ j) t

, если да, то стоп - найден локальный максимум. Если нет, то переходим снова к шагу 1.

Концептуальные алгоритмы

Алгоритм Cobweb

В алгоритме COBWEB реализовано вероятностное представление категорий. Принадлежность категории определяется не набором значений каждого свойства объекта, а вероятностью появления значения. Например,

P (A j = υ i j | C k)

- это условная вероятность, с которой свойство

A j

, принимает значение

υ i j

, если объект относится к категории

C k

. Для каждой категории в иерархии определены вероятности вхождения всех значений каждого свойства. При предъявлении нового экземпляра система COBWEB оценивает качество отнесения этого примера к существующей категории и модификации иерархии категорий в соответствии с новым представителем. Критерием оценки качества классификации является полезность категории (category utility). Критерий полезности категории был определен при исследовании человеческой категоризации. Он учитывает влияние категорий базового уровня и другие аспекты структуры человеческих категорий.

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

Значения суммируются по всем категориям

C k

, всем свойствам

A j

и всем значениям свойств

υ i j

. Значение

P (A j = υ i j | C k)

называется предсказуемостью (predictability). Это вероятность того, что объект, для которого свойство

A j

- принимает значение

υ i j

, относится к категории

C k

. Чем выше это значение, тем вероятнее, что свойства двух объектов, отнесенных к одной категории, имеют одинаковые значения. Величина

P (C k | A = υ i j)

называется предиктивностью (predictiveness). Это вероятность того, что для объектов из категории

C k

свойство

A j

принимает значение

υ i j

. Чем больше эта величина, тем менее вероятно, что для объектов, не относящихся к данной категории, это свойство будет принимать указанное значение. Значение

P (A = υ i j

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

После некоторых преобразований (Байеса в частности) и некоторых агрументированных изменений мы получаем более правильную формулу:

$CU= \frac{ \sum_{k=1}^N {P(A={\upsilon}_{ij}|C_k)} \sum_{j} { \sum_{i} {({P(C_k | A={\upsilon}_{ij})}^2 - {P(A={\upsilon}_{ij})}^2)}}}{N}$ N -число категорий.

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

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

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

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

Сетевые алгоритмы

Метод WaveCluster

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

Для применения алгоритма надо выбрать, какой именно фильтр будет применяться (какое именно из вейвлет-преобразований будет применяться).

0. Квантификация данных. Именно за это алгоритм называется сетевым. Каждое l-ное , $1 < l \le D$ измерение D-мерного пространства данных (то есть каждый атрибут) разделяется на

m l

отрезков длиной

s l

. Тогда в D-мерном пространстве существует N точек

M j = (μ 1,...,μ l,...,μ d)

, где

μ

- это некоторое количество отрезков длиной

s l

. Тогда $1 \le {\mu}_l \le m_l, N=\prod_{l=1}^D m_l$ (если число

m l = m

одинаково по всем осям, то

N = m D

) .

И тогда объекту $x_i = (x_i^1, ..., x_i^l,...,x_i^D)$ назначается в сооветствие

M j

, когда для каждого

l

$(\mu_l -1)s_l \le x_i < \mu_l s_l.$ Фактически мы разбили все D-мерное пространство, в котором расположены наши объекты, на некую совокупность D-мерных прямоугольных призм (кубиков), характеризуемых наиболее дальней от начала координат точкой призмы

M j

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

1. Применение вейвлет-преобразования. Теперь мы применяем дискретное вейвлет-преобразование к этим точкам

M j

. Тогда на выходе мы получаем новую совокупность точек

T k

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

2. Обнаружение кластеров в измененном пространстве признаков. В измененном пространстве признаков ищутся связанные компоненты </math>T_k</math>. Они являются кластерами. Более того, в общем случае многомерного пространства можно искать в подпространствах, которые также формируются вейвлет-преобразованием и в которых поиск гораздо легче в силу меньшей размерности этих пространств. В результате поиск сводится к поиску связанных компонент в двумерной картинке. В первом проходе находятся все связанные компоненты в картинке, и во втором - им назначают метки кластеров, отбрасывая уже отмеченные. Тогда мы получаем некоторое количество кластеров С и их меток

c f

3. Создание таблицы соответствия. На этом этапе через соответствие исходных точек

M j

и полученных в результате преобразования

T k

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

M j

к определенному кластеру

c f

4. А так как мы знаем, каким точкам соответствует

M j

, мы получаем и соответствие этих кластеров конкретным точкам.

Знаете ли Вы, что в 1974 - 1980 годах профессор Стефан Маринов из г. Грац, Австрия, проделал серию экспериментов, в которых показал, что Земля движется по отношению к некоторой космической системе отсчета со скоростью 360±30 км/с, которая явно имеет какой-то абсолютный статус. Естественно, ему не давали нигде выступать и он вынужден был начать выпуск своего научного журнала "Deutsche Physik", где объяснял открытое им явление. Подробнее читайте в FAQ по эфирной физике.

CU =	∑	∑	∑	P(A = υ_ij \| C_k)P(C_k \| A = υ_ij)P(A = υ_ij)
	k	i	j

Методы и средства анализа данных

Кластеризация. Типы алгоритмов

Постановка задачи