?

?

核聚類與支持向量聚類?

?

聚類是數據挖掘中用來發現數據分布和隱含模式的一項重要技術[1]。作為一種常見的數據分析工具和無監督機器學習方法，聚類的目的是把數據集合分成若干類（或簇），使得每個類中的數據之間最大限度地相似，而不同類中的數據最大程度地不同。根據聚類算法所采用的基本思想，大致可以將它們分為五種[2]，即劃分聚類、層次聚類、基于密度的聚類、基于網格的聚類和基于模型的聚類。目前對聚類算法的研究正在不斷深入，其中核聚類算法和譜聚類算法是近年來受到廣泛關注的兩種算法[3]。

?

核聚類方法的主要思想是通過一個非線性映射，將輸入空間中的數據點映射到高維特征空間中，并選取合適的Mercer核函數代替非線性映射的內積，在特征空間中進行聚類。該方法是普適的，它比經典的聚類方法有較大的改進。它通過非線性映射增加了數據點線性可分的概率，即能較好地分辨、提取并放大有用的特征，從而實現更為準確的聚類，算法收斂速度也較快。在經典聚類算法失效的情況下，核聚類算法常常能得到較好的聚類結果[4]。

?

?支持向量聚類（Support Vector Clustering, SVC）屬于核聚類的一種，它以支持向量機（Support Vector Machine, SVM）為工具進行聚類[5]。它是Ben-Hur等在基于高斯核的SVDD（Support Vector Domain Description）算法基礎上進一步發展起來的無監督非參數型的聚類算法[6]。它的基本思想是：利用高斯核，將數據空間中的數據點映射到一個高維的特征空間中。再在特征空間中尋找一個能包圍所有數據點象的半徑最小的球，將這個球映回到數據空間，則得到了包含所有數據點的等值線集。這些等值線就是簇的邊界。每一條閉合等值線包圍的點屬于同一個簇[7, 8]。SVC算法主要分為兩個階段：SVC訓練階段和聚類分配階段。其中SVC訓練階段包括高斯核寬度系數的確定、核矩陣的計算、Lagrange乘子的計算、支持向量的選取和高維特征空間中特征球半徑的計算。聚類分配階段首先生成鄰接矩陣，然后根據鄰接矩陣進行聚類分配[9]。

?

SVC算法具有兩大顯著優勢：能產生任意形狀的簇邊界；能分析噪聲數據點且能分離相互交疊的簇。這是許多聚類算法無法做到的。但SVC算法仍存在兩個瓶頸： Lagrange乘子的計算和鄰接矩陣的計算。相對而言，后者需要消耗的計算時間遠比前者多[9]。因此很多新的SVC算法都旨在提高鄰接矩陣的計算效率[10, 11]。

?

from: http://www.sciencenet.cn/m/user_content.aspx?id=252321

?

參考文獻

[1] Xu R, Wunsch D. Survey of Clustering Algorithms. IEEE Transaction on Neural Networks, 2005, 16(3): 645-678.

[2] Han J, Kamber M. Data Mining: Concepts and Techniques, Second Edition. Morgan Kaufmann, San Francisco, 2006.

[3] Filippone M, Camastra F, Masulli F, Rovetta S. A Survey of Kernel and Spectral Methods for Clustering. Pattern Recognition, 2008, 41(1): 176-190.

[4] 張莉，周偉達，焦李成. 核聚類算法. 計算機學報, 2002, 25(6): 587-590.

[5] Burges C J C. A Tutorial on Support Vector Machines for Pattern Recognition. Data Mining and Knowledge Discovery, 1998, 2(2): 121-167.

[6] Tax D M J, Duin R P W. Support Vector Domain Description. Pattern Recognition Letters, 1999, 20(11-13): 1191-1199.

[7] Ben-Hur A, Horn D, Siegelmann H T, Vapnik V. Support Vector Clustering. Journal of Machine Learning Research, 2001, 2(12): 125-137.

[8] Scholkopf B, Williamson R, Smola A, Shawe-Taylor J, Platt J. Support Vector Method for Novelty Detection. Advances in Neural Information Processing System 12. 2000: 582-588.

[9] 呂常魁，姜澄宇，王寧生. 一種支持向量聚類的快速算法. 華南理工大學學報. 2005, 33(1): 6-9.

[10] Lee J, Lee D. An Improved Cluster Labeling Method for Support Vector Clustering. IEEE Transactions on Pattern Analysis and Machine Intelligence. 2005, 27(3): 461-464.

[11] Camastra F, Verri A. A Novel Kernel Method for Clustering. IEEE Transactions on Pattern Analysis and Machine Intelligence. 2005, 27(5):801-805.

?

?

總結

以上是生活随笔為你收集整理的核聚类与支持向量聚类的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。