基于改进K-medoids算法的社会化标签聚类研究
2014-07-25郭伟光
郭伟光
（合肥学院 管理系，安徽 合肥 230061）
基于改进K-medoids算法的社会化标签聚类研究
郭伟光
（合肥学院 管理系，安徽 合肥 230061）
为了对社会化标注系统中的标签进行有效聚类，并针对传统K-medoids算法存在的聚类结果易受初始聚类中心影响的问题，本文提出了一种改进的K-medoids标签聚类算法.该算法应用社会化标签的余弦相似值进行初始聚类中心的选择，然后进行标签聚类.对Delicious标签数据集的实验结果表明算法具有较强的的可行性和有效性.
社会化标签；标签聚类；K-medoids聚类算法
1 引言
社会化标注系统是允许用户对网络资源（如照片、博客、网址、地图、视频等）赋予个性化的标签，并通过标签的聚合和相关度来实现信息组织的系统.标签是一种用户标注的关键词，该关键词隐性反馈了用户兴趣.近年来，Youtube、Flickr、Last.fm和delicious.com等一大批基于社会化标注系统的网站取得了巨大的商业成功和社会影响力.
在社会化标注系统中，用户可以自由地选择词语对其感兴趣的内容进行标注，由于用户认知程度不同，不同用户在标注同一网络资源时使用了不同的标签，但是系统却无法创建这些标签之间的联系，从而导致了标签的多样性和模糊性.因而，有必要采取一定的分析方法，寻找标签间的相互关系，识别可能存在的相关标签组或标签群，进行标签或其标注的资源的自动聚类，这对于改善网络搜索、个性化信息推荐服务和实现标签间的语义关系的自动提取都具有重要意义.
2 相关研究
在社会化标注（Socialtagging）系统中，包括了三个主要要素：用户、资源和标签，其中资源主要是网络URL.社会化标注系统模型如图1所示.在图1中，资源R2分别被用户User1、User3使用
图1 社会化标注系统模型
聚类是一个将整体的数据对象划分为以类或簇存在的包含局部数据对象的过程.目前常用的聚类算法主要有划分聚类算法和层次聚类算法.标签的聚类是利用标签统计学规律以及相关聚类算法，将标签或其标注的资源划分为不同的子集，聚类结果一般有两种，一种是同类（或相关）标签的聚合，这是非层次聚类的结果；另一种是同类（或相关）标签间的概念空间，这是层次聚类的结果.韩敏[1]提出一种基于TFIDF的标签相似度计算方法和基于该相似度的聚类算法；曹高辉等人利用凝聚式层次聚类方法将用户标签进行聚类，从而实现对用户标签的重新组织[2]；Begeman等人[3]提出了利用自动标签聚类的方法来改善自由分类法的检索和浏览；吴志媛等人[4]提出使用概率潜在语义索引模型对标签进行潜在语义分析，经回火期望最大化法训练得到在潜在语义下的条件概率，生成概率向量并在此基础上，提出凝聚式层次k中心点聚类算法对概率向量进行聚类；熊回香等人[5]提出运用关联规则挖掘标签间的相互关系，并结合典型的划分聚类算法K-medoids进行Tag资源自动聚类，从而实现对Tag资源重新组织.总体来说，目前主要集中于对社会标签之间聚类算法的研究以及基于社会标签进行相似用户的发现和资源推荐，而在基于社会标签改善资源聚类效果方面的研究相对较少.
K-medoids算法(Kmeansclusteringalgorithm，K-medoids)是基于划分的经典聚类算法之一[6].该算法的基本思路是：选取数据集里的实际对象来代表簇，每个簇使用一个代表对象，聚类过程有两个主要步骤，首先任意指定每个簇的代表对象，计算其余对象和K个聚类代表对象间的距离，并将其分配到与之最后近的代表对象所在的簇中；接着计算、更新K个簇的代表对象，这两步迭代执行下去，直到簇不再改变.K-medoids使用一个准则函数来衡量聚类效果，E值越小聚类效果越好：
P为簇Cj中的非代表对象，oj为簇Cj的中心对象，|p-oj|表示两个对象间的距离.
K-medoids算法易于实现，但K-medoids算法仍然有一些缺点：第一，它对初始聚类中心敏感，如果随机选择的初始聚类中心分布过于密集，或选择噪音数据和边缘数据，则不能很好的代表整个数据集中数据的分布情况，这可能会导致算法收敛于局部最优解，并很难得到全局最优解；第二，必须预先设置聚类数目k，而这个值在缺少先验知识的情况下是非常难以估计的.
3 基于改进K-medoids算法的社会化标签聚类算法
K-medoids算法需要事先确定聚类个数K和K个初始聚类中心，特别是对于K个初始聚类中心的选择，K-medoids算法极其的敏感，其所获得的聚类结果将会随着初始聚类中心的不同而不同，容易使算法陷入局部最优.为了改善这一问题，我们所提出的算法首先计算标签的相似值，并应用标签相似值辅助选择聚类中心.在标签K-medoids聚类时，相似的标签会往聚类中心移动，如此一来能提高聚类中心的稳定性并提高分群结果的精确度.
定义1（数据集D）：设数据集D（uitj,rk)，（i=1KM，j=1KX，k=1KY）表示用户ui用标签tj标注了网络资源rk.数据集的标签经过一定的清冼（如标签小写化，符号、乱码清理等）都具有一定的语义标识能力.
定义2（标签向量）：设数据集D中，标签tj的标签向量Tj=(wj1KwjkKwjY)，其中wjk只能取值为c (c=1,2K），若wjk=c表示用标签tj标注了网络资源rk总共c次，否则wjk=0.
定义3（标签的相似性）：设数据集D中，标签tj与标签tn之间的相似性为；标签两两进行相似性计算，构成标签的相似性矩阵ConSimX×X=（ConSimj1,Λ,ConSimjn,ΛConSimjX）（j=1KX, n=1KX）
算法名称：基于改进K-medoids的社会化标签聚类算法
输入：数据集D，资源聚类数目K；
输出：K个标签簇
算法流程：
（1）根据定义1构建数据集D；
（2）抽取数据集D中标签和资源，分别形成标签集T，则|T|=X，资源集R，则|R|=Y，即数据集中共X个标签，Y个资源.以标签为行，以资源为列构建标签向量矩阵TRX×Y，其中等j行为标签tj的标签向量Tj=(wj1KwjkKwjY)；
（3）应用定义3中公式，计算标签tj与标签tn之间的相似性ConSimjn，构成标签的相似性矩阵ConSimX×X；
（4）建立K个空心簇，并将其中一个初始化为标签集T；
（5）计算各个簇中包含标签的个数，选择标签最多的一个簇，记为M；
（6）在M中选取两个最不相似的标签ta和tb（即ConSimab值最小）分别填充到创建的空簇中；
（7）分别以ta和tb为聚类中心，根据M中剩用标签分别与ta和tb的相似性，将这些标签分别归并入与ta和tb相似度最大的那一个类别之中；
（8）检查是否将数据集T划分为K个类簇，是则转第10步，将得到K个聚类中心，否则转第5步；
（9）根据第8步得到的K个中心点，重新进行K-medoids聚类；
（10）重新计算每一个标签簇新的中心点，比较新的中心点与上一次计算得到的中心点，如果中心点不变转第11步，否转到第9步；
（11）输出聚类后的K个标签簇，算法结束.
4 实验与结果分析
实验数据来源于社会化标注的典型应用delicious.com.数据集是明尼苏达大学计算机科学系GroupLens实验室收集整理的hetrec2011-delicious-2k数据集（下载地址：http://grouplens.org/ datasets/hetrec-2011/），该数据集主要收集了2010年437593个[user,tag,URL]标签标注记录.我们的实验使用了其中2010年11月份的数据共10660个[user,tag,URL]记录，经过清理剩下9268个[user,tag, URL]标注记录作为实验数据集D.
由于所提出的方法是按照Folksonomy的方式去进行标签资源分群，所以请网络用户评价一些标签是否应分在一群是比较是合理的.但直接评价标签分在一组是否合理有一定的困难，我们的思路是选择该组标签标注网络资源的相似性来评价标签的聚类结果，如果该组网址有较高的相似性，说明该组标签一定有内在的关联性.我们的评价方法是从各标签群标注的网络资源中分别找出一些网址资源请用户去评价其相似性并打分，评分结果分为非常认同（得4分）、认同（得3分）、一般（得2分）、不认同（得1分）、非常不认同（得0分）.例如：http: //cn.reuters.com/与http://www.hexun.com这两个网址为相似网站，您的评价是：非常认同、认同、一般、不认同、非常不认同.
我们的实验方法是请40名大学生，在同一时间根据提供网址资源上网浏览后给出评价.实验分2次进行，分别确定K值为3和5，即网址资源分3群和5群，我们分别从每次实验结果的每群中找出用户标注次数的10个网址资源两两一组让用户评价.第一次的平均分数为58.3%，第二次的平均认同分数为67.6%，说明用户对这样的分群结果是有近65%的认同率，可见认同率是较高的.
5 结束语
Folksonomy是一种大众化的分类机制，简单来说就是由用户自发使用标签定义信息类别，不像Taxonomy要按照事先规定的类别框架进行分类.为从群体智慧中获取有用信息，我们从Delicious中提取标签进行聚类研究，并且利用改进的K-medoids算法以达到更好的聚类结果.但还有一些问题需进一步研究，比如最终的聚类数目K的值会直接影响聚类的结果，那么如何确定最佳K呢？再如什么样的标签必须过滤，哪些看似无意义却是聚类中重要的连结中继点的标签应当保留等.
〔1〕韩敏,唐常杰,段磊，等.基于TF-IDF相似度的标签聚类方法[J].计算机科学与探索,2010,4(3): 240－245.
〔2〕曹高辉,焦玉英,成全.基于凝聚式层次聚类算法的标签聚类研究 [J].现代图书情报技术，2008 (04):23－28.
〔3〕BEGEMAN G，KELLER P，SMADJIA F．Automatedtagclustering:improvingsearchand explorationinthetagspace［C］//Procof Collaborative Web Tagging Workshop at WorldWideWeb．2006:22－26．
〔4〕吴志媛,钱雪忠.基于PLSI的标签聚类研究[J].计算机应用研究,2013,30(5):1316-1319.
〔5〕熊回香,王学东.社会化标注系统中基于关联规则的Tag资源聚类研究[J].情报科学,2013,31(9): 73－77.
〔6〕王勇,唐靖,饶勤菲等.高效率的K-medoids最佳聚类数确定算法 [J].计算机应用，2014，34(5): 1331－1335.
G250.2；TP393.09
A
1673-260X（2014）12-0017-03
安徽省教育厅自然科学基金一般项目“基于社会化标签的用户兴趣建模与个性化信息推荐研究”（KJ2012B155）；合肥学院科研发展基金重点项目“基于社会化标注的电子商务商品个性化推荐模型及算法研究”（13KY08ZD）
