一种基于时空多维特征的轨迹数据聚类方法

1.本发明涉及数据聚类分析技术领域，更具体地说，它涉及一种基于时空多维特征的轨迹数据聚类方法。


背景技术：

2.空间聚类是一种重要的数据分析技术，搜索并且识别一个有限的种类或簇集合，进而描述空间数据。通过聚类，人们能够识别密集和稀疏的区域，进而确定全局分布模式和数据属性之间的有趣关系。空间聚类分析作为统计学的一个分支，已经被研究了许多年，并在城市规划、生态环境、公共卫生、交通系统、市场分析等多个领域得到了广泛的应用。
3.空间聚类方法分为基于分区的方法、基于分层的方法、基于密度的方法、基于图的方法、基于模型的方法、基于网格的方法和其他方法。通过对比分析，这些算法存在初始点选择、敏感参数设置、全局最优解、相邻单元独立性、大尺度数据处理慢等问题。因此，聚类算法的选择应充分考虑求解问题的聚类要求，这需要对现有的聚类技术进行改进，并不断发展新的聚类理论和方法以适应新的应用。
4.随着时间维属性添加到数据挖掘中，时空聚类得到了发展。时空数据聚类可以在一系列事件中获得空间分布规律，可用于识别热点并生成新的空间研究单位。许多学者将时空聚类应用于不同的领域。nanni和pedreschi基于轨迹之间距离的简单概念，使用了带有轨迹数据的基于密度的聚类算法。这种方法对数据集的密度很敏感，算法中的密度参数可能会影响聚类的质量。birant和kut提出了一种对时空数据进行聚类的算法，该算法能够根据对象的非空间，空间和时间值来发现聚类。但是，该算法无法解决多维线性不等式。zhao等人提出了一种基于图的聚类算法来选择聚类参数，确定聚类数量和识别聚类中心。但是，该算法无法处理非欧几里得空间中的时空数据。这些算法针对某些特定问题或领域取得了较好的聚类结果，但不适用于多维时空数据聚类。
5.时空数据通常具有多维和海量的特征。然而，基于上述分析，大多数先前应用的时空数据(例如轨迹点)聚类方法必须在计算前设置初始聚类中心、聚类半径等敏感参数。不同的参数设置将产生不同的结果，许多实验无法管理具有不同参数的大量数据。因此，需要一种聚类方法可以在参数设置较少的情况下自动获得最优解。此外，在分析多维时空数据时，必须同时考虑位置特征以及时间和专题属性以获得准确的结果。
6.近邻传播聚类算法(ap)是在2007年的《science》杂志上提出的一种新型聚类算法。由于不需要提前指定聚类的数量，因此可以解决选择初始类代表点的问题。ap算法还可以解决非欧几里得空间(例如不满足对称性或三角形不等式)和大规模稀疏矩阵计算的相关问题，并以较少的参数设置快速处理大规模数据。研究人员已将ap算法应用于社区结构分析，模式识别，生物工程等领域，这促进了该算法的发展。考虑到ap算法的优势，适用于时空数据聚类；然而，由于自动获得最佳聚类类别很困难，其在不可分割的多维线性条件下聚类性能较差，因此提出本发明所提供的一种基于时空多维特征的轨迹数据聚类方法(mdst-ap)。


技术实现要素：

7.本发明的目的是提供一种基于时空多维特征的轨迹数据聚类方法，该方法可以更好地提取多维时空数据中的隐藏信息，适用于聚类分析。
8.本发明的上述技术目的是通过以下技术方案得以实现的：一种基于时空多维特征的轨迹数据聚类方法，所述方法考虑不同维度下的多类属性，提出高斯核变换方法来解决多维属性距离计算时线性不可分割问题,自适应参数设置方法来解决聚类算法的参数设置问题，具体包括以下4个步骤：
9.s1.数据预处理；
10.s2.相似性矩阵建立；
11.s3.吸引度和归属度计算；
12.s4.聚类有效性评价。
13.本发明进一步设置为：所述数据预处理包含数据选择、地图匹配和归一化，其具体操作如下：保留必要数据，删除错误数据，使用最短距离法将轨迹点与道路网进行匹配。
14.本发明进一步设置为：所述相似性矩阵建立需要考虑多维属性的相似性和高斯核下数据的距离；
15.所述多维属性的相似性包括空间属性、时间属性和专题属性之间的相似性；
16.所述高斯核下数据的距离公式如下：
[0017][0018]
其中
[0019][0020][0021]
对于任意的x，y∈x，x是样本空间，l、b、s、d可代表时空轨迹点的位置属性、速度属性、方向属性(或包含更多的属性)。
[0022]
本发明进一步设置为：所述吸引度和归属度计算公式如下：
[0023][0024][0025]
其中偏向参数s(i,j)＝-dh(i,j)，即时空数据相似度矩阵中距离的负值，i、j、k为时空数据。当s(k,k)较大时吸引度r(k,k)较大时，归属度a(i,j)也较大，从而类数据点k作为最终聚类中心的可能性较大；同样，当越多的s(k,k)较大时，越多的类代表倾向于成为最终的聚类中心。因此，增大或减小s(k,k)可以增加或减少输出的聚类数目。
[0026]
本发明进一步设置为：所述聚类有效性评价依赖于db指数，所述db指数的计算公式如下：
[0027][0028]
其中c
ij
＝‖v
i-vj‖，表示ci与cj的类间离散程度，wi表示第i类的类内平均离散程度，vi、vj表示簇ci与cj的质心，∣ci∣表示簇ci中的数据点个数，k表示聚类数。
[0029]
综上所述，本发明具有以下有益效果：本发明所提供方法可以更好地提取多维时空数据中的隐藏信息，适用于聚类分析。该方法在开源的四个数据集上的平均聚类准确率为85％，平均计算时间为4.31秒。同时利用k-means算法、ap算法、与mdst-ap算法在真实的某一天轨迹数据进行了聚类分析，结果表明本方法对实际交通状况的判断精度优于前两种方法。说明mdst-ap方法能够在相对较短的时间内可获得比ap算法更好的聚类结果。
附图说明
[0030]
图1是本发明方法原理的流程图。
具体实施方式
[0031]
以下结合附图1对本发明作进一步详细说明。
[0032]
实施例：一种基于时空多维特征的轨迹数据聚类方法，如图1所示，所述方法考虑不同维度下的多类属性，提出高斯核变换方法来解决多维属性数据相似度线性不可分割问题,自适应参数设置方法来解决聚类算法的参数设置问题，具体包括以下4个步骤：
[0033]
s1.数据预处理；
[0034]
s2.相似性矩阵建立；
[0035]
s3.吸引度和归属度计算；
[0036]
s4.聚类有效性评价。
[0037]
所述数据预处理包含数据选择、地图匹配和归一化，其具体操作如下：保留必要数据，删除错误数据，使用最短距离法将轨迹点与道路网进行匹配。
[0038]
所述相似性矩阵建立需要考虑多维属性的相似性和高斯核下数据的距离；
[0039]
所述多维属性的相似性包括空间属性、时间属性和专题属性之间的相似性；
[0040]
所述高斯核下数据的距离公式如下：
[0041][0042]
其中
[0043][0044]
对于任意的x，y∈x，x是样本空间。
[0045]
吸引度和归属度计算公式如下：
[0046]
[0047][0048]
其中偏向参数s(i,j)＝-dh(i,j)，即时空数据相似度矩阵中距离的负值，i、j、k为时空数据。
[0049]
所述聚类有效性评价依赖于db指数，所述db指数的计算公式如下：
[0050][0051]
其中c
ij
＝‖v
i-vj‖，表示ci与cj的类间离散程度，wi表示第i类的类内平均离散程度，vi、vj表示簇ci与cj的质心，∣ci∣表示簇ci中的数据点个数，k表示聚类数。
[0052]
本发明使用了加州大学欧文分校(uci)提供的开放数据集来分析mdst-ap算法的可靠性和复杂性。如表1所示，表示了uci数据集的一些重要特征。
[0053]
表1.uci数据集信息
[0054][0055]
如表2展示了ap算法和mdst-ap算法在四个数据集上聚类的平均准确度f测量值和平均计算时间。整体来说，mdst-ap算法在相对较短的时间内可获得比ap算法更好的聚类结果。mdst-ap算法的平均聚类准确率为85％，平均计算时间为4.31秒。与ap算法相比，mdst-ap算法的聚类精度提高了5.5％。在小体积、结构简单的数据集(如iris和seeds)上，mdst-ap算法的平均运行时间与ap算法的运行时间没有太大差异。然而，随着数据集数量的增加和数据集结构的复杂性，mdst-ap算法的运算速度变得比ap算法快得多。例如，对于wine质量的白色数据集，mdst-ap算法的平均操作时间比ap算法少3.31秒。
[0056]
表2 ap算法与mdst-ap算法聚类结果对比
[0057][0058]
工作原理：数据预处理是指数据选择、地图匹配和归一化。根据实验要求，保留了必要的数据，并删除了错误数据，使用最短距离法将轨迹点与道路网进行匹配。为了确保不同单位或数量级的数据保持可比性，通常需要对数据进行适当的更改。本发明采用了z-score标准化方法，该方法适用于属性的最大值和最小值未知的情况，或有超出取值范围的离群数据的情况。经过上述标准化处理，每个变量的均值为0，标准差为1，原始数据均转换为无量纲化指标测评值，即各指标值都处于同一个数量级别上，进而可以进行综合测评分析。
[0059]
传统聚类方法在对空间实体进行聚类时仅考虑唯一属性或位置属性；而本发明所提出的方法可以同时计算空间属性、时间属性和专题属性之间的相似性。
[0060]
针对ap聚类的线性不可分割问题，本发明使用了高斯核空间。内核技能可以提供从线性特征到非线性特征的连接，并表示两个向量之间的点积。
[0061]
设有一个低维输入空间中的数据集对其实施非线性映射：
[0062]
φ:x
→
f，x∈x
→
φ(x)∈f
[0063]
称上述非线性映射φ为核映射，称空间f为核空间，或特征空间，原始的低维空间x称为样本空间或输入空间。将样本空间中的数据非线性映射到核空间后，需要在核空间中对新的数据进行运算，这主要涉及到核空间中向量的内积运算。核函数把非线性映射和特征空间中向量的内积运算这两步结合起来，将核空间中的运算转化成样本空间中的运算，使得非线性映射隐式地进行。
[0064]
设φ为样本空间x到核空间f的一个核映射，对任意的x,y∈x，核空间中的内积＜φ(x)，φ(y)＞,构成样本空间上的二元函数，为核函数，记为k(x，y)，即
[0065]
k(x，y)＝(φ(x)，φ(y))
[0066]
利用核函数可以提高数据的线性可分性，增强聚类效果，但如何针对具体的问题设计出最适当的核函数却是一个难点。实际上，经常采用的方法是直接给定带参数的核函数族，然后通过实验或其它方法选择合适的核参数。常见核函数通常可以分为两类：局部核和全局核，而局部核根据所选择核参数的不同，又分为大尺度核与小尺度核。对欧氏空间的相似度进行核变换，从而将原来的线性度量转换为非线性度量(即核化的相似性度量)。
[0067]
令x＝{x1,x2,...,xn}为模式空间rn的一个有限数据集，xi(i＝1,2,...,n)是该空间中的一个向量，采用非线性变换φ将输入数据空间x映射到一个高维特征空间h，变换后的高维空间向量为φ(xi)(i＝1,2,...,n)。数据点在特征空间的距离为：
[0068][0069]
输入空间中的点积形式在高维特征空间可以用mercer核来表示，为k(x,y)＝＜φ(x)，φ(y)＞。则上式变成：
[0070][0071]
在聚类分析领域，常用的核函数有线性核函数、多项式核函数、高斯核函数。考虑到线性核函数主要用于线性可分的情况，多项式核度量会改变数据集的自身结构，可能带来错误的聚类划分，而高斯核函数中核度量只是对欧式度量进行一个径向伸缩，不会改变数据间的相对位置，从而不会对数据结构产生影响，所以本发明引入高斯核函数，高斯核函数是径向基函数中最常用的核函数。高斯核函数对应的特征空间是无穷维的，有限的样本在无穷维空间必定线性可分。高斯核函数的公式如下：
[0072][0073]
因此，采用基于高斯核的相似性度量。k(x,x)＝1，所以上式可简化为：
[0074]
[0075]
在实际应用中，不同的数据有不同的量纲，为了使不同单位或量级的数据也能进行比较，通常需要对数据做适当的变换。为了保证数据空间距离与属性距离单位的统一，对各个维度的数据进行标准化，再求各数据间的相关性。
[0076]
本发明使用z-score标准化方法，该方法适用于属性的最大值和最小值未知的情况，或有超出取值范围的离群数据的情况。经过上述标准化处理，每个变量的均值为0，标准差为1，原始数据均转换为无量纲化指标测评值(即各指标值处于同一数量水平)；进而可以进行综合测评分析。
[0077]
设a’(l1,b1,s1,d1,t1)和b’(l2,b2,s2,d2,t2)是两个标准化后的数据点，包含经纬度数据(分别为l和b)、速度属性s、方向属性d和时间属性t(或更多属性)，则两点之间的距离如下：
[0078][0079][0080]
其中||a
’‑
b’||表示标准化后的数据点中空间位置属性与其他非位置属性之间的欧氏距离。
[0081]
ap算法聚类过程是基于数据之间的相似度矩阵进行的，以标准化核空间距离代替原有算法的欧氏距离度量。
[0082]
在传统的ap算法中，将偏向参数p(即前文中的s(i,j))设为相似度的均值或中值，可以得到一个确定的聚类，但不一定是最佳聚类。根据ap算法的原理，当每个数据点的p值相同时，聚类数随p值的增大而增大，所以为得到不同聚类数，在p值的取值区间[p
min
,p
max
]内，获得相等距离的p值(即自适应步长和动态调整p值的聚类方法)。相关等式如下：
[0083][0084][0085][0086]
m是输入参数，表示设置m个不同的p。分析上式可知，当i取1时，pi＝p
min
；当i取m时，pi＝p
max
，故公式的设置是合理的。p影响聚类数目，聚类数目又影响评价指标，即不同的p值具有不同的评价结果，因此，本发明选择davies-bouldin(db)指标来评价聚类结果，根据评价结果再确定最终的p值。
[0087]
本发明采用davies-bouldin(db)指数对聚类结果进行有效性评价。db指数是指一个合理的聚类结果其内部应该是均匀且紧密的，并且簇之间应该有良好的分离，其公式如下：
[0088][0089]
其中c
ij
＝v
i-vj，表示ci与cj的类间离散程度，wi表示第i类的类内平均离散程度，
vi、vj表示簇ci与cj的质心，ci表示簇ci中的数据点个数，k表示聚类数。显然当c
ij
越大，wi、wj越小时，db值越小，此时聚类效果越好。则最小的db值对应的k为最佳聚类。
[0090]
本发明所提出的方法的伪代码如下：
[0091][0092]
本具体实施例仅仅是对本发明的解释，其并不是对本发明的限制，本领域技术人员在阅读完本说明书后可以根据需要对本实施里做出没有创造性贡献的修改，但只要在本发明的权利要求范围内都受到专利法的保护。

技术特征：
1.一种基于时空多维特征的轨迹数据聚类方法，其特征是：所述方法考虑不同维度下的多类属性，提出高斯核变换方法来解决多维属性线性不可分割问题,自适应参数设置方法来解决聚类算法的参数设置问题，具体包括以下4个步骤：s1.数据预处理；s2.相似性矩阵建立；s3.吸引度和归属度计算；s4.聚类有效性评价。2.根据权利要求1所述的一种基于时空多维特征的轨迹数据聚类方法，其特征是：所述数据预处理包含数据选择、地图匹配和归一化，其具体操作如下：保留必要数据，删除错误数据，使用最短距离法将轨迹点与道路网进行匹配。3.根据权利要求1所述的一种基于时空多维特征的轨迹数据聚类方法，其特征是：所述相似性矩阵建立需要考虑多维属性的相似性和高斯核下数据的距离；所述多维属性的相似性包括空间属性、时间属性和专题属性之间的相似性；所述高斯核下数据的距离公式如下：其中对于任意的x，y∈x，x是样本空间。4.根据权利要求1所述的一种基于时空多维特征的轨迹数据聚类方法，其特征是：所述吸引度和归属度计算公式如下：吸引度和归属度计算公式如下：其中偏向参数s(i,j)＝-d
h
(i,j)，即时空数据相似度矩阵中距离的负值，i、j、k为时空数据。吸引度r(i,j)和归属度a(i,j)受s(i,j)的影响。5.根据权利要求1所述的一种基于时空多维特征的轨迹数据聚类方法，其特征是：所述聚类有效性评价依赖于db指数，所述db指数的计算公式如下：其中c
ij
＝‖v
i-v
j
‖，表示c
i
与c
j
的类间离散程度，w
i
表示第i类的类内平均离散程度，v
i
、v
j
表示簇c
i
与c
j
的质心，∣c
i
∣表示簇c
i
中的数据点个数，k表示聚类数。

技术总结
本发明公开了一种基于时空多维特征的轨迹数据聚类方法，涉及数据聚类分析技术领域，其技术方案要点是：所述方法考虑不同维度下的多类属性，提出高斯核变换方法来解决线性不可分割问题,自适应参数设置方法来解决聚类算法的参数设置问题，具体包括数据预处理、相似性矩阵建立、吸引度和归属度计算和聚类有效性评价4个步骤。相较于现有方法而言，可以更快、更有效地处理多维时空数据点。有效地处理多维时空数据点。有效地处理多维时空数据点。


技术研发人员：何贞铭 崔海福 陈华军 马子云 蒋松谕
受保护的技术使用者：长江大学
技术研发日：2023.06.28
技术公布日：2023/10/15