融合多信息源耦合张量分解的标签推荐方法

摘要

本发明公开了一种融合多信息源耦合张量分解的标签推荐方法，首先，在标签‑资源‑用户三元组信息构造的张量CP分解同时，添加了标签与标签、标签与资源、标签与用户三个辅助信息矩阵参与联合分解，并且在构建标签与标签相似性矩阵时本发明同时考虑了标签间的共现关系和标签在WordNet中的语义相似性，以两种相似性的线性集成作为最终的标签间相似性度量。其次，在构建问题的损失函数后，用ADMM算法对目标函数进行参数优化。最后根据分解补全的预测张量更准确地向（用户，资源）对推荐Top‑N标签。本发明融合了标签的同异构信息，应用于各社会化标注系统上具有通用性。

说明书

技术领域

本发明涉及一种融合多信息源耦合张量分解的标签推荐方法，属于计算机网络标注技术领域。

背景技术

随着Web2.0网站的日益发展，Web上的信息以惊人的速度快速增长，信息增长的速度远远超过人们的处理能力。此时推荐系统在有效处理信息的过程中扮演了越来越重要的角色。社会化标注系统是推荐系统的一个典型应用得到了迅速发展，如共享音乐的last.fm、共享图片的Flicker、共享书签的Delicious等，在这些社会化标注系统当中，用户主动产生标签，并通过标签标识、管理和发现信息资源。标签的推荐是当前标注系统的一个研究热点，旨在减轻用户负担，帮助用户选择合适的标签完成标注操作。与传统的推荐系统只处理用户-资源(user-item)不同，社会化标注系统需要处理用户-标签-资源(user-tag-item)三个维度，所以只考虑二元关系的模型已不再适合包含用户、资源和标签三元关系的社会化标注系统。同时张量模型已经成为研究高阶数据之间潜在关联的流行方法，因此越来越多的学者开始研究基于张量分解模型的标签推荐。但是已有的张量分解方法，在标签推荐过程中仍然面临数据极度稀疏、缺失值以及过拟合问题。

针对上述三个问题，现有的基于张量分解的标签推荐方法只利用了标签-标签之间的同构辅助信息，而没有考虑利用标签-资源和标签-用户之间的异构辅助信息。

发明内容

目的：随着社会化标注系统应用的普及，为了克服现有基于张量分解的标签推荐方法只利用了标签-标签之间的同构信息的不足，为了提高标签推荐的准确性，本发明提供一种融合多信息源耦合张量分解的标签推荐方法。

技术方案：为解决上述技术问题，本发明采用的技术方案为：

一种融合多信息源耦合张量分解的标签推荐方法，具体步骤如下：

Step1:基于标签共现和语义相关两种相似性度量的线性集成构造标签相似矩阵B；

Step2：构造标签-资源，Tag-Item矩阵C；

Step3：构造标签-资源，Tag-User矩阵D；

Step4：模型构建及参数优化算法；

Step5：标签推荐。

作为优选方案，所述Step1包括如下步骤：

Step1.1计算标签共现相似性：

假设t_i和t_j是标签相似矩阵B数据集中的两个标签，那么它们之间共现相似性的度量方法如式1所示：

|t_i∩t_j|表示t_i和t_j共同标注的资源数，|t_i∪t_j|表示t_i和t_j标注的资源总和；

Step1.2计算标签语义相似性：

根据标签在WordNet中语义相似性计算标签的语义相似性，数据集中两个标签t_i和t_j语义相似性如式2所示：

其中LCS是t_i和t_j的最小公共超概念，depth(LCS)是从LCS到分类根的节点数目；N1是从t_i到LCS路径上节点的数目，N2是从t_j到LCS路径上节点的数目；

Step1.3集成相似性和语义作为最后相似度：

Step1.1和Step1.2分别获取标签共现相似性和标签语义层级的相互关联关系，为了使这两种方式相互补充，组合两种标签间的相似性计算作为t_i和t_j最后的相似度：

B_i,j＝γ×cooccurrence_B_i,j+(1-γ)×senmantic_B_i,j,γ∈[0，1]>

Step1.4标签图Laplacian作为正则化项：

标签图正则化的假设是如果标签i和标签j相似，那么由张量分解过程挖掘的标签的隐含特征因子矩阵U⁽¹⁾中标签i和标签j的隐含特征行向量和也会非常接近；

其中，B_i,j为Step>(1)第i行第d列元素，代表标签的隐含特征因子矩阵U⁽¹⁾整个第d列，L称为图Laplacian矩阵，L＝D-B，D为对角矩阵，D对角元素的第i个值为相似矩阵B对应第i行的元素和，即D_ii＝∑_jB_i,j；而tr(.)表示矩阵的迹。

作为优选方案，所述Step2包括如下步骤：

将社会化标注系统的训练数据集中所有标签视为文档集，标签t_h标注资源v_j的权重为：

其中Num(h,j)表示标签t_h在整个标签集中出现的次数，M为系统中资源总的个数，d_hj表示标签标注的资源数。

作为优选方案，所述Step3包括如下步骤：

将社会化标注系统的训练数据集中所有标签视为文档集，则标签t_k被用户u_i使用的权重为：

其中Num(k,i)表示标签t_k在整个标签集中出现的次数，N为系统中总的用户数，W_ki表示标签标注的用户数。

作为优选方案，所述Step4包括如下步骤：

Step4.1：形式化标签推荐为基本的CP张量分解模型：

设定U⁽¹⁾,U⁽²⁾,U⁽³⁾分别是标签(Tag)、资源(Item)、用户(User)对应的隐含特征因子矩阵；其中k为张量的秩，k＜＜＜min(|Tag|,|Item|,|User|),则基于CP张量分解的标签推荐模型定义为如下约束优化问题：

其中，为利用社会化标注系统的训练数据集构造的初始张量，λ为正则化参数，|| ||_F为L₂范数，为Tikhonov正则化项，防止目标表达式过拟合并提供唯一解，代表和同样大小的非负指示器张量，如果有观测到的标注行为值，则否则等于代表观测到的标注行为值；

Step4.2：整合Step1-Step3构造的辅助信息作为正则化项加入到步骤4.1构造的模型，步骤4.1中模型变换成解决如下约束优化问题：

其中α控制标签之间相似性的辅助信息参与分解的权重，β控制标签-资源矩阵C和标签-用户矩阵D作为辅助信息参与分解的权重；

因为公式(8)没有闭式解，本发明用ADMM，Alternating Direction Method of Multipliers算法优化目标函数求解；目标函数公式(8)写成部分拉格朗日函数形式如式公式(9)：

其中Z⁽ⁿ⁾≥0，n＝1,2,3是为了求解式(9)引入的临时变量，Y⁽ⁿ⁾(n＝1，2，3)为拉格朗日乘子矩阵,η是惩罚参数，<*,*>是内积运算；

Step 4.3：ADMM优化目标表达式公式(9)：

本发明采取迭代方案求解式(9)，分别更新然后接着更新{Y⁽¹⁾,Y⁽²⁾,Y⁽³⁾}，具体步骤如下:

(1)更新Z⁽¹⁾,Z⁽²⁾,Z⁽³⁾

为了更新Z⁽¹⁾,Z⁽²⁾,Z⁽³⁾,只需要求解如下优化问题，如式(10)所示:

把Z,Y,U写成列向量形式，比如Z＝[Z₁...Z_m]，Z_i是Z的第i列，因此Z_i,Y_i,U_i都是列向量；Z⁽ⁿ⁾通过求解优化问题公式(11)和公式(12)被有效的更新：

解(11)得到

解(12)得到

其中I为单位矩阵；

(2)更新U⁽¹⁾,U⁽²⁾,U⁽³⁾：

为了更新U⁽¹⁾,U⁽²⁾,U⁽³⁾,式(9)重新写成式(15):

其中E⁽ⁿ⁾＝(U^(N)⊙...U⁽ⁿ⁺¹⁾⊙U^(n-1)⊙LU⁽¹⁾)^T|_N＝3,⊙为Khatri-Rao积,X_(n)是张量的mode-n展开矩阵；那么得到关于U⁽ⁿ⁾的更新公式如下:

(3)更新

其中是的补，等于

(4)更新Y⁽ⁿ⁾：

(5)更新η：

自适应更新η加速优化算法，按式(21)更新η：

η_t+1＝min(ρη_t,η_max)>

作为优选方案，所述Step5包括如下步骤：

经过对式(9)的联合分解后，可以得到补全后的张量中元素代表一个四元组(t,v,u,p),p代表用户u对资源v打t标签的可能性；标签可以根据(u,v)对应的权重进行推荐；如果当用户u给资源v打标签时，欲推荐N个标签，那么就从高到低选择N个权值对应的标签。

有益效果：本发明提供的融合多信息源耦合张量分解的标签推荐方法，首先通过构建标签与标签、标签与资源、标签与用户三个辅助信息矩阵，在构建了问题模型后，用ADMM算法对训练模型进行参数优化，使用耦合张量-矩阵分解方法计算标签、用户和资源的隐含特征向量，为标注用户推荐标签。该算法可以有效地利用标签的同构和异构语义信息，有效缓解了上述数据稀疏、缺失值和过拟合问题；具有通用性，适合应用于各社会化标注系统。

附图说明

图1为耦合张量-矩阵分解模型示意图；

图2为标签推荐算法框架图；

图3为ADMM优化模型参数算法图。

具体实施方式

下面结合附图对本发明作更进一步的说明。

如图1-2所示，一种融合多信息源耦合张量分解的标签推荐方法，具体步骤如下：

Step1:基于标签共现和语义相关两种相似性度量的线性集成构造标签相似矩阵B；

如果两个资源被打过相似的标签，那么这两个资源很有可能具有相似的隐含特征向量，因此可以通过标签信息正则化耦合张量-矩阵分解过程。

Step1.1计算标签共现相似性：

假设t_i和t_j是标签相似矩阵B数据集中的两个标签，那么它们之间共现相似性的度量方法如式1所示：

|t_i∩t_j|表示t_i和t_j共同标注的资源数，|t_i∪t_j|表示t_i和t_j标注的资源总和；

Step1.2计算标签语义相似性：

根据标签在WordNet中语义相似性计算标签的语义相似性，数据集中两个标签t_i和t_j语义相似性如式2所示：

其中LCS是t_i和t_j的最小公共超概念，depth(LCS)是从LCS到分类根的节点数目；N1是从t_i到LCS路径上节点的数目，N2是从t_j到LCS路径上节点的数目；

Step1.3集成相似性和语义作为最后相似度：

步骤1.1和步骤1.2分别获取标签共现相似性和标签语义层级的相互关联关系，为了使这两种方式相互补充，组合两种标签间的相似性计算作为t_i和t_j最后的相似度：

B_i,j＝γ×cooccurrence_B_i,j+(1-γ)×senmantic_B_i,j,γ∈[0，1]>

Step1.4标签图Laplacian作为正则化项：

标签图正则化的主要假设是如果标签i和标签j相似，那么由张量分解过程挖掘的标签的隐含特征因子矩阵U⁽¹⁾中标签i和标签j的隐含特征行向量和也会非常接近。

其中，B_i,j为Step>(1)第i行第d列元素，代表标签的隐含特征因子矩阵U⁽¹⁾整个第d列，L称为图Laplacian矩阵，L＝D-B，D为对角矩阵，D对角元素的第i个值为相似矩阵B对应第i行的元素和，即D_ii＝∑_jB_i,j；而tr(.)表示矩阵的迹。

Step2：构造标签-资源(Tag-Item)矩阵C：

将社会化标注系统的训练数据集中所有标签视为文档集，标签t_h标注资源v_j的权重为：

其中Num(h,j)表示标签t_h在整个标签集中出现的次数，M为系统中资源总的个数，d_hj表示标签标注的资源数；

Step3：构造标签-资源(Tag-User)矩阵D：

将社会化标注系统的训练数据集中所有标签视为文档集，则标签t_k被用户u_i使用的权重为：

其中Num(k,i)表示标签t_k在整个标签集中出现的次数，N为系统中总的用户数，W_ki表示标签标注的用户数；

Step4：模型构建及参数优化算法：

Step4.1形式化标签推荐为基本的CP张量分解模型：

设定U⁽¹⁾,U⁽²⁾,U⁽³⁾分别是标签(Tag)、资源(Item)、用户(User)对应的隐含特征因子矩阵。其中k为张量的秩，k＜＜＜min(|Tag|,|Item|,|User|),则基于CP张量分解的标签推荐模型可以定义为如下约束优化问题：

其中，为利用社会化标注系统的训练数据集构造的初始张量，λ为正则化参数，|| ||_F为L₂范数，为Tikhonov正则化项，防止目标表达式过拟合并提供唯一解，代表和同样大小的非负指示器张量，如果有观测到的标注行为值则否则等于代表观测到的标注行为值；

Step4.2整合Step1-Step3构造的辅助信息作为正则化项加入到步骤4.1构造的模型，步骤4.1中模型变换成解决如下约束优化问题：

其中α控制标签之间相似性的辅助信息参与分解的权重，β控制标签-资源矩阵C和标签-用户矩阵D作为辅助信息参与分解的权重。

因为式(8)没有闭式解。本发明用ADMM(Alternating Direction Method of Multipliers)算法优化目标函数求解。目标函数(8)写成部分拉格朗日函数形式如式(9)：

其中Z⁽ⁿ⁾≥0，n＝1,2,3是为了求解式(9)引入的临时变量，Y⁽ⁿ⁾(n＝1，2，3)为拉格朗日乘子矩阵,η是惩罚参数，<*,*>是内积运算。

如图3所示，Step 4.3：ADMM优化目标表达式：

本发明采取迭代方案求解式(9)，分别更新然后接着更新{Y⁽¹⁾,Y⁽²⁾,Y⁽³⁾}，具体步骤如下:

(1)更新Z⁽¹⁾,Z⁽²⁾,Z⁽³⁾

为了更新Z⁽¹⁾,Z⁽²⁾,Z⁽³⁾,只需要求解如下优化问题，如式(10)所示:

把Z,Y,U写成列向量形式，比如Z＝[Z₁...Z_m],Z_i是Z的第i列,因此Z_i,Y_i,U_i都是列向量。Z⁽ⁿ⁾可以通过求解优化问题(11)和(12)被有效的更新:

解(11)得到

解(12)得到

其中I为单位矩阵。

(2)更新U⁽¹⁾,U⁽²⁾,U⁽³⁾.

为了更新U⁽¹⁾,U⁽²⁾,U⁽³⁾,式(9)重新写成式(15):

其中E⁽ⁿ⁾＝(U^(N)⊙...U⁽ⁿ⁺¹⁾⊙U^(n-1)⊙LU⁽¹⁾)^T|_N＝3,⊙为Khatri-Rao积,X_(n)是张量的mode-n展开矩阵。那么得到关于U⁽ⁿ⁾的更新公式如下:

(3)更新

其中是的补，等于

(4)更新Y⁽ⁿ⁾

(5)更新η

可以自适应更新η加速优化算法，按式子(21)更新η。

η_t+1＝min(ρη_t,η_max)>

Step5 标签推荐

经过对式(9)的联合分解后，可以得到补全后的张量中元素代表一个四元组(t,v,u,p),p代表用户u对资源v打t标签的可能性；标签可以根据(u,v)对应的权重进行推荐；如果当用户u给资源v打标签时，欲推荐N个标签，那么就从高到低选择N个权值对应的标签。

以上所述仅是本发明的优选实施方式，应当指出：对于本技术领域的普通技术人员来说，在不脱离本发明原理的前提下，还可以做出若干改进和润饰，这些改进和润饰也应视为本发明的保护范围。