论文研究 一种基于动机倾向的标签推荐方法.pdf

为了能够推荐符合用户信息需求的标签, 在深入分析社会标签空间和传统标签推荐方法的基础上, 提出了度量用户和资源的动机倾向性的五种指标, 并对其测度有效性进行了验证。基于此指标体系, 建立了动机倾向性判别模型, 并设计了推荐算法。实验结果表明, 基于动机倾向的推荐算法比当前主流推荐算法具有更加准确的推荐结果。74计算机应用研究第30卷相同时,TSOF→1,说明用户有描述倾向;反之,说明用户u所使用的样本数据为推荐实验所用的两个数据集,每个数据集有分类倾向。包含100个用户所有资源的所有标注。每和度量指标都是从1.2.5标签的相对条件熵不同的方面来度量用户的标注动机。但从表2的检验结果来从信息论的角度看,用户选择标签的过程就是为资源进行看,相关性较高的是TRR和TSOF,这两个指标本质上是致编码的过程。对于分类倾向的用广来说,他们希望标签有最大的,其他的三个指标中LFIH和TRCE高度相关。相对来说的区分度,实际上就是希望为特定信息的编码最短,即条件信五个指标中ST"R和其他指标的相关性要小些。这些高度相关息熵最大。根据信息熵的知识,每个标签的使用率相同吋,标的指标预示着可能有相似的动机。例如,为提高浏览效率和分签的条件信息熵最大。也就是说,所有标签都有均等机会被使类一致性,分类倾向的用户会尽可能使用少而不重复的标签用到。而对于描述倾向的用户来说,他们并不关心标签的区分这样他们的TRR和TSOF就会比较低。同时,他们希望尽可能度。可以按照式(4)来计算标签的条件信息熵。少地使用低频标签,尽可能使得每个标签都有相同的使用率,Hn(R|T)=-∑∑n(r,)log2p(rt)(4)即使得LFTR和TRCE尽可能的低。其中:;(r,)为标签在资源上的分布。为了能够区分用户之间表2五种动机倾向性指标的 Spearman系数的差别,对条件熇过行归一化处理以保留编码信息,用实测的指标 TRR LFTR TRCE TSOF STR条件熵(R7)和理想的条件熵〃(RT)进行比较。理想TRCE0.810.8的条件熵lm(|T)在每个标签都有相同使用率的情况取得。在此基础上,用户u标签的相对条件熵 TRCE( tag relative conSTR0560.490.5ditional entropy)计算如式(5)所小。TRCE,=H (RIT)-H (RIT)J/H (RIT)2用户倾向性判别品然,TRCE∈(0,1)当用户u把标签用做分类时,标签21用户倾向性判别分析的区分能力最强,条件嫡也最接近理想情况,此时,TRCE。也社会标签系统中并不要求用户具体描述使用标签的日的越接近0,可以认为用户也倾向十分类;反之,可以认为用广倾和解释选择某一标签的因。但在标注时,用户实际上在短时向于描述。间内启动∫一个语义建立过程,即当用户浏览资源时,用户在1.2.6疑问副词标签使用率脑海中就形成了一些与资源相关的概念,然后从众多概念中选般情况下,用户不会使用when、how、what等疑问副词作择合适的概念赋予资源1。虽然这个过程间完成,但为标签。但笔者对实验所用数据进行处理时发现,疑问副词作定程度上还是能反映一段时间内用户相对稳定的信息需求为标签时,该次标注的其他枟签往往是资源标题中的实词。对虽然不能直接度量标注用户的动机,但可以利用标注的结使用疑问副词作为标签的这类用户进行分析,发现这类用户具果进行反推。本文使用了五种指标对用户所使用的标签历史有明显的描述倾向,如图1中用户 breneaux的标注记录进行度量。基于这种度量,构建判别用户动机倾向性的模型When it drope I helping you keep track cf the newest releasee eAVEIeHAnes lates games mories books rek如下WUHtb11 D'ibbble. Melanie matthews saM,=CIa TRR +C,* LFTU +C,* TRCE + Ca TSOF +Cs STR (723 11 Dve Into HTML5 SAVE ShARE18.N1ign Inspiration: 30 Creative Negative Space Logos I iBrandStudio其中:c=(c1,r2,3,4,3),C1,C2,C3,C4,C5∈(0,1)为判别系bgo ccirn nspiaju数;T"RR、IFTU、TRCF、TSOF、STR为1.2节中所构建的度量指iBrandStudio| Freebies, Tutorials, and Inspiration Resources for Designing thedesign blog inspan branding tutorial reference tutors m枟,这些指标的取值均在0~1间。显而易见,Mn∈(0,1)。根musc mashup koons annatto gun tak据1.2节中每个指标的含义,很容易推理出以下结论:C9 DEC 10 Meet Buck on Vimeo sAvE:HAHtFacebook animal mowa)M,具有单调性。图1用户 breneaux的标注记录b)当M。因此,疑问副词作为特殊标签的使用率可以作为用户标注M时,用户u的动机趋于描述,M1m为分类动机和描述倾向性的判别指标之一。如果用户使用疑问副词标签的比例动机的临界值。很高,那么该用户可判定为具有描述倾向;反之,可判定为具有因此,在判定用户动机倾向性时,首先计算该用户的五个分类倾向。疑问副词标签使用率STR( special tag ratio)计算度量指标,并将计算结果代入推荐模型计算得到M,将M。和如式(6)所示。临界值M-进行比较来确定用户的动机倾向性,按照式(8)STR1=curd(t∈T)/|Tn(6进行判别。其中:=|what,who,when, where,…l;card(t∈)为用户uM> Mbrcshald用广属于描述动机使用疑问副词作为标签的个数,含重复计数。显然,STRn∈M< Muresluld用户属于分类动机(0,1)。当STR→1时,用户u越可能具有描述倾向;当STRM4= M用户动机待判如0时,用户u越不可能具有述倾向。临界值Mlc和判别系数c的确定方法参考文献[19]1.3度量指标间相关性检验Mlm的计算如式(9)所示。为了吏好地建立推荐模型,本文采用 Spearman系数(表Muesul=(n M,+2M)/(nI+n2)2)对用户标注倾向性的度量指标间的相关性进行检验。检验其中:n1、M为描述倾向用户数和所有描述用户M值的平均第1期靳延安:一种基于动机倾向的标签推荐方法75值,n2、M,为分类倾向用户数和所有分类用户M值的平均值。输出:标签列表L通过计算可以得到本文数据集的临界值M=0.4461,所1计算r的五种度量指标,把r的动机倾向性表示为M:=(TRR对应的判别系数为c=(0.854,0.713,0.496,0.261,0.091)。TFT1,TRCF:,TS0F;,STR2)。2.2度量指标反映用户标注动机有效性检验2计算u的五种度量指标,把u的动机偭向性表示为M。=本文中用户动机倾向性的主要判定依据是1.2节中所提TRR LFTU, TRCE,, TSOF, STR,)3 Rim =,t=qp到的五种度量,那么这些指标是否真的有效,必须加以讨论4 for i=1 to IR为了检验其有效性,笔者首先使用OMDM模型对样本用户进5计算r1的五和度量指标,把r的动机倾向性表示为M行动机倾向性判别,然后采取人工方式对样本用户的动机倾问(TRR,, LFTU, TRCE. TSOF. STR性进行评判,进而比较两者的·致性。OMDM模型判别使用6 for i=1 to IIR式(8)即可,使用表3进行人工评判。样本数据来自于 Bibo7 beginnomy和 Delicious数据集。8sim;e,(M,M2)=M,·M;/|M1|M表3不同动机的特征9 if simie r(M-,M:)>α分类倾向描述倾10R=H∪资源杯签率低同义词出现情况高多小多12 fi改变标答的代价大13 begin标签取自标题词表规模有限无限14sim;eB(M-,M1)=M·M/|M1‖M浏览查询与检索15sim∈Bin(M1,M)>β人工评判过程如下:从 Delicious和 Bibsonoiny中各选取三rlin(Mr,M1)≥B个用户,记为P1,P2,P3,P4,P5,P6}。由这六个用户对他们每17 end次标注按分类倾向和描述倾向进行归类,并完成从用户A的18m(1)=[0,…,0],In=标签判断用户所属动机(表4)。19/rec(t)为标签1与资源相关性表4从用户A的标签判断用户所属动机20 for each t in T用户A的标签分类倾向描述倾向21 for each w in rr1,r2URLo23 p(w)=log(t(w, r)/N,+1)log (NR/IR(w)I+I24 s(wD log N-min( i log f(w),logl(ovpmax( log f(w), log f(t))-log f(w, t)r1,t2□5计算re(t)=∑p(w)s(本文采用平均Cohn’ s Kappa系数κ来验证人工评判与6 L,=L,UtOMDⅥ模型方法的致性。如果0.6≤K<0.80,可以认为人27 end工评判与OMDM模型方法具有很好的一致性。已就是说,8按照re(1)降序排列Iuc五种揞标能够真实反映用广动机 c Cohen’ s Kappa杀数计算如3.2用户和资源的动机倾向性表表5所示,平均 Cohen'’ s Kappa系数k=0.65。正如引言所述,用户在标注吋的动机倾向性并不是一成不表5人工评判与OMDM模型方法的一致性检验变的,可能在标注某一资源时倾向于使用描述的标签,而换另用户PPP个资源时可能倾向于使用分类的标签。因此,用户的标注动P10.630.780.720.650.690.740.570.50.540.660.63机不可能很绝对地分成分类动机和描述动机,只能是倾向于某0.640.690.610.一种动机。基于1.2节提出的倾向性度量指标,本文把用户uP0.670的动机倾向性M,表小为P0.620.65M =(TRR., LFTU, TRCE, TSOF, STR)P0.58其中:TRR、LFTU、TRCE、TSOF、STR,分别为用户u的五种3基于OMDM模型的标签推荐方法度量指标在社会标签系统中,每一个资源被不同的用户在各种动机享法3.1基本思想及算下进行标注。一个用户可能使用分类标签来标汁,而另一个用基木思想是首先找到与待标注资源有相似动机倾向性的户可能使用描述标签来标汴同一资源。因此,可以认为不同类其他资源;然后筛选出与用户具有相似动机倾向性的资源,并型的标签反映了资源的不同动机倾向性。那么,对于个资源聚合它们的标签;将这些标签作为候选推荐对象依次计算候r,同样可以用五种度量指标来表示其动机倾向性,如式(11)选推荐对象和待标汴资源内容的相关性,将相关性大的标笭推所示。荐给用户。其算法措述如下M, =(TRR, LF'TL,, TRCE, ISOF, SIR.)(11输人:资源集合R,用户集合U,标签集合T;特定用户u;待标注其中:TR,、IFTU、TRCF、TOF,、ST,分别为对资游的五种资源r度量指标。76计算机应用研究第30卷3.3发现与待标注资源动机倾向性相似的资源户从推荐候选标签中的选择比率。但山于客观现实不能满足,通常情况下以前使用过的标签是用户标注资源的首选。所以本文采用式(16)来计算推荐的准确率。因此,可以充分利用与待标注资源相似的资源标签作为候选标准确率P=ard(推孝标签列表∩原始标签列表card(推荐标签列表)(16)签,这样将会得到与用户意图相似的标签。资源相似性计算采表6给出了在 Bibsonomy和 Delicious数据集上基于CRM用基于向量空间的余弦法来计算,如式(12)所示。和OMDM两种模型进行推荐的准确率。从表6中可以看出sim,er(m, )=4.M /IM, I(12)OMDM的平均准确率超过了CHM。分析这一现象的主要原因其中:M,、M分别为用户已标注和待标注资源的动机倾向性表示。为了降低数据规模和找到更准确的标签本文仅考虑和标签更符合用炉意标注动机出发进行推荐,此推荐的在于OMDM是从用户待标注资源的动机倾向具有较高相似性的已标注资源。将这表6基于CRM和OM冂M两种模型进行推荐的准确率比较些已标注资源的集合表示为Rm,即Rm={rsim,;c(M,数据集推荐方法P@5P@10,a为相似性控訇因子0.630.598Bibsonomy3.4计算β中与用户动机倾向性相似的资源并聚合标签OMDM F0.756CR计算Rm中资源与用户倾向性的相关度,如式(13)所示。DeliciousOMDM0.7920.787R(M,, M)=M,MIM, M.(13)表7为控制因子α对推荐准确性的影响。从表7可以看其中:M,为R中资源的倾向性表示,M为用户的倾向性表出,控制因子a对推荐准确性的影响比较大。分析其原因主示。同样,为了降低数据规模和找到更符合用户意图的标签要在于各个资源之间的倾向性差异较大,更深层的原因是資源这里只考虑与用户的动机倾间具有较高相似性的已标注资源。的内容区别比较大。提升控制因子a,推荐准确率增加明显。因此设定控制因子来控制聚合的资源数量按照式(14)聚从表7中还可以看出,控制因子a对Dims数据集的影响合与用户有着相似动机倾向性资源的全部标签,这个集合记较 Bibsonomy数据集大,这主要是因为 Bibsumumy是对学术论为T。文的标注系统,其多数标签是取自于学术论文的内容,而Deli=0,sim(M2,M2)≥B(14)cios本身就是一个基于标签的分类系统。3.5生成推荐标签表7控制因子α对推葶准确性的影响资源的内容是标签推荐时不能忽略的重要囚素。囚此,当_数据集控刽因子P@5P10P020为用户标注特定的资源时推荐标签,必须考虑标签与特定资源0.20.6390.6270.594a=0.40.6440.6480.609内容的相关性。不同形式的资源刻画其内容的方式也不同Bibsonomy0.60.6610.6710.615对于木文的网页资源,内容通过共文木来刻画。因此,对于网a=00.7040.7110.693页资源,计算T中标签与资源内容的相关性可以使用式(15)ry=1.00.7130.704来计算0.6250.5880.5910.653uMo(r)=∑p()s(u,l)0.8120.778其中:p()是词v在资源r的内容中的权重,可以采用绎典信.837.824O.8860息检索的 TFIDF算法计算21;而s(o,)则是词w和聚合标签集T中标签t之间的相关性,采用Cge距离公式来表8为控制因子β对推荐性能的影响。从表8可以看出计算控制囚子β对推荐准确性的影响并不明显。分析共原因在于用户的动机倾向性和资源的动机倾向在一段时期内具有一定4实验与分析的稳定性。所以,提升控制因子β,准确率只是略有增加。表8控制因子对推荐性能的影响4.1数据集数据集控制因子BP@5本文在两个数据集上进行了实验, Bibsonurnv数据集是来0.679自于2008年 ECML/PKDD Discovery Challenge竞赛,该数据集0.40.7150.680.636conomy0.7260.682被认为具有描述倾向:第二个数据集是从 Delicious抓取而来B=0.80.7190.7040.67该数据集被认为具有分类倾向。0.7344.2实验设置0.6450.6230.6186=0.40.6560.630.625首先获取用户的动机倾向性,将每个数据集分为两部分,6=0.60.6790.633其屮一部分用于获取用户的动机倾向性.另一部分用于评价推6-0.80.6960.6630.652荐的质量,并采用文献[23]中基于CRM模型的推荐算法的推0.6910.683荐结果来考察基于OMDM模型的推荐算法;其次还要考察α、β对推荐准确性的影响。5结束语4.3评价方法本文从用户标注动机不能绝对二分出发,提出用户在标注对于推荐系统来说,最客观的评价方法是在线实时统计用某个具体资源肘实际上是存在不同的动机倾向,通过建立五种第1期靳延安:一种基于动机倾向的标签推荐方法77度量指标,提岀了基于动机倾向性的标签推荐模型(OMDM)并设计了基于该模型的算法。在两个不同的数据集上的实验[Novo. NAAMAN M, CHEN Ye. Motivational, Structural and tenure结果表明,基于动机倾冋性的社会标笭推荐模型能获得更准确factors that impact online community photo sharing Cl//Proc of the的备选标签。3rd International AAAI Conference on Weblogs and Social Media本文在标签推荐研究上提供了一个新的研究视角,但研究2009:138-145本身还存在很多局限性。本文仅从五个观察指标对倾向性进1215NHAR. A cognitive analysis of tagging [EB/C.201.02.241行了度量,是否还存在其他不同质的度量指标,或者说从心理http://rashmisinha.com/2005/09/27/a-cognitive-analysis-of-tagging学、认知科学的理论角度有没有其他的指标来测量倾向性还有[13] MARLOW C, NAAMAN M, BOYD D,mal.m6,wg" g paper待究。另外,本文提出的模型和算法并没有考虑所推荐的标taxonomy, Flickr, academic article, to read LC]//Proc of the 17th签的新颖性、召回率,这也是笔者准备进行扩展的研究内容。Conference on Ilypertext and Ilypermedia. New York: ACM Piess2006:31-40参考文献[14 XU Zhi-chen, FU Yun, MAO Jian-chang, et al. Towards the semantic[1 SIGURBJOR NSSON B, Van ZWOL R. Flickr tag recommendationWeb: collaborative tag suggestions C//Proc of Collaborative Webbased on collective knowledge[C//Proe of the 17th InternationalTagging Workshop at the Www. New York Acm Press, 2006Conference on Www. New York Ac.m prEss 2008:327-3[2 HOTHO A, JASCHKE R, SCHMITZ C, ct al. Information retrieval15] SEN S, LAM S K, RASHID A M, et al. Tagging, communities, vocabufolksonomies search and ranking C]//Proc of the 3rd European Con-lary, evolution[ C]//Proc of the 20th ANNIVERSARY Conference onference on the Semantic Web. Berlin: Springer, 2006: 411-426Computer Supported Cooperative Work. Berlin: Springer, 2006: 181[3 SYMEONIDIS P, NANOPOULOS A, MANOLOPOLLOS Y A unified190framework for providing recommendations in social tagging systems L 16 STROIIMAIER M, KORNER C, KERN I. Why do users lag? detecbased on ternary semantic analysis[J]. IEEE Trans on Knowledgeting users'motivation for tagging in social tagging systems[ C]//Procand Data Engineering, 2010, 22(2): 179-192of ICWsM.2010:339-342[4 HARVEY M, BAILLIE M, RUTHVEN I, et al. Tripartite hidden topic[17]JIA\G JJ, CONRATH D W Semantic similarity bascd on corpus stamodels for personalised lay suggest ion[C/Prx of the 32 nd europetistics and lexical taxonomy [C]// Proc of International Conference onan Conference on IR Research. Berlin Springer: 2010: 432-443[5Motivation[Eb/oL].[2012-02-20]http://en.wikipediaorg/wiki/Research Computational Linguistics. 1997: 19-33Motiva-tion JHJcite note-O[18 FU WT, KANNAMPALLIL T G, KANG Ruo-gu, et aL. Semantic Imi[6 TOM C. Iwo cultures of fauxonomies collide[EB/OL1.[2012-02-tation in social tagging[ J]. ACM Trans on Computer-Human In22].hllp://www.plasticbay.ory/archives/2005/06/iwn_eultteraction,2010,17(3):1-3of fauxonomies collide[19]范克新.社会学定量方法[M].南京:南京大学出版社,2004:346L7 IIAMMOND T, IIANNAY T, LUND B, et al. Social bookmarking tools(I): a general review [J]. D-Lib Magazine, 2005: 11(4)[20 LANDIS J R, KOCH GG. The measurement of observer agreement for[8 HECKNER M, HEILEMANN M, WOLFF C Personal information macategorical data [J]. Biometrics, 1977, 33(1): 159-174nagement ys. resource sharing, tow ards a model of information behav21 SALTON C, MeCilL M J. Introduction to modern information retrievaliour in social tagging systems[ C]//Proc of International AAAl Con「M1.「S.1.]: MeCraw-Hill,1983ference on Webloys and cocial media. 2009. 42-49[22] CILIBRASI R, VITANYI P M B. The Google similarity distanee [J][9 WASH R, RADER E, Public bookmarks and private benefits: an analysis of incentives in social computing [J]. Journal of the AmericanIEEE Trans on Knowledge and Data Engineering 2007, 19(3):Society for Information Science and Technology, 2007, 44(1)370-3831-1323]靳廷安,李玉华,刘行军.不同粒度标签推荐算法的比较研究[10J AMES M, NAAMAN M. Why we tag: motivations for annotation in moLJ.计算机应月研究,2012,29(2):504-509bile and online media C〃/' oc of SIGCHI Conference on Human L24」窦玉萌,赵丹群.协作标注系统研究综述L』」.现代图书情报技Factors on Computing Systems. New York: ACM Press: 2007: 971末,200,3(2):9-1(上接第59页)阳:东北大学,2008「9] ZHoU Kang, CAO Zun -hai, XU Jin. An algorithm of DNA computin「13许逹,周康,章磊,等.0-1规划问題的闭环DNA算法「J.糸统工on 0-I planning problem J. Advances in Systems Science and程与电子技术,2009,31(4):947-951Applications,2005,5(4):587-593[14 BRAICH R S, CHELYAPOV N, JHONSON C, et aL. Solution of a 20-[10] WANG Shi-ying, YANG Ai-ming DNA solution of integer linear provariable 3-SAT problem on a DNA computer[J]. Science, 2002, 296gramming[ J. Applied Mathematics and Computation, 2005, 170(4):499-502(1):626-632.[15 SANCHES C AA, SOMAN Y A polynomial-time DNA computing so-[11 ZHANG Feng-yue, YIN Zhi-xiang, LIU Bo, et al. DNA computationlution for the hinI-packing problem J. Applied Mathematics andmodel to solve 0-1 programming problem[ J]. Biosystems, 2004, 74Computation,2009,215(6):2055-2062(1-3):9-14L16」孙伟,尤加宇,江宏,等.纳米粒子标记DNA探针的制备与尬测应[12]罗海波.基于0-1规划的DNA计算模型的设计与实现[D].沈用[].中国卫生检验杂忘,205,15(8):1008-1010