Ｃｏｍｐｕｔｅｒ Ｅｎｇｉｎｅｅｒｉｎｇ ａ” ，ｆｃ口ｆ Ｄｎ 计算机工程与应用 用于不均衡数据集分类的ＫＮＮ算法 孙晓燕，张化祥，计华 ＳＵＮ Ｘｉａｏｙａｎ，ＺＨＡＮＧ Ｈｕａｘｉａｎｇ，ＪＩ Ｈｕａ 山东师范大学信息科学与工程学院，济南２５００１４ Ｄｅｐａｒｔｍｅｎｔ ｏｆ Ｉｎｆｏｒｍａｔｉｏｎ Ｓｃｉｅｎｃｅ ａｎｄ Ｅｎｇｉｎｅｅｒｉｎｇ，Ｓｈａｎｄｏｎｇ Ｎｏｒｍａｌ Ｕｎｉｖｅｒｓｉｔｙ，Ｊｉｎａｎ ２５００１４，Ｃｈｉｎａ ＳＵＮ Ｘｉａｏｙａｎ，ＺＨＡＮＧ Ｈｕａｘｉａｎｇ，Ｊｌ Ｈｕａ．Ｉｍｐｒｏｖｅｄ ＫＮＮ ａｌｇｏｒｉｔｈｍ ｉｎ ｃｌａｓｓｉｉｃａｔｉｆｏｎ ｏｆ ｉｍｂａｌａｎｃｅｄ ｄａｔａ ｓｅｔｓ・Ｃｏｍｐｕｔｅｒ Ｅｎｇｉｎｅｅｒｉｎｇ ａｎｄ Ａｐｐｆｉｃａｔｉｏｎｓ，２０１１，４７（２８）：１４３—１４５． Ａｂｓｔｒａｃｔ：Ｗｈｅｎ ｔｈｅ ＫＮＮ ａｌｇｏｒｉｔｈｍ ｉｓ ｕｓｅｄ ｔｏ ｄｅａｌ ｗｉｔｈ ｉｍｂａｌａｎｃｅｄ ｄａｔａ ｓｅｔｓ，ｉｔ ｈａｓ ｐｏｏｒ ｐｅｒｆｏｒｍａｎｃｅ ｉｎ ｔｈｅ ｍｉｎｏｒｉｙ ｔｃｌａｓｓ ｐｒｅｄｉｃｔｉｏｎ ａｃｃｕｒａｃｙ．Ａｎ ｉｍｐｒｏｖｅｄ ａｌｇｏｒｉｔｈｍ（Ｇ—ＫＮＮ）ｉｓ ｐｒｏｐｏｓｅｄ ｔｏ ｓｏｌｖｅ ｔｈｉｓ ｐｒｏｂｌｅｍ．Ｆｏｒ ｔｈｅ ｍｉｎｏｒｉｔｙ ｃｌａｓｓ ｓａｍｐｌｅｓ， ｔｈｉｓ ａｌｇｏｒｉｔｈｍ ｕｓｅｓ ｔｈｅ ｃｒｏｓｓｏｖｅｒ ｏｐｅｒａｔｏｒ ａｎｄ ｍｕｔａｔｉｏｎ ｏｐｅｒａｔｏｒ ｔｏ ｇｅｎｅｒａｔｅ ｓｏｍｅ ｏｆ ｔｈｅ ｎｅｗ ｍｉｎｏｒｉｔｙ ｃｌａｓｓ ｓａｍｐｌｅｓ．Ｏｎｅ ｎｅｗ ｓａｍｐｌｅ ｉＳ ｃｏｎｓｉｄｅｒｅｄ ｖａｌｉｄ．ｏｎｌｙ ｉｆ ｉｔｓ Ｅｕｃｌｉｄｅａｎ ｄｉｓｔａｎｃｅ ｔｏ ｐａｒｅｎｔ ｉＳ ｌｅｓｓ ｔｈａｎ ｔｈｅ ｍａｘｉｍｕｍ ｄｉｓｔａｎｃｅ ｂｅｔｗｅｅｎ ｐａｒｅｎｔｓ． Ｔｈｅｎ ｔｈｉｓ ｖａｌｉｄ ｓａｍｐｌｅ ｉｓ ｕｓｅｄ ｔｏ ｐｒｏｄｕｃｔ ｔｈｅ ｍｉｎｏｒｉｔｙ ｃｌａｓｓ ｓａｍｐｌｅｓ ｉｎ ｔｈｅ ｎｅｘｔ ｒｏｕｎｄ ｏｆ ｔｈｅ ｐｒｏｃｅｓｓ．Ｔｈｅ ｅｘｐｅｒｉｍｅｎｔａｌ ｒｅ— ｓｕｌｔｓ，ｗｈｉｃｈ ａｒｅ ｔｅｓｔｅｄ ｏｎ ｔｈｅ ＵＣＩ ｄａｔａ ｓｅｔｓ，ｓｈｏｗ ｔｈａｔ ｔｈｉｓ ａｌｇｏｒｉｔｈｍ ｉｓ ｓｕｐｅｒｉｏｒ ｔｏ ＫＮＮ ａｌｇｏｒｉｔｈｍ ｉｎ ｔｈｅ ａｐｐｌｉｃａｔｉｏｎ ｏｆ ｒａｎ— ｄｏｍ ｏｖｅｒ－ｓａｍｐｌｉｎｇ ｉｎ ｉｍｐｒｏｖｉｎｇ ｔｈｅ ｃｌａｓｓｉｉｃａｔｉｆｏｎ ａｃｃｕｒａｃｙ ｏｆ ｔｈｅ ｍｉｎｏｒｉｙ ｃｌｔａｓｓ． Ｋｅｙ ｗｏｒｄｓ：ｉｍｂａｌａｎｃｅｄ ｄａｔａ ｓｅｔｓ；Ｋ－Ｎｅａｒｅｓｔ Ｎｅｉｇｈｂｏｒ（ＫＮＮ）ａｌｇｏｒｉｔｈｍ；ｏｖｅｒ－ｓａｍｐｌｉｎｇ；ｃｒｏｓｓｏｖｅｒ 摘要：针对ＫＮＮ在处理不均衡数据集时，少数类分类精度不高的问题，提出了一种改进的算法Ｇ—ＫＮＮ。该算法对少数类样本 使用交叉算子和变异算子生成部分新的少数类样本，若新生成的少数类样本到父代样本的欧几里德距离小于父代少数类之间的 最大距离，则认为是有效样本，并把这类样本加入到下轮产生少数类的过程中。在ＵＣＩ数据集上进行测试，实验结果表明，该方 法与ＫＮＮ算法中应用随机抽样相比，在提高少数类的分类精度方面取得了较好的效果。 关键词：不均衡数据集；Ｋ最近邻居（ＫＮＮ）算法；过抽样；交叉算子 ＤＯＩ：１０．３７７８／ｊ．ｉｓｓｎ．１００２—８３３１．２０１１．２８．０３９ 文章编号：１００２—８３３１（２０１１）２８—０１４３．０３ 文献标识码：Ａ 中图分类号￣ＴＰ３９１ 近年来，不均衡数据集分类问题在机器学习和数据挖掘 方面引起了越来越多的关注。不均衡数据集，是指在一个数 据集中，某一类的样本占多数，而另外一类的样本占少数，占 易导致过学习。 基于以上的分析，本文提出了一种使用遗传算法中交叉 算子与变异算子产生少数类样本生成方法，属于一种过抽样 多数的类称为多数类，而占少数的类称为少数类 。传统的分 类算法预测倾向于多数类，而在实际问题中，少数类的分类精 度更为重要。因此，如何提高少数类的分类精度，成为机器学 习领域一个亟待解决的问题。目前，针对不均衡数据集分类 问题，解决方法有：（１）数据层方法，如代价敏感学习、集成学 习、单分类器方法等 ；（２）数据层方法，包括简单过抽样、欠 算法。当实例的属性值为连续数值型时，若两个实例之间的 欧几里德距离较小，可认为两个实例在空间分布中相近，即实 例类标相同的可能性较大。这个认识同ＫＮＮ算法的隐含假 定相似。因此，本文在ＫＮＮ算法中使用遗传算法中的交叉算 子和变异算子产生少数类，并对这部分少数类进行验证。若 新产生样本到父代样本距离小于父代之间最大的距离，则认 为是有效的样本，并将这部分样本加入到下轮产生少数类样 抽样算法及在此基础上提出的改进方法等 。 以上提出的方法，在很大程度上解决了不均衡数据集分 类问题，但仍存在一定的不足之处，如代价敏感学习中代价项 的设置、集成学习中权重的设置等存在不稳定性，过抽样算法 容易产生过度拟合等。ＫＮＮ［７］作为一种简单的分类算法，它根 据待分类实例的邻近 个实例的类别，投票进行预测，而在不 均衡数据集中多数类比例较高，一个少数类的实例周围 个 近邻可能绝大部分为多数类，因此，它对少数类分类精度不 高。而简单的过抽样算法虽增加了少数类样本的数量，但容 本的过程中，直到产生满足要求的少数类个数，最后将新产生 的少数类样本和父代少数类加入到训练样本中，增加了训练 集中少数类的个数，有利于少数类的分类。因此该方法可以 提高ＫＮＮ分类算法在处理不均衡数据集中少数类的分类性能。 １不均衡数据集分类问题评价标准 在评价传统的分类方法时，一般采用分类精度（式（１））来 表示。但是对于不均衡数据集而言，传统的分类算法预测会 基金项日：山东省自然科学基金（Ｎｏ．ＺＲ２０１０ＦＭ０２１）；山东省科技研究计划项目（Ｎｏ．２００７ＺＺ１７，Ｎｏ．２００８ＧＧ１０００１０１５，Ｎｏ．２００８Ｂ００２６）；山东省教 育厅科研项目（Ｎｏ．Ｊ０９ＬＧ０２）。 作者简介：孙晓燕，硕士，主要研究方向：机器学习、数据挖掘；张化祥，通讯作者，教授，博士生导师；计华，ｌｇ￣，副教授。Ｅ－ｍａｉｈｘｉａｏｍｅｉｘｉ１９８７＠１６３．ｃｏｒｎ 收稿日期：２０１０—０４—２７；修回Ｉｔ期：２０１０．１０—１３ Ｃｏｍｐｕｔｅｒ Ｅｎｇｉｎｅｅｒｉｎｇ ａｎｄＡｐｐｌｉｃａｔｉｏｎｓ计算机工程与应用 倾向于多数类，如果只是用分类精度来衡量算法的分类性能， 则有失公允。因此，对于不均衡数据集，需要更加合理的评价 标准 。表１所示为二分类问题时常用的混淆矩阵。将多数类 称为正类（Ｐｏｓｉｔｉｖｅ），而少数类称为反类（Ｎｅｇａｔｉｖｅ），第一行与 类标相同的可能性大。在应用ＫＮＮ算法时，参数 的选择一 般依经验而定。 ２．２遗传算法 遗传算法 （Ｇｅｎｅｔｉｃ Ａｌｇｏｒｉｔｈｍ，ＧＡ）利用遗传算子产生 新一代种群实现种群优化。该算法被广泛应用到机器学＞Ｊ、 模式识别、工程优化等领域。遗传算法中，最重要的是三个算 子的选择： 第二行分别表示真实的多数类样本和少数类样本数量。ＴＰ与 Ⅳ分别表示正确分类的多数类和少数类数量。刚表示真实 Ｉ类标是多数类却被分类器误分为少数类的数量，ＦＰ表示真实 类标是少数类而被误分为多数类的数量。Ｆ－ｖａｌｕｅｔ （式（６））综 合考察查全率（式（５））与查准率（式（４）），其中 是可调节参 数，一般取值为１。只有当查全率与查准率都增大时，Ｆ－ｖａｌｕｅ 值才会增加，因此它可以作为不均衡数据集中有效的评价准 （１）选择算子 选择是从当前种群中选择适应度高的个体来重组或交 叉，选择时需要根据每个个体的适应度来选择新的个体代替 父代个体。如轮盘赌算法，它根据个体的适应度，分别计算每 则。Ｇ—ｍｅａｎ （式（７））是多数类分类精度（式（２））与少数类的 分类精度（式（３））乘积的平方根。显然，当Ａｃｃ 与Ａｃｃ这两个 值都大时，Ｇ－ｍｅａｎ的值才会大。故，Ｇ—ｍｅａｎ也可作为不均衡 数据集分类问题中合理的评价标准。 表１ 二分类问题的混淆矩阵 分类精度： Ａｃｃｕｒａｃｙ＝（丁Ｐ＋刀、ｒ）／（力’＋ＴＮ＋ＦＰ＋ＦＮ） 多数类分类精度： Ａｃｃ￣＝ＴＰ／（ＴＰ＋ＦＮ） 少数类分类精度： Ａｃｃ一＝ＴＮ／（ＴＮ＋ＦＰ） 查准率： Ｐｒｅｃｉｓｉｏｎ＝ＴＮ／ＴＮ＋ＦＮ 查全率： Ｒｅｃａｌｌ＝ＴＮ／ＴＮ＋ＦＰ ｌｕｅ＝．（１＋ｆｌ２）＊Ｐｒｅｃｉｓｉｏｎ＊Ｒｅｃａｌｌ ＊Ｒｅｃａｌｌ＊Ｐｒｅｃｉｓｉｏｎ Ｇ— 册： ｉ ２基于ＫＮＮ算法的少数类样本生成方法 ２．１ ＫＮＮ算法 ＫＮＮ［ ］（Ｋ－Ｎｅａｒｅｓｔ Ｎｅｉｇｈｂｏｒ）即 最近邻分类，是一种消 极学习方法，即该算法仅在需要时才计算每个新查询实例的 分类。对于一个新查询实例的最邻近是根据欧几里德距离计 算。例如，两个实例 、ｘ 之问的距离定义为ｄ（ｘ ，ｘｊ），其中， 厂 ————一 ｄ（ｘ ， ）＝ｆ∑ 一１ ）。，其中 表示实例 的第尼个属性。 ＝该算法思想可描述为： （１）对于每个待分类的每个样本 做以下步骤。 （２）计算待分类样本Ｘ 到训练实例Ｄ中每个样本 的距 离ｄ（ｘ ， ）。 （３）选取与待分类样本Ｘ 的 个距离最小的样本，并表示 为 ｌ， ２，…，Ｘ 。 （４）待分类样本 的类标为Ｘ，，Ｘ 一，Ｘ 中最普遍的类标。 由以上的描述可以看出ＫＮＮ是一种典型的基于类比的 算法，该算法在分类时隐含假定，在空间上距离相近的实例， 个个体的选择概率及累加概率，在每一轮随机选择【０，ｌ】之间 的一个随机数，该随机数作为选择指针来确定被选个体。 （２）交叉算子 交叉即从父代个体中选择个体进行两两交换，产生新的 个体加入到种群中。如单点交叉，即对于父代个体１与父代个 体２，随机产生一个交叉点位置，、ｉ、，父代个体１与父代个体２在交 、 、，＼ ∽ 叉点之后的基因部分进行互换，形成子代个体１与子代个体２。 （３）变异算子 变异即新产生的子代个体以很小的概率发生变化，变异 增加了种群的多样性，在一定程度上克服了遗传算法早熟收 敛的缺点。对于采用二进制编码的种群，对基因码的一位进 行翻转即可实现变异操作。 ２．３使用交叉算子与变异算子生成少数类样本 如上所述，过抽样方法通过增加少数类样例的数量来减 轻数据集的不均衡程度；遗传算法中的交叉算子与遗传算子 可以生产子代个体，并根据某种标准验证这部分子代个体的 有效性。基于两种算法的优点，本文提出了基于ＫＮＮ算法的 少数类样本生成方法（Ｇ．ＫＮＮ）。其中对于训练集 中少数类 使用遗传算法中交叉算子与变异算子产生新的子代个体，并 应用欧几里德距离验证样本的有效性。因为，本文认为新生 成的子代个体的类标与父代个体相同，则新生成的样本到父 代的欧式距离应小于某个最大值Ｍａｘ，而Ｍａｘ可取父代个体 之间的欧氏距离的最大值。算法具体步骤如下： （１）对于训练样本集合 ，分离出其中的少数类样本集合 Ｄ做下面的步骤。 （２）计算Ｄ中的每一个样本 到Ｄ中其他样本 （ｉ＃ｊ） 的平均欧几里德距离ｄ（ｘ，，Ｘｉ），并把最大值赋予Ｍａｘ。ｄ（ｘ ，ｘｊ）＝ 尘 一，Ｍａｘ＝Ｍａｘｄ（ｘ ，ｘ ），ｌ＜ｉ＜ｎ，”为少数类样本 ｎ—ｌ 。 个数。 （３）对少数类样本集合Ｄ使用遗传算法中的交叉算子与 变异算子产生少数类样本。 ①对训练集Ｄ依据轮盘赌算法选取”个个体加入到 集合中，并进行下面的交叉变异，个体的选择依据ｄ（ｘ ， ｆ）的 大小，部分个体在选择时被淘汰。 ②在选出ｎ个个体中，依据一定的概率随机选择两两实例 进行交叉，这里本论文采用单点交叉，每对父代个体交叉之后 产生一对子代个体，子代个体将代替父代个体加入到 中， 因此，交叉之后的样本容量依然是ｎ。 孙晓燕，张化祥，计华：用于不均衡数据集分类的ＫＮＮ算法 表３调整后的新数据集 数据集 ｍａｃｈｉｎｅ ２１ ｇｌａｓｓ ２９ ｇｌａｓｓ＿４６ ｄｉａｂｅｔｅｓ ｐａｇｅ—ｂｌｏｃｋｓ ３２９ ③交叉之后，按照一定的变异率对样本进行变异，新产生 的变异个体代替父代个体加入到Ｎ中。 ④验证新产生的个体的有效性，对于无效的样本，用这个 样本的一个父代个体代替。 ⑤若少数类样本的数量没有达到要求，则返回（３），继续 进行下一轮的交叉变异，直到满足条件为止。 此算法输出多个 的并集作为新产生的少数类集合，并 加入到训练集 中，形成最终的训练样本集 。即Ｔ＝｛ Ｕ １ ０ ０．９ ．ＶｌＵⅣ１Ｕ…ＵⅣ ｝，其中， 是新生成的少数类样本的集合，ｑ 是少数类扩充的倍数。例如，若少数类只需扩充一次就满足 ０．８ 要求，则新产生的少数类加入到集合Ⅳ１中，此时Ｔ ＝｛ ＵＮ１）； 若少数类需扩充两倍，则第一次时产生的少数类加入到集合 中，第二次新产生的少数类加入到集合Ⅳ，中，取Ｔ‘＝ ｛ ＵⅣ１Ｕ ｝。依次类推。 验证新产生的样本的有效性，即计算每个新产生的子代 个体 到训练集Ｄ中所有少数类的平均欧几里德距离，即 川ｘｉ一 ｄ（ｘ ，ｘ，）： 一。若 （ ， ，） Ｍａｘ，则认为此样本落 在了少数类样本的边界范围之内，有利于少数类的分类，应保 留；否则，应抛弃。 ３实验结果及分析 ３．１实验数据集 本文所用数据集来自于ＵＣＩ（ｈｔｔｐ：／／ａｒｃｈｉｖｅ．ｉｃｓ．ｕｃｉ．ｅｄｕ／ｍｌ／ ｄａｔａｓｅｔｓ．ｈｔｍ１）。其中，ｄｉａｂｅｔｅｓ是两类样本的不均衡数据集；将 ｍａｃｈｉｎｅ中第“一”类、ｇｌａｓｓ中第“七”类、ｇｌａｓｓ中第“三”类和第 “七”类、ｐａｇｅ—ｂｏｌｃｋｓ中第“二”类看做它们的少数类，其他类合 并作为多数类，分别形成新的不均衡数据集ｍａｃｈｉｎｅ ２１， ｇｌａｓｓ ２９，ｇｌａｓｓ ４６，ｐａｇｅ—ｂｌｏｃｋｓ～３２９ 。处理之后的数据集如 表２所示。 表２数据集描述 数据集 样本个数属性个数类数量（多：少）少数类比例／（％） ３．２实验设置 如何设置遗传算法中的各种参数，到目前为止还没有一 个合理的理论依据。通常情况下，交叉概率选取０．４～０．９，变异 率选取０．００１－４）．１之间＿ｌ３１。对于每个数据集，本文中采取迭代 次数为３０次，交叉率为０．６６７，变异率为０．０５。同时采用十折 交叉验征对算洳斩ｉ耳骱，评价防 住使用Ｆ－ｖａｌｕｅ值与Ｇ—ｍｅａｎ值。 ３．３实验结果及分析 按照本文提出的基于交叉算子与变异算子产生少数类的 方法，对表２中的数据集进行调整，调整后的数据如表３显 示。其中，表３中的数据是十折交叉验证中被用来训练ＫＮＮ 分类器的那部分数据。图１显示了传统ＫＮＮ，加入随机过抽 样后的ＫＮＮ算法（Ｒ—ＫＮＮ）及本文提出的Ｇ．ＫＮＮ在少数类的 Ｆ－ｖａｌｕｅ上的对比。图２显示的是三种算法在Ｇ—ｍｅａｎ上的比较。 Ｏ．７ Ｏ ６ ０．５ ｍａｃｈｉｎｅ２１ ｇｌａｓｓ２９ ｇｌａｓｓ ４６ ｄｉａｂｅｔｅｓ ｐａｇｅ一 数据集 ｂｌｏｃｋｓ一３２９ 图１ ＫＮＮ、Ｒ—ＫＮＮ及Ｇ—ＫＮＮ在Ｆ－ｖａｌｕｅ卜的比较 １．０ ０．９ ０．８ 蔷 芒 ０．７ ０．６ ０．５ ｍａｃｈｉｎｅ２ １ ｇｌａｓｓ２９ ｇｌａｓｓ４６ ｄｉａｂｅｔｅｓ ｐａｇｅ一 数据集 ｂｌｏｃｋｓ～３２９ 图２ ＫＮＮ、Ｒ—ＫＮＮ及Ｇ—ＫＮＮ在Ｇ—ｍｅａｎ｝：的比较 从图１中可以看出，Ｒ—ＫＮＮ与ＫＮＮ在少数类的Ｆ－ｖａｌｕｅ值 上相差不大，这是因为随机过抽样并没有增加新的少数类样 例，故而在少数类分类性能方面并没有很大的提高；而本文提 出的Ｇ．ＫＮＮ算法相比于其他两种算法，在五个数据集上获得 较高的Ｆ－ｖａｌｕｅ值，即在少数类分类性能方面取得了不错的效 果。其中，Ｆ－ｖａｌｕｅ值在ｍａｃｈｉｎｅ ２１数据集提高了９．１％，在 ｇｌａｓｓ ２９数据集上提高了２．４％，在ｇｌａｓｓ ４６数据集上提高了 ４．２％，在ｄｉａｂｅｔｅｓ数据集上提高了２．８％，而在ｐａｇｅ．ｂｌｏｃｋｓ ３２９ 数据集上只提高了０．１％，是因为虽然少数类相对于多数类而 言比较少，但是它的个数足够用来训练一个分类器，因此。其 Ｆ－ｖａｌｕｅ值并没有大幅度的提高。图２显示的是三种算法在 Ｇ—ｍｅａｎ上的比较结果，可以看出Ｇ—ＫＮＮ算法的总体分类性能 在选用的数据集上优于Ｒ—ＫＮＮ及ＫＮＮ。 综上所述，实验结果验证了Ｇ．ＫＮＮ方法的有效性，该算 法产生的少数类样本都在原来少数类样本的周围，因此在使 用ＫＮＮ算法时，一个少数类的测试样例周围的样本数增加 了，测试样例被分类正确的可能性就增大了。所以，该算法不 仅提高了少数类的分类精度，而且总体的分类性能也有提高。 ４结束语 传统的ＫＮＮ分类算法在处理不均衡数据集时，分类预测 倾向于多数类；加入随机的过抽样算法可以提高少数类的分 类精度，但易导致过学习。本文提出了一种在ＫＮＮ算法中使 （下转２３６页） ２３６ ２０１１，４７（２８） Ｃｏｍｐｕｔｅｒ Ｅｎｇｉｎｅｅｒｉｎｇ ａｎｄＡｐｐｌｉｃａｔｉｏｎｓ计算机工程与应用 群算法ＡＣＯ和快速随机搜索树算法ＲＲＴ进行了性能实验比 较，比较结果示于表１。实验环境如图１ｌ和图１３所示。 表１相同环境下时间性能的比较 参考文献： （１］Ｔｒｏｖａｔｏ Ｋ Ｉ，Ｄｏｒｓｔ Ｌ．Ｄｉｆｅｒｅｎｔｉａｌ Ａ’［Ｊ】．ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｋｎｏｗｌｅｄｇｅ ａｎｄ Ｄａｔａ Ｅｎｇｉｎｅｅｒｉｎｇ，２００２，１４（６）：１２１８—１２２９． ［２马兆青，袁曾任．２］基于栅格方法的移动机器人实时导航和避障［Ｊ】． 机器人，１９９６，１８（６）：３４４—３４８。 【３高云峰，黄海．３］复杂环境下基于势场原理的路径规划方法［Ｊ】＿机器 人，２００４，２６（２）：１１４—１１８ 由表ｌ结果可以看出，在两种环境下，本文算法的收敛时 【４］谢宏斌．动态环境中移动机器人路径规划的研究【Ｄ１．无锡：江南大 学，２００３． 间都优于ＡＣＯ算法，在有陷阱类的复杂环境下，本文算法的耗 时远远小于其他两种算法，且从图１１和图１３的结果看，用本 文算法都能得到全局最优路径，这都展示本文算法性能优于 这些代表性算法。 ［５］樊晓平，罗熊，毕异，等复杂环境下基于蚁群优化算法的机器人路 径规划［Ｊ】．控制与决策，２００４，１９（２）：１６６．１７０． 【６］Ｋｅｎｎｅｄｙ Ｊ，Ｅｂｅｒｈａｒｔ Ｒ Ｃ．Ｐａｒｔｉｃｌｅ ｓｗａｍｉ ｏｐｔｉｍｉｚａｔｉｏｎ［Ｃ］／／Ｐｒｏｃ ｏｆ ＩＥＥＥ Ｉｎｔｌ Ｃｏｎｆｏｎ Ｎｅｕｔｒａｌ Ｎｅｔｗｏｒｋｓ，Ｐｅｒｔｈ，１９９５：１９４２—１９４８． ［７】Ｈｏｌｌａｎｄ Ｊ Ｈ．Ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ ｏｐｔｉｍａｌ ａｌｌｏｃａｔｉｏｎ ｏｆ Ｗａｉｌｓ ｓＩ ［Ｊ】． ５结语 本文提出了一种基于环境二次划分和改进遗传算法的机 Ｊｏｕｒｎａｌ ｏｆ Ｃｏｍｐｕｔｉｎｇ，１９７３，２（２）：８８—１０５． ［８］Ｎｅａｒｃｈｏｕ Ａ Ｃ．Ｐａｔｈ ｐｌａｎｎｉｎｇ ｏｆ ａ ｍｏｂｉｌｅ ｒｏｂｏｔ ｕｓｉｎｇ ｇｅｎｅｔｉｃ ｈｅｕｒｉｓｔｉｃｓ［Ｊ］．Ｒｏｂｏｔｉｃａ，１９９８，１６（５）：５７５—５８８． 器人路径规划算法，将基本栅格环境依据障碍物的多少进行 了二次划分，提高了种群染色体编码自适应环境的能力；算法 采用基于显性基因的保险矩阵这一启发信息的初始种群产生 策略，克服了传统遗传算法在个体编码和种群初始化上的盲 目性，显著地提高了初始种群的有效性和遍历性；同时，在遗 传操作中，选择算子也采用了保险矩阵的启发信息，从而提高 了选择的效率。仿真实验结果证实了即使是在有陷阱等复杂 障碍物的环境下，用本文算法也能获得最优路径，且收敛速度 ［９］国海涛．基于蚂蚁自动分流的机器人路径规划新算法研究【Ｄ】．南 京：南京师范大学，２００８． ［１Ｏ】毕慧敏．董海鹰＿改进遗传算法在机器人路径规划中的应用［Ｊ］．测 控技术，２００６，２５（４）：５３—５４． ［１ １】于红斌，李孝安．基于栅格法的机器人快速路径规划［Ｊ】．微电子学 与计算机，２００５，２２（６）：９８—１００． ［１２１何娟，涂中英，牛玉刚．一种遗传蚁群算法的机器人路径规划方法［Ｊ】． 计算机仿真，２０１０，２７（３）：１７０—１７２． ［１３］周兰凤，洪炳熔．用基于知识的遗传算法实现移动机器人路径规 划…．电子学报，２００６，５（５）：９１１—９１２． 比已有代表性算法有显著提高，效果令人满意。 然而在本文算法中只针对静态障碍物避碰做出处理，对 于环境中存在动态障碍物，找出一种对动态障碍物依靠环境 信息选择环境划分机制是以后的研究方向之一。 ［１４】肖晓明，陈志兴，高平安．动态确定基因数的遗传算法路径规划【Ｊ】． 计算机应用研究，２００９，２６（７）：２４６９．２４８２． （上接１４５页） ｃａｔｉｏｎｌ ．Ｊｏｕｒｎａｌ ｏｆ Ｍａｃｈｉｎｅ Ｌｅａｒｎｉｎｇ Ｒｅｓｅａｒｃｈ，２００１，２（２）：１３９—１５４． ［５］Ｋｕｂａｔ Ｍ，Ｍａｔｗｉｎ Ｓ．Ａｄｄｒｅｓｓｉｎｇ ｔｈｅ ｃｏｕｒｓｅ ｏｆ ｉｍｂａｌａｎｃｅｄ ｔｒａｉｎ— 用交叉算子与遗传算子生成少数类的方法（Ｇ．ＫＮＮ），并对生 成的少数类进行有效性验证，对符合要求的少数类要入到训 ｎｇ ｓｅｔｓ：ｏｎｅ—ｓｉｉｄｅｄ ｓｅｌｅｃｔｉｏｎ［Ｃ］／／Ｐｒｏｃ ｏｆ ｔｈｅ １４ｔｈ Ｉｎｔｅｍａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｍａｃｈｉｎｅ Ｌｅａｍｉｎｇ，Ｓａｎ Ｆｒａｎｃｉｓｃｏ，ＣＡ，１９９７：１７９—１８６． 练集中。实验的结果证明，此算法不仅提高了少数类的分类 性能，而且总体的性能也有所提高。但是，也应看到，本文提 出的生成少数类样本的过抽样算法，在ＫＮＮ算法中取得了不 错的效果，但如何把这样的少数类生成方法扩展到其他的传 统方法，是本文下一步需继续努力的方向。同时，在遗传算子 与交叉算子的选择方面也是依据经验而定，更一般的参数设 置还需更加科学的理论探索。 【６］Ｃｈａｗｌａ Ｎ Ｖ，Ｂｏｗｙｅｒ Ｋ Ｗ，Ｈａｌｌ Ｌ Ｏ，ｅｔ ａ１．ＳＭＯＴＥ：ｓｙｎｔｈｅｔｉｃ ｍｉｎｏｒｉｔｙ ｏｖｅｒ－ｓａｍｐｌｉｎｇ ｔｅｃｈｎｉｑｕｅ［Ｊ］．Ｊｏｕｒｎａｌ ｏｆ Ａｒｔｉｉｆｃｉａｌ Ｉｎｔｅｌｌｉ— ｇｅｎｃｅ ａｎｄ Ｒｅｓｅａｒｃｈ，２００２：３２１—３５７． ［７］Ｄａｓａｒａｔｈｙ Ｂ Ｖ．Ｎｅａｒｅｓｔ Ｎｅｉｇｈｂｏｒ（ＮＮ）ｎｏｒｍｓ：ＮＮ ｐａｔｔｅｍ ｃｌａｓｓｉｉｆ－ ｃａｔｉｏｎ ｔｅｃｈｎｉｑｕｅｓ［Ｍ］．Ｌｏｓ Ａｌａｍｉｔｏｓ，Ｃａｌｉｆｏｍｉａ：ＩＥＥＥ Ｃｏｍｐｕｔｅｒ Ｓｏｃｉｅｔｙ Ｐｒｅｓｓ，１９９１． 【８】谷琼．面向ｊ 北京：中国地质大学，２００９． 参考文献： ［１］Ｗｅｉｓｓ Ｇ Ｍ．Ｍｉｎｉｎｇ ｗｉｔｈ ｒａｒｉｔｙ：ａ ｕｎｉｆｙｉｎｇ ｆｒａｍｅｗｏｒｋ［Ｊ］．ＳＩＧ— ＫＤＤ Ｅｘｐｌｏｒａｔｉｏｎｓ，２００４，６（１）：７—１９． ［９】Ｊｏｓｈｉ Ｍ Ｖ．Ｏｎ ｅｖａｌｕａｔｉｎｇ ｐｅｒｆｏｒｍａｎｃｅ ｏｆ ｃｌａｓｓｉｆｉｅｒｓ ｆｏｒ ｒａｒｅ ｃｌａｓｓｅｓ［Ｃ］／／Ｐｒｏｃ ｏｆ ｔｈｅ ２ｎｄ ＩＥＥＥ Ｉｎｔｅｍａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｄａｔａ Ｍｉｎｉｎｇ，Ｍａｅｂａｓｈｉ，Ｊａｐａｎ，２００２：６４１—６４４． 【２】Ｃｉｒａｃｏ Ｍ，Ｒｏｇａｌｅｗｓｋｉ Ｍ，Ｗｅｉｓｓ Ｇ Ｍ．Ｉｍｐｒｏｖｉｎｇ ｃｌａｓｓｉｆｉｅｒ ｕｔｉｌｉ— ｔｙ ｂｙ ａｌｔｅｒｉｎｇ ｔｈｅ ｍｉｓｃｌａｓｓｉｆｉｃａｔｉｏｎ ｃｏｓｔ ｒａｔｉｏｎ［Ｃ］／／Ｐｒｏｃ ｏｆ ｔｈｅ Ｉ ｓｔ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｗｏｒｋｓｈｏｐ ｏｎ Ｕｔｉｌｉｔｙ—ｂａｓｅｄ Ｄａｔａ Ｍｉｎｉｎｇ．Ｎｅｗ Ｙｏｒｋ：ＡＣＭ，２００５：４６—５２． ［１０１ Ｍｉｔｃｈｅｌ Ｔ Ｍ．机器学习【Ｍ】．曾华军，张银奎，译．北京：机械工业出 版社，２００３：１６５—１６８． ［１１］王小平，曹立明．遗传算法—理论、应用与软件实现［Ｍ】－西安：西安 交通大学出版社，２００２：３６—４６． 【１２］韩慧，王路，温明，等．不均衡数据集学习中基于初分类的过抽样 算法【Ｊ］．计算机应用，２００６，２６（８）：１８９４—１８９７． ［１３】杜鹃，姜丽丽，陈红丽．不均衡数据集文本分类中少数类样本成长 方法研究［Ｊ］ｌ计算机应用研究，２００９，２６（１Ｏ）：３７３１・３７３３． 【３］Ｆａｎ Ｗ，Ｓｔｏｌｆｏ Ｓ Ｊ，Ｚｈａｎｇ Ｊ，ｅｔ ａ１．ＡｄａＣｏｓｔ：ｍｉｓｃｌａｓｓｉｃａｔｉｏｎ ｃｏｓｔ・ｓｅｎｓｉｉｔｖｅ ｂｏｏｓｔｉｎｇ［Ｃ］／／Ｐｒｏｃ ｏｆ ｔｈｅ １６ｔｈ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒ— ｅｎｃｅ ｏｎ Ｍａｃｈｉｎｅ Ｌｅａｒｎｉｎｇ．［Ｓ．１．］：Ｍｏｒｇａｎ Ｋａｕｆｍａｎｍ，１９９９：９７—１０５． ［４】Ｍａｎｅｖｉｔｚ Ｌ Ｍ，Ｙｏｕｓｅｆ Ｍ Ｏｎｅ—ｃｌａｓｓ ＳＶＭｓ ｆｏｒ ｄｏｃｕｍｅｎｔ ｃｌａｓｓｉｆｉ—