資源描述：
《各種聚類算法介紹及對比》由會員上傳分享，免費在線閱讀，更多相關內容在教育資源-天天文庫。
1、一、層次聚類1、層次聚類的原理及分類1）層次法（Hierarchicalmethods）先計算樣本之間的距離。每次將距離最近的點合并到同一個類。然后，再計算類與類之間的距離，將距離最近的類合并為一個大類。不停的合并，直到合成了一個類。其中類與類的距離的計算方法有：最短距離法，最長距離法，中間距離法，類平均法等。比如最短距離法，將類與類的距離定義為類與類之間樣本的最短距離。層次聚類算法根據(jù)層次分解的順序分為：自下底向上和自上向下，即凝聚的層次聚類算法和分裂的層次聚類算法（agglomerative和d
2、ivisive），也可以理解為自下而上法（bottom-up）和自上而下法（top-down）。自下而上法就是一開始每個個體（object）都是一個類，然后根據(jù)linkage尋找同類，最后形成一個“類”。自上而下法就是反過來，一開始所有個體都屬于一個“類”，然后根據(jù)linkage排除異己，最后每個個體都成為一個“類”。這兩種路方法沒有孰優(yōu)孰劣之分，只是在實際應用的時候要根據(jù)數(shù)據(jù)特點以及你想要的“類”的個數(shù)，來考慮是自上而下更快還是自下而上更快。至于根據(jù)Linkage判斷“類”的方法就是最短距離法、最
3、長距離法、中間距離法、類平均法等等（其中類平均法往往被認為是最常用也最好用的方法，一方面因為其良好的單調性，另一方面因為其空間擴張/濃縮的程度適中）。為彌補分解與合并的不足，層次合并經(jīng)常要與其它聚類方法相結合，如循環(huán)定位。?2）Hierarchicalmethods中比較新的算法有BIRCH（BalancedIterativeReducingandClusteringUsingHierarchies利用層次方法的平衡迭代規(guī)約和聚類）主要是在數(shù)據(jù)量很大的時候使用，而且數(shù)據(jù)類型是numerical。首先
4、利用樹的結構對對象集進行劃分，然后再利用其它聚類方法對這些聚類進行優(yōu)化；ROCK（AHierarchicalClusteringAlgorithmforCategoricalAttributes）主要用在categorical的數(shù)據(jù)類型上；Chameleon（AHierarchicalClusteringAlgorithmUsingDynamicModeling）里用到的linkage是kNN（k-nearest-neighbor）算法，并以此構建一個graph，Chameleon的聚類效果被認為非
5、常強大，比BIRCH好用，但運算復雜度很高，O(n^2)。2、層次聚類的流程凝聚型層次聚類的策略是先將每個對象作為一個簇，然后合并這些原子簇為越來越大的簇，直到所有對象都在一個簇中，或者某個終結條件被滿足。絕大多數(shù)層次聚類屬于凝聚型層次聚類，它們只是在簇間相似度的定義上有所不同。這里給出采用最小距離的凝聚層次聚類算法流程：(1)將每個對象看作一類，計算兩兩之間的最小距離；(2)將距離最小的兩個類合并成一個新類；(3)重新計算新類與所有類之間的距離；(4)重復(2)、(3)，直到所有類最后合并成一類。
6、?9聚類的效果如下圖，黑色是噪音點：另外我們可以看出凝聚的層次聚類并沒有類似基本K均值的全局目標函數(shù)，沒有局部極小問題或是很難選擇初始點的問題。合并的操作往往是最終的，一旦合并兩個簇之后就不會撤銷。當然其計算存儲的代價是昂貴的。3、層次聚類的優(yōu)缺點優(yōu)點：1，距離和規(guī)則的相似度容易定義，限制少；2，不需要預先制定聚類數(shù)；3，可以發(fā)現(xiàn)類的層次關系；4，可以聚類成其它形狀缺點：1，計算復雜度太高；2，奇異值也能產(chǎn)生很大影響；3，算法很可能聚類成鏈狀?r語言中使用hclust(d,method="compl
7、ete",members=NULL)：進行層次聚類。d為距離矩陣；method表示類的合并方法，single最短距離法，complete最長距離法，median中間距離法，mcquitty?相似法，average?類平均法，centroid重心法，ward離差平方和法；members為NULL或d長度的矢量。二、劃分聚類法k-means基于劃分的方法（Partition-basedmethods）：其原理簡單來說就是，想象你有一堆散點需要聚類，想要的聚類效果就是“類內的點都足夠近，類間的點都足夠遠”
8、。首先你要確定這堆散點最后聚成幾類，然后挑選幾個點作為初始中心點，再然后依據(jù)預先定好的啟發(fā)式算法（heuristicalgorithms）給數(shù)據(jù)點做迭代重置（iterativerelocation），直到最后到達“類內的點都足夠近，類間的點都足夠遠”的目標效果。Partition-basedmethods聚類多適用于中等體量的數(shù)據(jù)集，但我們也不知道“中等”到底有多“中”，所以不妨理解成，數(shù)據(jù)集越大，越有可能陷入局部最小。1、Kmeans算法的原理k-means算法以k
