【正文】 最終聚類結(jié)果如圖52示：圖52 聚類結(jié)果圖53所示界面為分類界面：圖53 分類界面在聚類基礎(chǔ)上，對(duì)測(cè)試文本進(jìn)行。算法中的EM聚類和KNN分類都很好的通過(guò)C++語(yǔ)言編程實(shí)現(xiàn)。5 實(shí)驗(yàn)與分析 實(shí)驗(yàn)平臺(tái)實(shí)驗(yàn)平臺(tái)：CPU為AMD Athlon（tm），規(guī)格64 2 Dual Core Processor 4000+ ，內(nèi)存為1G DDR2；實(shí)驗(yàn)開(kāi)發(fā)環(huán)境：Windows Xp+ Microsoft Visual C++ 。由此可知，本文算法在前期準(zhǔn)備工作上稍有欠缺。但經(jīng)典的KNN算法不需要使用訓(xùn)練集進(jìn)行訓(xùn)練，訓(xùn)練時(shí)間復(fù)雜度為0。而如果用本文算法分類，設(shè)聚類后形成的新的訓(xùn)練集文檔數(shù)為，其中，則其分類時(shí)間復(fù)雜度為。而KNN分類的計(jì)算復(fù)雜度和訓(xùn)練集中的文檔數(shù)目成正比，也就是說(shuō)，如果訓(xùn)練集中文檔總數(shù)為，那么KNN的分類時(shí)間復(fù)雜度為。也就是說(shuō)EM算法聚類的最小復(fù)雜度為,與訓(xùn)練集數(shù)目的平方值有關(guān)。（訓(xùn)練文檔集數(shù)目）個(gè)對(duì)象進(jìn)行層次聚類的平均復(fù)雜度為,最壞復(fù)雜度為。算法效率的分析也就是對(duì)算法時(shí)間復(fù)雜度的分析，而一個(gè)算法的質(zhì)量?jī)?yōu)劣將直接受算法乃至程序效率的影響。由上圖可以十分清楚的了解到分類算法的步驟，具體如下：假設(shè)有一個(gè)訓(xùn)練集，類別，每個(gè)類別中有若干個(gè)訓(xùn)練樣本。（4）比較類的權(quán)重，將文本分到權(quán)重最大的那個(gè)類別中。具體步驟如下：（1）根據(jù)EM算法的聚類結(jié)果，對(duì)每一類計(jì)算出其中心點(diǎn)；（2）在眾多中心點(diǎn)中選出與新文檔最相似的K個(gè)中心點(diǎn)，公式為：其中，K 值的確定目前還沒(méi)有很好的方法，一般采用先定一個(gè)初始值，然后根據(jù)實(shí)驗(yàn)測(cè)試的結(jié)果調(diào)整 K值。Mstep中，根據(jù)Estep的值，計(jì)算使得似然函數(shù)值最大的參數(shù)估計(jì)。完整數(shù)據(jù)的似然函數(shù)為： （415）算法是在Estep和Mstep之間迭代?？梢钥闯?，隨機(jī)向量的分布是由和決定的，若表示第次迭代的最大似然函數(shù)值，表示第次迭代的最大似然函數(shù)值，可知證明，EM算法能夠保證，并且算法是收斂的。Estep： (412)顯然，輔助函數(shù)的值就是的期望值，并且是的函數(shù)，是上一步迭代運(yùn)算求得的參數(shù)值。是給定的有限整數(shù)。參數(shù)由均值和協(xié)方差矩陣組成。表示某一觀察值屬于第類的概率，即權(quán)重。假設(shè)觀測(cè)樣本，每個(gè)向量都是維的。故本節(jié)將分別介紹高斯混合模型和聚類EM算法。如此可以很大的提高分類器的性能?；舅枷肴鐖D42所示，圖中兩個(gè)多邊形代表聚類結(jié)果，其它的與圖41相同。本文所研究的基于半監(jiān)督的分類算法就是為解決此類問(wèn)題，盡可能減少錯(cuò)誤的分類，從而提高分類器的性能。虛線代表可能造成的錯(cuò)誤分類，實(shí)線為正確的分類。故現(xiàn)在文本分類大部分都是應(yīng)用的半監(jiān)督算法，以標(biāo)記數(shù)據(jù)為主，未標(biāo)記數(shù)據(jù)為輔來(lái)不斷完善分類器。前面已經(jīng)介紹了，文本分類需要大量的數(shù)據(jù)集進(jìn)行訓(xùn)練。（6）分值最大的類別即為測(cè)試文本的類別。對(duì)這K個(gè)文檔所屬類的分值統(tǒng)計(jì)完畢后，即按分值進(jìn)行排序，只有分值超過(guò)閾值的類才予以考慮。在此基礎(chǔ)上，給每一個(gè)文檔類打分，分值為K個(gè)訓(xùn)練文檔中屬于該類的文檔與測(cè)試文檔之間的相似度之和。 KNN算法K近鄰算法[22]是一種穩(wěn)定而有效的基于實(shí)例的文本分類方法。EM算法要求在Estep和Mstep之間不斷迭代，直到所估計(jì)的參數(shù)達(dá)到局部最優(yōu)。名為EM算法是為了強(qiáng)調(diào)迭代算法的兩個(gè)步驟，即Expectation step和Maximization step：（1）Estep：在給定觀測(cè)資料和前一次迭代所得的參數(shù)估計(jì)情況下計(jì)算完全資料對(duì)應(yīng)的條件期望，利用當(dāng)前網(wǎng)絡(luò)結(jié)構(gòu)和參數(shù)對(duì)未標(biāo)記樣本數(shù)據(jù)做軟分類；（2）Mstep：用極大似然函數(shù)估計(jì)確定參數(shù)的值，用于下一步的迭代。就某一個(gè)聚類算法而言，往往融合了多種聚類方法的思想，并不能簡(jiǎn)單地將其歸為上述某一類方法。（5）基于模型的方法(modelbased method):基于模型的方法為每個(gè)簇假定了一個(gè)模型，尋找數(shù)據(jù)對(duì)給定模型的最佳擬合。所有的聚類操作都在這個(gè)網(wǎng)絡(luò)結(jié)構(gòu)(即量化的空間)上進(jìn)行。這樣的方法可以用來(lái)過(guò)濾“噪音”孤立點(diǎn)數(shù)據(jù)，發(fā)現(xiàn)任意形狀的簇。以局部數(shù)據(jù)特征作為聚類的判斷標(biāo)準(zhǔn)，主要思想是:只要臨近區(qū)域的密度(對(duì)象或數(shù)據(jù)點(diǎn)的數(shù)目)超過(guò)了某個(gè)閥值，就繼續(xù)聚類。這類方法只能發(fā)現(xiàn)球狀簇，而在發(fā)現(xiàn)任意形狀的簇上遇到了困難。層次聚類方法的缺陷在于，一旦一個(gè)步驟(合并或者分裂)完成，它就不能被撤銷，即不能更正錯(cuò)誤的決定。（ii）分裂的方法，也稱為自頂向下方法，一開(kāi)始將所有對(duì)象置于一個(gè)簇中。（i）凝聚的方法，也稱自底向上方法。（2）基于層次的方法 (heirarchical method):該方法對(duì)給定的數(shù)據(jù)對(duì)象集合進(jìn)行層次分解。此類方法比較適用于聚類的形狀為凸形，大小和密度相似，聚類的數(shù)目可以合理估計(jì)的情況。實(shí)際上，絕大多數(shù)應(yīng)用采用了以下兩個(gè)比較流行的啟發(fā)式方法:（i）k平均算法:在此算法中，每個(gè)簇用該簇中對(duì)象的平均值來(lái)表示。主要的聚類算法可以劃分為如下幾類：（1）劃分的方法 (Partioning method):它是一種基于原型的聚類方法，其基本思路是:首先從數(shù)據(jù)集中隨機(jī)地選擇幾個(gè)對(duì)象作為聚類的原型，然后將其他對(duì)象分別分配到由原型所代表的最相似、也就是距離最近的類中。不論采用上述那一種距離計(jì)算方法，區(qū)間變量計(jì)量單位越小，度量值越大，對(duì)距離計(jì)算影響也就越大，從而使得差異度值也越大。當(dāng)=1時(shí)，表示曼哈頓距離。那么對(duì)象和之間的相似度一般以它們之間的距離來(lái)表示。（2）、距離函數(shù):設(shè)用個(gè)特征項(xiàng)來(lái)描述樣本，那么我們就可以把每個(gè)樣本點(diǎn)看作維空間中的一個(gè)點(diǎn)，進(jìn)而使用某種距離來(lái)表示樣本點(diǎn)之間的相似性，距離越近的樣本點(diǎn)性質(zhì)越相似，距離越遠(yuǎn)的樣本點(diǎn)差異越大。而正交時(shí)值為0。當(dāng)兩個(gè)向量的方向相近時(shí)，夾角余弦值較大，反之則小。如果一個(gè)函數(shù):滿足以下條件，我們就稱之為相似系數(shù)函數(shù)： （41） （42） （43）越接近1，兩個(gè)特征變量間的關(guān)系越密切。樣本點(diǎn)愈不相似，則相似系數(shù)值愈接近0。對(duì)應(yīng)不同性質(zhì)的數(shù)據(jù)，人們給出了不同的相似性度量標(biāo)準(zhǔn)。而采用無(wú)監(jiān)督學(xué)習(xí)方法時(shí)，就不需要人工預(yù)先確定訓(xùn)練文本類別，省去了枯燥而又費(fèi)時(shí)的工作。分類方法是典型的有監(jiān)督學(xué)習(xí)方法，它需要預(yù)先定義一個(gè)訓(xùn)練集，即對(duì)文本集合進(jìn)行人工分類，作為構(gòu)造分類函數(shù)或分類模式的基礎(chǔ)。聚類是一個(gè)無(wú)監(jiān)督的學(xué)習(xí)過(guò)程，分類是有監(jiān)督的學(xué)習(xí)過(guò)程，兩者的根本區(qū)別在于:分類時(shí)需要事先知道分類所依據(jù)的屬性值，而聚類是要找到這個(gè)分類屬性值。通過(guò)適當(dāng)?shù)木垲?，事物才便于研究，事物的?nèi)部規(guī)律才可能為人類所掌握。通過(guò)實(shí)驗(yàn)我們發(fā)現(xiàn)，上述算法在很大程度上減少了其計(jì)算復(fù)雜度，從而提高了分類器的性能。在上述經(jīng)典KNN算法中，對(duì)于一個(gè)測(cè)試文檔，需要計(jì)算它與訓(xùn)練樣本集中每個(gè)文本的相似度，計(jì)算復(fù)雜度非常高。4 基于EM和KNN的半監(jiān)督文本分類本文針對(duì)的是KNN這種常用的文本分類算法。本章主要是對(duì)文本分類相關(guān)知識(shí)的學(xué)習(xí)。（6）使用不同的分類方法。（4）是否采用了特征平滑技術(shù)。 （2）使用不同的特征提取方法。用、和表示微平均中的微觀召回率、微觀準(zhǔn)確率和微觀F值，則分類系統(tǒng)的微平均計(jì)算公式如下: （318） （319） （320）用、和表示宏平均中的宏觀召回率、宏觀準(zhǔn)確率和宏觀F值，則分類系統(tǒng)的宏平均計(jì)算公式如下: （321） （322） （323）一般來(lái)說(shuō)，微平均易受到大類結(jié)果的影響，而宏平均是對(duì)全部類別取均值，相對(duì)易受小類分類結(jié)果的影響。對(duì)于多類別分類，一般采用平均的方法:微平均(microaverage)和宏平均(macroaverage)。對(duì)于簡(jiǎn)單的兩類分類器，評(píng)價(jià)系統(tǒng)性能的指標(biāo)分別定義如下:（1）正確率:識(shí)別正確的樣本數(shù)/識(shí)別樣本總數(shù)（2）召回率()/查全率:分類器正確判為該類的樣本數(shù)/該類的樣本總數(shù)，即：漏識(shí)率，（3）準(zhǔn)確率（）:正確判為該類的樣本數(shù)/判為該類的樣本總數(shù)，即:誤識(shí)率，（4）錯(cuò)誤率:識(shí)別錯(cuò)誤的樣本數(shù)/識(shí)別樣本總數(shù)（5）漏識(shí)率:該類樣本中沒(méi)有被判為該類的樣本數(shù)/該類樣本總數(shù)（6）誤識(shí)率:不屬于該類的樣本數(shù)/判為該類的樣本總數(shù)（7） F值:將準(zhǔn)確率與召回率兩者結(jié)合為一個(gè)指標(biāo)，兩者相對(duì)比重可用參數(shù)來(lái)刻畫(huà)，計(jì)算公式如下: （317）式中，當(dāng)=0時(shí)，；當(dāng)=時(shí)，；當(dāng)=1時(shí)（即F1），Precision與Recall在系統(tǒng)中有著同樣的重要性。 是分類器預(yù)測(cè)為類的文檔數(shù)。文本分類是為了揭示分類器的分類性能，因此除了上述兩項(xiàng)指標(biāo)外，還采用了收益率(Gain)、分類正確率(ClassifiCation)、準(zhǔn)確率與召回率的幾何平均數(shù)、信息估計(jì)值等來(lái)衡量分類器的性能。從而導(dǎo)致分類精度的降低。(4)、類別總量是影響分類系統(tǒng)準(zhǔn)確度的一個(gè)重要因素，類別總量越多，分類精度越低，產(chǎn)生分類交叉的可能性也就越大，如果人工分類過(guò)于詳細(xì)，系統(tǒng)在自動(dòng)分類中，對(duì)于一些交叉的類別分類精度會(huì)降低。而部分學(xué)科，存在著交叉現(xiàn)象，分類精度較低，如政治、經(jīng)濟(jì)等。(3)、類別特點(diǎn)的影響:分類標(biāo)準(zhǔn)的制定，在相當(dāng)程度上影響文本分類的準(zhǔn)確度，特別是存在類別交叉情況時(shí)更突出。(2)、訓(xùn)練語(yǔ)料的影響: 在相同的分類標(biāo)準(zhǔn)下，各人對(duì)分類規(guī)則的理解差異，較大程度影響分類系統(tǒng)的準(zhǔn)確度，以相同的分類標(biāo)準(zhǔn)與分類層次(1層)等測(cè)試環(huán)境，以來(lái)源于復(fù)旦大學(xué)的訓(xùn)練語(yǔ)料作為學(xué)習(xí)樣板，測(cè)試來(lái)源于人民日?qǐng)?bào)和sina網(wǎng)的語(yǔ)料，發(fā)現(xiàn)分類的精度下降很多。封閉性測(cè)試是指訓(xùn)練語(yǔ)料的學(xué)習(xí)獲取分類知識(shí)，開(kāi)放性測(cè)試是對(duì)測(cè)試語(yǔ)料進(jìn)行分類實(shí)驗(yàn)。影響分類效果的主要因素根據(jù)實(shí)驗(yàn)和經(jīng)驗(yàn)，影響文本分類算法和系統(tǒng)質(zhì)量評(píng)價(jià)的因素是多方面的，除分類算法的因素外，還與測(cè)試方法、分類標(biāo)準(zhǔn)、分類層次和語(yǔ)料庫(kù)是否標(biāo)準(zhǔn)等有關(guān)。支持向量與超平面之間的距離為，則支持向量間距為，尋找超平面的問(wèn)題可化為求解以下二次規(guī)劃問(wèn)題：最小化泛函數(shù)約束條件為：利用Lagrange優(yōu)化方法得到最優(yōu)分類面：，為任意支持向量從上式可以看出，=0的樣本對(duì)于分類不起任何作用，只有0的樣本起作用，從而決定分類結(jié)果，這樣的樣本即為支持向量。離超平面最近的數(shù)據(jù)點(diǎn)就被稱為支持向量，也就是圖中在H1和H2上的數(shù)據(jù)點(diǎn)。Margin=H1HH2圖37 支持向量機(jī)的決策面在線性可分空間中，決策面常被稱為超平面。該算法基于結(jié)構(gòu)風(fēng)險(xiǎn)最小化原理，將數(shù)據(jù)集合壓縮到支持向量集合(通常為前者的3％～5％)，學(xué)習(xí)得到分類決策函數(shù)。這個(gè)過(guò)程是利用決策樹(shù)進(jìn)行分類的過(guò)程，利用幾個(gè)變量(每個(gè)變量對(duì)應(yīng)一個(gè)問(wèn)題)來(lái)判斷所屬的類別(最后每個(gè)葉子會(huì)對(duì)應(yīng)一個(gè)類別)。每個(gè)分支要么是一個(gè)新的決策節(jié)點(diǎn)，要么是樹(shù)的結(jié)尾，稱為葉子。如CART算法得到的決策樹(shù)每個(gè)節(jié)點(diǎn)有兩個(gè)分支，這種樹(shù)稱為二叉樹(shù)。收入165。決策樹(shù)中最上面的節(jié)點(diǎn)稱為根節(jié)點(diǎn)，是整個(gè)決策樹(shù)的開(kāi)始。但是該假設(shè)對(duì)于絕大多數(shù)真實(shí)的文本都不成立，從而分類精度有所降低。計(jì)算和的過(guò)程就是建立分類模型的過(guò)程。根據(jù)NB分類法有: （314） (315)對(duì)文檔進(jìn)行分類，就是按(315)式計(jì)算所有文檔類在給定情況下的概率。NB方法的一個(gè)前提假設(shè)是:在給定的文檔類語(yǔ)境下，文檔屬性是相互獨(dú)立的。通常，為了強(qiáng)調(diào)正例文本的重要性，正例的權(quán)值取得較大，而反例的權(quán)值取得比較小。Rocchio公式為： （313）其中指類的中心向量，是指文檔向量的權(quán)重，是所有訓(xùn)練樣本的數(shù)目，是訓(xùn)練集中屬于類的正例樣本的個(gè)數(shù)，為反例樣本的個(gè)數(shù)。下面介紹幾種常用的分類方法:（1）、Rocchio算法[17]Rocchio算法是情報(bào)檢索領(lǐng)域最經(jīng)典的算法。常用的文本分類算法文本轉(zhuǎn)化為向量形式并經(jīng)特征提取以后，便可以進(jìn)行文本分類了，也稱特征匹配。但采用多分類器的假設(shè)前提是認(rèn)為各類文本之間是相互獨(dú)立的，事實(shí)上，這一點(diǎn)很難做到，因?yàn)樽匀徽Z(yǔ)言的豐富多樣性使得各類文本之間存在著用語(yǔ)“斜交”的情況，也就是說(shuō)，這種獨(dú)立性的假設(shè)前提是不存在的，因而各個(gè)類別的特征子空間之間的相互獨(dú)立也是很難做到的。對(duì)于樣本的邊界重疊問(wèn)題，也就是對(duì)存在著兼類現(xiàn)象的文本，在多分類器模式下，會(huì)對(duì)此類文本賦予多個(gè)類別。多分類器模式下，每個(gè)類別的分類器的輸出為待分類文本是否屬于該類別。而對(duì)于圖33所示的情況，在采用KNN法或SVM法的時(shí)候，很難給予正確的分類，而采用Rocchio法則需要很好地選擇類向量。這樣一來(lái)，在單分類器模式下，對(duì)處于這兩種情況下的樣本，很難給予正確的分類。具體地說(shuō)，就是同類樣本之間的距離可能會(huì)大于不同樣本之間的距離，各類樣本存在著混雜分布的情況。在單分類器模式下的輸出為待分類文本所屬的具體的類別[12]。考慮到文檔長(zhǎng)度的影響，對(duì)上面公式進(jìn)行歸一化: （311）為了降低的作用將式(311)調(diào)整為： （312）文本分類模式CjCkCjCjCk圖33 樣本的多峰分布 圖34 樣本的邊界重疊文本分類器包括兩個(gè)要素，一個(gè)是文本存在的特征空間，另一個(gè)是在該特征空間中所采取的分類方法。二是文檔集中含有特征詞的文檔數(shù)越大越不重要，