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

好的聚類算法應該滿足以下幾個方面：

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

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

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

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

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

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

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

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

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

聚類分析主要在以下幾個方面應用：

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

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

（3） 可以完成孤立點挖掘，用來預示欺詐行為的存在。

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

2 通過類的中心或類的邊界點表示一個類。

2 使用聚類樹中的結點圖形化地表示一個類。

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

聚類分析的方法：

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

度量標準：

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

2 明可夫斯基距離：

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

，r=2為歐式距離。

2 二次型距離：

2 余弦距離

2 二元特征樣本的距離

假定x和y分別是n維特征，xi和yi分別表示每維特征，且xi和yi的取值為二元類型數(shù)值{0，1}。則x和y的距離定義的常規(guī)方法是先求如下幾個參數(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）類間距離

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

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

2 最長距離法：類中最遠的兩個元素的距離為類間距離

2 重心法：類中兩個中心點間的距離為類間距離。因此就需要定義類中心，類中心的定義：

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

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

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

2 每個簇至少包含一個對象

2 每個對象屬于且僅屬于一個簇

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

評價函數(shù)：

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

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

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

算法描述：

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

輸出：k個簇，是平方誤差準則最小

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

（2） Repeat

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

（4） 更新簇的平均值，即計算每個對象簇中對象的平均值

（5） 計算準則函數(shù)

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

算法性能：

優(yōu)點：

（1） 簡單、快速

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

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

缺點：

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

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

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

改進措施：

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

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

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

一個非代表對象Oh是否是當前一個代表對象Oi的一個好的替代，對于每個非中心點對象Oj，有以下四種情況需要考慮：

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

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

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

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

然后計算

如果 為負，則可以替換。

算法描述：

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

輸出：k個簇，使得所有對象與其最近中心點的相異度總和最小

（1） 任意選擇k個對象作為初始的簇中心點

（2） Repeat

（3） 指派每個剩余對象給離他最近的中心點所表示的簇

（4） Repeat

（5） 選擇一個未被選擇的中心點Oi

（6） Repeat

（7） 選擇一個未被選擇過的非中心點對象Oh

（8） 計算用Oh代替Oi的總代價并記錄在S中

（9） Until 所有非中心點都被選擇過

（10） Until 所有的中心點都被選擇過

（11） If 在S中的所有非中心點代替所有中心點后的計算出總代價有小于0的存在，then找出S中的用非中心點替代中心點后代價最小的一個，并用該非中心點替代對應的中心點，形成一個新的k個中心點的集合；

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

算法性能：

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

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

(3) 必須指定k

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