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

Download
2011
İnkaya, Tülin
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.

Suggestions

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...
A simulated annealing approach to bicriteria scheduling problems on a single machine
Karasakal, Esra (2000-08-01)
In this paper, we apply a simulated annealing approach to two bicriteria scheduling problems on a single machine. The first problem is the strongly NP-hard problem of minimizing total flowtime and maximum earliness. The second one is the NP-hard problem of minimizing total flowtime and number of tardy jobs. We experiment on different neighbourhood structures as well as other parameters of the simulated annealing approach to improve its performance. Our computational experiments show that the developed appro...
A Probabilistic approach to sparse multi scale phase based stereo
ULUSOY PARNAS, İLKAY; Halıcı, Uğur; HANCOCK, EDWIN (2004-04-30)
In this study, a multi-scale phase based sparse disparity algorithm and a probabilistic model for matching are proposed. The disparity algorithm and the probabilistic approach are verified on various stereo image pairs.
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.