Abstract: To address the problem of fluctuation in clustering accuracy caused by the influence of initial clustering centers in traditional K-means algorithm, a combined clustering algorithm based on improved particle swarm optimization (PSO) was proposed. Firstly, based on the one-dimensional raw data of road operating velocity, two features, including relative velocity ratio (αt) and velocity fluctuation rate (βt), were added to establish a new three-dimensional dataset. Secondly, based on the randomized delayed distributed particle swarm optimization (RODDPSO), an improved RODDPSO algorithm (IRODDPSO algorithm) was proposed, in which a nonlinear constraint function for the maximum particle velocity was introduced. As the number of iterations increased, the maximum update speed of particles gradually decayed nonlinearly. According to the evolutionary characteristic value ξ of each iteration round, different particle update strategies were determined. Finally, the IRODDPSO algorithm was utilized to generate the initialized clustering centers for K-means, and the global search capability of the PSO algorithm was used to find the optimally initialized clustering centers. The research results show that the IRODDPSO algorithm can be successfully applied to clustering analysis of urban road operating conditions. The accuracy and recall rates of the combined algorithm were 0.935 and 0.957, respectively, which were 4.8% and 3.6% higher than that of the RODDPSO algorithm and 13.2% and 11.1% higher than that the benchmark PSO algorithm. The running time consumption of the combined algorithm decreases by 6.7% and 16.3% respectively, compared to the above two algorithms. The proposed maximum speed nonlinear constraint strategy enhances the convergence ability of the algorithm and demonstrates good robust on different levels of roads, including expressways and arterial roads.

Key words: traffic engineering; particle swarm algorithm; K-means clustering algorithm; nonlinear velocity constraint; distributed delay; road state recognition

摘要： 针对传统K均值聚类算法(K-means)受到初始聚类中心影响导致聚类精度波动问题，提出了基于改进粒子群(PSO)的组合聚类算法。在道路运行速度一维原始数据上，增加相对速度比αt、速度波动率βt这2个特征，建立新的三维数据集；在分布式延迟粒子群算法(RODDPSO)基础上，提出改进RODDPSO算法(IRODDPSO算法)，引入了粒子最大速度非线性约束函数，随着迭代次数增加，粒子最大更新速度逐步非线性衰减，根据每轮迭代的进化特征值ξ确定不同的粒子更新策略；利用IRODDPSO算法产生K-means初始化聚类中心，利用PSO算法全局搜索能力，寻找出最优初始化聚类中心。研究结果表明：IRODDPSO算法可成功应用在城市道路运行状态聚类分析中，组合算法的准确率、 召回率分别为0.935、 0.957，较RODDPSO算法分别提升了4.8%、 3.6%，较基准PSO算法提升13.2%、 11.1%，运行时耗分别下降了6.7%、 16.3%；所提出的最大速度非线性约束策略提升了算法收敛能力，并且在快速路、主干路等不同等级道路中表现出良好的稳健性。

关键词: 交通工程；粒子群算法；K均值聚类算法；非线性速度约束；分布式延迟；道路状态识别