哪種聚類演算法可以不需要指定聚類的個數，而且可以生成聚類的規則？

01-07

給一些實例，然後找到一種可以自動聚類的演算法，無需指定聚類的個數，而且會生成聚類的依據（規則）。。。

聚類的規則無非就是"rich get richer"，不指定類別數目的意思就是根據樣本的大小自動選擇合適的聚類中心數目來解釋這些數據，並且希望隨著數據越多，越有可能生成新的類別。

Nonparametric Bayesian 方法可用於解決這類問題，即不限定模型的複雜度，用隨機過程作為類別參數的先驗來模擬數據的生成。在聚類問題上，通常用Dirichlet process作為mixture proportions的先驗，這方面的理論大概從Ferguson, 1973; Blackwell, Macqueen, 1973 到Sethuraman, 1994為止構建完成。應用是從Neal 1992; Rasmussen 2000 的論文開始，是關於infinite mixture model的。

DP的擴展包括Hierarchical Dirichlet process 和 Pitman-Yor process。前者是對joint groups的數據建模，假設這些groups共享一個base distribution，也就是參數的先驗。而PYP在Chinese restaurant process的基礎上加了一個參數用於控制類別數目的生成速度，使得PYP能夠更好的刻畫Power-law這一現象。這兩種擴展很大程度推動了DP的應用，比如基於HDP-HMM以及Infinite PCFG，還有Hierarchical-PYP等。

不要太相信有這種方法，一般都是將k轉化為別的參數。畢竟這是一個如何防止過擬合的情況下得出最優解的問題。如果資源足夠豐富，可以考慮對不同的k賦予先驗的概率之後使用貝葉斯

順便推薦 Deciding the Number of Clusterings

Hierarchical Dirichlet Process http://www.cs.berkeley.edu/~jordan/papers/hdp.pdf

We consider problems involving groups of data, where each observation within a group is a draw from a mixture model, and where it is desirable to share mixture components between groups. We assume that the number of mixture components is unknown a priori and is to be inferred from the data. In this setting it is natural to consider sets of Dirichlet processes, one or each group, where the well-known clustering property of the Dirichlet process provides a nonparametric prior for the number of mixture componentswithin each group. Given our desire to tie the mixture models in the various groups, we consider a hierarchical model, speci?cally one in which the base measure for the child Dirichlet processes is itself distributed according to a Dirichlet process. Such a base measure being discrete, the child Dirichlet processes necessarily share atoms. Thus, as desired, the mixture models in the different groups necessarily share mixture components. We discuss representations of hierarchical Dirichlet processes in terms of a stick-breaking process, and a generalization of the Chinese restaurant process that we refer to as the 「Chinese restaurant franchise.」 We present Markov chain Monte Carlo algorithms for posterior inference in hierarchical Dirichlet process mixtures, and describe applications to problems in information retrieval and text modelling.

上面引用的部分是文章摘要，加粗的部分是說HDP將聚類的數目當做一個未知的先驗，通過數據推出來，也就是達到了你說的不需要指定聚類的個數。

但是，這個演算法卻只能達到你所說的前一部分，至於規則什麼的，HDP是做不到的（至少我理解的是）。

其實我猜你想問的是怎麼改進k-means演算法，可以拜託手工指定k值。我自己也找過相關的內容，依照我的經驗，這類實質上通過算距離達到聚類的演算法是必須要手工指定一個值的，也就是說需要一個參照。至於DBSCAN等其他傳統聚類演算法，也必然需要人工的先驗知識的。

--------------------------以下是我不成熟的見解，因為HDP我到現在也是略知一二----------------------------

HDP高級的地方在於使用數據說話，和把聚類數目作為一個先驗。這樣通過數據和Bayesian學派的各種方法就可以將聚類數目推斷出來。說實話，的確不太好理解。折棍(stick-breaking)我覺得比較抽象，Polay Urn更是複雜，相比較而言中國餐館過程(因為是美國人寫的Chinese這個名字，我自然不自然的就把restaurant翻譯成餐館了，唐人街情節嚴重了吧) 還是比較容易理解的。

即使這樣，我覺得HDP還是比較複雜的，不知道工業上有沒有成功的應用。

1.基於層次聚類演算法：

常見的有由下而上的兩步聚類，確定相似函數及相似度的ROCK聚類等

2.基於密度聚類演算法：

常見的有基於最低信任值及最低n/N閥值的Dbscan

3.基於神經網路的聚類：

常見的有把輸入變數離散到目標維度上的SOM

4.基於統計學的聚類：

常見的有類似於變數迭代的方式，產出如同決策樹形式的COBWeb

affinity propagation, dbscan, hierarchical clustering

如果數據能轉化成用網路(network)來表示，那麼用community detection的技術便可以把所有節點(node)聚類。據我所知其中很多方法都不需要提前指定community數目，而且也不需要程序自己指定community數目。我覺得這主要是因為它們採用了greedy heuristic的演算法。

Community detection method裡面最流行的是modularity maximization，它搜索一種community partition使得所有節點的模式特徵最明顯。這種方法基於的想法是：community內部的連接(edge)應該更多更強，對於一種特定的community partition，每個community中的連接應該和一個隨機網路的連接相差越大越好，這個差值一般就定義成modularity。不過，這種方法實際應用時還是要考慮很多問題，比如隨機網路的null model如何選取等等。另外，很多其它community detection method也可以考慮一下。

GMM cluster就完全不用指定聚類個數啊……可以用model evidence（簡單點就用BIC）確定聚類個數，或者用cross-validation的likelihood確定聚類個數。為什麼沒人回答這個……這個只是對很多問題效果不好而已，尤其是類別本身離Gaussian差很遠的時候。（但既然你覺得k-means可以用，那GMM cluster就不會差）

當然還是上面多人指出的Dirichlet Process才是王道，不過還是有個需要求的超參數alpha……

@吳惠甲已經講得比較清楚了。以前也做過一些nonparametric方法的研究，但總體感覺離實際應用還有點距離。當然scalability是最大的issue, 而且rich get richer的假設在某些方面並不是特別適合。

不管怎樣，如果想學習這方面的知識，個人比較推薦一下資料：

https://github.com/echen/dirichlet-process （把intuition講得比較清楚）

http://cs.brown.edu/people/sudderth/papers/sudderthPhD.pdf (1,2章節是入門資料）

當然也可以去讀Emily Fox, Yee Whye Teh, Erik B. Sudderth等學者的論文。

呵呵這是個有趣的問題，LZ可以想一想：如果有這樣的方法，你覺得它要用什麼樣的證據才能證明你它替你自動選擇的類個數是最佳的呢？

自動確定聚類個數的話，可以參考一下聚類穩定性（Cluster Stability）研究，2009年有個綜述（Clustering Stability: An Overview），說實話這方法有各種問題，但思路總是值得一試的。

層次聚類，通過指定類別間的距離（比如歐式距離）來控制演算法的迭代次數。

Affinity propagation 一系列吧

最近看了一篇Science 2007文章，似乎Affinity Propagation可以不指定聚類數。

DBSCN演算法基於密度的聚類演算法，可以不指定聚類數目，而且易於發現不規則的聚類！

MeanShift

Meanshift 是一種概率密度估計方法，所有點都會沿著梯度上升方向收斂到它各自的mode（峰值）。收斂到同一個mode的點為一個類，最終有多少個mode，就有多少個類，不需要指定聚類個數。下面這張圖比較直觀，mode detection 自動確定有幾個類：

聚類是聚類，規則是規則，別想著一個演算法就能解決你想要的問題。

層次聚類會把你的記錄數從N聚稱一個，不需要你事先制定聚類個數，但聚完後你得觀察，到哪個類結束，也就是你最終給他分類的個數。

聚類完後，後續需要決策樹提取規則，這個@wenyingge 已經提到過。

密度聚類，比如DBSCAN, OPTICS都可以不指定聚類中的類別個數的，你可以看看周志華老師的機器學習那本書，封面是塊西瓜http://product.m.dangdang.com/product.php?pid=23898620host=product.dangdang.com

聚類演算法兩步聚類可以不用設定聚類個數，至於聚類規則可以嘗試用決策樹提取規則~

總得有個超參數，不指定類別數，也得指定個其他形式的超參數……

外行來說一句，最近讀了李德毅院士的《不確定性人工智慧》，裡面用到的自適應高斯雲變換演算法似乎可以不用指定聚類數目，是否自動生成聚類規則可能還需商榷。

至於效果如何，我沒模擬過。。。反正書上說挺好的。