改进的正弦余弦文本分类特征选择算法研究

沙特国王大学学报一种改进的正弦余弦文本分类特征选择算法Mouhoub Belazzouga，b，Mohamed Touahriaa，Farid Nouiouab，d，Mohammed Brahimib，caFerhat Abbas Stif 1大学计算机科学系，阿尔及利亚b阿尔及利亚Bordj Bou Arreridj Mohamed El Bachir El Mushimi大学计算机科学系c阿尔及利亚阿尔及尔USTHB大学计算机科学系d艾克斯-马赛大学、法国国家科学研究中心、法国土伦-马赛大学阿提奇莱因福奥文章历史记录：收到2019年2019年6月19日修订2019年7月10日接受在线预订2019年保留字：文本分类信息增益特征子集选择Wrapper方法改进的正弦余弦算法A B S T R A C T词袋模型是文本分类的常用模型。该模型的主要问题在于涉及的特征数量太多，影响了分类任务的性能。为了解决这一问题，特征选择方法是必要的。特征选择有利于降低问题的维数，从而减少计算时间，提高分类任务的性能。在本文中，我们提出了一个新的改进算法的原始正弦余弦算法（SCA）的特征选择，它允许更好地探索在搜索空间。与SCA只关注最佳解决方案以生成新的解决方案不同，我们建议的新算法（ISCA）考虑了解决方案的两个位置。(i)的位置，最好的解决方案，到目前为止发现，和（ii），从搜索空间的一个给定的随机位置。这种组合使我们能够提出一个简单的算法，这是能够避免过早收敛，并获得非常满意的性能。为了验证ISCA算法的有效性，我们在9个文本集上进行了一系列实验，此外，从现有的技术水平，遗传算法（GA）和蚁群算法（ACO）的选择在我们的比较研究。我们的评估结果表明，我们提出的ISCA算法，这使得它非常有用的文本分类问题的高性能。©2019作者制作和主办：Elsevier B.V.代表沙特国王大学这是一CC BY-NC-ND许可下的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。1. 介绍如今，越来越多的电子文档需要自动组织方法。在这种情况下，文本分类（TC）旨在将新文档分配给预定义的类别集（Reintiani，2002）。词袋（BagofWords，BoW）模型是TC中常用的模型，每个文档用一个词向量表示BoW模型考虑了大量的特征。然而，大多数提取的特征是不相关的或冗余的。因此，这种高维度自然沙特国王大学负责同行审查制作和主办：Elsevier电 子 邮 件 地 址 ： belazoug. gmail.com （ M.Belazzoug ） ， 穆 罕 默 德 。touahria@univ-setif.dz （ M. Touahria ） ，nouioua. univ-bba.dz （ F.Nouioua） ，mohamed. univ-bba.dz（M. 卜拉希米）增加了分类算法的计算时间并降低了其结果的准确性特征选择（FS）是TC预处理中的一个重要步骤，以克服这个问题。它的目的是确定一个子集，包含有限数量的相关功能，足以维持或提高分类任务的性能。基于评估程序，FS方法可以分为三种主要方法：过滤器，包装器和嵌入式方法（Gheyas和Smith，2010）。特征选择在许多领域都有应用，包括文本分类（Lee和Lee，2006）、文档聚类（Kogan，2003）、图像处理、计算机视觉、生物信息学和工业应用（Bogunovic等人，2015年）等。从计算的角度来看，特征选择是一个困难的问题。对于一个给定的N特征搜索空间，存在2N个可能的特征子集组合（Mladeni，2006）。通常，FS算法包括启发式或随机搜索策略，试图避免这种过高的复杂性。然而，最终特征子集的最优程度往往会降低。https://doi.org/10.1016/j.jksuci.2019.07.0031319-1578/©2019作者。制作和主办：Elsevier B.V.代表沙特国王大学这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。可在ScienceDirect上获得目录列表沙特国王大学学报杂志首页：www.sciencedirect.comM. Belazzoug等人/Journal of King Saud University455在FS中提出的搜索算法中，基于种群的优化算法如GA、粒子群优化（PSO）和ACO是常用的。这些方法试图迭代地改进它们的解。他们开始与代理的初始人口，这些代理更新他们的位置在搜索空间中根据一个适当的公式，使代理的位置进行连续的变化，以达到最优解。重复该过程，直到达到结果的阈值或达到最大迭代次数。在文本分类中，已有几种元启发式搜索算法被提出来处理特征选择问题。这样的算法的示例包括：遗传算法结合经典FS方法，如IG（U uz，2011; Ghareb等人，2016）;增强的蚁群优化（Janaki Meena等人，2012）以及PSO风格的算 法 （ Baykan ， 2014;Chantar 和 Corne ， 2011; Karabulut ，2013）。TC过程一般分为四个步骤：文本预处理和表示阶段、术语缩减阶段、分类任务和结果评估阶段。在本文中，我们遵循图1所示的标准TC架构。在这里我们使用两个步骤来执行FS任务：一个filter步骤和一个wrapp-per步骤.值得注意的是，在第一步（过滤）中，我们基于信息增益（IG）算法快速获得排名前200的特征。然后，从IG算法得到的特征子集被用作包装步骤（ISCA）的输入。因此，这些特征的小的有限数量使得搜索算法ISCA更方便和有效。本文的主要贡献是提出了一种新的包装算法，称为改进的正弦余弦算法（ISCA）。实际上，ISCA是Mirjalili（Mirjalili，2016）提出的最新强大算法Sine Cosine Algorithm （SCA ）的改进版本ISCA算法试图发现更多的新区域的搜索空间相对于原来的SCA算法。与SCA只关注最佳解以生成新的解不同，我们建议的新算法（ISCA）考虑了解的两个位置：第一个是迄今为止找到的最佳解的位置，第二个是搜索空间中给定的随机这种结合使我们既能避免过早收敛，又能提高性能。对于包装器算法中使用的适应度函数，我们应用朴素贝叶斯（NB）分类器（McCallum和Nigam，1998）来评估候选特征子集的质量此外，为了评估我们的包装器算法的全局性能本文的其余部分组织如下：在第二节中，我们提出了相关的工作，特征选择方法，我们简要介绍了遗传算法和蚁群算法。第3节中我们提出了在这项研究中使用的背景元素，即过滤方法（IG）以及原始算法SCA的基础。在第4中描述了所提出的ISCA算法。事实上，我们解释了我们的搜索算法（ISCA）采用的多样化策略。实验，结果和比较与国家的最先进的算法，并在第5节中讨论。最后，我们在第6节中总结了本文，并对未来的工作提出了展望。2. 相关作品特征选择算法可以分为三类：过滤器，包装器和嵌入式方法。在滤波器方法中，评估标准与学习算法无关。在这种方法中，特别是特征排名，每个特征通过使用统计测量单独评估，然后选择具有最高分数的特征。此外，特征选择过程仅执行一次。因此，它可以快速消除不相关的特征。这种方法（特征排序）的一个主要缺点是它没有消除特征之间的冗余。在包装器方法中，FS算法使用学习算法一次性评估所有特征的子集。它是基于一个搜索算法以及测量标准。特征子集的质量通过学习机的性能来表示。在文本分类应用的情况下，目标函数是分类算法的性能对每个特征子集重复评估包装器方法比过滤器方法具有更好的性能，但它非常耗时。在嵌入式方法中，特征选择和学习算法是交错的。更确切地说，过滤器被包括在包装器算法的学习机中。在这种情况下，我们区分三种算法：指数算法，顺序算法和随机算法。指数Fig. 1. 提出的文本分类策略流程图。456M. Belazzoug等人/Journal of King Saud University算法评估相对于特征空间的大小指数增加的子集的数量。顺序算法是按顺序添加或删除特征的，这使得它们面临着早熟收敛到局部最优的问题。最后，随机算法将FS问题视为黑箱。这些算法通过在其搜索过程中改变输入变量来迭代地达到输出变量的值。这使它们能够避免局部最优，并使它们能够很好地适应任何类型的优化问题。在文献中，一些FS方法的基础上的功能在文本分类的背景下，作者（Yang和Pedersen，1997）比较了几种方法，如文档频率（DF），信息增益（IG），互信息（MI），卡方（X2）和术语强度加权的FS。比较表明，IG和X2是最有效的两种方法.此外，Forman（2003）对12种特征选择方法进行了广泛的实证比较.他发现被称为“双正态分离”（BNS）的特征选择度量至于包装方法，一些元启发式搜索算法已被用来解决特征选择问题的TC。遗传算法（Genetic Algorithms，GA）是一种基于自然启发的进化算法（Holland andReitman，1978）。它们模仿自然界中基因的突变、选择和繁殖。例如，遗传算法已被用作解决数据挖掘中的特征选择问题的工具（Siedlecki和Sklansky，1989）。蚁群优化算法是智能群算法家族中的一种启发式算法。蚁群算法是一种基于蚁群觅食行为的随机搜索方法（DORIGO，1992）。更准确地说，每只蚂蚁在特定的路径上行走时会释放相同数量的信息素，这些信息素会吸引其他蚂蚁跟随这条路径。在其他路径中选择特定路径的概率与这条路径上信息素的数量成正比：路径上信息素的数量越多，它就越受青睐。同时，存在于不同路径中的信息素的量根据预定义的蒸发速率减少。因此，短路径随着时间的推移会保留更多的信息素，它们更有可能被蚂蚁选择。在（Aghdam等人，2009年），作者应用了基于FS的方法ACO文本分类算法的研究。Al-Ani（2005）也提出了一种将蚁群算法应用于语音分类问题的FS方法。在本文中，我们特别感兴趣的正弦余弦算法-rithm（SCA）. SCA最近由Mirjalili（2016）提出。SCA是一种全局优化方法，它使用基于正弦和余弦函数的数学模型来迭代更新一组候选解决方案。SCA算法的有效性已在多个应用中得到证明，例如在连续函数的优化中，SCA已在多个数据集上进行了测试，以及在解决翼型设计问题等实际问题中（Mirjalili，2016）。此外，（Abd El Aziz et al.，2017）已经实现了SCA，用于使用图像检索检测星系。最近，已经提出了一种改进的SCA算法来解决全局优化问题（Abd Elaziz等人，2017年）。SCA算法的这种变体将基于反对的学习（OBL_SCA）视为搜索空间探索的多样化策略的机制。作者通过在几个基准函数上测试他们的算法，以及在一些工程问题上评估其能力，来验证他们的算法来解决真正的问题在（Li等人，2017），作者提出了一种基于Levy Flight的改进正弦余弦算法。其主要思想是：没有得分进步的个体飞行，以提高探索能力。该算法在复杂的非线性优化问题中表现出良好的性能。在（Meshkat和Parhizgar，2017）中提出了一种新的加权更新位置机制，以提高正弦余弦算法（加权_SCA）的性能。已经表明，Weighted_SCA算法优于SCA，并且与之相比能够更快地收敛。最近，对于全局优化应用，已经提出了几种算法，包括：2018）、基于正交并行信息的改进正余弦算法（Rizk-Allah，2018）和改进正余弦水波优化算法（Zhang例如， 2018年）。在FS领域中，SCA被提出作为用于特征选择系统（Hafez等人，2016年）。在后一项工作中，SCA算法已经在18个数据集上实现和测试。实验表明，SCA的进步，其他搜索方法，如粒子群算法和遗传算法。最后，具有精英策略的SCA的改进版本已经应用于机器学习中的FS（Sindhu等人，2017年）。在该变型中，提出了一种改进的溶液位置更新。但是，它需要一个额外的参数，应该进行调整。在本文中，我们解决了文本分类的特征选择问题特别是，我们的目标是证明我们提出的包装ISCA FS的效率。我们的包装ISCA相结合的信息增益过滤器，以克服巨大的维数问题。参考本节中的上述文献，SCA及其变体已在多个领域显示出其效率。事实上，它已被证明，这些改进的变种以及SCA算法优于最先进的优化算法，如PSO，GA和ACO在许多情况下。这一成功促使我们将工作重点放在一个新的改进SCA变体的建议上，该变体能够进一步改善文本分类上下文中的特征选择结果。在详细介绍我们提出的算法之前，让我们在下一节回顾SCA算法的主要原理和在滤波步骤中使用的信息增益方法3. 预赛本节介绍了本研究中使用的背景要素。第3.1节描述了统计测量IG，它测量类别和术语之间的信息位数。该滤波方法用于快速去除不相关的特征，并作为下一个特征选择步骤的预处理第3.2节描述了在我们的改进算法ISCA中使用的原始SCA算法的基础和细节。3.1. 信息增益如上所述，包装器方法在执行时间方面对于大维度应用程序是非常昂贵的。为了克服这一困难，我们首先将过滤方法称为预压步骤。只有过滤器方法选择的最佳特征才被用作包装器算法（ISCA）的输入。在过滤步骤中，我们应用了信息增益（IG）测量（Reintiani，2002）。它通过了解文档中术语的存在或不存在来测量类别预测所获得的信息位数。项t和范畴ci的IG由公式（9）给出。为了简化IG公式，我们引入以下四个依赖元组：● cii：t的存在和ci中的成员。● C.非会员：在C. I .中的T和非会员。M. Belazzoug等人/Journal of King Saud University457.Σ●;ththðÞt1不不不不X ij不不不t;ci：没有t和ci的成员。●.t;c i组：没有t组和不属于c i组。4. 一种改进的正弦余弦特征选择算法（ISCA）ICXCC不Xttpt0clog←pt0;cpt0pcð9Þ本部分介绍了新的改进ISCA算法的新的多样化策略的主要思想。尽管SCA2fijig0 2fijig其中p是某项在给定类中出现或不出现的概率。该概率表示属于类别ci的文档中术语t的出现次数。3.2. SCA算法正弦-余弦算法是最近的迭代随机算法（Mirjalili，2016），其中，在每次迭代时，解基于正弦或余弦函数被更新，如等式（1）所示。（1）和（2）分别：Xi; j t1¼ Xi; jt r 1 ω sinr 2 ω。r 3 Pjt-Xi; jt.ð1ÞXi;jX i;jr1 ωcosr 2 ω。r 3 Pj-Xi;j.ð2Þ在几个优化应用中取得了成功，SCA算法也是如此与其他元启发式算法一样，它也不是完美的，存在一些需要克服的事实上，SCA往往陷入次优区域，这反映在获得最佳性能所需的计算工作量中。其原因可能依赖于搜索空间探索的限制，因为我们可以观察到朝向或向外更新最佳找到的解决方案的解决方案的限制因此，如果我们使该算法能够参考来自研究空间的更远区域的其他解，我们将有更多的机会发现突出区域，从而避免收敛到局部最优。我们直观的想法是，使势解的动力学不仅依赖于最佳解，而且依赖于一些随机解图图2显示了两种算法之间发现的空间区域的差异SCA和ISCA。在此基础上，很明显，其中Xi;jt是当前解i在第t次迭代时在第j维中的位置，Pjt是第t次迭代时在第j维中的最佳个体的位置，j：j表示绝对值符号，并且r1、r2和r3是随机变量。上述两个等式可以组合成以下等式：（Xi; jr1 ω sin r 2 <$ω. r3 Pj-Xi; j. IFR 4 <0：5¼不不不ISCA的面积大于原始SCA的面积。为了正式捕捉这一想法，我们建议，一个人(i) 由以下公式给出：Xi;jt11-r 1ωXi;jtr1R 5其中Xi，jt是当前解i在第t次迭代时在第j维中的位置，R是搜索空间中包括的随机位置R1是与上述公式4中使用的相同的随机变量。的;tXi; jr1 ω cosr 2 <$ω. r 3 Pj-Xi; j. IFR4≥ 0： 5ð3Þ其中r4是0和1之间的随机实变量。前面的参数r1、r2、r3和r4的含义直观地给出如下：参数r1指示下一个位置区域（或移动方向），其可以在位于当前解和目的地之间的空间中或在该空间之外。参数r2定义了应该向目的地或向目的地外参数r3为目的地带来随机权重，以便在定义距离时随机强调（r3> 1）或不强调（r3>最后，参数r4在等式中的正弦和余弦分量之间相等地切换。（三）、SCA算法的伪代码在算法1中给出。为了在开发和探索之间取得平衡，（Mirjalili，2016）在公式（1）和（2）中使用了正弦和余弦范围的自适应变化。公式（4）显示了这一细节：参数影响新解的位置的更新。实际上，新解的位置在搜索开始时被随机位置R吸引但是，在搜索结束这种从R位置到X（i，j）位置以及从发散到收敛的吸引交易通过迭代地减小r1的值来保证，参见公式（4）。此外，我们对方程组（3）进行了一些修改。一方面，我们建议将正弦和余弦两个实际上，我们认为，在这两个公式之间作出选择是任意的，因为两个正弦而余弦函数对于区间[0，2p]中的实数输入返回-1和+1之间的值。因此，我们认为，免除这两种职能之间的交替不会造成r1¼a-aωtð4Þ其中t是当前迭代。T是最大迭代次数，a是常数。算法1正弦余弦算法。1. 初始化一组随机代理2. 计算每个代理的成本函数3. 选择优化成本函数的最佳代理4. 更新r1，r2，r3和r45. 使用等式（3）更新搜索代理的位置6. 如果（t max number of iteration（T））变为2。7. 返回迄今为止获得的最佳解作为全局最优解图二.SCA算法、ISCA算法、正弦余弦算法的研究与开发算法在上图，改进的正余弦算法在下图。权重R1-R2和R2-R3分别表示当前位置X1-R2和随机位置R这些458M. Belazzoug等人/Journal of King Saud University..-←←fit¼aω错误率算法的性能。另一方面，为了在集约化和多样化之间达到一个很好的折衷，我们引入了一个新的方程，它取决于随机变量c和r1。这确保了勘探和开发之间的有效过渡。当量（6）下表显示最新情况及多元化策略：4.2. 特征子集评价在每一代中，根据基于适应度函数计算的适应度值对特征子集的优先级进行排序。ISCA的适应度函数是最大化准确性并尝试达到一个短子集。为此，我们将特征数量和错误率合并到一个公式中。因此，Xi;jt1n =1-r 1 <$ωX<$i;j<$t<$r1ωR如果cr 1

下载后可阅读完整内容，剩余1页未读，立即下载