模式挖掘韩萌 pdf下载

模式挖掘
	曾用价	59.00
	出版社	科学出版社
	版次	1
	出版时间	2018年06月
	开本	16
	作者	韩萌
	装帧	平装
	页数	112
	字数	150000
	ISBN编码	9787030578549

本书详细介绍面向数据流模式挖掘的理论和方法。本书主要内容包括四部分：第1和第2章介绍数据库和数据流模式挖掘的相关知识；第3章介绍基于滑动窗口模型和时间衰减模型的闭合频繁模式挖掘算法的研究与实现过程；第4章介绍基于多支持度的连续闭合序列模式挖掘算法的研究；第5章介绍基于约束闭合模式的决策树分类算法的研究与实现过程。每章都有相关算法的实验证明，供读者更好地了解本书内容。


目录
前言
第1章 绪论 1
1.1 研究背景和意义 1
1.2 研究现状 2
1.2.1 数据挖掘 2
1.2.2 数据流模式挖掘 3
1.2.3 数据流分类 5
1.2.4 数据流聚类 7
1.3 主要研究内容 8
1.4 本书结构 9
第2章 模式挖掘研究相关工作 11
2.1 相关概念 11
2.2 模式类型 13
2.2.1 闭合频繁模式 13
2.2.2 *大频繁模式 15
2.2.3 top-k频繁模式 16
2.2.4 约束频繁模式 16
2.3 数据流挖掘方法 17
2.3.1 窗口方法 17
2.3.2 衰减方法 18
2.3.3 模式增长方法 20
2.3.4 近似方法 22
2.3.5 假阳性与假阴性方法 23
2.4 算法评价准则 24
2.5 模式度量准则 24
第3章 基于时间衰减模型的闭合模式挖掘算法 26
3.1 引言 26
3.2 背景知识 27
3.2.1 闭合模式选择方法 27
3.2.2 新近事务处理方法 28
3.2.3 频繁与临界频繁闭合模式 28
3.3 基于均值衰减因子的挖掘算法 29
3.3.1 均值衰减因子研究 30
3.3.2 算法设计 31
3.3.3 实验方式及其结果分析 34
3.4 基于高斯衰减函数的挖掘算法 41
3.4.1 高斯衰减函数研究 41
3.4.2 算法设计 44
3.4.3 实验方式及其结果分析 46
3.5 本章小结 49
第4章 基于多支持度的连续闭合模式挖掘算法 51
4.1 引言 51
4.2 连续闭合模式的研究 52
4.2.1 连续闭合模式 52
4.2.2 基于多支持度的连续模式 54
4.3 算法设计 56
4.4 实验方式及其结果分析 60
4.5 本章小结 64
第5章 基于约束闭合模式的决策树分类算法 65
5.1 引言 65
5.2 背景知识 66
5.2.1 实例数据流的频繁模式 66
5.2.2 数据流分类方法 67
5.2.3 分类过程中概念漂移检测方法 71
5.3 算法设计 73
5.3.1 约束模式的研究 74
5.3.2 约束闭合模式挖掘算法 76
5.3.3 基于模式的决策树算法 78
5.4 实验方式及其结果分析 83
5.4.1 学习评估方式 83
5.4.2 实验数据 83
5.4.3 实验表现 85
5.5 案例分析 90
5.5.1 航空数据与待解决问题 90
5.5.2 数据预处理 92
5.5.3 关联规则设计与应用分析 94
5.5.4 分类结果分析 97
5.6 本章小结 102
第6章 总结与展望 103
6.1 研究工作总结 103
6.2 未来工作展望 104
参考文献 106


第1章 绪论
　　智能终端、互联网及无线传感网络的发展带来了一个大数据的时代，使得数据产生的速度越来越快，信息量呈现爆炸式增长。迅速膨胀的数据促使产生了具有重要意义和广阔发展前景的数据流模型（data stream model）。数据流成为未来数据发展的一个主要趋势，而从数据流中挖掘有用的知识得到广泛的重视。本书将对数据流模式挖掘相关技术及应用进行研究。
　　1.1 研究背景和意义
　　数据流模型广泛应用于社会生产和生活的各个领域，它是未来数据发展的一个主要趋势。它主要是由金融行情、网络监控和流量管理性能测量，网络跟踪和个性化的日志记录或点击流，制造过程，传感器数据源，电信，电子邮件等产生的。从数据流中挖掘有用的知识得到广泛的重视。数据流的主要特征是有序的、快速变化的、海量的和潜在无限的。数据流模型的特点决定了数据流挖掘算法与传统的数据库的挖掘技术有显著的区别。由于存储容量的有限性，挖掘过程中不可能完整地保存全部数据流元素。鉴于数据流的高速性和连续性，数据流算法应是动态增量的，也必须是高时空效率的。现有的数据库挖掘技术已不再适合数据流环境。因此，数据流环境下的数据挖掘研究具有更大的机遇和挑战性[1，2]。
　　模式挖掘是数据挖掘的热点问题，已被广泛地应用在商业、企业、过程控制、政府部门及科学研究等领域。频繁模式挖掘可以很好地概括数据流中有用的实例信息，找到有区别力的模式用于数据流的分类、聚类、趋势预测和异常检测等。同时，它不受噪声数据的影响。
　　数据流的一个重要特征在于其可能存在概念漂移现象，即历史事务数据可能与当前信息摘要无关甚至是有害的。概念漂移（concept drift）是指由于数据流中上下文的变化而引发的隐含目标概念变化，甚至是根本性变化的现象。概念漂移具有较强的时间性，数据在一定的时间内反映的只是当时的概念，但随着时间的推移，可能会改变数据中的概念。因此，对该类数据流挖掘时除了需要考虑空间和时间的限制，还需要进行概念漂移的检测和处理。本书面向数据流，研究其模式挖掘的主要理由在于以下几方面。
　　（1）数据流中的概念漂移问题是研究的热点，虽然已有大量研究工作及成果，但是缺少有效的概念漂移检测及处理方法。本书将对数据流模式挖掘过程中和数据流分类模型学习中的概念漂移问题分别进行研究，目的是提高模式挖掘的完整性和准确性，以及分类的正确率。
　　（2）大规模数据流模式挖掘面临的一个主要问题是挖掘的模式数量巨大，其中存在大量无用的模式。当长事务或*小支持度阈值低时，这个问题尤其严重。压缩模式和约束模式可以用于选择满足不同要求的有趣模式，同时能够有效地减少模式的数量。为了得到有趣的模式集合，本书研究闭合频繁模式和约束频繁模式。为此设计的剪枝策略会降低算法执行消耗的内存空间，且得到的有趣模式集合更加有利于用户的使用。
　　（3）数据流中包含大量的数据，这些数据可能包含大量的冗余信息甚至是噪声，而模式挖掘可以去除数据中的冗余信息且不受噪声的影响。因此，挖掘有趣的、频繁的和有区分力的模式，可以用于有效地分类。基于模式的分类具有更高的准确性，并且可以很好地解决缺损值的问题。有关基于模式的决策树分类模型的研究较少，本书将对此进行研究。
　　1.2 研究现状
　　本节介绍数据挖掘的主要方法，以及数据流挖掘的相关内容，包括数据流分类、数据流聚类和数据流频繁模式的国内外研究现状。
　　1.2.1 数据挖掘
　　在信息社会，提取知识是很重要的任务。而知识革命发展面临的挑战已经改变为如何创造和使用无限的知识。数字时代产生了海量的数据，需要采用有效的计算方法来处理它们。数据挖掘（datamining，DM），又称为知识挖掘（knowledge discovery in databases，KDD），它的主要目的是从大规模数据库中获取知识或信息，即数据挖掘是从大量数据中提取或挖掘出有效的、隐含的、先前未知的并具有潜在价值模式的非平凡过程。数据挖掘的任务主要包括关联分析、分类、聚类、序列分析、回归、偏差检测、预测等。
　　数据挖掘过程大致可以分成三个阶段：数据预处理、数据挖掘、结果评价和表达。数据预处理主要是对大量数据进行选择、净化、推测、转换、缩减等，来消除在挖掘过程中无用的数据。数据预处理阶段非常重要，它影响到数据挖掘的效率和准确度。数据挖掘阶段的工作首先是根据不同的任务选择相应的挖掘实施算法，例如，分类、聚类、关联规则、粗糙集、神经网络、遗传算法等，然后进一步对数据进行分析，从而得到知识的模型。结果评价和表达阶段主要是从所有的知识模式模型中发现更加有意义的模型。
　　数据挖掘的主要方法可以分成四类。
　　（1）分类分析方法。分类或回归模型可以区分不同类别中的个体并且可以用来预测个体的类别。常用的分类技术有决策树方法、支持向量机方法、基于规则的分类方法、贝叶斯分类方法、集成分类方法、神经网络方法、*近邻分类方法；回归模型一般分为线性回归和非线性回归，经过适当的变换，很多非线性模型都可以转化为线性回归模型进行解决。
　　（2）聚类分析方法。聚类是将数据分类到不同的类或者簇这样的一个过程，所以同一个簇中的对象有很大的相似性，而不同簇间的对象有很大的相异性。聚类分析以相似性为基础，这样可以把样本空间分成多个簇。聚类算法的选择由数据类型、聚类目的和应用决定。聚类分析的算法主要可以分为划分法（partitioning methods）、基于密度的方法（density-based methods）、基于网格的方法（grid-based methods）、基于模型的方法（model-based methods）以及层次法（hierarchical methods）等。
　　（3）关联分析方法。关联分析就是从大量数据中发现项集之间有趣的关联和联系。关联规则挖掘需要考虑两个步骤：一是利用模式支持度（support）挖掘所有的频繁模式；二是利用置信度（confidence）找到所有规则。这个问题的核心就是怎样高效地挖掘出所有的频繁模式，即频繁模式挖掘问题。关联分析的算法主要有先验算法、基于划分的算法、FP树算法等。
　　（4）异常检测方法。异常检测（anomaly detection）也称偏差检测，它的假设是入侵者活动要异常于正常主体的活动。根据这一假设首先建立主体正常活动的活动简档，将当前主体的活动状况与活动简档相比较，当违反其统计规律时，认为该活动可能是入侵行为。异常检测的难题在于如何建立活动简档以及如何设计统计算法，从而不把正常的操作作为入侵或忽略真正的入侵行为。异常检测的方法主要有基于邻近度的技术、基于模型的方法、基于密度的技术等。
　　关联规则挖掘是数据挖掘领域中的一个重要的研究方向，其重要工作是挖掘频繁模式集合。根据处理事务数据集的类型不同，分为静态数据集上的频繁模式挖掘和动态数据流上的频繁模式挖掘。
　　1.2.2 数据流模式挖掘
　　数据流作为一种新型数据模型广泛出现在多种应用领域。与传统的数据集不同，数据流的特点在于按时间顺序的、快速变化的、海量的和潜在无限的。数据流主要产生于网络，如Web点击流分析、网络日志、交通流量监控与管理、电力供应管理与预测、电信数据管理、金融服务和商业交易管理与分析等。专用网络同样产生大量的数据流，如基于卫星的高分辨率测量地球测地学数据、雷达衍生的气象数据、连续的大型天文光学、调查红外线与无线电波长和大气辐射测量等。这些数据流是海量的、高速流动的、快速变化的和潜在无限的，每天产生百万数据项，如WalMart记录2亿条记录、Google处理10亿条搜索、AT&T处理27.5亿条呼叫记录等。
　　数据流挖掘目前成为一项新兴的智能信息处理技术，引起了广大研究工作者的关注，不论在国内还是国外都得到了广泛重视，许多文献对该领域的研究进展进行了报告。数据流模型不同于传统的数据库，它具有一定的约束，具体如下所示。
　　（1）数据流具有无限性，即包含的数据个数是无限的。因此，使得存储受到限制，只能存储概要信息，其余信息被丢弃。
　　（2）数据到达速度快，需要实时处理，处理后即被丢弃。
　　（3）产生的数据项的分布会随着时间而改变，因此历史数据可能无关甚至有害。
　　（4）项集的组合爆炸会加剧挖掘任务困难程度[3]。
　　从挖掘功能的角度考虑，目前数据流的挖掘主要包括数据流模式挖掘、数据流分类、数据流聚类和数据流查询等技术。由于数据流模型的特性，对其进行挖掘时需要考虑其时空约束，还要考虑数据变化而带来的概念漂移问题。设计数据流挖掘算法时需要自适应概念的变化，应是增量更新处理过程。
　　频繁模式（frequent patterns）或频繁项集（frequent itemsets）是指在数据集合中出现次数多于用户定义*小支持度阈值的项集。频繁模式挖掘可以看作许多数据挖掘任务的基础，如关联分析、相关性分析、序列挖掘、分类和聚类等。
　　对数据流进行频繁模式挖掘应用范围较广，可用于检测异常值、极端事件、欺诈、入侵、不寻常或异常的活动、监控复杂的相关性、跟踪趋势、支持探索分析和执行复杂的任务等。如对网络流量、Web服务器日志和点击流挖掘，可以用于设计查询系统，推荐系统，对用户行为进行预测等。对电信数据、金融、医学和零售数据分析，可以进行用户身份或行为隐私保护、异常检测等。对电子商务应用，股市监管和房地产数据分析，可以处理相关交易。对数据流进行结构挖掘可以进行用户行为的语义分析和社会网络分析等。对传感器网络的数据分析，可用于设计传感器监控系统，基于位置的服务，以及医疗诊断系统；可以用于分析数据，找出有趣的模式，如拥堵或道路危害分析、队列末尾监测和交通状态估计。对无线信号网络的管理可以用于研究分布系统与数据库系统。
　　早期的频繁模式挖掘方式是采用先验方法[4]生成和测试候选集合，但是这样生成候选集合的代价有点高，尤其是存在长模式或大量模式时。为了解决这个问题，Fp-growth[5]算法使用了频繁模式树（FP-tree）结构存储压缩的、关键的频繁模式信息。把一个大的数据库压缩成一个紧密的小的数据结构，避免了重复扫描数据库。H-mine[6]算法中设计了一个使用超链接的数据结构，这个结构在算法执行过程中会动态调整链接。当数据集合变得密集时，会在挖掘过程中动态地创建FP-tree结构。该算法的优势在于使用了非常有限的和准确预测的内存空间，并且执行速度快。PrePost[7]和PrePost+[8]算法在FP-tree编码前缀树的基础上设计了一种新的结构N-list。相同前缀的事务会在N-list中共享相同的节点，使得该结构紧凑。PrePost的优势还在于它在某些情况下可以不产生候选项集，利用N-list的单路径属性找到频繁模式。N-list的不足在于需要对树中的每个节点进行前序和后序编码。FIN[9]在N-list的基础上设计了一种仅需要前序（或后序）编码的新数据结构Nodesets，相比而言可以减少一半的内存。这些方法主要用于挖掘静态数据集合中的频繁模式，由于需要多次扫描数据库，因此不能直接用于数据流挖掘。
　　挖掘频繁模式是数据挖掘的热点问题，在传统数据库中挖掘频繁模式这个问题已经被广泛地研究和应用。然而，在数据流环境下挖掘频繁模式给研究者带来更大的机遇和挑战。数据流中挖掘的模式类型主要包括：频繁序列[10-12]、高效用[13，14]、子图（subgraphs）[15，16]、episode[17]和频繁项集等。
　　近年来，研究者研究数据流中挖掘频繁模式的方法。算法StickySampling采用统计抽样技术来估计项集的支持数[18]。算法FTP-DS采用基于回归的方法找到数据流中的时间频繁模式[19]。但是，这两个算法没有给定项集支持度允许的误差上限。为了限定假阳性错误的上限，Counting给定了错误参数来找数据流中的频繁模式[18]。为了降低内存消耗，设定内存中临时存储事务，而项集支持度存储在二级存储器中。同样的还有estDec算法，它为了提高内存的使用，采用前缀树存储具有重要意义的模式而不是全部的模式[20]。用户给定意义阈值，支持度超过此阈值的就认为是有重要意义的。由于内存中存储的树结构会随着模式的增加而不断增长，当树的大小超过定义的内存空间时会停止生长，会影响模式挖掘的准确性。estDec+在estDec基础上进行改进，提出一种压缩树结构来挖掘数据流中的频繁项集，目的是降低内存消耗[21]。这些算法使用的是用户定义的边界，都是假阳性算法。FDPM是一种假阴性算法，它挖掘数据流中满足误差界和*小支持度的频繁模式[22]。它得到的结果集中模式数量相比会大幅度降低，但是可能会丢失一些频繁模式。DFP-SEPSF使用一种动态频繁模式树挖掘高维数据流中的频繁模式，这些模式用于捕获类的变化[23]。
　　1.2.3 数据流分类
　　数据流分类模型主要分为单分类模型和集成分类模型。单分类模型技术维护和增量更新单个分类模型，有效地对概念漂移做出回应。集成模型需要比单个模型相对简单的技术更新概念，且同样有效地处理概念漂移。提出处理概念漂移时，集成分类器优于单个分类器：它们易于扩展和并行，通过剪枝整合中的某些部分可以快速适应漂移，它们可以得到更准确的概念描述。并且，通常基础分类器的训练速度要高于单一模型的更新速度，因此也更加适合处理高速产生的数据流。由于数据流的特征，因此对其进行处理时采用的主要是增量算法[24]。增量算法是指按照顺序一个接一个（或一批接一批）地处理实例，每次处理一个（一批）实例后更新模型。
　　数据流分类方法包括神经网络[25，26]、支持向量机[27，28]、关联/分类规则、决策树等。关联规则挖掘是一种基于频繁模式的分类方式，在传统数据库中得到广泛应用。近年来，出现了针对数据流的规则分类算法。如CAPE算法是*早的基于频繁模式的规则分类算法，用来处理数据流，它利用衰减窗口方法处理概念漂移问题，取得了比较好的实验结果[29]。CBC-DS算法采用闭合频繁模式用于挖掘类关联规则，使得算法具有较高的效率[30]。PNRMXS算法发现XML数据流中的正、负关联规则[31]。Esper算法在Aprior和FPGrowth算法的基础上发现数据流中的关联规则并进行相关分析[32]。该算法对不同特征的数据流使用了滑动窗口模型和倾斜窗口模型进行规则挖掘。AMRules算法用于发现数据流中的规则来解决回归问题[33]。规则的前件是属性值的条件连接，后件是属性值的线性组合。它设计一种策略检验数据的改变，并通过剪枝规则集合对改变做出反应。FRBCs在FPGrowth算法的基础上进行模糊扩展，挖掘模糊频繁模式，从而生成模糊关联分类模型[34]。其中模糊的项是由离散化输入变量和从这些离散间隔中定义强模糊划分产生的。MapReduce在FPGrowth算法的基础上进行分布式设计挖掘分类关联规则[35]。一旦挖掘出分类关联规则，则进行分布式规则剪枝。得到的规则集合可以用于分类未标记的模式。
　　决策树模型被广泛用于创建分类器处理数据流，原因在于决策树模型类似于人类的推理很容易被理解[36]，其中基于Hoeffding的决策树算法是从数据流中学习树的*受欢迎的方法之一，如快速决策树（very fast decision tree，VFDT）[37]、概念自适应快速决策树（concept-adapting very fast decision tree，CVFDT）[38]、VFDTc[39]、模糊模式树（fuzzy pattern trees）[40]、哈希树[41]、Hoeffding选择树（Hoeffding option trees，HOT）[42]、Hoeffding自适应树（Hoeffding adaptive tree，HAT）[43]、自适应Hoeffding选择树（adaptive Hoeffding option tree，AdoHOT）[44]和自适应大小Hoeffding树（adaptive-size Hoeffding tree，ASHT）[44]等。VFDT是针对数据流挖掘环境建立分类决策树的方法。它通过不断地将叶节点替换为分支节点而生成，即在每个决策节点保留一个重要的统计量，当该节点的统计量达到一定阈值时，则进行分裂测试。其*主要的创新是利用Hoeffding不等式确定叶节点变为分支节点所需要的样本数目与分裂点。该算法仅需扫描一次流数据，具有较高的时空效率，且分类器性能近似于传统算法生成的分类器。不足在于不能很好地处理概念漂移问题。CVFDT对VFDT进行了扩展以快速解决概念漂移数据流的分类。其核心思想是当新子树分类更准确时，用新子树替换历史子树。它维