基于广义归纳逻辑因果模型的知识发现与算法实现

D0I:10.13374/i.issn1001053x.2003.041.022 第25卷第4期 北京科技大学学报 VoL25 No.4 2003年8月 Journal of University of Science and Technology Beijing Ag2003 基于广义归纳逻辑因果模型的 知识发现与算法实现 张德政》石阳)邓一)杨炳儒) 1)北京科技大学信息工程学院，北京1000832)鞍山科技大学计算机系，鞍山114002 摘要以语言场、广义细胞自动机和广义归纳逻辑因果模型为理论依据，分析了广义因果 联系类知识的发现机理，给出了因果联系类知识发现的实现算法，该算法为解决具有随机不 确定和模糊不确定性特征的因果联系类知识的发现提供了行之有效的方法，通过算法的运 行实例，验证和说明了算法的正确性和有效性， 关键词广义逻辑归纳因果模型；广义因果联系；数据挖掘：知识发现 分类号TP18 随着数据挖掘(Data Mining,DM)和知识发现 数据挖掘或知识发现方法进行分析. (Knowledge Discovery in Database,KDD)理论与实 广义归纳逻辑因果模型是构建在语言场与 现技术研究及应用的不断深入，已经建立了多种 语言值结构和广义细胞自动机理论基础上的完 不同类型的知识发现算法.然而，在科学与工 备归纳推理机制，通过不确定性广义归纳因果模 程领域广泛存在的、具有随机性、模糊不确定性、 型的构建，形成了包含大量随机和模糊不确定性 非线性时变性和动态特征的广义因果联系类知 特征的完备基础知识库.在知识发现的过程中， 识的发现，迄今还没有行之有效的发现理论和算 这些知识作为知识发现的元知识具有普遍性，它 法，这类知识是反映客观世界因果性和因果联系 们构成了广义因果联系类知识发现的模板，可 的深层次知识.它们对于探索客观事物间的必然 指导广义因果关联规则的发现.这样可以发现那 联系，确定其发展变化的内在机理，把握事物的 些用常规的关联规则获取方法所无法的得到 本质有重要意义，从数据库中获取这类知识，无 的低频率高强度关联规则， 论对于广泛意义下从事务数据库中获取知识还 是对于从科学数据库中发现必然性联系的规则， 1广义归纳逻辑因果模型 都是目前所亟待解决的问题. 1.1语言场与语言值结构 广义因果联系类知识是指事物之间存在的 自然语言易于被理解和接受，并且可表达十 一种潜在的因果必然性联系，是一类高关联强度 分复杂、具有抽象性和不确定性特征的知识.自 的知识.它以穆勒关于因果关系定义的普遍性原 然语言可以很好地表示有关事物状态、变态以及 理、因果共变原理和先因后果原理为特征，事物 反映因果性和因果联系的知识.利用语言场与语 的状态以及状态的变化反映出事物之间以及自 言值结构，本文建立了描述状态和变态的统一构 身属性之间所存在的广义因果联系，决定事物之 架，并提供了字符型属性值量化的模板 间必然性联系和因果性关系.这类知识蕴含在现 定义1C=<D,I,N,≤心，若满足下列条件，则 实世界的复杂联系之中，在一般情况下这类知识 称C为语言场：(I)D为R上数的集合或其上闭区 所反映的是复杂非线性关系，具有随机不确定、 间的集合，D为其对应开集：(2)W≠)为语言值的 模糊不确定和非线性时变等性质，难以用常规的 有限集：(3)≤w为N上的全序关系；(4)：N一D为标 收稿日期2002-11-11张德政男，39岁，刮教授，博士 准值映射，满足保序性，即：廿n,nz∈Nn≠Ah≤w *国家自然科学基金重点项目QNo.69835001)

第 卷 第 期 年 月 北 京 科 技 大 学 学 报 几 一 基于广义归纳逻辑 因果模型 的 知识发现与算法实现 张德 政 ” 石 阳 ， 邓 一 ” 杨 炳 儒 ” 北京科技大学信 息 工 程学 院 ， 北京 鞍 山科技大 学计 算机 系 ， 鞍 山 摘 要 以语 言场 、 广义 细 胞 自动机和 广义 归纳逻辑因果模型 为理 论依据 ， 分析 了广义 因 果 联 系类 知 识 的发现 机理 ， 给 出 了 因 果 联 系类 知 识 发 现 的 实现算法 该 算法 为解 决具 有 随机 不 确 定和 模糊不 确 定性特征 的 因果 联系类知 识 的发现提供 了行 之有 效 的方法 通 过算法 的运 行 实例 ， 验证和 说 明 了算法 的正 确性和 有 效 性 关健词 广 义 逻辑 归纳 因 果 模型 广 义 因果 联 系 数据挖 掘 知 识 发现 分类号 仔 随着数据 挖 掘 ， 和 知 识 发现 五 鲍 ， 理 论 与 实 现 技术研 究及 应 用 的不 断深 入 ， 已经 建立 了多种 不 同类 型 的知 识 发 现 算法 【 一 然 而 ， 在 科 学 与 工 程领 域广泛存在 的 、 具有 随机性 、 模 糊不确 定性 、 非 线 性 时变 性 和 动 态特 征 的广 义 因果 联 系类 知 识 的发现 ， 迄今还 没 有行 之有 效 的发现 理论 和 算 法 这类 知 识 是 反 映客观 世 界 因果性和 因果 联系 的深层 次知 识 它们 对 于探 索客 观 事物 间 的必 然 联 系 ， 确 定其 发展 变化 的 内在 机理 ， 把握 事物 的 本质 有 重 要 意 义 从 数据 库 中获取 这 类 知 识 ， 无 论 对 于 广 泛 意 义 下 从 事 务 数 据 库 中获取 知 识 还 是对 于从 科 学数据 库 中发现 必 然 性 联系 的规 则 ， 都 是 目前所 鱼 待解 决 的 问题 广 义 因 果 联 系 类 知 识 是 指 事 物 之 间存 在 的 一种潜在 的 因果必 然 性联 系 ， 是一类高关联 强度 的知 识 它 以穆勒 关于 因果 关系 定义 的普遍 性 原 理 、 因果 共变 原理和 先 因后 果 原理 为特 征’ 事物 的状 态 以及 状 态 的变 化 反 映 出事 物 之 间 以及 自 身属 性之 间所存在 的广义 因果联系 ， 决定 事物之 间必 然 性联 系和 因果性 关系 这类 知 识 蕴 含在现 实世 界 的复 杂联 系之 中 ， 在一般 情 况 下 这类 知识 所 反 映 的是 复 杂 非 线 性 关 系 ， 具 有 随机 不 确 定 、 模 糊不确 定和 非线 性 时变等性质 ， 难 以用 常规 的 收稿 日期 一 张德政 男 ， 岁 ， 副教授 ， 博士 国家 自然科学基金重 点项 目困。 数据挖 掘或 知 识 发现 方 法进 行 分 析 广 义 归 纳 逻 辑 因果 模 型 是 构 建 在语 言 场 与 语 言值 结构 和 广 义 细 胞 自动 机 理 论 基 础 上 的完 备 归纳 推 理机制 通 过 不确 定性广 义 归纳 因果模 型 的构建 ， 形 成 了包 含 大量 随机 和模 糊 不 确 定性 特 征 的完 备基础 知 识 库 在 知 识 发现 的过 程 中 ， 这 些 知 识 作 为知 识 发现 的元 知 识 具 有 普遍 性 ， 它 们 构成 了广义 因果 联系类 知 识 发现 的模板， ， 可 指 导广 义 因果 关联规 则 的发现 这样可 以发现那 些 用 常规 的关联 规 则 获取 方 法 口， 所 无 法 的得 到 的低 频率 高强度 关联 规 则 广 义 归纳 逻 辑 因 果 模 型 语 言场 与语 言值 结 构 自然 语 言 易于 被 理 解 和 接 受 ， 并且 可 表达 十 分 复 杂 、 具 有 抽 象 性和 不确 定性特 征 的知 识 自 然 语 言可 以很 好 地表 示 有关事物状态 、 变态 以及 反 映 因果性和 因果 联系 的知 识 利用 语 言场 与语 言值 结构 ， 本文 建立 了描述状 态和 变态 的统 一构 架 ， 并提 供 了字 符型属 性值 量 化 的模 板‘认 定 义 ， ， ， ‘ 户 ， 若 满足 下 列 条件 ， 则 称 为语 言场 为 上 数 的集 合 或 其 上 闭 区 间 的集 合 ， 为其对 应 开集 羊 为语 言值 的 有 限集 ‘ 二 为 上 的全 序 关 系 万一 为标 准值 映射 ，满 足保 序 性 ， 即 ，， 任 羊 八 ，簇 ， DOI ：10．13374／j ．issn1001－053x．2003．04．022

378 北京科技大学学报 2003年第4期 m→(n)s(n2),≤为偏序关系) 定义6=<T,一称为广义细胞自动机，因果 定义2对于语言场C=<D,I,N,≤>，称F=<D, 必然性规律pNe),)一p(e,)要满足如下条件的 W,>为的语言值结构，如果C满足以上定义，K (1)(3),并且→满足条件(4)： 为自然数：且形：N→[0,1满足： (1)有限变化原理一自然界的因果必然性 廿n,n2∈Wn1≤wn2-n)≤Wnz), 规律是构筑在适于描述任何时空区域的有限集 廿n,n2∈Nn,≠h一Wn)≠叭n2). 合基础上，每个时空区域都可作为这些性质的描 其中，≤为R上的字典序，即(a,,d)≤(b',…,b) 述对象. 当且仅当存在h,使得当0sh时，d==b,d≤b. (2)因果存在性原理—规律支配某时空区 定义3设C,C2为两个语言场，称C1是C2的 域，则对自动机大部分区域也适用（适于似决定 扩张，若存在1-1映射f:D,→D2,gN一N2,使得： 论的细胞自动机)， (1f单调：(2)（廿n,∈N,)fU(n)=gU2(m)):其中， (3)因果一致性原理一该规律不仅适于某 C1=<D1,I1,N1,≤w,>,C2=<D2,I2,NW2,≤w> 时空区域，而且适于整个细胞自动机，即整个可 定义4设C=<D,I,N,≤心>的语言值结构为F= 达性时空区域（适于决定论的细胞自动机） <C,W,K>,F2=<C,W,K>,若存在1-1映射h: (4)因果状（变）态原理一在连续、渐变的因 [0,1]K一[0,1]满足： 果联系过程中，对于任意样本空间而言，细胞e (1)h在字典序下严格单调： 在时刻'的所有可能的状（变）态（作为结果）必然 (2)(n∈NW(n)=W(n): 是由前一时刻t细胞e的邻域N(e)取“正”与“反” (3)(3c∈R(tn,n'∈W(dis(w(n),W(n)= 两类状态作为原因所导致的 disa(W2(n),Wa(n)). 定义7广义归纳逻辑因果模型是满足下列 其中，dis:[0,1]×[0,1]K-[0,1],dis2:[0,1]K×[0,1]→ 条件的语义结构A=<S,I>: [0,1],则称F与F为(dis,dis2)同构. (1)S={S,S,…,Sw,S为受因果必然性规律 定理1设C1,C2为两个语言场，C是C2的扩张 与·相关原理所支配的可能因果世界：S为现实 的充要条件是C与C2是同型语言场（即W,W2). 的因果世界；S={V,'2,…},V表示组成S的不同 定理2设F为C的语言值结构，则F与F的double 历史，每个历史含有不同的时空段，每个时空段 扩展在加权Hamming距离下同构， 里潜含着各类因果联系，而因与果又对应着各自 由语言场与语言值结构的定义和理论知，在 的语言场与语言值结构， 同构意义下，同型语言场中语言值的描述可不加 (2)T是广义因果细胞自动机，每个可能的因 区分.在ds同构意义下，语言值可构建在不同维 果世界都用相应的广义因果细胞自动机来描述， 空间上.当语言值集合R为[0,1]时，根据语言场和 语言值结构，状（变）态的定量描述可简化， 12广义细胞自动机和广义归纳逻辑因果模型 2标准样本空间中广义归纳逻辑 基于广义归纳逻辑因果模型的知识发现是 模型知识库的构造 以广义细胞自动机为理论基础构建不确定广义 归纳逻辑因果模型，并形成广义因果关联规则发 在广义归纳逻辑因果模型中，设导致结果S 现的基础知识库-) 的原因有A,B,C,…、当用广义因果细胞自动机 定义5在离散化的欧几里德时空中，在现实 去描述标准样本空间在时刻t的因果间的状（变） 空间向语言场转化的的条件下称I=<U,T,E,> 态联系时，首先得到了因果各种状（变）态的语言 为广义细胞自动机，其中，T是时间序列，其元素 值描述及其对应的离散型的向量表示.A在t时 t称为时刻：E是细胞集合，其元素e称为细胞（即 刻的状（变）态标准向量为AP-(a,b,c,d,e,(i= 空间区域)：={φ1，中，…}是左复合映射集合，元 1,2,3,4,5),结果S在'时状（变）态标准向量为：S9= 素中=Wo中，即定义中的赋态映射中确定细胞e在 pn9…rr0=1,2,3,4,5). 时刻t'的状态，并将状态用相应语言值描述，然后 定义8在标准样本空间中，设AP与59分别 再经语言值结构中的映射W确定离散型表示状 表示原因A在1时刻状（变）态与结果S在时刻状 态的K维向量. (变)态的标准向量，则因果状态必然性规律：

， 北 京 科 技 大 学 学 报 年 第 期 一 ‘ ， ‘ 为偏 序 关 系 定 义 对 于 语 言 场 介 ‘ ， ， ，‘ 户 ， 称 ‘ ， 矶 犬 为 的语 言值 结 构 ， 如 果 满 足 以上 定 义 ， 为 自然 数 且 然 万神 【 ， 满 足 ，伪任 ， ‘ 边 ， 叫 ‘ 叫跳 ， ， 任 ，羊 一 叫 袭 叫 其 中 ， ‘ 为 上 的字 典 序 ， 即 ，，… ，矿 ‘ ，… ， 当且 仅 当存 在 ， 使 得 当 习 时 ， 歹 ， ‘ 扩 定 义 设 ，， 为 两 个 语 言场 ， 称 ， 是 的 扩 张 ， 若 存 在 一 映射厂 ，一几 ， 凡 一从 ， 使 得 丫单 调 任抓 拭 喇石 其 中 ， ，五 ，凡 ， ， ， 长 ，几 ，从 ， 三、 定 义 设 介 ， ，， ‘ 户 的语 言值 结构 为名 ，， 琳 ， 凡 ， 凡 ， 爪 ，凡 ， 若 存 在 一 映 射 ， ‘ 一 〔 ， 护满 足 在 字 典序下 严 格 单 调 任劝 琳 ” 矶 日 任 ， ’任的 ， 爪 ， 爪 矶 ， 矶 今 其 中 ， ， 【 ， 沪 ， 护 【 ， ， ， 势 【 ， 势一 ， ， 则 称凡 与凡 为 ， 工同构 定 理 设 已 ， 为 两 个 语 言场 ， 是 已 的扩 张 的充要 条件 是 ，与 是 同型语 言场 即囚 从 定 理 设 为 的语 言值 结构 ， 则 与 的 扩 展 在 加 权 距 离 下 同构 由语 言场 与语 言值 结 构 的定 义 和 理 论 知 ， 在 同构 意义 下 ， 同型语 言场 中语 言值 的描 述 可 不 加 区分 在 一 同构 意 义 下 ， 语 言值 可 构 建在 不 同维 空 间上 当语 言值 集合 为 ， 时 ， 根据 语 言场 和 语 言值 结 构 ， 状 变 态 的定 量 描 述 可 简化 广 义 细 胞 自动 机 和 广 义 归 纳 逻 辑 因 果 模 型 基 于 广 义 归纳 逻 辑 因 果 模 型 的 知 识 发 现 是 以广 义 细 胞 自动 机 为理 论 基 础 构 建 不 确 定 广 义 归纳逻 辑 因果模型 ， 并形 成 广 义 因果 关联 规 则 发 现 的基 础 知 识 库【，，一 ，，， 定义 在 离散化 的欧几 里 德 时空 中 ， 在现 实 空 间 向语 言 场 转 化 的 的条 件 下 称耳 ，， 刀， 为 广 义 细 胞 自动 机 其 中 ， 是 时 间序 列 ， 其 元 素 称 为 时刻 是 细 胞 集 合 ， 其 元 素 称 为细 胞 即 空 间 区 域 矿 价 ，咖 ，… 是 左 复合 映射 集 合 ， 元 素或二 朴妈 ， 即定 义 中 的赋 态 映射价确 定 细胞 在 时刻扩的状态 ， 并将状态 用相 应语 言值 描述 ， 然 后 再 经 语 言值 结 构 中 的 映 射 那确 定 离 散 型 表 示 状 态 的 维 向量 定 义 厂 ‘ 刀 ， 称 为广义 细 胞 自动机 ， 因果 必 然 性 规 律 诃 州 ，一诃 ， 要 满 足 如 下 条 件 的 卜 ， 并 且 满 足 条 件 有 限变 化 原 理－ 自然 界 的 因果 必 然 性 规 律是 构 筑 在 适 于 描 述 任 何 时 空 区域 的有 限集 合 基础 上 ， 每个 时空 区 域 都可 作 为这些 性质 的描 述 对 象 因 果 存 在 性 原 理－ 规 律 支 配 某 时 空 区 域 ， 则对 自动 机 大 部分 区 域 也 适 用 适 于 似 决 定 论 的 细胞 自动 机 因果 一 致 性 原理－ 该 规 律 不 仅适 于 某 时 空 区 域 ， 而 且 适 于 整 个 细 胞 自动 机 ， 即整 个 可 达 性 时 空 区 域 适 于 决 定 论 的细 胞 自动 机 因果状 变 态 原 理－ 在连 续 、 渐变 的因 果 联 系 过 程 中 ， 对 于任 意样 本 空 间 而 言 ， 细 胞 在 时刻厂的所 有 可 能 的状 变 态 作 为结果 必 然 是 由前 一 时刻 细 胞 的邻 域 取 “ 正 ” 与 “ 反 ” 两 类 状 态 作 为 原 因所 导 致 的 定 义 广 义 归纳 逻 辑 因 果模 型 是 满足 下 列 条 件 的语 义 结 构’ 二 召 ， ， ’ 渴 ，… ，凡 ， 况为 受 因果 必 然 性 规 律 与 一 相 关 原 理 所 支 配 的可 能 因果 世 界 为现 实 的 因果 世 界 及 ，玖 ，… ， 气表示 组 成民的不 同 历 史 ， 每 个 历 史含 有 不 同 的 时 空段 ， 每 个 时空 段 里 潜含着 各类 因果 联 系 ， 而 因与果 又 对应 着各 自 的语 言场 与 语 言值 结 构 班 ’ 是 广 义 因果 细 胞 自动机 ， 每个可 能 的 因 果 世 界 都用 相 应 的广 义 因果 细胞 自动 机来描述 标 准样 本 空 间 中广 义 归 纳 逻 辑 模 型 知识 库 的构 造 在 广 义 归纳 逻 辑 因果 模 型 中 ， 设 导 致 结 果 的 原 因有月 ， ， ， · … 当用 广 义 因果 细 胞 自动机 去 描 述 标准 样 本 空 间在 时刻 的因果 间 的状 变 态 联 系 时 ， 首 先 得 到 了 因果 各 种 状 变 态 的语 言 值描 述及 其对 应 的离散型 的 向量表 示 「’ 在 时 刻 的状 变 态 标 准 向量 为川悠， ， 。 ， 动 ， ， ，， ，， ， 结果 在 厂时状 变 态标准 向量 为 酥介 仇 ， ， ，… 芍 ， ， 仃 ， ， ， ， 定 义 在 标准 样本 空 间 中 ， 设月护与酬分 别 表 示 原 因月 在 时刻 状 变 态 与 结果 在 时刻 状 变 态 的标 准 向量 ， 则 因果 状 态 必 然 性 规 律

VoL.25 No.4 张德政等：基于广义归纳逻辑因果模型的知识发现与算法实现 ·379· A,)一pS,),由带有模糊性与随机性的状态的 联系，尤其是因果扰动及响应奠定了基础 关系矩阵给出，，即 (A,)-(A,)(A)xS,C(H,E) (1) 3 知识发现算法及其实现 其中，C(H,)为归纳确认度函数，它表明证据E对 基于上述理论，提出了相应的广义因果联系 假说H即此表示因果状态的必然性规律)的支持 类知识（称之为因果关联规则）的发现算法.因果 程度。 关联规则的获取可形式化地描述为：设= 在归纳确证度函数C(H,)中证据包括两部 {,2,,i}是由m个不同属性组成的集合，对于一 分，即逻辑证据和经验证据.逻辑证据是领域及 个给定的数据库D,若属性集ASL,S二I,AnSO, 背景知识，体现在归纳分析之中，即寓于广义逻 则A和S的因果联系可用因果关联规则表示为 辑归纳因果模型的构造中，经验证据是由观测值 A→S. 或实例所确定.由于广义逻辑归纳模型构造为完 定义10因果关联规则A,→S,的支持度sup 全归纳，同时数据挖掘和知识发现所面对的是海 pot为A,与S,在数据库D中同时出现的概率，即 量数据，因而C(H,E)可以由基于确证度理论的归 support(A,→S). 纳概率函数来PH,E)表示， 定义11因果关联强度S,表示属性之间因果 定义9归纳概率函数PH,E)是经验概率 关系的强弱程度S.=support(A,一S)/support(A∧ PH,E)与逻辑概率PH,E)的线性和，即： B). P(HE)-aP(H.E.)+BP(H,E) (2) 定义12规则的可信度C℉由定义9中给出 式中，a=EWB=EMl.根据广义细胞自动 的归纳概率函数来表征， 机定义中的因果状（变）态原理，结果S在时刻'的 广义归纳因果模型及其知识库的构造为广 所有可能的状（变）态，可由下式获得： 义因果关联类知识的发现提供了框架形式表示 (pA,）-pS,1)A(@A,)→pS,tL(A)r×5H 的元知识，使得先验知识同已经发现的知识可以 [(1-A)TxS] (3) 耦合到新的知识发现过程，用于确定新的知识发 式(3)中，由(A,)所导致的p(S,)将融合了所有 现的方向和目标使得知识发现过程不再是盲目 可能的多个结果（标准向量），实现了在标准样本 进行，而是具有一定的目的性.同时规定了所获 空间中，在认知极限内的完全归纳，由式所形成 得的知识是反映因果关系的广义因果联系类知 的每一个矩阵均称为状（变）态矩阵，统记作M. 识.基于上述理论的知识发现流程见图1. 在广义归纳因果模型构造下，在可能的因果 世界中，以含有因果联系信息的状（变）态矩阵M 状（变）态变量的标准化 为背景（大前提），原因A在某个状（变）态下所能导 模板构造 致结果的状态（结论）为： Seio(Mo+M),0=1,2,,n) (4) 原因向量的类化 式中，Mo:p,(A,)-+9S,,Mp(4,)一S,1, M0A,)一prS,;Ai为因向量. 构造知识矩阵 扫描数据库 考患因果状态的全部组合情况时，利用一次 计量结果向量的估计值 合成规则可形成因果状（变）态表.在局部大前 提A"一S”时，可得到小前提A所对应的结果向 计算结果向量的估计值同实际值间的距离 量，构成矩阵M(称为知识矩阵)，以此类推.当小 前提取o个状态时，可得ω个形如M的知识矩阵： 支持度、关联强度和可信度 当局部大前提涉及的结果状（变）态取σ个时，可 否 假设规则获取？ 得到全部知识矩阵为oa个称其集合{M,…,Mn} 为基础知识库.基础知识库中集中了在标准样本 是 规则评价，解释 空间（通常为有限空间）中带有随机不确定性与 模糊不确定性的因果状态联系的全部信息，为在 图1因果关联规则发现算法流程图 一般样本空间（通常为无限空间）中寻求因果性 Fig.1 Flow chart of the knowledge discovery algorithm

、 一 张 德政等 基 于广义归 纳逻辑因果 模型 的知识 发现与 算法实现 ， 诃 ，一诃，灼 ， 由带有模糊 性 与 随机 性 的状态 的 关 系矩阵给 出‘， ， “ ，， 即 诚 ，一诚 ，约会 黔 酬 ， 万万 其 中 ， 斌万刀 为归纳 确认 度 函数 ， 它 表 明证 据 对 假说 即此表示 因果 状 态 的必 然 性规 律 的支 持 程 度 在 归纳确 证 度 函 数 ， 中证 据 包 括 两 部 分 ， 即逻 辑证据 和 经验 证据间 逻辑证 据是领域及 背 景 知 识 ， 体现 在 归纳 分析 之 中 ， 即寓于 广 义 逻 辑 归纳因果模型 的构造 中 经验证据 是 由观测 值 或 实例 所确定 由于广义 逻辑归纳模型构造 为完 全 归纳 ， 同时数据挖掘 和 知 识 发现所面对 的是海 量 数 据 ， 因而以厅万 可 以 由基于 确证 度 理论 的归 纳概率 函数 来尸毋万 表 示 定 义 ， 归 纳 概 率 函 数烈拭石 是 经 验 概 率 尸 拭双 与逻 辑概率尸田万 的线性 和 ， 即 尸佩司 护 城 双 切尸 凡石 式 中 ， ， 以 囚 ，介 囚 、 根 据 广 义细 胞 自动 机 定义 中的因果状 变 态原理 ， 结果 在 时刻 ’ 的 所有 可 能 的状 变 态 ， 可 由下 式 获得 或 ，一诃， 协 诚叼 ， 一诚，约会 黔 “ 瑟 〔 一 尸 酬〕 式 中 ， 由试 ，所导 致 的诚，玲将融合 了所 有 可 能 的多个 结果 标准 向量 ， 实现 了在标 准样 本 空 间 中 ， 在 认 知 极 限 内的完全 归纳 ， 由式 所 形 成 的每 一 个矩 阵均称 为 状 变 态矩 阵 ， 统 记 作 几 在 广 义 归纳 因果模型 构造 下 ， 在可 能 的因果 世 界 中 ， 以含 有 因果 联 系信息 的状 变 态 矩 阵 为背景 大前提 ， 原 因才在某个状 变 态下 所 能导 致结果 的状 态 结论 为 全 从 从 ， 公 ， ，… ， 式 中 ， 风浏 ，， 衅，均 ，朋 衅 〕 ，一叫 ， 飞 从 讨 ，一砂 ，玲 刁二为 因 向量 考 虑 因 果 状态 的全 部 组 合 情况 时 ， 利用 一 次 合成 规则可 形成 因果状 变 态表 ‘ 在局 部 大前 提澎 一留 ，时 ， 可 得到 小前提 所对应 的结果 向 量 ， 构成矩 阵斌 称 为知 识 矩阵 ， 以此类推 当小 前提取 。 个 状 态时 ， 可 得功 个形如斌 的知 识矩 阵 当局 部大前 提涉 及 的 结果 状 变 态 取 。 个 时 ， 可 得 到 全 部知 识 矩 阵 为砂 个称 其 集 合 冠 ，… 泳弋公 为基础 知识 库 基础 知识库 中集 中 了在标准样本 空 间 通 常 为有 限 空 间 中带有 随 机不 确 定 性 与 模糊 不确 定性 的 因果 状态联 系的全部信 息 ， 为在 一 般样本 空 间 通 常 为无 限 空 间 中 寻 求 因果性 联 系 ， 尤 其是 因果扰动 及 响 应 奠 定 了基 础 知识 发 现 算法 及 其实现 基 于上 述 理 论 ， 提 出 了相应 的广 义 因 果联系 类知 识 称 之 为 因果 关联规 则 的发现 算法 因果 关 联 规 则 的 获 取 可 形 式 化 地 描 述 为 设 介 」，几 ，…， 是 由 个不 同属 性组成 的集 合 ， 对 于 一 个给 定 的数据 库 ， 若 属 性集 二， ‘ ， 毖 ， 则 和 的 因 果 联 系 可 用 因 果 关 联 规 则 表 示 为 ‘ “ 况 定义 因果 关联规 则刁 ，一况的支 持度 即 为 ，与况在数据 库 中 同时 出现 的概 率 ， 即 叼 ，一， 定义 因 果关 联 强度尽 ， 表 示 属 性之 间 因果 关 系 的 强 弱 程 度 二 叼产，店 八 定义 规 则 的可 信 度 由定义 中给 出 的 归 纳概 率 函数 来表 征 广 义 归纳 因 果 模型 及 其 知 识 库 的构造 为广 义 因 果 关 联类 知 识 的发 现 提 供 了框 架 形 式表 示 的元知 识 ， 使得 先验知 识 同 己经 发现 的知 识 可 以 祸合 到新 的知识 发现过程 ， 用 于确 定新 的知识 发 现 的 方 向和 目标 使得 知 识 发 现 过 程 不 再 是 盲 目 进行 ， 而 是具 有 一 定 的 目的性 同时规 定 了所 获 得 的 知 识 是 反 映 因 果 关 系 的广 义 因 果 联 系类 知 识 基 于 上 述理 论 的知 识 发 现 流程 见 图 扫描数据库 构造知识矩阵 计算结果向量的估计值同实际值间的距离 支持度 、 关联强度和可信度 备 假设规则获取 一汀 一 薪 图 因果关联规则 发现算法 流程 图 眯 比 比 理叮 妙 比

·380· 北京科技大学学报 2003年第4期 知识发现过程中的几个主要步骤的实现过 然语言的形式表示出来. 程详述如下： 同一般的关联规则发现算法不同的是本文 (1)数据预处理.根据所采用的知识发现机 所提到的算法是发现因关联类算法，如气体的物 制，即验证机制或发现机制，对现实数据库D中 理变化过程中的温度、压力以及气体体积之间的 的属性值进行标准化，形成用于知识发现的数据 关系.由该算法所获得的知识反映客观事物的内 库D'.对于单一语言场，序偶P={<,>}表示原 在联系，属于深层次的知识. 因状（变）态空间中的样本值()和结果状（变）态空 为能够说明算法的正确性和有效性，以北京 间中的样本值().原因的样本值(k=1,2,,)根 某地区相关的5个气象台站16a的气象观测资 据下式进行标准化，可得到因状（变）态向量 料作为实例进行了时序因果关联规则的发现.天 a=-\A: (5) 气系统是复杂的，其复杂性不仅表现在天气过程 其中，为落在第i个区间的输入数据，to为第i个 的复杂性也表现在气象数据本身的复杂性上，通 区间的中点数据，(，为第i个区间的长度，A,为第 常有些气象资料是无法用数值测量或描述，如天 i个区间中的因状（变）态标准向量，A为依t的 气现象、天气系统、沙尘暴、云量等，它们只能有 落点而定的左邻或右邻区间中的因状（变）态标 程度上的差异，有些资料虽然能够用数值描述， 但通常也用粗略模糊的方式进行表示，如风速、 准向量，这样可得到at. (2)判定原因向量的状（变）态归属.判定原因 降水等.可以看出，气象数据具有典型的随机和 状（变）态向量a:所属因状（变）态类型，如A 模糊不确定性，气象数据中各个因子之间的关系 (k=1,2,3,4,5).由下式计算a与各因状（变）态标 也十分复杂，因此气象数据之间的关系可采用本 准向量A的测度d,取最小者a:为归属的因状 文提出的知识发现算法来进行研究. 影响气候变化的大气环流系统、下垫面热力 (变)态类型 3 状况及天文因子等环境因素十分复杂，因此，选 du(a,A.)=Eua-uA! (6) P 择物理意义明确的因子和分析其相互间的关系， 其中4a与A分别为其各自对应的分量值. 是人们致力探索的关键问题.虽然引起灾害性气 (3)构造知识矩阵.原因状（变）态向量通过自 候（比如汛期旱涝）的影响因子进行了分析，但由 组织方式找到相应的知识矩阵，通过推理，计算 于气候预测学科本身的难度，有的联系还没有完 其可能的结果状（变）态向量，并确定其所属结果 全揭示出来.由于气候的突变性，有相当的物理 状态类型o 信号作为预报因子和预报量的相互关系是随年 在标准样本空间中，首先根据因果状（变） 代变化的.表现在物理统计学方法上，预报因子 态和抽取的原因状（变）态向量，由基础知识库 是时间的函数，是动态因子，通过气象数据的数 {M,,M}求得原因状（变）态向量对应的知识 据挖掘与知识发现，可以考虑大气、海洋因子对 矩阵Mmm(i1,2,3,4,5:i=1,2,3,4,5:i-1,2,3,4,5). 要素场的影响，也考虑了要素场自身变化特征， (4)计算可能的结果状（变）态向量.由原因状 短期要素场变化，除了受大气环流系统演变 (变)态向量和其相应的知识矩阵M,根据下式 规律的制约，以及海洋下垫面和海气相互作用的 求得可能的结果状（变）态向量 影响外，还与天文因子有密切关系，分析计算中 SwueaMr (7) 所考虑的因子场具体构成如下.(1)环流因子共69 (⑤)因果关联规则的获取，标准化原因状（变） 项：包括北半球各类副热带环流系统特征量45 态所对应的结果状态向量S,计算其与各个结果 项：北半球各类极涡系统特征量12项：大西洋欧 状（变）态向量的测度并判定其所属类型，计算S 洲环流型3项：北半球中纬度西风带环流特征指 与S的距离，并在设定的阙值下判定二者是否匹 数4项：东亚槽特征量2项：西藏高原特征指数2 配，如果匹配说明因果关联规则A·S成立， 项：冬春季冷空气活动因子1项.(2)太阳黑子相 计算所获取的规则得支持度、可信度和因果 对数，黑潮指数等.1951~1996年北京汛期(79 关联强度.若规则的支持度、可信度和因果关联 月)11站雨量资料，雨量场自身变化因子等， 强度分别满足设定的阙值，则此因果关联规则被 在知识发现过程中，对96项因子10a(1986- 接受，否则拒绝.将所获取的因过关联规则以自 1995年)的数据进行了分析计算.先按正负距平

北 京 科 技 大 学 学 报 年 第 期 知 识 发 现 过 程 中 的 几 个 主 要 步 骤 的 实 现 过 程 详 述 如 下 数 据 预 处 理 根据 所 采 用 的知 识 发 现 机 制 ， 即验 证 机 制 或 发 现 机 制 ， 对 现 实数 据 库 中 的属 性值 进行 标准 化 ， 形 成 用 于 知 识 发 现 的数 据 库 ’ 对 于 单 一 语 言场 ， 序 偶尸 二 ， 户 表 示 原 因状 变 态 空 间 中 的样 本值 和 结果 状 变 态 空 间 中 的样本 值 原 因 的样 本值 二 ， ， … 川根 据 下 式进 行 标 准 化沙，， 可 得 到 因状 变 态 向量 一 生二兰司 刀 全五 ，。 一 法一 皿云当 刊 邻 也 到 其 中 ， 武为落 在 第 个 区 间 的输入 数 据 ， 肠 为第 个 区 间 的 中点数据 ， 武为第 个 区 间 的长 度 ， ， 为第 个 区 间 中 的 因状 变 态 标 准 向量 ， 翅邻 为 依 的 落 点而 定 的左 邻 或 右 邻 区 间 中的 因状 变 态 标 准 向量 ， 这 样 可 得 到 判 定 原 因 向量 的状 变 态 归属 判 定 原 因 状 变 态 向量 ’ 所 属 因状 变 态 类 型 ， 如 态 二 ， ， ， ， 由下 式计 算 与各 因状 变 态 标 准 向量 ， 的测 度 琉 ， 取 最 小者 为 归属 的 因 状 变 态类 型 、 、 ， ‘卜三砂 一 、 川 其 中声 与州夕 ，分 别 为其 各 自对 应 的分 量 值 构造 知 识 矩 阵 原 因状 变 态 向量 通 过 自 组 织 方 式 找 到 相 应 的知 识 矩 阵 通 过 推 理 ， 计 算 其 可 能 的结 果 状 变 态 向量 ， 并 确 定 其所 属 结果 状 态 类 型 在标 准 样 本 空 间 中 ， 首 先 根 据 因 果 状 变 态 和 抽 取 的原 因状 变 态 向量 ， 由基 础 知 识 库 斌 ，… 泳几 求 得 原 因状 变 态 向量 对 应 的知 识 矩 阵从 、 ， 、 ，， 任 ， ， ， ， ‘， ， ， ， ， “ ， ， ， ， ， 计 算可 能 的结 果 状 变 态 向量 由原 因状 变 态 向量 和 其 相 应 的知 识 矩 阵麟，’ ， 根据 下 式 求 得 可 能 的 结 果 状 变 态 向量 又。 全 · 鱿。 ， 因果 关 联 规 则 的获 取 标 准 化 原 因状 变 态所 对 应 的结果 状 态 向量及 ，， 计 算其 与各 个 结果 状 变 态 向量 的测 度 并 判 定其 所 属 类 型 ， 计 算及 ， 与况 ’ 的距 离 ， 并在 设 定 的 阂值 下 判 定 二 者 是 否 匹 配 ， 如 果 匹 配 说 明因 果 关 联 规 则 属一 成 立 计 算所 获 取 的规 则 得 支 持度 、 可 信 度 和 因 果 关联 强度 若 规 则 的支 持 度 、 可 信 度 和 因果 关 联 强度 分 别 满 足 设 定 的 闽值 ， 则 此 因果 关 联规 则被 接 受 ， 否 则 拒 绝 将 所 获 取 的 因过 关 联 规 则 以 自 然 语 言 的形 式表 示 出来 同一 般 的 关 联 规 则 发 现 算 法 不 同 的 是 本 文 所 提 到 的算 法 是 发 现 因关 联类算法 ， 如气 体 的物 理变 化过程 中的温度 、 压 力 以及 气 体体积 之 间 的 关 系 由该 算法 所 获得 的知识 反 映客观 事物 的 内 在 联 系 ， 属 于 深 层 次 的知 识 为 能够 说 明算 法 的正确 性和 有 效性 ， 以北 京 某 地 区 相 关 的 个 气 象 台站 的气 象观 测 资 料 作 为 实例 进 行 了时序 因果 关联规 则 的发现 天 气系统 是 复杂 的 ， 其 复杂 性不仅表现在天 气过程 的复 杂 性 也表 现 在 气 象 数 据 本 身 的复杂性 上 通 常 有 些 气 象 资料 是 无 法用 数值测 量 或 描述 ， 如 天 气 现 象 、 天 气 系 统 、 沙尘 暴 、 云 量 等 ， 它 们 只 能有 程 度 上 的差 异 ， 有些 资料 虽 然 能够用 数值 描 述 ， 但 通 常 也 用 粗 略模糊 的方 式进 行 表 示 ， 如 风速 、 降水等 可 以看 出 ， 气 象 数据 具有典型 的随机和 模 糊 不确 定性 ， 气象 数据 中各个 因子之 间 的关 系 也 十 分 复 杂 ， 因此气 象数据 之 间 的关系 可采用本 文 提 出 的知 识 发现 算法 来进 行 研 究 影 响气 候 变 化 的大气 环 流 系统 、 下 垫 面 热 力 状 况 及 天 文 因 子 等环 境 因 素 十分 复杂 ， 因此 ， 选 择 物 理 意义 明确 的因子 和 分 析其相 互 间 的关系 ， 是 人 们 致 力探 索 的关键 问题 虽然 引起 灾害性气 候 比 如 汛 期 早 涝 的影 响 因 子进 行 了分析 ， 但 由 于 气 候 预 测 学科 本 身 的难度 ， 有 的联 系还 没 有完 全 揭 示 出来 由于 气 候 的突变 性 ， 有 相 当 的物理 信 号 作 为 预 报 因 子 和 预 报 量 的相 互 关 系是 随 年 代变 化 的 表现 在 物理 统计 学方法 上 ， 预 报 因子 是 时 间 的 函 数 ， 是 动 态 因子 通 过气 象 数据 的数 据 挖 掘 与 知 识 发 现 ， 可 以考 虑 大 气 、 海 洋 因子对 要 素场 的影 响 ， 也考 虑 了要 素场 自身变 化特 征 短 期 要 素场 变 化 ， 除 了受 大气 环 流 系统演变 规 律 的制 约 ， 以及 海洋 下 垫 面 和 海气 相 互 作用 的 影 响外 ， 还 与天 文 因子 有密 切 关系 分 析计 算 中 所考虑 的 因子场 具体构成 如下 环 流 因子共 项 包 括 北 半 球 各类 副 热 带 环 流 系 统特 征 量 项 北 半 球 各类 极 涡 系统特 征 量 项 大 西 洋 欧 洲环 流 型 项 北 半球 中纬 度 西 风 带环 流特征 指 数 项 东亚 槽特 征 量 项 西 藏 高原特 征 指 数 项 冬 春 季冷 空 气 活 动 因子 项 太 阳 黑 子 相 对 数 ， 黑 潮 指数 等 一 年 北 京 汛 期 一 月 站 雨 量 资料 ， 雨 量 场 自身变 化 因子 等 在 知 识 发 现 过 程 中 ， 对 项 因子 年 的数 据 进 行 了分 析 计 算 先 按 正 负距 平

Vol.25 No.4 张德政等：基于广义归纳逻辑因果模型的知识发现与算法实现 ·381· 将96项因子划分为“0,1”两类型数据，再分别寻 covery method for scientific and technologic [J].J Univ 找时段为1个月，2个月，…，12个月10a相关关 Sci Technol Beijing,2002,21(3):237 系假设规则.计算结果表明，时段为3~4个月的 4吴炳荣，王雨田，归纳逻辑与人工智能M.北京： 时序关系中规则的可信度和支持度最大.该时段 中国纺织大学出版社，1995 与大气、海洋韵律基本一致.对北京地区汛期天 5程继华，施鹏飞，概念指导的关联规则的挖掘)计 算机研究与发展，1999,36(9：1092 气过程的韵律关系做了研究，得到97条韵律规 6 Elena Baralis,Bluseppe Psaila.Designing templates for 则，共发现33种韵律间隔，最短15d,最长为140 mining association rules [J].J Intell Inf Syst,1997(9):7 d,并验证了北京地区汛期降水存在大约3~4个 7 Agrawal R.Database mining:a performance perspective 月的规律， [J].IEEE Trans Knowledge Data Eng,1993,5(6):914 8 Sri 4结语 kant R,Agrawal R.Mining generalized association rules [A]. Proc 21*International Conference on Very Large Data- 基于广义归纳逻辑因果模型的知识发现算 base [C].Zurich,1995.407 法是以广义细胞自动机理论、广义归纳逻辑因果 9杨炳儒，基于综合语言场的因果关系推理模型[ 模型及其知识库构造为理论基础，语言场语言值 模式识别与人工智能，1996,9(1)：31 结构实现了定性与定量的相互转化.该方法可以 10 Yang Bingru.FIA and CASE based on fuzzy tanguage fi- 解决具有随机不确定和模糊不确定性特征的广 etd [J].Fuzzy Sets Syst,1998,95(2):83 义因果联系知识发现.算法中蕴含了在一般状态 11 Halpem JY,Moses YO.A guide to completeness and con- plexily for model logic of knowledge and belief []Artif 空间中利用广义归纳逻辑因果模型所构造的知 Intell,1992,54:221 识库，知识库是完备的，它包含了具有模糊和随 12 Furnas G W,Buja A.Prosections views:dimensional in- 机不确定性特征的完备知识，这些知识作为知识 ference through sections and projections [J].Comput 发现的元知识具有普遍性，构成了广义因果关联 Graphical Stat,1994,3(4):323 类知识发现的模板，从而利用演绎归纳指导知识 13杨炳儒.一类因果关系定性推力方法及其应用[A]. 的定向发掘，提高了知识发现的效率. 离散数学及其应用论集[C].北京：北京大学出版社， 1994 参考文献 14杨炳儒.广义细胞自动机与广义归纳逻辑因果模型 1 Berson Alex,Smith Stephen J.Data Warehousing,Data ).北京科技大学学报，1997,19(4)：403 Mining,OLAP[M].MeGraw-Hill Book Co,1999 15杨炳儒.专家系统中的一类不确定性归纳型自动推 2杨炳儒，张德政.关于知识发现系统的扩展性研究 理机制.模式识别与人工智能，1997,10(4)：326 [).北京科技大学学报，2000,21(1)：84 3 Zhang Dezheng.Yang Bingru.A new knowledge dis- Algorithm and Realization of KDD Based on the Generalized Inductive Logical Causal Model ZHANG Dezheng",SHI Yang",DEND Y,YANG Bingru 1)Information Engineering School,University of Science and Technology Beijing,Beijing 100083,China 2)Anshan Science and Technology University,Anshan 114002,China ABSTRACT Based on the fuzzy language field,generalized cell automation and generalized inductive logical causal model,the mechanism of causal relation knowledge discovery were studied,and an algorithm of KDD with causal rules was proposed.With this algorithm,the causal relation knowledge discovery with uncertainty of random and fuzzy can be done effectively.An example illustrate the correctness and effectiveness of the algorithm KEY WORDS generalized inductive logical causal model;generalized causal relation;data mining;knowledge discovery

】 张德 政 等 基 于 广 义 归纳逻 辑 因 果 模型 的知 识 发现 与 算法 实现 将 项 因子 划 分 为， ， ” 两类 型 数据 ， 再 分 别 寻 找 时段 为 个 月 ， 个 月 ， … ， 个 月 相 关 关 系假 设规 则 计 算结果表 明 ， 时段 为 一 个 月 的 时序 关 系 中规 则 的可信度 和 支 持度 最 大 该 时段 与大气 、 海洋 韵律 基 本 一 致 对 北 京地 区汛 期 天 气 过 程 的韵律 关 系 做 了研 究 ， 得 到 条 韵律 规 则 ， 共 发现 种 韵律 间隔 ， 最 短 ， 最 长 为 ， 并验 证 了北 京地 区 汛 期 降水 存 在 大 约 一 个 月 的规律 结 语 基 于 广 义 归纳 逻 辑 因 果 模 型 的 知 识 发 现 算 法 是 以广 义 细胞 自动 机 理 论 、 广 义 归纳 逻 辑 因果 模 型及 其 知 识库 构 造 为 理 论基础 ， 语 言场 语 言值 结构 实现 了定 性 与 定 量 的相 互 转化 该 方法 可 以 解 决 具 有 随机 不 确 定和 模糊 不 确 定 性特 征 的广 义 因果联 系知 识 发现 算 法 中蕴含 了在 一般状 态 空 间 中利 用 广 义 归纳 逻 辑 因 果 模 型 所 构造 的知 识库 知 识库 是 完备 的 ， 它 包 含 了具 有 模糊 和 随 机不确 定性特 征 的完备知 识 ， 这 些 知 识 作 为知识 发现 的元 知识 具有普遍性 ， 构成 了广 义 因果关联 类 知 识 发现 的模板 ， 从 而 利用 演 绎 归纳 指 导知 识 的定 向发掘 ， 提 高 了知 识 发现 的效 率 参 考 文 献 ， 研 ， ， 【 ， 杨炳儒 ， 张德 政 关于 知 识发现 系统 的扩展性研 究 北 京科技大 学学报 ， ， ， 丫功 可 ， ， 吴炳 荣 ， 王 雨 田 归纳逻辑与人 工 智 能 北 京 中 国纺 织大 学 出版社 ， 程 继 华 ， 施 鹏 飞 概 念 指 导 的关联规 则 的挖 掘 明 ， 计 算机研 究 与发 展 ， ， ， 刀 ， ， ， 刚 民 ， 杨炳 儒 基于 综 合 语 言场 的 因 果 关 系推 理 模型 模式识 别与 人工 智 能 ， ， 目甩 乙 石 ， ， ， 】 ， ， 城 而 ， ， 杨炳儒 一 类 因 果关 系 定性推 力 方法及其应用 』 离散数学及 其应用 论集 北 京 北 京大学 出版 社 ， 杨 炳儒 广义 细 胞 自动机与广义 归纳 逻 辑 因 果模型 北 京科技大学学报 ， ， 巧 杨炳儒 专家系统 中的一类 不 确定性 归纳型 自动推 理 机制明 模式识 别与 人 工 智能 ， ， 乙队咬刀 气及万 犷愁刀石探 扮气 从子 王 ， 肠 腼 ， ， 】 ， ， 二 ， 】泳 ， ， 叨 ， ‘ 如 朋 叨 砂 田叮 扮 】 灿 电