數(shù)據(jù)挖掘與數(shù)據(jù)分析：基于R語言- 課件 第8、9章 層次聚類、k均值聚類

DataMiningandDataAnalysiswithR數(shù)據(jù)挖掘與數(shù)據(jù)分析：基于R語言合作QQ：243001978第八章層次聚類合作QQ：243001978算法原理01算法示例02模型理解03R語言編程04章節(jié)內(nèi)容8.1

算法原理圖8-1層次聚類樹狀圖和嵌套簇圖聚類分析是一種典型的無監(jiān)督學(xué)習(xí)，將未知類別的樣本按照一定的規(guī)則劃分成不同的類或簇，從而揭示樣本之間的內(nèi)在性質(zhì)和相互之間的聯(lián)系。聚類被廣泛應(yīng)用于醫(yī)學(xué)、生物學(xué)、市場營銷、心理學(xué)和數(shù)據(jù)挖掘等領(lǐng)域。層次聚類是最常用的聚類方法之一，它通過計算不同類別數(shù)據(jù)點間的相似度來創(chuàng)建一棵有層次的嵌套聚類樹，如圖8-1所示。自下而上的凝聚法（Agglomerative）和自頂向下的分裂法（Divisive）是兩種層次聚類的基本方法。凝聚層次聚類凝聚層次聚類是一種常見的聚類方法，從單個樣本點作為類開始，不斷合并最相似的兩個類，直到所有類聚成一類為止。算法步驟如下：①定義每個觀測值（樣本點）為一類；②計算任意兩類之間的距離，度量樣本間的相似度；③合并距離最近（相似度最高）的兩個類；④重復(fù)步驟②和③，直到所有類合并為一類。在上述過程中，最重要的環(huán)節(jié)是計算樣本點間、類之間的距離，下面將介紹具體距離度量準(zhǔn)則。凝聚層次聚類

凝聚層次聚類類之間距離度量：最小距離：將兩個類中距離最近的樣本間的距離定義為兩個聚類間的距離。最大距離：將兩個類中距離最遠(yuǎn)的樣本間的距離定義為兩個聚類間的距離。凝聚層次聚類

凝聚層次聚類

分裂層次聚類合作QQ：243001978分裂層次聚類先將所有樣本作為一類，然后找出類中距離最遠(yuǎn)的兩個簇并進行分裂，不斷重復(fù)直到每個樣本為一類。算法步驟如下：①定義所有觀測值（樣本點）為一類；②計算任意兩樣本點之間的距離；③找出同一類中距離最遠(yuǎn)的兩個樣本點a和b，分別作為兩個簇的中心；④若類中剩余的樣本點距離類中心a更近，將其分配到以a為中心的類中，否則分配到以b為中心的類中；⑤重復(fù)步驟③和④，直到每個觀測值為一類。8.2

算法示例圖8-65個二維點的集合例8-1：使用最小距離度量類之間的相似度，對如圖8-2的樣本數(shù)據(jù)進行凝聚層次聚類。點X坐標(biāo)Y坐標(biāo)p10.410.53p20.340.28p30.670.43p40.160.38p50.450.30表8-15個點的坐標(biāo)p1p2p3p4p5p10.0000.2600.2790.2920.233p20.2600.0000.3620.2060.112p30.2790.3620.0000.5120.256p40.2920.2060.5120.0000.301p50.2330.1120.2560.3010.000表8-25個點的歐式距離矩陣8.2

算法示例p1p2p3p4p5p10.0000.2600.2790.2920.233p20.2600.0000.3620.2060.112p30.2790.3620.0000.5120.256p40.2920.2060.5120.0000.301p50.2330.1120.2560.3010.000

p1{p2,p5}p3p4p10.0000.2330.2790.292{p2,p5}0.2330.0000.2560.206p30.2790.2560.0000.512p40.2920.2060.5120.000更新2.繼續(xù)找出距離最近的兩個簇{p2,p5}和p4，合并為{p2,p4,p5}，并更新距離矩陣。p1{p2,p5}p3p4p10.0000.2330.2790.292{p2,p5}0.2330.0000.2560.206p30.2790.2560.0000.512p40.2920.2060.5120.000更新p1{p2,p4,p5}p3p10.0000.2330.279{p2,p4,p5}0.2330.0000.256p30.2790.2560.0008.2

算法示例3.接著繼續(xù)找出距離最近的兩個簇{p2,p4,p5}和p1，合并為{p1,p2,p4,p5}，更新距離矩陣。4.最后合并剩下的兩個簇，即獲得最終結(jié)果，如下圖所示。在樹狀圖中兩個簇合并處的高度反映兩個簇的距離，例如p2和p5間距離為0.112，即為樹狀圖中兩個簇合并時對應(yīng)的高度。更新p1{p2,p4,p5}p3p10.0000.2330.279{p2,p4,p5}0.2330.0000.256p30.2790.2560.000{p1,p2,p4,p5}p3{p1,p2,p4,p5}0.0000.256p30.2560.000圖8-7凝聚層次聚類結(jié)果8.2

算法示例例8-2：使用最小距離度量類之間的相似度，對如圖8-2的樣本數(shù)據(jù)（例8-1中的相同數(shù)據(jù)）進行分裂層次聚類，過程如下：將所有樣本點聚為一類{p1,p2,p3,p4,p5}找出距離最遠(yuǎn)的兩點p3、p4作為兩個子類的中心，并根據(jù)距離最近原則將剩余點分配到這兩個子類。此時，將原本類分裂為{p1,p3,p5}和{p2,p4}對每個子類，再執(zhí)行分裂過程，直至所有樣本點均屬于一類，結(jié)束圖8-65個二維點的集合p1p2p3p4p5p10.0000.2600.2790.2920.233p20.2600.0000.3620.2060.112p30.2790.3620.0000.5120.256p40.2920.2060.5120.0000.301p50.2330.1120.2560.3010.000表8-25個點的歐式距離矩陣8.2

算法示例例8-2：使用最小距離度量類之間的相似度，對如圖8-2的樣本數(shù)據(jù)（例8-1中的相同數(shù)據(jù)）進行分裂層次聚類，結(jié)果如下圖所示：圖8-8分裂層次聚類結(jié)果8.3

模型理解層次聚類的優(yōu)點：層次聚類中距離和相似度容易定義，算法相對簡單。適用于任意形狀和任意屬性的數(shù)據(jù)集。層次聚類不需要預(yù)先指定聚類數(shù)，能夠得到不同粒度上的多層次聚類結(jié)構(gòu)?？梢允褂脴湫螆D對聚類結(jié)果進行可視化，易于解釋和理解。對樣本的輸入順序不敏感。層次聚類的缺點：算法時間復(fù)雜度較大。過程具有不可逆性，一旦合并或分裂執(zhí)行，就不能修正。如果某個合并或分裂決策在后來證明是不好的選擇，該方法無法退回并更正。合并或分裂需要檢查和估算大量的對象或簇，不具有很好的可伸縮性。距離度量的選擇最小和最大距離代表簇間距離度量的兩個極端，它們對離群點或噪聲數(shù)據(jù)過分敏感。使用平均距離和質(zhì)心距離是對最小和最大距離之間的一種折中方法，而且可以克服離群點敏感性問題。盡管質(zhì)心距離計算簡單，但平均距離既能處理數(shù)值數(shù)據(jù)又能處理分類數(shù)據(jù)，具有一定優(yōu)勢。8.4R語言編程game_df<-read.csv("./game.csv",header=TRUE,sep=",")str(game_df)輸出:

數(shù)據(jù)簡介：本案例采用北美和歐洲以及其他地區(qū)的游戲發(fā)行量情況數(shù)據(jù)集，其中包含游戲發(fā)行商（例如任天堂、索尼等），及不同類型游戲的銷量和評分等級等詳細(xì)信息。主要目的是分析2000年以來不同年份發(fā)售的游戲間的相似性及差異性。數(shù)據(jù)導(dǎo)入：使用read.csv()函數(shù)讀取原始數(shù)據(jù)集game.csv，并通過str()函數(shù)查看詳細(xì)信息，代碼如下：數(shù)據(jù)導(dǎo)入屬性名稱屬性解釋屬性示例Name游戲名稱NewSuperMarioBros.platform所支持平臺DSYear_of_Release發(fā)行年份2006Genre游戲類型PlatformPublisher游戲發(fā)行商NintendoNA_Sales北美銷量11.28EU_Sales歐洲銷量9.14JP_Sales日本銷量6.5Other_Sales其他地區(qū)銷量2.88Global_Sales全球總銷量29.8Critic_Score測評師評分89Critic_Count評分測評師數(shù)量65User_Score用戶評分8.5User_Count評分用戶數(shù)量431Developer游戲開發(fā)者NintendoRating游戲分級E數(shù)據(jù)集屬性的解釋表格匯總：數(shù)據(jù)預(yù)處理將發(fā)布年份從字符串轉(zhuǎn)換為數(shù)值刪除缺失值過濾發(fā)布時間早于2000年的數(shù)據(jù)game_df$Year_of_Release<-suppressWarnings(as.numeric(as.character(game_df$Year_of_Release)))game_df<-na.omit(game_df)game_df<-subset(game_df,game_df$Year_of_Release>=2000)summary(game_df)輸出:聚類分組層次聚類方法：hclust(d,method=…)參數(shù)method表示類之間相似性的度量方法，包括："single"、"complete"、"average"、"centroid"和"ward"距離計算方法：dist(x,method=…)參數(shù)method含義同上，可取值為"euclidean"、"maximum"、"manhattan"、"minkowski"、"canberra"和"binary"，且默認(rèn)為歐式距離。聚類分組聚類代碼和結(jié)果game<-game_df[,6:14]#抽取銷量和評分?jǐn)?shù)據(jù)set.seed(1234)game<-game[sample(nrow(game),20),]#隨機抽取20個數(shù)據(jù)game<-matrix(unlist(game),nrow=20)#轉(zhuǎn)換成matrixgame.scale<-scale(game)#數(shù)據(jù)標(biāo)準(zhǔn)化distance<-dist(game.scale)fit.average<-hclust(distance,method="average")plot(fit.average,hang=-1)輸出:圖8-11不同年份游戲發(fā)售數(shù)量的相似性及差異性結(jié)果分析選擇聚類數(shù)為4，并對結(jié)果進行觀察第一類有14個觀測值：{9,18,12,5,16,2,14,11,13,6,20,19,1,8}第二類有4個觀測值：{3,17,4,10}

第三類有1個觀測值：{7}第四類有1個觀測值：{15}clusters<-cutree(fit.average,4)#輸出每一類內(nèi)樣本的數(shù)量table(clusters)輸出:結(jié)果分析獲取每類的中位數(shù)，包括原始數(shù)據(jù)和標(biāo)準(zhǔn)化數(shù)據(jù)兩種度量形式aggregate(as.data.frame(game),by=list(cluster=clusters),FUN=median,na.rm=TRUE)aggregate(as.data.frame(game.scale),by=list(cluster=clusters),FUN=median,na.rm=TRUE)輸出:結(jié)果分析使用rect.hclust()函數(shù)疊加四類，重新繪制樹狀圖plot(fit.average,hang=-1)rect.hclust(fit.average,k=4)輸出:圖8-13不同年份游戲發(fā)售數(shù)量平均距離聚類結(jié)果分析聚類結(jié)果總結(jié)第一類游戲比較小眾，但較受用戶歡迎。其在各地銷量較低，但用戶和測評師對游戲的評分都比較高；第二類游戲銷量和評分都比較低，不被大多數(shù)用戶喜愛；第三類游戲比較受歡迎，游戲銷售量和評分都比較高；第四類游戲銷量一般，但用戶評分比較高，也是受小眾用戶喜歡的游戲。本章小結(jié)首先詳細(xì)介紹了層次聚類算法原理，包括凝聚法和分裂法；隨后通過示例講解兩種算法的運行過程；接著，為了加深讀者對層次聚類的理解，介紹了層次聚類的優(yōu)缺點以及距離度量的選擇；最后利用R語言對層次聚類過程進行實踐。DataMiningandDataAnalysiswithR數(shù)據(jù)挖掘與數(shù)據(jù)分析：基于R語言合作QQ：243001978第九章K均值聚類合作QQ：243001978算法原理01算法示例02模型理解03R語言編程04章節(jié)內(nèi)容9.1

算法原理K均值聚類是經(jīng)典的劃分聚類算法，是一種迭代的聚類分析算法，在迭代過程中不斷移動聚類中心，直到聚類準(zhǔn)則函數(shù)收斂為止，迭代步驟如下：①隨機選擇K個點作為質(zhì)心；②將每個數(shù)據(jù)對象劃分到距離最近的質(zhì)心所在的類中；③計算每個類中數(shù)據(jù)對象的均值作為新的質(zhì)心；④重復(fù)步驟②和③,直到質(zhì)心不再發(fā)生變化或達到最大迭代次數(shù)。最優(yōu)K值選取

最優(yōu)K值選取手肘法SSE和K值關(guān)系示例圖：

從上圖目測,肘部對應(yīng)的K值為4,即為最佳聚類數(shù)。當(dāng)目測法難以識別肘部位置時，可以通過觀測斜率、斜率變化量等指標(biāo)進行定量判斷。最優(yōu)K值選取

最優(yōu)K值選取

距離度量

K均值算法延伸K-Means++：對K均值算法隨機初始化質(zhì)心的過程進行優(yōu)化，使初始質(zhì)心的選擇更合理，從而提升算法收斂速度。elkanK-Means：利用兩邊之和大于第三邊，以及兩邊之差小于第三邊的三角形性質(zhì)，來減少距離的計算，相較于傳統(tǒng)的K-Means迭代速度有很大的提高。MiniBatchK-Means：使用樣本集中的部分樣本來做傳統(tǒng)的K-Means，這樣可以避免樣本量太大時的計算難題，算法收斂速度大大加快，但聚類的精確度也會有所降低。為了增加算法的準(zhǔn)確性，一般會運行多次MiniBatchK-Mean算法，并選擇其中最優(yōu)的聚類簇。9.2

算法示例例9-1：對如下年齡數(shù)據(jù)進行聚類：[14,15,16,18,18,20,21,21,23,28,34,40,43,49,60,61]。K值設(shè)定為2，隨機選擇16和23作為兩個質(zhì)心，使用歐式距離。步驟如下：（1）計算距離，并進行第一次迭代將各樣本點劃分到距離最近的質(zhì)心所在的類（Group）中，并更新各個聚類的質(zhì)心（Mean），得到以下分類結(jié)果：141516181820212123283440434960611621022455712182427334445239875532205111720263738表9-1各樣本點與質(zhì)心的距離矩陣Group1(16)Group2(23)Mean1(16)Mean2(23)[14,15,16,18,18][20,21,21,23,28,34,40,43,49,60,61]16.236.36表9-2第一次迭代結(jié)果9.2

算法示例（2）將兩個分組中樣本數(shù)據(jù)的均值作為新的質(zhì)心，并重復(fù)之前步驟Group1(16.2)Group2(36.36)Mean1(16.2)Mean2(36.36)[14,15,16,18,18,20,21,21,23][28,34,40,43,49,60,61]18.445表9-3第二次迭代結(jié)果Group1(18.4)Group2(45)Mean1(18.4)Mean2(45)[14,15,16,18,18,20,21,21,23,28][34,40,43,49,60,61]19.447.83表9-4第三次迭代結(jié)果Group1(19.4)Group2(47.83)Mean1(19.4)Mean2(47.83)[14,15,16,18,18,20,21,21,23,28][34,40,43,49,60,61]19.447.83表9-5第四次迭代結(jié)果9.2

算法示例（3）算法終止條件：新求得的質(zhì)心和原質(zhì)心相同，如表9-5所示。最終，得到以下兩類：Group1(19.4)=[14,15,16,18,18,20,21,21,23,28]Group2(47.83)=[34,40,43,49,60,61]Group1(19.4)Group2(47.83)Mean1(19.4)Mean2(47.83)[14,15,16,18,18,20,21,21,23,28][34,40,43,49,60,61]19.447.83表9-5第四次迭代結(jié)果9.3

模型理解K均值聚類優(yōu)點：聚類效果較優(yōu)。原理比較簡單，比較容易實現(xiàn)，收斂速度快。算法可解釋性比較強。K均值聚類缺點：K值選取不當(dāng)可能會導(dǎo)致較差的聚類結(jié)構(gòu)。采用迭代方法，得到的結(jié)果只是局部最優(yōu)，在大規(guī)模數(shù)據(jù)上收斂較慢。如果各隱含類別的數(shù)據(jù)不均衡，會導(dǎo)致聚類效果不佳。不適合發(fā)現(xiàn)非凸面形狀的簇，或者大小差別很大的簇。對噪聲點和異常點比較敏感。初始聚類中心的選擇很大程度上會影響聚類效果。9.4R語言編程案例使用R語言內(nèi)置的iris數(shù)據(jù)集，忽略種類變量Species，對150種鳶尾花植物樣本進行K均值聚類分析，數(shù)據(jù)集情況如下：#R編程示例-iris數(shù)據(jù)集head(iris)輸出:

屬性名稱屬性解釋屬性示例Sepal.Length花瓣長度5.1Sepal.Width花瓣寬度3.5Petal.Length花萼長度1.4Petal.Width花萼寬度0.2Species所屬物種setosa表9-6iris數(shù)據(jù)屬性解釋數(shù)據(jù)預(yù)處理對花瓣長度、花瓣寬度、花萼長度和花萼寬度四種屬性進行z-score標(biāo)準(zhǔn)化處理df<-scale(iris[1:4])head(df)輸出:

確定最佳K值R語言factoextra包中的fviz_nbclust()函數(shù)可對最佳K值進行選擇

fviz_nbclust(x,FUNcluster=NULL,method=c(“silhouette”,“wss”,),diss=NULL,k.max=10,...)，參數(shù)含義如下：

FUNcluster：用于聚類的函數(shù)，可用的參數(shù)值為：kmeans,cluster::pam,cluster::clara,cluster::fanny,hcut等；method：用于評估最佳簇數(shù)的指標(biāo)；diss：相異性矩陣，由dist()函數(shù)產(chǎn)生的對象，如果設(shè)置為NULL，那么表示使用dist(data,method="euclidean")計算data參數(shù)，得到相異性矩陣；k.max：最大的簇數(shù)量，至少是2。確定最佳K值