…, CN 重要性的权值矢量 , w ik 代表第 k 个分类器在对类
别 Ci 的分类中 ,相对于其他分类器的重要性 。
由各个分类器给出的对于类 Ci 的分类结果 mi1 , mi2 ,
…, mi K 加权相加相应的权值 w i1 , w i2 , …, w i K , 得到关于
此类最终的分类结果 oi ,用公式表达即为 :
在遗传算法中 ,需要把假设表示成一个称作染色体 (chromosome) 的串 ,通常是二进制串 ,然后再利用交叉和 变异等遗传算子对这些串进行操作 ,以生成新的串 ,即下 一代染色体 。在这里 ,把假设表示成一个真实值的串 。这 些真实 值 的 取 值 即 权 值 w i1 , w i2 , …, w i K ( i = 1 ,2 , …, N) 。要解决的问题就是在搜索空间中找到最优的权值矩 阵 ,以合并 K 个分类器产生的分类结果 。串的表示方法如 图 4 所示 。
图 1 串行分类器合并的结构示意图
图 2 并行分类器合并的结构示意图 分类器输出的分类结果有三种形式 :抽象形式 、排序 形式和分类度量值形式 。抽象形式的输出直接给出输入 数据属于某一类的类别标签 ;排序形式将输入数据按照属 于每一类的可能性大小排序后的排序结果作为输出 ;分类
© 1995-2005 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved.
·17 ·
续表 ②交叉 :根据上面给出的 Pr ( hi) ,从 P 中按概率选择 r ·
p/ 2 对假设 。对于每对假设 < h1 , h2 > , 应用交叉算 子产生两个后代 ,把所有的后代加入 Ps
③变异 :使用均匀的概率从 Ps 中选择 m % 的成员 。对于 选出的每个成员 ,在它的表示中随机选择一位取反
从 P 中选择假设 hi 的概率为 Pr ( hs) =
Fit ness ( hi)
S
∑Fitness ( hj)
j =1
© 1995-2005 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved.
第 1 期 任江洪等 :遗传算法在数据挖掘多种分类器合并中的应用
摘 要 :数据挖掘在电子商务中发挥着越来越重要的作用 。分类是数据挖掘中一项非常重要的任务 。由于单独的分类器 都具有一定的适用范围 ,所以将多个分类器的分类结果进行合并形成更高精度的分类结果是很有意义的一种方法 。文中 提出了一种基于遗传算法将多种分类器进行合并 ,以提高分类精度 ,扩大数据挖掘程序应用范围的方法 。 关键词 :数据挖掘 ;遗传算法 ;分类 ;合并 中图分类号 : TP301 . 6 文献标识码 :A 文章编号 :1005 - 3751 (2004) 01 - 0015 - 03
分类是数据挖掘中的一个非常重要的应用方面 。有 许多不同的分类算法 ,例如决策树分类 、贝耶斯分类器 、神 经网络以及粗糙集等等 。虽然某些算法会在某些特定的 应用中优于其他的算法 ,但不存在某一种分类算法在所有 的分类任务中都一定优于其他的算法 。某些问题由于其 特征可能特别适于某种算法 ,但人们很难事前就发现这种 算法 。所以采用多种分类器 ,利用多种分类器的分类结果 之间具有的互补性 ,通过合并算法整合多个分类结果产生 精确度更高的结果是一种非常可行的方法 。
Abstract :Data mining has more and more importance in E - Commence. Because of t he limited applicable field of a single special classifier , combining t he classifying output of multi - classifier to get more accuracy is very valuable. Classification is a very important task of data mining . The paper proposes an approach combining several different classifiers toget her based on genetic algorit hm to improve t he classify2 ing accuracy and extend t he applicable area of data mining. Key words :data mining ;genetic algorit hm ;classify ; combining
w ik mik , w ik 是权值矩阵 Wq 中
k =1
的成员 。η是常数 ,控制 H ( Wq) 对整个学习过程的影响 。j
· 1 6 · 微 机 发 展 第 14 卷
度量值形式是文中将要考虑的形式 ,它的值是输入数据属 于某一类的可能性度量结果 。神经网络分类器的输出就 是这样的形式 。
1 遗传算法在分类方法合并中的应用
笔者提出了一种基于遗传算法的多分类器合并方法 ,
机选择的权值开始 ,通过优化这些权值不断反应出各分类
器的相对重要性 。
图 3 基于遗传算法的多分类器结合的结构图 1. 1 基于遗传算法的学习
遗传算法是受生物进化过程启发的一种随机搜索的 优化算法 。它不再是从一般到特殊或者简单到复杂地搜
索假设 ,而是通过变异或重组当前已知的最好假设来生成 后续的假设 。每一步 ,更新当前称为群体 ( Population) 的 一组假设 ,方法是通过使用目前适应度高的假设作为候 选 ,通过某些运算形成新的个体组成新一代群体 。遗传算 法常用于系统参数的优化 ,例如模糊成员函数的优化都非 常适于使用遗传算法求解 。遗传算法的优点在于它在问 题的求解过程中对求解值能够随机地引入一些很大的变 化 ,避免陷入局部极小 ,这种特性特别适于求解一些用逐 步下降法难以解决的处于离散空间中的问题 。
表 1 遗传算法原型
GA ( Fitness ,Fitness - t hreshold , p , r , m)
Fitness :适应度函数 ,为给定假设赋予一个评估分数
Fitness - t hreshold :指定终止判据的阈值
p :群体中包含的假设数量
r :每一步通过交叉取代群体成员的比例
图 4 串的示意图 Wi ( i = 1 ,2 , …, K) 分别为 K 个分类器的权值矢量 , w ik 是 Wk 的第 i 个权值 ,代表第 k 个分类器相对于第 i 类 的相对重要性 ,取值范围为(0 ,1) 。 对遗传算法而言 ,一个群体需要被初始化并且随着进 化进程不断被更新 。在此应用中初始群体通过随机产生 每个个体中的权值而形成 。一旦初始群体形成 ,遗传算法 不断地更新群体 。在这个算法的每一次迭代中 ,使用概率 的方法在当前一代中选择某个个体作为候选 。在当前这 一代的成员已被选入下一代群体后 ,使用交叉与变异操作 生成下一代的其他的成员 。遗传算法的原型描述如表 1 所示[2 ] 。
第
14 卷 第 1 2004 年 1 月
期
Micro微com p机ute r 发Dev e展lopment
VoJla. n1.4
No . 2004
1
遗传算法在数据挖掘多种分类器合并中的应用
任江洪 ,曹长修
(重庆大学 自动化学院 ,重庆 400044)
m :变异率
◆ 初始化群体 : P ←随机产生的 p 个假设
◆ 评估 :对于 P 中的每个 h ,计算 Fitness( h)
◆ 当 maxFitness ( h) < Fitness - t hreshold , 做 :
产生新一代 Ps :
①选择 :用概率方法选择 P 的(1 - r) p 个成员加入 Ps ,
E( X) =
i <Λ
排除 其它情况
α是给定的阈值 。
如图 3 所示 ,这种带权值的多分类器合并实际是一个
单层网络 。从各分类器得到的度量值被传递给输入层 , o1 , o2 , …, oN 是输出层的输出值 。输出层的节点数等于所有
的分类数 。利用遗传算法不断优化网络的连接权值 ,从随
0 引 言 数据挖掘 (Data Mining ,DM) 通过数据的分析 ,对客户
行为进行预测的能力 ,已使其成为电子商务不可或缺的一 个基点[1 ] ,同时也成为人工智能和机器学习的一个极其重 要和活跃的应用领域 。数据挖掘的任务就是从大量的原 始数据中挖掘出隐含的 、有用的 、尚未发现的信息和知识 (如概念 、关联规则 、分类信息 、聚类信息等) ,为决策者提 供决策支持 。
合并算法分为两大类 :串行合并和并行合并 。串行合 并按一定顺序将分类器排成一列 ,前一个分类器的分类结
收稿日期 :2003 - 06 - 09 作者简介 :任江洪 (1976 —) ,男 ,重庆人 ,硕士研究生 ,研究方向为数 据挖掘 、机器学习 。
果作为输入被送入下一个分类器 ;并行合并将分类器并行 排列 ,输入 (训练值或者待分类数据) 被同时送入各个分类 器 ,各个分类器的分类结果再通过合并算法合并 。在串行 合并中 ,分类器的排列顺序相对于单个分类器的性能对系 统总的性能更加重要 ;而并行合并中 ,系统的性能主要依 赖于合并算法的效果 。文中提出的算法属于并行合并 。 串行合并与并行合尝的结构示意图分别如图 1 、图 2 所 示。
能够把多个分类器输出的分类结果进行合并 ,产生精确度
更高的单一结果 。
对于模式分类问题 ,任一模式 x 属于事先给定的 N 类 可能的分类 C1 , C2 , …, CN 中的一类 。用Λ = { 1 ,2 , …, N } 表示类标签的集合 。假设拥有 K 个分类器 , 每个分类器使