文摘

提出了一种增量式基因表达式编程的分类器。其主要功能包括使用基分类器组成的两级合奏形式的基因和metagene的上层分类器形式。这种方法使我们能够处理大数据集通过控制计算时间使用数据还原机制。用户可以控制属性的数量用于诱导基分类器以及用于诱导metagenes基分类器的数目。优化参数设置阶段,一种方法基于正交试验设计原则,提出了允许统计评价不同因素对分类器性能的影响。此外,该算法漂移检测配备了一个简单的机制。算法的详细描述是紧随其后的是广泛的计算实验。其结果验证方法。计算实验结果表明,该方法为多与几个先进的增量分类器。

1。介绍

通过数据挖掘学习环境仍然是一个重要的研究挑战。提出了很多方法、算法和技术近年来处理数据挖掘任务。这些努力的一个重要组成部分侧重于挖掘大数据集和数据流。真实数据集的规模带来的障碍,一方面,和约束的可用资源来执行数据挖掘任务,包括时间和计算资源,另一方面,是不容易克服的。额外的并发症,除了上述复杂问题,经常遇到由于非平稳的环境。

最有效的方法之一,挖掘大数据集和数据流是使用在线或增量的学习者。在线学习假设严格处理数据流。在线学习者应该有以下属性1]:(我)单次的数据。(2)每个例子是加工过的非常快,在持续一段时间。(3)无时间限制的学习:分类器应该提供最好的答案在每一刻的时间。

增量学习是理解为一个稍宽的概念,与在线学习。增量学习不仅可以处理数据流也与大数据集的存储在数据库中使用“一”或“按原样”的方法可以更有效的比使用传统的“批处理”学习者,即使没有概念漂移检测。增量学习的一个重要特点是他们的能力更新目前使用模型只使用新提供个人数据实例,而无需再加工所有过去的实例。

事实上,使用增量学习者,经常,唯一可能的方法来提取任何有意义的知识。通常对于当代数据库是一个常数流入的新数据实例。因此,数据库中发现知识需要不断更新,这对经典的学习者通常是一个不可行的任务。数据流,甚至存储数据集,可能是受到所谓的概念漂移的影响。在上述情况下,在线或增量学习是必要的。

在本文中,我们提出一个新版本的增量分类器基于基因表达式编程(GEP)数据简化和metagene最后,上层,分类器。分类器使用GEP-induced表达式树,产生令人满意的或非常好的结果的分类精度。我们的方法使用GEP-induced表达式树构建学习者能够处理大型数据集的环境和概念漂移的现象。剩下的纸是组织如下。节2一个简短的调查提供的相关结果。节3我们描述一个新版本的建议的方法。部分4包含一个详细描述验证计算实验和讨论的结果包括建议如何处理现实生活中的数据集通过正交试验设计技术。部分5包括未来的研究的结论和观点。

2。相关工作

满足所需的性能的在线学习者在文献中提出了几种方法和技术。最成功的包括抽样、窗口和漂移检测。抽样假设只使用一些数据实例或实例的可用的数据集的一部分。在[14)与概率的随机抽样策略提出了训练集的一些实例。后来,这个想法是长在15]。提出了一些更高级的抽样策略(16]。抽样策略对分类精度的影响研究(17]。

因为它一直在观察的审查18),数据采样方法对机器学习研究了几十年。根据上述文章,近年来进展的方法可以大致分为随机抽样包括密度偏差和非均匀采样方法,主动学习的方法,这是semisupervised学习的类型,和进步的抽样方法,可以视为上述两种方法的结合。

抽样滑动窗口模型密切相关。滑动窗口可以看到运行对一个潜在的集合的一个子集。几个版本的方法中可以找到19- - - - - -21]。我们的想法是,数据流的分析是基于最近的实例只有数量有限的数据实例,通常等于窗口大小,用来产生一个分类器。在机器学习中,这个概念可以用于增量挖掘关联规则的22]。滑动窗口技术的另一个有趣的应用程序被称为高实用模式挖掘(23]。

嘈杂的环境或环境概念漂移的关键问题是何时和如何应采用当前的模型。可能的解决方案包括明确的漂移检测模型(参见调查Ditzler et al。24])或显式分区方法(见,例如,25])。

最成功的增量挖掘数据流的方法是使用漂移检测技术。漂移检测的目的是标识数据分布的统计特性随时间的变化。这种变化通常被称为概念漂移。减少学习者的恶化造成的精度概念漂移,一个可以应用变化检测测试和修改或替换一个学习者发现漂移(见,例如,[26,27])。上述方法被称为积极的解决方案而不是一个被动的人,不断地重新训练模型的基于最近的样本。最近几个极端学习机(ELM)讨论了增量学习方法。例如,[28)提出了一个概念叫FP-ELM遗忘参数。最近的调查数据流挖掘可以发现在24,29日]。

在增量模型,还有那些基于利用系综分类器。合奏学习者涉及几个模型的结合。他们的预测可以以某种方式相结合,例如,平均或投票到达最终的预测。合奏学习者提出了数据流挖掘,其中,在30.- - - - - -34]。

技术用于构造增量分类器之一是基因表达式编程(GEP)。介绍了基因表达式编程(35]。实施项目表示为线性染色体固定长度的字符串,在随后的健身评价,演变成表达式树,无需任何用户干预。这个特性使得GEP-induced表达式树一个方便的模型构造分类器(36]。

一个进步的基本实施分类器可以通过结合GEP-induced弱分类器分类器集合。在[37)两个著名的整体技术、装袋和提高,被用来加强实施分类器的泛化能力。另一个方法来构建GEP-based提出了分类器集成技术(38]。想法是构造薄弱(基地)从不同的属性子集分类器控制这些子集之间的多样性通过应用小生境技术的一种变体。进一步扩展和变异GEP-induced系综分类器进行了讨论(39),提出了增量学习和基于集群学习的想法。方法从GEP-induced弱分类器构造系综分类器也研究[40]。

3所示。提出了增量GEP-Based分类器

在本文中,我们扩展和改善增量GEP-based分类器提出了(41]。在上面的纸,GEP被用来诱导基分类器。基分类器构造分类器的整体服务。这样一个整体要求应用程序的集成技术比如多数投票,装袋或提高。回顾整体施工方法的在线学习可以在找到42]。或者,可以构造metaclassifier后堆放泛化的概念(43]。在我们的案例中,这样一个metaclassifier称为metagene。

我们的方法遵循步骤提出了(41)的分类和各自的metagenes建设基地。学习的最佳分类器使用GEP算法工作如下。假设一个训练数据集,每个向量数据集有一个正确的标签代表的类。在最初的步骤,计算每个属性的最小和最大价值和生成一个随机的染色体。每个染色体都是由单个基因分成两部分,在最初的首尾相接法(35]。头的大小是由用户提供建议的大小不小于中的属性数据集的数量。大小的尾巴是计算 。染色体的大小 。对于每个基因,符号的头部分是随机选择的函数集,或者不是,XOR,也和终端类型的集合 ,的价值在属性的范围和是一个关系操作符。尾部分的符号都是终端。在图1基因的一个例子。开始位置(位置 )染色体对应的表达式树的根(或者,在这个例子中)。然后,下面的每个函数的分支连接有很多作为函数的参数数量,在我们的例子中。以下符号在染色体附加到分支机构在给定的水平。过程完成时,每个分支与终端完成。染色体的符号形式的数量表达式树表示的终止点。讨论的例子,终止点 ;因此进一步符号是没有意义的,是用的在图1。规则对应的染色体图1是

如果 或不 然后类1。

引入变异的人口使用下列遗传算子:(我)突变,(2)换位的插入序列元素(转换),(3)根换位(RIS调换),(iv)一点重组,(v)两点重组。

染色体突变可以发生在任何地方。这意味着我们认为一点突变概率,称为突变率,一个符号在染色体发生了变化。对于功能符号取代另一个随机选择的函数;否则为 一个随机的关系操作符 ,一个属性 ,和一个常数在的范围被选中。注意,突变可以改变各自的表达式树因为一个参数的函数可能突变为一个函数的两个参数,反之亦然。

换位代表染色体的一部分转移到另一个位置。这里我们考虑转位因子的两种。在换位的插入序列(是)三个值都是随机选择:染色体的位置(开始),序列的长度和目标网站的头部,两个位置之间的一条纽带。则在削减债券定义的目标站点和插入序列复制到网站的插入。下游序列复制的元素了,结束的时候,尽可能多的符号长度的转座子。观察到由于目标站点的头部,新创建的个人总是语法正确但也会显著地重塑树。对于根换位,头部的位置是随机选择的,选择这个职位后第一个函数;这是开始的RIS元素。如果没有找到函数,然后执行没有变化。选择插入序列的长度。 The insertion sequence is copied at the root position and at the same time the last symbols of the head (as many as RIS length) are deleted.

两种复合两父染色体 , 随机选择和两个新的子染色体吗 , 形成。一点重组的情况下,在一个位置是随机生成的,父染色体是由这个位置分割成两部分。孩子的染色体(分别 )形成含有第一部分来自哪里(分别 )和第二部分(和 )。在两点重组两个位置都是随机选择的交换和重组之间的符号位置两个父染色体之间形成两个新的子染色体。再次观察到,在这两种情况下,新成立的染色体是语法正确,无论是否复合头寸从头部或尾部。

在《学习全球经济展望》中,个人选择和复制到下一代基于他们的健身和精英主义的轮盘赌抽样保证生存和克隆的下一代最好的染色体。

进一步的细节在《运营商和全球经济展望》《学习可以在全球经济展望》(39,40,44]。

对于一个固定的训练集和固定的基因适应度函数计算向量的比例正确的分类: 在哪里 在生成的人口基因可以创建一个对应于人口metagenes创建一个分类器。这个想法是这样的。让人口的基因,每个基因的识别 。创建metagenes从我们定义的函数作为布尔的上面并设置终端相当于基因的标识符。例如,metagene如图2利用三个基因g1、g2和g3。 为一个固定的属性向量每个终端(即。,gene) has a Boolean value and thus the value of metagene can be computed. For the metagene从图2和 我们有 同样是在(1),一个固定的训练集和固定metagene适应度函数计算向量从测试集分类正确的比例: 增量GEP与metagenes分类器在轮工作。在每一轮,一大块数据用于诱导基因诱导metagenes和另一块。块大小是一个增量分类器参数。它的作用是控制的频率更新模型以适应概念漂移。这种方法的主要假设如下:(我)类标签的实例属于第一和第二块在一开始就已经知道了(2)类标签的实例属于块3号,和所有的块后,会立即显示在每个实例的类被预测(3)除所有实例属于前两块分类一个接一个的“自然”

基于上述假设,在2),下列程序实现。在每一轮的训练数据用于创建人口基因,下一块数据用于创建metagenes并选择一个最佳的人口metagene表示 ,和下面的块由metagene测试 。在下一轮中, , 和下一块用作 。为进一步比较,增量分类器从[2)和Inc-GEP1表示。

计算实验证实Inc-GEP1执行得很好。与最先进的增量分类表明,该方法优于,在大多数情况下,现有的解决方案的分类精度。不幸的是,Inc-GEP1遭受高对计算资源的需求,在很多情况下,可能会阻止它从大数据挖掘数据流和数据集的环境。上述情况背后的原因之一是,Inc-GEP1没有配备任何适应机制提供更新模型只有在检测到概念漂移。相反,该模型诱导后每次重新分类的实例。

提供更大的灵活性和缩短计算时间与Inc-GEP1相比我们提出两个措施。第一个是一个广泛的数据简化的选择,二是提供一些适应机制,以减少所需的学习者的数量更新期间计算。遵循随机抽样的概念提出了经典的(nonincremental)学习者41),提出了增量学习,用户有一个选项来设置以下值主要参数:(我)块大小( )(2)基分类器的数量( )(3)数量的属性用于诱导基因(底部 )(iv)百分比的实例用于诱导基因(底部 )(v)百分比的实例用于诱导metagenes ( )

上述每个选项可以用来控制和有效地减少或增加计算时间的整个过程,包括学习模型和预测类标签传入的实例。设置的值块大小决定了学习者更新频率。规模较小导致增加更新的数量。在我们的例子中,这个数字可以通过减少之后在这一节中描述的提出适应机制。基分类器的数目用于诱导metagenes完成工作所需计算时间的影响。较少的基分类器,然而,减少由此产生的metagenes的准确性。属性用来诱导基因基础的数量应该小于原始属性的数量的每个实例数据集。一旦设置,它导致随机选择尽可能多的属性需要从所有数据属性的集合。随机的属性发生每次当一个基分类器的感应。这意味着,对于每个基分类器的组合属性诱导多次随机。 Setting percent of instances used to induce the base genes and metagenes results in randomly sampling chunks used to induce the base genes and metagenes, respectively. Such filtering results in diminishing the number of instances used to induce each of the base classifiers and each of metagenes, by a given percentage.

除了数据简化措施,我们也建议引入简单的适应机制减少不必要的学习者更新。后使用前两个数据块诱导组初始的基分类器和当前metagene ( ),使用下面的计划。属于第三块类标签的实例预计使用和类的平均精度预测块( )是记录。在下一步中,第四块是用来预测类标签吗和平均预测的准确性计算并记录。如果 ,然后更新学习者使用和产生新的电流 。,当前metagene是用来预测类标签的实例属于下一个传入的数据块。重复这个过程,直到所有块的分类实例。不平等在哪里 认为,当前metagene使用块替换为一个新的诱导和 。上面的适应机制和ADAPT1表示。另外,第二个版本的适应机制,作为ADAPT2表示,可以使用。下ADAPT2当前metagene后被一个新诱导的平均分类精度连续两块比前任的准确性metagene诱导产生的块。使用ADAPT1显示为算法的过程3省略ADAPT2和理由,是相似的。增量分类器与数据简化和ADAPT1机制进一步称为Inc-GEP2。这种分类器配备ADAPT2机制进一步称为Inc-GEP3。

诱导基分类器和metagenes显示为程序算法1和2,分别。在这两种情况下,适应度函数是类标签的准确性预测计算各自的数据块。

4所示。计算实验结果

评价该方法的性能,我们进行了计算实验了一批有代表性的公开课程基准数据集包括大型数据集和数据集通常用来测试增量学习算法。实验中使用的数据集如表所示1。

在表2实验设置用于Inc-GEP2和Inc-GEP3显示。有主要参数影响提出了分类器的性能。块大小指的是一个一个的实例数量分类,没有使用当前metagene中断。的数量是指随机选择的数量属性用于诱导每个基因。还原速度反映了两个实例使用的百分比用于诱导metagenes诱导基因和实例。的分类器是指基分类器的数目(基因)。上述参数设置值的方法解释。其他设置包括GEP(设定的迭代次数 )和应用遗传算子的概率(设置为(2)已经在整个实验相同。

在表3平均分类精度Inc-GEP1、Inc-GEP2 Inc-GEP3显示。精度和标准偏差计算平均值获得的一步运行参数设置如表所示2。Inc-GEP1块大小和数量的属性是相同的对于Inc-GEP2 Inc-GEP3。在Inc-GEP1,然而,并没有减少对基因的比例用于诱导基分类器和metagenes。此外,在Inc-GEP1基分类器和metagenes诱导使用全套的属性。

参数值表所示2通过正交试验设计被选择(OED)方法。因为有四个主要影响因素分类器的性能,已经决定使用一个L9正交阵列识别的影响对分类器性能不同的独立变量。为每一个变量设置的值水平,水平值的选择是任意的,但基于常识。

决定使用《牛津英语词典》方法之前一直比较意味着每个数据集分类精度值和每个组合的主要因素在分析组合。因此,对于每一个数据集,我们有组样本,每个都包含通过运行考虑分类器的分类精度获得次为每一个因素的结合。零假设的单向方差分析表明样品在所有组都来自相同的人口意味着值表明,所有被认为是数据集除了银行营销数据集,应该拒绝零假设。这一发现保证感性因素寻找最佳组合的值为每个数据集。

正交试验的过程和选择参数值如下所示的海洋数据集的例子。类似的过程已经被应用到所有的数据集。

在表4因子(术语)水平的正交阵列与大海在实验中使用数据集所示。在表5响应值代表使用显示Inc-GEP2分类器分类精度。第一列显示因素水平数。未来十列包含响应值。最后一列的平均响应。

响应表信噪比表所示6表明关键作用最大化的讨论比戏剧属性在数据表的数量7显示响应表分类精度意味着表明精度发挥最大化的关键因素下的数量分类器的数量和属性。信噪比的响应表包含一行每个因素水平的平均信噪比,三角洲和排名。三角洲的区别是最大和最小平均响应的因素。响应表意味着显示效果的大小的区别特征平均最高和最低的一个因素。排名在响应表允许快速识别哪些因素有最大的效果。然而,所有因素对反应有显著影响。这是确认的主要影响情节意味着如图3。主要影响情节由策划意味着每一个变量的值。每个变量的线连接的点。当线水平(平行于x轴),没有主效应。响应的意思是相同的所有因素的水平。另一方面,当线不水平,主要影响现在和响应的意思是不一样的在所有因子的水平。陡峭的直线的斜率,主要影响的大小。

作为数据表5表明,最好的因素水平组合对海洋的数据集窗口(块)规模2500,2属性诱导基分类器,用于诱导基因和10%的实例,分别metagenes, 30分类器。类似的分析已经完成所有考虑数据集,以找出最佳的参数组合(因素)的值。

正交阵列分析也可以进行的计算时间。例如,在海洋数据集的情况下各自的响应表计算时间意味着表明关键作用在减少计算时间扮演的窗口大小和数量分类用于构造。各自的主要影响情节显示考虑因素如何影响海洋数据集计算时间图所示4。在这个图”的意思是“指次秒需要对一个实例进行分类。在表8比较平均计算时间的考虑数据集和设置的参数表2显示。各自的值引用100次秒需要分类实例的考虑算法运行在戴尔精密3520工作站Xeon处理器和16 GB的RAM。列Speed-up1和Speed-up2包含加速因素比较Inc-GEP1 Inc-GEP2和Inc-GEP1 Inc-GEP3,分别。从表可以观察到8有显著差异在运行算法所需计算时间的比较。平均而言,提出Inc-GEP2分类器/ 2倍快与增量基因表达式编程有metagenes没有数据减少(Inc-GEP1)。此外,提出Inc-GEP3分类器是,平均而言,比控制算法Inc-GEP1快7倍多。恰当地评估Inc-GEP2和Inc-GEP3还必须评估他们的表现的分类精度。假设方差相等,单向方差分析可以观察到零假设,指出这三个意思置信水平下精度是相等的成立。因此,备择假设,指出不是所有的考虑意味着相等应该被拒绝。上面的发现证实了费舍尔和图基测试。

在表9比较建议的GEP-based增量分类器与一些文献报道的增量分类器的分类精度是显示。缩写用于增量分类如下:FTDD,费舍尔测试漂移检测;IncSVM增量支持向量机;EDDM,早期漂移检测方法;IncN-B增量朴素贝叶斯;KFCM,在线与模糊c内核基于距离的分类器;IncEnsemble增量合奏;和鱼,统一选择算法实例。

从表9可以看出,该分类器表现良好和有竞争力几个其他方法。在一些情况下,GEP-based增量分类器比早些时候可用的解决方案。

5。结论

论文的主要贡献是提出了增量与metagenes基因表达式编程分类器和数据减少。metagenes增加了分类精度的概念而减少数据允许控制计算时间。该方法扩展了早些时候增量GEP-based分类器(2]。此外,扩展的版本包含一个简单的漂移检测机制允许更有效地处理数据流。

另一个重要的新奇介绍了使用正交试验设计原则建立分类器的参数值。方法允许我们轻易评价统计的重要性主要参数(因素)显示通过主要情节和影响各自的响应表的关键因素及其影响分类器的性能和信噪比。

一个广泛的计算实验证实,该分类器提供了更好的性能在所需的计算倍相比,它的早期版本。同时,它提供了类似的结果分类精度。算法通过调整的可能性也提供了可伸缩性计算次用户的需求,这可能是一个有用的功能的成本甚至可能有点降低分类精度。

比较建议的GEP-based增量分类器与一些文献报道的增量分类器的平均分类精度证明我们的方法提供了令人满意的解决方案,在很多情况下优于现有方法。该方法可能是有用的在单程内存有限的数据分析和大数据处理模型支持治疗中的大数据流环境越来越需要(45]。

未来的研究将集中精力将更复杂的漂移检测机制和进一步提高效率,实现算法在并行环境中。

首字母缩写词和缩写词

创业计划:	基因表达式编程
是:	顺序插入
RIS:	根换位
TR:	训练集
流行:	种群的基因
mg:	Metagene
适合:	健身功能基因
适合:	适应度函数为metagenes
ch:	块大小
注:	数量的基分类器
拿拿淋:	数量的基分类器
RB:	百分比的实例用于诱导基分类器
RM:	用于诱导metagenes百分比的实例
公元前:	基分类器
ADAPT1 ADAPT2:	两个版本的适应过程
Inc-GEP1:	增量式分类器
Inc-GEP2:	与适应ADAPT1增量分类器
Inc-GEP3:	与适应ADAPT2增量分类器。

数据可用性

之前报道的数据集的数据被用来支持这项研究,公开在UCI机器学习库(参见[36钞票])对银行营销、身份验证、乳腺癌,糖尿病,心脏,形象,互联网广告,电离层。航空公司的数据集是公开在打开机器学习网站(https://www.openml.org/)。国际象棋和卢森堡数据集可从里边的Zliobaite(见[4])。电力数据集从UCI Repository-Massive公开可用的在线分析(见[15])。海洋和Usenet2数据集是公开可从华金Vanschoren et al。(见[41])。这些数据集引用文本中相关的地方。

的利益冲突

作者宣称没有利益冲突。