轨迹聚类算法研究：TCMM与NNCluster的探索

### 轨迹聚类算法研究：TCMM与NNCluster的探索 在当今科技飞速发展的时代，定位和传感器技术如GPS和RFID的进步，让我们能够轻松记录移动对象的轨迹信息。这些轨迹数据在各个领域都有着广泛的应用，如推荐有趣的旅行路线、发现具有相似生活经历的用户等。本文将深入探讨两种轨迹聚类算法：TCMM框架和NNCluster算法，分析它们的原理、特点以及实验效果。 #### TCMM框架：增量式轨迹聚类的有效方案 TCMM框架采用两步处理方式来处理增量数据集，旨在实现高效的轨迹聚类。 ##### 1. 轨迹微聚类 - **平行距离计算**：平行距离的计算公式为 \(d^*_{\parallel}(L^*_i, L^*_j) = \max\left\{0, \min(l_{\parallel1}, l_{\parallel2}) - (\text{extent}_i^{\text{length}} + \text{extent}_j^{\text{length}})/2\right\}\)，其中 \(\text{extent}_j^{\text{length}}\) 是 \(\text{extent}_j^{\text{length}}\) 在 \(L^*_i\) 上的投影。需要注意的是，带有范围的两个代表性线段之间定义的距离小于两个原始线段之间定义的距离，当带有范围的代表性线段之间存在重叠时，距离可能为零。 - **合并算法**：给定 \(M\) 个微聚类，计算任意两个微聚类之间的距离，然后将它们从最相似到最不相似进行排序。最相似的对是合并的最佳候选者，因为合并它们导致的信息损失最少。不断合并，直到微聚类的数量满足给定的空间约束。 ##### 2. 轨迹宏聚类 宏聚类是TCMM框架的最后一步，只有在用户调用时才会触发。由于微聚类之间的距离已经定义，因此可以轻松适应任何空间点的聚类方法，只需将空间点之间的距离替换为微聚类之间的距离。在该框架中，使用基于密度的聚类方法，与TRACLUS算法相同，但不同的是，TCMM的宏聚类是在微聚类集合上进行的，而不是像TRACLUS那样在轨迹分区集合上进行。 ##### 3. 实验评估 - **合成数据**：生成合成轨迹数据来快速测试TCMM的“准确性”。对象沿着预定路径移动，有小的扰动（相对预定点的距离小于10%），并添加15%的随机噪声。实验结果表明，提取的微聚类与直观的聚类相匹配。 - **真实动物数据**：使用1995年鹿的运动数据进行实验，该数据集包含32条轨迹，约20,000个点。将TCMM的结果与TRACLUS进行比较，采用平方距离和（SSQ）作为性能度量。实验发现，TCMM的平均SSQ略高于TRACLUS，但处理时间明显更快。例如，处理所有20,000个点，TCMM仅需0.7秒，而TRACLUS需要43秒。 - **真实交通数据**：使用旧金山一家出租车公司的GPS记录数据进行测试，数据集包含7,727条轨迹（100,000个点）。实验结果显示，TCMM和TRACLUS的聚类结果相似，TCMM的平均SSQ仅略高于TRACLUS（最坏情况下高2%，平均高1.4%），但TCMM的处理效率更高，处理所有数据，TRACLUS约需4.6小时，而TCMM仅需约7分钟。 - **参数敏感性**：TCMM的