FPGrowth關聯算法
前言：本站為你精心整理了FPGrowth關聯算法范文，希望能為你的創作提供參考價值，我們的客服老師可以幫助你提供個性化的參考范文，歡迎咨詢。
摘要關聯規則挖掘用于從大量數據中揭示項集之間的有趣關聯或相關聯系，是數據挖掘的一項重要研究內容。本文首先對FP-Growth算法進行分析，然后運用該算法分析聚類結果中的學生簇與該簇學生所具有因素的關聯關系，實踐證明了該算法具有較強的實用性。
關鍵詞數據挖掘；關聯分析；頻繁模式；FP-Tree
1引言
關聯規則(AssociationRules)挖掘是數據挖掘研究領域的一個重要研究方向，它由美國IBMAlmadenResearchCenter的RakeshA-Grawal等人于1993年首先提出，是描述數據庫中數據項之間存在的一些潛在關系的規則。
2關聯分析概念
設I={I1，I2，…，Im}是項的集合，D={T1，T2，…，Tn}是一個事務數據庫，其中每個事務T是項的集合，使得TI。每個事務有一個標識符，稱為TID。如果I的一個子集X滿足XT，則稱事務T包含項目集X。一個關聯規則就是形如X=Y的蘊涵式，XI、YI、X∩Y=。
規則XY在交易數據庫中的支持度(support)就是交易集中包含X和Y的交易數與所有交易數之比，記為support(XY)，即support(XY)=┃{T：X∪YT，TD}┃/┃D┃。
規則X=Y在交易數據庫中的置信度(confidence)是指包含X和Y的交易數與包含X的交易數之比，記為confidence(X=Y)，即confidence(X=Y)=┃{T：X∪YT，T∈D}┃/┃{T：XT，T∈D}┃。
支持度和置信度是描述關聯規則的兩個重要概念，前者用于衡量關聯規則在整個數據集中的統計重要性，后者用于衡量關聯規則的可信程度。一般來說，只有支持率和置信度均較高的關聯規則才可能是用戶感興趣、有用的關聯規則。
關聯規則的挖掘是一個兩步的過程：
(1)找出所有的頻繁項集：根據定義，這些項集出現的頻繁性至少等于預定義的最小支持度計數。
(2)由頻繁項集產生強關聯規則：根據定義，這些規則必須滿足最小支持度和最小置信度。
在以上兩個步驟中，第二步較容易，挖掘關聯規則的總體性能由第一步決定。
3FP-Growth關聯算法分析
針對經典關聯Apriori算法的固有缺陷，產生了候選挖掘頻繁項集的方法—FP-Growth算法。FP-Growth算法采用分而治之的策略，在經過第一遍掃描之后，把數據庫中的頻繁項集壓縮到一棵頻繁模式樹(FP-Tree)，同時依然保留其中的關聯信息，隨后再將FP-Tree分化成一些條件數據庫，每個條件數據關聯一個頻繁項，然后再分別對這些條件庫進行挖掘。FP-Growth算法將發現長頻繁模式的問題轉換為遞歸地發現一些短模式，然后連接后綴。它使用最不頻繁的項作為后綴，提供了好的選擇性。FP-Growth算法核心思想如下所示：
輸入：事務數據庫D；最小支持度閾值min_sup。
輸出：頻繁模式的完全集。
方法：
(1)構造FP-Tree。
①掃描事務數據庫D一次。收集頻繁項的集合F和它們的支持度。對F按支持度降序排序，結果為頻繁項表L。
②創建FP-Tree的根節點，以“NULL”標記它。對于D中每個事務Trans，執行：選擇Trans的頻繁項，并按照L中的次序排序。設排序后的頻繁項表為[p|P]，其中p是第一個元素，而P是剩余元素的表。調用insert_tree([p|P]，T)。該過程執行過程如下：如果T有子女N使得N.item-name=p.item-name，則N的計數增加1，否則創建一個新節點N，將其計數設置為1，鏈接到它的父節點T，并且通過節點鏈結構將其鏈接到具有相同item-name的節點。如果P非空，遞歸地調用insert_tree(P，N)。
(2)通過調用FP-Growth(FP-Tree，null)實現FP-Tree的挖掘。該過程實現如下：
ProcedureFP-Growth(Tree，α)
①ifTree含單個路徑Pthen
②for路徑P中節點的每個組合(記作β)
③產生模式β∪α，其支持度support=β中節點的最小支持度；
④elseforeachαi在Tree的頭部{
⑤產生一個模式β=αi∪α，其支持度support=αi.support；
⑥構造β的條件模式基，然后構造β的條件FP-Treeβ；
⑦ifTreeβ≠then
⑧調用FP-Growth(Treeβ，β)；}
對FP-Tree方法的性能研究表明：對于挖掘長和短的頻繁模式，它都是有效和可伸縮的，并且比Apriori方法快了1個數量級。
4應用實現
本文主要是將FP-Growth算法應用到我校學生成績數據庫中，在學生成績聚類的基礎上對學生成績的聚類簇與學生的內外部因素進行關聯分析。
4.1關聯分析目標
目前我校面對的教務處學生成績數據庫是一個多維的關系數據庫，我們急切需要從這些海量數據中發現潛在的有用信息來幫助教學部門掌握更多的學生信息。基于此，根據學生的成績信息對學生聚類，這些聚類信息反映了學生學習成績的升降起伏等學習情況，結合學生的聚類信息與學生因素調查表信息，采用關聯挖掘技術分析每一類學生的學生成績與其內外部因素間的關聯信息，進而分析得到影響學生學習的因素。4.2算法實現
定義頻繁節點結構，用以構造頻繁一次項的降序排列
typedefstructItemCode//SortItem
{
intCount；//頻繁度
intPosition；//排序位置
ItemCode*Next；//下一個節點的地址
CStringData；//節點值
}ItemCode；
ItemCode*GetItem(CStringTableName，intSupport，intNumber，intCluNum)；//由數據庫得到未排序頻繁一項集節點鏈，并返回首節點；
voidGetSortItem(ItemCode*pHeadItem)；//對頻繁一項集排序；
voidCreateFPTree(CStringTableName，CTreeCtrl&TempTree，CTreeCtrl&TreeCopy，boolSort，intNumber，intCluNum)；//按照頻繁項排序建立FP-Tree；
voidGetFPItem(CTreeCtrl&TempTree，CListBox&LBox，intSupport，intNumber，intCluNum)；//按Support的支持度對TempTree的FP-Tree進行關聯分析，得到頻繁項顯示在LBox；
voidSaveResultToDB()；//保存頻繁項集結果到數據庫；
voidComputeAssociate(intNumber，intCluNum)；//計算關聯結果的相關分析值；
voidShowInChart(CActiveFrmChart&Chart，intNumber，intCluNum，intIndex)；//將挖掘結果顯示在Chart中；
4.3挖掘結果
為了深入了解學生所處的內外部因素對學生成績的影響，將分別對每個簇的學生所處的內外部因素進行關聯挖掘，以獲取每個簇學生所處內外部因素間的關聯關系，分別對每個簇學生的內外部因素采用FP-Growth改進算法進行關聯挖掘，因為支持度計數是與問題域相關的，用戶可選擇不同的支持度計數實驗，我們在這里支持度計數選取為5。
部分簇構造FP-Tree如圖1所示，因篇幅有限，只列舉有代表意義的關聯項。
圖1生成的FP-Tree(灰色是頻繁項)
5結束語
對該算法的研究和應用可以看出算法具有很強的實用性。本文對關聯挖掘中支持度、置信度的選擇沒有進行深入的研究，因為對于一組給定的樣本，由于缺乏經驗或具體的問題域不同等其它原因導致事先不能合理地對聚類數目K、支持度、置信度的取值，這是一個比較棘手的問題，目前關于這方面研究的資料文獻較少，因此將此問題作為下一步研究的方向具有重要的現實意義。
參考文獻
[1][加]JiaweiHanMichelineKamber，范明，孟小峰等譯.數據挖掘概念與技術[M].北京：機械工業出版社，2001.
[2]顏躍進，李舟軍，陳火旺.基于FP-Tree有效挖掘最大頻繁項集[J].軟件學報，2005，16(2)：215-222.
[3]易彤，徐寶文，吳方君.一種基于FP樹的挖掘關聯規則的增量更新算法[J]計算機學報2004.5
[4]胡向前，基于FP-Tree的多層關聯規則挖掘算法研究[D]重慶大學碩士學位論文2005.5
