×

zbMATH — the first resource for mathematics

Cellular tree classifiers. (English) Zbl 1293.62067
Summary: The cellular tree classifier model addresses a fundamental problem in the design of classifiers for a parallel or distributed computing world: Given a data set, is it sufficient to apply a majority rule for classification, or shall one split the data into two or more parts and send each part to a potentially different computer (or cell) for further processing? At first sight, it seems impossible to define with this paradigm a consistent classifier as no cell knows the “original data size”, \(n\). However, we show that this is not so by exhibiting two different consistent classifiers. The consistency is universal but is only shown for distributions with nonatomic marginals.

MSC:
62G05 Nonparametric estimation
62G20 Asymptotic properties of nonparametric inference
62H30 Classification and discrimination; cluster analysis (statistical aspects)
68T10 Pattern recognition, speech recognition
Software:
C4.5
PDF BibTeX XML Cite
Full Text: DOI Euclid
References:
[1] A.C. Anderson and K.S. Fu. Design and development of a linear binary tree classifier for leukocytes. Technical Report TR-EE-79-31, Purdue University, 1979.
[2] P. Argentiero, R. Chin, and P. Beaudet. An automated approach to the design of decision tree classifiers. IEEE Transactions on Pattern Analysis and Machine Intelligence , 4:51-57, 1982.
[3] A. Arora, P. Dutta, S. Bapat, V. Kulathumani, H. Zhang, V. Naik, V. Mittal, H. Cao, M. Demirbas, M. Gouda, Y. Choi, T. Herman, S. Kulkarni, U. Arumugam, M. Nesterenko, A. Vora, and M. Miyashita. A line in the sand: A wireless sensor network for target detection, classification, and tracking. Computer Networks , 46:605-634, 2004.
[4] L.A. Bartolucci, P.H. Swain, and C. Wu. Selective radiant temperature mapping using a layered classifier. IEEE Transactions on Geosciences and Electronics , 14:101-106, 1976.
[5] J.L. Bentley. Multidimensional binary search trees used for associative searching. Communications of the ACM , 18:509-517, 1975. · Zbl 0306.68061 · doi:10.1145/361002.361007
[6] G. Biau, L. Devroye, and G. Lugosi. Consistency of random forests and other averaging classifiers. Journal of Machine Learning Research , 9:2015-2033, 2008. · Zbl 1225.62081 · www.jmlr.org
[7] L. Breiman. Random forests. Machine Learning , 45:5-32, 2001. · Zbl 1007.68152 · doi:10.1023/A:1010933404324
[8] L. Breiman, J.H. Friedman, R.A. Olshen, and C.J. Stone. Classification and Regression Trees . Chapman & Hall, New York, 1984. · Zbl 0541.62042
[9] X. Cheng, J. Xu, J. Pei, and J. Liu. Hierarchical distributed data classification in wireless sensor networks. Computer Communications , 33:1404-1413, 2010.
[10] P.A. Chou. Optimal partitioning for classification and regression trees. IEEE Transactions on Pattern Analysis and Machine Intelligence , 13:340-354, 1991.
[11] T.H. Cormen, C.E. Leiserson, R.L. Rivest, and C. Stein. Introduction to Algorithms. Third Edition . The MIT Press, Cambridge, 2009. · Zbl 1187.68679
[12] T.M. Cover and J.A. Thomas. Elements of Information Theory. Second Edition . Wiley, New York, 2006. · Zbl 1140.94001
[13] H.A. David and H.N. Nagaraja. Order Statistics. Third Edition . Wiley, Hoboken, 2003. · Zbl 1053.62060
[14] L. Devroye, L. Györfi, and G. Lugosi. A Probabilistic Theory of Pattern Recognition . Springer, New York, 1996. · Zbl 0853.68150
[15] M. Drmota. Random Trees . Springer, Vienna, 2009. · Zbl 1170.05022
[16] H. Edelsbrunner and J. van Leeuwen. Multidimensional data structures and algorithms: A bibliography. Technical Report F104, Technische Universität Graz, 1983.
[17] P. Flajolet and R. Sedgewick. Analytic Combinatorics . Cambridge University Press, Cambridge, 2008. · Zbl 1165.05001
[18] J.H. Friedman. A tree-structured approach to nonparametric multiple regression. In T. Gasser and M. Rosenblatt, editors, Smoothing Techniques for Curve Estimation , pages 5-22, Heidelberg, 1979. Lecture Notes in Mathematics #757, Springer. · Zbl 0415.62046
[19] S.B. Gelfand and E.J. Delp. On tree structured classifiers. In I.K. Sethi and A.K. Jain, editors, Artificial Neural Networks and Statistical Pattern Recognition, Old and New Connections , pages 71-88, Amsterdam, 1991. Elsevier Science Publishers.
[20] S.B. Gelfand, C.S. Ravishankar, and E.J. Delp. An iterative growing and pruning algorithm for classification tree design. IEEE Transactions on Pattern Analysis and Machine Intelligence , 13:163-174, 1991.
[21] S. Gey and E. Nédélec. Model selection for CART regression trees. IEEE Transactions on Information Theory , 51:658-670, 2005. · Zbl 1301.62064
[22] L. Gordon and R.A. Olshen. Asymptotically efficient solutions to the classification problem. The Annals of Statistics , 6:515-533, 1978. · Zbl 0437.62056 · doi:10.1214/aos/1176344197
[23] H. Guo and S.B. Gelfand. Classification trees with neural network feature extraction. IEEE Transactions on Neural Networks , 3:923-933, 1992.
[24] D.E. Gustafson, S. Gelfand, and S.K. Mitter. A nonparametric multiclass partitioning method for classification. In Proceedings of the Fifth International Conference on Pattern Recognition , pages 654-659, 1980.
[25] L. Györfi, M. Kohler, A. Krzyżak, and H. Walk. A Distribution-Free Theory of Nonparametric Regression . Springer, New York, 2002. · Zbl 1021.62024
[26] C.R.P. Hartmann, P.K. Varshney, K.G. Mehrotra, and C.L. Gerberich. Application of information theory to the construction of efficient decision trees. IEEE Transactions on Information Theory , 28:565-577, 1982. · Zbl 0483.68064 · doi:10.1109/TIT.1982.1056522
[27] M.I. Jordan. A message from the President: The era of big data. ISBA Bulletin , 18:1-3, 2011.
[28] M.W. Kurzynski. The optimal strategy of a tree classifier. Pattern Recognition , 16:81-87, 1983. · Zbl 0508.62053 · doi:10.1016/0031-3203(83)90011-0
[29] Y.K. Lin and K.S. Fu. Automatic classification of cervical cells using a binary tree classifier. Pattern Recognition , 16:69-80, 1983.
[30] W.Y. Loh and N. Vanichsetakul. Tree-structured classification via generalized discriminant analysis. Journal of the American Statistical Association , 83:715-728, 1988. · Zbl 0649.62055 · doi:10.2307/2289295
[31] K. Mehlhorn. Data Structures and Algorithms 3: Multi-dimensional Searching and Computational Geometry . Springer, Berlin, 1984. · Zbl 0556.68003
[32] W.S. Meisel and D.A. Michalopoulos. A partitioning algorithm with application in pattern classification and the optimization of decision trees. IEEE Transactions on Computers , 22:93-103, 1973. · Zbl 0248.68043 · doi:10.1109/T-C.1973.223603
[33] J.K. Mui and K.S. Fu. Automated classification of nucleated blood cells using a binary tree classifier. IEEE Transactions on Pattern Analysis and Machine Intelligence , 2:429-443, 1980.
[34] M.H. Overmars and J. van Leeuwen. Dynamic multi-dimensional data structures based on quad- and \(k\)-\(d\) trees. Acta Informatica , 17:265-287, 1982. · Zbl 0489.68055 · doi:10.1007/BF00264354
[35] Y. Park and J. Sklansky. Automated design of linear tree classifiers. Pattern Recognition , 23:1393-1412, 1990.
[36] H.J. Payne and W.S. Meisel. An algorithm for constructing optimal binary decision trees. IEEE Transactions on Computers , 26:905-916, 1977. · Zbl 0363.68131 · doi:10.1109/TC.1977.1674938
[37] J. Pearl. Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference . Morgan Kaufmann Publishers, San Mateo, 1988. · Zbl 0746.68089
[38] S. Qing-Yun and K.S. Fu. A method for the design of binary tree classifiers. Pattern Recognition , 16:593-603, 1983. · Zbl 0534.62042 · doi:10.1016/0031-3203(83)90076-6
[39] J.R. Quinlan. Induction of decision trees. Machine Learning , 1:81-106, 1986.
[40] J.R. Quinlan. C4.5: Programs for Machine Learning . Morgan Kaufmann Publishers, San Mateo, 1993.
[41] L. Rokach and O. Maimon. Data Mining with Decision Trees: Theory and Applications . World Scientific, Singapore, 2008. · Zbl 1154.68098
[42] H. Samet. The quadtree and related hierarchical data structures. Computing Surveys , 16:187-260, 1984.
[43] H. Samet. The Design and Analysis of Spatial Data Structures . Addison-Wesley, Reading, 1990. · Zbl 0719.90022
[44] I.K. Sethi and B. Chatterjee. Efficient decision tree design for discrete variable pattern recognition problems. Pattern Recognition , 9:197-206, 1977. · Zbl 0383.68070 · doi:10.1016/0031-3203(77)90004-8
[45] S. Shlien. Multiple binary decision tree classifiers. Pattern Recognition , 23:757-763, 1990.
[46] H.U. Simon. The Vapnik-Chervonenkis dimension of decision trees with bounded rank. Information Processing Letters , 39:137-141, 1991. · Zbl 0735.68072 · doi:10.1016/0020-0190(91)90109-U
[47] C.Y. Suen and Q.R. Wang. Large tree classifier with heuristic search and global training. IEEE Transactions on Pattern Analysis and Machine Intelligence , 9:91-101, 1987.
[48] P.H. Swain and H. Hauska. The decision tree classifier: Design and potential. IEEE Transactions on Geosciences and Electronics , 15:142-147, 1977.
[49] Q.R. Wang and C.Y. Suen. Analysis and design of a decision tree based on entropy reduction and its application to large character set recognition. IEEE Transactions on Pattern Analysis and Machine Intelligence , 6:406-417, 1984. · Zbl 0548.68087 · doi:10.1109/TPAMI.1984.4767546
[50] K.C. You and K.S. Fu. An approach to the design of a linear binary tree classifier. In Proceedings of the Symposium of Machine Processing of Remotely Sensed Data , pages 3A-1-10, West Lafayette, 1976. Purdue University.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.