论文部分内容阅读
膜计算是计算科学领域和生命科学的交叉研究领域的一个新的重要研究分支,其计算模型具有分布式与极大并行计算能力及容错性强的优点。对于数据进行聚类是数据挖掘与知识发现的重要组成部分,是一种处理分析数据的有效方式。聚类有多种方法,这些方法各有自己的优势与不足,分别在不同的情况下取得理想的聚类效果,基于图划分的聚类方法相对直观,易于理解和实现。随着数据量陡然增加,数据类型纷繁复杂,经典聚类算法已经不能满足当今日益变化的需要,对于聚类算法的优化研究成为领域内的研究热点。论文从P系统的设计与图划分聚类算法优化两个方面进行研究,首先提出高效的P系统变型,证明其计算通用性和解决实际问题的能力;其次,改进基于图的聚类算法,并设计P系统的结构与规则,在系统中实现优化后的图划分聚类算法,提高算法的运行效率。主要工作如下: 1.介绍了本研究涉及的膜计算与基于图划分的聚类算法的研究背景和国内外研究现状,膜计算及图论的基本理论和方法,膜计算的研究对象、结构、规则与计算框架,现有的图聚类算法发展状况,以及目前对于图聚类算法的一些改进,及本研究的创新点与难点。 2.拓展了细胞型P系统的结构形式和功能,在细胞型P系统中构造一种条件检测模式,实现P系统在将对象赋予规则之后,对规则的使用进行检测,弱化了系统的非确定性,有助于 P 系统在计算机上的实现。研究了该新型 P 系统作为数的识别装置时的识别能力,证明了带有条件检测模式的细胞型P系统在包含3个膜的状态下可以刻画递归可枚举数集。此外,将设计系统的具体结构及规则,以最小生成树的求解为例,证明该P系统在实际应用问题中的可行性。 3.提出了两个优化的图划分聚类算法。第三章提出基于拓展P系统的二次最小生成树聚类算法,该算法改进了最小生成树聚类算法,强化了结构信息在聚类中的作用,并设计了相应的膜结构和膜规则实现该算法。将改进的算法与之前的算法做实证分析,证明了我们的算法在聚类准确率方面的优越性。第四章改进了谱聚类算法中k-means易受初始聚类中心和噪声点影响的缺陷,保留谱聚类在维度约减方面的优势,设计了两个阈值在数据点的k最近邻中动态的确定类别的归 属。另外,设计P系统的结构与规则,将改进的算法进行实现。实验部分,本算法与传统谱聚类算法和基础 k-means 做了比较,在两个 UCI 数据集上都表现出更好的聚类效果,证明了算法的有效性。 4.提出并定义了关键频繁模式的概念,包括对单频繁项集和多频繁项集的内聚度提出约束以作为选择特征的参考。频繁项集特征的提取和表示以A-priori算法为基础,改善了文本数据集维度高和现有特征表示方法对语义遗漏的问题。并结合第四章中改进的聚类算法进行实验,在Reuters和WebKB两个数据集上,比较了新的特征表示方法与传统特征表示方法的效果,证明了本方法在维度约减方面效果显著,在聚类效果上也有较好表现。