Naive Bayes for value difference metric

Abstract

The value difference metric (VDM) is one of the best-known and widely used distance functions for nominal attributes. This work applies the instanceweighting technique to improveVDM. An instance weighted value difference metric (IWVDM) is proposed here. Different from prior work, IWVDM uses naive Bayes (NB) to find weights for training instances. Because early work has shown that there is a close relationship between VDM and NB, some work on NB can be applied to VDM. The weight of a training instance x, that belongs to the class c, is assigned according to the difference between the estimated conditional probability \widehat{P}(c|x) by NB and the true conditional probability P(c|x), and the weight is adjusted iteratively. Compared with previous work, IWVDM has the advantage of reducing the time complexity of the process of finding weights, and simultaneously improving the performance of VDM. Experimental results on 36 UCI datasets validate the effectiveness of IWVDM.

Keywords

value difference metric / instance weighting / naive Bayes / distance-based learning algorithms

References

[1] CoverT M, HartP E. Nearest neighbor pattern classification. IEEE Transactions on Information Theory, 1967, 13: 21-27

[2] AhaD, KiblerD, AlbertMK. Instance-based learning algorithms. Machine Learning, 1991, 6: 37-66

[3] DomingosP. Rule induction and instance-based learning: a unified approach. In: Proceedings of the 14th International Joint Conference on Artificial Intelligence. 1995, 1226-1232

[4] FrankE, HallM, PfahringerB. Locally weighted naive bayes. In: Proceedings of the 19th Conference on Uncertainty in Artificial Intelligence. 2003, 249-256

[5] MitchellT M. Machine Learning, 1st edition. McGraw-Hill, 1997

[6] TanP N, SteinbachM, KumarV. Introduction to Data Mining, 1st edition. Pearson Education, 2006

[7] StanfillC, WaltzD. Toward memory-based reasoning. Communications of the ACM, 1986, 29: 1213-1228

[8] ShortR D, FukunagaK. The optimal distance measure for nearest neighbour classification. IEEE Transactions on Information Theory, 1981, 27: 622-627

[9] MylesJ P, HandD J. The multi-class metric problem in nearest neighbour discrimination rules. Pattern Recognition, 1990, 23: 1291-1297

[10] CostS, SalzbergS. A weighted nearest neighbor algorithm for learning with symbolic features. Machine Learning, 1993, 10: 57-78

[11] WilsonD R, MartinezT R. Improved heterogeneous distance functions. Journal of Artificial Intelligence Research, 1997, 6: 1-34

[12] LiC, LiH. One dependence value difference metric. Knowledge-Based Systems, 2011, 24: 589-594

[13] JiangL, LiC. An augmented value difference measure. Pattern Recognition Letters, 2013, 34: 1169-1174

[14] DerracJ, TrigueroI, GarcíaS, HerreraF. Integrating instance selection, instance weighting, and feature weighting for nearest neighbor classifiers by coevolutionary algorithms. IEEE Transactions On Systems, Man, and Cybernetics-Part B: Cybernetics, 2012, 42: 1383-1397

[15] García-PedrajasN. Constructing ensembles of classifiers by means of weighted instance selection. IEEE Transactions On Neural Network, 2009, 20: 258-277

[16] JahromiM Z, ParvinniaE, JohnR. A method of learning weighted similarity function to improve the performance of nearest neighbor. Information Sciences, 2009, 179: 2964-2973

[17] WangJ, NeskovicP, CooperL. Improving nearest neighbor rule with a simple adaptive distance measure. Pattern Recognition Letters, 2007, 28: 207-213

[18] KasifS, SalzbergS, WaltzD, RachlinD J. A. A probabilistic framework for memory-based reasoning. Artificial Intelligence, 1998, 104: 287-311

[19] TianY, ShiY, LiuX. Recent advances on support vector machines research. Technological and Economic Development of Economy, 2012, 18: 5-33

[20] QiZ, TianY, ShiY. Laplacian twin support vector machine for semisupervised classification. Neural Networks, 2012, 35: 46-53

[21] QiZ, TianY, ShiY. Structural twin support vector machine for classification. Knowledge-Based Systems, 2013, 43: 74-81

[22] Saar-TsechanskyM, ProvostF. Active sampling for class probability estimation and ranking. Machine Learning, 2004, 54: 153-178

[23] JiangL, ZhangH. Learning naive bayes for probability estimation by feature selection. In: Proceedings of the 19th Canadian Conference on Artificial Intelligence. 2006, 503-514

[24] GrossmanD, DomingosP. Learning bayesian network classifiers by maximizing conditional likelihood. In: Proceedings of the 21st International Conference on Machine Learning. 2004, 361-368

[25] LowdD, DomingosP. Naive bayes models for probability estimation. In: Proceedings of the 22nd International Conference on Machine Learning. 2005, 529-536

[26] HallM. A decision tree-based attribute weighting filter for naive bayes. Knowledge-Based Systems, 2007, 20: 120-126

[27] WittenI H, FrankE. Data Mining: Practical Machine Learning Tools and Techniques, 2nd edition. San Francisco: Morgan Kaufmann, 2005

[28] WilsonD, MartinezT. Reduction techniques for exemplar-based learning algorithms. Machine Learning, 2000, 38: 257-286

[29] BrightonH, MellishC. Advances in instance selection for instancebased learning algorithms. Data Mining and Knowledge Discovery, 2002, 6: 153-172

[30] ParedesR, VidalE. Learning prototypes and distances: a prototype reduction technique based on nearest neighbor error minimization. Pattern Recognition, 2006, 39: 180-188

[31] GarcíaS, DerracJ, CanoJ R, HerreraF. Prototype selection for nearest neighbor classification: taxonomy and empirical study. IEEE Transactions On Pattern Analaysis and Machine Intelligence, 2012, 34: 417-435

[32] TrigueroI, DerracJ, GarcíaS, HerreraF. A taxonomy and experimental study on prototype generation for nearest neighbor classification. IEEE Transactions On Systems, Man, and Cybernetics, Part C: Applications and Reviews, 2012, 42: 86-100

[33] WuX, KumarV, QuinlanJ R, GhoshJ, YangQ, MotodaH, MclachlanG J, NgA, LiuB, YuP S, ZhouZ H, SteinbachM, HandD J, SteinbergD. Top 10 algorithms in data mining. Knowledge and Information Systems, 2008, 14: 1-37

[34] JiangL, WangD, CaiZ. Discriminatively weighted naive bayes and its application in text classification. International Journal on Artificial Intelligence Tools, 2012, 21(1): 1250007:1-1250007:19

[35] HallM A. Correlation-based feature selection for discrete and numeric class machine learning. In: Proceedings of the 17th International Conference on Machine Learning. 2000, 359-366

[36] JiangL, ZhangH, CaiZ. A novel bayes model: hidden naive bayes. IEEE Transactions on Knowledge and Data Engineering, 2009, 21: 1361-1371

[37] NadeauC, BengioY. Inference for the generalization error. Machine Learning, 2003, 52: 239-281

[38] KurganL A, CiosK J, TadeusiewiczR, OgielaM, GoodendayL S. Knowledge discovery approach to automated cardiac spect diagnosis. Artificial Intelligence in Medicine, 2001, 23: 149-169

RIGHTS & PERMISSIONS

Higher Education Press and Springer-Verlag Berlin Heidelberg