群體計算中的偶圖匹配算法

滿君豐 劉 鳴 彭 成 劉美博

(湖南工業大學計算機學院智能信息感知及處理技術重點實驗室 湖南 株洲 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中元素集V分為兩組U1和U2，滿足U1∪U2=V，且U1∩U2=?，E為圖G的邊集，E中的任意一邊的兩個端點一個屬于U1，另一個屬于U2，圖G也可表示為G。在人機協作中，將U1看作經過可信度評估的人群集，將U2看作進過自適應切割后的任務集，將E看作人群集和任務集的匹配邊。

定義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算法充分考慮了任務的領域和人群的特點，實現了人群與任務之間的高效匹配，提高了任務完成的質量和效率，為人機協作的任務有效分配做出了重要的貢獻。在下一步的研究中，我們將會從更多方面考慮人群特點以及任務的劃分來提高人群與任務的匹配效果，并以不斷提高匹配效率為目標，讓人機協作能夠迎接更多可變的挑戰。