计 算 机 工 程 第 33 卷 第9期
Vol.33 No.9 Computer Engineering ·人工智能及识别技术·
文章编号:1000—3428(2007)09—0219—03
文献标识码:A
2007年5月
May2007
中图分类号:TP301
基于模拟退火遗传算法的贝叶斯分类
胡为成1,程转流1,王本年1,2
(1. 铜陵学院计算机系,铜陵 244000;2. 南京大学计算机学院,南京 240000)
摘 要:朴素贝叶斯分类器是一种简单而高效的分类器,但是其属性独立性假设限制了对实际数据的应用。文章提出一种新的算法,该算法为避免数据预处理时的属性约简对分类效果的直接影响,在训练集上通过随机属性选取生成若干属性子集,以这些子集构建相应的朴素贝叶斯分类器,采用模拟退火遗传算法进行优选。实验表明,与传统的朴素贝叶斯方法相比,该方法具有更好的性能。 关键词:数据挖掘;朴素贝叶斯;模拟退火算法;遗传算法;属性约简;适应度函数
Bayesian Classification Based on Simulated Annealing
Genetic Algorithms
HU Weicheng1, CHENG Zhuanliu1, WANG Bennian1,2
(1. Department of Computer, Tongling College, Tongling 244000; 2. College of Computer, Nanjing University, Nanjing 240000)
【Abstract】Although Naïve Bayesian classifier is a simple and highly efficient classification method, its attribute of independence assumptionlimits its real application. A new algorithm is introduced in this paper to avoid the direct influence of feature reduction on the performance ofclassification. This algorithm generates certain attribute subsets of the training sets through randomattribute selection, constructs the correspondingNaïve Bayesian classifiers, and optimizes the Bayesian classifiers by using simulated annealing genetic algorithms. Experiment shows that thisalgorithm has better performance when compared with traditional Naïve Bayesian methods.
【Key words】Data mining; Naïve Bayesian; Simulated annealing algorithms; Genetic algorithms; Feature reduction; Fitness function
数据挖掘(Data Mining, DM)是从大量的、不完全的、有噪声的、模糊的、随机的数据中提取隐含的、事先未知的、潜在有用的信息的处理过程。分类预测是数据挖掘中的重要分支。分类是找出一组能够描述数据集合典型特征的模型,以便对未知变量做出预测或分类。分类算法的核心部分是构造分类器。
朴素贝叶斯分类器(Naïve Bayesian Classifiers, NBC)[1]由于计算高效、精确度高,并具有坚实的理论基础而得到广泛的应用[2,3]。但由于朴素贝叶斯分类器的条件独立性假设,使得所选数据集的条件属性集在预处理时必须进行属性约简。
遗传算法(Genetic Algorithm, GA)是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化概率搜索算法,具有较强的鲁棒性,其思想简单、应用广泛[4]。本文结合改进的模拟退火遗传算法,提出一种基于模拟退火遗传算法的朴素贝叶斯分类方法。 i=i+1;
如果满足则转步骤(5),否则转步骤(2); (4)检查终止条件,
(5)当前解Si为最优解,输出结果,停止。 Metropolis抽样算法描述:
(1)令k=0时,当前解S(0)=S,在温度T下,进行以下各步操作;
(2)按某个规定的方式根据当前解S(k)所处的状态S产生一个近邻子集N(S(k)) S,从N(S(k))中随机得到一个新状
计算能量之差△C’=C(S’)-C(S(k)); 态S’作为下一个候选解,
(3)如果△C’<0,则接受S’作为下一个当前解,否则,以概率exp(-△C’/T) 接受S’作为下一个当前解。若S’被接受,则令S(k+1)= S’,否则S(k+1)= S(k);
(4)k=k+1,检查算法是否满足终止条件,如果满足则转步骤(5),否则转步骤(2);
(5)返回S(k),结束。
1 模拟退火算法
模拟退火算法的基本思想:通过模拟高温物体退火过程的方法,来找到优化问题的全局最优或近似全局最优解。从统计物理学的观点看,随差温度的降低,物质的能量逐渐趋近于一个较低的状态,并最终达到某种平衡[5~7]。
模拟退火算法描述如下:
(1)选S0作为初始状态,令S(0)=S0,同时设初始温度T,令i=0;
(2)令T=Ti,以T和Si来调用Metropolis抽样算法,返回状态S作为本算法的当前解,Si=S;
(3)按照一定方式进行降温,即T=Ti+1,其中Ti+1<Ti,
2 基于模拟退火遗传算法的朴素贝叶斯分类
(1)遗传算法的基本思想
遗传算法是从代表问题可能潜在解集的一个种群开始的,而一个种群则由经过基因编码的一个数目的个体组成。每个个体实际上是染色体带有特征的实体。染色体作为遗传物质的主要载体,即多个基因的集合,其内部表现(即基因型)
基金项目:安徽省高等学校自然科学基金资助项目(KJ2007B236);安徽省高等学校自然科学基金资助重点项目(2006kj027A)
作者简介:胡为成(1975-),男,讲师、硕士,主研方向:数据挖掘,遗传程序设计等;程转流,讲师;王本年,教授、博士 收稿日期:2006-07-10 E-mail:huwc@tlu.edu.cn
—219—
基于遗传算法的朴素贝叶斯分类研究_自然科学_专业资料。数据挖掘相关知识以及算法...基于模拟退火算法的遗传程序设计方法,计算机工 程与设计,2007.2,己录用. 3.胡...
http://www.cnki.net 第 1 期 胡为成等 : 基于遗传算法的朴素贝叶斯分类 ...基于模拟退火遗传算法的关联规λ= 1 记录数 属性数 3 196 8 124 625 286 ...
基于遗传算法的朴素贝叶斯分类_专业资料。朴素贝叶斯分类器是一种简单而高效的... 基于模拟退火遗传算法的... 2人阅读 3页 2.00 基于ICA方法的朴素贝叶斯...
关键词:聚类;遗传算法;模拟退火算法;模拟退火遗传算法 中图法分类号:,-(*%+ + + 文献标识码:.+ + + 文章编号:%""%$ (’*& !""&) ""!#$ "( (...
2008年 序号 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 科研热词 遗传算法 模拟退火 遗传模拟退火算法 贝叶斯网络 贝叶斯网分解 认知无线电 认知引擎...
模糊聚类 遗传算法 模拟退火算法 树型编码 中图分类号 JK1%& 文章编号 &""...% " ’$ 林士敏#王双成#陆玉昌 $ 贝叶斯方法的学习机制与问题求解 OPQ$ ...
关键词:聚类;遗传算法;模拟退火算法;模拟退火遗传算法 中图法分类号:,-(*%+ + + 文献标识码:.+ + + 文章编号:%""%$ (’*& !""&) ""!#$ "( (...
针对高维数据对象 , 特征选择 不仅可以在保证数据完整性的情况下减少特征维数 ,还能够提高分类精度 。文中提出了一种基于 自适应模拟退火遗传算法的特征选择方法 ,...
模拟退火遗传算法 模拟退火遗传算法 模拟退火遗传算法来源于固体退火原理添加了遗传算法的交叉性, 模拟退火算法模拟将 固体加温至充分高, 再让其徐徐冷却, 加温时,...
热门文档