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

摘要

在“KDD中双库协同机制的研究（Ⅰ）”的理论基础上，实现了对知识库的简约并实现了双库协同机制的两个协调器，从而建立了由KDD融入双库协同机制的新结构模型——KDD^*，这是一个在结构和功能上相对于KDD而言的开放的、优化的扩体。基于双库协同机制与KDD^*，提出了挖掘关联规则和聚类规则的新算法，充分体现了内在机理研究对主流发展的影响，开辟了一条全新的研究方向与路径。

正文

《1 构建供挖掘的知识库》

1 构建供挖掘的知识库

《1.1规则的简约表示》

1.1规则的简约表示

文献[1] 建立了论域中按数据子类结构形式所构成发掘数据库的可达范畴, 与基于属性间关系的发掘知识库的推理范畴之间的等价关系, 这两个范畴的等价关系为定向发掘和定向搜索奠定了理论基础。但在文献[1]中建立的知识库规模庞大, 因此要把知识库中的规则用简约的形式表示, 从而建立简约知识库, 以便提高挖掘效率。

《1.1.1 简约规则》

1.1.1 简约规则

定义1 对n=θ₀a₁θ₁a₂…θ_m-1a_mθ_m, 定义n的合取度为n的表达式中出现的合取号“∧”的总数, 记为DegCon (n) ;定义n的析取度为n的表达式中出现的析取号“∨”的总数, 记为DegDis (n) 。n的度定义为n的析取度与合取度之和, 记为Deg (n) 。

定义2 规则r= (n→k) 中的知识结点n称为规则r的始知识结点, k称为r的终知识结点, 规则r的度定义为始知识结点的度与终知识结点的度之和, 记为Deg (r) 。

由于对不同的表示形式, 知识结点的度不唯一, 因此对不同形式给出的同一条规则, 规则的度也是不唯一的。

定义3 若论域的一个知识结点是一个或多个两两互不相同且两两取自不同属性的属性程度词合取的形式, 则称为简约始知识结点;若一个知识结点是一个或多个两两互不相同且两两取自不同属性的属性程度词析取的形式, 则称为简约终知识结点。所有简约始知识结点构成的集合称为简约始知识结点集, 记为N^s;所有简约终知识结点构成的集称为简约终知识结点, 记为N^t。

定义4 若规则r= (n→k) 中, n是简约始知识结点, k为简约终知识结点, 则 (n→k) 称为简约规则;由所有的简约规则构成的集合{ (n_i→k_j) | n_i∈N^s, k_j∈N^t} 称为简约规则集, 记为R^r。一条规则若能等价地分解为一条或多条简约规则, 则称该规则有简约分解。

《1.1.2 规则的简约分解定理》

1.1.2 规则的简约分解定理

引理1 规则r= (L→R) 有且仅有两种情况:或者它的始知识结点L为简约始知识结点, 或者r能等价地表示成两条规则:L₁→R和L₂→R, 并且DegCon (L_i) ≤DegCon (L) , DegDis (L_i) ≤DegDis (L) -1, i=1, 2。 (证明略)

引理2 论域X的知识库中的任意规则 (L→R) 均可以等价地分解为若干条规则 (Li→R) , i=1, 2, …, s, 并且L_i为简约始知识结点, DegCon (L_i) ≤ DegCon (L) ;类似地, (L→R) 也可以等价地分解为若干条规则 (L→R_j) , j=1, 2, …, t, 并且R_j为简约的终知识结点, DegDis (L_i) ≤DegDis (L) 。 (证明略)

由引理2很容易地就可以得出:

定理1 论域X的任意规则均有简约分解, 并且分解后的规则的简约始知识结点的度不大于分解前规则的始知识结点的合取度;分解后的规则的简约终知识结点的度不大于分解前的规则的终知识结点的析取度。 (证明略)

推论论域X的任意规则经过简约分解后, 规则的简约始知识结点的属性程度词的个数不大于分解前规则的始知识结点的合取度加1, 从而它也不大于分解前规则的始知识结点中属性程度词的个数;分解后规则的简约终结点的属性程度词的个数不大于分解前规则的终知识结点的析取度加1, 从而它也不大于分解前规则的终知识结点中属性程度词的个数。

定理2 假设α, p, I₁以及B的意义分别由文 (Ⅰ) 的定理11给出, v₁是I₁的势。当α<p (1-B) /v₁时, 若知识库中的一条规则r能等价地分解成若干条简约规则r₁, r₂, …, r_k, 则随着对应的数据子类结构库中元组数目的增加, 相应的可达关系F_H (r) 能等价地分解成可达关系F_H (r₁) , F_H (r₂) , …, F_H (r_k) 的概率趋于1;反之亦然。 (证明略)

定义5 论域X的简约始知识结点集、简约终知识结点集以及简约规则集共同构成X的简约知识库。

《1.1.3 恒真规则与恒假规则》

1.1.3 恒真规则与恒假规则

定理3 若某一条简约规则中的始知识结点和终知识结点中出现属于相同属性的相同属性程度词, 则这条规则是恒真规则;若某一规则的始知识结点和终知识结点中出现属于相同属性的不同属性程度词, 则这一条规则等价于另一条简约规则, 该规则的始知识结点同于原来规则的始知识结点;而终知识结点是把原来的终知识结点中去掉相应属性的属性程度词。 (证明略)

定理4 假设有简约规则 (L→R) , 若属性程度词a与L中的任何属性程度词均取自不同的属性, 那么有简约规则 (a∧L→R) ;若属性程度词b与R中的任何属性程度词均不相同, 则有简约规则 (L→b∨R) 。 (证明略)

定理3和定理4可以发现一些无须通过数据发掘就可以得到的假设规则, 通过评价后就可入库, 这将在一定程度上减小数据发掘算法的复杂度。

《1.2简约知识库的结构》

1.2简约知识库的结构

《1.2.1 逻辑结构》

1.2.1 逻辑结构

在双库协同机制中, 知识库的逻辑结构是根据推理范畴的结构决定的。由于范畴是由对象集及对象间的态射集决定的, 故知识库如图1所示的结构。图1中的点表示知识结点, 有向弧线表示知识结点之间存在推理关系。如果有推理关系, 则有向弧线存在, 如果没有推理关系, 则有向弧线不存在。但是, 由于这样的知识库的知识结点数目庞大, 并且推理弧线的数目是知识结点数目的方幂的形式, 所以直接用这种方式建立知识库在具体实现上较为复杂。

《图1》

图1 知识库结构示意图

Fig.1 Knowledge base structure sketch map

《1.2.2 软件实现结构》

1.2.2 软件实现结构

在规定了简约始知识结点和简约终知识结点后, 简约知识库可视为一个二维数组 (或二维表) , 它的第一维是简约始知识结点;第二维是简约终知识结点;二维数组的每一个元素包含相应规则的信息。简约知识库的结构如表1所示。其中, 二维数组R[1:m][1:n]的每一个元素含有与该简约规则有关的信息。其中一个元素Rule[i, j]是一个数据结构, 这个数据结构至少包含如下几方面的信息。

表1 简约知识库的结构

Table 1 The structure of reduced knowledge base

《图2》

1) 该规则有无意义, 无意义的规则包括恒成立的规则、恒不成立的规则和冗余的规则。

2) 是否有领域基础知识能分解成这条规则。

3) 表示对这条规则是否已进行了数据发掘。

4) 若这条规则分别从基础知识和数据发掘中获得, 它们之间有无相容性?

5) 可信度;支持度;规则强度。

由于二维数组只是在程序运行中出现, 而不能存储, 所以我们要把知识库的信息存储到类关系数据库中去。类关系数据库中的一条记录便是一条规则, 如表2所示。

表2 存放知识库规则的类关系数据库中一条记录的形式

Table 2 A record in similar relational database which store the rule of knowledge base

《图3》

《1.2.3 规则的序在知识结点集中, 要规定知识结点的序。首先, 对于始知识结点:》

1.2.3 规则的序在知识结点集中, 要规定知识结点的序。首先, 对于始知识结点:

1) 用属性程度词的数目作为始知识结点的第一序。由于在简约始知识结点中, 每一个属性中至多出现一个属性程度词, 所以可以用知识结点中属性的数目作为第一序。

2) 对属性程度词个数相同的始知识结点, 用属性的字典序作为知识结点的第二序。

3) 对属性程度词的数目相同并且属性的字典序相同的始知识结点, 用同一属性中属性程度词的字典序作为始知识结点的第三序。

其次, 对于终知识结点:

1) 用属性程度词的数目作为第一序。

2) 用全体属性程度词的字典序作为第二序。

《1.3简约知识库的初始化和基础知识入库》

1.3简约知识库的初始化和基础知识入库

《1.3.1 初始化》

1.3.1 初始化

1) 恒成立的规则:

a. 始知识结点中存在着某个属性程度词包含在终知识结点中;

b. 简约终知识结点中包含了某个属性所有的属性程度词。

2) 恒不成立的规则:

a. 终知识结点只有一个属性程度词, 并且始知识结点中包含一个和它属于同一属性的属性程度词;

b. 终知识结点的属性程度词来自于同一个属性, 并且始知识结点中存在一个属性程度词来自于这个属性且与终知识结点中的属性程度词均不相同。

3) 出现冗余:

a. 有规则 (m→k) 和规则 (n→k) , 但m的属性程度词全部包含在n中。这时, 规则 (n→k) 便是冗余规则, 可以去掉;

b. 有规则 (k→m) 和规则 (k→n) , 但n中包含了m的所有属性程度词。这时, 规则 (k→m) 是冗余的, 可以去掉。

《1.3.2 基础知识入库具体分为3个步骤:》

1.3.2 基础知识入库具体分为3个步骤:

1) 基础规则进行简约分解;

2) 查找分解后的简约规则在简约知识库中的位置;

3) 对查到的位置上有关基础规则的信息加以调整。

《2 构建供挖掘的数据子类结构库》

2 构建供挖掘的数据子类结构库

《2.1产生数据子类结构集及其元素间的关系》

2.1产生数据子类结构集及其元素间的关系

定义6 称由单个属性程度词构成的知识结点为素知识结点;素知识结点对应的数据子类结构称为数据子类素结构。

产生所有的数据子类素结构。假设某一个素知识结点n仅含的一个属性程度词A_ij对应的数值子域D_ij是一个半开区间[lower, upper) , 则可以用SQL语句产生知识结点n对应的数据子类结构。

产生了数据子类素结构后, 就可以繁衍出其他所有的简约知识结点对应的数据子类结构。可以产生两个数据子类结构的并交和一个数据子类结构的补。另外, 数据子类结构之间有可达性关系 (参见文献[1]的定义12) 。可达关系的得出必须计算两个数据子类结构之间的可信度, 而可信度的得出又必须首先产生两个数据子类结构的交, 同时得到交中元素的数目。

《2.2数据子类结构库的更新和维护》

2.2数据子类结构库的更新和维护

数据子类结构库是直接由关系数据库导出的。关系数据库的更新就要求数据子类结构库的更新。假设在关系数据库中追加了一条新的记录u, u的序号 NO必须添加到与u有关的数据子类结构中去。

首先, u与每一个属性有关, 而且只与每一个属性的其中一个属性程度词有关。对于某一属性X[i], 如果a (u) 属于第j个属性程度词A[i][j]对应的数值子域, 则把A[i][j]记录下来, 于是可以得到一个一维整数数组Change [s], 记录了所有与新元组有关系的属性程度词。通过这个属性程度词, 可以查找所有与这个新元组有关的数据子类素结构, 而在其中末尾的位置添加这个元组。

《3 实现双库协同机制的2个协调器》

3 实现双库协同机制的2个协调器

《3.1启发协调算法与启发型协调器》

3.1启发协调算法与启发型协调器

启发型协调器的主要目的是为系统的聚焦提供另一个途径。在经典KDD进程中, 系统的聚焦通常是由用户提供感兴趣方向, KDD沿此方向进行挖掘。但如果仅沿此方向进行, 大量数据中的潜在的、也许会对用户有用的信息往往被忽略。为帮助KDD尽可能多的搜索到对用户有用的信息, 以弥补用户或领域专家自身的局限性, 提高机器的认知自主性, 构造了启发型协调器。

当基础知识入库之后, 简约知识库中始知识结点到终知识结点的推理弧线部分地建立起来, 但对于许多的其他未建立的推理弧线, 不能只靠专家的经验和感兴趣度对它们进行发掘, 而应该建立一种搜索策略, 让机器自身进行搜索知识的短缺, 搜索的顺序 (即定向挖掘的顺序) 应该按照待挖掘规则的规则强度之大小 (见3.2节) 依序进行。

启发型协调器是通过启发协调算法来实现的, 算法的奠基是在文献[1]中讨论的等价定理与结构对应定理;算法的流程图见图2。

《3.2对规则强度的度量方法》

3.2对规则强度的度量方法

《3.2.1 规则强度》

3.2.1 规则强度

定义7 假设论域X的知识库中的一个知识结点n对应的数据子类结构〈n, R (n) 〉中所含元组的数目为S (n) , 数据库中所含元组的总数为S (R) , 则对于一条规则r= (n→k) ;称比值S (n) /S (R) 为规则r的前支持度, 记为S_f (r) ;称比值S (k) /S (R) 为规则r的后支持度, 记为S_b (R) ;称比值S (n∧k) /S (n) 为规则r的可信度, 记为C (r) 。可信度与后支持度的比称为熵比, 记为γ (r) 。

《图4》

图2 启发协调算法流程图

Fig.2 Heuristic coordinator algorithm flow chart

定义8 对于给定论域X, 所谓规则强度函数是指从X的规则集R到非负实数集[0, +∞) 的一个映射

$Γ : R \to [0, + \infty),$ $Γ : R \to [0, + \infty),$

这个映射具体为自变量S_f (r) 和γ (r) 到[0, +∞) 的一个二元函数

$Γ : [0, + \infty) \times [0, + \infty) \to [0, + \infty),$ $Γ : [0, + \infty) \times [0, + \infty) \to [0, + \infty),$

使得,

1) Γ (S_f, 1) = 0;

2) Γ (S_f, 0) = Γ (S_f, +∞) = sup_γΓ (S_f, γ) ;

3) γ的函数Γ (S_f, γ) 在[0, 1) 上单调减, 并且当S_f≠0时, 为严格单调减;γ的函数Γ (S_f, γ) 在[1, +∞) 上单调增, 并且当S_f≠0时, 为严格单调增。

4) S_f的函数Γ (S_f, γ) 在[0, 1]上为单调增函数, 并且当γ≠1时为严格单调增函数;

任何一个满足定义8的要求的函数都可以作为规则强度函数, 但应该选择一个表达和计算简单、光滑性比较好的函数, 例如:

$Γ (S_{f}, γ) = S_{f} R (γ, 0) = S_{f} γ e^{- γ^{2} / ? 2} ‚ (1)$ $Γ (S_{f}, γ) = S_{f} R (γ, 0) = S_{f} γ e^{- γ^{2} / ? 2} ‚ (1)$

其中R (γ, 0) 为瑞利分布函数。

《3.2.2 特殊情况的讨论》

3.2.2 特殊情况的讨论

定义规则强度函数有重要的意义, 这不但在规则提供给用户时给每条规则分配了明确的优先级, 而且在数值子域的划分中具有重要的量化参考意义。

在给出定义8时, 隐含了一个假设:后支持度不为0。但事实上, 有些规则的后支持度是0。一旦这样的情况出现, 就不能直接用定义8定义的规则强度函数。对此可以采取三种方案:

第一种方案基于信息扩散的假设对于给定的规则r= (n→k) , 如果S (k) =0, 则必有S (n∧k) =0, 从而S_f (r) 和C (r) 均为0。于是熵比γ (r) = C (r) /S_f (r) 为“0/0”型。因此, 应该把其他空间中样本所含的信息扩散到这两个空间范围d=ψ (f^-1 (k) ) 和e=ψ (f^-1 (n∧k) ) 中去。为此建立如下的s维欧几里德空间 (-∞, +∞) _s上的抛物型偏微分方程:

《图5》

其中:u (x₁, x₂, …, x_s, t) 是温度函数 (在这里是信息强度函数) , Δu为s维拉普拉斯算子, a²=k/cρ, f=f₀/c, k为热传导常数, c为比热常数, ρ为物质密度, f为热源 (在这里是信息源) 函数f (x₁, x₂, …, x_s) 。

在确定了初、边值条件之后, 就可以解上述偏微分方程, 并得到解u (x₁, x₂, …, x_s, t, ε) ;然后, 令t→+∞, 可以得到一个空间上的函数

《图6》

然后, 把函数u_∞ (x₁, x₂, …, x_s, ε) 在s维空间 d₁ =ψ (f^-1 (n∧k) ) , d₂ =ψ (f^-1 (n) ) , d₃ =ψ (f^-1 (R) ) , d₄=ψ (f^-1 (k) ) 上分别积分, 即

$Ι_{i} (ε) = \int_{d_{i}} u_{\infty} (x_{1}, x_{2} ‚ \dots ‚ x_{s}, ε) ‚ i = 1, 2, 3, 4 (3)$ $Ι_{i} (ε) = \int_{d_{i}} u_{\infty} (x_{1}, x_{2} ‚ \dots ‚ x_{s}, ε) ‚ i = 1, 2, 3, 4 (3)$

最后可以得出规则r= (n→k) 的强度为

$Γ (r) = \lim_{ε \to \infty} \frac{Ι_{1} (ε) \cdot Ι_{3} (ε)}{Ι_{2} (ε) \cdot Ι_{4} (ε)} 。 (4)$ $Γ (r) = \lim_{ε \to \infty} \frac{Ι_{1} (ε) \cdot Ι_{3} (ε)}{Ι_{2} (ε) \cdot Ι_{4} (ε)} 。 (4)$

第二种方案是第一种方案的简化把海量个热源转化为n个热源, 使原方程大大简化。然后, 再用与方案一类似的方法, 就可以得到规则的强度。

第三种方案是一种简单化了的方案把所有已知的规则的强度总平均, 凡遇到规则强度为“0/0"型的情况, 则规则强度一律为这个平均值乘上固定的系数。

规则强度函数从正、反两个方面说明了规则的重要性。如果规则的熵比大于1, 那么规则为正规则;反之, 如果规则的熵比小于1, 那么为反规则;当规则的熵比等于1时, 为平凡规则。

对于一个特定的规则, 首先应该考虑它的强度, 对强度大的规则保留, 而把强度小的规则去掉;然后, 查看规则的熵比, 用熵比和1的关系确定规则是正规则、反规则还是平凡规则。在启发型协调算法中, 如前述, 据待挖掘规则的强度大小排序, 依次自主地形成新聚焦以发现新知识。

《3.3中断协调算法与中断型协调器》

3.3中断协调算法与中断型协调器

中断型协调器是通过中断协调算法来实现的, 其算法流程图见图3。

《图7》

图3 中断协调算法流程图

Fig.3 Interruptive coordinator algorithm flow chat

由于中断型协调器对KDD过程的介入, 可以在对于重复性、一致性、冗余性、从属性、循环性等给予准确定义的基础上, 利用超图等理论工具, 实时地、尽早地将重复、矛盾、冗余的知识淘汰掉, 从而做到只对那些有可能成为新知识的假设进行评价, 最大限度地减少了评价工作量。在实际的专家系统中, 最终成为新知识的假设占原假设的比例是很小的 (发现新知识是困难的) , 大量假设会是重复和冗余的, 因此中断型协调器的引入将提高KDD的效率。

《4 KDD*总体结构》

4 KDD*总体结构

《4.1 KDD*的总体结构》

4.1 KDD*的总体结构

将双库协同机制融入KDD中, 形成所提出的KDD^*新系统的总体结构模型如图4所示。

《4.2KDD*的特征》

4.2KDD*的特征

KDD^*相对于KDD而言, 是KDD与双库协同机制相融合的一种知识发现的新结构, 具有以下特征:

1) KDD^*有机地沟通与融合了KDD^*新发现的知识与基础知识库中固有的知识, 使它们成为一个有机的整体;即实现了用户的先验知识与先前发现的知识可以耦合到发现的过程中。

《图8》

图4 KDD^*的总体结构模型图

Fig.4 KDD^* general structure model chart

2) 在知识发现过程中, KDD^*对于冗余性的、重复性的、不相容的信息作出了实时处理, 有效地减少了由于过程积累而造成的问题复杂性, 同时为新旧知识的融合与合成提供了先决条件;实现了知识与数据库同步进化。

3) 在数据库的数据积累过程中, 虽然知识库的结构具有一定的稳定性, 但它也是随着数据的积累而不断进化, 并且这种进化的能力是双库协同机制本身所具有的、无须领域专家干预的。

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

从认知科学的角度看, KDD^*强化并提供了知识发现的智能化程度, 提高了认知自主性 (这将是今后相当长的一阶段内保持的研究基调) , 较有效地克服领域专家的自身局限性, 实现了采用领域知识辅助初始发现的聚焦。

5) 作为KDD^*的核心技术——双库协同机制的研究, 揭示了在一定的建库原则下知识子库与数据子类结构之间的对应关系, 为实现限制性的搜索, 而减小搜索空间、提高发掘效率提供了有效的技术方法。

6) 双库协同机制与其诱导的新结构模型KDD^*对KDD主流的发展有着极大的作用。提出的关联规则与数据聚类规则的挖掘算法与目前实行的算法对比, 具有更好的可扩展性与有效性。

《5 关联规则的新挖掘算法》

5 关联规则的新挖掘算法

《5.1Apriori算法描述》

5.1Apriori算法描述

基于Apriori的大项集方法, 即使进行了优化, 仍存在一些无法克服的固有缺陷:a. 无法对稀有信息进行分析。由于大项集方法使用了参数最小支持度minsup, 所以就无法对小于minsup的事件进行分析;而如果将minsup设成一个很低的值, 那么算法的效率就成了一个很难处理的问题。只要人们仍把支持度作为最初的项集产生的主要决定因素, 要么把支持度设得足够低以使得不丢失任何有意义的规则, 或者冒丢失一些重要规则的风险。对前一种情形可能会产生组合爆炸或计算效率问题, 而后一种情形则有可能丢失从用户观点来看是有意义的规则问题。对于前一种情形, 文献[2]提出了一种不用支持度阈值的方法, 但它必须给定挖掘规则的结论, 并且只能挖掘可信度非常高 (接近1) 的规则。为了弥补后一种情形, 文献[3]提出了挖掘意外规则 (即支持度都很低而可信度很高的规则) , 但它利用了常规规则与意外规则是一规则对的性质, 故只能挖掘与常规规则相对应的意外规则, 仍然会有丢失一些重要规则的风险。b. Apriori的大项集方法需要对整个数据库进行多遍扫描, 即使候选集中只有一个元素, 也同样需要整个数据库, 即它是一种全局扫描搜索。而且它没有考虑现在知识库中是否已经有这些知识, 或已经可以从知识库中经过推理得出这些知识。c. 对于Apriori算法的第2步, 也有必要研究。该算法产生的规则是非常多的, 对L_k中任一元素, 就可能产生C $_{k}^{1}$ $_{k}^{1}$ +C $_{k}^{2}$ $_{k}^{2}$ +…+C $_{k}^{k - 1}$ $_{k}^{k - 1}$ 条规则, 它一方面增加运算时间;另一方面对成千上万条规则, 用户的评价量非常大, 甚至会无从着手;固有这些知识的入库必须考虑是否与原知识库的知识产生矛盾、冗余、循环、从属、重复等问题。

笔者提到的Maradbcm算法, 将从KDD内在机理研究入手, 从双库协同机制, 这一构建KDD过程中最重要的两个参与要素 (数据库与知识库) 本质联系的认知规律出发, 利用新的知识发现结构模型KDD^* (特别是两个协调器) , 较好地解决上述存在的若干缺陷。

《5.2Maradbcm算法的理论基础》

5.2Maradbcm算法的理论基础

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

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

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

3) 双库协同机制主要由启发型协调器和中断型协调器来实现。启发型协调器的功能是通过搜索知识库中知识结点的不关联态, 以发现知识短缺, 产生创见意象, 从而启发与激活真实数据库中相应的数据类, 以产生定向发掘进程 , 即完成了计算机自动聚焦。

中断型协调器的功能是, 从真实数据库的大量数据中经聚焦而生成规则 (知识) 之后, 使KDD进程产生“中断”, 而去搜索知识库中对应位置有无此生成规则的重复、冗余、矛盾、从属、循环等。若有, 则取消该生成规则或做相应处理后返回KDD的始端;若无, 则继续KDD进程, 即知识评价。

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

《5.3 Maradbcm算法的算法的描述》

5.3 Maradbcm算法的算法的描述

设规则强度阈值为minIntensity, 支持度阈值为minSup, 可信度阈值为minCon。限于篇幅, 下面将根据KDD^*的结构图1简要介绍所提出的新算法——Maradbcm算法:

Step1 数据预处理这里主要是用户选择真实数据库, 对于多值属性利用文献[4]进行离散化, 形成发掘数据库。

Step2 发现知识短缺为此, 首次提出了用有向超图H来表示知识库中的知识的新表示方法, 并给出了有向超图的邻接矩阵A (H) 表示, 在此基础上提出了一种计算有向超图的可达矩阵P (H) 新算法, 可达矩阵P (H) 中的0元素就是短缺的知识。

Step3 产生K₂ 设短缺知识集用K来表示, 用K_m表示规则长度为m的短缺知识集, 即K_m={r|Len (r) =m}。因为K中的元素非常多, 利用上面介绍的规则强度Intensity (r_i) 对K₂进行剪枝, 对Intensity (r_i) □ minIntensity (r_i) 的规则r_i进行聚焦。即对于短缺知识r_i:e_p→e_q (r_i∈K₂) , 必须满足:支持度sup (e_p) , sup (e_q) □minSup, 而Intensity (r_i) 中的sup (r_i) = min (sup (e_p) , sup (e_q) ) 。

Step4 m =2。

Step5 对K_m产生假设规则对K_m中的短缺知识r_i:e₁∧e₂∧…∧e_p→e_q (r_i∈K_m) , 进行定向挖掘, 即对数据表table1, table2, …, table p, table q进行挖掘, 计算Con (r_i) 和Intensity (r_i) , 如果Con (r_i) minCon且Intensity (r_i) □minIntensity (r_i) , 则转Step6;否则, 删除该规则。

Step6 对规则r_i应用中断型协调器进行处理搜索基础知识库中对应位置有无此生成规则的重复、冗余、矛盾、从属、循环等。若有, 则取消该生成规则或做相应处理, 转Step8;若无, 则转Step7。

Step7 对规则r_i进行评价若评价通过, 则入库, 并对有向超图对应可达矩阵进行计算, 对K_m, 进行调整;若评价没有通过, 则删除该规则。

Step8 K_m是否结束若结束, 转Step9;若没有结束, 转Step5进行下一条规则的处理。

Step9 m=m+1, 若K_m=Φ, 转Step10;否则, 转Step5。

Step10 显示新产生的规则。

Step11 结束。

对于Maradbcm算法, 其中有些步骤的执行次序是可以调整的。

《5.4Maradbcm算法的优越性》

5.4Maradbcm算法的优越性

综上所述, Maradbcm算法与Apriori算法的主要共同点是二者在本质上都是基于统计方法的;二者的主要区别在于以下5个方面:

1) 基于的学术思想不同 Maradbcm算法是基于内在机理研究, 具体是基于知识短缺 (利用有向超图) 进行定向挖掘;而Apriori算法是基于组合论的数据库全局搜索。

2) 基本流程 (或基于的模型) 不同Maradbcm算法的流程见KDD*结构模型图, 它是短缺知识一条一条地挖掘;而Apriori算法是整体性一并挖掘。

3) 基础不同 Maradbcm算法是基于规则强度, 它考虑了主观和客观两个方面, 即考虑了用户的聚焦 (感兴趣度) , 并涵盖了Apriori算法的支持度阈值。

4) 发现知识的量不同 Maradbcm算法考虑的知识库, 从而能真正发现新颖的、用户感兴趣的知识, 这正是符合了KDD定义;而Apriori算法是把满足条件的规则全部挖掘出来;另外, Maradbcm算法克服了Apriori算法的两大缺点:遗漏重要的规则和数据库的全局搜索。

5) Maradbcm算法可融入KDD中形成新的开放型的结构模型——KDD^*, 整个算法实现的运算背景是KDD^*结构;而Apriori算法是原有的封闭系统KDD。

《5.5实例运行》

5.5实例运行

为了具有比较性, 利用文献[5]所提供的蘑菇数据库 (mushroom database) 进行实验, 该数据库有8124条纪录, 记录了蘑菇的帽子形状、帽子的颜色、颈的形状、颈的颜色、气味、生存环境、是否有毒等23种属性, 每种属性有2～12个枚举值。其中的属性stalk-root有2480个样本缺省, 另外veil-type属性有两个枚举值partial和universal, 而所有样本值均为partial, 故对这两个属性不予考虑。我们只对蘑菇是否有毒感兴趣, 因此规则的后件均为是否有毒这一属性 (即包括‘edible’、‘可以食用’和‘poisonous’、‘有毒’) 。该算法是所采用的编程语言为Delphi 5.0, 数据库系统是微软的SQL-Server 7.0, 采用了Client-Server结构, 计算机CPU为Intel的766, 内存为256 MB。

首先, 运行Apriori算法, 设置阈值支持度minSup=0.4, 可信度minCon=0.6, 产生19条规则。其次, 运行意外规则的挖掘算法。设置阈值支持度minSup=0.14, 可信度minCon=0.8, 另外产生9条与上述常规规则相对应的意外规则。最后, 以上述的28条规则作为基础知识库, 运行启发型协调器, 为了可比性, 设置阈值支持度minSup=0.14, 可信度minCon=0.6, 规则强度minIntensity=0.45。另外产生45条规则, 如图5所示 (仅显示了其中的12条规则) 。

《图9》

图5 Maradbcm算法产生的新规则

Fig.5 Maradbcm algorithm create new rule

《6 挖掘聚类规则的新算法》

6 挖掘聚类规则的新算法

《6.1评价函数》

6.1评价函数

对知识库的某一个特定的级别, 假设所有的规则框架集 (因为还未知是正规则、反规则还是平凡规则, 只知道它们的始知识结点和终知识结点) R中含有T条规则。定义数值域划分的评价函数为所有规则强度的平均值。即对于给定的T条规则框架, 数值域划分的评价函数是一个从划分集P到非负实数集的一个映射:

《图10》

使得

《图11》

也就是说, 对每一个划分p, 都有唯一的非负实数来评价这个划分, 式 (5) 是评价一种划分优劣的依据。

《6.2编码、交叉和突变策略》

6.2编码、交叉和突变策略

采用遗传算法, 既保证了分解离散块时的小粒度, 又保证了求解最优解的可行性。自然地, 把数值域划分的评价函数式 (5) 作为遗传算法中的适应度函数。下面着重解决遗传算法中的编码问题。

《6.2.1 编码》

6.2.1 编码

为了避免边界点选取不合理的情况, 采用一种适当限定的方法。即先给每一个分界点确定一个适当的范围, 使这一个分界点只能在这一个范围内选取。如数值域的两个边界点固定在两端, 而中间的4个边界点可以在各自的范围内自由选取。

如果数值域是一个连续的区间[a, b], 则可以把它等分成2^m块, 然后给每一块一个二进制编码, 这一块的二进制编码是一个m位的, 并且块的集合与m位二进制数的集合形成了一一对应。数与块的对应关系是通常的二进制与十进制的对应关系。

如果数值域本身是离散的, 它只有M个离散点, 则取m为ent lb M (向大的方向取整数) 。但这样生成的2^m个二进制编码与M个离散点可能是非一一对应的关系。一个二进制数只有一个离散点与之对应;但一个离散点可以有一个或两个二进制数与它对应。建立对应的策略是:建立一个长度为2^m个单位小区间的区间, 把M个离散点均匀分布在区间上。当离散点向二进制代码映射时, 如果离散点在某一个小区间之中, 则把这个离散点对应于这个小区间;如果离散点在两个小区间的边界上, 则把离散点对应于左边的小区间。当二进制代码 (小区间) 向离散点映射时, 选择与小区间的中心最近的离散点;如果两个离散点同时与小区间中心位置距离最近, 则选择左边的离散点。

于是得到了一条二进制数形成的编码, 共分为s段, 每一段上是对应属性数值域划分所对应的二进制代码。于是, 对数值域的每一个划分映射到唯一一条二进制编码链;然而几条二进制编码链可能会映射到同一个数值域的划分, 但这种情况出现时, 这几条二进制编码链在各个段上的数值是很相近的 (最多相差1) 。

《6.2.2 交叉》

6.2.2 交叉

假设二进制编码链 (基因链) 共有G位。对于给定的两个基因g₁和g₂, 其交叉方法:

1) 在1到G之间 (包括1和G本身) 随机地取两个数b和e, 若b>1, 则b、e交换;

2) 把基因g₁中b到e的位 (包括b和e本身) 平行地与基因g₂中b到e的位交换。

3) 基因g₁成为下一代g₁′, 基因g₂成为下一代g₂。

《6.2.3 突变对于给定的基因g, 它产生突变的方法:》

6.2.3 突变对于给定的基因g, 它产生突变的方法:

1) 在1到G之间 (包括1和G) 随机地选取一个整数b;

2) 把第b位的编码取反 (0变1, 1变0) ;

3) 得到的新基因为下一代g′。

《6.3基于双库协同机制的数值域划分算法 (数据聚类算法) 的描述》

6.3基于双库协同机制的数值域划分算法 (数据聚类算法) 的描述

1) 对每一个属性确定划分的边界点的可变范围;

2) 对每一个属性的每一个范围分割成小的区间, 并确定与它们对应的二进制编码长度;

3) 随机产生7N条基因链 (N一般取40左右) ;

4) 把所得7N条基因链中每一条基因链分别映射到一种划分, 并分别求出划分的评价函数值, 把函数值从大到小排序, 淘汰评价函数值最小的3N个基因链;

5) 找出评价函数最大的N条基因链, 作为下一代的一部分;

6) 在未被淘汰的4N基因链中随机地挑选6N条基因链, 并以95 %的概率进行随机地交叉配对, 以5 %的概率进行基因突变, 得到下一代;

7) 重复从第4开始执行, 直到最优基因的评价函数值前后相差不超过给定误差值ε, 记录下最优基因链;

8) 对最优基因链用梯度法再进行优化, 得到最终基因链;

9) 把最终基因链映射成一种划分, 便得到最优 (或次优) 划分。

使用遗传算法是因为它具有全局搜索能力和极强的鲁棒性, 一般不会陷入局部最优。但在若干代遗传、交叉、突变之后, 它很可能在一个最优解的周围回旋而不能达到这个最优解;因此, 在算法的最后用梯度下降法使它能更好地接近最优解。

《7 结论》

7 结论

上述成果充分证实:知识发现系统内在机理之一——双库协同机制的研究, 对KDD的主流发展起到了重要的推动作用。主要表现为:

1) 阐明了作为KDD过程中的两个组成要素, (知识库和数据库) 之间的关系构造了新的结构模型KDD^*; 从而大大缩减了KDD的搜索与挖掘空间, 使传统的KDD运行机制向着开放和智能化的方向拓展。

2) 产生了一种知识库的实时维护机制。随着新知识的随时入库, 知识库的重复、冗余、矛盾、从属、循环等随时进行检查。

3) 充分体现了知识发现系统的认知自主性——KDD 的核心概念与研究基调, 提高了发现空间的自动化程度。

4) 通过这种机制的研究, 可以对当前KDD着重于研究具有高效的可扩展性的挖掘算法这一主线, 起着本质的强劲的拉动作用;可以派生出超越现有流行算法的新算法, 如:Maradbcm算法与数值域划分 (数据聚类) 算法等。

5) 在哲学方面带来了许多新的思考, 同时也反作用于KDD领域的研究。

展示更多