Naive Bayes has distinct requirements of discretization due to its attribute independence assumption. This work provides theoretical analysis of those requirements and new techniques that improve classification accuracy.
PKIDiscretize is a standard Weka component that implements our proportional k-interval discretization technique.
Publications
Martinez, A.; Webb, G. I.; Flores, M.; Gamez, J.
Non-Disjoint Discretization for Aggregating One-Dependence Estimator Classifiers
Proceedings of the 7th International Conference on Hybrid Artificial Intelligent Systems, pp. 151-162, Springer, Berlin / Heidelberg, 2012, ISBN: 978-3-642-28930-9.
@inproceedings{MartinezEtAl12,
title = {Non-Disjoint Discretization for Aggregating One-Dependence Estimator Classifiers},
author = {A. Martinez and G. I. Webb and M. Flores and J. Gamez},
isbn = {978-3-642-28930-9},
year = {2012},
date = {2012-01-01},
booktitle = {Proceedings of the 7th International Conference on Hybrid Artificial Intelligent Systems},
pages = {151-162},
publisher = {Springer},
address = {Berlin / Heidelberg},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
Liu, B.; Yang, Y.; Webb, G. I.; Boughton, J.
Proceedings of the 13th Pacific-Asia Conference, PAKDD 2009, pp. 302-313, Springer, Bangkok, Thailand, 2009.
@inproceedings{LiuYangWebbBoughton09,
title = {A Comparative Study of Bandwidth Choice in Kernel Density Estimation for Naive Bayesian Classification},
author = {B. Liu and Y. Yang and G. I. Webb and J. Boughton},
doi = {10.1007/2F978-3-642-01307-2_29},
year = {2009},
date = {2009-01-01},
booktitle = {Proceedings of the 13th Pacific-Asia Conference, PAKDD 2009},
pages = {302-313},
publisher = {Springer},
address = {Bangkok, Thailand},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
Yang, Y.; Webb, G. I.
Discretization for Naive-Bayes Learning: Managing Discretization Bias and Variance
Machine Learning, vol. 74, no. 1, pp. 39-74, 2009.
@article{YangWebb09,
title = {Discretization for Naive-Bayes Learning: Managing Discretization Bias and Variance},
author = {Y. Yang and G. I. Webb},
doi = {10.1007/s10994-008-5083-5},
year = {2009},
date = {2009-01-01},
journal = {Machine Learning},
volume = {74},
number = {1},
pages = {39-74},
publisher = {Springer},
address = {Netherlands},
abstract = {Quantitative attributes are usually discretized in Naive-Bayes learning. We establish simple conditions under which discretization is equivalent to use of the true probability density function during naive-Bayes learning. The use of different discretization techniques can be expected to affect the classification bias and variance of generated naive-Bayes classifiers, effects we name discretization bias and variance. We argue that by properly managing discretization bias and variance, we can effectively reduce naive-Bayes classification error. In particular, we supply insights into managing discretization bias and variance by adjusting the number of intervals and the number of training instances contained in each interval. We accordingly propose proportional discretization and fixed frequency discretization, two efficient unsupervised discretization methods that are able to effectively manage discretization bias and variance. We evaluate our new techniques against four key discretization methods for naive-Bayes classifiers. The experimental results support our theoretical analyses by showing that with statistically significant frequency, naive-Bayes classifiers trained on data discretized by our new methods are able to achieve lower classification error than those trained on data discretized by current established discretization methods.},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
Quantitative attributes are usually discretized in Naive-Bayes learning. We establish simple conditions under which discretization is equivalent to use of the true probability density function during naive-Bayes learning. The use of different discretization techniques can be expected to affect the classification bias and variance of generated naive-Bayes classifiers, effects we name discretization bias and variance. We argue that by properly managing discretization bias and variance, we can effectively reduce naive-Bayes classification error. In particular, we supply insights into managing discretization bias and variance by adjusting the number of intervals and the number of training instances contained in each interval. We accordingly propose proportional discretization and fixed frequency discretization, two efficient unsupervised discretization methods that are able to effectively manage discretization bias and variance. We evaluate our new techniques against four key discretization methods for naive-Bayes classifiers. The experimental results support our theoretical analyses by showing that with statistically significant frequency, naive-Bayes classifiers trained on data discretized by our new methods are able to achieve lower classification error than those trained on data discretized by current established discretization methods.
Lu, J.; Yang, Y.; Webb, G. I.
Incremental Discretization for Naive-Bayes Classifier
Li, Xue; Zaiane, Osmar R.; Li, Zhanhuai (Ed.): Lecture Notes in Computer Science 4093: Proceedings of the Second International Conference on Advanced Data Mining and Applications (ADMA 2006), pp. 223-238, Springer, Xian, China, 2006.
@inproceedings{LuYangWebb06,
title = {Incremental Discretization for Naive-Bayes Classifier},
author = {J. Lu and Y. Yang and G. I. Webb},
editor = {Xue Li and Osmar R. Zaiane and Zhanhuai Li},
year = {2006},
date = {2006-01-01},
booktitle = {Lecture Notes in Computer Science 4093: Proceedings of the Second International Conference on Advanced Data Mining and Applications (ADMA 2006)},
pages = {223-238},
publisher = {Springer},
address = {Xian, China},
abstract = {Naive-Bayes classifiers (NB) support incremental learning. However, the lack of effective incremental discretization methods has been hindering NB's incremental learning in face of quantitative data. This problem is further compounded by the fact that quantitative data are everywhere, from temperature readings to share prices. In this paper, we present a novel incremental discretization method for NB, incremental flexible frequency discretization (IFFD). IFFD discretizes values of a quantitative attribute into a sequence of intervals of flexible sizes. It allows online insertion and splitting operation on intervals. Theoretical analysis and experimental test are conducted to compare IFFD with alternative methods. Empirical evidence suggests that IFFD is efficient and effective. NB coupled with IFFD achieves a rapport between high learning efficiency and high classification accuracy in the context of incremental learning.},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
Naive-Bayes classifiers (NB) support incremental learning. However, the lack of effective incremental discretization methods has been hindering NB's incremental learning in face of quantitative data. This problem is further compounded by the fact that quantitative data are everywhere, from temperature readings to share prices. In this paper, we present a novel incremental discretization method for NB, incremental flexible frequency discretization (IFFD). IFFD discretizes values of a quantitative attribute into a sequence of intervals of flexible sizes. It allows online insertion and splitting operation on intervals. Theoretical analysis and experimental test are conducted to compare IFFD with alternative methods. Empirical evidence suggests that IFFD is efficient and effective. NB coupled with IFFD achieves a rapport between high learning efficiency and high classification accuracy in the context of incremental learning.
Yang, Y.; Webb, G. I.
Weighted Proportional k-Interval Discretization for Naive-Bayes Classifiers
Whang, K-Y.; Jeon, J.; Shim, K.; Srivastava, J. (Ed.): Lecture Notes in Artificial Intelligence Vol. 2637: Proceedings of the Seventh Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD'03), pp. 501-512, Springer-Verlag, Seoul, Korea, 2003.
@inproceedings{YangWebb03,
title = {Weighted Proportional k-Interval Discretization for Naive-Bayes Classifiers},
author = {Y. Yang and G. I. Webb},
editor = {K-Y. Whang and J. Jeon and K. Shim and J. Srivastava},
year = {2003},
date = {2003-01-01},
booktitle = {Lecture Notes in Artificial Intelligence Vol. 2637: Proceedings of the Seventh Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD'03)},
pages = {501-512},
publisher = {Springer-Verlag},
address = {Seoul, Korea},
abstract = {The use of different discretization techniques can be expected to affect the bias and variance of a learning algorithm. We call such an effect discretization bias and variance. Proportional k-interval discretization (PKID) tunes discretization bias and variance by adjusting discretized interval size and number proportional to the number of training instances. Theoretical analysis suggests that this is desirable for naive-Bayes classifiers. However PKID has sub-optimal performance when learning from small training data. We argue that this is because PKID equally weighs bias reduction and variance reduction. But for small data, variance reduction can contribute more to lower learning error and thus should be given greater weight than bias reduction. Accordingly we propose weighted proportional k-interval discretization (WPKID), which establishes a more suitable bias and variance trade-off for small data while allowing additional training data to be used to reduce both bias and variance. Our experiments demonstrate that for naive-Bayes classifiers, WPKID improves upon PKID for smaller datasets with significant frequency; and WPKID delivers lower classification error significantly more often than not in comparison to the other three leading alternative discretization techniques studied.},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
The use of different discretization techniques can be expected to affect the bias and variance of a learning algorithm. We call such an effect discretization bias and variance. Proportional k-interval discretization (PKID) tunes discretization bias and variance by adjusting discretized interval size and number proportional to the number of training instances. Theoretical analysis suggests that this is desirable for naive-Bayes classifiers. However PKID has sub-optimal performance when learning from small training data. We argue that this is because PKID equally weighs bias reduction and variance reduction. But for small data, variance reduction can contribute more to lower learning error and thus should be given greater weight than bias reduction. Accordingly we propose weighted proportional k-interval discretization (WPKID), which establishes a more suitable bias and variance trade-off for small data while allowing additional training data to be used to reduce both bias and variance. Our experiments demonstrate that for naive-Bayes classifiers, WPKID improves upon PKID for smaller datasets with significant frequency; and WPKID delivers lower classification error significantly more often than not in comparison to the other three leading alternative discretization techniques studied.
Yang, Y.; Webb, G. I.
On Why Discretization Works for Naive-Bayes Classifiers
Gedeon, T. D.; Fung, L. C. C. (Ed.): Lecture Notes in Artificial Intelligence Vol. 2903: Proceedings of the 16th Australian Conference on Artificial Intelligence (AI 03), pp. 440-452, Springer, Perth, Australia, 2003.
@inproceedings{YangWebb03c,
title = {On Why Discretization Works for Naive-Bayes Classifiers},
author = {Y. Yang and G. I. Webb},
editor = {T. D. Gedeon and L. C. C. Fung},
year = {2003},
date = {2003-01-01},
booktitle = {Lecture Notes in Artificial Intelligence Vol. 2903: Proceedings of the 16th Australian Conference on Artificial Intelligence (AI 03)},
pages = {440-452},
publisher = {Springer},
address = {Perth, Australia},
abstract = {We investigate why discretization is effective in naive-Bayes learning. We prove a theorem that identifies particular conditions under which discretization will result in naive Bayes classifiers delivering the same probability estimates as would be obtained if the correct probability density functions were employed. We discuss the factors that might affect naive-Bayes classification error under discretization. We suggest that the use of different discretization techniques can affect the classification bias and variance of the generated classifiers, an effect named discretization bias and variance. We argue that by properly managing discretization bias and variance, we can effectively reduce naive-Bayes classification error},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
We investigate why discretization is effective in naive-Bayes learning. We prove a theorem that identifies particular conditions under which discretization will result in naive Bayes classifiers delivering the same probability estimates as would be obtained if the correct probability density functions were employed. We discuss the factors that might affect naive-Bayes classification error under discretization. We suggest that the use of different discretization techniques can affect the classification bias and variance of the generated classifiers, an effect named discretization bias and variance. We argue that by properly managing discretization bias and variance, we can effectively reduce naive-Bayes classification error
Yang, Y.; Webb, G. I.
Non-Disjoint Discretization for Naive-Bayes Classifiers
Sammut, C.; Hoffmann, A. G. (Ed.): Proceedings of the Nineteenth International Conference on Machine Learning (ICML '02), pp. 666-673, Morgan Kaufmann, Sydney, Australia, 2002.
@inproceedings{YangWebb02b,
title = {Non-Disjoint Discretization for Naive-Bayes Classifiers},
author = {Y. Yang and G. I. Webb},
editor = {C. Sammut and A. G. Hoffmann},
year = {2002},
date = {2002-01-01},
booktitle = {Proceedings of the Nineteenth International Conference on Machine Learning (ICML '02)},
pages = {666-673},
publisher = {Morgan Kaufmann},
address = {Sydney, Australia},
abstract = {Previous discretization techniques have discretized numeric attributes into disjoint intervals. We argue that this is neither necessary nor appropriate for naive-Bayes classifiers. The analysis leads to a new discretization method, Non-Disjoint Discretization (NDD). NDD forms overlapping intervals for a numeric attribute, always locating a value toward the middle of its discretized interval to obtain more reliable probability estimation. It also adjusts the number and size of discretized intervals to the number of training instances, seeking an appropriate trade-off between bias and variance of probability estimation. We justify NDD in theory and test it on a wide cross-section of datasets. Our experimental results suggest that for naive-Bayes classifiers, NDD works better than alternative discretization approaches.},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
Previous discretization techniques have discretized numeric attributes into disjoint intervals. We argue that this is neither necessary nor appropriate for naive-Bayes classifiers. The analysis leads to a new discretization method, Non-Disjoint Discretization (NDD). NDD forms overlapping intervals for a numeric attribute, always locating a value toward the middle of its discretized interval to obtain more reliable probability estimation. It also adjusts the number and size of discretized intervals to the number of training instances, seeking an appropriate trade-off between bias and variance of probability estimation. We justify NDD in theory and test it on a wide cross-section of datasets. Our experimental results suggest that for naive-Bayes classifiers, NDD works better than alternative discretization approaches.
Yang, Y.; Webb, G. I.
A Comparative Study of Discretization Methods for Naive-Bayes Classifiers
Yamaguchi, T.; Hoffmann, A.; Motoda, H.; Compton, P. (Ed.): Proceedings of the 2002 Pacific Rim Knowledge Acquisition Workshop (PKAW'02), pp. 159-173, Japanese Society for Artificial Intelligence, Tokyo, Japan, 2002.
@inproceedings{YangWebb02a,
title = {A Comparative Study of Discretization Methods for Naive-Bayes Classifiers},
author = {Y. Yang and G. I. Webb},
editor = {T. Yamaguchi and A. Hoffmann and H. Motoda and P. Compton},
year = {2002},
date = {2002-01-01},
booktitle = {Proceedings of the 2002 Pacific Rim Knowledge Acquisition Workshop (PKAW'02)},
pages = {159-173},
publisher = {Japanese Society for Artificial Intelligence},
address = {Tokyo, Japan},
abstract = {Discretization is a popular approach to handling numeric attributes in machine learning. We argue that the requirements for effective discretization differ between naive-Bayes learning and many other learning algorithms. We evaluate the effectiveness with naive-Bayes classifiers of nine discretization methods, equal width discretization (EWD), equal frequency discretization (EFD), fuzzy discretization (FD), entropy minimization discretization (EMD), iterative discretization (ID), proportional k-interval discretization (PKID), lazy discretization (LD), non-disjoint discretization (NDD) and weighted proportional k-interval discretization (WPKID). It is found that in general naive-Bayes classifiers trained on data preprocessed by LD, NDD or WPKID achieve lower classification error than those trained on data preprocessed by the other discretization methods. But LD can not scale to large data. This study leads to a new discretization method, weighted non-disjoint discretization (WNDD) that combines WPKID and NDD's advantages. Our experiments show that among all the rival discretization methods, WNDD best helps naive-Bayes classifiers reduce average classification error.},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
Discretization is a popular approach to handling numeric attributes in machine learning. We argue that the requirements for effective discretization differ between naive-Bayes learning and many other learning algorithms. We evaluate the effectiveness with naive-Bayes classifiers of nine discretization methods, equal width discretization (EWD), equal frequency discretization (EFD), fuzzy discretization (FD), entropy minimization discretization (EMD), iterative discretization (ID), proportional k-interval discretization (PKID), lazy discretization (LD), non-disjoint discretization (NDD) and weighted proportional k-interval discretization (WPKID). It is found that in general naive-Bayes classifiers trained on data preprocessed by LD, NDD or WPKID achieve lower classification error than those trained on data preprocessed by the other discretization methods. But LD can not scale to large data. This study leads to a new discretization method, weighted non-disjoint discretization (WNDD) that combines WPKID and NDD's advantages. Our experiments show that among all the rival discretization methods, WNDD best helps naive-Bayes classifiers reduce average classification error.
Yang, Y.; Webb, G. I.
Proportional K-Interval Discretization for Naive-Bayes Classifiers
DeRaedt, L.; Flach, P. A. (Ed.): Lecture Notes in Computer Science 2167: Proceedings of the 12th European Conference on Machine Learning (ECML'01), pp. 564-575, Springer-Verlag, Freiburg, Germany, 2001.
@inproceedings{YangWebb01,
title = {Proportional K-Interval Discretization for Naive-Bayes Classifiers},
author = {Y. Yang and G. I. Webb},
editor = {L. DeRaedt and P. A. Flach},
year = {2001},
date = {2001-01-01},
booktitle = {Lecture Notes in Computer Science 2167: Proceedings of the 12th European Conference on Machine Learning (ECML'01)},
pages = {564-575},
publisher = {Springer-Verlag},
address = {Freiburg, Germany},
abstract = {This paper argues that two commonly-used discretization approaches, fixed k-interval discretization and entropy-based discretization have sub-optimal characteristics for naive-Bayes classification. This analysis leads to a new discretization method, Proportional k-Interval Discretization (PKID), which adjusts the number and size of discretized intervals to the number of training instances, thus seeks an appropriate trade-off between the bias and variance of the probability estimation for naive-Bayes classifiers. We justify PKID in theory, as well as test it on a wide cross-section of datasets. Our experimental results suggest that in comparison to its alternatives, PKID provides naive-Bayes classifiers competitive classification performance for smaller datasets and better classification performance for larger datasets.},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
This paper argues that two commonly-used discretization approaches, fixed k-interval discretization and entropy-based discretization have sub-optimal characteristics for naive-Bayes classification. This analysis leads to a new discretization method, Proportional k-Interval Discretization (PKID), which adjusts the number and size of discretized intervals to the number of training instances, thus seeks an appropriate trade-off between the bias and variance of the probability estimation for naive-Bayes classifiers. We justify PKID in theory, as well as test it on a wide cross-section of datasets. Our experimental results suggest that in comparison to its alternatives, PKID provides naive-Bayes classifiers competitive classification performance for smaller datasets and better classification performance for larger datasets.