基于类别相关的新文本特征提取方法

第２９卷第５期２０１２年５月

计算机应用研究

ＡｐｐｌｉｃａｔｉｏｎＲｅｓｅａｒｃｈｏｆＣｏｍｐｕｔｅｒｓ

Ｖ０１．２９Ｎｏ．５

Ｍａｖ２０１２

基于类别相关的新文本特征提取方法

林少波，杨丹，徐玲

（重庆大学软件学院，重庆４０００３０）

摘要：为了避免文本特征提取过程中负相关特征与弱相关特征产生的干扰，提出一个新的基于类别正相关并口

强相关（ｓＰ）的特征提取方法。通过结合正相关性因子和强相关因子，ｓＰ方法能够有效地区别特征与类别正负相关性和强弱相关程度，通过优先选择正相关和强相关特征，避免了负相关和弱相关特征的干扰，从而有效地提

取高质量的文本特征。实验结果表明，该方法具有强降雏能力和良好的分类效果。关键词：正相关；强相关；文本分类；特征降雏；特征提取中图分类号：ＴＰ３９１

文献标志码：Ａ

文章编号：１００１—３６９５（２０１２）０５—１６８０一０４

ｄｏｉ：１０．３９６９／ｉ．ｉｓｓｎ．１００１．３６９５．２０１２．０５．０２１

Ｎｅｗａｐｐｒｏａｃｈ

ｔｏ

ｆｅａｔｕｒｅｓｅｌｅｃｔｉｏｎｆｏｒ

ｔｅｘｔ

ｃａｔｅｇｏｒｉｚａｔｉｏｎｕｓｉｎｇｃｌａｓｓｃｏｒｒｅｌａｔｉｏｎ

ＵＮＳｈａｏ＿ｂｏ，ＹＡ“ＧＤａｎ，ＸＵＬｉｎｇ

（ｓ旃剐矿ｓ妒ｍｍ西洒Ｍ＾昭，矾ｏ，啪蛔№妇ｍ蚵，‰“卯ｉｎｇ４０００３０，肌￡ｍ）

Ａｂｓｔ瑚ｃｔ：Ｔｈｉｓｐ印ｅｒｐｍｐｏｓｅｄ

ｃｏｒｒｅｌａｄｏｎａｎｄｐｏｓｉｔｉｖｅｃｌａｓｓ

ａ

ｎｅｗ印ｐｒｏａｃｈｏｆｆｅａｔｕｒｅｓｅｌｅｃｔｉｏｎｆｏｒｔｅｘｔｃａｔｅｇｏｒｉｚａｔｉｏｎ，ｗｈｉｃｈ

ｗａｓｂａｓｅｄ

ｏｎ

ｔｈｅｓｔｒｏｎｇｃｌａｓｓ

ｃｏｎ．ｅｌａｔｉｏｎ，ｎ砌ｅｄ

ＳＰ．ＳＰｃｏＩｌｌｄｅｌｉｍｉｎａｔｅｔｈｅｅｆＥｂｃｔｏｆｎｅｇａｔｉｖｅａｎｄｐｏｏｒｃｏｎ℃１ａｄｏｎｆｅａｔｕｒｅｅⅡｂｃｔ－

ｔＩｌｅｎｅｇａｔｉｖｅｂｙｐｏｓｉｔｉＶｅｃｏｒｒｅｌａｔｉ蚰ｆａｃｔｏｒ－．ａＩｌｄｅｌｉ商ｎａｔｅｄｔｈｅ

ｅＨｋｃｔ０ｆｎｅｇａｄｖｅｆｂａｔｕｒｅ．ＳＰｄｉｓｃｒ主ｌＩｌｉｎａｔｅｄｂｅｔｗｅｅｎｔｈｅｓｔＩＤｎｇｃｌａｓ８ｏｆｆｅａｔｕｒｅｓａｎｄｔｈ。ｐｏｏｒｃｌａｓｓｃｏｒｒｅｌａｔｉｏｎｏｆｆｅａ・ｔｕｒｅｓｂｙｐｏｓｉｔｉｖｅｃｌａｓｓｃｏｒｒｅｌａｔｉｏｎｆａｃｔｏｒ，ａｎｄｅｌｉｍｉｎａｔｅｄｔｈｅ雒ｂｃｔｏｆｐ００ｒｃｏ玎ｄａｔｉｏｎｆｅａｔｕｒｅ．ＳＰｃｏｕｌｄｓｅ】ｅｃｔｈｉｇｈｑｕ８１ｉｔｙｆｅａ—ｔｕｒｅｓｅⅡｂｃｔｉｖｅｌｙｂｙｃｏｍｂｉｎｉｎｇｔｌｌｅｓｅｔｗｏｆａｃｔｏｒｓ．ＴｈｅＴｅｓｕｈｏｆＥ１ｐｅｒｉｍｅｎｔｉｎｄｉｃａｔｅｓｔｈａｔｔｈｅｐｒｏｐｏｓｅｄ印ｐｍａｃｈｈａｓａｇｏｏｄｐｅｒ－ｌｙ．ＳＰｄｉｓｃｒｉｍｉｎａｔｅｄｂｅｔｗｅｅｎｔｈｅｐｏｓｉｔｉｖｅ

ｆｅａｔ岍ａｎｄ

ｋｔｕｒｅｃｏｒｒｅ№ｏｎ

ｆｏ咖ａｎｃｅ

ａｔ

ｃａｔｅｇｏｒｉｚａｔｉｏｎａｎｄｒｅｄｕｃｉｒｌｇｈｉｇｈｄｉｍｅｎｓｉｏｎａｌ侣ａｔⅡｒｅ８ｐａｃｅ．

Ｋｅｙｗｏｒｄｓ：ｐｏｓｉｔｉｖｅｃｏｎ℃ｌａｔｉｏｎ；ｓｔｍｎｇｃｏｒｒｅｌａｔｉｏｎ；ｔｅｘｔｃｌａｓｓｉｆｉｃａ石ｏｎ；ｆｅａｔｌｌｒｅｒｅｄｕｃｔｉｏｎ；ｆｅａｔｕｒｅｓｅｌｅｃｔｉｏｎ

特征子集，以达到降低特征空问维度的目的。在特征选择过程

Ｏ引言

文本自动分类是在给定分类体系的情况下，根据预定义类别中的文本数据信息总结归纳出分类的规律性，根据这个规律性将未标明类别的文本映射到预定义的类别¨Ｊ。

现有文本分类技术通常有两种文本表示模型，即布尔模型和向量空间模型嵋１。向量模型中特征向量与文本集合中的文本一一对应，将文本集合中的词条作为向量中的特征项。布尔模型可以看做是向量模型的一种特例，根据特征项在文档中出现与否，特征项的权值只能取ｌ或ｏ。布尔模型不能很好地体现文本特征的重要程度，通常情况下布尔模型的效果不如其他模型。ＩｆＩｉ向量空间模型是一种不考虑词与词之间的上下文关系、出现的顺序和位置以及文本长度的词袋（ｂａｇ

ｏｆ

中不包括任何学习算法。特征提取通过对特征向量空间的降维，不仅提高了分类速度，而且过滤ｒ噪声数据，在提高精度的同时还有助于解决过拟合问题。

现有的特征提取方法包括文档频数（ｄ∞ｕｍｅｎｔ“ｑｕｅｎｅｙ，ＤＦ）、信息增益（ｉｎ南ｍ撕ｏｎｇａｉｎ，ＩＧ）、互信息（ｍｕｔｕａｌ

ｉ山ｍａ．

ｔｉｏｎ，ＭＩ）、ｒ统计（ｃｈｉ－ｓｑＩｌａｒｅｓｔａｔｉｓｔｉｃ，ｃＨＩ）和ｃｃ（ｃ０Ｈｅｌａｔｉｏｎ

ｃｏｅｍｃｉｅｎｔ）等Ｈ“。。目前ＣＨＩ和ＩＧ性能较好，ＤＦ和ＭＩ性能较差＂’。Ｃｃ是基于相关系数的特征提取方法，是ＣＨＩ公式的开平方式。两者的区别是，ｃＨＩ评价函数计算得到特征值具有非负性，等同了正相关和负相关特征的对文本分类的重要性，而ｃｃ通过对ＣＨＩ公式的开平方，使得特征值具有正负性，区别了正相关和负相关特征对文本分类的重要件。８Ｊ。文献［９］使用选择带有较强类别信息的特征词，在线性分类器上有较好的准确率。文献［１０］指出对于文本分类而言，特征的重要性主要由特征的正相关能力决定。过多地考虑特征项与类别的负相关度，不仅不能提高分类的精度，还可能对分类结果产生干扰。

本文提出了一种基于类别正相关和类别强相关的新特征提取方法ＳＰ。该方法只选取与类别正相关和强相关的特征。

ｗｏｒｄｓ）文

本表示模型。故本文选择向量空问模型作为文本表示模型。

针对文本分类中文本特征向量空间的高维性问题，采用特征提取方法进行特征降维。，该方法是基于过滤模型ｐ１的一种特征选择方法，过滤模型的基本思想是根据训练集数据的一般特性进行特征选择，通过构造某种特征评价函数，来统计文本特征空问中各个特征项的值，将各个特征项按其特征值排序，并根据设置的阈值选择出合适规模的对文本分类贡献较大的

收稿日期：２０１１—１０—２０；修回日期：２０１１．１１—３０

（ＣＳＴＣ２００９ＡＢ２２３０）

基金项目：国家自然科学基金资助项目（６０９７５叭５）；重庆市重点攻关资助项目

作者简介：林少波（１９８６一），男，福建莆田人，硕士研究生，主要研究方向为文本分类、企业信息化及电子政务（ｈｎｓｈａｏｂ０１２３＠１２６ｃｏｍ）；杨丹（１９６２一），男，重庆云阳人，教授，博导，博士，主要研究方向为图像处理、模式识别、机器学习；徐玲（１９７５一），女，安徽庐江人，讲师，博士，主要研究方向为数据挖掘、图像处理

第５期

林少波。等：基于类别相关的新文本特征提取方法

・１６８１・

首先给出特征与类别相关性和相关度的概念，通过对ｃＨＩ不能区别正相关特征与负相关特征重要程度的原因分析，将文本特征与类别正、负相关特征的重要性差异度作为正相关性因子，用来区别特征与类别正负相关性。通过对文本特征在文本集合中分布规律的分析，将文本特征类内和类间的相关度指标结合成为强相关度因子，用来区别特征与类别的强弱相关度。

１

ｂ）若存在一个特征词，在当前所在类别内，包含该特征词的文档在该类别中比例越高越能代表当前类别，对分类贡献越大。将衡量类内特征分散度的指标称为相关度的类内指标。

在此采用两种比值表示相关度的类间指标和类内指标：

ａ）舍。如果特征词“只与类别ｃ。相关度高，舍值越高，

』

特征与类别的相关性

特征与类别的相关性包括正相关性和负相关性。为了更

那么说明特征词ｌ。能很好地代表类别ｃ。，那么詈的值就高。

ｂ）≠。在类别ｃ。中有两个特征词ｋ和‘。，它们各自对应ｕＩ

好地描述特征与类别的正负相关陛概念，这里将通过对文本集

合的一般特性的分析，具体地描述特征与类别的正负相关性。文本集合这种特性可以由表１中四种基本元素４、曰、ｃ、口表示。为进一步解释，现作以下假设：在一个文本集合日中，假设存在一个类别ｑ，集合中除ｃ。以外的类别表示为ｃ。，则按照文本所属类别划分，该集合日可以表示为ｈ，ｃ。｝。假设存在一个文本特征词ｚ；，集合中除ｔ。外的特征词表示为缸，则按照是否包括特征词屯划分，该集合日可以表示为ｈ，“｝。按照文本是否包括特征词“，是否属于类别ｃ。，可将文本集合日表示为ｈ，ｃ；｝和ｈ，￡。｝的笛卡尔乘积。该集合由表ｌ所示的四个信息元素Ａ、曰、Ｃ、Ｄ构成。

表１信息基本元素表

一个务值，那么争值越大的特征词越能代表类别‰

鉴于以上概念的提出，结合类间指标和类内指标来刻画特征与类别的相关程度，区别强、弱相关特征。将特征与类别的强相关度因子ｓｃＤ（ｓ咖ｎｇｃ０Ⅱｅ１．ａｔｉｏ口ｄｅ孕ｅｅ）表示为

ｓｃＤ（％ｃ。）２蔼

＾

一

（１）

若一个特征与一个类别相关度越强，则ｓｃＤ值越大。ｓｃＤ优先选择与类别强相关的特征，从而能够有效地避免弱相关特征产生的噪声干扰。

３

ＳＰ文本特征提取方法

基于以上文本特征与类别的相关性和相关度的概念的提

ｅ￡

ＢｌＤ．

出，采用强相关度因子ｓＣＤ来区别特征与类别相关度的强弱，并对ｃＨＩ无法体现正相关特征与负相关特征的重要性差异度的原因进行分析，寻求特征与类别间的正负相关性的具体表示

表１中，Ａ。＝‰，ｃ，）表示不仅包含特征靠而且属于类别ｑ

的文本数量；Ｂ；＝（“，ｃ。）表示包含特征‘但是不属于类别ｃ。的文本数量；ｃ。＝（“，ｑ）表示不包含特征屯但是属于类别ｑ

方法。

ｃＨｌ统计方法是在数理统计中一种常用的检验两个变量独立性的方法。ｃＨＩ最基本的思想就是通过观察实际值与理论值的偏差来确定理论的正确与否。其运用在文本特征选择中，假设“与类别ｃ。之间是独立的”“。这种独立关系类似于

的文本数量；Ｄｊ＝瓴，ｑ）表示不包含特征ｔ。并且不属于类别ｃｆ

的文本数量。文本总数量Ⅳ＝Ａ＋Ｂ＋ｃ＋Ｄ。

基于表ｌ的描述，将特征选择方法根据特征与类别的相关性进行分类，包括正相关性和负相关性”…。

定义ｌ若特征项“当且仅当只出现在与类别ｑ相关的文本中，则称特征项‘。与类别ｃ。正相关。

定义２若特征项￡。当且仅当只出现在与类别ｑ不相关的文本中，则称特征项缸与类别ｃ。负相关。

表ｌ中Ａ。＝（“，ｃ。）和Ｄ；＝（屯，ｃ；）描述的是特征项气和类别ｑ的正相关程度，段＝（气，ｑ）和ｃ；＝（靠，ｃ；）描述的是特征项“和类别ｃ。的负相关程度。

具有一维自由度的，分布，九对于ｃ；的ｃＨＩ统计量为

．

ⅣｆｄＤ—ＢＣ、２

矿（‰ｑ）２瓦了两面膏面可等南面了可

（２）

ｃＨＩ统计方法用ｒ（靠．ｃ．）来度量特征项屯和类别ｃ。之间的相关程度。ｒ（＃。，ｃｉ）值越大说明特征项缸和类别ｃ，相关程

度越高，此时特征项“所包含的与类别ｃ：相关的信息就越多。

∥（１。，ｃｉ）＝ｏ表示特征项屯与类别ｃ；相互独立。特征项“与类别ｑ的相关陛越强掰２（靠，ｅ；）的值就越大。特征性选择的过程就是计算特征项ｋ和类别ｃ：的，（屯，ｃ；）值，然后按值大小

排序，根据实际需要选取ｃＨＩ值大的特征项。

由定义ｌ和定义２可知，Ａ；和Ｄ。描述的是特征项屯和类别ｃ。的正相关程度，曰。和ｃ。描述的是特征项“和类别ｃ，的负相关程度。由概率论可知，假设Ａ。的值越大，Ｄ。的值越大，即特征屯出现在ｃ；类的文本里丽的概率越大，则ｆ。与ｃ；正相关度越大。假设置的值越大，ｃ。的值越大，那么特征“出现在类别ｃ。的概率越大。

Ａ；Ｄ；一Ｂ；ｃ；体现了特征ｋ与类别ｃ；的正、负相关特征重要性差异度。若Ａ。Ｄ。一日．Ｇ；＞０，则特征“与类别ｃ；体现出正相关性；若Ａ。Ｄ；一丑；ｃ。＜Ｏ，则特征“与类别ｃ。体现出负相关

２特征与类别的相关度

特征与类别的相关度可分为强相关和弱相关。在此结合本文第ｌ章的文本集合一般性描述来进一步阐述特征与类别的相关度概念。特征的相关度是衡量一个特征代表一个类别的程度。特征与类别的相关度评价可以基于以下两种指标：

ａ）若存在一个特征词，该特征词越集中出现在当前所在类别文档中，在其他类别文档中越少出现，那么这个特征词越

能区别所在类别与文本集合中的其他类别。即该特征词越能

代表当前类别，对分类贡献越大。这里将衡量类别问特征分散度的指标称为相关度的类间指标。

性。由式（２）可知，分子中（Ａ；Ｄ。一ＢｉＧ）ｊ使得４。Ｄ。一曰。ｃ。呈现

・１６８２・

计算机应用研究

第２９卷

非负性，若特征“与类别ｃ；体现出正相关度越大，那么Ａ。Ｄ。一层ｃ。必然为正值，且值将随正相关度的增加而增大，ｃＨＩ得出的特征值也将增大。若特征“与类别ｃ。体现出负相关性，那么Ａ。Ｄ；一占。ｃ．必然为负值，而且值随着负相关度的增加而减小，但是（Ａ。Ｄ。一曰。ｃ。）２的值将随之变大，ｃＨＩ得出的特征值也将变大。这样正、负相关特征的重要性差异度便无法体现。

通过以上分析，正、负相关特征重要性差异度能很好地刻画文本特征与类别的正负相关性。假定用正相关性因子Ｐｃ（ｐｏｓｉｔｉ”ｃｏｒｒｅｌａｔｉｏｎ）来区别特征与类别间的正负相关性，则

Ｐｃ（“，ｃ；）＝一。Ｄ。一吼ｃ。

（３）

新文本特征提取方法的目的是选择与类别正相关并且强

．相关的特征词。综上所述，提出新的文本特征提取方法ｓＰ

（ＳＣＤ＆ＰＮＣ）：

＾Ａ

一，）

５Ｐ（‰ｑ）２

ｓｃＤ。９ｃ

２蔼（４ｔＤｆ一日ｔｃｔ）２‘蔬‘１）《（４）

著一个特征词与类别正相关并且强相关，那么ｓＰ值一定越大，故ｓＰ优先选择与类别正相关并且强相关的特征词。

文本特征提取策略可以分为局部和全局特征提取。文献［１２］指出在均衡数据中，全局特征提取优于局部特征提取，单独利用局部特征提取的缺点是它不能有效地选取到能代表所有类别的特征集合，忽视了全体训练样本和类别的整体性。文献［１３］指出在偏斜数据集中使用加权局部特征选择优于全局特征，因为偏斜数据中各个类别问文档数量差距很大，基于全局提取的特征集合不能代表少数类。本文使用均衡数据集，采用全局特征提取策略。

基于全局特征提取策略的特征提取方法，需获取特征项“对整个文档集的全局特征值时，由于ｓＰ是基于类别正相关性与强相关性的特征提取方法，采用式（５）基于最大值的方式计算全局特征，度量各个特征对于分类的重要性，能够选择出对某一个类具有较好标志作用的特征项。

ｓＰ…（“）＝ｍ“｛ｓＰ（“，ｑ）｝

（５）

ＳＰ特征提取方法的优点在于：计算复杂度低，只选择与类别正相关并且强相关的特征，避免了弱相关特征和负相关特征的干扰。

４实验结果及分析

本实验采用复旦大学计算机信息与技术系国际数据库中心自然语言处理小组的文本分类语料库…。该语料库共分为２０个类别，测试集共９８０４篇文章，训练集９８０４篇文章。本文从中抽取９个类别作为训练集，包括艺术、历史、航空、计算机、环境、农业、经济、政治、体育。在原训练集中每个类别随机抽取２００个训练文档，共计１８００个训练文档。在原测试集中每个类别随机抽取ｌｏｏ个测试文档，共计９００个测试文档。训

练文档和测试文档的比例为２：ｌ，通过预处理，测试文档包含

５７

７７１个特征词。

实验采用ＫＮＮ分类算法，实验效果的评价指标采用Ｍ”－

ｃｏ—ＲｅｃａＩｌ、Ｍａｒｃｏ—Ｐｒｅｃｉｓｉｏｎ、和Ｍａｒｃｏ—Ｆ１。式（６）～（８）分别表不宏平均查全率、宏平均查准率、宏平均Ｆ１值。其中ｒｅｃ丑１１。表示类ｃ。查全率，ｐｒｅｃｉｓｉｏｎ。表示类ｃ：查准率，Ｆｌｉ表示类ｃ：的Ｆ１法ｃＨＩ、ｃＣ、ＤＦ进行比较。

ｌＣｌ

∑ｒｅｃａｌｌｉ

ＭａｒｃｐＲｅｃａｌｌ

２苛

（６）

ＩＣｌ

Ｍ—ｕ‘Ｐｔｅｃ－ｓｊｏ【－一旦可广

三ｐｒｅｅｉｓｉｏｎ；

（７）

｝Ｃ｝

Ｍ一小２苛

∑Ｆ１。

．（８）

如图１—３所示，ｃＣ和Ｃｍ在提取的文本特征向量维数为

１５００维时，分类效果最优；ｓＰ在提取的文本特征向量维数为ｌ

５００维时，分类效果最优；ＤＦ在提取的文本特征向量维数为３

０００维时，分类效果最优。ＣＣ、ｃＨＩ、ＳＰ在分类效果达到最优

时，Ｍａｒｃｏ．Ｒｅｃａｌｌ、Ｍａｒｃｏ．Ｐｒｅｃｉｓｉｏｎ、Ｍａ”ｏ．Ｆ１二项评价指标数值相当，ＤＦ效果最差。

特征词数目特征１同数目

图２宏平均查准率对比图３宏平均Ｆ１值对比

当提取的文本特征向量维数为３００维时，ｓＰ的分类效果远好于Ｃｃ、ｃＨＩ和ＤＦ，此时Ｍａｒｃｏ－Ｒｅｃａｌｌ＝０．８８６７，Ｍａｒｃｏ—Ｐｒｅ—ｃｉｓｉｏｎ＝０．８８９４，Ｍａｒｃｏ．Ｆｌ＝０．８８５８。通过观察可知，在一定范围内，随着文本特征向量维数的增加，分类效果会逐渐提高，但是当文本特征向量维数超过一定数值时将趋于平稳甚至下降，同时提高了计算代价。虽然ＳＰ在提取的文本特征向量维数为

２

０００时分类效果最好，此时Ｍａｒｃｏ—Ｒｅｃａｌｌ＝０．８９３３，Ｍａｒｃｏ—Ｉｈ—

ｃｉｓｉｏｎ＝Ｏ．８９６５，Ｍａｒｃｏ—Ｆｌ＝０．８９３２，但是通过与ｓＰ提取的文本特征向量维数为３００维的分类效果作比较，发现其提高的分类性能很有限。由以上分析可知，ｓＰ提取的文本特征向量维

数为３００维，即特征降维达到９９．４８％时，已经使ＫＮＮ具有一个良好的分类效果，可以有效对未知文本进行分类。

通过实验结果可知，ｓＰ通过提取高质量的特征词，构造低维的特征向量，能够有效地降低特征空间维度，并且有效地表示各个类别的文本，反映了类别间的差异度。实验结果表明该方法应用在ＫＮＮ分类算法上分类效果良好。

５结束语

本文提出一个新的基于类别正相关和类别强相关的新特征提取方法ｓＰ。与传统方法相比，该方法能够充分利用特征项在文本集合中的分布统计信息选择与文本类别正相关并且强相关的特征。该方法在降维能力上有突出表现，实验中在保证良好分类效果的情况下．可对经过预处理后的特征向量进行高达９９．４９％的降维，整体评价指标上表现优于ＤＦ方法，降维能力、

第５期林少波，等：基于类别相关的新文本特征提取方法

・１６８３・参考文献：

【８１

ＹＡＮＧＹｉ—ｍｉｎｇ，ＰＥＤＥＲｓＥＮｊＯ．ＡｃｏｍＰ甜砒ｉｖｅ

ｓｔｕｄｙｏｎ耗ａｔｕｒｅ

ｓｅ・

［１］ｏＧｕＲＡＨ，ＡＭＡＮｏＨ，ＫｏＮＤ０

Ｍ．Ｆｅａｔｕｒｅ

ｓｅｌｅｃｔｉｏｕｗｉｔｈ

ｌｅｃｔｉｏｎｉｎ

ｔｅｘｔ

ａ

ｍｅ踮ｕ砷

ｃａｔｅ９０ｄｚ撕ｏｎ［ｃ］／／Ｐｒｏｃ０ｆｔｈｅ１４ｔｈｈｌｔｅｍａｔｉｏｎａｌＣｏｎ—

ｏｆｄｅｖｉａｄｏｎｓｆｍ珊Ｐｏｉ８ｓｏｎｉｎｔｅｘｔ

ｃａｔｅｇｏｄｚａｔｉｏｎ［Ｊ］．Ｅｘｐｅｎｋｌ＿ｅｎｃｅ

ｏｎ

ＭａｄｕｎｅＳｙＳｔｅｒｎｓ

ＬｅａｒＩｌｉＩｌｇ．Ｓａｎ

ＦＩｍｌｃ诘ｃｏ：Ｍ叫ｇａｎ

Ｋａｒｌｈｎａｌｌｌｌ，

ｗｎｈ

Ａｐｐ｛ｉｃａｔＩｏｎｓ，２００９，３６（３）：６８２６—６８３２．

１９９７：４１２—４２０．

［２］李荣陆．吏本分类及其相关技术研究［Ｄ］．上海：复旦大学，

［９］

ｃｕＩｚｉ—ｆｅ“ｇ，ｘｕＢ舶－ｗｅｎ，ｚＨＡＮＧｗｅｉ—ｆｅｎｇ，讲Ⅱｆ．Ａｎｅｗ印ｐｒｏａｃｈ

２００５．

ｔｏ

ｆｅａｔｌｌｒｅｓｅｌｅｄｉｏｎｆ研ｔｅｘｔ

ｃａｔ。ｇｏｄｚａ６０ｎ［Ｊ］．ｗｕｈａｎＵｎｉＶｅ瞧时

［３］

ｗＡＮＡｓＮＭ．ｓＡＩＤＤＡ，ＨＥＧＡｚＹ

ＮＨ，ｄｏｆ，Ａ髓ｕｄｙ

ｏ￡ｋａｌ

ａ耐

ＪｏｕｍａｌｏｆＮａｔｕｒａＩ

Ｓｃ｜ｅＩ℃ｅｓ，２００６，１（５）：１３３５一１３３９，

ｄｏｂａｌｔｈ比ｓｈ０１ｄｉ【ｌｇｔｅｃｈｎｌｑｕｅｓ

ｌｎｔｅｘｔ

ｃａｔ。ｇｏｎｚｍＪｏＩｌ［ｃ］／／ｆ．ｍｃ

ｏｆｌｌｌｅ

［１０］ＧＡＬＡＶｏＴ兀Ｌ，ｓＥＢＡＳｌｌＡＮｌＦ，ｓＩＭＩ

Ｍ．Ｅｘｐｅｒｉｍｅｎｔｓｏｎ

ｔｈｅｕｓｅ０ｆ

５ｔｈ

Ａｕｓｔ谢器ｉ粕ｃｏｒ血ｒｅｎｃｅ帆ＤａｔａＭｉｎｉ“ｇ卸ｄＡｎａｌｖｓｔｉｃｓ．Ｄａｄｉｎ｝

ｆｅａｔｕｒｅｓｅｌｅｃｔｉ衄ａＩｌｄｎｅｇ撕ｖｅｅｖｉｄｅｎｃｅ

ｉｎ

ａｕｔｏｍａｔｅｄ

ｔｅ俎ｃａｔｅ９０ｒｉｚａ—

ｈｕｒｓｔ，Ａｕｓ叫ｉａ：Ａｕ８训№Ｃｏ“ｐｕｔｅｒＳｏｃＩｄｙ，２００６：９Ｌ—１０１．

ｕｏｎ［ｃ］／／Ｐ㈣ｏｆ

ｔｈｅ４ｔｈ

Ｅｕ坤ｐｅａｎ

ｃｏ出鼢蹴ｏＢ凰孵玳ｈ

ａｎｄＡｄ—

［４］

ＴＪ

ｓｈｏｕ－ｓｈａｎ，ｘＩＡＲｕｉ，ｚＯＮＧｃｈｅ“ｇ—ｑｊｎｇ，甜ⅡｆＡ如ｍｅｗｏｒｋ０ｆｋａ—

ｖａｎｃｅｄ

ＴｅｃｈⅡｏｌｏｇｙｆｏｒＤ酶ｔａｌ“ｂｒ蕊ｅｓ．Ｌ０ｎｄｏｎ：ｓＰ血ｇｅ卜Ｖｅｒｌ日ｇ，

ｔｕｒｅ

ｓｅｌｅｃ在衄ｍｅｔｈｏｄｓｆｏｒ

ｔｅｘｔ

ｃａＩｅｇｏ缸ｚａｔｉ∞［ｃ］／／ｆ＿Ｄｃ

０ｆｔｌｌｅ４７山

２０（）【Ｉ１５９—６８．

Ａ卫ｎｕ８Ｉ

Ｍｅｅｄｎｇ

０ｆｍｅＡＣＬ蚰ｄｔ｜Ｉｅ４ｔ｜ｌＩｎｔｅ工ｌｌａｔｉｏｒ试Ｊ０ｍｔ

Ｃｏ赶ｅＩ邗ｃｅ

［１１］ｚＨＥＮＧｚｈａｏ－ｈｕｉ，ｗｕｘｉ舳一弘ｎ，ｓＲＩＨＡＲＩ

Ｒ

Ｆｅａｔｌ腿ｓｅＬ比ｔｉｏｎ

ｆｏｒ

帆Ｎａ【ｕｒａｌ

ｋｇｕａｇｅ

Ｐｒｏｃｅｓｓｉ“ｇ

０ｆｔ｝Ｉｅ

ＡＦＮ口．Ｓ咖ｕｄｓｂ“增，ＰＡ：Ａｓｓ【卜

ｔｅｘｔ

ｃａｔｅ９０五ｚａｔｉｏｎ

ｏｎ

ｉｌｎｂａｌａＩｌｃｅｄ

ｄａｔａ［Ｊ］．ＳＩＧＫＤＤＥｘｐｌｏｒａｔｉｏｎｓ，

ｃｉａｔｉｏｎ

ｆｏｒ

Ｃｏｍｐｕｔａｔｉ伽ａｌ

ｈｇＬｌｉ８ｎｃｓ，２００９：６９２－７００．

２００２，６（１）：８０＿８９．［５］ＬＩｕＨｕａ—ｗｅｎ，ｓｕＮＪｉ—ｇｕｉ．ＬＩＵＬｅｉ，ｅ＃甜．Ｆｅａｔｕｒｅｓｅｌｅｃｔｉｏｎｗｉｔｈｄｙ—

［１２ＪＨ０ｗ

Ｂ

Ｃ，ＮＡＲＡＹＡＮＡＮＫ．Ａｎｅｍｐｉｒｉｃａｌｓｔｕｄｙｏｆｆｅａｔｕｒｅｓｅｌｅｃ吐ｏｎ

ｎａＩｎｉｃ

ｍｕｔｕ越ｉ幽瑚ａｔｊ咖【ｊ］．Ｐａ№ｍＲｅｃｏｇｎ惜ｏｎ，２００９，４２（７）：

ｆｏｒ

ｔｅｘｔｃａｔｅｇｏｎｚａｈｏｎ

ｂ鹅ｅｄ

ｏｕ

０ｆＩＥＥＥ／

１３３０．１３３９

ｔｅ珊ｗｅｉｇｌｌｔ孵［ｃ］／／Ｐｒｏｃ

ＷＩＣ／ＡＣＭＩｎｔｅＩＩｌａｔｉｏｎａｌＣｏｎｆｂｒｅｎｃｅ

ｏｎ

［６］

肖婷，唐雁．改进的，统计文本特征选择方法［Ｊ】，计算机工程与

Ｗ曲Ｉｎ瞄ｌｉｇｅｎｃｅ．Ｗａｓｈｉｎｇ【０“

ＤＣ：ＩＥＥＥ

应用，２００９，４５（１４）：１３６一１３７，１４０、ＣｏｍｐｕｔｅｒＳｏｃｉｅｌｙ，２００４：５９９－６０２．Ｌ．Ｆ锄ｕ工ｅＧｗ

Ｆ色ａｔｕ代ｓｅｌｅｃｔｉｏｎ

［７］

ＮＧ

ＨＴ，ＧＯＨｗＢ，ＬＯｗＫ

８ｅｌｅｃｔｉｏｎ，ｐｅｒｃｅｐ咖ｎｌｅ邪ｉＩｌｇ，

［１３］ｓＯｕｃＹ

Ｐ，ＭＩＭＥＡｕ

ｓｔｒａｔｅ奇ｅｓｆｏｒ

ｔｅｘｔ

ｃａ咏。一

ａＩｌｄ

１６ｔ｝ｌｃ如ａｄｉａｎａ

ｌｌｓａｂｉｌｉｃｙｃ船ｅｓｔｕｄｙｆｏｒｔｅ砒ｅｍ锷０ｒｉ跄ｔｉ∞［Ｃ］／／Ｐ妣０ｆｔｌｌｅ２０ｔｌｌ

出出ｏｎ［ｃ］／／Ｐｍｃｏｆｔｈｅｓｏｃｉｅ‘ｙｈｃｏｍｐｕＬａｔｉ佃ａｌ

ＡｎｎｕａｌＩｎｌｅｍａｔｉｏｎａｌＡＣＭＳＩＣＩＲＣｏｒｄ毫ｒｅｎｏｅｏｎＲｅ８ｅａｒｃｈａｎｄＳｔｕｄｉｅｓ

ｏｆ

ｉｎＡｒｔｍｃａＪＩｎｔｅｌｌｉ・

Ｄｅｖｅｌｏｐ－

ＩｎｔｅｌｌｌｇｅｎｃｅＣｏｎｆｅｒｅｎｃｅ

０Ｉｌ

ＡｄⅧｃｅｓ

ｍｅｎｔｉｎ

ｈｌｆｏｎｍｔｉｏｎ

Ｒ“删ａ１．ＮｅｗＹｏｒｋ：ＡＣＭ．１９９７：６７－７３．

ｇｅｎｃｅ．ＢｅｒＩｉ“：Ｓｐ曲ｇｅｒ—Ｖｅｒｈｇ，２００３：５０５—５０９．

（上接第１６７２页）数，如设定为１００，这样如果没有低于或等于快、全局搜索能力强，对于求解大规模优化问题具有其优越性。】７０的最优值，进化到１００代也停止进化，输出１００代中得到的参考文献：

最优结果。

［１］王勇，毛海军，刘静，等．带时间窗的物流配送区域划分模型及其

根据以上设定，采用自适应遗传算法（即采用自适应策略算法［Ｊ］．东南大学学报：自然科学版，２０ｌｏ，４０（５）；１０７７一１０８３．的遗传算法）进行计算，获得最后的解决方案，最优的行程总［２］雷胜华．城市物流配送车辆调度问题的研究与应用［Ｄ］，北京：北

长度为１６２，把运行停止判断条件中的最优值判断参数设为京工业大学．２０ｌＯ．１７６，进化代数判断参数设为１００，其他设置不变。运行２０次，［３］ＴＳＥＮＧ

Ｌ

Ｙ，ｕＮ

Ｙ

Ｔ．Ａ

ｈｙｂ砌ｇｅ凹ｔｉｃＩｏｃａｌｓｅ锄ｈａ【９０＾ｃｈｍｆｏｒｔＩｌｅ

结果如表３所示。

ｐｃｍｕｔａｔｉｏｎｎｄｗｓｈｏｐｓｃｈｅｄｌｌｌｉｎｇｐｒｏｂｌｅｍ［Ｊ】ＥｕｒｏｐｅａｎＪｏｕｍａＩｏｆ

表３多次运行结果比较

０ｐｅｒａｔｉｏｎａｌ

Ｒｅｓｅａｒｃｈ，２００９，１９８（１）：８４－９２

［４］王洋．范剑英，林立军，等．物流配送路径优化理论在立体匹配技

术中的应用研究［Ｊ］．哈尔滨理工大学学报．２０１１，１６（２）：２４—２８．［５］廖洁君，陈燕．配送调度优化模型的研究及应用［Ｄ］大连：大连

海事大学，２‘）０５．

比较以上分析数据，可以说明本文采用的自适应遗传算法［６］张维泽，林剑波，昊洪森，等．基于改进蚁群算法的物流配送路径

所得到的解决方案优于采用基本遗传算法所得到的解决方案。

优化［Ｊ］．浙江大学学报：工学版，２００８，４２（４）：５７４－５７８．４结束语

［７］

ＹｕＥＮ

ｓＹ，ｃＨ０ｗｃＫ．Ａｇｅｎｄｉｅａｌｇｏ血ｈｍｔｈａｔａｄ叩ｔｉｖｅｌｙ

ｍｕｔａｔｅｓ

锄ｄ

ｎｅｖｅｒ斟商ｔｓ【Ｊ］．１ＥＥＥ

Ｔｒａｎｓ

ｏｎ

ＥＶｏｌｕ苗ｏｎａｒｙＣｏｍｐｕｔａｔｉｏｎ，

本文针对配送运输的一般问题，提出了优化配送的运送距２００９，１３（２）：４５４－４７２．

离来对物流配送问题进行寻优。在考虑实际情况下，引入』，多［８］胡祥培，于楠，丁秋雷，等．物流配送车辆的干扰管理序贯决策方

货物的配送情况，分析了物流配送抽象流程，以求取优化配送法研究【Ｉ］，管理工程学报，２０ｌｌ，２５（２）：１８６ｉ９０．

效率、降低算法的时间和空间复杂度为目标，设计了基于自适［９］晏梦君，陈震遗传算法在配迭优化系统中的应用［Ｄ］，长春：吉

应的多类型物流配送改进遗传算法。将基于自适应遗传算法林大学，２００７．

的多类型物漉配送优化算法应用到实际物流配送过程中，针对［１０】孙丽君．基于畅通可靠性分析的癌。市物渡配送网络优化研究

处理结果进行科学评价。

［Ｄ］．长沙：长沙理工大学，２０１０

与采用的基本遗传算法得到的解决方案相比，实例仿真的［１１］朱晓锋，蔡延光物流配送的优化模型及算法在连锁企业中应用

结果表明，本文采用的自适应遗传算法求解效率高、收敛速度

［Ｊ】．电子学报，２０１１，９（１）：１４—１７．

第２９卷第５期２０１２年５月

计算机应用研究

ＡｐｐｌｉｃａｔｉｏｎＲｅｓｅａｒｃｈｏｆＣｏｍｐｕｔｅｒｓ

Ｖ０１．２９Ｎｏ．５

Ｍａｖ２０１２

基于类别相关的新文本特征提取方法

林少波，杨丹，徐玲

（重庆大学软件学院，重庆４０００３０）

摘要：为了避免文本特征提取过程中负相关特征与弱相关特征产生的干扰，提出一个新的基于类别正相关并口

强相关（ｓＰ）的特征提取方法。通过结合正相关性因子和强相关因子，ｓＰ方法能够有效地区别特征与类别正负相关性和强弱相关程度，通过优先选择正相关和强相关特征，避免了负相关和弱相关特征的干扰，从而有效地提

取高质量的文本特征。实验结果表明，该方法具有强降雏能力和良好的分类效果。关键词：正相关；强相关；文本分类；特征降雏；特征提取中图分类号：ＴＰ３９１

文献标志码：Ａ

文章编号：１００１—３６９５（２０１２）０５—１６８０一０４

ｄｏｉ：１０．３９６９／ｉ．ｉｓｓｎ．１００１．３６９５．２０１２．０５．０２１

Ｎｅｗａｐｐｒｏａｃｈ

ｔｏ

ｆｅａｔｕｒｅｓｅｌｅｃｔｉｏｎｆｏｒ

ｔｅｘｔ

ｃａｔｅｇｏｒｉｚａｔｉｏｎｕｓｉｎｇｃｌａｓｓｃｏｒｒｅｌａｔｉｏｎ

ＵＮＳｈａｏ＿ｂｏ，ＹＡ“ＧＤａｎ，ＸＵＬｉｎｇ

（ｓ旃剐矿ｓ妒ｍｍ西洒Ｍ＾昭，矾ｏ，啪蛔№妇ｍ蚵，‰“卯ｉｎｇ４０００３０，肌￡ｍ）

Ａｂｓｔ瑚ｃｔ：Ｔｈｉｓｐ印ｅｒｐｍｐｏｓｅｄ

ｃｏｒｒｅｌａｄｏｎａｎｄｐｏｓｉｔｉｖｅｃｌａｓｓ

ａ

ｎｅｗ印ｐｒｏａｃｈｏｆｆｅａｔｕｒｅｓｅｌｅｃｔｉｏｎｆｏｒｔｅｘｔｃａｔｅｇｏｒｉｚａｔｉｏｎ，ｗｈｉｃｈ

ｗａｓｂａｓｅｄ

ｏｎ

ｔｈｅｓｔｒｏｎｇｃｌａｓｓ

ｃｏｎ．ｅｌａｔｉｏｎ，ｎ砌ｅｄ

ＳＰ．ＳＰｃｏＩｌｌｄｅｌｉｍｉｎａｔｅｔｈｅｅｆＥｂｃｔｏｆｎｅｇａｔｉｖｅａｎｄｐｏｏｒｃｏｎ℃１ａｄｏｎｆｅａｔｕｒｅｅⅡｂｃｔ－

ｔＩｌｅｎｅｇａｔｉｖｅｂｙｐｏｓｉｔｉＶｅｃｏｒｒｅｌａｔｉ蚰ｆａｃｔｏｒ－．ａＩｌｄｅｌｉ商ｎａｔｅｄｔｈｅ

ｅＨｋｃｔ０ｆｎｅｇａｄｖｅｆｂａｔｕｒｅ．ＳＰｄｉｓｃｒ主ｌＩｌｉｎａｔｅｄｂｅｔｗｅｅｎｔｈｅｓｔＩＤｎｇｃｌａｓ８ｏｆｆｅａｔｕｒｅｓａｎｄｔｈ。ｐｏｏｒｃｌａｓｓｃｏｒｒｅｌａｔｉｏｎｏｆｆｅａ・ｔｕｒｅｓｂｙｐｏｓｉｔｉｖｅｃｌａｓｓｃｏｒｒｅｌａｔｉｏｎｆａｃｔｏｒ，ａｎｄｅｌｉｍｉｎａｔｅｄｔｈｅ雒ｂｃｔｏｆｐ００ｒｃｏ玎ｄａｔｉｏｎｆｅａｔｕｒｅ．ＳＰｃｏｕｌｄｓｅ】ｅｃｔｈｉｇｈｑｕ８１ｉｔｙｆｅａ—ｔｕｒｅｓｅⅡｂｃｔｉｖｅｌｙｂｙｃｏｍｂｉｎｉｎｇｔｌｌｅｓｅｔｗｏｆａｃｔｏｒｓ．ＴｈｅＴｅｓｕｈｏｆＥ１ｐｅｒｉｍｅｎｔｉｎｄｉｃａｔｅｓｔｈａｔｔｈｅｐｒｏｐｏｓｅｄ印ｐｍａｃｈｈａｓａｇｏｏｄｐｅｒ－ｌｙ．ＳＰｄｉｓｃｒｉｍｉｎａｔｅｄｂｅｔｗｅｅｎｔｈｅｐｏｓｉｔｉｖｅ

ｆｅａｔ岍ａｎｄ

ｋｔｕｒｅｃｏｒｒｅ№ｏｎ

ｆｏ咖ａｎｃｅ

ａｔ

ｃａｔｅｇｏｒｉｚａｔｉｏｎａｎｄｒｅｄｕｃｉｒｌｇｈｉｇｈｄｉｍｅｎｓｉｏｎａｌ侣ａｔⅡｒｅ８ｐａｃｅ．

Ｋｅｙｗｏｒｄｓ：ｐｏｓｉｔｉｖｅｃｏｎ℃ｌａｔｉｏｎ；ｓｔｍｎｇｃｏｒｒｅｌａｔｉｏｎ；ｔｅｘｔｃｌａｓｓｉｆｉｃａ石ｏｎ；ｆｅａｔｌｌｒｅｒｅｄｕｃｔｉｏｎ；ｆｅａｔｕｒｅｓｅｌｅｃｔｉｏｎ

特征子集，以达到降低特征空问维度的目的。在特征选择过程

Ｏ引言

文本自动分类是在给定分类体系的情况下，根据预定义类别中的文本数据信息总结归纳出分类的规律性，根据这个规律性将未标明类别的文本映射到预定义的类别¨Ｊ。

现有文本分类技术通常有两种文本表示模型，即布尔模型和向量空间模型嵋１。向量模型中特征向量与文本集合中的文本一一对应，将文本集合中的词条作为向量中的特征项。布尔模型可以看做是向量模型的一种特例，根据特征项在文档中出现与否，特征项的权值只能取ｌ或ｏ。布尔模型不能很好地体现文本特征的重要程度，通常情况下布尔模型的效果不如其他模型。ＩｆＩｉ向量空间模型是一种不考虑词与词之间的上下文关系、出现的顺序和位置以及文本长度的词袋（ｂａｇ

ｏｆ

中不包括任何学习算法。特征提取通过对特征向量空间的降维，不仅提高了分类速度，而且过滤ｒ噪声数据，在提高精度的同时还有助于解决过拟合问题。

现有的特征提取方法包括文档频数（ｄ∞ｕｍｅｎｔ“ｑｕｅｎｅｙ，ＤＦ）、信息增益（ｉｎ南ｍ撕ｏｎｇａｉｎ，ＩＧ）、互信息（ｍｕｔｕａｌ

ｉ山ｍａ．

ｔｉｏｎ，ＭＩ）、ｒ统计（ｃｈｉ－ｓｑＩｌａｒｅｓｔａｔｉｓｔｉｃ，ｃＨＩ）和ｃｃ（ｃ０Ｈｅｌａｔｉｏｎ

ｃｏｅｍｃｉｅｎｔ）等Ｈ“。。目前ＣＨＩ和ＩＧ性能较好，ＤＦ和ＭＩ性能较差＂’。Ｃｃ是基于相关系数的特征提取方法，是ＣＨＩ公式的开平方式。两者的区别是，ｃＨＩ评价函数计算得到特征值具有非负性，等同了正相关和负相关特征的对文本分类的重要性，而ｃｃ通过对ＣＨＩ公式的开平方，使得特征值具有正负性，区别了正相关和负相关特征对文本分类的重要件。８Ｊ。文献［９］使用选择带有较强类别信息的特征词，在线性分类器上有较好的准确率。文献［１０］指出对于文本分类而言，特征的重要性主要由特征的正相关能力决定。过多地考虑特征项与类别的负相关度，不仅不能提高分类的精度，还可能对分类结果产生干扰。

本文提出了一种基于类别正相关和类别强相关的新特征提取方法ＳＰ。该方法只选取与类别正相关和强相关的特征。

ｗｏｒｄｓ）文

本表示模型。故本文选择向量空问模型作为文本表示模型。

针对文本分类中文本特征向量空间的高维性问题，采用特征提取方法进行特征降维。，该方法是基于过滤模型ｐ１的一种特征选择方法，过滤模型的基本思想是根据训练集数据的一般特性进行特征选择，通过构造某种特征评价函数，来统计文本特征空问中各个特征项的值，将各个特征项按其特征值排序，并根据设置的阈值选择出合适规模的对文本分类贡献较大的

收稿日期：２０１１—１０—２０；修回日期：２０１１．１１—３０

（ＣＳＴＣ２００９ＡＢ２２３０）

基金项目：国家自然科学基金资助项目（６０９７５叭５）；重庆市重点攻关资助项目

作者简介：林少波（１９８６一），男，福建莆田人，硕士研究生，主要研究方向为文本分类、企业信息化及电子政务（ｈｎｓｈａｏｂ０１２３＠１２６ｃｏｍ）；杨丹（１９６２一），男，重庆云阳人，教授，博导，博士，主要研究方向为图像处理、模式识别、机器学习；徐玲（１９７５一），女，安徽庐江人，讲师，博士，主要研究方向为数据挖掘、图像处理

第５期

林少波。等：基于类别相关的新文本特征提取方法

・１６８１・

首先给出特征与类别相关性和相关度的概念，通过对ｃＨＩ不能区别正相关特征与负相关特征重要程度的原因分析，将文本特征与类别正、负相关特征的重要性差异度作为正相关性因子，用来区别特征与类别正负相关性。通过对文本特征在文本集合中分布规律的分析，将文本特征类内和类间的相关度指标结合成为强相关度因子，用来区别特征与类别的强弱相关度。

１

ｂ）若存在一个特征词，在当前所在类别内，包含该特征词的文档在该类别中比例越高越能代表当前类别，对分类贡献越大。将衡量类内特征分散度的指标称为相关度的类内指标。

在此采用两种比值表示相关度的类间指标和类内指标：

ａ）舍。如果特征词“只与类别ｃ。相关度高，舍值越高，

』

特征与类别的相关性

特征与类别的相关性包括正相关性和负相关性。为了更

那么说明特征词ｌ。能很好地代表类别ｃ。，那么詈的值就高。

ｂ）≠。在类别ｃ。中有两个特征词ｋ和‘。，它们各自对应ｕＩ

好地描述特征与类别的正负相关陛概念，这里将通过对文本集

合的一般特性的分析，具体地描述特征与类别的正负相关性。文本集合这种特性可以由表１中四种基本元素４、曰、ｃ、口表示。为进一步解释，现作以下假设：在一个文本集合日中，假设存在一个类别ｑ，集合中除ｃ。以外的类别表示为ｃ。，则按照文本所属类别划分，该集合日可以表示为ｈ，ｃ。｝。假设存在一个文本特征词ｚ；，集合中除ｔ。外的特征词表示为缸，则按照是否包括特征词屯划分，该集合日可以表示为ｈ，“｝。按照文本是否包括特征词“，是否属于类别ｃ。，可将文本集合日表示为ｈ，ｃ；｝和ｈ，￡。｝的笛卡尔乘积。该集合由表ｌ所示的四个信息元素Ａ、曰、Ｃ、Ｄ构成。

表１信息基本元素表

一个务值，那么争值越大的特征词越能代表类别‰

鉴于以上概念的提出，结合类间指标和类内指标来刻画特征与类别的相关程度，区别强、弱相关特征。将特征与类别的强相关度因子ｓｃＤ（ｓ咖ｎｇｃ０Ⅱｅ１．ａｔｉｏ口ｄｅ孕ｅｅ）表示为

ｓｃＤ（％ｃ。）２蔼

＾

一

（１）

若一个特征与一个类别相关度越强，则ｓｃＤ值越大。ｓｃＤ优先选择与类别强相关的特征，从而能够有效地避免弱相关特征产生的噪声干扰。

３

ＳＰ文本特征提取方法

基于以上文本特征与类别的相关性和相关度的概念的提

ｅ￡

ＢｌＤ．

出，采用强相关度因子ｓＣＤ来区别特征与类别相关度的强弱，并对ｃＨＩ无法体现正相关特征与负相关特征的重要性差异度的原因进行分析，寻求特征与类别间的正负相关性的具体表示

表１中，Ａ。＝‰，ｃ，）表示不仅包含特征靠而且属于类别ｑ

的文本数量；Ｂ；＝（“，ｃ。）表示包含特征‘但是不属于类别ｃ。的文本数量；ｃ。＝（“，ｑ）表示不包含特征屯但是属于类别ｑ

方法。

ｃＨｌ统计方法是在数理统计中一种常用的检验两个变量独立性的方法。ｃＨＩ最基本的思想就是通过观察实际值与理论值的偏差来确定理论的正确与否。其运用在文本特征选择中，假设“与类别ｃ。之间是独立的”“。这种独立关系类似于

的文本数量；Ｄｊ＝瓴，ｑ）表示不包含特征ｔ。并且不属于类别ｃｆ

的文本数量。文本总数量Ⅳ＝Ａ＋Ｂ＋ｃ＋Ｄ。

基于表ｌ的描述，将特征选择方法根据特征与类别的相关性进行分类，包括正相关性和负相关性”…。

定义ｌ若特征项“当且仅当只出现在与类别ｑ相关的文本中，则称特征项‘。与类别ｃ。正相关。

定义２若特征项￡。当且仅当只出现在与类别ｑ不相关的文本中，则称特征项缸与类别ｃ。负相关。

表ｌ中Ａ。＝（“，ｃ。）和Ｄ；＝（屯，ｃ；）描述的是特征项气和类别ｑ的正相关程度，段＝（气，ｑ）和ｃ；＝（靠，ｃ；）描述的是特征项“和类别ｃ。的负相关程度。

具有一维自由度的，分布，九对于ｃ；的ｃＨＩ统计量为

．

ⅣｆｄＤ—ＢＣ、２

矿（‰ｑ）２瓦了两面膏面可等南面了可

（２）

ｃＨＩ统计方法用ｒ（靠．ｃ．）来度量特征项屯和类别ｃ。之间的相关程度。ｒ（＃。，ｃｉ）值越大说明特征项缸和类别ｃ，相关程

度越高，此时特征项“所包含的与类别ｃ：相关的信息就越多。

∥（１。，ｃｉ）＝ｏ表示特征项屯与类别ｃ；相互独立。特征项“与类别ｑ的相关陛越强掰２（靠，ｅ；）的值就越大。特征性选择的过程就是计算特征项ｋ和类别ｃ：的，（屯，ｃ；）值，然后按值大小

排序，根据实际需要选取ｃＨＩ值大的特征项。

由定义ｌ和定义２可知，Ａ；和Ｄ。描述的是特征项屯和类别ｃ。的正相关程度，曰。和ｃ。描述的是特征项“和类别ｃ，的负相关程度。由概率论可知，假设Ａ。的值越大，Ｄ。的值越大，即特征屯出现在ｃ；类的文本里丽的概率越大，则ｆ。与ｃ；正相关度越大。假设置的值越大，ｃ。的值越大，那么特征“出现在类别ｃ。的概率越大。

Ａ；Ｄ；一Ｂ；ｃ；体现了特征ｋ与类别ｃ；的正、负相关特征重要性差异度。若Ａ。Ｄ。一日．Ｇ；＞０，则特征“与类别ｃ；体现出正相关性；若Ａ。Ｄ；一丑；ｃ。＜Ｏ，则特征“与类别ｃ。体现出负相关

２特征与类别的相关度

特征与类别的相关度可分为强相关和弱相关。在此结合本文第ｌ章的文本集合一般性描述来进一步阐述特征与类别的相关度概念。特征的相关度是衡量一个特征代表一个类别的程度。特征与类别的相关度评价可以基于以下两种指标：

ａ）若存在一个特征词，该特征词越集中出现在当前所在类别文档中，在其他类别文档中越少出现，那么这个特征词越

能区别所在类别与文本集合中的其他类别。即该特征词越能

代表当前类别，对分类贡献越大。这里将衡量类别问特征分散度的指标称为相关度的类间指标。

性。由式（２）可知，分子中（Ａ；Ｄ。一ＢｉＧ）ｊ使得４。Ｄ。一曰。ｃ。呈现

・１６８２・

计算机应用研究

第２９卷

非负性，若特征“与类别ｃ；体现出正相关度越大，那么Ａ。Ｄ。一层ｃ。必然为正值，且值将随正相关度的增加而增大，ｃＨＩ得出的特征值也将增大。若特征“与类别ｃ。体现出负相关性，那么Ａ。Ｄ；一占。ｃ．必然为负值，而且值随着负相关度的增加而减小，但是（Ａ。Ｄ。一曰。ｃ。）２的值将随之变大，ｃＨＩ得出的特征值也将变大。这样正、负相关特征的重要性差异度便无法体现。

通过以上分析，正、负相关特征重要性差异度能很好地刻画文本特征与类别的正负相关性。假定用正相关性因子Ｐｃ（ｐｏｓｉｔｉ”ｃｏｒｒｅｌａｔｉｏｎ）来区别特征与类别间的正负相关性，则

Ｐｃ（“，ｃ；）＝一。Ｄ。一吼ｃ。

（３）

新文本特征提取方法的目的是选择与类别正相关并且强

．相关的特征词。综上所述，提出新的文本特征提取方法ｓＰ

（ＳＣＤ＆ＰＮＣ）：

＾Ａ

一，）

５Ｐ（‰ｑ）２

ｓｃＤ。９ｃ

２蔼（４ｔＤｆ一日ｔｃｔ）２‘蔬‘１）《（４）

著一个特征词与类别正相关并且强相关，那么ｓＰ值一定越大，故ｓＰ优先选择与类别正相关并且强相关的特征词。

文本特征提取策略可以分为局部和全局特征提取。文献［１２］指出在均衡数据中，全局特征提取优于局部特征提取，单独利用局部特征提取的缺点是它不能有效地选取到能代表所有类别的特征集合，忽视了全体训练样本和类别的整体性。文献［１３］指出在偏斜数据集中使用加权局部特征选择优于全局特征，因为偏斜数据中各个类别问文档数量差距很大，基于全局提取的特征集合不能代表少数类。本文使用均衡数据集，采用全局特征提取策略。

基于全局特征提取策略的特征提取方法，需获取特征项“对整个文档集的全局特征值时，由于ｓＰ是基于类别正相关性与强相关性的特征提取方法，采用式（５）基于最大值的方式计算全局特征，度量各个特征对于分类的重要性，能够选择出对某一个类具有较好标志作用的特征项。

ｓＰ…（“）＝ｍ“｛ｓＰ（“，ｑ）｝

（５）

ＳＰ特征提取方法的优点在于：计算复杂度低，只选择与类别正相关并且强相关的特征，避免了弱相关特征和负相关特征的干扰。

４实验结果及分析

本实验采用复旦大学计算机信息与技术系国际数据库中心自然语言处理小组的文本分类语料库…。该语料库共分为２０个类别，测试集共９８０４篇文章，训练集９８０４篇文章。本文从中抽取９个类别作为训练集，包括艺术、历史、航空、计算机、环境、农业、经济、政治、体育。在原训练集中每个类别随机抽取２００个训练文档，共计１８００个训练文档。在原测试集中每个类别随机抽取ｌｏｏ个测试文档，共计９００个测试文档。训

练文档和测试文档的比例为２：ｌ，通过预处理，测试文档包含

５７

７７１个特征词。

实验采用ＫＮＮ分类算法，实验效果的评价指标采用Ｍ”－

ｃｏ—ＲｅｃａＩｌ、Ｍａｒｃｏ—Ｐｒｅｃｉｓｉｏｎ、和Ｍａｒｃｏ—Ｆ１。式（６）～（８）分别表不宏平均查全率、宏平均查准率、宏平均Ｆ１值。其中ｒｅｃ丑１１。表示类ｃ。查全率，ｐｒｅｃｉｓｉｏｎ。表示类ｃ：查准率，Ｆｌｉ表示类ｃ：的Ｆ１法ｃＨＩ、ｃＣ、ＤＦ进行比较。

ｌＣｌ

∑ｒｅｃａｌｌｉ

ＭａｒｃｐＲｅｃａｌｌ

２苛

（６）

ＩＣｌ

Ｍ—ｕ‘Ｐｔｅｃ－ｓｊｏ【－一旦可广

三ｐｒｅｅｉｓｉｏｎ；

（７）

｝Ｃ｝

Ｍ一小２苛

∑Ｆ１。

．（８）

如图１—３所示，ｃＣ和Ｃｍ在提取的文本特征向量维数为

１５００维时，分类效果最优；ｓＰ在提取的文本特征向量维数为ｌ

５００维时，分类效果最优；ＤＦ在提取的文本特征向量维数为３

０００维时，分类效果最优。ＣＣ、ｃＨＩ、ＳＰ在分类效果达到最优

时，Ｍａｒｃｏ．Ｒｅｃａｌｌ、Ｍａｒｃｏ．Ｐｒｅｃｉｓｉｏｎ、Ｍａ”ｏ．Ｆ１二项评价指标数值相当，ＤＦ效果最差。

特征词数目特征１同数目

图２宏平均查准率对比图３宏平均Ｆ１值对比

当提取的文本特征向量维数为３００维时，ｓＰ的分类效果远好于Ｃｃ、ｃＨＩ和ＤＦ，此时Ｍａｒｃｏ－Ｒｅｃａｌｌ＝０．８８６７，Ｍａｒｃｏ—Ｐｒｅ—ｃｉｓｉｏｎ＝０．８８９４，Ｍａｒｃｏ．Ｆｌ＝０．８８５８。通过观察可知，在一定范围内，随着文本特征向量维数的增加，分类效果会逐渐提高，但是当文本特征向量维数超过一定数值时将趋于平稳甚至下降，同时提高了计算代价。虽然ＳＰ在提取的文本特征向量维数为

２

０００时分类效果最好，此时Ｍａｒｃｏ—Ｒｅｃａｌｌ＝０．８９３３，Ｍａｒｃｏ—Ｉｈ—

ｃｉｓｉｏｎ＝Ｏ．８９６５，Ｍａｒｃｏ—Ｆｌ＝０．８９３２，但是通过与ｓＰ提取的文本特征向量维数为３００维的分类效果作比较，发现其提高的分类性能很有限。由以上分析可知，ｓＰ提取的文本特征向量维

数为３００维，即特征降维达到９９．４８％时，已经使ＫＮＮ具有一个良好的分类效果，可以有效对未知文本进行分类。

通过实验结果可知，ｓＰ通过提取高质量的特征词，构造低维的特征向量，能够有效地降低特征空间维度，并且有效地表示各个类别的文本，反映了类别间的差异度。实验结果表明该方法应用在ＫＮＮ分类算法上分类效果良好。

５结束语

本文提出一个新的基于类别正相关和类别强相关的新特征提取方法ｓＰ。与传统方法相比，该方法能够充分利用特征项在文本集合中的分布统计信息选择与文本类别正相关并且强相关的特征。该方法在降维能力上有突出表现，实验中在保证良好分类效果的情况下．可对经过预处理后的特征向量进行高达９９．４９％的降维，整体评价指标上表现优于ＤＦ方法，降维能力、

第５期林少波，等：基于类别相关的新文本特征提取方法

・１６８３・参考文献：

【８１

ＹＡＮＧＹｉ—ｍｉｎｇ，ＰＥＤＥＲｓＥＮｊＯ．ＡｃｏｍＰ甜砒ｉｖｅ

ｓｔｕｄｙｏｎ耗ａｔｕｒｅ

ｓｅ・

［１］ｏＧｕＲＡＨ，ＡＭＡＮｏＨ，ＫｏＮＤ０

Ｍ．Ｆｅａｔｕｒｅ

ｓｅｌｅｃｔｉｏｕｗｉｔｈ

ｌｅｃｔｉｏｎｉｎ

ｔｅｘｔ

ａ

ｍｅ踮ｕ砷

ｃａｔｅ９０ｄｚ撕ｏｎ［ｃ］／／Ｐｒｏｃ０ｆｔｈｅ１４ｔｈｈｌｔｅｍａｔｉｏｎａｌＣｏｎ—

ｏｆｄｅｖｉａｄｏｎｓｆｍ珊Ｐｏｉ８ｓｏｎｉｎｔｅｘｔ

ｃａｔｅｇｏｄｚａｔｉｏｎ［Ｊ］．Ｅｘｐｅｎｋｌ＿ｅｎｃｅ

ｏｎ

ＭａｄｕｎｅＳｙＳｔｅｒｎｓ

ＬｅａｒＩｌｉＩｌｇ．Ｓａｎ

ＦＩｍｌｃ诘ｃｏ：Ｍ叫ｇａｎ

Ｋａｒｌｈｎａｌｌｌｌ，

ｗｎｈ

Ａｐｐ｛ｉｃａｔＩｏｎｓ，２００９，３６（３）：６８２６—６８３２．

１９９７：４１２—４２０．

［２］李荣陆．吏本分类及其相关技术研究［Ｄ］．上海：复旦大学，

［９］

ｃｕＩｚｉ—ｆｅ“ｇ，ｘｕＢ舶－ｗｅｎ，ｚＨＡＮＧｗｅｉ—ｆｅｎｇ，讲Ⅱｆ．Ａｎｅｗ印ｐｒｏａｃｈ

２００５．

ｔｏ

ｆｅａｔｌｌｒｅｓｅｌｅｄｉｏｎｆ研ｔｅｘｔ

ｃａｔ。ｇｏｄｚａ６０ｎ［Ｊ］．ｗｕｈａｎＵｎｉＶｅ瞧时

［３］

ｗＡＮＡｓＮＭ．ｓＡＩＤＤＡ，ＨＥＧＡｚＹ

ＮＨ，ｄｏｆ，Ａ髓ｕｄｙ

ｏ￡ｋａｌ

ａ耐

ＪｏｕｍａｌｏｆＮａｔｕｒａＩ

Ｓｃ｜ｅＩ℃ｅｓ，２００６，１（５）：１３３５一１３３９，

ｄｏｂａｌｔｈ比ｓｈ０１ｄｉ【ｌｇｔｅｃｈｎｌｑｕｅｓ

ｌｎｔｅｘｔ

ｃａｔ。ｇｏｎｚｍＪｏＩｌ［ｃ］／／ｆ．ｍｃ

ｏｆｌｌｌｅ

［１０］ＧＡＬＡＶｏＴ兀Ｌ，ｓＥＢＡＳｌｌＡＮｌＦ，ｓＩＭＩ

Ｍ．Ｅｘｐｅｒｉｍｅｎｔｓｏｎ

ｔｈｅｕｓｅ０ｆ

５ｔｈ

Ａｕｓｔ谢器ｉ粕ｃｏｒ血ｒｅｎｃｅ帆ＤａｔａＭｉｎｉ“ｇ卸ｄＡｎａｌｖｓｔｉｃｓ．Ｄａｄｉｎ｝

ｆｅａｔｕｒｅｓｅｌｅｃｔｉ衄ａＩｌｄｎｅｇ撕ｖｅｅｖｉｄｅｎｃｅ

ｉｎ

ａｕｔｏｍａｔｅｄ

ｔｅ俎ｃａｔｅ９０ｒｉｚａ—

ｈｕｒｓｔ，Ａｕｓ叫ｉａ：Ａｕ８训№Ｃｏ“ｐｕｔｅｒＳｏｃＩｄｙ，２００６：９Ｌ—１０１．

ｕｏｎ［ｃ］／／Ｐ㈣ｏｆ

ｔｈｅ４ｔｈ

Ｅｕ坤ｐｅａｎ

ｃｏ出鼢蹴ｏＢ凰孵玳ｈ

ａｎｄＡｄ—

［４］

ＴＪ

ｓｈｏｕ－ｓｈａｎ，ｘＩＡＲｕｉ，ｚＯＮＧｃｈｅ“ｇ—ｑｊｎｇ，甜ⅡｆＡ如ｍｅｗｏｒｋ０ｆｋａ—

ｖａｎｃｅｄ

ＴｅｃｈⅡｏｌｏｇｙｆｏｒＤ酶ｔａｌ“ｂｒ蕊ｅｓ．Ｌ０ｎｄｏｎ：ｓＰ血ｇｅ卜Ｖｅｒｌ日ｇ，

ｔｕｒｅ

ｓｅｌｅｃ在衄ｍｅｔｈｏｄｓｆｏｒ

ｔｅｘｔ

ｃａＩｅｇｏ缸ｚａｔｉ∞［ｃ］／／ｆ＿Ｄｃ

０ｆｔｌｌｅ４７山

２０（）【Ｉ１５９—６８．

Ａ卫ｎｕ８Ｉ

Ｍｅｅｄｎｇ

０ｆｍｅＡＣＬ蚰ｄｔ｜Ｉｅ４ｔ｜ｌＩｎｔｅ工ｌｌａｔｉｏｒ试Ｊ０ｍｔ

Ｃｏ赶ｅＩ邗ｃｅ

［１１］ｚＨＥＮＧｚｈａｏ－ｈｕｉ，ｗｕｘｉ舳一弘ｎ，ｓＲＩＨＡＲＩ

Ｒ

Ｆｅａｔｌ腿ｓｅＬ比ｔｉｏｎ

ｆｏｒ

帆Ｎａ【ｕｒａｌ

ｋｇｕａｇｅ

Ｐｒｏｃｅｓｓｉ“ｇ

０ｆｔ｝Ｉｅ

ＡＦＮ口．Ｓ咖ｕｄｓｂ“增，ＰＡ：Ａｓｓ【卜

ｔｅｘｔ

ｃａｔｅ９０五ｚａｔｉｏｎ

ｏｎ

ｉｌｎｂａｌａＩｌｃｅｄ

ｄａｔａ［Ｊ］．ＳＩＧＫＤＤＥｘｐｌｏｒａｔｉｏｎｓ，

ｃｉａｔｉｏｎ

ｆｏｒ

Ｃｏｍｐｕｔａｔｉ伽ａｌ

ｈｇＬｌｉ８ｎｃｓ，２００９：６９２－７００．

２００２，６（１）：８０＿８９．［５］ＬＩｕＨｕａ—ｗｅｎ，ｓｕＮＪｉ—ｇｕｉ．ＬＩＵＬｅｉ，ｅ＃甜．Ｆｅａｔｕｒｅｓｅｌｅｃｔｉｏｎｗｉｔｈｄｙ—

［１２ＪＨ０ｗ

Ｂ

Ｃ，ＮＡＲＡＹＡＮＡＮＫ．Ａｎｅｍｐｉｒｉｃａｌｓｔｕｄｙｏｆｆｅａｔｕｒｅｓｅｌｅｃ吐ｏｎ

ｎａＩｎｉｃ

ｍｕｔｕ越ｉ幽瑚ａｔｊ咖【ｊ］．Ｐａ№ｍＲｅｃｏｇｎ惜ｏｎ，２００９，４２（７）：

ｆｏｒ

ｔｅｘｔｃａｔｅｇｏｎｚａｈｏｎ

ｂ鹅ｅｄ

ｏｕ

０ｆＩＥＥＥ／

１３３０．１３３９

ｔｅ珊ｗｅｉｇｌｌｔ孵［ｃ］／／Ｐｒｏｃ

ＷＩＣ／ＡＣＭＩｎｔｅＩＩｌａｔｉｏｎａｌＣｏｎｆｂｒｅｎｃｅ

ｏｎ

［６］

肖婷，唐雁．改进的，统计文本特征选择方法［Ｊ】，计算机工程与

Ｗ曲Ｉｎ瞄ｌｉｇｅｎｃｅ．Ｗａｓｈｉｎｇ【０“

ＤＣ：ＩＥＥＥ

应用，２００９，４５（１４）：１３６一１３７，１４０、ＣｏｍｐｕｔｅｒＳｏｃｉｅｌｙ，２００４：５９９－６０２．Ｌ．Ｆ锄ｕ工ｅＧｗ

Ｆ色ａｔｕ代ｓｅｌｅｃｔｉｏｎ

［７］

ＮＧ

ＨＴ，ＧＯＨｗＢ，ＬＯｗＫ

８ｅｌｅｃｔｉｏｎ，ｐｅｒｃｅｐ咖ｎｌｅ邪ｉＩｌｇ，

［１３］ｓＯｕｃＹ

Ｐ，ＭＩＭＥＡｕ

ｓｔｒａｔｅ奇ｅｓｆｏｒ

ｔｅｘｔ

ｃａ咏。一

ａＩｌｄ

１６ｔ｝ｌｃ如ａｄｉａｎａ

ｌｌｓａｂｉｌｉｃｙｃ船ｅｓｔｕｄｙｆｏｒｔｅ砒ｅｍ锷０ｒｉ跄ｔｉ∞［Ｃ］／／Ｐ妣０ｆｔｌｌｅ２０ｔｌｌ

出出ｏｎ［ｃ］／／Ｐｍｃｏｆｔｈｅｓｏｃｉｅ‘ｙｈｃｏｍｐｕＬａｔｉ佃ａｌ

ＡｎｎｕａｌＩｎｌｅｍａｔｉｏｎａｌＡＣＭＳＩＣＩＲＣｏｒｄ毫ｒｅｎｏｅｏｎＲｅ８ｅａｒｃｈａｎｄＳｔｕｄｉｅｓ

ｏｆ

ｉｎＡｒｔｍｃａＪＩｎｔｅｌｌｉ・

Ｄｅｖｅｌｏｐ－

ＩｎｔｅｌｌｌｇｅｎｃｅＣｏｎｆｅｒｅｎｃｅ

０Ｉｌ

ＡｄⅧｃｅｓ

ｍｅｎｔｉｎ

ｈｌｆｏｎｍｔｉｏｎ

Ｒ“删ａ１．ＮｅｗＹｏｒｋ：ＡＣＭ．１９９７：６７－７３．

ｇｅｎｃｅ．ＢｅｒＩｉ“：Ｓｐ曲ｇｅｒ—Ｖｅｒｈｇ，２００３：５０５—５０９．

（上接第１６７２页）数，如设定为１００，这样如果没有低于或等于快、全局搜索能力强，对于求解大规模优化问题具有其优越性。】７０的最优值，进化到１００代也停止进化，输出１００代中得到的参考文献：

最优结果。

［１］王勇，毛海军，刘静，等．带时间窗的物流配送区域划分模型及其

根据以上设定，采用自适应遗传算法（即采用自适应策略算法［Ｊ］．东南大学学报：自然科学版，２０ｌｏ，４０（５）；１０７７一１０８３．的遗传算法）进行计算，获得最后的解决方案，最优的行程总［２］雷胜华．城市物流配送车辆调度问题的研究与应用［Ｄ］，北京：北

长度为１６２，把运行停止判断条件中的最优值判断参数设为京工业大学．２０ｌＯ．１７６，进化代数判断参数设为１００，其他设置不变。运行２０次，［３］ＴＳＥＮＧ

Ｌ

Ｙ，ｕＮ

Ｙ

Ｔ．Ａ

ｈｙｂ砌ｇｅ凹ｔｉｃＩｏｃａｌｓｅ锄ｈａ【９０＾ｃｈｍｆｏｒｔＩｌｅ

结果如表３所示。

ｐｃｍｕｔａｔｉｏｎｎｄｗｓｈｏｐｓｃｈｅｄｌｌｌｉｎｇｐｒｏｂｌｅｍ［Ｊ】ＥｕｒｏｐｅａｎＪｏｕｍａＩｏｆ

表３多次运行结果比较

０ｐｅｒａｔｉｏｎａｌ

Ｒｅｓｅａｒｃｈ，２００９，１９８（１）：８４－９２

［４］王洋．范剑英，林立军，等．物流配送路径优化理论在立体匹配技

术中的应用研究［Ｊ］．哈尔滨理工大学学报．２０１１，１６（２）：２４—２８．［５］廖洁君，陈燕．配送调度优化模型的研究及应用［Ｄ］大连：大连

海事大学，２‘）０５．

比较以上分析数据，可以说明本文采用的自适应遗传算法［６］张维泽，林剑波，昊洪森，等．基于改进蚁群算法的物流配送路径

所得到的解决方案优于采用基本遗传算法所得到的解决方案。

优化［Ｊ］．浙江大学学报：工学版，２００８，４２（４）：５７４－５７８．４结束语

［７］

ＹｕＥＮ

ｓＹ，ｃＨ０ｗｃＫ．Ａｇｅｎｄｉｅａｌｇｏ血ｈｍｔｈａｔａｄ叩ｔｉｖｅｌｙ

ｍｕｔａｔｅｓ

锄ｄ

ｎｅｖｅｒ斟商ｔｓ【Ｊ］．１ＥＥＥ

Ｔｒａｎｓ

ｏｎ

ＥＶｏｌｕ苗ｏｎａｒｙＣｏｍｐｕｔａｔｉｏｎ，

本文针对配送运输的一般问题，提出了优化配送的运送距２００９，１３（２）：４５４－４７２．

离来对物流配送问题进行寻优。在考虑实际情况下，引入』，多［８］胡祥培，于楠，丁秋雷，等．物流配送车辆的干扰管理序贯决策方

货物的配送情况，分析了物流配送抽象流程，以求取优化配送法研究【Ｉ］，管理工程学报，２０ｌｌ，２５（２）：１８６ｉ９０．

效率、降低算法的时间和空间复杂度为目标，设计了基于自适［９］晏梦君，陈震遗传算法在配迭优化系统中的应用［Ｄ］，长春：吉

应的多类型物流配送改进遗传算法。将基于自适应遗传算法林大学，２００７．

的多类型物漉配送优化算法应用到实际物流配送过程中，针对［１０】孙丽君．基于畅通可靠性分析的癌。市物渡配送网络优化研究

处理结果进行科学评价。

［Ｄ］．长沙：长沙理工大学，２０１０

与采用的基本遗传算法得到的解决方案相比，实例仿真的［１１］朱晓锋，蔡延光物流配送的优化模型及算法在连锁企业中应用

结果表明，本文采用的自适应遗传算法求解效率高、收敛速度

［Ｊ】．电子学报，２０１１，９（１）：１４—１７．