基于加权矢量场的轨迹层次聚类*

陈 琳， 王 蒙

(昆明理工大学 信息工程与自动化学院，云南 昆明 650500)

基于加权矢量场的轨迹层次聚类*

陈 琳， 王 蒙

(昆明理工大学 信息工程与自动化学院，云南 昆明 650500)

传统的轨迹聚类方法存在定义轨迹相似度难度大，聚类过程中容易忽略轨迹细节等问题。基于矢量场的轨迹聚类(VFC)在保持轨迹原始运动特征的基础上，利用矢量场的几何结构可以很好地度量轨迹相似度。引入加权拟合方法，降低噪声对聚类的影响，以解决VFC鲁棒性较差问题。采用层次聚类动态地决定聚类类别数，以解决聚类类别数不能自适应的问题，提高聚类有效性。采用亚特兰大飓风数据作为实验原始轨迹数据，分别使用经典矢量场的轨迹聚类，k-means聚类，k-mediods聚类以及提出的方法进行实验，实验结果证明了加权拟合矢量场的层次聚类算法的有效性。

轨迹； 矢量场聚类； 加权拟合； 层次聚类

0 引 言

轨迹是对一个移动对象位置和时间的记录序列。作为一种重要的时空对象数据类型和信息源，轨迹的应用范围涵盖了人类行为、交通物流、应急疏散管理和动物习性等诸多方面。生态学家通过学习动物的运动，来获取动物种群的增长，迁徙模式[1]。气象学家通过轨迹数据来帮助预测风暴的路径[2]。

目前，轨迹聚类的方法主要包括两类，一类是将轨迹嵌入到一个度量空间中，定义轨迹的相似度概念，使用基于轨迹点的聚类。Lee J G等人[3]提出关于轨迹聚类的新的分割与群组的框架，将一条轨迹划分成不同的段，然后将相似的段聚到一类中。Gudmundsson J等人[4]将多个领域的轨迹数据嵌入运动空间进行概念建模,该方法的缺点是，定义轨迹相似度难度大，容易忽略轨迹中细节的部分。另一类是基于模型的方法,Wei J等人[5]扩展和并行化回归模型对大量轨迹进行聚类。Gaffney S J等人[6]采用曲线混合模型对经纬度空间的冬季温带气旋进行概率聚类。这种方法模型适应性不强，轨迹数据不同需要的聚类模型不同。

基于矢量场轨迹聚类(VFC)方法，可以有效地解决上述定义轨迹相似度难度大，容易忽略轨迹中细节部分和算法适应性不强等问题。VFC算法利用轨迹的几何结构来自动编码轨迹特征，从而度量轨迹相似度，很好地保留轨迹原有特征。Ferreira N等人[7]通过VFC算法，研究台风运动与GPS行人追踪等。Brillinger D R等人[8]利用VFC算法研究动物的运动规律。Camargo S J[9]利用VFC算法研究台风的活动规律。文献[7～9]存在聚类类别不能自适应，没有考虑采集轨迹过程中的量测噪声，算法鲁棒性差等问题。

针对上述VFC算法中聚类类别数不能自适应的问题，本文提出了层次聚类的方法。将矢量场作为聚类依据，通过设置阈值使算法自动对轨迹进行分类。针对算法鲁棒性差，易受噪声干扰的问题，提出加权拟合矢量场的方法。给噪声数据分配较小的权重，减小噪声数据对矢量场拟合的影响。通过实验对基于加权矢量场的轨迹层次聚类(WVFHC)进行验证，效果较好。

1 基于加权矢量场的轨迹层次聚类算法

1.1 数据预处理

点bsj(x,y)为轨迹Ti上一坐标点，点Q11(x11,y11),Q12(x12,y12),Q21(x21,y21),Q22(x22,y22)为bsj(x，y)周围最近的4个坐标点如图1(a)。定义dx=x-[x],dy=y-[y]，则点Q11(x11,y11)，Q12(x12,y12)，Q21(x21,y21)，Q22(x22,y22)可以通过bsj(x,y)表示

Q11(x11,y11)=bsj(x,y)·dx·(1-dy)

(1)

Q21(x21,y21)=bsj(x,y)·dx·dy

(2)

Q22(x22,y22)=bsj(x,y)·(1-dx)·dy

(3)

Q12(x12,y12)=bsj(x,y)·(1-dx)·(1-dy)

(4)

图1 双线性插值和拉普拉斯贝特拉米算子

1.2 轨迹数据矢量场拟合

假设对于一组轨迹数据α={T1,T2,…,Tn}存在一组平滑的矢量场Xj来解释这组轨迹中的移动规律,即需要找到矢量场Xj与类别集合Φ∶α→{1,2,…,k}来解释该组轨迹的移动规律。

如图1(b)所示采用拉普拉斯贝特拉米算子L作为平滑矩阵对矢量场进行平滑

(5)

则该组轨迹的移动规律可以表示为

(6)

式中L为拉普拉斯余切矩阵；Xj为拟合之后的矢量场。

用矩阵的形式表示并进行最小二乘拟合，定义能量函数E，则式(6)可化简为求E=‖LX‖2+‖CX-b‖2的最小值,其中，C为网格数据，b为原始轨迹数据。

1.3 轨迹数据加权矢量场拟合

在轨迹数据采集过程中设备误差可能会生成存在噪声的轨迹数据，若直接运算，可能对聚类结果产生影响,进行加权拟合，会降低噪声对聚类结果的影响。加权矢量场拟合的核心部分为权值的确定，权值通过调谐常数cH与局部估计噪声偏差σ共同确定[10，11]。其中

σ=1.482 6 med|ri-medri|

(7)

式中 ri为第i个数据点的残差。

(8)

式中cH为调谐常数，取固定值1.345;wH,i为权重矩阵。

通过迭代更新权值矩阵wH,i，定义停止准则F(l)来停止迭代过程

(9)

式中l为当前迭代过程。当第l次迭代过程与第l-1次迭代过程的差值小于0.001时，迭代收敛，即

|F(l)-F(l-1)|<0.001，l=1,2,…

(10)

对能量函数E中的拟合部分进行加权,即

E=‖LX‖2+‖W(CX-b)‖2

(11)

X=(LTL+CTWTWC)CTWTWb

(12)

式中W为权重矩阵。

1.4 矢量场层次聚类

VFC算法聚类类别数需提前设定，适应性较差。使用层次聚类，通过设置阈值动态地决定聚类类别数，提高算法的适应性。

WVFHC算法步骤如下：

1)输入：轨迹数据α={T1,T2,…,Tn},th;

2)初始化：根据1.1节将轨迹数据映射到网格Ci上，i=1;

3)根据式(12)由Ci得到Xi;

4)i=i+1;

5)若i

6)采用层次聚类方法，根据聚类阈值th对V聚类得到M类，Φj={Φj,j=1,2,3,…,M}(M不固定)，且{Xi,i∈Φj};

7)分别输出聚类后的矢量场Yj。

2 实验结果与分析

2.1 实验设计与评价指标

用文献[7]中的飓风数据以及人造数据作为实验数据。用飓风数据进行了VFC算法，k-means[12～14]算法，k-medoids[15]算法以及VFHC算法实验。用人造数据进行了VFHC算法与WVFHC算法实验。

采用4种性能评价指标[16]：RS(R-Squares)[17，18],CH指数(Calinski-Harabaszindex)[19],DB指数(Davies-Bouldinindex)[20]与修正的HubertГ统计(ModifiedHubertΓstatistic)[21]。QCH，QRS，QГ值越高聚类结果越准确,QDB值越小聚类结果越准确。

2.2 实验结果与分析

2.2.1 真实数据集

利用文献[7]中的飓风数据作为真实数据集，包含1 415条轨迹。

设置不同的阈值，得到不同的聚类类别数，结果如表1所示,NC为聚类类别数。图2(a)～(d)为评价指标折线图，可以看出:在阈值为“1.5”时，QDB发生异常变化，其他指标没有出现异常，所以阈值为“2.5”，“2”与“1.8”时，聚类效果较好，对应的类别数分别为“4”，“5”与“6”。

图2(e)～(h)为4种算法评价指标直方图，可以看出:在聚类类别数为“4”，“5”，“6”时。VFHC算法的聚类效果更好。因为在聚类类别数较小时，k-means算法,k-medoids算法与VFC算法固定了聚类类别数，使每一类中的轨迹数据方差变大，所以聚类效果较差。VFHC算法通过阈值获取聚类类别，每一类中的轨迹数据相似度更高，所以聚类效果更好。图4为VFHC算法在阈值为2.5时各类别的矢量场图。

图2 实验结果

图3 实验数据

图4 阈值为2.5时各类的矢量场图

阈值评价指标QCHQDBQRSQГ2．5(NC=4)7．64×1050．00280．0888851．97782(NC=5)9．54×1050．00170．010971．90081．8(NC=6)1．18×1060．03180．16595．81991．5(NC=7)1．35×106183．50470．21123．18881．3(NC=9)1．57×106108．77830．2102183．1176

2.2.2 人造数据集

从飓风数据中随机选取142条轨迹，加入噪声得到人造数据集。原始轨迹数据与噪声轨迹数据如图3(b)，图3(c)所示。将人造数据替换原来的轨迹数据作为人造数据集。采用加权拟合与不加权拟合得到矢量场，进行层次聚类。

图2(i)～(l)为评价指标直方图，可以看出，WVFHC算法的聚类效果好。因为加入噪声后，VFHC算法将异常数据作为正常数据进行矢量场拟合，影响聚类结果。而WVFHC算法通过给异常数据分配较小的权重，降低异常数据的影响，所以聚类效果较好。

3 结 论

本文提出WVFHC方法，对真实轨迹数据与人造轨迹数据进行聚类。VFHC方法能够解决VFC算法聚类类别数不能自适应的问题。通过与k-means算法，k-medoids算法，VFC算法的实验对比得出，在聚类类别较小时效果较好，但在聚类类别较大时效果较差。通过WVFHC方法对人造轨迹数据进行聚类，能够降低噪声的干扰，增强算法的鲁棒性。通过与VFHC算法的对比得出，WVFHC算法效果更好。在今后的研究中，研究重点为改进WVFHC算法，增强算法的适应性。

[1] Grundy E,Jones M W,Laramee R S,et al.Visualisation of sensor data from animal movement[J].Computer Graphics Forum,2009,28(3):815-822.

[2] Camargo S J,Robertson A W,Gaffney S J,et al.Cluster analysis of typhoon tracks[J].Journal of Climate,2007,20(14):3654-3676.

[3] Lee J G,Han J,Whang K Y.Trajectory clustering:A partition-and-group framework[C]∥Proceedings of the 2007 ACM SIGMOD International Conference on Management of Data,ACM,2007:593-604.

[4] Gudmundsson J,Laube P,Wolle T.Computational movement analysis[M].Berlin Heidelberg：Springer,2012:423-438.

[5] Wei J,Wang C,Yu H,et al.A sketch-based interface for classi-fying and visualizing vector fields[C]∥2010 IEEE Pacific Visua-lization (PacificVis)Symposium,IEEE,2010:129-136.

[6] Gaffney S,Smyth P.Trajectory clustering with mixtures of regression models[C]∥Proceedings of the Fifth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,ACM,1999:63-72.

[7] Ferreira N,Klosowski J T,Scheidegger C E,et al.Vector fieldk-means:Clustering trajectories by fitting multiple vector field-s[C]∥Computer Graphics Forum,2013:201-210.

[8] Brillinger D R,Preisler H K,Ager A A,et al.An exploratory data analysis(EDA)of the paths of moving animals[J].Journal of Statistical Planning and Inference,2004,122(1):43-63.

[9] Camargo S J,Robertson A W,Gaffney S J,et al.Cluster analysis of typhoon tracks—Part II:Large-scale circulation and ENSO[J].Journal of Climate,2007,20(14):3654-3676.

[10] Meer P,Mintz D,Rosenfeld A,et al.Robust regression methods for computer vision:A review[J].International Journal of Computer Vision,1991,6(1):59-70.

[11] 严筱永,钱焕延,施卫娟,等.一种利用统计中值的加权定位算法[J].传感器与微系统,2011,30(8):120-123.

[12] MacQueen J B.On the asymptotic behavior ofk-means[R].Los Angeles:Western Management Science Inst,Univ of California at Los Angeles,1965.

[13] 王联国,韩晓慧,宋 磊.基于改进混合蛙跳-K均值聚类算法的无功电压控制分区[J].传感器与微系统,2013,32(6):18-21.

[14] 张乙竹,周礼争,唐 瑞,等.基于k-means聚类点密度的WSNs加权质心定位算法[J].传感器与微系统,2015,34(7):125-127.

[15] Kaufman L,Rousseeuw P.Clustering by means of medoids[M].Amsterdam:North-Holland Publisher,1987.

[16] Liu Y,Li Z,Xiong H,et al.Understanding of internal clustering validation measures[C]∥2010 IEEE 10th International Confe-rence on Data Mining(ICDM),IEEE,2010:911-916.

[17] Sharma S.Applied multivariate techniques[M].New York:John Wiley & Sons Inc,1995.

[18] Halkidi M,Batistakis Y,Vazirgiannis M.On clustering validation techniques[J].Journal of Intelligent Information Systems,2001,17(2):107-145.

[19] Caliński T,Harabasz J.A dendrite method for cluster analy-sis[J].Communications in Statistics-theory and Methods,1974,3(1):1-27.

[20] Davies D L,Bouldin D W.A cluster separation measure[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,1979(2):224-227.

[21] Hubert L,Arabie P.Comparing partitions[J].Journal of classification,1985,2(1):193-218.

王 蒙(1985-)，博士，讲师，主要从事计算机视觉、图像处理、机器学习，以及语音识别方向研究工作,E—amil:vicong@live.com。

Trajectory hierarchical clustering based on weighted vector field*

CHEN Lin, WANG Meng

(School of Information Engineering and Automation,Kunming University of Science and Technology,Kunming 650500,China)

It is hard to define similarity of trajectories and trends to ignore details of trajectories using a traditional trajectory clustering method.Vector field based clustering methods keep the inherent features of movements and measures similarities of trajectories with the geometric structure information derived from it.Weighted fitting scheme is introduced to weaken the effects of noises and increase the robustness of clustering.A hierarchical approach is employed to automatically determine the number of class solving the problem that traditional methods cannot be self-adaptive to clustering,thus improving the effectiveness of our method.Experiments of traditional vector field clustering,k-means clustering andk-mediods clustering as well as the proposed method are conducted on the Atlanta Hurricane dataset,and the result shows the effectiveness of the hierarchical clustering algorithm based on weighted vector field.

trajectory; vector field clustering; weighted fitting; hierarchical clustering

2016—06—08

国家自然科学基金地区基金资助项目(61563025)；云南省教育厅科学研究基金资助项目(2015Z047)

10.13873/J.1000—9787(2017)06—0010—04

TP 311

A

1000—9787(2017)06—0010—04

陈 琳(1992-)，男，硕士研究生，主要研究方向为计算机视觉、模式识别。