# High-Dimensional Text Clustering by Dimensionality Reduction and Improved Density Peak

Authors: Yujia Sun; Jan Platoš
Journal: Wireless Communications and Mobile Computing
 (2020)

---

## Abstract

This study focuses on high-dimensional text data clustering, given the inability of K-means to process high-dimensional data and the need to specify the number of clusters and randomly select the initial centers. We propose a Stacked-Random Projection dimensionality reduction framework and an enhanced K-means algorithm DPC-K-means based on the improved density peaks algorithm. The improved density peaks algorithm determines the number of clusters and the initial clustering centers of K-means. Our proposed algorithm is validated using seven text datasets. Experimental results show that this algorithm is suitable for clustering of text data by correcting the defects of K-means.


---

## Body

## 1. Introduction

Clustering is the main technique used for unsupervised information extraction. In clustering, the aim is to divide the unlabelled dataset into multiple nonoverlapping class clusters, making the data points in the cluster as similar as possible, while making the data points between the clusters as different as possible. In text clustering, text vectors are characterized by high dimension, sparsity, and correlation among dimensions, which requires improvements to the clustering algorithm to process high-dimension text [1, 2].When the K-means method is used to process high-dimensional data, the “Curse of Dimensionality” [3] problem becomes prominent, and the redundancy index also increases. Consequently, the conventional clustering method cannot process the data accurately. Some research [4–9] has proposed improvements on the text clustering algorithm, and some studies [10, 11] have proposed improvements on the K-means algorithm. To apply the K-means, it is necessary to specify the number of clusters in advance and randomly select the initial clustering centers. The clustering result is greatly influenced by the selection of the initial center point. Improper selection of the initial center can easily cause the clustering result trap into the local optimal solution and lead to an inaccurate clustering result.In recognition of these problems, we propose an enhanced K-means text clustering algorithm based on the clustering by fast search and find of density peaks (DPC) algorithm [12]. Since text-based data is usually high-dimensional and sparse, we propose a deep random projection dimensionality reduction framework, named Stacked-Random Projection (SRP), a greedy layer-wise architecture. We first use the dimensionality reduction method to reduce the dimension of the high-dimensional text feature vectors. Then use the improved density peaks algorithm to determine the number of clusters and the initial clustering centers, after which the K-means algorithm is used for clustering.The organization of this paper is as follows. The proposed methodology is discussed in Methods. In Experiments and Discussion, experimental results are explained. Finally, Conclusions concludes the paper and highlights future work related to the study.


## 2. Methods

### 2.1. Stacked-Random Projection

The basic idea of random projection is to choose a random hyperplane to map original variables into a low-dimensional space. In 1948, Johnson and Lindenstrauss proposed a theorem, nowadays termed the Johnson-Lindenstrauss lemma (JL) [13]. JL lemma is the theoretical basis of random projection, which guarantees that the subspace errors generated by random projection are controllable. The JL lemma states that for any 0<ε<1, and any integer n, let k be a positive integer such that
(1)k≥ε22−ε33−1lnn.Then, for anyn-point set V in Rd, there is a map f: Rd⟶Rk, such that for all u, vϵV,
(2)1‐εu−v2≤fu−fv2≤1+εu−v2.It indicates that by using random projection, the original high-dimensional data is reduced to low-dimensional data, and the distance between the original data is maintained approximately with a high probability. Zhang et al. [14] proposed a random projection ensemble approach and applied it to the prediction of drug-target interaction. Gondara [15] also proposed an ensemble random projection, in which the random projection matrix is applied to different subsets of the original dataset, and which can achieve greater classification accuracy compared with the random forest and AdaBoost methods.According to the Johnson-Lindenstrauss lemma, the minimum size of the target dimension after dimensionality reduction that guarantee theε embedding is given by Equation (3):
(3)dimension≥4lognsamplesε2/2−ε3/3.For example, wherensamples is the number of samples, it would require at least 6,515 dimensions to project 2k samples without too much distortion (ε=0.1). Thousands of dimensions are still high-dimensional data for the following step such as classification or clustering. Inspired by stacked Auto-Encoder, we propose a deep random projection framework, named Stacked-Random Projection (SRP), which incorporates random projection as its core stacking element. The SRP framework with k layers uses the input data as the first layer, and the output of the lth (l<k) layer is taken as the (l+1) layer input. In this way, a group of random projections method can be combined layer by layer in a stack.The main idea of the SRP dimensionality reduction method based on the high-dimensional text feature vector can be illustrated by means of taking the 20-newsgroups dataset as an example (further details are provided in Experiments and Discussion). First, the dataset is subjected to tokenization, stop-words removal, and TF-IDF in order to obtain the high-dimensional sparse text vector space (the feature dimension of the 20-newsgroups dataset was found to be 130,107). Then, a 4-layer SRP is constructed, this process is shown in Figure1. Thus, the dimensionality reduction process from high dimensionality to low dimensionality is completed. The illustration of our proposed SRP is provided in Figure 2.Figure 1
The SRP dimensionality reduction process for the 20-newsgroups dataset. The 4-layer SRP realizes the dimensionality reduction, using the random projection method from 130,107 down to 10k, down to 5k, down to 1k, and down to 100.Figure 2
Architecture of Stacked-Random Projection.


### 2.2. Improved DPC

The DPC algorithm is a granular computing model based on two assumptions: (1) the clustering center is surrounded by neighbour data points with lower local density; (2) the distance between any clustering center and data points with higher density is relatively far. In recent years, DPC has been applied in many fields, particularly natural language processing, due to its process and its effectiveness. The DPC algorithm can cluster data of different dimensions and shapes. At present, many researchers have researched DPC and have also proposed many improved algorithms. The main optimization aspects are speed improvement [16], accuracy improvement [17–19], and other aspects [20, 21]. Heimerl et al. [22] applied the DPC algorithm in the high-dimensional space to estimate the optimal cluster numbers for a given set of documents and assigned stability to one of the peaks based on the density structure of the data; however, the resulting computing speed of the DPC algorithm in the high-dimensional space was slow. Wang et al. [23] used DPC to measure the hierarchical relevance and diversity of sentences and selected highly representative sentences to generate news summaries. However, they reported that if there are multiple peaks in the sentence, then the key sentence will be redundant.For any pointi, two properties of the local density and relative distance are required. The calculation of these two attributes depends on the distance between any two points vi and vj in the graph. The two attributes are defined as follows:Definition 1.
local densityρi (Gaussian kernel):
(4)ρi=∑je−dijdc2,where dij is the Euclidean distance between vi and vj, and dc is the cut-off distance; these are important parameters for calculating ρi. One recommended practice is to select dc so that the average nearest neighbour from each point is 1%~2% of the total dataset size. As can be seen in Equation (4), the more points i contained in dc, the greater the local density ρ.Of the text clustering methods, the K-means method based on cosine similarity is still the most widely used text clustering algorithm due to its simplicity and fast convergence [24]. For text vectors, using cosine similarity has a better effect than Euclidean distance. Euclidean distance is a direct measure of the linear interval or length between vectors and is an absolute value of the difference in dimensional values. Cosine similarity describes the similarity between vectors using the cosine value of the angle, that is, the direction, and pays more attention to the difference between the relative levels of the dimensions. In text similarity analysis, one feature of similarity is the occurrence of the same words at the same time, which translates into nonzero values for the same dimension at the same time. We therefore redefine Definition 1 in terms of cosine similarity.Definition 2.
Local densityρi based on cosine similarity (Gaussian kernel):
For any two vectors in spacevi=x1,x2,⋯,xn and vj=y1,y2,⋯,yn, the cosine similarity is defined as the cosine of the angle between the two vectors:
(5)cosi,j=∑k=1nxkyk∑k=1nxk2∑k=1nyk2=∑k=1nxkykx•y,(6)ρi=∑je−cosi,jcosc2,where cosi,j is the cosine similarity between vi and vj, and cosc is the cut-off distance which needs to manually set the value to the nearest neighbour number of the sample approximately 1%~2% of the size of the entire dataset. As can be seen in Equation (6), the more points i contained in cosc, the greater the local density ρ.Definition 3.
Relative distanceδi:
(7)δi=maxjcosi,jρiisthemaximumminj:ρi<ρjcosi,jotherwise.Equation (7) indicates that cosine similarity distance δi can be obtained by calculating the minimum distance from the data point xi to any point with a density greater than that. After calculating the two parameters, a decision graph with ρ as the horizontal axis and δ as the vertical axis can be constructed. By observing the decision graph, the decision graph divides the data points into three different types, namely the density peak point, the normal point, and the outlier point. As shown in Figure 3, the data points are arranged in the order of decreasing density. There are five points that stand out, which are spread out towards the upper right corner of the decision graph, with varying high ρ values and higher δ values. These five points indicate that there are no data points with higher density than these five points in a larger area. Therefore, these five points are the so-called peak density points, and so they make a suitable clustering center. In order to better verify the accuracy of the clustering center point in the decision graph, the DPC define another variable γ=ρ∗δ, where a clustering center point has a large ρ value and δ value, the clustering center has a higher γ value. We conclude from our analysis of the decision graph and that ρ and δ are of two different orders of magnitude. To avoid the influence of different orders of magnitude, it is necessary to normalize them.
(8)ρi′=ρi−ρminρmax−ρmin,(9)δi′=δi−δminδmax−δmin,(10)γi=ρi′δi′.Figure 3
The decision graph of BBC dataset.Theγ values for Equation (10) are plotted in Figures 4 and 5. Figure 4 verifies the correctness of the clustering centers in the decision graph shown in Figure 3. Figure 5 is plotted according to the descending order of γ value, and it can be noted that γ value changes from large to small. The point at the clustering center has an enormous γ value, while the noncenter point has a smaller γ value, and the change tends to be flat. It can be concluded that according to the γ value, there are five clustering centers.Figure 4
The value ofγ according to the ρ∗δ in Figure 3.Figure 5
The value ofγ of Figure 4 in decreasing order.


### 2.3. DPC-K-means

The K-means clustering algorithm cannot extract data features effectively when processing high-dimensional data directly, and problems also occur when it randomly selects initial clustering centers and specifies the number of clustering in advance. These problems have been researched in numerous papers over the recent decades, as discussed elsewhere [25–27]. Therefore, we propose an improved method using the DPC algorithm.We first use SRP or random projection to reduce the dimensionality of high-dimensional text data and then combine it with the improved DPC algorithm. The choice of dimensionality reduction method SRP or random projection depends on whether the feature vector dimension is greater than the target dimension calculated according to Formula (3). If the feature vector dimension is greater than the minimum size of the target dimension, the SRP dimension reduction framework is performed. If the feature vector dimension is less than or equal to the target dimension, random projection is used directly. Using the cosine similarity calculation of ρ and δ, we select some points with high local density, which are far apart from each other as the clustering center; by doing so, the initial clustering center and the number of clusters can be obtained automatically; this makes the clustering algorithm, which we name the DPC-K-means. The improved algorithm is described below:Algorithm 1:
The DPC-K-means.Input: text feature vectorAϵRn×d, t is the minimum size of the target dimension.Output: the clustering results.Begin:Step1: determine whetherd is greater than t calculated according to Formula (3). If d is greater than t, use the SRP dimension reduction framework in Step2. If d is less than or equal to t, random projection is used in Step2.Step2: the SRP dimension reduction framework is used to reduce the dimensionality ofA layer by layer, until matrix A’ after dimension reduction is obtained. Or directly use random projection to reduce the dimension to get the matrix A’.Step3: Calculate theρ value and δ value of A’ according to Equations (6) and (7) and plot the decision graph with ρ and δ axes.Step4: calculate theγ value according to Equation (10) to verify the clustering centers and the number of clusters.Step5: perform K-means clustering: the clustering centers obtained in Step4 are used as the initial cluster centers, and the number of clusters is used as thek value for K-means clustering.Supposen input data, the original dimension d,t’ is the dimension of implementing SRP or random projection to reduce dimension to low-dimensional space, and the time complexity analysis of DPC-K-means algorithm is as follows:
(1)
The time complexity of a single random projection in Step2 isOndt’. The time complexity of Stacked-Random Projection is Ondh+nhl+⋯+nrt’ (l is the target dimension of the second layer, and r is the target dimension for the penultimate layer)(2)
The time complexity of Step3 is to calculateρ and δ, which is On2(3)
The time complexity of Step4 is to calculateγ and sort γ in descending order, which is Onlog2n(4)
The time complexity of Step5 K-means for specifying the cluster center and the number of clusters isOknt’.The total time complexity of DPC-K-means algorithm isOn2.Figure6 shows the overall structure of the proposed method. Table 1 shows the time complexity of several clustering algorithms.Figure 6
The detailed process of DPC-K-means.Table 1
The time complexity of several clustering algorithms.
DPC-K-meansDPCK-meansDBSCANSpectral ClusteringAffinity PropagationTime complexityOn2On2Onkt’On2On3On2logn


## 2.1. Stacked-Random Projection

The basic idea of random projection is to choose a random hyperplane to map original variables into a low-dimensional space. In 1948, Johnson and Lindenstrauss proposed a theorem, nowadays termed the Johnson-Lindenstrauss lemma (JL) [13]. JL lemma is the theoretical basis of random projection, which guarantees that the subspace errors generated by random projection are controllable. The JL lemma states that for any 0<ε<1, and any integer n, let k be a positive integer such that
(1)k≥ε22−ε33−1lnn.Then, for anyn-point set V in Rd, there is a map f: Rd⟶Rk, such that for all u, vϵV,
(2)1‐εu−v2≤fu−fv2≤1+εu−v2.It indicates that by using random projection, the original high-dimensional data is reduced to low-dimensional data, and the distance between the original data is maintained approximately with a high probability. Zhang et al. [14] proposed a random projection ensemble approach and applied it to the prediction of drug-target interaction. Gondara [15] also proposed an ensemble random projection, in which the random projection matrix is applied to different subsets of the original dataset, and which can achieve greater classification accuracy compared with the random forest and AdaBoost methods.According to the Johnson-Lindenstrauss lemma, the minimum size of the target dimension after dimensionality reduction that guarantee theε embedding is given by Equation (3):
(3)dimension≥4lognsamplesε2/2−ε3/3.For example, wherensamples is the number of samples, it would require at least 6,515 dimensions to project 2k samples without too much distortion (ε=0.1). Thousands of dimensions are still high-dimensional data for the following step such as classification or clustering. Inspired by stacked Auto-Encoder, we propose a deep random projection framework, named Stacked-Random Projection (SRP), which incorporates random projection as its core stacking element. The SRP framework with k layers uses the input data as the first layer, and the output of the lth (l<k) layer is taken as the (l+1) layer input. In this way, a group of random projections method can be combined layer by layer in a stack.The main idea of the SRP dimensionality reduction method based on the high-dimensional text feature vector can be illustrated by means of taking the 20-newsgroups dataset as an example (further details are provided in Experiments and Discussion). First, the dataset is subjected to tokenization, stop-words removal, and TF-IDF in order to obtain the high-dimensional sparse text vector space (the feature dimension of the 20-newsgroups dataset was found to be 130,107). Then, a 4-layer SRP is constructed, this process is shown in Figure1. Thus, the dimensionality reduction process from high dimensionality to low dimensionality is completed. The illustration of our proposed SRP is provided in Figure 2.Figure 1
The SRP dimensionality reduction process for the 20-newsgroups dataset. The 4-layer SRP realizes the dimensionality reduction, using the random projection method from 130,107 down to 10k, down to 5k, down to 1k, and down to 100.Figure 2
Architecture of Stacked-Random Projection.


## 2.2. Improved DPC

The DPC algorithm is a granular computing model based on two assumptions: (1) the clustering center is surrounded by neighbour data points with lower local density; (2) the distance between any clustering center and data points with higher density is relatively far. In recent years, DPC has been applied in many fields, particularly natural language processing, due to its process and its effectiveness. The DPC algorithm can cluster data of different dimensions and shapes. At present, many researchers have researched DPC and have also proposed many improved algorithms. The main optimization aspects are speed improvement [16], accuracy improvement [17–19], and other aspects [20, 21]. Heimerl et al. [22] applied the DPC algorithm in the high-dimensional space to estimate the optimal cluster numbers for a given set of documents and assigned stability to one of the peaks based on the density structure of the data; however, the resulting computing speed of the DPC algorithm in the high-dimensional space was slow. Wang et al. [23] used DPC to measure the hierarchical relevance and diversity of sentences and selected highly representative sentences to generate news summaries. However, they reported that if there are multiple peaks in the sentence, then the key sentence will be redundant.For any pointi, two properties of the local density and relative distance are required. The calculation of these two attributes depends on the distance between any two points vi and vj in the graph. The two attributes are defined as follows:Definition 1.
local densityρi (Gaussian kernel):
(4)ρi=∑je−dijdc2,where dij is the Euclidean distance between vi and vj, and dc is the cut-off distance; these are important parameters for calculating ρi. One recommended practice is to select dc so that the average nearest neighbour from each point is 1%~2% of the total dataset size. As can be seen in Equation (4), the more points i contained in dc, the greater the local density ρ.Of the text clustering methods, the K-means method based on cosine similarity is still the most widely used text clustering algorithm due to its simplicity and fast convergence [24]. For text vectors, using cosine similarity has a better effect than Euclidean distance. Euclidean distance is a direct measure of the linear interval or length between vectors and is an absolute value of the difference in dimensional values. Cosine similarity describes the similarity between vectors using the cosine value of the angle, that is, the direction, and pays more attention to the difference between the relative levels of the dimensions. In text similarity analysis, one feature of similarity is the occurrence of the same words at the same time, which translates into nonzero values for the same dimension at the same time. We therefore redefine Definition 1 in terms of cosine similarity.Definition 2.
Local densityρi based on cosine similarity (Gaussian kernel):
For any two vectors in spacevi=x1,x2,⋯,xn and vj=y1,y2,⋯,yn, the cosine similarity is defined as the cosine of the angle between the two vectors:
(5)cosi,j=∑k=1nxkyk∑k=1nxk2∑k=1nyk2=∑k=1nxkykx•y,(6)ρi=∑je−cosi,jcosc2,where cosi,j is the cosine similarity between vi and vj, and cosc is the cut-off distance which needs to manually set the value to the nearest neighbour number of the sample approximately 1%~2% of the size of the entire dataset. As can be seen in Equation (6), the more points i contained in cosc, the greater the local density ρ.Definition 3.
Relative distanceδi:
(7)δi=maxjcosi,jρiisthemaximumminj:ρi<ρjcosi,jotherwise.Equation (7) indicates that cosine similarity distance δi can be obtained by calculating the minimum distance from the data point xi to any point with a density greater than that. After calculating the two parameters, a decision graph with ρ as the horizontal axis and δ as the vertical axis can be constructed. By observing the decision graph, the decision graph divides the data points into three different types, namely the density peak point, the normal point, and the outlier point. As shown in Figure 3, the data points are arranged in the order of decreasing density. There are five points that stand out, which are spread out towards the upper right corner of the decision graph, with varying high ρ values and higher δ values. These five points indicate that there are no data points with higher density than these five points in a larger area. Therefore, these five points are the so-called peak density points, and so they make a suitable clustering center. In order to better verify the accuracy of the clustering center point in the decision graph, the DPC define another variable γ=ρ∗δ, where a clustering center point has a large ρ value and δ value, the clustering center has a higher γ value. We conclude from our analysis of the decision graph and that ρ and δ are of two different orders of magnitude. To avoid the influence of different orders of magnitude, it is necessary to normalize them.
(8)ρi′=ρi−ρminρmax−ρmin,(9)δi′=δi−δminδmax−δmin,(10)γi=ρi′δi′.Figure 3
The decision graph of BBC dataset.Theγ values for Equation (10) are plotted in Figures 4 and 5. Figure 4 verifies the correctness of the clustering centers in the decision graph shown in Figure 3. Figure 5 is plotted according to the descending order of γ value, and it can be noted that γ value changes from large to small. The point at the clustering center has an enormous γ value, while the noncenter point has a smaller γ value, and the change tends to be flat. It can be concluded that according to the γ value, there are five clustering centers.Figure 4
The value ofγ according to the ρ∗δ in Figure 3.Figure 5
The value ofγ of Figure 4 in decreasing order.


## 2.3. DPC-K-means

The K-means clustering algorithm cannot extract data features effectively when processing high-dimensional data directly, and problems also occur when it randomly selects initial clustering centers and specifies the number of clustering in advance. These problems have been researched in numerous papers over the recent decades, as discussed elsewhere [25–27]. Therefore, we propose an improved method using the DPC algorithm.We first use SRP or random projection to reduce the dimensionality of high-dimensional text data and then combine it with the improved DPC algorithm. The choice of dimensionality reduction method SRP or random projection depends on whether the feature vector dimension is greater than the target dimension calculated according to Formula (3). If the feature vector dimension is greater than the minimum size of the target dimension, the SRP dimension reduction framework is performed. If the feature vector dimension is less than or equal to the target dimension, random projection is used directly. Using the cosine similarity calculation of ρ and δ, we select some points with high local density, which are far apart from each other as the clustering center; by doing so, the initial clustering center and the number of clusters can be obtained automatically; this makes the clustering algorithm, which we name the DPC-K-means. The improved algorithm is described below:Algorithm 1:
The DPC-K-means.Input: text feature vectorAϵRn×d, t is the minimum size of the target dimension.Output: the clustering results.Begin:Step1: determine whetherd is greater than t calculated according to Formula (3). If d is greater than t, use the SRP dimension reduction framework in Step2. If d is less than or equal to t, random projection is used in Step2.Step2: the SRP dimension reduction framework is used to reduce the dimensionality ofA layer by layer, until matrix A’ after dimension reduction is obtained. Or directly use random projection to reduce the dimension to get the matrix A’.Step3: Calculate theρ value and δ value of A’ according to Equations (6) and (7) and plot the decision graph with ρ and δ axes.Step4: calculate theγ value according to Equation (10) to verify the clustering centers and the number of clusters.Step5: perform K-means clustering: the clustering centers obtained in Step4 are used as the initial cluster centers, and the number of clusters is used as thek value for K-means clustering.Supposen input data, the original dimension d,t’ is the dimension of implementing SRP or random projection to reduce dimension to low-dimensional space, and the time complexity analysis of DPC-K-means algorithm is as follows:
(1)
The time complexity of a single random projection in Step2 isOndt’. The time complexity of Stacked-Random Projection is Ondh+nhl+⋯+nrt’ (l is the target dimension of the second layer, and r is the target dimension for the penultimate layer)(2)
The time complexity of Step3 is to calculateρ and δ, which is On2(3)
The time complexity of Step4 is to calculateγ and sort γ in descending order, which is Onlog2n(4)
The time complexity of Step5 K-means for specifying the cluster center and the number of clusters isOknt’.The total time complexity of DPC-K-means algorithm isOn2.Figure6 shows the overall structure of the proposed method. Table 1 shows the time complexity of several clustering algorithms.Figure 6
The detailed process of DPC-K-means.Table 1
The time complexity of several clustering algorithms.
DPC-K-meansDPCK-meansDBSCANSpectral ClusteringAffinity PropagationTime complexityOn2On2Onkt’On2On3On2logn


## 3. Experiments and Discussion

### 3.1. Summarization Datasets

Experimental work was conducted on seven standard text datasets. The summary of datasets is presented in Table2. Datasets are described as follows. The features are obtained by tokenization, stop-words removal, and TF-IDF.Table 2
The summary of datasets.
DatasetInstancesDimension of featuresClustersLabelBBC2,22511,2275Yes20-newsgroups100013,01074~8YesSports article1,0003482YesAsian Religious590398YesCNAE-91,0808579NoStack Overflow1671674YesAmazon1001002YesThe BBC news dataset (http://mlg.ucd.ie/datasets/bbc.html.) has a total of 2,225 text files on five topical areas published on the BBC news website. Text documents were arranged into folders containing five labels: business, entertainment, politics, sports, and technology.The 20-newsgroups dataset (http://scikit-learn.org/stable/modules/classes.html#module-sklearn.datasets) of approximately 20k newsgroup documents was partitioned evenly across the 20 different newsgroups. We selected 1k documents and 4~8 various newsgroups (4 groups~8 groups) for our experimental dataset.The Sports Article dataset (http://archive.ics.uci.edu/ml/datasets.php) was labelled using Amazon Mechanical Turk as objective or subjective.The Asian Religious (http://archive.ics.uci.edu/ml/datasets.php) dataset was the words from the bag of words preprocessing of the mini-corpus made up of eight religious books.The CNAE-9 dataset (http://archive.ics.uci.edu/ml/datasets.php) contains 1,080 documents of free text business descriptions of Brazilian companies which were categorized into a subset of nine categories.The Stack Overflow dataset (http://www.kaggle.com/c/predict-closed-questions-on-stack-overflow/download/train.zip) is challenge data published on http://Kaggle.com/. The dataset consists of 3,370,538 samples dated from July 31, 2012, to August 14, 2012. In our experiments, we randomly selected 167 question titles from 4 different tags.The Amazon dataset (http://archive.ics.uci.edu/ml/datasets.php) is the product reviews extracted from websites and marked with positive and negative.


### 3.2. Simulation Environments

The simulation environments for all algorithms performed in our experiments were as follows: the Python 3.7 software environment running with Intel i7-7500U CPU, 2.70GHz with 8GB RAM.


### 3.3. Experiment 1

According to Formula (3), the minimum size of the target dimension (ε=0.1) of the BBC and 20-newsgroups datasets is 6,609 and 5,920. According to the flowchart Figure 6, the feature vector dimensions of the two datasets are larger than the minimum size of the target dimension, so that SRP was used to reduce the dimensionality of these two datasets. We compared the dimensionality reduction performance of Principal Component Analysis (PCA), Multiple Dimensional Scaling (MDS), Random Projection (RP), and Stacked-Random Projection (SRP). To correctly compare the performance of these dimensionality reduction methods, we experimentally reduced the feature vector of the BBC news dataset and 20-newsgroups dataset to 2k, 500, and 100. Table 3 shows the run time (time), mean ratio of distances (projected/original, ratio), and the standard deviation of ratio of distances (projected/original, standard deviation). The mean ratio of distances is the degree to which the distance between the original data is maintained in the low-dimensional space when the original high-dimensional data is reduced to low-dimensional data. The value is approximately close to 1, indicating better preservation. The smaller the standard deviation of the ratio of distances, the closer is it to the mean ratio of distances. As shown in Table 3, RP and SRP considerably shorten the run time of dimension reduction compared with PCA and MDS. We can see that there is little difference in the distribution of the distortion between SRP and RP for high values of the dimension. But for low values of the dimension, the distortion distribution is controlled, and the distances are well preserved by the SRP. Text data is usually high-dimensional and small-sampling data. The characteristic of high-dimensional and small-sampling data is that the number of dimensions is much larger than the number of samples. SRP is suitable for dimensionality reduction of this type of data, which significantly reduces the running time of dimensionality reduction, and the distances are well preserved.Table 3
The run time, ratio, and standard deviation of each dimension reduction method reduce the dimension to 2,000, 500, and 100.
Dimension=2,000Dimension=500Dimension=100Time (s)RatioStandard deviationTime (s)RatioStandard deviationTime (s)RatioStandard deviationBBCPCA30.521.000.0215.160.570.094.990.230.09MDS57.991.000.0228.671.000.0715.471.000.07RP1.121.000.040.561.000.080.411.010.18SRP2.871.000.052.381.000.072.271.000.1220-newsgroupsPCA24.871.000.0013.351.000.084.201.000.1MDS65.271.000.0244.741.000.0323.130.990.06RP0.100.990.060.461.000.120.310.990.28SRP3.331.000.052.851.000.072.721.000.15


### 3.4. Experiment 2

Since DPC is a clustering algorithm, we use the Euclidean distance and cosine similarity to calculate DPC local densityρi and observe the difference between these two methods by clustering performance metrics. According to Formula (3), the minimum size of the target dimension (ε=0.1) of the BBC and 20-newsgroups datasets is 6,609 and 5,920. According to the flowchart Figure 6, SRP was used to reduce the dimensionality of these two datasets to 100 dimensions. The minimum size of the target dimension of Sports Article, CNAE-9, and Stack Overflow datasets is larger than the feature vector dimension, so that the dimension can be reduced by random projection to 100 dimensions. The feature dimensions of the Asian Religions and Amazon datasets are ≤100, so there is no need for dimension reduction in this experiment. To correctly compare these two methods’ performance, we used the four cluster evaluation metrics—ARI (Adjusted Rand Index), NMI (Normalized Mutual Information), FMI (Fowlkes-Mallows Index), and Clusters (the number of clusters)—to evaluate the performance of the clustering algorithm. ARI, NMI, and FMI are all used to measure the consistency between clustering results and real category data, among which ARI, NMI, and FMI have value ranges of [-1,1], [0,1], and [0,1], respectively. The higher the three evaluation metrics’ values, the better the clustering quality, and the more consistent the clustering results are with the real category data. Clusters are the number of clusters after DPC. By comparing with Table 2, we can compare which method of the Euclidean distance and cosine similarity can cluster accurately. Table 4 shows the clustering performances of local density calculated by the Euclidean distance (Euclidean) and cosine similarity (Cosine).Table 4
The clustering performances of local density calculated by Euclidean distance and cosine similarity.
DatasetARINMIFMIClustersEuclideanCosineEuclideanCosineEuclideanCosineEuclideanCosineBBC0.84220.90020.82230.86810.87590.9204554 groups0.97150.97810.95230.96230.97860.9836445 groups0.84380.84330.84110.83810.88510.8846556 groups0.61950.67590.68740.73510.73260.7700667 groups0.22130.58580.30390.64870.49990.7031578 groups0.18890.46640.26720.55070.46070.613858Sports Article00000.56740.729812Asian Religious0.05620.01890.12880.01630.31450.466568Stack Overflow00000.36600.439924Amazon00.001400.00480.55150.669622CNAE-9——————69To further judge the clustering performance proposed in this paper, a pairedt-test was used to test the clustering significance. A paired t-test is used to determine whether there is a significant difference between the two samples. The Euclidean distance and cosine similarity were used to calculate the local density of DPC and test the cluster evaluation metrics. The p value gives the probability of observing the test results under the null hypothesis. The confidence level is at 95%, and the cut-off value of p is 0.05; if p<0.05, the proposed algorithm clustering results and the comparison algorithm are significantly different. If p≥0.05, there is no significant difference between the proposed algorithm and the comparison algorithm’s clustering results. Table 5 shows the paired t-test results of each evaluation metric of Euclidean distance (Euclidean) and cosine similarity (Cosine) in Table 4.Table 5
Table4’s paired t-test results of ARI, NMI, and FMI.
Pairing methodPairedt-test indexARINMIFMIEuclidean and Cosinet-1.70-1.40-4.16p0.12400.19580.0025As shown in Table5, there are substantial differences in FMI between the Euclidean distance and cosine similarity and no significant difference in ARI, NMI. As can be seen from the number of clusters of Tables 2 and 4, the improved DPC of the local density calculated with cosine similarity can accurately determine the number of clusters. Figure 7 shows the decision graph, the γ values of the BBC dataset following dimensionality reduction by SRP. Figure 8 shows the decision graph, the γ values of the four newsgroups in the 20-newsgroups dataset following dimensionality reduction by SRP. Figure 9 shows the decision graph, the γ values of the Amazon dataset. Figure 10 shows the decision graph, the γ values of the Sports Article dataset. As shown in these figures, improved DPC can accurately determine the dataset of the number of clusters, indicating that using cosine similarity to calculate the local density of DPC is better than using the Euclidean distance. Therefore, cosine similarity is more suitable for text vector calculation.Figure 7
The improved DPC clustering of the BBC dataset. (a) Decision graph. (b)γ value.
(a)(b)Figure 8
The improved DPC clustering of the four newsgroups in the 20-newsgroups dataset. (a) Decision graph. (b)γ value.
(a)(b)Figure 9
The improved DPC clustering of the Amazon dataset. (a) Decision graph. (b)γ value.
(a)(b)Figure 10
The improved DPC clustering of the Sports Article dataset. (a) Decision graph. (b)γ value.
(a)(b)


### 3.5. Experiment 3

We compared the clustering performance of DPC, DBSCAN, Spectral Clustering, Affinity Propagation, and DPC-K-means. In a comparative study of these clustering algorithms, we used the four evaluation metrics—ARI (Adjusted Rand Index), NMI (Normalized Mutual Information), FMI (Fowlkes-Mallows Index), and MSE (Mean Squared Error)—to evaluate the performance of the clustering algorithm. The mean-square error (MSE) is the average of the sum of squares of the difference between the predicted value and the real value used to measure the expected result. It is nonnegative, and values closer to zero are better. For even comparisons with these methods, we repeated the experiment ten times to obtain the average clustering performance as the final performance of each method. Table6 shows the ARI of each method. Table 7 shows the NMI of each method. Table 8 shows the FMI of each method. Table 9 shows the MSE of each method.Table 6
The ARI of each clustering algorithm.
DatasetDPC-K-meansDPCDBSCANSpectral ClusteringAffinity PropagationBBC0.90280.90020.46510.89610.147720-newsgroups4 groups0.97830.97810.72660.97560.14925 groups0.85210.84330.59930.84150.15086 groups0.67210.67590.41660.51300.13347 groups0.60780.58580.42600.49140.14808 groups0.48580.46640.13890.45990.1589Sports Article0.194100.03540.19060.0175Asian Religious0.15660.018900.18290.1064Stack Overflow000.038600.0349Amazon00.0014000.0114Table 7
The NMI of each clustering algorithm.
DatasetDPC-K-meansDPCDBSCANSpectral ClusteringAffinity PropagationBBC0.90280.86810.56520.86500.369620-newsgroups4 groups0.97630.96230.67250.95770.36285 groups0.84210.83810.67090.84040.36536 groups0.77210.73510.57210.69870.33047 groups0.70780.64870.55110.64980.36028 groups0.68580.55070.28460.62490.3719Sports Article0.187000.12860.18490.0307Asian Religious0.26730.016300.24430.2094Stack Overflow000.05180.02040.0819Amazon00.0048000.0116Table 8
The FMI of each clustering algorithm.
DatasetDPC-K-meansDPCDBSCANSpectral ClusteringAffinity PropagationBBC0.92250.92040.58050.91720.340220-newsgroups4 groups0.98230.98360.79300.98170.32255 groups0.88640.88460.68100.88310.29926 groups0.84860.77000.54850.63320.25937 groups0.78230.70310.54150.58130.25608 groups0.65350.61380.38960.54680.2592Sports Article0.73000.72980.57650.61140.1653Asian Religious0.48020.46650.46150.38330.2341Stack Overflow0.55120.43990.40040.38160.1649Amazon0.71920.66960.70410.68920.2624Table 9
The MSE of each clustering algorithm.
DatasetDPC-K-meansDPCDBSCANSpectral ClusteringAffinity PropagationBBC1.06613.27913.20856.237815.432820-newsgroups4 groups0.55903.20876.20402.710314.67435 groups1.72032.26105.86103.004713.40506 groups6.63908.45306.90405.028013.72907 groups7.84538.05039.61037.242015.98808 groups5.472313.036716.67577.514320.1617Sports Article1.30202.09502.09801.81508.4410Asian Religious5.18986.464416.483111.967856.6118Stack Overflow3.80846.736518.077811.191660.4068Amazon0.47000.52000.51000.53005.2500To further judge the difference between the clustering results of the algorithm proposed in this paper DPC-K-means and those of other cluster methods, a pairedt-test was used to test the clustering results significance. Table 10 shows the paired t-test results of each evaluation metric of these methods in Tables 6–9. The p value gives the probability of observing the test results under the null hypothesis. The confidence level is at 95%, and the cut-off value of p is 0.05; if p<0.05, the proposed algorithm’s clustering results and the comparison algorithm are significantly different. If p≥0.05, there is no significant difference between the proposed algorithm and the comparison algorithm clustering performance.Table 10
Pairedt-test results of clustering algorithms.
Pairing methodPairedt-test indexARINMIFMIMSEDPC-K-means and DPCt1.732.552.80-2.88p0.11710.03110.02070.0181DPC-K-means and DBSCANt4.393.935.47-3.50p0.00170.00350.00040.0067DPC-K-means and Spectral Clusteringt1.602.602.62-2.35p0.14480.02890.00560.0430DPC-K-means and Affinity Propagationt3.683.7212.52-3.19p0.00500.00470.00000.0109As shown in Table10, there are significant changes in NMI, FMI, and MSE metrics between DPC-K-means and comparison methods. DPC-K-means is superior to comparison algorithms in NMI, FMI, and MSE. DPC-K-means compared to DPC and Spectral Clustering has no significant difference in ARI, indicating that DPC and Spectral Clustering are performed as well as DPC-K-means on the ARI metric. A one-sample t-test method is used to evaluate the DPC-K-means algorithm significance on different datasets. Taking the FMI evaluation metric in the BBC dataset as an example of significance testing, the process is as follows: Firstly, a test hypothesis is established and the threshold chosen for statistical significance was determined (H0:μ=μ0, α=0.1). Secondly, the t is calculated:
(11)t=x¯−μ0sn=0.9225−μ0s5=0.9225−0.73620.26575=1.568,v=5−1=4,where x¯ represents the FMI value obtained by DPC-K-means on the BBC dataset, μ0 is the mean FMI of the five comparison algorithms on the BBC dataset, s represents the standard deviation FMI of the five comparison algorithms on the BBC dataset, and n is the sample size. The degree of freedom v used in this test is 4. Finally, the table was queried of t-distribution, the p value was determined, and an inference conclusion was made. According to α=0.1 and v=4, the p value is 1.533, t=1.568>p, and H0 is rejected, indicating the difference between the FMI metric of DPC-K-means on the BBC dataset, and the FMI value of other comparison algorithms is statistically significant. According to the above significance test steps, the t-test results of DPC-K-means were calculated on the ARI, NMI, and FMI evaluation metrics. The results are shown in Tables 11–13.Table 11
The results of thet-test of DPC-K-means on ARI.
DatasetMeanStandard deviationtpDifferenceBBC0.66240.34381.3981.533No20-newsgroups4 groups0.76170.35931.3481.533No5 groups0.65740.30261.4391.533No6 groups0.48220.22931.8971.533Yes7 groups0.45180.18491.8861.533Yes8 groups0.34200.17671.8201.533YesSports Article0.08750.09652.4691.533YesAsian Religious0.0930.08131.7501.533YesStack Overflow0.08420.16941.1111.533NoAmazon0.00260.00501.1501.533NoTable 12
The results of thet-test of DPC-K-means on NMI.
DatasetMeanStandard deviationtpDifferenceBBC0.71410.23611.7871.533Yes20-newsgroups4 groups0.78630.26871.5811.533Yes5 groups0.71140.20691.4131.533No6 groups0.62170.17941.8751.533Yes7 groups0.58350.13692.0291.533Yes8 groups0.50360.16992.3991.533YesSports Article0.10620.08692.0781.533YesAsian Religious0.14750.12902.0781.533YesStack Overflow0.03080.03561.9381.533YesAmazon0.00330.00511.4401.533NoTable 13
The results of thet-test of DPC-K-means on FMI.
DatasetMeanStandard deviationtpDifferenceBBC0.73620.26571.5681.533Yes20-newsgroups4 groups0.81260.28601.3271.533No5 groups0.72690.25481.4001.533No6 groups0.61190.22902.3111.533Yes7 groups0.57280.20142.3251.533Yes8 groups0.49260.16482.1841.533YesSports Article0.56260.23261.6091.533YesAsian Religious0.40510.10281.6321.533YesStack Overflow0.38760.14082.5981.533YesAmazon0.60890.19461.2681.533NoAs shown in Table11, there are significant differences in the ARI metric of DPC-K-means on five datasets, and as shown in Table 12 there are significant differences in the NMI metric of DPC-K-means on eight datasets. It can be seen from Table 13 that DPC-K-means have significant difference in the FMI metric on the seven datasets. DPC-K-means are statistically significant on most datasets. Combined with Tables 9 and 10, it further shows that DPC-K-means is better than other comparison algorithms.The clustering performance of DPC-K-means is better than K-means because DPC-K-means can select the number of clusters and obtain the initial clustering center. The number of clusters and the initial clustering centers can be used in the K-means algorithm, which achieves better clustering performance than K-means. Figures11 and 12 illustrate the clustering centers automatically determined by DPC-K-means which are closer to the real class centers.Figure 11
The BBC news dataset clustering center of K-means marked in black, and DPC-K-means clustering center marked in red and the 3D clustering results.Figure 12
The 4 groups in the 20-newsgroups dataset clustering center of K-means marked in black, and DPC-K-means clustering center marked in red and the 3D clustering results.Tables6–9 show that the clustering metrics changed significantly from 4 newsgroups to 8 newsgroups; this was caused by the loss of clustering due to irregular data distribution. Due to the inherent nature of the DPC algorithm, it cannot identify the phenomenon of “False peaks,” and its clustering effect on “No density peaks” datasets is low, which are all factors that affect the accuracy of the DPC-K-means algorithm. The algorithm is limited in its processing of more complex datasets.DPC-K-means has a parametercosc, which is the cut-off distance. The value suggested in the literature [12] is set to the nearest neighbour number of the sample, approximately 1%~2% of the total dataset size. In the experiment, we were able to obtain the correct number of class clusters according to this valued principle. This parameter has no significant influence on the result of the algorithm within the value range of 1%–2% of the entire dataset size. The K-nearest neighbour method was used to establish the similarity matrix in the Spectral Clustering parameters in the experiment. The damping factor in Affinity Propagation was set to 0.9, and the nearest distance measurement of the DBSCAN parameter value was set to “cosine” by cosine similarity.


## 3.1. Summarization Datasets

Experimental work was conducted on seven standard text datasets. The summary of datasets is presented in Table2. Datasets are described as follows. The features are obtained by tokenization, stop-words removal, and TF-IDF.Table 2
The summary of datasets.
DatasetInstancesDimension of featuresClustersLabelBBC2,22511,2275Yes20-newsgroups100013,01074~8YesSports article1,0003482YesAsian Religious590398YesCNAE-91,0808579NoStack Overflow1671674YesAmazon1001002YesThe BBC news dataset (http://mlg.ucd.ie/datasets/bbc.html.) has a total of 2,225 text files on five topical areas published on the BBC news website. Text documents were arranged into folders containing five labels: business, entertainment, politics, sports, and technology.The 20-newsgroups dataset (http://scikit-learn.org/stable/modules/classes.html#module-sklearn.datasets) of approximately 20k newsgroup documents was partitioned evenly across the 20 different newsgroups. We selected 1k documents and 4~8 various newsgroups (4 groups~8 groups) for our experimental dataset.The Sports Article dataset (http://archive.ics.uci.edu/ml/datasets.php) was labelled using Amazon Mechanical Turk as objective or subjective.The Asian Religious (http://archive.ics.uci.edu/ml/datasets.php) dataset was the words from the bag of words preprocessing of the mini-corpus made up of eight religious books.The CNAE-9 dataset (http://archive.ics.uci.edu/ml/datasets.php) contains 1,080 documents of free text business descriptions of Brazilian companies which were categorized into a subset of nine categories.The Stack Overflow dataset (http://www.kaggle.com/c/predict-closed-questions-on-stack-overflow/download/train.zip) is challenge data published on http://Kaggle.com/. The dataset consists of 3,370,538 samples dated from July 31, 2012, to August 14, 2012. In our experiments, we randomly selected 167 question titles from 4 different tags.The Amazon dataset (http://archive.ics.uci.edu/ml/datasets.php) is the product reviews extracted from websites and marked with positive and negative.


## 3.2. Simulation Environments

The simulation environments for all algorithms performed in our experiments were as follows: the Python 3.7 software environment running with Intel i7-7500U CPU, 2.70GHz with 8GB RAM.


## 3.3. Experiment 1

According to Formula (3), the minimum size of the target dimension (ε=0.1) of the BBC and 20-newsgroups datasets is 6,609 and 5,920. According to the flowchart Figure 6, the feature vector dimensions of the two datasets are larger than the minimum size of the target dimension, so that SRP was used to reduce the dimensionality of these two datasets. We compared the dimensionality reduction performance of Principal Component Analysis (PCA), Multiple Dimensional Scaling (MDS), Random Projection (RP), and Stacked-Random Projection (SRP). To correctly compare the performance of these dimensionality reduction methods, we experimentally reduced the feature vector of the BBC news dataset and 20-newsgroups dataset to 2k, 500, and 100. Table 3 shows the run time (time), mean ratio of distances (projected/original, ratio), and the standard deviation of ratio of distances (projected/original, standard deviation). The mean ratio of distances is the degree to which the distance between the original data is maintained in the low-dimensional space when the original high-dimensional data is reduced to low-dimensional data. The value is approximately close to 1, indicating better preservation. The smaller the standard deviation of the ratio of distances, the closer is it to the mean ratio of distances. As shown in Table 3, RP and SRP considerably shorten the run time of dimension reduction compared with PCA and MDS. We can see that there is little difference in the distribution of the distortion between SRP and RP for high values of the dimension. But for low values of the dimension, the distortion distribution is controlled, and the distances are well preserved by the SRP. Text data is usually high-dimensional and small-sampling data. The characteristic of high-dimensional and small-sampling data is that the number of dimensions is much larger than the number of samples. SRP is suitable for dimensionality reduction of this type of data, which significantly reduces the running time of dimensionality reduction, and the distances are well preserved.Table 3
The run time, ratio, and standard deviation of each dimension reduction method reduce the dimension to 2,000, 500, and 100.
Dimension=2,000Dimension=500Dimension=100Time (s)RatioStandard deviationTime (s)RatioStandard deviationTime (s)RatioStandard deviationBBCPCA30.521.000.0215.160.570.094.990.230.09MDS57.991.000.0228.671.000.0715.471.000.07RP1.121.000.040.561.000.080.411.010.18SRP2.871.000.052.381.000.072.271.000.1220-newsgroupsPCA24.871.000.0013.351.000.084.201.000.1MDS65.271.000.0244.741.000.0323.130.990.06RP0.100.990.060.461.000.120.310.990.28SRP3.331.000.052.851.000.072.721.000.15


## 3.4. Experiment 2

Since DPC is a clustering algorithm, we use the Euclidean distance and cosine similarity to calculate DPC local densityρi and observe the difference between these two methods by clustering performance metrics. According to Formula (3), the minimum size of the target dimension (ε=0.1) of the BBC and 20-newsgroups datasets is 6,609 and 5,920. According to the flowchart Figure 6, SRP was used to reduce the dimensionality of these two datasets to 100 dimensions. The minimum size of the target dimension of Sports Article, CNAE-9, and Stack Overflow datasets is larger than the feature vector dimension, so that the dimension can be reduced by random projection to 100 dimensions. The feature dimensions of the Asian Religions and Amazon datasets are ≤100, so there is no need for dimension reduction in this experiment. To correctly compare these two methods’ performance, we used the four cluster evaluation metrics—ARI (Adjusted Rand Index), NMI (Normalized Mutual Information), FMI (Fowlkes-Mallows Index), and Clusters (the number of clusters)—to evaluate the performance of the clustering algorithm. ARI, NMI, and FMI are all used to measure the consistency between clustering results and real category data, among which ARI, NMI, and FMI have value ranges of [-1,1], [0,1], and [0,1], respectively. The higher the three evaluation metrics’ values, the better the clustering quality, and the more consistent the clustering results are with the real category data. Clusters are the number of clusters after DPC. By comparing with Table 2, we can compare which method of the Euclidean distance and cosine similarity can cluster accurately. Table 4 shows the clustering performances of local density calculated by the Euclidean distance (Euclidean) and cosine similarity (Cosine).Table 4
The clustering performances of local density calculated by Euclidean distance and cosine similarity.
DatasetARINMIFMIClustersEuclideanCosineEuclideanCosineEuclideanCosineEuclideanCosineBBC0.84220.90020.82230.86810.87590.9204554 groups0.97150.97810.95230.96230.97860.9836445 groups0.84380.84330.84110.83810.88510.8846556 groups0.61950.67590.68740.73510.73260.7700667 groups0.22130.58580.30390.64870.49990.7031578 groups0.18890.46640.26720.55070.46070.613858Sports Article00000.56740.729812Asian Religious0.05620.01890.12880.01630.31450.466568Stack Overflow00000.36600.439924Amazon00.001400.00480.55150.669622CNAE-9——————69To further judge the clustering performance proposed in this paper, a pairedt-test was used to test the clustering significance. A paired t-test is used to determine whether there is a significant difference between the two samples. The Euclidean distance and cosine similarity were used to calculate the local density of DPC and test the cluster evaluation metrics. The p value gives the probability of observing the test results under the null hypothesis. The confidence level is at 95%, and the cut-off value of p is 0.05; if p<0.05, the proposed algorithm clustering results and the comparison algorithm are significantly different. If p≥0.05, there is no significant difference between the proposed algorithm and the comparison algorithm’s clustering results. Table 5 shows the paired t-test results of each evaluation metric of Euclidean distance (Euclidean) and cosine similarity (Cosine) in Table 4.Table 5
Table4’s paired t-test results of ARI, NMI, and FMI.
Pairing methodPairedt-test indexARINMIFMIEuclidean and Cosinet-1.70-1.40-4.16p0.12400.19580.0025As shown in Table5, there are substantial differences in FMI between the Euclidean distance and cosine similarity and no significant difference in ARI, NMI. As can be seen from the number of clusters of Tables 2 and 4, the improved DPC of the local density calculated with cosine similarity can accurately determine the number of clusters. Figure 7 shows the decision graph, the γ values of the BBC dataset following dimensionality reduction by SRP. Figure 8 shows the decision graph, the γ values of the four newsgroups in the 20-newsgroups dataset following dimensionality reduction by SRP. Figure 9 shows the decision graph, the γ values of the Amazon dataset. Figure 10 shows the decision graph, the γ values of the Sports Article dataset. As shown in these figures, improved DPC can accurately determine the dataset of the number of clusters, indicating that using cosine similarity to calculate the local density of DPC is better than using the Euclidean distance. Therefore, cosine similarity is more suitable for text vector calculation.Figure 7
The improved DPC clustering of the BBC dataset. (a) Decision graph. (b)γ value.
(a)(b)Figure 8
The improved DPC clustering of the four newsgroups in the 20-newsgroups dataset. (a) Decision graph. (b)γ value.
(a)(b)Figure 9
The improved DPC clustering of the Amazon dataset. (a) Decision graph. (b)γ value.
(a)(b)Figure 10
The improved DPC clustering of the Sports Article dataset. (a) Decision graph. (b)γ value.
(a)(b)


## 3.5. Experiment 3

We compared the clustering performance of DPC, DBSCAN, Spectral Clustering, Affinity Propagation, and DPC-K-means. In a comparative study of these clustering algorithms, we used the four evaluation metrics—ARI (Adjusted Rand Index), NMI (Normalized Mutual Information), FMI (Fowlkes-Mallows Index), and MSE (Mean Squared Error)—to evaluate the performance of the clustering algorithm. The mean-square error (MSE) is the average of the sum of squares of the difference between the predicted value and the real value used to measure the expected result. It is nonnegative, and values closer to zero are better. For even comparisons with these methods, we repeated the experiment ten times to obtain the average clustering performance as the final performance of each method. Table6 shows the ARI of each method. Table 7 shows the NMI of each method. Table 8 shows the FMI of each method. Table 9 shows the MSE of each method.Table 6
The ARI of each clustering algorithm.
DatasetDPC-K-meansDPCDBSCANSpectral ClusteringAffinity PropagationBBC0.90280.90020.46510.89610.147720-newsgroups4 groups0.97830.97810.72660.97560.14925 groups0.85210.84330.59930.84150.15086 groups0.67210.67590.41660.51300.13347 groups0.60780.58580.42600.49140.14808 groups0.48580.46640.13890.45990.1589Sports Article0.194100.03540.19060.0175Asian Religious0.15660.018900.18290.1064Stack Overflow000.038600.0349Amazon00.0014000.0114Table 7
The NMI of each clustering algorithm.
DatasetDPC-K-meansDPCDBSCANSpectral ClusteringAffinity PropagationBBC0.90280.86810.56520.86500.369620-newsgroups4 groups0.97630.96230.67250.95770.36285 groups0.84210.83810.67090.84040.36536 groups0.77210.73510.57210.69870.33047 groups0.70780.64870.55110.64980.36028 groups0.68580.55070.28460.62490.3719Sports Article0.187000.12860.18490.0307Asian Religious0.26730.016300.24430.2094Stack Overflow000.05180.02040.0819Amazon00.0048000.0116Table 8
The FMI of each clustering algorithm.
DatasetDPC-K-meansDPCDBSCANSpectral ClusteringAffinity PropagationBBC0.92250.92040.58050.91720.340220-newsgroups4 groups0.98230.98360.79300.98170.32255 groups0.88640.88460.68100.88310.29926 groups0.84860.77000.54850.63320.25937 groups0.78230.70310.54150.58130.25608 groups0.65350.61380.38960.54680.2592Sports Article0.73000.72980.57650.61140.1653Asian Religious0.48020.46650.46150.38330.2341Stack Overflow0.55120.43990.40040.38160.1649Amazon0.71920.66960.70410.68920.2624Table 9
The MSE of each clustering algorithm.
DatasetDPC-K-meansDPCDBSCANSpectral ClusteringAffinity PropagationBBC1.06613.27913.20856.237815.432820-newsgroups4 groups0.55903.20876.20402.710314.67435 groups1.72032.26105.86103.004713.40506 groups6.63908.45306.90405.028013.72907 groups7.84538.05039.61037.242015.98808 groups5.472313.036716.67577.514320.1617Sports Article1.30202.09502.09801.81508.4410Asian Religious5.18986.464416.483111.967856.6118Stack Overflow3.80846.736518.077811.191660.4068Amazon0.47000.52000.51000.53005.2500To further judge the difference between the clustering results of the algorithm proposed in this paper DPC-K-means and those of other cluster methods, a pairedt-test was used to test the clustering results significance. Table 10 shows the paired t-test results of each evaluation metric of these methods in Tables 6–9. The p value gives the probability of observing the test results under the null hypothesis. The confidence level is at 95%, and the cut-off value of p is 0.05; if p<0.05, the proposed algorithm’s clustering results and the comparison algorithm are significantly different. If p≥0.05, there is no significant difference between the proposed algorithm and the comparison algorithm clustering performance.Table 10
Pairedt-test results of clustering algorithms.
Pairing methodPairedt-test indexARINMIFMIMSEDPC-K-means and DPCt1.732.552.80-2.88p0.11710.03110.02070.0181DPC-K-means and DBSCANt4.393.935.47-3.50p0.00170.00350.00040.0067DPC-K-means and Spectral Clusteringt1.602.602.62-2.35p0.14480.02890.00560.0430DPC-K-means and Affinity Propagationt3.683.7212.52-3.19p0.00500.00470.00000.0109As shown in Table10, there are significant changes in NMI, FMI, and MSE metrics between DPC-K-means and comparison methods. DPC-K-means is superior to comparison algorithms in NMI, FMI, and MSE. DPC-K-means compared to DPC and Spectral Clustering has no significant difference in ARI, indicating that DPC and Spectral Clustering are performed as well as DPC-K-means on the ARI metric. A one-sample t-test method is used to evaluate the DPC-K-means algorithm significance on different datasets. Taking the FMI evaluation metric in the BBC dataset as an example of significance testing, the process is as follows: Firstly, a test hypothesis is established and the threshold chosen for statistical significance was determined (H0:μ=μ0, α=0.1). Secondly, the t is calculated:
(11)t=x¯−μ0sn=0.9225−μ0s5=0.9225−0.73620.26575=1.568,v=5−1=4,where x¯ represents the FMI value obtained by DPC-K-means on the BBC dataset, μ0 is the mean FMI of the five comparison algorithms on the BBC dataset, s represents the standard deviation FMI of the five comparison algorithms on the BBC dataset, and n is the sample size. The degree of freedom v used in this test is 4. Finally, the table was queried of t-distribution, the p value was determined, and an inference conclusion was made. According to α=0.1 and v=4, the p value is 1.533, t=1.568>p, and H0 is rejected, indicating the difference between the FMI metric of DPC-K-means on the BBC dataset, and the FMI value of other comparison algorithms is statistically significant. According to the above significance test steps, the t-test results of DPC-K-means were calculated on the ARI, NMI, and FMI evaluation metrics. The results are shown in Tables 11–13.Table 11
The results of thet-test of DPC-K-means on ARI.
DatasetMeanStandard deviationtpDifferenceBBC0.66240.34381.3981.533No20-newsgroups4 groups0.76170.35931.3481.533No5 groups0.65740.30261.4391.533No6 groups0.48220.22931.8971.533Yes7 groups0.45180.18491.8861.533Yes8 groups0.34200.17671.8201.533YesSports Article0.08750.09652.4691.533YesAsian Religious0.0930.08131.7501.533YesStack Overflow0.08420.16941.1111.533NoAmazon0.00260.00501.1501.533NoTable 12
The results of thet-test of DPC-K-means on NMI.
DatasetMeanStandard deviationtpDifferenceBBC0.71410.23611.7871.533Yes20-newsgroups4 groups0.78630.26871.5811.533Yes5 groups0.71140.20691.4131.533No6 groups0.62170.17941.8751.533Yes7 groups0.58350.13692.0291.533Yes8 groups0.50360.16992.3991.533YesSports Article0.10620.08692.0781.533YesAsian Religious0.14750.12902.0781.533YesStack Overflow0.03080.03561.9381.533YesAmazon0.00330.00511.4401.533NoTable 13
The results of thet-test of DPC-K-means on FMI.
DatasetMeanStandard deviationtpDifferenceBBC0.73620.26571.5681.533Yes20-newsgroups4 groups0.81260.28601.3271.533No5 groups0.72690.25481.4001.533No6 groups0.61190.22902.3111.533Yes7 groups0.57280.20142.3251.533Yes8 groups0.49260.16482.1841.533YesSports Article0.56260.23261.6091.533YesAsian Religious0.40510.10281.6321.533YesStack Overflow0.38760.14082.5981.533YesAmazon0.60890.19461.2681.533NoAs shown in Table11, there are significant differences in the ARI metric of DPC-K-means on five datasets, and as shown in Table 12 there are significant differences in the NMI metric of DPC-K-means on eight datasets. It can be seen from Table 13 that DPC-K-means have significant difference in the FMI metric on the seven datasets. DPC-K-means are statistically significant on most datasets. Combined with Tables 9 and 10, it further shows that DPC-K-means is better than other comparison algorithms.The clustering performance of DPC-K-means is better than K-means because DPC-K-means can select the number of clusters and obtain the initial clustering center. The number of clusters and the initial clustering centers can be used in the K-means algorithm, which achieves better clustering performance than K-means. Figures11 and 12 illustrate the clustering centers automatically determined by DPC-K-means which are closer to the real class centers.Figure 11
The BBC news dataset clustering center of K-means marked in black, and DPC-K-means clustering center marked in red and the 3D clustering results.Figure 12
The 4 groups in the 20-newsgroups dataset clustering center of K-means marked in black, and DPC-K-means clustering center marked in red and the 3D clustering results.Tables6–9 show that the clustering metrics changed significantly from 4 newsgroups to 8 newsgroups; this was caused by the loss of clustering due to irregular data distribution. Due to the inherent nature of the DPC algorithm, it cannot identify the phenomenon of “False peaks,” and its clustering effect on “No density peaks” datasets is low, which are all factors that affect the accuracy of the DPC-K-means algorithm. The algorithm is limited in its processing of more complex datasets.DPC-K-means has a parametercosc, which is the cut-off distance. The value suggested in the literature [12] is set to the nearest neighbour number of the sample, approximately 1%~2% of the total dataset size. In the experiment, we were able to obtain the correct number of class clusters according to this valued principle. This parameter has no significant influence on the result of the algorithm within the value range of 1%–2% of the entire dataset size. The K-nearest neighbour method was used to establish the similarity matrix in the Spectral Clustering parameters in the experiment. The damping factor in Affinity Propagation was set to 0.9, and the nearest distance measurement of the DBSCAN parameter value was set to “cosine” by cosine similarity.


## 4. Conclusions

This study proposed a Stacked-Random Projection (SRP) dimension reduction framework based on deep networks and an improved K-means text clustering algorithm based on density peak (DPC-K-means). In the experiment, SRP, the improved DPC, and DPC-K-means were validated by using different datasets. Firstly, we compared SRP with PCA, MDS, and Random Projection. Multiple evaluation metrics demonstrated that SRP maintained a sufficient balance between running time and distance before and after dimension reduction. Secondly, we compared the difference between the Euclidean distance and cosine similarity in calculating DPC local density. Cosine similarity is more suitable for text vector calculation. Finally, DPC-K-means are an improved K-means algorithm that uses a text feature vector’s cosine similarity to calculate local density and get the initial clustering center and cluster number. Then, the K-means algorithm is used for clustering. We compared DPC-K-means with DPC, DBSCAN, Spectral Clustering, and Affinity Propagation. We found that DPC-K-means can accurately determine the number of clusters and the initial clustering centers of high-dimensional text data. It is superior to other clustering algorithms in ARI, NMI, FMI, and MSE. Furthermore, we analyzed the influence of parameters on the algorithm and limitations of our proposed methods. We will focus on determining the number of layers and the target dimension of each layer dimensionality reduction for future work and improve the matching degree between DPC-K-means and datasets.



---

*Source: 8881112-2020-10-28.xml*