改进的朴素贝叶斯增量算法研究

doi:10.11959/j.issn.1000-436x.2016199

摘要/Abstract

摘要：

提出了一种新增特征的朴素贝叶斯增量算法。在无标注语料增量样本的选择上，借助传统的类置信度阈值，构建一个最小后验概率作为样本选择的双阈值，当识别到增量语料中有新的特征时，会将该特征加入到特征空间，并对分类器进行相应的更新，发现对类置信度阈值起到很好的补充作用，最后利用了无标注和有标注语料验证所提算法。实验结果表明，改进的朴素贝叶斯增量算法较传统增量算法表现出了更优的增量学习效果。

关键词: 朴素贝叶斯, 增量算法, 特征空间, 评价指标

Abstract:

A novel Naive Bayes incremental algorithm was proposed,which could select new features.For the incremental sample selection of the unlabeled corpus,a minimum posterior probability was designed as the double threshold of sample selection by using the traditional class confidence.When new feature was detected in the corpus,it would be mapped into feature space,and then the corresponding classifier was updated.Thus this method played a very important role in class confidence threshold.Finally,it took advantage of the unlabeled and annotated corpus to validate improved incremental algorithm of Naive Bayes.The experimental results show that an improved incremental algorithm of Naive Bayes significantly outperforms traditonal incremental algorithm.

Key words: Naive Bayes, incremental algorithm, feature space, evaluation index

曾谁飞,张笑燕,杜晓峰,陆天波. 改进的朴素贝叶斯增量算法研究[J]. 通信学报, 2016, 37(10): 81-91.

Shui-fei ZENG,Xiao-yan ZHANG,Xiao-feng DU,Tian-bo LU. Improved incremental algorithm of Naive Bayes[J]. Journal on Communications, 2016, 37(10): 81-91.

图/表 8

表1

表2

图1

图2

表3

表4

表5

表6

参考文献 26

[1]	CHRISTOPHER M . Pattern recognition and machine learning[M]. New York: SpringerPress, 2006.
[2]	ESCALANTE H J , MORALES E F , SUCAR L E . A Naive Bayes baseline for early gesture recognition[J]. Pattern Recognition Letters, 2016,73: 91-99.
[3]	DIMKOVSKI M , AN A . A Bayesian model for canonical circuits in the neocortex for parallelized and incremental learning of symbol representations[J]. Neurocomputing, 2015,149: 1270-1279.
[4]	FENG L , WANG Y , ZUO W . Quick online spam classification method based on active and incremental learning[J]. Journal of Intelligent ＆Fuzzy Systems, 2015,30(1): 17-27.
[5]	董立岩, 隋鹏, 孙鹏 ,等. 基于半监督学习的朴素贝叶斯分类新算法[J]. 吉林大学学报:工学版, 2016(03). DONG L Y , SUI P , SUN P ,et al. Novel Naive Bayes classification al-gorithm based on semi-supervised learning[J]. Journal of Jilin Univer-sity,Engineering and Technology Edition, 2016(03).
[6]	罗福星 . 增量学习朴素贝叶斯中文分类系统的研究[D]. 长沙:中南大学, 2008. LUO F X . Research on incremental learning naive Bayesian classifica-tion system[D]. Changsha:Central South University, 2008.
[7]	张智敏 . 基于增量学习的分类算法研究[D]. 广州:华南理工大学, 2010. ZHANG Z M . The study of classification based on incremental learn-ing[D]. Guangzhou:South China University of Technology, 2010.
[8]	侯凯 . 加权贝叶斯增量学习中文文本分类研究[D]. 长沙:长沙理工大学, 2013. HOU K . The weighted Bayesian incremental learning Chinese text classification study[D]. Changsha:Changsha University of Science ＆Technology, 2013.
[9]	李金华, 梁永全, 吕芳芳 . 一种加权朴素贝叶斯分类增量学习模型[J]. 计算机与现代化, 2010,2010(5): 30-32. LI J H , LIANG Y Q , LV F F . An incremental learning model of weighted Naive Bayesian cassification[J]. Computer and Moderniza-tion, 2010,2010(5): 30-32.
[10]	罗福星, 刘卫国 . 一种朴素贝叶斯分类增量学习算法[J]. 微计算机应用, 2008,29(6): 107-112. LUO F X , LIU W G . An incremental learning algorithm based on weighted Naive Bayes classification[J]. Microcomputer Applications, 2008,29(6): 107-112
[11]	宫秀军, 刘少辉, 史忠植 . 一种增量贝叶斯分类模型[J]. 计算机学报, 2002,25(6): 645-650. GONG X J , LIU S H , SHI Z Z . An incremental Bayes classification model[J]. Chinese Journal of Computers, 2002,25(6): 645-650
[12]	高洁, 吉根林 . 一种增量式 Bayes 文本分类算法[J]. 南京师范大学学报(工程技术版), 2004,4(3): 49-52. GAO J , JI G L . Incremental Bayes text categorization algorithm[J]. Journal of Nanjing Normal University(Engineering and Technology), 2004,4(3): 49-52.
[13]	王小林, 镇丽华, 杨思春 ,等. 基于增量式贝叶斯模型的中文问句分类研究[J]. 计算机工程, 2014,40(9): 238-242. WANG X L , ZHEN L H , YANG S C ,et al. Chinese question classifi-cation research based on incremental Bayes model[J]. Computer En-gineering, 2014,40(9): 238-242.
[14]	段华 . 支持向量机的增量学习算法研究[D]. 上海:上海交通大学, 2008. DUAN H . Study on the incremental learning algorithms for support vector machines[D]. Shanghai:Shanghai Jiao Tong University, 2008.
[15]	姜卯生, 王浩, 姚宏亮 . 朴素贝叶斯增量学习序列算法研究[J]. 计算机工程与应用, 2004,40(14): 57-59. JIANG M S , WANG H , YAO H L . Studies on incremental learning sequence algorithm of Naive Bayesian classifier[J]. Computer Engi-neering and Applications, 2004,40(14): 57-59
[16]	ZHANG H , SHENG S . Learning weighted Naive Bayes with accurate ranking[C]// Fourth IEEE International Conference on Data Mining. 2004: 567-570.
[17]	READ J , BIFET A , PFAHRINGER B ,et al. Batch-in cremental versus instance-incremental learning in dynamic and evolving data[C]// International Symposium on Intelligent Data Analysis. Springer Berlin Heidelberg, 2012: 313-323
[18]	GU P , ZHU Q S , ZHANG C . A multi-view approach to semi-supervised document classification with incremental Naive Bayes[J]. Computers＆ Mathematics with Applications, 2009,57(6): 1030-1036.
[19]	MUHLBAIER M D , TOPALIS A , POLIKARO R . NC:combining ensemble of classifiers with dynamically weighted consult-and-vote for efficient incremental learning of new classes[J]. IEEE Transactions on Neural Networks, 2009,20(1): 152-168.
[20]	BOUGUELIA M , BELA?D Y , BELA?D A , . A stream-based semi-supervised active learning approach for document classification[C]// 2013 12th International Conference on Document Analysis and Recognition. IEEE, 2013: 611-615.
[21]	FONG S,BIUK-AGHAI R P , SI Y ,et al. A lightweight data preprocessing strategy with fast contradiction analysis for incremental classifier learning[J]. Mathematical Problems in Engineering, 2015,2015: 1-11.
[22]	EYHERAMENDY S , LEWIS D D , MADIGAN D . On the Naive Bayes model for text categorization[J/OL]. , 2003.
[23]	PEDRO D , MICHAEL P . On the optimality of the simple Bayesian classifier under zero-one loss[J]. Machine Learning, 1997,29: 103-130.
[24]	ANDREW M C , KAMAL N . A comparison of event models for Naive Bayes text classification[J]. In AAAI-98 Workshop on Learning for Text Catego, 2009,62(2): 41-48.
[25]	AY N , JORDAN M . On discriminative vs generative classifiers:a comparison of logistic regression and Naive Bayes[J]. Advances in Neural Information Processing Systems, 2002,2(3): 169-187.
[26]	ZHANG H , . The optimality of Naive Bayes[C]// The Seventeenth International Florida Artificial Intelligence Research Society Conference. Miami Beach,Florida,USA, 2004: 562-567.

训练语料/份	大类	描述	人物	地点	数字	实体	时间	未知	总数
	初始训练集问题分布	707	300	843	968	1 118	539	9	4 484
9∶1
	增量集问题分布	78	33	93	108	124	59	1	496
	初始训练集问题分布	628	267	749	861	994	479	8	3 986
4∶1
	增量集问题分布	157	66	187	215	248	119	2	994
	初始训练集问题分布	589	250	702	807	932	449	8	3 737
3∶1
	增量集问题分布	196	83	234	269	310	149	2	1 243
	初始训练集问题分布	524	222	624	718	828	399	7	3 322
2∶1
	增量集问题分布	261	111	312	358	414	199	3	1 658
	初始训练集问题分布	393	167	468	538	621	299	5	2 491
1∶1
	增量集问题分布	392	366	468	538	621	299	5	2 689
	初始训练集问题分布	262	111	312	359	414	200	4	1 662
1∶2
	增量集问题分布	523	222	624	717	828	398	6	3 318
	初始训练集问题分布	197	84	234	269	311	150	3	1 248
1∶3
	增量集问题分布	588	249	702	807	931	448	7	3 732
	初始训练集问题分布	157	67	188	216	249	120	2	999
1∶4
	增量集问题分布	628	266	748	860	993	478	8	3 981
	初始训练集问题分布	79	34	34	108	125	60	1	441
1∶9
	增量集问题分布	706	299	902	968	1 117	538	9	4 539
	总计	785	333	936	1 076	1 242	598	10	4 980

训练语料/份	直接训练	初始训练	传统增量	改进增量
9∶1	77.63%	77.55%	77.25%	77.70%
4∶1	77.63%	78.31%	77.85%	77.85%
3∶1	77.63%	77.63%	78.16%	77.70%
2∶1	77.63%	78.23%	77.78%	77.70%
1∶1	77.63%	75.34%	77.47%	77.55%
1∶2	77.63%	72.60%	76.18%	77.47%
1∶3	77.63%	72.37%	74.51%	77.63%
1∶4	77.63%	73.74%	75.49%	77.25%
1∶9	77.63%	70.78%	71.84%	77.25%

增量系数α	增量准确数量	增量总数量	分类准确数量	增量准确率	增量召回率
10	819	896	1 021	91.41%	80.22%
20	756	813	1 021	92.99%	74.05%
50	669	709	1 021	94.36%	65.52%
100	609	638	1 021	95.45%	59.65%
200	543	561	1 021	96.79%	53.18%
400	468	482	1 021	97.10%	45.84%
600	443	454	1 021	97.58%	43.39%
800	402	412	1 021	97.57%	39.37%
1 000	384	393	1 021	97.71%	37.61%
2 000	324	332	1 021	97.59%	31.73%
4 000	277	282	1 021	98.23%	27.13%
6 000	258	262	1 021	98.47%	25.27%
8 000	235	239	1 021	98.33%	23.02%
10 000	223	226	1 021	98.67%	21.84%
20 000	200	203	1 021	98.52%	19.59%
40 000	165	166	1 021	99.40%	16.16%
60 000	153	154	1 021	99.35%	14.99%
80 000	146	147	1 021	99.32%	14.30%
100 000	137	137	1 021	100.00%	13.42%

增量系数β	增量准确数量	增量总数量	分类准确数量	增量准确率	增量召回率
1	638	769	1 021	82.96%	62.49%
2	455	525	1 021	86.67%	44.56%
3	338	394	1 021	85.79%	33.10%
4	252	298	1 021	84.56%	24.68%
5	184	223	1 021	82.51%	18.02%
6	135	170	1 021	79.41%	13.22%
7	105	136	1 021	77.21%	10.28%
8	82	90	1 021	91.11%	8.03%
9	64	71	1 021	90.14%	6.27%
10	48	54	1 021	88.89%	4.70%
11	42	45	1 021	93.33%	4.11%
12	18	18	1 021	100.00%	1.76%

增量系数α	增量准确数量	增量总数量	分类准确数量	增量准确率	增量召回率
10	294	298	1 021	98.66%	28.80%
20	274	276	1 021	99.28%	26.84%
50	254	255	1 021	99.61%	24.88%
100	236	237	1 021	99.58%	23.11%
200	224	225	1 021	99.56%	21.94%
400	190	190	1 021	100.00%	18.61%
600	181	181	1 021	100.00%	17.73%
800	169	169	1 021	100.00%	16.55%
1 000	165	165	1 021	100.00%	16.16%