改进聚类算法在公交数据挖掘中的应用研究

刘 凯，龚兰兰，凌兴宏,2，周家骎

(1.苏州大学文正学院，江苏 苏州 215104；2.苏州大学 计算机科学与技术学院，江苏 苏州 215104)

0 引 言

公交枢纽站是公交线路之间、公共交通与其他客运方式换乘相对集中的场所。有多条公交路线通过公交枢纽站，因此公交枢纽站的效率，关系到整体公交运营的效率以及对于乘客的便利性。而对于公交枢纽站站点位置的确定，除传统的人为规划方式外，文中对公交系统运行的数据进行分析，重新确定公交枢纽站点的方法。通过乘客换乘数据挖掘聚类来确定公交枢纽站更加科学合理。

K-means[1]是聚类算法中最常用的一种算法，该算法最大的特点是简单，运算快速，但是也有两个主要缺陷[2]：类簇数K值需要事先确定，随机选择的初始中心点会严重影响聚类结果。层次聚类算法[3]又称为分级聚类算法，是一种较为常用、实现简单的聚类算法。

文中主要研究使用基于K-means的层次聚类算法[4]确定交通规划中枢纽站点确定的问题，并且提出了使用遗传算法[5]设置基于层次的K-means聚类算法的双类簇数。

1 聚类算法及其评估

1.1 相似度

如何比较数据与数据，数据与簇之间特性的相似性成为了聚类算法的关键问题。对于一种聚类算法，其聚类的结果主要取决于数据间相似度的判断。

用s(x,y)表示数据或簇x与数据或簇y的相似度。当x与y的相似度越高时，s(x,y)的值就越大，而当两者相似度越低时，s(x,y)的值就越小。s(x,y)具有以下特性：

(1)0≤s(x,y)≤1；

(2)s(x,y)=s(y,x)。

通常在聚类算法中，相似度通过数据或类之间的特征空间中的距离来表示，用d(x,y)表示数据或簇x与数据或簇y的相似度，当x与y相似度越高时，d(x,y)就越小；当x与y相似度越低时，d(x,y)就越大。通常聚类算法使用的特征空间中的距离算法有Minkovski距离、余弦距离、皮尔斯相关系数、KL散度。

1.2 评估方式

一般的给出明确标签的数据进行聚类，是可以通过给出的标签与聚类的结果评价聚类好坏，但大多数数据并没有给出明确的标签。因此需要一种可以在原始数据的基础上用来评价不同算法或者算法不同运行方式对聚类结果所产生的影响的评估方式。

常用的聚类结果评价指标分为两种：内部评价指标和外部评价指标。常用内部评价指标有Davies-Bouldin指标、Silhouette指标、Xie-Beni指标，常用外部评价指标有Rand指标、Jaccard系数、ARI指数、Russel-Rao指标。

文中采用了Silhouette[6]这一评价指标，该指标也称作轮廓系数。轮廓系数最早由Peter J.Rousseeuw于1986年提出，是结合了内聚度和分离度两种因素的一种评价指标。

1.3 K-means聚类算法简述

K-means算法[7]是一种无监督的机器学习算法，是基于划分的聚类方法中应用最广泛的算法。该算法具有线性的时间复杂度，且实现简单，因此被广泛应用于各种实际应用问题。

该算法易于理解与实现，同时时间复杂度低，但算法需要手工确定类簇数，对初始值的设置敏感；主要发现圆形或球形的类簇，不能识别非球形的类簇。

算法流程[8]如下：

(1)假设给定的数据集为R；

(2)随机选取K个点作为聚类质心点(cluster centroids)，即u1,u2,…,uk∈R。

重复下面过程直到收敛：

·对于每一个数据计算其到每一个质心点的距离，并将其归入距离最小的类，也就是归入与其特征最相似的类。ci=argmin(‖xi-uj‖2)

·对于每一个类j，重新计算该类的质心。质心的特性等于属于该类的每个数据的平均值，即

1.4 凝聚层次聚类算法简述

凝聚层次聚类算法[9]是一种自上而下的层次聚类算法。首先找到两条最接近的类，将它们合并成一个类，然后，使用剩下的类加上合并好的类，寻找下一对最接近的类。不断重复此过程，直到所有的类都被合并到一个大类或者满足结束条件。因为分级聚类的复杂度很高，通常用在数据点数目不太大的情况下。该算法无需事先确定类簇数；可以发现层次间关系，但算法计算复杂度太高；孤立点对聚类结果影响较大。

算法流程如下：

(1)假设给定的数据集为R；

(2)将数据集R中每个数据作为一个类簇。

重复以下过程直到生成K或者1个类：

对于每一个类，计算其与其他所有类的距离，生成距离矩阵，将距离矩阵中最小距离的两个类合并成一个类并重新计算该类簇的质心。

1.5 基于K-means的凝聚层次聚类算法

根据评估算法的主要思想，聚类结果的好坏取决于聚类的凝聚度和分离度，即同一类中各数据间的相似度与类与类之间的相似度。为了高聚类结果，可以从聚类的凝聚度和分离度两个方面出发对层次聚类算法进行改进。

与基于层次聚类的K均值算法不同的是：基于层次聚类的K均值算法以层次算法为基础[10]，当数据样本中孤立点较多时则聚类效果会变差，产生类簇只包含单个数据的情况，而使用基于K-means算法的层次聚类时，K-means算法对于孤立点进行了一定的处理，再使用层次聚类时，提高了聚类效果，避免了孤立点对聚类结果的影响。

针对本实验该算法消除了孤立点对实验结果的影响，同时区别于单纯的层次聚类算法，会产生多种不同实验结果，有利于公交枢纽站点的确定。

算法主要思想：

首先对于数据进行预估，预设两个适合的K1、K2值且K1>K2(凝聚层次聚类算法的过程中类簇数会不断减少，因此凝聚层次聚类算法的类簇数会少于K-means算法类簇数)，然后对数据使用K-means划分，直到划分出K1个类簇，再使用凝聚层次聚类算法对K1个类簇进行凝聚，直到产生K2个类簇。

算法流程如下：

(1)从数据集R中，选定K1个点作为聚类质心点；

(2)重复下述过程直到收敛：

·对于每一个数据计算其到每一个质心点的距离，并将其归入距离最小的类，也就是归入与其特征最相似的类；

·对于每一个类j，重新计算该类的质心。质心的特性等于属于该类的每个数据的平均值。

(3)计算所有类簇之间的距离，生成距离矩阵；

(4)将距离矩阵中距离最短的两个类簇合并生成新的类簇并重新计算该类簇的质心；

(5)重复4、5直到凝聚到K2个类簇为止。

2 基于遗传算法的改进聚类算法

遗传算法是Holland在20世纪60年代末提出的，是受遗传学中自然选择和遗传机制启发发展起来的一种搜索算法。它的基本思想是模拟生物种群进化的原则，包含了交叉、变异等操作，在不断的种群迭代中，搜索历代种群中的最优个体即为最优解。

2.1 聚类效果评价指标确定

轮廓系数[11]是评估聚类效果好坏的一种方式，其结合了聚类的凝聚度和分离度。该值处于-1～1之间，该值越大，表示聚类的效果越好，该值越小，表示聚类效果越差。

具体计算方法如下：

(1)对于每一个数据i，计算其与所在类簇中其余数据间的特征空间距离的平均值，用于度量类簇内的凝聚度，记为a(i)；

(2)遍历每一个非i所在的类簇，计算i与该类簇中所有数据的特征空间距离的平均值，记作b(i)，用于度量类簇间的分离度；

(3)对于样本点i，轮廓系数为：

(4)计算所有i的轮廓系数，求出平均值即为当前聚类的整体轮廓系数，度量数据聚类的紧密程度。

2.2 算法基本流程

(1)随机产生一个由确定长度的特征串组成的初始种群；

(2)对种群中的每一个个体采用改进的聚类算法进行聚类并将聚类结果的轮廓系数作为适应值；

(3)对初始种群进行交叉操作、变异操作、复制操作；

对学生与数据分析观念相关的调查研究主要是从三个方面进行研究：一是就某一些统计概念的理解展开调查，如曲元海对初中生统计量理解的调查研究[12].二是单独对学生的数据分析观念进行调查，如李红梅对七年级学生数据分析观念的现状调查[4].三是在调查数学核心素养中包含数据分析，如张淑梅对高中数学核心素养统计分析过程中发现，数学建模与数据分析的相关性较大[13].

(4)在所有操作结束后判断是否满足迭代终止的条件。

·若满足，则终止迭代并将所求的最优解作为遗传算法的执行结果并输出，这个结果就是对应问题的最优解或者近似解；

·若不满足，则终止条件并对当前的种群进行步骤2中的操作。

2.3 编码预处理以及编码

编码是遗传算法要解决的首要问题。编码方法有很多[12]，如二进制编码、实数编码、符号编码等等。针对文中的问题，最适合的编码方式为二进制编码。

通过初步的实验，发现优秀个体的两个K值(K1、K2)具有一定合适的比率大小关系。因此每个个体有两条染色体，一条K1值染色体，一条比率染色体，K2的值由K1和比率所确定。

2.4 适应值计算以及评估

遗传算法中，适应值决定个体遗传的概率[13]。在文中适应值越小，则个体遗传概率越大，适应值越大，则个体遗传概率越小。

2.5 选择算子

针对本问题，选择了轮盘赌选择[14]从而避免了使用确定性选择产生的样本单一问题。

轮盘赌选择的基本思想是：各个体被选中的概率与其适应度大小成正比。具体操作方法如下：

(1)计算出种群中每个个体的适应度f(Ci)。I取值范围为1～n,n为种群大小。

(2)计算出每个个体被遗传到下一代群体中的概率。

(3)计算出每个个体的累计概率。

(4)在[0,1]区间之间产生一个伪随机数r。

(5)若r

(6)重复步骤4到步骤5共n次。

2.6 交叉算子

交叉运算指的是将两个染色体按某种规则提取相应的部分然后按某种方式进行交叉互换，从而产生两个新的个体。交叉运算时遗传算法区别于其他进化算法的重要特征，其设计包括两个方面[15]:①如何确定交叉基因的位置；②如何对交叉部分的基因进行互换。

该算法采用的是双点交叉。双点交叉的思想：从两组染色体的开头到相同的位置i提取这一段基因进行互换，再从相同的位置j到染色体结束的位置提取这一段基因进行互换。交叉后发现会产生K值超过数据集最大个数或者比率超过额定范围的情形，对此则重新选择个体进行交叉。

2.7 变异算子

变异算子是对染色体的某些基因做改动从而产生一串新的染色体，作用是维持种群的多样性，避免算法过早收敛甚至无法得到全局最优解。交叉运算的设计包括两个方面：①如何确定变异基因的位置；②如何对所需变异基因值进行替换。

在此所采用的是倒位变异，即在一串染色体中随机选取两个位i,j,将从第i位到第j位的染色体反转从而实现变异效果。对于变异后产生K值大于数据集个数或者比率大于额定范围的情形，则重新选取个体变异。

2.8 遗传算法优化

针对过早收敛问题，根据遗传算法的模式定理，适应度更高的个体有更多复制的机会，因此，在种群还没有达到最优解时便有可能由某一当前最优解过早占领了种群的统治地位从而得到了局部的最优解，但在后续种群的迭代过程中，无法最终收敛到全局最优解。这个现象就称为过早收敛。文中采用了迁移思想，在算法中设置一个变量times记录当前最优解在后面的代数中保持统治地位的次数，当次数达到一定的时候，保留当前适应度大于平均适应度的样本，删除其余样本重新组合成种群，然后继续算法。采用迁移的想法，从一定程度上避免了过早收敛这一现象，在迭代次数足够多时能够稳定地求出问题的最优解。

过慢结束是指在样本迭代到一定次数之后，整个种群已经大部分收敛了，但还是无法稳定收敛到全局最优解，最优解的适应度与样本平均适应度差别不大，导致了无法筛选出较好的算子进行复制操作。针对过慢结束问题，在复制算子中增加了一个函数用于判定是否出现了样本的适应度最优值与平均值相差不大的情形，若相差小于平均适应度的10%，则执行放大函数，用来临时放大种群中各个样本的适应值与平均值之间的差距，从而能更好地选择出样本进行复制操作。

3 实验分析

文中数据来自于苏州市吴中区公交数据。实验目的是确定所有公交站点中的枢纽站点。

对实验数据进行预处理之后，一共包含1 124个数据对象，每个数据对象包含了单个属性。采用上文提及的凝聚层次聚类和K-means聚类结合改进后的聚类算法。

K-means算法与改进后的聚类算法的实验结果见表1。遗传算法确定K值的实验结果见表2。

表1 K-means算法与改进算法

表1中K值由均方根方法确定。从表1可以看出改进后的算法比较改进之前，以轮廓系数作为评价依据有了较明显的提升。

表2 遗传算法设计K值

从表2可以看出使用遗传算法设置改进聚类算法的K值，以轮廓系数为依据，可行度较高。

通过文中的研究可以得出以下结论：

(1)在枢纽站点确定的问题中，将K-means算法与凝聚层次聚类算法相结合，其聚类效果相比于单一算法有了很好的提升。

(2)使用遗传算法来设置K值，达到了较优解的效果，种群中的最优个体的轮廓系数与采用均方根的效果差距较小。

(3)与目前已经规划的公交枢纽站点相比，本实验结果又通过对数据的分析，列出了潜在的公交枢纽站点，同时对于各个公交站点流量进行了分析，为公交枢纽站点的二次规划提供了有效的数据支持。

4 结束语

针对城市交通规划中枢纽站点确定的问题，提出了使用改进的基于K-means的凝聚层次聚类算法对公交数据进行处理；同时为得到更优的聚类结果，有别于传统确定类簇数K的方法，使用遗传算法确定K-means算法与层次聚类算法结合时的类簇数以及两个类簇数之间的关系。通过实验表明，使用改进的聚类算法确定枢纽站点为公交枢纽站点二次规划提供了可靠的数据支持，并且使用遗传算法改进的聚类算法的聚类效果有了较好的提升。