一类大数据挖掘的“特质技法库”构造技术

本发明基于我们提出的原创性知识发现理论KDTICM(获三项重要国际奖励，得国 内外著名科学家“原创性理论”的评价)，发明了领域知识驱动、形态递进、逐层递阶的数据 挖掘“特质技法库”构造技术，融模型与算法于一体，集领域通用与专业特用于一体，用来解 决传统数据挖掘技术无法解决的在线过程控制与预测中的若干难题。

一、数据挖掘技术：

自二十世纪六十年代中期至今，在蛋白质二级结构预测的研究中，迫切需要提出 一种新的、精度更高的预测模型与方法。由于数据挖掘(或知识发现)在处理海量数据方面 具有得天独厚的优势，而且知识发现领域在处理生物序列信息和预测方面已有一些较为成 熟的技术，故越来越多的学者逐渐利用数据挖掘的技术方法研究蛋白质的结构预测问题并 取得了一定成果。

数据挖掘(知识发现)是国际学术前沿多学科交叉的新兴边缘学科，它是指从海量 信息中发现新颖的、潜在有用、最终可被用户理解的知识。它融合了人工智能、机器学习、模 式识别、统计学、数据库、计算机网络、自然语言处理等众多学科的内容，它是针对生成收集 数据的能力迅猛发展，而对信息的处理仍然采用数据统计等传统的方法，这一矛盾而产生 的，并迅速发展起来的。

通过数据挖掘(KDD，Knowledge Discovery in Database)过程，感兴趣的知识或 高层信息可以从数据库相关数据集中抽取出来并从不同角度进行研究。目前绝大部分KDD 的算法没有将KDD作为认知的复杂系统对其内在的规律性加以研究，且都没有深层次地考 虑知识库，挖掘出来的许多假设规则与知识库中的已有知识是重复的和冗余的，甚至是不 相容的，并且仅靠人机交互形成聚焦，而没有体现系统自身的认知自主性，因此对KDD定义 中要求的新颖性和有效性就无法体现出来。为此，KDD*过程模型从知识发现、认知科学与智 能系统交叉结合的角度，提出了双库协同机制。构建了将KDD与双库协同机制相结合的KDD* 过程模型，从而改变了KDD固有的运行机制，在结构与功能上形成了相对于KDD而言的一个 开放的、优化的扩体。双库协同机制的引入使得KDD在功能上得到了进一步的完善，KDD系统 的流程框图如图1所示。

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

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

一、本发明的目的在于，公开了一类大数据挖掘的“特质技法库”构造技术，该发明 属大数据分析与挖掘领域。该构造技术利用了我们提出的原创性知识发现理论KDTICM，并 将“过程模型”和“算法”有机融合，发明了领域知识驱动、形态递进、逐层递阶的数据挖 掘“特质技法库”构造技术，此系列发明融模型与算法于一体，集领域通用与专业特用于一 体，用来解决传统数据挖掘技术无法解决的在线过程控制与预测中的若干难题

本发明提出一种全新大数据挖掘的“特质技法库”的构造技术。该模型融合了“过 程模型”和“算法”。

二、本发明的技术方案为：一类大数据挖掘的“特质技法库”的构造技术，其模型由 以下三个发明点构成。

1)“过程模型”：发明了基于内在认知机理研究、全程融入领域知识的数据挖掘 “过程模型”，从本质上提升了经典知识发现系统的运行流程。

2)“算法”：发明了由模型驱动的多层级数据挖掘“算法”，解决了从结构化 数据，到非(半)结构化数据，再到高阶逻辑知识挖掘的效率、精度、可扩展性等系列关键技 术问题。

3)“特质技法库”：发明了领域知识驱动的、形态递进、逐层递阶的“特质技法库”构 造技术，将“过程模型”与“算法”有机融合，为其在各个领域间的应用搭建了桥梁。

三、本发明技术方案的特征与优势：由所构造的大数据挖掘的“特质技法库”的分 析可知，具有以下特征与优势：

1)发现了双库协同机制。把知识发现本体(过程或系统)作为研究对象，基于认知 心理学的“创见意象”与“心理信息修复”，通过论证结构对应定理发现了在特定构造下数据 库与知识库间的对应关系，设计了启发型协调器与维护型协调器，构建了KDD*模型，解决了 定向搜索、定向挖掘、自主发现、实时维护、领域知识参与发现过程等难题。

结构对应定理：论域X的推理范畴Cr(N)与完全数据子类结构可达范畴
等价。

2)发现了双基融合机制。发明了知识库中知识发现系统，通过论证过程模型逻辑 等价定理，将数据库中的知识发现与知识库中的知识发现统一在一个系统(过程)中。设计 了R型协调器、S型协调器与T型协调器，发明了KDK*模型，解决了KDK依赖与部分转化为KDD 的难题。

过程模型逻辑等价定理：设KDK的过程模型为M＝，KDD的过程模型为N＝ ，在依知识结点网络构建知识库，依数据子类结构构建数据库的条件下，M与 N逻辑等价。

3)发明了基于双库协同机制与双基融合机制的综合型知识发现过程模型KD(D& K)。KD(D&K)模型具有多个抽象级，涵盖了不同知识层面的多层递阶，是综合集成的知识发 现过程模型，与KDD及KDK的区别如表1所示。

表1KD(D&K)与KDD/KDK的特征对比表

4)提出了挖掘结构化数据的系列算法。针对单关系结构化数据，从降低长度较短 的模式的处理代价入手，提出了包含索引数据组织形式，进而提出了频繁模式挖掘的系列 新算法，精简了挖掘结果的数量，提高了挖掘效率，改进效果明显，如表2所示。针对多关系 结构化数据，构造了适用于多关系数据流环境的数据概要模型，论证了保证容差的最大周 期采样率的计算方法，进而提出了多关系数据流决策树算法，改善了分类精度。

表2.M算法与Clementine在关联规则挖掘方面的比较

5)发明了非(半)结构化数据挖掘新方法。通过构造Hilbert子空间融入领域知识， 将非(半)结构化数据的特征抽取、变换与映射过程融为一体(图3)，加快了简约特征子空间 的选取过程，提高了挖掘非(半)结构化数据的效率，在Web挖掘等领域取得了良好效果。

6)提出了知识库中知识发现的新算法。在KDK*模型的基础上，针对知识库中的事 实，采用归纳学习方法产生假设，再用卡尔纳普的归纳逻辑进行验证与评价；针对知识库中 的规则，采用广义概念格方法产生假设，再用柯恩的归纳逻辑进行验证与评价。

7)构造了特质技法库的运行流程。将“过程模型”与“算法”有机融合，以领域 知识为贯穿，按结构化数据挖掘层—非(半)结构化数据挖掘层--知识库挖掘层等构成了多 层形态递进挖掘进程；每一层面都全部内含了我们原创性的模型与算法，并形成了相互联 系、无缝对接的技法，其运行流程如图4所示。

8)将特质技法库作为智能系统的知识获取方法库，发明了新的智能系统构造方 法。构建了具有多知识源、多知识融合、多抽象级等特征的专家系统和智能决策支持系统， 使用创新的数据挖掘方法作为新的知识自动获取构件，为传统智能系统增加了新的知识获 取渠道，从根本上改善了长期困扰智能系统领域的“知识匮乏”的瓶颈问题。智能决策支持 系统结构图如图4所示。

9)自主设计了作为“特质技法库”载体的软件系统ICCKDSS。ICCKDSS集成了本项目 发明的系列模型与算法，可有效解决结构化数据、非(半)结构化数据、知识库的挖掘问题， 被列为“国家重点推广计划项目”。

图1为现有技术的KDD系统的流程框图；

图2为本发明所采用的KDD*结构图；

图3为本发明所采用的非(半)结构化数据挖掘方法；

图4为本发明所采用的智能决策支持系统结构图；

图5为本发明所采用的基于领域知识驱动、形态递进、逐层递阶的“特质技法库”的 运行流程；

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

图7为KDD*挖掘过程示意图；

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

图9为KDD*挖掘过程流程图

一、理论基础：

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

定义1：C＝，若满足下列条件：

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

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

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

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

定义2：对于语言场C＝，称F＝为C的语言值结构，如果：(1)C 满足定义1；

(2)K为自然数；

(3)W：N→Rk满足：

∀ n 1 , n 2 ∈ N ( n 1 ≤ N n 2 → W ( n 1 ) ≤ d i c W ( n 2 ) > ,

∀ n 1 , n 2 ∈ N ( n 1 ≠ n 2 → W ( n 1 ) ≠ W ( n 2 ) ) .

其中，≤dic为[0，1]k上的字典序，即(a1，…。，ak)≤dic(b1，…。，bk)当且仅当存 在h，使得当0≤j

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

1)知识结点：

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

(1) P ( X ) ⇒ Q ( X )

(2)

(3)

(4)

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

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

2)数据子类(结构)：

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

I：N→U，它是按语言值将数据集的类U进行划分的映射。在数据连续分布时，通常
划分为若干交叉区间(即：(ui∩u_j≠Φ))；

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

∀ n 1 , n 2 ∈ N ( n 1 ≤ N n 2 → W ( n 1 ) ≤ d i c W ( n 2 ) ) ,

∀ n 1 , n 2 ∈ N ( n 1 ≠ n 2 → W ( n 1 ) ≠ W ( n 2 ) ) .

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

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

F：X×[0,1]n→Y为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：设给定两个拓扑空间，若至少存在一个空间到另一个空间的一个泛同伦等 价的映射，则称这两个空间为同一泛同伦型的空间。

由上述分析可知：在把一个空间换成同一个泛同伦型的空间时，泛同伦类集合的 结构并无改变，所以在同伦理论里，可以把同一泛同伦型的空间看做是相同的。给出了知识 子库中“知识结点”与相应数据子库中“数据子类结构”中的层之间的一一对应关系，如图6 所示。

3、广义细胞自动机

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

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

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

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

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

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

(1)S＝(Sa，S1，……SM)，Si为受因果必然性规律所支配的可能的因果世界，Sa为现 实的世界；Si＝(Vi1，Vi2，……)，Vij表示组成Si的不同的历史，每个历史是不同时空段的世 界。

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

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

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

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

4、知识短缺

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

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

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

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

(3)根据具体问题确定短缺知识最多的前件个数，因为前件个数过多势必

造成规则难于理解。

(4)对某条规则e1∧e2∧…∧em→h，其规则长度为m+1：

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

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

定义13：一个超图是一个二元组，其中V＝{p1，p2，…pn}是一个非空集合，它 的元素称为有向图的顶点；E＝{e1，e2，…，em}是超边的集合，其中任意的ei(i＝1，2，…，m) 都是V的一个子集。

定义14：一个有向超图是一个二元组，其中V＝{p1，p2，…pn}是素知识结点的 集合作为图的顶点，E＝{e1，e2，…，em}是知识库中规则所对应的有向边。如一条规则ri＝p1 ∧p2∧…∧pk→pj，则有向边ei＝<(p1，p2，…，pk)，pj>是一个序偶，其第一个元素是V的一个 子集，与规则的前件相对应，其第二个元素是V的一个元素，与规则的后件相对应。

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

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

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

I n t e r e s t i n g ( F ) = Σ i = 1 m I n t e r e s t i n g n e s s ( e i ) / m

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

I n t e r e s t i n g n e s s ( r i ) = [ Σ i = 1 m I n t e r e s t i n g n e s s ( e i ) + I n t e r e s t i n g n e s s ( h ) ] / L e n ( r i )

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

定义17：规则强度(Intensity)包含对规则的客观的支持度和主观的感兴趣度两 方面。对规则ri:F→h，其规则强度为

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

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

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

定义18:若在可达矩阵中p(fi1，fi2，…，fis)，j)＝1，则称知识R:fi1∧fi2∧…∧fis →j是重复的。

定义19:知识R:fi1∧fi2∧…∧fis→j是矛盾的当且仅当在知识库中存在一个知识 T:fi1，fi2，…，fis→i且attr(pi)＝attr(ps)。

定义20:知识R:fi1∧fi2∧…∧fis→j是冗余的当且仅当在知识库中存在一个知识 T:fi1，fi2，…，fis→i和知识K:i→j。

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

金子塔模型是一种全新的逐步求精、多层递阶的预测系统模型，其集成与混合了 由多种属原创型、新型与改进型方法组成的方法。其模型共有四层，分别为综合分析层、 辅助判定层、核心判定层、结果优化层，每层中集成了多个方法。其中综合分析层中集成了 同源性分析与优化的SVM类化分析；辅助判定层中层采用优化的SVM二分类方法，以及基于 KDD*过程模型的M算法；核心判定层是原创性的基于KDTICM理论的KDD*模型与M算法，以及 改进的关联规则分类CBA方法；结果优化层主要设计倾向性因子、位能函数及合情推理三类 方法。

下面分别论述合成金子塔模型中各层次主要涉及的具体技术的实现方案：

1、基于KDD*过程模型的Maradbcm算法技术实现方案:

KDD*挖掘过程示意图如图7所示，包括

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

KDD*挖掘过程流程图如图9所示：

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

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

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

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

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

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

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

步骤8：删除cm；

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

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

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

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

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

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

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

Function calculate_reach_matrix

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

步骤2、e:＝1；

步骤3、读取知识库中第e条长度为2的规则re:pi→pj；

步骤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的规则re:pf1∧pf2∧…pfj→pi；

步骤9、Calculate_matrix2((f1，f2，…，fj)，i)；//调用过程Calculate_matrix2

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

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

步骤1、for k:＝1to n

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

步骤2、for m:＝1to n

If P(m，j)＝1then

for k:＝1to n

P(m，k):＝P(m，k)∨P(j，k)Procedure

过程Calculate_matrix2((f1，f2，…，fj)，i)//(j>1)

步骤1、若虚结点pf1∧pf2∧…pfj不存在，则可达矩阵的后面加一行表示该结点

步骤2、P(pf1∧pf2∧…pfj，i)＝1；

步骤3、for s:＝1to n

P(pf1∧pf2∧…pfj，s):＝P(pf1∧pf2∧…pfj，s)∨P(i，s)

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

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

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

启发型协调器算法的实现步骤：

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

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

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

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

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

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

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

步骤2、K2＝φ；

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

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

if(P(i,j)＝0and attr(pi)≠attr(pj)and support(pipj)>min_sup)//attr(pi) 为知识素结点pi所对应的属性,相同属性的不同程度词不能出现在同一规则中，对i,j对应 的数据表tablei,tablej进行挖掘计算support(ri)

K2＝K2∪{i→j}；

Procedure Heuristic_Coordinator(Kx-1,Kx)

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

步骤1、Kx＝Φ；

步骤2、对于Kx-1中任意两规则fi1∧fi2∧…∧fix-1→j和gi1∧gi2∧…∧gix-1→i,若 fi1＝gi1,…,fix-1＝gix-1且j≠i,则Kx＝Kx∪{fi1∧fi2∧…∧fix-1∧i→j,fi1∧fi2∧…∧fix-1 ∧j→i}

步骤3、对所有ri∈Kx

步骤4、若support(ri)<＝min_sup，则对ri对应的数据表table1,table2,…, tablep,tableq进行挖掘；计算support(ri)

步骤5、Kx＝Kx-ri；

维护型协调器算法的实现步骤：

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

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

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

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

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

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(K2)产生K2；

步骤4、m＝2；

步骤5、对Km产生假设规则：对Km中的短缺知识ri：e1∧e2∧…∧ep→eq(ri∈Km)，进 行定向挖掘，即对数据表table1，table2，…，tablep，tableq进行挖掘，计算Con(ri)和 Intensity(ri)，如果Con(ri)>Min_Con并且Intensity(ri)>Min_Intensity(ri)，则转步骤 6；否则，Km＝Km-ri，转步骤8；

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

步骤7、对规则ri进行评价。若评价通过则入库；若m＝＝2，调用过程Calculate_ matrix1(s，t)(ri:(s→t))来调整超图的可达矩阵；否则调用过程Calculate_matrix2((f1， f2，…，fs)，t)(ri:(f1∧f2∧…∧fs→t))来调整超图的可达矩阵。若评价没有通过，则删除 该规则；

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

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

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

步骤11、结束。

过程X1(P)

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

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

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

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

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

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

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

2.双库对应原理

Neisser把认知心理学定义为“由感官获取的信息的传输、简约、分散、存储、恢复 和使用的全过程”，这与数据挖掘认知过程惊人地相似。于是我们利用认知心理学的两个重 要特征(即“创建意象”与“心理信息修复”)来研究数据挖掘的两个重要主题,：(1)通过模拟 “创建意象”来实现系统自主发现知识短缺,实施启发式的聚焦(除用户感兴趣式的聚焦 外)；(2)通过模拟“心理信息修复”来实现知识库的实时维护。即对于BDM而言，不能仅就数 据库论数据挖掘，而要利用其“外力”---知识库，即领域知识驱动数据挖掘；实现“用户的先 验知识与先前发现的知识可以耦合到发现过程中”。

在巨大的数据集面前，要实现上述两个主题，就必须避免的全局搜索和全局挖掘, 而要采取“定向搜索”和“定向挖掘”；从而,等效地缩小搜索空间、降低算法的复杂度。为此, 必须在数据挖掘进程中、数据库和知识库的特定构造下,建立二者之间的某种对应关系。

我们有如下结果：

定义21:论域X的知识结点集N连同其元素间的推理关系r构成一个范畴。把N连同 其元素间的推理关系r构成的范畴，称为论域X的推理范畴,记为Cr(N)。

定义22:论域X的数据子类结构集连同其元素间的可达关系“∝”构成一
个范畴(证略)。把连同“∝”构成的范畴称为X的数据子类结构可达范畴,记为
相应的本原数据子类结构可达范畴记为完全数据子类结构
可达范畴记为

定义23：论域X的推理范畴Cr(N)到本原数据子类结构(完全数据子类结构)可达范
畴之间存在函子。

证：首先，我们建立论域X的知识结点集N到数据子类结构集之间的自然
的1-1映射:其中，f和g的意义分别为1-1映射。当把数据子
类结构集换成本原数据子类结构集或完全数据子类结构集时，FO的
意义不变。

对任意(n→k)∈HomCr(N)，在元组集中任取u,必有a(u)∈ψ(f-1(n)),也即u/
n。但由于u是本原数据库中的元组，故它必须满足论域X本身所固有的属性间的相关规律。
由规则的定义，可得u/k,从而a(u)∈f-1(ψ(k))，即于是，
从而所以，若有n→
k，就有上式成立。于是，我们由这个关系得到了一个从正规则集到可达关系集的映射FH：

下面我们证明映射对(Fo,FH)是一个函子。

设任意η,ζ∈HomCr(N)，η＝(m→n),ζ＝(n→k).由FO的定义，
我们来验证
(FO,FH)满足函子的4个条件：FO(dom(η))＝dom(FH(η))。由FH的定义，显然成立。FO(cod
(η))＝cod(FH(η)).由FH的定义，显然成立。

因为comp(η,ζ)∈HomCr(Ν),所以
于是，FH(comp(η,ζ))＝FH(comp(m→n,n→k))＝FH(m→k)＝(FO(m)∝FO(k))＝comp(FO(m)
∝FO(n),FO(n)∝FO(k))＝comp(FH(η),FH(ζ))。

对知识结点n，必有n→n，因此有FO(n)∝FO(n).也就是说，FH(1(n))＝1(FO(n))。

故(FO,FH)是Cr(Ν)到的一个函子。证毕。

从定义23可见，若Cr(Ν)中m到n的推理关系存在，则在中FO(m)到
FO(n)的可达关系存在，但反之却不一定成立。因此，进一步地，我们给出双库对应原理中最
重要的范畴等价定理：

定义24：(结构对应定理)论域X的推理范畴C_r(N)与完全数据子类结构可达范畴
等价。

证：假设函子(FO FH)的意义如引理3所述。由引理3的证明知：FO是一个1-1映射， 故FO-1存在。下面再证明FH也是一个一一映射。

取中的任意一个态射(FO(m)∝FO(n)),我们要证明m→n。反证：若
不然，则m×→n.由完全数据库的定义，至少存在一个元组u,使得u/m且即
但也即关系不成立，从而FO(m)∝FO
(n)不成立。这与假设(FO(m)∝FO(n))是态射矛盾。因此，m→n.所以FH-1存在。

容易证明，(FO-1,FH-1)是到Cr(Ν)的一个函子。所以Cr(Ν)与
等价。

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