【正文】 ）召回率()/查全率:分類器正確判為該類的樣本數(shù)/該類的樣本總數(shù)，即：漏識率，（3）準(zhǔn)確率（）:正確判為該類的樣本數(shù)/判為該類的樣本總數(shù)，即:誤識率，（4）錯(cuò)誤率:識別錯(cuò)誤的樣本數(shù)/識別樣本總數(shù)（5）漏識率:該類樣本中沒有被判為該類的樣本數(shù)/該類樣本總數(shù)（6）誤識率:不屬于該類的樣本數(shù)/判為該類的樣本總數(shù)（7） F值:將準(zhǔn)確率與召回率兩者結(jié)合為一個(gè)指標(biāo)，兩者相對比重可用參數(shù)來刻畫，計(jì)算公式如下: （317）式中，當(dāng)=0時(shí)，；當(dāng)=時(shí)，；當(dāng)=1時(shí)（即F1），Precision與Recall在系統(tǒng)中有著同樣的重要性。（4）是否采用了特征平滑技術(shù)。在上述經(jīng)典KNN算法中，對于一個(gè)測試文檔，需要計(jì)算它與訓(xùn)練樣本集中每個(gè)文本的相似度，計(jì)算復(fù)雜度非常高。分類方法是典型的有監(jiān)督學(xué)習(xí)方法，它需要預(yù)先定義一個(gè)訓(xùn)練集，即對文本集合進(jìn)行人工分類，作為構(gòu)造分類函數(shù)或分類模式的基礎(chǔ)。如果一個(gè)函數(shù):滿足以下條件，我們就稱之為相似系數(shù)函數(shù)： （41） （42） （43）越接近1，兩個(gè)特征變量間的關(guān)系越密切。那么對象和之間的相似度一般以它們之間的距離來表示。實(shí)際上，絕大多數(shù)應(yīng)用采用了以下兩個(gè)比較流行的啟發(fā)式方法:（i）k平均算法:在此算法中，每個(gè)簇用該簇中對象的平均值來表示。（ii）分裂的方法，也稱為自頂向下方法，一開始將所有對象置于一個(gè)簇中。這樣的方法可以用來過濾“噪音”孤立點(diǎn)數(shù)據(jù)，發(fā)現(xiàn)任意形狀的簇。名為EM算法是為了強(qiáng)調(diào)迭代算法的兩個(gè)步驟，即Expectation step和Maximization step：（1）Estep：在給定觀測資料和前一次迭代所得的參數(shù)估計(jì)情況下計(jì)算完全資料對應(yīng)的條件期望，利用當(dāng)前網(wǎng)絡(luò)結(jié)構(gòu)和參數(shù)對未標(biāo)記樣本數(shù)據(jù)做軟分類；（2）Mstep：用極大似然函數(shù)估計(jì)確定參數(shù)的值，用于下一步的迭代。對這K個(gè)文檔所屬類的分值統(tǒng)計(jì)完畢后，即按分值進(jìn)行排序，只有分值超過閾值的類才予以考慮。虛線代表可能造成的錯(cuò)誤分類，實(shí)線為正確的分類。故本節(jié)將分別介紹高斯混合模型和聚類EM算法。是給定的有限整數(shù)。Mstep中，根據(jù)Estep的值，計(jì)算使得似然函數(shù)值最大的參數(shù)估計(jì)。算法效率的分析也就是對算法時(shí)間復(fù)雜度的分析，而一個(gè)算法的質(zhì)量優(yōu)劣將直接受算法乃至程序效率的影響。而如果用本文算法分類，設(shè)聚類后形成的新的訓(xùn)練集文檔數(shù)為，其中，則其分類時(shí)間復(fù)雜度為。算法中的EM聚類和KNN分類都很好的通過C++語言編程實(shí)現(xiàn)。5 實(shí)驗(yàn)與分析 實(shí)驗(yàn)平臺實(shí)驗(yàn)平臺：CPU為AMD Athlon（tm），規(guī)格64 2 Dual Core Processor 4000+ ，內(nèi)存為1G DDR2；實(shí)驗(yàn)開發(fā)環(huán)境：Windows Xp+ Microsoft Visual C++ 。而KNN分類的計(jì)算復(fù)雜度和訓(xùn)練集中的文檔數(shù)目成正比，也就是說，如果訓(xùn)練集中文檔總數(shù)為，那么KNN的分類時(shí)間復(fù)雜度為。由上圖可以十分清楚的了解到分類算法的步驟，具體如下：假設(shè)有一個(gè)訓(xùn)練集，類別，每個(gè)類別中有若干個(gè)訓(xùn)練樣本。完整數(shù)據(jù)的似然函數(shù)為： （415）算法是在Estep和Mstep之間迭代。參數(shù)由均值和協(xié)方差矩陣組成。如此可以很大的提高分類器的性能。故現(xiàn)在文本分類大部分都是應(yīng)用的半監(jiān)督算法，以標(biāo)記數(shù)據(jù)為主，未標(biāo)記數(shù)據(jù)為輔來不斷完善分類器。在此基礎(chǔ)上，給每一個(gè)文檔類打分，分值為K個(gè)訓(xùn)練文檔中屬于該類的文檔與測試文檔之間的相似度之和。就某一個(gè)聚類算法而言，往往融合了多種聚類方法的思想，并不能簡單地將其歸為上述某一類方法。以局部數(shù)據(jù)特征作為聚類的判斷標(biāo)準(zhǔn)，主要思想是:只要臨近區(qū)域的密度(對象或數(shù)據(jù)點(diǎn)的數(shù)目)超過了某個(gè)閥值，就繼續(xù)聚類。（i）凝聚的方法，也稱自底向上方法。主要的聚類算法可以劃分為如下幾類：（1）劃分的方法 (Partioning method):它是一種基于原型的聚類方法，其基本思路是:首先從數(shù)據(jù)集中隨機(jī)地選擇幾個(gè)對象作為聚類的原型，然后將其他對象分別分配到由原型所代表的最相似、也就是距離最近的類中。（2）、距離函數(shù):設(shè)用個(gè)特征項(xiàng)來描述樣本，那么我們就可以把每個(gè)樣本點(diǎn)看作維空間中的一個(gè)點(diǎn)，進(jìn)而使用某種距離來表示樣本點(diǎn)之間的相似性，距離越近的樣本點(diǎn)性質(zhì)越相似，距離越遠(yuǎn)的樣本點(diǎn)差異越大。樣本點(diǎn)愈不相似，則相似系數(shù)值愈接近0。聚類是一個(gè)無監(jiān)督的學(xué)習(xí)過程，分類是有監(jiān)督的學(xué)習(xí)過程，兩者的根本區(qū)別在于:分類時(shí)需要事先知道分類所依據(jù)的屬性值，而聚類是要找到這個(gè)分類屬性值。4 基于EM和KNN的半監(jiān)督文本分類本文針對的是KNN這種常用的文本分類算法。 （2）使用不同的特征提取方法。 是分類器預(yù)測為類的文檔數(shù)。而部分學(xué)科，存在著交叉現(xiàn)象，分類精度較低，如政治、經(jīng)濟(jì)等。影響分類效果的主要因素根據(jù)實(shí)驗(yàn)和經(jīng)驗(yàn)，影響文本分類算法和系統(tǒng)質(zhì)量評價(jià)的因素是多方面的，除分類算法的因素外，還與測試方法、分類標(biāo)準(zhǔn)、分類層次和語料庫是否標(biāo)準(zhǔn)等有關(guān)。該算法基于結(jié)構(gòu)風(fēng)險(xiǎn)最小化原理，將數(shù)據(jù)集合壓縮到支持向量集合(通常為前者的3％～5％)，學(xué)習(xí)得到分類決策函數(shù)。收入165。根據(jù)NB分類法有: （314） (315)對文檔進(jìn)行分類，就是按(315)式計(jì)算所有文檔類在給定情況下的概率。下面介紹幾種常用的分類方法:（1）、Rocchio算法[17]Rocchio算法是情報(bào)檢索領(lǐng)域最經(jīng)典的算法。多分類器模式下，每個(gè)類別的分類器的輸出為待分類文本是否屬于該類別。在單分類器模式下的輸出為待分類文本所屬的具體的類別[12]。 布爾權(quán)重布爾權(quán)重是最簡單的一種加權(quán)方法，如果特征詞出現(xiàn)次數(shù)為0，則其權(quán)重為0，如果特征詞出現(xiàn)詞數(shù)大于0，則其權(quán)重為1。算法的計(jì)算復(fù)雜度也為。和類似，如果和不相關(guān)，則 (，)值為0，因?yàn)樵谶@種情況下，個(gè)訓(xùn)練文本的數(shù)目應(yīng)該在這四種文本中均勻分布，即===。假設(shè)文檔集合分為類，記為，…，特征項(xiàng)對于文檔類別的互信息 (，)的計(jì)算公式如下: （33）其中 (，)為特征項(xiàng)出現(xiàn)在類中的概率， (，)為特征項(xiàng)在所有文檔中的出現(xiàn)概率。它從信息論角度出發(fā)，用各個(gè)特征取值情況來劃分學(xué)習(xí)樣本空間，根據(jù)所獲取信息增益的多寡，來選擇相應(yīng)的特征。常用的文本特征選擇方法有:文檔頻率()、信息增益()、互信息()、統(tǒng)計(jì)量()，文本證據(jù)權(quán)，優(yōu)勢率，統(tǒng)計(jì)()等。向量空間模型的主要優(yōu)點(diǎn)在于:(l)標(biāo)引詞加權(quán)改進(jìn)了檢索效果。這樣，只需要提取出一份文檔中蘊(yùn)涵的各個(gè)特征詞的詞頻信息就可以對其進(jìn)行正確的分類。(1) 生成訓(xùn)練語料庫的文本特征全集；(2) 文本特征提取，形成特征子集；(3) 采用某種數(shù)學(xué)模型和分類方法進(jìn)行分類器構(gòu)造；(4) 利用訓(xùn)練語料庫中的文本對分類器進(jìn)行訓(xùn)練，得到分類器的相關(guān)參數(shù)。Susan Dumais等學(xué)者對這5種方法進(jìn)行了專門的比較研究。 1962年博科()等人提出了利用因子分析法進(jìn)行文獻(xiàn)的自動分類。從數(shù)學(xué)的角度來看，文本分類是一個(gè)映射過程，它將未標(biāo)明類別的文本映射到現(xiàn)有類別中，該映射可以是一一映射，也可以是一對多映射，因?yàn)橥ǔＲ黄谋究梢耘c多個(gè)類別相關(guān)聯(lián)。但有時(shí)源數(shù)據(jù)已經(jīng)具有圖的形式。大多數(shù)圖方法通過利用圖的拉普拉斯算子來涉及到圖。（GraphBased Methods）這曾經(jīng)是半監(jiān)督學(xué)習(xí)研究最活躍的領(lǐng)域。盡管找到精確的TSVM解是NP完全問題，但一些近似的方法已經(jīng)提出并有積極的效果[23]。（S3VMs）半監(jiān)督支持向量機(jī)（SemiSupervised SVMs）本來被稱為直推式支持向量機(jī)（TSVM），之所以現(xiàn)在稱為半監(jiān)督支持向量機(jī)是因?yàn)樗鼈円策m用于歸納，而不僅僅是直推。生成式模型以及EM方法可看成是“軟”自訓(xùn)練的特例。多種資源數(shù)據(jù)也不易統(tǒng)一切分特征屬性，在某些領(lǐng)域(如自然語言)，聯(lián)合訓(xùn)練算法也存在許多局限[6][7]。然后利用此訓(xùn)練集集合某種分類器再進(jìn)行分類。根據(jù)半監(jiān)督學(xué)習(xí)算法的工作方式，可以大致將現(xiàn)有的很多半監(jiān)督學(xué)習(xí)算法分為三大類。主要探討的問題是在歐氏空間聚集程度比較高的地方，也就是比較大的地方，變化一定很平緩的假設(shè)的合理性。其涵蓋的范圍非常廣泛，例如半監(jiān)督回歸問題；利用標(biāo)簽和特征維都缺失的數(shù)據(jù)集進(jìn)行學(xué)習(xí)；標(biāo)簽有噪聲時(shí)的數(shù)據(jù)處理；利用少量正樣本和大量未標(biāo)注數(shù)據(jù)進(jìn)行學(xué)習(xí)以及對于大量未標(biāo)注數(shù)據(jù)中已知只存在少量正樣本的情況下對于正樣本進(jìn)行檢測；對各種監(jiān)督學(xué)習(xí)算法進(jìn)行修改，探討如何融入非監(jiān)督數(shù)據(jù)信息或者對于非監(jiān)督學(xué)習(xí)算法進(jìn)行修改，探討監(jiān)督數(shù)據(jù)信息的引入；利用有限混合模型對于數(shù)據(jù)的概率分布進(jìn)行建模或者利用其他模型對于數(shù)據(jù)標(biāo)簽關(guān)于特征維的條件概率進(jìn)行建模，利用EM算法學(xué)習(xí)模型參數(shù)的半監(jiān)督學(xué)習(xí)的研究；引入合適的數(shù)學(xué)方法進(jìn)行半監(jiān)督學(xué)習(xí)，例如基于核矩陣的譜的分析，高斯隨機(jī)場的利用，利用圖論中的方法來對于樣本集進(jìn)行聚類分析；半監(jiān)督數(shù)據(jù)的流形分析等。這里均為維向量，為示例的標(biāo)記，||和||分別為和的大小，即它們所包含的示例數(shù)。2 半監(jiān)督學(xué)習(xí)半監(jiān)督學(xué)習(xí)是相對于監(jiān)督學(xué)習(xí)和無監(jiān)督學(xué)習(xí)提出來的，其介于監(jiān)督學(xué)習(xí)和無監(jiān)督學(xué)習(xí)之間。在機(jī)器學(xué)習(xí)領(lǐng)域，分類屬于監(jiān)督學(xué)習(xí)。這種分類方法適應(yīng)性強(qiáng)，方便移植，不需要行業(yè)專家的介入。因?yàn)槲谋痉诸惪梢詷O大地增強(qiáng)人們對海量信息的處理能力，早在上世紀(jì)中葉，有關(guān)文本分類的研究就已經(jīng)開展起來。 clustering。文本分類是指分析文本內(nèi)容并按一定的策略把文本歸入一個(gè)或多個(gè)合適的類別的應(yīng)用技術(shù)。然后鑒于高分類精度需要大規(guī)模己標(biāo)記訓(xùn)練集而已標(biāo)記文檔缺乏，利用未標(biāo)識文檔進(jìn)行學(xué)習(xí)的半監(jiān)督學(xué)習(xí)算法己成為文本分類的研究重點(diǎn)這一情況，著重研究了半監(jiān)督分類算法。統(tǒng)計(jì)表明，目前網(wǎng)頁的數(shù)量呈指數(shù)型增長，平均每年增加一倍。[1]從20世紀(jì)60年代起步至80年代末，文本分類主要是以專家人工構(gòu)建的知識工程技術(shù)為支撐，具有代表性的是卡內(nèi)基集團(tuán)為路透社開發(fā)的新聞自動分類系統(tǒng)(Construe System)。為此，我們需要開發(fā)比搜索引擎信息檢索技術(shù)更高層次的新技術(shù)。無疑它將在一定程度上提高學(xué)習(xí)算法的性能。所謂的“標(biāo)記”是指示例所對應(yīng)的輸出，在分類問題中標(biāo)記就是示例的類別，通常想要獲得有標(biāo)記的訓(xùn)練示例是很困難的，或者是費(fèi)時(shí)耗力的，因?yàn)橐獦?biāo)記它們需要使用人類的經(jīng)驗(yàn)進(jìn)行人工的干預(yù)。半監(jiān)督學(xué)習(xí)研究主要關(guān)注當(dāng)訓(xùn)練數(shù)據(jù)的部分信息缺失的情況下，如何獲得具有良好性能和推廣能力的學(xué)習(xí)機(jī)器，這里的信息缺失涵蓋數(shù)據(jù)的類別標(biāo)簽缺失或者存在噪聲，數(shù)據(jù)的部分特征維缺失等多種情況。[2]半監(jiān)督學(xué)習(xí)研究正在繼續(xù)從廣度和深度上不斷進(jìn)行擴(kuò)展，但是依然存在很多問題。分析如何利用監(jiān)督數(shù)據(jù)信息設(shè)計(jì)合適的核空間以進(jìn)行半監(jiān)督學(xué)習(xí)，討論和的關(guān)系對于半監(jiān)督學(xué)習(xí)機(jī)理中的聚類假設(shè)的分析有著很重要的理論研究意義。由于在后文中會對EM算法有詳細(xì)介紹，故在此將不作介紹。文獻(xiàn)[5]分析了聯(lián)合訓(xùn)練算法優(yōu)于EMNB的三個(gè)主要原因:原因之一是前者利用了網(wǎng)頁文檔的兩種結(jié)構(gòu)信息進(jìn)行聯(lián)合訓(xùn)練。典型地，最先確定的未標(biāo)記數(shù)據(jù)點(diǎn)，連同其預(yù)測的標(biāo)記，都被添加到訓(xùn)練集。[11]自訓(xùn)練已經(jīng)被應(yīng)用于幾個(gè)自然語言處理的工作。[11]TSVM通過把邊界置于低密度區(qū)域建立了和判別式?jīng)Q策邊界之間的聯(lián)系?？梢钥闯?，這種估計(jì)是有問題的，尤其是有標(biāo)記樣本較少的情況下，一旦估計(jì)不正確，將會導(dǎo)致較差的結(jié)果?；趫D的方法建立在流行假設(shè)上。圖的權(quán)重矩陣表示為：由定義的對角陣稱為的度矩陣。面對網(wǎng)上海量的信息，傳統(tǒng)的做法是對網(wǎng)上信息進(jìn)行人工分類，并加以組織和整理，從而為人們提供一種相對有效的信息獲取手段。在理論研究方面，對單類別分類的研究要遠(yuǎn)遠(yuǎn)多于對多類別分類的研究。第二階段(1965年1974年)，自動分類的實(shí)驗(yàn)研究。我國自動分類的研究大體上正在經(jīng)歷從可行性探討輔助分類自動分類系統(tǒng)的發(fā)展階段。而要想讓計(jì)算機(jī)“讀懂”文本，必須能夠找到用于文本表示的數(shù)學(xué)模型。特征項(xiàng):文本的內(nèi)容特征常常用它所含有的基本語言單位(字、詞、詞組或短語)來表示，一般中文中使用詞語作為文本的特征項(xiàng)。與其他的檢索模型相比，向量空間模型簡單、便捷，而且分類性能也非常好，已成為當(dāng)今最流行的檢索模型。在特征項(xiàng)選擇中，計(jì)算每個(gè)特征項(xiàng)在訓(xùn)練集合中出現(xiàn)的頻率，根據(jù)預(yù)先設(shè)定的閡值排除那些文檔頻率特別低和特別高的特征項(xiàng)。 表示在整個(gè)文本訓(xùn)練集中出現(xiàn)的概率。為克服這個(gè)缺陷，使用以下公式計(jì)算特征項(xiàng)和類別的相關(guān)性: （34）其中: 為和同時(shí)出現(xiàn)的次數(shù)。在衡量詞和類別之間的相關(guān)關(guān)系上，互信息和統(tǒng)計(jì)量之間有一定的相似之處。以上介紹了五種常用的特征選擇方法，它們具有的共同優(yōu)勢是計(jì)算量相對較小，而且結(jié)果特征集的解釋性強(qiáng)，就是原來特征詞集的子集，但是它們一些方面還需改進(jìn)，比如分類器的特征集包含很多冗余的信息，同義詞、多義詞都能造成這種情況。公式如下： （39） 權(quán)重該方法基于以下兩點(diǎn)原因:一是特征詞在文檔中出現(xiàn)詞數(shù)越多越重要，權(quán)重和成正比。同類樣本的分布不夠緊湊，大多數(shù)的樣本處于類別的邊界，類與類之間存在著邊界重疊的情況。多分類器模式事實(shí)上是通過特征空間的劃分取代單分類器模式下的區(qū)域劃分，以此來解決樣本的多峰分布及邊界重疊問題，而空間的劃分也導(dǎo)致了其上執(zhí)行的分類方法的隔離。、分別用來控制中心向量、正例集和反例集所占的權(quán)重。NB方法假設(shè)一個(gè)單詞在一個(gè)分類文檔中的發(fā)生概率與該文檔中的其它單詞無關(guān)，從而使得計(jì)算復(fù)雜度簡單，具有較高的效率。允許節(jié)點(diǎn)含有多于兩個(gè)子節(jié)點(diǎn)的樹稱為多叉樹。如圖37所示，圓圈為一類數(shù)據(jù)點(diǎn)，實(shí)心圓為另一類數(shù)據(jù)點(diǎn)，H即為分割它們的超平面。與封閉性實(shí)驗(yàn)相比，開放性測試的結(jié)果更具有