Density Estimation Using Optimally Quantized Histograms

摘要

The paper derives a method for obtaining an optimal histogram estimate of a multivariate probability density function. In an optimal histogram, the location, shape and size of each of the bins for the histogram are chosen to minimize the integrated mean square error of the density estimate. The mean square error is shown to be the sum of a variance term, which is proportional to the number of bins in the histogram divided by the sample size used for the estimate, and a bias term, which depends on the number of histogram bins and on their location, shape and size. The bias can be expressed as a weighted Euclidean distance, with weighting matrix equal to the outer product of the gradient of the density. It shows that a local minimum of the bias term can be obtained with the k-means clustering algorithm used in vector quantization. Thus the optimal histogram is formed by vector quantizing the feature vector using the weighted Euclidean distortion measure, and estimating the value of the density on the resulting quantization regions. The optimal number of bins for the density estimate is determined by minimizing an approximation to the integrated mean square error of the estimate, and is expressed in terms of the sample size and number of features. (Copyright (c) 1989 Xerox Corporation.)