研究報(bào)告大數(shù)據(jù)技術(shù)報(bào)告

1、-. z- - - .總結(jié)資料研究生大數(shù)據(jù)技術(shù)報(bào)告 題 目： 第27組-基于KNN文本分類分析學(xué) 號(hào)姓 名 專 業(yè) 計(jì)算機(jī)技術(shù) 指 導(dǎo) 教 師 院系、所 計(jì)算機(jī)學(xué)院 -. z填表考前須知本表適用于攻讀碩士學(xué)位研究生選題報(bào)告、學(xué)術(shù)報(bào)告，攻讀博士學(xué)位研究生文獻(xiàn)綜述、選題報(bào)告、論文中期進(jìn)展報(bào)告、學(xué)術(shù)報(bào)告等。以上各報(bào)告容及要求由相關(guān)院系、所做具體要求。以上各報(bào)告均須存入研究生個(gè)人學(xué)籍檔案。本表填寫要求文句通順、容明確、字跡工整。-. z研究背景研究背景以及現(xiàn)實(shí)意義隨著Internet的迅速開展，現(xiàn)在處于一個(gè)信息爆炸的時(shí)代，人們可以在網(wǎng)絡(luò)上獲取更多的信息，如文本、圖片、聲音、視頻等，尤其是文本最為常用和

2、重要。因此文本的分類在發(fā)現(xiàn)有價(jià)值的信息中就顯得格外重要。文本分類技術(shù)的產(chǎn)生也就應(yīng)運(yùn)而生，與日常生活嚴(yán)密聯(lián)系，就有較高的實(shí)用價(jià)值1。文本分類的目的是對(duì)文本進(jìn)展合理管理，使得文本能分門別類，方便用戶獲取有用的信息。一般可以分為人工2和自動(dòng)分類。人工分類是早期的做法，這種方式有較好的效勞質(zhì)量和分類精度，但是耗時(shí)、耗力、效率低、費(fèi)用高。而隨著信息量以驚人的速度增長(zhǎng)，這種方式就顯得很困難，所以需要一種自動(dòng)分類的方式來代替人工分類；自動(dòng)分類節(jié)省了人力財(cái)力，提高準(zhǔn)確力和速度。國外研究現(xiàn)狀3對(duì)文本分類進(jìn)展了開創(chuàng)性的研究將詞頻統(tǒng)計(jì)思想應(yīng)用于文本分類，1960年，Maro發(fā)表了關(guān)于自動(dòng)分類的第一篇論文，隨后，K.

3、Spark，GSalton，R.M.Needham，M.E.Lesk以及K.S.Jones等學(xué)者在這一領(lǐng)域進(jìn)展了卓有成效的研究。目前，文本分類已經(jīng)廣泛的應(yīng)用于電子分類、電子會(huì)議、數(shù)字圖書館、搜索引擎、信息檢索等方面4。至今，國外文本分類技術(shù)在以下一些方面取得了不錯(cuò)的研究成果。(1)向量空間模型5的研究日益成熟Salton等人在60年代末提出的向量空間模型在文本分類、自動(dòng)索引、信息檢索等領(lǐng)域得到廣泛的應(yīng)用，已成為最簡(jiǎn)便高效的文本表示模型之一。(2)特征項(xiàng)的選擇進(jìn)展了較深入的研究對(duì)于英法德等語種，文本可以由單詞、單詞簇、短語、短語簇或其他特征項(xiàng)進(jìn)展表示。國對(duì)于文本分類的研究起步比擬晚，1981年，

4、侯漢清教授對(duì)于計(jì)算機(jī)在文本分類工作中的應(yīng)用作了探討，并介紹了國外計(jì)算機(jī)管理分類表、計(jì)算機(jī)分類檢索、計(jì)算機(jī)自動(dòng)分類、計(jì)算機(jī)編制分類表等方面的概況。此后，我國陸續(xù)研究出一批計(jì)算機(jī)輔助分類系統(tǒng)和自動(dòng)分類系統(tǒng)。但是中英文之間存在較大差異，國的研究無法直接參照國外的研究成果，所以中文文本分類技術(shù)還存在這一些問題。(1)缺少統(tǒng)一的中文語料庫不存在標(biāo)準(zhǔn)的用于文本分類的中文語料庫，各個(gè)學(xué)者分頭收集自己的訓(xùn)練文本集，并在此根底上開展研究，因此，系統(tǒng)的性能可比性不強(qiáng)。同時(shí)，由于財(cái)力人力有限，中文語料庫的規(guī)模普遍不大。(2)向量空間模型的研究還不十分成熟國的學(xué)者，例如，吳立德和黃萱菁也提出了如何選擇特征項(xiàng)的問題，他

5、們提出可以使用字、詞、概念作為特征項(xiàng)來構(gòu)成向量空間模型，并對(duì)以此為根底的文本分類系統(tǒng)進(jìn)展了初步的性能比擬。但是，在這方面的研究6還沒有深入的開展，尤其是對(duì)于概念的定義不清晰，沒有全面的比擬和測(cè)試系統(tǒng)。另外，在特征項(xiàng)抽取算法方面也缺少深入的研究。(3)文本分類算法的研究不十分完整每個(gè)分類器通常只實(shí)現(xiàn)一種分類算法，然后進(jìn)展測(cè)試和分析，缺少完整的多種分類算法性能的比擬和測(cè)試。-. z解決方案KNN文本分類算法KNN7算法最初由Cover和Hart于1968年提出8，是一個(gè)理論上比擬成熟的方法。該算法的根本思想是:根據(jù)傳統(tǒng)的向量空間模型，文本容被形式化為特征空間中的加權(quán)特征向量，即D=D(T1，W1;

6、T2，W2;Tn，Wn)。對(duì)于一個(gè)測(cè)試文本，計(jì)算它與訓(xùn)練樣本集中每個(gè)文本的相似度，找出K個(gè)最相似的文本，根據(jù)加權(quán)距離和判斷測(cè)試文本所屬的類別。具體算法步驟如下:(1)對(duì)于一個(gè)測(cè)試文本，根據(jù)特征詞形成測(cè)試文本向量。(2)計(jì)算該測(cè)試文本與訓(xùn)練集中每個(gè)文本的文本相似度，計(jì)算公式為:式中:di為測(cè)試文本的特征向量，dj為第j類的中心向量;M為特征向量的維數(shù);Wk為向量的第k維。(3)按照文本相似度，在訓(xùn)練文本集中選出與測(cè)試文本最相似的k個(gè)文本。(4)在測(cè)試文本的k個(gè)近鄰中，依次計(jì)算每類的權(quán)重，計(jì)算公式如下:式中:*為測(cè)試文本的特征向量;Sim(*，di)為相似度計(jì)算公式;b為閾值，有待于優(yōu)化選擇;而y

7、(di，Cj)的取值為1或0，如果di屬于Cj，則函數(shù)值為1，否則為0。(5)比擬類的權(quán)重，將文本分到權(quán)重最大的那個(gè)類別中。KNN方法基于類比學(xué)習(xí)，是一種非參數(shù)的分類技術(shù)，在基于統(tǒng)計(jì)的模式識(shí)別中非常有效，對(duì)于未知和非正態(tài)分布可以取得較高的分類準(zhǔn)確率，具有魯棒性、概念清晰等優(yōu)點(diǎn)。但在文本分類中，KNN方法也存在缺乏，如KNN算法是懶散的分類算法，各維權(quán)值一樣，使得特征向量之間的距離計(jì)算不夠準(zhǔn)確，影響分類精度。針對(duì)這些缺乏，分別提出了相應(yīng)的改良算法。下面將詳細(xì)介紹。-. z改良的KNN文本分類算法提高分類效率的改良算法KNN算法的主要缺點(diǎn)是，當(dāng)訓(xùn)練樣本數(shù)量很大時(shí)將導(dǎo)致很高的計(jì)算開銷。KNN算法是懶

8、散的分類算法，對(duì)于分類所需的計(jì)算都推遲到分類時(shí)才進(jìn)展，在其分類器中存儲(chǔ)有大量的樣本向量，在未知類別樣本需要分類時(shí)，再計(jì)算和所有存儲(chǔ)樣本的距離，對(duì)于高維文本向量或樣本集規(guī)模較大的情況，其時(shí)間和空間復(fù)雜度較高。針對(duì)這個(gè)缺點(diǎn)，提出了一些改良算法:如基于FuzzyART的K-最近鄰分類改良算法，該算法用模糊自適應(yīng)共振理論(FuzzyART)對(duì)K-最近鄰的訓(xùn)練樣本集進(jìn)展?jié)饪s，以改善K-最近鄰的計(jì)算速度。該算法首先用FuzzyART將訓(xùn)練樣本集中的每一類樣本進(jìn)展聚類，減少了訓(xùn)練樣本集的數(shù)據(jù)量，提高了算法的計(jì)算速度，保持了預(yù)測(cè)精度，從而使該算法適用于海量數(shù)據(jù)集的情況。試驗(yàn)說明，該算法適用于對(duì)復(fù)雜而數(shù)據(jù)量較大

9、的數(shù)據(jù)庫進(jìn)展分類。提出了一種基于K-近鄰方法的漸進(jìn)式中文文本分類技術(shù)，利用文本的標(biāo)題、摘要、關(guān)鍵詞、重點(diǎn)段落進(jìn)展?jié)u進(jìn)式的分類處理。這樣，不用分析全文就能將局部待分類文本成功分類，從而提高了文本分類的效率。試驗(yàn)結(jié)果說明，該方法在保證分類準(zhǔn)確率的根底上能夠有效地提高分類效率。對(duì)于減少KNN計(jì)算量的優(yōu)化而做的研究主要是如何從原始數(shù)據(jù)集中選取代表實(shí)例集，大局部?jī)H對(duì)低維的情況適用，而且在代表實(shí)例集每增加或刪除一個(gè)代表實(shí)例時(shí)，都要對(duì)樣本進(jìn)展一次測(cè)試，工作量大，為此，根據(jù)測(cè)試文檔在各個(gè)樣本類中的分布情況提出了基于KNN分類的兩個(gè)有助于減少大量計(jì)算的重要算法:排類算法和歸類算法。從而構(gòu)建了一個(gè)基于KNN的快速

10、文檔分類方法。理論與實(shí)驗(yàn)證明，這種方法可以在不影響原有準(zhǔn)確率的條件下，提高文檔的分類速度?；谀Ｊ骄酆虾吞卣鹘稻S的改良算法在計(jì)算相似度時(shí)，不考慮特征詞間的關(guān)聯(lián)關(guān)系。針對(duì)這一缺乏進(jìn)展的改良有:主要考慮文檔間特征詞屬性關(guān)聯(lián)與共現(xiàn)對(duì)相似度的作用，用一個(gè)匹配系數(shù)調(diào)整兩文檔間的距離。它實(shí)質(zhì)上是強(qiáng)化了文本中語義鏈屬性因子的作用，修正了次要因素的噪聲影響，使文本分類結(jié)果更加理想，已有的測(cè)試結(jié)果證明了這一點(diǎn)，尤其在測(cè)試文本與訓(xùn)練文本集中的*些文本直觀上較相似時(shí)，結(jié)果更佳。通過分析特征詞對(duì)分類奉獻(xiàn)的大小，提出了一種應(yīng)用向量聚合技術(shù)的KNN文本分類方法，很好的解決了關(guān)聯(lián)特征詞的提取問題，該方法根據(jù)每個(gè)特征詞的CH

11、I分布曲線來確定它們?cè)诜诸愔械姆瞰I(xiàn)，應(yīng)用向量聚合技術(shù)很好地解決了關(guān)聯(lián)特征詞的提取問題。其特點(diǎn)在于:聚合文本向量中相關(guān)聯(lián)的特征詞作為特征項(xiàng)，從而取代傳統(tǒng)方法中一個(gè)特征詞對(duì)應(yīng)向量一維的做法，這樣不但縮減了向量的維數(shù)，而且加強(qiáng)了特征項(xiàng)對(duì)文本分類的奉獻(xiàn)。試驗(yàn)說明，該方法明顯提高了分類的準(zhǔn)確率和召回率。基于特征加權(quán)的改良算法KNN方法是建立在VSM模型上的，其樣本距離的測(cè)度使用歐式距離或余弦距離，各維權(quán)值一樣，也就是以為各維對(duì)于分類的奉獻(xiàn)是一樣的，這是不符合實(shí)際情況的，同等的權(quán)重使得特征向量之間距離或夾角余弦的計(jì)算不夠準(zhǔn)確，進(jìn)而影響分類精度。針對(duì)這一缺乏，提出了基于神經(jīng)網(wǎng)絡(luò)和CHI的改良KNN方法，應(yīng)用

12、SOM神經(jīng)網(wǎng)絡(luò)進(jìn)展VSM模型各維權(quán)重的計(jì)算。該方法首先運(yùn)用CHI概率統(tǒng)計(jì)方法進(jìn)展初步特征提取和模式聚合，其特征權(quán)重的計(jì)算原理為:如果*一維在各個(gè)類別中取值根本一樣，則此維對(duì)于文本分類的奉獻(xiàn)率就相對(duì)較低，如果在各個(gè)類別中取值有較大的差異，則就具有較強(qiáng)的文本分類能力，而方差正好是反響變量分布均勻狀態(tài)的主要指標(biāo)。該方法有效地提高了文本分類的精度。提出了利用SVM9來確定特征的權(quán)重，即基于SVM特征加權(quán)算法(FWKNN，featureweightedKNN)。試驗(yàn)說明，在一定的條件下，F(xiàn)WKNN能夠極提高分類準(zhǔn)確率。該方法利用SVM可以定量確定樣本的每個(gè)特征與分類的相關(guān)度由分類函數(shù)的權(quán)重向量給出:其中

13、為每個(gè)樣本對(duì)應(yīng)的Lagrange乘子。特征權(quán)重確定后，就可以修改樣本之間的距離函數(shù)以便更好地反映實(shí)際問題。-. z實(shí)驗(yàn)結(jié)果及分析數(shù)據(jù)集實(shí)驗(yàn)數(shù)據(jù)集由中科院計(jì)算所提供的中文文本分類語料庫TanCorpV1.0，本語料庫收集了12類文本，共14150篇。該數(shù)據(jù)集中的文本已通過分詞、去除停用詞等預(yù)處理工作，可為實(shí)驗(yàn)節(jié)省一定的時(shí)間。本次實(shí)驗(yàn)在其中抽取了財(cái)經(jīng)、電腦、教育、科技、體育和娛樂6個(gè)類，每個(gè)類別隨機(jī)抽取600篇文本，共3600篇。計(jì)算出平均文本長(zhǎng)度后，通過互聯(lián)網(wǎng)各類論壇搜索出文本長(zhǎng)度約為每個(gè)類別平均文本長(zhǎng)1/5-1/2的測(cè)試文本共600篇，每類100篇。改良的KNN實(shí)驗(yàn)方案在3600篇文本中隨機(jī)抽

14、取每個(gè)類中的400篇作為訓(xùn)練文本，其余的1200篇作為待測(cè)文本。反復(fù)使用不同Low值，觀察分類結(jié)果，直到找到適宜的值。改良的KNN實(shí)驗(yàn)結(jié)果及分析執(zhí)行3.2中方案，其目的在于觀測(cè)Low的取值的對(duì)查全率、查準(zhǔn)率、F1值以及分類耗時(shí)的影響，從中找到比擬適宜的Low值。其結(jié)果如圖3-1和圖3-2所示。圖3-1 Low/Mid0,1的分類結(jié)果圖3-2 Low/Mid0,1的分類耗時(shí)可以看出，當(dāng)Low/Mid 0.6時(shí)，KNN分類器的查全率、查準(zhǔn)率和F1值開場(chǎng)趨于穩(wěn)定，并且其分類耗時(shí)是隨著Low/Mid的增大成正比的。-. z總結(jié)與展望本文系統(tǒng)地介紹了KNN文本分類算法根本原理，以及針對(duì)KNN算法的缺乏而

15、做的各種改良，對(duì)文本分類算法的理論研究和實(shí)際應(yīng)用起了指導(dǎo)作用。目前，KNN文本分類算法在科技文獻(xiàn)分類、網(wǎng)絡(luò)信息文本分類、中文不良文本的過濾以及對(duì)未知病毒的檢測(cè)等領(lǐng)域取得了一定的成果?？傊?，隨著互聯(lián)網(wǎng)和多媒體技術(shù)的開展，要求文本分類技術(shù)在文本的處理方法、克制噪聲干擾、分類精度等方面有進(jìn)一步的提高。如何利用KNN算法在這些方面做進(jìn)一步的改良依然是一個(gè)研究熱點(diǎn)。參考文獻(xiàn)1 袁軍鵬, 朱東華, 毅. 文本挖掘技術(shù)研究進(jìn)展. 計(jì)算機(jī)應(yīng)用研究, 2006, 23(2): 1-42 J.W.Han, M. Kamber. 數(shù)據(jù)挖掘：概念與技術(shù). . 機(jī)械工業(yè)出版, 2007: 3-63 Luhn H.P.

16、Auto-encoding of documents for information retriveal systems. In: M.Boaz,Modem Trends in Documentation, 1959: 45-584 金樹, 博鋒, *昕. 基于機(jī)械學(xué)習(xí)的中文文本分類技術(shù)研究進(jìn)展. 軟件學(xué)報(bào)，2006, 17: 1848-18595 Salton G, Wong A, Yang C S. A Vetor spaee Model for Automatic Inde*ing. In:munications of ACM, 1975, 18(11): 613-6206 Nigam

17、K, Mccallum A, Thrun S, et al. Learning to classify te*t from labeled andunlabeled documents. In: Mostow J, Madison C.R, eds. Proc. Of the 15thNational Conf.on Artificial Intelligence. Wisconsin, 1998: 792-7997 Yiming Yang. An evaluation of statistical approaches to te*t categorization. In:Information Retrieval, 1999, 1(1): 69-908 Cover T.M, Hart P.E. Nearest neighbor pattern Classification. In: IEEE TransonInforma