S. J. Wan
Abstract
A new divisive algorithm for multidimensional data clustering is suggested. Based on the minimization of the sum-of-squared-errors, the proposed method produces much smaller quantization errors than the median-cut and mean-split algorithms. It is also observed that the solutions obtained from our algorithm are close to the local optimal ones derived by the k-means iterative procedure.
- 1 BENTLEY, J. L. Multidimensional divide-and-conquer. Commun. ACM 23, 4 (Apr. 1980), 214-229. Google Scholar
- 2 BENTLEY, J. L., AND FRIEMAN, J.H. Data structure for range searching. A CM Comput. Surv. 11, 4 (Dec. 1979), 397-409. Google Scholar
- 3 DUDA, R. O., AND HART, P.E. Pattern Classification and Scene Analysis. Wiley, New York, 1973.Google Scholar
- 4 FRIEMAN, J. H., BENTLEY, J. L., AND FINKEL, R.A. An algorithm for finding best matches in logarithmic expected time. ACM Trans. Math. So{tw. 3, 3 (Sept. 1977), 209-226. Google Scholar
- 5 HALL, E.L. Computer Image Processing and Recognition. Academic Press, New York, 1979.Google Scholar
- 6 HARTIGAN, J.A. Clustering Algorithms. Wiley, New York, 1975. Google Scholar
- 7 HECKBERT, P. Color image quantization for frame buffer display. ACM Trans. Comput. Gr. 16, 3 (July 1982), 297-307. Google Scholar
- 8 HYAFIL, L., AND RIVEST, R.L. Construction optimal binary decision trees is NP-complete. In./. Process. Lett. 5 (May 1976), 15-17.Google Scholar
- 9 MACQUEEN, J.B. Some methods for classification and analysis of multivariate observations. In Proceedings of the 5th Berkley Symposium on Mathematical Statistics and Probability I (1967), 281-297,Google Scholar
- 10 SELIM, S, Z., AND ISMAIL, M.A. K-means-type algorithms: A generalized convergence theorem and characterization of local optimality. IEEE Trans. Pattern Anal. Mach. Intell. PAMI-6, 1 (1984), 81-87.Google Scholar
- 11 WAN, S. J., WONG, S, K. M., AND PRUSINKIEWICZ, P. Variance-based color image quantization for frame buffer display. Submitted for publication.Google Scholar
- 12 WON(~, S. K. M., WAN, S. J., AND PRUSINKIEWICZ, P. Monochrome image quantization. Submitted for publication.Google Scholar
- 13 Wu, X., AND WITTEN, }. H. A fast k-means type clustering algorithm. Dept. Computer Science, Univ. of Calgary, Canada, May 1985.Google Scholar
Index Terms
- An algorithm for multidimensional data clustering
Recommendations
Hybrid Bisect K-Means Clustering Algorithm
BCGIN '11: Proceedings of the 2011 International Conference on Business Computing and Global InformatizationIn this paper, we present a hybrid clustering algorithm that combines divisive and agglomerative hierarchical clustering algorithm. Our method uses bisect K-means for divisive clustering algorithm and Unweighted Pair Group Method with Arithmetic Mean (...
Improvement in k-Means Clustering Algorithm Using Data Clustering
ICCUBEA '15: Proceedings of the 2015 International Conference on Computing Communication Control and AutomationThe set of objects having same characteristics are organized in groups and clusters of these objects reformed known as Data Clustering. It is an unsupervisedlearning technique for classification of data. K-means algorithm is widely used and famous ...
Multidimensional Discrete Big Data Clustering Algorithm Based on Dynamic Grid
Traditionally, the data clustering algorithm is lack of comprehensive performance, leading to low clustering purity and long clustering time. In addition, the consistency between the clustering results and the original data distribution is not strong. ...
Reviews
Florian Petrescu
The authors introduce a new and promising multivariate data clustering algorithm. They adopt a divisive strategy, that is, a procedure that partitions the input data space sequentially into a number of disjoint subregions. After reviewing several well-known clustering techniques, namely the median-cut, mean-split, and k-means algorithms, they present their method. The clustering algorithm has to make two important decisions at each step while partitioning the input data space: first, which hyperbox should be partitioned and, second, which hyperplane is appropriate to subdivide the hyperbox. Both decisions are based on minimizing the sum-of-squared-errors. Finally, the paper compares the performance of the algorithm and the above-mentioned clustering techniques on three collections of data of different dimensions from a color image database. The new clustering algorithm seems to perform better than the previously known methods.
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments