从海量短新闻中识别相似新闻的方法及相关设备

摘要

本发明属于大数据分析技术领域，具体涉及一种识别相似新闻的方法及相关设备。从海量短新闻中识别相似新闻的方法及相关设备，其中方法包括：获取预设的格式化主体词汇并建立索引；获取多篇新闻，对每篇新闻进行向量化；计算每篇目标新闻与其他新闻是否相似，将与目标新闻相似的其他新闻作为相似新闻；提取目标新闻和相似新闻之间差异的多个字符，在格式化主体词汇建立的索引中查找每个字符，判定目标新闻与相似新闻是否相似；输出新闻相似结果。本发明能很准确地计算出短新闻之间是否相似，能够识别出除了格式化主体不同之外基本一致的格式化新闻是不相似的，避免了格式化新闻都被判为相似的错误。

说明书

技术领域

本发明属于大数据分析技术领域，具体涉及一种识别相似新闻的方法及相关设备。

背景技术

海量文本相似度算法是文本处理中的重要基础性算法，很多文本处理程序如新闻分析中的新闻去重、搜索引擎的网页去重等都需要能够处理海量文本的相似度算法。

目前主流的海量文本相似度算法是simhash算法。simhash算法是一种局部敏感哈希算法，原理是将文本分解为词，计算每个词的hash值，并加权求和，求和后大于0的位置为1，等于0的位置保持为0，由此得到文本的hash串。过比较文本hash串的海明距离来判断文本是否相似，海明距离大于阈值的为不相似，反之为相似。为了减少比较次数，通常会把hash串分割成n段并以各段为key建立索引，n的值为海明距离阈值加1，因此通常simhash算法使用一个固定阈值。

除了基本的simhash算法之外，还有一些基于simhash的改进算法。如申请号为CN201910225442.9的专利《改进的Simhash算法在文本去重中的方法及系统》提出了一种改进词权重的方式，基于TF-IDF算法与信息熵进行加权得到权重。申请号为CN201810535318.8的专利《一种基于改进的simhash文本对比方法》提出了一种基于改进的simhash文本对比方法，通过对文章标题出现次数较高的词的权重进行设置，进而提高查重的准确率。

simhash算法及其改进算法，对于较长的文本计算相似度效果较好，但对于较短如600字以下的文本效果欠佳。原因是较长的文本会在加权求和的过程中把不同文字带来的影响进行稀释，从而减少两篇文本最终hash值的海明距离；而对于短文本，不同文字带来的影响相对较大，少量文字的不同也会导致两篇文本最终hash值的海明距离较大，从而使文本被判为不相似。而且在实践中simhash算法往往使用固定阈值，无法自动适应文本长度的变化。

Simhash算法的另一个缺陷是无法正确处理格式化新闻。在新闻特别是财经新闻中，很多新闻是一种模板式的结构，除了新闻描述的主体如股票名称、大宗商品(以下称为“格式化主体”)等之外几乎完全一致。Simhash算法往往会把这种新闻判为相似，但是主体不同的两篇新闻不应该被判为相似新闻。通过设置词权重优化simhash的方法一定程度上可以缓解对格式化新闻的误判，但对格式化主体词汇权重进行加强的同时也会影响到非格式化新闻，导致算法对非格式化新闻的效果变差。

发明内容

本发明针对现有的simhash算法及其改进算法针对于较短文本和格式化主体的新闻，相似度识别效果较差的技术问题，目的在于提供一种从海量短新闻中识别相似新闻的方法及相关设备。

从海量短新闻中识别相似新闻的方法，包括：

获取预设的格式化主体词汇并建立索引；

获取多篇新闻，对每篇所述新闻进行向量化；

计算每篇目标新闻与其他新闻是否相似，将与所述目标新闻相似的其他新闻作为相似新闻；

提取所述目标新闻和所述相似新闻之间差异的多个字符，在所述格式化主体词汇建立的索引中查找每个所述字符，如果多个所述字符能构成多于预设目标阈值的格式化主体词汇，则判定所述目标新闻与所述相似新闻不相似，否则判定所述目标新闻与所述相似新闻相似；

输出新闻相似结果。

可选的，所述获取预设的格式化主体词汇并建立索引，包括：

从数据库中获取预设的格式化主体词汇，加入到词表W；

分别建立索引数据结构IW、名称长度数组WL；

从所述词表W中取出词w

取w

将字c

将i添加到索引数据结构IW[idx

直至词w

可选的，所述获取多篇新闻，对每篇所述新闻进行向量化前，包括获取多篇新闻，对每篇所述新闻进行过滤：

获取新闻D

如果所述新闻D

将所述新闻D

去除所述新闻D

可选的，所述对每篇所述新闻进行过滤后，还包括：

判断过滤后的所述新闻D

可选的，所述获取多篇新闻，对每篇所述新闻进行向量化，包括：

建立新闻向量矩阵A，所述新闻向量矩阵A为二维矩阵，所述新闻向量矩阵A的每一行对应一篇新闻的文字向量；

将过滤后的所述新闻D

将所述文字向量V

直至所有的新闻均转化为文字向量并添加到所述新闻向量矩阵A中。

可选的，将字C

如果所述字C

如果所述字C

如果所述字GB2312范围内的汉字，则所述位置索引idx

如果所述字C

将字C

可选的，所述计算每篇目标新闻与其他新闻是否相似，将与所述目标新闻相似的其他新闻作为相似新闻，包括：

通过矩阵减法计算所述目标新闻和所有其他新闻向量的差，得到两个新闻之间的差异量，判断所述差异量是否满足预设的相似阈值条件，将满足所述相似阈值条件的新闻作为相似新闻。

可选的，每篇所述新闻进行向量化后得到新闻向量矩阵A，取所述新闻向量矩阵A的行向量A

取矩阵C的行向量C

判断所述差异量Pos

可选的，所述判断所述差异量Pos

通过分段线性函数来判断所述差异值是否满足相似阈值条件。

可选的，所述通过分段线性函数来判断所述差异值是否满足相似阈值条件，包括：

计算用于判断相似阈值条件的两个数值：

mid_valuei＝K*0.08

off_set

其中，K为所述目标新闻的长度；

如果所述差异量Pos

如果所述差异量Pos

如果所述差异量Pos

y

如果y

如果所述差异量Neg

y

如果y

可选的，所述提取所述目标新闻和所述相似新闻之间差异的多个字符，在所述格式化主体词汇建立的索引中查找每个所述字符，如果多个所述字符能构成多于预设目标阈值的格式化主体词汇，则判定所述目标新闻与所述相似新闻不相似，否则判定所述目标新闻与所述相似新闻相似，包括：

提取所述行向量C

从Pos_idx中取Pos

直至l等于len(Pos_idx)后，提取C

直至l等于len(Neg_idx)，如果name_diff＞2，则判定新闻i和新闻j不相似，否则判定新闻i和新闻j是相似的，记录下相似对(i，j)。

从海量短新闻中识别相似新闻的装置，包括：

初始化模块，用于获取预设的格式化主体词汇并建立索引；

新闻向量化模块，用于获取多篇新闻，对每篇所述新闻进行向量化；

计算新闻相似性模块，用于计算每篇目标新闻与其他新闻是否相似，将与所述目标新闻相似的其他新闻作为相似新闻；

格式化新闻判别模块，用于提取所述目标新闻和所述相似新闻之间差异的多个字符，在所述格式化主体词汇建立的索引中查找每个所述字符，如果多个所述字符能构成多于预设目标阈值的格式化主体词汇，则判定所述目标新闻与所述相似新闻不相似，否则判定所述目标新闻与所述相似新闻相似；

输出结果模块，用于输出新闻相似结果。

一种计算机设备，包括存储器和处理器，所述存储器中存储有计算机可读指令，所述计算机可读指令被所述处理器执行时，使得所述处理器执行上述从海量短新闻中识别相似新闻的方法的步骤。

一种存储有计算机可读指令的存储介质，所述计算机可读指令被一个或多个处理器执行时，使得一个或多个处理器执行上述从海量短新闻中识别相似新闻的的步骤。

本发明的积极进步效果在于：本发明采用从海量短新闻中识别相似新闻的方法，能很准确地计算出短新闻之间是否相似，并且还能够识别出除了格式化主体不同之外基本一致的格式化新闻是不相似的，避免了格式化新闻都被判为相似的错误。

附图说明

图1为本发明方法的一种流程图；

图2为本发明初始化流程图；

图3为本发明单篇新闻向量化流程图；

图4为本发明计算相似新闻流程图；

图5为本发明分段函数的一种函数图。

具体实施方式

为了使本发明实现的技术手段、创作特征、达成目的与功效易于明白了解，下面结合具体图示进一步阐述本发明。

参照图1，从海量短新闻中识别相似新闻的方法，包括如下具体步骤：

S1，初始化：获取预设的格式化主体词汇并建立索引。

在一个实施例中，参照图2，本步骤的初始化过程，具体采用如下方式：

S101，从数据库中获取预设的格式化主体词汇，加入到词表W，转到下一步。

S102，分别建立索引数据结构IW、名称长度数组WL，转到下一步。

其中，索引数据结构IW是一个长度为7236的python列表，列表的每个元素是一个空的集合(python的set)。

名称长度数组WL是一个空的python列表。

S103，从词表W中取出词wi，i∈[1，N]；其中，i表示w

S104，取w

S105，将字C

在一个实施例中，位置索引idx

S10501，如果字C

S10502，如果字C

S10503，如果字GB2312范围内的汉字，则位置索引idx

由于GB2312是用两个字节来表示汉字，因此本步骤把C

例如汉字′啊′的高位字节是0xB0，低位字节是0xA1。

S10504，如果字C

S106，将i添加到索引数据结构IW[idx

S107，如果j＝＝n，转到下一步，否则j+＝1，转到S104。

S108，将n添加到WL，即执行WL.append(n)，转到下一步。

S109，如果i＝＝N，转到下一步，否则i+＝1，转到S103。

S110，初始化结束。

S2，新闻过滤：获取多篇新闻，对每篇新闻进行过滤。

本步骤为可选步骤，在获取了多篇新闻后，可以先对每篇新闻进行过滤，也可以直接进行后续对每篇新闻进行向量化步骤。

具体的，本发明在对新闻向量化之前对新闻内容进行了过滤，去除了“原标题”、“摘要”等内容，并去除了除汉字、英文和数字之外的字符，从而排除掉了噪音，提升了相似度计算的准确性。

S3，新闻向量化：对每篇新闻进行向量化。

为了快速地计算短新闻之间的文本相似度，并减少内存占用，本发明将短新闻转为长度为7236的向量进行存储，其中10位是数字字符位，26位是英文字符位，7200位是汉字字符位。每个汉字、英文字母和数字分别对应向量上的一个位置，汉字、英文字母和数字都可以通过其编码直接计算出字符在向量中的位置，位置上的值表示该字符在新闻中出现的次数。为了减少内存占用，汉字采用GB2312字符集，GB2312编码包含的汉字是6763个，但编码区间中存在空白位，为了简化计算，使得从字符计算出位置的计算尽量简化，本发明中保留了GB2312中的空位，因此汉字字符位是7200位。GB2312中包含了汉字的常见字，非常见字未包含在内，但是为了减少内存占用，本发明在计算中剔除了非常见字。由于本发明所处理的文本主要是新闻文本，而新闻的受众是广大普通读者，因此新闻中的非常见字较为少见，对于新闻这种文体而言，剔除非常见字带来的误差可以忽略。

具体的，计算字符在向量中位置的方式是直接从字符的编码计算出位置。阿拉伯数字字符对应的位置是向量中的第0-9位，可以直接将数字字符的数据类型从文本转为数字得到。英文字符对应的位置是向量中的第10-35位，通过英文字符的ASCII编码减去′a′的ASCII编码再加上10得到。汉字字符对应的位置是向量中第36位及以后的位置，计算方式是通过汉字字符的GB2312编码计算得到。GB2312是用两个字节来表示汉字，对于汉字c

本发明中计算字符在向量中位置的耗时是常数时间，而且计算公式都是线性公式，因此计算位置消耗的时间优化到了最低。

S4，计算新闻相似性：计算每篇目标新闻与其他新闻是否相似，将与目标新闻相似的其他新闻作为相似新闻。

本步骤通过矩阵减法计算目标新闻和所有其他新闻向量的差，得到两个新闻之间的差异量，判断差异量是否满足预设的相似阈值条件，将满足相似阈值条件的新闻作为相似新闻。

上述设计将要计算相似度的新闻的向量存为矩阵，计算相似度时，通过矩阵减法计算目标新闻向量和所有新闻向量的差，这个差表示了两个新闻间字符的差异量，再根据阈值函数判断差异量是否满足相似阈值条件，满足相似阈值条件的新闻称为和目标新闻向量相似的新闻。

为了解决固定阈值带来的适应性差的问题，本发明的一个实施方式为采用一个分段线性函数来计算向量的差异量是否满足相似阈值条件，且函数的参数与目标新闻的长度相关，以此来避免固定阈值带来的对不同长度文本适应性不佳的问题。

为了提高运算速度，本发明中所涉及向量间计算和矩阵间计算的部分均使用能够进行矩阵运算的软件工具进行，如python的numpy等。

S5，格式化新闻判别：提取目标新闻和相似新闻之间差异的多个字符，在格式化主体词汇建立的索引中查找每个字符，如果多个字符能构成多于预设目标阈值的格式化主体词汇，则判定目标新闻与相似新闻不相似，否则判定目标新闻与相似新闻相似。

为了解决格式化新闻被误判为相似的问题，本发明预先加载了格式化主体词汇，并对这些词建立以字为key的倒排索引。当一篇新闻被判定为和目标新闻向量相似之后，提取出该新闻和目标新闻之间差异的字符，并在倒排索引中查找这些字符。如果差异的字符能构成多于阈值个格式化主体词，那么判定这两篇新闻是不相似的，反之则判定为相似的，这个判定的结果是最终结果。

S6，输出结果：输出新闻相似结果。

在一个实施例中，对新闻进行S2至S6的具体方式如下：

S201，获取新闻D

S202，如果新闻D

其中，第一预设字段可以设置为“原标题”，第二预设字段可以设置为“摘要”。

S203，将新闻D

S204，去除新闻D

S205，判断过滤后的新闻D

本发明设定的短新闻标准是过滤后字符数小于等于MAX_LEN，MAX_LEN可根据实际情况调整，MAX_LEN的一个可选值是600。由于相似新闻的长度可能大于MAX_LEN，因此留出一定的余量，过滤后字符数小于等于MAX_LEN+100的新闻都纳入计算。即本发明优选预设总数为MAX_LEN+100。

S301，建立新闻向量矩阵A，新闻向量矩阵A为二维矩阵，新闻向量矩阵A的每一行对应一篇新闻的文字向量。

S302，将过滤后的新闻D

在一个实施例中，将新闻D

S30201，声明一个文字向量V

本步骤中的文字向量V

S30202，计算新闻D

具体的，字符c

参照图3，对于每个字符c

如果字符c

如果字符c

如果字符c

如果字符c

文字向量V

S303，将文字向量V

S304，如果i等于M，转到下一步，否则i+＝1，转到S201；

参照图4，对于新闻i计算与其他新闻的相似性：

S401，取新闻向量矩阵A的行向量A

本步骤中，可利用预设的数学计算工具的广播机制，例如NumPy广播机制，对二维矩阵B做自动扩展后，使得二维矩阵B和新闻向量矩阵A的维度相等，从而满足矩阵减法的要求。

S402，取矩阵C的行向量C

S403，判断差异量Pos

在一个实施方式中，计算差异量是否满足相似阈值条件的方法如下：

参照图5，通过分段线性函数来判断差异值是否满足相似阈值条件，分段线性函数的表达式为：

令x＝Neg

采用分段函数的原因是Pos

参照图4，在一个实施方式中，通过分段线性函数来判断所述差异值是否满足相似阈值条件的具体方法如下：

计算用于判断相似阈值条件的两个数值：

mid_value

off_set

其中，K为目标新闻的长度；

上述两个数值的计算可在步骤S402取C

如果差异量Pos

如果差异量Pos

如果差异量Pos

y

如果y

如果差异量Neg

y

如果y

S501，提取行向量C

S502，从Pos_idx中取Pos

S503，从IW[Pos

S504，如果l等于len(Pos_idx)，转到下一步，反之l+＝1，转到S502。

S505，提取C

S506，从Neg_idx中取Neg

S507，从IW[Neg

S508，如果l等于len(Neg_idx)，转到下一步，反之l+＝1，转到S506。

S509，如果name_diff＞2，则判定新闻i和新闻j不相似，否则判定新闻i和新闻j是相似的，记录下相似对(i，j)，转到下一步。

S510，如果j等于M，转到下一步，反之j+＝1，转到S402。

S511，如果i等于M-1，转到下一步，反之i+＝1，转到S401。

S601，输出新闻相似计算结果，计算结束。

以上显示和描述了本发明的基本原理、主要特征和本发明的优点。本行业的技术人员应该了解，本发明不受上述实施例的限制，上述实施例和说明书中描述的只是说明本发明的原理，在不脱离本发明精神和范围的前提下，本发明还会有各种变化和改进，这些变化和改进都落入要求保护的本发明范围内。本发明要求保护范围由所附的权利要求书及其等效物界定。