基于公共詞塊及N-gram模型的問句相似度算法

黃賢英，謝 晉，龍姝言

(重慶理工大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院， 重慶 400054)

基于公共詞塊及N-gram模型的問句相似度算法

黃賢英，謝 晉，龍姝言

(重慶理工大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院， 重慶 400054)

問句相似度算法是問答系統(tǒng)的核心問題，直接影響著問答系統(tǒng)的準(zhǔn)確性。針對公共詞塊算法(CCS)對于中文文本的不適用性，提出一種改進(jìn)的問句相似度算法(CNS)。該方法結(jié)合N-gram模型及公共詞塊來計(jì)算問句向量的相似度，其主要思路是把問句分解成一元模型和二元模型，然后再分析問句之間的公共詞塊并考慮其順序結(jié)構(gòu)。實(shí)驗(yàn)結(jié)果表明：新算法在Top-N條數(shù)據(jù)集的平均相似度和不同相似度閾值下的準(zhǔn)確率均優(yōu)于常用的問句相似度算法。

問句相似度；N-gram模型；一元模型；公共詞塊

近年來，隨著信息技術(shù)的飛速發(fā)展，智能問答(QA)領(lǐng)域吸引了大量的用戶[1]，問句相似度計(jì)算則成為了QA中最為關(guān)鍵的環(huán)節(jié)[2]。QA通過問句相似度計(jì)算來獲取用戶所要查詢的內(nèi)容與知識庫中現(xiàn)有問題之間的關(guān)系，再通過合理的篩選答案候選集[3]自動給出用戶滿意答案[4-5]。

目前，問句相似度算法主要使用的是針對所有句子的相似度算法[6]。這種方法忽略問句的特殊句型結(jié)構(gòu)，將問句視為短文本，利用常用的短文本處理方法來分析問句。首先對問句進(jìn)行分詞、詞性標(biāo)注、去停用詞處理，為處理后的問句賦值權(quán)重，將其轉(zhuǎn)換成向量化的形式，再使用相似度算法進(jìn)行計(jì)算。文獻(xiàn)[7]提出一種基于平均信息熵的中文問句關(guān)鍵詞提取方法，其中心思想是通過計(jì)算問句中每個詞的平均信息熵以更好地體現(xiàn)該詞在問句中的重要性。但這種算法只考慮了單個詞的貢獻(xiàn)度，沒有考慮到詞語組合的貢獻(xiàn)度。文獻(xiàn)[8]提出一種改進(jìn)的TFIDF問句相似度算法，對特征詞進(jìn)行聚類，并賦予其更高的權(quán)重，但這種算法需要有良好的分類語料庫作為支撐。文獻(xiàn)[9]考慮到了中文分詞對相似度計(jì)算的影響，提出結(jié)合多種分詞結(jié)果的相似度計(jì)算方式，但分詞方式的改變會影響句子所包含的特征詞。文獻(xiàn)[10]考慮了公共特征詞以及詞序?qū)τ谙嗨贫扔?jì)算的影響，但這種算法面向英文語料，對于中文語料有一定的約束性。

傳統(tǒng)基于詞項(xiàng)的文本相似度算法只考慮了詞項(xiàng)因素，忽略了詞序?qū)Χ涛谋鞠嗨菩缘挠绊?。本文為了將問句的詞序納入考量，引入了問句的公共詞塊信息?？紤]到中文文本與英文文本的不同，本文同時引入N-gram模型，在考慮公共詞塊及其相關(guān)順序的同時，也將漢語語言模型作為影響因子，提出一種在N-gram語言模型的基礎(chǔ)上利用公共詞塊作為計(jì)算單元的問句相似度算法。

1 相關(guān)研究

1.1 問題定義及參數(shù)

本文將Q1和Q2定義為2個不同的問句，sw(Q1,Q2)為2個問句之間都出現(xiàn)的關(guān)鍵詞個數(shù)，L(Qi)表示第i個問句中的關(guān)鍵詞個數(shù)，如表1所示。其中，pwi(Q1)表示Q1中第i個關(guān)鍵詞的權(quán)重，pwi(Q2)為Q2中第i個關(guān)鍵詞的權(quán)重。Sim1(Q1,Q2)表示基于公共子序列的相似度，Sim2(Q1,Q2)表示基于關(guān)鍵詞序的相似度。

表1 參數(shù)定義

1.2 公共詞塊的相似度算法

基于公共詞塊的相似度算法主要是將2個文本中所有連續(xù)出現(xiàn)的相同關(guān)鍵詞看作1個詞塊單元，利用所有公共詞塊中的關(guān)鍵詞計(jì)算重疊相似度，并考慮這些公共詞塊在2個文本中的出現(xiàn)順序?qū)Χ涛谋鞠嗨贫鹊挠绊?，做加?quán)處理，以提高文本相似度計(jì)算的算法性能。它的主要工作流程為：首先，從2條需要進(jìn)行相似度計(jì)算的問句中提取出共同出現(xiàn)的詞項(xiàng)；然后，在2條問句挑選出的共同詞項(xiàng)集合中，尋找2條問句都連續(xù)出現(xiàn)的共同詞組，這個共現(xiàn)詞組即為一個公共詞塊。

傳統(tǒng)的基于公共子序列的相似度算法為保證2個短文本的相對相似度一致，相似度計(jì)算方法如式(1)所示：

(1)

由于上述相似度算法未考慮公共關(guān)鍵詞出現(xiàn)的順序，文本相似度計(jì)算存在較大誤差，因此需要考慮公共關(guān)鍵詞的詞序，相似度計(jì)算如下：

(2)

綜合考慮最優(yōu)子序列相似度計(jì)算方法與基于順序的相似度計(jì)算方法，對式(1)和(2)做加權(quán)處理。文獻(xiàn)[10]提出一種基于公共詞塊的相似度計(jì)算方法，如式(3)所示：

Sim(Q1,Q2)=α*Sim1(Q1,Q2)+

β*Sim2(Q1,Q2)

(3)

其中α+β=1。文獻(xiàn)[10]詳細(xì)解釋了參數(shù)的取值。

2基于公共詞塊及N-gram模型的問句相似度算法

N-gram語言模型是一種基于統(tǒng)計(jì)的文本模型，其算法的基本思想是將文本內(nèi)容按字節(jié)流進(jìn)行大小為N的滑動窗口操作，形成長度為N的字節(jié)片斷序列，每個字節(jié)片斷被稱為gram。對全部gram的出現(xiàn)頻度進(jìn)行統(tǒng)計(jì)，并按照事先設(shè)定的閾值進(jìn)行過濾，形成關(guān)鍵gram列表，即為該文本內(nèi)容的特征向量空間，列表中每一種gram均為一個特征向量維度[12]。因此，在處理中文語料時，使用N-gram模型不需要對文本內(nèi)容進(jìn)行語言學(xué)處理，也不需要構(gòu)建詞典和規(guī)則，能避免中文文本分詞過程中的數(shù)據(jù)缺失，可有效保留特征項(xiàng)之間的關(guān)系。

在中文文本中應(yīng)用公共詞塊的相似度算法，由于時常會存在檢測不到公共詞塊的問題，因此會影響相似度的計(jì)算。例如：通過中文分詞得到{飛機(jī)場}和{飛機(jī)}，這2個詞項(xiàng)相似度很高，但他們不屬于公共詞塊，因此忽略了二者之間的相似關(guān)系。針對這一問題，本文提出了基于公共詞塊及N-gram模型的問句相似度算法，綜合考慮了中文文本一元模型和二元模型表示時的作用各不相同的情況，通過結(jié)合一元模型及二元模型作為特征來表示問句，并融合問句之間的公共詞塊共同表征問句相似度，以提高相似度計(jì)算的準(zhǔn)確率。

首先，對于需要進(jìn)行相似度計(jì)算的2條問句Q1和Q2，使用中科院分詞工具ICTCLAS進(jìn)行一元模型及二元模型表示。示例如下：

Q1：院長您好，我想請問如何重修物理？

一元模型表示Q1-U：院，長，您，好，我，想，請，問，如，何，重，修，物，理

二元模型表示Q1-B：院長，您好，我想，請問，如何，重修，物理

Q2：院長，辦理物理重修需要哪些手續(xù)？

一元模型表示Q2-U：院，長，辦，理，物，理，重，修，需，要，哪，些，手，續(xù)

二元模型表示Q2-B：院長，辦理，物理，重修，需要，哪些，手續(xù)

將每組問句以一元模型及二元模型的形式表示出來，分別查詢一元模型及二元模型中的公共詞塊。上述例子通過檢測可以得到：Q1-U與Q2-U的公共詞塊集合為{{院},{長},{重},{修},{物},{理}}；Q1-B和Q2-B的公共詞塊集合為{{院長},{重修},{物理}}。然后，將其應(yīng)用到相似度計(jì)算式(3)，得到Sim(Q1-U,Q2-U)以及Sim(Q1-B,Q2-B)，分別表示利用一元模型和二元模型表示的問句相似度值。對得到的兩個相似度進(jìn)行加權(quán)處理，如式(4)所示：

Sim-T(Q1,Q2)=λ×Sim(Q1-U,Q2-U)+

(1-λ)×Sim(Q1-B,Q2-B)

(4)

其中：Sim-T(Q1,Q2)表示問句Q1和Q2的整體相似度；λ和1-λ表示一元模型和二元模型相似度值的比率，經(jīng)多次調(diào)整參數(shù)值發(fā)現(xiàn)，其取值的變化對結(jié)果影響不大，因此設(shè)置參數(shù)值為0.5。

3 實(shí)驗(yàn)與分析

3.1 實(shí)驗(yàn)數(shù)據(jù)

實(shí)驗(yàn)數(shù)據(jù)來自重慶理工大學(xué)計(jì)算機(jī)學(xué)院院長信箱(“http://cs.cqut.edu.cn/ DeanMail/MailList.aspx”)，選取了“2014年4月1日—2017年4月1日”共6 129條數(shù)據(jù)，并清洗掉無文字的數(shù)據(jù)(數(shù)據(jù)中存在一些由特殊符號或表情組成的無法識別的信息)。數(shù)據(jù)格式如表2所示。

3.2 實(shí)驗(yàn)評價標(biāo)準(zhǔn)

實(shí)驗(yàn)評價標(biāo)準(zhǔn)分為3部分：第1部分為不同數(shù)據(jù)集數(shù)目時相似度平均值的比較；第2部分為不同相似度閾值下的準(zhǔn)確率比較；第3部分為不同相似度閾值下的召回率比較。

(5)

(6)

3.3 實(shí)驗(yàn)結(jié)果

選取表2中學(xué)生所提出的問題內(nèi)容和問題回復(fù)這2項(xiàng)作為相似度計(jì)算的對比數(shù)據(jù)集，同時選取3種常規(guī)算法進(jìn)行對比試驗(yàn)。

算法1：余弦相似度算法

算法2：最長公共子序列算法

算法3：基于公共詞塊的相似度算法

表3直觀地反映出當(dāng)前N條數(shù)據(jù)作為數(shù)據(jù)集時，4種算法的相似度平均值。由實(shí)驗(yàn)結(jié)果可以看出：算法1的相似度平均值保持在0.09～0.11；算法2的相似度平均值保持在0.08～0.09；算法3的相似度平均值保持在0.20～0.22；而本文算法的相似度平均值高于前3個算法，保持在0.36～0.41附近。

在表4中，分別比較算法1、算法2、算法3以及本文算法在不同相似度閾值下的準(zhǔn)確率。各算法在不同相似度閾值下的準(zhǔn)確率對比如圖1所示。

表3 各算法在不同數(shù)據(jù)集數(shù)目時的相似度平均值

表4 各算法在不同相似度閾值下的準(zhǔn)確率

從圖1可以看出：算法1即使在較小的閾值下準(zhǔn)確率依然偏低；算法3及本文算法的準(zhǔn)確率明顯高于前兩種算法，但算法3的準(zhǔn)確率在不同閾值下的波動性偏大，當(dāng)閾值大于0.19時，其準(zhǔn)確率驟減；本文算法相比其他算法，在準(zhǔn)確率及穩(wěn)定性方面均有提高。從圖2可以看出：算法1的召回率低于其他方法；當(dāng)相似度閾值低于0.1時，算法2、算法3和本文算法的召回率基本接近100%；當(dāng)相似度閾值大于0.3時，本文算法的召回率最大，算法2 和算法3 的召回率基本相同，其中算法3略大于算法2。

圖1 各算法在不同相似度閾值下的準(zhǔn)確率對比

圖2 各算法在不同相似度閾值下的召回率對比

3.4 結(jié)果分析

本文在實(shí)驗(yàn)部分主要比較了基于詞項(xiàng)的余弦相似度算法、基于詞項(xiàng)的最長公共子序列相似度算法、基于公共詞塊的相似度算法以及本文算法。

基于詞項(xiàng)的余弦相似度算法只集中于獨(dú)立詞項(xiàng)的相同數(shù)量關(guān)系，未考慮詞項(xiàng)間的詞序關(guān)系，雖然相似度均值較大，召回率較低?；谠~項(xiàng)的最長公共子序列相似度算法集中于句子對間的最長公共子序列，考慮了詞序信息，但僅提取部分共現(xiàn)詞，相似度均值不高?；诠苍~塊的相似度算法加入了公共詞塊信息，考慮詞序關(guān)系影響，通過對句子中共現(xiàn)詞的數(shù)量自動調(diào)整加權(quán)系數(shù)，但在使用中文分詞器劃分公共詞塊時存在較大的誤差，會導(dǎo)致錯分或漏分。本文算法既考慮了共現(xiàn)詞的詞項(xiàng)信息，又兼顧了詞項(xiàng)間的詞序信息，并將N-gram模型融入算法，改善了劃分公共詞塊的準(zhǔn)確性，得到了較高的相似度均值，同時具有較好的穩(wěn)定性。

4 結(jié)束語

本文針對基于最優(yōu)公共子序列和利用公共詞塊計(jì)算中文文本相似度時存在的缺陷，提出一種結(jié)合N-gram模型及公共詞塊的新方法。這種方法既考慮了中文文本在尋找公共詞塊時的稀疏性，又加大了詞塊之間的相似性，從而避免了因該詞項(xiàng)未被公共詞塊收錄而出現(xiàn)較大實(shí)驗(yàn)誤差的情況。在實(shí)驗(yàn)部分對比了本文算法和其他3種相似度計(jì)算方法。實(shí)驗(yàn)結(jié)果表明：本文算法在相似度平均值以及相似度準(zhǔn)確率方面有良好的表現(xiàn)。本文算法的不足之處是：在表示問句文本時并未考慮語義信息，因此在今后的研究中將考慮同義詞項(xiàng)的重要性以及問句的語義相似度。

[1] AMIRI H,RESNIK P,BOYD G J,et al.Learning Text Pair Similarity with Context-sensitive Autoencoders[C]//Meeting of the Association for Computational Linguistics. Germany:[s.n.],2016:1882-1892.

[2] GAIZAUSKAS R,HUMPHREYS K.A Combined IR/NLP Approach to Question Answering Against Large Text Collections[C]//Proceedings of the 6th Content-based Multimedia Information Access(RlAO-2000).France:[s.n.],2000.

[3] VOORHEES E.The TREC-8 Question Answering TrackReport[C]//Proceedings of the Eighth Text Retrieval Conference(TREC 2002).USA:[s.n.],2002.

[4] POONAM G,VISHAI G.A Survey of Text Question Answering Techniques[J],International Journal of Computer Applications,2013,53(4):1-8.

[5] MATTHEW W B,ERIC N.Improving Text Retrieval Precision and Answer Accuracy in Question Answering Systems[C]//Proceedings of the 2nd workshop onInformation Retrieval for Question Answering(Coling 2008),Manchester.UK:[s.n.],2008:1-8.

[6] 徐海洲.自動問答系統(tǒng)中問句相似度計(jì)算方法研究[D].南昌:華東交通大學(xué),2014.

[7] 丁菲菲,楊思春,劉仁金.基于平均信息熵的中文問句關(guān)鍵詞提取[J].皖西學(xué)院學(xué)報,2014(5):46-49.

[8] 李吉月.中文社區(qū)問答系統(tǒng)中問題檢索技術(shù)研究[D].北京：北京理工大學(xué),2016.

[9] JIANG R,KIM S,BANCHS R E,et al.Towards improving the performance of Vector Space Model for Chinese Frequently Asked Question Answering[C]//International Conference on Asian Language Processing.China:IEEE,2015:136-139.

[10] 黃賢英,劉英濤,饒勤菲.一種基于公共詞塊的英文短文本相似度算法[J].重慶理工大學(xué)學(xué)報(自然科學(xué)),2015,29(8):88-93.

[11] SEVERYN A,NICOSIA M,MOSCHITTI A.Learning Semantic Textual Similarity with Structural Representations[C]//51st Annual Meeting of the Association for Computational Linguistics.Bulgaria:[s.n.],2013:714-718.

[12] 于津凱,王映雪,陳懷楚.一種基于N-Gram改進(jìn)的文本特征提取算法[J].圖書情報工作,2004,48(8):48-50.

(責(zé)任編輯楊黎麗)

QuestionSimilarityAlgorithmBasedonCommonChunksandN-GramModel

HUANG Xianying, XIE Jin, LONG Shuyan

(College of Computer Science and Engineering, Chongqing University of Technology, Chongqing 400054, China)

Question similarity algorithm is the key problem of QA, which directly affects the accuracy of QA. Aiming at the non applicability of the common chunks similarity algorithm (CCS) to Chinese text, an improved question similarity algorithm (CNS) is proposed, which combines the N-gram model and the common chunks to compute the similarity of the question vectors. The main idea is to break the question into unigram model and bigram model, then to analyze the common chunks between the questions and consider their sequential structure. Experimental results show that the new algorithm is better than the commonly used question similarity algorithms in the average similarity of Top-N data sets and the accuracy of different similarity threshold.

question similarity; N-gram model; unigram model; common chunks

2017-02-25

教育部人文社科青年項(xiàng)目(16YJC860010)，重慶市社會科學(xué)規(guī)劃博士項(xiàng)目(2015BS059)

黃賢英(1967—)，女，重慶人，教授，碩士生導(dǎo)師，主要從事信息檢索、移動計(jì)算研究，E-mail:hxy@cqut.edu.cn；謝晉(1993—)，男，湖北十堰人，碩士研究生，主要從事信息檢索、文本挖掘研究,E-mail: 895309382@qq.com。

黃賢英，謝晉，龍姝言.基于公共詞塊及N-gram模型的問句相似度算法[J].重慶理工大學(xué)學(xué)報(自然科學(xué))，2017(10):175-179，197.

formatHUANG Xianying, XIE Jin, LONG Shuyan.Question Similarity Algorithm Based on Common Chunks and N-Gram Model[J].Journal of Chongqing University of Technology(Natural Science)，2017(10):175-179，197.

10.3969/j.issn.1674-8425(z).2017.10.028

TP391.1

A

1674-8425(2017)10-0175-05