Sage Journals: Discover world-class research

Abstract

Conventional clustering algorithms optimize a single criterion, which may not conform to diverse needs of multidimensional data science. This paper proposes a new clustering algorithm that solves multiple clustering issues, called clustering by Marked Point Process (ClusterMPP). It is a new, efficient, scalable and unsupervised density-based clustering algorithm. ClusterMPP simulates a proposed Marked Point Process (MPP) to find clusters of complex shapes present in the raw data space. The outputs of this new algorithm, in the first step, are the observations belonging to each cluster mode called “prototypes”. The classification process is achieved, in the second step, using an improved KNN algorithm. We conduct intensive experiments to compare ClusterMPP with the most well-known algorithms. The results of ClusterMPP proved its efficiency on high complex and scalable datasets.

Keywords

Unsupervised learning density-based clustering mode detection Marked Point Process non-parametric multidimensional data overlapping clusters

Get full access to this article

View all access options for this article.

References

Agarwal

and Dhar

, Big Data, Data Science and Analytics the Opportunity and Challenge for IS Research, Information Systems Research 25(3) (2014), 443–448.

Alata

Burg

and Dupas

, Grouping/degrouping point process, a point process driven by geometrical and topological properties of a partition in regions, Computer Vision and Image Understanding 115(9) (2011), 1324–1339.

Benedek

, Detection of soldering defects in Printed Circuit Boards with Hierarchical Marked Point Processes, Pattern Recognition Letters 32(13) (2011), 1535–1543.

Benedek

Descombes

and Zerubia

, Building Development Monitoring in Multitemporal Remotely Sensed Image Pairs with Stochastic Birth-Death Dynamics, Pattern Analysis and Machine Intelligence, IEEE Transactions 34(1) (2012), 33–50.

Yang

B.S.

W.X.

and Zhen

, Automated Extraction of Building Outlines From Airborne Laser Scanning Point Clouds, Geoscience and Remote Sensing Letters, IEEE 10(6) (2013), 1399–1403.

Bohm

Railing

Kriegel

H.P.

and Kroger

, Density connected clustering with local subspace preferences, In IEEE ICDM, 2004.

Bouveyron

and Brunet-Saumard

, Model-based Clustering of High-dimensional Data: A Review, Comput. Stat. Data Anal 71 (2014), 52–78.

Carlos

and Coello-Coello

, Evolutionary Multiobjective Optimization: A Historical View of the Field, IEEE Computational Intelligence Magazine 1(1) (2006), 28–36.

Cassisi

Ferro

Giugno

et al., Enhancing density-based clustering Parameter reduction and outliers detection, Information Systems 38(3) (2013), 317–330.

10.

Chin

Y.C.

and Baddeley

A.J.

, Markov interacting component processes, Advances in Applied Probability 32(3) (2000), 597–619.

11.

Chin

Y.C.

and Baddeley

A.J.

, On connected component Markov point processes, Advances in Applied Probability 31(2) (1999), 279–282.

12.

Clifford

, Markov random fields in statistics, in: Grimmett

G.R.

Welsh

D.J.A.

(Eds.), Disorder in Physical Systems, A Volume in Honour of J.M. Hammersley. Clarendon Press, Oxford, 1990, pp. 19–32.

13.

Correa

C.D.

and Lindstrom

, Locally-scaled Spectral Clustering using Empty Region Graphs, In Proceeding KDD (2012), 1330–1338.

14.

Dempster

A.P.

Laird

N.M.

and Rubin

D.B.

, Maximum likelihood from incomplete data via the EM algorithm, Journal of the Royal Statistical Society, Serie B 39 (1977), 1–38.

15.

Descomber

Minlos

and Zhizhina

, Object Extraction Using a Stochastic Birth-and-Death Dynamics in Continuum, Journal of Mathematical Imaging and Vision 33(3) (2009), 347–359.

16.

Ester

Kriegel

H.P.

Sander

and Xu

, A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise, in: Proc of International Conference on Knowledge Discovery and Data Mining, 1996, pp. 226–231.

17.

Fahad

Alshatri

Tari

Alamri

Khalil

Zomaya

A.Y.

Foufou

and Bouras

, A Survey of Clustering Algorithms for Big Data: Taxonomy and Empirical Analysis, IEEE Transactions on Emerging Topics in Computing 2(3) (2014), 267–279.

18.

Glory

Shah

Bhensdadia

and Ganatra

A.P.

, An Empirical Evaluation of Density-Based Clustering Techniques, International Journal of Soft Computing and Engineering 2(1) (2012), 216–223.

19.

Green

P.J.

, Reversible jump Markov chain Monte Carlo computation and Bayesian model determination, Biometrika 82 (1995), 711–732.

20.

Jain

A.K.

, Data clustering: 50 years beyond K-means, Pattern Recognition Letters 31(08) (2010), 651–666.

21.

Khalid

and Razzaq

, TOBAE: A Density-based Agglomerative Clustering Algorithm, Journal of Classification 32(2) (2015), 241–267.

22.

Liang

Bai

Dang

and Cao

, The K-Means-Type Algorithms Versus Imbalanced Data Distributions, IEEE Transactions on Fuzzy Systems 20(4) (2012), 728–745.

23.

Lieshout

M.V.

and Stoica

R.S.

, Perfect simulation for marked point processes, Computational Statistics and Data Analysis 51(2) (2006), 679–698.

24.

Liu

You

and Cao

, A novel and quick svm-based multi-class classifier, Pattern Recognition 39(11) (2006), 2258–2264.

25.

Tang

Cao

and Tian

, An ef fi cient and scalable density-based clustering algorithm for datasets with complex structures, Neurocomputing 171 (2016), 9–22.

26.

Moussa

Sbihi

and Postaire

J.G.

, A Markov random field model for mode detection in cluster analysis, Pattern Recognition Letters 29(9) (2008), 1197–1207.

27.

Mouysset

Noailles

Ruiz

and Tauber

, Spectral Clustering: interpretation and Gaussian parameter, Studies in Classification, Data Analysis, and Knowledge Organization 4 (2013), 153–162.

28.

Ntoutsi

Zimek

Palpanas

Kroger

and Kriegel

H.P.

, Density-based projected clustering over high dimensional data streams, In SIAM SDM, 2012.

29.

Ordonez

, Models for association rules based on clustering and correlation, Intelligent Data Analysis 13(2) (2009), 337–358.

30.

Parimala

Daphne

and Senthilkumar

N.C.

, A Survey on Density Based Clustering Algorithms for Mining Large Spatial Databases, International Journal of Advanced Science and Technology 31 (2011), 59–66.

31.

Park

H.S.

and Jun

C.H.

, A Simple and Fast Algorithm for K-medoids Clustering, Expert Systems with Applications 36 (2009), 3336–3341.

32.

Postaire

J.G.

and Vasseur

C.P.C.

, An approximate solution to normal mixture identification with application to unsupervised pattern classification, IEEE Trans. Pattern Anal. Machine Intell 3(2) (1981), 163–179.

33.

Reddy

C.K.

and Vinzamuri

, A Survey of Partitional and Hierarchical Clustering Algorithms, Data Clustering: Algorithms and Applications (2013), 87–110.

34.

Schneider

and Vlachos

, Fast parameterless density-based clustering via random projections, in: Proc ACM International Conference on Information and Knowledge Management, 2013, pp. 861–866.

35.

Shao

Bohm

Yang

and Plant

, Synchronization-Inspired Partitioning and Hierarchical Clustering, IEEE Transactions on Knowledge and Data Engineering 25(4) (2013), 893–905.

36.

Stoica

R.S.

Gay

and Kretzschmar

, Cluster Pattern Detection in Spatial Data Based on Monte Carlo Inference, Biometrical Journal 49(4) (2007), 505–519.

37.

Stoica

R.S.

Martinez

V.J.

and Saar

, Filaments in observed and mock galaxy catalogues, Astronomy and Astrophysics 510(38) (2010), 1–12.

38.

Tran

Drab

and Daszykowski

, Revised DBSCAN algorithm to cluster data with dense adjacent clusters, Chemom. Intell. Lab. Syst 120 (2013), 92–96.

39.

Vallim

R.M.

Filho

J.A.

Mello

R.F.

Carvalho

A.C.

and Gama

, Unsupervised density-based behavior change detection in data streams, Intelligent Data Analysis 18(2) (2014), 181–201.

40.

Chen

Xiong

and Xie

, External validation measures for K-means clustering: A data distribution perspective, Expert Systems with Applications 36(3) (2009), 6050–6061.

41.

K.L.

and Yang

M.S.

, Mean Shift-based Clustering, Pattern Recognition 40 (2007), 3035–3052.

42.

Zhu

G.Q.

and Ding

, Data Mining with Big Data, IEEE Transactions on Knowledge and Data Engineering 26(1) (2014), 97–107.

43.

Zhang

X.Y.

and Song

Q.B.

, Predicting the number of nearest neighbors for the k-NN classification algorithm, Intelligent Data Analysis 18(3) (2014), 449–464.

44.

Yang

M.S.

Lai

C.Y.

and Lin

C.Y.

, A Robust EM Clustering Algorithm for Gaussian Mixture Models, Pattern Recognition 45 (2012), 3950–3961.

45.

Yang

Zhu

and Huang

, Spectral Clustering with Density Sensitive Similarity Function, Knowledge-Based Systems (2011), 621–628.

46.

Zhang

and Yu

, Local Density Adaptive Similarity Measurement for Spectral Clustering, Pattern Recognition Letters 32 (2011), 352–358.

ClusterMPP: An unsupervised density-based clustering algorithm via Marked Point Process

Abstract

Keywords

Get full access to this article

References