·146 智能系统学报 第4卷 模式树中即可 该树，和CFP相比，节省了大量的内存 4实验结果和性能分析 50r MCFP ■iCFP 40 old pcl=80%,new pct=60% 本节通过一系列实验来比较算法MCFP和 30 CFP由于在算法MCFP中每次只有一个条件树存 在内存中，和C℉P相比显然节省了大量的内存，所 20 以对2种算法不进行所消耗内存的比较，只从算法 的运行时间上进行比较 算法均用C++语言编写.运行环境 0.20.40.60.8 约束改变前后的比值 ntel Pentium IV24 Hz CRU,10GB内存，40GB硬盘. 实验数据都来自于文献【7]，所以很具有可比性.实 图8处理松约束性变化 验中所用的数据库包括10万个记录，每个事务大约 Fig 8 Relaxing change constraint 包含l0个项.数据库由BM Amadem Research 图7和图8给出了处理动态约束变化时的执行 Center产生.设最小支持度8为Q01%,这2种算法 时间，MCFP的效率同样高于CFP当约束变化时， 的运行时间如图6、图7和图8所示 MCFP只需从最大模式中来找满足新的约束的频繁 125 模式.另外，MCFP能挖掘到最大模式，当只需要挖 口MCFP ■iCFP 100 掘最大模式时，MCFP算法就节省了更多的时间.因 此，MCFP算法的性能高于CFP 75 50 5结束语 提出了一种新的交互式约束的频繁模式挖掘算 法，该算法不仅能挖掘最大频繁模式，而且在此基础 20 406080 00 选中项日/% 上能找到所有的满足约束的支持度精确的频繁模 图6运行时间比较 式.该算法克服了以前的最大模式挖掘算法中不能 Fig 6 Comparison of running tmes 精确知道由最大模式产生的所有频繁模式的支持度 50r 问题.另外，该算法采用新的构建FP-tree的方法，避 ▣MCFP ■iCFP 40 old pcl=80%,new pct=60% 免了在约束变化时重新构建FP-tree 30 参考文献： 20 1 ]A GRAWAL R,SR IKANT R Fast algorithms orm ining as- sociaton rules[C]//Proceedings 20 th Intemational Confer ence on VLDB.Morgan Kaufnann,1994:487-499 0.20.40.60.8 1.0 [2颜跃进，李舟军，陈火旺.频繁项集挖掘算法[J)计算 约束改变前后的比值 机科学，2004,31(3)：112-114 图7处理紧约束性变化 YAN Yuejin,LI Zhoujun,CHEN Huowang Frequent item Fig 7 Tighting constraint change sets m ining algorithms [J ]Computer Science,2004,31 (3):112-114 图6表明MCFP比CFP算法更有效.第一， [3颜跃进，李舟军，陈火旺.基于FP-Tee有效挖掘最大 MCFP在建立FP-tee时只需扫描遍数据库，而CFP 频繁项集[J]软件学报，2005,16(2)：215-222 需扫描2遍，1/O代价付出大.第二，在挖掘满足约 YAN Yuejin,LI Zhoujun,CHEN Huowang Efficiently 束的频繁项时，CFP需要不断地建立条件树，并且 m ining ofmaxmal frequent item sets based on FP-Tree[J. 不释放，这样占用了大量的内存，然而，MCFP只需 Joumal of Sofware,2005,16(2):215-22 建立一次每个项的条件树，并且在挖掘完成后释放 [4 ]AGRAWAL R,M IEL NSKI T,SWAMIA M ining associ 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net模式树中即可. 4 实验结果和性能分析 本节通过一系列实验来比较算法 MCFP 和 iCFP. 由于在算法 MCFP中每次只有一个条件树存 在内存中 ,和 iCFP相比显然节省了大量的内存 ,所 以对 2种算法不进行所消耗内存的比较 ,只从算法 的运行时间上进行比较. 算 法 均 用 C + + 语 言 编 写. 运 行 环 境: Intel Pentium Ⅳ2. 4GHz CPU, 1. 0GB内存 , 40GB 硬盘. 实验数据都来自于文献 [ 7 ],所以很具有可比性. 实 验中所用的数据库包括 10万个记录 ,每个事务大约 包含 10 个项. 数据库由 IBM A lmadern Research Center产生. 设最小支持度 δ为 0. 01% ,这 2种算法 的运行时间如图 6、图 7和图 8所示. 图 6 运行时间比较 Fig. 6 Comparison of running times 图 7 处理紧约束性变化 Fig. 7 Tighting constraint change 图 6 表明 MCFP比 iCFP算法更有效. 第一 , MCFP在建立 FP2tree时只需扫描遍数据库 ,而 iCFP 需扫描 2遍 , I/O代价付出大. 第二 ,在挖掘满足约 束的频繁项时 , iCFP需要不断地建立条件树 ,并且 不释放 ,这样占用了大量的内存 ,然而 ,MCFP只需 建立一次每个项的条件树 ,并且在挖掘完成后释放 该树 ,和 iCFP相比 ,节省了大量的内存. 图 8 处理松约束性变化 Fig. 8 Relaxing change constraint 图 7和图 8给出了处理动态约束变化时的执行 时间 ,MCFP的效率同样高于 iCFP. 当约束变化时 , MCFP只需从最大模式中来找满足新的约束的频繁 模式. 另外 ,MCFP能挖掘到最大模式 ,当只需要挖 掘最大模式时 ,MCFP算法就节省了更多的时间. 因 此 ,MCFP算法的性能高于 iCFP. 5 结束语 提出了一种新的交互式约束的频繁模式挖掘算 法 ,该算法不仅能挖掘最大频繁模式 ,而且在此基础 上能找到所有的满足约束的支持度精确的频繁模 式. 该算法克服了以前的最大模式挖掘算法中不能 精确知道由最大模式产生的所有频繁模式的支持度 问题. 另外 ,该算法采用新的构建 FP2tree的方法 ,避 免了在约束变化时重新构建 FP2tree. 参考文献 : [ 1 ]AGRAWAL R, SR IKANT R. Fast algorithm s formining as2 sociation rules[ C ] / /Proceedings 20 th International Confer2 ence on VLDB. Morgan Kaufmann, 1994: 4872499. [ 2 ]颜跃进 , 李舟军 , 陈火旺. 频繁项集挖掘算法 [J ]. 计算 机科学 , 2004, 31 (3) : 1122114. YAN Yuejin, L I Zhoujun, CHEN Huowang. Frequent item sets m ining algorithm s [ J ]. Computer Science, 2004, 31 (3) : 1122114. [ 3 ]颜跃进 , 李舟军 , 陈火旺. 基于 FP2Tree有效挖掘最大 频繁项集 [J ]. 软件学报 , 2005, 16 (2) : 2152222. YAN Yuejin, L I Zhoujun, CHEN Huowang. Efficiently m ining of maximal frequent item sets based on FP2Tree[J ]. Journal of Software, 2005, 16 (2) : 215222. [ 4 ]AGRAWAL R, IM IEL INSKI T, SWAM IA. M ining associ2 ·146· 智 能 系 统 学 报 第 4卷