上述两种方法皆可得到描述轨迹的序列。对于我们的公共子序列聚类来说，我们使用 GeoHash 得到轨迹序列能够得到较高的效率（花费时间基本为保留高位小数法的 60%）。此外需要注意的就是：1.该聚类方法并不关心轨迹点的先后顺序，也就是时间无关性；2.产生的轨迹序列会有重复值，但我们只关心轨迹是否在某一空间，而不关心在某一空间出现的次数，也就是重复无用性。基于以上两点，初步产生的轨迹序列需要去重，这对于查找公共子序列来说也是一种效率优化。
这对于 c#来说是极其简单的:
//并行迭代轨迹获得轨迹序列 Parallel.ForEach(tracks, t => { // t.GeoCodes = GeoHelper.GetGeoCodes(t.GeoPoints, 3).ToList();//保留高位小数法 t.GeoCodes = t.GeoPoints .Select(tt => GeoHash.Encode(tt.Latitude, tt.Longitude, 7)) .Distinct() .ToList();//GeoHash法 }); 轨迹相似度的计算在得到每条轨迹的序列基础上，我们可以进行轨迹的相似度计算。而轨迹相似度可以归结为轨迹序列间的公共子序列占原始序列的比率。
//array为轨迹列表，ibf为索引1，jaf为索引2，计算GeoCodes的交集 var intersect = array[ibf].GeoCodes.Intersect(array[jaf].GeoCodes).ToList(); //公共子序列的个数转为浮点型，避免下一步计算为整形时结果直接归零 var intersectCount = (float) intersect.Count; //公共轨迹（子序列）的与轨迹1的相似度 var rateIbf = intersectCount / array[ibf].GeoCodes.Count; //公共轨迹（子序列）的与轨迹2的相似度 var rateJaf = intersectCount / array[jaf].GeoCodes.Count; 轨迹族谱的生成得到轨迹相似度后，我们定义了两个阈值：一个为兄弟姐妹相似度scaleSimilar，一个为后代相似度scaleBlood。注意，兄弟姐妹相似度总是比后代相似度的值要大。根据这两个阈值，我们可以进行轨迹族谱的生成。如果相似度rateIbf和rateJaf都大于scaleSimilar，说明两条轨迹极为相似，被定义为兄弟姐妹。如果都大于scaleBlood，并且rateIbf大于rateJaf，则轨迹 2 是 1 的后代，反之 1 是 2 的后代。
以下是这个算法的核心：
//构建轨迹树（族谱） public IEnumerable<Trajectory> BuildClusterTree(IEnumerable<Trajectory> trajectories, float scaleSimilar = 0.8f, float scaleBlood = 0.6f) { var array = trajectories.OrderByDescending(t => t.GeoCodes.Count).ToArray(); for (var ibf = 0; ibf < array.Length; ibf++) { Parallel.For(ibf + 1, array.Length, jaf => { if (array[jaf].Level == 1) return; var intersect = array[ibf].GeoCodes.Intersect(array[jaf].GeoCodes).ToList(); var intersectCount = (float) intersect.Count; var rateIbf = intersectCount / array[ibf].GeoCodes.Count; var rateJaf = intersectCount / array[jaf].GeoCodes.Count; if (rateIbf >= scaleSimilar && rateJaf >= scaleSimilar) { array[jaf].Level = 1; array[ibf].Siblings.Add(array[jaf]); array[jaf].Siblings.Add(array[ibf]); } else if (rateJaf > rateIbf && rateIbf >= scaleBlood) { array[jaf].Level = 1; array[jaf].Parent = array[ibf]; array[ibf].Children.Add(array[jaf]); } else if (rateIbf > rateJaf && rateJaf >= scaleBlood) { array[ibf].Level = 1; array[ibf].Parent = array[jaf]; array[jaf].Children.Add(array[ibf]); } }); } var root = array.Where(t => t.Level == 0 ).ToList(); SetClusterTreeLevelInfo(root); return root; } //设置代数及标签信息 private void SetClusterTreeLevelInfo(IEnumerable<Trajectory> tree,int level = 0, string levelTag = "") { Parallel.For(0, tree.Count(), i => { var node = tree.ElementAt(i); node.Level = level; node.LevelTag = $"{levelTag}{i}"; for (var j = 0; j < node.Siblings.Count; j++) { var sib = node.Siblings.ElementAt(j); sib.Level = level; sib.LevelTag = $"{node.LevelTag}__{j}_sim"; } SetClusterTreeLevelInfo(node.Children, level + 1, $"{node.LevelTag}_"); }); } 结果展示及说明我们直接上最终的轨迹族谱图的展示
读者放大后应该能够看清图片的文件名，文件名是代数标签。以“3.png”和“3_0.png”来说，“3.png”是“3_0.png”的父亲。对应的，后者是前者的孩子（所有轨迹对于都是自适应固定大小的图片画的，所以缩放比例和整体偏移会导致看起来有差别。读者仔细观察能够发现 3_0 只是 3 的左下角一部分）。而对于“3_0_4_8.png”和“3_0_4_8__sim_0.png”来说则互为兄弟姐妹（缩略图与自适应的确影响了结果的查看）。
此外，我们能够看出第 3 和第 6 是两个大家族。如果利用所有轨迹的数据生成热力图，那么 3 族和 6 族所经过的地方热力值相对来说要高很多。把一个大家族的所有成员轨迹叠加后可以得到我们想要的热迹。
总结