# Nonuniform Sparse Data Clustering Cascade Algorithm Based on Dynamic Cumulative Entropy

Authors: Ning Li; Yunxia Gu; Zhongliang Deng
Journal: Mathematical Problems in Engineering
 (2016)

---

## Abstract

A small amount of prior knowledge and randomly chosen initial cluster centers have a direct impact on the accuracy of the performance of iterative clustering algorithm. In this paper we propose a new algorithm to compute initial cluster centers fork-means clustering and the best number of the clusters with little prior knowledge and optimize clustering result. It constructs the Euclidean distance control factor based on aggregation density sparse degree to select the initial cluster center of nonuniform sparse data and obtains initial data clusters by multidimensional diffusion density distribution. Multiobjective clustering approach based on dynamic cumulative entropy is adopted to optimize the initial data clusters and the best number of the clusters. The experimental results show that the newly proposed algorithm has good performance to obtain the initial cluster centers for the k-means algorithm and it effectively improves the clustering accuracy of nonuniform sparse data by about 5%.


---

## Body

## 1. Introduction

Clustering is an important discovery technique of exploratory data mining and a common technique for statistical data analysis. Iterative clustering algorithm is one kind of the clustering algorithms. Andk-means is the most popular and the fast method in iterative clustering algorithms. Because of the simplicity of k-means algorithm, it is used in many fields, including machine learning, medicine, image analysis, pattern recognition, information retrieval, bioinformatics, and computer. For example, in the medical field, cancer genomics [1], cell signaling [2], and viral genomes [3] use k-means as a data analysis tool; in the bioinformatics field, bioanalytical chemistry [4], the vibrational spectra of biomolecules [5], and the nervous system [6] use k-means to mine potential information; in the image analysis field, imaging techniques [7] use k-means to partition a given set of points into homogeneous groups; in the pattern recognition field, automatic system for imbalance diagnosis in wind turbines [8] uses k-means to suggest the optimum number of groups. Reference [9] uses k-means to analyze network data. Reference [10] generates profiles by k-means to group together days with a similar pattern of request arrivals.Althoughk-means algorithm has been developed to solve a wide range of different problems, it has three major drawbacks:(1)
It needs to predetermine the cluster numberk by user. In practice, due to little prior knowledge, k value is generally difficult to determine.(2)
It is sensitive to selection of the initial cluster centers. That is,k-means selects different initial cluster centers with different results. Because of randomly chosen initial clusters centers, populations are generally composed of low quality individuals exclusively.(3)
The effect ofk-means algorithm for nonuniform sparse data processing is not good.To overcome these drawbacks, many evolutionary algorithms such as GA, TS, and SA have been introduced. Kao et al. have proposed a hybrid technique based on combining thek-means algorithm [11]. Bahmani Firouzi et al. have introduced a hybrid evolutionary algorithm based on combining PSO, SA, and k-means to find optimal solution [12]. Niknam and Amiri have proposed a hybrid algorithm based on a fuzzy adaptive PSO, ACO, and k-means for cluster analysis [13]. Niknam et al. have purposed a novel algorithm that is based on combining two algorithms of clustering: k-means and Modified Imperialist Competitive Algorithm [14]. Evolutionary algorithms require large amounts of data to study; however, many real-world problems are like black boxes; hence no sufficient data about their internals is available.In addition, to solve the problem of selection of the initial cluster centers, Bianchi et al. have proposed two density-basedk-means initialization algorithms for nonmetric data clustering [15]. Tunali et al. have proposed an improved clustering algorithm for text mining: multicluster spherical k-means [16]. Tvrdík and Křivý have proposed a new algorithm combining differential evolution and k-means [17]. Rodriguez and Laio proposed selection of the initial cluster centers by density peak. Khan and Ahmad [18] have proposed the cluster center initialization algorithm for k-means clustering. But the computing of the above methods is laborious.In order to solve the situation that a small amount of prior knowledge and randomly chosen initial cluster centers have a direct impact on the accuracy of the performance of iterative clustering algorithm. In this paper, we propose a new algorithm for nonuniform sparse data clustering based on cascade entropy increase and decrease. It designs Euclidean distance sparse degree of aggregation density control factor, determines the initial cluster center of nonuniform sparse data, and groups initial data clusters by multidimensional diffusion data distribution density. Multiobjective clustering approach is adopted to compensate the clustering error of initial data clusters. The experimental results show that the new data clustering algorithm can effectively improve the clustering accuracy of nonuniform sparse data clusters.


## 2. Nonuniform Sparse Data Clustering Cascade Algorithm Based on Dynamic Cumulative Entropy

In order to obtain the optimal clustering results of nonuniform sparse data, in this paper, we use multidimensional diffusion density distribution to obtain the initial data clusters, while the Euclidean distance control factor based on aggregation density sparse degree is put forward to solve the problem that multidimensional data is easy to misjudge. The initial data clusters are more than the real cluster. So we need to select optimal initial cluster centers by decision graph and then executek-means on complete data set based on multiobjective clustering approach.


### 2.1. Initial Data Clustering Using Multidimensional Diffusion Density Distribution

In iterative clustering algorithms, choosing initial cluster centers is extremely important as it has a direct impact on the formation of final clusters. It is dangerous to select some samples as initial centers, which are away from normal samples. In this paper, first we define the multidimensional diffusion density distribution of samples and the comprehensive distance, according to which we get the initial data clusters.


#### 2.1.1. Multidimensional Diffusion Data Normalization

Different attributes of multidimensional data have different units of measurement and value ranges, which has a serious impact on clustering formation. So in order to avoid the above situation at first we need to normalize clustering data to make all attributes have the same weights. Normalization is done using the following formula.Calculate the average of the absolute deviation:D is the set of n data elements described with attributes A1,A2,…,Am where m is the number of attributes and all attributes are numeric. X1A1′ is the measured value of the first attribute belonging to the first data:(1)SA1=1nX1A1′-MA12+X2A1′-MA12+⋯+XnA1′-MA12X1,X2,…,Xn∈D,where(2)MA1=1nX1A1′+X2A1′+⋯+XnA1′,X1A1=X1A1′-MA1SA1.


#### 2.1.2. Multidimensional Diffusion Density Distribution

In iterative clustering algorithms the function adopted for density is the cut-off kernel [19]: (3)ρi=∑j∈D/iχdij-dc,where(4)χX=1,X<0,0,X≥0,dij=XiA1-XjA12+XiA2-XjA22+⋯+XiAm-XjAm2,where dc is the cut-off distance determined by user and dc>0.X i A 1 is the ith data with attributes A1 and XjA1 is the jth data with attributes A1. dij measures the Euclidean distance between XiA1 and XjA1. So ρi is the number of data whose distance to the data i is less than dc.The clustering results of multidimensional data have shortcoming using the above functions adopted for density. Some multidimensional data are misjudged for the functions without considering the difference among attributes. If few attributes of some data change a lot but other attributes are close to other data, these mutating data can be misjudged into the cluster that they are not similar to for the changing attributes are ignored. In order to solve the above problems, we put forward the Euclidean distance control factor based on aggregation density sparse degreeE:(5)E=log⁡max⁡XiAq-XjAq2min⁡XiAp-XjAp2dij,where q is the qth attribute of data about which XiA and XjA have the maximum distance and p is the attribute of data about which XiA and XjA have the minimum distance.According to the above views, we propose the optimized density formula:(6)ρi=∑j∈D/iχ1+Edij-dc.Formula (6) makes distinction among different attributes using the Euclidean distance control factor based on aggregation density sparse degree E. The attributes with large differences are given more weights’ computing density, which reduces the risk of misjudged data. The optimized density is multidimensional diffusion density:(7)Zρ=ρ¯+δρ,where ρ¯ is the average of multidimensional diffusion density ρi and δρ is the standard deviation of multidimensional diffusion density. Zρ is standard value of multidimensional diffusion density. Let the data whose multidimensional diffusion density is bigger than Zρ in a collection named B:(8)σ=σi=min⁡dij,ρi<ρj,σi=max⁡dijρimax⁡Xi,Xj∈B.σ is the distance between Xi and Xj, and both of them are from collection B:(9)Zσ=σ¯+δσ,where σ¯ is the average of distance between the data from collection B. And δσ is the standard deviation of distance between the data from collection B. Zσ is standard value of distance. Let the data whose distance is bigger than Zσ be in a collection named C. Reference [19] shows that the initial cluster centers have the large density and the far distance. So the data in collection C are likely to be initial cluster centers. We choose them as the initial cluster centers of initial data clusters.


#### 2.1.3. Obtaining Initial Data Clusters by Multidimensional Diffusion Density Distribution

In this subsection we present execution steps of our proposed initial data clustering using multidimensional diffusion density distribution fork-means clustering. This algorithm consists of two parts. The first part deals with the the initial cluster centers of the initial data. Then we execute the second part of the algorithm to group the data.D = { x 1 , x 2 , … , x n }, which is the set of n data elements described with attributes A1,A2,…,Am where m is number of attributes and all attributes are numeric. Compute ρi of each data, mean ρ¯, standard deviation δρ, and Zρ. Choose the data whose ρi is bigger than Zρ, and put them into collection B. Compute σ of each piece of data in B collection, σ¯, standard deviation δσ, and Zσ. Choose the data whose σ is bigger than Zσ and put them into C collection, C=c1,c2,…,ck′ is the set of the initial cluster centers of the initial data, and k′ is the number of the initial cluster centers:(10)dXi,cj=∑a=1mXiAa-cjAa2,i=1,…,n;j=i,…,k′.d ( X i , c j ) measures the Euclidean distance between a pattern Xi and its cluster center cj that is in the C collection.k-means algorithm minimizes the function which is defined as object function [18]:(11)JMSE=∑i=1k′∑xj∈Cixj-cj2.Thek-means algorithm groups the data iteratively as follows. Choose the data in C collection as the initial cluster centers and the number of them is k′, the number of initial data clusters. Decide membership of the patterns in one of the K-clusters according to the minimum distance from cluster center criteria. Then calculate new cj centers as: (12)cj=1N∑Xi∈cjXi.N is the number of data from which the jth cluster center of. Repeat the previous steps till there is no change in cluster centers. The clusters are the initial data clusters. Let W=w1,w2,…,wk′,Wi=x1,x2,…,xN be a clusters set of the initial data clusters.


### 2.2. Multiobjective Clustering Approach Based on Dynamic Cumulative Entropy

Obtaining the initial data clusters by multidimensional diffusion density distribution is the primary data processing. To get the accurate clustering results we need to cluster again on the basis of it, and the initial data clusters are the basic elements.


#### 2.2.1. Multiobjective Clustering Function Based on Dynamic Cumulative Entropy

In thek-means algorithm the object function is JMSE. But it is not suitable for optimizing the primary clusters of data and determining k, the number of clusters because JMSE decreases monotonously for the increase of the number of clusters. When JMSE reduced to the global minimum, the initial cluster centers are putted away from their data, which makes single data a cluster. So proposed objective function refers to the information of each initial data cluster in the process of the deepening clustering.The paper tries to solve the above problems by studying the clusters’ structure by informational entropy theory and the principle of Maximum Informational Entropy. We propose a multiobjective clustering functionJ based on dynamic cumulative entropy to determine the final clustering results. Firstly, we define the information entropy formula of cluster:(13)Hi=-∑i=1kPinln⁡Pin,where Pi is the number of data in the ith initial data clusters, n is the number of data to be clustered, and k is the number of clusters.According to the principle of Maximum Informational Entropy, if clusters have no elements, the information entropy is 0,H=0. When clusters tend to be stable and meet the condition that the numbers of elements belonging to different clusters Pi are very similar, the information entropy is maximum; Hmax=ln⁡k. Based on the information entropy formula (14) of cluster, we define the cluster structure equilibrium degree S:(14)Si=HiHmax=-∑i=1kPi/nln⁡Pi/nln⁡k′.S is time-varying entropy-to-maximum entropy ratio, which shows the balance degree of clusters and 0≤S≤1. When Si=0, cluster is in the most uneven condition. When Si=1 clusters are in ideal equilibrium state:(15)Y=1-S.Y is the degree of equilibrium gain, which reflects the cluster occupancy of data.Finally, we get the multiobjective clustering function based on dynamic cumulative entropyJ:(16)J=JMSE+∑i=1kYiR,where(17)R=2βkk-1∑i=1k∑j=1Pdci,cj.R is the average distance among the clusters. The multiobjective clustering function considers not only the distance among the cluster centers and its data influence on the clustering results, but also the amount of information. JMES decreases monotonically with the decreasing of distance among the cluster centers and its data influence on the clustering results. On the contrary, ∑i=1kYiR increases monotonically with the increasing of the number of the global clusters. So ∑i=1kYiR as restricting factor prevents the number of clusters k more than the real k for JMES decreasing. It improves the clustering accuracy and reliability when the number of clusters k is not determined.


#### 2.2.2. Multiobjective Clustering Approach Based on Dynamic Cumulative Entropy

The initial data clustersW={w1,w2,…,wk′} by multidimensional diffusion density distribution need to be clustered again. The initial cluster centers C=c1,c2,…,ck′ are determined again by the distance-information decision graph.The less information of a cluster has, the smaller its uncertainty is and the more likely it is to be the final cluster. At the same time, the global classification is more stable. Formula for information of the initial data clusters is(18)Ici=-log⁡Pin,∑i=1k′Pi=n,i=1,2,…,k′.Calculate the distance among the initial data clusters:(19)β=βi=dmin⁡Mi,Mj,Ii<Ij,βi=dmax⁡Mi,Mj,Iimax,ij∈C,where Mi=1/N∑f=1NXf, Xf is the data from which the ith cluster center of.By the nature of the clustering, we can know that the cluster’s uncertainty should be small and the distance among clusters should be large. According to this, we can draw distance-information decision graph to determinek and the initial cluster centers. Take two-dimensional data for example, such as shown in Figure 1. Multidimensional diffusion density distribution obtains initial data clusters A, B, C, D, E, F, G, H, I, J, and K. Figure 2 is distance-information decision graph with the inverse of information of the initial data cluster as the horizontal axis (1/I) and the distance among initial data clusters as the longitudinal axis (β).Figure 1
Initial data cluster.Figure 2
Distance-information decision graph.By the distance-information decision graph we can see that initial data clustersA, H, D, and K have compared low information and large distance among clusters because the larger k value can expand the searching scope of solution space, which avoids ignoring the sparse clusters. The selection of the initial cluster centers can be expanded according to the distance-information decision graph. Select the respective average values m of initial data clusters A, H, D, K, G, and B as the initial cluster centers and k1 as 6; minimize the multiobjective clustering function with result J1. Select the respective average values m of initial data clusters A, H, D, K, and G as the initial cluster centers and k2 as 5; minimize the multiobjective clustering function with result J2. Select the respective average values m of initial data clusters A, H, D, and K as the initial cluster centers and k3 as 4; minimize the multiobjective clustering function with result J3. Then compare J1, J2, and J3; the minimum is the best choice.


## 2.1. Initial Data Clustering Using Multidimensional Diffusion Density Distribution

In iterative clustering algorithms, choosing initial cluster centers is extremely important as it has a direct impact on the formation of final clusters. It is dangerous to select some samples as initial centers, which are away from normal samples. In this paper, first we define the multidimensional diffusion density distribution of samples and the comprehensive distance, according to which we get the initial data clusters.


### 2.1.1. Multidimensional Diffusion Data Normalization

Different attributes of multidimensional data have different units of measurement and value ranges, which has a serious impact on clustering formation. So in order to avoid the above situation at first we need to normalize clustering data to make all attributes have the same weights. Normalization is done using the following formula.Calculate the average of the absolute deviation:D is the set of n data elements described with attributes A1,A2,…,Am where m is the number of attributes and all attributes are numeric. X1A1′ is the measured value of the first attribute belonging to the first data:(1)SA1=1nX1A1′-MA12+X2A1′-MA12+⋯+XnA1′-MA12X1,X2,…,Xn∈D,where(2)MA1=1nX1A1′+X2A1′+⋯+XnA1′,X1A1=X1A1′-MA1SA1.


### 2.1.2. Multidimensional Diffusion Density Distribution

In iterative clustering algorithms the function adopted for density is the cut-off kernel [19]: (3)ρi=∑j∈D/iχdij-dc,where(4)χX=1,X<0,0,X≥0,dij=XiA1-XjA12+XiA2-XjA22+⋯+XiAm-XjAm2,where dc is the cut-off distance determined by user and dc>0.X i A 1 is the ith data with attributes A1 and XjA1 is the jth data with attributes A1. dij measures the Euclidean distance between XiA1 and XjA1. So ρi is the number of data whose distance to the data i is less than dc.The clustering results of multidimensional data have shortcoming using the above functions adopted for density. Some multidimensional data are misjudged for the functions without considering the difference among attributes. If few attributes of some data change a lot but other attributes are close to other data, these mutating data can be misjudged into the cluster that they are not similar to for the changing attributes are ignored. In order to solve the above problems, we put forward the Euclidean distance control factor based on aggregation density sparse degreeE:(5)E=log⁡max⁡XiAq-XjAq2min⁡XiAp-XjAp2dij,where q is the qth attribute of data about which XiA and XjA have the maximum distance and p is the attribute of data about which XiA and XjA have the minimum distance.According to the above views, we propose the optimized density formula:(6)ρi=∑j∈D/iχ1+Edij-dc.Formula (6) makes distinction among different attributes using the Euclidean distance control factor based on aggregation density sparse degree E. The attributes with large differences are given more weights’ computing density, which reduces the risk of misjudged data. The optimized density is multidimensional diffusion density:(7)Zρ=ρ¯+δρ,where ρ¯ is the average of multidimensional diffusion density ρi and δρ is the standard deviation of multidimensional diffusion density. Zρ is standard value of multidimensional diffusion density. Let the data whose multidimensional diffusion density is bigger than Zρ in a collection named B:(8)σ=σi=min⁡dij,ρi<ρj,σi=max⁡dijρimax⁡Xi,Xj∈B.σ is the distance between Xi and Xj, and both of them are from collection B:(9)Zσ=σ¯+δσ,where σ¯ is the average of distance between the data from collection B. And δσ is the standard deviation of distance between the data from collection B. Zσ is standard value of distance. Let the data whose distance is bigger than Zσ be in a collection named C. Reference [19] shows that the initial cluster centers have the large density and the far distance. So the data in collection C are likely to be initial cluster centers. We choose them as the initial cluster centers of initial data clusters.


### 2.1.3. Obtaining Initial Data Clusters by Multidimensional Diffusion Density Distribution

In this subsection we present execution steps of our proposed initial data clustering using multidimensional diffusion density distribution fork-means clustering. This algorithm consists of two parts. The first part deals with the the initial cluster centers of the initial data. Then we execute the second part of the algorithm to group the data.D = { x 1 , x 2 , … , x n }, which is the set of n data elements described with attributes A1,A2,…,Am where m is number of attributes and all attributes are numeric. Compute ρi of each data, mean ρ¯, standard deviation δρ, and Zρ. Choose the data whose ρi is bigger than Zρ, and put them into collection B. Compute σ of each piece of data in B collection, σ¯, standard deviation δσ, and Zσ. Choose the data whose σ is bigger than Zσ and put them into C collection, C=c1,c2,…,ck′ is the set of the initial cluster centers of the initial data, and k′ is the number of the initial cluster centers:(10)dXi,cj=∑a=1mXiAa-cjAa2,i=1,…,n;j=i,…,k′.d ( X i , c j ) measures the Euclidean distance between a pattern Xi and its cluster center cj that is in the C collection.k-means algorithm minimizes the function which is defined as object function [18]:(11)JMSE=∑i=1k′∑xj∈Cixj-cj2.Thek-means algorithm groups the data iteratively as follows. Choose the data in C collection as the initial cluster centers and the number of them is k′, the number of initial data clusters. Decide membership of the patterns in one of the K-clusters according to the minimum distance from cluster center criteria. Then calculate new cj centers as: (12)cj=1N∑Xi∈cjXi.N is the number of data from which the jth cluster center of. Repeat the previous steps till there is no change in cluster centers. The clusters are the initial data clusters. Let W=w1,w2,…,wk′,Wi=x1,x2,…,xN be a clusters set of the initial data clusters.


## 2.1.1. Multidimensional Diffusion Data Normalization

Different attributes of multidimensional data have different units of measurement and value ranges, which has a serious impact on clustering formation. So in order to avoid the above situation at first we need to normalize clustering data to make all attributes have the same weights. Normalization is done using the following formula.Calculate the average of the absolute deviation:D is the set of n data elements described with attributes A1,A2,…,Am where m is the number of attributes and all attributes are numeric. X1A1′ is the measured value of the first attribute belonging to the first data:(1)SA1=1nX1A1′-MA12+X2A1′-MA12+⋯+XnA1′-MA12X1,X2,…,Xn∈D,where(2)MA1=1nX1A1′+X2A1′+⋯+XnA1′,X1A1=X1A1′-MA1SA1.


## 2.1.2. Multidimensional Diffusion Density Distribution

In iterative clustering algorithms the function adopted for density is the cut-off kernel [19]: (3)ρi=∑j∈D/iχdij-dc,where(4)χX=1,X<0,0,X≥0,dij=XiA1-XjA12+XiA2-XjA22+⋯+XiAm-XjAm2,where dc is the cut-off distance determined by user and dc>0.X i A 1 is the ith data with attributes A1 and XjA1 is the jth data with attributes A1. dij measures the Euclidean distance between XiA1 and XjA1. So ρi is the number of data whose distance to the data i is less than dc.The clustering results of multidimensional data have shortcoming using the above functions adopted for density. Some multidimensional data are misjudged for the functions without considering the difference among attributes. If few attributes of some data change a lot but other attributes are close to other data, these mutating data can be misjudged into the cluster that they are not similar to for the changing attributes are ignored. In order to solve the above problems, we put forward the Euclidean distance control factor based on aggregation density sparse degreeE:(5)E=log⁡max⁡XiAq-XjAq2min⁡XiAp-XjAp2dij,where q is the qth attribute of data about which XiA and XjA have the maximum distance and p is the attribute of data about which XiA and XjA have the minimum distance.According to the above views, we propose the optimized density formula:(6)ρi=∑j∈D/iχ1+Edij-dc.Formula (6) makes distinction among different attributes using the Euclidean distance control factor based on aggregation density sparse degree E. The attributes with large differences are given more weights’ computing density, which reduces the risk of misjudged data. The optimized density is multidimensional diffusion density:(7)Zρ=ρ¯+δρ,where ρ¯ is the average of multidimensional diffusion density ρi and δρ is the standard deviation of multidimensional diffusion density. Zρ is standard value of multidimensional diffusion density. Let the data whose multidimensional diffusion density is bigger than Zρ in a collection named B:(8)σ=σi=min⁡dij,ρi<ρj,σi=max⁡dijρimax⁡Xi,Xj∈B.σ is the distance between Xi and Xj, and both of them are from collection B:(9)Zσ=σ¯+δσ,where σ¯ is the average of distance between the data from collection B. And δσ is the standard deviation of distance between the data from collection B. Zσ is standard value of distance. Let the data whose distance is bigger than Zσ be in a collection named C. Reference [19] shows that the initial cluster centers have the large density and the far distance. So the data in collection C are likely to be initial cluster centers. We choose them as the initial cluster centers of initial data clusters.


## 2.1.3. Obtaining Initial Data Clusters by Multidimensional Diffusion Density Distribution

In this subsection we present execution steps of our proposed initial data clustering using multidimensional diffusion density distribution fork-means clustering. This algorithm consists of two parts. The first part deals with the the initial cluster centers of the initial data. Then we execute the second part of the algorithm to group the data.D = { x 1 , x 2 , … , x n }, which is the set of n data elements described with attributes A1,A2,…,Am where m is number of attributes and all attributes are numeric. Compute ρi of each data, mean ρ¯, standard deviation δρ, and Zρ. Choose the data whose ρi is bigger than Zρ, and put them into collection B. Compute σ of each piece of data in B collection, σ¯, standard deviation δσ, and Zσ. Choose the data whose σ is bigger than Zσ and put them into C collection, C=c1,c2,…,ck′ is the set of the initial cluster centers of the initial data, and k′ is the number of the initial cluster centers:(10)dXi,cj=∑a=1mXiAa-cjAa2,i=1,…,n;j=i,…,k′.d ( X i , c j ) measures the Euclidean distance between a pattern Xi and its cluster center cj that is in the C collection.k-means algorithm minimizes the function which is defined as object function [18]:(11)JMSE=∑i=1k′∑xj∈Cixj-cj2.Thek-means algorithm groups the data iteratively as follows. Choose the data in C collection as the initial cluster centers and the number of them is k′, the number of initial data clusters. Decide membership of the patterns in one of the K-clusters according to the minimum distance from cluster center criteria. Then calculate new cj centers as: (12)cj=1N∑Xi∈cjXi.N is the number of data from which the jth cluster center of. Repeat the previous steps till there is no change in cluster centers. The clusters are the initial data clusters. Let W=w1,w2,…,wk′,Wi=x1,x2,…,xN be a clusters set of the initial data clusters.


## 2.2. Multiobjective Clustering Approach Based on Dynamic Cumulative Entropy

Obtaining the initial data clusters by multidimensional diffusion density distribution is the primary data processing. To get the accurate clustering results we need to cluster again on the basis of it, and the initial data clusters are the basic elements.


### 2.2.1. Multiobjective Clustering Function Based on Dynamic Cumulative Entropy

In thek-means algorithm the object function is JMSE. But it is not suitable for optimizing the primary clusters of data and determining k, the number of clusters because JMSE decreases monotonously for the increase of the number of clusters. When JMSE reduced to the global minimum, the initial cluster centers are putted away from their data, which makes single data a cluster. So proposed objective function refers to the information of each initial data cluster in the process of the deepening clustering.The paper tries to solve the above problems by studying the clusters’ structure by informational entropy theory and the principle of Maximum Informational Entropy. We propose a multiobjective clustering functionJ based on dynamic cumulative entropy to determine the final clustering results. Firstly, we define the information entropy formula of cluster:(13)Hi=-∑i=1kPinln⁡Pin,where Pi is the number of data in the ith initial data clusters, n is the number of data to be clustered, and k is the number of clusters.According to the principle of Maximum Informational Entropy, if clusters have no elements, the information entropy is 0,H=0. When clusters tend to be stable and meet the condition that the numbers of elements belonging to different clusters Pi are very similar, the information entropy is maximum; Hmax=ln⁡k. Based on the information entropy formula (14) of cluster, we define the cluster structure equilibrium degree S:(14)Si=HiHmax=-∑i=1kPi/nln⁡Pi/nln⁡k′.S is time-varying entropy-to-maximum entropy ratio, which shows the balance degree of clusters and 0≤S≤1. When Si=0, cluster is in the most uneven condition. When Si=1 clusters are in ideal equilibrium state:(15)Y=1-S.Y is the degree of equilibrium gain, which reflects the cluster occupancy of data.Finally, we get the multiobjective clustering function based on dynamic cumulative entropyJ:(16)J=JMSE+∑i=1kYiR,where(17)R=2βkk-1∑i=1k∑j=1Pdci,cj.R is the average distance among the clusters. The multiobjective clustering function considers not only the distance among the cluster centers and its data influence on the clustering results, but also the amount of information. JMES decreases monotonically with the decreasing of distance among the cluster centers and its data influence on the clustering results. On the contrary, ∑i=1kYiR increases monotonically with the increasing of the number of the global clusters. So ∑i=1kYiR as restricting factor prevents the number of clusters k more than the real k for JMES decreasing. It improves the clustering accuracy and reliability when the number of clusters k is not determined.


### 2.2.2. Multiobjective Clustering Approach Based on Dynamic Cumulative Entropy

The initial data clustersW={w1,w2,…,wk′} by multidimensional diffusion density distribution need to be clustered again. The initial cluster centers C=c1,c2,…,ck′ are determined again by the distance-information decision graph.The less information of a cluster has, the smaller its uncertainty is and the more likely it is to be the final cluster. At the same time, the global classification is more stable. Formula for information of the initial data clusters is(18)Ici=-log⁡Pin,∑i=1k′Pi=n,i=1,2,…,k′.Calculate the distance among the initial data clusters:(19)β=βi=dmin⁡Mi,Mj,Ii<Ij,βi=dmax⁡Mi,Mj,Iimax,ij∈C,where Mi=1/N∑f=1NXf, Xf is the data from which the ith cluster center of.By the nature of the clustering, we can know that the cluster’s uncertainty should be small and the distance among clusters should be large. According to this, we can draw distance-information decision graph to determinek and the initial cluster centers. Take two-dimensional data for example, such as shown in Figure 1. Multidimensional diffusion density distribution obtains initial data clusters A, B, C, D, E, F, G, H, I, J, and K. Figure 2 is distance-information decision graph with the inverse of information of the initial data cluster as the horizontal axis (1/I) and the distance among initial data clusters as the longitudinal axis (β).Figure 1
Initial data cluster.Figure 2
Distance-information decision graph.By the distance-information decision graph we can see that initial data clustersA, H, D, and K have compared low information and large distance among clusters because the larger k value can expand the searching scope of solution space, which avoids ignoring the sparse clusters. The selection of the initial cluster centers can be expanded according to the distance-information decision graph. Select the respective average values m of initial data clusters A, H, D, K, G, and B as the initial cluster centers and k1 as 6; minimize the multiobjective clustering function with result J1. Select the respective average values m of initial data clusters A, H, D, K, and G as the initial cluster centers and k2 as 5; minimize the multiobjective clustering function with result J2. Select the respective average values m of initial data clusters A, H, D, and K as the initial cluster centers and k3 as 4; minimize the multiobjective clustering function with result J3. Then compare J1, J2, and J3; the minimum is the best choice.


## 2.2.1. Multiobjective Clustering Function Based on Dynamic Cumulative Entropy

In thek-means algorithm the object function is JMSE. But it is not suitable for optimizing the primary clusters of data and determining k, the number of clusters because JMSE decreases monotonously for the increase of the number of clusters. When JMSE reduced to the global minimum, the initial cluster centers are putted away from their data, which makes single data a cluster. So proposed objective function refers to the information of each initial data cluster in the process of the deepening clustering.The paper tries to solve the above problems by studying the clusters’ structure by informational entropy theory and the principle of Maximum Informational Entropy. We propose a multiobjective clustering functionJ based on dynamic cumulative entropy to determine the final clustering results. Firstly, we define the information entropy formula of cluster:(13)Hi=-∑i=1kPinln⁡Pin,where Pi is the number of data in the ith initial data clusters, n is the number of data to be clustered, and k is the number of clusters.According to the principle of Maximum Informational Entropy, if clusters have no elements, the information entropy is 0,H=0. When clusters tend to be stable and meet the condition that the numbers of elements belonging to different clusters Pi are very similar, the information entropy is maximum; Hmax=ln⁡k. Based on the information entropy formula (14) of cluster, we define the cluster structure equilibrium degree S:(14)Si=HiHmax=-∑i=1kPi/nln⁡Pi/nln⁡k′.S is time-varying entropy-to-maximum entropy ratio, which shows the balance degree of clusters and 0≤S≤1. When Si=0, cluster is in the most uneven condition. When Si=1 clusters are in ideal equilibrium state:(15)Y=1-S.Y is the degree of equilibrium gain, which reflects the cluster occupancy of data.Finally, we get the multiobjective clustering function based on dynamic cumulative entropyJ:(16)J=JMSE+∑i=1kYiR,where(17)R=2βkk-1∑i=1k∑j=1Pdci,cj.R is the average distance among the clusters. The multiobjective clustering function considers not only the distance among the cluster centers and its data influence on the clustering results, but also the amount of information. JMES decreases monotonically with the decreasing of distance among the cluster centers and its data influence on the clustering results. On the contrary, ∑i=1kYiR increases monotonically with the increasing of the number of the global clusters. So ∑i=1kYiR as restricting factor prevents the number of clusters k more than the real k for JMES decreasing. It improves the clustering accuracy and reliability when the number of clusters k is not determined.


## 2.2.2. Multiobjective Clustering Approach Based on Dynamic Cumulative Entropy

The initial data clustersW={w1,w2,…,wk′} by multidimensional diffusion density distribution need to be clustered again. The initial cluster centers C=c1,c2,…,ck′ are determined again by the distance-information decision graph.The less information of a cluster has, the smaller its uncertainty is and the more likely it is to be the final cluster. At the same time, the global classification is more stable. Formula for information of the initial data clusters is(18)Ici=-log⁡Pin,∑i=1k′Pi=n,i=1,2,…,k′.Calculate the distance among the initial data clusters:(19)β=βi=dmin⁡Mi,Mj,Ii<Ij,βi=dmax⁡Mi,Mj,Iimax,ij∈C,where Mi=1/N∑f=1NXf, Xf is the data from which the ith cluster center of.By the nature of the clustering, we can know that the cluster’s uncertainty should be small and the distance among clusters should be large. According to this, we can draw distance-information decision graph to determinek and the initial cluster centers. Take two-dimensional data for example, such as shown in Figure 1. Multidimensional diffusion density distribution obtains initial data clusters A, B, C, D, E, F, G, H, I, J, and K. Figure 2 is distance-information decision graph with the inverse of information of the initial data cluster as the horizontal axis (1/I) and the distance among initial data clusters as the longitudinal axis (β).Figure 1
Initial data cluster.Figure 2
Distance-information decision graph.By the distance-information decision graph we can see that initial data clustersA, H, D, and K have compared low information and large distance among clusters because the larger k value can expand the searching scope of solution space, which avoids ignoring the sparse clusters. The selection of the initial cluster centers can be expanded according to the distance-information decision graph. Select the respective average values m of initial data clusters A, H, D, K, G, and B as the initial cluster centers and k1 as 6; minimize the multiobjective clustering function with result J1. Select the respective average values m of initial data clusters A, H, D, K, and G as the initial cluster centers and k2 as 5; minimize the multiobjective clustering function with result J2. Select the respective average values m of initial data clusters A, H, D, and K as the initial cluster centers and k3 as 4; minimize the multiobjective clustering function with result J3. Then compare J1, J2, and J3; the minimum is the best choice.


## 3. Experimental Results and Analysis

### 3.1. Experimental Objects and Related Settings

All experiments were performed on Intel® Core™ i5 with 3.30 GHz CPU and 4.00 GB of random access memory (RAM). All programs were coded by standard MATLAB language and operating system was Windows 7. To show the accuracy of the proposed algorithm, it has been applied to the two types of data sets. One is the AR artificial data set from experimental data and the other is UCI data. To define the quality of proposed algorithm we use 4 indicators. They are accuracy, Adjust Rand Index, MSE, and BIC. The “Adjusted Rand index” is the best clustering validity evaluation criterion [20]. And BIC is often used as an the accurate evaluation [21]. Because the value of MSE is large, the results of it are scaled down. The MSE is different from other indicators; it is the smaller the better.In this paper, an experimental system is used to evaluate the effectiveness of the proposed approach. A wireless information collection system of field soil temperature and humidity is used in this work to obtain the real data sets. The measurement system is shown in Figure3. The field soil temperature is measured by TM-100 and humidity is measured by SP40A. The TM-100 measuring range is from 0% to 100%, and the SP40A measuring range is from −20°C to 60°C. The JN5148 is used for receiving and transmitting the soil temperature and humidity data. Then the data is controlled and recorded digitally by a pc. The measurements were performed in four fields. So the record data are from four real data sets. The collecting places are shown in Figure 4. Table 1 shows the measurements data named artificial data AR. The artificial data AR that sets two-dimensional distribution is shown in Figure 5.Table 1
The artificial data AR.
Cluster Cluster center Data range Number of samples Cluster 1 (10,25) [2,15] 110 Cluster 2 (24,25) [15,29] 80 Cluster 3 (18,9) [10,25] 120 Cluster 4 (35,10) [27,40] 80Figure 3
Field soil temperature and humidity collection system.Figure 4
Four fields for measurement.Figure 5
The artificial data AR.The AR artificial data set clusters by the proposed algorithm in this paper. Multidimensional diffusion density distribution obtains initial data clusters. The proposedZρ of AR is 37, and the Zσ of AR is 2.97. The data samples with ρi bigger than Zρ and σ bigger than Zσ are putted into C. And k′=11, C=(5.6,28.0), (5.1,24.6), (10.7,24.4), (19.2,25), (24.8,27.4), (26.3,22.5), (18.9,12.8), (11.3,8.2), (19.1,6.6), (31.7,14.3), (35.4,6.5). The elements in C are the initial cluster centers of the initial data. We obtain initial data clusters A, B, C, D, E, F, J, H, I, G, and K by using multidimensional diffusion density distribution. The results are shown in Figure 6.Figure 6
Initial data clusters.The optimal clustering result is obtained by using the multiobjective clustering approach based on dynamic cumulative entropy. The information and the distance among the initial data clusters are obtained by the proposed formula.The distance-information decision graph is shown in Figure7. From the graph we can clearly see that the uncertainty of initial data clusters G, C, E, and J is low and the distance among them is large. So we select the respective average values m of initial data clusters G, C, E, J, and H as the initial cluster centers and k1 value as 5 and calculate the minimum of J. Then we select the respective average values m of initial data cluster G, C, E, J as the initial cluster centers and k2 value as 4 and calculate the minimum of J. From the proposed formula J1=247.49, J2=218.36, so the optimal number of clusters is 4. And the optimal clustering result is shown in Figure 8.Figure 7
Distance-information decision graph.Figure 8
The optimal clustering result.We get the cluster centers of AR. They are (10.2, 26.2), (23.7, 26.4), (17.8, 9.1), and (36, 10.5). And the real cluster centers are (10, 25), (24, 25), (18, 9),and (35, 10). The similarity between our cluster centers and the real cluster centers is 95.582%, 97.628%, 99.337%, and 96.968%. The average value of similarity of cluster centers is 94.72%, the clustering accuracy is 92.14%, Adjust Rand Index is 0.7840, and MSE (Mean Squared Error) is 3.82.The AR artificial data is clustered by [11, 15]. The comparisons of cluster center’s similarity and clustering result’s accuracy and Adjust Rand Index and MSE, using our algorithm and literature [11, 15], for AR data sets, are shown in Figures 9, 10, 11, 12, and 13.Figure 9
The comparisons of cluster center’s similarity.Figure 10
The comparisons of clustering results accuracy.Figure 11
The comparisons of Adjust Rand Index.Figure 12
The comparisons of MSE.Figure 13
The comparisons of BIC.The comparison of similarity of initial cluster centers computed using our algorithm and [11, 15], for the AR data set, is shown in Figure 9. The algorithm with high value will have a good selection of cluster centers. The result of our algorithm has the highest value of similarity of initial cluster centers. What is more, for the other numerous measures used for clustering validation, the accuracy, Adjust Rand Index MSE, and BIC, our algorithm has better performance than other algorithms.Obviously, our algorithm can find the optimal clustering numberk and the optimal cluster center to get the best clustering result, which provides the accuracy of clustering.


### 3.2. Experimental Results and Comparative Analysis of UCI Data Sets

In order to verify the effectiveness of the our algorithm, this paper selects 8 data sets of UCI data to carry out the experiment. They are Iris(150∗4∗3), Soybean • small (47∗35∗4), Segmentation (210∗19∗7), WDBC (569∗30∗2), Pima Indians Diabetes (768∗8∗2), Wine (178∗13∗3), Ionosphere (351∗34∗2), and Yeast (1484∗8∗10). Clustering results use the clustering time, clustering accuracy, the “Rand index Adjusted,” and MSE for evaluation. Table 2 shows the comparison of average of the running time of clustering algorithms; the unit is S. Figures 14, 15, 16, and 17 are the comparisons about the clustering accuracy, the “Rand index Adjusted,” MSE, and the BIC of our algorithm and [11, 15].Table 2
Comparison of running time on UCI data set.
DS Reference [11] Reference [15] Our algorithm Soybean • small 1.83 2.056 2.169 Iris 2.89 2.962 2.984 Segmentation 2.883 3.055 3.087 WDBC 3.142 3.436 3.541 Pima Indians Diabetes 4.780 4.985 5.001 Wine 7.106 7.938 7.942 Ionosphere 9.488 9.647 9.884 Yeast 17.219 17.863 17.894Figure 14
Comparison of the accuracy for UCI data.Figure 15
Comparison of the Adjust Rand Index for UCI data.Figure 16
Comparison of the MSE for UCI data.Figure 17
Comparison of the BIC for UCI data.According to clustering results of UCI data we can see that for all the tested data sets, the proposed algorithm gets improved and consistent clusters for all data sets in comparison to [11, 15]. Its accuracy for complicated data sets also was high. However, the algorithm of [11] is quicker than the proposed algorithm.


## 3.1. Experimental Objects and Related Settings

All experiments were performed on Intel® Core™ i5 with 3.30 GHz CPU and 4.00 GB of random access memory (RAM). All programs were coded by standard MATLAB language and operating system was Windows 7. To show the accuracy of the proposed algorithm, it has been applied to the two types of data sets. One is the AR artificial data set from experimental data and the other is UCI data. To define the quality of proposed algorithm we use 4 indicators. They are accuracy, Adjust Rand Index, MSE, and BIC. The “Adjusted Rand index” is the best clustering validity evaluation criterion [20]. And BIC is often used as an the accurate evaluation [21]. Because the value of MSE is large, the results of it are scaled down. The MSE is different from other indicators; it is the smaller the better.In this paper, an experimental system is used to evaluate the effectiveness of the proposed approach. A wireless information collection system of field soil temperature and humidity is used in this work to obtain the real data sets. The measurement system is shown in Figure3. The field soil temperature is measured by TM-100 and humidity is measured by SP40A. The TM-100 measuring range is from 0% to 100%, and the SP40A measuring range is from −20°C to 60°C. The JN5148 is used for receiving and transmitting the soil temperature and humidity data. Then the data is controlled and recorded digitally by a pc. The measurements were performed in four fields. So the record data are from four real data sets. The collecting places are shown in Figure 4. Table 1 shows the measurements data named artificial data AR. The artificial data AR that sets two-dimensional distribution is shown in Figure 5.Table 1
The artificial data AR.
Cluster Cluster center Data range Number of samples Cluster 1 (10,25) [2,15] 110 Cluster 2 (24,25) [15,29] 80 Cluster 3 (18,9) [10,25] 120 Cluster 4 (35,10) [27,40] 80Figure 3
Field soil temperature and humidity collection system.Figure 4
Four fields for measurement.Figure 5
The artificial data AR.The AR artificial data set clusters by the proposed algorithm in this paper. Multidimensional diffusion density distribution obtains initial data clusters. The proposedZρ of AR is 37, and the Zσ of AR is 2.97. The data samples with ρi bigger than Zρ and σ bigger than Zσ are putted into C. And k′=11, C=(5.6,28.0), (5.1,24.6), (10.7,24.4), (19.2,25), (24.8,27.4), (26.3,22.5), (18.9,12.8), (11.3,8.2), (19.1,6.6), (31.7,14.3), (35.4,6.5). The elements in C are the initial cluster centers of the initial data. We obtain initial data clusters A, B, C, D, E, F, J, H, I, G, and K by using multidimensional diffusion density distribution. The results are shown in Figure 6.Figure 6
Initial data clusters.The optimal clustering result is obtained by using the multiobjective clustering approach based on dynamic cumulative entropy. The information and the distance among the initial data clusters are obtained by the proposed formula.The distance-information decision graph is shown in Figure7. From the graph we can clearly see that the uncertainty of initial data clusters G, C, E, and J is low and the distance among them is large. So we select the respective average values m of initial data clusters G, C, E, J, and H as the initial cluster centers and k1 value as 5 and calculate the minimum of J. Then we select the respective average values m of initial data cluster G, C, E, J as the initial cluster centers and k2 value as 4 and calculate the minimum of J. From the proposed formula J1=247.49, J2=218.36, so the optimal number of clusters is 4. And the optimal clustering result is shown in Figure 8.Figure 7
Distance-information decision graph.Figure 8
The optimal clustering result.We get the cluster centers of AR. They are (10.2, 26.2), (23.7, 26.4), (17.8, 9.1), and (36, 10.5). And the real cluster centers are (10, 25), (24, 25), (18, 9),and (35, 10). The similarity between our cluster centers and the real cluster centers is 95.582%, 97.628%, 99.337%, and 96.968%. The average value of similarity of cluster centers is 94.72%, the clustering accuracy is 92.14%, Adjust Rand Index is 0.7840, and MSE (Mean Squared Error) is 3.82.The AR artificial data is clustered by [11, 15]. The comparisons of cluster center’s similarity and clustering result’s accuracy and Adjust Rand Index and MSE, using our algorithm and literature [11, 15], for AR data sets, are shown in Figures 9, 10, 11, 12, and 13.Figure 9
The comparisons of cluster center’s similarity.Figure 10
The comparisons of clustering results accuracy.Figure 11
The comparisons of Adjust Rand Index.Figure 12
The comparisons of MSE.Figure 13
The comparisons of BIC.The comparison of similarity of initial cluster centers computed using our algorithm and [11, 15], for the AR data set, is shown in Figure 9. The algorithm with high value will have a good selection of cluster centers. The result of our algorithm has the highest value of similarity of initial cluster centers. What is more, for the other numerous measures used for clustering validation, the accuracy, Adjust Rand Index MSE, and BIC, our algorithm has better performance than other algorithms.Obviously, our algorithm can find the optimal clustering numberk and the optimal cluster center to get the best clustering result, which provides the accuracy of clustering.


## 3.2. Experimental Results and Comparative Analysis of UCI Data Sets

In order to verify the effectiveness of the our algorithm, this paper selects 8 data sets of UCI data to carry out the experiment. They are Iris(150∗4∗3), Soybean • small (47∗35∗4), Segmentation (210∗19∗7), WDBC (569∗30∗2), Pima Indians Diabetes (768∗8∗2), Wine (178∗13∗3), Ionosphere (351∗34∗2), and Yeast (1484∗8∗10). Clustering results use the clustering time, clustering accuracy, the “Rand index Adjusted,” and MSE for evaluation. Table 2 shows the comparison of average of the running time of clustering algorithms; the unit is S. Figures 14, 15, 16, and 17 are the comparisons about the clustering accuracy, the “Rand index Adjusted,” MSE, and the BIC of our algorithm and [11, 15].Table 2
Comparison of running time on UCI data set.
DS Reference [11] Reference [15] Our algorithm Soybean • small 1.83 2.056 2.169 Iris 2.89 2.962 2.984 Segmentation 2.883 3.055 3.087 WDBC 3.142 3.436 3.541 Pima Indians Diabetes 4.780 4.985 5.001 Wine 7.106 7.938 7.942 Ionosphere 9.488 9.647 9.884 Yeast 17.219 17.863 17.894Figure 14
Comparison of the accuracy for UCI data.Figure 15
Comparison of the Adjust Rand Index for UCI data.Figure 16
Comparison of the MSE for UCI data.Figure 17
Comparison of the BIC for UCI data.According to clustering results of UCI data we can see that for all the tested data sets, the proposed algorithm gets improved and consistent clusters for all data sets in comparison to [11, 15]. Its accuracy for complicated data sets also was high. However, the algorithm of [11] is quicker than the proposed algorithm.


## 4. Conclusion

We have presented an algorithm for iterative clustering algorithm with a small amount of prior knowledge for nonuniform sparse data. This procedure is based on the dynamic cumulative entropy. However, the outliers are more susceptible to a change in cluster membership. We propose multidimensional diffusion density distribution in computing initial cluster centers, which generate the initial data clusters that may be more than the number of desired clusters. So we need to cluster again on the basis of them for getting the accurate clustering results by multiobjective clustering approach based on dynamic cumulative entropy. Experimental results show improved and consistent cluster structures. And the experimental results show that compared with full search, our proposed method may got production up by 5 percent for nonuniform sparse data set from field soil temperature and humidity. The superiority of our method over other algorithms is more remarkable, when a data set with higher data dimension and larger number of clusters is used. And our method handles clustering with little prior knowledge, so our method is at high complexity.Following our paper, several interesting problems deserve to be explored, for example, how to reduce computation and enhance the algorithm speed with a similar approximation ratio. To generalize our method to the setting of arbitrary partition is also challenging but useful in some scenarios.



---

*Source: 5707692-2016-11-21.xml*