基于Word2Vec模型特征扩展的Web搜索结果聚类性能的改进

杨楠 李亚平

摘 要：对于用户泛化和模糊的查询，将Web搜索引擎返回的列表内容聚类处理，便于用户有效查找感兴趣的内容。由于返回的列表由称为片段（snippet）的短文本组成，而传统的单词频率逆文档频率（TF-IDF）特征选择模型不能适用于稀疏的短文本，使得聚类性能下降。一个有效的方法就是通过一个外部的知识库对短文本进行扩展。受到基于神经网络词表示方法的启发，提出了通过词嵌入技术的Word2Vec模型对短文本扩展，即采用Word2Vec模型的TopN个最相似的单词用于对片段（snippet）的扩展，扩展文档使得TF-IDF模型特征选择得到聚类性能的提高。同时考虑到通用性单词造成的噪声引入，对扩展文档的TF-IDF矩阵进行了词频权重修正。实验在两个公开数据集ODP239和SearchSnippets上完成，将所提方法和纯snippet无扩展的方法、基于Wordnet的特征扩展方法和基于Wikipedia的特征扩展方法进行了对比。实验结果表明，所提方法在聚类性能方面优于对比方法。

关键词：特征扩展;片段;词嵌入技术;搜索结果聚类

中图分类号： TP391.1

文献标志码：A

Abstract： Aiming at generalized or fuzzy queries， the content of the returned list of Web search engines is clustered to help users to find the desired information quickly. Generaly， the returned list consists of short texts called snippets carring few information which traditional Term Frequency-Inverse Document Frequency （TF-IDF） feature selection model is not suitable for， so the clustering performance is very low. An effective way to solve this problem is to extend snippets according to a external knowledge base. Inspired by neural network based word presenting method， a new snippet extension approach based on Word2Vec model was proposed. In the model， TopN similar words in Word2Vec model were used to extend snippets and the extended text was able to improve the clustering performance of TF-IDF feature selection. Meanwhile，in order to reduce the impact of noise caused by some common used terms， the term frequency weight in TF-IDF matrix of the extended text was modified. The experiments were conducted on two open datasets OPD239 and SearchSnippets to compare the proposed method with pure snippets， Wordnet based and Wikipedia based feature extensions. The experimental results show that the proposed method outperforms other comparative methods significantly in term of clustering effect.

Key words： feature extension; snippet; word embedding technology; search result clustering

0 引言

用户通常使用Web搜索引擎在网络上查询所需的信息，而搜索引擎返回的结果列表由一些称为片段（snippet）的信息组成。一个片段通常包含URL、题目和描述网页的短文本。片段中的文本内容，是关于网页的简单描述，一般包含查询关键词。然而，传统搜索引擎反馈的结果面临两个问题[1]：首先，搜索结果符合用户各种需要的效率不高;其次，它无法指出哪条结果与用户查询内容最相关。这是因为查询关键词内容通常是几个词，缺少上下文，在这种情况下通常匹配的结果较为模糊。

一个有效的解决方法是针对网络搜索返回的结果列表按照主题聚类，从而有助于用户快速找到相关的结果。聚类方法把主题相似的结果片段聚集起来，以更紧凑的形式呈现给用户，同时方便用户按主题进行浏览。这种方法称为搜索结果聚类（Search Results Clustering， SRC）[1-2]，它们按照主题形成片段组，并用主题来命名各组。用户如果对这个主题感兴趣，只需要查看相关主题的群组即可。

但由于片段中的短文本长度较短，单词的共现度低，存在数据稀疏问题，缺少充足的上下文信息进行相似度度量，使得传统的特征选择方法不能得到良好的聚类结果[3]。为了克服短文本的数据稀疏缺陷，研究人员主要采用两种方法来扩展短文本片段：一种方法是使用搜索引擎结果扩展短文本片段[4]。对于某个短文本，通过统计搜索引擎的返回结果计算相似得分，其缺点是多次访问搜索引擎过于耗时，不利于实时查询。另一种方法是利用在离线知识数据库，例如本体对短文本片段进行扩展。基于Wordnet的短文本扩展方法[5]，文本特征的扩展采用来自本体的概念，可以解决多义词（synonyms）问题，同时概念化有利于文档识别。例如，包含特征“beef”的文档与包含特征“pork”的文档不存在关联关系。而作为两者的通用概念“meat”作为特征添加到扩展特征之中，使得两个文档关联起来。文献[5]提出了三个扩展策略：特征加入概念、概念替换和仅采用概念的方法。最后结论是，三种方法均可改进聚类性能，加入概念的方法效果好一些。但是，Wordnet沒有包含一些专有名词，使得该方法在应用中受到限制。将Wikipedia作为外部知识源扩展短文本片段[6]的方法可解决这一问题，Wikipedia可以提供百科全书式的知识扩展。snippet文档采用Wikipedia的概念进行扩展。先下载Wikipedia的文章，除去模板和Wikipedia描述部分，去停词，再去除少于50个词的文章，建立Wikipedia文章索引机制。用片段的两个部分（标题和描述短文）去检索数据库，取返回的前10个概念用于特征扩展，该方法取得了较好的效果。

近些年来出现的神经网络和表示学习方法，也为解决数据稀疏问题提供了新的思路，并且已经出现了许多模型用于表达词向量。词向量在神经网络模型中表示为一个实数向量。利用向量距离表示词向量之间的距离。研究者利用预先训练好的集合，快速完成在自然语言处理方面的任务。

受到词向量表示方法的启发，本文提出了基于Word2Vec模型扩充搜索短文本片段的方法，从而获得片段之间恰当的距离表达，适用于短文本片段的聚类。首先提取片段中的单词，在训练好的模型中，寻找和它距离接近的若干个单词，进行片段扩充。对于扩充后的单词，依然采用传统的单词频率逆文档频率（Term Frequency-Inverse Document Frequency， TF-IDF）特征选择方法计算文本单词特征矩阵。然后，考虑到每个单词的通用程度，通过对词频单词特征进行加权修正，最后采用传统的聚类方法对该矩阵聚类计算。通过实验确定了词汇扩充合理的窗口尺寸，并获得了稳定而快速的聚类效果。在两个公开数据集上进行了大量实验，实验结果表明，本文方法在聚类性能方面优于其他方法。

1 相关工作

搜索结果聚类是对搜索引擎的返回结果进行聚类处理，以主题分组的形式展现给用户，可以帮助用户快速发现相关主题内容。这种方法把数据按照语义分组，同一组中的语义和主题结果相近。由于搜索结果片段中包含的信息较少，影响了聚类效果。研究人员针对稀疏数据集上解决该问题语做了相关研究。一种是对于每个短文本片段，再次利用搜索引擎搜索，统计返回的结果，来扩展和丰富上下文[4];其缺点是反复进行查询耗时间，不适合实时的应用。另一种方法利用离线知识库，例如Wordnet[5]、Wikipedia[6]作为外部知识源，来进行上下文扩充。

神经网络方法在解决数据稀疏问题上提供了新的思路，并且出现了许多用于词表示的神经网络模型[7-10]。Mnih等[8]提出了一种称为词嵌入（Word Embedding） 的单词向量表示方法。这使得能够通过两个单词的嵌入向量之间的距离来度量词的语义相关性。神经网络方法利用预先训练好的嵌入词，在许多自然语言处理中展现了较好的性能。例如，Mikolov[9]使用循环神经网络方法建立语言模型，Socher等[11]提出用递归的神经网络方法来分析短语和句子的敏感性，Ghosh等[12]使用半监督递归的自动编码预测句子的敏感性，Mikolov等[13]提出的段落检测方法也用到了递归神经网络。

目前一些基于神经网络模型的方法，例如Word2Vec 和 Doc2Vec用于分析文本语料[12]。这些方法一旦训练完成，可以很容易用来分析新的文本语义和结构。这对于自动化分类法的建立是很有效的。经典的Word2Vec方法是无监督，并且不需要领域知识的。Word2Vec使用神经网络模型对每个单词学习其向量表示，能够在低维连续向量空间得到单词的表示方法，同时利用文本语料库的上下文关系，使得语义相近的词在空间距离更接近。

2 Word2Vec模型描述

文献[13-15]中介绍了一种新的词向量学习方法，Google公司在2013年开放了Word2Vec用于训练词向量的软件工具，它能够将词语表达为向量形式。

Word2Vec模型包含两种词向量学习结构模型：Skip-Gram模型和连续词袋（Continuous Bag Of Words， CBOW）模型。这两種结构都包含一个输入层、映射层和输出层。当确定词w上下文单词的个数n时，Skip-Gram模型就对当前词的上下文进行预测;而CBOW模型利用上下文词汇，预测当前词。图1是这两个模型结构的描述。

3 通过Word2Vec对snippet的扩展

传统的空间向量模型（Space Vector Model， SVM）和TF-IDF特征选择模型是聚类算法中用于文本的表示方法。即每个snippet可以通过一个在文本中出现的term的向量来表示。每个term的权值可以是该term在文档中出现的频率。由于snippet是短文本，其中许多term的出现形式为，不论重要程度，在文档中仅出现一次。由于term的稀疏性，使得传统的TF-IDF模型缺少统计基础，无法适用于短文本聚类。前面提到了很多相关的技术解决短文本稀疏的问题，如基于搜索引擎、Wordnet、Wikipedia的短文本扩展等。本文中，引入神经网络和表示学习的词嵌入技术来对短文本进行扩展。Word2Vec是一个从文本中学习词嵌入的高度可扩展的预测模型，属于大规模神经网络语言模型。

使用训练后的Word2Vec模型库扩展snippet特征。Word2Vec基于分布式假设， 即在相同文本中出现的单词其语义可能很相近，大部分这样的嵌入单词具有相同上下文。单词嵌入技术具有捕捉语义规则和模式的能力。例如，Cabrilovich等[16]提出了加权向量来表示文本语义相关度的方法。因此，本文提出基于Word2Vec模型可以丰富snippet的内容，加大相关单词的权重和改进语义识别的能力。

3.1 TopN扩展

文本中每个词被扩展为一组语义关联的单词组，可以使得短文本中原来没有共现关系的单词之间建立联系。例如，“car”和“vehicle”之间没有共现关系，虽然语义相近，但共现为0。在Word2Vec模型中，采用前10个单词的扩展集：

可以看出增大了两个单词的共现程度。因而，以语义关联的单词组扩充了文本内容，加大语义相关文档之间的单词共现的机会，因而提高聚类的性能。

从每个snippet的文本可以得到单词的集合，可以通过训练后的Word2Vec模型中的单词库来扩展snippet的内容。本文的扩展方法是，寻找每个term在Word2Vec库中语义最相近的TopN单词实现对snippet的扩展。设一个snippet是由若干个term组成，即Vsnip={t1，t2，…，tl} 。针对每个ti进行Word2Vec模型下的扩展，得到对应一组扩展单词集合Vtn={w1，w2，…，wn}。将该集合Vsnip和Vtn合并，就得到该snippet的扩展集。

3.2 基于词频的权重修正

但是，简单的扩充没有考虑单词的通用程度，会将许多通用单词扩充到文档之中，例如一些较为通用单词，如 “time”“link”“include”等扩充到文档中，无形中引入了噪声信息，反而会降低聚类性能。

因此，针对由Word2Vec扩展之后形成的扩展单词集合，为了防止通用单词对聚类结果精度的下降的影响，本文采取了词频权重的方法，抑制通用词的作用，降低噪声的影响。

设扩充之后的文本经过TF-IDF特征选择处理，保留的term形成的字典集合为V={t1，t2，…，tm}。而词频库为针对文档集的词频统计数据库，其中每个表项由〈t，count〉组成。对于集合V中的每个t的频率权值由以下式（3）计算：

3.3 处理流程

对于测试集合中的n个文档，每个文档都要经过如下7个步骤（本文方法处理流程）的处理：

步骤1 将原始的文档的title和snippet分解为单词的集合，经过小写处理，过滤非英文字符、过短的单词、数字和标点符号，再过滤停词，形成新的单词（term）的集合。

步骤2 对单词集合进行扩展，每个单词查找Word2Vec模型库，返回最相關的TopN个单词形成一个返回清单。

步骤3 对返回清单中的单词进行处理，过滤非英文字符、过短的单词、数字和标点符号，再过滤停词，形成扩展单词集合。

步骤4 将原始单词集合和扩展单词集合合并为新的单词集合，作为新方法的扩展集。

步骤5 采用IF-IDF特征选择方法，建立文档单词权值矩阵。

步骤6 采用3.2节的权值修正方法进行权值的修正，最后归一化处理。

步骤7 对该矩阵进行聚类运算，统计运行结果，计算性能评价指标。

4 实验与结果分析

4.1 数据集

为了评测本文方法，使用了两个公开的数据集：ODP239和SearchSnippets。ODP239是从ODP（Open Directory Project）中抽取的一个子集，一共14个大主题，其中包含239个子主题，每个子主题约100个文档，一共包含25580个文档。每个文档含4项：ID、URL、title和snippet。在实验中，仅抽取title和snippet用于文本聚类，平均每个文档含23.63个单词。SearchSnippets是Phan等[3]收集的8个不同的主题从Web搜索结果中选择的数据集，包含10060个文档的训练集和2280个文档的测试集，平均每个文档长度约18.07个单词。在实验中选用训练集和测试合并构成12340个文档。

Word2Vec模型训练集采用了ODP项目下载的dump数据，其中包含ODP全部信息，共1938099个文档。经过对该下载数据的处理和文档中单词的预处理，以及Word2Vec模型的训练，得到ODP文档库下的Word2Vec模型。

另外，词频统计模型也是在ODP下载数据的基础上，统计每个单词出现的频率，形成词频统计数据。

4.2 评价指标

4.3 实验策略

传统的测试策略是直接将全体数据集的文档和标签作为输入数据进行一次聚类测试。经过实验发现，一次数据集的测试，可能会由于某些与聚类无关的单词的分布，造成对聚类结果的影响。例如，假设三个主题是“business”“sport”“shopping”的文档集合的聚类过程中，可能由于某些单词的分布，例如“link”“time”“site”等和主题无关单词的分布，巧合地与某个主题分布近似，会造成该主题聚类结果好的假象。

本文的观点是仅凭数据集的一次聚类，不能公正地反映算法的性能，因此，在借鉴交叉验证方法的基础上，提出采用成组测试的策略，通过对原始数据集重复随机抽样形成一组测试子集的方法。每个方法需要对该组测试子集中的每个测试子集运行聚类算法，用一组子集结果的平均值作为测试结果。

设定主题数目（聚类簇数目）为一个测试条件，针对每种测试条件抽取10个测试子集构成测试组。每个测试组对应一个主题数量。从3到8分别产生6个测试组，命名为group（i），其中i表示主题的个数。每个测试组的产生是重复以下步骤10次，每组产生10个测试子集：

1）从原始数据集的主题中随机选择i个主题;

2）针对每个主题，在原始数据集对应的主题下随机选择10个snippet形成文档。

最终，按照主题的数量从3到8一共产生了6个测试组，即group（3）到group（8）。

4.4 TopN的确定

TopN表示通过Word2Vec扩展词的数量。通过大量的实验，针对不同的数据集，改变TopN的值，得到如图2所示的运行结果。其中NA_NMI和NA_ACC是没有扩展的文本聚类性能，而TopN_NMI和TopN_ACC是不同TopN下的聚类性能。从图2中可知，实验取TopN=50，即如果某个单词属于Word2Vec字库，则扩展至少到50个单词。

4.5 聚类算法确定

为了实验比较的公平性，不同方法产生的文本特征矩阵都在统一的聚类算法平台下进行测试。经过反复比较，选择了聚类性能较好的聚类工具cluto，cluto是明尼苏达大学开发的一个用于高维数据聚类分析的软件包，具有以下优点：相比其他聚类方法，具有较好的聚类性能;聚类结果的确定性，同一数据集下多次运行后的结果是相同的，每次运行一次即可得到结果。而K-means算法每次运行结果不同，因此，采用K-means聚类，通常需要多次运行结果取平均值的方法;cluto比K-means的运行时间短。

4.6 结果分析

得到上述结果的原因分析是：本体Wordnet以单词为主，缺少专有名词，扩展的范围有限，而Wikipedia虽然包含相关的信息，但Wikipedia不是一个字典，不如Wordnet的单词中的内容丰富，扩展依然受限;但是，Word2Vec模型并不是关于单词的知识本体，而是提供单词之间语义关联程度的向量模型库，只要单词库包含的词（缩写也不例外），模型库都会提供该单词语义相关的其他单词的集合。因此，从扩大文档之间的单词共现率角度分析，Word2Vec的效果会好一些。

5 結语

Web搜索引擎是目前用户在Web上查询相关信息的标准平台。而针对用户提交的查询关键词，搜索引擎将回送给用户一个与查询相关度排序后的结果列表。当用户提交的查询是宽领域或模糊概念时，用户无法从大量的返回结果中快速找到查询的信息。解决该问题的一个有效方法是采用文本聚类技术将相似主题的文档聚集在一起，而使得结果的输出以更为紧凑的形式展现出来，用户可以在主题的分组形式下浏览结果集合。但是，搜索引擎返回的结果列表主要是由称为snippet的短文本组成，而snippet携带很少量的信息，使得传统的TF-IDF模型下的聚类结果的效果很差。解决这一问题的有效方法是采用外部的文本库或语料库对snippet的信息进行扩展。有两种对snippet的扩展方法：一种是再次使用搜索引擎的扩展技术，另一种是使用外部文本数据库。近年来，神经网络和表示学习技术引起了人们的注意，许多词表示学习的神经模型被提出用来解决数据稀疏问题。受到基于Word2Vec模型启发，本文提出了一个扩展snippet的方法，采用模型下TopN个最相似度的词用于对snippet的扩展，并且考虑了词频权重选择，降低由于通用词的扩展而引入的噪声的影响。

为了验证本文方法的有效性，在2个公开数据集下进行了大量的实验，包括模型训练和词频的统计。实验结果的分析表明，本文方法相比基准测试方法在性能上有很大的提高。尽管本文方法是有效的，但是扩展方法依旧显得过于简单，另外仅通过词频过虑噪声数据的方法还不完善。因此，我们未来的工作将集中在Word2Vec模型下扩展方法的深入研究，同时可以考虑结合词性标注（Part Of Speech， POS）、实体识别和本体等内容的结合，进一步提高聚类的性能。

参考文献 （References）

[1] CARPINETO C， OSINSKI S， ROMANO G， et al. A survey of Web clustering engines [J]. ACM Computing Surveys， 2009， 41（3）： Article No. 17.

[2] CARPINETO C， ROMANO G. Optimal meta search results clustering [C]// Proceeding of the 33rd International ACM SIGIR Conference on Research and Development in Information Retrieval. New York： ACM， 2010： 170-177.

[3] PHAN X H， NGUYEN L M， HORIGUCHI S. Learning to classify short and sparse text & Web with hidden topics from large-scale data collections [C]// WWW 2008： Proceedings of the 17th International Conference on World Wide Web. New York： ACM， 2008： 91-100.

[4] BOLLEGALA D， MATSUO Y， ISHIZUKA M. Measuring semantic similarity between words using Web search engines [C]// Proceedings of the 16th International Conference on World Wide Web. New York： ACM， 2007： 757-766.

[5] HOTHO A， STAAB S， STUMME G. Ontologies improve text document clustering [C]// ICDM 2003： Proceedings of the Third IEEE International Conference on Data Mining. Washington， DC： IEEE Computer Society， 2003： 541-544.

[6] BANERJEE S， RAMANATHAN K， GUPTA A. Clustering short texts using Wikipedia [C]// Proceedings of the 30th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. New York： ACM， 2007： 787-788.

[7] BENGIO Y， DUCHARME R， VINCENT P， et al. A neural probabilistic language model [J]. Journal of Machine Learning Research， 2003， 3（6）： 1137-1155.

[8] MNIH A， HINTON G E. Three new graphical models for statistical language modelling [C]// Proceedings of the Twenty-Fourth International Conference on Machine Learning. New York， ACM： 2007： 641-648.

[9] MIKOLOV T. Statistical language models based on neural networks [D]. Brno： Brno University of Technology， 2012： 26-43.

[10] COLLOBERT R， WESTON J， BOTTOU L， et al. Natural language processing （almost） from scratch [J]. Journal of Machine Learning Research， 2011， 12（7）： 2493-2537.

[11] SOCHER R， PENNINGTON J， HUANG E H， et al. Semi-supervised recursive autoencoders for predicting sentiment distributions [C]// Proceedings of the 2011 Conference on Empirical Methods in Natural Language Processing. Stroudsburg， PA： Association for Computational Linguistics， 2011： 151-161.

[12] GHOSH S， CHARKRABORTY P， COHN E， et al. Characterizing diseases from unstructured text： a vocabulary driven Word2Vec approach [C]// Proceedings of the 25th ACM International Conference on Information and Knowledge Management. New York： ACM， 2016： 1129-1138.

[13] MIKOLOV T， CHEN K， CORRADO G， et al. Efficient estimation of word representations in vector space [EB/OL]. [2018-08-16]. http：//www.surdeanu.info/mihai/teaching/ista555-spring15/readings/mikolov2013.pdf.

[14] MIKOLOV T， SUTSKEVER I， CHEN K， et al. Distributed representations of words and phrases and their compositionality [C]// Proceedings of the 26th International Conference on Neural Information Processing Systems. North Miami Beach， FL： Curran Associates Inc.， 2013： 3111-3119.

[15] MIKOLOV T， YIH W， ZWEIG G. Linguistic regularities in continuous space word representations [C]// Proceedings of the 2013 Conference of the North American Chapter of the Association of Computational Linguistics. Stroudsburg， PA： Association for Computational Linguistics， 2013： 746-751.

[16] GABRILOVICH E， MARKOVITCH S. Computing semantic relatedness using Wikipedia-based explicit semantic analysis [C]// Proceedings of the 20th International Joint Conference on Artificial Intelligence. San Francisco， CA： Morgan Kaufmann Publishers Inc.， 2007： 1606-1611.

[17] XU W， LIU X， GONG Y H. Document clustering based on non-negative matrix factorization [C]// Proceedings of the 26th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. New York： ACM， 2003： 267-273.

[18] PAPADIMITRIOU C H， STEIGLITZ K. Combinatorial Optimization： Algorithms and Complexity [M]. New York： Courier Dover Publications， 1998： 248-254.