數(shù)據(jù)挖掘聚類分析

數(shù)據(jù)挖掘聚類分析第1頁，共74頁，2023年，2月20日，星期五引言“物以類聚，人以群分”。對事物進(jìn)行分類，是人們認(rèn)識事物的出發(fā)點(diǎn)，也是人們認(rèn)識世界的一種重要方法。因此，分類學(xué)已成為人們認(rèn)識世界的一門基礎(chǔ)科學(xué)。在生物、經(jīng)濟(jì)、社會、人口等領(lǐng)域的研究中，存在著大量量化分類研究。例如：在生物學(xué)中，為了研究生物的演變，生物學(xué)家需要根據(jù)各種生物不同的特征對生物進(jìn)行分類。在經(jīng)濟(jì)研究中，為了研究不同地區(qū)城鎮(zhèn)居民生活中的收入和消費(fèi)情況，往往需要劃分不同的類型去研究。在地質(zhì)學(xué)中，為了研究礦物勘探，需要根據(jù)各種礦石的化學(xué)和物理性質(zhì)和所含化學(xué)成分把它們歸于不同的礦石類。在人口學(xué)研究中，需要構(gòu)造人口生育分類模式、人口死亡分類狀況，以此來研究人口的生育和死亡規(guī)律。第2頁，共74頁，2023年，2月20日，星期五但歷史上這些分類方法多半是人們主要依靠經(jīng)驗作定性分類，致使許多分類帶有主觀性和任意性，不能很好地揭示客觀事物內(nèi)在的本質(zhì)差別與聯(lián)系；特別是對于多因素、多指標(biāo)的分類問題，定性分類的準(zhǔn)確性不好把握。為了克服定性分類存在的不足，人們把數(shù)學(xué)方法引入分類中，形成了數(shù)值分類學(xué)。后來隨著多元統(tǒng)計分析的發(fā)展，從數(shù)值分類學(xué)中逐漸分離出了聚類分析方法。隨著計算機(jī)技術(shù)的不斷發(fā)展，利用數(shù)學(xué)方法研究分類不僅非常必要而且完全可能，因此近年來，聚類分析的理論和應(yīng)用得到了迅速的發(fā)展。聚類分析就是分析如何對樣品（或變量-在多元統(tǒng)計中，它就是一個向量）進(jìn)行量化分類的問題。通常聚類分析分為Q型聚類和R型聚類。Q型聚類是對樣品進(jìn)行分類處理，R型聚類是對變量進(jìn)行分類處理。第3頁，共74頁，2023年，2月20日，星期五什么是聚類聚類（clustering）就是將數(shù)據(jù)分組成多個簇（cluster），使得同一個簇的對象之間具有較高的相似度，不同簇的對象相異早在孩提時代，人就通過不斷改進(jìn)下意識中的聚類模式來學(xué)會如何區(qū)分貓和狗、動物和植物第4頁，共74頁，2023年，2月20日，星期五聚類無所不在第5頁，共74頁，2023年，2月20日，星期五聚類無所不在第6頁，共74頁，2023年，2月20日，星期五聚類無所不在第7頁，共74頁，2023年，2月20日，星期五聚類的應(yīng)用領(lǐng)域第8頁，共74頁，2023年，2月20日，星期五有貢獻(xiàn)的領(lǐng)域第9頁，共74頁，2023年，2月20日，星期五什么情況下應(yīng)該聚類第10頁，共74頁，2023年，2月20日，星期五聚類分析原理第11頁，共74頁，2023年，2月20日，星期五第12頁，共74頁，2023年，2月20日，星期五第13頁，共74頁，2023年，2月20日，星期五第14頁，共74頁，2023年，2月20日，星期五第15頁，共74頁，2023年，2月20日，星期五第16頁，共74頁，2023年，2月20日，星期五第17頁，共74頁，2023年，2月20日，星期五聚類與分類第18頁，共74頁，2023年，2月20日，星期五相似性及其度量從復(fù)雜數(shù)據(jù)中提取相對簡單分組結(jié)構(gòu)的主要工作是找到一個“緊密度”或相似性度量“當(dāng)我們看到它的時候，我們即可領(lǐng)會”基于特征來測量相似性產(chǎn)生特征提煉特征規(guī)范化特征減少特征第19頁，共74頁，2023年，2月20日，星期五第20頁，共74頁，2023年，2月20日，星期五測量相似性在選擇相似性度量時摻雜著大量的主觀因素：變量的本質(zhì)（離散的、連續(xù)的、二值的）或測量刻度（標(biāo)稱的、順序的、間隔的、比值的）及主題知識當(dāng)所有項被聚類后，通常用距離表明鄰近度變量通?；谙嚓P(guān)系數(shù)或關(guān)聯(lián)度量而聚合第21頁，共74頁，2023年，2月20日，星期五距離度量的常見計算方法令O1和O2表示客觀世界中的兩個對象，O1和O2之間的距離（相異性）是一個實數(shù)，用distance(O1,O2)或d(O1，O2)明考夫斯基距離第22頁，共74頁，2023年，2月20日，星期五第23頁，共74頁，2023年，2月20日，星期五第24頁，共74頁，2023年，2月20日，星期五（4）冪距離（5）差異百分率第25頁，共74頁，2023年，2月20日，星期五二元屬性對象的相似性當(dāng)項不能用有意義的p維測量表示時，項對之間的比較通常根據(jù)某些特征的存在和缺失完成，相似的項具有更多的共同項引入二元變量來描述是否具有某種特征，若具有該特征變量值為1，否則變量值為0個體對的變量得分計算得分矩陣11的個數(shù)為a10的個數(shù)為b01的個數(shù)為c00的個數(shù)為d第26頁，共74頁，2023年，2月20日，星期五第27頁，共74頁，2023年，2月20日，星期五相似性系數(shù)簡單匹配系數(shù)SMCJaccard系數(shù)Rao系數(shù)第28頁，共74頁，2023年，2月20日，星期五第29頁，共74頁，2023年，2月20日，星期五實例分析第30頁，共74頁，2023年，2月20日，星期五第31頁，共74頁，2023年，2月20日，星期五第32頁，共74頁，2023年，2月20日，星期五第33頁，共74頁，2023年，2月20日，星期五聚類的基本類型第34頁，共74頁，2023年，2月20日，星期五層次聚類自底向上（凝聚）假定所有項屬于一個單獨(dú)簇，然后尋找最佳配對并合并成一個新的簇自頂向下（分裂）開始將所有數(shù)據(jù)看作一個簇，考慮所有可能的方法，將簇一分為二選擇最佳劃分，并遞歸第在這兩個上繼續(xù)劃分第35頁，共74頁，2023年，2月20日，星期五凝聚層次聚類

依靠共同的距離度量，聚類過程從尋找距離最近的簇開始，并把這兩個簇合并為一個簇。在開始時，讓每個對象自成一簇，每個簇都以選定的距離度量定義合并后，如何確定新簇之間的距離？？？單連接（singlelinkage）完全連接（completelinkage）第36頁，共74頁，2023年，2月20日，星期五單連接（最近鄰）兩個簇的距離由不同簇的兩個最近的對象間的距離決定簇的距離是屬于不同簇的兩個樣本間的最近距離d(c1,c2)=min{d(o,O)}第37頁，共74頁，2023年，2月20日，星期五完全連接（最遠(yuǎn)鄰）兩個簇的距離隸屬于不同簇的距離最遠(yuǎn)的兩個對象的距離所決定（最遠(yuǎn)鄰的距離）第38頁，共74頁，2023年，2月20日，星期五組平均兩個簇的距離就是隸屬不同簇的所有對象的距離的平均加權(quán)平均組質(zhì)心加權(quán)組質(zhì)心沃德法第39頁，共74頁，2023年，2月20日，星期五單連接第40頁，共74頁，2023年，2月20日，星期五第41頁，共74頁，2023年，2月20日，星期五第42頁，共74頁，2023年，2月20日，星期五第43頁，共74頁，2023年，2月20日，星期五第44頁，共74頁，2023年，2月20日，星期五完全連接第45頁，共74頁，2023年，2月20日，星期五第46頁，共74頁，2023年，2月20日，星期五第47頁，共74頁，2023年，2月20日，星期五第48頁，共74頁，2023年，2月20日，星期五層次聚類的優(yōu)缺點(diǎn)優(yōu)點(diǎn)可以通過觀察樹狀圖來確定正確的簇數(shù)目層次的本質(zhì)很好地反映了人類對某些領(lǐng)域的直覺樹狀圖的一個潛在應(yīng)用時可以用來檢測離群點(diǎn)缺點(diǎn)有時會表現(xiàn)出無意義的或者不合邏輯的模式無需事先指定簇的數(shù)目層次本質(zhì)很好地反映了人類對某些領(lǐng)域認(rèn)識的直覺可伸縮性不好：時間復(fù)雜性至少為O(n2),n是所有對象的數(shù)量和任何啟發(fā)式搜素算法一樣，局部最優(yōu)是一個問題對結(jié)果的解釋具有主觀性第49頁，共74頁，2023年，2月20日，星期五算法的步驟決定k的取值初始化k個簇中心通過把對象分配給最近的簇中心來確定N個對象的簇隸屬關(guān)系假設(shè)上面所得的隸屬關(guān)系是正確的，重新計算k個簇中心若在最后一次迭代中N個對象無一再改變隸屬關(guān)系，則退出，否則再轉(zhuǎn)第3步第50頁，共74頁，2023年，2月20日，星期五K-means算法基本思想是初始隨機(jī)給定K個簇中心，按照最鄰近原則把待分類樣本點(diǎn)分到各個簇。然后按平均法重新計算各個簇的質(zhì)心，從而確定新的簇心。一直迭代，直到簇心的移動距離小于某個給定的值K-Means聚類算法主要分為三個步驟：

(1)第一步是為待聚類的點(diǎn)尋找聚類中心

(2)第二步是計算每個點(diǎn)到聚類中心的距離，將每個點(diǎn)聚類到離該點(diǎn)最近的聚類中去

(3)第三步是計算每個聚類中所有點(diǎn)的坐標(biāo)平均值，并將這個平均值作為新的聚類中心

反復(fù)執(zhí)行(2)、(3)，直到聚類中心不再進(jìn)行大范圍移動或者聚類次數(shù)達(dá)到要求為止第51頁，共74頁，2023年，2月20日，星期五第52頁，共74頁，2023年，2月20日，星期五第53頁，共74頁，2023年，2月20日，星期五第54頁，共74頁，2023年，2月20日，星期五K-均值非常適合用于產(chǎn)生球狀簇，是數(shù)值的、非監(jiān)督的、非確定的、迭代的表示數(shù)據(jù)點(diǎn)xij到簇中心Cj的距離度量，也指示n個數(shù)據(jù)點(diǎn)及其各自簇中心的距離第55頁，共74頁，2023年，2月20日，星期五第56頁，共74頁，2023年，2月20日，星期五第57頁，共74頁，2023年，2月20日，星期五第58頁，共74頁，2023年，2月20日，星期五第59頁，共74頁，2023年，2月20日，星期五第60頁，共74頁，2023年，2月20日，星期五第61頁，共74頁，2023年，2月20日，星期五第62頁，共74頁，2023年，2月20日，星期五K-中心點(diǎn)與k-均值相同的過程，只有樣本空間中的數(shù)據(jù)點(diǎn)可以作為中心點(diǎn)K-重點(diǎn)店是典型的劃分算法。對于給定的k，采用該算法的目標(biāo)是在數(shù)據(jù)集中尋找k個代表，使得每個對象劃歸到它最鄰近的代表所表示的簇中時，對象和代表的距離最小第63頁，共74頁，2023年，2月20日，星期五算法1）任意選取k個對象作為初始中心點(diǎn)2）Repeat

把剩余對象分配到距離它最近的中心點(diǎn)所在的簇隨機(jī)選擇一個非中心點(diǎn)對象O

計算隨機(jī)用O交換Oj的總代價S

如S<0,則用O交換Oj，形成新的k個中心點(diǎn)的集合

Until無變化發(fā)生3）結(jié)束第64頁，共74頁，2023年，2月20日，星期五工作方式首先在數(shù)據(jù)中為每個簇隨意選一個對象，從而在n個對象中發(fā)現(xiàn)k個簇這些作為代表的對象稱為中心點(diǎn)，其余對象為非中心點(diǎn)計算所有非中心點(diǎn)到每個中心點(diǎn)的距離，并將所有非中心點(diǎn)劃分到距它最近的簇只要聚類結(jié)果可以改善，便不斷地用非中心點(diǎn)代替中心點(diǎn)聚類質(zhì)量通過代價函數(shù)來評價，該代價函數(shù)反映了對象和它所屬簇的代表之間的平均相異性第65頁，共74頁，2023年，2月20日，星期五工作方式1）任意選擇k個代表對象2）計算每對代表對象Oi和非代表兼Oh的TCih3）選擇滿足min(Oi,Oh,TCih)的Oi,Oh對如果最小的TCih為負(fù)，用Oh代替Oi，返回到第2步4）否則，為每個非代表對象尋找最相似對象第66頁，共74頁，2023年，2月20日，星期五現(xiàn)代聚類方法五類：層次方法（BIRCH/CURE/ROCK)劃分方法(K-均值/PAM/CLARA/CLARANS/K-眾數(shù)）基于密度方法基于網(wǎng)格方法基于模型方法第67頁，共74頁，2023年，2月20日，星期五增量聚類現(xiàn)在，有些應(yīng)用涉及到成千上萬個高維數(shù)據(jù)集。由于數(shù)據(jù)集規(guī)模太大，不可能把整個數(shù)據(jù)集儲存在主存儲器里。有三個方法可處理這類數(shù)據(jù)的聚類分析：可以把數(shù)據(jù)集存儲在輔助存儲器里，對數(shù)據(jù)的各個子集進(jìn)行獨(dú)立地聚類，然后合并生成整個數(shù)據(jù)集的聚類，稱為分治方法?？梢允褂迷隽烤垲愃惴ā？梢圆⑿袑崿F(xiàn)聚類算法，并行計算的好處是提高了分治方法的效率。第68頁，共74頁，2023年，2月20日，星期五增量聚類算法的步驟：把第一個數(shù)據(jù)項分配到第一個類里。考慮下一個數(shù)據(jù)項，把它分配到目前某個類中或一個新類中。它基于一些準(zhǔn)則的，例如新數(shù)據(jù)項到目前類的重心的距離。在這種情況下，每次添加一個新數(shù)據(jù)項到一個目前的類中時，需要重新計算重心的值。重復(fù)步驟2，直到所有的數(shù)據(jù)樣本都被聚類完畢。第69頁，共74頁，2023年，2月20日，星期五增量算法是非迭代的，需要主存儲空間非常小，所需要的時間也很少，即使采用迭代算法，所需的計算時間也不會顯著增加。增量聚類存在的一個明顯的缺點(diǎn)：對樣本的順序非常敏感。不同的順序會產(chǎn)生不同的分區(qū)。例如：仍然采用上例的數(shù)據(jù)集。假定樣本的順序是x1,x2,x3,x4,x5，則類相似度閾值水平是δ=3。第70頁，共74頁，2023年，2月20日，星期五第一樣本x1為第一個類C1={x1}。C1的重心為M1={0,2}。開始分析其他樣本。

a)把第二個樣本x2和M1比較，距離d為：

d(x2,M1)=(02+22)1/2=2.0<3

因此，x2屬于類C1

，新的重心是：

M1={0,1}b)第三個樣本x3和重心M1比較：

d(x3,M1)=(1.52+12)1/2=1.8<3x3∈C1→C1={x1,x2,x3}→M1={0.5,0.66}第71頁，共74頁，2023年，2月20日，星期五c)第四個樣本x4和重心M1比較：

d(x4,M1)=(4.52+0.662)1/2=4.55>3x4→C2={x4}→M2={5,0}d)第五個樣本和