The OPTICS algorithm is a hierarchical density-based clustering method. It creates reachability plots to identify all clusters in the point set. Nevertheless, it has limitation, namely it is very slow for large data sets. We introduce the GridOPTICS algorithm, which builds a grid structure to reduce the number of data points, then it applies the OPTICS clustering algorithm on the grid structure. In order to get the clusters, the algorithm uses the reachability plots of the grid structure, then it determines to which cluster the original input points belong. The experimental results show that our new algorithm is faster than the OPTICS, the speed-up can be one or two orders of magnitude or more, which depends mainly on the τ parameter of the GridOPTICS algorithm. At the end of the article, we give some advice to which point set you can apply the GridOPTICS algorithm.
AchtertE., BöhmC. and KrögerP., DeLi-clu: Boosting robustness, completeness, usability and efficiency of hierarchical clustering by a closest pair ranking, in: Advances in Knowledge Discovery and Data Mining, edited by NgW.-K., KitsuregawaM., LiJ. and ChangK., Lecture Notes in Computer Science, Springer Berlin Heidelberg, 3918 (2006), 119-128. http://dx.doi.org/101007/11731139_16.
2.
AgrawalR., GehrkeA.R.J., GunopulosD. and RaghavanP., Automatic subspace clustering of high dimensional data for data mining applications, SIGMOD Rec, 27(2) (Jun 1998), 94-105. doi: 10.1145/276305.276314.
3.
AlzaalanM.E., AldahdoohR.T. and AshourW., Eoptics enhancement ordering points to identify the clustering structure, in: International Journal of Computer Applications (0975-8887)40(17) (2012).
4.
AnkerstM., BreunigM.M., KriegelH.-P. and SanderJ., OPTICS: Ordering points to identify the clustering structure, in: Proceedings of the 1999 ACM SIGMOD International Conference on Management of Data, SIGMOD '99, New York, NY, USA: ACM, (1999), 49-60. doi: 10.1145/304182.304187.
BreunigM.M., KriegelH.-P. and SanderJ., Fast hierarchical clustering based on compressed data and optics, in: Proceedings of the 4th European Conference on Principles of Data Mining and Knowledge Discovery, PKDD '00, London, UK, UK: Springer-Verlag, (2000), 232-242. http://dlacm.org/citation.cfm?id=645804.669672.
7.
HuangD. and PengW., Grid-based DBSCAN algorithm with referential parameters, Physics Procedia, Part B, 24(0) (2012), 1166-1170. doi: http://dxdoi.org/10.1016/j.phpro.2012.02.174.
8.
EsterM., KriegelH.-P., SanderJ. and XuX., A density-based algorithm for discovering clusters in large spatial databases with noise, KDD96(34) (1996), 226-231.
9.
FräntiP. and VirmajokiO., Iterative shrinking method for clustering problems, Pattern Recognition39(5) (May 2006), 761-765.
10.
GanG., MaC. and WuJ., Data Clustering: Theory, Algorithms and Applications, SIAM, 20 (2007).
11.
GionisA., MannilaH. and TsaparasP., Clustering aggregation, ACM Transactions on Knowledge Discovery From Data (TKDD)1(1) (2007), 1-30.
12.
HanJ. and KamberM., Data mining, concepts and techniques, Elsevier (2006).
13.
HinneburgA. and KeimD.A., Optimal grid-clustering: Towards breaking the curse of dimensionality in high-dimen- sional clustering, in: Proceedings of the 25th International Conference on Very Large Data Bases, VLDB '99, San Francisco, CA, USA: Morgan Kaufmann Publishers Inc., (1999), 506-517. http://dlacm.org/citation.cfm?id=645925.671505.
14.
HinneburgA. and GabrielH.-H., DENCLUE 2.0: Fast clustering based on kernel density estimation, in: Advances in Intelligent Data Analysis VII, BertholdM.R., Shawe-TaylorJ. and LavračN., ed., Lecture Notes in Computer Science, Springer Berlin Heidelberg, 4723 (2007), 70-80. http://dxdoi.org/10.1007/978-3-540-74825-0_7.
15.
KärkkäinenA. and PasiF., Dynamic local search algorithm for the clustering problem, Research Report A (2002), 6.
16.
KarypisG., HanE.H. and KumarV., CHAMELEON: A hierarchical 765 clustering algorithm using dynamic modeling, IEEE Trans on Computers32(8) (1999), 68-75.
17.
MaL., GuL., QiaoS.Y. and WangJ., G-DBSCAN: An improved DBSCAN clustering method based on grid, in: Advanced Science and Technology Letters74 (ASEA), (2014), 23-28. http://dxdoi.org/10.14257/astl.2014.74.05..
18.
MaS., WangT.J., TangS.W., YangD.Q. and GaoJ., A new fast clustering algorithm based on reference and density, in: Advances in Web-Age Information Management, DongG., TangC. and WangW., ed., Lecture Notes in Computer Science, Springer Berlin Heidelberg2762 (2003), 214-225. http://dxdoi.org/10.1007/978-3-540-45160-0_21.
19.
MannA.K. and KaurN., Grid density based clustering algorithm, in: International Journal of Advanced Research in Computer Engineering and Technology, (IJARCET) 2(6) (2013), 2143-2147.
20.
ParikhM. and VarmaT., Survey on different grid based clustering algorithm, in: International Journal of Advance Reseach in Computer Science and Management Studies2(2) (2014). heep://www.ijarcsms.com.
21.
PatwaryM.A., PalsetiaD., AgrawalA., LiaoW.-K., ManneF. and ChoudharyA., Scalable parallel optics data clustering using graph algorithmic techniques, in: Proceedings of the International Conference on High Performance Computing, Networking, Storage and Analysis, SC '13, New York, NY, USA: ACM, (2013), 49:1-49:12. doi: 10.1145/2503210.2503255.
22.
SanderJ., QinX., LuZ., NiuN. and KovarskyA., Automatic extraction of clusters from hierarchical clustering representations, in: Proceedings of the 7th Pacific-Asia Conference on Advances in Knowledge Discovery and Data Mining, PAKDD '03, Berlin, Heidelberg: Springer-Verlag, (2003), 75-87. http://dlacm.org/citation.cfm?id=1760894.1760906.
23.
SchneiderJ. and VlachosM., Fast parameterless density-based clustering via random projections, in: Proceedings of the 22nd ACM International Conference on Conference on Information and Knowledge Management, CIKM '13, New York, NY, USA: ACM, (2013), 861-866. doi: 10.1145/2505515.2505590.
24.
SheikholeslamiG., ChatterjeeS. and ZhangA., WaveCluster: A wavelet-based clustering approach for spatial data in very large databases, The VLDB Journal8(3-4) (Feb 2000), 289-304. doi: 10.1007/s007780050009.
25.
WangW., YangJ. and MuntzR.R., STING: A statistical information grid approach to spatial data mining, in: Proceedings of the 23rd International Conference on Very Large Data Bases, VLDB '97, San Francisco, CA, USA: Morgan Kaufmann Publishers Inc., (1997), 186-195. http://dlacm.org/citation.cfm?id=645923.758369.
26.
YueS., WeiM., LiY. and WangX., Ordering grids to identify the clustering structure, in: Advances in Neural Networks - ISNN 2007, LiuD., FeiS., HouZ., ZhangH. and SunC., ed., 4492612-619, Lecture Notes in Computer Science, Springer Berlin Heidelberg, (2007). http://dxdoi.org/10.1007/978-3-540-72393-6_73.
27.
ZhangT., RamakrishnanR. and LivnyM., BIRCH: A new data clustering algorithm and its applications, Data Mining and Knowledge Discovery1(2) (1997), 141-182. doi: 10.1023/A:1009783824328.
28.
ZhaoY., CaoJ., ZhangC. and ZhangS., Enhancing grid-density based clustering for high dimensional data, Journal of Systems and Software84(9) (2011), 1524-1539.
