论文查重 | 论文文献库 | 基于上下文相似度矩阵的Single-Pass短文本聚类

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

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

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