Вычисление центров масс кластеров
Вспомните, что центр масс (центроид) кластера — это последовательность, наиболее репрезентативная среди остальных последовательностей, назначенных кластеру, и один из способов определить центр масс кластера — вычисление средней последовательности с поиском последовательности, ближайшей к средней. Среднюю последовательность в каждом кластере вычисляет вспомогательный метод 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: первый индекс представляет идентификатор кластера, а второй — указывает атрибут данных.
Итак, в каждом кластере есть центр масс (центроид), которым является наиболее репрезентативная в кластере последовательность. Значения центра масс вычисляются нахождением одной последовательности в каждом кластере, ближайшей к усредненной в том же кластере. Каждая последовательность данных назначается кластеру, центр масс которого ближе всего к этой последовательности.