⊆*：P →≤{}⟨ ⟩ ⊆ ⊆⊆SoftwareX 6（2017）193原始软件出版物featsel：一个用于特征选择算法和成本函数的基准测试框架马塞洛·SReisa，b，*，Gustavo Estrelab，c，Carlos Eduardo Ferreirac，Junior Barrerab，ca巴西布坦坦研究所Ciclo Celular特别顾问B 毒素、免疫反应和细胞信号传导中心（CeTICS），巴西c巴西圣保罗大学数学和统计学院ar t i cl e i nf o文章历史记录：2017年4月18日收到2017年7月18日收到修订版，2017年保留字：特征选择基准布尔格组合优化a b st ra ct在本文中，我们介绍featsel，一个框架的基准测试的特征选择算法和成本函数。该框架允许用户将搜索空间作为布尔格来处理，并以C++为核心编码以提高计算效率。此外，featsel包含Perl脚本，用于添加新的算法和/或成本函数，生成随机实例，绘制图表并将结果组织成表格。此外，该框架已经提供了数十种用于基准测试实验的算法和成本函数我们还提供了说明性的例子，其中featsel优于流行的Weka工作台在UCI机器学习存储库的数据集上的特征选择过程©2017作者。由爱思唯尔公司出版这是CC BY许可下的开放获取文章（http://creativecommons.org/licenses/by/4.0/）中找到。代码元数据代码元数据描述当前代码版本v1.3。用于此代码版本的代码/存储库的永久链接https://github.com/ElsevierSoftwareX/SOFTX-D-17-00031法律代码许可证GNUGeneralPublicLicensev3使用git的代码版本控制系统使用C++、Perl的编译要求，操作环境依赖性C++编译器，make，Perl解释器，gnuplot，flex（可选），bison（可选），groff（可选）链接到开发人员文档/手册github.com/msreis/featsel/wiki技术支持电子邮件marcelo. butantan.gov.br1. 动机和意义在机器学习和统计学的上下文中，特征选择是从特征集合S中选择子集X S的过程，使得X包含用于给定分类器设计过程的最相关特征。如果X的相关性可以通过成本函数c（S）R+来度量，则特征选择被简化为称为特征选择问题的组合优化问题，其中目标是最小化c（X）。众所周知，特征选择问题是NP难的[1];然而，在成本函数c测量估计误差并且使用固定数量的样本计算的情况下，由于“维数灾难”，c地址：Avenida Vital Brasil，1500邮政编码05503-900，圣保罗，巴西。电子邮件地址：marcelo. butantan.gov.br（M.S. Reis）。http://dx.doi.org/10.1016/j.softx.2017.07.005样本限制增加c（X）的点，导致子集链，其图形描述U形曲线。在特征选择问题的一个特殊情况下考虑了这一观察：给定一个实例S， c，如果对于每个XY Z S，c（Y）max c（X），c（Z）成立，则S， c也是U曲线问题的一个实例[2]。虽然U曲线问题也是NP难的[3]，但许多特征选择算法依赖于将搜索空间建模为该问题的实例的策略：其中有次优算法（即，不保证找到全局最小值的算法），如顺序向前搜索（SFS）[4]，以及最优算法，包括U曲线搜索（UCS）算法[5]。然而，在实际的特征选择实例中，子集链不具有完美的U形曲线，因为这样的链经常呈现振荡（即，一次或多次违反U形曲线假设）。根据这些振荡的水平，只有穷举搜索才能保证全局最小值，尽管有一些次优算法，2352-7110/©2017作者。由爱思唯尔公司出版这是CC BY许可下的开放获取文章（http://creativecommons.org/licenses/by/4.0/）。可在ScienceDirect上获得目录列表SoftwareX期刊主页：www.elsevier.com/locate/softx194M.S. Reis等人/SoftwareX 6（2017）193⊆设计来规避这个问题;一个例子是最佳优先搜索（BFS）[6]。然而，成本函数c的不同选择会影响特征选择算法的性能。例如，在子集链具有朝向全局最小值降低成本的趋势（可以通过汉明距离成本函数近似的条件[3]）的情况下，诸如SFS的贪婪策略将是特征选择的良好选择。然而，如果实例的全局最小值分布在整个搜索空间中，并且它们的链描述了完美的U形曲线，则诸如UCS的算法将适合于最优搜索。此外，如果这些实例在其链中具有振荡（当使用平均条件熵来估计形态算子时会发生这种情况[7]），则可以使用诸如BFS之类的算法进行次优搜索，其动态包括回溯。一旦代价函数和算法的适当选择对特征选择过程的性能具有相关影响，新的方法就不断被提出。然而，通常这些新的算法和/或成本函数被引入它们自己的实现，并且经常使用不同的编程语言和/或数据结构，这使得它们的实验基准测试变得困难在与实现相关联的常数和/或多项式因子没有被算法和成本函数的渐近复杂性压倒的情况下，这会加剧此外，提供特征选择过程的通用机器学习工作台也不被设计为允许包括新算法和成本函数（例如，MLC++库[8]）或不考虑上述恒定因素的减轻来实现Weka工作台[9]）。因此，需要一种有效的标准化环境，以允许容易地编程和测试不同的算法和成本函数，特别是将新提出的解决方案与良好建立的解决方案（所谓在本文中，我们介绍featsel，一个开源框架的基准的特征选择算法和成本函数。这个框架的核心是用C++编写的，允许用户将搜索空间作为布尔格（P（S），）;这个属性是非常有帮助的，因为特征集合S的子集X可以被有效地描述为X的特征向量，从而允许应用布尔运算。此外，featsel包括辅助Perl脚本，以最大限度地减少在添加新算法和/或成本函数，生成随机实例，绘制图形和组织基准测试结果到LaTeX和超文本标记语言（HTML）表中的工作。该框架在GNUGPL v3许可下，可在github.com/msreis/featsel下载。本文的其余部分组织如下：在第2节中，我们对框架的主要功能进行了高级描述在第3节中，我们介绍了整个软件体系结构，其中包括通过类图和其主要类的描述对系统的图形组件概述在第4节中，我们展示了一些说明性的例子，其中对于不同大小的数据集，featsel的性能与Weka工作台的性能进行了在第5节中，我们指出了这个框架在机器学习学术界内外的预期影响。最后，在第6节中，我们对这项工作做了一些总结，并指出了未来改进的想法。2. 软件描述Featsel是被设计为辅助特征选择算法和成本函数之间的系统比较的框架：对于给定的成本函数，每个算法针对相同类型的一组或多组实例来执行（例如，具有相同数量的特征），并且将所获得的结果平均化并组织到汇总表中。单个特征选择过程的执行由框架核心（主程序）提供;该核心由主辅助脚本包装，该主辅助脚本负责启动每个算法执行，组织结果并生成输出文件。featsel的核心是通过基于类的、对象的面向建模选择面向对象的编程语言来编写核心代码是C++。由于基准测试是我们的主要目标，从计算效率的角度来看，与Java等解释型语言相比，C++具有更好的回报，这与减少可能影响算法和成本函数之间比较的常量因素有关主要的辅助脚本是用Perl编写的，并为用户提供了使用存储在临时输入目录中的实例或通过可定制模块生成随机实例的可能性还有其他Perl脚本可以帮助包含和删除算法和成本函数。在补充材料第2节中，我们提供了如何使用所有这些脚本的详细示例;更多信息可以在featsel'suser guide中获得这个框架版本（v1.3）包括几十个算法和成本函数的实现，它们都列在表1和表2中。3. 软件构架正如我们在前一节中所描述的，框架核心是在面向对象编程范式下设计的。核心中的主要对象交互如下：功能是系统的元素;几个元素的聚合产生一个集合，而每个集合可以与它的子集相关联;子集可以被聚集成子集的集合，并且还与成本函数相关联;解算器由子集的集合组成（例如，以存储被访问子集的列表）和计算子集成本的成本函数。成本函数和求解器都是抽象类，这意味着它们分别作为成本函数和算法的具体实现的图 1，我们将这些交互总结成一个类图，它包含六个主要类。下面讨论这些类的最相关属性元素这个类表示一个功能，并具有存储和检索其相关属性的属性和方法。例如，如果在使用k个样本的形态算子估计期间特征在于窗口的像素中，则该类的对象存储k个整数的阵列，每个整数对应于那些样本中的每个样本中的该像素的观测值。ElementSet。在特征选择过程中考虑的组成完整集合S的元素的集合这个类具有从dat（平面文件）或xml（扩展标记语言）实例文件加载给定集合S为此，它依赖于辅助解析器类DatParserDriver和XmlParserDriver。元素子集。完整集合S的子集X表示为这个类的一个实例，用于在搜索空间中显式表示其对应的节点，并计算X的成本。子集表示是通过M.S. Reis等人/SoftwareX 6（2017）193195（1）⊆⊆P表1 featsel框架的此版本（v1.3）中可用的算法列表。对于每个算法，它在featsel核心中突出显示了它的参数代码，它在框架架构中的类名，以及它最初发表的出版物的引用;算法变元码类名原始出版物最佳优先搜索BFSBFS[6]美国穷举搜索es穷举搜索[3]第一章无规链RC随机链没有一顺序后向浮点搜索sbfsSBFS[10个国家]顺序向后搜索SBSSBS[第十一届]顺序前向搜索SFSSFS[4]美国顺序前向浮点搜索SFFSSFFS[10个国家]条件互信息spec_cmiSpecCMI[12个]U曲线分支定界UBBUcurveBranchandBound[3]第一章U型曲线搜索UCSUCurveSearch[五]《中国日报》表2featsel框架版本（v1.3）中可用的成本函数列表。对于每个成本函数，突出显示了其在featsel核心中的参数代码，其在框架架构中的类名，以及其最初发布的出版物的参考;成本函数变元码类名原始出版物阿塔什帕斯-加尔加里-布拉加-内托-多尔蒂AbdAbd[13个国家]基于相关性的特征选择CFSCFS[14个]条件互信息CMI条件互信息[12个]显式代价函数显式显式没有一汉明距离汉明距离汉明距离[第十五条]平均条件熵mce平均条件熵[七]《中国日报》互信息mi互动资讯[16个]其他常数函数点点没有一子集和多项式约简子集和SubsetSum[3]第一章裁剪凸包裁缝定制凸壳[17个]使用X的特征向量，其为函数χX：S→{0，1}定义为：4. 说明性实例χX（s）=1，如果s X0，否则。为了显示使用featsel的特征选择过程的效率，我们用不同数量的特征和样本的数据集进行了计算实验。那些布景一旦子集的这种表示是二进制的，布尔运算就可以通过实现并集、交集和补码运算的这类方法在χX上执行收藏. 这个类实现了ElementSubset类的对象集合。这个类的主要目的是提供一种方法来存储已经被被访问的，并且还登记沿着搜索过程找到的最小成本的子集。为此，该类具有添加、删除和搜索存储在给定集合中的子集成本函数这是一个抽象类，也就是说，一个充当框架内实现成本函数的“脚手架”的类为此，成本函数具体类从CostFunction继承了一个虚拟构造函数和一个虚拟方法来计算给定子集的成本因此，用户必须编程她/他自己的成本函数的内部逻辑例如，对于图1所示的HammingDistance类， 1，可以计算并返回作为成本方法的参数接收的子集X与该类的构造函数作为参数接收的常数子集Y之间的汉明距离。解决者一个抽象类，用于帮助实现框架内的算法。一个算法具体类继承了一个名为get_minima_list的虚方法，该方法启动一个搜索，其确切过程必须由用户编程。表示在搜索期间要使用的成本函数的对象必须作为一个名为set_parameters的方法的参数传递给算法，该方法必须在get_minima_list之前调用。例如，根据图1所示的图。 1，穷举搜索的实例化对象可以用汉明距离的对象初始化，然后计算所有X S的成本函数。在这种情况下，最小成本的元素将是用于实例化成本函数对象的子集Y S从加州大学欧文分校（UCI）机器学习库获得[18]。将每个数据集离散化（如果需要），转换为特征数据格式，并使用Weka工作台（版本3.6.1）的Java API和特征框架进行特征选择。这两个程序都采用了各自的基于相关性的特征选择（CFS）代价函数以及穷举搜索（ES）或BFS算法。重要的是要注意，对{CFS，ES}或{CFS，BFS}应该在featsel和Weka中产生相同的搜索结果，因为两者 实 现 相 同 的 算 法 和 成 本 函 数 。 所 有 实 验 都 在 具 有 64 个AMDOpteronTM 内 核 （ 每 个 内 核 2.1GHz ） 、 256GB RAM 和Ubuntu的计算机服务器中进行14.04.5 LTS操作系统。在 表 3 中 ， 我 们 总 结 了 在 八 个 不 同 数 据 集 （ 心 律 失 常 、Gisette、Madelon、Musk2、Optdigits、Promoters、波形1和Zoo）上进行的实验的结果从计算的角度来看，对于所有考虑的数据集，featsel框架始终优于Weka工作台。这个组件可以通过一个名为compare_featsel_against_Weka.pl的Perl程序在其他计算环境中重现，该程序包含在这个框架版本中。featsel框架的功能在补充材料第4.1和4.2节中进一步这些额外的示例采用SFS和UCS算法，并且还说明了由基准测试程序自动生成的图。5. 影响在机器学习领域，新的特征选择算法不断被提出。然而，缺乏有效的软件选择，系统地比较这些新的196M.S. Reis等人/SoftwareX 6（2017）193图1.一、 类图在统一建模语言（UML）的featsel核心，包括关键类属性和方法。在该图中，示例性地示出了成本函数具体类汉明距离和算法具体类穷举搜索的推导。穷举搜索的对象可以使用汉明距离的对象作为成本函数来实例化表3Weka工作台和featsel框架的此版本（v1.3）之间的性能比较。对于每个数据集和每个软件，所示算法和成本函数执行20次。之后，计算所需计算时间的平均值和偏差BFSBFSaOptdigits64 5620 BFSa麝香2166 6598 BFSa心律失常279 452 BFSaMadelon500 2600 BFSaGisette5000 6000 BFSa0.5353± 0.00500. 0540± 0。00070.3733 ± 0.00610. 0098± 0. 00030.8988 ± 0.03150. 3748± 0。03441.0985 ± 0.02130. 3722± 0。00451.8305 ± 0.34120.5777± 0. 00541.4246 ± 0.02070.6118± 0. 0100365.8821± 52.9896130. 5534± 6。3817一 BFS在正向执行，并在五个非改进节点后终止搜索。反对已经确立的解决办法的想法妨碍了对这些解决办法的适当评价。因此，这个框架可以是有用的，以协助在这一领域的新方法的发展此外，特征选择是上下文相关的，这意味着对于给定的一组问题（即，对要采用的可能的成本函数的约束），更适合于解决它们的算法可以戏剧性地改变-通过因此，一个有效的，系统的基准之间的不同对算法和成本函数有可能提高选择最适合的一个功能选择问题在特定的上下文中。最后，由于特征选择是许多领域所需的过程（仅举其中几个：生物信息学，统计学，图像处理），处理、数学形态学等），我们相信featsel框架有可能在机器学习学术界之外得到广泛的使用。6. 结论在本文中，我们介绍了featsel，一个开源的，C++编码的框架，以协助基准的算法和成本函数，用于解决特征选择问题。featsel包括辅助Perl脚本，以帮助添加新的租金和/或成本函数，生成随机实例，绘制图表，并将基准测试结果组织到LaTeX和HTML表格中。此外，我们还强调了CFSCFSCFSCFSCFS数据集#特性样本数量算法成本函数Weka required time（s）featsel required time（s）动物园波形115211015000ES一CFSCFS0.4010± 0.00540的情况。1331±0。0029CFSM.S. Reis等人/SoftwareX 6（2017）193197通过计算实验，它在UCI机器学习库的八个数据集上的特征选择过程中超过了Weka工作台目前，我们正在努力添加新的算法和成本函数，以及新类型的图形。featsel的其他正在进行的改进包括：使用简化的二进制决策图来更有效地表示从搜索空间中删除的元素[19];在主要Perl辅助脚本中并行化特征选择过程调用;将用于实现并行算法的方法纳入框架致谢感谢Ronaldo F。Hashimoto和Edu Sanchez- Castro的评论和建议，Leo K. Iwai对本文进行了修订。我们也感谢匿名评论者的有益评 论 。 这 项 工 作 得 到 了 CNPq 的 奖 学 金 #142039/2007-1 和 资 助#305705/2014-8的支持，以及资助#2013/03447-6，#2013/07467-1，#2015/01587-0和#2015/01587-0的支持。#2016/25959-7，圣保罗研究基金会（FAPESP）。附录A.补充数据与本文相关的补充材料可以在http://dx.doi.org/10.1016/j.softx.2017.07.005上找到。引用[1] Guyon I ， Elisseeff A. 介 绍 变 量 和 特 征 选 择 。 J MachLearn Res2003;3（Mar）：1157-82.[2] Ris M，Barrera J，Martins-Jr DC. U曲线：布尔格上U形代价函数的分支定界优化算法，用于特征选择问题。Pattern Recognit2010;43（3）：557-68.[3] Reis MS ， Minimization of decomposable in U-shaped curves functionsdefined on poset chains巴西圣保罗大学数学与统计研究所论文（葡萄牙文），2012年。[4] 惠 特 尼AW 。 非 参 数 测 量 选 择 的 一种 直 接 方 法 IEEETrans Comput1971;20（9）：1100-3.[5] Reis MS，Ferreira CE，Barrera J，U曲线优化问题：对原始算法的改进和时间复杂度分析，2014年。ArXiv预印本ArXiv：1407.6067，pp. 1-30[6] 放大图片作者：John H.用于特征子集选择的包装器。Artif Intell1997;97（1-2）：273-324.[7] 放大图片作者：Martins-JrDC，Cesar-Jr RM，Barrera J.W-算子窗口设计的最小化平均条件熵。 PAAPattern Anal. Appl. 2006;9（2）：139-53.[8] [10]杨文，王文. MLC++：一个C++机器学习库。第六届人工智能工具国际会议。IEEE;1994年。p. 740-3[9] Holmes G，Donkin A，Witten IH. Weka：一个机器学习工作台。第二届澳大利亚和新西兰智能信息系统会议论文集。IEEE;1994年。p. 1比5。[10] Pudil P，Novovicová J，Kittler J.特征选择中的浮动搜索方法。PatternRecognit Lett1994;15（11）：1119-25.[11] Marill T，Green D.论识别系统中受体的有效性。IEEE Trans. Inform.Theory1963;9（1）：11-7.[12] NguyenXV，Chan J，Romano S，Bailey J.基于互信息的特征选择的有效全局方 法 。第 20 届 ACM SIGKDD 知 识 发 现 和 数 据 挖 掘 国 际 会 议 论 文 集 。ACM;2014. p. 512-21[13] Atashpaz-Gargari E，Braga-Neto UM，Doughterer.改进的分枝定界算法求解U型曲线优化问题。在：IEEE基因组信号处理和统计国际研讨会。IEEE;2013年。p. 100比1。[14] Hall MA，离散和数值类机器学习的基于相关性的特征选择，Tech。代表，怀卡托大学，计算机科学系，2000年1-10。[15] Hamming RW.错误检测和错误校正码。Bell Syst Tech J1950;29（2）：147-60.[16] BarreraJ ， Cesar-Jr RM ， Martins-Jr DC ， Vêncio RZN ， Merino EF ，Yamamoto MM，Leonardi FG，Pereira CAB，del Portillo HA. 从红细胞内发育周期的动态表达信号构建恶性疟原虫的概率遗传网络。在：微阵列数据分析方法V.Springer;2007。p. 11-26[17] Reis MS，Barrera J.通过简化U曲线问题解决数学形态学问题。 数学形态学及其在信号和图像处理中的应用国际研讨会. Springer;2013. p. 49比60[18] 利 希 曼 UCI 机 器 学 习 库 。 Irvine ： University ofCalifornia ， School ofInformationandComputerSciences;2013URLhttp://archive.ics.uci.edu/ml。[19] Bryant RE.基于图的布尔函数操作算法。IEEETrans Comput1986;100（8）：677-91.[20] Dagum L，Menon R. OpenMP：用于共享内存编程的行业标准API。IEEEComput Sci Eng1998;5（1）：46-55.
我的内容管理
展开
