【正文】 正整數(shù)。當(dāng)=1時(shí)，表示曼哈頓距離。當(dāng)=2時(shí)，表示歐幾里德距離，它是比較常用的距離計(jì)算公式。不論采用上述那一種距離計(jì)算方法，區(qū)間變量計(jì)量單位越小，度量值越大，對距離計(jì)算影響也就越大，從而使得差異度值也越大。為了避免計(jì)量單位對差異度計(jì)算的這種影響，可以對變量進(jìn)行標(biāo)準(zhǔn)化處理。主要的聚類算法可以劃分為如下幾類：（1）劃分的方法 (Partioning method):它是一種基于原型的聚類方法，其基本思路是:首先從數(shù)據(jù)集中隨機(jī)地選擇幾個(gè)對象作為聚類的原型，然后將其他對象分別分配到由原型所代表的最相似、也就是距離最近的類中。對于劃分聚類方法，一般需要一種迭代控制策略，對原型不斷進(jìn)行調(diào)整，從而使得整個(gè)聚類得到優(yōu)化，例如使得各對象到其原型的平均距離最小。實(shí)際上，絕大多數(shù)應(yīng)用采用了以下兩個(gè)比較流行的啟發(fā)式方法:（i）k平均算法:在此算法中，每個(gè)簇用該簇中對象的平均值來表示。（ii）k中心點(diǎn)算法:在此算法中，每個(gè)簇用接近聚類中心的一個(gè)對象表示。此類方法比較適用于聚類的形狀為凸形，大小和密度相似，聚類的數(shù)目可以合理估計(jì)的情況。此外這兩種方法都要求用戶指定聚類數(shù)目k。（2）基于層次的方法 (heirarchical method):該方法對給定的數(shù)據(jù)對象集合進(jìn)行層次分解。根據(jù)層次的分解如何形成，層次聚類方法可以分為凝聚的和分裂的。（i）凝聚的方法，也稱自底向上方法。一開始將每個(gè)對象作為單獨(dú)的一個(gè)組，然后相繼合并相近的對象或組，直到所有的組合并為一個(gè)(層次的最上層)，或者達(dá)到一個(gè)終止條件。（ii）分裂的方法，也稱為自頂向下方法，一開始將所有對象置于一個(gè)簇中。在迭代的每一步中，一個(gè)簇被分裂為更小的簇，直到最終每個(gè)對象在單獨(dú)的一個(gè)簇中，或者達(dá)到一個(gè)終止條件。層次聚類方法的缺陷在于，一旦一個(gè)步驟(合并或者分裂)完成，它就不能被撤銷，即不能更正錯(cuò)誤的決定。（3）基于密度的方法(densitybased method):絕大多數(shù)劃分方法基于對象之間的距離進(jìn)行聚類。這類方法只能發(fā)現(xiàn)球狀簇，而在發(fā)現(xiàn)任意形狀的簇上遇到了困難。隨之提出了基于密度的另一類聚類方法。以局部數(shù)據(jù)特征作為聚類的判斷標(biāo)準(zhǔn)，主要思想是:只要臨近區(qū)域的密度(對象或數(shù)據(jù)點(diǎn)的數(shù)目)超過了某個(gè)閥值，就繼續(xù)聚類。也就是說，對給定類中的每個(gè)數(shù)據(jù)點(diǎn)，在一個(gè)給定范圍的區(qū)域中必須至少包含某個(gè)數(shù)目的點(diǎn)。這樣的方法可以用來過濾“噪音”孤立點(diǎn)數(shù)據(jù)，發(fā)現(xiàn)任意形狀的簇。（4）基于網(wǎng)格的方法(gridbased mehotd):基于網(wǎng)格的方法把對象空間量化為有限數(shù)目的單元，形成了一個(gè)網(wǎng)絡(luò)結(jié)構(gòu)。所有的聚類操作都在這個(gè)網(wǎng)絡(luò)結(jié)構(gòu)(即量化的空間)上進(jìn)行。這種方法的主要優(yōu)點(diǎn)是處理速度快，其處理時(shí)間獨(dú)立于數(shù)據(jù)對象的數(shù)目，只與量化空間中每一維的單元數(shù)目有關(guān)。（5）基于模型的方法(modelbased method):基于模型的方法為每個(gè)簇假定了一個(gè)模型，尋找數(shù)據(jù)對給定模型的最佳擬合。如一個(gè)基于模型的算法可能通過構(gòu)建反映數(shù)據(jù)點(diǎn)空間分布的密度函數(shù)來定位聚類。就某一個(gè)聚類算法而言，往往融合了多種聚類方法的思想，并不能簡單地將其歸為上述某一類方法。 EM算法EM算法[21]是由Dempster提出，是一種被廣泛使用的半監(jiān)督學(xué)習(xí)算法，這是一種在不完全資料情況下計(jì)算極大似然函數(shù)估計(jì)和后驗(yàn)概率分布的迭代算法，亦用于計(jì)算邊緣分布。名為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ù)的值，用于下一步的迭代。把所有已標(biāo)記樣本和已軟分類的樣本作為訓(xùn)練樣本集，計(jì)算出新的最大可能的參數(shù)分布，并用來替換原有的。EM算法要求在Estep和Mstep之間不斷迭代，直到所估計(jì)的參數(shù)達(dá)到局部最優(yōu)。目前，許多EM算法的擴(kuò)展版本關(guān)注的是如何修改EM算法使得能夠盡量收斂到合理的局部極值，例如確定性退火EM算法（Deterministic Annealing EM algorithm簡寫為DAEM)[28]，分裂融合EM算法（Split and Merge EM簡寫為SMEM）[29]，或者使得EM算法在理論上能夠收斂到全局最優(yōu)值，例如利用可逆的可跳轉(zhuǎn)的Markov Monte Carlo[30]鏈基于隨機(jī)采樣的機(jī)制搜索全局最優(yōu)，另一方面，是關(guān)于如何對于模型復(fù)雜度加入約束以使EM算法能夠自動選擇有限混合模型的成分的數(shù)量同時(shí)收斂到合理的局部極值，例如基于最小信息長度（Minimum Message Length簡寫為MML）[31]準(zhǔn)則的一個(gè)算法，和基于競爭機(jī)制的EM算法。 KNN算法K近鄰算法[22]是一種穩(wěn)定而有效的基于實(shí)例的文本分類方法。采用KNN方法進(jìn)行文檔分類的過程如下：對于某一給定的測試文檔d，在訓(xùn)練文檔集中，通過相似度找到與之最相似的K個(gè)訓(xùn)練文檔。在此基礎(chǔ)上，給每一個(gè)文檔類打分，分值為K個(gè)訓(xùn)練文檔中屬于該類的文檔與測試文檔之間的相似度之和。也就是說，如果在這K個(gè)文檔中，有多個(gè)文檔同屬于一個(gè)類，則該類的分值為這些文檔與測試文檔之間的相似度之和。對這K個(gè)文檔所屬類的分值統(tǒng)計(jì)完畢后，即按分值進(jìn)行排序，只有分值超過閾值的類才予以考慮。具體步驟如下：（1）假定K=最近鄰數(shù)； （2）計(jì)算測試文檔d與所有訓(xùn)練文本的相似度； （3）從中選出K個(gè)與文本d最相似的訓(xùn)練文本為測試文本d的最近鄰；（4）收集這些已選出的最近鄰的類別；（5）根據(jù)K個(gè)最近鄰，給每一個(gè)類別打分；其中，為閾值。（6）分值最大的類別即為測試文本的類別。本節(jié)將重點(diǎn)介紹本文所研究的基于半監(jiān)督的文本分類算法，對算法思想、算法步驟、算法的具體操作及算法的效率都做了詳細(xì)的介紹。前面已經(jīng)介紹了，文本分類需要大量的數(shù)據(jù)集進(jìn)行訓(xùn)練。然而在眾多訓(xùn)練集中，得到有標(biāo)記的數(shù)據(jù)是非常困難的，且費(fèi)時(shí)費(fèi)力；但未標(biāo)記的數(shù)據(jù)卻很容易就能得到。故現(xiàn)在文本分類大部分都是應(yīng)用的半監(jiān)督算法，以標(biāo)記數(shù)據(jù)為主，未標(biāo)記數(shù)據(jù)為輔來不斷完善分類器。然而就是因?yàn)閹?biāo)記數(shù)據(jù)比較難得到，數(shù)據(jù)非常少，從而可能造成前期訓(xùn)練分類器時(shí)出現(xiàn)錯(cuò)誤，如圖41示：圖41 分類示圖其中，實(shí)心為已標(biāo)記數(shù)據(jù)，空心為未標(biāo)記數(shù)據(jù)，三角形和圓形代表兩類。虛線代表可能造成的錯(cuò)誤分類，實(shí)線為正確的分類。如圖41，在分類中由于標(biāo)記數(shù)據(jù)非常少，很可能造成如“虛線”一般的錯(cuò)誤分類。本文所研究的基于半監(jiān)督的分類算法就是為解決此類問題，盡可能減少錯(cuò)誤的分類，從而提高分類器的性能。本章所研究的算法思想是：先根據(jù)標(biāo)記數(shù)據(jù)進(jìn)行聚類，計(jì)算每類的中心點(diǎn)，用新的中心點(diǎn)和未聚類文本組成新的訓(xùn)練集，然后用新的訓(xùn)練集進(jìn)行分類?；舅枷肴鐖D42所示，圖中兩個(gè)多邊形代表聚類結(jié)果，其它的與圖41相同。圖42 聚類分類圖根據(jù)以上所述，本文所研究的基于半監(jiān)督的文本分類算法就是先對數(shù)據(jù)集進(jìn)行聚類之后，然后在應(yīng)用半監(jiān)督分類算法進(jìn)行分類。如此可以很大的提高分類器的性能。本章所研究的基于EM算法的聚類數(shù)據(jù)集是基于高斯混合模型的。故本節(jié)將分別介紹高斯混合模型和聚類EM算法。[32][33]（1）高斯混合模型假設(shè)有一系列觀測值由某混合分布產(chǎn)生，該分布又是由個(gè)成分構(gòu)成，每一個(gè)成分都代表一個(gè)不同的類別(cluster)。假設(shè)觀測樣本，每個(gè)向量都是維的。表示是第類的密度函數(shù)，是相應(yīng)的參數(shù)。表示某一觀察值屬于第類的概率，即權(quán)重。最大化混合似然函數(shù)： （47）如果是多元正態(tài)分布，即高斯分布，則此混合聚類的模型即為高斯混合模型(GMM)，個(gè)成分即個(gè)獨(dú)立的高斯分布。參數(shù)由均值和協(xié)方差矩陣組成。密度函數(shù)如下： (48)該分布可由個(gè)高斯密度函數(shù)的加權(quán)平均所表示的概率密度函數(shù)描述如下： (49)（2）聚類的EM算法假設(shè)存在一個(gè)完整數(shù)據(jù)集，是不完整的數(shù)據(jù)集，是引入的隱含變量。，是給定的有限整數(shù)。于是則完整數(shù)據(jù)的似然函數(shù)為： (410)該似然函數(shù)的期望值： (411)采用EM算法的基本思想是對于上述的不完整數(shù)據(jù)集，假設(shè)這些數(shù)據(jù)獨(dú)立同分布于我們已知的某一個(gè)模型，如GMM，而我們知道該模型的參數(shù)，因此可以根據(jù)該模型推出屬于每個(gè)成分的各數(shù)據(jù)點(diǎn)的概率，然后修改每個(gè)成分的值，重復(fù)該過程直到收斂到結(jié)束條件。Estep： (412)顯然，輔助函數(shù)的值就是的期望值，并且是的函數(shù)，是上一步迭代運(yùn)算求得的參數(shù)值。Mstep: (413)求解，使得得到極大值?？梢钥闯觯S機(jī)向量的分布是由和決定的，若表示第次迭代的最大似然函數(shù)值，表示第次迭代的最大似然函數(shù)值，可知證明，EM算法能夠保證，并且算法是收斂的。高斯混合模型(GMM)里，假設(shè)完整數(shù)據(jù)為，為可觀測變量，為隱含變量， (414)設(shè)是獨(dú)立同分布于類，其概率分別為，并且由給出的的密度為：。完整數(shù)據(jù)的似然函數(shù)為： （415）算法是在Estep和Mstep之間迭代。在Estep，由可觀測變量和當(dāng)前的參數(shù)估計(jì)，計(jì)算出完整數(shù)據(jù)似然的條件期望值。Mstep中，根據(jù)Estep的值，計(jì)算使得似然函數(shù)值最大的參數(shù)估計(jì)。，但此Knn算法分類是在前期EM算法對訓(xùn)練集聚類分析的基礎(chǔ)上進(jìn)行操作的。具體步驟如下：（1）根據(jù)EM算法的聚類結(jié)果，對每一類計(jì)算出其中心點(diǎn)；（2）在眾多中心點(diǎn)中選出與新文檔最相似的K個(gè)中心點(diǎn)，公式為：其中，K 值的確定目前還沒有很好的方法，一般采用先定一個(gè)初始值，然后根據(jù)實(shí)驗(yàn)測試的結(jié)果調(diào)整 K值。（3）在新文本的 K 個(gè)鄰居中依次計(jì)算每類的權(quán)重，公式為：其中，為新文本分特征向量，為相似度計(jì)算公式，與上一步的計(jì)算公式相同，而為類別屬性函數(shù)，即如果屬于，那么函數(shù)值為1，否則為零。（4）比較類的權(quán)重，將文本分到權(quán)重最大的那個(gè)類別中。 針對以上兩節(jié)提出的EM算法和KNN算法，本文將二者結(jié)合在一起提出了一種基于EM和KNN的半監(jiān)督文本分類算法，算法流程如圖43示：圖43e 新文檔所屬類別圖43a 樣本點(diǎn)原始分布圖43c 樣本中的中心點(diǎn)圖43b 聚類后的結(jié)果圖43d 新文檔與中心點(diǎn)之間的歐幾里得距離圖43 算法步驟流程其中，紅色圓點(diǎn)為標(biāo)示樣本，黑色為類別中心點(diǎn)，三角為待分類樣本。由上圖可以十分清楚的了解到分類算法的步驟，具體如下：假設(shè)有一個(gè)訓(xùn)練集，類別，每個(gè)類別中有若干個(gè)訓(xùn)練樣本。（1）對訓(xùn)練集中的文檔進(jìn)行預(yù)處理，得到圖43a的樣本點(diǎn)分布；（2）根據(jù)標(biāo)示樣本應(yīng)用EM算法進(jìn)行聚類，圖43b所示；（3）計(jì)算聚類后每類的中心點(diǎn)，中心點(diǎn)與未聚類樣本組成新的訓(xùn)練集，圖43c所示；（4）計(jì)算新文檔與中心點(diǎn)和其它樣本點(diǎn)之間的歐幾里距離；如，兩點(diǎn)和的歐幾里德距離是：，圖43d所示；（5）將新文檔分到距離最近的類中，圖43e所示。算法效率的分析也就是對算法時(shí)間復(fù)雜度的分析，而一個(gè)算法的質(zhì)量優(yōu)劣將直接受算法乃至程序效率的影響。本文算法是在EM算法聚類的基礎(chǔ)上應(yīng)用KNN算法進(jìn)行文本分類的，故在此將分別對EM算法聚類和KNN算法分類的效率進(jìn)行分析。（訓(xùn)練文檔集數(shù)目）個(gè)對象進(jìn)行層次聚類的平均復(fù)雜度為,最壞復(fù)雜度為?？紤]到特征的因素，在個(gè)特征詞構(gòu)成的空間中，對個(gè)文檔特征矢量進(jìn)行聚類的平均復(fù)雜度為,最壞復(fù)雜度為。也就是說EM算法聚類的最小復(fù)雜度為,與訓(xùn)練集數(shù)目的平方值有關(guān)。KNN算法本身簡單有效，它是一種lazylearning算法，分類器不需要使用訓(xùn)練集進(jìn)行訓(xùn)練，訓(xùn)練時(shí)間復(fù)雜度為0。而KNN分類的計(jì)算復(fù)雜度和訓(xùn)練集中的文檔數(shù)目成正比，也就是說，如果訓(xùn)練集中文檔總數(shù)為，那么KNN的分類時(shí)間復(fù)雜度為。 綜上所述，如有一文檔數(shù)為的訓(xùn)練集，用經(jīng)典KNN算法分類，則其分類時(shí)間復(fù)雜度為。而如果用本文算法分類，設(shè)聚類后形成的新的訓(xùn)練集文檔數(shù)為，其中，則其分類時(shí)間復(fù)雜度為。由此知，在分類時(shí)間復(fù)雜度上本文算法優(yōu)于經(jīng)典的KNN算法。但經(jīng)典的KNN算法不需要使用訓(xùn)練集進(jìn)行訓(xùn)練，訓(xùn)練時(shí)間復(fù)雜度為0。而本文算法需要先對訓(xùn)練集聚類，而聚類的平均復(fù)雜度為。由此可知，本文算法在前期準(zhǔn)備工作上稍有欠缺。本章首先介紹了EM半監(jiān)督學(xué)習(xí)算法以及KNN文本分類算法，然后在此基礎(chǔ)之上提出了基于EM和KNN的半監(jiān)督的文本分類算法，最后重點(diǎn)研究了該算法的具體實(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++ 。（1）算法實(shí)現(xiàn)本文所研究的EMKNN算法是通過VC++編程實(shí)現(xiàn)的。算法中的EM聚類和KNN分類都很好的通過C++語言編程實(shí)現(xiàn)。算法界面如圖51示：圖51 聚類界面以上界面是聚類的實(shí)現(xiàn)，對訓(xùn)練樣本進(jìn)行聚類，其基本偽代碼為： 輸入：訓(xùn)練樣本的向量集； 初始假設(shè)：協(xié)方差矩陣為單位陣，先驗(yàn)概率為整體均值； 計(jì)算：協(xié)方差矩陣，聚類中心； 最大化：最大化高斯模型中的權(quán)重、均值、協(xié)方差； 迭代：不斷迭代E和M步驟； 輸出：向量類別期望矩陣、聚類中心、協(xié)方差矩陣。最終聚類結(jié)果如圖52示：圖52 聚類結(jié)果圖53所示界面為分類界面：圖53 分類界面在聚類基礎(chǔ)上，對測試文本進(jìn)行