基于關鍵詞提取的TFIDF和TextRank方法的對比研究

1、基于關鍵詞提取的 TFIDF 和 TextRank 方法的對比研究題目：開發(fā)一個程序，在該程序中，允許輸入一段文本（以界面或者文件輸入方式均可）， 該程序自動抽取出包含的關鍵詞，并按照關鍵詞的權(quán)重由高到低排序后輸出。完成日期： 2016.06.05一、需求分析以文本的形式讀入數(shù)據(jù)，將每個單詞抽象成一棵樹，將單詞與單詞之間的關 系抽象為圖。TFIDF算法部分以EXCEL形式將所有數(shù)據(jù)輸出，TextRank算法部分直接以窗 口形式輸出排名前十位的數(shù)據(jù)。本程序的目的是在提取文本關鍵詞的同時，比較TFDIF和TextRank算法的準確性和性能方面的差異。測試數(shù)據(jù)（附后）。二、概要設計抽象數(shù)據(jù)類型映射樹

2、定義如下：ADT Map 數(shù)據(jù)對象 ID： ID 是類型為 char 的元素集合，即為一個單詞中的單個字 符，稱為字符集。數(shù)據(jù)對象 val ：val 是類型為 double 或 int 的元素集合，為每個單詞對應 的 TF 值或 IDF 值，稱為頻率集。數(shù)據(jù)對象 is_end ：is_end 是類型為 bool 的元素集合，判斷當前子結(jié)點是 否為單詞末尾數(shù)據(jù)關系 R :R= IDVal IDVal= word num| word ID , num val，表示從 word 至U num 之間的一一映射 運算符重載：下標運算符 :運算對象為 string 值，返回對應 string 值的子樹所代

3、表的 val 值。算術運算符 = ：運算對象為 double 或 int 值，等式左值的 val 值 替換為等式右值，并返回當前子樹。算術運算符 +-*/ :運算對象為 double 或 int 值，對其 val 值進行運算，并返回當前子樹。相等運算符 = 和!= : 運算對象為 val 值，判斷其 val 值是否相等， 返回對應的 bool 值?；静僮鳎篒nitMap(&T);操作結(jié)果：構(gòu)造空樹。DestroyMap(&T);初始條件：樹 T 存在。操作結(jié)果：構(gòu)造空樹。CreateMap(&T, word);初始條件：樹 T 存在且 word 為 string 值。 操作結(jié)果：按照 wor

4、d 的字符順序自上而下遍歷，如果有字 符結(jié)點未創(chuàng)造，則構(gòu)造新子結(jié)點，直到字符結(jié)束。MapEmpty(T);初始條件：樹 T 存在。操作結(jié)果：若T為空樹，則返回True，否則False。MapDepth(&T);初始條件：樹T存在。操作結(jié)果：返回樹的深度。Root(&T);初始條件：樹T存在。操作結(jié)果：返回 T 的根。Value(&T, value);初始條件：樹T存在，value為T中某個結(jié)點的值。 操作結(jié)果：返回 value 的值。Assign(&T, word, value);初始條件：樹T存在，且word結(jié)點也存在。操作結(jié)果：結(jié)點 word 的 value 值替換為當前 value 。P

5、arent(&T, word);初始條件：樹T存在，且word結(jié)點也存在。操作結(jié)果：返回 word 結(jié)點的雙親。InsertWord (&T, word);初始條件：樹 T 存在。操作結(jié)果：往樹加入 word 值，并將其 value 值默認初始化DeleteChild(&T, word);初始條件：樹 T 存在，且 word 結(jié)點也存在。操作結(jié)果：將 word 對應子節(jié)點的 is_end 值改為 false 。TraverseMap(&T, visit() );初始條件：樹 T 存在， visit 是對結(jié)點操作的應用函數(shù)。操作結(jié)果：按某種次序?qū)?T 的每個結(jié)點調(diào)用 visit 一次且至 多一次

6、。一旦 visit 失敗，則操作失敗。ADT Map抽象數(shù)據(jù)類型圖定義如下ADT Graph數(shù)據(jù)對象 n：n 是具有相同特征的數(shù)據(jù)元素集合，稱為頂點集。 數(shù)據(jù)關系：DR=|v,w n且表示從v指向w的 弧基本操作：CreateGraph(&G, V, VR) ;初始條件：V是圖的頂點集，VR是圖中弧的集合操作結(jié)果：按V和VR的定義構(gòu)造圖GDestroyGraph(&G);初始條件：圖G存在操作結(jié)果：銷毀圖 GLocateVex (G,u);初始條件：圖G已存在，u和G中頂點有相同特征 操作結(jié)果：若G中存在頂點u,則返回該頂點在圖中位置， 否則返回其它信息GetVex(G, v);初始條件：圖G

7、存在，v是G中某個頂點 操作結(jié)果：返回 v 的值PutVex(&G, v, value);初始條件：圖G存在，v是G中某個頂點操作結(jié)果：對 v 賦值 valueFirstAdjVex(G, v);初始條件：圖G存在，v是G中某個頂點操作結(jié)果：返回v的第一個鄰接頂點。若頂點在 G中沒有鄰 接頂點，則返回“空”NextAdjVex(G, v, w);初始條件：圖G存在，v是G中某個頂點，w是v的鄰接頂點操作結(jié)果：返回v的(相對于w的)下一個鄰接頂點。若 w是 v 的最后一個鄰接點，則返回 空”InsertVex (&G,v);初始條件：圖G存在，v和G中頂點有相同特征 操作結(jié)果：在圖中增添新頂點

8、vDeleteVex (&G,v);初始條件：圖G存在，v是G中某個頂點 操作結(jié)果：刪除G中頂點v及其相關的弧InsertArc(&G, v, w)初始條件：圖G存在，v和w是G中兩個頂點 操作結(jié)果：在圖G中增添弧v,w，若G是無向的，則還應 增添對稱弧 w,vDeleteArc(&G, v, w)初始條件：圖G存在，v和w是G中兩個頂點操作結(jié)果：刪除G中的弧vv,w，若G是無向的，則還應刪 除對稱弧DFSTraverse(G, v, visit()初始條件：圖G存在，v是G中某個頂點，visit是對頂點 的應用函數(shù)操作結(jié)果：從頂點v起深度優(yōu)先遍歷圖 G,并對每個頂點調(diào) 用函數(shù) visit()

9、 一次且至多一次。一旦 visit() 失敗，則操作失敗BFSTraverse(G, v, visit()初始條件：圖G存在，v是G中某個頂點，visit是對頂點 的應用函數(shù)操作結(jié)果：從頂點v起廣度優(yōu)先遍歷圖 G,并對每個頂點調(diào) 用函數(shù) visit() 一次且至多一次。一旦visit() 失敗，則操作失敗ADT Graph本程序包含兩大模塊， TF-IDF 算法部分和 TextRank 算法部分主函數(shù)部分void mai n () TF-IDF 算法；TextRank 算法;TF-IDF 算法構(gòu)建語料庫（語料庫的原料來源于超過八億詞的文本）導入語料庫讀入文本分析所讀入的單詞合并語料庫輸出到EX

10、CELTextRank 算法讀入數(shù)據(jù)分析所讀入的單詞構(gòu)造矩陣套用公式結(jié)果排序輸出前十名各模塊之間的調(diào)用關系如下:導入語料庫分析所讀入的單詞讀入文本f、合并語料庫構(gòu)造矩陣7套用公式fX輸出到EXCEL結(jié)果排序輸出前十名三、詳細設計設計思路TF-IDF和TextRank關鍵詞提取算法，進本程序以實現(xiàn)關鍵詞抽取為目的，選取了 行兩者的效率和準確性的比較研究。TFIDF 算法. TF-IDF算法簡介TF-IDF是一種統(tǒng)計方法，用以評估一字詞對于一個文件集或一個語料庫中的其中一個詞組 或短語的重要程度。字詞的重要性隨著它在文件中出現(xiàn)的次數(shù)成正比增加，但同時會隨著它在語料庫中出現(xiàn)的頻率成反比下降。在一組文

11、檔中，刻畫某一文檔特征的特征項可以根 據(jù)其在這組文檔中出現(xiàn)的頻率賦予相應的權(quán)重，只有在少數(shù)文檔中出現(xiàn)的較特殊的詞，權(quán) 重要比在多篇文檔中出現(xiàn)的詞的權(quán)重要高。TF-IDF加權(quán)的各種形式常被搜索引擎應用，作為文件與用戶查詢之間相關程度的度量或評級。. TF-IDF算法原理TF-IDF實際上是 TF和IDF的組合。TF即詞頻（Term Frequency），IDF即逆向文檔）。頻率（In verse Docume nt Freque ncyTF （詞頻）就是某個詞在文章中出現(xiàn)的次數(shù)，此文章為需要分析的文本。為了統(tǒng)一標準，有如下兩種計算方法TF （詞頻）某個詞在文章中出現(xiàn)的次數(shù)該篇文章的總次數(shù)TF詞頻

12、_某個詞在文章中出現(xiàn)的次數(shù)_ 該篇文章出現(xiàn)最多的單詞的次數(shù)IDF （逆向文檔頻率）為該詞的常見程度，需要構(gòu)建一個語料庫來模擬語言的使用環(huán)境。IDF逆向文檔頻率語料庫的文檔總數(shù)包含該詞的文檔總數(shù)+ 1【2】如果一個詞越常見，那么其分母就越大，IDF值就越小。? ?=?司頻 X?逆文檔頻率）之后，將每個單詞的 TF-IDF值按從大到小降序排列，排在最前面的幾個詞即為關鍵!詞。. TF-IDF算法實現(xiàn). 構(gòu)建映射Map類C+STL函數(shù)庫中已經(jīng)包含了 map的庫函數(shù)，但為了使用起來更加方便、更便于個性化定制操作，于是使用自己定制的Map類模板。這個類函數(shù)主要是構(gòu)建單詞的stri ng 值與其TF、ID

13、F值的一一對應關系，方便直接用string 值下標訪問其int值或double值，簡化寫代碼的工作量。同時模板類中主要采取樹形結(jié)構(gòu)，建立一棵查找樹，利用vector的空間動態(tài)分配的靈活性，從stri ng 的第一個字母開始一個一個往下找。每個Map類代表*一個字母，從根部開始向下遍歷，利用bool值判斷該處是否為一個單詞結(jié)尾。代碼如下：映射函數(shù)Map類Type為存儲的 TF、IDF、TF-IDF值，如 int、double 等 旨在通過string類型下標訪問其Type值template class Mappublic :/Type 值，類型為 int、doubleType val = NUL

14、L/*下標運算符重載中值為string類型如果該string值已存在，則返回對應val如果不存在則新建一個，返回初始值*/Type&operator (string item)Map&temp = find( item );/引用類函數(shù)find()查找到的值if (temp != NULL/找到，則返回對應val一個并返回新的值create( item); return find( item ).val;/*算術運算符=重載左值為找到的Map.val引用右值為對應的val值返回當前Map勺引用*Map&operator = (Typeitem ):*類函數(shù)列表find為查找函數(shù)，找到則返回其值

15、，沒找到則新建一個返回初值create為創(chuàng)建新值得函數(shù)*/Mapfi nd( stri ng word);void create( stringword);private :/是否為單詞結(jié)尾/代表當前類的字母/子節(jié)點集合bool is_e nd = false char ID;vector childs;/*find查找函數(shù)如果該string值已存在，則返回對應值如果不存在則新建一個，返回初始值*/template Map Map:fi nd(stri ng word)for ( auto &r : childs)/遍歷類函數(shù)的所有子節(jié)點直到找到對應項if (r-ID = word0 & r-

16、is_end)/如果相等且為單詞末尾return r-find(word.substr(1, word.size() - 1);/ 遞歸調(diào)用 find函數(shù)，一次減少一個字符return NULL/返回空類|/*create創(chuàng)建函數(shù)遞歸創(chuàng)建字母樹*template vclass Typevoid Map:create( string word) return/如果找到，則減少第一個字符，繼續(xù)遞歸向下遍歷r-creat( word.substr(1, word.size() - 1);return ;Map*temp = n ewMap/沒找到，則新建一個Maptemp-ID = word 0;/

17、將其所代表的字符ID設為當前word的第一個字符childs.push_back(temp);/子節(jié)點中增加這一 Maptemp-creat( word.substr(1, word.size() - 1);/ 繼續(xù)遞歸創(chuàng)建后續(xù)字符return ;構(gòu)建語料庫為了使語料庫更符合本程序的應用場景，語料庫采用自己構(gòu)建的語料庫。語料庫素材來源于小說新聞等，總詞數(shù)超過8億詞。因為每篇文檔有幾十萬字，為了使詞語的ITF更具普遍性，假設每1000詞為一篇文章。然后每次將文章先存入一個臨時語料庫中，進行分析處理后，將處理后的詞加入臨時語料庫。之后再將臨時語料庫合并入總的語料庫，流程圖如下：定義語料庫 定義臨時

18、語料庫 循環(huán)讀入文件corpus r.first +;/合并語料庫中對應數(shù)值/建立語料庫/語料庫，由字/文章總數(shù)，作為計算頻mapstring , double corpus; 母string到岀現(xiàn)頻率double的映射 longlongint times = 0;率的基數(shù)ofstreamoutput( corpus.csv);/輸岀到excel表格中存儲吠*導入制作好的語料庫存在一一映射corpus中*/void buildCorpus() |ifstream input( corpus.csv );/ 打開文件stri ng item;/定義臨時存儲變量string和doubledoubl

19、e val;while (!input.eof()庫映射中in put item val; corpus item = val; 丁/讀入文件，存儲到語料/*分析處理讀入的string短語先刪去字符前的不必要符號如數(shù)字、標點(等等將剩下的大寫字符轉(zhuǎn)化為小寫|_保留字符中的標點，女口 Mr.Bill等再刪除字符后的不必要標點，如.,:等等返回修改后的字符*/string analysis(string item )string temp =;bool flag = false ;個字母時，flag變?yōu)閠rue，否則為false，濾過不必要的前綴for ( auto &r : item )/遍歷s

20、tring中每一個字符if (r =,| r =;)continue ;/定義空字符/flag標記，當碰到第/濾過,;等符號if (r = a )/ 碰到字母標記 trueflag = true ;if (r = A )/ 轉(zhuǎn)化大小寫flag = true ;r += 32;if (flag)/如果已碰到字母，則在緩存string中加入該字符temp += r;if (temp.size() = 0)/如果是空字符，直接returnreturn temp;for ( auto i = temp.rbegin(); i= temp.rend(); i+)/從尾開始遍歷string ,刪去stri

21、ng中不必要的后綴 1if ( *i = a)/若碰到字母，則跳岀循break;temp.pop_back();/ 刪去后綴return temp;/返回處理過的字符str ing/*遍歷臨時語料庫的數(shù)值將其合并到總的語料庫*/void print(mapstring , double &frequency )for ( auto &r : frequency )/ 遍歷臨時語料庫if (corpus.find(r.first)= corpus.end()/ 第一次岀現(xiàn)則將在總語料庫中新建一個，并將其初始化corpus r.first = 0.0;/*創(chuàng)建語料庫通過文件讀入文章由于部分文章為小

22、說，有幾十萬字，于是統(tǒng)一按每1000字為一篇文章語料庫素材中所有文章的總次數(shù)大概有8億詞將該文章中出現(xiàn)的單詞存入臨時語料庫中每一千字更新總語料庫corpus，清空臨時語料庫frequency |最后計算每個單詞的IDF值 */void readDictEn()int words = 0;/記錄當前已讀入的 word詞數(shù)，每一千字更新一次maestri ng , double freque ncy;/ 臨時語料庫，存放string單詞到double頻率的一一映射Ion glo ngintent = 0;臨時變量，記錄臨時語料庫被清零多少次for ( int i = 1; i = 633; i+)

23、/ 遍歷語料庫素材 TXT文檔，共有633個TXT文檔，每篇文檔平均12萬詞/*每篇文檔的命名方式為EN(i),i為文檔編號先利用stringstream流創(chuàng)建文件名的字符串再用ifstream流打開對應文件*/cout i : ;/輸岀當前讀入文件狀態(tài)ostr in gstream out;/stri ngstream流，存儲文件名字符串/打開文件/臨時存儲變量/讀入文件/將讀入字符串處理成所out EN ( i item;item = an alysis(item);需要求if (item.empty()/空字符串則略過continue ;if (frequency.find(item)=

24、 frequency.end()/ 女口果是新的字符串，則在語料庫里新建一個并初始化frequency item = 0.0;frequency item +; words+;if (words = 1000)篇文章時，合并語料庫并清空臨時語料庫pr in t(freque ncy); freque ncy.clear(); cn t+;words = 0;/增加岀現(xiàn)次數(shù)/讀入一千詞時，即讀入for ( auto &r : corpus)r.sec ond /= (ent + 1);r.sec ond = abs(log(r.sec on d); output r.first r.second

25、 freque ncy;/打開文件/單詞總數(shù)，包括相同的單詞/這篇文章的語料庫while (!file.eof()/循環(huán)讀入文章中所有單過程類似/以下過程與構(gòu)建語料庫file item; item = an alysis(item);if (item.empty()continue ;if (idle.find(item)!= idle.end()continue ;if (frequency.find(item)= frequency.end()frequency item = 0.0;frequency item +; words+;/輸岀數(shù)據(jù)到Exceloutput.open( data

26、.csv);for ( auto &r : frequency)r.sec ond /= words;r.second *= corpus r.first ;output r.first, r.second PageRank的基本思想主要是：一個網(wǎng)頁的重要程度取決于鏈接到它的網(wǎng)頁的數(shù)量以及這些網(wǎng)頁的重要程度。比如有n個網(wǎng)頁，對于其中一個網(wǎng)頁？?，所有鏈接到？?的頁面集合記為In ?所有?鏈接到的頁面集 合記為Out ?，則其重要程度為：1Importanee ?=Importanee ?Out ?3n ?此處的求和號可以通過矩陣計算來模擬實現(xiàn)，并通過不斷地迭代，重要性的值會不斷 收斂為一常值，

27、最后可以求出最后的網(wǎng)頁重要性。TextRank就是仿造這算法設計?！?】算法思路TextRank總體思路與PageRank類似。因為文本中不存在窗口與鏈接，所以要模擬造 出窗口。在這里不妨設 k個詞為一個窗口，其中每個單詞為一個鏈接，當一個窗口中的單 詞與另一個窗口中的單詞一樣時，即視為兩個窗口有鏈接。當然也可以脫離PageRa nk的思想來解釋這一算法。對于一個句子，其中的一個單詞 與這個句子的剩余單詞都有關聯(lián)性。同時，這個句子中的每一個單詞又與另外其他句子中 相同的單詞也有關聯(lián)性。也就是說，一個單詞的重要性不僅僅取決于單詞的重要性，還與 該句子中其他單詞的重要性相關。但為了使構(gòu)造出來的矩陣

28、運算更為簡便，在此將單詞句子假定為長度為k，每個單詞為k的第一個單詞。這樣，每k個單詞就構(gòu)成一個句子，句子與句子中任意兩個單詞之間就構(gòu)成一條邊，最后形成的圖是一個無向圖。為了加快運算速度，圖采用鄰接矩陣的方式 存儲。而且，經(jīng)過實際檢驗可以發(fā)現(xiàn)，該矩陣并不稀疏，所以直接轉(zhuǎn)化為二維數(shù)組。每次 計算時就不斷按照公式迭代。如此循環(huán)遍歷下去，這樣不僅得到的矩陣運算方便計算，而 且對結(jié)果的準確性也沒有影響。迭代公式如下：Importanee ?1=1- ?+?Importanee ?Out ?In Word其中d是阻尼系數(shù)，一般設置為0.85。初始時，可以先設重要性為1。容易看出，經(jīng)過多次迭代后，該重要性

29、的值會逐漸收斂為一常數(shù)。. TextRank算法實現(xiàn)TextRank所主要用到的主要是圖的鄰接矩陣存儲，矩陣相乘合并等數(shù)據(jù)結(jié)構(gòu)算法。流 程圖如下：定義鄰接矩陣阻尼向量讀入文件正序遍歷去除前綴構(gòu)造結(jié)構(gòu)體將矩陣結(jié)果信息轉(zhuǎn)存到結(jié)構(gòu)體中對其進行排序算法代碼如下:ifstream EnF ile; ofstream output; str in gstream tempFile;set idle;mapstring , int EnMatr打印前十個結(jié)果 int EnRank = 0;con sti nt k = 8;int key1000010000;作為關鍵詞抽取結(jié)果double d 510000;

30、double ans10000;/*讀入文件并去除停用詞仿造TF-IDF的方法，對讀入的詞進行分析處理將文章中處理過的詞按照原來的順序存入stringstream流tempFile中將每個詞按照構(gòu)造語料庫的方法，存入語料庫中構(gòu)建單詞圖的鄰接矩陣*/void scan( string namifstream stop( Stop.txt);while (!stop.eof()stri ng temp;stop temp;idle.i nsert(temp);EnFile.open( nam; stri ng temp;while (!EnFile.eof()keyEnMatr temp EnMa

31、tr r +;keyEnMatr temp EnMatr r +;EnF ile temp; temp = an alysis(temp);if (idle.find(temp)!= idle.end()continue ;if (temp =)continue ;if (EnMatr.find(temp)= EnMatr.end()EnMatr temp = EnRank+; tempFile temp /*讀入文件并去除停用詞仿造TF-IDF的方法，對讀入的詞進行分析處理將文章中處理過的詞按照原來的順序存入stringstream流tempFile中將每個詞按照構(gòu)造語料庫的方法，存入語料庫中構(gòu)建單詞圖的鄰接矩陣*/void build()stri ng bufferk;fc)r ( int i = 0; i bufferi;for ( int i = 0; !tempFile.eof(); i = (i + 1) % k)/ 將string 流中的數(shù)據(jù)讀入循環(huán)數(shù)組中/為節(jié)省空間，數(shù)組只開k項，利用循環(huán)數(shù)組存儲更新stri ng temp = bufferi;for ( auto &r : buffer)/ 構(gòu)造鄰接矩陣if (r = temp)con ti nuetempFile