Computer Engineering and Applications ›› 2015, Vol. 51 ›› Issue (16): 166-170.
Previous Articles Next Articles
ZHU Qingsheng, TANG Hui, FENG Ji
Online:
Published:
朱庆生,唐 汇,冯 骥
Abstract: 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.
Key words: Delaunay triangulation, outlier, space neighbors, [K-nearest] neighbor
摘要: 在传统的基于[K]近邻的算法中,需要为算法设置邻居参数[k]的值,只有具备相关的先验知识才能确定合适的参数值。为了减少参数对于离群点检测的影响,提出了一种无需参数的基于Delaunay三角剖分的离群点检测算法。Delaunay三角剖分是数值分析以及图形学中的重要基础理论,它的构建无需任何参数,在三角剖分图中的每个数据对象与它空间上相邻的点都存在边直接相连,因此可以形成一种有效的邻居关系。算法首先通过Delaunay三角剖分形成每个点的空间邻居集合,然后根据每个点与它们空间邻居之间的分布特征,计算它们的离群程度,根据离群程度的大小判断该点是否为离群点。通过实验与相关的算法比较,算法具有更好的效果。
关键词: Delaunay三角剖分, 离群点, 空间邻居, [K]近邻
ZHU Qingsheng, TANG Hui, FENG Ji. Outlier detection algorithm based on Delaunay triangulation[J]. Computer Engineering and Applications, 2015, 51(16): 166-170.
朱庆生,唐 汇,冯 骥. Delaunay三角剖分在离群点检测中的应用[J]. 计算机工程与应用, 2015, 51(16): 166-170.
0 / Recommend
Add to citation manager EndNote|Ris|BibTeX
URL: http://cea.ceaj.org/EN/
http://cea.ceaj.org/EN/Y2015/V51/I16/166