要解决的问题

大多数的聚类算法只把整体作为轨迹的相似度，而忽略了子轨迹之间的相似度。文章提出了TRACLUS聚类方法。

而豪斯多夫距离是应用在TRACLUS聚类方法中的相似性度量方法。

TRACLUS方法主要分为两部分：partitioning and grougping。

首先使用minimum description length（MDL）准则，进行partitioning 算法。

然后，使用基于密度的线段聚类方法。

豪斯多夫距离简介

豪斯多夫距离本来是模式识别中的一种相似性度量的方法。

设X和Y是度量空间M的两个紧子集。那么豪斯多夫距离dH(X,Y)是最小的数r使得X的闭r—邻域包含Y，Y的闭r—邻域也包含X。**

image.png

以此图为例，dH(X, Y)，就是对于X上的每一个点，到Y集合都会有一个最小的距离。对于X上的所有点对应的所有轨迹中的最大值，就是最小的数r使得X的闭r一邻域包含Y，Y的闭r一邻域也包含X的数值r。

显然，原本的豪斯多夫方法是不考虑时间因素的，整个“集合”是一个抽象的概念。当它直接应用于时空轨迹的相似性度量的时候，效果显然并不会很好。

因此，想要让豪斯多夫距离更加适合时空数据挖掘，必须进行改进。

改进豪斯多夫距离简介

豪斯多夫距离方法在线段聚类中使用，此方法主要由三部分组成：①垂直距离，②平行距离，③角距离。该方法分别从平行距离，垂直距离和角距离3个方面对轨迹段之间的距离进行计算。

image.png

如上图所示，si,ei表示线段Li，sj,ej表示线段Lj。

垂直距离定义如下：

image.png

分别指Lj的两个端点到另一条线段的垂直距离。

平行距离定义如下：

image.png
分别指Lj的两个端点在Li上对应的垂点与最临近的端点之间的距离。而

是取两者的最小值。

角距离定义如下：

image.png

，是Lj、Li之间夹角的小角。||Lj||指的是Lj的长度。（不是元素的个数，是这条线段的长度）

需要注意的是，这里是线段，不是直线。而且是有向的。（因此

）

三个定义中需要用到的ps、pe、e可以通过简单的几何关系得到：

image.png

即当已知四个点的时候，可以完全地把三个距离计算出来。

其实这三个d，都是豪斯多夫距离。实在垂直方向、平行方向、旋转方向上的三种豪斯多夫距离。对着三种距离线性叠加，得到的距离将会同时反映两条（线段）轨迹的位置、方向关系。

因此，TRACLUS中，改进豪斯多夫距离的定义为：

豪斯多夫距离的使用——TRACLUS方法简介

显然，豪斯多夫方法有点特殊：他把一条完整的轨迹全部划分成了一条一条的线段。划分线段的准则是，行为轨迹有着大幅度的变化。例如：

image.png

轨迹被划分之后就再也没有复原，TRACLUS方法是用来聚类的，目的是加强对子轨迹的关注。其最终聚类（使用的基于密度的线段聚类）结果也是一个个线段。而后对于每一个cluster，都计算一个代表性的轨迹。

当豪斯多夫聚类被用于预测：

预测的前提是每一个cluster足够精细，有足够具有代表性的线段。且豪斯多夫距离对于噪声点、离群点的支持并不好：没有噪声点抑制手段，对噪声非常敏感。对于local time shifting 的支持也不算好。虽然最终匹配的时候可以根据查询轨迹来减少或者增加（因为代表轨迹一般足够理想，所以此处一般是减少）参考轨迹（理想轨迹）的坐标点，但是毫无疑问会丢失很多的信息（相当于把不匹配的点直接略过去了）。

显然，豪斯多夫方法可以被用于聚类，但是需要先抑制噪声点。且豪斯多夫方法不适合被用来做预测的相似度匹配。

优缺点

Hausdorff方法把轨迹划分成了一个个的小线段，足够精细。

但是由于其本身的划分思想（找改变最大的地方），就造成了它对噪声非常敏感。

显然，豪斯多夫方法可以被用于聚类，但是需要先抑制噪声点。且豪斯多夫方法不适合被用来做预测的相似度匹配**。