|
关键词:文本聚类;样本加权聚类;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]、文本集合的自动组织[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进行加权聚类,来改善网页的聚类效果。
基于样本加权的文本聚类算法认为:在基于划分的聚类方法中,不同的聚类样本或聚类对象对聚类效果的影响不一样,在聚类过程中,对不同的样本或对象(注:本文对聚类对象和聚类的样本这两个概念不作严格区分)赋予不同的权重,能提高聚类的效果[12]。样本偏离聚类中心越大,则该样本的权重就越小。本文以经济类的论文为聚类对象,以K-Means算法作为聚类算法基础,分别利用论文的引用频次、简化的论文PageRank值作为权重,进行了基于样本加权的文本聚类实验。
本文以K-Means聚类算法为基础,进行基于样本加权的文本聚类算法研究。在不考虑样本权重的情况下,K-Means聚类算法在准则函数收敛时结束聚类,其中准则函数如公式(1)所示。
(1)
其中:J又可以称为凝聚度,可用来度量聚类效果。K为类簇的总数目;mi是类簇i中的成员总数;