论文部分内容阅读
【摘要】随着计算机信息技术的迅速发展，数据流挖掘分类技术应用在许多领域。如金融市场、网络监控、电信数据管理、传感器网络等。然而，数据流挖掘和分类技术还有进一步改进和提高的空间，所以数据流挖掘将成为目前的研究热点。
【关键词】数据流挖掘；分类技术。应用领域；研究热点
中图分类号： C37 文献标识码： A 文章编号：
一、前言
本文着重介绍了近年来国际上数据流挖掘领域的研究成果，对数据流挖掘的关键技术从聚类、分类、频繁模式发现和时间序列分析四个方面进行了介绍，并对相关算法进行了归纳总结，最后提出了分类技术改进的新思路等问题，希望有一定的理论指导意义。
二、數据流挖掘概述
数据流，顾名思义，数据流就是连续产生的数据，数据流是实时、连续、有序、时变、无限的元组序列。数据流分类，在一个数据流S中，每一个元素S属于一个预定义的类型，有一个潜在的类标，但是类标的真实值未知。数据流分类通过对训练数据集进行学习，推导出一个有效的分类模型，预测未知数据的真实类标。与传统的数据集相比，数据流具有以下一些鲜明的特点 ：
a有序性。数据流中的元组按时问有序生成 ，序号隐含于到来的时刻或直接以时间戳记录。
b不可再现性。数据流中的数据一旦流过处理节点就不会再次出现，除非进行特殊的保存。
c高速性。数据流数据高速地生成，即产生元组的速率较 高。
d无限性。数据流数据一直连续不断地产生，往往是无限量的。
e高维性。数据流往往包含大量的属性，即描述数据流的维数较高。
f动态性。产生数据流的概率分布模型是时变的，且变化的速率无法控制。
三、数据流挖掘的研究热点
目前对数据流挖掘的研究热点主要集中在数据流的聚类、分类、离群点检测和频繁模式挖掘等方面。
1.数据流聚类算法
聚类是指对一个已给的数据对象集合，将其中相似的对象划分为一个或多个组(称为“簇”)的过程 。同一个簇中的元素彼此相似 ，而与其它簇中的元素相异。数据流的聚类算法不同于传统数据的聚类算法，必须是增量式的，对聚类的表示要简洁，对新数据的处理要快速，对噪音和异常数据必须是稳健的。因此，基于数据流的聚类算法要在一个相对较小的内存空间上，对数据流进行一遍扫描后，把数据集合分为一个个簇集。典型的数据流聚类算法包括STREAM[、C1uStream、DenStrearnE1。
2.数据流分类算法
数据挖掘分类方法一般分为两个步骤：首先根据一组已知目标类别的训练样本生成一个分类器，用以描述数据属性与目标类别的概念：然后根据前面生成的分类器对其他未经分类的测试数据进行分类。分类方法根据训练样本获取方式的不同，分为增量式和非增量式两种。数据流挖掘的增量式方法一般都假设取得的样本是由平稳分布的数据中所获得。但现实世界中，新数据的概念可能会随着时问的延续而与历史数据产生改变，这种概念随着时问延续而改变的情形，称为概念漂移。在研究数据流挖掘的过程中，最初都是假设数据是平稳分布的，更注重的是如何解决数据流中大数据样本的问题。后来，在传统机器学习研究领域关于概念漂移解决方法的基础上，很多研究者提出了解决数据流上概念漂移问题的分类技术。本节将分析几种代表性的数据流分类算法。
（一）VFDT是一种基Z-Hoeffding不等式建立决策树的方法，它通过不断地将叶节点替换为决策节点而生成．其中每个叶节点都保存有关于属性值的统计信息，这些统计信息用于计算基于属性值的测试。根据不同的属性取值进入不同的分支，最终到达树的叶节点。当数据到达I1一P节点后，节点上的统计信息就被更新，同时该节点基于属性值的测试值就被重新计算。如果统计信息计算显示测试满足一定的条件，则该叶节点变为决策节点。新的决策节点根据属性的可能取值的数目产生相应数目的子女叶节点。VFDT很好地解决了数据流的样本过多的问题，所产生的决策树在大量减少处理样本数目的同时，能够保证和用全部样本所产生的决策树具有无限接近的精度。
（二）CVFDT，该算法在叶节点可能会产生概念漂移时产生一棵备选子树，并且在新子树变得更精确时用新子树替代原先的子树。每当有新样本到达，就把VFDT应用到滑动窗口上。
（三）CVFDT通过不断地把VFDT算法应用到固定大小的滑动窗体上，从不断变化的数据流上生成决策树。Wang等人提出了一种利用加权的多个分类器挖掘概念漂移数据流的方法。系统首先从数据流中训练几个分类器，同时根据测试数据集上的分类精度期望进行加权。集成学习方法既提高了学习模型的效率，也提高了分类精度。
3.数据流离群点检测算法
离群点检测问题是数据挖掘技术的重要研究领域之一，它被广泛应用于网络入侵抵御、信用卡恶意透支检测等风险控制领域。离群点检测算法可分为基于统计的方法、基于距离的方法、基于密度的方法和基于偏离的方法等。在有限运行空间上通过对数据流进行一次或较少次数的扫描，实现有效的数据流离群点挖掘具有重要意义。数据流离群点的挖掘已引起国内外研究者的广泛关注。
4.频谱的离群点检测算法SODA，该算法可用来挖掘定时的、类型确定的离群事件。它支持基于距离和基于密度的2种离群点定义，对当前到来的数据进行在线分布式离群点挖掘。该算法效率较好，。但需要计算受影响对象的距离、局部可达密度、局部离群因子LOF，对数据集要进行3次扫描。但只适用于分布式传感器网络数据流。
四、数据流分类技术的新思路
由上述分析可知，对于时变的数据流，需要一定的类标数据检测变化的性质。如果数据流发生显著变化，需要足够的类标数据更新过时的分类模型。本文提出采用主动学习方法降低检测变化和更新模型对类标数据的需求量；采用半监督学习方法大大降低更新模型对类标数据的需求量。因此，主动学习和半监督学习可以可靠地检测数据流的变化，保持一个有效的分类模型。
1.主动学习方法
监督学习基于两个基本的假设：存在足够的训练数据和训练数据集是整个数据总体的一个简单的随机样本。主动学习通过选择性采样方法来组织训练数据，它设法选出信息量最大的对象作为训练数据。大大降低更新模型对类标数据的需求量，需要的标记资源大大减少，高效地利用有限的标记资源，组织包含信息量最大的类标数据集。从机器学习的角度而言，分类属于一种监督学习，建立和更新模型依赖于训练数据。在计算时间上，有些NP完全问题降为多项式可解。可以组织信息量丰富的类标数据作为训练数据，提高分类模型的性能，间接地降低了模型对类标数据的需求量。利用可以学习得到一个高质量的分类模型。
2.半监督学习方法
半监督学习位于监督学习和无监督学习之间，结合监督学习和无监督学习的优点，弥补各自的不足，利用少量的类标数据和大量的无类标数据学习一个有效的分类模型。监督学习可以得到一个准确的分类模型，但需要较大数量的类标数据作为训练集，且模型的性能随着训练数据的增加而提高。与传统的监督学习相比，半监督学习可以较大地提高模型的性能，特别是类标数据极少的情况。利用半监督学习方法，结合少量的类标数据D和大量的无类标数据D，可以推导出一个有效的模型h，h的性能和P相当。
五、研究方向展望
基于目前数据流挖掘的现状，以下方面的研究将得到更多的关注：
1.将现有的数据流管理系统和数据流挖掘技术进行集成，设计反映数据流特性的具有实用价值的动态系统，并考虑分布和并行的特性；
2.在具有带宽限制的无限传感器网络中实现流数据挖掘技术；
3.研究数据流上挖掘结果变化趋势的表示和建模方法，并研究数据流的局部周期挖掘算法．
数据流上的挖掘技术已经成为当前数据库领域的研究热点，随着研究的深入和技术的进步，它将在在物理学、天文学、经济以及商业等等领域中实现前所未有的价值．
六、结束语
虽然数据流挖掘的研究只是处于刚刚起步的阶段，但它已经引起计机和网络研究者的广泛关注。随着数据流挖掘和分类技术的不断深入研究，这项技术将被广泛应用于各个领域。
参考文献：
[1]杨路明，刘立新，毛伊敏等.数据流挖掘 算法[J].计算机应用研究 ，2010.27(2).
[2]倪巍伟，陆介平，陈耿等．基于k均值分区的数据流离群点检测算法[J]．计算机研究与发展，2006，43(9).
【关键词】数据流挖掘；分类技术。应用领域；研究热点
中图分类号： C37 文献标识码： A 文章编号：
一、前言
本文着重介绍了近年来国际上数据流挖掘领域的研究成果，对数据流挖掘的关键技术从聚类、分类、频繁模式发现和时间序列分析四个方面进行了介绍，并对相关算法进行了归纳总结，最后提出了分类技术改进的新思路等问题，希望有一定的理论指导意义。
二、數据流挖掘概述
数据流，顾名思义，数据流就是连续产生的数据，数据流是实时、连续、有序、时变、无限的元组序列。数据流分类，在一个数据流S中，每一个元素S属于一个预定义的类型，有一个潜在的类标，但是类标的真实值未知。数据流分类通过对训练数据集进行学习，推导出一个有效的分类模型，预测未知数据的真实类标。与传统的数据集相比，数据流具有以下一些鲜明的特点 ：
a有序性。数据流中的元组按时问有序生成 ，序号隐含于到来的时刻或直接以时间戳记录。
b不可再现性。数据流中的数据一旦流过处理节点就不会再次出现，除非进行特殊的保存。
c高速性。数据流数据高速地生成，即产生元组的速率较 高。
d无限性。数据流数据一直连续不断地产生，往往是无限量的。
e高维性。数据流往往包含大量的属性，即描述数据流的维数较高。
f动态性。产生数据流的概率分布模型是时变的，且变化的速率无法控制。
三、数据流挖掘的研究热点
目前对数据流挖掘的研究热点主要集中在数据流的聚类、分类、离群点检测和频繁模式挖掘等方面。
1.数据流聚类算法
聚类是指对一个已给的数据对象集合，将其中相似的对象划分为一个或多个组(称为“簇”)的过程 。同一个簇中的元素彼此相似 ，而与其它簇中的元素相异。数据流的聚类算法不同于传统数据的聚类算法，必须是增量式的，对聚类的表示要简洁，对新数据的处理要快速，对噪音和异常数据必须是稳健的。因此，基于数据流的聚类算法要在一个相对较小的内存空间上，对数据流进行一遍扫描后，把数据集合分为一个个簇集。典型的数据流聚类算法包括STREAM[、C1uStream、DenStrearnE1。
2.数据流分类算法
数据挖掘分类方法一般分为两个步骤：首先根据一组已知目标类别的训练样本生成一个分类器，用以描述数据属性与目标类别的概念：然后根据前面生成的分类器对其他未经分类的测试数据进行分类。分类方法根据训练样本获取方式的不同，分为增量式和非增量式两种。数据流挖掘的增量式方法一般都假设取得的样本是由平稳分布的数据中所获得。但现实世界中，新数据的概念可能会随着时问的延续而与历史数据产生改变，这种概念随着时问延续而改变的情形，称为概念漂移。在研究数据流挖掘的过程中，最初都是假设数据是平稳分布的，更注重的是如何解决数据流中大数据样本的问题。后来，在传统机器学习研究领域关于概念漂移解决方法的基础上，很多研究者提出了解决数据流上概念漂移问题的分类技术。本节将分析几种代表性的数据流分类算法。
（一）VFDT是一种基Z-Hoeffding不等式建立决策树的方法，它通过不断地将叶节点替换为决策节点而生成．其中每个叶节点都保存有关于属性值的统计信息，这些统计信息用于计算基于属性值的测试。根据不同的属性取值进入不同的分支，最终到达树的叶节点。当数据到达I1一P节点后，节点上的统计信息就被更新，同时该节点基于属性值的测试值就被重新计算。如果统计信息计算显示测试满足一定的条件，则该叶节点变为决策节点。新的决策节点根据属性的可能取值的数目产生相应数目的子女叶节点。VFDT很好地解决了数据流的样本过多的问题，所产生的决策树在大量减少处理样本数目的同时，能够保证和用全部样本所产生的决策树具有无限接近的精度。
（二）CVFDT，该算法在叶节点可能会产生概念漂移时产生一棵备选子树，并且在新子树变得更精确时用新子树替代原先的子树。每当有新样本到达，就把VFDT应用到滑动窗口上。
（三）CVFDT通过不断地把VFDT算法应用到固定大小的滑动窗体上，从不断变化的数据流上生成决策树。Wang等人提出了一种利用加权的多个分类器挖掘概念漂移数据流的方法。系统首先从数据流中训练几个分类器，同时根据测试数据集上的分类精度期望进行加权。集成学习方法既提高了学习模型的效率，也提高了分类精度。
3.数据流离群点检测算法
离群点检测问题是数据挖掘技术的重要研究领域之一，它被广泛应用于网络入侵抵御、信用卡恶意透支检测等风险控制领域。离群点检测算法可分为基于统计的方法、基于距离的方法、基于密度的方法和基于偏离的方法等。在有限运行空间上通过对数据流进行一次或较少次数的扫描，实现有效的数据流离群点挖掘具有重要意义。数据流离群点的挖掘已引起国内外研究者的广泛关注。
4.频谱的离群点检测算法SODA，该算法可用来挖掘定时的、类型确定的离群事件。它支持基于距离和基于密度的2种离群点定义，对当前到来的数据进行在线分布式离群点挖掘。该算法效率较好，。但需要计算受影响对象的距离、局部可达密度、局部离群因子LOF，对数据集要进行3次扫描。但只适用于分布式传感器网络数据流。
四、数据流分类技术的新思路
由上述分析可知，对于时变的数据流，需要一定的类标数据检测变化的性质。如果数据流发生显著变化，需要足够的类标数据更新过时的分类模型。本文提出采用主动学习方法降低检测变化和更新模型对类标数据的需求量；采用半监督学习方法大大降低更新模型对类标数据的需求量。因此，主动学习和半监督学习可以可靠地检测数据流的变化，保持一个有效的分类模型。
1.主动学习方法
监督学习基于两个基本的假设：存在足够的训练数据和训练数据集是整个数据总体的一个简单的随机样本。主动学习通过选择性采样方法来组织训练数据，它设法选出信息量最大的对象作为训练数据。大大降低更新模型对类标数据的需求量，需要的标记资源大大减少，高效地利用有限的标记资源，组织包含信息量最大的类标数据集。从机器学习的角度而言，分类属于一种监督学习，建立和更新模型依赖于训练数据。在计算时间上，有些NP完全问题降为多项式可解。可以组织信息量丰富的类标数据作为训练数据，提高分类模型的性能，间接地降低了模型对类标数据的需求量。利用可以学习得到一个高质量的分类模型。
2.半监督学习方法
半监督学习位于监督学习和无监督学习之间，结合监督学习和无监督学习的优点，弥补各自的不足，利用少量的类标数据和大量的无类标数据学习一个有效的分类模型。监督学习可以得到一个准确的分类模型，但需要较大数量的类标数据作为训练集，且模型的性能随着训练数据的增加而提高。与传统的监督学习相比，半监督学习可以较大地提高模型的性能，特别是类标数据极少的情况。利用半监督学习方法，结合少量的类标数据D和大量的无类标数据D，可以推导出一个有效的模型h，h的性能和P相当。
五、研究方向展望
基于目前数据流挖掘的现状，以下方面的研究将得到更多的关注：
1.将现有的数据流管理系统和数据流挖掘技术进行集成，设计反映数据流特性的具有实用价值的动态系统，并考虑分布和并行的特性；
2.在具有带宽限制的无限传感器网络中实现流数据挖掘技术；
3.研究数据流上挖掘结果变化趋势的表示和建模方法，并研究数据流的局部周期挖掘算法．
数据流上的挖掘技术已经成为当前数据库领域的研究热点，随着研究的深入和技术的进步，它将在在物理学、天文学、经济以及商业等等领域中实现前所未有的价值．
六、结束语
虽然数据流挖掘的研究只是处于刚刚起步的阶段，但它已经引起计机和网络研究者的广泛关注。随着数据流挖掘和分类技术的不断深入研究，这项技术将被广泛应用于各个领域。
参考文献：
[1]杨路明，刘立新，毛伊敏等.数据流挖掘 算法[J].计算机应用研究 ，2010.27(2).
[2]倪巍伟，陆介平，陈耿等．基于k均值分区的数据流离群点检测算法[J]．计算机研究与发展，2006，43(9).