论文摘要
关联规则的挖掘就是要发现大量数据中项集之间的关联或相关联系,它是数据挖掘研究的重要内容之一,在科学研究、电信网络、市场与风险管理、客户关系管理（CRM）、存货控制、军事等方面得到了广泛应用。但是,传统的关联规则以支持度衡量项集的重要性,会丢失一些支持度不高但效用很高、用户很可能感兴趣的规则。本文研究的高效用关联规则弥补了传统关联规则无法表达项集效用的不足,能反映用户偏好,更好地满足决策需求。本文主要研究高维大数据集中高效用关联规则的挖掘算法,弥补了现有的基于效用关联规则挖掘算法不能有效处理高维大数据集的不足。文中还结合效用与支持度的特点,提出了基于效用与支持度的关联规则挖掘问题及算法,可发现更多的用户感兴趣的规则。本文的主要研究有:（1）提出了一种新的在高维大数据集中挖掘高效用长项集的算法Inter-transaction。该算法基于行枚举,通过长事务的交集运算,直接得到长项集,不必从短项集逐步扩展得到长项集。在高维数据集中,长事务间共同项目很少,事务进行交集运算后变短的速度很快,因此这种行枚举方法具有很好的收敛性。Inter-transaction算法还把划分的方法引入到效用挖掘中,仅扫描数据库两次,能很好地适应高维大数据集环境。同时,由于采用了新的剪枝策略,避免了大量的候选集的生成、检验。（2）提出了一种双向搜索高效用项集的混杂算法。现有的基于效用的关联规则挖掘算法采用类似Apriori的搜索策略,需要多次扫描数据库。当模式很长且数据集很大时,I/O负担太重。本文提出了一种从上下两个方向搜索高效用项集的混杂算法。该算法把发现所有高效用项集的任务分解为发现高效用长项集和高效用短项集两个相对容易解决的子问题,然后再选择不同的算法完成挖掘任务,避免了从短项集逐步扩展到长项集的冗长过程。（3）提出了一种优化长事务交集运算的方法。我们提出的挖掘高效用长项集的算法同时以水平项目向量（Horizontal item-vector,简称HIV）和水平项目列表（Horizontal item-list,简称HIL）两种格式存储事务,并利用HIL格式数据提供的信息减少比特级逻辑“与”运算的次数,使逻辑“与”运算的次数等于HIL格式数据的长度,与比特向量（HIV格式）的长度无关。这种以空间换时间的方法解决了事务交集运算的性能随比特向量长度的增长而降低的问题,保证了在高维环境下的高性能。这种优化方法也可有效提高垂直挖掘算法挖掘频繁长模式的效率。（4）提出了基于效用与支持度的关联规则挖掘问题。支持度与效用分别反映了项集的统计特性与语义特性,但人们对事物的兴趣度（或事物对人们的重要性）不但取决于事物本身的客观因素（如项集的支持度）,与人们的主观因素（如人们对效用的不同理解）也密不可分。为克服单个度量（支持度或效用）的不足,本文提出了一种衡量项集重要性的新的度量:激励。项集的激励定义为支持度与效用的乘积,反映了用户获得某种效用的可能性或以某种可能性可获得多大的效用。在基于效用与支持度的关联规则挖掘中,高激励项集的挖掘避免了那些支持度不高但效用较高、或效用不高但支持度较高的项集的丢失,能发现更多的用户感兴趣的规则。（5）论证了激励具有两个重要的数学性质:上界特性和事务权重激励向下封闭特性。根据这两个特性,设计了两种挖掘高效用频繁集的算法HM-Miner和HM-Two-Phase-Miner。两种算法都采用了类似Apriori的自下而上的搜索方式,适合于短模式数据集的挖掘。HM-Miner利用激励的上界特性剪枝,HM-Two-Phase-Miner则利用事务权重激励向下封闭特性剪枝。（6）给出了一个高效用关联规则挖掘的应用系统,并用于购物篮分析中。该系统能同时输出关联规则（项集）的支持度、效用与激励,以比较基于支持度的关联规则与高效用关联规则挖掘的区别与联系。实际挖掘结果表明,高效用关联规则的挖掘能发现一些基于支持度关联规则无法发现的有趣模式,帮助商家找出高效用商品组合,促进高利润商品的销售。经过数据的转换处理,该系统还可应用于其他领域。例如,在网页分析中,把网页被访问的次数与浏览时间作为评价网页受欢迎程度的尺度,将网页挖掘问题变成高效用项集的挖掘问题。