论文部分内容阅读
在技术不断变革的今天,越来越多的数据被生产出来。如何从庞杂的数据中发现有趣或有价值的内容成为目前学术界和工业界最为关注的问题。其中频繁模式挖掘因其能有效地挖掘出事务内在的联系而被广泛地应用于基因分析、文本分类、肿瘤诊断、图像处理等领域,但是频繁模式算法中的项在事务中只有两种状态:存在或者不存在。为了解决频繁模式算法只考虑项是否存在事务中而忽略了项本身效用的不足,高效用模式挖掘算法被提出。然而目前的高效用模式挖掘算法仍然存在很多不足,其中最主要问题是:(1)算法不易扩展;(2)算法缺少对于事务信息的有效压缩;(3)算法时效性低。本文针对这三个主要问题分别提出了基于静态数据库的高效用模式挖掘算法和基于动态增量数据库的增量高效用模式挖掘算法,并取得了优异的效果。同时本文给出了高效用模式挖掘算法在微博好友推荐中的实际应用。本文的主要工作有:1.提出了一个静态数据库中基于投影的高效用模式挖掘算法HUPMP。HUPMP是一阶段算法,在进行高效用模式挖掘的过程中不产生任何候选模式。2.提出了一个用以解决动态增量数据库问题的增量高效用算法IHUP。IHUP是在HUPMP的基础上提出的,充分利用了 HUPMP算法的可扩展性。3.提出了两个有效的结构HUP-Array和HUP-Result分别用来存储事务信息和高效用模式。使用HUP-Array结构将事务进行合并压缩,同时还极大地提高了算法的可扩展性。HUP-Result结构可以对结果集进行快速的查找和更新,使得算法在动态增量数据库的业务场景中有更高的响应速度。4.制定了四个策略用来提高算法的时间性能和减少算法的内存消耗。其中项按支持度降序排列策略可以极大地合并事务,将事务有效压缩以节省内存。前缀项之和的策略可以将HUP-Array的比较时间复杂度从O(M×N)降到O(1)。紧凑事务权重上限策略可以快速对低效用模式进行删减,提高算法性能。只处理新增事务中的项的策略可以很好应对增量高效用模式挖掘中对算法响应度高的要求。5.通过实验分别验证了 HUPMP和IHUP算法的有效性。通过与多个优秀算法在不同数据库下的仿真实验表明本文提出的HUPMP和IHUP算法分别在静态数据库和动态增量数据库中都有不错的性能。6.给出了高效用模式挖掘算法在微博好友推荐中的实际应用。通过对静态数据库和动态增量数据库两种不同场景下的高效用模式挖掘应用,说明了高效用模式挖掘算法在实际推荐系统中的灵活性和可扩展性。