黃賢英，謝 晉，龍姝言

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

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

黃賢英，謝 晉，龍姝言

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

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

問(wèn)句相似度；N-gram模型；一元模型；公共詞塊

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

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

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

1 相關(guān)研究

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

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

表1 參數(shù)定義

1.2 公共詞塊的相似度算法

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

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

(1)

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

(2)

綜合考慮最優(yōu)子序列相似度計(jì)算方法與基于順序的相似度計(jì)算方法，對(duì)式(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模型的問(wèn)句相似度算法

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

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

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

Q1：院長(zhǎng)您好，我想請(qǐng)問(wèn)如何重修物理？

一元模型表示Q1-U：院，長(zhǎng)，您，好，我，想，請(qǐng)，問(wèn)，如，何，重，修，物，理

二元模型表示Q1-B：院長(zhǎng)，您好，我想，請(qǐng)問(wèn)，如何，重修，物理

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

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

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

將每組問(wèn)句以一元模型及二元模型的形式表示出來(lái)，分別查詢一元模型及二元模型中的公共詞塊。上述例子通過(guò)檢測(cè)可以得到：Q1-U與Q2-U的公共詞塊集合為{{院},{長(zhǎng)},{重},{修},{物},{理}}；Q1-B和Q2-B的公共詞塊集合為{{院長(zhǎng)},{重修},{物理}}。然后，將其應(yīng)用到相似度計(jì)算式(3)，得到Sim(Q1-U,Q2-U)以及Sim(Q1-B,Q2-B)，分別表示利用一元模型和二元模型表示的問(wèn)句相似度值。對(duì)得到的兩個(gè)相似度進(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)表示問(wèn)句Q1和Q2的整體相似度；λ和1-λ表示一元模型和二元模型相似度值的比率，經(jīng)多次調(diào)整參數(shù)值發(fā)現(xiàn)，其取值的變化對(duì)結(jié)果影響不大，因此設(shè)置參數(shù)值為0.5。

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

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

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

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

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

(5)

(6)

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

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

算法1：余弦相似度算法

算法2：最長(zhǎng)公共子序列算法

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

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

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

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

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

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

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

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

3.4 結(jié)果分析

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

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

4 結(jié)束語(yǔ)

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

[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] 徐海洲.自動(dòng)問(wèn)答系統(tǒng)中問(wèn)句相似度計(jì)算方法研究[D].南昌:華東交通大學(xué),2014.

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

[8] 李吉月.中文社區(qū)問(wèn)答系統(tǒng)中問(wèn)題檢索技術(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é)報(bào)(自然科學(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].圖書(shū)情報(bào)工作,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)，重慶市社會(huì)科學(xué)規(guī)劃博士項(xiàng)目(2015BS059)

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

黃賢英，謝晉，龍姝言.基于公共詞塊及N-gram模型的問(wèn)句相似度算法[J].重慶理工大學(xué)學(xué)報(bào)(自然科學(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