分類與聚類演算法

『壹』 數據挖掘干貨總結（四）--聚類演算法

本文共計2680字，預計閱讀時長七分鍾

聚類演算法

 

一 、 本質

將數據劃分到不同的類里，使相似的數據在同一類里，不相似的數據在不同類里

 

二 、 分類演算法用來解決什麼問題

文本聚類、圖像聚類和商品聚類，便於發現規律，以解決數據稀疏問題

三 、 聚類演算法基礎知識

1. 層次聚類 vs 非層次聚類

– 不同類之間有無包含關系

2. 硬聚類 vs 軟聚類

– 硬聚類：每個對象只屬於一個類

– 軟聚類：每個對象以某個概率屬於每個類

3. 用向量表示對象

– 每個對象用一個向量表示，可以視為高維空間的一個點

– 所有對象形成數據空間（矩陣）

– 相似度計算：Cosine、點積、質心距離

4. 用矩陣列出對象之間的距離、相似度

5. 用字典保存上述矩陣（節省空間）

    D={(1,1):0,(1,2):2,(1,3):6...(5,5):0}

6. 評價方法

– 內部評價法（Internal Evalution）：

• 沒有外部標准，非監督式

• 同類是否相似，跨類是否相異

DB值越小聚類效果越好，反之，越不好

– 外部評價法（External Evalution）：

• 准確度（accuracy）: (C11+C22) / (C11 + C12 + C21 + C22)

• 精度（Precision）: C11 / (C11 + C21 )

• 召回（Recall）: C11 / (C11 + C12 )

• F值（F-measure）：

β表示對精度P的重視程度，越大越重視，默認設置為1，即變成了F值，F較高時則能說明聚類效果較好。

四 、 有哪些聚類演算法

主要分為 層次化聚類演算法 ， 劃分式聚類演算法 ， 基於密度的聚類演算法 ， 基於網格的聚類演算法 ， 基於模型的聚類演算法等 。

4.1 層次化聚類演算法

又稱樹聚類演算法，透過一種層次架構方式，反復將數據進行分裂或聚合。典型的有BIRCH演算法，CURE演算法，CHAMELEON演算法，Sequence data rough clustering演算法,Between groups average演算法,Furthest neighbor演算法,Neares neighbor演算法等。

凝聚型層次聚類 ：

先將每個對象作為一個簇，然後合並這些原子簇為越來越大的簇，直到所有對象都在一個簇中，或者某個終結條件被滿足。

演算法流程：

1. 將每個對象看作一類，計算兩兩之間的最小距離；

2. 將距離最小的兩個類合並成一個新類；

3. 重新計算新類與所有類之間的距離；

4. 重復2、3，直到所有類最後合並成一類。

特點：

1. 演算法簡單

2. 層次用於概念聚類（生成概念、文檔層次樹）

3. 聚類對象的兩種表示法都適用

4. 處理大小不同的簇

5. 簇選取步驟在樹狀圖生成之後

4.2 劃分式聚類演算法

預先指定聚類數目或聚類中心，反復迭代逐步降低目標函數誤差值直至收斂，得到最終結果。K-means,K-modes-Huang,K-means-CP,MDS_CLUSTER, Feature weighted fuzzy clustering，CLARANS等

經典K-means：

演算法流程：

1. 隨機地選擇k個對象，每個對象初始地代表了一個簇的中心；

2. 對剩餘的每個對象，根據其與各簇中心的距離，將它賦給最近的簇；

3. 重新計算每個簇的平均值，更新為新的簇中心；

4. 不斷重復2、3，直到准則函數收斂。

特點：

1.K的選擇

2.中心點的選擇

– 隨機

– 多輪隨機：選擇最小的WCSS

3.優點

– 演算法簡單、有效

– 時間復雜度：O(nkt)

4.缺點

– 不適於處理球面數據

– 密度、大小不同的聚類，受K的限制，難於發現自然的聚類

4.3 基於模型的聚類演算法

為每簇假定了一個模型，尋找數據對給定模型的最佳擬合，同一」類「的數據屬於同一種概率分布，即假設數據是根據潛在的概率分布生成的。主要有基於統計學模型的方法和基於神經網路模型的方法，尤其以基於概率模型的方法居多。一個基於模型的演算法可能通過構建反應數據點空間分布的密度函數來定位聚類。基於模型的聚類試圖優化給定的數據和某些數據模型之間的適應性。

SOM 神經網路演算法 ：

該演算法假設在輸入對象中存在一些拓撲結構或順序，可以實現從輸入空間(n維)到輸出平面(2維)的降維映射，其映射具有拓撲特徵保持性質,與實際的大腦處理有很強的理論聯系。

SOM網路包含輸入層和輸出層。輸入層對應一個高維的輸入向量，輸出層由一系列組織在2維網格上的有序節點構成，輸入節點與輸出節點通過權重向量連接。學習過程中，找到與之距離最短的輸出層單元，即獲勝單元，對其更新。同時，將鄰近區域的權值更新，使輸出節點保持輸入向量的拓撲特徵。

演算法流程：

1. 網路初始化，對輸出層每個節點權重賦初值；

2. 將輸入樣本中隨機選取輸入向量，找到與輸入向量距離最小的權重向量；

3. 定義獲勝單元，在獲勝單元的鄰近區域調整權重使其向輸入向量靠攏；

4. 提供新樣本、進行訓練；

5. 收縮鄰域半徑、減小學習率、重復，直到小於允許值，輸出聚類結果。

4.4 基於密度聚類演算法

只要鄰近區域的密度（對象或數據點的數目）超過某個閾值，就繼續聚類，擅於解決不規則形狀的聚類問題，廣泛應用於空間信息處理,SGC,GCHL，DBSCAN演算法、OPTICS演算法、DENCLUE演算法。

DBSCAN：

對於集中區域效果較好，為了發現任意形狀的簇，這類方法將簇看做是數據空間中被低密度區域分割開的稠密對象區域；一種基於高密度連通區域的基於密度的聚類方法，該演算法將具有足夠高密度的區域劃分為簇，並在具有雜訊的空間數據中發現任意形狀的簇。

4.5 基於網格的聚類演算法

    基於網格的方法把對象空間量化為有限數目的單元，形成一個網格結構。所有的聚類操作都在這個網格結構（即量化空間）上進行。這種方法的主要優點是它的處理 速度很快，其處理速度獨立於數據對象的數目，只與量化空間中每一維的單元數目有關。但這種演算法效率的提高是以聚類結果的精確性為代價的。經常與基於密度的演算法結合使用。代表演算法有STING演算法、CLIQUE演算法、WAVE-CLUSTER演算法等。 

『貳』 聚類演算法的演算法分類

很難對聚類方法提出一個簡潔的分類，因為這些類別可能重疊，從而使得一種方法具有幾類的特徵，盡管如此，對於各種不同的聚類方法提供一個相對有組織的描述依然是有用的，為聚類分析計算方法主要有如下幾種： 劃分法(partitioning methods)，給定一個有N個元組或者紀錄的數據集，分裂法將構造K個分組，每一個分組就代表一個聚類，K<N。而且這K個分組滿足下列條件：
（1） 每一個分組至少包含一個數據紀錄；
（2）每一個數據紀錄屬於且僅屬於一個分組（注意：這個要求在某些模糊聚類演算法中可以放寬）；
對於給定的K，演算法首先給出一個初始的分組方法，以後通過反復迭代的方法改變分組，使得每一次改進之後的分組方案都較前一次好，而所謂好的標准就是：同一分組中的記錄越近越好，而不同分組中的紀錄越遠越好。
大部分劃分方法是基於距離的。給定要構建的分區數k，劃分方法首先創建一個初始化劃分。然後，它採用一種迭代的重定位技術，通過把對象從一個組移動到另一個組來進行劃分。一個好的劃分的一般准備是：同一個簇中的對象盡可能相互接近或相關，而不同的簇中的對象盡可能遠離或不同。還有許多評判劃分質量的其他准則。傳統的劃分方法可以擴展到子空間聚類，而不是搜索整個數據空間。當存在很多屬性並且數據稀疏時，這是有用的。為了達到全局最優，基於劃分的聚類可能需要窮舉所有可能的劃分，計算量極大。實際上，大多數應用都採用了流行的啟發式方法，如k-均值和k-中心演算法，漸近的提高聚類質量，逼近局部最優解。這些啟發式聚類方法很適合發現中小規模的資料庫中小規模的資料庫中的球狀簇。為了發現具有復雜形狀的簇和對超大型數據集進行聚類，需要進一步擴展基於劃分的方法。
使用這個基本思想的演算法有：K-MEANS演算法、K-MEDOIDS演算法、CLARANS演算法； 層次法(hierarchical methods)，這種方法對給定的數據集進行層次似的分解，直到某種條件滿足為止。具體又可分為「自底向上」和「自頂向下」兩種方案。
例如，在「自底向上」方案中，初始時每一個數據紀錄都組成一個單獨的組，在接下來的迭代中，它把那些相互鄰近的組合並成一個組，直到所有的記錄組成一個分組或者某個條件滿足為止。
層次聚類方法可以是基於距離的或基於密度或連通性的。層次聚類方法的一些擴展也考慮了子空間聚類。層次方法的缺陷在於，一旦一個步驟（合並或分裂）完成，它就不能被撤銷。這個嚴格規定是有用的，因為不用擔心不同選擇的組合數目，它將產生較小的計算開銷。然而這種技術不能更正錯誤的決定。已經提出了一些提高層次聚類質量的方法。
代表演算法有：BIRCH演算法、CURE演算法、CHAMELEON演算法等； 基於密度的方法(density-based methods)，基於密度的方法與其它方法的一個根本區別是：它不是基於各種各樣的距離的，而是基於密度的。這樣就能克服基於距離的演算法只能發現「類圓形」的聚類的缺點。
這個方法的指導思想就是，只要一個區域中的點的密度大過某個閾值，就把它加到與之相近的聚類中去。
代表演算法有：DBSCAN演算法、OPTICS演算法、DENCLUE演算法等； 基於網格的方法(grid-based methods)，這種方法首先將數據空間劃分成為有限個單元（cell）的網格結構,所有的處理都是以單個的單元為對象的。這么處理的一個突出的優點就是處理速度很快，通常這是與目標資料庫中記錄的個數無關的，它只與把數據空間分為多少個單元有關。
代表演算法有：STING演算法、CLIQUE演算法、WAVE-CLUSTER演算法； 基於模型的方法(model-based methods)，基於模型的方法給每一個聚類假定一個模型，然後去尋找能夠很好的滿足這個模型的數據集。這樣一個模型可能是數據點在空間中的密度分布函數或者其它。它的一個潛在的假定就是：目標數據集是由一系列的概率分布所決定的。
通常有兩種嘗試方向：統計的方案和神經網路的方案。

『叄』 聚類演算法和分類演算法有什麼區別么

聚類是未知結果會有多少類的，即可能聚成10個類也可能聚成100個類，只是根據某些相似性條件把數據聚合在一起，當然也有讓用戶自定義類數目的聚類演算法，但這個數目也不好定的。分類是已知一共有多少類，並明確知道該類的特點，然後把未知的按一定規則分到某一個類中
聚類聚類的數據集要比較多，這樣才有東西聚成一堆一堆的。分類可以多可以少，當然數據量大才能很好地說明分類演算法的優異。但實際上分類演算法在確定某些規則後，你可以只有一個未知的數據也可以把它分到某一個類別當中，但聚類如果只有一個未知的數據怎麼聚啊。

『肆』 機器學習中分類與聚類的本質區別

機器學習中分類與聚類的本質區別
機器學習中有兩類的大問題，一個是分類，一個是聚類。
在我們的生活中，我們常常沒有過多的去區分這兩個概念，覺得聚類就是分類，分類也差不多就是聚類，下面，我們就具體來研究下分類與聚類之間在數據挖掘中本質的區別。
分類
分類有如下幾種說法，但表達的意思是相同的。
分類（classification）:分類任務就是通過學習得到一個目標函數f，把每個屬性集x映射到一個預先定義的類標號y中。
分類是根據一些給定的已知類別標號的樣本，訓練某種學習機器（即得到某種目標函數），使它能夠對未知類別的樣本進行分類。這屬於supervised learning（監督學習）。
分類：通過學習來得到樣本屬性與類標號之間的關系。
用自己的話來說，就是我們根據已知的一些樣本（包括屬性與類標號）來得到分類模型（即得到樣本屬性與類標號之間的函數），然後通過此目標函數來對只包含屬性的樣本數據進行分類。
分類演算法的局限
分類作為一種監督學習方法，要求必須事先明確知道各個類別的信息，並且斷言所有待分類項都有一個類別與之對應。但是很多時候上述條件得不到滿足，尤其是在處理海量數據的時候，如果通過預處理使得數據滿足分類演算法的要求，則代價非常大，這時候可以考慮使用聚類演算法。
聚類
聚類的相關的一些概念如下
而聚類指事先並不知道任何樣本的類別標號，希望通過某種演算法來把一組未知類別的樣本劃分成若干類別，聚類的時候，我們並不關心某一類是什麼，我們需要實現的目標只是把相似的東西聚到一起，這在機器學習中被稱作 unsupervised learning （無監督學習）
通常，人們根據樣本間的某種距離或者相似性來定義聚類，即把相似的（或距離近的）樣本聚為同一類，而把不相似的（或距離遠的）樣本歸在其他類。
聚類的目標：組內的對象相互之間時相似的（相關的），而不同組中的對象是不同的（不相關的）。組內的相似性越大，組間差別越大，聚類就越好。
分類與聚類的比較
聚類分析是研究如何在沒有訓練的條件下把樣本劃分為若干類。
在分類中，對於目標資料庫中存在哪些類是知道的，要做的就是將每一條記錄分別屬於哪一類標記出來。
聚類需要解決的問題是將已給定的若干無標記的模式聚集起來使之成為有意義的聚類，聚類是在預先不知道目標資料庫到底有多少類的情況下，希望將所有的記錄組成不同的類或者說聚類，並且使得在這種分類情況下，以某種度量（例如：距離）為標準的相似性，在同一聚類之間最小化，而在不同聚類之間最大化。
與分類不同，無監督學習不依賴預先定義的類或帶類標記的訓練實例，需要由聚類學習演算法自動確定標記，而分類學習的實例或數據樣本有類別標記。
要說明內容
因為最近在研究者兩種演算法，也就剛好用來說一下分類和聚類不同的演算法。
SVM與二分K均值演算法的區別之一：支持向量機（SVM）是一種分類演算法，二分k均值演算法屬於一種聚類演算法。
在《數據挖掘導論（完整版）》這本書第306頁中有這樣一句話：聚類可以看做一種分類，它用類標號創建對象的標記，然而只能從數據導出這些標號。相比之下，前面所說的分類是監督分類（supervisedclassification）:即使用有類標號已知的對象開發的模型，對新的、無標記的對象賦予類標號。為此，有時稱聚類分析為非監督分類（unsupervised classification）。在數據挖掘中，不附加任何條件使用術語分類時，通常是指監督分類。
因此，SVM與二分K均值演算法的區別之一：支持向量機（SVM）是一種監督分類演算法，二分k均值演算法屬於一種非監督分類演算法。

『伍』 聚類演算法有哪些分類

聚類演算法的分類有：

1、劃分法

劃分法(partitioning methods)，給定一個有N個元組或者紀錄的數據集，分裂法將構造K個分組，每一個分組就代表一個聚類，K小於N。而且這K個分組滿足下列條件：

（1） 每一個分組至少包含一個數據紀錄；

（2）每一個數據紀錄屬於且僅屬於一個分組（注意：這個要求在某些模糊聚類演算法中可以放寬）；

2、層次法

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

例如，在「自底向上」方案中，初始時每一個數據紀錄都組成一個單獨的組，在接下來的迭代中，它把那些相互鄰近的組合並成一個組，直到所有的記錄組成一個分組或者某個條件滿足為止。

3、密度演算法

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

4、圖論聚類法

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

5、網格演算法

基於網格的方法(grid-based methods)，這種方法首先將數據空間劃分成為有限個單元（cell）的網格結構,所有的處理都是以單個的單元為對象的。這么處理的一個突出的優點就是處理速度很快，通常這是與目標資料庫中記錄的個數無關的，它只與把數據空間分為多少個單元有關。

代表演算法有：STING演算法、CLIQUE演算法、WAVE-CLUSTER演算法；

6、模型演算法

基於模型的方法(model-based methods)，基於模型的方法給每一個聚類假定一個模型，然後去尋找能夠很好的滿足這個模型的數據集。這樣一個模型可能是數據點在空間中的密度分布函數或者其它。它的一個潛在的假定就是：目標數據集是由一系列的概率分布所決定的。

通常有兩種嘗試方向：統計的方案和神經網路的方案。

(5)分類與聚類演算法擴展閱讀：

聚類演算法的要求：

1、可伸縮性

許多聚類演算法在小於 200 個數據對象的小數據集合上工作得很好；但是，一個大規模資料庫可能包含幾百萬個對象，在這樣的大數據集合樣本上進行聚類可能會導致有偏的結果。

我們需要具有高度可伸縮性的聚類演算法。

2、不同屬性

許多演算法被設計用來聚類數值類型的數據。但是，應用可能要求聚類其他類型的數據，如二元類型(binary)，分類/標稱類型（categorical/nominal），序數型（ordinal）數據，或者這些數據類型的混合。

3、任意形狀

許多聚類演算法基於歐幾里得或者曼哈頓距離度量來決定聚類。基於這樣的距離度量的演算法趨向於發現具有相近尺度和密度的球狀簇。但是，一個簇可能是任意形狀的。提出能發現任意形狀簇的演算法是很重要的。

4、領域最小化

許多聚類演算法在聚類分析中要求用戶輸入一定的參數，例如希望產生的簇的數目。聚類結果對於輸入參數十分敏感。參數通常很難確定，特別是對於包含高維對象的數據集來說。這樣不僅加重了用戶的負擔，也使得聚類的質量難以控制。

5、處理「雜訊」

絕大多數現實中的資料庫都包含了孤立點，缺失，或者錯誤的數據。一些聚類演算法對於這樣的數據敏感，可能導致低質量的聚類結果。

6、記錄順序

一些聚類演算法對於輸入數據的順序是敏感的。例如，同一個數據集合，當以不同的順序交給同一個演算法時，可能生成差別很大的聚類結果。開發對數據輸入順序不敏感的演算法具有重要的意義。

『陸』 技術 | 文本聚類與分類

按照處理的對象和處理的方法不同，可將常見文本分類/聚類任務分為以下幾種：

① 文檔聚類： 把一組未知類別的文檔劃分為若干類別，例如將介紹奧運會的新聞都歸到某一類；

② 文檔分類： 給定一個文檔，將其劃分到預定義好的某一個類別中，例如將所有介紹奧運會的新聞都標記為「體育」；

③ 詞彙聚類： 把一組未知類別的詞彙劃分為若干類別，例如將各種運動的項目名稱（詞彙）都歸為一類；

④ 詞彙分類： 給定一個詞彙，將其劃分到預定義好的某一個類別中，例如將籃球、足球等都比較為球類，將打獵、射箭等都標記為射擊。

要實現上述目的，通常有以下幾個核心問題要解決：

1. 特徵選擇

1.1 用什麼作為特徵項

用於表示文本的基本單位通常稱為文本的特徵或特徵項。特徵項必須滿足：能夠標識文本內容、能夠將目標文本與其他文本相區分、個數不能太多、特徵項分離要比較容易實現。在中文文本中可以採用字、詞或短語作為表示文本的特徵項。

相比較而言，詞比字具有更強的表達能力，而詞和短語相比，詞的切分難度比短語的切分難度小得多。因此，目前大多數中文文本分類系統都採用詞作為特徵項，稱作特徵詞。這些特徵詞作為文檔的中間表示形式，用來實現文檔與文檔、文檔與用戶目標之間的相似度計算 。

1.2 選取哪些作為特徵項

如果把所有的詞都作為特徵項，那麼特徵向量的維數將過於巨大，從而導致計算量太大，在這樣的情況下，要完成文本分類幾乎是不可能的。特徵提取的主要功能是在不損傷文本核心信息的情況下盡量減少要處理的單詞數，以此來降低向量空間維數，從而簡化計算，提高文本處理的速度和效率。

特徵選取的方式有2種：用映射或變換的方法把原始特徵變換為較少的新特徵（將原始特徵用新特徵表示）；從原始特徵中挑選出一些最具代表性的特徵（只保留部分原始特徵，不產生新特徵），即根據某個特徵評估函數計算各個特徵的評分值，然後按評分值對這些特徵進行排序，選取若干個評分值最高的作為特徵詞，常見的特徵評估函數包括TF-IDF、信息增益、互信息等。

2. 文本表示

2.1 如何表示文檔

為了讓計算機能夠「計算」文本，就需要我們將文本數據轉換成計算機可以處理的結構化數據。常見的文本表示模型有布爾模型、向量空間模型、統計主題模型等。其中，向量空間模型概念簡單，把對文本內容的處理簡化為向量空間中的向量運算，並且它以空間上的相似度表達語義的相似度，直觀易懂，目前應用最廣。

2.2 如何確立權重

一篇文檔有很多詞，有些詞表達的語義很重要，有些相對次要，那麼如何確定哪些重要？哪些次要呢？因此，需要進一步對每個詞的重要性進行度量。常見的確立詞彙權重的演算法有TF-IDF、詞頻法等。

3. 相似性計算

要實現文本的分類和聚類，需要設計一種演算法計算出文檔與文檔、詞彙與詞彙之間的相似性。

3.1 文檔相似性

設定我們要比較X和Y間的差異，它們都包含了N個維的特徵，即X=（x1, x2, x3, … xn），Y=（y1, y2, y3, … yn）。下面來看看主要可以用哪些方法來衡量兩者的差異，主要分為距離度量和相似度度量。

a. 距離度量

距離度量（Distance）用於衡量個體在空間上存在的距離，距離越遠說明個體間的差異越大。常見的距離有歐幾里得距離(Euclidean Distance)、明可夫斯基距離(Minkowski Distance)、曼哈頓距離(Manhattan Distance)、切比雪夫距離(Chebyshev Distance)、馬哈拉諾比斯距離(Mahalanobis Distance)。

b. 相似性度量

相似度度量（Similarity），即計算個體間的相似程度，與距離度量相反，相似度度量的值越小，說明個體間相似度越小，差異越大。常見的相似性度量有向量空間餘弦相似度(Cosine Similarity)、皮爾森相關系數(Pearson Correlation Coefficient)、Jaccard相似系數(Jaccard Coefficient)、調整餘弦相似度(Adjusted Cosine Similarity)。

歐氏距離是最常見的距離度量，而餘弦相似度則是最常見的相似度度量，很多的距離度量和相似度度量都是基於這兩者的變形和衍生，所以下面重點比較下兩者在衡量個體差異時實現方式和應用環境上的區別。下面藉助三維坐標系來看下歐氏距離和餘弦相似度的區別：

從圖上可以看出距離度量衡量的是空間各點間的絕對距離，跟各個點所在的位置坐標（即個體特徵維度的數值）直接相關；而餘弦相似度衡量的是空間向量的夾角，更加的是體現在方向上的差異，而不是位置。如果保持A點的位置不變，B點朝原方向遠離坐標軸原點，那麼這個時候餘弦相似度cosθ是保持不變的，因為夾角不變，而A、B兩點的距離顯然在發生改變，這就是歐氏距離和餘弦相似度的不同之處。

根據歐氏距離和餘弦相似度各自的計算方式和衡量特徵，分別適用於不同的數據分析模型：歐氏距離能夠體現個體數值特徵的絕對差異，所以更多的用於需要從維度的數值大小中體現差異的分析，如使用用戶行為指標分析用戶價值的相似度或差異；而餘弦相似度更多的是從方向上區分差異，而對絕對的數值不敏感，更多的用於使用用戶對內容評分來區分用戶興趣的相似度和差異，同時修正了用戶間可能存在的度量標准不統一的問題（因為餘弦相似度對絕對數值不敏感）。

3.2 詞彙相似性

目前我接觸的常見詞彙相似性的方法有：

a. 傳統圖情領域：基於共現頻次這一基本統計量衍生出來的，如association strength、inclusion index、Jaccard』s coefficient、Salton』s cosine（Ochiia系數）等；

b. 計算機領域：一是基於語義詞典的方法，即依據詞典分類體系挖掘所包含的詞義知識，常用的詞典包括Wordnet、Hownet等；二是基於語料庫的方法，這里的語料庫較為多元，例如網路預料、唐詩宋詞預料等；；三是進行詞向量化，如Word2vec。

4. 文本分類/聚類演算法

有了文本表示方法，又有了計算相似性的公式，下一步就可以在此基礎上討論文本分類/聚類的演算法了。

4.1 文本分類

醫生對病人進行診斷就是一個典型的分類過程，任何一個醫生都無法直接看到病人的病情，只能觀察病人表現出的症狀和各種化驗檢測數據來推斷病情，這時醫生就好比一個分類器，而這個醫生診斷的准確率，與他當初受到的教育方式（構造方法）、病人的症狀是否突出（待分類數據的特性）以及醫生的經驗多少（訓練樣本數量）都有密切關系。

分類器是對樣本進行分類的方法的統稱，包含決策樹、邏輯回歸、樸素貝葉斯、神經網路等演算法。舉個例子：假如你想區分小明是好學生還是壞學生，那麼區分「好學生」和「壞學生」就是一個分類任務。

4.1.1 K最鄰近

「別和其他壞學生在一起，否則你也會和他們一樣。」 —— 家長

主要思想是通過離待預測樣本最近的K個樣本的類別來判斷當前樣本的類別。從K最近鄰演算法的角度來看，就是讓目標樣本與其他正樣本距離更近、與其他負樣本距離更遠，從而使得其近鄰中的正樣本比例更高，更大概率被判斷成正樣本。

4.1.2 樸素貝葉斯

「根據以往抓獲的情況來看，十個壞學生有九個愛打架。」 —— 教導主任

「十個壞學生有九個愛打架」就意味著「壞學生」打架的概率P(打架|壞學生)=0.9，假設根據訓導處歷史記錄壞學生占學生總數P(壞學生)=0.1、打架發生的概率是P(打架)=0.09，那麼這時如果發生打架事件，就可以通過貝葉斯公式判斷出當事學生是「壞學生」的概率P(壞學生|打架)=P(打架|壞學生)×P(壞學生)÷P(打架)=1.0，即該學生100%是「壞學生」。

4.1.3 決策樹

「先看抽不抽煙，再看染不染頭發，最後看講不講臟話。」 ——社區大媽

假設「抽煙」、「染發」和「講臟話」是社區大媽認為的區分「好壞」學生的三項關鍵特徵，那麼這樣一個有先後次序的判斷邏輯就構成一個決策樹模型。在決策樹中，最能區分類別的特徵將作為最先判斷的條件，然後依次向下判斷各個次優特徵。決策樹的核心就在於如何選取每個節點的最優判斷條件，也即特徵選擇的過程。

而在每一個判斷節點，決策樹都會遵循一套IF-THEN的規則：

IF 「抽煙」 THEN -> 「壞學生」 ELSE IF 「染發」 THEN -> 「壞學生」 ELSE IF 「講臟話」 THEN -> 「壞學生」 ELSE -> 「好學生」

4.1.4 邏輯回歸

「上課講話扣1分，不交作業扣2分，比賽得獎加5分。」 ——紀律委員

我們稱邏輯回歸為一種線性分類器，其特徵就在於自變數x和因變數y之間存在類似y=ax+b的一階的、線性的關系。假設「上課講話」、「不交作業」和「比賽得獎」的次數分別表示為x1、x2、和x3，且每個學生的基礎分為0，那麼最終得分y=-1 x1-2 x2+5*x3+0。其中-1、-2和5分別就對應於每種行為在「表現好」這一類別下的權重。

對於最終得分y，邏輯回歸還通過Sigmoid函數將其變換到0-1之間，其含義可以認為是當前樣本屬於正樣本的概率，即得分y越高，屬於「表現好」的概率就越大。也就是說，假如紀律委員記錄了某位同學分別「上課講話」、「不交作業」和「比賽得獎」各一次，那麼最終得分y=-2-1+5=2，而對2進行Sigmoid變換後約等於0.88，即可知該同學有88%的概率為「好學生」。

4.1.5 支持向量機

「我想個辦法把表現差的學生都調到最後一排。」 ——班主任

支持向量機致力於在正負樣本的邊界上找到一條分割界線（超平面），使得它能完全區分兩類樣本的同時，保證劃分出的間隔盡量的大。如果一條分割界線無法完全區分（線性不可分），要麼加上鬆弛變數進行適當的容忍，要麼通過核函數對樣本進行空間上的映射後再進行劃分。對於班主任來講，調換學生們的座位就相當於使用了核函數，讓原本散落在教室里的「好」、「壞」學生從線性不可分變得線性可分了。

4.2 文本聚類

4.2.1 基於分層的聚類

hierarchical methods： 對數據集進行逐層分解，直到滿足某種條件為止。可分為「自底向上」和「自頂向下」兩種。例如「自底向上」指初始時每個數據點組成一個單獨的組，在接下來的迭代中，按一定的距離度量將相互鄰近的組合並成一個組，直至所有的記錄組成一個分組或者滿足某個條件為止。代表演算法有：BIRCH，CURE，CHAMELEON等。自底向上的凝聚層次聚類如下圖所示。

4.2.2 基於劃分的聚類

partitioning methods： 給定包含N個點的數據集，劃分法將構造K個分組，每個分組代表一個聚類，這里每個分組至少包含一個數據點，每個數據點屬於且僅屬於一個分組。對於給定的K值，演算法先給出一個初始的分組方法，然後通過反復迭代的方法改變分組，使得每一次改進之後的分組方案較前一次好，這里好的標准在於同一組中的點越近越好，不同組中的點越遠越好。代表演算法有：K-means，K-medoids，CLARANS。K-means聚類過程圖解如下：

4.2.3 基於密度的聚類

density-based methods： 基於密度的方法的特點是不依賴於距離，而是依賴於密度，從而克服基於距離的演算法只能發現「球形」聚簇的缺點。其核心思想在於只要一個區域中點的密度大於某個閾值，就把它加到與之相近的聚類中去。代表演算法有：DBSCAN，OPTICS，DENCLUE，WaveCluster。DBSCAN的聚簇生成過程的簡單理解如下圖。

4.2.3 基於網格的聚類

gird-based methods： 這種方法通常將數據空間劃分成有限個單元的網格結構，所有的處理都是以單個的單元為對象。這樣做起來處理速度很快，因為這與數據點的個數無關，而只與單元個數有關。代表演算法有：STING，CLIQUE，WaveCluster。基於Clique的聚類過程可直觀如下圖進行理解。

4.2.4 基於模型的聚類

model-based methods： 基於模型的方法給每一個聚類假定一個模型，然後去尋找能很好的擬合模型的數據集。模型可能是數據點在空間中的密度分布函數或者其它。這樣的方法通常包含的潛在假設是：數據集是由一系列的潛在概率分布生成的。通常有兩種嘗試思路：統計學方法和神經網路方法。其中，統計學方法有COBWEB演算法、GMM(Gaussian Mixture Model)，神經網路演算法有SOM(Self Organized Maps)演算法。下圖是GMM過程的一個簡單直觀地理解。

4.2.5 基於圖論的聚類

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

聚類問題的研究不僅僅局限於上述的硬聚類，即每一個數據只能被歸為一類，模糊聚類也是聚類分析中研究較為廣泛的一個分支。模糊聚類通過隸屬函數來確定每個數據隸屬於各個簇的程度，而不是將一個數據對象硬性地歸類到某一簇中。目前已有很多關於模糊聚類的演算法被提出，如著名的FCM演算法等。

『柒』 數據分類和聚類有什麼區別

主要區別是，性質不同、目的不同、應用不同，具體如下：

一、性質不同

1、數據分類

數據分類就是把具有某種共同屬性或特徵的數據歸並在一起，通過其類別的屬性或特徵來對數據進行區別。為了實現數據共享和提高處理效率，必須遵循約定的分類原則和方法，按照信息的內涵、性質及管理的要求，將系統內所有信息按一定的結構體系分為不同的集合，從而使得每個信息在相應的分類體系中都有一個對應位置。

2、數據聚類

數據聚類是指根據數據的內在性質將數據分成一些聚合類，每一聚合類中的元素盡可能具有相同的特性，不同聚合類之間的特性差別盡可能大。

二、目的不同

1、數據分類

數據分類的目的是根據新數據對象的屬性，將其分配到一個正確的類別中。

2、數據聚類

聚類分析的目的是分析數據是否屬於各個獨立的分組，使一組中的成員彼此相似，而與其他組中的成員不同。

三、應用不同

1、數據分類

應用於統計學、計算機控制。

2、數據聚類

廣泛應用於機器學習，數據挖掘，模式識別，圖像分析以及生物信息等。

以上內容參考網路-數據分類、網路-數據聚類

『捌』 分類和聚類的區別及各自的常見演算法

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演算法；基於模型的方法)。