王 鑫,廖祎瑋,趙國生,王 健,謝寶文
(1.哈爾濱師范大學計算機科學與信息工程學院,黑龍江 哈爾濱 150025; 2.哈爾濱理工大學計算機科學與技術學院,黑龍江 哈爾濱 150080)
移動群智感知是指利用移動設備來收集、分析和共享感知信息與數據。隨著移動設備的普及,移動群智感知技術得到了越來越多的關注[1],并且已經廣泛服務于各大應用領域,如交通狀況監控[2]、環境監測[3]和移動社交推薦[4]等。在移動群智感知系統中,感知任務具有類型多、范圍廣和數量大等基本特性。面向不同的任務需求,將任務分配給合適的用戶以提高任務與用戶的匹配度,同時提高任務的分配效率成為群智感知任務分配的關鍵。
目前,國內外很多學者對群智感知任務分配問題展開了研究。Amintoosi等[5]針對社會感知中參與者復雜的、未知的社交關系提出一種參與者選擇架構,根據參與者的適合性得分和參與者間的相互信任度選擇合適的參與者。Xiao等[6]基于貪心算法提出了一種最大程度提高已招募用戶的效率同時在截止時間內使感知支出最小的用戶招募算法,該算法招募多個用戶合作完成感知任務。韓俊櫻等[7]提出了基于貪婪算法的分布式多任務分配方法,該方法劃分任務和用戶區域,動態定價并發任務組合構成的任務路徑,根據感知用戶的歷史信譽度分配任務。上述任務分配機制主要以用戶或平臺為中心進行設計,沒有考慮任務與用戶的聯系。為解決上述問題,Zhao等[8]提出一種每個任務最多由一個用戶來完成的感知任務拍賣機制,該機制并沒有考慮任務分配過程中用戶可靠性的影響。Peng等[9]提出在任務分配時首先預測用戶的期望任務完成質量來選擇高可靠性的用戶,并且為了使用戶提交的數據質量更高,根據用戶實際提交的數據質量來決定用戶的報酬。劉媛妮等[10]以最大化用戶效用為目的提出了一種基于拍賣模型的激勵機制,該機制以任務為中心選擇贏標用戶且基于臨界價格對贏標用戶支付報酬,該機制中用戶可將未完成任務轉售他人。Han等[11]研究了一種用戶根據感知時間和感知成本對平臺發布的感知任務進行競爭的激勵機制,感知平臺在預算約束下支付報酬。Koutsopoulos[12]基于反向競拍模型考慮到平臺的預算條件約束,設計了一種最小化平臺預算成本的激勵機制,該機制結合用戶貢獻的數據量和數據質量進行用戶選擇與報酬支付。
群智感知中感知平臺發布的任務是多類的,用戶完成不同類別任務的效力也互不相同,上述研究均沒有考慮到面向任務需求的用戶分配問題,無法滿足任務需求的復雜性。王濤春等[13]提出了從5個方面評估參與者信譽度的參與者信譽評估方案,包括參與者歷史信譽度、提交數據的響應時間、距離、數據相關性和數據質量,通過建立信譽評估方程計算出參與者本次提交數據后的信譽度,新任務由群智感知網絡根據更新后的信譽度選擇合適的參與者來完成。Messaoud等[14]提出了在滿足信息質量與能量約束的條件下,最大化信息質量和最小化能耗地選擇合適的用戶參與感知任務,該機制基于禁忌搜索算法且對能量和信息質量敏感。Li等[15]基于感知任務的實時性和異構性難題提出根據離線算法和在線算法來招募合適的參與者。Luo等[16]提出了一個基于Stackelberg博弈的激勵框架,該框架考慮了不同情況下平臺和用戶之間的交互關系以及任務之間的相互關系。Feng等[17]設計一種考慮用戶和任務的位置關聯的激勵機制,該機制基于逆向競拍框架,用戶根據自身的位置信息響應感知任務并上報目標報酬,感知平臺通過贏標價決策算法決定贏標價,以最小化預算成本。上述任務分配機制雖面向任務需求對用戶進行選擇,但未明確用戶適合完成任務的類別,未考慮用戶具有完成多類別任務的能力,且一旦有新任務推送會再次對用戶信息進行處理,增加了機制的整體復雜性。因此,構建一種以任務為中心,篩選適合任務類別且滿足任務其他需求的用戶的高效任務分配模型有重要研究意義。
針對上述問題,本文提出了一種任務需求特征提取算法TRFEA(Task Requirement Feature Extraction Algorithm)和用戶標簽分類方法相結合的TREAULCM(Task Requirement Extraction Algorithm and User Label Classification Method)任務分配模型。利用任務需求特征提取算法提取感知任務的類別關鍵詞,通過多線性神經網絡訓練得到數據集中各類數據的高層特征并利用徑向基核函數將高層特征融合,通過多核學習訓練得到分類器,利用分類器預測用戶的類型標簽。根據任務類別、空間位置信息和用戶參與度選擇滿足任務需求的用戶分發任務。本文主要貢獻包括以下2點:
(1)本文通過用戶標簽分類方法得到適合用戶的任務類別標簽,根據任務需求選擇合適的用戶進行任務分發,實現用戶優選。
(2)本文針對多線性神經網絡2個全連接層提取到的特征,采用多核學習方法將它們在核空間中自適應融合,融合后的特征有更好的表現力和魯棒性。
群智感知的經典網絡體系結構由任務發布者、感知平臺和感知用戶3部分組成。任務發布者向感知平臺購買感知數據;感知平臺根據感知任務需求和激勵機制等選擇合適的感知用戶發布任務,并對用戶提交的數據進行評估和支付報酬;感知用戶可根據自身條件有選擇性地參與任務。
本文提出的任務分配模型如圖1所示。該模型首先對感知任務進行處理,明確感知任務類別,然后通過用戶標簽分類方法對數據集進行訓練,得到分類器,利用分類器得到適合用戶處理的任務類別并給予用戶該類標簽。在任務分配過程中,感知平臺選擇符合任務類別且滿足其他任務需求的用戶執行任務,使任務分配更有針對性,任務完成后對用戶的標簽進行迭代預測。

Figure 1 Model of task assignment圖1 任務分配模型
感知平臺發布的不同類別的感知任務,意味著不同的任務需求。只有從任務需求的角度選擇和感知任務需求匹配度更高的用戶參與任務,才能最大限度保證任務的完成率和感知數據的可用性,使得資源利用最大化,減少感知平臺工作量。本文提出任務需求特征提取算法TRFEA和用戶標簽分類方法,其中TRFEA用于提取感知任務類型的關鍵詞;用戶標簽分類方法用于提取用戶類型標簽。
發布的感知任務可形式化地描述為任務屬性向量task=(Tt,U,Lab,St,W,Par),其中,Tt代表任務的文字描述;U代表需要招募的感知用戶數量;Lab代表任務要求的用戶類型;St為感知任務的位置信息;W為任務要求的距離遠近度;Par為任務要求的用戶參與度。用矩陣Bg×e存放任務向量,其中g個任務用g行表示,任務的第e個屬性用第e列表示。任務集可表示為Task={task1,task2,…,taskt}。
感知用戶可形式化地描述為用戶屬性向量user=(X,Y,Su),其中,X為用戶的數據集;Y為用戶的標簽集;Su為用戶的位置信息。用矩陣Qx×f存放用戶向量,其中x個用戶用x行表示,用戶的第f個屬性用第f列表示。用戶集可表示為User={user1,user2,…,useru}。為了方便理解,表1給出了本文部分符號標記及其對應的定義。

Table 1 Symbols and their definitions表1 符號及其定義
本文提出了TRFEA算法來提取感知任務的類別關鍵詞。TRFEA算法用隸屬度確定每個數據點屬于某個聚類的程度并自適應地確定聚類中心個數。去除任務文字描述中無實際意義的虛詞和代詞,得到所有任務的詞集Tx={T1,T2,…,Tnu},將其用空間向量模型表示,轉換成高維空間中的向量,然后對這些向量聚類。Txi表示任務taski的詞集,任一Txi可表示為以特征項的權重為分量的向量Ti,其中每個詞或詞組作為特征項,權重為詞或詞組出現的頻數。
每個Ti到聚類中心Cj(j=1,2,…,q)的隸屬度Fij的計算公式為:
(1)
其中,ψ是模糊指數,此處取ψ=2;‖Ti-Cj‖表示第i個任務的描述向量與第j個聚類中心之間的歐幾里得距離,所有任務到每個聚類中心隸屬度總和為1。
聚類中心的計算公式為:
(2)
設置目標函數JFK:
(3)
對于聚類算法得到的聚類中心集C={C1,C2,…,Cq}中任一聚類結果Cs,把構成Cs的每一個任務看作一個有v個不同單詞的序列W=(w1,w2,…,wv),每一個wi到該類的主題詞服從泊松分布,并把聚類中心集C中涉及的所有不同單詞組成大集合Word。通過統計主題LDA(Latent Dirichlet Allocation)模型來識別潛藏的主題信息。TRFEA算法流程如算法1所示:
算法1TRFEA算法
輸入:任務描述集Tx={T1,T2,…,Tnu}。
輸出:各類任務的類別關鍵詞集合Lab。
步驟1隨機得到自適應q個模糊聚類中心Cj,并初始化,設迭代次數num=0;
步驟2通過式(1)計算每個Ti到聚類中心Cj的隸屬度Fij;
步驟3通過式(2)計算聚類中心。根據Cj的變化,重新計算隸屬度Fij;
步驟4通過式(3)計算目標函數JFK,如果目標函數不收斂,num=num+1,返回步驟3,否則得到聚類中心集C,轉步驟5;
步驟5設置主題的參數α和詞的參數δ,兩者均隨著訓練和學習過程自動變化;
步驟6對于聚類結果Cs中每個詞wi,根據其到各個主題發生的概率P(θ|α)得到主題分布θ,主題個數設為Tnum,并以概率P(Zs|θ)選擇當前的主題Zs;
步驟7按照當前主題Zs下的多項分布概率P(topici|Zs,δ),選擇一個單詞topici,topici∈Word;
步驟8對于每類任務主題詞的結果集Topic={topic1,topic2,…,topicTnum},返回步驟1進行聚類分析,直到結果集Topic不再變化,轉步驟9;
步驟9Lab=Topic,并返回Lab。
明確任務需求基礎上的用戶選擇問題實際上是篩選和任務需求更匹配的用戶,本文提出了一種多線性神經網絡結合多核學習的用戶標簽分類方法,如圖2所示,其中MLSVM(Multi Label Support Vector Machine)表示多核支持向量機。該方法首先通過多線性神經網絡訓練數據集得到各類數據的高層特征并利用徑向基核函數融合特征,根據已知的類別信息通過多核學習訓練得到一個分類器,待預測用戶的數據經過分類器可得到該用戶的標簽集。

Figure 2 Framework of user label classification method 圖2 用戶標簽分類方法框架
對于數據集{(X1,Y1),(X2,Y2),…,(XHH,YHH)},數據集中數據信息表示為Xh={xh1,xh2,…,xhη},xh*∈χ,χ為數據空間,η為Xh中數據個數,Yh?Y為Xh的標簽集Yh={yh1,yh2,…,yhλ},Y為標簽空間,λ為Yh中包含的標簽個數。對數據集中每類數據均隨機抽取2/3并去掉標簽組成訓練集Tr,對于每類數據進行高層特征提取并得到核函數。
本文設計了一種卷積層-池化層循環的優化多線性神經網絡結構,保持了網絡良好的可區分性,縮短了計算時間。本文搭建多線性神經網絡結構提取各類數據的高層特征,該網絡結構的前5層每層由卷積層和池化層構成,用l1~l5表示。ac1和ac2表示第6層和第7層,第6層、第7層為全連接層,將第6層和第7層特征作為2種不同的高層特征。將訓練集Tr輸入到搭建好的網絡中。首先計算每個神經元的輸出值。
(1)卷積層。
(4)

(2)池化層。
(5)

(3)全連接層。
(6)
其中,pl-1表示第l-1層所有特征圖的加權結果。
其次,反向計算多線性神經網絡整體損失函數。設任一帶標簽樣本Ii(i=1,2,…,Nm),Nm表示訓練集樣本總個數,Ii的標簽實際上是一對多標簽。
(7)

(8)
損失函數E0的計算公式為:
(9)

(10)
更新多線性神經網絡的參數H,同時最小化損失函數E0:
(11)
其中,ω表示多線性神經網絡的學習率,決定了每步調整的幅度;H(i)表示第i組更新的參數。
最后根據式(6),分別得到ac1、ac2層輸出結果ac1-r、ac2-r,二者分別包含了ac1、ac2層計算得到的所有特征圖,將其作為待融合的全連接層特征。
本文利用徑向基核函數解決全連接層特征融合問題。進一步地,可以利用基于核的分類器得到用戶的類型標簽。
(12)
其中,k(Xn) 表示第n類數據的核函數;za表示Xn中第a個數據在多核某一尺度下ac1層的特征向量ac1-r;zb表示Xn中第b個數據在多核某一尺度下ac2層的特征向量ac2-r,μ表示帶寬參數。
在群智感知任務分配中一個用戶可完成多類任務,故而用戶的數據樣本分布特征存在差異性,如果數據采用同一種高維映射方式,會忽略不同任務類別的差異性。因此,本文采用多核學習方法通過融合不同權系數的核函數使分類的靈活性和準確性更高。
根據得到的每類數據的核函數和訓練集數據的類別信息,采用SimpleMKL工具箱訓練得到一個MLSVM分類器hy并得到權系數βn(1≤n≤N),完成多核融合過程,如圖3所示。

Figure 3 Multi-kernel fusion process圖3 多核融合過程
(13)

本文根據任務的需求類別、距離遠近度和用戶參與度3種因素共同決定感知用戶的選擇,實現滿足任務需求的任務分配。
在實際的群智感知任務分配問題中,感知平臺希望選擇距離較近的感知用戶參與感知任務以減少報酬支出,感知用戶也會偏向于參與離自身位置較近的任務,為了最大化用戶的參與意愿,最小化平臺支出,本文考慮到任務與用戶的空間位置信息,提出距離遠近度W作為任務分配的決定性因素之一,計算公式如下:
Wij=1-min[logodis(Sti,Suj),1],Wij∈[0,1]
(14)
其中,Wij為任務taski和用戶userj的距離遠近度,Wij越接近1,則無論從感知平臺還是從用戶角度考慮,雙方的開銷都越小;o為感知平臺設置的任務區域半徑,即在該半徑內選擇用戶參與任務;dis(Sti,Suj)表示任務taski的位置Sti到用戶userj的位置Suj的歐幾里得距離。
為了選擇更活躍的用戶參與任務以保證已分配任務的完成情況,且調動用戶的參與積極性,本文提出以用戶參與度作為用戶選擇的決定性因素之一。在本文模型中,用戶參與度由其之前在其他感知任務中的表現共同決定。
設frj是用戶userj對所分配任務的執行總次數,fej是用戶userj對所分配任務的未執行總次數,用戶userj在過去任務中積累的執行情況為:
(15)
感知平臺對用戶提供的數據進行評分,評分值在[1,5],結合用戶執行任務的情況,可計算用戶userj的參與度:
(16)
其中,num為用戶完成任務的總個數;s(i)為用戶完成任務taski后平臺的評分;min(i)和max(i)為對完成任務taski的所有用戶,平臺評分最低值和最高值。
TREAULCM任務分配模型詳細描述如下:
(1)對于任務集Task={task1,task2,…,taskt},通過算法1得到任務taski的類別關鍵詞Labi。
(2)對于用戶集User={user1,user2,…,useru},將數據通過用戶標簽分類方法訓練好的MLSVM分類器得到用戶userj的類型標簽集YLabj。
(3)根據任務要求的用戶類型篩選用戶。如果YLabj中某一元素是Labi中的元素,那么userj進入候選用戶集Usercd={user1,user2,…,userc}(1 (4)計算候選用戶集中所有用戶到任務taski的距離遠近度,形成以距離遠近度降序排列的新候選用戶序列Usercd1。 (5)對于Usercd1中用戶,以用戶參與度降序排列得到用戶序列Usercd2。 (6)根據任務需要招募的感知用戶數量,從前往后選取Usercd2中需求用戶數量×120%個用戶組成最終的待分發任務用戶集。 為了驗證本文的TRFEA算法在任務需求特征提取方面的效率和準確性,將TRFEA算法與IKAnalyzer算法[18]和傳統的最長子串LCS(Longest Common Subsequence)算法進行對比。其中,IKAnalyzer算法[18]是一種中文文本的分詞技術,它根據給定的字符而不是依賴于字符數量來分詞,該算法掃描文本,遇到預先定義的字符才會進行分詞;LCS算法具有語種獨立性,適用處理中文文本,該算法不需要對文本內容進行語言預處理,并且對提取出的公共子字符串的長度沒有限制。 為了驗證本文模型在任務分配中的高效性和準確性,在相同實驗環境下,將本文模型與采用余弦相似度計算方法的用戶選擇激勵模型TRIM(Task Requirement-oriented user selection Incentive Mechanism)[19]和基于邏輯回歸LR(Logistic Regression)方法的任務分配模型[20]進行比較。 實驗基于Python 3.5以及TensorFlow 2.0實現,并在Linux環境下運行。本文數據集由公用數據集MSRC-v2[21]中的數據組成,MSRC-v2[21]數據集包含23類的591幅圖像,每幅圖像大小為320×213左右,其中很多圖像同時屬于多類。在數據集上每類數據均隨機選取2/3的樣本組成訓練集,剩余樣本用作測試。根據數據集MSRC-v2[21]隨機生成由23種類別信息和其他文字組成的任務文字描述,每個任務描述大于100字符數,作為實驗中的感知平臺發布的任務信息,并對包含類別信息的詞或詞組進行標記,同時隨機生成其他任務需求;由MSRC-v2[21]數據集中591幅圖像數據組成用戶的歷史感知數據,并隨機生成其他用戶信息,構造100個感知用戶。 根據數據集設置主題數目Tnum=23,聚類中心個數q=23,參數α=50/Tnum,參數δ=0.01,多線性神經網絡中初始學習率ω=0.001,帶寬參數μ=0.05,核函數的總個數N=23,在[0,1]隨機選擇用戶參與度。 6.2.1 任務類別關鍵詞提取準確率 TRFEA算法著重于提高任務類別關鍵詞提取的準確率,任務類別關鍵詞提取的準確率與任務文本的長度具有相關性,通過式(17)計算任務類別關鍵詞的提取準確率Tra,如圖4所示。 (17) 其中,CHd表示其有標記的關鍵詞的字符數;fqb表示其有標記的關鍵詞在文本中出現的頻數;CH表示提取出的所有關鍵詞的字符數;fq表示其提取出的關鍵詞在文本中出現的頻數。 Figure 4 Extraction accuracy of task category keywords 圖4 任務類別關鍵詞提取準確率 從圖4可以看出,TRFEA算法的任務類別關鍵詞提取準確率明顯高于IKAnalyzer算法和傳統的LCS算法的,準確率在85%以上,且隨著任務字符數的增多呈上升趨勢。這是因為TRFEA算法采用了自適應聚類方法,該方法用隸屬度確定聚類中心,對任務需求進行聚類預處理,該方法提取出的詞或詞組不會由于截取而失去其原本的含義,并且能夠自適應調整聚類中心,不斷優化任務類別關鍵詞與任務的契合性。又因為TRFEA算法用LDA模型將文本信息轉化成易于建模的數字信息,所以其與文本描述的任務需求類別更為貼近,模型會隨著信息的增多更加完善,使TRFEA算法提取關鍵詞的準確率更高。IKAnalyzer算法雖然分詞較為準確,但是由于并不具有關鍵詞提取的功能,僅通過給定字符分詞,缺乏自主性和能動性,使得提取準確率較低。綜上,TRFEA算法的任務類別關鍵詞提取準確率較高。 6.2.2 任務類別關鍵詞提取時間 任務類別關鍵詞提取時間會隨著測試文本長度的增加而增加,本文選取了100個任務文本來測試算法的執行時間,并求取平均值,結果如圖5所示。 Figure 5 Relationship of execution time and the number of task characters圖5 執行時間與任務字符數的關系 從圖5可以看出,TRFEA算法提取任務類別所需時間少于傳統的LCS算法的,略多于IKAnalyzer算法的。因為TRFEA算法在進行詞或詞組提取時需對文本進行聚類提取,而傳統的LCS算法對提取出的公共子字符串的長度沒有限制,該算法的空間復雜度會隨著文本分句長度的增長呈平方倍增長。TRFEA算法將文本信息轉化成數字信息進而識別關鍵詞,降低了空間復雜度,因此效率高于傳統的LCS算法。IKAnalyzer算法需要掃描文本尋找指定的字符進行分詞,因此耗時與TRFEA算法相近。但是,TRFEA算法使用的聚類方法適合處理批量任務,隨著任務數量的增加,總的任務需求提取時間少于IKAnalyzer算法和傳統的LCS算法的,如圖6所示,此處選用的任務文本長度在[200,400]。 Figure 6 Relationship of execution time and the number of tasks圖6 執行時間與任務數量的關系 綜上分析,本文的TRFEA算法適用于任務需求的提取,準確率高于IKAnalyzer算法和傳統的LCS算法的,處理多個任務的效率也優于兩者。 6.2.3 任務分發效率 在相同時間內對TRIM模型、LR模型和本文TREAULCM模型進行任務分發率(Tdr)對比,結果如圖7所示。通過式(18)計算Tdr: (18) 其中,Tdrp表示單位時間內成功分發的任務個數;Tdrs表示單位時間內待分發任務的總數。假設每小時待分發的任務數為500個,任務分發率越高,模型效率越高。 從圖7可以看出,在相同時間內TREAULCM的任務分發率明顯大于LR模型的,略大于TRIM模型的。這是由于隨著任務數量的增加,多線性神經網絡訓練模型不斷最小化損失函數,并更新網絡中各個參數使任務分配模型不斷完善。因此,TREAULCM的任務分發率更高。 Figure 7 Comparison of task distribution rate圖7 任務分發率對比 6.2.4 感知任務與用戶的匹配度 為了驗證文本模型對任務與用戶匹配的準確性,本文選擇了基于空間權值向量的余弦度量法計算任務-用戶匹配度。將任務的類別關鍵詞和用戶標簽抽象為詞語向量,余弦度量法通過計算兩者的夾角余弦值得到任務-用戶匹配度。具體過程如下: 假設Wd={wd1,wd2,…,wdε}是任務taski的描述Ti和用戶userj的類型標簽YLabj的所有詞集合。taski的類別關鍵詞Labi在Wd中的出現次數為c1i(1≤i≤ε);用戶userj的類型標簽在Wd中的出現次數為c2i(1≤i≤ε),分別可以表示為向量Mi=(c11,c12,…,c1ε)和Nj=(c21,c22,…,c2ε)。任務-用戶匹配度計算如下所示: (19) 表2為根據式(19)計算TRIM模型、LR模型和TREAULCM對MSRC-v2數據集上不同類別的平均任務-用戶匹配度。從表2可以看出,TREAULCM模型對不同類別任務的識別度更高,這表明TREAULCM模型具有準確性高的優點。 任務-用戶匹配度越大,表明用戶完成該類別任務的優勢越大。圖8表明隨著任務數量的增加,TREAULCM的平均任務-用戶匹配度略高于TRIM模型的,明顯高于LR模型的。這是因為無論采用余弦相似度計算方法的用戶選擇激勵模型TRIM還是基于邏輯回歸(LR)方法的任務分配模型,在用戶選擇上依賴固定的設置,缺乏靈活性;而本文的用戶標簽分類方法不斷調整分類器的最優參數,隨著任務數量和迭代次數的增加,用戶標簽不斷更新,使任務與用戶的匹配有更高的準確性。因此,本文模型在用戶選擇方面有較大的優勢。 Figure 8 Relationship of number of tasks and average task-user matching圖8 任務數量與平均任務-用戶匹配度的關系 本文針對群智感知中的任務分配問題,提出了一種面向任務需求的任務分配模型。由于任務需求具有多元性,本文首先通過TRFEA算法提取感知任務的類別關鍵詞;然后通過用戶標簽分類方法得到用戶類型標簽,根據任務類別、空間位置信息和用戶參與度選擇滿足任務需求的用戶分發任務。仿真結果表明,與其他模型相比,本文提出的模型能以較少的時間開銷相對準確地選擇合適的用戶執行任務,能夠批量處理用戶數據,適合大宗任務分發。然而現實中任務平臺和用戶任務交互過程復雜且受到的隨機干擾因素眾多,可能會影響用戶類型標簽的預測。本文模型對隨機因素的考慮還不夠全面,針對這個問題進行改進是下一步研究的重點。 Table 2 Average task-user matching degree of different task types in three models表2 3種模型對不同任務類別的平均任務-用戶匹配度6 仿真分析
6.1 仿真環境
6.2 實驗分析





7 結束語
