基于凝聚式层次聚类算法的标签聚类研究_曹高辉

基于凝聚式层次聚类算法的标签

＊

聚类研究

曹高辉　焦玉英　成　全

(武汉大学信息资源研究中心　武汉430070)

【摘要】对标签、标注、大众分类等概念进行界定,指出现有标签标注系统中存在着标签描述信息的精确度不高、标签检索结果相关度低、标签缺乏有效组织等问题,提出采用凝聚式聚类算法对标签聚类,从而实现对标签的重新组织,为用户提供更好的标签导航、浏览机制。最后通过实验对标签聚类方法进行验证。【关键词】标签　标签聚类　凝聚式层次聚类【分类号】G250.7

ResearchonTagClusterBasedonHierarchicalAgglomerativeClusteringAlgorithm

CaoGaohui　JiaoYuying　ChengQuan

(CenterforStudiesofInformationResources,WuhanUniversity,Wuhan430070,China)

【Abstract】Thispaperfirstlydefinestag,tagging,folksonomy,thenanalyzesthelimitationofcollaborativetaggingsys-tem.Inordertoachievereorganizationoftheusertagsandbettertagnavigation,browsingmechanism,theauthorspro-poseamethodonusinghierarchicalagglomerativeclusteringalgorithmtoclusterthetags.Finallyexperimentscertifythetagclustermethod.

【Keywords】Tag　Tagcluster　Hierarchicalagglomerativeclusteringalgorithm

1　引　言

　　随着Internet技术的不断发展,互联网逐渐从以信息提供商为中心的Web1.0向以用户为中心的Web2.0转变。Web2.0作为一种架构在用户、微内容、应用基础上的高度网络化、自由化的互联网形态吸引了大量网络用户,衍生出诸如博客、播客、人际网络、网络文摘、维基百科等Web2.0类应用。在Web2.0时代,信息技术的发展使得网络用户广泛参与到信息资源的组织和描述活动中成为可能,用户不再仅仅是网络信息资源的消费者,同时也是信息资源的生产者、描述者、组织者。Flickr、del.icio.us、豆瓣网、和讯博客等网站都采用了协同标注分类法

[2]

[1]

、大众

让用户参与信息资源描述和组织,网站允许用户自由使用标签对文章、图片、视频、声音等对象进行描

述,并利用这些用户标签完成信息资源的分类、组织、检索。然而,与传统的信息资源分类、组织方法相比,采用协同标注对信息资源进行描述、分类、组织、检索过程中存在着信息描述精确度不高、标签组织混乱等缺陷。本文将以豆瓣网的标签为研究数据来源,试图以凝聚式层次聚类方法将用户标签进行聚类,从而实现对用户标签的重新组织,为用户提供更好的标签导航、浏览机制。

　　收稿日期:2007-12-03　　收修改稿日期:2007-12-08

　　＊本文系教育部人文社会科学重点研究基地重大项目“网络环境下数字化信息服务研究”(项目编号:06JJD870006)的研究成果之一。

XIANDAITUSHUQINGBAOJISHU　　23

知识组织与知识管理

　　(2)标签检索结果相关度低

　　标签难以按照统一规范的语词对信息资源进行描述,导致使用标签检索到的信息,查全率和查准率都比较低。实践表明,在RSS、ATOM等信息聚合工具运用中都能根据用户自定义标签实现信息聚合,检索到信息的相关度很低。

　　(3)标签无序、缺乏有效组织

　　现在对标签的组织主要有利用标签搜索引擎和利用可视化的标签空间工具(如标签云)两种方式组织,但标签仍然太凌乱和缺乏有效组织。2.3　标签有序化研究

　　现阶段对于标签系统进行优化的研究主要集中于标签云

[5,6]

[4]

2　研究背景

2.1　大众分类法与标签

　　大众分类法(Folksonomy)是美国信息架构专家ThomasVanderWal和GeneSmith于2004年首先提出,由Folk和Taxonomy两个词合成而来,含义是“由大众的一致意见而产生的基于用户的分类体系”

[3]

,中文翻

译为“通俗分类”、“大众分类”、“自由分类”等。与传统结构严谨的登记体系分类法、复杂庞大的叙词法、分面分类法以及网站预设的信息分类组织体系不同,此种分类法并没有预先定义任何信息分类方法和词表,完全是用户根据个人的使用习惯,以自定义的自由词对数字资源对象进行标注和分类。

　　标签(Tag)是网络用户用于描述某个信息资源所使用的字、词或短语,是大众分类法的一个核心。大众分类法正是采用一种模糊化、智能化的“散秩分类”方式,鼓励大众本着自己的需要和个性化理解,对文字、图片、网页、视频等信息资源使用标签进行标注,通过互联网用户的大量交互以及相关的内容匹配,从而实现有效的信息检索和信息传播。2.2　标签的局限性

　　标签作为新一代互联网形态Web2.0的核心应用之一,实现了大众分类的思想,它的推广和应用将会引发评价标准和分类的多元化,促进人们的远程交流,有利于社会网络的形成。近年来,Flickr、del.icio.us、Technorati等国外的网站成功地将Tag运用于对图片、网络文摘等内容的描述、分类中。2005年,中文博客服务商BlogBus在国内最早引入了Tag理念,“博客中国”(Blogchina)则率先设计开发了Tag搜索引擎,搜狐、新浪等网站也广泛运用了Tag。然而,利用标签实现信息描述和检索还存在许多问题。　　(1)标签描述信息的精确度低

　　首先,标签作为一种原生态的自然语言,其固有语义模糊性、同义词、多义词等特性,这使得难以让大众按照统一规范的语词对信息资源进行描述。再则,对于同一个信息资源,不同的用户由于关注点、兴趣爱好不同,会采用不同的标签对其进行标注,实际上,同一个用户在不同的时间也有可能对同一个信息资源采用不同标签进行标注。换句话说,单一用户难以选择一个合适的标签准确地对某一个信息资源进行分类表述。

,这

两种方式在一定程度上实现了标签和网络信息的有序

、标签的有序化组织

[6,7]

、垃圾标签识别与清

除等方面,本文主要关注标签有序化研究。Begelman等人论述了现有标签系统存在的缺陷,提出采用聚类技术对大量标签进行聚类,从而提高系统的导航和检索性能。研究发现标签同时出现的频率会在某一个临界点显著变化,将这个临界点作为阈值,来确定两个标签是否相关。利用这种相关关系构建成一个加权无向图,图的顶点表示标签,边线的权重表示同时出现的次数。采用“SpectralbisectionClustering”算法对标签进行聚类分析,从RawSugar数据库中采集了200000个页面和30000个标签进行实验,实验表明通过对标签进行聚类,可以提高用户的标注经验和标签的组织。如在实验系统中检索“health”,将能检索到shopping、nutrition、fitness、science等相关标签,但这些标签是杂乱的,通过对相关标签进行聚类,可以得到如图1所示的结果

[4]

:

Querytag:health—shopping,research—nutrition,food,diet—fitness,workout,running—article,science

—life,lifehack,product,howto,get　

图1　“health”相关标签聚类结果

　　Heymann和Garcia-Molina试图构建标签的层次分类,他们从del.icio.us上搜集了60000个标签,根据标签的向量相似度确定相关标签,将相关标签连接成无权重的无向图,采用相关算法将无向图转换为层次

　24　现代图书情报技术总第163期　2008年　第4期

结构的分类树

[7]

。再进行聚类生成树状层次结构视图。

　　已有研究成果表明,对标签进行聚类,有助于实现标签的有序化组织。本文在综合上述学者研究的基础上,采用凝聚式层次聚类(HierarchicalAgglomerativeClustering,HAC)算法来探讨标签聚类的有效方法。

3　基于凝聚式层次聚类的标签聚类

3.1　聚类分析

　　聚类(Clustering)是分类的一种,是分类的逆向方法,它采用的分类规则是统计学的聚类分析方法

[8]

图2　标签聚类系统示意图

3.3　标签特征抽取

　　在传统的信息检索模型中,特征项是指文档中能够代表文档性质的基本语言单位(如字、词),也就是通常所指的检索词。而标签本身就是单独的字或词,难以对其再进行抽取。现有的标签系统往往根据用户使用标签的频率提供相关标签,如在豆瓣网中,与“小说”相关的标签有“外国文学”、“文学”、“爱情”、“外国小说”、“美国”、“中国文学”、“中国”、“名著”,这些相关标签在一定程度上对“小说”这一标签的概念进行了描述,但系统中相关标签采用平行视图,难以精确展示标签之间的关系,不能为用户提供良好的导航视图。笔者将在已有的标签系统中,检索与某一个标签相关的标签,抽取与检索词同时出现的标签为描述项,采用传统空间向量模型表示,计算标签之间的相关程度,从而实现标签聚类。具体实现步骤如下:

　　①对于标签p,检索相关标签,并对相关标签进行预处理,得到n个相关标签,以D(t)表示;p=1,t2,…,tn

　　②采用空间向量模型来表示特征选项,V(d)=(t1,w(d);…;t,w(d);…;t,w(d)),其中t表示第i个相关1iinni标签,w(d)表示t在向量V(d)中的权重,采用传统的TF-iiIDF权重计算方法来计算每个相关标签在相应向量中的权重,计算公式见公式(1):

w(d)=(1+logf)×log(N/n+0.01)t,it,ii

(1)

。

聚类分析作为统计学的一个分支,已被广泛地研究了多年,主要集中在基于距离的聚类分析。基于K均值、K-medoids和其他一些方法的聚类分析工具已经被加入到许多统计分析软件包或系统中。在机器学习领域,聚类是无指导学习的一个例子,与分类不同,聚类和无指导学习不依赖预先定义的类和带类标号的训练实例。在概念聚类中,一组对象只有当它们可以被一个概念描述时才形成一个簇,这不同于基于几何距离度量相似度的传统聚类。常见的聚类分析的方法有4类:划分方法、层次方法和基于密度的方法、基于网格的方法

[9]

。聚类分析常用于对大量文本聚类进行数据

挖掘,本文试图将聚类分析技术应用于标签聚类中。3.2　标签聚类的基本思想

　　标签聚类与传统的文本聚类存在很大差别,传统的文本聚类中,由于文本包含的信息量大,可以采用文档频度、信息增益、X统计、互信息、给定词浓度等方法提取文本特征

[10,11]

2

,构建文本矩阵,实现文本聚类。

而标签一般都是单个的字、词或短语,包含的信息量很小,计算机难以自动抽取其特征。本文中将采用如图2所示的方法,借助标签系统中已有的标签,根据其他用户的标注,进行特征抽取,然后采用HAC算法实现标签的聚类,生成树状层次结构视图。如在豆瓣网中标签“小说”、“文学”、“数学”可以分别用“外国文学、文学、爱情、外国小说、美国、中国文学、中国、名著”、“小说、外国文学、中国、中国文学、散文、欧美、诗歌、名著”、“数学分析、Math、数学相关、科普、好玩的数学、概率论、经济数理基础、数学史”这样一些相关标签进行描述,可以看出“小说”和“文学”都有“外国文学”、“中国文学”相关标签,而“数学”与“小说”、“文学”没有相同的相关标签,根据相关标签计算它们之间的相关度,

其中f表示t在V(d)中的频率,N表示标签总数量,n表t,iii示t在相关标签向量中出现的次数;i

　　③计算标签向量相关度,以sim(v,v)表示向量vaba和v的相关度,计算公式见公式(2):b

sim(v,v)=cos(v,v)abab

(2)

　　④计算向量集合的平均相关度,simA(C,C)表示标签ij集C和C的平均相关度,计算公式见公式(3):ij

1

∑∑cos(v,v)(3)simC,C)=abA(ij

v∈C∈C C C aivbjij

3.4　凝聚式层次聚类算法

　　凝聚式层次聚类是一种常用的文本层次聚类方法,它自底向上分析目标文档,每个目标文档最初被看

XIANDAITUSHUQINGBAOJISHU　　25

知识组织与知识管理

成一个最小的聚类,两个相似度最大的聚类被合并为一个最大的聚类,这个过程一直持续到所有文档合并为一个聚类或者达到一个终止条件。其实现的基本思想如下

矩阵;

　　②初始构造n个簇类,每个文档自成一簇类;　　③合并距离最近的两个类为一个新类;

　　④计算新类与当前簇类的相似性,更新相似性矩阵,若簇类数等于1或达到一个停止准则,则跳到步骤⑤,否则跳到步骤③;

　　⑤选定分类阈值,决定簇类的个数和簇类。

[12,13]

　　②计算C中每对簇类(C,C)之间的相似度sim(C,ijiC),形成初始相似性矩阵S;j

　　③选取具有最大相似度的簇对max(sim(C,C)),并将ijC和C合并为一个新的簇类C∪C,从而构成D的一ijk=Cij个新的簇类C={C,更新相似矩阵;1,…,Cn-1}

　　④重复上述步骤,直到C中只剩下一个类或者满足停止规则为止。

:

　　①计算n个文档两两之间的相似性S,记为初始相似性ij

4　标签聚类实验

4.1　数据采集

　　实验从豆瓣网(www.douban.com)采集数据,选择了Java、Python、编程、软件4个标签,分别用P1、P2、P3、P4表示,从豆瓣网检索相关标签,对检索数据进行处理,选择出与查询标签最相关的前20个标签,如表1所示。4.2　相关标签权重计算

　　采用的公式(1)计算相关标签的权重,计算结果如表2所示。

　　所谓停止准则是指用户提前定义聚类数目或者聚类程度,当达到这个数目或程度时,聚类自动停止。具体过程如下:

　　①将文档集D={d,…,d,…,d}中的每一个文档dlini看作是一个具有单个成员的簇类C={d},这些簇类构成了iiD的一个聚类C={C,…,C,…,C};lin

表1　前20个最相关标签表

P1相关标签

编程J2EE计算机重构软件开发Spring软件工程Hibernate技术设计模式Design虚拟机JUnitStruts模式WebEffectiveTomcatFrameworkEclipseJSP

频率1551081381059791786965503541272121181715141413

P2相关标签

编程计算机程序设计脚本技术Oreilly程序语言Django网络WxPythonCookbook计算机科学

WebTwisted软件开发Nutshell教程GUI入门Design开源

频率1856137222217151212121010998887765

P3相关标签计算机算法C++UNIX软件软件开发设计模式

CJavaScript程序设计计算机科学

经典重构PythonJava代码大全计算机系统

DomDesign算法导论SICP

频率6044432342122092001751581541311141071059996838282675941

P4相关标签软件开发编程计算机设计模式项目管理Java交互设计重构管理代码大全设计软件敏捷开发DesignUI人月神话Code程序设计AgilePattern敏捷

频率312305285212181161136105958374736767594945403837

　26　现代图书情报技术总第163期　2008年　第4期

表2　相关标签权重表

TagAgileCC++CodeCookbookDesignDjangoDomEclipseEffectiveFrameworkGUIHibernateJ2EEJavaJavaScriptJSPJUnitNutshellOreillyPatternPythonSICPSpringStrutsTomcatTwistedUI项目管理虚拟机重构UNIXWebwxPython编程程序设计程序语言代码大全管理计算机计算机科学计算机系统技术交互设计脚本教程经典开源敏捷敏捷开发模式人月神话入门软件软件工程软件开发设计设计模式算法算法导论网络

P1000000.0022000.12540.15230.125400.61820.9677000.11650.2419000000.81540.18820.13440000.36740.199900.081100.295200000.00000.292800000000.18820000.690.006200.0952000

P200000.07510.00030.090100000.05250000000.06010.12760000000.0676000000.0340.09010.29520.0590.1126000.00330.037700.08300.16520.060100.037500000.0525000.000400000.0901

P30

0.36330.538000.001100.18850000000.1110.3541000000.22760.094300000000.05130.48750000.000.095900.01　0.13180.188500000.2460000000.241600.003300.08550.98320.13570

P40.1781000.218100.0021000000000.3603000000.16910000000.24930.805700.09930000.28850.042600.18570.42290.00910000.605400000.170.298200.218100.163300.01　0.32940.2006000

4.3　聚　类

　　根据相关标签权重表,分别计算标签之间的相关度,计算结果为Sim(P1,P2)=0.0153,Sim(P1,P3)=0.0296,Sim(P1,P4)=0.0997,Sim(P2,P3)=0.0279,Sim(P2,P4)=0.2714,Sim(P3,P4)=0.1191,聚类结果示意图如图3所示。

图3　P1、P2、P3、P4聚类结果示意图

5　结　语

　　本文提出采用层次凝聚算法对用户标签进行聚类,以达到为用户提供更好的标签导航机制。通过实验表明,文中所提出的方法能够完成标签聚类,对聚类结果进行可视化后,能够在一定程度上表现标签之间的语义关系。接下来,笔者将对下面的内容作进一步研究。

　　(1)完善标签权重算法,将用户数引入到权重计算中;

　　(2)对聚类结果进行优化,使其能更好的表达标签概念之间的语义关系;

　　(3)研究其他聚类方式在标签聚类中的应用,并比较不同聚类算法在标签聚类中的效率。

参考文献:

[1]GolderS,HubermanB.UsagePatternsofCollaborativeTagging

Systems[J].JournalofInformationScience,2006(2):198-208.[2]HammondT,HannayT,LundB,etal.SocialBookmakingTools

(I):aGeneralReview[EB/OL].[2007-12-05].http://www.dlib.org/dlib/april05/hammond/04hammond.html.[3]MathesA.Folksonomies-CooperativeClassificationandCommuni-cationThroughSharedMetadata[EB/OL].[2007-11-10].www.adammathes.com/academic/computer-mediated-communi-cation/folksonomies.html.

[4]BegelmanG,KellerP,SmadjiaF.AutomatedTagClustering:Im-provingSearchandExplorationintheTagSpace[C].In:Collabo-rativeWebTaggingWorkshop,15thInternationalWorldWideWeb

XIANDAITUSHUQINGBAOJISHU　　27

知识组织与知识管理

Conference,Edinburgh,UK,May22-26,2006.

[5]Speroni.TagcloudsandCulturalChanges[EB/OL].[2007-11-10].http://blog.pietrosperoni.it.

[6]OwenK,DanielL.TagCloudDrawing:AlgorithmsforCloudVisu-alization[C].In:proceedingsofTaggingandMetadataforSocialInformationOrganization(WWW2007),2007.

[7]HeymannP,Garcia-MolinaH.CollaborativeCreationofCommu-nalHierarchicalTaxonomiesinSocialTaggingSystems[EB/OL].[2007-11-10].http://dbpubs.stanford.edu:8090/pub/2006-10.

[8]孙建军,成颖.信息检索技术[M].北京:科学出版社,2004:

201-202.

[9]张建辉.K means聚类算法研究及应用[D].武汉:武汉理工大

学,2007.

[10]YangY,PedersenJP.FeatureSelectioninStatisticalLearningof

TextCategorization[C].Inthe14thInt.Conf.OnMachineLearn-ing,SanFrancisco,1997.

[11]ChuangSL,ChienLF.TaxonomyGenerationforTextSegments:

aPracticalWeb-basedApproach[J].ACMTransactionsonInfor-mationSystems,2005,23(4):363-369.

[12]ChuangSL,ChienLF.TowardsAutomaticGenerationofQuery

Taxonomy:AHierarchicalQueryClusteringApproach[C].In:Proceedingsofthe2002IEEEInternationalConferenceonDataMin-ing,MaebashiCity.Japan:IEEEComputerSocietyPress,75-82.

[13]BrandesU,GaertlerM,WagnerD.ExperimentsonGraphCluste-ring[C].In:Proceedingsofthe11thAnnualEuropeanSymposiumonAlgorithms(ESA'03),volume2832ofLectureNotesinCom-puterScience,2003:568-579.

(作者E-mail:ghcao@mail.ccnu.edu.cn)

　28　现代图书情报技术