中文模板

Transcription

1 ISSN , CODEN RUXUEW Journal of Software, Vol.19, No.2, February 2008, pp DOI: /SP.J Tel/Fax: by Journal of Software. All rights reserved. 一 种 基 于 语 义 及 统 计 分 析 的 Deep Web 实 体 识 别 机 制 寇 月 1+, 申 德 荣 1, 李 冬 2 1, 聂 铁 铮 1 ( 东 北 大 学 信 息 科 学 与 工 程 学 院, 辽 宁 沈 阳 ) 2 ( 东 软 集 团 有 限 公 司 商 用 软 件 事 业 部, 辽 宁 沈 阳 ) A Deep Web Entity Identification Mechanism Based on Semantics and Statistical Analysis KOU Yue 1+, SHEN De-Rong 1, LI Dong 2, NIE Tie-Zheng 1 1 (College of Information Science and Engineering, Northeastern University, Shenyang , China) 2 (Business Software Division, Neusoft Group Ltd., Shenyang , China) + Corresponding author: Phn: , Fax: , kouyue@ise.neu.edu.cn, Kou Y, Shen DR, Li D, Nie TZ. A deep Web entity identification mechanism based on semantics and statistical analysis. Journal of Software, 2008,19(2): Abstract: According to analyzing the traditional entity identification methods, a deep Web entity identification mechanism based on semantics and statistical analysis (SS-EIM) is presented in this paper, which includes text matching model, semantics analysis model and group statistics model. Also a three-phase gradual refining strategy is adopted, which includes text initial matching, representation relationship abstraction and group statistics analysis. Based on the text characteristics, semantic information and constraints, the identification result is revised continuously to improve the accuracy. By performing the self-adaptive knowledge maintenance strategy, the content of representation relationship knowledge database can be more complete and effective. The experiments demonstrate the feasibility and effectiveness of the key techniques of SS-EIM. Key words: deep Web; data integration; entity identification; data deduplication; representation consolidation 摘 要 : 分 析 了 常 见 的 实 体 识 别 方 法, 提 出 了 一 种 基 于 语 义 及 统 计 分 析 的 实 体 识 别 机 制 (deep Web entity identification mechanism based on semantics and statistical analysis, 简 称 SS-EIM), 能 够 有 效 解 决 Deep Web 数 据 集 成 中 数 据 纠 错 消 重 及 整 合 等 问 题.SS-EIM 主 要 由 文 本 匹 配 模 型 语 义 分 析 模 型 和 分 组 统 计 模 型 组 成, 采 用 文 本 粗 略 匹 配 表 象 关 联 关 系 获 取 以 及 分 组 统 计 分 析 的 三 段 式 逐 步 求 精 策 略, 基 于 文 本 特 征 语 义 信 息 及 约 束 规 则 来 不 断 精 化 识 别 结 果 ; 根 据 可 获 取 的 有 限 的 实 例 信 息, 采 用 静 态 分 析 动 态 协 调 相 结 合 的 自 适 应 知 识 维 护 策 略, 构 建 和 完 善 表 象 关 联 知 识 库, 以 适 应 Web 数 据 的 动 态 性 并 保 证 表 象 关 联 知 识 的 完 备 性. 通 过 实 验 验 证 了 SS-EIM 中 所 采 用 的 关 键 技 术 的 可 行 性 和 有 效 性. 关 键 词 : deep Web; 数 据 集 成 ; 实 体 识 别 ; 数 据 消 重 ; 表 象 整 合 中 图 法 分 类 号 : TP393 文 献 标 识 码 : A 随 着 信 息 技 术 的 不 断 发 展,Web 上 的 信 息 量 呈 爆 炸 性 增 长. 按 照 所 蕴 含 信 息 深 度 的 不 同, 可 以 将 Web 划 分 为 Supported by the National Natural Science Foundation of China under Grant No ( 国 家 自 然 科 学 基 金 ) Received ; Accepted

2 寇 月 等 : 一 种 基 于 语 义 及 统 计 分 析 的 Deep Web 实 体 识 别 机 制 195 Surface Web 和 Deep Web 两 大 类. 统 计 数 据 表 明 :Deep Web 蕴 含 的 信 息 量 及 数 据 访 问 量 等 都 远 远 高 于 Surface Web [1]. 因 此, 随 着 Web 数 据 库 的 不 断 增 长, 能 够 自 动 获 取 蕴 含 在 Deep Web 中 的 数 据 资 源 并 对 其 进 行 大 规 模 集 成 显 得 尤 为 重 要. 然 而, 数 据 源 内 部 及 数 据 源 之 间 的 数 据 往 往 存 在 数 据 不 一 致 及 数 据 重 复 等 问 题, 如 果 不 对 这 些 低 质 量 的 数 据 进 行 预 处 理 而 直 接 作 为 查 询 结 果 返 回, 将 严 重 影 响 Deep Web 的 查 询 效 率. 利 用 实 体 识 别 技 术 可 以 对 数 据 集 成 中 产 生 的 重 复 记 录 进 行 检 测 并 整 合, 有 效 地 消 除 数 据 源 内 部 以 及 数 据 源 之 间 的 数 据 不 一 致 性. 以 论 文 检 索 网 站 ACM 和 DBLP 为 例, 若 要 查 询 John Allen 发 表 的 论 文 信 息, 两 个 网 站 上 的 结 果 数 据 如 图 1 所 示. 从 图 1 中 可 以 看 出, 由 于 拼 写 方 式 或 定 义 格 式 的 不 同, 无 论 是 数 据 源 内 部 还 是 数 据 源 之 间 都 具 有 不 同 表 现 形 式 但 对 应 于 同 一 事 物 的 结 果 数 据. 我 们 将 与 现 实 世 界 一 一 对 应 的 事 物 或 事 件 称 为 实 体, 例 如 姓 名 为 John Allen 的 某 个 具 体 的 人 ; 将 实 体 的 不 同 表 现 形 式 定 义 为 实 体 的 表 象, 例 如 可 以 将 这 个 人 表 示 成 John Allen,J. Allen 等. 如 果 直 接 将 这 些 表 象 作 为 结 果 返 回, 则 无 疑 将 增 加 用 户 对 其 进 一 步 分 类 筛 选 的 负 担. 因 此, 为 了 提 高 结 果 数 据 的 质 量, 需 要 事 先 通 过 实 体 识 别 技 术 将 这 些 表 象 按 照 实 体 类 别 聚 类, 并 将 聚 类 结 果 以 知 识 的 形 式 存 储, 以 指 导 实 际 查 询 中 的 资 源 整 合. 针 对 此 例, 就 是 要 判 断 :DBLP 网 站 中 的 表 象 r 2,r 3 与 r 4 是 否 代 表 同 一 个 人 ;ACM 中 r 1 对 应 于 DBLP 中 r 2,r 3 与 r 4 的 哪 个 人 的 信 息. 因 此, 通 过 实 体 识 别 技 术 为 用 户 提 供 高 质 量 的 集 成 结 果 是 Deep Web 数 据 集 成 中 必 不 可 少 的 一 个 过 程. r 2: J. Allen r 1: John Allen r 4: John G. Allen r 3: John A. Allen Fig.1 ACM DBLP Demonstration of data inconsistency existing in a single data source or among multiple data sources 图 1 存 在 于 一 个 数 据 源 内 部 或 多 数 据 源 之 间 的 数 据 不 一 致 性 示 例 然 而, 目 前 针 对 Web 数 据 实 体 识 别 的 研 究 与 开 发 还 处 于 起 步 阶 段, 大 多 数 工 作 都 是 围 绕 静 态 环 境 来 构 建 实 体 识 别 系 统 ( 如 数 据 挖 掘 领 域 中 数 据 清 理 问 题 的 研 究 [2] ), 与 这 些 实 体 识 别 系 统 相 比,Deep Web 实 体 识 别 的 研 究 更 具 挑 战 性, 主 要 体 现 在 以 下 几 个 方 面 : 当 前 大 多 数 实 体 识 别 系 统 仅 单 一 地 考 虑 文 本 属 性 特 征 或 上 下 文 语 义 信 息 来 衡 量 数 据 间 的 相 似 性, 没 有 对 聚 类 结 果 进 行 逐 步 求 精 处 理, 识 别 的 准 确 性 难 以 保 证, 因 此, 已 有 的 识 别 策 略 有 待 改 进 ; 蕴 含 在 Deep Web 中 的 数 据 资 源 具 有 较 强 的 动 态 性, 如 果 按 照 传 统 的 数 据 挖 掘 等 方 法 将 获 取 的 所 有 表 象 关 联 信 息 保 存 在 数 据 仓 库 中, 则 具 有 相 对 静 态 特 性 的 数 据 仓 库 的 内 容 不 能 实 时 地 反 映 数 据 的 动 态 变 化, 因 此, 传 统 的 数 据 清 理 方 法 对 于 动 态 性 强 的 数 据 资 源 并 不 适 用 ; 由 于 Deep Web 数 据 量 巨 大, 若 对 所 有 数 据 源 进 行 分 析 识 别, 势 必 影 响 识 别 的 处 理 效 率, 相 反, 若 只 分 析 部 分 信 息, 表 象 关 联 知 识 的 完 备 性 将 会 受 到 影 响, 因 此, 样 本 数 据 量 的 大 小 难 以 确 定. 综 上 所 述, 要 想 有 效 地 整 合 Deep Web 上 的 数 据 就 必 须 解 决 以 上 问 题. 本 文 将 着 重 解 决 的 问 题 是 : 在 表 象 模 式 已 知 的 前 提 下, 如 何 基 于 实 例 信 息 来 分 析 并 获 取 表 象 关 联 知 识, 如 何 确 保 这 些 知 识 具 有 较 高 的 完 备 性 与 准 确 性, 以 及 如 何 保 证 表 象 关 联 知 识 库 中 的 内 容 能 够 适 应 于 Deep Web 环 境 中 数 据 的 动 态 性. 1 相 关 工 作 目 前, 关 于 实 体 识 别 技 术 的 研 究 主 要 集 中 在 两 方 面 : 一 方 面 是 基 于 实 体 的 属 性 文 本 特 征 进 行 实 体 识 别 (feature-based similarity, 简 称 FBS 方 法 ), 侧 重 于 研 究 文 本 相 似 函 数 的 设 置 ( 包 括 函 数 定 义 选 取 和 相 关 阈 值 的 确

3 196 Journal of Software 软 件 学 报 Vol.19, No.2, February 2008 定 ) [3 7] [8 10] [11] 属 性 权 重 的 选 取 以 及 相 关 优 化 措 施 等 ; 另 一 方 面 是 基 于 实 体 上 下 文 语 义 信 息 或 特 定 领 域 知 识, 利 用 数 据 挖 掘 等 方 法 进 行 实 体 识 别, 侧 重 于 研 究 语 义 关 联 的 表 示 方 式 及 计 算 方 法 [12 17]. 其 中, 基 于 属 性 特 征 进 行 实 体 识 别 的 相 关 工 作 包 括 :Bilenko [3] 通 过 采 用 机 器 学 习 方 法 SVM 自 适 应 地 选 取 最 佳 文 本 相 似 度 算 法, 以 满 足 不 同 领 域 数 据 的 特 点 及 需 求 ;Cohen [4] 分 析 并 比 较 了 多 种 字 符 串 匹 配 函 数 ( 如 编 辑 距 [5] 离 Token 距 离 Levenstein 距 离 等 ), 并 从 中 选 取 最 佳 函 数 来 衡 量 属 性 特 征 的 相 似 性 ;Zhu 等 人 根 据 关 系 表 的 决 定 属 性 值 划 分 记 录 集, 并 在 每 个 记 录 集 内 应 用 动 态 优 先 队 列 聚 类 算 法 和 合 并 逆 序 算 法 来 检 测 数 据 库 中 的 相 似 [6] 重 复 记 录 ;Ling 等 人 将 Web 页 面 中 的 数 据 划 分 成 记 录 块, 基 于 记 录 块 间 的 文 本 相 似 性 来 判 断 不 同 数 据 源 上 的 记 录 是 否 重 复, 并 通 过 迭 代 训 练 来 确 定 相 关 参 数 的 阈 值. 以 上 工 作 侧 重 于 研 究 相 似 函 数 的 定 义 选 取 及 阈 值 设 [8] 置, 除 此 之 外, 文 本 匹 配 中 属 性 权 重 的 选 取 及 相 关 优 化 措 施 的 采 用 也 越 发 引 起 关 注, 例 如,Wang 等 人 利 用 梯 度 递 减 算 法 为 数 据 的 描 述 属 性 赋 予 权 值, 并 基 于 属 性 权 重 学 习 算 法 和 聚 类 算 法 将 相 似 的 数 据 聚 类 ;Chaudhuri [11] 提 出 一 种 高 效 的 重 复 记 录 模 糊 检 测 算 法, 通 过 采 用 特 定 索 引 排 序 等 优 化 措 施 有 效 地 搜 索 出 与 当 前 元 组 最 相 似 的 K 个 关 联 元 组. 基 于 上 下 文 语 义 信 息 或 特 定 领 域 知 识 进 行 实 体 识 别 的 相 关 工 作 包 括 :Chen [12] 将 表 象 间 的 语 义 关 联 以 图 形 化 表 示, 并 应 用 图 分 割 技 术 对 表 象 集 进 行 聚 类 分 组, 每 组 由 对 应 于 同 一 实 体 的 表 象 集 组 成 ;Thor [13] 建 立 了 一 个 灵 活 的 表 象 匹 配 框 架 MOMA, 通 过 该 框 架 采 用 不 同 的 表 象 匹 配 算 法 获 取 表 象 关 联 集, 并 将 其 合 成, 从 而 计 算 表 象 间 [14] 的 关 联 强 度 ;Nie 等 人 利 用 上 下 文 在 互 联 网 共 同 出 现 的 情 况, 通 过 计 算 网 页 的 URL 距 离 来 计 算 不 同 表 象 的 互 联 网 关 联 强 度. 以 上 工 作 大 多 数 是 基 于 静 态 环 境 构 建 的 实 体 识 别 系 统, 不 能 较 好 地 适 应 Deep Web 环 境 下 数 据 资 源 的 动 态 性 并 保 证 表 象 关 联 知 识 的 完 备 性 ; 另 外, 这 些 实 体 识 别 系 统 或 者 基 于 属 性 文 本 特 征, 或 者 基 于 上 下 文 信 息 来 识 别 数 据 间 的 相 似 性, 缺 乏 对 聚 类 结 果 进 行 逐 步 求 精 的 过 程, 因 此, 单 一 地 应 用 实 体 属 性 特 征 或 上 下 文 信 息 来 进 行 实 体 识 别 将 会 影 响 识 别 结 果 的 准 确 性. 为 此, 本 文 探 讨 了 一 种 基 于 语 义 及 统 计 分 析 的 Deep Web 实 体 识 别 机 制, 主 要 贡 献 在 于 : 提 出 了 SS-EIM(deep Web entity identification mechanism based on semantics and statistical analysis) 的 模 型, 其 中 包 括 文 本 匹 配 模 型 语 义 分 析 模 型 和 分 组 统 计 模 型, 能 够 有 效 解 决 Deep Web 数 据 集 成 中 数 据 纠 错 消 重 及 整 合 等 问 题 ; 提 出 了 文 本 粗 略 匹 配 表 象 关 联 关 系 获 取 以 及 分 组 统 计 分 析 的 三 段 式 逐 步 求 精 策 略, 有 效 地 提 高 了 实 体 识 别 的 准 确 性 ; 基 于 有 限 的 实 例 信 息, 采 用 静 态 分 析 动 态 协 调 相 结 合 的 自 适 应 知 识 维 护 策 略, 构 建 和 完 善 表 象 关 联 知 识 库, 能 够 适 应 Web 数 据 的 动 态 性 并 保 证 表 象 关 联 知 识 的 完 备 性 ; 通 过 实 验 验 证 了 SS-EIM 中 所 采 用 的 关 键 技 术 的 可 行 性 和 有 效 性, 与 其 他 实 体 识 别 策 略 相 比,SS-EIM 在 知 识 准 确 性 知 识 完 备 性 等 性 能 上 具 有 一 定 的 优 势. 本 文 第 2 节 介 绍 SS-EIM 的 模 型 ; 第 3 节 介 绍 文 本 匹 配 模 型 ; 第 4 节 提 出 基 于 上 下 文 的 语 义 分 析 模 型 ; 第 5 节 介 绍 基 于 约 束 规 则 的 分 组 统 计 模 型 ; 第 6 节 给 出 三 段 式 逐 步 求 精 算 法 以 及 性 能 分 析 ; 第 7 节 讨 论 表 象 关 联 知 识 维 护 策 略 ; 第 8 节 给 出 相 关 实 验 结 果 并 进 行 分 析 ; 第 9 节 总 结 全 文. 2 SS-EIM 的 模 型 通 过 预 获 取 的 有 限 的 实 例 信 息 可 以 分 析 和 推 导 出 实 例 间 的 关 联 关 系 并 构 建 表 象 关 联 知 识 库, 利 用 表 象 关 联 知 识 可 以 有 效 地 指 导 实 时 查 询 中 资 源 选 择 消 重 及 数 据 整 合 等 操 作. 本 节 首 先 介 绍 SS-EIM 的 模 型, 然 后 针 对 模 型 中 涉 及 的 相 关 概 念 给 出 定 义. SS-EIM 的 模 型 如 图 2 所 示. 其 中,R 是 有 限 数 据 集 D 中 的 所 有 表 象 r i 构 成 的 集 合, 记 为 {r 1,r 2,,r R }. 将 D 中 与 现 实 世 界 一 一 对 应 的 实 体 集 记 为 E={e 1,e 2,,e E },e i 是 由 对 应 于 同 一 实 体 的 表 象 所 组 成 的 表 象 集. 实 体 识 别 的 任 务 就 是 给 定 一 个 表 象 集 R, 通 过 匹 配 推 理 及 分 析 等 过 程, 将 对 应 于 同 一 实 体 的 表 象 进 行 聚 类, 最 终 得 到 实 体 集 E, R E. 实 际 上,E 是 理 想 情 况 下 的 实 体 识 别 结 果, 由 于 Web 表 现 形 式 的 多 样 性 以 及 数 据 的 复 杂 性 很 难 将 R 准 确 无 误 地 转 化 成 E. 因 此, 可 以 利 用 SS-EIM 生 成 的 聚 类 集 C={c 1,c 2,,c C } 来 近 似 地 表 示 实 体 集 E, C E.SS-EIM 模 型 首 先 将 模 式 已 知 的 表 象 集 R 作 为 待 识 别 数 据, 基 于 文 本 匹 配 模 型 语 义 分 析 模 型 和 分 组 统 计 模 型 对 这 些 实 例

4 寇 月 等 : 一 种 基 于 语 义 及 统 计 分 析 的 Deep Web 实 体 识 别 机 制 197 信 息 进 行 静 态 分 析, 分 别 生 成 一 系 列 文 本 相 似 集 语 义 相 似 集 和 满 足 约 束 集, 并 形 成 初 始 的 表 象 关 联 知 识 ; 然 后, 基 于 知 识 维 护 模 型 以 及 用 户 的 实 际 查 询 结 果 对 当 前 表 象 关 联 知 识 库 中 的 内 容 进 行 动 态 协 调, 使 其 不 断 被 扩 充 和 完 善, 以 保 证 表 象 关 联 知 识 的 完 备 性 和 有 效 性. Gradual refining R={r 1,,r R } Text similar set Semantic similar set Constraints satisfied set Representation relationship knowledge C={c 1,c 2,,c C } Text matching model Semantic analysis model Statistical grouping model Static analysis Fig.2 SS-EIM model 图 2 SS-EIM 模 型 Knowledge maintenance model Dynamic coordination 文 本 匹 配 模 型 通 过 比 较 属 性 取 值 的 文 本 相 似 度 来 检 测 由 数 据 格 式 拼 写 错 误 等 因 素 造 成 的 数 据 不 一 致 性. 但 是, 文 本 匹 配 模 型 只 是 通 过 字 面 粗 略 地 对 表 象 进 行 聚 类, 而 文 本 特 征 相 似 的 表 象 很 可 能 代 表 不 同 的 实 体, 因 此 语 义 分 析 模 型 通 过 上 下 文 语 义 信 息 来 进 一 步 提 高 聚 类 的 准 确 性. 除 了 分 析 字 符 串 类 型 的 属 性 及 其 语 义 关 联 以 外, 分 组 统 计 模 型 还 用 来 对 数 值 型 属 性 进 行 统 计 分 析 以 提 高 实 体 识 别 的 准 确 性. 为 了 使 表 象 关 联 知 识 库 的 内 容 适 应 Web 数 据 的 动 态 性, 知 识 维 护 模 型 通 过 收 集 实 际 查 询 过 程 中 的 动 态 结 果 数 据, 以 此 作 为 基 准 来 实 时 检 测 表 象 关 联 知 识 库 的 完 备 性 和 有 效 性, 从 而 对 表 象 关 联 知 识 库 中 的 内 容 不 断 进 行 调 整 并 完 善. 从 SS-EIM 模 型 中 可 以 看 出, 文 本 相 似 集 语 义 相 似 集 以 及 满 足 约 束 集 的 生 成 过 程 是 对 表 象 聚 类 集 逐 步 求 精 的 过 程, 将 其 分 别 记 为 S txt,s sem 和 S con, 三 者 的 关 系 为 S txt [r i ] S sem [r i ] S con [r i ], 现 给 出 具 体 定 义. 定 义 1( 文 本 相 似 集 S txt [r i ]). 基 于 实 体 的 属 性 取 值 利 用 文 本 相 似 函 数 Sim 计 算 表 象 间 的 相 似 度, 文 本 相 似 集 由 文 本 相 似 度 达 到 文 本 相 似 阈 值 σ txt 的 表 象 以 及 与 该 表 象 具 有 异 名 同 义 或 层 次 包 含 关 系 的 表 象 S txt_extend [r i ] 所 组 成, 具 体 定 义 为 { σ } _ S [ r] = r r R r ( r S [ r] Sim( r, r ) > ) S [ r] (1) txt i j j k k txt i j k txt txt Extend i 定 义 2( 语 义 相 似 集 S sem [r i ]). 依 据 语 义 关 联 进 一 步 分 析 每 个 文 本 相 似 集, 语 义 相 似 集 由 表 象 间 关 联 强 度 CS 大 于 语 义 相 似 阈 值 σ sem 的 表 象 所 组 成, 具 体 定 义 为 { } S [ r] = r r S [ r] r ( r S [ r] CS( r r ) > σ ) (2) sem i j j txt i k k sem i j k sem 定 义 3( 满 足 约 束 集 S con [r i ]). 基 于 约 束 规 则 检 测 语 义 相 似 集 的 聚 类 准 确 性, 满 足 约 束 集 由 语 义 相 似 集 内 满 足 约 束 规 则 的 表 象 所 组 成, 具 体 定 义 为 { } S [ r] = r r S [ r] S [ r] 满 足 约 束 规 则 (3) con i j j sem i con i 其 中, 语 义 关 联 是 指 存 在 于 表 象 间 直 接 或 间 接 的 上 下 文 联 系, 关 联 强 度 是 对 语 义 关 联 强 弱 的 量 化 表 示. 以 图 1 为 例, 若 r 1 与 r 2 有 相 同 的 合 作 者, 则 认 为 表 象 r 1 与 r 2 之 间 存 在 语 义 关 联. 约 束 规 则 是 指 针 对 某 领 域 中 表 象 的 属 性 聚 集 值 所 定 义 的 约 束 条 件. 例 如, 若 图 1 中 ACM 网 站 的 r 1 与 DBLP 网 站 的 r 2,r 3 对 应 同 一 个 人, 那 么 该 作 者 在 两 个 网 站 中 被 收 录 的 文 章 总 数 应 相 差 不 多, 可 以 将 其 作 为 约 束 规 则 来 进 一 步 检 测 聚 类 的 准 确 性. 3 文 本 匹 配 模 型 在 特 定 的 领 域 范 围 内, 对 应 于 相 同 实 体 的 表 象 往 往 具 有 相 似 的 属 性 特 征. 因 此, 本 文 应 用 文 本 匹 配 模 型 对 实 [18] 例 信 息 进 行 文 本 粗 略 匹 配, 借 鉴 文 本 编 辑 距 离 函 数 来 衡 量 表 象 间 属 性 级 相 似 度, 并 采 用 多 属 性 合 成 函 数 将 多 个 属 性 级 相 似 度 进 行 合 并, 进 而 衡 量 表 象 级 的 相 似 程 度, 最 终 将 具 有 相 似 文 本 特 征 的 表 象 聚 成 一 类, 形 成 一 系 列 文 本 相 似 集. 具 体 步 骤 如 下 : 步 骤 1. 借 鉴 已 有 的 属 性 选 择 算 法 [8 10], 利 用 近 似 函 数 依 赖 关 系 来 量 化 实 体 描 述 属 性 a 1 ~a n 的 重 要 度, 并 赋

5 198 Journal of Software 软 件 学 报 Vol.19, No.2, February 2008 予 不 同 的 权 值 w 1 ~w n, 具 体 定 义 如 公 式 (4) 所 示. 其 中, â 表 示 ai 与 其 他 属 性 的 组 合 属 性 ; error aˆ a ) 表 示 为 了 使 ( j 近 似 函 数 依 赖 aˆ a 成 立, 需 要 从 关 系 中 移 除 的 记 录 占 整 个 关 系 的 最 小 比 例. error aˆ a ) 越 小, 说 明 关 系 中 满 j 足 该 函 数 依 赖 的 记 录 就 越 多,a i 的 影 响 力 就 越 大, 因 此 被 赋 予 较 高 的 权 值. n 1 error(ˆ a a j ) wi = aˆ j= 1 ( j 步 骤 2. 针 对 每 个 表 象 对 (r i 与 r j ) 中 的 各 个 属 性 a k (k=1~n), 分 别 基 于 文 本 编 辑 距 离 函 数 计 算 表 象 间 属 性 级 的 相 似 度 Sim(r i.a k,r j.a k ), 具 体 定 义 如 下 : ed( ri. ak, rj. ak) Sim( ri. ak, rj. ak) = 1 max{ ra., r. a (5) } i k j k 步 骤 3. 基 于 多 属 性 合 成 函 数 及 属 性 权 重 将 多 个 属 性 级 的 相 似 度 进 行 合 并, 从 而 计 算 出 表 象 级 的 文 本 相 似 度 Sim(r i,r j )( 如 公 式 (6) 所 示 ). 最 终 将 满 足 文 本 相 似 阈 值 的 所 有 聚 类 进 行 合 并, 生 成 一 系 列 初 始 文 本 相 似 集. Sim( r, r ) = Com( Sim( r. a, r. a ),..., Sim( r. a, r. a ),..., Sim( r. a, r. a )) i j i 1 j 1 i k j k i n j n n = w Sim( r. a, r. a ) k= 1 k i k j k 步 骤 4. 针 对 每 个 初 始 文 本 相 似 集, 基 于 辅 助 信 息 库, 如 Wordnet, 将 与 其 存 在 异 名 同 义 及 层 次 包 含 关 系 的 表 象 S txt_extend [r i ] 扩 充 到 其 中, 以 保 证 最 终 生 成 的 文 本 相 似 集 具 有 较 高 的 完 备 性 和 准 确 性. 由 此 可 见, 文 本 粗 略 匹 配 得 到 的 是 从 属 性 特 征 上 具 有 相 似 性 的 表 象 聚 类 集, 然 而, 表 象 的 外 在 表 现 形 式 不 足 以 作 为 聚 类 的 判 定 依 据. 例 如,J. Smith 既 可 以 表 示 John Smith, 又 可 以 表 示 Jane Smith, 虽 然 基 于 文 本 匹 配, 这 些 表 象 可 能 被 聚 集 在 同 一 个 文 本 相 似 集 内, 但 它 们 分 别 对 应 不 同 的 实 体. 因 此, 文 本 匹 配 只 是 基 于 属 性 特 征 对 表 象 集 粗 略 地 划 分, 其 准 确 性 难 以 保 证. 但 是, 利 用 文 本 匹 配 模 型 可 以 使 后 续 的 操 作 在 较 小 的 数 据 空 间 上 进 行, 从 而 降 低 了 实 体 识 别 的 执 行 代 价. 4 语 义 分 析 模 型 语 义 分 析 模 型 用 来 对 每 个 文 本 相 似 集 的 表 象 进 行 语 义 关 联 分 析, 将 具 有 语 义 相 似 性 的 表 象 进 行 聚 类, 从 而 在 属 性 文 本 匹 配 的 基 础 上 提 高 了 实 体 识 别 的 准 确 性. 首 先, 基 于 表 象 的 上 下 文 信 息 将 其 语 义 关 联 用 表 象 关 联 图 来 表 示 ; 然 后, 针 对 表 象 关 联 图 中 表 象 间 的 多 条 路 径 进 行 分 析, 并 从 中 选 取 进 行 关 联 强 度 运 算 的 最 佳 路 径 ; 最 后, 计 算 表 象 间 的 关 联 强 度, 将 关 联 强 度 大 于 语 义 相 似 阈 值 的 表 象 聚 成 一 类 而 形 成 语 义 相 似 集. 4.1 语 义 关 联 规 则 针 对 某 一 领 域, 对 应 于 同 一 实 体 的 表 象 之 间 往 往 存 在 着 直 接 或 间 接 的 语 义 关 联, 利 用 这 些 关 联 信 息 可 以 提 高 实 体 识 别 的 准 确 性. 因 此, 需 要 事 先 挖 掘 出 该 领 域 表 象 间 的 语 义 关 联 规 则. 设 待 聚 类 表 象 集 为 R, 本 文 首 先 采 取 人 工 筛 选 的 方 式 从 R 中 确 定 一 系 列 标 准 聚 类 集 c, 其 中 每 个 c 由 对 应 同 一 实 体 的 表 象 组 成 ; 然 后, 将 R 与 该 领 域 内 其 他 表 象 集 R k 分 别 组 合 形 成 一 系 列 候 选 关 联 R_R k, 借 鉴 数 据 挖 掘 中 的 Apriori 算 法 [19,20], 针 对 每 一 种 候 选 关 联 R_R k, 挖 掘 所 有 标 准 聚 类 集 中 的 频 繁 2 项 集 {r i,r j } 并 计 算 其 支 持 度 Support(r i r j ),R_R k 的 支 持 度 由 这 些 频 繁 2 项 集 的 支 持 度 聚 集 而 成 ( 如 公 式 (7) 所 示 ); 最 后, 选 取 支 持 度 较 高 的 候 选 关 联 以 及 它 们 的 有 限 次 迭 加 作 为 实 体 识 别 的 语 义 关 联 规 则. Support( R _ R ) = Support( r r ) k i j ri, rj R. c rk ( rk Rk ri rk rj) { ri, rj} 是 频 繁 2项 集 以 论 文 检 索 领 域 为 例, 若 待 聚 类 的 表 象 集 是 作 者 表 象 集 合, 则 该 领 域 内 的 关 联 组 合 包 括 作 者 _ 合 作 者 作 者 _ 会 议 作 者 _ 出 版 日 期 等 候 选 关 联. 若 存 在 某 合 作 者 表 象 r k, 同 时 与 标 准 聚 类 集 中 的 两 个 作 者 表 象 r i,r j 具 有 合 作 关 系 r i r k r j, 且 该 现 象 频 繁 发 生, 则 作 者 _ 合 作 者 关 联 的 支 持 度 较 高, 因 而 将 该 关 联 作 为 实 体 识 别 的 语 义 关 联 规 则. 以 此 类 推, 针 对 该 领 域 的 特 征, 最 终 确 定 如 下 语 义 关 联 规 则 作 为 构 建 表 象 关 联 图 的 依 据. 合 作 者 关 联 ( 作 者 _ 合 作 者 ): 若 两 个 表 象 的 合 作 者 集 合 存 在 交 集, 则 认 为 该 表 象 间 存 在 合 作 者 关 联. (4) (6) (7)

6 寇 月 等 : 一 种 基 于 语 义 及 统 计 分 析 的 Deep Web 实 体 识 别 机 制 199 出 处 关 联 ( 作 者 _ 会 议 ): 若 两 个 表 象 出 自 同 一 个 会 议 或 出 版 机 构, 则 认 为 该 表 象 间 存 在 出 处 关 联. 混 合 关 联 : 表 象 间 经 过 合 作 者 关 联 或 出 处 关 联 的 有 限 次 迭 加 而 建 立 的 关 联. 4.2 表 象 关 联 图 基 于 这 些 预 先 挖 掘 的 语 义 关 联 规 则, 可 以 检 测 出 表 象 间 的 关 联 关 系, 将 这 些 信 息 以 图 形 化 表 示 出 来 的 过 程 就 是 构 建 表 象 关 联 图 (representation relationship graph, 简 称 RRG) 的 过 程.RRG 由 节 点 集 合 V 和 边 集 合 E 组 成,V 用 来 表 示 实 体 的 不 同 表 象, 包 括 文 本 相 似 集 内 的 表 象 以 及 与 之 具 有 语 义 关 联 的 所 有 表 象, 如 上 例 中 的 作 者 和 会 议 等 ;E 用 来 表 示 表 象 间 存 在 的 语 义 关 联, 如 上 例 中 的 合 作 者 关 联 出 处 关 联 等. 表 象 关 联 图 类 似 于 关 系 数 据 库 中 的 实 体 联 系 模 型, 不 同 的 是, 表 象 关 联 图 表 示 的 是 实 例 ( 表 象 ) 间 的 关 联 信 息, 因 此, 可 以 将 表 象 关 联 图 看 成 是 对 实 体 联 系 模 型 的 实 例 化 表 示. 针 对 论 文 检 索 领 域 某 一 文 本 相 似 集 内 的 两 个 表 象 John Allen 与 J. Allen 构 建 的 表 象 关 联 图 如 图 3 所 示, 其 中, 节 点 分 为 两 类, 分 别 表 示 作 者 表 象 和 会 议 表 象 ; 同 样, 按 照 表 象 间 关 联 类 型 的 不 同, 边 也 分 为 合 作 者 关 联 与 出 处 关 联. 具 体 来 说, 图 3(a) 表 示 John Allen 的 合 作 者 Helen 同 样 也 是 J. Allen 的 合 作 者, 则 认 为 John Allen 与 J. Allen 存 在 合 作 者 关 联 ; 图 3(b) 表 示 John Allen 发 表 的 某 篇 文 章 与 J. Allen 的 来 源 于 同 一 会 议 VLDB, 则 认 为 John Allen 与 J. Allen 存 在 出 处 关 联 ; 图 3(c) 表 示 John Allen 与 J. Allen 之 间 既 存 在 合 作 者 关 联 又 存 在 出 处 关 联, 则 认 为 John Allen 与 J. Allen 之 间 存 在 混 合 关 联. John Allen Collaborate Helen Collaborate J. Allen (a) John Allen Publish VLDB Publish J. Allen (b) John Allen Collaborate Helen Publish VLDB Publish J. Allen (c) Author Conference Coauthor association Conference association Fig.3 Demonstration of representation relationship graph 图 3 表 象 关 联 图 示 例 4.3 最 佳 路 径 选 取 表 象 关 联 图 中 两 个 表 象 之 间 如 果 存 在 多 条 关 联 路 径, 如 何 从 中 选 取 一 条 最 佳 路 径 作 为 表 象 间 关 联 强 度 计 算 的 依 据 就 成 为 一 个 有 待 解 决 的 问 题. 通 常, 如 果 两 个 表 象 间 语 义 关 联 所 在 的 上 下 文 环 境 包 含 的 表 象 越 少, 语 义 关 联 就 越 有 针 对 性, 表 象 同 属 于 一 个 实 体 的 概 率 也 就 相 对 越 高. 为 此, 本 文 定 义 了 路 径 重 要 度 来 量 化 表 象 间 语 义 关 联 的 独 特 性, 并 选 取 重 要 度 高 的 路 径 作 为 最 佳 路 径 来 计 算 关 联 强 度. 定 义 4( 路 径 重 要 度 ). 若 两 个 表 象 间 某 关 联 路 径 上 的 所 有 表 象 节 点 ( 不 包 含 起 始 表 象 和 终 止 表 象 ) 为 {r 1,, r k }, 与 节 点 r i 存 在 语 义 关 联 的 表 象 个 数 为 m i, 则 该 关 联 路 径 的 路 径 重 要 度 为 k i= 1 1. m 如 图 4 所 示, 表 象 John Allen 与 J. Allen 之 间 路 径 A 的 重 要 度 为 0.01, 而 路 径 B 的 重 要 度 为 0.5. 这 是 由 于 VLDB 与 很 多 作 者 之 间 都 存 在 出 处 关 联, 表 象 覆 盖 率 较 高, 因 此 削 弱 了 该 关 联 针 对 作 者 John Allen 与 J. Allen 的 表 现 能 力 ; 相 反,Helen 只 与 i 100 associations linked with VLDB Path A John Allen Publish VLDB Publish J. Allen Collaborate Helen Collaborate Path B Fig.4 Selection of the best path 图 4 最 佳 路 径 的 选 择 John Allen 和 J. Allen 具 有 合 作 者 关 联, 该 关 联 的 针 对 性 较 强, 突 出 表 现 了 John Allen 与 J. Allen 之 间 语 义 关 联 的 独 特 性. 因 此, 在 本 例 中, 优 先 选 择 表 现 能 力 较 强 的 路 径 B 作 为 最 佳 路 径 来 计 算 表 象 John Allen 与 J. Allen 之 间 的

7 200 Journal of Software 软 件 学 报 Vol.19, No.2, February 2008 关 联 强 度. 4.4 关 联 强 度 的 计 算 关 联 强 度 是 基 于 最 佳 路 径 对 表 象 间 语 义 关 联 的 量 化 表 示, 能 够 在 一 定 程 度 上 反 映 出 表 象 间 潜 在 的 语 义 相 似 性. 随 着 关 联 类 型 的 不 同, 其 语 义 关 联 程 度 也 有 所 不 同, 因 此, 需 要 针 对 不 同 的 关 联 类 型 为 其 赋 予 不 同 的 权 值. 由 此 可 见, 前 文 中 最 佳 路 径 的 选 取 是 根 据 表 象 关 联 图 中 关 联 的 独 特 性 来 进 行 的, 而 关 联 强 度 则 是 基 于 表 象 间 关 联 的 语 义 表 达 能 力 来 进 行 计 算 的. 表 象 r 1 到 r n 间 关 联 路 径 的 关 联 强 度 如 公 式 (8) 所 示. 1 CS( r1 r2) CS( rn 1 rn) n1w n mw CS( r1 r2... rn ) = = 1 n 1 n 1 Support( R _ Ri ) wi = 1 m Support( R _ R ) k = 1 可 见, 表 象 间 的 关 联 强 度 相 当 于 关 联 路 径 上 每 条 子 路 径 r i 1 r i 关 联 强 度 的 平 均 值. 其 中,n 1 ~n m 表 示 关 联 路 径 上 属 于 各 种 关 联 类 型 的 关 联 数 目 ;w 1 ~w m 表 示 按 照 语 义 关 联 程 度 对 不 同 的 关 联 类 型 ( 设 有 m 个 ) 所 赋 予 的 权 值 ( 如 公 式 (9) 所 示 ). 需 要 注 意 的 是, 语 义 关 联 的 表 达 能 力 越 强, 被 赋 予 的 权 值 就 越 小, 关 联 强 度 也 就 越 大. 例 如, 在 论 文 检 索 领 域 中, 合 作 者 关 联 比 出 处 关 联 具 有 更 强 的 语 义 表 现 能 力, 经 计 算, 其 权 值 分 别 为 0.3 和 0.7, 则 图 3(a) 图 3(b) 和 图 3(c) 中 表 象 John Allen 与 J. Allen 间 关 联 强 度 分 别 为 0.7,0.3 和 分 组 统 计 模 型 文 本 匹 配 与 语 义 分 析 针 对 的 都 是 字 符 串 类 型 的 属 性, 实 际 应 用 中 实 体 的 某 些 特 征 也 经 常 用 数 值 型 属 性 加 以 描 述, 如 报 价 库 存 量 等. 对 应 于 同 一 实 体 的 不 同 表 象 在 这 些 数 值 型 属 性 上 往 往 具 有 相 似 的 聚 集 值, 例 如 在 不 同 数 据 源 中, 同 一 商 品 的 平 均 价 格 基 本 一 致 同 一 作 者 被 检 索 的 文 章 总 数 基 本 相 同 等. 因 此, 可 以 基 于 这 些 数 值 型 属 性 对 语 义 相 似 集 的 表 象 进 行 统 计 分 析, 并 按 照 属 性 聚 集 值 的 相 似 程 度 进 一 步 对 表 象 进 行 聚 类. 5.1 约 束 规 则 我 们 将 存 在 于 不 同 数 据 源 中 的 同 一 聚 类 分 组 应 该 满 足 的 统 计 规 律 定 义 为 约 束 规 则. 约 束 规 则 所 约 束 的 目 标 是 不 同 数 据 源 内 的 聚 类 分 组, 而 不 同 于 文 本 匹 配 与 语 义 分 析 以 表 象 作 为 操 作 对 象. 因 此, 需 要 在 聚 类 分 组 的 层 次 上 针 对 不 同 的 数 据 源 对 其 进 行 统 计 分 析. 需 要 强 调 的 是, 只 有 当 聚 类 分 组 所 包 含 表 象 的 个 数 大 于 1 时, 才 有 必 要 进 行 统 计 分 析, 因 此, 通 常 认 为 只 包 含 1 个 表 象 的 聚 类 分 组 均 满 足 约 束 规 则 ; 另 外, 只 有 当 数 据 源 规 模 较 大 时, 统 计 分 析 才 能 有 效 进 行, 因 此, 分 组 统 计 分 析 适 合 在 表 象 覆 盖 率 较 大 的 数 据 源 上 进 行. 以 论 文 检 索 领 域 为 例, 假 设 语 义 相 似 集 S sem {John Allen,J. Allen,J. A. Allen,J. B. Allen,Jane Allen} 在 数 据 源 DS 1 和 DS 2 中 的 相 关 统 计 信 息 见 表 1, 针 对 作 者 的 被 收 录 文 章 数 参 与 会 议 数 可 以 为 每 个 聚 类 分 组 ( 包 含 的 表 象 数 大 于 1) 定 义 如 下 约 束 规 则 : 文 章 数 目 约 束 : 对 应 于 同 一 实 体 的 表 象 集 {r 1,,r n } 在 DS 1 中 被 收 录 的 文 章 总 数 应 等 于 在 DS 2 中 被 收 录 的 文 章 总 数, 记 为 DS 1.Sum(r 1. 文 章 数,,r n. 文 章 数 )=DS 2.Sum(r 1. 文 章 数,,r n. 文 章 数 ). 会 议 次 数 约 束 : 对 应 于 同 一 实 体 的 表 象 集 {r 1,,r n } 在 DS 1 中 参 与 某 会 议 的 总 次 数 应 等 于 在 DS 2 中 参 与 该 会 议 的 总 次 数, 记 为 DS 1.Sum(r 1. 会 议 数,,r n. 会 议 数 )=DS 2.Sum(r 1. 会 议 数,,r n. 会 议 数 ). Table 1 Statistical information of a semantic similar set in different data sources 表 1 不 同 数 据 源 中 某 语 义 相 似 集 的 统 计 信 息 S sem Number of accepted papers Number of attended conferences DS 1 DS 2 DS 1 DS 2 John Allen J. Allen J. A. Allen J. B. Allen Jane Allen k m (8) (9)

8 寇 月 等 : 一 种 基 于 语 义 及 统 计 分 析 的 Deep Web 实 体 识 别 机 制 201 表 1 中,S sem 在 DS 1 与 DS 2 中 被 收 录 的 文 章 总 数 分 别 为 225 和 150, 参 与 的 会 议 总 次 数 分 别 为 12 和 24, 说 明 S sem 包 含 属 于 多 个 实 体 的 表 象 而 不 满 足 约 束 规 则, 需 要 对 其 重 新 分 组, 直 到 各 个 分 组 均 满 足 约 束 规 则 为 止. 然 而, 由 于 Web 数 据 的 复 杂 性, 聚 类 分 组 很 难 完 全 满 足 预 定 义 的 约 束 规 则, 为 了 保 证 统 计 分 析 的 有 效 性, 通 过 设 置 分 组 阈 值 σ G (0 σ G 1) 适 当 地 放 宽 约 束 限 制. 例 如, 上 例 中 可 以 将 文 章 数 目 约 束 定 义 为 Min{DS 1.Sum(r 1. 文 章 数,,r n. 文 章 数 ),DS 2.Sum(r 1. 文 章 数,,r n. 文 章 数 )}/Max{DS 1.Sum(r 1. 文 章 数,,r n. 文 章 数 ),DS 2.Sum(r 1. 文 章 数,,r n. 文 章 数 )} σ G. 5.2 基 于 统 计 分 析 树 的 表 象 重 组 对 于 不 满 足 约 束 规 则 的 聚 类 分 组, 需 要 在 语 义 相 似 集 内 部 对 其 重 新 划 分. 为 此, 本 文 基 于 语 义 分 析 阶 段 生 成 的 表 象 关 联 图 构 建 统 计 分 析 树, 并 进 行 表 象 重 组, 最 终 生 成 满 足 约 束 规 则 的 聚 类 分 组. 其 过 程 如 下 : 步 骤 1. 针 对 某 语 义 相 似 集 ( 包 含 表 象 个 数 >1) 截 取 表 象 关 联 图 RRG 中 与 之 相 关 的 片 断 ( 若 表 象 间 存 在 多 条 路 径, 只 保 留 最 佳 路 径 ), 记 为 RRG. 步 骤 2. 在 RRG 中 只 保 留 该 语 义 相 似 集 的 表 象, 并 将 表 象 间 的 关 联 用 对 应 的 关 联 强 度 代 替, 记 为 RRG. 步 骤 3. 将 RRG 中 所 有 表 象 组 成 的 集 合 作 为 统 计 分 析 树 的 根 节 点, 按 照 表 象 间 关 联 强 度 由 小 到 大 的 顺 序 将 RRG 划 分 成 不 连 通 的 两 部 分, 分 别 作 为 统 计 分 析 树 的 叶 子 节 点. 步 骤 4. 检 测 当 前 统 计 分 析 树 中 的 叶 子 节 点 是 否 均 满 足 约 束 规 则, 若 满 足, 则 结 束 操 作 ; 否 则, 对 不 满 足 规 则 的 叶 子 节 点 按 步 骤 3 继 续 划 分, 直 到 所 有 叶 子 节 点 均 满 足 约 束 规 则 为 止. 以 表 1 中 的 表 象 为 例, 其 表 象 重 组 的 过 程 如 图 5 所 示. 首 先, 针 对 语 义 相 似 集 {John Allen,J. Allen,J. A. Allen,J. B. Allen,Jane Allen} 截 取 表 象 关 联 图 中 的 相 关 片 断 RRG, 由 于 图 中 只 保 留 最 佳 路 径, 因 此 表 象 间 不 存 在 回 路 ; 然 后, 对 RRG 进 行 简 化 处 理, 只 保 留 语 义 相 似 集 的 表 象 并 标 明 关 联 强 度 ; 将 语 义 相 似 集 作 为 根 节 点 构 建 统 计 分 析 树, 优 先 选 择 RRG 中 关 联 强 度 较 小 的 边 断 开, 将 得 到 的 不 连 通 的 两 部 分 作 为 叶 子 节 点 ; 由 于 存 在 叶 子 节 点 {John Allen,J. Allen,J. A. Allen,J. B. Allen} 不 满 足 约 束 规 则, 需 要 对 其 继 续 划 分 ; 以 此 类 推, 最 终 得 到 3 个 满 足 约 束 集 : {John Allen,J. Allen,J. A. Allen},{J. B. Allen} 和 {Jane Allen}. John Allen J. Allen J. A. Allen J. B. Allen Jane Allen RRG John Allen {John Allen, J. Allen, J. A. Allen, J. A. Allen J. B. Allen, Jane Allen} Not Satisfy {John Allen, J. Allen, 0.9 {Jane Allen} 0.7 J. B. Allen J. A. Allen, J. B. Allen} Satisfy Not Satisfy 0.3 J. Allen 0.2 {John Allen, J. Allen, {J. B. Allen} 1 J. A. Allen} Satisfy Satisfy Jane Allen RRG Statistical analysis tree Fig.5 Transition from representation relationship graph to statistics analysis tree 图 5 从 表 象 关 联 图 到 统 计 分 析 树 的 转 换 6 三 段 式 逐 步 求 精 算 法 及 性 能 分 析 本 文 基 于 文 本 匹 配 模 型 语 义 分 析 模 型 以 及 分 组 统 计 模 型, 采 用 文 本 粗 略 匹 配 表 象 关 联 关 系 获 取 以 及 分 组 统 计 分 析 的 三 段 式 逐 步 求 精 策 略, 结 合 属 性 文 本 特 征 上 下 文 语 义 信 息 及 约 束 规 则 对 识 别 结 果 不 断 进 行 精 化, 以 提 高 识 别 结 果 的 准 确 性. 本 节 将 介 绍 SS-EIM 的 三 段 式 逐 步 求 精 算 法, 并 对 其 性 能 进 行 分 析. 6.1 SS-EIM 的 三 段 式 逐 步 求 精 算 法 基 于 前 文 定 义 的 文 本 匹 配 模 型 语 义 分 析 模 型 以 及 分 组 统 计 模 型,SS-EIM 的 三 段 式 逐 步 求 精 (three-phase gradual refining, 简 称 TGR) 算 法 具 体 描 述 如 下. 阶 段 1. 文 本 粗 略 匹 配 阶 段. 应 用 文 本 匹 配 模 型 分 别 计 算 针 对 属 性 级 和 表 象 级 的 文 本 相 似 度, 并 将 表 象 按 照

9 202 Journal of Software 软 件 学 报 Vol.19, No.2, February 2008 属 性 特 征 进 行 聚 类, 生 成 一 系 列 文 本 相 似 集. 阶 段 2. 表 象 关 联 关 系 获 取 阶 段. 基 于 语 义 分 析 模 型 分 析 文 本 相 似 集 内 表 象 所 处 上 下 文 环 境 的 语 义 信 息, 将 达 到 一 定 关 联 强 度 的 表 象 聚 成 一 类, 生 成 一 系 列 语 义 相 似 集. 阶 段 3. 分 组 统 计 分 析 阶 段. 基 于 分 组 统 计 模 型 进 一 步 检 测 语 义 相 似 集 是 否 满 足 预 先 定 义 的 约 束 规 则, 利 用 统 计 分 析 树 将 不 满 足 约 束 规 则 的 表 象 集 进 行 表 象 重 组, 最 终 生 成 一 系 列 满 足 约 束 集 ( 每 个 集 合 对 应 于 一 个 实 体 的 表 象 聚 类 集 ), 以 达 到 实 体 识 别 的 目 的, 并 将 其 作 为 表 象 关 联 知 识 存 储. 由 上 可 知,TGR 算 法 是 对 实 体 的 表 象 聚 类 集 逐 步 求 精 的 过 程, 其 目 的 是 为 了 保 证 表 象 关 联 知 识 的 准 确 性. 本 文 重 点 介 绍 表 象 关 联 关 系 获 取 ( 见 算 法 2) 和 分 组 统 计 分 析 ( 见 算 法 3) 的 过 程, 具 体 识 别 算 法 如 下 : 算 法 1. TGR 算 法. 输 入 :R={r 1,r 2,,r R }, 文 本 相 似 阈 值 σ txt, 语 义 相 似 阈 值 σ sem, 分 组 统 计 阈 值 σ G,RRG 最 大 搜 索 深 度 L. 输 出 : 实 体 聚 类 集 C={c 1,c 2,,c C }. 步 骤 : 1: Vector txtsets:=r.initialtxtmatching(σ txt ); // 对 R 进 行 文 本 粗 略 匹 配 并 将 结 果 存 入 向 量 txtsets 2: Vector C:= ; // 为 实 体 聚 类 集 设 置 初 始 值 3: for(int i=0;i<txtsets.size();i++) // 顺 序 访 问 txtsets 中 的 每 个 文 本 相 似 集 4: Vector txtset:= txtsets.get(i); // 从 向 量 txtsets 中 取 一 个 文 本 相 似 集 存 入 txtset 5: Vector semsets:=getsemsets(txtset,σ sem,l); // 生 成 一 系 列 语 义 相 似 集 并 存 入 向 量 semsets 6: for(int j=0;j<semsets.size();j++) // 顺 序 访 问 semsets 中 的 每 个 语 义 相 似 集 7: Vector semset:=semsets.get(j); // 从 向 量 semsets 中 取 一 个 语 义 相 似 集 存 入 semset 8: Vector consets:=getconsets(semsets,σ G ); // 生 成 一 系 列 满 足 约 束 集 存 入 向 量 consets 9: C=C consets; // 将 当 前 生 成 的 consets 添 加 到 实 体 聚 类 集 C 中 10: return C; // 将 最 终 的 实 体 聚 类 集 C 作 为 结 果 返 回 算 法 2. 语 义 相 似 集 生 成 算 法 getsemsets(vector txtset,float σ sem,int L). 输 入 : 文 本 相 似 集 txtset, 语 义 相 似 阈 值 σ sem,rrg 最 大 搜 索 深 度 L. 输 出 : 一 系 列 语 义 相 似 集 semsets. 步 骤 : 1: Vector semsets:= ; // 用 来 存 储 生 成 的 一 系 列 语 义 相 似 集 2: for(int i=0;i<txtset.size();i++) // 顺 序 访 问 文 本 相 似 集 txtset 中 的 每 个 表 象 3: String rep:= txtset.get(i); // 从 txtset 中 取 一 个 表 象 rep 4: if(rep.semgroupid==0) // 如 果 rep 没 有 被 聚 类 到 任 何 一 个 语 义 相 似 集 内, 则 对 其 进 行 语 义 分 析 5: Vector oldv:={rep}; // 将 rep 存 入 向 量 oldv, 作 为 当 前 的 语 义 相 似 集 6: Vector newv:= ; // 用 于 与 当 前 的 语 义 相 似 集 进 行 比 较, 判 断 其 是 否 需 要 继 续 扩 充 7: for(int j=0;j<l; j++) // 以 深 度 L 遍 历 表 象 关 联 图 8: newv:=oldv {repnew CS(repOld repnew)>σ sem and repold oldv}; // 将 所 有 与 oldv 中 的 表 象 具 有 一 定 语 义 关 联 的 表 象 repnew 扩 充 到 当 前 语 义 相 似 集 内 9: if(newv==oldv) // 判 断 是 否 满 足 结 束 条 件, 也 就 是 不 再 有 新 的 表 象 被 扩 充 到 oldv 中 10: oldv.setsemgroupid(); // 将 oldv 作 为 一 个 语 义 相 似 集 并 为 其 设 置 组 号 标 识 11: break; // 跳 出 当 前 循 环, 继 续 生 成 下 一 个 语 义 相 似 集 12: oldv:=newv; // 将 oldv 赋 值 为 newv, 并 对 其 继 续 扩 充, 直 到 满 足 结 束 条 件 13: semsets.add(oldv); // 将 当 前 生 成 的 语 义 相 似 集 添 加 到 结 果 集 semsets 中 14: return semsets; // 将 最 终 的 semsets 作 为 结 果 返 回 算 法 3. 满 足 约 束 集 递 归 生 成 算 法 getconsets(vector semset,float σ G ). 输 入 : 语 义 相 似 集 semset, 分 组 统 计 阈 值 σ G.

10 寇 月 等 : 一 种 基 于 语 义 及 统 计 分 析 的 Deep Web 实 体 识 别 机 制 203 输 出 : 一 系 列 满 足 约 束 集 consets. 步 骤 : 1: Vector consets:= ; // 用 来 存 储 生 成 的 一 系 列 满 足 约 束 集 2: if(semset.satisfyconstraints(σ G )) // 判 断 当 前 集 合 semset 是 否 满 足 预 定 义 的 约 束 规 则 3: return semset; // 如 果 满 足, 则 无 须 对 semset 进 行 表 象 重 组, 直 接 作 为 满 足 约 束 集 返 回 4: else Vector tempv:=split(semset); // 否 则, 将 semset 划 分 为 不 相 交 的 两 部 分, 并 存 入 向 量 tempv 中 5: for(int i=0;i<2;i++) // 顺 序 访 问 tempv 中 的 每 个 表 象 集 合 ( 共 两 个 ) 6: Vector tempset:=tempv.get(i); // 从 tempv 中 取 一 个 表 象 集 合 存 入 tempset 中 7: consets=consets getconsets(tempset); // 针 对 tempset 递 归 调 用 getconsets 方 法 8: return consets; // 将 最 终 的 consets 作 为 结 果 返 回 6.2 算 法 性 能 分 析 SS-EIM 的 识 别 时 间 代 价 可 以 按 照 处 理 阶 段 的 不 同 划 分 为 3 个 部 分, 都 是 将 上 一 阶 段 的 结 果 作 为 下 一 阶 段 的 处 理 对 象.SS-EIM 的 实 体 识 别 的 总 体 时 间 代 价 为 TimeSS EIM = TimetxtInitialMatching + TimerelAbstraction + TimestatAnalyse 其 中,Time txtinitialmatching 为 文 本 粗 略 匹 配 的 时 间,Time relabstraction 为 表 象 关 联 关 系 获 取 所 需 要 的 时 间,Time statanalyse 为 分 组 统 计 分 析 的 时 间. 假 设 实 体 识 别 过 程 中 产 生 的 文 本 相 似 集 语 义 分 析 集 满 足 约 束 集 的 数 目 分 别 为 N txtsets, N semsets 和 N consets, 且 平 均 每 个 文 本 相 似 集 含 有 m 个 表 象,RRG 最 大 搜 索 深 度 为 L, 则 基 于 上 述 算 法, 我 们 给 出 表 象 关 联 关 系 获 取 和 分 组 统 计 分 析 的 时 间 复 杂 度. 其 中,Time relabstraction 的 时 间 复 杂 度 为 O(N txtsets m L ( newv log newv + oldv log oldv )), 由 于 newv 及 oldv 包 含 元 素 的 个 数 最 大 为 m, 所 以 Time relabstraction 的 上 限 为 O(N txtsets L m 2 logm),time statanalyse 的 时 间 复 杂 度 为 O(N txtsets N semsets N consets ). 为 了 提 高 SS-EIM 的 处 理 效 率, 我 们 对 以 上 算 法 采 取 了 如 下 优 化 措 施 : 首 先, 为 了 防 止 某 些 特 殊 情 况 下 遍 历 RRG 的 时 间 过 长, 通 过 预 先 设 置 RRG 最 大 搜 索 深 度 L, 使 得 表 象 关 联 关 系 获 取 能 够 在 相 对 有 限 的 范 围 内 进 行, 以 降 低 Time relabstraction 的 时 间 复 杂 度 ; 其 次, 由 于 表 象 关 联 关 系 获 取 和 分 组 统 计 分 析 只 集 中 在 各 个 文 本 相 似 集 内 部 进 行, 因 此 本 文 采 用 多 线 程 并 发 处 理 机 制, 将 针 对 不 同 文 本 相 似 集 的 语 义 分 析 及 分 组 统 计 处 理 并 行 进 行, 从 而 进 一 步 降 低 了 Time relabstraction 和 Time statanalyse 的 时 间 复 杂 度 ; 同 时,SS-EIM 将 关 联 路 径 上 表 象 间 关 联 强 度 运 算 的 中 间 结 果 存 储 在 缓 存 中, 从 而 避 免 了 无 谓 的 重 复 性 计 算, 提 高 了 实 体 识 别 的 处 理 效 率 ; 另 外,SS-EIM 的 三 段 式 逐 步 求 精 过 程 为 离 线 型 服 务 操 作, 不 会 对 用 户 的 操 作 造 成 直 接 影 响. 7 自 适 应 的 知 识 维 护 策 略 如 果 抽 取 Deep Web 中 所 有 数 据 源 上 的 数 据 进 行 实 体 识 别, 显 然 可 以 保 证 表 象 关 联 知 识 的 完 备 性, 但 由 此 产 生 的 巨 额 执 行 代 价 使 得 这 种 方 法 不 可 行 ; 同 时, 由 于 Web 环 境 中 数 据 的 动 态 特 性, 存 储 在 表 象 关 联 知 识 库 中 的 信 息 不 是 一 成 不 变 的, 需 要 对 其 有 效 性 及 时 检 测. 为 此, 本 文 采 用 静 态 分 析 动 态 协 调 相 结 合 的 自 适 应 知 识 维 护 策 略 (adaptive knowledge maintenance, 简 称 AKM) 构 建 和 完 善 表 象 关 联 知 识 库, 以 适 应 Web 数 据 的 动 态 性 并 保 证 表 象 关 联 知 识 的 完 备 性. 具 体 定 义 如 下 : 静 态 分 析 : 将 Web 中 一 定 量 的 静 态 页 面 中 的 信 息 作 为 预 获 取 的 实 例 信 息, 并 进 行 模 式 抽 取 ; 基 于 这 些 实 例 信 息 进 行 静 态 分 析, 也 就 是 采 用 前 文 提 到 的 文 本 粗 略 匹 配 表 象 关 联 关 系 获 取 以 及 分 组 统 计 分 析 的 三 段 式 逐 步 求 精 策 略, 生 成 初 始 的 表 象 关 联 知 识 库. 动 态 协 调 : 随 着 用 户 查 询 的 增 多, 基 于 用 户 查 询 请 求 和 返 回 结 果 的 实 例 信 息 来 动 态 协 调 表 象 关 联 知 识 库 中 的 内 容, 对 其 进 行 不 断 修 正 和 完 善. 理 想 情 况 下, 某 个 实 体 的 所 有 表 象 应 该 同 属 于 一 个 聚 类, 但 实 际 的 识 别 结 果 往 往 不 能 达 到 绝 对 的 准 确, 本 属 (10)

11 204 Journal of Software 软 件 学 报 Vol.19, No.2, February 2008 于 同 一 实 体 的 表 象 有 可 能 被 识 别 到 不 同 的 聚 类 中. 因 此, 本 文 针 对 特 定 领 域 中 的 某 类 查 询 请 求, 以 最 终 查 询 结 果 中 的 实 例 信 息 作 为 基 准, 引 入 实 体 熵 的 概 念 来 衡 量 某 个 实 体 的 表 象 集 分 散 到 多 个 聚 类 中 的 分 散 程 度, 从 而 检 测 表 象 关 联 知 识 库 的 有 效 性. 假 设 某 查 询 结 果 集 中 的 实 例 信 息 为 e={r 1,r 2,,r n }, 表 明 表 象 r 1 ~r n 对 应 于 某 实 体 e, 表 象 关 联 知 识 库 中 对 应 于 该 类 查 询 请 求 的 内 容 为 C={c 1,c 2,,c m }, 每 个 聚 类 集 c i 都 由 一 组 语 义 上 相 似 且 满 足 约 束 规 则 的 表 象 组 成, 则 实 体 熵 H(e) 的 定 义 如 公 式 (11) 所 示. 其 中,C ={c 1,,c m } 为 C 中 与 e 存 在 交 集 的 聚 类 集 合, c i e 表 示 e 中 的 表 象 被 聚 类 到 c i 中 的 个 数, 因 此 可 以 将 c i e /n 理 解 为 聚 类 集 c i 对 e 的 覆 盖 率. 理 想 情 况 下,e 中 所 有 表 象 均 被 聚 类 到 C 中 的 某 个 聚 类 集 c i 中, 此 时 H(e) 为 0; 相 反, 若 e 中 表 象 被 分 散 地 聚 类 到 C 中 的 多 个 聚 类 集 中, 则 随 着 分 散 程 度 的 增 大,H(e) 将 趋 近 于 log n 2. 因 此, 可 以 将 用 户 的 实 际 查 询 结 果 以 及 实 体 熵 作 为 表 象 关 联 知 识 库 的 信 息 是 否 完 备 和 有 效 的 衡 量 标 准, 具 体 检 测 过 程 如 下 : c e He () = log i (11) m n i c e 2 i= 1 n 完 备 性 检 测 : 若 C 为 空, 则 说 明 表 象 关 联 知 识 库 的 信 息 不 够 完 备 ( 说 明 目 前 C 中 至 少 不 包 含 实 体 e 的 信 息 ), 因 此 将 e 中 的 表 象 集 合 作 为 c m+1 扩 展 到 C 中, 并 存 入 表 象 关 联 知 识 库 ; 若 C =1, 则 说 明 C 中 只 有 1 个 聚 类 集 ( 假 设 为 c 1 ) 与 e 存 在 交 集, 此 时 将 c 1 内 原 有 的 表 象 连 同 e 中 新 出 现 的 表 象 组 合 成 新 的 聚 类 来 取 代 c 1. 有 效 性 检 测 : 若 C >1, 则 或 者 是 由 于 静 态 分 析 阶 段 将 本 属 于 同 一 实 体 e 的 表 象 错 误 地 识 别 成 对 应 多 个 实 体, 或 者 由 于 Web 数 据 的 动 态 更 新 使 得 当 前 知 识 库 中 的 部 分 内 容 失 效. 然 而, 小 范 围 的 表 象 识 别 错 误 或 数 据 失 效 不 会 对 整 体 的 数 据 集 成 产 生 太 大 的 影 响, 为 了 降 低 纠 错 的 处 理 代 价, 本 文 通 过 设 定 阈 值 σ H, 只 针 对 达 到 一 定 程 度 的 识 别 错 误 或 数 据 失 效 进 行 处 理. 具 体 来 说, 基 于 结 果 表 象 集 e 以 及 聚 类 集 C 计 算 H(e), 如 果 H(e)<σ H, 则 说 明 目 前 表 象 关 联 知 识 库 的 信 息 比 较 准 确, 可 以 保 持 不 变 ; 否 则, 需 要 对 C 连 同 e 中 的 表 象 重 新 进 行 实 体 识 别. 举 例 说 明, 假 设 C={c 1,c 2 },c 1 ={r 1,,r 10 },c 2 ={r 11,,r 20 },σ H 为 0.8. 若 e={r 21,r 22 }, 由 于 e 与 c 1,c 2 都 不 存 在 交 集, 则 将 e 作 为 一 个 新 的 聚 类 集 扩 展 到 C 中, 以 保 证 表 象 关 联 知 识 库 的 完 备 性 ; 若 e={r 1,r 21 }, 则 C 中 的 c 1 将 被 更 新 为 {r 1,,r 10,r 21 }; 若 e={r 1,,r 9,r 11 }, 则 H(e) 为 0.47 且 小 于 σ H, 因 此 可 以 忽 略 C 中 少 数 表 象 的 识 别 错 误 或 数 据 失 效 ; 若 e={r 1,,r 5,r 11,,r 15 }, 则 H(e) 为 1 且 大 于 σ H, 此 时 需 要 对 c 1,c 2 以 及 e 中 的 表 象 重 新 进 行 实 体 识 别, 并 对 表 象 关 联 知 识 库 进 行 更 新, 以 保 证 其 内 容 的 有 效 性. 8 实 验 测 试 本 节 针 对 SS-EIM 中 提 出 的 部 分 关 键 技 术 进 行 实 验 测 试, 主 要 包 括 对 比 不 同 数 据 量 不 同 初 始 分 组 数 的 实 体 识 别 时 间 代 价, 分 析 文 本 相 似 阈 值 σ txt 语 义 相 似 阈 值 σ sem 分 组 阈 值 σ G 等 参 数 的 设 置 对 实 体 识 别 准 确 性 的 影 响, 以 及 比 较 不 同 实 体 识 别 策 略 的 性 能. 8.1 数 据 集 本 文 主 要 针 对 论 文 检 索 领 域 中 的 作 者 表 象 进 行 实 体 识 别, 通 过 获 取 数 据 的 属 性 特 征 分 析 数 据 之 间 的 语 义 关 联 以 及 执 行 相 关 统 计, 对 作 者 的 不 同 表 象 进 行 识 别 并 将 论 文 信 息 按 照 作 者 进 行 聚 类, 以 此 来 提 高 集 成 数 据 的 质 量. 本 文 使 用 的 数 据 集 分 别 来 源 于 论 文 检 索 网 站 ACM 和 DBLP, 通 过 向 它 们 提 交 特 定 的 查 询 请 求 来 获 取 一 定 量 的 静 态 页 面 并 进 行 模 式 抽 取, 最 终 将 模 式 已 知 的 1M 条 记 录 作 为 实 验 数 据 集. 为 了 有 效 地 进 行 实 体 识 别, 提 交 的 查 询 请 求 应 尽 量 满 足 以 下 几 个 条 件 : 首 先, 基 于 这 些 请 求 所 得 到 的 查 询 结 果 集 具 有 较 大 的 数 据 量 ; 其 次, 在 这 些 结 果 数 据 中 存 在 较 多 由 同 一 个 人 所 发 表 的 文 章 信 息, 且 该 作 者 具 有 多 种 不 同 的 表 象 ; 最 后, 查 询 请 求 相 互 独 立, 以 保 证 结 果 集 之 间 不 存 在 交 集. 按 照 使 用 阶 段 的 不 同, 将 数 据 集 划 分 为 两 个 类 别 : 分 析 集 和 协 调 集. 分 析 集 应 用 于 实 体 识 别 的 静 态 分 析, 是 文 本 粗 略 匹 配 表 象 关 联 关 系 获 取 和 分 组 统 计 分 析 的 处 理 对 象, 用 来 构 建 初 始 的 表 象 关 联 知 识 库 ; 协 调 集 用 来 模 拟 从 用 户 实 际 查 询 中 所 得 到 的 结 果 集, 以 检 测 表 象 关 联 知 识 库 中 的 内 容 是 否 完 备 准 确, 主 要 应 用 在 实 体 识 别 的 动 态 协 调 过 程. 从 数 据 集 中 随 机 选 取 800K 条 记 录 作 为 分 析 集, 将 剩 余 的 数 据 集 作 为 协 调 集.

12 寇 月 等 : 一 种 基 于 语 义 及 统 计 分 析 的 Deep Web 实 体 识 别 机 制 205 实 验 环 境 设 置 如 下 : 主 机 采 用 Dell 2.4GHz P4, 内 存 容 量 为 512MB, 硬 盘 容 量 为 80GB, 操 作 系 统 为 Win 评 价 指 标 本 文 主 要 以 执 行 时 间 识 别 准 确 性 和 知 识 完 备 性 作 为 SS-EIM 的 评 价 指 标. 识 别 准 确 性 体 现 在 两 个 方 面 : 针 对 某 实 体 的 聚 类 分 散 性 和 针 对 某 聚 类 的 实 体 多 样 性. 前 者 是 指 某 个 实 体 的 表 象 集 分 散 到 多 个 聚 类 中 的 分 散 程 度, 可 以 用 前 文 定 义 的 实 体 熵 来 衡 量 ; 后 者 是 指 某 个 聚 类 c 所 包 含 实 体 类 别 的 多 样 化 程 度, 为 此 本 文 引 入 聚 类 熵 H(c) 的 概 念. 假 设 某 聚 类 表 象 集 为 c={r 1,r 2,,r n }, 实 体 集 为 E={e 1,e 2,,e m }, 其 中 每 个 实 体 e i 是 由 该 实 体 的 所 有 表 象 组 成 的 集 合, 则 聚 类 熵 的 定 义 如 公 式 (12) 所 示. 其 中,E ={e 1,,e m } 为 E 中 与 c 存 在 交 集 的 实 体 集 合, e i c 表 示 聚 类 c 中 属 于 实 体 e i 的 表 象 的 数 目. 理 想 情 况 下,c 中 的 表 象 均 对 应 于 同 一 个 实 体 e,h(c) 为 0; 相 反, 若 c 中 包 含 多 个 实 体 类 别 的 表 象, 随 着 类 别 的 增 多,H(c) 将 趋 近 于 log n 2. 将 E 中 所 有 实 体 的 实 体 熵 H(e) 的 平 均 值 记 为 H(E). 同 样, 将 C 中 所 有 聚 类 的 聚 类 熵 H(c) 的 平 均 值 记 为 H(C).H(E) 和 H(C) 越 小, 表 象 关 联 知 识 的 准 确 性 就 越 高. 知 识 完 备 性 用 来 衡 量 表 象 关 联 知 识 库 中 的 内 容 是 否 完 备, 我 们 将 数 据 集 内 实 际 存 在 的 实 体 类 别 数 目 记 为 m, 其 中 通 过 SS-EIM 正 确 识 别 的 实 体 类 别 数 目 为 n, 则 知 识 完 备 性 (recall) 为 n/m. 综 上 所 述, 本 实 验 的 评 价 指 标 主 要 包 括 : 执 行 时 间 知 识 准 确 性 ( 通 过 平 均 实 体 熵 H(E) 和 平 均 聚 类 熵 H(C) 来 衡 量 ) 和 知 识 完 备 性. e c Hc () = log i (12) m n i e c 2 i= 1 n 8.3 执 行 代 价 本 实 验 首 先 针 对 不 同 的 数 据 量 来 对 比 实 体 识 别 所 花 费 的 时 间 代 价, 分 别 从 分 析 集 中 随 机 抽 取 10K,50K, 100K,500K,800K 条 记 录 作 为 实 验 数 据 集 ; 然 后, 基 于 这 些 数 据 测 试 实 体 识 别 所 花 费 的 时 间 代 价, 其 中 将 RRG 最 大 搜 索 深 度 设 置 为 3, 实 验 结 果 如 图 6 所 示. 从 图 中 可 以 看 出, 随 着 数 据 量 的 增 长, 实 体 识 别 的 时 间 代 价 不 断 增 大, 从 具 体 的 时 间 代 价 和 增 长 速 度 来 看, 本 文 采 用 的 实 体 识 别 策 略 是 可 行 的. 另 外, 本 实 验 针 对 50K 记 录 测 试 不 同 初 始 分 组 数 对 后 续 处 理 所 需 要 的 时 间 代 价 的 影 响. 这 里 的 初 始 分 组 是 指 文 本 粗 略 匹 配 而 产 生 的 文 本 相 似 集, 可 以 通 过 设 置 不 同 的 文 本 相 似 阈 值 而 获 取 到 不 同 数 目 的 初 始 分 组, 测 试 结 果 如 图 7 所 示. 从 图 中 可 以 看 出, 初 始 分 组 数 越 大, 每 个 分 组 内 的 数 据 量 就 越 小, 分 组 内 进 行 实 体 识 别 的 时 间 代 价 也 就 越 小. 又 由 于 本 文 采 用 了 多 线 程 并 发 处 理 方 式, 因 此 总 体 时 间 代 价 也 随 之 减 少. Fig.6 Time (s) K 50K 100K 500K 800K Data amount Time cost of entity identification in SS-EIM with different size of data set 图 6 SS-EIM 在 不 同 数 据 规 模 下 的 实 体 识 别 时 间 代 价 Fig.7 Time (s) K 2K 3K 4K 5K Number of initial groups Time cost of entity identification in SS-EIM with different number of initial groups 图 7 SS-EIM 在 不 同 初 始 分 组 数 目 下 的 实 体 识 别 时 间 代 价 8.4 实 体 识 别 参 数 的 选 取 文 本 相 似 阈 值 σ txt 语 义 相 似 阈 值 σ sem 和 分 组 统 计 阈 值 σ G 的 初 始 值 由 领 域 专 家 来 设 置. 随 着 分 析 数 据 量 的 加 大, 这 些 参 数 将 逐 步 趋 于 最 优 化 配 置. 本 实 验 通 过 综 合 比 较 H(E) 和 H(C), 来 确 定 适 当 的 阈 值, 实 验 结 果 如 图 8 所 示. 随 着 这 些 阈 值 的 增 大, 分 组 条 件 越 发 严 格, 从 而 使 每 个 聚 类 包 含 的 表 象 数 目 逐 渐 减 少. 这 样, 每 个 聚 类 包 含 的 实 体 类 别 将 趋 向 理 想 的 单 一 化 趋 势, 但 同 时 也 加 重 了 对 应 于 同 一 实 体 的 表 象 分 散 化 程 度. 因 此, 随 着 这 些 阈 值 的 增 大,H(C) 不 断 降 低,H(E) 不 断 增 加. 为 了 综 合 提 高 SS-EIM 的 识 别 准 确 性, 我 们 选 取 (H(C)+H(E))/2 的 最 小 值 所 对

13 206 Journal of Software 软 件 学 报 Vol.19, No.2, February 2008 应 的 阈 值 作 为 参 数 的 最 佳 阈 值. 通 过 测 试,σ txt,σ sem 和 σ G 的 最 优 配 置 分 别 为 0.6,0.6 和 0.8. Entropy H(C) H(E) (H(C)+H(E))/ σ txt Entropy H(C) H(E) (H(C)+H(E))/ σ sem Entropy H(C) H(E) (H(C)+H(E))/ σ G Fig.8 Selection of entity identification parameters 图 8 实 体 识 别 参 数 的 选 取 8.5 SS-EIM 与 FBS,Sem-EIM,Stat-EIM 的 性 能 比 较 本 实 验 将 SS-EIM 与 相 关 工 作 中 所 采 取 的 实 体 识 别 策 略 ( 基 于 属 性 文 本 特 征 的 实 体 识 别 FBS [3 11] 基 于 语 义 分 析 的 实 体 识 别 Sem-EIM [12 17] ) 以 及 基 于 统 计 分 析 的 实 体 识 别 Stat-EIM 进 行 对 比, 实 验 结 果 如 图 9 所 示. FBS 是 单 一 地 基 于 属 性 特 征 对 表 象 进 行 聚 类 ;Sem-EIM 是 基 于 FBS 的 结 果 进 一 步 作 语 义 分 析, 将 具 有 语 义 关 联 的 表 象 聚 成 一 类 ;Stat-EIM 是 对 FBS 的 结 果 基 于 约 束 规 则 进 行 统 计 分 析. 聚 类 数 目 越 多, 每 个 聚 类 所 包 含 的 实 体 类 别 数 目 就 越 少, 因 此 H(C) 也 就 越 小 ; 但 同 时 也 加 重 了 对 应 于 同 一 实 体 的 表 象 的 分 散 程 度, 因 而 H(E) 增 大. 由 于 SS-EIM 采 用 了 三 段 式 逐 步 求 精 策 略, 在 实 体 识 别 中 综 合 考 虑 了 属 性 文 本 特 征 表 象 间 语 义 关 联 以 及 表 象 组 的 约 束 规 则,H(C) 减 少 的 速 度 大 于 H(E) 增 长 的 速 度. 因 此, 与 其 他 3 种 策 略 相 比, 准 确 性 有 了 较 大 的 提 高 ( 对 应 的 H(C) 与 H(E) 的 平 均 值 最 小 ). 1.6 H(C) H(E) (H(C)+H(E))/2 Entropy FBS Sem-EIM Stat-EIM SS-EIM Fig.9 Performance comparison among SS-EIM, FBS, Sem-EIM and Stat-EIM 图 9 SS-EIM 与 FBS,Sem-EIM 和 Stat-EIM 的 性 能 比 较 8.6 AKM 与 N-AKM 的 性 能 比 较 本 实 验 将 协 调 集 内 的 数 据 通 过 人 工 进 行 实 体 识 别 来 模 拟 用 户 实 际 查 询 中 所 得 到 的 结 果 集, 并 将 其 应 用 在 SS-EIM 的 动 态 协 调 过 程 中. 然 后 将 本 文 提 出 的 静 态 分 析 与 动 态 协 调 相 结 合 的 自 适 应 知 识 维 护 策 略 (AKM) 与 只 进 行 静 态 分 析 而 没 有 动 态 协 调 的 策 略 (N-AKM) 进 行 比 较, 比 较 结 果 如 图 10 所 示 H(C) H(E) (H(C)+H(E))/2 Recall Fig.10 0 N-AKM AKM Performance comparison between AKM and N-AKM 图 10 AKM 与 N-AKM 的 性 能 比 较

14 寇 月 等 : 一 种 基 于 语 义 及 统 计 分 析 的 Deep Web 实 体 识 别 机 制 207 由 于 AKM 基 于 用 户 的 查 询 结 果 对 表 象 关 联 知 识 库 中 的 内 容 不 断 扩 充, 与 N-AKM 相 比, 扩 充 后 的 表 象 关 联 知 识 库 具 有 较 高 的 完 备 性 ; 另 外, 通 过 AKM 策 略 将 知 识 库 中 当 前 内 容 与 实 际 结 果 数 据 进 行 对 比, 利 用 实 体 熵 来 衡 量 数 据 的 有 效 性 并 及 时 修 正, 使 得 知 识 库 的 内 容 更 能 反 映 数 据 的 真 实 状 况, 从 而 具 备 较 高 的 知 识 准 确 性. 9 结 论 本 文 针 对 Deep Web 数 据 集 成 中 的 实 体 识 别 问 题 进 行 了 较 为 深 入 的 研 究, 提 出 了 一 种 基 于 语 义 及 统 计 分 析 的 实 体 识 别 机 制, 能 够 有 效 解 决 Deep Web 数 据 集 成 中 的 数 据 消 重 及 表 象 整 合 等 问 题. 目 前 已 完 成 的 工 作 包 括 : 基 于 文 本 匹 配 模 型 语 义 分 析 模 型 和 分 组 统 计 模 型, 构 建 了 SS-EIM 的 整 体 模 型 框 架 ; 提 出 了 文 本 粗 略 匹 配 表 象 关 联 关 系 获 取 以 及 分 组 统 计 分 析 的 三 段 式 逐 步 求 精 策 略, 基 于 文 本 特 征 语 义 关 联 及 约 束 规 则 对 表 象 进 行 聚 类 ; 提 出 了 静 态 分 析 动 态 协 调 相 结 合 的 自 适 应 知 识 维 护 策 略, 利 用 用 户 实 际 的 查 询 结 果 来 不 断 完 善 和 扩 充 表 象 关 联 知 识 库. 通 过 模 拟 实 验 表 明, 由 于 SS-EIM 综 合 考 虑 了 文 本 特 征 语 义 关 联 及 约 束 规 则, 对 识 别 结 果 进 行 不 断 精 化, 有 效 地 提 高 了 识 别 结 果 的 准 确 性 ; 通 过 对 实 体 熵 和 聚 类 熵 的 折 衷 评 价, 以 保 证 实 体 识 别 过 程 中 相 关 参 数 的 合 理 化 配 置 ; 另 外, 在 表 象 关 联 知 识 库 构 建 过 程 中, 由 于 采 用 静 态 分 析 动 态 协 调 相 结 合 的 自 适 应 知 识 维 护 策 略 对 关 联 知 识 不 断 扩 充 和 完 善, 在 一 定 程 度 上 保 证 了 表 象 关 联 知 识 的 有 效 性 和 完 备 性. 下 一 步, 我 们 将 针 对 语 义 分 析 与 分 组 统 计 的 性 能 改 进 实 体 识 别 相 关 参 数 的 合 理 化 配 置 以 及 表 象 关 联 知 识 的 智 能 化 管 理 等 方 面 进 行 深 入 研 究. References: [1] Chang KCC, He B, Li CK, Patel M, Zhang Z. Structured databases on the Web: Observations and implications. SIGMOD Record, 2004,33(3): [2] Guo ZM, Zhou AY. Research on data quality and data cleaning: A survey. Journal of Software, 2002,13(11): (in Chinese with English abstract). [3] Bilenko M, Mooney R. Adaptive duplicate detection using learnable string similarity measures. In: Getoor L, ed. Proc. of the 9th ACM SIGKDD Washington: ACM Press, [4] Cohen WW, Ravikumar P, Fienberg SE. A comparison of string distance metrics for name-matching tasks. In: Kambhampati S, ed. Proc. of IJCAI-03 Workshop on Information Integration on the Web (IIWeb 2003). New York: AAAI Press, [5] Zhu HM, Wang NS. Improved method for detecting approximately duplicate database records. Journal of Control and Decision, 2006,21(7): (in Chinese with English abstract). [6] Ling YY, Liu W, Wang ZY, Ai J, Meng XF. Entity identification for deep Web data integration. Journal of Computer Research and Development, 2006,43(Suppl.):46 53 (in Chinese with English abstract). [7] Koudas N, Sarawagi S, Srivastava D. Record linkage: Similarity measures and algorithms. In: Chaudhuri S, ed. Proc. of the ACM SIGMOD Int l Conf. on Management of Data. Chicago: ACM Press, [8] Wang LJ, Guan SY, Wang XL, Wang XZ. Fuzzy C mean algorithm based on feature weights. Chinese Journal of Computers, 2006, 29(10): (in Chinese with English abstract). [9] Das G, Hristidis V. Ordering the attributes of query results. In: Chaudhuri S, ed. Proc. of the ACM SIGMOD Int l Conf. on Management of Data. Chicago: ACM Press, [10] Nambiar U, Kambhampati S. Mining approximate functional dependencies and concept similarities to answer imprecise queries. In: Amer-Yahia S, ed. Proc. of the 7th Int l Workshop on the Web and Databases (WebDB 2004). Paris: ACM Press, [11] Chaudhuri S, Granti V, Motwani R. Robust identification of fuzzy duplicates. In: Toyama M, ed. Proc. of the 21st Int l Conf. on Data Engineering (ICDE 2005). Tokyo: IEEE Computer Society, [12] Chen ZQ, Kalashnikov DV, Mehrotra S. Exploiting relationships for object consolidation. In: Ozcan F, ed. Proc. of the 2nd Int l ACM SIGMOD Workshop on Information Quality in Information Systems (IQIS 2005). Baltimore: ACM Press, [13] Thor A, Rahm E. MOMA A mapping-based object matching system. In: Weikum G, ed. Proc. of the 3rd Biennial Conf. on Innovative Data Systems Research (CIDR 2007). Asilornar: Wisconsin,

15 208 Journal of Software 软 件 学 报 Vol.19, No.2, February 2008 [14] Nie ZQ, Wen JR, Ma WY. Object-Level vertical search. In: Weikum G, ed. Proc. of the 3rd Biennial Conf. on Innovative Data Systems Research (CIDR 2007). Asilornar: Wisconsin, [15] Bhattacharya I, Getoor L. Iterative record linkage for cleaning and integration. In: Das G, ed. Proc. of the 9th ACM SIGMOD Workshop on Research Issues in Data Mining and Knowledge Discovery (DMKD 2004). Paris: ACM Press, [16] Dong X, Halevy A, Madhaven J. Reference reconciliation in complex information spaces. In: Ozcan F, ed. Proc. of the ACM SIGMOD Int l Conf. on Management of Data. Baltimore: ACM Press, [17] Wei M, Naumann F. DogmatiX tracks down duplicates in XML. In: Ozcan F, ed. Proc. of the ACM SIGMOD Int l Conf. on Management of Data. Baltimore: ACM Press, [18] Hall P, Dowling G. Approximate string matching. ACM Computing Surveys, 1980,12(4): [19] Skikant R, Agrawal R. Mining generalized association rules. In: Dayal U, ed. Proc. of the 21st Int l Conf. on Very Large Data Bases (VLDB 1995). Heidelberg: Springer-Verlag, [20] Liu B, Hsu W, Ma YM. Integrating classification and association rule mining. In: Agrawal R, ed. Proc of the 4th Int l Conf. on Knowledge Discovery and Data Mining (KDD 1998). New York: AAAI Press, 附 中 文 参 考 文 献 : [2] 郭 志 懋, 周 傲 英. 数 据 质 量 和 数 据 清 洗 研 究 综 述. 软 件 学 报,2002,13(11): [5] 朱 恒 民, 王 宁 生. 一 种 改 进 的 相 似 重 复 记 录 检 测 方 法. 控 制 与 决 策,2006,21(7): [6] 凌 妍 妍, 刘 伟, 王 仲 远, 艾 静, 孟 小 峰.Deep Web 数 据 集 成 中 的 实 体 识 别 方 法. 计 算 机 研 究 与 发 展,2006,43( 增 刊 ): [8] 王 丽 娟, 关 守 义, 王 晓 龙, 王 熙 照. 基 于 属 性 权 重 的 Fuzzy C Mean 算 法. 计 算 机 学 报,2006,29(10): 寇 月 (1980-), 女, 辽 宁 沈 阳 人, 博 士 生, 助 教,CCF 学 生 会 员, 主 要 研 究 领 域 为 Deep Web 数 据 管 理. 李 冬 (1979-), 男, 工 程 师, 主 要 研 究 领 域 为 嵌 入 式 软 件 环 境. 申 德 荣 (1964-), 女, 博 士, 教 授,CCF 高 级 会 员, 主 要 研 究 领 域 为 Web 数 据 管 理, 分 布 式 系 统, 数 据 网 格. 聂 铁 铮 (1980-), 男, 博 士 生, 助 教,CCF 学 生 会 员, 主 要 研 究 领 域 为 Web 数 据 集 成.