The k-Means clustering algorithm generates a specified number of disjoint clusters. This method gives the best results for spherical clusters (with shapes approximating a sphere or ellipse). Clusters are convex shapes, which means that a line segment connecting two elements of the same cluster is always inside this cluster.
The method requires numerical data because the algorithm has to calculate distances between points (distance is calculated using the Euclidean metric).
The classic k-Means algorithm is non-deterministic, because the initial locations of the cluster centroids are chosen randomly. It is an iterative method as the approximations of the final results are obtained in successive iterations of the algorithm.
The algorithm starts by randomly selecting the initial locations of cluster centroids. The number of clusters is set by the user. In the next step, the distances to each cluster (centroid) are calculated for each point and the cluster membership matrix is generated. Columns correspond to clusters and rows to observations in the data set. This matrix has the following properties:
The sum of all elements in each row is equal to 1.
This is because every observation has to belong to exactly one cluster. If the distance between an observation and a cluster centroid is minimal then the corresponding entry in the membership matrix is equal to 1, in any other case this value is 0. If the distance from an observation to cluster centroid is equal for two or more nearest clusters, it will be assigned to the first cluster from the group.
The sum of all elements in each column is greater than or equal to 0.
In practice, this implies that some clusters may have no members. AdvancedMiner allows this situation because the user can specify more clusters than there actually are in the data.
In the next step the centroids of new clusters are computed, so that the new centroid is closer to all the members of the cluster than the previous one.
The number of cluster members may change in each iteration, bacause each time a new membership matrix is calculated.
The algorithm stops when the cluster membership matrix does not change anymore.
AdvancedMiner allows the user the set the required number of iterations. In this situation the algorithm will stop only when this number of iterations is performed, regardless of whether the membership matrix changes or not.