一种基于遗传算法的数据抽样方法

摘要：朴素贝叶斯分类器是一种基于独立假设的贝叶斯定理的简单概率分类器，依靠精确的自然概率模型，在有监督学习的样本集中能获取得非常好的分类效果。本文以朴素贝叶斯分类器为基础，提出一种最优保存简单遗传算法为搜索方法，随机抽样分类测试作为适应性函数来设计实现实例选择算法。实验表明，该抽样方法在不降低朴素贝叶斯分类器精度的前提下明显降低计算代价，对部分数据集还可有效地提高分类器的分类精度。

关键词：贝叶斯分类器 数据质量 实例选择 数据挖掘

中图分类号：TP18 文献标识码：A 文章编号：1007-9416（2013）01-0107-01

贝叶斯分类器是建立在贝叶斯统计学和贝叶斯网络方法基础上的[1][2]，是一种最优分类器模型。遗传算法对解决多目标优化问题和模式优化问题上有着较好的性能[3]，本文使用遗传算法做样本搜索工作。

1 算法设计

通过贝叶斯分类器的数据实例过滤器算法，选择实例用抽样分类测试作实例子集的评价指标，使用数据集的子集构建分类器，对原始数据集随机抽样，选一个测试用子集，再使用该分类器对其测试，最后通过映射调整分类的正确率，作为子集的质量标准。本文使用最优保存遗传算法 （MOSGAS），可以证明[4]满足公式（1）的定义，即最优保存简单遗传算法具有全局收敛性。即可证明算法从任意状态出发，都收敛到最大值概率1，所以选用最优保存遗传算法作为数据抽样的搜索方法。

（1）

通过学习子集DS建立一个分类器函数CF后，建立随机测试集TS（大小为TSN），数据子集的质量f（DS）表示为公式（2），（3）所示。公式（2）中的F函数是用来评价单个实例的分类效果，（3）则是对F函数值进行统计的函数。

（2）

（3）

对原始数据集进行测试耗时巨大，所以随机抽取样本数据，抽样测试设定样本大小，方便控制运行时间，对抽样数据多次运行，保证数据测试结果更逼真。算法步骤如下：（1）获取原始数据集；（2）初始化种群；（3）初始化当前世代的随机抽样测试样本；（4）对当前种群中的个体进行评估；（5）对评估值映射调整；（6）保留最优秀个体；（7）使用适应度比例方法选择个体，进行交叉联合和变异；（8）判断是否达到结束条件，若没有则返回3；（9）选择最优个体，返回数据子集。

2 实验结果和分析

在Weka系统上实现算法，使用UCI数据集验证。选取较大规模的数据集对算法进行测试验证。使用GAIS指代本算法。使用的数据集如表1所示。

把数据集分为中型和大型数据集。对中型数据集，做10%，30%，50%抽样构建分类器，以原始数据集测试，比较是否使用抽样算法的分类精度。分类性能比较的折线图如（图1）所示。

从图1看到，GAIS对中型数据进行抽样有良好性能，相对原始数据可保证分类精度不下降。30%和50%抽样的分类精度折线基本重合，即抽样基本等效。对大型数据集进行1%，3%，5%抽样，用原数据集建立分类器，进行10重交叉验证如图2所示。从图2看到，对大型数据集，使用极少样本可达到非常接近，甚至超出使用原始数据集的分类精度。这说明对大型数据集，选择一个最优的子集可以提高分类算法的效率和精度。

3 结论及展望

使用遗传算法进行搜索方法，随机抽样分类测试作为评价函数的实例过滤器算法，可以有效地降低数据集的规模，同时保证使用经过过滤的数据集建立的分类器的性能，比原始的数据集建立的分类器的性能要高。而且对于大部分数据集可有效地增加分类器的分类精度。

参考文献

[1]I.H.Witten，E.Frank.董琳，邱泉，于晓峰等译.数据挖掘实用机器学习技术[M].北京：机械工业出版社，2005.

[2]N.Friedman，M.Goldszmidt. Building Classifiers using Bayesian Networks.In proceedings of Thirteenth National Conference on Artificial Intelligence（AAAI）.VOL.2，1996.pp.1277-1284.

[3]F.Ros，S.Guillaume，M.Pintore，J.R.Chretien.Hybrid genetic algorithm for dual selection.Springer London，2007.

[4]曲中水，刘淑兰.基本遗传算法的收敛性分析方法.哈尔滨理工大学计算机与控制学院，黑龙江哈尔滨，2002.