參與式感知系統(tǒng)中用戶累積行為信譽(yù)計算①

張曉濱,張嘉誠

(西安工程大學(xué) 計算機(jī)科學(xué)學(xué)院,西安 710048)

共享經(jīng)濟(jì)和移動技術(shù)的廣泛普及推動了參與式感知的發(fā)展,大量基于智能手機(jī)的參與式感知系統(tǒng)被人們重視并應(yīng)用到現(xiàn)實生活中[1],如任務(wù)分配[2]、數(shù)據(jù)轉(zhuǎn)發(fā)[3]、在線社區(qū)[4]、昆蟲監(jiān)視[5]、空氣污染監(jiān)測[6]等.由于感知數(shù)據(jù)是由普通參與者自愿收集并共享,因而錯誤操作或惡意貢獻(xiàn)者很大程度上會降低數(shù)據(jù)質(zhì)量.如何提高感知數(shù)據(jù)質(zhì)量及數(shù)據(jù)使用率越來越引起學(xué)者重視和研究.

在感知數(shù)據(jù)質(zhì)量方面,部分學(xué)者主要針對低質(zhì)量數(shù)據(jù)問題展開研究,文獻(xiàn)[7]建議使用信譽(yù)管理對所收集的數(shù)據(jù)進(jìn)行分類,以向數(shù)據(jù)分析員提供有用信息;文獻(xiàn)[8]在處理低質(zhì)量數(shù)據(jù)的同時考慮私人數(shù)據(jù)的機(jī)密性,提出了線性盲回歸建模方式,該模型在不了解本地私有數(shù)據(jù)的情況下既可以收集參與者感知數(shù)據(jù)又可以有效地建立全局線性回歸模型的最佳估計,以幫助檢測感知數(shù)據(jù);文獻(xiàn)[9]提出基于累積聲譽(yù)模型提高數(shù)據(jù)質(zhì)量,該模型通過對參與者歷史感知數(shù)據(jù)質(zhì)量及參與頻率的積累,識別并減少不良影響以獲得較準(zhǔn)確的感應(yīng)結(jié)果;文獻(xiàn)[10,11]等基于低質(zhì)量數(shù)據(jù)研究進(jìn)行了深入探索,以便能夠很好地區(qū)分高質(zhì)量與低質(zhì)量數(shù)據(jù).但上述研究并沒有考慮將數(shù)據(jù)質(zhì)量與影響數(shù)據(jù)質(zhì)量的參與者關(guān)聯(lián),以減少惡意貢獻(xiàn)者或數(shù)據(jù)篡改者對數(shù)據(jù)真實性的影響.部分學(xué)者針對可能影響數(shù)據(jù)質(zhì)量的參與者展開研究,文獻(xiàn)[12]以參與者行為為研究起點,從時間、空間兩個方面分析感知用戶的行為及感知活動空間,但未分析行為因素與參與者自身或感知數(shù)據(jù)質(zhì)量之間的聯(lián)系;文獻(xiàn)[13]通過考慮參與者的時空可用性解決參與者選擇問題,以選擇有效的參與者繼而提高數(shù)據(jù)質(zhì)量;文獻(xiàn)[14]主要針對影響參與者貢獻(xiàn)度的激勵機(jī)制和隱私問題提出了一種通用的隱私感知激勵方案,以減少用戶對隱私泄露的擔(dān)憂,提高用戶主動參與性.上述研究雖對數(shù)據(jù)質(zhì)量或影響數(shù)據(jù)質(zhì)量的參與者因素展開了研究,但在進(jìn)行參與者研究時,也可以考慮通過對用戶可信度的分析提高對信賴參與者的選擇,從而提高數(shù)據(jù)質(zhì)量.

為提高感知用戶可信度分析的真實性與可靠性,本研究提出了基于用戶累積行為的信譽(yù)計算模型.首先,該模型在考慮實現(xiàn)感知環(huán)境累積行為信譽(yù)計算時參與者數(shù)量龐大、分布廣泛的前提下,采用OPTICS算法在降低對輸入?yún)?shù)敏感度的同時對行為數(shù)據(jù)集進(jìn)行聚類處理,實現(xiàn)場景定義;其次,考慮到實際應(yīng)用中感知用戶行為的多樣性,為避免用戶單一行為的偽裝對信譽(yù)判斷的錯誤影響,提出融合多行為的累積行為信譽(yù)計算模型;最后,考慮用戶行為對信譽(yù)判斷的影響度可能隨時間增加而降低,通過引入時間戳標(biāo)記拋棄部分舊行為實現(xiàn)信譽(yù)更新.

1 場景定義

在實際感知環(huán)境中,由于參與用戶數(shù)量龐大、分布廣泛.因此,在進(jìn)行信譽(yù)計算時如何高效、精確地選取所需用戶成為感知信譽(yù)研究中需要解決的首要問題.通常,用戶分類或場景定義通過發(fā)現(xiàn)用戶之間的潛在聯(lián)系解決分布廣泛的問題,幫助選擇具備某些特征或符合條件的用戶.學(xué)者們針對場景分類問題展開了一系列研究并提出多種可用方法[15–20],但針對感知環(huán)境中的用戶復(fù)雜性、行為多樣性以及核心用戶不確定性等特殊問題,本文使用OPTICS 聚類算法對用戶進(jìn)行場景分類,該算法可以降低數(shù)據(jù)集對輸入?yún)?shù)的敏感度,幫助獲取不同鄰域半徑的簇集,有助于選擇合適的用戶及行為集進(jìn)行累積信譽(yù)計算.

OPTICS 算法在對行為數(shù)據(jù)集進(jìn)行聚類時,首先遍歷樣本集X,尋找所有符合其ε-鄰域內(nèi)樣本點數(shù)大于鄰域最小點數(shù)MinPts的樣本點,并將這些樣本點加入核心對象集合.其次,隨意選擇一個未處理的核心對象xi,通過對xi與其ε-鄰域內(nèi)未訪問的樣本點(xj)間的可達(dá)距離排序得到有序列表決策圖.最后,通過決策圖可以得到 ε取不同值時的行為數(shù)據(jù)聚類結(jié)果.(可達(dá)距離是指xi的核心距離和xi>與xj歐幾里得距離間的最大值,核心距離是指使xi成為核心對象的最小距離).算法偽代碼如算法1.

算法1.OPTICS 算法輸入:樣本集X,鄰域半徑,-鄰域最小點數(shù)MinPts,種子集合Seeds輸出:有序樣本點varepsilonε 1.初始化核心對象集合;?=?2.遍歷X 的元素,如果是核心對象,則將其加入到核心對象集合 中;X≠??3.while do?4.for 中所有核心對象,隨機(jī)選擇一個未處理的核心對象 并標(biāo)記為已處理,同時加入有序列表p;xi ε x jx j xi 5.計算 與-鄰域中所有 的可達(dá)距離,并將 插入到根據(jù)可達(dá)距離排序的種子集合Seeds 中;S eeds=?6.if執(zhí)行步驟4;else 選擇Seeds 中可達(dá)距離最近的點seed,標(biāo)記為已處理同時將其壓入有序列表p;7.if seed 不是核心對象執(zhí)行步驟6;else 將seed 的所有鄰居點加入到種子集合,重新計算可達(dá)距離,執(zhí)行步驟6;8.end 9.end

2 累積行為信譽(yù)模型

2.1 累積行為信譽(yù)計算

采用OPTICS 算法得到不同場景下的行為數(shù)據(jù)集,定義上述獲得的場景集Beha={bi1,bi2,···,bkx}(i=1,2,···,k表示共有k個場景),每一場景下的行為集UserBeha=(m=1,2,···,m表示第m個行為)中可以得到x用戶的m個行為.對比同一場景中同一行為下不同用戶的執(zhí)行結(jié)果,通過每一個結(jié)果的出現(xiàn)率和偏差率給出對該行為真實性與可信度判斷的初步分值,并存入行為分值集S=中,使用穩(wěn)健平均值迭代算法[10]計算每一行為分值在信譽(yù)計算中所占權(quán)重wm,所有行為的權(quán)重集可以表示為W={w1,w2,···,wm}.具體計算方法如下:

其中,wi初始值為,ε是一個用來改進(jìn)算法的較小數(shù)值[21],穩(wěn)健平均值求權(quán)重算法如算法2.

算法2.穩(wěn)健平均值求權(quán)重UserBeha={b111,···,bmix}輸入:行為集,行為分值W={w1,w2,···,wm}S={s111,···,smix}輸出:行為權(quán)重1.for i=1 to m wi=1 2.初始化;wmi?wm?1i 3.while 收斂 do m 4.式(1)～式(3)計算,;5.end 6.end w wi

通過算法2 得到每一行為分值在信譽(yù)計算時所占的權(quán)重,再使用式(4)計算用戶信譽(yù).

2.2 信譽(yù)的更新

用戶行為的時效性主要體現(xiàn)在其在信譽(yù)計算中的影響度可能隨時間的增加而降低,因而本文在進(jìn)行累積行為計算時引入時間戳標(biāo)記信息,減少舊行為對信譽(yù)的影響并及時更新用戶信譽(yù).

研究中將時間軸劃分為若干個長度為t0的時間窗口,定義每一行為的初始時間為tini,計算信譽(yù)的當(dāng)前時間為tend,|tend?tini|時間段內(nèi)存在j個時間窗口且用戶在這一時間段內(nèi)行為i(i=1,2,···,m)的發(fā)生頻數(shù)為k,則基于時間因素更新用戶信譽(yù)的計算函數(shù)如下:

其中,Repg表示第g個時間窗口的用戶信譽(yù).為時間衰減函數(shù),λ為可主觀設(shè)定的時間調(diào)節(jié)系數(shù)[21],g越大距離當(dāng)前信譽(yù)計算時間間隔越長,時間衰減函數(shù)值越小,則該時間窗口的信譽(yù)值在用戶信譽(yù)更新時所占比重越小.

通過對累積行為信譽(yù)計算模型中場景定義、信譽(yù)計算、信譽(yù)更新的描述,得到累積行為信譽(yù)算法如算法3.

算法3.累積行為信譽(yù)算法輸入:樣本集X,鄰域半徑,-鄰域最小點數(shù)MinPts,種子集合Seeds,行為集,行為分值Rep?n={Repnew1,Repnew2,···,Repnewn εε UserBeha={b111,···,bmix}S={s111,···,smix}輸出:用戶信譽(yù)值}1.執(zhí)行算法1,場景定義;?UserBeha 2.if 新行為執(zhí)行步驟1;3.else 執(zhí)行算法 2;4.if 經(jīng)歷t0 時長5.式(5)更新用戶信譽(yù);6.end

3 實驗分析

實驗采用SNAP 公布的Bitcoin Alpha trust weighted signed network 數(shù)據(jù)集[22,23].該數(shù)據(jù)集信息來源Alpha平臺下5 種不同網(wǎng)絡(luò)環(huán)境下比特幣交易的用戶信譽(yù)信息,包含3783 個用戶節(jié)點,24 186 條用戶交互邊,每條邊的權(quán)值從?10 到10 不等,其中積極數(shù)據(jù)集占總數(shù)據(jù)集的93%.本文選取任意一個網(wǎng)絡(luò)下的用戶交互信息進(jìn)行實驗,實驗先對這些數(shù)據(jù)進(jìn)行統(tǒng)一處理,形成包含源用戶ID、目標(biāo)用戶ID、源用戶對目標(biāo)用戶的行為分值和用戶初始信譽(yù)4 個字段的數(shù)據(jù)集.

為驗證累積行為及時間戳概念能夠較準(zhǔn)確的計算并更新信譽(yù)值,首先使用OPTICS 算法對隨機(jī)選取數(shù)據(jù)集中的500 條行為數(shù)據(jù)進(jìn)行聚類處理,得到有序列表決策圖和可視化分類圖,結(jié)果如圖1所示.

圖1(a)圖為有序列表決策圖,圖1(b)為可視化聚類結(jié)果圖.從決策圖可以看出實驗數(shù)據(jù)集被分為5 個類別(決策圖的每一個凹槽代表1個類別).從這5 個類別的行為數(shù)據(jù)集中隨機(jī)選取a、b、c 三組進(jìn)行以下兩組對比實驗.

圖1 場景分類結(jié)果圖

(1)對比單一行為、累積行為計算的用戶信譽(yù)及用戶的真實信譽(yù).

從圖2信譽(yù)計算對比圖可以看出,使用累積行為計算用戶信譽(yù)更貼近真實信譽(yù).從圖2(a)可以看出,a 組數(shù)據(jù)中僅有7.36%的單一行為信譽(yù)比累積行為信譽(yù)更貼近真實信譽(yù),相反,有92.64%的累積行為信譽(yù)更貼近真實信譽(yù);從圖2(b)可以看出,b 組數(shù)據(jù)中有10.27%的單一行為信譽(yù)比累積行為信譽(yù)更貼近真實信譽(yù),3.63%的單一行為信譽(yù)與累積行為信譽(yù)相等,但有86.1%的累積行為信譽(yù)更貼近真實信譽(yù);從圖2(c)可以看出,c 組數(shù)據(jù)中僅有2.46%的單一行為信譽(yù)比累積行為信譽(yù)更貼近真實值,而有97.54%的累積行為信譽(yù)更貼近真實值.

(2)對比未引入時間戳的用戶信譽(yù)及引入時間戳的信譽(yù)更新值.

從圖3信譽(yù)更新對比圖可以看出,引入時間戳概念對用戶信譽(yù)進(jìn)行更新,能夠減少舊行為的不恰當(dāng)影響,得到較為準(zhǔn)確的信譽(yù)值.從圖3(a)可以看出,在a 組數(shù)據(jù)中僅有2.46%的更新信譽(yù)值與未更新信譽(yù)值相等,而有62.38%的更新信譽(yù)值更貼近真實信譽(yù)值且有36.69%的更新信譽(yù)值與真實信譽(yù)值相等;從圖3(b)可以看出,在b 組數(shù)據(jù)中僅有2.46%的未更新信譽(yù)值更貼近真實信譽(yù),但65.36%的更新信譽(yù)值更貼近真實信譽(yù)值且有33.78%的更新信譽(yù)值與真實信譽(yù)相等;從圖3(c)可以看出,在c 組數(shù)據(jù)中所有更新信譽(yù)值的效果均優(yōu)于未更新信譽(yù)值,且有30.27%的更新信譽(yù)值與真實信譽(yù)相等.

圖2 信譽(yù)計算對比圖

4 總結(jié)

本文針對感知用戶信譽(yù)計算過程中行為多樣性的影響和信譽(yù)更新的問題,提出基于累積行為的信譽(yù)計算模型.該模型結(jié)合OPTICS 算法對用戶行為場景定義,基于用戶分類結(jié)果再使用穩(wěn)健平均值迭代算法調(diào)整每一行為在累積信譽(yù)計算中的比重,最后引入時間戳標(biāo)記剔除較久發(fā)生的行為,實現(xiàn)用戶信譽(yù)更新.

該信譽(yù)計算模型能夠考慮到用戶行為的多樣性及時效性,對用戶信譽(yù)有一個較為準(zhǔn)確的判斷,使感知用戶的信譽(yù)計算更加具有客觀性,符合實際生活規(guī)律,有助于感知環(huán)境中的參與者選擇.后期可考慮根據(jù)所更新的用戶信譽(yù)進(jìn)行可信賴社區(qū)探索.

圖3 信譽(yù)更新對比圖