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

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

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

3、了關(guān)于自動分類的第一篇論文，隨后，K.Spark,GSalton,R.M.Needham，M.E.Lesk以及KSJones等學(xué)者在這一領(lǐng)域進(jìn)行了卓有成效的研究。目前，文本分類已經(jīng)廣泛的應(yīng)用于電子郵件分類、電子會議、數(shù)字圖書館、搜索引擎、信息檢索等方面4。至今，國外文本分類技術(shù)在以下一些方面取得了不錯的研究成果。向量空間模型臣的研究日益成熟Salton等人在60年代末提出的向量空間模型在文本分類、自動索引、信息檢索等領(lǐng)域得到廣泛的應(yīng)用，已成為最簡便高效的文本表示模型之一。(2)特征項的選擇進(jìn)行了較深入的研究對于英法德等語種，文本可以由單詞、單詞簇、短語、短語簇或其他特征項進(jìn)行表示。國內(nèi)對于文本

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

5、德和黃萱菁也提出了如何選擇特征項的問題，他們提出可以使用字、詞、概念作為特征項來構(gòu)成向量空間模型，并對以此為基礎(chǔ)的文本分類系統(tǒng)進(jìn)行了初步的性能比較。但是，在這方面的研究6還沒有深入的開展，尤其是對于概念的定義不清晰，沒有全面的比較和測試系統(tǒng)。另外，在特征項抽取算法方面也缺少深入的研究。(3)文本分類算法的研究不十分完整每個分類器通常只實現(xiàn)一種分類算法，然后進(jìn)行測試和分析，缺少完整的多種分類算法性能的比較和測試。2解決方案2.1KNN文本分類算法KNN7算法最初由Cover和Hart于1968年提出問，是一個理論上比較成熟的方法。該算法的基本思想是根據(jù)傳統(tǒng)的向量空間模型，文本內(nèi)容被形式化為特征空

6、間中的加權(quán)特征向量，即D二D(T1,W1;T2,W2;Tn,Wn)。對于一個測試文本，計算它與訓(xùn)練樣本集中每個文本的相似度，找出K個最相似的文本，根據(jù)加權(quán)距離和判斷測試文本所屬的類別。具體算法步驟如下：(1)對于一個測試文本，根據(jù)特征詞形成測試文本向量(2)計算該測試文本與訓(xùn)練集中每個文本的文本相似度，計算公式為:Siin(di,di)=丫W(wǎng)UlXk-1式中:di為測試文本的特征向量，dj為第j類的中心向量;M為特征向量的維數(shù);Wk為向量的第k維(3) 按照文本相似度,在訓(xùn)練文本集中選出與測試文本最相似的k個文本在測試文本的k個近鄰中，依次計算每類的權(quán)重，計算公式如下:1如果工P(X,Cj)=

7、d聲期lo.其它式中:x為測試文本的特征向量;Sim(x,di)為相似度計算公式;b為閾值，有待于優(yōu)化選擇;而y(di，Cj)的取值為1或0，如果di屬于Cj,則函數(shù)值為1,否則為0(5)比較類的權(quán)重，將文本分到權(quán)重最大的那個類別中。KNN方法基于類比學(xué)習(xí)，是一種非參數(shù)的分類技術(shù)，在基于統(tǒng)計的模式識別中非常有效，對于未知和非正態(tài)分布可以取得較高的分類準(zhǔn)確率，具有魯棒性、概念清晰等優(yōu)點。但在文本分類中，KNN方法也存在不足，如KNN算法是懶散的分類算法，各維權(quán)值相同，使得特征向量之間的距離計算不夠準(zhǔn)確，影響分類精度。針對這些不足，分別提出了相應(yīng)的改進(jìn)算法。下面將詳細(xì)介紹。2.2改進(jìn)的KNN文本分

8、類算法2.2.1提高分類效率的改進(jìn)算法KNN算法的主要缺點是，當(dāng)訓(xùn)練樣本數(shù)量很大時將導(dǎo)致很高的計算開銷。KNN算法是懶散的分類算法，對于分類所需的計算都推遲到分類時才進(jìn)行，在其分類器中存儲有大量的樣本向量，在未知類別樣本需要分類時，再計算和所有存儲樣本的距離，對于高維文本向量或樣本集規(guī)模較大的情況，其時間和空間復(fù)雜度較高。針對這個缺點，提出了一些改進(jìn)算法:如基于FuzzyART的K最近鄰分類改進(jìn)算法，該算法用模糊自適應(yīng)共振理論(FuzzyART)對K最近鄰的訓(xùn)練樣本集進(jìn)行濃縮，以改善K最近鄰的計算速度。該算法首先用FuzzyART將訓(xùn)練樣本集中的每一類樣本進(jìn)行聚類，減少了訓(xùn)練樣本集的數(shù)據(jù)量，提

9、高了算法的計算速度，保持了預(yù)測精度，從而使該算法適用于海量數(shù)據(jù)集的情況。試驗表明，該算法適用于對復(fù)雜而數(shù)據(jù)量較大的數(shù)據(jù)庫進(jìn)行分類。提出了一種基于K近鄰方法的漸進(jìn)式中文文本分類技術(shù)，利用文本的標(biāo)題、摘要、關(guān)鍵詞、重點段落進(jìn)行漸進(jìn)式的分類處理。這樣，不用分析全文就能將部分待分類文本成功分類，從而提高了文本分類的效率。試驗結(jié)果表明，該方法在保證分類準(zhǔn)確率的基礎(chǔ)上能夠有效地提高分類效率。對于減少KNN計算量的優(yōu)化而做的研究主要是如何從原始數(shù)據(jù)集中選取代表實例集，大部分僅對低維的情況適用，而且在代表實例集每增加或刪除一個代表實例時，都要對樣本進(jìn)行一次測試，工作量大，為此，根據(jù)測試文檔在各個樣本類中的分布

10、情況提出了基于KNN分類的兩個有助于減少大量計算的重要算法:排類算法和歸類算法。從而構(gòu)建了一個基于KNN的快速文檔分類方法。理論與實驗證明，這種方法可以在不影響原有準(zhǔn)確率的條件下，提高文檔的分類速度。2.2.2 基于模式聚合和特征降維的改進(jìn)算法在計算相似度時，不考慮特征詞間的關(guān)聯(lián)關(guān)系。針對這一不足進(jìn)行的改進(jìn)有:主要考慮文檔間特征詞屬性關(guān)聯(lián)與共現(xiàn)對相似度的作用，用一個匹配系數(shù)調(diào)整兩文檔間的距離。它實質(zhì)上是強化了文本中語義鏈屬性因子的作用，修正了次要因素的噪聲影響，使文本分類結(jié)果更加理想，已有的測試結(jié)果證明了這一點，尤其在測試文本與訓(xùn)練文本集中的某些文本直觀上較相似時，結(jié)果更佳。通過分析特征詞對分

11、類貢獻(xiàn)的大小，提出了一種應(yīng)用向量聚合技術(shù)的KNN文本分類方法，很好的解決了關(guān)聯(lián)特征詞的提取問題，該方法根據(jù)每個特征詞的CHI分布曲線來確定它們在分類中的貢獻(xiàn)，應(yīng)用向量聚合技術(shù)很好地解決了關(guān)聯(lián)特征詞的提取問題。其特點在于:聚合文本向量中相關(guān)聯(lián)的特征詞作為特征項，從而取代傳統(tǒng)方法中一個特征詞對應(yīng)向量一維的做法，這樣不但縮減了向量的維數(shù)，而且加強了特征項對文本分類的貢獻(xiàn)。試驗表明，該方法明顯提高了分類的準(zhǔn)確率和召回率。2.2.3 基于特征加權(quán)的改進(jìn)算法KNN方法是建立在VSM模型上的，其樣本距離的測度使用歐式距離或余弦距離，各維權(quán)值相同，也就是以為各維對于分類的貢獻(xiàn)是相同的，這是不符合實際情況的，同

12、等的權(quán)重使得特征向量之間距離或夾角余弦的計算不夠準(zhǔn)確，進(jìn)而影響分類精度。針對這一不足，提出了基于神經(jīng)網(wǎng)絡(luò)和CHI的改進(jìn)KNN方法，應(yīng)用SOM神經(jīng)網(wǎng)絡(luò)進(jìn)行VSM模型各維權(quán)重的計算。該方法首先運用CHI概率統(tǒng)計方法進(jìn)行初步特征提取和模式聚合，其特征權(quán)重的計算原理為:如果某一維在各個類別中取值基本相同，那么此維對于文本分類的貢獻(xiàn)率就相對較低，如果在各個類別中取值有較大的差異，那么就具有較強的文本分類能力，而方差正好是反應(yīng)變量分布均勻狀態(tài)的主要指標(biāo)。該方法有效地提高了文本分類的精度。提出了利用SVM9來確定特征的權(quán)重，即基于SVM特征加權(quán)算法(FWKNN,featureweightedKNN)。試驗表

13、明，在一定的條件下，F(xiàn)WKNN能夠極大地提高分類準(zhǔn)確率。該方法利用SVM可以定量確定樣本的每個特征與分類的相關(guān)度由分類函數(shù)的權(quán)重向量給出：niW=(whw2,w3-'*wJ=工y心肌4AO其中為每個樣本對應(yīng)的Lagrange乘子。特征權(quán)重確定后，就可以修改樣本之間的距離函數(shù)以便更好地反映實際問題3實驗結(jié)果及分析3.1數(shù)據(jù)集實驗數(shù)據(jù)集由中科院計算所提供的中文文本分類語料庫TanCorpVI.O,本語料庫收集了12類文本，共14150篇。該數(shù)據(jù)集中的文本已通過分詞、去除停用詞等預(yù)處理工作，可為實驗節(jié)省一定的時間。本次實驗在其中抽取了財經(jīng)、電腦、教育、科技、體育和娛樂6個類，每個類別隨機抽取

14、600篇文本，共3600篇。計算出平均文本長度后，通過互聯(lián)網(wǎng)各類論壇搜索出文本長度約為每個類別平均文本長1/5-1/2的測試文本共600篇，每類100篇。3.2改進(jìn)的KNN實驗方案在3600篇文本中隨機抽取每個類中的400篇作為訓(xùn)練文本,其余的1200篇作為待測文本。反復(fù)使用不同Low值，觀察分類結(jié)果，直到找到合適的值。3.3改進(jìn)的KNN實驗結(jié)果及分析執(zhí)行3.2中方案，其目的在于觀測Low的取值的對查全率、查準(zhǔn)率、F1值以及分類耗時的影響，從中找到比較合適的Low值。其結(jié)果如圖3-1和圖査準(zhǔn)率-査范率T|二們圖3-1Low/MidW0,1的分類結(jié)果.20.4O.5056oa.8o1±

15、圖3-2Low/Mid£0,1的分類耗時可以看出，當(dāng)Low/Mid>0.6時，KNN分類器的查全率、查準(zhǔn)率和F1值開始趨于穩(wěn)定，并且其分類耗時是隨著Low/Mid的增大成正比的4總結(jié)與展望本文系統(tǒng)地介紹了KNN文本分類算法基本原理，以及針對KNN算法的不足而做的各種改進(jìn)，對文本分類算法的理論研究和實際應(yīng)用起了指導(dǎo)作用。目前，KNN文本分類算法在科技文獻(xiàn)分類、網(wǎng)絡(luò)信息文本分類、中文不良文本的過濾以及對未知病毒的檢測等領(lǐng)域取得了一定的成果?？傊?，隨著互聯(lián)網(wǎng)和多媒體技術(shù)的發(fā)展，要求文本分類技術(shù)在文本的處理方法、克服噪聲干擾、分類精度等方面有進(jìn)一步的提高。如何利用KNN算法在這些方面做

16、進(jìn)一步的改進(jìn)依然是一個研究熱點。參考文獻(xiàn)1袁軍鵬,朱東華,李毅.文本挖掘技術(shù)研究進(jìn)展.計算機應(yīng)用研究,2006,23(2):1-42J.W.Han,M.Kamber.數(shù)據(jù)挖掘：概念與技術(shù).北京.機械工業(yè)出版,2007:3-63 LuhnH.P.Auto-encodingofdocumentsforinformationretrivealsystems.In:M.Boaz,ModemTrendsinDocumentation,1959:45-584 蘇金樹,張博鋒,徐昕.基于機械學(xué)習(xí)的中文文本分類技術(shù)研究進(jìn)展.軟件學(xué)報，2006,17:1848-18595 SaltonG,WongA,YangC

17、S.AVetorspaeeModelforAutomaticIndexing.In:CommunicationsofACM,1975,18(11):613-6206 NigamK,MccallumA,ThrunS,etal.Learningtoclassifytextfromlabeledandunlabeleddocuments.In:MostowJ,MadisonC.R,eds.Proc.Ofthe15thNationalConf.onArtificialIntelligence.Wisconsin,1998:792-7997 YimingYang.Anevaluationofstatisticalapproachestotextcategorization.In:InformationRetrieval,1999,1(1):69-908 CoverT.M,HartP.E.NearestneighborpatternClass