群体计算中的偶图匹配算法
2018-09-26满君丰刘美博
满君丰 刘 鸣 彭 成 刘美博
(湖南工业大学计算机学院智能信息感知及处理技术重点实验室 湖南 株洲 412007)
0 引 言
大数据的复杂性(规模大、形式多样等)给计算机技术带来了冲击，使得计算机单方面的高性能计算能力已无法应对高速增长的数据任务。为了迎接大数据带来的挑战，越来越多的研究者们投入于大数据的研究。大量的研究发现，要想高效地挖掘大数据的潜在价值，需要解决大数据的4V(数据量大、类型繁多、价值密度低、速度时效快)特征，而传统的依赖计算机高性能计算已经无法解决这些问题，需要依靠人群和机群的协作来完成。
在人群与机群协作过程中需要考虑人群与机群的特点，有效地将任务分配给合适的人群和机群。在此过程中提出了许多匹配方法，如传统过程中的随机匹配算法[1]，因其匹配算法的随机性大且具有较大的不稳定性，不适用于对匹配性能有较高要求的匹配情况。暴力匹配算法[2-4]也称为朴素字符串匹配算法，该算法适用于同种事物间的匹配(即查询匹配)，无法适用于关联性匹配问题。文献[5]设计了人机合作的智能系统，但该系统以人为主，并未平衡人与计算机的关系。天梯匹配算法[6]，能同时匹配的人群与任务量一般不会超过1万，否则其性能会直线下降，因此不适用于大数据环境下的人机协作。人群和机群协作中必然涉及到任务的匹配问题，我们将任务中涉及计算的部分交给计算机处理，而需要认知推理的部分交给用户，那么如何有效将任务分配给人群是一个亟待解决的问题。
文献[6-7]提出了人群和机群协作的构想，理性地分析了机群和人群的特点，综合了机群的计算能力和人类大脑的认知推理能力，使人群和机群通过协作完成大数据环境下的复杂任务[8]。本文深受该构想的启发，提出了人群与任务的偶图匹配算法。
人机协作中任务分配算法主要由图1中几个模块构成，任务建模、质量评估模块和任务发布/收集模块之间相辅相成。任务发布/收集模块用于发布任务和收集任务反馈的结果，切割机制将任务自适应切割成多个子任务，并用匹配机制将任务匹配给人群。针对匹配机制中的算法匹配问题，我们提出的偶图匹配算法很好地解决了任务随机匹配带来的盲目性和随机性[9]。偶图[10]是计算机科学家Robin Milner提出的一种在图形基础上的形式化理论模型，这个模型被提出的目的是为普适计算提供一个平台[11]。偶图应用十分广泛，如元素的查找、树和图的遍历等，其也适用于人机协作中任务与人群的匹配[12]。
图1 偶图匹配算法的整体结构
将可信度评估较好的人群和自适应切割好的任务集看作两种元素集U和V，通过偶图匹配算法寻找U中和V中的匹配点进行最大匹配，甚至是完美匹配，从而将任务分配给合适的人群，最终获得较高质量的反馈结果[13-15]。这种匹配算法比起随机匹配算法虽然增加了一些复杂度，但有效提高任务完成的质量，适合于对专业层次要求较高的复杂任务的分析和解决，可以应用于大数据的挖掘、数据分析、领域知识答疑等领域。对未来的数据传输、大数据处理、感知数据质量等方面有着重要的影响。
1 偶图结构
定义1偶图 又称为“二分图”，即将无向图G
定义2最大匹配和完美匹配 在偶图中，匹配为边的集合，其中任意两条边都不会有公共的顶点，也就是说大型任务被切割成多个小任务后，人群中经过评估后的人只能匹配其中的一个小任务，以提高任务完成的效率。如图2所示，初始时如(a)一样每个用户可以和多个小任务进行匹配，通过偶图匹配算法将具有专业背景和高可信度的用户与相关的任务进行匹配。经过匹配的用户和任务不再和其他用户或任务进行匹配，如(b)中U1和V1进行匹配后，其他与U1和V1关联的边都属于无用边。一个大任务自适应切割后分成的所有小任务的所有匹配中含有匹配边数最多的匹配被称为偶图的最大匹配。如(c)中U集中每个元素都能在V集中找到一个元素与之相关联，最大匹配边数为4，匹配边的两端分别是U集和V集。若可信度评估后参与匹配的用户与自适应切割后的小任务集能够一一对应，即U集和V集中每个元素都是匹配点，则该匹配便称为完美匹配。很显然(c)也是完美匹配。
图2 最大匹配和完美匹配
偶图匹配过程中是根据什么来确保用户和任务之间建立联系，需要我们对任务进行建模。用户经过可信评估后便可以获取用户的专业背景、知识储备能力等。一个任务在自适应分割后会分成许多不同的小任务，这些任务可能属于不同领域，也可能属于类似领域。将具有相同或相似领域的用户和任务进行偶图匹配，用户完成任务的质量还可以作为下一次任务匹配的参照，这样的良性循环会使匹配的效果越来越好。因此建立同种任务切割后的小任务间的关联度是必要的，而任务间的关联度取决于任务所属领域和描述相似度，综合以上两个因素可以推出：
TS=θ×AS+φ×SS
(1)
式中:系数θ和φ是根据数据集而定的，TS是分割后小任务间的关联度，AS是任务领域相似度，SS是任务描述相似度。AS根据领域的重叠程度取值0、0.5和1。将任务的描述说明抽象成一个集合，而描述说明可以根据关键字、主题等抽象，通过小任务间描述集合的交集来确定SS的大小。如图3所示，Task1与Task4分属于两个不同领域，故它们之间的领域相似度为0。Task3与其他任务间的领域相似度为0.5，以上便构成了图上各边关联度的权重，从而建立起任务间的关系，让任务在偶图匹配中更有效地匹配到与任务关联度高的用户。
图3 任务关联
2 偶图匹配原理
偶图匹配过程中需要考虑两个因素：(1)用户完成任务每次所花费的代价M；(2)用户完成任务后获得的增量值H。偶图将代价M值小的用户优先匹配，而增量值H用于下一次用户与任务进行匹配的附加量，如下所示：
(2)
(3)
增量值H是由两部分构成：(1)用户完成任务所期望的收益量EI(Tx)；(2)用户完成与该任务相同领域和相关联的任务期望收益量EI(RTy)。其中T表示匹配的任务，RT表示与任务T相关联但还没有进行匹配或者未完成的任务。用户所获得的期望随任务的不同而不同，参数φ和ω是由用户量、任务量以及数据集共同决定的。任务花费代价M也是由两部分构成：(1)一个是任务困难因子ax，每个任务的困难程度不一，其困难程度是由该任务所处领域、用户评价和完成量决定的；(2)是用户完成任务的领域因子by，任务有可能只涉及一个领域，也有可能涉及多个领域，从任务分割的角度来看，小任务涉及的领域越少，分割的则越彻底，故by的值与涉及的领域有关。
用户的增量H值是随任务的不同而改变的，我们可以获得用户完成某一具体任务的任务期望收益量一般形式：
(4)
EI(T)表示用户完成某一具体任务T所获得的期望收益量，x表示任务变量，θ表示领域范围。而pr(x|θ)表示用户完成的任务质量合格概率，合格是任务完成的一个标准，用户所完成的任务质量越高，其pr(x|θ)的值也就越大；pr(x)表示任务本身所给定标准的概率，也就是任务发布者所期望的标准。
偶图匹配算法首先考虑任务情况再进行寻找相匹配的用户，任务在经过自适应切割后，便可以得到各小任务所属领域、任务关联情况，从而能够确定用户群体所处领域和专业背景。经过可信度评估后的人群可以选择相关领域的任务先进行偶图模拟匹配，从而计算出完成任务所需的代价。偶图通过所得代价和用户以往完成相同或同一领域相类似的任务所获得的期望增量值与合适的任务进行匹配，从而提高任务完成质量和效率。
3 偶图匹配算法
在人机协作中的偶图匹配主要用到了Hopcroft-Karp算法，它是匈牙利算法的继承和扩展，故需要先了解匈牙利算法的原理和特点。
定义3交替匹配路 从一个未匹配的用户出发，借助多次的虚拟匹配，依次经过非匹配用户、匹配用户这样循环形成的路径,我们将之称为交替匹配路。
定义4增广匹配路 和交替匹配路相同，从一个未匹配的用户开始，走交替匹配路，除出发点外如果途中遇到另一未匹配点，则将这条特殊的交替匹配路称之为增广匹配路。如图4所示，(a)是用户与任务匹配过程中所走的交替匹配路，而(b)是从(a)中抽取出来的增广匹配路。由V4这个未匹配的用户出发，途径非匹配边、匹配边交替循环，并且中途遇到的点皆是匹配点，直到遇到未匹配点U2形成一条增广匹配路。不难看出在该增广匹配路中非匹配边比匹配边多一条，而这也是增广匹配路的一个重要特点。将匹配边与非匹配边交换，则交替匹配路多出一条匹配边，这样既多出一条匹配边，又不会破坏偶图匹配，而我们研究增广匹配路也是为了改进匹配。
图4 增广匹配路示意图
偶图在匹配过程中会由图匹配转换成树匹配，即匈牙利树。匈牙利树从一个未匹配用户出发，走交替匹配路，进行增广匹配，不断地循环寻找增广匹配路，直到无法找到未匹配点为止。如图5所示，(b)是由(a)转化而得的树，转化得到的树存在一个非匹配的叶子节点7，而匈牙利树要求所有的叶子节点必须是匹配节点，故该树不是匈牙利树。因为节点7是非匹配节点，所以可以将节点7去除，再进行匹配将(a)转化为(c)。除了节点2以外所有节点为匹配节点，以节点2为根节点转化为匈牙利树，类似于广度优先搜索(BFS)树，转化得到的树所有叶子节点均为匹配节点，此刻的匹配达到最大匹配。
图5 匈牙利树
以图5(c)来说明在匈牙利匹配基础上的Hopcroft-Karp算法：
(1) 初始检查，进行虚拟匹配。以节点1为例，在初始化时，获取用户(节点1)的专业背景和擅长领域等信息，发现自适应切割后的小任务(节点7和9)满足匹配条件，记录信息，其他节点也是如此。
(2) 初始匹配。将节点1按照权值等与节点7匹配。
(3) 加入节点3，发现节点3可与节点7和8匹配，按照条件发现节点7更适合，但节点7已经是匹配节点并与节点1进行匹配，找到节点3出发的交替路径3-7-1-9，将交替路上已在匹配上的边1-7去除，剩余的边3-7、1-9加入到匹配边中。
(4) 循环往复处理其他节点即可完成所有匹配。
Hopcroft-Karp算法根据匈牙利算法进行改进所得的算法流程如下：
输入：X={X1,X2,…,Xn}，P={P1,P2,…,Pn}；
输出：Y={
//任务匹配结果键值对
① 获取自动切分后的任务子集：x1,x2,…,xg
② G_Theory(X,P)
// 根据任务集进行人群博弈
③ G_init(X,P)
// 从G=(X,P,E)中取得初始匹配
④ Init_X(X,-1,X.length);
⑤ Init_Y(Y,-1,Y.length);
⑥ G_read(X, Y)
// 读取节点进行匹配
⑦ IF(X.isEmpty)
//所有任务结点获得匹配(完美匹配)，返回
⑧ RUTURN 0
⑨ IF(!X.Empty)
// 非完美匹配进行一次BFS
⑩ G_BFS()
// 标记各点到源点之间的距离
// 从X中找到未被M匹配到的结点x0
// 循环查找满足条件的边集E
// 满足条件dis[x]=dis[v]+1，并做记录S={x0}
// 未匹配节点进行最大匹配
// 重复多次宽度优先遍历
// 无法得到更大匹配，返回；否则取∀y0∈N(S)
//y0被M匹配并转步骤18，否则转步骤19
//获取(y0,z0)，并转步骤6
// 做一条x0→y0的增光路经P(x0,y0)
Hopcroft-Karp算法使用键值对作为输入和输出，数据主要以Text、String类型为主，主要应用于互联网群智计算中，如众包、社会感知任务、城市交通感知与室内定位等。以大量用户参与作为基础和前提，通过合理的协作完成计算机和用户单独不可能完成的复杂任务。如果无法整合大量的互联网用户，则该算法无法成功实施，则匹配也无从谈起。
4 实验结果及分析
为了了解Hopcroft-Karp算法的匹配准确率和匹配效果，分别使用随机匹配算法和匈牙利算法作为参照实验对象。考虑到众包平台不支持偶图匹配算法，所以具体的实验我们只能在线下用仿真迭代实验。下面分别进行了非标准数据测试实验和标准测试实验来检验Hopcroft-Karp算法的效果。
4.1 非标准数据测试
在该实验中，我们采用了三个主题：药品主题、音乐主题和电脑器材主题，三个主题涉及的任务数达到n=1 200，即每个主题有400个任务。假设有90个用户参与该实验，并且每个用户擅长其中1个领域主题，那么用户回答擅长领域主题的准确率服从高斯分布，其准确率从gauss(0.7,0.3)中进行数据采样。
在实验初始时将关联度高的任务自适应切分为低耦合的小任务，由于选择的主题明确，所以不存在领域关联度为0.5，不同背景任务的关联度为0，相同背景任务的关联度为1。在实验中，将任务分成20批次，每批次有60个任务，在任务分发过程中，任务的难度逐渐递减。任务使用随机分配算法、匈牙利算法、Hopcroft-Karp算法分别进行1 000次匹配，收集每次任务完成的情况，最后取其平均准确率。
如图6所示，任务难度按照贝塔分布，其中(a,b)分别取值(2,1)、(4,1)、(7,1)、(10,1),a的值从2至10表示任务难度从难到易。该图纵坐标是实验中任务重复1 000次匹配所取得的平均准确率。从图中可以看出任务按照随机分配，随着任务难度的降低，其平均准确率有所提高，但不明显。随机分配并不考虑任务的领域和背景，也不考虑用户的专业和能力，进行随机匹配，所以任务的难易程度对随机分配影响不大。匈牙利算法和Hopcroft-Karp算法受贝塔分布的影响较大，因为这两个算法需考虑任务的领域和关联情况以及用户的可信评估情况，以此计算用户完成任务所期望的收益量EI(Tx)、增量值和完成任务花费的代价M。所以随着任务难度降低，用户完成任务的收益越大，花费的代价也越小，从而完成任务的平均准确率也会越高。由于Hopcroft-Karp算法是对匈牙利补充和扩展，对其匹配的质量没有太大的影响，再者实验次数多，所以两者的平均准确率基本一致。
图6 三种算法正确率比较
匈牙利算法和Hopcroft-Karp算法匹配质量差不多，我们从两者的匹配效率进行比较。图7是数据量从1 k到10 k递增的情况下两个算法花费的时间之差，左边纵坐标是两个算法(柱状图)花费的时间，右边是两算法时间差(折线图)。从图中可以看出随着数据量的增大，Hopcroft-Karp算法匹配花费的时间比匈牙利算法匹配花费的时间越来越少，适合大数据量情况下的任务匹配，而我们群体计算中人机协作所面向的正是大数据和大人群。
图7 时间复杂度
下面通过某一具体β值来观察用户完成任务的准确率情况。由于匈牙利算法和Hopcroft-Karp算法的平均准确率基本一致，我们就只比较随机分配算法和Hopcroft-Karp算法的平均准确率。图8是从中进行采样，进行20轮任务匹配的情况，从图中可以看出，使用随机分配算法匹配，用户完成任务的准确率平均在40%；使用Hopcroft-Karp算法随着轮数的增加，其平均在准确率是有小幅度的提高的。在第一轮的时候，由于初始无法获得前轮用户完成任务花费的代价M值，所以其平均准确率较低，但其考虑的因素较多，其匹配的准确率也比随机分配的效果要好。在第二轮匹配的时候有了前轮的M值，其平均准确率有较大幅度的提高。因为Hopcroft-Karp具有不断优化的效果，所以随着轮数的增加，其匹配的效果会越好。
图8 β(4,1)对应的任务完成准确率
4.2 标准数据测试
标准数据集来源于infochimps公司(简称IFC)公开数据集http://www.data.gov中的Education数据https://www.data.gov/education/。我们从Education中获取medicines数据集、English数据集、law数据集三种类型的数据集来检验Hopcroft-Karp算法的有效性。对于medicines的数据集，我们收集了药品名称、药品知识问答等相关问题；对于English数据集，我们收集了词汇问题、语法问题以及其他相关英语问题；对于law数据集，我们收集了法律相关知识问答题。每个任务实验3次，对于答案不明确的任务采用投票原则(少数服从多数)。图9是Hopcroft-Karp算法的实验效果图。
图9 主题数据对应的准确率
从图9中可以看出，标准的三种数据集与非标准数据集平均准确率趋势相一致，随机分配算法的效果和人群质量有很大关系。如英语的普及使得随机配算法匹配人群与任务获得的平均准确率相对其他两个数据集获得的平均准确率要高，但由于其随机性，所以获得的平均准确率不是很高。而Hopcroft-Karp算法获得的准确率在90%左右，匹配的效果非常好。
5 结 语
本文提出了基于偶图的人群与任务匹配方法，使用Hopcroft-Karp算法充分考虑了任务的领域和人群的特点，实现了人群与任务之间的高效匹配，提高了任务完成的质量和效率，为人机协作的任务有效分配做出了重要的贡献。在下一步的研究中，我们将会从更多方面考虑人群特点以及任务的划分来提高人群与任务的匹配效果，并以不断提高匹配效率为目标，让人机协作能够迎接更多可变的挑战。
