基于文本的信息自动聚类的算法很多，我以前介绍过一些，比较流行的算法有我以前提到的KNN和SVM，在过去的一段时间里，空闲的时间基本上都用来研究能否快速的实现自动聚类。上周终于完成了文本自动聚类的兼并算法，能够相对快速的实现文本信息的自动聚类。下面就介绍一下信息自动聚类的实现，希望能够帮助大家了结google news 的新闻如何进行自动聚类工作。
1] 什么是简并算法
简并算法是指在文本信息空间内寻找任何两个最相关的文本信息，并将之简并成一个文本信息，从而实现信息数量的收缩。
2] 如何实现
1. 简并算法的实现通过比较整个信息空间内的所有文本的相关性（相识性），得到相互之间的相关性后两两(注)进行配对。配对的要求是这两个文本信息的相关性最大，例如A 找到了文档B，那么B 也一定找到最相关的文档就是A 。
注，某些情况A 最相近的文档是C ，那么B 而B 最相关的文档也是C ，存在一种情况，A,B,C 三者之间自恰，就是构成空间信息最近的一个三角形。
2. 得到了最相似文档后，将只进行平均化，或者简单的迭加。
3. 信息空间中独立信息的数量会减少到原来的一半以下，然后重复实现1 的过程，在进行兼并。
4. 信息最后简并到唯一的一个信息，就是整个信息文本的平均值。
5. 画出信息树的结构，就能够根据要进行规模不同大小的聚类进行自动聚类了。
如下的信息树结构是对我进行测试的一个小样本大约70个文档进行信息简并算法得到的图像：
完整的树结构可以看这里：
从上图可以看出，经过自动聚类后类别0,2具有最相近的关系然后进行兼并后和类别5进行了简并，然后在和类别6进行了简并，最终和另外一支的信息进行了最后的简并，聚成唯一的全部的信息简并。
图中矩阵的明暗表明了信息之间的相关程度，矩阵经过对角化后可以明显看到聚类的效应。
本试验的文本信息和分类结果下载：
下面是我进行文本聚类的文档公布下载『一共70个文档』，我产生的文本的相关性的矩阵下载。
简并算法我也实现在大样本的聚类上，大约2000个文档进行自动的分类后进行聚类的运算时间大约为2个小时「抱歉，我基本上是用shell scripts 和perl scripts 来写代码」，如果先进行聚类在分类大约要5个小时。
最耗时间的过程是产生相关性矩阵，2000X2000有400万的元素，当然不会那么快了。
经过实践，简并算法的自动聚类还有很多需要改进的地方，例如最关键的是信息之间的相识性的计算，我采用了最大似然(Maximum Likelihood Fitting)的拟合，在计算上比较消耗时间，以后可以改变成其它的算法。
文本的自动聚类可以看到Google New上面已经相当成熟，这里的简并算法未来将为博客中国的新闻搜索提供支持，希望能够提供较好的机器新闻。
- 卢亮 2005年2月20日
联系客服
