2023学年完整公开课版数据流挖掘

数据流挖掘学习目标2知识目标●数据平稳分布的分类方法●数据带概念漂移分类方法能力目标●了解数据流漂移挖掘研究现状●掌握数据流挖掘分类方法●掌握数据挖掘之数据流处理学习任务3数据流挖掘分类方法数据流漂移分类研究现状数据挖掘之数据流处理过滤数据4数据挖掘之数据流处理数据流挖掘分类方法目录数据流挖掘分类方法5在数据流挖掘分类方法的应用上有：电子邮件的区分、个性化网站、电脑入侵检测等，因为无法在一个分类器建立完成前获取到所有适合用来做训练样本的数据，数据流挖掘的增量式方法一般都假设取得的样本是由平稳分布的数据中所获得，但现实世界中，新数据的概念可能会随着时间的延续而与历史数据产生改变，定义为St={(x，y)|y=f(x)+st}，t=1,2,…代表数据集合是由伴随着时间变化参数的函数所产生的，以致相同的条件可能会产生不同的行动，这种概念随着时间延续而改变的情形，称为概念漂移。6VFDTVFDT(veryfastdecisiontree)是一种基于Hoefiding不等式建立决策树的方法，它通过不断地将叶节点替换为决策节点而生成其中每个叶节点都保存有关于属性值的统计信息，这些统计信息用于计算基于属性值的测试当一个新样本到达后，在沿着决策树从上到下遍历的过程中，它在树的每个节点都进行划分测试，根据不同的属性取值进入不同的分支，最终到达树的叶节点当数据到达叶节点后，节点上的统计信息就被更新，同时该节点基于属性值的测试值就被重新计算，如果统计信息计算显示测试满足一定的条件，则该叶节点变为决策节点新的决策节点根据属性的可能取值的数目产生相应数目的子女叶节点决策节点只保存该节点的划分测试所需要的信息。7VFDTcVFDT只是在有足够多样本情况下才将一个叶节点转换为决策节点，这通常需要较多样本为分类测试样本，大部分分类策略只是用到类分布信息，而没有用到属性值信息，这显然只用到了可用信息的一部分，只是对样本分布的粗略近似，另一方面贝叶斯分类不仅考虑类的前验分布，而且考虑在给定分类的情况下属性值的条件概率，通过这种方"法可以更多地利用每个叶节点的可用信息此外，贝叶斯本身就是增量式的，在处理不同类型的数据和缺值数据方面都有好处。VFDTc提出了解决连续属性的方法，但是它在划分点的选择上将考虑所有的连续属性的可能取值"这带来了很大的开销Fayyad等人已经证明属性的两个紧邻值只有取不同的分类，其中间点才可能是最佳划分点，这在VFDTc中并没有得到应用。8NIPDTSmallClassHistograms。主要由离散属性的类，直方图构成离散属性的元素数目不会太多因此每个属性的类直方图都不会太大此外，对于那些属性取值小于指定数目的连续属性也维持一个小尺寸类直方图。

对于连续属性，在处理时的一个问题就是备选划分节点的数目过多，因此选择最佳划分节点就非常耗时计算资源，针对VFDT中处理了离散属性的问题。NIP方法的基本做法就是将连续属性取值划分为不同的区间，然后利用统计测试对这些区间进行剪枝任何时刻，每个区间或者被剪枝或者保持完整如果一个区间不可能包含最佳划分节点则把该区间剪枝掉、完整区间是指没有被剪枝的区间。对于连续属性，为了选择最佳划分节点，NIP方法为每个节点保存下列数据集合。9NIPDTConciseClassHistograms。对于有很多不同取值的连续属性将其取值划分成多个区间对于连续属性的每个区间，精确类直方图用于记录该区间范围内各个类别的样本出现的次数。DetailedInformation。详细信息根据效率分成两种方式:第1种方式是区间的样本数目直方图当样本数目很多而连续属性的取值相对较小时，这种方式比较有效:第2种方式只是简单地保存每个分类的样本数目，而不需要处理剪枝掉的区间中的详细信息以获取最佳划分节点这种方法的好处是不需要处理剪枝掉的区间内的详细信息，因此可以在少精下很好地减少执行时间。10IFDTIFDT(incrementalfuzzydecisiontrees)是由Guetova等人提出的一种增量式模糊决策树数据流分类方法它综合了决策树和模糊逻辑的优点同时它是增量式的，很好地满足了数据流分类的要求首先它生成决策树，这就很好地利用了决策树的特点:其次，它使用模糊逻辑，这非常符合人们日常的思维习惯:此外它是增量式的这为分类器提供了学习新数据的能力算法综合了模糊决策树的决策能力和决策树在经典逻辑下的增量算法，并且能多和非增量算法产生相同的结果。11数据带概念漂移分类方法数据流中的概念流可以通过以下三种方式进行处理：基于窗口的方法、基于重量的方法以及集成分类。基于窗口的方法是通过选择一个固定的或动态的滑动窗口构建一个分类模型，在分类精度的基础上调整窗口的大小（Lee，2009）。在以重量为基础的方法上，每个训练实例被分配一个权重。最流行的演变技术来处理概念漂移的数据流是使用集成分类（分类器的组合），几个输出分类器的组合是用来确定最终的分类，这通常被称为融合规则。另外，在每个时间点的个体输出分类器上分配权重，权重通常为一个历史表现函数，通过使用交叉验证过去或估计的函数。12数据流概念漂移挖掘研究现状为了从大量来自真实世界的复杂数据中提取最有用的信息和知识，在过去十年，各种数据挖掘算法已经被提出和发展。Masud等（2011）建议在真正的标记新类型的实例之前应使用分类器来检测新的类别。为了确定每个个体是否属于某一新类型，其分类模型有时需要收集更多的测试实例来发现数据之间的异同。Polikar（2011）也推出了可以渐进式学习流的分类器集合体，并命名为学习+NSE方法，通过当前和过去的环境动态加权多数表决技术结合这些分类可以调整各个分类时间的准确率。Song（2010）提出了一种基于关联规则的关联分类算法的数据流，其工作宗旨是发现各项集之间的关系，并从输入的数据集中提取一套完整的频繁模式。13在数据挖掘和机器学习领域中的数据流分析和挖掘是一项具有挑战性的研究，它最近受到许多计算智能研究人员的关注（Holmes，2012）。数据流分类是提取知识和连续数据点信息的方法（Read，2010）。在数据流中的数据是随着时间的推移所产生的，并且不能由任何预先定义的顺序来控制。一个数据流与传统的静态数据或数据库相比有非常多元化的特点，包括：动态、无限、高维、有序、不重复、高速和时变（Zliobaite，2009年）。大多数现有的数据挖掘技术不能检测及在数据流环境中进行分类（Qin，2007），因而现有的挖掘模型会将这些分类新实例与类标签弄错（Biswas，2004）。因此，这样的数据流分类需要不断更新和再培训通过在线数据流中标记新来的数据。数据流概念漂移分类研究现状14

数据流查询的类型和处理策略：数据挖掘之数据流处理

固定查询：对前来的数据一直在执行查询和计算。即时查询adhoc：仅当一个查询操作提交时，才对数据进行计算查询计算问题的近似解，比精确解高效的多hash技术，对求解近似解非常有帮助151.

抽样统计带来的问题;2.

统计用户的重复查询问题;3.

抽样时，涉及概率的乘法定理要谨慎处理，因为抽样后的概率运行可能与全集下的概率运算结果完全不同;大数据流抽样带来的问题16大数据流抽样带来的问题解决方法：对用户进行抽样，而不是对每个用户的数据进行抽样。一般性的抽样问题：将某些字段看成关键字组合，并利用hash的a/b策略，即b个桶，a作为阈值，保留小于a的采样值。新问题：新用户出现，每个用户的样本规模不断变大，以至于抽样的数据都超出了分配的空间，如何处理？那么就设定新的阈值a-1，即降低阈值，并将hash值等于a的数据删除，这样可以提高效率，节省空间。17过滤指定规则的数据主要是指Bloom过滤器;Bloom过滤器组成部分：n位的数组；k个hash函数；m个待过滤的元素；则bloom过滤器的假阳的概率是：(1-e^(-km/n))^k推导：元素不能落入指定的位置的概率是(n-1)/n，那么m个元素，hash了k次，仍未落入指定位置的概率是(1-1/n)^(km)，即当n较大时，指定位置为0的概率近似于e^(-km/n)，为1的概率为1-e^(-km/n)。而假阳的概率，是k个hash函数产生的k个指定位置，都为1的概率：

(1-e^(-km/n))^k。过滤数据18如果对N位的二进制数据，统计1的个数，那么精确统计1的个数就需要只是O(N)的开销,当N大于内存的容量时，那么快速的求解这个问题，可以采用求近似解的策略。DGIM算法：(1)维护一个数据结构：将二进制分组，每组中1的个数是2的次幂，从