FP-growth算法的优化

信息技术与信息化研究与探讨FP-gr owth算法的优化Optimization of FP-growth Algorithm闫越’姜昌金YAN Yue JIANG CHang-jin摘要FP-growth算法是关联规则挖掘中效率较高的算法，以自底向.上方式探索树，由PP树产生频繁项集。本文针对PP树构造过程中需多次遍历频繁项列表L的缺点，提出了一种基于散列表的改进算法，实现了项名称关键字到存储地址的映射，进而实现了项名称关键字到其支持度计数的映射。在查找某项的支持度计数时，只需给出其名称关键字，无需从头遍历频繁项列表L，时间复杂度由0(n)提高到0(1)。实验结果表明，改进算法的性能优于原算法，节省了遍历时间，提高了挖掘效率。关键词数据挖掘频繁项列表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关联规则[n是数据挖掘的主要技术之一，也是针对上述缺点，本文提出了一种基于散列表4在无指导学习系统中挖掘本地模式的最普通形式，的改进算法，实现了项名称到存储地址的映射，进用于发现隐藏在大型数据集中的有意义的联系。FP-而实现了项名称到其支持度计数的映射。在查找某项growth算法1是关联规则挖掘中效率较高的算法，的支持度计数时，只需给出项名称，无需从第一项它以自底向上方式探索树，由FP树产生频繁项集(2。遍历频繁项列表L，查找时间复杂度由0(n)提高到其实现过程分为三步::是扫描数据库，得出频繁0(1)。实验结果表明，改进算法的性能优于原算法，项列表L8，二是构造FP树，三是对FP树进行挖掘。节省了遍历时间，提高了挖掘效率。在FP树构造过程中，确定某项是否为频繁项以及查1 FP-growth算法找任一-频繁项的支持度计数[3]时，均需从频繁项列表L的第一项开始遍历，当事务数据库的项集很大时，1. 1基本思想会严重影响算法执行效率。FP-growth中国煤化工掘频繁项集东南大学自动化学院江苏南京210096的一个有效算注YHCN MH G时不存在产2013年第6期125研究与探讨信息技术与信息化生候选集的繁琐过程，而是采取分治策略[5。首先，1.2.2.2构造 FP-tree5)将提供频繁项的数据库压缩到一棵频繁模式树(FP创建FP树的根节点，以“null”标记它。对于树) ,但仍保留项集关联信息。然后，将压缩后的数事务数据集中每个事务trans,设排序后频繁项列表据库划分成一组条件数据库，每个条件数据库关联一(即表3中每条事务)为[p|P],其中,p是第-一个元素，个频繁项，并分别对每个条件数据库进行挖掘。而P是剩余元素的列表。对每个事务调用insert_1.2算法描述 .tree([p|P],T)，其中T为相对父节点。该过程执1.2.1 扫描数据库，得到频繁项列表L .行情况如下:如果T有一个子女N，使得N. item-对事务数据集(格式见表1)进行一次扫描，确name=p. item- name,则N的计数增加1;否则，创建定每个项的支持度计数。丢弃非频繁项，将频繁项按个新节点N,将其计数设置为1, 链接到它的父节支持度递减排序[2。之所以这样排序，是因为FP树点T，并通过节点链结构将其链接到具有相同item-中的每-一个路径也是依照此顺序的1]name的节点。如果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所示，其基本思想是，由长度为1 的频繁模式[5] (初始采用二维数组Arr[][]的存储结构，当然也可以采用后缀模式)开始，构造它的条件模式基(一个子数据容器vector>的类型。库，由FP-tree中与后缀模式- -起 出现的前缀路径集表1事物数据集组成)。构造该初始后缀模式的条件FP-tree,并递TID项集ID归地在该树.上实现挖掘。模式增长通过后缀模式与条01f,a,c，d，g，m件FP- tree产生的频繁模式连接实现。)2b，a，c，f，1，m，003b, f，, h，2改进算法)4，b, c，k，s，!05a,f,c，e,p，m，n2.1基本思想.根据_上述FP- growth算法工作原理，可知:如表2频繁项列表L果要判定某项是否为频繁项，或是要找出某个频繁项逻辑地址35|的支持度计数，均需从频繁项列表L的第一项开始遍Arr[][0] (项f| ci历，查找到与之匹配的项名称(项关键字)，返回查ID)| Arr[][1] (sup |。找成功和相应的支持度计数，否则返回查找失败。无54计数)论频繁项列表L的存储结构是二维数组Arr[][D]的形式，还是容器vector>的形式，只1.2.2构造FP-tree能进行顺序查找。当频繁项列表L的数据集增大时，1.2.2.1原事务数据集的优化第二次扫描事务数据集，对事务数据集中的每条查找某项的遍历时间会随之增加，严重影响算法执行事务进行优化。首先丢掉L列表中未出现过的非频繁项，然后将保留的频繁项按照L列表中次序(即按递本文提出的改进算法基于散列表。设定一一个散列减支持度计数)排序，得到优化后事务数据集(如表函数h(k)，将项名称k与存储地址h(k)对应起来，并将其支持度计数存储于该地址，最终得到一个散3所示)。表3优化后事务数据集列表。改进算法实现了项名称到存储地址的映射，进而实现了项名称到其支持度计数的映射。在查找某项优化后项集ID)1f，c，a,m的支持度计数时，只需给出项名称k，通过散列函数02f，c，a,b，mh(k)可直接计算出其存储地址，直接获得其支持度.f, b计数，而无需中国煤化工，查找时间04，c，b，I)5f，c，a，m，p复杂度由0(n)MHCNMHG表L的存储1262013年第6期信息技术与信息化研究与探讨结构为brr[h(k)] (见表4)。列表L中未出现的非频繁项。例如，表1中TID编号表4改进后频繁项列表L为01的事务中，判定项d是否为频繁项，原算法中散列 |h(a)|h(b |h(e)| h(f)| |h(m)h(p)需要从表2的第一项开始遍历arr[][0]中存储的项地址=0|)=1|=2 .=5 .=12 =15| ””名称，直至最后没有找到与之匹配的项名称，才返回sup查找失败。而改进算法中，只需计算h(d)=4,由表4计数| 3| 3|40|5|o| .3| 02| 0中brr[4]=0可直接返回查找失败。本例中,项名称以26个小写英文字母表示，而每个(2)对已丢掉非频繁项的每条事务，项集按L英文字母的ASCII码是唯一-的， 所以可设置- - 个长度为表中顺序排序。例如，表1中TID编号为03的事务中,26的散列表brr[26];且因a的ASCII码是97,散列函对只剩下频繁项b、f的事务排序，要判定b和f的数可定义为h(k)=(int)k-97。如: 对于项m, h(m)=(int)先后顺序，原算法中需要从表2的第一项开始， 遍历至第四项，方可确定项f在项b之前。而改进算法中，m-97=109- 97=12,brr[12]=3,故其支持度计数为3。当然，散列表会因为项和散列函数的不同定义法只需比较表4中brr[h[f]]和brr[h[b]]的大小，便出现冲突现象4，即对不同项名称k1和k2,可能得可判定项f在项b之前。到同一散列地址h(k1)=h(k2)。对于这种现象可采用(3)当对两个支持度计数相等的项排序时。例如，表1中TID编号为02的事务中，b和a的支持度计开放定址法4]、链接法(41等进行优化。例如，线性表A= (17, 75, 60, 43,54)，为了散列数均为3，无法确定其先后顺序。原算法中需要再从存储该线性表，选取散列函数h(k)=k%m,其中k为元表2的第一-项开始遍历至第四项，分别记录下其逻辑素关键字，m要大于等于线性表长度n, n为A的元地址2和3才能确定项a在项b之前。而改进算法中素个数，此处为5，可取m为10。由此得出的散列地只需比较其散列函数值h(b)和h(a)的大小，便可判定项a在项b之前。址依次为(7,5, 0,3,4)，其存储映像如表5:表5线性表A的存储结构3实验及结果分析0|1|2|3|4|56|7|8..9|3.1算法测试地3.1.1测试环境西60||43|54|75验证改进算法性能优于原算法性能的测试环境:当向该线性表插入元素25时，由散列函数操作系统WindowsXP，内存2G，测试数据库采用h(25) =25%10=5知，其散列地址为5,但散列地址为5SQL Server 2005 中AdventureWorks示例数据。以的存储单元已被元素75使用，25 无法存储在此单元，Microsoft Visual Studio 2010 为开发平台，使用这便是冲突现象。为此，约定当由h(k)计算得出的c++语言分别实现原算法和改进算法，对测试数据进散列地址已被使用时，以此地址的下一个地址为起始行挖掘。地址，依次向下查询，当查到第一个没有存储任何3.1.2具体实现元素的单元时停止，将元素存储于此单元。所以，25AdventureWorks数据库中，表Sales. Sales0rder应该存储在散列地址为6的单元。当再向该线性表插-Detail的Sales0rderID和ProductID属性分别记录入元素55时，根据以上约定，55应该存储在散列地了每次购物交易的商品号和数量,共121317条记录，址为8的单元，以此类推。因此，如何尽量避免冲突31465次交易，商品号为707-999。定义一个长度为和冲突发生后如何解决是散列存储的两个关键问题。300的散列表，散列函数为h(k)=ProductID-700。在2.2算法分析不同最小支持度下，原算法与改进算法性能比较的测分析FP-growth工作原理中FP- tree的构造过程，试数据如表6。对比频繁项列表L的存储结构表2和表4可知，改进表6测试数据算法效率的提高主要体现在以下三个方面。最小支持度%中国煤化工2(1)第二次扫描事物数据集时，丟掉了频繁项FP-growthCN M H G252| 419运行时间s2013年第6期127研究与探讨信息技术与信息化改进算法北京:清华大学出版社，2011. 167-175.运行时间s320291274270|263|280236213 191| 207时间差s1222427961 212_[4] 徐孝凯.数据结构实用教程(c/c++描述) [M].北京:清华大学出版社，1999. 264-270.时间差折线图如下:[S]Jiawei Han， Micheline Kamber. 范明，孟小峰.数据挖掘概念与技术[M].北京:机械工时间差折线图.50 r业出版社，2007. 157-159.200 t[作者简介]闫越， (1989-)， 女，硕士研究生,150 --.-研究方向:数据 挖掘。盐100(收稿日期: 2013-09-04 )50 t(上接第105页)03217总装配图.最小支持度%总装图如图7所示。图1测试结果3.2结果分析测试结果表明，改进算法性能优于原算法性能，特别是最小支持度小于5%的范围，这是因为随着最T小支持度的减小，频繁项列表L中的项集增大。即频图7总装图繁项列表L中的项集越大时，改进算法对原算法的优化效果越明显。由此可以推断，在同一-最小支持度下，8结语数据记录数越多，改进算法的优化效果也会越明显。所以，改进算法效率较高，更适合大数据集的挖掘。在流量积算仪的检测中，使用这种探针式检测装置，会大大提高检测效率和整机合格率，节省检测时.4结论间和相应的资金，从而提高产品生产效率，创造更多本文提出的基于散列表的改进算法，实现了项名的价值。称到存储地址的映射，进而实现了项名称到其支持度参考文献计数的映射，从而改进了FP-growth算法，使得某项[1]郭启全，李莉，王翔. Autocad 2000 基础教程的支持度计数查找时间复杂度由0(n)提高到0(1)。[M].北京:北京理工大学出版社, 2000, (1).在支持度要求越小、L列表所含项集越大时，该算法[2]曲世惠。电工作业[M].北京:气象出版社，的效率提高越明显，因而，改进算法更适合大数据集2001, (1).的挖掘。[3]张学政。金属工艺学[M]. 中央广播电视大参考文献:学,1996, (1)[4]濮良贵，纪名刚.机械设计[M]. 北京:高等1] 闪四清，陈茵，程雁. Mehmed Kantardzic. 数教育出版社, 2001, (7).据挖掘一概念、模型、方法和算法[M].北京:(收稿日期: 2013-04-06 )清华大学出版社，2003. 149-152.[2] Pang-Ning Tan, Michael Steinbach, VipinKumar.范明，范宏建.数据挖掘导论[M].北京:人民邮电出版社，2011. 223-228. .中国煤化工郑岩.数据仓库与数据挖掘原理及应用[MMHCNMHG1282013年第6期