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

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

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

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

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

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

（5） 對(duì)于輸入記錄順序不敏感

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

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

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

（9） 挖掘出來(lái)的信息是可理解的和可用的。

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

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

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

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

基本概念

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

2 通過(guò)類的中心或類的邊界點(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è)聚類分析過(guò)程的質(zhì)量取決于對(duì)度量標(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ù)量

則簡(jiǎn)單匹配系數(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 最長(zhǎng)距離法：類中最遠(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è)對(duì)象的數(shù)據(jù)集，劃分聚類技術(shù)將構(gòu)造數(shù)據(jù)k個(gè)劃分，每一個(gè)劃分就代表一個(gè)簇，k<=n。 這k個(gè)劃分滿足下列條件：

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

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

對(duì)于給定的k，算法首先給出一個(gè)初始的劃分方法，以后通過(guò)迭代來(lái)改變劃分，是得每一次改進(jìn)之后的劃分方案都較前一次更好。所謂更好的標(biāo)準(zhǔn)時(shí)是：同一個(gè)簇中的對(duì)象越接近越好，不同簇之間的對(duì)象越遠(yuǎn)越好。目標(biāo)是最小化所有對(duì)象與其參考點(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ù)來(lái)定義，最簡(jiǎn)單的就是計(jì)算類內(nèi)的每一個(gè)點(diǎn)到類中心的距離的平方和，一般用w(C)表示。類間差異定義為類中心之間的距離，一般用b(C)表示。

K-means算法

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

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

算法描述：

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

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

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

（2） Repeat

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

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

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

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

算法性能：

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

（1） 簡(jiǎn)單、快速

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

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

缺點(diǎn)：

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

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

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

改進(jìn)措施：

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

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

PAM算法（也稱k-中心點(diǎn)算法）

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

一個(gè)非代表對(duì)象Oh是否是當(dāng)前一個(gè)代表對(duì)象Oi的一個(gè)好的替代，對(duì)于每個(gè)非中心點(diǎn)對(duì)象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è)對(duì)象的數(shù)據(jù)庫(kù)

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

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

（2） Repeat

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

（4） Repeat

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

（6） Repeat

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

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

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

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

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

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

算法性能：

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

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

(3) 必須指定k

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