An algorithm for multidimensional data clustering

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.

REFERENCES

• 1: Jon Louis Bentley, Multidimensional divide-and-conquer, Communications of the ACM, v.23 n.4, p.214-229, April 1980 [doi>10.1145/358841.358850]
• 2: Jon Louis Bentley , Jerome H. Friedman, Data Structures for Range Searching, ACM Computing Surveys (CSUR), v.11 n.4, p.397-409, Dec. 1979 [doi>10.1145/356789.356797]
• 3: DUDA, R. O., AND HART, P.E. Pattern Classification and Scene Analysis. Wiley, New York, 1973.
• 4: Jerome H. Freidman , Jon Louis Bentley , Raphael Ari Finkel, An Algorithm for Finding Best Matches in Logarithmic Expected Time, ACM Transactions on Mathematical Software (TOMS), v.3 n.3, p.209-226, Sept. 1977 [doi>10.1145/355744.355745]
• 5: HALL, E.L. Computer Image Processing and Recognition. Academic Press, New York, 1979.
• 6: John A. Hartigan, Clustering Algorithms, John Wiley & Sons, Inc., New York, NY, 1975
• 7: Paul Heckbert, Color image quantization for frame buffer display, ACM SIGGRAPH Computer Graphics, v.16 n.3, p.297-307, July 1982
• 8: HYAFIL, L., AND RIVEST, R.L. Construction optimal binary decision trees is NP-complete. In./. Process. Lett. 5 (May 1976), 15-17.
• 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,
• 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.
• 11: WAN, S. J., WONG, S, K. M., AND PRUSINKIEWICZ, P. Variance-based color image quantization for frame buffer display. Submitted for publication.
• 12: WON(~, S. K. M., WAN, S. J., AND PRUSINKIEWICZ, P. Monochrome image quantization. Submitted for publication.
• 13: Wu, X., AND WITTEN, }. H. A fast k-means type clustering algorithm. Dept. Computer Science, Univ. of Calgary, Canada, May 1985.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.3 Clustering
          Subjects: Algorithms

General Terms:
Algorithms, Performance