# Improvement of K-Means Algorithm and Its Application in Air Passenger Grouping

Authors: Donghua Yu; Shuhua Dong; Shuang Yao
Journal: Computational Intelligence and Neuroscience
 (2022)

---

## Abstract

The k-means is one of the most popular clustering analysis algorithm and widely used in various fields. Nevertheless, it continues to have some shortcomings, for example, extremely sensitive to the initial center points selection and the special points such as noise or outliers. Therefore, this paper proposed initial center points’ selection optimization and phased assignment optimization to improve the k-means algorithm. The experimental results on 15 real-world and 10 synthetic datasets show that the improved k-means outperforms its main competitor k-means++ and under the same setting conditions, namely, using the default parameters,its clustering performance is better than Affinity Propagation, Mean Shift, and DBSCAN. The proposed algorithm was applied to analyze the airline seat selection data to air passengers grouping. The clustering results, as well as absolute deviation rate analysis, realized customer grouping and found out suitable audience group for the recommendation of seat selection services.


---

## Body

## 1. Introduction

Clustering is to divide the dataset into nonoverlapping subsets, such that the objects in the cluster are as similar as possible, and the objects between the clusters are as dissimilar as possible [1]. There are numerous kinds of clustering algorithms, such as AP [2], DPC [3–6], which show excellent clustering performance. However, as one of the most classic clustering algorithm, the k-means aimed to partition the given dataset into K subsets so as to minimize the within-cluster sum of squared distances continues to be one of the most popular clustering algorithms [7]. Its efficiency and simplicity of implementation make it successfully applied in various fields, such as image [8, 9], education [10], bioinformatics [11], medical [12], partial multiview data [13], agricultural data [14], fuzzy decision-making [15].Optimizing the initial center points may be one of the most effective methods to improve the performance of k-means algorithm. The study of Fränti and Sieranoja [16] reported that (a) the k-means clustering algorithm can be significantly improved by using a better initialization technique and by repeating (re-starting) the algorithm; (b) when the data have overlapping clusters, k-means can improve the results of the initialization technique; (c) when the data have well separated clusters, the performance of k-means depends completely on the goodness of the initialization; (d) initialization using simple furthest point heuristic (Maxmin) reduces the clustering error of k-means from 15% to 6%, on average. With the popularity of deep learning in various fields, optimizing data representation is also a means to improve clustering performance, especially in the face of high-dimensional data. The robust deep k-means (RDKM) algorithm [17] exploit the hierarchical information of multiple-level attributes with using the deep structure to hierarchically perform k-means.Thek−means++ [18] provided a simple and effective initial center points optimization method called D2−sampling. It adds new center point one by one and assigns different selection probabilities to each potential center point. Since then, especially after being embedded in scikit-learn as the default k-means algorithm, it has almost become the first choice based on partitioning clustering algorithms. However, due to k-means ++ randomly selects the first center point uniformly and randomly adds subsequent center points according to the probability, some special data distribution can also lead to k-means ++ poor results, even unreasonable clustering results. For example, a dataset with five clusters is synthesized and some noise points half-circle surrounding them are added. The clustering result of k-means ++ was shown in Figure 1, where each color represents a cluster. The desired clustering result should be that the points in the upper left corner are divided into five clusters, but the actual result is that the points in the lower (green points) are clustered into a single cluster to be a wrong result. In this paper, some methods were proposed to solve this problem.Figure 1
Thek−means++ clustering result on synthesized dataset.Cluster analysis is one of the basic methods of data knowledge discovery. With the development of airline business, ancillary services that satisfy passengers’ personal requirement are becoming more and more important for airlines [19, 20]. However, owing to the impact of COVID-19, the airline market faced a dramatic regression (2019–2021), compelling airlines to seek revenue other than from flight tickets [21, 22]. Therefore, establishing ancillary services is significantly important for airlines due to the ability to increase the airline’s revenue. In this paper, the improved k-means algorithm is applied into cluster analysis an airline seat selection dataset, which aims to group airline passengers to serve the establishment of auxiliary services.Based on the above analysis and application requirements, this paper proposed an improved k-means algorithm, called as k-means2o, based on initial center points selection optimization and phased assignment optimization, and realized the clustering analysis on airline seat selection dataset. The main contributions are summarized as follows:(1)
Two optimization methods are proposed for the k-means algorithm: initial center points selection and phased assignment. In the initial center points selection optimization, this method inherits the center point incremental strategy of k-means++ [18], K-MC 2 [23] and AFK-MC 2 [24], but redefines the first center point selection strategy and the subsequent center point incremental strategy. In the phased assignment optimization, the Tukey’s rule is adopted to divide dataset into core and noncore sets to realize two-stage assignment, then two assignment strategies are proposed corresponding to the core and noncore sets, respectively.(2)
Four popular algorithms, k-means++ [18], affinity propagation [2], mean shift [25], and DBSCAN [26], are used to verify the effectiveness and the performance improvement of k-means2o based on 15 real-world and 10 synthetic datasets. Further, the impact of core and noncore sets on the clustering result is analyzed.(3)
The improved k-means algorithm is applied to an airline seat selection dataset, and the passenger groups who are more willing to pay for seat selection are found out. The absolute deviation rateadr is defined to analyze the significance of passenger grouping. This provides valuable information for auxiliary services.


## 2. Related Works

There are many possible ways to optimize the initial center points. The k-means++ [18] provided D2−sampling method which assigns different selection probabilities to each potential center point. Bachem et al. [23] replaced the D2−sampling in k-means ++ with MCMC-sampling and obtained a nearly linear improved k-means algorithm K-MC2. However, this algorithm defines two data-dependent hypothesis αX,βX, which will have an important impact on the clustering result and the algorithm complexity. Subsequently, Bachem et al. [24] solved the hypothesis defect of the K-MC2 algorithm. They extended a regular term based on D2−sampling of k-means ++. This new algorithm is called AFK-MC2. Whether it is K-MC2 or AFK-MC2, they all follow the first center point selection strategy of the k−means++ algorithm, namely that it first samples an initial center uniformly at random. At the same time, they all have similar center point selection methods, that is, a point farther from the currently selected center points has a greater probability of being chosen as the next center point. For more information on the optimization method of the initial center point, please consult the literature [27].Phased assignment, generally speaking, is to divide the data into different stages to complete the cluster label assignment, or assign the cluster labels to only part of the data, and the remaining part will be removed as outliers, noise, etc. Zhou et al. [28] proposed a three-stage k-means algorithm to cluster data and detect outliers. In the first stage, the fuzzy c-means algorithm is applied to cluster the data. In the second stage, local outliers are identified, and the cluster centers are recalculated. In the third stage, certain clusters are merged, and global outliers are identified. Im et al. [29] proposed the NK-means algorithm which emphasizes the removal of noise/outliers and is a two-stage k-means algorithm. In the first stage, a greedy algorithm is utilized to remove abnormal points. In the second stage, the center points are optimized in the constructed core set, and cluster label is assigned to each point. In term of preprocessing techniques, k-means ++ is utilized as an additional filtering step to remove out z of data points as outliers before applying the conventional k-means. The clustering process is only performed on the remaining data which are outlier-free. The outliers data are completely removed and not classified to any known cluster as collected initially. The KMOR algorithm is proposed by Gan and Ng [30] assigns outliers to an additional cluster. This algorithm redefines the clustering objective function and takes into account the SSE between outliers and center points. However, it introduces two new parameters to adjust outlier number. The k-means-sharp is proposed by Olukanmi et al. [31] to eliminate the outliers’ influences from the clusters’ centroid. The detected outliers are completely excluded from the mean measurement only, but they are involved later in the clustering process. However, the data point with all attributes is eliminated completely from centroid measurement. In this case, the algorithm cannot recognize an outlier’s presence in every attribute independently. This is because the single value of the distance metric represents the entire vector instead the single attribute be removed. Therefore, an empty cluster may occur in case of the presence of at least one outlier in each data point [32]. The phased assignment is not only used to optimize the k-means algorithm. For example, Yu et al. [33] also adopted a two-stage assignment strategy based on boundary conditions to optimize the DPC clustering algorithm. For a dataset to be clustered, in many cases, users do not care whether it contains outliers, because the outliers themselves are difficult to define, but they definitely want to assign them cluster labels. Wang et al. [34] proposed an improved integrated clustering learning strategy based on three-stage affinity propagation algorithm with density peak optimization theory (DPKT-AP). In the first stage, the clustering center point was selected by density peak clustering. In the second stage, the k-means algorithm was used to cluster the data samples. In the third stage, DPKT-AP used the AP algorithm to merge and cluster the spherical subgroups.


## 3. Proposed K-Means Algorithm

Suppose a given datasetX=x1,x2,…,xn,xi∈ℝm, and divide it into K mutually disjoint sets C=C1,…,CK, so that ∪iKCi=X and Ci∩Cj=Φ,∀i,j,i≠j.


### 3.1. Initial Center Points Optimization

Like the k-means++ algorithm, the k-means2o adopts a strategy of increasing center points one by one until the desired K points are reached. However, the difference is that the new algorithm redefines the selection of the first center point and subsequent center points. For this purpose, first, define the distance function dx,S between the point x and the set S:(1)dx,S=minxj∈Sdx,xj,where dx,xj represents the distance between two points x,xj. In this paper, Euclidean distance is selected.Letci,i=1,…,K represent the center point of cluster ci,i=1,…,K, then the first center point c1 is selected as follows:(2)c1=1Score∑xi∈Scorexi,where Score represents the number of elements in the core set Score. Then, the (2) shows that c1 is the mean value of the core set Score.LetCk=c1,…,ck represents a set containing k center points, then the selection method of k+1th center point ck+1 is as follows:(3)ck+1=argmaxxi∈Scoredxi,Ck,then Ck+1=Ck∪ck+1. Equation (3) shows that ck+1 is the point farthest from the selected center points in the core set Score. The whole process above is shown in Figure 2.Figure 2
The flow chart of initial center points optimization.


### 3.2. Phased Assignment

The k-means2o is mainly divided into two stages to complete the clustering. The first stage is to assign cluster label to the core setScore, and the second stage is to assign cluster label to the noncore set Snoncore. The Tukey’s rule is adopted to divide the dataset X into sets Score,Snoncore. Tukey’s rule is one of the most robust used techniques for anomaly detection in univariate data [35].In the first stage, the k-means2o establishes the Tukey’s rule for each attribute of the data, and then the judgment results in all dimensions are integrated to determine whether the sample pointx belongs to the core set Score.First, calculate the first quartileQ1 and third quartile Q3 on each attribute:(4)Q1j=xij|i=roundn+1×0.25,Q3j=xij|i=roundn+1×0.75.Then, calculate the upper and lower boundsBupper,Blower as follows:(5)Blowerj=Q1j−r×IQRj,Bupperj=Q3j+r×IQRj,where IQRj=Q3j−Q1j and r is a scale factor.Finally, calculate the core setScore and noncore set Snoncore as follows:(6)Score=xi∈X|Blowerj≤xij≤Bupperj,∀j,Snoncore=X−Score,Equation (6) shows that this paper will evaluate each attribute of the data individually, and then integrate all m attributes to determine whether it belongs to the core set Score. As long as any attribute does not satisfy the inequality constraints, it will be judged as belonging to Snoncore. According to equations (3) and (6), it is obvious that c2 almost will be the point in the noncore set Snoncore, that is, c2∈Snoncore, and ci,i>2 will also select the point in the noncore set Snoncore with a high probability.The scale factorr in equation (5) is a predefined adjustable parameter. If you have sufficient prior knowledge of dataset, you can set it depending on experience. If not, it recommends to set r=1.5. Although in the field of anomaly detection research, r=1.5 is often regarded as the boundary value of the outlier. In cluster analysis, points in Snoncore cannot be regarded as outliers and discarded, and they still need to be assigned cluster labels. Whether points in Score or in Snoncore, in the final clustering result, it is necessary to assign cluster labels which are also one of the goals of cluster analysis. On the 15 real datasets in this paper, each sample has an exact class label, but the Snoncore of almost all datasets are not empty. After constructing Score, it is more helpful to obtain a more excellent initial center points. Not only that Score effectively assists the selection of the initial center points but also has a positive effect on the update of center points.When we obtainScore, use the initial center points selection method described in Section 3.1 to select the initial center points set CK from Score, and then use the traditional center points update method of k-means to complete clustering in Score. Obtain the optimal clustering center points set C^K and clusters C¯1,…,C¯K. The first stage of clustering ends.(7)xi∈C¯k⇔dxi,C^K=dxi,c^k,xi∈Score.In the second stage, points inSnoncore will be assigned cluster label. With the help of the optimal clusters C¯1,…,C¯K obtained in the first stage, determine the cluster label of ∀xi∈Snoncore:(8)xi∈Ck⇔dxi,Score=dxi,C¯k,xi∈Snoncore,where dxi,Score,dxi,C¯k are defined in (1), and Ck is the k−tk cluster.The whole process above is shown in Figure3.Figure 3
The flow chart of phased assignment.


### 3.3. Algorithm Flow and Complexity Analysis

The k-means2o algorithm that optimizes the initial center points selection and phased assignment are performed. The algorithm 1 shows its detail process. The steps 1–15 corresponds to the first stage, including that the Step 1 determinesScore,Snoncore, and the Steps 2–4 optimize the initial center points. The Steps 16–19 correspond to the second stage.Algorithm 1: k-means2o.
Input: DatasetX, cluster number K, scale factor rOutput: Clustering resultsC=C1,…,CK, center points set C^K, sum of squared error SSE(1)
Using (6) divide dataset X into Score,Snoncore(2)
Using (2) generate c1(3)
Fori=2 to K do(4)
Using (3) generate ci(5)
End for(6)
Forj=1 to max_iter do(7)
for∀x∈Score do(8)
According to the principle of the nearest distance betweenx and CK, classify x into the corresponding cluster(9)
end for(10)
ifSSE does not change then(11)
break(12)
end if(13)
end for(14)
Update the center points setCK and compute SSE(15)
Compute the optimal center pointsC^K(16)
for∀x∈Snoncore do(17)
According to the principle of the nearest distance betweenx and Score, classify x into the corresponding cluster(18)
end for(19)
ComputeSSE(20)
Return clustering resultsC=C1,…,CK, center points set C^K, sum of squared error SSEAccording to the detailed steps in algorithm 1, the complexity of k-means2o algorithm is analyzed with data sizen, attribute m, and cluster number K. The number of iterations is denoted as t, and its maximum value is max_iter. Step 1 generates Score,Snoncore with Onm. Steps 2–5 select initial center points with OnK. Steps 6–13 are a traditional k-means clustering process; however, Step 8 is a new label assignment strategy, so the complexity of these steps becomes On2t. In summary, the complexity of the k-means2o algorithm is On2t.


## 3.1. Initial Center Points Optimization

Like the k-means++ algorithm, the k-means2o adopts a strategy of increasing center points one by one until the desired K points are reached. However, the difference is that the new algorithm redefines the selection of the first center point and subsequent center points. For this purpose, first, define the distance function dx,S between the point x and the set S:(1)dx,S=minxj∈Sdx,xj,where dx,xj represents the distance between two points x,xj. In this paper, Euclidean distance is selected.Letci,i=1,…,K represent the center point of cluster ci,i=1,…,K, then the first center point c1 is selected as follows:(2)c1=1Score∑xi∈Scorexi,where Score represents the number of elements in the core set Score. Then, the (2) shows that c1 is the mean value of the core set Score.LetCk=c1,…,ck represents a set containing k center points, then the selection method of k+1th center point ck+1 is as follows:(3)ck+1=argmaxxi∈Scoredxi,Ck,then Ck+1=Ck∪ck+1. Equation (3) shows that ck+1 is the point farthest from the selected center points in the core set Score. The whole process above is shown in Figure 2.Figure 2
The flow chart of initial center points optimization.


## 3.2. Phased Assignment

The k-means2o is mainly divided into two stages to complete the clustering. The first stage is to assign cluster label to the core setScore, and the second stage is to assign cluster label to the noncore set Snoncore. The Tukey’s rule is adopted to divide the dataset X into sets Score,Snoncore. Tukey’s rule is one of the most robust used techniques for anomaly detection in univariate data [35].In the first stage, the k-means2o establishes the Tukey’s rule for each attribute of the data, and then the judgment results in all dimensions are integrated to determine whether the sample pointx belongs to the core set Score.First, calculate the first quartileQ1 and third quartile Q3 on each attribute:(4)Q1j=xij|i=roundn+1×0.25,Q3j=xij|i=roundn+1×0.75.Then, calculate the upper and lower boundsBupper,Blower as follows:(5)Blowerj=Q1j−r×IQRj,Bupperj=Q3j+r×IQRj,where IQRj=Q3j−Q1j and r is a scale factor.Finally, calculate the core setScore and noncore set Snoncore as follows:(6)Score=xi∈X|Blowerj≤xij≤Bupperj,∀j,Snoncore=X−Score,Equation (6) shows that this paper will evaluate each attribute of the data individually, and then integrate all m attributes to determine whether it belongs to the core set Score. As long as any attribute does not satisfy the inequality constraints, it will be judged as belonging to Snoncore. According to equations (3) and (6), it is obvious that c2 almost will be the point in the noncore set Snoncore, that is, c2∈Snoncore, and ci,i>2 will also select the point in the noncore set Snoncore with a high probability.The scale factorr in equation (5) is a predefined adjustable parameter. If you have sufficient prior knowledge of dataset, you can set it depending on experience. If not, it recommends to set r=1.5. Although in the field of anomaly detection research, r=1.5 is often regarded as the boundary value of the outlier. In cluster analysis, points in Snoncore cannot be regarded as outliers and discarded, and they still need to be assigned cluster labels. Whether points in Score or in Snoncore, in the final clustering result, it is necessary to assign cluster labels which are also one of the goals of cluster analysis. On the 15 real datasets in this paper, each sample has an exact class label, but the Snoncore of almost all datasets are not empty. After constructing Score, it is more helpful to obtain a more excellent initial center points. Not only that Score effectively assists the selection of the initial center points but also has a positive effect on the update of center points.When we obtainScore, use the initial center points selection method described in Section 3.1 to select the initial center points set CK from Score, and then use the traditional center points update method of k-means to complete clustering in Score. Obtain the optimal clustering center points set C^K and clusters C¯1,…,C¯K. The first stage of clustering ends.(7)xi∈C¯k⇔dxi,C^K=dxi,c^k,xi∈Score.In the second stage, points inSnoncore will be assigned cluster label. With the help of the optimal clusters C¯1,…,C¯K obtained in the first stage, determine the cluster label of ∀xi∈Snoncore:(8)xi∈Ck⇔dxi,Score=dxi,C¯k,xi∈Snoncore,where dxi,Score,dxi,C¯k are defined in (1), and Ck is the k−tk cluster.The whole process above is shown in Figure3.Figure 3
The flow chart of phased assignment.


## 3.3. Algorithm Flow and Complexity Analysis

The k-means2o algorithm that optimizes the initial center points selection and phased assignment are performed. The algorithm 1 shows its detail process. The steps 1–15 corresponds to the first stage, including that the Step 1 determinesScore,Snoncore, and the Steps 2–4 optimize the initial center points. The Steps 16–19 correspond to the second stage.Algorithm 1: k-means2o.
Input: DatasetX, cluster number K, scale factor rOutput: Clustering resultsC=C1,…,CK, center points set C^K, sum of squared error SSE(1)
Using (6) divide dataset X into Score,Snoncore(2)
Using (2) generate c1(3)
Fori=2 to K do(4)
Using (3) generate ci(5)
End for(6)
Forj=1 to max_iter do(7)
for∀x∈Score do(8)
According to the principle of the nearest distance betweenx and CK, classify x into the corresponding cluster(9)
end for(10)
ifSSE does not change then(11)
break(12)
end if(13)
end for(14)
Update the center points setCK and compute SSE(15)
Compute the optimal center pointsC^K(16)
for∀x∈Snoncore do(17)
According to the principle of the nearest distance betweenx and Score, classify x into the corresponding cluster(18)
end for(19)
ComputeSSE(20)
Return clustering resultsC=C1,…,CK, center points set C^K, sum of squared error SSEAccording to the detailed steps in algorithm 1, the complexity of k-means2o algorithm is analyzed with data sizen, attribute m, and cluster number K. The number of iterations is denoted as t, and its maximum value is max_iter. Step 1 generates Score,Snoncore with Onm. Steps 2–5 select initial center points with OnK. Steps 6–13 are a traditional k-means clustering process; however, Step 8 is a new label assignment strategy, so the complexity of these steps becomes On2t. In summary, the complexity of the k-means2o algorithm is On2t.


## 4. Performance Analysis of the Proposed Algorithm

In this section, the improved k-means algorithm, k-means2o, testing and verification for clustering performance compared with the well-known k-means++ [18] which is the most commonly used partition-based algorithm with different initializations of the centroids to reduce the sensitivity. Then, the performance of the k-means2o will be compared with affinity propagation (AP) [2], mean shift (MS) [25], DBSCAN [26]. Although the latter obtain excellent clustering performance on some special datasets, they require to preset one or more important parameter(s), which is a very difficult task. The k-means2o is designed with Python and k-means ++, AP, MS, DBSCAN are called from scikit-learn [36].


### 4.1. Datasets and Evaluation Metrics

A total of 15 real-world datasets used in the experiments were taken from UCI [37]. The data size n, attribute m, and cluster number K are summarized in Table 1 and Table 2 shows 10 synthetic datasets from references [38, 39], where the K1 dataset is synthesized by this paper, see Figure 1. All datasets are publicly available1.Table 1
Real-world datasets.
DatasetnmKDatasetnmKBreast-cancer569302Banknote137242Bupa34562Compound39926Ct221362Hayes-roth13253Iris15043Libras3609015Parkinsons195222Penbased109921610Vowel9901011Waveform215000213Waveform405000403Wdbc569302Wine178133Table 2
Synthetic datasets.
DatasetnmKDatasetnmKAggregation78827circlesA330023D313100231Flame24022Jain37322K126225R15600215S15000215S35000215Spiral31223An appropriate and uniform evaluation index is both required and meaningful to compare the different clustering algorithms. Therefore, the quality was measured via the accuracy (ACC), the Adjusted Rand Index (ARI) [40], the Normalized Mutual Information (NMI) [41] and the Fowlkes–Mallows Index (FMI) [42] between the produced clusters and the truth categories. Larger evaluation index values indicate improved clustering performance, and all index upper bounds =1, representing perfectly correct clustering:(9)ACC=∑i=1nδlabel_true,maplabel_predn,ARI=RI−ERImaxRI−ERI,NMI=MIU,VmeanHU,HV,FMI=TPTP+FPTP+FN.where U,V are predicted label and true label.


### 4.2. Experimental Results and Discussion

The experimental datasets were clustered using k-means++ and k-means2o. The ACC, ARI, NMI, and FMI of them are listed in Tables 3 and 4, where k-++ represents k-means ++ and k-2o represents k-means2o. The best clustering performance evaluation values are shown in bold, and 1 means that the clustering result is completely correct. The value 0.0000 in the table represents its real metric value <0.0001.Table 3
Clustering results of k-means++ and k-means2o on real-world datasets.
DatasetACCARINMIFMIk-++k-2ok-++k-2ok-++k-2ok-++k-2oBreast-cancer0.85410.89100.49140.60620.46470.52760.79150.8286Banknote0.61220.59540.04850.03560.03030.02390.55170.5231Bupa0.85500.57680.00000.00580.00000.01120.61920.5136Compound0.65660.63650.53780.50430.71910.65570.64220.6181Ct0.82350.83250.41600.43990.32960.34850.70780.7199Hayes–Roth0.43930.44690.02020.02260.02870.03170.35010.3519Iris0.89330.89330.73020.73020.75810.75810.82080.8208Libras0.42770.44160.31990.27600.60660.57160.37340.3389Parkinsons0.72300.63070.00000.06250.00000.04930.74440.5889Penbased0.76740.60350.59920.49070.69270.67230.64120.5582Vowel0.36360.36450.20280.22040.41410.43370.27890.2868Waveform210.50160.50180.25360.25470.36220.36540.50390.5047Waveform400.51460.51600.25160.25300.50230.50350.36050.3632Wdbc0.85410.89100.49140.60620.46470.52760.79150.8286Wine0.70220.70220.37110.36750.42870.41640.58350.5809Maximum71061061088The best clustering performance evaluation values are shown in bold.Table 4
Clustering results of k-means++ and k-means2o on synthetic datasets.
DatasetACCARINMIFMIk-++k-2ok-++k-2ok-++k-2ok-++k-2oAggregation0.78550.86800.76240.74380.87920.83730.81590.7992CirclesA30.58330.58660.12830.13110.36160.36330.49030.4915D310.97640.92900.95220.90590.96690.94980.95380.9090Flame0.83750.83750.45340.45340.39870.39870.73630.7363Jain0.78550.78550.32410.32410.36900.36900.70050.7005K10.78240.99230.73180.98090.81600.97650.79620.9847R150.99660.99660.99270.99270.99420.99420.99320.9932S10.99380.99360.98670.98630.98660.98610.98760.9872S30.85680.85680.72700.72700.79590.79620.74530.7453Spiral0.34610.34610.00000.00000.00070.00050.32760.3277Maximum78877677The best clustering performance evaluation values are shown in bold.From Table3, the k-means ++ and k-means2o simultaneously obtained the maximum FMI value for 8 of the 15 datasets. This shows that the two algorithms have the same performance, and further performance comparison and analysis of other evaluation indicators are required. From the view of ARI in Table 3, the most significant and direct conclusion is that the k-means2o outperforms the k-means ++ on most datasets, and the performance of the two algorithms is also very close on a few datasets that are inferior to k-means ++. Specifically, the k-means2o achieved the maximum ARI value for 10 of the 15 datasets, as well as the NMI and it obtained the same result, and the k-means ++ achieved the best clustering performance only on 6 datasets in ARI, as well as in NMI. For banknote, iris, wine datasets, the k-means2o is only inferior to k-means ++ with a small gap. For ACC evaluation, it comes to the exact same conclusion as NMI and ARI, that is, the k-means2o clustering performance is better than the k-means ++.For the synthetic datasets in Table2, the four evaluation metrics in Table 4 show that k-means ++ and k-means2o have similar clustering performance. For datasets with spherical cluster distribution, such as D31, R15, S1, and S3, the clustering results of the two algorithms are close to the real cluster partition, while for datasets with nonspherical distribution such as spiral, flame, circlesA3, the clustering performance of them drops sharply. When the size of the distribution area of spherical clusters is significantly different, the performance difference between k-means ++ and k-means2o can be revealed. For example, in the aggregation dataset, the two algorithms’ clustering results are shown in Figure 4. The evaluation values of ARI, NMI, and FMI all show that k-means ++ is better than k-means2o, but ACC gives the opposite conclusion. Figure 4(a) shows that k-means ++ selects seven center points in six real clusters, and two different clusters (green points in the figure) are wrongly classified into the same cluster. Figure 4(b) shows that k-means2o can select center points in seven real clusters, respectively.Figure 4
Clustering results on aggregation dataset: (a) k-means++; (b) k-means2o.
(a)(b)Further, the performance of the k-means2o will be compared with AP, MS, and DBSCAN. The ARI and NMI of these algorithms are listed in Table5, and the ACC and FMI are listed in Table 6. The values larger than the one of the k-means2o are marked in bold. The three comparison algorithms all use default parameters. Considering better performance, the data are normalized here. From the perspective of ARI values, compared with AP, MS, and DBSACN, the k-means2o obtained better clustering performance on 12,14,13 datasets, respectively. The evaluation results of NMI are similar to ARI, except for the AP algorithm. The AP’s measurement results of NMI and ARI are very different, which may be tied to the number of error clusters given by the AP algorithm. The ACC evaluation conclusion is consistent with ARI, but FMI and NMI reach opposite conclusions. For the MS algorithm, its FMI value is better than k-means2o algorithm in 9 out of 15 datasets, while for the AP algorithm, its FMI value on all datasets is smaller than k-means2o algorithm. Based on the four evaluation metrics, the k-means2o algorithm is superior to the comparison methods in at least three of these metrics on most datasets. Therefore, k-means2o has better clustering performance.Table 5
ARI and NMI evaluation results on real-world datasets with AP, MS, DBSCAN.
DatasetARINMIAPMSDBSCANk-2oAPMSDBSCANk-2oBreast-cancer0.05740.22750.06870.60620.26920.24390.04150.5276Banknote0.04910.00000.00000.03560.29730.00000.00000.0239Bupa0.00000.00000.00370.00580.02870.02370.01300.0112Compound0.30230.71890.00000.41330.62890.76920.00000.6240Ct0.10060.00000.32710.43990.25290.06010.25630.3485Hayes-Roth0.03500.00000.05890.02260.20100.00000.11680.0317Iris0.33810.56810.00000.73020.57060.73360.00000.7581Libras0.28820.00000.00580.27600.63750.00000.14490.5716Parkinsons0.03050.00000.00000.06250.18890.06410.02270.0493Penbased0.10370.00000.00080.49070.59290.00000.03800.6723Vowel0.13150.00000.00000.22040.55250.00000.00000.4337Waveform210.01680.00000.00000.25470.23450.00000.00030.3654Waveform400.01870.00000.00000.25300.20520.00000.00000.3632Wdbc0.05740.22750.06870.60620.26920.24390.04150.5276Wine0.26890.00000.42280.36750.52640.00000.52630.4164Number312—821—Table 6
ACC and FMI evaluation results on real-world datasets with AP, MS, DBSCAN.
DatasetACCFMIAPMSDBSCANk-2oAPMSDBSCANk-2oBreast-cancer0.13530.71530.66260.89100.24910.71170.67750.8286Banknote0.10130.55540.55540.59540.22300.71120.71120.5231Bupa0.08410.51880.99130.57680.15400.62240.70730.5136Compound0.35840.73930.39600.63650.45300.81590.49720.6181Ct0.21720.49770.78730.83250.32670.67240.66330.7199Hayes-Roth0.15150.38640.35610.44690.19810.58760.34360.3519Iris0.41330.66670.33330.89330.51450.77150.57350.8208Libras0.38890.06670.12780.44160.33330.25310.24290.3389Parkinsons0.15900.65130.61540.63070.24650.68570.64360.5889Penbased0.10180.10410.11950.60350.24160.31640.30800.5582Vowel0.16570.09090.09090.36450.22660.30000.30000.2868Waveform210.03680.33920.33740.50180.10670.57730.56130.5047Waveform400.06500.33840.33840.51600.11240.57730.57730.5035Wdbc0.13530.71530.66260.89100.24910.71170.67750.8286Wine0.34270.39890.69660.70220.46040.58130.64820.5809Number021—097—As for the abnormal conclusion given by a certain evaluation metric for a specific algorithm, for example, the NMI evaluation metric for the AP algorithm, the FMI evaluation metric for the MS algorithm, it may be caused by too many or too few clusters. Table7 shows that the AP and MS algorithms give the wrong number of clusters on any datasets, and the former far exceeds the true number of clusters, while the latter divides more than half of the datasets into one cluster. Undeniably, the AP, MS, and DBSCAN algorithms provide a method to identify the number of clusters. If the parameters for the AP algorithm, damping factor, and preference value are carefully adjusted, it maybe achieves better clustering performance in these real-world datasets. In those clustering algorithms that contain parameters, careful selection of parameters is often time-consuming and requires prior knowledge. Therefore, these algorithms have poor universality.Table 7
The number of real and 3 algorithms predicted clusters in the real-world datasets.
DatasetAPMSDBSCANRealBreast-cancer431222Bupa321422Ct20722Iris9213Parkinsons21522Vowel851111Waveform40157113Wine14133Banknote45112Compound15316Hayes-roth16143Libras301615Penbased1991710Waveform21148123Wdbc431222The performance of all five algorithms can be directly compared in Figure5. In this radar chart, each axis represents a dataset, and its value is the cluster evaluation ARI value. According to the previous analysis, the k-means2o has the best performance, and its corresponding red line in the radar chart reaches the maximum value on more polar axes, that is, farther away from the center point.Figure 5
Radar chart of ARI values on the real-world datasets.


### 4.3. Comparative Analysis of Different Initialization Methods

In this subsection, the effects of three different initialization methods on the performance of the k-means clustering algorithm are compared. These three methods are represented byRandom, D2-sampling, New respectively, see the header of Table 8. Random means randomly initializing the center point. D2-sampling means assigning a selection probability to each noncenter point and randomly selecting the center point. New means the center point initialization optimization method proposed in this paper. In fact, the k-means algorithm based on D2-sampling is the famous k-means ++ algorithm.Table 8
Results of different initialization methods of k-means algorithm.
DatasetARINMIRandomD2-SamplingNewRandomD2-SamplingNewBreast-cancer0.49140.49140.49140.49140.49140.4914Banknote0.04850.04850.04850.04850.04850.0485Bupa0.00000.00000.00000.00000.00010.0001Compound0.53280.53780.41330.72200.71910.6240Ct0.41600.41600.00000.32960.32960.0219Hayes-Roth0.01600.02020.02020.02500.02870.0287Iris0.73020.73020.73020.75810.75810.7581Libras0.30620.31990.28680.58960.60660.5767Parkinsons0.08530.00000.00010.05050.00010.0001Penbased0.54420.59920.42650.68350.69270.6486Vowel0.21800.20280.20580.43320.41410.4067Waveform210.25360.25360.25350.36220.36220.3622Waveform400.25160.25160.25150.36050.36050.3605Wdbc0.49140.49140.49140.46470.46470.4647Wine0.37110.37110.37110.42870.42870.4287Maximum1113711129The initial center points optimization plays an important role in the performance improvement of k-means2o. However, Table8 shows that only using the initialization method proposed in this paper cannot improve the clustering performance. From the evaluation value of ARI, the optimal initialization method is D2-sampling, followed by Random, and the worst is New which is the initialization method proposed in this paper. Except for tiny numerical differences on individual datasets, the NMI evaluation shows similar conclusions. Combined with the conclusion of k-means2o performance improvement, it is the combination of initial center point optimization and phased assignment that improves the performance of k-means2o, not just the center points optimization.


### 4.4. Impact Analysis of Core and Noncore Sets

This paper uses Tukey’s rule to realize the division ofScore and Snoncore. Therefore, a scale factor r needs to be given. Tukey’s rule comes from the field of anomaly detection. Generally, the scale factor is set to 1.5. Points that do not meet the conditions of the scale factor are called outliers. In most cases, these points are directly abandoned. This idea is introduced into cluster analysis and used in the data preprocessing stage. As a result, the points detected as abnormal will be discarded and not assign cluster label. There will be great hidden trouble in this way. Table 9 shows the number of elements in Score and Snoncore in 15 real-world datasets when r=1.5. Except that the Snoncore of compound dataset is empty, the Snoncore of the remaining 14 datasets are not empty. However, as well as we known, all points in these datasets are labeled with class labels. Therefore, it is unreasonable to abandon these suspected outliers simply and rudely. For this reason, this paper proposes a two-stage assignment method, whose first stage assigns cluster label to the points in Score and second stage assigns the points in the Snoncore. For the compound dataset, the empty Snoncore indicates that Tukey’s rule has no effect on this dataset and will directly lead to the failure of the second stage assignment.Table 9
The number of core and noncore subsets elementsScore,Snoncore in k-means2o clustering.
DatasetScoreSnoncoreDatasetScoreSnoncoreBreast-cancer398171Banknote128092Bupa28065Compound3990Ct16457Hayes-roth10230Iris1464Libras3564Parkinsons14847Penbased10482510Vowel96030waveform214740260Waveform404116884Wdbc398171Wine16117The k-means2o algorithm relies on a predefined scale factorr, so it is necessary to perform a sensitivity test of this parameter. Therefore, we took the iris, wine, breast_cancer, banknote, and bupa datasets as an example to investigate the effects of different r on ARI and NMI, as shown in Figure 6. Its shows that the ARI and NMI curves of the five datasets do not fluctuate drastically, so the clustering performance of the k-means2o algorithm based on the scale factor r is relatively robust. Nevertheless, the scale factor r still has a slight impact on the clustering performance. For example, in the iris dataset, when r=0.5, its ARI and NMI values reach 0.8340 and 0.8191, respectively. This clustering result is better than k-means ++, see Table 3 (the values are ARI =0.7302 and NMI =0.7581).Figure 6
Clustering evaluation for differentr on five datasets: (a) ARI curve and (b) NMI curve.
(a)(b)In the above analysis, the k-means2o outperforms k-means++, AP, MS, and DBSCAN. Combined with the fact, almost all Snoncore of these datasets in Table 9 are nonempty. These results show that the combination optimization of the initial center point and the core subset works and improves the k-means clustering performance.


## 4.1. Datasets and Evaluation Metrics

A total of 15 real-world datasets used in the experiments were taken from UCI [37]. The data size n, attribute m, and cluster number K are summarized in Table 1 and Table 2 shows 10 synthetic datasets from references [38, 39], where the K1 dataset is synthesized by this paper, see Figure 1. All datasets are publicly available1.Table 1
Real-world datasets.
DatasetnmKDatasetnmKBreast-cancer569302Banknote137242Bupa34562Compound39926Ct221362Hayes-roth13253Iris15043Libras3609015Parkinsons195222Penbased109921610Vowel9901011Waveform215000213Waveform405000403Wdbc569302Wine178133Table 2
Synthetic datasets.
DatasetnmKDatasetnmKAggregation78827circlesA330023D313100231Flame24022Jain37322K126225R15600215S15000215S35000215Spiral31223An appropriate and uniform evaluation index is both required and meaningful to compare the different clustering algorithms. Therefore, the quality was measured via the accuracy (ACC), the Adjusted Rand Index (ARI) [40], the Normalized Mutual Information (NMI) [41] and the Fowlkes–Mallows Index (FMI) [42] between the produced clusters and the truth categories. Larger evaluation index values indicate improved clustering performance, and all index upper bounds =1, representing perfectly correct clustering:(9)ACC=∑i=1nδlabel_true,maplabel_predn,ARI=RI−ERImaxRI−ERI,NMI=MIU,VmeanHU,HV,FMI=TPTP+FPTP+FN.where U,V are predicted label and true label.


## 4.2. Experimental Results and Discussion

The experimental datasets were clustered using k-means++ and k-means2o. The ACC, ARI, NMI, and FMI of them are listed in Tables 3 and 4, where k-++ represents k-means ++ and k-2o represents k-means2o. The best clustering performance evaluation values are shown in bold, and 1 means that the clustering result is completely correct. The value 0.0000 in the table represents its real metric value <0.0001.Table 3
Clustering results of k-means++ and k-means2o on real-world datasets.
DatasetACCARINMIFMIk-++k-2ok-++k-2ok-++k-2ok-++k-2oBreast-cancer0.85410.89100.49140.60620.46470.52760.79150.8286Banknote0.61220.59540.04850.03560.03030.02390.55170.5231Bupa0.85500.57680.00000.00580.00000.01120.61920.5136Compound0.65660.63650.53780.50430.71910.65570.64220.6181Ct0.82350.83250.41600.43990.32960.34850.70780.7199Hayes–Roth0.43930.44690.02020.02260.02870.03170.35010.3519Iris0.89330.89330.73020.73020.75810.75810.82080.8208Libras0.42770.44160.31990.27600.60660.57160.37340.3389Parkinsons0.72300.63070.00000.06250.00000.04930.74440.5889Penbased0.76740.60350.59920.49070.69270.67230.64120.5582Vowel0.36360.36450.20280.22040.41410.43370.27890.2868Waveform210.50160.50180.25360.25470.36220.36540.50390.5047Waveform400.51460.51600.25160.25300.50230.50350.36050.3632Wdbc0.85410.89100.49140.60620.46470.52760.79150.8286Wine0.70220.70220.37110.36750.42870.41640.58350.5809Maximum71061061088The best clustering performance evaluation values are shown in bold.Table 4
Clustering results of k-means++ and k-means2o on synthetic datasets.
DatasetACCARINMIFMIk-++k-2ok-++k-2ok-++k-2ok-++k-2oAggregation0.78550.86800.76240.74380.87920.83730.81590.7992CirclesA30.58330.58660.12830.13110.36160.36330.49030.4915D310.97640.92900.95220.90590.96690.94980.95380.9090Flame0.83750.83750.45340.45340.39870.39870.73630.7363Jain0.78550.78550.32410.32410.36900.36900.70050.7005K10.78240.99230.73180.98090.81600.97650.79620.9847R150.99660.99660.99270.99270.99420.99420.99320.9932S10.99380.99360.98670.98630.98660.98610.98760.9872S30.85680.85680.72700.72700.79590.79620.74530.7453Spiral0.34610.34610.00000.00000.00070.00050.32760.3277Maximum78877677The best clustering performance evaluation values are shown in bold.From Table3, the k-means ++ and k-means2o simultaneously obtained the maximum FMI value for 8 of the 15 datasets. This shows that the two algorithms have the same performance, and further performance comparison and analysis of other evaluation indicators are required. From the view of ARI in Table 3, the most significant and direct conclusion is that the k-means2o outperforms the k-means ++ on most datasets, and the performance of the two algorithms is also very close on a few datasets that are inferior to k-means ++. Specifically, the k-means2o achieved the maximum ARI value for 10 of the 15 datasets, as well as the NMI and it obtained the same result, and the k-means ++ achieved the best clustering performance only on 6 datasets in ARI, as well as in NMI. For banknote, iris, wine datasets, the k-means2o is only inferior to k-means ++ with a small gap. For ACC evaluation, it comes to the exact same conclusion as NMI and ARI, that is, the k-means2o clustering performance is better than the k-means ++.For the synthetic datasets in Table2, the four evaluation metrics in Table 4 show that k-means ++ and k-means2o have similar clustering performance. For datasets with spherical cluster distribution, such as D31, R15, S1, and S3, the clustering results of the two algorithms are close to the real cluster partition, while for datasets with nonspherical distribution such as spiral, flame, circlesA3, the clustering performance of them drops sharply. When the size of the distribution area of spherical clusters is significantly different, the performance difference between k-means ++ and k-means2o can be revealed. For example, in the aggregation dataset, the two algorithms’ clustering results are shown in Figure 4. The evaluation values of ARI, NMI, and FMI all show that k-means ++ is better than k-means2o, but ACC gives the opposite conclusion. Figure 4(a) shows that k-means ++ selects seven center points in six real clusters, and two different clusters (green points in the figure) are wrongly classified into the same cluster. Figure 4(b) shows that k-means2o can select center points in seven real clusters, respectively.Figure 4
Clustering results on aggregation dataset: (a) k-means++; (b) k-means2o.
(a)(b)Further, the performance of the k-means2o will be compared with AP, MS, and DBSCAN. The ARI and NMI of these algorithms are listed in Table5, and the ACC and FMI are listed in Table 6. The values larger than the one of the k-means2o are marked in bold. The three comparison algorithms all use default parameters. Considering better performance, the data are normalized here. From the perspective of ARI values, compared with AP, MS, and DBSACN, the k-means2o obtained better clustering performance on 12,14,13 datasets, respectively. The evaluation results of NMI are similar to ARI, except for the AP algorithm. The AP’s measurement results of NMI and ARI are very different, which may be tied to the number of error clusters given by the AP algorithm. The ACC evaluation conclusion is consistent with ARI, but FMI and NMI reach opposite conclusions. For the MS algorithm, its FMI value is better than k-means2o algorithm in 9 out of 15 datasets, while for the AP algorithm, its FMI value on all datasets is smaller than k-means2o algorithm. Based on the four evaluation metrics, the k-means2o algorithm is superior to the comparison methods in at least three of these metrics on most datasets. Therefore, k-means2o has better clustering performance.Table 5
ARI and NMI evaluation results on real-world datasets with AP, MS, DBSCAN.
DatasetARINMIAPMSDBSCANk-2oAPMSDBSCANk-2oBreast-cancer0.05740.22750.06870.60620.26920.24390.04150.5276Banknote0.04910.00000.00000.03560.29730.00000.00000.0239Bupa0.00000.00000.00370.00580.02870.02370.01300.0112Compound0.30230.71890.00000.41330.62890.76920.00000.6240Ct0.10060.00000.32710.43990.25290.06010.25630.3485Hayes-Roth0.03500.00000.05890.02260.20100.00000.11680.0317Iris0.33810.56810.00000.73020.57060.73360.00000.7581Libras0.28820.00000.00580.27600.63750.00000.14490.5716Parkinsons0.03050.00000.00000.06250.18890.06410.02270.0493Penbased0.10370.00000.00080.49070.59290.00000.03800.6723Vowel0.13150.00000.00000.22040.55250.00000.00000.4337Waveform210.01680.00000.00000.25470.23450.00000.00030.3654Waveform400.01870.00000.00000.25300.20520.00000.00000.3632Wdbc0.05740.22750.06870.60620.26920.24390.04150.5276Wine0.26890.00000.42280.36750.52640.00000.52630.4164Number312—821—Table 6
ACC and FMI evaluation results on real-world datasets with AP, MS, DBSCAN.
DatasetACCFMIAPMSDBSCANk-2oAPMSDBSCANk-2oBreast-cancer0.13530.71530.66260.89100.24910.71170.67750.8286Banknote0.10130.55540.55540.59540.22300.71120.71120.5231Bupa0.08410.51880.99130.57680.15400.62240.70730.5136Compound0.35840.73930.39600.63650.45300.81590.49720.6181Ct0.21720.49770.78730.83250.32670.67240.66330.7199Hayes-Roth0.15150.38640.35610.44690.19810.58760.34360.3519Iris0.41330.66670.33330.89330.51450.77150.57350.8208Libras0.38890.06670.12780.44160.33330.25310.24290.3389Parkinsons0.15900.65130.61540.63070.24650.68570.64360.5889Penbased0.10180.10410.11950.60350.24160.31640.30800.5582Vowel0.16570.09090.09090.36450.22660.30000.30000.2868Waveform210.03680.33920.33740.50180.10670.57730.56130.5047Waveform400.06500.33840.33840.51600.11240.57730.57730.5035Wdbc0.13530.71530.66260.89100.24910.71170.67750.8286Wine0.34270.39890.69660.70220.46040.58130.64820.5809Number021—097—As for the abnormal conclusion given by a certain evaluation metric for a specific algorithm, for example, the NMI evaluation metric for the AP algorithm, the FMI evaluation metric for the MS algorithm, it may be caused by too many or too few clusters. Table7 shows that the AP and MS algorithms give the wrong number of clusters on any datasets, and the former far exceeds the true number of clusters, while the latter divides more than half of the datasets into one cluster. Undeniably, the AP, MS, and DBSCAN algorithms provide a method to identify the number of clusters. If the parameters for the AP algorithm, damping factor, and preference value are carefully adjusted, it maybe achieves better clustering performance in these real-world datasets. In those clustering algorithms that contain parameters, careful selection of parameters is often time-consuming and requires prior knowledge. Therefore, these algorithms have poor universality.Table 7
The number of real and 3 algorithms predicted clusters in the real-world datasets.
DatasetAPMSDBSCANRealBreast-cancer431222Bupa321422Ct20722Iris9213Parkinsons21522Vowel851111Waveform40157113Wine14133Banknote45112Compound15316Hayes-roth16143Libras301615Penbased1991710Waveform21148123Wdbc431222The performance of all five algorithms can be directly compared in Figure5. In this radar chart, each axis represents a dataset, and its value is the cluster evaluation ARI value. According to the previous analysis, the k-means2o has the best performance, and its corresponding red line in the radar chart reaches the maximum value on more polar axes, that is, farther away from the center point.Figure 5
Radar chart of ARI values on the real-world datasets.


## 4.3. Comparative Analysis of Different Initialization Methods

In this subsection, the effects of three different initialization methods on the performance of the k-means clustering algorithm are compared. These three methods are represented byRandom, D2-sampling, New respectively, see the header of Table 8. Random means randomly initializing the center point. D2-sampling means assigning a selection probability to each noncenter point and randomly selecting the center point. New means the center point initialization optimization method proposed in this paper. In fact, the k-means algorithm based on D2-sampling is the famous k-means ++ algorithm.Table 8
Results of different initialization methods of k-means algorithm.
DatasetARINMIRandomD2-SamplingNewRandomD2-SamplingNewBreast-cancer0.49140.49140.49140.49140.49140.4914Banknote0.04850.04850.04850.04850.04850.0485Bupa0.00000.00000.00000.00000.00010.0001Compound0.53280.53780.41330.72200.71910.6240Ct0.41600.41600.00000.32960.32960.0219Hayes-Roth0.01600.02020.02020.02500.02870.0287Iris0.73020.73020.73020.75810.75810.7581Libras0.30620.31990.28680.58960.60660.5767Parkinsons0.08530.00000.00010.05050.00010.0001Penbased0.54420.59920.42650.68350.69270.6486Vowel0.21800.20280.20580.43320.41410.4067Waveform210.25360.25360.25350.36220.36220.3622Waveform400.25160.25160.25150.36050.36050.3605Wdbc0.49140.49140.49140.46470.46470.4647Wine0.37110.37110.37110.42870.42870.4287Maximum1113711129The initial center points optimization plays an important role in the performance improvement of k-means2o. However, Table8 shows that only using the initialization method proposed in this paper cannot improve the clustering performance. From the evaluation value of ARI, the optimal initialization method is D2-sampling, followed by Random, and the worst is New which is the initialization method proposed in this paper. Except for tiny numerical differences on individual datasets, the NMI evaluation shows similar conclusions. Combined with the conclusion of k-means2o performance improvement, it is the combination of initial center point optimization and phased assignment that improves the performance of k-means2o, not just the center points optimization.


## 4.4. Impact Analysis of Core and Noncore Sets

This paper uses Tukey’s rule to realize the division ofScore and Snoncore. Therefore, a scale factor r needs to be given. Tukey’s rule comes from the field of anomaly detection. Generally, the scale factor is set to 1.5. Points that do not meet the conditions of the scale factor are called outliers. In most cases, these points are directly abandoned. This idea is introduced into cluster analysis and used in the data preprocessing stage. As a result, the points detected as abnormal will be discarded and not assign cluster label. There will be great hidden trouble in this way. Table 9 shows the number of elements in Score and Snoncore in 15 real-world datasets when r=1.5. Except that the Snoncore of compound dataset is empty, the Snoncore of the remaining 14 datasets are not empty. However, as well as we known, all points in these datasets are labeled with class labels. Therefore, it is unreasonable to abandon these suspected outliers simply and rudely. For this reason, this paper proposes a two-stage assignment method, whose first stage assigns cluster label to the points in Score and second stage assigns the points in the Snoncore. For the compound dataset, the empty Snoncore indicates that Tukey’s rule has no effect on this dataset and will directly lead to the failure of the second stage assignment.Table 9
The number of core and noncore subsets elementsScore,Snoncore in k-means2o clustering.
DatasetScoreSnoncoreDatasetScoreSnoncoreBreast-cancer398171Banknote128092Bupa28065Compound3990Ct16457Hayes-roth10230Iris1464Libras3564Parkinsons14847Penbased10482510Vowel96030waveform214740260Waveform404116884Wdbc398171Wine16117The k-means2o algorithm relies on a predefined scale factorr, so it is necessary to perform a sensitivity test of this parameter. Therefore, we took the iris, wine, breast_cancer, banknote, and bupa datasets as an example to investigate the effects of different r on ARI and NMI, as shown in Figure 6. Its shows that the ARI and NMI curves of the five datasets do not fluctuate drastically, so the clustering performance of the k-means2o algorithm based on the scale factor r is relatively robust. Nevertheless, the scale factor r still has a slight impact on the clustering performance. For example, in the iris dataset, when r=0.5, its ARI and NMI values reach 0.8340 and 0.8191, respectively. This clustering result is better than k-means ++, see Table 3 (the values are ARI =0.7302 and NMI =0.7581).Figure 6
Clustering evaluation for differentr on five datasets: (a) ARI curve and (b) NMI curve.
(a)(b)In the above analysis, the k-means2o outperforms k-means++, AP, MS, and DBSCAN. Combined with the fact, almost all Snoncore of these datasets in Table 9 are nonempty. These results show that the combination optimization of the initial center point and the core subset works and improves the k-means clustering performance.


## 5. The Application of K-Means2o

In this section, the k-means2o is applied into cluster to analyze the airline seat selection dataset provided by Neusoft. According to the meaning of clustering, the samples in the same cluster are as similar as possible, and the samples between different clusters are as dissimilar as possible. If most samples in the same cluster have a certain property, it can be inferred that other samples in the same cluster are also most likely to have the same property. If the most passengers in the cluster are willing to accept some of the personalized recommendation service, such as paying for seat selection, the same service should be recommended to other passengers in the cluster, and a clearer audience group will increase the personalized recommendation service success rate. For the airline seat selection dataset, the appropriate clusters number is required to be determined first.The silhouette coefficient is a simple and effective method to determine the appropriate clusters number for the k-means algorithm. The silhouette coefficient of the k-means2o algorithm on this dataset is shown in Figure7. The figure shows that the SSE change tends to be gentle from 16 clusters. Therefore, the optimal number of clusters would be selected as 16. Then, the k-means2o is applied and divides the data into 16 clusters. The number of passengers in each cluster is shown in the column named as size in Table 10. The 3rd, 4th, and 5th columns of Table 10 (payment, no-payment, payment ratio), respectively, show the number of paid passengers, the number of nonpaid passengers and the proportion of paid ones in the airline seat selection. The absolute deviation rate adr in the last column is defined as follows:(10)adrc=rc−rr,where rc is the payment rate in cluster c and r is the payment rate in the dataset. The larger the adr value, the more significant the difference between the payment behavior of passengers in the cluster and the whole dataset.Figure 7
Silhouette coefficient of the k-means2o algorithm on passenger seat selection dataset.Table 10
The airline seat selection dataset clustering result.
ClusterSizePaymentNo-paymentPayment ratio (%)adr (%)C0258018523957.1713.99C1177112716447.1713.99C211393011092.6358.19C3125610711498.5235.45C415964315532.6957.23C5158211214707.0812.56C6761227392.8954.05C7193516617698.5836.41C8193014017907.2314.94C916236715564.1334.34C10202317618478.7038.31C11695216743.0251.99C1214385813804.0335.93C1337983712.1166.45C14909678427.3717.17C15181514616698.0427.82The clustering results show that the number of passengers in each cluster is not close. The cluster with the largest number of passengers isC0, with 2580, while the smallest one is C13, with 379.Further, the significant differences are explored between clusters. Figure8 shows the kernel density estimation curves of three attributes, pax_fcny, pax_tax, recent_gap_day. On the whole, these curves in each cluster are not completely coincident, and there are significant differences, which show that the data distribution of each cluster is different. This conclusion is consistent with the expectation of cluster analysis, that is, the samples between clusters are dissimilar as much as possible. From a single attribute point of view, the discrimination of pax_fcny attribute is the most significant, with different mean point, peak point, and data span. Followed by pax_tax attribute. The third one is recent_gap_day attribute. Its mean and span are very similar, but the peak point is still different. The difference of peak points indicates that there are differences in the concentration of data distribution in the cluster. The larger the peak value, more points are distributed near the mean value.Figure 8
Kernel density estimation curves of pax_fcny, pax_tax, and recent_gap_day attributes.Table 10 discusses the k-means2o algorithm clustering results of the airline seat selection dataset from the similarities within clusters and dissimilarities between the clusters. The clustering results will be a good reference basis for customer grouping. Air passenger grouping will enable the decision-makers to more accurately find the audience of the personalized recommendation service, such as payment for airline seat selection. The dataset shows the label of payment for airline seat selection. Theadr value of each cluster is greater than 12%, which is significantly different from the payout rate of the entire dataset of 6.29%. The cluster with the largest adr value is C13, reaching 66.45%, and the one with the smallest adr value is c5, reaching 12.56%. These results show that passenger payment behavior within clusters is more agglomerated compared to the entire dataset. Since the payment rate of C13 is 2.11%, it is a reverse difference. In other words, the adr=66.45% indicates that passengers in C13 are extremely unwilling to pay for seat selection, and the willingness to pay is significantly lower than the overall level. In 9 of the 16 clusters, the ratio of paying for airline seat selection exceeds 5%. According to the precise recommendation or personalized marketing strategy, enterprises should pay more attention to the passengers in these nine clusters, and their marketing is more likely to succeed. Compared with the passengers in other clusters, the ones in these clusters will be more willing to accept such recommendations and enhance their stickiness. On designing a recommendation system, this clustering result will become a good auxiliary prior information.


## 6. Conclusion

In this paper, two optimization methods for k-means are initial center points selection and phased assignment were proposed, and then the improved k-means algorithm, k-means2o, were proposed. In contrast to the previously introduced algorithms, k-means++, K-MC2, and AFK-MC2, the new initial center points selection optimization redefines the first center point selection strategy and the subsequent center point incremental strategy. The phased assignment optimization adopted the Tukey’s rule to divide dataset into core and noncore sets, then two assignment strategies were proposed corresponding to the core and noncore sets, respectively. These two optimization methods complement each other to form combinatorial optimization. The experimental results on 15 real-world and 10 synthetic datasets show that the k-means2o outperforms its main competitor k-means ++, and under the same setting conditions, namely using the default parameters, the clustering performance of k-means2o is better than affinity propagation, mean shift, and DBSCAN.The improved k-means algorithm, k-means2o, is applied to analyze the airline seat selection dataset. Combined with the data label of paying for seat selection, the clustering results realize customer grouping, and find suitable audience group for the recommendation of seat selection services. Through the analysis of the newly defined absolute deviation rateadr index, the appropriate groups for service recommendation are found, and the groups that are not suitable for recommendation are distinguished. Therefore, the airline enterprises can use limited resources to promote the groups with high-payment willingness, improve the success rate, and avoid promoting seat selection services to the groups with low-payment willingness which not only wastes resources but also causes passengers’ disgust.After a lot of experimental tests, the k-means2o algorithm, like other algorithms, cannot be adapted to all fields and situations, such as high-dimensional sparse data. If the data are a huge number of attributes or higher dimensions, it will easily lead to fewer samples inScore, and in extreme cases, it may be less than the number of clusters. The Olivetti Face image data with 112∗92=10304 dimension have been tested and found that |Score|<40, that is, the number of samples in the core set is less than the number of clusters; therefore, the clustering fails. Due to the division of the core and noncore sets, the k-means2o algorithm is not suitable for huge number of attributes or higher dimensions. We will continue to study this problem and hope to solve this problem in the future.



---

*Source: 3958423-2022-09-12.xml*