智能数据挖掘--面向不确定数据的频繁模式（精）

作者简介

内容简介

第3章Eclat框架下基于支持度的双向排序策略 前面章节简单介绍了频繁模式挖掘的主要概念、背景和方法，分析了目前主要的不确定数据模型，综述了各种不确定频繁模式挖掘技术，并指出不确定频繁项集挖掘方法是其他不确定频繁模式挖掘方法的基础，后者大都借鉴了确定数据库中的经典挖掘算法。 本章主要讨论基于概率数据的不确定频繁项集挖掘问题和相应的改进策略。本章结构安排如下: 3.1节介绍经典Eclat算法存在的不足并证明一个关于支持度的性质；3.2节介绍面向确定数据库、基于支持度排序的双向处理策略；3.3节介绍面向不确定数据库、适用于概率频繁模式挖掘的双向排序策略；相关实验结果及分析在3.4节列出；最后3.5节对本章内容进行小结。 3.1基于垂直数据格式的Eclat算法〖1〗3.1.1存在的问题在频繁项集挖掘中，项集支持度的计算主要采用计数和交操作两种方法\[26\]。Eclat算法是首个采用垂直数据格式，通过交操作枚举所有频繁项集的算法。该算法采用自底向上的深度优先搜索，引入等价类概念将搜索空间划分为多个不重叠的子空间，然后针对各个子空间内的候选项集分别处理。Eclat算法中支持度计算和候选项集生成步骤同时完成，通过计算两个项集的Tidlist交集快速得到候选项集的支持度。若候选项集的支持度小于最小支持度阈值min_sup，则自动删除。 由上述处理过程得知，Eclat算法可能存在以下问题\[174,175\]。 (1) 候选项集由两个子集的并操作产生，即对拥有k-1个共同前缀的两个k频繁项集进行并操作产生(k+1)候选项集。这样，当Tidlist规模庞大时，完成并操作，通过交操作计算候选项集的支持度都会耗费大量的时空代价。/智能数据挖掘——面向不确定数据的频繁模式第3章Eclat框架下基于支持度的双向排序策略/(2) Eclat算法采用自底向上深度搜索的方式，逆字母表顺序处理等价类，自右向左通过交操作逐步挖掘所有频繁项集。这里，算法没有充分利用已产生的支持度计数信息缩减候选项集的搜索范围。 (3) Eclat算法没有充分利用Apriori先验性质对候选项集进行有效的剪枝。因此，某些情况下，Eclat算法产生的候选项集数目远远大于Apriori算法。 3.1.2支持度性质及证明 猜想支持度越高的子集，越有可能成为更长候选项集的一部分；而支持度较低的子集，构成更长候选项集的可能性也相对降低。 证明数学归纳法。 任选项集X∈D，构成项集X的项目可以按照不同顺序排列: X={xmax,xmax-1,xmax-2,…,x1}表示构成项集X的项目按照支持度降序排列，而X={x1,x2,…,xmax} (max为整数)表示项目按支持度升序排列。对于频繁项集X，存在sup({x1})≤sup({x2})≤…≤sup({xmax-1})≤sup({xmax})。如果使用项目y作为项集的前缀，并对项集X进行扩展从而生成候选k项集，可以表示为1\|item\|extension(X):=Y={y}∪X。 当n=1时，对单元素频繁项集X进行1项集扩展。根据Apriori先验性质或反单调性，存在:sup({xmax}∩{xmax-1})≤min(sup{xmax},sup{xmax-1})≤sup({xmax-1}) sup({x1}∩(x2})≤min(sup{x1},sup{x2})≤sup({x1})给定sup({x1})≤min_sup≤sup({xmax-1})。这里项目xmax-1也是单元素频繁项集，可以作为前缀参与生成更长频繁项集；而项目x1在给定的最小支持度阈值下作为非频繁项目被剪枝。在sup({x1})≤min_sup≤sup({xmax-1})这一前提条件下，给定不同的最小支持度阈值，具有较高支持度的项集xmax-1更有可能满足不等式sup({xmax-1})≥min_sup。也就是说，与x1相比，项目xmax-1成为频繁项目的可能性更大，因此，更有可能作为前缀生成更长候选项集。这样，单元素频繁项集X在进行1项集扩展时，支持度高的项集有更多机会构成更长频繁项集。 假设n＝k时命题成立。存在(k-1)频繁项集X和频繁项目y，构成项集X的所有项目可以按照不同顺序排列: 按支持度降序排列可以表示为X={xk-1,xk-2,…,x1}，按支持度升序排列可以表示为X={x1,x2,…,xk-1}。下面分别用xk，y1做前缀对项集X进行扩展进而生成候选k项集，表示为如下形式: Y1={xk}∪X={xk}∪{xk－1,xk－2,…,x1}，Y2={y1}∪X={y1}∪{x1,x2,…,xk-1}。存在sup({y1})≤sup({x1})≤sup({xk－1})≤sup({xk})，并且如下不等式: sup({y1}∪X)≤sup({xk}∪X)成立，即前缀xk有更多机会参与生成更长频繁项集。 当n＝k+1时，对k频繁项集X进行1项集扩展的情况。构成项集X的项目按照支持度升序排列，可以表示为sup({x1})≤sup({x2})≤…≤sup({xk－1})≤sup({xk})≤sup({xk+1})。下面分别用xk+1、z1做前缀，扩展项集X进而生成候选(k+1)项集，表示为如下形式: Z1={xk+1}∪{xk,xk－1,xk－2,…,x1}={xk+1}∪Y1；Z2={z1}∪{y1,x1,x2,…,xk－1}={z1}∪Y2，其中，sup({z1})≤sup({y1})≤…≤sup({xk})≤sup({xk+1})。根据Apriori先验性质或反单调性，比较不同排序方式下(k+1)项集的支持度计数: sup(({xk+1}∪Y1)∩({xk}∪Y1))≤min(sup({xk+1}∪Y1),sup({xk}∪Y1)) ≤sup({xk}∪Y1)≤sup({xk}∪X) sup(({z1}∪Y2)∩({y1}∪Y2))≤min(sup({z1}∪Y2)),sup({y1}∪Y2)) ≤sup({z1}∪Y2)≤sup({y1}∪Y2)≤sup({y1}∪X)给定最小支持度阈值min_sup，满足如下不等式: sup({y1}∪X)≤min_sup≤sup({xk}∪X)。根据n=k时不等式sup({y1}们首先参与交运算并进行支持度比对。根据支持度性质，一旦发现其支持度低于给定的最小支持度阈值，立即终止，从而保证了尽早结束递归算法。相反，BiEclat逆序算法中项集采用支持度降序排列，位于频繁项集开头的每一个项目具有最高的支持度，在进行支持度比对时极有可能大于最小支持度阈值，从而继续下一步交操作，直至最后找到支持度较小的项目才退出递归算法。这时虽然发现前面的比对操作只是“无用功”而陡然增加了冗余操作，但也是无计可施，从而导致算法性能较差。 实验结果分析中还得到以下可能结论。图3.3在稠密数据集Connects上的性能比较 图3.4在稠密数据集Mushroom上的性能比较 图3.5在中等密度数据集Accidents上的性能比较 图3.6在较稀疏数据集T40I10D100K上的性能比较 首先，给定相同的min_sup阈值，尽管这三种算法耗费的运行时间存在差别，但挖掘出的频繁项集数量基本相同(见图3.7)。算法运行结果的一致性验证了算法的正确性，为下一步针对三种算法的性能比较奠定了基础。 图3.7双向处理策略在稀疏数据集T10I4D100K上的性能: 频繁项集数量 其次，从实验结果明显看到，算法的时间开销随着最小支持度阈值min_sup的增加而减少，这是因为给定的min_sup阈值越大, 产生的候选项集数目越少, 扫描数据库的次数也减少(见图3.3～图3.6)。当min_sup阈值降低时，这三种算法挖掘出的频繁项集数量也迅速增加(见图3.7)，运行时间也都显著提高(见图3.8)。 实验结果表明，随着min_sup阈值的提高，这三种算法的内存占用都平滑降低，尽管降低的幅度很小(见图3.9)。实际上，数据库按支持度升序或降序存储并没有增加额外的内存开销。当然，在内存需求方面，双向处理策略也没有表现出显著的性能优势。在内存占用相似的前提下，基于相同的Eclat框架，采用不同支持度排序策略的频繁项集挖掘算法在不同数据集上显示出迥然不同的挖掘性能。在中等稠密度的Accidents数据集上，BiEclat算法和BiEclat逆序算法在运行时间指标上都取得了优势，虽然与不确定数据集上的实验结果相比，这一优势并不十分明显。与先前的预测一致，传统Eclat算法的性能 图3.8双向处理策略在稀疏数据集T10I4D100K上的性能比较: 运行时间 图3.9双向处理策略在稀疏数据集T10I4D100K上的性能比较: 内存占用 明显落后于两种按照支持度排序的算法。究其原因，应该是字母序排列的Eclat算法在处理过程中受累于冗长的交运算和繁复的计算而导致了性能损失。∪X)≤sup({xk}∪X)成立，得知具有较高支持度的项集{xk}∪X更有可能满足不等式sup({xk}∪X)≥min_sup。这样，用单元素频繁项集做前缀对频繁项集X进行1项集扩展时，支持度较高的前缀xk+1有更多机会参与生成更长频繁项集。因此，当n=k＋1时，命题成立。 结论: 用单元素频繁项集做前缀对频繁项集X进行1项集扩展时，上述猜想成立。 使用相似方法，可以证明任意长度的频繁项集运用并运算对频繁项集X进行k项集扩展，并用两个k-1频繁项集的交运算产生候选k项集时，上述猜想均成立。因此得到了关于支持度的性质。 性质3.1支持度越高的子集，越有可能成为更长候选项集的一部分；而支持度较低的子集，构成更长候选项集的可能性也相对降低。 3.2基于支持度排序的双向处理策略 依据支持度性质，本节提出基于支持度排序的双向处理策略，并对传统的Eclat算法进行改进，提出BiEclat算法。BiEclat算法的核心思想是: 在存储事务时，Tidlist结构中的数据按支持度降序排列以提高数据存储的紧致性，改进存储效率；在支持度计数并产生频繁项集阶段，参与计算的(k-1)频繁项集按支持度升序排列，以减少冗余操作，提高计算效率, 进而达到提升整个算法性能的目的。 3.2.1支持度升序排列阶段 在频繁项集发现阶段，候选项集的规模对算法的执行效率有着举足轻重的影响。Eclat算法基于字母表顺序自底向上搜索频繁项集，因此，候选项集的数量主要取决于划分的等价类尺寸和需要搜索的存储空间范围。由于Eclat算法没有基于支持度并依据Apriori先验性质对候选项集进行有效剪枝，随着Tidlist结构的规模不断增大，算法效率显著降低。 考虑到支持度计算中采用不同排序方式对频繁项集生成效率的影响，基于上述支持度性质对Eclat算法进行改进。在频繁项集产生阶段，候选项集及构成候选项集的项目按照支持度升序排列并参与交运算和支持度计算。采用这一策略的出发点主要体现在如下两个方面。 (1) 对构成候选项集的项目按照支持度升序排列后，首先选取支持度较低的项目作为前缀扩展生成更长频繁项集。这样，具有较低支持度的项目首先参与交操作，在计算过程中一旦检查出支持度小于min_sup的非频繁节点就立即终止计数过程，减少了实际访问的项目数量，避免了后续的冗余操作。例如，当确定候选项集{A，B，E}时，若采用字母表顺序(即A