一种基于张量分解及加权HITS的时间感知个性化POI推荐方法

摘要

本发明涉及一种基于张量分解及加权HITS的时间感知个性化POI推荐方法，本发明针对传统POI推荐方法中面临的数据稀疏性问题，首先通过引入附加信息的协同张量分解对用户偏好进行建模，然后通过加权HITS同时整合用户偏好与POI的流行度为POI进行打分。最后根据POI打分为用户提供排名靠前的若干POI作为推荐。本发明通过集成协同张量分解与加权HITS考虑用户偏好、时间及当地特色三个因素，克服数据稀疏性问题，为用户提供高质量的个性化POI推荐。

说明书

技术领域

本发明涉及POI推荐领域，尤其涉及一种基于张量分解及加权HITS的时间感知个性化POI推荐方法。

背景技术

随着装备GPS智能设备的快速发展，产生了基于位置的社交网络服务(Location-based Social Networking Services，LBSNs)，如Foursquare、Facebook Places、GooglePlaces等。在LBSNs上，用户可以登录(check-in)商店、餐厅等POI(Point of Interest)并分享。由于LBSNs用户众多并能覆盖广大的区域，在其基础上出现了POI推荐服务，不仅可以帮助用户认识新的POI和探索不熟悉的区域，而且可以方便广告主向目标用户推送移动广告。

传统的个性化POI推荐方法主要有两类：第一类是基于协同过滤(collaborativefiltering，CF)方法。协同过滤又可以分为基于记忆协同过滤(memory-based CF)方法和基于模型协同过滤方法(model-based CF)，其中基于记忆协同过滤方法包括基于用户(user-based CF)与基于项目(item-based CF)协同过滤方法。然而，一个用户能够访问的POI是有限的，而城市中有数量庞大的POI，对于传统的基于协同过滤的推荐方法，用户-POI矩阵过于稀疏。第二类是基于链路分析(link analysis)方法。链路分析算法(如：PageRank和HITS)广泛用于网页排序，可以通过分析图的结构提取高质量节点。基于链路分析的POI推荐算法包括全局推荐与个性化推荐。其中全局推荐方法的明显缺陷是不能提供个性化的推荐服务，而能够提供个性化POI推荐的方法依赖用户位置历史的规模，当用户位置历史规模小时推荐效果往往不够理想。此外，高质量的POI推荐需要同时考虑以下三种因素：1)用户偏好：个性化POI推荐需要符合用户的偏好，例如音乐爱好者对音乐会感兴趣，购物狂会更加关注购物商场，根据用户偏好对不同的用户提供不同的推荐。2)时间：用户偏好会随着时间而变化，例如中午在中餐馆吃午餐，午夜在酒吧消遣。3)当地特色：用户的偏好或行为模式会随着地理区域的变化而变化，比如杭州的越剧爱好者到香港旅行，往往会去访问香港本地的特色场所(如购物中心和美食餐馆等)，而不是去看越剧，因此为用户推荐本地的特色场所非常有意义。

发明内容

本发明为克服上述的不足之处，目的在于提供一种基于张量分解及加权HITS的时间感知个性化POI推荐方法，本发明针对当前个性化POI推荐的数据稀疏性问题，同时考虑到用户偏好、时间及当地特色在POI推荐中扮演的重要角色，主要包括用户偏好建模和POI打分及推荐，在用户偏好建模阶段，首先构建一个用户偏好张量和三个附加矩阵，然后通过这三个矩阵的协同帮助补全该张量，从而提高用户偏好建模的准确性。在POI打分及推荐阶段，给定一个查询用户以及其所在的位置和时间，首先建立LBSN图，用户间的边权为用户相似性，然后将该LBSN图输入HITS算法，计算每个POI的分数，并取分数高的前若干POI作为推荐。

本发明是通过以下技术方案达到上述目的：一种基于张量分解及加权HITS的时间感知个性化POI推荐方法，包括如下步骤：

1)基于协同张量分解的用户偏好建模：

1.1)输入用户check-in历史数据及POI类别数据，根据用户在任意一个时间段内对一类POI的访问频数，构建三维用户偏好张量并对其进行归一化；

1.2)输入用户check-in历史数据、POI类别数据及用户信息数据，根据用户的个人信息及对不同类POI的访问历史，构建用户-特征矩阵X，并对其进行归一化；

1.3)输入用户check-in历史数据及POI类别数据，根据不同时间段内各中类别POI被访问的频数，构建时间段-POI类别矩阵Y，并对其进行归一化；

1.4)输入POI类别数据，将POI类别两两组合构成搜索引擎的关键字，将返回的结果数作为相应POI类别间的相关性构建类别-类别矩阵Z，并对其进行归一化；

1.5)输入三维用户偏好张量用户-特征矩阵X、时间段-POI类别矩阵Y和类别-类别矩阵Z，通过矩阵X、Y、Z的协同张量分解帮助补全三维用户偏好张量

2)基于加权HITS的POI打分及推荐：

2.1)输入用户-特征矩阵X，根据余弦相似性计算公式计算用户间的相似性，作为LBSN图中用户间边的权值；

2.2)将查询用户当前时间τ映射为用户偏好张量中的一个时间段t；

2.3)输入查询区域当地所有用户的check-in历史数据、当地用户间的相似性及当前时间查询用户的偏好，为查询用户构建LBSN图；

2.4)将构建得到的LBSN图输入加权HITS中，计算查询区域当地所有POI分数；

2.5)根据查询用户当前位置l确定产生候选项的区域r；

2.6)根据区域r内POI分数，选取分数最大的前若干项作为提供给该查询用户的POI推荐。

作为优选，所述对三维用户偏好张量进行归一化的方法为将三维用户偏好张量中的每一项除以内所有项中的最大值。

作为优选，所述的用户特征包括用户性别特征F_g和位置历史特征F_l，将每个用户的特征F_g和F_l串联成一个向量形式，形成用户-特征矩阵；进行归一化操作时，将每个特征项的值映射到[0-1]区间，映射公式如下所示：

其中，x表示原值，x′表示归一化后的值，min和max分别表示F_g或F_l特征值的最小值和最大值。

作为优选，所述步骤1.5)利用tucker分解模型在X、Y和Z的协同帮助下对进行补全：

(i)张量被分解为一个核张量和三个矩阵的相乘形式，即其中核张量矩阵X被分解为两个矩阵的相乘形式，即X＝U×V，其中矩阵Y被分解为两个矩阵的相乘形式，即Y＝T×C^T，其中

(ii)得到协同张量分解的目标函数，如下式所示：

其中，||·||为Frobenius范数；控制张量分解误差；||X-UV||²控制矩阵X的分解误差，||Y-TC^T||²控制矩阵Y的分解误差；||S||²+||U||²+||C||²+||T||²+||V||²为防止模型过拟合的正则项；λ₁，λ₂，λ₃和λ₄为控制分解过程中各部分重要程度的参数；tr(C^TL_YC)由如下公式推导得到：

∑_ij||C(i，·)-(j，·)||²Z_ij＝∑_k∑_ij||C(i，k)-C(j，k)||²Z_ij＝tr(C^T(D-Z)C)＝tr(C^TL_YC)

其中，tr(·)表示矩阵的迹，D(D_ii＝∑_iZ_ij)为对角矩阵，L_Z＝D-Z为拉普拉斯矩阵；

(iii)采用梯度下降算法优化目标函数，得到补全后的张量

作为优选，所述的余弦相似性计算公式如下所示：

其中，u_i和u_j表示任意两个用户，和分别为用户u_i和u_j的归一化的特征向量。

作为优选，所述用户偏好张量中的一个时间段t优选跨度为1小时。

作为优选，所述构建得到的LBSN图中，用户和POI作为节点，用户间的朋友关系表示成无向边，用户对POI的check-in关系表示成从用户到POI的有向边；用户间的边权为对应用户间的相似性，用户与POI>j间的边权为查询用户u_i在时间段t_k内对该POI的偏好值

作为优选，所述步骤2.4)将LBSN图输入到加权HITS中，按照如下公式迭代计算得到针对查询用户查询区域内所有POI的分数：

其中，POI的authority值α_POI定义为访问过该POI所有用户的hub值之和，用户的hub值h_U定义为该用户所有朋友的hub值之和加上该用户访问过的所有POI的authority值之和，用户与POI展现出相互加强的关系；0＜β＜1；W_U为用户-用户邻接矩阵，定义如下：

其中，0＜λ＜1；E^f表示用户间的边集，e_ij∈E^f是用户u_i与用户u_j间的边；W_U(i，j)表示W_U中的一项；sim_ij表示用户u_i与用户u_j间基于用户特征向量的余弦相似性；为用户u_i访问过的所有POI的数；W_U-POI为用户-POI邻接矩阵，定义如下所示：

其中，E^c为用户与POI间的边集；e_ik∈E^c表示用户u_i到POI>k的有向边；W_U-POI(i，k)是W_U-POI中的一项；up._j表示查询用户u_i在时间段t_k内对该POI>j的偏好值为用户u_i的朋友数；W_POI-U为POI-用户邻接矩阵，定义如下所示：

其中，P_ki为POI>j被用户u_i访问的概率。

作为优选，所述步骤2.5)以查询用户当前位置l为中心，以R为半径确定产生候选项的区域r。

作为优选，所述步骤2.6)具体如下：根据区域r内所有POI分数，选取该区域r内用户以前没有访问过的POI作为候选项，并根据POI分数对候选POI进行降序排序，选择分数最大的前若干POI作为推荐结果。

本发明的有益效果在于：本发明通过集成协同张量分解与加权HITS考虑用户偏好、时间及当地特色三个因素，克服数据稀疏性问题，为用户提供高质量的个性化POI推荐。

附图说明

图1是本发明方法的流程示意图；

图2是本发明实施例构建的三维用户偏好张量示意图；

图3是本发明实施例的协同张量分解示意图；

图4是本发明实施例构建的LBSN图示意图；

图5是本发明实施例确定产生的候选区示意图。

具体实施方式

下面结合具体实施例对本发明进行进一步描述，但本发明的保护范围并不仅限于此：

实施例：如图1所示，一种基于张量分解及加权HITS的时间感知个性化POI推荐方法，包括以下步骤：

(1)基于协同张量分解的用户偏好建模

步骤1：输入用户check-in历史数据及POI类别数据，根据用户在某个时间段内对某类POI的访问频数，构建三维用户偏好张量(用户，时间段，POI类别)，并对其进行归一化；

用户偏好张量对时间感知的用户偏好进行建模，构建结果如图2所示。POI类别表示POI功能并且有不同的粒度，往往表示成类别层次结构。

本发明假设已存在该POI类别层次，并分为两层，第一层为n个大类，第二层为m个小类(n＜＜m)。该张量的第一维表示用户u＝[u₁，u₂，…，u_i，…，u_N]；第二维为POI类别层次中的第二层c＝[c₁，c₂，…，c_j，…，c_M]，其中M＝m；最后一维为时间段t＝[t₁，t₂，…，t_k，…，t_L]，其中L＝24为一天中的24小时。张量中的每一项保存用户u_i在时间段t_k内对类别为c_j的POI的访问频数，并除以所有项中的最大值进行归一化操作。

步骤2：输入用户check-in历史数据、POI类别数据及用户信息数据，根据用户的个人信息及对不同类POI的访问历史，构建用户-特征矩阵X，并对其进行归一化；

用户特征包括用户性别特征F_g和位置历史特征F_l。特征F_l包括用户对POI类别层次中第一层各类别POI的访问频次f_l(|f_l|＝n)以及f_l的相关统计特征(如，最大值、最小值、均值、标准差、总数、中位数等)。将每个用户的特征F_g和F_l串联成一个向量形式，从而形成用户-特征矩阵(P表示用户特征维数)。针对每个特征项，对其进行归一化操作，使每一项的值映射到[0-1]间，其转换公式如(1)所示，其中x表示原值，x′表示归一化后的值，min和max表示某特征值的最小值和最大值。

步骤3：输入用户check-in历史数据及POI类别数据，根据不同时间段内各中类别POI被访问的频数，构建时间段-POI类别矩阵Y，并对其进行归一化；

本发明通过构建时间段-POI类别矩阵来对时间特征进行建模。该矩阵Y的每行表示一个时间段，每列表示一个POI类别，每项Y_kj表示在时间段t_k内访问类别为c_j的POI的频次。

步骤4：输入POI类别数据，将POI类别两两组合构成搜索引擎的关键字，其返回的结果数作为相应POI类别间相关性，从而构建类别-类别矩阵Z，并对其进行归一化；

POI类别c_i和c_j间的相关性Cor(c_i，c_j)可以通过将上述两种类别的类别名作为搜索引擎的关键字搜索得到，即搜索引擎返回的结果数。将所有类别间的相关性放在一起形成类别-类别矩阵然后Z中的每一项除以所有项中的最大值进行归一化操作。

步骤5：输入稀疏的用户偏好张量用户-特征矩阵X、时间段-POI类别矩阵Y和类别-类别矩阵Z，通过协同张量分解补全用户偏好张量从而精确地对用户偏好进行建模。

如图3所示，本发明利用tucker分解模型在X、Y和Z的协同帮助下对进行补全。张量被分解为一个核张量和三个矩阵的相乘形式，即其中核张量矩阵X被分解为两个矩阵的相乘形式，即X＝U×V，其中矩阵Y被分解为两个矩阵的相乘形式，即Y＝T×C^T，其中

协同张量分解的目标函数如上式(2)所示，其中||·||为Frobenius范数；控制张量分解误差；||X-UV||²控制矩阵X的分解误差，||Y-TC^T||²控制矩阵Y的分解误差；||S||²+||U||²+||C||²+||T||²+||V||²为防止模型过拟合的正则项；λ₁，λ₂，λ₃和λ₄为控制分解过程中各部分重要程度的参数。此外，tr(C^TL_YC)由下式(3)推导得到，其中tr(·)表示矩阵的迹，D(D_ii＝∑_iZ_ij)为对角矩阵，L_Z＝D-Z为拉普拉斯矩阵。本发明基于张量中的非零项，使用梯度下降算法优化目标函数。从而根据下式(4)得到补全后的张量用户u_i在时间段t_k内的偏好可以表示成

(2)基于加权HITS的POI打分及推荐

步骤1：输入用户-特征矩阵X，根据余弦相似性计算公式计算用户间的相似性，作为LBSN图中用户间边的权值；

针对任意两个用户u_i和u_j，根据余弦相似性计算公式得到两个用户相应的相似性，其中和分别为用户u_i和u_j的归一化的特征向量。余弦相似性计算公式如下式所示：

步骤2：将查询用户当前时间τ映射为时间段t：将查询用户当前的查询时间τ映射为用户偏好张量中时间段维中的一个时间段。本发明的时间段划分方式是将一天划分为24个时间段，每个时间段跨度为1小时。

步骤3：输入查询区域当地所有用户的check-in历史数据、当地用户间的相似性及当前时间查询用户的偏好，为查询用户构建LBSN图；如图4所示为查询用户构建LBSN图。其中用户和POI作为节点，用户间的朋友关系表示成无向边，用户对POI的check-in关系表示成从用户到POI的有向边。用户间的边权为对应用户间的相似性，用户与POI>j间的边权为查询用户u_i在时间段t_k内对该POI的偏好值从而构建针对用户u_i的LBSN图。需要注意的是LBSN图可以针对每个城市离线初步构建，在线阶段只需将用户与POI间的边权替代为当前查询用户的偏好，从而提高LBSN图构建的效率。

步骤4：将针对查询用户而构建的LBSN图输入加权HITS中，计算查询区域当地所有POI分数；

在此阶段，针对每个查询用户，本发明假设查询区域当地所有用户的偏好与该查询用户一致，同时考虑当地特色，从而得到该基于加权HITS的POI打分方法。当查询用户对某POI有偏爱时，指向该POI的边权值相对较大，从而最后的打分也相对较大(考虑用户偏好)；当查询用户对某POI比较不喜欢时，相应的边权较小，但如果该POI属于本地特色时，有许多指向其的边，从而最终的分数也不小(考虑本地特色)。将上述LBSN图输入到加权HITS中，如等式(6)所示，POI的authority值α_POI定义为访问过该POI所有用户的hub值之和，用户的hub值h_U定义为该用户所有朋友的hub值之和加上该用户访问过的所有POI的authority值之和，用户与POI展现出相互加强的关系。从而通过迭代计算得到针对查询用户查询区域内所有POI的分数。

其中，0＜β＜1；W_U为用户-用户邻接矩阵，定义在等式(7)中；W_U-POI为用户-POI邻接矩阵，定义在等式(8)中；W_POI-U为POI-用户邻接矩阵，定义在等式(9)中。

其中，0＜λ＜1；E^f表示用户间的边集，e_ij∈E^f是用户u_i与用户u_j间的边；W_U(i，j)表示W_U中的一项；sim_ij表示用户u_i与用户u_j间基于用户特征向量的余弦相似性；为用户u_i访问过的所有POI的数量。

其中，E^c为用户与POI间的边集；e_ik∈E^c表示用户u_i到POI>k的有向边；W_U-POI(i，k)是W_U-POI中的一项；up._j表示查询用户u_i在时间段t_k内对该POI>j的偏好值为用户u_i的朋友数。

其中，P_ki为POI>j被用户u_i访问的概率。

步骤5：根据查询用户当前位置l确定产生候选项的区域；

对于带有查询位置l的查询用户u，即q＝(u，l)，本发明以当前位置l为中心，确定一个半径为R的范围为产生候选项区域r，如图5所示。

步骤6：根据区域r内所有POI分数，选取分数最大的前若干项作为提供给该查询用户的POI推荐。

此步骤中，选取该区域r内用户以前没有访问过的POI作为候选项，并根据POI分数对这些候选POI进行降序排序，选择分数最大的前若干POI作为推荐结果。

以上的所述乃是本发明的具体实施例及所运用的技术原理，若依本发明的构想所作的改变，其所产生的功能作用仍未超出说明书及附图所涵盖的精神时，仍应属本发明的保护范围。