數(shù)據(jù)挖掘fptree樹(編輯修改稿)
2024-07-16 22:52 本頁面
【文章內(nèi)容簡(jiǎn)介】 選集，而直接發(fā)現(xiàn)頻繁項(xiàng)集，從而找出感興趣的關(guān)聯(lián)規(guī)則呢。如果我們不產(chǎn)生大量的候選集，那么掃描事務(wù)數(shù)據(jù)庫進(jìn)行匹配的次數(shù)也自然就會(huì)大大降低。我在思考過程中，想到老師上課講到的一句話“把條件進(jìn)行簡(jiǎn)單化處理，先找出一個(gè)可行解”，這樣思維就大大開闊。聯(lián)系到《數(shù)據(jù)倉(cāng)庫與數(shù)據(jù)挖掘》在開始的課程“分類”中的第一個(gè)方法：決策樹，顯然關(guān)聯(lián)分析是進(jìn)行名詞性布爾值的分析，而決策樹的應(yīng)用范圍也正是名詞性數(shù)據(jù)的分類。我們來對(duì)比下，在決策樹算法中，我們根據(jù)元組的信息增益的大小來進(jìn)行生成樹的判斷依據(jù)。類比決策樹算法，我們可以利用關(guān)聯(lián)分析中事務(wù)發(fā)生的支持計(jì)數(shù)的大小來代替熵減值。根據(jù)我在《算法導(dǎo)論》中所學(xué)習(xí)到的思想——遞歸算法中的分治策略，再加上決策樹這個(gè)“先例”的借鑒，我對(duì)于提高Apriori算法的效率有了一個(gè)較為清晰的方向。首先，對(duì)于事務(wù)數(shù)據(jù)庫中的所有事務(wù)都是由一項(xiàng)集構(gòu)成的，所以我們可以根據(jù)在整個(gè)事務(wù)數(shù)據(jù)庫中所有的一項(xiàng)集的支持計(jì)數(shù)來進(jìn)行排序（類似決策樹中對(duì)于每個(gè)元組的熵減值計(jì)算）。接著，參考決策樹算法中樹的生成方法和分治策略思想，我們?cè)趻呙枋聞?wù)數(shù)據(jù)庫的一個(gè)事務(wù)時(shí)，根據(jù)第一步的排序順位，進(jìn)行調(diào)整，將該事務(wù)的所有項(xiàng)都有序化，依照順序建立一棵樹，下次的事務(wù)按照這個(gè)方法繼續(xù)對(duì)前面的樹的節(jié)點(diǎn)值進(jìn)行修改、增加節(jié)點(diǎn)或者生成另一棵樹，這樣我們就可以保證越靠近樹根的支持計(jì)數(shù)越高，而葉子節(jié)點(diǎn)的支持計(jì)數(shù)越低，十分有利于降低我們?cè)谕诰蛴腥ひ?guī)則時(shí)的開銷。經(jīng)過上面的分析后，我們對(duì)于怎么提高Apriori算法的有了一個(gè)有效的解決辦法。而且在2000年針對(duì)Apriori算法的固有缺陷， 算法。該算法直接將事務(wù)數(shù)據(jù)庫壓縮成一個(gè)頻繁模式樹，然后通過這棵樹生成關(guān)聯(lián)規(guī)則。而這個(gè)算法和我上面分析時(shí)提出的思想大致相同，下面我們?nèi)匀桓鶕?jù)書上的例子進(jìn)行FPtree算法的演示：第一步，進(jìn)行事務(wù)數(shù)據(jù)庫的掃描，得到每個(gè)一項(xiàng)集的支持計(jì)數(shù)，然后進(jìn)行排序。所有一項(xiàng)集的計(jì)數(shù)：{I1,6}，{I2,7}{I3,6},{I4,2},{I5,2}；按照支持計(jì)數(shù)進(jìn)行排序I2I1I3I4I576622 第二步，掃描事務(wù)數(shù)據(jù)庫的每個(gè)事務(wù)，生成樹。I1: 2I3: 2I5: 1I4: 1I3: 2
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1