基于DNA计算的层次图聚类算法  

Hierarchical Graph Clustering Algorithm Based on DNA Computing

作　　者：薛洁[1] 刘希玉[1] 

机构地区：[1]山东师范大学管理科学与工程学院,济南250014

出　　处：《计算机工程》2012年第12期188-190,共3页Computer Engineering

基　　金：国家自然科学基金资助项目"基于计算智能算法的聚类技术研究(60873058);国家自然科学基金资助项目"基于DNA计算与离散Morse理论的聚类研究分析"(61170038);山东省自然科学基金资助项目(ZR2011FM001);山东省软科学重大基金资助项目(2010RKMA2005)

摘　　要：为解决使用DNA计算图聚类问题,提出一种基于DNA计算的层次图聚类算法。在分裂层次聚类中,使用DNA分子对图中顶点、边进行编码,在试管中并行产生最小生成树,根据给定阈值,通过切割树枝得到聚类结果。在凝聚聚类中使用DNA计算产生哈密尔顿路径,通过寻找最短哈密尔顿路径得到聚类结果。实验结果验证了该算法的可行性。This paper uses DNA computing to solve graph clustering,provides a new approach to analyze graph problems.In split-level clustering,it uses DNA strands to assign vertices and edges,constructs the minimum spanning tree and cuts branches whose length is longer than the threshold,and gets the clustering results.In agglomerative hierarchical clustering,DNA computing to the undirected Shortest Hamilton Path（SHP） problem is introduced,and the clustering results are gotten.Experimental results prove the feasibility of the algorithm.

关 键 词：DNA计算 图聚类 分裂聚类算法 凝聚聚类算法 最小生成树 最短哈密尔顿路径 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]