高效用项集挖掘是通过效用值来衡量项集的重要性、反应用户的兴趣度,能较好的解决用户的问题,是数据挖掘研究领域的一个热门话题。高效用项集挖掘算法研究相对比较成熟,其效用值是正值,但随着处理实际问题的应用研究的深入,发现现实生活中存在负项值的情形,例如,商场时常推出的买赠活动,赠送的商品获得的利润值为负值。又例如,一些商品在商场中由于季度等原因可能会频繁地上架下架等问题,因此,考虑含有负项值、on-shelf时间段的高效用项集挖掘更具有现实意义,而传统的高效用项集挖掘算法无法解决该类问题。本文从提升含有负项值的高效用项集挖掘性能的角度出发,主要研究了含有负项值的高效用项集挖掘和含有负项值的on-shelf效用项集挖掘两个问题,主要的工作有:(1)研究了如何有效提高含有负项值的高效用项集挖掘的挖掘效率。处理含有负项值的高效用项集挖掘的算法在剪枝过程中考虑了正项而忽略了负项,影响剪枝效果。为此,提出了高效的挖掘算法EHINM。EHINM算法提出一种改进的效用列表结构来保存事务数据库的效用信息。这种效用列表结构为三元组结构,与以往含有负项值的高效用项集挖掘算法中使用的四元组效用列表结构不同,其考虑了负项进而将四元组结构中存储的信息进行了压缩,既减少了存储空间,又能根据结构中存储的信息对搜索空间进一步的缩减。算法根据重新定义的剪枝上界和改进的效用列表结构提出了三种剪枝策略。同时,提出了负项的扩展性质用于减少对搜索空间的遍历。实验结果表明,EHINM算法能够有效地提升项集挖掘效率。(2)研究了含有负项值的on-shelf效用项集并行挖掘问题。On-shelf效用项集挖掘和高效用项集挖掘一样,面临着指数级的搜索空间,因而如何有效地提高挖掘效率是其亟需解决的问题。算法并行化是提高算法效率的一种有效途径,为此,提出了含有负项值的on-shelf效用项集并行挖掘算法DTP-Houn。DTP-Houn算法基于MapReduce框架,充分利用on-shelf时间段因素,将原始事务数据库按照时间段进行分片。算法将挖掘过程转化为MapReduce工作,Map阶段在分片数据库中挖掘候选项集,Reduce阶段并行计算候选项集的on-shelf效用值。实验结果表明,DTP-Houn算法取得了较高的挖掘效率。