A Multivariate Decision Tree for Big Data Classification of Distributed Data Streams
-
摘要: 分布式数据流大数据中的类别边界不规则且易变，因此基于单变量决策树的集成分类器需要较大数量的基分类器才能准确地近似表达类别边界，这将降低集成分类器的学习与分类性能.因而，本文提出了基于几何轮廓相似度的多变量决策树.在最优基准向量的引导下将n维空间样本点投影到一维空间以建立有序投影点集合，然后通过类别投影边界将有序投影点集合划分为多个子集，接着分别对不同类别集合的交集递归投影分裂，最终生成决策树.实验表明，本文提出的多变量决策树GODT具有很高的分类精度和较低的训练时间，有效结合了单变量决策树学习效率高与多变量决策树表示能力强的优点.Abstract: Considering the irregularity and variability of the class boundaries of distributed big data streams, when the univariate decision tree is used as the base classifier in an ensemble classifier, large amounts of base classifiers are needed to accurately approximate class boundaries. This will reduce the learning and classification performance of ensemble classifiers. This article proposes a multivariate decision tree based on geometric outline similarity (GODT). Firstly, by using the optimal reference vector, the n-dimensional data points are projected onto the one-dimensional space, thus a set of ordered projection points are established. Secondly, the set of projection points are divided into several subsets, and the intersections of different subsets are projected and divided by recursive projecting and splitting. Finally, a decision tree is built. Experimental results show that GODT has a better classification accuracy and requires less training time. It combines the high learning efficiency of univariate decision tree algorithm with the strong representation power of multivariate decision tree.
-
Key words:
- Distributed data streams /
- big data /
- classification /
- outline similarity /
- multivariate decision tree
-
分布式和流动性的大数据简称分布式数据流大数据, 广泛存在于大型电子商务网站的交易系统、网络监控系统、传感器网络、股票交易及银行业务等系统, 具有突发性、快速性、无限性、概念漂移、分散性、信息价值稀疏性等特点[1-3], 给此类数据的分类挖掘提出了极大的挑战.
针对数据流的分类问题, 基于集成学习[4-5]的分类模型是较好的解决方法, 因其具有很高的抗概念漂移能力, 并且分类准确性也较高[6].很多集成分类模型采用决策树作为基分类器, 因为决策树学习效率高, 模型简单, 其内在的不稳定性可以提高集成分类模型的多样性[7].但是, 面对分布式数据流大数据分类, 现有基于决策树的集成分类模型面临一个急需解决的问题:此类数据在线到达的数据量大且分散化, 类别的边界呈现易变性和不规则性, 而且这些有价值的边界信息相对于数据总体呈现稀疏性.然而, 现有基于决策树的集成分类器多采用单变量决策树作为基分类器, 由于单变量决策树只能生成平行于坐标轴的决策边界, 因此需要较大数量的基分类器才能正确地近似表示类别边界, 这使得集成分类模型的学习性能和预测效率降低, 很难适应入侵检测等需要快速预测的应用.
鉴于上述问题, 本文提出了基于几何轮廓相似度的多变量决策树(Decision tree based on geometric outline similarity, GODT). GODT可以产生任意角度的决策边界, 相比单变量决策树, 其表示能力更强.另外, 最小交集分裂准则促使GODT可以快速发现类别边界, 而递归投影分裂策略可以有效降低中间节点的分裂次数, 因此GODT具有较低的学习时间.在表示相同决策边界的条件下, 相比单变量决策树, GODT作为基分类器所需的数量更少, 所以可有效解决因增加基分类器而由此产生的学习与预测性能下降问题.本文研究的创新点主要包括两点: 1)提出最小交集分裂准则.基于类别相似度偏差最大化的方法求解最优基准向量, 使得在最优基准向量的引导下, 不同类别投影点集合的交集最小, 实现了类别归属不确定的样本集合最小化. 2)提出递归投影分裂策略.针对父节点中的投影重叠区域, 在其子节点重新计算最优基准向量, 这样可使得重叠区域的样本点经过重新投影之后, 被正确地分离开, 解决了投影重叠区域的分裂问题.
本文组织结构如下:第1节介绍面向数据流分类的基于决策树的集成学习方法的相关研究; 第2节介绍经典的多变量决策树算法和几何轮廓相似度函数; 第3节详细阐述GODT, 包括建立属性组合度量标准, 分析算法的原理, 设计和实现GODT算法; 第4节是实验, 从分类的准确性、训练时间和多样性等几个方面测试GODT; 第5节是总结及后续的研究.
1. 相关工作
近些年, 针对数据流的分类挖掘, 研究人员已经提出了很多基于决策树构建集成分类器的方法. Street等[8]于2001年提出SEA算法, 使用连续数据块训练C4.5生成彼此独立的基分类器, 并利用启发式的替换策略更新集成分类器来解决大规模数据流分类问题. 2009年, Bifet等[9]提出了两种改进的Bagging学习方法: ADWIN Bagging和ASHT Bagging, 其中ASHT Bagging通过将多个可变尺寸的HoeffdingTree进行结合, 进而增加基分类器的多样性.同年, Polat等[10]基于C4.5以及一对多(One-against-all)分类方法构建集成分类器, 此方法很好地解决了多类分类问题. 2011年, Wozniak[11]提出了iDTt-NGE学习算法, 利用广义嵌套范式(Nested generalized exemplar)算法协同训练多个基分类器C4.5来解决概念漂移问题. Abdulsalam等[12]通过调整分类模型的参数来优化随机森林的分类效果, 提出了基于随机森林的数据流分类方法, 该方法在多类分类问题中可以达到较高的准确性. 2012年, Bifet等[13]提出了基于``学习法''的集成分类方法, 通过在指定维数的每个子空间上训练初级学习器HoeffdingTree, 利用初级学习器的输出训练sigmoid感知器来生成次级学习器, 并验证了该方法在准确率、时间和空间消耗等方面优于Bagging方法. 2014年, Ahmad等[14]提出了基于线性多变量决策树构建集成分类器的方法, 利用随机投影(Random projection)与随机离散化(Random discretization)相结合的方法训练基分类器以增强集成分类器的表示能力. 2016年, Blaser等[7]提出了旋转特征空间的集成学习方法, 基于随机旋转的特征空间训练基分类器来提高集成分类器的多样性, 此方法特别适用于决策树的集成学习.毛国君等[15]提出了基于淘汰策略的集成分类方法, 使用微簇集合重构训练数据来训练基分类器C4.5, 并利用淘汰策略生成集成分类器来解决分布式数据流分类问题.
上述相关工作主要从基分类器和集成学习方法两个角度开展的研究, 为本文的研究提供了可借鉴的理论和方法.
2. 理论基础
2.1 多变量决策树
决策树采用自顶向下的归纳学习方法来创建, 分为单变量决策树(Univariate decision trees)[16-17]和多变量决策树(Multivariate decision trees)[18-19].与单变量决策树不同, 多变量决策树的分裂判别标准建立在属性组合之上而非单一属性, 进而可以产生任意角度的超平面来分割数据集, 所以表示能力更强, 但同时计算复杂度也更高[14].根据属性组合的方式, 多变量决策树分为线性组合多变量决策树、布尔组合多变量决策树和非线性组合多变量决策树等, 其中最常用的是线性组合多变量决策树, 它利用属性的线性组合作为检验标准.
$ \begin{align} \sum\limits_{i=1}^k {a_i x_i } \le C \end{align} $
(1) 其中, ${x}_i $为第$i$个属性, $a_i $为属性${x}_i $的权重, $C$为阈值.
多变量决策树同单变量决策树一样也会出现生长过盛的问题, 因此需要对其剪枝.剪枝策略主要分为事前剪枝(Pre-pruning)和事后剪枝(Post-pruning)两种类型[20-26].
2.2 几何轮廓相似度函数
几何轮廓相似度函数[27]是建立在伽罗华群-单纯型理论之上的多维对象相似性度量方法, 其主要思想是通过计算多维对象的几何轮廓相似度来反映多维对象的亲疏关系.
设多元随机向量$X=(x_1, x_2, \cdots, x_m)$, 其中是向量$X$的第$j$个特征变量($j=1, 2, \cdots , m$).设$X$的观测样本集$T=(X_1, X_2 , \cdots , X_n)$, 称$X_i$为$T$的第$i$个样本($i=1, 2, \cdots, n$), 令$X_i =(x_{i1}$, $x_{i2}$, $\cdots , x_{im})$.
定义1. 点集称为样本$X_i $的几何轮廓.
定义2. 样本$X_k $与$X_s $的几何轮廓相似度函数:
$ \begin{align} &\rho _{ks} = \\ &\quad\frac{1}{m}\sum\limits_{j=1}^m {\sqrt {\left(1-\frac{| d_{kj} -d_{sj} |}{R_j }\right)\left(1-\frac{|x_{kj} -x_{sj} |}{W_j }\right)} } \end{align} $
(2) 其中,
$ \begin{align} &d_{ij} = \begin{cases} {x_{ij+1} -x_{ij} }, &{1\le j\le m-1} \\ {x_{im} -x_{i1} }, &{j=m} \end{cases} \end{align} $
(3) $ \begin{align} &R_j =\max _{i=1, \cdots, n}\{d_{ij} \}-\min _{i=1, \cdots, n} \{d_{ij} \} \end{align} $
(4) $ \begin{align} & W_j =\max _{i=1, \cdots, n} \{x_{ij} \}-\min _{i=1, \cdots, n} \{x_{ij} \} \end{align} $
(5) 给定3个样本$X_1 $, $X_2 $和$X_3 $, $X_1 $与$X_2 $的相似度值记为, $X_3 $与$X_2 $的相似度值记为$\rho _{32} $.若$\rho _{12}$ $>$ $\rho _{32} $, 则样本$X_1 $与$X_2 $更相似; 若, 则样本$X_3 $与$X_2 $更相似.因此, 几何轮廓相似度函数为构建多变量决策树提供了一种有效的非线性降维投影方法, 并且降维后的一元变量$\rho _{ij} $具有可解释性:由于树中非叶子节点的每个分支弧都代表一个相似度区间, 且其对应的分支节点代表与父节点的基准向量相似度介于此区间的样本子空间, 因此非叶子节点的每一种划分都具有可解释性, 这使得基于几何轮廓相似度的多变量决策树具有可解释性.
3. 基于几何轮廓相似度的多变量决策树(GODT)
3.1 属性组合方法及其度量标准
定义3. 对于给定的样本集$T$ (见第2.2节), 点集 ($f(x_j )$为随机变量$x_j$到实数域${\bf R}$的映射)称为样本集$T$的基准几何轮廓; 多元随机向量, $f(x_m ))$称为样本集$T$的基准向量.
利用式(2)计算样本$X_i $与基准向量$S$的相似度, 记为$Y_i $, 如果与$Y_i $一一映射, 之后只需建立基于$Y_i $的度量标准, 因为基于的度量标准与基于$X_i $的度量标准是等价的.
定理1.给定一个样本集$T$ (样本数为$n$), $X_i=$ $x_{i2}, \cdots, x_{im})$为$T$的第$i$个样本, $S=(f(x_1 )$, , $\cdots , f(x_m ))$为$T$的基准向量, $Y_i =\rho (X_i )=$ 其中见式(3),
$ \begin{align*} d_{0j} = \begin{cases} {f(x_{j+1} )-f(x_j )}, &{1\le j\le m-1} \\ {f(x_m )-f(x_1 )}, &{j=m} \end{cases} \end{align*} $
$R_j $和$W_j $见式(4)和(5), 则$X_i $与$Y_i $一一映射.
证明.显然$\rho $是满射.只需证$\rho $是单射, 即对任意$X_i \ne X_k $, 均有$Y_i \ne Y_k $, 包括三种情况:
1) 假定不等式$f(x_j )>x_{ij}, x_{kj}$成立.由$X_i\ne$ $X_k $, 不妨设$f(x_1 )>x_{i1} >x_{k1}>0$, $ x_{ij} =x_{kj}$, $j=$ $2$, .此时假设
$ \begin{align} &Y_i -Y_k = \\&\qquad\frac{1}{p}\left(1-\frac{|d_{i1} -d_{01} |}{R_1 }\right)\left(1-\frac{|x_{i1} -f(x_1 )|}{W_1 }\right)- \\&\qquad \left(1-\frac{|d_{k1} -d_{01} |}{R_1 }\right)\left(1-\frac{|x_{k1} -f(x_1 )|}{W_1 }\right)=0 \end{align} $
(6) 即
$ \begin{align} &\left(1-\frac{|d_{i1} -d_{01} |}{R_1 }\right)\left(1-\frac{|x_{i1} -f(x_1 )|}{W_1 }\right)= \\&\qquad \left(1-\frac{|d_{k1} -d_{01} |}{R_1 }\right)\left(1-\frac{|x_{k1} -f(x_1 )|}{W_1 }\right)\end{align} $
(7) $ \begin{align}& \dfrac{1-\dfrac{|d_{i1} -d_1 |}{R_1 }}{1-\dfrac{|d_{k1} -d_1 | }{R_1 }}=\dfrac{1-\dfrac{|x_{k1} -f(x_1 )|}{W_1 }}{1-\dfrac{| x_{i1} -f(x_1 )|}{W_1 }} \end{align} $
(8) 由$f(x_1 )>x_{i1} >x_{k1} $, 可知$|x_{k1} -f(x_1 )| > |x_{i1}$ $-$ $f(x_1 )|$, 进而
$ \begin{align} 1-\frac{|x_{k1} -f(x_1 )|}{W_1 } <1-\frac{|x_{i1} -f(x_1 )|}{W_1 } \end{align} $
(9) 所以
$ \begin{align} 1-\frac{|d_{i1} -d_{01} |}{R_1 } <1-\frac{|d_{k1} -d_{01} |}{R_1 } \end{align} $
(10) 即
$ \begin{align*} |d_{i1} -d_{01} |>|d_{k1} -d_{01} |, ~ |x_{i2} -x_{i1} | >|x_{k2} -x_{k1} | \end{align*} $
由假设$x_{i2} =x_{k2}, $可得$x_{i1} <x_{k1} $, 与已知$x_{i1}$ $>$ $x_{k1} $矛盾, 所以$Y_i \ne Y_k $, $\rho $为单射.
2) 同理可证, 不等式$f(x_j )<x_{ij}, x_{kj} $成立时$\rho $也是单射.
3) 若不等式$x_{ij} <f(x_j ) <x_{kj} $成立, 且$f(x_1 )$ $=$ , $ R_1 =R_2 =\cdots =R_m$, $W_1$ $=$ , $X_i $与$X_k $关于$S$对称时, 有$X_i$ $\ne$ $X_k , $使, 此情况为一种零概率事件.除此之外, 同理可证$\rho $也是单射.
综上所述, 以概率1有$X_i $与$Y_i $一一映射.
$Y_i$的全体构成了一维数轴上的一个点集$Y=$ .现对$Y$中的元素从小到大排序, 得到有序集合$P$ ( $(n\ge j>i\ge 1)\}$). $P$中的每个元素$Y_i $表示样本与基准向量$S$的相似程度, 并且从左至右相似程度越来越高.假设样本集$T$的两个子集分别为和$T_2 $, 且$T_1 $中的样本同属类别$C_1 $; 中的样本同属类别$C_2 $, $T_1 $中的样本$X_i $与$S$的相似度值构成的集合记为$P_1 $ ($P_1$ $\subset$ $P$); $T_2 $中的样本与$S$的相似度值$Y_j $构成的集合记为$P_2 $ ($P_2 \subset P$).由于$T_1 $中的样本同属类别$C_1 $, 因此中的样本与基准样本$S$的相似程度是相当的, 也就是说中的元素位置是相近的(同处一个邻域), 同理中的元素位置也是相近的, 而$P_1 $中的元素与$P_2 $中的元素是疏远的, 这样$P_1 $与$P_2 $在一维数轴上便形成了2个簇, 如图 1所示.
图 1 投影点集合$P_1 $与$P_2 $的位置关系Fig. 1 The position relationship of projection point sets $P_1 $ and $P_2 $$P_1 $和$P_2 $的位置关系有不相交和相交两种.对于第一种关系(不相交), 很容易找到一个分裂点将$P_1 $和完全分割开, 但对于第二种关系(相交), 这样的分裂点是不存在的, 然而实际上第二种关系是最多的.针对此种情况, 采取逐步分裂的方法, 首先将$P_1 $和$P_2 $的差集部分从$P$中分离出去, 之后对交集部分进行逐步分裂, 其中每一步都执行相同的操作(重新投影、排序、分组和分离非交集部分), 直到交集部分为空.被分裂的交集部分越小, 则分裂的不确定性越小, 准确性越高, 整体的分裂次数越少, 为了实现被分裂交集部分最小化, 本文使用了变基投影策略.通过基于类别相似度偏差最大化的方法求解最优基准向量, 使其引导下的不同类别的投影点集合的交集最小, 以实现样本集的最优分裂.上述逐步分裂的整个过程构成了一棵决策树, 接下来本文介绍基于几何轮廓相似度的多变量决策树.
3.2 基于几何轮廓相似度的多变量决策树(GODT)
基于几何轮廓相似度的多变量决策树, 在最优基准向量的引导下, 利用几何轮廓相似度函数把$m$维空间下的样本投影到一维空间的数轴上, 并对投影点进行排序、分组, 得到一组有序集合$P_1, P_2$, $\cdots$, $P_k$ ($k$为类别数目), 计算$P_1, P_2 , \cdots, P_k $的交集与差集, 其中交集记为; 差集记为$T_{q1}, T_{q2} , \cdots, T_{qt}$.将$T_{qi}$ $(i=1, 2, \cdots, t)$标记为叶子节点, 而将交集$T_{pj}$ $(j=1, 2, \cdots, s)$标记为中间节点, 之后分别对每个中间节点递归地投影分裂, 直到满足一定条件分裂停止, 最终生成一棵决策树.该算法在设计过程中需要解决关键问题.
1) 参数$R_j $和$W_j $的确定.由式(5)可知$W_j$ , 因此需要分别确定和$\min _{i=1}^n \{x_{ij} \}$, 而和$\min _{i=1}^n \{x_{ij} \}$是总体的最大值和最小值, 所以无法获得实际的取值.但可以通过训练样本集中的$\max _{i=1}^{T} \{x_{ij} \}$和来估计总体$x_j $的和$\min _{i=1}^n \{x_{ij} \}$.设是来自随机变量$x_j $的样本, 对应样本值为$x_{1j}, x_{2j}, \cdots$, $x_{tj}$, 由于$s_1 , s_2, \cdots, s_t $相互独立, 且$t\ge 30$时, $x_j$ $\sim $ ${\rm N}(\mu, \sigma ^2)$, 则$x_j $的似然函数为
$ \begin{align} L(\mu , \sigma ^2)=\prod\limits_{i=1}^{T} {\frac{1}{\sqrt {2\pi } \sigma }} {\rm e}^{-\frac{(x-\mu )^2}{2\sigma ^2}} \end{align} $
(11) 求解得$\mu$, $\sigma ^2$的极大似然估计量为$\hat{\mu}$ $=$ $\bar{x}_j$, .令$M=\max(s_1, s_2, \cdots, s_t)$, $N$ $=$ $\min(s_1, s_2, \cdots, s_t)$, 则
$ \begin{align} &P\{M\le z\}=P\{s_1 \le z, s_2 \le z, \cdots, s_t \le z\}= \\&\qquad P\{s_1 \le z\}P\{s_2 \le z\}\cdots P\{s_t \le z\}=(F(z))^n \end{align} $
(12) $ \begin{align} &P\{N\le u\}=1-P\{N>u\}= \\ &\qquad 1-P\{s_1 >u, s_2 >u, \cdots, s_t>u\}= \\ &\qquad 1-P\{s_1>u\}P\{s_2 >u\}\cdots \\ &\qquad P\{s_t >u\}= 1-(1-F(u))^n \end{align} $
(13) 若$P\{M\le z\}=P\{N\le u\}=\alpha $, 则$\Phi((z$ $-$ , , 进而求出置信水平为$\alpha $时的总体最大值$z$和最小值$u$, 于是可得$W_j =z-u$.
由式(4)可知,
$ {R_j} = \mathop {\max }\limits_{i = 1, \cdots ,n} \{ {d_{ij}}\} - \mathop {\min }\limits_{i = 1, \cdots ,n} \{ {d_{ij}}\} $
又由于
$ \mathop {\max }\limits_{i = 1, \cdots ,n} \{d_{ij} \}\le\mathop {\max }\limits_{i = 1, \cdots ,n} \{x_{ij+1} \}-\mathop {\min }\limits_{i = 1, \cdots ,n} \{x_{ij} \} $
而
$ \mathop {\min }\limits_{i = 1, \cdots ,n} \{d_{ij} \}\le \mathop {\min }\limits_{i = 1, \cdots ,n} \{x_{ij+1} \}-\mathop {\max }\limits_{i = 1, \cdots ,n}\{x_{ij} \} $
因此
$ \begin{align*} &R_j \le \max _{i=1, \cdots, n} \{d_{ij} \}\le \\ &\qquad \left(\max _{i=1, \cdots, n} \{x_{ij+1} \}-\min\limits_{i=1, \cdots, n} \{x_{ij} \}\right)-\\ &\qquad \left(\min _{i=1, \cdots, n} \{x_{ij+1} \}-\max _{i=1, \cdots, n} \{x_{ij} \}\right)\end{align*} $
进一步合并, 可得
$ R_j =\mathop {\max }\limits_{i = 1, \cdots ,n} \{d_{ij} \}\le W_{j+1} +W_j $
2) 最优基准向量的构建. $P_i \cap P_j $ 表示数轴上的某一区间$[a, b]$, 区间内的投影点既有属于类别, 也有属于类别$C_j $, 因此该区间内样本的类别归属是不确定的.如果 $(i\ne j)$越大, 则$T$中样本类别归属的不确定性越高, 不可分的样本越多, 反之则越小.通过改变基准向量$S$, 可以减小$P_i$ $\cap$ $P_j$ $(i\ne j)$, 若基准向量$S$与$C_i $中样本的相似度越高, 而同时与$C_j $中样本的相似度越低, 则$S$引导下的两类投影点集合与$P_j $的交集越小, 当$P_i $与$P_j $的交集最小时, $S$与$C_i $, 两类的相似度差异性最大, 此时$S$即为最优基准向量$S_b $.
设$C_i $的均值向量为, $C_j $的均值向量为, $\overline X $与$\overline Y $的偏差向量为, $a_i=\overline {x}_i$ $-$ $\overline {y}_i$, 令, 其中$w_1 $, $w_2 $, $\cdots$, $w_m $为权重系数, 基准向量$S=\overline X +v$, 则$S$与$\overline X $, 的相似度偏差为
$ \begin{align} f=&\ \rho (\overline X )-\rho (\overline Y )= \\&\ \sum\limits_{j=1}^m \left[\left(1-\frac{|w_{j+1} a_{j+1} -w_j a_j |}{R}\right)^\frac{1}{2}\right.\times \\&\ \left(1-\frac{|w_j a_j | }{W}\right)^\frac{1}{2} - \\&\ \left(1-\frac{|(w_{j+1} +1)a_{j+1} -(w_j +1)a_j |}{R}\right)^\frac{1}{2}\times \\&\ \left.\left(1-\frac{|(w_j +1)a_j |}{W}\right)^\frac{1}{2}\right] \end{align} $
(14) 若$w_1 , w_2 , \cdots, w_m $取一组值使得$f$最大, 则$S_b$ $=$ 或$S_b =S=\overline Y -v$.接下来只需求解如下非线性方程组即可求得权重系数$w_1, w_2 , \cdots$, $w_m $, 进而得到最优基准向量$S_b$.
$ \begin{align} \begin{cases} {\dfrac{\partial f}{\partial w_1 }=0} \hfill \\[2.9mm] {\dfrac{\partial f}{\partial w_2 }=0} \hfill \\ \qquad\vdots \hfill \\ {\dfrac{\partial f}{\partial w_m }=0} \hfill \\ \end{cases} \end{align} $
(15) 由于上述的相似度偏差$f$中存在开方和绝对值运算, 所以其偏导运算复杂, 且构成的方程组不易求解, 为了解决这一问题, 本文利用函数
$ \begin{align} &g(w_1, w_2, \cdots, w_m )= \\&\qquad \sum\limits_{j=1}^m \left[ \left(1-\frac{(w_{j+1} a_{j+1} -w_j a_j )^2}{R_j^2 }\right)\right.\times \\ & \qquad \left.\left(1-\frac{w_j ^2a_j ^2}{W_j ^2}\right)\right]- \\& \qquad\left[\left(1-\frac{[ {(w_{j+1} +1)a_{j+1} -(w_j +1)a_j } ]^2}{R_{j+1}^2 }\right)\right.\times \\& \qquad \left.\left(1-\frac{(w_j +1)^2a_j ^2}{W_{j+1}^2 }\right)\right] \end{align} $
(16) 来度量基准向量$S$与$\overline X $, $\overline Y$的相似度偏差, 并称其为相似差异度.然后利用相似差异度$g$对$w_j $ $(j=$ $1$, $2$, $\cdots$, $m)$求偏导并建立方程组, $g$对$w_j $的偏导数如下:
$ \begin{align} \frac{\partial g}{\partial w_j }=&\ R_j^2 W_j^2 [2a_{j+1} W_{j-1}^2 (a_{j+1} -a_j ) + \\&\ 6a_j^3 a_{j+1} w_{j-1}^2 - 2a_j^2 a_{j+1}^2 w_{j-1}^2 + \\[1mm]&\ 6a_j^3 a_{j+1} w_{j-1} - 4a_j^2 a_{j+1}^2 w_{j-1} w_j - \\[1mm]&\ 2a_j^2 a_{j+1}^2 w_j - 4a_j^2a_{j+1}^2 w_{j-1}+ 2a_j^3 a_{j+1} - \\[1mm]&\ 2a_j^2 a_{j+1}^2 ]+ R_{j-1}^2W_{j-1}^2 [(6a_j^3 a_{j+1} + \\[1mm]&\ 2a_j^4 )w_j^2 +6a_j^3 a_{j+1} w_{j+1} -4a_j^2 a_{j+1}^2 w_{j+1} + \\[1mm]&\ 12a_j^3a_{j+1}w_j- 12a_j^4 w_j -2a_j^2 a_{j+1}^2 w_j + \\[1mm]&\ (12a_j^3 a_{j+1} -4a_j^2 a_{j+1}^2 )w_j w_{j+1} - \\[1mm]&\ 2a_j^2 a_{j+1}^2 w_{j+1}^2 +2a_j^2 R_j^2 - \\[1mm]&\ 2a_j W_j^2 (a_{j+1} -a_j )+ 2a_j^3 (a_{j+1} -a_j )- \\[1mm]&\ 2a_j^2 (a_{j+1} -a_j )^2] \end{align} $
(17) 从式(17)可以看出, 为一元二次方程, 因此, 其构成的方程组为非线性方程组.
$ \begin{align} \begin{cases} {f_1(w_n , w_1 , w_2 )=\dfrac{\partial g}{\partial w_1 }=0} \\[3mm] {f_2(w_1 , w_2 , w_3 )=\dfrac{\partial g}{\partial w_2 }=0} \\ \qquad\qquad \vdots \\ {f_m(w_{m-1} , w_m , w_1 )=\dfrac{\partial g}{\partial w_m }=0} \\ \end{cases} \end{align} $
(18) 利用多变量Newton方法求解上述方程组, 设$F(x)$ $=$ , $x=(w_1 , w_2 , \cdots, w_m )$, 则Jacobi矩阵$DF(x)$为
$ \begin{align} \left( {{\begin{array}{*{20}c} {\dfrac{\partial f_1 }{\partial w_1 }}&{\dfrac{\partial f_1 }{\partial w_2 }} &0&{\cdots} &0 & {\dfrac{\partial f_1 }{\partial w_m }} \\[2mm] {\dfrac{\partial f_2 }{\partial w_1 }}&{\dfrac{\partial f_2 }{\partial w_2 }} &{\dfrac{\partial f_2 }{\partial w_3 }}&0 &{\cdots}&0 \\[2mm] 0& {\dfrac{\partial f_3 }{\partial w_2 }}&{\dfrac{\partial f_3 }{\partial w_3 }}&{\dfrac{\partial f_3 }{\partial w_4 }} & 0 &{\cdots} \\[2mm] \cdots &0 &{\dfrac{\partial f_4 }{\partial w_3 }} & {\dfrac{\partial f_4 }{\partial w_4 }} &{\dfrac{\partial f_4 }{\partial w_5 }}&{0} \\ \vdots& \vdots& \vdots& \vdots& \vdots &\vdots\\ {\dfrac{\partial f_m }{\partial w_1 }}& 0& {\cdots}& 0 &{\dfrac{\partial f_m }{\partial w_{m-1} }}& {\dfrac{\partial f_m }{\partial w_m }}\\ \end{array} }} \right) \end{align} $
(19) 其中,
$ \begin{align} \frac{\partial f_i}{\partial w_{i-1}}=&\ R_i^2W_i^2[12a_j^3a_{j+1}w_{i-1} - \\&\ 4a_j^2 a_{j+1}^2 (w_{i-1} +w_i ) + \\&\ 6a_j^3 a_{j+1} -4a_j^2 a_{j+1}^2 ] \\[1.5mm] \frac{\partial f_i }{\partial w_i }=&\ R_{i-1}^2 W_{i-1}^2 [12a_j^3 a_{j+1} (w_{i+1} +w_i ) - \\&\ 4a_j^2 a_{j+1}^2 w_{i+1}- 24a_j^4 w_i + \\&\ 12a_j^3 a_{j+1} -12a_j^4 -2a_j^2 a_{j+1}^2 ] - \\&\ R_i^2 W_i^2 (4a_j^2 a_{j+1}^2 w_{i-1} +2a_j^2 a_{j+1}^2 ) \\[1.5mm] \frac{\partial f_i }{\partial w_{i+1} }=&\ R_{i-1}^2 W_{i-1}^2 [12a_j^3 a_{j+1} w_i - \\ &\ 4a_j^2 a_{j+1}^2 (w_i +w_{i+1} ) + \\&\ 6a_j^3 a_{j+1} -4a_j^2 a_{j+1}^2 ] \end{align} $
(20) 接下来迭代求解如下矩阵方程即可求解权重系数$w_1 $, $w_2 $, $\cdots$, $w_m $, 最后根据$C_i $, $C_j $所含样本的数量来确定最优基准向量.
$ \begin{align} \begin{cases} {DF(x_k )t=-F(x_k )} \\ {x_{k+1} =x_k +t} \\ \end{cases} \end{align} $
(21) $ \begin{align} S_b = \begin{cases} {\overline X +v}, &{n_i >n_j } \\ {\overline Y -v}, &{n_i \le n_j } \\ \end{cases} \end{align} $
(22) 虽然在最优基准向量$S_b $的引导下$P_i \cap P_j$ $(i$ $\ne$ $j)$最小, 但是$P_i \cap P_j \ne \phi$ $(i\ne j)$.如果根据投影点的类别归属直接分裂$P_i \cap P_j$ $(i\ne j)$, 将导致分裂不均衡和分裂效率降低, 分裂后的每一个子集含有极少相同类别样本(极端情况, 甚至只含一个样本).如此分裂直到终止, 最后生成的决策树非常复杂且过拟合严重.为了实现 $(i\ne j)$最优分裂, 本文提出了递归投影分裂方法, 主要思想是重新计算投影点集$P_i \cap P_j$ 对应的样本集合的最优基准向量$S_b^0$, 使得在$S_b^0$的引导下, 父节点中交叉排列的不同类别样本点在子节点经过重新投影之后被成功的分离开, 如图 2所示.因此, 不同类别投影点集合的交集进一步缩小, 然后采用相同的方法对产生的交集递归地投影分裂, 直到满足一定终止条件, 这样便可实现对$P_i \cap P_j$ $(i\ne j)$最大程度地正确分裂.
3) 终止策略. GODT采用了两种终止策略: a)若当前节点样本集所含样本同属一类, 则分裂停止, 并把该节点标记为叶子节点. b)若当前节点样本集所含样本分属多类且所含样本数量超过阈值, 则分裂停止, 并把该节点标记为叶子节点, 该节点的类别标签与其父节点中包含样本最多的类别标签相同.
4) 剪枝.虽然递归投影可以改善树的结构, 降低过拟合的程度, 但是过拟合不能完全消除, 为了进一步降低过拟合, 本文引入了事后剪枝策略.现有的事后剪枝策略有很多, 其中经典的方法包括Error-complexity pruning, Critical value pruning, Minimum-error pruning, Reduced-error pruning, Pessimistic pruning和Error-based pruning, 文献[21-22]对上述方法进行了详细的对比分析, 本文选择了Pessimistic pruning作为GODT的剪枝方法, 因为此方法不会出现过度剪枝, 其剪枝后决策树的平均错误率与C4.5算法中使用的Error-based pruning方法相差甚微, 然而其运行时间更低.
基于几何轮廓相似度的多变量决策树算法流程如下:
算法1.基于几何轮廓相似度的多变量决策树算法
Input:
$T:$训练样本集
$Minobj:$节点最小样本数
$R:$根节点
Output:
$Tree: $ GODT决策树
Function GODT ($T$, $Minobj$, $R$)
Begin
if ($R$的所有样本同属类别$C)$
标记$R$为叶子节点, 其类别为$C$;
Return;
else if ($R$的样本数小于$Minobj)$
标记$R$为叶子节点, 其类别为$R$的父节点包含
样本数最多的类别;
Return
else
计算最优基准向量$S_b$;
利用式(2)计算有序投影点集合$P_1 , P_2 , \cdots, P_j $;
计算$P_1, P_2 , \cdots, P_j $的差集与交集, 分别记为:
$T_{q1} , T_{q2}, \cdots, T_{qt} $;
$T_{p1} , T_{p2} , \cdots, T_{ps} $;
for each $T_{qi} $ in $T_{q1} , T_{q2}, \cdots, T_{qt}$
创建$R$的子节点$L_i $, 并将其标记为叶子节点;
存储分裂点$Y_i^b $;
end for
for each $T_{pj}$ in $T_{p1}, T_{p2}, \cdots, T_{ps}$
创建$R$的子节点$M_j$;
存储分裂点$Y_j^b $;
获取$T_{pj} $的样本集$T_j $;
GODT ($T_j $, $Minobj$, $M_j )$;
end for
end if
End
End Function
通过训练、剪枝, 最终生成一棵GODT.接下来, 应用GODT对未知类别样本进行分类, 分类过程如下:
步骤1.如果当前节点是叶子节点, 则待测样本的类别输出为当前节点的类别标签.
步骤2. 否则计算待测样本$X_i $与当前节点最优基准向量的相似度$Y_i $, 根据$Y_i $与$Y_j^b $的比较结果, 选择进入相应的子节点, 回到步骤1.
在每个中间节点, GODT主要完成以下计算任务:
1) 构建最优基准向量;
2) 计算样例与最优基准向量的几何轮廓相似度;
3) 排序和分裂训练集.
任务1)中最耗时的计算为求解权重系数$w_1 $, $w_2 $, $\cdots$, $w_m $, 其训练时间复杂度为O$(m^3)$; 任务2)的训练时间复杂度为O$(nm)$ $(n$为当前节点的训练样例数量); 任务3)采用快速排序方法, 其训练时间复杂度为O$(n\log n)$.于是, GODT在每个中间节点的总代价为O$(m^3)+{\rm O}(nm)+{\rm O}(n\log n)$.若$n$ $\gg$ $m$时, 则GODT在每个中间节点的训练时间复杂度为O$(nm)$; 若$m\gg n$时, 则GODT在每个中间节点的训练时间复杂度为O$(m^3)$.
4. 实验及结果分析
本节在分布式数据流大数据环境下共设计3个实验.
实验1. 测试基于GODT的集成分类器EGODT的分类精度和训练时间, 并选择相关工作中的基分类器C4.5[8, 10-11, 15], HoeffdingTree[9, 13]和Cart-LC[14]构建对比集成分类器: EC45, EHoeffdingTree和ECart-LC;
实验2. 在不同的基分类器数量下, 测试4种集成分类器的分类精度;
实验3. 测试基分类器GODT的多样化程度, 并与C4.5, HoeffdingTree和Cart-LC作对比.
4.1 实验环境和数据
本文选择真实数据集KDDCUP99[28], Record Linkage[28]和Heterogeneity Activity[29]作为测试数据集.数据的详细信息见表 1.
表 1 数据集Table 1 DatasetDataset Number of attributes Type of attributes Size Number of class KDDCUP99 42 Nominal, Numeric 5 209 460 23 Record Linkage 12 Numeric 4 587 620 2 Heterogeneity Activity 7 Numeric 13 062 475 7 GODT算法由C#语言编写实现, 并在Visual Studio 2013环境下编译执行, 所有实验全部在同一台工作站(CPU: E5-2620, 内存: 40 GB)上完成.
4.2 分布式数据流环境下的测试
为了模拟分布式数据、流式大数据环境, 本文编写了一个生成数据流的软件工具Stream Generator. Stream Generator包含1个控制参数:数据流速$dfs$.另外, 为了从局部节点获取训练数据, 本文编写了数据采集工具Data Collector. Data Collector包含1个控制参数:滑动窗口大小$wt$.
本节实验的分布式环境由4个局部节点和1个中心节点组成, 利用VM Workstation在1台工作站上构建5台虚拟机, 每台虚拟机分配4 GB内存, 利用其中4台作为局部节点(Distributed node), 1台作为中心节点(Master node).训练数据集和测试数据集分布存储在4个局部节点, 并在每个局部节点部署Stream generator来模拟数据流在线到达的过程以形成窗口数据.为了更好地模拟数据随机到达的情况, 每个局部节点的数据流速$dfs$会随着时间不断变化, 其变化范围设置为[1 000, 3 000].在中心节点部署Data collector和全局分类器, Data collector为全局分类器收集训练数据, 而全局分类器负责训练分类器并将生成的分类器分发给局部节点, 局部节点利用最新的分类器替换现有分类器, 继续对在线到达的测试数据进行分类.
中心节点的全局分类器为集成分类器, 其更新学习策略为:设集成分类器的基分类器数量为$n$, 假设当前挖掘时间点为$t_i $, 上一个挖掘点生成的集成分类器为 $(c_j^{i-1} $为$ec_{i-1} $中第$j$个基分类器), 窗口下的训练集为$T_i $.若$m$ $\leq$ $n$, 利用训练第$m+1$个基分类器$c_{m+1}^i $; 若$m$ $>$ $n$, 利用训练$ec_{i-1} $中分类错误率最高的基分类器, 这样做既可以保证基分类器之间的差异性, 又实现了在相同的条件下训练基分类器.
4.2.1 集成分类器的精度测试
在$n=10$的条件下, 随着$wt$的增加, 图 3给出了4种集成分类器的分类精度变化情况.
图 3 分类精度随滑动窗口大小的变化情况Fig. 3 The variation of classification accuracy with the sliding window size从图 3可以看出, 在KDDCUP99和Heterogeneity Activity数据集上, 随着$wt$的增加, 4个分类器的精度都在逐步提升, 这是因为训练数据的数量与$wt$成正比, $wt$越大, 训练数据越多, 则4个分类器学习质量越好.然而, 这种学习特性在Record Linkage数据集上体现不明显, 这是因为此数据集为二分类数据集, 其类别边界相对简单, $wt=5$时的训练数据量便满足了绝大部分类别边界的泛化学习, 因此随着$wt$的增加, 分类精度提升幅度很小.另外, 相比EC45和EHoeffdingTree, EGODT与ECart-LC的分类精度较好, 并且当$wt=5$时, EGODT的分类精度最高, 而此时的训练数据最少, 这体现了EGODT在小训练集环境下的学习优势, 这是因为GODT是基于类别边界构建的决策树, 其非叶子节点的每个分支弧都对应着一个分裂边界, 而这些分裂边界是由投影点的类别边界所决定的.每个投影点代表随机样本与最优基准向量的几何轮廓相似度, 第3.1节已经讨论过同属一类的投影点是相近的, 它们所处的区域相对整个数轴是一定的, 相同类别的小样本集与大样本集的投影区域大致相同, 因此小样本集的投影点即可确定类别的近似边界, 这就是GODT能够在小训练集环境下获得较高分类精度的原因.
为了进一步说明GODT的这种学习特性, 图 4给出了4种集成分类器在$wt=5$时的整个挖掘序列的学习过程.在KDDCUP99数据集的挖掘序列初始阶段, 4种分类器的分类精度均出现了较大的波动, 这是由分类器的更新学习策略所导致的, 因为在初始阶段集成分类器中的基分类器数量少, 并且基分类器之间的差异大, 所以分类精度出现较大波动.但是, EGODT的波动范围比其他3种算法小很多, 并且随着基分类器数量的增多, EGODT的波动很快收敛到一个较小的范围, 而且在后续的挖掘序列, 始终保持在这个较小的范围, 而ECart-LC的波动也很快收敛到一定的范围, 但波动范围较大; EC45的波动范围在700点之后才趋于稳定; EHoeffdingTree始终在较大范围波动.对于Heterogeneity Activity数据集的整个挖掘序列, EGODT和ECart-LC的波动范围较小, 而EC45在1 500点之后波动范围扩大, EHoeffdingTree的波动范围在750点之后才趋于稳定.由于Record Linkage数据集的类别边界简单且变化小, 因此4个分类器在整个挖掘序列的分类精度趋于稳定, 波动范围非常小.图 4验证了EGODT在较小的滑动窗口下可以获得较高的分类性能, 这种特性使得在分布式数据流大数据分类环境下, 能够进一步尝试缩小滑动窗口的大小来适应突发式或渐进式的概念漂移, 以及减少通信代价.
图 4 $wt=5$时, 分类精度在整个挖掘序列的变化情况Fig. 4 The variation of classification accuracy in the mining sequence when $wt=5$4.2.2 集成分类器的精度测试
由于每次更新学习只生成一个基分类器, 因此集成分类器的单次训练时间即为基分类器的训练时间.图 5给出了4种集成分类器的训练时间.
图 5 训练时间随滑动窗口大小的变化情况Fig. 5 The variation of training time with the sliding window size从图 5可以看出, 当$wt$从5增加到40, 4种集成分类器一次更新学习的时间都会增加, 这是因为如果$wt$增大, 则$wt$时间段内收集的训练数据增多, 因此学习时间加长.此外, 在KDDCUP99数据集上, EGODT的训练时间小于其他3种分类器, 而在Heterogeneity Activity数据集上, EGODT与EC45的训练时间相当, 并低于ECart-LC.在Record Linkage数据集上, EGODT与EC45、ECart的训练时间接近, 并低于EHoeffdingTree.综上, GODT的平均训练时间接近单变量决策树C4.5, 而低于多变量决策树Cart-LC, 这是因为GODT的递归投影策略使得每个非叶子节点的分裂至少产生一个叶子节点, 因此待分裂示例的数量从根节点便开始减少, 最终导致整体的分裂次数减少, 降低了决策树的生成时间.同时, 随着学习示例的增多, EGODT平均爬升幅度低于其他3种分类器, 主要是因为增加的绝大部分样例被投影到类别的非交集部分, 只有很少一部分投影到类别的交集部分(类别边界区域), 因此分裂交集所增加的计算量很少, 进而训练时间增加的幅度很小.
4.2.3 不同基分类器数量下的测试
在$wt=30$的条件下, 随着$n$的增大, 图 6给出了4种集成分类器的分类精度变化情况.
图 6 分类精度随基分类器数量的变化情况Fig. 6 The variation of classification accuracy with the number of base classifiers从图 6可以看出, 对于KDDCUP99数据集, EGODT与ECart-LC在$n=5$时的分类精度已经接近于EC45在$n=30$的分类精度, 而高于EHoeffdingTree在$n=30$的分类精度.在Heterogeneity Activity数据集上, EGODT在$n=5$的分类精度接近于ECart-LC在$n=10$的分类精度以及EC45在$n=20$的分类精度, 而高于EHoeffdingTree在$n=30$的分类精度.由于Record Linkage数据集的类别边界简单, 因此4种分类器在$n=5$时即可完成绝大部分类别边界的表达, 随着$n$的增大, 4种分类器的分类精度变化极小.综上, 图 6验证了GODT与Cart-LC的表示能力更强, 在表示相同决策边界时, GODT与Cart-LC所需的数量更少.
4.2.4 基分类器的多样性测试
基分类器多样性的度量指标有很多, 本节选用不合度量(Disagreement measure)[30]作为评价指标, 因为它简单、易表述, 其数学描述如下:
$ \begin{align} \label{eq17} dis_{ij} =\frac{b+c}{m} \end{align} $
(23) 其中, $m$为样本总数, $b$为分类器$i$预测为正例且分类器$j$预测为反例的样本数, $c$为分类器$i$预测为反例且分类器$j$预测为正例的样本数.
在$wt=10$, $n=10$的条件下, 表 2~5给出了4种基分类器在3个数据集上的平均不合度量结果.
表 2 EGODT的基分类器间的不合度量Table 2 The disagreement measure between base classifiers of EGODTGODT $c$1 $c$2 $c$3 $c$4 $c$5 $c$6 $c$7 $c$8 $c$9 $c$10 $c$1 0 0.43 0.52 0.55 0.51 0.41 0.43 0.43 0.41 0.48 $c$2 0 0.51 0.46 0.6 0.32 0.29 0.39 0.29 0.6 $c$3 0 0.24 0.24 0.56 0.6 0.56 0.6 0.52 $c$4 0 0.35 0.66 0.56 0.67 0.55 0.73 $c$5 0 0.53 0.64 0.52 0.57 0.58 $c$6 0 0.41 0.19 0.13 0.37 $c$7 0 0.12 0.19 0.68 $c$8 0 0.2 0.64 $c$9 0 0.6 $c$10 0 表 3 EC45的基分类器间的不合度量Table 3 The disagreement measure between base classifiers of EC45C4.5 $c$1 $c$2 $c$3 $c$4 $c$5 $c$6 $c$7 $c$8 $c$9 $c$10 $c$1 0 0.31 0.44 0.44 0.35 0.3 0.31 0.31 0.29 0.35 $c$2 0 0.48 0.48 0.53 0.11 0.09 0.09 0.09 0.53 $c$3 0 0.02 0.53 0.55 0.53 0.52 0.51 0.55 $c$4 0 0.52 0.55 0.53 0.53 0.53 0.54 $c$5 0 0.48 0.51 0.53 0.49 0.04 $c$6 0 0.08 0.09 0.07 0.47 $c$7 0 0.02 0.07 0.53 $c$8 0 0.08 0.54 $c$9 0 0.49 $c$10 0 表 4 ECart-LC的基分类器间的不合度量Table 4 The disagreement measure between base classifiers of ECart-LCCart-LC $c$1 $c$2 $c$3 $c$4 $c$5 $c$6 $c$7 $c$8 $c$9 $c$10 $c$1 0 0.39 0.31 0.31 0.3 0.37 0.46 0.46 0.32 0.32 $c$2 0 0.22 0.22 0.36 0.57 0.48 0.47 0.48 0.6 $c$3 0 0 0.15 0.61 0.5 0.5 0.5 0.5 $c$4 0 0.15 0.61 0.5 0.5 0.5 0.5 $c$5 0 0.46 0.52 0.52 0.39 0.39 $c$6 0 0.57 0.57 0.2 0.16 $c$7 0 0 0.38 0.5 $c$8 0 0.38 0.5 $c$9 0 0.12 $c$10 0 表 5 EHoeffdingTree的基分类器间的不合度量Table 5 The disagreement measure between base classifiers of EHoeffdingTreeHoeffdingTree $c$1 $c$2 $c$3 $c$4 $c$5 $c$6 $c$7 $c$8 $c$9 $c$10 $c$1 0 0.26 0.53 0.54 0.38 0.3 0.36 0.31 0.24 0.47 $c$2 0 0.42 0.47 0.2 0.18 0.12 0.16 0.1 0.32 $c$3 0 0.45 0.45 0.43 0.58 0.58 0.46 0.45 $c$4 0 0.52 0.44 0.45 0.5 0.47 0.51 $c$5 0 0.54 0.57 0.56 0.58 0.07 $c$6 0 0.08 0.15 0.14 0.51 $c$7 0 0.19 0.12 0.58 $c$8 0 0.25 0.57 $c$9 0 0.56 $c$10 0 从表 2~5可以看出, GODT的不合度量样本均值与方差为, 而C4.5, Cart-LC和HoeffdingTree的不合度量样本均值与方差分别为(0.36, 0.038), (0.40, 0.025)和(0.38, 0.028). GODT的不合度量样本均值高于其他3种分类器, 而且其相邻基分类器的最小不合度量为0.12, 而C4.5, Cart-LC和HoeffdingTree相邻基分类器的不合度量分别为0.02, 0和0.08, 说明GODT的多样性更强.另外, GODT的方差与Cart-LC相同, 并低于另外两种分类器, 说明其多样性相对稳定.因此, 基于GODT可以构建泛化能力更强的集成分类器.
5. 结论与未来工作
本文提出了一种新的多变量决策树.利用几何轮廓相似度函数将多维属性合成为一维属性, 建立了非线性属性组合方法, 并在此基础上提出了最小交集分裂准则, 这使得中间节点分裂的不确定性最小化.此外, 通过对投影分裂过程的分析, 提出了递归投影策略, 并将该策略与最优分裂准则相结合, 形成了一种有效的分裂方法, 降低了中间节点分裂的不均衡性, 简化了决策树的结构.同其他几种面向数据流的基分类器相比, 在分布式数据流环境下, 本文提出的多变量决策树具有较高的分类准确性和较低的训练时间, 为构建分布式数据流大数据环境下的集成分类模型提供了一种有效的基分类器.
分布式数据流大数据的分类挖掘需要整体的解决方法, 并非单一技术所能解决, 本文算法也仅仅是针对单变量决策树在分布式数据流大数据分类中的表示能力有限来研究对应的解决方法, 除此之外, 分布式数据流大数据的分类挖掘还面临数据类型多样化、大数据的形式化表达、多节点的概念漂移检测、复杂多分布的数据统计与样本重构方法等很多问题, 下一步工作的重点将围绕复杂多分布环境下的数据统计与样本重构方法, 开展相应的理论和算法研究.
-
图 1 投影点集合$P_1 $与$P_2 $的位置关系
Fig. 1 The position relationship of projection point sets $P_1 $ and $P_2 $
图 3 分类精度随滑动窗口大小的变化情况
Fig. 3 The variation of classification accuracy with the sliding window size
图 4 $wt=5$时, 分类精度在整个挖掘序列的变化情况
Fig. 4 The variation of classification accuracy in the mining sequence when $wt=5$
图 5 训练时间随滑动窗口大小的变化情况
Fig. 5 The variation of training time with the sliding window size
图 6 分类精度随基分类器数量的变化情况
Fig. 6 The variation of classification accuracy with the number of base classifiers
表 1 数据集
Table 1 Dataset
Dataset Number of attributes Type of attributes Size Number of class KDDCUP99 42 Nominal, Numeric 5 209 460 23 Record Linkage 12 Numeric 4 587 620 2 Heterogeneity Activity 7 Numeric 13 062 475 7 
下载: 导出CSV
表 2 EGODT的基分类器间的不合度量
Table 2 The disagreement measure between base classifiers of EGODT
GODT $c$1 $c$2 $c$3 $c$4 $c$5 $c$6 $c$7 $c$8 $c$9 $c$10 $c$1 0 0.43 0.52 0.55 0.51 0.41 0.43 0.43 0.41 0.48 $c$2 0 0.51 0.46 0.6 0.32 0.29 0.39 0.29 0.6 $c$3 0 0.24 0.24 0.56 0.6 0.56 0.6 0.52 $c$4 0 0.35 0.66 0.56 0.67 0.55 0.73 $c$5 0 0.53 0.64 0.52 0.57 0.58 $c$6 0 0.41 0.19 0.13 0.37 $c$7 0 0.12 0.19 0.68 $c$8 0 0.2 0.64 $c$9 0 0.6 $c$10 0
下载: 导出CSV
表 3 EC45的基分类器间的不合度量
Table 3 The disagreement measure between base classifiers of EC45
C4.5 $c$1 $c$2 $c$3 $c$4 $c$5 $c$6 $c$7 $c$8 $c$9 $c$10 $c$1 0 0.31 0.44 0.44 0.35 0.3 0.31 0.31 0.29 0.35 $c$2 0 0.48 0.48 0.53 0.11 0.09 0.09 0.09 0.53 $c$3 0 0.02 0.53 0.55 0.53 0.52 0.51 0.55 $c$4 0 0.52 0.55 0.53 0.53 0.53 0.54 $c$5 0 0.48 0.51 0.53 0.49 0.04 $c$6 0 0.08 0.09 0.07 0.47 $c$7 0 0.02 0.07 0.53 $c$8 0 0.08 0.54 $c$9 0 0.49 $c$10 0
下载: 导出CSV
表 4 ECart-LC的基分类器间的不合度量
Table 4 The disagreement measure between base classifiers of ECart-LC
Cart-LC $c$1 $c$2 $c$3 $c$4 $c$5 $c$6 $c$7 $c$8 $c$9 $c$10 $c$1 0 0.39 0.31 0.31 0.3 0.37 0.46 0.46 0.32 0.32 $c$2 0 0.22 0.22 0.36 0.57 0.48 0.47 0.48 0.6 $c$3 0 0 0.15 0.61 0.5 0.5 0.5 0.5 $c$4 0 0.15 0.61 0.5 0.5 0.5 0.5 $c$5 0 0.46 0.52 0.52 0.39 0.39 $c$6 0 0.57 0.57 0.2 0.16 $c$7 0 0 0.38 0.5 $c$8 0 0.38 0.5 $c$9 0 0.12 $c$10 0
下载: 导出CSV
表 5 EHoeffdingTree的基分类器间的不合度量
Table 5 The disagreement measure between base classifiers of EHoeffdingTree
HoeffdingTree $c$1 $c$2 $c$3 $c$4 $c$5 $c$6 $c$7 $c$8 $c$9 $c$10 $c$1 0 0.26 0.53 0.54 0.38 0.3 0.36 0.31 0.24 0.47 $c$2 0 0.42 0.47 0.2 0.18 0.12 0.16 0.1 0.32 $c$3 0 0.45 0.45 0.43 0.58 0.58 0.46 0.45 $c$4 0 0.52 0.44 0.45 0.5 0.47 0.51 $c$5 0 0.54 0.57 0.56 0.58 0.07 $c$6 0 0.08 0.15 0.14 0.51 $c$7 0 0.19 0.12 0.58 $c$8 0 0.25 0.57 $c$9 0 0.56 $c$10 0
下载: 导出CSV
-
[1] 朱群, 张玉红, 胡学钢, 李培培.一种基于双层窗口的概念漂移数据流分类算法.自动化学报, 2011, 37(9):1077-1084 doi: 10.3724/SP.J.1004.2011.01077Zhu Qun, Zhang Yu-Hong, Hu Xue-Gang, Li Pei-Pei. A double-window-based classification algorithm for concept drifting data streams. Acta Automatica Sinica, 2011, 37(9):1077-1084 doi: 10.3724/SP.J.1004.2011.01077 [2] Wu X D, Zhu X Q, Wu G Q, Ding W. Data mining with big data. IEEE Transactions on Knowledge and Data Engineering, 2014, 26(1):97-107 doi: 10.1109/TKDE.2013.109 [3] 孙大为, 张广艳, 郑纬民.大数据流式计算:关键技术及系统实例.软件学报, 2014, 25(4):839-862 http://www.cnki.com.cn/Article/CJFDTOTAL-RJXB201404011.htmSun Da-Wei, Zhang Guang-Yan, Zheng Wei-Min. Big data stream computing:technologies and instances. Journal of Software, 2014, 25(4):839-862 http://www.cnki.com.cn/Article/CJFDTOTAL-RJXB201404011.htm [4] Freund Y, Schapire R E. A decision-theoretic generalization of on-line learning and an application to boosting. Journal of Computer and System Sciences, 1997, 55(1):119-139 doi: 10.1006/jcss.1997.1504 [5] Breiman L. Bagging predictors. Machine Learning, 1996, 24(2):123-140 [6] Zhang P, Zhou C, Wang P, Gao B J, Zhu X Q, Guo L. E-tree:an efficient indexing structure for ensemble models on data streams. IEEE Transactions on Knowledge and Data Engineering, 2015, 27(2):461-474 doi: 10.1109/TKDE.2014.2298018 [7] Blaser R, Fryzlewicz P. Random rotation ensembles. Journal of Machine Learning Research, 2016, 17(4):1-26 [8] Street W N, Kim Y. A streaming ensemble algorithm (SEA) for large-scale classification. In: Proceedings of the 7th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. San Francisco, California, USA: ACM, 2001. 377-382 [9] 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 [10] Polat K, Güneş. A novel hybrid intelligent method based on C4.5 decision tree classifier and one-against-all approach for multi-class classification problems. Expert Systems with Applications, 2009, 36(2):1587-1592 doi: 10.1016/j.eswa.2007.11.051 [11] Wozniak M. A hybrid decision tree training method using data streams. Knowledge and Information Systems, 2011, 29(2):335-347 doi: 10.1007/s10115-010-0345-5 [12] Abdulsalam H, Skillicorn D B, Martin P. Classification using streaming random forests. IEEE Transactions on Knowledge and Data Engineering, 2011, 23(1):22-36 [13] Bifet A, Frank E, Holmes G, Pfahringer B. Ensembles of restricted hoeffding trees. ACM Transactions on Intelligent Systems and Technology (TIST), 2012, 3(2):Article No. 30 [14] Ahmad A, Brown G. Random projection random discretization ensembles-ensembles of linear multivariate decision trees. IEEE Transactions on Knowledge and Data Engineering, 2014, 26(5):1225-1239 doi: 10.1109/TKDE.2013.134 [15] 毛国君, 胡殿军, 谢松燕.基于分布式数据流的大数据分类模型和算法.计算机学报, 2017, 40(1):161-175 doi: 10.11897/SP.J.1016.2017.00161Mao Guo-Jun, Hu Dian-Jun, Xie Song-Yan. Models and algorithms for classifying big data based on distributed data streams. Chinese Journal of Computers, 2017, 40(1):161-175 doi: 10.11897/SP.J.1016.2017.00161 [16] Quinlan J R. Induction of decision trees. Machine Learning, 1986, 1(1):81-106 [17] Quinlan J R. C4. 5: Programs for Machine Learning. San Mateo, CA, USA: Morgan Kaufmann, 1993. [18] Breiman L, Friedman J H, Olshen R A, Stone C J. Classification and Regression Trees. Belmont, CA, USA:CRC Press, 1984. [19] Brodley C E, Utgoff P E. Multivariate decision trees. Machine Learning, 1995, 19(1):45-77 [20] Ferri C, Flach P A, Hernández-Orallo J. Improving the AUC of probabilistic estimation trees. In: Proceedings of the 2003 European Conference on Machine Learning. Berlin, Heidelberg, Germany: Springer, 2003. 121-132 [21] Mingers J. An empirical comparison of pruning methods for decision tree induction. Machine Learning, 1989, 4(2):227-243 doi: 10.1023/A:1022604100933 [22] Esposito F, Malerba D, Semeraro G, Kay J. A comparative analysis of methods for pruning decision trees. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1997, 19(5):476-491 [23] Fournier D, Crémilleux B. A quality index for decision tree pruning. Knowledge-Based Systems, 2002, 15(1-2):37-43 doi: 10.1016/S0950-7051(01)00119-8 [24] Osei-Bryson K M. Post-pruning in decision tree induction using multiple performance measures. Computers and Operations Research, 2007, 34(11):3331-3345 [25] Elomaa T, Kääriäinen M. An analysis of reduced error pruning. Journal of Artificial Intelligence Research, 2001, 15(1):163-187 [26] Quinlan J R. Simplifying decision trees. International Journal of Man-Machine Studies, 1987, 27(3):221-234 doi: 10.1016/S0020-7373(87)80053-6 [27] 包研科, 赵凤华.多标度数据轮廓相似性的度量公理与计算.辽宁工程技术大学学报(自然科学版), 2012, 31(5):797-800 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=lngcjsdxxb201205053Bao Yan-Ke, Zhao Feng-Hua. Measure axiom of outline similarity of multi-scale data and its calculation. Journal of Liaoning Technical University (Natural Science), 2012, 31(5):797-800 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=lngcjsdxxb201205053 [28] Bache K, Lichman M. UCI machine learning repository[Online], available: http://archive.ics.uci.edu/ml, January 1, 2016 [29] Stisen A, Blunck H, Bhattacharya S, Prentow T S, Kjaergaard M B, Dey A, Sonne T, Jensen M M. Smart devices are different: assessing and mitigating mobile sensing heterogeneities for activity recognition. In: Proceedings of the 13th ACM Conference on Embedded Networked Sensor Systems. Seoul, South Korea: ACM, 2015. 127-140 [30] Zhou Z H. Ensemble Methods: Foundations and Algorithms. Boca Raton, FL, USA: Chapman and Hall/CRC, 2012. 期刊类型引用(16)
1. 杨晓波，李颖，魏子睿. 基于JSP技术的高压客户业扩报装系统. 自动化技术与应用. 2022(09): 79-82 . 
百度学术2. 袁智勇，肖泽坤，于力，徐全，林跃欢，李培强，何西. 智能电网大数据研究综述. 广东电力. 2021(01): 1-12 . 百度学术3. 付维明，秦家虎，朱英达. 基于扩散方法的分布式随机变分推断算法. 自动化学报. 2021(01): 92-99 . 本站查看4. 龚健虎，张跃进. 深度AWB结合改进DIT的高效大数据分类. 计算机工程与设计. 2021(02): 468-474 . 百度学术5. 徐军委，刘长胜. 基于人工智能和深度数据分析技术的考评系统设计. 电子设计工程. 2021(06): 179-183 . 百度学术6. 薛岩. 克苏鲁式数据结构模型理论. 科技创新与应用. 2021(15): 23-25 . 百度学术7. 张宇，刘威，邵良杉. 面向分布式在线学习的共享数据方法. 控制与决策. 2021(08): 1871-1880 . 百度学术8. 尹春勇，张帼杰. 面向分布式漂移数据流的集成分类模型. 计算机应用. 2021(07): 1947-1955 . 百度学术9. 赖红清. 基于逻辑回归的企业二次创业金融数据分类方法研究. 重庆工商大学学报(自然科学版). 2021(05): 114-119 . 百度学术10. 唐雅娜，袁琛. 基于邻域相似的大数据流滞后相关性挖掘仿真. 计算机仿真. 2020(06): 318-321+337 . 百度学术11. 钟章生，陈世炉，陈志龙. 利用并行惯性权重OOL-FA的大数据分类. 计算机工程与设计. 2020(10): 2818-2824 . 百度学术12. 王金焱. 分布式网络混合云数据分类捕获方法研究. 安阳工学院学报. 2020(06): 59-62+74 . 百度学术13. 吴增源，周彩虹，刘畅，郑素丽. 基于不平衡大数据的CS-AdaBoost-DT模型在家电产品质检中的应用. 工业工程与管理. 2020(05): 42-49 . 百度学术14. 袁焦，王珣，潘兆马，杨学锋，邹文露. 基于机器学习的列车设备故障预测模型研究. 计算机与现代化. 2020(12): 49-54 . 百度学术15. 李晓峰，李东. 基于SOM聚类的多模态医学图像大数据挖掘算法. 西安工程大学学报. 2019(04): 462-467 . 百度学术16. 王艳，蒋天伦. 融合决策树的分布式多工厂协同生产调度方法. 系统仿真学报. 2019(11): 2181-2197 . 百度学术其他类型引用(11)
-
下载:
计量
- 文章访问数: 2458
- HTML全文浏览量: 436
- PDF下载量: 843
- 被引次数: 27
