为提高癌症基因表达数据聚类的准确性和效率，对具有完全学习策略的量子行为粒子群优化(CLQPSO)算法和广义回归神经网络(GRNN)进行了研究，实现了一种CLQPSO癌症基因聚类算法. GRNN能充分利用多条相似基因隐含的规律，对基因表达缺失值的预测有较高的可信度；CLQPSO算法在迭代更新时能充分利用各粒子当前最佳位置和粒子群所提供的社会合作信息，避免过早收敛于局部最优解.实验结果表明，综合使用GRNN和CLQPSO算法对癌症基因表达数据进行聚类，比K-Means、谱聚类、离散粒子群算法具有更好的聚类性能和全局收敛性.
To improve the accuracy and efficiency of cancer gene expressing data clustering, Quantum-behaved particle swarm with comprehensive learning strategy(CLQPSO) and generalized regression neural network (GRNN) are studied, A cancer gene clustering algorithm was generated based on CLQPSO. GRNN takes advantage of the implicit rules in a number of similar genes and the prediction of missing values for gene expression has higher credibility; CLQPSO algorithm can make full use of each particle best position and particle swarm social cooperation information offered, avoiding premature convergence in local optimum value. Experiments show that the integrated use of GRNN and CLQPSO algorithm has better clustering performance and global convergence compared with K-Means, spectral clustering, discrete particle swarm algorithm in the aspect of cancer gene expressing data clustering.
对癌症基因表达数据进行数据挖掘，主要是通过聚类等方法研究癌症的亚型分型，发现新的癌症标志物.已有一些聚类算法应用于基因表达数据的聚类，但据文献的实验结果可发现这些算法都存在不足：K-Means算法依赖一个不能在聚类之前准确预测的K值，且当样本空间非凸时易陷入局部最优；自组织映射聚类容易产生不均衡分类；遗传算法在处理规模较大的问题时容易早熟；简单的粒子群算法不能保证以概率1收敛于全局最优；谱聚类算法未充分利用样本点分布特性所隐含的先验信息，在处理复杂样本数据点集时，聚类结果并不理想.
以癌症基因表达数据为实验对象，在借助GRNN对基因表达数据的缺失值进行预测的基础上，使用CLQPSO算法进行聚类.实验表明，该方法具有收敛速度快和全局收敛能力强的优势.
1 改进的CLQPSO算法粒子群优化(PSO，particle swarm optimization)是一种基于群体智能的优化算法，其进化公式除包含粒子前一时刻的信息之外，还加权融合了进化过程中的粒子自身经验信息和群体共享信息，具有易实现、不受解空间限制性假设的约束等优点.但PSO算法在求解复杂多峰问题时易早熟，因此要根据所求最优化问题的数据特点改进粒子进化公式.
不少文献致力于改善PSO算法易早熟、精度低的缺点，典型的有陶新民等[1]提出一种多尺度协同变异的PSO算法，并证明了该算法能以概率1收敛到全局最优解；Zhan Zhihui等[2]提出自适应PSO算法，通过评价迭代过程中每个粒子的性能改善指标，对加速因子及其他参数进行自动控制；Kiranyaz等[3]通过多维PSO和分形全局最优构建技术，无需引入额外参数即能以适宜的搜索速度收敛到全局最优，不受搜索空间维数、群体规模及问题复杂性的影响；陈伟等[4]提出CLQPSO算法，在迭代更新时能充分利用所有粒子当前最佳位置所提供的社会信息，并通过粒子间的社会合作丰富种群的多样性，改善算法在求解多峰优化问题时的全局收敛性能.
针对陈伟提出的CLQPSO算法，在参数的自适应取值等方面进行改进，提高了算法的收敛速度和精度.改进后的算法描述：对最优化问题P，在解空间范围内，初始化m个随机的可行解，每个可行解视为一个粒子，设粒子在量子空间中运行并具有量子行为，做以下假定.
记粒子i在搜索空间中的某时刻t的位置为Xi=(xi1(t), xi2(t), …, xiD(t)).根据问题性质，确定评价粒子Xi接近最优解程度的适应度函数F(Xi).
记搜索过程中粒子i当前最靠近全局最优解的最佳值为Pi=(pi1, pi2, …, piD)，记粒子i的局部吸引子为qi=(qi1, qi2, …, qiD)，则CLQPSO聚类算法的粒子进化公式[4]为
|
(1) |
其中：α为控制粒子收敛速度的收缩扩张因子，u为(0, 1) 范围内均匀分布的随机数. u > 0.5时，α前的符号取+，否则取－.对于远离全局最优解的粒子，α应小一些，反之应增大α.实验表明，通过自适应机制对α的取值进行变化可以让QPSO具有较好的收敛性能.式(2) 是一个求α值的自适应经验函数.
|
(2) |
其中
|
误差ΔF表示某粒子Xi与全局最优位置g的接近程度. ΔF越小，表示该粒子离全局最优值越接近，此时粒子的搜索范围也应随之缩小.
式(1) 中，
对粒子i，引入参数学习概率为
|
(3) |
pci值的大小决定了粒子i的全局勘探和局部开发能力.对粒子i的每一维，如第j维，产生一个随机数，若该随机数大于pci，则fi(j)=i，即qij(t)=pij(t)，表示取粒子i的t时刻最佳值的第j维的值；否则，就需要向其他粒子学习，即在粒子群中随机选取除粒子i外的几个其他粒子的t时刻最佳值，把适应度最好的那个粒子的第j维的值赋给qij(t).为提高粒子的全局勘探能力，若qij(t)的所有维决策变量均取自粒子i的t时刻最佳值的对应维的值，则需在qij(t)随机选择某几维向其他粒子的t时刻最佳值的对应维学习.
式(3) 可以使各粒子的pci值从0.05非线性增加到0.5，使种群粒子的全局勘探能力和局部开发能力达到一个理想的平衡状态，从而使算法能适应不同类型目标函数的最优化问题[4].
上述改进后的CLQPSO(MCLQPSO)算法的流程如下.
① 指定粒子个数M，随机产生各粒子的当前值，并把该值作为该粒子的当前最佳值；
② 根据粒子群中各粒子的当前最佳值，找出全体粒子的当前最佳值g；
③ 采用完全学习策略(式(1))更新每个粒子的局部吸引子，然后计算Xi(t+1) 各维的值；
④ 对每个粒子，若F(Xi(t+1) 优于F(Pi)，则置Pi=Xi(t+1)；
⑤ 重复步骤②~④，直到满足停止准则或达到预设的最大迭代次数为止.
2 基于MCLQPSO的癌症基因聚类癌症基因表达数据用矩阵表示，行表示基因的表达模式，列表示不同时间点或者不同实验条件下的样本.对其聚类可以按基因(行)进行，按样本(列)进行，同时按基因和样本双向进行.笔者基于MCLQPSO，设计了对基因表达矩阵的行聚类，通过更改粒子的数据结构，也可实现列聚类.
基于MCLQPSO的癌症基因聚类分为以下2个步骤.
1) 数据预处理
基因表达数据的预处理包括数据去噪、缺失值处理、数据转换与标准化.如果某基因存在缺失值，则采用GRNN来估算缺失值. GRNN模型[5]如下.
设自变量x及其函数y均为随机变量，f(X, Y)为其概率密度函数.记x的观测值为X，对应的函数值记为Y, 其数学期望为
|
设f(X, Y)服从正态分布，则有
|
其中：n为学习样本数目，d为x的维数，σ为平滑因子，用f(X, Y)代替f(X, Y)求期望，可得到
|
(4) |
其中
|
(5) |
|
(6) |
GRNN模型由输入层、模式层、求和层、输出层4层网络构成.输入层神经元数等于样本向量的维数，用来接收学习样本；模式层接收输入层传递的信息并将其经式(6) 转换后传递至求和层；求和层中有两类神经元，分别对模式层中数据通过式(5) 求S、T的值，送输出层按式(4) 计算结果[5].
基于GRNN估算癌症基因表达数据缺失值：
从基因表达数据矩阵中复制那些不存在缺失值的基因表达数据，构成一个子矩阵，记为
|
设基因b存在缺失值，在B中找到k个与b最相似的基因训练GRNN并估计b的缺失值.判断B中某基因与基因b之间的相似度，可使用欧氏距离或Pearson相关系数.
2) 使用基于MCLQPSO算法按基因进行聚类
用向量集{x1, x2, …, xn}表示基因表达数据矩阵的n个基因，其中xi=(xi1, xi2, …, xiD)表示第i个基因.对数据集的聚类划分用数码串a1, …, an表示，其中ai为基因Xi在聚类结果中所属类的编号.用Gk代表第k个类，Zk为Gk类中的基因总数，Gk类的聚类中心记为Ck=(ck1, ck2, …, ckD)，其元素值为
|
(7) |
确定相似性度量公式的方法如下.
实验表明，对具有连续特征的数据集采用距离公式比较好，对由多种变量组合的数据集采用相关系数比较好.对于基因表达数据，若数据与时间序列关系密切，可用距离公式，而对于基于不同实验条件的，应采用Pearson相关系数定义.分别采用欧氏距离[6](式(8))、Pearson相关系数(式(9))、最小类质心距离(式(10))3种相似度公式，来构造求总体类间差异(TWCV，total within-cluster variation)的公式，分别为
|
(8) |
|
(9) |
|
(10) |
式(10) 中，
TWCV是衡量聚类效果的重要指标.对于粒子群进化过程中的每个聚类划分，使用式(8)、式(10) 作为适应度函数，值越小越接近全局的最优聚类.若使用式(9)，值越大越接近全局的最优聚类.
粒子编码：设基因的目标聚类个数为K，粒子以K个类的聚类中心为分量进行编码，即将粒子i表示为
初始化粒子值：随机将基因数据分到K个类中，按式(7) 计算出这K个类中每个类的聚类中心，作为粒子的K个分量，生成一个粒子.按此种方法，生成粒子群中的其他粒子.
求粒子群的全局最佳值：将各粒子的当前值作为其当前最佳值，按式(8) 或式(10) 计算以所有粒子的当前最佳值为类划分的TWCV值，并把TWCV值最小的那个粒子定义为粒子群的全局最佳值.若按式(9) 计算，则把TWCV值最大的那个粒子定义为粒子群的全局最佳值.
基于MCLQPSO算法，对粒子群进行进化：
① 对群中各粒子，按式(1) 生成新一代粒子，并将粒子各维的值视为各类的新的聚类中心.
② 以粒子各分量的值为聚类中心对基因表达数据重新聚类，并根据新的聚类结果，按式(7) 计算出各类的聚类中心，用来替换粒子中对应维的值，生成新的粒子.对群中各粒子均如此操作，从而形成新的粒子群.
③ 在新生成的粒子群中，计算每个粒子的当前最佳值，进而计算出粒子群的全局最佳值.
④ 重复步骤①~③，直到满足停止准则或达到预设的最大迭代次数为止.
3 实验数据分析及进一步工作内部确认测量技术基于数据的内部信息，通过测量聚类结果的划分与数据自然结构的对应程度进行质量预测，是常用的聚类确认方法.内部确认测量有不同的指数，其中Silhouette指数能较好地反映聚类算法的性能和聚类结果的质量.笔者使用Silhouette指数和TWCV值对聚类结果进行分析.
为验证MCLQPSO算法在对癌症基因表达数据进行聚类时的有效性及性能，使用3个真实的数据集做了2个实验.数据集分别是乳腺癌(http://mgm.duke.edu/geneme/dnamicro/work/)、Alon等公布的结肠癌(http://microarray.princeton.edu/Oncology/affydata/index.html)、Golub公布的白血病(http://www.wi.mit.edu/MPR/dataset_ALL_AML.html)，各数据集的特征如表 1所示.
|
表 1 数据集特征 |
实验1使用本文算法与K-Means、谱聚类、离散粒子群算法(DPSO，discrete particle swarm optimization)，分别对测试数据进行聚类并比较聚类结果的性能和正确率，结果见表 2(用式(8) 求相似度)；实验2使用了本文算法，但聚类时分别使用式(8)、式(9)、式(10) 计算相似度，比较这3种相似度在不同数据集上的聚类准确率，结果如表 3所示.
|
|
表 2 不同算法聚类有效性对比 |
|
|
表 3 本文算法在3种相似度下的聚类正确率 |
表 2是使用式(8) 作为相似度计算公式得到的聚类性能评价数据，作为对比所使用的谱聚类和DPSO算法均为当前同类算法中最新提出的性能比较好的算法.对比结果显示本文算法在4种算法中具有最好的性能.根据其他文献中K-Means算法、谱聚类、DPSO算法与其他算法的比较可以推知，在现有的基因表达数据聚类算法中，本文算法具有较好的聚类性能和全局收敛性.
表 3的结果用来分析不同相似度计算公式对聚类准确度影响，由表 3不能看出某个相似度计算公式在所列的数据集中都表现出较高的准确度，这说明同一个相似度计算公式并不能在不同的数据集上都表现出优越性能.因此在进行聚类分析时，应分别使用不同的相似度计算公式进行聚类并对聚类结果进行对比分析，以使聚类结果更接近真实值.
4 结束语结合GRNN，将MCLQPSO算法应用在癌症基因表达数据的聚类分析上.实验证明本文算法对癌症基因表达数据的聚类是高效的、可信的.下一步要研究以下任务：一是PSO算法进化过程中的并行化问题，特别是如何在低硬件成本下并行化；二是相似度评价函数的选择问题.未来要通过对各种类型的数据集进行在不同相似度评价函数下的聚类，分析聚类效果，找出一种能在大多数数据集中相似度评价平均性能最好的评价函数，以便能对大多数数据集做出较为可信的聚类.
| [1] |
陶新民, 刘福荣, 刘玉, 等. 一种多尺度协同变异的粒子群优化算法[J]. 软件学报, 2012, 23(7): 1805–1815.
Tao Xinmin, Liu Furong, Liu Yu, et al. Multi-scale coop-erateve mutation particle swarm optimization algorithm[J].Journal of Software, 2012, 23(7): 1805–1815. |
| [2] | Zhan Zhihui, Zhang Jun, Li Yun, et al. Adaptive particle swarm optimization[J].IEEE Trans on Systems, Man, and Cybernetics, 2009, 39(6): 1362–1381. doi: 10.1109/TSMCB.2009.2015956 |
| [3] | Kiranyaz S, Ince T, Yildirim A, et al. Fractional particle swarm optimization in multidimensional search space[J].IEEE Trans on Systems, Man, and Cybernetics—Part B, 2010, 40(2): 298–318. doi: 10.1109/TSMCB.2009.2015054 |
| [4] |
陈伟, 周頔, 孙俊, 等. 一种采用完全学习策略的量子行为粒子群优化算法[J]. 控制与决策, 2012, 27(5): 719–730.
Chen Wei, Zhou Di, Sun Jun, et al. Improved quantum-behaved particle swarm optimization algorithm based on comprehensive learning strategy[J].Control and Decision, 2012, 27(5): 719–730. |
| [5] |
贾义鹏, 吕庆, 尚岳全. 基于粒子群算法和广义回归神经网络的岩爆预测[J]. 岩石力学与工程学报, 2013, 32(2): 343–348.
Jia Yipeng, Lü Qing, Shang Yuequan. Rockburst prediction using particle swarm optimization algorithm and general regression neural network[J].Journal of Rock Mechanics and Engineering, 2013, 32(2): 343–348. |
| [6] |
朱思峰, 刘芳, 柴争义. 免疫聚类算法在基因表达数据分析中的应用[J]. 北京邮电大学学报, 2010, 33(2): 54–57.
Zhu Sifeng, Liu Fang, Chai Zhengyi. Application of immune clusterng algorithm to the analysis of gene expression data[J].Journal of Beijing University of Posts and Telecommunications, 2010, 33(2): 54–57. |