小型微型计算机系统JournalofChineseComputerSystems2010年2月第2期Vol131No.22010自由标签系统中标签的层次关系提取方法刘磊,吴锡(吉林大学计算机科学与技术学院,吉林长春130012)E2mail:liulei@jlu.edu.cn摘要:在自由标签系统中,标签之间没有显式的表示出层次关系,但其内在却隐含着某个标签是其他一些标签的子标签这样的层次关系.提出一种简单高效的、基于概率统计的方法,用OWL本体中的类来表示标签,并从中提取出类的层次关系.实验表明,本方法的提取结果在正确率、召回率上完全满足实际需要,算法执行效率高,非常符合信息飞速增长的互联网的需要.:TP311文献标识码:A文章编号:100021220(2010)0220302205MethodforExtractingTagHierarchiesfromFolksonomyLIULei,WUXi(CollegeofComputerScienceandTechnology,JilinUniversity,Changchun130012,China)Abstract:Infolksonomy,thereisnoexplicithierarchybetweentags,howeverthereimplicitlyexistssuchhierarchicalrelationshipthatonetagisasub2tagofothers.Thispaperpresentsasimplebutremarkablyefficientalgorithmforderivinghierarchicaltaxonomyoftagsfromfolksonomybasedonstatistics,inwhichtag,infloksonomy,isrepresentedbyOWLclass.Experimentsshowthatthisalgorithmhasahighrecallrateandagreatprecisioninadditiontoaremarkableefficiency.Itfitstheneedoninternetwhereinformationgrowsrapidly.是它的分类是非层次的[3],无法表示上面所说的层次关系.本文提出了一种解决以上各个分类系统的缺点,取其长处,以更好的为数据分析服务的方法.该方法是基于概率统计的,能够很好的挖掘出标签与标签之间潜在层次包含关系,然后用一种近似贪心算法的高效算法将标签间的二元关系构建成一个完整的层次图,最终生成OWL本体.1引言元数据被大家最为接受的抽象的定义为:关于数据的数据(dataaboutdata)[1],是一个高度结构化的、提供关于信息资源或数据的一种结构化的数据,是对信息资源的结构化的描述.在互联网中常被用来对数据进行分类.2005年,自由标签系统(Folksonomy)[1,2]也随着web2.0兴起而迅速流行起来.Folksonomy也被叫做协作标签系统,是用关键词将特定内容分类标记的方法,其中起标记作用的关键词被叫做标签(Tag)[123].与此同时,语义网[4]技术也越来越受到人们关注.其中,本体[4]的研究是语义网技术的一个热点,涌现出了很多本体的表示框架,其中最有影响力的是W3C制定的RDFS[5]和OWL[6].同样,在本体中的一个最基本概念:类(class)[527]也是在对事物进行分类.分类可以帮助计算内容的相似度,对搜索引擎分析互联网内容的相关度上能起到很大的作用,特别是带有层次等级的分类.OWL中有很好的表示层次关系的方法:owl:subClassOf[7]可以用来表示一个类是另一个类的子类,这样就有效的表示了两个类的层次关系.虽然分类有种种好处,但是,传统的由领域专家来定义类别的方法虽然比较准确,但已经无法满足现在飞速发展的互联网的需求[1].幸好自有标签系统很好的解决了这一问题,并在实践中被人们所接受.但是,自有标签系统的最大缺陷就2相关研究在与标签相关的研究方面,已经有一些人正在进行研究,如:Hak2LaeKim等人提出了一种在社会语义标签云中(SCOT)计算标签出现频率的方法[8].其中在挖掘标签间层次关系做得比较好的是PatrickSchmitz进行的从Flickr的Tags生成本体的研究[9]和PaulHeymann的基于相似度的计算标签层次算法[10].下面就对这两种算法进行简单介绍.2.1从Flickr的标签中推导出本体的方法该方法是基于包含模型的本体生成方法[9].先是对Flickr中每组标签进行词频统计,并记录下标签与标签之间同时出现频率,并基于父类包含子类的思想,将所有标签之间的关系表示出来.最后通过剪掉如下类之间的关系,以建立类的层次关系:ifA→B,A→C,B→C收稿日期:2008210215基金项目:国家自然科学基金项目(60873044)资助;高等学校博士学科点专项科研基金项目(20060183044)资助.作者简介:刘磊,男,1960年生,教授,博士生导师,研究方向为软件形式化,语义网及本体工程;吴锡,男,1983年生,硕士研究生thendeleteA→B,enhanceB→C,A→B→C图1是该方法的一个测试用例的结果.是关于"圣...