張曉濱,張嘉誠

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

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

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

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

1 場景定義

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

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

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

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

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

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

其中,wi初始值為,ε是一個(gè)用來改進(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)計(jì)算,;5.end 6.end w wi

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

2.2 信譽(yù)的更新

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

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

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

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

算法3.累積行為信譽(yù)算法輸入:樣本集X,鄰域半徑,-鄰域最小點(diǎn)數(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 時(shí)長5.式(5)更新用戶信譽(yù);6.end

3 實(shí)驗(yàn)分析

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

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

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

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

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

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

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

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

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

4 總結(jié)

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

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

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