第六章數(shù)據(jù)挖掘基本算法-3

1、數(shù)據(jù)倉庫與數(shù)據(jù)挖掘數(shù)據(jù)倉庫與數(shù)據(jù)挖掘2數(shù)據(jù)倉庫與數(shù)據(jù)挖掘數(shù)據(jù)倉庫與數(shù)據(jù)挖掘第一章 數(shù)據(jù)倉庫與數(shù)據(jù)挖掘概述第二章 數(shù)據(jù)倉庫的分析第三章 數(shù)據(jù)倉庫的設(shè)計與實(shí)施第四章 信息分析的基本技術(shù)第五章 數(shù)據(jù)挖掘過程第六章第六章 數(shù)據(jù)挖掘基本算法數(shù)據(jù)挖掘基本算法第七章 非結(jié)構(gòu)化數(shù)據(jù)挖掘第八章 離群數(shù)據(jù)挖掘第九章 數(shù)據(jù)挖掘語言與工具的選擇第十章 知識管理與知識管理系統(tǒng)3第六章第六章 數(shù)據(jù)挖掘基本算法數(shù)據(jù)挖掘基本算法6.1 分類規(guī)則挖掘分類規(guī)則挖掘6.2 預(yù)測分析與趨勢分析規(guī)則6.3 數(shù)據(jù)挖掘的關(guān)聯(lián)算法6.4 數(shù)據(jù)挖掘的聚類算法數(shù)據(jù)挖掘的聚類算法6.5 數(shù)據(jù)挖掘的統(tǒng)計分析算法6.6 數(shù)據(jù)挖掘的品種優(yōu)化算法6.7

2、數(shù)據(jù)挖掘的進(jìn)化算法46.4 數(shù)據(jù)挖掘的聚類算法數(shù)據(jù)挖掘的聚類算法聚類分析是對群體及成員進(jìn)行分類的遞歸過程。一個簇是一組數(shù)據(jù)對象的集合，在同一簇中的對象彼此類似，而不同簇中的對象彼此相異。將一組物理或抽象對象分組成由類似對象組成的多個簇的過程被稱為聚類。聚類就是將數(shù)據(jù)對象分組成多個類或簇，在同一個簇中的對象之間具有較高的相似度，而不同簇中的對象差別較大。距離是經(jīng)常采用的度量方式。56.4 數(shù)據(jù)挖掘的聚類算法數(shù)據(jù)挖掘的聚類算法聚類分析的應(yīng)用：市場或客戶分割、模式識別、生物學(xué)研究、空間數(shù)據(jù)分析、Web文檔分類等。聚類分析可以用作獨(dú)立的數(shù)據(jù)挖掘式工具，來獲得對數(shù)據(jù)分布的了解，也可以作為其他數(shù)據(jù)挖掘算法

3、的預(yù)處理步驟。聚類的質(zhì)量是基于對象相異度來評估的。相異度是描述對象的屬性值來計算的。相異度可以對多種類型的數(shù)據(jù)來計算，包括區(qū)間標(biāo)度變量、二元變量、標(biāo)稱變量、序數(shù)型變量和比例度型變量類型的組合。66.4 數(shù)據(jù)挖掘的聚類算法數(shù)據(jù)挖掘的聚類算法聚類分析的算法可以分為：劃分方法：首先得到初始的K個劃分的集合。如K-平均、K-中心點(diǎn)、CLARANS以及對它們的改進(jìn)。層次方法：創(chuàng)建給定數(shù)據(jù)對象集合的一個層次性的分解。根據(jù)層次分解的過程可以分為凝聚（自底向上）或分裂（自頂向下）?；诿芏鹊姆椒ǎ焊鶕?jù)密度的概念來聚類對象，如DBSCAN、DENCLUE、OPTICS?；诰W(wǎng)格的方法：首先將對象空間量化為有限數(shù)

4、目的單元，形成網(wǎng)格結(jié)構(gòu)，然后在網(wǎng)格結(jié)構(gòu)上進(jìn)行聚類，如STING、CLIQUE、WaveCluster。基于模型的方法：為每個簇假設(shè)一個模型，發(fā)現(xiàn)數(shù)據(jù)對模型的最好匹配，如COBWEB、CLASSIT和AutoClass。76.4 數(shù)據(jù)挖掘的聚類算法數(shù)據(jù)挖掘的聚類算法類別類別算法算法分裂/劃分方法K-MEANS（K-平均）、K-MEDOIDS算法（K-中心點(diǎn)）、CLARANS算法（基于選擇的方法）層次法BIRCH算法（平衡迭代規(guī)約和聚類）、CURE算法（代表聚類）、CHAMELEON算法（動態(tài)模型）基于密度的方法DBSCAN算法（基于高密度連接區(qū)域）、OPTICS算法（對象排序識別）、DENCUR

5、E算法（密度分布函數(shù)）基于網(wǎng)格的方法STING算法（統(tǒng)計信息網(wǎng)格）、CLIQUE算法（聚類高維空間）、WAVE-CLUSTER算法（小波變換）基于模型的方法統(tǒng)計學(xué)方法、神經(jīng)網(wǎng)絡(luò)方法表6.9 主要的聚類算法的分類86.4 數(shù)據(jù)挖掘的聚類算法數(shù)據(jù)挖掘的聚類算法6.4.1 聚類分析的概念6.4.2 聚類分析中兩個對象之間的相異度計算方法6.4.3 劃分方法6.4.4 層次方法*6.4.5 基于密度的方法*6.4.6 基于網(wǎng)格的方法*6.4.7 基于模型的聚類方法*6.4.8 模糊聚類算法*96.4.1 聚類分析的概念聚類分析的概念聚類就是按照事物的某些屬性，把事物聚集成類，使類間的相似性盡可能小，類

6、內(nèi)相似性盡可能大。聚類是一個無監(jiān)督學(xué)習(xí)的過程，它與分類的根本區(qū)別在于，分類是需要事先知道所依據(jù)的數(shù)據(jù)特征，而聚類是要找到這個數(shù)據(jù)特征。因此在很多應(yīng)用中，聚類分析作為一種數(shù)據(jù)預(yù)處理過程，是進(jìn)一步分析和處理數(shù)據(jù)的基礎(chǔ)。聚類是一種對具有共同趨勢和模式的數(shù)據(jù)元組進(jìn)行分組的方法，試圖找出數(shù)據(jù)集中的共性和差異并將具有共性的元組聚合在相應(yīng)的類或段中。106.4.1 聚類分析的概念聚類分析的概念數(shù)據(jù)挖掘?qū)垲惖牡湫鸵笕缦拢?）可伸縮性：算法能夠處理海量的數(shù)據(jù)庫對象。2）處理不同類型屬性的能力3）發(fā)現(xiàn)具有任意形狀的聚類的能力4）輸入?yún)?shù)對領(lǐng)域知識的弱依賴性5）處理噪聲數(shù)據(jù)或離群數(shù)據(jù)的能力6）結(jié)果對于輸入記錄順

7、序的無關(guān)性7）處理高維度數(shù)據(jù)的能力8）結(jié)果的可解釋性和可用性9）基于約束的聚類分析能力116.4.2 聚類分析中兩個對象之間的相異度計算方法聚類分析中兩個對象之間的相異度計算方法基于內(nèi)存的聚類算法多選擇如下兩種有代表性的數(shù)據(jù)結(jié)構(gòu)：（1）數(shù)據(jù)矩陣（）數(shù)據(jù)矩陣（data matrix）數(shù)據(jù)矩陣用m個變量（也稱屬性）來表現(xiàn)n個對象，這種數(shù)據(jù)結(jié)構(gòu)是關(guān)系表的形式，或nm維（n個對象m 個屬性）的矩陣。nmnnmmxxxxxxxxx212222111211(6-12)126.4.2 聚類分析中兩個對象之間的相異度計算方法聚類分析中兩個對象之間的相異度計算方法（2）相異度矩陣（）相異度矩陣（dissimil

8、atory matrix）存儲n個對象兩兩之間的近似性，通常用一個nn維的矩陣表示。02 ,1 ,02 , 31 , 301 , 20ndndddd其中d(i,j)是對象i和對象j之間的測量差或相異度，通常它是一個非負(fù)的數(shù)值。對象i和j之間越相似，其值越接近0；兩個對象越不同，其值越大。由于d(i,j) = d(j,i) ；且d(i,i) =0，可以得到（6-13）。(6-13)136.4.2 聚類分析中兩個對象之間的相異度計算方法聚類分析中兩個對象之間的相異度計算方法數(shù)據(jù)矩陣的行和列代表不同的實(shí)體，也被稱為二模矩陣。相異度矩陣的行和列代表相同的實(shí)體，也被稱為單模矩陣。許多聚類算法都是以相異度

9、矩陣為數(shù)據(jù)源運(yùn)行的，如果數(shù)據(jù)是用數(shù)據(jù)矩陣的形式存儲的，在使用聚類算法之前要將其轉(zhuǎn)化為相異度矩陣。146.4.2 聚類分析中兩個對象之間的相異度計算方法聚類分析中兩個對象之間的相異度計算方法計算相異度的常用方法有：區(qū)間標(biāo)度變量計算方法，二元變量計算方法，標(biāo)稱、序數(shù)和比例標(biāo)度計算方法，或這些變量類型的組合來描述對象的相異度計算方法。156.4.2 聚類分析中兩個對象之間的相異度計算方法聚類分析中兩個對象之間的相異度計算方法（1）區(qū)間標(biāo)度變量計算方法）區(qū)間標(biāo)度變量計算方法區(qū)間標(biāo)度變量是一個粗略線性標(biāo)度的連續(xù)度量。度量單位的選用將直接影響聚類分析的結(jié)果。一般而言，所用的度量單位越小，變量可能的值域就越

10、大，這樣對聚類的結(jié)果影響就越大。因此為了避免對度量單位選擇的依賴，應(yīng)該對數(shù)據(jù)進(jìn)行標(biāo)準(zhǔn)化。標(biāo)準(zhǔn)化度量值試圖給所有的變量相等的權(quán)重，當(dāng)沒有關(guān)于數(shù)據(jù)的先驗(yàn)知識時，這樣做是十分有效的。166.4.2 聚類分析中兩個對象之間的相異度計算方法聚類分析中兩個對象之間的相異度計算方法為了實(shí)現(xiàn)度量值的標(biāo)準(zhǔn)化，一種方法是將原來的度量值轉(zhuǎn)化為無單位的值。給定一個變量f的變量值，可以進(jìn)行如下的變換。其中，x1f,x2f,xnf是f的n個度量值，mf是f的平均值，即fnffffffmxmxmxns211nffffxxxnm2111） 計算均值絕對偏差sf176.4.2 聚類分析中兩個對象之間的相異度計算方法聚類分析中兩

11、個對象之間的相異度計算方法均值絕對偏差sf比標(biāo)準(zhǔn)的偏差f對于孤立點(diǎn)具有更好的魯棒性。在計算均值絕對值偏差時，度量值與平均值的偏差沒有被平方，因此孤立點(diǎn)的影響在一點(diǎn)程度上減小了。采用均值絕對偏差的優(yōu)點(diǎn)在于孤立點(diǎn)的z-score值不會太小，因此孤立點(diǎn)仍可別發(fā)現(xiàn)。ffififsmxz2） 計算標(biāo)準(zhǔn)化的度量值186.4.2 聚類分析中兩個對象之間的相異度計算方法聚類分析中兩個對象之間的相異度計算方法標(biāo)準(zhǔn)化后，或者在某些應(yīng)用中不需要標(biāo)準(zhǔn)化，區(qū)間標(biāo)度變量描述的對象間的相異度（或相似度）通?；趯ο箝g的距離來計算。常用的距離度量方法如下：1）歐幾里德距離2/112,nkjkikxxjid其中，jnjjini

12、ixxxjxxxi,2121和是兩個n維的數(shù)據(jù)對象。196.4.2 聚類分析中兩個對象之間的相異度計算方法聚類分析中兩個對象之間的相異度計算方法2）曼哈頓距離nkjkikxxjid1,3）明考斯基距離是歐幾里德距離和曼哈頓距離的推廣。pnkpjkikxxjid/11,其中，p是一個正整數(shù)。p=1時，它表示曼哈頓距離； p=2時，它表示歐幾里德距離。206.4.2 聚類分析中兩個對象之間的相異度計算方法聚類分析中兩個對象之間的相異度計算方法如果對每個變量根據(jù)其重要性賦予一個權(quán)重，加權(quán)的歐幾里德距離可以計算如下：2/112,nkjkikkxxjid同理，加權(quán)也可以用于曼哈頓距離和明考斯基距離。21

13、6.4.2 聚類分析中兩個對象之間的相異度計算方法聚類分析中兩個對象之間的相異度計算方法例6.7 x1=(2,9)和x2=(4,6)表示兩個對象，計算x1和x2的歐幾里德距離和曼哈頓距離。x1和x2的歐幾里德距離x1和x2的曼哈頓距離61. 36942,2221xxd56942,21xxd226.4.2 聚類分析中兩個對象之間的相異度計算方法聚類分析中兩個對象之間的相異度計算方法（2）二元變量計算方法）二元變量計算方法一個二元變量只有兩個狀態(tài)：0或1，其中0表示該變量為空，1表示該變量存在。如果所有的二元變量具有相同的權(quán)重，可以得到一個兩行兩列的可能性如表6.10所示。236.4.2 聚類分析

14、中兩個對象之間的相異度計算聚類分析中兩個對象之間的相異度計算方法方法表6.10中，q表示對象i和對象j的值都為1的變量的數(shù)目；r表示在對象i中值為1，但在該對象j中值為0的變量的數(shù)目； s表示在對象i中值為0，但在該對象j中值為1的變量的數(shù)目； t表示對象i和對象j的值都為0的變量的數(shù)目。變量的總數(shù)是p，p=q+r+s+t。對象j10求和對象i1qrq+r0sts+t求和q+sr+tp=q+r+s+t表6.10 二元變量的相依表246.4.2 聚類分析中兩個對象之間的相異度計算方法聚類分析中兩個對象之間的相異度計算方法評價兩個對象i和j之間的相異度標(biāo)準(zhǔn)如下。（1）簡單匹配系數(shù)（2）Jaccar

15、d系數(shù)（3）Rao系數(shù)tsrqsrjid,srqsrjid,srqppjid,256.4.2 聚類分析中兩個對象之間的相異度計算聚類分析中兩個對象之間的相異度計算方法方法例6.8 二元變量之間的相異度使用實(shí)例 假設(shè)一個病人記錄表（表6.11）包含屬性姓名、性別、發(fā)燒、咳嗽、test-1、test-2、test-3和test-4，其中姓名是對象標(biāo)識，屬性都是二元變量。值Y和P被置為1，值N被置為0。求病人間患病的相似情況。表6.11 二元屬性的關(guān)系變量姓名性別發(fā)燒咳嗽test-1test-2test-3test-4ZhangMYNPNNNLiFYNPNPNWangMYNNNNP266.4.2 聚

16、類分析中兩個對象之間的相異度計算方法聚類分析中兩個對象之間的相異度計算方法根據(jù)Jaccard系數(shù)公式，三個病人Zhang，Li和Wang兩兩之間的相異度如下：d(Zhang,Li)=(0+1)/(2+0+1)=0.33d(Zhang,Wang)=(1+1)/(1+1+1)=0.67d(Li, Wang)=(1+2)/(1+1+2)=0.75因此，Wang和Li患有相似的疾病可能性較低，因?yàn)樗麄冇兄罡叩南喈惗?，而Zhang和Li最可能有類似的疾病。276.4.2 聚類分析中兩個對象之間的相異度計算聚類分析中兩個對象之間的相異度計算方法方法（3）標(biāo)稱型、序數(shù)型和比例標(biāo)度型變量計算方法）標(biāo)稱型、序

17、數(shù)型和比例標(biāo)度型變量計算方法1）標(biāo)稱變量標(biāo)稱變量是二元變量的推廣，它可以具有多于兩個狀態(tài)的值。假設(shè)一個標(biāo)稱變量的狀態(tài)數(shù)目是M。這些狀態(tài)可以用字母、符號，或者一組整數(shù)來表示（注意：這些整數(shù)只是用于數(shù)據(jù)處理，并不代表任何特定的順序）。兩個對象i和j之間的相異度可以用簡單匹配方法來計算：pmpjid,這里m是匹配的數(shù)目，即對i和j取值相同的變量的數(shù)目；而p是全部變量的數(shù)目?？梢酝ㄟ^賦權(quán)重來增加m的影響，或者賦給有較多狀態(tài)的變量的匹配更大的權(quán)重。286.4.2 聚類分析中兩個對象之間的相異度計算方法聚類分析中兩個對象之間的相異度計算方法2）序數(shù)型變量一個離散的序數(shù)型變量類似于標(biāo)稱變量，不同在于序數(shù)型變

18、量的M個狀態(tài)是以有意義的序列排序的。序數(shù)型變量對記錄那些難以客觀度量的主觀評價是非常有用的。一個連續(xù)的序數(shù)型變量看起來像一個未知刻度的的連續(xù)數(shù)據(jù)的集合，即值的相對順序是必要的，而其實(shí)際的大小則不重要。將區(qū)間標(biāo)度變量的值域劃分為有限個區(qū)間，從而將其值離散化，可以得到序數(shù)型變量。一個序數(shù)型變量的值可以映射為排序。例如，一個變量f有Mf個狀態(tài)，這些有序的狀態(tài)定義了一個序列1,Mf。296.4.2 聚類分析中兩個對象之間的相異度計算聚類分析中兩個對象之間的相異度計算方法方法處理序數(shù)型變量：在計算對象的相異度時，序數(shù)型變量的處理與區(qū)間標(biāo)度變量的處理方法類似。假設(shè)f是用于描述n個對象的一組序數(shù)型變量之一，

19、關(guān)于f的相異度計算步驟如下：Step 1 第i個對象的f值為xif，變量f有Mf個有序的狀態(tài)，對應(yīng)于序列1,Mf 。用對應(yīng)的秩rif代替xif， rif 1,Mf 。Step 2 既然每個序數(shù)變量可以有不同數(shù)目的狀態(tài)，必須經(jīng)常將每個變量的值域映射到0.0,1.0上，以便每個變量都有相同的權(quán)重。這一點(diǎn)可以通過zif代替rif來實(shí)現(xiàn)。11fijifMrz(6-14)306.4.2 聚類分析中兩個對象之間的相異度計算方法聚類分析中兩個對象之間的相異度計算方法Step 3 相異度的計算可以采用任意一種距離度量方法，采用zif作為第i個對象的f值。316.4.2 聚類分析中兩個對象之間的相異度計算方法聚

20、類分析中兩個對象之間的相異度計算方法3）比例標(biāo)度型變量比例標(biāo)度型變量在非線性的標(biāo)度取正的度量值，例如指數(shù)標(biāo)度，近似地遵循 AeBT。計算用比例標(biāo)度型變量描述的對象之間的相異度，目前有三種方法： 采用與處理區(qū)間標(biāo)度變量同樣的方法。缺點(diǎn)：標(biāo)度可能被扭曲。 對比例標(biāo)度型變量進(jìn)行對數(shù)變換。變換得到的值可用區(qū)間標(biāo)度方法計算，對于比例標(biāo)度型變量可以采用log-log或者其他形式的變換，具體做法取決于定義和應(yīng)用。 將xif看作連續(xù)的序數(shù)型數(shù)據(jù)，將其秩作為區(qū)間標(biāo)度的值來對待。326.4.2 聚類分析中兩個對象之間的相異度計算方法聚類分析中兩個對象之間的相異度計算方法（4）混合類型的變量計算方法）混合類型的變量

21、計算方法一個數(shù)據(jù)庫可能包含區(qū)間標(biāo)度量、對稱二元變量、不對稱二元變量、標(biāo)稱變量、序數(shù)型變量或者比例標(biāo)度變量。第一種方法：計算用混合類型變量描述的對象之間的相異度方法是將變量按類型分組，對每種類型的變量進(jìn)行單獨(dú)的聚類分析。如果這些分析得到兼容的結(jié)果，這種做法是可行的。但在實(shí)際應(yīng)用中，這種情況是不大可能的。第二種方法：將所有變量一起處理，只進(jìn)行一次聚類分析。將不同類型的變量組合在單個的相異度矩陣中，把所有有意義的變量轉(zhuǎn)換到共同的值域區(qū)間0.0,1.0上。336.4.2 聚類分析中兩個對象之間的相異度計算聚類分析中兩個對象之間的相異度計算方法方法假設(shè)數(shù)據(jù)集包含p不個同類型的變量，對象i和對象j之間相異

22、度d(i,j)定義為： pffijpffijfijdjid11/,(6-15)其中，如果xif或者xjf缺失，或者xif = xjf=0，且變量f是不對稱的二元變量，則指示項(xiàng) ，否則 。 0fif 1fif346.4.2 聚類分析中兩個對象之間的相異度計算聚類分析中兩個對象之間的相異度計算方法方法變量f對i和j之間相異度的計算方式與其具體類型有關(guān)。1）如果f是二元變量或標(biāo)稱變量： 。否則如果1; 0,fijfijjfifddxx2）如果f是區(qū)間標(biāo)度變量：3）如果f是序數(shù)型或者比例標(biāo)度型變量： 的所有非空缺對象。遍歷變量這里的fh,minmaxhfhhfhjfiffijxxxxd 待。作為區(qū)間標(biāo)

23、度變量值對并將，和計算秩iffififzMrzr11if356.4.3 劃分方法劃分方法給定一個包含n個數(shù)據(jù)對象的數(shù)據(jù)庫，以及要生成的簇的數(shù)目k，一個劃分類的算法將數(shù)據(jù)對象組織為k個劃分（kn），其中每個劃分代表一個簇。通常會采用一個劃分準(zhǔn)則（相似度函數(shù)）以便在同一個簇中的對象是“相似的”，而不同簇中的對象是“相異的”。366.4.3 劃分方法劃分方法（1）典型的劃分方法：）典型的劃分方法：k-平均和平均和k-中心點(diǎn)中心點(diǎn)最著名與最常用的劃分方法是k-平均、k-中心點(diǎn)和它們的變種。1）基于簇的重心技術(shù)： k-平均方法k-means算法是基于質(zhì)心的算法。k-means算法以k為參數(shù)，把n個對象分

24、為k個簇，以使簇內(nèi)具有較高的相似度，而簇間的相似度最低。相似度的計算根據(jù)一個簇中對象的平均值（被看作簇的重心）來進(jìn)行。376.4.3 劃分方法劃分方法k-means聚類算法的具體流程：Step1 從數(shù)據(jù)集中任意選擇k個對象C1,C2, ,Ck作為初始的簇中心；Step2 把每個對象分配到與之最相似的聚合。每個聚合用其中所有對象的均值來代表，“最相似”就是指距離最小。對于每個點(diǎn)Vi，找出一個質(zhì)心Cj，使它們之間的距離d(Vi, Cj)最小，并把Vi分到第j組。Step3 把所有的點(diǎn)分配到相應(yīng)的簇之后，重新計算每個組的質(zhì)心Cj 。Step4 循環(huán)執(zhí)行Step 2和Step 3，直到數(shù)據(jù)的劃分不再發(fā)

25、生變化。386.4.3 劃分方法劃分方法通常采用的準(zhǔn)則函數(shù)是平方誤差準(zhǔn)則函數(shù)，其定義如下：kiiCpimpE12(6-16)其中，E是數(shù)據(jù)庫中所有對象的平方誤差的總和；p是空間中的點(diǎn)，表示給定的數(shù)據(jù)對象；mi是簇Ci的平均值（p和mi都是多維的）。也就是說，對于每個簇中的每個對象，求對象到其簇中心距離的平方，然后求和。這個準(zhǔn)則試圖使生成的結(jié)果簇盡可能地緊湊和獨(dú)立。396.4.3 劃分方法劃分方法輸入：k：簇的數(shù)目n：數(shù)據(jù)庫對象的個數(shù)輸出：k個簇，使平方誤差最小方法： 隨機(jī)選擇k個對象作為初始的代表對象； repeat； 根據(jù)與每個中心的距離，將每個對象賦給最近的簇； 重新計算每個簇的平均值；

26、until 不再發(fā)生變化。406.4.3 劃分方法劃分方法例例6.9 k-means算法使用實(shí)例算法使用實(shí)例 設(shè)數(shù)據(jù)對象集合如表6.12所示。簇數(shù)目k=2，采用k-means算法對其進(jìn)行聚類。表6.12pxy11121.21.230.81.240.90.751.30.9611.473383.12.893.23.4102.73.3112.62.9416.4.3 劃分方法劃分方法第一次迭代：選擇p3(0.8,1.2)，p8(3.1,2.8)為簇C1，C2的初始簇代表。283. 02 . 118 . 012231 pp766. 28 . 211 . 312281 pp3181pppp所以，將p1分配

27、給p3所屬的類C1，同理，將p2 、 p3 、 p4 、 p5 、 p6分配給p3所屬的類C1，將p7 、 p8 、 p9 、 p10 、 p11分配給p8所屬的類C2 。426.4.3 劃分方法劃分方法第二次迭代，用m1(1.033,1.067)，m2(2.92,3.08)作為簇C1，C2的簇中心，重新對數(shù)據(jù)進(jìn)行劃分。將p1、p2 、 p3 、 p4 、 p5 、 p6分類C1，將p7 、 p8 、 p9 、 p10 、 p11分配給類C2 。m1= (1.033,1.067)， m2= (2.92,3.08)，E=1.023 067. 1 ,033. 164 . 19 . 07 . 02

28、. 12 . 11,13 . 19 . 08 . 02 . 111m 08. 3 ,92. 259 . 23 . 34 . 38 . 23,6 . 27 . 22 . 31 . 332m023. 108. 39 . 292. 26 . 2067. 11033. 11222222E436.4.3 劃分方法劃分方法由于在兩次迭代過程中，2個簇中心都不變，所以停止迭代過程。得到的兩個聚類分別為：C1=p1, p2, p3, p4, p5, p6C2=p7, p8, p9, p10, p11446.4.3 劃分方法劃分方法k-means聚類算法嘗試找出使平方誤差函數(shù)值最小的k個劃分。當(dāng)結(jié)果簇是密集的，

29、而簇與簇之間區(qū)別明顯時，它的效果較好。對處理大數(shù)據(jù)集，該算法是相對可伸縮的和高效率的，復(fù)雜度是O(nkt)，n是所有對象的數(shù)目，k是簇的數(shù)目，t是迭代的次數(shù)。456.4.3 劃分方法劃分方法不足：k-means算法只有在簇的平均值被定義的情況下才能使用。k-means算法的不足之處在于它要多次掃描數(shù)據(jù)庫。k-means算法只能找出球形的類，而不能發(fā)現(xiàn)任意形狀的類。初始質(zhì)心的選擇對聚類結(jié)果有較大的影響。k-means算法對于噪聲和孤立點(diǎn)數(shù)據(jù)是敏感的，少量的該類數(shù)據(jù)能夠?qū)ζ骄诞a(chǎn)生極大的影響。k-平均算法的變種：k-模方法、EM算法等466.4.3 劃分方法劃分方法2）基于有代表性的對象的技術(shù)：k

30、-中心點(diǎn)法為了避免k-means算法對孤立點(diǎn)的敏感性，不采用簇中對象的平均值作為參照點(diǎn)，可以選用簇中位置最中心的對象，即medoid。這樣的劃分方法仍然是基于最小化所有對象與其參照點(diǎn)之間的相異度之和的原則來執(zhí)行的。這是k-medoids方法的基礎(chǔ)。通常采用的準(zhǔn)則函數(shù)是絕對誤差準(zhǔn)則函數(shù)，其定義如下：kiiCpiopE12(6-17)其中，E是數(shù)據(jù)庫中所有對象的絕對誤差的總和；p是空間中的點(diǎn)，表示給定的數(shù)據(jù)對象；oi是簇Ci中的代表對象。476.4.3 劃分方法劃分方法k-medoids算法的基本策略：首先隨機(jī)選擇k個對象，每個對象代表一個簇，把其余的對象分別分配給最相似的簇。然后，反復(fù)地嘗試把每

31、個中心分別用其他非中心來代替，檢查聚類的質(zhì)量是否有所提高。若是，則保留該替換，重復(fù)上述過程，直到不再發(fā)生變化。為了判定一個非代表對象Orandom是否是當(dāng)前一個代表對象Oj的好的替代，對于每一個非中心點(diǎn)對象，考慮下面的四種情況：第一種情況：p當(dāng)前隸屬于中心點(diǎn)對象Oj。如果Orandom代替Oj作為一個中心點(diǎn)，且p離Oi最近，ij，那么p被重新分配給Oi 。486.4.3 劃分方法劃分方法第二種情況：p當(dāng)前隸屬于中心點(diǎn)對象Oj。如果Orandom代替Oj作為一個中心點(diǎn)，且p離Orandom最近，那么p被重新分配給Orandom 。第三種情況：p當(dāng)前隸屬于中心點(diǎn)對象Oi ，ij 。如果Orando

32、m代替Oj作為一個中心點(diǎn)，且p離Oi最近，那么對象的隸屬不發(fā)生變化 。第四種情況：p當(dāng)前隸屬于中心點(diǎn)對象Oi ，ij 。如果Orandom代替Oj作為一個中心點(diǎn)，且p離Orandom最近，那么p被重新分配給Orandom 。496.4.3 劃分方法劃分方法每當(dāng)重新分配時，平方-誤差E所產(chǎn)生的差別對代價函數(shù)有影響。因此，如果一個當(dāng)前的中心點(diǎn)對象被非中心點(diǎn)所代替，就通過代價函數(shù)計算平方-誤差值所產(chǎn)生的差別。替換的總代價是所有非中心點(diǎn)對象所產(chǎn)生的代價之和。如果總代價是負(fù)的，那么實(shí)際的平方-誤差將會減少，Oj可以被Orandom代替。如果總代價是正的，則當(dāng)前的中心點(diǎn)Oj被認(rèn)為是可接受的，在本次迭代中沒

33、有變化發(fā)生。506.4.3 劃分方法劃分方法輸入：k：簇的數(shù)目n：數(shù)據(jù)庫對象的個數(shù)輸出：k個簇，使所有對象與其最近代表對象的相異度總和最小方法： 隨機(jī)選擇k個對象作為初始的代表對象； repeat； 指派每個剩余的對象給離它最近的代表對象所代表的簇； 隨意地選擇一個非代表對象Orandom； 計算用Orandom代替Oj的總代價S； 如果S0，則用Orandom替換Oj ，形成新的k個代表對象的集合； until 不發(fā)生變化。516.4.3 劃分方法劃分方法k-medoids算法的過程和k-means算法的不同之處在于：k-medoids算法用類中最靠近中心的一個對象來代表聚類，而k-mean

34、s算法用質(zhì)心來代表聚類。k-means算法對噪聲非常敏感，因?yàn)橐粋€極大的值會對質(zhì)心的計算帶來很大的影響，而k-medoids算法中，通常用中心來代替質(zhì)心，可以有效地消除該影響。526.4.3 劃分方法劃分方法PAM（partitioning around medoid, 圍繞中心點(diǎn)的劃分）是最早提出的k-中心點(diǎn)算法之一。它試圖對n個對象給出k個劃分。最初隨機(jī)選擇k個中心點(diǎn)后，該算法反復(fù)地進(jìn)行，試圖找出更好的中心點(diǎn)：對所有可能的對象進(jìn)行分析，每兩個對象的一個對象被看作是中心點(diǎn)，而另一個不是；對可能的各種組合，計算聚類結(jié)果的質(zhì)量。一個對象Oj被可以產(chǎn)生最大平方-誤差值減少的對象代替，使在一次迭代中

35、產(chǎn)生的最佳對象的集合為下次迭代的中心點(diǎn)。536.4.3 劃分方法劃分方法（2）大型數(shù)據(jù)庫中的劃分方法：基于選擇的）大型數(shù)據(jù)庫中的劃分方法：基于選擇的k-中心點(diǎn)中心點(diǎn)CLARANS方法方法典型的k-中心點(diǎn)劃分算法PAM方法，對小的數(shù)據(jù)集合非常有效，由于沒有良好的可伸縮性，所以不適合答的數(shù)據(jù)集合。為了處理較大的數(shù)據(jù)集合，可以采用一個基于選擇的方法CLARA（clustering large applications, CLARA）。CLARA的基本思想是：不考慮整個數(shù)據(jù)集合，選擇實(shí)際數(shù)據(jù)的一小部分作為數(shù)據(jù)的樣本。然后用PAM方法從樣本中選擇中心點(diǎn)。如果樣本是以非隨機(jī)方式選取，它應(yīng)當(dāng)足以代表原來的數(shù)

36、據(jù)集合。546.4.3 劃分方法劃分方法改進(jìn)CLARA的聚類質(zhì)量和可伸縮性是將CLARANS（clustering large applications based upon randomized search, CLARANS）的采樣技術(shù)和PAM結(jié)合起來。與CLARA不同，CLARANS沒有在任一給定時間內(nèi)局限于任一樣本，即不同于CLARA在搜索的每個階段都有一個固定的樣本，CLARANS在搜索的每一步帶一定隨機(jī)性地抽取一個樣本。556.4.4 層次方法層次方法一個層次的聚類方法將數(shù)據(jù)對象組成一棵聚類的樹。根據(jù)層次分解是自底向上，還是自頂向下形成，層次的聚類方法可以進(jìn)一步分為凝聚和分裂層次聚

37、類。一個純粹的層次聚類方法的聚類質(zhì)量受限于如下特點(diǎn)：一個合并或分裂一旦執(zhí)行，就不能修正。（1） 凝聚的和分裂的層次聚類 （2） BIRCH：平衡迭代歸約和聚類 （3） ROCK：分類屬性層次聚類算法 （4） CURE：使用代表點(diǎn)聚類方法 （5） Chameleon：動態(tài)建模層次聚類56（1） 凝聚的和分裂的層次聚類凝聚的和分裂的層次聚類1）凝聚的方法首先將每個對象作為單獨(dú)的一個原子簇然后相繼地合并相近的對象或原子簇直到所有的原子簇合并為一個（層次的最上層），或者達(dá)到一個終止條件2）分裂的方法首先將所有的對象置于一個簇中在迭代的每一步中，一個簇被分裂為更小的簇，直到最終每個對象在單獨(dú)的一個簇中，

38、或者達(dá)到一個終止條件57（1） 凝聚的和分裂的層次聚類凝聚的和分裂的層次聚類四個常用的簇間距離度量方法如下：最小距離：最大距離：平均值的距離：平均距離：(6-18)(6-19)(6-20)(6-21)min,minppCCdjCpiCpjimin,maxppCCdjCpiCpjijijimeanmmCCd, iCpjCpjijiavgppnnCCd1,其中，|p-p|是兩個對象p和p之間的距離，mi是簇Ci的平均值，而ni是簇Ci中對象的數(shù)目。58（2）BIRCH：平衡迭代歸約和聚類：平衡迭代歸約和聚類利用層次方法的平衡迭代規(guī)約和聚類（Balanced Iterative Reducing a

39、nd Clustering using Hierarchies, BIRCH）用于歐幾里德向量空間數(shù)據(jù)，即平均值有意義的數(shù)據(jù)。該算法通過聚類特征（Clustering Feature, CF）對簇的信息進(jìn)行匯總描述，然后對簇進(jìn)行分類。假設(shè)某個簇中包含N個d維的數(shù)據(jù)點(diǎn)或者數(shù)據(jù)對象oi，則該簇的聚類特征定義如下：SSLSNCF,(6-22)其中，N是簇中數(shù)據(jù)對象的數(shù)目， 是N個對象的線性和，即LSniio1SS是對象的平方和，即niio12，它記錄了計算聚類和有效利用存儲的關(guān)鍵度量。59（2） BIRCH：平衡迭代歸約和聚類：平衡迭代歸約和聚類BIRCH算法的主要目標(biāo)是使I/O時間盡可能小，原因在

40、于大型數(shù)據(jù)集通常不能完全裝入內(nèi)存中。BIRCH算法通過把聚類分為多個階段來達(dá)到此目的。首先通過構(gòu)建CF-樹對原數(shù)據(jù)集進(jìn)行預(yù)聚類，在前面預(yù)聚類的基礎(chǔ)上進(jìn)行聚類。CF1CF2CFnCF11CF12CF1n根層第一層圖6.10 CF樹的結(jié)構(gòu)60（2） BIRCH：平衡迭代歸約和聚類：平衡迭代歸約和聚類BIRCH共包含四個階段：預(yù)聚類階段：掃描整個數(shù)據(jù)庫，構(gòu)建初始聚類特征樹，該樹保存在內(nèi)存中，用簡潔的匯總信息或者葉子節(jié)點(diǎn)中的子聚類來代表數(shù)據(jù)點(diǎn)的密集區(qū)域。（可選階段）重新掃描葉子節(jié)點(diǎn)項(xiàng)，來構(gòu)建一個更小的CF-樹。采用別的聚類算法，對CF-tree的葉子節(jié)點(diǎn)進(jìn)行聚類。（可選階段）把前一個階段中找到的聚類的

41、質(zhì)心，用作種子來創(chuàng)建最終的聚類。其它數(shù)據(jù)點(diǎn)根據(jù)到這些種子所代表聚類的遠(yuǎn)近來重新分配到各個聚類中。61（2） BIRCH：平衡迭代歸約和聚類：平衡迭代歸約和聚類BIRCH算法的主要缺點(diǎn)之一就是在初始掃描完成之后，它使用基于質(zhì)心的方法來形成聚類，當(dāng)聚類的形狀不同或大小各異的情況下，就容易出現(xiàn)問題。BIRCH算法采用直徑作為控制參數(shù)，所以當(dāng)類的形狀非球形或不同大小的類時，聚類效果不佳。BIRCH算法對數(shù)據(jù)的輸入順序很敏感，還需要用戶手工設(shè)置一些參數(shù)。62（3）ROCK：分類屬性層次聚類算法：分類屬性層次聚類算法分類屬性的層次聚類算法（Robust Clustering using linKs），針對

42、具有分類屬性的數(shù)據(jù)使用了鏈接（指兩個對象共同的近鄰數(shù)目）的概念。對于聚類包含布爾或分類屬性的數(shù)據(jù)，傳統(tǒng)聚類算法使用距離函數(shù)，然而實(shí)驗(yàn)表明對分類數(shù)據(jù)聚類時，這些距離度量不能產(chǎn)生高質(zhì)量的簇。大多數(shù)聚類算法在進(jìn)行聚類時只估計點(diǎn)與點(diǎn)之間的相似度；也就是說，在每一步中那些最相似的點(diǎn)合并到一個簇中。這種局部方法很容易導(dǎo)致錯誤。63（3）ROCK：分類屬性層次聚類算法：分類屬性層次聚類算法ROCK算法采用一種比較全局的觀點(diǎn)，通過考慮成對點(diǎn)的鄰域情況進(jìn)行聚類。如果兩個相似的點(diǎn)同時具有相似的鄰域，那么這兩個點(diǎn)可能屬于同一個簇而合并。 ROCK算法使用一個相似度閾值和共享鄰域的概念從一個給定的數(shù)據(jù)相似度矩陣中首先

43、構(gòu)建一個稀疏圖，然后在這個稀疏圖上執(zhí)行凝聚層次聚類。使用一個優(yōu)度度量評價聚類。采用隨機(jī)抽樣處理大規(guī)模的數(shù)據(jù)集。ROCK算法在最壞情況下的時間復(fù)雜度為O(n2+nmmma+n2logn) ，其中mm和ma分別是近鄰數(shù)目的最大值和平均值，n是對象的個數(shù)。64（4） CURE：使用代表點(diǎn)聚類方法：使用代表點(diǎn)聚類方法使用代表點(diǎn)的聚類方法（Clustering Using Representative, CURE）解決了偏好球形和相似大小的問題，在處理孤立點(diǎn)上也更加健壯。 CURE選擇了位于基于質(zhì)心和基于代表對象方法之間的中間策略，它不用單個質(zhì)心或?qū)ο髞泶硪粋€簇，而是選擇數(shù)據(jù)空間中固定數(shù)目的具有代表性

44、的點(diǎn)。一個簇的代表點(diǎn)通過如下方式產(chǎn)生：首先選擇簇中分散的對象然后根據(jù)一個特定的分?jǐn)?shù)或收縮因子向簇中心收縮或移動它們在算法的每一步，有最近距離的代表點(diǎn)對（每個點(diǎn)來自于一個不同的簇）的兩個簇被合并65（4） CURE：使用代表點(diǎn)聚類方法：使用代表點(diǎn)聚類方法每個簇有多于一個的代表點(diǎn)使得CURE算法可以適應(yīng)非球形的幾何形狀。簇的收縮或凝聚可以有助于控制孤立點(diǎn)的影響。因此，CURE算法對于孤立點(diǎn)的處理更加健壯，而且能夠識別非球形和大小變化較大的簇。對于大規(guī)模數(shù)據(jù)庫，它也具有良好的伸縮性，而且沒有犧牲聚類質(zhì)量。66（4） CURE：使用代表點(diǎn)聚類方法：使用代表點(diǎn)聚類方法針對大型數(shù)據(jù)庫，CURE算法采用隨機(jī)

45、取樣和劃分兩種方法的組合：一個隨機(jī)樣本首先被劃分，每個劃分在被部分聚類；然后這些聚類結(jié)果簇被聚類產(chǎn)生希望的結(jié)果。該算法的具體過程如下。Step 1 源數(shù)據(jù)對象中抽取一個隨機(jī)樣本S；Step 2 將樣本S分割為一組劃分；Step 3 對每個劃分局部地聚類；Step 4 通過隨機(jī)取樣剔除孤立點(diǎn)。如果一個簇增長的太慢，就去掉它；Step 5 對局部的簇進(jìn)行聚類。落在每個新形成的簇中的代表點(diǎn)根據(jù)用戶定義的一個收縮因子收縮或向簇中心移動。這些點(diǎn)代表了簇的形狀；Step 6 用相應(yīng)的簇標(biāo)簽來標(biāo)記數(shù)據(jù)。67（4） CURE：使用代表點(diǎn)聚類方法：使用代表點(diǎn)聚類方法CURE算法特點(diǎn)：CURE算法可以適應(yīng)非球形的

46、幾何形狀算法對孤立點(diǎn)的處理更加健壯能夠識別非球形和大小變化較大的簇；CURE算法的復(fù)雜性為O(n)。CURE從源數(shù)據(jù)對象中抽取一個隨機(jī)樣本S，基于對此樣本的劃分進(jìn)行聚類，如果抽取的樣本發(fā)生傾斜，則會嚴(yán)重影響聚類結(jié)果 。68（5） Chameleon：動態(tài)建模層次聚類：動態(tài)建模層次聚類Chameleon是一個在層次聚類中利用動態(tài)模型的層次聚類算法，屬于凝聚聚類技術(shù)。在聚類過程中，如果兩個簇之間的互連性和近似度與簇內(nèi)部對象間的互連性和近似度高度相關(guān)，則合并這兩個簇。基于動態(tài)模型的合并過程有利于自然的和相似的聚類的發(fā)現(xiàn)，而且只要定義了相似度函數(shù)就可以應(yīng)用于所有類型的數(shù)據(jù)。69（5）Chameleon

47、：動態(tài)建模層次聚類：動態(tài)建模層次聚類Chameleon通過兩個簇的相對互連度RI(Ci,Cj)和相對接近度RC (Ci,Cj)來決定簇之間的相似度。相對互連度是被簇的內(nèi)部互聯(lián)度規(guī)范化的兩個簇的絕對互連度，如果結(jié)果簇中的點(diǎn)之間連接幾乎和原來的每個簇一樣強(qiáng)，兩個簇合并，數(shù)學(xué)表述為：jCiCjCiCjiECECECCCRI21,其中，ECCi,Cj是連接簇Ci和Cj的邊之和；類似地， ECCi （或ECCj ）是二分簇Ci（或Cj）的割邊最小和。(6-23)70（5） Chameleon：動態(tài)建模層次聚類：動態(tài)建模層次聚類相對接近度是被簇的內(nèi)部互聯(lián)度規(guī)范化的兩個簇的絕對接近度，兩個簇合并，僅當(dāng)結(jié)果簇

48、中的點(diǎn)之間的接近程度幾乎與原來的每個簇一樣。數(shù)學(xué)表述為：其中，|Ci|和|Cj|分別是簇Ci和Cj的大??；jCECjijiCECjiijCiCECjiSCCCSCCCSCCRC,(6-24)jCiCECS,是連接Ci和Cj節(jié)點(diǎn)的邊的平均權(quán)值；）（或jCECiCECSS是二分簇Ci（或Cj）的邊的平均權(quán)值；EC表示割邊。71（5） Chameleon：動態(tài)建模層次聚類：動態(tài)建模層次聚類Chameleon算法的思想是：首先通過一個圖劃分算法將數(shù)據(jù)對象聚類為大量相對較小的子聚類，然后用一個凝聚的層次聚類算法通過反復(fù)地合并子類來找到真正的結(jié)果簇。Chameleon既考慮了互連性，又考慮了簇間的近似度，

49、特別是簇內(nèi)部的特征，來確定最相似的子簇。它不依賴于一個靜態(tài)的，用戶提供的模型，能夠自動地適應(yīng)被合并的簇的內(nèi)部特征。72（5） Chameleon：動態(tài)建模層次聚類：動態(tài)建模層次聚類與CURE和DBSCAN相比：Chameleon在發(fā)現(xiàn)高質(zhì)量的任意形狀的聚類方面有更強(qiáng)的能力但是在最壞的情況下，高維數(shù)據(jù)的處理代價可能對n個對象需要 O(n2)的時間736.4.5 基于密度的聚類方法基于密度的聚類方法基于密度的聚類方法將簇看作數(shù)據(jù)空間中由低密度區(qū)域分隔開的高密度對象區(qū)域。主要思想：只要臨近區(qū)域的密度（對象或數(shù)據(jù)點(diǎn)的數(shù)目）超過某個閾值，就繼續(xù)聚類，即對給定類中的每個數(shù)據(jù)點(diǎn)，在一個給定范圍的區(qū)域中必須至

50、少包含某個數(shù)目的點(diǎn)。基于密度的聚類方法可以用來過濾噪聲孤立點(diǎn)數(shù)據(jù)，發(fā)現(xiàn)任意形狀的簇。（1）DBSCAN：基于高密度連通區(qū)域聚類 （2）OPTICS：通過點(diǎn)排序識別聚類結(jié)構(gòu) （3）DENCLUE：基于密度分布函數(shù)的聚類74（1）DBSCAN：基于高密度連通區(qū)域聚類：基于高密度連通區(qū)域聚類基于高密度連通區(qū)域的聚類（Density-Based Spatial Clustering of Application with Noise, DBSCAN）將具有足夠高密度的區(qū)域劃分為簇，并可以在帶有噪聲的空間數(shù)據(jù)庫中發(fā)現(xiàn)任意形狀的聚類。它定義簇為密度相連的點(diǎn)的最大集合。定義：一個給定對象周圍半徑內(nèi)的區(qū)域稱為

51、該對象的鄰域。如果一個對象的鄰域至少包含最小數(shù)目MinPts的對象，那么該對象稱為核心對象。給定一個對象集合D，如果p是在q的鄰域內(nèi)，而q是一個核心對象，我們說對象p從對象q出發(fā)是直接密度可達(dá)的。75（1）DBSCAN：基于高密度連通區(qū)域聚類：基于高密度連通區(qū)域聚類如果存在一個對象鏈p1,p2, ,pn，p1=q，pn=p，對piD，1i n， pi +1是從pi關(guān)于和MinPts直接密度可達(dá)的，則對象p是從對象q關(guān)于和MinPts密度可達(dá)的。如果對象集合D中存在一個對象o，使得對象p和q是從o關(guān)于和MinPts密度相連的。密度可達(dá)性是直接密度可達(dá)性的傳遞閉包，這種關(guān)系式非對稱的。只有核心對象

52、之間是相互密度可達(dá)的。基于密度的簇是基于密度可達(dá)性的最大的密度相連對象的集合，不包含在任何簇中的對象認(rèn)為是噪聲。76（1）DBSCAN：基于高密度連通區(qū)域聚類：基于高密度連通區(qū)域聚類DBSCAN算法通過檢查數(shù)據(jù)庫中每個點(diǎn)的-鄰域來尋找聚類。如果一個點(diǎn)p的鄰域包含多于MinPts個點(diǎn)，則創(chuàng)建一個以p作為核心對象的新簇。然后，DBSCAN算法迭代地尋找從這些核心對象直接密度可達(dá)的對象，這個過程可能涉及一些密度可達(dá)簇的合并。當(dāng)沒有新的點(diǎn)可以被添加到任何簇時，該過程結(jié)束。77（1）DBSCAN：基于高密度連通區(qū)域聚類：基于高密度連通區(qū)域聚類算法：DBSCAN輸入：D：數(shù)據(jù)對象集合Eps：鄰域或稱為半徑

53、MinPts：密度閾值輸出：k個簇，使平方誤差最小方法：Step1 讀取D中任意一個未分類的對象p；Step2 檢索出與p的距離不大于Eps的所有對象Neps(p)； Step3 如果 |Neps(p)|MinPts，則剔除已經(jīng)打上標(biāo)記的對象，將余下的未分類對象打上類標(biāo)簽newid，然后壓入堆棧；Step6 Seeds.pop，判斷Seeds是否為空，是，則執(zhí)行Step1 ，否則執(zhí)行Step5。79（1）DBSCAN：基于高密度連通區(qū)域聚類：基于高密度連通區(qū)域聚類DBSCAN算法不僅可以發(fā)現(xiàn)任意形狀的聚類，對數(shù)據(jù)輸入順序不敏感，并且具有處理異常數(shù)據(jù)（噪聲）的能力。DBSCAN算法對用戶定義的參

54、數(shù)是敏感的，而參數(shù)的恰當(dāng)選擇是需要有相關(guān)經(jīng)驗(yàn)的。80（2）OPTICS：通過點(diǎn)排序識別聚類結(jié)構(gòu)：通過點(diǎn)排序識別聚類結(jié)構(gòu)對于真實(shí)的，高維的數(shù)據(jù)集合而言，參數(shù)的設(shè)置通常是依靠經(jīng)驗(yàn)，難以確定。絕大多數(shù)算法對參數(shù)值是非常敏感的：設(shè)置的細(xì)微不同可能導(dǎo)致差別很大的聚類結(jié)果。OPTICS算法通過對象排序識別聚類結(jié)構(gòu)。OPTICS沒有顯式地產(chǎn)生一個數(shù)據(jù)集合簇，它為自動和交互的聚類分析計算一個簇排序。這個次序代表了數(shù)據(jù)的基于密度的聚類結(jié)構(gòu)。81（3）DENCLUE：基于密度分布函數(shù)的聚類：基于密度分布函數(shù)的聚類DENCLUE是對k-means聚類算法的一個推廣：DENCLUE算法得到的是全局最優(yōu)劃分。DENCL

55、UE主要基于：每個數(shù)據(jù)點(diǎn)的影響可以用一個數(shù)學(xué)函數(shù)來形式化地模擬，它描述了一個數(shù)據(jù)點(diǎn)在鄰域內(nèi)的影響，被稱為影響函數(shù)；數(shù)據(jù)空間的整體密度可以被模型化為所有數(shù)據(jù)點(diǎn)的影響函數(shù)的總和；然后聚類可以通過確定密度吸引點(diǎn)來得到，這里的密度吸引點(diǎn)是全局密度函數(shù)的局部最大。82（3）DENCLUE：基于密度分布函數(shù)的聚類：基于密度分布函數(shù)的聚類DENCLUE算法步驟：Step1 對數(shù)據(jù)點(diǎn)占據(jù)的空間推導(dǎo)密度函數(shù)；Step2 識別局部最大點(diǎn)；Step3 通過沿密度增長最大的方向移動，將每個點(diǎn)關(guān)聯(lián)到一個密度吸引點(diǎn)；Step4 定義與特定的密度吸引點(diǎn)相關(guān)聯(lián)的點(diǎn)構(gòu)成的簇；Step5 丟棄密度吸引點(diǎn)的密度小于用戶指定閾值的簇

56、；Step6 合并通過密度大于等于的點(diǎn)路徑連接的簇。836.4.6 基于網(wǎng)格的聚類方法基于網(wǎng)格的聚類方法基于網(wǎng)格的方法把對象空間量化為有限數(shù)目的單元，形成了一個網(wǎng)格結(jié)構(gòu)。所有的聚類操作都在這個網(wǎng)格結(jié)構(gòu)（即量化的空間）上進(jìn)行。這種方法的主要優(yōu)點(diǎn)是處理速度快，其處理時間獨(dú)立于數(shù)據(jù)對象的數(shù)目，僅依賴于量化空間中每一維上的單元數(shù)目。（1）STING：統(tǒng)計信息網(wǎng)格聚類（2） WaveCluster：利用小波變換聚類84（ 1）STING：統(tǒng)計信息網(wǎng)格聚類：統(tǒng)計信息網(wǎng)格聚類STING是一種基于網(wǎng)格的多分辨率聚類技術(shù)，它將空間區(qū)域劃分為矩形單元。針對不同級別的分辨率，通常存在多個級別的矩形單元，這些單元形成

57、了一個層次結(jié)構(gòu)：高層的每個單元被劃分為多個低一層的單元。關(guān)于每個網(wǎng)格單元屬性的統(tǒng)計信息（例如平均值、最大值和最小值）被預(yù)先計算和存儲。這些統(tǒng)計信息用于回答查詢。85（1）STING：統(tǒng)計信息網(wǎng)格聚類：統(tǒng)計信息網(wǎng)格聚類優(yōu)點(diǎn)：計算是獨(dú)立于查詢的；有利于并行處理和增量更新；效率很高。86（1）STING：統(tǒng)計信息網(wǎng)格聚類：統(tǒng)計信息網(wǎng)格聚類缺點(diǎn)如果粒度比較細(xì)，處理的代價會顯著增加；但是，如果網(wǎng)格結(jié)構(gòu)最低層的粒度太粗，將會降低聚類分析的質(zhì)量；在構(gòu)建一個父親單元時沒有考慮孩子單元和其相鄰單元之間的關(guān)系，因此，結(jié)果簇的形狀是isothetic，即所有的聚類邊界或者是水平的，或者是豎直的，沒有對角的邊界。盡管

58、該技術(shù)有快速的處理速度，但可能降低簇的質(zhì)量和精確性。87（2）WaveCluster：利用小波變換聚類：利用小波變換聚類WaveCluster是一種多分辨率的聚類算法，首先通過在數(shù)據(jù)空間上加一個多維網(wǎng)格結(jié)構(gòu)來匯總數(shù)據(jù)，然后采用一種小波變換來變換原特征空間，在變換后的空間中找到密集區(qū)域。在該方法中，每個網(wǎng)格單元匯總了一組映射到該單元中的點(diǎn)的信息。這種匯總信息適合于在內(nèi)存中進(jìn)行多分辨率小波變換和隨后的聚類分析使用。88（2）WaveCluster：利用小波變換聚類：利用小波變換聚類強(qiáng)調(diào)點(diǎn)密集的區(qū)域，而忽視在密集區(qū)域外的較弱的信息。在原始特征空間中的密集區(qū)域成為了附近點(diǎn)的吸引點(diǎn)， 距離較遠(yuǎn)的點(diǎn)成為抑

59、制點(diǎn)。能夠自動地排除孤立點(diǎn)。有助于發(fā)現(xiàn)不同精度的聚類。聚類速度很快。可以并行化。896.4.7 基于模型的聚類方法基于模型的聚類方法 （1） 統(tǒng)計學(xué)方法COBWEB（2）神經(jīng)網(wǎng)絡(luò)方法SOMs（3）高維數(shù)據(jù)聚類方法90（1）統(tǒng)計學(xué)方法）統(tǒng)計學(xué)方法COBWEB COBWEB算法將對象增量地加入到分類樹中。 COBWEB算法沿著一條適當(dāng)?shù)穆窂较蛳?，修改計?shù)，尋找可以分類該對象的最好節(jié)點(diǎn)。 COBWEB算法也計算為給定對象創(chuàng)建一個新的節(jié)點(diǎn)所產(chǎn)生的分類效用。它與基于現(xiàn)存節(jié)點(diǎn)的計算相比較。根據(jù)產(chǎn)生最高分類效用的劃分，對象被置于一個已存在的類，或者為它創(chuàng)建一個新類。COBWEB算法可以自動修正劃分中類的數(shù)目

60、。它不需要用戶提供這樣的輸入?yún)?shù)。91（1）統(tǒng)計學(xué)方法）統(tǒng)計學(xué)方法COBWEB CORWEB算法的優(yōu)點(diǎn)：它不需要用戶輸入?yún)?shù)來確定分類的個數(shù)，它可以自動修正劃分中類的數(shù)目。缺點(diǎn)：首先，它基于這樣一個假設(shè)：在每個屬性上的概率分布是彼此獨(dú)立的。由于屬性間經(jīng)常是相關(guān)的，這個假設(shè)并不總是成立。此外，聚類的概率分布表示使得更新和存儲類相當(dāng)昂貴。因?yàn)闀r間和空間復(fù)雜度不只依賴于屬性的數(shù)目，而且取決于每個屬性的值的數(shù)目，所以當(dāng)屬性有大量的取值時情況尤其嚴(yán)重。92（2）神經(jīng)網(wǎng)絡(luò)方法）神經(jīng)網(wǎng)絡(luò)方法SOMs算法步驟：Step1 隨機(jī)選取一組輸入層神經(jīng)元到輸出層神經(jīng)元之間的權(quán)值；Step2 選取輸出神經(jīng)元j 的鄰接神