Abstract:

Padma Mundur et.al proposed a clustering algorithm based on Delaunay triangulation, and applied it to the clustering of multidimensional characteristics data of video frames to generate the video summarization, which got good results. However, because of too much calculation, the efficiency of the algorithm is not high. In order to improve the efficiency of the algorithm, we propose an improved clustering algorithm based on Delaunay triangulation, which is suitable for processing large data sets. We also put forward a new method to determine the global clustering threshold based on experiments on some typical data sets, so that the amount of calculation is reduced greatly. Experimental results show that clustering parameters are not necessary for obtaining better clustering results, and the proposed algorithm can realize automatic clustering. It also has faster calculation speed and higher efficiency, and therefore, more suitable for clustering on large data sets.  

Key words: algorithm;clustering;Delaunay;computational geometry;data mining