一种基于关联分析与关联分类的蛋白质二级结构预测技术

本发明涉及蛋白质二级结构预测技术，特别涉及一种基于KDD^*过程模型的智能预测技 术，具体说是一种基于关联分析与关联分类的蛋白质二级结构预测技术(KAAPRO)。

背景技术

一、蛋白质结构预测技术：

蛋白质结构预测是后基因组时代的一项重要任务。针对蛋白质结构的研究最早可追溯至 上世纪70年代。在生物信息学领域，研究者运用信息技术及数理方法，对生物大分子(DNA 和蛋白质)进行分析，来理解生物大分子的生物学意义。蛋白质结构预测问题，在生物信息 学的诸多研究内容中占有重要地位。

就蛋白质结构研究的基本方法而言，X射线晶体学方法及多维核磁共振方法是至今为止 最有效的方法，它们能达到很高的精度，但存在测定周期长，分子量不能超过20000等局限 性。因而迫切需要一种不依赖晶体培养、迅速、简便易行的测定蛋白质结构的方法，利用蛋 白质一级结构所提供的氨基酸序列信息来进行高级结构预测的方法就是应这种需要而发展起 来的。

蛋白质的三级结构预测大致有两种路线：其一是由蛋白质的一级结构直接预测；另一种 是先根据蛋白质的一级结构预测二级结构，然后在二级结构的基础上再预测三级结构。由于 沿后一种路线的研究，同时探索一二级与二三级之间的影响，可以揭示更深层次的生物学问 题。因此，采用后一种路线将更具有理论意义。对这种路线，蛋白质的二级结构预测承上启 下，起着关键性的作用。

基于计算机程序的蛋白质二级结构预测研究已经有30多年的历史，归纳各种不同的预测 方法，大致可以分成三类：1)基于机器学习的方法(如SVM方法)；2)使用多序列排列信 息的方法(如BLAST方法)；3)使用规则和统计结合的方法(如ILP方法，Chou-Fasman方 法等)。然而近年来，蛋白质二级结构预测研究进展缓慢，虽然通过将机器学习与数据挖掘技 术引入蛋白质结构预测中等教育取得了一定成果，然而预测精度一般较低(低于80％)；同时 当前所建立的模型与方法，无法完成揭示序列与空间构象的关系，成为本世纪初分子生物学 和生物信息学领域中国际性的一大难题。

二、机器学习与数据挖掘技术：

目前在基于计算机程序的蛋白质二级结构预测领域，存在三大主流方法：基于机器学习 的、多序列排列信息的以及使用规则和统计结合的方法。正如前文所述，这些方法都假定蛋 白质的二级结构主要是由临近残基间的相互作用所决定的，然后通过对已知空间结构的蛋白 质分子进行分析和归纳，制定出一套预测规则，并根据这些规则对其它结构未知的蛋白质分 子的二级结构进行预测。这些方法各有侧重，多数方法只能在一小部分蛋白质中获得令人满 意的预测准确度，普适性较弱，因此难以推广应用。最近的研究结果表明：混合预测模型与 集成预测模型通常可以获得更优的预测准确度，吸引了一些生物信息学家的注意，并建立了 一些混合预测模型，如HYPROSP模型等。这些模型在一定程度上，提高了预测精度，一般 可提高至80％左右，但仍然存在稳定性差的不足。这主要是由于这些方法基本采用单一方法 多次复用的形式，或利用神经网络对多方结果合成的形式，由于这类方法在整体设计中未考 虑方法的层次链接，因此不能有效利用各个独立的预测子模型，相反合成金字塔模型利用层 次间的智能接口将各种子模型与方法有机融合，充分发挥各个预测子模型以及数据挖掘为主 体的方法群的优势，使整体效果达到最优。

自二十世纪六十年代中期至今，在蛋白质二级结构预测的研究中，迫切需要提出一种新 的、精度更高的预测模型与方法。数据挖掘(KDD，Knowledge Discovery in Database)是国 际学术前沿多学科交叉的新兴边缘学科，它是指从海量信息中发现新颖的、潜在有用、最终 可被用户理解的知识。由于数据挖掘(或知识发现)在处理海量数据方面具有得天独厚的优 势，而且数据挖掘领域在处理生物序列信息和预测方面已有一些较为成熟的技术，故越来越 多的学者逐渐利用数据挖掘的技术方法研究蛋白质的结构预测问题并取得了一定成果。

三、KDD^*(基于双库协同机制的KDD系统)过程模型技术：

信息挖掘即指从各种各样的信息源(包括结构化的和非结构化的信息源)中，抽取先前 未知的、完整的模式，来做关键的业务决策。它融合了人工智能、机器学习、模式识别、统计学、数 据库、计算机网络、自然语言处理等众多学科的内容，它是针对生成收集数据的能力迅猛发展， 而对信息的处理仍然采用数据统计等传统的方法，这一矛盾而产生的，并迅速发展起来的。

目前数据挖掘主要存在两个研究方向。其一：数据库的知识发现。它适用以结构化、 数值型的数据为特点的领域。其二：Web挖掘(Web Mining)。它主要处理来源于网络上的半 结构或非结构、字符型数据、多媒体数据、用户访问日志信息、网页间的超链接信息等等。 KDD技术是从大量数据中提取出可信的、新颖的、有效的并能被人理解的模式的高级处理过 程。通过这一过程，感兴趣的知识或高层信息可以从数据库相关数据集中抽取出来并从不同 角度进行研究。目前绝大部分KDD的算法没有将KDD作为认知的复杂系统对其内在的规律 性加以研究，且都没有深层次地考虑知识库，挖掘出来的许多假设规则与知识库中的已有知 识是重复的和冗余的，甚至是不相容的，并且仅靠人机交互形成聚焦，而没有体现系统自身 的认知自主性，因此对KDD定义中要求的新颖性和有效性就无法体现出来。为此，KDD^*系 统从知识发现、认知科学与智能系统交叉结合的角度，提出了双库协同机制，作为对于KDD 系列性研究中所提出的新研究方向，即内在机理的研究。构建了将KDD与双库协同机制相 结合的KDD^*结构，从而改变了KDD固有的运行机制，在结构与功能上形成了相对于KDD 而言的一个开放的、优化的扩体。双库协同机制的引入使得KDD在功能上得到了进一步的 完善，KDD^*的结构图如图1所示。

关联分析作为一种数据挖掘方法，被广泛应用到金融、生物、电信等多个领域。相对一 般数据挖掘方法，关联分析具有较强的归纳学习能力，且其取得的结果具有较好的易理解性。 作为一种新颖的关联分析数据挖掘模型，基于双库协同机制的KDD^*过程模型将知识发现系 统视为认知系统，从认知心理学的角度来考察知识发现过程，重在研究知识发现的认知自主 性。通过构造启发型协调器和维护型协调器分别模拟两个特征，实现自主发现知识短缺及知 识库的实时维护，并运用双库协同机制建立数据库和知识库的特定对应关系，从一个特定角 度揭示知识发现的潜在本质、规律与复杂性，改造知识发现过程。

本发明以双库协同机制为基础，将KDD^*过程模型引入蛋白质二级结构预测问题中，提 出了一种基于关联分析与关联分类的蛋白质二级结构预测技术(KAAPRO)(KDD^*Association Analysis PROtein secondary structure prediction)，该方法由KDD^*模型诱导的Maradbcm算法 与基于复杂度量的CBA算法构成，并且以KAAPRO为核心形成全新的逐步求精、多层递阶 的预测模型----合成金字塔模型。KAAPRO方法所取得的关联规则在一定程度上揭示了氨基 酸物化属性对蛋白质二级结构空间构象的影响关系。以KAAPRO方法为核心的合成金字塔模 型总体结构图如图2所示。

发明内容

本发明的目的在于，提供一种基于关联分析与关联分类的蛋白质二级结构预测技术 (KAAPRO)，用以克服现有的蛋白质二级结构预测方法的不足，提高预测精度。

回顾蛋白质二级结构预测的发展，我们可以看到其预测精度长时间徘徊不前的主要原因 是：1)目前的预测方法的实验色彩较浓，缺乏坚实的理论基础；2)除同源性信息外，绝大 多数领域知识没有得到充分的利用；3)混合方法是未来发展的主流，但不同方法之间如何协 同工作，优势互补，尚有待进一步的深入研究。同时发现其预测精度的每次大幅度提高的背 后，都有预测模型与方法的质的变化。在最近的研究中，混合预测模型(Hybrid Prediction Model)与集成预测模型(Ensemble Prediction Model)被广泛应用于金融、生物、电信等多 个领域。相对一般预测模型，混合预测模式与集成预测模型综合优化多个单一预测模型的结 果，使预测结果的准确度大大超过单一模型。两者的区别在于：混合预测模型一般使用多类 预测方法，而集成预测模型中只采用一种预测方法。然而这些方法的设计要不没有考虑各种 方法结果的有机结合，要不没有结合氨基酸物化属性等领域知识，这些不足严重局限了模型 整体预测精度。

生物信息学作为一个前沿领域，在最近十几年取得了长足进展，然而作为该领域中最为 重要的任务之一，蛋白质二级结构的预测，仍然是一个难以解决的问题。虽然集成预测模型 与混合预测模型的引入，为预测精度带来了一定提高，然而其距离从二级结构推导三级结构 的目标，仍然存在很大差距。为更好地解决预测蛋白质二级结构问题，在KDTICM理论框架 下，本发明提出了一种用于蛋白质二级结构预测的基于KDD^*过程模型的关联分析与关联分 类技术(KAAPRO)，并以其为核心，构建了逐步求精、多层递阶的合成金字塔模型。KAAPRO 能够较好地完成了对结构特征不明显氨基酸的预测，其所获得的关联规则易为人理解，在一 定程度上揭示了氨基酸物化属性对蛋白质二级结构空间构象的影响关系，且合成金字塔模型 在蛋白质二级结构的预测效果优势较为明显。

本发明的技术方案为：一种基于关联分析与关联分类的蛋白质二级结构预测技术 (KAAPRO)，包括：KDD^*过程模型关联分析方法；基于复杂度量的D-CBA算法。

基于KDD^*过程模型的关联分析方法，其目的是获得对C库进行挖掘的关联规则集，模型 以人工选取的方式对C数据库进行构造，具体方式为对RS126数据集分割窗口化，收集中间残 基结构为C的记录组合而成，在此基础上，在KDD^*过程模型的作用下，获得精化的关联规则 集；

基于复杂度量的D-CBA关联分类方法主要特征包括两方面：其一使用可信度与支持度的测 度作为一个复合型度量；其二根据蛋白质生物数据的特性，使用内容分别相对偏向alpha、beta 的蛋白质库；此两个数据库是以CATH分类为基础，以同源性小于30％为条件，选择α型、β 型的蛋白质而构成；利用基于KDD^*模型的Maradbcm算法对纯度较高的α蛋白质库与β蛋白 质库进行关联规则的挖掘，由此获得的挖掘结果是精化的规则，其在保证本层预测精度的同 时，为生物学家对二级结构折叠的进一步分析提供了依据；

通过基于KDD^*过程模型关联分析方法得到精化的关联规则集，复杂度量的D-CBA关联分 类方法：在合成金字塔复合结构中，核心判定层起着精化判定的重要作用，为优化层算法判 断中间层CBA算法无法判断的情况与为底层同源分析与SVM的投票层提供依据；在偏alpha、 beta型蛋白质二级结构预测中，核心判定层主要的作用是对同源分析与SVM三分类的结果的 不同的部分进行分类，主要的工具是KDD^*模型与基于支持度与可信度的复杂度量的CBA算 法，通过KDD^*系统生成的alpha、beta的规则，进行一定程度的约简后得到的精炼的alpha、 beta规则库，使用改进型CBA算法，经过对训练集的反复实验得到适用于alpha、beta库的支持 度与可信度的比例的系数；

在D-CBA的使用过程中，按照可信度的累加来作为alpha、beta的判定标准，使用可信度 与支持度的距离来作为一个复合型度量，这个更能体现两大指标在蛋白质二维结构预测中的 作用。

附图说明

图1为KDD^*的总体结构图；

图2为KAAPRO方法为核心的合成金字塔模型总体结构图；

图3为知识子库与数据子库的对应结构图，给出了知识子库中“知识结点”与相应数据子 库中“数据子类结构”中的层之间的一一对应关系；

图4为KDD^*挖掘过程示意图；

图5为问题推理过程流程图；

图6为KDD^*挖掘过程示意图；

图7为启发式协调器算法流程图；

图8为维护型协调器算法流程图；

具体实施方式

一、理论基础：

1、知识表示方法-语言场与语言值结构

定义1：C＝<D，I，N，≤N>，若满足下列条件：

(1)D为基础变量论域R上交叉闭区间的集合，D+为其对应开集；

(2)N≠Φ为语言值的有限集；

(3)≤N为N上的全序关系；

(4)I：N→D为标准值映射，满足保序性，即：n1，n2∈N(n1≠n2∧n1≤N n2→I(n1) ≤I(n2))，(≤为偏序关系)；则称C为语言场。

定义2：对于语言场C＝<D，I，N，≤N>，称F＝<D，W，K>为C的语言值结构，如 果：(1)C满足定义1；

(2)K为自然数；

(3)W：N→Rk满足：

n1，n2∈N(n1≤N n2→W(n1)≤dicW(n2)>，

n1，n2∈N(n1≠n2→W(n1)≠W(n2))。

其中，≤dic为[0，1]k上的字典序，即(a1，...。，ak)≤dic(b1，...。，bk)当且仅 当存在h，使得当0≤j＜h时aj＝bj，ah≤bh。

2、挖掘库与知识库之间泛同伦关系的建立：

1)知识结点：

定义3：在相关于论域X的知识子库中，称按如下形式表达的知识为不确定性规则型知 识：

$\left(1\right),P\left(X\right)\Rightarrow Q\left(X\right)$

其中P(X)，Pi(x)，Q(X)，Qj(X)分别为“属性词”(或“状态词”)+程度词”的形式。

定义4：在定义3中，P(X)与Pi(x)称为知识始结点，Q(X)与Qj(X)称为知识 终结点，并分别称为知识素结点；，两者统称为知识 结点。

2)数据子类(结构)：

定义5：对于论域X，在相应于知识子库的数据子库中，与每个知识素结点相应的结构S ＝<U，N，I，W>称为数据子类结构。其中，U≠Φ，U＝{u1，u2，...}，(ui是数据集，由下 述的I形成)，它是在特定的语言场与语言值结构下，表征相应于知识素结点“属性词”或“状 态词”的数据集的类(称为数据子类)；N≠Φ为语言值的有限集，它是刻划相应于知识素结点“程度 词”的语言值的集合；

I：N→U，它是按语言值将数据集的类U进行划分的映射。在数据连续分布时，通常划 分为若干交叉区间(即：${\forall }_{i,j}(u_i\cap u_j\ne \Phi ));$

W：N→[0，1]K(k为正整数)满足：

n1，n2∈N(n1≤N n2→W(n1)≤dicW(n2))，

n1，n2∈N(n1≠n2→W(n1)≠W(n2))。

3)“知识结点”与“数据子类(结构)”的关系：

定义6：设X与Y是任意的拓扑空间，称连续映射

F：X×[0，1]n→X到Y的映射的泛同伦。(通常意义下同伦概念的扩展)。

定义7：设f，g为从拓扑空间X到Y的连续映射，若存在泛同伦F(x，t)＝ft(x)，使 得对于任意点x∈X均有f(x)＝F(x，(0，...，0))，g(x)＝F(x，(1，...，1))，则称g 泛同伦于f，并称F为连续映射f与映射g的泛同伦，记作f～g。

定义8：设给定两个拓扑空间，若至少存在一个空间到另一个空间的一个泛同伦等价的 映射，则称这两个空间为同一泛同伦型的空间。

由上述分析可知：在把一个空间换成同一个泛同伦型的空间时，泛同伦类集合的结构并 无改变，所以在同伦理论里，可以把同一泛同伦型的空间看做是相同的。

3、广义细胞自动机

定义9：在离散化的欧几里德时空条件下，Ц＝<U，T，E，η>称为细胞自动机。其中，U 是状态空间U，其元素u称为状态；T是时间序列，其元素t称为时刻；E是细胞集合，其元 素e称为细胞(即空间区域)；是映射集合，元素E*T□U称为赋态映射。

定义10：∏＝<Ц，□>称为因果细胞自动机，若因果必然性规律满足下列三个条件：

(1)有限变化原理-自然界的因果必然性规律是构筑在适于描述任何时空区域的有限 集合基础上，每个时空区域都可作为这些性质的描述对象；

(2)因果存在性原理-规律支配某时空区域，则对自动机大部分区域也适用(适于似 决定论的细胞自动机)；

(3)因果一致性原理-该规律不仅适于某时空区域，而且适于整个细胞自动机，即整 个可达性时空区域(适于决定论的细胞自动机)；

定义11：归纳逻辑因果模型是满足下列条件的语义结构X＝<S，∏>

(1)S＝(S^a，S¹，......S^M)，Sⁱ为受因果必然性规律所支配的可能的因果世界，S^a为 现实的世界；Sⁱ＝(Vⁱ¹，Vⁱ²，......)，V^ij表示组成Sⁱ的不同的历史，每个历史是不同时空 段的世界。

(2)∏是满足定义10的因果细胞自动机；每个可能的因果世界都用相应的因果细胞自 动机来描述。

定义12：Γ^*＝<∏^*，→>称为广义细胞自动机，若因果必然性规律 满足定义10，和下述条件：

(1)因果状(变)态原理-在连续、渐变的因果联系过程中，对于任意样本空间而言， 细胞e在时刻t′的所有可能的状(变)态(作为结果)必然是由前一时刻t细胞e的邻域N(e) 取“正”(如语言值“小”)与“反”(如语言值“不小”)两类状态作为原因所导致的。

(2)(变态与状态转换原理)当原因与结果所取变态与状态的语言场同构时，对于因果 变态联系的规律同样适用于因果状态联系的规律，反之亦然。

4、知识短缺

启发型协调器的功能是模拟“创见意象”这一认知心理特征，从而实现系统自身发现知识 短缺(短缺知识就是知识库中到当前为止还没有的知识)。在经典KDD进程中，系统的聚焦 通常是由用户提供感兴趣方向，大量数据中的潜在有用的信息往往被用户忽略。为帮助KDD 尽可能多的搜索到对用户有用的信息，以弥补用户或领域专家自身的局限性，提高机器的认 知自主性，我们构造了启发型协调器。这样，知识发现系统在原有的用户聚焦的基础上，又 增加了系统自身提供聚焦方向的功能。

那么何为“知识短缺”呢？我们要做如下的限定：

(1)短缺知识只考虑单个后件的规则；

(2)同一属性的属性程度词不同时出现在同一规则的前件和后件中；

(3)根据具体问题确定短缺知识最多的前件个数，因为前件个数过多势必造成规则难 于理解。

(4)对某条规则e₁∧e₂∧...∧e_m→h，其规则长度为m+1：

(5)如果知识库中已有了A→B和B→C，则规则A→C就不是短缺的知识。

如何发现“知识短缺”呢？如果知识库中只考虑单前件和单后件的知识，我们可以把规则 的前件和后件看作图的顶点，利用图论中求解可达关系的方法来发现“知识短缺”。但知识库 中的规则很多都具有多个条件，为此，我们定义了有向超图来解决这个问题。

定义13：一个超图是一个二元组<V，E>，其中V＝{p₁，p₂，...p_n}是一个非空集合，它 的元素称为有向图的顶点；E＝{e₁，e₂，...，e_m}是超边的集合，其中任意的e_i(i＝1，2，...， m)都是V的一个子集。

定义14：一个有向超图是一个二元组<V，E>，其中V＝{p₁，p₂，...p_n}是素知识结点的 集合作为图的顶点，E＝{e₁，e₂，...，e_m}是知识库中规则所对应的有向边。如一条规则 r_i＝p₁∧p₂∧...∧p_k→p_j，则有向边ei＝<(p₁，p₂，...，p_k)，p_j>是一个序偶，其第一个元 素是V的一个子集，与规则的前件相对应，其第二个元素是V的一个元素，与规则的后件相 对应。

定义15：我们称与同一条超边关联的顶点互相邻接；若两条超边有一公共顶点，则称这 两条有向超边邻接。

我们使用关联规则的支持度(support)的概念来描述规则强度的客观方面。即规则A→B 的支持度是数据库事务的集合中同时包含A和B的百分比。

定义16：感兴趣度(interestingness)是指对数据库中的各属性或属性程度词的感兴趣程 度，也就是用户对知识库中知识素结点的感兴趣程度。在预处理阶段，首先由用户给出每个 属性程度词的感兴趣度，即对知识素结点e_k的感兴趣程度，记为Interestingness(e_k)，其值 域为[0，1]，该值越大，说明用户对该知识素结点越感兴趣。对于知识合结点F＝e₁∧e₂∧...∧e_m， 其感兴趣度为各知识素结点的感兴趣度的平均值，即

$\mathrm{Interesting}\left(F\right)=\underset{i=1}{\overset{m}{\Sigma }}\mathrm{Interestingness}\left(e_i\right)/m$

对于一条规则r_i：F→h，它的感兴趣度为

$\mathrm{Interestingness}\left(r_i\right)=[\underset{i=1}{\overset{m}{\Sigma }}\mathrm{Interestingness}\left(e_i\right)+\mathrm{Interestingness}\left(h\right)]/\mathrm{Len}\left(r_i\right)$

其中，Len(r_i)是规则r_i的长度。

定义17：规则强度(Intensity)包含对规则的客观的支持度和主观的感兴趣度两方面。

对规则r_i：F→h，其规则强度为

Intensity(r_i)＝[Interestingness(r_i)+support(r_i)]/2

规则强度同时考虑了主观和客观两方面。一方面，即使支持度较小，只要用户对该规则 特别感兴趣，则规则强度就不会太小，从而该知识还可以被聚焦；另一方面，如果用户对某 一规则不太感兴趣，只有该规则具有很高的支持度才有可能被聚焦。

维护型协调器的功能是模拟“心理信息修复”这一认知心理特征，从而实现知识库的实时 维护。由于维护型协调器对KDD过程的介入，可以在对于重复性、矛盾、冗余性给予准确 定义的基础上，利用超图等理论工具，实时地、尽早地将重复、矛盾、冗余的知识进行处理， 从而做到只对那些有可能成为新知识的假设进行评价，最大限度地减少了评价工作量；同时， 可对知识库进行实时维护。在实际的专家系统中，最终成为新知识的假设占原假设的比例是 很小的，大量假设会是重复和冗余的，因此维护型协调器的引入将提高KDD的效率。在这 里，首先给出知识重复、矛盾和冗余的定义，然后给出维护型协调算法。

定义18：若在可达矩阵中p(f_i1，f_i2，...，f_is)，j)＝1，则称知识R：f_i1∧f_i2∧...∧f_is→j 是重复的。

定义19：知识R：f_i1∧f_i2∧...∧f_is→j是矛盾的当且仅当在知识库中存在一个知识T：f_i1， f_i2，...，f_is→i且attr(p_i)＝attr(p_s)。

定义20：知识R：f_i1∧f_i2∧...∧f_is→j是冗余的当且仅当在知识库中存在一个知识T：f_i1， f_i2，...，f_is→i和知识K：i→j。

5.结构对应定理

基于认知心理学的“创见意象”与“心理信息修复”，发现了在知识发现过程中，在特定 的构造下，数据库与知识库间的对应关系；论证了结构对应定理。该定理给出了知识库中的 知识素结点与数据库中“数据子类结构”中的层之间的一一对应关系，如图3所示。双库协同 机制的构建从根本上解决了“定向搜索”与“定向挖掘进程”的问题。

1)结构对应定理：论域X的推理范畴Cr(N)与完全数据子类结构可达范畴C∝＜γ，c(γ) >等价.(建立了两个证明路径：(1)利用范畴论；(2)利用我们提出的连续映射的同伦理论 的拓广——泛同论理论)。

2)通过结构对应定理，可建立数据库中数据子类结构的”层”与知识库中知识”素结点”的 一一对应关系，实现定向搜索与定向挖掘.提出并实现了两个协调算法：一是对领域固有的知 识库的实时维护(通过维护型协调算法与构件)；二是自主发现知识短缺产生创见意象(通过 启发型协调算法与构件)。

3)关于双库协同机制具体实现的进一步讨论。例如：可达关系的概率估计定理：设 p＞2α+α2/(1-α)；对定义的参数β和B，令α＜β＜(1-α)p，令(1-p+pα)/(1-α)＜B＜1-α.则 随着论域X的数据库(X)中元组数目S(R)的增加，本原知识库中每一条正规则对应的数 据子类结构库中的关系为一个可达关系的概率均趋于1；每一条反规则对应的关系为非可达关 系的概率均趋于1。

二、本发明的具体技术方案：

KAAPRO方法是基于创新的KDD^*过程模型的蛋白质二级结构预测方法。包括基于KDD^*创新模型关联规则方法，以及改进的关联规则分类D-CBA(Classification Based on Association) 方法。主要涉及到KDD^*过程模型；维护型协调器；启发型协调器；Maradbcm算法；D-CBA 方法。

具体技术的实现方案：

1.KDD^*过程模型方法实现方案：

在KDD^*模型中，启发型协调器和维护型协调器是两个最重要的机制。其中启发型协调 器的功能是模拟认知心理学的“创见意象”特征，实现系统自身发现知识短缺.在经典KDD 进程中，系统的聚焦通常是由用户提供感兴趣方向，KDD依此为据进行挖掘，这种情况下大 量数据中的潜在有用的信息往往被用户忽略.为帮助KDD尽可能多的搜索到对用户有用的信 息，以弥补用户或领域专家自身的局限性，提高机器的认知自主性，启发型协调器使得知识 发现系统在原有用户聚焦的基础上，增加了系统自身提供聚焦方向的功能，从而有效提高了 数据中隐含信息的发现概率。

维护型协调器的功能是模拟“心理信息修复”这一认知心理特征，从而实现知识库的实 时维护.由于维护型协调器对KDD过程的介入，可以在对于重复性、矛盾、冗余性给予准确 定义的基础上，利用超图等理论工具，实时地、尽早地将重复、矛盾、冗余的知识进行处理， 从而做到只对那些有可能成为新知识的假设进行评价，最大限度地减少了评价工作量；同时， 可对知识库进行实时维护.在实际的专家系统中，最终成为新知识的假设占原假设的比例是很 小的，大量假设会是重复和冗余的，因此维护型协调器的引入将提高KDD的效率.

KDD^*挖掘过程示意图如图4所示，包括数据预处理、聚焦、定向挖掘、求取假设规则、 实时维护、评价；

1)数据预处理：对真实数据库中的数据进行再加工，形成发掘数据库，并与所述的基础 知识库在基于属性建库的构造下建立对应关系；

2)聚焦：由通过人机交互输入的内容来指导数据发掘的方向；

3)定向挖掘：启发型协调器搜索知识库中“知识结点”的不关联态，计算有向超图的可达 矩阵来实现发现“知识短缺”，产生“创见意象”，从而启发与激活真实数据库中相应的“数据 类”，以产生“定向发掘进程”，进而用规则强度阈值进行剪枝并由计算机自动完成聚焦。

4)求取假设规则：通过选定的知识发掘法，从发掘数据库中提取用户所需要的知识，并 用特定的模式表达所提取的知识，主要通过可信度阈值来实现(以挖掘关联规则为例)

5)实时维护：当从真实数据库的大量数据中经聚焦而生成规则(知识)后，中断型协调 器则用SQL语言或计算有向超图的可达矩阵，去搜索知识库中对应位置有无此生成规则的重 复、冗余、矛盾、从属、循环等。若有，则取消该生成规则或相应处理后返回KDD的“始端”； 若无，则继续KDD进程，即知识评价。

6)评价：对步骤5)处理后并被选取的规则进行价值评定，将被接受的规则存入衍生知 识库。

图5所示为问题推理过程流程图。

步骤1、使指针指向知识库中的第一条知识；

步骤2、判断知识库是否已经搜索完毕，如还有知识未被检索，则转步骤3；

步骤3、从知识库中将此规则提取出来；

步骤4、根据此规则前提和数据库所支持的该规则的可信度等参数，得到该规则结论的 可信度；

步骤5、判断该结论可信度是否大于可信度阈值，如不大于，则转步骤6；

步骤6、取下一条规则，系统执行步骤2；否则如可信，则转步骤7；

步骤7、使该结论作为新事实放入数据库中，如果该结论已经在数据库中了，根据可信 度计算模型重新计算新的模型，并从知识库中删除知识R，并转向执行步骤2。知识库搜索 结束后，转步骤8；

步骤8、判断数据库内容是否有增加，如有则转向步骤1；否则转步骤9；

步骤9、将数据库中的相关结论取出。

如图6所示的KDD^*挖掘过程示意图：

步骤1、对真实数据库进行预处理，形成挖掘数据库；

步骤2、将计数指针置为1；

步骤3、从挖掘数据库产生所有大于最小支持度的数据的集合，即大项集L_i；

步骤4、从知识库中产生候选集C_i+1；

步骤5、判断候选集是否为空，如果判断是肯定的，则转到步骤13；否则执行步骤6；

步骤6、计算规则强度intensity(c_m)；

步骤7、判断规则强度是否小于规则强度阈值MinIntensity，如果判断是肯定的，则执行 步骤8以删除c_m，然后转到步骤14；如果判断是否定的，则执行步骤9；

步骤8、删除c_m；

步骤9、产生知识短缺集K_i+1；

步骤10、判断知识短缺集K_i+1是否为空，如果判断是肯定的，则转到步骤13，否则执 行步骤11；

步骤11、调用KDD进程进行数据的挖掘；

步骤12、使计数指针加1后转到步骤4；

步骤13、显示产生的新观则；

步骤14、则结束本次运行。

计算有向超图的邻接矩阵P(H)的算法。

Function calculate_reach_matrix

步骤1、知识库中所有的知识素结点的ID号，1，2，...n，组成一个矩阵P_n×n，用一个 二维数组来表示P_n×n，其元素均为0，即P(i，j)＝0，其中i，j＝1，2，...，n；

步骤2、e：＝1；

步骤3、读取知识库中第e条长度为2的规则r_e：p_i→p_j；

步骤4、矩阵P(H)的元素P(i，j)＝1；

步骤5、Calculate_matrix1(j，i，n)；//调用过程Calculate_matrix1

步骤6、知识库中长度为2的规则是否读完？若没读完，则e：＝e+1，转步骤3；否则转 步骤7；

步骤7、e：＝1；

步骤8、读取知识库中的第e条长度大于2的规则r_e：p_f1∧p_f2∧...p_fj→p_i；

步骤9、Calculate_matrix2((f₁，f₂，...，f_j)，i)；//调用过程Calculate_matrix2

步骤10、知识库中长度大于2的规则是否读完？若没读完，则e：＝e+1，转步骤8；否则结 束。

过程Calculate_matrix1(j，i，n：integer)

步骤1、for k：＝1 to n

          P(j，k)：＝P(j，k)∨P(i，k)

步骤2、for m：＝1 to n

          If P(m，j)＝1 then

          for k：＝1 to n

                P(m，k)：＝P(m，k)∨P(j，k)

过程Calculate_matrix2((f₁，f₂，...，f_j)，i)//(j＞1)

步骤1、若虚结点p_f1∧p_f2∧...p_fj不存在，则可达矩阵的后面加一行表示该结点；

步骤2、P(p_f1∧p_f2∧...p_fj，i)＝1；

步骤3、for s：＝1 to n

         P(p_f1∧p_f2∧...p_fj，s)：＝P(p_f1∧p_f2∧...p_fj，s)∨P(i，s)

我们实现了找出长度不大于2的短缺知识。但对长度大于2的短缺知识则不能全部从可 达矩阵P(H)中得到，因为该矩阵中只包含了在知识库中出现的合结点。为此，我们定义了 规则强度来找出长度大于2的短缺知识。

由于规则强度中包含了支持度，因此可利用该支持度对短缺知识分层聚焦。即对长度为 2的短缺知识K₂进行聚焦，然后对长度为3的短缺知识K₃进行聚焦，直至长度为L的短缺 知识为空，即K_L＝φ；或者长度大于预先给定的最大长度M，即L＞M。K₂可直接从可达矩阵 P(H)中产生，K₂与知识库中已有的知识构成集合K₂’(${\forall r}_j\in K_2^{\prime },$support(r_j)＞min_sup) (这里min_sup是最小支持度阈值)，K₃将利用支持度从K₂’中产生。因为${\forall r}_3\in K_3,$r₃的支 持度必不大于r₃子集的支持度，即support(r₃)≤sup(r₂)，其中r₂是r₃中的任意两个知识素 结点组成的规则，而support(r₃)＞min_sup，故support(r₂)＞min_sup，因此r₂∈K′₂。

接下来，启发协调器自主地形成新聚焦以发现新知识，即产生“创见意象”。

相对于KDD而言，KDD^*是KDD与双库协同机制相融合的一种新的知识发现过 程模型，它具有以下特征：

1)KDD^*有机地沟通与融合了KDD^*新发现的知识与基础知识库中固有的知识。

2)在知识发现过程中，KDD^*有效地减少了由于过程积累而造成的问题复杂性， 同时为新旧知识的融合与合成提供了先决条件。

3)双库协同机制本身提供了随着知识库的结构变化而不断进化的能力。

4)KDD^*改变与优化了知识发现的过程与运行机制，实现了“多源头”聚焦与减 少评价量。

5)从认知科学的角度，KDD^*强化并提高了知识发现的智能化程度，提高了认知 自主性。

6)双库协同机制，揭示了在一定的建库原则下，知识子库与数据子类结构之间 的对应关系。

7)双库协同机制与其诱导的KDD^*模型，派生出新的Maradbcm算法，与目前流 行的算法对比，具有更好的可扩展性与有效性。

2.启发型协调器的实现方案：

启发型协调器是在以属性为基础的知识库建库原则下，通过搜索知识库中“知识结点”的 不关联态，以发现“知识短缺”，产生“创见意象”，从而启发与激活真实数据库中相应的“数 据子类”，以产生“定向挖掘进程”，为了防止“无序定向挖掘”现象的产生，必须规定优先级， 以定向挖掘较可信与关联性强的待定规则。

如图7所示，我们给出启发协调算法的实现步骤。

步骤1、搜索自关联强度大于某一阈值的语言变量值，形成结点集S；

步骤2、对结点集S中的结点进行组合，形成元组集合；

步骤3、搜索现有知识库，从元组中除去已在知识库中存在的元组；

步骤4、对剩余元组按关联强度排序，给出定向搜索的优先序；

步骤5、按优先级排序，并逐一扫描各元组，聚集到数据库相应入口，进行定向挖掘； 并进行KDD进程；

具体实现过程如下：

Procedure Heuristic_Coordinator(K₂)该程序模块用以产生所有长度为2的短缺知 识

步骤1、把可达矩阵从数据表ReachMatrix中读出，把support(p_i)＞min_sup的知识素 结点与全部知识合结点存入数组P中；

步骤2、K₂＝φ；

步骤3、for i：＝0 to n//可达矩阵的列数

           for j：＝0 to n//可达矩阵的列数

if(P(i，j)＝0 and attr(p_i)≠attr(p_j)and support(p_ip_j)＞min_sup)

//attr(p_i)为知识素结点p_i所对应的属性，相同属性的不同程度词不能出现在同一规则中，对i，j 对应的数据表tablei，tablej进行挖掘计算support(r_i)

K₂＝K₂∪{i→j}；

Procedure Heuristic_Coordinator(K_x-1，K_x)

该程序模块用以由长度为x-1的短缺知识产生所有长度为x(x＞2)的短缺知识

步骤1、K_x＝Φ；

步骤2、对于K_x-1中任意两规则f_i1∧f_i2∧...∧f_ix-1→j和g_i1∧g_i2∧...∧g_ix-1→i，若 f_i1＝g_i1，...，f_ix-1＝g_ix-1且j≠i，则K_x＝K_x∪{f_i1∧f_i2∧...∧f_ix-1∧i→j，f_i1∧f_i2∧...∧f_ix-1∧j→i}

步骤3、对所有r_i∈K_x

步骤4、若support(r_i)＜＝min_sup then

//对r_i对应的数据表table1，table2，...，tablep，tableq进行挖掘；计算support(r_i)

步骤5、K_x＝K_x-r_i；

3.维护型协调算法的实现方案：

维护型协调器是当从真实数据库的大量数据中经聚焦而生成感兴趣的与具有一定可信度 的规则后，使KDD进程产生“中断”，而去定向搜索知识库中对应位置有无此生成规则的重复、 冗余与矛盾，若有重复与冗余，则取消该生成规则或冗余规则而返回KDD的“始端”；若无， 则继续KDD进程；对于矛盾的处理，采用约束规则的条件与根据其可信度或关联强度来裁 决方法。其主要功能有：1)重复的处理：重复是指两条知识表达方式、内容完全一致，为此 对重复的知识进行处理，当新知识的可信度大于旧知识的可信度时，则以新知识的可信度代 替旧知识的可信度，其它的不变；否则扔掉新知识；2)矛盾的处理：矛盾是指由相同的前提 推出相反的结论，或由相反的前提推出相同的结论；3)冗余的处理：冗余是指有些新产生的 知识可以由知识库中固有的知识表达出来。

如图8所示，我们给出维护型协调器算法的实现步骤：

步骤1、对挖掘出的知识逐一判断知识的可信度是否大于给定的阈值；若是，则进入步 骤2；否则进入下一条知识的判断；

步骤2、对由步骤1得到的知识判断知识是否重复；若是，则转入步骤1；否则转入步骤 3；

步骤3、对由步骤2得到的知识判断知识是否冗余；若是，则转入步骤1；否则转入步骤 4；

步骤4、对由步骤1得到的知识判断知识是否矛盾；若是，则转入步骤1；否则将知识存 入知识库；若所有的知识处理完，则算法终止；否则转入步骤1；

基于双库协同机制——这一构建KDD过程中最重要的两个参与要素(数据库与知识库) 本质联系的认知规律，利用新的知识发现结构模型KDD^*(特别是两个协调器)，我们提出了 Maradbcm算法。该算法较好地解决Apriori算法存在的某些问题。

4.Maradbcm算法的实现方案：

Maradbcm算法赖以产生的理论基础是双库协同机制与KDD^*新结构模型。此处说明四 点：

1)根据结构对应定理，知识库中的知识素结点与数据库中数据子类结构的层相对应，也 就是和该素结点相应的属性程度词相对应。为此经过预处理^[30]把真实数据库分成n个表 (table)，即table1，table2，...，tablen，n为属性程度词的个数，而tablek中的k对应了每 个属性程度词的ID号。每个表的字段只有一个，用来存放真实数据库中的数据的ID号，该 ID所对应的数据处于属性程度词k所描述的状态。挖掘数据库就是由这n个Table组成，这 样就无需搜索整个数据库，对于每条短缺的知识只需扫描知识结点所对应几个表。这对于大 型数据库就显得尤为重要，这些小的表可以放入内存进行运算，而整个数据库就无法进行(即 Apriori算法就会受到影响)。

2)知识子库以属性为基础，其特点是便于形成知识结点与数据子类的对应关系，从而为 定向数据挖掘奠定基础。其逻辑结构是在相应的论域内，以属性为基础将规则库类化为若干 规则子库，每一规则子库与挖掘数据库相对应。

3)双库协同机制主要由启发型协调器和维护型协调器来实现。启发型协调器的功能是通 过搜索知识库中“知识结点”的不关联态，以发现“知识短缺”，产生“创见意象”，从而启发与 激活真实数据库中相应的“数据类”，以产生“定向挖掘进程”，即完成了系统自动聚焦。维护 型协调器的功能是当从真实数据库的大量数据中经聚焦而生成规则(知识)后，使KDD进 程产生“中断”，而去搜索知识库中对应位置有无此生成规则的重复、冗余、矛盾、从属、循 环等。若有，则取消该生成规则或相应处理后返回KDD的“始端”；若无，则继续KDD进程， 即知识评价。

4)KDD^*的实现主要包括启发型协调器、KDD过程和维护型协调器的功能实现。启发型 协调器主要通过计算有向超图的可达矩阵来实现发现“知识短缺”，进而用规则强度阈值进行 剪枝并形成聚焦；KDD过程主要通过可信度阈值来实现(以挖掘关联规则为例)；而维护型 协调器则用SQL语言或计算有向超图的可达矩阵来判断知识的重复、冗余、矛盾、从属、循 环等，并进行相应的处理。

下面给出Maradbcm算法的具体实现步骤：

设规则强度阈值为Min_Intensity，支持度阈值为Min_Sup，可信度阈值为Min_Con。

步骤1、数据预处理：这里主要是用户选择真实数据库，对于多值属性进行离散化。

步骤2、划分数据子库，依据子库建立数据子类结构，形成挖掘数据库；划分知识子库， 依据知识子库建立知识结点，调用过程calculate_reach_matrix产生可达矩阵，从而形成挖掘 知识库。

步骤3、调用过程Heuristic_Coordinator(K₂)产生K₂；

步骤4、m＝2；

步骤5、对K_m产生假设规则：对K_m中的短缺知识r_i：e₁∧e₂∧...∧e_p→e_q(r_i∈K_m)， 进行定向挖掘，即对数据表table1，table2，...，tablep，tableq进行挖掘，计算Con(r_i) 和Intensity(r_i)，如果Con(r_i)＞Min_Con并且Intensity(r_i)＞Min_Intensity(r_i)，则转步 骤6；否则，K_m＝K_m-r_i，转步骤8；

步骤6、对规则r_i应用维护型协调器进行处理。即若Maintenance_Coordinator(r_i)＝＝0， 则取消该生成规则或相应处理；转步骤8；若无，则转步骤7；

步骤7、对规则r_i进行评价。若评价通过则入库；若m＝＝2，调用过程Calculate_matrix1 (s，t)(r_i：(s→t))来调整超图的可达矩阵；否则调用过程Calculate_matrix2((f₁， f₂，...，f_s)，t)(r_i：(f₁∧f₂∧...∧f_s→t))来调整超图的可达矩阵。若评价没有通过，则 删除该规则；

步骤8、K_m是否结束。若结束，当m＝＝2时调用X1(P)，否则调用X2(P)；调用过程 Heuristic_Coordinator(K_m，K_m+1)来产生K_m+1.转步骤9；若没结束，则转步骤5进 行下一条规则的处理；

步骤9、m＝m+1，若K_m＝φ或者m＞M(M为预先给定的最大长度)，转步骤10；否则，转 步骤5；

步骤10、显示新产生的规则；

步骤11、结束。

过程X1(P)

步骤1、for i：＝0 to n//可达矩阵的列数

步骤2、for j：＝0 to n//可达矩阵的列数

           if(P(i，j)＝＝1)K_m＝K_m∪{i→j}；

过程X2(P)//带有结点的规则

步骤1、for i：＝n+1 to T//T为可达矩阵的行数

步骤2、for j：＝0 to n//可达矩阵的列数

        if(P(i，j)＝＝1)K_m＝K_m∪{i→j}；

5、改进型关联分类D-CBA方法技术实现方案：

在合成金字塔复合结构中，核心判定层起着精化判定的重要作用，为优化层算法判断中 间层CBA算法无法判断的情况与为底层同源分析与SVM的投票层提供依据。在偏alpha、 beta型蛋白质二级结构预测中，核心判定层主要的作用是对同源分析与SVM三分类的结果 的不同的部分进行分类。主要的工具是KDD^*模型与基于支持度与可信度的复杂度量的CBA 算法，D-CBA。通过KDD^*系统生成的alpha、beta的规则，进行一定程度的约简后得到的精 炼的alpha、beta规则库，使用改进型D-CBA算法，经过对训练集的反复实验得到适用于alpha、 beta库的支持度与可信度的比例的系数，通过实验验证其结果是可靠的，证明我们得到的 alpha、beta规则库与支持度、可信度的系数是可以作为知识固定下来，嵌入到整体的合成金 字塔模型中。

在CBA的使用过程中，我们突破常规的设定支持度的阈值，按照可信度的累加来作为 alpha、beta的判定标准，我们不单单使用可信度这个单一的度量，而是使用可信度与支持度 的距离来作为一个复合型度量，这个更能体现两大指标在蛋白质二维结构预测中的作用。

在使用规则的生产中，我们突破常规，根据蛋白质生物数据的特性，放弃了使用通用数 据库来生成规则，我们使用内容分别相对偏向alpha、beta的蛋白质库，这样解决了长期以来 的，蛋白质关联规则挖掘中存在的生成的规则的支持度与可信度较低，规则并不可信的问题， 经过试验证明与原先的蛋白质通用数据库的判定准确率有了较大的提升。

经典的CBA算法在分类问题中，在设定一个固定的支持度阈值后，单一的考虑可信度， 这样虽然简化了问题，但是相当于在问题的求解空间中，无形的约简掉了支持度维度，单一 的考虑可信度维度，我们认为这种做法在蛋白质二维结构预测问题中是不合时宜的。支持度 同样也是关联规则挖掘得到的重要参数，其中隐藏着指导分类问题规则的关键度量，所以我 们设计了基于复杂度量的CBA算法。

经典的CBA算法的评价函数如下：

${\mathrm{Score}}_{\mathrm{CBA}}^{\alpha /\beta }=\underset{i=1}{\overset{n}{\Sigma }}{\mathrm{confidence}}_i$

评价函数仅仅将符合的规则rule_i的可信度confidence_i进行简单的累加，根据 Score_CBA^α□Score_CBA^β判断蛋白质为alpha型蛋白质，如果Score_CBA^α□Score_CBA^β则判断 蛋白质为beta型蛋白质，如果差别不大，则将该条蛋白质提交到优化层处理。这样就相当于 放弃了支持度这一维的考虑，仅仅简单的使用一个支持度的阈值的设定。由于蛋白质数据是 典型的非线性数据结构，在空间呈现高度的扭曲，简单的通过设定支持度阈值的方式是不能 很好的完成蛋白质分类问题。

基于经典CBA算法的单一考虑可信度，仅仅依靠支持度阈值设定的方法是不适合的。我 们基于经典CBA算法提出了基于支持度与可信度的复杂度量的CBA算法，其评价函数如下：

${\mathrm{Score}}_{D-\mathrm{CBA}}^{\alpha /\beta }=\underset{i=1}{\overset{n}{\Sigma }}{({\left(w_{\mathrm{conf}}{\mathrm{confidence}}_i\right)}^2+{\left(w_{\sup }\sup {\mathrm{port}}_i\right)}^2)}^{1/2}$

w_conf与w_sup分别是可信度与支持度的系数，为了方便在训练中方便设定，不失一般性 的将评价参数重写为：

${\mathrm{Score}}_{D-\mathrm{CBA}}^{\alpha /\beta }=\underset{i=1}{\overset{n}{\Sigma }}{({\left({\mathrm{confidence}}_i\right)}^2+{\left(\frac{w_{\sup }}{w_{\mathrm{conf}}}\sup {\mathrm{port}}_i\right)}^2)}^{1/2}$

$=\underset{i=1}{\overset{n}{\Sigma }}{({\left({\mathrm{confidence}}_i\right)}^2+{\left(w_{\sup /\mathrm{conf}}\sup {\mathrm{port}}_i\right)}^2)}^{1/2}$

这样，当w_sup/conf→0时，Score_D-CBA^α/β退化为Score_CBA^α/β；反之，当w_sup/conf→∞时， Score_D-CBA^α/β退化为${\mathrm{Score}}_{D-\mathrm{CBA}}^{\alpha /\beta }=\underset{i=1}{\overset{n}{\Sigma }}\sup {\mathrm{port}}_i,$即仅仅考虑支持度的情况。有以上分析，可 以看出经典的CBA算法是我们所设计的基于支持度与可信度的距离的CBA算法在 w_sup/conf→0下的特例。这样，我们通过在训练集的训练，就在于选择一个分类效果最好的 w^*_sup/conf，使其可以将alpha型蛋白质与beta型蛋白质有效的进行区分。

下面给出关联分类D-CBA算法的具体实现步骤：

步骤1、基于Maradbcm算法的挖掘结果，形成alpha、beta的精化关联规则库。其中每 条规则均带有可信度和支持度两个属性；

步骤2、对于关联规则库中每条规则进行复杂度量；

步骤3、计算每条规则的评价函数，并由此得出规则的SCORE。其中评价函数为

${\mathrm{Score}}_{D-\mathrm{CBA}}^{\alpha /\beta }=\underset{i=1}{\overset{n}{\Sigma }}{({\left(w_{\mathrm{conf}}{\mathrm{confidence}}_i\right)}^2+{\left(w_{\sup }\sup {\mathrm{port}}_i\right)}^2)}^{1/2}$

步骤4、按照复杂度量SCORE对关联规则库中的规则进行从大到小排序；

步骤5、按照排序后的关联规则库进行alpha、beta分类。

步骤6、在待分类的蛋白质数据库中，找到符合优先级最高的规则的数据集，也就是符合 关联规则库中复杂度量最高的规则的条件。

步骤7、用优先级最高规则的类别结果来标记步骤6中所有满足规则条件的数据集。

步骤8、将步骤7中满足规则条件的数据库从待分类蛋白质数据库中移除。

步骤9、重复步骤6。直到关联规则库为空或者待分类蛋白质数据库为空。

步骤10、结束。

以上具体实施方式仅用于说明本发明，而非用于限定本发明。