基于電子政務(wù)的改進(jìn)FP_Growth算法研究和應(yīng)用.pdf

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

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

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

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