Abstract:

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.

Key words: clustering, DBSCAN algorithm, approximate EMD, high-dimensional data