基于情境分析的移動(dòng)社交網(wǎng)絡(luò)群體任務(wù)分配

王小雪，張志勇，史培寧

(河南科技大學(xué) 信息工程學(xué)院，河南 洛陽(yáng) 471023)

0 引 言

群體計(jì)算[1]旨在整合互聯(lián)網(wǎng)上大量未知用戶(人群)和計(jì)算資源(機(jī)群)來(lái)處理現(xiàn)有計(jì)算技術(shù)難以完成的復(fù)雜任務(wù)。在群體計(jì)算的研究中，任務(wù)分配問(wèn)題是核心問(wèn)題之一，該問(wèn)題研究如何將實(shí)時(shí)出現(xiàn)的群體任務(wù)分配給適宜的用戶。現(xiàn)有工作[2]通常基于靜態(tài)場(chǎng)景，即全部群體任務(wù)與用戶的信息在任務(wù)分配前已經(jīng)完整獲知，較少融合用戶多維環(huán)境信息[3]，且很少考慮到用戶的屬性信息與歷史記錄，但群體任務(wù)在實(shí)際應(yīng)用中動(dòng)態(tài)出現(xiàn)，且需實(shí)時(shí)地對(duì)其進(jìn)行任務(wù)分配。上下文感知[4-6]在1994年被提出，并將情景定義為位置，周邊的人和對(duì)象的集合和這類(lèi)對(duì)象的變化。Carl K.Chang[7]提出了情境分析理論，并基于此理論提出Situ架構(gòu)，該架構(gòu)能夠通過(guò)分析用戶歷史行為數(shù)據(jù)獲取用戶的實(shí)時(shí)意圖，從而為用戶提供實(shí)時(shí)并且個(gè)性化的服務(wù)。張等[8]在上述理論的基礎(chǔ)上建立了SocialSitu理論，提出了一種面向在線社交網(wǎng)絡(luò)用戶的行為模式發(fā)現(xiàn)方法，通過(guò)分析用戶的歷史行為數(shù)據(jù)，預(yù)測(cè)用戶下一時(shí)刻意圖。因此，在此研究的基礎(chǔ)上，通過(guò)分析移動(dòng)社交用戶的SocialSitu(t)序列和歷史信息提出了面向移動(dòng)在線社交網(wǎng)絡(luò)的任務(wù)分配架構(gòu)，進(jìn)一步提出基于SocialSitu的用戶適合度任務(wù)分配算法并通過(guò)實(shí)驗(yàn)驗(yàn)證算法的適用性。

1 任務(wù)分配架構(gòu)

本文所提出的面向在線社交網(wǎng)絡(luò)的群體計(jì)算系統(tǒng)架構(gòu)的目的在于為社交網(wǎng)絡(luò)中的用戶分配合適的任務(wù)，因此需滿足3個(gè)基本需求：①在社交網(wǎng)絡(luò)中找到最適合某項(xiàng)任務(wù)的移動(dòng)用戶群體；②服務(wù)端可以自主設(shè)計(jì)、發(fā)布、評(píng)價(jià)任務(wù)；③提供用戶執(zhí)行任務(wù)的接口，因此本文設(shè)計(jì)了一個(gè)層次架構(gòu)以滿足這些要求，群體計(jì)算系統(tǒng)架構(gòu)如圖1所示。具體的分層架構(gòu)設(shè)計(jì)如下：

(1)社交平臺(tái)設(shè)施層

第一層是社交平臺(tái)設(shè)施層，其中社交媒體平臺(tái)服務(wù)器設(shè)計(jì)并發(fā)布群體計(jì)算任務(wù)。該層的主要功能是待用戶完成任務(wù)并回傳數(shù)據(jù)至本層時(shí)，平臺(tái)設(shè)施層對(duì)用戶返回的數(shù)據(jù)進(jìn)行處理，處理結(jié)果將作為下次該用戶分配任務(wù)的參考，同時(shí)更新群體的信息。

(2)數(shù)據(jù)處理中間層

第二層是數(shù)據(jù)處理中間層，數(shù)據(jù)傳輸鏈將社交平臺(tái)設(shè)施層的群體用戶數(shù)據(jù)傳遞至數(shù)據(jù)處理中間層，本層分析用戶的訪問(wèn)行為(如：登錄)與歷史信息(如：成功率)，根據(jù)基于SocialSitu的用戶適合度任務(wù)分配算法尋找合適的用戶。同時(shí)，本層還整理、分析、存儲(chǔ)來(lái)自群體用戶應(yīng)用層的結(jié)果數(shù)據(jù)。

(3)群體用戶應(yīng)用層

第三層是群體用戶應(yīng)用層，本層包括不同種類(lèi)的群體應(yīng)用，并提供群體用戶接口。用戶加入群體任務(wù)后，可以轉(zhuǎn)發(fā)任務(wù)興趣相投的好友，待執(zhí)行任務(wù)之后，用戶將結(jié)果數(shù)據(jù)返回至數(shù)據(jù)處理中間層處理。

圖1 任務(wù)分配架構(gòu)

2 基于SocialSitu的用戶適合度任務(wù)分配算法

移動(dòng)社交用戶具有移動(dòng)性、隨機(jī)性和復(fù)雜性等特征，因此面向移動(dòng)社交網(wǎng)絡(luò)用戶群體的任務(wù)分配不單單要著重考慮用戶的可信度和服務(wù)能力，而且更要關(guān)注用戶的訪問(wèn)行為的變化及歷史服務(wù)信息等因素。考慮到影響任務(wù)分配的因素，本文通過(guò)分析移動(dòng)社交用戶的歷史信息定義了影響任務(wù)分配的屬性，由這些屬性計(jì)算得出的用戶任務(wù)適合度即用戶適合某項(xiàng)任務(wù)的程度。

2.1 相關(guān)定義

定義1 SocialSitu (t)：定義請(qǐng)參見(jiàn)文獻(xiàn)[8]。

定義2 成功率Ssucc為移動(dòng)用戶成功完成歷史任務(wù)的比例，如式(1)所示，其中Nsucc為歷史服務(wù)成功次數(shù)，Ntotal為歷史服務(wù)總次數(shù)

(1)

定義3 平均服務(wù)應(yīng)答時(shí)間Sdel為平臺(tái)分配任務(wù)到移動(dòng)用戶接受任務(wù)的時(shí)間間隔，如式(2)所示，其中d(hj)為歷史任務(wù)hj的應(yīng)答時(shí)間(hj∈H)，sdel(Ui)為平臺(tái)分配任務(wù)的時(shí)間，e(Ui)為用戶Ui接受任務(wù)的時(shí)間，H為用戶歷史信息

(2)

定義4 滿意度Ssat為用戶對(duì)于系統(tǒng)為其分配的任務(wù)的滿意程度，如式(3)所示，其中s(hj)為用戶對(duì)平臺(tái)分配歷史任務(wù)hj的滿意度(hj∈H)，ρ(式(4))為衰減因子，它是一種隨時(shí)間變化而動(dòng)態(tài)衰減的量，即所隔時(shí)間越久，用戶滿意度對(duì)服務(wù)決策的影響越小

(3)

(4)

定義5 用戶適合度是評(píng)價(jià)用戶適合執(zhí)行某項(xiàng)任務(wù)的程度。由以上成功率、平均服務(wù)應(yīng)答時(shí)間、滿意度計(jì)算得出，由式(5)所示，適合度越大表示用戶越適合此項(xiàng)任務(wù)。其中wij表示用戶i的第j個(gè)屬性，αit表示對(duì)于任務(wù)t，用戶Ui的第j個(gè)屬性duj所占的權(quán)重，p為屬性的個(gè)數(shù)

(5)

2.2 分配算法

為實(shí)時(shí)準(zhǔn)確地為移動(dòng)社交用戶分配任務(wù)，采用的基于SocialSitu(t)的用戶意圖序列化算法可根據(jù)用戶的歷史行為的SocialSitu序列實(shí)時(shí)地預(yù)測(cè)用戶在下一時(shí)刻的意圖，在了解用戶的意圖(用戶會(huì)選擇何種任務(wù))的情況下，再計(jì)算出移動(dòng)用戶的任務(wù)適合度，依據(jù)任務(wù)適合度大小分配任務(wù)。算法流程如圖2所示，具體的算法過(guò)程如下所示：

(1)獲取待完成任務(wù)的相關(guān)信息。待完成任務(wù)列表R={r1,r2,…rn}，遍歷i(1≤i≤n)個(gè)任務(wù)ri的ID，需要完成該項(xiàng)任務(wù)的人數(shù)K，待完成任務(wù)的類(lèi)別庫(kù)C，以及任務(wù)完成的截止時(shí)間T。

(2)在用戶列表中獲取用戶的歷史信息，計(jì)算出包括用戶的完成度Ssucc，平均服務(wù)應(yīng)答時(shí)間Sdel，滿意度Ssat。

(3)如果用戶u當(dāng)前在線，則跳到步驟(4)，如果用戶u為離線用戶，則跳到步驟(8)。

(4)對(duì)在線用戶u的歷史SocialSitu(t)信息進(jìn)行分析處理，并通過(guò)用戶行為模式發(fā)現(xiàn)算法SituBehaviorAnalytics(DS, Min_Support, G)獲得用戶u的行為序列模式。

(5)將用戶u對(duì)應(yīng)特定意圖的行為序列模式存儲(chǔ)，Compare(Social(0)u,Social(1)u,…,SocialSitu(t-1)u),uBehaviorpattern[intention]函數(shù)將用戶u當(dāng)前行為與行為模式序列進(jìn)行對(duì)比，并預(yù)測(cè)用戶u下一刻意圖。

(6)如果用戶u的意圖與待完成任務(wù)ri的類(lèi)別C相關(guān)，則將用戶u的ID存入待分配任務(wù)的用戶集合U。

(7)計(jì)算用戶u對(duì)于待完成任務(wù)ri的適合度Sui。

(8)計(jì)算出所有對(duì)于待分配任務(wù)ri的用戶的適合度，按照適合度從高到低進(jìn)行排序，選出被分配的用戶集合L，將任務(wù)ri分配給L中的所有用戶。

(9)重復(fù)步驟(1)～(7)直到不再有新的未分配的任務(wù)。

圖2 算法流程

算法1：任務(wù)分配算法

Input: 用戶集合：U， 用戶歷史信息：H， 用戶的情境信息： SocialSitu(t)， 待完成任務(wù)集合：T， 待分配任務(wù)用戶集合：UT， 所需人數(shù)：K

Output: 待分配任務(wù)的用戶的UserID

TaskAssign(UT, T)

(1)Begin

(2)foreachri∈Randi←1ton

(3)foreachu∈UandSsucc、Sdel、Ssat

(4)ifu is online

(5)u.Behaviorpattern[intentionm]=SituBehaviorAnlytics(DS,Min_Support,G);

(6)foreach intentionm∈Intention

(7)Compare(Social(0)u,Social(1)u,…SocialSitu(t+1)u),uBehaviorpattern[intention]

(8)ifintentionut=intentionm

(9)ifintentionut∈C

(10)u∈UT

(11)endif

(12)endif

(13)foreachu∈UT

(15)endfor

(16)endif

(17)else

(18)foru∈UT

(20)endfor

(21)Rank(Sui);

(22)endfor

(23) Assign(UT, T)

(24)endfor

(25)End

其中SituBehaviorAnlytics(DS, Min_Support, G)函數(shù)指分析用戶特定意圖下的行為模式，DS為用戶行為數(shù)據(jù)集，Min_Support,為最小支持度，G為用戶的意圖。Compare(Social(0)u,Social(1)u,…,SocialSitu(t-1)u),uBehaviorpattern[intention]函數(shù)指將用戶當(dāng)前行為與行為模式進(jìn)行對(duì)比[8]。

3 實(shí)驗(yàn)與結(jié)果

本文所采用的實(shí)驗(yàn)平臺(tái)是在線社交網(wǎng)絡(luò)平臺(tái)CyVOD[9](www.cyvod.net)和CyVOD客戶端應(yīng)用。該平臺(tái)架構(gòu)如圖3所示。CyVOD平臺(tái)作為設(shè)計(jì)、發(fā)布、分配任務(wù)的服務(wù)端，如圖4所示。客戶端則作為用戶申請(qǐng)、執(zhí)行、反饋、轉(zhuǎn)發(fā)任務(wù)的應(yīng)用端，如圖5所示。

圖3 CyVOD體系架構(gòu)

圖4 服務(wù)端任務(wù)分配界面

圖5 客戶端執(zhí)行任務(wù)界面

3.1 實(shí)驗(yàn)設(shè)計(jì)

移動(dòng)社交網(wǎng)絡(luò)作為人類(lèi)傳播信息、進(jìn)行社會(huì)交流活動(dòng)的平臺(tái)，引發(fā)了廣泛的應(yīng)用和關(guān)注。當(dāng)今社交網(wǎng)絡(luò)平臺(tái)上的安全隱私問(wèn)題的凸顯，亟需社交網(wǎng)絡(luò)用戶對(duì)平臺(tái)功能、安全防范、隱私保護(hù)等功能進(jìn)行評(píng)估[10-12]。根據(jù)當(dāng)前社交網(wǎng)絡(luò)中普遍存在的安全問(wèn)題，本文設(shè)計(jì)了7項(xiàng)社交平臺(tái)群體評(píng)估任務(wù)，分別對(duì)社交網(wǎng)絡(luò)平臺(tái)的安全信任等方面進(jìn)行評(píng)估，評(píng)估內(nèi)容見(jiàn)表1。群體評(píng)估的流程如圖6所示。

3.2 實(shí)驗(yàn)結(jié)果

為驗(yàn)證所提算法的正確性，因此與隨機(jī)分配和基于用戶屬性兩種任務(wù)分配算法進(jìn)行對(duì)比。隨機(jī)任務(wù)分配算法即不考慮用戶的多維屬性與影響因子，只是簡(jiǎn)單隨機(jī)地選取用戶后分配任務(wù)。操作簡(jiǎn)單但無(wú)針對(duì)性，因此用戶完成度，反饋率均較低。基于用戶屬性分配算法充分考慮用戶的多維屬性與影響因子，但是不考慮用戶的行為與意圖，因此提出的基于SocialSitu算法綜合二者優(yōu)點(diǎn)，取長(zhǎng)補(bǔ)短。既充分分析了用戶的行為與意圖，還綜合考量了多維屬性與影響因子。

表1 群體評(píng)估任務(wù)

圖6 群體評(píng)估流程

3.2.1 正確性分析

表2是通過(guò)基于SocialSitu(t)的用戶意圖序列化算法根據(jù)用戶的歷史行為的SocialSitu序列得出用戶的行為模式，并實(shí)時(shí)地預(yù)測(cè)出的下一時(shí)刻的意圖。

表2 基于SocialSitu的用戶行為模式與意圖

表3是采用隨機(jī)分配算法所得出的實(shí)驗(yàn)數(shù)據(jù)，表4是采用基于用戶屬性的任務(wù)分配算法所得出的實(shí)驗(yàn)數(shù)據(jù)，表5是采用基于SocialSitu的用戶適合度分配算法所得出的實(shí)驗(yàn)數(shù)據(jù)，很顯然，隨機(jī)算法以及基于用戶屬性分配算法所選取的用戶并沒(méi)有及時(shí)反饋信息，從而導(dǎo)致用戶完成率低下，用戶對(duì)平臺(tái)的所分配任務(wù)的滿意程度也較低，相對(duì)而言，基于SocialSitu的用戶適合度分配算法大大提高了用戶的完成率與用戶滿意度。

表3 隨機(jī)算法任務(wù)分配及回收情況

表4 基于用戶屬性的任務(wù)分配及回收情況

表5 基于SocialSitu的用戶適合度任務(wù)分配及回收情況

3.2.2 有效性分析

為驗(yàn)證所提算法有效性，比較同一任務(wù)下用戶的適合度，如圖7所示，用戶ID為9，8，5更適合此項(xiàng)任務(wù)。在總體任務(wù)數(shù)相同的基礎(chǔ)上分別比較采用3種算法整體用戶的任務(wù)平均完成度和滿意度，實(shí)驗(yàn)結(jié)果如圖8和圖9所示。通過(guò)3種分配算法的對(duì)比結(jié)果可以得出基于SocialSitu的用戶適合度分配算法在提高用戶任務(wù)完成度與用戶滿意度方面效果顯著，用戶整體平均完成度較隨機(jī)和基于屬性的分配算法提高平均0.4和0.2左右，平均滿意度提高平均0.1和0.2左右，因此可說(shuō)明基于SocialSitu的用戶適合度任務(wù)分配算法優(yōu)勢(shì)明顯。

圖7 用戶適合度對(duì)比情況

圖8 3種算法的整體用戶完成度比較

圖9 3種算法的整體用戶滿意度比較

4 結(jié)束語(yǔ)

在線社交網(wǎng)絡(luò)的迅速發(fā)展，移動(dòng)設(shè)備的普及使得在線社交網(wǎng)絡(luò)中含有豐富的計(jì)算資源，為了充分地利用這些資源，本文提出了一種面向移動(dòng)社交網(wǎng)絡(luò)群體的任務(wù)分配架構(gòu)，同時(shí)提出了基于SocialSitu的用戶適合度任務(wù)分配算法，通過(guò)分析用戶的訪問(wèn)行為、歷史信息為用戶分配適合的任務(wù)，并通過(guò)群體評(píng)估實(shí)驗(yàn)驗(yàn)證了算法的有效性。該算法的分配準(zhǔn)確率和用戶完成度較高，運(yùn)算速度還較慢。在后續(xù)研究中，考慮利用機(jī)器學(xué)習(xí)中的關(guān)聯(lián)規(guī)則解決此問(wèn)題。