第9章 聚類分析

第九章聚類分析一、聚類分析含義將物理或抽象對象的集合分組成為由類似的對象組成的多個類的過程稱為聚類，由聚類所組成的簇是一組對象的集合，這些對象與同一簇中的對象彼此相似，與其它簇中的對象相異。與分類不同，它要劃分的類是未知的。二、聚類分析中的數(shù)據(jù)類型及轉(zhuǎn)換1、數(shù)據(jù)矩陣：用p個變量（也稱為度量或?qū)傩裕﹣肀憩F(xiàn)n個對象，例如用年齡、身高、性別等屬性來表現(xiàn)對象“人”。構(gòu)成一個n*p的矩陣。2、相異度矩陣：存儲n個對象兩兩之間的近似程度性，表現(xiàn)形式是一個n*n的矩陣。這里d(i,j)是對象i和對象j之間相異性的量化表示3、區(qū)間標度度量一個粗略線性標度的連續(xù)度量。（如重量，溫度等）

實現(xiàn)度量值的標準化：將原來的度量值轉(zhuǎn)換為無單位的值。為什么這么做?

選用的度量單位會直接影響聚類結(jié)果。例如千克改位克。一般，所用的單位越小，變量的值域就越大，對聚類的影響也越大。為了避免數(shù)據(jù)對度量單位的依賴，數(shù)據(jù)應(yīng)當標準化。給定變量f，變換方法：（1）計算平均的絕對偏差Sf（2）計算標準化度量值，或z-score:注意：在特定的應(yīng)用中，是否要數(shù)據(jù)標準化和如何標準化是用戶自己的事情4、已標準化數(shù)據(jù)后怎么計算兩個對象的相似度三種常用的距離計算公式

（1）歐幾里德距離（2）曼哈坦距離（2）明斯基距離5、其它類型變量的相異度計算（1）二元變量變量的取值只有兩個狀態(tài)，如性別，表示是否吸煙，醫(yī)療檢查正常還是不正常等。

i和j是兩個變量：q是兩個變量中都為1的個數(shù)

l是兩個變量中都為0的個數(shù)

s是i變量中為0，j中為1的個數(shù)

r是i變量中為1，j中為0的個數(shù)

p=q+r+s+t二元變量權(quán)重相同(對稱的，如性別）即：分子為兩者相異的總數(shù)，分母為二元變量總數(shù)二元變量權(quán)重不同(非對稱的）例如，一個疾病化驗結(jié)果正常和不正常，對一個群體，正常者總是大多數(shù)，我們用1表現(xiàn)幾率小的情況，0表示另一種情況。評價系數(shù)，Jaccard系數(shù)

即：兩個相異的數(shù)量作為分子，相異的數(shù)量加兩個為1的數(shù)量作為分母。（同對稱二元變量相比，兩個同為0的數(shù)量不出現(xiàn)在分母中）例：假定一個病人記錄表如下：姓名發(fā)燒咳嗽檢查1檢查2檢查3檢查4張明是否不正常正常正常正常王枚是否不正常正常不正常正常李力是是正常正常正常正?！?….….….….....…..例：假定一個病人記錄表如下：姓名發(fā)燒咳嗽檢查1檢查2檢查3檢查4張明是否不正常正常正常正常王枚是否不正常正常不正常正常李力是是正常正常正常正常….….….….….....…..例：假定一個病人記錄表如下：姓名發(fā)燒咳嗽檢查1檢查2檢查3檢查4張明是否不正常正常正常正常王枚是否不正常正常不正常正常李力是是正常正常正常正常….….….….….....…..從左邊的計算知道：（1）李力和王枚不大可能有相同疾病，因為相異很高；（2）張明和王枚最可能得相同的疾?。?）枚舉變量

可以有若干個不同取值，比如反映產(chǎn)品顏色的color可以是{紅、黃、綠、蘭、粉紅}

假設(shè)一個枚舉變量的狀態(tài)數(shù)目是M。這些狀態(tài)可以映射到字母、符號或一組整數(shù)(1,2,…,M)。p是全部變量的數(shù)目m是匹配的數(shù)目。（3）序數(shù)型變量是枚舉但有序，比如{金牌、銀牌、銅牌}

區(qū)間標度度量值劃成了區(qū)間，比如年齡分成了年齡段{10

歲以下，11..20,21..30,..}等。一個序數(shù)型變量的值可以映射為秩。例如一個變量f可以有Mf個狀態(tài)，可以映射到一個有序排列{1，2，…,Mf}。如何處理序數(shù)型變量？假設(shè)f是用于描述n個對象的一組序數(shù)型變量之一，關(guān)于f的相異度計算包括如下步驟：

1）第i個對象的f值為xif，變量f有Mf個有序的狀態(tài)，對應(yīng)于序列1，…，Mf。用對應(yīng)的秩rif代替xif，rif{1，..，Mf}2）既然每個序數(shù)型變量可以有不同數(shù)目的狀態(tài)，經(jīng)常必須將每個變量的值映射到[0.0，1.0]上，以便每個變量都有相同的權(quán)重?？梢酝ㄟ^用zif代替rif來實現(xiàn)3)相異度的計算可以采用前面的任意一種距離度量方法（4）比例標度型非線性的取正的數(shù)據(jù)，如指數(shù)型數(shù)據(jù)。對數(shù)變換，對象i的f變量的值xif被變換成yif

，yif

=log(xif)將xif看成序數(shù)型數(shù)據(jù)6、混合類型的變量真實數(shù)據(jù)庫的元組的變量往往是混合的。處理方法為：（1）將變量按類型分組，對每種類型的變量進行單獨的聚類分析。如果這些分析得到的結(jié)果是兼容的，則該方法是可行的。實際應(yīng)用中，這種情況比較少見。（2）將所有變量一起處理，只進行一次聚類。將不同類型的變量組合在單個相異度矩陣中，把所有有意義的變量轉(zhuǎn)換到共同的值域區(qū)間[0.0，1.0]上。假設(shè)數(shù)據(jù)集包含p個不同類型的變量，對象i和j之間的相異度d(i，j)定義為：

其中，如果xif或xjf缺，或者xif=xjf=0，且變量f是不對稱的二元變量，則指示項=0；否則等于1。變量f對i和j之間相異的計算方式與其具體類型相關(guān)：如果f是二元變量或枚舉變量：如果xif=xjf,,否則為1。如果f是區(qū)間標度變量：如果f是虛數(shù)型或者比例標度型變量：計算秩rif，在變換zif三、劃分方法劃分方法:將一個包含n個數(shù)據(jù)對象的數(shù)據(jù)庫組織成k個劃分（k<=n），其中每個劃分代表一個簇。給定一個k，要構(gòu)造出k個簇，并滿足采用的劃分準則：k-平均

:由簇的中心來代表簇；k-中心點:

每個簇由簇中的某個數(shù)據(jù)對象來代表。K-平均算法：把n個對象分為k個簇，是簇內(nèi)具有較高的相似度，而簇間的相似度較底。相似度的計算根據(jù)一個簇中對象的平均值（重心）來進行。

流程：首先，隨機的抽取k個對象，每個對象初始地代表一個簇的平均值。對剩余的每個對象，根據(jù)與各個簇中心的距離，將它賦給最近的簇。然后重新計算各個簇的平均值。過程不斷反復(fù)，直到準則函數(shù)收斂。一般采用平方誤差準則：這里，p是空間的點，表示給定的對象，mi是簇Ci的平均值。例子初始點初始點K-中心點：首先為每個簇隨意選擇一個代表；剩余的對象根據(jù)其與代表對象的距離分配給最近的一個簇。然后反復(fù)地用非代表對象代替代表對象，以改進聚類質(zhì)量。質(zhì)量用一個代價函數(shù)估算。該函數(shù)計算對象與參照對象之間的平均相異度。（比如：代替后的點的平方誤差函數(shù)-原來的平方誤差函數(shù))描述：1）隨機選擇k個對象作為初始的中心點；2）repeat3）指派每個剩余的對象給離它最近的中心點所代表的簇；4）隨機地選擇一個非中心點對象Orandom;5)計算用Orandom代替Oj的總代價S;6)ifS<0thenOrandom代替Oj

,形成新的k個中心點的集合；7)until不發(fā)生變化；

判定一個非代表對象Orandom是否是一個代表對象Oj的更好替代，對每個非中心點對象p,考慮下面四種情況：1）p當前隸屬于中心點對象Oj。如果用Orandom代替它后，p離Oi更近，p重新分配給OiOiOjpOrandom

判定一個非代表對象Orandom是否是一個代表對象Oj的更好替代，對每個非中心點對象p,考慮下面四種情況：1）p當前隸屬于中心點對象Oj。如果用Orandom代替它后，p離Oi更近，p重新分配給Oi。2)p當前隸屬于中心點對象Oj。如果用Orandom代替它后，p離Orandom更近，p重新分配給Orandom

。OiOjpOrandom

判定一個非代表對象Orandom是否是一個代表對象Oj的更好替代，對每個非中心點對象p,考慮下面四種情況：1）p當前隸屬于中心點對象Oj。如果用Orandom代替它后，p離Oi更近，p重新分配給Oi。2)p當前隸屬于中心點對象Oj。如果用Orandom代替它后，p離Orandom更近，p重新分配給Orandom

。3)p當前隸屬于中心點對象Oi。如果Oj被Orandom代替作為中心點后，而p仍然離Oi更近，那么對象的隸屬關(guān)系不變。OiOjpOrandom

判定一個非代表對象Orandom是否是一個代表對象Oj的更好替代，對每個非中心點對象p,考慮下面四種情況：1）p當前隸屬于中心點對象Oj。如果用Orandom代替它后，p離Oi更近，p重新分配給Oi。2)p當前隸屬于中心點對象Oj。如果用Orandom代替它后，p離Orandom更近，p重新分配給Orandom

。3)p當前隸屬于中心點對象Oi。如果Oj被Orandom代替作為中心點后，而p仍然離Oi更近，那么對象的隸屬關(guān)系不變。4)p當前隸屬于中心點對象Oi。如果Oj被Orandom代替作為中心點后，而p離Orandom更近，那么p重新分配給Orandom