基于信息熵差异性度量的数据流增量集成分类算法

doi:10.11959/j.issn.1000-0801.2015014

摘要/Abstract

摘要：

摘要：对分类器之间的差异性进行了研究，提出了一种基于信息熵差异性度量的增量集成分类算法，将信息熵差异性度量方法融入到基分类器选择过程中，通过对训练数据集的基分类结果的信息熵差异度计算，采用循环迭代优化的选择方法，以熵差异性最优化为约束目标，动态调整基分类器个数，实现了分类准确稳定，减少了系统开销。通过实验比对，证明了算法在数据流处理时比其他算法具有更小的开销和较强的适应性。

关键词: 集成分类器, 差异性度量, 信息熵, 增量集成, 数据流

Abstract:

The diversity between classifiers was studied and an incremental classification algorithm for data stream based on information entropy diversity measure was proposed, the method of information entropy diversity measure was integrated into the selection process of base classifiers, the information entropy diversity of base classifier which trained from training data was calculated, by means of cyclic iterative as optimization method and entropy diversity as optimization constrained goal, the numbers of base classifiers was dynamic adjusted that improved the classification accuracy and stability to reduce system costs. The experiments prove that the algorithm has less cost and strong adaptability compare with other data stream algorithm when processing data stream.

Key words: ensemble classifier, diversity measure, entropy of information, incremental ensemble, data stream

琚春华,邹江波. 基于信息熵差异性度量的数据流增量集成分类算法[J]. 电信科学, 2015, 31(2): 86-96.

Chunhua Ju,Jiangbo Zou. An Incremental Classification Algorithm for Data Stream Based on Information Entropy Diversity Measure[J]. Telecommunications Science, 2015, 31(2): 86-96.

图/表 16

图1

图2

图3

表1

表2

表3

图4

图5

表4

表5

图6

图7

图8

图9

表6

表7

参考文献 21

1	Chu F , Zaniolo C . Fast and light boosting for adaptive mining of data streams. Proceedings of the 5th Pacific-Asia Conference on Knowledge Discovery and Data Mining, Sydney,Australia, 2004
2	孙岳，毛国君，刘旭等．基于多分类器的数据流中的概念漂移挖掘．自动化学报， 2008,1(38): 93～96 Sun Y , Mao G J , Liu X , et al. Mining concept drifts from data streams based on multi-classifiers. ACTA Automatica Sinica, 2008,1(38): 93～96
3	Kolter J Z , Maloof M A . Using additive expert ensemble to cope with concept drift. Proceedings of the 22nd International Conference on Machine Learning, Bonn,Germany, 2005
4	琚春华，陈之奇．一种挖掘概念漂移数据流的模糊积分集成分类方法．山东大学学报（工学版）, 2011,4(41): 44～48 Ju C H , Chen Z Q . A method of fuzzy integral ensemble classifiers for handling concept-drifting data streams. Journal of Shandong University of Technology, 2011,4(41): 44～48
5	Zhou Z H , Wu J X , Tang W . Ensembling neural networks: many could be better than all. Artificial Intelligence, 2002,137(12): 239～263
6	Bi Y X . The impact of diversity on the accuracy of evidential classifier ensembles. International Journal of Approximate Reasoning, 2012(53)
7	罗建宏，陈德钊．兼顾正确率和差异性的自适应集成算法及应用．浙江大学学报（工学版）, 2011,45(1): 558～562 Luo J H , Chen D Z . Application of adaptive ensemble algorithm based on correctness and diversity. Journal of Zhejiang University（Engineering Science）, 2011,45(1): 558～562
8	琚春华，邹江波，张芮等．基于MapReduce技术的并行集成分类算法．电信科学， 2012,28(7): 40～46 Jun C H , Zou J B , Zhang R , et al. Parallel ensemble classification algorithm based on the MapReduce technology. Telecommunications Science, 2012,28(7): 40～46
9	孙博，王建东，陈海燕等．集成学习中的多样性度量．控制与决策， 2014,29(3): 385～395 Sun B , Wang J D , Chen H Y , et al. Diversity measures in ensemble learning. Control and Decision, 2014,29(3): 385～395
10	Chu R , Wang M , Zeng X Q , et al. A new diverse measure in ensemble learning using unlabeled data. Proceedings of the 4th Int Conf on Computational Intelligence, Communication Systems and Networks, Washington,DC,USA, 2012
11	Li N , Yu Y , Zhou Z H . Diversity regularized ensemble pruning. Proceedings of the European Conf on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, Athens,Greece, 2012
12	杨显飞，张健沛，杨静．数据流选择性集成的两阶段动态融合方法．计算机工程， 2010,20(37): 180～184 Yang X F , Zhang J P , Yang J . Two-phase dynamic fusion method for data stream selective integration. Computer Engineering, 2010,20(37): 180～184
13	Sun S L , Zhang C S . Subspace ensembles for classification. Statistical Mechanics and Its Applications, 2007,385(1): 199～207
14	Opitz D , Maclin R . Popular ensemble methods: an empirical study. Journal of Artificial Intelligence Research, 1999(11)
15	Kuncheva L I , Whitaker C J . Measures of diversity in classifier ensembles and their relationship with the ensemble accuracy. Machine Learning, 2003,51(2): 181～207
16	Gupta L , Kota S , Molfese D L . Diversity-based selection of components for fusion classifiers. Proceedings of the 32nd Annual International Conference of the IEEE EMBS, Buenos Aires, Argentina 2010:6304～6307
17	Minku L L , White A P , Yao X . The impact of diversity on online ensemble learning in the presence of concept drift. IEEE Transactions on Knowledge and Data Engineering, 2010,22(5): 730～742
18	Grbovic M , Vucetic S . Tracking concept change with incremental boosting by minimization of the evolving exponential loss. Machine Learning and Knowledge Discovery in Databases, 2011,6911:516～532
19	邹江波．面向数据流挖掘的集成分类模型研究（硕士学位论文）．浙江工商大学， 2014 Zou J B . Reaserch on ensemble classifier model for data stream mining（master dissertation）. Zhe Jiang Gong Shang University, 2013
20	杨长盛．基于成对差异性度量的选择性集成学习方法研究（硕士学位论文）．安徽大学， 2010 Yang C S . Selective ensemble learning algorithm based on pairwise diversity measures（master dissertation）. An Hui Univeristy, 2010
21	Zhang P , Zhu X Q , Shi Y . Robust ensemble learning for mining noisy data streams. Decision Support Systems, 2011,50(2): 469～479

	D_k正确分类	D_k错误分类
D_i正确分类	N¹¹	N¹⁰
D_i错误分类	N⁰¹	N⁰⁰

	Z₁	Z₂	Z₃	Z₄	Z₅	Z₆	Z₇	Z₈	Z₉	Z₁₀
D₁	0	0	0	1	1	0	1	1	1	1
D₂	1	1	1	1	0	1	0	0	0	1

	Z₁	Z₂	Z₃	Z₄	Z₅	Z₆	Z₇	Z₈	Z₉	Z₁₀
D₁	1	0	1	1	1	1	1	0	0	1
D₂	1	1	1	1	1	1	1	1	0	1

编号	分类器名称	分类器的简单描述
1	Na_?ve Bayes	朴素贝叶斯分类算法，实验中算法对连续特征属性运用核密度估计方法，而不是采用以前的样本服从一个标准正态分布
2	SMO	序列最小优化算法通过采用多项式核函数训练支持向量机
3	J48	J48决策树算法，采用Java实现C4.5算法
4	IBk	IBk是基于样本实例的一种分类算法
5	KStar	KStar分类算法通过使用最近邻和熵距离作为分类方法
6	NNge	NNge分类算法采用非嵌套泛化样本作为训练
7	PART	一种利用不完整的决策树在数据集中提取规则的算法
8	AOD	一种有效的朴素贝叶斯分类器的集成算法，它通过为每个输入属性分别建立一个超1-依赖贝叶斯分类器，然后将它们对新的样例的预测值进行平均作为集成的最终结果

数据集名称	数据量	类别数/个	属性数（标称属性/数值属性）/个
HP1	200000	10	5（0/5）
HP2	400000	5	10（0/10）
RT1	200000	8	8（4/4）
RT2	400000	4	12（7/5）
SEA1	500000	2	3（0/3）
SG1	500000	2	3（3/0）