數(shù)據(jù)挖掘各類(lèi)算法綜述.doc

《數(shù)據(jù)挖掘各類(lèi)算法綜述.doc》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫(kù)。

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

2、頻繁項(xiàng)集的非空子集都必須也是頻繁的”這一原理對(duì)事務(wù)數(shù)據(jù)庫(kù)進(jìn)行多次掃描，第一次掃描得出頻繁卜項(xiàng)集L,第k(k>l)次掃描前先利用第k-l次掃描的結(jié)果(即頻繁k-1項(xiàng)集1山-1)和函數(shù)Apriori—gen產(chǎn)生候選k-項(xiàng)集Ck，然府在掃描過(guò)程中確主6女中每個(gè)元索的支持?jǐn)?shù)，最厲在每次掃描結(jié)束時(shí)計(jì)算出頻繁k-項(xiàng)集Lk,算法在當(dāng)頻繁葉項(xiàng)集為空時(shí)結(jié)束。算法：Apriori,使用根據(jù)候選生成的逐層迭代找出頻繁項(xiàng)集輸入：事務(wù)數(shù)據(jù)庫(kù)D;最小支持度閾值minsup輸出：D中的頻繁項(xiàng)集L方法：(1)Li=findfrequent1-itemsets(D);(2)for(k=2;Lk-iH①

3、；k++){(3)Ck=apriorigen(Lk-i,minsup);(4)foreachtransactiontuD{//seanDforcounts(5)Ct=subset(Ck,t);//getthesubsetoftthatareCandidates(6)foreachcandidsteceCt(7)c.count++;(8)}(1)Lk={cGCkIc.count》minsup};(11)returnL=UrLr；//apriori-gen用來(lái)產(chǎn)生候選k項(xiàng)集procedureapriorigen(Lr-i:(kT)項(xiàng)頻繁集,min_sup：最小值尺度)(1

4、)foreachitemsettGLk-iforeachitemsetfeeLk-iifA(6[2]=fe[2])A—A(6[k-2]=fe[k-2])A(6[k-i]

5、false;appriori￡en做兩個(gè)動(dòng)作：連接和剪枝。在連接部分，Lki與Lk-1連接產(chǎn)生對(duì)能的候選（1-4步）。剪枝-部分（第5-7步）使川Apriori性質(zhì)刪除具有非頻繁子集的候選。非頻繁子集的測(cè)試在過(guò)程has_infrequent_subse中。有了頻繁項(xiàng)集就可以通過(guò)如卜的方法得到強(qiáng)關(guān)聯(lián)規(guī)則：?對(duì)于每個(gè)頻繁項(xiàng)集L,產(chǎn)生L的所有非空子集?對(duì)于L的每個(gè)非空子集s,如果supportcount（L）/supportcount（s）2minconf,則輸出規(guī)則“s?（L-s）”o其中minconf是最小置信度閾值為了提高Apriori的有效性，后來(lái)乂出現(xiàn)了基于散列、

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

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