【作者】 王修君；

【导师】 沈鸿；

【作者基本信息】 中国科学技术大学 ， 计算机软件与理论， 2011， 博士

【摘要】 随着网络通信技术的迅速发展,以数据流形式呈现的数据大量涌现在各个信息处理领域。例如无限传感器网络中传回基站的传感数据流,人们浏览网页时产生的网络点击流,证券买卖产生的实时交易信息等等。数据流具有数据量大,持续快速产生,数据分布随时间变化等特点。而传统静态数据集合中的分析处理技术往往只适用于处理那些可存储在磁盘上的有限静态数据。这些传统技术往往都需要多次扫描所处理的全部数据,从而使得将它们直接用于处理数据流时,会带来严重的低效率和高代价。面对这些持续快速到达的海量数据流,如何利用有限的资源来有效的分析处理它们成为时下最为关心的问题。典型的数据流分析处理问题包括数据流聚类、数据流变化检测和副本检测等。随着互联网的发展,网络信息的监测和管理中急需高效的处理海量文本数据(如大量的网络网页)。而传统的文本分析处理技术仅适用于处理小规模的文本数据,而难以处理海量的文本数据。典型的文本处理问题包括文本分类、文本聚类和文本信息抽取等等。本文对数据流和海量文本处理技术中若干关键问题进行了深入研究,主要包括以下内容：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=[In(2)M/W]≥2为使用的哈希函数个数。给定同样的内存空间G和滑动窗口大小W(FBF使用的计数器个数是DBF的1og W/(logW+1))FBF的误是率上界为(0.25)k(1-1/logW)(1+k(1-1/logW))。当W≥32时,这个上界比DBF的误是率要小。4.一种滑动窗口上概率数据流副本检测有效算法针对确定性数据流的副本检测方法无法保存概率数据流中元素的存在概率。基于Count ing Bloom Filter,本文提出了一种新的数据结构Floating Counter Bloom Filter(FCBF)。基于FCBF结构,本文提出了一种滑动窗口上概率数据流的副本检测算法。给定滑动窗口大小W和浮点计数器个数N,针对滑动窗口上的一个元素t,本文的方法以概率1-(1/2)In(2)*N/W输出该元素的精确存在概率。5.针对海量文本的KNN改进分类算法：面对海量文本数据时,传统的KNN分类算法无论在分类精度还是分类时间方面都明显效果很差。针对这个问题,基于最小化学习误差增量的思想,本文将学习型矢量量化(LVQ)和生长型神经气(GNG)结合起来提出了一种新的增量学习型矢量量化方法,并将其应用到海量文本分类中。本文提出的算法对所有的训练样本有选择性的进行一次训练就可以生成有效的代表样本集,从而适合处理海量文本数据,且可以有效的提高分类精度和减少分类时间。更多还原

【Abstract】 With the rapid development of network technology, data streams have been more and more commonly used in many real world applications. For example, base station receives sensor data streams from sensor nodes in a wireless sensor network; click streams are generated when people surf the Internet and so on. Data streams are usually characterized by large volumes of data, rapid generation speed and evolving data distribution. Traditional data processing algorithms are only suitable for static finite data which can be stored on hard disk. These algorithms always need several scans on the stored static data. So they can not be applied in processing data streams.Thus how to efficiently utilize limited storage and computation resource to process data streams becomes an important task. Typical data stream processing problems include clustering, change detection, duplicate detection and so on.With the rapid development of the Internet, how to efficiently process massive text data (e.g. a large number of web pages) becomes an important task for many applications such as network information management. Traditional text processing algorithms are usually only suitable for small scale text data. Typical text data processing problems include text classification, text clustering and so on.This thesis focuses on the problems of efficiently processing data streams and massive text data. Its main contributions are:1. A change detection method for high-dimensional data streams We propose a change detection method for high-dimensional data streams. This method divides the data space of a data stream into cells with same volume, then detects the distribution changes in different combinations of cells called grid. Based on Hoeffding bound, we set the upboundεof the variance of experiential distribution for the grids (on the hypothesis that the underlying distribution does not change). Then, inspired by FP algorithm [Han et al 2000], a modified data structure of VT-Tree is defined to save the change of experiential distribution in every cell and all grids with variance greater thanεare found. Simulation results on empirical data show that our proposed method is quite effective.2. Clustering high dimensional data streams with representative points The fixed-size interval partitioning adopted in traditional grid based clustering methods can not capture clusters in each dimension well when they are applied in evolving high dimensional data streams. In this thesis, we quantify each dimension (attribute) of data points separately and use the generated representative data points for each dimension to substitute the fixed-size interval. These data points are updated with incoming data points continuously so that they can capture the cluster trends in each dimension more accurately than the fixed-size intervals.Experiment results on synthetic and real data sets display the high effectiveness and accuracy of the proposed method.3. Improved online detection of duplicates in streaming data over sliding windows In this thesis, we propose a new data structure, namely Flag Bloom Filter (FBF), that improves the Decaying Bloom Filter (DBF), the known most efficient variant of Bloom Filter, and an efficient algorithm based on FBF for online approximate detection of duplicates over sliding windows. Given the same sliding window size W and M counters, with M bits more memory our FBF reduces the false positive rate (FPR) of DBFby a factor of 2k/(k+1), where k= [ln(2)M/W]≥2 is the number of hash functions. When using the same memory size G and sliding window size W, our FBF uses a factor of 1/(log W+1) fewer counters than DBF and has an FPR bounded by (0.25)k(1-1/logW)(1+k(1-1/logW)) which is smaller than the FPR of DBF when W≥32.4. Approximately detecting duplicates for probabilistic data streams over sliding windowsDuplicate detection method for certain data streams can not maintain existential probabilities of elements in a probabilistic data stream. In this thesis, we presenta novel data structure, Floating Counter Bloom Filter (FCBF), as anextension of Counting Bloom Filters which can maintain these existential probabilities effectively. Based on FCBF, we present an efficient algorithm to approximately detect duplicates for probabilistic datatreams over sliding windows. Given a sliding window size W and floating counter number N, for any t which occurs in the pastsliding window, our method output the accurate existentialprobability of t with probability 1-(1/2)ln(2)*N/W. Experimental results on the synthetic data verify the effectiveness of our approach.5. An improved KNN method for massive text classification As a simple, non-parametric, and effective method, KNN has been widely applied in text classification. But in handling massive text, both classification accuracy and classification time become unacceptable. To solve this problem, based on minimizing the increment of learning errors and combining LVQ and GNG, we propose a new growing LVQ method and apply it to text classification. Our method can generate a representative sample set after one phase of selective training of a sample set, and hence acquires a strong learning ability. Experiments show that this method can reduce the testing time of KNN, and maintain or even improve the accuracy of classification.更多还原