Функция Distance и нормализация данных

Метод ComputeCentroid вызывает метод Distance, чтобы определить, какая последовательность данных ближе всего к центру масс кластера. Как уже описывалось, самый распространенный способ измерить расстояния от последовательностей до средней — использовать евклидову метрику:

1. static double Distance(double[] tuple, double[] vector)

2. {

3. double sumSquaredDiffs = 0.0;

4. for (int j = 0; j < tuple.Length; ++j)

5. sumSquaredDiffs += Math.Pow((tuple[j] - vector[j]), 2);

6. return Math.Sqrt(sumSquaredDiffs);

7. }

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

Другой важный фактор, связанный с выбором функции вычисления метрики в алгоритме кластеризации k-средних, — нормализация данных. Демонстрационная программа использует исходные, ненормализованные данные. Поскольку значения веса в последовательностях — это обычно величины вроде 160.0, а значения роста — на уровне 67.0, разница в значениях веса имеет гораздо большее влияние, чем разница в значениях роста. Во многих ситуациях, исходные данные полезно нормализовать перед кластеризацией. Сделать это можно разными методами. Распространенный способ — вычисление среднего (m) и стандартного отклонения (standard deviation, sd) для каждого атрибута, а затем вычисление для значения каждого атрибута (v) нормализованного значения nv = (v–m)/sd.

Назначение каждой последовательности кластеру

Располагая методом вычисления центроида каждого кластера, можно написать метод для назначения каждой последовательности кластеру. Метод Assign представлен на рис. 6.

Рис. 6. Метод Assign

1. static bool Assign(double[][] rawData,

2. int[] clustering, double[][] centroids)

3. {

4. int numClusters = centroids.Length;

5. bool changed = false;

6. double[] distances = new double[numClusters];

7. for (int i = 0; i < rawData.Length; ++i)

8. {

9. for (int k = 0; k < numClusters; ++k)

10. distances[k] = Distance(rawData[i], centroids[k]);

11. int newCluster = MinIndex(distances);

12. if (newCluster != clustering[i])

13. {

14. changed = true;

15. clustering[i] = newCluster;

16. }

17. }

18. return changed;

19. }

Метод Assign принимает массив centroids и перебирает каждую последовательность данных. Для каждой из последовательностей вычисляется расстояние до каждого центроида кластера и сохраняется локальный массив с именем distances, индекс которого представляет идентификатор кластера. Затем вспомогательный метод MinIndex определяет индекс в массиве distances, где хранится наименьшее значение метрики, и это соответствует кластеру, центр масс которого находится ближе всего к данной последовательности.

Вот как выглядит вспомогательный метод MinIndex:

1. static int MinIndex(double[] distances)

2. {

3. int indexOfMin = 0;

4. double smallDist = distances[0];

5. for (int k = 0; k < distances.Length; ++k)

6. {

7. if (distances[k] < smallDist)

8. {

9. smallDist = distances[k]; indexOfMin = k;

10. }

11. }

12. return indexOfMin;

13. }

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

Эта реализация алгоритма k-средних предполагает, что каждому кластеру всегда назначена хотя бы одна последовательность данных. Как видно на рис. 6, метод Assign не предотвращает ситуации, где кластеру вообще не назначается ни одной последовательности. На практике это обычно не проблема. Предотвратить ошибочную ситуацию не так-то просто. Подход, который я обычно применяю, заключается в создании массива centroidIndexes, работающий в сочетании с массивом centroids. Вспомните, что массив centroids содержит значения центров масс, например (61.0, 120.0) — это центр масс для кластера 2 на рис. 2. Массив centroidIndexes хранит сопоставленный индекс последовательности, скажем [3]. Затем в методе Assign мы первым делом назначаем каждому кластеру последовательность данных, которая содержит значения центра масс, и только после этого метод перебирает остальные последовательности и назначает их кластерам. Такой подход гарантирует, что в каждом кластере будет минимум одна последовательность.