數(shù)據(jù)挖掘--聚類方法(1)

聚類就是將數(shù)據(jù)對象分組成多個(gè)類或者簇，劃分的原則是在同一個(gè)粗中的對象之間具有較高的相似度，而不同簇中的對象差別較大。屬于一種無指導(dǎo)的學(xué)習(xí)方法。

好的聚類算法應(yīng)該滿足以下幾個(gè)方面：

（1） 可伸縮型：無論對小數(shù)據(jù)量還是大數(shù)據(jù)量應(yīng)該都是有效的。

（2） 具有處理不同類型屬性的能力。

（3） 能夠發(fā)現(xiàn)任意形狀的聚類。

（4） 輸入?yún)?shù)對領(lǐng)域知識(shí)的弱依賴性

（5） 對于輸入記錄順序不敏感

（6） 能夠處理很多維度的數(shù)據(jù)，而不止是對3維左右的數(shù)據(jù)有效

（7） 處理噪聲數(shù)據(jù)的能力

（8） 基于約束的距離：既能找到滿足特定的約束，又具有良好聚類特性的數(shù)據(jù)分組

（9） 挖掘出來的信息是可理解的和可用的。

聚類分析主要在以下幾個(gè)方面應(yīng)用：

（1） 可以作為其他算法的預(yù)處理步驟

（2） 可以作為一個(gè)獨(dú)立的工具來獲得數(shù)據(jù)的分布情況

（3） 可以完成孤立點(diǎn)挖掘，用來預(yù)示欺詐行為的存在。

聚類分析的輸入可以用一組有序?qū)Γ╔,s）或(X,d)表示，這里X表示一組樣本，s和d分別是度量樣本間相似度或相異度(距離)的標(biāo)準(zhǔn)。聚類系統(tǒng)的輸出是一個(gè)分區(qū)C={C1,C2,…,Ck}，其中Ci是X的子集，成為類。類的特征可以用如下幾種方式表示：

2 通過類的中心或類的邊界點(diǎn)表示一個(gè)類。

2 使用聚類樹中的結(jié)點(diǎn)圖形化地表示一個(gè)類。

2 使用樣本屬性的邏輯表達(dá)式表示類。

聚類分析的方法：

聚類分析有很多大量的、經(jīng)典的算法，比如k-平均、k-中心點(diǎn)、PAM、CLARANS, BIRTH,CURE,OPTICS,DBSCAN,STING,CLIQUE,WAVECLUSTER等。

度量標(biāo)準(zhǔn)：

一個(gè)聚類分析過程的質(zhì)量取決于對度量標(biāo)準(zhǔn)的選擇，因此必須仔細(xì)選擇度量標(biāo)準(zhǔn)。（1）距離函數(shù)

2 明可夫斯基距離：

x, y 是相應(yīng)的特征，n是特征的維數(shù)。則明可夫斯基距離d(x,y)表示如下

，r=2為歐式距離。

2 二次型距離：

2 余弦距離

2 二元特征樣本的距離

假定x和y分別是n維特征，xi和yi分別表示每維特征，且xi和yi的取值為二元類型數(shù)值{0，1}。則x和y的距離定義的常規(guī)方法是先求如下幾個(gè)參數(shù)，然后采用SMC、Jaccard系數(shù)或Rao系數(shù)。

a是樣本x和y中滿足 xi=yi=1的二元類型屬性的數(shù)量

b是樣本x和y中滿足xi=1,yi=0的二元類型屬性的數(shù)量

c是樣本x和y中滿足xi=0,yi=1的二元類型屬性的數(shù)量

d是樣本x和y中滿足xi=yi=0的二元類型屬性的數(shù)量

則簡單匹配系數(shù)（Simple Match Coefficient, SMC）的公式如下：

Jaccard系數(shù)：

Rao系數(shù)：

（2）類間距離

設(shè)有兩個(gè)類Ca和Cb，分別有m和n個(gè)元素，他們的中心分別為ra和rb。設(shè)元素x屬于Ca，y屬于Cb，這兩個(gè)元素之間的距離記為d(x,y),類間距記為D(Ca,Cb)。

2 最短距離法：類中最靠近的兩個(gè)元素的距離為類間距離：

2 最長距離法：類中最遠(yuǎn)的兩個(gè)元素的距離為類間距離

2 重心法：類中兩個(gè)中心點(diǎn)間的距離為類間距離。因此就需要定義類中心，類中心的定義：

2 類平均法：兩個(gè)類中任意兩個(gè)元素之間的距離相加后取平均值。

2 離差平方和：用到了類直徑，類直徑反應(yīng)了類中各元素的差異，可以定義為各元素到類中心的歐式距離之和，這樣就得到了Ca,Cb,Ca+b的直徑分別為ra,rb,ra+b,那么類間距為ra+b – ra - rb。

給定一個(gè)有n個(gè)對象的數(shù)據(jù)集，劃分聚類技術(shù)將構(gòu)造數(shù)據(jù)k個(gè)劃分，每一個(gè)劃分就代表一個(gè)簇，k<=n。 這k個(gè)劃分滿足下列條件：

2 每個(gè)簇至少包含一個(gè)對象

2 每個(gè)對象屬于且僅屬于一個(gè)簇

對于給定的k，算法首先給出一個(gè)初始的劃分方法，以后通過迭代來改變劃分，是得每一次改進(jìn)之后的劃分方案都較前一次更好。所謂更好的標(biāo)準(zhǔn)時(shí)是：同一個(gè)簇中的對象越接近越好，不同簇之間的對象越遠(yuǎn)越好。目標(biāo)是最小化所有對象與其參考點(diǎn)之間的相異度之和。這里的遠(yuǎn)近或者相異度/相似度實(shí)際上是聚類的評(píng)價(jià)函數(shù)。

評(píng)價(jià)函數(shù)：

評(píng)價(jià)函數(shù)應(yīng)該考慮里兩個(gè)方面：每個(gè)簇應(yīng)該是緊湊的，每個(gè)簇間的距離應(yīng)該盡可能地遠(yuǎn)。這就需要觀察兩個(gè)值：類內(nèi)差異和類間差異。類內(nèi)差異可以采用多種距離函數(shù)來定義，最簡單的就是計(jì)算類內(nèi)的每一個(gè)點(diǎn)到類中心的距離的平方和，一般用w(C)表示。類間差異定義為類中心之間的距離，一般用b(C)表示。

首先隨機(jī)地選擇k個(gè)對象，每個(gè)對象處劃地代表了一個(gè)簇的平均值或中心。對剩余的每個(gè)對象根據(jù)其與各個(gè)簇中心的距離，將它賦給最近的簇。然后重新計(jì)算每個(gè)簇的平均值。這個(gè)過程不斷重復(fù)，直到準(zhǔn)則函數(shù)收斂。準(zhǔn)則如下：

準(zhǔn)則函數(shù)其實(shí)就是所有對象的平法誤差的總和，這個(gè)準(zhǔn)則試圖試生成的結(jié)果簇盡可能地緊湊和獨(dú)立。

算法描述：

輸入：簇的數(shù)目k和包含n個(gè)對象的數(shù)據(jù)庫

輸出：k個(gè)簇，是平方誤差準(zhǔn)則最小

（1） 任意選擇k個(gè)對象作為初始的簇中心

（2） Repeat

（3） 根據(jù)簇中對象的平均值，將每個(gè)對象賦給最類似的簇

（4） 更新簇的平均值，即計(jì)算每個(gè)對象簇中對象的平均值

（5） 計(jì)算準(zhǔn)則函數(shù)

（6） Until E不再明顯地發(fā)生變化

算法性能：

優(yōu)點(diǎn)：

（1） 簡單、快速

（2） 對大數(shù)據(jù)集，是可伸縮和高效率的。

（3） 算法嘗試找出使平方誤差函數(shù)值最小的k個(gè)劃分。當(dāng)結(jié)果簇是密集的，而簇與簇之間區(qū)別明顯的時(shí)候，效果較好。

缺點(diǎn)：

（1） 不適合分類屬性的數(shù)據(jù)

（2） 必須給定k，對初始值k比較敏感

（3） 不適合發(fā)現(xiàn)非凸面形狀的簇，對噪聲和孤立點(diǎn)數(shù)據(jù)是敏感的。

改進(jìn)措施：

（1）k-模算法，可以對離散屬性計(jì)算

（2）不采用簇中的平均值作為參考點(diǎn)，而選用簇中位置最靠近中心的對象。這樣可以避免孤立點(diǎn)的影響。

PAM算法需用簇中位置最靠近中心的對象作為代表對象，然后反復(fù)地用非代表對象來代替代表對象，試圖找出更好的中心點(diǎn)，在反復(fù)迭代的過程中，所有可能的“對象對”被分析，每個(gè)對中的一個(gè)對象是中心點(diǎn)，另一個(gè)是非代表對象。一個(gè)對象代表可以被最大平方-誤差值減少的對象代替。

一個(gè)非代表對象Oh是否是當(dāng)前一個(gè)代表對象Oi的一個(gè)好的替代，對于每個(gè)非中心點(diǎn)對象Oj，有以下四種情況需要考慮：

（1） Oj當(dāng)前隸屬于Oi，如果Oi被Oh替換，且Oj離另一個(gè)Om最近，i！=m，那么Oj被分配給Om，則替換代價(jià)為Cjih=d(j,m)-d(j,i)。

（2） Oj當(dāng)前隸屬于Oi，如果Oi被Oh替換，且Oj離Oh最近，那么Oj被分配給Oh，則替換代價(jià)為Cjih=d(j,h)-d(j,i)。

（3） Oj當(dāng)前隸屬于Om，m！=i，如果Oi被Oh替換，且Oj仍然離Om最近，那么Oj被分配給Om，則替換代價(jià)為Cjih=0。

（4） Oj當(dāng)前隸屬于Om，m！=i，如果Oi被Oh替換，且Oj離Oh最近，那么Oj被分配給Oh，則替換代價(jià)為Cjih=d(j,h)-d(j,m)。

然后計(jì)算

如果 為負(fù)，則可以替換。

算法描述：

輸入：簇的數(shù)目k和包含n個(gè)對象的數(shù)據(jù)庫

輸出：k個(gè)簇，使得所有對象與其最近中心點(diǎn)的相異度總和最小

（1） 任意選擇k個(gè)對象作為初始的簇中心點(diǎn)

（2） Repeat

（3） 指派每個(gè)剩余對象給離他最近的中心點(diǎn)所表示的簇

（4） Repeat

（5） 選擇一個(gè)未被選擇的中心點(diǎn)Oi

（6） Repeat

（7） 選擇一個(gè)未被選擇過的非中心點(diǎn)對象Oh

（8） 計(jì)算用Oh代替Oi的總代價(jià)并記錄在S中

（9） Until 所有非中心點(diǎn)都被選擇過

（10） Until 所有的中心點(diǎn)都被選擇過

（11） If 在S中的所有非中心點(diǎn)代替所有中心點(diǎn)后的計(jì)算出總代價(jià)有小于0的存在，then找出S中的用非中心點(diǎn)替代中心點(diǎn)后代價(jià)最小的一個(gè)，并用該非中心點(diǎn)替代對應(yīng)的中心點(diǎn)，形成一個(gè)新的k個(gè)中心點(diǎn)的集合；

（12） Until 沒有再發(fā)生簇的重新分配，即所有的S都大于0.

算法性能：

(1) 消除了k-平均算法對于孤立點(diǎn)的敏感性。

(2) K-中心點(diǎn)方法比k-平均算法的代價(jià)要高

(3) 必須指定k

(4) PAM對小的數(shù)據(jù)集非常有效，對大數(shù)據(jù)集效率不高。特別是n和k都很大的時(shí)候。