Means Algorithm

One of the most popular and widely used clustering techniques is the application of the. -Means algorithm. It is available with all popular cluster analysis software packages and can be applied to relatively large sets of data. The objective of the method is to partition the m objects, characterized by n variables, into K clusters so that the square of ffie within-cluster sum of distances is minimized. Being an optimization-based technique, the number of possible solutions cannot be predicted and the best possible partitioning of the objects may not be achieved. In practice, the method finds a local optimum, defined as being a classification in which no movement of an observation from one cluster to another will reduce the within-cluster sum of squares. 

Many versions of the algorithm exist, but in most cases the user is expected to supply the number of clusters, K, expected. The algorithm described here is that proposed by Hartigan.  

The data matrix is defined by X with elements (1 i m, where m is the number of objects and n is the number of variables used to characterize the objects. The cluster analysis seeks to find K partitions or clusters, with each object residing in only one of the clusters. 

The mean value for each variable j, for all objects in cluster L is denoted by Bl,p L K). The number of objects residing in cluster L is Rl-The distance, between the I th object and the centre or average of each cluster is given by the Euclidean metric. 

The algorithm proceeds by moving an object from one cluster to another in order to reduce e, and ends when no movement can reduce e. The steps involved are  

---

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 A -means algorithm, the number of clusters are prespecified, while the isodata algorithm uses various heuristics to identify an unconstrained number of clusters. 

There are numerous definitions of combinatorial optimization. We will use this definition Combinatorial optimization means algorithms which generate quants and assign them to resources such that the costs summarized over all quants are minimized and all constraints are met. ... 

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

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. 

The number k of clusters being inherent in the data set is usually unknown, but it is needed as an input of the fc-means algorithm. Since the algorithm is very fast, it can be run for a range of different numbers of clusters, and the best result can be selected. Here, best refers to an evaluation of the results by cluster validity measures (see Section 6.7). 

FIGURE 6.8 Results of the 1-means algorithm for varying number of clusters, 1, for an artificial data set consisting of three spherical groups. The different symbols correspond to the cluster results. 

Methods to Calculate Consensus Value - Robust mean - Algorithm A... 

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

Ischemia in the forearm was studied by Mansfield et al. in 1997 [38], In this study, the workers used fuzzy C means clustering and principal component analysis (PCA) of time series from the NIR imaging of volunteers forearms. They attempted predictions of blood depletion and increase without a priori values for calibration. For those with a mathematical bent, this paper does a very nice job describing the theory behind the PCA and fuzzy C means algorithms. 

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. 

---