基于占空比的聚类算法评价指标研究

张欣环，刘宏杰，吴金洪，施俊庆，毛程远，孟国连

1.浙江师范大学道路与交通工程研究中心，浙江 金华 321004

2.西安交通大学电子信息工程学院，西安 710049

轨迹挖掘是指以出行者长期的活动轨迹为基础，将其活动轨迹点聚类成一个个合适的区域。城市公共交通系统中，出行者的轨迹数据的挖掘是构建定制公交网络的关键技术之一，也是公交站点选址优化的基础。目前，公交线路及站点的设置大多以运营成本最低为目标，较少考虑出行者的距离和时间成本。

本文提出一种改进的密度聚类算法（DBSCAN）及其对应的有效性评价指标，挖掘出行者活动轨迹：根据出行者的起、终点识别结果，优化站点设置以减少出行者的步行距离，提升出行体验，提高服务可靠性，节约出行成本，并为智慧城市构建定制公交网络提供数据支撑。

根据改进的DBSCAN 算法、全新的轨迹聚类结果的有效性指标来实现DBSCAN 输入参数的自动选择。该指标平衡了聚内凝聚度、聚类间距和聚类内密度，计算出密度聚类模型的最优输入参数值，从而避免了人为设定参数的局限性。比对仿真数据和延安市公共交通出行数据后，可以看出该有效性评价指标在基于密度的地理位置信息聚类中优于传统的评价指标。

1 文献综述

轨迹聚类是轨迹模式挖掘的一种，轨迹聚类的目标是寻找不同运动对象共有的代表性路径或共同趋势[1]。许多文献都采用了不同的方法来实现轨迹挖掘的目标。Cheng 等[2]将轨迹划分为子轨迹段，然后应用基于密度的聚类算法对子轨迹进行聚类，挖掘出热点。Wang[3]提出了一种基于网格的移动轨迹挖掘算法，首先基于网格划分数据，然后使用DBSCAN 对每个网格进行聚类。由于集群的数量是FCM 集群所需的输入，所以Choong 等[4]指定了三个数字作为参数。但是，以上方法只对轨迹数据进行切片或网格化，然后将聚类算法应用到实际的轨迹聚类场景中。由于聚类算法本身没有改进，所以聚类参数不够精确，不能达到最优结果。

DBSCAN 由于其简单性和检测不同大小、形状的集群的能力，在许多科学领域得到了广泛的应用。由于传统的DBSCAN算法在选择聚类参数时严重依赖于用户的手工经验，如果用户没有足够的实践经验来确定适当的参数值，那么输入参数的取值不当可能会影响聚类结果的质量。为了克服这一缺陷，一方面，一些研究人员将两种方法结合起来确定参数，Sharma等[5]结合K-近邻算法和DBSCAN实现无参数聚类技术，Hou等[6]混合Dsets（优势集）与DBSCAN 自动查找取值，但是这些方法需要至少两次处理数据，复杂的步骤不适合大规模的数据。另一方面，改进聚类算法的有效性指标，也可以有效地选择聚类参数，提高聚类效果。Duun index（邓恩指数）[7]、DBI（Davies-Bouldin index）指数[8]和轮廓（Silhouette）系数[9]是评价无标记聚类算法的三个基本指标。Zhou 等[10]设计了一个新的聚类有效性指标，称为紧-分离比例（compact-separate proportion，CSP）指数，以评估AHC 算法产生的聚类结果，并确定最优的聚类数目。Karo 等[11]提出了一种利用多边形不相似度函数（polygon dissimilarity function，PDF）对Davies Bouldin指数进行修正的空间区域聚类有效性指标。Acharya等[12]在四种已知的聚类效度指标的定义中引入了一种新的基于线对称的距离效度指标。Thomas等[13]用圆柱距离代替了欧几里德距离，该距离尝试捕获沿连接均值线段的数据密度，以估计聚类均值之间的距离。江玉铃等[14]为挖掘AIS数据中有关船舶运动规律有效的、潜在的信息，利用类似DBSCAN算法对轨迹段进行聚类，得出船舶运动典型轨迹。周培培等[15]针对现有的异常轨迹检测算法往往侧重于检测轨迹的空域异常，忽略了对轨迹时域异常的检测，并且检测精确度不高等问题，提出了基于增强聚类的异常轨迹检测算法。然而，现有的有效性指标一般都是针对二维人工数据集，只关注聚内凝聚度、聚类间距，而忽略了聚类内密度。这意味着这些方法的聚类结果可能会变成长条聚类，这在现实生活中是不合理的。针对这些指标的缺陷，有必要对DBSCAN 及其有效性指标同时进行改进，以正确找出出行者位置信息数据集的最优聚类数。

2 研究方法

2.1 无参数的DBSCAN算法

DBSCAN 的应用程序需要两个重要参数：给定点在邻域内成为核心对象的最小邻域点数MinPts，邻域半径Eps。然而在选择这两个聚类参数时，DBSCAN算法依赖于用户的实践经验。本节使用改进的DBSCAN聚类算法对数据进行聚类，可以自动确定输入参数。

本文提出的改进DBSCAN 算法中，将聚类过程产生的聚类结果作为评价函数的输入参数，然后得到评价结果，具体表达如下：

算法改进的DBSCAN聚类算法

（1）输入参数

D是当前输入数据集。D1(x1,y1)表示集合中平面坐标的x和y。

MaxEps 是两个平面坐标点之间的最大距离，可以根据实际意义灵活确定。

MinEps 是两个平面坐标点之间的最小距离，可以根据实际意义灵活确定。

E表示集合中任意两点之间的距离，取值范围为MinEps和MaxEps之间。

MaxNum设置了聚类阈值的上限，因为如果聚类的数量太大，数据集可能无法形成有效的聚类。

MinNum 设置集群阈值的下限。如果聚类的数量太少，可能会导致聚类太多，甚至一个点变成一个类，没有最终计算结果。

M确定了某个集群的最优数量阈值，其值范围在MaxNum和MinNum之间。

（2）输出参数

ResultC是聚类结果，使用不同的输入参数可以得到不同的聚类结果。

MinIedci是最小占空比，最初设置为无穷大。

BestEps是E的最佳值，最初设置为0。

BestMinPts是M的最佳值，初始值为0。

不同的输入参数会产生不同的聚类结果。为了防止丢失某些参数，该算法给出了输入参数的范围，遍历该范围内的所有参数值，然后生成聚类结果。通过对聚类结果的评价和计算，可以得到最优的评价值，并基于反向传播法计算出最优的输入参数。算法流程如下：

（1）构建输入参数范围

在不同的应用场景中，最佳的聚类输入参数值在一定范围内波动。由于输入参数的范围决定了算法执行的效率和找到最优值的可能性，因此在算法执行之前建立一个合适的输入参数范围就显得尤为重要。聚类次数过多，数据集可能无法形成有效的聚类；聚类次数过少，聚类过于分散，不实用。此外，聚类点之间的距离会影响聚类内的紧度。如果距离度量太大，聚类太离散，无法有效区分不同的聚类。如果距离度量太小，则聚类距离太近，可能会产生太多琐碎、无价值的聚类结果。因此，在聚类的前期，首先要确定Eps 和MinPts 的最大值和最小值，从而构建聚类参数的有效范围。

（2）生成聚类结果

以步骤1的邻域半径范围为输入参数，进行循环密度聚类，完成所有出行者6 个月内轨迹点的聚类计算，并保存各聚类结果（resultC）。

（3）评价聚类结果

利用轮廓系数、DBI 指数以及本文提出的内外占空比指数IEDCI（internal and external duty cycle index）等评价指标对各聚类结果进行评价，并将最佳聚类参数BestEps和BestMinPts保存到评价指标中。

（4）获得最优聚类结果

以步骤（3）中的BestEps 和BestMinPts 为输入参数，计算最佳聚类结果。本文的聚类结果是出行者实际活动轨迹的聚类，是后续研究中出行者所有可能出行的起、终点。

2.2 基于占空比的聚类评价指标

通常，选择聚类评价指标来评价聚类结果的质量，也称为聚类有效性分析。一个好的集群划分应具有以下特点：不同集群中的样本尽可能地不同，同一集群中的样本尽可能地相似。

通过对出行者历史轨迹的研究，发现影响聚类结果的因素不仅包括聚类的内聚程度和聚类之间的边界距离，还包括聚类中轨迹点的数量。传统的评价指标由于只考虑了聚类的内聚程度和聚类间距等系数，在轨迹聚类方面存在一定的局限性。在进行聚类凝聚度评价时，没有考虑聚类内密度，忽略了聚类内部个数与聚类大小的关系。在不规则聚类中，单个变量的影响程度往往过大，聚类结果往往停留在边界点上，无法实现参数的最优选择。

针对现有的评价指标不适合基于密度的地理位置信息聚类问题，本文提出了一种基于聚类内外占空比的有效性指标IEDCI。内外占空比公式如下：

根据公式（1），内外占空比涉及三个区域（如图1所示）：si、sj和si+j，其中si、sj为第i、j类中最外层点围成的区域，si+j表示两个类合并后最外层点围成的区域。利用占空比平衡聚类内距离和聚类间距离的关系，解决单点成类或所有点成类的不适当情况。面积是一个二维的标准，可以用来评估两个类的离散程度，从而有效地避免两个类中某些点可能存在的线性极值距离。

图1 占空比系数示意图Fig.1 Duty cycle coefficient diagram

在定义了内外部占空比的概念后，提出了基于内外部占空比的评价指标IEDCI，公式如下：

为寻找最优的输入参数和最优聚类结果，本文提出了一种基于聚类点和聚类占空比的有效性评价指标，用于评估不同输入参数所产生的聚类结果，并根据之前的反馈确定当前的最佳输入参数。

轮廓系数和DBI 在处理聚类结果时只考虑聚内凝聚度、聚类间距的关系，没有充分考虑单个聚类结果中聚类点对整体聚类效果的影响。因此，本文提出的聚类评价优于上述评价函数。

3 案例验证

3.1 数据集

3.1.1 仿真数据集

仿真数据集为计算机模拟生成的随机数。每个数据集有1 200 个点，每个点都以坐标的形式表示并划分为一个簇。这些数据集是清晰簇、模糊簇、晕簇和非簇（如图2 所示），在这些数据集中，清晰簇和模糊簇的结构是凸的，晕簇的结构是环形的，而非簇的结构是飞溅的。

图2 二维合成数据集Fig.2 2-D synthetic data sets

3.1.2 案例数据集

本文使用的案例数据来自Yi Bus 手机APP。Yi Bus是一款手机APP，可以查询附近的车站、线路换乘、实时到达预测等交通信息。在本文中，使用了延安市近6个月（2020年1月至2020年6月）的500名用户的位置信息数据。一共获得了500 个.txt 格式的文件，每个文件代表每位出行者在这6 个月的所有位置信息。每位出行者的轨迹数据由轨迹点x坐标和y坐标表示，此外，由于数据集代表的是真实的出行者的轨迹点，因此与计算机生成的仿真数据集相比，数据的结构是多种多样的，包括线性、环形、凸形和飞溅形。案例数据集的数据结构如表1 所示，其中UID 为用户SIM 卡的唯一标识，LNG 为当前用户位置的经度，LAT为当前用户位置的维数，UP_TIME为坐标上传时间。

表1 延安市公交出行数据结构Table 1 Data structure of bus trip in Yan’an city

由于APP 采集的数据存在损坏数据、重复数据、无效数据等情况，需要对这些数据进行预处理。本文主要采用以下两种方法对数据进行预处理。

（1）数据清洗：本文对数据的预处理主要是删除不相关的数据和重复的数据，对有噪声的数据进行平滑处理。

（2）数据ETL（extract-transform-load）：以用户唯一识别编码，从数据实例中抽取用户的所有行为轨迹，构建一个用户的单体数据集，循环遍历所有用户，最终形成多个用户的单体数据集，作为整个聚类集合的候选集。从候选集合中抽取若干候选人作为实验对象，确保单一用户轨迹数据大于1 000，构建聚类集合。

3.2 参数选择对比

在出行者轨迹挖掘中，Eps 是出行者的行走距离，MinPts是出行者在一定区域停留的次数，两者都有实际意义。因此，可以根据实际意义来划定参数范围。通过对现有数据的统计，可以得出出行者的行走半径大部分在20 m 到110 m 之间，因此，本文实验中将Eps 阈值设定在（20，110）以内，所有后续的实验测试都是基于此范围的。

聚类太少点或太多点都没有实际意义，因为聚类坐标阈值太小可能是一个噪声点，很难找到阈值较大的聚类。因此，在本文的实验中，MinPts的阈值设置在（8，13）以内，后续的实验测试是基于此范围的。

为了验证改进的DBSCAN算法自动选择的参数性能，本文使用了案例数据集并生成聚类结果，并与其他参数进行比较，包括经验值和统计值。

对所有输入参数的结果进行统计，找出最常见的聚类数（如图3 所示）。图3 统计此时的输入参数，取当前输入参数的中位数（60，12）作为统计输入参数（Eps值为60，MinPts 值为12）。经验值获得的Eps 和MinPts 值分别为85 和10；改良DBSCAN 得到的Eps 和MinPts 分别为65和12。

图3 聚类结果的频率Fig.3 Frequency of clustering results

案例数据集共有500 个个体的定位点信息。使用紧度、分离度和DBI来评价聚类结果。紧度和DBI代表类的内聚度，分离度代表类之间的距离，紧度和DBI 值越小，分离值越高，聚类效果越好。从表2可以看出，本文提出的方法自动生成的参数在分离度和DBI 上取得了更好的聚类效果，与传统的经验值相比，该方法的性能有了很大的提高。

表2 不同性能参数实验结果Table 2 Experimental results of different performance parameters

3.3 评价指标对比

为了验证IEDCI 的性能，本文分别使用仿真数据集、案例数据集来生成聚类结果，并将其与其他有效性指标进行比较，包括DBI和轮廓系数评价。

3.3.1 仿真数据集

本文使用紧度和分离来评估四个仿真数据集的聚类结果。表3为三个评价指标的紧度评价结果，从结果可以看出，IEDCI 对数据集清晰簇、模糊簇和非簇的评价值更好。表4为三个评价指标的分离度评价结果，从结果可以看出，IEDCI对于清晰簇和非簇的数据集有更好的评价值。

表3 不同评价指标的紧度评价结果Table 3 Compactness results of diffenent evaluation indexes

表4 不同评价指标的分离度评价结果Table 4 Separation results of diffenent evaluation indexes

3.3.2 案例数据集

本小节使用案例数据集来评估算法的性能，整个评估过程如下。

（1）最优输入选择：利用轮廓系数、DBI和IEDCI这三个评价指标来执行前文的改进DBSCAN算法。遍历参数范围内所有可能的值后，算法可以得到三个评价函数对应的最优输入参数，如表5所示。

表5 最佳MinPts和Eps值Table 5 Best value of MinPts and Eps

（2）聚类结果：使用三个评价指标的最优输入值生成三个不同的聚类结果。从图4中可以看出，对于相同范围内的聚类点，由轮廓系数评价指标产生的结果将红色椭圆内的离散点聚集成一个类。然而，从出行者轨迹的实际情况来看，由于出行者活动过多，聚类结果较差。在DBI 聚类结果中，将红色椭圆分为两部分。同理，图中A点到B点的距离在图4（b）中远远超出了人们活动的范围（500 m）。在本文算法的聚类结果中，出行者活动的范围小于居民轨迹的半径。因此，该算法在实际应用中表现良好。

图4 不同性能指标的聚类结果Fig.4 Clustering results of different validity indexes

（3）聚类评价：对生成的聚类结果进行紧度和分离度评价，评价结果如表6所示。在充分考虑聚类密度和聚类间距影响的基础上，本文提出的方法得到的结果具有更高的分离性和更小的紧致性，这更符合轨迹聚类中人们活动的实际情况。

表6 分离度和紧度评价结果Table 6 Evaluation results of compactness and separation

4 结论

本文提出了一种全新的出行者轨迹挖掘方法：使用一种全新的评价指标对DBSCAN 的输入参数进行评价，该评价指标平衡了聚类内距离和聚类间距离，从而获得了出行者位置信息聚类的最优输入参数，避免了人工经验导致的参数不准确的问题。其次，基于延安市城市公交出行数据，对本文提出的方法进行了验证，实验表明，本文提出的算法能够在弹道数据集上找到最优的输入参数值。通过对聚类结果的紧实度和分离度的计算，并与DBI 和轮廓系数相比，IEDCI 找到的最优参数值具有较小的内聚值和较大的聚类间距值。因此，本文提出的算法在挖掘出行者轨迹方面具有良好的性能。

本文提出的方法不仅可以用于出行者位置信息的聚类（以获取出行起终点），还可以推广到物流与供应链管理、汽车动态路由、加油站规划等路由问题。因为所有这些问题都是二维地图上的点聚类问题，而与其他集群不同的是，由于人或车辆有一定的运动范围，集群的大小受到限制。

本研究未来的改进包括以下两个方面：首先，可将用户的SIM卡定位信息添加到实验数据中，以丰富数据多样性，APP的使用频率直接决定了当前集群的集群密度；其次，可将计算步长引入到计算过程中，以提高整体计算效率。