基于邻域互信息和[K]均值的基因选择算法

摘要：多数传统的属性聚类算法不能直接处理连续型属性，为了避免连续数据离散化处理时造成的信息损失，降低样本属性邻域求解的复杂度，提高特征基因提取的效率。文中提出一种将邻域互信息用于属性聚类的特征基因选择方法，用于在海量的基因表达谱数据中挖掘出少量的具有分类识别能力且冗余度较小的特征基因。

关键词：粒计算；邻域互信息；属性聚类；基因选择

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2014）04-0821-03

1 概述

基于属性约简算法的特征基因选择是为了获得一组基因数量尽可能小而分类能力却尽可能强的特征基因子集。对于传统的属性聚类算法[1]，依据信息熵作为相关度，将属性分成不同的簇，然而，多数聚类算法不能直接处理连续型属性。当需要处理连续型属性时，通常的做法是将连续数据离散化[2]，而离散化会导致信息丢失，使选出的特征基因子集的分类准确率较其他方法不高。

基于粒计算的特征基因提取方法是在邻域互信息和聚类的基础上提出的，结合最小冗余度，最大相关的方法，进行属性约简。对样本基因进行K均值聚类，聚成十类，形成十个簇。利用邻域互信息作为相关性度量，选择出每一个簇的模式，用于进一步基因选择。邻域互信息的方法不需要对连续数据进行离散化处理，避免了信息损失，同时，提高了特征基因子集提取的效率。

2 邻域互信息和K均值方法

2.1 邻域互信息

定义2.1 对于任何一个样本，其[δ]邻域为[3]：

[δ（xi）=x|x∈Gene，Δ（x，xi）≤δ] （1）

定义2.2 第[i]样本的邻域互信息[NMIδ（R；S）]为[4]：

[NMIδ（R；S）=-1ni=1nlog||δR（xi）||?||δS（xi）||n||δS?R（xi）||] （2）

其中[δR（xi）]，[δS（xi）]分别是[xi]在属性集合[R]与[S]上的[δ]邻域，[δR?S（xi）]是[xi]在属性集合[R?S]上的邻域，X是集合[X]的基。

算法1：邻域互信息

Step1：对整个基因组数据[Gene=x1，x2，…xn]，[xi]表示第[i]个样本[（i=1…n）]，[n]表示样本个数；

Step2：[Fj]表示属性集合[（j=1，…，9217），][R]表示第[i]个样本的所有属性，[S]表示整个的所有属性，根据式子得到第[i]样本的邻域互信息[NMIδ（R；S）]；

Step3：对第[i]样本的邻域互信息[NMIδ（R；S）]进行归一化处理，得到归一化之后的数据[NMIδ]。

2.2 K均值算法描述

给定一个包含[n]个数据对象的数据库，以及要生成簇的数目[k]，随机选取[k]个对象作为初始的[k]个聚类中心；然后计算剩余各个样本到每一个聚类中心的距离，把该样本归到离它最近的聚类中心所在的类，对调整后的新类使用平均值的方法计算新的聚类中心；如果相邻两次的聚类中心没有任何变化，说明样本调整结束且聚类平均误差准则函数已经收敛[5][6]。

算法2：划分并计算基于簇中对象的平均值[7]

输入：簇的数目[k]和包含[n]个对象的数据库

输出：平方误差总和最小条件下的[k]簇

Step1：选择[k]个样本作为初始凝聚点（聚类种子），或者将所有样本分成[k]个初始类，然后将[k]个类的重心（均值）作为初始凝聚点；

Step2：对除凝聚点之外的所有样品逐个归类，将每个样品归入离它最近的凝聚点所在的类，该类的凝聚点更新为这一类目前的均值，直至所有样品都归了类；

Step3：重复步骤2；

Step4：直至所有的样品不能再分配为止。

[K]均值算法的工作过程说明如下[8]：首先从[n]个数据对象任意选择[k]个对象作为初始聚类中心；而对于所剩下其它对象，则根据它们与这些聚类中心的相似度（距离），分别将它们分配给与其最相似的（聚类中心所代表的）聚类；然后再计算每个所获新聚类的聚类中心（该聚类中所有对象的均值）；不断重复这一过程直到标准测度函数开始收敛为止。一般都采用均方差作为标准测度函数。[k]个聚类具有以下特点：各聚类本身尽可能的紧凑，而各聚类之间尽可能的分开。

3 属性相关度的聚类算法

定义3.1 设某个样本的单个属性为[Fj]，[Fk]与[Fh]，[h≠k≠j]，[j，k，h∈（1，...，9217）]。在第[i]个样本里[Fj]表示[j]个属性，[Fk]表示第[k]个属性，[Fh]表示第[h]个属性，则[Fj]与[Fk]相关度为：

[NRδ（Fj；Fk）=NMIδ（Fj；Fk）NHδ（Fj，Fk）] （3）

其中，[NMIδ（Fj；Fk）]为属性[Fj]与[Fk]的邻域互信息，[NHδ（Fj，Fk）]为属性[Fj]与[Fk]的联合邻域信息熵。

[NMIδ（Fj；Fk）]度量了已知[Fk]对于了解[Fj]不确定性的平均减少量。如果[NMIδ（Fj；Fk）>NMIδ（Fj；Fh）]，则[Fj]与[Fk]的相关度要大于[Fj]与[Fh]的相关度。当[NHδ（Fj，Fk）=1]时，[Fj]与[Fk]严格相关；当[NHδ（Fj，Fk）=0]时，则[Fj]与[Fk]在统计上独立。而当[0

定义3.2 设属性[Fj]在簇[C=Fj|1，…，9217]中，则[Fj]对于簇[C]的显著多元相关度定义为：

[MNRδ（Fj）=j=1pNRδ（Fj；Fk）] （4）

其中，[NRδ（Fj；Fk）]为属性[Fj]与[Fk]的相关度。

定义3.3 设属性[Fj]在簇[C=Fk|1，…，9217]中，如果[MNRδ（Fj）≥MNRδ（Fk）]，[k∈1，…，9217]，则簇[C]的模式[η（C）]为[Fj]。

可见，簇[C]的模式[η（C）]是簇中显著多元相关度最大的属性。基于邻域互信息的特征基因聚类算法就是利用邻域互信息作为相关性度量，结合[K]均值算法，将各属性聚类成簇，选择出簇的模式，用于进一步基因选择。

算法3：属性相关度

Step1：对第[i]样本基因的[NMIδ]进行[K]均值聚类算法，聚成10类，每个类是一个簇，[Cii（ii=1，…，10）]表示第[i]个样本的第[ii]个簇；

Step2：[Cii]中有[m]个属性，得到[η（Cii）]，则[η（C）]表示第[i]个样本的第[ii]个簇的模式。

4 实验结果与分析

为了验证该算法的有效性，该文采用了UCI数据库中3个常用的标准数据集作为实验数据（如表1所示）。

在表1中，乳腺癌数据集Breast[16]有84个样本和9216个基因表达数据。Golub等人公布的急性白血病数据集Leukemia[17]共有72个急性白血病样本，每个样本均含7129个基因的表达数据。结肠癌数据集Colon[18]是在1999年由Alon描述和在网上提供下载，该数据集共有62个样本和2000个基因表达数据。

根据以上算法，通过筛选得到的聚类划分图像如图1所示：

在聚类划分的图像中，纵坐标表示划分的十个簇的序号，横坐标表示数据归一化之后属性的数值分布，以0为界限，如果属性分布接近于1，则划分比较完善。否则，需要通过修改划分的簇数目（分类精度）来调整聚类划分的良好性。

同时，我们选择基因数据集中的前两组基因样本，利用邻域互信息和聚类的方法进行逐一筛选，并求出每个筛选结果的相关度，统计得到的数据表格如表2所示：

5 结束语

本文在基于邻域互信息和属性聚类划分的基础上，提出了在K均值中的邻域求解方法，该方法通过邻域相关度、分类精度、冗余度等特征值选择出具有代表性的特征基因，此方法不仅降低了样本属性邻域求解的复杂度，还提高了特征基因提取的效率。

参考文献：

[1] 胡清华，赵辉，于仁达.基于邻域粗糙集的符号与数值属性快速约简算法[J].模式识别与人工智能，2008，21（6）：732-738.

[2] 胡清华，于仁达，谢宗霞.基于邻域粒化和粗糙逼近的数值属性约简[J].软件学报，2008，19（3）.

[3] 秦奇伟，梁吉业，钱宇华.一种基于邻域距离的聚类特征选择方法[J].计算机科学，2012（1）.

[4] 谢娟英，李楠，乔子芮.基于邻域粗糙集的不完整决策系统特征选择算法[J].南京大学学报：自然科学版，2011（4）.

[5] 谢娟英，郭文娟，谢维信.基于邻域的K中心点聚类算法[J].陕西师范大学学报：自然科学版，2012（4）.

[6] 孙吉贵，刘杰，赵连宇.聚类算法研究[J].软件学报，2008，19（1）：48-61.

[7] 刘靖明，韩丽川，侯立文.一种新的聚类算法——粒子群聚类算法[J].计算机工程与应用，2005（20）.

[8] 周才英，黄龙军.模糊K-Prototype聚类算法初始点选取方法的改进[C]//2010国际信息技术与应用论坛论文集，2010.