文本相似度計算

1、 文本相似度計算系統(tǒng)摘要在中文信息處理中，文本相似度的計算廣泛應用于信息檢索、機器翻譯、自動問答系統(tǒng)、文本挖掘等領域，是一個非常基礎而關鍵的問題，長期以來一直是人們研究的熱點和難點。本次畢設的設計目標就是用兩種方法來實現(xiàn)文本相似度的計算。本文采用傳統(tǒng)的設計方法，第一種是余弦算法。余弦算法是一種易于理解且結(jié)果易于觀察的算法。通過余弦算法可以快捷的計算出文本間相似度，并通過余弦算法的結(jié)果（0、1之間）判斷出相似度的大小。由于余弦計算是在空間向量模型的基礎上，所以說要想用余弦算法來完成本次系統(tǒng)，那么必須要將文本轉(zhuǎn)化成空間向量模型。而完成空間向量模型的轉(zhuǎn)換則要用到加權。在空間向量模型實現(xiàn)之前，必須要進

2、行文本的去停用詞處理和特征選擇的處理。第二種算法是BM25算法，本文將采用最基礎的循環(huán)來完成，目的是觀察余弦算法中使用倒排索引效率是否提高有多大提高。本次文本相似度計算系統(tǒng)的主要工作是去除停用詞、文本特征選擇、加權，在加權之后用余弦算法計算文本的相似度。在文本特征選擇之后用BM25計算相似度。由于為了使系統(tǒng)的效率提高，在程序設計中應用了大量的容器知識以及內(nèi)積、倒排算法。關鍵詞：文本相似度；余弦；BM25；容器TextSimilarityAlgorithmResearchAbstractInChineseinformationprocessing，textsimilaritycomputatio

3、niswidelyusedintheareaofinformationretrieval，machinetranslation,automaticquestionanswering，textminingandetcItisaveryessentialandimportantissuethatpeoplestudyasahotspotanddifficultyforalongtimeCurrently，mosttextsimilarityalgorithmsarebasedonvectorspacemodel(VSM)However,thesemethodswillcauseproblemsof

4、highdimensionandsparsenessMoreover，thesemethodsdonoteffectivelysolvenaturallanguageproblemsexistedintextdataThesenaturallanguageproblemsaresynonymandpolysemeTheseproblemssidturbtheefficiencyandaccuracyoftextsimilarityalgorithmsandmaketheperformanceoftextsimilaritycomputationdeclineThispaperusesanewt

5、houghtwhichgetssemanticsimiralitycomputationintotraditionaltextsimilaritycomputationtoprovetheperformanceoftextsimilarityalgorithmsThispaperdeeplydiscussestheexistingtextsimilarityalgorithmsandsamentictextcomputationandgivesaChinesetextsimilarityalgorithmwhichisbasedonsemanticsimilarityThereisanonli

6、neinformationmanagementsystemwhichisusedtomanagestudentsgraduatedesignpapersThosepapersaleusedtocalculatesimilaritybythatthealgorithmtovalidatethatalgorithmThistextsimilaritycomputingsystemsmainjobistostopwordremoval,textfeatureselection,weighting,afterweightingusingcosinealgorithmtocalculatethesimi

7、larityofthetext.AfterthetextfeatureselectioncalculationofsimilaritywiththeBM25.Becauseinorderforthesystemsefficiency,knowledgeapplicationinprogrammingalotofcontainersaswellastheinnerproduct,theinversionalgorithmKEYWORDS：Textsimilarity；cosine；BM25；container目錄1緒論錯誤！未定義書簽1.1開發(fā)背景錯誤！未定義書簽1.2課題研究意義錯誤！未定義書

8、簽1.3本課題要解決的問題錯誤！未定義書簽2研究方法錯誤！未定義書簽2.1根據(jù)研究的側(cè)重點闡述相關的研究方法錯誤！未定義書簽2.2歷史以及研究現(xiàn)狀錯誤！未定義書簽3關鍵問題及分析（一）（余弦）錯誤！未定義書簽3.1研究設計中的關鍵問題錯誤！未定義書簽3.2具體實現(xiàn)中采用的關鍵技術錯誤！未定義書簽3.2.1容器錯誤！未定義書簽3.2.2倒排錯誤！未定義書簽3.2.3內(nèi)積錯誤！未定義書簽3.2.4算法錯誤！未定義書簽3.3本章小結(jié)錯誤！未定義書簽4關鍵問題及分析（二）（BM25）錯誤！未定義書簽4.1研究設計中的關鍵問題錯誤！未定義書簽4.2具體實現(xiàn)中采用的關鍵技術錯誤！未定義書簽。4.2.1容器

9、錯誤！未定義書簽4.2.2算法錯誤！未定義書簽4.3本章小結(jié)錯誤！未定義書簽5系統(tǒng)設計及實現(xiàn)錯誤！未定義書簽5.1設計實現(xiàn)的策略和關鍵技術描述錯誤！未定義書簽5.2分模塊詳述系統(tǒng)各部分的實現(xiàn)方法錯誤！未定義書簽5.2.1文檔載入模塊錯誤！未定義書簽5.2.2去除停用詞模塊錯誤！未定義書簽5.2.3特征選擇模塊錯誤！未定義書簽5.2.4加權模塊錯誤！未定義書簽5.2.5余弦計算模塊錯誤！未定義書簽5.2.6BM25計算模塊錯誤！未定義書簽5.2.7相似度顯示模塊錯誤！未定義書簽5.2.8相似度導出模塊錯誤！未定義書簽5.3程序流程錯誤！未定義書簽5.4界面設計錯誤！未定義書簽5.5測試環(huán)境與測試

10、條件錯誤！未定義書簽5.6實例測試（表格）錯誤！未定義書簽5.7性能分析錯誤！未定義書簽6結(jié)論與展望錯誤！未定義書簽參考文獻錯誤！未定義書簽致謝錯誤！未定義書簽1緒論隨著計算機的廣泛應用和Intemet的普及，各類信息都在急速地膨脹。信息量的增長給人們帶來了方便，同時也帶來了信息過量的問題。面對海量信息，人們越來越希望能夠在數(shù)據(jù)分析的基礎上進行科學研究、商業(yè)決策和企業(yè)管理，帶來經(jīng)濟效益或社會效益。在現(xiàn)實世界中，文本是最重要的信息載體。因此對文本文檔的處理和分析成為當今數(shù)據(jù)挖掘和信息檢索技術的熱點之一。處理和研究文本文檔的技術有很多，其中重要的一個技術就是文本相似度，它在文本聚類、Web智能檢索

11、、問答系統(tǒng)、網(wǎng)頁去重、自然語言處理等很多領域中有著重要的應用，文本相似度是這些應用的關鍵。本次目標就是做出文本相似度的計算工具，用兩種算法來計算文本間的相似度。11開發(fā)背景：文本相似度有著比較廣泛的應用，典型的應用有：(1)信息智能檢索：搜索引擎對用戶輸入關鍵字的反應是列出所有與該關鍵字相匹配的網(wǎng)頁。這些網(wǎng)頁的數(shù)量之大，往往要以十萬百萬來計量，而且對于某一關鍵字檢索出來的網(wǎng)頁有可能對應于不同的主題。這些各種主題的網(wǎng)頁有些沒有相關性，有些內(nèi)容很相似。這種各類主題雜亂在一起的搜索結(jié)果和冗余頁面給用戶找到自己感興趣的信息帶來極大的不便。如果利用文本相似度技術，對搜索結(jié)果進行進一步的處理，在搜索結(jié)果中

12、將相似度很高的信息分為不同類別，或者去掉相似度很高的重復的信息，為用戶提供一個清晰的導航。這將大大的有利于用戶發(fā)現(xiàn)自己感興趣的信息，提高信息檢索的質(zhì)量。(2)自動問答系統(tǒng)：在這種系統(tǒng)中，問題是多種多樣，且非常巨大的，有些問題是非常相似的，如果用人工來回答，將耗費大量的時間和人力，如果在這種系統(tǒng)中應用文本相似度技術，將相似度很高的問題歸為一類，使系統(tǒng)對這類問題自動做出答復，將節(jié)省大量的時間。(3)文本查重：在某些領域，考慮到隱私性和獨創(chuàng)性，要求文本不能重復出現(xiàn)，那么應用文本相似度技術，對這類文本進行相似度的計算，就可以看出哪些文本多次出現(xiàn)。因此，研究文本相似度的算法具有重要的實際價值。12課題研

13、究意義文本相似度計算系統(tǒng)是自然語言處理的一部分，可以計算一個文本中不同詞條的相似度，可以計算倆個文本間的相似度也可以進行批處理，對多個文本之間進行兩兩計算，并輸出文本間相似度的最后結(jié)果。文本相似度除了簡單的計算相似度外，還可以在其基礎上進一步發(fā)展，成為其他的功能軟件。其中最主要的體現(xiàn)就是檢索工具與信息挖掘，例如：語義檢索、招聘信息檢索等。在這些軟件中，文本相似度計算系統(tǒng)起到了決定性的作用。文本相似度計算系統(tǒng)中的去除停用詞功能、文本特征選擇以及加權功能還可以單個的拿出，作為單獨的一個程序或者成為其他系統(tǒng)的一部分。13本課題要解決的問題文本相似度計算系統(tǒng)包括去除停用詞、文本特征選擇、加權、余弦算法

14、、BM25算法。在去除停用詞中，主要的問題就是選詞范圍和set容器的使用。由于給出的詞語前面是有詞性的，所以在選詞的時候要注意將詞性去掉。這樣才能得到準確的結(jié)果。雖然去除停用詞這一功能十分的簡單。但是由于它是第一個功能，所以一定要保持它的正確性。文本的特征選擇目的是選出那些重要但是又不是每行都有的詞，并且輸出該詞語的特征量。所以在特征選擇這一項，我在程序中做了三個模塊，選出那些特征為一的特殊詞語，并且刪除。由于BM25計算方法是在特征選擇之后進行的，所以在這一部分還特別為BM25就算出了不為一的文本等。加權是在文本特征選擇之后，是為余弦做準備。通過加權可以得到文本的空間向量模型，由于該結(jié)果為全

15、數(shù)字，所以要十分的主要加權的準確性。余弦算法作為該程序的兩個算法之一，是該程序的靈魂所在，在余弦算法中除了VC基本知識、容器之外還用到了倒排索引和內(nèi)積。余弦算法也是該程序的難點之一。BM25算法是一種很陌生的算法，很多人都可能是第一次聽過，BM25算法具有準確這一特點，是一種十分專業(yè)的算法。BM25算法中只用到了循環(huán)，目的是驗證倒排索引、內(nèi)積等方法可以提高多少效率。2研究方法21根據(jù)研究的側(cè)重點闡述相關的研究方法目前較為常用的相似度計算方法有許多，例如本次程序要用到的余弦相似度就算方法和BM25相似度計算方法。除此之外內(nèi)積相似度計算方法，SMART相似度計算方法、PivotedNormalis

16、ation相似度計算方法、Log-linear相似度計算方法等。但是由于相似度的用途、方法等原因，很多方法都是不常見的。余弦算法作為大家熟知的計算方法而被廣泛的應用。在本次程序中，主要的流程就是將語料去除停用詞，之后進行文本的特征選擇，將特征項為一的和特征項與文本數(shù)相同的去掉。接下來進行文本加權，將語料變?yōu)橐粋€空間向量模型。最后通過內(nèi)積與倒排索引按照余弦公式最終計算出文本間的相似度大小。BM25算法是一種嚴謹?shù)挠嬎惴椒ǎ诖舜雾椖恐?，進行特征選擇之后就可以開始進行計算了。BM25比余弦好的地方在于其不用經(jīng)過加權形成空間向量模型，但是它在公式中也有一部類似加權的計算步驟。22歷史以及研究現(xiàn)狀目前

17、，國內(nèi)外很多學者在研究文本相似度計算問題，并提出了一些解決方案和技術，在這些技術中，Salton等人(1975)提出的向量空間模型(VSM)是最常用的方法。Salton等人(1975)的觀點是，向量空間模型VSM的基本思想是把文檔簡化為以特征項的權重為分量的向量表示，它假設詞與詞間不相關，用向量來表示文本，從而簡化了文本中的關鍵詞之間的復雜關系，文檔用十分簡單的向量表示，使得模型具備了可計算性。這種機制通過為文檔中的索引項分配權重來實現(xiàn)。權重應該能體現(xiàn)關鍵詞的重要程度，是對整個文檔的描述能力，和區(qū)別其他文檔的區(qū)分能力的量化。特征項的權重計算一般利用統(tǒng)計的方法獲得，通常使用詞頻來表示?；谙蛄康?/p>

18、文本相似度計算方法是最常用的文本相似度計算方法，該方法將要比較相似度的文本根據(jù)文本中的詞語將文本映射為n維空間向量，然后通過比較向量間的關系來確定文本間的相似度，其中最為常用的方法是計算向量間的余弦系數(shù)。Frakes等人(1992)的觀點是，向量空間模型的最大優(yōu)點在于它在知識表示方法上的巨大優(yōu)勢，在該模型中，文本內(nèi)容被形式化為多維空間中的一個點，通過向量的形式給出，把對文本內(nèi)容的處理簡化為向量空間中向量的運算。潘有能(2002)，魯松(2000)等人的觀點是，向量的權重計算可以通過簡單的頻數(shù)統(tǒng)計來完成，使問題的復雜性大為降低。向量空間模型的缺點在于關鍵詞之間的線性無關的假說前提。在自然語義中，

19、詞或短語間存在十分密切的聯(lián)系，很難滿足假定的條件，因此對計算結(jié)果的可靠性造成一定的影響。此外，將復雜的語義關系歸結(jié)為簡單的向量結(jié)構(gòu)，丟失了許多有價值的線索。因此，引進改進技術以獲取深層語義結(jié)構(gòu)是有必要的。同時權值計算是相似度計算里面關鍵的部分，如何定義最準確的權值也是向量空間模型要考慮的一大問題。此外其他學者在文本相似度計算方法上也提出了不同的見解，如哥倫比亞大學的CarbonellJ.等人(1998)提出的最大邊緣相關的方法MMR(MaximalMarginalRelevance)方法。Lambms等人(1994)提出同時依據(jù)句子的表層結(jié)構(gòu)和內(nèi)容計算相似度的方法。在計算相似度時，系統(tǒng)使用了兩

20、級動態(tài)規(guī)劃技術，應用動態(tài)規(guī)劃算法允許在兩個長度不同的句子之間計算語句相似度。Nirenburg等人(1993)提出了兩種串匹配的方法，即更規(guī)范的“切塊+匹配+重組”方法和整句級匹配的方法，這兩種方法所采用的相似度衡量機制都是詞組合法。該系統(tǒng)的相似度計算采用罰分制，兩個句子匹配所得到的總罰分值由句子中每個對應單詞對的比較所得的罰分組合而成。其它方法還有根據(jù)Ricardo(2005)所提到的Belkin和Croft于1992年提出的概率型。Lee(2005)、Lipika(2006)、0ng(2006)和Blaz(2006)等人的觀點是，一個類別主要是以用機器學習的方法，比如聚類分析和模糊邏輯去構(gòu)

21、造文本的本體模型，然后用這些模型，根據(jù)Navigli(2005)、Sugumaran(2005)等人的觀點，對文本進行處理。但是，這些方法需要分析整個文檔語料庫去構(gòu)造一個好的本體模型，而且文本處理的好壞取決于構(gòu)造本體模型的良好程度。在語料分析中，一些項在文本中很少出現(xiàn)，因為他們的出現(xiàn)頻率很低，而往往被忽視。然而，根據(jù)信息理論，這些少見的項卻對文本處理來說是有價值的。忽視他們在構(gòu)建本體模型的時候可能會影響文本處理的性能。這些基于本體的方法也沒有完全能和LSI抗衡。3關鍵問題及分析(一)(余弦)研究設計中的關鍵問題余弦:關鍵問題是先要明確余弦的相關定義，理解公式每個地方代表了什么，之后理解相關定義

22、的內(nèi)容，最后結(jié)合C+中的容器知識解決問題。去除停用詞預處理：在計算余弦算法之前，必須要有預處理的過程，其中包括去除停用詞和特征選擇。去除停用詞主要就是按照停用詞表中的詞語將語料中不常見的符號，標點級亂碼去掉。在去除停用詞中除了用到基本的輸入輸出流，還用到了set容器。set容器重要作用在本次去除停用詞過程中存儲“哈工大停用詞表”，在用循環(huán)輸入“三類語料”，如果在set容器中就去掉，不在就輸出。set容器是容器中最常用也是最基礎的知識，下面具體介紹了set容器的基本操作。set容器：定義一個元素為整數(shù)的集合a,可以用seta;基本操作：對集合a中元素的有插入元素：a.insert(1);刪除元素

23、(如果存在)：a.erase(1);判斷元素是否屬于集合：if(a.find(1)!=a.end()特征選擇：特征選擇的目的：特征選擇也屬于預處理中的一部分，其最終的目的是將文本中只在一行出現(xiàn)的詞語和在每行都出現(xiàn)的詞語去掉。特征選擇的實現(xiàn)方法：在特征選擇中用到了set、map、multimap三中容器。首先用set容器來存放去停用詞后的文本。在這里set起到的功能與去除停用詞中功能是一樣的。map是STL的一個關聯(lián)容器，它提供一對一（其中第一個可以稱為關鍵字，每個關鍵字只能在map中出現(xiàn)一次，第二個可能稱為該關鍵字的值）的數(shù)據(jù)處理能力，由于這個特性map內(nèi)部的實現(xiàn)自建一顆紅黑樹（一種非嚴格意義

24、上的平衡二叉樹），這顆樹具有對數(shù)據(jù)自動排序的功能。由于map容器排序的特性，得到得特征排序的很亂的，所以用到了multimap。Multimap所起到的作用就是一個排序的作用，他使得最終結(jié)果按特征選擇的值來排序，為后面的去除做一個準備。在進行文本的特征選擇之后要像去除停用詞一樣去除特征為1的和特征數(shù)等于文本行數(shù)的特征。因為特征為1的表示特征過小，只在一行出現(xiàn)，對文本的影響不大。而特征數(shù)過大的與文本行數(shù)相等的說明每一行都出現(xiàn)了，不具有代表行。加權：由于用余弦來計算相似度，所以引入了空間模型的概念。G.Salton提出的向量空間模型（VSM）有較好的計算性和可操作性，是近年來應用較多且效果較好的一

25、種模型，向量空間模型最早成功應用于信息檢索領域，后來又在文本分類領域得到了廣泛的運用。向量空間模型的假設是，一份文檔所屬的類別僅與某些特定的詞或詞組在該文檔中出現(xiàn)的頻數(shù)有關，而與這些單詞或詞組在該文檔中出現(xiàn)的位置或順序無關。也就是說，如果將構(gòu)成文本的各種詞義單位（如單詞i、詞組）統(tǒng)稱為“詞項”以及詞頻在文本中出現(xiàn)的頻數(shù)稱為“詞頻”，那么一份文檔中蘊含的各個詞項的詞頻信息足以用來對其進行正確的分類。在向量空間模型中的文本被形式化為n維空間中的向量：其中略利為第i個特征的權重。向量空間模型：向量空間模型重簡單方面說就是一個完全由向量所組成的文本，由于余弦算法是按照向量的夾角來計算的，所以必須通過加

26、權來計算出每個詞語的權重。加權公式：IDF（q）logN其中N為文本的總行數(shù)，n為出現(xiàn)該詞語的總行in（q）i數(shù)。具體實現(xiàn)中采用的關鍵技術容器本系統(tǒng)主要運用的map容器和vector容器的相關知識。下面先介紹map容器相關的知識：map容器：Map是STL的一個關聯(lián)容器，它提供一對一(其中第一個可以稱為關鍵字，每個關鍵字只能在map中出現(xiàn)一次，第二個可能稱為該關鍵字的值)的數(shù)據(jù)處理能力，由于這個特性，它完成有可能在我們處理一對一數(shù)據(jù)的時候，在編程上提供快速通道。這里說下map內(nèi)部數(shù)據(jù)的組織，map內(nèi)部自建一顆紅黑樹(一種非嚴格意義上的平衡二叉樹)，這顆樹具有對數(shù)據(jù)自動排序的功能，所以在map內(nèi)

27、部所有的數(shù)據(jù)都是有序的，后邊我們會見識到有序的好處。下面舉例說明什么是一對一的數(shù)據(jù)映射。比如一個班級中，每個學生的學號跟他的姓名就存在著一一映射的關系，這個模型用map可能輕易描述，很明顯學號用int描述，姓名用字符串描述。Vector容器的相關知識如下：vector是C+標準模板庫中的部分內(nèi)容，它是一個多功能的，能夠操作多種數(shù)據(jù)結(jié)構(gòu)和算法的模板類和函數(shù)庫。vector是一個容器，它能夠存放各種類型的對象，簡單地說，vector是一個能夠存放任意類型的動態(tài)數(shù)組，可以動態(tài)改變大小。倒排索引倒排索引的概念：這種索引表中的每一項都包括一個屬性值和具有該屬性值的各記錄的地址。由于不是由記錄來確定屬性值

28、，而是由屬性值來確定記錄的位置，因而稱為倒排索引(invertedindex)。帶有倒排索引的文件我們稱為倒排索引文件，簡稱倒排文件倒排的應用：倒排的目的是為了使計算的方法簡便，使程序的效率提高。倒排就是用mapint,mapdp這樣一個大的復合容器來將結(jié)果顯示為3列。for(mapint,map:iteratori=dp.begin();i!=dp.end();i+)for(map:iteratorj=i-second.begin();j!=i-second.end();j+)writefirstfirstsecondn;這樣就將文件成一個3列的輸出，為后面的內(nèi)積計算做了一個鋪墊。內(nèi)積內(nèi)積(

29、innerproduct)，又稱數(shù)量積(scalarproduct)、點積(dotproduct)他是一種矢量運算，但其結(jié)果為某一數(shù)值，并非向量。設矢量A二al,a2,.an,B二bl,b2.bn則矢量A和B的內(nèi)積表示為：AB=alXbl+a2Xb2+anXbnAB=|A|X|B|Xcos0|A|=(al2+a22+.+an2)(1/2);|B|=(b12+b22+.+bn2)(1/2).其中，|A|和|B|分別是向量A和B的模，是0向量A和向量B的夾角(0e0,n)。若B為單位向量，即|B|=1時，AB=|A|Xcos0，表示向量A在B方向的投影長度。向量A為單位向量時同理。算法初看余弦相似

30、度的公式，不明所以的人一定會對復雜的數(shù)學符號感到頭疼，其實大可不必，下面我摘錄了一個比較通俗易懂的余弦相似度的解釋：在向量空間模型中，文本泛指各種機器可讀的記錄。用D(Document)表示,特征項(Term，用t表示)是指出現(xiàn)在文檔D中且能夠代表該文檔內(nèi)容的基本語言單位，主要是由詞或者短語構(gòu)成，文本可以用特征項集表示為D(T1,T2,Tn)，其中Tk是特征項，1二k二N。例如一篇文檔中有a、b、c、d四個特征項，那么這篇文檔就可以表示為D(a，b，c，d)。對含有n個特征項的文本而言，通常會給每個特征項賦予一定的權重表示其重要程度。即D=D(T1,W1；T2,W2；，Tn，Wn),簡記為D=

31、D(W1,W2,Wn),我們把它叫做文本D的向量表示。其中Wk是Tk的權重，1二k=N。在上面那個例子中，假設a、b、c、d的權重分別為30，20，20，10，那么該文本的向量表示為D(30，20，20，10)。在向量空間模型中，兩個文本D1和D2之間的內(nèi)容相關度Sim(Dl,D2)常用向量之間夾角的余弦值表示，公式為：珀門.花V丘1出1其中，Wlk、W2k分別表示文本D1和D2第K個特征項的權值，1=k=No在自動歸類中，我們可以利用類似的方法來計算待歸類文檔和某類目的相關度。例如文本D1的特征項為a，b，c，d,權值分別為30，20，20，10，類目Cl的特征項為a，c，d，e，權值分別為

32、40，30，20，10，貝UD1的向量表示為D1(30,20,20,10,0),C1的向量表示為C1(40，0，30，20，10)，則根據(jù)上式計算出來的文本D1與類目C1相關度是0.86那么0.86具體是怎么推導出來的呢？在數(shù)學當中，n維向量是Vv1,v2,v3,.,vn他的模：|v|=sqrt(v1*v1+v2*v2+.+vn*vn)兩個向量的點擊m*n=n1*m1+n2*m2+nn*mn相似度=(m*n)/(|m|*|n|)物理意義就是兩個向量的空間夾角的余弦數(shù)值下面是代入公式的過程：d1*c1=30*40+20*0+20*30+10*20+0*10=2000|d1|=sqrt(30*30

33、+20*20+20*20+10*10+0*0)=sqrt(1800)|c1|=sqrt(40*40+0*0+30*30+20*20+10*10)=sqrt(3000)相似度=d1*c1/(|d1|*|c1|)=2000/sqrt(1800*3000)=0.860663.3本章小結(jié)本章主要介紹了余弦相似度的具體算法，余弦計算前去除停用詞、文本特征選擇、加權和如何利用C+中的容器來書寫程序描述這個算法。對于一個給定的算法，我們主要的精力是研究如何用程序來實現(xiàn)這個算法，我個人覺得這個有些南轅北轍的味道，我們應該從最深處理解算法的精髓，能寫出算法的人是大師，而用程序?qū)崿F(xiàn)算法的人只是一個程序員，由于個人

34、的原因，本人的數(shù)學功底有些差，但是我會再以后的道路上努力彌補自己的不足，完善自我。4關鍵問題及分析（三）（BM25）研究設計中的關鍵問題本章節(jié)主要面對的問題是1.BM25的數(shù)學公式是什么？2.BM25公式的主要的參數(shù)是什么意思？3.用程序?qū)崿F(xiàn)BM25的算法用到哪些相關的知識？具體實現(xiàn)中采用的關鍵技術4.2.1容器本章主要用到了map容器和vector容器。解釋map容器：Map是STL的一個關聯(lián)容器，它提供一對一（其中第一個可以稱為關鍵字，每個關鍵字只能在map中出現(xiàn)一次，第二個可能稱為該關鍵字的值）的數(shù)據(jù)處理能力，由于這個特性，它完成有可能在我們處理一對一數(shù)據(jù)的時候，在編程上提供快速通道。這

35、里說下map內(nèi)部數(shù)據(jù)的組織，map內(nèi)部自建一顆紅黑樹（一種非嚴格意義上的平衡二叉樹），這顆樹具有對數(shù)據(jù)自動排序的功能，在map內(nèi)部所有的數(shù)據(jù)都是有序的。Vector容器的相關知識如下：vector是C+標準模板庫中的部分內(nèi)容，它是一個多功能的，能夠操作多種數(shù)據(jù)結(jié)構(gòu)和算法的模板類和函數(shù)庫。vector是一個容器，它能夠存放各種類型的對象，簡單地說，vector是一個能夠存放任意類型的動態(tài)數(shù)組，可以動態(tài)改變大小。算法BM25通常用于信息檢索的領域，它是一種用于排序跟搜索關鍵詞相關的文本的一種排序的函數(shù)，最早在1970年，由S.E.Robertson等提出的，基于概率檢索的框架(probabilis

36、ticretrievalframework)發(fā)展。BM25是一個bag-of-words的檢索函數(shù)，綜合了特征在文本中的詞頻、以及在語料中的文檔頻度、平衡了文檔的長度等特征。這個函數(shù)有很多變種，其中應用最普遍的計算方法，如公式(5.2所示：score(D,Q)=蘭i=iIDF(q)-if(q,D)-(k+1)if(q,D)+k-(1-b+b-iDL)i1avgdl5.2)其中Q是用來計算的檢索的query的向量Q=q,qn,n代表向量Q的關鍵詞的個數(shù)；D是語料中的一個樣本向量D=W1,-Wm，M代表向量D特征個數(shù)；f(qi,D)是檢索詞qi的在樣本D中的出現(xiàn)的次數(shù)；1D|表示文檔D的長度(指文

37、檔中詞語的個數(shù)，包括重復的詞語)；avgdl是Q中的query檢索到的全部樣本的平均長度。匕和b是自由參數(shù)，通常情況下，ki取值為2.0，b取值為0.75。IDF(qi)5.3)是文檔頻度的倒數(shù)，是檢索詞qi的權重，計算如公式(5.3)所示：IDF(q)=log“-叫+0.5in(q)+0.5i其中N是整個數(shù)據(jù)集上的文檔總數(shù)，n(qi)是指包含檢索詞qi的文檔數(shù)。在實際計算中，耐值有可能是負數(shù)，使得的BM25值也有可能是負數(shù)，由于BM25公式中IDF(q.)偏重于未出現(xiàn)檢索詞qi和出現(xiàn)索引詞qi的樣本數(shù)的比重，對于DF值較高的索引詞，未出現(xiàn)索引詞qi的文檔個數(shù)有小于DF值，取log之后IDF(

38、qi)的值變?yōu)樨撝?。在本文的實驗中去掉了BM25值為負數(shù)的樣本。4.3本章小結(jié)BM25算法計算相比余弦算法過程要簡單的多，但是我只是運用了一個循環(huán)的方法，目的是看用“倒排”的效率，結(jié)果“不看不知道,一看下一跳”。結(jié)果不是差了一點半點啊。使用“倒排”的效率大大提高。關于BM25算法的結(jié)果，個人表示沒有余弦好理解，因為他的結(jié)果是無規(guī)律且大小相差很多，非專業(yè)人員(我)無法用BM25來看出相似度到底有多少，而余弦的結(jié)果是01之間的，可以一目了然的看到兩篇文本的相似度是多少。通過了BM25的實現(xiàn)，使我的數(shù)學有了提高，而且更加深入的了解到了如何編算法，以前總感覺算法是很難實現(xiàn)的，但是現(xiàn)在感覺已將給了公式，

39、這樣邏輯就很明了了。相信下次我會編的更好。5系統(tǒng)設計及實現(xiàn)本章從系統(tǒng)的實現(xiàn)過程，各模塊的功能、各模塊間的關系、界面設計及測試等幾個方面闡釋了系統(tǒng)的具體實現(xiàn)。5.1設計實現(xiàn)的策略和關鍵技術描述在上邊的講解里提出了關于本程序的相關模塊，在這一節(jié)里將對每個模塊進行詳細講解，并對其實現(xiàn)方法進行描述。通過設計方案可以確定出本程序主要分為如下模塊：文檔載入模塊、去除停用詞模塊、加權模塊、特征選擇模塊、余弦算法模塊、BM25算法模塊、相似度顯示模塊，相似度導出模塊。分模塊詳述系統(tǒng)各部分的實現(xiàn)方法5.2.1文檔載入模塊獲取文件的信息可包括兩個方面，一個是獲取原文本文檔（三類語料.txt）中的翻譯信息，一個是獲

40、取停用詞表（哈工大停用詞表txt）中的信息。下面分別對獲取文本文檔中的原文信息和獲取停用詞表中的信息進行詳細的介紹。1）獲取文本文檔（三類語料.txt）中的翻譯信息文本文件（txt）文件的格式相對比較簡單，本程序用C+語言讀取文本文件的方法讀取原文的信息。用了C+語言中的getline方法讀取文件信息，之后用C+語言中的istringstream函數(shù)進行分詞操作。原文格式如下：濟濟沢丘濟濟一經(jīng)經(jīng)弓經(jīng)經(jīng).定菜合產(chǎn)發(fā)賓決蔬綜生快怦院、的隔加陶彩食源制心報匡糧資及中本.，竹料為.:加大監(jiān)管力度確尿用藥歪全本報評論員最近:中西部地區(qū)外商投資優(yōu)勢產(chǎn)業(yè)目錄山西省1尿鮮和加工2.林木營造及林木良種引進3.3

41、.民族特需產(chǎn)品、工藝美術、包裝及容器材:圧紀云在黑龍江考察時強調(diào)堅持以經(jīng)濟建設:武警黑龍江省森林愿隊調(diào)集官兵投農(nóng)撲.火戰(zhàn)斗2）獲取文本文檔（哈工大停用詞表.txt）中的翻譯信息獲取停用的操作相對來說簡單了些，因為每個停用詞獨占一行，用C+語言的讀一行文件的操作即可，此處就不做詳述了。去除停用詞模塊去除停用詞的目的是去除停用詞表中的詞語，因為一個剛剛分好詞的文本會有許多不重要的詞或符號。去除停用詞的操作是一個非常常見的教科書程序，而且在我的印象中還做過相關課設，去除停用詞的方法主要就是一個循環(huán)，但是由于這次要去除的詞是在一個文本中，所以要用到一個set容器。特征選擇模塊特征選擇模塊的最終目的一共

42、有兩個，一個是輸出每個詞的特征，即在文本中有多少行含有該詞。另一個目的就是去除特征為一的詞語和特征等于該文本的總行數(shù)的詞語，因為程序的最終目的是比較相似度，特征為一的就表示該詞不是一個由代表性的詞語，而特征數(shù)與總行數(shù)相等則說明了有無該詞對相似度的結(jié)果是沒有影響的。所以我們對原文做了如下特征選擇的操作，去除每篇文章都出現(xiàn)的單詞或者有且僅有只在一篇文章中出現(xiàn)的單詞。5.2.4加權模塊對權值的解釋：權值就是指這個指標在整個分析過程中所占的重要程度，比如你買輛車你對車的屬性有幾方面認識假定只有3個方面質(zhì)量價格舒適程度你認為這個質(zhì)量對你最重要你賦權值為0.5價格其次重要賦值0.3舒適程度適當考慮并賦值0

43、.2OK我們可以以此為標準來評判你看中了車A給它三方面打分質(zhì)量90價格80舒適80車B質(zhì)量80價格90舒適80然后你把這些分數(shù)乘以相應的權值可以有A的得分90*0.5+80*0.3+80*0.2=85B的得分80*0.5+90*0.3+80*0.2=83故A車對你是較好的選擇權值就是這樣在問題分析中起到重要作用一般的權值累加為1實際上這只是習慣不為1而為任意正數(shù)都沒有關系我們在此處用了如下的加權公式：(寫公式)下面是對公式的通俗解釋(摘錄自維基百科)：有很多不同的數(shù)學公式可以用來計算TF-IDF。這邊的例子以上述的數(shù)學公式來計算。詞頻(TF)是一詞語出現(xiàn)的次數(shù)除以該文件的總詞語數(shù)。假如一篇文件

44、的總詞語數(shù)是100個，而詞語“母牛”出現(xiàn)了3次，那么“母牛”一詞在該文件中的詞頻就是0.03(3/100)。一個計算文件頻率(DF)的方法是測定有多少份文件出現(xiàn)過“母?！币辉~，然后除以文件集里包含的文件總數(shù)。所以，如果“母牛”一詞在1,000份文件出現(xiàn)過，而文件總數(shù)是10,000,000份的話，其逆向文件頻率就是4(ln(10,000,000/1,000)。最后的TF-IDF的分數(shù)為0.12(0.03*4)。5.2.5余弦計算模塊此處利用了余弦公式求解了預先相似度的值，公式如下：和向量余弦的計算方法是文本相似度計算中最常見的一種方法，標記為cosine。用向量空間模型表示文本Di和文本D2，兩

45、個向量的余弦計算，如公式6.1)所示：小r、d-dcos(D,D)=i212|d|dII125.1)工(weigh(d,t)-weightd,t)1i2ii=0weigh(d,t)2-eigh(d,t)21i2ji=0其中k表示樣本Di和樣本D2兩個向量的共現(xiàn)特征的個數(shù),n、m分別表示向量Di和D2的向量的維數(shù)。此處求的的余弦的相似度在01之間。5.2.6BM25計算模塊BM25是一個bag-of-words的檢索函數(shù)，綜合了特征在文本中的詞頻、以及在語料中的文檔頻度、平衡了文檔的長度等特征。這個函數(shù)有很多變種，其中應用最普遍的計算方法，如公式(5.2)所示：score(D,Q)二蘭IDF(q

46、)-ii=1f(q,D)(k+1)i1f(q,D)+k(1-b+b1D)i1avgdl5.2)其中Q是用來計算的檢索的query的向量Q=q，,q,n代表向量Q的關鍵詞1n的個數(shù)；D是語料中的一個樣本向量D=w.w,M代表向量D特征個數(shù)；1,Mf(q,D)是檢索詞q的在樣本D中的出現(xiàn)的次數(shù)；IDI表示文檔D的長度(指文檔ii中詞語的個數(shù)，包括重復的詞語)；avgdi是Q中的query檢索到的全部樣本的平均長度。k和b是自由參數(shù)，通常情況下，k取值為2.0，b取值為0.75。IDF(q)11i是文檔頻度的倒數(shù)，是檢索詞q的權重。iIDF(q)=log叫+0.5in(q)+0.5i其中N是整個數(shù)據(jù)

47、集上的文檔總數(shù)，叫是指包含檢索詞qi的文檔數(shù)。本模塊利用BM25算法對輸入的文章進行比對，并將生成的相似度結(jié)果顯示在ClistCtrl控件上。5.2.7相似度顯示模塊本模塊的主要作用是將兩篇文檔的余弦（BM25）的相似度結(jié)果顯示在ClistCtrl控件中，使用戶能方便快速的看到兩篇文章的余弦（BM25）相似度對比的結(jié)果。5.2.8相似度導出模塊本模塊主要做的是，將兩篇文章的余弦相似度的結(jié)果保存在文本文檔中。保存格式如下圖所示：1：111:20-02193341:30-14845二和第二篇文章的相似度之比以第二行為例：，1：20廿193己表示第一篇文章0.0219334OS1:50-136715

48、5.3程序流程（50-219212本系統(tǒng)的主要流程如下圖所示：69842581:80-1051圖1.1系統(tǒng)總的流程圖界面設計本程序的主要功能是文本相似度的計算，為了方便用戶操作，本系統(tǒng)將所有用戶需要的功能都放在了程序的顯著位置即界面的上方，并以按鈕的形式和用戶交換。下圖為用戶的主界面部分：圖1.2主界面圖當用戶按下“打開語料”按鈕時系統(tǒng)將彈出Windows文件管理工具菜單如圖所示：打開三類語料操作圖中選擇打開的是文本文檔（*.txt）。選擇三類語料這個文本文件，之后點擊打開”按鈕。打開停用詞的操作上步操作打開了“三類語料”，之后點擊“打開停用詞”按鈕，系統(tǒng)同樣會彈出Windows文件管理工具菜

49、單，如圖所示：選擇停用詞的操作選擇“哈工大停用詞表.txt”，點擊“打開”按鈕。界面如下圖所示:待輸入算法前的界面之后就可以選擇計算文本相似度的算法了，如果選擇想選擇余弦算法的話，點擊“余弦”按鈕。之后系統(tǒng)會在后臺計算余弦的相似度，并在下半部分的表格中顯示出來。顯示結(jié)果如下圖所示：EM251去停用詞1特征為一余弦序號對比行1冠比毎I卷弦駆5相似度A0111.0000001120.021933LSII2130.1484903140.0131334150.136T155160.2192126170.0698437180.10510081y0.22419191100.05723310210.02193311221.00000012230.063175V特征枷一去特征選擇加權顯示余弦相似度的界面第一列的序號代表比較的次序，第二列表示的對比行一所在的行數(shù)，第三列表示的對比行二所在的行數(shù)，第四列表示二、三列所表示的文件的余弦相似度。同樣，如果想選擇BM25算法的話，可以點擊“BM2