ch 聚類(lèi)數(shù)據(jù)挖掘技術(shù)

會(huì)計(jì)學(xué)1ch聚類(lèi)數(shù)據(jù)挖掘技術(shù)聚類(lèi)分析源于許多研究領(lǐng)域，包括數(shù)據(jù)挖掘、統(tǒng)計(jì)學(xué)、機(jī)器學(xué)習(xí)、模式識(shí)別等。作為一個(gè)數(shù)據(jù)挖掘中的一個(gè)功能，聚類(lèi)分析能作為一個(gè)獨(dú)立的工具來(lái)獲得數(shù)據(jù)分布的情況，并且概括出每個(gè)簇的特點(diǎn)，或者集中注意力對(duì)特定的某些簇做進(jìn)一步的分析。數(shù)據(jù)挖掘技術(shù)的一個(gè)突出的特點(diǎn)是處理巨大的、復(fù)雜的數(shù)據(jù)集，這對(duì)聚類(lèi)分析技術(shù)提出了特殊的挑戰(zhàn)，要求算法具有可伸縮性、處理不同類(lèi)型屬性的能力、發(fā)現(xiàn)任意形狀的類(lèi)、處理高維數(shù)據(jù)的能力等。根據(jù)潛在的各項(xiàng)應(yīng)用，數(shù)據(jù)挖掘?qū)垲?lèi)分析方法提出了不同要求。第1頁(yè)/共66頁(yè)二、聚類(lèi)在數(shù)據(jù)挖掘中的典型應(yīng)用：聚類(lèi)分析可以作為其它算法的預(yù)處理步驟：利用聚類(lèi)進(jìn)行數(shù)據(jù)預(yù)處理，可以獲得數(shù)據(jù)的基本概況，在此基礎(chǔ)上進(jìn)行特征抽取或分類(lèi)就可以提高精確度和挖掘效率。也可將聚類(lèi)結(jié)果用于進(jìn)一步關(guān)聯(lián)分析，以獲得進(jìn)一步的有用信息?？梢宰鳛橐粋€(gè)獨(dú)立的工具來(lái)獲得數(shù)據(jù)的分布情況：聚類(lèi)分析是獲得數(shù)據(jù)分布情況的有效方法。通過(guò)觀察聚類(lèi)得到的每個(gè)簇的特點(diǎn)，可以集中對(duì)特定的某些簇作進(jìn)一步分析。這在諸如市場(chǎng)細(xì)分、目標(biāo)顧客定位、業(yè)績(jī)估評(píng)、生物種群劃分等方面具有廣闊的應(yīng)用前景。聚類(lèi)分析可以完成孤立點(diǎn)挖掘：許多數(shù)據(jù)挖掘算法試圖使孤立點(diǎn)影響最小化，或者排除它們。然而孤立點(diǎn)本身可能是非常有用的。如在欺詐探測(cè)中，孤立點(diǎn)可能預(yù)示著欺詐行為的存在。第2頁(yè)/共66頁(yè)廣泛的應(yīng)用領(lǐng)域商務(wù)：幫助市場(chǎng)分析人員從客戶(hù)信息庫(kù)中發(fā)現(xiàn)不同的客戶(hù)群，用購(gòu)買(mǎi)模式來(lái)刻畫(huà)不同的客戶(hù)群的特征土地使用：在地球觀測(cè)數(shù)據(jù)庫(kù)中識(shí)別土地使用情況相似的地區(qū)保險(xiǎn)業(yè)：汽車(chē)保險(xiǎn)單持有者的分組城市規(guī)劃：根據(jù)房子的類(lèi)型，價(jià)值和地理分布對(duì)房子分組生物學(xué)：推導(dǎo)植物和動(dòng)物的分類(lèi)，對(duì)基因進(jìn)行分類(lèi)第3頁(yè)/共66頁(yè)聚類(lèi)分析的目標(biāo)就是形成的數(shù)據(jù)簇，并且滿(mǎn)足下面兩個(gè)條件：一個(gè)簇內(nèi)的數(shù)據(jù)盡量相似（highintra-classsimilarity）；不同簇的數(shù)據(jù)盡量不相似（lowinter-classsimilarity）。衡量一個(gè)聚類(lèi)分析算法質(zhì)量，依靠：相似度測(cè)量機(jī)制是否合適。是否能發(fā)現(xiàn)數(shù)據(jù)背后潛在的、手工難以發(fā)現(xiàn)的類(lèi)知識(shí)。三、聚類(lèi)分析的目標(biāo):第4頁(yè)/共66頁(yè)四、聚類(lèi)分析方法的分類(lèi):按照聚類(lèi)的標(biāo)準(zhǔn)，聚類(lèi)方法可分為如下兩種：統(tǒng)計(jì)聚類(lèi)方法：這種聚類(lèi)方法主要基于對(duì)象之間的幾何距離的。概念聚類(lèi)方法：概念聚類(lèi)方法基于對(duì)象具有的概念進(jìn)行聚類(lèi)。按照聚類(lèi)算法所處理的數(shù)據(jù)類(lèi)型，聚類(lèi)方法可分為三種：數(shù)值型數(shù)據(jù)聚類(lèi)方法：所分析的數(shù)據(jù)的屬性只限于數(shù)值數(shù)據(jù)。離散型數(shù)據(jù)聚類(lèi)方法：所分析的數(shù)據(jù)的屬性只限于離散型數(shù)據(jù)?；旌闲蛿?shù)據(jù)聚類(lèi)方法：能同時(shí)處理數(shù)值和離散數(shù)據(jù)。第5頁(yè)/共66頁(yè)按照聚類(lèi)的尺度，聚類(lèi)方法可被分為以下三種：基于距離的聚類(lèi)算法：用各式各樣的距離來(lái)衡量數(shù)據(jù)對(duì)象之間的相似度，如k-means、k-medoids、BIRCH、CURE等算法?；诿芏鹊木垲?lèi)算法：相對(duì)于基于距離的聚類(lèi)算法，基于密度的聚類(lèi)方法主要是依據(jù)合適的密度函數(shù)等?；诨ミB性(Linkage-Based)的聚類(lèi)算法：通?；趫D或超圖模型。高度連通的數(shù)據(jù)聚為一類(lèi)。第6頁(yè)/共66頁(yè)按照聚類(lèi)聚類(lèi)分析算法的主要思路，可以被歸納為如下幾種。劃分法（PartitioningMethods）：基于一定標(biāo)準(zhǔn)構(gòu)建數(shù)據(jù)的劃分。屬于該類(lèi)的聚類(lèi)方法有：k-means、k-modes、k-prototypes、k-medoids、PAM、CLARA、CLARANS等。層次法（HierarchicalMethods）：對(duì)給定數(shù)據(jù)對(duì)象集合進(jìn)行層次的分解。密度法（density-basedMethods）：基于數(shù)據(jù)對(duì)象的相連密度評(píng)價(jià)。網(wǎng)格法（Grid-basedMethods）：將數(shù)據(jù)空間劃分成為有限個(gè)單元（Cell）的網(wǎng)格結(jié)構(gòu)，基于網(wǎng)格結(jié)構(gòu)進(jìn)行聚類(lèi)。模型法（Model-BasedMethods）：給每一個(gè)簇假定一個(gè)模型，然后去尋找能夠很好的滿(mǎn)足這個(gè)模型的數(shù)據(jù)集。第7頁(yè)/共66頁(yè)五、數(shù)據(jù)相似性的度量---距離距離越大，相似性越小。點(diǎn)間距離與類(lèi)間距離類(lèi)間距離基于點(diǎn)間距離計(jì)算距離函數(shù)應(yīng)同時(shí)滿(mǎn)足

1.d(i,j)≥02.d(i,i)=03.d(i,j)=d(j,i)4.d(i,j)≤d(i,k)+d(k,j)第8頁(yè)/共66頁(yè)常用點(diǎn)間距離—相異度歐式距離城區(qū)距離切比雪夫距離明科夫斯基距離數(shù)據(jù)矢量x=(x1,x2,…xn),y=(y1,y2,…yn)…………….第9頁(yè)/共66頁(yè)常用類(lèi)間距離最短距離法最長(zhǎng)距離法類(lèi)平均法重心法兩個(gè)聚類(lèi)p和q…………….第10頁(yè)/共66頁(yè)六、聚類(lèi)方法劃分方法：構(gòu)造數(shù)據(jù)的最優(yōu)劃分層次方法：對(duì)數(shù)據(jù)進(jìn)行層次分解或合并基于密度的方法：（1）基于密度連通性，如DBSCAN,OPTICS；（2）基于密度分布函數(shù)，如DENCLUE基于網(wǎng)格的方法：采用多分辨率網(wǎng)格數(shù)據(jù)結(jié)構(gòu)，如STING,BANG,CLIQUE,MAFIA基于模型的方法：SOM神經(jīng)網(wǎng)絡(luò)第11頁(yè)/共66頁(yè)(1)劃分方法給定一個(gè)有n個(gè)對(duì)象的數(shù)據(jù)集，劃分聚類(lèi)技術(shù)將構(gòu)造數(shù)據(jù)k個(gè)劃分，每一個(gè)劃分就代表一個(gè)簇，kn。也就是說(shuō)，它將數(shù)據(jù)劃分為k個(gè)簇，而且這k個(gè)劃分滿(mǎn)足下列條件：每一個(gè)簇至少包含一個(gè)對(duì)象。每一個(gè)對(duì)象屬于且僅屬于一個(gè)簇。對(duì)于給定的k，算法首先給出一個(gè)初始的劃分方法，以后通過(guò)反復(fù)迭代的方法改變劃分，使得每一次改進(jìn)之后的劃分方案都較前一次更好。第12頁(yè)/共66頁(yè)啟發(fā)式方法:k-平均算法和k-中心點(diǎn)算法k-均值算法:每個(gè)簇用該簇中對(duì)象的平均值來(lái)表示。k-中心點(diǎn)算法:每個(gè)簇用接近聚類(lèi)中心的一個(gè)對(duì)象來(lái)表示第13頁(yè)/共66頁(yè)k-means算法，也被稱(chēng)為k-平均或k-均值，是一種得到最廣泛使用的聚類(lèi)算法。相似度的計(jì)算根據(jù)一個(gè)簇中對(duì)象的平均值來(lái)進(jìn)行。⑴首先將所有對(duì)象隨機(jī)分配到k個(gè)非空的簇中。⑵計(jì)算每個(gè)簇的平均值，并用該平均值代表相應(yīng)的簇。⑶根據(jù)每個(gè)對(duì)象與各個(gè)簇中心的距離，分配給最近的簇。⑷然后轉(zhuǎn)第二步，重新計(jì)算每個(gè)簇的平均值。這個(gè)過(guò)程不斷重復(fù)直到滿(mǎn)足某個(gè)準(zhǔn)則函數(shù)才停止。K-均值算法第14頁(yè)/共66頁(yè)K-均值聚類(lèi)示例From“DataMining:ConceptsandTechniques”,J.HanandM.Kamber第15頁(yè)/共66頁(yè)算法k-means算法輸入：簇的數(shù)目k和包含n個(gè)對(duì)象的數(shù)據(jù)庫(kù)。輸出：k個(gè)簇，使平方誤差準(zhǔn)則最小。（1)assigninitialvalueformeans;/*任意選擇k個(gè)對(duì)象作為初始的簇中心*/(2)REPEAT(3)FORj=1tonDOassigneachxjtotheclosestclusters;(4)FORi=1tokDO /*更新簇平均值*/(5)Compute /*計(jì)算準(zhǔn)則函數(shù)E*/(6)UNTILE不再明顯地發(fā)生變化。算法首先隨機(jī)地選擇k個(gè)對(duì)象，每個(gè)對(duì)象初始地代表了一個(gè)簇的平均值或中心。對(duì)剩余的每個(gè)對(duì)象根據(jù)其與各個(gè)簇中心的距離，將它賦給最近的簇。然后重新計(jì)算每個(gè)簇的平均值。這個(gè)過(guò)程不斷重復(fù)，直到準(zhǔn)則函數(shù)收斂。準(zhǔn)則函數(shù)試圖使生成的結(jié)果簇盡可能地緊湊和獨(dú)立。第16頁(yè)/共66頁(yè)樣本數(shù)據(jù)序號(hào)屬性1屬性2 11 1 22 1 31 2 42 2 54 3 65 3 74 4 85 4迭代次數(shù)平均值 平均值 產(chǎn)生的新簇 新平均值新平均值（簇1） （簇2） （簇1）（簇2）

1（1，1） （1，2） {1，2}，{3，4，5，6，7，8}（1.5，1）（3.5，3） 2（1.5，1） （3.5，3）{1，2，3，4}，{5，6，7，8}（1.5，1.5）（4.5，3.5） 3（1.5，1.5） （4.5，3.5）{1，2，3，4}，{5，6，7，8}（1.5，1.5）（4.5，3.5） 根據(jù)所給的數(shù)據(jù)通過(guò)對(duì)其實(shí)施k-means(設(shè)n=8，k=2)，其主要執(zhí)行執(zhí)行步驟：第一次迭代：假定隨機(jī)選擇的兩個(gè)對(duì)象，如序號(hào)1和序號(hào)3當(dāng)作初始點(diǎn)，分別找到離兩點(diǎn)最近的對(duì)象，并產(chǎn)生兩個(gè)簇{1，2}和{3，4，5，6，7，8}。對(duì)于產(chǎn)生的簇分別計(jì)算平均值，得到平均值點(diǎn)。對(duì)于{1，2}，平均值點(diǎn)為（1.5，1）（這里的平均值是簡(jiǎn)單的相加除2）；對(duì)于{3，4，5，6，7，8}，平均值點(diǎn)為（3.5，3）。第二次迭代：通過(guò)平均值調(diào)整對(duì)象的所在的簇，重新聚類(lèi)，即將所有點(diǎn)按離平均值點(diǎn)（1.5，1）、（3.5，3）最近的原則重新分配。得到兩個(gè)新的簇：{1，2，3，4}和{5，6，7，8}。重新計(jì)算簇平均值點(diǎn)，得到新的平均值點(diǎn)為（1.5，1.5）和（4.5，3.5）。第三次迭代：將所有點(diǎn)按離平均值點(diǎn)（1.5，1.5）和（4.5，3.5）最近的原則重新分配，調(diào)整對(duì)象，簇仍然為{1，2，3，4}和{5，6，7，8}，發(fā)現(xiàn)沒(méi)有出現(xiàn)重新分配，而且準(zhǔn)則函數(shù)收斂，程序結(jié)束。實(shí)例第17頁(yè)/共66頁(yè)k-means算法的性能分析主要優(yōu)點(diǎn)：是解決聚類(lèi)問(wèn)題的一種經(jīng)典算法，簡(jiǎn)單、快速。對(duì)處理大數(shù)據(jù)集，該算法是相對(duì)可伸縮和高效率的。當(dāng)結(jié)果簇是密集的，它的效果較好。主要缺點(diǎn)在簇的平均值被定義的情況下才能使用，可能不適用于某些應(yīng)用。必須事先給出k（要生成的簇的數(shù)目），而且對(duì)初值敏感，對(duì)于不同的初始值，可能會(huì)導(dǎo)致不同結(jié)果。不適合于發(fā)現(xiàn)非凸面形狀的簇或者大小差別很大的簇。而且，它對(duì)于“躁聲”和孤立點(diǎn)數(shù)據(jù)是敏感的。第18頁(yè)/共66頁(yè)k-means算法的幾種改進(jìn)方法k-mode算法：實(shí)現(xiàn)對(duì)離散數(shù)據(jù)的快速聚類(lèi)，保留了k-means算法的效率同時(shí)將k-means的應(yīng)用范圍擴(kuò)大到離散數(shù)據(jù)。k-prototype算法：可以對(duì)離散與數(shù)值屬性?xún)煞N混合的數(shù)據(jù)進(jìn)行聚類(lèi)，在k-prototype中定義了一個(gè)對(duì)數(shù)值與離散屬性都計(jì)算的相異性度量標(biāo)準(zhǔn)。k-中心點(diǎn)算法k-means算法對(duì)于孤立點(diǎn)是敏感的。為了解決這個(gè)問(wèn)題，不采用簇中的平均值作為參照點(diǎn)，可以選用簇中位置最中心的對(duì)象，即中心點(diǎn)作為參照點(diǎn)。這樣劃分方法仍然是基于最小化所有對(duì)象與其參照點(diǎn)之間的相異度之和的原則來(lái)執(zhí)行的。第19頁(yè)/共66頁(yè)k-中心點(diǎn)算法（k-medoids）也稱(chēng)PAM算法（PartitioningAroundMedoids）

基于有代表性的數(shù)據(jù)（中心點(diǎn)），而不是均值代表每個(gè)簇。思路

1.為每個(gè)簇隨機(jī)選擇一個(gè)代表對(duì)象(中心點(diǎn))；

2.剩余的對(duì)象根據(jù)其與代表對(duì)象的距離分配給與其最近的一個(gè)簇；

3.反復(fù)地用非代表對(duì)象來(lái)替換代表對(duì)象，以提高聚類(lèi)的質(zhì)量，直至找到最合適的中心點(diǎn)。第20頁(yè)/共66頁(yè)P(yáng)AM作為最早提出的k-中心點(diǎn)算法之一，它選用簇中位置最中心的對(duì)象作為代表對(duì)象，試圖對(duì)n個(gè)對(duì)象給出k個(gè)劃分。代表對(duì)象也被稱(chēng)為是中心點(diǎn)，其他對(duì)象則被稱(chēng)為非代表對(duì)象。最初隨機(jī)選擇k個(gè)對(duì)象作為中心點(diǎn)，該算法反復(fù)地用非代表對(duì)象來(lái)代替代表對(duì)象，試圖找出更好的中心點(diǎn)，以改進(jìn)聚類(lèi)的質(zhì)量。在每次迭代中，所有可能的對(duì)象對(duì)被分析，每個(gè)對(duì)中的一個(gè)對(duì)象是中心點(diǎn)，而另一個(gè)是非代表對(duì)象。對(duì)可能的各種組合，估算聚類(lèi)結(jié)果的質(zhì)量。一個(gè)對(duì)象Oi被可以產(chǎn)生最大平方-誤差值減少的對(duì)象代替。在一次迭代中產(chǎn)生的最佳對(duì)象集合成為下次迭代的中心點(diǎn)。第21頁(yè)/共66頁(yè)計(jì)算用非代表對(duì)象h替換代表對(duì)象i的總代價(jià)：?jiǎn)蝹€(gè)數(shù)據(jù)的替換代價(jià)：用h代替i后，j到中心點(diǎn)距離的變化第22頁(yè)/共66頁(yè)為了判定一個(gè)非代表對(duì)象Oh是否是當(dāng)前一個(gè)代表對(duì)象Oi的好的替代，對(duì)于每一個(gè)非中心點(diǎn)對(duì)象Oj，下面的四種情況被考慮:

第一種情況：Oj當(dāng)前隸屬于中心點(diǎn)對(duì)象Oi。如果Oi被Oh所代替作為中心點(diǎn)，且Oj離一個(gè)Om最近，i≠m，那么Oj被重新分配給Om。

第二種情況：Oj當(dāng)前隸屬于中心點(diǎn)對(duì)象Oi。如果Oi被Oh代替作為一個(gè)中心點(diǎn)，且Oj離Oh最近，那么Oj被重新分配給Oh。

第三種情況：Oj當(dāng)前隸屬于中心點(diǎn)Om，m≠i。如果Oi被Oh代替作為一個(gè)中心點(diǎn)，而Oj依然離Om最近，那么對(duì)象的隸屬不發(fā)生變化。

第四種情況：Oj當(dāng)前隸屬于中心點(diǎn)Om，m≠i。如果Oi被Oh代替作為一個(gè)中心點(diǎn)，且Oj離Oh最近，那么Oi被重新分配給Oh。第23頁(yè)/共66頁(yè)每當(dāng)重新分配發(fā)生時(shí)，平方-誤差E所產(chǎn)生的差別對(duì)代價(jià)函數(shù)有影響。因此，如果一個(gè)當(dāng)前的中心點(diǎn)對(duì)象被非中心點(diǎn)對(duì)象所代替，代價(jià)函數(shù)計(jì)算平方-誤差值所產(chǎn)生的差別。替換的總代價(jià)是所有非中心點(diǎn)對(duì)象所產(chǎn)生的代價(jià)之和。如果總代價(jià)是負(fù)的，那么實(shí)際的平方-誤差將會(huì)減小，Oi可以被Oh替代。如果總代價(jià)是正的，則當(dāng)前的中心點(diǎn)Oi被認(rèn)為是可接受的，在本次迭代中沒(méi)有變化?？偞鷥r(jià)定義如下：其中，Cjih表示Oj在Oi被Oh代替后產(chǎn)生的代價(jià)。下面介紹上面所述的四種情況中代價(jià)函數(shù)的計(jì)算公式，其中所引用的符號(hào)有：Oi和Om是兩個(gè)原中心點(diǎn)，Oh將替換Oi作為新的中心點(diǎn)。第24頁(yè)/共66頁(yè)第二種情況

Oj被重新分配給Oh，

Cjih=d(j,h)-d(j,i)第一種情況

Oj被重新分配給Om，Cjih=d(j,m)-d(j,i)第三種情況

Oj的隸屬不發(fā)生變化，Cjih=0

第四種情況

Oi被重新分配給Oh，

Cjih=d(j,h)-d(j,m)第25頁(yè)/共66頁(yè)算法PAM（k-中心點(diǎn)算法）輸入：簇的數(shù)目k和包含n個(gè)對(duì)象的數(shù)據(jù)庫(kù)。輸出：k個(gè)簇，使得所有對(duì)象與其最近中心點(diǎn)的相異度總和最小。（1）任意選擇k個(gè)對(duì)象作為初始的簇中心點(diǎn)；（2）REPEAT（3）指派每個(gè)剩余的對(duì)象給離它最近的中心點(diǎn)所代表的簇；（4）REPEAT（5）選擇一個(gè)未被選擇的中心點(diǎn)Oi；（6）REPEAT（7）選擇一個(gè)未被選擇過(guò)的非中心點(diǎn)對(duì)象Oh；（8）計(jì)算用Oh代替Oi的總代價(jià)并記錄在S中；（9）UNTIL所有的非中心點(diǎn)都被選擇過(guò)；（10）UNTIL所有的中心點(diǎn)都被選擇過(guò)；（11）IF在S中的所有非中心點(diǎn)代替所有中心點(diǎn)后的計(jì)算出的總代價(jià)有小于0的存在THEN找出S中的用非中心點(diǎn)替代中心點(diǎn)后代價(jià)最小的一個(gè)，并用該非中心點(diǎn)替代對(duì)應(yīng)的中心點(diǎn)，形成一個(gè)新的k個(gè)中心點(diǎn)的集合；（12）UNTIL沒(méi)有再發(fā)生簇的重新分配，即所有的S都大于0.第26頁(yè)/共66頁(yè)實(shí)例假如空間中的五個(gè)點(diǎn)｛A、Ｂ、Ｃ、Ｄ、Ｅ｝如圖1所示，各點(diǎn)之間的距離關(guān)系如表1所示，根據(jù)所給的數(shù)據(jù)對(duì)其運(yùn)行PAM算法實(shí)現(xiàn)劃分聚類(lèi)（設(shè)k=2）。樣本點(diǎn)間距離如下表所示:

樣本點(diǎn)起始中心點(diǎn)為A,B

樣本點(diǎn)ABCDEA01223B10243C22015D24103E33530第27頁(yè)/共66頁(yè)第一步建立階段：假如從5個(gè)對(duì)象中隨機(jī)抽取的2個(gè)中心點(diǎn)為{A，B},則樣本被劃分為{A、C、D}和{B、E}，如圖所示。第二步交換階段：假定中心點(diǎn)A、B分別被非中心點(diǎn){C、D、E}替換，根據(jù)PAM算法需要計(jì)算下列代價(jià)TCAC、

TCAD、

TCAE、TCBC、TCBD、

TCBE。以TCAC為例說(shuō)明計(jì)算過(guò)程：a)當(dāng)A被C替換以后，A不再是一個(gè)中心點(diǎn)，因?yàn)锳離B比A離C近，A被分配到B中心點(diǎn)代表的簇，CAAC=d(A,B)-d(A,A)=1。b)B是一個(gè)中心點(diǎn)，當(dāng)A被C替換以后，B不受影響，CBAC=0。c)C原先屬于A中心點(diǎn)所在的簇，當(dāng)A被C替換以后，C是新中心點(diǎn)，符合PAM算法代價(jià)函數(shù)的第二種情況CCAC=d(C,C)-d(C,A)=0-2=-2。d)D原先屬于A中心點(diǎn)所在的簇，當(dāng)A被C替換以后，離D最近的中心點(diǎn)是C，根據(jù)PAM算法代價(jià)函數(shù)的第二種情況CDAC=d(D,C)-d(D,A)=1-2=-1。e)E原先屬于B中心點(diǎn)所在的簇，當(dāng)A被C替換以后，離E最近的中心仍然是B，根據(jù)PAM算法代價(jià)函數(shù)的第三種情況CEAC=0。因此，TCAC=CAAC+CBAC+CBAC+CDAC+CEAC=1+0-2-1+0=-2。第28頁(yè)/共66頁(yè)

在上述代價(jià)計(jì)算完畢后，我們要選取一個(gè)最小的代價(jià)，顯然有多種替換可以選擇，選擇第一個(gè)最小代價(jià)的替換（也就是C替換A），根據(jù)圖（a）所示，樣本點(diǎn)被劃分為{B、A、E}和{C、D}兩個(gè)簇。圖（b）和圖（c）分別表示了D替換A，E替換A的情況和相應(yīng)的代價(jià)

(a)C替換A,TCAC=-2(b)D替換A,TCAD=-2(c)E替換A,TCAE=-1圖替換中心點(diǎn)A第29頁(yè)/共66頁(yè)圖（a）、（b）、（c）分別表示了用C、D、E替換B的情況和相應(yīng)的代價(jià)。

C替換B,TCBC=-2(b)D替換B,TCBD=-2(c)E替換B,TCBE=-2圖替換中心點(diǎn)B

通過(guò)上述計(jì)算，已經(jīng)完成了PAM算法的第一次迭代。在下一迭代中，將用其他的非中心點(diǎn){A、D、E}替換中心點(diǎn){B、C}，找出具有最小代價(jià)的替換。一直重復(fù)上述過(guò)程，直到代價(jià)不再減小為止。第30頁(yè)/共66頁(yè)P(yáng)AM算法特點(diǎn)比k-means健壯，但對(duì)于大數(shù)據(jù)集效率不高。當(dāng)存在“噪聲”和離群數(shù)據(jù)時(shí)，k-中心點(diǎn)方法比k均值方法更健壯，這是因?yàn)橹行狞c(diǎn)不像平均值那樣易被極端數(shù)據(jù)影響。k-中心點(diǎn)方法的執(zhí)行代價(jià)比k-平均高。第31頁(yè)/共66頁(yè)改進(jìn)算法CLARA(ClusteringLargeApplications),1990

用實(shí)際數(shù)據(jù)的抽樣來(lái)代替整個(gè)數(shù)據(jù)，然后再在這些抽樣的數(shù)據(jù)上利用K-medoids算法得到最佳的中心點(diǎn)。如果樣本是以非隨機(jī)的方式選取，它應(yīng)當(dāng)足以代替原來(lái)的數(shù)據(jù)集合。從中選出的代表對(duì)象（中心點(diǎn)）很可能與從整個(gè)數(shù)據(jù)集合選出的代表相似。

第32頁(yè)/共66頁(yè)改進(jìn)算法CLARANS(“隨機(jī)化的”CLARA)，1994

利用多次不同抽樣來(lái)改進(jìn)CLARA。其聚類(lèi)過(guò)程可以被描述為對(duì)一個(gè)圖的收索過(guò)程，圖中的每一個(gè)節(jié)點(diǎn)都是一個(gè)潛在的解，即k個(gè)中心點(diǎn)的集合。在替換了一個(gè)中心點(diǎn)后得到的聚類(lèi)結(jié)果被當(dāng)成是前聚類(lèi)結(jié)果的鄰居。如果一個(gè)更好的鄰居被發(fā)現(xiàn)，也就是說(shuō)它有更小的平方誤差值，clarans移到該鄰居節(jié)點(diǎn)，處理過(guò)程重新開(kāi)始，如果沒(méi)有發(fā)現(xiàn)更好的鄰居，則達(dá)到局部最優(yōu)。第33頁(yè)/共66頁(yè)(2)層次聚類(lèi)方法層次聚類(lèi)方法對(duì)給定的數(shù)據(jù)集進(jìn)行層次的分解，直到某種條件滿(mǎn)足為止。具體又可分為：凝聚的層次聚類(lèi)：一種自底向上的策略，首先將每個(gè)對(duì)象作為一個(gè)簇，然后合并這些原子簇為越來(lái)越大的簇，直到某個(gè)終結(jié)條件被滿(mǎn)足。分裂的層次聚類(lèi)：采用自頂向下的策略，它首先將所有對(duì)象置于一個(gè)簇中，然后逐漸細(xì)分為越來(lái)越小的簇，直到達(dá)到了某個(gè)終結(jié)條件。層次凝聚的代表是AGNES算法。層次分裂的代表是DIANA算法。第34頁(yè)/共66頁(yè)AGNES算法AGNES(AGglomerativeNESting)算法最初將每個(gè)對(duì)象作為一個(gè)簇，然后這些簇根據(jù)某些準(zhǔn)則被一步步地合并。兩個(gè)簇間的相似度由這兩個(gè)不同簇中距離最近的數(shù)據(jù)點(diǎn)對(duì)的相似度來(lái)確定。聚類(lèi)的合并過(guò)程反復(fù)進(jìn)行直到所有的對(duì)象最終滿(mǎn)足簇?cái)?shù)目。第35頁(yè)/共66頁(yè)算法AGNES（自底向上凝聚算法）輸入：包含n個(gè)對(duì)象的數(shù)據(jù)庫(kù)，終止條件簇的數(shù)目k。輸出：k個(gè)簇，達(dá)到終止條件規(guī)定簇?cái)?shù)目。(1)將每個(gè)對(duì)象當(dāng)成一個(gè)初始簇；(2)REPEAT(3)根據(jù)兩個(gè)簇中最近的數(shù)據(jù)點(diǎn)找到最近的兩個(gè)簇；(4)合并兩個(gè)簇，生成新的簇的集合；(5)UNTIL達(dá)到定義的簇的數(shù)目；第36頁(yè)/共66頁(yè)實(shí)例序號(hào) 屬性1 屬性2 1 1 1 2 1 2 3 2 1 4 2 2 5 3 4 6 3 5 7 4 4 8 4 5步驟 最近的簇距離 最近的兩個(gè)簇 合并后的新簇 1 1 {1}，{2} {1，2}，{3}，{4}，{5}，{6}，{7}，{8}2 1 {3}，{4} {1，2}，{3，4}，{5}，{6}，{7}，{8}3 1 {5}，{6} {1，2}，{3，4}，{5，6}，{7}，{8}4 1 {7}，{8} {1，2}，{3，4}，{5，6}，{7，8} 5 1 {1，2}，{3，4} {1，2，3，4}，{5，6}，{7，8} 6 1 {5，6}，{7，8} {1，2，3，4}，{5，6，7，8}結(jié)束 第1步：根據(jù)初始簇計(jì)算每個(gè)簇之間的距離，隨機(jī)找出距離最小的兩個(gè)簇，進(jìn)行合并，最小距離為1，合并后1，2點(diǎn)合并為一個(gè)簇。第2步：，對(duì)上一次合并后的簇計(jì)算簇間距離，找出距離最近的兩個(gè)簇進(jìn)行合并，合并后3，4點(diǎn)成為一簇。第3步：重復(fù)第2步的工作，5，6點(diǎn)成為一簇。第4步：重復(fù)第2步的工作，7，8點(diǎn)成為一簇。第5步：合并{1，2}，{3，4}成為一個(gè)包含四個(gè)點(diǎn)的簇。第6步：合并{5，6}，{7，8}，由于合并后的簇的數(shù)目已經(jīng)達(dá)到了用戶(hù)輸入的終止條件程序結(jié)束。第37頁(yè)/共66頁(yè)AGNES算法的性能分析AGNES算法比較簡(jiǎn)單，但經(jīng)常會(huì)遇到合并點(diǎn)選擇的困難。假如一旦一組對(duì)象被合并，下一步的處理將在新生成的簇上進(jìn)行。已做處理不能撤消，聚類(lèi)之間也不能交換對(duì)象。如果在某一步?jīng)]有很好的選擇合并的決定，可能會(huì)導(dǎo)致低質(zhì)量的聚類(lèi)結(jié)果。這種聚類(lèi)方法不具有很好的可伸縮性，因?yàn)楹喜⒌臎Q定需要檢查和估算大量的對(duì)象或簇。假定在開(kāi)始的時(shí)候有n個(gè)簇，在結(jié)束的時(shí)候有1個(gè)簇，因此在主循環(huán)中有n次迭代，在第i次迭代中，我們必須在n-i+1個(gè)簇中找到最靠近的兩個(gè)聚類(lèi)。另外算法必須計(jì)算所有對(duì)象兩兩之間的距離，因此這個(gè)算法的復(fù)雜度為

O(n2)，該算法對(duì)于n很大的情況是不適用的。第38頁(yè)/共66頁(yè)DIANA算法DIANA(DivisiveANAlysis)算法是典型的分裂聚類(lèi)方法。在聚類(lèi)中，用戶(hù)能定義希望得到的簇?cái)?shù)目作為一個(gè)結(jié)束條件。同時(shí)，它使用下面兩種測(cè)度方法：簇的直徑：在一個(gè)簇中的任意兩個(gè)數(shù)據(jù)點(diǎn)的距離中的最大值。平均相異度（平均距離）：第39頁(yè)/共66頁(yè)算法DIANA（自頂向下分裂算法）輸入：包含n個(gè)對(duì)象的數(shù)據(jù)庫(kù)，終止條件簇的數(shù)目k。輸出：k個(gè)簇，達(dá)到終止條件規(guī)定簇?cái)?shù)目。（1）將所有對(duì)象整個(gè)當(dāng)成一個(gè)初始簇；（2）FOR（i=1;i≠k;i++)DOBEGIN（3）在所有簇中挑出具有最大直徑的簇C；（4）找出C中與其它點(diǎn)平均相異度最大的一個(gè)點(diǎn)p并把p放入splintergroup，剩余的放在oldparty中；（5）.REPEAT（6）在oldparty里找出到最近的splintergroup中的點(diǎn)的距離不大于到oldparty中最近點(diǎn)的距離的點(diǎn)，并將該點(diǎn)加入splintergroup。（7）UNTIL沒(méi)有新的oldparty的點(diǎn)被分配給splintergroup；（8）splintergroup和oldparty為被選中的簇分裂成的兩個(gè)簇，與其它簇一起組成新的簇集合。（9）END.第40頁(yè)/共66頁(yè)實(shí)例序號(hào) 屬性1 屬性2 1 1 1 2 1 2 3 2 1 4 2 2 5 3 4 6 3 5 7 4 4 8 4 5 步驟 具有最大直徑的簇 splintergroup Oldparty 1 {1，2，3，4，5，6，7，8} {1} {2，3，4，5，6，7，8}2 {1，2，3，4，5，6，7，8} {1，2} {3，4，5，6，7，8} 3 {1，2，3，4，5，6，7，8} {1，2，3} {4，5，6，7，8} 4 {1，2，3，4，5，6，7，8} {1，2，3，4} {5，6，7，8} 5 {1，2，3，4，5，6，7，8} {1，2，3，4} {5，6，7，8}終止第1步，找到具有最大直徑的簇，對(duì)簇中的每個(gè)點(diǎn)計(jì)算平均相異度（假定采用是歐式距離）。

1的平均距離：（1+1+1.414+3.6+4.24+4.47+5）/7=2.96

類(lèi)似地，2的平均距離為2.526；3的平均距離為2.68；4的平均距離為2.18；5的平均距離為2.18；6的平均距離為2.68；7的平均距離為2.526；8的平均距離為2.96。挑出平均相異度最大的點(diǎn)1放到splintergroup中，剩余點(diǎn)在oldparty中。第2步，在oldparty里找出到最近的splintergroup中的點(diǎn)的距離不大于到oldparty中最近的點(diǎn)的距離的點(diǎn)，將該點(diǎn)放入splintergroup中，該點(diǎn)是2。第3步，重復(fù)第2步的工作，splintergroup中放入點(diǎn)3。第4步，重復(fù)第2步的工作，splintergroup中放入點(diǎn)4。第5步，沒(méi)有在oldparty中的點(diǎn)放入了splintergroup中且達(dá)到終止條件（k=2），程序終止。如果沒(méi)有到終止條件，因該從分裂好的簇中選一個(gè)直徑最大的簇繼續(xù)分裂。第41頁(yè)/共66頁(yè)層次聚類(lèi)方法的改進(jìn)層次聚類(lèi)方法盡管簡(jiǎn)單，但經(jīng)常會(huì)遇到合并或分裂點(diǎn)的選擇的困難。改進(jìn)層次方法的聚類(lèi)質(zhì)量的一個(gè)有希望的方向是將層次聚類(lèi)和其他聚類(lèi)技術(shù)進(jìn)行集成，形成多階段聚類(lèi)。下面介紹兩個(gè)改進(jìn)的層次聚類(lèi)方法CURE和BIRTH。第42頁(yè)/共66頁(yè)BIRCH（利用層次方法的平衡迭代歸約和聚類(lèi)）是一個(gè)綜合的層次聚類(lèi)方法，它用聚類(lèi)特征和聚類(lèi)特征樹(shù)（CF）來(lái)概括聚類(lèi)描述。該算法通過(guò)聚類(lèi)特征可以方便地進(jìn)行中心、半徑、直徑及類(lèi)內(nèi)、類(lèi)間距離的運(yùn)算。CF樹(shù)是一個(gè)具有兩個(gè)參數(shù)分支因子B和閡值T的高度平衡樹(shù)，存儲(chǔ)了層次聚類(lèi)的聚類(lèi)特征。分支因子定義了每個(gè)非葉節(jié)點(diǎn)孩子的最大數(shù)目，而閾值給出了存儲(chǔ)在樹(shù)的葉子節(jié)點(diǎn)中的子聚類(lèi)的最大直徑。第43頁(yè)/共66頁(yè)BIRCH算法主要分兩個(gè)階段進(jìn)行：階段一：掃描數(shù)據(jù)庫(kù)，建立一個(gè)初始的CF樹(shù)，它可以被看作一個(gè)數(shù)據(jù)的多層壓縮，試圖保留數(shù)據(jù)內(nèi)在的聚類(lèi)結(jié)構(gòu)。當(dāng)一個(gè)對(duì)象被插入到最近的葉節(jié)點(diǎn)（子聚類(lèi)）中時(shí)，隨著對(duì)象的插入，CF樹(shù)被動(dòng)態(tài)地構(gòu)造，不要求所有的數(shù)據(jù)讀入內(nèi)存，而可在外存上逐個(gè)讀入數(shù)據(jù)項(xiàng)。因此，BIRTH方法對(duì)增量或動(dòng)態(tài)聚類(lèi)也非常有效。階段二：采用某個(gè)聚類(lèi)算法對(duì)CF樹(shù)的葉節(jié)點(diǎn)進(jìn)行聚類(lèi)。在這個(gè)階段可以執(zhí)行任何聚類(lèi)算法，例如典型的劃分方法。

BIRCH算法具有可伸縮性，通過(guò)對(duì)數(shù)據(jù)集的首次掃描產(chǎn)生一個(gè)基本聚類(lèi)，二次掃描則進(jìn)一步改進(jìn)聚類(lèi)質(zhì)量并處理孤立點(diǎn)。BIRCH算法處理速度較快，只是對(duì)非球形簇處理效果不好。第44頁(yè)/共66頁(yè)很多聚類(lèi)算法只擅長(zhǎng)處理球形或相似大小的聚類(lèi)，另外有些聚類(lèi)算法對(duì)孤立點(diǎn)比較敏感。CURE算法解決了上述兩方面的問(wèn)題，選擇基于質(zhì)心和基于代表對(duì)象方法之間的中間策略，即選擇空間中固定數(shù)目的具有代表性的點(diǎn)，而不是用單個(gè)中心或?qū)ο髞?lái)代表一個(gè)簇。該算法首先把每個(gè)數(shù)據(jù)點(diǎn)看成一簇，然后再以一個(gè)特定的收縮因子向簇中心“收縮”它們，即合并兩個(gè)距離最近的代表點(diǎn)的簇。第45頁(yè)/共66頁(yè)CURE算法的主要步驟如下：⑴從源數(shù)據(jù)集中抽取一個(gè)隨機(jī)樣本S。⑵為了加速聚類(lèi)，把樣本劃分成p份，每份大小相等。⑶對(duì)每個(gè)劃分進(jìn)行局部地聚類(lèi)。⑷根據(jù)局部聚類(lèi)結(jié)果，通過(guò)隨機(jī)抽樣剔除孤立點(diǎn)。主要有兩種措施：如果一個(gè)簇增長(zhǎng)得太慢，就去掉它；在聚類(lèi)結(jié)束的時(shí)候，非常小的類(lèi)被剔除。⑸對(duì)上一步中產(chǎn)生的局部的簇進(jìn)一步聚類(lèi)。落在每個(gè)新形成的簇中的代表點(diǎn)根據(jù)用戶(hù)定義的一個(gè)收縮因子收縮或向簇中心移動(dòng)。這些點(diǎn)代表和捕捉到了簇的形狀。⑹用相應(yīng)的簇標(biāo)簽來(lái)標(biāo)記數(shù)據(jù)。第46頁(yè)/共66頁(yè)由于CURE回避了用所有點(diǎn)或單個(gè)質(zhì)心來(lái)表示一個(gè)簇的傳統(tǒng)方法，將一個(gè)簇用多個(gè)代表點(diǎn)來(lái)表示，使CURE可以適應(yīng)非球形的幾何形狀。另外，收縮因子降底了噪音對(duì)聚類(lèi)的影響，從而使CURE對(duì)孤立點(diǎn)的處理更加健壯，而且能識(shí)別非球形和大小變化比較大的簇。CURE的復(fù)雜度是O(n)，n是對(duì)象的數(shù)目，所以該算法適合大型數(shù)據(jù)的聚類(lèi)。第47頁(yè)/共66頁(yè)(3)密度聚類(lèi)密度聚類(lèi)方法的指導(dǎo)思想是，只要一個(gè)區(qū)域中的點(diǎn)的密度大于某個(gè)閾值，就把它加到與之相近的聚類(lèi)中去。這類(lèi)算法能克服基于距離的算法只能發(fā)現(xiàn)“類(lèi)圓形”的聚類(lèi)的缺點(diǎn)，可發(fā)現(xiàn)任意形狀的聚類(lèi)，且對(duì)噪聲數(shù)據(jù)不敏感。但計(jì)算密度單元的計(jì)算復(fù)雜度大，需要建立空間索引來(lái)降低計(jì)算量，且對(duì)數(shù)據(jù)維數(shù)的伸縮性較差。這類(lèi)方法需要掃描整個(gè)數(shù)據(jù)庫(kù)，每個(gè)數(shù)據(jù)對(duì)象都可能引起一次查詢(xún)，因此當(dāng)數(shù)據(jù)量大時(shí)會(huì)造成頻繁的I/O操作。代表算法有：DBSCAN、OPTICS、DENCLUE算法等。第48頁(yè)/共66頁(yè)DBSCAN（Density-BasedSpatialClusteringofApplicationswithNoise）一個(gè)比較有代表性的基于密度的聚類(lèi)算法。與劃分和層次聚類(lèi)方法不同，它將簇定義為密度相連的點(diǎn)的最大集合，能夠把具有足夠高密度的區(qū)域劃分為簇，并可在有“噪聲”的空間數(shù)據(jù)庫(kù)中發(fā)現(xiàn)任意形狀的聚類(lèi)。DBSCAN第49頁(yè)/共66頁(yè)定義1對(duì)象的ε-臨域：給定對(duì)象在半徑ε內(nèi)的區(qū)域。定義2核心對(duì)象：如果一個(gè)對(duì)象的ε-臨域至少包含最小數(shù)目MinPts個(gè)對(duì)象，則稱(chēng)該對(duì)象為核心對(duì)象。例如，在圖中，ε=1cm，MinPts=5，q是一個(gè)核心對(duì)象。定義3直接密度可達(dá)：給定一個(gè)對(duì)象集合D，如果p是在q的ε-鄰域內(nèi)，而q是一個(gè)核心對(duì)象，我們說(shuō)對(duì)象p從對(duì)象q出發(fā)是直接密度可達(dá)的。例如，在圖中，ε=1cm，MinPts=5，q是一個(gè)核心對(duì)象，對(duì)象p從對(duì)象q出發(fā)是直接密度可達(dá)的。圖直接密度可達(dá)第50頁(yè)/共66頁(yè)定義4密度可達(dá)的：如果存在一個(gè)對(duì)象鏈p1，p2，…，pn，p1=q，pn=p，對(duì)pi∈D，（1<=i<=n），pi+1是從pi關(guān)于ε和MitPts直接密度可達(dá)的，則對(duì)象p是從對(duì)象q關(guān)于ε和MinPts密度可達(dá)的。例如，在圖中，ε=1cm，MinPts=5，q是一個(gè)核心對(duì)象，p1是從q關(guān)于ε和MitPts直接密度可達(dá)，p是從p1關(guān)于ε和MitPts直接密度可達(dá)，則對(duì)象p從對(duì)象q關(guān)于ε和MinPts密度可達(dá)的。圖密度可達(dá)第51頁(yè)/共66頁(yè)定義5密度相連的：如果對(duì)象集合D中存在一個(gè)對(duì)象o，使得對(duì)象p和q是從o關(guān)于ε和MinPts密度可達(dá)的，那么對(duì)象p和q是關(guān)于ε和MinPts密度相連的。定義6噪聲:一個(gè)基于密度的簇是基于密度可達(dá)性的最大的密度相連對(duì)象的集合。不包含在任何簇中的對(duì)象被認(rèn)為是“噪聲”。圖密度相連圖噪聲第52頁(yè)/共66頁(yè)DBSCAN通過(guò)檢查數(shù)據(jù)集中每個(gè)對(duì)象的ε-鄰域來(lái)尋找聚類(lèi)。如果一個(gè)點(diǎn)p的ε-鄰域包含多于MinPts個(gè)對(duì)象，則創(chuàng)建一個(gè)p作為核心對(duì)象的新簇。然后，DBSCAN反復(fù)地尋找從這些核心對(duì)象直接密度可達(dá)的對(duì)象，這個(gè)過(guò)程可能涉及一些密度可達(dá)簇的合并。當(dāng)沒(méi)有新的點(diǎn)可以被添加到任何簇時(shí)，該過(guò)程結(jié)束。具體如下：DBSCAN算法描述算法5-5DBSCAN輸入：包含n個(gè)對(duì)象的數(shù)據(jù)庫(kù)，半徑ε，最少數(shù)目MinPts。輸出：所有生成的簇，達(dá)到密度要求。1.REPEAT2.從數(shù)據(jù)庫(kù)中抽取一個(gè)未處理過(guò)的點(diǎn)；3.IF抽出的點(diǎn)是核心點(diǎn)THEN找出所有從該點(diǎn)密度可達(dá)的對(duì)象，形成一個(gè)簇4.ELSE抽出的點(diǎn)是邊緣點(diǎn)(非核心對(duì)象)，跳出本次循環(huán)，尋找下一點(diǎn)；5.UNTIL所有點(diǎn)都被處理；第53頁(yè)/共66頁(yè)下面給出一個(gè)樣本事務(wù)數(shù)據(jù)庫(kù)（見(jiàn)左表），對(duì)它實(shí)施DBSCAN算法。

根據(jù)所給的數(shù)據(jù)通過(guò)對(duì)其進(jìn)行DBSCAN算法，以下為算法的步驟（設(shè)n=12，用戶(hù)輸入ε=1，MinPts=4）樣本事務(wù)數(shù)據(jù)庫(kù)DBSCAN算法執(zhí)行過(guò)程示意

聚出的類(lèi)為{1，3，4，5，9，10，12}，{2，6，7，8，11}。序號(hào)屬性1屬性2110240301411521631741851902101211421213步驟選擇的點(diǎn)在ε中點(diǎn)的個(gè)數(shù)通過(guò)計(jì)算可達(dá)點(diǎn)而找到的新簇112無(wú)222無(wú)333無(wú)445簇C1：{1，3，4，5，9，10，12}553已在一個(gè)簇C1中663無(wú)775簇C2：{2，6，7，8，11}882已在一個(gè)簇C2中993已在一個(gè)簇C1中10104已在一個(gè)簇C1中，11112已在一個(gè)簇C2中12122已在一個(gè)簇C1中第54頁(yè)/共66頁(yè)算法執(zhí)行過(guò)程：第1步，在數(shù)據(jù)庫(kù)中選擇一點(diǎn)1，由于在以它為圓心的，以1為半徑的圓內(nèi)包含2個(gè)點(diǎn)（小于4），因此它不是核心點(diǎn)，選擇下一個(gè)點(diǎn)。第2步，在數(shù)據(jù)庫(kù)中選擇一點(diǎn)2，由于在以它為圓心的，以1為半徑的圓內(nèi)包含2個(gè)點(diǎn)，因此它不是核心點(diǎn)，選擇下一個(gè)點(diǎn)。第3步，在數(shù)據(jù)庫(kù)中選擇一點(diǎn)3，由于在以它為圓心的，以1為半徑的圓內(nèi)包含3個(gè)點(diǎn)，因此它不是核心點(diǎn)，選擇下一個(gè)點(diǎn)。第4步，在數(shù)據(jù)庫(kù)中選擇一點(diǎn)4，由于在以它為圓心的，以1為半徑的圓內(nèi)包含5個(gè)點(diǎn)，因此它是核心點(diǎn)，尋找從它出發(fā)可達(dá)的點(diǎn)（直接可達(dá)4個(gè)，間接可達(dá)3個(gè)），聚出的新類(lèi){1，3，4，5，9，10，12}，選擇下一個(gè)點(diǎn)。第5步，在數(shù)據(jù)庫(kù)中選擇一點(diǎn)5，已經(jīng)在簇1中，選擇下一個(gè)點(diǎn)。第6步，在數(shù)據(jù)庫(kù)中選擇一點(diǎn)6，由于在以它為圓心的，以1為半徑的圓內(nèi)包含3個(gè)點(diǎn)，因此它不是核心點(diǎn)，選擇下一個(gè)點(diǎn)。第7步，在數(shù)據(jù)庫(kù)中選擇一點(diǎn)7，由于在以它為圓心的，以1為半徑的圓內(nèi)包含5個(gè)點(diǎn)，因此它是核心點(diǎn)，尋找從它出發(fā)可達(dá)的點(diǎn)，聚出的新類(lèi){2，6，7，8，11}，選擇下一個(gè)點(diǎn)。第8步，在數(shù)據(jù)庫(kù)中選擇一點(diǎn)8，已經(jīng)在簇2中，選擇下一個(gè)點(diǎn)。第9步，在數(shù)據(jù)庫(kù)中選擇一點(diǎn)9，已經(jīng)在簇1中，選擇下一個(gè)點(diǎn)。第10步，在數(shù)據(jù)庫(kù)中選擇一點(diǎn)10，已經(jīng)在簇1中，選擇下一個(gè)點(diǎn)。第11步，在數(shù)據(jù)庫(kù)中選擇一點(diǎn)11，已經(jīng)在簇2中，選擇下一個(gè)點(diǎn)。第12步，選擇12點(diǎn)，已經(jīng)在簇1中，由于這已經(jīng)是最后一點(diǎn)所有點(diǎn)都已處理，程序終止。步驟選擇的點(diǎn)在ε中點(diǎn)的個(gè)數(shù)通過(guò)計(jì)算可達(dá)點(diǎn)而找到的新簇112無(wú)222無(wú)333無(wú)445簇C1：{1，3，4，5，9，10，12}553已在一個(gè)簇C1中663無(wú)775簇C2：{2，6，7，8，11}882已在一個(gè)簇C2中993已在一個(gè)簇C1中10104已在一個(gè)簇C1中，11112已在一個(gè)簇C2中12122已在一個(gè)簇C1中第55頁(yè)/共66頁(yè)OPTICS算法是對(duì)DBSCAN算法的改進(jìn)，因?yàn)樵贒BSCAN算法中需要用戶(hù)設(shè)定ε-鄰域和MitPts，但是在實(shí)際應(yīng)用中用戶(hù)往往很難確定這些參數(shù)，而且這些參數(shù)設(shè)置的不同往往會(huì)導(dǎo)致聚類(lèi)結(jié)果有很大差別。在OPTICS算法中認(rèn)定對(duì)象應(yīng)該以特定的順序進(jìn)行處理，這個(gè)順序首先處理最小的ε值密度可達(dá)的對(duì)象，這樣可以首先完成高密度的聚類(lèi)。DENCLUE算法的依據(jù)是某個(gè)數(shù)據(jù)點(diǎn)在鄰域內(nèi)的影響可以用一個(gè)數(shù)學(xué)函數(shù)來(lái)形式化地模擬，這個(gè)函數(shù)為影響函數(shù)。所聚類(lèi)數(shù)據(jù)空間的整體密度看成是所有數(shù)據(jù)點(diǎn)影響函數(shù)的總和。在聚類(lèi)時(shí)就根據(jù)全局密度函數(shù)的局部最大，即密度吸引點(diǎn)來(lái)確定。

第56頁(yè)/共66頁(yè)將對(duì)象空間量化為有限數(shù)目的單元，形成一個(gè)網(wǎng)