Traclus轨迹聚类算法

参考链接

MDL原则包括两个部分：

如图所示：

输入：轨迹 TR_i = p_1p_2p_3...p_{len_i}

输出： CP_i 集合代表轨迹的特征点

算法：

  我们近似划分轨迹的关键思想是将局部最优集合视为全局最优。当假设 p_i 和 p_j 仅是特征点时，令 MDL_{par}(p_i,p_j) 表示 p_i 和 p_j(i <j) 之间的轨迹的MDL成本( = L(H) + L(D|H) )。当假设在 p_i 和 p_j 之间没有特征点时，即当保留原始轨迹时，令 MDL_{nopar}(p_i,p_j) 表示MDL成本。我们注意到 MDL_{nopar}(p_i,p_j) 中的 L(D|H) 为零。然后，局部最优是最长轨迹分区 p_ip_j ，其满足每k的 MDL_{par}(p_i,p_k)≤MDL_{nopar}(p_i,p_k) ,使得 i <k ≤ j 。如果前者小于后者，我们知道选择 p_k 作为特征点会使MDL成本小于不选择它。此外，为了简洁起见，我们尽可能地增加该轨迹分区的长度。我们为轨迹中的每个点计算 MDL_{par} 和 MDL_{nopar} （第5~6行）。如果 MDL_{par} 大于 MDL_{nopar} ，我们将前一个点 p_{currIndex-1} 插入到特征点的集合 CP_i 中（第8行）。然后，我们从那一点开始重复相同的过程（第9行）。否则，我们增加候选轨迹分区的长度（第11行）。

基于密度的聚类算法，思想同DBSCAN算法：

输入：1. 线段集合： D = {L_1,L_2,...,L_{num_{l_n}}}

   2. 两个参数 \epsilon 和 MinLns

算法：

  基于密度分为多个簇，然而对于一个簇中所有轨迹的走向及其它特征并没有直观简洁地展示出来，因此有必要提取簇中的整体信息并用可视化的手段展示出来方便进一步分析。

  一种可行的方法是计算簇中的平均轨迹，用平均轨迹来代表整个簇中轨迹的整体信息。原文中将这条轨迹形象地称为“代表性轨迹(Representative Trajectory)”。

  用一条垂直于簇中线段的平均走向的直线扫描各条线段，每次经过一条线段的起点或终点时都要判断一下此时相交线段的个数是否不小于MinLns。若是，则计算一个所有交点的平均点并存储于列表中，否则不予理会。最终生成的列表即为平均轨迹的结点坐标信息。

  这里忽略了一个问题，簇中线段的平均走向如何计算？

  原文中是将簇中所有的线段用向量表示，向量的长度为线段的长度，将所有向量相加并单位化即可代表簇中线段的平均走向。

  除此之处，由于算法要反复计算扫描直线与簇中线段的交点，如果扫描直线与x轴所成角度不为90度的整数倍，则计算量稍大。因此算法对此进行了预处理，将坐标系旋转使X轴与平均走向平行，这样计算起来就方便许多。

输入：1. 一个 C_i 簇

   2. MinLns

   3.一个光滑的参数 \gamma

输出： C_i 簇的代表性轨迹 PTR_i

算法：

以下案例中国地图为例，如果想使地图显示为白色，可以按照图2进行 *** 作。

第一行：输入年份和月份，一次只能输入一个月份，注意要安照图片中的类似格式21 08 （表示2021年08月)；

第二行：若只计算一个高度的轨迹，可以取消勾选Multi_locations选项，在空白格中输入需要计算的经纬度和高度。若要计算多个高度或多个位置，则需要勾选Multi_locations，在locations中输入研究地点的经纬度及高度，案例为新乡，最后一个数字为气团的高度，一般为500m到1000m。

第三行：Run Hours 为研究气团的后向时间，向后追溯2天则为（-48）

第四行：Starting Hours(HH HH ……)为研究气团的一天中的几个时刻，来模拟一天之中的气团总变化。对于数据量较小的数据可将24个小时从00 01 02 03……到24，全部表示出来；数据量较大时，可选择00 06 12 18这四个时刻，这四个一般是实际观察的数据，其他时刻有时为在此基础上计算得到。

第五行：Add Meteorological Files 添加轨迹数据。GDAS数据是按周存储的，后向轨迹需要前几天的数据，因此记得在选择数据要选择上个月最后一个星期的数据。

Duration为从每个月的第几天到第几天的周期，研究一月为单位时可以选择1到31

第六行：Execute File 为后向轨迹聚类的处理程序

第七行：Output Path 为输出路径，可以自己选择，这里选择桌面。

最后得到：（1）每天所选择的四个时刻的轨迹数据（2）根据这个四个时刻合并的tgs数据（3）整个月份的tgs数据

右键打开属性表可以查看轨迹属性

可选择聚类方法Distance: EUCLIDEAN/ANGLE,欧拉距离聚类或角度距离聚类，这里选择欧拉距离聚类。点击calculate,并查看TSV变化曲线，当曲线增长变化幅度最高时，该点对应的聚类个数即为聚类分析的最佳聚类曲线数，这里选择4条曲线，并设置cluster number 为5。

点击Mean Traj 平均聚类生成文件，命名为jlx；并点击Add to traj 将聚类的结果添加到合并后轨迹的属性表内。

关闭2021.08的trajectory文件，可见聚类后的轨迹已经显示在图上面了

双击Cluster文件夹下jl1.shp,文件曲线，点击Legend——选择UniqueValue和Ratio,并对线性颜色，粗细进行设计。

点击标注，添加聚类后轨迹比例，字段选择Ratio比例

将地图切换至版面，调整地图位置，点击插入添加指北针，比例尺，图例

点击导出图片图标，得到导出的图片

---