Improvement of the Fast Clustering Algorithm Improved by K-Means in the Big Data

The data Data is are quantizsed symbol of the information. Data clustering is a process to find the effective information and hidden structure feature based on data collection and reasonable division by a similarity measure, which is an important data mining technique for unsupervised learning and have an is important and widely used in pattern recognition [1,2,3], machine learning [4,5], image processing [6,7] and other fields. In the era of Big Data, a great deal of valuable data information is produced at all times with the rapid development of economy, science and technology. Different from traditional data, Big Data usually is sparse and has multi noise, , high dimension, sparse, heterogeneous feature fusion and so on [8,9,10]. How to construct efficient clustering models and algorithms for Big Data is a very important and challenging research topic, and has important scientific value and economic benefits.

Data clustering, as an important data mining technology, aims to divide data objects into several different clusters according to similarity measure, so that data objects within clusters have the greatest similarity and data objects between different clusters have the smallest similarity. A variety of data clustering algorithms have been researched in past years, which include nonnegative matrix factorizsation [11,12,13,14], mean shift [15,16,17], spectral clustering [18,19,20], sparse subspace clustering [21,22,23], and K-means [24,25,26,27], etc. Undoubtedly, K-means is the most commonly used and important clustering algorithm. The purpose of K-means clustering purpose is to minimizse the sum of squared Euclidean distance between each data points and its closest centere point [25]: (1)mincj,j∑j=1k∑i∈ℂjdist(mi−cj)\mathop {\min }\limits_{{c_{j,j}}} \sum\limits_{j = 1}^k {\sum\limits_{i \in {{\mathbb C}_j}} {dist\left( {{m_i} - {c_j}} \right)} } where dist is the distance function, k is the clustering number, c_j is the clustering centere, ℂ_j is the index set of the j-th cluster and ∪ℂj=1kj={1,2,⋯,n}\cup {\mathbb C}_{j = 1}^kj = \{ 1,2, \cdots ,n\} . In fact, this process is similar to Voronoi diagram of function dist in data space, so locating the global optimum solution of this problem is NP-hard even for the simplest case. Therefore, only the local minimum of K-means model is applied in practice. The most commonly used algorithm is Lloyd’s algorithm [25]. Lloyd’s algorithm is a heuristic iterative refinement method, which can quickly converge to the local optimum solution. For the pre-selected cluster centeres, the algorithm mainly carries out the following iterative processes: allocation steps and update steps. The purpose of the allocation step is to allocate the data points to each data centere by calculating the distance from the checkpoint to each clustering centere,; the update steps is to involves recalculateion of the new clustering centeres through the current allocation. From the Lloyd’s algorithm, we can find that different clustering models and corresponding algorithms can be obtained by defining different similarity measure dist, selecting different initial clustering centeres and defining different recalculating clustering centeres. It is precisely because K-means model and Lloyd’s algorithm have such flexible forms that they can choose suitable forms according to different problems, so they have been widely used. However, regardless of the model and algorithm, the disaster of data scale and dimension is unavoidable. We know that the most time-consuming part of the Lloyd’s algorithm is the allocation step. The calculating amount of the distance between the point and centere (e.g. Euclidean distance) is O(kdn), and the total amount of calculation of Lloyd’s algorithm is O(tkdn), where t is the iteration step. Therefore, when d and n is are large, the efficientcy of Lloyd’s algorithm will be greatly reduced [28,29,30].

In the process of clustering, the basic K-means model needs to determine three parameters the following: the selection of initial iteration point c₀ and the iterative process;, the determination or estimation of clustering number k; and the definition of similarity measure dist between sample points. Many improved K-means models and algorithms can be obtained by choosing different processing methods offor the above-mentioned three parameters. Several improved initializsation schemes were proposed to deal with the initializsation issue of Lloyd’s algorithm. For example, one of the most important improved models is the K-means++++ [28]. This is assuming that k¯(0<k¯<k)\bar k\left( {0 < \bar k < k} \right) initial clustering centeres have been selected,; the farther away from the current k¯{\bar k} clustering centeres, the higher the probability of selecting the k¯+1\bar k + 1 clustering centere. For more detail on initializsation methods for K-means, we refer to Celebi et al. the Reference [30]. According to the different selection rules of clustering number k, the improved K-means model generally includes: K-J inflection point model [31] and ISODATA [32] (Iterative Self-Organizing Data Analysis Techniques Algorithm (ISODATA) [32]. The K-J model calculates a series of cluster number k and cluster objective function value J, draws the relationship between them and uses the inflection point of the graph to determine the value of k. The ISODATA repeatedly modifies the number of clustering centeres to get a more reasonable number of categories k in the process of iteration. When given parameters, this modification is achieved by merging and splitting, we can (refer to the Reference [33]). In order to deal with data clustering problems with different data distributions, it is necessary to select different similarity measures between sample points, so that different types of K-means improved models can be obtained. Kernel K-means model is similar to the idea of kernel function in support vector machine, mapping all samples to another vector space and clustering [31]. Fuzzy C-means model introduces the fuzzy factors, calculates the membership degree from each point to each cluster and uses this membership degree to determine the level to which each point belongs to a cluster [34]. Spherical K-means model is to solve the problem clustering data points on a sphere [35]. When using this model, we need to normalizse each data point, and then use cosine dissimilarity instead of Euclidean distance to measure the similarity between data points. In addition, there are some improved models that used Mahalanobis distance, Itakura–Saito divergence and Bergman divergence instead of Euclidean distance as a similarity measure. For sample points x ∈ R^m×n, and y ∈ R^m×n, S is covariance, and Φ is convex function, there are we have [36,37,38]:

Mahalanobis distance: (2)d(x,y)=(x−y)TS−1(x−y)d\left( {x,y} \right) = \sqrt {{{\left( {x - y} \right)}^T}{S^{ - 1}}\left( {x - y} \right)}

Itakura–Saito divergence: (3)d(x,y)=xy−ln(xy)−1d\left( {x,y} \right) = {x \over y} - \ln ( {{x \over y}} ) - 1

Bergman divergence: (4)d(x,y)=Φ(x)−Φ(y)−〈∇Φ(y),(x−y)〉d\left( {x,y} \right) = \Phi \left( x \right) - \Phi \left( y \right) - \left\langle {\nabla \Phi \left( y \right),\left( {x - y} \right)} \right\rangle

In Big Data clustering problems, the advantages of K-means and related improved algorithms are mainly focused on include the following: concise and intuitive, high computing efficiency and scalability. Comparatively, it also has obvious shortcomings: the distribution of clustering data is too strict;, different initial points lead to distinct clustering results and easily fall into local optimal solution; and computational complexity is linearly correlated with data dimension. Therefore, when dealing with the low-dimensional data clustering problems, K-means and related improved algorithms usually get more accurate results and the running time is acceptable. However, for high-dimensional Big Data, due to the impact of dimension disaster, data distribution, data size, data noise and so on, the K-means and related improved algorithms often cannot get the desired results and the computational efficiency is low. In order to deal with this problem, a common method is to reduce the dimensionality of data, that is, to seek low-dimensional features of high-dimensional data, and then to cluster within low-dimensional features. However, there are some difficulties problems in high-dimensional data clustering algorithm based on dimensionality reduction. Firstly, is low-dimensional data the dominating feature needed in clustering of practical problems? Secondly, whether the mapping of distances between low-dimensional data points is conductive clustering?. Generally speaking, data dimensionality reduction and low-dimensional clustering are two important partsteps in solving large data clustering process: data dimensionality reduction clears obstacles for low-dimensional clustering (removing data noise, reducing data dimension, etc.), and low-dimensional clustering achieves the ultimate goal of clustering. In order to achieve excellent processing results, the two processes of data dimensionality reduction and low-dimensional clustering should complement and match each other in Big Data clustering.

In this paper, unlike the existing improved K-means models, aiming at the low efficiency of traditional algorithms caused by Big Data, we purpose clustering in feature space to improve the efficiency of the algorithm while ensuring the accuracy. We point out that as long as the clustering centere and distance function satisfy certain conditions, most K-means algorithms can be accelerated with our ideas. In addition, we proved that the processing steps (data dimension reduction) and clustering steps (low-dimensional clustering) of the proposed method are completely matched in the problem of Dig Data clustering.

In the classical K-means model, the mean of data points is usually chosen as the clustering centere and the initial value is chosen randomly. In the problems of Big Data clustering, through continuous theoretical research and practical application, researchers found that European distance is extremely unfavourable to measure the similarity between high-dimensional data, especially sparse high-dimensional data. In addition, the selection method of random cluster centeres is also very sensitive to noise. The improved models and algorithms are mainly aimed at the above-mentioned two points. Next, we will introduce two famous improved models in practical application forms in Big Data clustering problems: spherical K-means model and K-medoids model.

For Big Data clustering, the original data are heterogeneous, noisy, high-dimensional and sparse. The directional differences between the original data are far more important than the metric measurement differences, because the length of the original data is likely to be different, even though the differences between the same measurements should be significant. Based on this, in 2011, Dhillon et al. proposed the use of cosine dissimilarity to measure the distance between data [35], that is spherical K-means model. The definition of cosine difference of two points x ∈ R^d×n and y ∈ R^d×n is as follows: (5)d(x,y)=1−cos(x,y)=1−〈x,y〉‖x‖‖y‖d\left( {x,y} \right) = 1 - \cos \left( {x,y} \right) = 1 - {{\left\langle {x,y} \right\rangle } \over {\left\| x \right\|\left\| y \right\|}}

It can be obtained that the objective function of spherical K-means model has the following form: (6)∑j=1k∑i=1nuij(1−〈mi,cj〉‖mi‖‖cj‖)=∑j=1k[∑i=1nuij−〈∑i=1nuijmi‖mi‖,cj‖cj‖〉]\sum\limits_{j = 1}^k {\sum\limits_{i = 1}^n {{u_{ij}}(1 - {{\left\langle {{m_i},{c_j}} \right\rangle } \over {\left\| {{m_i}} \right\|\left\| {{c_j}} \right\|}}) = \sum\limits_{j = 1}^k {[\sum\limits_{i = 1}^n {{u_{ij}} - \left\langle {\sum\limits_{i = 1}^n {{u_{ij}}{{{m_i}} \over {\left\| {{m_i}} \right\|}},{{{c_j}} \over {\left\| {{c_j}} \right\|}}} } \right\rangle } ]} } }

Using Cauchy–Schwartz inequality, spherical K-means model can get the optimal value if and only if: (7)cj←∑i=1nuijmi‖mi‖∀j{c_j} \leftarrow \sum\limits_{i = 1}^n {{u_{ij}}} {{{m_i}} \over {\left\| {{m_i}} \right\|}}\forall j

If the data is are normalizsed, i.e. ‖m_i‖ = 1, the clustering centere of spherical K-means model can be expressed as: (8)cj←∑i=1nuijmi‖mi‖=∑i∈jmi∀j{c_j} \leftarrow \sum\limits_{i = 1}^n {{u_{ij}}{{{m_i}} \over {\left\| {{m_i}} \right\|}} = \sum\limits_{i \in j} {{m_i}\forall j} } that is, the clustering centere c_j is proportional to the sum of all the data in the j class., where m_i ∈ M, M ∈ R^d×n is the original data, k is the clustering number, c_j is the clustering centere, j is the index set of the j-th cluster, and u_ij = {0,1} is the indicator function.

For spherical K-means model, Lloyd iteration algorithm cannot increase the objective function, but and cannot guarantee certain convergence. The algorithm process is shown in below Figure 1.

Figure 1

In Big Data clustering, there are always a lot of outliers due to the influence of practical problem. Generally speaking, the accuracy of K-means will be greatly reduced when the data hasve outliers. The main reason is that the clustering centere will be seriously affected by outliers. In order to solve this problem, Kaufman and Rousseeuw proposed using medoids, a point in the centere of data (location in the centere), as the clustering centere. Therefore, this method is also called K-medoids model. The algorithm process is shown in below Figure 2.

Figure 2

Medoid minimizses the average difference between all data points in the same cluster, so it has high robustness to noise. But However, the calculation of medoid needs to compare the distance of all data points before deciding which one is medoid, which is much more complex than mean, resulting in the low computational efficiency of K-medoids model for high-dimensional data. It has good robustness but low efficiency in the application of Big Data clustering. Partitioning Around Medoids PAM (PAMPartitioning Around Medoids) is the most effective algorithm for solving K-medoids model. Given a randomly selected initial value, PAM replaces each cluster centere with a data point that reduces the objective function. This process continues to iterate until each medoids cannot be replaced. In each iteration, the computational complexity of PAM is O(d(n − k)²k). In order to reduce the computational complexity, Park and Jun proposed a fast K-medoids clustering algorithm. This method calculates the distance matrix iteratively and uses it to calculate the mew medoids. The computational complexity of this algorithm is consistent with K-means, which makes this algorithm widely concerned applicable in Big Data clustering. However, when the data scale increases sharply, the calculation of the preprocessing matrix is too large.

To reasonably utilise In order to make the concise and efficient K-means algorithm reasonably utilized in Big Data clustering, we will consider the improved K-means algorithm in dimension reduction space (feature space). Assuming that the rank of the data matrix M ∈ R^d×n is r = Rank(M) ≤ min(d,n), and M is decomposed into M = UΣV^T by singular value decomposition, then: (9)UTM=ΣVT=[Σr000][V1︸rV2︸n−r]T=[ΣrV1T0]≜[M^0]{U^T}M = \Sigma {V^T} = \left[ {\matrix{{{\Sigma _r}} & 0 \cr 0 & 0 \cr } } \right]{\left[ {\underbrace {{V_1}}_r\;\underbrace {{V_2}}_{n - r}} \right]^T} = \left[ {\matrix{{{\Sigma _r}V_1^T} \cr 0 \cr } } \right] \buildrel \Delta \over = \left[ {\matrix{{\hat M} \cr 0 \cr } } \right] where V₁ contains the first r right singular vectors of data M. We have the following theorem about the problem of original problem and feature space, that is, the original problem is completely equivalent to the problem of feature space under certain conditions.

Based on the above discussion, when using K-means to deal with Big Data clustering problem, we can first reduce the dimension of the data, and then carry out clustering analysis in the feature space. The algorithm process is shown in below Figure 3.

Figure 3

In this section, we use artificial data and actual data to test the performance of the algorithm, mainly verifying two aspects: whether the objective function is consistent, whether the running time is reduced. All numerical experiments were run on a desktop computer with an Intel Core i7-3770 CPU at 3.40 GHz with 8 GB RAM under Matlab R2017b.

We construct the following artificial data to verify the accuracy of the algorithm. Firstly, k points in d dimensional space are randomly selected as clustering centeres. Then, Gaussian points with variance of σ are added around the clustering centeres, and the total number of data points is n. Finally, n data points are randomly replaced. In order to test the influence of data dimension, we make d vary from 1,000 to 50,000. The number of samples is n = 1,000, and the number of clusters is k =10.

Table 1 records the differences of K-means, spherical K-means and K-medoids objective functions between the original space and the feature space. It can be seen that the clustering results of the original space and the feature space are consistent from in any initial value. Table 2 records the running time ratio of K-means, spherical K-means and K-medoids in the original space and feature space. It can be see that when the dimension of d is small (compared with the number of samples), clustering in the feature space does not speed up the algorithm, because clustering in the feature space also needs to calculate the eigenvalues decomposition. However, with the increase of in dimension, K-means clustering in the feature space should to save a lot of time (when d = 50,000, the running time of the algorithm is reduced by 44 times).

Next, we will test the performance of the algorithm on image data and DNA data. These two kinds of data from different fields, have different meanings and the scale of data is also different, which is helpful to verify the advantages and disadvantages of our algorithm in different data. Table 3 records information of various data. The first three data are image data and the last four data are DNA data.

Table 4 records the differences in objective functions of K-means, spherical K-means and K-medoids objective functions between the original space and the feature space. It can be seen that the clustering results of the original space and the feature space are consistent from for any initial value. Table 5 records the running time ratio of K-means, spherical K-means and K-medoids in the original space and feature space. It can be see that the acceleration effect of the algorithm for LunG data is not obvious, because the data dimension is not high (d = 1,000) and the number of samples is relatively large (n = 197). The algorithm has the best acceleration effect (more than 10 times) for Prostate data, mainly due to the high dimension and small number of data.

In this paper, we aim at the low efficiency of K-means algorithm caused by high-dimensional data. The clustering algorithm in the feature space is proposed to improve the efficiency of the algorithm while ensuring the accuracy. We also point out that as long as the clustering centere and distance function satisfy certain conditions, K-means type problems and corresponding algorithms can be accelerated with our ideas. In addition, we demonstrate in detail that the pre-processing steps (data dimensionality reduction) of our proposed method perfectly match the clustering steps (low-dimensional clustering) for the problem of high-dimensional Big Data problem.