一种基于近似EMD的DBSCAN改进算法

DBSCAN(density based spatial clustering of applications with noise)算法是基于密度的经典聚类算法,但是该算法应用于高维数据时,常用距离函数不能很好地反映出数据点之间的关系, 从而可能导致聚类簇不够精确。如果能在高维空间中采用合适的距离度量,将会改善聚类结果。针对上述问题,提出利用近似EMD(earth mover’s distance,堆土机距离)作为距离测度,通过迭代搜索的方法找出所有直接密度可达对象实现聚类。实验结果表明:在高维文本数据的聚类中,和原来算法相比,改进算法的正确率提高了6％,两者在时间上相差不大;而对低维的Iris数据,改进算法通过EMD改善了实体间的相似性度量,减少了划分为噪声点的数据点个数,平均正确率提高了10％。实验结果表明了改进算法对高维数据的有效性,并可以改善聚类性能。

An improved DBSCAN algorithm based on the approximate EMD

The DBSCAN algorithm is one of the classic clustering algorithms based on the density.When this algorithm was applied to high-dimensional data,the distance measures in common use could not reflect the relationships between instances well,which would lead to the inaccurate clustering.If appropriate distance measures were adopted in high-dimensional space,the clustering result would be improved.To solve the above problem,the approximate EMD(earth mover′s distance) instead of the common distance was used as the distance measure,and the clustering was achieved by finding all density-reachable objects with the method of iterative search.The experimental results showed that the performance of improved algorithm was 6% higher than that of the original algorithm for the high-dimensional text clustering,while there is no obvious difference in time cost.For low-dimensional Iris data,the proposed algorithm could improve the similarity measure between the instances,reduce the number of data points classified as noise points,and boot the performance with 10%.The experimental results also indicated that the proposed algorithm could reveal its effectiveness for high-dimensional data,and could improve the clustering performance.