Consistency of data-driven histogram methods for density estimation and classification. (English) Zbl 0859.62040

Summary: We present general sufficient conditions for the almost sure \(L_1\)-consistency of histogram density estimates based on data-dependent partitions. Analogous conditions guarantee the almost-sure risk consistency of histogram classification schemes based on data-dependent partitions. Multivariate data are considered throughout.
In each case, the desired consistency requires shrinking cells, subexponential growth of a combinatorial complexity measure and sublinear growth of the number of cells. It is not required that the cells of every partition be rectangles with sides parallel to the coordinate axis or that each cell contains a minimum number of points. No assumptions are made concerning the common distribution of the training vectors.
We apply the results to establish the consistency of several known partitioning estimates, including the \(k_n\)-spacing density estimate, classifiers based on statistically equivalent blocks and classifiers based on multivariate clustering schemes.


62G07 Density estimation
62H30 Classification and discrimination; cluster analysis (statistical aspects)
62G20 Asymptotic properties of nonparametric inference
Full Text: DOI


[1] ANDERSON, T. W. 1966. Some nonparametric multivariate procedures based on statistically Z. equivalent blocks. In Multivariate Analy sis P. R. Krishnaiah, ed. 5 27. Academic Press, New York. Z. · Zbl 0245.62054
[2] BREIMAN, L., FRIEDMAN, J. H., OLSHEN, R. A. and STONE, C. J. 1984. Classification and Regression Trees. Wadsworth, Belmont, CA. Z. · Zbl 0541.62042
[3] CHEN, X. R. and ZHAO, L. C. 1987. Almost sure L -norm convergence for data-based histogram 1 density estimates. J. Multivariate Anal. 21 179 188. Z. · Zbl 0614.62044
[4] COVER, T. M. 1965. Geometrical and statistical properties of sy stems of linear inequalities with applications in pattern recognition. IEEE Transactions on Electronic Computers 14 326 334. Z. · Zbl 0152.18206
[5] CSISZAR, I. and KORNER, J. 1981. Information Theory: Coding Theorems for Discrete Memory\' \" less Sy stems. Academic Press, New York.
[6] DEVROy E, L. 1988. Automatic pattern recognition: a study of the probability of error. IEEE Transactions on Pattern Analy sis and Machine Intelligence 10 530 543. Z. · Zbl 0661.62056
[7] DEVROy E, L. and Gy ORFI, L. 1983. Distribution-free exponential bound on the L error of \" 1 partitioning estimates of a regression function. In Proceedings of the Fourth PannonZ ian Sy mposium on Mathematical Statistics F. Konecny, J. Mogy orodi and W. Wertz, \'. eds. 67 76. Akademiai Kiado, Budapest, Hungary. \' Ź. · Zbl 0607.62040
[8] DEVROy E, L. and Gy ORFI, L. 1985. Nonparametric Density Estimation: The L View. Wiley, New \" 1 York. Z. · Zbl 0546.62015
[9] GERSHO, A. and GRAY, R. M. 1992. Vector Quantization and Signal Compression. Kluwer, Boston.Z. · Zbl 0782.94001
[10] GESSAMAN, M. P. 1970. A consistent nonparametric multivariate density estimator based on statistically equivalent blocks. Ann. Math. Statist. 41 1344 1346. Z. · Zbl 0203.51502
[11] GORDON, L. and OLSHEN, R. A. 1978. Asy mptotically efficient solutions to the classification problem. Ann. Statist. 6 515 533. Z. · Zbl 0437.62056
[12] GORDON, L. and OLSHEN, R. A. 1980. Consistent nonparametric regression from recursive partitioning schemes. J. Multivariate Anal. 10 611 627. Z. · Zbl 0453.62035
[13] GORDON, L. and OLSHEN, R. 1984. Almost surely consistent nonparametric regression from recursive partitioning schemes. J. Multivariate Anal. 15 147 163. Z. · Zbl 0542.62032
[14] HARTIGAN, J. A. 1975. Clustering Algorithms. Wiley, New York. Z. · Zbl 0372.62040
[15] LINDER, T., LUGOSI, G. and ZEGER, K. 1994. Rates of convergence in the source coding theorem, empirical quantizer design, and universal lossy source coding. IEEE Trans. Inform. Theory 40 1728 1740. Z. · Zbl 0826.94006
[16] LUGOSI, G. and NOBEL, A. B. 1993. Consistency of data-driven histogram methods for density estimation and classification. Technical Report UIUC-BI-93-01, Beckman Institute, Univ. Illinois, Urbana Champaign. Z. · Zbl 0859.62040
[17] MAHALANOBIS, P. C. 1961. A method of fractile graphical analysis. Sankhy a Ser. A 23 41 64. Z. · Zbl 0097.34905
[18] NOBEL, A. 1995. Recursive partitioning to reduce distortion. Technical Report UIUC-BI-95-01, Beckman Institute, Univ. Illinois, Urbana Champaign. Z. · Zbl 0878.94041
[19] NOBEL, A. 1996. Histogram regression estimation using data-dependent partitions. Ann. Statist. Z. 24 3. Z. · Zbl 0862.62038
[20] PARTHASARATHY, K. R. and BHATTACHARy A, P. K. 1961. Some limit theorems in regression theory. Sankhy a Ser. A 23 91 102. Z. · Zbl 0097.34903
[21] PATRICK, E. A. and FISHER, F. P., II 1967. Introduction to the performance of distribution-free conditional risk learning sy stems. Technical Report TR-EE-67-12, Purdue Univ. Z.
[22] POLLARD, D. 1984. Convergence of Stochastic Processes. Springer, New York. Z. · Zbl 0544.60045
[23] STONE, C. J. 1977. Consistent nonparametric regression. Ann. Statist. 5 595 645. Z. · Zbl 0366.62051
[24] STONE, C. J. 1985. An asy mptotically optimal histogram selection rule. In Proc. Berkeley Conf. Z. in Honor of Jerzy Ney man and Jack Kiefer L. Le Cam and R. A. Olshen, eds. 2 513 520. Wadsworth, Belmont, CA. Z.
[25] VAN Ry ZIN, J. 1973. A histogram method of density estimation. Communications in Statistics 2 493 506. Z. · Zbl 0283.62040
[26] VAPNIK, V. N. and CHERVONENKIS, A. YA. 1971. On the uniform convergence of relative frequencies of events to their probabilities. Theory Probab. Appl. 16 264 280. Z. · Zbl 0247.60005
[27] ZHAO, L. C., KRISHNAIAH, P. R. and CHEN, X. R. 1990. Almost sure L -norm convergence for r data-based histogram estimates. Theory Probab. Appl. 35 396 403. · Zbl 0721.62037
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.