章成志  师庆辉  薛德军

 

 摘 要：  样本加权聚类算法是一种最近才引起人们注意的算法，还存在一些需要解决的问题，例如聚类对象之间的结构信息对样本加权聚类是否有帮助，如何将结构信息自动化转换为样本或对象的权重？针对该问题，本文以学术论文为聚类对象，以K-Means算法为聚类算法基础，利用论文之间的引用关系计算每篇论文的PageRank值，并将其作为权重，提出一种基于样本加权的新的文本聚类算法。实验结果表明，基于论文PageRank值加权的聚类算法能改善文本聚类效果。该算法可推广到网页的聚类中，利用网页的PageRank进行加权聚类，来改善网页的聚类效果。

关键词：文本聚类；样本加权聚类；PageRank；被引频次

分类号：TP391

Document Clustering Algorithm Based on Sample Weighting

Zhang Chengzhi, Shi Qinghui, Xue Dejun

Abstract:                Sample weighting clustering algorithm have been noticed recently. There are some unsolved problems, for example, whether the structure information among the clustering objects is helpful to sample weighting clustering? How to transform structure information into the weight of samples or not? To solve these problems, a novel sample weighting clustering algorithm is presented based on K-Means algorithm. The algorithm uses academic documents as the clustering objects. The PageRank value of each document is calculated according to the cited relationship among them, and it is used as the weight in the algorithm. Experiments show that the proposed algorithm is an effective solution to improve the performance of document clustering, and it can be extended to Web pages clustering based on PageRank value of each Web page.

Key words:      Document clustering, Sample weighted clustering, PageRank, Citied frequency

1          引 言

聚类分析是数据分析中的一种重要技术，在生物学、社会学、人工智能和信息检索等多个领域受到广泛关注和研究。其中，文本聚类是聚类分析在信息检索领域的一种重要应用。在信息检索领域，文本聚类的主要应用包括：基于文本聚类方法的自动摘要^[1]、文本集合的自动组织^[2]、搜索结果聚类^[3]等。作为一种典型的非监督学习问题，文本聚类方法大致可以分为划分方法、层次的方法、基于密度的方法、基于网格的方法以及基于模型的方法等几种类型^[4]。

在传统的基于划分的聚类方法中，一般都是对聚类样本或对象同等对待，例如K-Means算法^[5]，模糊C-Means算法^[6]以及EM算法^[7]等。但实际上，不同的样本或对象对聚类结果有不同的贡献，样本或对象加权聚类的思想由此而产生^{[8][9][10][11][12][13]}。以往的聚类研究中，只有仅仅几个算法考虑样本权重，如CFCM算法^[8]、基于确定性退火的聚类^[9]等。但不幸的是，上面提到的算法，需要靠用户或者启发式规则来对样本进行加权，这样就限制了这些算法的应用。因此，寻找自动计算每个样本的权重的方法是一个引人关注的的工作^[10]。最近，Richard Nock、Frank Nielsen利用Boosting 算法的思想, 提出了一个一般的自适应样本权重聚类算法框架^[11]，指出在聚类过程中自动化计算样本或对象的权重的重要意义^[12]。Li Jie、Gao Xinbo等人提出了一个用于大数据集的典型样本加权聚类算法，利用原子聚类算法获取待加权的聚类样本，根据样本的原子数进行加权^[13]。

作为一种最近才引起人们注意的算法，样本加权聚类算法还存在一些需要解决的问题，例如，样本或对象之间的结构信息对样本加权聚类是否有帮助，如何将结构信息自动化转换为样本或对象的权重？针对这一问题，本文以学术论文为聚类对象，以K-Means算法作为聚类算法基础，利用学术论文之间的引用关系计算每篇论文的PageRank值，并以此作为权重，进行了文本的样本加权聚类实验。实验结果表明，基于论文PageRank值加权的聚类算法能改善文本聚类效果。该算法可以推广到网页的加权聚类，利用网页的PageRank进行加权聚类，来改善网页的聚类效果。

2          基于样本加权的文本聚类算法

2.1 基本思想

基于样本加权的文本聚类算法认为：在基于划分的聚类方法中，不同的聚类样本或聚类对象对聚类效果的影响不一样，在聚类过程中，对不同的样本或对象（注：本文对聚类对象和聚类的样本这两个概念不作严格区分）赋予不同的权重，能提高聚类的效果^[12]。样本偏离聚类中心越大，则该样本的权重就越小。本文以经济类的论文为聚类对象，以K-Means算法作为聚类算法基础，分别利用论文的引用频次、简化的论文PageRank值作为权重，进行了基于样本加权的文本聚类实验。

2.2 算法描述

本文以K-Means聚类算法为基础，进行基于样本加权的文本聚类算法研究。在不考虑样本权重的情况下，K-Means聚类算法在准则函数收敛时结束聚类，其中准则函数如公式（1）所示。

                        （1）

    其中：J又可以称为凝聚度，可用来度量聚类效果。K为类簇的总数目；m_i是类簇i中的成员总数；为类簇i中的第j个成员； 为类簇i的中心向量，通过式（2）计算得到。

                            （2）

为文本 与类簇中心点的相似度，文本和类簇的中心向量都是利用向量空间模型表示，经特征提取，计算特征权重^[14]等步骤后分别得到它们的向量表示，本文利用向量夹角的余弦计算得到^[14]。若文本为中文，则事先进行文本的中文分词处理，本文采用基于词典的逆向最大匹配法进行分词。

在样本加权聚类算法中，聚类样本加权后，聚类准则函数通过式（3）求得。

                 （3）

其中： 为聚类样本加权后的类中心向量，通过式（4）求得。

                           （4）

其中：为聚类样本i的权重，。可以看出，如果，即对聚类样本的权重作均衡赋值，则式（4）转换为式（2），式（3）则转换为式（1），使得样本加权聚类算法退化到常规的K-Means算法。

基于样本加权的文本聚类算法具体的描述如图1所示。

 

2.3 样本加权方法

本文根据样本的重要性进行加权，一般说来，论文之间的引用关系大致可表明论文的权威程度。论文之间的引用关系可以看作文本集合中的一种结构信息，本文利用引用关系，进行了简化的论文PageRank值计算。分别利用文本的引用频次、简化的文本PageRank值作为权重，进行了文本的样本加权聚类的对比实验。其中，文本的引用频次、简化的文本PageRank值分别说明如下。

定义1：文本的被引用频次，待聚类的文本集合D中文本被D中其他文本引用的总频次（本文以每篇学术论文的参考文献作为统计对象），记为Cited_Freq()。

论文的参考文献中提到的论文一般是在之前发表过的论文，若论文A被论文B引用，则不可能同时出现论文B被论文A引用的情况，论文之间的链接关系总是单向的，如图2所示。这一点和网页的链接关系完全不同，因为两个网页可能存在互相链接的情况。根据论文的这一特征，本文提出了简化的带有时间属性的、简化的文本PageRank值计算方法。

定义2：简化的文本PageRank，反映文本的重要程度，记为PageRank()，并设其初始值为1，即PageRank()=1。

将文本的链接图看成单向图，根据网页的PageRank值计算方法^[15]，进行文本的PageRank值计算。计算公式为式（5）。

        （5）

其中：PageRank ()为文本的级别；PageRank ()为文本的级别，文本链向文本 ；C()为文本链出的链接数量，即的参考文献中的文献总篇数；r为阻尼系数，为系统设定的经验值，通常取0.15，rÎ[0,1]；阻尼系数的使用，减少其它文本对文本的排序贡献。N为文本总数。

论文级别由引用它的论文的级别决定，但每个引用论文的贡献的值是不同的。如果p_i中参考文献（即链出）越多，它对当前论文的贡献就越小。论文被引用（即链入）越多，其级别也越高；与计算网页的PageRank不同的是，因为论文的链接图是单向图，经过一次迭代计算就会收敛。没有被引用的论文的简化PageRank为0.15。

论文经过Cited_Freq值与PageRank值计算后，其权重分别表示为， ，分别通过式（6）和式（7）求得。 

   （6）

       （7）

3          实验与聚类结果测评

3.1 测评数据与实验步骤

本文以经济类的学术论文为聚类对象。数据规模分别为10000篇，并且每篇论文带有分类标签。经过文本的被引用频次、简化的文本PageRank值计算，分别得到每篇论文的Cited_Freq值与PageRank值。其中，Cited_Freq值与PageRank值的最大值分别为：311、18.49928。论文的Cited_Freq值与PageRank值的分布如图3所示。在进行文本聚类实验时，事先对论文进行了中文分词、停用词过滤、特征提取以及特征权重的计算，用向量空间模型^[14]表示文本。

  

 

本文利用图1所示算法，以10000篇经济学类别的学术论文为聚类对象，进行加权聚类实验。为了评估样本加权聚类算法，分别对样本不加权（作为基准测试，记为Baseline）、利用为 加权(记为Cited_Freq)、利用加权（记为PageRank）进行了比较实验。设定三种不同的聚类中心数目K分别为为10、15，20，分别进行三组实验。在每一组实验中，根据所选择的初始聚类中心的不同，分别进行5次，再取其平均值。

3.2 聚类评估方法

对聚类结果进行评估的方式大致可以分为监督评估与非监督评估两种方法。

(1) 监督评估

基于监督学习的评估方法主要是度量预测的类簇标签与实际的标签（即人工标记的标

签，这里称其为分类标签）的对应程度。由于这种评估方法是存在分类测试集的情况下对聚类效果进行评价，通常又称为外部评价标准。

①  熵^[16]

度量每个类簇由单个类的成员组成的程度。首先通过以下公式计算得到每个类簇的熵：

    

                        （8）

其中：E_i为类簇i的熵；L为分类标签的总数；p_ij为类簇i的成员属于类j的概率，可通过式（9）求得p_ij：

p_ij =  m_ij/m_i                                                （9）

其中：m_i是类簇i中的成员个数；m_ij是类簇i中类j的成员的个数。类簇集合的总熵通过每个类簇的加权和计算，由式(10)得到。总熵值越低，聚类性能就越好。

                             （10）

其中：E为类簇集合的总熵；K为类簇的总数目；m为聚类对象的总数目。

②  纯度（Purity）^[16]

度量类簇在多大程度上包含单个类的成员的另一种度量。类簇i的纯度通过式（11）求得，聚类的总纯度通过式（12）计算得到。总纯度越高，聚类性能就越好。

Purity_i=Max (p_ij）                           （11）

                                       （12）

（2） 非监督评估

在只利用数据集本身的特征的条件下，比较聚类的效果，又称为内部标准评价。一般

通过分离度与凝聚度进行评估。已经证明最大凝聚度(SSE)等价于最小化分离度(SSB)^[16]。

因此本文只利用凝聚度来进行文本聚类效果的非监督评估。凝聚度通过式（3）计算得到，本文利用 进行凝聚度评估，因此SSE越小，聚类性能就越好。

3.3 测评结果与分析

根据3.1中的实验以及3.2中的评估方法，得到分组实验的结果分别如表1（K=10时）、表2（K=15）、表3（K=20）所示。根据每组结果，按照K=10、15、20等三种条件，得到样本加权聚类结果的总熵值、纯度 、凝聚度比较图分别如(a)、(b)、 (c)所示。

由图4(a)可以看出，K分别取10、15，20时，聚类结果的总熵值(E)是：BaseLine>Cited_Freq>PageRank。由于总熵值越低，聚类性能越好，因此，从总熵值角度考虑，聚类性能最好的是基于PageRank加权，其次为基于Cited_Freq加权，最差的为不加权。

由图4(b)可以看出，K分别取10、15，20时，聚类结果的纯度(Purity)是：PageRank>Cited_Freq>BaseLine，其中，基于Cited_Freq加权和不加权的聚类效果比较接近。从聚类结果纯度角度考虑，聚类性能最好的是基于PageRank加权的样本加权聚类算法。

由图4(c)可以看出，K分别取10、15，20时，聚类结果的凝聚度（SSE）是： BaseLine>Cited_Freq>PageRank。由于SSE越低，聚类性能就越好，因此，从凝聚度角度考虑，聚类性能最好的是基于PageRank加权，其次为基于Cited_Freq加权，最差的为不加权。综上，从监督评估与非监督评估两个方面的结果都可以得出，基于样本加权的文本聚类算法对提高文本聚类的性能有帮助。这也从一个侧面回答了本文一开始所提出的问题，即：样本或对象之间的结构信息对样本加权聚类是有帮助的，利用文本间引用关系，自动计算得到简化的论文PageRank值，并用于样本加权聚类算法，能改善文本聚类效果。

 4          结语

本文以学术论文为聚类对象，以K-Means算法为聚类算法基础，利用论文之间的引用关系计算每篇论文的PageRank值，并将其作为权重，进行了文本的样本加权聚类实验。实验结果表明，基于简化的论文PageRank值加权的聚类算法能改善文本聚类效果。

未来工作主要包括：将K-Means算法扩展到模糊C-Means算法、EM算法等划分型聚类算法，测试本文所提出算法的效果；在没有足够先验知识的情况下，利用最大熵模型进行文本权重计算，进一步改善文本聚类效果；利用网页的PageRank进行样本加权聚类研究等。

参考文献

1           Hatzivassiloglou V, Klavans J L, Holcombe M L, et al. Simfinder: A flexible clustering tool for summarization. In: Proceedings of the NAACL 2001 Workshop on Automatic Summarization, 2001, 41~49.

2           Cutting, D. R., Karger, D. R, Pedersen, J. O. and Tukey, J. W. Scatter/Gather: A cluster-based approach to browsing large document collections. In: Proceedings of the 15th International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR'92), 1992, 318~329.

3           Hearst, M. and Pedersen, P. Reexamining the cluster hypothesis: Scatter/gather on retrieval results. In: Proceedings of the 19th International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR'96), 1996, 76~84.

4           J. Han and M. Kamber. Data Mining: Concepts and Techniques, Morgan Kaufmann, 2000.

5           MacQueen J. Some Methods for Classification and Analysis of Multivariate Observations, In: Proceedings of the 5th Berkeley Symposium on Mathematical Statistics and Probability, 1967, 281~297.

6           Bezdek, J.C. Pattern Recognition with Fuzzy Objective Function Algorithms. Plenum Press, New York, 1981.

7           A.P. Dempster, N.M. Laird, and D.B. Rubin. Maximum Likelihood from Incomplete Data via the EM Algorithm. J. Royal Statistical Soc. B, Vol. 39, 1977, 1~38.

8           W. Pedrycz. Conditional fuzzy c-means. Pattern Recognition Letters, Vol. 17, 1996, 625~632.

9           K. Rose. Deterministic annealing for clustering, compression, classification, regression, and related optimization problems. In: Proceedings of the IEEE, 86(11), 1998, 2210~2239.

10        Jian Yu. Sample Weighting Clustering. Technical report of Institute of Computer Science, Beijing Jiaotong University, 2006.

11        Richard Nock and Frank Nielsen. An abstract Weighting Framework for Clustering Algorithms. In: Proceedings of the Fourth International SIAM Conference on Data Mining, 2004, 200~209.

12        Richard Nock and Frank Nielsen, On weighting exponent, IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 28, NO. 8, 2006, 1223~1235.

13        Jie Li, Xinbo Gao, and Licheng Jiao. A Novel Typical-Sample-Weighted Clustering Algorithm for Large Data Sets, LNAI 3801, 2005, 696~703.

14        G. Salon and M. J. Mcgill. Introduction to Modern Information Retrieval. McGraw-Hill Book Co., NewYork, 1983.

15        Brin S, Page L. The anatomy of a large-scale hypertextual Web search engine. In: Proceedings of the 7th ACM-WWW International Conference, 1998, 107~117.

16        Pang-Ning Tan, Michael Steinbach, and Vipin Kumar, Introduction to Data Mining, Pearson Education, Inc, 2005.

 

 

注：本文发表于《情报学报》2008年第1期。　

 

 

 

   本文全文：基于样本加权的文本聚类算法研究

 

　相关论文：Document Clustering Using sample Weighting（expanded version）

 

 　　　　　　　　　

　　　　　　　　　　　　

　　　　　　　　　　　　　

 

 

转载本文请联系原作者获取授权，同时请注明本文来自章成志科学网博客。
链接地址：https://blog.sciencenet.cn/blog-36782-16154.html

上一篇：信息检索系统的相关词提示技术与评测
下一篇：基于多层特征的字符串相似度计算模型