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

158
views

0
downloads

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

Journal

PATTERN RECOGNITION LETTERS

DOI

https://doi.org/10.1016/j.patrec.2014.09.007

Collections

Department of Industrial Engineering, Article

Suggestions

OpenMETU
Core

An Approach for introducing a set of domain specific components Yiğit, İbrahim Onuralp; Doğru, Ali Hikmet; Department of Computer Engineering (2015) In this thesis, a preliminary methodology is proposed for the determination of a set of components to populate the domain model of a Software Product Line infrastructure. Software Product Line based approaches focus on the reusability of assets for a family of software products. For effective reuse, the definition of reusable assets in this thesis considers variability in a domain. The approach is based on variability specifications that is rooted in Feature Models and is reflected to a component modeling n...
A Graph-Based Concept Discovery Method for n-Ary Relations Abay, Nazmiye Ceren; MUTLU, ALEV; Karagöz, Pınar (2015-09-04) Concept discovery is a multi-relational data mining task for inducing definitions of a specific relation in terms of other relations in the data set. Such learning tasks usually have to deal with large search spaces and hence have efficiency and scalability issues. In this paper, we present a hybrid approach that combines association rule mining methods and graph-based approaches to cope with these issues. The proposed method inputs the data in relational format, converts it into a graph representation, and...
A prefetching method for interactive WEB GIS applications Yeşilmurat, Serdar; İşler, Veysi; Department of Computer Engineering (2010) A Web GIS system has a major issue of serving the map data to the client applications. Since most of the GIS services provide their geospatial data as basic image formats like PNG and JPEG, constructing those images and transferring them over the internet are costly operations. To enhance this inefficient process, various approaches are offered. Caching the responses of the requests on the client side is the most commonly implemented solution. However, this method is not adequate by itself. Besides caching ...
A clustering method for web data with multi-type interrelated components Bolelli, Levent; Ertekin Bolelli, Şeyda; Zhou, Ding; Giles, C Lee (2007-05-08) Traditional clustering algorithms work on "flat" data, making the assumption that the data instances can only be represented by a set of homogeneous and uniform features. Many real world data, however, is heterogeneous in nature, comprising of multiple types of interrelated components. We present a clustering algorithm, K-SVMeans, that integrates the well known K-Means clustering with the highly popular Support Vector Machines(SVM) in order to utilize the richness of data. Our experimental results on author...
Investigation of haptic line graph comprehension through co production of gesture and language Deniz, Ozan; Mehmetcan, Fal; Acartürk, Cengiz (null; 2013-06-30) In communication settings, statistical graphs accompany language by providing visual access to various aspects of domain entities, such as conveying information about trends. A similar and comparable means for providing perceptual access is to provide haptic graphs for blind people. In this study, we present the results of an experimental study that aimed to investigate visual line graphs and haptic line graphs in time domain by means of gesture production as an indicator of event conceptualization. The par...

Citation Formats

T. İNKAYA, S. Kayaligil, and N. E. Özdemirel, “An adaptive neighbourhood construction algorithm based on density and connectivity,” PATTERN RECOGNITION LETTERS, pp. 17–24, 2015, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/40684.