基于聚类和猫群优化的基因选择算法

敖　培,李　贺,李　明,杨百顺,李延强（.河南师范大学计算机与信息工程学院；.河南师范大学软件学院；. 河南师范大学政治与公共管理学院,河南 新乡 45007）

基于聚类和猫群优化的基因选择算法

敖培1,李贺1,李明2,杨百顺2,李延强3
（1.河南师范大学计算机与信息工程学院；2.河南师范大学软件学院；3. 河南师范大学政治与公共管理学院,河南 新乡 453007）

本文提出一种基于聚类和猫群优化基因选择算法，用来剔除大量冗余基因，提高样本预测的准确率。首先采用k-均值聚类算法将基因分成固定数目的簇，并采用ELM分类器评价筛选特征基因，构成备选基因库；然后采用基于CSO和ELM的缠绕法从备选基因库中选择同时具备最大分类准确率和最小数目的基因子集。通过与经典方法的比较，本文提出的方法能够以较少的基因获得更高的分类性能。

k-均值；猫群算法；基因选择

1　引言

微阵列数据的显著特点是基因维数大、样本维数小。在应用微阵列数据进行分类的过程中，数据往往存在大量与分类无关的冗余基因，因此有必要在分类之前采用基因选择方法剔除冗余基因。为了克服传统的基因选择方法会选择大量冗余基因而导致样本预测准确率下降的缺陷，本文提出一种基于聚类和猫群优化（CatSwarmOptimization,CSO）的基因选择算法。通过对急性白血病和结肠癌两个微阵列数据进行基因筛选的实验结果可以看出，与其他方法相比较，本文方法能成功选择较少数目但有较高分类率的基因子集。

2 　猫群算法

猫群算法[1]是一种基于猫的搜寻行为和跟踪行为的全局优化算法。CSO算法的步骤如下：

Step1：初始化N只猫，每只猫具有D维位置坐标值，xi,d代表第ith只猫第dth维的位置坐标值。

Step2：为每一维位置随机初始化速度Vi,d。

Step3：评估每一只猫的适应函数值，将具有最优适应函数值的猫作为局部最优猫Lb。

Step4：根据MR（定义了猫群中有多少只猫进入搜寻模式，多少只猫进入跟踪模式）的大小，猫群被随机分配到搜寻模式，或跟踪模式。

Step5：评估所有猫将具有最优适应函数值的猫极为Lb。

Step6：检查终止条件，如果不满足则重复执行Step4和Step5，都则结束。

3 　判别熵

判别熵[2]是用来表征不同分布间区别大小的熵函数。对于二分类问题，基因微阵列数据中某组特征基因在不同类别间的概率密度为w1(xi)与w2(xi)，其差别程度定义为相对熵V(w1,w2)=-∑w1(xi) log[w1(xi)/w2(xi)]≤0，则判别熵定义为：

4 　基于聚类和猫群优化的基因选择算法

针对微阵列数据具有高维小样本的特点，本文提出一种基于聚类和猫群优化的基因选择算法。首先对于相似度高的基因，采用k-均值聚类算法将聚成一簇，然后对各簇的基因分类性能采用ELM算法进行分析，筛选出具有高分类性能簇的基因子集，组成一个冗余度较低的初始基因库，最后对于初始基因库采用CSO结合ELM算法找出分类性能最优的基因组合。算法步骤如下：

Step1：生成微阵列数据训练集和测试集，按照第3节计算各个基因对不同类别的判别熵值，并按照绝对值排序筛选判别熵绝对值较大的基因构成备选基因库。然后训练集再分为训练集和验证集两部分。

Step2：采用k-均值聚类算法在训练集上对选出的基因进行聚类，根据样本类别特点确定聚类数目。

Step3：将每簇基因作为一个搜索空间，以获取每个聚类中基因对分类的影响。在搜索空间内，对猫的位置和速度进行随机初始化，一个基因子集就是一只猫。子基因库由经CSO算法在一个簇中筛选出的分类性能较高的基因组。

Step4：计算每个基因子集的适应度值，并根据ELM分类器在验证集上的准确率评价适应度值。全局最优解的获得则通过猫群的位置和速度不断更新来搜索。

Step5：如果迭代条件没有满足，并且没有达到最大迭代次数，则转至Step4。最终的基因子集是验证准确率最优、数目最小的基因子集。

5 　实例分析

本文实验采用Golub等公布的急性白血病数据集和Alon等公布的结肠癌数据集两个微阵列数据集，如表1所示。在实验中，对于第一个数据集随机划分为38例训练集和34例测试集；对于第二个数据集随机划分为40例训练集和22例测试集。将本文方法与其他经典的基因选择方法进行比较以验证本文基因选择方法的有效性。采用相关方法所获取的最小基因子集及相应的最大分类准确率如表2所示。从表2中可以看出，本文算法对于白血病数据集在达到100%分类率的情况下，选择的基因子集数目最少；在选择相同数目的基因子集的情况下，本文算法对于结肠癌数据集样本的分类率最高。综上，与其他方法相比较，采用本文基因选择方法能够在选出小冗余基因的同时保证高的样本分类率。

表1 　微阵列数据集

表2 　数据集中结构类的组成

6 　结语

本文提出一种基于聚类和CSO优化的基因选择算法，以期在进行微阵列基因选择时，降低基因冗余度。采用k-均值聚类算法将基因分成固定数目的簇，并采用ELM分类器评价筛选特征基因，将基因簇中贡献大的基因子集组成基因库，作为CSO的搜索空间。通过实验可以看出，本文提出的方法能够以较少的数目的基因子集获得较高的分类精度。

[1]孔令平.基于猫群算法的无线传感器网络路由优化算法研究[D].哈尔滨工业大学硕士学位论文,2013.

[2]关健,韩飞,杨善秀.基于粒子群优化和判别熵信息的基因选择算法[J].计算机工程,2013,39(11):187-196.

敖培（1979-），女，蒙古族，辽宁省沈阳市人，讲师，博士研究生，研究领域为智能信息处理。

河南省教育厅科学技术研究重点项目基础研究计划No.13A413506;河南师范大学青年科学基金项目No.01116400031。