Membership Representation for Subspace Clustering
Membership Representation for Subspace Clustering
- 주제(키워드) membership representation , probabilistic membership , block-diagonal , subspace clustering , nonparametric estimation
- 발행기관 아주대학교
- 지도교수 나상신
- 발행년도 2019
- 학위수여년월 2019. 2
- 학위명 박사
- 학과 및 전공 일반대학원 전자공학과
- 실제URI http://www.dcollection.net/handler/ajou/000000028568
- 본문언어 영어
- 저작권 아주대학교 논문은 저작권에 의해 보호받습니다.
초록/요약
Recent advance of subspace clustering has provided a new way of constructing affinity matrices for clustering. Unlike the kernel-based subspace clustering, which needs tedious tuning among infinitely many kernel candidates, the self-expressive models, the new way derived from linear subspace assumptions, are rigorously combined with the sparse or the low-rank optimization theory to yield a coefficient matrix as a solution of an optimization problem. The coefficient matrices expected to have a (approximately) block-diagonal structure are applied to spectral clustering in order to find the final clusters. Nevertheless, these matrices have quite different meanings from the traditional ones consists of metric similarities of spectral clustering. In fact, most subspace clustering methods perform some sort of value rearrangement as post-processing. However, there is no definitive way to construct the affinity matrices from the coefficient matrices and it is unclear whether these affinity matrices are good enough to apply spectral clustering. In this dissertation, we want to find the clusters directly from the cluster membership estimated from the coefficient matrix without applying spectral clustering. Thus, we propose two framework methods. First, we propose membership representation (MR) which is an alternative approach to detect the block-diagonal structure from the coefficient matrix by constructing a self-expressive system based on a Hadamard product of the coefficient matrix and a membership matrix. To resolve the difficulty in handling the membership matrix, we solve the convex relaxation of the problem. Then another problem is constructed to transform the representation to a normalized membership matrix that is closely related to spectral clustering. We also solve the convex relaxation of the problem. The final cluster result is obtained by performing spectral clustering. However, since MR has a problem that it may be vulnerable to noise and outliers, and that spectral clustering must be performed in order to find clusters. Second, therefore, we propose probabilistic membership representation (PMR) which is a nonparametric method formulated as a maximum a posteriori (MAP) optimization problem to estimate the probabilistic cluster membership that can directly find the clusters from. The likelihood for the coefficient matrix is defined nonparametrically based on histograms given the cluster membership, which is defined as a combination of probability simplices, and the prior probability for the cluster membership is defined as a Bernoulli distribution to regularize the problem. Solving this MAP problem replaces the spectral clustering procedure, and the final cluster membership can be calculated by selecting the clusters with maximum probabilities. The proposed methods provide the state-of-the-art performance for well-known subspace clustering methods on popular benchmark databases. The segmentation accuracy and the normalized mutual information of the proposed methods increase to 0.09-1.12% and 0.88-3.88% for Hopkins155 motion database, and 0.91% and 0.08-0.63% for Yale face database B, respectively.
more초록/요약
최근 부분 공간 클러스터링 분야에서는 유사도 행렬들을 구성하는 새로운 방법이 제안되었습니다. 커널 기반 부분 공간 클러스터링과는 달리, 선형 부분 공간 가정으로부터 유도된 새로운 방법인 자기표현 모델들은 희소 (sparse) 또는 낮은 계수 (low-rank) 최적화 이론과 결합되어 최적화 문제에 대한 솔루션으로 계수 행렬을 산출합니다. 이런 계수 행렬들은 (대략) 블록 대각선 구조를 가질 것으로 예상되며 최종 클러스터를 찾기 위해 스펙트럼 클러스터링을 적용되지만, 이 행렬들은 메트릭 유사성으로 구성된 기존 스펙트럼 클러스터링의 행렬들과는 완전히 다른 의미를 가지고 있습니다. 실제로, 대부분의 부분 공간 클러스터링 방법들은 후처리 과정으로 일종의 값 재배치를 수행합니다. 그러나 계수 행렬들로부터 유사도 행렬들을 구성하는 확실한 방법은 없으며 이런 유사도 행렬들이 스펙트럼 클러스터링에 적용되어도 되는 지에 대한 여부는 불분명합니다. 이 논문에서 우리는 스펙트럼 클러스터링을 적용하지 않고 계수 행렬로부터 추정된 클러스터 멤버쉽으로부터 직접 클러스터를 찾고자 합니다. 따라서, 우리는 프레임워크가 다른 두 가지 방법들을 제안합니다. 첫 번째로, 계수 행렬과 멤버쉽 행렬의 아다마르 (Hadamard) 곱을 기반으로 자기표현 시스템을 구성하여, 계수 행렬로부터 블록 대각 구조를 검출하는 멤버쉽 표현 MR (membership representation)을 제안합니다. 멤버십 행렬을 풀기에는 어렵기 때문에 문제의 볼록 완화 (convex relaxation)를 풉니다. 그 다음, 멤버쉽 표현을 스펙트럼 클러스터링과 밀접한 관계가 있는 정규화된 멤버십 행렬로 변환하기 위한 문제를 구성하고 이 문제의 볼록 완화를 풉니다. 최종 클러스터 결과는 스펙트럼 클러스터링을 수행하여 얻습니다. 하지만 MR은 잡음과 특이값에 취약할 수 있는 문제와 클러스터를 찾기 위해서는 결국 스펙트럼 클러스터링을 수행해야 하는 문제가 있습니다. 그래서 두 번째로, 클러스터를 직접 찾을 수 있는 확률적 클러스터 멤버쉽을 추정하기 위해 최대 사후 확률 (MAP) 최적화 문제로 공식화한 비모수적 방법인 확률적 멤버쉽 표현 PMR (probabilistic membership representation)을 제안합니다. 계수 행렬에 대한 우도는 확률 단순성의 조합으로 정의되는 클러스터 멤버십에 주어진 히스토그램을 기반으로 비모수적으로 정의되며, 클러스터 멤버쉽에 대한 사전 확률은 문제를 규칙화하기 위해 베르누이 분포로 정의됩니다. 이 MAP 문제를 풀면 스펙트럼 클러스터링 과정이 대체되고, 확률이 최대인 클러스터를 선택하여 최종 클러스터 멤버쉽을 계산할 수 있습니다. 제안된 방법들은 부분 공간 클러스터링 방법들에서 잘 알려진 데이터들에 대해 좋은 성능을 나타냅니다. 제안된 방법들의 세분화 정확도와 정규화된 상호 정보는 Hopkins155 모션 데이터베이스에서 각각 0.09-1.12%와 0.88-3.88%, Yale 얼굴 데이터베이스 B에서 각각 0.91% 와 0.08-0.63% 증가합니다.
more목차
I Introduction 1
I.A. Previous works for subspace clustering 1
I.B. Motivation 6
I.C. Organization of the dissertation 9
II Review on Related Works 11
II.A. Sparse and low-rank subspace clustering 11
II.B. Spectral clustering 14
III Membership Representation (MR) 19
III.A. Detecting block-diagonal structure 19
III.A.1. Membership representation 19
III.A.2. Normalized membership representation 23
III.B. Detailed algorithm 27
III.B.1. Finding M ̆ 27
III.B.2. Finding F ̆29
III.B.3. Post-processing 31
IV Probabilistic Membership Representation (PMR) 33
IV.A. MAP formulation 33
IV.B. Relaxation to probabilistic membership representation 39
IV.C. Detailed algorithm 42
IV.D. Practical considerations 48
V Experiments 53
V.A. Experimental setting 53
V.B. Experimental results 58
V.B.1. Motion clustering 59
V.B.2. Face image clustering 65
V.B.3. Object image clustering 70
V.B.4. Handwritten digit clustering 72
V.B.5. Action clustering 78
VI Conclusion 82
