Learning with Adaptive Neighbors for Image Clustering

1 Introduction

Clustering, which aims to partition the data points from different groups such that the samples in the same group have high similarity to each other, has been playing an important role in data mining applications. Lots of clustering algorithms have been proposed in the past decades, such as K-means clustering [MacQueen and others, 1967; Gao et al., 2018], hierarchical clustering [Johnson, 1967], support vector clustering [Ben-Hur et al., 2001; Liu et al., 2018], maximum margin clustering [Xu et al., 2005; Wang et al., 2017], multi-view clustering [Cai et al., 2013; Wang et al., 2013]. As the manifold information and data graph are utilized in the clustering model, the graph-based clustering method often outperforms K-means method, especially for a small number of clusters.

Some clustering methods based on graphical representations of the relationships among data have achieved the stateof-the-art performance, including ratio cut [Hagen and Kahng, 1992], spectral clustering [Ng et al., 2002] and normal-

∗Corresponding author: Q. Gao. (qxgao@xidian.edu.cn)

†Corresponding author: Z. Yang. (yangzh@buaa.edu.cn)

ized cut [Shi and Malik, 2000]. [Ding et al., 2005] gave a discussion of the relations among these graph-based clustering methods. To enhance the learning results, graph-based learning methods often require pre-processing on the affinity matrix. The doubly stochastic matrix (also called bistochastic matrix) was utilized to normalize the affinity matrix and showed promising clustering results [Zass and Shashua, 2007]. For example, [Nie et al., 2011] attempted to cluster data in a high dimension. [Nie et al., 2014] constructed the similarity matrix by adaptively selecting reliable neighbors of data. Additionally, sparse subspace clustering (SSC) was proposed in [Elhamifar and Vidal, 2013] to explore a sparse representation corresponding to the data from the same subspace. After obtaining the representation of the subspace, the spectral clustering can be performed on such new representation. The low-rank subspace segmentation was proposed in [Liu et al., 2013] to find the subspace structure with a low-rank representation.

Although all above clustering techniques have achieved state-of-the-art performance, they still exist some disadvantages. (1) Such methods tend to conduct the similarity matrix from original data but rarely modify it. The real world datasets often contain outliers and noise that result in the unreliable and inaccurate matrix which will impair the finally performance. (2) These methods involve a two-stage process in which a graph is formed from the data points, and then various optimization procedures are invoked on this fixed input data graph [Nie et al., 2016], which result in the final clustering structures are not represented explicitly in the data graph. (3) They are sensitive to the particular graph construction methods because the final clustering results are dependent on the quality of the input data graph.

In this paper a novel graph-based clustering model is proposed to learn a graph with exactly c connected components (where c is the number of clusters). Instead of fixing the original data graph associated to the affinity matrix, the proposed model tries to learn a new similarity block diagonal matrix which has c connected components. Then, the obtained similarity matrix can be directly used for the final clustering task, rather than requiring post-processing to extract the clustering indicators. To guarantee the existence of exactly c connected components, in our model, a rank constraint on the Laplacian graph of the similarity matrix is imposed. A non-greedy iterative algorithm is presented to efficiently solve our model and the convergence of the proposed optimization method is also proved. Experimental results on real-world benchmark datasets illustrate that our proposed method outperforms other related methods in most cases.

Notation: Throughout the paper, all the matrices are written as uppercase. For a matrix M ∈ Rd×n , the i-th row and the ij-th element of M are denoted by mi and mij, respectively. The Frobenius norm of matrix M is denoted by ‖M‖F . The trace of matrix M is denoted by tr(M), and the transpose of matrix M is denoted by MT . I denotes an identity matrix, and 1 denotes a column vector with all the elements as one. The L2-norm and the L0-norm of vector m is denoted by ‖m‖2 and ‖m‖0 , respectively.

2 NewClustering Formulations

To solve the three challenges mentioned in the introduction, we need to learn a new data graph S based on the given data graph A so that the graph S is more suitable for the final clustering task. In order to construct a clustering objective function based on this motivation, we start from the following theorem 1. Given an affinity matrix S which is nonnegative, then the Laplacian matrix Ls = Ds - (ST + S)/2 has the following important property.

Theorem 1 [Chung, 1997; Mohar et al., 1991]: The multiplicity c of the eigenvalue zero of the Laplacian matrix Ls (nonnegative) is equal to the number of connected components in the graph with the similarity matrix S.

Theorem 1 indicates that if rank(Ls) =n- c, then the graph will be an ideal graph based on which we already partition the data points into c clusters, and there is no need to perform K-means or other discretization procedures.

Motivated by theorem 1, we aim to learn a similarity matrix S ∈ Rn×n (n is the number of samples) such that the corresponding Laplacian matrix Ls satisfied rank(Ls) =n - c. Under this constraint, the learned S is block diagonal matrix, and we can directly partition the data points into c clusters based on S [Nie et al., 2014]. To avoid the case that some rows of S are all zeros, we also constrain the S such that the sum of each row of S equals to one. Under all these constraints, we learn a similarity matrix S according to the following objective function.

The Lagrange function of Eq. (1) can be written as:

where Λ denotes the Lagrange multiplier, and Γ(Λ, S) denotes the formalized term derived from constraints. Taking the derivative of Eq. (2) w.r.t S and setting the derivative to zero, we get following equation:

where

As v is related to the matrix S, we cannot solve Eq. (3) directly. However, if v is set to be stationary, Eq. (3) can be considered accounting for following problem:

We can optimize Eq. (5) through an alternative method. Under the assumption that v is stationary, the Lagrange function of Eq. (2) can apply to Eq. (5). If S is solved by Eq. (5), the value of v can be updated correspondingly.

3 Optimization Algorithms

Let σi(Ls) denote the i-th smallest eigenvalue of Ls. σi(Ls) ≥ 0 because Ls is positive semi-definite. Furthermore, if ∑ci=1 σi(Ls) = 0, the constraint condition rank(Ls) =n - c will be satisfied. According to Ky Fan's Theorem [Fan, 1949], we have:

Therefore, the problem (5) can be equivalent to the following problem:

where γ is a very large number, and the optimal solution of the problem (7) can let equation ∑ci=1 σi(Ls) = 0 hold.

3.1 Fix S, Update v andH

When S is fixed, we can easily calculate the value of v by Eq. (4). So the first and second item of problem (7) can be seen as constants, then it transforms into:

The optimal solution H is composed of the eigenvectors of Ls corresponding to the c smallest eigenvalues.

3.2 Fix v andH, Update S

When v and H are fixed, after a simple algebra, the Eq. (7) becomes:min

where dij = v ‖ai - aj‖22 .

Note that there is an elementary but very important equation in spectral analysis

Denote eij = ‖hi -hj‖22 , since the Eq. (9) is independent between different i, we can solve following problem individually for each i:

Let fi ∈ Rn×1 denote the vector with the j-th element as fij = dij +λeij, then Eq. (11) is rewritten as follow:

The problem (12) can be solved by an efficient iterative algorithm [Huang et al., 2015] and the intermediate variable β can be determined using the number of adaptive neighbours [Nie et al., 2017]. By iteratively solving problem (5), we can get the final S in the objective function Eq. (1). The pseudo code is summarized in Algorithm 1. In this algorithm, we update the m nearest similarities for each sample in S and thus the complexity of updating S and H ( only requires computing the top c eigenvectors of a very sparse matrix) is reduced significantly. In our further work, we will make this technique reliable on very large scale datasets.

Algorithm 1:

Input: affinity matrix A ∈ Rn×n , cluster number c, parameter γ.

Initialize v = 1, then each row si of S can be initialized by solving the following problem:

repeat

1. Update v by using Eq. (4).
2. Update H by solving the Eq. (8).
3. Update each row of S by solving the Eq. (12). until converge

Output: similarity matrix S ∈ Rn×n with exact c connected components.

4 Convergence Analysis

The proposed algorithm 1 can find a local optimal solution. Before proving the convergence, we first introduce the following lemma [Marsden et al., 1993].

Lemma 1: For any positive real number w and q, the following inequality holds:

Theorem 2: In Algorithm 1, updated S will decrease the objective value of problem (1) until converge.

Proof: Suppose the updated S is ̂S in each iteration, so ̂S makes the objective of Eq. (5) have the smaller value than S. Combining Eq. (4), we have

According to Lemma 1, we have

after a simple algebra, the Eq. (15) becomes:

According to Eq. (14) and Eq. (16), we have:

5 Learning An Initial Graph

In the algorithm 1, before learning the normalized and blockdiagonal similarity matrix S ∈ Rn×n . an initial graph affinity matrix A is required to be given. In this section, similar with [Nie et al., 2016], we give an approach to initialize graph A. We want to learn a normalized and nonnegative similarity matrix S, so it is desirable for the initial graph A to have the same constraint.

Given the data points {x1, x2, · · · , xn}, we want to learn the affinity values of A such that smaller distance ‖xi - xj‖22 between data points xi and xj corresponds to a larger affinity value aij . Then we solve the following problem:

where zij = ‖xi -xj‖22 , furthermore, in many cases, we want to get a sparse affinity matrix A for higher performance. Therefore, we learn the affinities with the maximal u such that the optimal solution ai to the question (18) has exactly m nonzero values; i.e., the L0-norm of ai is constrained to be m. To this end, we solve the following problem:

where ⌢ai is the optimal solution to the Eq. (18).

After a simple algebra, Eq. (18) becomes:

The Lagrangian function of Eq. (20) is:

where δ and ηi are the Lagrange multipliers.

The optimal solution ⌢a should satisfy that the derivative of Eq. (21) w.r.t. ai is equal to zero, so we have

Noting that aijηij = 0 and according to the KKT condition, we have

According to the constraint ∥∥∥⌢ai∥∥∥0 = m in Eq. (19), we know ⌢aim > 0 and ⌢ai,m+1 > 0. Therefore, we have

According to Eq. (23) and the constraint in Eq. (18), we have

According to Eq. (24) and Eq. (25), we can get the following inequality:

Therefore, to obtain the optimal solution ⌢ai to the Eq. (18) that has exactly m nonzero values, the maximal is

According to Eqs. (23), (25) and (27), we have the optimal affinities ⌢aij as follows:

The affinities ⌢aij computed by Eq. (28) have the following advantages [Nie et al., 2016]:

(1). Eq. (28) only involves the basic operations (i.e. addition, subtraction, multiplication and division). Some methods often can be used to compute the affinities such as LLE [Roweis and Saul, 2000] and sparse coding [Wright et al., 2009], but the computations of Gaussian functions and other more operations that make these methods less efficient than our method.

• (2). The learned Initial matrix ⌢A is naturally sparse, which is computationally efficient for graph-based learning tasks such as clustering.
• (3). The property that the affinities are distance consistent is guaranteed from the motivation of this method. If the distance between samples xi andxj is smaller than the distance between xi and xk, then the affinity ⌢aij computed by Eq. (28) is larger than the affinity ⌢aik. However, this property is not guaranteed in LLE and sparse coding.
• (4). Computing the affinities by Eq. (28) only involves one parameter i.e., the number of neighbors m. This parameter is easy to tune. In general, m < 10 can produce good results. This property is important because the tuning of parameters remains a open and difficult problem in clustering task. In graph-based clustering task, there are few labeled samples and thus traditional parameter tuning techniques such as cross validation will not be used.

6 Experiments

In this section, we will validate our proposed method on four benchmark datasets (Handwritten numerals, MSRC-v1, COIL20 and UMIST), and compare it with other clustering methods: spectral clustering (SC) [Ng et al., 2002], K-means clustering [MacQueen and others, 1967], Constrained Laplacian Rank (CLR) [Nie et al., 2016]. In our model, we determine the value of γ in a heuristic way to accelerate the procedure. At first, we set γ with a small positive value, then in each iteration, decrease it ( γ = γ/2 ) if the number of zero eigenvalues in Ls is larger than class number c or increase it ( γ = 2γ ) if smaller than c, otherwise the iteration stopped.

6.1 Datasets Descriptions

COIL20 databast [Nene et al., 1996] includes 1440 color images of 20 objects (72 images per object). The object has a wide variety of complex geometric and reflectance characteristics. This database, called Columbia Object Image Library (COIL-20), was used in a real-time 20 object recognition system. Each object was placed in a stable configuration at approximately the center of the turntable. The turntable was then rotated through 360 degrees and 72 images were taken per object; one at every 5 degrees of rotation.

UMIST dataset [Graham and Allinson, 1998] consists of 564 images of 20 individuals (mixed race/gender/appearance). Each individual is shown in a range of poses from profile to frontal views and images are numbered consecutively as they were taken. The files are all in PGM format, approximately 220×220 pixels with 256-bit grey-scale.

Handwritten numerals (HW) dataset [Asuncion and Newman, 2007] is composed of 2,000 data points for 0 to 9 ten digit classes and each class has 200 data points. Five published features can be used for clustering: View1: 76 Fourier coefficients of the character shapes (FOU), View2: 216 profile correlations (FAC), View3: 240 pixel averages in 2×3 windows (PIX), View4: 47 Zernike moment (ZER) and View5: 6 morphological (MOR) features.

MSRC-v1 dataset [Winn and Jojic, 2005] contains 240 images and can be divided into 8 classes. Following [Lee and Grauman, 2009], we select 7 classes composed of tree, building, airplane, cow, face, car, bicycle and each class has 30 images. To distinguish all of scenes, we extract four visual features from each image: View1: 24 Color Moment, View2: 576 Histogram of Oriented Gradient, View3: 256 Local Binary Pattern and View4: 254 Centrist features.

6.2 Evaluation Criteria

In experiments, we evaluate the clustering performance with two standard clustering evaluation metrics, i.e. Accuracy (ACC) [Cai et al., 2005] and Normalized Mutual Information (NMI) [Est´evez et al., 2009].

Given an input data matrix X = [x1, x2, · · · xn] ∈ Rd×n composed of n feature vectors of d dimensions as its columns, r = [r1, r2, · · · rn] ∈ Rn and ˜r = [˜ r1, ˜ r2, · · · ˜ rn] ∈ Rn denote the truth class label vector and predict class label vector, respectively. ri, and ˜ ri are the truth label and predict label of xi.

Accuracy (ACC): ACC measures one-to-one relationship between predict class and the true classes:

where map(ri) is a permutation mapping function that maps each cluster label ri to the equivalent label from the dataset. δ(x, y) is the delta function defined as:

Normalized Mutual Information (NMI): NMI measures the similarity between the clustering results and the true classes:

where Mutual Information MI(r,˜r) and entropy H(r) are respectively calculated as follows:

where p(ri) is the probabilities that the arbitrary image belongs to the cluster ri, and p(ri, ˜ rj) is the joint probability that the image belongs to the both the clusters ri and cluster ˜ rj .

6.3 Experimental Results Analysis

For each dataset, we repeat experiments 10 times because all the methods are spectral clustering based methods. Spectral clustering has k-means procedure, however, the performance of it has large relationship with the choice of initial centroids. Finally, we report the average performance including ACC and NMI. Table 1 and Table 2 show the results on HW dataset and MSRC-v1 dataset, respectively. Table 3 shows the results on COIL20 dataset and UMIST dataset. Figure 1 shows the converge curve of our method on four datasets. Comparing the aforementioned experimental results, we have several interesting observations as follows:

(1) From Table 1 and Table 2 we conclude that our proposed methods outperform the competing methods on each view, which means our model is robust to different visual features on clustering task. The results of Table 3 also shows our model obtains the best performance on COIL20 dataset and UMIST dataset. Moreover, our model is very robust to the parameter γ, it nearly can be seen parameter-free approach. By contrast, the parameter-free method CLR is robust to some extent, but the performance is not satisfactory.

(2) In order to show the convergence effect on the same graph, we choose the log value of the objective function as the ordinate. Figure 1 shows the log value of function converges within only three steps. This is consistent with our analysis in Section 3. It illustrates that our algorithm has a good practical application for its good convergence.

7 Conclusions

In this paper, a novel graph-based clustering model is proposed to learn a new graph with exactly c connected components (where c is the number of clusters). Instead of fixing the original data graph associated to the affinity matrix, the proposed model tries to learn a new block diagonal data similarity matrix such that the clustering results can be immediately obtained without requiring any post-processing to extract the clustering indicators. An optimization algorithm is also given to solve our model. Empirical results on some real benchmark datasets showed our method is significantly better than several well-established clustering approaches.

Acknowledgements

This work is supported by National Natural Science Foundation of China under Grant 61773302 and the 111 Project of China (B08038).