A Proposed Modification of K-Means Algorithm

Published Online June 2015 in MECS

Nowadays data have become as an asset for human beings. Almost in every sector data is stored for future utilization. As the data grows in size, the technique to utilize these data becomes more challenging.

This large amount of data is then used for discovering new knowledge. Essentially, data mining (DM) utilizes these large data warehouses to extract the information [1]. Data mining is a technique by which users try to gain knowledge from the stored data. It is frequently used in knowledge discovery system. Additionally data mining is used to design artificially intelligent systems, machine learning process and statistical systems [2] [3].

Clustering is an application of Data mining. Clustering is concerned with grouping together objects that are similar to each other but different from the object that belongs to other clusters [4]. It is a way to classify raw data reasonably so that one can find out the hidden pattern that may exist in the dataset [5]. Clustering is one of the key technologies used in data mining field and also in machine learning sector. It is also utilized in many areas such as knowledge discovery, pattern recognition and classification, data compression and vector quantization. It also plays an important role in the field of biology, geology, geography and marketing [6].

This process is repeated several times unless any object moves to another cluster [7]. This algorithm is very popular for distributing data objects into desired clusters. However the main problem of this algorithm is that it requires a high number of computations and hence takes an extensive time.

There are many improved version of k-means algorithm proposed by the researchers. In the paper [8] [9], researchers proposed to maintain two data structures to save the current minimum distance and current assigned cluster name. This process reduces the computation in a large scale and provided a better performance than the traditional K-means algorithm. But the main problem of this algorithm was that the “current minimum distance” is not always the correct minimum distance.

As mentioned above, the main objective of this paper is to propose modification of the k-means algorithm which will have the same functionality as the traditional k-means algorithm. But it will overcome the problems discussed in the previous section. A more efficient and less computationally expensive algorithm will be proposed in this paper.

In different sections of this paper, the total procedure and the way of advancement of the work along with the related background studies are explained elaborately. Here is the glimpse of the paper

In Background Studies, related previous works are presented in a summarized way. The work related to the improved k-means clustering algorithm, improved initial center theory and better initial cluster concepts are focused here.

In Proposed Algorithm section, the algorithm is proposed. The algorithm and some graphical descriptions are provided here.

The Result Analysis section is focused on result analysis. The outcome of the proposed algorithm is discussed here along with the comparison with other modification of traditional K-means algorithm.

And finally the draw backs and future work is described in the conclusion section.

• II.    Related Works

Before starting the proposed algorithm, it is essential to discuss about the related background studies. In this section the related ideas and researches are discussed in brief. A lot of work has been done with the k-means algorithm. Here it will be discussed from the very beginning for a better understanding.

In modern world data is becoming more and more important day by day. Large organizations tend to keep their data safe and store them in such a way that it can be used in the future. As the volume of the data grows, the need to preserve it in a structured way is becomes challenging. In data mining technology, this challenge is handled in a structural way. In this technology data are mined in such a way that useful information can be obtained from this data if needed. In present world data is a continuous by product of every business that can be used for good.

Clustering is a process that organizes a set of objects into disjoint classes. These classes are referred as clusters [9]. It is a version of unsupervised classification and hence does not depend on predefined classes. It tries to partition a data set based on specific features so that within a cluster the objects are more similar than the object in different one [4] [10-11].

K-means algorithm is a partition-based clustering method [12-15].In the traditional k-means algorithm k random points are chosen from the whole dataset as the primary cluster center. Then the distance between each object and each cluster center is calculated. Finally each object is assigned to the nearest cluster. To find the distance Euclidian Formula is used.

So the whole algorithm can be described as below [16]: Input: N-objects and number of cluster K

Output: K- Custer each having 0

Arbitrarily select k objects as initial luster centers.

Calculate distance between each object xi and each cluster center.

Assign each object to the nearest cluster. For calculating the distance Euclidian formula is used. The formula is:

d(xl,ml')

Jd

$

(x

-m;)²

Where i=1…..N; j=1……..k;

d(xi, mi) is the distance between data i and cluster j.

Calculate the average of every object in each cluster as new cluster center, using the following formula.

m; = — Ey^ X[jWhere i=1,2........k; Ni is the number of object in current cluster i.

Repeat until convergence criterion is met.

In traditional K-Means algorithm a lot of calculations are needed as this a brute force algorithm. As a result we have to compute the distance of each object from its cluster center whether or not it moves in or out from the cluster. Even for the closest object from one cluster center needs to be make sure that it is not close to any other cluster center. That results in a large number of calculations.