Clustering approaches for high‐dimensional databases: A review

Advanced Review

Jasleen K. Sethi, Duraisamy Jude Hemanth, Lalit M. Goyal, Mamta Mittal

Published Online: Jan 23 2019

DOI: 10.1002/widm.1300

Full article on Wiley Online Library: HTML PDF

Can't access this content? Tell your librarian.

Data mining is an inevitable task in most of the emerging computing technologies as it debilitates the complexity of datasets by rendering a better insight. Moreover, it entails the efficacy to envisage ingeniously the vast and heterogeneous datasets and thus delineates substantial knowledge from the abundance of data by pragmatic implementation of suitable algorithm. There are galore of algorithms in literature for this purpose. Furthermore, clustering is widely used techniques to analyze the data within the purview of data mining and thus it became as a motivational impetus for the authors to survey the existing literature on this topic rigorously and have consequently identified various key parameters so that concomitant improvement can be possible while selecting a best fit clustering algorithm pertaining to a specific problem domain. Furthermore, clustering, classification and association rule mining are akin and indispensable to data mining and owing to these authors have also included interrelation and intertwining among these terms so that this work will presage chunk of help for the researchers working in this field. The present study also envisages and manifests the challenges associated with the clustering algorithms for two‐ and high‐dimensional databases in a flamboyant fashion. Over and above, this work identifies key parametric attributes to assess the clustering algorithms which in turn benevolent the existing work and paves the way for profound future research in this realm. This article is categorized under: Technologies > Structure Discovery and Clustering Technologies > Classification Technologies > Association Rules Fundamental Concepts of Data and Knowledge > Big Data Mining

Data mining techniques

[ Normal View | Magnified View ]

Taxonomy of clustering algorithms for high‐dimensional databases

[ Normal View | Magnified View ]

Clustering approaches for two‐dimensional databases

[ Normal View | Magnified View ]

References

Aggarwal,, C. C., Wolf,, J. L., Yu,, P. S., Procopiuc,, C., & Park,, J. S. (1999). Fast algorithm for projected clustering. In Proceedings of the ACM SIGMOD International Conference on Management of Data (pp. 61–72). New York, NY: ACM Press.
Aggarwal,, C. C., & Yu,, P. S. (2000). Finding generalized projected clusters in high dimensional spaces. In Proceedings of the ACM SIGMOD International Conference on Management of Data (pp. 70–81). New York, NY: ACM Press.
Agrawal,, R., Gehrke,, J., Gunopulos,, D., & Raghavan,, P. (1998). Automatic subspace clustering of high dimensional data for data mining applications. Proceedings of the ACM SIGMOD International Conference on Management of Data, Seattle, WA (pp. 94–105).
Agrawal,, R., & Srikant,, R. (1994). Fast algorithms for mining association rules. Proceedings of the 20th VLDB Conference (pp. 487–499).
Ankerst,, M., Breuing,, M. M., Kriegel,, H.‐P., & Sander,, J. (1999). OPTICS: Ordering points to identify the clustering structure. Proceedings of the ACM SIGMOD International Conference on Management of Data (pp. 49–60).
Arandjelovic,, O. (2013, August). Discriminative k‐means Clustering. Paper presented at the International Joint Conference on Neural Networks (IJCNN) (pp. 1–7).
Berkhin,, P. (2006). A survey of clustering data mining techniques. In Kogan Jacob, Nicolas Charles, Teboulle Marc (Eds.), Grouping multidimensional data (pp. 25–71). Berlin, Heidelberg: Springer.
Bezdek,, J. C., Ehrlich,, R., & Full,, W. (1984). FCM: The fuzzy c‐means clustering algorithm. Computers %26 Geosciences, 10, 191–203.
Biswas,, G., Weinberg,, J. B., & Fisher,, D. H. (1998). ITERATE: A conceptual clustering algorithm for data mining. IEEE Transactions on Systems, Man and Cybernetics, Part C, 28, 100–111.
Breiman,, L., Friedman,, J. H., Olshen,, R. A., & Stone,, C. J. (1984). Classification and regression trees. Monterey, CA: Wadsworth %26 Brooks.
Chang,, J.‐W., & Jin,, D.‐S. (2002). A new cell‐based clustering method for large, high‐dimensional data in data mining applications. In Proceedings of the ACM Symposium on Applied Computing (pp. 503–507). New York, NY: ACM Press.
Chen,, L. F., Jiang,, Q. S., & Wang,, S. R. (2007). A new unsupervised term weighting scheme for document clustering. Journal of Computational Information Systems, 3(4), 1455–1464.
Cheng,, C. H., & Fu,, A. W. (1999). Entropy‐based subspace clustering for mining numerical data. (Unpublished PhD dissertation). Chinese University of Hong Kong.
Chiu,, S. L. (1994). Fuzzy model identification based on cluster estimation. Journal of Intelligent Fuzzy Systems, 2(3), 267–278.
Chiu,, T., Fang,, D. P., Chen,, J., Wang,, Y., & Jeris,, C. (2001). A robust and scalable clustering algorithm for mixed type attributes in large database environment. Proceedings of the International Conference on Knowledge Discovery and Data Mining (KDD01), San Francisco, CA (pp. 263–268).
Cortes,, C., & Vapnik,, V. (1995). Support‐vector networks. Machine Learning, 20(3), 273–297.
Cover,, T., & Hart,, P. (1967). Nearest neighbor pattern classification. IEEE Transactions on Information Theory, 13(1), 21–27.
De la Torre,, F., & Kanade,, T. (2006, June). Discriminative cluster analysis. Proceedings of the 23rd International Conference on Machine Learning (pp. 241–248). ACM.
Dempster,, A. P., Laird,, N. M., & Rubin,, D. B. (1977). Maximum likelihood from incomplete data via the EM algorithm. Journal of the Royal Statistical Society, Series B, 39, 1–38.
Dubey,, A. K., Gupta,, U., & Jain,, S. (2016). Analysis of k‐means clustering approach on the breast cancer Wisconsin dataset. International Journal of Computer Assisted Radiology and Surgery, 11(11), 2033–2047.
Duda,, R. O., & Hart,, P. E. (1973). Pattern classification and scene analysis. New York, NY: John Wiley and Sons.
El‐Hamdouchi,, A., & Willett,, P. (1989). Comparison of hierarchic agglomerative clustering methods for document retrieval. The Computer Journal, 32(3), 220–227.
Ester,, M., Kriegel,, H.‐P., Sander,, J., & Xu,, X. (1996). A density based algorithm for discovering clusters in large spatial databases with noise. In Proceedings of the 2nd International Conference on Knowledge Discovery in Databases and Data Mining (pp. 226–231). Portland: AAAI Press.
Fahad,, A., Alshatri,, N., Tari,, Z., Alamri,, A., Khalil,, I., Zomaya,, A. Y., … Bouras,, A. (2014). A survey of clustering algorithms for big data: Taxonomy and empirical analysis. IEEE Transactions on Emerging Topics in Computing, 2, 267–279.
Fahim,, A. M., Salem,, A. M., Torkey,, F. A., & Ramadan,, M. A. (2006). An efficient enhanced k‐means clustering algorithm. Journal of Zhejiang University. Science. A, 7(10), 1626–1633.
Friedman,, J. H., & Meulman,, J. J. (2002). Clustering objects on subsets of attributes. Journal of the Royal Statistical Society: Series B, 66(4), 815–849.
Ghosh,, S., & Dubey,, S. K. (2013). Comparative analysis of k‐means and fuzzy c‐means algorithms. International Journal of Advanced Computer Science and Applications, 4(4), 35–39.
Goil,, S., Nagesh,, H., & Choudhary,, A. (1999). MAFIA: Efficient and scalable subspace clustering for very large data sets. Technical Report CPDC‐TR‐9906‐010. Northwestern University, Evanston, IL.
Gong,, M., Liang,, Y., Shi,, J., Ma,, W., & Ma,, J. (2013). Fuzzy c‐means clustering with local information and kernel metric for image segmentation. IEEE Transactions on Image Processing, 22(2), 573–584.
Górriz,, J. M., Ramírez,, J., Lang,, E. W., & Puntonet,, C. G. (2006). Hard C‐means clustering for voice activity detection. Speech Communication, 48(12), 1638–1649.
Goyal,, L. M., Mittal,, M., & Sethi,, J. K. (2016). Fuzzy model generation using subtractive and fuzzy C‐means clustering. CSI Transactions on ICT, 4(2‐4), 129–133.
Guha,, S., Rastogi,, R., & Shim,, K. (1998). CURE: An efficient clustering algorithm for large databases. Proceedings of the ACM SIGMOD International Conference on Management of Data (pp. 73–84).
Guha,, S., Rastogi,, R., & Shim,, K. (1999). Rock: A Robust Clustering Algorithm for Categorical Attributes. Paper presented at the International Conference on Data Engineering, Sydney, Australia, March 1999 (pp. 512–521).
Halkidi,, M., Batistakis,, Y., & Vazirgiannis,, M. (2001). On clustering validation techniques. Journal of Intelligent Information Systems, 17(2/3), 107–145.
Halkidi,, M., Batistakis,, Y., & Vazirgiannis,, M. (2002a). Cluster validity methods: Part I. SIGMOD Record, 31(2), 40–45.
Halkidi,, M., Batistakis,, Y., & Vazirgiannis,, M. (2002b). Cluster validity checking methods: Part II. SIGMOD Record, 31, 19–27.
Han,, E.‐H., Karypis,, G., Kumar,, V., & Mobasher,, B. (1997). Clustering in a high‐dimensional space using hypergraph models. Technical Report. Department of Computer Science, University of Minnesota, Minneapolis, MN.
Han,, J., & Kamber,, M. (2006). Data mining: Concepts and techniques. Massachusetts, MA: Morgan Kaufmann Publishers.
Han,, J., Pei,, J., & Yin,, Y. (2000). Mining frequent patterns without candidate generation. ACM Sigmod Record (Vol. 29, No. 2, pp. 1–12). ACM, New York, NY.
Hinneburg,, A., & Keim,, D. (1998). An efficient approach to clustering in large multimedia databases with noise. Proceedings of the 4th International Conference on Knowledge Discovery and Data Mining, New York (pp. 58–65).
Hodge,, V. J., & Austin,, J. (2004). A survey of outlier detection methodologies. Artificial Intelligence Review, 22(2), 85–126.
Hofmayer,, D. P. (2017). Clustering by minimum cut hyper planes. IEEE Transactions on Pattern Analysis and Machine Intelligence, 39(8), 1547–1560.
Hu,, T., Liu,, C., Tang,, Y., Sun,, J., Xiong,, H., & Sung,, S. Y. (2014). High‐dimensional clustering: A clique‐based hypergraph partitioning framework. Knowledge and Information Systems, 39(1), 61–88.
Jain,, A. K. (2010). Data clustering: 50 years beyond K‐means. Pattern Recognition Letters, 31(8), 651–666.
Janssens,, F., Glänzel,, W., & De Moor,, B. (2007). Dynamic hybrid clustering of bioinformatics by incorporating text mining and citation analysis. Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (pp. 360–369). ACM.
Jin,, C. H., Pok,, G., Lee,, Y., Park,, H. W., Kim,, K. D., Yun,, U., & Ryu,, K. H. (2015). A SOM clustering pattern sequence‐based next symbol prediction method for day‐ahead direct electricity load and price forecasting. Energy Conversion and Management, 90, 84–92.
Karypis,, G., Han,, E.‐H., & Kumar,, V. (1999). CHAMELEON: A hierarchical clustering algorithm using dynamic modeling. IEEE Computer, 32(8), 68–75.
Karypis,, G., & Kumar,, V. (1998). hMETIS 1.5: A hypergraph partitioning package. Technical Report. Department of Computer Science, University of Minnesota, Minneapolis, MN.
Kaufman,, L., & Rousseeuw,, P. J. (1987). Clustering by means of medoids. In Y. Dodge, (Ed.), Statistical data analysis based on the L1 norm (pp. 405–416). Amsterdam: Elsevier.
Kausar,, N., Abdullah,, A., Samir,, B. B., Palaniappan,, S., AlGhamdi,, B. S., & Dey,, N. (2016). Ensemble clustering algorithm with supervised classification of clinical data for early diagnosis of coronary artery disease. Journal of Medical Imaging and Health Informatics, 6(1), 78–87.
Kohonen,, T. (1998). The self‐organizing map. Neurocomputing, 21(1), 1–6.
Kriegel,, H. P., Kröger,, P., & Zimek,, A. (2009). Clustering high‐dimensional data: A survey on subspace clustering, pattern‐based clustering, and correlation clustering. ACM Transactions on Knowledge Discovery from Data, 3(1), 1–57.
Krishnapuram,, R., Joshi,, A., Nasraoui,, O., & Yi,, L. (2001). Low‐complexity fuzzy relational clustering algorithms for web mining. IEEE Transactions on Fuzzy Systems, 9(4), 595–607.
Kumar,, D., Bezdek,, J. C., Palaniswami,, M., Rajasegarar,, S., Leckie,, C., & Havens,, T. C. (2016). A hybrid approach to clustering in big data. IEEE Transactions on Cybernetics, 46(10), 2372–2385.
Lloyd,, S. P. (1982). Least squares quantization in PCM. IEEE Transactions on Information Theory, 28, 129–137.
MacQueen,, J. (1967). Some methods for classification and analysis of multivariate observations. Proceedings of the 5th Symposium on Mathematical Statistics and Probability, Berkeley, CA (Vol. 1, pp. 281–297).
Markovitch,, S., & Rosenstein,, D. (2002). Feature generation using general constructor functions. Machine Learning, 49(1), 59–98.
Milenova,, B. L., & Campos,, M. M. (2002). O‐cluster: Scalable clustering of large high dimensional data sets. In Vipin Kumar (Ed.), Oracle Data Mining Technologies (pp. 290–297). Oracle Corporation.
Mittal,, M., Sharma,, R. K., & Singh,, V. P. (2014). Validation of k‐means and threshold based clustering method. International Journal of Advancements in Technology, 5(2), 1–7.
Mittal,, M., Sharma,, R. K., & Singh,, V. P. (2015). Modified single pass clustering with variable threshold approach. International Journal of Innovative Computing, Information and Control, 11(1), 1–8.
Mittal,, M., Singh,, V. P., & Sharma,, R. K. (2011). Random automatic detection of clusters. In International Conference on Image Information Processing (ICIIP) (pp. 1–6).
Ng,, R. T., & Han,, J. (2002). CLARANS: A method for clustering objects for spatial data mining. IEEE Transactions on Knowledge and Data Engineering, 14(5), 1003–1016.
Pandey,, S. C., & Nandi,, G. C. (2014). TSD based framework for mining the induction rules. Journal of Computational Science, 5, 184–195.
Pandey,, S. C., & Nandi,, G. C. (2016). Convergence of knowledge, nature and computations: A review. Soft computing—A fusion of foundations. Methodologies and Applications, 20, 319–342.
Parsons,, L., Haque,, E., & Liu,, H. (2004). Subspace clustering for high dimensional data: A review. ACM SIGKDD Explorations Newsletter, 6(1), 90–105.
Polat,, K. (2016). Intelligent recognition of diabetes disease via FCM based attribute weighting. World Academy of Science, Engineering and Technology. International Journal of Computer and Information Engineering, 10(4), 676–680.
Pramod,, S., & Vyas,, O. P. (2010). Survey on frequent item set mining algorithms. International Journal of Computer Applications, 1(15), 1–8.
Procopiuc,, C. M., Agarwal,, P. K., Jones,, M., & Murli,, T. M. (2002). A Monte Carlo algorithm for fast projective clustering. In Proceedings of the ACM SIGMOD International Conference on Management of Data (pp. 418–427). New York, NY: ACM Press.
Quinlan,, J. R. (1986). Induction of decision trees. Machine Learning, 1, 81–106.
Quinlan,, J. R. (1993). C4.5: programs for machine learning. San Mateo, CA: Morgan Kaufmann Publishers.
Saxena,, A., Mohan Goyal,, L., & Mittal,, M. (2015). Comparative analysis of clustering methods. International Journal of Computer Applications, 118(21), 30–35.
Shao,, Y., & Lunetta,, R. S. (2012). Comparison of support vector machine, neural network, and CART algorithms for the land‐cover classification using limited training data points. ISPRS Journal of Photogrammetry and Remote Sensing, 70, 78–87.
Sheikholeslami,, G., Chatterjee,, S., & Zhang,, A. (2000). WaveCluster: A wavelet‐based clustering approach for spatial data in very large databases. The VLDB Journal, 8, 289–304.
Von Luxburg,, U. (2007). A tutorial on spectral clustering. Statistics and Computing, 17(4), 395–416.
Wang,, W., Yang,, J., & Muntz,, R. (1997). STING: A statistical information grid approach to spatial data mining. Proceedings of the 23rd VLDB Conference, Athens, Greece (pp. 186–195).
Wen,, Z., Hou,, B., Wu,, Q., & Jiao,, L. (2017). Discriminative transformation learning for fuzzy sparse subspace clustering. IEEE Transactions on Cybernetics, 48(8), 2218–2231.
Woo,, K. G., Lee,, J.‐H., Kim,, M.‐H., & Lee,, Y.‐J. (2002). FINDIT: A fast and intelligent subspace clustering algorithm using dimension voting. Information and Software Technology, 46(4), 255–271.
Xiong,, H., Wu,, J., & Chen,, J. (2009). k‐means clustering versus validation measures: A data‐distribution perspective. IEEE Transactions on Systems, Man and Cybernetics, Part B, 39(2), 318–331.
Yang,, J., Wang,, W., Wang,, H., & Yu,, P. (2002). δ‐clusters: Capturing subspace correlation in a large data set. Proceedings of the 18th International Conference on Data Engineering (pp. 517–528).
Yazdani‐Chamzini,, A., Razani,, M., Yakhchali,, S. H., Zavadskas,, E. K., & Turskis,, Z. (2013). Developing a fuzzy model based on subtractive clustering for road header performance prediction. Automation in Construction, 35, 111–120.
Yoo,, J. Y., Lee,, M. H., Aloyce,, G., & Yang,, D. M. (2016). Creating a Naïve Bayes document classification scheme using an Apriori algorithm. Advanced Science and Technology Letters, 133, 34–38.
Zaki,, M., Parthasarathy,, S., Ogihara,, M., & Li,, W. (1997). New algorithms for fast discovery of association rules. Proceedings of the 3rd International Conference on Knowledge Discovery and Data Mining (KDD) (pp. 283–286).
Zhang,, G. P. (2000). Neural networks for classification: A survey. IEEE Transactions on Systems, Man, and Cybernetics. Part C, 30(4), 451–462.
Zhang,, T., Ramakrishnan,, R., & Livny,, M. (1996). BIRCH: An efficient data clustering method for very large databases. Proceedings of the ACM SIGMOD Conference on Management of Data, Montreal, Canada (pp. 103–114). ACM, New York, NY.

Access to this WIREs title is by subscription only.

Recommend to Your
Librarian Now!

Clustering approaches for high‐dimensional databases: A review

Browse by Topic

Access to this WIREs title is by subscription only.

The latest WIREs articles in your inbox