基于关联规则的标签推荐

陈双双，王晓军

(南京邮电大学 计算机学院，江苏 南京 210003)

0 引 言

标签系统在实际生活中应用广泛，用户通过标签可以标注或者搜索自己感兴趣的资源，反映该用户的偏好，表达对事物的看法，因此标签是连接用户和事物的纽带。目前常见的标签推荐方法大都基于FolkRank算法[1]，这种方法主要是基于用户、标签、资源三者之间的关系，并且以这种关系为基础构建一个无向图进行标签推荐，但是现有的方法没有考虑到标签与标签之间的关系，并且也不能有效地缓解数据稀疏问题。针对这些问题，引入了标签与标签的关系，并且利用标签之间的关系进行推荐。

1 相关研究

Kim等[2]强调标签数据可以描述用户潜在的兴趣和特征，并认为结合不同的算法(协同过滤、随机游走模型等等)可以得到显著的优势，提高个性化推荐的质量。Mahboob等[3]在推荐过程中应用热扩散算法，在提取数据，如用户、标签、资源以及它们之间的关系之后，从系统日志文件创建基于图的模式；根据用户的活动路径并观察所创建的模式的热传导，将预期进一步的目标推荐给该用户。Mao等[4]通过记录各个用户使用共同标签的情况，建立一个带有权重节点的网络，然后在标签-资源两偶图上执行一个扩散过程，将标签的权值转换成推荐项的分数，进行个性化推荐。Ma等[5]为了提高推荐的精确度，改进了基于用户的协同过滤方法，提出融合用户标签与用户关系网的方法。Li等[6]针对在线用户构建了一种新的LDA(latent Dirichlet allocation)模型，以学习用户的动态兴趣，并且结合LDA模型和增长Biterm主题模型(incremental biterm topic model，IBTM)设计了一种新的自动标签推荐方法。Rawashdeh等[7]为了提高标签推荐的准确度，提出了基于用户-标签-项目关系的邻接矩阵，并结合卡茨模型(Katz model)构建出一个关于用户、标签、项目的卡茨矩阵。Mashal等[8]利用近邻法(K-nearest neighbors，KNN)进行标签推荐，KNN方法从文档集合中选择出与新文档最相关的K个文档，将这K个文档标签推荐给新文档，相似度越大的文档，其标签推荐的位置越靠前。Belem等[9]提出了一种有监督的主题模型，是针对主题模型LDA的一种改进，它增加了一个连续变量代表标签，并利用标签训练出最优的参数。Si等[10]也是在LDA模型的基础上，提出了主题模型Tag-LDA，此方法基于文档内容和标签联合建模。

以上研究虽然在一定程度上提高了精确度，却忽略了标签与标签之间的关系，并且没能考虑到标签数据稀疏问题。在实际应用中，用户的标签数据往往会一直处于稀疏的状态，系统无法准确捕捉其兴趣偏好，从而影响了推荐的质量。针对标签数据稀疏问题，提出一种基于重叠的时间窗口模型(based on overlapping time window model，OTWM)标签数据采集方法；此方法按照时间窗口顺序去采集标签数据，每两个相邻的时间窗口有重叠的时间区间，这使得重叠时间区间内的标签重复利用，缓解了数据稀疏问题。为了提高标签推荐的精确度，提出了一种基于关联规则的标签推荐方法(based on association rules tag recommendation，ATRecom)。首先，构建一种基于重叠的时间窗口模型用来采集用户的标签数据；然后，对这些标签数据进行挖掘分析，找到标签与标签之间的关系；最后，利用挖掘出来的关联规则为用户进行标签推荐。

2 标签的关联规则挖掘

2.1 关联规则概念

关联规则可反映一个事务与其他事务之间的关联性[11]。若两个或者多个事务之间存在关联关系，那么就能通过已经发生的事务预测与其关联的事务，例如广为人知的啤酒与尿布案例。

关联规则定义为形如X→Y的蕴涵式，描述了频繁共现的事务X，Y同时出现的规律和模式，表示规则前件事务X和后件事务Y中的项目频繁地同时出现。例如{tag1,tag2}→{tag3}的蕴涵式，描述了标签集{tag1,tag2}出现时，标签集{tag3}也很有可能出现。

关联规则挖掘过程主要包含3个阶段[12]：

第一阶段是采集数据事务库。

第二阶段从数据事务库发现频繁项集集合。

第三阶段利用挖掘获得的频繁项集集合，产生关联规则(association rules)。

2.2 相关定义

定义1：时间窗口TW。

假设S={tag1, tag2, …, tagn}是一个在时间区域[TS,TE]内出现的标签序列；Sw={tagw+1, tagw+2,… ,tagw+m}是一个在时间区域[ts,te]内的标签序列，即Sw⊆S，其中ts>TS，te

定义2：滑动步长ST。

假设在两个相邻时间窗TWi= [ti,tj]和TWi+1= [ti+1,tj+1]中，ti

定义3：标签事务和标签事务库。

L(uid,TW) = {tag1,tag2,…, tagh}是用户uid在时间窗口TW内使用过的标签序列，它定义为一条标签事务(tag transaction)。多条标签事务组成的集合就是标签事务库T。

定义4：频繁共现标签集。

设P为一个由多个标签组成的集合，P={tag1，tag2,…，tagk}，P中所有标签在标签事务集合T中同时出现的次数为sup(P)，称为P的支持度。给定一个最支持度minSup，当sup(P)> minSup时，称P为频繁共现标签集，且频繁共现标签集有一个特征，如果P是频繁共现的，那么P的子集也是频繁共现的。

2.3 基于OTWM的数据采集

图1是基于关联规则的标签推荐(ATRecom)过程。

图1 基于关联规则的标签推荐过程

系统在采集用户的标签数据时，首先在第一个时间窗口TW1内采集每个用户所使的标签序列L(uid,TW1)，即用户标识为uid的标签事务，并且将这条标签事务添加到标签事务库T中；当采集完该窗口内所有用户的标签数据后，时间窗口向前滑动ST步长，到达第二时间窗口TW2，同样采集第二时间窗口TW2内所有用户的标签数据，针对每个用户都会生成一条关于该用户的标签事务，添加到标签数据库T中。依次类推，OTWM模型会把所有时间窗口内的用户标签数据采集完成，得到标签事务库T，标签数据采集完成。其过程如下：

步骤1：定义时间窗口TW的大小t，滑动步长ST。

步骤2：采集当前时间窗口TWi(代表第i个时间窗口)内的每个用户对应的标签事务，直到所有用户在该窗口内的标签数据采集完毕，得到该窗口内所有用户的标签事务，加入标签事务库T中。

步骤3：判断当前窗口TWi是否为最后一个时间窗口。

步骤4：如果当前窗口不是最后一个时间窗口，滑动时间窗口ST步长，到达下一个时间窗口TWi+1，重复步骤2，采集此窗口内每个用户的标签数据，生成关于该用户的标签事务，将其加入标签事务库T中；如果当前窗口是最后一个时间窗口，那么用户标签数据采集完毕。得到最终的标签事务库T。

2.4 标签关联规则挖掘

频繁项集合挖掘的方法有许多，但是实际应用中常见的有两种：(1)Apriori及其改进算法，其基本思想是[13]由k项频繁项集产生k+1项频繁项集，直到满足条件的频繁项集发现为止。Apriori算法通过不断地构造候选集、筛选候选集挖掘出频繁项集，需要多次扫描原始数据，当原始数据较大时，磁盘I/O次数太多，效率比较低下。(2)FP-Growth算法处理数据的效率比较高，其基本思想是将原始数据压缩到一个FP-Tree，在该树上进行频繁项集的挖掘，只需要扫描两边数据库[14]。

ATRecom采用FP-Growth算法。利用FP-Growth算法对标签事务库T[15]进行频繁项[16]挖掘，得到频繁共现的标签集集合，记F={P1,P2,…,Pm}，其中Pi是频繁共现的标签组成的集合，即频繁共现标签集。

对上述得到的频繁共现的标签集集合F进行挖掘，找出标签之间的关联规则库R。其过程主要分为以下几步：

步骤1：读取频繁共现标签集集合F，其中F={F1,F2,…,Fi,…,Fn}。

步骤2：对频繁共现标签集集合F中每个频繁共现标签集Fi，产生其所有非空子集，并存放在集合Sub中，其中Sub={sub1,sub2,sub3…}。

步骤3：对于非空子集集合Sub中的每个元素Subi都计算其在F中的支持度；如果为最小支持度minSup，则认为关联规则“subi→(Fi-subi)”是可靠的，并且保存到关联规则库R中。

2.5 标签推荐

针对要进行推荐的目标用户uid收集其标签事务，得到关于该用户的标签事务库Tu，然后利用上一小节中挖掘获得的标签之间的关联规则库R寻找用户uid潜在感兴趣的标签列表。其过程主要分为以下几步：

(1)收集待推荐用户uid使用过的所有标签，得到关于该用户标签集合tuid= {tag(uid,1)， tag(uid,2),…， tag(uid,k)}；

(2)依次读取上述标签关联规则库R中形如X→Y的关联规则，并且判断该规则中的先导标签集X是否存在于关于该用户的标签集合tuid中；

(3)当判断为存在时，即X⊆tuid，并且该条规则X→Y中先导标签集X关联的后继标签集Y⊄tuid，将标签集Y推荐给对应用户。

3 实验与结果分析

3.1 数据集与评估标准

实验选取了在标签推荐系统中常用的两个数据集，分别是Last.fm[17]和CiteULike[18]，它们的数据特征如表1所示。Last.fm是一家著名的音乐网站，它通过分析用户的听歌行为来预测用户对音乐的兴趣，数据集包含用户2 100个，标签12 648个，项目(歌手)18 745个，用户给项目贴标签的信息186 479条。CiteULike是一个著名的论文书签网站，它允许研究人员提交或者收藏他们感兴趣的论文，给论文打标签，从而帮助用户更好地发现和自己研究领域相关的优秀论文，数据集包含用户2 614个，项目4 096个，标签2 310个，用户给资源打标签信息161 395条。

表1 数据特征

评估标签推荐系统的性能度量主要采用精确度(precision)和召回率(recall)[19]。

3.2 实验结果

实验采用了基于关联规则的标签推荐和基于卡茨(Katz)模型的标签推荐[7]两种方法。其中，基于Katz模型的标签推荐方法主要根据用户-标签-项目的关系构建出一个关于用户、项目、标签的三元邻接矩阵，通过最佳匹配文本相似度公式(Best Match25，BM25)计算出这个邻接矩阵上的各个权值，然后结合Katz模型，对该矩阵进行矩阵处理，得到Katz矩阵。最后根据Katz矩阵计算用户、项目、标签的Katz评分，从而进行推荐。ATRecom是利用标签与标签之间的关系进行推荐，而KatzBM25则是根据用户、标签、项目之间的关系。

利用ATRecom方法的标签推荐涉及到时间窗口TW这个不确定参数。为了找出最为合适的时间窗口值TW，验证了TW取值在20到90之间的均匀分布的实验结果。图2显示了时间窗口TW的变化对标签推荐结果精确度的影响，当时间窗口TW的取值为50时，推荐的精确度是最高的。

图2 时间窗口对精确度的影响

数据稀疏度是影响推荐精确度重要因素。数据集Last.fm和CiteULike的数据稀疏度计算如下：

其中，sparsity是数据的稀疏度；users是用户个数；items是项目个数；tagassinments是用户给项目打标签的记录条数。

为了观察数据稀疏度对ATRecom、KatzBM25方法推荐精确度的影响，验证了这两种方法在Last.fm、CiteULike数据集，3种不同稀疏度下的实验结果。图3、表2显示了各数据集在时间窗口TW为50时，在不同的稀疏度下获得的实验结果。

(a)Last.fm

数据集稀疏度ATRecomSwallowMATKatzBM25Last.fm0.0030.450.410.370.340.003 70.520.480.430.400.004 70.590.570.540.50CiteULike0.013 10.510.480.450.430.014 10.580.550.530.510.015 10.660.630.610.60

结果表明，ATRecom获得的精确度比KatzBM25高，并且当数据的稀疏程度发生变化时，ATRecom的精确度变化幅度低于KatzBM25。这表明ATRecom推荐方法在一定程度上缓解了数据稀疏造成的推荐不准确的问题，其主要原因是在数据采集过程中，ATRecom采用了有重叠的时间窗口，这使稀疏的标签数据可以二次利用。

(a)Last.fm

(b)CiteULike

图4显示了ATRecom和KatzBM25在Last.fm和CiteULike两种数据集推荐的准确度和召回率的关系，在此，Last.fm数据集的稀疏度为0.004 7，CiteULike数据集的稀疏度为0.015 1，ATRecom中的时间窗口TW为50。可知，推荐的精确度越高召回率就会越低。但是ATRecom推荐结果精确度、召回率都明显高于KatzBM25。

4 结束语

基于关联规则的标签推荐方法不同于传统的标签推荐，该方法中采用基于重叠的时间窗口模型的标签数据采集方法能够使重叠时间区间内的标签数据多次合理利用，缓解了数据稀疏问题；同时避免了当标签信息的时间跨度过大时，本来无关的标签之间的相互影响造成的规则挖掘的不准确性。此外，这种标签推荐方法也考虑到了标签-标签的关系，而不在拘泥于传统的用户-标签，资源-标签这种关系。