聚類分析方法與應(yīng)用

聚類分析方法與應(yīng)用第1頁，課件共71頁，創(chuàng)作于2023年2月本章提綱

聚類分析的基礎(chǔ)理論6.1

聚類分析的方法6.2

應(yīng)用聚類分析方法6.3

小結(jié)6.4第2頁，課件共71頁，創(chuàng)作于2023年2月6.1聚類分析的基礎(chǔ)理論6.1.1聚類分析的定義6.1.2對聚類算法性能的要求第3頁，課件共71頁，創(chuàng)作于2023年2月6.1.1聚類分析的定義聚類（Clustering）是將數(shù)據(jù)劃分成群組的過程。研究如何在沒有訓(xùn)練的條件下把對象化分為若干類。通過確定數(shù)據(jù)之間在預(yù)先制定的屬性上的相似性來完成聚類任務(wù)，這樣最相似的數(shù)據(jù)就聚集成簇（Cluster）。聚類與分類不同，聚類的類別取決于數(shù)據(jù)本身，而分類的類別是由數(shù)據(jù)分析人員預(yù)先定義好的。使用聚類算法的用戶不但需要深刻地了解所用的特殊技術(shù)，而且還要知道數(shù)據(jù)收集過程的細節(jié)及擁有應(yīng)用領(lǐng)域的專家知識。用戶對手頭數(shù)據(jù)了解地越多，用戶越能成功的評估它的真實結(jié)構(gòu)。第4頁，課件共71頁，創(chuàng)作于2023年2月6.1.1聚類分析的定義聚類分析方法可以應(yīng)用在數(shù)據(jù)挖掘的各個過程之中，比如在數(shù)據(jù)預(yù)處理操作中，針對數(shù)據(jù)需求，對于數(shù)據(jù)結(jié)構(gòu)簡單或者是與運量分析有單屬性和較少屬性關(guān)聯(lián)的數(shù)據(jù)可以在經(jīng)過數(shù)據(jù)清理等預(yù)處理后直接整合入數(shù)據(jù)倉庫。對于復(fù)雜結(jié)構(gòu)的多維數(shù)據(jù)可以通過聚類的方法將數(shù)據(jù)聚集后構(gòu)造出邏輯庫，使復(fù)雜結(jié)構(gòu)數(shù)據(jù)標(biāo)準(zhǔn)化，為某些數(shù)據(jù)挖掘方法（如關(guān)聯(lián)規(guī)則、粗糙集方法）提供預(yù)處理。為了滿足某些數(shù)據(jù)挖掘算法的需要，我們需要對連續(xù)的數(shù)據(jù)進行離散化處理，使條件屬性和決策屬性值簡約化、規(guī)范化。這時我們就需要對數(shù)據(jù)進行聚類處理。第5頁，課件共71頁，創(chuàng)作于2023年2月6.1.2對聚類算法性能的要求

聚類就是將數(shù)據(jù)對象分組成為多個類或簇的過程，在同一個簇中的對象之間具有較高的相似度，而不同簇中的對象差別較大。相似度是根據(jù)描述對象的屬性值來計算的。聚類是經(jīng)常采用的度量方式。聚類分析源于許多研究領(lǐng)域，包括數(shù)據(jù)挖掘、統(tǒng)計學(xué)、生物學(xué)以及機器學(xué)習(xí)等。第6頁，課件共71頁，創(chuàng)作于2023年2月6.1.2對聚類算法性能的要求

1.伸縮性這里的可伸縮性是指算法要能夠處理大數(shù)據(jù)量的數(shù)據(jù)庫對象，比如處理上百萬條記錄的數(shù)據(jù)庫，這就要求算法的時間復(fù)雜度不能太高，最好是多項式時間的算法。值得注意的是，當(dāng)算法不能處理大數(shù)據(jù)量時，用抽樣的方法來彌補也不是一個好主意，因為它通常會導(dǎo)致歪曲的結(jié)果。2.處理不同字段類型的能力算法不僅要能處理數(shù)值型的字段，還要有處理其他類型字段的能力。如布爾型、枚舉型、序數(shù)型及混合型等。第7頁，課件共71頁，創(chuàng)作于2023年2月6.1.2對聚類算法性能的要求

3.發(fā)現(xiàn)具有任意形狀的聚類的能力很多聚類分析算法采用基于歐幾里德距離的相似性度量方法，這一類算法發(fā)現(xiàn)的聚類通常是一些球狀的、大小和密度相近的類，但可以想象，顯示數(shù)據(jù)庫中的聚類可能是任意形狀的，甚至是具有分層樹的形狀，故要求算法有發(fā)現(xiàn)任意形狀的聚類的能力。第8頁，課件共71頁，創(chuàng)作于2023年2月6.1.2對聚類算法性能的要求

4.輸入?yún)?shù)對領(lǐng)域知識的依賴性很多聚類算法都要求用戶輸入一些參數(shù)，例如需要發(fā)現(xiàn)的聚類數(shù)、結(jié)果的支持度及置信度等。聚類分析的結(jié)果通常都對這些參數(shù)很敏感，但另一方面，對于高維數(shù)據(jù)，這些參數(shù)又是相當(dāng)難以確定的。這樣就加重了用戶使用這個工具的負擔(dān)，導(dǎo)致分析的結(jié)果很難控制。一個好的聚類算法應(yīng)當(dāng)針對這個問題，給出一個好的解決方法。第9頁，課件共71頁，創(chuàng)作于2023年2月6.1.2對聚類算法性能的要求

5.能夠處理異常數(shù)據(jù)現(xiàn)實數(shù)據(jù)庫中常常包含有異常數(shù)據(jù)，例如數(shù)據(jù)不完整、缺乏某些字段的值，甚至是包含錯誤數(shù)據(jù)現(xiàn)象。有一些數(shù)據(jù)算法可能會對這些數(shù)據(jù)很敏感，從而導(dǎo)致錯誤的分析結(jié)果。6.結(jié)果對輸入記錄順序的無關(guān)性有些分析算法對記錄的輸入順序是敏感的，即對同一個數(shù)據(jù)集，將它以不同的順序輸入到分析算法，得到的結(jié)果會不同，這是我們不希望的。第10頁，課件共71頁，創(chuàng)作于2023年2月6.1.2對聚類算法性能的要求

7.處理高維數(shù)據(jù)的能力每個數(shù)據(jù)庫或者數(shù)據(jù)倉庫都有很多的字段或者說明，一些分析算法對處理維數(shù)較少的數(shù)據(jù)集時表現(xiàn)不錯，但是對于高維數(shù)據(jù)的聚類分析就會稍顯不足。因為在高維空間中，數(shù)據(jù)的分布是極其稀疏的，而且形狀也可能是極其不規(guī)則的。第11頁，課件共71頁，創(chuàng)作于2023年2月6.1.2對聚類算法性能的要求

8.增加限制條件后的聚類分析能力現(xiàn)實的應(yīng)用中經(jīng)常會出現(xiàn)各種各樣的限制條件，我們希望聚類算法可以在考慮這些限制的情況下，仍舊有很好的表現(xiàn)。9.結(jié)果的可解釋性和可用性聚類的結(jié)果最終都是要面向用戶的，所以結(jié)果應(yīng)該是容易解釋和理解的，并且是可應(yīng)用的。這就要求聚類算法必須與一定的語義環(huán)境及語義解釋相關(guān)聯(lián)。領(lǐng)域知識如何影響聚類分析算法的設(shè)計是很重要的一個研究方面。第12頁，課件共71頁，創(chuàng)作于2023年2月6.2聚類分析的方法6.2.1基于劃分的聚類方法6.2.2基于層次的聚類方法6.2.3基于密度的聚類方法6.2.4基于網(wǎng)格的聚類方法6.2.5基于模型的聚類方法第13頁，課件共71頁，創(chuàng)作于2023年2月6.2.1基于劃分的聚類方法

給定一個含有N個對象的數(shù)據(jù)集，以及要生成的簇的數(shù)目K。每一個分組就代表一個聚類，K<N。這K個分組滿足下列條件：每一個分組至少包含一個數(shù)據(jù)記錄；每一個數(shù)據(jù)記錄屬于且僅屬于一個分組（注意：這個要求在某些模糊聚類算法中可以放寬）。第14頁，課件共71頁，創(chuàng)作于2023年2月6.2.1基于劃分的聚類方法

對于給定的K，算法首先的任務(wù)就是將數(shù)據(jù)構(gòu)建成K個劃分，以后通過反復(fù)迭代從而改變分組的重定位技術(shù)，使得每一次改進之后的分組方案都較前一次好。將對象在不同的劃分間移動，直至滿足一定的準(zhǔn)則。一個好的劃分的一般準(zhǔn)則是：在同一個簇中的對象盡可能“相似”，不同簇中的對象則盡可能“相異”。在劃分方法中，最經(jīng)典的就是k-平均（k-means）算法和k-中心（k-medoids）算法，很多算法都是由這兩個算法改進而來的。第15頁，課件共71頁，創(chuàng)作于2023年2月6.2.1基于劃分的聚類方法

k-means算法只有在平均值被定義的情況下才能使用，因此該算法容易受到孤立點的影響，k-medoids算法采用簇中最中心的位置作為代表點而不是采用對象的平均值。因此，與k-means算法相比，當(dāng)存在噪聲和孤立點數(shù)據(jù)時，k-medoids算法要較k-means算法健壯，而且沒有k-means算法那樣容易受到極端數(shù)據(jù)的影響。、在時間復(fù)雜度上，k-means算法的時間復(fù)雜度為O(nkt)，而k-medoids算法的時間復(fù)雜度大約為O(n2)，后者的執(zhí)行代價要高得多。此外，這兩種方法都要求用戶指定聚類數(shù)目K。第16頁，課件共71頁，創(chuàng)作于2023年2月6.2.1基于劃分的聚類方法

基于劃分的聚類方法優(yōu)點是收斂速度快，缺點是它要求類別數(shù)目K可以合理的估計，并且初始中心的選擇和噪聲會對聚類結(jié)果產(chǎn)生很大影響。第17頁，課件共71頁，創(chuàng)作于2023年2月6.2.2基于層次的聚類方法

基于層次的聚類方法對給定的數(shù)據(jù)進行層次的分解，直到某種條件滿足為止。首先將數(shù)據(jù)對象組成一棵聚類樹，然后根據(jù)層次，自底向上或是自頂向下分解。層次的方法可以分為凝聚的方法和分裂的方法。第18頁，課件共71頁，創(chuàng)作于2023年2月6.2.2基于層次的聚類方法

凝聚的方法，也稱為自底向上的方法，初始時每個對象都被看成是單獨的一個簇，然后通過逐步的合并相近的對象或簇形成越來越大的簇，直到所有的對象都在一個簇中，或者達到某個終止條件為止。層次凝聚的代表是AGNES（AGglomerativeNESting）算法。分裂的方法，也稱為自頂向下的方法，它與凝聚層次聚類恰好相反，初始時將所有的對象置于一個簇中，然后逐漸細分為更小的簇，直到最終每個對象都在單獨的一個簇中，或者達到某個終止條件為止。層次分裂的代表是DIANA（DIvisiveANAlysis）算法。第19頁，課件共71頁，創(chuàng)作于2023年2月6.2.2基于層次的聚類方法

為了改進層次聚類算法的聚類質(zhì)量，新的研究從層次聚類與其他聚類技術(shù)結(jié)合入手，將層次聚類和其他聚類技術(shù)進行集成，形成多階段的聚類。比較常見的方法有四種：BIRCH、CURE、ROCK和CHAMELEON。下面介紹最具代表性的BIRCH算法和CURE算法。第20頁，課件共71頁，創(chuàng)作于2023年2月6.2.2基于層次的聚類方法

BIRCH（BalancedIterativeReducingandClusteringusingHierarchies）算法是一個綜合性的層次聚類方法，它利用層次方法的平衡迭代進行歸約和聚類。其核心是用一個聚類特征三元組表示一個簇的有關(guān)信息，從而使簇中的點可用對應(yīng)的聚類特征表示。它通過構(gòu)造滿足分支因子和簇直徑限制的聚類特征樹來求聚類。該算法通過聚類特征可以方便地進行中心、半徑、直徑及類內(nèi)、類間距離的運算。第21頁，課件共71頁，創(chuàng)作于2023年2月6.2.2基于層次的聚類方法

該算法的優(yōu)點是具有對象數(shù)目的線性易伸縮性及良好的聚類質(zhì)量，一次掃描就可以進行較好的聚類，其計算復(fù)雜度為O(n)，n是對象的數(shù)目。缺點是BIRCH算法只適用于類的分布呈凸形及球形的情況，對不可視的高維數(shù)據(jù)則是不可行的。第22頁，課件共71頁，創(chuàng)作于2023年2月6.2.2基于層次的聚類方法

CURE（ClusteringUsingREprisentatives）算法中既有層次部分，也有劃分部分，所以CURE是一個綜合性的聚類算法。CURE算法過程為：首先從每個簇中選擇c（常數(shù)）個點，然后通過應(yīng)用收縮因子a，將這些分散的點向簇的質(zhì)心方向收縮。當(dāng)a為1的時候，所有點都收縮成一點，即質(zhì)心。通過多個有代表性的點，簇的形狀可以更好地被表示出來。再使用層次聚類算法中的凝聚算法。在凝聚算法中的每一步，距離最近的代表性點所對應(yīng)的簇將被合并。它們之間的距離被定義為兩個簇中代表性點之間距離的最小值。第23頁，課件共71頁，創(chuàng)作于2023年2月6.2.2基于層次的聚類方法

CURE算法的優(yōu)點是它回避用所有點或單個質(zhì)心來表示一個簇的傳統(tǒng)方法，而是將一個簇用多個具有代表性的點來表示，使CURE可以適應(yīng)非球形的幾何形狀。另外，收縮因子降底了噪音對聚類的影響，從而使CURE對孤立點的處理更加健壯，而且能識別非球形和大小變化比較大的簇，對于大型數(shù)據(jù)庫具有良好的伸縮性。缺點是參數(shù)設(shè)置對聚類結(jié)果有很大的影響，不能處理分類屬性。CURE的復(fù)雜度是O(n)，其中n是對象的數(shù)目。第24頁，課件共71頁，創(chuàng)作于2023年2月6.2.3基于密度的聚類方法

基于密度的方法與其它方法的一個根本區(qū)別是：它不是基于各種各樣的距離的，而是基于密度的，這樣就能克服基于距離的算法只能發(fā)現(xiàn)球狀聚類，對發(fā)現(xiàn)任意形狀的聚類則顯得不足的缺點。基于密度的聚類方法從對象分布區(qū)域的密度著手，對于給定類中的數(shù)據(jù)點，如果在給定范圍的區(qū)域中，對象或數(shù)據(jù)點的密度超過某一閾值就繼續(xù)聚類。這樣通過連接密度較大區(qū)域，就能形成不同形狀的聚類，而且還可以消除孤立點和噪聲對聚類質(zhì)量的影響，發(fā)現(xiàn)任意形狀的簇?；诿芏鹊木垲惙街凶罹叽硇缘氖荄BSCAN算法、OPTICS算法和DENCLUE算法。第25頁，課件共71頁，創(chuàng)作于2023年2月6.2.3基于密度的聚類方法

DBSCAN（Density-BasedSpatialClusteringofApplacationswithNoise）算法可以將足夠高密度的區(qū)域劃分為簇，并可以在帶有“噪聲”的空間數(shù)據(jù)庫中發(fā)現(xiàn)任意形狀的聚類。該算法定義簇為密度相連的點的最大集合。第26頁，課件共71頁，創(chuàng)作于2023年2月6.2.3基于密度的聚類方法

DBSCAN通過檢查數(shù)據(jù)庫中每個點的鄰域來尋找聚類。如果一個點p的鄰域中包含數(shù)據(jù)項的個數(shù)多于最小閾值，則創(chuàng)建一個以p作為核心對象的新簇。然后反復(fù)地尋找從這些核心對象直接密度可達的對象，當(dāng)沒有新的點可以被添加到任何簇時，該過程結(jié)束。不被包含在任何簇中的對象被認(rèn)為是“噪聲”。DBSCAN算法不進行任何的預(yù)處理而直接對整個數(shù)據(jù)集進行聚類操作。第27頁，課件共71頁，創(chuàng)作于2023年2月6.2.3基于密度的聚類方法

DBSCAN算法的優(yōu)點是能夠發(fā)現(xiàn)空間數(shù)據(jù)庫中任意形狀的密度連通集；在給定合適的參數(shù)條件下，能很好地處理噪聲點；對用戶領(lǐng)域知識要求較少；對數(shù)據(jù)的輸入順序不太敏感；適用于大型數(shù)據(jù)庫。缺點是要求事先指定領(lǐng)域和閾值；具體使用的參數(shù)依賴于應(yīng)用的目的。第28頁，課件共71頁，創(chuàng)作于2023年2月6.2.4基于網(wǎng)格的聚類方法

首先將數(shù)據(jù)空間劃分成有限個單元（Cell）的網(wǎng)格結(jié)構(gòu)，所有的處理都是以單個單元為對象，在這個網(wǎng)格結(jié)構(gòu)上進行的。這類方法的主要優(yōu)點就是它的處理速度很快，處理時間獨立于數(shù)據(jù)對象的數(shù)目，僅依賴于量化空間中每一維的單元數(shù)目;聚類的精度取決于單元格的大小，也就是說通常與目標(biāo)數(shù)據(jù)庫中記錄的個數(shù)無關(guān)，只與把數(shù)據(jù)空間分為多少個單元有關(guān)。缺點是只能發(fā)現(xiàn)邊界是水平或垂直的簇，而不能檢測到斜邊界。此外，在處理高維數(shù)據(jù)時，網(wǎng)格單元的數(shù)目會隨著屬性維數(shù)的增長而成指數(shù)增長。第29頁，課件共71頁，創(chuàng)作于2023年2月6.2.4基于網(wǎng)格的聚類方法

常見的基于網(wǎng)格的方法有：STING算法、CLIQUE算法和WAVE-CLUSTER算法。STING利用存儲在網(wǎng)格單元中的統(tǒng)計信息來聚類；WAVE-CLUSTER用一種小波變換的方法來聚類；CLIQUE是在高維數(shù)據(jù)空間中基于網(wǎng)格和密度的聚類方法。第30頁，課件共71頁，創(chuàng)作于2023年2月6.2.4基于網(wǎng)格的聚類方法

STING（STatisticalINformationGrid）算法是一種格的多分辨率聚類技術(shù)，它將空間區(qū)域劃分為矩形單元。針對不同級別的分辨率，通常存在多個級別的矩形單元，這些單元形成了一個層次結(jié)構(gòu)，高層的每個單元被劃分為多個低一層的單元。高層單元的統(tǒng)計參數(shù)可以很容易地從低層單元的計算得到。這些參數(shù)包括：屬性無關(guān)的參數(shù)count，屬性相關(guān)的參數(shù)m（平均值），s（標(biāo)準(zhǔn)偏差），min（最小值），max（最大值），以及該單元中屬性值遵循的分布（Distribution）類型。第31頁，課件共71頁，創(chuàng)作于2023年2月6.2.4基于網(wǎng)格的聚類方法

STING算法效率高，是獨立于查詢的，且利于并行處理和增量更新。但由于STING采用了一個多分辨率的方法來進行聚類分析，聚類的質(zhì)量取決于網(wǎng)格結(jié)構(gòu)的最低層粒度。如果數(shù)據(jù)粒度比較細，處理的代價會明顯增加，而且該算法沒有考慮子單元和其他相鄰單元之間的關(guān)系。盡管該算法處理速度較快，但是可能會降低簇的質(zhì)量和精確性。第32頁，課件共71頁，創(chuàng)作于2023年2月6.2.5基于模型的聚類方法

基于模型的聚類方法試圖優(yōu)化給定的數(shù)據(jù)和某些數(shù)學(xué)模型之間的適應(yīng)性。給每一個聚類假定一個模型，然后去尋找能夠很好的滿足這個模型的數(shù)據(jù)集。這樣一個模型可能是數(shù)據(jù)點在空間中的密度分布函數(shù)或者其它。它的一個潛在的假定就是：目標(biāo)數(shù)據(jù)集是由一系列潛在的概率分布所決定的。在這類算法中，聚類的數(shù)目也根據(jù)統(tǒng)計數(shù)字自動決定，噪聲和孤立點也是通過統(tǒng)計數(shù)字來分析?；谀Ｐ偷木垲惙椒ㄖ饕腥悾航y(tǒng)計學(xué)方法、神經(jīng)網(wǎng)絡(luò)方法以及基于群的聚類方法。第33頁，課件共71頁，創(chuàng)作于2023年2月6.2.5基于模型的聚類方法

1.統(tǒng)計學(xué)方法從統(tǒng)計學(xué)的觀點看，聚類分析是通過數(shù)據(jù)建模簡化數(shù)據(jù)的一種方法。概念聚類就是其中的一種。概念聚類的絕大多數(shù)方法都采用了統(tǒng)計學(xué)的途徑，在決定概念或聚類時，使用概率度量。它將數(shù)據(jù)分成多組，對一組未標(biāo)記的數(shù)據(jù)對象產(chǎn)生一個分類模式，并對每個分類模式給出其特征描述，即每組對象代表了一個概念或類。在這里，聚類質(zhì)量不再只是單個對象的函數(shù)，而是加入了如導(dǎo)出的概念描述的簡單性和一般性等因素。第34頁，課件共71頁，創(chuàng)作于2023年2月6.2.5基于模型的聚類方法

1.統(tǒng)計學(xué)方法COBWEB是一種典型的簡單增量概念聚類算法，以一個分類樹的形式創(chuàng)建層次聚類。它的輸入對象用“分類屬性—值”對來描述。在給定一個新的對象后，COBWEB沿一條適當(dāng)?shù)穆窂较蛳?，修改計?shù)，以尋找可以分類該對象的最好節(jié)點。該判定將對象臨時置于每個節(jié)點，并計算劃分結(jié)果的分類效用。產(chǎn)生最高分類效用的位置應(yīng)當(dāng)是對象節(jié)點的一個好的選擇。第35頁，課件共71頁，創(chuàng)作于2023年2月6.2.5基于模型的聚類方法

1.統(tǒng)計學(xué)方法COBWEB可以自動修正劃分中類的數(shù)目，不需要用戶提供輸入?yún)?shù)。缺點是COBWEB基于這樣一個假設(shè)：在每個屬性上的概率分布是彼此獨立的。但這個假設(shè)并不總是成立。分類樹對于偏斜的輸入數(shù)據(jù)不是高度平衡的，它可能導(dǎo)致時間和空間復(fù)雜性的劇烈變化。COBWEB不適用于聚類大型數(shù)據(jù)庫的數(shù)據(jù)。第36頁，課件共71頁，創(chuàng)作于2023年2月6.2.5基于模型的聚類方法

2.神經(jīng)網(wǎng)絡(luò)方法神經(jīng)網(wǎng)絡(luò)以其分布式存儲、并行協(xié)同處理以及自學(xué)習(xí)等特性被用于聚類分析領(lǐng)域。在聚類分析中經(jīng)常被用到的神經(jīng)網(wǎng)絡(luò)的方法有：Kohonen自組織神經(jīng)網(wǎng)絡(luò)競爭神經(jīng)網(wǎng)絡(luò)自組織共振神經(jīng)網(wǎng)絡(luò)這些方法都涉及有競爭的神經(jīng)單元。第37頁，課件共71頁，創(chuàng)作于2023年2月6.2.5基于模型的聚類方法

2.神經(jīng)網(wǎng)絡(luò)方法競爭學(xué)習(xí)（CompetitiveLearning）采用了若干個單元的層次結(jié)構(gòu)，它們以一種“勝者全取”的方式對系統(tǒng)當(dāng)前處理的對象進行競爭。在一個簇中獲勝的單元成為活躍的，而其他單元是不活躍的。各層之間的連接是激發(fā)式的，即在某個給定層次中的單元可以接收來自低一層次所有單元的輸入。在一層中活動單元的布局代表了高一層的輸入模式。第38頁，課件共71頁，創(chuàng)作于2023年2月6.2.5基于模型的聚類方法

2.神經(jīng)網(wǎng)絡(luò)方法在某個給定層次中，一個簇中的單元彼此競爭，對低一層的輸出模式做出反應(yīng)。一個層次內(nèi)的聯(lián)系是抑制式的，以便在任何簇中只有一個單元是活躍的。獲勝的單元修正它與簇中其他單元連接上的權(quán)重，以便未來它能夠?qū)εc當(dāng)前對象相似或一樣的對象做出較強的反應(yīng)。如果我們將權(quán)重看作定義的一個標(biāo)本，那么新的對象被分配給具有最近標(biāo)本的簇。結(jié)果簇的數(shù)目和每個簇中單元的數(shù)目是輸入?yún)?shù)。第39頁，課件共71頁，創(chuàng)作于2023年2月6.2.5基于模型的聚類方法

2.神經(jīng)網(wǎng)絡(luò)方法在聚類過程結(jié)束時，每個簇可以被看作一個新的“特征”，它檢測對象的某些規(guī)律性。這樣產(chǎn)生的結(jié)果簇可以被看作一個底層特征向高層特征的映射。神經(jīng)網(wǎng)絡(luò)聚類方法與實際的大腦處理有很強的理論聯(lián)系。由于較長的處理時間和數(shù)據(jù)的復(fù)雜性，需要進行進一步的研究來使它適用于大型數(shù)據(jù)庫。第40頁，課件共71頁，創(chuàng)作于2023年2月6.2.5基于模型的聚類方法

3.基于群的聚類方法基于群的聚類方法是進化計算的一個分支。模擬生物界中蟻群、魚群和鳥群在覓食或逃避敵人時的行為。主要分為兩類：一類是蟻群算法或蟻群優(yōu)化（AntColonyOptimization,ACO），另一類稱為粒子群算法（ParticleSwarmOptimization,PSO）。第41頁，課件共71頁，創(chuàng)作于2023年2月6.2.5基于模型的聚類方法

3.基于群的聚類方法蟻群算法是將數(shù)據(jù)挖掘概念和原理與生物界中蟻群行為結(jié)合起來形成的新算法?；谙伻核惴ǖ木垲惙椒◤脑砩峡梢苑譃樗姆N：運用螞蟻覓食的原理，利用信息素來實現(xiàn)聚類；利用螞蟻自我聚集行為來聚類；基于螞蟻堆的形成原理實現(xiàn)數(shù)據(jù)聚類；運用蟻巢分類模型，利用螞蟻化學(xué)識別系統(tǒng)進行聚類。

第42頁，課件共71頁，創(chuàng)作于2023年2月6.2.5基于模型的聚類方法

3.基于群的聚類方法粒子群算法模擬了魚群或鳥群的行為。PSO將群中的個體稱為particles，整個群稱為swarm。要將其應(yīng)用到實際的大規(guī)模數(shù)據(jù)挖掘的聚類分析中還需要做大量研究工作。第43頁，課件共71頁，創(chuàng)作于2023年2月6.3應(yīng)用聚類分析方法6.3.1k-means聚類方法6.3.2k-medoids聚類方法6.3.3AGNES聚類方法6.3.4DIANA聚類方法6.3.5DBSCAN聚類方法第44頁，課件共71頁，創(chuàng)作于2023年2月6.3.1k-means聚類方法k-means算法接受輸入量k，然后將n個數(shù)據(jù)對象劃分為k個聚類以便使得所獲得的聚類滿足：同一聚類中的對象相似度較高，而不同聚類中的對象相似度較小。聚類相似度是利用各聚類中對象的均值所獲得一個“中心對象”（引力中心）來進行計算的。k-means算法的工作過程說明如下：首先從n個數(shù)據(jù)對象任意選擇k個對象作為初始聚類中心；而對于所剩下其它對象，則根據(jù)它們與這些聚類中心的相似度（距離），分別將它們分配給與其最相似的聚類中心所代表的聚類；第45頁，課件共71頁，創(chuàng)作于2023年2月6.3.1k-means聚類方法然后再計算每個所獲新聚類的聚類中心（該聚類中所有對象的均值）；不斷重復(fù)這一過程直到標(biāo)準(zhǔn)測度函數(shù)開始收斂為止。一般都采用均方差作為標(biāo)準(zhǔn)測度函數(shù)，即準(zhǔn)則函數(shù)。k個聚類具有以下特點：各聚類本身盡可能的緊湊，而各聚類之間盡可能的分開。樣本點分類和聚類中心的調(diào)整是迭代交替進行的兩個過程。第46頁，課件共71頁，創(chuàng)作于2023年2月6.3.1k-means聚類方法k-means算法描述：輸入：聚類個數(shù)k，以及包含n個數(shù)據(jù)對象的數(shù)據(jù)庫輸出：滿足方差最小標(biāo)準(zhǔn)的k個聚類處理流程：Step1從n個數(shù)據(jù)對象任意選擇k個對象作為初始聚類中心；Step2根據(jù)簇中對象的平均值，將每個對象重新賦給最類似的簇；Step3更新簇的平均值，即計算每個簇中對象的平均值；Step4循環(huán)Step2到Step3直到每個聚類不再發(fā)生變化為止。第47頁，課件共71頁，創(chuàng)作于2023年2月6.3.1k-means聚類方法定義6.1兩個數(shù)據(jù)對象間的距離1.明氏距離（MinkowskiDistance）

(6.1)這里的xi=(xi1,xi2,...,xip)和xj=(xj1,xj2,...,xjp)是兩個p維的數(shù)據(jù)對象并且ij。第48頁，課件共71頁，創(chuàng)作于2023年2月6.3.1k-means聚類方法2.歐氏距離（EuclideanDistance）當(dāng)明氏距離中q=2時，公式6.1即為歐氏距離。第49頁，課件共71頁，創(chuàng)作于2023年2月6.3.1k-means聚類方法3.馬氏距離(MahalanobisDistance)(6.3)其中，

i,j=1,2,…,p。如果Σ-1存在，則馬氏距離為

(6.4)第50頁，課件共71頁，創(chuàng)作于2023年2月6.3.1k-means聚類方法4.蘭氏距離(CanberraDistance)(6.5)定義6.2準(zhǔn)則函數(shù)

(6.6)設(shè)待聚類的數(shù)據(jù)集為X={x1,x2,...,xn}，將其劃分為k個簇Ci，均值分別為zi，即zi為簇Ci的中心(i=1,2,…,k)。E是所有對象的平方誤差的總和，xX是空間中的點，d(x,zi)為點x與zi間的距離，可以利用明氏、歐氏、馬氏或者蘭氏距離求得。第51頁，課件共71頁，創(chuàng)作于2023年2月6.3.2k-medoids聚類方法圍繞中心的劃分（PartitioningAroundMedoid,PAM）是最早提出的k-medoids算法之一，它選用簇中位置最中心的對象作為代表對象，試圖對n個對象給出k個劃分。代表對象也被稱為是中心點，其他對象則被稱為非代表對象。最初隨機選擇k個對象作為中心點，然后反復(fù)地用非代表對象來代替代表對象，試圖找出更好的中心點，以改進聚類的質(zhì)量。第52頁，課件共71頁，創(chuàng)作于2023年2月6.3.2k-medoids聚類方法在每次迭代中，所有可能的對象對被分析，每個對中的一個對象是中心點，而另一個是非代表對象。對可能的各種組合，估算聚類結(jié)果的質(zhì)量。一個對象Oi可以被使最大平方誤差值E（計算方法如公式6.6所示）減少的對象代替。在一次迭代中產(chǎn)生的最佳對象集合成為下次迭代的中心點。為了判定一個非代表對象Oh是否是當(dāng)前一個代表對象Oi的好的代替，對于每一個非中心點對象Oj，下面的四種情況被考慮：第53頁，課件共71頁，創(chuàng)作于2023年2月6.3.2k-medoids聚類方法第一種情況：假設(shè)Oi被Oh代替作為新的中心點，Oj當(dāng)前隸屬于Oi。如果Oj離某個中心點Om最近，i≠m，那么Oj被重新分配給Om；第二種情況：假設(shè)Oi被Oh代替作為新的中心點，Oj當(dāng)前隸屬于Oi。如果Oj離這個新的中心點Oh最近，那么Oj被重新分配給Oh；第54頁，課件共71頁，創(chuàng)作于2023年2月6.3.2k-medoids聚類方法第三種情況：假設(shè)Oi被Oh代替作為新的中心點，但是Oj當(dāng)前隸屬于另一個中心點對象Om，i≠m。如果Oj依然離Om最近，那對象的隸屬不發(fā)生變化；第四種情況：假設(shè)Oi被Oh代替作為新的中心點，但是Oj當(dāng)前隸屬于另一個中心點對象Om，i≠m。如果Oj離這個新的中心點Oh最近，那么Oj被重新分配給Oh。第55頁，課件共71頁，創(chuàng)作于2023年2月6.3.2k-medoids聚類方法每當(dāng)重新分配發(fā)生時，E所產(chǎn)生的差別對代價函數(shù)會有影響。因此，如果一個當(dāng)前的中心點對象被非中心點對象所代替，代價函數(shù)計算E所產(chǎn)生的差別。替換的總代價是所有非中心點對象所產(chǎn)生的代價之和。如果總代價是負的，那么實際的E將會減少，Oi可以被Oh替代。如果總代價是正的，則當(dāng)前的中心點Oi被認(rèn)為是可以接受的，在本次迭代中沒有變化?？偞鷥r定義如下：

(6.7)其中Cjih表示Oi被Oh替代后產(chǎn)生的代價。第56頁，課件共71頁，創(chuàng)作于2023年2月6.3.2k-medoids聚類方法在PAM算法中，可以把過程分為兩個步驟：（1）建立：隨機尋找k個中心點作為初始的簇中心點。（2）交換：對于所有可能的對象對進行分析，找到交換后可以使平方誤差值E減少的對象，代替原中心點。第57頁，課件共71頁，創(chuàng)作于2023年2月6.3.2k-medoids聚類方法k-medoids算法描述：輸入：聚類個數(shù)k，以及包含n個數(shù)據(jù)對象的數(shù)據(jù)庫輸出：滿足方差最小標(biāo)準(zhǔn)的k個聚類處理流程：Step1從n個數(shù)據(jù)對象任意選擇k個對象作為初始簇中心點；Step2指派每個剩余的對象給離它最近的中心點所代表的簇；Step3選擇一個未被選擇的中心點對象Oi；Step4選擇一個未被選擇過的非中心點對象Oh；Step5計算用Oh替代Oi的總代價并記錄在集合S中；Step6循環(huán)Step4到Step5直到所有的非中心點都被選擇過；Step7循環(huán)Step3到Step6直到所有的中心點都被選擇過；Step8IF在S中的所有非中心點代替所有中心點后計算出的總代價有小于0的存在，THEN找出S的中心點，形成一個新的k個中心點的集合。Step9循環(huán)Step3到Step8直到?jīng)]有再發(fā)生簇的重新分配，即S中所有的元素都大于0。第58頁，課件共71頁，創(chuàng)作于2023年2月6.3.3AGNES聚類方法AGNES算法是凝聚的層次聚類方法。AGNES算法最初將每個對象作為一個簇，然后這些簇根據(jù)某些準(zhǔn)則被一步步地合并。這是一種單鏈接方法，其每個簇可以被簇中所有對象代表，兩個簇間的相似度由這兩個不同簇中距離最近的數(shù)據(jù)點對的相似度來確定。聚類的合并過程反復(fù)進行直到所有的對象最終合并形成一個簇。在聚類中，用戶能定義希望得到的簇數(shù)目作為一個結(jié)束條件。第59頁，課件共71頁，創(chuàng)作于2023年2月6.3.3AGNES聚類方法AGNES算法描述：輸入：包含n個數(shù)據(jù)對象的數(shù)據(jù)庫，終止條件簇的數(shù)目k輸出：達到終止條件規(guī)定的k個簇處理流程：Step1將每個對象當(dāng)成一個初始簇；Step2根據(jù)兩個簇中最近的數(shù)據(jù)點找到最近的兩個簇；Step3合并兩個簇，生成新的簇的集合；Step4循環(huán)Step3到Step4直到達到定義的簇的數(shù)目。第60頁，課件共71頁，創(chuàng)作于2023年2月6.3.4DIANA聚類方法DIANA算法屬于分裂的層次聚類。與凝聚的層次聚類相反，它采用一種自頂向下的策略，它首先將所有對象置于一個簇中，然后逐漸細分為越來越小的簇，直到每個對象自成一簇，或者達到了某個終結(jié)條件，例如達到了某個希望的簇數(shù)目，或者兩個最近簇之間的距離超過了某個閾值。在DIANA方法處理過程中，所有的對象初始都放在一個簇中。根據(jù)一些原則（如簇中最臨近對象的最大歐式距離），將該簇分裂。簇的分裂過程反復(fù)進行，直到最終每個新的簇只包含一個對象。第61頁，課件共71頁，創(chuàng)作于2023年2月6.3.4DIANA聚類方法在聚類中，用戶能定義希望得到的簇數(shù)目作為一個結(jié)束條件。同時，它使用下面兩種測度方法。1.簇的直徑：在一個簇中的任意兩個數(shù)據(jù)點都有一個距離（如歐氏距離），這些距離中的最大值是簇的直徑。2.平均相異度（平均距離）：

(6.8)其中：davg(x,C)表示點x在簇C中的平均相異度，n為簇C中點的個數(shù)，d(x,y)為點x與點y之間的距離（如歐式距離）。第62頁，課件共71頁，創(chuàng)作于2023年2月6.3.4DIANA聚類方法DIANA算法描述：輸入：包含n個數(shù)據(jù)對象的數(shù)據(jù)庫，終止條件簇的數(shù)目k輸出：達到終止條件規(guī)定的k個簇處理流程：Step1將所有對象整個當(dāng)成一個初始簇；Step2在所有簇中挑出具有最大直徑的簇；Step3找出所挑簇里與其他點平均相異度最大的一個點放入splintergroup，剩余的放入oldparty中；Step4在oldparty里找出到splintergroup中點的最近距離不大于到oldparty中點的最近距離的點，并將該點加入splintergroup。Step5循環(huán)Step2到Step4直到?jīng)]有新的oldparty的點分配給splintergroup；Step6splintergroup和oldparty為被選中的簇分裂成的兩個簇，與其他簇一起組成新的簇集合。第63頁，課件共71頁，創(chuàng)作于2023年2月6.3.5DBSCAN聚類方法DBSCAN是一個比較有代表性的基于密度的聚類算法。與劃分和層次聚類方法不同，它將簇定義為密度