智能数据挖掘——面向不确定数据的频繁模式

本书全面总结了不确定数据环境下频繁模式挖掘领域的主要研究成果，从数据模型、问题定义、常用算法等方面系统介绍了不确定频繁项集挖掘、不确定序列模式挖掘、不确定频繁子图模式挖掘、不确定高效用项集挖掘以及不确定加权频繁项集挖掘技术。 

本书全面总结了不确定数据环境下频繁模式挖掘领域的主要研究成果，从数据模型、问题定义、常用算法等方面系统介绍不确定频繁项集挖掘、不确定序列模式挖掘、不确定频繁子图模式挖掘、不确定高效用项集挖掘和不确定加权频繁项集挖掘技术。重点针对两类典型的不确定数据，即概率数据和容错数据，进行概率频繁模式挖掘和近似频繁模式挖掘的研究，并应用于传统中医药数据环境下，从主观不确定性和客观不确定性两个方面提出相应的解决方案，实现基于不确定数据的高效频繁模式挖掘，并通过实验验证了它们的有效性和实用性。
本书主要面向对数据挖掘和机器学习感兴趣的科研人员和学生，特别适合从事不确定数据挖掘、频繁模式挖掘和关联规则发现以及相关研究领域的广大科技工作者和研究人员使用，也可以作为数据挖掘和机器学习相关课程的教学参考书。

目录

第1章不确定频繁模式挖掘概述1

1.1不确定数据挖掘1

1.2不确定频繁模式挖掘研究背景2

1.3相关工作5

1.3.1完整的频繁项集挖掘6

1.3.2频繁闭项集挖掘8

1.3.3频繁项集挖掘9

1.3.4Topk频繁模式挖掘10

1.3.5近似频繁模式挖掘11

1.4研究内容与本书贡献12

1.4.1研究内容12

1.4.2本书贡献13

1.5本书结构15第2章不确定频繁模式挖掘技术17

2.1数据不确定性的原因17

2.2可能性世界理论和概率数据库18

2.3不确定频繁项集挖掘19

2.3.1基于概率数据的不确定数据模型20

2.3.2基于水平数据格式的挖掘方法21/智能数据挖掘——面向不确定数据的频繁模式目录/2.3.3基于垂直数据格式的挖掘方法22

2.4不确定序列模式挖掘24

2.4.1不确定序列数据模型25

2.4.2不确定序列模式挖掘技术28

2.5不确定频繁子图模式挖掘32

2.5.1不确定图数据模型33

2.5.2不确定频繁子图模式挖掘技术37

2.6不确定高效用项集挖掘41

2.6.1不确定高效用数据模型41

2.6.2不确定高效用项集挖掘技术44

2.7不确定加权频繁项集挖掘46

2.7.1不确定加权数据模型47

2.7.2不确定加权频繁项集挖掘技术48

2.8本章小结52第3章Eclat框架下基于支持度的双向排序策略53

3.1基于垂直数据格式的Eclat算法53

3.1.1存在的问题53

3.1.2支持度性质及证明54

3.2基于支持度排序的双向处理策略56

3.2.1支持度升序排列阶段56

3.2.2支持度降序排列阶段57

3.2.3频繁项集挖掘中的双向处理策略57

3.2.4BiEclat算法58

3.2.5BiEclat算法示例59

3.3概率频繁模式挖掘中的双向排序策略61

3.3.1基于概率数据的不确定频繁模式挖掘61

3.3.2基于概率频度的双向排序策略64

3.4实验结果及分析65

3.4.1实验数据集65

3.4.2实验结果分析67

3.5本章小结76第4章Eclat框架下的概率频繁项集挖掘算法77

4.1概率频繁项集挖掘相关概念77

4.2概率频繁项集精确挖掘算法79

4.2.1相关工作80

4.2.2Tidlist数据结构81

4.2.3概率频度计算模块81

4.2.4UBEclat算法83

4.3概率频繁项集近似挖掘算法85

4.3.1近似挖掘理论基础85

4.3.2近似挖掘相关工作86

4.3.3NDUEclat算法88

4.4实验结果及分析89

4.4.1实验数据集90

4.4.2正态分布数据集中的性能分析90

4.4.3长尾分布数据集中的性能分析92

4.5本章小结95第5章基于粗糙集理论的近似频繁模式挖掘96

5.1容错数据中的频繁模式挖掘理论96

5.1.1容错数据模型96

5.1.2容错数据的挑战96

5.1.3粗糙集理论及相关概念99

5.1.4粗糙集理论在数据挖掘中的应用99

5.2面向容错数据的近似频繁模式挖掘101

5.2.1事务信息系统构建阶段101

5.2.2等价类生成阶段103

5.2.3下近似和上近似的定义104

5.2.4近似频繁模式挖掘阶段106

5.2.5精确度和覆盖度的定义108

5.3实验结果及分析109

5.3.1模拟数据集上的性能分析109

5.3.2真实数据集上的性能分析111

5.4本章小结115第6章在传统中医药数据集中挖掘Topk近似频繁闭模式116

6.1相关工作116

6.1.1面临的问题117

6.1.2近似频繁模式挖掘算法118

6.2基于粗糙集理论的Topk近似频繁闭模式挖掘123

6.2.1事务类划分阶段124

6.2.2核模式产生阶段126

6.2.3Topk近似频繁闭模式挖掘阶段129

6.3实验结果和分析131

6.3.1基于支持度的聚类算法性能分析131

6.3.2Topk近似频繁闭模式挖掘算法性能分析135

6.3.3实验结果分析138

6.4本章小结138第7章总结和展望140

7.1本书总结140

7.2研究展望141参考文献143

本书得到国家自然科学基金（No.61672329, No.61373149, No.61773246）的资助This monograph was sponsored by National Natural ScienceFoundation of China (No.61672329, No.61373149,No.61773246)前言大数据时代悄然到来，数据挖掘技术正面临着前所未有的机遇和挑战。作为数据挖掘领域的重要研究课题，频繁模式挖掘和关联规则发现受到持续而广泛的关注，并且涌现大量经典理论、高效算法和新兴应用领域。挖掘频繁项集是关联规则发现中的关键技术和步骤，其决定了关联规则发现过程的总体性能，目前已广泛应用于市场销售、文本挖掘和公众健康等领域。在实际应用中，由于技术手段有限、测量设备误差、通信开销限制和用户隐私保护等诸多因素的影响，获得的原始数据往往存在不确定性。同时，受到主客观条件的限制，频繁模式挖掘过程中也会带来一系列的不确定性，这些不确定性在挖掘过程中不断传播和积累，可能导致挖掘出的知识与真实结果之间存在较大误差甚至毫无意义。传统的挖掘方法未将这些因素考虑进去，只简单地认为挖掘出的知识一般都是有用的和确定的，致使传统的频繁模式挖掘方法在处理不确定数据时面临着得到的挖掘结果异常却难以解释的窘态。这显然是不科学和不妥当的。因此，针对不确定频繁模式挖掘的研究显得尤为重要，并日益受到广大研究人员的关注。本书主要针对两类典型的不确定数据(即概率数据和容错数据)进行概率频繁模式挖掘和近似频繁模式挖掘的研究，并应用在中医药诊疗数据环境下，实现基于不确定数据的高效频繁模式挖掘。本书的主要工作和成果总结如下。(1) 研究了实际应用中常见的各种不确定数据，分析了数据不确定性产生的原因。综述了目前常用的不确定数据模型和主要的不确定频繁模式挖掘算法，包括不确定频繁项集挖掘、不确定序列模式挖掘、不确定频繁子图挖掘、不确定高效用项集挖掘和不确定加权频繁项集挖掘技术，总结了各种不确定频繁模式挖掘技术的优缺点，并指出未来可能的发展方向。/智能数据挖掘——面向不确定数据的频繁模式前言/(2) 针对概率数据中垂直格式的数据表示形式，提出一种基于Eclat框架的概率频繁项集精确挖掘算法(UBEclat)。首先，对于采用垂直数据格式的概率数据，设计了一种适用于Eclat框架，旨在提高算法执行效率的双向排序策略；然后，基于概率频度的定义，提出采用分而治之方法的概率频繁项集精确挖掘算法。在基准数据集和真实数据集上的对比实验表明，UBEclat算法能够依据支持度的概率分布，准确挖掘出所有概率频繁项集。这为有效解决概率频繁项集的精确挖掘问题提供了新的思路。(3) 针对概率频繁项集精确挖掘算法执行效率较低、运行时间过长的问题，基于概率数据的可能性理论，提出一种高效的概率频繁项集近似挖掘算法(NDUEclat)。结合Eclat框架和近似方法的优势，NDUEclat算法采用分而治之的方法，应用大数定律优化挖掘过程，改进了频繁项集挖掘的效率。在基准数据集和真实数据集上的多组对比实验也验证了该算法具有良好的挖掘性能。目前，这也是个基于支持度的概率分布，在垂直数据格式的概率数据中高效挖掘不确定频繁项集的近似算法。(4) 针对NP|hard类的容错频繁模式挖掘问题，提出一种将容错数据库映射为事务信息系统、基于粗糙集理论挖掘近似频繁模式的新方法。依据挖掘出的频繁项目确定决策表中的决策属性；基于粗糙集理论中上近似和下近似概念，确定近似频繁模式的匹配程度。在基准数据集和真实数据集上进行的对比实验证实了该方法在挖掘的准确率指标上，比以往方法有更好的性能表现。显然，基于粗糙集理论的近似挖掘方法为有效提高近似频繁模式挖掘的准确性和适用性提供了新的思路。(5) 以减少敏感参数设置的影响、提高挖掘效率的同时保证实际挖掘结果的可用性为目的，研究了基于容错数据的粗糙集理论，提出一种挖掘近似频繁闭模式的新模型。新模型主要由三部分组成: 用聚类算法完成数据预处理；对同一类中的事务依据粗糙集理论进行属性约简生成核模式；将核模式作为初始种子构建等价类，用分而治之的方法挖掘近似频繁闭模式。传统中医药数据集的实验结果表明，该模型可以更精准地表达近似频繁模式，有利于实现基于中医诊疗应用的知识发现。综上所述，本书针对概率数据中如何提高频繁模式挖掘的效率、如何屏蔽容错数据中因数据表达不准确而对挖掘结果造成的影响，以及如何确定容错率以获得有意义的挖掘结果等问题，从数据库的特点和数据的表示方式、模式挖掘的类型、具体挖掘技术的选择等几个不同的角度提出相应的解决方案，并通过实验验证了它们的有效性。本书的工作可以为今后面向不确定数据的频繁模式挖掘研究提供帮助。本书是作者在密切跟踪该技术领域研究成果的基础上总结而成，是一本全面论述不确定频繁模式挖掘方法的著作。本书图文并茂，深入浅出，可读性强，并将理论与实践有机结合，以期为读者进一步学习、研究和应用打下基础。不确定频繁模式挖掘是一个复杂的热点问题，本书在撰写的过程中参考了大量国内外相关文献，直接引用的有数百篇。在此，向相关作者表示衷心的感谢。本书的出版得到国家自然科学基金(No.61672329, No. 61373149, No.61773246)的资助。另外，本书的编写还得到山东师范大学郑向伟教授、山东中医药大学附属医院阎小燕教授的大力支持，在此对这些教授的鼓励和帮助表示衷心的感谢。本书即将出版之际，特别感谢山东师范大学、山东中医药大学附属医院的相关专家和学者提出的宝贵意见，感谢清华大学出版社的编辑为本书的顺利出版而付出的辛勤劳动。限于作者的学识水平，书中不妥之处在所难免，恳请广大读者不吝赐教。
作者2018年4月于济南

第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}∪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}时，若采用字母表顺序(即Asup(Ai) do 5:  R=Ai∪Aj; 6:  tidlist(R)=tidlist(Ai)∩tidlist(Aj); 7:  If |tidlist(R)|≥min_sup8:  S=S∪{R};Ti=Ti∪{R}; 9:  end if10: end for11: while Ti≠ do find_ candidate_frequent_itemsets;12: end for3.2.5BiEclat算法示例BiEclat算法的优势可以通过下面的例子清楚地展示出来。考虑图3.1左侧所示图书销售数据集。数据集中包含八个不同的项目{A,C,D,T,W,F,H,K}，存在六位顾客分别购买了这八位作者的著作，该数据集用水平数据格式表示。图3.1右侧显示的是至少出现在两次购书事务中的图书项目，即支持度大于等于小支持度阈值的所有频繁项目(min_sup=2)。事务数据集显示为按支持度降序排列的垂直数据格式。图3.1事务数据库中的数据表示按照步的输出结果，将单元素频繁项集中的各原子项目按支持度升序排列为D,T,A,W,C。接着合并原子集合{D,T}和{D,A}，目的是产生候选项集{D,T,A}并检验其是否为3频繁项集。若项集{D,T,A}为频繁的，则进一步扩展项集{D,T,A}与{D,T,W}，生成4项集{D,T,A,W}。sup({D,T,A})=sup({D,T}∩{D,A}∩{T,A})=sup({5,6}∩{4,5,6}∩{1,3,5,6})=sup({5,6})=2≥min_supsup({D,T,W})=sup({D,T}∩{D,W}∩{T,W})=sup({5,6}∩{2,4,5}∩{1,3,5})因为sup({5,6}∩{2,4,5})=1