总 第 13 期 011 年 第 1 期 已 有 工 作 采 用 基 于 密 度 的 OPTICS 算 法 [1] 层 次 聚 [] 类 算 法 和 自 组 织 映 射 网 络 (SOM) [3] 等 方 法 研 究 了 话 题 的 聚 类, 但 这 些 方 法 均 是 批 学 习 (BatchLe

现 代 图 书 情 报 技 术 版 权 所 有, 欢 迎 下 载 引 用! 请 注 明 引 用 地 址 : 基 于 Single-Pas 的 网 络 话 题 在 线 聚 类 方 法 研 究 [J], 现 代 图 书 情 报 技 术,011(1):5-57. 情 报 分 析 与 研 究 基 于 Single-Pas 的 网 络 话 题 在 线 聚 类 方 法 研 究 1, 朱 恒 民 朱 卫 未 1 ( 南 京 大 学 信 息 管 理 系 南 京 10093) ( 南 京 邮 电 大 学 经 济 与 管 理 学 院 南 京 10046) 摘 要 基 于 Single-Pas 算 法 思 想, 研 究 网 络 话 题 的 在 线 聚 类 方 法, 以 期 及 时 捕 捉 网 络 信 息 的 动 态 变 化 在 分 析 该 方 法 聚 类 流 程 的 基 础 上, 重 点 研 究 网 络 动 态 信 息 流 的 文 本 特 征 抽 取 和 权 重 计 算 方 法, 以 及 话 题 类 表 示 和 更 新 等 关 键 问 题, 设 计 实 验 对 比 分 析 不 同 的 标 题 中 特 征 加 权 系 数 特 征 权 重 计 算 和 标 准 化 方 法 以 及 话 题 类 向 量 维 度 对 话 题 聚 类 质 量 和 时 间 效 率 的 影 响 关 键 词 网 络 舆 情 话 题 挖 掘 在 线 聚 类 Single-Pas 分 类 号 G353.1 StudyonWebTopicOnlineClusteringApproachBasedonSingle-Pas Algorithm ZhuHengmin 1, ZhuWeiwei 1 (DepartmentofInformationManagement,NanjingUniversity,Nanjing10093,China) (ColegeofEconomics&Management,NanjingUniversityofPosts&Telecommunications,Nanjing10046,China) Abstract InordertogetdynamicsofWebinformationtimely,anonlineWebtopicclusteringapproachbasedonSingle -Pasalgorithmisresearched.Theclusteringprocesofthisapproachisanalyzedfirstly,andthekeyproblemsincluding extractingandweightcalculatingoffeaturesaswelasrepresentationandmodificationoftopicclusteraredeliberated.ex perimentisdesignedtocomparetheefectsofdiferentweightfactoroffeaturesintitle,weightcalculatingandnormalizing methodsoffeaturesandthevectordimensionoftopicclusteronclusterqualityandtimeeficiency. Keywords Internetpublicopinion Topicmining Onlineclustering Single-Pas 1 引 言 网 络 是 一 个 涉 及 面 广 形 式 多 样 更 新 快 捷 的 动 态 信 息 流, 网 络 话 题 一 旦 激 起 广 大 网 民 的 关 注 和 热 烈 讨 论, 短 时 间 内 将 产 生 大 量 的 网 络 相 关 报 道 因 此, 迫 切 需 要 一 种 高 效 的 能 够 及 时 捕 捉 网 络 热 点 的 话 题 聚 类 方 法, 这 也 是 网 络 舆 情 监 控 和 预 警 的 一 项 重 要 内 容 收 稿 日 期 :011-09-6 收 修 改 稿 日 期 :011-11-17 本 文 系 江 苏 省 社 会 科 学 基 金 项 目 网 络 舆 论 危 机 的 生 成 与 预 警 机 制 研 究 ( 项 目 编 号 :10TQC009) 江 苏 省 教 育 厅 高 校 哲 学 社 会 科 学 项 目 互 联 网 舆 情 演 化 的 动 态 网 络 模 型 研 究 ( 项 目 编 号 :011SJB870006) 和 南 京 邮 电 大 学 青 蓝 计 划 网 络 舆 情 热 点 发 现 及 动 态 预 警 研 究 ( 项 目 编 号 :NY10055) 的 研 究 成 果 之 一 5 现 代 图 书 情 报 技 术

总 第 13 期 011 年 第 1 期 已 有 工 作 采 用 基 于 密 度 的 OPTICS 算 法 [1] 层 次 聚 [] 类 算 法 和 自 组 织 映 射 网 络 (SOM) [3] 等 方 法 研 究 了 话 题 的 聚 类, 但 这 些 方 法 均 是 批 学 习 (BatchLearning) 算 法, 即 算 法 是 在 整 个 文 档 集 合 上 进 行 聚 类 运 算 由 于 网 络 报 道 是 依 时 间 顺 序 不 断 到 达 的 动 态 信 息 流, 批 学 习 算 法 并 不 能 及 时 地 为 逐 个 到 来 的 网 络 报 道 进 行 话 题 聚 类 针 对 网 络 报 道 这 种 流 式 数 据, 许 多 学 者 设 计 了 [4] 各 种 各 样 的 增 量 算 法 :Guha 等 提 出 了 一 种 局 部 聚 类 方 法, 它 将 数 据 流 按 时 间 顺 序 分 成 若 干 数 据 小 块, 对 每 [5] 一 小 块 进 行 局 部 聚 类 ;Gupta 等 提 出 了 一 个 基 于 Sin gle-pas 的 聚 类 算 法 GenIc, 该 算 法 同 样 是 把 数 据 流 划 分 成 不 同 的 数 据 块, 通 过 评 价 类 中 心 的 合 适 度 来 决 [6] 定 是 保 留 或 是 删 除 该 类 中 心 ; 税 仪 冬 等 指 出 基 于 Single-Pas 的 话 题 聚 类 方 法 具 有 明 显 的 次 序 依 赖 缺 点, 提 出 了 先 聚 类, 再 周 期 分 类 的 话 题 聚 类 方 法, 以 提 [7] 高 话 题 簇 的 识 别 精 度 ; 胡 迁 乔 基 于 Single-Pas 思 想 设 计 了 网 络 论 坛 热 点 话 题 的 聚 类 算 法, 该 算 法 需 要 先 采 集 主 帖, 通 过 遍 历 统 计 出 单 词 文 档 频 率, 然 后 基 于 Single-Pas 思 想 进 行 话 题 聚 类 综 上 可 知, 由 于 具 有 增 量 处 理 特 性, 基 于 Single-Pas 思 想 的 聚 类 方 法 被 一 些 学 者 用 于 文 本 的 增 量 聚 类, 但 是 在 聚 类 过 程 中 上 述 文 献 多 是 采 用 传 统 的 文 本 处 理 方 法, 缺 乏 对 传 统 方 法 适 用 于 动 态 信 息 流 的 有 效 性 进 行 讨 论 和 实 验 分 析 在 基 于 Single-Pas 的 网 络 话 题 在 线 聚 类 过 程 中, 适 合 网 络 动 态 信 息 流 的 文 档 特 征 提 取 特 征 项 的 权 重 计 算, 以 及 话 题 类 的 科 学 表 示 和 动 态 调 整, 是 该 方 法 的 关 键 环 节 一 些 文 本 处 理 方 法 的 选 取 和 方 法 中 系 数 的 选 择, 以 及 对 传 统 方 法 的 改 进 直 接 影 响 了 话 题 聚 类 质 量 和 时 间 效 率, 本 文 结 合 理 论 分 析 和 实 验 评 价 对 此 展 开 研 究 Single-Pas 算 法 基 本 思 想 Single-Pas 算 法 又 称 单 通 道 法 或 单 遍 法, 是 流 式 数 据 聚 类 的 经 典 方 法 对 于 依 次 到 达 的 数 据 流, 该 方 法 按 输 入 顺 序 每 次 处 理 一 个 数 据, 依 据 当 前 数 据 与 已 有 类 的 匹 配 度 大 小, 将 该 数 据 判 为 已 有 类 或 者 创 建 一 个 新 的 数 据 类, 实 现 流 式 数 据 的 增 量 和 动 态 聚 类 Single-Pas 算 法 是 一 种 增 量 算 法, 适 合 对 流 数 据 进 行 挖 掘, 而 且 算 法 的 时 间 效 率 高 ; 不 足 之 处 主 要 表 现 在 该 方 法 具 有 输 入 次 序 依 赖 特 性, 即 对 于 同 一 聚 类 对 象 按 不 同 的 次 序 输 入, 会 出 现 不 同 的 聚 类 结 果 3 基 于 Single-Pas 的 网 络 话 题 在 线 聚 类 方 法 基 于 Single-Pas 的 网 络 话 题 在 线 聚 类 方 法 的 流 程 如 图 1 所 示 : 图 1 基 于 Single-Pas 的 网 络 话 题 在 线 聚 类 方 法 的 流 程 对 逐 个 到 来 的 网 页 d i 进 行 文 本 特 征 抽 取, 并 计 算 每 个 特 征 的 权 重, 从 而 构 建 出 文 本 d i 的 向 量 空 间 模 型 (VSM); 然 后 采 用 传 统 的 夹 角 余 弦 公 式 计 算 d i 同 已 有 话 题 类 向 量 之 间 的 距 离, 比 对 相 似 度 阈 值 将 其 判 为 已 有 类 或 新 创 建 的 类 c j ; 最 后, 基 于 d i 的 特 征 向 量 更 新 话 题 类 c j 的 表 示 向 量 其 中, 动 态 文 档 的 特 征 抽 取 特 征 权 重 计 算 以 及 话 题 类 的 表 示 与 调 整 是 该 方 法 的 关 键 环 节 3.1 网 络 文 本 的 向 量 空 间 模 型 网 络 文 本 采 用 传 统 的 向 量 空 间 模 型 来 表 示, 即 网 络 文 本 d i 可 用 形 式 化 的 方 式 来 描 述 :d i =(1,w i1 ),,w i ),,n,w in )) 其 中,t ij 代 表 文 本 内 容 的 特 征 项, 即 文 本 中 切 分 出 的 词 ;w ij 是 特 征 项 t ij 的 权 重 因 此, 针 对 网 络 动 态 信 息 流 特 点, 研 究 文 本 特 征 项 抽 取 及 其 权 重 计 算 是 构 建 网 络 文 本 向 量 空 间 模 型 的 关 键 步 骤 (1) 网 络 文 本 的 特 征 项 抽 取 由 于 汉 语 中 词 与 词 之 间 没 有 明 显 的 分 隔 标 记, 一 般 采 用 分 词 技 术 来 完 成 文 本 特 征 项 的 抽 取 本 文 采 用 中 国 科 学 院 计 算 技 术 研 究 所 的 汉 语 词 法 分 析 系 统 ICT CLAS011 对 网 络 文 本 内 容 进 行 分 词 处 理 ICT CLAS011 采 用 了 层 叠 隐 马 尔 可 夫 模 型 和 PDAT 大 规 模 知 识 库 管 理 技 术, 在 分 词 高 精 度 和 高 速 度 方 面 取 得 了 较 大 突 破 网 络 文 本 经 过 ICTCLAS011 分 词 后 的 词 向 量 空 间 维 度 很 大, 将 会 给 后 续 处 理 带 来 较 大 的 时 间 消 耗 ; 而 且, 切 分 出 的 特 征 词 中 包 含 了 大 量 的 虚 词 和 无 实 际 含 义 的 词, 它 们 对 话 题 的 描 述 与 识 别 不 起 任 何 作 用 因 XIANDAITUSHUQINGBAOJISHU 53

情 报 分 析 与 研 究 此, 本 文 在 分 词 过 程 中 根 据 词 性 和 词 的 长 度 过 滤 掉 助 词 介 词 连 词 等 虚 词 以 及 词 长 较 短 的 无 实 际 意 义 词 网 络 文 本 一 般 包 含 标 题 和 正 文 两 部 分 内 容, 标 题 往 往 点 出 了 报 道 的 主 题, 是 网 络 文 本 的 核 心 为 了 准 确 地 描 述 出 网 络 文 本 的 特 征, 本 文 分 别 抽 取 出 标 题 和 正 文 中 的 特 征 词, 在 统 计 特 征 项 词 频 时, 对 来 自 标 题 中 的 特 征 项 词 频 乘 上 一 个 加 权 系 数 α(α 1), 即 文 本 特 征 项 t i 的 词 频 f )=α f t )+ f c ), 其 中 f t ) f c ) 分 别 为 特 征 项 t i 在 标 题 和 正 文 中 的 词 频 如 果 α 取 值 过 小 将 不 足 以 突 出 标 题 中 特 征 项 的 重 要 性 ; 如 果 取 值 太 大, 将 会 抑 制 正 文 中 绝 大 部 分 特 征 项 对 文 本 主 题 的 描 述 能 力 因 此,α 的 取 值 直 接 关 系 到 话 题 的 聚 类 质 量, 实 验 将 对 其 进 行 讨 论 () 动 态 文 本 的 特 征 权 重 计 算 TF-IDF 是 计 算 文 本 特 征 权 重 的 常 见 方 法, 其 中 TF 为 特 征 项 在 文 档 中 出 现 的 频 率,IDF 为 特 征 项 的 反 引 文 档 频 率, 即 在 文 档 集 中 包 含 特 征 项 的 文 档 数 目 TF 越 大, 说 明 特 征 项 在 文 档 中 越 重 要 ;IDF 越 大, 即 特 征 项 在 文 集 中 的 多 篇 文 档 中 出 现, 这 反 映 出 该 特 征 项 并 不 是 本 文 档 的 独 有 特 征, 在 聚 类 过 程 中 对 类 的 划 分 所 起 的 作 用 并 不 大 因 此,TF-IDF 方 法 中 特 征 项 的 权 重 可 描 述 为 : w i =f a (TF i ) f b (N/IDF i ) (1) 其 中,N 为 文 集 中 的 文 档 数 目,f a 和 f b 分 别 是 关 于 TF 和 IDF 的 函 数 但 是, 网 络 信 息 流 是 依 据 时 间 顺 序 逐 个 到 达 的, 计 算 信 息 流 中 某 个 文 档 d i 的 特 征 项 权 重 时, 只 能 采 用 d i 及 其 之 前 到 达 的 文 档 构 成 的 文 档 集 来 计 算 特 征 项 的 IDF 这 样 每 篇 文 档 在 计 算 特 征 项 的 IDF 时 所 采 用 的 文 档 集 都 不 一 样, 影 响 了 IDF 计 算 的 准 确 性, 增 大 了 聚 类 结 果 对 网 络 文 档 输 入 顺 序 的 敏 感 性, 最 终 影 响 话 题 聚 类 的 质 量 因 此, 有 必 要 对 TF-IDF 方 法 应 用 于 网 络 信 息 流 在 线 聚 类 的 有 效 性 进 行 评 价 网 络 文 本 的 内 容 长 短 不 一, 内 容 较 长 的 文 档 中 特 征 项 出 现 的 词 频 往 往 较 大, 因 此 特 征 项 的 权 重 数 值 也 较 大 为 了 避 免 网 络 文 本 内 容 长 短 对 话 题 聚 类 结 果 的 影 响, 需 要 对 特 征 项 的 权 重 数 据 进 行 标 准 化 处 理 常 见 的 数 据 标 准 化 方 法 有 比 例 法 和 最 小 最 大 值 法, 假 设 网 络 文 档 d i 的 特 征 权 重 向 量 为 (w i1,w i,,w in ), 则 采 用 比 例 法 和 最 小 最 大 值 法 标 准 化 处 理 特 征 权 重 的 公 式 分 别 如 下 所 示 : w ij = w ij k w ik () w ij = w ij-w min w max -w min (3) 式 () 和 式 (3) 均 是 将 每 个 权 重 分 量 标 准 化 为 [0, 1] 内, 其 中 w max 和 w min 分 别 为 权 重 分 量 中 的 最 大 值 和 最 小 值 实 验 将 讨 论 上 述 两 种 数 据 标 准 化 方 法 对 话 题 聚 类 质 量 的 影 响 3. 话 题 类 的 表 示 和 动 态 调 整 话 题 类 的 表 示 一 般 有 质 心 向 量 和 中 心 向 量 两 种 方 法 中 心 向 量 法 是 指 话 题 类 由 其 中 一 个 文 档 作 为 中 心 向 量 来 表 示, 该 方 法 需 要 大 量 时 间 搜 索 合 适 的 中 心 向 量, 中 心 向 量 选 择 不 准 确 将 会 导 致 所 有 后 续 增 量 聚 类 出 错 质 心 向 量 法 是 采 用 类 中 所 有 文 档 向 量 的 平 均 值 来 表 示 话 题 类, 该 方 法 对 噪 声 和 孤 立 点 敏 感, 但 不 会 存 在 一 错 皆 错 的 问 题 考 虑 到 网 络 话 题 的 在 线 聚 类 需 要 较 高 的 时 间 效 率, 且 质 心 向 量 可 以 被 增 量 产 生, 本 文 采 用 质 心 向 量 法 表 示 话 题 类, 即 话 题 类 c j 在 t k 时 刻 的 质 心 向 量 c(c j,t k ) 可 表 达 如 下 : c(c j,t k )= 1 Ni=1 N d i (4) 其 中,N 为 该 话 题 类 的 文 档 数 由 于 话 题 类 的 质 心 向 量 是 类 中 所 有 文 档 的 特 征 向 量 叠 加 而 成, 因 此 向 量 维 数 非 常 高, 增 加 了 计 算 的 复 杂 度 为 了 限 制 话 题 类 向 量 的 维 数, 本 文 对 质 心 向 量 法 进 行 了 改 进, 取 质 心 向 量 中 权 重 较 大 的 前 N d 个 特 征 项 构 成 的 向 量 来 表 示 话 题 类 N d 的 不 同 取 值 将 会 影 响 到 话 题 聚 类 的 质 量 和 时 间 效 率, 实 验 将 对 N d 取 值 进 行 讨 论 在 线 聚 类 中 话 题 类 随 着 文 档 的 添 加 而 不 断 更 新, 因 此 话 题 类 向 量 也 要 动 态 更 新, 本 文 依 据 式 (4) 推 导 出 话 题 类 向 量 的 增 量 更 新 公 式, 如 下 所 示 : c(c j,t k+1 )= N-1 N c(c j,t k )+ 1 N d k+1 (5) 其 中,N d k+1 分 别 为 t k+1 时 刻 话 题 类 c j 中 的 文 档 数 量 和 此 时 刻 到 达 的 文 档 向 量 由 于 限 制 了 话 题 类 向 量 的 维 数, 话 题 类 表 示 向 量 只 是 其 质 心 向 量 的 一 部 分 同 网 络 文 本 向 量 一 样, 话 题 类 向 量 也 需 要 数 据 标 准 化 处 理, 以 避 免 向 量 权 重 数 值 较 大 的 话 题 类 主 导 着 聚 类 结 果 3.3 基 于 Single-Pas 的 网 络 话 题 在 线 聚 类 算 法 基 于 Single-Pas 的 网 络 话 题 在 线 聚 类 的 主 要 步 54 现 代 图 书 情 报 技 术

总 第 13 期 011 年 第 1 期 骤 如 下 : 算 法 1ClusterBySingle-Pas() Input: 网 络 动 态 信 息 流 d 1,d,,d n, 内 容 相 似 度 阈 值 T c, 以 及 话 题 类 的 向 量 维 度 N d ; Output: 话 题 类 c 1,c,,c k 1for 每 个 时 刻 t i 到 达 的 一 篇 网 络 报 道 d i do{ 3 通 过 特 征 抽 取 特 征 权 重 计 算 标 准 化 处 理 构 建 出 d i 的 向 量 空 间 模 型 ; if 尚 不 存 在 话 题 类 then{ 4 创 建 新 话 题 类 c 1, 并 将 d i c 1 ; 5 c(c 1,t i )= d i 中 依 据 特 征 权 重 大 小 取 其 前 N d 个 分 量, 标 准 化 处 理 ; 6 7 }else{ for 已 有 的 每 个 话 题 类 c j do{ 8 计 算 d i,c j 的 相 似 度 sim(d i,c j );} 9 10 瑏 瑡 瑏 瑢 瑏 瑣 令 maxs=max (sim(d i,c j )),maxc=c j sim(di,c j j )=maxs; IfmaxS>=T c then{ d i maxc; 依 据 式 (5) 调 整 c(maxc,t i ), 依 据 特 征 权 重 大 小 取 其 前 N d 个 分 量, 标 准 化 处 理 ; }else{ 瑏 瑤 创 建 新 话 题 类 c new, 并 将 d i c new ; 瑏 瑥 c(c new,t i )=d i 中 依 据 特 征 权 重 大 小 取 其 前 N d 个 分 量, 标 准 化 处 理 ; 瑏 瑦 } 瑏 瑧 }i++; 瑏 瑨 }return 所 有 的 话 题 类 c 1,c,,c k. 算 法 1 中, 步 骤 1 - 瑏 瑧 完 成 网 络 动 态 信 息 流 中 一 篇 文 档 d i 的 处 理 和 判 类 过 程 ; 其 中 步 骤 3-5 完 成 信 息 流 中 第 1 篇 文 档 的 判 类 ; 步 骤 7-9 识 别 出 与 d i 最 相 似 的 已 有 话 题 类 ; 步 骤 10 - 瑏 瑢 是 当 最 大 相 似 度 大 于 或 等 于 阈 值 时, 将 d i 判 给 已 存 在 的 类, 并 调 整 类 表 示 ( 话 题 1) 京 沪 高 铁 ( 话 题 ) 城 市 内 涝 ( 话 题 3) 郭 美 美 事 件 ( 话 题 4) 高 考 招 生 ( 话 题 5) 和 庆 祝 建 党 90 周 年 ( 话 题 6)6 个 热 门 话 题 的 45 个 网 页 实 验 文 集 的 获 取 是 先 通 过 设 置 关 键 词 时 间 段 和 来 源 网 站 等 检 索 条 件, 调 用 通 用 搜 索 引 擎 完 成 相 关 话 题 的 检 索, 然 后 利 用 网 络 爬 虫 采 集 通 用 搜 索 引 擎 返 回 的 检 索 结 果 ; 最 后 将 采 集 下 来 的 文 集 按 网 页 创 建 时 间 的 先 后 顺 序 进 行 排 序, 模 拟 出 实 验 中 的 网 络 信 息 流 实 验 中 网 络 爬 虫 和 基 于 Single-Pas 的 网 络 话 题 在 线 聚 类 方 法 均 在 Visu alc++6.0 开 发 环 境 下 实 现 实 验 采 用 准 确 率 P 召 回 率 R 和 综 合 指 标 F 来 评 价 方 法 的 话 题 聚 类 质 量, 其 中 P=n c /n a,r=n c /n t,n a 表 示 方 法 判 断 出 与 网 络 话 题 相 关 的 文 档 数 目,n c 为 n a 个 文 档 中 正 确 反 映 该 话 题 的 文 档 数 目,n t 表 示 由 人 工 判 断 出 实 验 文 集 中 与 该 话 题 相 关 的 所 有 文 档 数 目 ;F= P R /(P+R) 实 验 分 析 了 标 题 中 特 征 加 权 系 数 特 征 权 重 计 算 方 法 和 标 准 化 方 法 对 话 题 聚 类 质 量 的 影 响, 并 比 较 了 不 同 的 话 题 类 向 量 维 度 N d 对 话 题 聚 类 质 量 和 时 间 效 率 的 影 响 4.1 标 题 中 特 征 加 权 系 数 α 对 话 题 聚 类 质 量 的 影 响 本 实 验 比 较 了 标 题 中 特 征 加 权 系 数 α 的 不 同 取 值 对 话 题 聚 类 质 量 的 影 响, 实 验 结 果 如 图 所 示 : 向 量 ; 步 骤 瑏 瑣 - 瑏 瑦 是 当 最 大 相 似 度 小 于 阈 值 时, 以 d i 为 成 员 创 建 一 个 新 类 令 n 为 信 息 流 中 的 文 本 数 量,k 为 算 法 最 终 聚 出 话 题 类 的 数 目, 则 算 法 1 的 计 算 复 杂 性 是 O(nk), 其 计 算 开 销 远 低 于 其 他 聚 类 算 法 [1-3], 因 此 基 于 Single- Pas 的 网 络 话 题 在 线 聚 类 方 法 具 有 较 高 的 时 间 效 率 4 实 验 分 析 实 验 文 集 选 用 011 年 6 月 1 日 至 7 月 4 日 期 间 网 易 新 闻 (htp://news.163.com) 中 关 于 高 速 公 路 收 费 图 α 对 话 题 聚 类 质 量 的 影 响 分 析 可 以 看 出,α 对 话 题 聚 类 质 量 的 影 响 主 要 体 现 在 算 法 的 召 回 率 R 上, 当 α=3 时, 聚 类 算 法 的 R 和 F 值 最 大, 取 值 过 小 或 者 过 大 都 使 得 算 法 召 回 率 R 下 降, 因 此 本 实 验 中 α 取 值 为 3 4. 特 征 权 重 计 算 方 法 对 话 题 聚 类 质 量 的 影 响 面 向 网 络 动 态 信 息 流 的 话 题 在 线 聚 类 方 法 中, 由 于 不 能 在 一 个 统 一 的 文 集 下 计 算 反 引 文 档 频 率, 话 题 XIANDAITUSHUQINGBAOJISHU 55

情 报 分 析 与 研 究 聚 类 质 量 将 会 受 到 影 响, 且 对 文 档 输 入 顺 序 的 敏 感 性 将 会 增 强 考 虑 到 在 文 本 特 征 抽 取 时 依 据 词 性 和 词 长 过 滤 掉 无 意 义 的 词, 那 么 过 滤 后 特 征 词 的 词 频 能 够 反 映 该 特 征 词 的 重 要 程 度, 因 此 本 实 验 将 TF-IDF 方 法 ( 特 征 权 重 计 算 方 法 见 式 (6) [6] ) 同 仅 考 虑 词 频 的 方 法 ( 记 为 TF, 权 重 计 算 方 法 见 式 (7)) 进 行 了 对 比 w i =TF i ln(0.01+idf i ) (6) w i =ln(1+tf i ) (7) 由 于 两 种 特 征 权 重 计 算 方 法 得 出 的 文 档 与 话 题 类 的 内 容 相 似 度 对 阈 值 的 敏 感 程 度 不 一 样, 采 用 式 (6) 和 式 (7) 的 实 验 只 有 在 阈 值 分 别 达 到 0.043 和 0.119 时, 才 能 有 效 地 区 分 各 个 话 题 类, 因 此 实 验 分 别 以 0.043 和 0.119 为 阈 值 起 点 以 0.01 为 步 距, 选 择 5 个 不 同 的 阈 值 对 话 题 聚 类 质 量 和 文 档 顺 序 的 敏 感 性 进 行 了 对 比, 实 验 结 果 如 图 3 至 图 5 所 示 : 图 3 两 种 特 征 权 重 计 算 方 法 对 话 题 聚 类 质 量 的 影 响 图 5 TF 方 法 在 不 同 的 文 档 输 入 顺 序 下 的 聚 类 质 量 频 的 方 法 在 召 回 率 上 具 有 一 定 优 势 从 综 合 指 标 F 来 看, 除 第 个 阈 值 水 平 外, 两 种 方 法 的 F 值 非 常 接 近 对 比 图 4 和 图 5 中 两 种 方 法 在 不 同 文 档 输 入 顺 序 下 的 话 题 聚 类 质 量,TF-IDF 方 法 对 文 档 输 入 顺 序 的 敏 感 性 要 小 于 仅 仅 考 虑 词 频 的 方 法, 在 话 题 和 话 题 6 上 表 现 尤 为 明 显 综 合 实 验 结 果,TF-IDF 方 法 在 面 向 网 络 动 态 信 息 流 的 话 题 在 线 聚 类 方 法 中 具 有 良 好 表 现 4.3 特 征 权 重 标 准 化 方 法 对 话 题 聚 类 质 量 的 影 响 本 实 验 比 较 了 比 例 法 ( 记 为 Perc) 和 最 小 最 大 值 法 ( 记 为 Min-Max) 两 种 数 据 标 准 化 方 法 对 话 题 聚 类 质 量 的 影 响 由 于 采 用 两 种 方 法 计 算 出 的 文 档 与 话 题 类 的 内 容 相 似 度 对 阈 值 敏 感 程 度 不 一 样, 采 用 式 () 和 式 (3) 的 实 验 只 有 在 阈 值 分 别 达 到 0.043 和 0.030 时, 才 能 有 效 地 区 分 各 个 话 题 类 因 此 实 验 分 别 以 0.043 和 0.030 为 阈 值 起 点 以 0.01 为 步 距, 选 择 5 个 不 同 的 阈 值 对 话 题 聚 类 质 量 进 行 对 比, 实 验 结 果 如 图 6 所 示 : 图 4 TF-IDF 方 法 在 不 同 的 文 档 输 入 顺 序 下 的 聚 类 质 量 从 图 3 可 以 看 出, 两 种 特 征 权 重 计 算 方 法 在 各 个 阈 值 水 平 上 都 取 得 了 较 高 的 话 题 聚 类 准 确 率, 相 对 来 说,TF-IDF 方 法 在 准 确 率 上 略 微 占 优, 而 仅 仅 考 虑 词 图 6 两 种 特 征 权 重 标 准 化 方 法 对 话 题 聚 类 质 量 的 影 响 56 现 代 图 书 情 报 技 术

总 第 13 期 011 年 第 1 期 图 6 中 反 映 出 采 用 比 例 法 的 话 题 聚 类 算 法 在 准 确 率 P 召 回 率 R 和 综 合 指 标 F 上 均 高 于 最 小 最 大 值 法 4.4 话 题 类 向 量 维 度 对 话 题 聚 类 质 量 和 时 间 效 率 的 影 响 话 题 类 向 量 维 度 N d 的 选 取 将 会 影 响 到 话 题 聚 类 的 质 量 和 时 间 效 率 图 7 对 比 了 N d 不 同 取 值 时 的 话 题 聚 类 质 量, 其 中 N d =3781 是 指 实 验 中 若 不 限 制 话 题 类 向 量 维 数 时, 所 聚 出 话 题 类 向 量 的 最 大 维 度 图 7 N d 对 话 题 聚 类 质 量 的 影 响 分 析 从 图 7 中 可 看 出, 话 题 类 向 量 维 度 N d 对 算 法 召 回 率 影 响 较 大, 随 着 N d 取 值 增 大, 算 法 召 回 率 呈 现 先 快 速 后 缓 慢 地 上 升 这 是 因 为, 话 题 类 向 量 维 度 越 大, 包 含 的 文 本 特 征 就 越 多, 将 有 更 多 的 文 档 因 为 具 有 与 话 题 类 向 量 相 同 的 特 征 而 被 聚 为 一 类 图 8 N d 对 话 题 聚 类 时 间 效 率 的 影 响 分 析 图 8 对 比 了 N d 不 同 取 值 时 话 题 聚 类 的 时 间 效 率 由 于 算 法 运 行 时 间 受 到 计 算 机 硬 件 和 软 件 资 源 的 影 响, 纵 坐 标 刻 画 的 是 算 法 运 行 时 间 与 N d =300 时 算 法 运 行 时 间 的 比 值 图 7 反 映 出 当 N d 50 时, 话 题 聚 类 质 量 增 长 得 非 常 缓 慢, 但 从 图 8 中 可 看 出, 如 果 不 对 话 题 类 向 量 维 度 加 以 限 制, 话 题 聚 类 所 耗 费 的 时 间 明 显 增 加 因 此, 选 择 合 适 的 N d 来 限 制 话 题 类 向 量 维 度 非 常 有 必 要, 它 可 以 在 几 乎 不 损 失 聚 类 质 量 的 情 况 下 显 著 提 高 算 法 的 时 间 效 率 5 结 语 本 文 对 基 于 Single-Pas 的 网 络 话 题 在 线 聚 类 方 法 关 键 问 题 展 开 了 研 究 针 对 网 络 文 本 具 有 标 题 和 正 文 部 分 这 一 特 点, 通 过 为 标 题 中 特 征 项 加 权 来 抽 取 出 准 确 的 文 本 特 征, 并 通 过 实 验 评 价 出 合 适 的 加 权 系 数 ; 讨 论 了 动 态 信 息 流 环 境 下 常 见 文 本 特 征 权 重 计 算 方 法 存 在 的 问 题, 结 合 实 验 对 不 同 的 特 征 权 重 计 算 和 标 准 化 方 法 进 行 评 价 ; 对 话 题 类 的 质 心 向 量 表 示 法 进 行 了 改 进, 提 出 选 取 质 心 向 量 中 权 重 较 大 的 前 N d 个 特 征 项 构 成 的 向 量 来 代 表 话 题 类, 并 通 过 实 验 验 证 了 改 进 方 法 的 有 效 性 参 考 文 献 : [1] 王 伟, 许 鑫. 基 于 聚 类 的 网 络 舆 情 热 点 发 现 及 分 析 [J]. 现 代 图 书 情 报 技 术,009(3):74-79. []TrieschniggD,KraaijW.ScalableHierarchicalTopicDetection: ExploringaSampleBasedApproach[C].In:Procedingsofthe 8thAnnualInternationalACM SIGIRConferenceonResearchand DevelopmentinInformationRetrieval,Salvador,Brazil.005:655-656. [3] 朱 恒 民, 马 静, 黄 卫 东. 基 于 领 域 本 体 的 SOM 文 本 逐 层 聚 类 方 法 [J]. 情 报 学 报,008,7(6):845-850. [4]GuhaS,MishraN,MotwaniR,etal.ClusteringDataStreams [C].In:ProcedingsoftheAnnualSymposium onfoundationsof ComputerScience.000:359-366. [5]GuptaC,GrosmanRL.GenIc:ASinglePasGeneralizedIncre mentalalgorithmforclustering[c].in:procedingsofthe004si AM InternationalConferenceonDataMining,Philadelphia.004: 137-153. [6] 税 仪 冬, 瞿 有 利, 黄 厚 宽. 周 期 分 类 和 Single-Pas 聚 类 相 结 合 的 话 题 识 别 与 跟 踪 方 法 [J]. 北 京 交 通 大 学 学 报,009,33(5): 85-89. [7] 胡 迁 乔. 面 向 中 文 论 坛 的 网 络 舆 情 倾 向 性 分 析 [D]. 武 汉 : 华 中 科 技 大 学,009. ( 作 者 E-mail:hengminzhu@163.com) XIANDAITUSHUQINGBAOJISHU 57