趙冠哲，齊建鵬，于彥偉，劉兆偉，宋鵬

(煙臺大學(xué) 計算機與控制工程學(xué)院，山東 煙臺 264005)

移動社交網(wǎng)絡(luò)異常簽到在線檢測算法

趙冠哲，齊建鵬，于彥偉，劉兆偉，宋鵬

(煙臺大學(xué) 計算機與控制工程學(xué)院，山東 煙臺 264005)

隨著智能手機、Pad等智能移動設(shè)備的廣泛普及，移動社交網(wǎng)絡(luò)的應(yīng)用得到了快速發(fā)展。 本文針對移動社交網(wǎng)絡(luò)中用戶異常簽到位置檢測問題，提出了一類基于用戶移動行為特征的異常簽到在線檢測方法。 首先，在基于距離的異常模型基礎(chǔ)上，提出了基于歷史位置 (H-Outlier)和基于好友圈 (F-Outlier)兩種異常簽到模型；然后，針對H-Outlier提出了一種優(yōu)化的檢測算法H-Opt，利用所提的簽到狀態(tài)模型與優(yōu)化的鄰居搜索機制降低檢測時間；針對F-Outlier提出了一種基于觸發(fā)的優(yōu)化檢測算法F-Opt，將連續(xù)的在線異常檢測轉(zhuǎn)化成了基于觸發(fā)的異常檢測方式；最后，在真實的移動社交網(wǎng)絡(luò)用戶簽到數(shù)據(jù)集上，驗證了所提算法的有效性。實驗結(jié)果顯示，F(xiàn)-Opt顯著降低了H-Opt的異常檢測錯誤率；同時，相比于LUE算法，F(xiàn)-Opt和H-Opt的效率分別平均提升了2.34倍和2.45倍。

移動社交網(wǎng)絡(luò)；異常檢測；簽到位置；基于距離的異常；好友圈；簽到狀態(tài)；鄰居搜索；時間觸發(fā)檢測

隨著GPS終端、Pad、智能手機等位置感知設(shè)備的廣泛普及，各類新型社交網(wǎng)絡(luò)手機應(yīng)用不斷涌現(xiàn)，促使移動社交網(wǎng)絡(luò)(mobile social networks)得到了快速發(fā)展。移動社交網(wǎng)絡(luò)也稱基于位置的社交網(wǎng)絡(luò)(location-based social networks, LBSN)，本質(zhì)是提供一個在人群中分享興趣、愛好、狀態(tài)和活動等信息的平臺[1]。如國內(nèi)的騰訊QQ、微信、新浪微博、人人網(wǎng)，國外的Twitter、Facebook、Gowalla、Foursquare等，這些LBSN應(yīng)用聚集了大量移動用戶。據(jù)We Are Social公司在2016年數(shù)字報告[2]中指出，2016年全球社交網(wǎng)絡(luò)用戶約19.7億，占全球總?cè)丝诘?7%。LBSN中海量帶有位置信息的社會媒體數(shù)據(jù)可被用于各類挖掘應(yīng)用研究，如挖掘用戶興趣偏好、好友推薦、興趣點推薦、熱點路徑推薦等[3]。

移動社交網(wǎng)絡(luò)正逐漸改變著人們的生活方式和生活習(xí)慣，給人類社會帶來前所未有的變革以及巨大的經(jīng)濟收益[4]。同時它也吸引了一些不法者盜取用戶賬號及信息進行各種惡意行為，影響了用戶的正常使用，損害了用戶利益，甚至給用戶帶來了巨大的經(jīng)濟損失。因此，面向移動社交網(wǎng)絡(luò)，追蹤用戶的歷史簽到位置數(shù)據(jù)，從用戶移動行為特征視角，對用戶狀態(tài)進行在線異常檢測，這對于移動社交網(wǎng)絡(luò)的安全、用戶的隱私保護等具有重要意義。

針對移動社交網(wǎng)絡(luò)異常賬號的檢測問題，學(xué)術(shù)界和工業(yè)界都提出了大量檢測方案[5]，主要包括基于行為特征的檢測、基于內(nèi)容的檢測、基于圖的檢測和無監(jiān)督學(xué)習(xí)的異常檢測方法等。而針對移動社交網(wǎng)絡(luò)中簽到位置數(shù)據(jù)異常檢測研究還比較少。本文從用戶的移動位置特征視角對異常簽到位置進行檢測，針對移動社交網(wǎng)絡(luò)用戶異常簽到檢測問題，提出了一類基于簽到位置的在線異常檢測方法。首先，在基于距離的異常檢測基礎(chǔ)上，提出了兩種異常簽到模型，即基于歷史位置的異常簽到(history location based outlier，H-Outlier)和基于好友圈的異常簽到(friendship based outlier，F(xiàn)-Outlier)；其次，針對H-Outlier，提出了一種優(yōu)化的檢測算法H-Opt，利用優(yōu)化的檢測狀態(tài)與鄰居搜索機制降低檢測時間；然后，針對F-Outlier，基于提出的3個優(yōu)化策略，提出了一種基于觸發(fā)的優(yōu)化檢測算法F-Opt，將連續(xù)在線異常檢測轉(zhuǎn)化成了基于觸發(fā)的異常檢測方式，本文采用滑動窗口技術(shù)實現(xiàn)H-Opt和F-Opt；最后，在真實的移動社交網(wǎng)絡(luò)用戶簽到數(shù)據(jù)集上，驗證了所提算法的有效性和效率。

在移動社交網(wǎng)絡(luò)中用戶往往會在新地點進行簽到或登錄，所以H-Outlier檢測到的異常簽到地點很有可能并非真正的異常。為排除這些偽異常狀況，本文提出了好友圈的概念和基于好友圈的異常簽到模型F-Outlier，這是因為在移動社交網(wǎng)絡(luò)中50%～70%的行為可由周期行為解釋，還有10%～30%行為可根據(jù)好友關(guān)系行為解釋[6]。也就是說，在移動社交網(wǎng)絡(luò)中用戶往往與認識的好友共同出現(xiàn)在不經(jīng)常簽到的地點，如朋友聚餐、商務(wù)活動或者公務(wù)出差等。針對這些偽異常，我們通過檢測好友圈中好友簽到位置來判斷用戶的簽到是否為真正的異常簽到。

1 相關(guān)工作

Knorr和Ng[7]最早提出了基于距離的空間異常(DB-Outlier)檢測問題。給定一個數(shù)據(jù)集合，若某數(shù)據(jù)點的鄰域內(nèi)的數(shù)據(jù)個數(shù)小于給定閾值，則該數(shù)據(jù)點為基于距離的異常點。之后，Knorr等[8]將基于距離的異常模型應(yīng)用到時空軌跡數(shù)據(jù)異常檢測中。Ramaswamy等[9]提出了一種基于k近鄰的異常定義，根據(jù)數(shù)據(jù)點到第k近鄰的距離檢測出n個k近鄰距離最大的數(shù)據(jù)點作為異常點。Breunig等[10]提出另外一類基于密度的數(shù)據(jù)異常類型，通過計算本地異常因子LOF來檢測局部異常點數(shù)據(jù)，但該算法存在較高計算復(fù)雜度問題。

在數(shù)據(jù)流異常檢測方面，Yang等[11]采用滑動窗口方式在數(shù)據(jù)流上挖掘基于鄰居的模式，主要包括基于密度的聚類和基于距離的異常檢測。Angiulli等[12]通過在數(shù)據(jù)流上分析數(shù)據(jù)點是否為“safe inlier”來優(yōu)化檢測方法。Kontaki等[13]利用“safe inlier”設(shè)計了一種事件觸發(fā)的數(shù)據(jù)流異常檢測優(yōu)化算法。Cao等[14]提出了一種數(shù)據(jù)流異常檢測框架，該框架可用于處理基于距離的和基于k近鄰的兩類異常檢測模型。

針對移動對象的軌跡數(shù)據(jù)，Lee等[15]提出了一種劃分-檢測的軌跡異常檢測框架，將軌跡劃分成t-partition序列，通過計算t-partition間的距離和密度，以發(fā)現(xiàn)異常的子t-partition。Bu等[16]提出了一種連續(xù)監(jiān)控移動對象實時軌跡數(shù)據(jù)流的異常檢測算法，該方法關(guān)注在檢測單個移動對象實時軌跡數(shù)據(jù)中的異常子軌跡段。文獻[17]針對海量移動對象系統(tǒng)中異常對象，提出了一種基于鄰居的異常移動對象檢測方法，可發(fā)現(xiàn)不同于其他鄰居對象運動軌跡的異常對象。

2 問題定義

本節(jié)首先給出一些重要的定義和表示，然后對基于距離的移動社交網(wǎng)絡(luò)異常簽到模型進行描述。

本文采用基于簽到位置數(shù)量的滑動窗口W來處理移動社交網(wǎng)絡(luò)中實時的簽到數(shù)據(jù)，窗口長度標(biāo)記為|W|=w，也就是說，W中包含w個簽到位置。

從定義2可以看出，H-Outlier是基于自身歷史簽到位置的，這也是因為用戶日常活動軌跡記錄往往具有周期性[18]。

設(shè)Fr(ui)表示用戶ui的所有直接好友集合。與QQ、微信等社交網(wǎng)絡(luò)的好友圈的定義不同，這里給出的好友圈定義既包括用戶ui直接好友又包括與ui有一定數(shù)量共同好友的間接好友。

定義3好友圈。給定支持閾值m，用戶ui的好友圈包括ui的所有直接好友和與ui存在至少m個共同直接好友的間接好友，即Fr(ui)∪{uj||Fr(ui)∩Fr(uj)|≥m}，簡記為Net(ui)。

根據(jù)定義4可知，F(xiàn)-Outlier是在 H-Outlier定義的基礎(chǔ)上定義的，因此，F(xiàn)-Outlier集合是H-Outlier集合的子集。

文中涉及的符號名稱及描述由表1給出。

表1 符號名稱及描述

3 基于歷史位置的異常簽到檢測算法

本節(jié)將詳細介紹H-Outlier的在線檢測算法。為了提升檢測效率，首先介紹檢測算法采用的幾種優(yōu)化策略，然后給出詳細的檢測算法。

3.1 優(yōu)化策略

若兩個簽到位置之間距離小于給定距離閾值d，稱它們互為鄰居點。

1)簽到位置的狀態(tài)

傳統(tǒng)檢測方法僅將用戶的簽到位置分為正常和異常兩種狀態(tài)，而通過在滑動窗口下用戶簽到位置的檢測發(fā)現(xiàn)，簽到位置的狀態(tài)可進一步細分，以便減少距離計算。在滑動窗口W中簽到位置p的狀態(tài)可分為：①確定的正常點。如果p在W中鄰居數(shù)量大于等于k，并且在p點之后鄰居數(shù)量也大于等于k，這時不管W如何滑動，位置p在滑出窗口之前，在窗口內(nèi)鄰居數(shù)量一定大于等于k個，因此，此時p的狀態(tài)可以認定為確定的正常簽到點，記為safe-inlier。②不確定的正常點。如果p在W中鄰居數(shù)量大于等于k，但是在p點之后鄰居數(shù)量小于k，這時p雖然是一個正常狀態(tài)的簽到位置，但是當(dāng)W滑動時，在位置p之前的鄰居可能會滑出窗口，p的狀態(tài)可能會變成異常狀態(tài)，此時的p可認為是一個不確定的正常點，記為unsafe-inlier。③確定的異常點。設(shè)簽到位置p之前的鄰居集合為p.Neibefore，之后的鄰居集合為p.Neiafter，如果p在W中鄰居數(shù)量小于k，在p之前有mbefore個位置，如果|p.Neiafter|小于k-mbefore，這時不管W如何滑動，位置p在滑出窗口之前，都不可能包括k個鄰居，因此，此時p的狀態(tài)可以認定為確定的異常簽到點，記為safe-outlier。④異常點。 剩下的異常簽到點都劃歸為這一類，記為outlier。

很明顯，一旦確定safe-inlier和safe-outlier狀態(tài)之后不必再對這些簽到位置進行重新檢測。而隨著窗口滑動，outlier和unsafe-inlier仍需重新檢測狀態(tài)。

2)優(yōu)化的鄰居點搜索機制

根據(jù)上述簽到位置的狀態(tài)劃分方法，我們將簽到位置的鄰居點分為在p簽到之前和在p簽到之后兩個部分，以便快速確定簽到位置的狀態(tài)。若|p.Neiafter|≥k，p為safe-inlier；若|p.Neiafter| lt;k，但|p.Neibefore| +|p.Neiafter| ≥k，p為unsafe-inlier；若|p.Neibefore| +|p.Neiafter|lt;k，并且|p.Neiafter| lt;k-mbefore，p為safe-outlier；其他情況下，p為outlier。

通過觀察發(fā)現(xiàn)，隨著滑動窗口的滑動，對于簽到位置p的所有鄰居點p.Neibefore和p.Neiafter，p.Neibefore中的位置點不斷滑出窗口，而p.Neiafter則一直處在窗口內(nèi)，直到p也滑出窗口才會失效。因此，在搜索p的鄰居時可優(yōu)先搜索在其之后的鄰居，越靠后的鄰居有效期越長；而在其之前的鄰居，越靠近p存活期越長?；谠撚^察，在滑動窗口內(nèi)從最后一個簽到位置向前依次搜索鄰居，滿足優(yōu)先搜索Neiafter，又實現(xiàn)了從最近到最遠搜索Neibefore。

3) 最少鄰居點搜索機制

若查找出簽到位置p的所有鄰居，需掃描一遍窗口。受文獻[14]啟發(fā)，在檢測點p時，并不需要搜索出所有鄰居，當(dāng)滿足k個時，即可判定位置p的狀態(tài)，但是同時為了結(jié)合上述的優(yōu)化策略1)和2)，我們給出最少鄰居點搜索機制。

給定簽到位置p和新簽到位置pnew，若|p.Neiafter|≥k同時|pnew.Neibefore| ≥k，則無需計算p與pnew的距離。此時位置p已經(jīng)確定為safe-inlier，而pnew也已確定為unsafe-inlier。否則，將繼續(xù)計算pnew到所有之前簽到位置的距離，以確定pnew為outlier。采用該機制，既滿足了所有簽到位置狀態(tài)的檢測又實現(xiàn)了最少的距離計算。

3.2 H-Outlier在線檢測算法

算法1給出了H-Outlier的優(yōu)化檢測算法，對于新簽到位置pnew，對窗口W中所有簽到位置進行狀態(tài)重新檢測。首先，按照優(yōu)化的鄰居搜索機制，從窗口內(nèi)最后一個位置，依次向前搜索鄰居，如第1行所示。然后，采用最少鄰居點搜索機制，判定位置pi和pnew是否都已確定狀態(tài)，若已確定，則不用再繼續(xù)搜索鄰居2)～4)行，否則，繼續(xù)計算距離，更新鄰居集合(見5)～7))。如果pi的狀態(tài)不是safe-inlier或safe-outlier，則根據(jù)搜索鄰居情況更新其狀態(tài)，如8)～17)所示。如果pnew搜索到k個在其之前的鄰居，狀態(tài)更新為unsafe-inlier(見18)～19))，檢測完窗口W后，若鄰居數(shù)量依然少于k個，狀態(tài)標(biāo)記為outlier。

算法1 H-Outlier 優(yōu)化檢測算法

輸入當(dāng)前窗口W，k，d，pnew；

輸出所有p∈W的狀態(tài)。

1)fori從Wend到Wstartdo

2)ifpi.sta是safe-inlier 或者pi.sta是safe-outlier

3) ifpnew.sta是unsafe-inlier then

4)繼續(xù)

5) else ifpi與pnew的距離≤dthen

6)將pi添加到pnew.Neibefore

7)將pnew添加到pi.Neiafter

8) else

9)ifpi與pnew的距離≤dthen

10)將pi添加到pnew.Neibefore

11)將pnew添加到pi.Neiafter

12) if |pi.Neiafter|≥kthen

13)pi.status更新為safe-inlier

14)else if |pi.Neibefore|+|pi.Neiafter|≥kthen

15)pi.status更新為unsafe-inlier

16)else if |pi.Neibefore|lt;k-mbeforethen

17)pi.status更新為safe-inlier

18)if |pnew.Neibefore|≥kthen

19)pnew.status更新為unsafe-inlier

20) if |pnew.Neibefore|lt;kthen

21)pnew.status更新為outlier

4 基于好友圈的異常檢測算法

本節(jié)將詳細介紹基于好友圈的異常簽到F-Outlier的檢測算法。F-Outlier定義在H-Outlier之上，對于當(dāng)前窗口W上H-Outlier需進一步驗證是否為F-Outlier。H-Outlier僅在用戶自身近期的歷史簽到位置上查找鄰居點(滑動窗口W內(nèi))，而F-Outlier則在其好友圈用戶的最近簽到位置中搜索鄰居點(△t時間差內(nèi))。

為了進一步降低F-Outlier檢測的時間消耗，本節(jié)同樣給出了3個優(yōu)化策略。

1)最少好友搜索機制

2)歷史鄰近好友優(yōu)先原則

在社會學(xué)領(lǐng)域研究中發(fā)現(xiàn)，人們在某一段時間內(nèi)往往與相同一群人存在較密集的交互[4]。根據(jù)上述社會學(xué)的發(fā)現(xiàn)，我們對每個用戶維護一個鄰近好友的排序列表Lf，用于記錄歷史鄰近簽到狀況，最近一次的鄰近簽到好友排在首位，每次搜索鄰近好友時同時更新列表次序可以較大概率快速搜索鄰近的簽到好友，以排除H-Outlier，而不用隨機遍歷Net(ui)。

3)基于時間觸發(fā)的檢測機制

基于時間觸發(fā)的檢測機制將連續(xù)異常檢測轉(zhuǎn)化成了基于觸發(fā)的檢測，當(dāng)有新簽到數(shù)據(jù)時，才對未過期的簽到位置進行重新檢測，大大減少了額外的周期性重新檢測成本。

算法2 F-Outlier 檢測算法

輸出所有的F-Outlier。

3)forj取值1，2，…，|Net(ui)| do

4)Lf獲取j后給uj

7)將uj插入到Lf首位

13)ui.trigger更新到Trigger

5 實驗評估

實驗平臺配置為4.0 GHz i7-6700k處理器，8 GB內(nèi)存，Windows7操作系統(tǒng)，所有算法由Java實現(xiàn)。

數(shù)據(jù)集。實驗數(shù)據(jù)集采用的是基于位置的移動社交網(wǎng)絡(luò)Gowalla真實數(shù)據(jù)集[18]。數(shù)據(jù)集中包括了195 591個用戶，95萬條好友關(guān)系，收集了2009年2月～2010年10月之間的644萬個簽到位置數(shù)據(jù)。

對比方法。算法1描述的基于歷史位置的異常檢測算法記為H-Opt算法，算法2描述的基于好友圈的異常檢測算法記為F-Opt算法，對比方法記為LUE(lazy with update events)算法[13]。

評估方法。采用所有用戶在單個窗口內(nèi)異常率來評估所提方法的有效性。實驗結(jié)果取所有滑動窗口下的平均值。對于效率評估，通過變化各重要參數(shù)，采用單個窗口平均消耗的CPU時間和內(nèi)存占用來評估算法的性能。每次窗口滑動一個新簽到位置。

5.1 有效性評估

首先，對H-Opt和F-Opt算法的有效性進行了評估與分析。默認參數(shù)設(shè)置：d=300 m，w= 20，k=4，kf=3，Δt=3 h，m=4。H-Opt與F-Opt的異常檢測結(jié)果如圖1所示。圖1(a)描述的是變化參數(shù)k對不同算法的有效性影響?？梢园l(fā)現(xiàn)，隨著k的增加，H-Opt和F-Opt檢測出的異常率都呈線性增加，這是因為增加鄰居點數(shù)量閾值k會使較多的簽到點被認定為H-Outlier。由于F-Outlier基于H-Outlier，隨著H-Outlier數(shù)量的增加，F(xiàn)-Outlier也會有所上升，這與它們定義相符。同時還可以發(fā)現(xiàn)，隨著k的增加，F(xiàn)-Opt算法與H-Opt算法在異常率檢測上的差異不斷增大，即F-Opt的異常誤判率不斷降低。當(dāng)k=7時，降低的異常率已達到1.09%，也就是說，F(xiàn)-Outlier有效排除了30.27%的偽異常。

(a)參數(shù)k對異常率的影響

(b)參數(shù)W對異常率的影響圖1 不同參數(shù)下的算法異常率Fig.1 Outlier rate under different parameters

圖1(b)顯示的是變化參數(shù)W對不同算法的有效性影響。由圖1可以看出，隨著W的增大，異常率不斷下降。這是因為當(dāng)增大W時，鄰居點的歷史簽到時間范圍也隨之增加，從而簽到的鄰居點數(shù)量也會相應(yīng)增加，使H-Outlier和F-Outlier的異常率隨之減少，這也與它們定義相符。同時可以看出，F(xiàn)-Opt的異常率明顯低于H-Opt算法，這也證明了F-Outlier檢測的有效性。

為了更好地考察F-Opt算法的有效性，進一步對F-Opt算法進行了評估。圖2是kf、Δt和m在不同組合時，F(xiàn)-Outlier相比H-Outlier降低的異常率情況。如圖2(a)所示，當(dāng)kf值從2變化到6時，考慮間接好友的F-Outlier進一步降低了H-Outlier的異常率。共同好友的要求越低(m值越小)，異常的降低率越高，即偽異常越少，當(dāng)m=2時，相對僅考慮直接好友，F(xiàn)-Outlier異常的降低率平均提高了8%。圖2(b)展示的是當(dāng)kf=4時，Δt從1～5變化，對算法異常降低率的影響?？梢园l(fā)現(xiàn)，隨著Δt的增加，異常的降低率在不斷增大，這是因為搜索的時間區(qū)間增加，在時間區(qū)間內(nèi)鄰近簽到好友的數(shù)量也在增加。同樣地，考慮好友圈的F-Outlier減少了更多偽異常。在Δt≤4時，F(xiàn)-Outlier減少的異常率變化不大，這也說明大多鄰近好友的簽到是在較短時間差內(nèi)完成。

(a)參數(shù)kf、m對異常降低率的影響

(b)參數(shù)Δt、m對異常降低率的影響圖2 不同參數(shù)對F-Opt異常降低率的影響Fig. 2 F-Opt outlier decreasing rate w.r.t. different parameters

5.2 效率評估

本節(jié)評估了滑動窗口W和鄰居點數(shù)量k對H-Opt和F-Opt算法的消耗時間和內(nèi)存的影響，并與LUE算法進行了對比分析。默認參數(shù)：d=300，kf=3，Δt=3 h，m=4。

在圖3(a)中，固定k=4，W從10變化到30，隨著W的增加，3個算法消耗的時間都有所增加，這是因為窗口增加，都需要增加對異常點鄰居搜索范圍，而LUE需要計算當(dāng)前簽到點與窗口內(nèi)所有簽到點的距離，所以導(dǎo)致了耗時較長。同時，隨著窗口增長，H-Outlier和F-Outlier數(shù)量反而越少，雖然搜索鄰居的范圍增加導(dǎo)致了總消耗時間增加，但是由于采用了優(yōu)化的鄰居搜索機制和最少鄰居搜索機制，僅有異常點增加了鄰居搜索，因此，消耗的CPU時間增長越來越緩慢，而F-Opt算法需要再次檢測的異常點變少也使得消耗的時間越來越少。相比于LUE，F(xiàn)-Opt和H-Opt分別平均提升了2.34、2.45倍效率。在圖3(b)中固定W=20，k從2變化到6。隨著k的增加，3個算法消耗的CPU時間也逐漸增加。雖然F-Opt算法需要重新檢測更多H-Outlier異常，但F-Opt算法并沒有快速增加時間消耗，僅平均增加了0.002 ms。這也體現(xiàn)了我們提出的基于觸發(fā)的優(yōu)化檢測策略的作用。相比于LUE，F(xiàn)-Opt和H-Opt分別平均提升了2.31、2.36倍效率。

(a)參數(shù)W對CPU消耗時間的影響

(b)參數(shù)k對CPU消耗時間的影響圖3 不同參數(shù)下的算法消耗的時間Fig.3 CPU time w.r.t. different parameters

在內(nèi)存方面，如圖4所示，隨著W的增加，3個算法消耗的內(nèi)存也逐漸增加。這是因為隨著滑動窗口的增長，窗口內(nèi)存儲的簽到點也隨之增多。LUE算法需要儲存窗口存儲所有簽到點的鄰居點，消耗的內(nèi)存較多。 H-Opt和F-Opt消耗內(nèi)存較少，這是因為采用了優(yōu)化的鄰居搜索機制和最少鄰居搜索機制。由于增加了F-Outlier好友圈的鄰近簽到存儲，F(xiàn)-Opt略高于H-Opt。

圖4 參數(shù)W和k變化下內(nèi)存的消耗情況Fig.4 Memory w.r.t. parameter W and k

隨著k的增加，3個算法消耗的內(nèi)存也在增加。這是因為所有算法都需要尋找更多的鄰居。H-Opt和F-Opt消耗內(nèi)存增長緩慢，這是因為H-Opt算法采用最少鄰居點搜索機制，隨著k值的增加，在H-Opt算法中需要存儲的自身簽到點也隨之增加。相比于LUE，F(xiàn)-Opt和H-Opt分別平均減少了30%和32%的內(nèi)存消耗。

接下來，進一步評估了參數(shù)m、kf和Δt對F-Opt算法效率的影響。我們測試了變化kf和Δt對多個m值下F-Opt算法效率的影響，如圖5所示。固定W=20，k=4，d=300，在圖5(a)中固定Δt=3 h，在圖5 (b)中固定kf=3，可以看出，隨著kf和Δt增加，F(xiàn)-Opt消耗的CPU時間都逐漸增加。這是因為kf增加，使得鄰近簽到好友搜索的個數(shù)增加； Δt增加使得時間區(qū)間增加。因此消耗的CPU時間也要相應(yīng)增加。同時也發(fā)現(xiàn)，不考慮間接好友時的F-Opt算法消耗最多時間，考慮間接好友時共同好友數(shù)量m值越少，使用的檢測時間越少。這是因為m值越小，Net(u)集合越大，雖然搜索范圍增加了，偽異常也增多了，由于我們采用了歷史鄰近好友優(yōu)先原則和基于觸發(fā)的檢測機制，可快速發(fā)現(xiàn)偽異常，有效提升了算法檢測效率。結(jié)合圖2的實驗結(jié)果可以說明,在移動社交網(wǎng)絡(luò)異常簽到檢測中考慮用戶間接好友的必要性和優(yōu)勢。

(a)參數(shù)kf和m

(b)參數(shù)Δt和m圖5 不同參數(shù)變化的算法CPU時間Fig.5 CPU time w.r.t. different parameters

6 結(jié)束語

本文提出了一種針對移動社交網(wǎng)絡(luò)異常簽到位置的在線檢測方法?；诰嚯x的異常檢測，定義了基于歷史位置和基于好友圈的兩種異常簽到模型。然后，針對兩種異常簽到模型，分別提出了優(yōu)化的檢測算法，從簽到位置的狀態(tài)模型、優(yōu)化的鄰居搜索機制和基于時間觸發(fā)的檢測機制方面有效降低了檢測時間。最后，在真實的移動社交網(wǎng)絡(luò)用戶簽到數(shù)據(jù)集上，驗證了所提模型與算法的有效性和效率。下一步將結(jié)合用戶的操作行為進一步研究有效的移動社交網(wǎng)絡(luò)異常檢測方法。

[1]於志文, 周興社, 郭斌. 移動社交網(wǎng)絡(luò)中的感知計算模型、平臺與實踐[J]. 中國計算機學(xué)會通訊，2012，8(5): 15-21.

[2]WE ARE SOCIAL LTD. DIGITAL IN 2016[EB/OL]. [2017-03-10].http://wearesocial.com/uk/special-reports/digital-in-2016.

[3] ZHENG Yu, XIE X. Location-based social networks: locations[J]. Computing with spatial trajectories, 2011: 277-308.

[4]蕭世埨. 基于位置服務(wù)與人類活動的關(guān)系和影響[J]. 中國計算機學(xué)會通訊， 2010,6(6): 30-35.

[5]張玉清, 呂少卿, 范丹. 在線社交網(wǎng)絡(luò)中異常帳號檢測方法研究[J]. 計算機學(xué)報, 2015, 38(10): 2011-2027.

ZHANG Yuqing，LV Shaoqing，F(xiàn)AN Dan. Anomaly detection in online social networks[J]. Chinese journal of computers, 2015, 38(10): 2011-2027.

[6]CHO E, MYERS S A, LESKOVEC J. Friendship and mobility:user movement in location-based social networks[C]//ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.San Diego, USA, 2011: 1082-1090.

[7]KNORR E M, NG R T. Algorithms for mining distance-based outliers in large datasets[C]//International Conference on Very Large Data Bases. New York, USA, 1998: 392-403.

[8]KNORR E M, NG R T, TUCAKOV V. Distance-based outliers: algorithms and applications[J]. Vldb journal, 2000, 8(3/4): 237-253.

[9]RAMASWAMY S, RASTOGI R, SHIM K. Efficient algorithms for mining outliers from large data sets[C]//ACM SIGMOD International Conference on Management of Data. Dallas, USA, 2000: 427-438.

[10]BREUNIG MARKUS M. LOF: identifying density-based local outliers[J]. ACM sigmod record, 2000, 29(2): 93-104.

[11]YANG D, RUNDENSTEINER E A, Ward M O. Neighbor-based pattern detection for windows over streaming data[C]//International Conference on Extending Database Technology: Advances in Database Technology. Saint Petersburg, Russia, 2009: 529-540.

[12]ANGIULLI F, FASSETTI F. Detecting distance-based outliers in streams of data[C]//Sixteenth ACM Conference on Conference on Information and Knowledge Management. Lisboa, Portugal, 2007:811-820.

[13]KONTAKI M, GOUNARIS A, PAPADOPOULOS A N, et al. Continuous monitoring of distance-based outliers over data streams[C]// IEEE, International Conference on Data Engineering. Hannover, Germany, 2011:135-146.

[14]CAO L, YANG D, WANG Q, et al. Scalable distance-based outlier detection over high-volume data streams[C]//International Conference on Data Engineering. Chicago,USA, 2014: 76-87.

[15]LEE J G, HAN J, LI X. Trajectory outlier detection: a partition-and-detect framework[C]//International Confe- rence on Data Engineering. Cancun, Mexico, 2008: 140-149.

[16]BU Yingyi, CHEN L, FU W C, et al. Efficient anomaly monitoring over moving object trajectory streams[C]//ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Paris, France, 2009: 159-168.

[17]YU Yanwei, CAO Lei, RUNDENSTEINER E A, et al. Detecting moving object outliers in massive-scale trajectory streams[C]//ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York, USA, 2014: 422-431.

[18]LI Zhenhui, WANG J, Han J. Mining event periodicity from incomplete observations[C]// ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Beijing, China, 2012: 444-452.

趙冠哲，男，1992年生，碩士研究生，主要研究方向為數(shù)據(jù)挖掘。

齊建鵬，男，1992年生，碩士研究生，主要研究方向為數(shù)據(jù)挖掘。

于彥偉，男，1986年生，講師，博士，主要研究方向為時空數(shù)據(jù)挖掘、流式數(shù)據(jù)處理、分布式計算。主持國家自然科學(xué)基金青年基金1項，參與國家自然科學(xué)基金面上項目1項，山東省重點研發(fā)計劃項目1項。發(fā)表學(xué)術(shù)論文30余篇。

Onlinecheck-inoutlierdetectionmethodinmobilesocialnetworks

ZHAO Guanzhe, QI Jianpeng, YU Yanwei, LIU Zhaowei, SONG Peng

(School of Computer and Control Engineering, Yantai University, Yantai 264005, China)

With the increasing popularization of smartphone, Pads and other smart mobile devices, the use of mobile social networks has also developed rapidly. In this paper, we propose an online method for detecting check-in outliers based on user mobility behavior in mobile social networks. First, based on a distance-based outlier model, we propose two check-in outlier models with respect to historical location (H-Outlier) and friend circle (F-Outlier), respectively. Second, for the H-Outlier, we propose an optimized detection algorithm called H-Opt, which utilizes the proposed check-in status model and an optimized neighbor searching mechanism to reduce computation time. For the F-Outlier, we propose a trigger-based optimized detection algorithm called F-Opt, which transforms continuous online outlier detection into trigger-based outlier detection. Lastly, we present our experimental results, based on a real-world check-in dataset, which demonstrate the effectiveness of the proposed algorithm. Our experimental results show that F-Opt significantly reduces the error rate of H-Opt outlier detection. In addition, compared with the LUE algorithm, the F-Opt and H-Opt algorithms improved efficiency by 2.34 and 2.45 times, respectively.

location-based social networks; outlier detection; check-in location; distance-based outlier; friend circle; status of check-in; neighbor searching; time-triggered detection

10.11992/tis.201706027

http://kns.cnki.net/kcms/detail/23.1538.TP.20170831.1058.016.html

TP391

A

1673-4785(2017)05-0752-08

中文引用格式：趙冠哲，齊建鵬，于彥偉，等.移動社交網(wǎng)絡(luò)異常簽到在線檢測算法J.智能系統(tǒng)學(xué)報， 2017, 12(5): 752-759.

英文引用格式：ZHAOGuanzhe,QIJianpeng,YUYanwei,etal.Onlinecheck-inoutlierdetectionmethodinmobilesocialnetworksJ.CAAItransactionsonintelligentsystems, 2017, 12(5): 752-759.

2017-06-08. < class="emphasis_bold">網(wǎng)絡(luò)出版日期

日期：2017-08-31.

國家自然科學(xué)基金項目(61403328, 61572419); 山東省重點研發(fā)計劃項目(2015GSF115009); 山東省自然科學(xué)基金項目(ZR2014FQ016); 煙臺大學(xué)研究生科技創(chuàng)新基金項目(YDZD1712).

于彥偉. E-mail：yuyanwei@ytu.edu.cn.