透過張量法進行未給定群數之譜聚類

頻譜圖方法在非監督式學習的的領域中，經常勝過k-平均演算法或階層式等傳統分群法，並在資料分析裡扮演著重要的工具。也因為經過實證研究以及理論分析上的驗證，頻譜圖方法在各種不同領域都獲得廣泛的關注；但是，儘管頻譜圖的實驗結果極為出色，此方法卻有著先天上的限制—頻譜圖的理論假設是基於「兩點」間的相似度進行操作。以現今機器學習或者是電腦視覺的角度而言，同時考慮多個點或「高階」相似度來判讀數據是在過程中不可或缺的條件，於是這類型的問題也吸引了許多研究人員投入，以求得更為通用的理論框架。　　另外，群數的選擇對於分群法而言，也是不可避免的議題，在過去文獻也能看到來自各種不同角度的討論和研究。在此篇論文裡，我們從頻譜圖方法的觀點出發，利用拉普拉斯矩陣中的特殊對角結構，讓演算法能夠自動選擇群數。　　我們在此提出了讓頻譜分群法運用高階相似度、且能自動選擇群數的演算法框架；同時為了避免計算複雜度等問題，我們也運用了數值方法上的技巧，讓演算法能夠實際在資料分析上進行應用。只要給予合適的相似度度量方法，此方法便能給出適當的分群結果，而在實驗過程中，甚至能偵測出潛在的幾何結構。

關鍵字

高階譜聚類；張量分群法；超圖分割；非監督式學習

並列摘要

Spectral graph methods represent an important class tools for analyzing the data and often outperform traditional clustering algorithms such as k-means or single linkage. The technique earns a widespread concern in various fields due to its convincing empirical studies and the theory-guaranteed approaches. Despite the veritable success, pairwise relationship lies at the heart of its fundamental constraint in assumption. Recent challenges in machine learning or computer vision have necessitated the use of higher-order affinities in learning methods, and this has led to a considerable interest to higher-order partitioning problem. Another major issue for clustering algorithms is the choice of cluster number, and it evokes numerous studies to tackle the problem. The diagonal structure of Laplacian matrix in spectral graph methods is poised to provide an elegant automatic scheme. In this paper, we propose a framework on higher-order relationship for spectral clustering without determining the cluster number. Numerical techniques are also exploited in order to make the algorithm practical. The experiment demonstrates that, given an appropriate affinity measure, we can get the desired partition and may detect the underlying geometric structure.

並列關鍵字

Multi-way spectral clustering ； Tensor clustering ； Hypergraph partitioning ； Unsupervised learning

參考文獻

[2] S. Agarwal, J. Lim,L. Zelnik-Manor, P. Perona, D. Kriegman, and S. Belongie. Beyond pairwise clustering. In IEEE Conference on Computer Vision and Pattern Recognition, pp. 838-845, 2005.

[3] E. Arias-Castro, G. Chen, and G. Lerman. Spectral Clustering based on local linear approximations. Electronic Journal of Statistics, 5, pp. 1537-1587, 2011.

[5] S. R. Bulo and M. Pelillo. A game-theoretic approach to hypergraph clustering.

In Advances in Neural Information Processing Systems, 2009.

[6] G. Chen, S. Atev, and G. Lerman. Kernel spectral curvature clustering.

國際替代計量

透過張量法進行未給定群數之譜聚類

全文下載

主題瀏覽