數據挖掘（聚類分析）

數據挖掘對聚類算法的要求：可伸縮性（在小數據集上算法優，同樣要求在大數據集上算法優）、處理不同類型數據的能力、發現任意形狀簇的能力、輸入參數的領域知識最小化、處理噪聲數據的能力、對輸入數據順序的敏感、可解釋性和可用性、基于約束的聚類、處理高維數據的能力。

聚類方法的分類：

基于劃分的方法：構建數據集的k個劃分，每個劃分表示一個聚類（每個劃分至少包含一個對象、每個對象只屬于一個劃分（可相應變動））?；趧澐值姆椒榱诉_到全局的最優，可能要窮舉所有的可能化分，這種算法時間復雜度太大。因此采用兩種比較流行的啟發式算法kmeans（每個簇用該簇中的平均值代替）kmedoids（每個簇用最接近中心的一個對象來表示）這些算法在小規模數據的應用上達到了一個很好的效果

層次方法：將數據對象組成一棵聚類樹（凝聚層次和分裂層次）凝聚層次聚類和分裂層次聚類一個是自底向上合并相近的對象或者組，直到所有的組合合并為1個或者達到一個終止條件。分裂層次聚類就是一個相反的過程。層次聚類算法的缺陷在于：一旦一個步驟執行完畢，就不可以被撤銷。話外之意就是不能改正錯誤的決定。目前對于層次聚類算法提出了些改進的算法。層次聚類代表算法：BIRCH、CURE、ROCK算法

基于密度的算法：絕大部分劃分的方法都是基于對象之間的距離大小進行劃分。這些方法能夠發現球狀的簇，而在檢測任意形狀的簇上遇到了困難。就出現了基于密度的算法。主要思想：只要鄰近區域的密度超過某個閥值就繼續聚類，DBSCAN是一種具有代表性的基于密度的聚類算法

基于圖的聚類算法：基于圖的聚類算法，利用了圖的許多重要的性質和特性。代表算法chameleon和SNN

基于模型的方法：試圖將給定數據與某個數學模型達成最佳的擬合。代表算法EM算法

基于劃分的聚類算法：

基本k-means聚類算法：

算法流程：首先選擇k個對象，每個對象代表一個簇的初始均值或者中心；對剩余的每一個對象，根據其與各個簇中心的距離，將它指派到最近的簇，然后計算每個簇的新的均值，得到更新后的簇的中心；不斷的重復，知道準則函數收斂。（準則函數一般采用平方誤差）

算法k-means

輸入：數據集D，劃分簇的個數K

輸出：k個簇的集合

*從數據集D中任意選擇k個對象作為初始簇的中心

*repeat

for 數據集D中每個對象P do

計算對象P到K個簇中心的距離，將P指派到與其距離最近的簇

end for

計算每個簇中的對象的均值，更新簇的中心

until 簇的中心不再發生變化

k-means算法通常采用誤差平方和作為衡量聚類質量的目標函數

k-means的優點：描述容易、實現簡單、快速

k-means的缺點：算法中的k需要預先給定、算法對初始值的依賴很大（選擇不同的k值，會產生不同的結果）、當數據集很大的時候，算法的開銷很大、算法對噪聲點和離群點十分敏感，k-means算法只能發現球形的簇，算法只能用來處理數值型屬性

二分k-means算法：

思想：為了得到k個簇，將所有點的集合分裂成兩個簇，從中選擇一個繼續分裂，如此重復直到產生k個簇為止

算法：二分k-means

輸入：數據集D、劃分簇的個數k，每一次二分實驗的次數m

*初始化簇表，最初的簇表只包含一個包含所有樣本組成的簇

repeat

按照某種方法從中選擇一個簇

進行m次二分實驗

使用基本的k-means對其進行聚類，劃分成為兩個子簇

從這m次二分實驗中選擇兩個SSE總和最小的簇，將這兩個簇加入到簇表中

until 簇表中包含K個簇為止

k-means算法的擴展：
k-means中距離的計算時基于數值型的數據，沒有明確分類型的數據進行如何的操作。在k-means算法中對分類屬性的處理一般有3種：將分類型的屬性轉化為數值型的屬性。例如變量x有類別a，b，c，那么就采用三個數值共同表示，當x為a類別表示為100。采用適用于純分類型變量的k-modes或者適用于混合屬性的k-prototypes算法。其中k-modes采用眾數來代替基本k-means中的均值。兩者結合在一起就形成了k-prototypes算法。第三種是采用k-summary算法

k-medoids算法：

思想：不和基本k-means算法類似采用均值當中簇的中心，它采用距離中心最近的一個對象作為簇的中心

算法的基本過程：首先為每個簇隨機選擇一個代表對象，其余數據對象根據與代表對象的距離大小劃分到最近的一個簇中，然后反復的用非代表對象代替代表對象，以改進聚類的質量。聚類的質量用一個代價函數來估算，如果替換后的平方誤差減去替換前的平方誤差，為負值的時候則進行替換，否則就不進行替換

算法：k-medoids

輸入：數據集D，劃分簇的個數k

輸出：k的任意的集合

選擇k個不同的對象作為初始質心

repeat

把剩余對象按照距離劃分到最近的簇中

計算選擇一個非中心對象s代替一個中心對象的代價s，如果s<0則進行替換，形成新的k個中心

until  k個中心不再發生變化

層次聚類算法：凝聚層次和分裂層次（思想比較簡單）

改進的層次聚類算法：BIRCH算法（層次聚類算法和其他聚類算法的結合，層次聚類算法用于初始微聚類，其他方法用于后續的宏聚類）克服了凝聚聚類算法的不可伸縮和不可撤銷的缺點。另外BIRCH算法采用CF和CF-Tree來節省I\O和內存開銷、其核心是聚類特征CF和聚類特征樹

一個聚類特征CF為一個三元組（N，LS，SS）N為結點的個數，LS為結點的線性和，SS為數據的平方和。CF滿足可加性

CF-tree是一個高度平衡樹，具有兩個參數分支因子和閥值T（分支因子包含非葉子結點的最大條目數和葉子結點的最大條目數）樹的結構類似與B+樹

CF-tree的構造過程：

從根結點開始遞歸往下，計算當前條目與要插入的數據點的距離，尋找最小距離的那個路徑，直到找到與該結點最接近的葉子結點

比較計算出的距離是否小于閥值T，如果小于則直接吸收，否則執行下面步驟

判斷當前條目所在的葉子結點個數是否小于L，如果是，則插入，否則分裂該葉子結點。

BIRCH算法分為四個階段：掃描數據集，根據給定的初始閥值T建立一個聚類特征樹，通過提升閥值T重建CF樹，第三四階段利用全局聚類函數，對已有的CF樹進行聚類，來獲取更好的結果。

CURE算法：通過多個代表點來表示一個簇，提高算法對任意簇的能力。

CURE算法思想：采用凝聚聚類，在最開始的時候，每個對象屬于獨立的簇。然后從最相似的對象進行合并，為了能夠處理大數據，CURE采用隨機抽樣和分割的技術來降低數據的量。CURE采用多個對象代表一個簇，并通過收縮因子來調整簇的形狀。消除異常值的影響（分兩個階段完成，剛開始進行最相似對象合并，由于異常值的距離很大，所以其所在的類的結點數量增長很慢，接下來在聚類快要結束的時候，將增長慢的簇 當中異常值去掉）。CURE聚類完成后只包含樣本的數據，之后還得采取某種策略將非樣本的數據加入到聚類中

算法：CURE

輸入：數據集D

輸出：簇的集合

從源數據集D中抽取隨機樣本S

將樣本S劃分成大小相等的分組

對每個劃分進行局部聚類

去除孤立點

對局部的簇進行聚類，落在新形成的簇中的代表點根據用戶定義的一個收縮因子，向簇中心移動

用相應的簇標記來標記數據

ROCK算法：很多算法都是應用于數值型的數據，聚類依據為數據之間的距離。不能很好的應用于分類型數據。ROCK算法針對具有分類屬性的數據使用鏈接（兩個對象之間的共同的近鄰數目）這一個概念

算法：ROCK

輸入：數據集D

輸出：簇的集合

隨機選擇一個樣本

在樣本上用凝聚算法進行聚類，簇的合并是基于簇間的相似度進行（即來自不同簇而有相同鄰居的樣本數目）

將剩余的每個數據根據它與每個簇之間的連接，判斷它應該歸屬的簇

基于密度的聚類算法（DBSCAN算法）：

DBSCAN算法涉及的一些概念：EPs領域：給定對象半徑內的領域稱為該對象的Eps領域。MinPts：給定領域內包含點的最小數目；核心對象：如果對象的領域內至少包含了minPts個點，那么就稱這個對象為核心對象。邊界點：不是核心對象，但是落在某個核心對象的領域內，噪聲點；密度可達還有密度相連

算法：DBSCAN

輸入：數據集D，參數MinPts和Eps

輸出：簇的集合

首先將數據集D中所有的對象標志為未處理狀態

for 數據集中的每個對象p do

if 對象p已經歸納到某個簇或者已經標記為噪聲點  continue；

else   檢查對象p的領域；如果領域中包含的對象的個數小于minpts 標記對象p為邊界點或者噪聲點

else 建立新的簇，將對象p標記為核心點，將領域內的結點歸入C類

for 領域中的未處理對象，求其領域，若領域中的結點未歸類，將其歸為C類

end

基于圖的聚類算法：

chameleon聚類算法：

關鍵：確定合并哪兩個簇（用相對互連度和相對緊密度度量）

chameleon算法的三個關鍵步驟：稀疏化、圖劃分、子圖合并

步驟：

構建稀疏圖：由數據集構造成k-最鄰近圖集合G

多層圖劃分：通過一個多層圖劃分算法，將圖G劃分成大量的子圖，每個子圖代表一個簇

合并子圖：合并關于相對互聯度和相對緊密度而言

重復上一步直到沒有子圖可以合并。

基于SNN的聚類算法：

SNN即計算共享最近鄰相似度

找出所有點的k最近鄰

如果x和y不是相互在對方的最近鄰中 then Similarity(x,y)=0;

else  Similarity(x,y)=共享最近鄰個數

end

基于SNN的聚類算法：

構造SNN相似度矩陣

進行最近k鄰居的稀疏處理（根據某個閥值）并依此構造出最近鄰居圖，使得具有較強連接的樣本之間有鏈接

統計出所有樣本的鏈接強度，依此來確定核心點和噪聲點

最后將剩下的點聚類

另外SNN也可以和DBSCAN相結合

一趟聚類算法：

1，初始時，簇集合為空，讀入一個新的對象

2，以這個對象構造一個新的簇

3，讀入一個新的對象，計算對象與當前簇的距離，選擇最小的距離

4，若最小距離大于閥值，則轉到2，否則將其并入那個簇。

5，更新簇的質心

（注意閥值的選擇策略，對聚類的結果影響相當明顯）

基于模型的聚類算法（EM算法）：

對參數向量做初始估計：包括隨機選擇k個對象代表簇的中心以及估計其他參數

按照下面兩個步驟反復求精參數：

期望步：計算每個對象指派到類Ci的概率

最大化步：利用上一步得到的概率重新估計模型的參數

聚類的評價指標：

內部評價標準：主要通過計算內部的平均相似度簇間的平均相似度以及整體的平均相似度。理想的距離結果最小的簇內距離和最大的簇間距離。因此很多的距離評價標準都采用簇內和簇外的距離的比值來衡量

外部評價標準：已經存在一個人工分類的數據集，讓聚類的結果與其進行比較。