基于上下文相似度矩阵的Single-Pass短文本聚类

来源：论文查重 时间：2019-08-02 10:46:12

摘 要 在线社交网络已经成为人们信息交流的重要渠道和载体 ，形成了与现实世界交互影响的虚拟社会 。 众多的 网络事件通过社交网络进行快速传播 ，可以在短时间内成为舆论热点 ，而负面事件会对国家安全和社会稳定造成冲 击 ，从而引发一系列的社会问题 。 因此 ，挖掘社交网络中蕴含的热点信息 ，无论是从舆论监督方面还是舆情预警方面 都具有重要的意义 。 文本聚类是挖掘热点信息的一种重要方法 ，然而 ，使用传统长文本聚类算法处理海量短文本时准 确率将变低 ，复杂度急剧增长 ，从而导致耗时过长 ；现有的短文本聚类算法的准确率偏低 、耗时过长 。 文中基于文本关 键词 ，提出了结合上下文和相似度矩阵的关联模型 ，从而判断当前文本与上一文本的关联性 。 此外 ，根据该关联模型 对文本关键词权重进行调整 ，以进一步降低噪声 。 最后 ，在 Hadoop论文查重平台上实现了分布式的短文本聚类算法 。 与 K MEANS ，SP-NN ，SP-WC 算法的比较实验验证了所提算法在话题挖掘速度 、准确率和召回率等方面都具有更好的 效果 。
1 引言
在移动互联网时代 ，随着人们生活节奏的不断加快 ，简 洁 、快速地用短语进行交流互动更符合人们的生活 。 例如人 们经常使用几个简单的关键词通过搜索引擎查询信息 ；使用 微信 、QQ 等聊天交友 。 挖掘短文本信息可以获取相关的商 业信息 、人际关系信息 、热点新闻 、趋势信息等内容 ，以及对历 史事件进行相关分析总结 。 为了使系统能够自动挖掘短文本信息 ，现有的重要技术手段之一是通过聚类将相似文本组织 在一起 ，从而形成一个话题 。
各类社交网络应用产生了海量的短文本 ，具有持续性 、无 限性和动态性等特点［１］ 。 文本序列中包含大量嘈杂冗余的信 息 ；文本内容来源多样 ，而且其内容和受关注程度处于动态变 化之中［２］ ，话题中心也随着时间不断变化［３］ ；相邻文本间的上 下文相关性非常强 ；信息时效性要求越来越高 。 这些因素使 得通过及时 、准确地检测和追踪话题来获取相关信息的难度 越来越大 。
传统的长文本聚类分析一般是基于文本的特征向量进行 关联性判定 ，如典型的基于划分的聚类分析 、基于层次的聚类 分析以及基于密度的聚类分析［４-６］ 。 基于划分的聚类算法 （Partition-based Methods）的总体思想是将一个具有 N 条记 录的文本集最终划分为 K （K 虫 N）个分组 ，每一个分组表示 一个类别 ，聚类结果的评定标准为组内的记录关联性越近越 好 ，不同组间的记录关联性越远越好 ，并且每一条记录必须属 于唯一一个分组 ，每一个分组中至少包涵一个记录［７-９］ 。 典型 的 K-MEANS 算法［１０］ 、K-MEDOIDS 算法［１１］以及 CLARANS 算法［１２］都是基于划分思想的聚类算法 。 此类算法的优点是 ； 简单 、高效 ；缺点是不能很好地处理噪音及孤立点 ［１３ ］ ，而 且聚类效果对于初始值的选取有很大的依赖性 ，导致其聚 类消耗的时间很不稳定 ，而目前并没有很好的方法选择合 适的初始值 ，在处理大数据时很难估计处理文本所需的时 间 ，无法满足时效性要求 ，同时数据集较大时结果容易陷 入局部最优 。 基于层次的聚类算法（Hierarchical Methods） 是按层次对给定的待处理文本集进行关联性判定 ，如此循环 ， 逐层判定 ，直至达到设定的退出条件为止［１４-１６］ 。 层次聚类算 法按照处理方式的不同 ，可以分为“自底向上”的层次聚类和 “自顶向下”的层次聚类两种不同的聚类方式 。 以“自底向上” 的层次聚类为例 ，初始时将每一个元素当成一个单独的类 ，之 后对这些类之间进行关联分析 ，把达到一定关联阈值的类合 成一个 ，之后再对新得到的类进行同样的判定 ，直至满足算法 设定的退出条件为止［１７-１８］ 。 基于层次思想聚类的算法有很 多 ，典型的有 BIRCH 算法［１９］ 、CURE 算法［２０］以及 CHAME LEON 算法［２１］等 。 相比基于划分的聚类算法 ，层次聚类更加 灵活 ，但其计算量更大 ，时间复杂度更高 ，适用于较小的数据 集 ，且在特征很少的情况下判断类簇相似度时存在较大的误 差 ，致使后续判断受到影响 。 基于密度的聚类算法 （Density based Methods）并不是根据元素与类之间的距离进行相似性 判定 ，而是根据元素分布的密度进行划分 ，因此不存在基于距 离判定文本相似性所造成的过多依赖文本分布形状的不足 。
其判定依据是如果某个区域中点的密度大于设定的阈值 ，则 将该点归属到与之相邻的聚类中［２１-２２］ 。 常见的 DBSCAN 算 法［２３］ 、OPTICS 算法［２４］以及 DENCLUE 算法［２５］ 都属于基于 密度的聚类算法 。 DBSCAN 算法的一个不足之处在于其对 设定的扫描半径及最小包含点数极其敏感 ，这两个参数的细 微变动都会对聚类效果造成很大的影响 。 但遗憾的是 ，这两个参数的选择并没有固定的规律可循 ，只能根据经验进行人 为设定 。
这些方法都是采用词频-逆向文件频率（Term FrequencyInverse Document Frequency ，TF-IDF）计算关键词的权值 ，根 据文本间的特征向量计算两文本之间的距离或者对两文本之 间的紧密程度进行判定［２６-２７］ 。 这些方法对长文本能取得不 错的聚类效果 ，因为长文本一般有很多关键词 ，即使挖掘的特 征向量存在一定的误差 ，对聚类效果也不会存在很大的影响 。 社交网络短文本具有“精简”的特点［２８］ ，导致文本向量的稀疏 程度大 ；同时 ，通过 TF-IDF 计算的关键词的权值非常小 ，几 乎为 ０ ，在计算文本之间的相似度时会存在很大的误差 ，而且 浪费了不少的 CPU 处理时间及内存资源 。 当处理的话题种 类较多以及文本数据量较大时 ，若根据每个话题下所有文本 来计算话题中心 ，每次进行相似度判断都要对所有话题中心 进行比较 ，则随着数据规模增长 ，计算量呈指数级增长 ，导致 算法性能急速下降 ，耗时迅速增加 。 因此 ，这种全局范围内的 文本向量表示法不适合社交网络的短文本聚类算法 。
近年来 ，专门针对短文本聚类的算法层出不穷 ，但大多都 是对传统聚类算法进行改进［２９-３０］ ，如 WR-KMEANS［３１］等 ，其 在一定程度上提高了短文本聚类的效果 ，但准确率依旧较低 ， 且计算量较大 ，耗时过长 ，不能很好地解决海量数据处理的问 题 。 Shen 等［３２］提出了 ５ 种 Single-Pass 聚类算法 ：SPB ，SPWC ，SP-NN ，SP-WNN ，SP-LF 。 Single-Pass 聚类算法是数据 流聚类的经典方法 ，可以实时或者离线处理数据集 ，有效应对 文本内容的动态变化 ，并且算法的可解释性强 。 其缺点是对 文本输入的顺序相对敏感 ，但对类似新闻信息这类按时序严 格组织的文本的聚类结果的影响不大 ；对于每一个新文本 ，都 要计算其与已有文本的相似度 ，随着数据规模的增长 ，计算复 杂度也急剧增长 。 其他的热门方法如词共现聚类的方 法［３３-３４］在论文数据集上的效果很好 ，但是该方法对词的选择 非常敏感 ，而社交网络存在各种不规范用语 ，导致其在处理社 交网络短文本时会出现不确定性问题 。 因此 ，针对社交网络 中的短文本聚类问题 ，迫切需要寻找新的方法 。
基于上述问题 ，本文结合社交网络短文本的特点 ，提出了 基于上下文相似度矩阵的 Single-Pass 聚类方法（Single PassContext Similarity Matrix ，SP-CSM ） 。 该算法首先从短文本 的关键词入手 ，利用上下文信息计算相邻文本的关键词相似 度矩阵 ，来判断当前文本与上一文本的关联性 ，避免了短文本 关键词较少带来的稀疏性问题 。 每个新文本不需要与已有的 所有文本进行相似度比较 ，只需要计算与已有话题的最后一 个文本构成的文本集合间的关联度 ，避免了数据规模不断增 长而导致算法复杂度急剧增长的问题 。 通过对已有文本数据 的更新机制 ，保证了算法性能的稳定 、高效和准确 。 然后针对 关联文本 ，对关键词权重进行调整 ，突出重要关键词 ，抑制次 要关键词 ；同时 ，设置阈值来调节文本在每个关键词上的偏移 程度 ，检测出与主题无关的信息 ，过滤掉大量嘈杂冗余的信 息 ，从而提高算法性能和准确率 。 实验结果表明 ，所提算法与K-MEANS ，SP-WC ，SP-NN 等算法相比 ，无论是从话题挖掘 速度 ，还是从准确率和召回率方面 ，都具有更好的效果 。
2 问题描述与模型
2 ．1 基本定义
文本序列是一组顺序 、大量 、快速 、连续到达的数据序列 ， 可被视为一个随时间延续而无限增长的动态数据集合 。 本文 首先对文本序列进行形式化描述 ，在此基础上 ，定义滑动时间 窗口及其内的文本集合 。 定义 1 在时序文本数据中 ，在时间上连续的文本数据 项及其时间窗口构成一个文本序列 TS ＝ ｛x１ ，x２ ，⋯ ，xk ，⋯ ｝ ， 其中 xk 是第 k 个到达的文本 。
2 ．2 关键词抽取
社交网络短文本的关键词数量很少 ，每一个关键词对描 述该文本相关事件信息都有很大的贡献值 。 如果抽取的关键 词不够准确 ，就会存在很大的误差 ，从而对聚类效果产生很大 的影响 。 因此 ，抽取的关键词要尽可能反映出该文本所包含 的相关信息 ，本文将从文本中提取相关的人物 、地点及相关事 件信息作为文本的关键词 。
一个典型的微博文本一般包含微博作者的昵称 、＠ 其他 人 、微博的具体内容（事件的相关信息和涉及的人物） 。 分词 系统不能很好地处理社交网络中的昵称 ，因此本文以“＠ ”和 其后面的“空格”或者“＠ ”和其后面的“ ：”为分界线 （标识符 ） 来抽取文本的人物信息 。 地名抽取直接根据分词系统提供的 词性即可完成 。 由于挖掘的事件关键词在动词之后 ，因此本 文以句为单位 ，将每句中词性为动词性质的词作为开始记录 ， 之后将其后一定距离内的名词性质的词作为事件关键词 。 具 体伪代码如算法 １ 所示 。
3 实验结果与分析
本文实验主要是对单机实现的 SP-CSM 算法以及MapReduce 模式下的 SP-CSM 算法从运行时间 、加速比 、准确率 、 召回率等方面进行相关性能的综合评测 。 实验环境为 １１ 个 节点的 Hadoop 分布式处理平台 ，处理器为 １６ * Intel （R） Xeon（R） CPU E７３２０ ＠ ２ ．１３ GHz ，服务器内存为 １６ GB 内 存 、１GB 缓存以及 ２GB 交换区 ，操作系统为 ６４ 位 Linux 操作 系统（Red Hat ４ ．１ ．２-４２） 。
实验 １ 采用准确率 、召回率和 F１ 值来评估算法结果的 精度 。 通过已标注好的 ６ ０００ 条新浪微博（２０１３ 年 ６ 月的数 据 ，共包含 １０ 个话题类别）对单机模式下的 SP-CSM 算法进 行评测 ，算法的准确率和召回率分别取各个话题类别下的准 确率和召回率的均值 ，结果如表 １ 所列 。
可以看出 ，在数据量不大的情况下 ，SP-CSM 算法在单机 模式下的耗时比 MapReduce 模式下的耗时更低 ，这是因为 Hadoop 平台本身是为处理大数据而设计的 ，在数据量很小的 情况下并不能发挥它的优势 ，其反而因网络传输及任务调度 的消耗增加了耗时 。 但是随着数据量的增加 ，SP-CSM 算法 的耗时近似线性增长 ，而 K-MEANS 算法的耗时呈不稳定增 长状态 ，这主要是因为 K-MEANS 算法的性能与初始点的选 取有很大的关系 。 在数据量很大的情况下 ，K-MEANS 算法 的耗时急剧增长 ；相比 K-MEANS 算法 ，SP-CSM 算法的耗时 明显降低 ，尤其是 MapReduce 模式下的 SP-CSM 算法的耗时 大幅度降低 。 这说明 K-MEANS 算法不能很好地解决大数 据聚类的问题 ，而 SP-CSM 算法的耗时随着数据量的增长在 一定范围内几乎呈线性增长 ，说明 SP-CSM 算法具有更好的 稳定性及可扩展性 。 在数据量很大的情况下 ，Hadoop 平台发 挥了其优势 ，对大数据有较高的吞吐率 。
实验 ３ 测试 MapReduce SP-CSM 算法的可扩展性 。 加 速比是同一个任务在单处理器系统和并行处理器系统中运行 所消耗的时间的比率 ，用于衡量并行系统或程序并行化的性 能和效果 。 对 SP-CSM 算法在 MapReduce 模式下使用不同 节点数时处理 １５０M 文本集（大约 ４０ 万条微博）的耗时和加 速比进行实验 ，结果如图 ６ 所示 。 可以看出 ，MapReduce 模式 下的 SP-CSM 算法的耗时随着节点数的增加而减小 ，加速比 随节点数的增加而增加 ，说明 MapReduce 模式下的 SP-CSM 算法具有不错的可扩展性 。
结束语 本文提出了针对社交网络短文本聚类的 SP CSM 算法 ，能够检测和追踪话题 。 通过相邻文本的关键词相 似度矩阵判断当前文本与上一文本的关联性 ，解决了稀疏性 问题 。 将话题检测与追踪技术融合在一套系统中 ，通过分析 算法的瓶颈 ，将 SP-CSM 算法 MapReduce 并行化 ，很大程度 上提高了程序运行的效率 ，解决了聚类算法随着数据量增长 而导致性能下降的问题 。 通过与 K-MEANS ，SP-WC ，SP-NN 等算法的比较实验可知 ，SP-CSM 在运行时间 、准确率 、召回 率及可扩展性等方面都具有更好的效果 。 本文对 SP-CSM 只 实现了局部并行化 ，虽然很大程度上提高了程序的性能 ，但是 聚类部分依旧为单机处理 ，没有很好地利用 Hadoop 各节点 的处理能力 ，SP-CSM 的性能有待进一步提升 。 因此下一步 工作将对 SP-CSM 算法进行改进和优化 ，并对社交网络短文 本序列进行演化预测分析 。

相关文章：基于CNKI文献计量分析的国内建言行为研究知识图谱与评述