一种基于数据降维的移动目标轨迹分析方法*

吴 聪 崔 隽 施卫峰

(中国电子科技集团公司第二十八研究所 南京 210007)



一种基于数据降维的移动目标轨迹分析方法*

吴 聪 崔 隽 施卫峰

(中国电子科技集团公司第二十八研究所 南京 210007)

大数据是信息技术领域又一次颠覆性的技术革命,已在军用领域凸显潜在的应用价值。由于各类传感器广泛应用,军事系统采集到了大量移动目标的轨迹数据,但数据体量大、复杂多样且变化速度快,传统的数据分析和挖掘方法很多已不适用,难以发挥数据的效用。根据实际应用需求,论文借助大数据表示和感知的相关算法,提出了大量移动目标频繁访问的热门区域提取和轨迹相似性计算的方法,提高了计算效率,实用性较强。

轨迹分析; 大数据表示; 压缩感知; 热门区域; 轨迹相似性

Class Number TP311

1 引言

随着物联网、云计算、无线通信等技术的飞速发展以及多种传感器的广泛应用,数据种类和规模正以前所未有的速度积累,在社会、经济、国防和科技发展的方方面面起到了前所未有的重要作用,如何更好利用大数据已经成为普遍关注的话题[1]。美国政府在2012年宣布“大数据研究和发展倡议”[2],大力推动大数据的获取、存储、管理、分析和共享等技术研究,提高美国的科研、教育与国家安全能力。美军开展了包括DARPA的多尺度异常检测(ADAMS)、网络内部威胁(CINDER)、Insight、面向任务的弹性云、加密数据编程计算(PROCEED)等大数据发展战略及研究项目[3],通过海量数据感知、理解和决策支持的结合,提升战场态势感知、情报分析、智能决策以及安全防护能力,化数据优势为战争优势[4～5]。

在信息化作战中,军事系统中电、磁、声、光等形形色色的传感器不断发展与广泛应用,使得各种移动目标(如飞机、船舶等)都得到较为准确的定位和有效的追踪,采集到了大量移动目标的轨迹数据。但获取的轨迹数据体量大、复杂多样且变化速度快[6],其采集、存储、传输只解决了数据存在的问题[7],要发挥数据的效用,挖掘其中蕴含的丰富信息,必须对大数据进行分析处理[8],这直接关系到指挥者能否快速有效地分析敌方的行动企图并及时准确地做出决策。因此,提高移动目标轨迹的分析处理能力具有重要的研究价值和实战意义。

移动目标的轨迹是移动对象在某一时间段内所经过的路线,它可以表示为二维、三维甚至更高维的时间序列,移动目标轨迹具有复杂性、海量性和实时性等特点,传统的分析处理技术较难有效地发挥作用[9]。目前国内外已经开展了相关的研究工作,如轨迹聚类[10～11]、热门路径分析[12]、轨迹相似性度量[13]等,但大多集中于车辆的轨迹数据分析研究,受限于平面网络空间,如道路交通网络,通过提取一些停留点或者标志性的参考点来进行数据降维,并不适用于飞机或者船舶的轨迹数据分析。其中,有些研究考虑了移动目标的热门区域的挖掘方法,通过已有的复杂聚类算法发现所需的区域[14～15],但很少考虑大量轨迹数据分析时的计算效率,较难在实际中得以应用。

根据实际应用需求,借助大数据表示和感知的相关算法,本文从热门区域提取和轨迹相似性分析两个部分对移动目标轨迹数据进行分析,流程如图1所示。

图1 移动目标轨迹数据处理流程图

首先,针对大量移动目标的历史轨迹数据,挖掘移动目标频繁访问的热门区域,反映了移动目标的个体或群体运动模式,可辅助敌方意图判断和决策分析等。

为提高计算效率和实用性,本文将运动空间分割为不重叠的单元格,移动对象的轨迹转变为其经过的单元格,根据被访问的频率找出符合热门区域定义的若干相邻单元格的集合。计算开销只与单元格数目有关,计算量大大减少,并且针对实时数据具有较好的适用性,只需根据实时的子轨迹更新相应单元格的被访问频率。

其次,衡量移动目标轨迹之间的相似性对于提取移动对象的运动特征和分析敌方行为模式等起着重要的作用。由于大数据的高维非线性,本文通过流行的数据降维和特征提取方法,将高维原始数据映射到低维空间,保留重要信息,去除冗余信息,降低了计算复杂度,再利用基于差异和特征点集的相似性度量函数分析轨迹间的相似程度。

2 数据的表示和感知

随着大数据时代的到来,人们已经能够在不分时间和地域的情况下,方便地获取各种数据和信息。高维数据提供了有关客观现象的更加丰富和详细的信息描述,但给后续的数据分析和处理带来了前所未有的困难和挑战,可能导致计算效率低下、维度灾难、较难准确地从高维数据中找出本质的或者用户感兴趣的信息等问题。大数据的分析处理中,大数据的表示和感知是关键性环节:通过表示,大数据中高维蕴涵的有用信息得以凸现出来;通过感知,大数据中包含的重要信息得以定位和利用。

2.1 数据的表示

研究表明,高维数据中包含大量冗余信息和噪声,而其本质维度很低,需要对高维数据进行降维,即维数约简,即获取原始高维数据在低维空间中的表示,从而揭示蕴含在高维数据中的本质特性[16]。

传统的线性降维技术,如主成分分析(Principal Component Analysis,PCA)、线性判别分析(Linear Discriminant Analysis,LDA)等,对具有线性结构分布的数据集进行一定的维数约简,计算简单,易于理解,但现实世界中所获得的真实数据集更多呈现出结构非线性或属性强相关性,线性方法较难适用。

基于流形学习的降维方法是近年发展起来的非线性降维方法[17],假设高维观测数据采样于一个潜在的低维流形上,通过某种显示或隐式的映射关系学习出此假设存在的流形,并将原始数据从周围观测空间投影到一个低维嵌入空间,反映了数据的本质特征。假设给定数据集X={x1,x2,…,xn}⊂RD,其中X中的样本是由低维空间的数据集Y={y1,y2,…,yn}⊂Rd通过某个位置的非线性映射f所生成,即

xi=f(yi)+εi

(1)

式(1)中,εi表示噪声,d≪D,f:Rd→RD是嵌入映射,那么,流形学习的任务是基于给定的观测数据集X:

1) 获取低维表达Y={yi,i=1,2,…,n};

2) 构造从高维空间到低维空间的非线性映射f-1:RD→Rd。

数据降维不仅可以将高维数据压缩到低维空间,而且能够提取反映原始数据集的本征特征,为聚类、分类、可视化等后续分析工作提供更有价值的信息。

2.2 数据的感知

在大数据环境下,由于高维空间存在着稀疏性、空空间现象等特性,经典的聚类算法在高维数据空间上进行聚类分析时效果很差。大数据的量大且价值密度低的先天特性呼唤着有效感知数据核心规律的计算体系。压缩感知作为近年来兴起的信号处理手段,强调在大量数据中选择出“核心价值”,为简约数据规模、感知数据机理、揭示数据结构提供了必要的理论保障。

压缩感知(Compressed Sensing,CS)理论与传统奈奎斯特采样定理不同[17],它认为,如果信号在某一变换域上是稀疏的,就可以用一个与变换基不相关的观测矩阵将变换所得高维信号投影到一个低维空间上,然后通过求解优化问题就可以用此信号在某投影域上的观测向量来近似无损地重构原信号。

在压缩感知理论中,对于稀疏结构的探求可以描述为下列优化问题:

xl0=argmin‖x‖l0s.t.φx=y

(2)

式(2)中,‖ ‖l0表示l0范数,即零范数,表示矩阵中非零元素的个数,φ是一组观测矩阵,而y为现实世界中观测到的信号。然而,对于上述问题l0的优化求解是NP难问题,可以通过相应方法近似求解,获得高维数据的低维特征,大大提高了后续分析的计算效率。

3 移动目标轨迹分析

3.1 热门区域提取

热门区域通常是指移动对象频繁经过的区域,一定程度上反映着移动目标的个体或群体运动模式,可辅助敌方意图判断和决策分析等。本文针对大量移动目标的高维轨迹数据,将移动对象的运动空间分割为许多不重叠的二维或三维的单元格[11],移动对象的连续轨迹转变为其可能经过的单元格,通过统计单元格被访问次数和不同轨迹相交的单元格的频次[12],找出符合热门区域定义的若干相邻单元格的集合。其优势在于计算量大大减小,提高热门区域发现的效率,计算的开销只与单元格的数目有关[14],只要这些单元格足够小,该方法就可以提供较好的近似结果。

1) 轨迹网格化

由于轨迹数据是离散采样的,假设在二维坐标中给定两个连续的轨迹点Pm(xm,ym)和Pm+1(xm+1,ym+1)(对应时间点为tm和tm+1),可以根据移动目标的当时速度找出在Δt时间内移动目标可能的覆盖区域。由于车辆行驶轨迹灵活多变,已有椭圆、最小边界矩形、对称六边形等几种覆盖区域计算方法[14],然而飞机、船舶等敌方目标轨迹数据采样间隔相对较小,可以在Δt时间内的移动近似视为直线运动,即将两轨迹点连线经过的单元格视为其经过区域,相应简化的计算步骤如下。

首先将子轨迹PmPm+1等分为一系列子轨迹点Pk,则点Pk所在的单元格

(3)

其中l为单元格的长度,fix函数为取整函数,k=1,2,…,10,k值范围可根据单元格长度和轨迹点之间的距离调整。

相应地,子轨迹PmPm+1所经过的单元格的计算简化为每个子轨迹点所在单元格的并集,如下式所示。

Tri(PmPm+1)= {Grid(x1,y1)}∪{Grid(x2,y2)}

∪…∪{Grid(xm+1,ym+1)}

(4)

对每一段子轨迹做同样操作,可获得每条轨迹在单元格上的投影,最终将移动目标经过的一系列时空点转化为经过的一系列单元格{{Tri(PmPm+1)}}。

2) 频繁访问的单元格提取

在给定时间间隔Δt和相应的所有移动目标的历史轨迹{Tr1,Tr2,…,Trn}中,某个单元格Grid(a,b)的被访问的频率(Frequency)可表示为

Frequency(Grid(a,b))=N(a,b)/Δt

(5)

其中,N(a,b)是在时间段Δt内所有移动目标穿过单元格Grid(a,b)的次数。根据上述计算,由每条轨迹Tri经过的单元格{{Tri(PmPm+1)}}来构建单元格被访问的频次的矩阵Mi,其中

Mi(a,b)=

(6)

其中,Num(Grid(a,b))表示在时间段Δt内轨迹{{Tri(PmPm+1)}}穿过单元格Grid(a,b)的次数,最小值为1。

那么时间间隔Δt所有历史轨迹经过单元格Grid(a,b)的次数N(a,b)可表示为

N(a,b)=∑iMi(a,b)

(7)

将式(6)和式(7)带入到计算即可获得单元格Grid(a,b)在一定时间段内被所有移动目标穿过的频率。

将频繁访问的单元格定义为:若某个单元格被访问的频率大于等于设置的频率阈值δ1,则称该单元格为核心单元格;若某个单元格被访问的频率大于等于设置的频率阈值δ2,则称该单元格为重要单元格。阈值参数与移动目标的数目等数据相关联,可根据实际应用需求进行更改,其值越大,符合要求的区域也就越少。

(8)

经过上述步骤,根据某时间段内所有移动目标的历史轨迹将空间分为频繁访问的核心单元格、重要单元格和一般单元格。

3) 热门区域的发现

在实际过程中,某个区域可能由几个单元格组成,而单元格本身只是由划分获得一些不重叠的子区域,需要对单元格进行分类,进而组合成需要关注的热门区域。本文根据以下三个步骤来发现热门区域:

Step 1 若Grid(a,b)和Grid(c,d)是核心单元格且相邻,那么该热门区域为包含这两个核心单元格的最小外接矩形;

Step 2 若Grid(m,n)为重要单元格,且邻域中存在不相邻的若干个核心单元格或热门区域,那么更新后的热门区域应为包含上述区域的最小外接矩形;

Step 3 若两个热门区域存在相交区域,更新后的热门区域为包含上述区域的最小外接矩形。

每个步骤重复执行,直到没有更新再执行下一步骤。通过最小外接矩形框定热门区域符合使用习惯,也可以通过最小区域或其他图形来框定。

上述方法针对实时数据具有较好的适用性,只需要根据轨迹数据更新的子轨迹更新单元格的访问频率,不需要重新计算。上述过程使用二维平面位置数据举例分析,三维数据也可以采用上述过程进行分析。

3.2 轨迹相似性分析

移动目标的轨迹相似性分析是移动目标轨迹分析的典型应用之一,其目标就是从历史轨迹中找到相似的运动轨迹,提取移动对象的运动特征模式,便于敌方行为模式和意图分析等。轨迹相似性分析通过对轨迹数据降维和特征信息提取,确定轨迹间的相似程度,然后将相似程度较高的轨迹归为一类[19]。由于每个轨迹数据Tri由一系列的离散点组成,表示每条轨迹的维度较高,对于计算两条轨迹的相似性,传统的方法考虑计算所有的数据,计算量较大且效率较低。

1) 数据降维

本文采用流形学习中的局部线性嵌入法(Locally Linear Embedding,LLE)[20]进行数据降维。给定轨迹数据集Tr,其中Tri∈RD,i=1,…,N,其中N为样本总数,D为原始空间维数,在每个样本点寻找它的邻域{Tri(1),…,Tri(k)},Tri(k)∈Tr,然后通过求解如下一个约束最小二乘优化问题来计算最小重构权值。

(9)

将其转化成求解一个可能奇异的线性方程组,并通过引入一个小的正则因子来保证线性方程组系数矩阵的非奇异性。求出重构权值后,利用这些重构权值可以构造一个稀疏矩阵。

M=(I-W)T(I-W)

(10)

通过求解这个稀疏矩阵的几个最小特征值对应的特征向量来获得数据的低维嵌入{LTri},其中LTri∈Rd,d≪D。

2) 特征提取

基于压缩感知的特征提取来降低分析数据的维度也是一种可行的方法。基于上述原始高维数据的稀疏表示,采用稀疏子空间聚类(Sparse Subspace Clustering,SSC)方法,假设数据间的仿射矩阵是稀疏的,l0最小化问题的求解可以通过其凸包络[21],即l1来求解。因此,优化下列目标取而代之。

xl1=argmin‖x‖l1s.t.φx=y

(11)

式中,l1范数表示了信号中所有元素绝对值之和,上述优化目标可以通过凸优化的方式得以求解。基于l1范数的凸优化算法有基追踪算法(Basis Pursuit,BP)、梯度投影法、内点迭代法等,可将约束条件转换为惩罚项,构造非约束优化问题,如式(12)所示,控制参数可视为求解约束优化问题的Lagrange乘数,具体的计算步骤见文献[22]。

(12)

其中,原始数据为轨迹数据集Tr,Tri∈RD,通过求解获得特征数据FTr其中FTri∈Rm,m≪D,即轨迹上运动或状态发生明显变化的点,降低数据维度,去除冗余信息,找到蕴含其中的本质特性,便于后续的分析工作。

对轨迹数据采用数据降维或特征提取主要根据分析实际数据的效果进行选择,也可以结合考虑,目前上述两种方法都应用较广。

3) 相似性度量

如何衡量每对轨迹段之间的相似程度,是需要解决最重要的问题之一。为了简化计算,很多研究采用Hausdorff距离公式来衡量轨迹片段之间的差异[13],如式(13)和式(14)所示。

Diff(LTri,LTrj)= max(h(LTri,LTrj),

h(LTrj,LTri))

(13)

(14)

其中,h(LTri,LTrj)为直接Hausdorff距离,即LTri中的点到最近LTrj中的点的最大距离,dist(P,Q)表示两个轨迹点之间的欧式距离。

但由于轨迹数据中可能包含一些噪声点和异常点,对计算的结果影响较大,所以对于异步的轨迹数据,本文采用式(15)来衡量两个轨迹之间的差异。

(15)

其中,h(LTri,LTrj)为LTri中的点到最近LTrj中的点的平均距离。通过计算两条轨迹之间的差异就可以获得两条轨迹之间的相似性,如式(16)所示。

(16)

由上述公式可以看出,通过数据降维可以有效地降低相似性度量的计算量。

对于通过稀疏学习提取或自定义的特征点FTri,可以通过轨迹之间特征点集的关系计算两条轨迹之间的相似性,如式(17)所示,num表示集合中元素的个数。

(17)

4 结语

本文借助于大数据表示和感知的相关算法,针对蕴含重要信息的大量移动目标的轨迹数据,从实际应用角度出发,提出了大量移动目标频繁访问的热门区域提取和轨迹相似性计算的方法,降低了数据维度,提高了计算效率,实用性较强。可通过更先进的大数据技术,进一步对移动目标轨迹进行聚类、分类、预测等分析处理,挖掘出更多隐含的有用信息。

大数据技术在情报信息提取及处理、信息网络防御、网络安全及监控、作战指挥等方面开始发挥着越来越重要的作用,重点是研究海量数据分析、大数据处理、数据可视化等一些关键方法和技术,与国外相比还存在较大的差距。本文通过对移动目标轨迹大数据的分析处理,为大数据技术尽早在国防军事系统中广泛应用抛砖引玉。

[1] Mayer-Schönberger Viktor.大数据时代[M].周涛,译.杭州:浙江人民出版社,2012.

[2] Big Data Across the Federal Government[EB/OL]. http://www.whitehouse.gov/sites/default/files/microsites/ostp/big_data_fact_sheet_final_1.pdf,2012-10-02.

[3] 庄林,沈彬.美国国防部大数据项目研发与应用[J].国防科技,2013,34(3):58-61.

[4] 蒋盘林.大数据通用处理平台及其在ISR领域的潜在军事应用[J].通信对抗,2013,32(3):1-5.

[5] 李纪舟.美军大数据发展战略及对我启示[J].外军网络空间战,2012(4).

[6] 孟小峰,慈祥.大数据管理:概念、技术与挑战[J].计算机研究与发展,2013,50(1):146-169.

[7] 王珊,王会举,覃雄派,等.架构大数据:挑战、现状与展望[J].计算机学报,2011,34(10):1741-1752.

[8] 何清,李宁,罗文娟,等.大数据下的机器学习算法综述[J].模式识别与人工智能,2014,27(4):327-336.

[9] Zheng Y, Zhou X F. Computing with spatial trajectories[M]. New York: Springer-Verlag,2011:143-177.

[10] Kharrat A, Popa I S, ZeitouniKarine, et al. Clustering algorithm for network constraint trajectories[C]//Proceedings of 13th International Symposium on Spatial Data Handling, Montpellier, France: Springer,2008:631-647.

[11] Mamoulis N, Cao H P, Kollios G, et al. Mining, indexing, and querying historical spatiotemporal data[C]//Won K, Ron K, Johannes G, William D, eds. Proc. of the 10th ACM SIGKDD Int’l Conf. on KnowledgeDiscovery and Data Mining(KDD 2004). New York: ACM Press,2004:236-245.

[12] Verhein F, Chawla S. Mining spatio-temporal association rules, sources, sinks, stationary regions and thoroughfares in objectmobility databases[C]//Lee M, Tan KL, Wuwongse V, eds. Proc. of the 11th Int’l Conf. on Database Systems for Advanced Applications. Berlin, Heidelberg: Springer-Verlag,2006:187-201.

[13] Vlachos M, Gunopulos D, Kollios G. Robust similarity measures for mobile object trajectories[C]//Proceedings of the 13th International Workshop on Database and Expert Systems Applications. IEEE Computer Society,2002:721-728.

[14] 刘奎恩,肖俊超,丁治明,等.轨迹数据库中热门区域的发现[J].软件学报,2013,24(8):1816-1835.

[15] Giannotti F, Nanni M, Pedreschi D, et al. Trajectory pattern mining[C]//Berkhin P, Caruana R, Wu XD, eds. Proc. of the 13thACM SIGKDD Int’l Conf. on Knowledge Discovery and Data Mining(KDD 2007). New York: ACM Press,2007:330-339.

[16] 赵连伟,罗四维,赵艳敞,等.高维数据流形的低维嵌入及嵌入维数研究[J].软件学报,2005,16(8):1423-1430.

[17] 王自强,钱旭,孔敏.流形学习算法综述[J].计算机工程与应用,2008,44(8):9-12.

[18] Donoho D L. Compressed sensing[J]. IEEE Transactions onInformation Theory,2006,52(4):1289-1306.

[19] Gariel M, Srivastava A N, Feron E. Trajectory clustering and an application to airspace monitoring[J]. IEEE Transaction on Intelligent Transportation Systems,2011,12(4):1511-1524.

[20] Chang H, Yeung D Y. Robust locally linear embedding[J]. Pattern Recognition,2006,39(6):1053-1065.

[21] E. Elhamifar, R. Vidal. Sparse subspace clustering[C]//IEEE Conference on Computer Vision and Pattern Recognition,2009:2790-2797.

[22] Cong Wu, Bo Li, Shu Shen, et al. Vehicle classification in pan-tilt-zoom videos via sparse learning[J]. Journal of Electronic Imaging,2013,22(4):041102-1-12.

An Analysis Method of Moving Object Trajectories Based on Data Dimensionality Reduction

WU Cong CUI Jun SHI Weifeng

(The 28th Research Institute of CETC, Nanjing 210007)

Big data is another technological revolution in information technology domain, has highlighted the potential applications in the military field. Due to the wide application of various types of sensors, a large number of moving object trajectories has been collected. But the data is volume, complicated and fast changing, traditional data analysis and mining is no longer applicable in many ways. According to the actual application requirements, with big data representation and sensing algorithms, a method of hot region extraction and similarity measures for trajectory databases is proposed, which improves the computational efficiency and practicability.

trajectory analysis, big data representation, compressed sensing, hot region, trajectory similarity

2015年3月11日,

2015年4月26日

吴聪,男,博士,工程师,研究方向:数据分析和辅助决策。崔隽,男,博士,工程师,研究方向:数据建模和数据分析。施卫峰,男,硕士,高级工程师,研究方向:防空作战指挥。

TP311

10.3969/j.issn.1672-9730.2015.09.010