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

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

2、須也是頻繁的”這一原理對事務數(shù)據(jù)庫進行多次掃描，第一次掃描得出頻繁1-項集L,第k(k>1)次掃描前先利用第k-1次掃描的結(jié)果(即頻繁k-1項集Lk-1)和函數(shù)Apriorigen產(chǎn)生候選k-項集Ck,然后在掃描過程中確定Ck女中每個元素的支持數(shù)，最后在每次掃描結(jié)束時計算出頻繁k-項集Lk,算法在當頻繁n-項集為空時結(jié)束。算法：Apriori,使用根據(jù)候選生成的逐層迭代找出頻繁項集輸入：事務數(shù)據(jù)庫D;最小支持度閾值min_sup輸出：D中的頻繁項集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項集procedureapriori_gen(Lk-1:(k-1)項頻繁集,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)生候選項集(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做兩個動作：連接和剪枝。在連接部分，Lk-1與Lk-1連接產(chǎn)生可能的候選(1-4步)。剪枝部分(第5-7步)使用Apriori性質(zhì)刪除具有非頻繁子集的候選。非頻繁子集的測試在過程has_infrequent_subse中。有了頻繁項集就可以通過如下的方法得到強關聯(lián)規(guī)則：對于每個頻繁項集L,產(chǎn)生L的所有非空子集對于L的每個非空子集s,如果support_count(L)/support_count(s)>min_conf,則輸出規(guī)則“sf(L-s)”。其中min_conf是最小置信度閾值為了提高Apriori的有效性，后

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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