文本聚类总结

柔光的暖阳◎ 2022-05-24 01:38 264阅读 0赞

摘要：文本聚类是搜索引擎和语义web的基本技术，这次本蛙和大家一起学习一下简单的文本聚类算法，可能不能直接用于实际应用中，但对于想学搜索技术的初学者还是有一定入门作用的。这里会用到TF/IDF权重，用余弦夹角计算文本相似度，用方差计算两个数据间欧式距离，用k-means进行数据聚类等数学和统计知识。关于这些概念可以去google，或者参考文本后的参考链接。

思路：计算两篇文档的相似度，最简单的做法就是用提取文档的TF/IDF权重，然后用余弦定理计算两个多维向量的距离。能计算两个文本间的距离后，用标准的k-means算法就可以实现文本聚类了。

测试：首先我们准备以下数据

[转载地址 ][Link 1]  
===================  
奥运 拳击 入场券 基本 分罄 邹市明 夺冠 对手 浮出 水面  
股民 要 清楚 自己 的 目的  
印花税 之 股民 四季  
杭州 股民 放 鞭炮 庆祝 印花税 下调  
残疾 女 青年 入围 奥运 游泳 比赛 创 奥运 历史 两 项 第一  
介绍 一 个 ASP.net MVC 系列 教程  
在 asp.net 中 实现 观察者 模式 ，或 有 更 好 的 方法 （续）  
输 大钱 的 股民 给 我们 启迪  
Asp.Net 页面 执行 流程 分析  
运动员 行李 将 “后 上 先 下” 奥运 相关 人员 行李 实名制  
asp.net 控件 开发 显示 控件 内容  
奥运 票务 网上 成功 订票 后 应 及时 到 银行 代售 网点 付款  
某 心理 健康 站 开张 后 首 个 咨询 者 是 位 新 股民  
ASP.NET 自定义 控件 复杂 属性 声明 持久性 浅析  
==================  
很明显以上数据可以分为三类：asp.net，奥运和股民，我们就写程序来实现它，各种算法的原理网上都有，我就大概只贴代码，声明一下，部分代码是从网上直接抄的，k-means代码是我从一篇文章的java示例代码转换过来的，我给代码加了不少注释，希望能帮助大家理解。

以下是入口函数

![None.gif][] static  void  Main( string \[\] args)  
![ExpandedBlockStart.gif][] \{  
![InBlock.gif][]//1、获取文档输入  
![InBlock.gif][]string\[\] docs = getInputDocs("input.txt");  
![InBlock.gif][]if (docs.Length <1)  
![ExpandedSubBlockStart.gif][]\{  
![InBlock.gif][] Console.WriteLine("没有文档输入");  
![InBlock.gif][] Console.Read();  
![InBlock.gif][]return;  
![ExpandedSubBlockEnd.gif][] \}  
![InBlock.gif][]  
![InBlock.gif][]//2、初始化TFIDF测量器，用来生产每个文档的TFIDF权重  
![InBlock.gif][] TFIDFMeasure tf =new TFIDFMeasure(docs, new Tokeniser());  
![InBlock.gif][]  
![InBlock.gif][]int K =3; //聚成3个聚类  
![InBlock.gif][]  
![InBlock.gif][]//3、生成k-means的输入数据，是一个联合数组，第一维表示文档个数，  
![InBlock.gif][]//第二维表示所有文档分出来的所有词  
![InBlock.gif][]double\[\]\[\] data =newdouble\[docs.Length\]\[\];  
![InBlock.gif][]int docCount = docs.Length; //文档个数  
![InBlock.gif][]int dimension = tf.NumTerms;//所有词的数目  
![InBlock.gif][]for (int i =0; i < docCount; i\++)  
![ExpandedSubBlockStart.gif][]\{  
![InBlock.gif][]for (int j =0; j < dimension; j\++)  
![ExpandedSubBlockStart.gif][]\{  
![InBlock.gif][] data\[i\] = tf.GetTermVector2(i); //获取第i个文档的TFIDF权重向量  
![ExpandedSubBlockEnd.gif][] \}  
![ExpandedSubBlockEnd.gif][] \}  
![InBlock.gif][]  
![InBlock.gif][]//4、初始化k-means算法，第一个参数表示输入数据，第二个参数表示要聚成几个类  
![InBlock.gif][] WawaKMeans kmeans =new WawaKMeans(data, K);  
![InBlock.gif][]//5、开始迭代  
![InBlock.gif][] kmeans.Start();  
![InBlock.gif][]  
![InBlock.gif][]//6、获取聚类结果并输出  
![InBlock.gif][] WawaCluster\[\] clusters = kmeans.Clusters;  
![InBlock.gif][]foreach (WawaCluster cluster in clusters)  
![ExpandedSubBlockStart.gif][]\{  
![InBlock.gif][] List<int> members = cluster.CurrentMembership;  
![InBlock.gif][] Console.WriteLine("\-----------------");  
![InBlock.gif][]foreach (int i in members)  
![ExpandedSubBlockStart.gif][]\{  
![InBlock.gif][] Console.WriteLine(docs\[i\]);  
![ExpandedSubBlockEnd.gif][] \}  
![InBlock.gif][]  
![ExpandedSubBlockEnd.gif][] \}  
![InBlock.gif][] Console.Read();  
![ExpandedBlockEnd.gif][]\}   
![None.gif][]  
![None.gif][]

以下是分词器的主要代码

![ExpandedBlockStart.gif][] ///<summary>  
![InBlock.gif][]/// 以空白字符进行简单分词，并忽略大小写，  
![InBlock.gif][]/// 实际情况中可以用其它中文分词算法  
![InBlock.gif][]///</summary>  
![InBlock.gif][]///<param name="input"></param>  
![ExpandedBlockEnd.gif][]///<returns></returns>  
![None.gif][] public  IList < string >  Partition( string  input)  
![ExpandedBlockStart.gif][] \{  
![InBlock.gif][] Regex r=new Regex("(\[ \\\\t\{\}():;. \\n\])");  
![InBlock.gif][] input=input.ToLower() ;  
![InBlock.gif][]  
![InBlock.gif][] String \[\] tokens=r.Split(input);  
![InBlock.gif][]  
![InBlock.gif][] List<string> filter=new List<string>() ;  
![InBlock.gif][]  
![InBlock.gif][]for (int i=0; i < tokens.Length ; i\++)  
![ExpandedSubBlockStart.gif][]\{  
![InBlock.gif][] MatchCollection mc=r.Matches(tokens\[i\]);  
![InBlock.gif][]if (mc.Count <=0&& tokens\[i\].Trim().Length >0  
![InBlock.gif][]&&!StopWordsHandler.IsStopword (tokens\[i\]) )  
![InBlock.gif][] filter.Add(tokens\[i\]) ;  
![ExpandedSubBlockEnd.gif][] \}  
![InBlock.gif][]  
![InBlock.gif][]return filter.ToArray();  
![ExpandedBlockEnd.gif][]\}   
![None.gif][]  
![None.gif][]

以下是kmeans算法的基本代码

![None.gif][] public  class  WawaKMeans  
![ExpandedBlockStart.gif][] \{  
![ExpandedSubBlockStart.gif][]///<summary>  
![InBlock.gif][]/// 数据的数量  
![ExpandedSubBlockEnd.gif][]///</summary>  
![InBlock.gif][]readonlyint \_coordCount;  
![ExpandedSubBlockStart.gif][]///<summary>  
![InBlock.gif][]/// 原始数据  
![ExpandedSubBlockEnd.gif][]///</summary>  
![InBlock.gif][]readonlydouble\[\]\[\] \_coordinates;  
![ExpandedSubBlockStart.gif][]///<summary>  
![InBlock.gif][]/// 聚类的数量  
![ExpandedSubBlockEnd.gif][]///</summary>  
![InBlock.gif][]readonlyint \_k;  
![ExpandedSubBlockStart.gif][]///<summary>  
![InBlock.gif][]/// 聚类  
![ExpandedSubBlockEnd.gif][]///</summary>  
![InBlock.gif][]privatereadonly WawaCluster\[\] \_clusters;  
![InBlock.gif][]  
![InBlock.gif][]internal WawaCluster\[\] Clusters  
![ExpandedSubBlockStart.gif][]\{  
![ExpandedSubBlockStart.gif][]get\{ return \_clusters; \}  
![ExpandedSubBlockEnd.gif][] \}  
![InBlock.gif][]  
![ExpandedSubBlockStart.gif][]///<summary>  
![InBlock.gif][]/// 定义一个变量用于记录和跟踪每个资料点属于哪个群聚类  
![InBlock.gif][]/// \_clusterAssignments\[j\]=i;// 表示第 j 个资料点对象属于第 i 个群聚类  
![ExpandedSubBlockEnd.gif][]///</summary>  
![InBlock.gif][]readonlyint\[\] \_clusterAssignments;  
![ExpandedSubBlockStart.gif][]///<summary>  
![InBlock.gif][]/// 定义一个变量用于记录和跟踪每个资料点离聚类最近  
![ExpandedSubBlockEnd.gif][]///</summary>  
![InBlock.gif][]privatereadonlyint\[\] \_nearestCluster;  
![ExpandedSubBlockStart.gif][]///<summary>  
![InBlock.gif][]/// 定义一个变量，来表示资料点到中心点的距离,  
![InBlock.gif][]/// 其中—\_distanceCache\[i\]\[j\]表示第i个资料点到第j个群聚对象中心点的距离；  
![ExpandedSubBlockEnd.gif][]///</summary>  
![InBlock.gif][]privatereadonlydouble\[,\] \_distanceCache;  
![ExpandedSubBlockStart.gif][]///<summary>  
![InBlock.gif][]/// 用来初始化的随机种子  
![ExpandedSubBlockEnd.gif][]///</summary>  
![InBlock.gif][]privatestaticreadonly Random \_rnd =new Random(1);  
![InBlock.gif][]  
![InBlock.gif][]public WawaKMeans(double\[\]\[\] data, int K)  
![ExpandedSubBlockStart.gif][]\{  
![InBlock.gif][] \_coordinates = data;  
![InBlock.gif][] \_coordCount = data.Length;  
![InBlock.gif][] \_k = K;  
![InBlock.gif][] \_clusters =new WawaCluster\[K\];  
![InBlock.gif][] \_clusterAssignments =newint\[\_coordCount\];  
![InBlock.gif][] \_nearestCluster =newint\[\_coordCount\];  
![InBlock.gif][] \_distanceCache =newdouble\[\_coordCount,data.Length\];  
![InBlock.gif][] InitRandom();  
![ExpandedSubBlockEnd.gif][] \}  
![InBlock.gif][]  
![InBlock.gif][]publicvoid Start()  
![ExpandedSubBlockStart.gif][]\{  
![InBlock.gif][]int iter =0;  
![InBlock.gif][]while (true)  
![ExpandedSubBlockStart.gif][]\{  
![InBlock.gif][] Console.WriteLine("Iteration "\+ (iter\++) \+"![dot.gif][]");  
![InBlock.gif][]//1、重新计算每个聚类的均值  
![InBlock.gif][]for (int i =0; i < \_k; i\++)  
![ExpandedSubBlockStart.gif][]\{  
![InBlock.gif][] \_clusters\[i\].UpdateMean(\_coordinates);  
![ExpandedSubBlockEnd.gif][] \}  
![InBlock.gif][]  
![InBlock.gif][]//2、计算每个数据和每个聚类中心的距离  
![InBlock.gif][]for (int i =0; i < \_coordCount; i\++)  
![ExpandedSubBlockStart.gif][]\{  
![InBlock.gif][]for (int j =0; j < \_k; j\++)  
![ExpandedSubBlockStart.gif][]\{  
![InBlock.gif][]double dist = getDistance(\_coordinates\[i\], \_clusters\[j\].Mean);  
![InBlock.gif][] \_distanceCache\[i,j\] = dist;  
![ExpandedSubBlockEnd.gif][] \}  
![ExpandedSubBlockEnd.gif][] \}  
![InBlock.gif][]  
![InBlock.gif][]//3、计算每个数据离哪个聚类最近  
![InBlock.gif][]for (int i =0; i < \_coordCount; i\++)  
![ExpandedSubBlockStart.gif][]\{  
![InBlock.gif][] \_nearestCluster\[i\] = nearestCluster(i);  
![ExpandedSubBlockEnd.gif][] \}  
![InBlock.gif][]  
![InBlock.gif][]//4、比较每个数据最近的聚类是否就是它所属的聚类  
![InBlock.gif][]//如果全相等表示所有的点已经是最佳距离了，直接返回；  
![InBlock.gif][]int k =0;  
![InBlock.gif][]for (int i =0; i < \_coordCount; i\++)  
![ExpandedSubBlockStart.gif][]\{  
![InBlock.gif][]if (\_nearestCluster\[i\] == \_clusterAssignments\[i\])  
![InBlock.gif][] k\++;  
![InBlock.gif][]  
![ExpandedSubBlockEnd.gif][] \}  
![InBlock.gif][]if (k == \_coordCount)  
![InBlock.gif][]break;  
![InBlock.gif][]  
![InBlock.gif][]//5、否则需要重新调整资料点和群聚类的关系，调整完毕后再重新开始循环；  
![InBlock.gif][]//需要修改每个聚类的成员和表示某个数据属于哪个聚类的变量  
![InBlock.gif][]for (int j =0; j < \_k; j\++)  
![ExpandedSubBlockStart.gif][]\{  
![InBlock.gif][] \_clusters\[j\].CurrentMembership.Clear();  
![ExpandedSubBlockEnd.gif][] \}  
![InBlock.gif][]for (int i =0; i < \_coordCount; i\++)  
![ExpandedSubBlockStart.gif][]\{  
![InBlock.gif][] \_clusters\[\_nearestCluster\[i\]\].CurrentMembership.Add(i);  
![InBlock.gif][] \_clusterAssignments\[i\] = \_nearestCluster\[i\];  
![ExpandedSubBlockEnd.gif][] \}  
![InBlock.gif][]  
![ExpandedSubBlockEnd.gif][] \}  
![InBlock.gif][]  
![ExpandedSubBlockEnd.gif][] \}  
![InBlock.gif][]  
![ExpandedSubBlockStart.gif][]///<summary>  
![InBlock.gif][]/// 计算某个数据离哪个聚类最近  
![InBlock.gif][]///</summary>  
![InBlock.gif][]///<param name="ndx"></param>  
![ExpandedSubBlockEnd.gif][]///<returns></returns>  
![InBlock.gif][]int nearestCluster(int ndx)  
![ExpandedSubBlockStart.gif][]\{  
![InBlock.gif][]int nearest =\-1;  
![InBlock.gif][]double min = Double.MaxValue;  
![InBlock.gif][]for (int c =0; c < \_k; c\++)  
![ExpandedSubBlockStart.gif][]\{  
![InBlock.gif][]double d = \_distanceCache\[ndx,c\];  
![InBlock.gif][]if (d < min)  
![ExpandedSubBlockStart.gif][]\{  
![InBlock.gif][] min = d;  
![InBlock.gif][] nearest = c;  
![ExpandedSubBlockEnd.gif][] \}  
![InBlock.gif][]  
![ExpandedSubBlockEnd.gif][] \}  
![InBlock.gif][]if(nearest==-1)  
![ExpandedSubBlockStart.gif][]\{  
![InBlock.gif][] ;  
![ExpandedSubBlockEnd.gif][] \}  
![InBlock.gif][]return nearest;  
![ExpandedSubBlockEnd.gif][] \}  
![ExpandedSubBlockStart.gif][]///<summary>  
![InBlock.gif][]/// 计算某数据离某聚类中心的距离  
![InBlock.gif][]///</summary>  
![InBlock.gif][]///<param name="coord"></param>  
![InBlock.gif][]///<param name="center"></param>  
![ExpandedSubBlockEnd.gif][]///<returns></returns>  
![InBlock.gif][]staticdouble getDistance(double\[\] coord, double\[\] center)  
![ExpandedSubBlockStart.gif][]\{  
![InBlock.gif][]//int len = coord.Length;  
![InBlock.gif][]//double sumSquared = 0.0;  
![InBlock.gif][]//for (int i = 0; i < len; i++)  
![InBlock.gif][]//\{  
![InBlock.gif][]// double v = coord\[i\] - center\[i\];  
![InBlock.gif][]// sumSquared += v \* v; //平方差  
![InBlock.gif][]//\}  
![InBlock.gif][]//return Math.Sqrt(sumSquared);  
![InBlock.gif][]  
![InBlock.gif][]//也可以用余弦夹角来计算某数据离某聚类中心的距离  
![InBlock.gif][]return1\- TermVector.ComputeCosineSimilarity(coord, center);  
![InBlock.gif][]  
![ExpandedSubBlockEnd.gif][] \}  
![ExpandedSubBlockStart.gif][]///<summary>  
![InBlock.gif][]/// 随机初始化k个聚类  
![ExpandedSubBlockEnd.gif][]///</summary>  
![InBlock.gif][]privatevoid InitRandom()  
![ExpandedSubBlockStart.gif][]\{  
![InBlock.gif][]for (int i =0; i < \_k; i\++)  
![ExpandedSubBlockStart.gif][]\{  
![InBlock.gif][]int temp = \_rnd.Next(\_coordCount);  
![InBlock.gif][] \_clusterAssignments\[temp\] = i; //记录第temp个资料属于第i个聚类  
![InBlock.gif][] \_clusters\[i\] =new WawaCluster(temp,\_coordinates\[temp\]);  
![ExpandedSubBlockEnd.gif][] \}  
![ExpandedSubBlockEnd.gif][] \}  
![ExpandedBlockEnd.gif][]\}   
![None.gif][]  
![None.gif][]

以下是聚类实体类的定义

![None.gif][] internal  class  WawaCluster  
![ExpandedBlockStart.gif][] \{  
![InBlock.gif][]public WawaCluster(int dataindex,double\[\] data)  
![ExpandedSubBlockStart.gif][]\{  
![InBlock.gif][] CurrentMembership.Add(dataindex);  
![InBlock.gif][] Mean = data;  
![ExpandedSubBlockEnd.gif][] \}  
![InBlock.gif][]  
![ExpandedSubBlockStart.gif][]///<summary>  
![InBlock.gif][]/// 该聚类的数据成员索引  
![ExpandedSubBlockEnd.gif][]///</summary>  
![InBlock.gif][]internal List<int> CurrentMembership =new List<int>();  
![ExpandedSubBlockStart.gif][]///<summary>  
![InBlock.gif][]/// 该聚类的中心  
![ExpandedSubBlockEnd.gif][]///</summary>  
![InBlock.gif][]internaldouble\[\] Mean;  
![ExpandedSubBlockStart.gif][]///<summary>  
![InBlock.gif][]/// 该方法计算聚类对象的均值  
![InBlock.gif][]///</summary>  
![ExpandedSubBlockEnd.gif][]///<param name="coordinates"></param>  
![InBlock.gif][]publicvoid UpdateMean(double\[\]\[\] coordinates)  
![ExpandedSubBlockStart.gif][]\{  
![InBlock.gif][]// 根据 mCurrentMembership 取得原始资料点对象 coord ，该对象是 coordinates 的一个子集；  
![InBlock.gif][]//然后取出该子集的均值；取均值的算法很简单，可以把 coordinates 想象成一个 m\*n 的距阵 ,  
![InBlock.gif][]//每个均值就是每个纵向列的取和平均值 , //该值保存在 mCenter 中  
![InBlock.gif][]  
![InBlock.gif][]for (int i =0; i < CurrentMembership.Count; i\++)  
![ExpandedSubBlockStart.gif][]\{  
![InBlock.gif][]double\[\] coord = coordinates\[CurrentMembership\[i\]\];  
![InBlock.gif][]for (int j =0; j < coord.Length; j\++)  
![ExpandedSubBlockStart.gif][]\{  
![InBlock.gif][] Mean\[j\] \+= coord\[j\]; // 得到每个纵向列的和；  
![ExpandedSubBlockEnd.gif][] \}  
![InBlock.gif][]for (int k =0; k < Mean.Length; k\++)  
![ExpandedSubBlockStart.gif][]\{  
![InBlock.gif][] Mean\[k\] /= coord.Length; // 对每个纵向列取平均值  
![ExpandedSubBlockEnd.gif][] \}  
![ExpandedSubBlockEnd.gif][] \}  
![ExpandedSubBlockEnd.gif][] \}  
![ExpandedBlockEnd.gif][]\}   
![None.gif][]  
![None.gif][]

计算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.html  
TF/IDF实现  
http://www.codeproject.com/KB/cs/tfidf.aspx  
  
源码下载：[WawaTextCluster.zip][]

[Link 1]: https://blog.csdn.net/u013378306/article/details/52687694
[None.gif]: /images/20220524/4307c27bf7d84420aa2a931fedf74caf.png
[ExpandedBlockStart.gif]: /images/20220524/b653554dbfcf435c83494ab34db66636.png
[InBlock.gif]: /images/20220524/59afec19346b4861b97510bf95924b85.png
[ExpandedSubBlockStart.gif]: /images/20220524/8f22da44a19c49679a1b90c85490649d.png
[ExpandedSubBlockEnd.gif]: /images/20220524/26dbb1f8b6a846439c9d75b62aa3aaef.png
[ExpandedBlockEnd.gif]: /images/20220524/f7ea4429c25847d9806eebfb93a5f79d.png
[dot.gif]: /images/20220524/1d215dfa5baf46589f9f0f4b4069f265.png
[WawaTextCluster.zip]: http://files.cnblogs.com/onlytiancai/WawaTextCluster.zip