數(shù)據(jù)挖掘fptree樹-預(yù)覽頁
【正文】 項(xiàng)集支持度計(jì)數(shù){I1，I2，I3}{I1，I2,I5}22項(xiàng)集支持度計(jì)數(shù){I1，I2，I3}{I1，I2,I5}22L3C3比較候選支持度計(jì)數(shù)與最小支持度計(jì)數(shù)由L2產(chǎn)生候選C3，并掃描D對每個(gè)候選計(jì)數(shù)比較候選支持度計(jì)數(shù)與最小支持度計(jì)數(shù) 通過此演示，我們可以清晰地發(fā)現(xiàn)：雖然在許多情況下，Apriori的候選產(chǎn)生檢查方法顯著壓縮了候選項(xiàng)集的大小，并導(dǎo)致很好的性能。下面以課本P151頁例53來進(jìn)行Apriori算法的演示。此外為發(fā)現(xiàn)長度為100的頻繁模式，如{a1,a2,…,a100},必須產(chǎn)生總過多達(dá)2^100大約為10^30個(gè)候選。 經(jīng)過上面的分析我們可以確定，Apriori算法的兩大限制：產(chǎn)生大量的候選集；重復(fù)掃描事務(wù)數(shù)據(jù)庫。顯然無論是降低掃描的事務(wù)數(shù)據(jù)庫的次數(shù)，還是壓縮產(chǎn)生的候選集，都是針對于Apriori算法本身的調(diào)整，這就不可能在本質(zhì)上解決Apriori算法的效率低下問題。聯(lián)系到《數(shù)據(jù)倉庫與數(shù)據(jù)挖掘》在開始的課程“分類”中的第一個(gè)方法：決策樹，顯然關(guān)聯(lián)分析是進(jìn)行名詞性布爾值的分析，而決策樹的應(yīng)用范圍也正是名詞性數(shù)據(jù)的分類。首先，對于事務(wù)數(shù)據(jù)庫中的所有事務(wù)都是由一項(xiàng)集構(gòu)成的，所以我們可以根據(jù)在整個(gè)事務(wù)數(shù)據(jù)庫中所有的一項(xiàng)集的支持計(jì)數(shù)來進(jìn)行排序（類似決策樹中對于每個(gè)元組的熵減值計(jì)算）。該算法直接將事務(wù)數(shù)據(jù)庫壓縮成一個(gè)頻繁模式樹，然后通過這棵樹生成關(guān)聯(lián)規(guī)則。挖掘前，先進(jìn)行一下解釋和定義：由每個(gè)長度為1的頻繁模式（初始后綴模式）開始，構(gòu)造它的條件模式基（一個(gè)“子數(shù)據(jù)庫”，由FP樹與后綴式一起出現(xiàn)的前綴路徑集組成），然后，構(gòu)造它的（條件）FP樹，并遞歸地對該樹進(jìn)行挖掘。因此次路徑產(chǎn)生的頻繁模式的所有組合：{I2，I5:2},{I1，I5:2},{I2，I1，I5：2}。由于我只是實(shí)現(xiàn)了FPtree算法，所以我直接運(yùn)用weka平臺進(jìn)行數(shù)據(jù)測試。同時(shí)由測試時(shí)時(shí)間不同Apriori算法耗時(shí)約8s,FPGrowth算法大概1s，便可清晰的看出FPtree算法對于Apriori算法的優(yōu)勢。同時(shí)也引起了我對數(shù)據(jù)挖掘課程繼續(xù)深入學(xué)習(xí)的興
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1