數(shù)據(jù)挖掘各類算法綜述

1、數(shù)據(jù)挖掘各類算法綜述了解數(shù)據(jù)挖掘的各類算法的原理和應(yīng)用領(lǐng)域以及優(yōu)缺點(diǎn)對于在實(shí)際的工作中選擇合適的方法，并加以改進(jìn)有很重要的指導(dǎo)意義。1.1 關(guān)聯(lián)規(guī)則挖掘算法RAgrawal等人于1993年首先提出了挖掘顧客交易數(shù)據(jù)庫中項(xiàng)集間的關(guān)聯(lián)規(guī)則問題，其核心方法是基于頻集理論的遞推方法。此后人們對關(guān)聯(lián)規(guī)則的挖掘問題進(jìn)行了大量研究，包括對Apriori算法優(yōu)化、多層次關(guān)聯(lián)規(guī)則算法、多值屬性關(guān)聯(lián)規(guī)則算法、其他關(guān)聯(lián)規(guī)則算法等，以提高算法挖掘規(guī)則的效率。(a) Apriori算法Apriori算法是最有影響的挖掘布爾關(guān)聯(lián)規(guī)則頻繁項(xiàng)集的算法。算法Apriori利用“在給定的事務(wù)數(shù)據(jù)庫D中，任意頻繁項(xiàng)集的非空子集都必

2、須也是頻繁的”這一原理對事務(wù)數(shù)據(jù)庫進(jìn)行多次掃描，第一次掃描得出頻繁1-項(xiàng)集L,第k(k>1)次掃描前先利用第k-1次掃描的結(jié)果(即頻繁k-1項(xiàng)集Lk-1)和函數(shù)Apriorigen產(chǎn)生候選k-項(xiàng)集Ck,然后在掃描過程中確定Ck女中每個(gè)元素的支持?jǐn)?shù)，最后在每次掃描結(jié)束時(shí)計(jì)算出頻繁k-項(xiàng)集Lk,算法在當(dāng)頻繁n-項(xiàng)集為空時(shí)結(jié)束。算法：Apriori,使用根據(jù)候選生成的逐層迭代找出頻繁項(xiàng)集輸入：事務(wù)數(shù)據(jù)庫D;最小支持度閾值min_sup輸出：D中的頻繁項(xiàng)集L方法：(1) L1=find_frequent_1itemsets(D);(2) for(k=2;Lk-1w；k+)(3) Ck=aprio

3、ri_gen(Lk-1,min_sup);(4) foreachtransactiontCD/scanDforcounts(5) Ct=subset(Ck,t);/getthesubsetoftthatarecandidates(6) foreachcandidatecCCt(7) c.count+;(8)(9)Lk=cCk|c.count>min_sup;(1) (2) returnL=UkLk;/apriori_gen用來產(chǎn)生候選k項(xiàng)集procedureapriori_gen(Lk-1:(k-1)項(xiàng)頻繁集,min_sup:最小值尺度)(13) foreachitemsetI1CLk-

4、1(14) foreachitemsetI2CLk-1(15) if(l11=l21)A(l12=l22)A,A(l1k-2=l2k-2)A(l1k-1<l2k-1)then(16) c=l1自連接l2；產(chǎn)生候選項(xiàng)集(17) ifhas_infrequent_subset(c,Lk-1)then(18) deletec;/根據(jù)性質(zhì)作剪枝操作(19) elseaddctoCk;(20) (21) returnCk;/procedurehas_infrequent_subse(c,Lk-1)(5) foreach(k-1)-subsetsofc(6) ifsQLk-1then(7) retu

5、rnTrue;(8) returnfalse;appriori_gen做兩個(gè)動(dòng)作：連接和剪枝。在連接部分，Lk-1與Lk-1連接產(chǎn)生可能的候選(1-4步)。剪枝部分(第5-7步)使用Apriori性質(zhì)刪除具有非頻繁子集的候選。非頻繁子集的測試在過程has_infrequent_subse中。有了頻繁項(xiàng)集就可以通過如下的方法得到強(qiáng)關(guān)聯(lián)規(guī)則：對于每個(gè)頻繁項(xiàng)集L,產(chǎn)生L的所有非空子集對于L的每個(gè)非空子集s,如果support_count(L)/support_count(s)>min_conf,則輸出規(guī)則“sf(L-s)”。其中min_conf是最小置信度閾值為了提高Apriori的有效性，后

6、來又出現(xiàn)了基于散列、實(shí)物壓縮、劃分、采樣和動(dòng)態(tài)項(xiàng)計(jì)數(shù)多個(gè)改進(jìn)算法。然而對于基于Apriori的頻集方法，即使進(jìn)行了優(yōu)化，一些固有的缺陷還是無法克服。Apriori的算法及其優(yōu)化算法可能產(chǎn)生大量的候選集。當(dāng)長度為1的頻集有10000個(gè)的時(shí)候，長度為2的候選集就會(huì)成指數(shù)倍增長，其候選集個(gè)數(shù)將會(huì)超過10。如果要生成一個(gè)很長的規(guī)則時(shí)，要產(chǎn)生的中間元素也是巨大量的，此可采用FPW算法解決。FP樹算法FPW算法采用了一種FP-growth的方法。它采用了分而治之的策略：在對數(shù)據(jù)庫進(jìn)行第一次掃描后，把找到的頻集項(xiàng)壓縮進(jìn)一棵頻繁模式樹(FP-tree),同時(shí)依然保留其中的關(guān)聯(lián)信息。隨后再將FP-tree分化成

7、一些條件庫，每個(gè)庫和一個(gè)長度為1的頻集相關(guān)。然后再對這些條件庫分別進(jìn)行挖掘。當(dāng)原始數(shù)據(jù)量很大的時(shí)候，也可以結(jié)合劃分的方法，使得一個(gè)FP-tree可以放入主存中。實(shí)驗(yàn)表明，F(xiàn)P-growth對不同長度的規(guī)則都有很好的適應(yīng)性，同時(shí)在效率上比Apriori算法有很大的提高。算法：FP-增長。使用FP-樹，通過模式段增長，挖掘頻繁模式。輸入：事務(wù)數(shù)據(jù)庫D;最小支持度閾值min_sup;輸出：頻繁模式的完全集方法：按以下步驟構(gòu)造FP-樹：掃描數(shù)據(jù)庫D-次。收集頻繁項(xiàng)的集合F和它們的支持度。XF按照支持度降序排序，結(jié)果為頻繁項(xiàng)表L。創(chuàng)建FP-樹的根節(jié)點(diǎn)，以"null標(biāo)記。對于D中每個(gè)事務(wù)Tran

8、s,執(zhí)行：選擇Trans中的頻繁項(xiàng)，并按L中的次序排序。設(shè)排序后的頻繁項(xiàng)表為p|P,其中p是第一個(gè)元素，而幅剩下的元素表。調(diào)用insert_tree(p|P,T)。該過程執(zhí)行情況如下：如果TW子女楸得N.item-name=p.item-name,則題計(jì)數(shù)增加1;否則創(chuàng)建一個(gè)新節(jié)點(diǎn)N,將其計(jì)數(shù)設(shè)置為1,鏈接到它的父節(jié)點(diǎn)T,并且通過節(jié)點(diǎn)鏈結(jié)構(gòu)將其鏈接到具有相同item-name的節(jié)點(diǎn)。如果P非空遞歸地調(diào)用insert_tree(P,N)。FP-樹的挖掘通過調(diào)用FP-growth(FP_tree,null)實(shí)現(xiàn)。該過程實(shí)現(xiàn)如下：ProcedureFP_growth(Tree,a)ifTree含單個(gè)

9、路徑Pthenfor路徑P中節(jié)點(diǎn)的每個(gè)組合(記作3)產(chǎn)生模式3Ua,其支持度support=3中節(jié)點(diǎn)的最小支持度elseforeachai在Tree的頭部產(chǎn)生一個(gè)模式3=aiUa,其支持度support=ai.support構(gòu)造3的條件模式基，然后構(gòu)造3的條件FP-機(jī)nreepifTreepwthen調(diào)用FP_growth(Treep,3);3)多維關(guān)聯(lián)規(guī)則挖掘它指關(guān)聯(lián)規(guī)則涉及兩個(gè)或兩個(gè)以上變量。根據(jù)是否允許同一個(gè)維重復(fù)出現(xiàn)，多維關(guān)聯(lián)規(guī)則又可以細(xì)分為維間關(guān)聯(lián)規(guī)則(不允許維重復(fù)出現(xiàn))和混合維關(guān)聯(lián)規(guī)則(允許維在規(guī)則的左右同時(shí)出現(xiàn))。比如“年齡20至30,喜歡郊游一喜歡游泳”就是混合維關(guān)聯(lián)規(guī)則。維間

10、關(guān)聯(lián)規(guī)則和混合維關(guān)聯(lián)規(guī)則的挖掘還要考慮不同數(shù)據(jù)字段的類型。1.2分類算法近年來，數(shù)據(jù)挖掘分類已提出了很多算法，按大的方向分類主要有：決策樹、關(guān)聯(lián)規(guī)則、貝葉斯、神經(jīng)網(wǎng)絡(luò)、規(guī)則學(xué)習(xí)、k-臨近法、遺傳算法、粗糙集以及模糊邏輯技術(shù)等1)決策樹分類算法決策樹是一個(gè)類似于流程圖的樹結(jié)構(gòu)，其中每個(gè)內(nèi)部節(jié)點(diǎn)表示在一個(gè)屬性上的測試，每個(gè)分枝代表一個(gè)測試輸出，而每個(gè)樹節(jié)點(diǎn)代表類或類分布。樹的最頂層節(jié)點(diǎn)是根節(jié)點(diǎn)。決策樹算法的類型主要有基于決策樹歸納、強(qiáng)調(diào)在數(shù)據(jù)挖掘中可伸縮性的決策樹算法、決策樹歸納屬性選擇度量比較等。決策樹歸納算法ID3算法是較早也是最著名的決策樹歸納算法。該算法利用信息論中的互信息(信息增益)尋找

11、數(shù)據(jù)中具有最大信息增益的屬性字段，建立決策樹的一個(gè)節(jié)點(diǎn)，再根據(jù)該屬性字段的不同取值建立樹的分支。在每個(gè)分支子集中重復(fù)建立樹的下層節(jié)點(diǎn)和分支過程。這種方法的優(yōu)點(diǎn)是描述簡單、分類速度快，特別適合大規(guī)模的數(shù)據(jù)處理。但I(xiàn)D3算法是借用信息論中的互信息作為單一屬性能力的度量，其啟發(fā)式函數(shù)并不是最優(yōu)的，存在的主要問題有：互信息的計(jì)算依賴于屬性取值的較多特征，而這一屬性不一定最優(yōu)；ID3是非遞增學(xué)習(xí)算法；抗噪性差，訓(xùn)練例子中正例和反例較難控制。又ID3算法的早期改進(jìn)算法主要是ID3的增量版ID4、ID5及C4.5、CARTFACf口CHAI陰法等。后期的改進(jìn)算法主要有QUES和PUBLIC。算法：Gener

12、ate_decision_tree由給定的訓(xùn)練數(shù)據(jù)產(chǎn)生一棵判定樹輸入：訓(xùn)練樣本samples,由離散值屬性表示；候選屬性的集合attribute_list輸出：一個(gè)判定樹方法：創(chuàng)建節(jié)點(diǎn)N;ifsamples都在同一個(gè)類Cthen返回N乍為葉結(jié)點(diǎn)，以類的記；ifattribute_list為空then返回N乍為葉節(jié)點(diǎn)，標(biāo)記為samples中最普通的類；/多數(shù)表決選擇attribute_list中具有最高信息增益的屬性test_attribute;標(biāo)記節(jié)點(diǎn)N為test_attribute;foreachtest_attribute中的已知值ai/戈U分samples由節(jié)點(diǎn)N長出一個(gè)條件為test_

13、attribute=ai的分枝(10)設(shè)si是samples中test_attribute=的樣本的集合；/一個(gè)劃分(11)ifsi為空then(12)加上一個(gè)樹葉，標(biāo)記為samples中最普通的類；(13)else力口上個(gè)由Generate_decision_tree(si,attribute_list-test_attribute)返回的節(jié)點(diǎn)；強(qiáng)調(diào)可伸縮性的決策樹算法以上討論的算法對于小的數(shù)據(jù)集是很有效的。當(dāng)這些算法用于現(xiàn)實(shí)世界中非常大的數(shù)據(jù)庫的挖掘時(shí)，有效性和可伸縮性就成了需要關(guān)注的問題。大部分決策樹算法都限制訓(xùn)練樣本駐留主存，這一限制制約了這些算法的可伸縮性。為解決這一問題，一些可伸縮

14、性的決策樹算法相繼推出，如SLIQ、SPRINT“雨林”和BOAfT法等。2)貝葉斯分類算法貝葉斯分類基于貝葉斯定理。分類算法的比較研究發(fā)現(xiàn)，一種稱作樸素貝葉斯分類的簡單貝葉斯分類算法可以與決策樹和神經(jīng)網(wǎng)絡(luò)分類算法相媲美。理論上講，與其他的分類算法相比，貝葉斯分類具有最小的出錯(cuò)率。然而由于對其應(yīng)用的假定的不準(zhǔn)確性以及缺乏可用的概率數(shù)據(jù)，導(dǎo)致實(shí)踐中并非如此。貝葉斯分類還可以用來為不直接使用貝葉斯定理的其他分類算法提供理論判定。樸素貝葉斯分類的工作過程：(1)每個(gè)數(shù)據(jù)樣本用一個(gè)n維特征向量X=x1,X2,X3，,Xn表示，分別描述對n個(gè)屬性Ai,A2,A3,樣本的n個(gè)度量。(2)假定有mt類Q,C

15、2,Cn給定一個(gè)未知的數(shù)據(jù)樣本X(即沒有類標(biāo)號)，分類法將預(yù)測X屬于具有最高后3概率(條件X下)的類。即是說，樸素貝葉斯分類將未知的樣本分配給Q,當(dāng)且僅當(dāng)p(Ci|X)>p(Cj|X),1<j<m,JWi這樣最大化p(Ci|X)。(3)由于P(X)對于所有類為常數(shù)，只需要P(X|Ci)P(Ci)最大即可。如果類的先驗(yàn)概率未知，則通常假定這些類是等概率的。并據(jù)此對P(Ci|X)最大化。否則最大化P(X|Ci)P(Ci)。(4)給定具有許多屬性白數(shù)據(jù)集，計(jì)算P(Ci|X)的開銷可能非常大。為降低開銷，可以做類條件獨(dú)立的樸素假定。給定樣本的類標(biāo)號，假定屬性值相互條件獨(dú)立，即在屬性間

16、，不存在依賴關(guān)系。(5)為對未知樣本X分類，對每個(gè)類Ci,計(jì)算P(X|Ci)P(Ci)。樣本X被指派到類Ci,當(dāng)且僅P(X|Ci)P(Ci)>P(X|Cj)P(Cj),1wjWm,Jwl換言之，X被指派到其(X|Ci)P(Ci)最大的類Ci3)神經(jīng)網(wǎng)絡(luò)算法神經(jīng)網(wǎng)絡(luò)是大量的簡單神經(jīng)元按一定規(guī)則連接構(gòu)成的網(wǎng)絡(luò)系統(tǒng)。它能夠模擬人類大腦的結(jié)構(gòu)和功能，采用某種學(xué)習(xí)算法從訓(xùn)練樣本中學(xué)習(xí)，并將獲取的知識存儲(chǔ)在網(wǎng)絡(luò)各單元之間的連接權(quán)中。神經(jīng)網(wǎng)絡(luò)主要有前向神經(jīng)網(wǎng)絡(luò)、后向神經(jīng)網(wǎng)絡(luò)和自組織網(wǎng)絡(luò)。在數(shù)據(jù)挖掘領(lǐng)域，主要采用前向神經(jīng)網(wǎng)絡(luò)提取分類規(guī)則。神經(jīng)網(wǎng)絡(luò)算法最早在文獻(xiàn)10中得出，此后又提出許多變形，包括替換的誤

17、差函數(shù)、網(wǎng)絡(luò)拓?fù)涞膭?dòng)態(tài)調(diào)整、學(xué)習(xí)率和要素參數(shù)的動(dòng)態(tài)調(diào)整。近年來，從神經(jīng)網(wǎng)絡(luò)中提取規(guī)則受到越來越多的關(guān)注。這主要有以下二種傾向：(1)網(wǎng)絡(luò)結(jié)構(gòu)分解的規(guī)則提??；(2)由神經(jīng)網(wǎng)絡(luò)的非線性映射關(guān)系提取規(guī)則。未來神經(jīng)網(wǎng)絡(luò)的發(fā)展可向進(jìn)一步降低算法的復(fù)雜度、提高所提取規(guī)則的可理解性及算法的適用性方向發(fā)展。下面是后向傳播算法算法：后向傳播。使用后向傳播算法的神經(jīng)網(wǎng)絡(luò)分類學(xué)習(xí)輸入：訓(xùn)練樣本sample,學(xué)習(xí)率1,多層前饋網(wǎng)絡(luò)network輸出：一個(gè)訓(xùn)練的、對樣本分類的神經(jīng)網(wǎng)絡(luò)方法：初始化network的權(quán)和偏置while終止條件不滿足forsamples中的每個(gè)訓(xùn)練樣本X/向前傳播輸入for隱藏或輸出層每個(gè)單元

18、jIj=2iWjO+0j;/相對于前一層i,計(jì)算單元j的凈輸入Oj=1/(1+e-lj);/計(jì)算每個(gè)單元j的輸出/向后傳播誤差for輸出層每個(gè)單元jErrj=Oj(1-Oj)(Tj-Oj);/計(jì)算誤差(11)for由最后一個(gè)到第一個(gè)隱藏層，對于隱藏層每個(gè)單元(12)Errj=Oj（1-Oj）2ErrkVjk;/計(jì)算關(guān)于下一個(gè)較高層k的誤差fornetwork中每個(gè)權(quán)WijAVj=(l)ErrjOj;/權(quán)增值Wij=Wij+AWj;/權(quán)更新fornetwork中每個(gè)偏差0jA0j=(l)Errj;/偏差增值0j=0j+A0j;/偏差更新4）遺傳算法遺傳算法是模擬生物進(jìn)化過程的全局優(yōu)化方法，將較劣

19、的初始解通過一組遺傳算子（繁殖一一即選擇、交叉一一即重組、變異一一即突變），在求解空間按一定的隨機(jī)規(guī)則迭代搜索，直到求得問題的最優(yōu)解。遺傳算法在數(shù)據(jù)挖掘領(lǐng)域的主要應(yīng)用有：（1）用它和BFW法結(jié)合訓(xùn)練神經(jīng)網(wǎng)絡(luò)，然后從網(wǎng)絡(luò)提取規(guī)則；（2）分類系統(tǒng)的設(shè)計(jì)，如編碼方式、信任分配函數(shù)的設(shè)計(jì)以及遺傳算法的改進(jìn)等。遺傳算法用于數(shù)據(jù)挖掘存在的問題是：（1）算法較復(fù)雜，（2）收斂于局部極小的過早收斂等難題未得到解決。5）其他基于案例的推理（CaseBasedReasoning,CBR分類法是基于要求的。不像最臨近分類法將訓(xùn)練樣本作為歐氏空間的點(diǎn)存放，CB存放的樣本或“案例”是復(fù)雜的符號描述。它試圖組合臨近的訓(xùn)練

20、案例，提出新案例的解?；诎咐耐评砜赡苁褂帽尘爸R和問題求解策略，以便提出可行的組合解?；诎咐耐评泶嬖诘奶魬?zhàn)包括找到一個(gè)好的相似度量，開發(fā)對訓(xùn)練案例索引的有效技術(shù)和組合解的方法。粗糙集方法用于分類主要發(fā)現(xiàn)不準(zhǔn)確數(shù)據(jù)或噪聲數(shù)據(jù)內(nèi)在的結(jié)構(gòu)聯(lián)系，它用于離散值屬性，也可以用于特征歸約和相關(guān)分析。粗糙集已用于許多應(yīng)用的特征歸約和專家系統(tǒng)中。模糊集方法提供了在高抽象層處理的便利。一般地，模糊邏輯在基于規(guī)則的系統(tǒng)中的使用涉及：（1）將屬性值轉(zhuǎn)換成模糊值；（2）對于給定的新樣本，可以使用多個(gè)模糊規(guī)則；（3）組合上面得到的和，得到一個(gè)系統(tǒng)返回的值。1.3聚類算法目前，文獻(xiàn)中存在著大量的聚類算法，通?？梢苑?/p>

21、為基于分割的、基于層次的、基于密度的、基于網(wǎng)格的和基于模型的聚類方法五大類。1)分割的聚類方法分割聚類算法是將數(shù)據(jù)集分成若干子集.即給定一個(gè)例子的集合x,其中包括n個(gè)數(shù)據(jù)對象，并要生成數(shù)目為K勺簇。常用的基于分割的聚類方法有均值(Kmeans)法和中心法,CLAR袪和CLARANS等。K-均值法K-均值法首先由MacQueni出，它以K為參數(shù)，將n個(gè)對象分成K個(gè)簇，以使簇內(nèi)具有較高的相似度，而簇間的相似度較低.其相似度的計(jì)算根據(jù)一個(gè)簇中對象的平均值來進(jìn)行。此方法能有效地處理簇內(nèi)密集，但簇間區(qū)別明顯的數(shù)據(jù)的聚類，其時(shí)間復(fù)雜度為o(nkt),(其中t是迭代次數(shù))，因此有相對較高的可伸縮性和高效率。

22、但它只能聚類數(shù)值型的數(shù)據(jù)，且要求用戶必須事先確定參數(shù)K,也不適合發(fā)現(xiàn)非凸面形狀的簇或大小差別很大的簇，聚類結(jié)果與數(shù)據(jù)的輸入順序也有明顯的關(guān)系，對于“噪聲”和孤立點(diǎn)數(shù)據(jù)也是敏感的。算法：K-均值。劃分的k-均值算法基于簇中對象的平均值輸入：簇的數(shù)目由口包含n對象的數(shù)據(jù)庫輸出：k個(gè)簇，使平方誤差準(zhǔn)則最小方法：(1)任意選擇k個(gè)對象作為初始的簇中心(2)repeat(3)根據(jù)簇中對象的平均值，將每個(gè)對象(重新)賦給最類似的簇；(4)更新簇的平均值，即計(jì)算每個(gè)簇中對象的平均值until不再發(fā)生變化K-中心點(diǎn)方法它的基本策略是：首先為每個(gè)簇隨意選擇一個(gè)代表對象，剩余的對象根據(jù)其與代表對象的距離分配給最近

23、的一個(gè)簇，然后反復(fù)地用非代表對象來替代代表對象，以改進(jìn)聚類的質(zhì)量。這種方法能有效處理小數(shù)據(jù)集，且也能有效處理“噪聲”和孤立點(diǎn)，但其仍要求用戶輸入?yún)?shù)K,且算法的執(zhí)行代價(jià)比K-均值法高，沒有良好的伸縮性。算法：k-中心點(diǎn)。對基于中心點(diǎn)或者中心對象的劃分的典型k-中心點(diǎn)算法輸入：結(jié)果簇的數(shù)目k,包含n個(gè)對象的數(shù)據(jù)庫輸出：k個(gè)簇。使得所有對象與其最近中心點(diǎn)的相異度總和最小方法：(1)隨機(jī)選擇k個(gè)對象作為初始的中心點(diǎn)(2)repeat(3)指派每個(gè)剩余的對象給離它最近的中心點(diǎn)所代表的簇；(4)隨機(jī)地選擇一個(gè)非中心點(diǎn)對象Qandom；(5)計(jì)算用Qandomf弋替O的總代價(jià)S；ifS>0,then

24、Orandom>換。，形成新的k個(gè)中心點(diǎn)的集合;until不再發(fā)生變化；Clara算法Clara(ClusteringLargeApplications)算法的主要思想是：不考慮整個(gè)數(shù)據(jù)集合，選擇實(shí)際數(shù)據(jù)的一小部分作為數(shù)據(jù)的樣本，然后用K-中心點(diǎn)法選擇中心點(diǎn)。Clara算法能夠處理大量的數(shù)據(jù)，其每步的迭代時(shí)間復(fù)雜度為o(ks2+k(n-k)，其中，S是樣本的大小，K是簇的數(shù)目，而n是所有對象的總數(shù)。因此其的效率取決于采樣的大小。但運(yùn)用該方法時(shí)，一般不太可能得到最佳的結(jié)果。Clarans算法Clarans(ClusteringLargeApplicationsbaseduponRandom

25、izedSearch)算法是種基于隨機(jī)搜索的方法，它是在Clara算法的基礎(chǔ)上提出來的，它與Clara算法不同的是：在Clara算法尋找最佳的中心點(diǎn)的過程中，采樣是不變的，而Clarans算法在每一次循環(huán)過程中所采用的采樣都是不一樣的。此方法的優(yōu)點(diǎn)是一方面改進(jìn)了Clara的聚類質(zhì)量，另一方面拓展了數(shù)據(jù)處理量的伸縮范圍。其有較好地聚類效果，但其計(jì)算復(fù)雜度仍為O(n2),因此，低效仍是其存在的缺點(diǎn)之一，雖對噪聲數(shù)據(jù)不敏感，但對數(shù)據(jù)輸入順序敏感，只能聚類凸?fàn)罨蚯蛐瓦吔纭?)層次聚類方法層次聚類法是把對給定的數(shù)據(jù)集按層次進(jìn)行分解，結(jié)果是形成一棵以數(shù)據(jù)子集為節(jié)點(diǎn)的現(xiàn)在類別樹。根據(jù)層次分解的方式不同，其又

26、可以分為凝聚的層次方法和分裂的層次方法。比較常用的層次聚類方法有BIRCHt、CUR造等。BIRCH法：利用層次方法的平衡迭代規(guī)約和聚類BIRCHt是一種綜合優(yōu)化的層次聚類的方法，它的核心是采用了一個(gè)三元組的聚類特征機(jī)CF)匯總了一個(gè)簇的有關(guān)信息，從而使一個(gè)簇的表示可以用對應(yīng)的聚類特征，而不必用具體的一組點(diǎn)表示，通過構(gòu)造分支因子所口簇直彳5閾值T來進(jìn)行增量和動(dòng)態(tài)聚類。BIRCH!法的優(yōu)點(diǎn)是采用了多種聚類技術(shù)，對數(shù)據(jù)庫的一次掃描產(chǎn)生一個(gè)基本好的聚類，一次或更多的附加掃描能夠提高聚類的質(zhì)量，比較適合于大型數(shù)據(jù)集。這個(gè)算法的時(shí)間復(fù)雜度為0(n),這里n為對象的樹木。該算法具有對對象數(shù)目的線性伸縮性，

27、及較好的聚類質(zhì)量。它的缺點(diǎn)是只適合于類的分布呈凸?fàn)罨蚯驙钋闆r，并且需要提供正確的聚類數(shù)和簇直徑T,不適于高維數(shù)據(jù)。BIRCH勺算法的兩個(gè)階段：階段一：BIRCH3描數(shù)據(jù)庫，建立一個(gè)初始存放于內(nèi)存的CFW,它可以被看作數(shù)據(jù)的多層壓縮，試圖保留數(shù)據(jù)內(nèi)在的聚類結(jié)構(gòu)。階段二：BIRCHI用某個(gè)聚類算法對CF樹的葉節(jié)點(diǎn)進(jìn)行聚類。CUR造：利用代表點(diǎn)聚類CURE法是一種很新穎的層次聚集算法，采用了基于質(zhì)心和基于代表對象方法之間的中間策略，它選擇數(shù)據(jù)空間中固定數(shù)目的具有代表性的點(diǎn)來代表一個(gè)簇，并將這些點(diǎn)乘以一個(gè)適當(dāng)?shù)氖湛s因子，使它們更靠近簇的中心。它的時(shí)間復(fù)雜度為0(n)。其的優(yōu)點(diǎn)是選擇多個(gè)代表使得該算法可

28、以適應(yīng)非球狀的幾何形狀，簇的收縮或凝聚可以有助于控制噪聲的影響，同時(shí)該方法采用了隨機(jī)抽樣與分割相結(jié)合來提高效率，對大型數(shù)據(jù)庫有良好的收縮性。下面的步驟描述的CUR算法的核心：(1)從源數(shù)據(jù)對象中抽取一個(gè)隨機(jī)樣本So(2)將樣本陰割為一組劃分。(3)對每個(gè)劃分局部地聚類。(4)通過隨機(jī)取樣剔除孤立點(diǎn)。如果一個(gè)簇增長的太慢，就去掉它。(5)對局部的簇進(jìn)行聚類。落在每個(gè)新形成的簇中的代表點(diǎn)根據(jù)用戶定義的一個(gè)搜索因子”搜索或向簇中心移動(dòng)。這些點(diǎn)代表和捕捉到了簇的形狀。(6)用相應(yīng)的簇標(biāo)簽來標(biāo)記數(shù)據(jù)。Chameleon(變色龍)：一個(gè)利用動(dòng)態(tài)模型的層次聚類算法Chameleon是一個(gè)在層次聚類中采用動(dòng)態(tài)

29、模型的聚類算法。Chameleon的產(chǎn)生是基于對CUR的缺點(diǎn)。CUR吸其相關(guān)的方案忽略了關(guān)于兩個(gè)不同簇中對象的聚集互連性的信息，而ROC歐其相關(guān)的方案強(qiáng)調(diào)對象間互連性，卻忽略了關(guān)于對象間近似度的信息。Chameleon的主要思想：首先通過一個(gè)圖劃分算法將數(shù)據(jù)對象聚類為大量相對較小的子聚類，然后用一個(gè)凝聚的層次聚類算法通過反復(fù)地合并子類來找到真正的結(jié)果簇。它既考慮了互連性，又考慮了簇間的相似度，特別是簇內(nèi)部的特征，來確定最相似的子簇。3)基于密度的聚類方法這種算法的主要思想為：只要臨近區(qū)域的(對象或數(shù)據(jù)點(diǎn)的數(shù)目)超過某個(gè)閾值，就繼續(xù)聚類，這樣就能很好的過濾掉“噪聲”數(shù)據(jù)，發(fā)現(xiàn)任意形狀的簇。具有代

30、表性的基于密度的方法有DBSCANOPTIC序口DEN-CLUE(DensityBasedClustering)等。DBSCAN:基于高密度連接區(qū)域的密度聚類方法DBSCAN(DensityBasedSpatialClusteringofApplicationswithNoise)的算法思想是：檢查一個(gè)對象的£領(lǐng)域的密度是否足夠高，即一定距離E內(nèi)數(shù)據(jù)點(diǎn)的個(gè)數(shù)是否超Minpts來確定是否建立一個(gè)以該對象為核心對象的新簇，再合并密度可達(dá)簇。它可以在帶有“噪聲”的空間數(shù)據(jù)庫中發(fā)現(xiàn)任意形狀的聚類，另外此算法可以通過不斷執(zhí)行區(qū)域查詢來實(shí)現(xiàn)聚類。其缺點(diǎn)是對輸入?yún)?shù)£和Minpts相對敏

31、感，且這兩參數(shù)難以確定。在算法復(fù)雜度上，若采用空間索引R-樹，其時(shí)間復(fù)雜度為O(n*logn),否則仍為O(n2)。OPTICS:通過對象排列識別聚類結(jié)構(gòu)OPTICS(OrderingPointtoIdentifyt|leClusteringStructure)是為了解決DBSCAN算法中參數(shù)£和Minpts難以確定而提出來的。它不顯式地產(chǎn)生一個(gè)數(shù)據(jù)集合簇，而是為自動(dòng)和交互的聚類分析計(jì)算一個(gè)聚類分析方法。因此OPTIC鼠產(chǎn)生的是一個(gè)基于密度的簇的次序集合，它的時(shí)間復(fù)雜度與DBSCAN同。DENCLUEDENCLUUE(DensityBasedClustering)是用一個(gè)影響函數(shù)來模

32、擬每個(gè)數(shù)據(jù)點(diǎn)在領(lǐng)域的影響，所有數(shù)據(jù)點(diǎn)的影響函數(shù)總和來模擬數(shù)據(jù)空間的整體密度，通過確定密度吸引點(diǎn)即整體密度函數(shù)的局部最大來發(fā)現(xiàn)簇。DENCLUE的主要優(yōu)點(diǎn)是可以處理高維數(shù)據(jù)，集中任意形狀的簇，且具有較強(qiáng)的抗噪能力，有較快地處理速度。它的缺點(diǎn)是要求輸入密度參數(shù)b和噪聲閾值£,且聚類結(jié)果對這兩參數(shù)比較敏感。4)基于網(wǎng)格的聚類方法基于網(wǎng)格的聚類方法是指采用一個(gè)多分辨率的網(wǎng)絡(luò)數(shù)據(jù)結(jié)構(gòu)。它首先將數(shù)據(jù)空間劃分成為有限個(gè)單元(cell)的網(wǎng)格結(jié)構(gòu)，并且所有的處理都是以單個(gè)的單元為對象的.常用的方法有統(tǒng)計(jì)信息網(wǎng)格法STING基于小波變換的聚類法WaveCluster法以及聚類高維空間法CIQUE法等。

33、STINGt：統(tǒng)計(jì)信息網(wǎng)絡(luò)STINGY(StatisticalInformationGrid)的基本思想是：先將數(shù)據(jù)空間劃分成矩形單元，對應(yīng)不同級別的分辨率，存在著不同級別的矩形單元，這些單元形成一個(gè)層次結(jié)構(gòu)：高層的每個(gè)單元被劃分為多個(gè)低一層的單元。高層單元的統(tǒng)計(jì)信息可以由計(jì)算低層單元獲得，而統(tǒng)計(jì)信息的查詢則采用自頂向下的基于網(wǎng)格的方法。這種方法的主要優(yōu)點(diǎn)是：網(wǎng)格結(jié)構(gòu)有利于并行處理和增量更新，且其的計(jì)算是獨(dú)立于查詢的，另外它的處理效率很高，它通過掃描數(shù)據(jù)庫一次來計(jì)算單元的統(tǒng)計(jì)信息，因此其聚類時(shí)間復(fù)雜度為O(n),在層次結(jié)構(gòu)建立后，其查詢處理的時(shí)間復(fù)雜度為O(g),其中，g為最低層網(wǎng)格單元的數(shù)目。它的缺點(diǎn)是聚類質(zhì)量取決于網(wǎng)格結(jié)構(gòu)最低層的粒度，而粒度的大小會(huì)明顯地影響處理代價(jià)；另外，它的結(jié)果簇的形狀是isothetie,即所有的聚類邊界或者是水平的，或者是豎直的，沒有對角的邊界。WaveCluster法：采用小波變換聚類WaveCluster法(ClusteringUsingWaveletTransformation)是一種基于網(wǎng)格和密度的多分辨率變換的聚類方法，它的算法思想是：首先在數(shù)據(jù)空間上強(qiáng)加一個(gè)多維網(wǎng)格結(jié)構(gòu)來匯總數(shù)據(jù)，然后采用一種小波變換來變換原特征空間，在變換后的空間找到聚類區(qū)域。該算法