An adaptive neighbourhood construction algorithm based on density and connectivity

Date

2015-01-15

Author

İNKAYA, TÜLİN
Kayaligil, Sinan
Özdemirel, Nur Evin

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

17
views

0
downloads

Cite This

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.

Subject Keywords

Data neighbourhood, Gabriel graph, Density, Connectivity, Clustering, Local outlier detection

URI

https://hdl.handle.net/11511/40684

Collections

Department of Industrial Engineering, Article