【正文】 年 6 月系 （ 所 ） 計算機(jī)科學(xué)與技術(shù) 系 (所) 主任 批 準(zhǔn) 日 期 畢業(yè)設(shè)計(論文)任務(wù)書 電信學(xué) 院 計算機(jī) 系 84 班 學(xué)生 豐成平 畢業(yè)設(shè)計(論文)工作自 2013 年 2 月 21 日起至 2013 年 6 月 20 日止畢業(yè)設(shè)計(論文)進(jìn)行地點(diǎn)： 西安交通大學(xué) 課題的背景、意義及培養(yǎng)目標(biāo) 隨著文本文件的增多，對其自動進(jìn)行分門別類尤為重要。本畢設(shè)論文研究文本分類器的設(shè)計與實(shí)現(xiàn)。 中科院文本分詞工具(nlpir)。 3．設(shè)計并編程實(shí)現(xiàn)文本分類器。 課題的基本要求(工程設(shè)計類題應(yīng)有技術(shù)經(jīng)濟(jì)分析要求)程序可演示。這樣用機(jī)器代替人來“閱讀”文章，用機(jī)器代替人來“整理”文章，不僅減輕了工作人員的負(fù)擔(dān)，而且大大節(jié)省了時間，工作人員可以去做更多有意義的事情。最后，將文本分類運(yùn)用于眾多領(lǐng)域，例如：信息過濾、文檔管理、網(wǎng)絡(luò)安全、電子圖書整理、網(wǎng)絡(luò)圖書館，搜索引擎，這樣則不是通過關(guān)鍵字過濾，而是基于文本內(nèi)容的過濾或者是搜索，能大大提高過濾的可靠性以及搜索的準(zhǔn)確性，無疑使文本領(lǐng)域的一項重大的突破關(guān) 鍵 詞：文本向量；特征降維；分類算法；分類器設(shè)計。 Characteristics will be。 Classification algorithms。甚至同一個人，在不同的時間不同的地點(diǎn)，對一篇文章的分類頁不盡相同，這樣，很多嚴(yán)峻的問題隨之而來。如用引入文本分類系統(tǒng)，當(dāng)查詢某個關(guān)鍵字的時候，可以自動判定與之相關(guān)的文件類別，基于內(nèi)容的查詢，可以直接命5第一章 緒論中目標(biāo)，查詢速度和精度能得到有效的提升、網(wǎng)絡(luò)圖書館方面的應(yīng)用 任何一個圖書館的館藏資源成千上萬，如果沒能很好的分門別類，大量的圖書便會雜亂無章，不僅浪費(fèi)工作人員的時間進(jìn)行整理和查詢，而且讀者在找尋自己想要的圖書方面也會花費(fèi)很大的時間。目前 電信綠色上網(wǎng)，360綠色上網(wǎng)等都可以考慮引入此引擎，相信效果會更上一層樓。 到目前為止，文本自動分類在國外大致經(jīng)歷了三個發(fā)展階段： 預(yù)測分析階段（19581964）判斷文本分類是否能夠真正的在現(xiàn)實(shí)社會中起到作用 實(shí)際運(yùn)用構(gòu)思階段（19651974）主要進(jìn)行文本分類的初步構(gòu)思，形成大概的理論和框架。、文本分類的發(fā)展趨勢展望 只要漢語甚至語言文字依舊在使用，那么文本分類將永遠(yuǎn)有自己的重要性，而且隨著文字?jǐn)?shù)目的增多，文件類別的加劇，文本分類引擎將會越來越得到各界人士的關(guān)注，運(yùn)用領(lǐng)域?qū)絹碓綇V泛，重要性也會越來越高。開始訓(xùn)練集、測試集語料庫輸入文本采用中科院nlpir分詞 文本分詞TFIDF計算權(quán)值空間文本向量降維方法向量降維分類方法：svm/決策樹...進(jìn)行文本分類Weka、C++、matlab仿真最終結(jié)果 圖21 文本分類過程圖第二章文本分類的國主要過程、關(guān)于語料庫、文本分類語料庫介紹 本次試驗(yàn)中采用復(fù)旦大學(xué)語料庫，分為訓(xùn)練集與測試集，訓(xùn)練集20個類別，共計9804篇，測試集20個類別，共計9833篇。、文本分類，訓(xùn)練階段的主要步驟（1） 定義類別集合C={C1，C2，（2） 然后輸出所有分類的文本的類別，并對結(jié)果進(jìn)行統(tǒng)計。、文本空間向量的形成、VSM（Vector Space Model） 俗稱向量空間模型。 最后，一篇文章就被轉(zhuǎn)化為一個n維向量空間中的一個點(diǎn)，n可以理解為詞典中包括的總詞/短語數(shù)。Wi 說明：?、向量是有順序的，如果在詞典中未出現(xiàn)，那么該位標(biāo)記為0或者在該向量形成的時候，前面做標(biāo)記位進(jìn)行識別。詞頻與反文檔頻率的大體思想是：一個字詞對這篇文章的重要性隨著它在本篇文章中出現(xiàn)的次數(shù)正比例增加，但是相對整體語料庫而言，如果在整體語料庫中出現(xiàn)的次數(shù)太多，該字詞的表征作用會呈反比例下降。TFIDF最后得到i的權(quán)值公式為 （24） 舉例3：綜合例1，例2，那么地球這個詞，在語料庫中的權(quán)值為：TF*IDF=*3=TFIDF計算權(quán)值的好處分析 首先，如果不使用此方法，例如地球的公轉(zhuǎn)，“地球” 、“的”、 “公轉(zhuǎn)” 在文章中出現(xiàn)的次數(shù)分別為100、5，如果只是統(tǒng)計詞頻，假設(shè)文章有一千詞，那么三個詞的詞頻分別為： ， , 顯然，“的”的詞頻很大，但是“的”占了絕大部分，顯然這個詞不能表示本文的特征，反之，地球與公轉(zhuǎn)這兩個詞能表征文本大意，但是所占的比例卻相當(dāng)?shù)男?。最終的詞典長度和空間向量的長度是相同的。、信息增益方法在介紹信息增益方法之前，首先引入一個熵的概念，對于一些互斥事件，如果所有事件發(fā)生的概率之和為1，那么這個事件相應(yīng)的就有一個對應(yīng)的熵，熵的計算公式如下： （25）稱為事件X的的信息熵。一篇文章包含的詞可能有一千個，我們可以選取其中的前500個進(jìn)行試驗(yàn)，也可以選取100個 甚至10個進(jìn)行試驗(yàn)，只是最后得到的結(jié)果會有差異，對于結(jié)果如何，在后面的試驗(yàn)中會有詳細(xì)的數(shù)據(jù)對比。 、互信息方法互信息原本是信息論中的一個概念，主要表示兩個事物之間的相關(guān)程度，把互信息應(yīng)用到文本分類中，則很明顯可知，互信息表示的是特征詞t與文本類別C之間的關(guān)系，例如某個特征詞t對類別C1的表征作用比較高，但是對其他類別的表征作用比較低，那么這個詞相對于該類別的互信息就比較高。、X^2統(tǒng)計方法X^2統(tǒng)計方法表示特征詞t與文本類別C的相關(guān)度，顧名思義，當(dāng)然是相關(guān)度越高，該特征詞對某個類別的表征作用越明顯，反之表征作用越低。、本章小結(jié) 本章首先介紹了文本分類的總體過程，然后分而敘述各個比較重要的部分，講述了語料庫的大概結(jié)構(gòu)，講解了如何將一篇毫無邏輯的純文本文章形成為空間向量，然后如何對向量進(jìn)行處理，使其更簡易計算。、k臨近分類器、KNN算法概述KNN算法（即K鄰近算法），這種算法可以說是最簡單而又普遍的算法，通過尋找相鄰的點(diǎn)，然后計算各個點(diǎn)和所要決策的點(diǎn)之間的距離，從中找出距離最近的一個點(diǎn)，那么要判斷的點(diǎn)就屬于那個點(diǎn)所在的類別。y(di,cj)是判斷di這個文本是否屬于類別，屬于類別，則其值為1，反之其值為0。例如在某個語料庫中，可能其中某個類別里面的文章數(shù)比較多，而另外一個類別里面的文章數(shù)很少，那么在選擇的時候，肯定文章數(shù)比較多的文章靠近S的點(diǎn)會比較多，這樣就相當(dāng)于定向的將結(jié)果趨近于文章數(shù)比較多的那個類別，因此，在使用KNN分類算法時，訓(xùn)練集語料庫中的各個類別的文本數(shù)最好比較平均為好，這也是為什么本人在試驗(yàn)的時候，不直接把復(fù)旦語料庫直接拿來應(yīng)用，而是經(jīng)過自己處理進(jìn)行使用，就是為了保證結(jié)果的合理性。xb=0 表示一個超平面的公式，其中x是超平面上的點(diǎn),w表示垂直平面的一個向量，b的取值可以理解為是位移不斷的改變b的取值，可以在腦海中構(gòu)思，會形成很多個平行于原本平面的平面，然后我們從這些平面中選取2個平面： 這兩個平面到原本平面的距離是相等的，一個在原平面的上方，一個在下方，或一個左邊一個右邊，可以形象的這樣進(jìn)行理解，引入這個的目的是什么呢，接下來會以圖結(jié)合文字的方法進(jìn)行敘述。||W||表示二范數(shù)，可以理解為正常情況下的求向量的長度，求M的最大值，相當(dāng)于求W的最小值 用公式形象的表示為： （33）此式還有一個約束條件，如下： （34） （35）、線性不可分以上為線性可分的情況，直接用一條直線或者空間平面就可以對其進(jìn)行劃分，而在實(shí)際文本分類的過程中，肯定是存在相當(dāng)多的點(diǎn)，這些點(diǎn)錯綜交雜，不可能如以上那樣那么有條理，而是零散的分布在空間的多個區(qū)域，針對這種情況，要引入懲罰函數(shù)，如下圖所示：圖35 曲線劃分圖示 圖36 懲罰函數(shù)引入圖第一種方法：可以用一條曲線進(jìn)行劃分；第二種方法：還是如以上所說，用一條直線，但是在這條直線中，加入一個懲罰因子，懲罰函數(shù)的計算公式為： （36）由于這里面在劃分的時候，強(qiáng)制性的將原本不屬于該類別的點(diǎn)劃分如該類別中，所以加入懲罰函數(shù)權(quán)衡這樣做帶來的后果，當(dāng)然在最后計算中，懲罰函數(shù)越小越小，盡量產(chǎn)生更少的劃分錯誤的點(diǎn)。SVM采用核函數(shù)映射向高維空間，努力尋找最優(yōu)平面，而在分類決策的時候，支持向量起著至關(guān)重要的作用，不用涉及各個向量的測度，不用計算遍歷每個向量，在一定程度上，可以避免因維數(shù)而帶來的各種困難。上面的決策樹在第一次就將四個類兩兩分開，也有可能在第一次判斷的時候，就把某個類單獨(dú)的區(qū)分了開來，后面進(jìn)行區(qū)分的時候也是如此，每當(dāng)產(chǎn)生一個分類條件，就會單獨(dú)的決策分出一個單獨(dú)的類，這種屬于上述的一個特例。 當(dāng)此訓(xùn)練集輸入到?jīng)Q策樹分類器中，分類器就會統(tǒng)計各個屬性的信息，進(jìn)而進(jìn)行判定： 表格中的數(shù)據(jù)，對于溫度的這個屬性，冬季分別有1℃和零下8℃，春季分別為14℃、16℃，夏季分別為：37℃、32℃，秋季分別為：16℃、17℃。、決策樹分類器的構(gòu)造 這樣，當(dāng)有一條新的屬性信息到來時，前提是這則信息人們事先并不知曉它所處的季節(jié)，這樣決策樹分類器通過判斷該屬性的值，進(jìn)行判斷，權(quán)衡最終做出決策結(jié)果，該屬性到底屬于哪一個季節(jié)。舉例說明，貝葉斯算法的應(yīng)用：現(xiàn)分別有 A，B 兩個容器，在容器 A 里分別有 7 個紅球和 3 個白球，在容器 B 里有 1 個紅球和 9 個白球，現(xiàn)已知從這兩個容器里任意抽出了一個球，且是紅球，問這個紅球是來自容器 A 的概率是多少?假設(shè)已經(jīng)抽出紅球?yàn)槭录?B，從容器 A 里抽出球?yàn)槭录?A，則有：P(B) = 8 / 20，P(A) = 1 / 2，P(B | A) = 7 / 10，按照公式則有：P(A|B)=(7 / 10)*(1 / 2)/(8/20)=、貝葉斯分類器樸素貝葉斯分類器假設(shè)樣本每個特征與其他特征都不相關(guān)。 ?有類別集合C={y1,y2,...,yn}. ? 計算P(y1|x),P（y2|x）,...,P(yn|x)。 由于本次試驗(yàn)并未使用貝葉斯分類器進(jìn)行設(shè)計，因此關(guān)于此類方法了解敘述的較少，但是這種分類方法確實(shí)有自己獨(dú)到的好處，在這里不做過多的探究。X2YmXn隱含層輸出層輸入層 圖311 BP神經(jīng)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)圖 如圖所示，X1,X2,...,Xn是BP神經(jīng)網(wǎng)絡(luò)的輸入值，Y1，Y2，...，Ym是BP神經(jīng)網(wǎng)絡(luò)的預(yù)測值，ωij、ωjk 稱為神經(jīng)網(wǎng)絡(luò)的權(quán)值，或者閾值，BP神經(jīng)網(wǎng)絡(luò)可以看成是一個非線性函數(shù)，網(wǎng)絡(luò)的輸入值和預(yù)測值分別為該函數(shù)的自變量和因變量，如上圖所示的神經(jīng)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)則是表示一個從n個輸入映射到M個輸出的過程。 步驟二、隱含層輸出計算，根據(jù)輸入向量X,輸入層和隱含層之間連接權(quán)值計算隱含層輸出H。 i=1~n,j=1~l （313） j=1~l,l=1~m （314） 式中η表示學(xué)習(xí)效率。 上面一系列步驟，ab表示閾值，ijk分別對應(yīng)的長度為mln如此記憶，很有層次感。51第四章 實(shí)驗(yàn)結(jié)果分析統(tǒng)計第四章 試驗(yàn)結(jié)果分析統(tǒng)計、試驗(yàn)結(jié)果評估指標(biāo)簡介前面的部分已經(jīng)把文本分類詳細(xì)的的過程，文本分類里面主要的方法，以及各種分類器的構(gòu)造寫的非常詳細(xì)，本章就主要針對KNN、SVM這兩種方法的部分實(shí)驗(yàn)結(jié)果進(jìn)行展示和分析：試驗(yàn)結(jié)果的評測指標(biāo)，主要有兩個：查全率、查準(zhǔn)率。此分母就相當(dāng)于程序默認(rèn)的該類含有的總文章數(shù)