Вычисление центров масс кластеров

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

Рис. 4. Метод UpdateMeans

1. static void UpdateMeans(double [][] rawData, int [] clustering,

2. double [][] means)

3. {

4. int numClusters = means.Length;

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

6. for (int j = 0; j < means[k].Length; ++j)

7. means[k][j] = 0.0;

8. int [] clusterCounts = new int [numClusters];

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

10. {

11. int cluster = clustering[i];

12. ++clusterCounts[cluster];

13. for (int j = 0; j < rawData[i].Length; ++j)

14. means[cluster][j] += rawData[i][j];

15. }

16. for (int k = 0; k < means.Length; ++k)

17. for (int j = 0; j < means[k].Length; ++j)

18. means[k][j] /= clusterCounts[k]; // опасность

19. return;

20. }

Метод UpdateMeans предполагает, что массив массивов с именем means уже существует, а вовсе не создает его и не возвращает. Так как предполагается, что массив means имеется, вы, вероятно, предпочтете сделать его параметром, передаваемым по ссылке (ref parameter). Массив means создается вспомогательным методом Allocate:

1. static double [][] Allocate(int numClusters, int numAttributes)

2. {

3. double [][] result = new double [numClusters][];

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

5. result[k] = new double [numAttributes];

6. return result;

7. }

Первый индекс массива means представляет идентификатор кластера, а второй — указывает атрибут. Например, если means[0][1] = 150.33, то среднее значение веса (1) в последовательности в кластере 0 составляет 150.33.

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

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

Рис. 5. Метод ComputeCentroid

1. static double [] ComputeCentroid(double [][] rawData, int [] clustering,

2. int cluster, double [][] means)

3. {

4. int numAttributes = means[0].Length;

5. double [] centroid = new double [numAttributes];

6. double minDist = double. MaxValue;

7. for (int i = 0; i < rawData.Length; ++i) // Перебираем каждую последовательность данных

8. {

9. int c = clustering[i];

10. if (c!= cluster) continue;

11. double currDist = Distance(rawData[i], means[cluster]);

12. if (currDist < minDist)

13. {

14. minDist = currDist;

15. for (int j = 0; j < centroid.Length; ++j)

16. centroid[j] = rawData[i][j];

17. }

18. }

19. return centroid;

20. }

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

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

1. static void UpdateCentroids(double [][] rawData, int [] clustering,

2. double [][] means, double [][] centroids)

3. {

4. for (int k = 0; k < centroids.Length; ++k)

5. {

6. double [] centroid = ComputeCentroid(rawData, clustering, k, means);

7. centroids[k] = centroid;

8. }

9. }

Метод UpdateCentroids предполагает, что массив массивов с именем centroids уже существует. Массив centroids очень похож на массив means: первый индекс представляет идентификатор кластера, а второй — указывает атрибут данных.

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