基于膜计算的属性约简与划分聚类研究.pdf

重庆大学硕士学位论文 中文摘要 摘 要 膜计算是自然计算的新分支，是一个受生物细胞膜特性和功能启发从而抽象 出计算模型和方法的研究领域，包含的研究方向有膜计算模型理论研究、膜计算 模型应用研究、膜计算模型实现以及膜算法研究。由于膜计算模型中的规则执行 具有极大并行性，使它能在多项式时间内求解NP 难问题，所以，膜计算模型已经 应用于自动控制、经济学、计算机图形学等诸多领域。 属性约简是数据分析和处理中的一个基本问题，其目的是从原始数据的属性 集合里删除掉冗余的、不相关的属性，以保留最优的属性子集。基于粗糙集理论 进行属性约简是一种重要的属性约简方法，近年来取得了一系列研究成果。然而， 基于膜计算模型进行属性约简的研究鲜有报道。本文基于类细胞 P 系统模型设计 了一个基于粗糙集理论的属性约简 P 系统，其能在多项式时间内求解出所有最优 属性子集。 基于生物细胞膜在其生命周期中的进化机制，本文提出了一个新的膜进化算 法框架MEAF （Membrane Evolutionary Framework ），与传统的膜算法相比，MEAF 只需要依靠本身的进化算子进行计算而不再需要与其他算法结合。我们将 MEAF 应用于聚类问题，提出了一种新的划分聚类算法 MECA （Membrane Evolutionary Clustering Algorithm ），实验结果表明，MECA 具有良好的性能。 本文所完成的主要研究工作包括： ① 针对数据分析和处理中的属性约简问题，设计了一个基于粗糙集理论的属 性约简类细胞P 系统Π 。通过复杂度分析表明，其能在多项式时间内求解出属性 约简问题的所有最优属性子集；实例分析和仿真结果验证了Π 的可行性和有效性。 ② 针对聚类问题，本文提出了一种新的基于膜进化的划分聚类算法 MECA ， 与传统的膜算法相比，拥有了自己的进化算子。通过分析对比其他进化算法应用 于聚类问题的实验，验证了MECA 的有效性和稳定性。 本文将膜计算与属性约简和聚类分析相结合展开了相关的研究工作。研究成 果丰富了膜计算模型的应用领域，同时在理论方面，本文提出的基于膜进化算法 框架的划分聚类算法，对于进化算法和聚类算法的研究都具有一定的参考价值和 意义。 关键词：膜计算；P 系统；属性约简；划分聚类 I 重庆大学硕士学位论文 英文摘要 Abstract Membrane computing is a new branch of natural computing. It is a research field inspired by the characteristics and functions of biological cell membranes to abstract computing models and methods. The research directions include theory research of membrane computing model, application research of membrane computing model, membrane computing model implementation, and membrane algorithm research. Since the rule execution in the membrane computing model has maxi