《北京科技大学学报》：关于知识发现系统的扩展性研究

告瓷讯htp://www,cqvip.com 第22卷第1期 北京科技大学学报 Vol.22 No.1 2000年2月 Journal of University of Science and Technology Beijing Fcb.2000 关于知识发现系统的扩展性研究 件-8羽 杨炳儒 张德政 TP3升3 北京H技大学信息.L程学皖.化京00083 TP18 摘要在总结和分析月前基于数据库的知识发现竹理论，技术和方法现状的基础上：，对知识 女现的发展趋势进行了探索.介绍了在作者先前提山的基于双库协同机制的知识发现理论的 基出|.，就整个知口发现过程的机理、KDD扩展性结构和运行机制所进行的深入研究， 关键词数据挖掘：知识发现：双库协饲机制 分类号TP182 扩展赶，数据摩 1数据挖掘及知识发现的现状 模糊逻辑和粗糙集理论等" 数据挖掘和知识发现的应用对象从结构性 数据库及数据仓库技术的应用积累了大量 数据源发展到半结构性及非结构性数据源，包 的企业管理、金融活动、商业泛作、工程技术及 括关系数据库、面向对象数据库、空闻关系数据 科学研究等各行业和领域的大量数据及丰富的 库，推理数据库、多媒体数据库、时态数据库、文 信息资料：Internet的延展使得信息量剧增、各 本数据源、图像数据源及音频和视频数据源等， 类wb数据库、电子邮件和网内包含着丰富 近年来，数据挖斑和知识发现的理论研究表 的信息资源.在这些数据和资料中隐藏着各种 现出多学科交叉和多种技术方法融台及数据挖 不同领域的可满足不同需求的信息，但这些信 掘的泛化和识发现的统-一化特征.因而，需要 息通常是传统的分析方法和分析工其所无法提 有种新的知识发现体系来实现知识发规的统 供的.因而，数据挖掘及基于数据库的知识发现 ·和完备性以及认知自主性， 系统(Knowledge Discovery Based on Database. KDD)应运而生，数据挖掘是为了解决传统分析 2新的知识发现结构一KDD* 方法的不足，并针对大规模数据的分析处理而 出现的，数据挖掘可从人量数据中提取出隐藏 数据挖掘和知识发现发展到今天，已取得了 在数据之后的有用的信息，基于数据库的知识 重大进展，同时也出现了富有挑战性的生长点， 发现是识别数据中有效的、新颖的、潜在有用的 其中较为重要的是：(【)突破基丁数据库的知识 和最终可被理解的模式的非平凡过程，知识发 发现的封闭系统，而与知识库协同起来，由基础 现借助各种数据挖掘方法来获取各类知识，其 知识库制约与驱动KDD,从而发现新知识：(2) 中包括分类规则、预测模型、相似模式、聚类、关 目前多于具体发掘技术的研究，应提升到在宏 联规则、序列模式、依赖关系或依赖模型、异常 观背景下多个抽象级、不同知识层面上的知识 和趋势等. 发现系统的一般性框架的研究：(3)数据库的知 各个领域都从不同的角度利刑机应的理论 识发现与知识库的知识进化成有机融台，统一 和分析力法进行着数据挖掘的研究和开发「 在知识发现的全部运行过程中：〔4)发掘出知识 作，数据挖掘和知识发现所采用的方法涉及到 的可理解性，先验知识在数据发掘〔知识发现) 机器学习、统计分析、数据库分析、模式识别、机 中的应用问题：(5)实用化系统和开发工具的研 器发现、人工智能、知识获取、神经网络、数据可 制 视化、不确定性推理、智能数据分析、遗传算法、 针对上述认识与逻辑发展的必然，作者于 I997年从知识发现、认知科学与智能系统交叉 1999-2-06收稿杨炳情？.56：，教授，尊导 国家自然科学金资助课题No.698350011 结合的角度，提出了双库协同机制5.通过不断 的研究和开发，提出了基于双库协同机制的扩

第 22卷 第 1期 2000年 2月 8 北 京 科 技 大 学 学 报 JournalofUniversityofScienceandTechnologyBeijing V0I．22 No．1 Feb．20o0 关于 知识 发现 系统 的扩展性研 究 杨 炳 儒 张德政 北京 科技 大学信息 上程 学 院，北京 100083 弋 ／3 T?／f 摘 要 在 总结 和 分 析 目前基 r数 据 库 的 知 识 发 现 的理 隆、技 术 和 方 浊 现状 的 基 础 】．．列 知 识 发 现 的 发 艘 趋 势 进 行 了探 索 介 绍 了在 作 者 先 前 提 … 的基 于 双 库 协 同机 制 的 知 识 发 现 理 论 的 基 础 就 整 个 葺¨识 发现 过 程 的 机 理 、KDD扩 展 性 结 构和 运 行 机 制 所进 行 的潇 入 研究 ． 关键 词 数 据 挖 掘 知 识 发 现 ；双 库 协 机 制 分 类 号 TP182 1数 据 挖掘 及 知 识 发 现 的 现状 数 据 库 及 数 据 仓 库 技 术 的 庸 积 累 丁大 量 的 企 业 管 理 、金 融 活 动 、商 业 运 作 、工 程 技 术 及 科学研 究等 并 行业和 领 域 的大 量数 据 及丰 富 的 信 息 资 料 ；Internet的 延 展 使 啬息 量 剧 增 ，各 类 Web数据 库 、电子 邮件 和 嘲 必内包 含着 丰 富 的信 息 资 源 ．在这 些 数 据 和 资 料 中 隐藏 着各 种 不 同 领 域 的 可 满 足 不 削 需 求 的 信 息 ，但 这 些 信 息 通 常 是 传 统 的 分 析 方 法 和 分 析 工 具 所 无 法 提 供 的 ．因 而 ，数 据 挖 掘 及 基 1『数 据 库 的 知 识 发 现 系 统 (KnowledgeDiscoveryBased onDatabase， KDD)应 运 而 生 ，数 据 挖 掘 是 为 了解 决 传 统 分 析 方 法 的不 足 ，并针 对 大 规 模数 据 的分 析 处理 而 出 现 的 ，数 据 挖 掘 可 从 大 量 数 据 中 提 取 出 隐 藏 在 数 据 之 后 的 有 用 的 信 息 ，基 于 数 据 库 的 知 识 发现 是 识别数 据 中有 效 的 、新 颖 的 、潜在 有用 的 和 虽 终 可 被 理 解 的 模 式 的 非 平 凡 过 程 ，知 识 发 现借 助 各 种 数据 挖 掘 方 法 来 获取 各 类 知 识 ，其 中 包 括 分 类 规 则 、预 测 模 型 、相 似 模 式 、聚 类 、关 联 规 则 、序 列模 式 、依 赖 关 系或 依赖 模 、异 常 和 趋 势 等 ． 各 个领 域 都 从不 f『J角 度利 刚 相应 的理 论 和 分 析 方 法 进 行 着 数 据 挖 掘 的 研 究 和 开 发 一r 作 ，数 据 挖 掘 和 知 识发 现 所采 用 的方 法涉 及 到 机器 学 习 、统计 分 析 、数 据库 分 析 、模 式 识别 、机 器 发现 、人 工 智 能 、知 识 获 取 、神 经 网 络 、数 据 可 视 化 、不 确 定 性 推 理 、智 能 数 据 分 析 、遗 传 算 法 、 1999—124)6 收稿 杨 炳儒 要．56岁 ．教授 ，博 导 ·国家 自然科 学 牲 盘 资 助课 题 (No69835001I 撅 盥 掘 模 糊 逻辑 和粗 糙集 理论 等” 数 据 挖 掘 和 知识 发 现 的府 用 对 象 从 结构 性 数 据 源 发 展到 半 结 构性 及 非 结构 性 数据 源 ，包 括 关 系数 据 库 、面 向对 象数 据 库 、空 间关 系数 据 库 推 理数 据 库 、多媒 体数 据 库 、时态 数 据库 、文 本 数据 源 、图像数 据 源 及音 频 和视 频 数 据源 等 ． 近 年来 ，数据挖 掘和 知 识发 现 的理 论研 究表 现 出多学 科 交 叉和 多种技 术 方 法融 合及 数据 挖 掘 的泛 化和 知识 发 现 的统 一 化特 征 ． 而 ，需要 有 种新 的知 识发 现 体 系来 实现 知 识发现 的统 和 完备 性 以及认 知 自主性 ， 2 新 的知 识发 现结 构— — KDD 数 据挖 掘和 知 识发现 发展到 今天 ，已取得 了 重 大 进 展 ，同 时 也 出 现 了富 有 挑 战 性 的 生 长 点 ， 其 中较 为 重 要 的 是 ；(1)突 破 基 于 数 据 库 的 知 识 发 现 的 封 闭 系 统 ，而 知 识 库 协 起 来 ，由基 础 知 识 库 制 约 与 驱 动 KDD，从 而 发 现 新 知 识 ：(2) 目前 多于 具体 发掘 技术 的研 究 ，应 提 升 到在 宏 观 背 景 F多个抽 象 级 、不 同 知 识屡 面 的知 识 发 现 系 统 的 一 般 性 框 架 的 研 究 ；(3)数 据 库 的 知 识 发 现 与 知识 库 的 知识 进化 应有 机 融 合 ，统 一 在 知 识发 现 的全 部 运 行过 程 中：(4)发掘 出知 识 的 可 理 解 性 ，先 验 知 识 在 数 据 发 捌 (知 识 发 现 ) 中 的 应 用 问 题 ；(5)实 用 化 系 统 和 开 发 T 具 的 研 制 ． 针 埘 上述 认 识 与 逻 辑 发 展 的 必 然 ， 作 者 于 1997年 从 知 识 发 现 、认 知 科 学 与 智 能 系 统 交 叉 结 合 的角 度 ，提 出 了双库 协 同机 制 ．通 过 不 断 的研 究和 开 照 ，提 出 了基 于 双 库协 同机 制 的扩 维普资讯 http://www.cqvip.com

维告瓷讯http://www.cqvip..com Vol.22 No.1 物妈儒等：关于知识发现系统的邦摇性硒究 ·85· 展KDD结构KDD*系统 动态的参与数据库的挖拙过程，用的光验知 KDD*是在KDD技术的基础上融入双库协 识及知识库中的固有知识通过此机制可以产生 同机制，即构建数据库与基础知识库的内在联 “定向挖掘”，以提高认知自主性和避免海革搜 系“通道“，从而用基础识库去制约与驱动 索的产生：(2)在知识库的维护方面，通过双库协 KDD的发过程，改变KDD固有的运行机制. 同可在数据修掘过程中实时地修改和维护知识 在结构与功能上形成了相对于KDD而言的· 片中的内容，包括冗余性检验，矛盾处理等. 个开放的、优化的书体.双库协同机制的引入使 KDD*是KDD与双库协同机制相融合的·种知 得KDD在功能上得到了进一步的完善：(1)从 识发现的新结构，KDD*的系统总体结构图，如 数据挖掘方面，双库协同机制使得知识能够 图1. 蒋获得规则继入发掘知：识4检否是否重复，冗余，于后。 中断型协调器 《定向句搜索) 获得假设规侧 评价 定向发掘过程 衍生知识库 聚焦 根粥州'需求马 肩发型协调器 搜索发掘知识库中的知识节点的关联 状态，发现知识短缺，并确定优先等级 感兴趣知识 定问发掘) 根据F库形成救据了类 根据属性划分知识节点，形成 结构，构成发蜘数据库 推断弧线，构成发掘知识库 划分数据车 划分知识子库 子处理 真实数据车 基础知识库 图1KDD*系统总体结构图Fig1 General Framework KDD*System KDD*具有以下特征： 与数据子类结构之间的对应关系，为实现“限制 (1)KDD*有机地沟通与融合了KDD*新发 性的搜索”血减小搜索空间、提高发掘效率提供 现的知识与基础知识库中固有的知识，使它们 了有效的技术方法， 成为一个有机的整体：即实现了“用户的先验知 识与先前发现的知识可以耦合到发现过程中”. 3理论依据及算法 2)在知识发现过程中，KDD*对于元余性 双库协同机制构建在作者首次提出的泛同 的、重复性的、不相容的信息作出了实时处理， 伦概念、结构对应定理和泛同伦范畴同构定理 有效地减少了由于过程积累而造成的问题的复 杂性，同时为新旧知识的融台与合成提供了先 基础上，建立了知识库中知识节点与真实数据 库中数据子类结构的层之间的·对应关系， 决条件：实现了“知识与数据库同步进化” 从而实现了定向搜索与定向发拥 (3)从认知科学的角度看，KDD*强化并提高 3.1泛同伦和结构对应定理 了知识发现的智能化程度，提高了认知自主性 定义1设人，g为从拓扑空间X到Y的连续 (这将是今后相当长的一阶段内保特的研究基 映射，若存在泛同伦F(x,t=x),使得付J任意 调，较有效地克服领域专家的自身局限性，实 点xEK均有f(x)=Fx,(0.,0),gxJ=Fx,1, 现了“采用领域知识辅助初始发现的聚焦”. ,1)1,侧称g泛同伦于天并称F为连续映射f (4)作为KDD*的核心技术一双库协同机制 与映射g的泛同伦，记作fg. 的研究，揭示了在一定的健库原则下，知识子作 定义2从拓扑空间X到拓扑空间'的连续

Vo1．22 No．1 {西炳 儒 等 ：关 J知 酿蛙现 系 统 的 腱性 研 究 展 KDD结构——KDD 系统 ． KDD 是在 KDD技 术 的基 础上 融入 双库 协 同机 制 ，即 构建 数 据库 与 基 础 知 识库 的 内在 联 系 “通 道 ”， 从 而 用 基 础 知 识 库 去 制 约 弓驱 动 KDD的发 掘 过程 ，改变 KDD同有 的运 行 机 制 ， 在 结 构 与功 能 形 成 了相 对 y-KDD l 言 的 个 开放 的 、优 化 的扩体 ．双 库协 同机 制 的引 入使 得 KDD在 功 能上 得 到 了进 一步 的完善 ：(1)从 数据 挖 掘 方 面 ，双库 协 『机制 使 得 知 识库 能 够 匪 ! 匠 动 态 的 参 与 数 据 库 的 挖 掘 过 程 ，用 的 先 验 知 识及 知 识库 中的 固有 知识 通过 此 机制 可 以产 生 “定 向挖 掘 ”，以提 高 认 知 自主 性 和避 免 海 最搜 索 的产生 ；(2)在 知识 库 的维 护方 面 ，通 过 双库 协 『可 在数 据挖 掘 过程 中实 时地修 改和维 护 知识 的 内容 ，包 括 冗 余 性检 验 ， 矛盾 处 理 等 ． KDD 是 KDD与 双库 协 同机 制 相融 合 的 种知 识发 现 的新 结 构 ，KDD 的系 统 总 体结 构 图 ，如 1． 中断 型协 调器 f定 向拽 索 ) — — — 评 价 ] 『划分知识享库l 基础 知识 库 图 1 K1DD 系统 总 体 结 构 图 Fig1~ ltera|FTam 0TkKDD Sy~lem KDD 具 有 以 特 征 ： 【1)KDD 有机 地沟 通 与融 合 了 KDD 新发 现 的 知 识 与 基 础 知 识 库 中 固 有 的 知 识 ，使 它 们 成 为 一个 有 机 的整 体 ；即实现 了 “用广 的 先验知 识 与先前 发 现 的知 识可 以耦合 到发现 过 稗 中 ． (2)在 知识 发现 过 程 中，KDD*对 十冗余 性 的 、重 复性 的 、不 相 容 的信 息 作 出 了实 时处 理 ， 有 效地减 少了 由于 过程 积 累 而造成 的问题 的 复 杂 性 ，同 时为 新 旧知 识 的 融 合与 合成 提 供 了先 决 条件 ；实 现 了 “知识 与数据 库 同步进 化 ”． (3)从 认知科 学 的角度 看 ，KDD 强化并 提高 了知识 发 现 的 智能化 程 度 提高 ，认 知 自主 性 (这 将 是 今 后 相 当长 的 阶段 内保 持 的研 究 基 调 )，较 有 效地 克服 领域 专 家 的 自身 局 限性 ．实 现 了“采 Hj领域 知 识 辅助 初 始 发现 的聚焦 ”． (4)作 为 KDD 的 核心 技 术一 双库 协 同机 制 的研 究 ，揭示 了在 一 定 的建库 原 则下 ．知识 子库 与数据 子类 结 构之 间 的对应 关 系 ，为 实现 “限制 性 的搜 索 ”l『Ⅱ减 小搜 索 空间 、提高 发掘 效率 提供 了有效 的技 术 方法 ． 3理 论 依 据 及算 法 双 库协 同机 制构 建在 作者 首次提 出 的泛 同 伦 概念 、结 构 对应 定 理 和泛 同伦 范畴 同 构 定理 基 础 }：，建立 了知 识库 中知识 节 点 与真 实 数据 库 中数 据 子 类 结构 的层 之 间 的 一 对 应 关系 ， 从 而实 现 了定 向搜 索 与定 向发 掘 。． 3．1泛同伦和 结构 对应 定理 定 义 I设 g为从 拓 扑空 间 到 r的连 续 映 射 若存 在 泛 同伦 F(x，t)=fix)，使得 对 卜任意 点 x@X均 有 ，()：F(，(0 ．-，，0))，g(x)-F(x，(1， … ， 1))，则 称 g泛 同 伦 于 并 称 为 连 续 映 射 ， 与映射 g的泛 同伦 ，记 作 ， ． 定 义 2从拓 扑空 间 到 拓 扑 宁 问 r的连 续 维普资讯 http://www.cqvip.com

维告瓷讯http://www.cqvip..com -86 北京科技大学学报 2000年第1期 映射f称为泛同伦等价，若存在从拓扑空间Y到 寸in∈fn,≤n2一n)≤nz) 拓扑空间Y的连续映射g,使得合成映射gf和 寸EMn,丰，n)≠啊n) f·g分别是从Y和Y到自身的、泛同伦于对应 其中≤为N上全序关系，≤为[0,1]“上的 空间的恒等映射I和，的映射，分别记作gf 宇典序，Wn(n∈)为语言值的标准向量í即样 I,g~r:映射g也是泛同伦等价，山称为等价f 本取自语言值对应区间中点及其邻域时所对应 的逆等价， 的同量 定义3设给定两个石扑空间，若至少存在 在数据子类结构S-<UN,>中，称满足下 一个空间到另··个空间的一个泛同伦等价的映 列尔件的三元组<4，n,5,>为S的层： 射，则称这两个空间为同一泛同伦型的空间. 1)w,∈U,u.(i=1,2,3,,y)为初步划定的第i个 定理1（结构对应定理）：对于论域X,在相 区间段内样本数据集： 应的知识子库与数据子库中，关于知识结点的 2)n,∈N,ni=12,3,…,v)为依样本数据集所落 拓扑空间<E,a>与关于数据子类í结构)的拓扑 ×间阳属的语言值： 空间<F,B>是同一泛同伦型的空间. 3ri-1,2.3.…,y)的确定：iu中样本数据落 3.2知识结点、数据子类结构及其对应关系 于非交叉区间时，户，取为标准向量：此时， 在泛同伦的理论基础之上，知识子库与其 r,∈n.i)u,中样本数据落入交义区间内时，用 相应的数据子库之间的“知识结点”与“数据子 插值公式求得： 类í结构)"构建. =A1-匹二d+Au,二d (1)知识节点.在相关于论域X的知识子库 (为第：个区间标准样本数据，1为第个区 中，称按如下形成表达的知识为不确定性规则 间长度，A,为第个区间标准向量，Aa为依，落 型知识： 点所定的相邻区间标准向量) 1)P%)→Q() 2P.0→A. 冉根据与，r4的测度，或r与，F1的测 3)AP0→2，)4)AP.0→A2.0 度，决定取，或或r-1,并将此部分数据保留 其中Pn,Px),Q0,Q,0分别为“属性词" 在第i层或移至第计1层或移至第-1层. 「或“状态词”)十“程度词“的形式.P(门与Px) (3)知识结点、数据子类的结构对应关系 称为知识始结点，Q门与2，”称为知识终结 由上述的3.1.(1)与(2)可知，在把·个空间 换成同··个泛同伦型的空间时，泛同伦类集合 点，并分别称为知识素结点：AP(),AQ()分 的结构并无改变，所以在同伦理论里，可以把同 别称为知识台结点：两者统称为知识结点. 泛同伦型的空间看做是相同的.给出了知识 在相关于论域X的知识子车中，全体知识 子库中“知识结点”与相应数据子库中“数据子 结点的集台记作有限集)，其幂集记作PE): 类结构”中的层之间的一一对应关系，如图2所 设a=(E(a含中与E,则<E,a>构成一个拓扑空 示.这样就保持了面对巨大的数据库与知识库 间 而进行“定向”收搜与“定向”挖掘 (2)数据子类结构.对于论域，在相应于 知识子库的数据子库中，与每个知识素结点相 知识了库相应-于论域) 数据子库（相应于论域） 应的结构S=<U,N,I,W>称为数据子类结构. 其中，U丰中，U={u.,…},(4,是数据集，由下述 陶识素结点P。 对应于S的某个 的[形成)，它是刻划相应于知识素结点“属性 词”或“状态词”的数据集的类（称为数据子类： 儒P对座于S的装个 N丰中为语言值的有限集，它是刻划相应于知识 知识合结点分解 素结点“程度词”的语言值的集合： 对应十5，的某个 素P I:N一U,它是按语言值将数据集的类U进 行划分的映射.在数据连续分布时，通常划分为 先分解为各素知识结点 若下交叉区间（即；w门私丰中）片： 图2知识节点与数据子类结构对应图 W:N-0,1]k为正整数)满足： Fig2 Corresponding Graph

北 京 科 技 大 学 学 报 2000年 第 l期 映 射，称 为泛 同伦 等 价 ，若存 在 从拓 扑 空 间 r到 拓 扑 空 间 的连 续 映射 g，使得 台成 映 射 g。厂和 ，。P分 别 是 从 和 r到 自身 的 、泛 同伦 于对 应 空 间的 恒等 映 射 ^和 的 映射 ，分 别记 作 gof￾L，l厂og 映 射 g也 是 泛 l刊伦 等 价 ，且称 为 等 价， 的 逆 等 价 ． 定义 3设给 定 两个 拓 扑 问 ，若 至 少存 在 个 空 间到 另 ‘个 空间 的 ‘个泛 同伦等 价 的映 射 ，则 称这 两个 空 间为 同 一泛 同伦 型 的空 间 ． 定 理 1(结 构 对 应 定 理 )：对 于 论 域 ，在 相 应 的 知 识 子 库 与 数 据 子 库 中 ，关 于 知 识 结 点 的 拓扑 空 间 E，d>与关于 数 据子 娄 (结构 )的拓 扑 间 ， 是 同一 泛 同伦型 的空 间 ． 3．2知识结点 、数据子类结构 及其 对应 关系 在泛 I刊伦 的理 论基 础2 ，知 识 子 库与 其 相 应 的 数 据 子 库 之 间 的 “知 识 结 点 ”与“数 据 子 类 (结 构 )”构 建 ． (1)知 识节 点 ．在相 关 于 论域 的知 识子 库 中 ，称 按 如 F形 成表 达 的知 识 为不 确 定性 规 则 型 知 识 ： 1) 加 Q㈤ 2)P(曲 AQ¨。 _ l 3)6a(x) Q∞0 4)A C曲 AQ(劢 其 中P(∞ ，Jp舡)，Q( ，Q( 分 别为“属性 词 ” (或 “状 态词 ”)+“程 度 词 ”的形式 ．Jp( 与 ㈤ 称 为 知识 始 结 点 ，Q(m 与 Q(∞ 称 为 知 识终 结 点 ，并 分 别 称 为 知 识 素 结 点 A ㈣ ，AQ(∞ 分 别 称 为 知 识 合 结 点 ；两 者 统 称 为 知 识 结 点 ． 在 相 关 于论 域 的知 识子 岸 中 ，全体 知 识 结 点 的集 合 记 作 (有 限集 )，其 幂 集记 作p(E)； 设 d ( 含 与 目 ，则 ，>构成 一 个拓 扑 空 间 (2)数据 子类 结构 ．对 于论 域 ，在相 应 于 知 识子 库 的 数据 子库 中 ，与 每个 知 识 素 结点 相 应 的结 构 S <u，Ⅳ'I， 称 为数据 子类 结构 ． 其 中， ≠ ，U= {“．，“，·}， 是数据 集 ，由下 述 的 ，形 成 )，它 是 刻划 相 应 于知 识 素 结点 “属 性 词 ”或 “状态 词”的数据集 的类 (称 为数据 子类 )； N≠ 为语 言值 的有 限集 ，它 是 刻划 相 应 于知 识 素 结 点“程 度 词 ”的语 言 值 的集 合 ； I：．Ⅳ一u，它 是 按 语言 值 将 数据 集 的类 进 行划 分 的映 射 ．在数 据连 续 分布 时 ，通常 划分 为 若 T 交 叉 区 间 (即 ；V n ≠ ))； w：Ⅳ一 0，1]( 为 正 整数 )满 足 ： V… ∈Jv(n． 一 眦 ．) )) V ：∈Ⅳ(n．≠ 一 州 n．)≠ )) 其 中 为 Ⅳ上 序 关 系 ， 为 [0，1]上 的 字 典序 ，W(n)(nc邮 为语 言值 的标 准 向量 (即 样 本取 自语 言值 对应 区间 中点及 其邻域 时所对 应 的 向 量 )． 在 数 据 子 类 结 构 S-< Nd, 中 ，称 满 足 下 列 条什 的三 元组< ，n．，>为 的层 ： 1)M∈U“．0=1,2，3，一， 为初 步划 定 的 第 个 lx问 段 内样 本 数 据 集 ； 2)n．oN,n,(i-1，2,3，…，v)为依 样本数 据集 所 落 问 归属 的 语 言值 ； 3¨ 1，2,3，…，v)的确 定 ：i)*中样本 数 据 落 于 非 交 叉 区 间 时 取 为 标 准 向 量 ；此 时 ， r,E n)．ii) 中样本 数据 落入 交叉 区 间 内时，用 插 值 公式 求 得 ： r7=A(1_ ) ．1u,-， u；I 【为第 i个 区 问标 准 样 本数 据 ， 为第 i个 区 间 长度 ，A．为 第 i个 区 问标 准 向量 ，A 为依 “落 点所 定 的相 邻 区 间标 准 向量 )． 冉根 据 一与 ， ．的测度 ，或 _与n， ．的测 度 ．决定 取 或 ．或 … 并将 此 部 分数 据 保 留 在 第 i层 或移 至第 1层 或 移 至 第 1层 ， (3)知 识 结 点 、数据 子类 的结 构 对 应关 系 由上述 的 3．1，(1)与 (2)可知 ，在 把 个 空 问 换 成 同 。。个泛 同伦 型 的空 间时 ，泛 同伦 类 集合 的结构 并无改 变 ，所 以在 同伦 理论 里 ，可 以把 同 一 泛 同伦 型 的空 间看做 是相 同的 ．给 出 了知 识 子 库 中“知 识结 点 ”与 相应 数 据 子库 中 “数 据 子 类 结构 ”中的层之 间的 一一对 应 关系 ，如 图 2所 示 ，这 样 就保 持 了面对 巨大 的 数据 库与 知识库 而进行 “定 向”收 搜 与“定 向”挖 掘 ． 知识 r库 (相应 于论域 ) 数据 子库 (相施 于论 域) 图 2知识 节 点与数据 子类 结构 对应图 F CorrespondingGraph 蔼 衅乒啪 ． ， ＼ 骱 维普资讯 http://www.cqvip.com

维告瓷讯htp://www,cqvip.com Vol.22 No.1 阿砖佑等：共十知识发魏系统的展性研究 87 3,3双库协同的技术实现 4.2演示系统及应用 双库协同机制的技术实现的关键是要根据 我们的工作主要侧重在整个知识发现过程 中断协调算法与启发协调算法构造R型协调器 的机理、KDD扩展性结构和运行机制、以及软 与S型协调器、R型协调器的主要任务是当从 件系统的系列性开发.其主要特点为宏观与做 真实数据库的大量数据中经聚焦生成规则 观相结台、抽象与具体相结合、理论与应用相 i知识)后，使KDD进程产生“中断"，搜索知识 结，作此基础上，我们经历了从机理研究、算法、 库中付应位置有无此生成规则的重复、冗余与 编稈的全过程，开发了覆盖与扩展了现存软件 矛盾.若有，则取消该生成规则或相应处理后返 所有功能的KDD*软件，称为自主性KDD*软 回KDD的“始端”：若无.则继续KDD进程，即 件.从理论上基本解决了双库协同的机理及其 进行评价与入库、S型协调器的主要功能是在 技术实现、并初步用于实际领域中. 以属性为基础的知识库建库原则卜，通过搜索 知识发现理论和方法的应用范围广闭.在 知识库中“知识结点"的不关联念，以发现“知识 决策支特、商业行为论证、分析预测及科学研究 短缺”，产生“创见意象”、从而启发与激活真实 中表现出良好的应用前景.以发掘关联规则为 数据库中相应的“数据类“，以产尘“定向发掘进 例，以美国某地区社会调查结果的部分数据资 程””KDD*知识发现的开放体系结构，即在知 料来简单介绍KDD*软件，真实数据库内的属 识发现的基础上融入双协同机制，用基础知 性包括调查对象的工作状况、婚姻状况、初婚年 识库去制约与驱动知识发现过程，改变了数据 龄、小孩年龄、教育年限、年收入状祝、自我感觉 发掘和知识发岘的固有的运行机制，形成了在 等17个因素、 结构与功能上相对的与般数据发掘和知识发 根据专家感兴趣方向进行数据发掘（即为 现的的-一个开放、优化扩体. KDD过程)首先选择专家感兴趣的属性进行数 据发掘，如下图所示的选择“教育程度”作为条 4KDD*的实现与应用 件，“91年收入”作为结果.所发现的知识表示 成规则的形式，见下图3. 4.1KDD*系统的实现 主要包括如下儿个步骤： (1)预处理.对原始数据进行包括数据净化、 数值化与特定转换等在内的处理、形成发掘数 据库DMDB,以供数据发掘过程使用. (2)聚焦.即从发掘数据库里进行数据的选 择，进行聚焦的方法主要是利用聚类分析和判 别分析.指导数据聚焦的方式有：〈)通过人机 父互由专家提出感兴趣的内容，让专家来指导 数据发掘的方向.（ⅱ）利用启发式协调器进行定 4w」 时 向的数据发掘. (3)求取假设款则.在本系统中主要是抽取 图3所获取的规则Fig3 Rules Discovery 因果关联规则，从而进·步丰富基础知识库，使 利用启发型协调器进行自动发掘关联规则 用的发掘方法是统计归纳推理法，” (即DD*过程)， (4)双库协同机制.即采用中断型协调器、 启发型协调器是根据知识库中知识短缺， 启发型协调器，分别对所获得的假设规则进行 来自动发掘知识，然后再通过领域专家介入或 处理和利用关联强度激发数据聚焦进行数据发 相应的评价方法加以筛选.还以上面的数据库 掘、 为例，KDD*发现结果如图4所示. (5)评价.这一环节1要州于对所获得的假 由此可见，新的动态知识库系统较传统的 设规则进行价值评定，以决定所得的规则是否 知识库内涵知识的数量和深度都有了较大的扩 存入知识库.将经评价认可的规则作为新知识 展，有效地克服了领域专家的自身局限. 存入衍生知识库中

确 炳 儒 等 ：关 十 知 识 发 现 系 统 的扩 展 性研 究 3．3双库协 同的技术 实现 双库 协 同机制 的技术 实 现 的关键 是要 根据 中断 协 调算 法 与启发 协 调算 法构造 R型 协调 器 与 S型 协调 器 ，R型 协 调器 的主 要任 务是 当从 真 实数 据 库 的 大 量 数据 中经 聚 焦 lm生 成 规 则 (知 识)后 ，使 KDD进程 产 生“q断 ”，搜 索 知 识 库 中对应 位 置 有无 此 生 成 规 则 的重 复 、冗 余 与 矛 盾 ．若 有 ，则 取 消 该 生 成 规 则 或 相 应 处 理 后 返 回 KDD的 “始 端”；若 无 ，刚继 续 KDD进 程 ，即 进 行 评价 与入 库 ，S型 协调 器 的主要 功能 是在 以属 性 为基 础 的知 识 库 建库 原 则 F，通 过搜 索 知 识库 中“知 识结 点”的小 关 鹱态 以发现 “知识 短 缺 ”，产 生 “创 见 意 象 ”，从 而 启 发 与激 活 真 实 数 据库 中相应 的“数 据类 ”，以产 生“定 向发 掘进 程 ” ．KDD 知识 发现 的开 放体 系结 构 ，即在 知 识 发 现 的 摹 础 上 融 入 取 协 唰 机 制 ，用 基 础 知 识库 去 制 约 与 驱 动 知 识 发 现 过 程 改 变 了数 据 发掘 和知 识 发现 的同 有 的运 行 机制 ，形 成 了在 结构 与功 能上 相 对 的与 般 数据发 掘 和知 识发 现 的 的 一 个 开 放 、优 化 扩 体 ． 4 KDD*的实 现 与应 用 4．1KDD 系 统 的实 现 主 要 包 括 如 下 几 个 步 骤 ： (1)预 处理 ．对 原始数据 进行包 括数据 净化 、 数 值化 与特 定转 换 等在 内 的处理 ，形成 发掘 数 据 库 DMDB，以 供 数据 发掘 过程 使 ． (2)聚 焦 ．即从 发掘 数据 库里 进行 数据 的选 择 ．进 行 聚焦 的方 法主 要 是 利用 聚 类 分析 和 判 别分 析 ．指 导数 据 聚焦 的 方式 有 ：(i)通 过 人 机 交 互 由专 家提 出感 兴 趣 的 内容 ，让 专 家 来指 导 数据 发掘 的方 向．(“)利用 启 发式协 调器 进行 定 向 的 数 据 发 掘 ． L3)求 取假 设规 则 ，在 本 系统 中主要 是抽 取 因果关联 规则 ，从而 进… 步丰 富基 础知 识库 ．使 用 的 发掘方 法 是 统计 归纳推 理法 ． 【4)取 序 协同 机制 ．即采 用 中断型 协 调器 、 启 发 型 协 调 器 ，分 别 对 所 获 得 的 假 设 规 则 进 行 处理 和利 用关 联强 度激 发数 据聚 焦进行 数据 发 掘 ， (5)评 价 ．这一 环节主 要用 于对所 获得的假 设 规则 进行 价 值评 定 ，以决 定所 得 的规 则 是 否 存 入知 识 库 ．将 经评 价 认可 的规 则 作为 新 知识 存 入 衍 生 知 识 库 中 ． 4．2 演 示 系统 及应 用 我 们 的 工 作 主 要 侧 重 在 整 个 知 识 发 现 过 程 的机理 、KDD 扩展 性 结 构和 运行 机制 、以及 软 件 系统 的系 列性 开 发 ．其 主 要特 点为 宏观 与 微 观 干门结 合、抽 象 与 具体 相 结 合 、理 论 与应 用 相 结 ，存 此基 础 上 ，我们 经历 了从机 理研 究 、算 法 、 编稃 的全 过程 ，开 发 了覆 盖 与扩 展 了现 存 软 件 所 有 功 能 的 KDD+软件 ，称 为 自主 性 KDD*软 件 ．从 理 论 }基 本解 决 了双 库协 同的机 理 及 其 技 术实 现 ，并 初步用 于 实 际领 域 中 ． 知 识发 现理 论和 方法 的应用 范 围广 阔 ．在 决策 支持 、商 业 行为论 证 、分 析预 测及 科学 研 究 中 表现 出 良好 的应 用 前 景 ．以发 掘 关联 规 则为 例 ，以美 国某 地 区社 会 调 查结 果 的部 分 数据 资 料 来 简 单 介绍 KDDt软件 ．真 实数 据 库 内的属 性 包括 调 查对 象 的工 作状 况 、婚 姻状 况 、初 婚年 龄 、小孩 年龄 、教 育年 限 、年 收入状 况 、自我 感觉 等 l7个 因 素 ． 根 据 专家感 兴 趣方 向进 行数 据 发 掘 (即为 KDD过 程 )首先选 择 专家 感 兴趣 的属 性进 行 数 据 发 掘 ，如下 图所示 的选 择“教育 程 度 ”作 为条 ， “91年 收 入”作 为 结果 ．所 发 现 的知识 表 示 成 州 m0的形 式 ，见 下 图 3． 画 羲圈 ：： i 五 ：幽拜蒜篇童囊器瞥霜面谳丽商翥蔓—一 — 竺—J 巴 图 3 所 获 取 的 规 别 Fig3RulesDiscovery 利用 启发 型 协调器 进 行 自动 发掘关 联规 则 t即 KDD 过 程 )． 启发 型协 调 器 是 根据 知 识 库 中知 识 短 缺 ， 来 自动 发掘 知 识 ，然 后再 通 过领 域 专 家介 入 或 柙 应 的评 价 方法 加 以筛选 ．还 以 卜面 的数 据 库 为例 ，KDD+发 现 结 果如 图 4所 示 ． 由此 可 见 ，新 的动 态知 识 库系 统 较传 统 的 知 识库 内涵 知识 的数 量 和深度 都 有 了较 大 的扩 展 ，有 效 地克 服 了领 域 专 家 的 自身 局 限 ． 维普资讯 http://www.cqvip.com

维告瓷讯http://www.cqvip..com ·88· 北京科技大学学报 2000年第1期 2 I u H.Effective Data Mining Using Neural Networks.JEEE Transactions on Koowledge and Data Engineering,1996. 36957 3 Heckerman D.Bayesian Networks for Data Mining.Data Mining Knowledge Discovery,1997,(1k:79 4 Glymour C.Statistieal Themes and Lessons for Data Min- ing Data Mining Knowledge Discovery,1997,(1):11 5 Y'ang Bingru.KD(D&K and Double-Bases Cooperating Mechanism.Journal of System Engineering and Electro- 色室了 Detwt 〡 ics、1999.101:45 6 Yang Bingru.KDD+Based on Double Base Cooperating 图4假设规叫Fig4 Hypothesis Rule Mechanism and its Realization of Software.Journal of System Engineering and Electronics,1999,1014):521 1)当将以上程序用丁故障诊断时，可发现 7杨炳儒.广义细胞自动机与广义归纳逻辑因果模型 “故障链"，即可寻求出产生故障的根本原因，有 北京科技大学学，1997，l9(4:403 重要的实用意义， 8杨炳儒.数据发掘与数据库中的知识发现，北京科技 (2)将以上程序用各个领域的知识发现时， 学学报，I999,2I(2):202 可形成若干用于决策的规则 9枸炳儒，类因果关系定性推理方法及其应用.离散 故学及其应用论文集.北京：北京大学出版社.1994 参考文献 0杨炳橘.智能型多层次归纳推理摸型，国家补会科学 I Piatelsky-Shapiro G,Matheus C.Knowledge Discovery 基金与“863"项月专著归纳逻辑与人工智能，北京： Workbench for Exploring Business Databases.Interna- 中国纺大学H版社，1995.320 tional Journal of Inteltigent Systems.1992,7(7):675 Expanded Researching on Knowledge Discovery System YANG Bingru.ZHANG Decheng Informarion Engincering School.UST Beijing,Beijing 100083.China ABSTRACT Based on the summarizing and analyzing of the theory of knowledge discovery in database and the actuality of technological method,the trend of knowledge discovery in discussed.and introduced the mechanism of total data mining process,researching in expansible structure and algorithm of KDD.and seri- ally developing of software,according to the theory of double base cooperation. KEYWORDS data mining;knowledge discovery:double base cooperation

·88· 北 京 科 技 大 学 学 报 图 4 假 设规 则 l~ig4HypothesisRule (1)当将 以上程 序 用 丁故障诊 断 时 ，可发 现 “故 障链 ”，即可寻 求 出产 生 故障 的根 本 原 因 ，有 重 要 的实用 意义 ． (2)将 以上 程序 用 各个 领 域 的知 识 发现 时 ， 可 形 成 若 干 用 于 决 策 的 规 则 ． 参 考 文 献 Pimetsk'y—Shapiro G． M a血eusC．Kno,~|edgeDiscovery W orkbench forExploring BusinessDatabases lntem a￾tionalJournalofIntelligentSy~ems，1992，7(7)：675 2000年 第 1期 2 IuH EfectiveDataM iningUsingNeuralNetworks IEEE TransactionsonKnowledgeand Data Engineering，1996， 8(6、：957 3 Heckerm anD BayesianNetworksforDataM ining Data M ining& KnowledgeDiscovery,I997，I】)：79 4 GlymourC StatisticalThemesandLessonsfo rData M in￾ing Data M ining& KnowledgeDiscovery,I997，(I)：I1 5 "rang Bingru．KD(D&K)an dDouble-BasesCooperating M echanism Jouraa[ofSystem Ertgiaeering and Electro— nics，I999，Ioo)：45 6 "rang Bingru KDD Based on Double Base Cooperating M echanism and itsRealization ofSoftware Journ alof System Engineeringan dElectronics I999，10{4)：521 7 杨 炳 儒 ．广 义 细 胞 自动 机 与 广 义 归 纳逻 辑 因果 模 型 ． 北 京 科技 大学 学 报 ，1997，19(4)：403 8 杨炳 儒 数 据发 掘 与 数 据 库 中 的 知 识 发现 ．北 京 科技 大学 学撒 ，1999，21(2)：202 9 杨 炳 儒 ． 类 因果 关 系 定性 推 理 方 法 及 其 应 用 ．离散 数 学 及 其 应 用 论 文集 ．北京 ：北 京 大 学 舨 社 ，1994 10畅炳懦．智 能型 多层改归纳推理模 型．国家社 会科学 金与 “863”项 目专 著 《归纳 逻辑 与人 工智 能》 北京 ： 中 国纺 大 学 版 社 ，1995320 ExpandedResearchingonKnow ledgeDiscovery System YANG BingrH， ZHAN G Dezheng InformationEngineeringSchoo1．USFBeUing，Beiing100083，China ABSTRACT Based onthesum marizingand analyzing oftheth eory ofknowledgediscovery in database and theactuality oftechnologicalm ethod，th etrendofkn owledgediscovery indiscussed,and in troducedthe mechanism oftota ldata m in ingprocess，researchinginexpansiblestructureandalgorithm ofKDD ，an dseri￾ally developingofsoftwar e，according totheth eory ofdoublebas ecooperation． KEYV~ORDS datam ining；kn owledgediscovery ；doublebasecooperation 维普资讯 http://www.cqvip.com