基于電子政務的改進FP_Growth算法研究和應用.pdf

1、隨著信息技術(shù)迅速發(fā)展，電子政務的數(shù)據(jù)量激增。面對這些大量的數(shù)據(jù)，傳統(tǒng)數(shù)據(jù)庫技術(shù)難以發(fā)掘隱藏在數(shù)據(jù)中的有用信息，導致了數(shù)據(jù)僅被存儲而得不到有效利用的局面。為解決這一問題，數(shù)據(jù)挖掘技術(shù)逐漸深入電子政務，取得了很好的效果。其中關(guān)聯(lián)規(guī)則是數(shù)據(jù)挖掘領(lǐng)域的重要研究課題，它揭示項集之間的有趣關(guān)系，被廣泛應用到商業(yè)，醫(yī)療，網(wǎng)絡和通信，生物學等各個領(lǐng)域。
　　關(guān)聯(lián)規(guī)則的概念是于1993年Agrawal等人提出，他們基于對超市購物的分析，提出了經(jīng)典的

2、Apriori算法，引起國內(nèi)外學者的關(guān)注和研究，也發(fā)展出更多的算法。其中應用最為廣泛的是J Han等人提出的FP Growth算法，算法不需要生成候選項集，具有較高的效率。
　　本文的主要工作如下:
　　(1)首先對FP_Growth算法進行分析，發(fā)現(xiàn)FP_ Growth算法的三點不足，一是仍需遍歷數(shù)據(jù)庫兩次，增加了開銷;二是挖掘過程中需要多次遍歷FP-樹以及條件FP-樹，效率低;三是整個過程需要遍歷項頭表，而算法中項頭表采

3、用順序結(jié)構(gòu)，查詢效率低，影響了算法的執(zhí)行效率。
　　(2)針對這幾點不足，本文對FP_Growth算法進行改進，提出了新的結(jié)構(gòu)FP-Table，基于FP-Table提出改進的TFP_Growth算法。算法僅需一次掃描數(shù)據(jù)庫，通過二維表生成FP-Table，然后基于FP-Table挖掘頻繁項集，在很大程度上提高了算法的執(zhí)行效率。對TFP_Growth算法分析發(fā)現(xiàn)生成的二維表中存在很多無效數(shù)據(jù)，造成內(nèi)存空間的浪費。為此本文提出兩種優(yōu)化

4、方案，方案一是對二維表進行壓縮，壓縮之后所需空間僅為原來的1/2，大大提高了算法的空間效率。方案二是針對稀疏數(shù)據(jù)集，采用二次掃描數(shù)據(jù)庫的方式，避免了生成無效數(shù)據(jù)，提高了處理稀疏數(shù)據(jù)的效率。
　　(3)然后針對電子政務數(shù)據(jù)特點，對算法做相應的處理，通過信訪示例說明在電子政務領(lǐng)域的應用過程，包括數(shù)據(jù)選擇，數(shù)據(jù)預處理，數(shù)據(jù)挖掘，信息應用等過程。綜合整個過程，提出了一個可以應用于電子政務系統(tǒng)的數(shù)據(jù)挖掘應用框架。
　　(4)最后通過實