基于密度的计算机兵棋推演数据快速聚类算法

摘要

A clustering algorithm named quick density based spatial clustering of applications with noise (QDBSCAN) is proposed for the analysis and application of wargaming data. By detecting the isolated points, the QDBSCAN is used to determine the vulnerability of ground units' deployment rapidly. Compared with density based spatial clustering of applications with noise (DBSCAN) , the QDBSCAN makes some improvements in such aspects- Define the shortest viable path as the similarity measurement to make the clustering algorithm more coincident with the rules of computer wargames, set the density parameters dynamically instead of statically, choose a small number of representative objects to expand the cluster, which reduces the execution frequency of region query; groups the whole dataset by divisiory regions to reduce the scale of clustering. Experimental results indicate that the QDBSCAN is more effective and efficient than the DBSCAN in clustering large datasets.%针对计算机兵棋推演数据的特点,提出了一种基于密度的快速聚类算法一基于密度的快速空间聚类算法(quick density based spatial clustering of applications with noise,QDBSCAN),目的是通过聚类检测孤立点,快速定位地面部队兵力部署上的缺陷.QDBSCAN算法在基于密度的空间聚类算法(density based spatial clustering of applications with noise,DBSCAN)算法的基础上做了相关改进:在邻近度度量上提出了最短可行路径的概念,使聚类更符合计算机兵棋的规则；动态设置密度参数；采用提出的代表对象选择方法来减少对对象邻域的判断次数；按区域对数据进行分组以缩小聚类规模.实验表明,QDBSCAN算法的性能在数据规模较大的情况下,明显优于DBSCAN算法.