R語言大數(shù)據(jù)分析與挖掘 課件 第十章 聚類算法

第10章聚類算法內(nèi)容要點(diǎn)1、了解聚類算法的相關(guān)理論。2、掌握R語言K均值聚類算法建模的方法。3、掌握R語言凝聚式層次聚類算法建模的方法。聚類算法概述K均值聚類算法凝聚式層次聚類算法123聚類算法概述聚類分析（ClusterAnalysis）指將物理或抽象對(duì)象的集合分組為由類似的對(duì)象組成的多個(gè)類的分析過程。聚類結(jié)果一般分為4～6類。聚類分析的目的在于將相似的事物歸類，同一類中的個(gè)體有較大的相似性，不同類的個(gè)體差異性很大。兩個(gè)個(gè)體間（或變量間）的對(duì)應(yīng)程度或聯(lián)系緊密程度可以用兩種方式來測(cè)量。（1）采用描述個(gè)體對(duì)（變量對(duì)）之間的接近程度的指標(biāo)，

例如，“距離”越小的個(gè)體（變量）越具有相似性。（2）采用表示相似程度的指標(biāo)，例如，“相關(guān)系數(shù)”越大的個(gè)體（變量）越具有相似性。聚類算法概述聚類算法的類型（1）層次聚類與劃分聚類：若允許簇具有子簇，則我們得到一個(gè)層次聚類。層次聚類是嵌套簇的集族，組織成一棵樹。劃分聚類簡(jiǎn)單地將數(shù)據(jù)對(duì)象劃分成不重疊的子集（簇），使得每個(gè)數(shù)據(jù)對(duì)象恰在一個(gè)子集中。（2）互斥聚類、重疊聚類與模糊聚類：互斥聚類指每個(gè)對(duì)象都指派到單個(gè)簇。重疊聚類或模糊聚類用來反映一個(gè)對(duì)象同時(shí)屬于多個(gè)組的事實(shí)。在模糊聚類中，每個(gè)數(shù)據(jù)對(duì)象以一個(gè)0和1之間的隸屬權(quán)值屬于每個(gè)簇。每個(gè)對(duì)象與各個(gè)簇的隸屬權(quán)值之和往往是1。（3）完全聚類與部分聚類：完全聚類將每個(gè)對(duì)象指派到一個(gè)簇中。部分聚類中，某些對(duì)象可能不屬于任何組，如一些噪聲對(duì)象。聚類算法概述聚類算法評(píng)估的特點(diǎn)不同聚類算法的目標(biāo)函數(shù)相差比較大，沒有統(tǒng)一的評(píng)價(jià)標(biāo)準(zhǔn)。聚類不像分類有一個(gè)最優(yōu)化目標(biāo)和學(xué)習(xí)過程，聚類只是一個(gè)統(tǒng)計(jì)方法，把相似和不相似的數(shù)據(jù)分開。在很多實(shí)際問題中，聚類僅僅是其中的一步，聚類的目的只是觀察其是否對(duì)最終結(jié)果產(chǎn)生好的影響。在數(shù)據(jù)質(zhì)量高的情況下，一個(gè)好的聚類結(jié)果表明了數(shù)據(jù)中相對(duì)穩(wěn)定的某種模式或者分布，這種現(xiàn)象不會(huì)因?yàn)閭€(gè)別數(shù)據(jù)點(diǎn)的變化而改變，并且能夠盡可能將數(shù)據(jù)分開。12K均值聚類算法K均值聚類算法（K-MeansClusteringAlgorithm）是一種迭代求解的聚類分析算法，其步驟是，預(yù)將數(shù)據(jù)分為K組，則隨機(jī)選取K個(gè)對(duì)象作為初始的聚類中心，然后計(jì)算每個(gè)對(duì)劃分方法概述劃分方法是首先創(chuàng)建K個(gè)劃分，K為要?jiǎng)?chuàng)建的劃分個(gè)數(shù)；然后利用一個(gè)循環(huán)定位技術(shù)將對(duì)象從一個(gè)劃分移到另一個(gè)劃分來幫助改善劃分質(zhì)量。典型的劃分方法包括K-Means、K-Medoids、CLARA、CLARANS、FCM。K均值聚類算法的優(yōu)缺點(diǎn)1．優(yōu)點(diǎn)（1）速度快。（2）計(jì)算簡(jiǎn)便。2．缺點(diǎn)（1）必須提前知道數(shù)據(jù)有多少類/組。（2）K-Medians是K-Means的一種變體，是用數(shù)據(jù)集的中位數(shù)而不是均值來計(jì)算數(shù)據(jù)的中心點(diǎn)。（3）K-Medians計(jì)算中位數(shù)時(shí)需要對(duì)數(shù)據(jù)集中的數(shù)據(jù)進(jìn)行排序，速度相對(duì)于K-Means較慢。K均值聚類算法K均值聚類算法的流程K均值聚類算法，是聚類算法中最為基礎(chǔ)但也最為重要的算法。其算法流程如下。（1）選取數(shù)據(jù)空間中的K個(gè)對(duì)象并將其作為初始中心，每個(gè)對(duì)象代表一個(gè)聚類中心；（2）對(duì)于樣本中的數(shù)據(jù)對(duì)象，根據(jù)它們與這些聚類中心的歐氏距離，以距離最近為準(zhǔn)則，將它們分到距離它們最近的聚類中心（最相似）所對(duì)應(yīng)的類；（3）更新聚類中心，將每個(gè)類別中所有對(duì)象所對(duì)應(yīng)的均值作為該類別的聚類中心，計(jì)算目標(biāo)函數(shù)的值；（4）判斷聚類中心和目標(biāo)函數(shù)的值是否發(fā)生改變，若不變，則輸出結(jié)果，若改變，則返回步驟（2）。K均值聚類算法K均值聚類分析案例以R語言基礎(chǔ)包自帶的鳶尾花（iris）數(shù)據(jù)進(jìn)行K均值聚類分析，代碼如下：K均值聚類算法K均值聚類分析案例以R語言基礎(chǔ)包自帶的鳶尾花（iris）數(shù)據(jù)進(jìn)行K均值聚類分析，輸出結(jié)果為：K均值聚類算法K均值聚類分析案例kmeans模型將數(shù)據(jù)分成了3類，每類的數(shù)量分別為38、62、50，Clustermeans表示的是3個(gè)類別中4個(gè)變量的均值。將分類的結(jié)果進(jìn)行可視化，代碼如下：結(jié)果如圖10-1所示。凝聚式層次聚類算法層次聚類就是通過對(duì)數(shù)據(jù)集按照某種方法進(jìn)行層次分解，直到滿足某種條件為止。按照分類原理的不同，可以分為凝聚和分裂兩種方法。由下向上對(duì)小的類別進(jìn)行聚合，是凝聚式層次聚類；一層一層地進(jìn)行聚類，由上向下把大的類別（Cluster）分割，就是分裂式層次聚類。凝聚式層次聚類概述凝聚式層次聚類是一種自底向上的策略，首先將每個(gè)對(duì)象都作為一個(gè)簇，然后合并這些原子簇為越來越大的簇，直到所有的對(duì)象都在一個(gè)簇中，或者某個(gè)終止條件被滿足，絕大多數(shù)層次聚類方法都屬于這一類，它們只是在簇間相似度的定義上有所不同，簇間相似度也就是鄰近準(zhǔn)則。凝聚式層次聚類算法1．鄰近準(zhǔn)則對(duì)于凝聚式層次聚類，指定簇的鄰近準(zhǔn)則是非常重要的一個(gè)環(huán)節(jié)，有三種最常用的準(zhǔn)則，分別是MAX、MIN和AVERAGE，如圖10-2所示。（1）單鏈（Single-link）：不同簇的兩個(gè)最近的點(diǎn)之間的鄰近度，即MIN；（2）全鏈（Complete-link）：不同簇中兩個(gè)最遠(yuǎn)的點(diǎn)之間的鄰近度，即MAX；（3）組平均（Average-link）：不同簇的所有點(diǎn)對(duì)鄰近度的平均值（平均長(zhǎng)度），即AVERAGE。凝聚式層次聚類算法2．主要問題1）缺乏全局目標(biāo)函數(shù)這種方法產(chǎn)生的聚類算法避開了解決困難的組合優(yōu)化問題。2）如何處理待合并簇的相對(duì)大小這個(gè)問題值適用于涉及求和的簇臨近性方案，如質(zhì)心，Ward方法和組平均。有兩種方法：加權(quán)方法，平等地對(duì)待所有簇；非加權(quán)方法考慮每個(gè)簇的點(diǎn)數(shù)。換言之，平等地對(duì)待不同大小的簇表示賦予不同簇中的點(diǎn)不同的權(quán)值，而考慮簇的大小則賦予不同簇中的點(diǎn)相同的權(quán)值。3）合并決策是最終的凝聚式層次聚類算法趨向于做出好的局部決策，然而，一旦做出合并兩個(gè)簇的決策，以后就不能撤銷了。這種方法阻礙了局部最優(yōu)標(biāo)準(zhǔn)、編程全局最優(yōu)標(biāo)準(zhǔn)。一些試圖克服這個(gè)問題限制的技術(shù)如下。（1）修補(bǔ)層次聚類：移動(dòng)樹的分支以改善全局目標(biāo)函數(shù)。（2）劃分聚類技術(shù)（如K均值）來創(chuàng)建許多小簇，然后從這些小簇出發(fā)進(jìn)行層次聚類。凝聚式層次聚類算法3．算法優(yōu)缺點(diǎn)（1）優(yōu)點(diǎn)：通常，使用這類算法是因?yàn)榛緫?yīng)用需要層次結(jié)構(gòu)，如創(chuàng)建一種分類方法。這些算法能夠產(chǎn)生較高質(zhì)量的聚類。（2）缺點(diǎn)：這類算法的計(jì)算量和存儲(chǔ)需求代價(jià)昂貴。另外，對(duì)于噪聲、高位數(shù)據(jù)，也可能造成問題?？上仁褂闷渌夹g(shù)（如K均值）進(jìn)行部分聚類，這兩個(gè)問題都會(huì)在一定程度上得到解決。凝聚式層次聚類算法凝聚式層次聚類算法流程凝聚式層次聚類算法是一個(gè)迭代的過程，算法流程如下。（1）每次選最近的兩個(gè)簇合并，將這兩個(gè)合并后的簇稱為合并簇。（2）若采用MAX準(zhǔn)則，選擇其他簇與合并簇中離得最遠(yuǎn)的兩個(gè)點(diǎn)之間的距離作為簇之間的鄰近度。若采用MIN準(zhǔn)則，取其他簇與合并簇中離得最近的兩個(gè)點(diǎn)之間的距離作為簇之間的鄰近度。若采用組平均準(zhǔn)則，取其他簇與合并簇所有點(diǎn)之間距離的平均值作為簇之間的鄰近度。（3）重復(fù)步驟（1）和步驟（2），合并至只剩下一個(gè)簇。1凝聚式層次聚類算法凝聚式層次聚類算法流程（續(xù)）在這個(gè)算法中，需注意以下幾點(diǎn)。（1）鄰近度矩陣。鄰近度有許多種定義方式，如歐氏距離，曼哈頓距離，馬氏距離，余弦相似度，Jaccard系數(shù)，Bregman散度等。種類豐富，樣品奇多，根據(jù)不同的需求來選擇最適合的鄰近度，計(jì)算得到相應(yīng)的鄰近度矩陣。（2）簇與簇之間鄰近度的定義。每個(gè)簇中的點(diǎn)數(shù)不一定相等，如何計(jì)算兩個(gè)不同簇之間的鄰近度呢？常用的有三種方法：?jiǎn)捂湥∕IN準(zhǔn)則），全鏈（MAX準(zhǔn)則），組平均技術(shù)。算法流程示例如下。（1）圖10-3是一個(gè)有5個(gè)點(diǎn)的二維坐標(biāo)系。（2）表10-1為這5個(gè)點(diǎn)的歐式距離矩陣。凝聚式層次聚類算法凝聚式層次聚類算法流程（續(xù)）（3）根據(jù)算法流程，先找出距離最近的兩個(gè)簇P3、P4。合并P3、P4為{P3,P4}，根據(jù)MIN原則更新矩陣：MIN.distance({P3,P4},P1)=1.32;MIN.distance({P3,P4},P2)=1.56;MIN.distance({P3,P4},P5)=0.70。表10-2為歐式距離更新矩陣。凝聚式層次聚類算法凝聚式層次聚類算法流程（續(xù)）（4）接著繼續(xù)找出距離最近的兩個(gè)簇：{P3,P4}、P5。合并{P3,P4}、P5為{P3,P4,P5}，根據(jù)MIN原則繼續(xù)更新矩陣：MIN.distance(P1,{P3,P4,P5})=1.32;MIN.distance(P2,{P3,P4,P5})=1.56。表10-3為歐式距離更新矩陣。凝聚式層次聚類算法凝聚式層次聚類算法流程（續(xù)）繼續(xù)找出距離最近的兩個(gè)簇P1、P2。合并P1、P2為{P1,P2}，根據(jù)MIN原則繼續(xù)更新矩陣：MIN.distance({P1,P2},{P3,P4,P5})=1.32。表10-4為歐式距離更新矩陣。凝聚式層次聚類算法凝聚式層次聚類算法流程（續(xù)）（5）最終合并剩下的這兩個(gè)簇即可獲得最終結(jié)果，如圖10-4所示。MAX組平均算法流程與M