一种基于随机游走和条件随机场的社会标签推荐方法

技术领域

本发明涉及数据挖掘与推荐系统应用领域，具体涉及一种基于随机游走和条件随机场的社会标签推荐方法。

背景技术

信息技术的飞速发展带来了信息过载问题，给用户的信息选择带来了沉重的负担。为了解决信息过载问题，人们引入了推荐系统方法。随着Web2.0技术的发展，越来越多的网络用户能够自由的选择标签标注网络资源，形成了社会化标签。标签既能够描述资源，也表示了用户对资源的偏好。

在标签推荐系统中，社会标签推荐的任务是给定用户和资源，为用户推荐一系列其可能为该资源添加的标签。现有的多数标签推荐方法将社会标签三维关系转化为二维关系，直接应用传统推荐模型，导致在标签推荐过程中未充分利用用户资源标签三维关系，造成了标签推荐质量的降低。一个资源往往会被多个用户标注多个标签，但是由于用户对资源了解程度和偏好的不同，造成标签信息中包含了噪音，如能将资源本身具有的特征和标签建立关联，关注标签自身特征对标签的影响。随着多标签技术的发展，其在规则挖掘，生物基因功能、中医证型分类中的应用前景巨大。而一个资源可能对应多种标签，将资源作为实例，标签作为类别，则可将标签推荐问题转化成多标签分类问题。为了提高标签推荐系统的质量，需充分挖掘用户、资源网络数据，标签间相关性等信息。

发明内容

本发明的目的在于提出一种基于随机游走和条件随机场的社会标签推荐方法，该方法充分利用用户、资源、标签三维关系和资源本身具有的特征对标签推荐的影响，降低了将社会标签的三维关系转换为二维关系以及因用户造成的标签噪音对推荐质量的影响，提高标签推荐的准确度。

本发明具体技术方案如下：

一种基于随机游走和条件随机场的社会标签推荐算法，包括以下步骤：

步骤1，构造基于资源的多标签随机游走模型。标签数据中的实例通常由用户、资源、标签构成，抽取出关于资源和标签的数据，根据该数据构造基于资源的随机游走模型，该模型可以充分利用资源特征，推荐可能标签，降低了因用户导致的标签噪声问题。

步骤2，设计以标签共现率、用户相似度为边特征函数和标签预测概率为点特征函数的条件随机场。

步骤3，估计条件随机场的参数。依据步骤2，估计条件随机场的参数，获得条件随机场的各个参数值。

步骤4，基于条件随机场的社会标签推荐。依据步骤2获得的特征函数，步骤3获得的参数值，建立条件随机场，获得指定用户与资源的可能推荐标签，该方法能够有效利用资源、用户和标签之间的潜在联系，推荐可能标签。

进一步地，所述步骤1中，构建基于资源的多标签随机游走模型包括以下步骤：

步骤1.1，标签数据中的实例通常由(u,i,t)三元组构成，u代表用户，i代表资源，t代表u为i添加的标签，抽取出资源和标签数据D＝{(x_i,y_i)|1≤i≤m}，其中(u,i,t)中的i对应D＝{(x_i,y_i)|1≤i≤m}中的x_i，t对应y_i，x_i＝[x_i1,x_i2,...,x_id]代表资源i本身具有的d维特征向量，y_i∈Y，Y＝{λ₁,λ₂,...,λ_q}代表为资源可能添加的q个标签，在获得资源标签数据集的基础上，将该资源标签数据集映射为资源随机游走图，具体步骤如下：

步骤1.1.1，将资源标签数据集中的每个数据映射为一个点，如果两个资源数据具有相同的标签，则将这两个数据对应的点相连，依据该原则生成多标签随机游走图G＝(V,E)。为了更准确地描述两个资源数据之间的关系，对于任意资源节点，在所有的邻居节点中，如果一个节点与该资源相关性越小，游走到这个节点的概率越低，基于该思想，计算转移矩阵P。

步骤1.2，基于步骤1.1，针对一个预测资源和资源随机游走图，构造资源的随机游走图系列，具体步骤为：

步骤1.2.1，对d维输入空间的资源标签数据集和预测资源x，由训练集和预测资源x生成随机游走图系列。

步骤1.2.2,随机游走模型的初始化。利用随机游走模型的公式S＝(1-α)·P^T·S₀+α·d初始化多标签随机游走模型的邻接矩阵P、初始概率分布向量S₀、跳转发生概率α、发生跳转时跳转到图中每个节点的概率分布向量d四个参数。

步骤1.3，基于条件概率模型，获得预测资源的推荐标签概率向量，具体步骤为：

步骤1.3.1，对于随机游走图系列中的任一子图，应用随机游走模型得到预测资源x与标签子图的节点相连时，以x为起点游走到每个节点的稳定概率分布。

步骤1.3.2，求S向量中m个元素的平均值为预测资源游走到某标签的平均条件概率，其中m代表资源个数。

步骤1.3.3，计算预测资源x具有某标签的平均概率。

步骤1.3.4，根据条件概率模型，计算预测资源x被标记为某标签的概率。

步骤1.3.5，获得预测资源的预测标签概率向量，该概率向量刻画了预测资源标记为不同标签的可能性大小。

进一步地，所述步骤2中，设计以标签共现率、用户相似度为边特征函数和标签预测概率为点特征函数的条件随机场，具体步骤为：

步骤2.1，构造边特征函数。条件随机场的边特征函数又称状态转移函数，本模型在利用标签共现率、用户相似度刻画边特征函数。

步骤2.2，构造节点特征函数。依据步骤1.3.5预测标签概率向量中各标签的概率值构建条件随机场的点特征函数。

步骤2.3，在给定预测资源x的情况下，计算x可能被标记的标签y。

进一步地，所述步骤3中，估计资源的条件随机场的参数，采用极大似然估计。估计资源的条件随机场的参数θ＝(θ¹,θ²,θ³)，采用极大似然估计，将参数θ的似然函数写成其中m为训练样本中资源的数量，是边特征函数，ψ(λ_i,x)是点特征函数，Z(x)为规范化因子，对似然函数进行求导，使得导数为零。

进一步地，所述步骤4中，基于条件随机场的社会标签推荐。依据步骤2获得的特征函数，步骤3获得的参数值，构建条件随机场，获得资源的可能推荐标签，具体步骤为：

步骤4.1，在获得参数估计的基础上，求条件概率最大的输出序列，输出概率向量具体步骤为：

步骤4.1.1，初始化标签的概率。

步骤4.1.2，递推，从前向后推出每一步路径概率最大值，同时记录概率最大值的路径。

步骤4.1.3，从后往前返回每步的最优值，并求得标签排序向量。

步骤4.2，选择前k个标签作为资源的预测标签。

本发明的有益效果：

采用随机游走和条件随机场的社会标签推荐，利用多标签随机游走模型预测基于资源本身特征推荐可能标签，降低了标签噪音的影响，采用条件随机场，有效利用了用户、资源和标签的相关性信息构造的点特征函数和边特征函数，提高了标签推荐的质量。

本发明提出的一种利用多标签分类方法挖掘用户资源标签三维关系的社会标签推荐方法，该方法挖掘资源本身的信息对标注标签的影响，从而降低了因标签噪音导致的推荐质量不高的问题，帮助用户更好的依据资源获得合适的标签。

附图说明

图1为本发明实施例提供的基于随机游走和条件随机场的社会标签推荐方法的示意图。

图2为本发明实施例提供的数据抽取示意图。

图3为本发明实施例提供的条件随机场预测模型的流程图。

图4为本发明实施例提供的随机游走图。

图5为本发明实施例提供的随机游走图系列。

具体实施方式

为使本发明要解决的技术问题、技术方案和优势更加清楚，下面将结合附图及具体实施例进行详细描述。本发明选择Cleaned Dump数据集，该数据集是Bibsonomy网站的公共数据。

抽取该数据集中的用户标签、资源标签数据，形成用户标签数据集D₁,资源标签数据集D₂，抽取过程如图2所示。选择资源标签数据集中能够构建资源的候选标签的特征为资源的特征向量，包括url网址信息，description网址描述信息，titie书籍名称，description书籍描述信息。该数据集描述为D₂＝{(x_i,y_i)|1≤i≤m}，其中x_i代表资源，y_i代表资源添加的标签,其中x_i＝[ulr,des_bm,title,des_bt]代表资源i具有的4维特征向量，将具有相同特征属性值的数据进行数字化处理，y_i∈Y，Y＝{label1,label2,label3}代表为资源可能添加的q个标签，其中取值1代表资源被添加该标签，0表示资源目前没有被添加该标签，以其中几个数据为例，抽取的资源标签数据集D₂如下表1所示。

表1.资源标签数据子集D₂

一、构造基于资源的多标签随机游走模型。

1、构造多标签随机游走图系列，具体步骤为：

(1)将数据集D₂中的每个数据x_i映射为一个点，如果两个资源数据有相同的标签，则将这两个数据对应的点相连，由D₂生成多标签随机游走图G_D＝(V,E)，其中V＝{x_i|(x_i,y_i)∈D,1≤i≤m}，如图4所示。

(2)为了更准确地描述两个资源之间的关系，对于任意资源节点，在所有的邻居节点中，如果一个节点与该资源相关性越小，游走到这个节点的概率越低，基于该思想，计算转移矩阵P，对于任意的其中dis(x_i,x_j)为资源的欧氏距离

(3)对d维输入空间的资源标签训练数据集D₂和预测资源x＝[1,0,2,1,4]，定义由训练集D₂和预测资源x生成的多标签随机游走图系列为G_D,x＝{G_Di|D_i＝D∪{(x,{λ_i})},1≤i≤q},其中G_D,x是建立在D∪{(x,{λ_i})}上的一个多标签随机游走图，如图5所示。

(4)随机游走模型的初始化。随机游走模型的公式为S＝(1-α)·P^T·S₀+α·d，初始化多标签随机游走模型由邻接矩阵P、初始概率分布向量S₀、跳转发生概率α、发生跳转时跳转到图中每个节点的概率分布向量d四个参数。其中邻接矩阵P由步骤1.1.1可得，初始概率分布向量S₀表示随机游走初始时的相似度分布，假设初始时资源与其它节点的相似度为0，则S₀＝(1,0,0,0,0,0,0)^T，对于跳转发生概率α一般设置为0.15，假定待分样本以等概率跳转到图中任一节点，则d＝(1/7,1/7,1/7,1/7,1/7,1/7,1/7)。

2、基于条件概率模型，获得预测资源的推荐标签概率向量，具体步骤为：

(1)对于随机游走图系列G_D,x中的任一子图表示子图节点具有标签λ_j，以标签label1为例，应用随机游走模型得到预测资源x与具有标签label1子图的节点相连时，以x为起点游走到每个节点的稳定概率分布，该条件概率表示为P(x_i|x∈label1)＝S(i),1≤i≤m，其中x_i代表标签label1图的任意一点，S(i)表示向量S的第i个元素，m表示训练集中的资源个数。

(2)求S向量中m个元素的平均值为预测资源游走到标签label1的平均条件概率p(label1∈y_x|x∈label1)＝avg{p(x_i|x∈label1)|label1∈y_i}，y_x代表预测资源具有的标签，y_i代表可能的添加的标签。

(3)预测资源x具有标签label1的平均概率p(x∈label1)＝avg(dis(x,x_i)}，其中x_i表示在随机游走label1子图的任意节点。

(4)根据条件概率模型，预测资源x具有标签label1的概率表示为

(5)其他标签的计算方法与label1标签相同，获得预测资源的预测标签概率向量表示为p_x＝{p(label1),p(label2),p(label3)}，该概率向量刻画了预测资源x属于不同标签的可能性大小。

二、设计以标签共现率、用户相似度为边特征函数和标签预测概率为点特征函数的条件随机场，具体步骤为：

1、构造边特征函数。条件随机场的边特征函数又称状态转移函数，基于标签共现率的边特征函数计算公式为其中f_ij表示标签labeli、labelj在D₂中同时出现的次数，min(f_i,f_j)表示标签labeli、labelj出现次数的最小值。基于用户相似度的边特征函数为其中g_ij表示标签labeli、labelj在D₁中同时出现的次数，min(g_i,g_j)表示标签labeli、labelj出现次数的最小值。

2、构造节点特征函数。依据预测标签概率向量中各标签的概率值构建条件随机场的点特征函数，点特征函数定义为ψ(λ_i)＝1/(1+e^-p(labeli))，1≤i≤3，其中p(labeli)表示预测资源x被预测属于标签labeli的概率。

3、在给定输入序列x的情况下，计算输出序列y的条件概率为其中，Z(x)是规范因子，ζ_ij(λ_i,λ_j,x)，ψ_i(λi,x)分别代表节点i,j的边特征函数和节点i的点特征函数，该特征函数可以形象地刻画节点和节点之间的依赖关系，θ＝(θ¹,θ²,θ³)为特征函数的特征参数值。

三、估计资源的条件随机场的参数，具体步骤为：

估计资源的条件随机场的参数θ＝(θ¹,θ²,θ³)，采用极大似然估计，将参数θ的似然函数写成其中m为训练样本中资源的数量，对似然函数进行求导，使得导数为零。

四、基于条件随机场的资源的标签推荐。具体步骤为：

1、在获得参数估计的基础上，为了求得最佳的输出标签预测概率向量，将问题转化为在给定条件随机场和输入p(y|x)向量_px＝{p(label1),p(label2),p(label3)}的条件下，求条件概率最大的输出序列，输出概率向量具体步骤为：

(1)初始化标签的概率，另φ(1,λ_j)＝1；

(2)对于2≤i≤q,其中i代表状态，所有的标签labelj，其中1≤j≤q，计算

(3)计算标签概率，对于i＝q-1至i＝1，p(labeli)＝ψ(i+1,λ_(i+1))。

2、获得最终资源的标签预测概率向量p_x＝{p(label1),p(label2),p(label3)}，将标签按照概率的大小排序，选择前2个标签作为资源的预测标签。

综上，本发明的一种基于随机游走和条件随机场的社会标签推荐方法，标签推荐数据经过数据抽取，抽取出用户标签、资源标签数据；利用基于随机游走的多标签分类算法预测资源可能被标记的标签概率，该过程有效利用资源本身具有的特征，降低了因用户标注导致的标签噪声的影响；以预测资源可能被标记的标签概率设计点特征函数，标签共现率、用户相似度设计边特征函数，构造条件随机场，获得用户为资源可能添加的标签，选择大于阈值的标签作为推荐标签，该过程有效利用用户、资源、标签三维关系，降低了因将社会标签推荐三维关系转化为二维关系造成的有效信息的损失。本发明提出的社会标签推荐方法，有效利用标签、资源特征构造的点特征函数和用户、资源、标签构造的边特征函数，提高了标签推荐的质量，帮助用户更好的查找和定位社会资源。

以上所述是本发明的优选实施方式，应当指出，对于本技术领域的普通技术人员来说，在不脱离本发明所述原理的前提下，还可以进行多种变化、修改、替换和变型，均应视为本发明的保护范围。