Иерархическая таксономия

Принципы

в ГИС INTEGRO, иерархическая таксономия (иерархический кластерный анализ) - вид кластерного анализа, при котором кластеры, входящие в разбиение нижнего уровня, объединены в иерархическую структуру - некоторые два кластера объединяются в один (супер-)кластер более высокого уровня, и так до тех пор, пока не останется один кластер, в который входят все объекты. Таким образом, над кластерами разного уровня определено отношение включения. Различные срезы иерархии определяют "плоские" разбиения, которые сохраняются в ТОС как классовое свойство.

Алгоритмы иерархической кластеризации делятся на 2 типа: агломеративные и дивизивные.

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

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

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

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

На данный момент в ГИС INTEGRO реализованы следующие алгоритмы иерархической кластеризации: метод одиночной связи, центроидный взвешенный метод и метод Варда.

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

1) Выбрать два кластера ${\displaystyle S_i,S_j}$ таких, что расстояние между ними, взятое по метрике одиночной связи, является минимальным среди всех возможных пар: ${\displaystyle (i,j)=argmi{n}_{i,j}(dist(S_i,S_j)}$.

2) Поместить объекты из кластеров S_i, S_j в новый кластер S_k, и не рассматривать кластеры S_i и S_j в дальнейших итерациях.

Метрика одиночной связи выражает расстояние между двумя кластерами S_i и S_j как минимальное евклидово расстояние между любыми парами объектов, такими что объекты из этих пар принадлежат различным кластерам: ${\displaystyle dist(S_i,S_j)=mi{n}_{p\in S_i,q\in S_j}||x_p-x_q||}$, где x_p – вектор свойств объекта p.

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

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

${\displaystyle dist(S_i,S_j)=||M[x_p]{|}_{p\in S_i}-M[x_q]{|}_{q\in S_j}||}$

Взвешенность метода обозначает, что метрика взвешивается по количеству кластеров по следующей формуле:

${\displaystyle distw(S_i,S_j)=dist(S_i,S_j)\frac{N[S_i]N[S_j]}{N[S_i]+N[S_j]}}$

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

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

${\displaystyle dist(S_i,S_j)=D[S_i\cup S_j]-(D[S_i]+D[S_j])=D_{intragroup}[S_i,S_j]}$

, где D[S_i] имеет смысл дисперсии векторов признаков, принадлежащих кластеру, ${\displaystyle D_{intragroup}[\cdot ,\cdot \cdot ]}$ - интрагрупповая дисперсия. Метод имеет то же свойство, что и взвешенный центроидный метод, – избегание создания множества малых кластеров.

Метод полной связи имеет метрику следующего вида:

${\displaystyle dist(S_i,S_j)=ma{x}_{p\in S_i,q\in S_j}||x_p-x_q||}$

Метрика имеет смысл расстояния между двумя наиболее удалёнными объектами, принадлежащими кластеру.

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

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

Алгоритм выглядит следующим образом:

1. Найти кластер ${\displaystyle S_i}$ с максимальной дисперсией.

2. Найти направление, дающее наибольший вклад в дисперсию (метод аналогичен методу главных компонент) - главное направление.

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

4. Исключить кластер ${\displaystyle S_i}$ из рассмотрения и перейти к пункту 1, пока есть кластеры с ненулевой дисперсией, или не достигнуто условие остановки.

Особенности программной реализации

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

Инициализатор центров кластеров

На первом этапе двухэтапных алгоритмов используется предварительная кластеризация недетерминированными алгоритмами, то есть при двух запусках программы на одних и тех же данных и с одними и теми же выбранными алгоритмами и другими параметрами результаты получаются различные. Это связано с тем, что программа построения кластеризации использует генератор псевдослучайных чисел (ГПСЧ). Последовательность чисел, генерируемая ГПСК, определяется инициализацией его начального состояния, при этом он инициализируется при каждом запуске программы различным состоянием. Однако на практике часто требуется повторимость результата. Для того, чтобы программа продуцировала один и тот же результат, достаточно инициализировать ГПСЧ одними и теми же данными. Эти данные определяются параметром "инициализатор центров кластеров". Параметр принимает в качестве значения целое число в диапазоне от 0 до 2 млрд, и инициализируется случайным образом при запуске прогнозного блока.

Параметры

Алгоритм разбиения - В данной реализации выбор недоступен, используется "Растущий нейронный газ".

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

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

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

Рис. 1. Форма задания параметров для задачи Иерархическая таксономия

Параметры отрисовки Дендрограммы

Рис. 2. Дендрограмма, отображающая иерархию разбиения на классы

Начальное значение - минимальное количество классов отображаемое на дедрограмме

Конечное значение - максимальное количество классов отображаемое на дедргограмме

Количество кластеров - выбранное пользователем количество классов плоского разбиения, которое сохранится в свойство ТОС с выбранным именем; на дендрограмме отображается серой вертикалной линией.

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

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

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