# Large-Scale Spectral Clustering Based on Representative Points

Authors: Libo Yang; Xuemei Liu; Feiping Nie; Mingtang Liu
Journal: Mathematical Problems in Engineering
 (2019)

---

## Abstract

Spectral clustering (SC) has attracted more and more attention due to its effectiveness in machine learning. However, most traditional spectral clustering methods still face challenges in the successful application of large-scale spectral clustering problems mainly due to their high computational complexityοn3, where n is the number of samples. In order to achieve fast spectral clustering, we propose a novel approach, called representative point-based spectral clustering (RPSC), to efficiently deal with the large-scale spectral clustering problem. The proposed method first generates two-layer representative points successively by BKHK (balanced k-means-based hierarchical k-means). Then it constructs the hierarchical bipartite graph and performs spectral analysis on the graph. Specifically, we construct the similarity matrix using the parameter-free neighbor assignment method, which avoids the need to tune the extra parameters. Furthermore, we perform the coclustering on the final similarity matrix. The coclustering mechanism takes advantage of the cooccurring cluster structure among the representative points and the original data to strengthen the clustering performance. As a result, the computational complexity can be significantly reduced and the clustering accuracy can be improved. Extensive experiments on several large-scale data sets show the effectiveness, efficiency, and stability of the proposed method.


---

## Body

## 1. Introduction

Clustering is one of the fundamental topics in unsupervised learning. It has been widely and successfully applied in data mining, pattern recognition, and many other fields. Spectral clustering is one of the most popular methods used in unsupervised clustering tasks [1–4]. Especially, it performs well in nonconvex pattern and linear nonseparable clusters and converges to the global optimal solution [5]. However, spectral clustering is limited in its applicability to large-scale problems. Its bottleneck is the high computational complexity [6–8]. Many approaches have been proposed to speed up spectral clustering [9–11]. Unfortunately, these methods usually sacrifice a lot of information of the raw data, resulting in performance degradation.The traditional spectral clustering needs two independent steps: constructing similarity graph and performing spectral analysis [12]. Both the steps are computational expensive for large-scale data, and their computational complexity is οn2 and οn3, respectively. The conventional spectral clustering has three methods to construct the similarity graph which is constructed by pairwise similarities or pairwise distances. The goal is to model the local neighborhood relationships between the data points [13]. The first method is to construct the ε−neighborhood graph in which ε is the pairwise distance. All points whose pairwise distances are smaller than ε can be connected. In this method, a large amount of information between sample points is discarded because of this single and rough criterion. The second method is to generate similarity graph by the k-nearest neighbor method in which two vertices p and q are connected if the distance between p and q is among the k-th smallest distances from p to other objects. The last similarity graph is the fully connected graph. That means all points with positive similarity are connected with each other. The computational cost of all graphs mentioned above is very expensive. In the past years, a lot of extensions of spectral clustering have been proposed. Wang and Wu proposed to simultaneously learn clustered orthogonal projection and optimized local graph structure for each view, while enjoying the same magnitude over them both for all views, leading to a superior multiview spectral clustering consensus [14]. Houthuys et al. proposed a new model multiview kernel spectral clustering (MVKSC). This model is formulated as a weighted kernel canonical correlation analysis in a primal-dual optimization setting typical of least-squares support-vector machines (LSSVM). A coupling term enforces the clustering scores corresponding to the different views to align [15]. Tao et al. proposed a novel robust spectral ensemble clustering algorithm. It learns low-rank representation for the coassociation matrix to uncover the cluster structure and handle the noises, and meanwhile, it performs spectral clustering with the learned representation to seek for a consensus partition [16]. Huang et al. proposed ultrascalable spectral clustering (U-SPEC) and ultrascalable ensemble clustering (U-SENC). In U-SPEC, a hybrid representative selection strategy and a fast approximation method for K-nearest representatives are proposed for the construction of a sparse affinity submatrix. In U-SENC, multiple U-SPEC clusters are further integrated into an ensemble clustering framework to enhance the robustness of U-SPEC [17]. Yang et al. designed a constraint projection for a semisupervised spectral clustering ensemble (CPSSSCE) model. In this method, the original data are transformed to lower-dimensional representations by constraint projection before base clustering. Then, a similarity matrix is constructed using the base clustering results and modified using pairwise constraints. Finally, the spectral clustering algorithm is applied to process the similarity matrix to obtain a consensus cluster result [18].In recent years, many spectral clustering methods for large-scale data have been proposed. Zhao et al. proposed a spectral clustering based on iterative optimization (SCIO), which solves the spectral decomposition problem of large-scale and high-dimensional data set, and this method performs on multitask clustering [19]. The nonnegative matrix factorization (NMF) has been proposed as the relaxation technique for clustering with excellent performance [20, 21]. Yang et al. proposed a multitask spectral clustering model (MTSC) by exploring two types of correlations: intertask clustering correlation and intratask learning correlation [22]. He et al. reduced the complexity of spectral clustering by employing random Fourier features to explicitly represent data in kernel space [23]. Semertzidis et al. proposed an efficient spectral clustering method for large-scale data sets in which a set of pairwise constraints were given to increase clustering accuracy and reduce clustering complexity [24]. These methods greatly extend spectral clustering for large-scale data.Recently, the representative point-based graph has widely been adopted in the spectral-based method to speed up the procedure. Shinnou and Sasaki [25] constructed the similarity matrix on “committees” of raw data points, and large-scale spectral clustering was performed using the reduced similarity matrix. Yan et al. [26] introduced a fast spectral clustering method which used the k-means method to produce a set of reduced representative points for approximate spectral clustering (KASP: k-means-based approximate spectral clustering). Liu et al. [27] addressed the scalability issue plaguing graph-based semisupervised learning via the anchor points. Liu et al. [28] proposed an efficient cluster algorithm for large-scale graph data using spectral methods. In order to compress the original graph into a sparse bipartite graph, they repeatedly generate a small number of “supernodes” connected to the regular nodes. Cai and Chen [29] and Cai [30] proposed landmark-based spectral clustering and spectral dimensionality reduction. Li et al. [31] adopted the salient point-based subbipartite graph to achieve large-scale multiview spectral clustering. Wang et al. [32] explored the spectral and spatial properties of the hyperspectral image and proposed a novel method, called fast spectral clustering with anchor graph (FSCAG). This method solved the large-scale hyperspectral image clustering problem. These methods mentioned above adopt representative point-based strategy to construct the similarity graph to accelerate the procedure of spectral clustering.The representative point generation is one of the extremely important steps in representative point-based spectral clustering methods. These generated points directly affect the final performance. There are two main strategies to generate representative points. One is random selection, and the other is the k-means method. The random generation strategy is efficient, but the performance is not stable because of the randomness of representative points. Generally speaking, the k-means generation strategy can achieve good performance while the computational cost is expensive. Much effort has been devoted for accelerating the k-means procedure, e.g., early stopping iteration [33] or performing down-sampling on data, but they can also sacrifice some performance.To tackle the problem, a novel and efficient representative point-based spectral clustering method is proposed to deal with large-scale data sets. Three main contributions of this paper are listed as follows:(1)
The two-layer bipartite graph is constructed using the generated representation points by BKHK. BKHK has low computational complexity and high performance compared with k-means.(2)
We construct the similarity matrix between adjacent layers using the parameter-free neighbor assignment method, which avoids extra parameters. Furthermore, the final similarity matrix is easily obtained by multiplying the similarity matrix between adjacent layers.(3)
We perform the coclustering on the final similarity matrix. The coclustering mechanism takes advantage of the cooccurring cluster structure among the representative points and the original data to strengthen the clustering performance.(4)
Extensive experiments on several large-scale data sets demonstrate the effectiveness, efficiency, and stability of the proposed method.


## 2. Representative Points Generation

The most important step of representative point-based spectral clustering is the generation of representative points. In this paper, we design two-layer representative points by BKHK to gradually reduce the data size. BKHK adopts balanced binary tree structure; in other words, it iteratively segments the data into two cluster with the same number of samples [34].Given a data matrixX=x1,x2,…,xnT∈ℝn×d, where xi∈ℝd denotes the i-th sample, n is the number of samples, and d is the dimensionality of the data. The two class k-means can be formulated as follows:(1)minG∈Ind,1TG=κ,ιX−GCTF2,where G∈ℝn×2 is the index matrix, gij equals 1 or 0, the value of gi1 is 1, and the value of gi2 is 0 if the i-th sample belongs to the first cluster, or the value of gi1 is 0 and the value of gi2 is 1 otherwise, C∈Rd×2 is the center of the cluster, 1 is the column-vector of all ones, κ and ι are the number of samples in these two clusters, and k is the integer portion of n/2. Therefore, we have l=n−k. Furthermore, problem (1) can be rewritten as(2)minG∈Ind,1TG=κ,ι∑i=1n∑j=12xi−cj22gij,where cj is the j-th column of C.We define matrixE∈ℝn×2 and the j-th element of the i-th row of E is eij=xi−cj22, so problem (2) can be rewritten as(3)minG∈Ind,1TE=κ,ιTrETG.For convenience, letg denote the first column of G, obviously, the second column is 1−g. Substitute g and 1−g into problem (3), we have(4)ming∈0,1,1Tg=κgTe1−e2.Letgi=1 when the i-th element of e1−e2 is the κ minimum of all its elements. Obviously, the solution to the problem in problem (4) is obtained.We can obtain the first-layer representative points by performing above process iteratively. Then the procedure is repeated on the first-layer representative points to generate the second-layer representative points.


## 3. Similarity Matrix

Similar to conventional similarity graph construction, the similarity graph construction between the obtained representative points and raw points also has the problem of selecting the neighbor assignment strategy. The kernel-based neighbor assignment strategy usually is sued in conventional methods, but it always brings extra parameters [13]. A parameter-free method is adopted in this paper [35]. Let U∈ℝm×d denote the generated representative points, and Ui is the set of k-nearest representative points for the i-th sample. hxi,uj=xi−uj22 is the distance between the i-th sample and its j-th nearest representative point. The neighbor assignment strategy can be formulated as follows:(5)minbiT1=1,bi≥0∑j=1mhxi,yjbij+γ∑j=1mbij2,where B∈ℝn×m is the similarity matrix between raw data and representative points and bij is the element of B. bij denotes the similarity between the i-th data point and the j-th representative point. Fllow Nie et al. [35], γ is equal to k/2hi,k+1−1/2∑j=1khi,j. The solution to problem (5) is as follows:(6)bij=hxi,uk+1−hxi,uj∑j′=1khxi,uk+1−hxi,uj′.The two-layer representative points are successively generated by performing BKHK.B1∈ℝn×m1 denotes the similarity matrix between original data points and the first-layer representative points which can be obtained by solving problem (6), and B11 equals 1. B2∈ℝm1×m2 denotes the similarity matrix between the first-layer representative points and the second-layer representative points which can be obtained by the same process, and B21 equals 1. The final similarity matrix between the raw data points and the second-layer representative points can be obtained as follows:(7)A=B1×B2,where A∈ℝn×m2 is the final similarity matrix.


## 4. Coclustering on Similarity Matrix

As the same as document data, duality exists between the raw data points and the representative points. The representative points can be clustered based on their relations with the corresponding raw data clusters, while the raw data clusters are obtained according to their associations with distinct representative point clusters. In order to make full use of the duality information and strengthen the clustering performance, the coclustering method is adopted on the similarity matrix between the raw data points and the second-layer representative points.


### 4.1. Graph Partitioning

A signifies association between an original point, and a representative point signifies an edge in bipartite graph. It is easy to verify that the adjacency matrix of the bipartite graph can be written as follows:(8)M=0AAT0,where M∈ℝn+m2×n+m2 denotes the adjacency matrix and A∈ℝn×m2 is the similarity matrix between the raw data points and the second-layer representative points.Therefore, the degree matrixD of M can be obtained as follows:(9)D=D100D2,where D1 and D2 are the diagonal matrices whose entries are D1i,i=∑jAij and D2j,j=∑iAij, respectively. Obviously, the Laplacian matrix is(10)L=D−M=D1−A−ATD2.To partition the bipartite graph, the optimization problem of finding the minimum normalized cut can be formalized as the second eigenvector of the generalized eigenvalue problem with suitable relaxation [1]:(11)Lx=λDx.Substitute equations (9) and (10) into equation (11), we get(12)D1−A−ATD2x1x2=λD100D2x1x2.Furthermore, equation (12) can be written as follows:(13)D11/2x1−D1−1/2Ax2=λD11/2x1,−D2−1/2ATx1+D21/2x2=λD21/2x2.Lettingu=D11/2x1 and v=D21/2x2, and after a little algebraic manipulation, equation (13) can be written as follows:(14)D1−1/2AD2−1/2v=1−λu,D2−1/2ATD1−1/2u=1−λv.Obviously, equation (14) is the singular value decomposition of the normalized matrix An=D1−1/2AD2−1/2. u is the left singular vector, and v is the right singular vector while 1−λ is the corresponding singular value. Thus instead of directly computing the eigenvector of (12), we prefer to compute the left and right singular vectors of An to speed up the algorithm.In order to achieve multipartitioning, the data set can be formed as follows:(15)Z=D1−1/2UD2−1/2V,where U=u2,u3,…,uk+1 and V=v2,v3,…,vk+1 come from the k+1 minimum left and right singular vectors of An.To approximate the optimal multipartitioning, we can look for pointsm1,m2,…,mk such that the sum of squares is minimized [27]:(16)∑j=1k∑Zi∈mjZi−mj2.Obviously, the minimum of (16) can be achieved by the classical k-means algorithm.


### 4.2. Representative Point-Based Spectral Clustering

As mentioned, two-layer representative points can be successively generated by BKHK for large-scale spectral clustering and similarity graph can be constructed. Then coclustering can be performed on the final similarity matrix between original data points and representative points. So we propose a novel spectral clustering approach for large-scale data, called representative point-based spectral clustering (RPSC). The detailed algorithm is summarized in Algorithm1.Algorithm 1:Representative point-based spectral clustering.
Input: Data matrix
X
=
x
1
,
x
2
,
…
,
x
n
T
∈
ℝ
n
×
d;
Output:k clusters;
(1)
Produce the two-layer representative points using BKHK successively;
(2)
Construct the similarity matrixes B1 and B2 according to (6);
(3)
Construct the final similarity matrixA between original data and the second-layer representative points according to (7);
(4)
Compute D1 and D2:D1i,i=∑jAij; D2j,j=∑iAij;
(5)
ComputeAn=D1−1/2AD2−1/2;
(6)
Computek singular vectors of An: u2,u3,…,uℓ+1, v2,v3,…,vℓ+1;
(7)
Form the matrixZ=D1−1/2UD2−1/2V;
(8)
Run the k-means algorithm on the matrixZ to obtain the desired k-way multipartitioning.


## 4.1. Graph Partitioning

A signifies association between an original point, and a representative point signifies an edge in bipartite graph. It is easy to verify that the adjacency matrix of the bipartite graph can be written as follows:(8)M=0AAT0,where M∈ℝn+m2×n+m2 denotes the adjacency matrix and A∈ℝn×m2 is the similarity matrix between the raw data points and the second-layer representative points.Therefore, the degree matrixD of M can be obtained as follows:(9)D=D100D2,where D1 and D2 are the diagonal matrices whose entries are D1i,i=∑jAij and D2j,j=∑iAij, respectively. Obviously, the Laplacian matrix is(10)L=D−M=D1−A−ATD2.To partition the bipartite graph, the optimization problem of finding the minimum normalized cut can be formalized as the second eigenvector of the generalized eigenvalue problem with suitable relaxation [1]:(11)Lx=λDx.Substitute equations (9) and (10) into equation (11), we get(12)D1−A−ATD2x1x2=λD100D2x1x2.Furthermore, equation (12) can be written as follows:(13)D11/2x1−D1−1/2Ax2=λD11/2x1,−D2−1/2ATx1+D21/2x2=λD21/2x2.Lettingu=D11/2x1 and v=D21/2x2, and after a little algebraic manipulation, equation (13) can be written as follows:(14)D1−1/2AD2−1/2v=1−λu,D2−1/2ATD1−1/2u=1−λv.Obviously, equation (14) is the singular value decomposition of the normalized matrix An=D1−1/2AD2−1/2. u is the left singular vector, and v is the right singular vector while 1−λ is the corresponding singular value. Thus instead of directly computing the eigenvector of (12), we prefer to compute the left and right singular vectors of An to speed up the algorithm.In order to achieve multipartitioning, the data set can be formed as follows:(15)Z=D1−1/2UD2−1/2V,where U=u2,u3,…,uk+1 and V=v2,v3,…,vk+1 come from the k+1 minimum left and right singular vectors of An.To approximate the optimal multipartitioning, we can look for pointsm1,m2,…,mk such that the sum of squares is minimized [27]:(16)∑j=1k∑Zi∈mjZi−mj2.Obviously, the minimum of (16) can be achieved by the classical k-means algorithm.


## 4.2. Representative Point-Based Spectral Clustering

As mentioned, two-layer representative points can be successively generated by BKHK for large-scale spectral clustering and similarity graph can be constructed. Then coclustering can be performed on the final similarity matrix between original data points and representative points. So we propose a novel spectral clustering approach for large-scale data, called representative point-based spectral clustering (RPSC). The detailed algorithm is summarized in Algorithm1.Algorithm 1:Representative point-based spectral clustering.
Input: Data matrix
X
=
x
1
,
x
2
,
…
,
x
n
T
∈
ℝ
n
×
d;
Output:k clusters;
(1)
Produce the two-layer representative points using BKHK successively;
(2)
Construct the similarity matrixes B1 and B2 according to (6);
(3)
Construct the final similarity matrixA between original data and the second-layer representative points according to (7);
(4)
Compute D1 and D2:D1i,i=∑jAij; D2j,j=∑iAij;
(5)
ComputeAn=D1−1/2AD2−1/2;
(6)
Computek singular vectors of An: u2,u3,…,uℓ+1, v2,v3,…,vℓ+1;
(7)
Form the matrixZ=D1−1/2UD2−1/2V;
(8)
Run the k-means algorithm on the matrixZ to obtain the desired k-way multipartitioning.


## 5. Experiments

In this section, several experiments are conducted to demonstrate the effectiveness and efficiency of the proposed RPSC.


### 5.1. Data Sets Description

In the experiments, four large-scale data sets are collected to illustrate the performance of different spectral clustering methods. These data sets include two handwritten digit data sets, USPS, MNIST, one connect-4 game data set, CONNECT-4, and one capital letters in the English alphabet, LETTER. These data sets were downloaded from the UCI machine learning repository and the LibSVM data sets page. The brief description is listed below:USPS. A data set of handwritten digits (0–9). It contains 9298 samples from ten classes. Each sample has 256 features.MNIST. A data set of handwritten digits (0–9). It has 70000 samples from ten classes. Each sample has 784 features.CONNECT-4. A data set of connect-4 game. It consists of 67557 samples from three classes. Each sample has 126 features.LETTER. A data set of 26 capital letters in the English alphabet. It is composed of 20000 samples from 26 classes. Each sample has 16 features.


### 5.2. Evaluation Metric

All the codes in the experiments are implemented in MATLAB R2016a and run on a Windows 8.1 machine with 32 GB main memory. Every method was run 10 times, and the mean results were recorded. The average clustering accuracy and the average clustering time are displayed in Tables1 and 2, respectively. The clustering accuracy and the clustering time on different number of two-layer representative points of two data sets are recorded in Figures 1–4.Table 1
Clustering accuracy.
Data sets
Spectral clustering methods
SC
LSC-K
LSC-R
KASP
RPSC
USPS
43.27
60.83
58.30
55.71
61.65
MNIST
—
50.40
41.85
44.56
53.53
Connect-4
—
24.96
26.42
36.90
50.38
Letter
23.61
23.24
21.73
16.65
26.98Table 2
Clustering time.
Data sets
Spectral clustering methods
SC
LSC-K
LSC-R
KASP
RPSC
USPS
430.35
186.25
2.28
2.55
23.26
MNIST
—
432.40
8.17
109.06
49.93
Connect-4
—
149.29
5.07
21.68
20.93
Letter
635.86
27.85
4.45
1.40
14.25Figure 1
Clustering accuracy based on two-layer representative points of Connect-4.Figure 2
Clustering accuracy based on two-layer representative points of Letter.Figure 3
Clustering time based on two-layer representative points of Connect-4.Figure 4
Clustering time based on two-layer representative points of Letter.


### 5.3. Experimental Results

The performance of five methods evaluated by accuracy is reported in Table1. The conventional algorithm SC can only run on the small data sets USPS and Letter, and the clustering accuracy is low. LSC-K achieves high clustering accuracy on USPS and MNIST, but it does not perform well on LETTER and CONNECT-4. LSC-R has the low clustering accuracy on almost all data sets. KASP only performs well on one of the four data sets. The proposed RPSC achieves pretty high performance on all data sets. Table 2 summarizes the clustering time comparison on four data sets. Obviously, SC and LSC-K have high computational cost. KASP has low computational cost on smaller data sets, but the time cost is very high on large data sets. LSC-R is efficient while the performance is poor. It is easy to see that the proposed RPSC is efficient on all data sets, especially large data sets. Overall, RPSC is the best choice for large data sets among the compared approaches.Several experiments were conducted on CONNECT-4 and LETTER to demonstrate the influence of the parameter (number of two-layer representative points) for clustering time and performance. Figures1–4 display that more representative points can increase the clustering accuracy at the beginning, but overly large amounts of representative points are useless. However increasing number of representative points can make the time cost increase.


## 5.1. Data Sets Description

In the experiments, four large-scale data sets are collected to illustrate the performance of different spectral clustering methods. These data sets include two handwritten digit data sets, USPS, MNIST, one connect-4 game data set, CONNECT-4, and one capital letters in the English alphabet, LETTER. These data sets were downloaded from the UCI machine learning repository and the LibSVM data sets page. The brief description is listed below:USPS. A data set of handwritten digits (0–9). It contains 9298 samples from ten classes. Each sample has 256 features.MNIST. A data set of handwritten digits (0–9). It has 70000 samples from ten classes. Each sample has 784 features.CONNECT-4. A data set of connect-4 game. It consists of 67557 samples from three classes. Each sample has 126 features.LETTER. A data set of 26 capital letters in the English alphabet. It is composed of 20000 samples from 26 classes. Each sample has 16 features.


## 5.2. Evaluation Metric

All the codes in the experiments are implemented in MATLAB R2016a and run on a Windows 8.1 machine with 32 GB main memory. Every method was run 10 times, and the mean results were recorded. The average clustering accuracy and the average clustering time are displayed in Tables1 and 2, respectively. The clustering accuracy and the clustering time on different number of two-layer representative points of two data sets are recorded in Figures 1–4.Table 1
Clustering accuracy.
Data sets
Spectral clustering methods
SC
LSC-K
LSC-R
KASP
RPSC
USPS
43.27
60.83
58.30
55.71
61.65
MNIST
—
50.40
41.85
44.56
53.53
Connect-4
—
24.96
26.42
36.90
50.38
Letter
23.61
23.24
21.73
16.65
26.98Table 2
Clustering time.
Data sets
Spectral clustering methods
SC
LSC-K
LSC-R
KASP
RPSC
USPS
430.35
186.25
2.28
2.55
23.26
MNIST
—
432.40
8.17
109.06
49.93
Connect-4
—
149.29
5.07
21.68
20.93
Letter
635.86
27.85
4.45
1.40
14.25Figure 1
Clustering accuracy based on two-layer representative points of Connect-4.Figure 2
Clustering accuracy based on two-layer representative points of Letter.Figure 3
Clustering time based on two-layer representative points of Connect-4.Figure 4
Clustering time based on two-layer representative points of Letter.


## 5.3. Experimental Results

The performance of five methods evaluated by accuracy is reported in Table1. The conventional algorithm SC can only run on the small data sets USPS and Letter, and the clustering accuracy is low. LSC-K achieves high clustering accuracy on USPS and MNIST, but it does not perform well on LETTER and CONNECT-4. LSC-R has the low clustering accuracy on almost all data sets. KASP only performs well on one of the four data sets. The proposed RPSC achieves pretty high performance on all data sets. Table 2 summarizes the clustering time comparison on four data sets. Obviously, SC and LSC-K have high computational cost. KASP has low computational cost on smaller data sets, but the time cost is very high on large data sets. LSC-R is efficient while the performance is poor. It is easy to see that the proposed RPSC is efficient on all data sets, especially large data sets. Overall, RPSC is the best choice for large data sets among the compared approaches.Several experiments were conducted on CONNECT-4 and LETTER to demonstrate the influence of the parameter (number of two-layer representative points) for clustering time and performance. Figures1–4 display that more representative points can increase the clustering accuracy at the beginning, but overly large amounts of representative points are useless. However increasing number of representative points can make the time cost increase.


## 6. Conclusions

In this paper, we proposed a novel representative point-based spectral clustering approach, named RPSC, based on the two-layer bipartite graph. First, two-layer representative points are generated successively by BKHK. Then, the similarity matrices between adjacent layers are constructed. Different from the conventional kernel-based neighbor assignment strategy, we adopt a parameter-free yet effective neighbor assignment method, which avoids the need to tune the heat-kernel parameter. Furthermore, the final similarity matrix can be easily obtained by multiplying the similarity matrices between adjacent layers. Finally, the coclustering is performed on the final similarity matrix. The coclustering mechanism takes advantage of the cooccurring cluster structure among the last-layer representative points and the original data to strengthen the clustering performance. As a result, the computational complexity can be greatly reduced and the clustering accuracy can be improved. Extensive experiments conducted on 4 large data sets demonstrate the efficiency and effectiveness of the proposed RPSC in terms of computational speed and clustering accuracy. In future work, we will consider designing a more efficient representative point generation algorithm. Furthermore, the clustering ensemble based on the proposed method is an interesting research.



---

*Source: 5864020-2019-12-09.xml*