Algorithm K-means

The most widely known algorithm for partitioning is the k means algorithm (Hartigan 1975). It uses pairwise distances between the objects, and requires the input of the desired number k of clusters. Internally, the k-means algorithm uses the so-called centroids (means) representing the center of each cluster. For example, a centroid c, of a cluster j = 1,..., k can be defined as the arithmetic mean vector of all objects of the corresponding cluster, i.e.,... 

This index is employed by both the k-means (MacQueen, 1967) and the isodata algorithms (Ball and Hall, 1965), which partition a set of data into k clusters. With the k-means algorithm, the number of clusters are prespecified, while the isodata algorithm uses various heuristics to identify an unconstrained number of clusters. 

The hidden layer parameters to be determined are the parameters of hyperellipsoids that partition the input data into discrete clusters or regions. The parameters locate the centers (i.e., the means) of each ellipsoid region s basis function and describe the extent or spread of the region (i.e., the variance or standard deviations). There are many ways of doing this. One is to use random samples of the input data as the cluster centers and add or subtract clusters as needed to best represent the data. Perhaps the most common method is called the K-means algorithm (Kohonen, 1997 Linde et al 1980) ... 

K-means algorithm An iterative technique for automatic clustering. The first step in a Kohonen selfOorganizing map algorithm. 

Kohonen self-organizing map An unsupervised learning method of clustering, based on the k-means algorithm, similar to the first stage of radial basis function networks. Self-organized maps are used for classification and clustering. 

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 ... 

The objective function values of K-means algorithm with 50 iterative cycles are listed in Table 2, the lowest value is 168.7852. One notices that the behavior of K-means algorithm is influenced by the choice of initial cluster centers, the order in which the samples were taken, and, of course, the geometrical properties of the data. The tendency of sinking into local optima is obvious. Clustering by SA can provide more stable computational results. 

CLUSTER ANALYSIS BY K-MEANS ALGORITHM AND SIMULATED ANNEALING... 

The simulated data sets were composed of 30 samples (data set I) and 60 samples (data set II) containing 2 variables ( x, y ) for each (see Figure 3 and Figure 4, respectively ). These samples were supposed to be divided into 3 classes. The data were processed by using cluster analysis based on simulated annealing (SAC) and cluster analysis by K-means algorithm and simulated annealing(SAKMC), respectively. As shown in Table 5, the computation time... 

Cultivated calculus bovis samples No.4 and No.7 were misclassified into natural ones by K-means algorithm. Both SAC and SAKMC can get a global optimal solution 0. = 94.3589 ), only sample No. -4 belonging to cultivated calculus bovis was classified into a natural one corresponding to j, = 94.3589. If sample No. 4 is classified into a cultivated one, the corresponding objective function 0 would be 95.2626, this indicates that iiample No.4 is closer to natural calculus bovis. From the above results, one notices that calculus bovis samples can be correctly classified into natural and cultivated ones on the basis of their microelement contents by means of SAC and SAKMC except the sample No. 4. The computation times for SAC and SAKMC were 21 and 12 minutes, respectively. 

Figure 12 The K-means algorithm applied to the test data from Table 7(a), showing the initial four partitions (a) and subsequent steps, (b) to (d), until a stable result is achieved (e)...

Figure 15 Clustering resulting from application of two commercial programs of the K-means algorithm (a) and (b). to the data from Table 9...

A hybrid method, bisecting K-means, combines the divisive hierarchical and K-means methods to produce a controlled number of hierarchical document clusters. It has been shown to perform as good as or better than hierarchical methods while retaining the performance of the K-means approach [32]. The process of this method involves bisecting a selected cluster of documents (biggest or poorest quality) into two smaller clusters but optimizing the centroids to obtain new clusters with the best possible quality. An example of an implementation of this type of method is the Oracle Text hierarchical K-means algorithm. 

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... 

Figure 4.13 K-means algorithm applied to the test data from Table 4.7(a), showing the...

---