Bclusge: application of the law of buoyancy in the luster analysis

• Autorzy: Ziembiński R. Z.
• Języki publikacji: EN

Abstrakty

EN

The paper introduces a new algorithm for a cluster analysis named BClusGe. It uses a technique of the subspace clustering with an empty space removal. This new algorithm produces a multidimensional rectangular grid tightly adjusted to the processed data distribution. Afterwards, BClusGe merges adjacent folds contain-ing objects and produce the output set of clusters. An execution time of BClusGe depends on a number of folds created at the partitioning to describe the data distri-bution. Thus, data with the irregular distribution are clustered slower. Additionally, BClusGe delivers a B-tree structure describing found clusters. Its leafs are interconnected and allow to navigate between dense subspaces of the data distribution. The tree is useful in practical applications because it organizes hierarchically dependencies between clusters. The paper contains some experiments' results where BClusGe performance was compared to DBScan and K-means.

Słowa kluczowe

EN

cluster analysis; partitioning, subspace; grid; Law of Buoyancy

• Wydawca: Wydawnictwo Politechniki Poznańskiej
• Czasopismo: Foundations of Computing and Decision Sciences
• Rocznik: 2011
• Tom: Vol. 36, No. 2
• Strony: 131--155
• Opis fizyczny: Bibliogr. 15

Twórcy

autor

Ziembiński R. Z.

• Institute of Computing Science, Poznan University of Technology, ul. Piotrowo 2, 60-965 Poznan, Poland,

Bibliografia

• [1] Agrawal, R., Gehrke, J., Gunopulos, D., Raghavan, P.: Automatic subspace clustering of high dimensional data for data mining applications, Proc. of the 1998 ACM SIGMOD Int. Conf. on Management of Data, ACM Press, 1998, 94-105
• [2] Ester, M., Kriegel, H.-P., Sander, J., Xu, X.: A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise, Second Int. Conf. on Knowledge Discovery and Data Mining, AAAI Press, 1996, 226-231
• [3] Hinneburg, A., Keim, D. A.: An Efficient Approach to Clustering in Large Multimedia Databases with Noise, Knowledge Discovery and Data Mining, 1998, 58-65
• [4] Hinneburg, A., Keim, D. A.: Optimal Grid-Clustering: Towards Breaking the Curse of Dimensionality in High-Dimensional Clustering, Proc. of the 25th Int. Conf. on Very Large Data Bases, Morgan Kaufmann Publishers Inc., 1999, 506-517
• [5] Kailing, K., Kriegel, H. P., Kroger, P.: Density-Connected Subspace Clustering for High-Dimensional Data, Proc. 4th SIAM Int. Conf. on Data Mining, IEEE Computer Society, 2004, 246-256
• [6] Lai, J. Z. C., Huang, T.-J., Liaw, Y.-C.: A fast k-means clustering algorithm using cluster center displacement, Pattern Recognition, 42/11, Elsevier Science Inc., 2009, 2551-2556
• [7] MacQueen, J. B.: Some Methods for Classification and Analysis of MultiVariate Observations, Proc. of the fifth Berkeley Symposium on Mathematical Statistics and Probability, 1, University of California Press, 1967, 281-297
• [8] Meil, M.: Comparing clusterings - an information based distance, Journal of Multivariate Analysis, 98, Academic Press, 2007, 873-895
• [9] Nagesh, H. S., Goil, S., Choudhary A.: Adaptive Grids for Clustering Massive Data Sets, In Proc. of SIAM Int. Conf. on Data Mining, 2001, 1-17
• [10] Orlandic, R., Lai, Y., Yee, W. G.: Clustering high-dimensional data using an efficient and effective data space reduction, Proc. of the 14th ACM Int. Conf. on Information and Knowledge Management, ACM, 2005, 201-208
• [11] Parsons, L., Haque, E., Liu, H.: Subspace clustering for high dimensional data: a review, SIGKDD Explorations Newsletter, 6, ACM, 2004, 90-105
• [12] Wang, W., Yang, J., Muntz, R. R.: STING: A Statistical Information Grid Approach to Spatial Data Mining, Proc. of the 23rd Int. Conf. on Very Large Data Bases, Morgan Kaufmann Publishers Inc., 1997, 186-195
• [13] Ward, J.: Hierarchical grouping to optimize an objective function, Journal of the American Statistical Association, 58, Journal of the American Statistical Association, 1963, 236-244
• [14] Yue, S., Wei, M., Wang, J.-S., Wang, H.: A general grid-clustering approach, Pattern Recognition Letter, 29, Elsevier Science Inc., 2008, 1372-1384
• [15] Ziembiński, R. Z.: Algorithms for Context Based Sequential Pattern Mining, Fundamenta Informaticae, 76/4, IOS Press, 2007, 495-510