微博中用户间潜在关注关系的发现方法及装置

技术领域

本发明涉及网络数据挖掘领域，特别涉及一种微博中用户间潜在关注 关系的发现方法及装置。

背景技术

微博是一种互联网应用服务，它利用无线网络、有线网络、通信技术 等进行即时通讯，允许用户将自己的最新动态和想法以短信形式发送给手 机和个性化网站群，而不仅仅是发送给个人。与一般的社交网络不同的是， 微博对每次发送的消息长度进行了限制，从而降低了对用户语言编排组织 的要求，之言片语的内容也方便用户及时更新自己的个人信息。在微博中， 用户间的关系可分为两种，一种是显式的关系，即好友间的关注关系，一 种是隐式关系，如好友间转发消息，回复消息等。目前，如何通过获取的 微博中的消息和用户间的关注关系，来发现用户间潜在的关注关系，已是 研究者们非常感兴趣的问题之一。

现有的发现用户间潜在关注关系的方法多是通过用户间的链接关系 （即关注关系）来得到用户的关注关系图，然后根据图的结构，采用计算 最优路径的方式分析用户的潜在好友关系。此外，非负矩阵分解目前也是 数据挖掘领域中非常流行的一种技术，通过非负矩阵分解来计算用户间潜 在关注关系效率比较高且适于处理大量数据。然而，这些潜在关注关系的 发现方法通常只考虑微博中用户间连边的结构信息，即显式的关注关系， 而没利用用户间的互动行为（或称交互行为），使得通过现有技术发现用 户间潜在关注关系的结果误差比较大。

发明内容

根据本发明一个实施例，提供一种微博中用户间潜在关注关系的发现 方法，包括：

步骤1）、根据用户集和用户间关注关系集构建用户关注关系矩阵R， 其中用户集中的用户包括目标用户和候选用户，矩阵R中的每个元素R_ij表 示第i个用户对第j个用户的关注度；

步骤2）、计算矩阵R的两个非负分解矩阵A和B，其中，矩阵A和 矩阵B用于刻画用户间关注关系和交互行为对用户间潜在关注关系的影 响；

步骤3）、将矩阵A和矩阵B的乘积与矩阵R相减得到矩阵，从矩 阵中挑出所有目标用户对应行与所有候选用户对应列的位置的所有元 素，得到目标用户的潜在关注关系矩阵R^*，其中矩阵R^*的每个元素表 示第i’个目标用户对第j’个候选用户的潜在关注度。

在一个实施例中，步骤1）中，当第i个用户关注第j个用户时R_ij=1，否 则R_ij=0。

在一个实施例中，用户集中的用户还包括中间用户，其中，中间用户 包括目标用户关注的用户以及关注目标用户的用户；候选用户包括中间用 户集中的中间用户关注的用户以及关注中间用户的用户。

在进一步的实施例中，步骤2）中计算矩阵R的两个非负分解矩阵A 和B包括：

步骤21）、初始化矩阵A和矩阵B为任意非负值矩阵，矩阵A和矩阵 B相乘所得的矩阵维度与矩阵R的维度相同；

步骤22）、更新矩阵A和矩阵B，其中，

利用如下公式更新矩阵A中的每个元素：

${a^{\prime }}_{\mathrm{uk}}=a_{\mathrm{uk}}\frac{{\left(\underset{u=1}{\overset{n}{\Sigma }}\underset{k=1}{\overset{K}{\Sigma }}\underset{k^{\prime }=1}{\overset{K}{\Sigma }}{R}_i^f(k,k^{\prime })B^T\right)}_{\mathrm{uk}}-{\lambda }_1{a}_{\mathrm{uk}}}{{\left({\mathrm{ABB}}^T\right)}_{\mathrm{uk}}},$

$-({\lambda }_2\underset{k^{\prime }=1}{\overset{K}{\Sigma }}{W}_u(k,k^{\prime })-{\lambda }_3\underset{k^{\prime }=1}{\overset{K}{\Sigma }}{R}_i^f(k,k^{\prime }))\frac{a_{\mathrm{uk}}(a_{\mathrm{uk}}-a_{u{k}^{\prime }})}{W{\left({\mathrm{ABB}}^T\right)}_{\mathrm{uk}}}$

非负参数λ₁、λ₂和λ₃分别表示平滑系数、结构正则化系数和交互正则 化系数，a_uk表示矩阵A中的元素，n表示矩阵A的行的个数，K表示中间用 户的个数，(k,k')表示中间用户k和k’相对于用户i的交互行为相似度， W_u(k,k')表示中间用户k和k’相对于用户u的结构相似度，W是由W_u(k,k')构成 的中间用户结构相似度矩阵；

利用如下公式更新矩阵B中的每个元素：

${b^{\prime }}_{\mathrm{ki}}=b_{\mathrm{ki}}\frac{{\left(A^T\underset{u=1}{\overset{n}{\Sigma }}\underset{k=1}{\overset{K}{\Sigma }}\underset{k^{\prime }=1}{\overset{K}{\Sigma }}{R}_i^f(k,k^{\prime })\right)}_{\mathrm{ki}}-{\lambda }_1{b}_{\mathrm{ki}}}{{\left(A^T\mathrm{AB}\right)}_{\mathrm{ki}}}$

$-{\lambda }_2{b}_{\mathrm{ki}}\frac{\underset{j=1}{\overset{m}{\Sigma }}{W}_k(i,j)(b_{\mathrm{ki}}-b_{\mathrm{kj}})}{W^{\prime }{\left(A^T\mathrm{AB}\right)}_{\mathrm{ki}}},$

b_ki表示矩阵B中的元素，m表示矩阵B的列的个数，W_k(i,j)是用户i和j 相对于中间用户k的结构相似度，W’是由W_k(i,j)构成的候选用户结构相似度 矩阵；

步骤23）、计算更新后的矩阵A和更新后的矩阵B的乘积R'=AB，利 用如下公式计算矩阵R’与矩阵R之间的误差：

$\mathrm{rmse}=\sqrt{\frac{\underset{u=1}{\overset{n}{\Sigma }}\underset{i=1}{\overset{m}{\Sigma }}{(r_{\mathrm{ui}}-{\hat{r}}_{\mathrm{ui}})}^2}{\mathrm{mn}}},$

其中，r_ui表示矩阵R中的元素，表示矩阵R’中的元素，

如果误差rmse小于预定阈值，则输出更新后的矩阵A和矩阵B；

否则，调整参数λ₁、λ₂和λ₃，返回步骤22）。

在进一步的实施例中，当用户i为候选用户并且中间用户k和k’都转 发了用户i发布的消息时，(k,k')为1，否则为0。当用户u为目标用户， 并且中间用户k和k’同时关注用户u或用户u同时关注中间用户k和k’时， W_u(k,k')为1，否则为0。当用户i和j为候选用户，并且用户i和j同时关 注中间用户k或中间用户k同时关注用户i和j时，W_k(i,j)为1，否则为0。

在一个实施例中，所述方法还包括：

步骤4）将矩阵R^*的每一行按元素值由大到小进行排序，得到每个目 标用户的、按潜在关注度大小排序的潜在关注用户列表。

根据本发明的一个实施例，还提供一种微博中用户间潜在关注关系的 发现装置，包括：输入装置和计算装置。其中输入装置用于输入用户集、 用户间关注关系集和一段时间内用户间交互行为集，用户集中的用户包括 目标用户和候选用户；计算装置用于根据用户集和用户间关注关系集构建 用户关注关系矩阵R，根据一段时间内用户间交互行为集计算矩阵R的两 个非负分解矩阵A和B，根据矩阵A和矩阵B的乘积与矩阵R相减得到的 矩阵，从矩阵中挑出所有目标用户对应行与所有候选用户对应列的位 置的所有元素，得到目标用户的潜在关注关系矩阵R^*。

在一个实施例中，所述计算装置还用于将矩阵R^*的每一行按元素值由 大到小进行排序，得到每个目标用户的、按潜在关注度大小排序的潜在关 注用户列表。

采用本发明可以达到如下有益效果：

本发明考虑用户间连边的结构信息和用户间交互行为信息来发现用 户间潜在关注关系，使得发现用户间潜在关注关系的结果误差率比较低。

附图说明

图1是根据本发明一个实施例的微博中用户间潜在关注关系的发现方 法的流程图；

图2是根据本发明一个实施例的用户关注关系矩阵的示意图；

图3是根据本发明一个实施例的用户交互行为矩阵的示意图；

图4是根据本发明一个实施例的用户关注关系图；

图5是根据本发明一个实施例的用户相似度矩阵的示意图；

图6是根据本发明一个实施例的用于计算用户关注关系矩阵的两个非 负分解矩阵的方法的流程图。

具体实施方式

下面结合附图和具体实施方式对本发明进行详细说明。

根据本发明的一个实施例，提供一种微博中用户间潜在关注关系的发 现方法。该方法适用于提供基本功能的微博，并考虑了用户间连边（即关 注行为）及交互行为。

首先对微博所提供的基本功能进行描述：用户之间的关注关系包含关 注和被关注；消息功能包括消息的发送、评论和转发。由于用户通常通过 私信来发送消息使该行为难以追踪，且用户评论往往反映用户对话题的兴 趣而不能准确反映用户之间的关系。因而，相比发送和评论，转发消息这 种交互行为则能较准确地体现用户间的关系（例如，用户间有相同的兴趣 爱好等）。如没有特别说明，本发明的交互行为主要指用户间消息的转发。 图1示出了微博中用户间潜在关注关系的发现方法的一个实施例，具体包 括以下五个步骤：

步骤S101、建立用户关注关系矩阵R和用户交互行为矩阵R^f。

该步骤的输入可包括：用户集、用户间关注关系集和一段时间Δt内用 户间交互行为集，在一个实施例中，用户间交互行为集体现了一段时间Δt 内用户间转发消息的行为。

可根据输入的用户集和用户间关注关系集来构建用户关注关系矩阵 R。图2示出了用户关注关系矩阵R的一个示例，在矩阵R中，R_ij为矩阵中 的元素，用于描述第i个用户对第j个用户的关注度。在一个实施例中，R_ij=1 表示第i个用户（矩阵中的行节点i）关注第j个用户（矩阵中的列节点j）， R_ij=0则表示第i个用户不关注第j个用户。根据用户关注关系矩阵R，可得 到用户关注关系图。该用户关注关系图是有向图，图中的节点表示用户， 边表示用户间的关注关系，边的方向表示用户的关注方向。在下文中，用 户有时也称为节点。

除了用户关注关系矩阵，依据输入的用户集和一段时间Δt内的用户间 交互行为集，还可以建立一段时间Δt内的用户交互行为矩阵R^f。图3示出 了用户交互行为矩阵R^f的一个示例，在该实施例中，=1表示第i个用户 在时间段Δt内转发了第j个用户的消息，=0表示第i个用户在时间段Δt内 没有转发第j个用户的消息。该时间段Δt可以是一周或一个月等。

应理解，以上仅以示例为目的描述了用户关注关系矩阵和用户交互行 为矩阵的一种构建方法，这两种矩阵的构建方法不限于此。

步骤S102、对用户关注关系矩阵中的用户进行分类。

在一个实施例中，可将用户分为三类：目标用户、中间用户和候选用 户。按照该分类方法可以分别建立三个集合：目标用户集、中间用户集和 候选用户集。

其中，目标用户表示所指定的、需要发现其潜在关注关系的用户；中 间用户是目标用户集中的目标用户关注的用户，以及关注目标用户的用 户；候选用户是指中间用户集中的中间用户关注的用户，以及关注中间用 户的用户。图4描述了包括这三种用户集合的用户关注关系图的示例，其 中，子图41中包含的节点表示目标用户，子图42中包含的节点表示中间 用户，子图43中包含的节点表示候选用户。

步骤S103、依据步骤S102中用户的分类结果来计算用户相似度。其 中，用户相似度包括中间用户的结构相似度、中间用户的交互行为相似度 和候选用户的结构相似度。中间用户的结构相似度体现了中间用户两两之 间在关注行为上的相似程度；中间用户的交互行为相似度体现了中间用户 在交互行为（转发消息行为）上的相似程度；以及，候选用户的结构相似 度体现了候选用户在关注行为上的相似程度。

根据本发明一个实施例，可采用如下方法计算中间用户的结构相似 度：从目标用户集中选取（任意选取或按一定顺序选取）一个目标用户u， 从中间用户集中任意选取两个中间用户k和k’，参照用户关注关系矩阵R， 若目标用户u同时关注了中间用户k和k’，或者中间用户k和k’同时关注 了目标用户u，则中间用户k和k’相对于目标用户u的结构相似度为1， 否则中间用户k和k’相对于目标用户u的结构相似度为0。计算中间用户 集中所有的中间用户对相对于目标用户集中所有目标用户的结构相似度， 得到中间用户结构相似度矩阵，矩阵形式如图5所示，该中间用户结构相 似度矩阵的行是目标用户，该矩阵的列是中间用户对。

根据本发明一个实施例，可采用如下方法计算候选用户的结构相似 度：从中间用户集中选取（任意选取或按一定顺序选取）一个中间用户k， 从候选用户集中任意选取两个候选用户i和j，参考用户关注关系矩阵R， 若该中间用户k同时关注了候选用户i和j，或候选用户i和j同时关注了 中间用户k，则候选用户i和j相对于中间用户k的结构相似度为1，否则 候选用户i和j相对于中间用户k的结构相似度为0。计算候选用户集中所 有的候选用户对相对于中间用户集中所有中间用户的结构相似度，得到候 选用户结构相似度矩阵，矩阵形式如图5所示，该候选用户结构相似度矩 阵的行是中间用户，所述矩阵的列是候选用户对。

根据本发明一个实施例，可采用如下方法计算中间用户的交互行为相 似度：从候选用户集中任意或以一定顺序选取一候选用户i，从中间用户集 中选取任意两个中间用户k和k’。参考用户交互行为矩阵R^f，若中间用户k 和k’在一段时间内都转发了候选用户i发布的消息，则中间用户k和k’相对于 候选用户i的交互行为相似度为1，否则中间用户k和k’相对于候选用户i的 交互行为相似度为0。计算中间用户集中所有中间用户对相对于候选用户 集中所有候选用户的交互行为相似度，得到中间用户的交互行为相似度矩 阵，所述矩阵形式如图5所示，该中间用户交互行为相似度矩阵的行是候 选用户，该矩阵的列是中间用户对。

这里仅示例性地给出了计算用户相似度的方法，应理解，其他适于度 量用户行为相似度的方法也适用于此。例如，可以采取两个中间用户对候 选用户在一段时间内发布的若干条（如num条）消息的转发情况进行逐条 统计的方式。具体地，对候选用户的每条消息，若中间用户转发了该消息， 则统计取值为1，反之为0。这样得到两个长度为num的中间用户对候选 用户的消息转发向量，根据向量的相似度（如余弦相似度）计算中间用户 的交互行为相似度。

步骤S104、依据步骤S103得到的用户相似度，计算用户关注关系矩 阵R的两个非负分解矩阵A和B。图6示出了该方法的一个实施例的流程 图，其中矩阵A和B是两个低维的代表用户特征的矩阵，称为用户—因子 矩阵（user-factor matrix），构造它们可用于刻画用户的某些隐含特征对用 户间关注关系的影响。不同于现有的只是基于用户间结构信息（关注或被 关注）的矩阵分解，这里经过分解得到的矩阵A和B，还考虑了用户间交 互行为（如转发消息）对用户间潜在关注关系的影响，更符合微博中用户 间关注关系的产生机制。在一个实施例中，可通过乘法迭代更新公式来获 得矩阵A和B，具体步骤如下：

第一步：初始化矩阵A和矩阵B为任意非负值矩阵，使得矩阵A和矩 阵B相乘所得的矩阵的维度与用户关注关系矩阵R的维度相同。同时，初 始化非负参数λ₁、λ₂和λ₃，其中，λ₁是平滑系数，λ₂是结构正则化系数， 而λ₃是交互正则化系数。

第二步：更新矩阵A，包括以下两个步骤：

a）、从矩阵A中任取一个元素a_uk，利用公式（1）计算该元素的更新 值a'_uk。公式（1）中，n表示矩阵A的行的个数，K表示中间用户的个数。 (k,k')表示中间用户k和k’相对于用户i的交互行为相似度，当用户i不 属于候选用户集时，。W_u(k,k')表示中间用户k和k’相对于用户u 的结构相似度，当用户u不属于目标用户集时，W_u(k,k')=0，W是由W_u(k,k') 构成的中间用户结构相似度矩阵。

${a^{\prime }}_{\mathrm{uk}}=a_{\mathrm{uk}}\frac{{\left(\underset{u=1}{\overset{n}{\Sigma }}\underset{k=1}{\overset{K}{\Sigma }}\underset{k^{\prime }=1}{\overset{K}{\Sigma }}{R}_i^f(k,k^{\prime })B^T\right)}_{\mathrm{uk}}-{\lambda }_1{a}_{\mathrm{uk}}}{{\left({\mathrm{ABB}}^T\right)}_{\mathrm{uk}}}$

$-({\lambda }_2\underset{k^{\prime }=1}{\overset{K}{\Sigma }}{W}_u(k,k^{\prime })-{\lambda }_3\underset{k^{\prime }=1}{\overset{K}{\Sigma }}{R}_i^f(k,k^{\prime }))\frac{a_{\mathrm{uk}}(a_{\mathrm{uk}}-a_{u{k}^{\prime }})}{W{\left({\mathrm{ABB}}^T\right)}_{\mathrm{uk}}}$

公式(1)

b）、重复步骤a），直到矩阵A中每一个元素都计算得到对应的更新值， 利用所得到的矩阵A的所有元素更新值来更新矩阵A。

第三步：更新矩阵B，包括以下两个步骤：

c）、从矩阵B任取一个元素b_ki，利用公式（2）计算所述元素的更新 值b'_ki。公式（2）中，m表示矩阵B的列的个数。(k,k')表示中间用户k 和k’相对于用户i的交互行为相似度，当用户i不属于候选用户集时， 。W_k(i,j)是用户i和j相对于中间用户k的结构相似度，当用户i 和j不属于候选用户集时，W_k(i,j)=0。W’是由W_k(i,j)构成的候选用户结构 相似度矩阵。

${b^{\prime }}_{\mathrm{ki}}=b_{\mathrm{ki}}\frac{{\left(A^T\underset{u=1}{\overset{n}{\Sigma }}\underset{k=1}{\overset{K}{\Sigma }}\underset{k^{\prime }=1}{\overset{K}{\Sigma }}{R}_i^f(k,k^{\prime })\right)}_{\mathrm{ki}}-{\lambda }_1{b}_{\mathrm{ki}}}{{\left(A^T\mathrm{AB}\right)}_{\mathrm{ki}}}$

$-{\lambda }_2{b}_{\mathrm{ki}}\frac{\underset{j=1}{\overset{m}{\Sigma }}{W}_k(i,j)(b_{\mathrm{ki}}-b_{\mathrm{kj}})}{W^{\prime }{\left(A^T\mathrm{AB}\right)}_{\mathrm{ki}}}$公式(2)

d）、重复步骤c），直到矩阵B中每一个元素都计算得到对应的更新 值，利用所得到的矩阵B的所有元素更新值更新矩阵B。

第四步：依据更新得到的矩阵A和更新得到的矩阵B，计算更新后的 矩阵A和更新后的矩阵B的乘积R'=AB，然后根据公式（3）计算矩阵R’ 与用户关注关系矩阵R之间的误差：

$\mathrm{rmse}=\sqrt{\frac{\underset{u=1}{\overset{n}{\Sigma }}\underset{i=1}{\overset{m}{\Sigma }}{(r_{\mathrm{ui}}-{\hat{r}}_{\mathrm{ui}})}^2}{\mathrm{mn}}}$公式(3)

其中，r_ui表示用户关注关系矩阵R中的元素，表示矩阵R’中的元素。 若所得误差rmse满足要求（例如，小于某一预定阈值），则输出矩阵A和 矩阵B，否则，调整参数λ₁、λ₂和λ₃，并返回第二步继续更新矩阵A和矩 阵B，直到误差rmse满足要求。

应理解，上述更新矩阵B的过程也可以在更新矩阵A之前进行。

在另一个实施例中，也可以基于梯度下降的减法迭代更新公式来更新 矩阵A和B。

步骤S105、依据步骤S104得到的两个非负分解矩阵A和B，计算用 户关注关系估计矩阵R’，将该用户关注关系估计矩阵与用户关注关系矩阵 R相减，根据所得矩阵输出目标用户集中所有目标用户对应于候选用户集 中候选用户的潜在关注用户列表。在一个实施例中，获得该潜在关注用户 列表的方法具体如下：

将步骤S104计算所得的矩阵A和矩阵B相乘，得到用户关注关系估 计矩阵R’，所述估计矩阵R’与用户关注关系矩阵R相减，得到矩阵。挑 出矩阵中，目标用户集中所有目标用户的对应行和候选用户集中所有候 选用户对应列的位置的所有元素，得到目标用户的潜在关注关系矩阵R^*。 其中目标用户的潜在关注关系矩阵R^*的每个元素表示第i’个目标用户 对第j’个候选用户的潜在关注度（或称关注可能性）。对目标用户的潜在关 注关系矩阵中的第u行按元素值由大到小进行排序，得到第u行对应的目 标用户u的潜在关注用户的排序，则最大元素值的列对应的候选用户是目 标用户u的最大可能潜在关注用户，第二大元素值的列对应的候选用户是 目标用户u的第二大可能潜在关注用户，以此类推。对目标用户的潜在关 注关系矩阵的所有行都进行上述操作，则可得到目标用户集中每一个目标 用户按关注可能性大小排序的潜在关注用户列表。

本领域技术人员应理解，上述步骤S101也可以在步骤S102后进行。

本发明分别采用现有技术和本文描述的微博中用户间潜在关注关系 的发现方法，在真实Twitter数据集上进行了多次实验，实验参数如下：

实验所用的用户关注关系矩阵R是利用Twitter API采集的从2012年10 月1日到2012年11月19日的这一个半月中随机选择的1万个用户及其 关注用户和粉丝用户得到的1万行1万列的矩阵。用户交互行为矩阵R^f是 根据这段时间内用户的转发消息情况生成的1万行1万列矩阵。误差rmse 的阈值设定为0.00001，平滑系数λ₁初始化为0.001，经调整值为0.01，结 构正则化系数λ₂初始化为0.001，经调整值为0.001，交互正则化系数λ₃初 始化为0.001经调整为0.005，中间用户个数为4，矩阵A是1万行4列的 矩阵，矩阵B是4行1万列的矩阵。

经过实验得到如下结果：采用现有技术的误差rmse值为0.102，而采 用本发明提供的微博中用户间潜在关注关系的发现方法所得到的潜在关 注关系结果的误差rmse值仅为0.033。因而采用本发明提供的微博中用户 间潜在关注关系的发现方法比现有技术降低的误差达70%左右，极大地减 少了发现用户间潜在关注关系的结果误差。

根据本发明的一个实施例，本发明提供的微博中用户间潜在关系的发 现方法可使用于具有微博特点的各类网络服务中，例如Twitter、新浪微博 和腾讯微博等社交网络。

根据本发明的一个实施例，还提供一种微博中用户间潜在关注关系的 发现装置，包括输入装置、计算装置。

输入装置，用于输入用户集、用户间关注关系集和一段时间内用户间 交互行为集，其中，用户集中的用户分为目标用户、中间用户和候选用户。

计算装置，用于根据用户集和用户间关注关系集构建用户关注关系矩 阵R，根据一段时间内用户间交互行为集计算用户关注关系矩阵R的两个 非负分解矩阵A和B，根据矩阵A和矩阵B的乘积与用户关注关系矩阵R 相减得到的矩阵，从矩阵中挑出所有目标用户对应行与所有候选用户 对应列的位置的所有元素，得到目标用户的潜在关注关系矩阵R^*，其中矩 阵R^*的每个元素表示第i’个目标用户对第j’个候选用户的潜在关注度。

在一个实施例中，计算装置还用于将矩阵R^*的每一行按元素值由大到 小进行排序，得到每个目标用户的、按潜在关注度大小排序的潜在关注用 户列表。

应该注意到并理解，在不脱离后附的权利要求所要求的本发明的精神 和范围的情况下，能够对上述详细描述的本发明做出各种修改和改进。因 此，要求保护的技术方案的范围不受所给出的任何特定示范教导的限制。