This paper proposed a new spectral graph clustering model by casting the non-categorical spatial data sets into an undirected graph. Decomposition of the graph to Delaunay graph has been done for computational efficiency. All pair shortest path based model has been adapted for the creation of the underlying Laplacian matrix of the graph. The similarity among the nodes of the graph is measured by a random selection based correlation coefficients. The effectiveness as well as the efficiency of the proposed model has beentasted and measuredwith standard data and the performances are compared with that of existing standard models.

Graph Clustering;Delaunay Triangulation;All-pair Shortest Path Distance; Similarity Matrix; Spectral Clustering

[1] A. K. Jain, M. N. Murty and P. J. Flynn, “Data Clustering: A Review,” ACM Computing Surveys, vol. 31, no. 3, pp. 264-323, Sept. 1999
[2] Duda, R. O., P. E. Hart and D. G. Stork, “Pattern Classification,” 2nd ed.,John Wiley&Sons,UK, 2008.
[3] A. K. Jain, and R. C. Dubes, “Algorithms for clustering data,” Prentice Hall, , March 1988.
[4] RuiXu and Donald C. Wunsch, II, “Clustering,” Wiley-IEEE Press, October 24, 2008
[5] B. Everitt, S. Landau S., M. Leese and D. Stahl, “Cluster Analysis,” Wiley, 5thedn. February, 2011
[6] M.E.J. Newman and M. Girvan, Mixing patterns and community structure in networks, in: R. PastorSatorras, M. Rubi, A. DíazGuilera (Eds.), Statistical Mechanics of Complex Networks: Proceedings of the XVIII Sitges Conference on Statistical Mechanics, in: Lecture Notes in Physics, vol. 625, SpringerVerlag GmbH, Berlin, Germany, 2003.
[7] L.C. Freeman, “A set of measures of centrality based on betweenness,” Sociometry, vol. 40, no. 1, pp. 35–41, 1977.
[8] Waqas Nawaz, Kifayat-Ullah Khan and Young-Koo Lee, "SPORE: shortest path overlapped regions and confined traversals towards graph clustering", Applied Intelligence, vol. 43,no. 1, pp. 208-232, 2015, DOI 10.1007/s10489-014-0637-7
[9] Satu Elisa Schaeffer, “Graph Clustering,” Computer Science Review, vol. I, pp. 27-64, 2007.DOI 10.1016/j.cosrev.2007.05.001.
[10] B. Mohar, "Some Applications of Laplace eigenvalues of graphs", Graph Symmetry: Algebraic Methods and Applications, NATO ASI, Series.C-497, pp.225-275, pub.Kluwer, Editor. G. Hahn and Sabidussi, 1997.
[11] Jianbo Shi and Jitendra Malik, "Normalized Cuts and Image Segmentation", IEEE Transactions on Pattern Analysis and Machine Intelligence, vol.22, no.8, pp.888-905, August, 2000.
[12] Ulrike von Luxburg, “A Tutorial on Spectral Clustering,” Statistics and Computing, vol. 17, no. 4, pp. 1-32, 2007.
[13] Daniel A. Spielman and Shang-HuaTeng, "Spectral Partitioning Works: Planar Graphs and Finite Element Meshes", Linear Algebra and its Applications, vol.421, no. 2-3, pp.284-305, March, 2007.
[14] R. B. Bapat, “The Laplacian Matrix of A Graph,” The Mathematics Student, vol. 65, nos. 1-4, pp. 214-223, 1996.
[15] A. E. Brouwer and W. H. Haemers, “Spectra of Graphs,” Springer, February, 2011.
[16] Jianyuan Li, Yingjie Xia andYuncai Liu, "Scalable Constrained Spectral Clustering", IEEE Transactions on Knowledge and Data Engineering,vol. 27, no. 2, pp. 589-593, September, 2014.
[17] Christina Chrysouli andAnastasiosTefas, "Spectral clustering and semi-supervised learning using evolving similarity graphs", Applied Soft Computing, vol.34, No. C, pp. 625-637, 2015.
[18] Parthajit Roy and J. K. Mandal, "A Novel Spectral Clustering based on Local Distribution", International Journal of Electrical and Computer Engineering(IJECE), vol.5, No.2, pp.361-370, April, 2015.
[19] Parthajit Roy, Swati Adhikari and J.K. Mandal, A Novel Similarity Matrix based Spectral Clustering for Two Class Problems, in Proceedings of the National Conference on Computing, Communication and Information Processing (NCCCIP-2015), ISBN: 978-93-84935-27-6, pp:149-157, May, 2015.
[20] HongjieJia, Shifei Ding, XinzhengXuand RuNie, "The latest research progress on spectral clustering", Neural Computing & Applications, vol.24, , no. 7-8 pp.1477-1486, June, 2014 , DOI 10.1007/s00521-013-1439-2.
[21] M. D. Berg, O. Cheong, M. V. Kreveld and M. Overmars, “Computational Geometry: Algorithms and Applications” 3rd ed., Springer-verlag, 2008.
[22] Jia LV, "Clustering Algorithm Based on Delaunay Triangulation Density Metric", inProceedings of the Seventh International Conference on Fuzzy Systems and Knowledge Discovery (FSKD 2010),vol.4, pp.1621-1624, 2010.
[23] Min Deng, Qiliang Liu, Tao Cheng and Yan Shi, "An adaptive spatial clustering algorithm based on delaunay triangulation", Computers, Environment and Urban Systems, vol.35, no. 4, pp.320-332, July, 2011.
[24] Parthajit Roy and J. K. Mandal, "A Delaunay Triangulation Preprocessing Based Fuzzy-Encroachment Graph Clustering for Large Scale GIS Data", in Proceedings of the International Symposium on Electronic System Design, 2012, pp.300-305, December, 2012.
[25] Renjie Chen, Yin Xu, Craig Gotsman, Ligang Liu, "A spectral characterization of the Delaunay triangulation", Computer Aided Geometric Design, vol.27, no. 4, pp.295-300, May, 2010.
[26] R. A. Fisher, “UCI machine learning repository,” 1936. [Online]. Available: http://archive.ics.uci.edu/ml
[27] L. Fu and E. Medico, “ FLAME, a novelfuzzyclusteringmethod for the analysis of DNA microarray data,” BMC Bioinformatics, vol. 8, no. 3, January 4, 2007, DOI: 10.1186/1471-2105-8-3.
[28] SriparnaSaha and SanghamitraBandyopadhyay, “Performance Evaluation of Some Symmetry-Based Cluster Validity Indexes”, IEEE Transaction on Systems, Man, and Cybernetics-Part C: Applications and Reviews, Vol-39, No-4, pp-420-425, July 2009.
[29] Parthajit Roy and J.K. Mandal, Performance Evaluation of Some Clustering Indices, presented in the conference Computational Intelligence in Data Mining - 2014, Volume 3, Published in the Springer online in Smart Innovation, Systems and Technologies, Volume 33, ISSN:2190-3018, ISBN(print): 978-81-322-2201-9, ISBN(online):978-81-322-2202-6 , pp:509-517, 2015.