基于密度的樣本裁剪算法的改進及在knn中的應(yīng)用研究

1、<p><b>　　重慶大學</b></p><p><b>　　碩士學位論文</b></p><p>　　基于密度的樣本裁剪算法的改進及在kNN中的應(yīng)用研究</p><p><b>　　姓名：楊營輝</b></p><p><b>　　申請學位級別：碩士&

2、lt;/b></p><p>　　專業(yè)：計算機系統(tǒng)結(jié)構(gòu)</p><p><b>　　指導教師：熊忠陽</b></p><p><b>　　2010-04</b></p><p>　　重慶大學碩士學位論文</p><p><b>　　摘</b><

3、;/p><p><b>　　要</b></p><p><b>　　中文摘要</b></p><p>　　隨著信息技術(shù)的飛速發(fā)展和迅速普及，人們可以方便快捷地獲得大量的信息。</p><p>　　然而，在浩瀚的信息海洋里，如何快速準確地找到所需要的信息已經(jīng)成為人們不</p><p&g

4、t;　　得不面對的現(xiàn)實問題。因此，海量信息的組織管理和高效利用已經(jīng)成為急需解決</p><p>　　的問題。目前，大多數(shù)信息表現(xiàn)為文本形式，為了有效利用這些文本信息，對它</p><p>　　們進行高效、合理的分類是非常必要的。所以，文本分類已經(jīng)成為處理大量文本</p><p>　　信息的關(guān)鍵技術(shù)，并已成為數(shù)據(jù)挖掘領(lǐng)域中一個重要的研究方向。</p>&

5、lt;p>　　本文對文本分類及其相關(guān)技術(shù)進行了研究。首先介紹了文本分類的發(fā)展概況</p><p>　　和文本分類過程中的相關(guān)技術(shù)，重點介紹了文本預處理、文本的表示、文本特征</p><p>　　向量的提取、特征向量的加權(quán)、文本分類的經(jīng)典算法 kNN( k nearest neighbor)、訓</p><p>　　練樣本裁剪算法以及文本分類效果評估等；其次，分

6、析了 kNN 算法和訓練樣本裁</p><p>　　剪算法的不足并對其做出了改進。本文研究內(nèi)容和創(chuàng)新工作主要包括以下兩大方</p><p><b>　　面：</b></p><p>　　第一，對訓練樣本裁剪算法進行改進。在文本分類中，訓練集的分布狀態(tài)會</p><p>　　直接影響 kNN 分類器的效率和準確率。通過分析

7、基于密度的 kNN 文本分類器訓練</p><p>　　樣本的裁剪方法，發(fā)現(xiàn)它存在兩大不足：一是裁減之后的均勻狀態(tài)只是以 e 為半徑</p><p>　　的球形區(qū)域意義上的均勻狀態(tài)，而非最理想的均勻狀態(tài)即兩兩樣本之間的距離相</p><p>　　等；二是未對低密度區(qū)域的樣本做任何處理，裁減之后仍存在大量不均勻的區(qū)域。</p><p>　　針對

8、這兩處不足，提出了以下兩點改進：一是優(yōu)化了裁減策略，使裁減之后的訓</p><p>　　練集更趨于理想的均勻狀態(tài)；二是實現(xiàn)了對低密度區(qū)域樣本的補充。通過實驗表</p><p>　　明，改進后的算法在穩(wěn)定性和準確率方面都有明顯提高。</p><p>　　第二，對 kNN 算法進行改進。原始 kNN 算法中最佳 k 值的確定目前還沒有很</p><p

9、>　　好的方法，一般采用先設(shè)定一個初始值（一般為幾百到幾千之間），然后根據(jù)實驗</p><p>　　測試的結(jié)果來不斷的調(diào)整 k 值。這不利于 kNN 算法在實際中的推廣應(yīng)用。針對這</p><p>　　種不足，本文在基于密度的訓練樣本裁剪算法的基礎(chǔ)上提出一種改進算法。改進</p><p>　　算法的基本思路是：在給定新文本后，考慮訓練文本集中，屬于該新文本的

10、e 鄰域</p><p>　　的 k 篇文本，根據(jù)這 k 篇文本所屬的類別判定新文本所屬的類別。通過實驗表明，</p><p>　　改進算法較好的解決了 kNN 算法中參數(shù) k 取值的問題，同時，在時間效率上也要</p><p>　　優(yōu)于原始 kNN 算法。在分類效果上，改進算法跟原始 kNN 算法基本一致。</p><p>　　關(guān)鍵詞：文本

11、分類，kNN，快速分類，樣本裁剪，樣本補充</p><p><b>　　I</b></p><p>　　重慶大學碩士學位論文</p><p><b>　　英文摘要</b></p><p><b>　　ABSTRACT</b></p><p>　　Alon

12、g with the rapid development of information technology and popularization of</p><p>　　the Internet, large volumes of information can be acquired conveniently and quickly.</p><p>　　However, how t

13、o quickly and accurately find the right information in the vast</p><p>　　information ocean has become a realistic problem which people have to face. It</p><p>　　becomes an urgent requirement tha

14、t massive information could be managed in a</p><p>　　well-organized way and could be efficient ly utilized. At the present time, most</p><p>　　information exists as text. For effective utilizati

15、on of information, the efficient and</p><p>　　reasonable classification for information is very necessary. Therefore, text classification</p><p>　　has become a key technology for vast text infor

16、mation processing and has gradually</p><p>　　become an important research branch in the field of data mining.</p><p>　　Researches on text classification and its related technologies are done in

17、this paper.</p><p>　　The thesis firstly introduces general development of automated text categorization.</p><p>　　Specially, some introductions are made such as text preprocessing, text represen

18、tation,</p><p>　　feature selection, feature weighting, kNN (k nearest neighbor), the density-based</p><p>　　method for reducing the amount of training data, classification performance evaluation

19、</p><p>　　and so on. Then, we focus on the research and analysis of kNN algorithm and the</p><p>　　density-based method for reduc ing the amount of training data. Our primary works are</p>

20、<p>　　as follows.</p><p>　　Firstly, we propose an improved approach to the density-based method for</p><p>　　reducing the amount of training data in kNN. The density of training data dire

21、ctly</p><p>　　affects the efficiency and precision of kNN text classifier. Through the analysis of</p><p>　　density-based method for reducing the amount of training data in kNN text classifier,&

22、lt;/p><p>　　two disadvantages have been uncovered: one is the imperfect state of the even density</p><p>　　of the training data after reduced, which should be equal distance of every two training&l

23、t;/p><p>　　texts; and the other is absolutely no treatment of the low-density training texts, there are</p><p>　　large numbers of low-density texts in the training data after reduced. An improved&l

24、t;/p><p>　　approach to the mentioned deficiencies is proposed: the reducing strategy is optimized</p><p>　　and the method of supplementing appropriate data into training data is presented. The</

25、p><p>　　experiment shows that the improved method has a distinctly better performance both on</p><p>　　the algorithm stability and accuracy.</p><p>　　Secondly, an improved approach to

26、kNN is proposed. There wasn’t a proper</p><p>　　approach to figure the optimal k value of the original kNN algorithm, in which an initial</p><p><b>　　II</b></p><p>　　重慶大

27、學碩士學位論文</p><p><b>　　英文摘要</b></p><p>　　value was generally set between a few hundred and several thousand, and then it was</p><p>　　adjusted corresponding to the experime

28、ntal results. Actually, this is not a smart choice to</p><p>　　promote kNN algorithm in practice. Concerned with the deficiency, an improved</p><p>　　approach is proposed based on the density-ba

29、sed method for reducing the amount of</p><p>　　training data in this paper. The improved algorithm is briefly as follows: we find out the</p><p>　　k nearest neighbors which are in the e-neighbor

30、hood of the new text. Then we classify</p><p>　　the new text based on the k nearest neighbors. Results show that, the improved</p><p>　　algorithm can solve the problem of the k value's deter

31、mination in kNN algorithm better</p><p>　　and meanwhile has superior time efficiency. As for category efficiency, they are largely</p><p><b>　　the same.</b></p><p>　　Key

32、words: text classification; kNN; fast classification; reducing training data;</p><p>　　supplementing training data</p><p><b>　　III</b></p><p>　　重慶大學碩士學位論文</p><

33、;p><b>　　1 緒</b></p><p><b>　　論</b></p><p><b>　　1 緒 論</b></p><p>　　1.1 論文的研究背景及選題的意義</p><p>　　隨著信息科技的發(fā)展，特別是自 20 世紀 90 年代后期以來，Intern

34、et 技術(shù)的迅</p><p>　　猛發(fā)展，我們的生活已進入了信息爆炸的時代。據(jù) 1998 年統(tǒng)計，世界上每年出版</p><p>　　的期刊就約有 156000 種，而且還在以每年 12000 種的速度遞增[1] 。美國國內(nèi)每年</p><p>　　就有近 140 萬種書刊出版，同時還在以平均每年 6 萬種的速度增加[2] 。Internet 上</p>

35、;<p>　　的信息增長更是驚人。據(jù) 1999 年統(tǒng)計，Internet 上約有 3.5 億個 web 頁面，每天增</p><p>　　加將近 100 萬個。另外，在日常生活中人們經(jīng)常接觸的信息絕大部分都是文本信</p><p>　　息。這些信息要么以印刷品的方式存在，要么以電子文檔的形式出現(xiàn)。而隨著因</p><p>　　特網(wǎng)的迅猛發(fā)展，電子文檔日

36、益成為文本信息存在的主流形式。</p><p>　　如何有效的組織和管理這些龐大而且還在不斷急劇膨脹的文本信息，并且能</p><p>　　夠根據(jù)用戶不同的需求，迅速、準確地從中返回所需信息是當前信息科技領(lǐng)域面</p><p>　　臨的一大挑戰(zhàn)。而文本分類技術(shù)，是能夠解決信息混亂、幫助用戶準確地定位所</p><p>　　需信息的關(guān)鍵技術(shù)。因

37、此，文本自動分類己成為目前備受關(guān)注的關(guān)鍵技術(shù)，有著</p><p>　　很大的使用價值。它同時也是以下領(lǐng)域的技術(shù)基礎(chǔ)，有著廣泛的應(yīng)用前景。</p><p><b>　?、佟⌒畔⑦^濾</b></p><p>　　隨著 Internet 的飛速發(fā)展，網(wǎng)絡(luò)已成為我們方便快捷地獲取信息的重要渠道。</p><p>　　但面對如此

38、龐大的海量信息，如何快速的獲取用戶感興趣的信息，同時避免帶來</p><p>　　反面信息成為我們的一大困擾。而信息過濾正是解決這一困擾的關(guān)鍵技術(shù)，信息</p><p>　　過濾技術(shù)本質(zhì)上就是一個兩分類問題，它把信息分為兩類：感興趣的信息和不感</p><p>　　興趣的信息。一方面把用戶感興趣的信息提取出來反饋給用戶，另一方面把用戶</p><

39、p>　　不感興趣的、反面的信息給過濾掉。</p><p><b>　?、凇∴]件分類</b></p><p>　　當用戶特別是政府部門收到大量郵件時，就需要對郵件進行分類，以確定把</p><p>　　郵件分發(fā)給指定的人員去處理。例如美國白宮所使用的郵件分類系統(tǒng)能自動地把</p><p>　　總統(tǒng)收到的大量的 E-m

40、ail 分到指定的類別當中去，如政治、軍事、外交、經(jīng)濟、</p><p>　　環(huán)保等，從而交給適當?shù)娜藛T對郵件進行回復。</p><p><b>　?、邸∥谋緮?shù)據(jù)庫</b></p><p>　　隨著需求的發(fā)展，存儲、組織和查詢文本信息也不再是文本數(shù)據(jù)庫的全部功</p><p>　　能，而如何提供多層次的服務(wù)已成為文本數(shù)據(jù)

41、庫的重要功能，如文本挖掘。而文</p><p>　　本分類技術(shù)正是這些功能的重要基礎(chǔ)。</p><p>　　④ 電子會議和網(wǎng)絡(luò)論壇</p><p>　　電子會議就是所有參會者通過計算機網(wǎng)絡(luò)參與會議，它是一種新型的會議方</p><p><b>　　1</b></p><p>　　重慶大學碩士學位論

42、文</p><p><b>　　1 緒</b></p><p><b>　　論</b></p><p>　　式。為了調(diào)動參與者的積極性，參會者采用匿名的形式，以便于形成平等、活躍</p><p>　　的氣氛。然后由文本分類系統(tǒng)對電子會議上產(chǎn)生的大量意見和建議進行分類和組</p><

43、;p>　　織，以便確定進一步討論的主題。網(wǎng)絡(luò)論壇則是網(wǎng)絡(luò)上進行信息交流的一種重要</p><p>　　形式，對于用戶發(fā)表的大量信息，由文本分類系統(tǒng)進行分類和組織，以便于用戶</p><p><b>　　進行查找和瀏覽。</b></p><p><b>　?、荨?shù)字圖書館</b></p><p>

44、;　　數(shù)字圖書館已成為圖書館的發(fā)展趨勢，數(shù)字期刊所占的比重也越來越大。在</p><p>　　對圖書進行分類時，圖書管理員不可能對各個學科類別都非常了解，這就造成不</p><p>　　能對大量的圖書資料進行快速、準確的分類，而文本自動分類技術(shù)可以解決這一</p><p><b>　　問題。</b></p><p>&l

45、t;b>　?、蕖⌒畔⑼扑头?wù)</b></p><p>　　文本分類技術(shù)還可以應(yīng)用到主動的信息推送服務(wù)中。在這種模式里，用戶是</p><p>　　被動的，隨著信息的日益增多，信息服務(wù)系統(tǒng)可以主動地將最新的信息歸類，然</p><p>　　后根據(jù)用戶的需求和興趣推送給用戶。</p><p>　　因此，文本分類是一項基本而重要的

46、功能，它能夠很好地幫助用戶整理、獲</p><p>　　取信息，可以創(chuàng)造巨大的經(jīng)濟和社會效益。</p><p>　　k-最近鄰方法[3] [4] [5] （k-Nearest Neighbor, k-NN），作為一種基于統(tǒng)計的簡單、</p><p>　　有效、非參數(shù)的經(jīng)典分類方法，在文本分類中得到廣泛使用，并取得了很好的效</p><p>　

47、　果。其基本思想是在訓練樣本中找到測試樣本的 k 個最近鄰，然后根據(jù)這 k 個最</p><p>　　近鄰的類別來決定測試樣本的類別。k-最近鄰算法是一種基于需求的或懶惰的學習</p><p>　　方法，它在訓練階段只是簡單存放所有的訓練樣本，直到進入分類階段才建立分</p><p>　　類。這樣，與測試樣本比較的可能近鄰數(shù)量（即訓練樣本個數(shù)）較大時，會有很<

48、/p><p>　　大的計算代價。另外，訓練文本分布的不均勻也會造成分類準確率的下降。</p><p>　　因此，對訓練樣本集進行裁剪和選擇，將對提高 KNN 算法的分類效率和準確</p><p><b>　　率有重要的意義。</b></p><p>　　1.2 國內(nèi)外研究現(xiàn)狀綜述</p><p>　　

49、1.2.1 文本分類的研究現(xiàn)狀</p><p>　　國外文本自動分類的研究較早。美國 IBM 公司的 H.P.Luhn 首先于 20 世紀 50</p><p>　　年代末在這一領(lǐng)域進行了開創(chuàng)性的研究，他第一個提出將詞頻統(tǒng)計的思想運用到</p><p>　　文本分類中。Maron 于 1961 年發(fā)表了關(guān)于自動分類的第一篇論文[6] ，1962 年</p>

50、;<p>　　H.Borko 等人將因子分析法的思想引入到文本分類中。隨后，許多著名的科學家如</p><p>　　Sparck、Salton 等都在這一領(lǐng)域進行了富有成效的研究[7] 。文本分類的方法經(jīng)歷了</p><p>　　兩大階段：在 80 年代末之前都是基于知識工程的方法，即利用人為設(shè)定的規(guī)則來</p><p><b>　　2<

51、;/b></p><p>　　重慶大學碩士學位論文</p><p><b>　　1 緒</b></p><p><b>　　論</b></p><p>　　進行分類；而 90 年代以后，文本自動分類引入了統(tǒng)計方法和機器學習的方法[8] ，</p><p>　　并取得了豐

52、碩的成果，逐漸取代了知識工程方法。</p><p>　　國外的文本分類從理論研究到實際應(yīng)用的過程大體上可以分為三個階段：</p><p>　　1958 至 1964 年主要進行文本分類的可行性研究；1965 至 1974 年主要進行文本分</p><p>　　類的實驗研究；1975 至今一直在進行文本分類的實用化研究[9] 。</p><p>

53、;　　國內(nèi)的文本分類研究始于 20 世紀 80 年代初期，大體上也經(jīng)歷了三個階段：</p><p>　　可行性研究、輔助分類、自動分類。所采用的方法也比較單一，主要是結(jié)合中文</p><p>　　文本的特點采用相應(yīng)的策略，把英文文本分類的技術(shù)應(yīng)用到中文文本分類當中，</p><p>　　形成針對中文文本的分類系統(tǒng)。目前我國的自動分類系統(tǒng)大致可以分為兩類，即</

54、p><p>　　基于詞典方法的自動分類系統(tǒng)和基于專家系統(tǒng)方法的自動分類系統(tǒng)?？偟膩碚f，</p><p>　　我國的文本自動分類的發(fā)展階段和國外大致相同，但由于我國在該領(lǐng)域的研究起</p><p>　　步較晚，因此我們還有很多技術(shù)有待進一步研究。</p><p>　　在商業(yè)應(yīng)用方面，目前國外的已經(jīng)有 SAS 公司開發(fā)的數(shù)據(jù)挖掘集成軟件工具</

55、p><p>　　SAS/EM、SPSS 公司開發(fā)的 Clementine 等，可以應(yīng)用于文本分類方面的研究；國</p><p>　　內(nèi)由北京拓爾思信息技術(shù)有限公司開發(fā)的文本挖掘軟件 CKM，是國內(nèi)外第一個實</p><p>　　用化的中文文本挖掘軟件產(chǎn)品。另外，國內(nèi)的很多高等院校和研究機構(gòu)，也建立</p><p>　　了相關(guān)實驗室從事該領(lǐng)域的研究

56、，并且取得了很大的成就。如中科院開發(fā)的智多</p><p>　　星中文文本分類器、北京大學的天網(wǎng)等。目前，我國在中文文本分類領(lǐng)域已經(jīng)取</p><p>　　得了令人矚目的研究成果。</p><p>　　1.2.2 kNN 算法的研究現(xiàn)狀</p><p>　　kNN 方法作為一種簡單、有效、非參數(shù)的經(jīng)典分類方法，在文本分類中得到</p&g

57、t;<p>　　廣泛的應(yīng)用。但是這種方法計算量大，而且訓練樣本的分布不均勻會造成分類準</p><p><b>　　確率的下降。</b></p><p>　　目前主要通過兩種途徑來減小 k-最近鄰方法的計算量：一種途徑是設(shè)計快速</p><p>　　搜索算法，在盡量短的時間內(nèi)找到測試樣本的最近鄰[10] [11] ，另一種途徑是在

58、原來</p><p>　　的訓練樣本集中選取一些代表樣本作為新的訓練樣本集，或刪除原來的訓練樣本</p><p>　　集中的某些樣本，將剩下的樣本作為新的訓練樣本集，從而達到減小訓練樣本數(shù)</p><p><b>　　量的目的。</b></p><p>　　通過對訓練樣本進行選擇或裁減，使訓練樣本達到一個相對均勻的狀態(tài)，

59、一</p><p>　　方面可以降低文本分類器的計算量，另一方面還可以提高文本分類的精度[12] 。</p><p>　　1.2.3 樣本裁剪方法的研究現(xiàn)狀</p><p>　　文本分類方法主要可以分為基于統(tǒng)計的、基于連接的和基于規(guī)則的等三大類</p><p>　　方法。其中，目前使用較多的就是基于統(tǒng)計的分類方法，這類算法中最常見有 k-&l

60、t;/p><p>　　最近鄰、樸素貝葉斯、類中心向量、SVM 等。</p><p><b>　　3</b></p><p>　　重慶大學碩士學位論文</p><p><b>　　1 緒</b></p><p><b>　　論</b></p>&

61、lt;p>　　這種基于統(tǒng)計的分類算法，其分類器的建立一般是通過對訓練數(shù)據(jù)進行統(tǒng)計，</p><p>　　從而得到某種客觀規(guī)律，或者采用統(tǒng)計學中的某種定律來完成，因此這種分類算</p><p>　　法的訓練階段多為對訓練數(shù)據(jù)的某種統(tǒng)計和計算過程，而在分類階段，分類器根</p><p>　　據(jù)在訓練階段統(tǒng)計、計算出來的可以代表文本與類別之間關(guān)系的數(shù)據(jù)給出某種概&l

62、t;/p><p>　　率分類結(jié)果?；诮y(tǒng)計的方法實質(zhì)上就是一種定量推理的方法，定量是基于概率</p><p>　　的，因此具有不確定性，也必然會掩蓋小概率事件的發(fā)生。</p><p>　　由于基于統(tǒng)計的分類方法的統(tǒng)計結(jié)果是從訓練數(shù)據(jù)統(tǒng)計出來的，訓練數(shù)據(jù)是</p><p>　　否全面、均衡都會影響統(tǒng)計結(jié)果，因此訓練樣本集的選擇至關(guān)重要。</p

63、><p>　　國外從二十世紀六十年代開始研究如何主動的從訓練數(shù)據(jù)集中選擇出一部分</p><p>　　具有代表性的數(shù)據(jù)，然后僅使用這一部分數(shù)據(jù)作為訓練數(shù)據(jù)集。目前國外主要的</p><p>　　訓練樣本選擇方法有：Peter E Hart 于 1968 年提出的 Condensing 算法[13] 、Dennis L</p><p>　　Wils

64、on 于 1972 年提出的 Editing 算法[14] 、P Devijver 于 1982 年提出的 MultiEdit</p><p>　　算法[15] ，另外還有 Ludmila I Kuncheva 在 1995 年至 1997 年之間使用遺傳算法在</p><p>　　這方面進行的一些研究[16] [17] 。但這些方法存在兩方面的不足：一方面這些算法每</p>

65、<p>　　選擇一個樣本或者裁剪掉一個樣本，都要對選擇出來的數(shù)據(jù)集進行一次測試，反</p><p>　　復重復這一過程，直到選擇出來的數(shù)據(jù)集不再變化為止，因此，當原始訓練數(shù)據(jù)</p><p>　　集較大的時候，計算量會非常高；另一方面，這些算法沒有考慮到分類效果會受</p><p>　　訓練數(shù)據(jù)集分布狀態(tài)的影響。</p><p>

66、　　國內(nèi)對訓練樣本選擇方面的研究起步比較晚，也比較少。目前主要有復旦大</p><p>　　學的李榮陸博士于 2004 年提出的基于密度的 kNN 文本分類器訓練樣本裁剪方法，</p><p>　　徐義峰等人于 2007 年提出的一種新的基于密度的 k-最近鄰文本分類器訓練樣本約</p><p><b>　　減方法。</b></p>

67、<p>　　1.3 本文研究內(nèi)容</p><p>　　本文研究的內(nèi)容主要包括以下兩個部分：</p><p>　　①　分析基于密度的 kNN 分類器訓練樣本裁減方法的不足并提出改進：</p><p>　　1）基于密度的 kNN 分類器訓練樣本裁減方法中，通過對高密度區(qū)的樣本進</p><p>　　行裁減，使訓練樣本集在每個以 e

68、為半徑的圓形區(qū)域內(nèi)的樣本數(shù)相等，從而使整個</p><p>　　樣本區(qū)域達到一個相對均勻的狀態(tài)。在對某一個以 e 為半徑的區(qū)域內(nèi)的樣本裁減</p><p>　　時，優(yōu)先裁減分布最密集的樣本，但這樣的樣本并不一定是信息增益最小的樣本。</p><p>　　針對這種不足，本論文考慮在對高密度區(qū)的訓練樣本裁減時優(yōu)先裁減信息增益最</p><p>&

69、lt;b>　　低的樣本。</b></p><p>　　2）基于密度的 kNN 分類器訓練樣本裁減方法沒有實現(xiàn)對低密度區(qū)的樣本進</p><p>　　行補充，所以通過該方法裁減后的訓練樣本集仍存在一些比平均密度低的低密度</p><p><b>　　4</b></p><p>　　重慶大學碩士學位論文&l

70、t;/p><p><b>　　1 緒</b></p><p><b>　　論</b></p><p>　　區(qū)。針對這種不足，本論文實現(xiàn)一種對低密度區(qū)的訓練樣本進行補充的算法。</p><p>　?、凇⊙芯?kNN 算法中最佳 k 值的確定：</p><p>　　kNN 算法中的最

71、佳 k 值一般都是通過經(jīng)驗確定的，本論文通過研究最佳 k 值</p><p>　　與基于密度的 kNN 分類器訓練樣本裁減方法中的參數(shù) e 之間的關(guān)系，最終為最佳</p><p>　　k 值的確定提供一定的依據(jù)。</p><p>　　1.4 本文章節(jié)安排</p><p>　　本文共分五章，文章結(jié)構(gòu)及各章內(nèi)容安排如下：</p>&

72、lt;p>　　第一章：緒論。主要介紹本課題的研究背景及研究意義，分析文本分類、kNN</p><p>　　算法以及訓練樣本裁剪算法的國內(nèi)外研究現(xiàn)狀及存在的問題。并闡述本文的主要</p><p>　　研究內(nèi)容，最后給出本文的章節(jié)安排。</p><p>　　第二章：文本分類技術(shù)。主要介紹文本分類的相關(guān)技術(shù)，包括文本預處理、</p><p>

73、　　文本的表示、文本特征向量的提取、特征向量的加權(quán)、文本分類的經(jīng)典算法 kNN、</p><p>　　訓練樣本裁剪算法以及文本分類效果評估等。</p><p>　　第三章：裁剪算法的改進。對訓練樣本裁剪算法進行分析，針對其不足做出</p><p>　　改進，最后在兩個語料庫上進行實驗，對改進前后的算法進行對比，并分析實驗</p><p>&l

74、t;b>　　結(jié)果。</b></p><p>　　第四章：kNN 算法的改進。對 kNN 算法進行分析，針對其參數(shù) k 的設(shè)置只能</p><p>　　根據(jù)實驗結(jié)果進行調(diào)整的不足，提出一種改進的 kNN 算法，最后進行實驗對比，</p><p><b>　　并分析實驗結(jié)果。</b></p><p>　　第

75、五章：論文總結(jié)與展望。總結(jié)全文的研究內(nèi)容，并對下一步的研究工作和</p><p><b>　　研究方向進行討論。</b></p><p><b>　　5</b></p><p>　　重慶大學碩士學位論文</p><p><b>　　2 文本分類技術(shù)</b></p>

76、<p><b>　　2 文本分類技術(shù)</b></p><p>　　2.1 文本分類的一般過程</p><p>　　文本是一系列語句串聯(lián)而成的連貫序列，它可能只是一個單句，但一般來說</p><p>　　是由一系列的句子連貫而成。我們在日常生活中所看到的具有一定意義的文字段</p><p>　　落都可以稱之為文

77、本。文本自動分類就是利用計算機按照一定的分類體系或者規(guī)</p><p>　　則將待分類文本標記為預先設(shè)定好的某個或某些類別[18] 。文本自動分類的過程可</p><p>　　以用數(shù)學公式表示如下：</p><p>　　f : T?→ C 其中：T?? (D1, D2,L , Dn ) C?? (C1, C2 ,L Cm )</p><p>

78、　　其中 T 是待分類文本的集合，它可以是無限集；C 是預先設(shè)定好的所有類別</p><p>　　的集合，它必須是有限集。</p><p>　　通過數(shù)學公式可以看出，文本自動分類過程就是一個函數(shù)映射過程，由于一</p><p>　　個文本的內(nèi)容可以是跨領(lǐng)域的或者是多個領(lǐng)域的結(jié)合，因此它可以歸屬于多個類</p><p>　　別，相應(yīng)的，該函數(shù)映

79、射可以是一對一的映射也可以是一對多的映射。數(shù)學公式</p><p>　　中的函數(shù) f 對應(yīng)于文本分類的分類算法，這也是文本自動分類系統(tǒng)中的核心內(nèi)容，</p><p>　　即由分類算法從訓練數(shù)據(jù)集中總結(jié)出一定的規(guī)律，從而建立分類規(guī)則，也就是映</p><p>　　射函數(shù) f。對于待分類文本，文本自動分類系統(tǒng)就根據(jù)映射函數(shù) f 將其映射到某個</p>&l

80、t;p>　　或某幾個類別當中去。</p><p>　　文本自動分類的過程一般包括：文本的預處理、文本的表示、特征處理、構(gòu)</p><p>　　建分類器、對文本進行分類、對 分類結(jié)果進行評價，其主要功能模塊如圖 2.1 所示：</p><p><b>　　6</b></p><p>　　重慶大學碩士學位論文</

81、p><p><b>　　2 文本分類技術(shù)</b></p><p>　　圖 2.1 文本分類系統(tǒng)</p><p>　　Fig.2.1 Text classification system</p><p>　　各個模塊的主要功能如下：</p><p>　?、佟∥谋绢A處理：對原始語料集進行一系列的處理，如去

82、除停用詞、切分詞等，</p><p>　　將其轉(zhuǎn)化為可以由計算機處理的數(shù)據(jù)；</p><p>　?、凇∥谋灸Ｐ捅硎荆河锰囟ǖ臄?shù)學模型如向量空間模型來表示文本；</p><p>　?、邸√卣魈幚恚簩⑽谋镜奶卣魈崛〕鰜?，選出其中具有代表性的特征來表示文</p><p>　　本，并計算各個特征的權(quán)重；</p><p>　?、?/p>

83、　分類：首先選擇特定的分類算法，然后用訓練數(shù)據(jù)集對其訓練，得到分類</p><p>　　器模型，最后對待分類文本進行分類；</p><p>　?、荨⌒Чu價：采用一定的性能指標對分類結(jié)果進行評價，并根據(jù)分析結(jié)果對</p><p>　　分類器進行相應(yīng)的調(diào)整。</p><p>　　2.2 文本預處理與文本表示</p><p&g

84、t;　　2.2.1 文本預處理</p><p>　　文本預處理就是將人類可以理解的文本轉(zhuǎn)化為計算機可以理解并處理的數(shù)</p><p><b>　　7</b></p><p>　　重慶大學碩士學位論文</p><p><b>　　2 文本分類技術(shù)</b></p><p>　　據(jù)

85、，這也是文本自動分類的前提。另外，文本預處理的內(nèi)容以及側(cè)重點也應(yīng)隨不</p><p>　　同的情況如不同的分類對象、分類器等而有所不同。對于英文文本進行預處理，</p><p>　　一般只需要過濾停用詞、過濾非法字符等，而對于中文文本，由于中文文本中詞</p><p>　　與詞之間沒有天然的分隔符，就必須要進行切分詞。</p><p><

86、;b>　?、?過濾停用詞</b></p><p>　　將停用詞從原始文本中去除掉的過程即稱為過濾停用詞。停用詞主要是指那</p><p>　　些出現(xiàn)頻率很高但對文本分類沒有太大貢獻的單詞。各種語言中都存在很多這樣</p><p>　　的停用詞，例如，中文中的“的”、“是”、“啊”、“而”等語氣詞、助詞等，它們幾乎</p><p&

87、gt;　　在每個中文本文中都會出現(xiàn)，它們的存在僅僅是因為語法的需要，并沒有什么實</p><p>　　際含義，因此，它們幾乎不代表對應(yīng)文本的任何內(nèi)容。如果將這些詞也作為文本</p><p>　　的特征提取出來，只會增加特征空間的高維性，甚至影響分類精度。</p><p><b>　?、?過濾非法字符</b></p><p&g

88、t;　　所謂非法字符就是對文本分類無用的字符，它跟停用表的性質(zhì)有些相似，但</p><p>　　停用詞具有通用性，而非法字符一般來講隨分類方法的不同而有所不同。所以，</p><p>　　非法字符跟停用詞一樣，也要被處理掉，以提高分類精度。</p><p>　　上面這兩種文本分類技術(shù)在所有的文本分類系統(tǒng)中都會用到，目的就是處理</p><p>

89、;　　掉那些沒有的詞或字符。而下面要講到的兩種技術(shù)在特定的文本分類中才會用到，</p><p>　　中文分詞技術(shù)是中文文本分類中特有的，web 網(wǎng)頁預處理是針對 web 文本分類特</p><p><b>　　有的。</b></p><p><b>　?、?中文分詞技術(shù)</b></p><p>　　

90、中文分詞技術(shù)，顧名思義就是對中文文本進行切分詞，即把詞語從文本句子</p><p>　　中提取出來，也是中文文本預處理中最關(guān)鍵的一種技術(shù)。中文切分詞的難度較大，</p><p>　　因為中文不像英文那樣，單詞與單詞之間有空格加以區(qū)分，而必須根據(jù)詞語之間</p><p>　　的意思、概念來區(qū)分。目前中文分詞技術(shù)有三類：基于字符串匹配的分詞方法、</p>

91、<p>　　基于理解的分詞方法和基于統(tǒng)計的分詞方法。其中最常用的基于字符串匹配的分</p><p>　　詞方法又有三種：正向最大匹配法 (由左到右的方向)；逆向最大匹配法 (由右到左</p><p>　　的方向)；最少切分(使每一句中切出的詞數(shù)最小)。黃[19] 給出的中文分詞方法就是</p><p>　　基于字符串的匹配方法中的最大匹配法?；诶斫獾姆衷~

92、方法是通過讓計算機模</p><p>　　擬人對句子的理解，來達到識別詞的效果，其基本思想就是在分詞的同時進行句</p><p>　　法、語義分析，利用句法信息和語義信息來處理歧義現(xiàn)象。它通常包括三個部分：</p><p>　　分詞子系統(tǒng)、句法語義子系統(tǒng)、總控部分。最后一種方法則是基于統(tǒng)計的方法：</p><p>　　從形式上看，詞是穩(wěn)定的字

93、的組合，因此在上下文中，相鄰的字同時出現(xiàn)的次數(shù)</p><p>　　越多，就越有可能構(gòu)成一個詞。因此字與字相鄰共現(xiàn)的頻率或概率能夠較好的反</p><p><b>　　映成詞的可信度。</b></p><p><b>　　8</b></p><p>　　重慶大學碩士學位論文</p>&

94、lt;p><b>　　2 文本分類技術(shù)</b></p><p>　　到底哪種分詞算法的準確度更高，目前并無定論。對于任何一個成熟的分詞</p><p>　　系統(tǒng)來說，不可能單獨依靠某一種算法來實現(xiàn)，都需要綜合不同的算法。</p><p>　?、?web 網(wǎng)頁預處理：</p><p>　　web 已經(jīng)成為人類獲取信息

95、和得到服務(wù)主要方式之一。它與一般的文本文檔有</p><p>　　所不同，web 主要由半結(jié)構(gòu)化的 HTML 語言組成，而 HTML 語言中不同元素所包</p><p>　　含的信息量也有所不同，因此如何根據(jù) HTML 語言的特點最大量的提取出 web 文</p><p>　　本的有用信息是 web 文本分類的關(guān)鍵。</p><p>　　We

96、b 文本預處理的方法主要有以下幾類：1） 簡單的把 web 文本中的所有文</p><p>　　字信息全部作為有用信息，這就會導致包含大量的噪音信息而降低文本分類的精</p><p>　　度；或者把所有的文字信息作為無用信息而導致丟掉了大量的有用信息；2） 將</p><p>　　HTML 語言中某些元素的信息提取出來，如 Title、Key、超鏈接等，過濾掉其他部

97、</p><p>　　分的信息。這種方法能過濾掉大部分的無用信息，同時提取到大部分的有用信息，</p><p>　　能夠取得較好的效果。3） 人為的設(shè)定一些相應(yīng)的規(guī)則，然后根據(jù)這些規(guī)則決定</p><p>　　提取哪些信息。這樣可以根據(jù)不同的情況設(shè)定不同的規(guī)則，靈活性較大，但通用</p><p><b>　　性不強。</b&g

98、t;</p><p>　　2.2.2 文本表示</p><p>　　如何將文本表示為計算機能夠識別的模型是文本分類系統(tǒng)首先要解決的問</p><p>　　題。目前大部分文本分類系統(tǒng)都是通過此條匹配和計數(shù)將文本中的大部分信息提</p><p>　　取出來，常用的文本表示模型有三種：布爾模型，概率模型，向量空間模型。</p><

99、;p><b>　?、?布爾模型</b></p><p>　　布爾模型是最簡單的文本表示模型，就是采用布爾表達式表示文本。布爾模</p><p>　　型在傳統(tǒng)的信息檢索系統(tǒng)中有著廣泛的應(yīng)用，它也是其它表示模型的基礎(chǔ)。它把</p><p>　　每一個文本表示成一個向量，向量的維就是文本的特征集合，每一維的權(quán)重要么</p><

100、;p>　　為 0，要么為 1。當某一特征出現(xiàn)時，它的權(quán)重即為 1，否則為 0[20] 。</p><p><b>　?、?概率模型</b></p><p>　　信息檢索的概率模型考慮詞與詞之間的相關(guān)性，把文本集中的文本分為兩類：</p><p>　　相關(guān)文本和無關(guān)文本。它根據(jù)數(shù)學理論中的概率論原理，通過特定的計算方式計</p>

101、<p>　　算出每個詞出現(xiàn)在相關(guān)文本和無關(guān)文本中的概率，然后根據(jù)各個詞的概率計算出</p><p>　　文本間的概率，系統(tǒng)再以此做出決策。概率模型能夠解決文本信息相關(guān)性判斷的</p><p>　　不確定性和查詢信息表示的模糊性問題。</p><p>　　概率模型中的概率公式為 P( R | D, q) ，其中 P 表示文本 D 與用戶查詢 q 相關(guān)的&

102、lt;/p><p>　　概率。另外，用 R′ 來表示文本 D 與用戶查詢 q 不相關(guān)的概率，這樣，就有</p><p>　　P( R | D , q)?? P (R′ | D, q)?? 1，即用二值形式判斷相關(guān)性[24] 。</p><p>　　文本用特征項來表示，即 d i?? (t1 ,t2 ,L , tn) ，在概率模型中，用特征向量來表示，</p>

103、<p><b>　　9</b></p><p>　　重慶大學碩士學位論文</p><p><b>　　2 文本分類技術(shù)</b></p><p>　　即 d i?? (wi1 ,wi 2,L ,win )，查詢串 q 也用向量來表示， q?? (wq1 ,wq 2 ,L , wqm ) 。在概率</p&g

104、t;<p>　　模型中，特征項的權(quán)重都是二值的，即 wij?∈{0,1} ， wqj?∈{0,1} ，權(quán)重為 1 表示該特</p><p>　　征項在該文本中出現(xiàn)了，0 則表示該特征項沒有出現(xiàn)。</p><p>　　在信息檢索中，由于參數(shù)不好估計，直接計算 P 就比較困難，所以一般采用</p><p>　　計算 P( R | t , qk ) 來代替計

105、算 P( R | d , qk )，即只根據(jù)文本中出現(xiàn)的特征項來計算該文</p><p>　　本的相關(guān)概率。這樣，兩篇不同的文本如果包含的特征項相同，則他們的相關(guān)概</p><p>　　率是相同的。對所有的文本計算其相關(guān)概率 P( R | t , qk ) 后，按照 P 對文本進行排序，</p><p>　　這就相當于將所有文本按照特征向量排序。其中文本 d 的概率

106、相關(guān)性的計算公式</p><p><b>　　為</b></p><p>　　P( R | D , q)???∑ di?? lg</p><p>　　pi (1?? qi )</p><p>　　qi (1?? pi )</p><p><b>　　(2.1)</b><

107、/p><p>　　其中， pi?? P (ti?? 1| R, q), qi?? P(ti?? 1| R′, q) 。</p><p>　　參數(shù) pi，qi 主要是通過相關(guān)反饋進行估計，簡單的方法如：</p><p>　　pi?? ri / r , qi?? (ni?? ri ) / (n?? r)</p><p><b>　　(2.2

108、)</b></p><p>　　其中，n 為反饋文本集所含文本的總數(shù)，r 為與用戶查詢相關(guān)的文本數(shù)，ni 為</p><p>　　特征 ti 出現(xiàn)的樣本個數(shù)，ri 為特征 ti 出現(xiàn)且與用戶查詢相關(guān)的文本個數(shù)。概率模型</p><p>　　就是采用相關(guān)反饋的方法，從兩個初始的概率開始，不斷調(diào)整概率估計值，直到</p><p>　　

109、得到一個滿意的概率排序。</p><p>　　概率模型的優(yōu)點是采用嚴格的數(shù)學理論為依據(jù)，為人們提供了一種數(shù)學理論</p><p>　　基礎(chǔ)來進行匹配，采用相關(guān)性反饋原理，可開發(fā)出理論上更為堅實的方法。缺點</p><p>　　是增加了存儲和計算資源的開銷，且參數(shù)估計難度較大，另外，由于文本向量中</p><p>　　的權(quán)重只采用簡單的二值形式

110、，丟失了一部分有用的信息。</p><p><b>　　③ 向量空間模型</b></p><p>　　向量空間模型是在 1968 年由 Salton[21]</p><p><b>　　[22]</b></p><p>　　等人提出，這也是目前在信息檢索</p><p>　　

111、領(lǐng)域表示文本的經(jīng)典模型。向量空間模型一般使用詞作為特征項，使用這些特征</p><p>　　項以及其對應(yīng)的權(quán)重來表示文本。這樣，每個文本就被映射為由特征項組成的向</p><p><b>　　量空間中的一個點。</b></p><p>　　該模型的建立主要涉及兩個方面：一方面是提取特征詞，文本的內(nèi)容由前面</p><p>

112、;　　提到的詞或詞組等基本單位組成。對于英文可以直接提取單詞，對于中文可以通</p><p>　　過切分詞等技術(shù)提取詞。提取到的每一個特征項就作為向量空間中的一維。另一</p><p>　　方面，就是針對每一個文本為它相應(yīng)的特征項賦予不同的權(quán)重。權(quán)重表示該特征</p><p>　　項對于相應(yīng)文本的重要程度，其計算方式也有多種，目前較常用的技術(shù)包括以下</p&g

113、t;<p>　　兩種，布爾權(quán)重和通過 TFIDF 計算權(quán)重。布爾權(quán)重考慮的方式相對簡單，如果特</p><p>　　征項在文本中不出現(xiàn)則權(quán)重為 0，相反則為 1。布爾權(quán)重無法體現(xiàn)出詞條的重要程</p><p><b>　　10</b></p><p>　　重慶大學碩士學位論文</p><p><b&g

114、t;　　2 文本分類技術(shù)</b></p><p>　　度。TFIDF 不但要考慮特征項在文本中出現(xiàn)的頻度，同時還考慮到了它在整個語</p><p>　　料中的分布情況，因此被認為是較好的特征項權(quán)重計算公式。其中 TF 表示了特征</p><p>　　項在文本中出現(xiàn)的頻率，而 IDF 則表示特征項在整個語料集中的分布情況。TF 越</p>&

115、lt;p>　　大，表示該特征在這個文本中的重要程度越高，而 IDF 越大則表示它在整個文本</p><p><b>　　中的分布相對集中。</b></p><p>　　由此就得到了由特征項和特征項權(quán)重組成的向量空間模型[23] 。</p><p><b>　　2.3 特征處理</b></p><p

116、>　　通過對訓練樣本進行去除停用詞、切分詞等預處理，得到一個有詞或詞組構(gòu)</p><p>　　成的初始特征集。一般情況下這個特征集中的特征項數(shù)目都會很大，即使一個文</p><p>　　本數(shù)很少的訓練集，經(jīng)過預處理后也會得到數(shù)萬個特征項。特征項過多一方面會</p><p>　　造成計算量過大，制約分類效率；另一方面還會降低分類的精度，這是因為通過</p&

117、gt;<p>　　簡單預處理提取出來的特征項，其中一部分在文本中出現(xiàn)的頻率很低，這些特征</p><p>　　項對代表文本內(nèi)容的作用很小，甚至有可能成為分類的噪音數(shù)據(jù)，通常稱這些詞</p><p>　　為低頻弱關(guān)聯(lián)詞；而有些特征項在文本中出現(xiàn)的次數(shù)較多，它們蘊含了大量和類</p><p>　　別相關(guān)的信息，稱為高頻強關(guān)聯(lián)詞。特征處理就是要對通過預處理得

118、到的初始特</p><p>　　征集進行特征選擇和提取，只將其中有用的部分作為分類器學習的特征集，并通</p><p>　　過一定的計算方式賦予各個特征項不同的權(quán)重，來表示它對文本的重要程度[25] 。</p><p>　　2.3.1 特征提取方法</p><p>　　文本分類中存在兩大問題：特征空間的高維性和文本表示向量的稀疏性。特<

119、/p><p>　　征空間的高維性是由構(gòu)成文本的詞匯量相當大導致的，而文本表示向量的稀疏性</p><p>　　是因為某些詞只在少量的文本中出現(xiàn)，大部分文本在這個詞對應(yīng)的維上就為空值</p><p>　　了。特征空間向量的這兩大特性一方面會導致計算開銷過大，從而使很多分類算</p><p>　　法難以處理，另一方面也會造成分類結(jié)果精度的降低。所以，

120、我們應(yīng)該盡可能準</p><p>　　確、盡可能少的選擇那些與文本主題密切相關(guān)的特征集來參與分類器的訓練和分</p><p>　　類，這也就是所謂的特征降維。在進行有效的特征降維后，不僅可以大大降低分</p><p>　　類過程中的計算量提高分類器的分類效率，同時還可以提高分類器的分類精度。</p><p>　　因此如何在不降低分類器的分類精

121、度甚至提高分類精度的前提下尋求一種自</p><p>　　動、高效的特征抽取方法，成為文本分類中急需解決的重要問題。對于中文文本</p><p>　　分類，由于其自身的很多特性，如中文存在大量近義詞、多義詞以及中文詞匯量</p><p>　　相當大導致的特征空間的高維性和文本向量的稀疏性更加嚴重，所有這些決定了</p><p>　　中文文本特

122、征抽取問題在很大程度上不同于英文文本，在英文文本分類中運用得</p><p>　　很好的特征抽取方法不一定能直接應(yīng)用于中文文本。目前適合于中文文本分類的</p><p>　　特征抽取方法主要有以下幾種：最簡單的停用詞移除、互信息 MI、信息增益 IG</p><p><b>　　11</b></p><p>　　重慶大學