# Analysis of SimpleK-Mean and Parallel K-Mean Clustering for Software Products and Organizational Performance Using Education Sector Dataset

Authors: Rui Shang; Balqees Ara; Islam Zada; Shah Nazir; Zaid Ullah; Shafi Ullah Khan
Journal: Scientific Programming
 (2021)

---

## Abstract

Context. Educational Data Mining (EDM) is a new and emerging research area. Data mining techniques are used in the educational field in order to extract useful information on employee or student progress behaviors. Recent increase in the availability of learning data has given importance and momentum to educational data mining to better understand and optimize the learning process and the environments in which it takes place. Objective. Data are the most valuable commodity for any organization. It is very difficult to extract useful information from such a large and massive collection of data. Data mining techniques are used to forecast and evaluate academic performance of students based on their academic record and participation in the forum. Although several studies have been carried out to evaluate the academic performance of students worldwide, there is a lack of appropriate studies to assess factors that can boost the academic performance of students. Methodology. The current study sought to weigh up factors that contribute to improving student academic performance in Pakistan. In this paper, both the simple and parallel clustering techniques are implemented and analyzed to point out their best features. The Parallel K-Mean algorithms overcome the problems of simple algorithm and the outcomes of the parallel algorithms are always the same, which improves the cluster quality, number of iterations, and elapsed time. Results. Both the algorithms are tested and compared with each other for a dataset of 10,000 and 5000 integer data items. The datasets are evaluated 10 times for minimum elapse time-varying K value from 1 to 10. The proposed study is more useful for scientific research data sorting. Scientific research data statistics are more accurate.


---

## Body

## 1. Introduction

We are living in a world of data. Every day, people come across a large amount of data and store these data for further exploration or analysis. Such large datasets are growing rapidly so that it is a very challenging task to extract and mine important information, using conventional techniques [1]. Data are the collection of any facts, figures, and numbers that can be processed in order by a computer system. Nowadays, business organizations are accumulating grooving and huge volumes of data in different setups, formats, and databases. These include [2] transactional data also called operational data, i.e., cost, sales, accounting, payroll, and inventory, and nonoperational data, i.e., forecasting of data, industry sales and macroeconomic data, and metadata, such as data dictionary definitions or logical database design. Different efficient and effective data mining methods are used to mine useful and important information from bulky datasets. Clustering and classification are the most popular techniques of data mining for retrieving data from large datasets; classification is known as supervised learning phenomena while that of clustering is the unsupervised learning phenomena.Classification is also called supervised learning technique [3]. In order to understand a new phenomenon or to learn about a new object, people always try to compare it with other phenomena or objects based on similarities or dissimilarities [4]. After this comparison, a decision can be made. This mechanism is a classification technique of data mining [5]. Clustering also called the unsupervised learning method [6] involves grouping of data items into clusters that have high similarity but are dissimilar to data items of other clusters [7, 8]. The clustering method is used in many areas, for instance, computer sciences, engineering, Earth sciences, life and medical sciences, economics, social sciences, etc. Examples of its application are speech recognition [9], image segmentation, color recognition [10], web mining, text mining, and grouping of patients, students, customers and items [11]. The partitioning method splits the complete dataset into sub-datasets. The whole dataset given is signified by “n,” whereas “K” signifies the sub-datasets also called clusters. “N” represents the total number of data items in a dataset, whereas “k” is the sub-datasets (clusters); then, the whole dataset must be greater than the total number of clusters, i.e. (n > k). Data items in a cluster are alike but are different from the items of the other cluster. Partitioning methods are further classified into several different categories, that is, K-medoids clustering, K-Mean clustering, Relocation algorithms, and Probabilistic clustering [12]. In hierarchical clustering, each cluster node contains parent cluster, child clusters, and sibling clusters. It is further classified into bottom-up (agglomerative) and top-down (divisive clustering). The basic drawbacks of the hierarchical clustering method is that once a split or merge decision is executed, it cannot be readjusted [13]. Hierarchical clustering is a technique that integrates similar objects into different groups called clusters [14]. At the end, the numbers of clusters are ascertained, in which each cluster is different from the other cluster, and the data items in a cluster are similar. This research focuses on the two clustering techniques that are Simple and Parallel K-Mean schemes.SimpleK-Mean technique is one of the most popular and simple unsupervised learning approaches. Unsupervised learning techniques use input vectors for making inferences from the datasets without referring to labeled outcomes. Initially, Simple K-Mean selects the centroids randomly for the processing of data; these centroids are the starting points for these clusters and the optimized positions are calculated using the iterative procedure. Simple K-Mean is one of the partitioning methods, which is the simplest clustering technique. Simple K-Mean clustering algorithm partitioned the complete datasets into different subclusters, and the subclusters are represented by “k”. Simple K-Mean algorithm is easy and simple to implement but still has some drawbacks. In Simple way K-Mean, initial centroids (k) are irregularly preferred for each cluster. On each run or execution, Simple K-Mean algorithm produces different clusters. Then, different results are produced because of different initial centroids. In Simple K-Mean clustering algorithm, “k” represents a user-specified parameter. Here, the “k” number of different clusters shall be put in advance. Initial centroids should be carefully selected for K-Mean clustering algorithm. Because of the random selection of initial centroids, the outcome will be different from the previous one on each run. Due to this drawback, clusters vary from one another; also, data items in clusters may vary from one cluster to another. Simple K-Mean algorithm is noise sensitive because the arithmetic mean value can be considerably influenced by noisy data. Median is used to overcome this problem of Simple K-Mean clustering. It is applicable to process numeric type of data and cannot be useful for categorical type of data. If a large dataset is given, then more space is required for clustering. Most critical issues for Simple K-Mean clustering algorithm are the space and processing speed requirements, when dataset is very large. This algorithm uses Client-Server architecture. To solve the problems of processing speed and memory requirement, Simple Parallel K-Mean algorithm is used for huge datasets. In simple parallel K-mean clustering algorithm, the dataset is partitioned addicted to subparts, so less space and processing speed will be required to process subparts of the datasets. Initial centroids random selection is a disadvantage of Simple K-Mean algorithm. Due to initial centroids random selection, the outcomes of the Parallel K-Mean clustering algorithm vary from one run or execution to another. Also, the data items move from one cluster to another, which affects the cluster quality. Just like Simple K-Mean, Parallel K-Mean also iteratively changes in clusters.This paper consists of a total of six sections. The Introduction section discussed different general terminologies of clustering and specifically discussion about K-Mean and Parallel K-Mean clustering algorithms using in this study application of the clustering algorithm, different types of clustering. Section2 presents the existing research about Simple K-Mean and Parallel K-Mean algorithms, and their analysis based on the research. Section 3 discussed the study implementation and evaluation. Section 4 presents results and discussion of the study. Section 5 is dedicated for Conclusion and future.


## 2. Literature Review

J. B. MacQueen was among the pioneers to introduce theK-Means clustering algorithm (Simple) in 1967 [15]. Many researchers then worked on this Simple K-Mean clustering algorithm, and some of the latest research work is discussed here. The procedure is sustained till there is no difference in the clusters. Min-Max distance measure is introduced by Karthikeyani and suguna [16]. The input dataset is normalized first and then within the normalized range (0, 1), and initial centroids are selected on a random basis. Using min-max similarity measure, the distance is calculated. In [3], the whole dataset is partitioned into blocks, called unit blocks (UB), by using the minimum and maximum limits. After the transformation, formulation of the objects in datasets are sorted on the basis of distance and they are also divided into subclusters (k sets). Median value is also calculated for each set of values, the calculated median is measured as initial centroids, and then clusters are designed through using the designing of initial clusters [17, 18]. This technique used sorting algorithms, which have extra time complexity. Centroids of each unit block are calculated to form the simplest view of the dataset. For calculating finalized centroids, the reduced dataset is used. Each data point is moved to its appropriate cluster. Fahim et al. [19] and Shi and Xumin [20] have presented a K-Mean algorithm, and to store the information of all iterations, they use a data structure. Then, in the forthcoming iteration, the stored information is used. The time of computation is saved by their technique; however, a data structure is required. Also, the initial clusters are based on the random selection of initial centroids. Hongyang and Jia [21] have introduced a dynamic K-Mean clustering technique. In the first step at the server side, sub datasets are produced from the given dataset. After the transformation, formulation of the objects in datasets are sorted on the basis of distance and divided into sub clusters (k sets). Median value is also computed for each set of values, the calculated medium is measured as initial centroids, and then clusters are designed using the design of initial clusters [22]. This technique used sorting algorithms, which has extra time complexity. All client systems that are connected to the server receive these sub-datasets with “K” number of clusters, and also initial centroids. Client system calculates clusters and forwards the results to the server. These processes continue still there is no change occurs in the clusters. The “RBFNN” Radial Basis Function, Neural Network structure theory has been discussed, where a K-Means clustering dynamic method is used for the center selection. The experimental results of the study shows that here the approximation of RBFNN has good performance, where dynamic K-Mean clustering technique is used for center selection. Clusters formed by all of the client systems are then sent to the server system. At the server side, all of the clusters (received from all the clients) are compiled. Arithmetic means of each of the compiled clusters are calculated. Newly calculated arithmetic means (centroids) are compared with the previous arithmetic means (centroids). If the values of the new means (centroids) are equal to the previous means (centroids), the process is terminated, otherwise it will be continued.An algorithm is introduced by Jirong et al. [23], in which some sub-datasets are selected randomly from large datasets. Partitioning clustering algorithms are used to get centroids of the cluster to each of the subset. Partition algorithm is used to get the most popular centroids after gathering the center sets. Clustering and classification are the most popular techniques of data mining for retrieving data from large datasets; classification is known as supervised learning phenomena while that of clustering is the unsupervised learning phenomena. Median value is also calculated for each set of values; the calculated medium is measured as initial centroids and then clusters are designed using the designs of initial clusters [22]. This technique used sorting algorithms, which has extra time complexity. They documented that the Simple K-Mean clustering algorithm is explained in [24–26]. From the dataset, “k” initial centroids are selected randomly. Each of the data item is placed in its appropriate cluster by calculating distances between the data items and initial centroids. The procedure is sustained till there is no difference in the clusters. Min-Max distance measure is introduced by Karthikeyani and suguna [16]. The input dataset is normalized first and then within the normalized range (0, 1), initial centroids are selected on a random basis. Using min-max similarity measure, the distance is calculated. Santhi et al. has introduced an algorithm, which is able to check the absence or presence of negative numbers in datasets [27]. If a negative number is identified, it is transformed into positive numbers by applying subtraction operation to the lowest values of the dataset from the rest of the dataset’s numbers. Median value is calculated for each set of values, the calculated medium is measured as initial centroids, and then clusters are designed using the design of the initial clusters [28]. This technique used sorting algorithms, which has extra time complexity. A brief study on K-Mean clustering algorithm is also arranged by Chen and Xu [29], in which they discussed the pros and cons, and also typical requirements of K-Mean clustering procedure. Yujun et al. has introduced an algorithm, in which “split” and “merge” are the two major stages of clustering [30]. In the “split” stage, each cluster is divided into small sub-clusters using K-Mean clustering algorithm on selected datasets, while in the “merge” stage, the average distance worked for merging. Fahim et al. [7] and Shi and Xumin [20] have presented a K-Mean algorithm, to store the information all iterations they use in a data structure. Then, in the forthcoming iteration, the stored information is used. The time of computation is saved by their technique; however, a data structure is required. Also, the initial clusters are based on the random selection of initial centroids. Chawan et al. have introduced an algorithm, which is able to select the initial centroids randomly in the selected datasets [31], in which the clusters are made by a key which is designed by the ratio of maximal intra and minimal intra cluster distance. If the key distance is lesser than the smallest value, then a data point is assigned to the other cluster in the same dataset. It is investigated and observed that the selection centroids affect the meeting time in their commended algorithm.An author also introduces an algorithm, which improves the efficiency ofK-Mean clustering [32], where a dataset is converted into positive values, by subtracting the smallest values from all data items, if a negative value is identified in the dataset. Distance is calculated for data items; from common centroids, origins of a dataset are calculated. Initial centroids are selected in such a way that the first closest object in the dataset to the common centroids is selected as the initial centroid [33]. The objects are removed from the dataset having less correspondence to selected centroids. Chenfei and Zhiyi [15] have introduced a K-Mean clustering algorithm, in which any data item is selected in the dataset and the distance between that selected data point and other data points is calculated. Threshold value is calculated by dividing the entire area of data points into 100 parts. If the distance value matches the threshold value, it is selected as the initial centroid. The process is continued until “k” initial centroids are formed and the data points are assigned to their proper clusters. The process is continued to get final clusters. K-Mean clustering algorithm for mixed numeric and categorical data are introduced by [34]. Raed and Wasem [13] have proposed an algorithm for the selection of initial centroids in the K-Mean clustering method. “K” values are selected randomly in the dataset. Distance between the selected data items and other data items are calculated to check whether the guess of the random selection of initial centroids was valid or not? Data points in the given dataset are sorted according to the calculated distance. Closest data items, based on the threshold value, are selected as subset and arithmetic mean of the subset is calculated as the first accepted initial centroid. In this way, remaining initial centroids are computed. Sanpawat and Alva [2] have introduced the parallelized version of K-Mean clustering algorithm. Master-slave (Client-Server) method is used in the algorithm. Clustering, also called unsupervised learning method, groups data items into clusters that have high similarity but are dissimilar to data items of other clusters. The clustering method is used in many areas, for instance, computer sciences, engineering, Earth sciences, life and medical sciences, economics, social sciences, etc. Examples of its application are speech recognition image segmentation, color recognition, web mining, text mining, and grouping of patients, students, customers, and items.Qing et al. [12] have introduced the Parallel K-Mean clustering algorithm, which is based on the selection of initial centroids. Distance between each of the data item is calculated. Data items having the farthest distance are removed from the dataset and placed in a new list. A threshold value is selected for this new list. Clustering and classification are the most popular techniques of data mining for retrieving data from large datasets; classification is known as supervised learning phenomena while clustering is called unsupervised learning phenomena. When items in the new list reach the threshold, the values of the new list are returned as initial centroids. ParaMeans software is designed for the Parallel K-Mean clustering algorithm by [35]. They implement the parallelized Basic K-Mean clustering algorithm for the use of general laboratory. ParaMeans provide an easy and manageable client server application. Technique of dynamic load balance to enhance the Parallel K-Mean clustering algorithm is introduced by [36]. Clusters formed by all of the client systems are then sent to the server system. At the server side, all of the clusters (received from all the clients) are compiled. Arithmetic means of each of the compiled clusters are calculated. Newly calculated arithmetic means (centroids) are compared with the previous arithmetic means (centroids). If the value of the new means (centroids) are equal to the previous means (centroids), the process is terminated, otherwise it will be continued. In this technique, same size of the sub-dataset is assigned by the master system to the slave system. The Simple K-Mean clustering algorithm is explained in [37]. The distance between the data items and initial centroids is calculated and each of the data item is placed in its appropriate position. Many researchers then worked on this Simple K-Mean clustering algorithm, and some of the latest research work is discussed. The procedure is sustained till there is no difference in the clusters. Min-Max distance measure is introduced by Karthikeyani and suguna [38]. The input dataset is normalized first and then within the normalized range (0, 1), initial centroids are selected on a random basis. Using min-max similarity measure, the distance is calculated (0, 1) [39]. Ran Vijay and Bhatia [40] have introduced a K-Mean algorithm, items having least frequency. Average of each segment is calculated and considered as the centroid. At the server side, all of the clusters (received from all the clients) are compiled. Arithmetic means of each of the compiled clusters are calculated. Newly calculated arithmetic means (centroids) are compared with the previous arithmetic means for each of the cluster’s centroid; a threshold distance is calculated and at last data items are moved to their appropriate clusters.Chenfei and Zhiyi [41] have documented that any data item is selected in the dataset and distance between that selected data point and other data points is calculated. Threshold value is calculated by dividing the entire area of data points into 100 parts. If the distance value matches to the threshold value, it is selected as the initial centroid. The process is continued to get final clusters. A clustering algorithm is introduced for K-Mean for mixed numeric and categorical data by [42]. Raed and Wasem [43] have proposed an algorithm for the selection of initial centroids. Distance between the selected data items and other data items are calculated to check whether the guess of the random selection of initial centroids was valid or not. Closest data items, based on the threshold value, are selected as the subset, and arithmetic mean of the subset is calculated as the first accepted initial centroid. In this way, remaining initial centroids are computed [13]. Sanpawat and Alva [44] have introduced the parallelized version of Simple K-Mean clustering algorithm. Master-slave (Server-Client) method is used in the algorithm. This algorithm is based on random selection of the initial centroids. One another researcher applied the Parallel K-Mean algorithm using the agricultural data [45]. Client-server architecture is used for the processing of these datasets. They also parallelized Simple K-Mean technique also based on random selection of initial centroids [26, 46]. Parallel clustering technique based on message passing interface (MPI) called M-K-Means composed of MPI and Sequential K-Means is applied on the education datasets [47]. Also, K-Mean and Message Passing interface is mutually used in the same experiment, which is also based on random selection of initial centroids, in which a dataset is divided into “p” sub-datasets where “p” is the number of nodes connected to the main computer. The algorithm is tested on DNA dataset and Simple K-Mean algorithm is parallelized, where initial centroids are selected randomly. Qing et al. [48] have investigated the same nature of study where they found that there is a threshold value that is selected for this new list. When items in the new list reach the threshold, the values of the new list are returned as initial centroids. Para Means software is designed for the Parallel K-Mean clustering algorithm by [13,49]. They implement the parallelized Simple K-Mean clustering algorithm for the use of general laboratory. Para Means provide an easy and manageable client server application, written in C# [39].Technique of dynamic load balance to make the ParallelK-Mean clustering technique efficient and progressive is presented in [42]. In this technique, same size of the sub-dataset is assigned by the master system to the slave system [32]. K-Mean and Parallel K-Mean clustering algorithms are widely known research areas. Many researchers worked on Simple K-Mean and Parallel K-Mean algorithms individually, and they introduced different algorithms, which are discussed in section 2, But, they have no clear idea or suggestion as to how to use K-Mean and Parallel K-Mean algorithms, which could be used further in any area relevant to their usage. Clustering and classification are the most popular techniques of data mining for retrieving data from large datasets; classification is known as supervised learning phenomena while that of clustering is the unsupervised learning phenomena. The K-mean clustering algorithms are tested and compared with the parallel K-mean clustering algorithm for two types of datasets of 10,000 and 5000 data items. These two datasets of 10,000 and 5000 integers may represent the score of 10,000 students in two different subjects and 5000 employee’s attendance in two months, respectively.


## 3. Research Methodology

Figure1 depicts the graphical representation of the two approaches, namely, clustering and classification.Figure 1
Supervised and unsupervised learning.Clustering techniques are classified into four basic categories, which are shown in Figure2.Figure 2
Types of clustering.As discussed, there is no clear idea aboutK-Mean and Parallel K-Mean algorithms as to which one is the best and in which domain and situation the particular technique should be used? To overcome these problems, the study implements and analyzes both Simple K-Mean and Parallel K-Mean clustering to distinguish their performance attributes and cluster quality is applied in general. For this intention, the K-Mean clustering algorithms are evaluated, tested, and compared with the Parallel K-Mean for two types of datasets of 10,000 and 5000 data items. These two datasets of 10,000 and 5000 integers represent the score of 10,000 students in two different subjects and 5000 employee’s attendance in two months, respectively. This chapter discusses the details of the Methodology of this study for Simple K-Mean and Parallel K-Mean clustering. Figure 3 illustrates the overall methodology of the study as follows. The study implemented and analyzed both Simple and Parallel techniques using java and neat beans as a development environment; the two different parameters, i.e., cluster quality and number of iterations are tested and analyzed for two different datasets of integer-type data of 10000 and 5000, respectively, which shows the improvement and performance of cluster quality. This work overcomes the problem of random selection of initial centroids in K-Mean clustering.Figure 3
Research flow diagram.This research work implements and analyzes both Simple and ParallelK-Mean algorithms, to distinguish their performance attributes and cluster quality in general. For this intention, the K-Mean clustering algorithms are tested and compared with the Parallel K-Mean clustering algorithm for two types of datasets of 10,000 and 5000 data items. These two datasets of 10,000 and 5000 integers may represent the score of 10,000 students in two different subjects and 5000 employee’s attendance in two months, respectively. Typical representation of these students in two different subjects through two techniques is shown in Table 1, while the employee’s attendances are shown in Table 2.Table 1
Ten thousand student’s marks.
StudentsSubj-A marksSubj-B marks1836527582::::::::::8560100005575Table 2
Employees’ attendance.
Emp_idMonth_A attendance percentageMonth_B attendance percentageTotal attendance percentage00019075(90 + 75)/2 = …..0002759000038580….…………….……..…….50009575The input and output for these two algorithms may be employed as given below.Herek represents the number of clusters obtained from students and employees’ score in two different subjects and months, respectively, where the Di represents the two datasets containing 10000 students and 5000 employees, while a set of k clusters is the output. Simple and Parallel algorithms are applied individually lying on these data items. Standard notations of UML (Unified Modeling Language) are used to form the flowchart of Basic K-Mean clustering algorithm. The experimental results of both K-Mean and Parallel algorithms are evaluated and analyzed for the difference of these two clustering algorithms. For this purpose, these two algorithms are implemented using Neat beans as an integrated development environment using JAVA and C++platform to run different iterations for specific time and for a specific range of data. Simple K-Mean clustering algorithm takes “k” initial centroids randomly. In the second step, the Euclidean distance function is used to calculate the distances between centroids and data items.Different distance functions are mentioned in [24, 50]. Each of the data item is moved to the cluster having less space. In this way, initial clusters are formed. Then the arithmetic mean of each cluster is calculated. Data items having less distance to the arithmetic mean are placed in that particular cluster. Then again, the arithmetic mean of each cluster is designed and data points are move to the desired cluster. The process is sustained until no data point moves from one cluster to another cluster. Improving and creating clusters stop when:The provided number of iterations has been completedThe clustering has been successful, i.e., cluster has become stable


### 3.1. Algorithmic Steps of SimpleK-Mean Clustering Algorithm

Figure4 is the pseudo code for Simple K-Mean clustering algorithm [51].Figure 4
SimpleK-Mean clustering algorithm.


#### 3.1.1. Flow Chart of SimpleK-Mean Algorithm

Standard notations of UML are used to form the flowchart of SimpleK-Mean algorithm. Figure 5 shows the flow chart of Simple K-Mean algorithm.Figure 5
Flow chart of SimpleK-Mean algorithm.


### 3.2. ParallelK-Mean Clustering Algorithm

Most critical issues for SimpleK-Mean clustering algorithm are the space and processing speed requirements, when the dataset is very large. To resolve these issues, Simple K-Mean clustering algorithm is parallelized.


#### 3.2.1. Steps of ParallelK-Mean Algorithm

Three main steps of the Simple ParallelK-Mean arePartitionComputationCompilationIn the first step at the server side, sub-datasets are produced from a given dataset. All client systems that are connected to the server receive these sub-datasets with the number of clusters, i.e., “k” and initial centroids. The said client systems calculate clusters and forward that results to the server. This process continues till there is no change in the clusters.Server’s activitiesPartition dataset and randomly select initial centroids C=C1+ C2+………+ CnSend initial centroids C=C1+ C2+………+ Cn and sub-datasets to all connected clientsReceive clusters and centroids from all the clientsRecalculation of centroidsClient’s activitiesReceivek, initial centroids C=C1+ C2+………+ Cn and sub-datasets from the serverCalculate distances from all centroidsMove data items to appropriate clustersSend cluster elements to the server


#### 3.2.2. Flow Chart of ParallelK-Mean Clustering Algorithm

Steps described above are shown in the flow chart in Figure6. Standard notations of UML are used to form the flow chart.Figure 6
Flow chart of Simple ParallelK-Mean clustering algorithm.


### 3.3. SimpleK-Mean Implementation

#### 3.3.1. Calculation of Initial Centroids

SimpleK-Mean clustering algorithm depends on the selection of the initial centroids. If different data items are selected in different runs of the same dataset, different results are found in each run. To overcome this issue, initial centroids are calculated by the following steps:


#### 3.3.2. Initial Clusters

In order to find the initial cluster, the whole dataset is partitioned intok number of sub-datasets by using(1)initial clusters=floornk,where “n” is the total number of data items in the given dataset, which is to be clustered and “k” is the total number of clusters.Floor value ofn/k is taken in the parallel technique because all of the sub-datasets will have the same number of data items, and if any of the data items is left, it will be placed in the last cluster.


#### 3.3.3. Initial Centroids

After getting the initial clusters, initial centroids are calculated by(2)initial centroids=arithmetic mean of initial clusters,(3)arithmetic meanA.Mof initial cluster=∑sum of all data items in clustertotal number of data items.


#### 3.3.4. Distance Calculation

Distance between initial centroids and each of the data items is calculated by the Euclidean distance equation:(4)Euclidean distanceCi,Di=Ci−Di,where Ci is the initial centroid values for i ≤ k (k is the number of clusters) and Di is the data item for i ≤ n, where n is the total number of data items in the given dataset.


#### 3.3.5. Assignment of Data Item to Appropriate Cluster

Distances among all data items and initial centroids are compared. Data items having minimum distance from the initial centroid are assigned to that particular cluster. The minimum distance is calculated by the following formula:(5)min distance=mini≤nCi−Di,where “i” is a variable and “n” is the number of data items.Similar or closest data items are placed in the same cluster.


#### 3.3.6. Process of Termination

Arithmetic mean of each of the calculated clusters is compared with the previous mean value (centroid). If both of the means (centroid values) are the same, then the process will be terminated; otherwise, it will continue until the same centroids (mean values) are found.


### 3.4. ParallelK-Mean Algorithm Implementation

The basicK-Mean clustering algorithm requires maximum space and processing speed for large datasets. For this intention, K-Mean is parallelized. The K-Mean algorithm selects initial centroids randomly. Problems of the Simple K-Mean algorithm also exist in the Simple Parallel K-Mean clustering algorithm. To resolve these problems, Parallel algorithm is parallelized. Client server structural design is used in the efficient Parallel K-Mean clustering algorithm.


#### 3.4.1. Tasks of the Sever System

Main tasks of the server or the main system are as follows:Partition Data for all client systems (Client 1, Client 2….. Clientn)Partition Data and Calculate initial centroidsC=C1+ C2+………+ CnSend initial centroidsC=C1+ C2+………+ Cn to all systemsReceive clusters and centroids from all connected systems


#### 3.4.2. Tasks of Client Systems

Main tasks of the client systems are as follows:Receivek, initial centroids C=C1+ C2+………+ Cn and sub-dataset from the server systemCalculate distances from all centroidsMove data item to the appropriate clusterSend cluster elements back to the main system


### 3.5. Steps of ParallelK-Mean Algorithm

Following are the main steps of the ParallelK-Mean algorithm.


#### 3.5.1. Data Partitioning For Client Systems

The first step of the ParallelK-Mean clustering algorithm is to divide the input dataset into sub-datasets for all client systems. Dataset is divided into “x” number of sub-datasets, if total “x” number of client systems are connected to the server system. Value of “x” is calculated as(6)subdata setsi=x=floornx,where “n” is the total number of data items in the given dataset and “x” is the total number of client systems connected to the server system.


#### 3.5.2. Calculation of Initial Centroids

Initial centroids are calculated in two steps:Find initial cluster that can be formed by using equation (1)Calculate initial centroids using equations (2) and (3)Initial Centroids = Arithmetic Mean of initial clusters such as in (2)Arithmetic Mean (A.M) of initial cluster = Σ (sum of all data items in cluster)/total number of data items as in (3)


#### 3.5.3. Distance Calculation by Client Systems

Sub-datasets and initial centroids are sent to all clients. Only one sub-dataset is sent to each client. Distance is calculated using equation (4).


#### 3.5.4. Making Clusters by Client Systems

The distance between data items and initial centroids are compared. Data item closest to the centroid value is assigned to that cluster. In this way, data items are placed in their appropriate clusters.


#### 3.5.5. Compiling Results of Client Systems by the Server System and Termination

Clusters formed by all of the client systems are then sent to the server system. At the server side, all of the clusters (received from all the clients) are compiled. Arithmetic means of each of the compiled clusters are calculated. Newly calculated arithmetic means (centroids) are compared with the previous arithmetic means (centroids). If the values of the new means (centroids) are equal to the previous means (centroids), the process is terminated; otherwise, it will be continued.


### 3.6. Time Complexity ofK-Mean Algorithm

K-Mean algorithm comprises 2 phases. The 1st phase is to compute the initial clusters by dividing the dataset into “k” equal parts and to calculate the arithmetic mean. Time complexity for partitioning dataset into “k” equal parts and finding arithmetic mean is O(n). Thus, the time complexity of the first phase is O(n). In the second phase of the Parallel K-Mean clustering algorithm, data items are assigned to the appropriate cluster. This phase takes O(nkt). Where n is the number of data items, k is the number of clusters, and t is the number of iterations. Thus, the overall time complexity of the K-Mean clustering algorithm is maximum of O(n) and O(nkt). That is, O(n) + O(nkt), so the overall time complexity is O(nkt), as we ignore the lowest order and constant terms in the asymptotic notations.


## 3.1. Algorithmic Steps of SimpleK-Mean Clustering Algorithm

Figure4 is the pseudo code for Simple K-Mean clustering algorithm [51].Figure 4
SimpleK-Mean clustering algorithm.


### 3.1.1. Flow Chart of SimpleK-Mean Algorithm

Standard notations of UML are used to form the flowchart of SimpleK-Mean algorithm. Figure 5 shows the flow chart of Simple K-Mean algorithm.Figure 5
Flow chart of SimpleK-Mean algorithm.


## 3.1.1. Flow Chart of SimpleK-Mean Algorithm

Standard notations of UML are used to form the flowchart of SimpleK-Mean algorithm. Figure 5 shows the flow chart of Simple K-Mean algorithm.Figure 5
Flow chart of SimpleK-Mean algorithm.


## 3.2. ParallelK-Mean Clustering Algorithm

Most critical issues for SimpleK-Mean clustering algorithm are the space and processing speed requirements, when the dataset is very large. To resolve these issues, Simple K-Mean clustering algorithm is parallelized.


### 3.2.1. Steps of ParallelK-Mean Algorithm

Three main steps of the Simple ParallelK-Mean arePartitionComputationCompilationIn the first step at the server side, sub-datasets are produced from a given dataset. All client systems that are connected to the server receive these sub-datasets with the number of clusters, i.e., “k” and initial centroids. The said client systems calculate clusters and forward that results to the server. This process continues till there is no change in the clusters.Server’s activitiesPartition dataset and randomly select initial centroids C=C1+ C2+………+ CnSend initial centroids C=C1+ C2+………+ Cn and sub-datasets to all connected clientsReceive clusters and centroids from all the clientsRecalculation of centroidsClient’s activitiesReceivek, initial centroids C=C1+ C2+………+ Cn and sub-datasets from the serverCalculate distances from all centroidsMove data items to appropriate clustersSend cluster elements to the server


### 3.2.2. Flow Chart of ParallelK-Mean Clustering Algorithm

Steps described above are shown in the flow chart in Figure6. Standard notations of UML are used to form the flow chart.Figure 6
Flow chart of Simple ParallelK-Mean clustering algorithm.


## 3.2.1. Steps of ParallelK-Mean Algorithm

Three main steps of the Simple ParallelK-Mean arePartitionComputationCompilationIn the first step at the server side, sub-datasets are produced from a given dataset. All client systems that are connected to the server receive these sub-datasets with the number of clusters, i.e., “k” and initial centroids. The said client systems calculate clusters and forward that results to the server. This process continues till there is no change in the clusters.Server’s activitiesPartition dataset and randomly select initial centroids C=C1+ C2+………+ CnSend initial centroids C=C1+ C2+………+ Cn and sub-datasets to all connected clientsReceive clusters and centroids from all the clientsRecalculation of centroidsClient’s activitiesReceivek, initial centroids C=C1+ C2+………+ Cn and sub-datasets from the serverCalculate distances from all centroidsMove data items to appropriate clustersSend cluster elements to the server


## 3.2.2. Flow Chart of ParallelK-Mean Clustering Algorithm

Steps described above are shown in the flow chart in Figure6. Standard notations of UML are used to form the flow chart.Figure 6
Flow chart of Simple ParallelK-Mean clustering algorithm.


## 3.3. SimpleK-Mean Implementation

### 3.3.1. Calculation of Initial Centroids

SimpleK-Mean clustering algorithm depends on the selection of the initial centroids. If different data items are selected in different runs of the same dataset, different results are found in each run. To overcome this issue, initial centroids are calculated by the following steps:


### 3.3.2. Initial Clusters

In order to find the initial cluster, the whole dataset is partitioned intok number of sub-datasets by using(1)initial clusters=floornk,where “n” is the total number of data items in the given dataset, which is to be clustered and “k” is the total number of clusters.Floor value ofn/k is taken in the parallel technique because all of the sub-datasets will have the same number of data items, and if any of the data items is left, it will be placed in the last cluster.


### 3.3.3. Initial Centroids

After getting the initial clusters, initial centroids are calculated by(2)initial centroids=arithmetic mean of initial clusters,(3)arithmetic meanA.Mof initial cluster=∑sum of all data items in clustertotal number of data items.


### 3.3.4. Distance Calculation

Distance between initial centroids and each of the data items is calculated by the Euclidean distance equation:(4)Euclidean distanceCi,Di=Ci−Di,where Ci is the initial centroid values for i ≤ k (k is the number of clusters) and Di is the data item for i ≤ n, where n is the total number of data items in the given dataset.


### 3.3.5. Assignment of Data Item to Appropriate Cluster

Distances among all data items and initial centroids are compared. Data items having minimum distance from the initial centroid are assigned to that particular cluster. The minimum distance is calculated by the following formula:(5)min distance=mini≤nCi−Di,where “i” is a variable and “n” is the number of data items.Similar or closest data items are placed in the same cluster.


### 3.3.6. Process of Termination

Arithmetic mean of each of the calculated clusters is compared with the previous mean value (centroid). If both of the means (centroid values) are the same, then the process will be terminated; otherwise, it will continue until the same centroids (mean values) are found.


## 3.3.1. Calculation of Initial Centroids

SimpleK-Mean clustering algorithm depends on the selection of the initial centroids. If different data items are selected in different runs of the same dataset, different results are found in each run. To overcome this issue, initial centroids are calculated by the following steps:


## 3.3.2. Initial Clusters

In order to find the initial cluster, the whole dataset is partitioned intok number of sub-datasets by using(1)initial clusters=floornk,where “n” is the total number of data items in the given dataset, which is to be clustered and “k” is the total number of clusters.Floor value ofn/k is taken in the parallel technique because all of the sub-datasets will have the same number of data items, and if any of the data items is left, it will be placed in the last cluster.


## 3.3.3. Initial Centroids

After getting the initial clusters, initial centroids are calculated by(2)initial centroids=arithmetic mean of initial clusters,(3)arithmetic meanA.Mof initial cluster=∑sum of all data items in clustertotal number of data items.


## 3.3.4. Distance Calculation

Distance between initial centroids and each of the data items is calculated by the Euclidean distance equation:(4)Euclidean distanceCi,Di=Ci−Di,where Ci is the initial centroid values for i ≤ k (k is the number of clusters) and Di is the data item for i ≤ n, where n is the total number of data items in the given dataset.


## 3.3.5. Assignment of Data Item to Appropriate Cluster

Distances among all data items and initial centroids are compared. Data items having minimum distance from the initial centroid are assigned to that particular cluster. The minimum distance is calculated by the following formula:(5)min distance=mini≤nCi−Di,where “i” is a variable and “n” is the number of data items.Similar or closest data items are placed in the same cluster.


## 3.3.6. Process of Termination

Arithmetic mean of each of the calculated clusters is compared with the previous mean value (centroid). If both of the means (centroid values) are the same, then the process will be terminated; otherwise, it will continue until the same centroids (mean values) are found.


## 3.4. ParallelK-Mean Algorithm Implementation

The basicK-Mean clustering algorithm requires maximum space and processing speed for large datasets. For this intention, K-Mean is parallelized. The K-Mean algorithm selects initial centroids randomly. Problems of the Simple K-Mean algorithm also exist in the Simple Parallel K-Mean clustering algorithm. To resolve these problems, Parallel algorithm is parallelized. Client server structural design is used in the efficient Parallel K-Mean clustering algorithm.


### 3.4.1. Tasks of the Sever System

Main tasks of the server or the main system are as follows:Partition Data for all client systems (Client 1, Client 2….. Clientn)Partition Data and Calculate initial centroidsC=C1+ C2+………+ CnSend initial centroidsC=C1+ C2+………+ Cn to all systemsReceive clusters and centroids from all connected systems


### 3.4.2. Tasks of Client Systems

Main tasks of the client systems are as follows:Receivek, initial centroids C=C1+ C2+………+ Cn and sub-dataset from the server systemCalculate distances from all centroidsMove data item to the appropriate clusterSend cluster elements back to the main system


## 3.4.1. Tasks of the Sever System

Main tasks of the server or the main system are as follows:Partition Data for all client systems (Client 1, Client 2….. Clientn)Partition Data and Calculate initial centroidsC=C1+ C2+………+ CnSend initial centroidsC=C1+ C2+………+ Cn to all systemsReceive clusters and centroids from all connected systems


## 3.4.2. Tasks of Client Systems

Main tasks of the client systems are as follows:Receivek, initial centroids C=C1+ C2+………+ Cn and sub-dataset from the server systemCalculate distances from all centroidsMove data item to the appropriate clusterSend cluster elements back to the main system


## 3.5. Steps of ParallelK-Mean Algorithm

Following are the main steps of the ParallelK-Mean algorithm.


### 3.5.1. Data Partitioning For Client Systems

The first step of the ParallelK-Mean clustering algorithm is to divide the input dataset into sub-datasets for all client systems. Dataset is divided into “x” number of sub-datasets, if total “x” number of client systems are connected to the server system. Value of “x” is calculated as(6)subdata setsi=x=floornx,where “n” is the total number of data items in the given dataset and “x” is the total number of client systems connected to the server system.


### 3.5.2. Calculation of Initial Centroids

Initial centroids are calculated in two steps:Find initial cluster that can be formed by using equation (1)Calculate initial centroids using equations (2) and (3)Initial Centroids = Arithmetic Mean of initial clusters such as in (2)Arithmetic Mean (A.M) of initial cluster = Σ (sum of all data items in cluster)/total number of data items as in (3)


### 3.5.3. Distance Calculation by Client Systems

Sub-datasets and initial centroids are sent to all clients. Only one sub-dataset is sent to each client. Distance is calculated using equation (4).


### 3.5.4. Making Clusters by Client Systems

The distance between data items and initial centroids are compared. Data item closest to the centroid value is assigned to that cluster. In this way, data items are placed in their appropriate clusters.


### 3.5.5. Compiling Results of Client Systems by the Server System and Termination

Clusters formed by all of the client systems are then sent to the server system. At the server side, all of the clusters (received from all the clients) are compiled. Arithmetic means of each of the compiled clusters are calculated. Newly calculated arithmetic means (centroids) are compared with the previous arithmetic means (centroids). If the values of the new means (centroids) are equal to the previous means (centroids), the process is terminated; otherwise, it will be continued.


## 3.5.1. Data Partitioning For Client Systems

The first step of the ParallelK-Mean clustering algorithm is to divide the input dataset into sub-datasets for all client systems. Dataset is divided into “x” number of sub-datasets, if total “x” number of client systems are connected to the server system. Value of “x” is calculated as(6)subdata setsi=x=floornx,where “n” is the total number of data items in the given dataset and “x” is the total number of client systems connected to the server system.


## 3.5.2. Calculation of Initial Centroids

Initial centroids are calculated in two steps:Find initial cluster that can be formed by using equation (1)Calculate initial centroids using equations (2) and (3)Initial Centroids = Arithmetic Mean of initial clusters such as in (2)Arithmetic Mean (A.M) of initial cluster = Σ (sum of all data items in cluster)/total number of data items as in (3)


## 3.5.3. Distance Calculation by Client Systems

Sub-datasets and initial centroids are sent to all clients. Only one sub-dataset is sent to each client. Distance is calculated using equation (4).


## 3.5.4. Making Clusters by Client Systems

The distance between data items and initial centroids are compared. Data item closest to the centroid value is assigned to that cluster. In this way, data items are placed in their appropriate clusters.


## 3.5.5. Compiling Results of Client Systems by the Server System and Termination

Clusters formed by all of the client systems are then sent to the server system. At the server side, all of the clusters (received from all the clients) are compiled. Arithmetic means of each of the compiled clusters are calculated. Newly calculated arithmetic means (centroids) are compared with the previous arithmetic means (centroids). If the values of the new means (centroids) are equal to the previous means (centroids), the process is terminated; otherwise, it will be continued.


## 3.6. Time Complexity ofK-Mean Algorithm

K-Mean algorithm comprises 2 phases. The 1st phase is to compute the initial clusters by dividing the dataset into “k” equal parts and to calculate the arithmetic mean. Time complexity for partitioning dataset into “k” equal parts and finding arithmetic mean is O(n). Thus, the time complexity of the first phase is O(n). In the second phase of the Parallel K-Mean clustering algorithm, data items are assigned to the appropriate cluster. This phase takes O(nkt). Where n is the number of data items, k is the number of clusters, and t is the number of iterations. Thus, the overall time complexity of the K-Mean clustering algorithm is maximum of O(n) and O(nkt). That is, O(n) + O(nkt), so the overall time complexity is O(nkt), as we ignore the lowest order and constant terms in the asymptotic notations.


## 4. Results and Discussion

Both the algorithms are tested and compared with each other for a dataset of 10,000, and 5000 integer data items. The experimental results of both algorithms were satisfactory and overcome the problem of SimpleK-Mean clustering algorithm. Comparison of Simple K-Mean and Parallel K-Mean algorithm in terms of number of iterations, elapsed time, and cluster quality is given. The detailed and actual results of the comparison of the Simple and Parallel algorithms are discussed in the following section. Comparison of Simple K-Mean and Parallel K-Mean algorithm in terms of number of iterations, elapsed time, and cluster quality is given.


### 4.1. Number of Iterations

For different number of clusters (K), performance of the Simple K-Mean and Parallel K-Mean clustering algorithm is shown in the following tables and graphs. Table 3 represents the iterations for K = 3.Table 3
Iterations forK = 3.
ForK = 3Runs/executionsNumber of iterations by SimpleK-Mean clusteringNumber of iterations by ParallelK-Mean clustering0112302930312304930573061430793081230910310153In Table3, Simple K-Mean algorithms and Parallel K-Mean procedures are compared for the same datasets and (K = 3) the number of clusters. For each run, the same dataset, i.e. (10,000 data points), is entered to observe and perceive that each time, the number of iterations is different in Simple K-Mean algorithm. The numbers of iterations are the same (fixed) in the Parallel K-Mean algorithm because the initial centroids are not selected randomly. Graph of Table 3 is represented in Figure 7.Figure 7
Representation of Table3.Number of iterations are fixed in the case of ParallelK-Mean algorithm, i.e., 3 for k = 3, but keeps changing from one run to other in the case of Simple K-Mean clustering algorithm. Table 4 shows the iterations for K = 4.Table 4
Iterations forK = 4.
ForK = 4Runs/executionsNumber of iterations by SimpleK-Mean clusteringNumber of iterations by ParallelK-Mean clustering0115aph102181031810415105151061510716108131091311051Table4 shows that the number of iterations of Parallel K-Mean clustering algorithm are less than the number of iterations of Simple K-Mean clustering algorithm for k = 4. Graph of Table 4 is represented in Figure 8.Figure 8
Graph of Table4.Table5 shows the iterations for K = 4.Table 5
Iterations forK = 5.
ForK = 5Runs/executionsNumber of iterations by SimpleK-Mean clusteringNumber of iterations by ParallelK-Mean clustering011460210603760486051360618607166082660928610266Table5 shows that the number of iterations of Parallel K-Mean clustering algorithm are fixed and less than the number of iterations of Simple K-Mean clustering algorithm for k = 5. Graph of Table 5 is represented in Figure 9.Figure 9
Graph of Table5.Table6 shows the iterations for K = 6.Table 6
Iterations forK = 6.
.ForK = 6Runs/executionsNumber of iterations by SimpleK-Mean clusteringNumber of iterations by ParallelK-Mean clustering0113202172038204112051320611207202081820917210202Table6 shows the fixed and less number of iterations of Parallel and Simple K-Mean clustering algorithms for k = 6. Graph of Table 6 is represented in Figure 10.Figure 10
Graph of Table6. Number of iterations for K = 6.Table7 shows the iterations for K = 7.Table 7
Iterations forK = 7.
ForK = 7Runs/executionsNumber of iterations by SimpleK-Mean clusteringNumber of iterations by ParallelK-Mean clustering011080298031080412805118061980721808148091881068Table7 shows the number of iterations of Simple and Parallel algorithms for k = 7. Graph of Table 7 is represented in Figure 11.Figure 11
Graph of Table7. Number of iterations for K = 7.


### 4.2. Elapsed Time

For different number of clusters (K), elapsed time of the Simple and Parallel clustering algorithms is shown in the following tables and graphs. Screenshots are given in Appendix. Table 8 shows the elapsed time for K = 3.Table 8
Elapsed time forK = 3.
ForK = 3Runs/executionsElapsed time by SimpleK-Mean clustering in msElapsed time by ParallelK-Mean clustering in ms0118.77.80214.17.80320.39.30418.79.30514.09.30620.39.40714.67.80818.79.30914.69.31018.79.3In Table8, Simple and Parallel clustering algorithms are compared for K = 3. At each run, elapsed time of the Parallel K-Mean clustering algorithm is less than the elapsed time of the Simple K-Mean clustering algorithm. Graph of Table 8 is represented in Figure 12.Figure 12
Graph of Table8. Elapsed time for K = 3.Elapsed time of the ParallelK-Mean algorithm is less than the elapsed time of the Simple K-Mean algorithm at different runs or executions. Table 9 shows the elapsed time for K = 4.Table 9
Elapsed time forK = 4.
ForK = 4Runs/executionsElapsed time by SimpleK-Mean clustering in msElapsed time by ParallelK-Mean clustering in ms0114.67.80218.87.80318.77.80417.16.20518.76.20618.86.20718.76.30814.66.20914.66.21010.96.3Table9 shows the elapsed time of Parallel and Simple K-Mean clustering algorithm for k = 4. Graph of Table 9 is represented in Figure 13.Figure 13
Graph of Table9. Elapsed time for K = 4.Table10 shows the elapsed time for K = 5.Table 10
Elapsed time forK = 5.
ForK = 5Runs/executionsElapsed time by SimpleK-Mean clustering in msElapsed time by ParallelK-Mean clustering in ms0114.610.90214.010.90312.59.30412.510.90514.69.30618.710.90717.110.90823.49.40923.49.31023.49.3Table10 shows the comparison of the Parallel clustering algorithm and Simple K-Mean algorithm for k = 5 in terms of elapsed time. Graph of Table 10 is represented in Figure 14.Figure 14
Graph of Table10. Elapsed time for K = 5.Table11 shows the elapsed time for K = 6.Table 11
Elapsed time forK = 6.
ForK = 6Runs/executionsElapsed time by SimpleK-Mean clustering in msElapsed time by ParallelK-Mean clustering in ms0117.19.30223.49.40314.614.00417.19.40520.37.80617.19.30726.57.80818.79.30918.89.41020.314.0Table11 shows the similarity of the elapsed time of Parallel and the Simple K-Mean algorithms for k = 6. Graph of Table 11 is represented in Figure 15.Figure 15
Graph of Table11. Elapsed time for K = 6.Table12 shows the elapsed time for K = 7.Table 12
Elapsed time forK = 7.
ForK = 7Runs/executionsElapsed time by SimpleK-Mean clustering in msElapsed time by ParallelK-Mean clustering in ms0114.110.90214.012.50314.614.10417.214.00514.614.10612.514.10720.312.50823.414.00917.114.11020.212.5Graph of Table12 is represented in Figure 16.Figure 16
Graph of Table12. Elapsed time for K = 7.


### 4.3. Cluster Quality

Comparison of SimpleK-Mean and Parallel K-Mean algorithms in terms of cluster quality is discussed below. Table 13 represents the cluster quality of Simple K-Mean clustering for k = 3.Table 13
Cluster quality of SimpleK-Mean clustering for K = 3.
S.#No. of iterationsElapsed time in ms# of data items in cluster 1# of data items in cluster 2# of data items in cluster 3Total number of data items011218.73312276439241000002914.128383456370610000031220.32838345637061000004918.73706283834561000005714.027643312392410000061420.33706283834561000007914.634562838370610000081218.727643312392410000091014.634562838370610000101518.739243312276410000In Table13, different outcomes for the same dataset of 10,000 data items at different runs or executions are shown. Graph of Table 13 is represented in Figure 17.Figure 17
Graph of the Table13. Cluster quality of Simple K-Mean for K = 3.Table14 represents the cluster quality of Parallel K-Mean clustering for k = 3.Table 14
Cluster quality of ParallelK-Mean clustering for K = 3.
S.#No. of iterationsElapsed time in ms# of data items in cluster 1# of data items in cluster 2# of data items in cluster 3Total number of data items0137.8382227223456100000237.8382227223456100000339.3382227223456100000439.3382227223456100000539.3382227223456100000639.4382227223456100000737.8382227223456100000839.3382227223456100000939.3382227223456100001039.338222722345610000In Table14, same outcomes for the same dataset of 10,000 data items at different runs or executions are shown. Graph of Table 14 is represented in Figure 18.Figure 18
Graph of the Table14. Cluster quality of Parallel K-Mean clustering for K = 3.


### 4.4. Comparison of Simple and ParallelK-Mean Algorithms

Simple and Parallel K-Mean algorithms in terms of the number of iterations and comparison of elapsed time is given in the following.


#### 4.4.1. Number of Iterations

For different number of clusters (K), performance of the Simple K-Mean and Parallel K-Mean algorithms is shown in Table15.Table 15
Number of iterations for Simple and ParallelK-Means.
KNumber of iterationsSimpleK-Mean clusteringParallelK-Mean clustering2723153495Table15 shows that for different “k” number of clusters, number of iterations is less in Parallel K-Mean algorithm than the Simple K-Mean algorithm. Graph of Table 15 is represented in Figure 19.Figure 19
Graph of Table14. Number of iterations for Simple and Parallel K-Mean algorithms.


#### 4.4.2. Elapsed Time

Elapsed time of the SimpleK-Mean and Parallel K-Mean algorithms for k = 2 is shown in Table 16.Table 16
Elapsed time of ParallelK-Mean clustering for k = 2.
K = 2S#Client systemsElapsed time in ms (1stitr + 2nditr)# of data items in cluster 1# of data items in cluster 2Total data items1Client 16.0 + 6.053446610002Client 24.0 + 4.01000010003Client 34.0 + 4.01000010004Client 44.0 + 4.01000010005Client 58.0 + 4.01000010006Client 66.0 + 6.055244810007Client 74.0 + 4.00100010008Client 84.0 + 4.00100010009Client 94.0 + 4.001000100010Client 104.0 + 4.0010001000Total12.05086491410000Table16 shows that the dataset of 10,000 data items is partitioned into 10 sub-datasets for 10 client systems. Clusters are formed in 2 iterations (elapsed time for iterations by all client systems is mentioned in the table). In the first iteration, client 5 has the largest elapsed time, i.e., 8 ms, while in the second iteration, the largest elapsed time is 6 ms, so the total elapsed time of the client systems is 12 ms for the Parallel K-Mean clustering algorithm. Table 17 shows the elapsed time of Simple K-Mean for k = 2.Table 17
Elapsed time of SimpleK-Mean for k = 2.
K = 2S#Elapsed time# of data items in cluster 1# of data items in cluster 2Total data items114.05392460810000This section described the results and their discussion in detail of the proposed research. Experiments were designed to prove that Parallel algorithms are showing significant improvement in the SimpleK-Mean algorithm. Outcomes of the Parallel algorithms are also same, while outcomes of the Simple K-Mean algorithm give different results on every run or execution. Also, total iterations and elapse time is improved in the Parallel algorithms. The next section concludes the completed research work and shows the directions for the future research.


## 4.1. Number of Iterations

For different number of clusters (K), performance of the Simple K-Mean and Parallel K-Mean clustering algorithm is shown in the following tables and graphs. Table 3 represents the iterations for K = 3.Table 3
Iterations forK = 3.
ForK = 3Runs/executionsNumber of iterations by SimpleK-Mean clusteringNumber of iterations by ParallelK-Mean clustering0112302930312304930573061430793081230910310153In Table3, Simple K-Mean algorithms and Parallel K-Mean procedures are compared for the same datasets and (K = 3) the number of clusters. For each run, the same dataset, i.e. (10,000 data points), is entered to observe and perceive that each time, the number of iterations is different in Simple K-Mean algorithm. The numbers of iterations are the same (fixed) in the Parallel K-Mean algorithm because the initial centroids are not selected randomly. Graph of Table 3 is represented in Figure 7.Figure 7
Representation of Table3.Number of iterations are fixed in the case of ParallelK-Mean algorithm, i.e., 3 for k = 3, but keeps changing from one run to other in the case of Simple K-Mean clustering algorithm. Table 4 shows the iterations for K = 4.Table 4
Iterations forK = 4.
ForK = 4Runs/executionsNumber of iterations by SimpleK-Mean clusteringNumber of iterations by ParallelK-Mean clustering0115aph102181031810415105151061510716108131091311051Table4 shows that the number of iterations of Parallel K-Mean clustering algorithm are less than the number of iterations of Simple K-Mean clustering algorithm for k = 4. Graph of Table 4 is represented in Figure 8.Figure 8
Graph of Table4.Table5 shows the iterations for K = 4.Table 5
Iterations forK = 5.
ForK = 5Runs/executionsNumber of iterations by SimpleK-Mean clusteringNumber of iterations by ParallelK-Mean clustering011460210603760486051360618607166082660928610266Table5 shows that the number of iterations of Parallel K-Mean clustering algorithm are fixed and less than the number of iterations of Simple K-Mean clustering algorithm for k = 5. Graph of Table 5 is represented in Figure 9.Figure 9
Graph of Table5.Table6 shows the iterations for K = 6.Table 6
Iterations forK = 6.
.ForK = 6Runs/executionsNumber of iterations by SimpleK-Mean clusteringNumber of iterations by ParallelK-Mean clustering0113202172038204112051320611207202081820917210202Table6 shows the fixed and less number of iterations of Parallel and Simple K-Mean clustering algorithms for k = 6. Graph of Table 6 is represented in Figure 10.Figure 10
Graph of Table6. Number of iterations for K = 6.Table7 shows the iterations for K = 7.Table 7
Iterations forK = 7.
ForK = 7Runs/executionsNumber of iterations by SimpleK-Mean clusteringNumber of iterations by ParallelK-Mean clustering011080298031080412805118061980721808148091881068Table7 shows the number of iterations of Simple and Parallel algorithms for k = 7. Graph of Table 7 is represented in Figure 11.Figure 11
Graph of Table7. Number of iterations for K = 7.


## 4.2. Elapsed Time

For different number of clusters (K), elapsed time of the Simple and Parallel clustering algorithms is shown in the following tables and graphs. Screenshots are given in Appendix. Table 8 shows the elapsed time for K = 3.Table 8
Elapsed time forK = 3.
ForK = 3Runs/executionsElapsed time by SimpleK-Mean clustering in msElapsed time by ParallelK-Mean clustering in ms0118.77.80214.17.80320.39.30418.79.30514.09.30620.39.40714.67.80818.79.30914.69.31018.79.3In Table8, Simple and Parallel clustering algorithms are compared for K = 3. At each run, elapsed time of the Parallel K-Mean clustering algorithm is less than the elapsed time of the Simple K-Mean clustering algorithm. Graph of Table 8 is represented in Figure 12.Figure 12
Graph of Table8. Elapsed time for K = 3.Elapsed time of the ParallelK-Mean algorithm is less than the elapsed time of the Simple K-Mean algorithm at different runs or executions. Table 9 shows the elapsed time for K = 4.Table 9
Elapsed time forK = 4.
ForK = 4Runs/executionsElapsed time by SimpleK-Mean clustering in msElapsed time by ParallelK-Mean clustering in ms0114.67.80218.87.80318.77.80417.16.20518.76.20618.86.20718.76.30814.66.20914.66.21010.96.3Table9 shows the elapsed time of Parallel and Simple K-Mean clustering algorithm for k = 4. Graph of Table 9 is represented in Figure 13.Figure 13
Graph of Table9. Elapsed time for K = 4.Table10 shows the elapsed time for K = 5.Table 10
Elapsed time forK = 5.
ForK = 5Runs/executionsElapsed time by SimpleK-Mean clustering in msElapsed time by ParallelK-Mean clustering in ms0114.610.90214.010.90312.59.30412.510.90514.69.30618.710.90717.110.90823.49.40923.49.31023.49.3Table10 shows the comparison of the Parallel clustering algorithm and Simple K-Mean algorithm for k = 5 in terms of elapsed time. Graph of Table 10 is represented in Figure 14.Figure 14
Graph of Table10. Elapsed time for K = 5.Table11 shows the elapsed time for K = 6.Table 11
Elapsed time forK = 6.
ForK = 6Runs/executionsElapsed time by SimpleK-Mean clustering in msElapsed time by ParallelK-Mean clustering in ms0117.19.30223.49.40314.614.00417.19.40520.37.80617.19.30726.57.80818.79.30918.89.41020.314.0Table11 shows the similarity of the elapsed time of Parallel and the Simple K-Mean algorithms for k = 6. Graph of Table 11 is represented in Figure 15.Figure 15
Graph of Table11. Elapsed time for K = 6.Table12 shows the elapsed time for K = 7.Table 12
Elapsed time forK = 7.
ForK = 7Runs/executionsElapsed time by SimpleK-Mean clustering in msElapsed time by ParallelK-Mean clustering in ms0114.110.90214.012.50314.614.10417.214.00514.614.10612.514.10720.312.50823.414.00917.114.11020.212.5Graph of Table12 is represented in Figure 16.Figure 16
Graph of Table12. Elapsed time for K = 7.


## 4.3. Cluster Quality

Comparison of SimpleK-Mean and Parallel K-Mean algorithms in terms of cluster quality is discussed below. Table 13 represents the cluster quality of Simple K-Mean clustering for k = 3.Table 13
Cluster quality of SimpleK-Mean clustering for K = 3.
S.#No. of iterationsElapsed time in ms# of data items in cluster 1# of data items in cluster 2# of data items in cluster 3Total number of data items011218.73312276439241000002914.128383456370610000031220.32838345637061000004918.73706283834561000005714.027643312392410000061420.33706283834561000007914.634562838370610000081218.727643312392410000091014.634562838370610000101518.739243312276410000In Table13, different outcomes for the same dataset of 10,000 data items at different runs or executions are shown. Graph of Table 13 is represented in Figure 17.Figure 17
Graph of the Table13. Cluster quality of Simple K-Mean for K = 3.Table14 represents the cluster quality of Parallel K-Mean clustering for k = 3.Table 14
Cluster quality of ParallelK-Mean clustering for K = 3.
S.#No. of iterationsElapsed time in ms# of data items in cluster 1# of data items in cluster 2# of data items in cluster 3Total number of data items0137.8382227223456100000237.8382227223456100000339.3382227223456100000439.3382227223456100000539.3382227223456100000639.4382227223456100000737.8382227223456100000839.3382227223456100000939.3382227223456100001039.338222722345610000In Table14, same outcomes for the same dataset of 10,000 data items at different runs or executions are shown. Graph of Table 14 is represented in Figure 18.Figure 18
Graph of the Table14. Cluster quality of Parallel K-Mean clustering for K = 3.


## 4.4. Comparison of Simple and ParallelK-Mean Algorithms

Simple and Parallel K-Mean algorithms in terms of the number of iterations and comparison of elapsed time is given in the following.


### 4.4.1. Number of Iterations

For different number of clusters (K), performance of the Simple K-Mean and Parallel K-Mean algorithms is shown in Table15.Table 15
Number of iterations for Simple and ParallelK-Means.
KNumber of iterationsSimpleK-Mean clusteringParallelK-Mean clustering2723153495Table15 shows that for different “k” number of clusters, number of iterations is less in Parallel K-Mean algorithm than the Simple K-Mean algorithm. Graph of Table 15 is represented in Figure 19.Figure 19
Graph of Table14. Number of iterations for Simple and Parallel K-Mean algorithms.


### 4.4.2. Elapsed Time

Elapsed time of the SimpleK-Mean and Parallel K-Mean algorithms for k = 2 is shown in Table 16.Table 16
Elapsed time of ParallelK-Mean clustering for k = 2.
K = 2S#Client systemsElapsed time in ms (1stitr + 2nditr)# of data items in cluster 1# of data items in cluster 2Total data items1Client 16.0 + 6.053446610002Client 24.0 + 4.01000010003Client 34.0 + 4.01000010004Client 44.0 + 4.01000010005Client 58.0 + 4.01000010006Client 66.0 + 6.055244810007Client 74.0 + 4.00100010008Client 84.0 + 4.00100010009Client 94.0 + 4.001000100010Client 104.0 + 4.0010001000Total12.05086491410000Table16 shows that the dataset of 10,000 data items is partitioned into 10 sub-datasets for 10 client systems. Clusters are formed in 2 iterations (elapsed time for iterations by all client systems is mentioned in the table). In the first iteration, client 5 has the largest elapsed time, i.e., 8 ms, while in the second iteration, the largest elapsed time is 6 ms, so the total elapsed time of the client systems is 12 ms for the Parallel K-Mean clustering algorithm. Table 17 shows the elapsed time of Simple K-Mean for k = 2.Table 17
Elapsed time of SimpleK-Mean for k = 2.
K = 2S#Elapsed time# of data items in cluster 1# of data items in cluster 2Total data items114.05392460810000This section described the results and their discussion in detail of the proposed research. Experiments were designed to prove that Parallel algorithms are showing significant improvement in the SimpleK-Mean algorithm. Outcomes of the Parallel algorithms are also same, while outcomes of the Simple K-Mean algorithm give different results on every run or execution. Also, total iterations and elapse time is improved in the Parallel algorithms. The next section concludes the completed research work and shows the directions for the future research.


## 4.4.1. Number of Iterations

For different number of clusters (K), performance of the Simple K-Mean and Parallel K-Mean algorithms is shown in Table15.Table 15
Number of iterations for Simple and ParallelK-Means.
KNumber of iterationsSimpleK-Mean clusteringParallelK-Mean clustering2723153495Table15 shows that for different “k” number of clusters, number of iterations is less in Parallel K-Mean algorithm than the Simple K-Mean algorithm. Graph of Table 15 is represented in Figure 19.Figure 19
Graph of Table14. Number of iterations for Simple and Parallel K-Mean algorithms.


## 4.4.2. Elapsed Time

Elapsed time of the SimpleK-Mean and Parallel K-Mean algorithms for k = 2 is shown in Table 16.Table 16
Elapsed time of ParallelK-Mean clustering for k = 2.
K = 2S#Client systemsElapsed time in ms (1stitr + 2nditr)# of data items in cluster 1# of data items in cluster 2Total data items1Client 16.0 + 6.053446610002Client 24.0 + 4.01000010003Client 34.0 + 4.01000010004Client 44.0 + 4.01000010005Client 58.0 + 4.01000010006Client 66.0 + 6.055244810007Client 74.0 + 4.00100010008Client 84.0 + 4.00100010009Client 94.0 + 4.001000100010Client 104.0 + 4.0010001000Total12.05086491410000Table16 shows that the dataset of 10,000 data items is partitioned into 10 sub-datasets for 10 client systems. Clusters are formed in 2 iterations (elapsed time for iterations by all client systems is mentioned in the table). In the first iteration, client 5 has the largest elapsed time, i.e., 8 ms, while in the second iteration, the largest elapsed time is 6 ms, so the total elapsed time of the client systems is 12 ms for the Parallel K-Mean clustering algorithm. Table 17 shows the elapsed time of Simple K-Mean for k = 2.Table 17
Elapsed time of SimpleK-Mean for k = 2.
K = 2S#Elapsed time# of data items in cluster 1# of data items in cluster 2Total data items114.05392460810000This section described the results and their discussion in detail of the proposed research. Experiments were designed to prove that Parallel algorithms are showing significant improvement in the SimpleK-Mean algorithm. Outcomes of the Parallel algorithms are also same, while outcomes of the Simple K-Mean algorithm give different results on every run or execution. Also, total iterations and elapse time is improved in the Parallel algorithms. The next section concludes the completed research work and shows the directions for the future research.


## 5. Conclusion and Future Work

The main problem in the existing technique is the different outcomes for the same data. In this research, both the Simple and Parallel clustering techniques are implemented and analyzed to point out their best features. The ParallelK-Mean algorithms overcome the problems of Simple algorithm and the outcomes of the parallel algorithms are always same, which improves the cluster quality, number of iterations, and elapsed time. Also, for different runs or execution, the outcomes of the Simple K-Mean are different, so the number of iterations are also different for each run or execution. Experiments were designed to prove that Parallel algorithms are showing significant improvement in the Simple K-Mean algorithm. Outcomes of the Parallel algorithms are also same, while outcomes of the Simple K-Mean algorithm give different results on every run or execution. Also, the number of iterations and elapsed time is improved in the Parallel algorithms. Experiments were designed to prove that Parallel algorithms are showing significant improvement in the Simple algorithm. Some other areas in which research can be extended in our future study as mentioned bellow:A method for theK-Mean clustering should be developed, which works for different nature of data. For example, a method should work better for categorical type of data. Selection of “k” number of clusters is an open research area. The Parallel algorithm is just to reduce elapsed time, number of iterations, and also to develop the quality of elapsed time. In the enhanced framework, number of clusters should be input by the user. Other enhanced algorithms can be extended for the selection of “k” number of clusters. The Parallel algorithm has been worked and tested just for the integer’s type of data, which can also be extended for text type of data like words of English language. When a dataset contains different words and all those words are clustered, the same words are placed in the same groups or clusters. A search engine can be introduced using enhanced K-Mean clustering algorithm to search for some specific words in a document.



---

*Source: 9988318-2021-05-17.xml*