基于遗传算法的准确分类规则知识发现

２００７全国通信新理论与新技术学术大会——信息处理与其它　基于遗传算法的准确分类规则知识发现　李佑文夏士雄周勇　（中国矿业火学计算机科学与技术学院江苏徐州２２１００８）　摘要：针对传统算法处理数据分类问题计算量大，易陷入局部最优解的缺陷，本文结合遗传算法　的全局搜索特性，给出了基于遗传算法的准确分类规则知识发现方法。首先分析了用遗传算法进　行分类规则挖掘的关键技术，给出个体编码、适应度函数的设计、遗传操作算子的设计；然后从　理论上详细阐述了遗传算法的准确分类规则挖掘的方法；最后开发了基于ＪＢｕｉ１ｄｅｒ２００６平台的仿　真程序，从标准数据库中发现了准确的分类规则，实验结果验证了算法的有效性　关键词：数据挖掘；遗传算法；分类规则；　中图分类号：ＴＰ２７４　文献标识码：Ａ　Ｋｎｏｗｌｅｄｇｅ　Ｄｉｓｃｏｖｅｒｙ　ｏｆ　Ａｃｃｕｒａｔｅ　Ｃｌａｓｓｉｉｃａｔｉｆｏｎ　Ｒｕｌｅｓ　Ｂａｓｅｄ　ｏｎ　Ｇｅｎｅｔｉｃ　Ａｌｇｏｒｉｔｈｍ　ＬＩ　Ｙｏｕ－Ｗｅｎ　ＺＨＯＵ　Ｙｏｎｇ　ＸＩＡ　Ｓｈｉ－Ｘｉｏｎｇ　（Ｓｃｈｏｏｌ　ｏｆＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅ　ａｎｄＴｅｃｈｎｏｌｏｇｙ，ＣｈｉｎａＵｎｉｖｅｒｓｉｔｙｏｆＭｉｎｉｎｇ　ａｎｄＴｅｃｈｎｏｌｏｇｙ，Ｘｕｚｈｏｕ，Ｊｉａｎｇｓｕ　２２１００８，Ｐ．Ｒ．Ｃｈｉｎａ．　ＬＩ　Ｙｏｕ—Ｗｅｎ：ｌｅｉｙｕｚｉｑｑ＠Ｉ　６３．ｃｏｍ；ＺＨＯＵ　Ｙｏｎｇ：ｙｚｈｏｕ＠ｃｕｍｔ．ｅｄｕ．ｃｎ）　Ａｂｓｔｒａｃｔ：Ｉｎ　ｏｒｄｅｒ　ｔｏ　ｓｏｌｖｅ　ｔｈｅ　ｄｅｆｅｃｔｓ　ｏｆ　ｔｒａｄｉｆｉｏｎａｌ　ｄａｔａ　ｃｌａｓｓｉｆｉｃａｔｉｏｎ　ａｌｇｏｒｉｔｈｍｓ．ｓｕｃｈ　ａｓ　ｃｏｍｐｌｅｘ　ｃｏｍｐｕｔａｔｉｏｎ　ａｎｄ　ｅａｓｙ　ｔｏ　ｆａｌｌ　ｉｎｔｏ　ａ　ｌｏｃａｌ　ｏｐｔｉｍａｌ　ｓｏｌｕｔｉｏｎ，ｔｈｉｓ　ｐａｐｅｒ　ｐｕｒｐｏｓｅｄ　ａ　ｍｅｔｈｏｄ　ｔｏ　ｄｉｓｃｏｖｅｒ　ｔｈｅ　ｋｎｏｗｌｅｄｇｅ　ｏｆ　ａｃｃｕｒａｔｅ　ｃｌａｓｓｉｆｉｃａｔｉｏｎ　ｒｕｌｅｓ　ｂａｓｅｄ　ｏｎ　ｔｈｅ　ｇｌｏｂａｌ　ｓｅａｒｃｈ　ｐｒｏｐｅｒｔｙ　ｏｆ　Ｇｅｎｅｔｉｃ　Ａｌｇｏｒｉｔｈｍ．　Ｆｉｒｓｔｌｙ，ｗｅ　ａｎａｌｙｚｅｓ　ｔｈｅ　ｋｅｙ　ｔｅｃｈｎｏｌｏｇｉｅｓ　ｆｏｒ　ｔｈｅ　ｉｍｐｌｅｍｅｎｔａｔｉｏｎ　ｏｆ　ｃｌａｓｓｉｆｉｃａｔｉｏｎ　ｒｕｌｅｓ　ｂａｓｅｄ　ｏｎ　ＧＡ，　ｉｎｃｌｕｄｉｎｇ　ｉｎｄｉｖｉｄｕａｌ　ｅｎｃｏｄｉｎｇ，ｆｉｔｎｅｓｓ　ｆｕｎｃｔｉｏｎ　ｄｅｓｉｇｎ　ａｎｄ　ＧＡ’ｓ　ｏｐｅｒａｔｏｒｓ　ｄｅｓｉｇｎ，ｅｔｃ．Ｔｈｅｎ，ｗｅ　ｇｉｖｅ　ａ　ｐａｒｔｉｃｕｌａｒ　ｍｅｔｈｏｄ　ｉｎ　ｔｈｅｏｒｙ　ｏｆ　ｈｏｗ　ｔｏ　ｍｉｎｉｎｇ　ａｃｃｕｒａｔｅ　ｃｌａｓｓｉｉｆｃａｔｉｏｎ　ｕｌｒｅｓ　ｕｓｉｎｇ　Ｇｅｎｅｔｉｃ　Ａｌｇｏｒｉｔｈｍ．Ａｔ　ｌａｓｔ　ｔｈｅ　ｅｘｐｅｒｉｍｅｎｔ　ｗｅｒｅ　ｇｉｖｅｎ　ｂｙ　ｔｈｅ　ｓｉｍｕｌａｔｅ　ｐｒｏｃｅｓｓｅｓ　ｏｎ　ＪＢｕｉｌｄｅｒ２００６　ｃｏｕｌｄ　ｄｉｓｃｏｖｅｒ　ｔｈｅ　ａｃｃｕｒａｔｅ　ｃｌａｓｓｉｉｆｃａｔｉｏｎ　ｕｌｒｅｓ　ｆｒｏｍ　ｈｅ　ｔｓｔａｎｄａｒｄ　ｄａｔａｂａｓｅ．ａｎｄ　ｉｔ　ｉｌｌｕｓｔｒａｔｅｄ　ｔｈｅ　ｅｆｆｅｃｔｉｖｅｎｅｓｓ　ｏｆ　ｈｉｔｓ　ａｌｇｏｒｉｔｈｍ．　Ｋｅｙ　ｗｏｒｄｓ：ｄａｔａ　ｍｉｎｉｎｇ；ｇｅｎｅｔｉｃ　ａｌｇｏｒｉｔｈｍ；ｃｌａｓｓｉｆｉｃａｔｉｏｎ　ｕｌｒｅｓ；　１引言　２０世纪７０年代以来，数据库技术得到了迅速发展及广泛应用。数据反映了客观事物发展变化的历史　过程，是一笔宝贵的财富，但是寻找隐藏在其中的有用信息无异于大海捞针。由于缺乏挖掘大量数据背后　隐藏知识的有效手段，导致了“数据丰富但知识贫乏”（ｄａｔａ　ｒｉｃｈ　ｂｕｔ　ｋｎｏｗｌｅｄｇｅ　ｐｏｏｒ）。随着计算机技术的　飞速发展和企业界不断提出的新需求，数据挖掘（ｄａｔａ　ｍｉｍｉｎｇ）技术应运而生。数据挖掘是指从大型数据　库的数据中提取人们感兴趣的知识，这些知识是隐含的、事先未知的潜在的有用信息【ｌ　Ｊ。数据分类是数据　挖掘的一个重要方面，目前常用的分类规则挖掘方法有遗传算法、决策树方法、神经网络、粗糙集方法等。　分类的主要目的是分析输入的数据，通过在训练样本数据集中的数据表现出来的特性，为每一类找到一种　准确的分类函数或构造出一个分类模型（即我们通常所说的分类器Ｃｌａｓｓｉｉｆｅｒ，一般用规则或决策树模式表　示），并用该模型对未来的数据进行分类，尽管这些未来的数据类别是未知的，我们仍然可以由此预测出这　维普资讯 http://www.cqvip.com

２００７全国通信新理论与新技术学术大会——信息处理与其它　些新数据所属的类，即我们获得了这个类的知识发现。　２数据分类的步骤和分类规则　２．１数据分类的步骤　一般来说数据分类都可以分成两步　Ｊ：　（１）建立一个描述已知数据集类别或概念的模型。是指在￣ＨｉＪ　ａｌ练样本类别情况下，通过学习建立　相应模型，通常分类学习所获得的模型可以表示为分类规则形式、决策树形式或数学公式形式。　（２）利用所获得的模型进行分类操作。分类操作前要对模型分类准确率进行评估，例如使用保持　（ｈｏｌｄｏｕｔ）方法【引。保持方法是一种简单的估计分类规则准确率的方法，即把给定数据随机地划分成两个独立　的集合：训练集（２／３）和测试集（１／３）。使用训练集导出分类规则，然后在测试集上计算其正确率，本文采用　的评估方法是对第一步得到的分类规则分别计算其在训练集和测试集中的适应度值，若分类规则在训Ｉ练集　和测试集中的适应度值越接近，则说明分类的精度越高。　２．２分类规则　数据分类的核心是设计分类器。要构造分类器，需要有一个训练集作为输入，训练集是构造分类器的　基础。本文的分类器采用的是分类规则的形式。最一般的分类规则如下所示：　（Ｖｌ＝Ｉ１）八（Ｖ２　Ｉ２）八…Ａ（ｖ　一　）ｔｈｅｎ　ｃ　Ｊ　其中，ｉｆ部分是规则的前提，ｔｈｅｎ部分是规则的结论。Ｉｉ（ｆ＝１，２…　）表示对应属性值的集合，＝表示　ｉｎ，Ｊ表示类别。本文采用的是ＰｌａｙＴｅｎｎｉｓ训练集，含４个特征属性和１个类别属性。对于该数据集，分类　的目的是为了了解在什么样的天气适宜去ＰｌａｙＴｅｎｎｉｓ，所以最后得到的规则形式应该是这样的：“ｉｆ（Ｏｕｔｌｏｏｋ　＝Ｏｖｅｒｃａｓｔ）ａｎｄ（Ｔｅｍｐｅｒａｔｕｒｅ＝Ｈｏｔ）ａｎｄ（Ｈｕｍｉｄｉｔｙ＝Ｈｉｇｈ）ａｎｄ（Ｗｉｎｄ＝Ｗｅａｋ）ｔｈｅｎ　ＰｌａｙＴｅｎｎｉｓ＝Ｙｅｓ”，　一旦建立规则之后，就可以用来预测未来在什么样的天气适宜ＰｌａｙＴｅｎｎｉｓ了。　３基于遗传算法的准确分类规则知识发现　３．１分类规则的编码　使用遗传算法进行分类规则挖掘时，首先要构造规则的编码形式。本文采用Ｍｉｃｈｉｇａｎ编码方式，即每　条染色体代表一条规则，并且不对规则的结论部分进行编码，即参与进化的初始群体由同类个体组成，算　法运行一次得到一类个体对应的分类规则。即若数据库中的数据有ｎ类，则需要将遗传算法运行Ｉｉ次，当　然，可以在多处理器，或ＰＶＭ并行机群上同时分任务进行，则编码方式如下表１所示：　表１规则的编码结构　ＧＥＮＥＩ（Ａ１）　Ｗｅｉｇｈｔ　Ｏｐｅｒａｔｏｒ　、，ａｌｕｅ　ＧＥＮＥ（Ａｎ）　Ｗｅｉｇｈｔ　Ｏｐｅｒａｔｏｒ　、，ａｌｕｅ　其中，Ｖａｌｕｅ是值域，它在该属性的所有可能取值中取值。另外，为了加大规则的准确度，本文采用　的是可变长度的染色体，即在每个属性的所有可能取值中加入了一个新值“Ａｎｙ”。Ｖａｌｕｅ＝“Ａｎｙ”表示该基　因上取什么值并不重要，其属性在这条规则中可以去掉，此时规则长度变短；Ｗｅｉｇｈｔ为权值域，其值是在　特征属性上取当前值（Ｖａｌｕｅ）个体数占所有个体数的百分比。设置Ｗｅｉｇｈｔ目的是为了忽略那些只出现了很　少次数的属性值，这个闽值一般设置为０．０５—０．２；Ｏｐｅｒａｔｏｒ是与特征属性相联系的操作运算符，对离散属性　而言，取“一’或“≠”符号，对连续属性而言，取“　”或“）”符号。　１６１　维普资讯 http://www.cqvip.com ２００７全国通信新理论与新技术学术大会——信息处理与其它　３．２适应度函数设计　对于前提为Ａ，结论为Ｃ的分类规则，数据中存在４类不同的个体，如表２所列：　表２数据库中的规则以及与之匹配的记录数量　规则形式　ｌｆＡｔｈｅｎ　Ｃ　ｌｆＡｔｈｅｎ　ｎｏｔＣ　匹配的记录个数　ｐｐ　ｐｎ　ＩｆｎｏｔＡｔｈｅｎ　Ｃ　ＩｆｎｏｔＡｔｈｅｎ　ｎｏｔＣ　ｎｐ　ｎｎ　为了计算规则的准确性，有如下的几个定义【４】　ｎｎ　定义３．１　规则的覆盖度ｃｏｍｐ＝—　ｐｐ七ｎｐ　从覆盖度的定义可以看出它表示的是在所有的同类个体中这条规则的普遍性意义。规则的覆盖度越　大，表明在同类个体空间中符合规则前提的个体数目越多。　ｎｎ　定义３．２规则的置信度ｃｆ：—　一　ＰＰ＋Ｐ　从置信度的定义可以看出它表示的是在所有符合规则前件的记录中它能正确判断记录所属类别的正　确率。规则的置信度越大，规则的可信度越强，因为它能更正确地判断个体。从某种意义上来说更加关心　的是规则的置信度，但与此同时又不能忽略规则的普遍意义，所以把规则的准确性定义为：　定义３．３规则的准确性ａｃｃｕｒａｃｙ＝ｃｏｍｐ丰ｃｆ　为了得到高准确性的规则，定义规则的适应度函数等于规则的准确性，即：　定义３．４规则的适应度ｆｉｔｎｅｓｓ＝ａｃｃｕｒａｃｙ　３．３遗传操作［５］　遗传操作包括三个基本遗传算子：选择、交叉和变异。这三个遗传算子的操作都是按一定的概率进行　的，遗传操作使群体中个体高效地、有方向性地向最优解迁移，本节将讨论遗传算子的设计。　１）选择算子的设计：选择操作是建立在群体中每个个体适应度评估基础之上的选择优胜个体、淘汰　劣个体的操作，模拟的是自然界中的“物竞天择，适者生存”。本文采用轮盘赌选择策略和精英保存策略　相结合的方式；交叉算子的设计：２）交叉算子模拟的是自然界中的繁殖现象，交叉算子能够产生很多的新　个体，交叉时使用到交叉概率Ｐｃ。若Ｐｃ过小，则交叉很难发生，容易使遗传算法陷迟钝搜索；若太大，　则会使已经找到的较好模式遭到破坏，所以Ｐｃ一般在０．２５—０．８之间，本文采用的是一种单点交叉的方法；　变异算子的设计：３）变异算子模拟的是自然界中的个体基因突变现象，在遗传算法中就是对个体编码随机　挑选一个或多个基因对其基因值作变动。变异概率Ｐｍ的设定主要是为了辅助搜索操作，维持群体多样性。　变异概率一般取在０．００１—０．２左右。　３．４算法的步骤　采用遗传算法挖掘准确分类规则的步骤如下：　Ｓｔｅｐ　１确定分类所需特征属性和类别属性，并使用保持方法，随机生成２／３的数据库中的记录作为初　始训练集，另外ｌ／３作为测试集。　Ｓｔｅｐ　２预处理数据并产生初始群体Ｐ（ｔ），设置进化代数计数器ｔ＝０，和最大进化代数为ＭＡＸＧＥＮ。　Ｓｔｅｐ　３选择操作。先依据定义３．４计算群体Ｐ（ｔ）ｄＰ所有个体的适应度值，再利用轮盘赌选择策略和精　６２　维普资讯 http://www.cqvip.com ２００７全国通信新理论与新技术学术大会——信息处理与其它　英保存策略相结合的方式进行选择操作。　Ｓｔｅｐ　４交叉操作。把Ｐ（ｔ）中的个体随机配对，再进行单点交叉运算。　Ｓｔｅｐ　５变异操作。对Ｐ（ｔ）中的个体进行变异运算，变异完成后更新进化代数计数器ｔ＝ｔ＋ｌ；　Ｓｔｅｐ　６终止条件判断。若ｔ＜ＭＡＸＧＥＮ，转到Ｓｔｅｐ　３，若ｔ＝ＭＡＸＧＥＮ，则终止并输出最佳规则。　４实验及分析　４。１算法的实验数据及参数设置　本文选择的是Ｐｌａｙ　Ｔｅｎｎｉｓ数据集ｆ６Ｊ，数据如下表２：　表２　ＰｌａｙＴｅｎｎｉｓ数据集　ＤＩ　Ｄ２　Ｄ３　Ｄ４　Ｄ５　Ｄ６　Ｄ７　Ｒａｉｎ　Ｓｕｎｎｙ　Ｏｖｅｒｃａｓｌ　Ｒａｉｎ　Ｒａｉｎ　Ｒａｉｎ　Ｏｖｅｒｃ￣ｌ　Ｃ０ｏＩ　ＨＯｌ　ＨＯｌ　Ｍｉｌｄ　ＣＯＯＩ　ＣＯＯＩ　ＣＯＯＩ　Ｈｉ曲　Ｈｉ曲　Ｈｉ曲　Ｈｉ曲　Ｎｏｒｎ＇ｌａＩ　ＮｏｒｌｎａＩ　Ｎｏｒｎ＇ｌａＩ　Ｗｍｋ　Ｓｔｒｏｎｇ　Ｗｅａｌｃ　Ｗ　ａｋ　ｋ　Ｓｔｒｏｎｇ　Ｓｔｒｏｎｇ　Ｙｅｓ　ＮＯ　Ｙｅｓ　Ｙｅｓ　Ｙ　ｓ　ＮＯ　Ｙ　ｓ　Ｄ８　Ｄ９　Ｄ１０　ＤＩＩ　Ｓｕｎｎｖ　Ｓｕｎｎｙ　Ｒａｉｎ　Ｓｕｎｎｖ　Ｍｉｌｄ　ＣｏｏＩ　Ｍｉｌｄ　Ｍｌｉｄ　Ｈｉ曲　ＮｏｒｌｎａＩ　Ｎｏｒｎ＇ｌａＩ　Ｎｏｒｎ＇ｌａＩ　Ｗ　ａｌｃ　Ｗ如ｋ　Ｗ　ａｋ　Ｓｔｒｏｎｇ　ＮＯ　Ｙｅｓ　Ｙ　ｓ　Ｙｅｓ　Ｄｌ２　ＤＩ３　ＤＩ４　ＤＩ５　Ｏｖｅｒｃａｓｌ　ＯｖｅｒｃａｓＩ　Ｓｕｎｎｙ　Ｒａｉｎ　Ｍｉｌｄ　ＨＯｌ　Ｍｉｌｄ　Ｍｉｌｄ　Ｈｉ曲　Ｎｏｒｎ＇ｌａＩ　Ｎｏｒｎ＇ｌａＩ　Ｎｏｒｎ＇ｌａＩ　Ｓｔｒｏｎｇ　Ｗｅａｌｃ　Ｗ　ａｋ　Ｓｔｒｏｎｇ　Ｙ　ｓ　Ｙ　ｓ　Ｙｅｓ　ＮＯ　ＤＩ６　ＤＩ７　Ｄｌ８　Ｄ１９　Ｏｖｅｒｃ￣ｌ　Ｓｕｎｎｖ　Ｏｖｃｒｃａｓｌ　Ｓｕｎｎｖ　ＨＯｌ　Ｃ０ｏＩ　Ｃ０ｏＩ　Ｈｏｌ　Ｈｉ曲　Ｈｉ曲　Ｎｏｒｎ＇ｌａＩ　Ｎｏｒｎ＇ｌａｉ　Ｓｔｒｏｎｇ　Ｗ　ａｋ　ｋ　Ｓｔｒｏｎｇ　Ｙ色ｓ　ＮＯ　Ｙｅｓ　Ｙｅｓ　Ｄ２０　Ｄ２Ｉ　Ｒ且ｉｎ　Ｏｖｅｒｃ￣ｌ　ＨＯｌ　Ｍｉｌｄ　Ｈｉ曲　Ｎｏｒｎ＇ｌａＩ　Ｓｔｒｏｎｇ　Ｗ　ａｋ　ＮＯ　Ｙｅｓ　Ｄ２２　Ｄ２３　Ｄ２４　Ｄ２５　Ｒａｉｎ　Ｓｕｎｎｙ　Ｒａｉｎ　Ｓｕｎｎｙ　ＨＯｌ　Ｃ０ｏＩ　ＣＯＯＩ　ＨＯｌ　Ｈｉ曲　Ｈｉ曲　Ｈｊ曲　Ｈｉｇｈ　Ｗ　ａｋ　Ｓｔｒｏｎｇ　Ｓｔｒｏｎｇ　Ｗ　ａｋ　Ｙ色ｓ　ＮＯ　Ｎ０　ＮＯ　Ｄ２６　Ｏｖｅｒｃａｓｌ　Ｍｉｌｄ　Ｎｏｒｎ＇ｌａＩ　Ｓｔｒｏｎｇ　Ｙ　ｓ　Ｄ２７　Ｏｖｅｒｃａｓｌ　ＣＯＯＩ　Ｈｉ曲　Ｓｔｒｏｎｇ　Ｙ　ｓ　Ｄ２８　Ｄ２９　Ｒａｉｎ　Ｓｕｎｎｙ　Ｍｉｌｄ　ＣＯＯＩ　Ｈｉ曲　Ｎｏｒｎ＇ｌａＩ　Ｓｔｒｏｎｇ　Ｓｔｒｏｎｇ　ＮＯ　Ｙ　ｓ　Ｄ３Ｏ　Ｏｖｅｒｃ￣ｔ　Ｈ０ｌ　Ｈｉ曲　Ｗ　ａｋ　Ｙ　ｓ　Ｄ３Ｉ　Ｄ３２　Ｓｕｎｎｖ　Ｒａｉｎ　ＨＯｌ　ＨＯＩ　Ｈｊ曲　Ｎｏｒｎ＇ｌａＩ　Ｓｔｒｏｎｇ　Ｓｔｒｏｎｇ　ＮＯ　ＮＯ　Ｄ３３　Ｏｖｅｒｃ￣ｔ　ＭｉＩｄ　Ｈｉ曲　Ｓｔｒｏｎｇ　Ｙ　ｓ　该表有３３个数据，被分成了两类，每个数据记录包含有４个特征属性和１个类别属性。　１６３　维普资讯 http://www.cqvip.com ２００７全国通信新理论与新技术学术大会——信息处理与其它　按照３．３中的分析，在实验中遗传算法参数配置如下：种群大小＝ｌｌ、染色体长度＝４、最大进化代　数＝５０、交义概率ＰＣ＝Ｏ．８，变异概率ＰＭ＝０．０５，权值域阂值＝Ｏ．１。　４．２实验结果及分析　在本文进行实验时，对每一类遗传算法都分别运行了五次，并把五次运行的最优结果定为预测此类的　最好分类规则，最后得到的最优规则如表３所示，表中也分别给出了规则的适应度和正确率。　表３最优规则及其适应度、正确度　训练集／￣，ｌＪ试集　训练集／测试　类别　最优规则　上的适应度　Ｙｅｓ　Ｎｏ　ｉｆｏｕｔ１ｏｏｋ＝Ｏｖｅｒｃａｓｔ　ａｎｄＴｅｍｐｅｒａｔｕｒｅ＝Ａｎｙ　ａｎｄＨｕｍｉｄｉｔｙ＝Ａｎｙ　ａｎｄＷｉｎｄ＝Ａｎｙ称为：规则１）　ｉｆＯｕｔｌｏｏｋ＝Ｒａｉｎ　ａｎｄＴｅｍｐｅｒａｔｕｒｅ＝Ａｎｙ　ａｎｄ　Ｈｕｍｉｄｉｗ＝Ａｎｙ　ａｎｄ　Ｗｉｎｄ＝Ｓｔｒｏｎｇ（称为：规则２）　０．５４／０　５　Ｏ．５，０．５　集上的正确率　１　０１１．０　１．０／１．０　Ｎｏ　ｉｆＯｕｔｌｏｏｋ＝ＳｕｎｎｙａｎｄＴｅｍｐｅｒａｔｕｒｅ＝Ａｎｙ　ａｎｄＨｕｍｉｄｉｔｙ＝Ｈｉ曲ａｎｄ　ｗｉｎｄ＝Ａｎｙ（称为：规则３）　Ｏ．５，０．５　１．Ｏ／１．Ｏ　从上表中可以看出，规则在训练集和测试集上的适应度非常接近，说明这些规则在训练集和测试集上　都有较好的置信度和覆盖度。更值得欣喜的是，挖掘出的规则在训练集和测试集上的正确率都是１．０，即这　些规则可以在这个数据集上能够将具有这些规则形式的所有记录都识别正确。手动将这些规则与表２中的　数据记录相比较匹配，可以验证这些规则确实都具有很高的准确性：　表２中与规则ｌ前提部分相匹配的数据有：Ｄ３、Ｄ７、Ｄ１２、Ｄ１３、Ｄ１６、Ｄ１８、Ｄ２１、Ｄ２６、Ｄ２７、Ｄ３０　和Ｄ３３，这ｌ　ｌ条记录的类别属性都是“Ｙｅｓ”；表２中与规则２前提部分相匹配的数据有：Ｄ６、Ｄ１５、Ｄ２０、　Ｄ２４、Ｄ２８和Ｄ３２，这６条记录的类别属性都是“Ｎｏ”；表２中与规则３前提部分相匹配的数据有：Ｄ２、　Ｄ８、Ｄ１７、Ｄ２３、Ｄ２５和Ｄ３１，这６条记录的类别属性都是“Ｎｏ”。可以看出，这些数据的结论部分也与规　则的结论部分相比配，说明这些规则具有极高的准确性（正确率为１００％），可以使用它们来预测将来的记　录类别。　下面仅给出在得到规则１时ＪＢｕｉｌｄｅｒ的输出界面及其代数与平均适应度的关系：　图２代数与平均适应度的关系　幽１规则１的运行界血　从图２中可以很明显的看出，在得到这条规则的时候，随着遗传算法代数的增加，群体的平均适应度　在开始是逐渐增加的，并且在最后趋于收敛，这也证明了本文提出的算法的可行性与有效性。　５结束语　本文针对利用遗传算法进行数据挖掘研究领域，提出了一种基于遗传算法的数据分类方法，用遗传算　法挖掘出了准确的分类规则，仿真结果表明本文算法挖掘出来的分类规则都具有１００％的正确率。另外，　由于本文所使用的数据量小，所以遗传算法的收敛时间较短，但是针对大型数据库而言，遗传算法的每一　次训练达到收敛往往需要几百次，甚至几千次迭代，算法的效率较慢，严重影响了训练时间，如何通过多　维普资讯 http://www.cqvip.com

２００７全国通信新理论与新技术学术大会——信息处理与其它　处理器的并行计算减少分类时问，是下一步　Ｉ　作需要研究的问题。　参考文献　【ｌ】夏火松．数据仓库与数据挖掘技术【Ｍ】　第二版　北京：科学出版社，２００４　【２】张磊．基于混合遗传算法的分类规则挖掘方法及其并行实现【Ｄ】．重庆：重庆大学，２００４　【３］Ｈａｎ　Ｊｉａｗｅｉ，Ｍｉｃｈｅｌｉｎｅ　Ｋａｍｂｅｒ著．范明，盂小峰等译．数据挖掘概念与技术【Ｍ】．］ｔ京：机械工业出版社，２００１　【４】Ａ．Ａ　Ｆｒｅｉｔａｓ．Ａ　ｓｕｒｖｅｙ　ｏｆ　ｅｖｏｌｕｔｉｏｎａｒｙ　ａｌｇｏｒｉｔｈｍｓ　ｆｏｒ　ｄａｔａ　ｍｉｎｉｎｇ　ａｎｄ　ｋｎｏｗｌｅｄｇｅ　ｄｉｓｃｏｖｅｒｙ［Ａ］．Ａｄｖａｎｃｅｓ　ｉｎ　ｅｖｏｌｕｔｉｏｎａｒｙ　ｃｏｍｐｕｔｉｏｎ［Ｃ］．Ｂｅｒｌｉｎ：Ｓｐｒｉｎｇｅｒ－Ｖｅｒｌａｇ．２００２．８　ｌ　９—８４５　【５】Ｗｒｉｔｔｅｎ　Ｂｙ　Ｘｕａｎ　ＧｕａｎｇＮａｎ【Ｊａｐａｎ】ａｎｄ　Ｃｈｅｎｇ　ＲｕｎＷｅｉ．Ｔｒａｎｓｌａｔｅｄ　Ｂｙ　Ｙｕ　ＹｉｎＪｉｅ　ａｎｄ　Ｚｈｏｕ　ＧｅｎＧｕｉ．Ｇｅｎｅｔｉｃ　Ａｌｇｏｒｉｔｈｍ　ａｎｄ　Ｅｎｇｉｎｅｅｒｉｎｇ　Ｏｐｔｉｍｉｚａｔｉｏｎ［Ｍ］．ＢｅｉＪｉｎｇ：Ｔｓｉｎｇｈｕａ　Ｕｎｉｖｅｒｓｉｔｙ　Ｐｒｅｓｓ，２００４　【６】李雄飞，李军．数据挖掘与知识发现【Ｍ】．笫二版．北京：高等教育出版社．２００３　基金项目：国家自然科学基金项目（５０６７４０８６），高等学校博士学科点专项科研基金项目（２００６０２９０５０８），中国矿业大学青　年科研基金（２００６Ａ０４７）　作者简介：　李佑文（１９８５一），男，硕士研究生，主要研究领域为人工智能，计算机应用技术；夏士雄（１９６１一），男，博士，教授，　博士生导师，主要研究领域为模式识别，人工智能；￣Ｊ（１９７４－－），男，江苏徐，、Ｉ＇Ｉ．Ｌ，博士，讲师，主要研究领域为人　工智能，无线传感器网络。　ｌ６５