matlab調(diào)幅廣播系統(tǒng)的仿真設計SVD在文本分類中的應用

南京工程學院課程設計任務書課程名稱matlab調(diào)幅廣播系統(tǒng)的仿真設計院(系)專業(yè)班級姓名學號指導教師目錄1、引言……………31.1課程設計應達到的目的………………31.2課程設計題目及要求……………………32、調(diào)頻廣播系統(tǒng)的模型及仿真環(huán)境…………………42.1MATLAB及SIMULINK建模環(huán)境簡介………………42.2調(diào)幅廣播系統(tǒng)介紹………………………42.3模型參數(shù)指標……………42.3仿真參數(shù)設計……………53、系統(tǒng)的建立與仿真……………………63.1仿真參數(shù)設置……………63.2系統(tǒng)中仿真模塊參數(shù)的設置……………63.3SCOPE端的最終波形圖…………………73.4調(diào)幅的包絡檢波和相干解調(diào)性能仿真比較……………83.5腳本程序…………………94、總結與體會………………105、主要參考文獻……………111 引言1.1設計目的及任務要求1．課程設計應達到的目的（1）掌握使用Matlab語言及其工具箱進行基本信號分析與處理的方法。（2）用matlab和simulink設計一個通信系統(tǒng)，加深對通信原理基本原理和matlab應用技術的理解；學習使用計算機建立通信系統(tǒng)仿真模型的基本方法及基本技能，學會利用仿真的手段對于實用通信系統(tǒng)的基本理論、基本算法進行實際驗證；（3）提高和挖掘?qū)W生將所學知識與實際應用相結合的能力，學習現(xiàn)有流行通信系統(tǒng)仿真軟件MATLAB的基本使用方法，學會使用這些軟件解決實際系統(tǒng)出現(xiàn)的問題；（4）培養(yǎng)學生的合作精神和獨立分析問題和解決問題的能力； 通過系統(tǒng)仿真加深對通信課程理論的理解。（5）用MATLAB完成調(diào)幅廣播系統(tǒng)的仿真，提高學生科技論文的寫作水平。1.2課程設計題目調(diào)幅廣播系統(tǒng)的仿真設計設計任務：1.采用接收濾波器AnalogFilterDesign模塊，在同一示波器上觀察調(diào)幅信號在未加入噪聲和加入噪聲后經(jīng)過濾波器后的波形。采用另外兩個相同的接收濾波器模塊，分別對純信號和純噪聲濾波，利用統(tǒng)計模塊計算輸出信號功率和噪聲功率，繼而計算輸出信噪比，用Disply顯示結果。模型文件保存為ex1_1.mdl。對中波調(diào)幅廣播傳輸系統(tǒng)進行仿真，其技術指標為：1)載波信號：幅度為1的正弦波，設初相為0，頻率在550~1605Hz內(nèi)可調(diào)；2)基帶信號：調(diào)制度(信號最大幅度與載波幅度之比)ma=0.3，頻率在100~600Hz內(nèi)可調(diào)；3)接收機選頻濾波器帶寬為12KHz，中心頻率為1000KHz；4)在信道中加入加性高斯噪聲，需要先計算出信道中應該加入噪聲的方差。設計接收機選頻濾波器輸出信噪比為20dB。2.構建包絡解調(diào)和相干解調(diào)電路，用示波器顯示解調(diào)波形。構建一個信噪比測試子系統(tǒng)，該系統(tǒng)能使輸入的兩路解調(diào)信號中的信號和噪聲近似分離，以分別計算信號和噪聲分量的功率，進而計算信噪比，并用Display顯示，同時將信噪比數(shù)據(jù)送入Workspace。模型文件保存為ex1_2.mdl。3.編寫腳本程序ex1.m，通過選擇不同信噪比，計算加性噪聲的方差送入仿真模型，調(diào)用模型文件執(zhí)行仿真，并通過matlab繪圖得到包絡解調(diào)和相干解調(diào)后的輸出信噪比與輸入信噪比的關系曲線。2調(diào)幅廣播系統(tǒng)的模型及仿真環(huán)境MATLAB及Simulink建模環(huán)境簡介MATLAB是美國MathWorks公司出品的商業(yè)數(shù)學軟件，用于算法開發(fā)、數(shù)據(jù)可視化、數(shù)據(jù)分析以及數(shù)值計算的高級技術計算語言和交互式環(huán)境，主要包括MATLAB和Simulink兩大部分。Simulink是MATLAB最重要的組件之一，它提供一個動態(tài)系統(tǒng)建模、仿真和綜合分析的集成環(huán)境。在該環(huán)境中，無需大量書寫程序，而只需要通過簡單直觀的鼠標操作，就可構造出復雜的系統(tǒng)。Simulink具有適應面廣、結構和流程清晰及仿真精細、貼近實際、效率高、靈活等優(yōu)點，并基于以上優(yōu)點Simulink已被廣泛應用于控制理論和數(shù)字信號處理的復雜仿真和設計。同時有大量的第三方軟件和硬件可應用于或被要求應用于Simulink。Simulink是MATLAB中的一種可視化仿真工具，是一種基于MATLAB的框圖設計環(huán)境，是實現(xiàn)動態(tài)系統(tǒng)建模、仿真和分析的一個軟件包，被廣泛應用于線性系統(tǒng)、非線性系統(tǒng)、數(shù)字控制及數(shù)字信號處理的建模和仿真中。Simulink可以用連續(xù)采樣時間、離散采樣時間或兩種混合的采樣時間進行建模，它也支持多速率系統(tǒng)，也就是系統(tǒng)中的不同部分具有不同的采樣速率。為了創(chuàng)建動態(tài)系統(tǒng)模型，Simulink提供了一個建立模型方塊圖的圖形用戶接口(GUI)，這個創(chuàng)建過程只需單擊和拖動鼠標操作就能完成，它提供了一種更快捷、直接明了的方式，而且用戶可以立即看到系統(tǒng)的仿真結果.Simulink®是用于動態(tài)系統(tǒng)和嵌入式系統(tǒng)的多領域仿真和基于模型的設計工具。對各種時變系統(tǒng)，包括通訊、控制、信號處理、視頻處理和圖像處理系統(tǒng)，Simulink提供了交互式圖形化環(huán)境和可定制模塊庫來對其進行設計、仿真、執(zhí)行和測試。.調(diào)幅廣播系統(tǒng)介紹模擬幅度調(diào)制是無線電最早的遠距離傳輸技術。在幅度調(diào)制中，以聲音信控制高頻率正弦信號的幅度，并以幅度變化的高頻率正選信號放大后經(jīng)過天線發(fā)射出去，成為電磁波輻射。 波動的信號要能夠有效地從天線發(fā)送出去，或者有效地將信號接收過來，需要天線的長度至少達到波長的四分之一。聲音轉換成電信號后其波長為15～15000km之間，實際中不能造出這樣長度的天線進行有效的信號收發(fā)。因此需要將象聲音信號這樣的低頻信號搬到較高的頻段上去，以便通過較短的天線發(fā)射出去。例如：移動通信所使用的900MHz頻率段上的電磁波信號長度約為0.33米，其收發(fā)天線的尺寸應為波長的四分之一，即約8cm左右。而調(diào)幅廣播中波范圍為550~1605kHz，短波約為3·30MHz，其波長范圍在幾十米到幾百米，相應的天線要長一些。 人耳可聞的聲音信號通過話筒轉化為波動的電信號，其頻率范圍為20~20kHz。大量實驗發(fā)現(xiàn)，人耳對語音頻率敏感區(qū)域約為300~3400Hz,為了節(jié)約頻帶帶寬資源，國際標準中將電話通信的傳輸頻帶規(guī)定為300~3400Hz。調(diào)幅廣播除了傳輸語音之外，還要播送音樂節(jié)目，這就需要更寬的頻帶。一般而言，調(diào)幅廣播的傳輸頻率范圍約為100~6000Hz。模型參數(shù)指標（1）基帶信號：調(diào)制度(信號最大幅度與載波幅度之比)ma=0.3，頻率在100~600Hz內(nèi)可調(diào)；（2）載波信號：幅度為1的正弦波，設初相為0，頻率在550~1605Hz內(nèi)可調(diào)；（3）接收機選頻濾波器帶寬為12kHz，中心頻率為1000kHz。（4）信道中加入噪聲。當調(diào)制度為0.3時，設計接收機選頻濾波器輸出信噪比為20dB。要求設計信道中應加入噪聲的方差，并能夠測量接收選頻濾波器實際輸出信噪比。仿真參數(shù)設計系統(tǒng)工作最高頻率為調(diào)幅載波頻率1605kHz，設計仿真采樣率為最高工作頻率的10倍左右，因此取仿真步長為 相應的仿真帶寬為仿真采樣頻率的一半，即 設基帶測試正弦信號為，載波為，則調(diào)制度為為的調(diào)制輸出信號為 顯然，的平均功率為 設信道無衰減，其中加入的白噪聲功率譜密度為，那么仿真帶寬內(nèi)噪聲的方差為 設接收選頻濾波器的功率增益為1，帶寬為B，擇選通濾波器的輸出噪聲功率為 因此，接收選通濾波器輸出信噪比為 故信道中的噪聲方差為根據(jù)上面的公式，編程計算出噪聲的方差，并將方差值和其它已知值作為仿真系統(tǒng)的參數(shù)。根據(jù)仿真設計要求的輸出信噪比SNRout可計算出相應信道中應加入的噪聲方差值，計算程序和結果如下：程序：SNR_dB=20;SNR=10.^(SNR_dB/10);m_a=0.3;P=0.5+(m_a^2)/4;W=8025.7e3;B=12e3;sigma2=P/SNR*W/B運行后結果：sigma2=3.49453.系統(tǒng)的建立與仿真仿真參數(shù)設置按照調(diào)幅廣播系統(tǒng)的物理與數(shù)學模型建立系統(tǒng)模型。根據(jù)相干方式的原理圖利用MATLAB的Simulink建立系統(tǒng)的模擬仿真圖。如下圖所示：圖3-1-1中波調(diào)幅廣播傳輸系統(tǒng)仿真參考模型系統(tǒng)中仿真模塊參數(shù)的設置SignalGenerator:信號發(fā)生器，產(chǎn)生基帶信號Waveform:sineAmplitude:0.3Frequency:1000SignalGenerator1:信號發(fā)生器，產(chǎn)生載波信號Waveform:sineAmplitude:1Frequency:1000000RandomNumber:隨機噪聲發(fā)生器，產(chǎn)生高斯正態(tài)分布隨機信號，這里用來構造高斯白噪聲信道Mean:0Variance:3.4945AnalogFilterDesign:模擬濾波器設計，三個模擬濾波器分別用于純信號，純噪聲以及信號和噪聲混合信號的濾波Designmethod:ButterworthFiltertype:BandpassLowerpassbandedgefrequency(rads/sec):2*pi*(1e6-6e3)Upperpassbandedgefrequency(rads/sec):2*pi*(1e6+6e3)Zero-OrderHold:零界保持器Sampletime:6.23e-8Variance:計算向量的方差選中RunningvariancedBConversion:分別對純信號和混合信號做對數(shù)變換Convertto:dB Inputsignal:PowerFun:運算函數(shù)Expression:u(1)-u(2)Display:顯示SNR的結果Format:shortScope端的最終波形圖在系統(tǒng)仿真模型圖中，用加法器和乘法器實現(xiàn)調(diào)幅，用RandomNumber產(chǎn)生噪聲樣值序列，并用加法器實現(xiàn)AWGN通道。為了測量輸出信噪比，以參數(shù)完全相同的三個濾波器模塊分別對純信號，純噪聲以及信號和噪聲混合信號的濾波，最后利用統(tǒng)計模塊計算輸出信號功率和噪聲功率，繼而計算輸出信噪比。某次仿真執(zhí)行后，測試信噪比為20.11dB，與設計值20dB相符。按接收濾波器輸出的調(diào)幅信號以及發(fā)送調(diào)幅信號的波形對比仿真結果如下圖所示：圖3-2-1接收濾波器輸出調(diào)幅信號以及發(fā)送調(diào)幅信號的波形及仿真3.4調(diào)幅的包絡檢波和相干解調(diào)性能仿真比較實例2：以實例1為傳輸模型，在不同輸入信噪比條件下仿真測量包絡檢波解調(diào)和同步相干解調(diào)對調(diào)幅波的解調(diào)輸出信噪比，觀察包絡檢波解調(diào)的門限效應。圖1-2所示的仿真模型(ex2.mdl)用于測量包絡檢波的門限效應，發(fā)送的調(diào)幅波參數(shù)以及仿真步進與實例1相同。首先，調(diào)幅信號通過AWGN信道后，分別送入包絡檢波器和同步相干解調(diào)器。包絡檢波器由Saturation模塊來模擬具有單向?qū)ㄐ阅艿臋z波二極管，模塊的上下門限分別設置為inf和0。兩解調(diào)器后接的低通濾波器相同。解調(diào)后的兩路信號送到示波器顯示，同時送入信噪比測試模塊，即圖中的子系統(tǒng)SNRDetection，其內(nèi)部如圖1-3所示。在SNRDetection模塊中，輸入的兩路解調(diào)信號通過濾波器將信號和噪聲近似分離，以分別計算信號和噪聲分量的功率，進而計算信噪比。兩個帶通濾波器參數(shù)相同，其中心頻率為1000Hz，帶寬為200Hz，對應于發(fā)送基帶測試信號頻率，其輸出近似視為純信號分量。兩個帶阻濾波器參數(shù)也相同，其中心頻率為1000Hz，帶寬為200Hz，其輸出可近似為信號中的噪聲分量。之后，通過零階保持模塊將信號離散化，再由buffer模塊和方差模塊計算出信號和噪聲的功率，buffer緩沖區(qū)長設置為1.6051e+005個樣值，這樣將在0.01s內(nèi)進行一次統(tǒng)計計算。最后，由分貝轉換模塊dBConversion和Fcn函數(shù)模塊計算出兩解調(diào)器的輸出信噪比。計算輸出Display顯示的同時，也送入工作空間，以便能夠編程作出兩解調(diào)性能曲線，ToWorkspace模塊設置為只將最后一次仿真結果以數(shù)組(Array)格式送入工作空間，變量名為SNR_out，它含有2個元素，即兩個解調(diào)輸出信號的檢測信噪比。當設置信道噪聲方差等于1時，執(zhí)行仿真所得到的解調(diào)信號波形如圖1-4所示?？梢钥闯?，相干解調(diào)輸出波形中，噪聲成分相對要小一些.圖3-4-1包絡檢波和相干解調(diào)性能測試仿真模型系統(tǒng)中仿真模塊參數(shù)的設置SignalGenerator:信號發(fā)生器，產(chǎn)生基帶信號Waveform:sineAmplitude:0.3Frequency:1000SignalGenerator1:信號發(fā)生器，產(chǎn)生載波信號Waveform:sineAmplitude:1Frequency:1000000RandomNumber:隨機噪聲發(fā)生器，產(chǎn)生高斯正態(tài)分布隨機信號，這里用來構造高斯白噪聲信道Mean:0Variance:1AnalogFilterDesign:Designmethod:ButterworthFiltertype:LowpassFilterOrder:2passbandedgefrequency(rads/sec):2*pi*6000Display:顯示SNR的結果Format:shortScopeTimerange:0.01圖3-4-2解調(diào)輸出信噪比近似于測量子系統(tǒng)SNRDetection的內(nèi)部結構系統(tǒng)中仿真模塊參數(shù)的設置AnalogFilterDesign:Filtertype:BandstopLowerpassbandedgefrequency(rads/sec):2*pi*900Upperpassbandedgefrequency(rads/sec):2*pi*1100AnalogFilterDesign:Filtertype:BandpassLowerpassbandedgefrequency(rads/sec):2*pi*900Upperpassbandedgefrequency(rads/sec):2*pi*1100Zero-OrderHold:零界保持器Sampletime:6.23e-8Variance:計算向量的方差選中RunningvarianceBufferOutputbuffersize:1.6051e+005dBConversion:分別對純信號和混合信號做對數(shù)變換Convertto:dB Inputsignal:PowerFun:運算函數(shù)Expression:u(3)-u(1)Expression:u(4)-u(2)Display:顯示SNR的結果Format:short圖3-4-3執(zhí)行仿真所得到的解調(diào)信號波形噪聲方差設為13.5任務三matlab源程序ex1.mclc;clearall;SNR_in_dB=0:2:6;SNR_in=10.^(SNR_in_dB./10);%信道信噪比m_a=0.3;%調(diào)制度P=0.5+(m_a^2)/4;%信號功率fork=1:length(SNR_in)sigma2=P/SNR_in(k);%計算信道噪聲方差并送入仿真模型sim('ex12.mdl');%執(zhí)行仿真SNRdemod(k,:)=SNR_out(:,1);%記錄仿真結果endplot(SNR_in_dB,SNRdemod(:,size(SNRdemod)));xlabel('輸入信噪比dB');ylabel('解調(diào)輸出信噪比dB');legend('包絡檢波','相干解調(diào)');將圖3—4—1中的RandomNumber:設置為Mean:0Variance:sigma2通過matlab繪圖得到包絡解調(diào)和相干解調(diào)后的輸出信噪比與輸入信噪比的關系曲線：4.總結與體會通過這次的課程設計，我們對信息和通信系統(tǒng)有了更進一步的認識，尤其是在系統(tǒng)設計方面，盡管是非?；A的調(diào)幅廣播從系統(tǒng)的仿真，也是經(jīng)過若干設備協(xié)同工作，才能保證信號有效傳輸，而小到僅僅是一個參數(shù)，都有可能導致整個系統(tǒng)無法正常運行。兩周的課程設計，讓我們領教了MATLAB矩陣實驗室強大的功能和實力。通過在Simulink環(huán)境下對系統(tǒng)進行模塊化設計與仿真，使我們獲得兩方面具體經(jīng)驗，第一是MATLAB中Simulink功能模塊的使用方法，第二是圖形化和結構化的系統(tǒng)設計方法。在整個課程設計過程中也遇到很多現(xiàn)實的問題，比如各版本MATLAB軟件并不完全兼容，許多復雜模塊參數(shù)深奧難以正確設置，，比如參數(shù)設置的不理想因此總是會出現(xiàn)波形失真的現(xiàn)象等問題。但是通過上網(wǎng)查找資料和查詢參考書能夠讓我更好的完成此次設計。同時這次設計也讓我能夠更好的對應用工具MATLAB有一個進一步的了解和應用。在學習MATLAB理論基礎后，我們又在此基礎上通過利用MATLAB仿真真正的看到了通信中傳輸信息的一系列的問題。比如說要使信號不失真的能夠傳輸?shù)浇邮斩司鸵紤]很多的因數(shù)。在發(fā)送端要注意噪聲的加入，盡量的減少噪聲進入信道中，以免在接收端使信號失真度過大而不能夠恢復成原來的信號。而在接收端，采用哪種解調(diào)方式能夠更好的恢復出原來的信號。感謝指導教師和同學們的在課程設計中的熱心幫助。5、主要參考文獻參考資料：【1】邵玉斌.Matlab/Simulink通信系統(tǒng)建模與仿真實例分析.北京:清華大學出版社,2008【2】張化光,劉鑫蕊,孫秋野.MATLAB/SIMULINK實用教程.北京:人民郵電出版社,2009【3】樊昌信,曹麗娜.通信原理.北京:國防工業(yè)出版社,2008【4】劉衛(wèi)國.MATLAB程序設計教程.北京:中國水利水電出版社,2005工程碩士學位論文SVD在文本分類中的應用作者姓名工程領域軟件工程校內(nèi)指導教師校外指導教師所在學院軟件學院論文提交日期ApplicationoftheSVDintextclassificationADissertationSubmittedfortheDegreeofMasterCandidate：Heliangliang Supervisor：Prof.ZhangPingjianSouthChinaUniversityofTechnologyGuangzhou，China分類號：TP3學校代號：學號：華南理工大學碩士學位論文SVD在文本分類中的應用作者姓名：申請學位級別：工程碩士工程領域名稱：軟件工程論文形式：?產(chǎn)品研發(fā)?工程設計應用研究?工程/項目管理?調(diào)研報告研究方向：軟件工程技術論文提交日期年月日論文答辯日期：年月日學位授予單位：：華南理工大學學位授予日期：年月日答辯委員會成員：主席：委員：緒論課題的研究背景及意義隨著計算機及互聯(lián)網(wǎng)的進一步普及，我們的信息正處在一個急劇增長的時代。據(jù)2012年7月19日發(fā)布的《第30次中國互聯(lián)網(wǎng)絡發(fā)展狀況調(diào)查統(tǒng)計報告》顯示，截至2012年6月底，中國網(wǎng)民數(shù)量達到5.38億，互聯(lián)網(wǎng)普及率為39.9%[1]。隨著網(wǎng)絡的進一步普及，網(wǎng)絡信息資源也進一步增長。截至2012年6月底，我國域名總數(shù)為873萬個，較2011年底增加98萬個，半年增長率為12.7%。.CN域名數(shù)為398萬個，半年增加46萬個。中國網(wǎng)站數(shù)量為250萬，半年增長21萬個，增長率為9.1%[1]。網(wǎng)絡資源迅猛發(fā)展的同時，傳統(tǒng)出版物的增長也呈現(xiàn)出百花齊放的局面。據(jù)2011年的數(shù)據(jù)統(tǒng)計，中國年出版的圖書超過30萬種，年圖書總印數(shù)超過70億冊，年出版報刊超過1萬種，報刊總印數(shù)約500億冊（份），位居世界第一。這些網(wǎng)絡資源（頁面）和傳統(tǒng)出版物大部分是以文本文檔的形式存在，而我們?nèi)粘Ｋ佑|的信息，也絕大部分是文本的形式，它們或以印刷品的方式存在，或以電子文檔的形式出現(xiàn)。尤其是近十年來，隨著網(wǎng)絡的飛速發(fā)展，數(shù)字圖書館的出現(xiàn)，越來越多的文本信息以電子文檔的形式存在。信息資源的增長也給人們獲取信息帶來了更多的困難，各種信息的雜亂無序，大量重復、無用的信息充斥其中。如何從海量的資源中快速獲取自己想要的信息成為越來越熱門的研究課題。文本分類作為處理和組織大量文本數(shù)據(jù)的關鍵技術，可以把數(shù)量巨大但缺乏結構的文本數(shù)據(jù)組織成規(guī)范的文本數(shù)據(jù)，幫助人們提高信息檢索的效率。文本自動分類就是利用計算機系統(tǒng)對文本集合按照一定的分類體系或標準進行自動類別標記，分類工具根據(jù)文本的信息將其分配到已經(jīng)存在的類別中。通過對文本信息進行基于內(nèi)容的分類，自動生成便于用戶使用的文本分類系統(tǒng)，從而可以大大降低組織整理文本耗費的人力資源，幫助用戶快速找到所需信息?，F(xiàn)有的文本分類方法大體可分為三種：基于統(tǒng)計的方法、基于規(guī)則的方法、基于連接的方法?；诮y(tǒng)計的方法是一種經(jīng)驗主義方法，是基于概率的。其缺點是忽略了小概率事件，其優(yōu)勢在于它的全部知識是通過對大規(guī)模語料分析所得到的，對語言處理提供了比較客觀的數(shù)據(jù)依據(jù)和可靠的質(zhì)量保證?；诮y(tǒng)計學方法主要有：NaiveBayes、K-最近鄰居、支持向量機等?；谝?guī)則的方法是一種確定性的演繹推理方法。常用的方法有決策樹、關聯(lián)規(guī)則等。這種方法的優(yōu)勢在于根據(jù)上下文對確定性事件進行定性描述，能充分利用現(xiàn)有的語言學成果?；诮y(tǒng)計的方法無法解決的問題在這里能很好地得到解決。但它成立的前提是有大量的知識，而這些知識是人類專家總結出來的，即需要大量的人力作為支持。基于連接的方法也即神經(jīng)網(wǎng)絡方法。這種方法的特點在于，信息分布存放、處理非線性、容錯性等。目前用的較多的是BP網(wǎng)絡。這種分類方法往往會出現(xiàn)局部最優(yōu)、維數(shù)災難等問題，它的優(yōu)點在于具有智能性，適用于學習一個復雜的非線性映射。文本分類旨在對文本集進行自動合理分類。它包括對訓練文本提取類標簽、判定新文本的類屬及模型評測等一系列的計算機自動處理。文本分類是模式分類和自然語言處理的交叉學科，它與普通模式分類相比有如下特性：（1）特征空間維數(shù)較高文本分類的特性文本分類的特性當我們把詞作為中文文本的特征元素時，即使一個1000篇左右的訓練文檔集，一般也會產(chǎn)生上萬個候選特征元素，從而導致特征空間維數(shù)太高．如何降低特征空間維數(shù)又不使真實信息大量損失是文本分類研究的重點之一。（2）特征詞歧義現(xiàn)象一個特征可能有多種含義，如：。教授。這個特征既可以表示職稱，也可以表示傳授知識。另一方面，許多相同的含義可以用不同的特征來描述，如：。計算機。和。電腦。這兩個特征又常用來表示同一含義。（3）特征詞分布稀疏在文本分類中，可以作為文本特征的往往是那些在語料庫中出現(xiàn)頻數(shù)適中的詞．對一具體文本來說。特征空間中多數(shù)特征詞在該文本中出現(xiàn)頻率通常為零，這導致表示該文本的文本向量中的多數(shù)元素的值為零，此即所謂特征詞分布稀疏。（4）海量文本的快速分類隨著文本處理規(guī)模的增大，對文本分類器的分類速度提出了更高的要求．如何在不降低分類精度的前提下，降低分類算法的時間復雜度，提高文本分類器的分類速度，又是文本分類研究的另一重點。按照人們解決文本分類問題的切入點的不同，文本分類可分為基于自然語言理解的文本分類和基于統(tǒng)計數(shù)學的文本分類。當然在實際應用中使用的方法大都是這兩種方法的結合。文本分類的處理對象是文本，而文本是以自然語言的形式出現(xiàn)的，因此，試圖把文本分類建立在自然語言理解的基礎之上是很自然的事情。然而事實并非如此，由于自然語言的復雜性，想把自然語言中的一切規(guī)則用知識的形式表示出來幾乎不可能，這條途徑事實上是相當困難的。因此，一方面，人們繼續(xù)跟隨著自然語言處理技術的發(fā)展，試圖建立更為理想的基于知識庫的分類系統(tǒng)；另一方面，人們另辟蹊徑開拓了一條新的文本分類的途徑，把文本分類建立在統(tǒng)計數(shù)學的基礎之上，用統(tǒng)計的方法從文本的字頻、詞頻等相關元素中提取文本的特征，再建立相應的數(shù)學模型以實現(xiàn)分類。國內(nèi)外研究狀況國外對文本分類的研究始于20世紀50年代末，H.P.Lutm首先將詞頻統(tǒng)計思想用于文本分類，在該領域進行了開創(chuàng)性的研究。1960年，Maron在JournalofASM上發(fā)表了有關自動分類的第一篇論文[2]，其后許多學者在這一領域進行了卓有成效的研究。從20世紀60年代直到20世紀80年代末，這期間最有效的文本分類系統(tǒng)一直是由專家人工構建的基于知識工程技術的分類系統(tǒng)。其典型應用就是卡內(nèi)基集團為路透社開發(fā)的Construe系統(tǒng)，它主要是由專業(yè)人員編寫了一些分類規(guī)則來指導分類，在路透社的部分語料庫上它的效果非常好，平均準確率和召回率大約都可達到90％，但是在其他的應用領域采用Construe系統(tǒng)將會消耗大量的人力和物力。這種自動分類器構造方法的缺點是知識獲取瓶頸的存在。它必須要為領域?qū)＜耀@取的知識和知識工程師的知識表示之間架起橋梁，二者缺一不可，如果這種分類器被轉到完全不同的領域，工作必須得重新開始。90年代初期，基于機器學習的分類技術開始取代基于知識工程的方法成為文本分類的主流技術。這種算法通過歸納文本集的特征自動創(chuàng)建一個分類器，這些文本集合事先被領域?qū)＜胰斯さ胤诸惖筋惣母鱾€類中，分類器可作為一個規(guī)則決定文本是否屬于類。近年來，研究者們針對機器學習的技術進行了大膽的探討，提出了多種分類模型和分類算法，如基于向量空間模型的Rocchio分類算法及其一系列的改進算法、K近鄰算法(KNN)、決策樹(DecisionTree)、樸素貝葉斯(NaiveBayes)、神經(jīng)網(wǎng)絡(Neuralnetwork)、支持向量機(SupportVectorMachine)等等。這些方法在英文以及歐洲語種文本分類上有著廣泛的應用，均取得了不錯的效果。國外很多研究人員對英文文本分類領域的各個問題都有相當深入的研究，對幾種流行的方法進行了大量的對比分析。此外，還有一些研究表明采用組合分類器的方式能夠提高分類的精度。目前，國外的分類系統(tǒng)己經(jīng)從最初的可行性研究經(jīng)歷了試驗性研究進入了實用化階段。并在郵件分類、電子會議、信息過濾等方面得到了較為廣泛的應用。1994年，AT&T實驗室的DavidD．Lewis等人對基于非確定性的分類技術做了研究。兩年后，該實驗室將分類的技術應用到了電子郵件領域。1997年，德國Dortmund大學計算機系的TorstenJoachims等人研究了基于向量空間模型的自動分類系統(tǒng)。同年，美國Stanford大學計算機系的DaphneKole得人提出了基于很少語料詞匯的層次自動分類方法。1998年，美國CarnegieMelton大學計算機系的YimingYang等人將聚類算法應用于在線自動分類。1999年，美國JustResearch公司的AndrewMcCalum等人運用信息熵理論、Bayes理論等實現(xiàn)了多類號的自動分類。隨后，美國Massachusetts大學計算機系專門針對文本庫開發(fā)了自動分類系統(tǒng)，美國IBM和Oracle公司為推廣電子商務而研制了基于文本內(nèi)容的電子郵件自動分類系統(tǒng)，Microsoft公司也為其瀏覽器開發(fā)了基于內(nèi)容屬性分類的插件。自從文本分類的概念在國內(nèi)出現(xiàn)以來，該項技術在國內(nèi)得到了長足的發(fā)展。然而和國外的發(fā)展狀況相比，我們的水平仍相對滯后。一方面由于國內(nèi)起步較晚，另一方面則由于分類的工作主要是針對中文文本。由于漢語有許多不同于英語的特點，使得中文文本分類的難度更大。比如，漢語的書面形式是連續(xù)書寫的，詞與詞之間沒有自然的界限，在進行文本分類之前，首先要對文本進行分詞。另外，在不同的語言的研究工作中，句法分析和語義分析所占的比倒是不同的。在英語中，句法分析比語義分析的比例要大，而漢語是一種分析型語言，語義分析在漢語研究中起著舉足輕重的作用，其所占的比例比句法分析要大得多。這使得在中文文本分類中，通過句法分析等基于語法的手段把握文本的內(nèi)容變得更加困難。就發(fā)展歷史而言，國內(nèi)的文本分類的發(fā)展經(jīng)歷了三個階段：國外研究成果引進階段、分類技術完善階段以及面向漢語分類技術的發(fā)展階段；而就發(fā)展方向來看，則有基于外延的分類方法和基于概念的分類方法之分。中國科學院、清華大學、上海交通大學、復旦大學、南京大學、一些大學的著名學者在該領域做出了一些研究成果，研制出一批基于詞典法和基于專家系統(tǒng)的分類系統(tǒng)。由于中文與英文存在較大的差異，不能照搬國外的研究成果，中文文本分類的研究基本上是在英文文本分類的研究策略上，結合中文文本的特點，繼而形成中文文本分類研究體系。通過對國內(nèi)外的文獻進行查閱得知，傳統(tǒng)的文本分類模型一般都是以單個的詞語作為特征的。而在研究中，往往為了降低模型的復雜度，一般主觀地認為詞與詞之間是相互獨立的，是沒有關聯(lián)的。這顯然是與事實相違背的，因此向量空間模型的效果一直不太好。1990年，ScottDeerwester提出了潛在語義索引(LatentSemanticIndexing，LSI)的方法，并將它用在信息檢索上，取得了很好的效果。此后，人們對LSI在信息檢索上的應用進行了深入的研究，并取得了大量的成果。在用詞來表示文本的時候，由于大量存在的同義詞、近義詞和多義詞，使得特征之間相互獨立的假設不能成立。LSI通過統(tǒng)計大量文本中這些詞的共現(xiàn)信息，來發(fā)掘它們的內(nèi)部聯(lián)系，稱為文本的語義。LSI認為每篇文章都包含有幾種語義，這些語義之間是相互獨立的，如果可以用這些語義來表示文檔，并拿它們來進行計算，則在降低計算復雜度的同時，還可以保持很好的效果。由于這種語義不能直接得到，只能通過對文章特征的分析得到，是潛藏在文章特征之間的，所以稱為“潛在語義”。LSI的一個缺點是它有可能使一個本來區(qū)分能力很強的特征在轉換到新的空間之后被淹沒掉。本次實踐項目中采用的潛在語義模型是通過矩陣的奇異值分解(SVD,SingularValueDecomposition)作為核心技術來構造實現(xiàn)的。目前矩陣SVD計算的方法主要分為兩類：基于矩陣QR分解的方法和基于Jacobi(雅可比)迭代的方法?；诰仃嘠R分解的算法比基于Jacobi迭代的算法計算速度更快，但是基于Jacobi迭代的算法計算得到的結果精度更高(Jacobi'smethodismoreaccuratethanQR)。文獻[3]中采用雙邊Jacobi算法實現(xiàn)了奇異值分解的并行化。在文獻[4]中采用單邊Jacobi算法實現(xiàn)了奇異值分解的并行化。SVD并行化算法的論文SVD并行化算法的論文在文獻[5]中，JamesDemmel針對雙對角矩陣奇異值分解給出了一個新的算法——基于QR迭代的雙對角矩陣奇異值分解算法，并證明了該算法比其他算法精確度高。MingGu在文獻[5]的基礎上給出了一個以精度換速度的算法——分而治之的雙對角矩陣奇異值分解算法[6]，這個算法基本思想是把原矩陣分解成幾個子任務，每個子任務采用QR迭代方法進行分解，然后將得到的結果進行回歸運算，從而得到最終結果。這兩種方法相比，前者速度慢但是精度高；后者并行度好，速度快，但是精度會低于前者。國內(nèi)的研究情況比較少，只有少量分開發(fā)的研究成果，文獻[7]提出了基于gamma:1驅(qū)動的數(shù)據(jù)重用模型，對基于QR迭代的雙對角矩陣奇異值分解算法進行并行化研究，并在一個多核平臺上實現(xiàn)了該算法。文獻[8]為了提高圖像復原算法的性能，提出了一種改進的奇異值分解算法來估計圖像的點擴散。論文的主要內(nèi)容本論文研究分析了文本分類的相關理論知識及其主要方法。并對文本分類中存在特征-文本矩陣的高維度及高稀疏的特征進行了研究。為了解決高維度矩陣在計算中過于消耗資源的問題，引進了矩陣的奇異值分解（簡稱SVD）方法，對高維矩陣進行分解實現(xiàn)降維，使其生成一個在新的語義空間上低維矩陣，并使這個低維矩陣高度擬合的初始的高維矩陣。主要工件如下：對SVD算法進行實現(xiàn)和改進，通過并行優(yōu)化了SVD算法當前論文主要內(nèi)容。當前論文主要內(nèi)容在SVD的K值選取步驟中，提出了K值百分比的方法，使得SVD在降維和擬合初始矩陣的兩個選擇中達到平衡。把SVD方法和其他的方法進行了實驗對比。通過實驗結果，證明了SVD在文本分類中可以有效地解決同義詞和多義詞問題，并提高了文本分類的精度與速度。論文的組織和架構第一章緒論部分，介紹了論文的研究背景及意義，目前國內(nèi)外研究現(xiàn)狀，并給出論文研究的主要內(nèi)容以及組織結構。第二章討論了文本分類的相關理論知識，包括文本分類的基本概念、文本分類的應用和一般過程、文本分類的方法、文本分類的評估方法以及文本分類面臨的挑戰(zhàn)。第三章詳細介紹奇異值分解理論，并對奇異值分解在文本分類的預處理中的應用做出了詳細的步驟說明。第四章詳細介紹了本次研究中的三組實驗，SVD優(yōu)化，K值選取和SVD在文本分類中的應用，并與其他方法進行了對比。實驗結果表明，SVD在文本分類中可以有效地解決同義詞和多義詞問題，并提高了文本分類的精度與速度。最后是結論與展望，總結全文并指出了以后的研究工作與方向。第二章文本分類技術綜述文本分類技術綜述文本分類概述文本分類（TC，TextClassification或TextCategorization）是指將給定文本按照事先劃分的類別進行歸類的操作。文本自動分類就是通過各種算法編程實現(xiàn)大量文本的分類操作。文本分類是一個典型的有指導的學習過程，根據(jù)已經(jīng)被標注的文本集合，通過學習得到一個文本特征和文本類別的之間的關系模型，然后利用這個模型對新文本進行分類。從數(shù)學角度看，文本分類就是一個映射的過程，將未標明類別的文本映射到預先確定的文本類別集合中，這個映射可以是一對一的映射，也可以是一對多的映射。文本分類的形式化一般定義為：給定文檔集合D={d1，d2，…，dm}，di表示第i篇文檔，D由m篇文檔組成；預先定義的文檔類別集合C={c1，c2，…，cn}，ci表示第i個類別，C由i個類別組成[9]。假設文檔集合和類別存在一個未知的目標函數(shù)?:D×C→{True，文本分類的任務可描述為努力找到一個函數(shù)?‘盡量逼近未知的目標函數(shù)?，?‘稱為分類器（Classifier）或者模型（Model），如果?di，cj=True，那么稱文檔di為類別對于一個新文本q，?‘(q)就是對文本q進行分類的結果。分類學習的目的就是尋找一個與理想映射?最相似的映射模型Min(即i=1|D|一般地，文本分類流程如下所示：圖2-1文本分類的過程文本預處理目前發(fā)布的一些語料庫或多或少存在著一些問題：一些語料庫存儲格式不盡相同，一般不能直接使用；有些文檔可能不完整，存在一些不規(guī)范字符；有些語料庫存在不少的重復文檔；有些語料庫是直接從網(wǎng)上下載的，內(nèi)容并沒有格式化，且編碼格式多樣。這些問題的存在會影響文本分類系統(tǒng)后續(xù)的工作以及分類性能，所以必須進行一些前期的工作，去除語料庫中的噪音信息，規(guī)范其內(nèi)容，使其中的文檔符合分類系統(tǒng)的要求。為保證文本分類任務能夠快速有效地執(zhí)行，必須進行文檔預處理，主要是將文檔轉化為適合文本分類系統(tǒng)處理的中間形式并濾除與任務不相關的冗余特征。一般而言，為方便各種算法的實現(xiàn)并能保持原文檔的意義，一般將文檔生成一個詞匯向量，眾多文檔就構成一個特征-文本矩陣，然后通過運行各種算法對些矩陣進行操作。預處理一般包括去除文檔中的格式標記、過濾非法字符、字母大小寫轉換、去除停用詞和稀有詞、詞干化等處理步驟，中文語料庫還有更重要的中文分詞處理。不同的以預處理方式會對分類器產(chǎn)生一定的影響，這使得很多研究人員之間的實驗結果有時很難進行比較和評優(yōu)。語料庫標簽處理每個語料庫都有各自固定的存儲格式，語料庫中的文檔有的是網(wǎng)頁，文件格式是超文本標記語言（HTML），網(wǎng)頁里除文本分類時需要的標題和文檔內(nèi)容外，還會有一些網(wǎng)頁分類需要提取的超鏈接、字體等信息。有的是半結構化的格式，自己定義了一些標記。對于網(wǎng)頁格式的文檔，由于HTML文件中存在大師的格式信息標記符號，在進行文本分類之前，我們必須根據(jù)標記提取出文檔的主要內(nèi)容，同時去除無關的一些格式標記。例如，我們一般只關心文檔的標題、正文和超鏈接描述，處理時就可以通過<TITLE><BODY><P><A>等標簽提取相應的文檔內(nèi)容。目前對于這類語料庫，網(wǎng)上已經(jīng)有一些開源工具供研究者使用，例如SourceForge網(wǎng)站上提供的HTML解析器HTMLParser以及亞洲研究院提供的基于視覺的網(wǎng)頁分割算法（Vision-basedPageSegmentation，VIPS）等[10]。目前國際公開發(fā)布的語料庫大多數(shù)是以標準通用標記語言（StandardGeneralizedMarkupLanguage，SGML）和擴展標識語言（ExtensibleMarkupLanguage，XML）表示文檔。文檔中的格式標記去除主要是指去除語料庫中的一些格式，提取文檔里的部分內(nèi)容，轉換為文本分類系統(tǒng)所需要處理的格式和內(nèi)容。比如有的語料庫會在標題前加括號注明標題，且有些標識內(nèi)有空格等，這些空格會導致分詞效果降低，會給目標矩陣加入額外的噪音。因此需要進行提取，去除噪音。中文分詞在中文文本預處理過程中，一般可以選擇字、詞或詞組作為文本的特征項。根據(jù)實驗結果，普遍認為選取詞作為特征項要優(yōu)于字和詞組，這是因為字所代表的信息量太少，而且存在很多多義字，字與字之間的界限模糊，而且用字作為特征項將導致特征向量龐大，學習分類器時容易造成特征空間的維災難；詞組雖然攜帶足夠的信息量，但詞組在文本中出現(xiàn)的機率不多，用詞組作為特征項會導致特征向量稀少，損失很多重要信息。因此，為了提取中文詞條，需要對中文文本進行較為復雜的分詞，稱為中文分詞。分詞目的是將連續(xù)的字序列按照一定的規(guī)范重新組合成詞序列的過程。目前的分詞算法一般分為以下三類：(1)機械分詞機械分詞指的是依據(jù)詞典，按一定的策略將漢字審與詞典中的詞逐一匹配，如果匹配成功，就加以切分。按照優(yōu)先匹配的詞長和掃描方向的不同，有四種常見方案，即正向最大匹配、正向最小匹配、逆向最大匹配和逆向最小匹配。機械分詞方法簡單，易于實現(xiàn)。但是由予自然語言豐富的表達方式，漢語句法構成的復雜性，新詞匯的不斷涌現(xiàn)，使得機械分詞法面臨著很多問題。如：一詞多義問題、歧義切分問題和未錄用詞識別問題，僅用機械分詞方法都不能夠很好地解決，這些問題直接影響了分詞的準確率。(2)基于理解的分詞通常的分析系統(tǒng)，都力圖在分詞階段消除所有歧義切分現(xiàn)象。而有些系統(tǒng)則在后續(xù)過程中來處理歧義切分問題，其分詞過程只是整個語言理解過程的一小部分。其基本思想就是在分詞的同時進行句法、語義分析，剩用句法信息和語義信息來處理歧義現(xiàn)象。它通常包括三個部分：分詞子系統(tǒng)、句法語義子系統(tǒng)、總控部分。在總控部分的協(xié)調(diào)下，分詞子系統(tǒng)可以獲得有關詞、句子等的句法和語義信息來對分詞歧義進行判斷，即它模擬了人對句子的理解過程。這種分詞方法需要使用大量的語言知識和信息。由于漢語語言知識的籠統(tǒng)、復雜性，難以將各種語言信息組織成機器可直接讀取的形式，因此目前基于理解的分詞系統(tǒng)還處在試驗階段。(3)基于統(tǒng)計的分詞這種分詞方法利用了一種基于統(tǒng)計學的N-Gram技術，根據(jù)相鄰字的共現(xiàn)頻率自動提取特征，使文本數(shù)據(jù)分類實現(xiàn)了分類的領域無關性和時間無關性。它無需任何詞典支持，對輸入文本所需的先驗知識少。但是，在進行N-Gram信息提取時，會產(chǎn)生非常大的數(shù)據(jù)冗余，時間代價較大，相比基于詞典分詞獲取文本特征的方法，其實現(xiàn)效率比較低。實際應用的統(tǒng)計分詞系統(tǒng)都要使用一部基本的分詞詞典(常用詞詞典)進行串匹配分詞，同時使用統(tǒng)計方法識別一些新的詞，即將串頻統(tǒng)計和串匹配結合起來，既發(fā)揮匹配分詞切分速度快、效率高的特點，又利用了無詞典分詞結合上下文識別生詞、自動消除歧義的優(yōu)點。本文采用基于詞典分詞方法。由于本文的主要研究點并不在于如何分詞，因此，我選取了中科院的ICTCLAS50分詞系統(tǒng)。中文詞法分析是中文信息處理的基礎與關鍵。中國科學院計算技術研究所在多年研究工作積累的基礎上，研制了漢語詞法分析系統(tǒng)ICTCLAS（InstituteofComputingTechnology，ChineseLexicalAnalysisSystem），主要功能包括中文分詞；詞性標注；命名實體識別；新詞識別；同時支持用戶詞典；支持繁體中文；支持gb2312、GBK、UTF8等多種編碼格式。ICTCLAS分詞速度單機500KB/s，分詞精度98.45%，API不超過100kb，各種詞典數(shù)據(jù)壓縮后不到3M，是世界上最好的漢語詞法分析器。去停用詞刪除文本（或文本表征詞典）中的停用詞和稀有詞。停用詞是指那些不能反映主題的功能詞，例如:中文中的“的”、“地”、“得”之類的助詞，以及“然而”、“因此”、“但是”之類只能反映句子語法結構的詞語等。停用詞通常是冠詞、助詞、代詞、介詞和連詞等，由于這些詞是自然語言中不可缺少的部分，所以它們頻繁地出現(xiàn)在各個類別的文檔中。然而，這些詞只包含很少量的分類信息，對文本的區(qū)分能力很弱。如果以這些詞作為文本特征的話，即使是內(nèi)容上完全不同的兩個文本也會由于這些共有的特征而很難被區(qū)分開。由于存儲這些詞既浪費存儲空間，又不會為分類帶來明顯的好處。所以，非常有必要將這些停用詞從文本中刪除。在實際應用中，文本分類系統(tǒng)通常會建立一個停用詞表，將出現(xiàn)在停用詞表中的詞直接進行過濾。這樣不僅方法簡單，而且也能將一些對分類無用的詞濾掉，禁止它們出現(xiàn)在最后的文本向量空間中，這個過程就稱為去停用詞。另外，一些稀有詞在全部文本中出現(xiàn)的次數(shù)極少，也不適合作為判斷文本內(nèi)容的特征，這些詞也要從文本中刪除。文檔表示文檔的特征自然語言形式的文本的結構非常復雜，如何將這樣的文本表示成計算機可以識別的格式是文本分類的一個基本問題，具有非常重要的意義。只有將原始的文本數(shù)據(jù)表示為結構化的計算機可處理的形式，才能對其中的信息進行分析和處理。組成中文文本的語言單位包括：字、詞、短語、句子和段落等，這些語言單位都可以作為文本的特征來表示文本，也可以選擇相應詞語或者短語的語義概念類作為文本的特征。一般來講，使用字作為文本的特征雖然簡單，但其對文本的表示能力較弱，忽略了中文的意義，在《矩陣的奇異值分解在文本分類研究中的應用》一文中，作者就是使用字作為基本表示特征，其實驗的結果并不能很好地符合實驗的預期；將詞作為文本的特征比較符合人們的自然思維習慣，也便于系統(tǒng)利用語言學知識。相對于字而言，詞中蘊含了更為豐富的語言信息，能夠更加完整和準確地表達文本中的信息。使用詞作為文本的特征，首先要求對文本進行有效的分詞，這樣會增大對文本處理的工作量和復雜度，所以一些研究中會使用短語代替高頻詞，以降低高頻詞的出現(xiàn)頻率。由于短語是以概念為特征來表示文本，相對于單純的詞而言，能夠更加準確地反映文本的內(nèi)容，因此用短語代替詞表示文本能夠提高對文本的表達能力。然而，對短語的處理相對于詞來說要復雜得多?？傊?，表示文本的特征越具有代表性，其所處的語言層次就越高，所包含的信息也就越豐富；但是，因為組合出的特征會呈現(xiàn)指數(shù)增長，所以為此所付出的分析代價也非常大。因此，基于句子和句群語言層次的特征在文本分類中很少使用。目前，普遍認為選取詞作為文本的特征要優(yōu)于字和短語。文檔的表示模型計算機不具有人類的智能，不能像人類一樣對文字信息產(chǎn)生認識和了解，所以進行聚類前，應該把非數(shù)值的文本標表示成計算機能理解的文本表示模型。文本的表示及其特征項的選取是文本挖掘、信息檢索的一個基本問題，它把從文本中抽取出的特征詞進行量化來表示文本信息。將它們從一個無結構的原始文本轉化為結構化的計算機可以識別處理的信息，即對文本進行科學的抽象，建立它的數(shù)學模型，用以描述和代替文本。使計算機能夠通過對這種模型的計算和操作來實現(xiàn)對文本的識別。由于文本是非結構化的數(shù)據(jù)，要想從大量的文本中挖掘有用的信息就必須首先將文本轉化為可處理的結構化形式。常用的文本特征表示模型有：布爾邏輯模型（BooleanModel），向量空間模型（VectorSpaceModel），潛在語義索引（LatentSemanticIndexing），概率模型（ProbabilisticModel）和后綴樹模式（SuffixTreeModel）等。下面來介紹比較經(jīng)典的布爾邏輯模型和本文采用的向量空間模型。（1）布爾邏輯模型布爾邏輯模型是一種比較簡單的檢索模型，在傳統(tǒng)的信息檢索中有廣泛的應用。在布爾邏輯模型中，每個文本文檔都被看作是由文本集中所有特征詞項所構成的向量。也就是說，可以把文本D看作是向量（T1，T2，…，Tn）的形式，其中T1，T2，…，Tn對應字典中所有包含的詞。Ti（1≤i≤n）的取值只有兩種情況，1或者0。文本表示形式如下：D=d1，布爾模型在20世紀中期開始得到了較大的發(fā)展，DIALOG、STAIRS、MEDLARS等商用檢索系統(tǒng)都用到了布爾模型。布爾模型的主要優(yōu)點在于簡單，速度快，能處理結構化提問，易于表示同義關系，但由于它僅僅使用特征項在文本中是否出現(xiàn)來表示文本特征向量，所以不能準確反映特征項對于文本的重要性，缺乏定量的分析。（2）概率模型假設待分類文本為d，預先確定的類別集合為C={c1，c2，…，cn}，所謂使用概率模型分類，就是對1≤i≤n計算條件概率P(ci|d)的值，將與待分類文本的條件概率最大的那個類別作為該文本所屬的類別。在常用的分類方法中，樸素貝葉斯方法就是基于概率模型的分類方法。（3）向量空間模型向量空間模型VSM[11-12]是Salton在20世紀60年代提出來的，是當前信息檢索領域最常用的文本特征表示模型，已經(jīng)被廣泛應用在商業(yè)搜索引擎對文本文檔的表示。向量空間模型使用到了以下幾個基本概念：文檔（Document）：文檔泛指一般的文本或者文本中的片段（包括段落、句子等），一般指一篇文章。項（Term）：項是文檔的內(nèi)容所包含的基本語言單位（譬如字、詞和短語等）。一個文檔可以看作是所有特征項的集合，表示為Document=D(t1，t2，…，tn)，其中ti是特征項，1≤i≤n，n為文檔中項的個數(shù)。項的權重（TermWeight）：對于含有n個項的文檔D(t1，t2，…，tn)，每一個特征項ti都會被賦予一定的權重wi，表示它們在文檔中的重要程度，即Document=D(t1，w1；t2，w2;…;tn，wn)，其中wi就是特征值ti的權重，1≤i≤n。通常特征項的權重由項對于文檔在文檔集中被檢索到的貢獻程度來決定，并與其成正比。在上述約定下，一個文檔可以看成是一個n維空間的向量，這就是向量空間模型。其優(yōu)點在于，把文本聚類問題轉化為空間聚類問題，易于操作和計算，提高了匹配的效率。缺點在于會忽略了特征之間的語義相關性和特征之間的順序關系。Salton提出了向量空間模型中項權重的量化方法：termfrequency-inverteddocumentfrequency（TFIDF）。TF-IDF的主要思想是，如果某個詞或短語在一篇文章中出現(xiàn)的頻率TF高，并且在其他文章中很少出現(xiàn)，則認為此詞或者短語具有很好的類別區(qū)分能力。該方法在計算某個文本文檔中詞語頻率的同時考慮該詞語在整個文檔集中的出現(xiàn)頻率，認為在文檔集中出現(xiàn)率很高或者很低的詞語的權重低于出現(xiàn)率中等的詞語。對于文檔D中詞語的TFIDF權重可以用公式(2-4)進行計算。tfi，j=ni，tf是某個詞語的出現(xiàn)頻率?ni，j是該項在文檔djidfi=log其中，|D|是文檔集中的文檔總數(shù)，而分母是包含項titfidfi，jTFIDF算法建立在這樣一個假設之上：對區(qū)別文檔最有意義的詞語應該是那些在文檔中出現(xiàn)頻率高，而在整個文檔集合的其他文檔中出現(xiàn)頻率少的詞語，所以如果特征空間坐標系取tf詞頻作為測度，就可以體現(xiàn)同類文本的特點。另外考慮到單詞區(qū)別不同類別的能力，TFIDF法認為一個單詞出現(xiàn)的文本頻數(shù)越小，它區(qū)別不同類別文本的能力就越大。因此引入了逆文本頻度idf的概念，以tf和idf的乘積作為特征空間坐標系的取值測度，并用它完成對權值tftf是權值？的調(diào)整，調(diào)整權值的目的在于突出重要單詞，抑制次要單詞。tf是權值？但是在本質(zhì)上idf是一種試圖抑制噪音的加權，并且單純地認為文本頻數(shù)小的單詞就越重要，文本頻數(shù)大的單詞就越無用，顯然這并不是完全正確的。idf的簡單結構并不能有效地反映單詞的重要程度和特征詞的分布情況，使其無法很好地完成對權值調(diào)整的功能，所以TFIDF法的精度并不是很高。此外，在TFIDF算法中并沒有體現(xiàn)出單詞的位置信息，這也是空間向量模型的不足點。維數(shù)約簡文本分類數(shù)據(jù)的兩個突出特點就是高維性和稀疏性。最直接的文檔特征表示方法是將一篇文檔中出現(xiàn)的全部詞語作為這篇文檔的特征，這樣，原始的文檔就可以很好地由這一個特征空間的向量表示。然后，這樣的原始特征空間的維數(shù)將十分巨大，通常數(shù)以萬計，甚至幾十萬，這樣的高維空間將給計算帶來高維災難。同時，原始特征空間也存在著大量的噪音，這些噪音在文檔分類是會極大地干擾分類的準度及效率。因此，很有必要對這些特征進行降維處理。這種簡化原始特征空間的技術就是維數(shù)約簡技術。維數(shù)約簡通常可以分為特征選擇（FeatureSelection，F(xiàn)S）和特征抽?。‵eatureExtraction，F(xiàn)E）兩種主要方法。特征選擇依據(jù)某個評價函數(shù)從原始特征集中選擇一部分最能反映類別統(tǒng)計特性的相關特征，評價函數(shù)用來度量文本分類中詞的重要程度，目的是濾除攜帶信息量較少的詞，只保留對分類貢獻大的詞，其理論大多數(shù)建立在統(tǒng)計和信息分類基礎上。顯然，評價函數(shù)的選擇是特征選擇的關鍵。常用的特征和選擇方法有：χ2特征抽取綜合考慮各個特征，通過原始特征的組合（線性）或轉換（非線性）得到新的特征，使其具有更好的分類特征。通常組合或者轉換后的新的特征空間能更好地表示原文檔的特征，且能夠大大降低原特征空間的維數(shù)。該方法能夠較好地處理多義詞（降低精度）、同義詞（降低召回率）問題。對原始特征做線性組合是一種非常具有吸引力的方法，因為線性組合容易計算。但是對于新組合或者轉換后的新特征不能給出合理的語義解釋。通常使用的潛在語義索引、主成分分析和Fisher線性判決分析。潛在語義分析向量空間模型的優(yōu)點在于將非結構化的文檔表示成向量形式，使得各種數(shù)學處理成為可能。但是向量空間模型關于詞間關系相互獨立的基本假設（正交假設）在實際環(huán)境中很難滿足，文檔中出現(xiàn)的詞往往存在一定的相關性。例如同義詞與多義詞現(xiàn)象。鑒于向量空間模型的特點，人們很自然要尋求一種方法，能夠獲取索引項與文檔中的潛在語義關系。潛在語義索引就是為了改善向量空間模型的效果而提出的。潛在語義索引通過對“文檔向量矩陣”進行奇異值分解（SingularValueDecomposition，SVD）將文檔矩陣分解為一個低維的正交矩陣，自動計算得到一個比原始空間小得多的有效語義空間。X=Urr其中：r是矩陣X的階；∑k=diag(σ1，?，文檔和特征間的操作就是在這個分解后的低維正交矩陣中進行語義操作。潛在語義索引方法，已經(jīng)被證明是對傳統(tǒng)的向量空間技術的一種改良，可以達到消除詞之間的相關性，簡化文檔向量的目的。本方法的具體應用訪求將在第三章進行闡述。主成分分析主成分分析應用線性代數(shù)中的KL(Karhunen-Loeve，KL)變換將原始特征空間映射到一個低維的正交空間[13-14]，由文檔矩陣X，可得到協(xié)方差矩陣（在文本分類中也稱詞條-詞條矩陣）Σ=XTX，其維數(shù)為n。那么它的前k(k<n)個最大的特征值入其對應的特征向量分別為λiζi文獻[14]的研究表明，使用PCA進行特征降維很難取得令人滿意的效果。Fisher線性判決分析雖然PCA方法對于代表數(shù)據(jù)樣本非常有效，但是并沒有理由說明主成分對區(qū)分不同的類別有什么大作用。如果我們把所有類別的樣本都放在一起，則被PCA方法拋棄的那些分布方向有可能正是能夠把不同的類別區(qū)分開來的分布方向。也就是說，PCA方法尋找的是用來有效表示的主軸方向，而判別分析方法（DiscriminateAnalysis）尋找的是用來有效分類的方向。Fisher線性判別分析是一種重要的特征提取方法。1975年Foley與Sammon基于Fisher準則，提出了一種針對兩類問題的正交判別矢量集。我們考慮把d維空間中的數(shù)據(jù)點投影到一條直線上去。當然，即使不同類的樣本點在d維空間中能夠形成互相分離的、各自內(nèi)部緊湊的集合，向任意的直線作投影也有可能把這些不同類的數(shù)據(jù)點混在一起，反而降低了分類的效果。然而，通過適當?shù)剡x擇投影直線，我們還是有可能找到能夠最大限度地區(qū)分各類數(shù)據(jù)點的投影方向。這就是經(jīng)典的可分性分析的目標。Fisher線性判決分析（FDA）[15]表示某一特征在類間分布的類內(nèi)分布之比，對于某一特征tμμ其中：C為文檔集中所有類別；N(d，t)為在文檔中t的頻數(shù)；N(d)為文檔d中所有特征的頻數(shù)之和。特征t的Fisher判決式為Fishert所以，依據(jù)對各個特征t的Fisher(t)的評分值進行特征降維。相似度計算方法相似性度量主要有以下兩種方法：相似度：相似度是兩個對象相似程度的數(shù)值度量。兩個對象越類似，它們的相似度就越高。相似度一般在區(qū)間[0,1]中取值。相異度：相異度是兩個對象差異程度的數(shù)值度量。兩個對象越類似，它們的相異度就越低。相異度常常在0和1之間取值。相似度和相異度是一個相反的概念，一般經(jīng)常使用的是對象間的相似度。相似度的計算方法有海明距離（HammingDistance）、歐幾里德距離（EuclideanDistance）、余弦距離（CosineDistance）。（1）海明距離的計算針對的是布爾邏輯模型，按公式(2-10)的方法計算文本向量中各部分的差異。Hamming_Distance(A，B)=i=1其中，ai、b（2）歐幾里德距離的計算方式如公式(2-11)：Euclidean_Distance(A，B)=i=1其中，ai、b（3）余弦距離是比較常用的相似度計算方式，計算方法如公式(2-12)：Cosine_Distance（A，其中，ai、b余弦距離更能體現(xiàn)文本間的相似度，本文采用了該方式計算余弦距離。文本分類評價指標因為文本分類從數(shù)學角度來看是一個映射過程，所以評估文本分類系統(tǒng)的標志是映射的準確程度和映射的速度。映射的速度取決于映射規(guī)則的復雜程度，而評估映射準確程度的參照物是通過專家思考判斷后對文本的分類結果(這里假設人工分類完全正確并且排除個人思維差異的因素)。主要的評估指標有：查全率（recallfactor）、查準率（也稱適中率，Pertinencyfactor）、漏分率（omissionfactor）、誤分率（也叫分類噪音，noisefactor）以及分類速度等。設n為分類系統(tǒng)中文本總量，m為分類輸出的文本量，a為n中與分類課題有關的文本量，b為m中與分類課題有關的文本量（分類正確文本量），令R表示查全率、P表示查準率、M表示漏分率、N表示誤分率，則R、P、M、N定義如下：表2-1文本分類評價指標含義預測類別實際類別Class=YesClass=NoClass=Yesa(TP)b(FN)Class=Noc(FP)d(TN)準確率查全率查準率M=100%-RN=100%-P最理想的分類效果是b、c均為0，即R、P均為100%，但實際上這是不可能的。實驗表明：R和P之間存在相反的相互依賴關系，即提高R會降低P，反之亦然[16]。通常，以查全率和查準率為指標來測定IR系統(tǒng)的有效性時，總是假定查全率為一個適當?shù)闹?，然后按查準率的高低來衡量系統(tǒng)的有效性。本章小結本章中，對文本分類技術作了一個綜述，在前人文獻的基礎上，總結了文本分類的主要步驟，詳細介紹了文本分類的各個步驟及每個步驟的相應代表方法。并著重對維數(shù)約簡這一步驟進行了研究，對潛在語義分析和主成分分析進行了介紹，并大概對各個方法的優(yōu)缺點作了闡述。第三章奇異值分解奇異值分解奇異值分解介紹奇異值分解是線性代數(shù)中一種重要的矩陣分解，是矩陣分析中正規(guī)矩陣酉對角化的推廣。奇異值分解能適應任意一個矩陣。一般而言，對于任意矩陣A，其奇異值分解數(shù)學定義如下：A=UΣV在式(3-1)中，A是一個m×n的矩陣。U是m×m階酉矩陣；Σ是半正定m×n階對角矩陣；而VT，即V的共軛轉置，是n×n階酉矩陣。這樣的分解就稱作A的奇異值分解。Σ如果Σ的矩陣中的對角元素按從大到小排列，剛Σ可以由A唯一確定。Σ=其中，σ1≥σ2≥?≥奇異值分解的數(shù)學理論在詳細介紹奇異值分解定理之前，我們先來看幾個數(shù)學定義：定義3.1[17]矩陣A=(aij)m×n定義3.2[17]設A是數(shù)域P上線性空間V的一個線性變換，如果對于數(shù)域P中一數(shù)λ0，存在一個非零向量ξ，使得Aξ=那么λ0稱為A的一個特征值，而ξ稱為A屬于特征值λ定義3.3[17]如果V是數(shù)域K上的線形空間，且對于V的任一向量x，對應一個實值函數(shù)||x||，它滿足以下三個條件：1．非負性：當x≠0時，||x||>0，當x=0時，||x||=0；2．齊次性：||ax||=||a||||x||，a∈K，x∈V；3．三角不等式：||x+y||≤||x||+||y||，x，y∈V；則稱x為V上向量x的范數(shù)，簡稱向量范數(shù)。******************************************************8定義3.4[17]向量X的P范數(shù)為||X||P定義3.5[17]矩陣空間Cm*n是一個m*n維的線性空間，設A=(a||A||被稱為Frobenius范數(shù)或簡稱為F-范數(shù)。定義3.6[17]對于一個秩為r的矩陣Am*n，ATλ1||A||F||A||2其中σi=λ在前面5個定義的基礎上，下面將介紹奇異值分解定理：定理3.1[17]奇異值分解定理(SingularValueDecomposition)設A∈Rm×n，且Rank(A)=r≤min(m，n)，則總存在正交矩陣U∈R使得：A=UΣV其中Σ=Σ1U分解式(3-2)稱作A的奇異值分解，通常簡稱SVD，其中U和V的列分別稱為矩陣A的左右奇異向量，Σ被稱為矩陣A的奇異值標準形，Σ的對角元素被稱為矩陣A的奇異值?？捎脭?shù)學歸納法證明，具體證明過程略，可參考文獻[17]。定理3.2[17]矩陣A的非零奇異值的個數(shù)等于Rank(A)。定理3.3[17]設矩陣A的SVD分解由式(3-2)給出，且r=Rank(A)≤p=min(m，n)，那么A表示A的k階截矩陣。其中UkRankRank也就是說，在F-范數(shù)意義下，Ak是和A最接近的k秩矩陣。奇異值分解的性質(zhì)及其與文本分類的關系奇異值的穩(wěn)定性定理3.4[17]：假設A，B∈Rm*n，A和B的奇異值分別為λ1≥λ2≥?≥λ定理3.4表明當矩陣A有微小擾動時，擾動前后矩陣奇異值的變化不會大于擾動矩陣的-2范數(shù)。這個性質(zhì)表明，對于存在同義詞、近義詞噪聲干擾等情況的文本特征矩陣，通過SVD后，文本的特征向量不會出現(xiàn)大的變化。這一性質(zhì)放寬了文本分類對特征的要求，并使匹配結果的準確性得到了保證。奇異值的比例不變性奇異值的比例不變性，即若矩陣A的奇異值為σ1≥σ2≥?≥a因此，為了消除幅度大小對特征提取的影響，所進行的歸一化處理不會從本質(zhì)改變奇異值的相對大小。奇異值的旋轉不變性奇異值的旋轉不變性，即若P為酉矩陣，則矩陣PA的奇異值與矩陣A的奇異值相同。即：A文本-特征矩陣的奇異值特征向量不但具有正交變換、旋轉、位移、鏡像映射等代數(shù)和幾何上的不變性，而且具有良好的穩(wěn)定性和抗噪性，可以很好地應用于文本分類中。對文本-特征矩陣進行奇異值分解的目的是：得到唯一、穩(wěn)定的特征描述；降低特征空間的維數(shù)；提高抵抗干擾和噪聲的能力。奇異值分解的幾何解釋SVD的幾何解釋對于我們更好地理解和使用潛在語義結構是十分必要的。任何一個矩陣，經(jīng)過SVD分解，得到相應的矩陣U0、Σ0和V0，選擇適當?shù)膋，化簡上述三個矩陣，得到降維的分解式A=UΣVTaa1文本1特征1文本2特征2特征3a2圖3-1奇異值分解的幾何解釋奇異值分解算法的并行優(yōu)化各種SVD算法及其特點首先來對SVD算法的發(fā)展來做簡單的回顧[18-19]：關于SVD算法的研究最早可以追溯到1873年Beltrami所做的工作，這中間在理論方面進行了大量的工作，這個歷史過程可以參考Stewart的文獻[20]。但是直到1965年Golub和Kahan才在SVD的數(shù)值計算領域取得突破性進展[21]，并且于1969給出了比較穩(wěn)定的算法（以下簡稱傳統(tǒng)QR迭代算法）[22]，這也是后來在LINPACK中所采用的方法[23]。它的中心思想是用正交變換將原矩陣化為雙對角線矩陣，然后再對雙對角線矩陣迭代進行QR分解。六十年代一份沒有出版的技術報告中，Kahan證明了雙對角線矩陣的奇異值可以精確地計算，具有和原矩陣元素的相對的精確度；進一步，1990年Demmel和Kahan給出了一種零位移的QR算法(zero-shiftQRalgorithm)，這種算法計算雙對角矩陣的奇異值具有很高的相對精度[24]，并且由此得到的奇異向量也具有很高的精度[25]。Fernando和Parlett在1994年將qd算法應用到奇異值的計算上，從而得到了一種全新的比zero-shiftQRalgorithm更加精確和快速的計算奇異值的算法[26-27]。而Demmel和Veselic在文獻[28]中則說明了用Jacobi方法與其它方法相比計算所得到的奇異值和奇異向量具有更高的精度，可惜Jacobi算法比DK算法速度要慢的多；在文獻[29]中對Jacobi方法進行了改進使得其在速度上幾乎和DK算法相當。和Strassen算法類似，SVD問題也有快速的分而制之算法，在文獻[30，31]對其有詳細的介紹，由此得到的算法在總計算量上比現(xiàn)有的LAPACK軟件包中所采用的方法要少的多。在文獻[32，33]中給出的bisection算法也可以對雙對角線矩陣計算得到具有相對精度的全部奇異值。在本次研究中，本人引用了傳統(tǒng)的QR迭代算法，并對其進行了并行優(yōu)化。傳統(tǒng)OR迭代算法具有穩(wěn)定性，這一特點在文本分類中的兩個要點之一。但是傳統(tǒng)OR迭代算法的速度還有待提升，因此，本人嘗試對傳統(tǒng)OR迭代算法進行并行優(yōu)化。本次實驗中的SVD算法設計本次實驗中，通過采用豪斯荷爾德(Householder)變換及變形QR算法對一般實矩陣A進行奇異值分解。主要步驟如下：設A為m*n階的實矩陣，則存在一個m*n的列正交矩陣U和n*n的列正交矩陣V，使A=U成立。其中Σ=diagσ0， 上式稱為實矩陣A的奇異值分解式，σi 利用A的奇異值分解式，可以計算A的廣義逆A+ 奇異值分解分為兩大步。 第一步，用豪斯荷爾德變換將A約化為雙角線矩陣。即B其中UVU中的每一個變換Uj(j=0， 對于每一個變換VjI其中ρ為一個比例因子，以避免計算過程中的溢出現(xiàn)象與誤差的積累。VjV則A其中W=ρ 第二步，用變形的QR算法進行迭代，計算所有的奇異值，即用一系列的平面旋轉變換將對角線矩陣B逐步變成對角矩陣。 在每一次的迭代中，用變換B其中變換Uj，j+1T將B中第j列主對角線下的一個非0元素變?yōu)?，同時在