一种改进的基于Delaunay三角网的聚类算法

Mundur等提出了一种基于Delaunay三角网的聚类算法,并将其应用于视频帧的多维特征数据的聚类以生成视频摘要,取得了较好的效果。但是,该算法计算量太大,导致效率不高。为提高该算法的效率,以适合于对大数据集的处理,提出了一种改进的基于Delaunay三角网的聚类算法。通过在典型数据集上的实验,提出了一种新的确定全局聚类阈值的方法,使得计算量大为减少。实验结果表明,该算法无需用户提供聚类参数,也能得到良好的聚类结果,因此能够实现聚类过程自动化;并且计算速度更快,效率更高,适合于大数据集的处理。

An improved clustering algorithm based on Delaunay triangulation

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.