文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 自然科学 > 基于模拟退火遗传算法的贝叶斯分类
侵权投诉

基于模拟退火遗传算法的贝叶斯分类

计 算 机 工 程 第 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—

第1页

你可能喜欢

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email