-
摘要: 概念漂移探测是数据流挖掘具有挑战意义的研究难点，属性约简是粗糙集理论的研究核心.从概念漂移的角度研究了粗糙集理论的属性约简，从粗糙集属性约简的角度研究了概念漂移，将概念漂移和属性约简进行分析比较，指出了它们之间的区别和联系.提出了基于属性依赖度和条件熵的概念漂移探测准则，并将两种常用的概念漂移探测准则与属性依赖度、条件熵探测准则进行了比较.属性依赖度和条件熵兼具分类准确率的可实验检验和联合概率分布可进行理论分析的优点，还可以进行属性约简（或特征选择）.实验结果显示，属性依赖度、条件熵和分类准确率都能有效地探测概念漂移，但是，与分类准确率相比，属性依赖度和条件熵在探测概念漂移时可以增加可重用性，减少工作量.属性约简和概念漂移之间关系的研究为属性约简、概念漂移的研究提供了新方法，为粗糙集、粒计算进一步融入大数据时代潮流提供了新思路.Abstract: Concept drift detection is a challenge to data stream mining, and attribute reduction is a focus of rough set theory. In this paper the phenomenon of concept drift is analyzed from the viewpoint of attribute reduction, and on the other hand, attribute reduction is analyzed deeply from the viewpoint of concept drift. The difference and the relation between concept drift and attribute reduction are investigated. Two criteria of concept drift detection, which rely on dependence of conditional attributes and conditional entropy, are presented. Analysis and comparison are conducted between two classical criteria of concept drift detection and two criteria of attribute reduction. Dependence of conditional attributes and conditional entropy possess the advantages of both testability of classification accuracy and theoretic analyzability of joint probability. Experimental results show that classification accuracy, dependence of conditional attributes and conditional entropy are valid and efficient for detecting concept drift. Moreover, compared with classification accuracy, the results can be reused and the workload can be reduced when dependence of conditional attributes and conditional entropy are employed to detect concept drift. The study on the relation between concept drift and attribute reduction provides a new method for attribute reduction and concept drift detection, as well as a new idea for rough set theory and granular computing to blend in the era of big data.
-
Key words:
- F-rough sets /
- data streams /
- concept drift /
- attribute reduction /
- conditional information entropy
-
现实中的数据往往随着时间推移而变化, 例如, 证券交易数据、微博、微信、视频、传感器数据等, 这种类型的数据称为数据流[1].数据流具有按照时间顺序排列、快速变化、海量甚至无限, 并且可能出现概念漂移现象等特征[2-3].概念漂移目前尚无统一定义, 是指数据流中概念(或目标变量的统计特性)的不稳定性、不确定性, 以及随着时间变化而变化的特征.数据流挖掘是当前数据挖掘研究的一个热点, 数据流分类和概念漂移探测是当前数据流挖掘的主要研究方向.
数据流的分类策略主要有:单一分类器[4-6]和集成分类器[3, 7-11].概念漂移的探测准则主要有:分类准确率和联合概率.无论是单一分类器还是集成分类器都常用分类准确率(或分类错误率)判断概念漂移, 将分类准确率低的分类器进行淘汰或改进, 从而提高分类效率.除了分类准确率外, 联合概率也常用于探测概念漂移[12-14].分类准确率往往用于通过实验分析探测概念漂移, 联合概率则往往用于从理论上对概念漂移进行分析或探测.
粗糙集理论[15-17]是一种处理不精确、不完全、含糊数据的有效数学工具, 是数据挖掘和分类的重要方法.属性约简与不确定性分析是粗糙集理论的两个重要应用.传统的粗糙集理论不太适合研究海量的、动态变化的数据, 也不太适合研究数据流; F-粗糙集[18-19]是第一个动态粗糙集模型, 它将粗糙理论从单个信息表或决策表推广到多个.与F-粗糙集相对应的属性约简方法是并行约简. F-粗糙集和并行约简比较适合研究动态变化的数据, 能够研究数据流和概念漂移.
利用粗糙集理论研究数据流和概念漂移比较少见.文献[20-21]利用粗糙集上下近似的变化去度量概念漂移, 这种从数据的结构角度度量概念漂移的方法, 难以进行移植和扩展, 也难以推广应用; 文献[22]把每个滑动窗口看成是一个决策子表, 利用F-粗糙集和并行约简的方法整体删除冗余属性, 通过比较不同子表之间的属性重要性变化探测概念漂移, 不受上下近似结构的限制, 具有很好的移植性和扩展性.除了并行约简之外, 粗糙集理论中还有很多种类的约简, 例如, Pawlak约简、互信息约简[23]、条件熵约简[24-25]等.粗糙集属性约简准则往往是不确定性分析的有力工具, 例如, 对应Pawlak约简、互信息约简、条件熵约简等的属性依赖度、互信息、条件熵等, 都是粗糙集理论分析数据不确定性的有力工具.但是, 能否直接用粗糙集属性约简准则探测概念漂移？属性约简与概念漂移有什么关系？受文献[22]启发, 本文努力揭示粗糙集理论的属性约简和概念漂移之间的内在联系.
本文首先从概念漂移的角度讨论了粗糙集的属性约简与概念漂移之间的联系和区别; 其次, 探讨粗糙集属性约简观点下的概念漂移准则与传统的概念漂移准则(包括分类准确率和联合概率)之间的区别与联系.在此基础上, 提出了属性依赖度和条件熵的概念漂移探测准则, 分析了条件熵和联合概率在探测概念漂移方面的联系.理论分析和实验结果显示, 与分类准确率一样, 属性依赖度和条件熵能有效地探测概念漂移.属性依赖度和条件熵具有联合概率进行理论分析的优点, 又具有分类准确率进行实验分析比较的优点, 并且可以增加可重用性、减少工作量.
1. 基础知识
本节简单介绍粗糙集[15-17]、F-粗糙集和并行约简[18-19]的基本知识.
1.1 粗糙集
$IS=(U, A) $是一个信息系统, 其中$U$是论域, $A$是论域$U$上的条件属性集.对于每个属性$a\in A$都对应一个函数$a:U\rightarrow V_{a}$, $V_{a}$称为属性$a$的值域, $U$中每个元素称为个体、对象或行.
对于每一个属性子集$B\subseteq A$和任何个体$x\in U$都对应一个如下的信息函数:
$ Inf_{B}(x)=\{(a, a(x)):a\in B\} $
$B$-不分明关系(或称为不可区分关系)定义为
$ IND(B)=\{(x, y):Inf_{B}(x)=Inf_{B}(y)\} $
任何满足关系$IND(B) $的两个元素$x$, $y$都不能由属性子集$B$区分, $[x]_{B}$表示由$x$引导的$IND(B) $等价类.
对于信息系统$IS=(U, A) $、属性子集$B\subseteq A$和概念$X\subseteq U$, 有
$ \begin{align*} &\underline{B}(X)=\underline{B}(IS, X)=\{x\in U: [x]_{B}\subseteq X\}\\ &\overline{B}(X)=\overline{B}(IS, X)=\{x\in U: [x]_{B}\cap X\neq \emptyset\}\end{align*} $
分别称为$B$-下近似和$B$-上近似. $B$-下近似也称为正区域, 记为$POS_{B}(X) $.序偶$(\underline{B}(X), \overline{B}(X)) $称为粗糙集.
在决策系统$DS=(U, A, d) $中, $\{d\}\cap A=\emptyset$, 决策属性$d$将论域$U$划分为块, $U/\{d\}=\{Y_{1}, Y_{2}$, $\cdots$, $Y_{M}\}$, 其中$Y_{i}$ $(i=1, 2, \cdots, M) $是等价类.决策系统$DS=(U, A, d) $的正区域定义为$POS_{A}(d)$ $=$ $\bigcup_{Y\in U/\{d\}}\underline{A}(Y) $.
有时决策系统$DS=(U, A, d) $的正区域$POS_{A}(d) $也记为$POS_{A}(DS, d) $或$POS(DS, A$, $d) $.
定义 1[15-17]. 在决策系统$DS=(U, A, d) $中, 称决策属性$d$以程度$h$ $(0\leq h\leq 1) $依赖条件属性集$A$, 其中,
$ h=\gamma(DS, A, d)=\frac{|POS_{A}(d)|}{|U|} $
符号$|\cdot|$表示集合的势.
1.2 F-粗糙集
F-粗糙集[18-19]和其他任何粗糙集模型不同, 它是关于信息系统簇或决策系统簇的粗糙集模型, 这个粗糙集模型比较适合并行计算, 也适合研究事物的动态变化.
下面用$FIS=\{IS_{i}\}$ $(i=1, 2, \cdots, n) $表示与决策系统簇$F=\{DT_{i}\}$相对应的信息系统簇, 其中$IS_{i}$ $= (U_{i}, A) $, $DT_{i}=(U_{i}, A, d) $.
定义 2[18-19]. 假设$X$是一个在不同情形下可能发生变化的概念(即$X$是一个概念变量), $N$是一种情形, $X|N$表示在情形$N$下的概念$X$.在一个信息系统簇$FIS=(IS_{1}, IS_{2}, \cdots, IS_{n}) $中, $X|IS_{i}=$ $X\cap IS_{i}$, $X|FIS=\{X|IS_{1}, X|IS_{2}, \cdots, X|IS_{n}\}$.如果不引起混淆, $X|N$可以缩写为$X$.
假设$X$是信息系统簇$FIS$中的一个概念, 那么$X$关于属性子集$B\subseteq A$的上近似、下近似、边界线区域和负区域的定义如下:
$ \overline{B}(FIS, X)=\{\{x\in U_{i}:[x]_{B}\cap X\neq \emptyset, X\subseteq U_{i}\}:i=1, 2, \cdots, n\}; $
$ \underline{B}(FIS, X)=\{\{x\in U_{i}:[x]_{B}\subseteq X, X\subseteq U_{i}\}:i$ $=1, 2, \cdots, n\}; $
$ BND(FIS, X)=\{\{x\in \overline{B}(IS_{i}, X)-\underline{B}(IS_{i}, $ $X):$ $X \subseteq U_{i}\}:i=1, 2, \cdots, n\}; $
$ NEG(FIS, X)=\{\{x\in U_{i}-\overline{B}(IS_{i}, X):X$ $\subseteq$ $U_{i}\}:$ $i=1, 2, \cdots, n\}. $
概念$X$关于信息系统簇$FIS$的上下近似、边界线区域、负区域分别是$FIS$中的信息子系统关于概念$X$的上下近似、边界线区域、负区域组成的集合.序偶$(\underline{B}(FIS, X), \overline{B}(FIS, X)) $称为F-粗糙集.如果$\underline{B}(FIS, X)=\overline{B}(FIS, X) $则称序偶$(\underline{B}(FIS$, $X)$, $\overline{B}(FIS, X)) $是精确的.
定义 3[18-19]. 设$F$是一个决策系统簇, $F$的正区域定义如下:
$ POS(F, A, d)=\{POS(DT, A, d):DT\in F\} $
定义 4[18-19]. 设$F$是一个决策系统簇, 称$B$ $\subseteq$ $A$为$F$的并行约简当且仅当满足下面条件:
1) $POS(F, B, d)=POS(F$, $A$, $d) $;
2) 对任意$S\subset B$, 都有$POS(F, S, d)\neq POS(F, A, d). $
2. 概念漂移准则分析与比较
概念漂移的评判准则主要分析比较以下三种:
1) 分类准确率(或分类错误率).如果分类器对数据集的分类准确率有较大的变化, 一般情况下是指分类准确率下降, 而且超过了一定的阈值, 则称发生了概念漂移.分类准确率是最常用的一种概念漂移探测准则, 常常用于实验分析中.
使用分类准确率的变化判断是否发生概念漂移, 是一种使用概念漂移的结果进行判断的方法, 也是使用最广泛的方法.这种方法依赖实验或实际应用, 能够从总体上把握概念漂移, 无论是在单一分类器还是集成分类器中都使用最广泛.但是, 对于同一训练集得到的分类器, 对于同一测试集, 如果特征选择不同, 则实验结果可能不同.
2) 联合概率.联合概率$p(X, Y)=p(X)p(Y|$$X)$ (其中, $X$表示由条件属性诱导的概念, $Y$表示由决策属性诱导的概念)发生变化, 而且超过一定的阈值.用联合概率作为概念漂移检测准则又分为虚拟漂移和真实漂移.虚拟漂移[12, 14]是指在联合概率中$p(Y|X) $不发生变化, 仅$p(X) $变化; 真实漂移[13-14]是指在联合概率中$p(X) $不发生变化, 而$p(Y|X) $发生变化.
联合概率的准则也较常用.这种准则因为有较强的数学理论基础(统计理论与概率论), 所以, 从理论方面研讨概念漂移, 人们喜欢使用联合概率的准则.但是, 这个准则局限于某些概念, 缺乏灵活性, 对于整个数据集而言就不太实用.这是因为联合概率$p(X, Y) $只能针对某些特定的$\langle X, Y\rangle$研究其变化, 而整个数据集可能是一系列的有序对, 它们的概率分布并不相同, 也很难用同一个表达式表示, 如果用联合概率$p(X, Y) $研究其变化, 难以从总体上把握概念漂移.
3) 属性重要性.用属性重要性变化探测概念漂移是文献[22]新提出来的.属性重要性是数据的内部属性, 是概念的内涵.用属性重要性准则探测概念漂移, 分析属性重要性随着数据的变化而变化, 不直接依赖于概念的外延, 而且用并行约简进行特征选择, 统一了比较准则, 避免了特征选择不同对概念漂移探测产生的负面影响, 所以, 用属性重要性准则探测概念漂移, 既有确定性, 又有灵活性; 既能用于实验检测, 又能用于理论分析, 兼具有分类准确率准则和联合概率准则的优点.
文献[22]定义的基于属性重要性的概念漂移准则, 探测了并行约简后各个属性重要性的变化而引起的概念漂移, 但是文献[22]中单个属性重要性的变化不能全面反映数据流中的概念漂移.为了更好地与分类准确率、联合概率分布进行比较, 本文定义和使用属性依赖度和条件熵作为概念漂移探测准则.
3. 属性约简与概念漂移的对比与分析
粗糙集中有很多种类的属性约简, 其中最常用的是基于正区域的属性约简和基于互信息的属性约简.这些属性约简的准则, 从概念漂移的角度看, 就是在同一数据集中保持在属性约简准则下不发生概念漂移的最小属性子集.但是各种准则并不一定兼容, 有时一个准则可能违背另一个准则, 也就是说, 在一个准则下不发生概念漂移的约简, 在另一个准则下可能发生概念漂移.实际上, 基于互信息的属性约简等价于基于条件熵的属性约简, 但是因为条件熵比互信息更接近联合概率, 所以, 本文以基于正区域的属性约简和基于条件熵的属性约简为例进行阐述.
定义 5[15-17]. 给定一个决策系统$DS= (U, A$, $d) $, $B\subseteq A$称作决策系统$DS$的一个约简当且仅当$B$满足如下两个条件:
1) $POS(DS, B, d)=POS(DS, A, d) $;
2) 对任意$S\subset B$, 都有$POS(DS, S, d)\neq POS(DS, A, d) $.
定义 6[15-17]. 给定一个决策系统$DS=(U, A$, $d) $, $B\subseteq A$称作决策系统$DS$的一个约简, 当且仅当$B$满足如下两个条件:
1) $\gamma(DS, B, d)=\gamma(DS, A, d) $;
2) 对任意的$S\subset B$, 均有$\gamma(DS, S, d)\neq$ $\gamma(DS$, $A, d)$.
定义5从正区域的结构出发定义了属性约简, 定义6从属性依赖度角度定义了属性约简; 定义5适合理解, 定义6适合计算.从概念漂移角度看, 定义5的条件属性约简保证决策系统正区域不发生改变, 保证正区域部分的条件概率$p(Y|X)=1$, 即正区域部分不发生真实概念漂移; 定义6的条件属性约简保证了决策系统的属性依赖度不发生概念漂移; 定义5只适合于单个决策表本身, 不适合推广.定义6可以从决策子表簇角度进行推广, 适合于探测决策子表簇中概念漂移.所以, 在决策子表簇中可以将基于属性依赖性的概念漂移准则定义如下:
定义 7.在决策子表簇$F$中, $DT_{i}, DT_{j}\in F$相对于属性依赖度的概念漂移定义为
$ DACD(DT_{i}, DT_{j})=|\gamma(DT_{i}, A, d)-\gamma(DT_{j}, A, d)| $
定义 8[24-25]. 给定一个决策系统$DS=(U$ $A, d) $, 设$A$和$\{d\}$在论域$U$上导出的划分分别为$X$和$Y$, 其中, $X=U/A=\{X_{1}, X_{2}, \cdots, X_{N}\}$, $Y$ $= U/\{d\}=\{Y_{1}, Y_{2}, \cdots, Y_{M}\}$, $p(X_{i})={|X_{i}|}/{|U|}$, $p(Y_{j})$ $={|Y_{j}|}/{|U|}$, $p(X_{i}, Y_{j})={|X_{i}\cap Y_{j}|}/{|U|}$, $i=1$, $2$, $\cdots, N$, $j=1, 2, \cdots, M$. $A$和$\{d\}$的信息熵分别定义为
$ \begin{align*} &H(DS, A)=-\sum\limits_{i=1}^{N}p(X_{i})lbp(X_{i})\\ &H(DS, \{d\})=-\sum\limits_{j=1}^{M}p(Y_{j})lbp(Y_{j})\end{align*} $
$\{d\}$相对于$A$的条件熵定义为
$ \begin{align*}&H(DS, \{d\}|A)=\\&\qquad-\sum\limits_{i=1}^{N}p(X_{i})\sum\limits_{j=1}^{M}p(Y_{j}|X_{i})lbp(Y_{j}|X_{i}) \end{align*} $
定义 9[24-25].给定一个决策系统$DS=(U, A$, $d) $, 若$B\subseteq A$满足下列两个条件:
1) $H(DS, \{d\}|A)=H(DS, \{d\}|B) $;
2) 对任意$b\in B$, 都有$H(DS, \{d\}|B) < H(DS$, $\{d\}|B-\{b\}).$
则称$B$是$A$的一个基于条件熵的相对约简.
定理 1.给定一个决策系统$DS=(U, A, d) $, $B_{1}$ $\subset B_{2}\subseteq A$, 由$B_{1}$, $B_{2}$导出的划分分别为$U/B_{1}=$ $\{X_{1}, X_{2}, \cdots, X_{N}\}$, $U/B_{2}=\{X'_{1}, X'_{2}, \cdots, X'_{M}\}$, 则联合概率有如下关系: $p(X'_{l}, Y_{j})\leq p(X_{k}, Y_{j}) $, 其中$X'_{l}$ $=[x]_{B_{2}}\in U/B_{2}$, $X_{k}= [x]_{B_{1}}\in U/B_{1}$, $Y_{j}\in$ $U/\{d\}$.
证明.对于$U/B_{1}=\{X_{1}, X_{2}, \cdots, X_{N}\}$中的每一块, 要么等于$U/B_{2}=\{X'_{1}, X'_{2}, \cdots, X'_{M}\}$中的某一块, 要么是某几块的并.不失一般性, 有$X'_{l}=$ $[x]_{B_{2}}\subseteq [x]_{B_{1}}=X_{k}$, 所以有${|X'_{l}\cap Y_{j}|}/{|U|}\leq$ $|X_{k}$ $\cap$ $Y_{j}|/{|U|}$, 即$p(X'_{l}, Y_{j})\leq p(X_{k}, Y_{j}) $.
关于在一个系统中的条件熵随条件属性的变化, 有下面引理:
引理 1[25].给定一个决策系统$DS=(U, A, d) $, $B_{1}$ $\subset B_{2} \subseteq A$, 则有
$ H(DS, \{d\}|B_{2})\leq H(DS, \{d\}|B_{1}) $
成立.
定理1和引理1说明, 在一个决策系统中, 联合概率与条件熵都是随着条件属性的增加而单调不增.根据文献[26]的属性约简准则, 条件熵可以作为属性约简的准则, 联合概率也可以作为属性约简的准则; 类似地, 联合概率可以作为概念漂移的准则, 条件熵也可以作为概念漂移的准则.
定义 10. 在决策子表簇$F$中, $DT_{i}, DT_{j}\in F$相对于条件熵的概念漂移定义为
$ \begin{align*} &IECD(DT_{i}, DT_{j})=\\ &\qquad |H(DT_{i}, \{d\}|A)-H(DT_{j}, \{d\}|A)|\end{align*} $
定理 2. 在决策子表簇$F$中, $B\subseteq A$是$F$相对于条件熵的并行约简, $DT_{i}, DT_{j}\in F$, 则约简后相对于条件熵的概念漂移等于约简前的概念漂移, 即
$ \begin{align*}&IECD(DT_{i}, DT_{j})=\\ &\qquad |H(DT_{i}, \{d\}|B)-H(DT_{j}, \{d\}|B)|\end{align*} $
定理 3. 在决策子表簇$F$中, $B\subseteq A$是$F$相对于属性依赖度的并行约简, $DT_{i}, DT_{j}\in F$, 则约简后相对于属性依赖度的概念漂移等于约简前的概念漂移, 即
$ \begin{align*}&DACD(DT_{i}, DT_{j})=\\ &\qquad |\gamma(DT_{i}, B, d)-\gamma(DT_{j}, B, d)|\end{align*} $
定理2和定理3根据相关定义可以非常容易证明.定理2和定理3说明, 在条件熵和属性依赖度等属性约简的条件下, 并行约简不会影响概念漂移的度量和探测, 并且并行约简可以将冗余属性删除, 减少计算量, 彰显对概念漂移发生起作用的条件属性.
通过以上分析和论述, 粗糙集和F-粗糙集的属性约简准则可以推广用于概念漂移的度量和探测.概念漂移和属性约简存在一定的内在联系, 属性约简是保证单个决策表或决策表簇内部不发生概念漂移的最小属性子集, 而一般情况下的概念漂移则是不同的数据集或变化的数据集之间某种度量发生变化而产生的.
与$\langle X, Y\rangle$的联合概率一样, $\langle X, Y\rangle$的条件熵也可以定义概念漂移:
定义 11. 在决策子表簇$F$中, $DT_{i}$, $DT_{j}\in F$, 其中$DT_{i}=(U_{i}, A, d) $, $DT_{j}=(U_{j}, A, d) $, $X\in U_{i}/$ $A$, $Y\in U_{i}/\{d\}$, $X'\in U_{j}/A$, $Y'\in U_{j}/\{d\}$, 并设$X$与$X'$、$Y$与$Y'$内涵相同(即它们对应的属性值相等), 则$\langle X, Y\rangle$的条件熵概念漂移定义为$PIECD(X, Y, X', Y')=|p(X')$ $p(Y'|X')lbp(Y'|$ $X')$ - $p(X)p(Y|X)lbp(Y|X)|.$
与决策表中的条件熵一样, $\langle X, Y\rangle$的条件熵也满足单调性, 根据文献[26]属性约简准则, 可以根据$\langle X, Y\rangle$的条件熵对单个的概念进行约简, 相应地, $\langle X, Y\rangle$的条件熵可以度量单个概念的概念漂移.
下面讨论联合概率与条件熵在探测概念漂移方面的关系.
定理 4. 在决策子表簇$F$中, $DT_{i}$, $DT_{j}\in F$, 其中$DT_{i}=(U_{i}, A, d) $, $DT_{j}=(U_{j}, A, d) $, $X\in U_{i}/A$, $Y\in U_{i}/\{d\}$, $X'\in U_{j}/A$, $Y'\in U_{j}/\{d\}$, 并设$X$与$X'$、$Y$与$Y'$内涵相同(对应的属性值相等).用联合概率准则探测发生虚拟概念漂移, 则用条件熵准则也发生虚拟概念漂移; 若用联合概率准则发生真实概念漂移, 则用条件熵准则也同样发生真实概念漂移.
证明.反设用联合概率准则没有发生概念漂移, 即$p(X, Y)=p(X', Y') $, $p(X)p(Y|X)=p(X')$ $\times$ $p(Y'|X') $,
令$p(X)=kp(X') $, 则$p(Y|X)=p(Y'|X')/k $.从而
$ \begin{align*}&p(X)p(Y|X)lbp(Y|X)=\\&\qquad kp(X')\frac{1}{k}p(Y'|X')(lbp(Y'|X')-lbk)=\\&\qquad p(X')p(Y'|X')(lbp(Y'|X')-lbk)\end{align*} $
1) 在$p(X) $不变, 即$p(X)=p(X') $的情况下:
a) 若$p(X, Y)=p(X', Y') $, 则必有
$ \begin{align*}&p(X)p(Y|X)lbp(Y|X)=\\&\qquad p(X')p(Y'|X')lbp(Y'|X') \end{align*} $
b) 若$p(X, Y)\neq p(X', Y') $, 则必有
$ p(X)p(Y|X)lbp(Y|X) \ne p(X')p(Y'|X')lbp(Y'|X') $
2) 在$p(Y|X) $不变, 即$p(Y|X)=p(Y'|X') $的情况下.
a) 若$p(X, Y)=p(X', Y') $, 则必有
$ \begin{align*}&p(X)p(Y|X)lbp(Y|X)=\\&\qquad p(X')p(Y'|X')lbp(Y'|X') \end{align*} $
b) 若$p(X, Y)\neq p(X', Y') $, 则必有
$ \begin{align*}&p(X)p(Y|X)lbp(Y|X)\neq\\&\qquad p(X')p(Y'|X')lbp(Y'|X') \end{align*} $
定理4说明, 用联合概率分布能探测到的虚拟概念漂移和真实概念漂移都能用条件熵探测.从上述推理过程可知, 定理4的逆定理也成立.
例1. 设$F=\{DT_{1}, DT_{2}\}$, 如表 1和表 2所示. $a$, $b$, $c$是条件属性, $d$是决策属性.
表 1 决策子系统DT1Table 1 A decision subsystem DT1U1 a b c d x1 0 0 1 1 x2 1 1 0 1 x3 0 1 0 0 x4 1 1 0 1 表 2 决策子系统DT2Table 2 A decision subsystem DT2U2 a b c d y1 0 1 0 0 y2 1 1 0 1 y3 1 1 0 1 y4 0 1 0 0 y5 1 2 0 0 y6 1 2 0 1 显然, $F$的并行约简为
$ \begin{align*}&B=\{a, b\}\\&DT_{1}/\{d\}=\{\{x_{1}, x_{2}, x_{4}\}, \{x_{3}\}\} \\&DT_{1}/B=\{\{x_{1}\}, \{x_{2}, x_{4}\}, \{x_{3}\}\}\\&DT_{2}/\{d\}=\{\{y_{1}, y_{4}, y_{5}\}, \{y_{2}, y_{3}, y_{6}\}\}\\&DT_{2}/B=\{\{y_{1}, y_{4}\}, \{y_{2}, y_{3}\}, \{y_{5}, y_{6}\}\} \end{align*} $
于是,
$ \begin{align*} &\gamma(DT_{1}, B, d)=1\\&\gamma(DT_{2}, B, d)=\frac{2}{3} \\& DACD(DT_{1}, DT_{2})=|\gamma(DT_{1}, B, d)\, -\\&\qquad\gamma(DT_{2}, B, d)|=\frac{1}{3} \\& H(DT_{1}, \{d\}|B)=\\&\qquad-\sum\limits_{i=1}^{3}p(X_{i}) \sum\limits_{j=1}^{2}p(Y_{j}|X_{i})lbp (Y_{j}|X_{i})=0\\& H(DT_{2}, \{d\}|B)=\\&\qquad-\sum\limits_{i=1}^{3}p(X_{i}) \sum\limits_{j=1}^{2}p(Y_{j}|X_{i})lbp(Y_{j}|X_{i})=\frac{1}{3} \\&IECD(DT_{1}, DT_{2}) =|H(DT_{1}, \{d\}|B)\, - \\&\qquad H(DT_{2}, \{d\}|B)|=\frac{1}{3}\end{align*} $
从例1可以看出, 无论是从属性依赖度还是从条件熵的角度, 只要选取的参数$\delta < {1}/{3}$, 两种标准都发生了概念漂移.
由此可见, 概念漂移和属性约简具有内在的联系.概念漂移探测的有些准则(例如联合概率)能够用于属性约简, 反过来, 属性约简的准则(例如属性依赖度和条件熵)也能用于概念漂移探测.属性约简就是保证某种准则下不发生概念漂移的删除冗余属性过程.然而, 作为不确定性度量指标的属性依赖度仅考虑正区域部分的数据, 不考虑非正区域部分的数据, 无论是在属性约简方面还是在探测概念漂移方面都忽略了非正区域数据的变化; 而条件熵则把所有的数据都考虑在内, 在属性约简和概念漂移探测上全盘考虑了数据的变化.所以, 我们推测, 大部分条件属性约简准则能够用于概念漂移探测, 能够用于数据流概念漂移探测的属性约简准则应该满足不依赖于数据的结构, 但不同的不确定性指标在属性约简和概念漂移探测方面各具特色.深入分析其他的属性约简准则是否能够用于概念漂移探测, 以及研究它们在概念漂移探测方面的区别与联系, 是我们下一步研究的内容.
下一节将通过实验比较属性依赖度、条件熵和两种特征选择(属性约简)后的分类准确率作为概念漂移探测准则.这两种特征选择分别是基于属性依赖度的属性约简和基于条件熵的属性约简.
4. 实验结果与分析
实验数据为KDD-CUP991网络入侵检测数据10%的子集.该数据包含494 021条记录, 42个属性.实验中滑动窗口的大小分别为5 000和10 000, 相邻窗口之间有或无10%的重复率, 实验中将第一个数据集(滑动窗口)当成训练集, 其余的数据集都是测试集.
1http://kdd.ics.uci.edu/databases/kddcup99/kddcup99.html
理论分析和实验结果显示, 分类准确率和属性依赖度都属于[0, 1], 而条件熵的值可以大于1, 实验结果也证实了这一点.
图 1~4虽然只是显示了这几种准则相对于训练集的值, 没有直接显示概念漂移, 但只要这些指标数值和训练集相应的指标数值相减, 然后取绝对值, 并与阈值(可以根据需要自己设定)进行比较, 就可以很容易判定是否发生概念漂移.而且图 1~4非常明显地显示, 特征选择不同, 对同一个数据集的分类准确率不同.
图 1 滑动窗口的大小为10 000, 且相邻窗口之间没有重复Fig. 1 The size of sliding windows is 10 000 without repeat
图 2 滑动窗口的大小为5 000, 且相邻窗口之间没有重复Fig. 2 The size of sliding windows is 5 000 without repeat
图 3 滑动窗口的大小为5 000, 且相邻窗口之间有10 %的重复Fig. 3 The size of sliding windows is 5 000 with 10 % repeat
图 4 滑动窗口的大小为10 000, 且相临窗口之间有10 %的重复Fig. 4 The size of sliding windows is 10 000 with 10 % repeat图 1~4显示基于属性重要度/条件熵的分类准确率和属性依赖度的整体变化趋势不如条件熵明显, 所以条件熵能更加准确地探测概念漂移.
图 1显示在第10~27个滑动窗口, 基于属性重要度/条件熵的分类准确率的值为0, 属性依赖度的值接近于0, 变化趋势不明显, 均不利于探测概念漂移; 在第10~22个滑动窗口, 条件熵的变化也不明显, 但在探测概念漂移过程中, 条件熵优于分类准确率和属性依赖度.
图 2显示在第25~43个滑动窗口, 基于属性重要度/条件熵的分类准确率的值为0, 属性依赖度的值接近于0, 变化趋势很不明显, 不利于探测概念漂移; 虽然在第32~38个滑动窗口, 条件熵的变化趋势很小, 但是在探测概念漂移的过程中, 条件熵优于上述三种方法.
图 3显示在第30~50个滑动窗口, 基于属性重要度/条件熵的分类准确率的值为0;在第35~65个滑动窗口, 属性依赖度的值趋近于0, 且变化趋势不大; 在第40~50个滑动窗口, 条件熵的变化趋势也不明显.但是, 条件熵变化不明显的滑动窗口数目较少, 因此, 条件熵作为概念漂移的探测准则较优.
图 4显示在第15~33个滑动窗口, 基于属性重要度/条件熵的分类准确率的值为0, 属性依赖度的变化较小, 均不利于探测是否发生了概念漂移; 条件熵的变化能有效的探测概念漂移.
从图 1~4可以看出, 使用这些指标都可以在一定的程度上判定是否发生概念漂移, 但分类准确率只能与训练集比较, 相邻两个滑动窗口(数据集)之间相对于分类准确率是否发生概念漂移, 只能以一个为训练集, 另一个为测试集, 工作量相当大, 而且没有对称性; 如果将两个相邻滑动窗口相对于训练集的分类准确率之差进行概念漂移探测, 那么很多时候都不利于探测概念漂移.然而使用属性依赖度和条件熵作为概念漂移的判定标准, 在元素个数和属性集不发生变化的情况下, 每个决策表的属性依赖度和条件熵都是不变的, 属性约简也不影响它们的值, 任何两个数据集(滑动窗口)之间都可以进行比较, 而且具有对称性和可重用性, 从而可以减少工作量.
5. 结论与展望
本文从F-粗糙集和概念漂移的角度, 揭示了概念漂移和粗糙集属性约简之间的区别与联系.属性约简是在一个信息表内部保持不发生概念漂移的最小属性子集.本文提出了基于属性依赖度和条件熵的概念漂移探测准则, 理论分析显示粗糙集的属性约简准则大部分都可用于度量概念漂移, 属性依赖度和条件熵具有联合概率分布可进行理论分析的优点, 又具有分类准确率可进行实验分析的优点, 即将粗糙集的属性约简准则用于概念漂移的探测兼具两种传统的的概念漂移准则的优点.此外, 属性依赖度和条件熵作为概念漂移探测准则还具有对称性和可重用性, 从而可以减少工作量.所以, F-粗糙集是研究数据流分类和概念漂移, 进行数据流分析的非常好的理论和实践工具.将F-粗糙集和粗糙集属性约简准则用于数据流挖掘及概念漂移探测, 丰富了数据流挖掘和概念漂移探测的工具, 同时, 对粗糙集及粒计算理论的发展与应用将起促进作用.
下一步研究重点是将F-粗糙集进一步运用于概念漂移探测和数据流分类, 特别是集成分类器的分类研究, 并深入研究这些概念漂移准则之间的关系.
-
图 1 滑动窗口的大小为10 000, 且相邻窗口之间没有重复
Fig. 1 The size of sliding windows is 10 000 without repeat
图 2 滑动窗口的大小为5 000, 且相邻窗口之间没有重复
Fig. 2 The size of sliding windows is 5 000 without repeat
图 3 滑动窗口的大小为5 000, 且相邻窗口之间有10 %的重复
Fig. 3 The size of sliding windows is 5 000 with 10 % repeat
图 4 滑动窗口的大小为10 000, 且相临窗口之间有10 %的重复
Fig. 4 The size of sliding windows is 10 000 with 10 % repeat
表 1 决策子系统DT1
Table 1 A decision subsystem DT1
U1 a b c d x1 0 0 1 1 x2 1 1 0 1 x3 0 1 0 0 x4 1 1 0 1 
下载: 导出CSV
表 2 决策子系统DT2
Table 2 A decision subsystem DT2
U2 a b c d y1 0 1 0 0 y2 1 1 0 1 y3 1 1 0 1 y4 0 1 0 0 y5 1 2 0 0 y6 1 2 0 1
下载: 导出CSV
-
[1] Babcock B, Babu S, Datar M, Motwani R, Widom J. Models and issues in data stream systems. In:Proceedings of the 21st ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems. Madison, Wisconsin, USA:ACM, 2002. 1-16 [2] 王涛, 李舟军, 颜跃进, 陈火旺.数据流挖掘分类技术综述.计算机研究与发展, 2007, 44(11):1809-1815 http://d.old.wanfangdata.com.cn/Periodical/jsjyjyfz200711001Wang Tao, Li Zhou-Jun, Yan Yue-Jin, Chen Huo-Wang. A survey of classification of data streams. Journal of Computer Research and Development, 2007, 44(11):1809-1815 http://d.old.wanfangdata.com.cn/Periodical/jsjyjyfz200711001 [3] 徐文华, 覃征, 常扬.基于半监督学习的数据流集成分类算法.模式识别与人工智能, 2012, 25(2):292-299 doi: 10.3969/j.issn.1003-6059.2012.02.016Xu Wen-Hua, Qin Zheng, Chang Yang. Semi-supervised learning based ensemble classifier for stream data. Pattern Recognition and Artificial Intelligence, 2012, 25(2):292-299 doi: 10.3969/j.issn.1003-6059.2012.02.016 [4] Lu N, Zhang G Q, Lu J. Concept drift detection via competence models. Artificial Intelligence, 2014, 209:11-28 doi: 10.1016/j.artint.2014.01.001 [5] Domingos P, Hulten G. Mining high-speed data streams. In:Proceedings of the 6th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Boston, Massachusetts, USA:ACM, 2002. 71-80 [6] Hulten G, Spencer L, Domingos P. Mining time-changing data streams. In:Proceedings of the 7th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. San Francisco, California, USA:ACM, 2001. 97-106 [7] 孙岳, 毛国君, 刘旭, 刘椿年.基于多分类器的数据流中的概念漂移挖掘.自动化学报, 2008, 34(1):93-97 http://www.aas.net.cn/CN/abstract/abstract16029.shtmlSun Yue, Mao Guo-Jun, Liu Xu, Liu Chun-Nian. Mining concept drifts from data streams based on multi-classifiers. Acta Automatica Sinica, 2008, 34(1):93-97 http://www.aas.net.cn/CN/abstract/abstract16029.shtml [8] Wang H X, Fan W, Yu P S, Han J W. Mining concept-drifting data streams using ensemble classifiers. In:Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Washington, D.C., USA:ACM, 2003. 226-235 [9] Li P P, Wu X D, Hu X G, Wang H. Learning concept-drifting data streams with random ensemble decision trees. Neurocomputing, 2015, 166:68-83 doi: 10.1016/j.neucom.2015.04.024 [10] 张明卫, 朱志良, 刘莹, 张斌.一种大数据环境中分布式辅助关联分类算法.软件学报, 2015, 26(11):2795-2810 http://d.old.wanfangdata.com.cn/Periodical/rjxb201511005Zhang Ming-Wei, Zhu Zhi-Liang, Liu Ying, Zhang Bin. Distributed assistant associative classification algorithm in big data environment. Journal of Software, 2015, 26(11):2795-2810 http://d.old.wanfangdata.com.cn/Periodical/rjxb201511005 [11] Bifet A, Holmes G, Pfahringer B, Kirkby R, Gavaldá R. New ensemble methods for evolving data streams. In:Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Paris, France:ACM, 2009. 139-148 [12] Gao J, Fan W, Han J W, Yu P S. A general framework for mining concept-drifting data streams with skewed distributions. In:Proceedings of the 2007 SIAM International Conference on Data Mining. Minnesota, USA:SIAM, 2007. [13] Widmer G, Kubat M. Effective learning in dynamic environments by explicit context tracking. In:Proceedings of the 1993 European Conference on Machine Learning. Vienna, Austria:Springer, 1993. 227-243 [14] 柴玉梅, 周驰, 王黎明.数据流上概念漂移的检测和分类.小型微型计算机系统, 2011, 32(3):421-425 http://d.old.wanfangdata.com.cn/Periodical/xxwxjsjxt201103008Chai Yu-Mei, Zhou Chi, Wang Li-Ming. Detecting concept drift and classifying data streams. Journal of Chinese Computer Systems, 2011, 32(3):421-425 http://d.old.wanfangdata.com.cn/Periodical/xxwxjsjxt201103008 [15] Pawlak Z. Rough sets. International Journal of Computer and Information Sciences, 1982, 11(5):341-356 doi: 10.1007/BF01001956 [16] 张清华, 薛玉斌, 王国胤.粗糙集的最优近似集.软件学报, 2016, 27(2):295-308 http://d.old.wanfangdata.com.cn/Periodical/rjxb201602008Zhang Qing-Hua, Xue Yu-Bin, Wang Guo-Yin. Optimal approximation sets of rough sets. Journal of Software, 2016, 27(2):295-308 http://d.old.wanfangdata.com.cn/Periodical/rjxb201602008 [17] 王国胤. Rough集理论与知识获取.西安:西安交通大学出版社, 2001.Wang Guo-Yin. Rough Set Theory and Knowledge Acquisition. Xi'an:Xi'an Jiaotong University Press, 2001. [18] 邓大勇, 陈林.并行约简与F-粗糙集.云模型与粒计算.北京:科学出版社, 2012. 210-228Deng Da-Yong, Chen Lin. Parallel reducts and F-rough sets. Cloud Model and Granular Computing. Beijing:Science Press, 2012. 210-228 [19] 陈林. 粗糙集中不同粒度层次下的并行约简及决策[硕士学位论文], 浙江师范大学, 中国, 2013.Chen Lin. Parallel Reducts and Decision in Various Levels of Granularity [Master thesis], Zhejiang Normal University, China, 2013. [20] Cao F Y, Huang J Z. A concept-drifting detection algorithm for categorical evolving data. In:Proceedings of the 17th Pacific-Asia Conference on Knowledge Discovery and Data Mining. Gold Coast, Australia:Springer, 2013. 485-496 [21] 邓大勇, 裴明华, 黄厚宽. F-粗糙集方法对概念漂移的度量.浙江师范大学学报(自然科学版), 2013, 36(3):303-308 doi: 10.3969/j.issn.1001-5051.2013.03.012Deng Da-Yong, Pei Ming-Hua, Huang Hou-Kuan. The F-rough sets approaches to the measures of concept drift. Journal of Zhejiang Normal University (Natural Sciences), 2013, 36(3):303-308 doi: 10.3969/j.issn.1001-5051.2013.03.012 [22] 邓大勇, 徐小玉, 黄厚宽.基于并行约简的概念漂移探测.计算机研究与发展, 2015, 52(5):1071-1079 http://d.old.wanfangdata.com.cn/Periodical/jsjyjyfz201505009Deng Da-Yong, Xu Xiao-Yu, Huang Hou-Kuan. Concept drifting detection for categorical evolving data based on parallel reducts. Journal of Computer Research and Development, 2015, 52(5):1071-1079 http://d.old.wanfangdata.com.cn/Periodical/jsjyjyfz201505009 [23] 苗夺谦, 胡桂荣.知识约简的一种启发式算法.计算机研究与发展, 1999, 36(6):681-684 http://d.old.wanfangdata.com.cn/Periodical/jsjyjyfz199906006Miao Duo-Qian, Hu Gui-Rong. A heuristic algorithm for reduction of knowledge. Journal of Computer Research and Development, 1999, 36(6):681-684 http://d.old.wanfangdata.com.cn/Periodical/jsjyjyfz199906006 [24] 王国胤, 于洪, 杨大春.基于条件信息熵的决策表约简.计算机学报, 2002, 25(7):759-766 doi: 10.3321/j.issn:0254-4164.2002.07.013Wang Guo-Yin, Yu Hong, Yang Da-Chun. Decision table reduction based on conditional information entropy. Chinese Journal of Computers, 2002, 25(7):759-766 doi: 10.3321/j.issn:0254-4164.2002.07.013 [25] 杨明.决策表中基于条件信息熵的近似约简.电子学报, 2007, 35(11):2156-2160 doi: 10.3321/j.issn:0372-2112.2007.11.023Yang Ming. Approximate reduction based on conditional information entropy in decision tables. Acta Electronica Sinica, 2007, 35(11):2156-2160 doi: 10.3321/j.issn:0372-2112.2007.11.023 [26] 邓大勇, 薛欢欢, 苗夺谦, 卢克文.属性约简准则与约简信息损失的研究.电子学报, 2017, 45(2):401-407 doi: 10.3969/j.issn.0372-2112.2017.02.019Deng Da-Yong, Xue Huan-Huan, Miao Duo-Qian, Lu Ke-Wen. Study on criteria of attribute reduction and information loss of attribute reduction. Acta Electronica Sinica, 2017, 45(2):401-407 doi: 10.3969/j.issn.0372-2112.2017.02.019 期刊类型引用(9)
1. 邓大勇，沈文新. F-粗糙集的拓展与应用. 浙江师范大学学报(自然科学版). 2024(04): 381-390 . 
百度学术2. 邓大勇，刘月铮，肖春水. 决策系统簇的平均代价敏感并行约简. 浙江师范大学学报(自然科学版). 2023(01): 7-17 . 百度学术3. 邓大勇，汪杰. 粗糙集的信息损失及其多阶定义. 浙江师范大学学报(自然科学版). 2023(04): 379-384 . 百度学术4. 邓大勇，唐雨朋，杜巧连. 理想信息系统及粗糙集模型的统一. 浙江师范大学学报(自然科学版). 2022(01): 21-25 . 百度学术5. 龚健虎，张跃进. 深度AWB结合改进DIT的高效大数据分类. 计算机工程与设计. 2021(02): 468-474 . 百度学术6. 邓志轩，郑忠龙，邓大勇. F-邻域粗糙集及其约简. 自动化学报. 2021(03): 695-705 . 本站查看7. 邓大勇，吴越，刘月铮. 增量式概念漂移适应与收敛. 浙江师范大学学报(自然科学版). 2021(02): 156-163 . 百度学术8. 刘月铮. 测试代价敏感的F-粗糙集方法. 电子技术. 2021(04): 61-63 . 百度学术9. 刘雁行，王婷. 基于PSD-BPA的电力系统监测大数据属性约简方法. 自动化与仪器仪表. 2020(09): 216-219 . 百度学术其他类型引用(6)
-
下载:
计量
- 文章访问数: 1877
- HTML全文浏览量: 230
- PDF下载量: 570
- 被引次数: 15
