On a Method of Multivariate Density Estimate Basedon Nearest Neighbours Graphs

Cover Page


A method of multivariate density estimation based on the reweighted nearest neighbours,mimicking the natural neighbours techniques, is presented. Estimation of multivariate densityis important for machine learning, astronomy, biology, physics and econometrics. A 2-additivefuzzy measure is constructed based on proxies for pairwise interaction indices. The neighboursof a point lying in nearly the same direction are treated as redundant, and the contributionof the farthest neighbour is transferred to the nearer neighbour. The calculation of the localpoint density estimate is performed by the discrete Choquet integral, so that the contributionsof the neighbours all around that point are accounted for. This way an approximation to theSibson’s natural neighbours is computed. The method relieves the computational burden of theDelaunay tessellation-based natural neighbours approach in higher dimensions, whose complexityis exponential in the dimension of the data. This method is suitable for density estimates ofstructured data (possibly lying on lower dimensional manifolds), as the nearest neighbours differsignificantly from the natural neighbours in this case.

Gleb Beliakov

Principal contact for editorial correspondence.
Deakin University 221 Burwood Hwy, Burwood 3125, Australia

Beliakov Gleb - professor, Candidate of Physical and Mathematical Sciences, professor of School of Information Technology of Deakin University, Australia

  • D. W. Scott, Multivariate Density Estimation, John Wiley and Sons, New York, 2015.
  • G. Beliakov, M. King, Density Based Fuzzy C-Means Clustering of Non-Convex Patterns, Europ. J. Oper. Res. 173 (2006) 717–728.
  • P. Angelov, R. R. Yager, Density-Based Averaging — a New Operator for Data Fusion, Information Sciences 222 (2013) 163–174.
  • G. Beliakov, T. Wilkin, On Some Properties of Weighted Averaging with Variable Weights, Information Sciences 281 (2014) 1–7.
  • E. Parzen, On the Estimation of a Probability Density Function and the Mode, Annals of Math. Stats. 33 (1962) 1065–1076.
  • C. Abraham, G. Biau, B. Cadre, Simple Estimation of the Mode of a Multivariate Density, The Canadian Journal of Statistics 31 (2003) 23–34.
  • W. E. Schaap, R. van de Weygaert, Continuous Fields and Discrete Samples: Reconstruction Through Delaunay Tessellations, Astronomy and Astrophysics 363 (2000) L29–L32.
  • E. Schubert, J. Sander, M. Ester, H. P. Kriegel, X. Xu, DBSCAN Revisited, Revisited: Why and How You Should (Still) Use DBSCAN, ACM Trans. Database Syst. 42 (2017) 19:1–19:21. doi: 10.1145/3068335.
  • N.-B. Heidenreich, A. Schindler, S. Sperlich, Bandwidth Selection for Kernel Density Estimation: a Review of Fully Automatic Selectors, AStA Adv. Stat. 97 (2013) 403–433.
  • G. Voronoi, Nouvelles applications des parametres continus a la theorie des formes quadratiques, Journal fur die Reine und Angewandte Mathematik 133 (1908) 97–178.
  • B. Delaunay, Sur la sph`ere vide, Bulletin de l’Academie des Sciences de l’URSS, Classe des sciences mathematiques et naturelles 6 (1934) 793–800.
  • R. Sibson, Brief Description of Natural Neighbor Interpolation, in: V. Barnett (Ed.), Interpreting Multivariate Data, John Wiley and Sons, New York, 1981, pp. 21–36.
  • W. Stuetzle, Estimating the Cluster Tree of a Density by Analyzing the Minimal Spanning Tree of a Sample, Journal of Classification 20 (2003) 25–47.
  • H. Samet, Foundations of Multidimensional and Metric Data Structures, Elsevier, Boston, 2006.
  • T. Hastie, R. Tibshirani, J. Friedman, The Elements of Statistical Learning, Springer- Verlag, New York, Berlin, Heidelberg, 2001.
  • B. Dasarathy, Nearest Neighbor Norms: NN Pattern Classification Techniques, IEEE Computer Society Press, Los Alamitos, CA, 1991.
  • S. Cost, S. Salzberg, A Weighted Nearest Neighbor Algorithm for Learning with Symbolic Features, Machine Learning 10 (1993) 57–78.
  • R. Yager, Using Fuzzy Methods to Model Nearest Neighbor Rules, IEEE Trans. on Syst., Man, and Cybernetics 32 (2002) 512–525.
  • E. H¨ullermeier, The Choquet-Integral as an Aggregation Operator in Case-Based Learning, in: B. Reusch (Ed.), Computational Intelligence, Theory and Applications, Springer, Berlin, Heidelberg, 2006, pp. 615–627.
  • D. Watson, Contouring: A Guide to the Analysis and Display of Spatial Data, Pergamon Press, Oxford, 1992.
  • J.-D. Boissonnat, F. Cazals, Smooth Surface Reconstruction Via Natural Neighbour Interpolation of Distance Functions, Proc. of the 16th Annual Symposium on Computational Geometry (2000) 223–232.
  • V. V. Belikov, V. D. Ivanov, V. K. Kontorovich, S. A. Korytnik, A. Y. Semenov, The Non-Sibsonian Interpolation: a New Method of Interpolation of the Values of a Function on an Arbitrary Set of Points, Computational Mathematics and Mathematical Physics 37 (1997) 9–15.
  • G. Beliakov, A. Pradera, T. Calvo, Aggregation Functions: A Guide for Practitioners, Springer, Heidelberg, 2007.
  • M. Grabisch, J.-L. Marichal, R. Mesiar, E. Pap, Aggregation Functions, Cambridge University press, Cambridge, 2009.
  • M. Grabisch, T. Murofushi, M. Sugeno (Eds.), Fuzzy Measures and Integrals. Theory and Applications, Physica-Verlag, Heidelberg, 2000.
  • M. Grabisch, k-Order Additive Discrete Fuzzy Measures and Their Representation, Fuzzy Sets and Systems 92 (1997) 167–189.
  • B. Mayag, M. Grabisch, C. Labreuche, A Characterization of the 2-additive Choquet Integral, in: Proc. of IPMU, Malaga, Spain, 2008, pp. 1512–1518.
  • J. W. Harris, H. Stocker, Spherical Segment (Spherical Cap), in: Handbook of Mathematics and Computational Science, Springer, New York, 1998.


Abstract - 39

PDF (English) - 6

Copyright (c) 2018 Beliakov G.

Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.