基于模糊相似度的RPCL文本聚类算法

开篇：润墨网以专业的文秘视角，为您筛选了一篇基于模糊相似度的RPCL文本聚类算法范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

摘要：文本聚类过程中，存在着文本数据空间维数巨大，聚类的数目不能直接确定等问题。为此，有专家学者提出了次胜者受罚的竞争学习（Rival Penalized Competitive Learning）算法，简称RPCL算法。该算法在一定程度上，解决了聚类的数目的确定问题。但是，该算法只适合做低维数据的聚类，对于高维数据聚类效果极差。该文提出了一种改进的RPCL算法，该方法不再采用欧氏距离去计算相似度，而是采用模糊相似度的方法，通过实验表明，改进的RPCL算法在聚类效果上好于经典的RPCL算法。

关键词：模糊相似度；RPCL；文本聚类

中图分类号：TP18文献标识码：A文章编号：1009-3044(2011)18-4416-02

RPCL Text Clustering Based on Fuzzy Similarity Degree

HAO Jian,GAO Mao-ting

(College of Information Engineering, Shanghai Maritime University, Shanghai 200135, China)

Abstract: There exist some problems in text clustering, such as huge dimensionality in text feature matrix, unknown cluster number. Some expert put forward the algorithm of Rival Penalized Competitive Learning, RPCL for short. The algorithm solved the problem of determining the clustering number in some degree. However, it is suited to cluster of text in lower dimension, not to higher dimension. This paper introduces a improved RPCL algorithm. Fuzzy similarity instead of Euclid distance is used to compute similarity. The experiments demonstrate that the improved RPCL algorithm is better than classic RPCL algorithm in clustering performance.

Key words: fuzzy similarity; RPCL; text clustering

随着网络技术的不断发展，互联网上的各类信息资源越来越丰富，如何从这些海量数据中，找出有价值的信息，一直是一个热点的研究问题。文本聚类能有效地帮助人们去获取那些有价值的信息。最早的聚类方法，k-means[1]就是其中一种经典的聚类方法。但其存在不足之处，它必须事先给定聚类的数目，而在实际聚类过程当中，聚类的数目是无法预先给定的。为了解决这一问题，Xu和Krzyzak提出了一种称为次胜者受罚的竞争学习RPCL（Rival Penalized Competitive Learning）[2]算法。该算法自动决定类的适当数目。该算法计算相似度采用的欧几里得距离。欧氏距离应用在低维空间去计算相似度，它能很好的去描述数据之间的相似性。然而，欧氏距离应用到单位超球面后，即应用到高维甚至超高维数据空间上，距离差别减小，准确率极差，不适合高维文本相似度的表达[3]。

本文提出了一种基于模糊相似度的rpcl 算法。本文的改进，是建立在这基础之上的，传统的RPCL采用的是欧氏距离计算相似度，这里用模糊相似度的方法，来计算相似度。模糊相似度是模糊数学中，来衡量两个模糊向量之间的相似关系的。它不再使用距离描述两者之间的相似性，这完全适合做高维数据的相似性关系判断。本文分别采用RPCL算法和改进的RPCL 算法进行文本聚类，并通过实验对聚类效果做了对比。

1 RPCL 聚类算法

RPCL是一种竞争神经网络，在竞争学习过程中，对每个输入而言，不仅将竞争获胜单元的权值按一定的学习率给以修正以适应输入值，使获胜神经元k的突触权值向量wk向输入模式移动，同时对它的对手(次胜单元)采用惩罚的策略，使之远离输入值，而对于其它的神经元则不作任何修正。通过重复多次的学习之后，各个权值向量wk趋向于聚类的各个聚簇中心，最后通过统计分布在权值向量周围的数据点的数目就可确定这个权值向量是否能构成聚类的一簇，所以，RPCL算法表现出能够自动确定数据集聚类数的特性[4]。

设t为竞争学习的迭代次数，tmax是允许的最大迭代次数，k为设定的聚类数，x为待聚类集合中的任一元素，每一单元的输出值为ui，它的权值矢量为wi，i=1、2、…、k，则RPCL算法可以描述如下:

步骤1随机初始化k个不同的权值矢量{Wi}ki=1 ，并设t=1。

步骤2从数据集中随机选取样本x，对i=1、…、k，使：

这里，c表示获胜单元，r表示次胜单元。ni是ui=1的次数。

步骤3修改权值矢量wi：

这里,0≤ac(t)，ac(t)≤1分别是竞争获胜单元和次胜单元的学习率。一般地，在迭代的过程中，保持ar(t)

步骤4 t值加1,若t

2 模糊相似度

模糊相似度是在模式识别领域中提出的一种相似性关系度量。模式识别是对所研究的对象进行认识分类，将整体划分为若干类型，作为一组标准模式，对某个具体对象判断识别它属于哪一类。如果是某个论域上的模糊子集，这种模式识别就被称为模糊模式识别。如果要考察一个模糊集与另一个模糊集之间的贴近程度，这里就是通过贴近度按择近原则来识别的。因此，提出了模糊集之间模糊相似度[5] 的衡量方法。

设论域U上有n个模糊子集：A1，A2，…，An。而被识别的对象是模糊的，也是论域U上的模糊子集B，这时就要考虑B与每一个Ai(i=1、2、…、n)贴近度(B，Ai)。B和哪一个Ai最贴近就认为它属于哪一个，这就要用到择近原则[6]。若Ai和B满足(B，Ai) =max{(B，A1)，(B，A2)，…， (B，An)},则认为B与Ai最贴近。

贴近度有各种不同的计算方法,常用的计算方法如下：

1）内外积贴近度

(B，A) =1/2*[B∩A+1-B∪A]，

式中,内积B∩A =∨u∈U[μA(u)∧μB(u)]，外积B∪A =∧u∈U[μA(u)∨μB(u)](∧表示取min，∨表示取max。

2）最大最小值贴近度

设ui(i =1、2、…、n)是U中的n个待选对象，则A，B的最大最小贴近度定义为:

3 基于模糊相似度的RPCL文本聚类

本算法的主要步骤如下：

步骤1对选取的文本进行分词处理，将所有文本用相应的特征词表示，本文采用的是向量空间模型来表示文本的。

步骤2计算每个特征词的词频，并用词频去表示特征词。

步骤3将词频向量转化为TF-IDF值，并进行归一化处理。

步骤4用改进的RPCL算法进行聚类。

步骤5统计分析去除多余的类别，并确定合理的聚类数。

步骤6确定待聚类文本集合的聚类结果。对待聚类文本集合中的每个文本，计算其到各个已确定的聚类中心的距离，将其归到距离最近的一类中，得到最终的文本聚类结果。

4 实验结果和分析

本实验的实验数据为海量公司的文本集，共5类486篇文本。本文采取平均准确率[7]来衡量聚类效果，即通过考察两两文本之间的隶属关系是否一致来评价。

文本之间的混淆矩阵[8]如表1。

积极准确率：PA=TP/（TP+FN） 消极准确率：NA=TN/（TN+FP）

平均准确率：AA=（PA+NA）/2

本实验共做五次，每一次的准确率计算如表2。

通过分析和比较实验结果，可以得出：

1）改进后的RPCL算法在准确率上，明显高于经典的RPCL算法。

2）经典的RPCL算法，采用欧式距离计算相似度，应用于高维数据是，距离之间的差别减小，准确率也会变差，而模糊相似度克服了此困难。

3）对于文本聚类，以后计算相似度，可以采用本文提出的算法，聚类效果会有所提高。

5 结束语

对于传统的k-means方法，简单实用，但是，必须事先确定聚类的个数，而实际的聚类情况在聚类之前无法获知，这就是k-means聚类算法的局限性。针对此问题，学者提出了RPCL算法，该算法在一定程度上确定的聚类的个数。然而，文本的空间维度的选择和相似度衡量方法的选择，影响了聚类效果。当对低维度文本进行聚类是，经典的RPCL算法，可以达到很好的效果。当维度是高维时，聚类的准确率明显下降。因此，本文提出了基于模糊相似度的聚类算法。该算法非常适合高维数据的聚类，同时，对于低维数据文本聚类效果也非常好。

参考文献：

[1] Xu L,Krzyzak A,Oja E.Rival penalized competitive learning for clustering analysis,RBF net,and curve detection[J].IEEE Transactions on Neural Networks,1993,4(4):636-649.

[2] Xu L,Krzyzak A,Oja E.Unsupervised and supervised classification by rival penalized competitive learning[C]//Proc 11th International Conference on Pattern Recognition,The Hague,The Netherlands,1992:492-496.

[3] 姜宁,宫秀军,史忠植.高维空间中文本聚类研究[J].计算机工程与应用,2002(10):63-67.

[4] 刘增良，刘有才.模糊逻辑与神经网络[M].北京:北京航空航天大学出版社,1996.

[5] Steinbach M,Karypis G,Kumar V.A Comparison of Document Clustering Techniques[C].Boston,MA,USA,:KDD-2000 Workshop on Text Mining,2000.

[6] Han Jiawei,Kamber M.Data mining:concepts and techniques[M].Morgan Kaufmann,USA,2001.

[7] 孙才志,王敬东,潘俊.模糊聚类分析最佳聚类数的确定方法研究[J].模糊系统与数学,2001,27(9):53-56.

[8] 李听,郑宇,江芳泽.用改进的RPCL算法提取聚类的最佳数目[J].上海大学学报,1999,40(8):120-122.

注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文