高效数据流和海量文本处理算法研究

摘要

随着网络通信技术的迅速发展，以数据流形式呈现的数据大量涌现在各个信息处理领域。例如无限传感器网络中传回基站的传感数据流，人们浏览网页时产生的网络点击流，还有证券买卖产生的实时交易信息等等。数据流具有数据量大，持续快速产生，数据分布随时间变化等等特点。而传统静态数据集合中的分析处理技术往往只适用于处理那些可存储在磁盘上的有限静态数据。这些传统技术往往都需要多次扫描所处理的全部数据，从而使得将它们直接于处理数据流时，会带来严重的低效率和高代价。面对这些持续快速到达的海量数据流，如何利用有限的资源来有效的分析处理它们成为时下最为关心的问题。典型的数据流分析处理问题包括数据流聚类,数据流变化检测,副本检测等等。
　　 随着互联网的发展，网络信息的监测和管理中急需处理海量文本数据(如大量的网络网页)。而传统的文本分析处理技术仅适用于处理小规模的文本数据，而难以处理海量的文本数据。典型的文本处理问题包括文本分类，文本聚类和文本信息抽取等等。
　　 本文对数据流和海量文本处理技术中若干关键问题进行了深入研究，主要包括以下内容：
　　 1.一种适用于高维数据流变化检测算法：
　　 本文首先将数据流上的变化检测问题转化为寻找变化显著单元格的问题。基于频繁模式挖掘FP算法，设计一种记录数据流中网格的经验分布变化值的数据结构--VT树（variation tree），并通过搜索VT树中的路径来发现高维数据流中所有经验分布变化值大于ε的网格。
　　 2.一种基于代表点的高维数据流上聚类算法
　　 传统的基于网格的聚类算法难以适用于处理处理演化的高维数据流。本文对高维数据流中数据点的每一个维度属性进行单独量化，并用量化得到的每个维度上的代表点来替代传统基于网格的聚类算法中的固定划分区间。本文算法中代表点是随着不断流过的高维数据流而演化变化的，从而能比其他数据流聚类算法更好的捕捉到演化高维数据流中聚类。
　　 3.一种滑动窗口上数据流副本检测的有效算法
　　 本文出一种新的数据结构：Flag Bloom Filter(FBF)。这种新的数据结构改进了目前最有效的Decaying Bloom Filter(DBF)。基于FBF，本文提出了一种高效的算法来解决滑动窗口上数据流副本检测问题。给定滑动窗口大小W，计数器个数M，FBF比DBF多使用M比特空间，但FBF的误是率是DBF的2k/(k+1)，其中k=[ln(2)M/W]≥2为使用的哈希函数个数。给定同样的内存空间G和滑动窗口大小W（FBF使用的计数器个数是DBF的logW/(logW+1)）FBF的误是率上界为(0.25)k(1-1/logW)(1+k(1-1/logW))。当W≥32时，这个上界比DBF的误是率要小。
　　 4.一种滑动窗口上概率数据流副本检测有效算法
　　 针对确定性数据流的副本检测方法无法保存概率数据流中元素的存在概率。基于Counting Bloom Filter，本文提出了一种新的数据结构Floating Counter Bloom Filter(FCBF)。基于FCBF结构，我们提出了一种滑动窗口上概率数据流的副本检测算法。给定滑动窗口大小W和浮点计数器个数N，针对滑动窗口上的一个元素t，我们的方法以概率1-(1/2)ln(2)*N/W输出该元素的精确存在概率。
　　 5.针对海量文本的KNN改进分类算法：
　　 面对海量文本数据时，传统的KNN分类算法无论在分类精度还是分类时间方面都明显效果很差。针对这个问题，基于最小化学习误差的增量的思想，本文将学习型矢量量化(LVQ)和生长型神经气（GNG）结合起来提出一种新的增量学习型矢量量化方法，并将其应用到海量文本分类中。本文提出的算法对所有的训练样本有选择性的进行一次训练就可以生成有效的代表样本集，从而适合处理海量文本数据，且可以有效的提高分类精度和减少分类时间。

目录

文摘

英文文摘

声明

第1章 引言

第2章 一种适用于高维数据流的变化检测方法

第3章 一种基于代表点的高维数据流聚类算法

第4章 一种滑动窗口上数据流副本检测的有效算法

第5章 一种滑动窗口上概率数据流副本检测的有效算法

第6章 基于增量学习型矢量量化的海量文本分类方法

第7章 总结

参考文献

致 谢

在读期间发表的学术论文与取得的研究成果