A methodology of swarm intelligence application in clustering based on neighborhood construction

Download

index.pdf

Date

2011

Author

İnkaya, Tülin

Metadata

Show full item record

Item Usage Stats

209
views

165
downloads

In this dissertation, we consider the clustering problem in data sets with unknown number of clusters having arbitrary shapes, intracluster and intercluster density variations. We introduce a clustering methodology which is composed of three methods that ensures extraction of local density and connectivity properties, data set reduction, and clustering. The first method constructs a unique neighborhood for each data point using the connectivity and density relations among the points based upon the graph theoretical concepts, mainly Gabriel Graphs. Neighborhoods subsequently connected form subclusters (closures) which constitute the skeleton of the clusters. In the second method, the external shape concept in computational geometry is adapted for data set reduction and cluster visualization. This method extracts the external shape of a non-convex n-dimensional data set using Delaunay triangulation. In the third method, we inquire the applicability of Swarm Intelligence to clustering using Ant Colony Optimization (ACO). Ants explore the data set so that the clusters are detected using density break-offs, connectivity and distance information. The proposed ACO-based algorithm uses the outputs of the neighborhood construction (NC) and the external shape formation. In addition, we propose a three-phase clustering algorithm that consists of NC, outlier detection and merging phases. We test the strengths and the weaknesses of the proposed approaches by extensive experimentation with data sets borrowed from literature and generated in a controlled manner. NC is found to be effective for arbitrary shaped clusters, intracluster and intercluster density variations. The external shape formation algorithm achieves significant reductions for convex clusters. The ACO-based and the three-phase clustering algorithms have promising results for the data sets having well-separated clusters.

Subject Keywords

Cluster analysis., Ant algorithms., Swarm intelligence.

URI

http://etd.lib.metu.edu.tr/upload/12613232/index.pdf
https://hdl.handle.net/11511/20685

Collections

Graduate School of Natural and Applied Sciences, Thesis

Suggestions

OpenMETU
Core

An interactive preference based multiobjective evolutionary algorithm for the clustering problem Demirtaş, Kerem; Özdemirel, Nur Evin; Karasakal, Esra; Department of Industrial Engineering (2011) We propose an interactive preference-based evolutionary algorithm for the clustering problem. The problem is highly combinatorial and referred to as NP-Hard in the literature. The goal of the problem is putting similar items in the same cluster and dissimilar items into different clusters according to a certain similarity measure, while maintaining some internal objectives such as compactness, connectivity or spatial separation. However, using one of these objectives is often not sufficient to detect differ...
An evolutionary approach to generalized biobjective traveling salesperson problem Köksalan, Mustafa Murat; Ozturk, Diclehan Tezcaner (2017-03-01) We consider the generalized biobjective traveling salesperson problem, where there are a number of nodes to be visited and each node pair is connected by a set of edges. The final route requires finding the order in which the nodes are visited (tours) and finding edges to follow between the consecutive nodes of the tour. We exploit the characteristics of the problem to develop an evolutionary algorithm for generating an approxiMation of nondominated points. For this, we approximate the efficient tours using...
A new anisotropic perfectly matched layer medium for mesh truncation in finite difference time domain analysis Tong, MS; Chen, YC; Kuzuoğlu, Mustafa; Mittra, R (1999-09-01) In this paper an unsplit anisotropic perfectly matched layer (PML) medium, previously utilized in the context of finite element analysis, is implemented in the finite difference time domain (FDTD) algorithm. The FDTD anisotropic PML is easy to implement in the existing FDTD codes, and is well suited for truncating inhomogeneous and layered media without special treatment required in the conventional PML approach. A further advantage of the present approach is improved performance at lower frequencies. The a...
A density functional theory study on the structural and electronic properties of PbxSbySez (x plus y plus z=2, 3) clusters Pekoz, Rengin; Erkoç, Şakir (2018-01-30) The structural and electronic properties of neutral ternary PbxSbySez clusters (x y + z = 2, 3) in their ground states have been explored by means of density functional theory calculations. The geometric structures and binding energies are systematically explored and for the most stable configurations of each cluster type vibrational frequencies, charges on atoms, energy difference between highest occupied and lowest unoccupied molecular orbitals, and the possible dissociations channels have been analyzed. ...
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...

Citation Formats

T. İnkaya, “A methodology of swarm intelligence application in clustering based on neighborhood construction,” Ph.D. - Doctoral Program, Middle East Technical University, 2011.