两类生物计算问题及其在数据挖掘中的应用研究

发布时间：2017-03-18 22:09

  本文关键词：两类生物计算问题及其在数据挖掘中的应用研究，由笔耕文化传播整理发布。

【摘要】：作为生物计算的新的研究内容，膜计算从生物体的自身运行机制和合作原理，即细胞、组织等结构中获得灵感，设计出P系统。到现在为止，主要的P系统有三大类：cell-like（细胞）P系统，tissue-like（组织）P系统，Spiking Neural （神经）P系统。这些P系统都是从生命体机制，如细胞、组织中概括提取出来的。膜计算的主要研究方向包括：膜系统的计算能力与计算效率，新型膜计算模型，膜计算的应用以及实现。得益于膜计算具有的并行性特点，膜计算已应用到经济学、语言学、生物建模、密码学、计算机图形学等多个领域，解决了许多问题。 DNA计算是以生物DNA为基础的计算，通过DNA分子的变性、复性退火等操作，在特定环境下，在试管中或表面上或芯片上进行反应，从而得出问题解集的过程。DNA计算具有三个显著优势(1)高并行性，运算速度快(2)DNA作为信息的载体，存储容量大。(3)DNA分子生物计算耗能低。研究DNA计算的热门所在，主要为：对于新的DNA模型的发现、分析与研究；能够解决非确定多项式问题的具体的DNA模型；构造基于DNA求解问题的装置并使之自动化等。 数据挖掘，是从数据中获取知识和信息的过程。在大数据背景下，针对其出现的新特点，如何对数据进行有效分析，从庞大的信息中发掘可利用的知识，提升数据的有效性和可阅读性，有待数据挖掘研究学者提出合理、可用的方法。聚类分析是一种处理数据（信息）的有用方法或技术。作为数据挖掘极其重要的一部分，聚类有着多种方法，如系统法，动态聚类法，模糊聚类方法等。这些方法各有优缺点，分别在某些特定的情况下取得了理想的聚类效果。论文从基于膜计算的聚类算法和基于DNA计算的聚类算法两个方面进行了研究，主要工作如下： (1)Pǎun曾说：“设计实现新的P系统是膜计算领域的一条重要发展道路”。本文首先对三种主要的膜计算模型进行了扩展，分别提出了基于层结构的膜系统模型，带有动态促进/抑制因子的组织型膜计算模型和具有拓展规则及多输出的脉冲神经模型。在数学图形学、拓扑学中，应用较多的一个理论叫做离散Morse理论。这一理论能够剖析一些离散图形结构的拓扑类型。将膜系统与新型数据结构(如单纯形、复形等)结合，提出基于格（偏序结构）的交流膜系统，基于单纯形的交流膜系统，并使用形式语言证明其计算完备性。 作为一种新型的计算方法，膜计算在聚类分析中的应用并不多。结合膜计算的强大并行能力，本文提出了基于动态促进/抑制因子的组织型膜系统的拓扑聚类算法，使用带有动态促进/抑制因子的组织型膜系统规则实现具体聚类步骤，通过一个包含十个数据点的示例说明了算法实施的可行性，与传统操作方法进行了时间复杂度的比较。将改进的脉冲神经膜计算模型与菱形网格相结合，提出基于拓展规则及多输出的脉冲神经膜系统的网格聚类，给出算法的规则，膜系统结构，通过包含多个数据点的示例说明了算法是管用的。提出基于格（偏序结构）的新型结构交流膜计算模型，设计了上确界和下确界规则，通过规则在膜系统中实现了密度聚类算法，减少了算法的时间复杂度，，提供了聚类算法的新思想。本文将所提出的基于膜计算的聚类算法应用于具体问题中，给出了三个方面的应用，包括：膜计算、DNA计算在真实数据集中的应用、膜计算在文本聚类以及在空气质量评估中的应用。 (2）使用著名Adleman模型、改进的粘贴模型以及K-臂DNA计算模型进行聚类分析。提出了基于Adlman-Lipton计算模型的拓扑聚类算法，基于改进的粘贴DNA计算模型的拓扑方法和基于k-臂即三维DNA模型的划分方法。分别将DNA计算与层次聚类，网格聚类等算法相结合。基于Adlman-Lipton计算模型的拓扑聚类算法，用单链DNA表示顶点和各个顶点之间的边，使用DNA测试分子序列顺序的方法与凝胶电泳方法，两种方法共同作用得到最小生成树，随后，按照一个具体数值（反应之前给定的）删除大于这个数值的边，结果中可连通的顶点的子图数目即聚类的簇的个数。基于改进的粘贴DNA计算模型的拓扑聚类算法中，首先，对于粘贴模型的存储与粘贴链结构、基本操作进行了补充、改进，然后，结合Chamlon算法进行聚类。基于k-臂DNA计算模型的划分聚类算法中，将DNA计算与网格聚类思想相结合，使用网格将二维数据转换到不同的单元格上，设定核心，对每个核心及其连接的顶点进行4-臂DNA编码，在试管中并行产生DNA团，以达到聚类的目的。 本文对传统的膜计算模型进行了扩展，并且提出了新型结构膜系统，使用形式语言证明其计算能力，将扩展的膜系统与新型膜系统用于数据挖掘聚类分析中，并通过实验进行了比较分析。使用著名Adleman模型、改进的粘贴模型以及K-臂DNA计算模型进行聚类分析。将上述技术应用到实际问题中。由于膜计算、DNA计算的并行性，在处理数据挖掘任务方面有着极大的潜力，不论在生物信息领域，还是商务智能领域都有着重要意义。
【关键词】：膜计算 DNA计算 数据挖掘 聚类分析
【学位授予单位】：山东师范大学
【学位级别】：博士
【学位授予年份】：2015
【分类号】：TP311.13;TP38
【目录】：

• 摘要7-10
• ABSTRACT10-14
• 1 绪论14-28
• 1.1 研究背景和意义14-15
• 1.2 研究现状及发展趋势15-23
• 1.2.1 膜计算的研究现状及发展趋势15-18
• 1.2.2 DNA 计算的研究现状及发展趋势18-20
• 1.2.3 聚类算法的研究现状及发展趋势20-23
• 1.3 论文研究内容及组织23-28
• 1.3.1 研究内容23-24
• 1.3.2 论文的创新点24-26
• 1.3.3 论文内容组织26-28
• 2 主要膜计算模型的扩展28-37
• 2.1 膜计算基本符号、概念及模型28-33
• 2.1.1 细胞型 P 系统29-30
• 2.1.2 组织型 P 系统30-31
• 2.1.3 神经型 P 系统31-33
• 2.2 三种主要的膜计算模型的扩展33-37
• 2.2.1 层结构细胞型膜计算模型33-34
• 2.2.2 带有动态促进/抑制因子的组织型膜计算模型34-35
• 2.2.3 具有拓展规则及多输出的脉冲神经膜计算模型35-37
• 3 新型结构膜计算模型研究37-57
• 3.1 新型结构膜计算模型37-44
• 3.1.1 基于格（偏序结构）的交流膜计算模型37-40
• 3.1.2 基于单纯形的交流膜计算模型40-44
• 3.2 新型结构膜计算模型计算能力证明44-57
• 3.2.1 形式语言与自动机理论基础44-47
• 3.2.2 格交流膜计算模型计算能力证明47-53
• 3.2.3 单纯形交流膜计算模型计算能力证明53-57
• 4 基于膜计算的聚类算法研究57-78
• 4.1 基于动态促进/抑制因子的组织型膜系统的拓扑聚类算法57-63
• 4.1.1 基本思想57-59
• 4.1.2 算法计算过程描述59-60
• 4.1.3 实验验证60-63
• 4.2 基于拓展规则及多输出的脉冲神经膜系统的网格聚类算法63-69
• 4.2.1 菱形网格图概念及描述63-65
• 4.2.2 聚类问题转化65-67
• 4.2.3 算法有效性验证67-69
• 4.3 基于格结构交流膜系统的密度聚类算法69-78
• 4.3.1 基本思想69-70
• 4.3.2 膜系统设计70-71
• 4.3.3 实验验证71-75
• 4.3.4 基于格结构交流膜系统的三种聚类算法对比75-78
• 5 基于 DNA 计算的聚类算法研究78-101
• 5.1 DNA 计算模型78-82
• 5.1.1 Adlman-Lipton DNA 计算模型78-80
• 5.1.2 改进的粘贴 DNA 计算模型80-81
• 5.1.3 k-臂 DNA 计算模型81-82
• 5.2 基于 DNA 计算的聚类算法研究82-101
• 5.2.1 基于 Adlman-Lipton 计算模型的拓扑聚类算法82-87
• 5.2.1.1 算法思想及流程分析82-83
• 5.2.1.2 实验验证83-86
• 5.2.1.3 算法步骤分析86-87
• 5.2.2 基于改进的粘贴 DNA 计算模型的拓扑聚类算法87-91
• 5.2.2.1 算法思想及过程描述87-90
• 5.2.2.2 实验验证90-91
• 5.2.3 基于 k-臂 DNA 计算模型的划分聚类算法研究91-101
• 5.2.3.1 网格树设计91-92
• 5.2.3.2 聚类问题到网格树的转化92-94
• 5.2.3.3 实验验证94-97
• 5.2.3.4 算法分析97-101
• 6 基于膜计算、DNA 计算的数据挖掘应用101-123
• 6.1 膜计算、DNA 计算在真实数据集中的聚类应用101-107
• 6.1.1 膜计算在膀胱炎病人病例数据集中的聚类应用101-106
• 6.1.2 DNA 计算在鸢尾花数据集中的聚类应用106-107
• 6.2 膜计算在文本聚类中的应用107-112
• 6.3 膜计算在空气质量评估中的分类应用112-123
• 7 总结与展望123-126
• 7.1 总结123-125
• 7.2 进一步的工作125-126
• 参考文献126-141
• 攻博期间发表的科研成果目录141-144
• 致谢144

【参考文献】

中国期刊全文数据库 前10条

1 程乾生;属性识别理论模型及其应用[J];北京大学学报(自然科学版);1997年01期

2 刘文斌,高琳,王淑栋,刘向荣,许进;最大匹配问题的DNA表面计算模型[J];电子学报;2003年10期

3 刘慧卿;张先起;;空气质量综合评价的基于熵权的属性识别模型[J];环境科学与技术;2008年07期

4 周康;同小军;许进;;基于闭环DNA模型的八皇后问题算法[J];计算机工程与应用;2007年06期

5 刘希玉;张建萍;;一种基于密度聚类的一般观点——拓扑聚类[J];计算机工程与应用;2007年26期

6 许进,张雷;DNA计算机原理、进展及难点(Ⅰ):生物计算系统及其在图论中的应用[J];计算机学报;2003年01期

7 许进,黄布毅;DNA计算机:原理、进展及难点(Ⅱ)计算机“数据库”的形成——DNA分子的合成问题[J];计算机学报;2005年10期

8 许进;张社民;范月科;郭养安;;DNA计算机原理、进展及难点(Ⅲ):分子生物计算中的数据结构与特性[J];计算机学报;2007年06期

9 许进;谭钢军;范月科;郭养安;;DNA计算机原理、进展及难点(Ⅳ):论DNA计算机模型[J];计算机学报;2007年06期

10 张兴义;曾湘祥;潘林强;罗斌;;脉冲神经膜系统求解任意两个自然数的乘积[J];计算机学报;2009年12期

  本文关键词：两类生物计算问题及其在数据挖掘中的应用研究，由笔耕文化传播整理发布。

本文编号：255108