基于智能优化计算的双聚类算法研究

作     者：田小龙 

作者单位：西安电子科技大学 

学位级别：硕士

导师姓名：李阳阳

授予年度：2014年

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 

主      题：双聚类 基因表达数据 群体智能优化 多目标优化 模式驱动搜索算子 

摘      要：在数据挖掘分析中,聚类技术是一种特别重要的工具,通过该技术,可以将数据集分成一些簇或类,使得这些类符合给定的指标,通过分出的类来了解数据的分布结构,进而对生产生活做出指导。随着技术的不断发展,数据不断积累,人们对数据的分析技术也不断提高,产生了大量对这些数据进行分析的聚类技术。在生物基因学研究方面,随着微阵列技术的快速发展,获取到的基因表达数据的维度也逐渐增大,这里所指的维度是指基因表达数据的行数和列数,由于这些数据的稀疏性以及高维性,再使用老方法进行分析,会遇到巨大挑战。双聚类技术是近年来兴起的一门新技术,该技术是一种二维聚类技术,它分别对二维矩阵的行和列同时进行聚类,对矩阵局部进行搜索,旨在发现高维数据的局部模式。通过双聚类技术发现的簇是行子集和列子集的组合,是二维数据矩阵的一个子矩阵,簇中包含的基因在所包含的条件集合下呈现高度的相关性。本论文所做的工作如下:1.对传统聚类技术的特点以及双聚类技术的常用的搜索策略进行了总结。在论文中,首先讨论了传统聚类算法的特点,并对传统方法进行了归类介绍,对个别经典的算法进行了较为详细的分析。在历史中,那些经典算法曾经对数据挖掘发挥了重要作用,但随着数据维度增高,一些新的问题不断出现,传统算法出现了严重的不足。双聚类克服了传统算法在高维数据分析中的不足,能够对高维数据进行有效分析。论文详细介绍了双聚类技术常用的几种搜索策略和几种经典的双聚类技术,并分析了各自的优缺点。群体智能优化算法是一种基于随机搜索策略的进化搜索技术,论文分析了群体智能优化在基因表达数据分析中应用的可能性,并介绍了常用到的一些智能优化算法。2.本文研究了粒子群优化(Particle Swarm Optimization,PSO)算法在基因表达数据分析中的应用,并以二进制版PSO作为基本框架,提出了一种基于模式驱动搜索的二进制PSO算法。粒子群优化是一种基于进化搜索策略的群体智能优化算法,该算法编程实现的时候比较简单,不需要一定的数学背景知识,但是基于进化搜索策略的算法在搜索效率上并不占优势,需要引入其他算子提高算法的局部搜索能力。模式驱动算子是一种利用基因表达数据自身轨迹信息进行搜索的算法,该算子的引用,改善了PSO算法的局部搜索能力,缩小了搜索空间,改善了算法的性能。3.本文改进了Mitra等提出的多目标双聚类算法,提出了一种新的多目标优化双聚类算法,该算法以NSGA-II为框架,对Cheng和Church的贪婪搜索算法和模式驱动算法进行了整合,以改善算法的性能。对基因表达数据进行分析时,常要考虑多个优化目标,而这些目标通常又是相互排斥的,在一个目标变好的同时,又会至少有一个目标变差,对于这种情况,比较适合使用多目标优化来进行求解,而NSGA-II是一种广泛应用的多目标算法。实验表明,在有限次数迭代下,本文所提出的算法能够取得分布较为均匀的Pareto前沿,且算法最终搜索到的双聚类的质量也比原算法要好。