FP-growth算法的優(yōu)化

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