第一章 绪论
1.1 课题背景
随着电子信息技术在各个行业的应用，大量的流数据正在以前所未有的速度产生出来[1]，同时一种基于流数据特点的数据挖掘技术应运而生，即流数据挖掘技术。因为流数据挖掘有很大的科研价值和很大的商业应用前景，自从流数据挖掘技术被提出以来一直受到学界和产业界的极大关注[2]。流数据有海量性，快速性和潜在无限等特征[3,4]，所以不能用存储的方法来实现将其转换为静态数据挖掘的方式来实现挖掘的目的。同时，因为不能大量存储，在流数据的挖掘过程中只能对数据单次扫描。在对流数据的长期研究中，很多经典算法被提出，比如算法 Apriori[5]和 FP-Growth[6]是经典的频繁模式挖掘算法，CHARM[7]、CLOSET[8]、CLOSET+[9]、FCI-base-Fplink[10]、NPG_mining[11]和 D-Miner[12]用来挖掘闭合频繁模式，Top-KFP-growth[13]、ExMiner[14]、OExMiner[15]和 MTKFP[16]在挖掘 top-k 频繁模式上非常出色。但是这些算法多数是从基于静态数据挖掘技术的方法上改进而来的，他们虽然都尝试引入一个概要存储结构以节省存储空间来达到少数数据多次扫描的目的，但是因为流数据的一些特点使得这些算法的效率和效果并不理想。根据挖掘的应用和侧重点的不同，流数据挖掘划分为很多不同的领域，包括分类、聚类、频繁项集检测、离群点检测等。本文研究的内容属于频繁项集检测的范畴。频繁项集检测主要完成流数据中符合某种条件的项的组合，有很好的商业应用前景，如在购物篮分析、网络检测、消费者行为分析等的领域有非常广阔的应用前景。总之，在频繁项集检测领域还有很多可以深入研究的内容，这些研究具有深远的意义。
…………
1.2 国内外研究现状
因为流数据的海量性和实时性，现有的数据挖掘算法都是秉承了这样一个思想——将离“目前”最近的一些数据存到一个概要存储结构里，通常是树结构，以最大限度的容纳更多的数据，然后在存储的这些数据中进行数据挖掘。当然了，维持这个结构是算法比较关键的部分。为了实现这种“维持”，很多算法都采用一种叫做窗口的机制，可细分为滑动窗口机制、界标窗口机制和衰退窗口机制。下面将介绍这三个机制的基本原理，然后针对各自的优缺点提出自己的非窗口维持机制。而在内存中的存储方式大多为树的结构，因为树的结构可以最大限度的使用不同项集的共同前缀，这样就节省了内存。然而树又分为很多种，比如 MCFI-SW[17]、FPCFI-DS[18]、 MFCIDS_BD[19]和 Stream-Close[20]等。滑动窗口机制中算法只关心从当前到达的项集开始往后数到窗口长度位置的项集信息[22-24, 31-33]。当有新项集到达时，窗口向前滑动，原来窗口中最旧项集被移出窗口。算法旨在在维持的窗口大小的数据中进行有效的数据挖掘。从另一个角度看就是滑动窗口算法只看重新产生的数据，而流数据挖掘中有时候关注的并不仅仅是当前的数据所表达出来的信息而是总体的数据的波动性信息，滑动窗口在这个方面是有先天性缺陷的，并且因为受到存储容量的限制，窗口大小有限，这也直接影响了挖掘的效果。
…………
第二章 算法 PDB-FIM 背景知识概述
2.1 引言
本章阐述了流数据挖掘的背景知识，同时提供了算法 PDB-FIM 用到结论的正确性证明，包括流数据的近似正态分布属性证明，算法剪枝原理的说明及正确性证明，算法的完备性证明等。数据项完全集是指到达数据包中的所有项的集合。一个数据项子集是这样一个集合，它所包含的元素都来自其所属的数据项完全集，但数据项子集不等于数据项完全集。一个数据项完全集包含多个数据项子集，每个数据项子集和数据项完全集发生的时间组成了多个不同的事件。如数据项完全集(A, B, C)在时间 t1 到达了，则事件(A)|t1、(B)|t1、(C)|t1、(B)|t1、(A, B)|t1、(A, C)|t1、(B, C)|t1、(A, B, C)|t1 同时发生。数据项集是以数据包为基础的，并且只相对于包中的数据而言，对包外的项集没有意义。如果包中只有 A，则(A)是一个数据项完全集，如果包中有 A,B,C,D则(A, B, C, D)是一个数据项完全集，前一个包中的(A)和后一个包中的(A, B, C, D)是没有关系也没有任何可比性的，虽然看上去后者包含前者。
…………
2.2 算法理论背景知识及正确性证明
流数据中不同事件的发生是不相互影响的，即事件的发生是相互独立的。例如网络点击事件中，某用户的点击事件和另一个浏览网页的人的点击事件是完全没有关系的。即便有关系我们也完全可以忽视这种关系对结果的影响。对于在时间段(t1, t2)上的分布，任意发生在(t1, t2)上的事件的发生时间都是服从这个分布的。即如果两个事件都来自(t1, t2)上，则他们是同分布的，分布函数如式 2-3 所示。在上面的证明中我们已经知道对于在某段时间发生的事件来说他们的均值是服从正态分布的，从另一个角度来说就是他们的集中程度是一定的。而所谓的集中程度就是概率密度的一种表现形式。所表示的随机事件发生的概率以中心点 x=μ 对称，并且离中心点越远发生的概率越高，反之越低。本文就是利用这一性质，将那些偏离中心点很远发生概率很小的事件判定为不可能事件然后做剪枝删除处理。关于这个不可能事件的边界条件，即不可能事件的概率因具体问题和数据特征而不同，在具体问题中需要不同的概率，并且本算法对于这个值是及其敏感的。这点将在以后的实验部分给出。前面讲了正态分布的中心对称特性，除了中心对称特性正态分布还有另外一个特性就是关于参数 σ 的。总体来说就是 σ 越小分布越“集中”，σ 越大分布越“分散”。可见 σ 也是对分布影响很大的一个参数，即如果要计算出给定不可能概率对应的时间必须同时确定 μ 和 σ 两个参数。对于一个已经给定的正态分布来说 μ 和 σ 的值是已知的，但是在日常的一些统计中这些值是不可能精确给定的，而是通过抽样调查然后估计的方法在允许的精度范围内给出一个估计值。对于估计的方法和理论依据将在下一小节给出。
…………
第三章 密度信息树 PDIT 概述..... 15
3.1 密度信息树 PDIT(Probability Density Information Tree)的定义 ..... 15
3.2 密度信息树 PDIT 的维持过程 .... 16
3.2.1 密度信息树 PDIT 的插入过程 ..... 16
3.2.2 密度信息树 PDIT 产生信息完全树的过程 ......... 18
3.2.3 密度信息树 PDIT 的剪枝 ....... 24
第四章 算法 PDB-FIM 实现过程........ 26
4.1 算法概述 ......... 26
4.2 算法 PDB-FIM 的执行条件......... 28
4.3 算法 PDB-FIM 的执行过程......... 30
4.4 算法 PDB-FIM 中不可能概率的计算方法......... 32
4.5 未解决问题及算法的缺陷 ..... 34
4.5.1 查询频度对结果有影响 .... 34
4.5.2 偷渡效应 ...... 35
4.6 实验 ..... 37
第四章 算法 PDB-FIM 实现过程
4.1 算法概述
在流数据中，情况是十分复杂的。到达的数据流中可能包含某个事件发生的时间，这样我们就可以很方便的用这个时间作为事件时间维度上的统计样本。然而有的数据流中是没有时间信息的，我们就不得不采用折中的办法，即用到达时间来代替发生时间，虽然在网络延迟的影响下可能会对结果产生影响，但是如果时间单位是以小时或者天计算的话，这种影响是可以忽略不计的。因为本算法的数据是模拟数据，并不能完全模拟到达时间所产生的影响，所以先假设数据是匀速产生的，也就是说事件和事件之间的间隔是均匀的，这样事件发生的时间和其在数据流中的位置就有了一个一一对应关系，所以在提供的算法中用事件在流数据中的位置信息代表事件发生的时间信息。对于位置信息是可以通过给到达的事件编号的方式简单实现的。本算法中的“事件发生时间”一律为事件到达时系统给定的一个事件编号。对于不断到达的流数据，其中的事件是非常多的，此算法以购物篮分析为例。假设到达一个购买的项集(A, B, C, D)|223，其中 223 代表了项集的编号，即为事件发生的时间，则认为事件(A)、(B)、(C)、(D)、(A, B, C)、(A, B, D)、(A, D)、(A, C)、(A, C, D)、(B, C)、(B, D)、(B, C, D)、(C, D)、(A, B, C, D)都发生了。所以在树中要更新所有这些事件所对应的统计信息。比如这个时候事件(A,B,C)对应的 N 为32(在此之前发生了 32 次)、α1为 2302、α2为 7033254，则更新数据 N 为 33(32+1)、α1为 2525(2302+223)、α2为 7033254(33254 + 2232)。对所有项集都要做同样的改动。初始项集的长度为 n 的话，产生的子集为 2n个，很显然当项集非常长的时候这种改动是很复杂麻烦的。所以在算法中采用了树的结构，在第一次到达的时候只更新(A, B, C, D)对应的数据区，然后在后续的重新插入为完全树的过程中将这种更新加入到其他项集中去。如：重新插入的时候(A, B, C, D)对应(45, 3234, 8144252)，(B, C, D)对应(10, 1432, 1021132)，则更新事件(B, C, D)的数据域为(10 + 45, 1432 +3234, 1021132 + 8144252)。这样就减少了每次计算的次数，将更新推迟到访问某个节点的时候。
…………
结论
算法 PDB-FIM 在流数据中发现频繁事件是有效的，它不但提出了一个流数据内存管理方法并且还在一定程度上解决了传统流数据挖掘中对历史频繁事件处理力不从心的问题。虽然算法还有一些缺陷有待完善，但是可以说这个算法输出结果的可依赖性还是很高的，并且我相信在不久的将来这些缺陷一定会被改进并完善到本算法中。现将算法 PDB-FIM 中的一些贡献总结如下：
(1)算法 PDB-FIM 介绍了密度信息树 PDIT 的概念，通过存储事件的密度信息将事件的密度信息完整的保存到了事件被挖掘以前。
(2)算法 PDB-FIM 的采用了通过密度信息剪枝达到维持一个保存了当前感兴趣的事件信息集合方法，并且给以后流数据挖掘的发展方向提供了新的思路。同时希望这些想法能给从事这方面研究的人提供更多的灵感。
(3)本文还介绍了完全信息树和不完全信息树的概念，并且采用通过保持一棵不完全信息树和一棵完全信息树的方法节省内存加速算法的速度。同时还讨论了其他可行的方案并比较了其和其他方法的优缺点。
(4)提供了密度信息的提取、处理、计算和使用方法，这也是本论文的核心内容。
……………
参考文献（略）