商務(wù)智能-Chapter05-Data Mining-Clustering學(xué)習(xí)課件

ZhangjunWu（伍章?。㊣nstituteofBusinessIntelligence,FacultyofElectronicCommerce,ManagementSchool第五章聚類分析2025/2/27?TheInstituteofBusinessIntelligence,HFUT2/104內(nèi)容提綱1.分類分析2.聚類分析3.關(guān)聯(lián)分析聚類聚類（Clustering）就是將對(duì)象集合分成為多個(gè)類（Cluster）的過程。聚類分析是一種重要的人類活動(dòng)。早在孩提時(shí)代，人就通過不斷改進(jìn)下意識(shí)中的聚類模式來學(xué)會(huì)如何區(qū)分貓和狗，動(dòng)物和植物。2025/2/27?TheInstituteofBusinessIntelligence,HFUT3/104聚類分析無處不在如果你是一個(gè)淘寶店鋪的老板…誰經(jīng)常光顧店鋪，誰買什么東西，買多少？按消費(fèi)者的性別、年齡、職業(yè)、瀏覽次數(shù)、瀏覽時(shí)間、購物種類、金額等變量對(duì)消費(fèi)者進(jìn)行聚類這樣淘寶店鋪可以…識(shí)別顧客購買模式（如哪些人喜歡周末時(shí)一次性大采購）需要針對(duì)不同的人群，制定不同的關(guān)系管理方式，以提高客戶對(duì)公司商業(yè)活動(dòng)的響應(yīng)率。2025/2/27?TheInstituteofBusinessIntelligence,HFUT4/104如果你是銀行的客戶經(jīng)理…利用儲(chǔ)蓄額、刷卡消費(fèi)金額、刷卡次數(shù)、誠信度等變量對(duì)客戶聚類，找出誰是銀行信用卡的黃金客戶、誰是容易流失的客戶這樣銀行可以……制定更吸引的服務(wù)，留住客戶！比如：一定額度和期限的免息透資服務(wù)！百盛的貴賓打折卡！在他或她生日的時(shí)候送上一個(gè)小蛋糕！2025/2/27?TheInstituteofBusinessIntelligence,HFUT5/104聚類分析無處不在如果你是社會(huì)性網(wǎng)站的站長(zhǎng)…把每個(gè)用戶想象成圖中的一個(gè)節(jié)點(diǎn)，如果用戶A對(duì)用戶B有互動(dòng)行為(轉(zhuǎn)發(fā)，評(píng)論等)，在用戶A和用戶B之間建立一條有向邊這樣網(wǎng)站可以……基于用戶的互動(dòng)信息，構(gòu)建用戶興趣的挖掘算法。發(fā)現(xiàn)網(wǎng)站中具有相同興趣的用戶群體2025/2/27?TheInstituteofBusinessIntelligence,HFUT6/104聚類分析無處不在聚類分析原理—引例我們看看以下的例子：有16張牌如何將他們分為一組一組的牌呢？AKQJ2025/2/27?TheInstituteofBusinessIntelligence,HFUT7/104分成四組每組里花色相同組與組之間花色相異AKQJ花色相同的牌為一副2025/2/27?TheInstituteofBusinessIntelligence,HFUT8/104聚類分析原理—引例分成四組符號(hào)相同的牌為一組AKQJ符號(hào)相同的的牌2025/2/27?TheInstituteofBusinessIntelligence,HFUT9/104聚類分析原理—引例分成兩組顏色相同的牌為一組AKQJ顏色相同的配對(duì)2025/2/27?TheInstituteofBusinessIntelligence,HFUT10/104聚類分析原理—引例分成兩組大小相近的牌為一組大配對(duì)和小配對(duì)AKQJ2025/2/27?TheInstituteofBusinessIntelligence,HFUT11/104聚類分析原理—引例聚類分析—基本過程基本過程選擇合理的相似度計(jì)算方法計(jì)算個(gè)體之間的距離或相似度，構(gòu)建距離矩陣或相似度矩陣基于相似性，采取某種聚類方法進(jìn)行聚類對(duì)不同類別的對(duì)象特征進(jìn)行分析基本原則類內(nèi)對(duì)象相似性盡可能大，類間對(duì)象相似性盡可能小2025/2/27?TheInstituteofBusinessIntelligence,HFUT12/1042025/2/27?TheInstituteofBusinessIntelligence,HFUT13/104聚類分析—基本過程顧客id訂單規(guī)模

訂單金額

點(diǎn)擊量c111.550c216.540c31.5225c44.57.575c548.520c65.5930c74.58552025/2/27?TheInstituteofBusinessIntelligence,HFUT14/104聚類分析—基本過程距離計(jì)算—連續(xù)型屬性歐氏距離（Euclideandistance）曼哈頓距離（Manhattandistance）明考斯基距離（Minkowskidistance）2025/2/27?TheInstituteofBusinessIntelligence,HFUT15/104顧客id訂單規(guī)模

訂單金額

點(diǎn)擊量c111.550c25.5955c358.540c44.57.575c548.520c63.5930c726.540距離10.0715.0235.0255.0110.0210.422025/2/27?TheInstituteofBusinessIntelligence,HFUT16/104距離計(jì)算—連續(xù)型屬性選用的度量單位直接影響聚類分析的結(jié)果，因此需要實(shí)現(xiàn)度量值的標(biāo)準(zhǔn)化，將原來的值轉(zhuǎn)化為無單位的值，給定一個(gè)變量f的度量值，可使用以下方法進(jìn)行標(biāo)準(zhǔn)化：最大-最小值方法z-score方法變量指數(shù)法距離計(jì)算—連續(xù)型屬性標(biāo)準(zhǔn)化2025/2/27?TheInstituteofBusinessIntelligence,HFUT17/104a’=(a-min)/(max-min)連續(xù)型屬性標(biāo)準(zhǔn)化—最大-最小值方法顧客id訂單規(guī)模

訂單金額

點(diǎn)擊量c111.550c25.5955c358.540c44.57.575c548.520c63.5930c726.540Max5.5975Min11.520訂單規(guī)模

訂單金額

點(diǎn)擊量0.000.000.551.001.000.640.890.930.360.780.801.000.670.930.000.561.000.180.220.670.362025/2/27?TheInstituteofBusinessIntelligence,HFUT18/104距離計(jì)算—連續(xù)型屬性顧客id訂單規(guī)模

訂單金額

點(diǎn)擊量c10.000.000.55c21.001.000.64c30.890.930.36c40.780.801.00c50.670.930.00c60.561.000.18c70.220.670.36距離1.420.300.661.010.220.51距離10.0715.0235.0255.0110.0210.422025/2/27?TheInstituteofBusinessIntelligence,HFUT19/104計(jì)算均值絕對(duì)偏差其中計(jì)算標(biāo)準(zhǔn)化的度量值(z-score)連續(xù)型屬性標(biāo)準(zhǔn)化—z-score方法2025/2/27?TheInstituteofBusinessIntelligence,HFUT20/104顧客id訂單規(guī)模

訂單金額

點(diǎn)擊量c111.550c25.5955c358.540c44.57.575c548.520c63.5930c726.540mf3.647.2144.29sf1.271.8413.47顧客id訂單規(guī)模

訂單金額

點(diǎn)擊量c1-2.09-3.110.42c21.470.970.80c31.070.70-0.32c40.680.162.28c50.280.70-1.80c6-0.110.97-1.06c7-1.30-0.39-0.322025/2/27?TheInstituteofBusinessIntelligence,HFUT21/104距離計(jì)算—連續(xù)型屬性顧客id訂單規(guī)模

訂單金額

點(diǎn)擊量c1-2.09-3.110.42c21.470.970.80c31.070.70-0.32c40.680.162.28c50.280.70-1.80c6-0.110.97-1.06c7-1.30-0.39-0.32距離5.431.212.684.140.881.95距離1.420.300.661.010.220.51距離10.0715.0235.0255.0110.0210.422025/2/27?TheInstituteofBusinessIntelligence,HFUT22/104變量指數(shù)法把屬性值除以該屬性所有取值的均值顧客id訂單規(guī)模

訂單金額

點(diǎn)擊量c111.550c25.5955c358.540c44.57.575c548.520c63.5930c726.540均值3.647.2144.29顧客id訂單規(guī)模

訂單金額

點(diǎn)擊量c10.270.211.13c21.511.251.24c31.371.180.90c41.241.041.69c51.101.180.45c60.961.250.68c70.550.900.902025/2/27?TheInstituteofBusinessIntelligence,HFUT23/104距離計(jì)算—離散型屬性屬性值的個(gè)數(shù)是有限的，如性別、學(xué)歷、職業(yè)等二元變量標(biāo)稱變量序數(shù)變量2025/2/27?TheInstituteofBusinessIntelligence,HFUT24/104距離計(jì)算—離散型屬性二元變量變量取值只有兩種狀態(tài)，0或1。二元變量分為對(duì)稱二元變量和非對(duì)稱二元變量顧客id性別已婚E71

手機(jī)電池

不滿意投訴退貨取消訂單c110111010c200011010c300001100c411110000c500101110c601010001c7111100002025/2/27?TheInstituteofBusinessIntelligence,HFUT25/104二元變量對(duì)稱的如果一個(gè)二元變量的兩個(gè)狀態(tài)是同等價(jià)值的，且發(fā)生具有相似的概率，則可以任取其中一種狀態(tài)編碼為1或者0。對(duì)于對(duì)稱的二元變量，采用簡(jiǎn)單匹配系數(shù)來評(píng)價(jià)兩個(gè)對(duì)象之間的相異度

Objectid(1,2)=0.5顧客id性別已婚E71

手機(jī)電池

c11011c20001Objectj2025/2/27?TheInstituteofBusinessIntelligence,HFUT26/104非對(duì)稱的

如果變量的兩個(gè)狀態(tài)不是同樣重要的，則稱該變量是不對(duì)稱的。將比較重要通常也是出現(xiàn)概率比較小的狀態(tài)編碼為1，將另一種狀態(tài)編碼為0。對(duì)于非對(duì)稱的二元變量，采用Jaccard系數(shù)來評(píng)價(jià)兩個(gè)對(duì)象之間的相異度2025/2/27?TheInstituteofBusinessIntelligence,HFUT27/104二元變量二元變量的相異度計(jì)算gender是一個(gè)對(duì)稱的二元變量其它的都是非對(duì)稱的二元變量，根據(jù)Jaccard系數(shù)計(jì)算得：NameGenderFeverCoughTest-1Test-2Test-3Test-4JackM101000MaryF101010JimM1100002025/2/27?TheInstituteofBusinessIntelligence,HFUT28/104標(biāo)稱變量（NominalVariables）標(biāo)稱變量是二元變量的推廣，它可以具有多于兩個(gè)的狀態(tài)，比如變量“學(xué)歷”可以有研究生、本科、本科以下等多種狀態(tài)。有兩種計(jì)算相異度的方法：方法1:簡(jiǎn)單匹配方法m是匹配的數(shù)目,

p是全部變量的數(shù)目方法2:使用二元變量為每一個(gè)狀態(tài)創(chuàng)建一個(gè)新的二元變量，可以用非對(duì)稱的二元變量來編碼標(biāo)稱變量。2025/2/27?TheInstituteofBusinessIntelligence,HFUT29/104顧客id學(xué)歷職業(yè)城市c1本科公務(wù)員合肥c2研究生公務(wù)員合肥c3本科教師六安c4本科以下程序員安慶c5研究生教師六安c6本科程序員安慶c7研究生程序員蚌埠d(1,2)=1/3d(2,3)=3/32025/2/27?TheInstituteofBusinessIntelligence,HFUT30/104標(biāo)稱變量（NominalVariables）顧客id學(xué)歷職業(yè)城市c1本科公務(wù)員合肥c2研究生公務(wù)員合肥c3本科教師六安顧客id本科研究生公務(wù)員教師合肥六安c1101010c2011010c31001012025/2/27?TheInstituteofBusinessIntelligence,HFUT31/104標(biāo)稱變量（NominalVariables）相似度計(jì)算交易ID產(chǎn)品1相機(jī)包，手機(jī)屏幕貼膜，濾鏡2鍵盤保護(hù)膜，遙控器，濾鏡相機(jī)包手機(jī)屏幕貼膜濾鏡鍵盤保護(hù)膜遙控器X111100X2001112025/2/27?TheInstituteofBusinessIntelligence,HFUT32/104聚類算法1.劃分聚類方法2.層次聚類方法3.密度聚類方法2025/2/27?TheInstituteofBusinessIntelligence,HFUT33/104實(shí)例顏色體形毛型類別1黑大卷毛危險(xiǎn)2棕大光滑危險(xiǎn)3棕中卷毛不危險(xiǎn)4黑小卷毛不危險(xiǎn)5棕中光滑危險(xiǎn)6黑大光滑危險(xiǎn)7棕小卷毛危險(xiǎn)8棕小光滑不危險(xiǎn)9棕大卷毛危險(xiǎn)10黑中卷毛不危險(xiǎn)11黑中光滑不危險(xiǎn)12黑小光滑不危險(xiǎn)實(shí)例顏色體形毛型1黑大卷毛2棕大光滑3棕中卷毛4黑小卷毛5棕中光滑6黑大光滑7棕小卷毛8棕小光滑9棕大卷毛10黑中卷毛11黑中光滑12黑小光滑2025/2/27?TheInstituteofBusinessIntelligence,HFUT34/104劃分聚類方法給定一個(gè)有n個(gè)對(duì)象的數(shù)據(jù)集X，劃分聚類技術(shù)將構(gòu)造k個(gè)類，k

n，這k個(gè)類滿足下列條件：每一個(gè)類至少包含一個(gè)對(duì)象。所有類的并集等于X。任意兩個(gè)類的交集為空。每一個(gè)對(duì)象屬于且僅屬于一個(gè)類。最經(jīng)典的劃分算法：k-mean算法2025/2/27?TheInstituteofBusinessIntelligence,HFUT35/104k-means算法，也被稱為k-平均或k-均值算法，是一種使用最廣泛的聚類算法。根據(jù)個(gè)體到每個(gè)類中心的距離進(jìn)行劃分，而類的中心用類中所有個(gè)體的均值來度量。1.Setkasaninteger.2.Selectkdistinctrecordsasinitialmeans,eachrepresentingacluster.3.Foreachrecordindata,calculatethesquaredEuclideandistancesbetweenitandthemeans.Assigntherecordtotheclusterwhosemeanisthenearesttotherecord.4.Afterallrecordsareassignedtoacluster,calculatethenewmeanforeachclusterastheaverageofallrecordsinthecluster.5.Ifthenewmeans

equaltothepreviousmeans,stop,otherwise,gotoStep2.K-means算法2025/2/27?TheInstituteofBusinessIntelligence,HFUT36/104K-means聚類示例2025/2/27?TheInstituteofBusinessIntelligence,HFUT37/104輸入：類的數(shù)目k和包含n個(gè)對(duì)象的數(shù)據(jù)庫。輸出：k個(gè)類，使平方誤差準(zhǔn)則最小。(1)assigninitialvalueformeans;/*任意選擇k個(gè)對(duì)象作為初始的類中心*/(2)REPEAT(3)FORj=1tonDOassigneachxj

totheclosestclusters;(4)FORi=1tokDO /*更新類平均值*/Compute /*計(jì)算準(zhǔn)則函數(shù)E*/(6)UNTILE不再明顯地發(fā)生變化。k-means算法偽代碼2025/2/27?TheInstituteofBusinessIntelligence,HFUT38/104實(shí)例根據(jù)下表數(shù)據(jù)實(shí)施k-means(k=2)聚類個(gè)體12345678屬性112124545屬性2112233442025/2/27?TheInstituteofBusinessIntelligence,HFUT39/104迭代平均值 平均值 產(chǎn)生的新類 新平均值新平均值次數(shù)（類1） （類2） （類1）（類2）

1（1，1）（1，2）234個(gè)體12345678屬性112124545屬性2112233442025/2/27?TheInstituteofBusinessIntelligence,HFUT40/104根據(jù)下表數(shù)據(jù)實(shí)施k-means(k=2)聚類實(shí)例迭代平均值平均值 產(chǎn)生的新類 新平均值新平均值次數(shù)（類1）（類2） （類1）（類2）

1（1，1）（1，2）{1，2}，{3，4，5，6，7，8}（1.5，1）（3.5，3）第一次迭代：假定隨機(jī)選擇的兩個(gè)對(duì)象，如序號(hào)1和序號(hào)3當(dāng)作初始點(diǎn)，分別找到離兩點(diǎn)最近的對(duì)象，并產(chǎn)生兩個(gè)類{1，2}和{3，4，5，6，7，8}。對(duì)于產(chǎn)生的類分別計(jì)算平均值，得到平均值點(diǎn)。對(duì)于{1，2}，平均值點(diǎn)為（1.5，1）；對(duì)于{3，4，5，6，7，8}，平均值點(diǎn)為（3.5，3）。實(shí)例第二次迭代：通過平均值調(diào)整對(duì)象的所在的類，重新聚類，即將所有點(diǎn)按離平均值點(diǎn)（1.5，1）、（3.5，3）最近的原則重新分配。得到兩個(gè)新的類：{1，2，3，4}和{5，6，7，8}。重新計(jì)算類平均值點(diǎn)，得到新的平均值點(diǎn)為（1.5，1.5）和（4.5，3.5）。實(shí)例迭代平均值平均值 產(chǎn)生的新類 新平均值新平均值次數(shù)（類1）（類2） （類1）（類2）

1（1，1）（1，2）{1，2}，{3，4，5，6，7，8}（1.5，1）（3.5，3）2（1.5，1）（3.5，3）{1，2，3，4}，{5，6，7，8}（1.5，1.5）（4.5，3.5）第三次迭代：將所有點(diǎn)按離平均值點(diǎn)（1.5，1.5）和（4.5，3.5）最近的原則重新分配，調(diào)整對(duì)象，類仍然為{1，2，3，4}和{5，6，7，8}，發(fā)現(xiàn)沒有出現(xiàn)重新分配，而且準(zhǔn)則函數(shù)收斂，程序結(jié)束。實(shí)例迭代平均值平均值 產(chǎn)生的新類 新平均值新平均值次數(shù)（類1）（類2） （類1）（類2）

1（1，1）（1，2）{1，2}，{3，4，5，6，7，8}（1.5，1）（3.5，3）（1.5，1）（3.5，3）{1，2，3，4}，{5，6，7，8}（1.5，1.5）（4.5，3.5）3

（1.5，1.5）（4.5，3.5）{1，2，3，4}，{5，6，7，8}（1.5，1.5）（4.5，3.5）2025/2/27?TheInstituteofBusinessIntelligence,HFUT44/104實(shí)例2025/2/27?TheInstituteofBusinessIntelligence,HFUT45/104練習(xí)Supposethatthedataminingtaskistoclusterthefollowingeightpoints(with(x,y)representinglocation)intothreeclusters:

A1(2,10),A2(2,5),A3(8,4),B1(5,8),B2(7,5),B3(6,4),C1(1,2),C2(4,9):ThedistancefunctionisEuclideandistance.SupposeinitiallyweassignA1,B1,andC1asthecenterofeachcluster,respectively.Usethek-meansalgorithmtoshowonly(a)Thethreeclustercentersafterthefirstroundexecution(b)Thefinalthreeclustersk-means算法的性能分析主要優(yōu)點(diǎn)：是解決聚類問題的一種經(jīng)典算法，簡(jiǎn)單、快速。對(duì)處理大數(shù)據(jù)集，該算法是相對(duì)可伸縮和高效率的。當(dāng)數(shù)據(jù)比較密集時(shí)，它的效果較好。主要缺點(diǎn)：在類的平均值被定義的情況下才能使用，可能不適用于某些應(yīng)用。必須事先給出k（要生成的類的數(shù)目），而且對(duì)初值敏感，對(duì)于不同的初始值，可能會(huì)導(dǎo)致不同結(jié)果。不適合于發(fā)現(xiàn)非凸面形狀的類或者大小差別很大的類。而且，它對(duì)于“躁聲”和孤立點(diǎn)數(shù)據(jù)是敏感的。2025/2/27?TheInstituteofBusinessIntelligence,HFUT46/104k-means算法局限非球形的類2025/2/27?TheInstituteofBusinessIntelligence,HFUT47/1042025/2/27?TheInstituteofBusinessIntelligence,HFUT48/104k-means算法局限k-means算法的幾種改進(jìn)方法k-mode算法：實(shí)現(xiàn)對(duì)離散數(shù)據(jù)的快速聚類，保留了k-means算法的效率同時(shí)將k-means的應(yīng)用范圍擴(kuò)大到離散數(shù)據(jù)。k-prototype算法：可以對(duì)離散與數(shù)值屬性兩種混合的數(shù)據(jù)進(jìn)行聚類，在k-prototype中定義了一個(gè)對(duì)數(shù)值與離散屬性都計(jì)算的相異性度量標(biāo)準(zhǔn)。2025/2/27?TheInstituteofBusinessIntelligence,HFUT49/104k-modes算法

k-modes算法把k-means算法擴(kuò)展到可分類數(shù)據(jù)，定義了新的度量可分類數(shù)據(jù)相異度的距離公式，并給出相應(yīng)的更新聚類中心的方式，能夠迅速處理可分類型數(shù)據(jù)。與k-means算法的區(qū)別k-modes算法改變了k-means算法的相異度測(cè)量方法，用一個(gè)簡(jiǎn)單的相異度測(cè)量對(duì)數(shù)據(jù)進(jìn)行聚類。假設(shè)X，Y是數(shù)據(jù)集中的兩個(gè)對(duì)象，它們用m維屬性描述，則這兩個(gè)對(duì)象之間的相異度為：

2025/2/27?TheInstituteofBusinessIntelligence,HFUT50/104與k-means算法的區(qū)別針對(duì)每一個(gè)屬性，取每個(gè)類別中出現(xiàn)頻率最大的一個(gè)屬性值作為該類別中心點(diǎn)的對(duì)應(yīng)屬性值。顧客id年齡收入月消費(fèi)金額c1老年高低c2青年高低c3青年低中c4中年中中c5中年低中c6青年高高c7中年高高顧客id年齡收入月消費(fèi)金額c11.000.800.00c20.120.630.40c30.000.000.50c40.470.200.45c50.260.070.55c60.090.571.00c70.381.000.902025/2/27?TheInstituteofBusinessIntelligence,HFUT51/104k-modes算法

k-prototypes算法在實(shí)際應(yīng)用中，數(shù)據(jù)可能是數(shù)值型的，同時(shí)也有可分類型的。k-prototypes算法綜合了k-means和k-modes算法，采用新的距離度量方法，能夠快速處理混合類型數(shù)據(jù)集的聚類問題。k-prototypes算法的聚類中心由數(shù)值型數(shù)據(jù)的聚類中心和可分類數(shù)據(jù)的聚類中心兩部分加權(quán)組成，其中數(shù)值型屬性的聚類中心和k-means算法類似，通過計(jì)算數(shù)值型屬性的平均值得到。而可分類型屬性的中心采用類似k-modes算法聚類中心的更新方式，通過計(jì)算可分類屬性值出現(xiàn)的頻率確定。2025/2/27?TheInstituteofBusinessIntelligence,HFUT52/104顧客id年齡收入月消費(fèi)金額學(xué)歷職業(yè)c11.000.800.00本科公務(wù)員c20.120.630.40研究生公務(wù)員c30.000.000.50本科教師c40.470.200.45本科以下程序員c50.260.070.55研究生教師c60.090.571.00本科程序員c70.381.000.90研究生程序員2025/2/27?TheInstituteofBusinessIntelligence,HFUT53/104k-prototypes算法k-中心點(diǎn)算法也稱PAM算法（PartitioningAroundMedoids）基于有代表性的數(shù)據(jù)（中心點(diǎn)），而不是均值代表每個(gè)類。思路

1.為每個(gè)類隨機(jī)選擇一個(gè)代表對(duì)象(中心點(diǎn))；

2.剩余的對(duì)象根據(jù)其與代表對(duì)象的距離分配給與其最近的一個(gè)類；

3.反復(fù)地用非代表對(duì)象來替換代表對(duì)象，以提高聚類的質(zhì)量，直至找到最合適的中心點(diǎn)。2025/2/27?TheInstituteofBusinessIntelligence,HFUT54/104k-中心點(diǎn)算法劃分方法仍然基于最小化所有對(duì)象與其對(duì)應(yīng)的參考點(diǎn)之間的相異度之和的原則來執(zhí)行。

通常使用絕對(duì)誤差來度量：

2025/2/27?TheInstituteofBusinessIntelligence,HFUT55/104whereEisthesumoftheabsoluteerrorforallobjectspinthedataset,andoiistherepresentativeobjectofCi.Thisisthebasisforthek-medoidsmethod,whichgroupsnobjectsintokclustersbyminimizingtheabsoluteerrork-中心點(diǎn)算法2025/2/27?TheInstituteofBusinessIntelligence,HFUT56/104為了確定非代表對(duì)象Orandom是否是當(dāng)前對(duì)象Oj

的好的替代，對(duì)于每一個(gè)非代表對(duì)象P，考慮如下四種情況：第一種情況：

P當(dāng)前隸屬于代表對(duì)象Oj。如果Oj

被Orandom所取代作為代表對(duì)象，并且P離其他代表對(duì)象Oi

(i

≠j)最近，則P重新分配給Oi。第二種情況：P當(dāng)前隸屬于代表對(duì)象Oj。如果Oj

被Orandom

所取代作為代表對(duì)象，并且P離Orandom最近，則P

重新分配給Orandom。第三種情況：P當(dāng)前隸屬于代表對(duì)象Oi，i≠j。如果Oj

被Orandom所取代作為代表對(duì)象，并且P仍然離Oi最近，則對(duì)象的隸屬不發(fā)生變化。第四種情況：P當(dāng)前隸屬于代表對(duì)象Oi，i≠j

。如果Oj

被Orandom

所取代作為代表對(duì)象，并且P離Orandom最近，則P

重新分配給Orandom。

k-中心點(diǎn)算法2025/2/27?TheInstituteofBusinessIntelligence,HFUT57/104為了確定非代表對(duì)象Orandom是否是當(dāng)前對(duì)象Oj

的好的替代，對(duì)于每一個(gè)非代表對(duì)象P，考慮如下四種情況：第一種情況：

P當(dāng)前隸屬于代表對(duì)象Oj。如果Oj

被Orandom所取代作為代表對(duì)象，并且P離其他代表對(duì)象Oi

(i

≠j)最近，則將P分配給Oi。第二種情況：P當(dāng)前隸屬于代表對(duì)象Oj。如果Oj

被Orandom

所取代作為代表對(duì)象，并且P離Orandom最近，則P

重新分配給Orandom。第三種情況：P當(dāng)前隸屬于代表對(duì)象Oi，i≠j。如果Oj

被Orandom所取代作為代表對(duì)象，并且P仍然離Oi最近，則對(duì)象的隸屬不發(fā)生變化。第四種情況：P當(dāng)前隸屬于代表對(duì)象Oi，i≠j

。如果Oj

被Orandom

所取代作為代表對(duì)象，并且P離Orandom最近，則P

重新分配給Orandom。

OrandomOjPOi

1.分配給Oi

k-中心點(diǎn)算法2025/2/27?TheInstituteofBusinessIntelligence,HFUT58/104為了確定非代表對(duì)象Orandom是否是當(dāng)前對(duì)象Oj

的好的替代，對(duì)于每一個(gè)非代表對(duì)象P，考慮如下四種情況：第二種情況：P當(dāng)前隸屬于代表對(duì)象Oj。如果Oj被Orandom所取代作為代表對(duì)象，并且P離Orandom最近，則將P分配給Orandom。第三種情況：P當(dāng)前隸屬于代表對(duì)象Oi，i≠j。如果Oj

被Orandom所取代作為代表對(duì)象，并且P仍然離Oi最近，則對(duì)象的隸屬不發(fā)生變化。第四種情況：P當(dāng)前隸屬于代表對(duì)象Oi，i≠j

。如果Oj

被Orandom

所取代作為代表對(duì)象，并且P離Orandom最近，則P

重新分配給Orandom。

OrandomOjPOi

2.分配給Orandom

k-中心點(diǎn)算法2025/2/27?TheInstituteofBusinessIntelligence,HFUT59/104為了確定非代表對(duì)象Orandom是否是當(dāng)前對(duì)象Oj

的好的替代，對(duì)于每一個(gè)非代表對(duì)象P，考慮如下四種情況：第三種情況：P當(dāng)前隸屬于代表對(duì)象Oi，i≠j。如果Oj被Orandom所取代作為代表對(duì)象，并且P仍然離Oi最近，則對(duì)象P的隸屬不發(fā)生變化。第四種情況：P當(dāng)前隸屬于代表對(duì)象Oi，i≠j

。如果Oj

被Orandom

所取代作為代表對(duì)象，并且P離Orandom最近，則P

重新分配給Orandom。

OrandomOjPOi

3.

P隸屬關(guān)系不變k-中心點(diǎn)算法2025/2/27?TheInstituteofBusinessIntelligence,HFUT60/104為了確定非代表對(duì)象Orandom是否是當(dāng)前對(duì)象Oj

的好的替代，對(duì)于每一個(gè)非代表對(duì)象P，考慮如下四種情況：第四種情況：P當(dāng)前隸屬于代表對(duì)象Oi，i≠j。如果Oj被Orandom所取代作為代表對(duì)象，并且P離Orandom最近，則將P分配給Orandom。

OrandomOjPOi

4.將P分配給Orandom

算法:

PAM（k-中心點(diǎn)算法）輸入：簇的數(shù)目k和包含n個(gè)對(duì)象的數(shù)據(jù)庫。輸出：k個(gè)簇，使得所有對(duì)象與其最近中心點(diǎn)的相異度總和最小。（1）任意選擇k個(gè)對(duì)象作為初始的簇中心點(diǎn)；（2）REPEAT（3）指派每個(gè)剩余的對(duì)象給離它最近的中心點(diǎn)所代表的簇；（4）REPEAT（5）選擇一個(gè)未被選擇的中心點(diǎn)Oj；（6）REPEAT（7）選擇一個(gè)未被選擇過的非中心點(diǎn)對(duì)象Orandom；（8）用Orandom代替Oj，并進(jìn)行調(diào)整；（9）計(jì)算用Orandom代替Oj的總代價(jià)記錄在S(絕對(duì)誤差值的差)中；（10）UNTIL

所有的非中心點(diǎn)都被選擇過；（11）UNTIL

所有的中心點(diǎn)都被選擇過；（12）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)的集合；（13）UNTIL沒有再發(fā)生簇的重新分配，即所有的S都大于0.2025/2/27?TheInstituteofBusinessIntelligence,HFUT61/104實(shí)例

假如空間中的五個(gè)點(diǎn)｛A、Ｂ、Ｃ、Ｄ、Ｅ｝如圖所示，各點(diǎn)之間的距離關(guān)系如表所示，根據(jù)所給的數(shù)據(jù)對(duì)其運(yùn)行PAM算法實(shí)現(xiàn)劃分聚類（設(shè)k=2）。樣本點(diǎn)間距離如下表所示:樣本點(diǎn)ABCDEA01223B10243C22015D24103E335302025/2/27?TheInstituteofBusinessIntelligence,HFUT62/104聚類算法1.劃分聚類方法2.層次聚類方法3.密度聚類方法2025/2/27?TheInstituteofBusinessIntelligence,HFUT63/104層次聚類方法層次聚類方法對(duì)給定的數(shù)據(jù)集進(jìn)行層次的分解，直到某種條件滿足為止。具體可分為：凝聚的層次聚類：一種自底向上的策略，首先將每個(gè)對(duì)象作為一個(gè)類，然后合并這些原子類為越來越大的類，直到某個(gè)終結(jié)條件被滿足。分裂的層次聚類：采用自頂向下的策略，它首先將所有對(duì)象置于一個(gè)類中，然后逐漸細(xì)分為越來越小的類，直到達(dá)到了某個(gè)終結(jié)條件。層次凝聚的代表是AGNES算法，層次分裂的代表是DIANA算法。2025/2/27?TheInstituteofBusinessIntelligence,HFUT64/1042025/2/27?TheInstituteofBusinessIntelligence,HFUT65/104層次聚類方法常用類間距離最短距離法最長(zhǎng)距離法平均距離法重心法2025/2/27?TheInstituteofBusinessIntelligence,HFUT66/104層次凝聚AGNES算法AGNES(AgglomerativeNesting)算法最初將每個(gè)對(duì)象作為一個(gè)類，然后這些類根據(jù)某些準(zhǔn)則被一步步地合并。兩個(gè)類間的相似度由這兩個(gè)不同類中距離最近的數(shù)據(jù)點(diǎn)對(duì)的相似度來確定。聚類的合并過程反復(fù)進(jìn)行直到所有的對(duì)象最終滿足類數(shù)目。2025/2/27?TheInstituteofBusinessIntelligence,HFUT67/104算法

:

AGNES（自底向上凝聚算法）輸入：包含n個(gè)對(duì)象的數(shù)據(jù)庫，終止條件類的數(shù)目k。輸出：k個(gè)類，達(dá)到終止條件規(guī)定類數(shù)目。步驟：(1)將每個(gè)對(duì)象當(dāng)成一個(gè)初始類；(2)REPEAT(3)根據(jù)兩個(gè)類中最近的數(shù)據(jù)點(diǎn)找到最近的兩個(gè)類；(4)合并兩個(gè)類，生成新的類的集合；(5)UNTIL達(dá)到預(yù)先定義的類的數(shù)目；2025/2/27?TheInstituteofBusinessIntelligence,HFUT68/104實(shí)例個(gè)體12345678屬性111223344屬性2121245452025/2/27?TheInstituteofBusinessIntelligence,HFUT69/104第1步：根據(jù)初始類計(jì)算每個(gè)類之間的距離，隨機(jī)找出距離最小的兩個(gè)類，進(jìn)行合并，最小距離為1，將1，2點(diǎn)合并為一個(gè)類。2025/2/27?TheInstituteofBusinessIntelligence,HFUT70/104實(shí)例個(gè)體12345678屬性111223344屬性212124545步驟最近的類距離 最近的兩個(gè)類 合并后的新類 1 1 {1}，{2} {1，2}，{3}，{4}，{5}，{6}，{7}，{8}

步驟最近的類距離 最近的兩個(gè)類 合并后的新類 1 1 {1}，{2} {1，2}，{3}，{4}，{5}，{6}，{7}，{8}2 1 {3}，{4} {1，2}，{3，4}，{5}，{6}，{7}，{8}

第2步：對(duì)上一次合并后的類計(jì)算類間距離，找出距離最近的兩個(gè)類進(jìn)行合并，合并后3，4點(diǎn)成為一類。2025/2/27?TheInstituteofBusinessIntelligence,HFUT71/104個(gè)體12345678屬性111223344屬性212124545實(shí)例步驟最近的類距離 最近的兩個(gè)類 合并后的新類 1 1 {1}，{2} {1，2}，{3}，{4}，{5}，{6}，{7}，{8}2 1 {3}，{4} {1，2}，{3，4}，{5}，{6}，{7}，{8}3 1 {5}，{6} {1，2}，{3，4}，{5，6}，{7}，{8}

第3步：重復(fù)第2步的工作，5，6點(diǎn)成為一類。2025/2/27?TheInstituteofBusinessIntelligence,HFUT72/104個(gè)體12345678屬性111223344屬性212124545實(shí)例步驟最近的類距離 最近的兩個(gè)類 合并后的新類 1 1 {1}，{2} {1，2}，{3}，{4}，{5}，{6}，{7}，{8}2 1 {3}，{4} {1，2}，{3，4}，{5}，{6}，{7}，{8}3 1 {5}，{6} {1，2}，{3，4}，{5，6}，{7}，{8}4 1 {7}，{8} {1，2}，{3，4}，{5，6}，{7，8}

第4步：重復(fù)第2步的工作，7，8點(diǎn)成為一類。2025/2/27?TheInstituteofBusinessIntelligence,HFUT73/104個(gè)體12345678屬性111223344屬性212124545實(shí)例步驟最近的類距離 最近的兩個(gè)類 合并后的新類 1 1 {1}，{2} {1，2}，{3}，{4}，{5}，{6}，{7}，{8}2 1 {3}，{4} {1，2}，{3，4}，{5}，{6}，{7}，{8}3 1 {5}，{6} {1，2}，{3，4}，{5，6}，{7}，{8}4 1 {7}，{8} {1，2}，{3，4}，{5，6}，{7，8}5 1 {1，2}，{3，4} {1，2，3，4}，{5，6}，{7，8}

第5步：合并{1，2}，{3，4}成為一個(gè)包含四個(gè)點(diǎn)的類。2025/2/27?TheInstituteofBusinessIntelligence,HFUT74/104個(gè)體12345678屬性111223344屬性212124545實(shí)例步驟最近的類距離 最近的兩個(gè)類 合并后的新類 1 1 {1}，{2} {1，2}，{3}，{4}，{5}，{6}，{7}，{8}2 1 {3}，{4} {1，2}，{3，4}，{5}，{6}，{7}，{8}3 1 {5}，{6} {1，2}，{3，4}，{5，6}，{7}，{8}4 1 {7}，{8} {1，2}，{3，4}，{5，6}，{7，8}5 1 {1，2}，{3，4} {1，2，3，4}，{5，6}，{7，8}6 1 {5，6}，{7，8} {1，2，3，4}，{5，6，7，8}結(jié)束

第6步：合并{5，6}，{7，8}，由于合并后的類的數(shù)目已經(jīng)達(dá)到了用戶輸入的終止條件程序結(jié)束。2025/2/27?TheInstituteofBusinessIntelligence,HFUT75/104個(gè)體12345678屬性111223344屬性212124545實(shí)例123456786543212025/2/27?TheInstituteofBusinessIntelligence,HFUT76/104步驟最近的類距離 最近的兩個(gè)類 合并后的新類 1 1 {1}，{2} {1，2}，{3}，{4}，{5}，{6}，{7}，{8}2 1 {3}，{4} {1，2}，{3，4}，{5}，{6}，{7}，{8}3 1 {5}，{6} {1，2}，{3，4}，{5，6}，{7}，{8}4 1 {7}，{8} {1，2}，{3，4}，{5，6}，{7，8}5 1 {1，2}，{3，4} {1，2，3，4}，{5，6}，{7，8}6 1 {5，6}，{7，8} {1，2，3，4}，{5，6，7，8}結(jié)束

實(shí)例AGNES算法的性能分析優(yōu)點(diǎn)AGNES算法比較簡(jiǎn)單。問題合并點(diǎn)選擇的困難。假如一旦一組對(duì)象被合并，下一步的處理將在新生成的類上進(jìn)行。

已做處理不能撤消，聚類之間也不能交換對(duì)象。不具有很好的可伸縮性，因?yàn)楹喜⒌臎Q定需要檢查和估算大量的對(duì)象或類。2025/2/27?TheInstituteofBusinessIntelligence,HFUT77/104DIANA算法DIANA(DivisiveAnalysis)算法是典型的分裂聚類方法。在聚類中，用戶定義希望得到的類數(shù)目作為一個(gè)結(jié)束條件。同時(shí)，它使用下面兩種測(cè)度方法：類的直徑：Max{類中的任意兩個(gè)數(shù)據(jù)點(diǎn)的距離}。平均相異度（平均距離）：2025/2/27?TheInstituteofBusinessIntelligence,HFUT78/104算法：DIANA（自頂向下分裂算法）輸入：包含n個(gè)對(duì)象的數(shù)據(jù)庫，終止條件類的數(shù)目k。輸出：k個(gè)類，達(dá)到終止條件規(guī)定類數(shù)目。步驟：（1）將所有對(duì)象整個(gè)當(dāng)成一個(gè)初始類；（2）FOR（i=1;i≠k;i++)DOBEGIN（3）在所有類中挑出具有最大直徑的類C；（4）找出C中與其它點(diǎn)平均相異度最大的一個(gè)點(diǎn)p,并把p放入splintergroup，剩余的放在oldparty中；（5）REPEAT（6）將oldparty中滿足下列條件的點(diǎn)加入splintergroup：

這些點(diǎn)到splintergroup的距離小于到oldparty的距離。（7）UNTIL沒有新的oldparty的點(diǎn)被分配給splintergroup；（8）splintergroup和oldparty為被選中的類分裂成的兩個(gè)類，與其它類一起組成新的類集合。（9）END.DIANA算法2025/2/27?TheInstituteofBusinessIntelligence,HFUT79/1042025/2/27?TheInstituteofBusinessIntelligence,HFUT80/104DIANA算法實(shí)例序號(hào)屬性1屬性2 1 1 12 1 23 2 14 2 25 3 46 3 57 4 48 4 5 2025/2/27?TheInstituteofBusinessIntelligence,HFUT81/104第1步：找到具有最大直徑的類，對(duì)類中的每個(gè)點(diǎn)計(jì)算平均相異度（假定采用是歐式距離）。

1的平均距離：（1+1+1.414+3.6+4.24+4.47+5）/7=2.96

2的平均距離為2.526；3的平均距離為2.68；4的平均距離為2.18；5的平均距離為2.18；6的平均距離為2.68；7的平均距離為2.526；8的平均距離為2.96。2025/2/27?TheInstituteofBusinessIntelligence,HFUT82/104序號(hào)屬性1屬性21 1 12 1 23 2 14 2 25 3 46 3 57 4 48 4 5 實(shí)例步驟 具有最大直徑的類 splintergroup Oldparty 1 {1，2，3，4，5，6，7，8} {1} {2，3，4，5，6，7，8}第2步：在oldparty里找出到splintergroup的距離小于到oldparty的距離的點(diǎn)，將該點(diǎn)放入splintergroup中，該點(diǎn)是2。2025/2/27?TheInstituteofBusinessIntelligence,HFUT83/104序號(hào)屬性1屬性21 1 12 1 23 2 14 2 25 3 46 3 57 4 48 4 5 實(shí)例步驟 具有最大直徑的類 splintergroup Oldparty 1 {1，2，3，4，5，6，7，8} {1} {2，3，4，5，6，7，8}2 {1，2，3，4，5，6，7，8} {1，2} {3，4，5，6，7，8} 第3步：重復(fù)第2步的工作，splintergroup中放入點(diǎn)3。2025/2/27?TheInstituteofBusinessIntelligence,HFUT84/104序號(hào)屬性1屬性21 1 12 1 23 2 14 2 25 3 46 3 57 4 48 4 5 實(shí)例步驟 具有最大直徑的類 splintergroup Oldparty 1 {1，2，3，4，5，6，7，8} {1} {2，3，4，5，6，7，8}2 {1，2，3，4，5，6，7，8} {1，2} {3，4，5，6，7，8} 3 {1，2，3，4，5，6，7，8} {1，2，3} {4，5，6，7，8} 第4步：重復(fù)第2步的工作，splintergroup中放入點(diǎn)4。2025/2/27?TheInstituteofBusinessIntelligence,HFUT85/104序號(hào)屬性1屬性21 1 12 1 23 2 14 2 25 3 46 3 57 4 48 4 5 實(shí)例步驟 具有最大直徑的類 splintergroup Oldparty 1 {1，2，3，4，5，6，7，8} {1} {2，3，4，5，6，7，8}2 {1，2，3，4，5，6，7，8} {1，2} {3，4，5，6，7，8} 3 {1，2，3，4，5，6，7，8} {1，2，3} {4，5，6，7，8} 4 {1，2，3，4，5，6，7，8} {1，2，3，4} {5，6，7，8} 第5步：沒有在oldparty中的點(diǎn)放入了splintergroup中且達(dá)到終止條件（k=2），程序終止。如果沒有到終止條件，應(yīng)該從分裂好的類中選一個(gè)直徑最大的類繼續(xù)分裂。2025/2/27?TheInstituteofBusinessIntelligence,HFUT86/104序號(hào)屬性1屬性21 1 12 1 23 2 14 2 25 3 46 3 57 4 48 4 5 實(shí)例步驟 具有最大直徑的類 splintergroup Oldparty 1 {1，2，3，4，5，6，7，8} {1} {2，3，4，5，6，7，8}2 {1，2，3，4，5，6，7，8} {1，2} {3，4，5，6，7，8} 3 {1，2，3，4，5，6，7，8} {1，2，3} {4，5，6，7，8} 4 {1，2，3，4，5，6，7，8} {1，2，3，4} {5，6，7，8} 5 {1，2，3，4，5，6，7，8} {1，2，3，4} {5，6，7，8}終止聚類算法1.劃分聚類方法2.層次聚類方法3.密度聚類方法2025/2/27?TheInstituteofBusinessIntelligence,HFUT87/104基于密度的聚類指導(dǎo)思想只要一個(gè)區(qū)域中的點(diǎn)的密度大于某個(gè)閾值，就把它加到與之相近的聚類中去。這類算法能克服基于距離的算法只能發(fā)現(xiàn)“類圓形”的聚類的缺點(diǎn)，可發(fā)現(xiàn)任意形狀的聚類，且對(duì)噪聲數(shù)據(jù)不敏感。2025/2/27?TheInstituteofBusinessIntelligence,HFUT88/104DBSCAN（Density-BasedSpatialClusteringofApplicationswithNoise）一個(gè)比較有代表性的基于密度的聚類算法。與劃分和層次聚類方法不同，它將類定義為密度相連的點(diǎn)的最大集合，能夠把具有足夠高密度的區(qū)域劃分為類，并可在有“噪聲”的空間數(shù)據(jù)庫中發(fā)現(xiàn)任意形狀的聚類。DBSCAN算法2025/2/27?TheInstituteofBusinessIntelligence,HFUT89/104定義1對(duì)象的ε鄰域：給定對(duì)象半徑ε內(nèi)的區(qū)域。定義2核心對(duì)象：如果一個(gè)對(duì)象的ε鄰域至少包含最小

數(shù)目MinPts個(gè)對(duì)象，則稱該對(duì)象為核心對(duì)象。

2025/2/27?TheInstituteofB