A Study of the Neighborhood Counting Similarity

@article{citeulike:2462923, abstract = {A novel similarity, neighborhood counting measure, was recently proposed which counts the number of neighborhoods of a pair of data points. This similarity can handle numerical and categorical attributes in a conceptually uniform way, can be calculated efficiently through a simple formula, and gives good performance when tested in the framework of k-nearest neighbor classifier. In particular it consistently outperforms a combination of the classical Euclidean distance and Hamming distance. This measure was also shown to be related to a probability formalism, G probability, which is induced from a target probability function P. It was however unclear how G is related to P, especially for classification. Therefore it was not possible to explain some characteristic features of the neighborhood counting measure. In this paper we show that G is a linear function of P, and G-based Bayes classification is equivalent to P-based Bayes classification. We also show that the k-nearest neighbor classifier, when weighted by the neighborhood counting measure, is in fact an approximation of the G-based Bayes classifier, and furthermore, the P-based Bayes classifier. Additionally we show that the neighborhood counting measure remains unchanged when binary attributes are treated as categorical or numerical data. This is a feature that is not shared by other distance measures, to the best of our knowledge. This study provides a theoretical insight into the neighborhood counting measure.}, author = {Wang, Hui and Murtagh, Fionn }, booktitle = {Knowledge and Data Engineering, IEEE Transactions on}, citeulike-article-id = {2462923}, doi = {10.1109/TKDE.2007.190721}, journal = {Knowledge and Data Engineering, IEEE Transactions on}, keywords = {distributional-similarity, machine-learning}, number = {4}, pages = {449--461}, posted-at = {2008-03-04 02:55:15}, priority = {2}, title = {A Study of the Neighborhood Counting Similarity}, url = {http://dx.doi.org/10.1109/TKDE.2007.190721}, volume = {20}, year = {2008} }

TY - JOUR ID - citeulike:2462923 L3 - citeulike-article-id:2462923 TI - A Study of the Neighborhood Counting Similarity T2 - Knowledge and Data Engineering, IEEE Transactions on JF - Knowledge and Data Engineering, IEEE Transactions on VL - 20 IS - 4 SP - 449 EP - 461 N2 - A novel similarity, neighborhood counting measure, was recently proposed which counts the number of neighborhoods of a pair of data points. This similarity can handle numerical and categorical attributes in a conceptually uniform way, can be calculated efficiently through a simple formula, and gives good performance when tested in the framework of k-nearest neighbor classifier. In particular it consistently outperforms a combination of the classical Euclidean distance and Hamming distance. This measure was also shown to be related to a probability formalism, G probability, which is induced from a target probability function P. It was however unclear how G is related to P, especially for classification. Therefore it was not possible to explain some characteristic features of the neighborhood counting measure. In this paper we show that G is a linear function of P, and G-based Bayes classification is equivalent to P-based Bayes classification. We also show that the k-nearest neighbor classifier, when weighted by the neighborhood counting measure, is in fact an approximation of the G-based Bayes classifier, and furthermore, the P-based Bayes classifier. Additionally we show that the neighborhood counting measure remains unchanged when binary attributes are treated as categorical or numerical data. This is a feature that is not shared by other distance measures, to the best of our knowledge. This study provides a theoretical insight into the neighborhood counting measure. KW - distributional-similarity KW - machine-learning AU - Wang, Hui AU - Murtagh, Fionn PY - 2008/// UR - http://dx.doi.org/10.1109/TKDE.2007.190721 ER -