基于DNA计算的CLIQUE聚类算法研究

【摘要】：随着全球科技的发展,世界网络化程度日益加深,互联网的普及导致信息量激增,对海量信息的数据挖掘已经引起了信息产业界的极大关注。聚类是数据挖掘的重要手段,然而现代计算机已经很难满足传统聚类算法对速度和存储能力的要求,因此设计新的高效的聚类算法势在必行。DNA计算是借助DNA分子和生化操作实现数学运算的一种新兴的学科交叉计算模式,它将电子计算机解决的问题转换到特定编码的DNA序列上,通过杂交、电泳、提纯等一系列的生物反应得到问题的解空间,具有并行性高、速度快、存储能力强的特点。本文将DNA计算与经典网格聚类算法CLIQUE相结合,提出了一种基于DNA计算的CLIQUE算法,仿真实验结果表明,该算法可以有效降低网格聚类的时空复杂度,提高计算速度,具有一定应用前景。本文的研究内容和主要成果如下:首先,提出基于DNA计算的CLIQUE算法。将CLIQUE网格中的单元格转换成节点并连接那些候选节点成图,利用Adleman博士解决哈密尔顿路径问题的模型,建立适合转换图的DNA计算模型,在DNA分子进行生化反应后的产物中提取聚类结果。其次,通过仿真实验检测DNA计算模型效果。仿真实验通过计算机模拟顶点和连接边的DNA编码,然后进行杂交、电泳、提纯等整个生化反应过程,生成生化操作的所有可能解,从中提取出聚类结果。仿真实验用人工合成的少量数据证明了DNA计算解决CLIQUE算法的可行性,与原CLIQUE算法相比,新算法在保证聚类效果的前提下提高了执行效率。最后,在乳腺癌病历三维数据集上进行仿真实验。将该三维数据集映射到二维平面上,形成三个二维数据集,通过计算机模拟得出这三个二维数据集的聚类结果,再取其交集获得三维聚类结果,得出的乳腺癌发病高峰期和完全治愈时间与实际数据的分析结果相符合。
【关键词】：DNA计算 Adleman模型 数据挖掘 CLIQUE算法 网格聚类
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：TP311.13