摘 要：文本聚類是搜索引擎和語(yǔ)義web的基本技術(shù)，這次本蛙和大家一起學(xué)習(xí)一下簡(jiǎn)單的文本聚類算法，可能不能直接用于實(shí)際應(yīng)用中，但對(duì)于想學(xué)搜索技術(shù)的初學(xué) 者還是有一定入門作用的。這里會(huì)用到TF/IDF權(quán)重，用余弦?jiàn)A角計(jì)算文本相似度，用方差計(jì)算兩個(gè)數(shù)據(jù)間歐式距離，用k-means進(jìn)行數(shù)據(jù)聚類等數(shù)學(xué)和 統(tǒng)計(jì)知識(shí)。關(guān)于這些概念可以去google，或者參考文本后的參考鏈接。
思路：計(jì)算兩篇文檔的相似度，最簡(jiǎn)單的做法就是用提取文檔的TF/IDF權(quán)重，然后用余弦定理計(jì)算兩個(gè)多維向量的距離。能計(jì)算兩個(gè)文本間的距離后，用標(biāo)準(zhǔn)的k-means算法就可以實(shí)現(xiàn)文本聚類了。
測(cè)試：首先我們準(zhǔn)備以下數(shù)據(jù)
===================
奧運(yùn) 拳擊 入場(chǎng)券 基本 分罄 鄒市明 奪冠 對(duì)手 浮出 水面
股民 要 清楚 自己 的 目的
印花稅 之 股民 四季
杭州 股民 放 鞭炮 慶祝 印花稅 下調(diào)
殘疾 女 青年 入圍 奧運(yùn) 游泳 比賽 創(chuàng) 奧運(yùn) 歷史 兩 項(xiàng) 第一
介紹 一 個(gè) ASP.net MVC 系列 教程
在 asp.net 中 實(shí)現(xiàn) 觀察者 模式 ，或 有 更 好 的 方法 （續(xù)）
輸 大錢 的 股民 給 我們 啟迪
Asp.Net 頁(yè)面 執(zhí)行 流程 分析
運(yùn)動(dòng)員 行李 將 “后 上 先 下” 奧運(yùn) 相關(guān) 人員 行李 實(shí)名制
asp.net 控件 開發(fā) 顯示 控件 內(nèi)容
奧運(yùn) 票務(wù) 網(wǎng)上 成功 訂票 后 應(yīng) 及時(shí) 到 銀行 代售 網(wǎng)點(diǎn) 付款
某 心理 健康 站 開張 后 首 個(gè) 咨詢 者 是 位 新 股民
ASP.NET 自定義 控件 復(fù)雜 屬性 聲明 持久性 淺析
==================
很明顯以上數(shù)據(jù)可以分為三類：asp.net，奧運(yùn)和股民，我們就寫程序來(lái)實(shí)現(xiàn)它，各種算法的原理網(wǎng)上都有，我就大概只貼代碼，聲明一下，部分代碼是從網(wǎng) 上直接抄的，k-means代碼是我從一篇文章的java示例代碼轉(zhuǎn)換過(guò)來(lái)的，我給代碼加了不少注釋，希望能幫助大家理解。
以下是入口函數(shù)
static void Main( string [] args)
{
// 1、獲取文檔輸入
string [] docs = getInputDocs( " input.txt " );
if (docs.Length < 1 )
{
Console.WriteLine( " 沒(méi)有文檔輸入 " );
Console.Read();
return ;
}
// 2、初始化TFIDF測(cè)量器，用來(lái)生產(chǎn)每個(gè)文檔的TFIDF權(quán)重
TFIDFMeasure tf = new TFIDFMeasure(docs, new Tokeniser());
int K = 3 ; // 聚成3個(gè)聚類
// 3、生成k-means的輸入數(shù)據(jù)，是一個(gè)聯(lián)合數(shù)組，第一維表示文檔個(gè)數(shù)，
// 第二維表示所有文檔分出來(lái)的所有詞
double [][] data = new double [docs.Length][];
int docCount = docs.Length; // 文檔個(gè)數(shù)
int dimension = tf.NumTerms; // 所有詞的數(shù)目
for ( int i = 0 ; i < docCount; i ++ )
{
for ( int j = 0 ; j < dimension; j ++ )
{
data[i] = tf.GetTermVector2(i); // 獲取第i個(gè)文檔的TFIDF權(quán)重向量
}
}
// 4、初始化k-means算法，第一個(gè)參數(shù)表示輸入數(shù)據(jù)，第二個(gè)參數(shù)表示要聚成幾個(gè)類
WawaKMeans kmeans = new WawaKMeans(data, K);
// 5、開始迭代
kmeans.Start();
// 6、獲取聚類結(jié)果并輸出
WawaCluster[] clusters = kmeans.Clusters;
foreach (WawaCluster cluster in clusters)
{
List < int > members = cluster.CurrentMembership;
Console.WriteLine( " ----------------- " );
foreach ( int i in members)
{
Console.WriteLine(docs[i]);
}
}
Console.Read();
}
以下是分詞器的主要代碼
/// <summary>
/// 以空白字符進(jìn)行簡(jiǎn)單分詞，并忽略大小寫，
/// 實(shí)際情況中可以用其它中文分詞算法
/// </summary>
/// <param name="input"></param>
/// <returns></returns>
public IList < string > Partition( string input)
{
Regex r = new Regex( " ([ //t{}():;. /n]) " );
input = input.ToLower() ;
String [] tokens = r.Split(input);
List < string > filter = new List < string > () ;
for ( int i = 0 ; i < tokens.Length ; i ++ )
{
MatchCollection mc = r.Matches(tokens[i]);
if (mc.Count <= 0 && tokens[i].Trim().Length > 0
&& ! StopWordsHandler.IsStopword (tokens[i]) )
filter.Add(tokens[i]) ;
}
return filter.ToArray();
}
以下是kmeans算法的基本代碼
public class WawaKMeans
{
/// <summary>
/// 數(shù)據(jù)的數(shù)量
/// </summary>
readonly int _coordCount;
/// <summary>
/// 原始數(shù)據(jù)
/// </summary>
readonly double [][] _coordinates;
/// <summary>
/// 聚類的數(shù)量
/// </summary>
readonly int _k;
/// <summary>
/// 聚類
/// </summary>
private readonly WawaCluster[] _clusters;
internal WawaCluster[] Clusters
{
get { return _clusters; }
}
/// <summary>
/// 定義一個(gè)變量用于記錄和跟蹤每個(gè)資料點(diǎn)屬于哪個(gè)群聚類
/// _clusterAssignments[j]=i;// 表示第 j 個(gè)資料點(diǎn)對(duì)象屬于第 i 個(gè)群聚類
/// </summary>
readonly int [] _clusterAssignments;
/// <summary>
/// 定義一個(gè)變量用于記錄和跟蹤每個(gè)資料點(diǎn)離聚類最近
/// </summary>
private readonly int [] _nearestCluster;
/// <summary>
/// 定義一個(gè)變量，來(lái)表示資料點(diǎn)到中心點(diǎn)的距離,
/// 其中—_distanceCache[i][j]表示第i個(gè)資料點(diǎn)到第j個(gè)群聚對(duì)象中心點(diǎn)的距離；
/// </summary>
private readonly double [,] _distanceCache;
/// <summary>
/// 用來(lái)初始化的隨機(jī)種子
/// </summary>
private static readonly Random _rnd = new Random( 1 );
public WawaKMeans( double [][] data, int K)
{
_coordinates = data;
_coordCount = data.Length;
_k = K;
_clusters = new WawaCluster[K];
_clusterAssignments = new int [_coordCount];
_nearestCluster = new int [_coordCount];
_distanceCache = new double [_coordCount,data.Length];
InitRandom();
}
public void Start()
{
int iter = 0 ;
while ( true )
{
Console.WriteLine( " Iteration " + (iter ++ ) + " 
" );
// 1、重新計(jì)算每個(gè)聚類的均值
for ( int i = 0 ; i < _k; i ++ )
{
_clusters[i].UpdateMean(_coordinates);
}
// 2、計(jì)算每個(gè)數(shù)據(jù)和每個(gè)聚類中心的距離
for ( int i = 0 ; i < _coordCount; i ++ )
{
for ( int j = 0 ; j < _k; j ++ )
{
double dist = getDistance(_coordinates[i], _clusters[j].Mean);
_distanceCache[i,j] = dist;
}
}
// 3、計(jì)算每個(gè)數(shù)據(jù)離哪個(gè)聚類最近
for ( int i = 0 ; i < _coordCount; i ++ )
{
_nearestCluster[i] = nearestCluster(i);
}
// 4、比較每個(gè)數(shù)據(jù)最近的聚類是否就是它所屬的聚類
// 如果全相等表示所有的點(diǎn)已經(jīng)是最佳距離了，直接返回；
int k = 0 ;
for ( int i = 0 ; i < _coordCount; i ++ )
{
if (_nearestCluster[i] == _clusterAssignments[i])
k ++ ;
}
if (k == _coordCount)
break ;
// 5、否則需要重新調(diào)整資料點(diǎn)和群聚類的關(guān)系，調(diào)整完畢后再重新開始循環(huán)；
// 需要修改每個(gè)聚類的成員和表示某個(gè)數(shù)據(jù)屬于哪個(gè)聚類的變量
for ( int j = 0 ; j < _k; j ++ )
{
_clusters[j].CurrentMembership.Clear();
}
for ( int i = 0 ; i < _coordCount; i ++ )
{
_clusters[_nearestCluster[i]].CurrentMembership.Add(i);
_clusterAssignments[i] = _nearestCluster[i];
}
}
}
/// <summary>
/// 計(jì)算某個(gè)數(shù)據(jù)離哪個(gè)聚類最近
/// </summary>
/// <param name="ndx"></param>
/// <returns></returns>
int nearestCluster( int ndx)
{
int nearest = - 1 ;
double min = Double.MaxValue;
for ( int c = 0 ; c < _k; c ++ )
{
double d = _distanceCache[ndx,c];
if (d < min)
{
min = d;
nearest = c;
}
}
if (nearest ==- 1 )
{
;
}
return nearest;
}
/// <summary>
/// 計(jì)算某數(shù)據(jù)離某聚類中心的距離
/// </summary>
/// <param name="coord"></param>
/// <param name="center"></param>
/// <returns></returns>
static double getDistance( double [] coord, double [] center)
{
// int len = coord.Length;
// double sumSquared = 0.0;
// for (int i = 0; i < len; i++)
// {
// double v = coord[i] - center[i];
// sumSquared += v * v; // 平方差
// }
// return Math.Sqrt(sumSquared);
// 也可以用余弦?jiàn)A角來(lái)計(jì)算某數(shù)據(jù)離某聚類中心的距離
return 1 - TermVector.ComputeCosineSimilarity(coord, center);
}
/// <summary>
/// 隨機(jī)初始化k個(gè)聚類
/// </summary>
private void InitRandom()
{
for ( int i = 0 ; i < _k; i ++ )
{
int temp = _rnd.Next(_coordCount);
_clusterAssignments[temp] = i; // 記錄第temp個(gè)資料屬于第i個(gè)聚類
_clusters[i] = new WawaCluster(temp,_coordinates[temp]);
}
}
}
以下是聚類實(shí)體類的定義
internal class WawaCluster
{
public WawaCluster( int dataindex, double [] data)
{
CurrentMembership.Add(dataindex);
Mean = data;
}
/// <summary>
/// 該聚類的數(shù)據(jù)成員索引
/// </summary>
internal List < int > CurrentMembership = new List < int > ();
/// <summary>
/// 該聚類的中心
/// </summary>
internal double [] Mean;
/// <summary>
/// 該方法計(jì)算聚類對(duì)象的均值
/// </summary>
/// <param name="coordinates"></param>
public void UpdateMean( double [][] coordinates)
{
// 根據(jù) mCurrentMembership 取得原始資料點(diǎn)對(duì)象 coord ，該對(duì)象是 coordinates 的一個(gè)子集；
// 然后取出該子集的均值；取均值的算法很簡(jiǎn)單，可以把 coordinates 想象成一個(gè) m*n 的距陣 ,
// 每個(gè)均值就是每個(gè)縱向列的取和平均值 , // 該值保存在 mCenter 中
for ( int i = 0 ; i < CurrentMembership.Count; i ++ )
{
double [] coord = coordinates[CurrentMembership[i]];
for ( int j = 0 ; j < coord.Length; j ++ )
{
Mean[j] += coord[j]; // 得到每個(gè)縱向列的和；
}
for ( int k = 0 ; k < Mean.Length; k ++ )
{
Mean[k] /= coord.Length; // 對(duì)每個(gè)縱向列取平均值
}
}
}
}
計(jì)算TF/IDF和利用余弦定理計(jì)算相似度的代碼見(jiàn)完整版的代碼下載，那兩部分都是外國(guó)人寫的，里面有它的聯(lián)系方式，不懂的可以問(wèn)他，反正我差不多懂了。
下面看看咱們的測(cè)試結(jié)果：
Iteration 0...
Iteration 1...
Iteration 2...
-----------------
奧運(yùn) 拳擊 入場(chǎng)券 基本 分罄 鄒市明 奪冠 對(duì)手 浮出 水面
杭州 股民 放 鞭炮 慶祝 印花稅 下調(diào)
殘疾 女 青年 入圍 奧運(yùn) 游泳 比賽 創(chuàng) 奧運(yùn) 歷史 兩 項(xiàng) 第一
運(yùn)動(dòng)員 行李 將 “后 上 先 下” 奧運(yùn) 相關(guān) 人員 行李 實(shí)名制
奧運(yùn) 票務(wù) 網(wǎng)上 成功 訂票 后 應(yīng) 及時(shí) 到 銀行 代售 網(wǎng)點(diǎn) 付款
-----------------
股民 要 清楚 自己 的 目的
印花稅 之 股民 四季
輸 大錢 的 股民 給 我們 啟迪
某 心理 健康 站 開張 后 首 個(gè) 咨詢 者 是 位 新 股民
-----------------
介紹 一 個(gè) ASP.net MVC 系列 教程
在 asp.net 中 實(shí)現(xiàn) 觀察者 模式 ，或 有 更 好 的 方法 （續(xù)）
Asp.Net 頁(yè)面 執(zhí)行 流程 分析
asp.net 控件 開發(fā) 顯示 控件 內(nèi)容
ASP.NET 自定義 控件 復(fù)雜 屬性 聲明 持久性 淺析 聚 類聚的非常準(zhǔn)確，而且只迭代了3次，模型就收斂了，當(dāng)然了這是最理想的效果，其實(shí)聚類的結(jié)果受好多種因素制約，提取特征的算法，隨機(jī)初始化函 數(shù)，kmeans算法的實(shí)現(xiàn)等，都有優(yōu)化的地方，不信你把輸入的數(shù)據(jù)的順序改改，聚類結(jié)果就不一樣了，或者把隨機(jī)數(shù)的種子變一下，結(jié)果也不一樣，k- means算法加入一些變異系數(shù)的調(diào)整，結(jié)果也不一樣，提取特征的地方不用TF/IDF權(quán)重算法用別的，結(jié)果肯定也不一樣。
完整代碼里還有另一組測(cè)試數(shù)據(jù)，結(jié)果也很不錯(cuò)，我的意思是我的算法不是針對(duì)一組測(cè)試數(shù)據(jù)，而是針對(duì)好多數(shù)據(jù)都有不錯(cuò)的結(jié)果。
總結(jié)：數(shù)學(xué)和英語(yǔ)真是寫程序之根本呀，弄這個(gè)東西遇到了好多英語(yǔ)單詞不會(huì)，查還查不出來(lái)，也理解不了，最后google一看，是個(gè)數(shù)學(xué)專用詞，再搜索這個(gè)數(shù)學(xué)專用詞的中文解釋，發(fā)現(xiàn)還是理解不了那數(shù)學(xué)原理。所以還是得多學(xué)習(xí)數(shù)學(xué)和英語(yǔ)。
參考鏈接：
K-MEANS算法
http://beauty9235.javaeye.com/blog/161675
什么是變異系數(shù)
http://zhidao.baidu.com/question/15013015.html
TF/IDF實(shí)現(xiàn)
http://www.codeproject.com/KB/cs/tfidf.aspx
源碼下載：WawaTextCluster.zip
http://www.cnblogs.com/onlytiancai/archive/2008/05/10/1191557.html 《來(lái)源》