An adaptive neighbourhood construction algorithm based on density and connectivity
An adaptive neighbourhood construction algorithm based on density and connectivity
复制标题
DOI：
10.1016/j.patrec.2014.09.007
复制
发表时间：
2015-01-15
影响因子：
5.1
通讯作者：
Ozdemirel, Nur Evin
中科院分区：
文献类型：
--
作者：
Inkaya, Tulin;Kayaligil, Sinan;Ozdemirel, Nur Evin
邻域是局部相似的数据点的细化组。它应该基于数据集中的局部关系来定义。然而，邻域参数的选择是传统邻域构造算法（如k-近邻和e-邻域）未解决的问题。为了解决这个问题，我们引入了一种新的邻域构造算法。我们假设没有关于数据集的先验信息。与文献中的邻域定义不同，该方法以自适应的方式提取数据点之间的密度、连通性和邻近关系，即考虑数据集中点的局部特征.它是基于一个接近图，加布里埃尔图。所提出的方法的输出是每个数据点的一组唯一的邻居。所提出的方法具有参数自由的优点。在聚类和局部离群点检测上对邻域构造算法的性能进行了测试。在不同数据集上的实验结果表明，与同类方法相比，该方法在邻域构造上平均精度提高了3-66%，在聚类上平均精度提高了4-70%.它还可以成功地检测离群值。(C)2014爱思唯尔有限公司版权所有。
A neighbourhood is a refined group of data points that are locally similar. It should be defined based on the local relations in a data set. However, selection of neighbourhood parameters is an unsolved problem for the traditional neighbourhood construction algorithms such as k-nearest neighbour and e-neighbourhood. To address this issue, we introduce a novel neighbourhood construction algorithm. We assume that there is no a priori information about the data set. Different from the neighbourhood definitions in the literature, the proposed approach extracts the density, connectivity and proximity relations among the data points in an adaptive manner, i.e. considering the local characteristics of points in the data set. It is based on one of the proximity graphs, Gabriel graph. The output of the proposed approach is a unique set of neighbours for each data point. The proposed approach has the advantage of being parameter free. The performance of the neighbourhood construction algorithm is tested on clustering and local outlier detection. The experimental results with various data sets show that, compared to the competing approaches, the proposed approach improves the average accuracy 3-66% in the neighbourhood construction, and 4-70% in the clustering. It can also detect outliers successfully. (C) 2014 Elsevier B.V. All rights reserved.