機器學習中，有沒有給定的閾值返回聚類結果的演算法？
聚類演算法中，多級聚類和k-means聚類都不能滿足我的需求。
想尋找一種聚類方法，根據參數返回不同聚類結果的演算法。
有沒有一種演算法，可以提供一個相似度參數作為聚類閾值，閾值越大（越接近1），返回的聚類類別數越多，越接近輸入數據的數量，反之，閾值越小（越接近0），返回的類別數量越少
這裡竟然也開始問專業問題了，內牛滿面。趕緊搶答一下。。。
你說的相似度問題，絕大多數演算法是從Rate Distortion Theory入手（Elements of Information Theory 2nd Ed. Chapter 13）。在這一框架下，相似度是Distortion rate，其核心思想是在給定一定失真度的前提下，如何最優對信號編碼。這樣，相似度誤差就可以在資訊理論框架下有一個很好的解釋了。
能想到的最直接Paper是Bialek@Princeton組前幾年的一篇PNAS
http://www.pnas.org/content/102/51/18297.full.pdf
應該算是直接解決了你的問題。
但是，對於Rate Distortion Theory我目前看到的最好的在Machine Learning上的演繹，是馬毅@UIUC他們組的這篇，雖然這個文章本身並不是直接探討clustering的：
http://perception.csl.uiuc.edu/coding/papers/Ma2007-PAMI.pdf
題主也可以考慮一下基於密度估計的聚類方法，例如這個回答里有人提到的mean shift.
基本思想就是先做一發概率密度估計，例如kernel density estimation, 然後再根據一些直觀的方法選擇密度大的區域作為類。 比如你可以選一個閾值，然後所有高於這個閾值的區域就是一個個的類。
其實，各種聚類方法是有差不多的理論保證的，收斂速度也差不多。在應用角度，這些方法一樣還是有超參數要選。kmeans是類的數目，層次聚類是合併/分離的閾值，非參貝葉斯是你的那些非參分布的prior之類，基於密度的也是要選擇閾值來決定最後結果。 實際用的時候還是要根據數據的多少，效率，實現難度等綜合考慮，複雜模型很多時候不見得比簡單的效果好多少。
插一句題外話，我反而覺得選擇聚類模型時更重要標準是你想要什麼樣的cluster. 如果想要一個個的球，那就kmeans. 如果想要一顆樹，則是層次聚類。關於怎麼樣的數據應該要放在一個類裡面也是，要歐式距離的球，還是近的點粘在一起的流型，還是說不規則的密度高的區域等等。
這些比超參數如何選更能決定最後聚類結果，是實際使用中除了好寫之外的最重要因素。
樓主的問題和樓上的諸位回答所引用的paper絕大多數(如果不是全部)都不能做到帶有outlier的clustering，仔細想一想這其實是不對的。
我覺得這一問題目前做的最好的方法是density clustering，其基本思想是：估計隨機變數的density function，並且用「閾值」截取，density高於閾值的樣本空間部分被聚類，閾值一下的樣本空間都被認為是outlier。這方面已經有了很多工作，LZ可以參考：Rinaldo
,
Wasserman
:
Generalized density clustering
這是該領域的一篇經典paper，LZ還可以好好讀一下它的reference里的很多paper
我想我看明白你意思了？
我想Centroid-based clustering應該符合你所說的~~~演算法是：
init：沒有類別
for：每篇文檔
與已經存在的類質心進行相似度計算，如果很相似，聚類，調整質心。否則，單獨列出一類。
這個聚類演算法，可以只依靠相似度聚類，類的數目沒有被規定。相似度閾值越大，聚類的結果類別越多。因為很多都不滿足這個相似度，所以單獨成一類了。
PS：層次聚類有兩種思想，一種是從一個類里有所有的文檔，之後你去做切分，每次可能就會多一個類。叫做分割式聚類（partitional clustering)。一種是聚合式聚類(agglomerative clustering)，開始自己都單獨成一類，之後根據你的相似性演算法去算閾值，然後聚類。我相信，其中也有你可以用到的.
hierarchical clustering algorithm for document dataset
這篇文章貌似提了16種層次聚類的方法，你可以看看~~~
有沒有一種演算法，可以提供一個相似度參數作為聚類閾值，閾值越大（越接近1），返回的聚類類別數越多，越接近輸入數據的數量，反之，閾值越小（越接近0），返回的類別數量越少
是有的 ，見：
Jia Li, Surajit Ray, Bruce G. Lindsay, "A nonparametric statistical approach to clustering via mode identification," Journal of Machine Learning Research, 8(8):1687-1723, 2007.
文章和代碼
Jia Li"s Homepage on Modal and Linkage Clustering
其中 Ridgeline EM (REM) (for analyzing cluster separability) 可以用來measure某個cluster是否足夠separable from other clusters，範圍是0到1。這個measure不是聚類的參數而是實際上是Model EM演算法的結果，所以認為是相對穩定的量，用它來做閾值非常直觀和容易解釋。
用戶一旦給出一個從0到1的閾值，HMAC就可以自動產生聚類結果，並且保證所有cluster的separability measure都大於閾值。
這是我目前見過最fit題主問題的方案。當然對不同的measure或者parameter做閾值都可以得到不同cluster 數目的結果，關鍵是結果對這個閾值是否敏感，傳統的Kmeans、層次聚類都存在這樣的缺點。除了我推薦的工作，題主還可以考慮 Dirichlet Processes Gaussian Mixture Model。
當然聚類方法實在太多了，這裡實在無法細說。聚類問題的一大難點就是如何有效確定聚類個數。這方面無論是學術界還是產業界都有很多有益的嘗試。
從學術角度，聚類問題的經典演算法，無論是k-means系列還是層次聚類演算法，都需要手工確定聚類個數。實際使用中，需要人們來遍歷各種聚類個數的設定，利用某種方式評價在哪種聚類個數下的效果最好，從而確定聚類個數，可以看到，這種做法費時費力。而如果將聚類個數作為模型的參數之一，機器學習領域關注的重點問題之一就是如何自動確定模型參數，即nonparametric bayesian模型。我認為近年來比較經典的不需要顯式指定聚類個數的聚類演算法是加拿大Frey組發表在2007年Science雜誌上的Affinity Propagation演算法，論文名稱：Clustering by Passing Messages Between Data Points。AP演算法只需要用戶設置一個閾值，控制聚類個數的多少，而不需要直接指定聚類個數。
從產業角度，可以在k-means的基礎上設置閾值來實現聚類個數的自動確定。具體方法可以參考一篇發表在2008年WWW的會議論文：Automatic online news issue construction in web environment。基本思想是首先設置一個聚類個數k，對一部分數據進行聚類，然後對剩下的數據不斷加入進來，判斷它們是否屬於已有的k個聚類，如果不屬於（這裡需要用到閾值）就新開一個聚類。具體可以看這篇論文。我看樓主要的 就是 分層聚類。
我說對了嗎？
- 聚類數目這個問題，其實很多演算法都沒有很好的解決，比如K-means明確要求有類別數目K。
- 部分解決這個問題的演算法，樓上@阿穩 說的基於圖的譜聚類，利用特徵值/特徵向量等信息判別出類別數目。
- 還有一類問題：子空間聚類 中的稀疏子空間聚類(SSC)，低秩表示(Low Rank Representation)等方法也可以根據 相似矩陣 判別出聚類數目K
感覺 樓主 就是在要分層聚類，想要多少聚類數目 你是可以控制的——改幾行代碼，提前終止好了
看看樓下怎麼說...
這個一定是你要的演算法：Canopy演算法。
維基鏈接： Canopy clustering algorithm
基本思路比較簡單，可以用於大至估算聚類數，但需事先給定閾值T1,T2(圖中大小兩個半徑)，因此實際是將聚類數量的確定轉化為閾值的確定。但是應該正是題主你需要的演算法。
基本思路比較簡單，可以用於大至估算聚類數，但需事先給定閾值T1,T2(圖中大小兩個半徑)，因此實際是將聚類數量的確定轉化為閾值的確定。但是應該正是題主你需要的演算法。
Canopy演算法流程如下，- 將需要聚類的數據轉化為一個表單形式，給出閾值T1,T2（T1&>T2）
- 將表單中的第一個數據點（或隨機某個點）從表單中去除並作為一個聚類中心mu1
- 計算表單中餘下數據點距離mu1的距離，如果在距離小於T1則將該點歸於mu1所在的cluster
- 如果距離小於T2則將該點從表單中刪除
- 重複2-4步,直到表單所有的點都被刪除
Canopy演算法允許一個點歸於多個Cluser中，但是已在某聚類中心T2聚類內的點無法再成為新的聚類中心，最終的聚類結果完全取決於閾值T1和T2，半徑越小得到的聚類數越多，半徑越大得到的聚類數越少。
如果需求只是考慮數據對象之間的相似程度，找出比較相似的那些個體，未必要用聚類。而且有時候聚類的結果並不是我們想要的，因為很可能存在聚類較大導致的個體之間並不是很相似的情況。畢竟聚類的動機不是找到相似的數據，而是找到相關的數據。這時候再根據相似程度劃分的話，其實在破壞自然聚類的結果。並且，如果這樣的話為什麼不一開始就不要用聚類呢，畢竟聚類演算法的複雜度都不低。
一定要用的話，除了其它答主的答案，有一篇這個文章：
IEEE Xplore Abstract Clustering by scale-space filtering
具體實現忘記了。但思想基本是這樣：
假設我們現在有一堆數據，已經放到了特徵空間當中。一個自然的聚類，我們認為是數據密度比較高的一個區域。然而在不同的尺度之下，也就是你離近了看這堆數據和遠遠地看這堆數據，得到的結果是不一樣的。離得很遠的話，你根本看不出什麼聚類，數據就一坨。離得很近的話，每個數據看起來和其它數據都是分開的，每個數據都是一類。
那麼，按照這個原理，我們對原數據不斷高斯模糊高斯模糊（有研究表明高斯模糊和人看遠處東西的模糊基本一樣），原來的數據集就被投射到了一個尺度空間，這個空間一端是一個一個的數據點的原數據集，一端是我們遠遠看這個數據集的時候成了一坨的樣子。中間就是我們離數據集不同距離時數據集的樣子。
比如，有一張報紙，我們遠遠看就一個灰點（一個聚類）。離近點就能看清上面有3個新聞塊（3個聚類）。再近點，可能就看清每個標題了（每個標題是一類），然後每段話，每個字這樣。
覺得好的話可以拿來用一下。有個Python庫里看到的。affinityPropagation。。。
庫里的damping，大概跟你描述的功能類似。。。
自動選擇類別的數目？這個應該可以做到 (message passing on factor graphs) http://www.sciencemag.org/content/315/5814/972
http://www.psi.toronto.edu/index.php?q=affinity%20propagation
我的答案這麼靠後，估計也沒什麼人看了，那乾脆放開談談吧。有點懷疑題主的研究思路是不是出現了些偏差，因為設置參數(其中，層級聚類中參數是聚類距離，k-means聚類中參數是簇數目)並給定特徵屬性得到的聚類結果都只是參數約束下最優結果，並非僅給定特徵屬性時得到的無參數約束最優結果，而無參數約束最優結果具有唯一性。無參數約束最優結果求解其實就是一個聚類有效性評估的問題。評估聚類有效性，既有統計學方法，也有CS方法。統計學採用ANOVA方法，重點分析「簇間離差」、「簇內離差」，如果「簇間離差」越大、「簇內離差」越小，則聚類越有效；CS方法最常用的是所謂Silhouette指標(Dudoit S,Fridlyyand J.A,2002)，公式為：Sil(i)=[b(i)-a(i)]/max{a(i),b(i)}，也是反映聚類結構的簇內緊密性和簇間分離性的指標，所有樣本的平均 Silhouette指標值越大，聚類質量越好，其最大值所對應類數為最佳聚類數。
補充一句：無論AP演算法的聚類閾值還是k-means的k值，都需要對參數進行設定。上述解答雖然僅根據數據的特徵屬性得到最優聚類結果，但所用方法(ANOVA、 Silhouette指標值 )都有一個前提假設：必須至少能分出兩類，如果整個數據本身就是一個大類，那麼這兩個方法就不起作用了。
講一個很簡單的一個思路，以k-mean為例。
兩個基本事實：
1，總方差=組內方差+組間方差
2，聚類數(k)越大，組內方差越小，組間方差越大。k=1, 組間方差為零，組內方差等於總方差。k=n，組內方差為零，組間方差等於總方差。
基於圖的聚類有大量滿足你需求的演算法，最簡單的做法是：
1、計算出點與點之間的相似度（為減少存儲空間，低於某個閾值的可以忽略），以相似值為權把點鏈接成圖。
2、設定一個閾值alpha，把低於閾值的邊砍掉，有邊連接的子圖作為一個聚類
2014年science上有篇根據密度聚類的文章，Clustering by fast search and find of density peak. Alex Rodriguez, Alessandro Laio，paper對應的網站有Matlab源碼，我跑過，效果特別好。
這個問題，我沒太看明白。
感覺上樓主期望得到一種能根據參數調整輸出類別數目的方法。
我覺得有一種方法也許可以滿足樓主的要求，它就是on-line kmean演算法：
具體步驟如下：
輸入：相似度參數閾值，所有樣本
輸出：類別數目和類別參數（中心，如果需要可以有協方差陣）
1，初始化類別集合為空；
2，對於輸入的一個樣本，計算其與所有已有類別中心的相似度（為距離大小的反向函數），找到最大相似度和對應的已有類別（如果已有類別集合為空，則認為該相似度為無窮大），如果相似度大於輸入的相似度參數閾值，則認為該樣本屬於該類，更新該類別的中心（以及協方差），如果相似度小於閾值，則認為該樣本不屬於任何類，則用其初始化一個新類別（該樣本即為類別中心）；
3，對所有樣本進行2的處理，最終得到N個類別；
4，對上述類別進行去噪處理，將屬於該類別的樣本數目小於設定閾值的類別刪除，剩下的結果即為最終聚類結果；
如果相似度閾值大，則要求嚴格，每類的覆蓋範圍就小，最終得到的類別數目會多；繁之，相似度閾值小，要求寬鬆，每類的覆蓋範圍大，最終得到的類別數目會少。
希望這個回答會對你有所啟發。可能是我沒看懂LZ的意思，我理解的是包括k-means在內的很多經典的clustering演算法都可以加入參數啊。本身帶參數的也有，基於密度的聚類。
拿k-means來說，你首先要解決的問題是k的選取，這裡就可以加入參數了啊；而在迭代的過程中，每次分配樣本的時候，也可以加入參數啊。
不一定要選一個現成的演算法啊，那些經典的演算法都是通用解，但往往不是具體場景下的最優解。你在理解思想過後，應該根據自己的應用加入一些特化的東西。
為啥這麼多人不懂題主的需求……題主是不知道有多少個類，想通過閾值來控制類的個數，所以HAC和K-means都不行。
於是題主你看這樣行不行，你遍歷所有的pairs，大於等於閾值的就記下來，小於的就扔掉。最後你得到一個鄰接矩陣，就自然而然解決問題了。
當然了你想做各種近似都可以，為了節約點複雜度嘛。LZ最好寫下為神馬K-means不能滿足你的要求
聚類演算法發展到今日已經有各種各樣帶參數或不帶參數的演算法，之前幾位也都提到了。之所以有各種演算法是因為需求不一樣，對類別的定義不一樣，比如密集的，稀疏的，信息量的。k-means檢測出的類別是以某點為中心的超球體，如果類的特性不是這樣就不能用了。GMM相比可以是個橢球體（我的理解是這樣...）。所以建議LZ先觀察想要的類的特性。當然還可能是相似度就沒定好，另說了。最簡單的辦法 將所有的分類數目通過編程 全部迭代一遍 然後選擇最佳的分類數 結果一目了然了
推薦閱讀：