Centroid clustering

Compute new cluster centroids and go to step (3). One continues to do this until convergence occurs (i.e., until the same clustering is found in two successive assignment steps). 

The objective function (Equation 6.7) also makes clear that not all pairwise distances are needed by the algorithm, but only the distances of the objects to all cluster centroids. For minimizing this objective function, several algorithms have been proposed. The most widely used algorithm for fc-means works as follows ... 

Select a number k of desired clusters and initialize k cluster centroids c , for example, by randomly selecting k different objects. 

Assign each object to the cluster with the closest centroid, i.e., compute for each object the distance 11 x, - Cj for j = 1,..., k and assign x, to the cluster where the minimum distance to the cluster centroid appears. 

Recompute the cluster centroids using Equation 6.6 for the new object assignments. 

The algorithm usually always converges however, it does not necessarily find the global minimum of the objective function (Equation 6.7). The outcome of the /t-means algorithm also depends on the initialization of the cluster centroids in step 1. As a possible solution, the algorithm can be run several times to reduce this drawback. 

Instead of using the Euclidean distance, also other distance measures can be considered. Moreover, another power than 2 could be used for the membership coefficients, which will change the characteristics of the procedure (degree of fuzzification). Similar to fc-means, the number of clusters k has to be provided as an input, and the algorithm also uses cluster centroids Cj which are now computed by... 

So, the cluster centroids are weighted averages of all observations, with weights based on the membership coefficients of all observations to the corresponding cluster. When using only memberships of 0 and 1, this algorithm reduces to /.--means. 

The term proximity is used here to include similarity and dissimilarity coefficients in addition to distance measures. Individual proximity measures are not defined in this review full definitions can be found in standard texts and in the articles by Barnard, Downs, and Willett.We now define the terms centroid and square-error, because they will be used throughout this chapter. For a cluster of s compounds each represented by a vector, let x(r) be the rth vector. The vector of the cluster centroid, x(c), is then defined as... 

The best-known relocation method is the k-means method, for which there exist many variants and different algorithms for its implementation. The k-means algorithm minimizes the sum of the squared Euclidean distances between each item in a cluster and the cluster centroid. The basic method used most frequently in chemical applications proceeds as follows ... 

Assign each compound to its nearest cluster centroid (classification step). 

Recalculate each cluster centroid (minimization step). 

The iterative adjustment of weight vectors is similar to the iterative refinement of k-means clustering to derive cluster centroids. The main difference is that adjustment affects neighboring weight vectors at the same time. Kohonen mapping requires O(Nmn) time and 0(N) space, where m is the number of cycles and n the number of neurons. 

Se and dee denote the centroid intracluster and intercluster distances, respectively. The intracluster distance for a given cluster is the average of all pairwise distances from points in the cluster to the cluster centroid. The intercluster distance between two clusters is computed as the distance between their centroids. M is the number of genes belonging to cluster k, given that a total of Nc clusters are found to exist in the data. A low value of DBI indicates good cluster structure. 

Document vectors are used for calculating a similarity (or distance) metric between two documents or a document and a cluster centroid (a vector representing the center of a cluster of documents). Similarly, centroid vectors can be used to... 

This simple example can be expanded by requesting 10 clusters from the k-Means algorithm. Because the algorithm is hierarchical in nature, the initial split of the root cluster is identical to the 2-cluster example. Further splitting steps are performed until 10 clusters are obtained while maximizing the relative cluster centroid distances and intercluster quality. Figure 6.13 shows the hierarchy of the final... 

Note A. Cluster attributes for a two-cluster example. Cluster Quality is the average percent similarity of a document in the cluster from the cluster centroid. Cluster tokens are the individual words/terms that statistically distinguish each cluster. The most significant terms are listed first. A non-expert cannot easily define a more general theme of each cluster. B. Cluster themes and gist better defines the biological content of the clustered documents. It becomes clear that cluster 1 is related to Alzheimer s disease while cluster 2 contains Lymphoma documents. 

---