一種面向軌跡信息的時(shí)序數(shù)據(jù)流異常檢測(cè)算法

高嘉偉,劉建敏

(1.山西大學(xué) 計(jì)算機(jī)信息與技術(shù)學(xué)院,太原 030006;2.計(jì)算智能與中文信息處理教育部重點(diǎn)實(shí)驗(yàn)室,太原 030006)

0 概述

軌跡信息是一種時(shí)序數(shù)據(jù)流,具有無限性、快速性和無約束性等特點(diǎn)[1]。對(duì)軌跡信息進(jìn)行有效分析,提取數(shù)據(jù)中的有效信息,及時(shí)發(fā)現(xiàn)異常軌跡,已成為目前學(xué)術(shù)界和工業(yè)界廣泛關(guān)注的領(lǐng)域之一。

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

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

綜上所述,目前關(guān)于時(shí)序數(shù)據(jù)的密度聚類算法仍存在3類問題:關(guān)于解決數(shù)據(jù)分布疏密不一的方法有待改進(jìn);基于網(wǎng)格的聚類方法網(wǎng)格都被預(yù)先劃分;未能有效地獲取任意時(shí)段內(nèi)數(shù)據(jù)的聚類結(jié)果。

此外關(guān)于軌跡異常檢測(cè)方法已有很多,比如文獻(xiàn)[10-11]提出對(duì)出租車異常軌跡檢測(cè)的算法,其主要特征是按區(qū)域?qū)壽E劃分,對(duì)區(qū)域內(nèi)的所有個(gè)體的軌跡進(jìn)行分析,但針對(duì)某一個(gè)體的軌跡,該算法并未給予有效的異常檢測(cè)的方法。

本文從個(gè)體的軌跡為著眼點(diǎn),針對(duì)以上3類問題對(duì)已有的時(shí)序數(shù)據(jù)流聚類算法進(jìn)行改進(jìn),提出一種基于密度和網(wǎng)格的聚類算法,并將其應(yīng)用于時(shí)序數(shù)據(jù)流異常檢測(cè)。

1 基本概念

1.1 定義

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

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

1.2 密度網(wǎng)格

由于數(shù)據(jù)流具有無限性,如果對(duì)數(shù)據(jù)一一處理,時(shí)間復(fù)雜度較高。為此,可以通過將數(shù)據(jù)空間劃分成多個(gè)子數(shù)據(jù)空間,先將數(shù)據(jù)映射到相應(yīng)的某個(gè)數(shù)據(jù)子空間中,之后再對(duì)所有數(shù)據(jù)子空間進(jìn)行處理,從而提高數(shù)據(jù)處理效率。

對(duì)于擁有d維屬性的數(shù)據(jù)流,每個(gè)數(shù)據(jù)xi=(ai1,ai2,…,aid)都可存儲(chǔ)到相應(yīng)的d維數(shù)據(jù)空間S=S1×S2×…×Sd。

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

定義4(網(wǎng)格群) 設(shè)數(shù)據(jù)塊內(nèi)所有數(shù)據(jù)單元形成了R個(gè)網(wǎng)格,則由這R個(gè)網(wǎng)格形成了一個(gè)網(wǎng)格群G=(g1,g2,…,gR)。

網(wǎng)格的位置由生成網(wǎng)格的數(shù)據(jù)單元所決定,網(wǎng)格之間可能會(huì)存在重疊的現(xiàn)象,因此,本文定義了鄰近網(wǎng)格。

定義5(鄰近網(wǎng)格) 對(duì)于網(wǎng)格群內(nèi)任意2個(gè)網(wǎng)格go和gw,若go∩gw≠?,go?gw且gw?go,則go與gw為鄰近網(wǎng)格,表示為go～gw。

定義6(網(wǎng)格單元密度) 設(shè)任意一網(wǎng)格單元gu在時(shí)刻t,網(wǎng)格內(nèi)數(shù)據(jù)的個(gè)數(shù)為ru,則此時(shí)網(wǎng)格的密度為[3]:

Dgu(t)=ru

(1)

即網(wǎng)格單元密度等于網(wǎng)格內(nèi)數(shù)據(jù)的個(gè)數(shù)。

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

(2)

其中,ru表示網(wǎng)格單元gu內(nèi)數(shù)據(jù)單元的個(gè)數(shù)。

定義8(網(wǎng)格單元結(jié)構(gòu)體) 網(wǎng)格單元結(jié)構(gòu)體有3個(gè)變量和2個(gè)數(shù)組,用來存儲(chǔ)該網(wǎng)格單元內(nèi)數(shù)據(jù)的概要信息。當(dāng)數(shù)據(jù)單元xi映射到某一網(wǎng)格時(shí),更新該網(wǎng)格單元結(jié)構(gòu)體。設(shè)某一時(shí)刻某一網(wǎng)格單元gu,其結(jié)構(gòu)體表示為:

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}分別表示某一時(shí)刻網(wǎng)格單元gu的密度、類別、中心點(diǎn)與由該網(wǎng)格內(nèi)數(shù)據(jù)在每一個(gè)屬性上取值的最小值和最大值所構(gòu)成的數(shù)組。

1.3 網(wǎng)格單元密度閾值

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

定義9(數(shù)據(jù)塊) 數(shù)據(jù)塊用于暫存某時(shí)間段內(nèi)的數(shù)據(jù)單元,其長(zhǎng)度為n(1≤n≤N)。

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

(4)

其中,Dgu(t)表示t時(shí)刻第u個(gè)網(wǎng)格的密度,R表示該數(shù)據(jù)塊內(nèi)網(wǎng)格的數(shù)量。

稠密網(wǎng)格閾值為[1]:

(5)

稀疏網(wǎng)格閾值為[1]:

(6)

則在時(shí)刻t,對(duì)于任意一個(gè)網(wǎng)格單元gu,其密度為Dgu(t),有如下定義:

稠密網(wǎng)格:

Dgu(t)≥DGTh(t)

過渡網(wǎng)格:

SGTh(t)

稀疏網(wǎng)格:

Dgu(t)≤SGTh(t)

1.4 格簇

由于本文采用網(wǎng)格劃分?jǐn)?shù)據(jù)空間的方法,將數(shù)據(jù)單元先映射到網(wǎng)格中,因此可以通過將有聯(lián)系的網(wǎng)格聚在一起形成多個(gè)格簇,從而得到聚類結(jié)果。

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

定義10(格簇) 通過采用深度優(yōu)先算法對(duì)所形成的無向有權(quán)圖進(jìn)行遍歷并獲取對(duì)應(yīng)的連通分支,將該過程所產(chǎn)生的連通分支定義為格簇,連通分支的個(gè)數(shù)即為格簇的個(gè)數(shù)。

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

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

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

(7)

(8)

(9)

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

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

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

(10)

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

(11)

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

(12)

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

(13)

定義15(格簇結(jié)構(gòu)體) 為每一個(gè)格簇構(gòu)建一個(gè)結(jié)構(gòu)體,用來存儲(chǔ)格簇的概要信息。設(shè)某一格簇kf,其結(jié)構(gòu)體表示為:

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

(14)

其中,keypkf、Th(kf)、lablekf、changekf分別表示格簇的關(guān)鍵點(diǎn)、格簇的閾值、格簇的類型和格簇內(nèi)點(diǎn)集分布的形態(tài)變化。

2 本文算法

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

2.1 設(shè)計(jì)方法

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

2.2 時(shí)序數(shù)據(jù)聚類

該聚類分為在線處理數(shù)據(jù)和離線處理數(shù)據(jù)2個(gè)處理過程。在線處理數(shù)據(jù)過程對(duì)數(shù)據(jù)塊內(nèi)的數(shù)據(jù)進(jìn)行處理,動(dòng)態(tài)生成網(wǎng)格并將數(shù)據(jù)一一映射到相應(yīng)的網(wǎng)格中,通過使用密度閾值對(duì)在線算法所產(chǎn)生的網(wǎng)格分成稠密網(wǎng)格、過渡網(wǎng)格和稀疏網(wǎng)格。根據(jù)對(duì)稠密網(wǎng)格、過渡網(wǎng)格和稀疏網(wǎng)格不同的處理方法對(duì)其進(jìn)行處理,得到格簇集合并將所有的格簇集合存入數(shù)據(jù)庫中。離線處理數(shù)據(jù)過程,根據(jù)用戶的需求,取出某時(shí)間段內(nèi)的格簇集合,通過判斷任意2個(gè)格簇是否相似進(jìn)行再次聚類,得到最終的聚類結(jié)果。

2.2.1 動(dòng)態(tài)生成網(wǎng)格單元方法

傳統(tǒng)的固定劃分網(wǎng)格方法不能適應(yīng)當(dāng)前數(shù)據(jù)的特征,且網(wǎng)格一旦劃分就不會(huì)改變。為了避免這種缺陷,本文引入了動(dòng)態(tài)生成網(wǎng)格的方法,根據(jù)當(dāng)前數(shù)據(jù)塊的特征自適應(yīng)地生成網(wǎng)格,且網(wǎng)格的劃分會(huì)隨著數(shù)據(jù)塊的變化而改變。

當(dāng)數(shù)據(jù)塊已滿即數(shù)據(jù)塊內(nèi)有n個(gè)數(shù)據(jù)單元時(shí),采集該數(shù)據(jù)塊內(nèi)數(shù)據(jù)單元特征,通過計(jì)算數(shù)據(jù)單元每一維屬性的均值δj,動(dòng)態(tài)地確定網(wǎng)格單元每一維空間劃分的長(zhǎng)度hj。每一維屬性的均值δj為:

(15)

其中,aij表示第i個(gè)數(shù)據(jù)單元的第j個(gè)屬性值。

網(wǎng)格單元gu每一維空間的劃分長(zhǎng)度hj為:

(16)

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

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

(17)

其中,ωuj表示所選取的第u個(gè)數(shù)據(jù)單元的第j個(gè)屬性值,則所生成的網(wǎng)格單元可以表示為:

(18)

2.2.2 各類網(wǎng)格的處理方法

網(wǎng)格的處理方法主要有以下2種方法:

1)稠密網(wǎng)格處理方法

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

2)過渡網(wǎng)格和稀疏網(wǎng)格處理方法

針對(duì)過渡網(wǎng)格,需先計(jì)算稠密格簇中每個(gè)稠密網(wǎng)格中所有點(diǎn)距該稠密網(wǎng)格中心點(diǎn)距離的標(biāo)準(zhǔn)差。設(shè)任意一個(gè)網(wǎng)格gm(1≤m≤R),其標(biāo)準(zhǔn)差為:

(19)

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

2.2.3 噪聲的處理

在對(duì)用戶的軌跡信息進(jìn)行訓(xùn)練獲取樣本集時(shí),可能會(huì)有異常軌跡參與訓(xùn)練。這些異常軌跡對(duì)于后續(xù)分析是很寶貴的資源,而在傳統(tǒng)聚類方法中往往將其標(biāo)注為噪聲予以舍棄。因而本文將噪聲數(shù)據(jù)獨(dú)立生成異常類進(jìn)行處理。

在時(shí)刻t,若某個(gè)格簇內(nèi)所有網(wǎng)格的數(shù)據(jù)個(gè)數(shù)之和依然小于稀疏網(wǎng)格閾值SGTh(t),則認(rèn)為該格簇內(nèi)所有的數(shù)據(jù)點(diǎn)為噪聲,將該格簇從所生成的格簇集合中分離,并將其標(biāo)記為異常類。

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

圖1 噪聲判別情況

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

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

2.2.4 類相似

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

(20)

(21)

設(shè)類CP和CQ的距離為:

(22)

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

類間距離歸一化處理:

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

(23)

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

2.2.5 在線處理數(shù)據(jù)過程描述

在線處理數(shù)據(jù)過程如下:

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

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

步驟1獲取數(shù)據(jù)塊Xb中的數(shù)據(jù)單元。

步驟2計(jì)算數(shù)據(jù)單元每一維度的平均值δj和維度劃分的長(zhǎng)度hj,并確定每個(gè)網(wǎng)格空間。

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

步驟4計(jì)算時(shí)刻t稠密網(wǎng)格閾值DGTh(t)和稀疏網(wǎng)格的閾值SGTh(t)。

步驟5判斷網(wǎng)格是稠密網(wǎng)格、過渡網(wǎng)格或稀疏網(wǎng)格。

步驟6對(duì)稠密網(wǎng)格、過渡網(wǎng)格和稀疏網(wǎng)格分別進(jìn)行處理,并得到稠密格簇集合DC,過渡格簇集合TC和稀疏格簇集合SC。

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

2.2.6 離線處理數(shù)據(jù)過程描述

在該過程處理前,先根據(jù)用戶所確定的時(shí)間段T,從數(shù)據(jù)庫中獲取該時(shí)段內(nèi)的格簇集合。

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

輸出聚類結(jié)果C=NC∪ABNC

步驟1確定每一個(gè)格簇的關(guān)鍵點(diǎn)。

步驟2判斷格簇內(nèi)的數(shù)據(jù)是否為噪聲點(diǎn),并得到相應(yīng)的正常軌跡格簇NLC和異常軌跡格簇ABNLC。

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

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

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

圖2 本文聚類算法流程

2.3 異常檢測(cè)過程

針對(duì)某一用戶可能在某段時(shí)間內(nèi)常去一些固定地點(diǎn),因此其軌跡具有一定的規(guī)律。同時(shí),也可能在某段時(shí)間內(nèi)去一些之前未去過的地點(diǎn)。若能及時(shí)發(fā)現(xiàn)用戶在該時(shí)間段內(nèi)出行軌跡的異常,對(duì)于用戶人身安全防護(hù),尤其是老人、兒童等弱勢(shì)群體,則具有重要的理論意義和應(yīng)用價(jià)值。

2.3.1 軌跡異常

若測(cè)試軌跡中的某一類與訓(xùn)練集中正常軌跡類的任何一類都不相似,則認(rèn)為該測(cè)試軌跡異常。當(dāng)測(cè)試軌跡中的某一類不僅與訓(xùn)練集中正常軌跡中的某類相似,而且也與異常軌跡中的某類相似時(shí),若與異常軌跡類的距離小于正常軌跡類的距離,則認(rèn)為該測(cè)試軌跡異常。

2.3.2 過程描述

異常檢測(cè)過程如下:

輸入某段時(shí)間內(nèi)的數(shù)據(jù)流X=(x1,x2,…,xi,…,xN),數(shù)據(jù)塊的長(zhǎng)度n,類間相似閾值μ

輸出軌跡是否異常

步驟1將數(shù)據(jù)流按數(shù)據(jù)塊長(zhǎng)度劃分為多個(gè)數(shù)據(jù)塊。

步驟2利用2.2節(jié)的聚類方法對(duì)每個(gè)數(shù)據(jù)塊進(jìn)行聚類。

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

步驟4輸出最終判斷結(jié)果。

3 實(shí)驗(yàn)結(jié)果與分析

本文實(shí)驗(yàn)以微軟亞洲研究院Geolife項(xiàng)目收集的用戶GPS軌跡信息[13]為研究對(duì)象。該項(xiàng)目收集了178位用戶從2007年4月—2011年10月的軌跡信息。該數(shù)據(jù)集的GPS軌跡表示時(shí)間戳點(diǎn)的序列,其中每一個(gè)包含緯度、經(jīng)度和海拔高度的信息。

本文實(shí)驗(yàn)采用2.5 GHz處理器,4 GB內(nèi)存。算法利用Eclipse4.4.2和Matlab2014a編程實(shí)現(xiàn)。

由于有些用戶的運(yùn)動(dòng)規(guī)律不明顯,因此本文實(shí)驗(yàn)從Geolife項(xiàng)目中篩選了運(yùn)動(dòng)規(guī)律較為明顯且軌跡信息較為完整的50名用戶在100 d內(nèi)的軌跡信息,并根據(jù)每個(gè)用戶的運(yùn)動(dòng)規(guī)律對(duì)其軌跡信息按時(shí)間段進(jìn)行劃分。

3.1 功能比較

若類間相似閾值設(shè)置不合理,則可能會(huì)導(dǎo)致最終異常檢測(cè)的判斷結(jié)果。在實(shí)驗(yàn)過程中發(fā)現(xiàn)類間相似閾值與樣本集中的經(jīng)度之差(最大經(jīng)度值與最小經(jīng)度值之差)和緯度之差(最大緯度值與最小緯度值之差)2個(gè)變量有關(guān)。因此,針對(duì)所選出50名用戶,隨機(jī)選取40名用戶的軌跡信息進(jìn)行了分析,并得到類間相似閾值。

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

(24)

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

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

μ(Δ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 類間相似閾值擬合曲線

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

表1 擬合參數(shù)的取值

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

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

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

圖4用戶4從2008-09-25—2008-10-25在00:00—05:00時(shí)間段內(nèi)的軌跡樣本

圖5 用戶4在2008-10-27的00∶00—05∶00時(shí)間段內(nèi)的正常軌跡

圖6 用戶4在2008-10-28的00∶00—05∶00時(shí)間段內(nèi)的正常軌跡

圖7 用戶4在2008-11-05的00∶00—05∶00時(shí)間段內(nèi)的異常軌跡

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

對(duì)剩余的10名用戶進(jìn)行測(cè)試,該10名用戶在原數(shù)據(jù)對(duì)應(yīng)的編號(hào)見表2。利用10名用戶前80 d內(nèi)的數(shù)據(jù)進(jìn)行訓(xùn)練得到樣本集,并用剩余的20 d數(shù)據(jù)進(jìn)行測(cè)試,通過類間閾值擬合曲線求得每個(gè)用戶軌跡信息的類間閾值。10名用戶后20 d內(nèi)的軌跡統(tǒng)計(jì)情況見表2。

表2 10名用戶軌跡統(tǒng)計(jì)情況

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

表3 各算法檢測(cè)正確率比較 %

3.2 時(shí)間效率比較

本文實(shí)驗(yàn)針對(duì)10名測(cè)試用戶的軌跡信息對(duì)文獻(xiàn)[4-5]和本文算法的時(shí)間效率進(jìn)行了測(cè)試,其結(jié)果如表4所示。

表4 算法運(yùn)行時(shí)間比較 s

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

綜上所述,本文算法更適用于處理個(gè)體軌跡信息等時(shí)序數(shù)據(jù)流的異常檢測(cè)問題。

4 結(jié)束語

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

[1] 胡 睿,林昭文,柯宏力,等.一種基于密度和滑動(dòng)窗口的數(shù)據(jù)流聚類算法[J].計(jì)算機(jī)科學(xué),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] 楊 寧,唐常杰,王 悅,等.一種基于時(shí)態(tài)密度的傾斜分布數(shù)據(jù)流聚類算法[J].軟件學(xué)報(bào),2010,21(5):1031-1041.

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

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

[7] 于彥偉,王 歡,王 沁,等.面向海量數(shù)據(jù)流的基于密度的簇結(jié)構(gòu)挖掘算法[J].軟件學(xué)報(bào),2015,26(5):1113-1128.

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

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

[10] 朱 燕,李宏偉,樊 超,等.基于聚類的出租車異常軌跡檢測(cè)[J].計(jì)算機(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] 金澈清,錢衛(wèi)寧,周傲英.流數(shù)據(jù)分析與管理綜述[J].軟件學(xué)報(bào),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] 高嘉偉,梁吉業(yè).非平衡數(shù)據(jù)集分類問題研究進(jìn)展[J].計(jì)算機(jī)科學(xué),2008,35(4):10-13.

[15] 高嘉偉,梁吉業(yè),劉楊磊,等.一種基于Tri-training的半監(jiān)督多標(biāo)記學(xué)習(xí)文檔分類算法[J].中文信息學(xué)報(bào),2015,29(1):104-110.