滿君豐 劉 鳴 彭 成 劉美博

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

0 引 言

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

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

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

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

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

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

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

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

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

圖2 最大匹配和完美匹配

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

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ù)的描述說明抽象成一個集合，而描述說明可以根據(jù)關(guān)鍵字、主題等抽象，通過小任務(wù)間描述集合的交集來確定SS的大小。如圖3所示，Task1與Task4分屬于兩個不同領(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)度高的用戶。

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

2 偶圖匹配原理

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

(2)

(3)

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

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

(4)

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

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

3 偶圖匹配算法

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

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

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

圖4 增廣匹配路示意圖

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

圖5 匈牙利樹

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

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

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

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

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

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

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

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

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

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

② G_Theory(X,P)

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

③ 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é)點進行匹配

⑦ IF(X.isEmpty)

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

⑧ RUTURN 0

⑨ IF(!X.Empty)

// 非完美匹配進行一次BFS

⑩ G_BFS()

// 標記各點到源點之間的距離

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

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

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

// 未匹配節(jié)點進行最大匹配

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

// 無法得到更大匹配，返回；否則取?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算法使用鍵值對作為輸入和輸出，數(shù)據(jù)主要以Text、String類型為主，主要應(yīng)用于互聯(lián)網(wǎng)群智計算中，如眾包、社會感知任務(wù)、城市交通感知與室內(nèi)定位等。以大量用戶參與作為基礎(chǔ)和前提，通過合理的協(xié)作完成計算機和用戶單獨不可能完成的復(fù)雜任務(wù)。如果無法整合大量的互聯(lián)網(wǎng)用戶，則該算法無法成功實施，則匹配也無從談起。

4 實驗結(jié)果及分析

為了了解Hopcroft-Karp算法的匹配準確率和匹配效果，分別使用隨機匹配算法和匈牙利算法作為參照實驗對象。考慮到眾包平臺不支持偶圖匹配算法，所以具體的實驗我們只能在線下用仿真迭代實驗。下面分別進行了非標準數(shù)據(jù)測試實驗和標準測試實驗來檢驗Hopcroft-Karp算法的效果。

4.1 非標準數(shù)據(jù)測試

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

在實驗初始時將關(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。在實驗中，將任務(wù)分成20批次，每批次有60個任務(wù)，在任務(wù)分發(fā)過程中，任務(wù)的難度逐漸遞減。任務(wù)使用隨機分配算法、匈牙利算法、Hopcroft-Karp算法分別進行1 000次匹配，收集每次任務(wù)完成的情況，最后取其平均準確率。

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

圖6 三種算法正確率比較

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

圖7 時間復(fù)雜度

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

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

4.2 標準數(shù)據(jù)測試

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

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

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

5 結(jié) 語

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