基于文本的信息自动聚类的算法很多，我以前介绍过一些，比较流行的算法有我以前提到的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...
对自动聚类又进行了测试，发现sliding window可以进行简化，实现简并算法，算是一个突破吧，因此重写这一章。 LL 2004/11/22 有了良好的分类机制，才能够对信息进行有效的聚类。 聚类采取自动的方法基本上基本上有三种： 1] 现有的依靠大量样本进行NNet训练后进行单次模糊模式识别的方法。 方法的特长是能够快速的准确的进行自动聚类，缺点是需要大量的样本进行预先的训练。 防止过度训练和如何处理误差等变得非常关键。 类似的机制还有 Knn，SVM和贝叶斯统计法，回头细致介绍。 2] 平移算法，或者也叫卷积（自相关）算法。 Corr= Intergal( f(x)*f(x-t) dt ) Clusty 的自动聚类就是采用的平移算法。 平移算法的特点是计算迅速，简单易用。 缺点是计算的次数和信息的数量的平方成正比：N^2/2 3] Sliding Window以及兼并算法 sliding window方法根据信息间的夹角，能非常有效的发现一簇信息，并且控制窗口的大小可以来订制聚类后信息的相识度。 Sliding window的优点是非常精确，可调节性强。 缺点是非常繁琐，所计算的次数和信息空间的维数的阶数成正比，例如1000维，大约要计算10^1000 次，天文数字。 简并算法：在对sliding window进行了分析后，可以采用一种简并算法来快速收敛。简并算法是先找到任何两个信息之间的最小夹角，然后进行简并，成为一个信息矢量，这样经过若干次的简并后就收缩到非常少的信息矢量上。而这些较少的信息矢量的夹角都比较大，是不同类别的信息矢量，即实现自动聚类。 举例说明：1000组的信息进行简并处理，六次就可以收缩到15个分类里面，而六次所需要的计算量大约为60万次，基本上不会有难处了。...
信息依照体特征进行分类，通常有两种分类方法： 1] 信息分类按照定义好的人为的划分进行分类，例如：教育，娱乐，商业等等。 2] 自动类聚依照信息在空间的夹角，并且对信息进行 Cluster 的寻找。 分类方法的；实例： 采用的方法比较常用的是”Sliding-Window“的做法，就是用一个大小合适的窗口在信息空间的球表面进行移动，当这个Window里包涵了较大的信息矢量个数的话，就说明这里是一个信息Cluster，或者叫做 info-jet. 这个window在这个位置一定是一个最大值，扫描到了信息cluster的中心，扩展可以得到整个cluster....
本章主要介绍信息空间和信息的形状 keywords: 信息空间 Information space, 信息的形状 information shape 1] 什么是信息空间 信息空间是由一组信息失 (information base vector) 构成的一个能够将需要表达的信息完全含概其中的一个多维向量空间。 正如上一章所阐述的概念，任何一个信息矢量可以通过信息基失的组合得到，也就是说信息在信息空间里具有线性的表达方式。 2] 什么是信息的形状 the shape of information 是对一个信息在信息空间里的一个总体概括。信息的形状与信息所表达的内容息息相关，我在这里对信息的形状进行如下的分类： 以信息A 为例 A = a_1 * i_1 + a_2 * i_2 +..+ i_n*a_n 其中 a_j = A点乘i_j ， j从1到n。 (1) 直线型信息 这类信息表示这个信息基本上投影在一个信息基失上，表象为整个信息同一个信息基失平行。 A = i*||A|| (2) 平面型信息 这类信息可以通过两个基失进行表达，因此是平面型的： A = ||A||(Sin(theta) * i + Cos(Theta) * j ) (3) 锥型信息 这类信息投影在3个或者3个以上的基失空间 (4) 球形型信息 这类信息投影在所有的基失空间，且基本均匀分布。 现实中的信息都是有以上4类的组合而成，真正完全属于以上（1,2,4）类的信息并不多见，而属于锥形的信息就比较常见。...
本章讲述两个问题：信息的夹角和信息的表达 1] 信息的夹角 Theta(I_A, I_B) = sqrt(arccos( Relation(I_A, I_B))) 信息在上述表达式里是矢量，信息之间的夹角表现为信息之间的点乘。而点乘的结果表现为信息之间的关系(见上一章里面信息的相关性)的开方，由此定义信息之间的夹角应是从0度到90度之间的数值： 0度，表明信息平行，或者乘平行的信息，说明信息之间完全相关。 90度，表明信息正交，正交的信息，说明信息之间没有相关性。 由此推算unix 和 Linux 之间的夹角为：73度。 2] 信息的表达： 信息失的概念： 对于任何信息失，对其取模可以得到信息失的长度，M_A=||I_A|| ，那么单位信息失表达为： i_A = I_A/M_A = I_A/||I_A|| 适当的选取信息失，从而可以选择单位信息失，那么任何的信息矢量可以通过单位信息失的组合得到。 我们首先来假设建立如下的一组信息失： i_1, i_2, i_3,... i_n. 即整个信息空间有n 维，并由信息失(i_1,..,i_n)来构造，那么任何这个信息空间的信息失A可以写成如下的格式： A = a_1 * i_1 + a_2 * i_2 +..+ i_n*a_n 其中 a_j = A点乘i_j ， j从1到n。...
第一章 数字信息概述 讲述数字信息的历史，特征。。。（略） 第二章 信息的相关性 信息的相关性在没有良好的方法来进行计算其相关性的时候，可以采用信息空间差值法： 为了简单期间，我们架设A元素得到了A_n个结果，搜索B得到了B_n个结果，联合A + B 得到了AB_n 个结果，那么A 与 B 的相关性可以这么定义： Correlation = (AB_n)/(A_n + B_n - AB_n)...
《数字信息搜索》 卢亮 一部指导搜索引擎理论的书 引言，打算业余的时间将这本书的骨架写出来，至于其中的血肉，有空了再补充上。这里基本上最主要的内容是数学＋信息学，基本上是我这几年的工作。 因此基本上以理论知识为主，当然也会有一些实用的例子，如果您问“如何提高网站的排名？”或者“如何提高被搜索到的次数？”，抱歉，这些问题不在我的回答范围内，我这里要写的是关于搜索的理论，已经被搜索引擎用到的和没有用的到，已经公开的或者未公开的知识。 备注：转载和联接请注明出处。...