CN102955857A - 一种搜索引擎中基于类中心压缩变换的文本聚类方法 - Google Patents

Abstract

本发明公开了一种搜索引擎中基于类中心压缩变换的文本聚类方法，该方法利用改进的tf-idf公式计算文本集中每个文档的词汇权重，计算初始类中心，挖掘同义词组和共现高频词组，计算词汇中心，依据初始类中心与各文档的相似度进行初次分类；根据标题词汇，文章长度，同义词，共现关联词等信息，压缩中心词汇，使得同一个词汇只出现在与其相似高的一些类中心里，利用新的聚类中心对文档集进行重新聚类。计算每个类的核心相似度，对最大的类进行分裂，对较小的类进行合并以产生新的类。对压缩，聚类，分裂操作进行迭代，直到类的个数收敛，且同一个类中的文本与类中心相似度到达一定阈值。本发明聚类精度明显高于传统的KMeans，DBSCAN等方法。

Description

一种搜索引擎中基于类中心压缩变换的文本聚类方法

技术领域

本发明属于文本挖掘，机器学习研究的技术领域，特别涉及一种搜索引擎中基于类中心压缩变换的文本聚类方法，通过结合同义词组，共现关联词组，词汇中心，类中心，标题内容，文档长度等多种因素，对文本集进行反复的聚类、分裂迭代方法来提高聚类精度。该方法适用于搜索引擎，信息检索系统。

背景技术

在现实世界中，文本是信息最重要的载体，事实上，研究表明信息有80％包含在文本文档中。特别是在互联网上，文本数据广泛地存在于各种形式，如新闻报道、电子图书、研究论文、数字图书馆、网页、电子邮件等等。文本聚类技术可以应用于信息过滤、个性化的信息推荐，使人们能够准确地检索到所需要的信息，缩短信息检索的时间。同时，文本聚类是不需训练集即可划分出类属的一种方法，它能够有效解决文本的自动划分问题。文本聚类由于不需要预先对文本手工标注类别，因此具有一定的灵活性和较高的自动化处理能力，已经成为对文本信息进行有效地组织、摘要和导航的重要手段。

目前已有的文本聚类方法大部分是基于VSM（文本向量模型）模型来计算文本与文本之间的相似度，在构造文本向量的时候假设词语之间是互相独立的。这种方法忽略了同一篇文档词语和词语之间的关联性，不同文档词语和词语之间的潜在联系等。传统的聚类模型受限制于文档的输入顺序，初始类的个数，最初中心点的选择等多种条件的限制。词语之间的位置聚类和同义词的挖掘也是常规文本聚类方法忽略的内容。因而文档相似度的计算受到影响，致使聚类的结果不够精确。因此，本专利提出的方法将针对数据集的特征提取关键词，去除无意义的词汇，过滤影响因子较小的词汇，挖掘文档主题，同义词组，共现高频词组等潜在语义关系来提高聚类精度，通过压缩中心词汇，利用改进的tf-idf方法来计算词汇间的相似权重，迭代聚类和分裂新类的方法来消除文档输入顺序的影响。最终达到使同类文本相似度尽量大，不同类文本相似度尽量小。

发明内容

本发明要解决的技术问题为：克服现有技术的局限性，提供一种基于类中心压缩变换的文本聚类方法，该方法挖掘文档主题，同义词组，共现高频词组等潜在语义关系，采用类中心压缩，中心重聚类，分裂新类等变换，来提高文本聚类精度。

本发明解决上述技术问题的技术方案为：一种搜索引擎中基于类中心压缩变换的文本聚类方法，该方法包括以下步骤：

步骤1、对聚类文本集中的每一个文本进行分词；

步骤2、去除停用词，过滤影响因子较小的词；

步骤3、计算每个文本中每个词出现的次数tf；

步骤4、计算词语的反文本频率

其中fileNum是文本的总数，freOccur是出现该词语的文本数量）；

步骤5、挖掘同义词组；

步骤6、挖掘共现高频词组，即同时出现在多个不同文本中的词组对；

步骤7、根据同义词组和高频共现词组，产生原始的类中心，每个类中心由一系列高频词汇组成，统计高频词汇的tf和idf，标记高频词汇所属的类中心；

步骤8、计算每个文本的内容长度，提取文章的标题，对标题进行分词；如果没有标题，则标题title设为空；提取段首词语与段尾词汇并加以标记以便后面的加权计算；

步骤9、计算任意两个文本之间的相似度，标题或内容中有相同或同义的词语时增加权重，段首词语与段尾词汇分别赋予不同的权重，计算公式如下：

pureFileSim_(i，j)＝(contentSimilarity_(i，j)+titleSimilarity_(i，j)/(log(fileLength_i*fileLength_j))；

${\mathrm{contentSimilarity}}_{(i,j)}=\underset{x,y}{\mathrm{\Σ}}\begin{array}{c}(\log \left({\mathrm{fileKeywodTf}}_{(i,x)}\right)+1)*{\mathrm{fileKeywodIdf}}_{(i,x)}*\∂\\ +(\log \left({\mathrm{fileKeywodTf}}_{(j,y)}\right)+1)*{\mathrm{fileKeywodIdf}}_{(j,y)}*\∂\end{array};$

${\mathrm{titleSimilarity}}_{(i,j)}=\underset{x,y}{\mathrm{\Σ}}\begin{array}{c}({\mathrm{fileTitleWordTf}}_{(i,x)}*{\mathrm{fileTitleWordIdf}}_{(i,x)})*\∂\\ +({\mathrm{fileTitleWordTf}}_{(j,y)}*{\mathrm{fileTitleWordIdf}}_{(j,y)})*\∂\end{array};$

式中：pureFileSim_(i,j)：文本i与文本j的纯相似度；

contentSimilarity_(i,j)：文本i与文本j的内容相似度；

titleSimilarity_(i,j)：文本i与文本j的标题相似度；

fileKeywordTf_(x，i)：文本i中关键字x的tf；

fileKeywordIdf_(x，i)：文本i中关键字x的idf；

fileTitleWordTf_(j,y)：类中心j关键词y的tf；

fileTitleWordIdf_(j,y)：类中心j关键词y的idf；

fileLengthi：文本i的内容长度；

步骤10、随机化文本的输入顺序：根据原始聚类中心对聚类文本集进行初始聚类，其算法如下：对每一篇文本，计算它与所有聚类中心的相似度，选择相似度最大的一个聚类中心id作为这个文本所属的类；文本i与类中心j的相似度计算公式如下：

${\mathrm{fileSim}}_{(i,j)}=\left(\underset{{\mathrm{fileKeyword}}_{(i,x)}\∈{\mathrm{center}}_j}{\mathrm{\Σ}}(\log \left({\mathrm{fileKeywordIf}}_{(x,i)}\right)+1\right)*{\mathrm{fileKeywordIdf}}_{(x,i)}$

$+\underset{{\mathrm{fileTitleWord}}_{(i,x)}\∈{\mathrm{center}}_j}{\mathrm{\Σ}}(\log \left({\mathrm{centerKeywordTf}}_{(j,y)}\right)+1)*\left({\mathrm{centerKeywordIdf}}_{(j,y)}\right)/{\mathrm{fileContentLength}}_i;$

式中：

fileKeywordTf_(x，i)：文本i中关键字x的tf；

fileKeywordIdf_(x，i)：文本i中关键字x的idf；

centerKeywordTf_(j，y)：类中心j关键词y的tf；

centerKeywordIdf_(j，y)：类中心j关键词y的idf；

fileContentLength_i：文本i的内容长度；

同时计算与每个词汇最接近的类中心，记录下词汇的wordid；

计算最相似的类中心比第二相似的类中心多出的百分比，记录到文本的diffRatio中；

步骤11、剔除diffRatio小于10%的文本，在剩下的文本中对属于同一个类的文本集进行关键词提取和统计，利用这些词汇重新生成该类的中心；被选的词汇要求tf和idf都不小于某个阈值；更新词汇的中心id，对类中心进行压缩，让同一个词汇只出现在与其相似高的一些类中心里，合并相似度较高的类中心；

步骤12、根据新的聚类中心重新计算每个文本所属的聚类中心，相似度计算同步骤9；

步骤13、计算每个类的核心相似度，尝试对最大的类进行分裂以产生新的类，其分裂算法如下：计算该类中最活跃的文本fx，即其它文本最相似文本中文本fx出现的次数最高，且相似值较大，在类中计算与文本fx相似度最低的文本fy，以fx及与fx最相似的文本集建立新的类中心ctx，以fy及与fy最相似的文本集建立新的类中心cty，对该类中剩下的文本计算其与ctx，cty的相似度，将它们分别并入两者之一；

步骤14、在步骤11的基础上对与类中心相似度较小的文本，根据其大多数词汇的中心id并入属于该id的类；

步骤15.重复步骤10-14，直到类的个数收敛，且同一个类中的文本与类中心相似度到达一定阈值，则终止。

本发明的原理在于：

一种搜索引擎中基于类中心压缩变换的文本聚类方法，改进了传统的tf-idf（termfrequency–inverse document frequency）公式，计算文本集中每个文档的词汇权重，通过大数据集产生初始类中心，挖掘同义词组和共现高频词组，计算词汇中心，文档间的纯相似度及关联相似度，依据初始类中心与各文档的相似度进行初次分类。根据标题词汇，文章长度，同义词，共现关联词，词汇中心，最相似的类中心比第二相似的类中心多出的百分比等信息，压缩中心词汇，使得同一个词汇只出现在与其相似高的一些类中心里，利用新的聚类中心对文档集进行重新聚类。计算每个类的核心相似度，对最大的类进行分裂以产生新的类。对压缩，聚类，分裂操作进行迭代，直到类的个数收敛，且同一个类中的文本与类中心相似度到达一定阈值。

本发明与现有技术相比的优点在于：

在文本聚类的研究领域中，KMeans（K均值方法：给定要构建的划分的数目k，划分方法首先创建一个初始划分。然后采用一种迭代的重定位技术，尝试通过对象在划分间移动来改进划分），DBSCAN（将簇看成是数据空间中被低密度区域分割开的高密度对象区域，对于一个簇中的每一文本对象，在其给定半径(用￡表示)的领域中包含的文本对象数目不小于某一给定的最小数目(用MinPts表示)，只要临近区域的密度(对象的数目)超过某个阈值，就继续聚类）是比较常用的方法。但是都存在一些缺点，如KMeans方法受初始簇中心影响较大，要预先指定聚类数k，容易受孤立点和文件输入顺序的影响。而DBSCAN方法，虽然能发现任意形状的簇，但对参数￡和MinPts敏感，容易将同一类型的文本划分成多个不同的类。传统的方法产生的聚类效果都不太理想。

本发明克服了传统方法中所显现出来的缺点，不需要预先指定聚类数目，文档的输入顺序不影响聚类结果，对相似半径等参数不敏感。

附图说明

图1是基于类中心压缩变换的文本聚类方法步骤图；

图2是基于类中心压缩变换的文本聚类方法结构图；

图3是随着初始K值上升KMeans方法和类中心压缩变换方法聚类精度的变化图；

图4是随着类中心相似度半径增长，DBSCAN方法和类中心压缩变换方法聚类数目的变化图；

图5是KMeans方法，DBSCAN方法和类中心压缩变换方法平均聚类精度的对比图。

具体实施方式

下面结合附图和实施例对本发明进一步说明。

本发明的一种基于类中心压缩变换的文本聚类方法，其充分挖掘文本词汇之间的潜在语义关联，计算词汇中心，压缩类中心，提高文本聚类的精度。计算类中心与文本的相似度，迭代分裂与合并，重组类中心，直至满足一定标准。所述的挖掘文本词汇之间的潜在语义关联，利用改进的tf-idf来计算文本之间的相似度，以此作为衡量文本词汇间关联度的一项重要指标。同时提取每篇文档的标题并进行分词，对标题词汇的相似度进行加权计算。

tf_new＝log(tf)+1

其中fileNum是文本的总数，freOccur是出现该词语的文本数量；

所述的挖掘文本词汇之间的潜在语义关联，挖掘同义词组，共现高频词组（共同出现在多篇文档中）来提高词汇相似度的计算精度，并以此作为初始词汇聚类中心。

所述的计算词汇中心，利用词汇出现在同一篇文档的次数，出现在不同文档的频率，与其近义的词，共现相关词汇等特征，对词汇进行分类标记，计算词汇最接近的词汇中心。

所述的压缩类中心，更新词汇的中心id，对类中心进行压缩，让同一个词汇只出现在与其相似高的一些类中心里。

所述的计算类中心与文本的相似度，随机化文本的输入顺序。根据聚类中心和文本预处理之后的信息计算相似度。对每一篇文本，计算它与所有聚类中心的相似度，选择相似度最大的一个聚类中心id作为这个文本所属的类。

所述的分裂类中心，计算每个类的核心相似度，尝试对最大的类进行分裂以产生新的类。分裂算法如下：计算该类中最活跃的文本fx，即其它文本最相似文本中文本fx出现的次数最高，且相似值较大。在类中计算与文本fx相似度最低的文本。以fx及与fx最相似的文本集建立新的类中心ctx，以fy及与fy最相似的文本集建立新的类中心cty。对该类中剩下的文本计算其与ctx，cty的相似度，将它们分别并入两者之一。

所述的合并类中心，计算类中心之间的相似度，将相似度达到一定标准的类合并，利用这些类的词汇重新生成该类的中心。被选的词汇要求tf和idf都不小于某个阈值。

所述的迭代操作，重复分裂类中心，重组类中心，直到类的个数收敛，且同一个类中的文本与类中心相似度到达一定阈值。

本发明的一种搜索引擎中基于类中心压缩变换的文本聚类方法主要分为以下15个步骤。

1.对聚类文本集中的每一个文本进行分词。

2.去除停用词，过滤影响因子较小的词。

3.计算每个文本中每个词出现的次数tf。

4.计算词语的反文本频率idf。

5.挖掘同义词组。

6.挖掘共现高频词组，即同时出现在多个不同文本中的词组对。

7.根据同义词组和高频共现词组，产生原始的类中心，每个类中心由一系列高频词汇组成，统计高频词汇的tf和idf，标记高频词汇所属的类中心。

8.计算每个文本的内容长度，提取文章的标题（如果没有标题，则title设为空），对标题进行分词；提取段首词语与段尾词汇并加以标记以便后面的加权计算。

9.计算任意两个文本之间的相似度（标题或内容中有相同或同义的词语才增加权重），段首词语与段尾词汇分别赋予不同的权重。计算公式：

pureFileSim_(i，j)＝(contentSimilarity_(i，j)+titleSimilarity_(i，j)/(log(fileLength_i*fileLength_j))；

${\mathrm{contentSimilarity}}_{(i,j)}=\underset{x,y}{\mathrm{\Σ}}\begin{array}{c}(\log \left({\mathrm{fileKeywodTf}}_{(i,x)}\right)+1)*{\mathrm{fileKeywodIdf}}_{(i,x)}*\∂\\ +(\log \left({\mathrm{fileKeywodTf}}_{(j,y)}\right)+1)*{\mathrm{fileKeywodIdf}}_{(j,y)}*\∂\end{array};$

${\mathrm{titleSimilarity}}_{(i,j)}=\underset{x,y}{\mathrm{\Σ}}\begin{array}{c}({\mathrm{fileTitleWordTf}}_{(i,x)}*{\mathrm{fileTitleWordIdf}}_{(i,x)})*\∂\\ +({\mathrm{fileTitleWordTf}}_{(j,y)}*{\mathrm{fileTitleWordIdf}}_{(j,y)})*\∂\end{array};$

式中：pureFileSim_(i,j)：文本i与文本j的纯相似度；

contentSimilarity_(i,j)：文本i与文本j的内容相似度；

titleSimilarity_(i,j)：文本i与文本j的标题相似度；

fileKeywordTf_(x，i)：文本i中关键字x的tf；

fileKeywordIdf_(x，i)：文本i中关键字x的idf；

fileTitleWordTf_(j,y)：类中心j关键词y的tf；

fileTitleWordIdf_(j,y)：类中心j关键词y的idf；

fileLengthi：文本i的内容长度。

10.随机化文本的输入顺序。根据原始聚类中心对聚类文本集进行初始聚类。算法如下：对每一篇文本，计算它与所有聚类中心的相似度，选择相似度最大的一个聚类中心id作为这个文本所属的类。文本i与类中心j的相似度计算公式如下：

${\mathrm{fileSim}}_{(i,j)}=\left(\underset{{\mathrm{fileKeyword}}_{(i,x)}\∈{\mathrm{center}}_j}{\mathrm{\Σ}}(\log \left({\mathrm{fileKeywordIf}}_{(x,i)}\right)+1\right)*{\mathrm{fileKeywordIdf}}_{(x,i)}$

$+\underset{{\mathrm{fileTitleWord}}_{(i,x)}\∈{\mathrm{center}}_j}{\mathrm{\Σ}}(\log \left({\mathrm{centerKeywordTf}}_{(j,y)}\right)+1)*\left({\mathrm{centerKeywordIdf}}_{(j,y)}\right)/{\mathrm{fileContentLength}}_i;$

式中：

fileKeywordTf_(x，i)：文本i中关键字x的tf

fileKeywordIdf_(x，i)：文本i中关键字x的idf

centerKeywordTf_(j，y)：类中心j关键词y的tf

centerKeywordIdf_(j，y)：类中心j关键词y的idf

fileContentLength_i：文本i的内容长度

同时计算与每个词汇最接近的类中心，记录下词汇的wordid。

计算最相似的类中心比第二相似的类中心多出的百分比，记录到文本的diffRatio中。

11.剔除diffRatio小于10%的文本，在剩下的文本中对属于同一个类的文本集进行关键词提取和统计，利用这些词汇重新生成该类的中心。被选的词汇要求tf和idf都不小于某个阈值。更新词汇的中心id，对类中心进行压缩，让同一个词汇只出现在与其相似高的一些类中心里。合并相似度较高的类中心。

12.根据新的聚类中心重新计算每个文本所属的聚类中心，相似度计算同步骤9。

13.计算每个类的核心相似度，尝试对最大的类进行分裂以产生新的类。分裂算法如下：计算该类中最活跃的文本fx，即其它文本最相似文本中文本fx出现的次数最高，且相似值较大。在类中计算与文本fx相似度最低的文本fy。以fx及与fx最相似的文本集建立新的类中心ctx，以fy及与fy最相似的文本集建立新的类中心cty。对该类中剩下的文本计算其与ctx，cty的相似度，将它们分别并入两者之一。

14.在步骤11的基础上对与类中心相似度较小的文本，根据其大多数词汇的中心id并入属于该id的类。

15.重复步骤10-14，直到类的个数收敛，且同一个类中的文本与类中心相似度到达一定阈值，终止。

Claims (1)

1.一种搜索引擎中基于类中心压缩变换的文本聚类方法，其特征在于：该方法包括以下步骤：

步骤1、对聚类文本集中的每一个文本进行分词；

步骤2、去除停用词，过滤影响因子较小的词；

步骤3、计算每个文本中每个词出现的次数tf；

步骤4、计算词语的反文本频率idf；

步骤5、挖掘同义词组；

步骤6、挖掘共现高频词组，即同时出现在多个不同文本中的词组对；

步骤7、根据同义词组和高频共现词组，产生原始的类中心，每个类中心由一系列高频词汇组成，统计高频词汇的tf和idf，标记高频词汇所属的类中心；

步骤8、计算每个文本的内容长度，提取文章的标题，对标题进行分词；如果没有标题，则标题title设为空；提取段首词语与段尾词汇并加以标记以便后面的加权计算；

步骤9、计算任意两个文本之间的相似度，标题或内容中有相同或同义的词语时增加权重，段首词语与段尾词汇分别赋予不同的权重，计算公式如下：pureFileSim_(i，j)＝(contentSimilarity_(i，j)+titleSimilarity_(i，j))/(log(fileLength_i*fileLength_j))；

${\mathrm{contentSimilarity}}_{(i,j)}=\underset{x,y}{\mathrm{\Σ}}\begin{array}{c}(\log \left({\mathrm{fileKeywodTf}}_{(i,x)}\right)+1)*{\mathrm{fileKeywodIdf}}_{(i,x)}*\∂\\ +(\log \left({\mathrm{fileKeywodTf}}_{(j,y)}\right)+1)*{\mathrm{fileKeywodIdf}}_{(j,y)}*\∂\end{array};$

${\mathrm{titleSimilarity}}_{(i,j)}=\underset{x,y}{\mathrm{\Σ}}\begin{array}{c}({\mathrm{fileTitleWordTf}}_{(i,x)}*{\mathrm{fileTitleWordIdf}}_{(i,x)})*\∂\\ +({\mathrm{fileTitleWordTf}}_{(j,y)}*{\mathrm{fileTitleWordIdf}}_{(j,y)})*\∂\end{array};$

式中：pureFileSim_(i,j)：文本i与文本j的纯相似度；

contentSimilarity_(i,j)：文本i与文本j的内容相似度；

titleSimilarity_(i,j)：文本i与文本j的标题相似度；

fileKeywordTf_(x，i)：文本i中关键字x的tf；

fileKeywordIdf_(x，i)：文本i中关键字x的idf；

fileTitleWordTf_(j,y)：类中心j关键词y的tf；

fileTitleWordIdf_(j,y)：类中心j关键词y的idf；

fileLength_i：文本i的内容长度；

步骤10、随机化文本的输入顺序：根据原始聚类中心对聚类文本集进行初始聚类，其算法如下：对每一篇文本，计算它与所有聚类中心的相似度，选择相似度最大的一个聚类中心id作为这个文本所属的类；文本i与类中心j的相似度计算公式如下：

${\mathrm{fileSim}}_{(i,j)}=\left(\underset{{\mathrm{fileKeyword}}_{(i,x)}\∈{\mathrm{center}}_j}{\mathrm{\Σ}}(\log \left({\mathrm{fileKeywordIf}}_{(x,i)}\right)+1\right)*{\mathrm{fileKeywordIdf}}_{(x,i)}$

$+\underset{{\mathrm{fileTitleWord}}_{(i,x)}\∈{\mathrm{center}}_j}{\mathrm{\Σ}}(\log \left({\mathrm{centerKeywordTf}}_{(j,y)}\right)+1)*\left({\mathrm{centerKeywordIdf}}_{(j,y)}\right)/{\mathrm{fileContentLength}}_i;$

式中：

fileKeywordTf_(x，i)：文本i中关键字x的tf；

fileKeywordIdf_(x，i)：文本i中关键字x的idf；

centerKeywordTf_(j，y)：类中心j关键词y的tf；

centerKeywordIdf_(j，y)：类中心j关键词y的idf；

fileContentLength_i：文本i的内容长度；

同时计算与每个词汇最接近的类中心，记录下词汇的wordid；

计算最相似的类中心比第二相似的类中心多出的百分比，记录到文本的diffRatio中；

步骤11、剔除diffRatio小于10%的文本，在剩下的文本中对属于同一个类的文本集进行关键词提取和统计，利用这些词汇重新生成该类的中心；被选的词汇要求tf和idf都不小于某个阈值；更新词汇的中心id，对类中心进行压缩，让同一个词汇只出现在与其相似高的一些类中心里，合并相似度较高的类中心；

步骤12、根据新的聚类中心重新计算每个文本所属的聚类中心，相似度计算同步骤9；

步骤13、计算每个类的核心相似度，尝试对最大的类进行分裂以产生新的类，其分裂算法如下：计算该类中最活跃的文本fx，即其它文本最相似文本中文本fx出现的次数最高，且相似值较大，在类中计算与文本fx相似度最低的文本fy，以fx及与fx最相似的文本集建立新的类中心ctx，以fy及与fy最相似的文本集建立新的类中心cty，对该类中剩下的文本计算其与ctx，cty的相似度，将它们分别并入两者之一；

步骤14、在步骤11的基础上对与类中心相似度较小的文本，根据其大多数词汇的中心id并入属于该id的类；

步骤15.重复步骤10-14，直到类的个数收敛，且同一个类中的文本与类中心相似度到达一定阈值，则终止。

Images