论文部分内容阅读
【摘要】 作为Web挖掘的一个重要分支，文本挖掘应用非常广泛。介绍了Web文本的定义、一般的文本聚类挖掘过程及常见的几种聚类算法。
【关键词】 文本挖掘；聚类算法
【中图分类号】：G623.58【文献标识码】：B 【文章编号】：1009-9646(2008)05-0106-01
Web上包含有大量页面，其中文本占到了整个信息量的80%以上。文本聚类是指应用数据挖掘、机器学习等技术对文本进行自动分类的过程，即将文本集合分类成多个簇，使得在同一个簇中的文本内容具有较高的相似度，而不同簇中的文本内容差别较大。
作为一种无指导的机器学习方法，聚类由于不需要训练过程，以及不需要预先对文档手工标注类别，因此具有一定的灵活性和较高的自动化处理能力，已经成为对文本信息进行有效地组织摘要和导航的重要手段，为越来越多的研究人员所关注。
1 文本的特征表示
文本挖掘的基础是文本的特征表示。文本特征是关于文本的元数据。万维网协会W3C(http://www.w3.org)[1]制定的XML[2]等规范提供了对Web文档资源进行描述的语言和框架，在此基础上，可以从半结构化的Web文档中抽取特征。
文本的表示大多采用向量空间模型(VSM,Vector Space Model)[3]。VSM的基本思想是把每一个特征词对应特征空间的一维，用向量来表示文本。如文本di就可以表示为：
V（di）=(Wil，Wi2，…，Wik，…，Wim)
其中Wik为第i个特征项的权重，表示该特征项在文本中的重要程度，通常是指其在文档中出现的频率，用函数ftk
(di)表示。
3 文本的聚类挖掘
3.1 文本预处理。预处理的主要目的是抽取代表文本特征的元数据(特征项)，用结构化的形式保存。文本预处理包括去除标记、去除停用词、词根还原以及在需要的情况下进行分词处理。去除标记主要是指去掉一些特殊的标记，去除停用词,主要是去掉一些对文章的内容没有什么表现力的字词。
3.2特征降维。构成文本的词汇，数量是相当大的，因此表示文本的向量空间的维数也相当大，可以达到几万维，因此要进行维数压缩。常用的降维方法有PCA，LSA等，利用词与词之间的依赖关系来合并这些词，但往往需要很大的内存空间。
3.3 聚类处理。聚类方法的选择取决于数据的类型、聚类目的和应用，目前常用的有二类：平面划分聚类、层次聚类。
3.3.1 划分聚类算法。平面划分聚类法通过优化一个评价函数把数据集合水平地分割为k个簇，然后采用一种迭代的重定位技术，通过对象在划分间的移动来改进划分。
对于给定的文档集合 D={d1,d2,…… ,dn}，划分聚类的步骤如下：
（1） 确定要生成簇的数目k；
（2） 根据某个规律生成 k 个群集中心作为群集的种子 S={sl,s2,……,sn }；
（3） 对 D中的每个文档di，依次计算它与各个种子sj的相似度sim(di,sj)。相似度可以根据一个簇内对象的平均值来计算（K-Means算法），也可以根据簇中位置最中心的对象值计算（K-Medic算法）。
（4） 选取具有最大相似度的种子,并将di化归为以sj为群集中心的簇cj，从而构成了D的一个新的群集C={c1,c2,……,ck }；
（5） 重复上述步骤，直到群集相对稳定。
该方法的执行速度较快，但是必须事先确定 k 的取值，且选取种子的质量对聚类结果影响较大，聚类效果最好的情况是选取的簇间相似度接近于球形时。
3.3.2 分层次聚类。分层次聚类则是由不同层次的平面划分组成，层次之间的分割具有嵌套的关系。
对于给定的文档集合 D={d1,d2,……,dn}，层次聚类法的具体步骤为：
1) 将 D 中的每个文件di看作是一个具有单个成员的簇ci={di}，这些簇构成了D的一个群集 C={c1,c2,……,cn }；
2) 计算 C 中每对簇(ci,cj)之间的相似度 sim(ci,cj)；
3) 选取具有最大相似度的簇对 maxsim(ci,cj)，并将 ci 和 cj 合并为一个新的簇 ck=ciUcj ，得到 D 的一个新的群集 C={c1,c2,? ,cn-1 }；
4) 重复上述步骤，直到 C 中只有一个簇。
该过程构造出一棵生成树，包含了簇的层次信息以及全部簇之间的相似度，准确度高。但在每次合并时，需要全局地比较所有簇之间的相似度，并选择出最佳的两个簇，因此执行速度慢，不适合大量文档的集合，并且不能产生相交簇。
3.4 聚类结果的应用。文本聚类的主要用途有：
（1）作为多文档自动文摘等自然语言处理应用的预处理步骤。比较典型的例子是哥伦比亚大学开发的多文档文摘系统Newsblaster。Newsblaster将每天发生的重要新闻文本进行聚类处理，并对同主题文档进行冗余消除、信息融合、文本生成等处理，从而生成一篇简明扼要的摘要文档；
（2）对搜索引擎返回的结果进行聚类，使用户迅速定位到所需要的信息。比较典型的系统则有vivisimo（http://www.vivisimo.com）等。用户输入检索关键词，系统对检索到的文档进行聚类处理，并输出各个不同类别的简要描述，用户只需关注比较有希望的主题。它还可以为用户二次检索提供线索；
（3）对用户感兴趣的文档（如用户浏览器cache中的网页）聚类，从而发现用户的兴趣模式，用于信息过滤和信息主动推荐等服务；
（4）文档集合的自动整理。如Scatter/Gather就是一个基于聚类的文档浏览系统。
5 结语
文本挖掘是一个非常活跃的研究领域，尤其以文本聚类应用十分广泛。快速高质量的文本聚类技术可以将大量文本信息精简成少量有用簇，这种技术能够提供导航/浏览机制，通过聚类驱动的降维或权值调整来改善性能，目前已成为文本挖掘的核心技术。
参考文献
[1] Jiawei Han.Micheline Kamber.数据挖掘概念与技术[M].北京:机械工业出版社.2001.3-6.328-332
[2] 韩家炜.孟小峰.王静.李盛恩.Web挖掘研究.计算机研究与发展.2001.4
[3] 朱明.数据挖掘.安徽:中国科学技术大学出版社.2002.5
[4] 杨学明.Web中文文本挖掘研究及实现.现代图书情报技术.2006.12
[5] 薛为民.陆玉昌.文本挖掘技术研究.北京联合大学学报(自然科学版).2005.12(19)
收稿日期：2008-5-1
注：“本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。”
【关键词】 文本挖掘；聚类算法
【中图分类号】：G623.58【文献标识码】：B 【文章编号】：1009-9646(2008)05-0106-01
Web上包含有大量页面，其中文本占到了整个信息量的80%以上。文本聚类是指应用数据挖掘、机器学习等技术对文本进行自动分类的过程，即将文本集合分类成多个簇，使得在同一个簇中的文本内容具有较高的相似度，而不同簇中的文本内容差别较大。
作为一种无指导的机器学习方法，聚类由于不需要训练过程，以及不需要预先对文档手工标注类别，因此具有一定的灵活性和较高的自动化处理能力，已经成为对文本信息进行有效地组织摘要和导航的重要手段，为越来越多的研究人员所关注。
1 文本的特征表示
文本挖掘的基础是文本的特征表示。文本特征是关于文本的元数据。万维网协会W3C(http://www.w3.org)[1]制定的XML[2]等规范提供了对Web文档资源进行描述的语言和框架，在此基础上，可以从半结构化的Web文档中抽取特征。
文本的表示大多采用向量空间模型(VSM,Vector Space Model)[3]。VSM的基本思想是把每一个特征词对应特征空间的一维，用向量来表示文本。如文本di就可以表示为：
V（di）=(Wil，Wi2，…，Wik，…，Wim)
其中Wik为第i个特征项的权重，表示该特征项在文本中的重要程度，通常是指其在文档中出现的频率，用函数ftk
(di)表示。
3 文本的聚类挖掘
3.1 文本预处理。预处理的主要目的是抽取代表文本特征的元数据(特征项)，用结构化的形式保存。文本预处理包括去除标记、去除停用词、词根还原以及在需要的情况下进行分词处理。去除标记主要是指去掉一些特殊的标记，去除停用词,主要是去掉一些对文章的内容没有什么表现力的字词。
3.2特征降维。构成文本的词汇，数量是相当大的，因此表示文本的向量空间的维数也相当大，可以达到几万维，因此要进行维数压缩。常用的降维方法有PCA，LSA等，利用词与词之间的依赖关系来合并这些词，但往往需要很大的内存空间。
3.3 聚类处理。聚类方法的选择取决于数据的类型、聚类目的和应用，目前常用的有二类：平面划分聚类、层次聚类。
3.3.1 划分聚类算法。平面划分聚类法通过优化一个评价函数把数据集合水平地分割为k个簇，然后采用一种迭代的重定位技术，通过对象在划分间的移动来改进划分。
对于给定的文档集合 D={d1,d2,…… ,dn}，划分聚类的步骤如下：
（1） 确定要生成簇的数目k；
（2） 根据某个规律生成 k 个群集中心作为群集的种子 S={sl,s2,……,sn }；
（3） 对 D中的每个文档di，依次计算它与各个种子sj的相似度sim(di,sj)。相似度可以根据一个簇内对象的平均值来计算（K-Means算法），也可以根据簇中位置最中心的对象值计算（K-Medic算法）。
（4） 选取具有最大相似度的种子,并将di化归为以sj为群集中心的簇cj，从而构成了D的一个新的群集C={c1,c2,……,ck }；
（5） 重复上述步骤，直到群集相对稳定。
该方法的执行速度较快，但是必须事先确定 k 的取值，且选取种子的质量对聚类结果影响较大，聚类效果最好的情况是选取的簇间相似度接近于球形时。
3.3.2 分层次聚类。分层次聚类则是由不同层次的平面划分组成，层次之间的分割具有嵌套的关系。
对于给定的文档集合 D={d1,d2,……,dn}，层次聚类法的具体步骤为：
1) 将 D 中的每个文件di看作是一个具有单个成员的簇ci={di}，这些簇构成了D的一个群集 C={c1,c2,……,cn }；
2) 计算 C 中每对簇(ci,cj)之间的相似度 sim(ci,cj)；
3) 选取具有最大相似度的簇对 maxsim(ci,cj)，并将 ci 和 cj 合并为一个新的簇 ck=ciUcj ，得到 D 的一个新的群集 C={c1,c2,? ,cn-1 }；
4) 重复上述步骤，直到 C 中只有一个簇。
该过程构造出一棵生成树，包含了簇的层次信息以及全部簇之间的相似度，准确度高。但在每次合并时，需要全局地比较所有簇之间的相似度，并选择出最佳的两个簇，因此执行速度慢，不适合大量文档的集合，并且不能产生相交簇。
3.4 聚类结果的应用。文本聚类的主要用途有：
（1）作为多文档自动文摘等自然语言处理应用的预处理步骤。比较典型的例子是哥伦比亚大学开发的多文档文摘系统Newsblaster。Newsblaster将每天发生的重要新闻文本进行聚类处理，并对同主题文档进行冗余消除、信息融合、文本生成等处理，从而生成一篇简明扼要的摘要文档；
（2）对搜索引擎返回的结果进行聚类，使用户迅速定位到所需要的信息。比较典型的系统则有vivisimo（http://www.vivisimo.com）等。用户输入检索关键词，系统对检索到的文档进行聚类处理，并输出各个不同类别的简要描述，用户只需关注比较有希望的主题。它还可以为用户二次检索提供线索；
（3）对用户感兴趣的文档（如用户浏览器cache中的网页）聚类，从而发现用户的兴趣模式，用于信息过滤和信息主动推荐等服务；
（4）文档集合的自动整理。如Scatter/Gather就是一个基于聚类的文档浏览系统。
5 结语
文本挖掘是一个非常活跃的研究领域，尤其以文本聚类应用十分广泛。快速高质量的文本聚类技术可以将大量文本信息精简成少量有用簇，这种技术能够提供导航/浏览机制，通过聚类驱动的降维或权值调整来改善性能，目前已成为文本挖掘的核心技术。
参考文献
[1] Jiawei Han.Micheline Kamber.数据挖掘概念与技术[M].北京:机械工业出版社.2001.3-6.328-332
[2] 韩家炜.孟小峰.王静.李盛恩.Web挖掘研究.计算机研究与发展.2001.4
[3] 朱明.数据挖掘.安徽:中国科学技术大学出版社.2002.5
[4] 杨学明.Web中文文本挖掘研究及实现.现代图书情报技术.2006.12
[5] 薛为民.陆玉昌.文本挖掘技术研究.北京联合大学学报(自然科学版).2005.12(19)
收稿日期：2008-5-1
注：“本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。”