第9章 聚類分析

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

實(shí)現(xiàn)度量值的標(biāo)準(zhǔn)化：將原來(lái)的度量值轉(zhuǎn)換為無(wú)單位的值。為什么這么做?

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

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

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

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

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

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

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

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

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

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

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

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

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

，yif

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

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

:由簇的中心來(lái)代表簇；k-中心點(diǎn):

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

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

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

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

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

。OiOjpOrandom

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

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

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

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