基于文本的信息自動(dòng)聚類的算法很多，我以前介紹過(guò)一些，比較流行的算法有我以前提到的KNN和SVM，在過(guò)去的一段時(shí)間里，空閑的時(shí)間基本上都用來(lái)研究能否快速的實(shí)現(xiàn)自動(dòng)聚類。上周終于完成了文本自動(dòng)聚類的兼并算法，能夠相對(duì)快速的實(shí)現(xiàn)文本信息的自動(dòng)聚類。下面就介紹一下信息自動(dòng)聚類的實(shí)現(xiàn)，希望能夠幫助大家了結(jié)google news 的新聞如何進(jìn)行自動(dòng)聚類工作。
1] 什么是簡(jiǎn)并算法
簡(jiǎn)并算法是指在文本信息空間內(nèi)尋找任何兩個(gè)最相關(guān)的文本信息，并將之簡(jiǎn)并成一個(gè)文本信息，從而實(shí)現(xiàn)信息數(shù)量的收縮。
2] 如何實(shí)現(xiàn)
1. 簡(jiǎn)并算法的實(shí)現(xiàn)通過(guò)比較整個(gè)信息空間內(nèi)的所有文本的相關(guān)性（相識(shí)性），得到相互之間的相關(guān)性后兩兩(注)進(jìn)行配對(duì)。配對(duì)的要求是這兩個(gè)文本信息的相關(guān)性最大，例如A 找到了文檔B，那么B 也一定找到最相關(guān)的文檔就是A 。
注，某些情況A 最相近的文檔是C ，那么B 而B(niǎo) 最相關(guān)的文檔也是C ，存在一種情況，A,B,C 三者之間自恰，就是構(gòu)成空間信息最近的一個(gè)三角形。
2. 得到了最相似文檔后，將只進(jìn)行平均化，或者簡(jiǎn)單的迭加。
3. 信息空間中獨(dú)立信息的數(shù)量會(huì)減少到原來(lái)的一半以下，然后重復(fù)實(shí)現(xiàn)1 的過(guò)程，在進(jìn)行兼并。
4. 信息最后簡(jiǎn)并到唯一的一個(gè)信息，就是整個(gè)信息文本的平均值。
5. 畫(huà)出信息樹(shù)的結(jié)構(gòu)，就能夠根據(jù)要進(jìn)行規(guī)模不同大小的聚類進(jìn)行自動(dòng)聚類了。
如下的信息樹(shù)結(jié)構(gòu)是對(duì)我進(jìn)行測(cè)試的一個(gè)小樣本大約70個(gè)文檔進(jìn)行信息簡(jiǎn)并算法得到的圖像：
完整的樹(shù)結(jié)構(gòu)可以看這里：
從上圖可以看出，經(jīng)過(guò)自動(dòng)聚類后類別0,2具有最相近的關(guān)系然后進(jìn)行兼并后和類別5進(jìn)行了簡(jiǎn)并，然后在和類別6進(jìn)行了簡(jiǎn)并，最終和另外一支的信息進(jìn)行了最后的簡(jiǎn)并，聚成唯一的全部的信息簡(jiǎn)并。
圖中矩陣的明暗表明了信息之間的相關(guān)程度，矩陣經(jīng)過(guò)對(duì)角化后可以明顯看到聚類的效應(yīng)。
本試驗(yàn)的文本信息和分類結(jié)果下載：
下面是我進(jìn)行文本聚類的文檔公布下載『一共70個(gè)文檔』，我產(chǎn)生的文本的相關(guān)性的矩陣下載。
簡(jiǎn)并算法我也實(shí)現(xiàn)在大樣本的聚類上，大約2000個(gè)文檔進(jìn)行自動(dòng)的分類后進(jìn)行聚類的運(yùn)算時(shí)間大約為2個(gè)小時(shí)「抱歉，我基本上是用shell scripts 和perl scripts 來(lái)寫代碼」，如果先進(jìn)行聚類在分類大約要5個(gè)小時(shí)。
最耗時(shí)間的過(guò)程是產(chǎn)生相關(guān)性矩陣，2000X2000有400萬(wàn)的元素，當(dāng)然不會(huì)那么快了。
經(jīng)過(guò)實(shí)踐，簡(jiǎn)并算法的自動(dòng)聚類還有很多需要改進(jìn)的地方，例如最關(guān)鍵的是信息之間的相識(shí)性的計(jì)算，我采用了最大似然(Maximum Likelihood Fitting)的擬合，在計(jì)算上比較消耗時(shí)間，以后可以改變成其它的算法。
文本的自動(dòng)聚類可以看到Google New上面已經(jīng)相當(dāng)成熟，這里的簡(jiǎn)并算法未來(lái)將為博客中國(guó)的新聞搜索提供支持，希望能夠提供較好的機(jī)器新聞。
- 盧亮 2005年2月20日
聯(lián)系客服
