1、第三章 數(shù)據(jù)聚類13.1引引言3.2相相似性性度量3.3聚聚類準(zhǔn)準(zhǔn)則3.4基基于試試探的兩兩種聚類類算法3.5系系統(tǒng)聚聚類法3.6動(dòng)動(dòng)態(tài)聚聚類3.7聚聚類評(píng)評(píng)價(jià)主要內(nèi)容容23.1引引言聚類：將將數(shù)據(jù)分分組成為為多個(gè)類類別，在在同一個(gè)個(gè)類內(nèi)對(duì)對(duì)象之間間具有較較高的相相似度，不同類類之間的的對(duì)象差差別較大大。根據(jù)各個(gè)個(gè)待分類類的模式式特征相相似程度度進(jìn)行分分類，相似的歸為一一類，不不相似的的作為另另一類。監(jiān)督學(xué)習(xí)習(xí)：需要用訓(xùn)訓(xùn)練樣本本進(jìn)行學(xué)學(xué)習(xí)和訓(xùn)訓(xùn)練非監(jiān)督學(xué)學(xué)習(xí)：對(duì)對(duì)于沒有有類別標(biāo)標(biāo)簽的樣樣本集，根據(jù)該該問題本本身的目目的和樣樣本的特特性，把把全體N個(gè)樣本本劃分為為若干個(gè)個(gè)子集，同類樣樣本特性性

2、相差小小，異類類樣本特特性相差差大。3聚類應(yīng)用用花瓣的“物以類類聚”4聚類應(yīng)用用早在孩提提時(shí)代，人就通通過不斷斷改進(jìn)下下意識(shí)中中的聚類類模式來來學(xué)會(huì)如如何區(qū)分分貓和狗狗，動(dòng)物物和植物物誰經(jīng)常光光顧商店店，誰買買什么東東西，買買多少？按照卡記記錄的光光臨次數(shù)數(shù)、光臨臨時(shí)間、性別、年齡、職業(yè)、購物種種類、金金額等變變量分類類這樣商店店可以.識(shí)別顧客客購買模模式（如如喜歡一一大早來來買酸奶奶和鮮肉肉，習(xí)慣慣周末時(shí)時(shí)一次性性大采購購）刻畫不同同的客戶戶群的特特征5聚類應(yīng)用用挖掘有價(jià)價(jià)值的客客戶，并并制定相相應(yīng)的促促銷策略略：如，對(duì)經(jīng)經(jīng)常購買買酸奶的的客戶對(duì)累計(jì)消消費(fèi)達(dá)到到12個(gè)個(gè)月的老老客戶針對(duì)潛在在

3、客戶派派發(fā)廣告告，比在在大街上上亂發(fā)傳傳單命中中率更高高，成本本更低！6聚類應(yīng)用用誰是銀行行信用卡卡的黃金金客戶？利用儲(chǔ)蓄蓄額、刷刷卡消費(fèi)費(fèi)金額、誠信度度等變量量對(duì)客戶戶分類，找出“黃金客客戶”！這樣銀行行可以制制定更吸吸引的服服務(wù)，留留住客戶戶！比如如：一定額度度和期限限的免息息透支服服務(wù)！商場(chǎng)的貴貴賓打折折卡！在他或她她生日的的時(shí)候送送上一個(gè)個(gè)小蛋糕糕！7聚類應(yīng)用用經(jīng)濟(jì)領(lǐng)域域：幫助市場(chǎng)場(chǎng)分析人人員從客客戶數(shù)據(jù)據(jù)庫中發(fā)發(fā)現(xiàn)不同同的客戶戶群，并并且用購購買模式式來刻畫畫不同的的客戶群群的特征征。誰喜歡打打國際長長途，在在什么時(shí)時(shí)間，打打到那里里？對(duì)住宅區(qū)區(qū)進(jìn)行聚聚類，確確定自動(dòng)動(dòng)提款機(jī)機(jī)ATM

4、的安放放位置股票市場(chǎng)場(chǎng)板塊分分析生物學(xué)領(lǐng)領(lǐng)域推導(dǎo)植物物和動(dòng)物物的分類類；對(duì)基因分分類，獲獲得對(duì)種種群的認(rèn)認(rèn)識(shí)數(shù)據(jù)挖掘掘領(lǐng)域作為其他他數(shù)學(xué)算算法的預(yù)預(yù)處理步步驟，獲獲得數(shù)據(jù)據(jù)分布狀狀況，集集中對(duì)特特定的類類做進(jìn)一一步的研研究8聚類分析析原理聚類分析析中“類類”的特特征：聚類所說說的類不不是事先先給定的的，而是是根據(jù)數(shù)數(shù)據(jù)的相相似性和和距離來來劃分聚類的數(shù)數(shù)目和結(jié)結(jié)構(gòu)都沒沒有事先先假定9聚類分析析原理聚類方法法的目的的是尋找找數(shù)據(jù)中中：潛在的自然分組組結(jié)構(gòu)感興趣的的關(guān)系10聚類分析析原理什么是自然分組組結(jié)構(gòu)?有16張張牌，如如何將他他們分組組呢？AKQJ11聚類分析析原理分成四組組：每組組里花色相

5、同同，組與組組之間花花色相異異AKQJ花色相同同的牌為為一組12聚類分析析原理分成四組組，符號(hào)相同同的牌為一一組AKQJ符號(hào)相同同的的牌牌為一組組13聚類分析析原理分成兩組組，顏色相同同的牌為一一組AKQJ顏色相同同的牌為為一組14聚類分析析原理分組的意意義在于于我們?cè)踉趺炊x義并度量量“相似性性”因此衍生生出一系系列度量量相似性性的算法法15聚類分析析原理相似性的的度量（統(tǒng)計(jì)學(xué)學(xué)角度）距離Q型聚類（主要討討論）主要用于于對(duì)樣本本分類常用的距距離有：明考夫斯斯基距離離(包括括：絕對(duì)對(duì)距離、歐式距距離、切切比雪夫夫距離)蘭氏距離離馬氏距離離斜交空間間距離此不詳述述，可參參考應(yīng)應(yīng)用多元元分析（第二

6、二版）王王學(xué)民16聚類分析析原理相似系數(shù)數(shù)R型聚類用于對(duì)變變量分類類，可以以用變量量之間的的相似系系數(shù)的變變形，如如1rij定義距離離17聚類分析析原理變量按測(cè)測(cè)量尺度度分類間隔尺度度變量連續(xù)變量量，如長長度、重重量、速速度、溫溫度等有序尺度度變量等級(jí)變量量，不可可加，但但可比，如一等等、二等等、三等等獎(jiǎng)學(xué)金金名義尺度度變量類別變量量，不可可加也不不可比，如性別別、職業(yè)業(yè)等183.2相相似性性度量聚類分析析符合“物以類類聚，人人以群分分“的原原則，它它把相似似性大的的樣本聚聚集為一一個(gè)類型型聚類分析析的關(guān)鍵鍵問題：如何在在聚類過過程中自自動(dòng)地確確定類型型數(shù)目 19相似性度度量20相似性度度量距

7、離相似似性度量量角度相似似性度量量21距離相似似性度量量模式樣本本向量與與之間的的歐氏距距離定義義為：若距離閾閾值ds選擇過大大，則全全部樣本本被視作作一個(gè)唯唯一類型型；若ds選取過小小，則可可能造成成每個(gè)樣樣本都單單獨(dú)構(gòu)成成一個(gè)類類型22距離相似似性度量量距離閾值值對(duì)聚類類的影響響23距離相似似性度量量特征選取取不當(dāng)使使聚類無無效特征選取取不足引引起誤分分類模式特征征坐標(biāo)單單位的選選取也會(huì)會(huì)強(qiáng)烈地地影響聚聚類結(jié)果果24距離相似似性度量量特征選取取不當(dāng)使使聚類無無效1225距離相似似性度量量特征選取取不足引引起誤分分類12326距離相似似性度量量acbd27解決尺度度問題標(biāo)準(zhǔn)準(zhǔn)化28解決尺度度

8、問題為了進(jìn)行行聚類，我們需需要一種種合適的的距離度度量尺度度。這種距離離度量尺尺度依賴賴于特征征標(biāo)準(zhǔn)化化方法為了選擇擇標(biāo)準(zhǔn)化化方法我我們必須須知道聚聚類的類類型試錯(cuò)法是是唯一的的避免這這種惡性性循環(huán)的的方法。選擇不不同的條條件進(jìn)行行試驗(yàn)，通過觀觀察、數(shù)數(shù)據(jù)解釋釋和效用用分析評(píng)評(píng)價(jià)相應(yīng)應(yīng)的解。平衡各各特征值值的貢獻(xiàn)獻(xiàn)，并保保持原有有的語義義信息。29角度相似似性度量量樣本與之之間的角角度相似似性度量量定義為為它們之之間夾角角的余弦弦303.3聚聚類準(zhǔn)準(zhǔn)則相似性度度量 集合合與集合合的相似似性相似性準(zhǔn)準(zhǔn)則 分類類效果好好壞的評(píng)評(píng)價(jià)準(zhǔn)則則聚類準(zhǔn)則則:試探法定義一種種相似性性度量的的閾值聚類準(zhǔn)則則函數(shù)

9、法法聚類準(zhǔn)則則是反映映類別間間相似性性或分離離性的函函數(shù)誤差平方方和準(zhǔn)則則（最常常用的）加權(quán)平均均平方距距離和準(zhǔn)準(zhǔn)則31誤差平方方和準(zhǔn)則則假定有混混合樣本本X=x1,x2, ,xn采用某種種相似性性度量，X被聚合成成c個(gè)分離開開的子集集X1,X2, ,Xc。每個(gè)子子集是一一個(gè)類型型，它們們分別包包含n1,n2, ,nc個(gè)樣本為了衡量量類的質(zhì)質(zhì)量，采采用誤差差平方和和Jc聚類準(zhǔn)則則函數(shù)，定義為為：mj為類型Xj中樣本的的均值，mj是c個(gè)集合的的中心，可以用用來代表表c個(gè)類型。32誤差平方方和準(zhǔn)則則誤差平方方和準(zhǔn)則則適用于于各類樣樣本比較較密集且且樣本數(shù)數(shù)目懸殊殊不大的的樣本分分布33誤差平方方和

10、準(zhǔn)則則例：34加權(quán)平均均平方距距離和準(zhǔn)準(zhǔn)則定義加權(quán)權(quán)平均平平方距離離和準(zhǔn)則則：式中：Sj*是類內(nèi)樣樣本間平平均平方方距離Xj中的樣本本個(gè)數(shù)nj，Xj中的樣本本兩兩組組合共有有nj(nj-1)/2種表示所有有樣本之之間距離離之和Pj為j類的先驗(yàn)驗(yàn)概率，可以用用樣本數(shù)數(shù)目nj和樣本總總數(shù)目n來估計(jì)，Pj=nj/n,j=1,2,c35加權(quán)平均均平方距距離和準(zhǔn)準(zhǔn)則例：363.4基基于試試探的兩兩種聚類類算法采用最近近鄰規(guī)則則的聚類類算法最大最小小距離聚聚類算法法37采用最近近鄰規(guī)則則的聚類類算法選取距離離閾值T，并且任任取一個(gè)個(gè)樣本作作為第一一個(gè)聚合合中心Z1，如：Z1=x1計(jì)算樣本本x2到Z1的距離

11、D21若D21T，則x2Z1，否則令令x2為第二個(gè)個(gè)聚合中中心，Z2=x2設(shè)Z2=x2，計(jì)算x3到Z1和Z2的距離D31和D32，若D31T和D32T，則建立立第三個(gè)個(gè)聚合中中心Z3。否則把把x3歸于最近近鄰的聚聚合中心心。依此此類推，直到把把所有的的n個(gè)樣本都都進(jìn)行分分類。按照某種種聚類準(zhǔn)準(zhǔn)則考察察聚類結(jié)結(jié)果，若若不滿意意，則重重新選取取距離閾閾值T、第一個(gè)個(gè)聚合中中心Z1，返回，直到滿滿意，算算法結(jié)束束。38采用最近近鄰規(guī)則則的聚類類算法最近鄰規(guī)規(guī)則的聚聚類算法法：計(jì)算算模式特特征矢量量到聚類類中心的的距離，和門限限T比較，決決定歸屬屬哪類或或作為新新的聚類類中心。該算法的的優(yōu)點(diǎn)是是簡(jiǎn)單，

12、如果有有樣本分分布的先先驗(yàn)知識(shí)識(shí)用于指指導(dǎo)閾值值和起始始點(diǎn)的選選取，則則可較快快得到合合理結(jié)果果。算法的結(jié)結(jié)果在很很多程度度上取決決于第一一個(gè)聚合合中心的的選取和和距離閾閾值的大大小。39閾值對(duì)聚聚類的影影響40起始點(diǎn)對(duì)對(duì)聚類的的影響Z=x1Z=x5Z=x741最大最小小距離聚聚類算法法若Dk1=maxDi1，則取取xk為第二個(gè)個(gè)聚合中中心Z2，計(jì)算所所有樣本本到Z1和Z2的距離Di1和Di2。若Dl=maxmin(Di1,Di2)，i=1,2,n，并且DlD12，D12為Z1和Z2間距離，則取xl為第三個(gè)個(gè)聚合中中心Z3。注意：Di1=|xi-Z1|，Di2=|xi-Z2|。如果Z3存在，則

13、則計(jì)算Dj=maxmin(Di1,Di2,Di3),i=1,2,n，若DjD12，則建立立第四個(gè)個(gè)聚合中中心。依依此類推推，直到到最大最最小距離離不大于于D12時(shí)，結(jié)束束尋找聚聚合中心心的計(jì)算算。給定，01，并并且任取取一個(gè)樣樣本作為為第一個(gè)個(gè)聚合中中心，Z1=x1尋找新的的聚合中中心，計(jì)計(jì)算其它它所有樣樣本到Z1的距離Di142最大最小小距離聚聚類算法法按最近鄰鄰原則把把所有樣樣本歸屬屬于距離離最近的的聚合中中心按照某聚聚類準(zhǔn)則則考查聚聚類結(jié)果果，若不不滿意，則重新新選擇，第一個(gè)個(gè)聚合中中心，返返回到，直到到滿意，算法結(jié)結(jié)束。最大最小小距離聚聚類算法法：在模模式特征征矢量集集中以最最大距離離

14、原則選選取新的的聚類中中心，以以最小距距離準(zhǔn)則則進(jìn)行模模式歸類類。獨(dú)立性能能不好，依賴先先驗(yàn)知識(shí)識(shí)。43最大最小小距離聚聚類算法法例：44最大最小小距離聚聚類算法法453.5系系統(tǒng)聚聚類法(層次化化聚類)融合算法法分裂算法法46融合算法法融合算法法基本思思想：給定n個(gè)樣本xi，最初把把每個(gè)樣樣本看成成一類i=xi，設(shè)聚聚類數(shù)c=n當(dāng)c1時(shí)，重復(fù)復(fù)進(jìn)行以以下操作作：利用合適適的相似似性度量量尺度和和規(guī)則確確定最相相近的兩兩個(gè)聚類類i和i合并i和j：ij=i,j，從而而得到一一個(gè)類別別數(shù)為c-1的聚聚類解將c值遞減注意：在在確定最最近的兩兩個(gè)聚類類時(shí)，需需要同時(shí)時(shí)依靠相相似性度度量和用用于評(píng)價(jià)價(jià)聚

15、類相相似性的的規(guī)則。47融合算法法設(shè)初始模模式樣本本共有N個(gè)，每個(gè)個(gè)樣本自自成一類類，即建建立N類：G1(0),G2(0), ,GN(0)。計(jì)算各各類之間間（在起起始時(shí)也也就是各各個(gè)樣本本之間）的距離離，可得得一個(gè)N*N維的距離離矩陣D(0)如在距距離運(yùn)算算中心已已求得距距離矩陣陣D(n)，則求D(n)中的最小小元素。如果它它是Gi(n),Gj(n)兩類之間間的距離離，則將將Gi(n),Gj(n)兩類合并并為一類類Gij(n+1)。由此建建立新的的分類G1(n+1),G2(n+1), 。計(jì)算合并并后的新新類別之之間的距距離，得得D(n+1)。計(jì)算Gij(n+1)與其他沒沒有發(fā)生生合并的的G1(

16、n+1),G2(n+1), 之之間的距距離時(shí)，有多種種不同的的距離計(jì)計(jì)算準(zhǔn)則則。跳到，重復(fù)計(jì)計(jì)算合并并，可一一直將全全部樣本本聚集成成一類。48融合算法法視N個(gè)模式各各成為一一類，計(jì)計(jì)算類與與類之間間的距離離，選擇擇距離最最小的一一對(duì)合并并成一個(gè)個(gè)新類，計(jì)算在在新的類類別分劃劃下各類類之間的的距離，再將距距離最近近的兩類類合并，直至所所有模式式聚成兩兩類為止止。49融合算法法例：給出出6個(gè)樣樣本待征征矢量如如下，按按最小距距離原則則進(jìn)行聚聚類。x1=(0,3,1,2,0)Tx2=(1,3,0,1,0)Tx3=(3,3,0,0,1)Tx4=(1,1,0,2,0)Tx5=(3,2,l,2,1)Tx

17、6=(4,1,1,1,0)T5051融合算法法系統(tǒng)聚類類過程可可繪成樹樹狀表示示，如圖圖所示52融合算法法聚類1=Aveiro,Setubal,V.Castelo；財(cái)產(chǎn)方面面的高犯犯罪率，超過對(duì)對(duì)人身安安全方面面的犯罪罪率；聚類2=Beja, Braga,Braganca,Coimbra,Porto, Santarem,Viseu；財(cái)產(chǎn)方面面的高犯犯罪率，低于對(duì)對(duì)人身安安全方面面的犯罪罪率。聚類3=C.Branco,Evora,Faro,Guarda,Leiria, Lisboa,Portalegre,V.Real；財(cái)產(chǎn)產(chǎn)和人身身安全方方面的平平均水平平的犯罪罪率。53融合算法法w1=I，Dw

18、2=A，B，C，E，F(xiàn)，G，Hw3=8，9w4=1，2，3，4，5，6，754融合算法法改進(jìn)可將類間間距離門門限T作為停止止條件，當(dāng)D(k)中最小小陣元大大于T時(shí)，聚類類過程停停止；也可將預(yù)預(yù)定的類類別數(shù)目目作為停停止條件件，在類類別合并并過程中中，類數(shù)數(shù)等于預(yù)預(yù)定值時(shí)時(shí)，聚類類過程停停止。55層次化聚聚類聯(lián)接接規(guī)則聯(lián)接規(guī)則則：衡量量聚類之之間相異異程度的的方法。單聯(lián)接完全聯(lián)接接規(guī)則類間平均均聯(lián)接規(guī)規(guī)則類內(nèi)平均均聯(lián)接規(guī)規(guī)則Ward方法563.6動(dòng)動(dòng)態(tài)聚聚類算法法算法首先先選擇某某種樣本本相似性性度量和和適當(dāng)?shù)牡木垲悳?zhǔn)準(zhǔn)則函數(shù)數(shù)，使用用迭代算算法，在在初始劃劃分的基基礎(chǔ)上，逐步優(yōu)優(yōu)化聚類類結(jié)果，

19、使準(zhǔn)則則函數(shù)達(dá)達(dá)到極值值。算法要解解決的關(guān)關(guān)鍵問題題：首先選擇擇有代表表性的點(diǎn)點(diǎn)作為起起始聚合合中心。若類型型數(shù)目已已知，則則選擇代代表點(diǎn)的的數(shù)目等等于類型型數(shù)目；若未知知，那么么聚類過過程要形形成的類類型數(shù)目目，是一一個(gè)問題題。代表點(diǎn)選選擇好之之后，如如何把所所有樣本本區(qū)分到到以代表表點(diǎn)為初初始聚合合中心的的范圍內(nèi)內(nèi)，形成成初始劃劃分57動(dòng)態(tài)聚類類算法k-均值聚聚類算法法使用的的聚類準(zhǔn)準(zhǔn)則函數(shù)數(shù)是誤差差平方和和準(zhǔn)則：k-均值聚聚類算法法ISODATA算法58k-均值聚聚類算法法59k-均值聚聚類算法法算法特點(diǎn)點(diǎn)：每次迭迭代中都都要考查查每個(gè)樣樣本的分分類是否否正確，若不正正確，就就要調(diào)整整，

20、在全全部樣本本調(diào)整完完之后，再修改改聚合中中心，進(jìn)進(jìn)入下一一次迭代代。如果果在某一一個(gè)迭代代運(yùn)算中中，所有有的樣本本都被正正確分類類，則樣樣本不會(huì)會(huì)調(diào)整，聚合中中心也不不會(huì)有變變化，也也就是收收斂了。初始聚聚合中心心的選擇擇對(duì)聚類類結(jié)果有有較大影影響。60k-均值聚聚類算法法例：現(xiàn)有有混合樣樣本集，共有樣樣本20個(gè)，分分布如下下圖所示示，類型型數(shù)目c=2。試試用k-均值算算法進(jìn)行行聚類分分析61k-均值聚聚類算法法62改進(jìn)k-均值算算法(c-均值算算法)6364k-均值聚聚類算法法k-均值算算法的結(jié)結(jié)果受如如下選擇擇的影響響：所選聚類類的數(shù)目目聚類中心心的初始始分布模式樣本本的幾何何性質(zhì)讀入次序序在實(shí)際應(yīng)應(yīng)用中，需要試試探不同同的K值值和選擇擇不同的的聚類中中心的起起始值。如果模式式樣本可可以形成成若干個(gè)個(gè)相距較較遠(yuǎn)的小小塊孤立立的區(qū)域域分布，一般都都能得到到較好的的