群體計(jì)算中的偶圖匹配算法

滿(mǎn)君豐 劉 鳴 彭 成 劉美博

(湖南工業(yè)大學(xué)計(jì)算機(jī)學(xué)院智能信息感知及處理技術(shù)重點(diǎn)實(shí)驗(yàn)室 湖南 株洲 412007)

0 引 言

大數(shù)據(jù)的復(fù)雜性(規(guī)模大、形式多樣等)給計(jì)算機(jī)技術(shù)帶來(lái)了沖擊，使得計(jì)算機(jī)單方面的高性能計(jì)算能力已無(wú)法應(yīng)對(duì)高速增長(zhǎng)的數(shù)據(jù)任務(wù)。為了迎接大數(shù)據(jù)帶來(lái)的挑戰(zhàn)，越來(lái)越多的研究者們投入于大數(shù)據(jù)的研究。大量的研究發(fā)現(xiàn)，要想高效地挖掘大數(shù)據(jù)的潛在價(jià)值，需要解決大數(shù)據(jù)的4V(數(shù)據(jù)量大、類(lèi)型繁多、價(jià)值密度低、速度時(shí)效快)特征，而傳統(tǒng)的依賴(lài)計(jì)算機(jī)高性能計(jì)算已經(jīng)無(wú)法解決這些問(wèn)題，需要依靠人群和機(jī)群的協(xié)作來(lái)完成。

在人群與機(jī)群協(xié)作過(guò)程中需要考慮人群與機(jī)群的特點(diǎn)，有效地將任務(wù)分配給合適的人群和機(jī)群。在此過(guò)程中提出了許多匹配方法，如傳統(tǒng)過(guò)程中的隨機(jī)匹配算法[1]，因其匹配算法的隨機(jī)性大且具有較大的不穩(wěn)定性，不適用于對(duì)匹配性能有較高要求的匹配情況。暴力匹配算法[2-4]也稱(chēng)為樸素字符串匹配算法，該算法適用于同種事物間的匹配(即查詢(xún)匹配)，無(wú)法適用于關(guān)聯(lián)性匹配問(wèn)題。文獻(xiàn)[5]設(shè)計(jì)了人機(jī)合作的智能系統(tǒng)，但該系統(tǒng)以人為主，并未平衡人與計(jì)算機(jī)的關(guān)系。天梯匹配算法[6]，能同時(shí)匹配的人群與任務(wù)量一般不會(huì)超過(guò)1萬(wàn)，否則其性能會(huì)直線(xiàn)下降，因此不適用于大數(shù)據(jù)環(huán)境下的人機(jī)協(xié)作。人群和機(jī)群協(xié)作中必然涉及到任務(wù)的匹配問(wèn)題，我們將任務(wù)中涉及計(jì)算的部分交給計(jì)算機(jī)處理，而需要認(rèn)知推理的部分交給用戶(hù)，那么如何有效將任務(wù)分配給人群是一個(gè)亟待解決的問(wèn)題。

文獻(xiàn)[6-7]提出了人群和機(jī)群協(xié)作的構(gòu)想，理性地分析了機(jī)群和人群的特點(diǎn)，綜合了機(jī)群的計(jì)算能力和人類(lèi)大腦的認(rèn)知推理能力，使人群和機(jī)群通過(guò)協(xié)作完成大數(shù)據(jù)環(huán)境下的復(fù)雜任務(wù)[8]。本文深受該構(gòu)想的啟發(fā)，提出了人群與任務(wù)的偶圖匹配算法。

人機(jī)協(xié)作中任務(wù)分配算法主要由圖1中幾個(gè)模塊構(gòu)成，任務(wù)建模、質(zhì)量評(píng)估模塊和任務(wù)發(fā)布/收集模塊之間相輔相成。任務(wù)發(fā)布/收集模塊用于發(fā)布任務(wù)和收集任務(wù)反饋的結(jié)果，切割機(jī)制將任務(wù)自適應(yīng)切割成多個(gè)子任務(wù)，并用匹配機(jī)制將任務(wù)匹配給人群。針對(duì)匹配機(jī)制中的算法匹配問(wèn)題，我們提出的偶圖匹配算法很好地解決了任務(wù)隨機(jī)匹配帶來(lái)的盲目性和隨機(jī)性[9]。偶圖[10]是計(jì)算機(jī)科學(xué)家Robin Milner提出的一種在圖形基礎(chǔ)上的形式化理論模型，這個(gè)模型被提出的目的是為普適計(jì)算提供一個(gè)平臺(tái)[11]。偶圖應(yīng)用十分廣泛，如元素的查找、樹(shù)和圖的遍歷等，其也適用于人機(jī)協(xié)作中任務(wù)與人群的匹配[12]。

圖1 偶圖匹配算法的整體結(jié)構(gòu)

將可信度評(píng)估較好的人群和自適應(yīng)切割好的任務(wù)集看作兩種元素集U和V，通過(guò)偶圖匹配算法尋找U中和V中的匹配點(diǎn)進(jìn)行最大匹配，甚至是完美匹配，從而將任務(wù)分配給合適的人群，最終獲得較高質(zhì)量的反饋結(jié)果[13-15]。這種匹配算法比起隨機(jī)匹配算法雖然增加了一些復(fù)雜度，但有效提高任務(wù)完成的質(zhì)量，適合于對(duì)專(zhuān)業(yè)層次要求較高的復(fù)雜任務(wù)的分析和解決，可以應(yīng)用于大數(shù)據(jù)的挖掘、數(shù)據(jù)分析、領(lǐng)域知識(shí)答疑等領(lǐng)域。對(duì)未來(lái)的數(shù)據(jù)傳輸、大數(shù)據(jù)處理、感知數(shù)據(jù)質(zhì)量等方面有著重要的影響。

1 偶圖結(jié)構(gòu)

定義1偶圖 又稱(chēng)為“二分圖”，即將無(wú)向圖G中元素集V分為兩組U1和U2，滿(mǎn)足U1∪U2=V，且U1∩U2=?，E為圖G的邊集，E中的任意一邊的兩個(gè)端點(diǎn)一個(gè)屬于U1，另一個(gè)屬于U2，圖G也可表示為G。在人機(jī)協(xié)作中，將U1看作經(jīng)過(guò)可信度評(píng)估的人群集，將U2看作進(jìn)過(guò)自適應(yīng)切割后的任務(wù)集，將E看作人群集和任務(wù)集的匹配邊。

定義2最大匹配和完美匹配 在偶圖中，匹配為邊的集合，其中任意兩條邊都不會(huì)有公共的頂點(diǎn)，也就是說(shuō)大型任務(wù)被切割成多個(gè)小任務(wù)后，人群中經(jīng)過(guò)評(píng)估后的人只能匹配其中的一個(gè)小任務(wù)，以提高任務(wù)完成的效率。如圖2所示，初始時(shí)如(a)一樣每個(gè)用戶(hù)可以和多個(gè)小任務(wù)進(jìn)行匹配，通過(guò)偶圖匹配算法將具有專(zhuān)業(yè)背景和高可信度的用戶(hù)與相關(guān)的任務(wù)進(jìn)行匹配。經(jīng)過(guò)匹配的用戶(hù)和任務(wù)不再和其他用戶(hù)或任務(wù)進(jìn)行匹配，如(b)中U1和V1進(jìn)行匹配后，其他與U1和V1關(guān)聯(lián)的邊都屬于無(wú)用邊。一個(gè)大任務(wù)自適應(yīng)切割后分成的所有小任務(wù)的所有匹配中含有匹配邊數(shù)最多的匹配被稱(chēng)為偶圖的最大匹配。如(c)中U集中每個(gè)元素都能在V集中找到一個(gè)元素與之相關(guān)聯(lián)，最大匹配邊數(shù)為4，匹配邊的兩端分別是U集和V集。若可信度評(píng)估后參與匹配的用戶(hù)與自適應(yīng)切割后的小任務(wù)集能夠一一對(duì)應(yīng)，即U集和V集中每個(gè)元素都是匹配點(diǎn)，則該匹配便稱(chēng)為完美匹配。很顯然(c)也是完美匹配。

圖2 最大匹配和完美匹配

偶圖匹配過(guò)程中是根據(jù)什么來(lái)確保用戶(hù)和任務(wù)之間建立聯(lián)系，需要我們對(duì)任務(wù)進(jìn)行建模。用戶(hù)經(jīng)過(guò)可信評(píng)估后便可以獲取用戶(hù)的專(zhuān)業(yè)背景、知識(shí)儲(chǔ)備能力等。一個(gè)任務(wù)在自適應(yīng)分割后會(huì)分成許多不同的小任務(wù)，這些任務(wù)可能屬于不同領(lǐng)域，也可能屬于類(lèi)似領(lǐng)域。將具有相同或相似領(lǐng)域的用戶(hù)和任務(wù)進(jìn)行偶圖匹配，用戶(hù)完成任務(wù)的質(zhì)量還可以作為下一次任務(wù)匹配的參照，這樣的良性循環(huán)會(huì)使匹配的效果越來(lái)越好。因此建立同種任務(wù)切割后的小任務(wù)間的關(guān)聯(lián)度是必要的，而任務(wù)間的關(guān)聯(lián)度取決于任務(wù)所屬領(lǐng)域和描述相似度，綜合以上兩個(gè)因素可以推出：

TS=θ×AS+φ×SS

(1)

式中:系數(shù)θ和φ是根據(jù)數(shù)據(jù)集而定的，TS是分割后小任務(wù)間的關(guān)聯(lián)度，AS是任務(wù)領(lǐng)域相似度，SS是任務(wù)描述相似度。AS根據(jù)領(lǐng)域的重疊程度取值0、0.5和1。將任務(wù)的描述說(shuō)明抽象成一個(gè)集合，而描述說(shuō)明可以根據(jù)關(guān)鍵字、主題等抽象，通過(guò)小任務(wù)間描述集合的交集來(lái)確定SS的大小。如圖3所示，Task1與Task4分屬于兩個(gè)不同領(lǐng)域，故它們之間的領(lǐng)域相似度為0。Task3與其他任務(wù)間的領(lǐng)域相似度為0.5，以上便構(gòu)成了圖上各邊關(guān)聯(lián)度的權(quán)重，從而建立起任務(wù)間的關(guān)系，讓任務(wù)在偶圖匹配中更有效地匹配到與任務(wù)關(guān)聯(lián)度高的用戶(hù)。

圖3 任務(wù)關(guān)聯(lián)

2 偶圖匹配原理

偶圖匹配過(guò)程中需要考慮兩個(gè)因素：(1)用戶(hù)完成任務(wù)每次所花費(fèi)的代價(jià)M；(2)用戶(hù)完成任務(wù)后獲得的增量值H。偶圖將代價(jià)M值小的用戶(hù)優(yōu)先匹配，而增量值H用于下一次用戶(hù)與任務(wù)進(jìn)行匹配的附加量，如下所示：

(2)

(3)

增量值H是由兩部分構(gòu)成：(1)用戶(hù)完成任務(wù)所期望的收益量EI(Tx)；(2)用戶(hù)完成與該任務(wù)相同領(lǐng)域和相關(guān)聯(lián)的任務(wù)期望收益量EI(RTy)。其中T表示匹配的任務(wù)，RT表示與任務(wù)T相關(guān)聯(lián)但還沒(méi)有進(jìn)行匹配或者未完成的任務(wù)。用戶(hù)所獲得的期望隨任務(wù)的不同而不同，參數(shù)φ和ω是由用戶(hù)量、任務(wù)量以及數(shù)據(jù)集共同決定的。任務(wù)花費(fèi)代價(jià)M也是由兩部分構(gòu)成：(1)一個(gè)是任務(wù)困難因子ax，每個(gè)任務(wù)的困難程度不一，其困難程度是由該任務(wù)所處領(lǐng)域、用戶(hù)評(píng)價(jià)和完成量決定的；(2)是用戶(hù)完成任務(wù)的領(lǐng)域因子by，任務(wù)有可能只涉及一個(gè)領(lǐng)域，也有可能涉及多個(gè)領(lǐng)域，從任務(wù)分割的角度來(lái)看，小任務(wù)涉及的領(lǐng)域越少，分割的則越徹底，故by的值與涉及的領(lǐng)域有關(guān)。

用戶(hù)的增量H值是隨任務(wù)的不同而改變的，我們可以獲得用戶(hù)完成某一具體任務(wù)的任務(wù)期望收益量一般形式：

(4)

EI(T)表示用戶(hù)完成某一具體任務(wù)T所獲得的期望收益量，x表示任務(wù)變量，θ表示領(lǐng)域范圍。而pr(x|θ)表示用戶(hù)完成的任務(wù)質(zhì)量合格概率，合格是任務(wù)完成的一個(gè)標(biāo)準(zhǔn)，用戶(hù)所完成的任務(wù)質(zhì)量越高，其pr(x|θ)的值也就越大；pr(x)表示任務(wù)本身所給定標(biāo)準(zhǔn)的概率，也就是任務(wù)發(fā)布者所期望的標(biāo)準(zhǔn)。

偶圖匹配算法首先考慮任務(wù)情況再進(jìn)行尋找相匹配的用戶(hù)，任務(wù)在經(jīng)過(guò)自適應(yīng)切割后，便可以得到各小任務(wù)所屬領(lǐng)域、任務(wù)關(guān)聯(lián)情況，從而能夠確定用戶(hù)群體所處領(lǐng)域和專(zhuān)業(yè)背景。經(jīng)過(guò)可信度評(píng)估后的人群可以選擇相關(guān)領(lǐng)域的任務(wù)先進(jìn)行偶圖模擬匹配，從而計(jì)算出完成任務(wù)所需的代價(jià)。偶圖通過(guò)所得代價(jià)和用戶(hù)以往完成相同或同一領(lǐng)域相類(lèi)似的任務(wù)所獲得的期望增量值與合適的任務(wù)進(jìn)行匹配，從而提高任務(wù)完成質(zhì)量和效率。

3 偶圖匹配算法

在人機(jī)協(xié)作中的偶圖匹配主要用到了Hopcroft-Karp算法，它是匈牙利算法的繼承和擴(kuò)展，故需要先了解匈牙利算法的原理和特點(diǎn)。

定義3交替匹配路 從一個(gè)未匹配的用戶(hù)出發(fā)，借助多次的虛擬匹配，依次經(jīng)過(guò)非匹配用戶(hù)、匹配用戶(hù)這樣循環(huán)形成的路徑,我們將之稱(chēng)為交替匹配路。

定義4增廣匹配路 和交替匹配路相同，從一個(gè)未匹配的用戶(hù)開(kāi)始，走交替匹配路，除出發(fā)點(diǎn)外如果途中遇到另一未匹配點(diǎn)，則將這條特殊的交替匹配路稱(chēng)之為增廣匹配路。如圖4所示，(a)是用戶(hù)與任務(wù)匹配過(guò)程中所走的交替匹配路，而(b)是從(a)中抽取出來(lái)的增廣匹配路。由V4這個(gè)未匹配的用戶(hù)出發(fā)，途徑非匹配邊、匹配邊交替循環(huán)，并且中途遇到的點(diǎn)皆是匹配點(diǎn)，直到遇到未匹配點(diǎn)U2形成一條增廣匹配路。不難看出在該增廣匹配路中非匹配邊比匹配邊多一條，而這也是增廣匹配路的一個(gè)重要特點(diǎn)。將匹配邊與非匹配邊交換，則交替匹配路多出一條匹配邊，這樣既多出一條匹配邊，又不會(huì)破壞偶圖匹配，而我們研究增廣匹配路也是為了改進(jìn)匹配。

圖4 增廣匹配路示意圖

偶圖在匹配過(guò)程中會(huì)由圖匹配轉(zhuǎn)換成樹(shù)匹配，即匈牙利樹(shù)。匈牙利樹(shù)從一個(gè)未匹配用戶(hù)出發(fā)，走交替匹配路，進(jìn)行增廣匹配，不斷地循環(huán)尋找增廣匹配路，直到無(wú)法找到未匹配點(diǎn)為止。如圖5所示，(b)是由(a)轉(zhuǎn)化而得的樹(shù)，轉(zhuǎn)化得到的樹(shù)存在一個(gè)非匹配的葉子節(jié)點(diǎn)7，而匈牙利樹(shù)要求所有的葉子節(jié)點(diǎn)必須是匹配節(jié)點(diǎn)，故該樹(shù)不是匈牙利樹(shù)。因?yàn)楣?jié)點(diǎn)7是非匹配節(jié)點(diǎn)，所以可以將節(jié)點(diǎn)7去除，再進(jìn)行匹配將(a)轉(zhuǎn)化為(c)。除了節(jié)點(diǎn)2以外所有節(jié)點(diǎn)為匹配節(jié)點(diǎn)，以節(jié)點(diǎn)2為根節(jié)點(diǎn)轉(zhuǎn)化為匈牙利樹(shù)，類(lèi)似于廣度優(yōu)先搜索(BFS)樹(shù)，轉(zhuǎn)化得到的樹(shù)所有葉子節(jié)點(diǎn)均為匹配節(jié)點(diǎn)，此刻的匹配達(dá)到最大匹配。

圖5 匈牙利樹(shù)

以圖5(c)來(lái)說(shuō)明在匈牙利匹配基礎(chǔ)上的Hopcroft-Karp算法：

(1) 初始檢查，進(jìn)行虛擬匹配。以節(jié)點(diǎn)1為例，在初始化時(shí)，獲取用戶(hù)(節(jié)點(diǎn)1)的專(zhuān)業(yè)背景和擅長(zhǎng)領(lǐng)域等信息，發(fā)現(xiàn)自適應(yīng)切割后的小任務(wù)(節(jié)點(diǎn)7和9)滿(mǎn)足匹配條件，記錄信息，其他節(jié)點(diǎn)也是如此。

(2) 初始匹配。將節(jié)點(diǎn)1按照權(quán)值等與節(jié)點(diǎn)7匹配。

(3) 加入節(jié)點(diǎn)3，發(fā)現(xiàn)節(jié)點(diǎn)3可與節(jié)點(diǎn)7和8匹配，按照條件發(fā)現(xiàn)節(jié)點(diǎn)7更適合，但節(jié)點(diǎn)7已經(jīng)是匹配節(jié)點(diǎn)并與節(jié)點(diǎn)1進(jìn)行匹配，找到節(jié)點(diǎn)3出發(fā)的交替路徑3-7-1-9，將交替路上已在匹配上的邊1-7去除，剩余的邊3-7、1-9加入到匹配邊中。

(4) 循環(huán)往復(fù)處理其他節(jié)點(diǎn)即可完成所有匹配。

Hopcroft-Karp算法根據(jù)匈牙利算法進(jìn)行改進(jìn)所得的算法流程如下：

輸入：X={X1,X2,…,Xn}，P={P1,P2,…,Pn}；

輸出：Y={,,…,}。

//任務(wù)匹配結(jié)果鍵值對(duì)

① 獲取自動(dòng)切分后的任務(wù)子集：x1,x2,…,xg

② G_Theory(X,P)

// 根據(jù)任務(wù)集進(jìn)行人群博弈

③ G_init(X,P)

// 從G=(X,P,E)中取得初始匹配

④ Init_X(X,-1,X.length);

⑤ Init_Y(Y,-1,Y.length);

⑥ G_read(X, Y)

// 讀取節(jié)點(diǎn)進(jìn)行匹配

⑦ IF(X.isEmpty)

//所有任務(wù)結(jié)點(diǎn)獲得匹配(完美匹配)，返回

⑧ RUTURN 0

⑨ IF(!X.Empty)

// 非完美匹配進(jìn)行一次BFS

⑩ G_BFS()

// 標(biāo)記各點(diǎn)到源點(diǎn)之間的距離

// 從X中找到未被M匹配到的結(jié)點(diǎn)x0

// 循環(huán)查找滿(mǎn)足條件的邊集E

// 滿(mǎn)足條件dis[x]=dis[v]+1，并做記錄S={x0}

// 未匹配節(jié)點(diǎn)進(jìn)行最大匹配

// 重復(fù)多次寬度優(yōu)先遍歷

// 無(wú)法得到更大匹配，返回；否則取?y0∈N(S)

//y0被M匹配并轉(zhuǎn)步驟18，否則轉(zhuǎn)步驟19

//獲取(y0,z0)，并轉(zhuǎn)步驟6

// 做一條x0→y0的增光路經(jīng)P(x0,y0)

Hopcroft-Karp算法使用鍵值對(duì)作為輸入和輸出，數(shù)據(jù)主要以Text、String類(lèi)型為主，主要應(yīng)用于互聯(lián)網(wǎng)群智計(jì)算中，如眾包、社會(huì)感知任務(wù)、城市交通感知與室內(nèi)定位等。以大量用戶(hù)參與作為基礎(chǔ)和前提，通過(guò)合理的協(xié)作完成計(jì)算機(jī)和用戶(hù)單獨(dú)不可能完成的復(fù)雜任務(wù)。如果無(wú)法整合大量的互聯(lián)網(wǎng)用戶(hù)，則該算法無(wú)法成功實(shí)施，則匹配也無(wú)從談起。

4 實(shí)驗(yàn)結(jié)果及分析

為了了解Hopcroft-Karp算法的匹配準(zhǔn)確率和匹配效果，分別使用隨機(jī)匹配算法和匈牙利算法作為參照實(shí)驗(yàn)對(duì)象?？紤]到眾包平臺(tái)不支持偶圖匹配算法，所以具體的實(shí)驗(yàn)我們只能在線(xiàn)下用仿真迭代實(shí)驗(yàn)。下面分別進(jìn)行了非標(biāo)準(zhǔn)數(shù)據(jù)測(cè)試實(shí)驗(yàn)和標(biāo)準(zhǔn)測(cè)試實(shí)驗(yàn)來(lái)檢驗(yàn)Hopcroft-Karp算法的效果。

4.1 非標(biāo)準(zhǔn)數(shù)據(jù)測(cè)試

在該實(shí)驗(yàn)中，我們采用了三個(gè)主題：藥品主題、音樂(lè)主題和電腦器材主題，三個(gè)主題涉及的任務(wù)數(shù)達(dá)到n=1 200，即每個(gè)主題有400個(gè)任務(wù)。假設(shè)有90個(gè)用戶(hù)參與該實(shí)驗(yàn)，并且每個(gè)用戶(hù)擅長(zhǎng)其中1個(gè)領(lǐng)域主題，那么用戶(hù)回答擅長(zhǎng)領(lǐng)域主題的準(zhǔn)確率服從高斯分布，其準(zhǔn)確率從gauss(0.7,0.3)中進(jìn)行數(shù)據(jù)采樣。

在實(shí)驗(yàn)初始時(shí)將關(guān)聯(lián)度高的任務(wù)自適應(yīng)切分為低耦合的小任務(wù)，由于選擇的主題明確，所以不存在領(lǐng)域關(guān)聯(lián)度為0.5，不同背景任務(wù)的關(guān)聯(lián)度為0，相同背景任務(wù)的關(guān)聯(lián)度為1。在實(shí)驗(yàn)中，將任務(wù)分成20批次，每批次有60個(gè)任務(wù)，在任務(wù)分發(fā)過(guò)程中，任務(wù)的難度逐漸遞減。任務(wù)使用隨機(jī)分配算法、匈牙利算法、Hopcroft-Karp算法分別進(jìn)行1 000次匹配，收集每次任務(wù)完成的情況，最后取其平均準(zhǔn)確率。

如圖6所示，任務(wù)難度按照貝塔分布，其中(a,b)分別取值(2,1)、(4,1)、(7,1)、(10,1),a的值從2至10表示任務(wù)難度從難到易。該圖縱坐標(biāo)是實(shí)驗(yàn)中任務(wù)重復(fù)1 000次匹配所取得的平均準(zhǔn)確率。從圖中可以看出任務(wù)按照隨機(jī)分配，隨著任務(wù)難度的降低，其平均準(zhǔn)確率有所提高，但不明顯。隨機(jī)分配并不考慮任務(wù)的領(lǐng)域和背景，也不考慮用戶(hù)的專(zhuān)業(yè)和能力，進(jìn)行隨機(jī)匹配，所以任務(wù)的難易程度對(duì)隨機(jī)分配影響不大。匈牙利算法和Hopcroft-Karp算法受貝塔分布的影響較大，因?yàn)檫@兩個(gè)算法需考慮任務(wù)的領(lǐng)域和關(guān)聯(lián)情況以及用戶(hù)的可信評(píng)估情況，以此計(jì)算用戶(hù)完成任務(wù)所期望的收益量EI(Tx)、增量值和完成任務(wù)花費(fèi)的代價(jià)M。所以隨著任務(wù)難度降低，用戶(hù)完成任務(wù)的收益越大，花費(fèi)的代價(jià)也越小，從而完成任務(wù)的平均準(zhǔn)確率也會(huì)越高。由于Hopcroft-Karp算法是對(duì)匈牙利補(bǔ)充和擴(kuò)展，對(duì)其匹配的質(zhì)量沒(méi)有太大的影響，再者實(shí)驗(yàn)次數(shù)多，所以?xún)烧叩钠骄鶞?zhǔn)確率基本一致。

圖6 三種算法正確率比較

匈牙利算法和Hopcroft-Karp算法匹配質(zhì)量差不多，我們從兩者的匹配效率進(jìn)行比較。圖7是數(shù)據(jù)量從1 k到10 k遞增的情況下兩個(gè)算法花費(fèi)的時(shí)間之差，左邊縱坐標(biāo)是兩個(gè)算法(柱狀圖)花費(fèi)的時(shí)間，右邊是兩算法時(shí)間差(折線(xiàn)圖)。從圖中可以看出隨著數(shù)據(jù)量的增大，Hopcroft-Karp算法匹配花費(fèi)的時(shí)間比匈牙利算法匹配花費(fèi)的時(shí)間越來(lái)越少，適合大數(shù)據(jù)量情況下的任務(wù)匹配，而我們?nèi)后w計(jì)算中人機(jī)協(xié)作所面向的正是大數(shù)據(jù)和大人群。

圖7 時(shí)間復(fù)雜度

下面通過(guò)某一具體β值來(lái)觀察用戶(hù)完成任務(wù)的準(zhǔn)確率情況。由于匈牙利算法和Hopcroft-Karp算法的平均準(zhǔn)確率基本一致，我們就只比較隨機(jī)分配算法和Hopcroft-Karp算法的平均準(zhǔn)確率。圖8是從中進(jìn)行采樣，進(jìn)行20輪任務(wù)匹配的情況，從圖中可以看出，使用隨機(jī)分配算法匹配，用戶(hù)完成任務(wù)的準(zhǔn)確率平均在40%；使用Hopcroft-Karp算法隨著輪數(shù)的增加，其平均在準(zhǔn)確率是有小幅度的提高的。在第一輪的時(shí)候，由于初始無(wú)法獲得前輪用戶(hù)完成任務(wù)花費(fèi)的代價(jià)M值，所以其平均準(zhǔn)確率較低，但其考慮的因素較多，其匹配的準(zhǔn)確率也比隨機(jī)分配的效果要好。在第二輪匹配的時(shí)候有了前輪的M值，其平均準(zhǔn)確率有較大幅度的提高。因?yàn)镠opcroft-Karp具有不斷優(yōu)化的效果，所以隨著輪數(shù)的增加，其匹配的效果會(huì)越好。

圖8 β(4,1)對(duì)應(yīng)的任務(wù)完成準(zhǔn)確率

4.2 標(biāo)準(zhǔn)數(shù)據(jù)測(cè)試

標(biāo)準(zhǔn)數(shù)據(jù)集來(lái)源于infochimps公司(簡(jiǎn)稱(chēng)IFC)公開(kāi)數(shù)據(jù)集http://www.data.gov中的Education數(shù)據(jù)https://www.data.gov/education/。我們從Education中獲取medicines數(shù)據(jù)集、English數(shù)據(jù)集、law數(shù)據(jù)集三種類(lèi)型的數(shù)據(jù)集來(lái)檢驗(yàn)Hopcroft-Karp算法的有效性。對(duì)于medicines的數(shù)據(jù)集，我們收集了藥品名稱(chēng)、藥品知識(shí)問(wèn)答等相關(guān)問(wèn)題；對(duì)于English數(shù)據(jù)集，我們收集了詞匯問(wèn)題、語(yǔ)法問(wèn)題以及其他相關(guān)英語(yǔ)問(wèn)題；對(duì)于law數(shù)據(jù)集，我們收集了法律相關(guān)知識(shí)問(wèn)答題。每個(gè)任務(wù)實(shí)驗(yàn)3次，對(duì)于答案不明確的任務(wù)采用投票原則(少數(shù)服從多數(shù))。圖9是Hopcroft-Karp算法的實(shí)驗(yàn)效果圖。

圖9 主題數(shù)據(jù)對(duì)應(yīng)的準(zhǔn)確率

從圖9中可以看出，標(biāo)準(zhǔn)的三種數(shù)據(jù)集與非標(biāo)準(zhǔn)數(shù)據(jù)集平均準(zhǔn)確率趨勢(shì)相一致，隨機(jī)分配算法的效果和人群質(zhì)量有很大關(guān)系。如英語(yǔ)的普及使得隨機(jī)配算法匹配人群與任務(wù)獲得的平均準(zhǔn)確率相對(duì)其他兩個(gè)數(shù)據(jù)集獲得的平均準(zhǔn)確率要高，但由于其隨機(jī)性，所以獲得的平均準(zhǔn)確率不是很高。而Hopcroft-Karp算法獲得的準(zhǔn)確率在90%左右，匹配的效果非常好。

5 結(jié) 語(yǔ)

本文提出了基于偶圖的人群與任務(wù)匹配方法，使用Hopcroft-Karp算法充分考慮了任務(wù)的領(lǐng)域和人群的特點(diǎn)，實(shí)現(xiàn)了人群與任務(wù)之間的高效匹配，提高了任務(wù)完成的質(zhì)量和效率，為人機(jī)協(xié)作的任務(wù)有效分配做出了重要的貢獻(xiàn)。在下一步的研究中，我們將會(huì)從更多方面考慮人群特點(diǎn)以及任務(wù)的劃分來(lái)提高人群與任務(wù)的匹配效果，并以不斷提高匹配效率為目標(biāo)，讓人機(jī)協(xié)作能夠迎接更多可變的挑戰(zhàn)。