【《基于K-Means的航迹聚类算法分析案例》4100字】

基于K-Means的航迹聚类算法分析案例1.1基础算法航迹聚类[14]就是将所有航迹划分成不同簇的过程，使得同一簇中的航迹彼此相似，但与其他簇中的航迹彼此相异。为得到更好的聚类分析效果，选择合适的聚类分析算法尤其关键，目前主流的聚类算法模型有K-Means聚类分许算法、DBSCAN聚类分析算法、层次聚类和Mean-Shift聚类分析算法等。（1）K-Means聚类算法K-Means算法是一种经典的基于划分的聚类分析算法[15][16]，K-Means算法的核心思想是：首先设置参数k值，k代表需要把一个数据集划分成k个类，随机地依次指定其中k个对象作为初始聚类的中心，再使用相似性度量将样本数据划分到不同初始聚类中心，相似性度量一般采用欧氏距离，由此将数据集划分为k个数据分布。重新计算划分好的聚类分布的中心点，并作为新的聚类中心，聚类中心也可以不是数据集中存在的数据对象，只代表划分类的中心位置，如果计算前后的聚类中心发生了偏移，则需要对所有数据对象重新进行划分，不断重复上述步骤，直至聚类中心位置不在发生移动，或者迭代次数达到最大迭代次数，聚类结束。K-Means算法就是通过迭代更新数据分布，达到降低类间误差平方和的目的，当SSE稳定时，标志着聚类过程结束，得到聚类结果。空间中数据地对象和聚类中心点之间的欧式距离计算公式表示为：（2.1）其中，x为数据对象，为第i个聚类中心，m为数据对象的维度，，为x和的第j个属性值。整个数据集的误差平方和SSE计算公式为：（2.2）其中，SSE的大小分别代表聚类分析结果的性能优劣和质量好坏，k为类的个数。K-Means聚类分析算法主要特征是通过不断的对各个划分类及其中心点进行迭代替代地过程，该聚类分析算法具有简单、高效并且保证数据集收敛速度快等特征。K-Means聚类算法的具体计算步骤是先设定目标数据集需要被划分类的个数k的值，从数据集X中任选k个对象作为X的初始聚类中心，初始聚类中心为，根据数据对象与k个初始数据中心的距离对X中所有数据进行划分，将X中每一个数据对象划分到与其距离最小的聚类中心形成一个类，当所有数据都被划分后，就将数据集划分成k个类。然后分别对每一个类进行计算，找到类内的距离中心点，计算结果即为下一次划分的聚类中心点，计算类中心点的公式为：（2.3）最后重复上述的步骤，直到重新计算后的聚类中心点相同于计算前的聚类中心，没有发生任何变化，则说明聚类结果已经达到收敛；根据K-Means算法的基本步骤流程，K-Means聚类分析算法的基本流程图如下所示：图2.1K-Means算法流程图（2）其他聚类算法DBSCAN聚类算法：DBSCAN聚类分析算法是采用了典型的基于密度的动态聚类分析算法[17]，能够将一些具有较高密度的区域分割组合形成簇，由于是基于密度的聚类分析算法，所以可以受噪声数据的影响也较小。对于一个样本点m，如果m的邻域内的数据点数大于（领域密度阈值），则认为样本点m在高密度区域，反之在低密度区域。DBSCAN算法中几个重要关键名词的解释：邻域：以目点为中心，为半径的一个球体空间，参数；：领域的密度阈值，当邻域内，认为一些数据对象在同一个簇中的最小值；m是核心对象：m的邻域内有至少个数据对象；直接密度可达：两个数据对象再彼此的邻域内；m从n密度可达：存在，使得，，且对于，从直接密度可达；和密度相连：存在，使得和都从n密度可达。DBSCAN算法伪代码如下所示：算法2.1DBSCAN算法输入：包含n个对象的数据集，邻域半径，邻域密度阈值输出：基于密度的簇的集合1标记所有对象为未访问；2do3任意选择一个未访问的对象m，标记m为已访问；4ifm的邻域内至少有个对象5创建一个新簇C，并把m添加到C；令N为m的邻域中对象集合；6forN中每个点7if未访问8标记为已访问9if的邻域至少有个点，把这些点添加到N；10if不属于任何簇，把添加到C；11endfor输出C；12else标记m为噪声；13until没有标记为未访问的对象层次聚类：通过进行层次簇的聚合分类对一个簇中给定的数据对象按照一定的层次聚类顺序对其进行聚合分解，直到簇的个数达到一个规定的簇数或者分解成最小单位为止，聚类策略包括自底向上和自顶向下两种，自底向上的层次聚类策略首先是将目标数据集中的所有数据对象都独立的看作为簇，这些簇处于层次聚类的最底层，通过对簇合并条件的判定，不断把底层的簇进行聚合，形成新的簇，直到簇的个数达到规定的数值或者数据集中的所有数据对象都在同一个簇中为止[18]；而自顶向下的策略恰恰相反，首先是将整个数据集视为一个簇，然后再逐渐进行细分而形成越来越小的簇，直到簇的个数达到规定的数值或者数据集中的每个数据对象都独立的为一个簇时，聚类终止。以自底向上策略为例，先是将数据集中的每个数据点都视作独立的簇的聚类中心，形成一个的数据集D的聚类集合，通过计算的每个聚类对的相似度，的计算公式为：（2.4）其中：（2.5）（2.6）（2.7）选取相似度最大的聚类对聚合成一个新的聚类，从而更新数据集D的聚类集合为。自底向上策略的层次聚类算法伪代码如下所示：算法2.2层次聚类算法输入：数据集，终止条件簇的个数k输出：聚类集合C1将中每一个对象形成簇；2do3while当前簇的个数；4forD中的每个点a5forD中的每个点b6计算（a，b）的相似度M（a，b）7find相似度最小的聚类对8合并相似度最小的聚类对9until或10printCMean-Shift聚类算法：Mean-Shift算法是基于密度的非参数聚类算法[19]。在进行参数密度的估计中，如果将目标的概率密度信息反馈并映射至与其对应的概率密度空间后，目标的概率密度值即可服从己知函数模型的概率密度的分布，那么就可以直接通过采样的方法来计算得出目标在概率密度空间中的概率密度。但是，在实践中，往往无法准确地得知概率密度函数的具体表达形式，因此对参数估计的应用便受到了限制。无参估计与参数估计之间最大地差异就在于我们无法准确地获知概率密度函数的具体表达式时，仍然能够直接利用该样本来计算得出概率密度。常用的无参估计方法之一就是核密度估计法，而Mean-Shift算法恰恰是一种较为新颖的核密度估计法，也常常被广泛应用于对目标追踪。Mean-Shift聚类的算法步骤是先指定一个点的向量，基本形式是：（2.8）是偏移向量，会指向数据样本点相对点x变化最多（最大）的方向，即梯度方向，也就是数据样本密度最大的方向。随着x向方向不断移动，当成为零向量时，认为样本点位于数据局部密度最大的区域，并且移动到相同局部密度最大区域的点被认为是同一个簇的成员。1.2算法设计2.2.1节中介绍的几种常用的聚类算法都有不同的优缺点和适用范围，具体如下：K-Means聚类分析算法具有简单、快速的特点，该聚类算法再处理大规模数据时往往表现出相对较高的可伸缩性和较好的效率，它的计算复杂度是，其中参数n所表示所有目标数据对象的数目，k表示簇的聚类目标数目，t表示迭代计算的次数。通常使k<<n。此种算法往往以一个局部最优解完成。算法试图通过找到使平方误差函数值最小的k个划分，当数据分布时密集的或者团状时，该算法的聚类效果很好。但该聚类算法对于k值的选择具有敏感性，k值的选择会较大程度上直接影响最终聚类的结果，当聚类数据集规模较大时也就无法直接确定将其具体分成几类才能使得聚类效果是最好的，除此之外，该算法还需要针对离群点和噪声点敏感进行处理，如果数据集中存在离群点，K-Means聚类算法就很容易单独将这些离群点划分为一类，从而影响最终的聚类效果，由于初始聚类中心的选择具有随机性，故使用K-Means算法有落入局部最优解的可能。DBSCAN是可以自适应的聚类方法，该算法无需事先设定k值大小，可以较好的判断离群点，并且判错离群点对聚类结果也几乎没有影响，同时该算法只需要定义邻域的大小和密度阈值就可以发现任意形状，任意大小的簇，聚类结果稳定，不受初始聚类中心影响。但该聚类分析算法的聚类结果主要取决于邻域空间半径和邻域的密度阈值两个参数的设定，当数据集的密度稀疏程度不同时，聚类的优化效果也明显的不同，即当数据集的密度不均匀时，很难发挥该算法的效果，聚类时间也随数据集样本的增大而增加。层次聚类算法其原理比较简单，容易被人们所理解，其聚类结果也比较稳定，但是合并点或者分裂点区不容易被选择，不适用于大数据集，此外，算法的目标簇数目和阈值不好确定。Mean-Shift聚类算法的主要优点是可以不必再自行设置簇的数目，容易作为一个模块被其他算法集成，该算法只需要确定带宽这唯一的参数就可以发现数据集中任意形状的簇，算法简单，计算量小，输出结果稳定。但是，Mean-Shift算法的聚类效果过于依赖带宽的取值，带宽值设置过小会导致结果类结果过多，聚类特征不明显；带宽值设置过大会导致数据特征的丢失。表2.1几种聚类算法比较聚类算法类型空间复杂度时间复杂度聚类形状备注K-Means划分球形、团状对噪声点敏感DBSCAN密度任意形状数据密度不均匀时不适用层次聚类层次任意形状不适合大数据集Mean-Shift密度任意形状计算量大舰船航迹数据是高度非线性的时序数据，具有数据规模大、复杂度高的特点，结合上述各聚类算法的优缺点，最终选择使用K-Means聚类算法。2.1.1节已经介绍过传统K-Means聚类算法原理，它根据事先设定的k值，生成k个初始聚类中心，以欧式距离为相似性度量不断调整聚类中心的位置，最终形成k个类。而AIS数据作为典型的时间序列数据，每一条航迹都由若干个位置坐标、时间和属性组成，采用动态时间归整（DynamicTimeWarping，DTW）算法[20]作为AIS数据的相似性度量，它主要是基于一种动态规划的理念，可以有效地解决时间序列速度不一致的问题。如图2.2所示，假设两条航迹为和，长度分别为m和n，航迹中的每一个航迹点用三元组表示，该算法的思想是使用迭代的方法求出任意两条航迹的匹配路径，使得结构化距离最小，可表示为：（2.9）其中：，表示除第一个点之后的。图2.2子航迹段匹配在确定了航迹间的相似性度量后，按照K-Means算法进行航迹聚类分析，首先设置k值，将航迹数据，随机选择k个初始航迹聚类的中心，然后根据DTW算法计算剩下的所有航迹对象至每一个初始聚类中心之间的距离，将已经计算好的航迹数据对象划分到距离最近的初始航迹中心形成类，这样就