第３４卷第２期 文章编号：１００６—９３４８（２０１７）０２—０３６７—０４ 计算机仿真 ２０１７年０２月 网络数据特征选择的优化方法研究与仿真 张 浩 （南京工业大学计算机科学与技术学院，江苏南京２１００００） 摘要：对网络数据特征进行有效选择，可提高网络数据分类性能。由于随着网络数据量的增加，使得网络数据特征种类过 多。传统的网络数据特征选择方法，主要通过对网络数据特征进行二次选择，获得高精度特征，但是全局搜索能力差，导致 网络数据特征选择准确度低的问题。提出自适应遗传算法与蚁群算法相融合的特征选择方法。利用遗传算法的快速随机 的全局搜索能力，生成初始信息素，再通过蚁群算法对特征进行二次选择，以获得高精度的特征子集，最终对取得的最优解 进行解码操作，实现网络数据特征选择的优化。仿真结果表明，改进算法可以提高网络数据特征选择速度。 关键词：特征选择；自适应遗传算法；蚁群算法；文本特征 中图分类号：ＴＰ３９１ 文献标识码：Ｂ Ｎｅｔｗｏｒｋ Ｄａｔａ Ｆｅａｔｕｒｅ Ｓｅｌｅｃｔｉｏｎ Ｒｅｓｅａｒｃｈ ａｎｄ Ｓｉｍｕｌａｔｉｏｎ Ｏｐｔｉｍｉｚａｔｉｏｎ Ｍｅｔｈｏｄ ＺＨＡＮＧ Ｈｎｏ （Ｄｅｐａｒｔｍｅｎｔ ｏｆ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ，Ｎａｎｊｉｎｇ Ｔｅｃｈ Ｕｎｉｖｅｒｓｉｔｙ，Ｎａｎｊｉｎｇ Ｊｉａｎｇｓｕ ２１００００，Ｃｈｉｎａ） ＡＢＳＴＲＡＣＴ：Ｉｎ ｔｈｉｓ ｐａｐｅｒ，ｗｅ ｐｒｏｐｏｓｅ ａ ｆｅａｔｕｒｅ ｓｅｌｅｃｔｉｏｎ ｍｅｔｈｏｄ ｗｈｉｃｈ ｉｎｔｅｇｒａｔｅｓ ａｄａｐｔｉｖｅ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ ｗｉｔｈ ａｎｔ ｃｏｌｏｎｙ ａｌｇｏｒｉｔｈｍ．Ｆｉｒｓｔｌｙ，ｗｅ ｕｓｅｄ ｔｈｅ ｒａｐｉｄ ａｎｄ ｒａｎｄｏｍ ｇｌｏｂａｌ ｓｅａｒｃｈｉｎｇ ａｂｉｌｉｔｙ ｏｆ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ ｔｏ ｇｅｎｅｒａｔｅ ｔｈｅ ｉｎｉｔｉｌ ｐｈｅｒｏｍｏｎｅ．Ｔｈｅｎ，ｗｅ ｕｓｅｄ ａｎｔａ ｃｏｌｏｎｙ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｔｈｅ ｓｅｃｏｎｄａｒｙ ｓｅｌｅｃｔｉｏｎ ｏｆ ｆｅａｔｕｒｅｓ ｔｏ ｏｂｔａｉｎ ｔｈｅ ｆｅａｔｕｒｅ ｓｕｂｓｅｔ ｗｉｔｈ ｈｉｇｈ ｐｒｅｃｉｓｉｏｎ．Ｆｉｎａｌｌｙ，ｗｅ ｄｅｃｏｄｅｄ ｏｐｔｉｍｕｍ ｓｏｌｕｔｉｏｎ ｔｏ ａｃｈｉｅｖｅ ｔｈｅ ｏｐｔｉｍｉｚａｔｉｏｎ ｏｆ ｆｅａｔｕｒｅ ｓｅｌｅｃｔｉｏｎ．Ｔｈｅ ｓｉｍｕｌａｔｉｏｎ ｒｅｓｕｌｔｓ ｓｈｏｗ ｔｈａｔ ｔｈｅ ｍｏｄｉｉｆｅｄ ｍｅｔｈｏｄ ｃａｎ ｉｍｐｒｏｖｅ ｓｅｌｅｃｔｉｏｎ ｒａｔｅ ｏｆ ｎｅｔｗｏｒｋ ｄａｔａ ｆｅａｔｕｒｅ ａｐｐａｒｅｎｔｌｙ． ＫＥＹＷＯＲＤＳ：Ｆｅａｔｕｒｅ ｓｅｌｅｃｔｉｏｎ；Ａｄａｐｔｉｖｅ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ；Ａｎｔ ｃｏｌｏｎｙ ａｌｇｏｒｉｔｈｍ；Ｔｅｘｔ ｃｈａｒａｃｔｅｒｉｓｔｉｃ 所以遗传算法是解决该类问题的理想方案 。ｊ。文中使用 １ 引言 随着网络社会的高速发展，信息量的不断增加，使得出 现大量的网络数据特征，因此，如何准确的从中提取所需的 自适应遗传算法思想对传统遗传算法中的交叉率和变异率 进行优化有效的加快遗传算法的收敛速度并能够避免出现 早熟现象 “ 。特征选择过程也可以将特征看作蚂蚁要访 问的文本，因而寻找最优特征集就可以转化为蚂蚁觅食寻找 最优路径的问题 “ 。蚁群算法采用正反馈机制，通过信息 网络数据特征变得十分重要 Ｊ。文本内容作为一种半结构 化的数据，若只是简单的使用向量空问模型（Ｖｅｃｔｏｒ Ｓｐａｃｅ Ｍｏｄｅｌ，ＶＳＭ）提取网络数据特征，其数量可达数万之多，采用 优秀的特征选择技术能够消除无用的特征并有效的提升文 素更新达到最终收敛，但由于算法初始阶段信息素不足，导 致求解效率低。充分利用自适应遗传算法和蚁群算法的优 势，采取使用自适应遗传算法快速全局搜索得到初始信息素 分布的策略，进一步利用蚁群算法高精度求解的特点获得较 高精度的文网络数据特征＿１ 。 本分类的效率。目前常见的特征选择方法有潜在语义索引， 信息增益，互信息，卡方统计等，以上特征选择方法都已经被 证明都存在一定的局限性 Ｊ。 遗传算法是依据生物遗传机制和进化的特点而提出的 算法，能高效得处理非线性规划的问题，因此在机器学习，组 合优化，规划设计等领域有着非常突出的适用性。特征选择 ２网络数据特征选择 ２．１具体选择 在优化的角度可以看作网络数据特征选择最优组合的过程， 收稿日期：２０１６—０３—２４修回日期：２０１６—０４—２２ 文本可以看为由大量特征项组成的多维信息空间，因此 可以通过使用向量空间模型来表示文档 Ｖ（ｄｏｃ）＝｛ｔｌ，Ｗ１；ｔ２，Ｗ２；…；ｔ＾，Ｗ ｝ －－－——（１） ３６７－－－—— 其中，ｔ 是特征词条， 为第ｉ个特征向量所具有的权重，权 量来获得分类的效果，因此选择个体特征中含有“０”个数多 的个体。 根据上述条件可以设定个体适应度函数为以下式子 ，＝Ａ ＋Ｂ Ｓ—ＩＭ，＋Ｃ ，‘ 重就是特征在文档中能表达文本信息的能力的大小值，一般 采用ｒｒＦ—ＩＤＦ（ｔｅｒｍ ｆｒｅｑｕｅｎｃｙ—ｉｎｖｅｒｓｅ ｄｏｃｕｍｅｎｔ ｆｒｅｑｕｅｎｃｙ） 确定权重大小。 ２．２自适应遗传算法 对于给定的网络数据特征集，文中采用二进制编码方 式，使用由词条构成的染色体代表特征集的解空间。在预处 理过的词汇表中选择ｎ个候选特征，则设定染色体长度为ｎ， 每个基因位对应相应次序的特征。用ｎ位０和１构成的二 ，Ａ＋Ｂ＋Ｃ：１（５） 其中Ａ、Ｂ、Ｃ为调整因子。 遗传算法通过优胜劣汰执行选择操作，个体的适应度大 小通过上述式子计算，并将得出的结果按照各自的适应度从 大到小排列，挑选前２０％优秀个体直接进入下一代，剩余部 分通过轮盘赌选择法进行筛选，其中所有个体对应的适应度 值的大小与其被选中的机率为正比关系，这样既可以保证下 进制字符串表示一个特征组合，即若某个特征被选中，则其 基因的二进制位改为１，否则定为０，这样每条染色体就分别 代表了不同的特征子集。使用此方案能够方便的进行编码 解码，又易于处理遗传算法中的交叉变异操作＿ｌ 。 ２．２．１初始种群的选择 初始种群的规模设定影响遗传算法效能，规模设定太小 不宜于保持种群多样性容易出现局部最优的现象，规模太大 则增加算法运行负担影响效率。为了提高初始种群质量。文 中首先采用随机方法生成１Ｏ个个体，个体基因等概率随机 选择，再从中挑选出适应性最强的个体为初始种群成员以提 高初始种群质量，重复以上操作Ｍ次获得规模为Ｍ的初始 种群。 ２．２．２适应度函数的确定 选择合适的适应度函数对遗传算法至关重要，遗传算法 通过适应度函数判断解的质量，使种群进化为优质解。根据 文本过滤的特点，适应度函数要保证优良个体具有较高适应 度值应满足以下条件¨ ： １）特征子集应该可以代表文本，其代表性通过特征的权 值体现。文中使用特征集的平均权值表示特征集的代表性， 其中特征集的平均权值越大则越能代表该类文本，平均权值 计算公式如下 ｔｌ ＝ （２） ２）在遗传算法中，较优的个体应该更能代表目标文本， 它在同一种群中与其它个体的相似性也越大。此处采用余 弦相似度的方式计算个体同其它个体之间的相似度 ＳＩＭ（Ｓ ，ｓｉ）＝ｃｏｓ（Ｓ ，ｓｉ）＝— ｋ＝∑ ＝ｌ＝＝＝＝＝ 目 （３） ， ｎ √ 埘 茸２ ～∑ＳＩ』 Ｍ（Ｓｌ‘ ，｜ｓｆＪ ） ＳＩＭ ＝卫 （４） 其中，ＳＩＭ（Ｓｉ，．ｓ ）代表种群中两个个体ｓ 和ｓｉ的相似程度， 代表个体Ｓ 中的第ｋ个特征的权重， 代表个体ｓ 的第 ｋ个特征的权重，ｎ为个体特征总数，最后求出个体Ｓ 平均相 似度。 ３）特征向量维数应该尽可能少，通过使用较少的特征 ．．．——３６８．．．—— 一代的最佳群体优于上一代的最佳群体也可以避免算法过 早收敛并具有一定的随机性。 ２．２．３自适应交叉变异 遗传算法通过交叉操作和变异操作生成新的后代并保 证种群具有多样性，是算法获得优质解最关键的步骤。较大 的交叉概率会加速新解的产生速率但会破坏原有优质解，较 小的交叉概率会使搜索陷入停滞状态。较大的变异概率使 算法成为随机搜索算法，过小则可能导致算法过早收敛。在 此采用改进的线性自适应遗传算法引入遗传代数利用余弦 值使遗传算法的交叉率与变异率值的选取随进化的推进而 平滑的改变，这样能在前期保证优良个体更容易产生，后期 种群更加平稳。公式如下 Ｅ＝ｃｏｓ（＿ｔ ｛） （６） 』（ＰＩ 一 （７） Ｐｆ１￥Ｅ ≤Ｌｖ， 一 Ⅲ （８） Ｐｖｌ Ｅ ≤ 其中，ｔ代表本次遗传代数，ｆ 是限定遗传代数，ｌ厂是变异个 体具有的适应度√ 是种群中适应度最大的个体 代表平 均适应度，，是两个交叉个体中适应度较大的个体。 ２．３蚁群算法 根据蚂蚁觅食行为，可将网络数据特征选择转化为如图 １所示的有向图形式，蚂蚁通过每个文本信息间的信息素进 行选择下一个文本，此信息素即为网络数据文本特征，蚂蚁 完成一次觅食所经过的特征信息就是得到的最优特征子 集［１ 。例如，初始蚂蚁位于 的信息，根据转移规则蚂蚁 选择 ， ， 后续文本信息，此时蚂蚁完成搜索，所要求的 最优特征子集就是路径｛ ， ， ，Ｖ４｝。 ２．３．１评估函数与转移概率的计算 以提高分类的准确率为目标使用查全率和查准率为评 估指标用以测试特征分类能力，将两者平等对待得出评估函 数定义为如下： Ｆ＝２ａ／（２ａ＋ｂ＋Ｃ） （９） 图１ 网络数据特征选择模型图 其中，ａ代表正确分类的样本数，ｂ表示分类认为不属于实际 属于的样本数，Ｃ表示分类认为属于此类实际不属于的样 本数。 蚂蚁位于特征信息通过判断可选路径所存有的信息素 浓度挑选下一特征，使用ｒ （ｔ）代表ｔ次迭代从特征ｉ到 的 信息素，并设置ｔａｂｕｋ表来保存编号为ｋ的蚂蚁已走过的特 征信息。蚂蚁从特征ｉ转移到特征 的概率如下： ＰＰ ：；＝｛∑ｒｆ【 ｏ ：（ｔ） （￡）”。，ｆ ｓ ｅ隹ｔｒｚ￡＇ 。 ｅ “ （，１。０） 其中，卵 为启发因子，根据特征在文档中出现的频率高往往 会具有更多的分类信息的规则 ，启发因子计算方式如下： Ｊ，７ ＝ｄｆ（ｔ ） （１１） ２．３．２基于自适应遗传蚁群算法的网络数据特征选择的 实现 蚂蚁结束一次觅食，就依照如下方式更替每个特征的信 息素值： ｆ （ｍ＋１）＝Ｐ ｒ （ｍ）＋∑ｈｒ ｛ （１２） 【∑ｈｒ；＝Ｑ／Ｆ（Ｓ ） 其中：ｐ（Ｏ＜ｐ＜１）表示信息素残留因子，ｋ为蚂蚁的编号，ｍ 为此次迭代次数，Ｑ为信息素增长浓度，Ｆ（Ｓ ）为特征子集 的适应度值。 若算法连续经过三次迭代后适应度函数没有发生多少 变化或者达到最大迭代次数则终止算法。 综上可知特征选择流程首先采用遗传算法的快速的随 机全局搜索能力，为蚁群算法生成初始信息素，再通过蚁群 算法的求解精度高的优点对特征进行二次选择，以获得高精 度的特征子集。最终对取得的最优解进行解码操作，得到的 结果就是所要求的高精度的网络数据特征，算法流程如图２ 所示。 ３仿真结果与分析 实验采用的网络数据文本集预料是复旦大学提供的文 本分类语料库，从中选取８００篇不同种类的文本用于进行分 类实验，其中包含有环境，交通，经济，军事，体育５大类，取 ３００篇文档作为训练集，剩余５００篇文档作为测试集。对这 些文本进行去停用词，词干还原等操作 获得１１８３４个原 图２ 自适应遗传蚁群算法特征选择的工作流程 始特征子集。文中采用常用的召回率 以及准确率Ｐ对分 类效果进行评估。设置参数如下：初始种群Ｍ＝８０，初始交 叉率Ｐ ＝０．９，初始变异率 ＝０．０５，自适应交叉率Ｐ ＝ ０．３，自适应变异率Ｐ ＝０．０２，信息素残留因子Ｐ＝０．９，启发 式因子权重和信息素权重 取值均定为１。 设置对比方案如下： 方法１：无降维 方法２：普通遗传算法特征选择 方法３：自适应遗传蚁群算法特征选择 ３．１不同方法的文本分类比对 文中采用ＳＶＭ（Ｓｕｐｐｏｒｔ Ｖｅｃｔｏｒ Ｍａｃｈｉｎｅ）作为文本分类器 进行分类，将传统方法１和２作为对照，使用以上３中方法 进行特征选择将所得特征用于文本分类，实验结果如下表 所示： 表１实验分类结果 ・－－——３６９・－－—— 其中，Ｐ代表分类精度，Ｒ代表分类效率。 从表１中可以看出由于未经过特征降维的文本的特征 维数巨大并具有较多的冗余特征干扰分类器分类效果，所以 分类效果表现不佳。使用了普通遗传算法特征选择后进行 文本分类分类器具有较佳的分类精度，但本文利用蚁群算法 在遗传算法的基础上更进一步提高特征选择的精度，对经过 遗传算法特征选择后筛选出的特征进一步精化选择，也表现 出比使用普通遗传算法进行特征选择更好的分类效果。由 上可知，文中提出的自适应遗传蚁群算法能够较好的去除文 本冗余特征，并保证网络数据分类效果。 ３．２不同方法下网络数据特征选择精度和误差比对 提高文本特征子集的精度。将遗传算法和蚁群算法结合应 用于文本分类中能有效的提高数据特征分类的性能，实现对 网络数据准确的分类。 参考文献： ［１］吴金源，等．基于特征选择技术的情感词权重计算［Ｊ］．北京 工业大学学报，２０１６，４２（１）：１４２—１５１．． ［２］周小娟．一种轻量级大数据分析系统的实现［Ｊ］．电子设计工 程２０１６，８（２４）：４Ｏ一４３． ［３］ 张晶，李德玉，王素格．基于多标记学习的汽车评论文本多性 能识别［Ｊ］．计算机工程与科学，２０１６，３８（１）：１８８—１９４． ［４］赵东红，王来生，张峰．遗传算法的粗糙集理论在文本降维上 本文传统方法１和２作为对照，使用以上３中方法进行 网络数据特征选择，将不同算法的选择精度和误差进行比 对，结果如表２所示。 表２不同方法下网络数据特征选择精度和误差比对 其中，Ｐ代表网络数据特征选择精度，Ｓ代表特征选择 误差。 分析表２可知，与传统算法相比，对于不同类型的文本 数据，本文提出的改进方法具有较高的分类精度，并能将误 差控制在一定的范围内，证明了改进算法在网络数据特征选 择精度上的绝对优势。 ４结论 本文提出了一种融合了自适应遗传算法与蚁群算法网 络数据特征选择方法，并对遗传算法中自适应交叉变异操作 进行改进，使其在求解过程中依照进化的推**滑改变，以 保证取得优质解的同时防止出现早熟收敛现象。算法利用 自适应遗传算法快速的搜索能力解决蚁群算法初期信息素 不足的缺点，将求得的后代再利用蚁群算法进行二次精选以 －－－－——３７０－－－－—— 的应用［Ｊ］．计算机工程与应用．２０１２，４８（３６）：１２５—１２８． ［５］ 杜芳华，冀俊忠，赵学武，吴晨生．基于特征映射的半监督文本 分类算法［Ｊ］．北京工业大学学报，２０１６—２：２３０—２３５． ［６］武川，陆伟．基于上下文特征的短文本实体链接研究［Ｊ］．情 报科学，２０１６，（２）：１４４—１４７． ［７］ 张人上，曲开社．一种基于新的特征选择的海量网络文本挖掘 算法研究［Ｊ］．计算机应用研究，２０１４，３１（９）：２６３２—２６３４． ［８］ 王璐，邱桃荣，何妞，刘萍．基于粗糙集和蚁群优化算法的特征 选择方法［Ｊ］．南京大学学报，２０１０，４６（５）：４８７—４９３． ［９］ 徐震．网络舆情内容分析中的Ｗｅｂ文本语义特征抽取研究 ［Ｊ］．图书馆学研究，２０１６，（１）：２６—３１． ［１０］ 王利琴，董永峰，顾军华．改进的精英遗传算法及其在特征选 择中的应用［Ｊ］．计算机工程与设计，２０１４，３５（５）：１７９２ —１７９６． ［１１］ 徐娇．基于Ｈａｄｏｏｐ的文本特征选择算法的研究［Ｄ］．兰州大 学，２０１５． ［１２］ 李凯齐，刁兴春，曹建军，李峰．基于改进蚁群算法的高精度 文本特征选择方法［Ｊ］．解放军理工大学学报（自然科学 版），２０１０，１１（６）：６３４—６３９． ［１３］朱贺军，马丁．海量短文本实时挖掘方法的研究与仿真［Ｊ］． 计算机仿真，２０１５，（１２）：４４２—４４６． 量 ［张究生，浩主（要１９研１究一领）域，男为作（数者汉据族简挖）介掘，浙］。 江金华人，硕士研