［ ］ ９－１ ０
２ 基于层次聚类的话题检测算法
２． １ 层次聚类算法设计原理 层次聚类算法是一种非常经典的聚类算法 ． 广泛 应用于文本识别 、 文本 分 类 等 相 关 应 用 领 域 ， 并且通 过长时间的应用表明 ， 层次聚类算法在文本识别和分
３ １ ４ － 类方面具有很好的应用价值 １ ． ［ ］
［ ］ ［］ ［］
赵 艳 红， 聂哲提出一种针 ．
＊
收稿日期 ： ２ ０ １ ２ １ ０ １ ２． － － （ ） 基金项目 ： 广西哲学社会科学课题 “ 基于物联网技术的图书馆服务模式研究 ” １ １ Ｂ ＴＱ ０ ０ １ ． ， 作者简介 ： 潘大庆 （ 男， 广西柳州人 ， 柳州市委党校副教授 ， 工程硕士 ， 研究方向 ： 计算机网络安全 ． １ ９ ７ ０ －）
关键词 ：敏 感 话 题 ； 层次聚类； 检测； 微博； 词频 ； 词性 中图分类号 ： Ｔ Ｐ １ ８ 文献标识码 ：Ａ （ ） 文章编号 ： １ ６ ７ ３－８ ４ ６ ２ ２ ０ １ ２ ０ ４－０ ０ ５ ６－０ ４
０ 引言
随着信息时代的迅猛发展 ， 网络舆论对国家和社 会的稳定与发展有着十分重要的影响作用 １－２ ． 而近 年来 ， 在网络上新出现的微博这种信息发布和传播方 式， 在很短的时间内 受 到 广 大 用 户 的 青 睐 ， 并且利用 微博进行信息的发 布 已 经 成 为 当 前 形 成 和 传 播 社 会 为了能够对通过微博发布和传 舆论的一个重要途径 ． 播的社会舆论更好地跟踪和识别 ， 有必要开展对微博 舆论的监测和识别算法的研究 ． 目 前， 针对网络上的娱评分析和研究的相关工 作， 在数年前已经有一系列的研究成果 ． 比如 ：洪宇 ， 张宇等通过介绍话 题 检 测 与 跟 踪 的 研 究 背 景 、 任 务、 定义 、 评 定 方 法 以 及 相 关 技 术， 分析了目前 Ｔ Ｄ Ｔ领 ［ ３］ 洪宇 ， 张宇 ， 范 域的研究现状展望未来的发展趋势 ． 基礼等提出基于语 义 域 语 言 模 型 的 关 联 性 检 测 方 法 来检测任一新闻报道是否为论述同一话题 ， 显著改进 了现 有 检 测 系 统 话题检测算法研究之前 ， 需要对微 博话题建立描述模型 ， 并通过完善的微博信息适时获 取平台采集 ， 微博信息的适时更新状况并通过采集的 微博更新信息应用 微 博 话 题 的 描 述 模 型 进 行 微 博 话 题的归一 化 表 示 由于微博信息的发布方式与 ． 普通的网页发布方式有较大的差别 ， 微博能够通过用
户之间建立起来的 关 联 关 系 快 速 地 进 行 信 息 的 转 载 因此 ， 在网络 上 获 取 微 博 信 息 需 要 首 先 对 微 和传播 ． 博用户所建立的连接关系进行提取 ， 采集微博用户当 前与其相关联的其 他 微 博 用 户 并 对 用 户 相 关 联 的 所 有微博用户信息更新状态进行了监控 ， 一旦发现任何 一个用户扩散的微博信息有更新 ， 则立刻对更新的微 博内容进行采集 ． 通过这种方式能够及时的发现网络 并及时地对所有 上微博用户的信息发布及更新情况 ， 完成微博语料的最初始的 微博更新的信息进行采集 ， 提取
层次聚类算法的 设 计 原 理 是 根 据 待 聚 类 的 初 始 文本信息进行划分 ， 假设初始待分类的文本信息有 Ｎ 组， 则将每一组文本信 息 设 定 为 一 个 初 始 的 分 类 ． 因 此， Ｎ 个待分组的数据源将形成 Ｎ 个初始的分类结 果， 之后对所形成的初始分类结果进行层次化的聚 类． 其聚类的原则是 ： 对初始分类结果中的不同类两 两进行比较 ， 分别计 算 任 意 两 个 类 之 间 的 相 似 度 值 ， 并形成分类结果的相似据证 ， 如果相似据证中的某个 元素小于分类预值 ， 则将这两个分类结果形成一个新 的聚类集合 ． 如此不断 循 环 ， 直到待分类的初始的文 字语料全部进行聚 类 计 算 并 得 到 与 预 期 要 求 的 分 类 此时 ， 停止聚类算法 ， 输出 数目完全一致的分类结果 ， 聚类结果 ． 传统的这种分层 聚 类 算 法 在 具 体 实 现 过 程 中 主 ）当 使 用 文 本 特 征 词 描 述 微 博 话 要面临以下 问 题 ： １ 如果一篇微博中含有大量的特征词则将导致描 题时 ， 述该微博的特征向量维数特别高 ， 当表示微博话题的 向量维数特别高时 ， 进行向量间的空间距离计算以及 不利 微博向量的分类结果评价的计算量都非常的高 ， ）层 次 聚 类 并 没 有 给 于快速实现 层 次 划 分 的 目 的 ． ２ 出理想的聚类终止条件 ， 目前人们设计和实现的层次 聚类算法往往是按照预先设定的聚类目标进行计算 ， 一旦形成了与目标 分 类 数 一 致 的 分 类 结 果 则 停 止 聚 类计算 ． 这种控制策略不能保证聚类结果在最佳的状 态时停止 ． 有的时候可能有些分类之间仍然是非常相 似的 ， 但聚类算法已经 停 止 运 算 了 ； 有的时候是分类 但层次聚类算法按照 结果已经不能够再进行合并了 ， 算法流程强制将某些分类结果进行合并 ， 反而使用户 理解各分类结果时产生内容含义上的混淆 ． 为了解决传统的层次聚类算法存在的问题 ， 针对 微博数据源的特点 必 须 设 计 一 种 实 现 简 单 易 于 控 制 的层次聚类算法 ， 使其能够实时的处理各种新产生的 微博信息 ， 并能够智能的根据当前的聚类结果控制聚 类层次的深度 ， 避免聚类过程的不足或过头 ． ２． ２ 层次聚类算法详细实现 为了提高层次聚类算法的实现速度 ， 笔者设计的
计 算 机 技 术
提取所有的特征词 会 给 微 博 敏 感 话 题 检 测 增 加 很 大 但可以在后续通过改进和优化处理算法提 的计算量 ， 高处理效率 ． 由于笔者在处理 微 博 敏 感 话 题 提 取 过 程 中 以 特 征词作为衡量微博 话 题 内 容 的 重 要 指 标 ． 因 此， 对微 博话题进行描述时采用空间向量的模型进行描述 ， 即 一个微博话题可以 表 示 为 多 个 特 征 向 量 值 所 组 成 的 具体如下 ： 空间向量 ． 对于任意的一个微博文档 ， 抽取其特征词表示该 由于每个特征词对整个微博文 微博文档的内容特征 ， 档的影响力各不相 同 ， 因 此， 可以给每个特征词定义 一个权重 ， 此时微博文档的空间向量模型表示为 ： …， …， Ｂ＝ （ ｓ ｗ１ ， ｓ ｗｉ， ｓ ｗｎ ） １ ｉ ｎ 其中 Ｂ 表示微博文档 ， ｎ 表示微博文档空间向量 模型定义的维数 ， 维数越高则 微博文档描述越精细， 越能精确地反映微博中的内容 ， 但随之信息处理的复 ， 杂度也越来越高 ．向量模型中各特征值ｓ ｉ 相互独立 既无直接联系也无重叠 ． 而 且 在 向 量 模 型 中， 各特征 值定义的前后关系与模型表达的含义无关 ． 利用微博文档的向量模型 ， 可以定义文档之间话

基于层次聚类的微博敏感 话题检测算法研究
＊
潘大庆
（ ） 柳州市委党校 ，广西 柳州 ５ ４ ５ ０ ０ ６
计 算 机 技 术
摘 要 ：针 对 微 博 对 社会 舆 情影响力日 趋 增 大 ， 设 计 了 基 于 层 次 聚 类 的 微 博 敏 感 话 题 检 测 算 法， 通过对
５ ７
广西民族大学学报 （ 自然科学版 ） ０ １ ２年１ ２月 第１ ８卷 ２
层次聚类算法从以下三个方面进行了改进 ： 第一 ， 在进行层次聚类计算时， 每次只在之前的 聚类基础上将聚类 基 产 生 的 微 博 数 据 与 历 史 形 成 的 结果进行合并 ， 即以历 史 聚 类 产 生 的 结 果 为 参 考 ， 将 其中一部 新产生的微博数据合并到历史聚类结果中 ， 分数据将直接合并到历史聚类数据中的某一类别中 ， 有些确确实实的新 产 生 的 话 题 则 重 新 形 成 新 的 分 类 结果 ， 通过采用这种增量式的聚类计算结果可以保证 使得层次聚 在算法的运行过程中大幅度减少计算量 ， 类算法的聚类结果 能 够 满 足 微 博 信 息 实 时 动 态 增 加 的应用特点 ， 第二 ， 在进行聚类运算时， 由于一些热点话题其 所对应的话题量会急剧 增 加 ， 因 此， 对于这类热点话 题， 其聚类的层次应该变得更为精细 ． 因此 ， 针对热点 话题进行层次聚类 计 算 时 所 选 取 的 聚 类 相 似 度 应 该 因此需要对设计的层次聚类 与其他衡量词度不一样 ， 算法在实现过程中 对 每 个 类 别 中 所 包 含 的 微 博 数 量 进行限制 ， 当符合同一话题的微博数量达到预先设置 的预值之后 ， 新产生的同一话题的微博与此将不再合 并， 而是作为一个新的 话 题 归 入 一 个 新 的 类 别 中 ． 通 过限定每一个话题 微 博 中 的 数 量 可 以 保 证 对 于 一 些 热点敏感话题进行 聚 类 分 析 时 得 到 更 为 精 细 的 分 类 并且可以从分类结果中清晰地看出热点话题随 结果 ， 着时间段的推移其话题的主题不断演化的过程 ． 第三 ， 在进行微博话题层次聚类运算时每次获得 新增加的微博信息 都 需 要 对 历 史 产 生 的 分 类 结 果 和 新增加的分类数据进行两两相似度的判断 ， 两个类别 的相似度的分析又以两两元素之间的计算为基础 ， 当 判断两个类别的 一个类别中的微博数量比较庞大时 ， 相似度运算的复杂度将变得比较大 ， 因此随着时间段 的推移 ， 聚类算法到 后 来 所 消 耗 的 时 间 将 越 来 越 多 ． 因此 ， 为了提高运算的 效 率 ， 笔者在计算两个分类之 间的相似度时 ， 每次都尽可能地从距离最远的两个元 素之间开始计算 ， 一旦计算到两个元素之间的距离大 于预先设定的预值 ， 则 认 为 这 两 个 分 类 相 似 度 较 低， 不满足聚类的条件 ， 直 接 退 出 后 续 的 聚 类 运 算， 以此 提高聚类算法的运算速度 ． ２． ３ 层次聚类算法实现流程 根据层次聚类算法的设计原理 ， 笔者设计了如图 在进 行 微 博 敏 感 话 １ 所示的层次聚类算法实现流程 ． 题检测之前 ， 首先通过微博之间的用户关系建立微博 用户关系数据模型 并 通 过 所 建 立 的 微 博 用 户 关 系 数 据模型引导网络爬 虫 对 相 关 联 的 用 户 微 博 上 的 信 息 以此获得微博话题检测中的原始语料设 进行扒 取 ， 计， 之后按照微博话题模型对所获取的数据进行描