2017/10/30更新，回答以下问题（均用红色标出），并完整的写出聚类过程：
1、轨迹聚合如何使用距离函数？
2、聚合如何分类？类别需要预先定义么？
3、如果一条路径，不同部分聚合在不同类中，如何处理？
（一）在具体的聚类前，我们需要先定义几个概念如下：
1>
：Li是一个line segment，N-eps(Li)表示Li的eps邻域，也即找出所有和Li的距离dist(Li,Lj)<eps的Lj集合。
（此处就用到了dist的概念，回答了问题1，dist的定义如下：
）
2>core line segment：表示如果N-eps(Li)>Min-Lins，也即Li得eps邻域包含的line segment数目若大于Min-Lins，则Li可以称之为一个core line segment，也即中心线段。
3>directly density-reachable：如果对Lj来说Li是directly density-reachable的，那么表示Li是在Lj的eps邻域里，并且Lj的eps邻域里包含的segment数目大于Min-Lins（说明什么？说明Lj一定是一个core line segment）（注意，directly density-reachable并不是对称的，即Li和Lj不一定满足交换律）
4>density-reachable：如果对Lj来说Li是density-reachable的，那么必定存在一个directly density-reachable的链，使得经过这些链的作用，可以把这种reachable传递下去（仍然说明Lj必须是一个core line segment）。（注意，density-reachable仍然不是对称的）
5>density-connected：如果Li和Lj是density-connected的，则说明必然存在一个Lk使得对Lk来说，Li和Lj都是density-reachable的。（是对称的）
6>density-connected set：如果一个非空集合C称为density-connected set则表示C满足下列条件。<1>对于任意Li,Lj，他们都是彼此density-connected的。<2>对于任意Li,Lj，如果Li属于C集合，并且对Li来说Lj是density-reachable的，那么必存在Lj也属于C集合。
（二）除上述基本定义外，我们还需定义一个概念，那就是trajectory cardinality：由于在cluster前，我们已经将segment进行了partition操作，所以聚类出来的cluster里面很可能有许多segment属于同一个trajectory，但是这样的聚类是毫无意义的，所以我们将定义一个trajectory cardinality概念，控制一个cluster的segment至少要来自于x条trajectory。
（三）下面开始cluster过程：（回答问题2:聚类过程如下，聚类不需要事先定义，是在算法执行过程中不断产生的。）
1>最初的时候，所有的segment都被指定为“未分类状态”，随着分类的进行，他们被分类成一个cluster或者一个noise。
2>第一步：先计算segment的eps邻域，如果某一个segment被指定为一个core line segment的话（也就是邻域的segment个数大于Min-Lins），那么程序就会标记其为cluster-x，并且执行第二步过程，通过这个segment扩展成cluster，如果不是core line segment的话，则标记为噪声。
3>第二步：由于要从core line segment，假设为Li，扩展成cluster，所以最初这个cluster内部segment的个数一定是这个Li的eps邻域大小。紧接着，算法计算Li的density-connected set，如果新加入的segment没有被标记，则除了标记其为cluster-x外还需要把它压入队列Q（为什么呢？因为这个segment还可能继续扩展，我们需要不断从Q中拿出segment进行分析，从而达到不断扩展cluster的目的，做到不重复不漏下），如果新加入的segment是一个noise，那么我们就不需要再压入队列Q（为什么呢？因为一个noise是不可能扩展成cluster的）。
4>第三步：算法需要检查所有cluster的trajectory cardinality，若trajectory cardinality小于某一threshold，那么就把这个cluster剔除。
回答问题3:一条路径，不同部分聚合在不同类中是很正常的现象，因为一条路径的首尾已经距离很远了，基本不可能聚合在一起。我们的目的不是将一条路径聚合在一起，而是寻找不同的trajectory在某一位置处的共同行为，再将这些cluster的representative trajectory描绘出来，通过representative trajectory在图形上的走向来观察大多数用户的行为轨迹。也就是说，我们正是需要不同部分聚合在不同类中，所以才能将多个不同轨迹的共同特性找出来。如果仍然按照整个一条轨迹来进行聚合，就像下文中Gaffney等人提出的观点一样，可能就找不出彼此的相似性了。
一些想法：本篇文章的重点在于从固定的，并不关心时序的trajectory中寻找出一个representative trajectory，很适用于飓风，动物迁徙等行为的分析，因为在这些分析中，我们并不关心飓风到达某处的时间（no time），我们只关心它更可能到达某处（only position）。而我们所做的全景视频传输问题比较关心时序和位置（both time and position），即我们需要知道在某个时刻，用户更可能在哪里。我们在分析全景视频的trajectory过程中最大的难题在于，我们的trajectory并不像文章中的数据集一样，基本上都是一条曲线，从某处来，到某处走，而是有可能在某处一直徘徊一直画圈，如果还按照这个做法的话我们就很难分析在这样的位置处用户停留了多久，因为在一张二维图上暂时还不能表示出时间维的信息，具体如何改进还需要仔细思考一下。
=========================================================================
学术界现存许多典型的聚类方法，如kmeans, BIRCH, DBSCAN, OPTICS 和STING等等，但是这些方法都是针对“点”的聚类，针对“轨迹的”聚类方法较少。Gaffney等人曾提出一种model-based轨迹聚类方法，利用最大似然来寻找轨迹之间（基本聚类单位是整条轨迹而不是离散的“点”）的相似性。然而，作者发现这种利用整条轨迹进行建模的方法对于寻找轨迹部分之间的相似性无能为力。比如两条很复杂并且很长的轨迹，即使某一阶段／部分十分相似，但是于整体而言，这种相似性看起来十分微弱（如下图所示）。
作者由此提出了一种名为partition-and-group的解决方案。顾名思义，算法需要先将trajectory分成line segments，然后再将相似的segment进行group，最终实现目标。不过，作者为什么要进行轨迹拆分呢？原因在于很多情况下， 尤其是当我们拥有roi位置时，我们更关心在roi处各个trajectory是否彼此有相似性，而不是观察整体的相似性。（比如观察飓风在某个位置处的轨迹，动物在某个位置处的迁徙行为）
此时也许又出现了新的问题，既然我们有了roi，为什么不将原有的轨迹删除一部分，只留下roi覆盖的部分，再利用传统方法进行聚类呢？作者提到，这种方式存在着两个缺点。1>我们很难决定哪些部分是useless的 2>去掉useless的部分使我们很难发现一些潜在的或者说出乎人们意料的聚类结果。
本篇文章的contribution：1>提出partition-and-group framework。 2>使用MDL原则对trajectory进行分割。 3>提出一种有效的density-based聚类算法。 4>经过对真实数据的建模，作者证实他们的算法可以有效的寻找出representative trajectories。（文章行文结构完全按照这四个contribution来进行，逻辑十分清楚）
在具体讲述算法前，作者首先定义距离函数如下：
（一）轨迹分割（trajectory partitioning）
在本篇文章中，作者提出了一个名为characteristic points的概念，这个point指的是轨迹剧烈变化的点，所以轨迹可以根据这个点进行分割。如下图。
一个好的partitioning策略需要同时满足preciseness and conciseness，然而这两者总是相互矛盾的，所以需要寻找一个tradeoff来实现最优。本文作者采用了MDL即最小描述长度来描述partition的效果。如下（L(H)代表conciseness L(D|H)代表preciseness）：
然而，用这种方式来寻找最优解是非常复杂的，因为我们需要考虑到一条轨迹的所有点才可以。由此，作者提出了一种估计解：以局部最优代表全局最优。具体过程：我们知道，若i,j是这条trajectory唯一的一对characteristic points，那么MDL（par） = L(H)+L(D|H)，若不是唯一的一对，路上都是characteristic points，那么L(D|H) = 0，MDL（nopar） = L(H)。所以我们可以采用一个近似最优的解法，即判断MDL（par）与MDL（nopar）的大小，若MDL（par）> MDL（nopar），则说明在当前点之前应插入一个characteristic points，否则不插入。虽然这种近似并不完美，但是已经可以实现80%的准确性了。
（二）轨迹聚合
由于有些line segment本身很短，所以造成角度距离很小，可能会出现在聚合时本不应该聚合在一起的segment由于这些短segment的存在而被聚合，为了解决这一问题，作者提出为MDL（nopar）在计算时增加一个小的偏置量，以牺牲preciseness为代价避免过度聚合
LineSegmentClustering聚合：整个聚合过程可以分为三步 1>寻找初始line segment，即L。2>以L为中心进行扩展，寻找density-reachable的segment，并标记至未找到集合为空。3>计算每个cluster的基数，排除掉不合格的cluster。这种聚合方式也很容易进行推广，根据我们的权重寻找每一个line segment的线邻域。
Representative Trajectory代表轨迹的选择:如图所示，MinLns = 3。首先在每一个segment开始和结束的位置处绘制一条垂直线（如图中虚线），从1处开始寻找代表轨迹，每一段的开始点都是计算出的average coordinate，每一段的方向都是average direction vector，如果在两条垂直线中间的segment数小于MinLns则直接横跨过去，否则重新计算，若距离前一个拐点过近也直接横跨不考虑。
（三）实验分析（TRACLUS算法分析）
实验数据包括两个trajectory：the hurricane track data set（named Best Track， has 570 trajectories and 17736 points） and the animal movement data set（including Elk1993 and Deer1995，Elk1993 has 33 trajectories and 47204 points; Deer1995 has 32 trajectories and 20065 points）
实验发现：经过与真实最优值进行对比，本篇文章的结果与真实的最优情况十分接近。
注：本篇文章是由Jae-Gil Lee, Jia-wei Han等UIUC的学生发表在ACM SIGMOD会议上的。