信息技術(shù)與信息化研究與探討FP-gr owth算法的優(yōu)化Optimization of FP-growth Algorithm閆越’姜昌金YAN Yue JIANG CHang-jin摘要FP-growth算法是關(guān)聯(lián)規(guī)則挖掘中效率較高的算法，以自底向.上方式探索樹(shù)，由PP樹(shù)產(chǎn)生頻繁項(xiàng)集。本文針對(duì)PP樹(shù)構(gòu)造過(guò)程中需多次遍歷頻繁項(xiàng)列表L的缺點(diǎn)，提出了一種基于散列表的改進(jìn)算法，實(shí)現(xiàn)了項(xiàng)名稱關(guān)鍵字到存儲(chǔ)地址的映射，進(jìn)而實(shí)現(xiàn)了項(xiàng)名稱關(guān)鍵字到其支持度計(jì)數(shù)的映射。在查找某項(xiàng)的支持度計(jì)數(shù)時(shí)，只需給出其名稱關(guān)鍵字，無(wú)需從頭遍歷頻繁項(xiàng)列表L，時(shí)間復(fù)雜度由0(n)提高到0(1)。實(shí)驗(yàn)結(jié)果表明，改進(jìn)算法的性能優(yōu)于原算法，節(jié)省了遍歷時(shí)間，提高了挖掘效率。關(guān)鍵詞數(shù)據(jù)挖掘頻繁項(xiàng)列表L FP-growth 散列表AbstractFP-growth is one of the most eficient algorithm among all the association rule algorithms.It is akind of algorithms that explores the FP-tree by a bottom-up way,then it generates frequent items by mining the FP-tree.This article puts forward an optimizing algorithm which is based on hash table against the defects during the process ofFP-tree consruction,because it usually traverses the frequent item table L time and time again.The new algorithm hasachieved a mapping of a key name to the storage address,thus it also achieved a mapping of a key name to its supportingnumber.As a result, just give an item-key or item-name when you want to search the supporting number of an item.The hash function will help you to calculate the logical address according to the item-key you provided,you will obtainthe supporting number directlly according to the logical address.There is no point at all in traversing the frequent itemtable L.Obviously,time complexity of searching one supporting number of an item improves from O(n) to 0(1).Atlast,experimental results show that optimizing algorithm is indeed better than the original algorithm in terms of the :running time.It spends less time than the original one.It saves traversal time and improvs mining efficiency.Keywords Data mining Frequent item table L FP-growth Hash tabledoi: 10. 3969/j. issn. 1672 - 9528. 2013. 06.35關(guān)聯(lián)規(guī)則[n是數(shù)據(jù)挖掘的主要技術(shù)之一，也是針對(duì)上述缺點(diǎn)，本文提出了一種基于散列表4在無(wú)指導(dǎo)學(xué)習(xí)系統(tǒng)中挖掘本地模式的最普通形式，的改進(jìn)算法，實(shí)現(xiàn)了項(xiàng)名稱到存儲(chǔ)地址的映射，進(jìn)用于發(fā)現(xiàn)隱藏在大型數(shù)據(jù)集中的有意義的聯(lián)系。FP-而實(shí)現(xiàn)了項(xiàng)名稱到其支持度計(jì)數(shù)的映射。在查找某項(xiàng)growth算法1是關(guān)聯(lián)規(guī)則挖掘中效率較高的算法，的支持度計(jì)數(shù)時(shí)，只需給出項(xiàng)名稱，無(wú)需從第一項(xiàng)它以自底向上方式探索樹(shù)，由FP樹(shù)產(chǎn)生頻繁項(xiàng)集(2。遍歷頻繁項(xiàng)列表L，查找時(shí)間復(fù)雜度由0(n)提高到其實(shí)現(xiàn)過(guò)程分為三步::是掃描數(shù)據(jù)庫(kù)，得出頻繁0(1)。實(shí)驗(yàn)結(jié)果表明，改進(jìn)算法的性能優(yōu)于原算法，項(xiàng)列表L8，二是構(gòu)造FP樹(shù)，三是對(duì)FP樹(shù)進(jìn)行挖掘。節(jié)省了遍歷時(shí)間，提高了挖掘效率。在FP樹(shù)構(gòu)造過(guò)程中，確定某項(xiàng)是否為頻繁項(xiàng)以及查1 FP-growth算法找任一-頻繁項(xiàng)的支持度計(jì)數(shù)[3]時(shí)，均需從頻繁項(xiàng)列表L的第一項(xiàng)開(kāi)始遍歷，當(dāng)事務(wù)數(shù)據(jù)庫(kù)的項(xiàng)集很大時(shí)，1. 1基本思想會(huì)嚴(yán)重影響算法執(zhí)行效率。FP-growth中國(guó)煤化工掘頻繁項(xiàng)集東南大學(xué)自動(dòng)化學(xué)院江蘇南京210096的一個(gè)有效算注YHCN MH G時(shí)不存在產(chǎn)2013年第6期125研究與探討信息技術(shù)與信息化生候選集的繁瑣過(guò)程，而是采取分治策略[5。首先，1.2.2.2構(gòu)造 FP-tree5)將提供頻繁項(xiàng)的數(shù)據(jù)庫(kù)壓縮到一棵頻繁模式樹(shù)(FP創(chuàng)建FP樹(shù)的根節(jié)點(diǎn)，以“null”標(biāo)記它。對(duì)于樹(shù)) ,但仍保留項(xiàng)集關(guān)聯(lián)信息。然后，將壓縮后的數(shù)事務(wù)數(shù)據(jù)集中每個(gè)事務(wù)trans,設(shè)排序后頻繁項(xiàng)列表?yè)?jù)庫(kù)劃分成一組條件數(shù)據(jù)庫(kù)，每個(gè)條件數(shù)據(jù)庫(kù)關(guān)聯(lián)一(即表3中每條事務(wù))為[p|P],其中,p是第-一個(gè)元素，個(gè)頻繁項(xiàng)，并分別對(duì)每個(gè)條件數(shù)據(jù)庫(kù)進(jìn)行挖掘。而P是剩余元素的列表。對(duì)每個(gè)事務(wù)調(diào)用insert_1.2算法描述 .tree([p|P],T)，其中T為相對(duì)父節(jié)點(diǎn)。該過(guò)程執(zhí)1.2.1 掃描數(shù)據(jù)庫(kù)，得到頻繁項(xiàng)列表L .行情況如下:如果T有一個(gè)子女N，使得N. item-對(duì)事務(wù)數(shù)據(jù)集(格式見(jiàn)表1)進(jìn)行一次掃描，確name=p. item- name,則N的計(jì)數(shù)增加1;否則，創(chuàng)建定每個(gè)項(xiàng)的支持度計(jì)數(shù)。丟棄非頻繁項(xiàng)，將頻繁項(xiàng)按個(gè)新節(jié)點(diǎn)N,將其計(jì)數(shù)設(shè)置為1, 鏈接到它的父節(jié)支持度遞減排序[2。之所以這樣排序，是因?yàn)镕P樹(shù)點(diǎn)T，并通過(guò)節(jié)點(diǎn)鏈結(jié)構(gòu)將其鏈接到具有相同item-中的每-一個(gè)路徑也是依照此順序的1]name的節(jié)點(diǎn)。如果P非空，遞歸地調(diào)用insert_例如，對(duì)表1的事物數(shù)據(jù)集掃描，設(shè)最小支持度tree(P, N)。sup為2,得頻繁項(xiàng)列表L={(f:5)，(c:4)， (a:3)，1.2.3挖掘 FP- tree,得出頻繁項(xiàng)集(b:3)，(m:3) ，(p:2) },其存儲(chǔ)結(jié)構(gòu)如表2所示，其基本思想是，由長(zhǎng)度為1 的頻繁模式[5] (初始采用二維數(shù)組Arr[][]的存儲(chǔ)結(jié)構(gòu)，當(dāng)然也可以采用后綴模式)開(kāi)始，構(gòu)造它的條件模式基(一個(gè)子數(shù)據(jù)容器vector>的類(lèi)型。庫(kù)，由FP-tree中與后綴模式- -起 出現(xiàn)的前綴路徑集表1事物數(shù)據(jù)集組成)。構(gòu)造該初始后綴模式的條件FP-tree,并遞TID項(xiàng)集ID歸地在該樹(shù).上實(shí)現(xiàn)挖掘。模式增長(zhǎng)通過(guò)后綴模式與條01f,a,c，d，g，m件FP- tree產(chǎn)生的頻繁模式連接實(shí)現(xiàn)。)2b，a，c，f，1，m，003b, f，, h，2改進(jìn)算法)4，b, c，k，s，!05a,f,c，e,p，m，n2.1基本思想.根據(jù)_上述FP- growth算法工作原理，可知:如表2頻繁項(xiàng)列表L果要判定某項(xiàng)是否為頻繁項(xiàng)，或是要找出某個(gè)頻繁項(xiàng)邏輯地址35|的支持度計(jì)數(shù)，均需從頻繁項(xiàng)列表L的第一項(xiàng)開(kāi)始遍Arr[][0] (項(xiàng)f| ci歷，查找到與之匹配的項(xiàng)名稱(項(xiàng)關(guān)鍵字)，返回查ID)| Arr[][1] (sup |。找成功和相應(yīng)的支持度計(jì)數(shù)，否則返回查找失敗。無(wú)54計(jì)數(shù))論頻繁項(xiàng)列表L的存儲(chǔ)結(jié)構(gòu)是二維數(shù)組Arr[][D]的形式，還是容器vector>的形式，只1.2.2構(gòu)造FP-tree能進(jìn)行順序查找。當(dāng)頻繁項(xiàng)列表L的數(shù)據(jù)集增大時(shí)，1.2.2.1原事務(wù)數(shù)據(jù)集的優(yōu)化第二次掃描事務(wù)數(shù)據(jù)集，對(duì)事務(wù)數(shù)據(jù)集中的每條查找某項(xiàng)的遍歷時(shí)間會(huì)隨之增加，嚴(yán)重影響算法執(zhí)行事務(wù)進(jìn)行優(yōu)化。首先丟掉L列表中未出現(xiàn)過(guò)的非頻繁項(xiàng)，然后將保留的頻繁項(xiàng)按照L列表中次序(即按遞本文提出的改進(jìn)算法基于散列表。設(shè)定一一個(gè)散列減支持度計(jì)數(shù))排序，得到優(yōu)化后事務(wù)數(shù)據(jù)集(如表函數(shù)h(k)，將項(xiàng)名稱k與存儲(chǔ)地址h(k)對(duì)應(yīng)起來(lái)，并將其支持度計(jì)數(shù)存儲(chǔ)于該地址，最終得到一個(gè)散3所示)。表3優(yōu)化后事務(wù)數(shù)據(jù)集列表。改進(jìn)算法實(shí)現(xiàn)了項(xiàng)名稱到存儲(chǔ)地址的映射，進(jìn)而實(shí)現(xiàn)了項(xiàng)名稱到其支持度計(jì)數(shù)的映射。在查找某項(xiàng)優(yōu)化后項(xiàng)集ID)1f，c，a,m的支持度計(jì)數(shù)時(shí)，只需給出項(xiàng)名稱k，通過(guò)散列函數(shù)02f，c，a,b，mh(k)可直接計(jì)算出其存儲(chǔ)地址，直接獲得其支持度.f, b計(jì)數(shù)，而無(wú)需中國(guó)煤化工，查找時(shí)間04，c，b，I)5f，c，a，m，p復(fù)雜度由0(n)MHCNMHG表L的存儲(chǔ)1262013年第6期信息技術(shù)與信息化研究與探討結(jié)構(gòu)為brr[h(k)] (見(jiàn)表4)。列表L中未出現(xiàn)的非頻繁項(xiàng)。例如，表1中TID編號(hào)表4改進(jìn)后頻繁項(xiàng)列表L為01的事務(wù)中，判定項(xiàng)d是否為頻繁項(xiàng)，原算法中散列 |h(a)|h(b |h(e)| h(f)| |h(m)h(p)需要從表2的第一項(xiàng)開(kāi)始遍歷arr[][0]中存儲(chǔ)的項(xiàng)地址=0|)=1|=2 .=5 .=12 =15| ””名稱，直至最后沒(méi)有找到與之匹配的項(xiàng)名稱，才返回sup查找失敗。而改進(jìn)算法中，只需計(jì)算h(d)=4,由表4計(jì)數(shù)| 3| 3|40|5|o| .3| 02| 0中brr[4]=0可直接返回查找失敗。本例中,項(xiàng)名稱以26個(gè)小寫(xiě)英文字母表示，而每個(gè)(2)對(duì)已丟掉非頻繁項(xiàng)的每條事務(wù)，項(xiàng)集按L英文字母的ASCII碼是唯一-的， 所以可設(shè)置- - 個(gè)長(zhǎng)度為表中順序排序。例如，表1中TID編號(hào)為03的事務(wù)中,26的散列表brr[26];且因a的ASCII碼是97,散列函對(duì)只剩下頻繁項(xiàng)b、f的事務(wù)排序，要判定b和f的數(shù)可定義為h(k)=(int)k-97。如: 對(duì)于項(xiàng)m, h(m)=(int)先后順序，原算法中需要從表2的第一項(xiàng)開(kāi)始， 遍歷至第四項(xiàng)，方可確定項(xiàng)f在項(xiàng)b之前。而改進(jìn)算法中，m-97=109- 97=12,brr[12]=3,故其支持度計(jì)數(shù)為3。當(dāng)然，散列表會(huì)因?yàn)轫?xiàng)和散列函數(shù)的不同定義法只需比較表4中brr[h[f]]和brr[h[b]]的大小，便出現(xiàn)沖突現(xiàn)象4，即對(duì)不同項(xiàng)名稱k1和k2,可能得可判定項(xiàng)f在項(xiàng)b之前。到同一散列地址h(k1)=h(k2)。對(duì)于這種現(xiàn)象可采用(3)當(dāng)對(duì)兩個(gè)支持度計(jì)數(shù)相等的項(xiàng)排序時(shí)。例如，表1中TID編號(hào)為02的事務(wù)中，b和a的支持度計(jì)開(kāi)放定址法4]、鏈接法(41等進(jìn)行優(yōu)化。例如，線性表A= (17, 75, 60, 43,54)，為了散列數(shù)均為3，無(wú)法確定其先后順序。原算法中需要再?gòu)拇鎯?chǔ)該線性表，選取散列函數(shù)h(k)=k%m,其中k為元表2的第一-項(xiàng)開(kāi)始遍歷至第四項(xiàng)，分別記錄下其邏輯素關(guān)鍵字，m要大于等于線性表長(zhǎng)度n, n為A的元地址2和3才能確定項(xiàng)a在項(xiàng)b之前。而改進(jìn)算法中素個(gè)數(shù)，此處為5，可取m為10。由此得出的散列地只需比較其散列函數(shù)值h(b)和h(a)的大小，便可判定項(xiàng)a在項(xiàng)b之前。址依次為(7,5, 0,3,4)，其存儲(chǔ)映像如表5:表5線性表A的存儲(chǔ)結(jié)構(gòu)3實(shí)驗(yàn)及結(jié)果分析0|1|2|3|4|56|7|8..9|3.1算法測(cè)試地3.1.1測(cè)試環(huán)境西60||43|54|75驗(yàn)證改進(jìn)算法性能優(yōu)于原算法性能的測(cè)試環(huán)境:當(dāng)向該線性表插入元素25時(shí)，由散列函數(shù)操作系統(tǒng)WindowsXP，內(nèi)存2G，測(cè)試數(shù)據(jù)庫(kù)采用h(25) =25%10=5知，其散列地址為5,但散列地址為5SQL Server 2005 中AdventureWorks示例數(shù)據(jù)。以的存儲(chǔ)單元已被元素75使用，25 無(wú)法存儲(chǔ)在此單元，Microsoft Visual Studio 2010 為開(kāi)發(fā)平臺(tái)，使用這便是沖突現(xiàn)象。為此，約定當(dāng)由h(k)計(jì)算得出的c++語(yǔ)言分別實(shí)現(xiàn)原算法和改進(jìn)算法，對(duì)測(cè)試數(shù)據(jù)進(jìn)散列地址已被使用時(shí)，以此地址的下一個(gè)地址為起始行挖掘。地址，依次向下查詢，當(dāng)查到第一個(gè)沒(méi)有存儲(chǔ)任何3.1.2具體實(shí)現(xiàn)元素的單元時(shí)停止，將元素存儲(chǔ)于此單元。所以，25AdventureWorks數(shù)據(jù)庫(kù)中，表Sales. Sales0rder應(yīng)該存儲(chǔ)在散列地址為6的單元。當(dāng)再向該線性表插-Detail的Sales0rderID和ProductID屬性分別記錄入元素55時(shí)，根據(jù)以上約定，55應(yīng)該存儲(chǔ)在散列地了每次購(gòu)物交易的商品號(hào)和數(shù)量,共121317條記錄，址為8的單元，以此類(lèi)推。因此，如何盡量避免沖突31465次交易，商品號(hào)為707-999。定義一個(gè)長(zhǎng)度為和沖突發(fā)生后如何解決是散列存儲(chǔ)的兩個(gè)關(guān)鍵問(wèn)題。300的散列表，散列函數(shù)為h(k)=ProductID-700。在2.2算法分析不同最小支持度下，原算法與改進(jìn)算法性能比較的測(cè)分析FP-growth工作原理中FP- tree的構(gòu)造過(guò)程，試數(shù)據(jù)如表6。對(duì)比頻繁項(xiàng)列表L的存儲(chǔ)結(jié)構(gòu)表2和表4可知，改進(jìn)表6測(cè)試數(shù)據(jù)算法效率的提高主要體現(xiàn)在以下三個(gè)方面。最小支持度%中國(guó)煤化工2(1)第二次掃描事物數(shù)據(jù)集時(shí)，丟掉了頻繁項(xiàng)FP-growthCN M H G252| 419運(yùn)行時(shí)間s2013年第6期127研究與探討信息技術(shù)與信息化改進(jìn)算法北京:清華大學(xué)出版社，2011. 167-175.運(yùn)行時(shí)間s320291274270|263|280236213 191| 207時(shí)間差s1222427961 212_[4] 徐孝凱.數(shù)據(jù)結(jié)構(gòu)實(shí)用教程(c/c++描述) [M].北京:清華大學(xué)出版社，1999. 264-270.時(shí)間差折線圖如下:[S]Jiawei Han， Micheline Kamber. 范明，孟小峰.數(shù)據(jù)挖掘概念與技術(shù)[M].北京:機(jī)械工時(shí)間差折線圖.50 r業(yè)出版社，2007. 157-159.200 t[作者簡(jiǎn)介]閆越， (1989-)， 女，碩士研究生,150 --.-研究方向:數(shù)據(jù) 挖掘。鹽100(收稿日期: 2013-09-04 )50 t(上接第105頁(yè))03217總裝配圖.最小支持度%總裝圖如圖7所示。圖1測(cè)試結(jié)果3.2結(jié)果分析測(cè)試結(jié)果表明，改進(jìn)算法性能優(yōu)于原算法性能，特別是最小支持度小于5%的范圍，這是因?yàn)殡S著最T小支持度的減小，頻繁項(xiàng)列表L中的項(xiàng)集增大。即頻圖7總裝圖繁項(xiàng)列表L中的項(xiàng)集越大時(shí)，改進(jìn)算法對(duì)原算法的優(yōu)化效果越明顯。由此可以推斷，在同一-最小支持度下，8結(jié)語(yǔ)數(shù)據(jù)記錄數(shù)越多，改進(jìn)算法的優(yōu)化效果也會(huì)越明顯。所以，改進(jìn)算法效率較高，更適合大數(shù)據(jù)集的挖掘。在流量積算儀的檢測(cè)中，使用這種探針式檢測(cè)裝置，會(huì)大大提高檢測(cè)效率和整機(jī)合格率，節(jié)省檢測(cè)時(shí).4結(jié)論間和相應(yīng)的資金，從而提高產(chǎn)品生產(chǎn)效率，創(chuàng)造更多本文提出的基于散列表的改進(jìn)算法，實(shí)現(xiàn)了項(xiàng)名的價(jià)值。稱到存儲(chǔ)地址的映射，進(jìn)而實(shí)現(xiàn)了項(xiàng)名稱到其支持度參考文獻(xiàn)計(jì)數(shù)的映射，從而改進(jìn)了FP-growth算法，使得某項(xiàng)[1]郭啟全，李莉，王翔. Autocad 2000 基礎(chǔ)教程的支持度計(jì)數(shù)查找時(shí)間復(fù)雜度由0(n)提高到0(1)。[M].北京:北京理工大學(xué)出版社, 2000, (1).在支持度要求越小、L列表所含項(xiàng)集越大時(shí)，該算法[2]曲世惠。電工作業(yè)[M].北京:氣象出版社，的效率提高越明顯，因而，改進(jìn)算法更適合大數(shù)據(jù)集2001, (1).的挖掘。[3]張學(xué)政。金屬工藝學(xué)[M]. 中央廣播電視大參考文獻(xiàn):學(xué),1996, (1)[4]濮良貴，紀(jì)名剛.機(jī)械設(shè)計(jì)[M]. 北京:高等1] 閃四清，陳茵，程雁. Mehmed Kantardzic. 數(shù)教育出版社, 2001, (7).據(jù)挖掘一概念、模型、方法和算法[M].北京:(收稿日期: 2013-04-06 )清華大學(xué)出版社，2003. 149-152.[2] Pang-Ning Tan, Michael Steinbach, VipinKumar.范明，范宏建.數(shù)據(jù)挖掘?qū)д揫M].北京:人民郵電出版社，2011. 223-228. .中國(guó)煤化工鄭巖.數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘原理及應(yīng)用[MMHCNMHG1282013年第6期