论文部分内容阅读
互联网、物联网、云计算等信息技术的快速发展，政治、经济、军事、工业等各个领域的传统应用开始与之相结合，产生了比以往任何时候都要多的数据。同时，智能移动设备、传感器、电子商务网站、社交网站等等数据来源每时每刻都在创造多种多样的数据。面对如此大量的数据，如何及时、有效地分析它们并从中提取出有价值的信息，是政府和企业亟待解决的问题。例如，中国证券监督管理委员会(CSRC)通过股票买家和卖家的交易价格和数量来判断是否存在交易内幕和炒家的操控;支付宝网络科技公司通过分析支付宝用户在网络平台上的消费记录获取不同用户的消费习惯并制定相应的市场策略;交通部以不同的时间间隔分析道路网络的交通流量信息，并制定减少城市交通拥堵的政策。数据挖掘作为一种从大量数据中挖掘重要的、未知的、有潜在价值的模式的处理过程，被广泛用于解决这类问题。关联规则挖掘(ARM)是数据挖掘的核心任务之一。然而，依赖支持度(value of support)提取模式的传统方法并不能很好支持依据效用(value of utility)的模式提取。因此，效用模式挖掘，这是我们研究的主题，已经出现了为了满足这一需求。最近，在这一领域提出了许多算法。然而，现有的挖掘算法在运行时、抽取模式数、挖掘结果更新处理等方面还存在一些问题此外，在一些应用程序中，仍然需要找到满足用户需求的新模式类型因此，本文提出了效用项集挖掘领域的四个问题，取得以下研究成果:
1.提出了一种新颖的基于单次扫描数据库的高效用项集挖掘算法SSUP-Growth。扫描数据库生成候选项集是高效用项集挖掘算法的主要挑战之一，UP-Growth算法是目前最先进算法。然而该算法有两个缺点:第一，它需要两次扫描数据库来构建UP树数据结构，这一过程通常非常耗时;第二，当使用新数据更新现有数据时，UP-Growth算法需要对新数据库和现有数据库进行双重扫描，该操作同样非常耗时。因此，本文提出SSUP-Growth算法来克服以上缺点，该算法只需一次扫描数据库构建UP树，同时在使用新数据更新挖掘结果时，也仅需要扫描一次新数据。算法同时使用树的一个分支来表示数据库中包含相同项目的不同事务，这样对树中一个分支的处理相当于对数据库中许多项目的处理，进一步提高了效率。通过实验验证，与类似算法相比，SSUP-Growth算法的运行时间得到了显著改善。
2.许多高效用项集挖掘算法使用多个最小效用(MMU)阈值来衡量项集中每个项目的重要性和属性的差分。在这些方法中，每个项目都被赋予一个独特的最小效用值。然而，由于最小效用值是使用百分比计算的，所以这些方法会出现“规则消失”和“规则爆炸”的问题。鉴于此，我们提出了一个新的策略——效用差分(Utility Differential，UD)，用于有效地指定最小项目效用值，以便使用多个最小效用阈值来增强高效用项集挖掘。UD确保了全局最小效用与每个项目的相应最小项目效用值之问的固定差分。此外，我们还提出了基于UD的两阶段算法HUI-MMU-UD。为了说明UD的有效性，我们将其应用到最先进的算法HUI-MMU，并在四个稠密和稀疏数据集上进行实验，对UD进行精确的评估。与现有策略相比，实验结果表明使用UD提取出的高效用项集更具说服力。
3.效用挖掘的已有工作绝大多数都只关心高效用项集(HUIs)。然而，在很多实际场景中，低效用项集(LUIs)也是十分有用且有意义的。比如，在安防系统中，低效用项集能够反映需要监视的安全盲区。因此，我们提出了一个新的低效用项集的关联规则挖掘框架LUIM，用来提取低效用项集。为了提高LUIM的性能，我们研究了TWDC(Transaction Weighted Downward Closure)属性，以改进效用挖掘生成器的包含性。具体地，所提出的策略基于项集TWU(Transaction Weighted Utility)来确定生成器，这对于效用挖掘来说更为有效。本文提出了两种高效算法:LUG-Miner(低效用生成挖掘)和LUIMA(低效用项集挖掘算法)。LUG-Miner从TWU模型获得有用的属性并结合level-wise算法提取低效用生成器(LUG);LUIMA使用LUG来挖掘所有低效用项集。在稠密和稀疏数据集上的实验结果验证了所提框架和算法均能有效运行。
4.许多模式的提取需要同时考虑频度阈值和效用阈值，比如频繁高效用项集模式和高效用稀有项集模式。然而，已有工作忽略了其中一个重要模式，即频繁低效用项集(FLUIs)，该模式中的项目频度是增加它们效用值的一个重要因素。因此，本文提出了一个用于提取频繁低效用项集(FLUI)这个新模式的框架，并设计了频繁低效用项集挖掘算法FLUI-Growth。FLUI-Growth算法是已知UP-Growth算法的扩展，使用紧凑树结构来提取所需的项集。为了评估所提框架和算法，论文在许多基准数据库上进行了实验。实验结果验证了新框架和新算法的有效性和实用性及其在现实生活中的适用性。
1.提出了一种新颖的基于单次扫描数据库的高效用项集挖掘算法SSUP-Growth。扫描数据库生成候选项集是高效用项集挖掘算法的主要挑战之一，UP-Growth算法是目前最先进算法。然而该算法有两个缺点:第一，它需要两次扫描数据库来构建UP树数据结构，这一过程通常非常耗时;第二，当使用新数据更新现有数据时，UP-Growth算法需要对新数据库和现有数据库进行双重扫描，该操作同样非常耗时。因此，本文提出SSUP-Growth算法来克服以上缺点，该算法只需一次扫描数据库构建UP树，同时在使用新数据更新挖掘结果时，也仅需要扫描一次新数据。算法同时使用树的一个分支来表示数据库中包含相同项目的不同事务，这样对树中一个分支的处理相当于对数据库中许多项目的处理，进一步提高了效率。通过实验验证，与类似算法相比，SSUP-Growth算法的运行时间得到了显著改善。
2.许多高效用项集挖掘算法使用多个最小效用(MMU)阈值来衡量项集中每个项目的重要性和属性的差分。在这些方法中，每个项目都被赋予一个独特的最小效用值。然而，由于最小效用值是使用百分比计算的，所以这些方法会出现“规则消失”和“规则爆炸”的问题。鉴于此，我们提出了一个新的策略——效用差分(Utility Differential，UD)，用于有效地指定最小项目效用值，以便使用多个最小效用阈值来增强高效用项集挖掘。UD确保了全局最小效用与每个项目的相应最小项目效用值之问的固定差分。此外，我们还提出了基于UD的两阶段算法HUI-MMU-UD。为了说明UD的有效性，我们将其应用到最先进的算法HUI-MMU，并在四个稠密和稀疏数据集上进行实验，对UD进行精确的评估。与现有策略相比，实验结果表明使用UD提取出的高效用项集更具说服力。
3.效用挖掘的已有工作绝大多数都只关心高效用项集(HUIs)。然而，在很多实际场景中，低效用项集(LUIs)也是十分有用且有意义的。比如，在安防系统中，低效用项集能够反映需要监视的安全盲区。因此，我们提出了一个新的低效用项集的关联规则挖掘框架LUIM，用来提取低效用项集。为了提高LUIM的性能，我们研究了TWDC(Transaction Weighted Downward Closure)属性，以改进效用挖掘生成器的包含性。具体地，所提出的策略基于项集TWU(Transaction Weighted Utility)来确定生成器，这对于效用挖掘来说更为有效。本文提出了两种高效算法:LUG-Miner(低效用生成挖掘)和LUIMA(低效用项集挖掘算法)。LUG-Miner从TWU模型获得有用的属性并结合level-wise算法提取低效用生成器(LUG);LUIMA使用LUG来挖掘所有低效用项集。在稠密和稀疏数据集上的实验结果验证了所提框架和算法均能有效运行。
4.许多模式的提取需要同时考虑频度阈值和效用阈值，比如频繁高效用项集模式和高效用稀有项集模式。然而，已有工作忽略了其中一个重要模式，即频繁低效用项集(FLUIs)，该模式中的项目频度是增加它们效用值的一个重要因素。因此，本文提出了一个用于提取频繁低效用项集(FLUI)这个新模式的框架，并设计了频繁低效用项集挖掘算法FLUI-Growth。FLUI-Growth算法是已知UP-Growth算法的扩展，使用紧凑树结构来提取所需的项集。为了评估所提框架和算法，论文在许多基准数据库上进行了实验。实验结果验证了新框架和新算法的有效性和实用性及其在现实生活中的适用性。