A Unified Framework for Discrete Spectral Clustering

1 Introduction

Clustering [Jain et al., 1999; Rodriguez and Laio, 2014; B¨uhler and Hein, 2009; Belkin et al., 2016] has long been serving as a critical technique in modern research fields, such as image segmentation [Shi and Malik, 2000; Felzenszwalb and Huttenlocher, 2004], gene expression analysis [Jiang et al., 2004], face analysis [Elhamifar and Vidal, 2013], contentbased image retrieval [Gordon et al., 2003], image annotation [Wang et al., 2008], heterogeneous data analysis [Liu et al., 2015] and image hashing [Shen et al., 2015].

As one of the most classic clustering approaches, k-means has been extensively applied in practice. The typical procedure of k-means iteratively assigns data points to their closest clusters and updates clustering centers. Nonetheless, kmeans suffers from the problem of "curse of dimensionality" [Ding and Li, 2007]. Recent research endeavors focus on finding a low-dimensional projection using dimensionality reduction techniques (e.g., PCA) and then performing k-means. Furthermore, several works have tried to employ discriminative analysis [De la Torre and Kanade, 2006; Ye et al., 2007a; Yang et al., 2011] to generate better partition of data. In [De la Torre and Kanade, 2006; Ding and Li, 2007], k-means and LDA were integrated together to discover discriminative subspace. In [Ye et al., 2007b], Ye et al. proposed a discriminative k-means (DKM) algorithm to formalize clustering as a trace maximization problem for learning better clustering labels.

As an alternative promising direction, spectral clustering [Filippone et al., 2008] has demonstrated its strong capability in group objects by analyzing complex data structural information. Spectral clustering has been extensively used in real-world applications, such as image/video segmentation [Galasso et al., 2014]. The advantage of spectral clustering family lies in the exploration of the intrinsic data structures [Xia et al., 2014; Yang et al., 2013; 2015], which are fully employed for predicting clustering labels by exploiting the different similarity graphs of data points. For instance, in [Wu and Scholkopf, 2007], an effective algorithm, termed as local learning based clustering (LLC), was developed according to the assumption that the cluster label of a data point can be determined by its neighbors.

It is well-known that optimizing the spectral clustering models will lead to an NP-hard problem due to the discrete constraint on the clustering labels. To achieve a feasible approximate solution, most spectral clustering algorithms follow a common practical paradigm. It first relaxes the discrete constraint to allow the clustering label matrix to be continuous-valued and performs eigenvalue decomposition on the specific Laplacian matrix to generate an approximate indicator with continuous values. Then, we can discretize the clustering label matrix by employing certain independent technique, such as k-means. Furthermore, to enable clustering new unseen data, one may learn an additional prediction function in an independent stage (module). In [Yang et al., 2013; Nie et al., 2011], the out-of-sample problem is addressed by introducing a regression learning module, and discriminative information is injected into the construction of the similarity matrix to improve clustering performance. Although existing spectral clustering has been applied in practice widely, they may easily achieve poor performance due to the following drawbacks:

• ÷ High risk of severe deviation of approximate solution

from the genuine discrete clustering labels;

• ÷ Information loss among separate independent stages, i.e., continuous label generation, label discretization and prediction function learning;
• ÷ Unreliability of the predicted cluster labels leading to poor prediction functions.

To cope with the aforementioned problems, we propose a spectral clustering scheme which directly learns discrete clustering labels and robust out-of-sample prediction functions in a unified manner. Specifically, in order to alleviate the influence caused by the information loss during the relaxation of traditional spectral clustering, we deliberately recover the abandoned discrete constraint with a smooth transformation (e.g., rotation) from the relaxed continuous clustering labels to a discrete solution. In this sense, the continuous clustering label just serves as an intermediate product. We integrate a discrete rotation functionality, which guarantees a tractable optimization problem with a discrete solution. Moreover, to further compensate the unreliability of the learned labels, we integrate an adaptive robust module to learn prediction function for unseen data. In particular, we devise a novel noise modelling approach by utilizing an effective `2↪p loss term over the prediction error residual to capture unreliability of clustering labels in a more adaptive way. The `2↪p loss is capable of inducing sample-wise sparsity, which naturally identifies unreliable predicted labels. Besides, different choices of p enables sufficient control on unpredictable conditions of label noise.

The rest of this paper is organized as follows. Section 2 elaborates the details of the proposed model, including problem formulation, introduction of model, an efficient algorithm and the corresponding analysis. Experimental results are reported and analyzed in Section 3. In the last, we conclude our work in Section 4.

2 The ProposedMethod

In this section, we elaborate the proposed discrete spectral clustering. We first present the formulation and then develop an efficient algorithm for optimization.

2.1 ProblemFormulation

Given n data points of d dimensions, denoted as X = [x1↪ x2↪ ▷ ▷ ▷ ↪ xn] 2 Rd⇥n , we aim to partition X into c groups ¶Cj♦cj=1 according to certain criteria. For instance, data in the same cluster should be similar to each other while those in different groups should have dissimilar representations. The family of spectral clustering algorithms is generally formulated as below:min

where Tr(·) computes the trace of a matrix and L 2 Rn⇥n is the Laplacian matrix of X. Y = [y1↪ y2↪ ▷ ▷ ▷ ↪ yn]T 2 Rn⇥c is the clustering label matrix, and Y 2 Idx means the clustering label vector of each sample yi 2 ¶0↪ 1♦c⇥1 contains one and only one element "1", which indicates the group membership of xi. It is recognized that the problem in Eq.(1) is NP-hard due to the discrete constraint on Y. A commonlyused practical way is to relax Y to be continuous-valued and thus we arrive at

where F 2 Rn⇥c is the relaxed continuous clustering label matrix. Ic is an identity matrix of size c ⇥ c. The orthogonal constraint FT F = Ic is used to avoid trivial solution. After solving the above problem via eigenvalue decomposition, we further use traditional clustering method, e.g., k-means, to transform clustering labels into discrete ones.

Though the two-stage strategy provides a feasible solution, it may unpredictably deviate from the genuine discrete clustering labels. To avoid this situation, we intend to devise a unified spectral clustering model to directly generate the discrete clustering label matrix.

2.2 Model

To bypass the difficulty of the NP-hard problem in Eq.(1), we propose to re-introduce the "new" discrete clustering indicator Y into Eq.(2). We expect Y has exactly the same properties as that in Eq.(1). Meanwhile, Y should also be certain reasonable transformation from F in order to preserve the structural knowledge derived from data. Based on such analysis, we employ the following model to achieve these goals:

where Q 2 Rc⇥c is a rotation matrix which adjusts the continuous-valued clustering label matrix into the real discrete clustering label matrix Y. ↵ is a trade-off parameter.

Recall that existing clustering methods can hardly generalize to new unseen data. Possible solutions either learn new prediction functions independently from scratch [Bengio et al., 2004] or incorporate learning model into clustering to generate prediction functions [Nie et al., 2011; Yang et al., 2013]. Denote prediction function learning component as L(W;X↪Y). One may choose the following loss

where W 2 Rd⇥c is the mapping variable.

However, integrating the above model into the discrete optimization framework as in Eq.(3) suffers from the following problem. The noise in Y can hardly be captured by Eq.(4). For example, if the clustering label of a training sample is incorrectly generated in previous process, then the error will be inevitably amplified due to the squared residual. The unreliability of the learned cluster labels probably in turn jeopardizes the subsequent learning of prediction functions. To handle the above problem, we propose to utilize a robust `2↪p loss term [Yang et al., 2014] to effectively control different levels of noise. Also, we also design a mutually reinforcing mechanism to explicitly make generation of clustering label codes and training of prediction functions interacted with each other, thereby exerting positive influence to the whole learning process. The robust learning model is depicted as follows:

where the loss function is changed to `2↪p (0 < p < 2) loss, which is capable of alleviating sample noise:

where (M)i is the i-th row of matrixM. The above `2↪p loss not only suppresses the inevitable noise but also enhances the flexibility for adapting different noise levels.

By substituting the robust learning module in Eq.(4) into Eq.(3), we have

where ↵ > 0 and β > 0 are balance parameters.

2.3 Solution

Due to the existence of `2↪p loss, direct optimizing the model (7) turns out to be difficult. In this part, we propose an efficient and effective algorithm which iteratively solves an alternative optimization problem and guarantees the obtained solution is the optimal solution to the original problem in (7). Denote the loss residual as

then we introduce the alternative problem as follows:

where D is a diagonal matrix with its i-th diagonal element computed as

where ri is the i-th row of R.

We show how to solve the above alternative problem first, and then explain the obtained solution is the optima of Eq.(7).

Update F: With Q↪W↪ Y fixed, the problem is reduced to

The above problem with orthogonal constraint can be effi-

ciently solved using the algorithm [Wen and Yin, 2013].

Update Y: When F↪ Q↪ W are fixed, we have

Given the facts that Tr(YT Y) = n and Tr(YT DY) = Tr(D), we can rewrite the above sub-problem as below:

Algorithm 1 Algorithm for optimizing the proposed spectral clustering model.

Input: Training data X; Output: F↪Q↪W↪Y;

• 1: Randomly initialize F↪Q↪W↪Y;
• 2: Construct Laplacian matrix L;
• 3: repeat
• 4: Update D according to Eq.(10);
• 5: Update F by solving the problem in Eq.(11);
• 6: Update Y according to Eq.(14);
• 7: Update Q by solving the problem in Eq.(15);
• 8: UpdateWaccording to Eq.(17);
• 9: until there is no change to F↪Q↪W↪Y
• 10: return F↪Q↪W↪Y

where P = ↵FQ+ βDXT W. The optimal solution of the above sub-problem can be easily generated as follows:

Update Q: When F↪W↪ Y are fixed, the problem becomes

which can be efficiently solved using the algorithm [Wen and Yin, 2013].

Update W: Fixing F↪ Q↪ Y, we arrive at

Setting the derivative of Eq.(16) w.r.t. W to zero, we have

where Id is an identity matrix of size d ⇥ d.

We summarize the optimization process of Eq.(7) in Algorithm 1. We will show that Algorithm 1 converges to an optima of the original problem in Eq.(7).

We first introduce two lemmas.

Lemma 1. Let ri be the i-th row of the residual R in previous iteration, and ˜ri be the i-th row of the residual ˜R in current iteration, then the following inequality holds:

Proof. Given the following unary function

We have h0 (x) = 2px - 2pxp-1 and h00 (x) = 2p - 2p(p - 1)xp-2 . Clearly, h0 (x) = 0 only when x equals to 1. Besides, when x 2 (0↪ 1), h0 (x) < 0 and when x > 1, h0 (x) > 0, which indicates that h(x) is monotonically decreasing as 0 < x < 1 and monotonically increasing when x > 1. Furthermore, we know h00 (1) = 2p(2 - p) > 0. Hence, we have the conclusion that for 8x > 0, h(x) ≥ h(1) = 0.

Then, by substituting x= k˜rik krik into Eq.(19), we obtain the conclusion

Lemma 2. Given R = [r1↪ r2 ▷ ▷ ▷ ↪ rn]T , then we have the following conclusion:

Proof. By summing up the inequalities of all ri↪ i = 1↪ 2↪ ▷ ▷ ▷ ↪ n according to Lemma 1, we can easily reach the conclusion of Lemma 2.

Theorem 1. Each iteration (line 4 to line 8) of Algorithm 1 decreases the value of the objective function in Eq.(7) monotonically.

Proof. Suppose ˜Y↪ ˜F↪ ˜Q↪ ˜W are the optimized solution of the alternative problem (9), and we denote

then we have

Using Lemma 2, we have

which indicates the monotonic decreasing trend of the objective function in Eq. (7) in each iteration.

To sum up, we can see that Algorithm 1 will eventually converge to the optima of the original problem in Eq. (7) according to Theorem 1.

3 Experiments

3.1 Experimental Settings

In the experiments, we evaluate our proposed approach on six UCI datasets [Lichman, 2013], including Image Segmentation, Vehicle, Vote, Ecoli, Solar and Wine. The statistics of datasets are summarized in Table 1.

We choose several existing clustering approaches for comparison, including k-means clustering (KM), discriminative k-means clustering (DKM) [Ye et al., 2007b], Spectral Clustering (SC), Local Learning Clustering (LLC) [Wu and Scholkopf, 2007], CLGR [Wang et al., 2009] and Spectral Embedding Clustering (SEC) [Nie et al., 2011]. We set the number of neighbors k to 5 for all spectral clustering methods. The parameters of all comparison algorithms are tested in ¶10-6 ↪ 10-4 ↪ 10-2 ↪ 100 ↪ 102 ↪ 104 ↪ 106 ♦. We set p of `2↪p loss in ¶0▷25↪ 0▷5↪ 0▷75↪ 1↪ 1▷25↪ 1▷5↪ 1▷75♦. We randomly choose 50% of samples for training and the rest are used for test.

We employ conventional Normalized Mutual Information (NMI) and Accuracy (ACC) as evaluation metrics.

• ÷ NMI: We first define normalized mutual information of two distributions A and B as below:

where I(A↪ B) computes the mutual information of A and B. H(·) is the entropy of a distribution. Denote ni as the number of datums in the i-th cluster Ci generated by a clustering algorithm, ˆnj as the number of data points in the j-th ground truth class Gj and ni↪j as the number of data occurring in both Ci and Gj. Then, NMI is calculated as follows:

• ÷ ACC: Denote oi as the resultant clustering label of xi using certain clustering method and gi as the ground truth of xi, then we have

where δ(x↪ y) = 1 if x = y; δ(x↪ y) = 0 otherwise, and map(gi) is the best mapping function that permutes clustering labels to match the ground truth labels. Larger ACC values indicate better clustering performance.

Table 2: Comparison of our proposed approach and existing methods on six evaluated datasets. (a) ACC on Training set; (b) NMI on Training set; (c) ACC on Test set; and (d) NMI on Test set.

(a) ACC on Training set.

(b) NMI on Training set.

(c) ACC on Test set.

(d) NMI on Test set.

3.2 Comparison

We compare our proposed discrete spectral clustering to several existing methods. Table 2 reports ACC and NMI performance on training and test sets of six evaluated datasets, from which we derive the following observation and analysis.

As we can see, our proposed approach significantly outperforms other comparison methods, including traditional clustering (KM and DKM), spectral clustering (SC, LL and CLGR) and clustering with out-of-sample extension (SEC). On the one hand, our solution is capable of searching "genuine" clustering membership of data, i.e., discrete labels, which helps to reach the optimal clustering without any extra discretizing manipulation, thereby leading to minimal loss.

On the other hand, the optimization of the prediction function learning module helps to control the unreliable factors in the derived clustering labels, which in turn exerts positive influence on the learning of the discrete spectral clustering to further boost the quality of the resultant clustering labels.

In order to further illustrate the efficacy of the discrete clustering, we compare clustering performance of discrete label matrix Y, original continuous label matrix F with spectral rotation [Huang et al., 2013] and the rotated continuous label matrix FQ with maximum value binarization. The ACC and NMI performance is reported in Figure 1. As we can see, the discrete clustering label matrix Y always achieves the best performance, and FQ performs slightly better than F. This phenomenon again implies that our discrete solution is closer to the real partition of data than the relaxed continuous clustering labels.

3.3 Parameter Sensitivity

We further study how our approach performs when using different settings of parameters. As stated before, we tune trade-off parameter ↵, β and γ in the range of ¶10-6 ↪ 10-4 ↪ 10-2 ↪ 100 ↪ 102 ↪ 104 ↪ 106 ♦, and p from 0▷25 to 1▷75. Figure 2 illustrates the experimental results.

• ÷ Joint effects of ↵ and β. ↵ and β controls the contributions of continuous label generation, label rotation and prediction learning. When ↵ and β are neither too large nor too small (e.g., ↵ = 1 and β = 0▷01), our approach can achieve satisfactory performance. This hints us that different components should be well balanced in order to maximize the joint effects.
• ÷ Effects of γ. γ controls the inner balance of prediction residual error kY-XT Wk2↪p and regularizer kWk2F . As γ increases from 10-6 to 10-2 , our approach performs gradually better. When γ keeps going up, we see a decreasing trend instead. If γ is small, the regularizer will be easily ignored, which may lead to overfitting problem. In contrary, when we use large γ, the prediction residual error will not be well controlled, which makes our approach to produce poor prediction functions and clustering labels.
• ÷ Effects of p. The performance of our approach fluctuates (from 0▷5 to 0▷9) when p varies from 0▷25 to 1▷75. For both training and test settings, the best performance is gained when p is not close to 2, which indeed reflects

the ability of `2↪p loss handling unreliable clustering labels.

3.4 Convergence Study

As aforementioned, we have shown that Algorithm 1 is guaranteed to converge to an optima when we iteratively solve the alternative problem (9). In this part, we empirically test the convergence and the efficiency of the proposed algorithm. As illustrated in Figure 3, we conduct experiments on six evaluated datasets. For illustration purpose, we consistently fix the values of all parameters to 1. As we can see, our algorithm is able to achieve a very rapid convergence within only a few iterations (less than 10). In this sense, it is reasonable for us to set the number of iterations to 10, which provides sufficient efficiency for the learning.

4 Conclusion

In this work, we coped with the problem existing in most traditional spectral clustering algorithms, i.e., relaxing discrete constraints to continuous one, which consists of two independent stages (i.e., first learning continuous labels and then rounding the learned labels into discrete ones). In order to reduce information loss and performance degradation, we proposed a unified spectral clustering approach to directly learn discrete clustering labels and robust out-of-sample prediction functions. To be more specific, our proposed approach can explicitly rotate continuous labels to discrete ones. Meanwhile, to the end of handling the noisy clustering labels, we integrated an adaptive robust module to learn prediction function for unseen data. Extensive experiments on six data sets demonstrated the promising performance of our proposal as compared to existing clustering approaches.

Acknowledgments

This work was supported in part by the National Natural Science Foundation of China under Project 61502081 and Project 61572108, and the Fundamental Research Funds for the Central Universities under Project ZYGX2014Z007.