基于主題和特征的文本相似度算法研究

藥珍妮

(北京郵電大學(xué) 網(wǎng)絡(luò)技術(shù)研究院，北京市 100088)

基于主題和特征的文本相似度算法研究

藥珍妮

(北京郵電大學(xué) 網(wǎng)絡(luò)技術(shù)研究院，北京市 100088)

本文提出了結(jié)合主題和各主題下關(guān)鍵特征的文本相似度算法，目的在于更準(zhǔn)確的挖掘被描述對(duì)象的近鄰對(duì)象集。本文首先介紹卡方統(tǒng)檢驗(yàn)特征統(tǒng)計(jì)法，并利用改進(jìn)的卡方檢驗(yàn)，計(jì)算訓(xùn)練集中已知主題的文本的特征；而后介紹了最小編輯距離算法、余弦相似度算法和杰卡德相似系數(shù)，在論證了主題對(duì)文本相似度的重要性后，又針對(duì)難提取主題的文本加以改進(jìn)，最終提出了基于主題和特征的文本相似度算法；然后對(duì)各個(gè)算法在測試集上的相似度計(jì)算結(jié)果進(jìn)行分析，證明本文提出的算法在速度和精確度上明顯優(yōu)于其他算法；最后將該算法應(yīng)用于股票的概念股題材標(biāo)注上，分析結(jié)果并提出改進(jìn)空間和不足之處。

數(shù)據(jù)挖掘；文本相似度；主題；特征

0 引言

文本相似度的計(jì)算已經(jīng)深入到互聯(lián)網(wǎng)發(fā)展的各個(gè)領(lǐng)域；如：在QA系統(tǒng)中，快而準(zhǔn)的判斷問題之間的相似度，決定了QA系統(tǒng)回答的響應(yīng)速度和準(zhǔn)確度；在各大門戶網(wǎng)站中，文本相似度的挖掘，是用戶個(gè)性化推薦系統(tǒng)和編輯系統(tǒng)的關(guān)鍵工作。

在文本分類的問題上，由于有本數(shù)量過多、描述篇幅過大或內(nèi)容部分缺失等問題，導(dǎo)致想完全依賴標(biāo)注好的訓(xùn)練集判斷新樣本的屬性越來越難。針對(duì)這類問題，本文提出了從文本所描述主題和的各個(gè)主題下描述內(nèi)容的特征入手，對(duì)于一個(gè)文和其相似度高的幾個(gè)文本，他們之間不論主題還是對(duì)應(yīng)的主要特征都存在相關(guān)性，這樣，既不會(huì)導(dǎo)致同名但內(nèi)容不符被判定為一類，也不會(huì)導(dǎo)致內(nèi)容高度相符但被判定成不同類的情況。

在文本分類訓(xùn)練中，之前的實(shí)驗(yàn)里，運(yùn)用了卡方分布和信息熵（Entropy）來計(jì)算每個(gè)特征詞在相應(yīng)概念下的權(quán)重，然后根據(jù)這個(gè)權(quán)重來判斷個(gè)文本最可能描述的幾個(gè)概念，然而計(jì)算結(jié)果并不讓人滿意，導(dǎo)致結(jié)果準(zhǔn)確率低的主要原因有兩個(gè)，其一是因?yàn)橐褬?biāo)注好概念的股票不到5分之一，另一個(gè)是，實(shí)際上，對(duì)這些股票的原始概念標(biāo)注并非來源于其對(duì)應(yīng)公司的經(jīng)營范圍概述，而是更多更詳細(xì)的對(duì)其各個(gè)從事領(lǐng)域的描述。

1 基于卡方檢驗(yàn)的特征統(tǒng)計(jì)

1.1 卡方檢驗(yàn)算法

假設(shè)，兩個(gè)分類變量X（特征）和T（主題），它們的值域分別為{x1 x2}和{t1, t2}，x1表示包含特征x，x2表示不包含特征x，t1表示屬于特征T，t2表示不屬于特征T，其樣本頻數(shù)列聯(lián)表為：

表1 卡方統(tǒng)計(jì)特征分布表

設(shè)：H1表示X與T相互獨(dú)立，考慮到當(dāng)特征與主體完全不相關(guān)時(shí)相關(guān)系數(shù)為0，這種情況時(shí)有AD-BC<=0，則卡方統(tǒng)計(jì)特征與主題的相關(guān)系數(shù)公式為：

1.2 對(duì)基于卡方檢驗(yàn)的特征統(tǒng)計(jì)的優(yōu)化

1.2.1 特征的歸一化處理

用傳統(tǒng)的卡方檢驗(yàn)得到的，不同主題下的特征權(quán)重是不同的，這樣在會(huì)導(dǎo)致計(jì)算結(jié)果傾向于在樣本空間中文本數(shù)量相對(duì)多的主題，為了解決這一問題，可以對(duì)數(shù)據(jù)進(jìn)行歸一化的處理，得：

其中max(T( x))為主題T下，所有特征中權(quán)值的最大值。

1.2.2 對(duì)頻繁項(xiàng)特征的懲罰

通過卡方檢驗(yàn)可以得到，一個(gè)主題概念下有若干個(gè)特征，但一個(gè)特征若屬于多個(gè)主題，那么該特征并不能代表作為這個(gè)主題下獨(dú)一無二的特征。所以，本文利用TF_IDF的思想，再次對(duì)特征的在某主題下的權(quán)值作出現(xiàn)頻度上的懲罰，最終得到較優(yōu)化的特征。

2 文本相似度計(jì)算算法

2.1 最小編輯距離算法

最小編輯距離的概念由俄羅斯科學(xué)家Vladimir Leven Shtein在1965年提出。最小編輯距離（LevenShtein距離）指：由一個(gè)字符串轉(zhuǎn)成另一個(gè)字符串所需的最少編輯操作次數(shù)；編輯操作次數(shù)包括：插入或刪除一個(gè)字符和將一個(gè)字符替換成另一個(gè)字符，其算法描述為：輸入兩個(gè)任意長度的字符串，str1和str2，其中str1的長度為m，用字母i表示str1中長度為i的子串，str2的長度為n，用字母j表示str2中長度為j的子串，len(i)和len(j)分別表示字串i，j的長度；edit(i,j)表示由str1的子串i到str2的子串j的最小編輯距離。

在對(duì)文本相似度的計(jì)算中，該算法的局限性體現(xiàn)在，僅可以找出句子結(jié)構(gòu)上最相似的兩段描述，并非語義上的相似，其過分強(qiáng)調(diào)編輯距離上的改動(dòng)最小，導(dǎo)致忽略了被文本描述的對(duì)象主題。舉例如下：

1. 某環(huán)保有限公司：從事環(huán)保設(shè)備領(lǐng)域內(nèi)的技術(shù)開發(fā)、技術(shù)服務(wù)、技術(shù)咨詢、技術(shù)轉(zhuǎn)讓。

2. 某醫(yī)療集團(tuán)：從事醫(yī)療發(fā)展領(lǐng)域內(nèi)的技術(shù)開發(fā)、技術(shù)服務(wù)、技術(shù)咨詢、技術(shù)轉(zhuǎn)讓。

因此，最小編譯距離并不能有效地表示兩個(gè)句子之間的語義的相似度。

2.2 余弦相似度和杰卡德系數(shù)

2.2.1 余弦相似度計(jì)算

余弦相似度是求兩個(gè)向量之間夾角對(duì)應(yīng)的余弦值，此余弦值可以用來表征這兩個(gè)向量的相似性。夾角越小，余弦值越接近于1，它們的方向更加吻合，則越相似。

用這一概念來衡量樣本向量之間的差異余弦相似度的公式為：

其中，x1、x2為維度相同的兩個(gè)向量。在機(jī)器學(xué)習(xí)中，文本常由向量表示，訓(xùn)練集中所涉及的詞量相對(duì)龐大，維度通常會(huì)維持在8000到15000，但對(duì)于短文本來說，且這個(gè)向量是高維且稀疏的。

2.2.2 杰卡德（Jaccard）相似系數(shù)計(jì)算

杰卡德相似系數(shù)是衡量兩個(gè)集合相似度一種指標(biāo)。在短文本中，其包含的詞可以用一個(gè)集合來表示，計(jì)算兩個(gè)文本的相似度時(shí)，用杰卡德相似系數(shù)表示要比用高維詞向量計(jì)算余弦相似度快得多。杰卡德相似系數(shù)的公式為：

其中，S(i)，S(j)分別表示第i和第j個(gè)句子中詞的集合。

2.3 基于主題和特征的文本相似度計(jì)算

在杰卡德相似系數(shù)的基礎(chǔ)上，加上主題對(duì)文本間整體相似度的影響權(quán)重，首先分析主題對(duì)文本相似度的影響，本文分三種情況去闡述，以兩段文本為例：

1. 僅一方可以提取到有效的主題，或兩方都提取不到有效主題。

2. 兩方提取到的有效主題不一致。3. 兩方提取到的主題一致。上述過程用公式表示為：

帶入式(4)，得：

其中x1，x2為相關(guān)系數(shù)，在實(shí)際計(jì)算中，可以通過不斷嘗試，最終確定x1和x2的值，本文初始化時(shí)默認(rèn)x1=0.5,x2=1.5。

在實(shí)際操作中，對(duì)主題的提取通常來源于標(biāo)題（或被描述對(duì)象的名稱），但并不是所有的文章標(biāo)題、物品名稱都可以容易地得到主題，在這種情況下，由3.3.1中提到相似相度的關(guān)系系數(shù)為1，起不到懲罰或鼓勵(lì)的做用，基于上述問題，本文通過如下方法進(jìn)行近一步的改進(jìn)。

1. 利用改進(jìn)的卡方檢驗(yàn)提取待計(jì)算文本的特征。

2. 對(duì)相似度的計(jì)算公式，增加特征權(quán)重這一參數(shù)，特征權(quán)重用公式如下：

x(i)、x(j)分別表示第i個(gè)樣本和第j個(gè)樣本的特征，本文取改進(jìn)的卡方檢驗(yàn)中，計(jì)算結(jié)果中權(quán)重最大的前五個(gè)座位特征集，若不滿5個(gè)則以較小的為基準(zhǔn)，保持?jǐn)?shù)量上的一致，x( i)-x( j)表示特征集合i與特征集合j的差集，（3.8）中的公式表示，差集的模越大，權(quán)值越小，若完全一致，則權(quán)值為1。

下面給出基于主題相關(guān)系數(shù)和特征權(quán)重的文本相似度計(jì)算公式：

該算法的優(yōu)勢在于，即考慮到主題對(duì)文本內(nèi)容的影響，又可以使文本內(nèi)容不完全依賴于主題之間的相似，模型相對(duì)簡單且易于理解。

3 實(shí)驗(yàn)結(jié)果及對(duì)比分析

本文將該算法應(yīng)用于對(duì)股票題材概念的提取，通過上市公司提取股票的經(jīng)營主題；再從上市公司的經(jīng)營范圍描述中。

3.1 最小編輯距離算法實(shí)驗(yàn)結(jié)果

如圖3.1比對(duì)短句：從事環(huán)保設(shè)備領(lǐng)域內(nèi)的技術(shù)開發(fā)、技術(shù)服務(wù)、技術(shù)咨詢、技術(shù)轉(zhuǎn)讓。

圖3.1 最小編輯距離下計(jì)算結(jié)果

3.2 杰卡德文本相似度計(jì)算實(shí)驗(yàn)結(jié)果

如圖3.2分析：沒有強(qiáng)調(diào)行業(yè)主題詞的作用，誤差主要產(chǎn)生于與主題相關(guān)性小的特征也都有機(jī)會(huì)參與計(jì)算，直接造成較長的文本占盡優(yōu)勢。

3.3 基于行業(yè)主題詞的文本相似度計(jì)算實(shí)驗(yàn)結(jié)果

如圖3.3分析：結(jié)果集的相似度很高，但局限住了很多符合某一行業(yè)特征，但文本比較短，且缺失行業(yè)主題的描述。

圖3.2 基于文本內(nèi)容的相似度計(jì)算結(jié)果

圖3.3 基于行業(yè)主題的相似度計(jì)算結(jié)果

3.4 基于行業(yè)主題詞的文本相似度計(jì)算實(shí)驗(yàn)結(jié)果

如圖3.4分析：最終結(jié)果考慮到了文章內(nèi)容、主題詞權(quán)重和文本的特征權(quán)重，得到了優(yōu)于上述三種方法的計(jì)算結(jié)果。

4 總結(jié)

在用改進(jìn)的卡方分布提取特征詞權(quán)重比較文本相似的實(shí)驗(yàn)中，誤差的來源于，拋開主題的影響后，文本的相似性過分依賴于分詞系統(tǒng)；在用最小編輯距離計(jì)算文本相似度中，誤差來源于過分強(qiáng)調(diào)文本中字的排列，忽略了主題詞本身的意義。

本文提出的方法很好的適用于段文本中，關(guān)鍵詞比較集中的（大多數(shù)相同行業(yè)的描述比較相似）本文相似度分析中，然而在此之后的的工作中，在面對(duì)100G這樣的大文本時(shí)，計(jì)算速度將成文一個(gè)必須解決的問題，所以還可以使用局部敏感哈希來對(duì)海量數(shù)據(jù)進(jìn)行處理。

最后，本算法還存在的在于泛化能力不強(qiáng)，很難將潛在的概念全部挖掘出來。在實(shí)驗(yàn)中，取最相似的10個(gè)文本對(duì)其概念進(jìn)行標(biāo)注，若取其中概念交集的前三個(gè)，準(zhǔn)確率僅有74.43%，但其中概念交集的第一個(gè)，準(zhǔn)確高達(dá)有98.87%。

圖3.4 加入行業(yè)權(quán)重主題詞的實(shí)驗(yàn)結(jié)果

[1] 李凡, 魯明羽, 陸玉昌. 關(guān)于文本特征抽取新方法的研究[J]. 清華大學(xué)學(xué)報(bào)(自然科學(xué)版), 2001, 41(7): 98-101.

[2] 劉濤. 用于文本分類和文本聚類的特征選擇和特征抽取方法的研究[D]. 南開大學(xué), 2004.

[3] 周水庚, 關(guān)佶紅, 胡運(yùn)發(fā). 隱含語義索引及其在中文文本處理中的應(yīng)用研究[J]. 小型微型計(jì)算機(jī)系統(tǒng), 2001, 22(2): 239-243.

[4] 孫爽, 章勇. 一種基于語義相似度的文本聚類算法[J]. 南京航空航天大學(xué)學(xué)報(bào), 2006, 38(6): 712-716.

[5] 劉群, 李素建. 基于知網(wǎng)的詞匯語義相似度的計(jì)算[C]. 第三屆漢語詞匯語義學(xué)研討會(huì), 臺(tái)北, 2002: 59-76.

[6] 陳龍, 范瑞霞, 高琪. 基于概念的文本表示模型[J]. 計(jì)算機(jī)工程與應(yīng)用, 2008, 44(20): 162-164.

[7] 單麗莉, 劉秉權(quán), 孫承杰. 文本分類中特征選擇方法的比較與改進(jìn)[J]. 哈爾濱工業(yè)大學(xué)學(xué)報(bào), 2011(s1): 319-324.

[8] 柴加加, 張德賢, 耿瑞煥. 基于TF-CA-CI算法的互信息特征選擇改進(jìn)研究[J]. 計(jì)算機(jī)應(yīng)用與軟件, 2013, 30(3): 255-257.

[9] Fragoudis D, Meretakis D, Likothanassis S. Best terms: an efficient feature-selection algorithm for text categorization[J]. Knowledge & Information Systems, 2005, 8(1): 16-33.

[10] Zheng D F, Shi B. Inductive learning algorithms and representations.

[11] 鄭世卓, 崔曉燕. 基于半監(jiān)督LDA的文本分類應(yīng)用研究[J].軟件, 2014, 35(1): 46-48.

[12] 鄭曉健. 面向領(lǐng)域主題的智能搜索引擎設(shè)計(jì)[J]. 軟件, 2014, 35(3): 4-5.

[13] 趙旭劍, 鄧思遠(yuǎn), 李波, 等. 互聯(lián)網(wǎng)新聞話題特征選擇與構(gòu)建[J]. 軟件, 2015, 36(7): 17-20.

The Research of Texts’ Similarity Algorithm Based on Topic and Features

YAO Zhen-ni
(Dept. Network Technology Research Institute, Beijing University of Posts and Telecommunications, Beijing, 100088, China)

In this paper, we proposes a texts’ similarity algorithm based on the topic and features of each text, the purpose is to accurately mine the nearest neighbor texts of a given text. Firstly, we introduces the characteristics of CHI Square Statistics and gives improvement to features selection of training text which have known topic; and then compare the minimum edit distance algorithm (LevenShtein Distance), Cosine Similarity Algorithm and Jaccard Similarity Coefficient, analyze principal defect of each algorithm and propose a new text similarity algorithm based on features and topic; after that we use the new algorithm on real data set and prove no matter in speed or accuracy the new one is better than others; In the end, the new algorithm is applied to stocks’ subject tagging, from the analysis of results, we expound recent shortage and put forward the improvement.

Data mining; The similarity between texts; Topic; Feature

TP391.1

A

10.3969/j.issn.1003-6970.2016.10.028

本文著錄格式：藥珍妮. 基于主題和特征的文本相似度算法研究[J]. 軟件，2016，37（10）：123-126