聚類演算法的實例

① 有哪些常用的聚類演算法

【聚類】聚類分析是直接比較各對象之間的性質，根據在對象屬性中發現的描述對象及其關系的信息，將數據對象分組。其目標是，組內的對象相互之間是相似的（相關的），而不同組中的對象是不同的（不相關的）。組內的相似性（同質性）越大，組間差別越大，聚類就越好。

聚類的目標是通過對無標記訓練樣本的學習來揭示數據的內在性質及規律，是無監督學習過程。在無監督學習中，訓練樣本標記信息是未知的。聚類試圖將數據集中的樣本劃分為若干個通常不相交的子集，每個子集稱為一個「簇」，每個簇可能對應於一些潛在的類別，這些類別概念對聚類演算法而言事先是未知的，聚類過程僅能自動形成簇結構，簇所對應的概念語義需要由使用者來把握和命名。

② 分類和聚類的區別及各自的常見演算法

1、分類和聚類的區別：
Classification (分類)，對於一個classifier，通常需要你告訴它「這個東西被分為某某類」這樣一些例子，理想情況下，一個 classifier 會從它得到的訓練集中進行「學習」，從而具備對未知數據進行分類的能力，這種提供訓練數據的過程通常叫做supervised learning (監督學習)，
Clustering (聚類)，簡單地說就是把相似的東西分到一組，聚類的時候，我們並不關心某一類是什麼，我們需要實現的目標只是把相似的東西聚到一起。因此，一個聚類演算法通常只需要知道如何計算相似度就可以開始工作了，因此 clustering 通常並不需要使用訓練數據進行學習，這在Machine Learning中被稱作unsupervised learning (無監督學習).
2、常見的分類與聚類演算法
所謂分類，簡單來說，就是根據文本的特徵或屬性，劃分到已有的類別中。如在自然語言處理NLP中，我們經常提到的文本分類便就是一個分類問題，一般的模式分類方法都可用於文本分類研究。常用的分類演算法包括：決策樹分類法，樸素貝葉斯分類演算法(native Bayesian classifier)、基於支持向量機(SVM)的分類器，神經網路法，k-最近鄰法(k-nearestneighbor，kNN)，模糊分類法等等。
分類作為一種監督學習方法，要求必須事先明確知道各個類別的信息，並且斷言所有待分類項都有一個類別與之對應。但是很多時候上述條件得不到滿足，尤其是在處理海量數據的時候，如果通過預處理使得數據滿足分類演算法的要求，則代價非常大，這時候可以考慮使用聚類演算法。
而K均值(K-mensclustering)聚類則是最典型的聚類演算法(當然，除此之外，還有很多諸如屬於劃分法K中心點（K-MEDOIDS）演算法、CLARANS演算法；屬於層次法的BIRCH演算法、CURE演算法、CHAMELEON演算法等；基於密度的方法：DBSCAN演算法、OPTICS演算法、DENCLUE演算法等；基於網格的方法：STING演算法、CLIQUE演算法、WAVE-CLUSTER演算法；基於模型的方法)。

③ k均值聚類演算法例題

第一輪
A1(2,10)
B1（5,8）,A3（8,4）,B2（7,5）,B3（6,4）,C2（4,9）
C1（1,2）,A2（2,5）
對應中心分別是（2,10),（6,6）,(1.5,3.5)
最後結果：
｛A1(2,10),B1（5,8）,C2（4,9）｝
｛A3（8,4）,B2（7,5）,B3（6,4）｝
｛C1（1,2）,A2（2,5）｝

④ 大數據分析之聚類演算法

大數據分析之聚類演算法
1. 什麼是聚類演算法
所謂聚類，就是比如給定一些元素或者對象，分散存儲在資料庫中，然後根據我們感興趣的對象屬性，對其進行聚集，同類的對象之間相似度高，不同類之間差異較大。最大特點就是事先不確定類別。
這其中最經典的演算法就是KMeans演算法，這是最常用的聚類演算法，主要思想是:在給定K值和K個初始類簇中心點的情況下，把每個點(亦即數據記錄)分到離其最近的類簇中心點所代表的類簇中，所有點分配完畢之後，根據一個類簇內的所有點重新計算該類簇的中心點(取平均值)，然後再迭代的進行分配點和更新類簇中心點的步驟，直至類簇中心點的變化很小，或者達到指定的迭代次數。
KMeans演算法本身思想比較簡單，但是合理的確定K值和K個初始類簇中心點對於聚類效果的好壞有很大的影響。
聚類演算法實現
假設對象集合為D，准備劃分為k個簇。
基本演算法步驟如下：
1、從D中隨機取k個元素，作為k個簇的各自的中心。
2、分別計算剩下的元素到k個簇中心的相異度，將這些元素分別劃歸到相異度最低的簇。
3、根據聚類結果，重新計算k個簇各自的中心，計算方法是取簇中所有元素各自維度的算術平均數。
4、將D中全部元素按照新的中心重新聚類。
5、重復第4步，直到聚類結果不再變化。
6、將結果輸出。

核心Java代碼如下：
/**
* 迭代計算每個點到各個中心點的距離，選擇最小距離將該點劃入到合適的分組聚類中，反復進行，直到
* 分組不再變化或者各個中心點不再變化為止。
* @return
*/
public List[] comput() {
List[] results = new ArrayList[k];//為k個分組，分別定義一個聚簇集合，未來放入元素。

boolean centerchange = true;//該變數存儲中心點是否發生變化
while (centerchange) {
iterCount++;//存儲迭代次數
centerchange = false;
for (int i = 0; i < k; i++) {
results[i] = new ArrayList<T>();
}
for (int i = 0; i < players.size(); i++) {
T p = players.get(i);
double[] dists = new double[k];
for (int j = 0; j < initPlayers.size(); j++) {
T initP = initPlayers.get(j);
/* 計算距離 這里採用的公式是兩個對象相關屬性的平方和，最後求開方*/
double dist = distance(initP, p);
dists[j] = dist;
}

int dist_index = computOrder(dists);//計算該點到各個質心的距離的最小值，獲得下標
results[dist_index].add(p);//劃分到對應的分組。
}
/*
* 將點聚類之後，重新尋找每個簇的新的中心點，根據每個點的關注屬性的平均值確立新的質心。
*/
for (int i = 0; i < k; i++) {
T player_new = findNewCenter(results[i]);
System.out.println("第"+iterCount+"次迭代，中心點是："+player_new.toString());
T player_old = initPlayers.get(i);
if (!IsPlayerEqual(player_new, player_old)) {
centerchange = true;
initPlayers.set(i, player_new);
}

}

}

return results;
}
上面代碼是其中核心代碼，我們根據對象集合List和提前設定的k個聚集,最終完成聚類。我們測試一下，假設要測試根據NBA球員的場均得分情況，進行得分高中低的聚集，很簡單，高得分在一組，中等一組，低得分一組。
我們定義一個Player類，裡面有屬性goal，並錄入數據。並設定分組數目為k=3。
測試代碼如下:
List listPlayers = new ArrayList();
Player p1 = new Player();
p1.setName(「mrchi1」);
p1.setGoal(1);
p1.setAssists(8);
listPlayers.add(p1);

Player p2 = new Player();
p2.setName("mrchi2");
p2.setGoal(2);
listPlayers.add(p2);

Player p3 = new Player();
p3.setName("mrchi3");
p3.setGoal(3);
listPlayers.add(p3);
//其他對象定義此處略。製造幾個球員的對象即可。
Kmeans<Player> kmeans = new Kmeans<Player>(listPlayers, 3);
List<Player>[] results = kmeans.comput();
for (int i = 0; i < results.length; i++) {
System.out.println("類別" + (i + 1) + "聚集了以下球員：");
List<Player> list = results[i];
for (Player p : list) {
System.out.println(p.getName() + "--->" + p.getGoal()

}
}
演算法運行結果：

可以看出中心點經歷了四次迭代變化，最終分類結果也確實是相近得分的分到了一組。當然這種演算法有缺點，首先就是初始的k個中心點的確定非常重要，結果也有差異。可以選擇彼此距離盡可能遠的K個點，也可以先對數據用層次聚類演算法進行聚類，得到K個簇之後，從每個類簇中選擇一個點，該點可以是該類簇的中心點，或者是距離類簇中心點最近的那個點。

⑤ 一種面向高維數據的集成聚類演算法

一種面向高維數據的集成聚類演算法
聚類集成已經成為機器學習的研究熱點，它對原始數據集的多個聚類結果進行學習和集成，得到一個能較好地反映數據集內在結構的數據劃分。很多學者的研究證明聚類集成能有效地提高聚類結果的准確性、魯棒性和穩定性。本文提出了一種面向高維數據的聚類集成演算法。該方法針對高維數據的特點，先用分層抽樣的方法結合信息增益對每個特徵簇選擇合適數量比較重要的特徵的生成新的具代表意義的數據子集，然後用基於鏈接的方法對數據子集上生成的聚類結果進行集成．最後在文本、圖像、基因數據集上進行實驗，結果表明，與集成前的K均值聚類演算法及基於鏈接的聚類集成演算法相比，該方法能有效的改善聚類結果。
引 言
聚類分析又稱群分析，是根據「物以類聚」的道理對樣品或指標進行分類的一種多元統計分析方法。它是一個將數據分到不同類或者簇的過程，所以同一個簇中的對象有很大的相似性，而不同簇間的對象有很大的相異性。聚類分析是機器學習、模式識別的一個最重要的研究方向之一，它是了解數據集的結構的一種最重要的手段，並已經成功的應用於數據挖掘、信息檢索、語音識別、推薦系統等領域。
現實世界中的數據集具有各種形狀和結構，不存在哪一種單一的演算法對任何數據集都表現的很好[3]，沒有一種聚類演算法能准確揭示各種數據集所呈現出來的多種多樣的形狀和簇結構，每一種聚類演算法都有其優缺點，對於任何給定的數據集，使用不同的演算法都會有不同的結果，甚至對於同一種演算法給定不同的參數都會有不同的聚類結果，自然分組概念內在的不明確性決定了沒有一個通用的聚類演算法能適用於任何數據集的聚類問題。此外，類存在多樣性的特點，類具有不同的形狀、大小、密度，而且類之間往往是相互重疊的，這樣的問題在高維數據中更加明顯，因為不相關的或者冗餘的特徵會使類的結構更加不明顯。K均值演算法[5]是一種應用廣泛的最經典的聚類演算法之一，它的特點之一就是隨機選取初始的聚類中心，如果選取的中心點不同，聚類結果就可能產生很大的差異。K均值聚類演算法對初始中心點的依賴性，導致K均值演算法的聚類結果不穩定。在這種情況下，聚類集成應運而生，許多學者在這個領域進行了深入的研究。
聚類集成的目的在於結合不同聚類演算法的結果得到比單個聚類演算法更優的聚類。對聚類集體中的成員聚類的問題成為一致性函數問題，或叫做集成問題。很多學者證實通過聚類集成可以有效的提高像K均值聚類這些單一聚類演算法的准確性、魯棒性和穩定性.在現有的研究中，產生基聚類結果的方法有:
(1)使用同一種聚類演算法，每次運行使用不同的參數和隨機初始化；
(2)使用不同的聚類演算法，如K均值產生多個不同的聚類;
(3)對數據集的子集聚類，子集通過不同采樣像bagging、Sub-sampling等方法獲得；
(4)在數據集的不同特徵子集或在數據集的不同子空間的投影上聚類得到不同聚類結果構成聚類集體。我們的方法主要是對第四種聚類集成問題進行了深入研究，在數據集的不同子集上進行集成分析。對於高維數據來說，數據點為單位劃分仍存在維數災難的問題，維數災難可能會引發這種現象，一個給定數據點與離它最近點的距離比與離它最遠的數據點的距離近，所以我們引入同樣的數據點但基於不同的特徵子集就可能會避免這種問題。生成基聚類結果以後就是設計一致性函數對聚類結果集成，就是將聚類成員進行合並，得到一個統一的聚類結果。目前存在很多一致性函數，常用的有投票法、超圖劃分、基於共協矩陣的證據積累、概率積累等等，我們在文章中用了文獻[1]中的方法，它是一種基於鏈接的方法。常規的集成方法往往基於一個由基聚類結果即這些數據基聚類結果內部的關系生成，忽略了這些結果之間的關系，所以Iam-on等利用簇之間的相似度來精煉集成信息矩陣。在高維數據中，我們將數據集的局部特徵子集用作聚類成員與基於鏈接的集成聚類方法有效結合，解決了高維數據進行集成聚類的問題。
本文組織如下：第2節對聚類集成做了一個概述，並針對於高維數據這一特殊數據集提出了自己的集成聚類方法。第3節是本文的核心部分，它講述了對特徵進行分層抽樣，並基於信息增益抽取出比較重要的具有代表意義的局部特徵子集的過程，此外對傳統的K均值演算法的具體過程進行了簡要的描述，然後引出了分層抽樣的概念，用分層抽樣的思想確定我們選擇的特徵的數目，最後給出了信息增益的定義，通過這個指標最終確定我們在每一個聚類簇中選擇的特徵；最後把我們前面的工作抽取局部特徵子集與基於鏈接的方法結合起來形成了自己的演算法描述；第4節首先對8個實際數據集包括文本、圖像、基因數據進行描述，然後在這八個數據集上比較和分析了我們的方法(SSLB)和傳統K均值演算法和基於鏈接的聚類集成演算法(LB)在四個聚類評價標准上的聚類性能；第5節是對全文的總結。
相關工作
聚類集成概述
聚類分析是按照某種相似性測度將多維數據分割成自然分組或簇的過程。聚類演算法很多，但是沒有一個萬能的聚類演算法能用於任何聚類問題，其原因在自然分組概念的內在不明確性以及類可以有不同的形狀、大小、密度等，這個在高維數據中的問題更為明顯，那些不相關的特徵和冗餘的特徵會使類結構更加模糊。單個聚類存在的這些問題，引發了學者們對聚類集成的研究。首先由Strehl[12]等人提出」聚類集成」的概念，而後Gionis[13]等人也給出該問題的描述。楊草原等給聚類集成下了一個定義，認為聚類集成就是利用經過選擇的多個聚類結果找到一個新的數據(或對象)劃分，這個劃分在最大程度上共享了所有輸入的聚類結果對數據或對象集的聚類信息。
聚類集成的符號化形式為：假設數據集X有n個實例，X={x1,x2,…,xn},首先對數據集X使用M次聚類演算法，得到M個聚類，?={?1,?2,…,?M}(下面稱為聚類成員)，其中?i(i=1,2,…,M)為第i次聚類演算法得到的聚類結果。然後用一致性函數T對?的聚類結果進行集成得到一個新的數據劃分?』[1].
摘 要

圖1聚類集成的基本過程。首先對數據集使用不同的聚類演算法得到不同的劃分，然後對這些劃分用一致性函數合並為一個聚類結果P』
由上面的聚類集成過程可知，對一個數據集進行聚類集成，主要有兩個階段，第一個階段是基聚類器對原始數據進行聚類，得到基聚類結果。第二個階段是基聚類結果集成，根據聚類集成演算法對前一個階段採集的基聚類結果進行處理，使之能夠最大限度地分享這些結果，從而得到一個對原始數據最好的聚類集成結果。
面向高維數據的集成聚類
信息時代互聯網成為最大的信息聚集地，像Web文檔、交易數據、基因表達數據、用戶評分數據等等，這些成為聚類分析的主要研究對象，而這些數據的維度成千上萬，甚至更高，這給聚類分析帶來了極大的挑戰。高維數據的聚類集成面臨更多的問題。
傳統的集成學習的第一步是產生多個基聚類結果，這一階段是對數據集或者其子集反復進行聚類演算法。現有的方法主要有：使用一個聚類演算法，每次運行設置不同的參數和隨機初始化；使用不同的聚類演算法；對數據集的子集進行聚類；將數據集的特徵空間投影到數據子空間。基聚類結果生成以後就開始對基聚類結果進行集成。一致性函數是一個函數或者是一個方法，它將聚類成員進行集成，得到一個統一的聚類結果。目前存在許多一致性函數，它大致可以分為:
(1)基於成對相似性的方法，它主要考慮的是所有的數據點對的關系的重現、
(2)基於超圖劃分的方法和(3)基於特徵的方法，它是把聚類的集成轉換為類標的集成。
針對高維數據的特點，我們選擇基於相似性的方法對聚類結果進行集成，凝聚層次聚類演算法是最經典的基於相似性方法，我們用了文獻中的方法，他把SL凝聚聚類演算法用來生成最終的劃分。但是基於成對相似度的集成的過程都是一個比較粗糙的過程，集成的結果往往基於一個由基聚類結果即這些數據劃分內部的關系生成，忽略了這些劃分結果之間的關系，所以它使用了Iam-on[17]等利用簇之間的相似度來精煉集成信息矩陣，實驗證明這種方法在很多數據集上表現很好，不僅增強了聚類穩定性也改善了聚類性能。由於我們研究的對象是高維數據，考慮到需要聚類的對象的維度很大，對完整的對象聚類一定會增加聚類演算法的運行開銷。這對基於鏈接的方法性能有所影響，因此，我們考慮對特徵空間的局部特徵子集進行聚類得到結果。經過上面的分析，我們引出自己的方法。我們對其中的基本步驟進行細化，我們的方法示意圖如下：

我們方法的示意圖，對聚類集成的過程進行了細化，描述了每一個過程的輸入和輸出
我們的方法就是針對高維數據的特點，對傳統的聚類集成進行了一些改進，我們首先用前面提到的K均值演算法對特徵進行聚類，然後用信息增益來衡量不同簇中的特徵的重要程度，而每個特徵簇中的所抽取特徵的數目nh由上面stratifiedsampling[18]的方法得到，最後利用信息增益選擇top(nh)的特徵。根據上述方法對特徵進行降維，得到了最具代表的數據子集。數據子集的生成，變換K均值演算法的k值，取k=2,3…√N(N為數據點的數目)生成不同的具有差異的數據子集，然後沿用[1]中的方法進行聚類集成，最後把這√N-2次的聚類結果進行最後一次集成得到我們最終的聚類結果。基於局部特徵子集的生成方法內容在下一章詳細講述。
基於局部特徵的數據子集生成方法
集成時使用哪種方法產生聚類成員一般從兩個方面來考慮，一個是集成者的目的，一個是數據集的結構。在機器學習的實際應用中，我們面對的絕大多數都是高維數據。數據集的特徵數量往往較多，可能存在不相關的特徵，特徵之間可能存在相互依賴，容易導致分析特徵、訓練模型的時間變長，甚至引發「維度災難」，模型復雜推廣能力下降。所以我們採用基於局部特徵的數據子集生成方法。圖3是我們生成局部特徵的數據子集的示意圖：

Fig. 3 The basic process of the generation of feature subset
首先我們用傳統的K均值演算法對數據集的特徵進行聚類，然後對於不同的特徵簇我們用信息增益來衡量它的重要性，不同的特徵簇中我們應該篩選多少特徵簇呢？分層抽樣很好的解決了這個問題，分層抽樣的思想是計算每個實例之間的相關性(用標准差、方差來衡量)，它認為類中的實例相關性比較大的可以選擇較多的樣本來代替當前類，類中相關性較小的就少選擇一些實例來代替當前類的樣本，根據分層抽樣中計算出的特徵簇的數目再利用信息增益這種衡量重要性的標准進行篩選後就得到了局部的特徵子集。下面具體論述基於局部特徵的數據子集生成方法中的關鍵技術。
k均值演算法
K均值演算法[5]是MacDueen提出的一個著名的聚類學習演算法。它根據相似度距離迭代的更新向量集的聚類中心，當聚類中心不再變化或者滿足某些停止條件，則停止迭代過程得到最終的聚類結果。K均值演算法的具體步驟為：
(1) 隨機選擇k個數據項作為聚類中心；
(2) 根據相似度距離公式，將數據集中的每一項數據分配到離他最近的聚類中去；
(3) 計算新的聚類中心；
(4) 如果聚類中心沒有發生改變，演算法結束；否則跳轉到第(2)步.
我們使用K均值演算法對數據集的特徵進行聚類，我們通過選取不同的k值進行特徵聚類，然後用後面的分層抽樣進行選擇得到差異度比較明顯的局部特徵的數據子集作為後面的聚類集成的輸入。
信息增益
對特徵進行聚類後得到多個特徵團，如何對它們進行特徵選擇，如何度量特徵團中的特徵的重要程度是我們面臨的問題。信息增益是資訊理論中的一個重要概念，它被廣泛應用在機器學習、數據挖掘領域，計算信息增益是針對一個特徵項而言的，它通過統計某一個特徵項t在類別C中出現與否的實例數來計算特徵項t對類別C的信息增益，定義為：

其中P(ci)表示ci類實例在數據集中出現的概率，p(t)表示數據集中包含特徵項t的實例數，p(ci|t)表示實例包含特徵項t時屬於ci類的條件概率，p(t ? )表示數據集中不包含特徵項t的實例數，p(c_i |t ? )表示實例不包含特徵項t時屬於ci類的概率，m為類別數。信息增益考慮特徵與類別信息的相關程度，認為信息增益值越大，其貢獻越大。我們的方法採用信息增益來度量特徵簇中的特徵的重要程度。
分層抽樣（Stratified sampling）
在對特徵進行聚類後對特徵進行選擇，我們採用信息增益來度量每個特徵簇中的特徵的重要程度。但是每個特徵簇我們選擇多少個特徵比較合適，這是分層抽樣解決的問題。抽樣的目的是在不影響聚類效果的情況下在已經分好或者聚好類的實例中，從每個類中抽取部分的樣本來代替整個類。Stratifiedsampling[18]方法遵循的原則是：計算每個實例之間的相關性(用標准差、方差來衡量)，我們認為類中的實例相關性比較大的可以選擇較小的樣本來代替當前類，類中相關性較小的就多選擇一些實例來代替當前類的樣本。這個方法就是確定每個類中篩選的實例的數目。此方法中每個類的樣本數目為：

其中nh是第h類應該抽取的實例數。n是預計抽取的總樣本數，Nh是在總體樣本中第h類的實例數，?h是第h類的標准差。通過(1)式我們就可以得到每個類中應該選擇的實例數目。提出這中抽樣方法的學者還對它的精確度、置信區間進行了分析，證明了它在不影響學習效果的情況下對可以對數據降維，提高學習效率。
在本文的方法中，我們先用前面提到的k均值演算法對特徵進行聚類，然後用信息增益來衡量不同簇中的特徵的重要程度，而每個特徵簇中的所抽取特徵的數目nh由上面stratifiedsampling的方法得到，最後利用信息增益選擇top(nh)的特徵。根據上述方法對特徵進行降維，得到了最具代表的數據子集，進行後面的數據集的聚類集成。
實驗結果與分析
實驗數據集
本文選用了8個數據集，包括文獻[1]中的兩個數據集：一個人工數據集Four-Gaussian[19]和一個被用來做基因數據聚類的真實數據集Leukemiadataset[20],另外就是六個真實數據集包括兩個文本數據集，兩個圖像數據集，兩個基因數據。表1給出了這些數據集的名稱以及數據的樣本、屬性、類別數量。
Table 1 Number of instance, features and classes of datasets

實驗分析
實驗中，本文對比了三種分類演算法包括傳統的k-means演算法，文獻[1]中的LB演算法以及我們實現的演算法SSLB。聚類性能通過下面四個評價指標來衡量，表2給出了這四個評價指標[1]的具體描述：
Table 2 Name of measures, formulas

K為聚類結果中簇的數目，nk是屬於第k個簇的數據點數目，d(xi,xj)是數據點xi和xj的距離，N是數據集中數據點的總數。n11是指在兩個劃分?』(正確的劃分)和?中出現在相同簇中的數據線對的個數，n00是指在兩個劃分?』、?中中出現在不同簇中的數據點對的個數，n01表示在劃分?中屬於不同簇在另一個劃分?』 中屬於同一個簇的數據點對數目，n10表示在劃分?』中屬於不同簇在另一個劃分?中屬於同一個簇的數據點對數目。
其中CP衡量的是在同一個簇中，所有數據點的數據點對的平均距離，越小越好。CA衡量的是與已經的類標相比，聚類正確的數據點數目，CA的范圍是從0到1，越大越好。RI這個指標衡量存在於相同和不同簇中的點對數目，RI的值從0到1，越大越好，AR也是越大越好。
本文對這8個數據集進行聚類集成，聚類成員由k均值對特徵聚類然後分層抽樣產生的局部特徵子集獲得，聚類中心的個數為數據集的類別數。為了增加實驗的可靠性，所有的實驗結果為10次結果的平均值。對比試驗採用原始的K均值聚類演算法、基於鏈接(LB)的方法，與我們實現的方法(SSLB)進行比較。在表3中，我們把關鍵值都突出的表現出來，在這8個數據集上，SSLB有在四個評價指標上都表現出比較大的優勢。
根據表四，比較集成前的K均值演算法、LB方法和SSLB方法，可以看出，在數據集Four-Gaussian上，SSLB在四種評價指標上都可以看出，其聚類性能明顯優於集成前的K均值演算法和LB聚類集成演算法。在兩種文本數據集Tr31和Tr41上，我們的方法優勢不是很明顯，但是在前兩個指標CP和CA上還是明顯好於集成前的K均值聚類，與LB演算法在這兩個指標上性能相當，而且在這兩個文本數據上，在RI和AR上集成前的K均值演算法與LB和SSLB方法相比都存在優勢。在兩個圖像數據集上，SSLB方法在CP這個評價指標上都遠遠好於集成前的K均值聚類演算法和LB演算法，但是在第二個評價指標和第三個評價指標上就比LB演算法差一點。在基因數據Colon上SSLB再第一個聚類評價指標上仍然存在很大的優勢，在聚類的准確率上，我們的方法與LB方法相當，但是明顯優於集成前的K均值演算法。在基因數據TOX-171上，我們的方法獲得了最好的聚類集成性能，在四個聚類評價指標上，都遠遠好於集成前的K均值演算法和LB演算法。
下面我們逐一在這四個聚類評價標准比較集成前的K均值演算法、SSLB演算法和LB演算法。圖四、圖五、圖六、以及圖七分別描述了集成前的K均值聚類、LB以及我們的方法SSLB在CP、CA、RI、AR上的表現。

聚類評價指標CP衡量的是在同一個簇中，所有數據點的數據點對的平均距離，越小越好。通過圖四可以看出，在所有數據集上，我們的演算法SSLB都存在很大的優勢，比集成前的K-means演算法以及LB演算法在CP這個指標上都好，此外還能看出CP在不同的數據集上的差異還是比較大的，在Four-Gaussian上明顯比其他數據集上差。

聚類評價指標CA衡量的是與已知的類標相比，聚類正確的數據點數目占總的數據點數目的比例，CA的范圍是從0到1，越大越好。從圖五可以看出我們的演算法在數據集Four-Gaussian、Tr41、Colon和TOX-171上的聚類精度比集成前的K均值演算法以及LB演算法都要好，但是在Tr31以及兩個圖像數據集上的優勢不大，這這個現象值得我們關注，也是我們接下來會研究的工作。

聚類評價指標RI衡量的是存在於相同和不同簇中的點對數目，RI的值從0到1，越大越好。從圖六可以看出我們的演算法在人工數據集Four-Gaussian以及幾個基因數據集上的表現比較突出、但是在其他數據集上就處於弱勢，而且可以看出集成前的K均值演算法在所有的數據集在RI上的表現都比較好。

聚類評價指標AR衡量的也是存在於相同和不同簇中的點對數目，AR的值從0到1，越大越好。從圖七可以看出我們的演算法SSLB在大多數數據集上存在著優勢，但是在數據集Leukemia、Tr41、Colon上的超過了集成前的K均值演算法和我們的演算法。這些現象和結果都是我們接下來的研究的重點。

綜上所述，在幾乎所有數據集上，在所有的聚類評價指標上我們的聚類集成演算法SSLB好於集成前K均值演算法的聚類效果，而且在大多數數據集上，我們的演算法比LB演算法存在一定的優勢，尤其是在基因數據上的表現較為突出。但是在有的數據集上優勢也不夠明顯，我們要繼續分析這些數據結構上的特點和我們的演算法可能存在的問題，這也是我們接下來研究的方向。
結 論
本文提出了一種面向高維數據的集成聚類方法。針對高維數據的特點，對傳統的聚類集成進行了一些改進，首先對特徵聚類然後基於分層抽樣抽取特徵子集，抽取到最具代表性的特徵子集後用基於鏈接的方法進行聚類集成。並在8個實際數據集包括文本、圖像、基因數據上進行實驗，在這8個數據集上分析和比較了我們的方法和集成前的K均值演算法以及基於鏈接的聚類集成演算法在四個評價標准上的聚類性能，能夠看出我們的演算法在聚類性能上有一定改善。

⑥ 用於數據挖掘的聚類演算法有哪些

一部專著的篇幅。即使是做綜述性的介紹，一篇三五十頁的論文也可以寫成了。所以我一直想怎麼能從頭到尾把這個問題logically串連起來。正好這段時間我在修改我做的交易策略裡面關於聚類的部分。就我的理解而言，如果想全面的了解聚類演算法並對其進行區別和比較的話，最好能把聚類的具體演算法放到整個聚類分析的語境中理解。那我接下來主要談談我的理解，就不搬弄教科書里的概念了。相似性衡量（similarity measurement）相似性衡量又可以細分為直接法和間接：直接法是直接求取input data的相似性，間接法是求取data中提取出的features的相似性。但無論是求data還是feature的相似性，方法都是這么幾種：距離。距離主要就是指Minkovski距離。這個名字雖然聽起來陌生，但其演算法就是Lp norm的演算法，如果是L1 norm，那就是絕對值/曼哈頓距離（Manhattan distance）；如果是L2 norm，那就是著名的歐式距離（Euclidean distance）了，也是應用最廣泛的；如果，supremum距離，好像也有叫切比雪夫距離的，但就很少有人用了。另外，還有Mahalanobis距離，目前來看主要應用於Gaussian Mixture Model（GMM），還有Lance&Williams距離等等，但幾乎沒見過求距離的時候會專門用這個的。相似系數。主要有夾角餘弦和相關系數。相關系數的應用也非常廣泛，其主要優勢是它不受原線性變換的影響，而且可以輕松地轉換為距離，但其運算速度要比距離法慢得多，當維數很高的時候。

⑦ 聚類演算法有哪些

聚類演算法有：劃分法、層次法、密度演算法、圖論聚類法、網格演算法、模型演算法。

1、劃分法

劃分法(partitioning methods)，給定一個有N個元組或者紀錄的數據集，分裂法將構造K個分組，每一個分組就代表一個聚類，K<N。使用這個基本思想的演算法有：K-MEANS演算法、K-MEDOIDS演算法、CLARANS演算法。

2、層次法

層次法(hierarchical methods)，這種方法對給定的數據集進行層次似的分解，直到某種條件滿足為止。具體又可分為「自底向上」和「自頂向下」兩種方案。代表演算法有：BIRCH演算法、CURE演算法、CHAMELEON演算法等。

3、密度演算法

基於密度的方法(density-based methods)，基於密度的方法與其它方法的一個根本區別是：它不是基於各種各樣的距離的，而是基於密度的。這樣就能克服基於距離的演算法只能發現「類圓形」的聚類的缺點。代表演算法有：DBSCAN演算法、OPTICS演算法、DENCLUE演算法等。

4、圖論聚類法

圖論聚類方法解決的第一步是建立與問題相適應的圖，圖的節點對應於被分析數據的最小單元，圖的邊（或弧）對應於最小處理單元數據之間的相似性度量。因此，每一個最小處理單元數據之間都會有一個度量表達，這就確保了數據的局部特性比較易於處理。圖論聚類法是以樣本數據的局域連接特徵作為聚類的主要信息源，因而其主要優點是易於處理局部數據的特性。

5、網格演算法

基於網格的方法(grid-based methods)，這種方法首先將數據空間劃分成為有限個單元（cell）的網格結構,所有的處理都是以單個的單元為對象的。代表演算法有：STING演算法、CLIQUE演算法、WAVE-CLUSTER演算法。

6、模型演算法

基於模型的方法(model-based methods)，基於模型的方法給每一個聚類假定一個模型，然後去尋找能夠很好的滿足這個模型的數據集。通常有兩種嘗試方向：統計的方案和神經網路的方案。

(7)聚類演算法的實例擴展閱讀：

聚類分析起源於分類學，在古老的分類學中，人們主要依靠經驗和專業知識來實現分類，很少利用數學工具進行定量的分類。隨著人類科學技術的發展，對分類的要求越來越高，以致有時僅憑經驗和專業知識難以確切地進行分類，於是人們逐漸地把數學工具引用到了分類學中，形成了數值分類學，之後又將多元分析的技術引入到數值分類學形成了聚類分析。聚類分析內容非常豐富，有系統聚類法、有序樣品聚類法、動態聚類法、模糊聚類法、圖論聚類法、聚類預報法等。

在商業上，聚類可以幫助市場分析人員從消費者資料庫中區分出不同的消費群體來，並且概括出每一類消費者的消費模式或者說習慣。它作為數據挖掘中的一個模塊，可以作為一個單獨的工具以發現資料庫中分布的一些深層的信息，並且概括出每一類的特點，或者把注意力放在某一個特定的類上以作進一步的分析；並且，聚類分析也可以作為數據挖掘演算法中其他分析演算法的一個預處理步驟。

⑧ 聚類演算法有哪幾種

聚類分析計算方法主要有： 層次的方法(hierarchical method)、劃分方法(partitioning method)、基於密度的方法(density-based method)、基於網格的方法(grid-based method)、基於模型的方法(model-based method)等。其中，前兩種演算法是利用統計學定義的距離進行度量。
k-means 演算法的工作過程說明如下：首先從n個數據對象任意選擇 k 個對象作為初始聚類中心;而對於所剩下其它對象，則根據它們與這些聚類中心的相似度(距離)，分別將它們分配給與其最相似的(聚類中心所代表的)聚類;然 後再計算每個所獲新聚類的聚類中心(該聚類中所有對象的均值);不斷重復這一過程直到標准測度函數開始收斂為止。一般都採用均方差作為標准測度函數. k個聚類具有以下特點：各聚類本身盡可能的緊湊，而各聚類之間盡可能的分開。
其流程如下：
(1)從 n個數據對象任意選擇 k 個對象作為初始聚類中心;
(2)根據每個聚類對象的均值(中心對象)，計算每個對象與這些中心對象的距離;並根據最小距離重新對相應對象進行劃分;
(3)重新計算每個(有變化)聚類的均值(中心對象);
(4)循環(2)、(3)直到每個聚類不再發生變化為止(標准測量函數收斂)。
優點： 本演算法確定的K個劃分到達平方誤差最小。當聚類是密集的，且類與類之間區別明顯時，效果較好。對於處理大數據集，這個演算法是相對可伸縮和高效的，計算的復雜度為 O(NKt)，其中N是數據對象的數目，t是迭代的次數。
缺點：
1. K 是事先給定的，但非常難以選定;
2. 初始聚類中心的選擇對聚類結果有較大的影響。

⑨ K-modes聚類演算法的實例應用

是一種聚類演算法，用於數據挖掘，演算法本身沒什麼研究的，當然實際應用中還要考慮好多問題。總的來說，kmean演算法對於一般的聚類任務還算可以。