论文部分内容阅读
单核苷酸多态性(single nucleotide polymorphism,SNP),主要是指因为单个核苷酸的改变而造成的DNA序列的改变,从而导致物种染色体基因组的多样性,从而表现出不同的性状。关联性分析就是分析随机变量之间的相关性,一个随机变量的变化跟另一个随机变量的变化之间的内在联系,常常用于网站的推荐算法。而SNP关联性分析指的是在一个人的所有的由基因表达水平组成的特征集中,寻找出与某一个疾病关联性最大的特征子集。本文致力于SNP关联性分析中的搜索算法以及该算法选择出来的特征与真实特征在疾病预测方面的比较,并提出一种混合特征选择算法MFS。常用的特征选择算法主要由四个模块组成,但是现在国内外研究的重点是搜索策略和评价准则这两个模块。根据搜索策略的不同可以将现有算法分为穷举式、序列式和随机式,根据评价准则的不同可分为过滤式和封装式。本文首先实现了基于序列浮动前向搜索和基于动态振荡搜索的两种不同搜索策略下的特征选择算法,详细介绍了这两类算法的实现原理、设计思想和算法的特点,并在Model1~Model3数据集上进行了实验。通过分析实验结果、比较这两种搜索算法各自的特点和适用范围,我们得到当算法的平均计算时间在可以容忍的范围内时,DOS搜索策略比SFFS搜索策略更适合SNP关联性分析这类问题,最终确定在MFS算法中采用DOS搜索策略。其次,介绍了混合特征选择算法的必要性以及怎么实现混合的,在MFS算法中我们根据Filter和Wrapper这两种评价准则的不同点和使用场景,我们将MFS算法分成两个重要的阶段:样本数据的降维阶段和核心搜索阶段,其中降维阶段用的是Filter评价准则而核心搜索阶段使用的是Wrapper评价准则,通过将它们运用到MFS算法中,使得算法在时间上和性能上有了更好的均衡。最后,针对基于DOS搜索的算法更加容易陷入局部最优这一重要的缺点,我们将Halton序列应用到MFS算法中,因为Halton序列具有低差异性和超均匀分布这两个特性,这两个特性使得搜索非常均匀,算法不会集中到某一个点附近搜索,从而避免了MFS算法陷入局部最优。我们将MFS算法与其它算法在模拟数据集和真实数据集上完成了实验。实验最终结果表明,MFS算法在SNP关联性分析中比常规特征选择算法具有更好的性能,算法的搜索时间更短、目标结果更准确。