Local and Structural Consistency for Multi-Manifold Clustering

1 Introduction

Data sets containing low-dimensional multi-manifold structures are ubiquitous in real-world tasks, and effective grouping of such data is an important yet challenging problem, which is referred as manifold clustering [Souvenir and Pless, 2005; Wang et al., 2010]. Many important problems of practical interest can be properly formalized under this framework. For instance, motion segmentation problem in computer vision, the point correspondences in a dynamic scene generally contain several moving objects each can be represented as a manifold; In classification of face images, the faces of the same person lie on the same manifold while different persons are associated with different manifolds.

Traditional clustering algorithms (e.g., K-means) have difficulty in effectively grouping multi-manifold data, which has attracted numerous researchers to study on manifold clustering during the last decade. Whereafter, several algorithms have been proposed, which can be roughly classified into two categories, i.e., linear and nonlinear. However, all linear algorithms fail to deliver good performance in the presence of nonlinear structures due to their linear nature. Thus, more attention should be paid to nonlinear manifold clustering, since a large number of recent research efforts have shown that the distributions of many natural data are inherently nonlinear [Saul and Roweis, 2004]. Existing nonlinear algorithms focus on dealing with well-separated manifolds or intersecting manifolds. However, a more accurate and general description of the real-life data is that samples are supported on a mixture of hybrid manifolds. That is, the manifolds on which the data points lie are (a) linear and/or nonlinear and (b) intersecting and/or not intersecting, which is referred as hybrid nonlinear manifold clustering [Wang et al., 2010]. Existing algorithms either could not effectively deal with such situation, or are quite heuristic. Therefore, an open and challenging problem in manifold clustering is how to design more principled methods for the grouping of multiple hybrid manifolds.

∗This research was partially supported by NSFC (60975038, 61005003, 61073097) and 973 Program (2010CB327903)

Inspired by the practical successes and rapidly developing theoretical underpinnings of spectral clustering algorithms, in this paper, we try to design a new spectral-based algorithm to the task of detecting multiple low-dimensional manifolds embedded in high-dimensional point clouds. Firstly, we study the potential of spectral methods for hybrid nonlinear manifold clustering and our analysis reveals that they have the potential only when the neighborhood graph is constructed to connect the neighboring samples from the same manifold. However, traditional spectral clustering algorithms [Shi and Malik, 2000; Ng et al., 2001], which identify neighbors according to Euclidean distance, are not suitable since samples belonging to different manifolds may be close to each other, especially near the intersection of different manifolds. To handle this drawback, our basic idea is to take advantage of additional structural information to identify the neighbors of each point from the same manifold rather than the entire Euclidean space. In doing that, we propose local and structural consistency criterion, which considers the neighboring information as well as the structural information implied by the samples. Based on this new criterion, we develop a simple yet effective spectral-based algorithm, named Local and Structural Consistency (LSC), for the task of detection of multiple hybrid manifolds. Experimental results on both synthetic and real-world data show its superior performance over existing manifold clustering algorithms.

The novelty of this work lies in: 1) the proposal of combining local consistency with structural consistency to address the fundamental problem of neighborhood selection for manifold clustering; 2) the method for constructing the local tangent space when there are intersecting clusters. To the best of our knowledge, we propose the first solutions to these two challenging problems.

The rest of this paper is organized as follows. Section 2 gives a brief review of the related works. Section 3 studies the potential of spectral methods for hybrid nonlinear manifold clustering and presents the LSC algorithm. Section 4 reports experiments on both synthetic and real-world data. Finally, we conclude in Section 5.

2 RelatedWork

Unlike classical clustering algorithms which are based on the concept that a cluster is centered around a single point, manifold clustering algorithms regard a cluster as a group of points compact around a low-dimensional manifold [Souvenir and Pless, 2005; Wang et al., 2010].

When only a mixture of linear or affine subspaces are used to represent the clusters, the corresponding problem, i.e., linear manifold clustering, is much easier to address since there are elegant representations for linear manifolds. Several linear manifold clustering algorithms have been proposed in the past decade and successfully applied to many real-life situations. Generalized Principal Component Analysis (GPCA) [Vidal et al., 2005] and K-planes [Tseng, 2000] learn a series of offset vectors and basis vectors from the data to represent the linear manifolds and then assign each point to the nearest linear manifold. Local Subspace Affinity (LSA) [Yan and Pollefeys, 2006] constructs an affinity matrix for any pair of points based on principal subspace angles of the local estimated tangent spaces to group the data. Spectral Curvature Clustering (SCC) [Chen and Lerman, 2009] addresses linear manifold clustering by building a polar curvature affinity matrix among certain fixed-size subset of the points to measure their possibilities of coming from the same manifold, and then uses multi-way spectral methods to group the samples.

Unlike its simple linear counterpart, nonlinear manifold clustering is more complex and difficult. The research on this topic is divided into three branches: intersecting, separated and hybrid. K-manifolds [Souvenir and Pless, 2005] which begins by estimating geodesic distances between pairwise points and then employs a EM-like algorithm to cluster samples in terms of geodesic distances, is primarily motivated for dealing with unorganized data nearly lying on multiple intersecting low-dimensional manifolds. When the observations are lying on or close to multiple well-separated manifolds, traditional spectral clustering algorithms [Shi and Malik, 2000; Ng et al., 2001] can be directly used to group the data and several studies have shown their promising results. MumCluster [Wang et al., 2010] is proposed to effectively deal with the general hybrid nonlinear manifold clustering problem where some data manifolds are separated but some are intersected. However, it is quite heuristic and heavily relies on the correct local dimension estimation. Up to now, it is not clear on how to design principled methods for the grouping of multiple hybrid manifolds, which is the main focus of this paper.

3 The Proposed Approach

The main focus of this section is to study the potential of spectral methods for hybrid nonlinear manifold clustering and then to design a new spectral-based algorithm to the task of detecting multiple low-dimensional manifolds.

3.1 Preliminaries

Suppose that we are given a set of unorganized data points X = {xi ∈ ℜD , i = 1, · · · ,N}, which are sampled from K > 1 distinct smooth manifolds {Ωj ⊆ ℜD , j = 1, 2, · · · ,K} where each manifold has Nj points (∑Kj=1 Nj = N). Moreover, some data manifolds are separated but some are intersected [Wang et al., 2010]. The objective of manifold clustering is to assign each sample to the manifold it belongs to. For simplicity, we restrict the discussion to the case where all the underlying manifolds have the same dimension d (0 < d < D), which, together with their number K, is known.

To reveal the potential of spectral methods for hybrid nonlinear manifold clustering, we first review below the main steps of Symmetrical Normalized Spectral Clustering with Lnearest neighbor graph and Simple weight (SNSC-LS) [Ng et al., 2001], which is the basis of our proposed approach: Step 1. Constructing neighborhood graph G Put an edge between xi and xj if xi is among the L-nearest neighbors of xj according to Euclidean distance, and vice versa. the top K eigenvectors of D-1/2WD-1/2 , where the degree

Step 2. Determining affinity matrix W If xi and xj are connected by G, then wij = 1; otherwise, wij = 0. Step 3. Spectral decomposition Extract U = [u1, · · · , uK], matrix D = diag{W ∗ 1}. Then, re-normalize each row of U to have unit length, obtaining matrix V .

Step 4. Clustering byK-means ApplyK-means to the rows of V (i.e., embedded data) to find K clusters. Finally, original data points are grouped into K clusters.

3.2 Potential

Recall that the performance of clustering depends on the adopted algorithm as well as the data. When the clustering algorithm is fixed, the performance mainly relies on the data. Unlike traditional clustering where clustering algorithm (e.g., K-means) is directly performed on the data, the grouping procedure of spectral clustering is performed on the embedded data. While the embedded data are obtained by performing spectral analysis on the affinity matrix of the neighborhood graph which in turn is determined by the L-nearest neighbors of each point. This fact reveals that the performance of spectral clustering is essentially relied on how to identify neighbors. In fact, we have the following Proposition.

Proposition 1 If the L-nearest neighbors of each point are from the same manifold and L is large enough to ensure that the points from the same manifold are connected, then spectral clustering gives the perfect underlying manifolds.

Proof. Without loss of generality, we assume that a permutation of indices of the data have been done such that all the points in the k-th manifold appear before the (k + 1)-th manifold, k = 1, · · · ,K - 1. Since the neighbors of each point are from the same manifold, pair-wise points xi and xj belonging to different manifolds could not be L-nearest neighbors of each other, hence their affinity value wij = 0. Then, the affinity matrix W is block-diagonal with K blocks, each block corresponding to one of the manifolds. It is easy to show that D-1/2WD-1/2 is also block-diagonal which has the largest eigenvalue 1 of multiplicity K under the restriction that each manifold is connected. Moreover, the top K eigenvectors associated with eigenvalue 1 can be described as:

where 1Nk denotes the Nk-dimensional vector of ones and R = (r1, r2, · · · , rK) ∈ ℜK×K is an orthonormal matrix. As a direct consequence of the row normalization of U, for all k = 1, · · · , K and l = 1, · · · , Nk, V 's rows satisfy

In other words, the K clusters are mapped to K mutually orthonormal points in ℜK . Then, the followed K-means will give grouping result corresponds exactly to the "true" clustering of the original manifolds. #

For the general case where not all the L-neighbors are from the same manifold, we have the following Theorem:

Theorem 1 [Arias-Castro, 2009] For k = 1, · · · ,K, let Ik denotes the index set of the k-th cluster and Wk denotes the submatrix of W corresponding to Ik. Define ˆDk i = ∑j∈Ik wij and ˜Dk i = ∑j/∈Ik wij as within-cluster connection and between-cluster connection of i ∈ Ik, respectively. Then, under the following conditions, there are K orthonormal vectors r1, r2, · · · , rK such that V 's rows satisfy

(A1) There exists δ > 0 such that, for all k = 1, · · · ,K, the second largest eigenvalue of Wk is bounded above by 1 - δ. (A2) There is some fixed ε1 > 0, so that for all k, l ∈ {1, · · · , K} with k ̸= l, ∑i∈Ik ∑j∈Il w2 ij / ˆDk i ˆDlj ≤ ε1.

(A4) There is some constant C > 0, so that for all k = 1, · · · ,K and i, j ∈ Ik, ˆDk i ≪C ˆDk j .

From the viewpoint of neighbors, Theorem 1 suggests that when each point has more neighbors (or a higher connection) with its own group than with the others, then the embedded data (i.e., the rows of V ) will form tight clusters around K well-separated points. Obviously, the followedK-means performed on the embedded data will easily give grouping result corresponds to the "true" clustering of the original manifolds.

Proposition 1 and Theorem 1 reveal the potential of spectral methods for hybrid nonlinear manifold clustering, i.e., we should try our best to identify the neighboring samples of each point from the same manifold. Moreover, they also make clear the invalidation of traditional spectral clustering algorithms to multiple intersecting or even hybrid manifolds. Traditional algorithms identify neighbors according to Euclidean distance, thus samples belonging to different manifolds will easily be connected by the neighborhood graph (especially those near the intersection of different manifolds), thus diffusing information across the wrong manifolds.

Therefore, in order to extend spectral-based algorithms to the task of detection of multiple hybrid manifolds, new and effective criteria to identify neighbors are specially desired.

3.3 Local and Structural Consistency

Our analysis in the previous subsection reveals that the key to extend spectral-based algorithms to the task of detection of multiple hybrid manifolds is trying to identify the neighbors of each point from the same manifold rather than the entire Euclidean space. To this end, our basic idea is to take advantage of the nature of manifolds to incorporate some geometric information encoded in the sampled data to identify the neighbors and then to find the correct clusters.

The type of geometric information incorporated in our proposed approach is local tangent space, based on the following observations: (a). Though the samples are from globally highly nonlinear distribution, locally, each data point and its neighbors are lying on a linear patch of the manifold [Saul and Roweis, 2004]. (b). Local tangent space at each point provides a reasonable approximation to the local geometric structure of the nonlinear manifold [Zhang and Zha, 2005]. (c). Near the intersection of different manifolds, the points from the same manifold have similar local tangent spaces (i.e., they are structural consistency) while the points belonging to different manifolds have dissimilar tangent spaces.

However, it should be noted that only structural consistency (i.e., neighbors have similar local tangent spaces) is not enough to be used to determine neighbors. One counterexample is that the points on the right-and-left corners of S-curve in Figure 2 (a) have similar local tangent spaces to the points on the vertical affine plane yet they are from different manifolds. This fact suggests that neighbors should not only be structural consistency, but also should be local consistency, that is they should be close to each other.

In doing that, we have a simple criterion (named as local and structural consistency criterion) to identify neighbors, which selects L neighbors of each point using the following measure of distance:

where Dis(xi, xj) is our measure of distance, ‖xi - xj‖2 is the Euclidean distance between xi and xj, and ‖Θi - Θj ‖F is the projection F-norm distance between the local tangent spaces of xi and xj (denoted as Θi and Θj, respectively). In (4), λ is a parameter which balances the contribution of local consistency and structural consistency.

After the L-nearest neighbors have been identified by our new measure of distance, the following procedures to group clusters are the same as traditional spectral clustering algorithms, thus our method to the task of detection of multiple hybrid manifolds is named as Local and Structural Consistency (abbreviated as LSC). The pseudo-code of LSC is shown in Figure 1.

3.4 Implementation

From (4) and Figure 1, we can see that the key to implement local and structural consistency criterion and the LSC algorithm are boiled down to effectively approximate the local tangent space at each sample, which will be discussed below.

Our basic idea to approximate the local tangent spaces is based on the following facts: (a). Globally nonlinear manifolds can locally be well-approximated by a series of local linear manifolds [Saul and Roweis, 2004]. (b). Probabilistic principal component analyzers [Tipping and Bishop, 1999] can successfully pass across the intersecting linear manifolds. (c). The points approximated by the same probabilistic analyzer usually have similar local tangent spaces which can be well-approximated by the principal subspace of the corresponding analyzer. Thus, we can train a set of probabilistic analyzers to approximate the nonlinear manifolds, and then determine the local tangent space of a given sample as the principal subspace of its corresponding analyzer.

Specifically, we train M mixtures of probabilistic principal component analyzers [Tipping and Bishop, 1999], each of which is characterized by the model parameters θm = {μm, Vm, σ2m}, m = 1, · · · , M, where μm ∈ ℜD is the mean vector, Vm ∈ ℜD×d and σ2m is a scalar. Under the m-th analyzer, observed data x is related to a corresponding latent variable y ∼ N(0, I) and noise εm ∼ N(0, σ2mI) as:

Then, the marginal distribution of x is given in the form

where Cm = σ2mI + VmV Tm . Moreover, the log-likelihood of observing the data set X for M analyzers is:

where πm ≥ 0 is the mixing proportion with ∑Mm=1 πm = 1.

We can learn all the model parameters μm, Vm, and σ2m by developing an iterative EM algorithm (initialized with Kmeans) to maximize (7). Due to page limitation, the principal steps of this EM learning procedure are omitted, more details can be found in [Tipping and Bishop, 1999].

Then, we group sample xi into the j-th probabilistic analyzer, which maximizes the posterior responsibility of xi:

where the posterior responsibility p(m|xi ) is given by

Finally, the local tangent space of xi is approximated by

The reconstruction error of using M probabilistic analyzers

Algorithm Local and Structural Consistency (LSC)

Input: Data set X, number of clusters K, dimension of the

manifolds d, number of mixture models M, number of neighbors L, balance parameter λ.

Steps: 1: Compute the local tangent space of each point.

2: Identify L-nearest neighbors of each point according to (4).

3-5: Same as steps 2-4 of the SNSC-LS algorithm.

Output: A partition of the data into K clusters.

Figure 1: Pseudo-code of the LSC algorithm

to approximate the underlying manifolds is:

where xjl , l = 1, · · · ,mj are the mj (∑Mj=1 mj = N) points which are grouped into the j-th probabilistic analyzer.

3.5 Complexity Analysis

Since the computational complexity of a clustering algorithm is much important to its applicability, let us briefly analyze the time complexity of the LSC algorithm.

The computational complexity of estimating the local tangent space of each point is O(NDM(t1 + dt2)), where t1 and t2 are the number of iterations before K-means and EM to convergence, respectively. Moreover, the complexity of computing the projection F-norm distances between any two local tangent spaces are O(M 2Dd2 ). Steps 2-5 of LSC have the same time complexity as SNSC-LS, which is O(N 3 + N 2D + NK2 t3) where t3 is the number of iterations before K-means to convergence in step 5. Therefore, the total time complexity of the LSC algorithm is

4 Experimental Results

In this section, we investigate the performance of LSC using a series of synthetic and real-world data sets. We also compare it with several state-of-the-art algorithms. All of our experiments are performed on a PC machine configured with Intel Dual Core based system with 4 ∗ 2.6 GHz CPU and 8GB RAM memory under Matlab platform.

4.1 Visual Comparison

We first visually compare LSC with SNSC-LS to the task of detection of multiple hybrid manifolds. The data points, as shown in Figure 2 (a), are sampled from three synthetically generated hybrid nonlinear manifolds: one S-curve, one two-dimensional affine plane, and one Swiss-roll in ℜ3 . The numbers of points are 1000, 500 and 1000, respectively. The connections among different points, as well as the grouping results of our LSC and SNSC-LS are shown in the last four sub-figures of Figure 2. Note that, to help the visualization of the connections, we have ordered the points so that all points belonging to the first manifold appear firstly and the points in the second manifold secondly.

As can be seen from Figure 2 (d) and (e), the performance of the proposed LSC which uses the new measure of distance (4) to select neighbors is surprisingly good: LSC identifies neighbors of each point generally from the same manifold and reliably finds clusters consistent with different manifolds. While SNSC-LS which selects neighbors according to Euclidean distance has many neighbors from different manifolds (Figure 2 (b)) and thus confuses points from the two intersecting manifolds though it can correctly partition the separated Swiss-roll (Figure 2 (c)).

These visual experiments validate our study of the potential of spectral methods for hybrid nonlinear manifold clustering and the effectiveness of the proposed LSC algorithm.

4.2 Parameter Influence

There are three adjustable parameters in LSC, i.e., M, L, and λ. In this subsection, we examine their influence to the performance of LSC and then try to give some default values to their setting. The results performed on the hybrid nonlinear manifolds of Figure 2 (a) over 10 independent trials are plotted in Figure 3. Note that, we set λ = ˆλ ∗ mLnn(X), where mLnn(X) is the mean squared Euclidean distance of all samples's L-th nearest neighbors in X and ˆλ is a scalar. This setting is based on two concerns: 1) to balance the magnitude between Euclidean distance and projection F-norm distance; 2) the most importantly, as revealed by our analysis, the key to the success of manifold clustering is to identify the neighbors of each point from the same manifold/cluster, and thus the added projection F-norm distance should ensure that the smallest "distance" between two inter-cluster points is larger than the "distance" between any point and its L-th intra-cluster nearest neighbors, which motivates us to bring mLnn(X) into the setting of λ.

As can be seen from Figure 3, LSC achieves significantly better results than traditional spectral clustering over a large range of parameter setting. In detail, we have the following observations: (a). LSC works well when the number of mixture models M is large enough (see Figure 3 (a)), which can be explained from Figure 3 (d): as the number of mixture models increasing, the average approximation error decreasing which means that the approximation to the local linear patches of the manifolds and the local tangent space of each sample become more faithful. Therefore, better clustering accuracy is given since LSC relies on the correct estimation of these tangent spaces. (b). The performance of LSC is robust for a range of values of L, as long as it is neither too small nor too large. This phenomenon is consistent with many existing observations [Saul and Roweis, 2004] since there may be many disconnected sub-clusters when L is too small, while local consistency will lose when it is too large. (c). LSC works well when ˆλ is relatively large but not too large. The reason is that the larger ˆλ, the more structural consistency is incorporated. However, local consistency becomes relatively small as ˆλ is too large. This fact confirms the validity of balancing between local consistency and structural consistency.

Finally, we can give some recommended values to the setup of these parameters which will be generally used to give the reported results. As a general recommendation we suggest to work with M = ⌈N/(7d)⌉, L = 2 ⌈log(N)⌉ and ˆλ = 1.2. We can work with a relative small M, e.g., M = 3K, when all the manifolds are linear.

4.3 Comparison on Benchmark Data Sets

In this subsection, we compare LSC algorithm with a considerable amount of state-of-the-art algorithms in manifold clustering: GPCA [Vidal et al., 2005], K-planes [Tseng, 2000], LSA [Yan and Pollefeys, 2006], SCC [Chen and Lerman, 2009], K-manifolds [Souvenir and Pless, 2005], SNSC-LS [Ng et al., 2001] and mumCluster [Wang et al., 2010]. We compare all these algorithms on four benchmark data sets with a wide variety of structures which cover all aspects of manifold clustering: three linear planes [Vidal et al., 2005] in ℜ3 , two well-separated circles [Ng et al., 2001] and two intersecting spirals [Souvenir and Pless, 2005] in ℜ2 , and the hybrid data as shown in Figure 2 (a).

The average clustering accuracy with the corresponding standard deviation and the average computation time over 10 independent runs are tabulated in Table 1. The best average accuracy are boldfaced. The results reveal several interesting observations: (a). Different from many state-of-the-art algorithms which are designed for a specific manifold clustering problem, such as linear algorithms (i.e., GPCA, Kplanes, LSA and SCC) for linear manifold clustering and Kmanifolds for intersecting manifolds, both mumCluster and the proposed LSC give promising performance to all cases of manifold clustering. (b). The proposed LSC performs better than SNSC-LS when there are intersecting manifolds in the data and it always achieves the best results. (c). Generally, as we have expected, the running time of LSC is comparable to many of other algorithms.

4.4 Experiments on Real Data

In this subsection, we compare the performance of LSC with the state-of-the-art algorithms on a well-known yet challenging object recognition database, i.e., the processed COIL-20 database [Nene et al., 1996]. As illustrated in Figure 4, the objects have a wide variety of complex geometric, appearance and reflectance characteristics. Several studies have shown that this task can be viewed as a manifold clustering problem [van der Maaten and Hinton, 2008].

The whole database (N = 1440) and three objects subject to the same topic (N = 216), i.e., three different cars, are used in our experiments. The original resolution of these images is 32 × 32. Here, for computational efficiency, all the algorithms are executed in 10-dimensional principal components space, except that GPCA is executed in 5-dimensional space since it requires a low-dimensional space to work properly [Vidal et al., 2005]. The results for all the algorithms are shown in Table 2, which show that LSC is superior to other algorithms, especially on the coil-three-cars data set.

5 Conclusion

In this paper, we study the potential of spectral methods for hybrid nonlinear manifold clustering. Then, we propose LSC algorithm to the task of detection of multiple hybrid manifolds. Experimental results validate its effectiveness.