蛙蛙推荐：蛙蛙教你文本聚类
摘要：文本聚类是搜索引擎和语义web的基本技术，这次本蛙和大家一起学习一下简单的文本聚类算法，可能不能直接用于实际应用中，但对于想学搜索技术的初学者还是有一定入门作用的。这里会用到TF/IDF权重，用余弦夹角计算文本相似度，用方差计算两个数据间欧式距离，用k-means进行数据聚类等数学和统计知识。关于这些概念可以去google，或者参考文本后的参考链接。
思路：计算两篇文档的相似度，最简单的做法就是用提取文档的TF/IDF权重，然后用余弦定理计算两个多维向量的距离。能计算两个文本间的距离后，用标准的k-means算法就可以实现文本聚类了。
测试：首先我们准备以下数据===================奥运 拳击 入场券 基本 分罄 邹市明 夺冠 对手 浮出 水面股民 要 清楚 自己 的 目的印花税 之 股民 四季杭州 股民 放 鞭炮 庆祝 印花税 下调 残疾 女 青年 入围 奥运 游泳 比赛 创 奥运 历史 两 项 第一介绍 一 个 ASP.net MVC 系列 教程在 asp.net 中 实现 观察者 模式 ，或 有 更 好 的 方法 （续）输 大钱 的 股民 给 我们 启迪Asp.Net 页面 执行 流程 分析运动员 行李 将 “后 上 先 下” 奥运 相关 人员 行李 实名制asp.net 控件 开发 显示 控件 内容奥运 票务 网上 成功 订票 后 应 及时 到 银行 代售 网点 付款某 心理 健康 站 开张 后 首 个 咨询 者 是 位 新 股民ASP.NET 自定义 控件 复杂 属性 声明 持久性 浅析==================很明显以上数据可以分为三类：asp.net，奥运和股民，我们就写程序来实现它，各种算法的原理网上都有，我就大概只贴代码，声明一下，部分代码是从网上直接抄的，k-means代码是我从一篇文章的java示例代码转换过来的，我给代码加了不少注释，希望能帮助大家理解。
以下是入口函数staticvoidMain(string[]args){//1、获取文档输入string[]docs=getInputDocs(“input.txt”);if(docs.Length<1){Console.WriteLine(“没有文档输入”);Console.Read();return;}//2、初始化TFIDF测量器，用来生产每个文档的TFIDF权重TFIDFMeasuretf=newTFIDFMeasure(docs,newTokeniser());intK=3;//聚成3个聚类//3、生成k-means的输入数据，是一个联合数组，第一维表示文档个数，//第二维表示所有文档分出来的所有词double[][]data=newdouble[docs.Length][];intdocCount=docs.Length;//文档个数intdimension=tf.NumTerms;//所有词的数目for(inti=0;i<docCount;i++){for(intj=0;j<dimension;j++){data[i]=tf.GetTermVector2(i);//获取第i个文档的TFIDF权重向量}}//4、初始化k-means算法，第一个参数表示输入数据，第二个参数表示要聚成几个类WawaKMeanskmeans=newWawaKMeans(data,K);//5、开始迭代kmeans.Start();//6、获取聚类结果并输出WawaCluster[]clusters=kmeans.Clusters;foreach(WawaClusterclusterinclusters){List<int>members=cluster.CurrentMembership;Console.WriteLine(“—————–“);foreach(intiinmembers){Console.WriteLine(docs[i]);}}Console.Read();}
以下是分词器的主要代码/**////<summary>///以空白字符进行简单分词，并忽略大小写，///实际情况中可以用其它中文分词算法///</summary>///<paramname=”input”></param>///<returns></returns>publicIList<string>Partition(stringinput){Regexr=newRegex(“([//t{}():;./n])”);input=input.ToLower();String[]tokens=r.Split(input);List<string>filter=newList<string>();for(inti=0;i<tokens.Length;i++){MatchCollectionmc=r.Matches(tokens[i]);if(mc.Count<=0&&tokens[i].Trim().Length>0&&!StopWordsHandler.IsStopword(tokens[i]))filter.Add(tokens[i]);}returnfilter.ToArray();}
以下是kmeans算法的基本代码publicclassWawaKMeans{/**////<summary>///数据的数量///</summary>readonlyint_coordCount;/**////<summary>///原始数据///</summary>readonlydouble[][]_coordinates;/**////<summary>///聚类的数量///</summary>readonlyint_k;/**////<summary>///聚类///</summary>privatereadonlyWawaCluster[]_clusters;internalWawaCluster[]Clusters{get{return_clusters;}}/**////<summary>///定义一个变量用于记录和跟踪每个资料点属于哪个群聚类///_clusterAssignments[j]=i;//表示第j个资料点对象属于第i个群聚类///</summary>readonlyint[]_clusterAssignments;/**////<summary>///定义一个变量用于记录和跟踪每个资料点离聚类最近///</summary>privatereadonlyint[]_nearestCluster;/**////<summary>///定义一个变量，来表示资料点到中心点的距离,///其中—_distanceCache[i][j]表示第i个资料点到第j个群聚对象中心点的距离；///</summary>privatereadonlydouble[,]_distanceCache;/**////<summary>///用来初始化的随机种子///</summary>privatestaticreadonlyRandom_rnd=newRandom(1);publicWawaKMeans(double[][]data,intK){_coordinates=data;_coordCount=data.Length;_k=K;_clusters=newWawaCluster[K];_clusterAssignments=newint[_coordCount];_nearestCluster=newint[_coordCount];_distanceCache=newdouble[_coordCount,data.Length];InitRandom();}publicvoidStart(){intiter=0;while(true){Console.WriteLine(“Iteration”+(iter++)+””);//1、重新计算每个聚类的均值for(inti=0;i<_k;i++){_clusters[i].UpdateMean(_coordinates);}//2、计算每个数据和每个聚类中心的距离for(inti=0;i<_coordCount;i++){for(intj=0;j<_k;j++){doubledist=getDistance(_coordinates[i],_clusters[j].Mean);_distanceCache[i,j]=dist;}}//3、计算每个数据离哪个聚类最近for(inti=0;i<_coordCount;i++){_nearestCluster[i]=nearestCluster(i);}//4、比较每个数据最近的聚类是否就是它所属的聚类//如果全相等表示所有的点已经是最佳距离了，直接返回；intk=0;for(inti=0;i<_coordCount;i++){if(_nearestCluster[i]==_clusterAssignments[i])k++;}if(k==_coordCount)break;//5、否则需要重新调整资料点和群聚类的关系，调整完毕后再重新开始循环；//需要修改每个聚类的成员和表示某个数据属于哪个聚类的变量for(intj=0;j<_k;j++){_clusters[j].CurrentMembership.Clear();}for(inti=0;i<_coordCount;i++){_clusters[_nearestCluster[i]].CurrentMembership.Add(i);_clusterAssignments[i]=_nearestCluster[i];}}}/**////<summary>///计算某个数据离哪个聚类最近///</summary>///<paramname=”ndx”></param>///<returns></returns>intnearestCluster(intndx){intnearest=-1;doublemin=Double.MaxValue;for(intc=0;c<_k;c++){doubled=_distanceCache[ndx,c];if(d<min){min=d;nearest=c;}}if(nearest==-1){;}returnnearest;}/**////<summary>///计算某数据离某聚类中心的距离///</summary>///<paramname=”coord”></param>///<paramname=”center”></param>///<returns></returns>staticdoublegetDistance(double[]coord,double[]center){//intlen=coord.Length;//doublesumSquared=0.0;//for(inti=0;i<len;i++)//{//doublev=coord[i]-center[i];//sumSquared+=v*v;//平方差//}//returnMath.Sqrt(sumSquared);//也可以用余弦夹角来计算某数据离某聚类中心的距离return1-TermVector.ComputeCosineSimilarity(coord,center);}/**////<summary>///随机初始化k个聚类///</summary>privatevoidInitRandom(){for(inti=0;i<_k;i++){inttemp=_rnd.Next(_coordCount);_clusterAssignments[temp]=i;//记录第temp个资料属于第i个聚类_clusters[i]=newWawaCluster(temp,_coordinates[temp]);}}}
以下是聚类实体类的定义internalclassWawaCluster{publicWawaCluster(intdataindex,double[]data){CurrentMembership.Add(dataindex);Mean=data;}/**////<summary>///该聚类的数据成员索引///</summary>internalList<int>CurrentMembership=newList<int>();/**////<summary>///该聚类的中心///</summary>internaldouble[]Mean;/**////<summary>///该方法计算聚类对象的均值///</summary>///<paramname=”coordinates”></param>publicvoidUpdateMean(double[][]coordinates){//根据mCurrentMembership取得原始资料点对象coord，该对象是coordinates的一个子集；//然后取出该子集的均值；取均值的算法很简单，可以把coordinates想象成一个m*n的距阵,//每个均值就是每个纵向列的取和平均值,//该值保存在mCenter中for(inti=0;i<CurrentMembership.Count;i++){double[]coord=coordinates[CurrentMembership[i]];for(intj=0;j<coord.Length;j++){Mean[j]+=coord[j];//得到每个纵向列的和；}for(intk=0;k<Mean.Length;k++){Mean[k]/=coord.Length;//对每个纵向列取平均值}}}}
计算TF/IDF和利用余弦定理计算相似度的代码见完整版的代码下载，那两部分都是外国人写的，里面有它的联系方式，不懂的可以问他，反正我差不多懂了。
下面看看咱们的测试结果：Iteration 0…Iteration 1…Iteration 2…—————–奥运 拳击 入场券 基本 分罄 邹市明 夺冠 对手 浮出 水面杭州 股民 放 鞭炮 庆祝 印花税 下调残疾 女 青年 入围 奥运 游泳 比赛 创 奥运 历史 两 项 第一运动员 行李 将 “后 上 先 下” 奥运 相关 人员 行李 实名制奥运 票务 网上 成功 订票 后 应 及时 到 银行 代售 网点 付款—————–股民 要 清楚 自己 的 目的印花税 之 股民 四季输 大钱 的 股民 给 我们 启迪某 心理 健康 站 开张 后 首 个 咨询 者 是 位 新 股民—————–介绍 一 个 ASP.net MVC 系列 教程在 asp.net 中 实现 观察者 模式 ，或 有 更 好 的 方法 （续）Asp.Net 页面 执行 流程 分析asp.net 控件 开发 显示 控件 内容ASP.NET 自定义 控件 复杂 属性 声明 持久性 浅析聚类聚的非常准确，而且只迭代了3次，模型就收敛了，当然了这是最理想的效果，其实聚类的结果受好多种因素制约，提取特征的算法，随机初始化函数，kmeans算法的实现等，都有优化的地方，不信你把输入的数据的顺序改改，聚类结果就不一样了，或者把随机数的种子变一下，结果也不一样，k-means算法加入一些变异系数的调整，结果也不一样，提取特征的地方不用TF/IDF权重算法用别的，结果肯定也不一样。完整代码里还有另一组测试数据，结果也很不错，我的意思是我的算法不是针对一组测试数据，而是针对好多数据都有不错的结果。
总结：数学和英语真是写程序之根本呀，弄这个东西遇到了好多英语单词不会，查还查不出来，也理解不了，最后google一看，是个数学专用词，再搜索这个数学专用词的中文解释，发现还是理解不了那数学原理。所以还是得多学习数学和英语。
参考链接：K-MEANS算法http://beauty9235.javaeye.com/blog/161675什么是变异系数http://zhidao.baidu.com/question/15013015.htmlTF/IDF实现http://www.codeproject.com/KB/cs/tfidf.aspx源码下载：WawaTextCluster.zip
有理想在的地方，地狱就是天堂
