基于标签的推荐系统关联算法研究

申 丹



基于标签的推荐系统关联算法研究

申 丹1、2

1.陕西省土地工程建设集团有限责任公司，陕西 西安 710075 2.陕西地建土地工程技术研究院有限责任公司，陕西 西安 710075

推荐系统存在的目的就是帮助用户快速发现所需信息，并结合用户自身特点和兴趣爱好，为用户寻找高质量高价值的资源，从而减少用户接触重复或无关信息带来的不利影响，提升用户体验度。对基于标签的推荐系统进行了深入了解，在传统算法的基础上引入关联规则挖掘，并通过使用K-means聚类方法对标签集合分类来降低矩阵的数据稀疏度。通过发现海量用户行为之间的隐含规律并作为推荐依据，提高推荐系统的准确度和对结果集中项目类型的覆盖率。

标签；个性化推荐；K-means聚类；关联规则；协同过滤

引言

推荐系统存在的目的就是帮助用户快速发现所需信息，并结合用户自身特点和兴趣爱好，为用户寻找高质量高价值的资源，从而减少用户接触重复或无关信息带来的不利影响，提升用户体验度。大众标注法的引入带来了推荐系统中对资源评价的另一种方式，标签简便易用且利于传播，它不仅能够体现出资源的差异性也反映出了标注者的行为特征与个人偏好。

1 推荐系统及相关技术

1.1 推荐系统基本理论

一直以来，推荐系统想要达到的理想状态是为用户创造一种具备人工智能因素的决策体系，目标在于对广义范围使用者提供高效且便利的推荐[1]。对数据环境的良好适应性和便捷访问的特点大大增强了推荐的效果，通用情况会采用“三要素分割法”，即把推荐系统中的节点划分为用户、备选资源、使用的推荐逻辑方法（见图1）。

1.2 系统建模技术

1.2.1 用户建模技术

模型反映用户的类别、喜好、特点，从而提供个性化服务[2]。整个建模的处理过程分为两个步骤：（1）收集用户信息，分析用户行为；（2）系统建立模型，并根据用户反应做出预期处理。在这其中要解决的问题有：记录用户数据、提取用户特征值、建立有效模型。

图1 推荐系统通用模型

1.2.2 物品建模技术

物品特征的建模方法可以归类为基于内容和基于分类两种。前者从物品本身的特征着手，最常使用的是加权关键词矢量。这是统计学中用来分析文档的方法，结果是得到文档的特征向量。

1.3 推荐算法

推荐算法是推荐系统中的核心模块。算法的效用会直接影响推荐的效率和质量[3]。目前较为主流的推荐算法有协同过滤推荐算法、基于内容推荐算法、基于知识推荐算法和混合推荐算法。这些算法连接User和Item的方式可以归为3种（见图2）。

图2 三种推荐系统联系User和Item的方式

2 标签中的关联规则挖掘研究

假设得到k阶频繁项集S={s1，s2...，sk}。在该项集中随意去掉一个元素就得到了k-1个非空子集，且这些子集全部也是频繁项集。选取其中任意两个子集对比后可以知道它们有（k-2）项是相同的，且并集是全集。例如，选择{s1，s2，…sn-2，sn-1}和{s1，s2，…sn-2，sn}。此外，对一个k+1阶频繁项集，其k阶频繁项集的非空子集必然是频繁项集。由此可得，任意k+1阶频繁项集，对应的k阶频繁项集中必定存在至少两个集合的并集与之相等。这样，只要对k阶频繁项集找出只有最后一项不同的集合并使之合并，就可以得到全部k+1阶频繁项集。当然，这时得到的项集不一定全部符合频繁项集的条件，有干扰项，需要进行“剪枝”[4]。重复此步骤，就得到了全部的k+1阶频繁项集。得到的频繁项集包含所有可能的规则，只要使用遍历法就能得到规整出来的关联规则。从1开始，依次选择直到k的元素作为结果，其余看作前件，在一定置信度的设立下就过滤掉低频规则。这种做法范围广，不会出现漏缺，但是时间复杂度高。若存在频繁项目g，那么通用规则表达式为（g-β）—>β。那么这条规则的置信度=g.count/(g-β).count。

根据置信度计算公式可以确定，频繁项目集g.count是定值。如果该规则是强关联规则，那么（g-βs）—>gs也是强关联规则[5]。其中βs是β的子集，因为(g-β).count 必然大于(g-βs).count。对一个给定的频繁项目集g，如果一条强关联规则的后件为β，那么所有由β的非空子集组成后件的关联规则也是强关联规则。综上所述，逻辑处理流程就可以描述为首先找到所有后件项数为n（n>=1）的强关联规则，然后再生成后件项数为n+1的强关联规则，依次类推，直至生成所有的强关联规则。Apriori的核心算法伪代码如下：

{L1= {large 1-itemsets};

Ck=apriori-gen(Lk-1);//新的候选集

for all transactions t∈D do begin

Ct=subset(Ck,t); //事务t中包含的候选集

for all candidates cÎ Ctdo

c.count++;

end

Lk={c∈Ck|c.count≥minsup}

end

Answer=∪kLk;}

最先得到的是频繁项集L1，之后产生频繁项集L2，当且仅当出现使Lr为空的值出现时算法终止[6]。这是一个循环算法，当循环进行到第k次时，得到k-（后件项数为k）项集的集合Ck，其中每一个项集等于两个有且仅有一个项不同的Lk-1频繁集进行（k-2）-连接得到的。备选频率集合出自于Ck中的项集，最后选中的频集Lk是Ck的某子集，Lk的元素是将Ck中的每个元素在交易事务集和中加以验证后才确定是否并入。

综上所述，标签关联规则挖掘的实现步骤如下：

步骤1：挖掘目标用户行为日志，清理标签，获得高质量的用户标签初始集合TU。

步骤2：对每一个ti∈Tui，在其标签集上使用K-means聚类算法，将Tui划分为由k个核心标签为代表的用户个人标签集合Tui*。

步骤3：在Tui*上使用Apriori算法，获得频繁项集，由频繁项集推导强关联规则。

3 实验评测

3.1 方案设计

本小结将通过实验设计来检测上文所提出的标签关联规则挖掘方法以及规则的推荐结果。通过处理数据集形成用户的标签集合，用Tui=｛t1，t2，t3，…tn｝表示用户ui所使用过的标签集合[7]。通过寻找不同用户标签集合的频繁项集，找到“凡是偏好标签A和B的用户，很有可能也会喜欢标签C”成立的规则模型。表1为五个用户一次事务中的标签集合：

表1 用户-标签列表

将一个用户所对于Tui的有效标签子集，规则选项卡U，Tx→Ty用于提取称之为UTmodel规则模型。其中U代表用户集，Tx表示子集中的某标签，Ty代表同一个用户标签子集中所包含的其他标签[8]。对于每一条UT模型可以按照如下公式来定义置信度conf和支持度supp：

由此会产生大量规则列表集合，对此设立如下的规则选择机制，规则按照设立顺序依次满足：

条件1：规则满足最低的支持度和可信度阈值；

条件2：选择最大置信度的规则；

条件3：置信度相同时，选择具有最大支持度的规则；

条件4：当置信度与支持度相同时，选择首次出现的规则。

按照上述步骤来处理表1中所展示的“用户-标签”集，可以得到例如表2中的关联规则：

表2 关联规则

3.2 测试结果及分析

实验中使用的数据集采用数据堂提供的Delicious数据集。该数据集经过简单的预处理，包含用户对标签的使用情况记录，数据格式为 [USER_ID, URL_ID, Tags]。部分数据集如表3所示：

表3 预处理数据集

表3所示是原始数据，经过标签清洗后，可以得到形式规整并且质量较高的数据集合，包括对大小写的归并，对缺省值的过滤和对错误输入的剔除。USER_ID为104的用户的原始记录有170条数据，经过标签清洗后有153条数据，之后对该用户使用K-means聚类后如图3所示：

图3 用户104标签聚类

进行关联规则挖掘，获得关联规则集合。表4展示了不同规则置信度和支持度的值，对于置信度小于60%的规则予以过滤。例如规则“104，blog→music”，只有55.71%的人对blog感兴趣的同时对music感兴趣，因此该条规则不会作为推荐依据。而对于规则“225，games→Apple”，其支持度高达87.04%，即喜欢games的人绝大多数都对Apple产品有较高的关注度，那么当一个用户检索跟games有关的标签时，Apple就会作为推荐标签之一推送给用户[9]。

表4 不同规则置信度和支持度的值

由此形成的推荐列表，通过准确率和召回率进行评测后结果如表5所示，结果表明该算法有较高的准确率，并且推荐列表选择为Top-5时的效果优于Top-3[10]。

表5 通过准确率和召回率进行评测后的推荐列表

4 结束语

本文针对标签所具有的特性以及对用户兴趣的建模，主要从以下两个方面进行了深入研究：从数据层面解析用户标记过程，提取并处理用户的历史标注行为。将用户标签通过脏数据清理，聚类形成极具个性化的用户标签社区。并将关联规则引入标签系统中，利用数据挖掘技术让隐含于标签集之间的联系显现出来。尽可能多的检测频繁项集，在大量数据中定义出可推理的关联规则。将这种规则运用到推荐流程中，帮助优化用户体验并提升算法效能。

[1]刘建国，周涛，汪秉宏.个性化系统研究进展[J].自然学进展，2009，19（1）：1-15.

[2]Ricci F，Rokach L，Shapira B. Introduction to Recommender Systems Handbook[J].Recommender Systems Handbook，2010：1-35.

[3]Chen H，Joshi A，Finin T. Dynamic Service Discovery for Mobile Computing: Intelligent Agents Meet Jini in the Aether[J].Cluster Computing，2001，4（4）：343-354.

[4]GANZHA V G，MAYR E W，VOROZHTSOV E V. Computer algebra in scientific computing: CASC 2000: proceedings of the Third Workshop on Computer Algebra in Scientific Computing, Samarkand, October 5-9, 2000[C]. Berlin: Springer, c2000.

[5]Schmidt B. Service to recommend opening an information object based on task similarity: US, doi:US20140019975 A1[P]. 2015.

[6]朱泽宇. 社会标签系统挖掘研究[J]. 江苏科技信息，2015（23）：26-27.

[7]Adomavicius A，Tuzhilin Gediminas. Toward the Next Generation of Recommender Systems: A Survey of the State-of-the-Art and Possible Extensions[J]. IEEE Transactions on Knowledge & Data Engineering，2005，17（6）：734-749.

[8]Younghoon Kim，KyuseokShim. TWILITE：A recommendation system for Twitter using a probabilistic model based on latent Dirichlet allocation[J]. Information Systems，2013.

[9]王国霞，刘贺平. 个性化推荐系统综述[J]. 计算机工程与应用，2012（7）：66-76.

[10]A Zapata，V H Menéndez，M.E. Prieto，C Romero. A framework for recommendation in learning object repositories: An example of application in civil engineering[J]. Advances in Engineering Software，2013，56.

Research on Association Algorithm of Label Based Recommendation System

Shen Dan1,2

1. Shaanxi Provincial Land Engineering Construction Group Co., Ltd., Shaanxi Xi’an 710075 2. Institute of Land Engineering and Technology, Shaanxi Provincial Land Engineering Construction Group Co., Ltd., Shaanxi Xi’an 710075

The recommendation system’s purpose is to help users quickly find the required information, and combined with the user’s own characteristics and interests, find the resources of high quality and high value for the users, thereby reducing user contact of redundant or irrelevant information brings adverse effect, enhance the user experience. The paper makes a deep understanding of the recommendation system based on the tags, the association rules is introduced based on the traditional algorithm in mining, and through the collection of classification label using K-means clustering method to reduce the data sparseness matrix. Through the discovery of the hidden rules between the massive users’ behavior as the basis for recommendation, improve the accuracy of the recommendation system and the coverage of the project type.

Tag; K-means clustering; personalized recommendation; association rules; collaborative filtering

TP391.3

A

1009-6434（2017）9-0056-04

申丹（1989—），女，汉族，陕西汉中人，当前职务为科研辅助，当前职称为初级工程师，硕士研究生学历，研究方向为情报学。