Variations of k-mean Algorithm: A Study for High-Dimensional Large Data Sets

INTRODUCTION

The clustering problem is a classical problem in the database, knowledge discovery, artificial intelligence and theoretical literature is used to find similar groups of records in very large database. The clustering algoritlnns are used for similarity search, customer segmentation, pattern recognition, trend analysis and classification. Basically clustering problem is to find a partition of the points into clusters so that the points within each cluster are similar to one another for a given set of points in multidimensional space. Similarity can be determined using various distance fnnctions (Han and Kamber, 2001). Clustering techniques are basically classified in so many categories such as partitioning Techniques, Hierarchical Techniques, Density based Techniques etc. (Pujari, 1999).

In the past three decades, cluster analysis has been extensively used to many areas such as medicine for classification of diseases, chemistry for grouping of components, social studies for classification of statistical findings, and so on. Its main aim is to discover structures or clusters present in the data. While there is no rmiversal definition of a cluster, algoritlnns have been developed to find several kinds of clusters: spherical, linear, drawn out, etc. redefining clustering problem in a diverse way for liigli dirnensioml applications (Aggarwal and Yu, 2002) facilitates fast computations.Among all the open variations of k-mean clustering algoritlnn, k-means, k-medoid and h-k-mean clustering algoritlnn are chosen for our study. Unlike many other partitioning methods, k-means andk-medoid (Kaufmann and Rousseeuw, 1990) are the most basic methods for clustering and h-k-mean (Garg et al., 2004) is heuristic based hybrid model of these two algoritlnn.

The study introduces clustering algoritlnns based on partition and variations of k-means algoritlnn i.e., k– mean, k-medoid (PAM) and h-k-mean, presents experimental results comparing the performance of k-means, k-medoid and h-k-mean clustering algoritlnns on a criterion evolved and finally explains conclusion and future scope in this field.

CLUSTERING ALGORITHMS BASED ON PARTITIONING

Basic concept of Partition based clustering method is to Construct a partition of a database D of n objects into a set of k clusters and minimizing an objective frmction. Exhaustively enumerate all possible partitions into k sets m order to find the global minimum is too expensive. following heuristic is used

The most well-knownl and commonly used partitioning methods are k-means, k-medoid and their variants.

k-means: The algorithm first select k of the objects, each of which mainly represents a cluster mean or center. Each of the remaining object is assigned to the cluster to which it is the most similar, based on the distance between the object and the cluster mean. It then recomputes the new mean for each cluster.

Fig. I:	Algorithm k-mean

This process iterates nntil the criterion fnnction converges. Typically the squared-error criterion is used, defined as

k-mean (Kuafmm and Rousseeuw, 1990) algorithm is described in Fig. 1.

k-medoid: There are two well-knownll k-medoid methods, PAM and CLARA. PAM (Partitioning Around Medoids) (Kaufman and Rousseeuw. 1990) .To find k clusters. PAM's approach is to determine a representative object for each cluster. This representative object, called a medoid is meant to be the most centrally located object for each cluster. Once the medoids have been selected, each non-selected objects is grouped with the medoid to which it is the most similar. More precisely, if O_j is a non-selected object, and O_i is a (selected) medoid, i. O_j belongs to the cluster represented by O_i if d(O_j, O_i) min o_ed(O_j , O_i), where the notation min o_edenotes the minimum over all medoids O_e, and the notation d(O_a, O_b) denotes the dissimilarity or distance between objects O_aand O_b. All the dissimilarity values are given as inputs to PAM. Finally, the quality of the chosenmedoids is measured by the average dissimilarity between an object and the medoid of its cluster. Figure 2 illustrates k-medoid (Kuafmann and Rousseeuw. 1990) algorithm.

To find the kmedoids. PAM begins with an arbitrary selection of k objects. Then in each step, a swap between a selected object O_i and a non-selected object O_h is made, as long as such a swap would result in an improvement of the quality of the clustering. In particular, to calculate the effect of such a swap between 0_i and O_h, PAM computes costs C_ih for all non-selected objects O_j. depending on which of the following cases O_j is in, C_jih is defined by one of the equation below.

First case: O_j cmently belongs to the cluster represented by 0_i. Furthermore, let O_j be more similar to O_j,2 than O_h, i.e., d (O_j, O_h)>=d(O_j, O_j.2) where O_j.2 is the second most similar medoid to O_j. Thus, is O_i is replaced by O_h as a medoid, O_j would belong to the cluster represented by O_j.2 hence, the cost of the swap as far as q is concerned is:

(1)

This equation always gives a non-negative C_jih indicating that there is a non-negative cost incmed in replacing O_i with O_h.

Fig. 2:	Algorithm k-medoid (PAM)

Second case: O_j cmently belongs to the cluster represented by 0_i. But this time, O_j is less similar to O_j.2 than . i.e.d(O_j,O_h)<d(O_j,O_j.2) Then, if O_i is replaced by O_h, O_j would belong to the cluster represented by O_h. Thus, the cost for O_j is given by:

(2)

Unlike in Eq. 1, C_jih here can be positive or negative, depending on whether O_j is more similar to O_i or to O_h.

Third case: suppose that O_j cmently belongs to a cluster other than the one represented by O_i. Let O_j.2 be the representative object of that cluster. Furthermore let O_j be more similar to O_j.2 than O_h. Then even if O_i is replaced by O_h, O_j would stay in the cluster represented by O_j.2 Thus, the cost is:

(3)

Fourth case: O_j currently belongs to a cluster represented by O_j.2 . But O_j is less similar to O_j.2 than O_h. Then replacing O_i with O_h would cause O_h to jump to the cluster of Oh from that of O_j.2 . Thus the cost is:

(4)

and is always negative. Combining the four cases above, the total cost for replacing O_i with O_h is given by:

(5)

h-k-mean: A hybrid approach of k-mean and k-medoid algoritlnn is h-k-mean algorithm which can deal with presence of noise and outliers efficiently. Heuristic followed by h-k-mean algorithm (Garg et oZ.,2004) is as under:

Running time for this algorithm is a little mre than nmning time of k-mean algorithm. This algorithm selects reference point which is most centrally located after considering removal of a possible outlier unlike a random reference point in k-medoid algorithm. k-mean algorithm is more robust than both the algorithms i.e., k-mean algorithm and k-medoid algorithm in the presence of noise and outliers because farthest values are temporarily removed while deciding cluster representing object.