层次聚类算法须要一个类间最大年夜距离阈值来断定两个聚类是否归并。在断定聚类Cx和Cy是否归并时，应用基于共享近邻(shared nearest neighbor，SNN)的个数的办法计算SNN(Cx,Cy)[。与第3.2节提出的轨迹间距离计算办法不合，SNN(Cx,Cy)只用于断定两个聚类是否归并。改进的凝集层次聚类算法步调如下。

算法1 凝集轨迹聚类算法。

输入：指准时光段的轨迹数据集T={Ti|1≤i≤n}，计算距离时邻近轨迹的个数k。

输出：聚类结不雅C={Cm|1<m<<n}。

步调1 为T的所有肇端地位O和所有停止地位D分别建立k-d树,并获得每条轨迹的kNN邻近轨迹。

步调2 按照第3.2节计算距离的办法计算每条轨迹和它的kNN邻近轨迹之间的距离,并根据距离升序分列。

步调3 将每一条轨迹初始化为一个聚类。

步调4 对按距离排序过后的每一个轨迹和它的邻近轨迹(p,q)。起首找到p和q分别地点的聚类Cx、Cy，然后计算Cx和Cy之间的距离,如不雅x≠y，并且SNN(Cx,Cy)<1，则Cx=Cx∪Cy，C=C-Cy。

在计算两个聚类Cx和Cy之间的距离时，按照平均连接(average-linkage)算法聚类法，应当计算Cx和Cy的轨迹之间的平均距离，然则如许十分耗时。是以，应用近似然则效力高的办法计算聚类Cx和Cy之间的距离，计算过程如图8所示，计算步调如下。

算法2 类间距离计算算法。

输入：聚类Cx和聚类Cy。

步调1 分别计算聚类Cx和Cy的肇端地位的质心Ocx和Ocy以及停止地位的质心Dcx和Dcy。

步调2 大年夜肇端地位集O中找到最接近Ocx和Ocy的点Ocx’和Ocy’，大年夜停止地位集D中找到最接近Dcx和Dcy的点Dcx’和Dcy’。

步调4 应用SNN(Ccx’,Ccy’)计算轨迹<Ocx’，Dcx’>和<Ocy’，Dcy’>之间的距离，用来近似表示聚类Cx和Cy之间的距离。

3.4 轨迹可视化

经由过程上述轨迹聚类算法对用户给准时光段下的手机用户轨迹进行聚类，获得了一组聚类结不雅。每个类用中心轨迹来代替该类，应用流向图的办法将每个类的代表轨迹画在地图中，如图9所示，显示至少包含70条轨迹以上的类。个中，原始数据为上海电信手机用户在顾村公园和欢快谷两个区域某天全天的24 278条轨迹数据，如图9(a)所示。设置k=150，应用聚类算法聚成了2 917个类，最大年夜的类包含了355条轨迹。个中90%以上的轨迹可以至少找到一条邻近轨迹，每个轨迹平均有7条邻近轨迹。有1 321条轨迹无法找到任何邻近轨迹，会本身形成一个类，在轨迹可视化时会去除这些零丁的类。

本文设计了一种多地图缩放级其余层次可视化办法，根据地图的缩放级别，显示不合聚类大年夜小的轨迹。本地图缩放级别较小时，只显示包含轨迹数量较大年夜的类，如图9(b)所示。当扩大年夜地图缩放级别时，增长显示其他包含轨迹数量较小的类，如图9(c)所示，该图表示的区域与图9(b)方框所示区域雷同。个中，色彩越深的线表示包含轨迹数量越多的类;反之，色彩越浅的线表示包含轨迹数量越少的类。

步调3 生成两个中心轨迹<Ocx’，Dcx’>和<Ocy’，Dcy’>表示聚类Cx和Cy。

图9 轨迹聚类结不雅可视化

应用热力争的办法表示用户选择的时光段的停止时刻的手机用户分布情况，如图10所示，图10为14:00—14:05用户的移动轨迹和用户在14:05时地点地位的热力争。热力争可以显示大年夜范围个别的┞符体状况，色彩越深表示数量越大年夜。

图10 热力争

3.5 参数选择与算法比较

在轨迹聚类时，若参数k设置过小，结不雅会产生很多很小的类;反之若k设置过大年夜，结不雅则会产生较大年夜的类，并且计算量也会异常大年夜。给定一个合适的类簇指标，只要假设的类簇的数量等于或者高于真实的类簇的数量时，该指标上升会很迟缓，而一旦试图获得少于真实数量标类簇时，该指标会急剧上升。本文类簇指标选择类簇的轨迹数量加权平均值，图11表示选择不合k值对应的类簇的轨迹数量加权平均值。可以看到，当k值取150阁下时，类簇指标的上升趋势开端加快，经由过程蚁群优化算法可以主动获得最优k值。

图12(a)为k=100的聚类结不雅，图12(b)为k=200的聚类结不雅，k=150的结不雅在图9(c)中。比较这3张地图可以发明，尽管最大年夜的类包含的轨迹数量不合、显示的聚类结不雅有些细微的不合，然则总体的模式是类似的。结不雅注解k值的设定对聚类结不雅的影响和整体的分析不是十分敏感，当须要看整体的流动情况时，用户可以选择较大年夜的k;当须要看局部区域的流动情况时，用户可以选择较小的k。

图12 不合k 值的聚类结不雅

为了验证改进算法的效力，本文分别应用传统的凝集层次聚类算法(agglomerative nesting，AGNES)、应用代表点的层次聚类算法(clustering using representatives，CURE)[19]以及本文改进的凝集层次聚类算法对不合条数的轨迹进行聚类，结不雅见表1和图13。实验结不雅注解，当轨迹数量较少时，AGNES聚类算法效力比较高，CURE和本文改进的聚类算法效力相对较低;当轨迹数量较多时，CURE聚类算法的效力略好于AGNES聚类算法，但比拟之下本文改进的聚类算法效力最高，并且运行时光呈线性增长。

　　推荐阅读

　　Windows 7系统mac地址修改攻略

谈起mac地址我想大年夜多半人都比较清跋扈，一旦我们设置了它就能在局域网防止别人盗用你的ip，不过如不雅mac地址被别人知道了就得修改一下，很多用户不知道Win7怎么改mac地址?其拭魅这个>>>详细阅读

本文标题：手机基站定位数据可视分析

地址：http://www.17bianji.com/lsqh/34598.html

 1/2    1