一种基于技能贡献值的网络团队自动组建方法

技术领域

本发明涉及社区问答系统技术领域，特别是涉及一种基于技能贡献值的网络团队自动组 建方法。

背景技术

作为一种知识共享的模式，社区问答系统(CQA)具有交互性和开放性的特点，能够更好 的为用户提供个性化的信息服务，因而人们越来越习惯在社区问答系统网站中进行问答操作。 据有效统计，从2006年到2008年，全球社区问答系统网站的用户量增长了800%。截至到 2013年3月，作为中文社区问答系统平台的百度知道已经收录了五亿多条解决问题 (http://www.baidu.com)。同时，腾讯旗下的搜搜问问已收录2亿多条已解决问题，同时在线用 户数达到70多万(http://wenwen.soso.com)。由此可见，社区问答系统发展的迅猛趋势以及人 们对社区问答系统的依赖程度。

日益增长的用户和数据资源也为CQA的研究提出了新的挑战，现在存在的一种困境就是 当用户提出的某个问题涉及到多个方面的专业知识领域的时候，单凭单个用户很难给出高质 量的解答。针对这种现象，团队组建能够很好的解决这一难题，也就是说当用户提出一个复 杂的问题时，系统根据该问题所需要的技能去到各个领域寻找专家，并将其组成一个专家团 队来进行问题作答，这样该团队就能对该问题所需要的技能完成覆盖，从而给出高质量的答 案。因此，团队组建是一个很有现实意义的研究点，本发明的重点在于如何组建团队并保证 团队的消耗较小，同时团队的技能质量较高。

对于社交网络中的团队组建问题的研究，国内目前没有成果发表，而国际上已经有一些 学者有所建树，所以在这个研究方向上国内的学者起步较晚。国际上的代表主要有：2009年 KDD的文章《Finding a team of experts in social networks》【1】，首次将团队组建引入到了社 交网络中，具有里程碑的意义，同时这篇文章中提到了在团队组建的过程中通过考虑团队成 员间的合作代价，希望以此增加团队合作的效率；2012年WWW的文章《Online Team  Formation in Social Networks》【2】，也是一篇较有影响力的文章，作者在【1】的基础上引入 了负载均衡这一因素，希望通过平衡团队成员的工作量来达到增加团队工作效率的效果。【1】 【2】这两篇文章是社交网络中团队组建问题研究的代表，这两篇文章的贡献不容小觑，但是 仍然为后来的研究者留下了待完善的方面。

【1】【2】都是通过提高团队的工作效率来达到给出高质量答案，没有从根本上提高问题 的作答质量。如何使得一个团队能给出高质量的答案呢，保证每个成员各自贡献的技能在相 应领域内的权威是一个有效的方式。在【1】【2】的研究中，学者们对成员技能的度量采用的 是0-1的方式，即某个人要么完全掌握了某技能，要么完全不会某技能，这显然是不切合实 际的。

从工程上来说，调研了一些国内外的社区问答系统，如百度知道、搜搜问问、雅虎知识 堂，发现这些问答系统均不具备团队组建的功能，即使出现“团队”字样的“百度团队”，也不 是研究意义上的团队，在本发明的研究中团队是希望成员能协同工作，各显所长，最后来完 成某个任务，而不是像“百度团队”为一些有共同兴趣爱好的人提供一个交互的平台。

总的来说，社区问答系统的团队组建问题研究在国内外都是一个比较新的研究点，而如 何提高团队的作答质量更是一个值得深入研究的问题。

发明内容

本发明的目的是提供一种基于技能贡献值的团队组建方法，该方法适用于社区问答系统， 能够有效的应对复杂问题无法得到很好解决的难题。

本发明的技术方案为一种基于技能贡献值的网络团队自动组建方法，包括以下步骤：

步骤1，进行问题建模过程，设待求解的问题T中涉及的任一技能记为s_i，i的取值为 1,2,…,m，m为问题T中涉及的技能数目；原始社区网络G0中的n个节点X₁,X₂,…X_n构成 点集X0＝{X₁,X₂,…X_n}，其中每个节点X_j表示一个用户，j的取值为1,2,…,n，点与点之间 的连线构成边集E0，边上的权重为相应两个用户的合作次数；所述问题建模过程包括以下子 步骤，

步骤1.1，根据贡献值过滤点集X0中与目标问题T中所涉及技能s_i无关的节点，得到集合X， 集合X中任一节点记为X_q；初始的社区网络G0中去掉相应无关的节点和边以后，得到网络 G；

步骤1.2，对步骤1.1所得集合X中每个用户X_q计算在技能s_i上的技能代价其中， cl_qi表示用户X_q在技能s_i上的贡献等级，所述贡献等级根据贡献值及采纳率划分；

步骤1.3，设用户X_q参与合作的总次数为cn_q，用户X_p参与合作的总次数为cn_p，用户X_q与 用户X_p的合作次数为cn_qp，计算集合X中用户X_q与用户X_p之间的合作代价 ${\mathrm{CC}}_{\mathrm{qp}}=1-\frac{{\mathrm{cn}}_{\mathrm{qp}}}{{\mathrm{cn}}_q+{\mathrm{cn}}_p-{\mathrm{cn}}_{\mathrm{qp}}};$

步骤2，进行团队组建过程，包括以下子步骤，

步骤2.1，扩展网络G为G′，包括以下子步骤，

步骤2.1.1，为问题T的每一个技能s_i创建一个技能节点Y_i，这些扩展的技能节点构成点 集Y；

步骤2.1.2，当用户X_q在技能s_i上的技能代价SC_qi不为1时，在X_q与Y_i间扩展一条技能 边；

步骤2.1.3，设Y_i到X_q的权重为SC_qi，X_q到Y_i的权重为极大值∞，将各用户间的合作次 数替换为合作代价CC_qp；

步骤2.2，采用斯坦纳树算法，求出一个初步结果集合X_h，包括以下子步骤，

步骤2.2.1，初步结果集合X_h初始化为空集，随机取点集Y中一个节点记为v，将节点v 从点集Y中取出加入初步结果集合X_h中；

步骤2.2.2，定义集合Y与集合X_h的差集Y/X_h，重复以下子步骤直到Y/X_h为空， 步骤2.2.2.1，求Y/X_h中到集合X_h的距离最小的节点v，将节点v从点集Y中取出加入初步结 果集合X_h中；

步骤2.2.2.2，如果G′中存在v到X_h的路径Path(v,X_h)，则将路径Path(v,X_h)上所经过的所有 节点加入到X_h中，然后返回步骤2.2.2.1；否则，返回失败，团队组建结束；

所述路径Path(v,X_h)的定义如下，

假设X_h中到点v的距离最小的点为u，则Path(v,X_h)表示点v到点u的最短路径；

两点间的距离定义为，两点之间的最短路径的长度，长度是最短路径上的权重值之和； 步骤2.3，去除X_h中所有的技能节点，所得子集X′为结果。

而且，根据贡献值过滤点集X0中与目标问题T中所涉及技能s_i无关的节点实现方式为， 对每个用户X_j，如果其对问题T中的各技能的贡献值均为零则过滤掉，否则留下。

本发明通过将合作代价赋值给用户节点之间的合作边，使得合作代价成为优化目标之一； 同时，在网络图中为每个相关技能构建节点并扩展技能边，使得技能代价也在考虑的范围之 内。由于同时优化了合作代价和技能代价，本发明针对社区问答系统中出现的复杂问题能快 速的组建出高效且高质量的专家团队。相比现有技术，本发明提出了基于技能贡献值的团队 自动组建方式，通过统计用户过去在某一技能上的作答历史来决定是否由该用户完成这个技 能，显然相对于某些由用户自己定义其技能值的方式更客观，并且建立过程高效智能化，无 需人工参与。

附图说明

图1是本发明实施例中所涉及的社会网络图。

图2是本发明实施例中过滤掉无关节点后的社会网络图。

图3是本发明实施例中针对图2抽象出来的合作网络图。

图4是本发明实施例中扩展技能节点和技能代价后的网络图。

具体实施方式

本发明提供一种应对社区问答系统中出现的涉及多个专业知识领域的复杂问题的技术方 案。本发明同时考虑了社区中用户间的合作关系和技能贡献值，将用户间的合作代价反映到 网络图中，同时通过扩展网络图，将复杂问题所涉及的技能和用户在各项技能上的技能代价 在网络图中展现。

下面结合实施例及附图对本发明作进一步说明。

实施例包括问题建模过程和团队组建过程。

步骤1，进行问题建模过程，对于预组建团队的社区网络G0，G0中的n个节点 X₁,X₂,…X_n构成点集X0＝{X₁,X₂,…X_n}，其中每个节点X_j表示一个用户，j的取值为 1,2,…,n，点与点之间的连线构成边集E0，边上的权重即为相应两个用户的合作次数，所述 网络即用G0(X0,E0)表示；G0中涉及到多个技能，目标问题T中涉及的技能一般是其中若 干，设记为s₁,s₂,…,s_m，其中任一技能记为s_i，i的取值为1,2,…,m，m为问题T中涉及的技 能数目。

如图1所示某问题所涉及的社会网络图中的用户节点用X_j标识，即n=11，j的取值为 1,2,…,11，节点间的连线表示用户间的合作关系，边上的数值为权重。且图中为每个用户标 识出了其所拥有的技能；用T表示上述所提出的复杂问题示例，分别用s₁,s₂,s₃,s₄标识T中 所涉及的四个技能（如传播学、预防学、病毒学和免疫学），即m=4，i的取值为1,2,3,4。

步骤1.1，过滤无关的节点。对于每个用户X_j，如果其所有涉及T中的相关技能的贡献 值均为零则过滤掉，否则留下；过滤掉点集X0中的无用节点后，剩下的节点构成集合X。X 中任一节点记为X_q，q的取值与步骤1.1的过滤结果有关，一般为{1,2,…,n}的子集。如图2 中q的取值为1,2,…,6。初始的社区网络G0中去掉相应无关节点和边以后，得到网络G。

针对步骤1.1中的贡献值及下面涉及到的贡献等级，做详细说明。为了标识用户在各个 技能上的贡献程度，本发明给出了贡献值这一概念。在具体的实施中，贡献值可采用社区系 统常用的经验值，还可以由本领域技术人员预设贡献等级划分规则来量化用户在各技能上的 贡献程度。例如，技能贡献值为零的用户其相应技能的贡献等级为1，通过调研常用的商业 问答系统，预先定义的贡献值等级策略如下表1所示。

表1：

也就是说，要得到一个用户在某一技能上的贡献等级，同时需要经验值和采纳率来共同 判断，在一般的社区问答系统中均有经验值和采纳率的评估策略，这里不再详述。

在具体实施中，此处可采用倒排索引的方法，即为每个技能s_i建立索引，求出其支持集 合support(s_i)（即拥有该技能的用户集合）。如图1，有support(s₁)＝{X₁,X₂}， support(s₂)＝{X₃}，support(s₃)＝{X₃,X₅}，support(s₄)＝{X₄,X₅,X₆}。

从社会网络中去掉不在∪support(s_i)中的用户和相关边。针对图1，有 support(s_i)＝{X₁,X₂,X₃,X₄,X₅,X₆}，去掉{X₇,X₈,X₉,X₁₀,X₁₁}和相关边后剩下的网络 如图2所示。

步骤1.2，构建技能代价矩阵。对于集合X中每个用户X_q，从预先建立的数据库中读取 该用户在技能s_i上的贡献等级cl_qi，定义用户X_q在技能s_i上的技能代价为构建技 能代价矩阵SC。具体实施时，可以预先根据贡献值划分每个用户在各个技能上的贡献等级， 构建数据库。

对于图2中的每个节点X_q，首先从数据库中读取该用户在各个技能s_i∈{s₁,s₂,s₃,s₄}上的 贡献等级cl_qi，图中各用户在各技能上的贡献等级如表2所示技能贡献等级矩阵；由于技能代 价SC_qi定义为贡献等级cl_qi的倒数，所以经过求解后，图2中各用户节点构成的技能代价矩阵 如表3所示。

在具体实施的过程中，可假设每个用户涉及所有技能的初始技能贡献等级都为1，所以 对于贡献等级为1的技能，认为该用户当前在该技能上未做出任何贡献，不拥有该技能。

表2

表3

步骤1.3，构建合作代价矩阵。从预先建立的数据库中读取集合X中各用户间的合作次 数，然后根据现有技术中的Jaccard距离公式计算出各用户间的合作代价，构建合作代价矩阵 CC。如，用户X_q参与合作的总次数为cn_q，用户X_p参与合作的次数为cn_p，用户X_q与用户X_p的合作次数为cn_qp，则用户X_q与用户X_p之间的合作代价为其中， q的取值范围和p的取值范围相同，q≠p。

对于图2中的社会网络图，将其抽象为图3所示用户间合作代价矩阵，并为各边加上权 重（即用户间的合作次数）；采用J氏系数计算各用户间的合作代价，构建合作代价矩阵CC。

例如，图中节点X₂共参与合作的次数为1+2+3+5＝11，X₄共参与合作的次数为 5+1+2+2+3＝13，根据J氏系数求得X₂与X₄的合作代价为类似此法， 求出各用户间的合作代价如表4所示。需要说明的是，对于未连接的节点之间的合作代价， 此处定义为一个极大值，用符号∞标识。

表4

步骤2，所述团队组建过程，针对步骤1中所述网络G和待求解问题T，具体的组建过 程如下：

步骤2.1，扩展网络G为G′。对于T中涉及的每个技能s_i创建一个技能节点Y_i。这样所 有的扩展节点构成点集Y。如果用户X_q在技能s_i上的技能贡献等级不为1，则连接X_q与Y_i， 并为该技能边加上双重权重，具体做法为：Y_i到X_q的权重为SC_qi，X_q到Y_i的权重为极大值∞。

实施例采用以下子步骤：

步骤2.1.1，扩展技能节点。为问题T的每一个相关技能s_i创建一个技能节点Y_i，这些扩 展的技能节点构成点集Y。

步骤2.1.2，扩展技能边。根据步骤1.2所求解的技能代价矩阵，当用户X_q在技能s_i上的 技能代价SC_qi不为1时，则在X_q与Y_i间扩展一条技能边。例如，用户X₁在技能s₁上的技能代 价为0.5，则在X₁与Y₁间扩展一条技能边。

步骤2.1.3，为技能边赋权重。根据步骤1.2所求解的技能代价矩阵，用户X_q在技能s_i上 的技能代价即为SC_qi，赋权重的方式为设Y_i到X_q的权重为SC_qi，X_q到Y_i的权重为极大值∞。 例如，为上述步骤1.2中的X₁与Y₁间的技能边赋权重0.5。

同时，根据步骤1.3所求解的合作代价矩阵，将各用户间的合作次数替换为合作代价， 图3的扩展图如图4所示。

步骤2.2，采用斯坦纳树算法，求出一个初步结果集合X_h，斯坦纳树算法的实现过程如 下：

步骤2.2.1，初步结果集合X_h初始化为空集，随机取点集Y中一个节点记为v，将节点v 从点集Y中取出加入初步结果集合X_h中；

步骤2.2.2，定义集合Y与集合X_h的差集Y/X_h，重复以下子步骤直到Y/X_h为空，

步骤2.2.2.1，求Y/X_h中到集合X_h的距离最小的节点v，将节点v从点集Y中取出加入初步结 果集合X_h中；

步骤2.2.2.2，如果G′中存在v到X_h的路径Path(v,X_h)，则将路径Path(v,X_h)上所经过的所有 节点加入到X_h中；否则，返回失败，团队组建结束。执行步骤2.2.2.2后返回步骤2.2.2.1。

所述路径Path(v,X_h)的定义如下，

假设X_h中到点v的距离最小的点为u，则Path(v,X_h)表示点v到点u的最短路径。

两点间的距离定义为，两点之间的最短路径的长度，长度是最短路径上的权重值之和。

对图4，步骤2.2具体执行步骤为：

步骤a，假设随机从Y中取的节点为Y₁，即此时X_h＝{Y₁}，Y/X_h＝{Y₂,Y₃,Y₄}。

步骤b，分别计算Y/X_h中各节点到X_h的距离，即Y₂Y₃Y₄分别到Y₁的距离，分别为0.90+∞、 1.23+∞、0.99+∞，此时距离最小的路径为Y₂到Y₁的路径{Y₂,X₃,X₂,Y₁}。此时 X_h＝{Y₁,Y₂,X₂,X₃}，Y/X_h＝{Y₃,Y₄}。

步骤c，继续计算Y/X_h中各节点到X_h的距离，即Y₃Y₄分别到X_h的距离，分别为0.5、0.99， 选择距离最小的路径{Y₃,X₃}。此时X_h＝{Y₁,Y₂,Y₃,X₂,X₃}，Y/X_h＝{Y₄}。

步骤d，最后就剩下Y₄到X_h的距离，最短距离为0.99，即{Y₄,X₄,X₂}。此时 X_h＝{Y₁,Y₂,Y₃,Y₄,X₂,X₃,X₄}，Y/X_h＝Φ。

步骤2.3，去除X_h中多余的节点。针对所述步骤2.2中的子集X_h，去除所有的技能节点 （即来自点集的Y节点），所得子集X′即为所求。

例如从X_h＝{Y₁,Y₂,Y₃,X₂,X₃}中去除多余的节点，最后X′＝{X₂,X₃,X₄}。

本文中所描述的具体实施例仅仅是对本发明精神作举例说明。本发明所属技术领域的技 术人员可以对所描述的具体实施例做各种各样的修改或补充或采用类似的方式替代，但并不 会偏离本发明的精神或者超越所附权利要求书所定义的范围。