基于文本的聚类算法研究毕业论文(编辑修改稿)

基于文本的聚类算法研究毕业论文(编辑修改稿)内容摘要：

本上参数的好坏对结果的影响都比较显著。 从这三个步骤可以 看出影响文本聚类分析效果的因素包括四个方面：文本表示模型、距离度量方法、算法模型和参数优化。 参数的设定主观性比较强，如何设定才是一个好的参数缺乏有效的方法，利用本文中实现的聚类算法包和聚类评价方法可以通过指标的变化曲线图寻找算法的最佳参数。 文本表示模型 在实际的文本聚类分析研究，将实际文本内容变成机器内部表示结构的方法多种多样，可以用词、字、短语、 nGram、 显著性短语等形成向量、树等结构。 在经典的研究中通常利用特征 (Term，包括字、词、词组等 )的词频信息建立文本向量，通过文本向量与文本向量之间 的相似度来进行聚类分析。 文本表示包括两个问题：表示与计算。 表示特指特征的提取，计算指权重的定义和语义相似度的定义。 特征提取包括特征的定义和筛选，特征定义和筛选考虑以什么作为文本的特征，并不是所有的词和字都要求或者可以成为特征。 特征的权重定义及特征结构上的相似度度量可以选取不同的模型，如向量空间模型、概率模型、语言模型等。 文本表示是文本聚类的第一步，该步骤的变化很多，对最终聚类效果的影响也不尽相同。 文本表示本质上是对原始文本进行转换，使之在机器上可形式化描述、可计算。 特征定义与筛选可以采用不同的特征选择方法 ，可利用 NGram、 PAT 树提取特征、可利用 LSI 降维转化特征、也可利用语义词典基于文本的聚类算法研究 5 WordNet 或者 HowNet 定义更复杂的特征结构。 关于特征定义与筛选可以参考自然语言处理领域中的相关研究，这里不详细介绍。 本节接下来主要介绍信息检索和文本分析处理中经常用到的几个检索模型，这几个检索模型根据不同的理论假设推导、定义了不同的特征权重计算方法与语义相似度计算方法，是文本表示模型的重要组成部分。 布尔模型 布尔模型是基于集合论与布尔代数之上的一种简单模型，主要应用于信息检索中。 在布尔模型中，一个文档表示成 文档中出现的特征的集合，也可以表示成为特征空间上的一个向量，向量中每个分量权重为 0 或者 1，这种布尔模型称为经典布尔模型。 经典布尔模型中查询与文档的相关性只能是 0或者 1，满足查询query 中的所有逻辑表达式的文档被判定相关，不满足的被判定为不相关。 经典布尔模型只能用于信息检索中计算用户查询与文档的相关性，而无法利用该模型计算两个文档更深层面的相似度，无法在更多的文本处理应用中使用。 在经典布尔模型基础上，研究人员又提出了扩展布尔模型 (Extended Boolean Approach)，重新定义了 And与 Or 操 作符成为多元操作符，使相关性可以成为 [0,1]之间的数。 向量空间模型 Salton 教授提出的向量空间模型简称 VSM 模型 (Vector Space Model)，是信息检索领域中经典的检索模型。 向量空间模型将文档表示成一个向量，向量的每一维表示一个特征，这个特征可以是一个字、一个词、一个 ngram或某个复杂的结构。 通过对文档 的解析处理可以得到这些特征。 通常情况下用向量空间模型中的向量表示文档时，需要对文档进行切分 (中文分词、英文通过词的分界符识别单词 )、停用词处理、英文词的词形还原或者提取词干 (Stemming)，经过若干个处理步骤后，基本上就可以得到一系列词，将这些词作为文档的特征。 所有的这些词构成一个“空间”，每个词对应着空间中的一维。 每个文档可以用文档中的词来表示，这些词及其对应的权重构成一个向量。 文档对应特征空间中的一个向量，对应特征空间中的一个点。 表 说明 VSM 模型中文档与向量空间之间的映射关系。 基于文本的聚类算法研究 6 表 VSM模型中文档与向量空间之间的映射关系 文本 相似度计算 文本相似度计算是自然语言处理、 Web 智能检索、文本分类和文本聚类研究中的一个基本问题。 一个文本聚类分析过程的质量取决于对度量标准的选择。 因此，在研究聚类算法之前，先要讨论其度量标准。 文本相似度是用来衡量文本之间相似程度大小的一个统计量。 文本相似度一般定义为界于 0 和 1 之间的一个值。 如果两文本之间相似度为 1，则说明这两个文本对象完全相同；反之，则说明两文本没有相似之处。 样本间相似度 在向量空间模型中，文本相似 性的度量方法很多，主要有内积法、 Dice 系数法、余弦法和距离度量法等。 通常在文本向量中，最常使用的相似度计算公式就是两个文本向量之间的“内积”运算，其定义为： 系数法 弦法 基于文本的聚类算法研究 7 上述各公式中， Sim(di,dj)表示文本 di 和 dj 之间的相似程度，分 Wki,Wkj分别表示文本 di 和 dj 的第 k 个特征项的权重， n 为文本特征项数。 Sim值越大表示两个文本越相似， Sim越小则表示两个文本区别越大。 在文本相似度计算中，我们也可以用两个文本之间的距离来度量文本之间 的相似程度。 常使用的距离公式如下： 公式中， Dis(di,dj)表示文本向量 di 和 dj 在向量空间的距离， Wki,Wkj分别表示文本的第 k 个特征项的权重，参数 p 决定了选择的是哪种距离计算。 (1) 当 p=1 时 (2) 当 p=2 时 这就是欧式距离，也就是向量空间中的直线距离。 簇间相似度 在聚类分析中，我们还需要衡量类与类之间的相似度，实现类与类之间的合并或拆分。 为了衡量文本集合之间的相似度，常见的方法有：最小距离、最大距离、平均距离、质心法、离差平方和等。 基于文本的聚类算法研究 8 文本聚类算法 聚类分析作为一个活跃的研究 领域，已经出现了很多聚类算法，总体上聚类算法可分为基于划分的方法、基于层次的方法、基于密度的方法、基于网格的方法等。 每种算法都有各自的优缺点，都有其适用的领域，并不是每一类算法都适合于文本聚类，我们必须根据文本数据的特点对聚类算法进行分析选择。 基于划分的方法 基于划分的聚类算法（ Partitioning Method）是文本聚类应用中最为普遍的算法。 方法将数据集合分成若干个子集，它根据设定的划分数目 k 选出 k 个初始聚类中心，得到一个初始划分，然后采用迭代重定位技术，反复在 k 个簇之间重新计算每个簇的 聚类中心，并重新分配每个簇中的对象，以改进划分的质量。 使得到的划分满足“簇内相似度高，簇间相似度小”的聚类原则。 典型的划分聚类方法有 kmeans 算法 [36]和 kmedoids 算法，两者的区别在于簇代表点的计算方法不同。 前者使用所有点的均值来代表簇，后者则采用类中某个数据对象来代表簇。 为了对大规模的数据集进行聚类，以及处理复杂形状的聚类，各类改进的划分算法逐渐增多。 基于划分方法的优点是运行速度快，但该方法必须事先确定 k 的取值。 算法容易局部收敛，且不同的初始聚类中心选取对聚类结果影响较大。 为此，应用最广泛 的 kmeans 算法有很多变种，他们可能在初始 k 个聚类中心的选择、相似度的计算和计算聚类中心等策略上有所不同，最终实现聚类结果改进的目标。 基于层次的方法 基于层次的聚类算法（ Hierarchical Method）又叫“分级聚类算法”或“树聚类”，它通过分解给定的数据对象集来创建一个层次。 这种聚类方法有两种基本的技术途径：一是先把每个对象看作一个簇，然后逐步对簇进行合并，直到所有对象合为一个簇，或满足一定条件为止；二是把所有对象看成一类，根据一些规则不断选择一个簇进行分解，直到满足一些预定的条件 ，如类的数目达到了预定基于文本的聚类算法研究 9 值，或两个最近簇的距离达到阈值等。 前者称为自下而上的凝聚式聚类，后者称为自上而下的分裂式聚类。 在文本聚类中，最常见的是凝聚的层次聚类算法。 使用该算法可以得到较好的聚类结果，而且该方法无需用户输入参数；但是层次聚类算法的时间复杂度比较高，达到了 O(n2)，对于大规模的文本集合，有其不适用性。 此外，在层次聚类算法中，一旦两个簇在凝聚和分裂后，这个过程将不能被撤销，簇之间也不能交换对象。 如果某一步没有很好的选择要凝聚或者分裂的簇，将会导致低质量的聚类结果。 基于密度的方法 绝大多 数划分算法都是基于对象之间的距离进行聚类，这类方法只能发现圆形或球状的簇，较难发现任意形状的簇。 为此，提出了基于密度的聚类算法（ DensityBased Clustering Method），其主要思想是：只要邻近区域的对象或数据点的数目超过某个阈值，就继续聚类。 即对给定类中的每个数据点，在一个给定范围的区域中至少包含某个数目的点，这样就能很好的过滤掉“噪声”数据，发现任意形状的簇。 其基本出发点是，寻找低密度区域分离的高密度区域。 具有代表性的方法是 DBSCAN（ Density Based Spatial Clustering of Applications with Noise），它是将密度足够大的那部分记录组成类，可以在带有“噪声”的空间数据库中发现任意形状的聚类，但它需要用户主观来选择参数，从而影响了最终的聚类结果。 基于密度的聚类算法在当前的文献中较少被用于文本聚类中。 这是由于文本间的相似度不稳定，同属一簇的文本，有些文本间的相似度较高，所以密度高；有些相似度较低，所以密度低。 如果根据全局的密度参数进行判断，显然是不适合的。 并且密度单元的计算复杂度大，需要建立空间索引来降低计算量，且对数据维数的伸缩性 较差。 基于网格的方法 基于网格的算法（ GridBased Clustering Method）把对象空间量化为有限数目的单元，形成了一个网络结构。 所用的聚类操作都在整个网络结构即量化的空间基于文本的聚类算法研究 10 上进行。 这种方法的一个突出的优点就是处理速度很快，其处理时间独立于数据对象的数目，只与量化空间中的每一维的单元数目有关。 此外，它还可以处理高维数据。 代表算法有统计信息网格法 STING 算法、聚类高维空间法 CLIQUE 算法、基于小波变换的聚类法 WAVECLUSTER 算法。 STING（ Statistical Information Grid），利用了存储在网格中的统计信息，它不但能并行处理且能增量更新，因而效率很高，缺点是簇的质量和精确性欠佳。 WaveCluster（ Clustering Using Wavelet Transformation）是一种多分辨率的聚类算法。 其主要优点是能有效地处理大规模数据集；能发现任意形状的簇；能成功地处理孤立点；对于输入的顺序不敏感；不要求指定任何参数；且效率和聚类质量都比较高。 CLIQUE（ Clustering in Quest）是一种将基于密度的方法与基于网格的方法相结 合的算法，能有效处理大型数据库的高维数据。 它对输入顺序不敏感，无需假设任何规范的数据分布。 另外，它还具有良好的可伸缩性。 但由于方法大大简化，聚类结果的精确可能降低。 基于模型的方法 基于模型的算法（ ModelBased Clustering Method）试图优化给定的数据和某些数学模型之间的适应性。 这样的算法经常是基于这样的假设，数据是根据潜在的概率分布生成的。 它通过为每个聚类假设一个模型来发现符合相应模型的数据对象。 根据标准统计方法并综合考虑“噪声”或异常数据，该方法可以自动确定聚类个数，从 而得到鲁棒性较好的聚类方法。 基于模型的算法主要有两类，分别为统计学方法和神经网络方法。 大多数的概念聚类采用的是统计的方法，即在决定一个类时，用可能性的描述语句，典型的代表就是 COBWEB，它是一个通用且简单的聚类方法。 基于神经网络的聚类方法是将每一个类看作一个标本，它是这个类型的“典型”，但不需要和某个具体的对象或例子相对应。 根据新对象和这个标本之间的距离，就可以将这个对象进行分类了。 如基于 SOM 的文档聚类方法在数字图书馆等领域得到了较好的应用。 聚类分析算法众多，应用于文档的聚类分析算法也种类繁多，基于文本的聚类算法研究 11 如何评 价文档聚类分析的效果，目前还没有一个确定的说法。 在实际的应用中一般都是实现几种算法，然后用人工判断的方法去选择合适的算法以及算法相对应的参数。 这么多的算法虽然带来了更多的选择，但同时也带来了应用上的困难，因此有必要在一个统一的尺度上来衡量一些算法并对他们做出评价。 本章小结 本章主要介绍了影响文本聚类结果的三方面主要因素：文本表示模型、相似度计算方法及聚类算法。 文本聚类过程中每个步骤都有可能影响最终的聚类效果，各方面因素变化情形众多，在实际研究和工程应用中，聚类评价工作困难重重。 为了更好地评价聚类结果 ，我们在下一章将详细介绍已有的文本聚类评价方法，比较各自的优缺点。 基于文本的聚类算法研究 12 第三章 k均值聚类算法 K均值聚类算法的思想 K均值聚类算法的基本思想 一九六七年，麦克奎因 [B. Mac Queen]提出了 K均值聚类算法，用来处理数据聚类的问题，该种算法由于其算法简便，又很早提出，因此在科学和工业领域的应用中影响力极为广泛。 该算法首先随机选取 k个数据点作为 n个 簇的初始簇中心，集合中每个数据点被划分到与其距离最近的簇中心所在的类簇之中，形成了 k 个。