曾依靈，許洪波，吳高巍，程學(xué)旗，白 碩,2

(1. 中國(guó)科學(xué)院 計(jì)算技術(shù)研究所，北京 100190； 2. 上海證券交易所，上海 200120)

1 引言

隨著互聯(lián)網(wǎng)內(nèi)容的指數(shù)增長(zhǎng)，對(duì)有效管理大規(guī)模文檔的需求日益急切。聚類作為一種重要的文本分析方法，已在信息檢索領(lǐng)域得到了廣泛應(yīng)用：它被用于加速信息檢索過(guò)程[1]，提高信息檢索系統(tǒng)的準(zhǔn)確率和召回率[2]，組織用戶的查詢結(jié)果[3]等。然而，聚類算法的性能常常受到模型不匹配問(wèn)題的影響：大部分聚類算法都基于一些潛在的模型假設(shè)，當(dāng)語(yǔ)料特性恰好滿足聚類算法的模型假設(shè)時(shí)算法性能良好，反之性能欠佳。

通常，解決模型不匹配問(wèn)題可以采取兩種策略：1)調(diào)整算法模型以適應(yīng)語(yǔ)料分布[5-6]； 2)通過(guò)變換特征空間以修正文本表示層的固有問(wèn)題[1,7]。其中，第一種策略通常需要基于訓(xùn)練錯(cuò)誤進(jìn)行算法修正，因此主要應(yīng)用于分類算法之中，通常這類策略只能對(duì)訓(xùn)練錯(cuò)誤發(fā)生的區(qū)域進(jìn)行局部修正，容易忽略語(yǔ)料分布的全局特性；第二種策略通過(guò)空間變換以解決當(dāng)前表示空間的固有問(wèn)題，然而，空間變換往往立足于自身的假設(shè)，這些假設(shè)與算法模型未必一致，因此空間變換的性能也會(huì)有所折扣。在本文中，我們提出的解決框架也可以看作是一種空間變換，但與以前的空間變換不同，該框架根據(jù)算法的模型假設(shè)進(jìn)行空間變換，以使變換后的語(yǔ)料分布更適應(yīng)當(dāng)前算法。

本文提出的解決框架被稱作M-R框架，具體而言，它是一種基于空間映射(Mapping)及尺度變換(Rescaling)的聚類解決框架。該解決框架統(tǒng)計(jì)類簇的分布特性并根據(jù)算法的模型假設(shè)對(duì)其進(jìn)行歸一化，以提升聚類性能。具體而言，M-R框架包含如下兩步：

Step1.空間映射(Mapping)：由于文本空間具有高維稀疏特性，在原空間進(jìn)行語(yǔ)料分布特性統(tǒng)計(jì)難以操作。我們選擇首先將語(yǔ)料映射到一個(gè)低維空間，該低維空間由一組具有區(qū)分度的方向構(gòu)成，并且具有適合分布特性統(tǒng)計(jì)的良好特性。

Step2.尺度變換(Rescaling)：根據(jù)統(tǒng)計(jì)而得的語(yǔ)料分布特性，我們構(gòu)造尺度變換函數(shù)，并以尺度變換的方式歸一化語(yǔ)料分布，以使語(yǔ)料分布更加契合算法的模型假設(shè)，從而在此之上的聚類策略也更加合理。

對(duì)于給定的聚類算法，如上兩步通過(guò)與算法相互迭代的方式以提高聚類性能，直至達(dá)到算法的最終收斂。本文將M-R框架應(yīng)用到了經(jīng)典的K-means算法及近年的研究熱點(diǎn)譜聚類算法上，并最后在國(guó)際標(biāo)準(zhǔn)語(yǔ)料集上驗(yàn)證M-R框架的實(shí)際性能。

本文后續(xù)章節(jié)結(jié)構(gòu)如下：在第2節(jié)中，我們首先分析不同聚類算法的隱含假定并介紹關(guān)于模型不匹配的已有研究，在第3節(jié)中，我們?cè)敿?xì)介紹M-R框架，在第4節(jié)中，我們將M-R框架應(yīng)用到K-means及譜聚類上，在第5節(jié)中，我們通過(guò)實(shí)驗(yàn)驗(yàn)證M-R框架所帶來(lái)的性能提升，并在第6節(jié)中對(duì)全文進(jìn)行總結(jié)。

2 相關(guān)工作

聚類是一個(gè)被廣泛研究了40多年的經(jīng)典問(wèn)題[4]，并形成了一系列的經(jīng)典聚類算法。這些算法建立在不同的模型假設(shè)之上：層次式聚類的基本假定是，任何的聚類簇都是由更小的、在語(yǔ)義上類似的子簇或者子話題構(gòu)成。劃分式聚類，以K-means為例，則認(rèn)為各個(gè)簇滿足方差相同的、各向同性的高斯分布。由此，在空間特性上，不同簇分布在半徑相同的球形區(qū)域內(nèi)?；诿芏鹊木垲惡突诰W(wǎng)格的聚類則關(guān)注于語(yǔ)料分布的局部特征(如在某個(gè)鄰域或空間小單元內(nèi)的分布特征)，并用這些特征進(jìn)行聚類判別。

值得單獨(dú)一提的是近些年研究較熱的譜聚類算法[8]。譜聚類的基本思想是將整個(gè)語(yǔ)料看作一個(gè)加權(quán)圖，并用圖劃分的方式最優(yōu)化給定的劃分權(quán)重(如Normalized Cut[9]，Ratio Cut[10]，Min-Max Cut[11]等)，以將語(yǔ)料劃成一個(gè)個(gè)聚類。這些最優(yōu)化劃分目標(biāo)可以通過(guò)特征分解的方式獲得，并保證全局最優(yōu)，因此譜聚類的性能往往好過(guò)傳統(tǒng)聚類算法。從表面上看，譜聚類對(duì)語(yǔ)料分布未作任何限定，并有能力區(qū)分不同形狀的簇，但這必須建立在一個(gè)前提之上——圖的劃分必須較好地吻合簇與簇的邊界。然而，如果譜聚類求解出的圖劃分不能較好地反映簇與簇的邊界，同樣會(huì)導(dǎo)致模型不匹配問(wèn)題的產(chǎn)生。

事實(shí)上，聚類算法的理想假定或多或少與實(shí)際語(yǔ)料的真實(shí)分布有所偏差(第3節(jié)將以實(shí)例分析這些偏差產(chǎn)生的原因)。因此。模型不匹配問(wèn)題成為文本挖掘領(lǐng)域的一個(gè)常見(jiàn)問(wèn)題。為解決這個(gè)問(wèn)題，研究人員在如下兩個(gè)方面尋求各種解決途徑。

一方面的解決途徑是通過(guò)修正算法模型來(lái)適應(yīng)語(yǔ)料分布。這方面的研究通常需要基于訓(xùn)練錯(cuò)誤進(jìn)行，因此集中在分類領(lǐng)域。典型的研究有：Wu等[5]根據(jù)訓(xùn)練錯(cuò)誤，用同樣的學(xué)習(xí)方法對(duì)每一個(gè)類的訓(xùn)練樣本重新訓(xùn)練一個(gè)子分類器，強(qiáng)迫子分類器根據(jù)訓(xùn)練語(yǔ)料學(xué)習(xí)需要修正的區(qū)域，從而使得分類模型更適應(yīng)當(dāng)前語(yǔ)料特征。Tan[6]則提出一種簡(jiǎn)潔有效的“拉推”策略，通過(guò)在線修正分類模型的方式以提高分類結(jié)果，使被錯(cuò)分的文檔也就更容易被重新分到正確的類中。在聚類領(lǐng)域，由于無(wú)法通過(guò)標(biāo)簽獲取信息，關(guān)于模型不匹配問(wèn)題的研究較為罕見(jiàn)?？偟亩?，這一類的研究通過(guò)局部修正來(lái)提高性能，但容易忽略語(yǔ)料的全局分布。

另一方面的解決途徑是通過(guò)空間映射以使原空間的相關(guān)問(wèn)題在新空間能得以恰當(dāng)?shù)慕鉀Q。典型的研究有：Dumais[1]認(rèn)為VSM模型的一大問(wèn)題是用非獨(dú)立的詞(term)作為獨(dú)立的空間維度，于是他們提出LSI以解決此問(wèn)題導(dǎo)致的空間缺陷，通過(guò)LSI分解，文檔與文檔以及詞與詞的相關(guān)性能在k維表示下進(jìn)行恰當(dāng)?shù)挠?jì)算。核方法[7]是另一種通過(guò)空間變換來(lái)解決問(wèn)題的重要方法，此類方法通過(guò)核函數(shù)k(x,y) =φ(x)·φ(y)來(lái)尋求一種隱式的空間映射φ，使得在新的空間中問(wèn)題更易解。大致而言，這一類研究專注于解決當(dāng)前特征空間的固有問(wèn)題，其中大部分研究并未考慮算法的固有假定，而空間變換往往意味著較高的時(shí)間復(fù)雜度和較大的存貯空間。

在下一節(jié)中，我們提出自己的解決框架，面向算法模型所期望的語(yǔ)料分布進(jìn)行空間變換，以提升聚類性能。

3 M-R框架

3.1 聚類中的模型不匹配問(wèn)題

本節(jié)首先以一個(gè)語(yǔ)料為例，分析其在不同算法假設(shè)下所遭遇的模型不匹配問(wèn)題。如下圖所示，假定給定的語(yǔ)料集中存在兩個(gè)固有簇，固有簇中的點(diǎn)分別由“+”和“○”標(biāo)識(shí)，并由虛線圈出。標(biāo)為“+”的點(diǎn)分布在一個(gè)狹長(zhǎng)的橢球形區(qū)域內(nèi)，而標(biāo)為“○”的點(diǎn)分布在一個(gè)標(biāo)準(zhǔn)的球形區(qū)域內(nèi)。

圖1 K-means的模型不匹配問(wèn)題

圖2 譜聚類的模型不匹配問(wèn)題

如果我們選擇K-means算法對(duì)語(yǔ)料進(jìn)行聚類(如圖1所示)，顯然，語(yǔ)料的分布特征破壞了K-means關(guān)于不同簇分布在半徑相同的球形區(qū)域內(nèi)的理想假設(shè)。K-means將按照自己的假設(shè)對(duì)語(yǔ)料進(jìn)行劃分，即沿圖中實(shí)線標(biāo)識(shí)的球形將所有點(diǎn)分成兩個(gè)簇。于是，部分標(biāo)記為“+”的點(diǎn)被錯(cuò)誤地與標(biāo)記為“○”的點(diǎn)劃分在了一起。該錯(cuò)誤劃分是如何產(chǎn)生的？根據(jù)K-means的決策準(zhǔn)則，一個(gè)數(shù)據(jù)點(diǎn)將被放到最近的簇中。以圖中的x為例，假定x到cluster1的簇中心的距離為d1，到cluster2的簇中心的距離為d2。盡管x屬于標(biāo)記為“+”的固有簇，由于d2

如果我們選擇譜聚類對(duì)語(yǔ)料進(jìn)行聚類(如圖2所示)，譜聚類將計(jì)算出最優(yōu)的劃分對(duì)語(yǔ)料進(jìn)行分割。為簡(jiǎn)化分析過(guò)程，我們假設(shè)譜聚類將語(yǔ)料轉(zhuǎn)化成圖表示時(shí)進(jìn)行了鄰域限制，同時(shí)，圖中點(diǎn)與點(diǎn)的權(quán)重采用譜聚類中最常使用的高斯相似度，即s(xi,xj)=exp(-‖xi-xj‖2/2σ2)。同樣以點(diǎn)x為例，其有效鄰域內(nèi)有4個(gè)點(diǎn)，分別標(biāo)記為a，b，c，d。從圖中可以看出，dxa>dxc，dxb>dxd。根據(jù)高斯相似度的定義可知s(x,a)

同一個(gè)語(yǔ)料，面對(duì)不同的聚類算法皆產(chǎn)生了模型不匹配問(wèn)題。表面上看，這是面對(duì)不同模型假設(shè)所產(chǎn)生的不同的模型不匹配問(wèn)題。但從本質(zhì)上，這其實(shí)是同一個(gè)問(wèn)題：語(yǔ)料中各個(gè)簇的不同形狀和尺度導(dǎo)致距離度量無(wú)法較好地反映數(shù)據(jù)點(diǎn)的類別歸屬。假定我們已經(jīng)知道了語(yǔ)料中各個(gè)簇的分布特征，并根據(jù)這個(gè)分布特征進(jìn)行空間變換，比如，將左邊橢球形的簇轉(zhuǎn)化成和右邊一樣的標(biāo)準(zhǔn)球形區(qū)域。那么，距離度量在新的場(chǎng)景下將發(fā)生改變：對(duì)于圖1將使得d1

3.2 基本原理

基于如上對(duì)模型不匹配問(wèn)題的分析，為了使距離度量更為合理，可以將每一個(gè)類簇根據(jù)分布特性進(jìn)行空間變換。然而，文本空間的維度災(zāi)難問(wèn)題和數(shù)據(jù)稀疏特性使得這樣的變換不切實(shí)際。對(duì)此，我們先將語(yǔ)料映射到一組具有區(qū)分度的方向構(gòu)成的一個(gè)新坐標(biāo)系中。

在上述最優(yōu)化準(zhǔn)則中，需要同時(shí)對(duì)類間離散度和類內(nèi)離散度進(jìn)行最優(yōu)化。而在我們提出的解決框架中，構(gòu)建新的坐標(biāo)系之后將進(jìn)一步根據(jù)固有簇的特征執(zhí)行尺度變換操作，尺度變換以隱式映射的方式對(duì)不同簇的分布進(jìn)行歸一化，以使距離度量更為合理。這種隱式的歸一化旨在消除不同簇分布上的差異。于是，在歸一化的場(chǎng)景下，類內(nèi)離散度這個(gè)反映類內(nèi)數(shù)據(jù)點(diǎn)散布程度的指標(biāo)得以相應(yīng)的規(guī)范，由類內(nèi)離散度造成的區(qū)分度影響也大為降低。因此，在求解具有區(qū)分度方向的過(guò)程中，我們將優(yōu)化準(zhǔn)則函數(shù)簡(jiǎn)化，忽略類內(nèi)離散度，僅考慮類間離散度，最優(yōu)化準(zhǔn)則函數(shù)變?yōu)椋?/p>

(1)

根據(jù)與Fisher判別類似的推導(dǎo)過(guò)程，最優(yōu)矩陣W的列向量可以通過(guò)求解SB的最大特征值對(duì)應(yīng)的特征向量，即求解SBwi=λiwi而得到。由SB的定義知，這些特征向量所張成的空間就是向量mi-m(1≤i≤k)張成的空間，因此，我們不妨直接選擇mi-m(1≤i≤k)構(gòu)成一個(gè)新的坐標(biāo)系。

(2)

因此，M-R坐標(biāo)系的每一個(gè)方向?qū)?yīng)著一個(gè)固有簇，該方向能以最大化類間離散度的方式區(qū)分當(dāng)前簇和其他簇。于是，在進(jìn)一步的尺度變換操作中，對(duì)于每一個(gè)方向，可用對(duì)應(yīng)簇的相關(guān)特征作為該維度上尺度變換操作的重要參照。

定義2(M-R距離)：假定M-R坐標(biāo)系下各個(gè)坐標(biāo)軸對(duì)應(yīng)的尺度變換函數(shù)分別為R1(·),…,Ri(·),…,Rk(·)，那么，其下的距離函數(shù)可寫(xiě)為：

(3)

公式(3)給出了M-R坐標(biāo)系中距離的一般形式。根據(jù)語(yǔ)料中固有簇的分布特征，我們可以采取不同的尺度變換函數(shù)，以使公式(3)給出的距離更為合理。尺度變換函數(shù)可以取線性函數(shù)，也可以取非線性函數(shù)。如果尺度變換函數(shù)為線性函數(shù)，也就是說(shuō)，Ri(·)的形式為Ri(x)=ξix+i，那么公式(3)可以進(jìn)一步寫(xiě)為：

(4)

其中，ξi(1≤i≤k)可看作各個(gè)坐標(biāo)軸的尺度變換系數(shù)，通過(guò)它對(duì)各個(gè)維度的坐標(biāo)值進(jìn)行擴(kuò)放或者收縮，以使各個(gè)維度的標(biāo)度更具有可比性。

我們期望各個(gè)坐標(biāo)軸有著可比較的標(biāo)度，也就是說(shuō)，各個(gè)坐標(biāo)軸上點(diǎn)的分布有著大致相當(dāng)?shù)某叨?。一個(gè)較為直觀合理的解決方式是，用一個(gè)與各個(gè)坐標(biāo)軸數(shù)據(jù)點(diǎn)分布尺度相關(guān)的統(tǒng)計(jì)量作為該坐標(biāo)軸的尺度變換系數(shù)。在所有的統(tǒng)計(jì)量中，標(biāo)準(zhǔn)差是一個(gè)反映一組數(shù)據(jù)散布尺度的統(tǒng)計(jì)量。因此，我們可以計(jì)算對(duì)應(yīng)簇在當(dāng)前坐標(biāo)軸上投影分布的標(biāo)準(zhǔn)差，并將其倒數(shù)作為當(dāng)前坐標(biāo)軸的尺度變換系數(shù)，即ξi=1/σi，以使各個(gè)軸語(yǔ)料的散布尺度趨于一致。于是，公式(4)可以表示如下

(5)

其中

(6)

通過(guò)以標(biāo)準(zhǔn)差為倒數(shù)的尺度變換函數(shù)，各個(gè)簇在對(duì)應(yīng)坐標(biāo)軸上的投影實(shí)現(xiàn)了等方差的歸一化，各個(gè)坐標(biāo)軸由此而具有更為可比的尺度，基于此尺度的距離計(jì)算也更為合理。值得指出的是，本文采用的標(biāo)準(zhǔn)差倒數(shù)只是眾多尺度變換函數(shù)中的一個(gè)特例，我們完全可以根據(jù)語(yǔ)料的特定分布情況構(gòu)造各種更精細(xì)更合理的尺度變換函數(shù)，以使語(yǔ)料能夠更好地轉(zhuǎn)化到更為理想的形式。

3.3 基本框架

當(dāng)前一個(gè)未解決的重要問(wèn)題是：我們?nèi)绾潍@取固有簇的信息？由于沒(méi)有類別標(biāo)簽，我們無(wú)法獲取固有簇的精確劃分。然而，如果能獲得一個(gè)大致反應(yīng)固有簇分布的初始劃分，我們依舊能夠粗略統(tǒng)計(jì)出反映各個(gè)簇分布特性的尺度變換系數(shù)。因此，我們的解決方案是，調(diào)用給定的算法獲得一個(gè)初始劃分，將其作為M-R算法的輸入。根據(jù)該初始劃分，可建立M-R坐標(biāo)系，并計(jì)算出各個(gè)軸的尺度變換系數(shù)，根據(jù)M-R距離得到更為合理的劃分結(jié)果。在新劃分結(jié)果的基礎(chǔ)上，可繼續(xù)構(gòu)造出更為合理的M-R坐標(biāo)系并計(jì)算出更為準(zhǔn)確的尺度變換系數(shù)，并再一次進(jìn)行更為精細(xì)的重劃分。為此，我們將迭代策略引入了M-R算法。通過(guò)迭代，能夠促使聚類結(jié)果和M-R坐標(biāo)系相互修正，并最終獲得一個(gè)令人滿意的聚類結(jié)果。

我們可以將M-R框架按如下方式應(yīng)用到給定聚類算法上：

1) 調(diào)用給定聚類算法產(chǎn)生一個(gè)初始劃分；

2) 根據(jù)當(dāng)前劃分構(gòu)造M-R坐標(biāo)系，并計(jì)算各個(gè)坐標(biāo)軸的尺度變換系數(shù):

3) 在M-R坐標(biāo)系下用M-R距離調(diào)用給定聚類算法生成新的聚類劃分:

4) 判斷迭代停止條件是否滿足，如果否，轉(zhuǎn)2，如果是，輸出結(jié)果。

4 基于M-R框架的聚類算法

本節(jié)我們將M-R框架應(yīng)用到兩個(gè)典型的聚類算法上：經(jīng)典的K-means算法與近年的研究熱點(diǎn)譜聚類算法，以證明M-R框架的與不同聚類算法結(jié)合的普適性。

4.1 M-R K-means

我們將M-R框架應(yīng)用到傳統(tǒng)的K-means算法上，得到M-R K-means算法。對(duì)于一個(gè)含有n篇文檔的語(yǔ)料M-R K-means算法流程如下：

1) 調(diào)用K-means算法進(jìn)行r次迭代，以生成一個(gè)含有k個(gè)簇的粗糙劃分；

2) 根據(jù)當(dāng)前劃分更新M-R坐標(biāo)系，同時(shí)更新各個(gè)坐標(biāo)系的尺度變換系數(shù)；

3) Fori=1 tokdo

3.1 計(jì)算xi在M-R坐標(biāo)系中的坐標(biāo)值；

3.2 根據(jù)M-R距離將xi劃入最近的簇中；

4) 重復(fù)2)-3)直到停止條件達(dá)到。

算法中，參數(shù)r控制K-means迭代次數(shù)，為保證初始劃分的迅速產(chǎn)生，r的取值通常很小(r=2或3)。顯然，第一步中，通過(guò)K-means迭代產(chǎn)生初始劃分的時(shí)間復(fù)雜度為O(krn)，其中k為簇的個(gè)數(shù)，r為迭代次數(shù)，n為數(shù)據(jù)點(diǎn)的個(gè)數(shù)。在M-R K-means的每一次迭代中，存在三種主要運(yùn)算：重新構(gòu)建M-R坐標(biāo)系，計(jì)算每個(gè)點(diǎn)在新M-R坐標(biāo)系下的坐標(biāo)，以及根據(jù)M-R距離公式計(jì)算點(diǎn)到所有簇中心的距離。每次新的迭代都將重新構(gòu)建M-R坐標(biāo)系，對(duì)于每個(gè)坐標(biāo)軸，都需要計(jì)算語(yǔ)料中心到簇中心的歸一化向量，所需時(shí)間為O(k)；接著，需要計(jì)算所有點(diǎn)在新M-R坐標(biāo)系下的坐標(biāo)，對(duì)于每個(gè)點(diǎn)，將根據(jù)公式(2)計(jì)算k個(gè)點(diǎn)乘，因此，計(jì)算所有點(diǎn)的M-R坐標(biāo)的時(shí)間復(fù)雜度為O(kn)。接著將在M-R坐標(biāo)系下根據(jù)公式(5)計(jì)算所有點(diǎn)到簇中心的M-R距離，由于每個(gè)距離計(jì)算只涉及k維，相比于原始空間，維度大為降低，因此，相比于前面的高維計(jì)算，這部分的計(jì)算量可以省略。將三部分運(yùn)算匯總，一次迭代的總運(yùn)算量為：O(k)+O(kn)=O(kn)。假定M-R K-means總的迭代次數(shù)為T(包括用K-means產(chǎn)生初始劃分的r次迭代)，M-R K-means聚類算法的時(shí)間復(fù)雜度為O(knT)。可見(jiàn)，M-R K-means聚類算法的時(shí)間復(fù)雜度保持在與K-means算法同一量級(jí)。

4.2 M-R Ncut

譜聚類系列算法中，我們選擇具有代表性的Normalized Cut(即 Ncut)算法[9]，并將M-R框架應(yīng)用到其上。然而，在Ncut算法中，構(gòu)造鄰接矩陣用的是高斯相似度，我們所要解決的問(wèn)題是，如何將M-R坐標(biāo)系及定義在其上的M-R距離與高斯相似度統(tǒng)一起來(lái)。不難發(fā)現(xiàn)，高斯相似度其實(shí)是基于高斯核的窗函數(shù)應(yīng)用到歐式距離上的結(jié)果：s(xi,xj)=exp (-‖xi-xj‖2/2σ2)=exp (-d(xi,xj)2/2σ2)。因此，在M-R坐標(biāo)系下，我們只需要將高斯相似度中的歐氏距替換成M-R距離即可。也就是說(shuō)，M-R坐標(biāo)系下的高斯相似度可類似地定義為：sM-R(xi,xj)=exp(-dM-R(xi,xj)2/2σ2)。M-R Ncut算法流程如下：

1) 調(diào)用Ncut算法一次以獲得一個(gè)初始劃分；

2) 根據(jù)當(dāng)前劃分更新M-R坐標(biāo)系，同時(shí)更新各個(gè)坐標(biāo)系的尺度變換系數(shù)；

3) 根據(jù)M-R坐標(biāo)系下的高斯相似度計(jì)算譜聚類中的鄰接矩陣；

4) 根據(jù)該鄰接矩陣再次調(diào)度Ncut算法生成新的聚類結(jié)果；

5) 重復(fù)2)-4)直到停止條件達(dá)到。

無(wú)論是一開(kāi)始調(diào)用Ncut算法獲取初始劃分還是在M-R坐標(biāo)系下迭代執(zhí)行Ncut算法，都需要對(duì)一個(gè)n×n的矩陣進(jìn)行特征分解，相對(duì)于特征分解的時(shí)間復(fù)雜度，計(jì)算鄰接矩陣，以及在特征向量張成空間中進(jìn)行K-means聚類的時(shí)間復(fù)雜度皆可忽略。因此，如果M-R Ncut算法共調(diào)用Ncut進(jìn)行了T次迭代，M-R Ncut的時(shí)間復(fù)雜度則是Ncut的T倍。

5 實(shí)驗(yàn)結(jié)果

5.1 語(yǔ)料集

在本節(jié)的實(shí)驗(yàn)中，我們將用到兩個(gè)國(guó)際標(biāo)準(zhǔn)文本語(yǔ)料庫(kù)：RCV1-v2[14]及20Newsgroup*http://www.ai.mit.edu/people/jrennie/20Newsgroups/。

RCV1-v2該語(yǔ)料集包含人工采集的來(lái)自路透社的800 000余篇新聞專線語(yǔ)料，存貯在103個(gè)類別中。我們從RCV1-v2中隨機(jī)地挑選類別及文檔，構(gòu)造出了一系列的測(cè)試語(yǔ)料集：R1、R2、R3、R4和R5，它們的類別數(shù)從7類到15類不等，文檔數(shù)從1 932到3 330不等。

20Newsgroup該語(yǔ)料集包含了來(lái)自20個(gè)Usenet新聞組中的20 000篇文章，每個(gè)類別1 000篇。我們隨機(jī)挑選20Newsgroup中的類別及文檔，構(gòu)造出了一系列測(cè)試語(yǔ)料集N1、N2、N3、N4和N5，它們的類別數(shù)從6類到15類不等，文檔數(shù)從2 112到3 406不等。

我們所構(gòu)造的兩個(gè)系列的測(cè)試語(yǔ)料集的概況如表1所示。在這兩個(gè)系列的語(yǔ)料上，我們都保持了類別數(shù)和文檔數(shù)的跨度，其原因是我們想觀察M-R框架在不同尺度的語(yǔ)料集上的性能。我們將這10個(gè)測(cè)試語(yǔ)料集轉(zhuǎn)換成歸一化的VSM向量矩陣，以供進(jìn)一步的實(shí)驗(yàn)之用。

表1 實(shí)驗(yàn)語(yǔ)料概況

5.2 評(píng)價(jià)指標(biāo)

聚類算法的評(píng)價(jià)指標(biāo)多種多樣，包括準(zhǔn)確率、召回率、F-Measure，熵等。其中最為常用的是F-Measure和熵[15]。

F-Measure將準(zhǔn)確率和召回率結(jié)合在一起。對(duì)于語(yǔ)料集中的任何一個(gè)類，F(xiàn)-Measure尋找聚類結(jié)果中與其最相似的簇，根據(jù)該簇計(jì)算該類的準(zhǔn)確率、召回率及F-Measure。而整個(gè)語(yǔ)料集的F-Measure由所有類的F-Measure加權(quán)而得，其中，權(quán)值是該類在語(yǔ)料集中的比重。

熵是一種衡量聚類簇純度的指標(biāo)，值越小表明聚類結(jié)果純度越大。當(dāng)所有簇的純度都最高時(shí)，熵值最佳。需要注意的是，當(dāng)所有簇都僅包含一個(gè)文檔時(shí)熵值亦達(dá)到最佳值。整個(gè)語(yǔ)料的熵值由聚類結(jié)果中所有簇的熵值加權(quán)累加產(chǎn)生，權(quán)值是該簇在聚類結(jié)果中的比重。

5.3 M-R框架性能

為了驗(yàn)證M-R框架的真實(shí)性能，我們?cè)谇拔乃鶚?gòu)建的10個(gè)語(yǔ)料集上運(yùn)行K-means，M-R K-means，Ncut及M-R Ncut算法并比較它們的實(shí)驗(yàn)結(jié)果。實(shí)驗(yàn)中的K-means和M-R K-means用C++實(shí)現(xiàn)，而Ncut算法源碼則來(lái)自華盛頓大學(xué)的譜聚類工具箱*http://www.cs.washington.edu/homes/sagarwal/code.html.，M-R Ncut則在Ncut源碼基礎(chǔ)上修改而成。實(shí)驗(yàn)中所用到的所有算法，都涉及到初始點(diǎn)的選擇。為避免初始點(diǎn)選擇對(duì)算法性能的影響，對(duì)于同一個(gè)語(yǔ)料集，我們每個(gè)算法運(yùn)行10次，并且，對(duì)其中的每一次運(yùn)行，所有算法都采用同樣一組隨機(jī)生成的初始點(diǎn)。最終，對(duì)于每一個(gè)算法，我們將10次實(shí)驗(yàn)的F-measure和熵值進(jìn)行平均，以供性能比較。對(duì)于所有算法，也同樣涉及到聚類結(jié)果中簇?cái)?shù)的設(shè)定，在實(shí)驗(yàn)中，我們統(tǒng)一將聚類結(jié)果的簇?cái)?shù)設(shè)定為語(yǔ)料集中的類別數(shù)。在K-means算法中，我們采用歐氏距離，以同M-R K-means中的M-R距離進(jìn)行比較。在我們的實(shí)驗(yàn)中，K-means的收斂條件是，平方和準(zhǔn)則函數(shù)(所有點(diǎn)到最近簇中心距離的平方和)在兩次迭代中的差值不超過(guò)0.001；M-R K-means的收斂條件是，簇與簇之間不存在文檔的遷移，或者達(dá)到了最大迭代次數(shù)(實(shí)驗(yàn)中設(shè)為20)；Ncut的收斂條件與K-means一致；而對(duì)于M-R Ncut，由于算法時(shí)間復(fù)雜度較大，為了方便實(shí)驗(yàn)進(jìn)行，我們將最大迭代次數(shù)設(shè)置為5。

對(duì)于Ncut和M-R Ncut，還需要確定高斯相似度中的參數(shù)σ，Ng[8]和Zelnik-Manor[12]提出了不同的確定參數(shù)σ的方法，Ng建議采用使得在譜空間中類簇分布盡量緊湊的σ值，Zelnik-Manor則建議用第k近鄰與當(dāng)前點(diǎn)的距離來(lái)估算σ。我們嘗試了這兩種確定σ參數(shù)的方法，Ng的方法盡管需要遍歷σ，但能夠使Ncut算法發(fā)揮更好的性能。Zelnik-Manor的方法易于實(shí)現(xiàn)但效果略差。盡管M-R框架在兩種σ選擇策略下都能取得性能的提升，為了使得Ncut系列和K-means系列也能有個(gè)性能比較的參照，我們僅列舉出Ng方法的實(shí)驗(yàn)結(jié)果。

實(shí)驗(yàn)結(jié)果的F-measure和熵值分別如表2和表3所示。

表2 所有語(yǔ)料集上的聚類結(jié)果F值比較

表3 所有語(yǔ)料集上的聚類結(jié)果熵值比較

從如上實(shí)驗(yàn)結(jié)果我們可以得到這樣一些結(jié)論：

(1) M-R框架在K-means和Ncut上皆取得了性能提升，性能提升全面而穩(wěn)定，語(yǔ)料集的大小及類簇的個(gè)數(shù)對(duì)性能的提升沒(méi)有明顯影響。我們對(duì)兩類算法應(yīng)用M-R框架前后的對(duì)比實(shí)驗(yàn)結(jié)果進(jìn)行t檢驗(yàn)，p-value皆小于0.01，這證實(shí)了M-R框架的有效性。

(2) 最好的聚類性能幾乎皆由M-R Ncut取得，這是因?yàn)橐环矫鍺cut的性能高于K-means，另一方面M-R Ncut基于Ncut取得了較為穩(wěn)定的性能提升。

(3) M-R框架在K-means上取得的性能提升較Ncut上略高。以F-measure為例，在RCV1系列上，M-R K-means取得的平均性能提升為0.050，M-R Ncut取得的平均性能提升為0.027；在Newsgroup系列上，M-R K-means取得的平均性能提升為0.071，M-R Ncut取得的平均性能提升為0.050。進(jìn)一步比較可以看出，在語(yǔ)料類簇?cái)?shù)較多時(shí)，M-R K-means甚至取得了與Ncut可比的性能。M-R框架在K-means上取得的性能更為顯著，其原因分析如下：K-means采用點(diǎn)到中心的距離進(jìn)行聚類判別，而Ncut采用點(diǎn)與點(diǎn)的距離構(gòu)建鄰接矩陣。盡管M-R框架對(duì)二者的修正都取得了較為顯著的效果，但K-means中點(diǎn)到中心的距離關(guān)系到點(diǎn)與簇的全局關(guān)系，因此用簇的全局信息(標(biāo)準(zhǔn)差)進(jìn)行修正更為有效。

5 結(jié)論及下一步研究

面向模型不匹配問(wèn)題，本文提出了一種基于空間映射及尺度變換的聚類框架，簡(jiǎn)稱M-R框架。該框架選擇一組具有區(qū)分度的方向構(gòu)造M-R坐標(biāo)系，并在該坐標(biāo)系下分析待聚類語(yǔ)料的分布特征，利用這些分布特征構(gòu)造尺度變換函數(shù)，以尺度變換的方式歸一化語(yǔ)料的分布，以使距離度量更好地反映文檔的類別歸屬。M-R框架伴隨聚類算法迭代執(zhí)行，以不斷提升聚類的性能。本文將M-R框架應(yīng)用到了K-means和Ncut上，在RCV1語(yǔ)料集及20Newsgroup語(yǔ)料集上的實(shí)驗(yàn)表明，M-R框架取得了聚類結(jié)果質(zhì)量的全面提升。

M-R框架最重要貢獻(xiàn)是提出了一種基于語(yǔ)料特征并面向算法假設(shè)的空間映射，該映射能夠?qū)⒄Z(yǔ)料歸一化到更為接近算法假設(shè)的分布形態(tài)。顯然，M-R框架可以應(yīng)用到更多的聚類算法上，也適用于分類領(lǐng)域。下一步，我們將對(duì)M-R框架的理論進(jìn)行更為深入的研究，并同時(shí)對(duì)M-R框架的應(yīng)用進(jìn)行更為廣泛的探索。

[1] Dumais S. T. LSI Meets TREC: A Status Report[C]// D. Harman (Ed.) Prof. of The First Text REtrieval Conference (TREC1), National Institute of Standards and Technology Special Publication 500-207, 1993: 137-152.

[2] Liu X., Croft W.B. Cluster-Based Retrieval Using Language Models[C]// Proc. of SIGIR, 2004: 186-193.

[3] Zamir O., Etzioni O., Madani O., et al. Fast and Intuitive Clustering of Web Documents[C]// Proc. of KDD, 1997: 287-290.

[4] Han J. and Kamber M. Data Mining: Concepts and Techniques, Second Edition[M]. Morgan Kaufmann Publishes, 2006.

[5] Wu H., Phang T. H., Liu B., et al. A Refinement Approach to Handling Model Misfit in Text Categorization[C]// SIGKDD, 2002: 207-216.

[6] Tan S., Cheng X., Ghanem MM, et al. A Novel Refinement Approach for Text Categorization[C]// Proc. of the 14th ACM CIKM, 2005: 469-476.

[7] Shawe-Taylor J., Cristianini N. Kernel Methods for Pattern Analysis[M]. Cambridge University Press, 2004.

[8] Ng A., Jordan M., Weiss Y. On Spectral Clustering: Analysis and an Algorithm[J]. T. Dietterich, S. Becker, and Ghahramani Z. (Eds.), Advances in Neural Information Processing Systems 14, MIT Press, 2002.

[9] Shi, J. and Malik, J. Normalized Cuts and Image Segmentation[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2000, 22(8): 888-905.

[10] Chan P. K., Schlag D. F., Zien J. Y. Spectral K-way Ratio-Cut Partitioning and Clustering[J]. IEEE Trans. Computer-Aided Design, 1994, 13:1088-1096.

[11] Ding C., He X., Zha H., et al. A Min-Max Cut Algorithm for Graph Partitioning and Data Clustering[C]// Proc. of ICDM, 2001: 107-114.

[12] Zelnik-Manor L., Perona P. Self-Tuning Spectral Clustering[C]// NIPS 17. 2005.

[13] Duda R. O., Hart P. E., Stork D. G. Pattern Classification, Second Edition[M].Wiley-Interscience Publishes, 2000.

[14] Lewis D. D., Yang Y., Rose T., et al. RCV1: A New Benchmark Collection for Text Categorization Research[J].Journal of Machine Learning Research, 2004.

[15] 周昭濤. 文本聚類分析效果評(píng)價(jià)及文本表示研究[D]. 北京: 中國(guó)科學(xué)院計(jì)算技術(shù)研究所, 2005.