Блог

Полезные статьи и новости о жизни WaveAccess

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

Иерархическая кластеризация – метод кластерного анализа, который предназначен для построения иерархического дерева кластеров. Подходы к иерархической кластеризации, как правило, сводятся к двум типам:

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

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

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

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

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

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

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

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

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

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

В приведенном ниже примере мы использовали схожий подход в улучшении асимптотики алгоритма, но снизили количество потребляемой памяти до O(N2 * (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(N2) памяти. Для оптимизации достаточно добавить к дереву отрезков персистетнтность. Это уменьшит потребляемую память до 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

DC

MIA

CHI

SEA

SF

LA

DEN

BOS

0

 

 

 

 

 

 

 

 

NY

206

0

 

 

 

 

 

 

 

DC

429

233

0

 

 

 

 

 

 

MIA

1504

1308

1075

0

 

 

 

 

 

CHI

963

802

671

1329

0

 

 

 

 

SEA

2976

2815

2684

3273

2013

0

 

 

 

SF

3095

2934

2799

3053

2142

808

0

 

 

LA

2979

2786

2631

2687

2054

1131

379

0

 

DEN

1949

1771

1616

2037

996

1307

1235

1059

0

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

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

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

 

BOS/NY

DC

MIA

CHI

SEA

SF

LA

DEN

BOS/NY

0

 

 

 

 

 

 

 

DC

331

0

 

 

 

 

 

 

MIA

1406

1075

0

 

 

 

 

 

CHI

882.5

671

1329

0

 

 

 

 

SEA

2895.5

2684

3273

2013

0

 

 

 

SF

3014.5

2799

3053

2142

808

0

 

 

LA

2882.5

2631

2687

2054

1131

379

0

 

DEN

1860

1616

2037

996

1307

1235

1059

0

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

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

 

BOS/NY/DC

MIA

CHI

SEA

SF

LA

DEN

BOS/NY/DC

0

 

 

 

 

 

 

MIA

1240.5

0

 

 

 

 

 

CHI

776.75

1329

0

 

 

 

 

SEA

2789.75

3273

2013

0

 

 

 

SF

2906.75

3053

2142

808

0

 

 

LA

2756.75

2687

2054

1131

379

0

 

DEN

1738

2037

996

1307

1235

1059

0

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

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

 

BOS/NY/DC

MIA

CHI

SEA

SF/LA

DEN

BOS/NY/DC

0

 

 

 

 

 

MIA

1240.5

0

 

 

 

 

CHI

776.75

1329

0

 

 

 

SEA

2789.75

3273

2013

0

 

 

SF/LA

2831.75

2870

2098

969.5

0

 

DEN

1738

2037

996

1307

1147

0

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

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

 

BOS/NY/DC/CHI

MIA

SEA

SF/LA

DEN

BOS/NY/DC/CHI

0

 

 

 

 

MIA

1284.75

0

 

 

 

SEA

2401.375

3273

0

 

 

SF/LA

2464.875

2687

808

0

 

DEN

1367

2037

1307

1147

0

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

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

 

BOS/NY/DC/CHI

MIA

SF/LA/SEA

DEN

BOS/NY/DC/CHI

0

 

 

 

MIA

1284.75

0

 

 

SF/LA/SEA

2433.125

2980

0

 

DEN

1367

2037

1227

0

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

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

 

BOS/NY/DC/CHI

MIA

SF/LA/SEA/DEN

BOS/NY/DC/CHI

0

 

 

MIA

1284.75

0

 

SF/LA/SEA/DEN

1900.063

2508.5

0

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

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

 

BOS/NY/DC/CHI/MIA

SF/LA/SEA/DEN

BOS/NY/DC/CHI/MIA

0

 

SF/LA/SEA/DEN

1896.625

0

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

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

  • Оригинальный алгоритм иерархической кластеризации
  • Модификации алгоритма, снижающие сложность с O(N3) до O(N2  log N)
  • Модификации, позволяющие снизить потребляемую память с O(N3) до O(N2  log N) с сохранением сложности O(N2  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 - и наши эксперты помогут разобраться и посоветуют решение.

Заказать звонок

Удобное время:

Отменить

Пишите!

Присоединить
Файл не больше 30 Мб.
Отменить