《改进的k-means融合微粒群优化的基因选择方法》由会员分享，可在线阅读，更多相关《改进的k-means融合微粒群优化的基因选择方法（8页珍藏版）》请在金锄头文库上搜索。
1、改进的 K-means 融合微粒群优化的基因选择方法 杜洪波 白阿珍 朱立军 沈阳工业大学理学院 北方民族大学信息与计算科学学院 摘 要： 为了解决基因选择困难问题, 提出一种基于改进的 K-means 算法融合微粒群优化 (IKPSO) 的基因选择方法。该方法首先运用过滤法 (Relief) 对基因进行筛选, 选择出对分类贡献大的基因构成备选基因子集;然后, 利用改进的 K-means算法将备选基因子集划分为一定数目的簇, 并运用微粒群 (PSO) 对每一类簇进行搜索选择出相应类簇中的最优和次优基因构成最优特征基因子集;最后, 训练支持向量机 (SVM) , 并利用其分类的性能来评价获得的最
2、优特征基因子集的质量。在两个典型的、公开的小样本的高维微阵列数据集上进行的实验, 结果表明该 IKPSO 算法总体分类性能相对较好, 并且与传统方法相比, IK-PSO 分类性能得到显著的提高, 证明了 IK-PSO 的可行性以及有效性。关键词： K-means 算法; 基因选择; 过滤法; 备选基因子集; PSO; SVM; 最优特征基因子集; 作者简介：杜洪波 (1977-) , 男, 吉林榆树人, 副教授, 硕士生导师, 主要从事数据挖掘、复杂网络方面的研究。作者简介：白阿珍 (1990-) , 女, 河北石家庄人, 硕士研究生。收稿日期：2017-07-03基金：国家自然科学基金资助项
3、目 (61362033) Gene Selection Method Based on the Fusion of Improved K-means Algorithm and Particle Swarm OptimizationDU Hong-bo BAI A-zhen ZHU Li-jun School of Science, Shenyang University of Technology; School of Information and Computation Sciences, North Minzu University; Abstract： In order to sol
4、ve the difficult problem of gene selection, this paper proposes a gene selection method based on the fusion of improved K-means algorithm and particles warm optimization (IK-PSO) .Firstly, this method uses filtration (Relief) to screen genes and selects genes that contribute greatly to classificatio
5、n to form subsets of candidate genes.Then the subsets of candidate genes is divided into certain number of clusters by the improved K-means algorithm, and using the particles warm (PSO) to search every cluster to select the optimal and suboptimal genes in the corresponding cluster to form optimal su
6、bset of feature genes.Finally, the support vector machine (SVM) is trained and the quality of the obtained optimal feature subsets is evaluated by its classification performance.The experiment results on two open, typical small sample of high-dimensional microarray data sets showthat the overall cla
7、ssification performance of the IK-PSO algorithm is relatively good, and that the IK-PSO classification performance is significantly improved compared with the traditional methods, and the feasibility and availability of the IK-PSO are also proved.Keyword： K-means algorithm; gene selection; Filter me
8、thod; subsets of candidate genes; classification; PSO; SVM; optimal subset of feature gene; Received： 2017-07-03微阵列数据的显著特点是样本小、基因的维数大、高噪声1, 并且存在基因选择难的问题。为了解决此问题, 多种方法已经被运用来处理微阵列数据, 譬如, 聚类算法2、基因选择方法3、分类算法4。聚类算法是研究基因之间的相互关系的最基本的手段1。聚类能够将功能相似的基因聚成一类, 并且按照聚类的结果, 预测未知的基因功能, 寻找基因之间的调控关系和发现共同的模式5。由于基因芯片中含有
9、大量的冗余的基因, 对基因进行分类之前非常有必要对其进行去冗余工作, 而基因选择方法就是一种合适的选择方法。综上讨论, 对基因微阵列运用改进的 K-means 融合 PSO 算法进行基因选择问题的研究。首先, 运用过滤法 Relief 对基因进行筛选;然后, 利用改进的 K-means 算法进行分类, 并利用 PSO 寻优;最后, 训练 SVM, 并评价获得的最优特征基因子集的质量。提出的“改进的 K-means 算法融合微粒群优化算法”简称为“IK-PSO 算法”。1 相关算法1.1 改进的 DPC 算法DPC 是 2014 年由 Alex Rodriguez 和 Alessandro La
10、io 提出来的一种基于密度的新的聚类算法6。DPC 算法的思想是:聚类中心往往是由一些局部密度较低的数据对象所包围, 并且与任何具有较高局部密度的其它的数据对象之间的距离都相对较大。在 DPC 算法中, 局部密度 i和距离 i的计算依赖于截断距离 dc, 而 DPC 中的截断距离 dc是通过人工设置的, 属于人工经验的方法, 虽然, 截断距离 dc的选择具有鲁棒性, 但是, 仍然缺少理论依据。因此, 运用文献7中的选取截断距离的方法来对 DPC 进行改进。对于数据对象 i 计算与其余各数据对象之间的赋权欧氏距离 dij (i, j=1, 2, , n;ij) , 从而得到向量 li=di1,
11、di2, , din, 接着将 li进行升序排序进而得到向量 ci=sort (li) =ai1, ai2, , ain, 再将 ci中的两两相邻的元素进行做差运算, 并根据下列公式得到数据对象 i 的截断距离 dci为式中, max (a i (j+1) -aij) 是向量 ci中相邻的两个元素之差的最大值。对于每一个数据对象 i 都有一个截断距离 dci, 因此, 这些截断距离就可以构成一个集合 Dc=dc1, dc2, , dcn, 而要选择的最优截断距离 dc=min (Dc) 。这种改进的方法为截断距离 dc的选择提供了依据, 而且容易实现、算法简单。1.2 K-means 算法K-
12、means 算法8是以 K 为参数, 将数据集对象分成 K 个簇, 使得簇内的相似度尽可能较高, 而簇间的相似度尽可能较低, 其相似度是根据数据对象与一个簇中所有对象的平均值 (即聚类中心) 之间的距离来进行度量的。K-means 的目标函数为式中, E 是数据集中的所有数据对象的平方误差总和;p 是数据集中的数据对象;mi是类簇 Ci的中心。K-means 算法描述如下:输入:包含 n 个对象的数据集和簇的数目 K。输出:满足目标函数最小值的 K 个簇。Step1:从 n 个数据对象中随机地选择 K 个对象作为初始聚类中心;Step2:对剩余对象, 根据它与聚类中心的距离, 并根据最小距离原
13、则将其指派到相应的类簇中进行划分;Step3:计算每个类簇的新的均值, 即新的类簇中心;Step4:回到 Step2, 循环, 直到聚类中心不再发生变化。1.3 基于改进的 DPC 算法的 K-means 算法针对 K-means 需要人为地确定聚类个数, 随机地选择初始聚类中心进行迭代从而导致不稳定的聚类结果的缺陷, 可以通过改进的 DPC 来自动确定聚类数目以及选取聚类中心作为 K-means 的初始聚类中心, 接着运用 K-means 算法进行迭代。而在基于改进的 DPC 算法的 K-means 算法中改进的 DPC 是利用文献7中介绍的方法来选择最优截断距离 dc。此外, 利用赋权欧氏
14、距离9来更准确地规范各对象的差异程度, 从而更好地聚类。改进的 K-means 算法具体描述:输入:含有 n 个数据对象的数据集合。输出:满足目标函数最小值的 K 个簇。Step1:运用熵值法来计算各个数据对象之间的赋权欧氏距离 dij, 并令 dij=dji, ij 将其补成满矩阵;Step2:确定截断距离 dc;Step3:根据确定的截断距离 dc, 并利用 DPC 算法中的方法计算每个数据对象 i的 i和 i;Step4:根据 i= i i (i=1, 2, , n) , i的值越大, 则 i 就越有可能是聚类的中心;Step5:确定聚类中心 cj (j=1, 2, , K) 与 K 的
15、值;Step6:计算剩余每个数据对象与各类簇的中心的距离, 并将每个数据对象分类给距其最近的类簇中, 从而达到划分的目的;Step7:重新计算每个新簇的均值作为新的类簇中心;Step8:计算目标函数值;Step9:直到目标函数不再发生任何的变化, 算法终止;否则, 转 Step7。1.4 PSO 算法PSO 算法10 (微粒群优化算法) 的思想来源于对鸟群捕食行为的研究, 它是模拟鸟集群飞行觅食的行为, 鸟之间通过集体的协作从而使群体达到最优目的。PSO 随机初始化粒子, 并且粒子的速度根据它本身的飞行经验以及同伴的飞行经验进行动态的调整, 而粒子的速度和位置按照以下的方程式进行迭代:式中,
16、是惯性权重值;c 1, c2为正常数, 称为加速系数;r 1, r2分别是0, 1范围内变化的随机常数。2 IK-PSO 算法因为微阵列具有高维、小样本的特点, 如果仅使用 PSO 算法随机地搜索最优特征基因子集, 无疑则会增加搜索的难度, 从而降低搜索能力。因此, 提出 IK-PSO 来对基因进行选择。首先, 对于数据集未划分成训练集和测试集的则利用bootstrap 法将其划分成训练集和测试集;接着, 在训练集上运用过滤法 Relief对基因进行初步筛选, 选择出对分类贡献大的基因从而构成备选基因子集;然后, 利用改进的 K-means 聚类算法将基因划分成一定数量的簇, 并运用 PSO 对每一类簇进行搜索选择出相应类簇中的最优基因构成最优特征基因子集, 在选择基因时, 只选择最优的基因可能会丢掉原本数据集中一些相对重要的基因, 因此, 除了要找出不同类簇中最优的基因外, 相应的也要找到相对应类簇中的次重要的基因, 从而构成
