基于相似度的文本聚类方法研究

摘要 随着计算机的广泛应用和Internet 的普及，人们所面对的信息量急剧增长。信息量的增加给人们带来方便，可同时也带来了一个信息过量的问题。面对浩如烟海、纷繁芜杂的信息，人们越来越希望能够在对已有的大量数据分析的基础上进行科学研究、商业决策或企业管理。 在现实世界中，文本是信息最重要的载体，事实上，研究表明信息有80%包含在文本文档中。面对大量无序的文本数据，为了便于工作的展开，人们经常遇到的一个问题就是，如何对文本进行分类、比较，评估文本的相关性和重要性，以及发现众多文本的模式与趋势。采用文本分类可以实现对大量文本的自动分类。文本分类是在分析文本内容的基础上将多篇文本分成一个或多个类别。财经类网页是我们日常生活中关注的主要内容。本文以财经类文本的聚类实现为研究实例，提出基于文本相似度向量的聚类方法。 关键词：相似度，聚类，财经目录摘要??? 2一、绪论??? 41.1问题的提出??? 41.2 课题开发背景??? 51.3 系统设计思想??? 7二、系统开发工具和开发平台??? 82.1 面向对象语言??? 82.2 关于VC++ 6.0??? 112.2.1编辑器方面的新特性??? 122.2.2、编译器、连接器和调试器方面的改进??? 132.3 系统运行环境??? 132.3.1软件运行平台??? 132.3.2硬件运行平台??? 13三、系统分析??? 143.1 文本建模方法??? 143.2 文本聚类算法分析??? 153.2.1 划分聚类算法??? 153.2.2 层次聚类算法??? 163.2.3 基于密度的聚类算法??? 163.2.4 基于模型的聚类算法??? 163.2.5 基于网格的聚类算法??? 17四、系统设计与实现??? 184.1 系统结构设计??? 184.2 界面设计??? 184.3 网页自动获取的实现??? 204.4 网页分析聚类的实现??? 21五、系统测试??? 225.1 测试??? 225.2 聚类效果分析??? 24结论??? 26致谢??? 27参考文献??? 28 课题开发背景 随着互联网的出现，大量的文本信息如潮水般不断涌现，网络已经成为一个庞大而杂乱无章的桌面图书馆。对海量的文献人们迫切需要能够自动实现文本的分类处理，在节省时间的同时更好的定位查找自己需要的文献。有效的信息检索需要有良好的索引和文本内容概括，文本聚类便是解决这类问题的一种手段。 文本聚类就是将一个训练文献集分成若干称为聚类簇（cluster）的子集，每个聚类簇中的成员之间具有较大的相似性，而聚类簇之间的文本具有较小的相似性。文本分类一般是通过统计方法或知识工程方法来实现的。知识工程方法需要编制大量的推理规则，因此其开发费用相当昂贵。相比之下，统计方法由于其简单的机制，为大多数实用文本分类系统所采用。在基于统计的各种分类方法中,它们的共同点是从文本中提取词汇信息，并以特征向量的形式来表示文本。基于以向量来表示的文本，聚类算法有很多种，本文是通过在特征向量中选取代表点来完成聚类的。在日常生活、生产、科研、工作中，经常要对被研究的对象分类。研究和处理给定对象分类的数学方法称为聚类分析（Clustering Analysis）。 聚类算法是数据挖掘中常用的方法之一。通常可以分为层次式和非层次式两种。本文介绍的是层次式聚类方法。其优点是聚类的形成一般依赖于数据，而不是通过用户预定义的聚类数得到。它通过对初始数据构造一个聚类层次来完成聚类。初始，输入的每个数据点被看成一个单独的聚类簇，然后将成对的聚类簇一一合并，同时依据各聚类簇中各对象间的最大距离应小于各聚类簇之间的最小距离的原则，在包含N 个对象的m 维单位空间中，对象间的平均距离为。按照“各聚类簇中对象间距离不应超过此标准，而各聚类簇之间距离不应低于此标准”规则，来结束聚类的。聚类簇合并的每一步，是合并距离最小的一对聚类簇。常用的聚类簇合并策略有：合并重心最为靠近的一对聚类簇；考察分属不同聚类簇的点之间的距离，并合并距离最小的一对数据点所对应的两个聚类簇；合并所有数据点间距离的平均值最小的两个聚类簇；考察分属不同聚类簇的点对之间的最大距离，合并该值最小的点对各自所在的聚类簇。如果待确定的各聚类簇内部数据点分布比较紧凑，且各聚类簇之间足够远离，这些策略都会得到较好的结果。然而，如果各聚类簇比较靠近（即使一些聚类簇之间是由离群数据连接的），或者聚类簇的形状不是超球形的且聚类簇的大小差异较大，则采用不同的合并策略产生的结果有相当大的差别。如果待聚类的资料为长条形结构，可能会使长条形聚类簇被割裂开，而且会将割裂的属于不同聚类簇的子聚类簇合并成一个单独的聚类。从以上的分析可以看出，基于重心的方法和考虑所有点的方法都不适用于非球形、任意形状的聚类。基于重心的方法缺点在于它仅仅用一个点（即聚类簇的重心）来代表整个聚类簇。对于一个大的聚类簇或是一个任意形状的聚类簇，它的各个子聚类簇的重心可能会距离相当远，这样就会导致这个聚类簇被分割开。另一方面，考虑所有点的方法用一个聚类簇内的所有点来代表它，这样就会使得聚类算法对离群数据极度敏感，而且数据点位置的微小变化都会导致算法结果有较大变动。此外大多数聚类学习算法，均需用户事先给定聚类个数K，且聚类结果对K 值大小都很敏感，不同K 值的聚类学习结果往往大相径庭，但就目前的状况来说，如何选择合适的K 值，本身就是一个难题 本文就K聚类方法进行了优化，通过相似度的计算，加强了K聚类算法的效果。 1.3 系统设计思想 一个方便用户使用的软件应该具备软件体积小，操作界面友好，基本功能稳定，运行速度较快，通过计算机技术及网络技术结合开发出能够进行网页分类功能的系统出来。 实用性：系统以用户需求为目标，以方便用户为原则。根据实际的需求情况，订造一套先进的局域网数据传输，从用户角度出发尽可能的方便用户使用，满足基本的用户需要，成为公司学校等通用的网络软件。 先进性：本设计将充分应用现有成熟的计算机技术、网络技术、软件开发技术。以VC 6.0为主要开发环境，其优秀的编码体制和强大的编译器是此系统的强力支柱。