基于方差优化谱聚类的热点区域挖掘算法*

梁卓灵,元昌安,覃 晓

(1.广西大学，广西南宁 530004；2.广西科学院，广西南宁 530007;3.南宁师范大学，广西南宁 530000)

0 引言

近年来，城市的交通拥堵问题日益严重，影响居民的出行以及城市的发展。为改善交通拥堵的情况，可以通过聚类分析的方法对城市居民出行轨迹数据进行挖掘，分析总结居民的出行规律及行为习惯，从而合理地规划城市的公交线路并优化交通资源的配置，为居民推荐合理的出行方式[1,2]。

Ng-Jordan-Weiss (NJW)谱聚类算法是由Ng等[3]提出的，属于经典的多路谱聚类算法。NJW谱聚类算法通过样本数据点的相似矩阵和度矩阵计算求得Laplician矩阵，并由Laplician矩阵的前k个最大特征值对应的特征向量建立一个n*k阶的矩阵。最后把矩阵中的每一行看作是空间中的点，用K-means聚类算法进行聚类。但K-means聚类算法[4]利用簇内点的平均值作为簇的中心点，对孤立点敏感，且其受初始值影响，易陷入局部最优解，不利于对热点区域的聚类挖掘。

轨迹数据是在空间无规则分布的且分布不均匀的数据。K-medoids聚类算法[5]总是选择簇中位置最接近簇中心的对象作为簇的中心点，能消除对孤立点和噪声点的敏感性，比K-means聚类算法更适用于轨迹数据的聚类。但K-medoids聚类算法对初始中心点的选取仍是随机的，而利用方差优化初始中心的K-medoids聚类算法可改善其对中心点的选取，实现对于热点区域的挖掘。

本文把方差优化初始中心的K-medoids聚类算法[6]运用到NJW谱聚类算法的最后聚类阶段，提出基于方差优化谱聚类的热点区域挖掘算法(Hot Region Mining algorithm based on improved K-medoids Spectral Clustering，HRM-KSC)，然后在真实的轨迹数据集上进行试验，证明HRM-KSC算法的聚类效果。

1 K-medoids聚类算法的基本原理

K-medoids聚类算法通常用一个代价函数来评估聚类质量的好坏，以重复迭代的方式寻找到最好的聚簇划分及聚簇中心点。这里使用聚类误差平方和来评估聚类结果质量，定义如下：

(1)

其中，x为各个簇类Ci中的样本，Oj为其聚类中心。

K-medoids聚类算法步骤可描述如下：

Step 1：从数据集中随机选择k个对象，作为初始的聚类中心点；

Step 2：根据与中心点距离的远近，将数据集中的其他非中心点对象分配到最近中心点所在的簇类；

Step 3：重新计算每个簇的中心点位置，使其到该簇其他样本的距离总和最小；

Step 4：重复执行Step 2和Step 3，直到聚类误差平方和基本不变，达到指定要求为止。

一般K-means聚类算法是通过计算簇类点的平均值来选取中心点，其对孤立点敏感，选取的中心点可能不存在。与K-means聚类算法不同，K-medoids聚类算法在迭代选取中心点时，总是在中心点的周围选择样本点作为新的中心点，消除了对孤立点的敏感性。

2 基于方差优化初始中心点的K-medoids聚类算法

方差优化初始中心点的K-medoids聚类算法是对K-medoids聚类算法的改进，称之为Standard-Deviation as radius of neighborhood (SD_K-medoids)算法。该算法利用方差是反映样本分布密集或疏散程度的特性[7]，以方差度量样本分布的密集程度，采用样本标准差为邻域半径，从不同的样本分布密集区域中选择样本作为K-medoids聚类算法的初始聚类中心。

2.1 基本概念描述

设样本数据集为X={xi|xi∈Rp,i=1,2,…,n}，则样本xi和xj间的欧式距离dist(i,j)可定义为

(2)

(3)

方差是各个数据与平均数之差的平方和的平均数，而标准差是方差的算术平方根。因此样本xi的方差Vi和标准差stdi可分别定义如下：

(4)

(5)

其中，N为样本总数。

2.2 SD_K-medoids算法描述

SD_K-medoids算法首先将样本标准化，然后计算数据集中各样本的方差，选择方差最小的样本作为第一个初始聚类中心加入中心点集；然后计算聚类中心的领域半径，从数据集中删除该样本点及该样本领域中的所有数据样本，在剩余数据样本中寻找方差最小的数据样本作为中心点，重复执行，直到选出k个初始中心点。剩余步骤则与K-medoids聚类算法相同：将数据集中的样本分配给与其距离最近的中心点，计算聚类误差平方和，计算新的中心点位置；重复执行，当聚类误差平方和不变，结束算法。

其中，SD_K-medoids算法通过方差反映样本分布的特性，每次可以在最密集的区域选取到中心点，使得初始类簇的划分更贴近数据集的真实分布，降低算法收敛的迭代次数，增加其收敛到全局最优解的概率。

使用样本标准差作为领域半径，每次选取一个中心点后，要把其领域内的样本点去除，从而避免初始中心点可能位于同一簇类的缺陷，使初始中心点尽可能地分布在不同的簇类。

所以，面对轨迹数据无规则分布、分布密度不均匀的特点时，SD_K-medoids算法可以尽快找到好的热点区域初始中心点，加快收敛速度，增加了收敛到全局最优解的可能。

3 基于方差优化谱聚类的热点区域挖掘算法

对于居民出行热点区域的挖掘，就是寻找居民频繁出行的区域，发现居民出行停留时间较长的聚集地点，因此需对居民出行停留点进行聚类操作。在聚类操作之前，本文主要借鉴文献[8]的方法，从移动对象的轨迹数据中提取居民出行停留点，详细方法本文不再具体说明。

针对谱聚类最后聚类阶段K-means聚类算法的不足，用SD_K-medoids算法来替代，提出基于方差优化谱聚类的热点区域挖掘算法(Hot Region Mining algorithm based on improved K-medoids Spectral Clustering，HRM-KSC)。HRM-KSC算法的基本思想是把居民出行停留点看作待聚类的空间样本点，在NJW谱聚类算法[9]中把停留点集映射到相似度矩阵和拉普拉斯矩阵中，并将拉普拉斯矩阵的特征向量构建为特征矩阵，最后改用SD_K-medoids算法对特征矩阵的每行元素进行聚类。

3.1 相似度矩阵的构造

谱聚类把居民出行停留点集看作是一个无向图G(V,E,A)的顶点集合V，由边集E把停留点连接起来，而图中权重集A表示停留点间的相似性。通过权重来构建停留点集的相似度矩阵，停留点间的相似性常用高斯函数wij来计算：

(6)

其中，si和sj分别表示停留点i和j的特征向量，σ为尺度参数。

3.2 拉普拉斯矩阵的构造

本文对停留点集的构建采用的是规范的拉普拉斯矩阵Lsym，其构造公式如下：

(7)

其中，W为相似度矩阵；D为图的度矩阵，其主对角线上的元素为相似度矩阵W的第i行元素之和，计算如下：

(8)

在构建停留点集的相似度矩阵及拉普拉斯矩阵后，将拉普拉斯矩阵前k个特征向量构建为特征矩阵，最后用SD_K-medoids算法对矩阵的每行元素进行聚类。

HRM-KSC算法流程如图1所示,具体过程描述如下：

图1 HRM-KSC算法流程图

Step 1：利用公式(6)计算停留点集的相似度矩阵；

Step 2：利用公式(7)和(8)计算停留点集的拉普拉斯矩阵；

Step 3：把拉普拉斯矩阵前k个特征向量组成的特征矩阵归一化为矩阵Y=[y1,y2,…,yk],把矩阵Y的每一行向量作为一个数据点yi′；

Step 4：把所有数据点yi′(i=1,2,…,k)作为新的样本点，根据式(3)对样本进行标准化。

Step 5：根据式(4)计算数据集中各样本的方差，如Vi表示第i个样本的方差值；其次初始化中心点集M为空，即M={}。

Step 6：从数据集X={x1,x2,…,xn}中寻找方差最小的样本xmin，将其作为第一个类簇的初始聚类中心C1加入到中心点集中，即M=M∪{C1}；根据式(5)计算邻域半径r1，从数据集中删除该样本以及该样本领域中的所有数据样本。

Step 7：重复执行Step 6，直到选出k个初始中心点，即|M|=k。

Step 8：将数据集中的样本分配给与其距离最近的中心点，由公式(1)计算聚类误差平方和。

Step 9：计算每个簇的新中心点位置，使其到该簇其他样本的距离总和最小。

Step 10：重复执行Step 8-Step 9，若聚类误差平方和变化不大，结束算法；否则继续迭代。

4 实验分析

为测试HRM-KSC算法的性能，本文使用微软亚洲研究院的geolife数据集，从2008年8月到10月的轨迹数据中提取出居民出行停留点集。其中，居民停留点的提取参照文献[8]中的方法。本次实验在Win10 64 bit操作系统，8 GB内存，CPU 2.60 GHz的环境下进行，用Python语言实现。

为度量2种算法在实验中的表现，采用SC轮廓系数作为评价指标。SC轮廓系数常用于度量未知类别的聚类数据集，表示聚类结果中各簇类的稠密程度及簇间的离散程度。

SC轮廓系数计算公式如下：

(9)

其中，a(i)表示计算样本i到同簇类其他样本的平均距离，b(i)表示计算样本i到其他样本的平均距离。SC在[-1,1]区间内取值。当SC越接近1时，表示聚类效果越好。

本次实验测试了2种算法在用户停留点集上的聚类效果，在一定区间内选取3种较好的结果，如表1所示。

表1 算法在停留点数据集上聚类结果

观察表1中2种算法在停留点数据集上的表现，发现HRM-KSC算法在选取相同参数的情况下，轮廓系数指标均比NJW谱聚类算法高，表明HRM-KSC算法的聚类结果中同簇类点更紧密，不同簇类点更离散，聚类结果更合理。

为更进一步展示2种算法的聚类结果，采用Python的matplotlib库，以经纬度为坐标画出不同参数条件下的聚类结果(图2—4)。从图中可以看出，在相同参数条件下，HRM-KSC聚类划分结果更合理，尤其在图2和图3中表现更明显，其原因是NJW谱聚类算法在最后阶段所使用的K-means算法，对于初始中心点的选取不够理想，影响了聚簇的划分效果。

图2 k=3,σ=10 时的实验结果

图3 k=4,σ=15 时的实验结果

图4 k=5,σ=20 时的实验结果

5 结论

本文针对NJW谱聚类算法最后阶段的K-means聚类算法对初始点敏感的缺陷，利用SD_K-medoids算法计算样本方差和领域半径，优化对初始中心点的选取，提出基于方差优化谱聚类的热点区域挖掘算法(HRM-KSC)。在居民停留点数据集上进行HRM-KSC算法和NJW谱聚类算法的对比实验，结果表明HRM-KSC算法的聚类质量更高，聚类效果更好。后续期望改善谱聚类算法中高斯函数尺度参数的选取，以及研究如何确定聚类数目，以进一步提高谱聚类算法的聚类质量。