Метод Cluster (рис. 7) — высокоуровневая процедура, которая вызывает все вспомогательные методы, выполняющие реальную работу по кластеризации данных.
Рис. 7. Метод Cluster
1. static int [] Cluster(double [][] rawData, int numClusters,
2. int numAttributes, int maxCount)
3. {
4. bool changed = true;
5. int ct = 0;
6. int numTuples = rawData.Length;
7. int [] clustering = InitClustering(numTuples, numClusters, 0);
8. double [][] means = Allocate(numClusters, numAttributes);
9. double [][] centroids = Allocate(numClusters, numAttributes);
10. UpdateMeans(rawData, clustering, means);
11. UpdateCentroids(rawData, clustering, means, centroids);
12. while (changed == true && ct < maxCount)
13. {
14. ++ct;
15. changed = Assign(rawData, clustering, centroids);
16. UpdateMeans(rawData, clustering, means);
17. UpdateCentroids(rawData, clustering, means, centroids);
18. }
19. return clustering;
20. }
Основной цикл while повторно назначает каждую последовательность данных кластеру, вычисляет новую последовательность усредненных значений для каждого кластера, а затем использует ее для вычисления новых значений центра масс для каждого кластера. Цикл прекращается, когда не происходит изменений в назначениях кластеров или когда достигается максимальное количество итераций. Поскольку массив means применяется только для вычисления центров масс, вы, возможно, захотите провести рефакторинг Cluster, поместив вызов UpdateMeans внутрь метода UpdateCentroids.
Перед запуском цикла обработки метод InitClustering инициализирует массив clustering:
1. static int [] InitClustering(int numTuples,
2. int numClusters, int randomSeed)
3. {
4. Random random = new Random(randomSeed);
5. int [] clustering = new int [numTuples];
6. for (int i = 0; i < numClusters; ++i)
7. clustering[i] = i;
8. for (int i = numClusters; i < clustering.Length; ++i)
9. clustering[i] = random.Next(0, numClusters);
10. return clustering;
11. }
Метод InitClustering сначала назначает последовательности от 0 до numClusters–1 кластерам от 0 до numClusters–1 соответственно, благодаря чему изначально в каждом кластере будет минимум одна последовательность. Остальные последовательности назначаются случайно выбранным кластерам.
Несколько удивляет, какой огромный объем исследований был проделан в отношении инициализации кластеризации k-средних, и вы, возможно, захотите поэкспериментировать с подходами, альтернативными представленным здесь. Во многих случаях результат, вызываемый алгоритмом k-средних, зависит от того, как была инициализирована кластеризация.
