February 20, 2005
简并算法：文本自动聚类算法的实现::[Source]
基于文本的信息自动聚类的算法很多，我以前介绍过一些，比较流行的算法有我以前提到的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日
参考文献：
Yiming Yang, S. Slattery and R. Ghani. A study of approaches to hypertext categorization (ps.gz) Journal of Intelligent Information Systems, Volume 18, Number 2, March 2002.
Yiming Yang and Xin Liu A re-examination of text categorization methods. Proceedings of ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR'99, pp 42--49), 1999.
Soft Clustering Criterion Functions for Partitional Clustering
Ying Zhao and George Karypis
(A poster paper appears in CIKM 2004)
Web Page Categorization and Feature Selection Using Association Rule and Principal Component Clustering
Jerome Moore, Eui-Hong (Sam) Han, Daniel Boley, Maria Gini, Robert Gross, Kyle Hastings, George Karypis, Vipin Kumar, and Bamshad Mobasher
Trackback
You can ping this entry by using http://www.wespoke.com/cgi-bin/mt/mt-tb.cgi/719
Comments
你的理论和实际水平都很高
受益良多
我正在做一个
贝叶斯论坛垃圾广告屏蔽演示系统
希望得到你的指导
http://www.domolo.com/domolo/bayes4bbs/index.aspx
我最近接手了一个项目，其中有一项要求就是要能实时搜索，不需要自动获取信息，我对算法没有什么研究，所以想向你请教一些关于算法的东西，获得一些指导，可以吗？
Posted by: qq at March 21, 2005 04:42 AM from 202.196.57.225我最近接手了一个项目，其中有一项要求就是要能实时搜索，不需要自动获取信息，我对算法没有什么研究，所以想向你请教一些关于算法的东西，获得一些指导，可以吗？
Posted by: qq at March 21, 2005 04:43 AM from 202.196.57.225我是做数字图像处理的，我觉得你这思想其实和影像匹配是相似的，所以我建议你看看模式匹配之类的资料！从而在算法上改进
Posted by: 永 at April 16, 2005 09:52 PM from 202.114.121.248你的这个图怎么这么眼熟？和我以前用的一个日本的open source软件很象。你是自己写的还是用别人的？
Posted by: bkt at April 23, 2005 09:42 PM from 80.237.140.233当然不是自己去写了, 你可以参考很多的画图软件, 我用的是clusto
Posted by: 6e at April 23, 2005 09:45 PM from 70.242.104.74我现在在做一个文本分类的毕业设计！想问下具体怎么实现阿？实在是没入门，我搞到了一个文本分类系统，不过只能用KNN和SVM算法的！具体怎么搞能给指点下吗？谢谢了！
Posted by: wanzhenyi at May 16, 2005 11:16 PM from 61.50.142.27我以前是搞关联规则的，毕业后听导师说现在的师弟们正在搞文本聚类，并且成绩斐然。所以对文本聚类有些感兴趣。希望在这里能够得到大家的指教。
Posted by: worrydog at May 18, 2005 03:09 AM from 211.154.11.3我现在在做一个关于搜索引擎的论文,找到的资料都太高深,还没自己的东西,搞得文章很空洞,我该在哪方面着手创新一下好呢?
Posted by: 冉冉 at June 10, 2005 05:34 PM from 220.194.195.129原来你就是用别人的软件跑了一下数据，也可以洋洋洒洒一篇，高！
Posted by: ssb at September 8, 2005 02:40 AM from 207.157.21.66hi,你们都是怎么找资料的阿，找的都是别人发表的文章，我怎么找不到
Posted by: jguan at November 22, 2005 10:46 PM from 220.249.248.117