基于PageRank算法的网络个性化推荐方法

暂无

基于PageRank算法的网络个性化推荐方法\n技术领域\n[0001] 本发明属于信息化处理技术领域，涉及协同过滤，特别是一种基于PageRank算法的网络个性化推荐系统，可用于在网络中的信息挖掘和信息服务。\n背景技术\n[0002] 互联网规模和覆盖面的迅速增长带来了信息超载的问题：过量信息同时呈现使得用户无法从中获取对自己有用的部分,信息使用效率反而降低。现有的很多搜索引擎和专业数据索引本质上都是帮助用户过滤信息的手段。然而传统的搜索算法只能呈现给所有的用户一样的排序结果，无法针对不同用户的兴趣爱好提供相应的服务。个性化推荐系统是建立在海量数据挖掘基础上，以推荐策略和推荐算法为技术支撑，对用户提供完全个性化的决策支持和信息服务。被认为是当前解决信息超载最有效的工具之\n[0003] 近年来，随着以Facebook和Twitter为代表的社会网络的兴起，社会化推荐逐渐成为个性化推荐方法的研究热点。社会化过滤方法利用组员和他的好友偏好的共同点，来分析好友的偏好，从而预测给定组员的偏好。最初的社会化过滤算法是基于邻域的算法。该方法利用组员及其周围的用户的相似特征，来找到组员之间的相似性偏好，从而实现组员的社会化推荐；接着出现了基于图模型的社会化过滤方法。该方法利用图模型将组员的社会网络和组员物品的偏好关系建模到一张图中，然后利用随机游走算法给组员做社会化推荐；随后出现了基于矩阵分解的社会化过滤方法。该方法利用矩阵分解的算法来分解组员的社会网络矩阵和组员物品偏好矩阵，计算出组员的特征向量和物品的特征向量，并最终利用特征向量的点乘度量组员对物品的偏好。\n[0004] 但是以上这些社会化推荐方法，随着组员和商品的增多，系统的性能会越来越低；\n都是针对单个组员进行偏好发现，所以对于组员比较多时，社交关系复杂的情况，推荐准确性就会大大下降。\n发明内容\n[0005] 本发明的目的是针对已有方法的不足，提出一种基于PageRank算法的网络个性化推荐方法，依据组员之间的信任关系，通过计算每个组员对组的重要性，提高在组员比较多、社交关系复杂情况下的推荐性能。\n[0006] 为实现上述目的，本发明包括如下步骤：\n[0007] （1）从网页配置文件中，获取组员以及组员之间的好友关系数据，定义基于好友关系的组为：G＝{u1,u2,…,ug}，其中ul为第l个组员,，g为组G中组员的个数；定义组G的邻接矩阵为M={aij}，aij表示组员ui与组员uj之间的关系，若aij＝1，则表示组员uj是组员ui的好友关系，若aij＝0，则表示组员uj不是组员ui的好友关系，其中ui,uj∈G，\n1≤i≤g，1≤j≤g；\n[0008] （2）根据组G内组员之间的好友关系，计算组员对组G归一化后的影响力向量为组员ul对组G归一化后的影响力，c为迭代计数器；\n[0009] （2a）初始化：设迭代计数器c为0，设 为每个组员对组G的影响力， 设为组员对组G的影响力向量，F0＝(1,1,...,1)，设收敛阈值为T，0＜T\n＜1；\n[0010] （2b）在组G内，若组员ul有k个好友ul1，ul2，...,ulk，1≤k≤g，则组员ul对组G的影响力 为：\n[0011] \n[0012] 其中，d是阻尼因子，0≤d≤1，C(uli)为uli好友的个数， 为好友uli对组G的影响力，\n[0013] （2c）根据步骤（2b）计算组员ul对组G的影响力 得到组G的影响力向量[0014] （2d）计算|Fc+1-Fc|的值，若|Fc+1-Fc|＜T，则对新的影响力向量Fc+1进行归一化，得到归一化后的影响力向量：\n[0015] 否则返回步骤（2c）；\n[0016] （3）收集组员ul对训练样本中的对象m的评分t，建立组员ul的个人喜好模型：P＝(v1,v2,…,vt)，1≤t≤5，t∈自然数，其中vt是评分为t的样本对象m集合的关键字向量，vt＝{w1,w2,…,wk}，其中wr为样本对象m的关键字,1≤r≤k，k为样本对象m的关键字个数；\n[0017] （4）输入待分析对象m′，并使用关键字表示待分析对象，得到待分析对象的关键字向量W′＝{w′1,w′2,…,w′k}，其中w′r为待分析对象m′的关键字,1≤r≤k，k为待分析对象m′的关键字个数；\n[0018] （5）计算组员ul对待分析对象m′的预测评分pred(ul,m′)，计算待分析对象m′的关键字向量W′和组员ul的个人喜好模型P中的vt之间的向量相似度，取向量相似度最大的vt所对应的分值t，作为组员ul对待分析对象m′的预测评分pred(ul,m′)，即：\n[0019] pred(ul,m′)＝t|max(rel(W′,vt)，\n[0020] 其中，rel(W′,vt)是待分析对象m′的关键字向量W′与组员ul的个人喜好模型P中，评分为t的样本对象集合的关键字向量vt之间的向量相似度；\n[0021] （6）计算组G对待分析对象m′的预测评分pred(G,m′)：\n[0022] \n[0023] （7）根据步骤（6）中所得的组G对待分析对象m′的预测评分pred(G,m′)的结果，来判断是否将对象m′推荐给组G，若pred(G,m′)≥λ，则表示待分析对象m′满足推荐条件，并向组G予以推荐；反之不予以推荐，λ为推荐系统预设的阈值，1≤λ≤5。\n[0024] 与现有技术相比，本发明具有如下优点：\n[0025] 1）本发明以组为单位进行个性化推荐，将推荐方法的处理对象由个人变成组，降低了过滤方法计算的复杂度，从而提高个性化推荐方法的效率。\n[0026] 2）本发明利用组内的信任特性，通过分析组内各组员间的拓扑关系，采用PageRank算法来计算各组员对组的影响，从而更好地反映出组的社会化影响，提高推荐性能。\n附图说明\n[0027] 图1是本发明流程图；\n[0028] 图2是本发明针对组中成员关系的拓扑结构图。\n具体实施方式：\n[0029] 下面结合附图对本发明进行详细说明：\n[0030] 参照图1，本发明的具体实现步骤如下：\n[0031] 本发明中所述基于PageRank算法的网络个性化推荐方法，有很多应用领域。比如，对电影的推荐，论文的推荐等领域。下面我们以电影推荐为例，介绍如何使用基于PageRank算法的网络个性化推荐方法。具体步骤如下：\n[0032] 步骤1：获取组G的组员以及组员之间的好友关系数据。\n[0033] 从网页配置文件中，获取组员以及组员之间的好友关系数据，定义基于好友关系的组为：G＝{u1,u2,…,ug}，其中ul为第l个组员,，g为组G中组员的个数；定义组G的邻接矩阵为M={aij}，aij表示组员ui与组员uj之间的关系，若aij＝1，则表示组员uj是组员ui的好友关系，若aij＝0，则表示组员uj不是组员ui的好友关系，其中ui,uj∈G，1≤i≤g，\n1≤j≤g。\n[0034] 本发明中的组是一种社会化的组，它可以描述为一个有向图。每个节点表示一个组员，节点之间的链接线表示组员之间的好友关系。指向节点的链接为入链接，从节点指出的链接为出链接。本发明中的好友关系是不对等的，例如组员a的好友是组员b，并不代表着组员b的好友也是组员a。\n[0035] 图2给出组G的好友关系拓扑图，组G共有4个组员G＝{u1,u2,u3,u4}。根据组G的拓扑图，得到组G的邻接矩阵： 组员u1的好友是组员u2，则a12＝\n1，组员u2的好友没有组员u1，则a21＝0。依此类推，可得组的邻接矩阵为\n[0036] \n[0037] 步骤2：采用PageRank算法，迭代计算组员对组G的影响力。\n[0038] 根据组G内组员之间的好友关系，计算组员对组G归一化后的影响力向量\n为组员ul对组G归一化后的影响力，c为迭代计数器。\n[0039] 2.1）初始化：设迭代计数器c为0，设 为每个组员对组G的影响力， 设\n为组员对组G的影响力向量，F0＝(1,1,...,1)，设收敛阈值为T，0＜T\n＜1；\n[0040] 2.2）在组G内，若组员ul有k个好友ul1，ul2，...,ulk，1≤k≤g，则组员ul对组G的影响力 为：\n[0041] \n[0042] 其中，d是阻尼因子，0≤d≤1，C(uli)为uli好友的个数， 为好友uli对组G的影响力，\n[0043] 如附图2，这里取d＝0.85，u1有2个组员好友组员，分别为组员u2、组员u3，组员\n0\nu2的好友组员个数为2，组员u3的好友组员个数为1，则组员u1的f1 迭代公式为：\n[0044] \n[0045] \n[0046] \n[0047] 依此类推，以计算所有组员的\n[0048] \n[0049] \n[0050] \n[0051] \n[0052] \n[0053] \n[0054] \n[0055] \n[0056] \n[0057] 2.3）根据步骤（2b）计算组员ul对组G的影响力 得到组G的影响力向量\n[0058] 第一次迭代后得到组G的影响力向量：\n[0059] \n[0060] \n[0061] 2.4）计算|Fc+1-Fc|的值，若|Fc+1-Fc|＜T，则对新的影响力向量Fc+1进行归一化，得到归一化后的影响力向量： 否则返回步骤\n（2c）；\n[0062] 经过有限次迭代，计算结果满足收敛条件T＝0.14，并将结果向量归一化得到[0063] 步骤3：根据训练样本，建立组员的个人喜好模型P。\n[0064] 收集组员ul对训练样本中的对象m的评分t，建立组员ul的个人喜好模型：P＝(v1,v2,…,vt)，1≤t≤5，t∈自然数，其中vt是评分为t的样本对象m集合的关键字向量，vt＝{w1,w2,…,wk}，其中wr为样本对象m的关键字,1≤r≤k，k为样本对象m的关键字个数。\n[0065] 例如对于电影对象，采用MovieLens数据集中电影数据的格式，包括电影的名称和流派标签，共有18种电影流派标签。向量vt＝{w1,w2,…,wk}是对应分值电影列表合集的形式描述，可以是电影名称、导演或演员列表。本发明采用电影流派标签来表示电影的特征，具体代表的流派标签内容见下表1，每部电影可采用一个18维的二进制码向量来表示，即电影的特征向量为W＝{ε1ε2…ε18}，其中εi取值为0或1，1≤i≤18。\n[0066] 样本中电影m的标签属性为“Action”、“Fantasy”、“Horror”和“War”，与18个流派标签中相同的是：w1，w9，w11和w17，则ε1，ε9，ε11和ε17的值均为1，剩余的ε2，ε3，ε4，ε5，ε6，ε7，ε8，ε10，ε12，ε13，ε14，ε15，ε16和ε18的值均为0，则其特征向量为W＝{100000001010000010}。\n[0067] 表1二进制码向量具体代表的流派标签\n[0068] \n w1 Action\n w2 Adventure\n w3 Animation\n w4 Children’s\n w5 Comedy\n w6 Crime\n w7 Documentary\n w8 Drama\n w9 Fantasy\n w10 Film-Noir\n w11 Horror\n w12 Musical\n w13 Mystery\n w14 Romance\n w15 Sci-Fi\n w16 Thriller\n w17 War\n w18 Western\n[0069] 针对组员u1，如果其评价为1分的电影有两部，这两部电影的特征向量分别为W1＝{101000000000000000}和W2＝{001001000000000000}，则组员u1评分为1的喜好模型v1＝W1|W2＝{101001000000000000}。依次类推，可计算v2、v3、v4和v5，即得到组员u1的喜好模型P＝(v1,v2,…,vt)。\n[0070] 对于论文对象，采用万方数据集中论文数据，包括论文的名称和关键字，共有11种论文标签。向量vt＝{w1,w2,…,wk}是对应分值论文列表合集的形式描述，可以是论文名称、作者或关键字等。本发明采用论文关键字来表示论文的特征，具体关键字内容见下表\n2，每个论文可采用一个11维的二进制码向量来表示，即论文的特征向量为W＝{ε1ε2…ε11}，其中εi取值为0或1，1≤i≤11。\n[0071] 样本论文m的关键字为“Data miming”、“Information extraction”和“filing”，与11个论文关键字中相同的是：w6，w10和w11，则ε6，ε10和ε11的值均为1，剩余的ε1，ε2，ε3，ε4，ε5，ε7，ε8和ε9的值均为0，则其特征向量为W＝{00000100011}。\n[0072] 表2二进制码向量具体代表的论文关键字\n[0073] \n w1 mathematics\n w2 physical\n w3 electricity\n w4 computer\n w5 Web security\n w6 Data miming\n w7 Pattern recognition\n w8 robot\n w9 chemistry\n w10 Information extraction\n w11 filing\n[0074] 针对组员u1，如果其评价为1分的论文有两篇，这两篇论文的特征向量分别为W1＝{10100010000}和W2＝{00000110000}，则组员u1评分为1的喜好模型v1＝W1|W2＝{10100110000}。依次类推，可计算v2、v3、v4和v5，即得到组员u1的喜好模型P＝(v1,v2,…,vt)。\n[0075] 步骤4：输入待分析对象m′及其特征向量\n[0076] 输入待分析对象m′，并使用关键字表示待分析对象，得到待分析对象的关键字向量W′＝{w′1,w′2,…,w′k}，其中w′r为待分析对象m′的关键字,1≤r≤k，k为待分析对象m′的关键字个数。\n[0077] 例如对于电影对象，则通过IMDB获取待推荐电影m′的流派标签“Action”、“Fantasy”、“Horror”和“War”，得到待推荐电影m′的关键字向量：\n[0078] W′＝{w′1,w′2,…,w′k}\n[0079] ＝{000000001000001010}；\n[0080] 对于论文对象，则通过万方数据库获取待推荐论文m′的关键字“Data miming”、“Information extraction”和“filing”得到待推荐论文m′的关键字向量：\n[0081] W′＝{w′1,w′2,…,w′k}\n[0082] ＝{100010000011000}。\n[0083] 步骤5：分别计算每个组员对待分析对象的预测值pred(ul,m′)。\n[0084] 计算组员u1对待分析对象m′的预测评分pred(ul,m′)，计算待分析对象m′的关键字向量W′和组员u1的个人喜好模型P中的vt之间的向量相似度，取向量相似度最大的vt所对应的分值t，作为组员u1对待分析对象m′的预测评分pred(ul,m′)，即：\n[0085] pred(ul,m′)＝t|max(rel(W′,vt)，\n[0086] 其中，rel(W′,vt)是待分析对象m′的关键字向量W′与组员u1的个人喜好模型P中，评分为t的样本对象集合的关键字向量vt之间的向量相似度。\n[0087] 例如对于电影对象W′与vt的向量相似度依次为：\n[0088] pred(u1,m′)＝t|max(rel(W′,vt)\n[0089] ＝t|max(2,2,4,3,1)\n[0090] ＝3\n[0091] 因为v3与W′的向量相似度4为最大值，则t＝3，故组员u1对待分析电影m′的预测值pred(u,m′)＝3。依此类推，可得pred(u2,m′)＝2，pred(u3,m′)＝3和pred(u4,m′)＝4。\n[0092] 对于论文对象W′与vt的向量相似度依次为：\n[0093] pred(u1,m′)＝t|max(rel(W′,vt)\n[0094] ＝t|max(1,4,2,3,1)，\n[0095] ＝2\n[0096] 因为v2与W′的向量相似度4为最大值，则t＝2，故组员u1对待分析论文m′的预测值pred(u1,m′)＝2。依此类推，可得pred(u2,m′)＝2，pred(u3,m′)＝4和pred(u4,m′)＝3。\n[0097] 步骤6：计算组G对待分析对象的预测值pred(G,m′)。\n[0098] 计算组G对待分析对象m′的预测评分pred(G,m′)：\n[0099] \n[0100] 例如对于电影对象，组G对待分析电影m′的预测值为：\n[0101] \n[0102] \n[0103] \n[0104] 对于论文对象，组G对待分析论文m′的预测值为：\n[0105] \n[0106] \n[0107] \n[0108] 步骤7：根据推荐条件给出待分析对象推荐结果。\n[0109] 根据步骤（6）中所得的组G对待分析对象m′的预测评分pred(G,m′)的结果，判断是否将对象m′推荐给组G，若pred(G,m′)≥λ，则表示待分析对象m′满足推荐条件，并向组G予以推荐；反之不予以推荐，λ为推荐系统预设的阈值，1≤λ≤5。\n[0110] 例如对于电影对象，这里取λ＝3，根据步骤（6）中得到的组G对待分析电影m′的预测值为：\n[0111] pred(G,m′)＝3.1414＞3，\n[0112] 所以可以将其推荐给组G。\n[0113] 对于论文对象，这里取λ＝3，根据步骤（6）中得到的组G对待分析论文m′的预测值为：\n[0114] pred(G,m′)＝2.7721＜3\n[0115] 所以不将其推荐给组G。\n[0116] 以上仅为本发明的一个具体实例，不构成对本发明的任何限制，显然用本发明方法可针对不同的领域，仅需修改获取其领域内关键字向量的方法，即可应用到网络上的不同领域，实现对不同领域对象的推荐。