Clustering [1] is a basic means of data mining in the current big data era, which has been used in many fields such as pattern recognition, image segmentation, and deep learning. Because traditional data clustering methods have certain limitations in processing data, such as low classification accuracy, low efficiency, and poor feasibility, more and more new clustering algorithms have been proposed, such as spectral clustering [2], kernel clustering [3], and integrated clustering [4]. The AP clustering algorithm proposed by Frey et al. [5] quickly became popular due to its fast and effective treatment.

The AP clustering is an algorithm based on the message passing between data points and mainly analyzes the clustering based on the similarity between samples. The algorithm considers each data point as a potential coalescence and effectively weakens the influence of the original center on the clustering effect. However, with the increase of the current data scale and data type, the process of clustering algorithm involves a large amount of computation, thus determining how to preprocess the initial dataset is particularly critical. It is also important to obtain an accurate similarity since the messages r(i, k) and a(i, k) transmitted between AP clustering data points are calculatedon the basis of similarity. [6] proposed a Map/Reduce AP clustering algorithm (MRAP) implemented in the distributed cloud environment Hadoop. Experiments with the K-means algorithm showed that the algorithm has high accuracy and short processing time. [7] proposed a MapReduce-based Distributed AP Clustering Algorithm (DisAP), which randomly divides data points into similarly sized subsets and performs sparse processing to improve the speed and accuracy of the algorithm. [8] proposed a layered AP clustering algorithm (HAP) for large-scale data. This algorithm can adaptively adjust the bias parameters. Compared with AP clustering and adaptive AP clustering, it can ensure the clustering effect and reduce the time energy consumption of clustering. As the AP clustering process needs multiple iterations to update the attractivity matrix R and the attribution matrix A, the clustering operation is slower. For this reason, [9] proposed a map/reduce AP clustering method based on Hadoop. The algorithm is performed after partitioning the data in the map phase, and the clustering results are merged in the reduce stage. Although the algorithm reduces the clustering iterations of the process, its clustering effect is easily affected by the merging strategy. Therefore, how to improve the operating efficiency of the algorithm while maintaining the original clustering effect is worth considering.

In order to solve the above problems, this paper proposes a coarse-grained parallel AP clustering algorithm based on intra-class and inter-class distance: IOCAP. The algorithm first proposes a coarse-grained partitioning strategy, which roughly divides the original dataset to be clustered into multiple subsets and initially reduces the complexity of the problem. Afterwards, the intra-class and inter-class distances are introduced to calculate the similarity in the AP algorithm, which can improve the accuracy of the clustering algorithm. Finally, the algorithm is arranged on the MapReduce model to achieve the parallelization of the AP clustering and improve the efficiency of the algorithm.

The granularity is initially used in the data warehouse to represent the data refinement and integration level of the data unit. Grains have different granularity, that is, the size of the grain. The calculation of granularity is mainly to simplify the cognition of things, thus reducing the complexity of problem solving.

According to the refinement standard of data granularity, the higher the degree of refinement, the smaller the granularity. Conversely, the lower the refinement degree, the greater the granularity. In parallel computing, the program needs to be divided according to parallel conditions to obtain parallel equivalent particles of different sizes. In some cases, the calculation can be completed by using a coarser granularity, but in some cases the granularity must be refined [10] before proceeding. The introduction of granularity can reduce the size of clustering data and effectively improve the efficiency of clustering algorithm. However, it is not uniform and unreasonable to divide the program only based on the parallel equivalent particles. With the refinement of the calculation granularity, the total traffic will increase, resulting in greater overhead. Therefore, how to scientifically and reasonably determine the granularity to divide a dataset has become an important issue in current research.

AP clustering is an algorithm based on message passing between data points. It mainly passes two types of messages: responsibility and availability [11]. The algorithm does not need to set the number of clusters in advance, and the most suitable clustering can be determined based on the communication between the data points.

The AP algorithm performs clustering calculations based on the similarity [12], where characteristics are symmetrical or asymmetrical. Among them, symmetry refers to the similarity between two data points and asymmetry refers to the dissimilarity between two data points. The similarity of s(i, j) is set to the N×N similarity matrix S. The diagonal values on the matrix S are s(k, k); the larger the value is, the more likely it will become the center of the cluster, which is also called the bias parameter p(k)=s(i, i). Introduce the responsibility matrix R=[r(i, k)] and the availability matrix A=[a(i, k)], where r(i, k) is a message that is sent by pointing i to the candidate cluster center k, indicating the degree to which the data point k is suitable as the clustering center of the data point i. a(i,k) is the message that is sent from k to the data point i, indicating the fitness of the data point ifor selecting the data point k as its clustering center. The iterative formula is as follows:

Among Equations (1) and (2), $a(i,{k}')$ represents the recognition (availability) degree of the data point i to the point ${k}'$, and $r({i}',k)$ represents the degree of availability of the data point k to other data points.

The AP algorithm continuously updates the availability and the attribution value of each data point through an iterative process until multiple high-quality cluster centers are generated, and the remaining data points are assigned to the corresponding clusters. Because the vibration is easily generated when parameters are updated in the clustering process, the damping coefficient dampneedsbe introduced to converge:

In Equations (3) and (4),${R}'$and${A}'$ represent the information values for the previous iteration. The value of damp is set between 0 and 1,and it is set to 0.5 in this paper.

In this section, the coarse-grained partitioning is first introduced to roughly classify clustered datasets, and then it combines intra-class and inter-class distance for similarity calculation to improve the AP clustering algorithm. On this basis, this paper proposes a parallel improved AP clustering algorithm based on MapReduce: IOCAP.

With the expansion of the scale and type of big data, the ability of data mining processing has become an increasingly prominent problem. The extensive application of parallel clustering technology effectively alleviates the low efficiency of clustering algorithms. In parallel computing, the granularity is used to divide the dataset, and as many parallel particles as possible are found simplify the dataset to improve the efficiency of data processing. However, because many datasets are not parallel to a certain size, it is necessary to divide them in order to find the appropriate size of the particles to form different data subsets of the granularity level, which helps reduce the noise data and makes the dataset have greater parallelism.

This paper divides the data based on the coarse-grained strategy. Set the sample dataset $\text{M}=\{{{m}_{1}},\text{ }{{m}_{2}},\text{ }\cdots ,\text{ }{{m}_{\ell }}\}$, which contains $\ell $ sample objects. The distance(Euclidean distance) between any data is dist(d_i,d_j),and the granularity variable is Gv, which represents the fusion radius of the data origin. The Equation (5) is:

According to Gv, the distance between two sample data is less than Gv, the adjacent data are initiallydivided into multiple sample clusters, and the sample cluster mean(geometric center) avg represents the cluster.For (m₁, m₂), (m₂, m₃), and (m₃, m₄)sample point pairs, calculate the Euclidean distance [13] between every two sample points. If the distance between sample points is less than Gvand these points are distributed adjacently, they can be divided into the same cluster, and the mean avg is used to represent the cluster. The initial cluster centeris selected through different levels of granularity. The dataset is divided based on the coarse-grained strategy aims to preprocess the initial dataset.The selection of coarse-grained particles can effectively avoid the increase of traffic caused by the high granularity of the data unit, thereby improving the efficiency of the AP clustering algorithm.

The steps for dividing a dataset based on a coarse-grained strategy are as follows:

Step 1 The sample points in the sample dataset $\text{M}=\{{{m}_{1}},\text{ }{{m}_{2}},\text{ }\cdots ,\text{ }{{m}_{\ell }}\}$ are stored in an adjacent distance matrixNdm=Nn×Nn, where Nn is the total number of data of the dataset M, and each row of the matrix represents the distance between the data m₁ in the dataset M and other data.

Step 2 Initialize the granularity variable Gv.The matrix Nm is divided by the granularity variable Gv, and the fused data are divided into a single sample cluster C={avg₁, avg₂, ⋯,avg_i}.

Step 3 Rank the sample clustersrank(AVG_i), which areobtained according to the pre-defined size.

Step 4 Observe the ranking results and propose the sample clusters with the highest n granularity levels as the initial clustering of the AP clustering algorithm.

Step 5 Remove noise points with a granularity level of 1 and output new datasets U={u₁, u₂, ⋯, u_n}.

3.2.1. Intra-Class and Inter-Class Distances

Since the AP algorithm implements clustering mainly through the similarity matrix between sample data, the calculation of the similarity matrix is extremely important and is related to the accuracy of the clustering result. The AP algorithm generally determines the clustering based on the Euclidean metric, which is a typical dissimilarity measure. Its calculation formula is as follows:

In Equation (6), D represents a function D: X×X→R, x, y∈X and where x_i, y_i represent the i^th and j^th coordinates of x and y respectively. Although the calculation of Euclidean distance is more intuitive, it does not take into account the random fluctuations that the measurement values may have and the effect of isolated points on the dispersion between classes in the sample data, so there are certain limitations.

In this paper, the intra-class distance and inter-class distance [14] are used to judge the similarity between data points to determine the optimal number of clustering samples and strengthen the clustering effect of the AP algorithm. The dataset U={u₁,u₂, ⋯,u_n} was obtained through a coarse-grained strategy division. Set the result set of the clustering for $\{{{{u}'}_{1}}\text{, }{{{u}'}_{2}}\text{, }\cdots ,\text{ }{{{u}'}_{k}}\}$. The average distance between the data object x_i in the cluster T_j and all other data objects belonging to the cluster is the intra-class distance:

In Equation (7), $u_{ik}^{j}$ represents the k^th dimension data of the data object u_iin the class T_j, and n_i represents the total number of data objects in the T_j. The intra-class distance can describe the degree of similarity between data elements within a class, so the smaller the value, the better.

The average distance between the data object x_i in the cluster T_j and all classes other than T_j, that is, the inter-class distance, is:

In Equation (8),t_hk represents the k^th dimensional data of data center t_h in classT_h. The inter-class distance E(i, j) represents the average distance between objects in the class and other class objects, so the larger the value, the better.

The similarity that includes the intra-class distance and inter-class distances is calculated as follows:

From Equation (9),when the intra-class distance is small and the class spacing is large, the clustering effect is best when the value IG(i, j) is close to 1, and the clustering effect is poor when the value IG(i, j) is close to -1.

3.2.2. Improved AP Clustering with Coarse-Grained Partitioning

By using intra-class and inter-class distances to construct the similarity between sample data points, the clustering algorithm can simultaneously consider the degree of closeness within sample classes and the degree of dispersion between sample classes. Assuming that there are n data that constitute the similarity matrix of N×N, ${S}'(i,j)$ is the degree of similarity between sample data points i and j, according to Equation (10):

The clustering center can be evaluated by the diagonal element value${S}'(i,j)$of the matrix${S}'.$The clustering effect is optimal when the value of ${S}'(i,j)$ tends to 1.

The coarse-grained AP clustering algorithm based on intra-class and inter-class distances first selects suitable coarse particles to preprocess the original dataset. After fusion, the sample datasets are divided into n subsets. Then, the similarity of data points in each subset is calculated by intra-class and inter-class distances. AP clustering is carried out to generate clustering sets. The specific process is shown in Algorithm 1.

Algorithm 1 Coarse-grained AP clustering algorithm based on intra-class and inter-class distances

Input: Dataset Z={z₁, z₂, ⋯,z_n}, where n represents the number of data points; Granularity variable Gv; Improved similarity matrix ${S}'\text{=}{S}'(i,j)$; Responsibility matrix R=[r(i,k)]; Availability matrix A=[a(i,k)]; Bias parameter p(k), number of iterations t

Output: Clustering result set and clustering center

Step 1 According to the coarse-grained strategy, the dataset is coarsely divided

1. Initialization: Initialize the granularity variable Gv;

2. Save the sample data in the dataset Z into the matrix Ndm;

3. Calculate the variable Gv according to Equation (5), and then subdivide the data that is smaller than Gv and adjacent data to clusters C(avg_i);

4. After calculating the mean value avg_i, the cluster of data is ranked according to the set coarse particles, and the clusters with the highest k levels are taken out;

5. Get a new dataset;

Step 2 Find the matrix R and A for the divided dataset U

1. Initialization: Let the similarity ${s}'(k,k)$ be the same value and assign it to the parameter p; let r(i,k)=0, a(i,k)=0 and store them in the matrix R and A respectively; Damping coefficient damp=0.5;

2. ${R}'$=R, ${A}'$=A;

3. Take the (t-1) times running results of A and the t iterations of R separately;

4. Calculate R according to the Equation, which represents the similarity calculated from the introduced intra-class and inter-class distances, and calculate A according to Equation (2);

5. When $k={k}',$ calculating r(k, k) according to the formula $r(k,\text{ }k)=p(k)-\max \{a(k,\text{ }{k}')+{s}'(k,\text{ }{k}')\}$ and put it into R and calculating a(k, k) according to Equation (2) and stored in A;

6. R=damp×${R}'$+(1-damp)×R, A=damp×${A}'$+(1-damp)×A;

7. Save the results of the t iterations of R and A respectively;

Step 3 Determine if the iteration end condition is satisfied

1. The clustering center remains stable after multiple iterations of updates;

2. The prescribed number of iteration exceeds the limits;

If one of the above conditions is satisfied, stopping iterating and go to Step 4, otherwise go back to Step 2.

Step 4 Output the final clustering result set and clustering center.

After coarse-grained AP clustering based on intra-class and inter-class distances, the MapReduce model [15] was used to optimize the algorithm by parallelizing the improved AP clustering. The IOCAP algorithm mainly includes two MapReduce processes in Figure 1. The first stage is to perform parallel AP clustering on the granularity-divided subsets, including Mapper1 and Reducer1, where Mapper1 acquires n datasets after granularity partitioning and Reducer1 performs AP clustering on n datasets in parallel, resulting in cluster representative and cluster center. The second stage consists of Mapper2 and Reducer2, which use the cluster representation formed in the first stage to indicate the final polycentricity for all data points.

The MapReduce process corresponding to the IOCAP algorithm is specifically expressed as follows:

Algorithm 2 IOCAP algorithm

Step 1 IOCAP Mapper1 algorithm

Input: Line number key of the dataset U, data unit $value {{u}_{\varepsilon }}$and the amount of data divided n

Output: key-value pair $\text{}ke{y}',\text{ }valu{e}'\text{}$, which $ke{y}'$ represents the cluster’s label, $valu{e}'$ represents the data unit

1. Get data subset U={u₁, u₂, ⋯, u_n} according to the coarse-grained partitioning strategy, where ${{u}_{\varepsilon }}\subseteq \text{U},\text{ }\varepsilon =1,\text{ }2,\text{ }\cdots ,\text{ }n$, and ${{u}_{\varepsilon }}\cap {{u}_{\varphi }}=\varnothing $. Random number$\delta \in \text{ }\!\![\!\!\text{ 1},n\text{ }\!\!]\!\!\text{ }$was generated by the random number generator and set it as the cluster label;

2. Let $ke{y}'=\delta, \text{ }valu{e}'={{u}_{\varepsilon }}$, and output data key-value pairs $\text{}ke{y}',\text{ }valu{e}'\text{}$;

Step 2 IOCAP Reducer1 algorithm

Input:Cluster label key, data list vaList which containing the same key value, damping coefficient damp in AP clustering algorithm

Output: HDFS file, where each row represents the clustering representation h_i,i =1,2, ⋯,|H_n’| of the data partition

1. According to the data list vaList, the similarity matrix ${{{S}'}_{n}}$_’ and the bias parameters P_n’ are calculated by using the intra-class and inter-class distances (Equation (10));

2. The AP clustering is carried out through the similarity matrix ${{{S}'}_{n}}$_’ and the bias parameter P_n’, and the clustering representation is generated;

3. Store the data units h_i∈H_n’,i =1, 2, ⋯, |H_n’| in the collection H_n’ into the file;

Step 3 IOCAP Mapper2 algorithm

Input:Line number key of the dataset U, data unit $ value {{u}_{\varepsilon }}$

Output: key-value pair $\text{}ke{y}',\text{ }valu{e}'\text{}$, where $ke{y}'$ represents the cluster label $Num(\varepsilon )$, $valu{e}'$ represents the data unit ${{u}_{\varepsilon }}$

1. Mapper2 removes the cluster representation H_n’ from the cache;

2. Get the cluster representation H_n’ that is most similar to the data point ${{u}_{\varepsilon }}$in the cluster representative set$Num(\varepsilon )$;

3. Let $key'=Num(\varepsilon ),\text{ }valu{e}'={{u}_{\varepsilon }}$, and output data pairs $\text{}ke{y}',\text{ }valu{e}'\text{}$;

Step 4 IOCAP Reducer2 algorithm

1. Reducer2 summarizes the clustering results and outputs the final cluster and clustering center.

To verify the impact of the IOCAP algorithm on the clustering effect, experiments are performed using the Iris dataset [16], the Diabetes dataset, and the MNIST (hand written digital) dataset. K-means clustering, the classic AP algorithm, and the IOCAP algorithm are used to cluster three kinds of datasets respectively. The damping coefficient damp of the algorithm is set to 0.5, the maximum number of iterations is set to 1200, the value of the granularity variable Gv is set to 0.6, and the number of iterations that make the centroid remain stable is set to 120 times.

In order to measure the merits of the clustering algorithm, the ACC index [17], the Purity index, and the NMI index are introduced to measure the accuracy of the clustering algorithm.

4.2.1. ACC (Accuracy) Index

Among Equation (11), n represents the number of data points, and c_i and u_i represent the actual cluster label and the obtained cluster label respectively. $\delta (c,u)$indicates that when c=u, the function value is 1; otherwise, $\delta (c,u)=0.$ The map function maps the obtained cluster tag to the actual tag, and the map can be obtained using the Kuhn-Munkres algorithm [18]. The larger the ACC value, the closer the clustering result is to the actual cluster.

4.2.2. Purity Index

The Purity index is evaluated by calculating the proportion of the correct data in the cluster to the total data.

AmongEquation (12), n represents the number of data points,${{\psi }_{k}}\in \Psi ,k=1,2,\cdots ,\left| \left. \Psi \right| \right.$, and ${{\psi }_{k}}$is the set of the k^th cluster.$\Phi =\text{ }\!\!\{\!\!\text{ }{{\phi }_{\text{1}}},\text{ }{{\phi }_{\text{2}}},\text{ }\cdots ,\text{ }{{\phi }_{n}}\text{ }\!\!\}\!\!\text{ }$, and ${{\phi }_{j}}$ is the j^th data. Purity∈[0,1], andthe closer the Purity value is to 1, the more accurate the clustering result is.Otherwise, the closer the value is to 0, the higher the error rate clustering.

4.2.3. NMI (Normalized Mutual Information) Index

This indicator is often used to measure the similarity of two clustering. SetU and Vas the distribution of N sample data. The entropy (representing the degree of uncertainty) of the two distributions is shown in Equation (13):

Among them:

In Equation(14), P(i) is the number of data of cluster i, ${P}'(j)$ is the number of data of cluster j, and N represents the total number of data.

The mutual information (MI) between U and V is shown in Equation (15):

Among them:

In Equation(16), P(i, j) is the same number of data in the i^th cluster as in the real tag j.

The standardized MI, that is, NMI is shown in Equation(17):

The range of NMI values is [0,1], and the higher the value, the higher the degree of similarity between the two clusters.

1) The running time of the AP algorithm and the IOCAP algorithm on the three datasetsare calculated. The experimental result data is taken as the average of multiple runs. The details are shown in Table 1:

From the experimental results, it can be seen that for a smaller dataset, the running time of the IOCAP algorithm is not faster than that of the AP algorithm. However, for large-scale data, the IOCAP algorithm significantly shortens the clustering time and improves the efficiency of the algorithm. This is because the IOCAP algorithm first preprocesses the original dataset, that is, it reduces the data size through coarse-grained partitioning, and then combined with the MapReduce model, the divided subsets are clustered in parallel. Compared with the AP algorithm, the IOCAP algorithm has obvious advantages in the clustering of large datasets. However, for the smaller dataset, as a result of the IOCAP algorithm in data preprocessing, the calculation of the similarity matrix has occupied a certain time. Thisincreases the communication overhead and makes the algorithm efficiency decline.

2) In order to measure the pros and cons of the algorithm, the average ACC index, Purity index, and NMI index of the K-means algorithm, AP algorithm,and IOCAP algorithm on the three datasets are calculated and compared. In the experiment, each algorithm is executed 25 times and the average value of three indicators is taken.

a. Iris dataset

The Iris dataset contains 150 data points and three types, and each data corresponds to a 4-dimensional vector. The clustering performance of the three algorithms is shown in Table 2.

In this experiment, the number of clusters of the K-means algorithm is set to 3. As can be seen from Table 1, each index of the IOCAP algorithm is all improved compared to the AP algorithm on the cluster evaluation indexes ACC, Purity, and NMI. Because the K-means algorithm needs to specify the number of clusters in advance and there are large fluctuations in the clustering process, the algorithm is very unstableand there is a certain limit. Experiments show that the clustering effect of the IOCAP algorithm on the Iris dataset is better.

b. Diabetes dataset

The Diabetes dataset consists of 442 data, which are divided into four types. The clustering performance of the three algorithms is shown in Table 3.

In this experiment, the number of clusters of the K-means algorithm is set to 2. From Table 2, it can be seen that the IOCAP algorithm performs better on the ACC and purity indicators, but it is inferior to the AP algorithm on the NMI indicator. Compared with the K-means algorithm and AP algorithm, the IOCAP algorithm occupies a certain advantage.

c. MNIST dataset

The MNIST dataset contains 5620 hand-written digital data. The clustering performance of the three algorithms is shown in Table 4.

In this experiment, the number of clusters of the K-means algorithm is set to 40. From Table 4, it can be seen that the AP algorithm performs poorly on this dataset on a relatively large dataset, and the K-means algorithm performs relatively well. But the IOCAP algorithm is superior to other indicators. This shows that IOCAP algorithm has better clustering performance for large-scale datasets.

Through three comparison experiments and the combination of three evaluation indicators, the IOCAP algorithm is superior to the K-means algorithm and the AP algorithm as a whole. This shows that the algorithm guarantees the clustering efficiency to some extent and also improves the accuracy. Therefore, considering the time, accuracy, and communication overhead of clustering, the advantages of IOCAP are obvious, and it is also more suitable for efficient and accurate clustering of large datasets.

For the current high-dimensional and complex data processing in the era of big data, the classic AP clustering algorithm has been difficult to meet its needs. The IOCAP algorithm uses a coarse-grained idea to simplify the dataset initially and then improves the AP clustering algorithm by combining the concepts of intra-class and inter-class distances, which greatly improves the accuracy of the algorithm. A parallelized improved AP algorithm based on the MapReduce modelis then implemented. Later, the improved AP algorithm based on the MapReduce model to achieve parallelization improves the algorithm's ability to handle large-scale data and clustering efficiency. For the clustering of complex large datasets, the advantages of the IOCAP algorithm can be clearly seen. The next step is to explore the issue of how to optimize the granularity of parallel particles and the speedup of clustering operations when the structure and time-space relationship of big data arecomplex.

This work was partly financially supported through grants from the National Natural Science Foundation of China (No.61672470) andthe Open Issues of Beijing CityKey Laboratory (No.BKBD-2017KF08).