一種面向軌跡信息的時序數據流異常檢測算法

高嘉偉,劉建敏

(1.山西大學 計算機信息與技術學院,太原 030006;2.計算智能與中文信息處理教育部重點實驗室,太原 030006)

0 概述

軌跡信息是一種時序數據流,具有無限性、快速性和無約束性等特點[1]。對軌跡信息進行有效分析,提取數據中的有效信息,及時發現異常軌跡,已成為目前學術界和工業界廣泛關注的領域之一。

傳統聚類算法無法對軌跡這類時序數據流進行聚類,為此,國內外學者關于時序聚類算法開展了研究并取得了一些成果。Aggarwal等人于2003年提出了一種時序數據流聚類算法——CluStream[2]。該算法通過在線和離線2個過程并利用金字塔時間框架對不同時間段內的數據進行聚類。由于該數據流聚類算法不能處理任意形狀的簇,因此文獻[3]提出D-stream聚類算法,其主要思想是將數據空間預先劃分成一系列網格,通過將時序數據映射到相應網格,對網格處理得到聚類結果。

然而,D-stream聚類算法需要用戶預先設置較多參數且精度較低。為此,許多學者基于該算法做了進一步改進。NDD-stream算法[3]通過計算網格單元的密度和簇的數目,動態地調整網格密度閾值,有效地避免了用戶對密度閾值設置的主觀性,但由于該算法僅對稠密網格及其邊界的過渡網格或稀疏網格進行聚類,忽視了未處于稠密網格邊界的過渡網格和稀疏網格。因此,從聚類結果來看,其聚類精度仍較低。文獻[4]考慮到數據的時態特征和空間傾斜分布,定義了時態密度和自適應的密度閾值函數,使得更多的網格參與聚類,提高了算法的聚類精度,但該算法對網格進行了預先劃分,由于劃分參數的不確定性,使得所劃分的網格不能很好地自適應當前數據,影響最終的聚類結果。文獻[5]定義了樣本分布的局部密度,利用類內密度有序性搜索聚類邊界并通過圈定聚類邊界來獲取聚類結果,但該算法通過不斷地改變搜索半徑來處理數據分布疏密度不一的問題,增加了算法時間復雜度。此外,這些算法以及之后一些改進的算法[6-9],僅能獲取當前時段內數據的聚類結果,而不能根據用戶需求獲取任意時段內數據的聚類結果。

綜上所述,目前關于時序數據的密度聚類算法仍存在3類問題:關于解決數據分布疏密不一的方法有待改進;基于網格的聚類方法網格都被預先劃分;未能有效地獲取任意時段內數據的聚類結果。

此外關于軌跡異常檢測方法已有很多,比如文獻[10-11]提出對出租車異常軌跡檢測的算法,其主要特征是按區域對軌跡劃分,對區域內的所有個體的軌跡進行分析,但針對某一個體的軌跡,該算法并未給予有效的異常檢測的方法。

本文從個體的軌跡為著眼點,針對以上3類問題對已有的時序數據流聚類算法進行改進,提出一種基于密度和網格的聚類算法,并將其應用于時序數據流異常檢測。

1 基本概念

1.1 定義

定義1(數據單元) 數據單元即擁有d個屬性值的數據,任意一個數據單元xi=(ai1,ai2,…,aid)[3]。

定義2(數據流) 數據流即按一定時間順序到達的數據單元的集合,數據流X=(x1,x2,…,xi,…,xN)[12]。

1.2 密度網格

由于數據流具有無限性,如果對數據一一處理,時間復雜度較高。為此,可以通過將數據空間劃分成多個子數據空間,先將數據映射到相應的某個數據子空間中,之后再對所有數據子空間進行處理,從而提高數據處理效率。

對于擁有d維屬性的數據流,每個數據xi=(ai1,ai2,…,aid)都可存儲到相應的d維數據空間S=S1×S2×…×Sd。

定義3(網格單元) 在數據空間S中,對任意一個網格gu,選取每一維的劃分為Hgu j(1≤j≤d),則對于任意一個網格單元gu=Hgu 1×Hgu 2×…×Hgu d[3]。

定義4(網格群) 設數據塊內所有數據單元形成了R個網格,則由這R個網格形成了一個網格群G=(g1,g2,…,gR)。

網格的位置由生成網格的數據單元所決定,網格之間可能會存在重疊的現象,因此,本文定義了鄰近網格。

定義5(鄰近網格) 對于網格群內任意2個網格go和gw,若go∩gw≠?,go?gw且gw?go,則go與gw為鄰近網格,表示為go～gw。

定義6(網格單元密度) 設任意一網格單元gu在時刻t,網格內數據的個數為ru,則此時網格的密度為[3]:

Dgu(t)=ru

(1)

即網格單元密度等于網格內數據的個數。

定義7(網格單元中心點) 對于任意一個網格gu,為其定義一個中心點foucusgu=(φgu1,φgu2,…,φguj,…,φgud)。其中,φguj表示gu網格的中心點在j維的屬性值,其數值上等于網格內所有數據單元在該維屬性上取值的均值,即:

(2)

其中,ru表示網格單元gu內數據單元的個數。

定義8(網格單元結構體) 網格單元結構體有3個變量和2個數組,用來存儲該網格單元內數據的概要信息。當數據單元xi映射到某一網格時,更新該網格單元結構體。設某一時刻某一網格單元gu,其結構體表示為:

GSTRgu= {Dgu,lablegu,focusgu,

{min{azj}|1≤j≤ru,1≤z≤d},

{max{azj}|1≤j≤ru,1≤z≤d}}

(3)

其中,Dgu、lablegu、focusgu、{min{azj}|1≤j≤ru,1≤z≤d}、{max{azj}|1≤j≤ru,1≤z≤d}分別表示某一時刻網格單元gu的密度、類別、中心點與由該網格內數據在每一個屬性上取值的最小值和最大值所構成的數組。

1.3 網格單元密度閾值

為解決數據分布密度不一的問題,本文引入了網格密度閾值,用于生成不同類型的網格。網格密度閾值參數的取值,對算法中格簇的形成以及聚類的結果有較大的影響。為此,本文定義了數據塊,通過獲取數據塊內所有網格的特征信息,采用文獻[1]提出的平均密度的思想,動態地確定網格單元密度閾值。

定義9(數據塊) 數據塊用于暫存某時間段內的數據單元,其長度為n(1≤n≤N)。

以數據塊為數據處理單元,將數據塊內所有的數據單元映射到網格中,設在某一時刻t由數據塊內數據單元所形成的所有網格的平均密度為Davg(t),網格最小密度為Dmin(t),網格最大密度為Dmax(t):

(4)

其中,Dgu(t)表示t時刻第u個網格的密度,R表示該數據塊內網格的數量。

稠密網格閾值為[1]:

(5)

稀疏網格閾值為[1]:

(6)

則在時刻t,對于任意一個網格單元gu,其密度為Dgu(t),有如下定義:

稠密網格:

Dgu(t)≥DGTh(t)

過渡網格:

SGTh(t)

稀疏網格:

Dgu(t)≤SGTh(t)

1.4 格簇

由于本文采用網格劃分數據空間的方法,將數據單元先映射到網格中,因此可以通過將有聯系的網格聚在一起形成多個格簇,從而得到聚類結果。

為了確定各網格之間的聯系,本文引用了圖論中圖的概念。對于一個網格群G=(g1,g2,…,gR),將網格群中的所有網格的中心點作為圖中的頂點。若該網格群內的某2個網格鄰近,則認為這2個網格具有一定的聯系并為其對應的頂點賦予一條邊,邊的權重為網格中心點間的距離,從而形成了一個無向有權圖。

定義10(格簇) 通過采用深度優先算法對所形成的無向有權圖進行遍歷并獲取對應的連通分支,將該過程所產生的連通分支定義為格簇,連通分支的個數即為格簇的個數。

定義11(格簇關鍵點) 對于任意一個格簇kf,將格簇中密度最大網格的中心點定義為該格簇的關鍵點keypkf,keypkf=(φkf1,φkf2,…,φkfj,…,φkfd),其中φkfj表示格簇kf的第j個屬性平均值。

定義12(稠密格簇、過渡格簇、稀疏格簇) 稠密格簇為由稠密網格所形成的連通圖的點的集合;過渡格簇為由過渡網格所形成的連通圖的點的集合;稀疏格簇為由稀疏網格所形成的連通圖的點的集合。

定義13(格簇閾值) 格簇閾值即為該格簇可容納其他格簇內數據點的最大鄰域半徑。對于不同類型的格簇,其閾值的定義也不同。設某一格簇kf,其關鍵點為keypkf且有v個網格,則該格簇內所有網格的中心點到該格簇關鍵點距離的最大值emax、平均值eavg和最小值emin為:

(7)

(8)

(9)

在式(7)～式(9)中,φguj表示網格gu中心點的第j個屬性平均值,φkfj表示格簇kf的第j個屬性平均值。

本文所有的距離均采用歐式距離,下文不再贅述。

對于任意一個格簇kf,其閾值Th(kf)為:

(10)

為了判斷某2個格簇內數據點的分布形態變化是否相同,采用文獻[5]判斷局部散布形態是否發生突變的方法。首先通過主成分分析提取每個格簇內數據點的特征,然后利用最大特征值和次大特征值的比值來確定該格簇內數據點的分布形態變化,并引入格簇內數據點分布形態相似閾值β(β≥1)來判斷某2個格簇內數據點的分布形態變化是否相同。對于一個格簇集合K=(k1,k2,…,kL)內的任意2個格簇kp和kq,kp內數據點的分布形態變化為changekp,關鍵點為keypkp且閾值為Th(kp),kq內數據點的分布形態變化為changekq,關鍵點為keypkq且閾值為Th(kq)。格簇kp的關鍵點keypkp與格簇kq關鍵點keypkq間的距離為:

(11)

定義14(相似格簇) 若格簇kp和kq相似,當且僅當滿足式(12)和式(13)2個條件[5]:

(12)

dist(keypkp,keypkq)≤Th(kp)+Th(kq)

(13)

定義15(格簇結構體) 為每一個格簇構建一個結構體,用來存儲格簇的概要信息。設某一格簇kf,其結構體表示為:

LCSTRkf={keypkf,Th(kf),lablekf,changekf}

(14)

其中,keypkf、Th(kf)、lablekf、changekf分別表示格簇的關鍵點、格簇的閾值、格簇的類型和格簇內點集分布的形態變化。

2 本文算法

針對前文所述目前關于時序數據的密度聚類算法仍存在3類問題,本文提出一種基于密度和網格的聚類算法,并應用于時序數據流異常檢測問題。針對現有時序數據流聚類算法存在的問題和異常軌跡檢測算法的局限性,本文主要針對某一個體的軌跡進行分析并提出了一種基于密度和網格的聚類算法。采取按時間段對個體軌跡劃分的方法對個體異常軌跡進行檢測,通過獲取當前數據塊內數據的特征動態地設置網格密度閾值、網格劃分等參數。針對目前時序數據流存在的問題,本文算法做了如下改進:針對數據分布密度不一的問題,通過對稠密網格、過渡網格和稀疏網格形成的稠密圖、過渡圖和稀疏圖分別進行聚類,并利用自適應閾值對所得結果進行再次聚類。針對網格被預先劃分的問題,本文算法引入了動態生成網格的方法。根據當前在線處理過程內數據點的特征,以某些數據點作為網格中心,自適應地重新生成網格。針對獲取任意時段內數據的聚類結果,通過獲取該段時間內的格簇進行再次聚類,并利用自適應閾值對所得結果進行再次聚類,得到最終的聚類結果。

2.1 設計方法

在傳統的異常檢測算法中,訓練集中必須要有異常軌跡參與訓練,否則學習器無法識別異常軌跡。然而,提前獲取用戶異常軌跡信息可能比較困難,因而本文采用聚類思想解決該問題。由于用戶的軌跡信息是一種時序數據流,因此本文算法采用時序數據聚類算法,根據用戶的運動規律將訓練的軌跡信息劃分時間段,并對相應時間段內的軌跡數據進行聚類,其聚類結果作為該用戶的訓練集。測試軌跡首先對相應時間段內的軌跡信息進行聚類,得到聚類結果作為測試集。若測試集中存在某一類與訓練集中的任何一類都不相似,則認為該測試軌跡異常。

2.2 時序數據聚類

該聚類分為在線處理數據和離線處理數據2個處理過程。在線處理數據過程對數據塊內的數據進行處理,動態生成網格并將數據一一映射到相應的網格中,通過使用密度閾值對在線算法所產生的網格分成稠密網格、過渡網格和稀疏網格。根據對稠密網格、過渡網格和稀疏網格不同的處理方法對其進行處理,得到格簇集合并將所有的格簇集合存入數據庫中。離線處理數據過程,根據用戶的需求,取出某時間段內的格簇集合,通過判斷任意2個格簇是否相似進行再次聚類,得到最終的聚類結果。

2.2.1 動態生成網格單元方法

傳統的固定劃分網格方法不能適應當前數據的特征,且網格一旦劃分就不會改變。為了避免這種缺陷,本文引入了動態生成網格的方法,根據當前數據塊的特征自適應地生成網格,且網格的劃分會隨著數據塊的變化而改變。

當數據塊已滿即數據塊內有n個數據單元時,采集該數據塊內數據單元特征,通過計算數據單元每一維屬性的均值δj,動態地確定網格單元每一維空間劃分的長度hj。每一維屬性的均值δj為:

(15)

其中,aij表示第i個數據單元的第j個屬性值。

網格單元gu每一維空間的劃分長度hj為:

(16)

根據數據塊內數據單元的特征,選取R(1≤R≤n)個數據單元作為網格的中心生成R個網格,對于任意一個網格gu(1≤u≤R)在每一維上的劃分Hguj表示為:

Hguj=[ωuj-hj/2,ωuj+hj/2]

(17)

其中,ωuj表示所選取的第u個數據單元的第j個屬性值,則所生成的網格單元可以表示為:

(18)

2.2.2 各類網格的處理方法

網格的處理方法主要有以下2種方法:

1)稠密網格處理方法

針對稠密網格,以網格中的中心點作為頂點,若任意2個網格相鄰,則為其賦予一條邊生成稠密無向有權圖,通過深度優先算法獲取有權圖的連通分支從而得到稠密格簇集合DC(Dense Cluster)。

2)過渡網格和稀疏網格處理方法

針對過渡網格,需先計算稠密格簇中每個稠密網格中所有點距該稠密網格中心點距離的標準差。設任意一個網格gm(1≤m≤R),其標準差為:

(19)

其中,rm為該稠密網格內數據單元的個數,azj為第z個數據單元的第j個屬性值,φgmj為該網格中心點的第j個屬性值,若過渡網格gl的中心點與某一稠密網格的中心點的距離小于標準差SDgm,則將該過渡網格gl歸入該稠密網格所屬的格簇中,并將gl從過渡網格集合移除。繼續計算歸入稠密格簇的過渡網格的標準差SDgl,若剩余的某個過渡網格的中心點與歸入稠密格簇的過渡網格的中心點的距離小于過渡網格gl的標準差SDgl,則將該過渡網格歸入過渡網格gl所屬的稠密格簇中,直到剩余的任意一個過渡網格都不可歸入某個稠密格簇為止。之后,對剩余的過渡網格采用和處理稠密網格相同的方法生成過渡無向有權圖,并得到相應的過渡格簇集合TC(Transition Cluster)。對稀疏格簇采用與過渡網格相同的處理方法得到稀疏格簇集合SC(Sparse Cluster)。

2.2.3 噪聲的處理

在對用戶的軌跡信息進行訓練獲取樣本集時,可能會有異常軌跡參與訓練。這些異常軌跡對于后續分析是很寶貴的資源,而在傳統聚類方法中往往將其標注為噪聲予以舍棄。因而本文將噪聲數據獨立生成異常類進行處理。

在時刻t,若某個格簇內所有網格的數據個數之和依然小于稀疏網格閾值SGTh(t),則認為該格簇內所有的數據點為噪聲,將該格簇從所生成的格簇集合中分離,并將其標記為異常類。

例如,不妨設SGTh(t)=8,某2個格簇都包含3個網格,在這2個格簇中,一個格簇內所有數據點為噪聲,而另一個格簇內所有數據點為非噪聲的情況,噪聲判別情況如圖1所示。

圖1 噪聲判別情況

由圖1(a)可知,圖稀疏格簇內數據點的個數之和為5,小于稀疏網格閾值SGTh(t),所以該格簇內所有的數據點為噪聲;圖1(b)格簇內數據點之和為9,大于稀疏網格閾值SGTh(t),因而該格簇內的數據為非噪聲點。

通過分離最后得到2種格簇集合,即正常軌跡格簇集合NNLC=(k1,k2,…,kNL)和異常軌跡格簇集合AABNLC=(kAB1,kAB2,…,kABNL)。

2.2.4 類相似

類實際上是格簇集合,那么對于任意2個類CP和CQ,設CP有bP個格簇,CQ有bQ個格簇,則CP=(k1,k2,…,kbP),CQ=(k1,k2,…,kbQ)。類CP的中心點為cP=(αcP1,αcP2,…,αcPd),類CQ的中心點為cQ=(αcQ1,αcQ2,…,αcQd)。

(20)

(21)

設類CP和CQ的距離為:

(22)

其中,式(20)中的αCPj表示類CP中心點cP的第j個屬性值,式(21)中的αCQj表示類CQ中心點cQ的第j個屬性值。

類間距離歸一化處理:

設所求的類間距離最大值為DCmax,最小距離為DCmin。

(23)

設類間相似閾值為μ(0<μ<1),若Dcen(CP,CQ)≤μ,則認為這2個類相似;否則不相似。

2.2.5 在線處理數據過程描述

在線處理數據過程如下:

輸入數據塊Xb=(xρ,xρ+1,…,xρ+n-1)

輸出格簇集合K=(k1,k2,…,kL)

步驟1獲取數據塊Xb中的數據單元。

步驟2計算數據單元每一維度的平均值δj和維度劃分的長度hj,并確定每個網格空間。

步驟3讀入新數據單元xυ(i≤υ≤i+n-1),如果數據xυ(i≤υ≤i+n-1)屬于當前某一網格則該網格密度加1;否則以數據單元xυ(i≤υ≤i+n-1)為中心生成一個新的網格。

步驟4計算時刻t稠密網格閾值DGTh(t)和稀疏網格的閾值SGTh(t)。

步驟5判斷網格是稠密網格、過渡網格或稀疏網格。

步驟6對稠密網格、過渡網格和稀疏網格分別進行處理,并得到稠密格簇集合DC,過渡格簇集合TC和稀疏格簇集合SC。

步驟7輸出格簇集合DC∪TC∪SC。

2.2.6 離線處理數據過程描述

在該過程處理前,先根據用戶所確定的時間段T,從數據庫中獲取該時段內的格簇集合。

輸入時間段T內的格簇集合K=(k1,k2,…,kL),形態相似閾值β

輸出聚類結果C=NC∪ABNC

步驟1確定每一個格簇的關鍵點。

步驟2判斷格簇內的數據是否為噪聲點,并得到相應的正常軌跡格簇NLC和異常軌跡格簇ABNLC。

步驟3根據格簇相似的方法,對NLC和ABNLC分別進行處理,將相似的格簇歸為一類并得到正常軌跡類NC和異常軌跡類ABNC。

步驟4輸出最終的聚類結果C=NC∪ABNC。

本文聚類算法的流程如圖2所示。

圖2 本文聚類算法流程

2.3 異常檢測過程

針對某一用戶可能在某段時間內常去一些固定地點,因此其軌跡具有一定的規律。同時,也可能在某段時間內去一些之前未去過的地點。若能及時發現用戶在該時間段內出行軌跡的異常,對于用戶人身安全防護,尤其是老人、兒童等弱勢群體,則具有重要的理論意義和應用價值。

2.3.1 軌跡異常

若測試軌跡中的某一類與訓練集中正常軌跡類的任何一類都不相似,則認為該測試軌跡異常。當測試軌跡中的某一類不僅與訓練集中正常軌跡中的某類相似,而且也與異常軌跡中的某類相似時,若與異常軌跡類的距離小于正常軌跡類的距離,則認為該測試軌跡異常。

2.3.2 過程描述

異常檢測過程如下:

輸入某段時間內的數據流X=(x1,x2,…,xi,…,xN),數據塊的長度n,類間相似閾值μ

輸出軌跡是否異常

步驟1將數據流按數據塊長度劃分為多個數據塊。

步驟2利用2.2節的聚類方法對每個數據塊進行聚類。

步驟3對步驟2所得的類,利用2.3.1節的方法,判斷軌跡是否異常。

步驟4輸出最終判斷結果。

3 實驗結果與分析

本文實驗以微軟亞洲研究院Geolife項目收集的用戶GPS軌跡信息[13]為研究對象。該項目收集了178位用戶從2007年4月—2011年10月的軌跡信息。該數據集的GPS軌跡表示時間戳點的序列,其中每一個包含緯度、經度和海拔高度的信息。

本文實驗采用2.5 GHz處理器,4 GB內存。算法利用Eclipse4.4.2和Matlab2014a編程實現。

由于有些用戶的運動規律不明顯,因此本文實驗從Geolife項目中篩選了運動規律較為明顯且軌跡信息較為完整的50名用戶在100 d內的軌跡信息,并根據每個用戶的運動規律對其軌跡信息按時間段進行劃分。

3.1 功能比較

若類間相似閾值設置不合理,則可能會導致最終異常檢測的判斷結果。在實驗過程中發現類間相似閾值與樣本集中的經度之差(最大經度值與最小經度值之差)和緯度之差(最大緯度值與最小緯度值之差)2個變量有關。因此,針對所選出50名用戶,隨機選取40名用戶的軌跡信息進行了分析,并得到類間相似閾值。

由于類間相似閾值無量綱,而經度之差和緯度之差是有量綱的數據,因此需先對經度之差和緯度之差進行歸一化處理。以經度之差為例,其歸一化過程如下:

(24)

其中,ΔLon表示某一用戶的實際經度之差,minΔLon為所有用戶經度之差的最小值,maxΔLon為所有用戶經度之差的最大值,Δlon為歸一化后的經度之差。

利用Matlab擬合工具cftool對40名用戶的類間閾值信息擬合得到類間相似閾值μ(Δlon,Δlat)與歸一化后經度之差Δlon,緯度之差Δlat的關系如下:

μ(Δlon,Δlat)= -0.048 61+17.49Δlon-20.84Δlat-

162.7Δ2lon-182.4ΔlonΔlat+

516.8Δ2lat-626.5Δ3lon+

769 9Δ2lonΔlat-1.25×

104ΔlonΔ2lat+410 9Δ3lat

類間相似閾值擬合曲線如圖3所示。

圖3 類間相似閾值擬合曲線

一條擬合曲線往往需要通過一些擬合參數來判斷其擬合效果,該曲線的擬合參數值“誤差平方和SSE、相關系數R-square、調整后的相關系數Adjusted R-square和標準差RMSE”如表1所示。

表1 擬合參數的取值

若SSE越接近0,R-square越接近1,則曲線擬合效果越好。從表1可見,該曲線的擬合參數R-square為0.951 1,較接近于1,表示該曲線能解釋因變量95.11%的變化,SSE誤差平方和為0.000 337,較接近于0。因此,可以判斷該曲線擬合效果較好,可用該曲線的擬合結果來確定類間相似閾值的大小。

本文算法檢測異常軌跡情況以用戶4在00∶00—05∶00時間段內的軌跡信息舉例說明。利用用戶4從2008-08-05—2008-10-25在00∶00—05∶00時間段內的數據生成樣本。判斷用戶4在2008-10-27、2008-10-28和2008-11-05的00∶00—05∶00時間段內軌跡是否異常。最后得到用戶4在2008-10-27和2008-10-28的00∶00—05∶00時間段內軌跡正常,在2008-11-05的00∶00—05∶00時間段內軌跡異常。

用戶4在2008-10-27、2008-10-28該時段內的正常軌跡,以及在2008-11-05該時段內的異常軌跡如圖4～圖7所示。

圖4用戶4從2008-09-25—2008-10-25在00:00—05:00時間段內的軌跡樣本

圖5 用戶4在2008-10-27的00∶00—05∶00時間段內的正常軌跡

圖6 用戶4在2008-10-28的00∶00—05∶00時間段內的正常軌跡

圖7 用戶4在2008-11-05的00∶00—05∶00時間段內的異常軌跡

從圖7可知,圖7中有一部分軌跡在圖4中沒有出現,可以認為用戶可能去了之前沒有去過的地方,該軌跡異常。圖5的軌跡和圖4的軌跡相似,可以認為該軌跡正常。圖6中的軌跡是圖4軌跡中的一部分,因此該軌跡也正常。

對剩余的10名用戶進行測試,該10名用戶在原數據對應的編號見表2。利用10名用戶前80 d內的數據進行訓練得到樣本集,并用剩余的20 d數據進行測試,通過類間閾值擬合曲線求得每個用戶軌跡信息的類間閾值。10名用戶后20 d內的軌跡統計情況見表2。

表2 10名用戶軌跡統計情況

各算法檢測正確率見表3。其中文獻[4-5]算法的參數值均取該文獻所建議的最優參數值,而本文算法參數的取值,通過實驗獲得最優參數。在表3中,TNR為真負率,ACC為準確率,其計算方法與文獻[14-15]TNR和ACC的計算方法相同。從表3中可得,文獻[4]檢測異常軌跡的平均正確率僅為38.4%,文獻[5]檢測異常軌跡的平均正確率為53.5%,本文算法檢測異常軌跡的平均正確率為72.2%,因此本文算法更適合于處理軌跡類數據信息并用來檢測異常軌跡。

表3 各算法檢測正確率比較 %

3.2 時間效率比較

本文實驗針對10名測試用戶的軌跡信息對文獻[4-5]和本文算法的時間效率進行了測試,其結果如表4所示。

表4 算法運行時間比較 s

由表4可得,文獻[4]的時間效率最高,文獻[5]的時間效率最低,而本文算法的時間效率介于兩者之間且更接近于文獻[4]算法。由實驗3.1節可知,文獻[4]判斷軌跡異常的平均TNR僅有38.4%,因此雖然該方法的時間效率高,但仍不適合用于軌跡信息的處理。文獻[5]判斷軌跡異常的平均TNR為53.5%,雖然比文獻[4]高,但其時間復雜度遠大于文獻[4]和本文算法,因此,該算法也不適合于對軌跡信息的處理。本文算法雖然比文獻[4]消耗的時間多,但判斷軌跡異常的平均TNR為72.2%,相當于文獻[4]的2倍。

綜上所述,本文算法更適用于處理個體軌跡信息等時序數據流的異常檢測問題。

4 結束語

本文提出一種面向軌跡信息的時序數據流異常檢測算法,算法主要分為訓練和測試2個階段,利用訓練階段得到的樣本集并通過類間相似閾值求解方法確定閾值的大小,對測試階段的測試集進行測試。對于2個階段的聚類過程,引入了動態劃分網格的方法以自適應當前數據的特征,并針對不同類型網格采用不同的方法進行處理,解決密度分布不均等問題。此外,根據用戶的需求可得到不同時間段內數據的聚類結果。實驗結果表明,本文算法能夠較好地處理軌跡信息等時序數據流。由于本文算法僅能檢測某時間段內用戶的軌跡是否異常,而無法實時判斷某一時刻用戶所處的位置是否異常,因此如何判斷用戶某一時刻的位置是否異常和降低算法的時間復雜度,是下一步主要研究方向。

[1] 胡 睿,林昭文,柯宏力,等.一種基于密度和滑動窗口的數據流聚類算法[J].計算機科學,2011,38(5):145-148.

[2] AGGARWAL C C,YU P S,HAN J,et al.A framework for clustering evolving data streams[C]//Proceedings of International Conference on VLDB’03.Washington D.C.,USA:IEEE Press,2003:81-92.

[3] CHEN Y,TU L.Density-based clustering for real-time stream data[C]//Proceedings of ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.San Jose,USA:ACM Press,2007:133-142.

[4] 楊 寧,唐常杰,王 悅,等.一種基于時態密度的傾斜分布數據流聚類算法[J].軟件學報,2010,21(5):1031-1041.

[5] 徐正國,鄭 輝,賀 亮,等.基于局部密度下降搜索的自適應聚類方法[J].計算機研究與發展,2016,53(8):1719-1728.

[6] 米 源,楊 燕,李天瑞.基于密度網格的數據流聚類算法[J].計算機科學,2011,38(12):178-181.

[7] 于彥偉,王 歡,王 沁,等.面向海量數據流的基于密度的簇結構挖掘算法[J].軟件學報,2015,26(5):1113-1128.

[8] 于彥偉,王 沁,鄺 俊,等.一種基于密度的空間數據流在線聚類算法[J].自動化學報,2012,38(6):1051-1059.

[9] 馬 帥,王騰蛟,唐世渭,等.一種基于參考點和密度的快速聚類算法[J].軟件學報,2003,14(6):1089-1095.

[10] 朱 燕,李宏偉,樊 超,等.基于聚類的出租車異常軌跡檢測[J].計算機工程,2017,43(2):16-20.

[11] ZENG Y,CAPRA L,WOLFSON O,et al.Urban computing:concepts,methodologies,and applications[J].ACM Transactions on Intelligent Systems & Technology,2014,5(3):38.

[12] 金澈清,錢衛寧,周傲英.流數據分析與管理綜述[J].軟件學報,2004,15(8):1172-1181.

[13] ZHENG Y,XIE X,MA W Y.GeoLife:a collaborative social networking service among user,location and trajectory[J].Bulletin of the Technical Committee on Data Engineering,2010,33(2):32-39.

[14] 高嘉偉,梁吉業.非平衡數據集分類問題研究進展[J].計算機科學,2008,35(4):10-13.

[15] 高嘉偉,梁吉業,劉楊磊,等.一種基于Tri-training的半監督多標記學習文檔分類算法[J].中文信息學報,2015,29(1):104-110.