Delaunay三角剖分在离群点检测中的应用

摘要

It is difficult to choose an appropriate parameter k when using the traditional K-nearest neighbor algorithm. In order to detect outlier points of clustering automatically and effectively, an outlier detection algorithm without parameter based on Delaunay triangulation is proposed. Delaunay triangulation is an important theory in numerical analysis and graphics. There exists an edge directly connecting each data object with its neighbor points in the Delaunay triangulation diagram, and then a neighbor relationship is established effectively. To detect the outliers, Delaunay triangulation is used to obtain the neighborhood of each point. The outlier degree is calculated according to the distribution characteristics of each point and its spatial neighbors. The outlier is determined according to its outlier factor. The experimental results show this algorithm is more effective compared with the relevant algorithm.%在传统的基于K 近邻的算法中，需要为算法设置邻居参数k的值，只有具备相关的先验知识才能确定合适的参数值。为了减少参数对于离群点检测的影响，提出了一种无需参数的基于Delaunay三角剖分的离群点检测算法。Delaunay三角剖分是数值分析以及图形学中的重要基础理论，它的构建无需任何参数，在三角剖分图中的每个数据对象与它空间上相邻的点都存在边直接相连，因此可以形成一种有效的邻居关系。算法首先通过Delaunay三角剖分形成每个点的空间邻居集合，然后根据每个点与它们空间邻居之间的分布特征，计算它们的离群程度，根据离群程度的大小判断该点是否为离群点。通过实验与相关的算法比较，算法具有更好的效果。