一种基于群体智能的文本聚类算法

一种基于群体智能的Web文档聚类算法吴斌傅伟鹏郑毅刘少辉史忠植（中科院计算技术研究所智能信息处理开放实验室北京100080）摘要本文提出了一种基于群体智能的Web文档聚类算法。首先运用向量空间模型表示Web文档信息，采用常规方法如消除无用词和特征词条约简法则得到文本特征集，然后将文档向量随机分布到一个平面上，运用基于群体智能的聚类方法进行文档聚类，最后从平面上采用递归算法收集聚类结果。本文将算法的实验结果与多层自组织特征映射算法的聚类结果进行比较分析，分析表明基于群体智能的Web文档聚类算法具有较好的聚类特性，它能将与一个主题相关的Web文档较完全和准确地聚成一类。关键词群体智能，文档聚类，自组织聚类，群体相似度ACLUSTERINGALGORITHMBASEDONSWARMINTELLIGENCEFORWEBDOCUMENTWubinFuweipengZhengyiLiuShaohuiShizhongzhiThelab.ofIntelligenceInformationProcessing,InstituteofComputingTechnology,CASAbstractAclusteringalgorithmbasedonswarmintelligenceforwebdocumentisproposed.Firstly,Webdocumentswhicharedenotedbyvectorspacemodelwithreduceddocumentfeaturesetarerandomlyprojectedonaplane.Then,clusteringanalysisisprocessedbyaclusteringmethodbasedonswarmintelligence.Finally,theclusteringresultsarecollectedfromtheplanebyarecursivealgorithm.TheexperimentresultsandthecomparisonwithMulti-layeredSOMmethodshowthatthiswebdocumentclusteringalgorithmbasedonswarmintelligencehasgoodclusteringperformance.Thewebdocumentsfocusonasubjectarerathercompletelyandexactlyclusteringtogether.Keywordsswarmintelligence,documentclustering,Self-organizingclustering,swarmsimilarity1引言Web已快速发展成为一个海量的、广泛分布的全球化信息空间。Web信息检索也就成为一个日益重要的研究领域。Web文档聚类是Web信息检索领域的一个重要问题。文档聚类是一种无指导的文档分类。它的目标是把一个文档集分成若干称为集簇(cluster)的子集，每个集簇中的成员之间具有较大的相似性，而集簇之间的文档具有较小的相似性。Web文档聚类则是将Web文档依据其内容进行聚类。它不仅可用于有效地组织Web文档，而且还可形成分类模板用于Web文档分类。目前使用的文档聚类算法有以G-HAC等算法为代表的层次凝聚法（agglomerativehierarchicalclustering,AHC），如Stanford大学数字图书馆系统中的Soina系统中采用的文档聚类方法；还有以K-Means算法为代表的平面划分法，以及以WEBSOM为代表的自组织特征映射（Self-OrganizingMaps,SOM）方法[1,2,3,4,12]。前两种算法是经典聚类算法在文档聚类方面的应用，同时也具有它们本身聚类算法的缺陷，有些缺点在文档聚类方面还更为突出。如AHC算法可能产生由几个互不相干的集簇合成为一个集簇，这非常不利于文档聚类；K-Means算法除了需要预先设定集簇个数K值外，它对噪声和例外（outliers）以及输入顺序都是敏感的，在对一个文档集进行聚类时，一般较难预先确定一个适当的集簇个数，而且对例外敏感也会影响文档聚类的质量。自组织聚类算法在克服上述缺陷方面有一定的优势，但是SOM算法在文档聚类时常常需要多层聚类，即在上一次聚类结果的基础上，将较大的类再进行SOM聚类，得到多层聚类结果，如HsinchunChen提出的多层SOM文档聚类算法[3]。本文提出了一种基于群体智能的Web文档聚类算法。它不仅是一种自组织Web文档聚类算法，而且在选用适当群体相似系数以后，一次聚类就能得到优于多层SOM文档聚类的结果，而群体相似系数的选取也相对容易。算法的主要过程是首先运用向量空间模型表示Web文档信息，采用常规方法如消除无用词和特征词条约简法则得到文本特征集，然后将文档向量随机分布到一个平面上，运用基于群体智能的聚类方法进行文档聚类，最后从平面上采用递归算法收集聚类结果。基于群体智能的聚类方法是以蚁群合作蚁巢分类的基本模型为基础提出的一种自组织聚类方法。基于群体智能的聚类算法的主导思想是将待聚类的对象看作蚁巢中的一个分类对象，每一个对象开始在平面上有一个随机初始位置，每一只蚂蚁依据当前对象与局部环境中其它对象的相似情况确定是否移动此对象，蚁群众多次的搬移将实现自组织聚类过程，即在平面上形成若干由同一类别的对象聚成的集簇。本文将算法的实验结果与多层SOM文档聚类的结果进行比较分析，分析表明基于群体智能的Web文档聚类算法具有较好的聚类特性，它能将与一个主题相关的Web文档较完全和准确地聚成一类。本文的其余部分组织如下：在第2节介绍群体智能及相关的聚类算法，第3节着重描述基于群体智能的Web文档聚类算法，包括它的基本过程和参数处理方法等关键内容，第4节给出算法的部分实验结果和与多层SOM文档聚类结果的对比分析，最后是结论和展望。2群体智能及相关的聚类算法群居性生物的群体行为涌现的群体智能正越来越得到人们的重视。启发于群居性生物的寻食、打扫巢穴等行为而设计的解决实际问题的算法获得了令人惊奇的成功。这些算法在组合优化、通信网络和机器人领域的应用实例的数量正成指数地增长[5,6,7,8,9]。Bonabeau等人认为群体智能是任何启发于群居性昆虫群体和其它动物群体的集体行为而设计的算法和分布式问题解决装置[10]。群体智能的特点是最小智能但自治的个体利用个体与个体和个体与环境的交互作用实现完全分布式控制，并具有自组织、可扩展性、健壮性等特性。基于群体智能的聚类算法起源于对蚁群蚁卵的分类研究。E.Lumer和B.Faieta将Deneubourg提出的蚁巢分类模型应用于数据聚类分析[7]，吴斌等人在简化分类模型的基础上系统地提出了一种基于群体智能的聚类算法（ClusteringalgorithmbasedonSwarmIntelligence,CSI），并将算法成功应用于标准机器学习数据库的聚类分析和客户关系管理（CRM）中的客户行为分析[14,15]。与经典的分层聚类算法和K均值动态聚类算法相比，基于群体智能的聚类算法具有群体智能算法的共同特点，它利用个体与个体和个体与环境的交互作用，不必预设聚类中心的数目，实现自组织聚类过程，具有健壮性、可视化等特点。基于群体智能的聚类算法的主要思路是将待聚类的对象随机放置一个两维网格的环境中，每一个对象有一个随机初始位置，每一只蚂蚁能够在网格上移动，并测量当前对象在局部环境的群体相似度，通过概率转换函数将群体相似度转换成移动对象的概率，以这个概率拾起或放下对象。蚁群联合行动导致属于同一类别的对象在同一个空间区域能聚积在一起。下面将给出上述两个重要概念群体相似度和概率转换函数的定义。定义1群体相似度是一个待聚类模式（对象）与其所在一定的局部环境中所有其它模式的综合相似度。群体相似度的基本测量公式是公式（1）)(),(1)(rNeighOjjiioodof（1）其中)(rNeigh表示局部环境，在两维网格环境中通常表示以r为半径的圆形区域。),(jiood表示对象属性空间里的对象io与jo之间的距离，常用方法是欧式距离和余弦距离等。定义为群体相似系数。它是群体相似度测量的关键系数，它直接影响聚类中心的个数，同时也影响聚类算法的收敛速度。定义2概率转换函数是将群体相似度转换为简单个体移动待聚类模式（对象）概率的函数。它是以群体相似度为变量的函数，此函数的值域是[0,1]。同时概率转换函数也可称为概率转换曲线。它通常是两条相对的曲线，分别对应模式拾起转换概率pp和模式放下转换概率dp。概率转换函数制定的主要原则是群体相似度越大，模式拾起转换概率越小，群体相似度越小，模式拾起转换概率越大，而模式放下转换概率遵循大致相反的规律。依照概率转换函数制定的主要原则，CSI算法将Deneubourg提出的一种二次曲线简化成斜率为k的直线，如公式（2）和（3）所示：kofkofofkofPpiiii/1)(0/1)(0)(10)(1（2）0)(0/1)(0)(/1)(1iiiiofkofofkkofPd（3）3基于群体智能的Web文档聚类算法基于群体智能的Web文档聚类算法是CSI算法在Web文档聚类方面一个应用。它的主要过程是首先运用向量空间模型表示Web文档信息，采用常规方法如消除停用词和特征词条约简法则得到文本特征集，然后将文档向量随机分布到一个平面上，运用基于群体智能的聚类方法进行文档聚类，最后从平面上采用递归算法收集聚类结果。由于向量空间模型是信息检索领域运用最广泛的模型，本算法中也采用此模型。向量空间模型用特征词条及其权值表示文档信息。向量),,,,(321m表示文档d的特征词条及相应权值，其中m为文档集中所有词条的数目，),,1(miwi表示词条it在文档d中的权值。为了获得特征词条，先将Web中文文档进行分词处理，利用停用词表将停用词从文档特征集中剔除，然后运用倒排文档频率（IDF）约简特征词条，保留文档集中倒排文档频率在一定范围内的特征词条作为文档特征集，选用归一化词频（TF）作为特征词条的权值，这样就得到了一组表示文档集的向量，也就是待聚类的模式集。Web文档向量相似度函数采用IR领域常用的余弦函数，函数返回值在[0,1]之间。数值越大，相似性越大，计算公式如（4）所示。||||),(11jijmimjijidd（4）上式中),,(1imiww为文档id的特征向量，),,(1jmjww为文档jd的特征向量。.||,||1212mkjkjmkikiwdwd公式（1）中群体相似系数是群体相似度测量的关键系数，为了便于选取对群体相似度的基本测量公式进行了如下修改。)()),(1(101)(rNeighOjjiiddsimdf（5）这样的取值一般可控制在[1,10]之间。基于群体智能的Web文档聚类算法描述描述如下：步骤1、参数初始化，,,,,,_sizeRknumberant最大循环次数n，标注类别值clusterno等；步骤2、将待聚类模式随机分散于一个平面上，即随机赋给每一个模式一对（x,y）坐标；步骤3、给一组蚂蚁赋初始模式值，初始状态为无负载；步骤4、fori=1,2……n；步骤4.1、forj=1,2…ant_number；步骤4.1.1、以本只蚂蚁初始模式对应坐标为中心，r为观察半径，利用公式（5）计算此模式在观察半径范围内的群体相似度。步骤4.1.2、若本只蚂蚁无负载，则用公式（2）计算拾起概率Pp；步骤4.1.3、与一随机概率Pr相比较，若Pp＜Pr则蚂蚁不拾起此模式，再随机赋给蚂蚁一个模式值，否则蚂蚁拾起此模式，蚂蚁状态改为有负载，随机给蚂蚁一个新坐标。步骤4.1.4、若本只蚂蚁有负载，则用公式（3）计算放下概率Pd；步骤4.1.5、与一随机概率Pr相比较，若PdPr则