No Access

A Novel Parameter-Light Subspace Clustering Technique Based on Single Linkage Method

Bhagyashri A. Kelkar

http://orcid.org/0000-0001-5847-5795

Department of CSE, Sanjay Ghodawat University, Atigre Kolhapur 416118, India

E-mail Address: kelkarba@gmail.com

Search for more papers by this author

Sunil F. Rodd

Department of CSE, Gogte Institute of Technology, Belagavi, Karnataka 590008, India

Search for more papers by this author

, and

Umakant P. Kulkarni

Department of CSE, SDMCET Dharwar, Karnataka 580002, India

Search for more papers by this author

https://doi.org/10.1142/S0219649219500072Cited by:0 (Source: Crossref)

Abstract

Subspace clustering is a challenging high-dimensional data mining task. There have been several approaches proposed in the literature to identify clusters in subspaces, however their performance and quality is highly affected by input parameters. A little research is done so far on identifying proper parameter values automatically. Other observed drawbacks are requirement of multiple database scans resulting into increased demand for computing resources and generation of many redundant clusters. Here, we propose a parameter light subspace clustering method for numerical data hereafter referred to as CLUSLINK. The algorithm is based on single linkage clustering method and works in bottom up, greedy fashion. The only input user has to provide is how coarse or fine the resulting clusters should be, and if not given, the algorithm operates with default values. The empirical results obtained over synthetic and real benchmark datasets show significant improvement in terms of accuracy and execution time.

Keywords:

References

Abavisani, M and V Patel [2018] Multimodal sparse and low-rank subspace clustering. Information Fusion, 39, 168–177. Web of Science, Google Scholar
Aggarwal, CC et al. [1999] Fast algorithms for projected clustering. In Proceedings of the ACM International Conference on Management of Data (SIGMOD), Philadelphia, PA, pp. 61–72. Google Scholar
Aggarwal, CC and PS Yu [2000] Finding generalized projected clusters in high dimensional spaces. In Proceedings of the ACM SIGMOD International Conference on Management of Data, Dallas, TX, USA, pp. 70–81. Google Scholar
Agrawal, R et al. [1998] Automatic subspace clustering of high dimensional data for data mining applications. In Proceedings of the ACM SIGMOD International Conference on Management of Data, Seattle, WA, USA, pp. 94–105. Google Scholar
Bellman, R [1961] Adaptive Control Processes: A Guided Tour. Princeton, New Jersey: Princeton University Press. Google Scholar
Bohm, C et al. [2004] Density connected clustering with local subspace preferences. In Fourth IEEE International Conference on Data Mining, 2004, ICDM’04. Brighton, UK, pp. 27–34. Google Scholar
Cheng, CH et al. [1999] Entropy-based subspace clustering for mining numerical data. In Proceedings of the Fifth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Diego, CA, USA, pp. 84–93. Google Scholar
Elhamifar, E and R Vidal [2013] Sparse subspace clustering: Algorithm, theory, and applications. IEEE Transactions on Pattern Analysis and Machine Intelligence, 35(11), 2765–2781. Web of Science, Google Scholar
Eren, K et al. [2013] A comparative analysis of biclustering algorithms for gene expression data. Briefings in Bioinformatics, 14(3), 279–292. Web of Science, Google Scholar
Goil, S et al. (1999). Mafia: Efficient and scalable subspace clustering for very large data sets. Technical Report CPDC-TR-9906-010, Northwestern University. Google Scholar
Heckel, R et al. [2017] Dimensionality-reduced subspace clustering. Information and Inference: A Journal of the IMA, 6(3), 246–283. Google Scholar
Huang, X et al. [2014] DSKmeans: A new kmeans-type approach to discriminative subspace clustering. Knowledge Based Systems, 70, 293–300. Web of Science, Google Scholar
Huang, X et al. [2016] Time series k-means: A new kmeans type smooth subspace clustering for time series data. Information Sciences, 367, 1–13. Web of Science, Google Scholar
Jäckle, D et al. [2017] Pattern trails: Visual analysis of pattern evolutions in subspaces. Paper Presented at VAST 2017, Phoenix, USA. Google Scholar
Jaya Lakshmi, B et al. [2017a] A rough set based subspace clustering technique for high dimensional data. Journal of King Saud University — Computer and Information Science. Available at: http://dx.doi.org/10.1016/j.jksuci.2017.09.003. Google Scholar
Jaya Lakshmi, B et al. [2017b] An efficient algorithm for density based subspace clustering with dynamic parameter setting. International Journal of Information Technology Computer Science, 9(6), 27–33. Google Scholar
Jun, J et al. [2006] Subspace clustering of microarray data based on domain transformation. In Data Mining and Bioinformatics, Lecture Notes in Computer Science, Vol. 4316, pp. 14–28, Heidelberg: Springer. Google Scholar
Kailing et al. [2004] Density-connected subspace clustering for high-dimensional data. In Proceedings of SIAM International Conference on Data Mining (SDM’04), pp. 246–257. Google Scholar
Kaur, A and A Datta [2015] A novel algorithm for fast and scalable subspace clustering of high-dimensional data. Journal of Big Data, 2(1), 1–24. Google Scholar
Kriegel, H et al. [2005] A generic framework for efficient subspace clustering of high-dimensional data. In IEEE International Conference on Data Mining, IEEE, Houston, Texas, USA, pp. 250–257. Google Scholar
Kriegel, H et al. [2009] Clustering high-dimensional data: A survey on subspace clustering, pattern-based clustering, and correlation clustering. ACM Transactions on Knowledge Discovery in Data, 3(1), 1–58. Web of Science, Google Scholar
Kuhn, HW [1955] The Hungarian method for assignment problems. Naval Research Logistic Quarterly, 2, 83–97. Google Scholar
Lee D and J Shim [2015] Impact parameter analysis of subspace clustering. International Journal of Distributed Sensor Networks, 2015, 398452. Available at: http://dx.doi.org/10.1155/2015/398452. Web of Science, Google Scholar
Moise, G and J Sander [2008] Finding non-redundant, statistically significant regions in high dimensional 630 data: A novel approach to projected and subspace clustering. In Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ACM, pp. 533–541. Google Scholar
Müller, E [2009] DensEst: Density estimation for data mining in high dimensional spaces. In Proceedings of the 9th SIAM International Conference on Data Mining (SDM), Sparks, NV, pp. 173–184. Google Scholar
Müller, E et al. [2009] Evaluating clustering in subspace projections of high dimensional data. In Proceedings of 35th International Conference on Very Large Data Bases (VLDB 2009), Lyon, France, pp. 1270–1281. Google Scholar
Ozkok, F and M Celik [2017] A new approach to determine Eps parameter of DBSCAN algorithm. International Journal of Intelligent Systems and Applications in Engineering, 5 (4), 247–251. Google Scholar
Parsons, L et al. [2004] Subspace clustering for high dimensional data: A review. ACM SIGKDD Explorations Newsletter, 6(1), 90–105. Google Scholar
Peng, C et al. [2017] Subspace Clustering via variance regularized ridge regression. In The Thirtieth IEEE/CVF Conference on Computer Vision and Pattern Recognition, Honolulu, Hawaii, pp. 2931–2940. Google Scholar
Procopiuc, CM et al. [2002] A monte carlo algorithm for fast projective clustering. In Proceedings of the ACM SIGMOD International Conference on Management of Data, Madison, WI, USA, pp. 418–427. Google Scholar
Puri, C and N Kumar [2017] An entropy based method for overlapping subspace clustering, Procedia Computer Science, 122, 276–283. Google Scholar
Qi, L et al. [2016] Transformation invariant subspace clustering. Journal of Pattern Recognition, 59(C), 142–155. Google Scholar
Sibson, R [1973] SLINK: An optimally efficient algorithm for the single-link cluster method. The Computer Journal-British Computer Society, 16(1), 30–34. Google Scholar
Sim, K et al. [2013] A survey on enhanced subspace clustering. Data Mining and Knowledge Discovery, 26(2), 332–397. Web of Science, Google Scholar
Struski, L et al. [2018] Lossy compression approach to subspace Clustering. Information Sciences, 435, 161–183. Web of Science, Google Scholar
UCI Machine Learning Repository. Available at: http://archive.ics.uci.edu/ml/. Accessed on 11 May 2018. Google Scholar
Woo, KG and JH Lee [2002] FINDIT: A fast and intelligent subspace clustering algorithm using dimension voting. Information and Software Technology, 46(4), 255–271. Web of Science, Google Scholar
Yang, J et al. [2002] $δ$ -clusters: Capturing subspace correlation in a large data set. In 18th International Conference on Data Engineering, San Jose, CA, USA, pp. 517–528. Google Scholar
Yang, C et al. [2015] Sparse subspace clustering with missing entries. In IEEE International Conference on Machine Learning, Lille, France, Vol. 37, pp. 2463–2472. Google Scholar
Yao, J et al. [2018] Robust subspace clustering via penalized mixture of Gaussians. Neurocomputing, 278, 4–11. Web of Science, Google Scholar
Zhang, H, Y Tang et al. [2016a] A novel subspace clustering method based on data cohesion model. Optik - International Journal for Light and Electron Optic, 127(20), 8513–8519. Google Scholar
Zhang, H, H Zhai et al. [2016b] Spectral-spatial sparse subspace clustering for Hyperspectral imagery. IEEE Transactions on Geoscience and Remote Sensing, 54(6), 3672–3684. Web of Science, Google Scholar
Zhu, P et al. [2017] Subspace clustering guided unsupervised feature selection. Pattern Recognition 66, 364–374. Web of Science, Google Scholar
Zhu, W and J Zhou [2017] Nonlinear subspace clustering. In 2017 IEEE International Conference on Image Processing (ICIP), Beijing, pp. 4497–4501. Google Scholar