减少候选项集的数据流高效用项集挖掘算法

《减少候选项集的数据流高效用项集挖掘算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第３４卷第１１期计算机应用研究Ｖｏｌ．３４Ｎｏ．１１２０１７年１１月ＡｐｐｌｉｃａｔｉｏｎＲｅｓｅａｒｃｈｏｆＣｏｍｐｕｔｅｒｓＮｏｖ．２０１７减少候选项集的数据流高效用项集挖掘算法１２茹蓓，贺新征（１．新乡学院计算机与信息工程学院，河南新乡４５３００３；２．河南大学计算机与信息工程学院，河南开封４７５００４）摘要：大数据环境下高效用项集挖掘算法中过多的候选项集极大地降低了算法的时空效率，为此提出了一种减少候选项集的数据流高效用项集挖掘算法。通过数据流中当前窗口的一次扫描建立一个全局树，并降低全局树中头表入口与节点的冗余效用值

2、。基于全局树生成候选模式，基于增长算法降低局部树的候选项集效用，从候选模式中选出高效用模式。基于真实数据流的实验结果表明，算法的时空效率与内存占用比均优于其他数据流的高效用模式挖掘算法。关键词：大数据；数据流；高效用项集；模式挖掘；模式增长；候选模式中图分类号：ＴＰ３０１．６文献标志码：Ａ文章编号：１００１３６９５（２０１７）１１３３７９０５ｄｏｉ：１０．３９６９／ｊ．ｉｓｓｎ．１００１３６９５．２０１７．１１．０３９Ｈｉｇｈｕｔｉｌｉｔｙｉｔｅｍｓｅｔｓｍｉｎｉｎｇａｌｇｏｒｉｔｈｍｏｆｄａｔａｓｔｒｅａｍｗｉｔｈｒｅ

3、ｄｕｃｉｎｇｃａｎｄｉｄａｔｅｉｔｅｍｓｅｔｓ１２ＲｕＢｅｉ，ＨｅＸｉｎｚｈｅｎｇ（１．ＳｃｈｏｏｌｏｆＣｏｍｐｕｔｅｒ＆ＩｎｆｏｒｍａｔｉｏｎＥｎｇｉｎｅｅｒｉｎｇ，ＸｉｎｘｉａｎｇＵｎｉｖｅｒｓｉｔｙ，ＸｉｎｘｉａｎｇＨｅｎａｎ４５３００３，Ｃｈｉｎａ；２．ＳｃｈｏｏｌｏｆＣｏｍｐｕｔｅｒ＆ＩｎｆｏｒｍａｔｉｏｎＥｎｇｉｎｅｅｒｉｎｇ，ＨｅｎａｎＵｎｉｖｅｒｓｉｔｙ，ＫａｉｆｅｎｇＨｅｎａｎ４７５００４，Ｃｈｉｎａ）Ａｂｓｔｒａｃｔ：Ｉｎｔｈｅｂｉｇｄａｔａｓｔｒｅａｍｓｃｅｎａｒｉｏ，ｈｉｇｈｕｔｉｌｉｔｙｐａｔｔｅｒｎ

4、ｍｉｎｉｎｇａｌｇｏｒｉｔｈｍｇｅｎｅｒａｔｅｄａｌｏｔｏｆｃａｎｄｉｄａｔｅｉｔｅｍｓｅｔｓａｎｄｒｅｄｕｃｅｄｔｈｅｅｆｆｉｃｉｅｎｃｙｏｆｔｉｍｅａｎｄｓｐａｃｅｏｆａｌｇｏｒｉｔｈｍ．Ｔｈｉｓｐａｐｅｒｐｒｏｐｏｓｅｄａｈｉｇｈｕｔｉｌｉｔｙｉｔｅｍｓｅｔｓｍｉｎｉｎｇａｌｇｏｒｉｔｈｍｏｆｄａｔａｓｔｒｅａｍｗｉｔｈｒｅｄｕｃｉｎｇｃａｎｄｉｄａｔｅｉｔｅｍｓｅｔｓｔｏｒｅｓｏｌｖｅｔｈａｔｐｒｏｂｌｅｍ．Ｆｉｒｓｔｌｙ，ｉｔｃｏｎｓｔｒｕｃｔｅｄａｇｌｏｂａｌｔｒｅｅｔｈｒｏｕｇｈａｓｉｎｇｌｅｓｃａｎｏｆｔｈｅｃ

5、ｕｒｒｅｎｔｗｉｎｄｏｗｉｎａｄａｔａｓｔｒｅａｍ，ｒｅｄｕｃｅｄｒｅｄｕｎｄａｎｃｙｕｔｉｌｉｔｉｅｓｉｎｂｏｔｈｅｎｔｒｉｅｓｏｆａｈｅａｄｅｒｔａｂｌｅａｎｄｎｏｄｅｓｉｎｔｈｅｔｒｅｅｉｎｔｈｉｓｓｔａｇｅ．Ｓｅｃｏｎｄｌｙ，ｉｔｇｅｎｅｒａｔｅｄｃａｎｄｉｄａｔｅｐａｔｔｅｒｎｓｆｒｏｍｔｈｅｃｏｎｓｔｒｕｃｔｅｄｔｒｅｅ，ｒｅｄｕｃｅｄｔｈｅｒｅｄｕｎｄａｎｃｙｕｔｉｌｉｔｉｅｓｏｆｌｏｃａｌｔｒｅｅｂｙｇｒｏｗｔｈａｌｇｏｒｉｔｈｍ．Ｌａｓｔｌｙ，ｉｔｉｄｅｎｔｉｆｉｅｄａｓｅｔｏｆｈｉｇｈｕｔｉｌｉｔｙｐａｔ

6、ｔｅｒｎｓｆｒｏｍｔｈｅｃａｎｄｉｄａｔｅｐａｔｔｅｒｎｓ．Ｒｅａｌｉｓｔｉｃｄａｔａｓｔｒｅａｍｓｂａｓｅｄｅｘｐｅｒｉｍｅｎｔａｌｒｅｓｕｌｔｓｓｈｏｗｔｈａｔｔｈｅｐｒｏｐｏｓｅｄａｌｇｏｒｉｔｈｍｐｅｒｆｏｒｍｓｂｅｔｔｅｒｉｎｅｆｆｉｃｉｅｎｃｙｏｆｔｉｍｅａｎｄｓｐａｃｅａｎｄｍｅｍｏｒｙｕｓａｇｅｉｎｄｅｘｔｈａｎｔｈｅｏｔｈｅｒｈｉｇｈｕｔｉｌｉｔｙｐａｔｔｅｒｎｍｉｎｉｎｇａｌｇｏｒｉｔｈｍｏｆｄａｔａｓｔｒｅａｍｓ．Ｋｅｙｗｏｒｄｓ：ｂｉｇｄａｔａ；ｄａｔａｓｔｒｅａｍ；ｈｉｇｈｕｔｉｌｉｔｙｉｔｅｍｓｅｔ

7、ｓ；ｐａｔｔｅｒｎｍｉｎｉｎｇ；ｐａｔｔｅｒｎｇｒｏｗｔｈ；ｃａｎｄｉｄａｔｅｐａｔｔｅｒｎ集扫描减少为只需要进行两次数据集的扫描便可挖掘出所有!引言的高效用模式。此类算法均通过产生候选项集以实现对高效用模式的提取，但过多的候选项集严重地降低了算法的运行时随着移动互联网的普及，信息呈爆炸式增长，用户更关心［８］间与挖掘效率。针对候选项集过多的问题，文献［９］通过将最近的数据流。例如在股票市场中，用户为了观察股市波动规事务项集和项集效用信息有效地保存到树结构ＨＵＰｔｒｅｅ中，律，重点分析近几天或最近几小时的交易情况。频繁模式挖掘

8、［１～３］提出了不需要候选项集的挖掘算法。该算法是对ｔｏｐｋ高效用是分析此类数据流的重要方案。频繁模式挖掘仅考虑项模式挖掘算法的改进，有一定的局限性。集在事务中的出现情况，并未考虑事务中各项的内部效用值（数量等）与外部效用值（利润、价格等）；而高效用项集挖掘算