DNA计算在数据挖掘中的应用研究

束建华，殷志祥

（1.安徽中医学院 医药信息工程学院，安徽 合肥 230008；2.安徽理工大学 理学院，安徽 淮南 232001）

1 引言

数据挖掘[1（]Data Mining），也称为数据库上的知识发现（Knowledge Discovery in Database），其可描述为从存放在数据库、数据仓库或其他信息库中的大量数据中挖掘出潜在有用的、先前未知的、最终可理解的知识的过程.数据挖掘的重要任务是发现数据中潜在的模式.主要技术方法有：聚类、关联分析、分类、序列分析、异常检测等.数据挖掘在零售业、金融数据分析、医学、农业生产各商业领域都存在广泛的使用价值，通过改进数据挖掘算法或者引入新的方法来提高数据挖掘方法的效率是非常有必要的.

DNA计算模型[2]是由美国加利福尼大学的Adleman博士于1994年提出来的，利用DNA（脱氧核糖核酸）对一个图论中的NP-完全问题-有向图的Hamilton路问题进行编码，借助连接、变性、复性、PCR扩增、电泳等生物操作可以求解出这一问题.DNA计算是作为一种新型的分子生物计算方法，以DNA作为信息的载体，具有存储容量大、高度的并行性、运算速度快等的优点，其在图论和组合优化问题的解决中发挥了极大的优势[3-5].将DNA计算应用于解决数据挖掘问题是一个非常好的思路，逐渐引起人们的关注.目前，DNA计算在数据挖掘领域应用主要有聚类问题和分类模型的建立，本文将分别讨论DNA计算在聚类分析和分类模型构造中的原理、方法及应用.

2 DNA 计算在聚类中的应用

聚类是一种对数据进行自动组织的方法，即按照数据的相似性和差异性，将数据划分为若干组(组内还可以再分组)，同组的数据尽量相似，不同组的数据尽量相异.广泛使用的聚类算法有：K-means聚类方法、基于层次的聚类方法、基于网格的聚类方法等.随着DNA计算研究的兴起，人们发现其在解决图和组合优化问题时已显示出极大的潜力，尽管我们很难直接利用DNA计算的思想解决聚类问题，但把聚类问题转化为图和组合优化问题就能较好的利用DNA计算进行解决[6].

2.1 聚类算法的DNA计算解决思路

聚类的分析方法的核心是分析数据集中各数据的相似性.聚类方法转化为图论问题的思路是：我们把数据对象看作是图中的顶点，数据之间的相似度看作是图中的带权边，聚类即在图中寻找满足属于同一簇的路径最短而连接不同簇之间的路径最长的路径.而聚类方法转化为图论问题的思路是：对数据对象的聚类看作是寻找一种最优组合方式的组合优化问题，即组合中的每个簇内每两个数据点之间的相似度最大而组合中的两个簇之间的数据点的相似度最小.因此，我们可通过先把聚类转化为图论问题或组合优化问题，就可以利用DNA计算来解决.

2.2 聚类算法转化为哈密顿图问题

DNA计算用来解决的第一个问题是图论中的哈密尔顿图问题，Adleman的解决方案基于如下非确定性算法[2]：随机产生生成图的各种路径，只保留由始点开始并且有终点结束的哪些路径，再只保留包含n（假设图中有n个节点）个节点且每个节点只进入一次的路径，最后选择最短路径.聚类分析中，我们把数据集中的数据对象作为顶点而数据间的相似性作为带权边即可以组成一个完全图，在完全图中寻找一条包含了所有数据点的最短路径，这条最短路径即为聚类结果.在这条最短路径中，相离较远的数据点（即相似性小）会分成不同的簇，而相距较近的数据点（即相似性大）就属于同一簇.

2.3 聚类问题的DNA计算实验主要步骤

聚类问题可以转换为哈密尔顿路径（回路）问题，也可以转换为生成树问题，都是可以通过DNA计算来解决的，并且有多种模型选择：过滤模型（Adleman实验所采用的DNA计算模型）、粘贴模型等.

我们设图中每个顶点用一个随机的长度为20的DNA串表示，以此作为一个模板，将生成相关联、由连接反应连接起来的边的DNA串.最终，连接反应将形成各种DNA分子，这些DNA分子可看作是对应图中的随机路径的编码，通过PCR扩增前面的产物得出只含起点和终点的DNA分子，最终电泳分离得分子量最小者.值得注意的是在生物实验使用的基本技术：熔化、退火、混合、分离或提取、扩增、检测和长度分离（这两种操作都应用凝胶电泳技术）对每一个操作都很重要.

算法描述步骤如下[12]：

输入：问题编码，输入试管T1,T2，图G

1：T←merge(T1,T2)：将包含图中每个顶点的试管与包含边的连接链试管合并后，放入试管T，进行充分反应

2：T←prefix(T,v1)：从试管T中提取出所有含有顶点v1DNA分子.

3:T←prefix(T,vn)：从试管T中提取出所有含有顶点vn的DNA分子.

4：T←amplify(T)：PCR扩增得出含有顶点v1和vn的DNA分子.

5：T←length-separate(T，m*n)：提取所有包含n个顶DNA分子（路径）.

6：for i←1 to n do

7：T←separate(T,vi)：提取包含图中每个顶点的DNA分子.

8：end for

9：return detect(T)：找出最短路径，即电泳分离，得分子量最小者.

2.4 DNA计算在聚类算法中的主要应用

Bakar等人将DNA计算用于解决k-means聚类问题，是首次提出利用DNA计算解决聚类分析问题的方法[6].该文的解决思路是：对中心点和各点的距离设计DNA编码，将包含中心点的试管和包含各点的距离的连接链试管合并，进行连接和混合反应，从而得到各种包含了各点、各中心点的DNA分子，分离出包含全部中心点的最短的DNA分子即为聚类结果.而后陆续有DNA计算应用于聚类分析的文章[7-10]，主要从编码、生化反应等方面进行改进研究，以提高聚类效率.

国内刘希玉教授带领的团队近几年开始研究将DNA计算应用于聚类中[6,11,12].在聚类中，整个图作为初始簇，用单链DNA 表示顶点和各顶点间的边，转化为最小生成树的问题，得出的各可连通的子图即聚类结果，或者转化为哈密尔顿问题，最短哈密尔顿路径即为聚类结果.

综上，我们知道只要能把聚类算法转化为图的问题或组合优化的问题，就可以使用DNA计算的方法，提高聚类效率和得到更好的聚类结果.

3 基于DNA 计算的分类模型

分类(classification)是另一个重要的数据挖掘任务，它会产生一组以自然的方式描述每个类的规则或类别.进化算法已经广泛应用于分类器构造中，众所周知的基于进化算法的分类学习系统有：神经网络、遗传算法、模糊集合方法、粗糙集方法等分类算法[13].直接使用DNA计算解决分类问题的文献尚未发现，主要通过DNA计算与其他方法（如遗传算法[14]、模糊推理[15]）融合研究的方式应用于分类模型的构造中.

DNA计算模型由两部分构成：DNA编码和DNA基因操作.将DNA计算引入到分类中，是利用DNA编码模型表达重要特征信息,通过DNA操作对DNA编码的调节与控制,获取最典型编码,实现编码匹配的最优化，其基本流程如图1所示[14].

图1 基于DNA计算分类方法的流程图

图中核心操作是第一步，即DNA计算模型初始化：(1)DNA种群参数选择:DNA模型需要设定DNA种群个体数量,交叉概率,变异概率,循环终止条件.(2)样本选择:样本分为两部分,包括训练样本与测试样本.从训练样本中选择一定数量的样本,作为DNA初始种群.

DNA编码方式采用四值(T、C、A、G)编码形式,提取了数据的重要特征.

DNA转译部分则是通过引入DNA链密码子转译框架,构建DNA链模糊匹配规则,将原始特征DNA编码转换为氨基酸参数链;在蛋白质层次上进行样本训练和分类操作.DNA转译机制进一步加强了编码系统的稳定性和容差性能.

适应度计算：通过衡量DNA种群个体与DNA操作训练样本之间氨基酸参数的绝对实际距离之和,获得种群中个体适应度.

遗传操作：按照与DNA种群个体适应度相应的概率,从DNA训练样本中选取部分个体,组成新DNA种群.对DNA种群进行交叉和变异操作,重新计算种群适应度,并将新种群中适应度最高的个体标记为最佳DNA个体.种群最佳DNA个体适应度达到设定阈值或循环次数达到最大循环次数.如不满足循环终止条件,则继续进行DNA操作.

从生物进化理论的角度看，基于DNA计算的分类模型和基于遗传算法的分类模型的基本思路和原理是相似的，但是DNA计算分类方法的核心在于利用DNA编码{A,G,C,T}提取各个类别数据的典型特征,实现主要特征的有效表达，并使用DNA操作对DNA编码的调节与控制，体现了DNA计算解决复杂问题的优势.

基于DNA计算的模糊推理方法应用于分类中，同样利用DNA编码和DNA基因操作得到模糊的IF-THEN规则达到分类的目的[15].

4 结论

由于DNA计算具有存储容量大、高度的并行性、运算速度快等的优点，使其在解决NP-问题上发挥极大的优势.数据挖掘主要应用于信息量大、需要知识进行控制和决策的领域，在数据存储和处理速度等方面都提出了更高的要求，DNA计算在存储能力和计算能力上都有着极大的潜力，DNA计算为数据挖掘问题的解决中提供一种新的思路.将DNA计算应用于数据挖掘中需要从以下几个方面进行进一步研究：（1）目前，研究人员只给出了少数分类和聚类算法的DNA计算解决方案，可对其他的数据挖掘算法做进一步研究；（2）目前只有关于聚类问题转换为图和组合优化问题后，使用DNA计算解决的方案；分类算法则是使用DNA计算结合遗传算法、模糊系统等的方式解决，下一步可以考虑把分类算法转换为图和组合优化问题后给出DNA计算模型；（3）与软计算进一步的集成，如DNA计算与遗传算法、模糊系统和神经网络等融合算法的研究，以及进一步整合在统一的框架模型；（4）与计算机技术的结合：可利用计算机技术帮助处理DNA计算机研究过程的很多辅助性技术（如显示问题等）、生化实验的计算机模拟实验等.

〔1〕倪志伟,李锋刚,毛雪岷.智能管理技术与方法[M].北京:科学出版社,2007.180-191.

〔2〕Adleman L M. Molecular computation of solutions to combinatorial problems [J]. Science, 1994,266 (5187):1021-1024.

〔3〕许进,et al.,DNA 计算机原理、进展及难点（IV）：论DNA计算机模型[J].计算机学报,2007，30(6):881-893.

〔4〕殷志祥,董亚非,许进.组合优化中的DNA 计算[J].计算机工程与应用,2002,38(19):25-27.

〔5〕张勋才,赵海兰,崔光照，等.DNA 计算的研究进展及展望[J].计算机工程与应用,2007,43(10):44-47.

〔6〕张鸿雁.基于DNA 计算的聚类算法研究[D].山东师范大学,济南,2011.

〔7〕Bakar,R.B.A.,J.Watada,Biological Clustering Method for Logistic Place Decision Making [J].Knowledge-Based Intelligent Information and Engineering Systems,2008(5179): 136-143.

〔8〕Bakar,R.B.A.,J.Watada,A Biologically Inspired Computing Approach to Solve Cluster-Based Determination of Logistic Problem[J].Biomedical Soft Computing and Human Sciences,2008.13(2):59-66.

〔9〕Bakar,R.B.A.,J.Watada,W.Pedrycz,DNA approach to solve clustering problem based on a mutual order[J].BioSystems,2008(91):1-12.

〔10〕Kim,I.,J.Watada.A DNA -Based Clustering Method Based on Statistics Adapted to Heterogeneous Coordinate Data [C].in International Conference on Complex,Intelligence and Software Intensive Systems(2009).2009::892-897.

〔11〕Xue Jie ,Liu xiyu ,Applying DNA Computing to Clustering in Graph,2nd International Conference on Artificial Intelligence, Management Science and Electronic Commerce,2011,986-989.

〔12〕薛洁,刘希玉.基于DNA 计算的层次图聚类算法[J].计算机工程,2012,38(12):188-190.

〔13〕束建华.群体智能及其在分布式知识管理中的应用研究[D].合肥工业大学,2007.

〔14〕JIAO Hongzan, ZHONG Yanfei, ZHANG Liangpei,et al. Classification of hyperspectral remote sensing data based on DNA computing [C].Journal of Remote Sensing, 2010, 14(5):865-871.

〔15〕KUMAR S, Mondal M. Classification Of Sodar Data By Dna Computing [J]. New Mathematics and Natural Computation, 2011, 7(03): 413-432.