基于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.