ICF算法：基于圆锥函数的大规模分类算法

SoftwareX 8（2018）59原始软件出版物ICF：一种基于圆锥函数的大规模分类算法Emre Cimena，b，*，Gurkan Ozturka，b，Omer Nezih Gereka一 Anadolu University，Faculty of Engineering，26555，Eskisehir，Turkeyb土耳其埃斯基谢希尔阿纳多卢大学计算智能和优化实验室（CIOL），26555ar t i cl e i nf o文章历史记录：2017年11月29日收到2017年12月5日接受保留字：多面体圆锥函数数学规划分类机器学习a b st ra ct增量圆锥函数（ICF）算法是基于数学规划理论发展起来的一种求解分类问题的算法。该算法在计算速度方面改进了以前的基于锥函数的分类器构造方法。此外，增量步骤避免了子类数量的先验知识（这是该分类算法的聚类步骤中的必要参数）。测试结果表明，ICF平均比以前的版本快近3倍，而不牺牲准确性。Python 2.7实现和软件解释。©2017由Elsevier B.V.这是一篇CC BY-NC-ND许可下的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）的网站上进行了介绍。代码元数据当前代码版本v1.0此代码版本使用的代码/存储库的永久链接https://github.com/ElsevierSoftwareX/SOFTX-D-17-00094法律代码许可证MIT使用Git的代码版本控制系统使用Python的软件代码语言、工具和服务（2.7）必须安装编译要求、操作环境&依赖性Numpy、Sklearn和Guesthouse包。如果有开发人员文档/手册链接无问题支持电子邮件ecimen@anadolu.edu.tr1. 动机和意义从数据中提取有意义的信息是许多现代应用中的关键步骤[1]。数据挖掘、聚类和分类工具是解决手势、人脸、指纹、字符识别等问题的关键技术。典型的方法是将问题分解为特征提取和分类器优化步骤，尽管存在更集成的挖掘方法。本研究的重点是“分类化”问题。分类器的子类可以被放入基于数学规划的分类器的类别中，涉及分类器优化期间的线性或整数规划。在文献[2]中，通过求解线性规划，提出了一种线性分离算法。在[3]中，超平面被用作分离表面。文[4]通过定义非光滑非凸误差函数引入了Max-Min分离的概念非光滑性在分类中的应用原文DOI：http://dx.doi.org/10.1016/j.dsp.2017.11.010。通讯作者。电子邮件地址：ecimen@anadolu.edu.tr（E. Cimen）。https://doi.org/10.1016/j.softx.2017.12.0032352-7110/©2017由Elsevier B. V.发布在[5]中进行了讨论分类文献中优化的其他用法可以在[6本文的求根方法是在文献[1，10]中首次构造的使用这些形状，进行了各种扩展和应用，例如PCFs与最大-最小分离的组合基于聚类的PCF算法被应用于一些现实生活中的问题，如心律失常分类[14]和手势识别[15]。本文提供了有关如何使用分类器的算法信息、来源和插图，这些信息在本特刊的DSP部分中详细介绍[16]。我们将这种改进称为通过避免两个缺点来改进基于k-Means的 PCF算法[12基于k-Means的 PCF算法的第一个缺点是必须初始确定聚类数k。新的ICF算法不需要猜测，并发现集群的数量递增。基于k-Means的PCF算法的第二个缺点是关于问题的大小，这是一篇CC BY-NC-ND许可下的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）的网站上进行了介绍。可在ScienceDirect上获得目录列表SoftwareX期刊主页：www.elsevier.com/locate/softx*60E. Cimen等人/SoftwareX 8（2018）59Fig. 1. ICF算法的流程图[16]。用线性规划（LP）求解。与其结构相关，基于k-Means的PCF算法求解线性约束与数据点数量一样多的LP。当数据量很大时，模型需要处理太多的约束，导致LP解决方案耗时。ICF算法可以不需要对每个圆锥函数求解LP;在某些情况下，它用代数方法求出圆锥分离函数，在另一些情况下，它通过巧妙地消除不必要的约束，用较少的约束求解LP。上述情况是根据称为“纯度”的参数确定的，该参数针对数据集的每个子类进行评估。该算法要么找到类“pure”以避免所有LP步骤并解析地构造单个锥，要么找到数据聚类内的区域，“最大纯部分”完全消除这些数据点，以便仅通过集合的壳部分更快地实现锥的增加的软件是ICF算法的实现，允许在与分类问题相关的使用这个软件，我们已经实现了与以前版本类似的训练和测试结果，但运行时间缩短了约64%该软件还发现自动集群的数量。我们声称ICF算法可以用于大数据集的实际问题。第二部分介绍了ICF算法软件，并给出了伪代码和说明.第3节解释了软件影响，第4节总结。软件的科学背景在本特刊随附的DSP部分中提供[16]。2. ICF算法软件描述该软件由三个文件组成使用该软件，可以使用ICF算法对数据进行分类。它可以读取每行表示数据点，每列表示特征。最后一列必须指明类别标签（数字）。例如，如果数据集中有5个类，则类标签必须为{1，2，3，4，5}。训练集和测试集可以单独给出。对于这种类型的使用，必须使用“ICF-培训-测试”文件。还可以获得k-折叠交叉验证测试结果，对于这种类型的使用，ICF的算法2在“ICF-Purity”文件中实现“”ICF-Purity“”文件中的函数因此，程序必须根据测试类型从“ICF-Training-Test”或“ICF-fold”运行ICF算法使用Python 2.7实现，并与MIT许可证共享。该软件的要求是Numpy，Sklearn和Guideline Python包。详细的用户指南可以从软件链接中找到。ICF算法是算法1和算法2的嵌套组合。ICF算法流程图如图1所示。在文件“ICF-训练-测试”和“ICF-文件夹”中实现的[16]中的算法1在文件“ICF-Purity”中实现的[16]中的算法2算法1和算法2的数学细节在相应的DSP文章[16]中给出。2.1. 说明性示例在本小节中，我们通过示例数据集提供了一个说明性示例来更好地解释该算法[12]。从图2中可以看出，所有类的凸包都是重叠的。此外，绿色标记类有两个独立的子集。这使得分类更加困难。首先，确定训练集和测试集 之后，选择将要被分类的第一类（集合A：图中的黄色标记）。 2），其余类被认为是集合B。黑色E. Cimen等人/SoftwareX 8（2018）5961--=∈图二、R2 中具有3个类的说明性示例数据集[12]。（关于此图例中颜色的参考解释，请读者参考本文的网络点属于图中的B。3.第三章。之后，计算集合A的半径并用于找到集合A的纯度。如果纯度不大于预设阈值，则使用k-Means算法将集合A分为两个聚类：标记为深黄色和浅黄色（图2）。 3）。假设图1中浅黄色标记的簇的纯度为0.0001。 三是不够纯。ICF算法的数据剔除过程是剔除最大半径对应的浅黄色标记簇内的点，在图4中，请注意淡黄色集群的中心部分被消除了。这减少了圆锥函数分类器编程的运行速度。另一种情况是相同数据集的绿色标记类这个类中的数据被分成三个区域，所以k3对于算法1-步骤2，r 1、 2、 3 图图5示出了两个纯子集（a和b），其中理想锥在没有LP迭代的情况下进行代数评估。然而，这个绿色标记的类的底部不是纯的，在消除其纯中心之后，LP需要组合几个锥体以形成如图1所示的分类。 5（c）.62E. Cimen等人/SoftwareX 8（2018）59图三. A组的两个子集群：暗黄色和浅黄色[16]。(For对本图图例中所指颜色的解释，读者可参考本文的网络见图4。浅黄色标记簇的数据消除。(a)（b）消除之前，（b）消除之后[16]。(For对本图图例中所指颜色的解释，读者可参考本文的网络版。）用于绿色标记类别的分类器的组合在图6中示出（通过执行算法1的步骤3）。对于该示例，绿色标记类别的最终分类器g（ x）被获得为在算法1-步骤2中找到的圆锥函数的逐点最小值g（x）= min {g1（x），g2（x），g3（x）}.3. 影响本文的主要动机是提出一个成功的和快速分类器（PCF）的信号处理和数据分析社区，其理论基础是在所附的DSP特刊[16]。光子晶体光纤是一种新的方法，图六、根 据 算 法 1 [ 16 ] 的 步 骤 3 组合两个代数和一个基于LP的圆锥函数。（关于此图例中颜色的参考解释，请读者参考本文的网络版本成功地与流行的分类器竞争，包括著名的SVM。PCF的一个缺点（及其基于k-均值的PCF的应用通过这项工作，引入了两种新的计算改进（如第1节，第2节和[16]中所述）。观察到的改进，以保持分类准确性，同时减少64%的执行时间（根据实验数据集）。有人认为，对于需要分类的所有可能的应用，拟议的ICF方法有望提供一个合理的替代方案。现在，随着其更快的实现，鼓励科学家和实践工程师将提供的算法应用于其他经典分类器（如朴素贝叶斯，SVM等）中的分类器为了显示ICF算法的效率和潜力，表1中列出了训练集和测试集的准确率。基于k-Means的PCF算法是一种新型方法，其性能优于几种最先进的分类器，包括SVM [12]。从表1中可以看出，ICF算法在更少的时间内实现了与基于k-Means的PCF算法4. 结论所提出的软件（ICF）的实施，以改善已经成功的PCF分类可能的应用程序，需要处理的大型数据集。改进是通过以下方式实现的：图五、从LP获得的分类器。（a）g1（x）（b）g2（x），（c）g3（x）。（关于此图例中颜色的参考解释，请读者参考本文的网络版本。E. Cimen等人/SoftwareX 8（2018）5963表1ICF算法在现实生活数据集上的训练和测试集准确率，以及运行时间[16]。数据集提出算法k-均值基于PCF火车测试时间（秒）K火车测试时间（秒）鲍鱼[17]48.8047.7016.02548.5046.740.90页面块[18]89.1086.0827.30393.7581.1398.00卫星[19]87.4086.10181.50687.6086.10372.20机场班车[20]93.4893.472671.20396.4296.5013038.50封面类型[21]61.4353.601242.33467.7852.452972.08在方法上消除（i）几个数据点和（ii）偶尔圆锥函数迭代的必要性。减少的数据点计数导致更简单（因此更快）的优化问题。在某些情况下，当子类的纯度足够好时，仍然不需要迭代地组合圆锥形状，但是单个解析圆锥表示足以对该纯群进行分类。这一观察结果也大大有助于算法的速度。据观察，所提出的方法平均比当前PCF实现快3倍[16]。所提出的方法的最后一个优点是，它在方法上获得了子集群的数量（k-均值步骤的k），这应该预先提供给基于k-均值的PCF的先前实现中的算法[13]。与这些改进一起，我们向需要在其大型数据集上进行最先进分类的科学家和实践工程师介绍了一种可用的软件实现。确认本文得到了阿纳多卢大学科学研究项目委员会的支持，项目编号为1506F499、1603F122、1605F524和1605F435。引用[1] 厄兹蒂尔克湾求解分类问题的一种新的数学规划方法。[博士论文]，EskisehirOsmangazi大学科学研究所;2007年土耳其文。[2] Bennett KP，Mangasarian OL.两个线性不可分集的鲁棒线性规划判别。OptimMethods Softw1992;1（1）：23-34.[3] Astorino A ， Gaudioso M. 多 面 体 可 分 离 性 贯 穿 广 义 LP 。 J OptimTheoryAppl2002;112（2）：265-93.[4] 巴吉罗夫最大最小可分性Optim Methods Softw2005;20（2 -3）：271- 90.[5] Astorino A，Fuduli A，Gorgone E.分类问题中的非光滑性。Optim MethodsSoftw 2008;23（5）：675-88.[6] Astorino A，Fuduli A，Astorino M.机器学习中分类问题的非线性规划。In：AIPconferenceproceedings-numericalcomputations：theoryandalgorithms，vol. 1776，No. 1，Pizzo Calabro，Italy，18-25 June 2016，2016.p. 一比四[7] Astorino A，Fuduli A.半监督学习中的支持向量机多面体可分性。J OptimTheory Appl2015;164（3）：1039-50.[8] Astorino A ， Gaudioso M. 分 类 问 题 的 椭 球 分 离 法 。 Optim MethodsSoftw2005;20（2-3）：267-76.[9] 黄杰苏肯斯，王S，霍尼格J，迈尔A.用截断的距离核进行分类. IEEE跨神经网络学习系统2017;PP（99）：1-6。[10] GasimovR，Ozturk G.通过多面体圆锥函数分离 OptimMethodsSoftw2006;21（4）：527-40.[11] Bagirov A，Ugon J，Webb D，Ozturk G，Kasımbeyli R.提出了一种新的基于多面圆锥曲线和最大-最小可分性的分段线性分类器。 TOP2013;21（1）：3-24.[12] Ozturk G ， Ciftci T. 基 于 聚 类 的 多 面 锥 函 数 分 类 算 法 。 J Ind ManagOptim2015;11（3）：921-32.[13] OzturkG，Bagirov AM，Kasimbeyli R.一种基于多面体圆锥分离的增量式分段线性分类器。 MachLearn 2015;101（1/3）：397-413.[14] Cimen E，Ozturk G.基于k-均值的多面体圆锥函数算法的心律失常分类。2016年计算科学和计算智能国际会议，NV，美国，2016年12月14日至17日。第798-802页。[15] 西门E基于多面圆锥函数分类器的手势识别[硕士论文]，阿纳多卢大学，科学研究所;2013年在土耳其。[16] Cimen E，Öztürk G，Gerek ÖN.大规模分类问题的增量圆锥函数算法。数字信号处理（SIonRep.研究）2017年。http://dx.doi.org/10.1016/j.dsp.2017.11.010网站。[to出现]。[17] 鲍鱼数据集，https://archive.ics.uci.edu/ml/datasets/Abalone。[18] 页面块分类数据集，https://archive.ics.uci.edu/ml/datasets/Page+Blocks+Classification。[19] Statlog（Landsat卫星）数据集，https://archive.ics.uci.edu/ml/datasets/Statlog+（Landsat+Satellite）。[20] Statlog（Shuttle）data set，https：//archive.ics.uci.edu/ml/data，sets/Statlog+（Shuttle）.[21] Covertype数据集，https://archive.ics.uci.edu/ml/datasets/Covertype。