數(shù)據(jù)挖掘（聚類分析）

數(shù)據(jù)挖掘對聚類算法的要求：可伸縮性（在小數(shù)據(jù)集上算法優(yōu)，同樣要求在大數(shù)據(jù)集上算法優(yōu)）、處理不同類型數(shù)據(jù)的能力、發(fā)現(xiàn)任意形狀簇的能力、輸入?yún)?shù)的領(lǐng)域知識最小化、處理噪聲數(shù)據(jù)的能力、對輸入數(shù)據(jù)順序的敏感、可解釋性和可用性、基于約束的聚類、處理高維數(shù)據(jù)的能力。

聚類方法的分類：

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

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

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

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

基于模型的方法：試圖將給定數(shù)據(jù)與某個數(shù)學(xué)模型達(dá)成最佳的擬合。代表算法EM算法

基于劃分的聚類算法：

基本k-means聚類算法：

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

算法k-means

輸入：數(shù)據(jù)集D，劃分簇的個數(shù)K

輸出：k個簇的集合

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

*repeat

for 數(shù)據(jù)集D中每個對象P do

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

end for

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

until 簇的中心不再發(fā)生變化

k-means算法通常采用誤差平方和作為衡量聚類質(zhì)量的目標(biāo)函數(shù)

k-means的優(yōu)點：描述容易、實現(xiàn)簡單、快速

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

二分k-means算法：

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

算法：二分k-means

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

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

repeat

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

進(jìn)行m次二分實驗

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

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

until 簇表中包含K個簇為止

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

k-medoids算法：

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

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

算法：k-medoids

輸入：數(shù)據(jù)集D，劃分簇的個數(shù)k

輸出：k的任意的集合

選擇k個不同的對象作為初始質(zhì)心

repeat

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

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

until  k個中心不再發(fā)生變化

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

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

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

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

CF-tree的構(gòu)造過程：

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

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

判斷當(dāng)前條目所在的葉子結(jié)點個數(shù)是否小于L，如果是，則插入，否則分裂該葉子結(jié)點。

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

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

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

算法：CURE

輸入：數(shù)據(jù)集D

輸出：簇的集合

從源數(shù)據(jù)集D中抽取隨機樣本S

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

對每個劃分進(jìn)行局部聚類

去除孤立點

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

用相應(yīng)的簇標(biāo)記來標(biāo)記數(shù)據(jù)

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

算法：ROCK

輸入：數(shù)據(jù)集D

輸出：簇的集合

隨機選擇一個樣本

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

將剩余的每個數(shù)據(jù)根據(jù)它與每個簇之間的連接，判斷它應(yīng)該歸屬的簇

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

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

算法：DBSCAN

輸入：數(shù)據(jù)集D，參數(shù)MinPts和Eps

輸出：簇的集合

首先將數(shù)據(jù)集D中所有的對象標(biāo)志為未處理狀態(tài)

for 數(shù)據(jù)集中的每個對象p do

if 對象p已經(jīng)歸納到某個簇或者已經(jīng)標(biāo)記為噪聲點  continue；

else   檢查對象p的領(lǐng)域；如果領(lǐng)域中包含的對象的個數(shù)小于minpts 標(biāo)記對象p為邊界點或者噪聲點

else 建立新的簇，將對象p標(biāo)記為核心點，將領(lǐng)域內(nèi)的結(jié)點歸入C類

for 領(lǐng)域中的未處理對象，求其領(lǐng)域，若領(lǐng)域中的結(jié)點未歸類，將其歸為C類

end

基于圖的聚類算法：

chameleon聚類算法：

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

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

步驟：

構(gòu)建稀疏圖：由數(shù)據(jù)集構(gòu)造成k-最鄰近圖集合G

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

合并子圖：合并關(guān)于相對互聯(lián)度和相對緊密度而言

重復(fù)上一步直到?jīng)]有子圖可以合并。

基于SNN的聚類算法：

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

找出所有點的k最近鄰

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

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

end

基于SNN的聚類算法：

構(gòu)造SNN相似度矩陣

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

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

最后將剩下的點聚類

另外SNN也可以和DBSCAN相結(jié)合

一趟聚類算法：

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

2，以這個對象構(gòu)造一個新的簇

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

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

5，更新簇的質(zhì)心

（注意閥值的選擇策略，對聚類的結(jié)果影響相當(dāng)明顯）

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

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

按照下面兩個步驟反復(fù)求精參數(shù)：

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

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

聚類的評價指標(biāo)：

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

外部評價標(biāo)準(zhǔn)：已經(jīng)存在一個人工分類的數(shù)據(jù)集，讓聚類的結(jié)果與其進(jìn)行比較。