一种融合社会标签相似度基于K近邻的协同过滤推荐系统

摘要

本发明公开了一种融合社会标签相似度基于K近邻的协同过滤推荐系统，系统包括对社会标签语义相似度的计算方法分析模块、两种社会标签相似度与评分相似度的融合模块和基于K近邻构建协同过滤推荐模块三个部分，分析模块根据项目之间的不同数据源来源，提出了除评分相似度以外的社会标签语义相似度；对社会标签语义相似度的计算，主要包括标签对之间的相似度计算和标签集合之前的相似度计算；融合模块中两种社会标签相似度与评分相似度的融合方式包括按比例融合和以权重的方式融合两种；最后将融合后的相似度度量基于K近邻来构建协同过滤推荐系统。本发明将社会标签数据信息和用户－项目评分数据信息进行融合，从而达到提高推荐精度的目的。

说明书

技术领域

本发明属于数据挖掘的技术领域，具体涉及一种融合了社会标签相似度基于K近邻的协同过滤推荐系统，适用于推荐结果的优化。 

背景技术

个性化推荐系统根据用户个人不同的兴趣爱好进行推荐，通常这种系统使用协同过滤技术来实现。在协同过滤推荐系统中，用户对不同项目的喜好以一个用户-项目评分矩阵来表示，越高的评分表明了用户对项目更强的兴趣。协同过滤技术使用已有的数据，处理和完成这个矩阵中缺失数据的估计问题。构造协同过滤推荐系统时最常用的两类模型是近邻关系模型和隐向量模型。近邻关系模型构建用户与用户或者项目与项目之间的邻居关系，使用用户或项目邻居之间已有的评分数据来做出评分预测。近邻关系模型使用和集成起来更加简单明了，其具备更高的灵活性，推荐结果也更加直观和易于理解。本发明一种融合社会标签相似度基于K近邻的协同过滤推荐系统采用近邻关系模型。 

本发明通过融合社会标签网络中的语义信息来优化基于K近邻模型的协同过滤算法。现有的系统只考虑了社会标签网络信息或者简单直接地使用了社会标签网络信息和评分数据。本系统旨在通过多数据源融合来优化传统的K近邻模型。系统使用社会标签网络的语义信息作为项目的相似度支持度，然后采取两种与评分数据融合的策略，按比例融合和按权重融合。通过这两种策略，K近邻模型能够提供更高的推荐精度，同时也可以通过降低K值从而降低计算的复杂度。 

发明内容

本发明要解决的技术问题为：本发明通过提出一种新的度量标准，社会标签相似度作为项目的相似度支持度，帮助优化K近邻集合的质量。在这种新的度量标准之上，系统采取两种融合策略来优化K近邻模型的推荐精度和K值来降低计算复杂度，从而构建出更好的基于K近邻的协同过滤推荐系统 

本发明解决上述技术问题采用的技术方案为：一种融合社会标签相似度基于K近邻的协同过滤推荐系统，其特征在于：具体包括： 

（一）社会标签语义相似度的计算方法分析模块 

该分析模块首先在给定的包含|I|个项目的社会标签数据上对标签信息进行分析，过滤，去重预处理，其中，I是项目集合，|I|代表项目集合I的个数；然后计算标签与标签之间的语义相似度，最后定义了标签集合之间的语义相似度的计算方法，作为两个项目之间的社会标签相似度； 

标签与标签的相似度使用WordNet中的Wu and Palmers算法定义： 

$>{\mathrm{Sim}}_{\mathrm{WP}}(c_1,c_2)=\frac{2\times \mathrm{depth}\left(\mathrm{lso}(c_1,c_2)\right)}{\mathrm{len}(c_1,c_2)+2\times \mathrm{depth}\left(\mathrm{lso}(c_1,c_2)\right)}---\left(1\right)$>

其中lso表示两个词语的公共父节点，depth表示一个词语在语义树中的深度，len是两个词语之间的路径长度，Wu and Palmers算法的含义是，两个词语的语义相似度是由两个词语之间的路径长度和其公共父节点的深度所共同决定的，因为一个词语可能有多个含义，处于多个语义网，将使用两个标签不同含义之间，语义相似度最大值作为它们的相似度； 

社会标签集合之间的语义相似度计算，对于给定的两个社会标签集合A，B，tag_i和tag_j表示集合中的两个标签，令sim_i，j表示标签之间的相似度；使用一个矩阵来存储A和B中的标签两两之间的相似度，这样就将社会标签集合之间的语义相似度的计算问题转化为了寻找最大二分匹配的问题，问题的目标就是找到标签之间最大可能匹配的数目； 

$>{\mathrm{FSim}}_{A,B}=\frac{N_{A-\mathrm{matching}-\mathrm{pairs}}+N_{B-\mathrm{matching}-\mathrm{pairs}}}{\left|A\right|+\left|B\right|}---\left(2\right)$>

式(2)中，两个标签集合AB的语义相似度用FSim_AB来表示，定义标签相似度大于设置的阈值时，为两个标签之间匹配，N_{A-matching-pairs}和N_{B-matching-pairs}分别表示从两个集合的优先考虑角度来寻找的匹配标签数目； 

（二）两种社会标签相似度和评分相似度的融合模块 

该融合模块使用社会标签相似度作为相似度支持的两种融合策略：一种是按比例融合的方法，其按比例融合的方法将两种相似度按比例融合在一起，社会标签相似度和评分相似度分别贡献自己的相似度的比例值；另外一种是以权重融合的方法，其以权重融合的方法考虑到评分相似度和社会标签相似度的特殊性，将使用社会标签相似度来作为权重修正评分相似度：越高的社会标签相似度表示其评分相似度的置信度越高；具体的： 

（1）按比例融合的方法 

这种方法将两种相似度按比例融合在一起，社会标签相似度和评分相似度分别贡献自己的相似度的比例值；给定两个项目i和j，RS表示它们的评分相似度，FS是社会标签相似度， 那么i和j最终的相似度计算方法是： 

Sim_i,j＝λ·FS_i,j+(1-λ)·RS_i,j    (3) 

其中的λ是比例系数，从0到1之间取值，根据实际系统的需要和运行性能选取合适的值； 

（2）以权重融合的方法 

这种策略考虑到评分相似度和社会标签相似度的特殊性，将使用社会标签相似度来作为权重修正评分相似度：越高的社会标签相似度表示其评分相似度的置信度越高； 

$>{\mathrm{Sim}}_{i,j}={\mathrm{RS}}_{i,j}·\frac{{\mathrm{FS}}_{i,j}-\min \left(\mathrm{FS}\right)}{\max \left(\mathrm{FS}\right)-\min \left(\mathrm{FS}\right)}---\left(4\right)$>

其中max（FS）和min（FS）代表训练数据中所有项目的最大最小社会标签相似度的值；通过这种方法将评分相似度转化成一个新值，在K近邻的构建时，最近邻居的选择将会倾向于评分相似度和社会标签相似度都高的项目，而不是仅仅由一种相似度所决定； 

（三）使用融合后的相似度信息基于K近邻构建协同过滤推荐模块 

该推荐模块通过在基于不同数据源的模型上计算项目之间的各种相似度，社会标签相似度项目相似度以支持度的方式集成到K近邻模型中去，来改善模型的性能，通过两种融合社会标签语义相似度和评分相似度的方法，包括以百分比融合和以权重融合，构建出基于K近邻的协同过滤推荐系统可以更好地通过已知数据预测出未知数据的评分信息，具有更高的推荐精度； 

项目之间的相似度采用Pearson相关相似度来计算， 

$>{\mathrm{Sim}}_{i,j}=\frac{\underset{u\in R_i\cap \mathrm{Rj}}{\Sigma }(r_{u,i}-\overline{r_i})·(r_{u,j}-\overline{r_j})}{\sqrt{\underset{u\in R_i\cap R_j}{\Sigma }{(r_{u,i}-\overline{r_i})}^2}·\sqrt{\underset{u\in R_i\cap R_j}{\Sigma }{(r_{u,j}-\overline{r_j})}^2}}---\left(5\right)$>

其中的 是项目i的平均评分，用户用u表示，i，j表示不同的项目，通过计算项目之间的相似度，系统将存储每个项目的K个最大相似度的近邻项目，对于未知的用户-项目评分将通过已知的评分数据和该项目的K近邻项目来估计得到： 

$>{\hat{r}}_{u,i}=\frac{{\Sigma }_{j\in \mathrm{KNN}\left(i\right)\cap R\left(u\right)}{\mathrm{Sim}}_{i,j}·r_{u,j}}{{\Sigma }_{j\in \mathrm{KNN}\left(i\right)\cap R\left(u\right)}{\mathrm{Sim}}_{i,j}}---\left(6\right)$>

KNN(i)表示项目i的K个最大相似度的近邻项目集合，R(u)是用户u的已知评分，Sim_i，j是通过上面公式计算出来的项目i和j之间的相似度和社会标签相似度融合得到，估计未知评分时，系统通过移除用户或者项目的平均评分来修正公式，这样将会大大增加推荐系统的精度，面向项目的K近邻公式加上平均评分修正之后变成： 

$>{\hat{r}}_{u,i}=\overline{r_i}+\frac{{\Sigma }_{j\in \mathrm{KNN}\left(i\right)\cap R\left(u\right)}{\mathrm{Sim}}_{i,j}·(r_{u,j}-{\bar{r}}_j)}{{\Sigma }_{j\in \mathrm{KNN}\left(i\right)\cap R\left(u\right)}{\mathrm{Sim}}_{i,j}}---\left(7\right)$>

通过上面的公式，推荐系统会将预测评分最高的项目推荐给用户。 

其中，在整个推荐系统构建的过程中，社会标签相似度和评分相似度共同决定项目之间的相关关系，在构建K近邻集合的时候使用融合之后的相似度，K值的选择将会影响到推荐系统的性能：选取一个较小的K值会导致较低的推荐精度，而太大的K值将会增加模型的计算复杂度，系统的K值根据用户和项目数量的大小、数据的稀疏程度以及社会标签的相关性来选择。 

本发明的原理在于： 

一种融合社会标签相似度基于K近邻的协同过滤推荐系统，系统包括对社会标签语义相似度的计算方法分析、两种社会标签相似度与评分相似度的融合方式和基于K近邻构建协同过滤推荐系统三个部分。基于K近邻的协同过滤推荐系统主要是利用给定的数据为用户或项目构建最近邻居，从而产生推荐结果。对社会标签语义相似度的计算，主要包括标签对之间的相似度计算和标签集合之前的相似度计算。两种社会标签相似度与评分相似度的融合方式包括按比例融合和以权重的方式融合两种。最后将融合后的相似度度量基于K近邻来构建协同过滤推荐系统，这样就将社会标签数据信息和用户－项目评分数据信息进行融合，从而达到提高推荐精度的目的。 

本发明优点及功效在于： 

（1）、采用语义模型从社会标签数据中抽取项目与项目之间在标签语义上的相似关系； 

（2）、通过按比例的方式和按权重的方式，将社会标签数据信息和用户-项目评分数据信息进行融合分析； 

（3）、能够充分挖掘用户-项目之间的关系，提高了协同过滤推荐系统推荐的精度。 

附图说明

图1是项目之间的数据来源的图示； 

图2是WordNet语义网图示； 

图3是项目之间的评分相似度和社会标签相似度的图示； 

图4是系统结构图示。 

具体实施方式

1.社会标签语义相似度的计算方法分析 

图示如图1所示。系统在计算社会标签的语义相似度之前，将对标签做一些预处理来解 决社会标签相似度难于计算的问题。在社会标签网络中，标签是自由地、自发地由用户指派给项目，它们包含了大量的除了项目内容之外的其他信息。通常来说，社会标签网络有三个特点：第一，用户具有它们各自的社会标签知识基础，比如习惯用语，地名和人名等；第二，包含有相似含义的标签可能有不同的表现形式；第三，对于同一个项目，不同的人可能会根据自己的理解给出成千上万个标签来描述。这三个特点使两个项目之间的社会标签相似度的计算难于评分相似度的计算。 

社会标签的预处理 

系统首先需要通过分析和统计，找出社会标签网络中的常用的词语比如地名，人名或其他特殊用法的短语。由社会标签网络的第一个特点可以发现，特殊用法的短语代表着用户的特别喜好，不能够将短语中的单词拆开来分析。比如人名“Bill Gates”，其中的“bi1l”和“gates”的意思是和原短语完全不相同的。 

对于包含这社会标签网络信息的推荐系统，其数据可以用一个四元组来表示D=<U,I,R,T>。其中U是指用户集合，I是项目集合，R表示评分集合，T是社会标签集合。元组的一个元素d，表示用户u对项目i的评分r，给予了一个标签t。 

本发明定义T_s包含用户所喜欢使用的所有特殊短语。在接下来对训练数据的处理中，如果一个标签属于Ts，将不会被分词，而是直接被作为一个用户喜好特征被添加到待聚类的集合中去。 

同时，预处理过程将过滤D中不常见的用户，不常被评分或标记项目和标签噪声。通过这个过程，训练数据将会有一定程度的缩小和聚集。这样会使训练出来的结果更具有代表性，同时会减少一些计算复杂度。 

下一步系统将进行单词的分词，通过分词来去除一些无意义的词语，停顿词和还原词根。因为标签是自由地、自发地由用户根据其喜好来随意添加的，社会标签网络中将包含很多停顿词和不同的时态。其中停顿词包括像“a”，“the”，无意义的词像“laji”等，这些都会影响之后的语义分析。词形和时态的问题，可以通过还原时态和还原词根来进行统一。 

本发明将一个项目所具有的社会标签信息描述为F=<t₁,t₂,…,t_n>，如果t_i是一个停顿词或无意义的词，那么直接从F中去除，同时需要判断t_i是否要还原时态或词根。最后，将得到的包含有成百上千个社会标签的集合进行聚类。通过以上步骤将在不丢失语义相似度精度的情况下，大大减少后续的计算复杂度。聚类算法通过计算项目所具有的社会标签集合中的标签之间的语义相似度来完成。算法将选取最具有代表性且不相似的一些标签来作为社会标签信息特征代表。 

聚类算法描述如下： 

算法1:聚类社会标签信息 

输入:未处理的社会标签集合 

输出:聚类之后的社会标签集合 

a.对于未处理的社会标签集合中的每一个元素，若是特殊含义的词，直接加入聚类之后的社会标签集合； 

b.若是一般词，计算它与已经聚类后的社会标签集合的语义相似度，如果它与其中的任何一个都不相似，则加入聚类之后的社会标签集合。 

c.当聚类之后的社会标签集合元素数量达到需求值时停止，否则继续。 

标签与标签的语义相似度计算 

系统使用WordNet来计算两个标签之间的语义相似度，这种相似度的计算是通过理解标签所包含的语义来完成的。WordNet是一个英语的词汇数据库。它将英文单词通过同义词语义网组织起来，提供了简短且常用的定义，并且记录了语义网之间的语义关系。图2给出了一个WordNet语义网的例子。 

本发明选择Wu和Palmer的算法来计算标签之间的语义相似度。在他们的算法描述中，两个词语的语义相似度是由“is_a”关系树来定义的，定义如下： 

$>{\mathrm{Sim}}_{\mathrm{WP}}(c_1,c_2)=\frac{2\times \mathrm{depth}\left(\mathrm{lso}(c_1,c_2)\right)}{\mathrm{len}(c_1,c_2)+2\times \mathrm{depth}\left(\mathrm{lso}(c_1,c_2)\right)}---\left(1\right)$>

其中lso表示两个词语的公共父节点，depth表示一个词语在语义树中的深度，len是两个词语之间的路径长度。这个算法的含义是，两个词语的语义相似度是由两个词语之间的路径长度和其公共父节点的深度所共同决定的。因为一个词语可能有多个含义，处于多个语义网。系统将使用两个标签不同含义之间，语义相似度最大值作为它们的相似度。 

社会标签集合之间的语义相似度计算 

对于给定的两个社会标签集合A，B，tag_i和tag_j表示集合中的两个标签，根据上一节的描述令sim_i，j表示标签之间的相似度。系统使用一个矩阵来存储A和B中的标签两两之间的相似度。这样就将社会标签集合之间的语义相似度的计算问题转化为了寻找最大二分匹配的问题，问题的目标就是找到标签之间最大可能匹配的数目。 

$>{\mathrm{FSim}}_{A,B}=\frac{N_{A-\mathrm{matching}-\mathrm{pairs}}+N_{B-\mathrm{matching}-\mathrm{pairs}}}{\left|A\right|+\left|B\right|}---\left(2\right)$>

上式中，两个标签集合AB的语义相似度用FSim_A，B来表示，定义标签相似度大于设置的阈值时，为两个标签之间匹配。N_{A-matching-pairs}和N_{B-matching-pairs}分别表示从两个集合的优先考虑角度来寻找的匹配标签数目。考虑到计算的复杂度，系统使用了一个快速的启发式算法来完成： 

算法2:计算社会标签集合之间的语义相似度 

输入:两个待计算语义相似度的标签集合 

输出:两个标签集合的语义相似度 

a.计算两个集合的两两标签相似度，用矩阵存储 

b.从最大的语义相似度开始寻找匹配的标签对数，如果已经匹配，则标记为已匹配，不再接受其他匹配 

c.分别从两个集合的元素优先选择匹配的角度寻找匹配的标签，得到总的匹配数目 

d.总的标签匹配数目除以两个集合标签的总数目，得到两个标签集合的语义相似度。 

2.两种社会标签相似度和评分相似度的融合方法 

在构建K近邻的过程中，使用社会标签相似度和评分相似度来优化K近邻集合的质量。系统使用社会标签相似度作为相似度支持的两种融合策略：一种是按比例融合的方法，另外一种是以权重融合的方法。 

（1）按比例融合的方法 

这种方法将两种相似度按比例融合在一起，社会标签相似度和评分相似度分别贡献自己的相似度的比例值。给定两个项目i和j，RS表示它们的评分相似度，FS是社会标签相似度，那么i和j最终的相似度计算方法是： 

Sim_i,j＝λ·FS_i,j+(1-λ)·RS_i,j                (3) 

其中的λ是比例系数，从0到1之间取值。根据实际系统的需要和运行性能选取合适的值。 

（2）以权重融合的方法 

这种策略考虑到评分相似度和社会标签相似度的特殊性，将使用社会标签相似度来作为权重修正评分相似度：越高的社会标签相似度表示其评分相似度的置信度越高。 

$>{\mathrm{Sim}}_{i,j}={\mathrm{RS}}_{i,j}·\frac{{\mathrm{FS}}_{i,j}-\min \left(\mathrm{FS}\right)}{\max \left(\mathrm{FS}\right)-\min \left(\mathrm{FS}\right)}---\left(4\right)$>

其中max（FS）和min（FS）代表训练数据中所有项目的最大最小社会标签相似度的值。通过这种方法将评分相似度转化成一个新值，在K近邻的构建时，最近邻居的选择将会倾向于评分相似度和社会标签相似度都高的项目，而不是仅仅由一种相似度所决定。 

3.使用融合后的相似度信息基于K近邻构建协同过滤推荐系统 

面向项目的K近邻模型使用评分数据来构建项目与项目的近邻关系。经典的项目之间的相似度使用向量相似度来计算，常见的有余弦相似度，Pearson相关相似度和修正的余弦相似度集中。本发明采用Pearson相关相似度，可以获得更好的推荐精度和性能。 

$>{\mathrm{Sim}}_{i,j}=\frac{\underset{u\in R_i\cap \mathrm{Rj}}{\Sigma }(r_{u,i}-\overline{r_i})·(r_{u,j}-\overline{r_j})}{\sqrt{\underset{u\in R_i\cap R_j}{\Sigma }{(r_{u,i}-\overline{r_i})}^2}·\sqrt{\underset{u\in R_i\cap R_j}{\Sigma }{(r_{u,j}-\overline{r_j})}^2}}---\left(5\right)$>

其中的是项目i的平均评分，用户用u表示，i，j表示不同的项目。通过计算项目之间的相似度，系统将存储每个项目的K个最大相似度的近邻项目。对于未知的用户-项目评分将通过已知的评分数据和该项目的K近邻项目来估计得到： 

$>{\hat{r}}_{u,i}=\frac{{\Sigma }_{j\in \mathrm{KNN}\left(i\right)\cap R\left(u\right)}{\mathrm{Sim}}_{i,j}·r_{u,j}}{{\Sigma }_{j\in \mathrm{KNN}\left(i\right)\cap R\left(u\right)}{\mathrm{Sim}}_{i,j}}---\left(6\right)$>

KNN(i)表示项目i的K个最大相似度的近邻项目集合，R(u)是用户u的已知评分，如图3所示，Sim_i,j是通过上面公式计算出来的项目i和j之间的评分相似度与步骤二计算的项目之间的社会标签相似度融合而来。估计未知评分时，可以通过移除用户或者项目的平均评分来修正公式，这样将会大大增加推荐系统的精度。所以面向项目的K近邻公式加上平均评分修正之后变成： 

$>{\hat{r}}_{u,i}=\overline{r_i}\frac{{\Sigma }_{j\in \mathrm{KNN}\left(i\right)\cap R\left(u\right)}{\mathrm{Sim}}_{i,j}·(r_{u,j}-\overline{r_j})}{{\Sigma }_{j\in \mathrm{KNN}\left(i\right)\cap R\left(u\right)}{\mathrm{Sim}}_{i,j}}---\left(7\right)$>

通过上面的公式，推荐系统会将预测评分最高的项目推荐给用户。在整个推荐系统构建的过程中，K值的选择将会影响到推荐系统的性能：选取一个较小的K值会导致较低的推荐精度，而太大的K值将会增加模型的计算复杂度。本发明使用评分相似度和社会标签相似度来构建K近邻集合，会更好地衡量用户的喜好的因素，使近邻关系的计算更加精准。系统流程图示如图4所示。