| | | 1 | | using System; |
| | | 2 | | using System.Collections.Generic; |
| | | 3 | | using System.Linq; |
| | | 4 | | using UnityEngine; |
| | | 5 | | |
| | | 6 | | // The k-means clusterer class performs k-means clustering. |
| | | 7 | | public class KMeansClusterer : ClustererBase { |
| | | 8 | | // Default maximum number of iterations. |
| | | 9 | | protected const int _defaultMaxNumIterations = 20; |
| | | 10 | | |
| | | 11 | | // Convergence threshold. |
| | | 12 | | protected const float _epsilon = 1e-3f; |
| | | 13 | | |
| | | 14 | | // Number of clusters. |
| | | 15 | | private readonly int _k; |
| | | 16 | | |
| | | 17 | | // Maximum number of iterations. |
| | | 18 | | private readonly int _maxNumIterations; |
| | | 19 | | |
| | 39 | 20 | | public KMeansClusterer(int k) : this(k, _defaultMaxNumIterations) {} |
| | 26 | 21 | | public KMeansClusterer(int k, int maxNumIterations) { |
| | 13 | 22 | | _k = k; |
| | 13 | 23 | | _maxNumIterations = maxNumIterations; |
| | 13 | 24 | | } |
| | | 25 | | |
| | | 26 | | // Generate the clusters from the list of hierarchical objects. |
| | 13 | 27 | | public override List<Cluster> Cluster(IEnumerable<IHierarchical> hierarchicals) { |
| | 15 | 28 | | if (hierarchicals == null || !hierarchicals.Any()) { |
| | 2 | 29 | | return new List<Cluster>(); |
| | | 30 | | } |
| | 11 | 31 | | if (_k <= 0) { |
| | 0 | 32 | | throw new ArgumentOutOfRangeException( |
| | | 33 | | paramName: "k", actualValue: _k, message: "Number of clusters must be positive."); |
| | | 34 | | } |
| | | 35 | | |
| | | 36 | | // Initialize the clusters with centroids located at the positions of k random hierarchical |
| | | 37 | | // objects. Perform Fisher-Yates shuffling to find k random hierarchical objects. |
| | 11 | 38 | | List<IHierarchical> hierarchicalsList = hierarchicals.ToList(); |
| | | 39 | | |
| | | 40 | | // Validate that k is not greater than the number of hierarchical objects. |
| | 12 | 41 | | if (_k > hierarchicalsList.Count) { |
| | 1 | 42 | | throw new InvalidOperationException( |
| | | 43 | | $"Cannot create {_k} clusters from {hierarchicalsList.Count} hierarchical objects."); |
| | | 44 | | } |
| | | 45 | | |
| | 10 | 46 | | var clusters = new List<Cluster>(); |
| | 83 | 47 | | for (int i = 0; i < _k; ++i) { |
| | 21 | 48 | | int j = UnityEngine.Random.Range(i, hierarchicalsList.Count); |
| | 21 | 49 | | (hierarchicalsList[i], hierarchicalsList[j]) = (hierarchicalsList[j], hierarchicalsList[i]); |
| | | 50 | | |
| | 21 | 51 | | clusters.Add(new Cluster { Centroid = hierarchicalsList[i].Position }); |
| | 21 | 52 | | } |
| | | 53 | | |
| | 10 | 54 | | bool converged = false; |
| | 10 | 55 | | int numIteration = 0; |
| | 48 | 56 | | while (!converged && numIteration < _maxNumIterations) { |
| | 19 | 57 | | AssignToClusters(clusters, hierarchicals); |
| | | 58 | | |
| | | 59 | | // Calculate the new clusters as the mean of all assigned hierarchical objects. |
| | 19 | 60 | | converged = true; |
| | 149 | 61 | | for (int clusterIndex = 0; clusterIndex < clusters.Count; ++clusterIndex) { |
| | 37 | 62 | | Vector3 oldClusterPosition = clusters[clusterIndex].Centroid; |
| | 37 | 63 | | if (clusters[clusterIndex].IsEmpty) { |
| | 0 | 64 | | int hierarchicalIndex = UnityEngine.Random.Range(0, hierarchicalsList.Count); |
| | 0 | 65 | | clusters[clusterIndex].Centroid = hierarchicalsList[hierarchicalIndex].Position; |
| | 37 | 66 | | } else { |
| | 37 | 67 | | clusters[clusterIndex].Recenter(); |
| | 37 | 68 | | } |
| | | 69 | | |
| | | 70 | | // Check whether the algorithm has converged by checking whether the cluster has moved. |
| | 48 | 71 | | if (Vector3.Distance(oldClusterPosition, clusters[clusterIndex].Position) > _epsilon) { |
| | 11 | 72 | | converged = false; |
| | 11 | 73 | | } |
| | 37 | 74 | | } |
| | 19 | 75 | | ++numIteration; |
| | 19 | 76 | | } |
| | 10 | 77 | | AssignToClusters(clusters, hierarchicals); |
| | 10 | 78 | | return clusters; |
| | 12 | 79 | | } |
| | | 80 | | |
| | | 81 | | private static void AssignToClusters(IReadOnlyList<Cluster> clusters, |
| | 29 | 82 | | IEnumerable<IHierarchical> hierarchicals) { |
| | | 83 | | // Clear all clusters. |
| | 261 | 84 | | foreach (var cluster in clusters) { |
| | 58 | 85 | | cluster.ClearSubHierarchicals(); |
| | 58 | 86 | | } |
| | | 87 | | |
| | | 88 | | // Determine the closest centroid to each hierarchical object. |
| | 471 | 89 | | foreach (var hierarchical in hierarchicals) { |
| | 128 | 90 | | float minDistance = Mathf.Infinity; |
| | 128 | 91 | | int minIndex = -1; |
| | 1024 | 92 | | for (int clusterIndex = 0; clusterIndex < clusters.Count; ++clusterIndex) { |
| | 256 | 93 | | float distance = Vector3.Distance(clusters[clusterIndex].Centroid, hierarchical.Position); |
| | 427 | 94 | | if (distance < minDistance) { |
| | 171 | 95 | | minDistance = distance; |
| | 171 | 96 | | minIndex = clusterIndex; |
| | 171 | 97 | | } |
| | 256 | 98 | | } |
| | 128 | 99 | | clusters[minIndex].AddSubHierarchical(hierarchical); |
| | 128 | 100 | | } |
| | 29 | 101 | | } |
| | | 102 | | } |