數(shù)據(jù)挖掘與商務(wù)智能范勤勤物流研究中心第十章聚類分析1聚類分析2劃分方法3層次方法4基于密度的方法聚類分析聚類分析：基本概念簇：每個(gè)子集是一個(gè)簇簇中的對(duì)象彼此相似與其他簇中的對(duì)象不相似典型應(yīng)用作為一個(gè)獨(dú)立的工具觀察數(shù)據(jù)分布的情況，觀察每個(gè)簇的特點(diǎn)，集中對(duì)特定的某些簇做進(jìn)一步分析作為其他算法（如分類等）的一個(gè)預(yù)處理步驟，這些算法再在生成的簇上進(jìn)行處理聚類分析是一個(gè)把數(shù)據(jù)對(duì)象劃分成子集的過程，由聚類分析產(chǎn)生的簇的集合稱作一個(gè)聚類聚類被稱為無監(jiān)督學(xué)習(xí)，因?yàn)闆]有提供類標(biāo)號(hào)信息4聚類分析：應(yīng)用示例Marketing在商業(yè)上，聚類能幫助市場(chǎng)分析人員從客戶基本庫(kù)中發(fā)現(xiàn)不同的客戶群Biology在生物學(xué)上，聚類能用于推導(dǎo)植物和動(dòng)物的分類，對(duì)基因進(jìn)行分類，獲得對(duì)種群中固有結(jié)構(gòu)的認(rèn)識(shí)Landuse在地球觀測(cè)數(shù)據(jù)庫(kù)中相似地區(qū)的確定5數(shù)據(jù)挖掘?qū)垲惖牡湫鸵罂缮炜s性：在大數(shù)據(jù)集合樣本上進(jìn)行聚類會(huì)導(dǎo)致有偏的結(jié)果處理不同屬性類型的能力：如圖、序列、圖像等發(fā)現(xiàn)任意形狀的簇：許多聚類算法基于歐式或曼哈頓距離，球狀簇對(duì)于確定輸入?yún)?shù)的領(lǐng)域知識(shí)的要求：對(duì)參數(shù)設(shè)定十分敏感處理噪聲數(shù)據(jù)的能力：對(duì)數(shù)據(jù)敏感，可能導(dǎo)致低質(zhì)量的聚類結(jié)果增量聚類（新數(shù)據(jù)）和對(duì)輸入次序不敏感：不能將新數(shù)據(jù)合并到已有的聚類結(jié)構(gòu)中，對(duì)于輸入數(shù)據(jù)的順序是敏感的聚類高維數(shù)據(jù)的能力：高維數(shù)據(jù)有可能是非常稀疏和高度傾斜基于約束的聚類：現(xiàn)實(shí)中有很多約束條件可解釋性和可用性6可以用于比較聚類方法的諸方面劃分準(zhǔn)則分層或不分層相似性度量雖然基于距離的方法常?？梢岳米顑?yōu)化技術(shù)，但是基于密度或基于連通性的方法常常可以發(fā)現(xiàn)任意形狀的簇簇的分離性作為簇的主題可能不是互斥的聚類空間子空間聚類發(fā)現(xiàn)揭示對(duì)象相似性的簇和子空間7基本聚類方法概述劃分方法(Partitioningapproach)基本思想：給定一個(gè)n個(gè)樣本的數(shù)據(jù)庫(kù)，劃分方法將數(shù)據(jù)劃分為k個(gè)劃分（k<=n），每個(gè)劃分表示一個(gè)簇，同時(shí)滿足：（1）每個(gè)簇至少包含一個(gè)樣本；（2）每個(gè)樣本必須屬于且僅屬于一個(gè)層次方法(Hierarchicalapproach)創(chuàng)建給定數(shù)據(jù)對(duì)象集的層次分解8基于密度的方法對(duì)給定簇中的每個(gè)數(shù)據(jù)點(diǎn)，在給定半徑的領(lǐng)域中必須至少包含最少數(shù)目的點(diǎn)9基本聚類方法概述方法一般特點(diǎn)劃分方法發(fā)現(xiàn)球形互斥的簇基于距離可以用均值或中心點(diǎn)等代表簇中心對(duì)中小規(guī)模數(shù)據(jù)集有效層次方法聚類是一個(gè)層次分解（即多層）不能糾正錯(cuò)誤的合并或劃分可以集成其他技術(shù)，如微聚類或考慮對(duì)象“連接”基于密度的方法可以發(fā)現(xiàn)任意形狀的簇簇是對(duì)象空間中被低密度區(qū)域分隔的稠密區(qū)域簇密度：每個(gè)點(diǎn)的“鄰域”內(nèi)必須具有最少個(gè)數(shù)的點(diǎn)可能過濾離群點(diǎn)劃分方法劃分方法給定一個(gè)n個(gè)對(duì)象或元組的數(shù)據(jù)庫(kù)，一個(gè)劃分方法構(gòu)建數(shù)據(jù)的k個(gè)劃分，每個(gè)劃分表示一個(gè)簇，并且k<=n。每個(gè)組至少包含一個(gè)對(duì)象每個(gè)對(duì)象屬于且僅屬于一個(gè)組簇的表示k-平均算法（由簇的平均值來代表整個(gè)簇）k中心點(diǎn)算法（由處于簇的中心區(qū)域的某個(gè)值代表整個(gè)簇）劃分準(zhǔn)則同一個(gè)聚類中的對(duì)象盡可能的接近或相關(guān)，不同聚類中的對(duì)象盡可能的遠(yuǎn)離或不同11K-均值：一種基于形心的技術(shù)假設(shè)數(shù)據(jù)集D包含n個(gè)歐式空間中的對(duì)象，劃分把D中的對(duì)象分配到k個(gè)簇中。簇Ci的質(zhì)量可以用簇內(nèi)變差度量，它是Ci中所有對(duì)象和形心ci之間的誤差的平方和，定義為12K-均值：一種基于形心的技術(shù)算法K-均值。用于劃分的k–均值算法，其中每個(gè)簇的中心都用簇中所有對(duì)象的均值來表示方法從D中任意選擇k個(gè)對(duì)象作為初始簇中心Repeat根據(jù)簇中對(duì)象的均值，將每個(gè)對(duì)象分配到最相似的簇更新簇均值，即重新計(jì)算每個(gè)簇中對(duì)象的均值Until不再發(fā)生變化輸入k：簇的數(shù)目D：包含n個(gè)對(duì)象的數(shù)據(jù)集13K-均值：例子-步驟114k1k2k3XY隨機(jī)選擇3個(gè)簇中心K-均值：例子-步驟215k1k2k3XY分配每個(gè)點(diǎn)到最近的簇中心K-均值：例子-步驟316XY移動(dòng)每個(gè)簇中心到每個(gè)簇的平均位置k1k2k2k1k3k3K-均值：例子-步驟417XY把對(duì)象重新分布到離簇中心最近的簇中k1k2k3K-均值：例子-步驟4…18XYA:threepointswithanimationk1k3k2K-均值：例子-步驟4b19XY重新計(jì)算簇的均值k1k3k2K-均值：例子-步驟520XY把簇的中心移到簇的均值k2k1k3K-均值：缺點(diǎn)21是局部最優(yōu)，不是全局最優(yōu)要求用戶必須事先給出要生成的簇的數(shù)目，選擇初始劃分的最佳方向、更新分區(qū)和停止準(zhǔn)則不適合發(fā)現(xiàn)大小很不相同的簇或具有凹狀的簇算法只有在簇的平均值被定義的情況下才能使用，這不適合涉及有類屬性的數(shù)據(jù)對(duì)噪音和異常點(diǎn)非常敏感孤立點(diǎn)（極大值）的存在，會(huì)大幅度扭曲數(shù)據(jù)的分布K-中心點(diǎn)：一種基于代表對(duì)象的技術(shù)k–中心點(diǎn)聚類：首先為每個(gè)簇隨意選擇選擇一個(gè)代表對(duì)象mediod；剩余的對(duì)象根據(jù)其與代表對(duì)象的距離分配給最近的一個(gè)簇。然后反復(fù)地用非代表對(duì)象來替代代表對(duì)象，以改進(jìn)聚類的質(zhì)量。聚類結(jié)果的質(zhì)量用一個(gè)代價(jià)函數(shù)來估算，該函數(shù)評(píng)估了對(duì)象與其參照對(duì)象之間的平均相異度。圍繞中心點(diǎn)劃分（PAM）與k–均值算法一樣，初始代表對(duì)象任意選取。考慮用一個(gè)非代表對(duì)象替換一個(gè)代表對(duì)象是否能夠提高聚類質(zhì)量PAM在小型數(shù)據(jù)集上運(yùn)行良好，但是不能很好地用于大數(shù)據(jù)集22PAM的改善CLARA：大型應(yīng)用聚類CLARANS：基于隨機(jī)搜索的聚類大型應(yīng)用K-中心點(diǎn)：一種基于代表對(duì)象的技術(shù)23012345678910012345678910K=2任意選取

k個(gè)對(duì)象作為初始medoids將其余對(duì)象分配到最近的medoids所代表的類隨機(jī)選取一非中心對(duì)象,Oramdom計(jì)算交換代價(jià)012345678910012345678910如果聚類質(zhì)量被提高,則代替原medoidDoloopUntilnochange012345678910012345678910層次方法凝聚的與分裂的層次聚類對(duì)給定數(shù)據(jù)對(duì)象集合進(jìn)行層次分解自底向上方法（凝聚）：開始將每個(gè)對(duì)象作為單獨(dú)的一個(gè)組，然后相繼的合并相近的對(duì)象或組，直到所有的組合并為一個(gè)，或者達(dá)到一個(gè)終止條件自頂向下方法（分裂）：開始將所有的對(duì)象置于一個(gè)簇中，在迭代的每一步，一個(gè)簇被分裂為多個(gè)更小的簇，直到最終每個(gè)對(duì)象在一個(gè)單獨(dú)的簇中，或達(dá)到一個(gè)終止條件缺點(diǎn)：合并或分裂的步驟不能被撤銷25層次方法將距離矩陣作為聚類標(biāo)準(zhǔn)這種方法不需要把簇k的數(shù)量作為一個(gè)輸入，但是需要一個(gè)終止條件26Step0Step1Step2Step3Step4bdceaabdecdeabcdeStep4Step3Step2Step1Step0凝聚的(AGNES)分裂的(DIANA)算法方法距離度量最小距離均值距離最大距離平均距離27BIRCH:使用聚類特征樹的多階段聚類BIRCH聚類特征CF=<n，LS,SS>LS表示n個(gè)點(diǎn)的線性和，而SS是數(shù)據(jù)點(diǎn)的平方和采用了一種多階段聚類技術(shù)：數(shù)據(jù)集的單遍掃描產(chǎn)生一個(gè)基本的好聚類，而一或多遍的額外掃描可以進(jìn)一步的改進(jìn)聚類質(zhì)量階段一：BIRCH掃描數(shù)據(jù)庫(kù)，建立一棵存放于內(nèi)存的初始CF-樹，它可以被看做數(shù)據(jù)的多層壓縮，試圖保留數(shù)據(jù)的內(nèi)在聚類結(jié)構(gòu)階段二：BIRCH采用某個(gè)（選定的）聚類算法對(duì)CF樹的葉節(jié)點(diǎn)進(jìn)行聚類，把稀疏的簇當(dāng)作離群點(diǎn)刪除，而把稠密的簇合并為更大的簇2829CF樹結(jié)構(gòu)CF1child1CF3child3CF2child2CF6child6CF1child1CF3child3CF2child2CF5child5CF1CF2CF6prevnextCF1CF2CF4prevnextB=7L=6Non-leafnodeLeafnodeLeafnodeChameleon:使用動(dòng)態(tài)建模的多階段層次聚類Chameleon（變色龍）是一種層次聚類算法，它采用動(dòng)態(tài)建模來確定一對(duì)簇之間的相似度如果兩個(gè)簇的互聯(lián)性都很高并且它們之間又靠的很近就將其合并30概率層次聚類算法層次聚類的缺點(diǎn)很難選擇一個(gè)好的距離度量數(shù)據(jù)對(duì)象不能有缺失的屬性值結(jié)果聚類層次結(jié)構(gòu)的優(yōu)化目標(biāo)可能不清晰概率層次聚類使用概率模型度量簇之間的距離生成模型：把待聚類的數(shù)據(jù)對(duì)象集看做要分析的基礎(chǔ)數(shù)據(jù)生成機(jī)制的一個(gè)樣本聚類的任務(wù)是使用待聚類的觀測(cè)數(shù)據(jù)對(duì)象，盡可能準(zhǔn)確地估計(jì)該生成模型31基于密度的方法基于密度的方法基于距離的聚類方法的缺點(diǎn)只能發(fā)現(xiàn)球狀的簇，難以發(fā)現(xiàn)任意形狀的簇基于密度的據(jù)類只要臨近區(qū)域的密度（對(duì)象或數(shù)據(jù)點(diǎn)的數(shù)目）超過某個(gè)臨界值，就繼續(xù)聚類優(yōu)點(diǎn)：可以過濾掉“噪聲”和“孤立點(diǎn)”，發(fā)現(xiàn)任意形狀的簇33DBSCAN:一種基于高密度連通區(qū)域的基于密度的聚類DBSCAN找出核心對(duì)象，即其鄰域稠密的對(duì)象。它連接核心對(duì)象和它們的鄰域，形成稠密區(qū)域作為簇密度可達(dá)：點(diǎn)p關(guān)于Eps,MinPts是從q密度可達(dá)的,如果存在一個(gè)節(jié)點(diǎn)鏈p1,…,pn,p1=q,pn=p使得pi+1是從pi直接密度可達(dá)的密度相連：點(diǎn)p關(guān)于Eps,MinPts與點(diǎn)q是密度相連的,如果存在點(diǎn)o使得,p和q都是關(guān)于Eps,MinPts是從o密度可達(dá)的34pqopqp1密度可達(dá)密度相連DBSCAN:一種基于高密度連通區(qū)域的基于密度的聚類DBSCAN缺點(diǎn)對(duì)用戶定義的參數(shù)是敏感的，參數(shù)難以確定（特別是對(duì)于高維數(shù)據(jù)，設(shè)置的細(xì)微不同可能導(dǎo)致差別很大的聚類）35OPTICS:通過點(diǎn)排序識(shí)別聚類結(jié)構(gòu)OPTICS:并不顯式地產(chǎn)生數(shù)據(jù)集聚類，而是輸出簇排序這個(gè)排序是所有分析對(duì)象的線性表，并且代表了數(shù)據(jù)的基于密度的聚類結(jié)構(gòu)這個(gè)排序等價(jià)于從廣泛的參數(shù)設(shè)置中得到的基于密度的聚類簇排序可以用來提取基本的聚類信息，導(dǎo)出內(nèi)在的聚類結(jié)構(gòu)，也可以提供聚類的可視化36每個(gè)對(duì)象需要存儲(chǔ)兩個(gè)值對(duì)象p的核心距離(core-distance)是使得p成為核心對(duì)象的最小

。如果p不是核心對(duì)象,p的核心距離沒有定義

對(duì)象q關(guān)于另一個(gè)對(duì)象p的可達(dá)距離(reachability-distance)是p的核心距離和p與q的歐幾里得距離之間的較大值.如果p不是一個(gè)核心對(duì)象,p和q之間的可達(dá)距離沒有定義

OPTICS:通過點(diǎn)排序識(shí)別聚類結(jié)構(gòu)37例:設(shè)

=6(mm),MinPts=5.p的核心距離是p與第四個(gè)最近的數(shù)據(jù)對(duì)象之間的距離

’。q1關(guān)于p的可達(dá)距離是p的核心距離(即

’=3mm),因?yàn)樗葟膒到q1的