Оптимизация средне-связного алгоритма Иерархической Кластеризации

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

В данной статье мы рассмотрим первый подход.

В большинстве случаев соединения происходят по принципу «жадного» алгоритма. А результатом иерархической кластеризации является дендрограмма.

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

Допустим существует набор из N элементов, которые нужно кластеризовать. Тогда будет существовать матрица расстояний размера NxN, и алгоритм будет состоять из следующих шагов :

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

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

Мы будем рассматривать алгоритм с методом средней связи.

В средне-связной кластеризации расстояние между кластерами определяется средним значением расстояния между их элементами.

Существует средне-связный алгоритм иерархической кластеризации со сложностью O(N²*log N), но он требует O(N² * (2 * sizeof(dataType) + sizeof(indexType))) памяти.

В приведенном ниже примере мы использовали схожий подход в улучшении асимптотики алгоритма, но снизили количество потребляемой памяти до O(N² * (sizeof(dataType) + 2 * sizeof(indexType))), где sizeof(dataType) > sizeof(indexType).

Пример #1

Абстрактные исходные данные перед построением дендрограммы.

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

Модификации исходного алгоритма

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

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

public float getCopheneticCorrelation(float[][] matrix) {

   matrix = Utils.toTriangularMatrix(matrix);
   
   Dendrogram dendrogram = getDendrogram(matrix); 
   …
}

activeRows = new TIntNSet(totalRowsCount);
for (int row = 0; row < rowsCount; ++row) {
   activeRows.addLast(row);
}

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

…
deactivateRow(minRow);
deactivateRow(minRowColumn);
…

…
activateRow(addedRow);
…
protected void deactivateRow(final int row) {
   activeRows.remove(row);
   tree.set(row, 0);
}

protected void activateRow(final int row) {
   activeRows.addLast(row);
   tree.set(row, 1);
}

2) Так как в алгоритме использовалась нижняя треугольная форма матрицы расстояний, и элементы в каждой строке были отсортированы, становится невозможным обновлять значения расстояний от элементов до нового кластера за O(1) без увеличения используемой памяти. Чтобы этого избежать, добавляется новый параметр, который сохраняет расположение элементов после сортировки.

this.rowColumns = new TShortIntArray[totalRowsCount]; //columns before sorting
this.rowColumnIndexes = new TShortIntArray[totalRowsCount]; //column positions after sorting

for (int row = 0; row < rowsCount; ++row) {
    Utils.DoubleValueIndexPair[] pairs = new Utils.DoubleValueIndexPair[row];
    for (int column = 0; column < row; ++column) {
        pairs[column] = new Utils.DoubleValueIndexPair(matrix[row][column], column);
    }

    Arrays.sort(pairs);

    rowColumns[row] = new TShortIntArray(row, row);
    rowColumnIndexes[row] = new TShortIntArray(row, row);

    for (int index = 0; index < row; ++index) {
        int column = pairs[index].index;
        rowColumns[row].setValue(index, column);
        rowColumnIndexes[row].setValue(column, index);
    }
}

3) Чтобы получить корректный индекс положения для требуемого столбца из третьего параметра, используется информация об удаленных строках. Исходная сложность этой операции O(N), но с использованием структуры дерева отрезков сложность снижается до O(log N).

4) Тем не менее, структура дерева отрезков увеличивает количество потребляемой памяти. Для каждого добавленного кластера требуется отдельная версия дерева, что требует O(N²) памяти. Для оптимизации достаточно добавить к дереву отрезков персистетнтность. Это уменьшит потребляемую память до O(log N). При работе с большими данными разница будет весьма существенной.

this.tree = new TPersistentSumSegmentTree(states, maxChangesCount);

Мы получаем расстояние от выбранных элементов и затем объединяем их.

float minRowDistance = getDistance(minRow, currentRow);
float minColumnDistance = getDistance(minRowColumn, currentRow);    

float addedRowDistance = getMergedDistance(minRow, minRowDistance, minRowColumn, minColumnDistance, addedRow);
protected int getColumnIndex(int row, int column) {
   if (row < rowsCount) {
      return column;
   }
   
   int changeRootIndex = (row - rowsCount + 1) * 3;
   int columnIndex = tree.getSum(changeRootIndex, 0, column) - 1;
   
   return columnIndex;
}

protected float getMergedDistance(int left, float leftDistance, int right, float rightDistance, int root) {
   float rootDistance = leftDistance * sizes[left] + rightDistance * sizes[right];
   rootDistance /= sizes[root];
      return rootDistance;
}

Пример #2 

Далее представлено применение иерархической кластеризации расстояний между городами США.

Исходная матрица расстояний:

Ближайшая друг к другу пара городов – это BOS и NY, которые находятся на расстоянии 206 миль. Они объединяются в кластер с названием "BOS/NY".

Далее мы вычисляем расстояние от нового кластера до остальных. Например, расстояние от "BOS/NY" до DC равно 331, что является средним значением расстояния от NY и BOS до DC. Аналогично расстояние от "BOS/NY" до DEN равняется 1860.

После объединения BOS с NY:

Ближайшая пара объектов - BOS/NY и DC, которые находятся на расстоянии 331. Они объединяются в кластер с названием "BOS/NY/DC". Далее мы вычисляем расстояние от нового кластера до остальных, чтобы получить новую матрицу расстояний:

После объединения DC с BOS-NY:

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

После объединения SF с LA:

Теперь ближайшая пара объектов CHI и BOS/NY/DC, которые находятся на расстоянии 776.75. Они объединяются в кластер с названием "BOS/NY/DC/CHI". Далее мы вычисляем расстояние от нового кластера до остальных, чтобы получить новую матрицу расстояний:

После объединения CHI с BOS/NY/DC:

Теперь ближайшая пара объектов SEA и SF/LA, которые находятся на расстоянии 808. Они объединяются в кластер с названием "SF/LA/SEA". Далее мы вычисляем расстояние от нового кластера до остальных, чтобы получить новую матрицу расстояний:

После объединения SEA с SF/LA:

Теперь ближайшая пара объектов DEN и SF/LA/SEA, которые находятся на расстоянии 1227. Они объединяются в кластер с названием "SF/LA/SEA/DEN". Далее мы вычисляем расстояние от нового кластера до остальных, чтобы получить новую матрицу расстояний:

После объединения DEN с SF/LA/SEA:

Теперь ближайшая пара объектов BOS/NY/DC/CHI и MIA, которые находятся на расстоянии 1284.75. Они объединяются в кластер с названием "BOS/NY/DC/CHI/MIA". Далее мы вычисляем расстояние от нового кластера до остальных, чтобы получить новую матрицу расстояний:

После объединения BOS/NY/DC/CHI с MIA:

В конце мы объединяем 2 последних кластера на уровне 1896.625.

В данной статье мы рассмотрели:

• Оригинальный алгоритм иерархической кластеризации
• Модификации алгоритма, снижающие сложность с O(N³) до O(N²  log N)
• Модификации, позволяющие снизить потребляемую память с O(N³) до O(N²  log N) с сохранением сложности O(N²  log N)
• Общий пример работы алгоритма

Список источников

• D'andrade,R. 1978, "U-Statistic Hierarchical Clustering" Psychometrika, 4:58-67.
• Johnson,S.C. 1967, "Hierarchical Clustering Schemes" Psychometrika, 2:241-254.
• http://habrahabr.ru/post/142572/
• Kaufman, L.; Rousseeuw, P.J. (1990). Finding Groups in Data: An Introduction to Cluster Analysis (1 ed.). New York: John Wiley. ISBN 0-471-87876-6.
• http://nlp.stanford.edu/IR-book/html/htmledition/time-complexity-of-hac-1.html

Если у Вас возникли дополнительные вопросы или необходима консультация по применению алгоритмов на Вашем проекте, пишите нам на hello@wave-access.com - и наши эксперты помогут разобраться и посоветуют решение.