混合二元帝国主义竞争特征选择算法和禁忌搜索方法使用基因表达数据

文摘

成千上万的基因组成的基因表达数据中扮演重要角色的分类平台和疾病诊断。因此,它是至关重要的选择的一个小子集特征在大量的基因表达数据。最近,许多研究人员致力于特征选择使用不同的计算智能方法。然而,在选择信息基因的进展,许多计算方法面临困难选择小子集对癌症分类由于大量的基因(高维度)和少量的样品相比,嘈杂的基因,基因无关。在本文中,我们提出一种新的混合算法HICATS把帝国主义竞争算法(ICA)执行全球搜索和禁忌搜索(TS),进行精确搜索。为了验证该算法的性能HICATS,我们已经测试了它著名的基准10日基因表达数据集分类与维度不同的从2308年到12600年。我们建议的方法的性能是优于其他相关工作,包括传统的二进制版本优化算法的分类精度和选定的基因的数量。

1。介绍

DNA微阵列技术,可以同时测量成千上万个基因的表达水平在生物领域的组织和生产数据库基于基因表达数据的癌症(1]在癌症研究有很大潜力。因为传统的癌症诊断方法是不准确的,基因表达数据已被广泛用于识别癌症生物标记物与肿瘤密切相关,这可能是强烈补充传统的病理评价来提高癌症诊断和分类的准确性(2)和改进的理解癌症的发病机理的发现新疗法。因此,它的应用已经得到普及癌症基因表达数据分类、诊断和治疗。

由于高维度的基因表达数据和少量的样品相比,嘈杂的基因,和不相关的基因,传统的分类方法不能有效地应用于基因分类由于贫穷的分类精度。基因数据的固有财产,需要高效的算法来解决这个问题在合理的计算时间。因此,许多监督机器学习算法,如贝叶斯网络、神经网络和支持向量机(svm)与特征选择技术相结合,用于处理基因数据(3]。基因选择的过程,选择最有预测力的信息基因的最小子集相对类使用一个分类模型。特征选择问题的目标是最大化分类能力和减少基因子集分类样本准确。从基因数据的最优特征选择问题是np难问题。因此,它是使用metaheuristics方法更有效,如自然启发的计算,来解决这个问题。近年来,metaheuristic算法基于全球搜索策略而非本地搜索策略显示在解决组合优化问题的优势,和许多metaheuristic方法已经应用于特征选择,例如,遗传算法(GA),粒子群优化(PSO),禁忌搜索(TS)和人工蜂群(ABC)。

Metaheuristic算法作为一种随机搜索技术,不能保证每次都找到最优解。因为一个metaheuristic算法经常被困到一个不成熟的解决方案,最近的趋势已经转向几种混合方法的研究。Kabir et al。4]介绍了一种新的混合遗传算法融合一个本地搜索来调整搜索特征选择。沈et al。5)提出了一种混合算法对特征选择和TS提高分类精度。接下来,李等人提出了一种混合算法和遗传算法6]。不幸的是,实验结果没有获得较高的分类精度。Alshamlan等人提出的ABC解决特征选择。他们第一次尝试应用ABC算法在分析微阵列基因表达结合最小冗余最大相关性(mRMR) [7]。然后,他们还杂化ABC和GA算法选择微阵列癌症分类和遗传特性的目标是整合两种算法的优点8]。ABC算法获得的结果在一定程度上改善,但少量的基因无法获得精度高。壮族et al。9]介绍了一种改进的二进制PSO的全球最好的粒子被重置为零位置在其适应度值三个连续的迭代后并没有改变。有大量的选择基因,该算法获得的结果在许多数据集分类精度100%。

所以,在本文中,我们专注于帝国主义竞争算法受社会政治行为,是一种新的群智能优化算法来解决从基因表达数据特征选择的过程。它始于一个初始种群和有效地搜索解空间通过一些特别设计的运营商收敛于最优或算法的解决方案。虽然ICA已经被证明是一个潜在的解决优化问题的搜索技术,它仍然面临着一些困难,ICA容易陷阱到当地最适条件,不能得到更好的结果。禁忌搜索(TS)作为局部搜索技术可以弥补ICA算法的不足。它有能力避免收敛到局部最优准则通过一个灵活的存储系统包括愿望和禁忌列表。由于本地搜索的TS, TS的收敛速度很大程度上取决于最初的解决方案。人口在ICA的并行性将有助于TS找到有前途的地区的快速搜索空间。所以混合算法HICATS有效地结合了ICA的优点和TS,在特征选择显示了优越性。

剩下的纸是组织如下。部分2描述了相关算法结合通用ICA和TS。部分的过程3阐述了提出HICATS包括框架,个人表示,帝国的初始化,殖民地同化,适应度函数评价。部分4描述了参数设置和实验结果基于几个基准基因数据集包括HICATS之间的比较结果和其他算法的变体。最后,给出了结论5。

2。相关的算法

2.1。通用的帝国主义竞争算法(ICA)

ICA是一种基于随机优化技术,提出了由Atashpaz-Gargari和卢卡斯(10]。ICA,最近metaheuristic优化技术之一,是受社会政治行为。回顾去年的研究表明,这种方法没有被用于解决基因表达数据进行特征选择。与其他进化算法一样,ICA始于一组初始的解决方案(国家)称为人口。每个人的人口是一个数组叫做“国家”在ICA和GA“染色体”。帝国组成的国家将是一个帝国主义或殖民地。强大的国家被认为是帝国主义和殖民地被分配到每个帝国基于每一个帝国主义国家的力量。后生成帝国,殖民地由相关的帝国主义同化这将使殖民地越来越走向有前途的地区。如果殖民地比其帝国主义向帝国主义时,然后交换位置的帝国主义和它的殖民地。作为一个帝国拥有更多的权力,它吸引了更多的殖民地和帝国主义之间的竞争ICA的帝国的基础。 The powerful imperialists are reinforced and the weak ones are weakened and gradually collapsed when the imperialist has no colony. Finally, the algorithm converges to the optimal solution. The flowchart of ICA is shown in Figure1。ICA已经成功地应用在许多领域:模糊系统控制、函数优化、神经网络训练,和其他应用程序的问题。

2.2。禁忌搜索算法

提出了禁忌搜索(TS) 1986年全球(11),这是一个著名的本地搜索算法,来解决各种困难的组合优化问题。算法从最初的解决方案和评估的健康值给定的解决方案。然后可以获得一组相关的可行解决方案通过一个简单的修改,给出解决方案。这一修改通过一个简单和基本的变换称为移动。如果最好的这些邻居不在禁忌列表,然后选择它作为新的当前的解决方案。禁忌列表跟踪之前探索解决方案,防止TS回顾一遍,以避免陷入局部最优。创建一个移动增加多样性即使它比当前的解决方案。同时,介绍了禁忌列表,用来记住更好的本地邻居已被搜索和将被忽视。创建可行的解决方案的一个子集后根据禁忌和评估目标函数列表。选择最好的最优解作为下一个解决方案。 This loop is stopped when the stopping criteria are satisfied.

3所示。提出HICATS

作为全球搜索metaheuristic ICA算法在解决组合优化问题揭示了优势;然而,人口的多样性将会极大地减少一些代之后,该算法可能导致过早收敛。TS为本地搜索技术可以利用当前解决方案的邻居得到更好的候选人,但它会花很多时间来获得全局最优或全球最佳。把TS到ICA是当地的改进策略的方法可以保持种群的多样性,禁止误导局部最优。每个二进制编码的字符串(国家)表示一组基因,这是由适应度函数评价。TS是应用于帝国主义在每个帝国选择新帝国主义,避免过早收敛。该算法框架HICATS可以如图2,进一步描述如下。

步骤1。算法的设置参数和初始化国家的二进制表示0和1。评估每个国家的人口利用支持向量机(SVM)分类器。健康是决定SVM的分类精度的比例和数量的特征子集。然后帝国生成取决于他们的健身价值。

步骤2。应用TS在每个帝国帝国主义。生成和评估帝国主义的邻居。选择新的解决方案根据禁忌列表和愿望标准取代旧的帝国主义。

步骤3。应用学习机制在殖民地一样Baldwinian学习(提单)机制(12]。找出不同的基因之间的帝国主义和它的一个殖民地;然后使用随机生成的学习概率来决定选择基因的数量为殖民地。这一策略使殖民地走向帝国主义。

步骤4。帝国主义及其殖民地之间比较客观值相同的帝国。交换帝国主义及其殖民地当殖民地的位置比它的帝国主义。

第5步。计算一个帝国的总功率和比较所有帝国;然后消除最弱的帝国当它就失去了所有的殖民地。

步骤6。如果终止条件(预定义的max迭代)不满足,回到步骤2。否则,输出最优解在当前人口和停止算法。

很明显,HICATS集成特征选择的两个完全不同的搜索策略,也就是说,手术在ICA可以探索新的地区和为TS提供理想的解决方案,虽然TS可以利用帝国主义的邻居更好的候选人,根据记忆系统避免陷入局部最优。评价函数,将支持向量机的准确性与选定的基因的数量特征子集,助攻HICATS找到最突出的特性减少冗余。一种可靠的基因选择方法应该有更高的分类精度和分类包含更少的冗余基因。更多的可理解性,HICATS每个组件的详细信息将在以下小节中描述。

3.1。个人代表和帝国的初始化

在本文中,我们利用随机方法生成一个二进制编码的字符串(国家)由0、1和它的长度等于基因表达数据的维度。值在国家表明这个基因的同时,应选择值0表示相应基因的无用。为了清楚地了解这些操作,我们举一个例子来解释。假设基因数据有10维(10特点:,,,,,,,,,);这个国家用0和1初始化。字符串的部分模板是10等于基因数据的维度。1的字符串是随机生成的,数字是5。因此,特征,,,,形成一个国家选择如图3。

后生成的人口,我们应该评估和初始化帝国由帝国主义国家和殖民地。一个国家的健身价值估计的适应度函数: 在这项研究中,假设初始人口规模;最强大的国家选为帝国主义和剩下的根据国家分配给这些帝国帝国主义的力量作为他们的殖民地。按比例分配的殖民地帝国主义,规范化的健身价值帝国主义被定义为 在哪里和的规范化的健身价值吗帝国主义和健身价值分别th帝国主义。这个帝国主义被定义为归一化功率 的归一化功率帝国主义揭示了帝国主义的力量。所以拥有殖民地th帝国将 在哪里菌落总数和吗是初始的殖民地帝国。生成每一个帝国,我们随机选择每个帝国主义殖民地,给他们。图1显示每个帝国包括帝国主义和殖民地的人口普查的初步使用相同的颜色。很明显,大帝国主义者有更多的殖民地而较弱的更少。最殖民地和帝国主义1形成最强大的帝国。

3.2。殖民地同化

在HICATS,同化是一个重要的操作,可能是一个重大的帮助在殖民地的发展进化。摘要连续提单的概念引入的HICATS殖民地帝国主义同化。这一战略可以利用一些特殊的微分信息从帝国主义,即帝国主义之间的微分信息和殖民地,这表明一个更有效的方法学习优秀的解决方案。它可以定义如下: 不同国家的操作,1减去0,结果是1;1减去1,结果是0;0减去1,结果是0;减去0,结果是0。的学习速率是一个随机生成的实数,意味着选择的比例差异的基因。是操作员,轮对最接近的整数,它的参数表示选择的基因。为了减少国家的维度,我们的研究采用随机生成的模板根据大尺寸的帝国主义和殖民地。帝国主义(IM)的五个特点,,,,六个特色和它的一个殖民地,,,,,在一个帝国,二进制模板(BT)的维数是6。模板生成的殖民地从英国电信营业外,用BTF。因为即时通讯功能基因的数量小于模板BT, BT的IMBT只需要一部分。描述它是如何工作的,我们将说明以下数值例子。帝国主义的代表;它的一个殖民地编码;然后被描述为微分信息。很明显,不同的基因的数量是3(1)的数量,根据参数从不同的基因集,选择基因的数量是2的特性和是选择。与此同时,是由随机策略是英国电信的营业外。从英国电信和获得吗等于BTF。在这个过程中,公司成为国家的特性,,和同化有限公司结合不同的基因有限公司和我之间有5个特点,,,,是生产。因此,吸收有限公司是由提单操作如图所示4。

3.3。适应度函数

基因表达数据的特征选择需要考虑分类准确性和选定的信息基因的数量。因此,适应度函数定义如下: 在这是leave-one-out-cross-validation (LOOCV)分类精度的一个国家(基因子集)获得的支持向量机模型。是最佳的尺寸问题;换句话说,它是为每个样本的基因总数选择基因的数量吗。我们使用的参数和测量分类精度的重要性,选择基因的数量,分别。分类精度比数量更重要的选择基因和设置的参数满足约束条件如下:和。

3.4。TS-Based本地搜索

在HICATS,每个殖民地可以吸收其帝国主义,然后改善自己。因此,整个算法的收敛速度。然而,经典的ICA很容易陷入局部最优。因此,开发是由TS搜索附近的更好的解决方案目前的帝国主义和逃离局部最优。如何产生解决方案和禁忌列表在TS算法非常重要。在我们的研究中,一个比特的营业外的解决方案是利用附近的生产解决方案。例如,如果基因表达数据与10个维度和当前国家,附近的解决方案可以从当前的解决方案获得通过TS-based算法如图5。

4所示。实验

4.1。基因表达数据集和参数设置

本文除了SRBCT由连续的图像分析,得到其余的基因微阵列数据集得到的寡核苷酸技术。目前,没有标准的处理方法的基因表达数据。因此,我们设计了一个有效的执行特征选择算法HICATS提高分类精度。基因表达数据的数据集包含10块,这可以从下载http://www.gems-system.org/。数据表中列出的描述1,其中包含的数据集名称和详细的表达式。表2给出了相关样本,基因,和类。这些数据集包含二进制类和多类数据包含成千上万的基因。

HICATS参数值如表所示3。非常清楚的是,该算法的参数小于二进制粒子群优化(全局搜索)。因此,参数设置对HICATS的影响相对较小,算法的鲁棒性更好。人口的大小会影响算法的性能和计算效率。大量的国家需要更多的计算时间完成特征选择,如果数量太小,虽然该算法可以发生在一个相对短的时间内,算法的性能得不到保证。因此,人口和迭代的中间值的大小选择15 - 50,分别。由于人口组成的帝国主义和殖民地,帝国主义者也需要确定的数量。如果帝国主义者的数量是1,HICATS算法转化为单一物种进化算法代替multisubpopulation而如果帝国主义者的数量太大,殖民地的数量无法保证。帝国主义者的数量为4在我们的实验中。节3.3的参数和介绍并给出值的范围。为了保证大于的值,和设置为0.8和0.2在我们与相同参数设置的EPSO算法(13]。

4.2。实验结果

本文使用混合算法HICATS将ICA和TS基因表达数据进行特征选择。TS是嵌入在ICA防止方法陷入到一个局部最优,而应用TS在帝国主义可以提高性能和加速收敛的TS。

实验结果包括分类精度和选定的功能基因的数量获得了HICATS 10独立运行数据集包括11 _tumors 9 _tumors SRBCT,白血病,白血病2,DLBCL, Prostate_Tumor, Lung_Cancer Brain_Tumors 1, Brain_Tumors 2,如表所示4,5,6。发现HICATS的分类精度达到100%,小于10的白血病基因1,白血病2,DLBCL和小于20 SRBCT选择基因。平均分类精度超过92.22%的所有数据集9 _tumors除外。换句话说,强烈表明,HICATS可以有效地选择信息从高维基因,二进制类,或多级分类的数据集。所有最好的分类结果,选定的基因是不到10除了_tumors 9和11 _tumors,平均分类结果,有益的基因子集也不到10除了9 _tumors 11 _tumors, SRBCT数据集。此外,所有数据的标准偏差小于5 9 _tumors和11 _tumors除外。分类精度和选择的基因,不难发现HICATS是一种有效的特征选择算法和生成算法基因从基因表达数据子集。

为了验证该算法的有效性,首先,我们将比较的性能与纯HICATS ICA使用支持向量机作为分类器在相同的实验条件;然后,我们将比较HICATS与其他优化算法在几个指标分类数据集。比较结果包括最优分类准确性和选定的基因的数量得到HICATS和ICA在桌子上7。这两个算法的区别只是是否每个包含本地搜索机制TS。很明显,HICATS执行所有数据集比原始ICA。因此,ICA结合TS可以有效地跳出局部最优和HICATS达到更好的性能。表8相比其他方法获得的实验结果从文学和HICATS拟议的方法。各种方法包括non-SVM和MC-SVM与我们的方法被用来比较。实验结果列在表中8被从壮族等人进行比较(9]。Non-SVM包含最近邻居法(9,14,15),反向传播神经网络(16),和概率神经网络(17]。MC-SVM包括one-versus-one和one-versus-the-rest [18],DAG-SVM [19),该方法由韦斯顿和沃特金斯(20.,21),该方法通过谎言和歌手(20.,22]。很明显,我们建议的方法HICATS获得的所有分类精度最高10基准数据集。non-SVM的平均分类精度最高,MC-SVM HICATS是97.14,93.63,和97.81,分别。白血病数据集的1,白血病2,SRBCT, DLBCL,分类精度可以达到100%。的平均分类精度HICATS IBPSO似乎是相同的;然而,所选基因HICATS明显低于那些IBPSO列在表中9因为降维机制是不同的。IBPSO算法主要利用乙状结肠函数的值来确定基因被选中。在初始迭代,0和1的概率是0.5,一个标准的s形的函数没有任何约束,没有修改。然后,在接下来的迭代中,概率可能受到速度矢量;然而,0和1的概率大多是维持其应用在基因表达数据由于其高维度和一个大的搜索空间。基因的数量最小化总数的一半基因在高维数据使用标准的c形的函数。因此,穆罕默德et al。13]引入了修正乙状结肠函数增加比特在一个粒子的位置的概率是零和最小化选择基因的数量。在我们的算法中,随机生成的二进制模板是用来减少维度选择基因在每一代由于同化机制,从他们的帝国主义殖民地学习很多不同的基因。因此,不难发现,收敛的速度是非常快和选定的数量的差异基因HICATS和IBPSO之间是巨大的。

的收敛图最好,平均分类精度通过HICATS 9 _tumors 11 _tumors SRBCT, DLBCL数据所示6和7。可以看出,最好的分类精度达到100%不到10迭代SRBCT DLBCL和10至20代。因此,HICATS具有更快的收敛速度和快速达到最优解。

5。结论

本文混合HICATS包含二进制帝国主义竞争算法和禁忌搜索算法进行特征选择和使用SVM HICATS one-versus-the-rest作为评估者的基因表达数据的分类问题。这项工作有效地结合了两种不同的搜索机制算法的优点获得基因表达数据的分类精度高的问题。一般来说,分类性能HICATS IBPSO一样好;然而,HICATS优于IBPSO和其他基因选择的方法。帝国主义在我们的算法中,为了避免过早收敛,TS嵌入局部搜索策略在ICA TS应用于帝国主义在每个帝国都可以利用帝国主义的邻居速度收敛和协助帝国主义进化。实验结果表明,我们的方法有效地分类样本与减少功能基因。在未来的工作中,帝国主义竞争算法结合使用其他智能搜索策略选择的基因。

相互竞争的利益

作者宣称没有利益冲突。

引用

1. h . Feilotter”,生物学家指南DNA微阵列数据的分析,“美国人类遗传学杂志》上,卷71,不。6,1483 - 1484年,2002页。视图:出版商的网站|谷歌学术搜索
2. r·西蒙“DNA微阵列表达数据,分析”最佳实践和研究:临床血液学,22卷,不。2、271 - 282年,2009页。视图:出版商的网站|谷歌学术搜索
3. h . Alshamlan g·德尔,y Alohali”比较研究癌症的分类方法使用微阵列基因表达谱,”学报第一国际会议上先进的数据和信息工程(别名“13)卷,285课堂讲稿电气工程施普林格,页389 - 398年,2014年。视图:谷歌学术搜索
4. m . m . Kabir m . Shahjahan, k . Murase”一种新的基于局部搜索的混合遗传算法对特征选择,”Neurocomputing,卷74,不。17日,第2928 - 2914页,2011年。视图:出版商的网站|谷歌学术搜索
5. 问:沈,W.-M。史,和w .香港,“混合粒子群优化和禁忌搜索方法选择基因肿瘤分类使用基因表达数据,”计算生物学和化学,32卷,不。1,53-60,2008页。视图:出版商的网站|谷歌学术搜索
6. 美国李、吴x和m . Tan“基因选择使用混合粒子群优化和遗传算法,”软计算,12卷,不。11日,第1048 - 1039页,2008年。视图:出版商的网站|谷歌学术搜索
7. h . Alshamlan g·德尔,y Alohali”MRMR-ABC:混合基因选择算法对癌症分类使用微阵列基因表达分析,“生物医学研究的国际604910卷,2015篇文章ID, 15页,2015年。视图:出版商的网站|谷歌学术搜索
8. h . m . Alshamlan g·h·巴德尔,和y . a . Alohali”基因蜜蜂殖民地(GBC)算法:一种新的微阵列基因选择方法癌症分类”计算生物学和化学卷,56 49-60,2002页。视图:出版商的网站|谷歌学术搜索
9. L.-Y。壮族,H.-W。Chang C.-J。你和学术界。杨:“改进的二进制PSO特征选择使用基因表达数据,”计算生物学和化学,32卷,不。1,29-37,2008页。视图:出版商的网站|谷歌学术搜索
10. 大肠Atashpaz-Gargari和c·卢卡斯,“帝国主义竞争算法:一个算法为优化受到帝国主义的竞争,”《2007年IEEE国会在进化计算(CEC ' 07)IEEE,页4661 - 4667年,新加坡,2007年9月。视图:出版商的网站|谷歌学术搜索
11. f·格洛弗,“未来的路径为整数规划和人工智能的链接,”电脑与行动研究,13卷,不。5,533 - 549年,1986页。视图:出版商的网站|谷歌学术搜索|MathSciNet
12. m .锣、l .焦和l .张“Baldwinian学习在克隆选择算法的优化”,信息科学,卷180,不。8,1218 - 1236年,2010页。视图:出版商的网站|谷歌学术搜索
13. m . s .穆罕默德,s . Omatu s•德里m .吉冈a·阿卜杜拉和z易卜拉欣,”一个改进的二进制粒子群优化基因选择分类癌症类”算法对分子生物学第十五条,卷。8日,2013年。视图:出版商的网站|谷歌学术搜索
14. b . v . Dasarathy神经网络的概念和技术:最近的邻国(NN)规范,IEEE计算机协会出版社,1991年。
15. t .封面和p·哈特,“最近邻模式分类,”IEEE信息理论,13卷,不。1,-,1967页。视图:出版商的网站|谷歌学术搜索
16. t·m·米切尔机器学习麦格劳-希尔,1997年。
17. d . f . Specht“概率神经网络”,神经网络,3卷,不。1,第118 - 109页,1990。视图:出版商的网站|谷歌学术搜索
18. c . Orsenigo和c·切利”,通过离散Multicategory分类支持向量机”,计算管理科学》第六卷,没有。1,第114 - 101页,2009。视图:出版商的网站|谷歌学术搜索|MathSciNet
19. j·c·普拉特:Cristianini, j . Shawe-Taylor“大型多级分类保证金无进取心的人,”先进的神经信息处理系统,12卷,不。3、547 - 553年,2010页。视图:谷歌学术搜索
20. l . Chin-Jen”比较多类支持向量机方法,”IEEE神经网络,13卷,不。2、415 - 425年,2002页。视图:出版商的网站|谷歌学术搜索
21. j·韦斯顿,“多支持向量机”《欧洲人工神经网络(ESANN ' 99)研讨会上,1999年28页。。视图:谷歌学术搜索
22. k .谎言和y歌手”的易学性和设计输出编码多类问题,“机器学习卷,47号2 - 3、201 - 233年,2002页。视图:出版商的网站|谷歌学术搜索

版权

版权©2016王Shuaiqun et al。这是一个开放分布式下文章知识共享归属许可,它允许无限制的使用、分配和复制在任何媒介,提供最初的工作是正确引用。