參與式感知系統中用戶累積行為信譽計算①

張曉濱,張嘉誠

(西安工程大學 計算機科學學院,西安 710048)

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

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

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

1 場景定義

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

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

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

2 累積行為信譽模型

2.1 累積行為信譽計算

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

其中,wi初始值為,ε是一個用來改進算法的較小數值[21],穩健平均值求權重算法如算法2.

算法2.穩健平均值求權重UserBeha={b111,···,bmix}輸入:行為集,行為分值W={w1,w2,···,wm}S={s111,···,smix}輸出:行為權重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 得到每一行為分值在信譽計算時所占的權重,再使用式(4)計算用戶信譽.

2.2 信譽的更新

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

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

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

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

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

3 實驗分析

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

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

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

圖1 場景分類結果圖

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

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

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

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

圖2 信譽計算對比圖

4 總結

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

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

圖3 信譽更新對比圖