最大多样频繁项集挖掘算法研究
发布时间：2021-06-23 03:41
随着信息技术的飞速发展,数据达到前所未有的规模体量。大规模的数据在给人们的日常生活、工作来了便利的同时也产生了许多问题,这主要体现在人类的数据收集、数据组织能力和数据处理能力之间存在非常大的差距,缺乏行之有效的数据分析和挖掘方法,人们无法充分利用收集到的数据,从而导致了“数据爆炸但知识贫乏”的现象。频繁模式挖掘通常是大规模数据分析的第一步,多年以来都是数据挖掘领域里非常活跃的一个研究主题。频繁项集挖掘是频繁模式挖掘中的一个重要任务,频繁项集挖掘是在给定数据集中挖掘支持度满足预定义的最小支持度阈值的项集,通过挖掘数据集中的频繁项集,能够分析数据的关联规则。传统的频繁项集挖掘方法存在一个问题是频繁项集的数量非常庞大,计算和存储这些频繁项集都是一个不小的挑战,而且挖掘如此大量的频繁项集通常是没有必要的。针对这个问题不少科研学者提出了很多基于条件约束的频繁项集,如闭频繁项集挖掘、最大频繁项集挖掘等。本论文通过对大量文献的研究整理,详细的介绍了频繁项集挖掘的背景、发展以及研究现状,分析了目前频繁项集研究领域的热点问题。论文在现有的研究基础上提出了一种最大多样频繁项集的概念,最大多样频繁项集满足最...
【文章来源】：深圳大学广东省
【文章页数】：63 页
【学位级别】：硕士
【部分图文】：
类别树示例
最大多样频繁项集挖掘算法研究18集中所有的最大频繁项集（MFIs），FPMax算法挖掘到的最大频繁项集存储在候选集中（MFIscandidateset）。然后系统会使用输入的类别树CT数据来计算候选集中每一个最大频繁项集的多样性，关于项集的多样性计算方法在2.2.1节中有详细的介绍，计算出来的带有多样性的最大频繁项集将放入结果队列（ResultQueue）中。结果队列是一个优先队列，它始终保持在队列中的候选结果是按照其多样性降序排列的。在计算出所有的最大频繁项集的多样性之后，就能够取得所需要挖掘的Top-k最大多样频繁项集了，只需要取出在结果队列中处于队列前面的k个最大频繁项集即可。从图2所示的使用基础算法挖掘最大多样频繁项集的架构图可知，基础算法在挖掘最大多样频繁项集的时候会首先挖掘出给定交易数据集中所有的最大频繁项集，然后会计算所有的最大频繁项集的多样性，进而对所有的最大频繁项集按照多样性排序。在这一系列步骤中基础算法均需要处理数据集中所有的最大频繁项集，而事实上最终用户关注的只是其中的k个最大频繁项集，这就导致了基础算法在挖掘最大多样频繁项集时效率不高，这也是本论文研究的基于边界检测的最大多样频繁项集挖掘算法需要解决的问题，该算法将在第3章中进行详细介绍。图2最大多样频繁项集挖掘系统架构2.5本章小结本章首先在2.1节中简单地介绍了频繁项集挖掘的一些基本概念，包括频繁项集挖
最大多样频繁项集挖掘算法研究21当用户给定的最小支持度阈值σ=2，那么根据FP-tree的构建算法，能够得到如图3所示的FP-tree。图3FP-tree示例为了实现基于边界检测的最大多样频繁项集挖掘算法，本论文研究设计了一种FP*-tree的索引结构，它是对FP-tree的一种改进和扩展。FP*-tree在原有的FP-tree的基础上为headertable中的每一个项增加了一个倒排表(PostingList)，记headertable中项i的倒排表为L(i)。倒排表L(i)是在FP*-tree创建过程中动态生成的，它是由数据集中的某些项item及其出现次数counter构成的二元组(item，counter)组成的集合；在该二元组中，item是和项i同时出现在同一交易记录中的一个项，counter是表示在数据集中项item和项i同时出现的次数。因此，项i的倒排表L(i)中记录了数据集中与项i同时出现的各个项及其同时出现的次数。例如，在图5所示的FP*-tree中，项a的倒排表L(a)={(c,8),(e,6)}，表示项c与项a同时出现在8个交易数据集中，项e与项a同时出现在6个数据集中。这里需要说明的是当项a与项b同时出现在一些交易记录中时，项a与项c同时出现同时意味着项c与项a同时出现，但是FP*-tree不会同时在两个项的倒排表中同时记录另外一个项的出现，而是只在一个项中记录另一个项的出现，例如在项a的倒排表中记录二元组（c,8）。如果数据集中的项i′出现在项i的倒排表中，那么必然满足以下两个条件：I：rank(i′)<rank(i)II：T(i′)∩T(i)≠。其中，rank(i)表示headertable中的一个项i在headertable中的位置。headertable中
本文编号：3244153
【文章来源】：深圳大学广东省
【文章页数】：63 页
【学位级别】：硕士
【部分图文】：
类别树示例
最大多样频繁项集挖掘算法研究18集中所有的最大频繁项集（MFIs），FPMax算法挖掘到的最大频繁项集存储在候选集中（MFIscandidateset）。然后系统会使用输入的类别树CT数据来计算候选集中每一个最大频繁项集的多样性，关于项集的多样性计算方法在2.2.1节中有详细的介绍，计算出来的带有多样性的最大频繁项集将放入结果队列（ResultQueue）中。结果队列是一个优先队列，它始终保持在队列中的候选结果是按照其多样性降序排列的。在计算出所有的最大频繁项集的多样性之后，就能够取得所需要挖掘的Top-k最大多样频繁项集了，只需要取出在结果队列中处于队列前面的k个最大频繁项集即可。从图2所示的使用基础算法挖掘最大多样频繁项集的架构图可知，基础算法在挖掘最大多样频繁项集的时候会首先挖掘出给定交易数据集中所有的最大频繁项集，然后会计算所有的最大频繁项集的多样性，进而对所有的最大频繁项集按照多样性排序。在这一系列步骤中基础算法均需要处理数据集中所有的最大频繁项集，而事实上最终用户关注的只是其中的k个最大频繁项集，这就导致了基础算法在挖掘最大多样频繁项集时效率不高，这也是本论文研究的基于边界检测的最大多样频繁项集挖掘算法需要解决的问题，该算法将在第3章中进行详细介绍。图2最大多样频繁项集挖掘系统架构2.5本章小结本章首先在2.1节中简单地介绍了频繁项集挖掘的一些基本概念，包括频繁项集挖
最大多样频繁项集挖掘算法研究21当用户给定的最小支持度阈值σ=2，那么根据FP-tree的构建算法，能够得到如图3所示的FP-tree。图3FP-tree示例为了实现基于边界检测的最大多样频繁项集挖掘算法，本论文研究设计了一种FP*-tree的索引结构，它是对FP-tree的一种改进和扩展。FP*-tree在原有的FP-tree的基础上为headertable中的每一个项增加了一个倒排表(PostingList)，记headertable中项i的倒排表为L(i)。倒排表L(i)是在FP*-tree创建过程中动态生成的，它是由数据集中的某些项item及其出现次数counter构成的二元组(item，counter)组成的集合；在该二元组中，item是和项i同时出现在同一交易记录中的一个项，counter是表示在数据集中项item和项i同时出现的次数。因此，项i的倒排表L(i)中记录了数据集中与项i同时出现的各个项及其同时出现的次数。例如，在图5所示的FP*-tree中，项a的倒排表L(a)={(c,8),(e,6)}，表示项c与项a同时出现在8个交易数据集中，项e与项a同时出现在6个数据集中。这里需要说明的是当项a与项b同时出现在一些交易记录中时，项a与项c同时出现同时意味着项c与项a同时出现，但是FP*-tree不会同时在两个项的倒排表中同时记录另外一个项的出现，而是只在一个项中记录另一个项的出现，例如在项a的倒排表中记录二元组（c,8）。如果数据集中的项i′出现在项i的倒排表中，那么必然满足以下两个条件：I：rank(i′)<rank(i)II：T(i′)∩T(i)≠。其中，rank(i)表示headertable中的一个项i在headertable中的位置。headertable中
本文编号：3244153
本文链接：https://www.wllwen.com/kejilunwen/ruanjiangongchenglunwen/3244153.html
