新型频繁项集快速挖掘模式树的方法摘要：在FP_growth算法中，FP_tree及条件FP_tree的构造和遍历占了算法绝大部分的时间，为了能减少这方面的时间，提出了一种新型快速的方法――改进的层次频繁模式树（inprovedhierarchyFP_tree，IHFP_tree）。该方法采用首先对数据库扫描一遍，产生每个项的等价类；然后去掉不频繁项，对等价类进行重新改写；最后再创建FP_tree??。引入层次频繁模式的概念,在挖掘过程中大大提高了算法的时空效率。与其他频繁模式挖掘的常用算法进行了时间复杂度和空间复杂度的比较，实验表明，IHFP_tree的挖掘速度比FP_tree方法要快得多。关键词：FP_tree；ＩHFP_tree；频繁模式；等价类：TP301.6文献标志码：A：1001-3695(2008)08-2325-03ResearchonnewminingalgorithmoffrequentitemsetWANG激ng-hong??1,LIULi-na??2,GENGZong-ke??1(1.CollgegofInformationTechnology,HebeiNormalUniversity,Shi激azhuang050091,China;2.HebeiAgriculturalUniversity,QinhuangdaoHebei066004,China)Abstract:InFP-growthalgorithm,itcostsmostofthetimeinconstructingandtraversingtheFP-treeandconditionalFP-tree.InordertoconstructingtheFP_treeefficiently,thispaperproposedanewfastalgorithmcalledinprovedhierarchyFP_tree(abbreviateIHFP_tree).Thealgorithmfirstlyscanedthedatabaseonlyonceforgeneratingequivalenceclassesofeachitem.Thendeletedthenon-frequentitemsandrewrotetheequivalenceclassesofthefrequentitems,andthenconstructedtheIHFP_tree??.Keywords：FP_tree;IHFP_tree;frequentpattern;equivalenceclass频繁模式挖掘是关联规则、时序模式挖掘应用中的关键技术和步骤。以往大多数研究采用Apriori算法[1]来挖掘频繁模式。Apriori算法利用generate-and-test方法产生和检测候选项集，在挖掘过程中产生了大量的候选项集,并且需要反复扫描数据库,从而严重影响了的效率。后来的一些基于Apriori的算法[2]虽然作了一些改进，如GSP[3]、PSP[4]，但仍然没有解决产生大量候选项集的问题。为此，Han激a-wei等人提出了一种不产生候选项集的FP-growth[5]算法，用一个压缩的树FP_tree来存储频繁一项集，并且只需要扫描数据库两次，大大提高了关联规则挖掘速度。实验分析表明，FP-growth算法比Apriori等算法快一个数量级，如FreeSpan[6]、PrefixSpan[7]、FP_growth。但当数据库数量太大和支持度阈值很小时，找出所有的频繁模式是很浪费时间的，所以为了解决频繁模式中的冗余问题，提出了有关挖掘最大频繁模式[8]和闭频繁模式[9]的算法。这些算法都是基于FP_tree的，创建FP_tree需要扫描两遍数据库，这样大大浪费了时间。1频繁模式的定义设??I={i??1，i??2，…，i??m}为数据项集合，即项集；Ｄ为与任务相关的数据集合，即交易数据库。其中的每项交易Ｔ??是一个数据项子集，??T??I??，每个交易均包含一个识别编号TID。??A??为一个数据项集合，??Ｋ??-项集是包含??k??个数据项的项集，如集合｛computer,finanicial_management_software｝为一个２-项集。一个项集的出现频率就是整个交易数据集??Ｄ??中包含该项集的交易记录数，称为该项集的支持度（supportcount）。对于一个项集??A??的出现频率大于最小支持度阈值乘以交易记录集Ｄ中的记录数，则称该项集满足最小支持度阈值；如果项集A的支持度大于等于用户给定的阈值min_sup，即满足最小支持阈值的项集为频繁??k??-项集(frequentitemset，ＦＩ)，或称为频繁模式。2FP_tree和基于FP_tree的算法FP_tree这种压缩的数据结构大大提高了挖掘速度，主要原因在于不用产生大量的候选项集。FP_tree的建立需要扫描两遍数据库，与Apriori算法相比，性能大大提高。1)FP_tree的构建过程input:数据库DB和最小支持度min_supoutput:FP_treemethord:a)扫描数据库DB，记录项集??F??和它们的支持度，并按照支持度降低的顺序排序放到集合??L??中。b)创建FP_tree的根节点??T??,且??T??=null。对于DB中的每个事务做以下操作，根据??L??集合中项的顺序排列频繁项，然后调用函数insert_tree??([p|P],T)??。c)insert_tree(??[p|P],T??){if??T??...