基于词典中词语量化关系的中文文本聚类研究.pdf

《基于词典中词语量化关系的中文文本聚类研究.pdf》由会员分享，可在线阅读，更多相关《基于词典中词语量化关系的中文文本聚类研究.pdf（5页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、基 于 词 典 中 词 语 量 化 关 系 的 中 文 文 本 聚 类 研 究!胡 熠 ! 陆 汝 占 陈 玉 泉 刘 慧（ 上 海 交 通 大 学 计 算 机 科 学 与 工 程 系 上 海 200240）摘 要 鉴 于 词 语 知 识 对 提 高 文 本 聚 类 性 能 的 价 值 ， 提 出 了 一 种 用 线 性 插 值 方 式 把 词 典词 语 之 间 的 量 化 关 系 和 余 弦 相 似 度 结 合 起 来 的 文 本 相 似 度 计 算 方 法 。 在 实 现 文 本 聚 类 之前 ， 基 于 词 典 中 一 个 词 条 和 其 释 义 在 语 义 上 等 价 的 假 设 ，

2、构 建 出 词 条 和 释 义 中 词 语 之 间 的量 化 关 系 ， 并 把 这 种 量 化 关 系 值 作 为 文 本 聚 类 用 到 的 知 识 。 在 !-均 值 聚 类 算 法 的 框 架下 ， 这 种 以 线 性 插 值 方 式 构 造 的 新 的 相 似 度 ， 给 文 本 聚 类 系 统 性 能 带 来 了 明 显 的 提 高 。 实验 结 果 说 明 从 词 典 中 获 取 的 词 语 量 化 关 系 对 将 来 的 文 本 聚 类 研 究 可 能 会 有 潜 在 的 贡 献 。关 键 词 文 本 聚 类 ， 词 语 量 化 关 系 ， 线 性 插 值 ， !-均 值0 引

3、 言随 着 Internet 以 及 各 种 文 本 管 理 系 统 中 可 用 文本 的 不 断 增 多 ， 将 文 本 集 合 预 先 分 割 成 若 干 类 别 ， 为诸 多 面 向 文 本 的 智 能 系 统 提 供 了 支 持 。 原 先 较 大 规模 的 文 本 集 合 在 聚 类 后 形 成 了 多 个 小 规 模 的 各 自 代表 某 个 主 题 的 文 本 类 ， 呈 现 出 一 种 层 次 结 构 的 形 式 。这 样 的 聚 类 对 于 大 量 文 本 的 索 引 、 检 索 、 管 理 和 挖 掘都 是 很 重 要 的 一 步 。文 本 聚 类 任 务 面 临 多 方

4、面 的 挑 战 性 的 问 题 。 例如 ， 大 多 数 已 有 文 本 聚 类 方 法 基 于 信 息 检 索 领 域 熟知 的 “ 词 袋 ” 模 型 l， 其 中 每 个 词 语 （ term） 被 用 作 特征 表 示 文 本 ， 词 语 之 间 认 为 是 相 互 独 立 的 ， 这 样 生 成的 文 本 向 量 空 间 一 般 维 数 较 高 ， 另 外 ， 聚 类 文 本 集 的规 模 往 往 很 大 。 对 于 这 两 个 问 题 ， Jing 等 人 提 出 了一 个 比 较 有 效 的 解 决 方 案 ， 就 是 在 一 个 可 扩 展 的 聚类 子 空 间 上 ， 利 用

5、 带 加 权 特 征 的 !-均 值 算 法 实 现 文本 聚 类 2。 第 三 个 问 题 就 是 文 本 表 现 出 的 复 杂 语 义也 远 远 不 是 各 维 词 语 独 立 的 文 本 向 量 所 能 描 述 的 ，这 种 独 立 性 假 设 显 然 并 不 符 合 语 言 事 实 。 所 以 ， 近年 来 一 些 研 究 人 员 专 注 于 利 用 本 体 论 （ OntOIOgy） 从文 本 中 抽 取 概 念 特 征 表 示 文 本 ， 他 们 的 主 要 做 法 就是 用 OntOIOgy 体 现 出 的 概 念 间 关 系 增 加 文 本 表 示 向量 中 的 词 语 数

6、量 或 修 改 词 语 对 应 的 权 值 ， 事 实 证 明这 种 基 于 OntOIOgy 的 方 法 的 确 提 高 了 聚 类 的 性能 3-5。 本 文 旨 在 研 究 ， 一 部 原 始 词 典 能 否 有 助 于 解决 第 三 个 问 题 。文 献 3-5 的 工 作 是 基 于 一 个 现 有 的 OntOIOgy 计算 文 本 向 量 自 身 各 维 词 语 之 间 的 关 系 。 而 我 们 的 工作 与 此 不 同 ， 是 利 用 一 部 中 文 词 典 （ 现 代 汉 语 规 范词 典 6） 一 种 非 结 构 化 的 数 据 源 作 为 背 景 知识 ， 来 挖 掘

7、词 语 之 间 的 量 化 关 系 。 这 种 量 化 关 系 的计 算 使 用 的 是 一 种 统 计 的 方 法 。 和 前 人 工 作 还 有 一点 不 同 的 是 ， 这 种 量 化 关 系 的 应 用 ， 不 是 改 造 文 本 向量 自 身 ， 而 是 文 本 间 相 似 性 的 计 算 。 为 把 这 种 量 化的 词 语 关 系 应 用 到 传 统 的 向 量 空 间 模 型 （ VSM） 中 ，我 们 设 计 了 一 种 新 的 文 本 相 似 度 计 算 方 法 。 这 里 的两 个 词 语 不 是 在 同 一 个 文 本 中 的 ， 而 是 在 不 同 文 本中 出 现

8、的 。 这 个 新 的 相 似 度 以 插 值 形 式 把 词 语 间 量化 关 系 和 标 准 的 余 弦 （ cOsine） 相 似 度 组 合 起 来 。 在实 验 中 ， 新 的 相 似 度 计 算 公 式 和 传 统 的 cOsine 在 !-均 值 7算 法 的 框 架 下 进 行 了 比 较 。 实 验 结 果 显 示 ，这 种 把 词 典 词 语 间 量 化 关 系 引 入 到 文 本 相 似 度 计 算的 方 法 ， 可 以 有 效 地 提 高 聚 类 的 性 能 。需 要 说 明 的 是 ， 我 们 选 择 了 !-均 值 算 法 是 因 为Steinbach 等 8比 较

9、 了 一 些 算 法 在 文 本 聚 类 任 务 中 的适 用 程 度 ， 得 出 的 结 论 是 ， !-均 值 算 法 是 目 前 聚 类 算法 里 表 现 较 好 的 ， 它 的 处 理 时 间 和 文 本 数 量 呈 线 性关 系 ， 性 能 和 层 次 算 法 相 当 。l 基 于 词 典 的 文 本 聚 类! ! 词 典 中 词 语 间 的 量 化 关 系从 语 言 学 家 的 观 点 来 看 ， 词 语 和 词 语 之 间 存 在着 某 种 联 系 ， 所 以 我 们 尝 试 着 挖 掘 词 语 之 间 的 这 种877高 技 术 通 讯 2007 年 8 月 第 l7 卷 第

10、8 期!男 ， l978 年 生 ， 博 士 生 ； 研 究 方 向 ： 自 然 语 言 处 理 ， 智 能 信 息 检 索 ， 信 息 抽 取 ； 通 讯 作 者 ， E-maiI： huyi （ 收 稿 日 期 ： 2006-07-l4）863 计 划 （ 200lAAll42l0-ll） 和 国 家 自 然 科 学 基 金 （ 60496326） 资 助 项 目 。关 系 ， 并 把 它 们 量 化 ， 而 不 是 继 续 使 用 传 统 的 向 量 空间 模 型 （ VSM） 中 词 语 间 的 独 立 性 假 设 。在 这 部 分 ， 我 们 着 重 介 绍 从 词 典 中 计 算

11、这 种 词语 间 量 化 关 系 的 思 路 。 和 其 他 研 究 人 员 9-12从 一 般性 文 本 中 构 建 词 语 关 系 的 做 法 不 同 ， 我 们 用 的 资 源是 一 部 词 典 现 代 汉 语 规 范 词 典 ， 通 过 统 计 计算 获 得 词 语 间 的 量 化 关 系 。 之 所 以 会 选 用 词 典 ， 是因 为 词 典 是 人 类 知 识 的 浓 缩 ， 词 典 中 词 条 的 解 释 一般 较 为 规 范 ， 正 确 ， 而 且 应 用 面 广 。就 构 建 词 语 间 量 化 关 系 而 言 ， 本 文 的 目 标 是 一个 词 条 和 其 释 义 中

12、的 词 语 之 间 的 关 系 。 在 这 里 我 们提 出 一 个 直 观 简 单 的 假 设 ： 一 个 词 条 E 在 词 典 中 被释 义 D 解 释 ， 即E 1 t1t2. . . tn（ 1）其 中 ， t1t2 tn是 构 成 词 条 释 义 D 的 词 序 列 ， 那 么 词条 E 和 释 义 D 在 语 义 信 息 上 等 价 ， 即SenseE= Sense（ 2）这 里 ， SenseE指 词 条 E 的 意 义 ； Sense代 表释 义 中 t1， t2， . . .， tn的 组 合 意 义 。 当 然 要 想 获 得 中文 词 序 列 ， 需 要 对 释 义 进

13、 行 切 分 。就 目 前 的 自 然 语 言 理 解 水 平 而 言 ， 自 动 、 准 确 地分 析 词 条 和 释 义 中 词 语 之 间 真 正 语 义 上 的 关 系 ， 仍然 是 一 件 很 困 难 的 工 作 ， 而 且 往 往 词 语 间 的 语 义 关系 在 不 同 语 境 中 还 会 有 所 变 化 。 所 以 我 们 的 工 作 只是 在 词 典 中 构 造 一 种 静 态 的 量 化 关 系 。 由 于 来 源 于词 典 ， 所 以 也 可 以 认 为 获 得 的 词 语 量 化 关 系 有 可 能是 基 本 正 确 的 。我 们 的 想 法 很 简 单 ： 如 果 一

14、 个 词 语 ti出 现 在 一个 词 条 E 的 释 义 中 ， 而 它 很 少 出 现 在 其 他 词 条 的 释义 中 ， 那 么 这 个 词 语 ti可 能 对 这 个 词 条 的 语 义 解 释贡 献 比 较 大 。 如 词 条 “ 经 济 ” 释 义 中 的 词 语 “ 消 费 ” ，在 其 他 词 条 的 释 义 中 很 少 出 现 ， 那 么 可 以 认 为 “ 消费 ” 对 于 解 释 “ 经 济 ” 的 贡 献 很 大 ， 专 属 度 比 较 高 ， 那么 “ 消 费 ” 和 “ 经 济 ” 的 量 化 关 系 应 该 比 较 大 。 这 个 思想 比 较 适 合 于 用

15、tf idf算 法 来 形 式 化 。 所 以 ， 在 我们 的 研 究 中 ， 我 们 采 用 了 标 准 tf idf公 式r（ E， ti）=（ 1+ log（ tf（ E， ti） ） ） logNef（ ti( )）tf（ E， ti） 00 tf（ E， ti）=0（ 3）来 计 算 词 条 和 它 释 义 中 某 个 词 语 之 间 的 关 系 。 这 里ti是 释 义 词 集 合 t1， t2， . . .， tn 中 的 某 个 词 语 。 另外 ， r（ E， ti） 表 示 ti对 于 解 释 词 条 E 的 重 要 程 度 ， 也是 两 者 之 间 的 量 化 关 系

16、； tf（ E， ti） 表 示 词 语 ti在 词条 E 的 释 义 中 出 现 的 次 数 ； ef（ ti） 表 示 在 自 身 释 义中 出 现 了 词 语 ti的 词 条 数 目 。 因 此 ， logNef（ ti( )）就是 类 似 于 原 来 “ 反 向 文 档 频 率 ” 的 “ 反 向 词 条 频 率 ” ，其 中 N 表 示 词 典 中 所 有 词 条 的 数 目 ， 在 我 们 使 用 的机 器 可 读 版 本 中 ， 共 计 94557 个 词 条 。 从 词 典 中 ， 我们 用 这 个 方 法 总 共 得 到 了 892575 个 词 语 对 。 部 分词 对 及

17、 其 量 化 关 系 如 表 1 和 表 2 所 示 。表 ! 不 同 的 词 条 和 相 同 的 词 语 （ 电 子 计 算 机 ）组 成 的 词 对 及 其 量 化 关 系（ E， t） 词 语 间 量 化 关 系（ 办 公 自 动 化 ， 电 子 计 算 机 ） 5.916202（ 程 序 设 计 ， 电 子 计 算 机 ） 5.916202（ 磁 盘 ， 电 子 计 算 机 ） 5.916202（ 存 储 器 ， 电 子 计 算 机 ） 5.916202（ 计 算 机 ， 电 子 计 算 机 ） 12.415814表 相 同 的 词 条 （ 经 济 ） 和 它 的 释 义 中 不 同词

18、 语 组 成 的 词 对 及 其 量 化 关 系（ E， t） 词 语 间 量 化 关 系（ 经 济 ， 国 家 ） 4.077537（ 经 济 ， 消 费 ） 12.192642（ 经 济 ， 流 通 ） 7.054450（ 经 济 ， 生 产 关 系 ） 8.536211（ 经 济 ， 政 治 ） 5.517453表 1 举 例 的 是 不 同 的 词 条 和 出 现 在 它 们 各 自 释义 中 同 一 个 词 语 构 成 的 词 语 对 及 其 量 化 关 系 。 可 以看 到 ， 由 于 是 同 一 个 t， 所 以 在 tf idf中 的 idf 值 对这 个 t 而 言 是 一

19、样 的 ， 所 不 同 的 就 是 tf 项 ， 对 于 tf项 也 相 同 的 词 条 ，（ E， t） 就 获 得 了 一 样 的 r 函 数 值 。表 2 是 相 同 的 词 条 （ 经 济 ） 和 它 释 义 中 不 同 词 语 构 成的 词 语 对 及 其 量 化 关 系 。 在 892575 个 词 语 对 中 ， 获得 最 大 的 关 系 值 的 是 （ 唯 物 主 义 ， 思 想 体 系 ） ，30.990878。 关 系 值 比 较 小 的 是 词 条 和 停 用 词 构 成的 词 对 。 如 （ 唯 物 主 义 ， 的 ） 的 关 系 值 就 几 乎 等 于 0。而 由 （

20、 3） 式 可 以 看 出 ： 在 词 条 释 义 中 没 有 出 现 的 词 和词 条 的 关 系 值 为 0。 这 样 ， 我 们 就 从 词 典 中 得 到 了词 语 对 的 关 系 值 ， 在 下 面 小 节 中 将 引 入 到 文 本 间 的相 似 度 计 算 上 。! # 插 值 形 式 的 文 本 相 似 度传 统 的 基 于 VSM表 示 方 式 的 文 本 可 以 写 成!d =（ w1， w2， . . .， wl） ， 这 里 wi（ 1il） 是 向 量对 应 维 上 的 词 语 在 文 本 中 的 权 值 ， 在 我 们 的 工 作 中977胡 熠 等 ： 基 于 词

21、 典 中 词 语 量 化 关 系 的 中 文 文 本 聚 类 研 究是 出 现 与 否 的 布 尔 值 。 基 于 这 样 的 文 本 表 示 方 式 ，有 很 多 方 法 可 以 测 量 两 个 文 本 ii和 i之 间 的 相 似度 ， 比 如 cosine 相 似 度 和 Minkowski 距 离 ， 包 括 Eu-clicean 距 离 ， Manhattan 距 离 ， Maximum 距 离 等等 7， l3。 这 里 我 们 使 用 的 是 cosine 相 似 度 ， 一 种 在VSM 中 广 泛 采 用 的 相 似 度 评 价 机 制 。 它 计 算 向 量空 间 中 代

22、表 两 个 文 本 的 向 量 之 间 的 夹 角 余 弦 。Cosine 相 似 度 ： 两 个 基 于 VSM 表 示 的 文 本 ii和i之 间 的 cosine 相 似 度 定 义 为 ：S（ ii， i）= cos（4（ i、i， i、） ）=i、i i、I i、iI I i、I（ 4）这 里I i、iI和I i、I分 别 表 示 向 量 i、i和 i、的 长 度 。i、i i、是 这 两 个 向 量 的 点 积 。 由 于 cosine 相 似 度 包含 了 一 个 向 量 空 间 各 维 之 间 独 立 的 假 设 ， 所 以 本 质上 来 讲 ， 它 是 一 个 向 量 同 维

23、 比 较 的 相 似 度 。 当 我 们考 虑 这 两 个 文 本 向 量 不 同 维 之 间 的 关 系 时 ， 就 很 自然 地 需 要 不 同 维 词 语 之 间 的 关 系 ， 前 文 获 得 的 量 化关 系 在 这 里 被 引 入 。我 们 把 标 准 的 cosine 相 似 度 改 造 成 如 下 的 插 值形 式 ：S（ ii， i）=! Xi、i i、i、i i、+（ l-!）XZIg = lZIp = lr（ tip， tg）max #i X MaxR（ 5）这 样 ， 两 个 文 本 ii和 i之 间 的 相 似 度 就 是 两 部分 共 同 贡 献 的 结 果 ： 组

24、 合 了 标 准 的 cosine 相 似 度 和词 语 关 系 的 相 似 度 。 在 相 似 度 计 算 公 式 （ 5） 中 ，!是调 节 相 似 度 函 数 达 到 最 优 性 能 的 控 制 系 数 ，!的 取值 范 围 为 0， l 。!值 越 大 ， 则 词 语 知 识 对 聚 类 的 影响 越 小 ， 反 之 ， 则 越 大 。!在 实 验 中 是 通 过 三 组 训 练语 料 获 得 的 最 佳!的 平 均 值 。 当 然!最 佳 的 取 值 也可 以 通 过 使 用 EM（ expectation-maximization） 估 计 的 方法 自 动 获 取 ， 这 将 是

25、 我 们 后 续 工 作 的 一 部 分 。 在 插值 式 （ 5） 的 第 二 部 分 ， 分 子 是 行 代 表 i、i， 列 代 表 i、的词 语 -词 语 矩 阵 中 所 有 矩 阵 元 素 之 和 ， tip 6ii， tg6i， 也 就 是 说 分 子 是 分 别 属 于 ii， i的 词 语 构 成的 词 语 对 关 系 值 之 和 。 显 然 其 中 很 多 r（ tip， tg） 是等 于 0 的 ， #i 是 不 为 0 词 语 对 的 个 数 。 而max #i 则 是 所 有 文 本 对 中 关 系 值 不 为 0 的 词 语对 个 数 的 最 大 值 。 这 样ZIg

26、 = lZIp = lr（ tip， tg）max #i 就 是 ii和i所 有 关 系 值 的 “ 均 值 ” 。 可 以 看 出 这 种 均 值 并 不 是真 正 意 义 上 的 均 值 ， 它 只 是 一 个 考 虑 了 文 本 对 中 关系 值 不 为 0 的 词 语 对 个 数 的 广 泛 意 义 上 的 均 值 。MaxR 是 所 有 892575 个 词 语 对 关 系 值 中 最 大 的 。MaxR 是 一 个 规 范 化 因 子 ， 把 平 均 关 系 值ZIg = lZIp = lr（ tip， tg）max #i 映 射 到 0， l 区 间 上 。我 们 在 后 面 的

27、 文 本 聚 类 实 验 中 使 用 了 这 个 新 的相 似 度 函 数 ， 并 和 经 典 的 cosine 相 似 度 作 了 比 较 。对 于!的 估 计 ， 在 本 文 中 使 用 多 点 取 最 优 的 方 法 。即 用 三 组 语 料 ， 分 别 设!的 值 为 0.l， 0.2， 直 到 0.9，第 一 组 中 使 聚 类 最 好 的!l和 后 面 两 组 使 聚 类 效 果最 好 的!2，!3三 者 取 平 均 ， 作 为 后 续 试 验 中 用 到 的!， 用!表 示 这 个 最 优 的!， 即! =!l +!2 +!33（ 6）2 实 验 及 结 果在 l.2 节 中 ，

28、 我 们 给 出 了 考 虑 词 语 间 关 系 的 文本 插 值 相 似 度 。 从 语 言 学 家 的 观 点 来 看 ， 考 虑 词 语之 间 的 关 系 而 不 是 忽 略 它 们 是 合 情 合 理 的 。 在 这 一节 中 ， 我 们 设 计 了 两 个 实 验 ： 一 个 是 获 取 相 似 度 （ 5）中 的 调 节 系 数!的 实 验 最 优 值 ； 另 一 个 就 是 在 使 用最 优!时 测 试 语 料 上 的 聚 类 效 果 ， 采 用 的 是 标 准 I-均 值 的 聚 类 算 法 。 我 们 使 用 的 语 料 是 复 旦 大 学 的 一个 分 类 语 料 库 作

29、为 聚 类 的 对 象 ， 同 时 原 有 的 分 类 信息 被 认 为 是 聚 类 结 果 的 对 照 答 案 。! # 聚 类 结 果 的 评 价给 定 一 个 数 据 集 包 含 I 个 文 本 ， I 个 类 别 。 使用 聚 类 算 法 把 这 个 文 本 集 聚 类 成 I 个 文 本 簇 。 我们 使 用 文 本 对 “ 相 对 位 置 的 正 确 率 ” 来 衡 量 聚 类 结 果的 好 坏 。 也 就 是 在 聚 类 结 果 中 ， 对 于 任 意 两 个 文 本ii和 i而 言 ， 有 两 种 正 确 的 结 果 ：（ l） ii和 i在 答 案中 属 于 同 一 个 类

30、， 在 聚 类 结 果 中 也 被 分 到 了 同 一 个簇 中 ；（ 2） ii和 i在 答 案 中 不 属 于 同 一 个 类 ， 在 聚 类结 果 中 也 被 分 到 了 不 同 的 簇 中 。 这 两 种 情 况 的 文 本对 之 和 与 所 有 文 本 对 个 数 的 比 值 ， 就 是 文 本 对 相 对位 置 的 正 确 率 ， 它 可 用 式Accuracy =ZiZSRight（ ii， i）#（ ii， i）（ 7）计 算 。 当 ii和 i满 足 上 述 两 种 正 确 位 置 关 系 时 ，SRight（ ii， i） 等 于 l。 #（ ii， i） 就 是 文 本

31、集 中 所087高 技 术 通 讯 2007 年 8 月 第 l7 卷 第 8 期有 文 本 对 的 个 数 。 需 要 说 明 的 是 ，（ 7） 式 考 虑 了（ di， dj） ， （ dj， di） 这 种 重 复 的 情 况 。 这 是 一 种 比较 简 单 的 评 价 方 法 ， 对 于 文 本 聚 类 结 果 的 评 价 还 有Eitropy 和 F-Score 14等 评 价 方 法 。2.2 最 优 的 调 节 系 数 （!）我 们 将 使 用 的 分 类 语 料 库 按 各 类 等 分 为 7 组 各不 相 交 的 子 文 本 集 ， 分 别 命 名 为 S1 S7， 每

32、个 约 有400 个 文 本 。 其 中 S1， S2， S3 用 来 估 计!； S4， S5，S6， S7 用 来 比 较 k-均 值 算 法 在 使 用 两 种 相 似 度 函数 时 的 性 能 。在 S1， S2， S3 上 ， 我 们 分 别 设 定!从 0. 1 变 化到 0.9， 看 对 于 S1， S2， S3 最 优 的 聚 类 结 果 出 现 在 什么 样 的!取 值 上 。 因 为 是 在 k-均 值 算 法 下 实 现 的 ，所 以 初 始 的 10 个 聚 类 中 心 （ 语 料 中 已 知 是 10 个 类别 ） 是 随 机 给 定 的 。 为 了 不 使 实 验

33、结 果 有 失 偏 颇 ， 我们 在 每 个!取 值 上 都 做 3 次 实 验 ， 也 就 是 随 机 选 定3 次 初 始 的 聚 类 中 心 ， 看 平 均 的 正 确 率 。 这 样 ， 选 择!的 实 验 结 果 如 表 3 所 示 。表 3 寻 找 聚 类 平 均 准 确 率 最 好 的!（ 在 !1， !2， !3 上 ，!分 别 等 于 0.5， 0.6， 0.6 时 聚 类 正 确 率 最 高 ）0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9S1 0.637171 0.767070 0.798923 0.831280 0.836296 0.819461

34、 0.811651 0.737643 0.782229S2 0.679657 0.715488 0.745584 0.797714 0.777239 0.817640 0.782896 0.776069 0.778653S3 0.728215 0.755288 0.787273 0.795960 0.784845 0.826734 0.786431 0.781482 0.793906根 据 （ 6） 式 ， 最 优 的!为! =!1 +!2 +!33=0.5 + 0.6 + 0.63!0.57。2.3 -均 值 聚 类 结 果k-均 值 算 法 是 一 种 用 于 数 据 聚 类 的 简 单

35、有 效 的方 法 。 对 给 定 类 别 数 （ k） 的 文 本 数 据 而 言 ， 它 的 基本 步 骤 是 先 随 机 选 定 k 个 文 本 向 量 作 为 初 始 的 聚类 中 心 ， 然 后 把 其 余 的 文 本 分 别 分 配 到 和 这 k 个 聚类 中 心 相 似 度 最 大 的 那 个 聚 类 中 心 所 代 表 的 簇 中 ，所 有 文 本 都 分 配 完 后 ， 计 算 这 时 k 个 簇 新 的 聚 类 中心 。 按 照 这 新 的 k 个 聚 类 中 心 ， 再 把 所 有 的 文 本 重新 分 配 到 与 自 己 相 似 度 最 大 的 那 个 聚 类 中 心

36、代 表 的簇 中 。 如 此 迭 代 下 去 ， 直 到 前 后 两 次 k 个 聚 类 中 心不 再 发 生 变 化 或 满 足 一 定 的 迭 代 要 求 ， 算 法 停 止 。有 关 k-均 值 更 多 的 细 节 ， 可 以 参 考 文 献 7 以 及MitcheII 的 著 作 15。这 里 我 们 比 较 了 k-均 值 算 法 中 两 种 不 同 的 相似 度 ： 一 种 就 是 标 准 的 cosine 相 似 度 ； 另 一 种 就 是 结合 了 词 语 间 量 化 关 系 的 插 值 形 式 的 相 似 度 。 在 S4 S7 这 4 个 文 本 集 上 ， 基 于 这 两

37、 种 相 似 度 的 k-均 值聚 类 的 结 果 如 表 4 所 示 。 同 样 的 ， 为 了 尽 量 避 免 初始 随 机 选 取 聚 类 中 心 可 能 带 来 的 问 题 ， 我 们 在 每 个测 试 文 本 集 上 ， 都 取 三 次 初 始 的 10 个 聚 类 中 心 ， 看聚 类 的 平 均 正 确 率 。由 表 4 的 实 验 结 果 可 以 看 到 ， 在 这 4 个 测 试 文本 集 上 ， 使 用 插 值 相 似 度 的 k-均 值 聚 类 结 果 要 明 显好 于 标 准 的 cosine 相 似 度 的 k-均 值 聚 类 ， 平 均 提 高达 到 5. 15%

38、。 这 说 明 对 于 从 词 典 中 按 照 本 文 的 假设 所 获 得 的 词 语 间 量 化 关 系 ， 也 可 以 有 效 地 提 高 聚类 的 性 能 。 需 要 进 一 步 说 明 的 是 ， 我 们 所 用 的 资 源是 非 结 构 化 的 资 源 ， 从 中 获 得 词 语 知 识 ， 比 之 构 造 工程 浩 大 的 ontoIogy 要 省 时 省 力 。表 4 基 于 两 种 不 同 相 似 度 的 -均 值 聚 类 算 法 在!4 !7 四 个 测 试 文 本 集 上 的 比 较S4 S5 S6 S7Cosine 相 似 度 0.796532 0.788585 0.8

39、00167 0.829764插 值 相 似 度 0.836599 0.839404 0.840370 0.8638393 结 论文 本 聚 类 在 信 息 检 索 、 自 然 语 言 处 理 等 领 域 有着 广 泛 的 应 用 。 本 文 在 经 典 的 向 量 空 间 模 型 的 框 架下 ， 通 过 词 语 间 量 化 关 系 ， 构 建 了 一 个 基 于 插 值 的 组合 相 似 度 ， 来 解 决 文 本 聚 类 中 最 核 心 的 文 本 距 离 问题 ， 并 和 传 统 的 余 弦 相 似 度 做 了 对 比 。本 文 加 入 的 词 语 知 识 ， 是 要 考 虑 文 本 间

40、 词 与 词之 间 的 一 种 内 在 关 系 。 这 种 关 系 的 获 取 源 于 我 们 的一 个 基 本 假 设 ： 词 典 的 词 条 和 解 释 它 的 释 义 在 语 义上 是 等 价 的 ， 并 且 据 此 独 立 计 算 词 条 与 其 释 义 词 语之 间 的 量 化 关 系 。在 获 取 词 语 间 的 量 化 关 系 后 ， 分 别 观 察 了 引 入词 语 关 系 与 未 加 入 词 语 知 识 的 聚 类 结 果 。 由 于 引 入的 是 一 个 相 似 度 的 插 值 模 型 ， 本 文 通 过 训 练 语 料 获取 了 最 佳 的 插 值 参 数 。 在 最 后

41、 的 比 较 实 验 中 ， 尽 管187胡 熠 等 ： 基 于 词 典 中 词 语 量 化 关 系 的 中 文 文 本 聚 类 研 究没 有 实 质 上 处 理 向 量 维 数 的 约 简 问 题 ， 但 由 于 加 入了 词 语 知 识 ， 结 果 表 明 插 值 形 式 的 相 似 度 使 得 中 文文 本 聚 类 的 平 均 正 确 率 优 于 仅 使 用 cosine 的 平 均 正确 率 。本 文 的 研 究 说 明 基 于 词 典 词 语 间 的 量 化 关 系 对于 提 高 文 本 聚 类 性 能 有 帮 助 ， 是 一 次 有 意 义 的 尝 试 。但 这 种 量 化 肯 定

42、 不 是 最 好 的 ， 因 为 这 种 词 语 关 系 在语 义 上 显 然 还 是 不 够 深 入 准 确 。 怎 样 进 一 步 从 词 典中 获 取 更 有 价 值 的 词 语 知 识 ， 以 及 怎 样 合 理 地 把 这些 知 识 引 入 到 文 本 聚 类 中 ， 是 我 们 下 一 步 需 要 深 入探 索 的 课 题 。参 考 文 献 1 SaIton G， McGiII M J. Introduction to Modern InformationRetrievaI. New York： McGraw-HiII Inc， 1983 2 Jing L， Ng M K， Xu

43、J， et aI. Subspace cIustering of textdocuments with feature weighting I-means aIgorithm. In：Proc of the 9th Pacific-Asia Conference on KnowIedge Discov-ery and Data Mining， Vietnam， 2005. 802-812 3 Hotho A， Staab S， Stumme G. Wordnet improves text docu-ment cIustering. In： Proc of the Semantic Web W

44、orkshop atthe 26th AnnuaI InternationaI ACM SIGIR Conference， Cana-da. 2003 4 BIoehdorn S， Hotho A. Text cIassification by boosting weakIearners based on terms and concepts. In： Proc of the 4thIEEE InternationaI Conference on Data Mining， UK， 2004.331-334 5 Jing L， Zhou L， Ng M K， et aI. OntoIogy-ba

45、sed distancemeasure for text cIustering. In： Proc of the 4th Workshop onText Mining， 6th SIAM InternationaI Conference on DataMining， 2006 6 李 行 健 . 现 代 汉 语 规 范 词 典 . 北 京 ： 外 语 教 学 与 研 究 出版 社 ， 2004 7 Anderberg M R. CIuster AnaIysis for AppIications. London：Academic Press， 1973 8 Steinbach M， Karypi

46、s G， Kumar V. A comparison of docu-ment cIustering technigues. In： Proc of KDD Workshop onText Mining， 6th ACM SIGKDD InternationaI Conference onData Mining， USA， 2000 9 HindIe D. Noun cIassification from predicate-argument struc-tures. In： Proc of the AnnuaI Meeting of the Association forComputatio

47、naI Linguistics， USA， 1990. 268-275 10 CarabaIIo S. Automatic construction of a hypernym-basednoun hierarch from text. In： Proc of the AnnuaI Meeting ofthe Association for ComputationaI Linguistics， USA， 1999.120-126 11 VeIardi P， Fabriani R， Missikoff M. Using text processingtechnigues to automatic

48、aIIy enrich a domain ontoIogy. In：Proc of the InternationaI Conference on FormaI OntoIogy inInformation Systems， USA， 2001. 270-284 12 Cimiano P， Hotho A， Staab S. Learning concept hierarchiesfrom text corpora using formaI concept anaIysis. Journal ofArtificial Intelligence Research， 2005， 24： 305-3

49、39 13 Han J， Kamber M. Data Mining： Concepts and Technigues.San Francisco： Morgan Kaufmann， 2001 14 Zhao Y， Karypis G. Comparison of aggIomerative and parti-tionaI document cIustering aIgorithms： TechnicaI report . U-niversity of Minnesota， 2002. 2-14 15 MitcheII T M. Machine Learning. Boston： McGraw-HiII，1997. 191-196Research on guantified lexical relationship within the dictionarybased chinese text clusteringHu Yi， Lu Ruzh