数据流分类变化的分析和检测

zangzhishan

数据流分类变化的分析和检测
数据流分类变化的分析和检测
黄树成，朱霞
(江苏科技大学计算机科学与工程学院，江苏镇江 212003)
摘要：针对主动挖掘和被动挖掘2 种典型分类方法的特点，分析实际问题中数据流的基本变化类型及衍生的各种变化情况，证明主动挖
掘方法在许多情况下无法有效工作，给出一个有效检测数据流变化的思路。采用主动学习方法，利用有限的资源可以组织高质量的类标数
据，降低训练数据的需求量。
关键词：数据流；概念漂移；分布变化；主动挖掘；被动挖掘
Analysis and Detection of Changes in Data Stream Classification
HUANG Shu-cheng, ZHU Xia
(School of Computer Science & Engineering, Jiangsu University of Science & Technology, Zhenjiang 212003, China)
【Abstract】Aiming at the characteristics of active mining and passive mining, this paper analyzes two basic types of change and possible
combination ones in a real-world data stream, demonstrates that the active mining method does not work in most situations. It offers an effective
framework for detecting the changes in data streams. By using active learning method, it employs limited resources to organize high-quality data,
and reduces the training data.
【Key words】data stream; concept-drift; distribution change; active mining; passive mining
DOI: 10.3969/j.issn.1000-3428.2011.04.028
计 算 机 工 程
Computer Engineering
第37 卷第 4 期
Vol.37 No.4
2011 年2 月
February 2011
·App技术与数据库· 文章编号：1000—3428(2011)04—0078—03 文献标识码：A 中图分类号：TP311
1 概述
挖掘数据流要求算法对整个数据流仅做一次扫描、具有
较小的时空开销。当产生数据流的模型发生变化时，需要及
时地调整当前的模型。随着应用需求的越来越多，在数据流
中挖掘常识已成为一个热门研究领域[1-2]。本文重点研究数据
流分类中变化的分析和检测。
传统方法基于一个不现实的假设：产生数据流的模型服
从一个稳定的分布。但在现实中，大多数数据流不符合这个
假设。对于已经发生变化的数据流，基于原来训练数据建立
的模型具有较低的分类能力，必须根据变化予以及时调整。
现有的算法可以分成主动挖掘算法[3-4]和被动挖掘算法[5-6]
2 类。被动挖掘算法被动地等待一些数据类标已知后，用这
些数据检测数据流是否发生变化。具体包括以下4 个步骤：
(1)基于历史训练数据学习得出一个初始的模型。
(2)在分类新数据的同时，被动地等待一些数据的类标。
(3)当得到一些数据的类标时，用这些数据更新原有的模型。
(4)返回到第(2)步。
相反，主动挖掘算法无须知道新数据的类标，它们采用特
定的方法，实时地监控数据流的变化。具体包括以下4 个步骤：
(1)基于历史训练数据学习得出一个初始的模型。
(2)分类新数据的同时实时地监控数据流的变化。
(3)当第(2)步中检测到的变化量大于允许的阈值时，投入
适当的费用调查小部分新数据的类标。基于这些已知类标的
数据，可以统计出原有模型损失的估计值。
(4)当损失估计值大于允许的极值时，基于这些类标已知
的数据，更新原有的模型，响应数据流的变化。
由此可见，当数据流变化速度很快时，被动算法无法及
时地做出调整；当数据流没有发生变化时，周期地更新模型
会浪费有限的资源。相反，主动算法可以实时地检测变化且
做相应的处理。本文主要对文献[3-4]的内容做了一定的扩展。
2 数据流挖掘面临的挑战
数据流分类存在 2 个关键问题：(1)很难确定数据流是否
发生变化，变化是否造成当前的分类模型无效；(2)即使能正
确地识别出变化，也很难组织充足的训练数据更新模型。
2.1 数据流变化的基本类型
一般而言，数据流的变化可以抽象成 2 种基本类型：分
布变化和概念漂移。假设一个数据流S ，它由以时间为顺序
的二元组构成，元组序列为I1, I2 ,􀀢Ik ,􀀢 。每个元组代表一
个具有类标“+”或“－”的对象， i p 表示对象i x 在S 中出
现的概率，按照到达时间的先后顺序将S 分成顺序块； i S 表
示第i 块，是时间ti 和ti 1 + 间隔中的元组序列1 2 , , ,d i i i I I I 􀀢 ； ik
p
表示对象xk 在Si 中的概率。假设把数据块0 S 当作初始训练数
据集，学习出一个初始的分类模型： c = f (x) 。
在数据流 S 中，Sm和Sn等不同的数据块可能具有不同的
目标分类模型，假设模型分别为c = fm (x) 和c = fn (x) 。因此，
基于数据块0 S 建立的初始模型不能直接用于其他数据块，即
在相同的损失函数条件下，取自不同数据块的相同对象xk 可
能具有不同的类：
fm (xk ) ≠ fn (xk ) (1)
这种变化称为概念漂移，2 个相邻数据块Si 和Si 1 + 的漂移
速度cr 等于它们模型不相同的概率， cr = Prob[ fm (xk ) ≠
fn (xk )]。否则，若：
fm (xk ) = fn (xk ) (2)
基金项目：国家自然科学基金资助项目(70871057)；江苏省高校自然
科学研究计划基金资助项目(2008DX065J)
编辑概况：黄树成(1969－)，男，副教授、博士，主研方向：数据挖
掘，机器学习；朱霞，工程师、硕士
收稿日期：2010-08-06 E-mail：schuang6@sohu.com
第37 卷第 4 期黄树成，朱霞：数据流分类变化的分析和检测 79
则认为数据流没有发生概念漂移。
就数据块 Sm和Sn而言，如满足下式：
(( ) ( ( )) (( )
( ( ))
m n
k m k n k k j n
m n
j m j j
x S x S p p x S
x S p p
∀ ∈ → ∈ ∧ = ∧ ∀ ∈ →
∈ ∧ = (3)
则称Sm和Sn具有相同的分布；否则，若相同的对象被Sm和
Sn选中的概率不同，即：
( ) ( m n )
∀xk ∈ Sm ∧ Sn → pk ≠ pk (4)
则这种变化称为数据流的分布变化。
2.2 数据流中的变化情况
在实际应用中，数据流可能产生多种复合的变化，基本
变化的不同组合可以形成如下不同的复合情况：
D
C 0 1
0 00 01
1 10 11(+)
11(－)
其中，“D”和“C”分别表示分布变化和概念漂移；“1”
表示有变化，“0”表示没有变化。下面从最简单的情况开始，
逐一分析每种变化情况。
“00”是一种理想的情况。数据流是一个稳定的随机过
程，既没有概念漂移也没有分布变化。在这种情况下，没有
必要修改初始模型，对于新的数据，使用初始模型计算它们
的函数值，可以得到预期的准确度。“01”表示数据流仅发
生了分布变化。容易推出，虽然一个对象在不同数据块出现
的概率不同，但它们具有相同的类标。类似于“00”的情况，
不需要改变模型。“10”表明数据流仅发生概念漂移变化。
这种情况需要改变当前模型拟合新的数据流。为了获取新模
型的信息，必须投入适当的费用确定新数据流中一小部分对
象的真正类标。“11”表示数据流中既有分布变化又有概念
漂移。另外，根据分布变化和概念漂移的相关性，可细分成
2 种情况：若它们正相关，表示成“11(+)”；否则，表示成
“11(－)”。在“11(+)”的情况下，分布变化和概念漂移具
有相同的行为，仅需检测2 种变化的一种，因为知道分布变
化的量可得出概念漂移变化的程度，反之也成立。
2.3 训练数据的不充足性
数据流分类是一种监督学习，需要基于训练数据学习出
一个分类模型。为了构建一个准确的分类模型，需要收集充
足、类标已知的训练数据。
在数据流分类中，即使知道数据流发生了明显变化，但
及时组织充足的训练数据相当困难。由于训练数据的不充足，
因此得到的新模型会产生过度拟合问题，不能有效地拟合变
化的数据流。
当数据流发生变化时，当前模型无效，需要收集足够的
类标数据作为新的训练数据集。但是，类标数据的获得一般
很困难或需要较高的代价。
3 数据流变化的检测
根据是否需要知道新数据的类标，检测方法分成 2 类：
需要知道类标的称为直接方法，不需要知道类标的检测方法
称为间接方法。
3.1 直接方法
文献[5]给出的CVFDT 系统是一个典型的直接检测变化
的方法。直接方法可行的前提是新数据的类标可知，在实际
中实时地确定新数据的类标很难，必须设计专门的工具和投
入很高的费用调查它们。
当数据流动态变化时，直接方法将陷入一些困境：当数
据流变化很快且大于预定的频率时，被动的直接方法将无法
及时地捕获变化；如果数据流没有发生变化，直接方法仍然
周期地刷新当前模型，对资源造成浪费。
3.2 间接方法
文献[3]提出了2 种检测变化的间接方法：基于决策树叶
子节点的数据分布统计量(PS)和基于希望损失统计量(LS)。
通过形式化地分析可以得出这2 种间接方法在本质上是相同
的，都表示数据流中分布变化的大小，它们在大多数情况下
无效，仅在“11(+)”情况下，即概念漂移和分布变化正相关
时才有效。
PS 统计量是数据流中分布变化的度量。假设一个数据流
S ，dt 是一个由训练数据集D 构建的初始决策树，所有叶子
节点形成一个集合{ } 1 2 , , ,d L = l l 􀀢 l ，li (1≤i≤d)是任意第i个
叶子节点。每个对象可由一条从根节点到叶子节点的唯一路
径分类，该路径上的每个节点代表一个测试属性，所有测试
属性形成测试属性集；根据测试属性，所有相同类型的对象
从根节点开始，沿着相同的路径到达同一个叶子节点li ，得
到相同的类标。
假设 pD (li ) 是训练集D 中对象被叶子节点li 分类的概
率；pS (li ) 是数据流S 中对象被叶子节点li 分类的概率。显然，
D ( ) S ( ) 1
L L
p l p l
∈ ∈
Σ = Σ =
􀁁 􀁁
。如果数据流S 与训练集D 具有相同的
分布，那么，∀l ∈ L → pS (l) = pD (l)；如果分布不同，S 与D
相比发生了分布变化，变化的大小定义为：
| () ()|
100
2
S D
L
p l p l
PS ∈
Σ −
= 􀁁 × % (5)
下面验证它在不同情况下的有效性。
在“00”和“01”情况下，虽然后者具有分布变化，但
没有概念漂移，不同数据块中的相同对象具有相同的类标。
对于这2 种情况，无须改变当前的模型，因此，PS 方法没有
意义，即无效。如果是“10”情况，仅有概念漂移变化，即
PS ≈ 0，从统计意义上说，没有任何数据流发生变化的信号，
无法主动地采取相应的措施。所以，PS 方法无效。对于“11”
情况，既有分布变化又有概念漂移，根据两者的相关性，可
分成3 种集体的情况：正相关，负相关和不相关。在第1 种
情况下，概念漂移和分布变化具有相同的行为，PS 统计量的
度量同样可以充当概念漂移的统计量，即PS 对这种情况是
有效的；对于另外2 种情况，PS 方法无效。
LS 统计量本质上与PS 的作用相同，下面形式化地推导
和证明这一点。一般情况下，决策树的每个叶子节点都有一
定的分类错误，由分类错误造成的损失称为分类损失。S 与
D 相比，如果它们没有统计上的变化，可以使用当前模型在
训练数据集D 上的分类损失La 来估计在数据流S 上的预期
损失Le ，即Le ≈ La ，无须检查数据流S ；如果数据流S 和D
相比发生了明显的变化，决策树dt 在数据流S 上的分类损失
Le 与在训练集D 上的分类损失La有明显的不同。dt 的不同
叶子节点具有不同的分类错误概率，假设err ( )
pD l 为叶子节点
l 对训练数据D 的分类错误概率， La和Le 分别为模型对D 和
S 分类损失的累加：
err ( )
a D D
L
L p p l
∈
= Σ ×
􀁁
(6)
err ( )
e D S
L
L p p l
∈
= Σ ×
􀁁
(7)
由式(6)和式(7)可以推出：
80 计算 机 工 程 2011 年2 月20 日
| | | err ( ) err ( ) |
e a D S D D
L L
LS L L p p l p p l
∈ ∈
= − = Σ × − Σ × =
􀁁 􀁁
| () ()|
| ( ) ( ) | 1 100
S D
err L
D S D
L err
D
p l p l
p pl pl
p
∈
∈
Σ −
× Σ − = 􀁁 ×
􀁁
% ( 8 )
容易得出：式(5)和式(8)表示的多项式除了权重1/2 与
err
pD 不同，其他都相同。在本质上，LS 统计量与PS 统计量
的作用相同。可见，检测变化的2 种间接方法只能检测分布
变化的大小，它们对于概念漂移几乎没有意义；在不知新数
据某些样本类标的情况下，检测概念漂移是困难的，间接方
法是无效的。
笔者正在进行的工作考虑了这些重要的因素。通过投入
较低的费用，采用主动学习方法选择具有代表性的部分新数
据csi，确定它们的真正类标。有了代表性的样本数据，就可
以利用直接检测变化方法，可靠地检测出数据流是否发生变
化。如果有变化，采用半监督学习方法，利用无类标数据，
形成充分的训练数据集，构建出当前数据流的最优模型，与
文献[7]相比，无须构建3 个额外的模型。如果没有变化，有
2 种可能：(1)因csi 的质量不高导致变化没有被检测出来；
(2)确实没有变化。前一种情况再一次表明了如何选取部分新
数据作为调查对象的重要性；如果是后一种情况，只要把csi
的信息加入当前的模型，就可进一步提高模型的性能。
4 结束语
本文通过系统地分析数据流的各种变化情况，证明了
2 种主动检测变化的方法在本质上是相同的，都只能检测数
据流的分布变化，在多数情况下无效。因此，当数据流发生
概念漂移时，主动挖掘方法往往是不现实的。
通过采用主动学习方法，利用有限的资源可以组织高质
量的类标数据，降低训练数据的需求量。有了这些类标已知、
具有代表性的新数据，可以采用直接方法检测出数据流是否
发生了变化。如果有变化发生，使用这些新数据作为种子数
据，采用半监督学习方法，利用无类标数据扩大训练数据，
构建新的模型；如果没有明显的变化，只要将这些数据的信
息加入当前模型就能得到性能更优的模型。
参考文献
[1] Aggarwal C C. Data Streams: Models and Algorithms[M]. Berlin,
Germany: Springer, 2007.
[2] 袁正午, 袁松彪. 基于时空划分的数据流挖掘[J]. 计算机工程,
2010, 36(7): 61-62, 65.
[3] Fan Wei, Huang Yian, Haixun Wang, et al. Active Mining of Data
Streams[C]//Proc. of the 4th SIAM International Conference on
Data Mining. Lake Buena Vista, Florida, USA: [s. n.], 2004: 457-461.
[4] Zhu Xingquan, Zhang Peng, Lin Xiaodong, et al. Active Learning
from Data Streams[D]. Boca Raton, USA: Department of Computer
Science and Engineering, Florida Atlantic University, 2007.
[5] Hulten G, Spencer L, Domingos P. Mining Time-changing Data
Streams[C]//Proc. of Int’l Conf. on Knowledge Discovery and
Data Mining. San Francisco, USA: ACM Press, 2001.
[6] Bifet A, Holmes G, Pfahringer B, et al. New Ensemble Methods for
Evolving Data Streams[C]//Proc. of the 15th ACM SIGKDD
International Conference on Knowledge Discovery and Data
Mining. [S. l.]: ACM Press, 2009: 139-148.
[7] Fan Wen. Systematic Data Selection to Mine Concept-drift Data
Streams[C]//Proc. of ACM SIGKDD International Conference on
Knowledge Discovery and Data Mining. Toronto, Canada: [s. n.],
2004: 128-137.
编辑张正兴
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
(上接第77 页)
排序算法前和后的系统。引入上述方法后的结果由第3 节所
先容的排列方法按照5 条、15 条和若干条组成。
表 1 元搜索引擎改进前后结果数量对比
关键词 隐形关键词组系统 前 5 条结果前 20 条结果前 40 条结果
前4 11 18
数据库关系、表、排序
后 5 18 32
前4 16 33
递归算法、数列
后 5 19 36
数据 前3 16 30
挖掘
应用、算法、
模型 后 5 18 34
前4 15 25
排序数据、交换
后 5 20 35
前5 18 36
UML 关系、图
后 5 19 35
引入上述方法前，系统和一般元搜索引擎采用同样的搜
索机制。由表1 可以发现，系统引入多隐形关键词组和本文
排序方法后的查准率比之前有所提高，可以符合垂直搜索的
需要。但在一些词汇(如UML)的搜索上，比之前没有很大提
高，而且在结果增多的情况下查准率反倒下降。这是由于这
类词汇本身就具有很强的专业性，使这类词汇可以很好地区
分信息，增加的关键词信息不能提高信息区分度。
5 结束语
随着 Internet 信息的膨胀，综合性的搜索引擎越来越难
以满足用户的搜索要求。针对目前垂直搜索引擎查全率较低
的问题，本文提出了一种以元搜索引擎为基础，结合用户行
为监测、文本分析、数据挖掘、结果排序的垂直搜索引擎系
统结构。提出隐形关键词组的概念，并为多关键词搜索的排
序问题提出改进的位置排序算法。该结构使得元搜索引擎的
结果更加专业化。为今后垂直搜索引擎的构架提供了一种新
的解决思路。本文没有对数据挖掘策略做深入研究，下一步
可根据系统实际使用中的问题，调整数据挖掘策略以期得到
更高的效果。
参考文献
[1] Kim Yang Sok, Kang Byeong Ho, Compton P. Search Engine
Retrieval of Changing Information[C]//Proc. of International
World Wide Web Conference. Banff, Alberta, Canada: [s. n.],
2007: 1195-1196.
[2] 邓 凡. 基于元搜索引擎的专业搜索引擎的研究与实现[D].
西安: 西北大学, 2008.
[3] 罗 景, 涂新辉. 基于概率潜在语义分析的中文信息检索[J].
计算机工程, 2008, 34(2): 199-201.
[4] 郑 军, 王巍, 杨武, 等. 基于类间距离参数估计的文本
聚类评价方法[J]. 计算机工程, 2009, 35(9): 37-39.
[5] 傅鹤岗, 徐晨霞. 基于知网的元搜索引擎多关键词检索研究[J].
计算机工程与应用, 2008, 44(22): 152-154.
[6] 曹 林, 韩立新, 吴胜利. 元搜索引擎排序综述[J]. 计算机应
用研究, 2009, 26(2): 411-414.
编辑索书志