KDD中双库协同机制的研究（Ⅰ）

摘要

针对KDD（基于数据库的知识发现）主流发展中存在的典型问题提出了用知识库去制约与驱动数据库, 并通过数据库改善知识库结构的知识发现的新思想，形成了具有双库协同机制的KDD的开放系统KDD*，从而提高了知识发现的速度、精度和认知自主性，并使知识库在结构上具备了实时维护与自我进化的能力，同时阐述了作为双库协同基础的数据库和知识库在本质上的对应关系。

正文

《1 引论》

1 引论

当前KDD (基于数据库的知识发现) 发展的主流是寻求在各类数据库和应用问题的背景下高性能、高扩展性的发掘算法。笔者另辟蹊径, 试图将KDD作为一个认知系统和智能体研究其内在的机理。这种内在机理的研究有助于当前发展的主流, 有助于解决KDD所面临的若干挑战和难题, 有助于扩展现有KDD的功能。基于此, 笔者杨于1997年从知识发现、认知科学与智能系统交叉结合的角度, 独立地提出了双库协同机制, 并构建了将KDD与双库协同机制相结合的KDD^*结构, 在结构与功能上形成了相对于KDD而言的一个开放的、优化的扩体。此外还相继提出了双基融合机制, 信息扩张机制及其扩展性结构模型等, 可能形成一个新的内在机理研究的新方向。

当我们做出了若干成果去查新文献的时候发现了一些零散的提法, 如1996年, S.S.Anand等, 在提出的基于证据理论的数据发掘一般框架ESD中, 提及了“用户的先验知识与先前发现的知识可以耦合到发现过程中”^[1];1992年, 在G.Piatesky-Shapiro等开发的知识发现平台KDW中提出过“采用领域知识辅助初始发现的聚焦, 限制性的搜索”的思想^[2];1993年, J.P.Yoon与L.Kerschberg提出一个数据库中知识发现与进化的概念, 提出使用正反两个方面的例子来发现新旧知识的协调一致, 以及知识与数据库同步进化的思想^[3]。然而, 他们都没有系统地研究其理论基础与具体实现方法。我们经过三年多的科研实践, 从理论上基本解决了双库协同的机理及其技术实现, 开发出了相应的软件, 并初步用于实际领域中^[4,5,6,7]。系列型论文 (Ⅰ) , (Ⅱ) (KDD中双库协同机制的研究 (Ⅰ) , (Ⅱ) ) 将给出双库协同机制的内在规律性、对KDD主流发展的作用及其若干应用性的结果。

双库协同的含义是什么呢?这里给出其非形式化的描述。在给定真实数据库和基础知识库的前提下, 在数据发掘过程中, 称具备以下特征的KDD中的运行机制为双库协同机制:

1) 在真实数据库上, 按数据子类结构形式所构成的发掘数据库的可达范畴与基于属性间关系的发掘知识库的推理范畴之间建立等价关系, 两个范畴的等价关系为定向发掘和定向搜索 (非全局性空间搜索) 奠定了理论基础。

2) 在KDD聚焦过程中, 除依据用户需求确定聚焦外, 通过启发协调算法可以形成依发掘知识库中知识短缺而生成的系统自身提供的聚焦方向, 进而形成在数据库中的定向发掘 (算法和进程) 。

3) 在获得假设规则到知识评价的过程中产生中断进程, 即先不对假设规则进行评价, 而是通过中断协调算法到发掘知识库中进行定向搜索 (算法和进程) , 以期发现产生的假设规则与基础知识库 (不包含挖掘出的新知识) 中原有的知识是否重复、冗余和矛盾, 并作相应处理, 即对知识库进行实时维护。

4) 知识库的结构不是单独由人为因素决定的, 而是参照数据库中的数据客观地、量化地决定的, 并且, 随着数据库中数据的积累, 知识库的结构也随之动态变化, 从而, 知识库具有了在内容和结构上自我进化的能力。

笔者旨在完成对1 (理论基础) 的讨论, 论述的核心是建立如图1所示的架构, 下面将分述之。而对2、3及4 (实现策略等) 将在另文 (Ⅱ) 中讨论。

《图1》

图1有关论域X的5个结构的关系

Fig.1 Corresponding relation between 5 structure of the universe of discourse X

《2 三个布尔代数及其关系》

2 三个布尔代数及其关系

《2.1数值域布尔代数》

2.1数值域布尔代数

《2.1.1 数值域》

2.1.1 数值域

论域X的每一个属性都对应一个“数值域”。数值域可以是有限集, 也可以是无限集;如果数值域是无限集, 则它可以是连续的, 也可以是离散的, 也可以是连续和离散兼有的。例如“温度”这个属性对应的数值域可以是 (15, 100] 这个实的半开区间。“性别”这个属性对应的数值域是 {男, 女} 这个离散的集合。但要求每一个属性对应的数值域是一个序集 (全序集) 。

属性X_i的数值域记为D_i, i=1, 2, …, s。论域X的一个采样是指从论域X测量、收集的一个s维向量, 其每一维上的分量属于相应属性的数值域。特别地, 论域X的一个现象是指论域X的一个无误差的或属于允许误差范围内的采样。

把论域X的所有属性各自对应的数值域的笛卡儿乘积称为论域X对应的数值域, 记作D。即

$D = D_{1} \times D_{2} \times \dots \times D_{s} 。$ $D = D_{1} \times D_{2} \times \dots \times D_{s} 。$

《2.1.2 数值子域》

2.1.2 数值子域

因为数值域是一个集合, 所以可以对它进行划分。依据不同的需要, 划分的方式也不一样。划分后, 数值域的子集称为数值子域。

定义1 把数值域D_i划分为t_i个数值子域D_i1, D_i2, …, D_{it_i}, 当这个划分满足如下条件时, 称为数值域D_i的正则划分:

1) 某一数值域D_i的所有数值子域的并为数值域D_i本身, 即:

$\cup_{j = 1}^{t_{i}} D_{i j} = D_{i}, i = 1, 2, \dots ‚ s 。$ $\cup_{j = 1}^{t_{i}} D_{i j} = D_{i}, i = 1, 2, \dots ‚ s 。$

2) 某一数值域的任意两个数值子域的交为空, 也就是对任意j₁≠j₂; 1≤j₁, j₂≤t_i, 有

$D_{i j_{1}} \cap D_{i j_{2}} = \emptyset 。$ $D_{i j_{1}} \cap D_{i j_{2}} = \emptyset 。$

3) 数值域D_i中元素的序和由其产生的数值子域D_i1, D_i2, …, D_{it_i}的序必须满足如下两种关系之一:

a. 数值子域依数值域中元素顺序按照升序排列, 即对任意的v₁, v₂∈D_i, v₁≤v₂, 若v₁∈D_ij₁, v₂∈D_ij₂, 则有j₁≤j₂。

b. 数值子域依数值域中元素顺序按照降序排列, 即对任意的v₁, v₂∈D_i, v₁≤v₂, 若v₁∈D_ij₁, v₂∈D_ij₂, 则有j₁≥j₂。

《2.1.3 数值域布尔代数》

2.1.3 数值域布尔代数

对每一个数值域的正则划分可以构成一个拓扑空间。对i=1, 2, …, s, 令

$E_{i} = {D_{i 1}, D_{i 2}, \dots ‚ D_{i t_{i}}} ‚$ $E_{i} = {D_{i 1}, D_{i 2}, \dots ‚ D_{i t_{i}}} ‚$

则E_i是由若干个数值子域构成的集合, 称为属性X_i的属性子域族。E_i的任意子集称为子域族。显然, 属性子域族是子域族的特殊情形。子域族的每一个元素是一个数值子域。

属性X_i的属性子域族E_i的所有子集形成它的幂集γ_i。幂集γ_i包含空集∅、属性子域族E_i和所有其他由属性X_i的若干个数值子域构成的域族。显然, 〈E_i, γ_i〉是一个拓扑空间, 称为属性X_i的数值子域划分拓扑空间。由于不考虑由属性的数值域按照自然的幂集形成的拓扑空间, 所以把属性的数值子域划分拓扑空间简称为数值域拓扑空间。对于任意y∈γ_i, y = {D_ij| D_ij∈E_i, j∈J⊆{1, 2, …, t_i}}, 定义y的真集为

$ψ (y) = \underset{j \in J}{\cup} D_{i, j} 。$ $ψ (y) = \underset{j \in J}{\cup} D_{i, j} 。$

显然, 真集ψ (y) 是数值域D_i的子集。

由于拓扑空间的乘积仍然是拓扑空间, 故〈E₁, γ₁〉×〈E₂, γ₂〉× …×〈E_s, γ_s〉也是一个拓扑空间, 记这个乘积拓扑空间为〈E, γ〉, 称为论域X的数值域划分拓扑空间, 简称为论域X的数值域拓扑空间。

在论域的数值域拓扑空间中, 存在着这样的元素:它是s个数值子域形成的序组, 其中每一个数值子域取自相应的属性子域族。称这样的序组为数值域拓扑空间的基本元, 由所有的基本元形成的集合称为基本元集。基本元集如下式所示:

$\begin{array}{l} {(d_{1}, d_{2}, \dots, d_{s}) | d_{1} \in E_{1}, \\ d_{2} \in E_{2}, \dots, d_{s} \in E_{s}} 。 (1) \end{array}$ $\begin{array}{l} {(d_{1}, d_{2}, \dots, d_{s}) | d_{1} \in E_{1}, \\ d_{2} \in E_{2}, \dots, d_{s} \in E_{s}} 。 (1) \end{array}$

把基本元集记为F。F中元素的数目为

$v = t_{1} \times t_{2} \times . . . \times t_{s} 。$ $v = t_{1} \times t_{2} \times . . . \times t_{s} 。$

在文中, v的意义保持不变, 并且, 把集合{1, 2, …, v}记为Δ。可以把基本元集排成一列, 记为F₁, F₂, …, F_v。

由乘积拓扑空间的性质, γ 是由F形成的幂集。因此, γ 中元素的数目为2^v个。对任意的y∈γ, y有如下的表示形式:

$y = {F_{i} | F_{i} \in F, i \in Ι \subseteq Δ} 。 (2)$ $y = {F_{i} | F_{i} \in F, i \in Ι \subseteq Δ} 。 (2)$

与在数值子域拓扑空间中定义真集的方式类似, 可以定义数值域拓扑空间幂集γ中的元素的真集。首先, 对任意的基本元y= (d₁, d₂, …, d_s) , 定义y的真集为

$ψ (y) = d_{1} \times d_{2} \times \dots \times d_{s} ‚$ $ψ (y) = d_{1} \times d_{2} \times \dots \times d_{s} ‚$

其中“×”为欧几里德乘积。ψ (y) 不再是一个序组, 而是数值域D中的一个子集。由此, 可以定义γ中任意元素的真集。对任意 y∈γ, y={F_j| F_j∈F, j∈J}, y的真集定义为 $ψ (y) = \underset{j \in J}{\cup} F_{j}$ $ψ (y) = \underset{j \in J}{\cup} F_{j}$ , 其中“∪”号为数值域中通常意义下集合间的并。显然, 由论域的数值域拓扑空间定义的任意真集是数值域的子集。

由真集定义可以得出, 对任意y, y₁, y₂∈γ,

$\begin{array}{l} ψ (y_{1} \cap y_{2}) = ψ (y_{1}) \cap ψ (y_{2}) ； (3) \\ ψ (y_{1} \cup y_{2}) = ψ (y_{1}) \cup ψ (y_{2}) ； (4) \\ ψ (\sim y) = \sim ψ (y) 。 (5) \end{array}$ $\begin{array}{l} ψ (y_{1} \cap y_{2}) = ψ (y_{1}) \cap ψ (y_{2}) ； (3) \\ ψ (y_{1} \cup y_{2}) = ψ (y_{1}) \cup ψ (y_{2}) ； (4) \\ ψ (\sim y) = \sim ψ (y) 。 (5) \end{array}$

但是, 在式 (3) 、式 (4) 和式 (5) 中, 等式左边的“∩”号、“∪”号和“～”号与等式右边的符号意义是不一样的。左边的符号表示对普通的集合 (数值域中的集合) 进行的操作, 而右边表示对集族进行的操作。通过真集, 可以建立数值域和它的拓扑空间之间的联系。

对任意的y₁, y₂∈γ, 根据式 (2) , y₁和y₂可以分别表示成 y₁ ={F_i| F_i∈F, i∈I₁⊆Δ}, y₂ ={F_i| F_i∈F, i∈I₂⊆Δ}。于是, y₁∩y₂ ={ F_i| F_i∈F, i∈I₁∩I₂⊆Δ}, 即y₁∩y₂∈γ, 同理可得y₁∪y₂∈γ, ～y₂∈γ。所以, 在集族γ中, 元素之间的交运算、并运算以及元素的补运算的结果仍然是γ中的元素, 即交、并、补运算在γ中是封闭的。

定理1 集族γ及其元素间的交运算“∩”和并运算“∪”以及元素的补运算“～”构成一个代数系统 (γ, ∩, ∪, ～) , 并且这个代数系统是一个布尔代数, 这个布尔代数的零元是∅;幺元是基本元集F。 (证明略)

把上述由论域X的数值域拓扑空间的幂集γ, 按照其元素间的交运算、并运算以及元素的补运算形成的布尔代数, 称为论域X的数值域布尔代数。

《2.2知识结点布尔代数》

2.2知识结点布尔代数

《2.2.1 属性程度词》

2.2.1 属性程度词

程度词是描述论域中属性状态的词语, 即语言值。对温度而言, “很高”、“高”、“中等”、“低”和“很低”等都是程度词。

属性程度词是把某一属性和它的一个程度词放在一起, 表示该属性的某种状态的词语。例如, “温度很低”是一个属性程度词。假设论域X中的每一个属性的属性程度词有有限个。对i=1, 2, …, s, 属性X_i含有t_i (t_i≥2) 个程度词。把这t_i个属性程度词按照程度的升序或降序排列, 分别记为A_i1, A_i2, …, A_{it_i}

把属性X_i的所有属性程度词构成的集合记为B_i;而把论域X的所有属性程度词构成的集合记为B。显然, $B = \cup_{i = 1}^{s} B_{i}$ $B = \cup_{i = 1}^{s} B_{i}$ 。

两个属性程度词集合在一起, 中间添加适当的析取或合取关系, 会形成新的意义。例如, 假设属性程度词a 为“温度高”, b 为“压强大”, 则a∧b 表示“温度高且压强大”, a∨b表示“温度高或压强大”。

任意一个属性程度词A_ij的非表示与属性程度词相反的意义。如果属性程度词A_ij表示“温度很高”, 则A_ij的非表示“温度很高”的非, 定义A_ij的非为

$\begin{array}{l} ┐ A_{i j} = A_{i 1} \lor \dots \lor A_{i, j - 1} \lor \\ A_{i, j + 1} \lor \dots \lor A_{i t_{i}} 。 (6) \end{array}$ $\begin{array}{l} ┐ A_{i j} = A_{i 1} \lor \dots \lor A_{i, j - 1} \lor \\ A_{i, j + 1} \lor \dots \lor A_{i t_{i}} 。 (6) \end{array}$

容易看出, 这个对非的定义与通常二值逻辑意义下对非的定义是不同的。

《2.2.2 知识结点》

2.2.2 知识结点

定义2 相应于论域X的知识结点, 是指如下不含否定联结词的合式公式:

$θ_{0} a_{1} θ_{1} a_{2} \dots θ_{m - 1} a_{m} θ_{m} (7)$ $θ_{0} a_{1} θ_{1} a_{2} \dots θ_{m - 1} a_{m} θ_{m} (7)$

其中:a_i∈B, i=1, 2, …, m;θ_i∈J, i=0, 1, …, m。这里J是由符号“∧”、“∨”、“ (” 、 “) ”等4个符号及其相应的组合以及NOP (空) 而形成的集合;但θ_i在其中取值要使合式公式 (7) 有意义;只有θ₀和θ_m可以取空。合式公式应记作F。

例如, 这里取m=3;a₁=温度很高, a₂=温度高, a₃=压强小;θ₀: (, θ₁:∨, θ₂:) ∧结构, θ₃:NOP。于是 θ₀a₁θ₁a₂θ₂a₃θ₃是一个知识结点, 它表示 (温度很高∨ 温度高) ∧ 压强小, 即同时发生或同时存在“温度很高或温度高”和“压强小”这件事情或这种状态。

当m=0时, 式 (7) 为空, 记为∅, 它表示空知识结点。属性X_i的所有属性程度词的析取是一个很重要的知识结点, 称为X_i的析取总项, 它表示该属性不作任何限制的状态, 记这个知识结点为U_i, i=1, 2, …, s。即U_i= A_i1∨A_i2∨…∨A_{it_i}。与空知识结点相反, 由论域X的所有属性程度词的析取构成的知识结点称为全知识结点, 记为Ω, 即

$Ω = \lor_{a \in B} a 。$ $Ω = \lor_{a \in B} a 。$

论域X的所有知识结点构成的集合称为论域X的知识结点集, 记为N。

《2.2.3 知识结点集的结构》

2.2.3 知识结点集的结构

在知识结点集N上, 可以定义知识结点的非以及知识结点间的合取、析取。对任意的n₁, n₂∈N, 设n₁=F₁, n₂=F₂, 自然地定义知识结点n₁与n₂的合取、析取分别为:n₁∧n₂ = F₁∧F₂;n₁∨n₂ = F₁∨F₂。

定义知识结点 n=θ₀a₁θ₁a₂…θ_m-1a_mθ_m 的非为┐n=┐ (θ₀a₁θ₁a₂…θ_m-1a_mθ_m) =θ₀′a₁′θ₁′a₂′…θ_m-1′ a_m′θ_m′。其中 θ_i′∈J, i=0, 1, …, m。当a_i′是肯定型的属性程度词时, 令其保持不变;当a_i′是否定型属性程度词时, 把它代换成式 (6) 右端的形式。经过这样的代换之后, ┐n仍然是一个不含否定联结词的合式公式。

从知识结点的三个运算的定义可以得出, 两个知识结点的合取和析取仍然是知识结点, 一个知识结点的非仍然是知识结点。从而, 合取、析取和非运算在知识结点集中是封闭的。

范式定理任一知识结点n=θ₀a₁θ₁a₂…θ_m-1a_mθ_m 均可唯一等价地表示为主析取范式的形式:

$m = L_{1} \lor L_{2} \lor \dots \lor L_{y} 。 (8)$ $m = L_{1} \lor L_{2} \lor \dots \lor L_{y} 。 (8)$

其中对i=1, 2, …, y, L_i = u_i1∧u_i2∧…∧u_{iw_i}, 均是单个属性程度词合取的形式, 其中的项称为成员项。成员项u_ij∈{a₁, a₂, …, a_m}, j=1, 2, …, w_i。事实上, u_i1, u_i2, …, u_{iw_i} 中的来自于同一属性的任意两个成员项u_ij₁, u_ij₂ 有且仅有两种关系之一:

1) 如果u_ij₁≠u_ij₂, 则由于u_ij₁∧u_ij₂=∅, 合取式L_i为∅, 项L_i就可以去掉。

2) 如果u_ij₁=u_ij₂, 则由于u_ij₁∧u_ij₂=u_ij₁, 合取式L_i经过这样的合并后, 不存在相同的属性词, L_i经合并后仍记为L_i。于是, 合并整理后的L_i成为简单合取式;并且知识结点n中简单合取式的个数不大于y, 不失一般性仍记为y;每一个简单合取式中属性程度词的数目不大于s个, 把合并整理后的每一个合取式中的属性程度词按照所归属的属性的顺序排列。若L_i中缺少某一个属性X_j的成员项, 那么把该属性的析取总项A_j1∨A_j2∨…∨A_{jt_j}人为地添加到相应的位置 (知识结点的意义不变) 。应当注意的是, 替代以后的L_i不是简单合取式, 但可以利用分配律把它变换成若干简单合取式的析取。最后得到知识结点n是若干个含有s个命题变元的简单合取式的析取:

$n = \lor_{i = 1}^{y} (\land_{j = 1}^{s} u_{i j}) ‚ (9)$ $n = \lor_{i = 1}^{y} (\land_{j = 1}^{s} u_{i j}) ‚ (9)$

其中u_ij∈B_j 。

定义3 称知识结点的式 (9) 所示的表示形式为知识结点的标准形, 相应的结点称为标准知识结点。

由式 (9) 可以看出, 标准知识结点是由一些简单合取式析取而得, 每一个简单合取式有s个成员项, 每个成员项依次取自相应的属性的程度词集。这样的简单合取式称为论域X的基本简单合取式。所有的基本简单合取式的全体构成的集合称为基本简单合取式集, 记为H。容易看出, H中元素的数目为前面定义的v。

把H中所有的元素依次记为H₁, H₂, …, H_v 。于是对任意n∈N, 有

$n = \lor_{j \in J} Η_{j} 。 (10)$ $n = \lor_{j \in J} Η_{j} 。 (10)$

其中J是集合Δ的子集。

引理1 论域X中任意两个不相同的基本简单合取式的析取为空知识结点。 (证明略)

推论若两个知识结点的标准型中没有相同的基本简单合取式, 则这两个知识结点的合取为空知识结点。

定理2 论域X的任意知识结点均可以表示成式 (9) 所示的标准形;并且标准形是唯一的。 (证明略)

表示成标准形后, 知识结点间的析取、合取运算以及知识结点的取非运算都有简单的形式:设n, n₁, n₂∈N, n =∨_i∈IH_i, n₁=∨_i∈I₁H_i, n₂=∨_i∈I₂H_i , 其中I, I₁, I₂均是包含于Δ的指标集, 容易证明:

$\begin{array}{l} n_{1} \land n_{2} = \lor_{i \in Ι_{1} \cap Ι_{2}} Η_{i} ； (11) \\ n_{1} \lor n_{2} = \lor_{i \in Ι_{1} \cup Ι_{2}} Η_{i} ； (12) \\ ┐ n = \lor_{i \in C \ Ι} Η_{i} 。 (13) \end{array}$ $\begin{array}{l} n_{1} \land n_{2} = \lor_{i \in Ι_{1} \cap Ι_{2}} Η_{i} ； (11) \\ n_{1} \lor n_{2} = \lor_{i \in Ι_{1} \cup Ι_{2}} Η_{i} ； (12) \\ ┐ n = \lor_{i \in C \ Ι} Η_{i} 。 (13) \end{array}$

其中H_i∈H。

在得出标准知识结点的合取、析取和取非运算分别如式 (11) 、式 (12) 和式 (13) 所示后, 可以更清楚地看出知识结点集的结构及其三种运算的封闭性。容易证明, (N, ∧, ∨, ┐) 是一个代数系统。

定理3 (N, ∧, ∨, ┐) 是一个布尔代数, 它的零元是空知识结点Φ;幺元是全知识结点Ω。 (证明略)

把这个由论域的知识结点集按照其元素间的合取运算、析取运算以及元素的非运算构成的布尔代数称为知识结点布尔代数。

《2.3数据子类结构布尔代数》

2.3数据子类结构布尔代数

《2.3.1 数据子类结构》

2.3.1 数据子类结构

定义4 对给定的论域X, 建立如下的关系数据库模式:

$R (Ν, X_{1}, X_{2}, \dots, X_{s}) 。 (14)$ $R (Ν, X_{1}, X_{2}, \dots, X_{s}) 。 (14)$

其中:N是主码, 它取自自然数集, 能唯一地识别一个元组;X_i是论域X的属性, i=1, 2, …, s。在模式 (14) 上建立的关系数据库称为论域X的数据库, 记为R (X) 。数据库R (X) 中的任意一个元组u是一个s+1维向量 (num, x₁, x₂, …, x_s) 的形式, 把采样 (x₁, x₂, …, x_s) 记为a (u) 。 R (X) 的所有元组的全体记为U, 即U={u_j|j∈I}, I是总指标集。

对拓扑空间〈F, γ〉中的任意开集y∈γ, 可以定义一个元组集{u|u∈R (X) , a (u) ∈ψ (y) }, 并记这个元组集为〈y, R (y) 〉。称这样的元组集为论域X的数据子类结构。y称为数据子类结构〈y, R (y) 〉的数据部分, R (y) 称为数据子类结构〈y, R (y) 〉的元组部分。论域X的所有数据子类结构形成数据子类结构集, 记为〈γ, R (γ) 〉。

《2.3.2 数据子类结构集的结构》

2.3.2 数据子类结构集的结构

在数据子类结构集中, 可以定义两个数据子类结构的相等关系为数据部分和元组部分都分别对应相等。即:〈y₁, R (y₁) 〉=〈y₂, R (y₂) 〉当且仅当y₁=y₂和R (y₁) =R (y₂) 分别成立。据此, 不同的数据子类结构可以具有相同的元组集。

下面可以建立数据子类结构集的元素运算关系。对数据子类结构集〈γ, R (γ) 〉中的任意3个元素 (可以是相等的元素) 〈y₁, R (y₁) 〉, 〈y₂, R (y₂) 〉和〈y, R (y) 〉, 定义

$\begin{array}{l} 〈 y_{1}, R (y_{1}) 〉 \cap 〈 y_{2}, R (y_{2}) 〉 = \\ 〈 y_{1} \cap y_{2}, R (y_{1}) \cap R (y_{2}) 〉 ‚ (15) \\ 〈 y_{1}, R (y_{1}) 〉 \cup 〈 y_{2}, R (y_{2}) 〉 = \\ 〈 y_{1} \cup y_{2}, R (y_{1}) \cup R (y_{2}) 〉 ‚ (16) \\ \sim 〈 y, R (y) 〉 = 〈 \sim y, \sim R (y) 〉 。 (17) \end{array}$ $\begin{array}{l} 〈 y_{1}, R (y_{1}) 〉 \cap 〈 y_{2}, R (y_{2}) 〉 = \\ 〈 y_{1} \cap y_{2}, R (y_{1}) \cap R (y_{2}) 〉 ‚ (15) \\ 〈 y_{1}, R (y_{1}) 〉 \cup 〈 y_{2}, R (y_{2}) 〉 = \\ 〈 y_{1} \cup y_{2}, R (y_{1}) \cup R (y_{2}) 〉 ‚ (16) \\ \sim 〈 y, R (y) 〉 = 〈 \sim y, \sim R (y) 〉 。 (17) \end{array}$

应当注意的是, 式 (15) 中的三个 “∩”号的意义两两不相同, 对式 (16) 和式 (17) 中的“∪”号和“～”号也是如此。从定义式 (15) 、式 (16) 和式 (17) 可以看出, 数据子类结构的“并”、“交”和“补”运算在数据子类结构集中是封闭的。容易证明 (〈γ, R (γ) 〉, ∩, ∪, ～) 构成一个代数系统。

定理4 (〈γ, R (γ) 〉, ∩, ∪, ～) 构成一个布尔代数, 其中零元为〈∅, R (∅) 〉, 幺元为〈Ω, R (Ω) 〉。 (证明略)

把这个由数据子类结构集及其元素间的交运算和并运算以及元素的补运算形成的布尔代数称为数据子类结构布尔代数。

《2.4三个布尔代数的关系》

2.4三个布尔代数的关系

《2.4.1 数值域布尔代数和知识结点布尔代数的关系》

2.4.1 数值域布尔代数和知识结点布尔代数的关系

在2.1.2节中给出了数值域正则划分的定义。从属性程度词的定义可以看出, 任意一组属性程度词可以唯一确定数值域的一个正则划分。事实上, 对论域X的任意一个属性, 如果令每一个属性程度词对应一个数值的范围, 并规定这些范围互不相交, 这些范围的并为整个属性的数值取值范围, 并且这些范围按升序或降序排列, 则该属性的所有属性程度词确定了数值子域的一个正则划分。

例如, 假设属性“温度”的数值域为[0, 100]这个闭区间, 如果定义属性程度词“温度很低”对应区间[0, 10], “温度低”对应 (10, 35], “温度中等”对应 (35, 65], “温度高”对应 (65, 90], “温度很高”对应 (90, 100], 则属性“温度”的5个属性程度词决定了数值域[0, 100]的一个正则划分。

通过属性程度词和数值域正则划分的关系, 就可以建立知识结点和数值域拓扑空间之间的关系, 有如下定理。

定理5 论域X的数值域布尔代数 (γ, ∩, ∪, ～) 和知识结点布尔代数 (N, ∧, ∨, ┐) 之间存在着同构关系。

证明首先, 对式 (1) 所示的基本元y = (d₁, d₂, …, d_s) 和式 (9) 中所含的基本简单合取式z = a₁∧a₂∧…∧a_s, 建立如下的映射关系:

$f : F \to Η,$ $f : F \to Η,$

使得

$f ((d_{1}, d_{2}, \dots, d_{s})) = a_{1} \land a_{2} \land \dots \land a_{s} 。$ $f ((d_{1}, d_{2}, \dots, d_{s})) = a_{1} \land a_{2} \land \dots \land a_{s} 。$

其中d_j对应的属性程度词为a_j。易证这个映射关系是一一对应。为了叙述方便, 改变基本元或基本简单合取式的序号, 从而可以使得

$f (F_{j}) = Η_{j} ‚$ $f (F_{j}) = Η_{j} ‚$

其中j=1, 2, …, v。

然后, 就可以把f扩张到整个的幂集γ上:

$f : γ \to Ν ‚$ $f : γ \to Ν ‚$

使得对任意的y∈γ, y ={F_j| j∈J⊆Δ}, 有

$f (y) = \lor_{j \in J} Η_{j} ‚$ $f (y) = \lor_{j \in J} Η_{j} ‚$

易证这个扩张之后的映射关系仍然是一一对应。然后证明这两个布尔代数之间存在着保运算的关系。事实上, 对任意的y₁, y₂∈γ, y₁ ={F_j| j∈J₁}, y₂ ={F_j| j∈J₂}, 有

$\begin{array}{l} f (y_{1} \cap y_{2}) = f ({F_{j} | j \in \\ J_{1}} \cap {F_{j} | j \in J_{2}}) = \\ f ({F_{j} | j \in J_{1} \cap J_{2}}) = \lor_{j \in J_{1} \cap J_{2}} Η_{j} = \\ (\lor_{j \in (J_{1} \ (J_{1} \cap J_{2})) \cup (J_{1} \cap J_{2})} Η_{j}) \land \\ (\lor_{j \in (J_{2} \ (J_{1} \cap J_{2})) \cup (J_{1} \cap J_{2})} Η_{j}) = \\ (\lor_{j \in J_{1}} Η_{j}) \land (\lor_{j \in J_{2}} Η_{j}) = f (y_{1}) \land f (y_{2}) 。 \end{array}$ $\begin{array}{l} f (y_{1} \cap y_{2}) = f ({F_{j} | j \in \\ J_{1}} \cap {F_{j} | j \in J_{2}}) = \\ f ({F_{j} | j \in J_{1} \cap J_{2}}) = \lor_{j \in J_{1} \cap J_{2}} Η_{j} = \\ (\lor_{j \in (J_{1} \ (J_{1} \cap J_{2})) \cup (J_{1} \cap J_{2})} Η_{j}) \land \\ (\lor_{j \in (J_{2} \ (J_{1} \cap J_{2})) \cup (J_{1} \cap J_{2})} Η_{j}) = \\ (\lor_{j \in J_{1}} Η_{j}) \land (\lor_{j \in J_{2}} Η_{j}) = f (y_{1}) \land f (y_{2}) 。 \end{array}$

上面的推导过程中用到了引理1及其推论。同理可以证明

$f (y_{1} \cup y_{2}) = f (y_{1}) \lor f (y_{2})$ $f (y_{1} \cup y_{2}) = f (y_{1}) \lor f (y_{2})$

和 f (～y₁) = ┐f (y₁) 。

于是f这个一一映射使两个布尔代数之间保运算, 从而这两个布尔代数同构, 并且γ的零元Φ对应着N的零结点Φ;γ的幺元F对应着N的全结点Ω。同时可以得到映射f的逆映射f^-1存在。

《2.4.2 三个布尔代数的关系》

2.4.2 三个布尔代数的关系

在2.3.1节中, 通过数值域拓扑空间中的元素定义了元组集。根据这个定义, 有:

定理6 数值域布尔代数和数据子类结构布尔代数之间存在着同构关系。

证明首先, 建立数值域布尔代数和数据子类结构布尔代数之间的映射关系:

$g : γ \to Ν$ $g : γ \to Ν$

使得对于任意y∈γ,

$g (y) = 〈 y, R (y) 〉 。$ $g (y) = 〈 y, R (y) 〉 。$

g显然是一个一一对应。于是, 对于任意y, y₁, y₂∈γ, 根据式 (15) 、式 (16) 和式 (17) , 有

$\begin{array}{l} g (y_{1} \cap y_{2}) = 〈 y_{1} \cap y_{2}, R (y_{1} \cap y_{2}) 〉 = \\ 〈 y_{1}, R (y_{1}) 〉 \cap 〈 y_{2}, R (y_{2}) = g (y_{1}) \cap g (y_{2}) 。 \end{array}$ $\begin{array}{l} g (y_{1} \cap y_{2}) = 〈 y_{1} \cap y_{2}, R (y_{1} \cap y_{2}) 〉 = \\ 〈 y_{1}, R (y_{1}) 〉 \cap 〈 y_{2}, R (y_{2}) = g (y_{1}) \cap g (y_{2}) 。 \end{array}$

同理可得

$\begin{array}{l} g (y_{1} \cup y_{2}) = g (y_{1}) \cup g (y_{2}) \\ 和 g (\sim y) = \sim g (y) 。 \end{array}$ $\begin{array}{l} g (y_{1} \cup y_{2}) = g (y_{1}) \cup g (y_{2}) \\ 和 g (\sim y) = \sim g (y) 。 \end{array}$

因此, 数值域布尔代数和数据子类结构布尔代数之间存在着同构关系, 并且, 数值域布尔代数的零元∅对应数据子类结构布尔代数的零元〈∅, R (∅) 〉;数值域布尔代数的幺元F对应数据子类结构的幺元〈Ω, R (Ω) 〉。同时可以得到映射g的逆映射g^-1存在。

由定理5和定理6, 自然可以得出定理7。

定理7 论域X的数值域布尔代数、知识结点布尔代数和数据子类结构布尔代数两两同构。 (证明略)

定理7说明了数值域拓扑空间幂集γ、知识结点集N、数据子类结构集〈γ, R (γ) 〉具有相同的代数结构。这对于知识结点的产生、数据子类结构的繁衍 (见文 (Ⅱ) ) 等具有重要意义。

《3 两个范畴及其关系》

3 两个范畴及其关系

《3.1推理范畴》

3.1推理范畴

《3.1.1 推理范畴》

3.1.1 推理范畴

给定论域X, 则它有一个知识结点集N。例如, 假设在论域X中有两个知识结点n₁ =“温度高”, n₂ =“压强大”。若论域X中存在着固有的规律是“如果温度高则压强大”, 那么知识结点n₁到n₂有推理关系:n₁→n₂, 或记为r (n₁, n₂) =r, 它表示:如果温度在“温度高”对应的子域上取值, 则压强必然在“压强大”对应的子域上取值;若存在着固有的规律是:“‘如果温度高则压强大’不成立”, 即n₁^×→n₂, 或记为r (n₁, n₂) =ϕ, 它表示:至少存在并可能出现着一个现象, 使它的温度分量在“温度高”对应的数值子域上取值时压强分量不在“压强大”对应的数值子域上取值。

定义5 称上述的知识结点n₁到n₂的推理关系n₁→n₂为一条正规则, n₁^×→n₂为一条反规则。n₁称为规则 (正规则或反规则) 的始知识结点, n₂称为规则的终知识结点。论域X上所有的正规则和反规则共同构成论域X的规则集。

定理8 论域X的知识结点集N连同其元素间的推理关系r构成一个范畴。

证明令对象类为N, 态射集hom [n_i, n_j]的元素为推理关系r或∅, 所以, hom [n_i, n_j]或者为空集, 或者只有一个元素r。如果s∈hom [n_h, n_i], t∈hom [n_i, n_j], u∈hom [n_j, n_k], 则有

1) t·s∈hom [n_h, n_j], 这是因为由n_h→n_i和n_i→n_j可以推出n_h→n_j;

2) u· (t·s) = (u·t) ·s;

3) s·l_ph= s, 并且l_pi·s = s。

这里l_ph∈hom [n_h, n_h], l_pi∈hom [n_i, n_i]。

把N连同其元素间的推理关系r构成的范畴称为论域X的推理范畴, 记为C_r (N) 。

《3.1.2 本原知识库》

3.1.2 本原知识库

定义6 论域X的知识结点集N连同知识结点之间固有的规则集称为论域X的本原知识库, 记为K^p (X) 。

本原知识库真实地反映了论域X中知识结点之间的推理关系存在与否:在本原知识库K^p (X) 中, r (n₁, n₂) =r (推理关系存在) 当且仅当论域X中n₁→n₂;在K^p (X) 中, r (n₁, n₂) =ϕ (推理关系不存在) 当且仅当论域X中n₁^×→n₂。由此, 给定论域X, 其本原知识库是唯一确定的。而且, 由于反规则集完全可以由正规则集确定, 所以如果推理范畴确定, 本原知识库也就确定了。

本原知识库K^p (X) 的规模庞大, 规则总数为2^2v。因此, 在文 (Ⅱ) 中提出知识库简约的概念和实现方法。

《3.2完全数据子类结构可达范畴》

3.2完全数据子类结构可达范畴

《3.2.1 数据库和数据子类结构的类型》

3.2.1 数据库和数据子类结构的类型

定义7 假设y是数值域布尔代数〈γ, R (γ) 〉中的一个元素, ψ (y) 是y的真集, n=f^-1 (y) 是y对应的知识结点。称2.3.1节定义的数据库R (X) 中的元组u满足y (或满足n) , 如果

$a (u) \in ψ (y) ‚ 记为 u / y ‚ 或者 u / n 。$ $a (u) \in ψ (y) ‚ 记为 u / y ‚ 或者 u / n 。$

若论域X对应的数据库R (X) 的任意一个元组u对应的向量a (u) 是论域X的一个现象 (无误差的采样) , 则称R (X) 为论域X的本原数据库, 记为R?^p (X) 。特别地, 在本原数据库中, 若对论域X的本原知识库K^p (X) 中的任意一条反规则n₁^×→n₂, R^p (X) 中均存在元组u, 使得a (u) /n₁和a (u) / (┐n₂) 都成立, 则称R^p (X) 为论域X的完全数据库, 记为R^c (X) 。

由本原数据库产生的数据子类结构称为本原数据子类结构;由完全数据库形成的数据子类结构称为完全数据子类结构。

《3.2.2 可达范畴》

3.2.2 可达范畴

定义8 在论域X的数据子类结构集〈γ, R (γ) 〉上建立元素之间的可达关系“∝”:〈y₁, R (y₁) 〉∝〈y₂, R (y₂) 〉当且仅当R (y₁) ⊆R (y₂) 。若〈γ, R (γ) 〉中元素〈y₁, R (y₁) 〉到元素〈y₂, R (y₂) 〉无可达关系, 则称〈y₁, R (y₁) 〉到〈y₂, R (y₂) 〉有非可达关系。所有的可达关系构成可达关系集;所有的非可达关系构成非可达关系集。

由论域X的关系数据库R (X) 生成的数据子类结构集〈γ, R (γ) 〉连同其元素间的可达关系集和非可达关系集构成论域X的数据子类结构库;与本原数据库和完全数据库相对应, 可以类似地定义论域X的本原数据子类结构库和完全数据子类结构库。

显然, 可达关系“∝”是一个偏序。因为任一具有偏序关系的集合均构成一个范畴, 所以有:

定理9 论域X的数据子类结构集〈γ, R (γ) 〉连同其元素间的可达关系“∝”构成一个范畴。 (证明略) 把数据子类结构集〈γ, R (γ) 〉连同其元素间的可达关系构成的范畴称为论域X的数据子类结构可达范畴, 记为C_∝〈γ, R (γ) 〉。相应地有:本原数据子类结构可达范畴, 记为C_∝〈γ, R^p (γ) 〉;完全数据子类结构可达范畴, 记为C_∝〈γ, R^c (γ) 〉。显然, 这3个范畴分别可由相应的数据子类结构库唯一确定。

《3.3两个范畴之间的关系——双库结构对应关系定理》

3.3两个范畴之间的关系——双库结构对应关系定理

引理2 论域X的推理范畴C_r (N) 到数据子类结构可达范畴C_∝〈γ, R (γ) 〉 (包括C_∝〈γ, R_-^D (γ) 〉与C_∝〈γ, R^C (γ) 〉之间存在函子。

证明首先, 建立论域X的知识结点集N到数据子类结构集〈γ, R (γ) 〉之间的自然的一一映射F_O = g f^-1:N→ 〈γ, R (γ) 〉。其中, f 和g的意义如2.4.2节所阐述。当把数据子类结构集换成本原数据子类结构集〈γ, R?^p (γ) 〉或完全数据子类结构集C_∝〈γ, R?^c (γ) 〉时, F_O的意义不变。

对任意 (n→k) ∈Hom C_r (N) , 在元组集R (n) 中任取u, 必有a (u) ∈ψ (f^-1 (n) ) , 即u/n。但由于u是本原数据库中的元组, 故它必须满足论域X本身所固有的属性间的相关规则。由规则的定义, 可得u/k, 从而a (u) ∈f^-1 (ψ (k) ) , 即u∈R (f^-1 (k) ) 。于是,

$\begin{array}{l} R (F_{Ο} (n)) \subseteq ((F_{Ο} (k)), \\ 从而 〈 f^{- 1} (n), R (f^{- 1} (n)) 〉 \propto \\ 〈 f^{- 1} (k), R (f^{- 1} (k)) 〉 。 (18) \end{array}$ $\begin{array}{l} R (F_{Ο} (n)) \subseteq ((F_{Ο} (k)), \\ 从而 〈 f^{- 1} (n), R (f^{- 1} (n)) 〉 \propto \\ 〈 f^{- 1} (k), R (f^{- 1} (k)) 〉 。 (18) \end{array}$

所以, 若有n→k, 就有式 (18) 成立。

由这个关系得到了一个从正规则集到可达关系集的映射F_H:

$\begin{array}{l} F_{Η} (n \to k) = (〈 f^{- 1} (n), R (f^{- 1} (n)) 〉 \propto \\ 〈 f^{- 1} (k), R (f^{- 1} (k)) 〉) 。 \end{array}$ $\begin{array}{l} F_{Η} (n \to k) = (〈 f^{- 1} (n), R (f^{- 1} (n)) 〉 \propto \\ 〈 f^{- 1} (k), R (f^{- 1} (k)) 〉) 。 \end{array}$

证明映射对 (F_O, F_H) 是一个函子。设任意η, ζ∈Hom C_r (N) , η= (m→n) , ζ= (n→k) 。由F_O的定义, F_O (m) =〈f^-1 (m) , R (f^-1 (m) ) 〉, F_O (n) =〈f^-1 (n) , R (f^-1 (n) ) 〉, F_O (k) =〈f^-1 (k) , R (f^-1 (k) ) 〉, 来验证 (F_O, F_H) 满足函子的4个条件:

1) F_O (dom (η) ) =dom (F_H (η) ) , 由F_H的定义, 显然成立;

2) F_O (cod (η) ) =cod (F_H (η) ) , 由F_H的定义, 显然成立;

3) comp (η, ζ) ∈Hom C_r (N) , 所以comp (F_H (η) , F_H (ζ) ) ∈Hom C_∝〈γ, R^p (γ) 〉, 于是,

$\begin{array}{l} F_{Η} (c o m p (η, ζ)) = \\ F_{Η} (c o m p (m \to n, n \to k)) = \\ F_{Η} (m \to k) = (F_{Ο} (m) \propto F_{Ο} (k)) = \\ c o m p (F_{Ο} (m) \propto F_{Ο} (n), F_{Ο} (n) \propto F_{Ο} (k)) = \\ c o m p (F_{Η} (η), F_{Η} (ζ)) ； \end{array}$ $\begin{array}{l} F_{Η} (c o m p (η, ζ)) = \\ F_{Η} (c o m p (m \to n, n \to k)) = \\ F_{Η} (m \to k) = (F_{Ο} (m) \propto F_{Ο} (k)) = \\ c o m p (F_{Ο} (m) \propto F_{Ο} (n), F_{Ο} (n) \propto F_{Ο} (k)) = \\ c o m p (F_{Η} (η), F_{Η} (ζ)) ； \end{array}$

4) 对知识结点n, 必有n→n, 因此有F_O (n) ∝F_O (n) , 即F_H (l (n) ) =l (F_O (n) ) 。故 (F_O, F_H) 是C_r (N) 到C_∝〈γ, R^p (γ) 〉的一个函子。

从引理2可见, 若C_r (N) 中m到n的推理关系存在, 则在C_∝〈γ, R?^p (γ) 〉中F_O (m) 到F_O (n) 的可达关系就存在。下面进一步给出最重要的结构对应定理。

定理10 (结构对应定理) 论域X的推理范畴C_r (N) 与完全数据子类结构可达范畴C_∝〈γ, R?^c (γ) 〉等价。

证明假设函子 (F_O, F_H) 的意义如引理2所述。由引理2的证明知, F_O 是一个一一映射, 故F_O^-1存在。

证明F_H也是一个一一映射。取C_∝〈γ, R?^c (X) 〉中的任意一个态射 (F_O (m) ∝F_O (n) ) , 需证明m→n。用反证法:若不然, 则m^×→n。由完全数据库R?^c (X) 的定义, 至少存在一个元组u, 使得u/m且u/┐n, 即u∈R (f^-1 (m) ) 但u∉R (f^-1 (n) ) , 也即关系R (f^-1 (m) ) ⊆R (f^-1 (n) ) 不成立, 从而F_O (m) ∝F_O (n) 不成立。这与假设 (F_O (m) ∝F_O (n) ) 是态射矛盾。因此, m→n, 所以F_H^-1存在。

易证, (F_O^-1, F_H^-1) 是C_∝〈γ, R?^c (γ) 〉到C_r (N) 的一个函子。所以C_r (N) 与C_∝〈γ, R?^c (γ) 〉等价。

至此, 已阐述了由论域X引出的5个代数结构及其之间的关系 (见图1) 。其中, 3个布尔代数是由论域的属性和对数值域的划分决定的, 是形式的;两个范畴是由论域中各个属性之间固有的相关规律决定的, 是内容的。

《4 进一步的讨论》

4 进一步的讨论

《4.1基本误差概率》

4.1基本误差概率

定理10的结论是:在确定完全数据子类结构可达范畴时, 本原知识库就随之确定。但实际上, 只能由论域的数据库得到数据子类结构库。因而, 前面的讨论意味着, 对本原知识库的实现要经过如下几个步骤:

1) 数据子类结构库→数据子类结构可达范畴;

2) 数据子类结构可达范畴→完全数据子类结构可达范畴;

3) 完全数据子类结构可达范畴→推理范畴;

4) 推理范畴→本原知识库。

其中, 第1、3、4步是确切的, 第2步是近似的;主要原因是数据库中元组数量不足和采样时存在误差。为了解决这个问题, 首先定义几个符号:

定义9 对论域X的数值域拓扑空间〈F, γ〉中的任意两个开集d, e, 它们对应的知识结点分别为n, k, 定义:

1) P₀ (d ) =P₀ (n) 为按照论域X中固有的概率分布某一现象属于ψ (d) (即满足知识结点n) 的概率;P₀ (e|d) =P₀ (k|n) 为按照论域X中固有的概率分布和属性相关关系, 一个现象在属于ψ (d) 的条件下, 它同时又属于ψ (e) 的条件概率;

2) P (d ) = P (n) 为采样时某一采样对应的现象 (而不是采样本身) 属于ψ (d ) 的概率;P (e|d) =P (k|n) 为采样时, 一个现象在属于ψ (d ) 的条件下, 它同时又属于ψ (e) 的条件概率;

3) P_m (d ) = P_m (n) 为一个采样属于d (即满足n) 的概率;P_m (e|d) = P_m (k|n) 为当现象属于ψ (d ) (即满足n) 时, 它对应的采样属于ψ (e) (即满足k) 的概率。

这里, 以引理的形式给出相关于定义9的一些结论:

引理3 对论域X的数值域拓扑空间〈F, γ〉中的任意两个开集d, e, 假设它们对应的知识结点分别为n, k, 则:

1) 如果P₀ (d) = 0, 则P (d) = 0 。即测量、收集采样时, 不可能获取到论域中不可能出现的现象对应的采样。于是, 如果记I₀={i|P₀ (F_i) =0, i=1, 2, …, v}, 记I₁={1, 2, …, v}/I₀, 则对i∈I₀, 有P (F_i) =0。

2) 如果n到k有推理关系n→k, 则P₀ (k|n) =1, 即P₀ (e|d ) =1, 且反之亦然;

3) P (e|d) (P₀ (e|d) , 即P (k|n) ≡P₀ (k|n) , 即每一个采样对应的现象都要满足论域X固有的属性间的相关规律。

4) P_m (d) =P_m (d|d) P (d) +P_m (d|～d) P (～d) 。 (证明略)

定义10 对数值域拓扑空间〈F, γ〉中的任意开集d, P_m (～d|d ) 的意义是:属于ψ (d) 的现象通过采样误差而使其对应的样本不属于ψ (d ) 的概率, 称为d的误差概率。对基本集F_i, 设P_m (～F_i|F_i) =α_i, i=1, 2, …, v。根据误差理论, α_i是一个接近于0的正实数, 记α=max (α₁, α₂, …α_v) , 则α是一个很小的正实数, 称为论域X的基本误差概率。

引理4 如果d是数值域拓扑空间〈F, γ〉中的任意开集, d≠∅, 则d的误差概率不大于论域X的基本误差概率。

证明假设d=∪_i∈IE_i, 由引理条件, d≠∅, 于是根据全概率公式,

$\begin{array}{l} Ρ_{m} (d | d) = Ρ_{m} (d | \cup_{i \in Ι} F_{i}) = \\ \sum_{i \in Ι} Ρ_{m} (d | F_{i}) Ρ (F_{i}) \geq \\ \sum_{i \in Ι} Ρ_{m} (F_{i} | F_{i}) Ρ (F_{i}) \geq \\ (1 - α) \sum_{i \in Ι} Ρ (F_{i}) = (1 - α) Ρ (d) \geq (1 - α) 。 \end{array}$ $\begin{array}{l} Ρ_{m} (d | d) = Ρ_{m} (d | \cup_{i \in Ι} F_{i}) = \\ \sum_{i \in Ι} Ρ_{m} (d | F_{i}) Ρ (F_{i}) \geq \\ \sum_{i \in Ι} Ρ_{m} (F_{i} | F_{i}) Ρ (F_{i}) \geq \\ (1 - α) \sum_{i \in Ι} Ρ (F_{i}) = (1 - α) Ρ (d) \geq (1 - α) 。 \end{array}$

故P_m (～d|d ) ≤α。

定义9的3中定义的“一个采样属于开集d的概率P_m (d) ”是一个很重要的量, 根据引理3的4项和引理4, 可以给出对这个量的估计:

引理5 如果d和e是拓扑空间〈F, γ〉中的任意两个开集, α是所定义的论域X的基本误差概率, 则

1) (1-α) P (d) ≤P_m (d) ≤ (1-α) P (d) +α。特别地, 当P (d) =0时, P_m (d ) ≤ (1-α) ;当P (d) =1时, P_m (d) ≥ (1-α) 。

2) 当P (d) ≠0时, P_m (e) /P_m (d ) 有意义, 它有如下估计 (证明略) :

$\frac{(1 - α) Ρ (e)}{(1 - α) Ρ (d) + α} \leq \frac{Ρ_{m} (e)}{Ρ_{m} (d)} \leq \frac{(1 - α) Ρ (e) + α}{(1 - α) Ρ (d)}$ $\frac{(1 - α) Ρ (e)}{(1 - α) Ρ (d) + α} \leq \frac{Ρ_{m} (e)}{Ρ_{m} (d)} \leq \frac{(1 - α) Ρ (e) + α}{(1 - α) Ρ (d)}$

引理6 设I₁的意义如引理3的1所述。记p=min{P (F_i) |i∈I₁}。设d和e分别是拓扑空间〈D, γ〉中的任意两个开集, e⊂d, 且至少存在k∈I₁, 使得F_k⊆d, 但F_k⊄e。如果p>2α+α²/ (1+α) , 则有:

1) P_m (d) >α;

2) P_m (e) /P_m (d) <1-α。

证明由引理条件, P (d) ≥p>2α, 根据引理5的1项, P_m (d) ≥ (1-α) P (d ) ≥ (1-α) p>2α (1-α) =2α-2α²。由于基本误差概率α是一个接近于0的正数, 所以α>2α²。故本引理的1项得证。

由p>2α+α²/ (1+α) 可得, p>α+α/ (1-α) 。从而, 1-p+α/ (1-α) < (1-α) 。由此可得

$(1 - α) - (p (1 - α) - α) < (1 - α)^{2} 。$ $(1 - α) - (p (1 - α) - α) < (1 - α)^{2} 。$

由于P (d) ≤1, (p (1-α) -α) ≥0, 故把上式的 (p (1-α) -α) 代换成 (p (1-α) -α) /P (d) , 则不等式仍然成立。即

$(1 - α) - \frac{(1 - α) p - α}{Ρ (d)} < (1 - α)^{2} 。$ $(1 - α) - \frac{(1 - α) p - α}{Ρ (d)} < (1 - α)^{2} 。$

变形得

$\frac{(1 - α) (Ρ (d) - p) + α}{Ρ (d)} < (1 - α)^{2} 。$ $\frac{(1 - α) (Ρ (d) - p) + α}{Ρ (d)} < (1 - α)^{2} 。$

根据引理条件中对基本集上的概率分布的规定, 至少存在一个基本集F_k, k⊆I₁, 使得F_k⊄d, 但F_k∉e。因此, P (e) ≤P (d) -p。故用P (e) 代替上式中的P (d) -p, 不等式仍然成立, 即

$\frac{(1 - α) Ρ (e) + α}{Ρ (d)} < (1 - α)^{2} 。$ $\frac{(1 - α) Ρ (e) + α}{Ρ (d)} < (1 - α)^{2} 。$

由引理5的2项可得P_m (e) /P_m (d) <1-α。

《4.2可信度》

4.2可信度

定义11 设 U是关系数据库R (X) 的元组集R的任意一个子集, 定义U的规模为S (U) =Size (U) =|U|, 即U中元组的数目。如果S (R (d) ) ≠0, 则把比值S (R (d) ∩R (e) ) /S (R (d) ) 称为e对d的可信度, 记为H (e/d) ;若d和e分别对应知识结点n和k, 则H (e/d ) 也记为H (k/n) , 称为知识结点k对n的可信度。

对论域X中任意两个知识结点n和k, n≠∅, 设它们分别对应拓扑空间〈F, γ〉中的两个开集d和e。对于论域X的一个固定的数据库R (X) , 数据子类结构集〈γ, R (γ) 〉也是固定的, S (R) 、 S (R (d) ) 和H (k/n) 均是一个相应的固定的数 (但对H (k/n) 要S (R (d) ) ≠0) , 其中S (R) 是数据库所有元组的总数;但当数据库R (X) 变化时, S (R (d) ) 、S (R (d) ) /S (R) 和H (k/n) 均是一个随机变量。

引理7 两个随机变量S (R (d) ) /S (R) 和H (k/n) 的数学期望分别为:P_m (d) 和P_m (e∩d) / (d) 。 (证明略)

在误差存在的情况下, 为了使论域X的数据子类结构可达范畴C_∝〈γ, R (γ) 〉仍可以用来决定推理范畴C_r (N) , 把定义9中的可达关系“∝”作适当修正。

《4.3可达关系的概率估计》

4.3可达关系的概率估计

定义12 设参数β和B都是一个正实数, 0≤β<B≤1。对于论域X的给定的数据库R (X) , 称数据子类结构〈d, R (d) 〉到〈e, R (e) 〉有可达关系, 如果S (R (d) ) ≤β|R|;或者如果S (R (d) ) >S (R) , S (R (d) ∩R (e) ) >S (R) , 并且H (e/d) ≥B. 仍把〈d, R (d) 〉到〈e, R (e) 〉有可达关系记为〈d, R (d) 〉∝<e, R (e) 〉, 称数据子类结构〈d, R (d) 〉到〈e, R (e) 〉有非可达关系, 如果S (R (d) ) >S (R) , S (R (d) ∩R (e) ) ≤S (R) ;或者如果S (R (d) ) >S (R) , S (R (d) ∩R (e) ) >S (R) , 并且H (e/d) <B。

数据子类结构库〈D, R (X) 〉中的每一个关系 (定义12所述的可达关系或非可达关系) 都对应着本原知识库K^p (X) 中一条规则, 理想的对应是:每一个可达关系对应的规则均为正规则;每一个非可达关系对应的规则均为反规则。但由于误差的存在和数据量的不足, 使理想的对应关系不一定成立。但是有

定理11 I₁的意义如引理3所述。设p>2α+α²/ (1-α) ;对定义12中定义的参数β和B, 令α<β< (1-α) p, 令 (1-p+pα) / (1-α) <B<1-α。则随着论域X的数据库R (X) 中元组数目S (R) 的增加, 本原知识库中每一条正规则对应的数据子类结构库中的关系为一个可达关系的概率均趋于1;每一条反规则对应的关系为非可达关系的概率均趋于1。

证明在论域X中任意取两个知识结点n和k, 设它们分别对应数值域拓扑空间〈F, γ〉中的两个开集d和e。

首先, 当P (n) =0时, 由定理条件中对基本集上概率分布的约定可得P₀ (n) =0, 因而恒有n→k。但由引理7, 数学期望E (S (R (d) ) /S (R) ) =P_m (d) , 把随机变量S (R (d) ) /S (R) 简记为s, 把R的规模S (R) 简记为R。由辛钦大数定律, 对任意ε>0,

$\begin{array}{l} Ρ (| s / R - Ρ_{m} (d) | < ε) \to 1, \\ 即 Ρ (Ρ_{m} (d) R - ε R (s (Ρ_{m} (d) R + ε R) \to 1, \\ Ρ (s < Ρ_{m} (d) R + ε R) \to 1 。 \end{array}$ $\begin{array}{l} Ρ (| s / R - Ρ_{m} (d) | < ε) \to 1, \\ 即 Ρ (Ρ_{m} (d) R - ε R (s (Ρ_{m} (d) R + ε R) \to 1, \\ Ρ (s < Ρ_{m} (d) R + ε R) \to 1 。 \end{array}$

由引理5, P_m (d) ≤α, 故 (s<αR+εR) →1。而定理条件中约定β>α, 又因ε是任意的, 所以 P (s<βR) →1。

由定义12, 正规则n→k对应的〈d, R (d) 〉到〈e, R (e) 〉的关系为可达关系的概率随数据库R (X) 的元组数目的增加而趋于1。

当P (n) ≠0时, 根据定理条件, 有P₀ (d) ≠0, 这种情况下, 当P (e) =0时, 必有P₀ (e) =0, 从而n^×→k, 用与上面类似的方法可以证明, 它对应着〈d, R (d) 〉到〈e, R (e) 〉的关系为非可达关系的概率趋于1。当P (e∩d) ≠0时又分两种情况:n到k为正规则 (n→k) 的情况和n到k为反规则 (n^×→k) 的情况。因为第一种情况的证明与当P (n) =0时的证明类似, 所以这里只讨论第二种情况。

当n到k为反规则时, P₀ (d) ≠0, 且至少存在k∈I₁, 使得E_k⊆d, 但Ek⊄e。与前面的结论类似, 首先有

$\begin{array}{l} Ρ (S (R (d)) > β | R |) \to 1, (19) \\ 和 Ρ (S (〈 e \cap d, R (e \cap d) 〉) > β | R |) \to 1 。 (20) \end{array}$ $\begin{array}{l} Ρ (S (R (d)) > β | R |) \to 1, (19) \\ 和 Ρ (S (〈 e \cap d, R (e \cap d) 〉) > β | R |) \to 1 。 (20) \end{array}$

把随机变量H (e/d) 简记为h, 则由引理7, E (h) =P_m (e∩d) /P_m (d) , 把P_m (e∩d) /P_m (d) 简记为r。由辛钦大数定律, 对任意ε>0, 随着元组数目的增加,

$\begin{array}{l} Ρ (| h - r | < ε) \to 1, \\ 因而 Ρ (h < r + ε) \to 1 。 \end{array}$ $\begin{array}{l} Ρ (| h - r | < ε) \to 1, \\ 因而 Ρ (h < r + ε) \to 1 。 \end{array}$

由引理6的2, r<1-α. 故 P (h<1-α+ε) →1, 但ε是任意的, B> (1-α) , 所以

$Ρ (h < B) \to 1 。 (21)$ $Ρ (h < B) \to 1 。 (21)$

由式 (19) 、式 (20) 和式 (21) 以及定义12, 反规则 (n^×→k) 对应〈d, R (d) 〉到〈e, R (e) 〉的关系为非可达关系的概率随元组数目的增加而趋于1。

基本误差概率α可以通过经验给出, 或利用领域的基础知识和数据库计算得出。当α为0时, 定理11的结论显然成立。此时的数据子类结构库退化为本原数据子类结构库。可以证明:如果对任意i∈I₁, P (F_i) >0, 则随着元组数目的增加, 本原数据库成为完全数据库的概率趋于1。

《5 结论》

5 结论

阐述了双库协同机制的涵义, 双库协同机制下的知识库及其结构、数据库及其结构, 以及两库之间在本质上的对应关系。只有揭示出这种对应关系, 才能完成定向搜索和定向发掘, 为实现文 (Ⅱ) 中的两个协调算法及其构件奠定了理论基础, 并为构造新的知识发现的结构模型KDD^*作了铺垫。

展示更多