论文部分内容阅读
受生物中活细胞的结构、功能等的启发,Gh.Pǎun提出了膜系统。膜系统自提出以来,引起了广大学者关注,在其基础上产生的膜计算,成为自然计算一个新的研究领域。由于膜系统是从生物细胞中抽象而来,因此具有分布式以及极大并行性的特点,能够克服串行计算的不足,大大的提高了计算的效率。通过形式化语言研究发现,膜计算的计算能力与图灵机是等价的,从而证明了在直觉上可以进行计算的函数同样可以通过膜计算来计算。因此,我们既可以利用P系统来真实的模拟细胞系统,又能够进行模型的建立和剖析,求解实际应用中遇到的问题。随着研究的深入,膜计算在经济学、密码学、电力系统诊断以及设计移动机器人控制器等方面已经取得一定进展,并展现出极大的发展空间。 对于数据进行聚类是数据挖掘与知识发现的重要组成部分,是一种处理分析数据的有效方式。在聚类研究中,提出了很多的聚类方法,我们可以根据不同的情况进行选择。本文主要对最小生成树(MST,Minimum Spanning Tree)聚类算法进行了研究,该类算法能够发现不规则边界的聚类簇,有效而合理地利用了最小生成树的几何特征以及图论的性质。在研究中发现,现有的该类算法在构造数据集的最小生成树时速度较慢,从而使得整个算法的效率降低。因此,MST聚类算法值得我们进一步的探讨和研究。本文首先对膜计算与最小生成树聚类算法的研究背景以及国内外研究现状进行了分析,其次,简单介绍了膜计算的构成、规则等理论基础等。随后,本文提出了一种新型的组织型P系统,即CFTP系统,在原有组织型P系统基础上,引入规则控制因子,对规则的实施顺序进行控制,优化规则执行流程 ,从而提高系统的运行效率。在此基础上,为解决最小生成树计算效率较慢等问题,将最小生成树算法与CFTP系统相结合,在构造最小生成树时,利用膜系统的极大并行性,使MST算法性能更优。除此之外,将最小生成树算法用于求解 K 最短路径问题,并与 CFTP 系统相结合,将数据集空间分成若干个基本的子数据集,把数据对象分配到各个膜中,使得计算出的结果簇更准确。最后,本文将基于CFTP系统的最小生成树算法应用于山东省各地市城镇化发展研究中,得到发展层次相似的城市类簇,为城镇化发展提供决策参考。 本文主要创新点如下:(1)提出了一种新的组织型P系统-CFTP系统,在原有组织型P系统基础上引入控制因子,对规则的实施顺序进行控制,优化规则执行流程,从而提高系统的运行效率。(2)提出了一种基于组织型P系统的MST聚类算法,将最小生成树算法与CFTP系统相结合,在构造最小生成树时,利用膜系统的极大并行性,使MST算法性能更优。(3)将基于CFTP系统的最小生成树算法应用于山东省各地市城镇化发展研究中,得到发展层次相似的城市类簇,为城镇化发展提供意见和建议。