# Bayesian Prediction Model Based on Attribute Weighting and Kernel Density Estimations

Authors: Zhong-Liang Xiang; Xiang-Ru Yu; Dae-Ki Kang
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

Although naïve Bayes learner has been proven to show reasonable performance in machine learning, it often suffers from a few problems with handling real world data. First problem is conditional independence; the second problem is the usage of frequency estimator. Therefore, we have proposed methods to solve these two problems revolving around naïve Bayes algorithms.
By using an attribute weighting method, we have been able to handle conditional independence assumption issue, whereas, for the case of the frequency estimators, we have found a way to weaken the negative effects through our proposed smooth kernel method. In this paper, we have proposed a compact Bayes model, in which a smooth kernel augments weights on likelihood estimation. We have also chosen an attribute weighting method which employs mutual information metric to cooperate with the framework. Experiments have been conducted on UCI benchmark datasets and the accuracy of our proposed learner has been compared with that of standard naïve Bayes. The experimental results have demonstrated the effectiveness and efficiency of our proposed learning algorithm.


---

## Body

## 1. Introduction

Naïve Bayes classifier is a supervised learning method based on Bayes rule of probability theory, running on labeled training examples and driven by a strong assumption that all attributes in the training examples are independent from one another on the given training examples known as naïve Bayes assumption or naïve Bayes conditional independence assumption. Naïve Bayes classifier has high performance and rapid classification speed and has exhibited its effectiveness especially in huge training instances with plenty of attributes mainly because of its independence assumption [1].In practice, classification performance is affected by the attribute independence assumption which is usually violated in real world. However, due to the attractive advantages of efficiency and simplicity, both stemming from the attribute independence assumption, many researchers have proposed effective methods to further improve the performance of naïve Bayes classifier by weakening the attribute independence without neglecting its advantages. We categorize some typical previous methods of relaxing naïve Bayes assumption and give brief reviews in Section3. However, we have found out that attribute weighting method has drawn relatively little attention among those previous methods in improving naïve Bayes classifier, especially in the case when attribute weighting method is combined with kernel method in a reasonable way.Although Chen and Wang [2] proposed attribute weighting method with the kernel, their weighting scheme generates a series of parameters from least squares cross-validation which is less meaningful in terms of interpretation than our proposed method. In contrast, we propose an attribute weighting algorithm based on attribute weighting framework with kernel method. Our method makes the weights embedded in kernel have relatively interpretable meaning; thus we can flexibly choose different metrics and methods to measure the weights based on our attribute weighting framework.Contributions of this paper are threefold:(i)
We briefly make a survey of ways to improve naïve Bayes, especially focusing on those naïve Bayes weighting methods.(ii)
We propose a novel attribute weighting framework called Attribute Weighting with Smooth Kernel Density Estimation, simply AW-SKDE. The AW-SKDE framework employs a smooth kernel that makes the probabilistic estimation of likelihood to be dominated by the weights, which enables the combination of kernel methods and weighting methods. After setting up the kernel, we can generate a set of weights directly by using various methods cooperating with the kernel.(iii)
On the AW-SKDE framework, we propose a learner called AW-SKDEMI in which we choose the mutual information criterion to measure the dependency between an attribute and its class label.Our experimental results show that mutual information criterion based on AW-SKDE framework exhibits superior performance compared to standard naïve Bayes classifier.The paper is organized as follows: we briefly make a survey of ways to improve naïve Bayes in Section2. In Section 3, we introduce the background of our study. In Section 4, we first propose our attribute weighting framework based on kernel density estimation. After that, we propose a method employing the mutual information criterion for attribute weighting based on our proposed framework. In Section 5, we describe the experiment and results in detail. Lastly, we draw conclusions for our study and describe the future research in Section 6.


## 2. Related Work

A number of methods that weaken attribute independent assumption for naïve Bayes have been proposed in the recent years. Jiang et al. [3] made a survey about improving naïve Bayes method. Those methods are broadly divided into five main categories: structure extension, feature selection, data expansion, local learning, and attribute weighting. We make a brief review by following this categorization.For data expansion, Kang and Sohn [4] have presented an algorithm called propositionalized attribute taxonomy learner, simply PAT-learner. In PAT-learner, the training data set is first disassembled into small pieces with attributes values; then, PAT-learner rebuilds a new data set called PAT-Table by using divergence between the distribution of the class labels associated with the corresponding attributes at the disassembled date set. Kang and Kim [5] also proposed a Bayes learner based on PAT-learner, called propositionalized attribute taxonomy guided naïve Bayes learner (PAT-NBL). They utilize propositionalized data set and PAT-Table that is generated from PAT-learner to build naïve Bayes classifiers.Wong [6] has focused on the discretization method of attributes to improve naïve Bayes. Wong has proposed a hybrid method for continuous attributes and mentioned that discretizing continuous attributes in a data set using different methods can improve the performance of naïve Bayes learner. Also, Wong provides a nonparametric measure to evaluate the dependence level between a continuous attribute and the class.In structure extension, Webb et al. [7] have proposed a method called aggregating one-dependence estimators, simply AODE. In AODE, the conditional probability of test instances given class is tuned by one attribute value which occurs in the test instance. After the training stage, AODE outputs an average one-dependence estimator. AODE is a lazy method of structure extension of Bayesian network. Jiang et al. [3] have proposed hidden naïve Bayes, simply HNB, which is also a kind of structure extension method.As for attribute weighting methods, we have two ways to get attribute weights. The first one is to construct a function with the parameters of attribute weight and to let this function fit itself with the training data by estimating the weights. Zaidi et al. [8] have proposed a weighted naïve Bayes algorithm, called weighting to alleviate the naïve Bayes independence assumption, simply WANBIA. Based on WANBIA framework, the authors have described two methods to obtain the attribute weights: WANBIACLL, which maximizes the conditional log likelihood function and WANBIAMSE, which minimizes mean squared error function.Chen and Wang [2] have also proposed an algorithm to minimize mean squared error function in order to obtain the attribute weights. In another paper, Chen and Wang [9] have proposed a method called subspace weighting naïve Bayes (simply SWNB) that is a naïve Bayes weighting method to deal with high-dimensional data. Using the local feature-weighting technique, SWNB has the ability to describe different contributions of attributes in the training data set and outputs an optimal set of attribute weights fitting a Logit normal priori distribution.There are many other methods that can be categorized into attribute weighting. Lee et al. [10] have calculated attributes weight via Kullback-Leibler divergence between the attribute and class label. Wu and Cai [11] have proposed decision tree-based attribute weighted AODE, simply DTWAODE. DTWAODE generates a set of attribute weights directly, and the weight value decreases according to attribute depth in the decision tree. Omura et al. [12] have proposed a weighting method, called confidence weight for naïve Bayes, and that confidence weight is derived from the probabilities of the majority class in the training data set.


## 3. Background

In this section, we explain the concepts of machine learning methods used in this paper, including naïve Bayes classifier, naïve Bayes attribute weighting, and kernel density estimation for naïve Bayes categorical attributes. The symbols used in this paper are summarized in Notations section.


### 3.1. Naïve Bayes Classifier

In supervised learning, consider a training data setD=x(1),…,x(n) composed of n instances, where each instance x=x1,…,xm∈D (m-dimensional vector) is labeled with class label c∈C. For the posterior probability of c given x, we have(1)pc∣x=px∣c·pcpx∝px∣c.But likelihoodp(x∣c) cannot be directly estimated from D because of insufficient data in practice. Naïve Bayes uses attributes independence assumption to alleviate this problem; from the assumption, p(x∣c) is shown as follows:(2)px∣c=∏i=1mpxi∣c.In the training phase, onlyp(xi∣c) and p(c) need to be estimated for each class c∈C and each attribute value xi∈Ai. The estimation method uses the frequency of xi given c and the frequency of c for p(xi∣c) and p(c), respectively.In the classification phase, if we have a test instancet=t1,…,tm where tm is an attribute value of the attribute m in the test instance, naïve Bayes classifier outputs a class label prediction of t based on the frequency estimation of p(xi∣c) and p(c) which have been generated in the training phase. The classifier of naïve Bayes is shown as follows:(3)CNBt=argmax⁡c∈C⁡p^c∏i=1mp^xi∣c.As it was aforementioned, naïve Bayes assumption conflicts with most real world applications (note that it is rare that attributes in the same data set do not have any relationships between each other). Therefore, many researchers provide proposals to relax naïve Bayes assumption effectively, which have been reviewed in Section2.In this paper, we focus on attribute weighting methods combined with kernel density estimation technique which is applied to naïve Bayes learner in order to relax conditional independence assumption.


### 3.2. Naïve Bayes Attribute Weighting

Generally, naïve Bayes attribute weighting scheme can be formulated in several forms. Firstly, the weight to each attribute is defined as follows:(4)p^c∣x=p^c∏i=1mp^xi∣cwi.If the weight depends on attribute and class, the corresponding formula is as follows:(5)p^c∣x=p^c∏i=1mp^xi∣cwci.The following formula is used for the case when the weight depends on attribute value:(6)p^c∣x=p^c∏i=1mp^xi∣cwi,xi.Referring back to (4), when ∀wi=w, the formula is shown as follows:(7)p^c∣x=p^c∏i=1mp^xi∣cw.It is worthwhile to mention that (7) is considered as a special case of naïve Bayes classifier, where each attribute Ai has the same weight ∀wi=w=1. In other words, naïve Bayes classifier ignores the importance of attributes. From information theoretic perspective, naïve Bayes classifier abandons the chance of digging more information from D to reduce the entropy of class. This is one of the reasons why attribute weighting method provides more accuracy of classification result than naïve Bayes classifier.In our approach, we follow (4) that assigns wi which corresponds to the attribute Ai. But instead of using wi as an exponential parameter, we incorporate wi into p^(xi∣c) so that it works in a more generalized form. The weight in our paper works in the kernel, as is shown in (13), described in Section 4.1.Based on information theoretic perspective, attribute weighting method tries to find out which attribute will give more information for classification than other attributes. If an attributeAi in data set D provides more information to reduce the entropy of class label C than other attributes, then Ai will be assigned with a higher weight.


### 3.3. Kernel Density Estimation for Naïve Bayes Categorical Attributes

In naïve Bayes learner, which has been discussed in Section3.1, the likelihood p(ai(j)∣c) is often estimated by f¯c(ai(j)), the frequency of ai(j) given c; note that ai(j) is the value of attribute i at the jth instance in a data set D. From a statistical perspective, a nonsmooth estimator has the least sample bias, but it also has a large estimation variance [2, 13] at the same time. Aitchison and Aitken [14] have proposed a kernel function and Chen and Wang [2] have proposed a variant of smooth kernel function alternating the frequency. The definition of their kernel function in [2] is as follows.Given a test instancet=t1,…,tm where tm is an attribute value of the attribute m in the test instance,(8)κti,aij,λci=1-Ai-1Aiλci:ti=aij1Aiλci:ti≠aij.Note thatκti,ai(j),λci is a kernel function for Ai given c, which may become an indicator if λci=0. λci(=wci·λc) is the bandwidth such that λc=1/nc, λci∈[0,1], and nc is a number of instances in D given c.In [2], they have used (8) to estimate p(ti∣c) as follows:(9)p^ti∣c,λci=1nc∑j=1ncκti,aij,λci=f¯cti+1Ai-f¯ctiλci,where we use p(ti∣c,λci) instead of p(ti∣c). (Note that p(c) is still estimated by frequency.) They minimize the cost function to take out a series wci for each Ai in class c. The cost function is defined as follows:(10)Jwc=∑i=1m∑aiAip^ai∣c-p^ai∣c,wci2.Hence, the classifier is formulated as follows:(11)Ct=argmaxc∈C⁡p^c∏i=1mp^ti∣c,λci.


## 3.1. Naïve Bayes Classifier

In supervised learning, consider a training data setD=x(1),…,x(n) composed of n instances, where each instance x=x1,…,xm∈D (m-dimensional vector) is labeled with class label c∈C. For the posterior probability of c given x, we have(1)pc∣x=px∣c·pcpx∝px∣c.But likelihoodp(x∣c) cannot be directly estimated from D because of insufficient data in practice. Naïve Bayes uses attributes independence assumption to alleviate this problem; from the assumption, p(x∣c) is shown as follows:(2)px∣c=∏i=1mpxi∣c.In the training phase, onlyp(xi∣c) and p(c) need to be estimated for each class c∈C and each attribute value xi∈Ai. The estimation method uses the frequency of xi given c and the frequency of c for p(xi∣c) and p(c), respectively.In the classification phase, if we have a test instancet=t1,…,tm where tm is an attribute value of the attribute m in the test instance, naïve Bayes classifier outputs a class label prediction of t based on the frequency estimation of p(xi∣c) and p(c) which have been generated in the training phase. The classifier of naïve Bayes is shown as follows:(3)CNBt=argmax⁡c∈C⁡p^c∏i=1mp^xi∣c.As it was aforementioned, naïve Bayes assumption conflicts with most real world applications (note that it is rare that attributes in the same data set do not have any relationships between each other). Therefore, many researchers provide proposals to relax naïve Bayes assumption effectively, which have been reviewed in Section2.In this paper, we focus on attribute weighting methods combined with kernel density estimation technique which is applied to naïve Bayes learner in order to relax conditional independence assumption.


## 3.2. Naïve Bayes Attribute Weighting

Generally, naïve Bayes attribute weighting scheme can be formulated in several forms. Firstly, the weight to each attribute is defined as follows:(4)p^c∣x=p^c∏i=1mp^xi∣cwi.If the weight depends on attribute and class, the corresponding formula is as follows:(5)p^c∣x=p^c∏i=1mp^xi∣cwci.The following formula is used for the case when the weight depends on attribute value:(6)p^c∣x=p^c∏i=1mp^xi∣cwi,xi.Referring back to (4), when ∀wi=w, the formula is shown as follows:(7)p^c∣x=p^c∏i=1mp^xi∣cw.It is worthwhile to mention that (7) is considered as a special case of naïve Bayes classifier, where each attribute Ai has the same weight ∀wi=w=1. In other words, naïve Bayes classifier ignores the importance of attributes. From information theoretic perspective, naïve Bayes classifier abandons the chance of digging more information from D to reduce the entropy of class. This is one of the reasons why attribute weighting method provides more accuracy of classification result than naïve Bayes classifier.In our approach, we follow (4) that assigns wi which corresponds to the attribute Ai. But instead of using wi as an exponential parameter, we incorporate wi into p^(xi∣c) so that it works in a more generalized form. The weight in our paper works in the kernel, as is shown in (13), described in Section 4.1.Based on information theoretic perspective, attribute weighting method tries to find out which attribute will give more information for classification than other attributes. If an attributeAi in data set D provides more information to reduce the entropy of class label C than other attributes, then Ai will be assigned with a higher weight.


## 3.3. Kernel Density Estimation for Naïve Bayes Categorical Attributes

In naïve Bayes learner, which has been discussed in Section3.1, the likelihood p(ai(j)∣c) is often estimated by f¯c(ai(j)), the frequency of ai(j) given c; note that ai(j) is the value of attribute i at the jth instance in a data set D. From a statistical perspective, a nonsmooth estimator has the least sample bias, but it also has a large estimation variance [2, 13] at the same time. Aitchison and Aitken [14] have proposed a kernel function and Chen and Wang [2] have proposed a variant of smooth kernel function alternating the frequency. The definition of their kernel function in [2] is as follows.Given a test instancet=t1,…,tm where tm is an attribute value of the attribute m in the test instance,(8)κti,aij,λci=1-Ai-1Aiλci:ti=aij1Aiλci:ti≠aij.Note thatκti,ai(j),λci is a kernel function for Ai given c, which may become an indicator if λci=0. λci(=wci·λc) is the bandwidth such that λc=1/nc, λci∈[0,1], and nc is a number of instances in D given c.In [2], they have used (8) to estimate p(ti∣c) as follows:(9)p^ti∣c,λci=1nc∑j=1ncκti,aij,λci=f¯cti+1Ai-f¯ctiλci,where we use p(ti∣c,λci) instead of p(ti∣c). (Note that p(c) is still estimated by frequency.) They minimize the cost function to take out a series wci for each Ai in class c. The cost function is defined as follows:(10)Jwc=∑i=1m∑aiAip^ai∣c-p^ai∣c,wci2.Hence, the classifier is formulated as follows:(11)Ct=argmaxc∈C⁡p^c∏i=1mp^ti∣c,λci.


## 4. AW-SKDE Framework and AW-SKDEMI Learner

As mentioned earlier, in this section, we propose an attribute weighting framework working on the categorical attribute calledAttribute Weighting with Smooth Kernel Density Estimations, simply AW-SKDE. Based on the AW-SKDE framework, a learner named AW-SKDEMI is proposed, in which mutual information attribute weighting is applied.


### 4.1. AW-SKDE Framework

In (8), we pose an assumption that if a certain attribute Ai has more importance for classification given class label, in other words, Ai can provide more information to reduce the indeterminacy of class c, then the value of p(ai(j)∣c) should be more close to f¯c(ai(j)); otherwise, if Ai is less meaningful for classification, then p(ai(j)∣c) should be more close to 1/Ai. We let the bandwidth λci=(1-wi)2×λc, where wi∈[0,1],λc=1/nc, and nc is the number of instances labeled C=c. The variation of (8) according to our proposal is as follows:(12)κti,aij,wi=1-Ai-1Ai1-wi2λc:ti=aij1Ai1-wi2λc:ti≠aij.The estimationp(ti∣c,wi) of probability of p(ti∣c) is described as follows:(13)p^ti∣c,wi=1nc∑j=1ncκti,aij,wi=f¯cti+1Ai-f¯cti1-wi2nc.Hence, AW-SKDE framework is defined as follows:(14)CAW-SKDEt=argmaxc∈C⁡pc∏i=1mp^ti∣c,wi.The AW-SKDE framework incorporates a smooth kernel to make the probabilistic estimation of likelihood dominated by the weights. This enables natural combination of kernel methods and weighting methods. After setting up the kernel, we can generate a set of weights estimated by various methods cooperating with the kernel.


### 4.2. AW-SKDEMI Learner

Our approach generates a set of attribute weightswi∈[0,1] by employing mutual information between Ai and C. It makes sense that if one attribute has more mutual information with class label, the attribute will provide more classification ability than other attributes and therefore should be assigned a larger weight.The average weightwi_avg of each attribute Ai is defined as follows:(15)wi_avg=IAi;C∑i=1mIAi;C,where the definition of I(Ai;C) is as follows:(16)IAi;C=∑i,cp^ai∣cp^clog⁡p^ai∣cp^ai.We also incorporate split information used in C4.5 [15] with wi_split into our weighting scheme to avoid choosing the attributes with lots of values. The split information for each Ai is defined as follows where ai(j) is the value of attribute Ai at jth instance (as described in Notations section): (17)Ai_split=-∑ai∈Aip^ailog⁡p^ai.Now, the weight ofAi is defined as follows:(18)wi=wi_avg/Ai_split∑i=1mwi_avg/Ai_split.We feed AW-SKDEMI with a training data set D. In the training stage, we generate wi_avg, Ai_split, and wi out for each Ai. In the classification phase, we give a test instance t; then AW-SKDEMI classifier is formed; a prediction of class is outputted finally. The learning algorithm of AW-SKDEMI is described in Algorithm 1.Algorithm 1:Mutual information based Attribute Weighting with Smooth Kernel Density Estimation (AW-SKDEMI) algorithm.
A
W
-
S
K
D
E
M
I:
Input: training data set D and a test instance t
Output: the class estimation of t
Training phase:
begin
(1)for each ai and c  in  Ai and C:
estimatep(ai,c), p(c), p(ai∣c), p(ai) and Ai.
(2)for each Ai and C:
IAi;C=∑i,cp^ai∣cp^clog⁡p^ai∣cp^ai
(3)for each Ai:
(a)wi_avg=IAi;C∑i=1mIAi;C
(b)Ai_split=-∑ai∈Aip^ailog⁡p^ai
(c)wi=wi_avg/Ai_split∑i=1mwi_avg/Ai_split
end.
Classification phase:
begin
(1) for each dimension of test instancet and C:
p^ti∣c,wi=f-cti+1Ai-f-cti1-wi2nc
(2) Output the class value
CAW-SKDEMIt = argmaxc∈C⁡p^c∏i=1mp^ti∣c,wi
end.During the training phase, AW-SKDEMI only needs to construct conditional probability tables (CPT), which are the tables that contain joint probabilities of attributes and a class label. In terms of time complexity, the calculation of I(Ai;C), wi_avg, Ai_split, and wi requires O(mnk), O(m2), O(mv), and O(m2), respectively. Therefore, the total time complexity is O(mnk+m2+mv) in the training phase. In the classification phase, the algorithm time complexity is O(km). We summarize the time complexity of AW-SKDEMI and naïve Bayes in Table 1.Table 1
Time complexity (m: the number of attributes, n: the number of training examples, k: the number of classes, and v: the average number of values for an attribute).
Algorithm
Training time
Classification time
NB
O
(
m
n
)
O
(
k
m
)
AW-SKDEMI
O
(
m
n
k
+
m
2
+
m
v
)
O
(
k
m
)Here, we also present a framework namedAttribute Weighting with Light Smooth Kernel Density Estimation, simply AW-LSKDE, which does not consider the bandwidth. AW-LSKDE can be regarded as a simple version of AW-SKDE. According to (8), we directly let λci=1-wi where wi∈[0,1]. Hence, the kernel κti,ai(j),λci is changed to κti,ai(j),wi which is defined as follows:(19)κti,aij,wi=1Ai+Ai-1Aiwi:ti=aij1Ai1-wi:ti≠aij.The estimationp(ti∣c,wi) is described as follows:(20)p^ti∣c,wi=1nc∑j=1ncκti,aij,wi=1Ai+wif¯cti-1Ai.We also build an attribute weighting naïve Bayes learner with mutual information metric based on this AW-LSKDE framework, called AW-LSKDEMI. The method of obtaining the weight of Ai is the same as that of AW-SKDEMI learner. Unfortunately, AW-LSKDE framework does not give us encouraging results. The experimental results of AW-LSKDEMI learner can be found in Table 3 with analysis of the results.


## 4.1. AW-SKDE Framework

In (8), we pose an assumption that if a certain attribute Ai has more importance for classification given class label, in other words, Ai can provide more information to reduce the indeterminacy of class c, then the value of p(ai(j)∣c) should be more close to f¯c(ai(j)); otherwise, if Ai is less meaningful for classification, then p(ai(j)∣c) should be more close to 1/Ai. We let the bandwidth λci=(1-wi)2×λc, where wi∈[0,1],λc=1/nc, and nc is the number of instances labeled C=c. The variation of (8) according to our proposal is as follows:(12)κti,aij,wi=1-Ai-1Ai1-wi2λc:ti=aij1Ai1-wi2λc:ti≠aij.The estimationp(ti∣c,wi) of probability of p(ti∣c) is described as follows:(13)p^ti∣c,wi=1nc∑j=1ncκti,aij,wi=f¯cti+1Ai-f¯cti1-wi2nc.Hence, AW-SKDE framework is defined as follows:(14)CAW-SKDEt=argmaxc∈C⁡pc∏i=1mp^ti∣c,wi.The AW-SKDE framework incorporates a smooth kernel to make the probabilistic estimation of likelihood dominated by the weights. This enables natural combination of kernel methods and weighting methods. After setting up the kernel, we can generate a set of weights estimated by various methods cooperating with the kernel.


## 4.2. AW-SKDEMI Learner

Our approach generates a set of attribute weightswi∈[0,1] by employing mutual information between Ai and C. It makes sense that if one attribute has more mutual information with class label, the attribute will provide more classification ability than other attributes and therefore should be assigned a larger weight.The average weightwi_avg of each attribute Ai is defined as follows:(15)wi_avg=IAi;C∑i=1mIAi;C,where the definition of I(Ai;C) is as follows:(16)IAi;C=∑i,cp^ai∣cp^clog⁡p^ai∣cp^ai.We also incorporate split information used in C4.5 [15] with wi_split into our weighting scheme to avoid choosing the attributes with lots of values. The split information for each Ai is defined as follows where ai(j) is the value of attribute Ai at jth instance (as described in Notations section): (17)Ai_split=-∑ai∈Aip^ailog⁡p^ai.Now, the weight ofAi is defined as follows:(18)wi=wi_avg/Ai_split∑i=1mwi_avg/Ai_split.We feed AW-SKDEMI with a training data set D. In the training stage, we generate wi_avg, Ai_split, and wi out for each Ai. In the classification phase, we give a test instance t; then AW-SKDEMI classifier is formed; a prediction of class is outputted finally. The learning algorithm of AW-SKDEMI is described in Algorithm 1.Algorithm 1:Mutual information based Attribute Weighting with Smooth Kernel Density Estimation (AW-SKDEMI) algorithm.
A
W
-
S
K
D
E
M
I:
Input: training data set D and a test instance t
Output: the class estimation of t
Training phase:
begin
(1)for each ai and c  in  Ai and C:
estimatep(ai,c), p(c), p(ai∣c), p(ai) and Ai.
(2)for each Ai and C:
IAi;C=∑i,cp^ai∣cp^clog⁡p^ai∣cp^ai
(3)for each Ai:
(a)wi_avg=IAi;C∑i=1mIAi;C
(b)Ai_split=-∑ai∈Aip^ailog⁡p^ai
(c)wi=wi_avg/Ai_split∑i=1mwi_avg/Ai_split
end.
Classification phase:
begin
(1) for each dimension of test instancet and C:
p^ti∣c,wi=f-cti+1Ai-f-cti1-wi2nc
(2) Output the class value
CAW-SKDEMIt = argmaxc∈C⁡p^c∏i=1mp^ti∣c,wi
end.During the training phase, AW-SKDEMI only needs to construct conditional probability tables (CPT), which are the tables that contain joint probabilities of attributes and a class label. In terms of time complexity, the calculation of I(Ai;C), wi_avg, Ai_split, and wi requires O(mnk), O(m2), O(mv), and O(m2), respectively. Therefore, the total time complexity is O(mnk+m2+mv) in the training phase. In the classification phase, the algorithm time complexity is O(km). We summarize the time complexity of AW-SKDEMI and naïve Bayes in Table 1.Table 1
Time complexity (m: the number of attributes, n: the number of training examples, k: the number of classes, and v: the average number of values for an attribute).
Algorithm
Training time
Classification time
NB
O
(
m
n
)
O
(
k
m
)
AW-SKDEMI
O
(
m
n
k
+
m
2
+
m
v
)
O
(
k
m
)Here, we also present a framework namedAttribute Weighting with Light Smooth Kernel Density Estimation, simply AW-LSKDE, which does not consider the bandwidth. AW-LSKDE can be regarded as a simple version of AW-SKDE. According to (8), we directly let λci=1-wi where wi∈[0,1]. Hence, the kernel κti,ai(j),λci is changed to κti,ai(j),wi which is defined as follows:(19)κti,aij,wi=1Ai+Ai-1Aiwi:ti=aij1Ai1-wi:ti≠aij.The estimationp(ti∣c,wi) is described as follows:(20)p^ti∣c,wi=1nc∑j=1ncκti,aij,wi=1Ai+wif¯cti-1Ai.We also build an attribute weighting naïve Bayes learner with mutual information metric based on this AW-LSKDE framework, called AW-LSKDEMI. The method of obtaining the weight of Ai is the same as that of AW-SKDEMI learner. Unfortunately, AW-LSKDE framework does not give us encouraging results. The experimental results of AW-LSKDEMI learner can be found in Table 3 with analysis of the results.


## 5. Experimental Results

In order to compare AW-ESKDMI, AW-LSKDEMI, and naïve Bayes in terms of classification accuracy, we have conducted experiments on UCI Machine Learning Repository Benchmark Data Sets [16]. The UCI benchmark data sets that we have used are shown in Table 2. Note that we have conducted preprocessing to each data set: removing missing values and discretizing numerical attribute values.Table 2
Description of data sets used in the experiments.
Data set
Instances
Attributes
Classes
Missing
Numeric
Anneal
898
39
6
Y
Y
Balance-scale
625
5
3
N
Y
Breast-cancer
286
10
2
Y
N
Breast-w
699
10
2
Y
N
Colic
368
23
2
Y
Y
Credit-a
690
16
2
Y
Y
Dermatology
366
35
6
Y
Y
Glass
214
10
7
N
Y
Heart-statlog
250
14
2
N
Y
Hepatitis
155
20
2
Y
Y
Ionosphere
351
35
3
N
Y
Lymph
148
19
4
N
Y
Primary-tumor
339
18
21
Y
N
Segment
2310
20
7
N
Y
Sick
3772
30
2
Y
Y
Vehicle
846
19
4
N
Y
Vote
435
17
2
Y
NTable 3
Experimental results in terms of classifiers’ accuracy. Note that accuracies are estimated using 10-fold cross-validation with 95% confidence interval.
Data set
Naïve Bayes
AW-SKDEMI
AW-LSKDEMI
Anneal
93.99 ± 1.55
96.55 ± 1.19
76.17 ± 2.79
Balance-scale
91.36 ± 2.20
91.36 ± 2.20
89.6 ± 2.39
Breast-cancer
71.68 ± 5.22
72.38 ± 5.18
70.28 ± 5.30
Breast-w
97.28 ± 1.21
96.85 ± 1.29
88.41 ± 2.37
Colic
82.07 ± 3.92
81.79 ± 3.94
79.62 ± 4.12
Credit-a
85.94 ± 2.59
86.09 ± 2.58
83.62 ± 2.76
Dermatology
97.81 ± 1.50
97.81 ± 1.50
75.14 ± 4.43
Glass
77.10 ± 5.63
76.64 ± 5.67
62.62 ± 6.48
Heart-statlog
83.70 ± 4.58
83.70 ± 4.58
77.78 ± 5.15
Hepatitis
89.03 ± 4.92
89.03 ± 4.92
79.35 ± 6.37
Ionosphere
92.02 ± 2.83
91.45 ± 2.93
86.61 ± 3.56
Lymph
85.81 ± 5.62
85.81 ± 5.62
76.35 ± 6.85
Primary-tumor
50.15 ± 5.32
49.85 ± 5.32
24.78 ± 4.60
Segment
89.09 ± 1.27
88.70 ± 1.29
75.28 ± 1.76
Sick
97.48 ± 0.50
97.03 ± 0.54
93.88 ± 0.76
Vehicle
66.67 ± 3.18
66.90 ± 3.17
61.82 ± 3.27
Vote
90.11 ± 2.81
89.89 ± 2.83
91.49 ± 2.62
Average
84.78 ± 3.23
84.81 ± 3.22
76.05 ± 3.86In the implementation of our algorithm, all the probabilities includingp^(C=c) and p^(Ai=ai,C=c) are estimated via Laplacian smoothing which is shown as follows:(21)p^C=c=countc+1n+Cp^Ai=ai,C=c=countai,c+1ni+Ai×C,where n is the number of training examples for which the class value is known; ni is the number of training examples for which both attribute i and the class are known. The count(•) is the count value of •. The quotient of p^(Ai=ai,C=c) as the dividend and p^(C=c) as the divisor result in conditional probability p^(Ai=ai∣C=c).To compare the performance of the algorithms, we have adaptedt-test with 10-fold cross-validation. We have conducted the experiments by applying our algorithm and standard naïve Bayes on the same training data sets as well as the same test data sets. The performance of the algorithm is evaluated through classification accuracy.Table3 shows the comparison of accuracies among standard naïve Bayes, AW-SKDEMI learner, and AW-LSKDEMI learner.It can be seen that AW-SKDEMI learner shows four better results, six even results, and seven worse results than naïve Bayes within seventeen UCI data sets. AW-LSKDEMI learner only has one better result. Note that accuracies are estimated using 10-fold cross-validation with 95% confidence interval. AW-SKDEMI has a significant performance in the anneal data set and the mean accuracy of the AW-SKDEMI learner is 84.81 which is better than that of naïve Bayes’ 84.78. This experimental result can prove that our new attribute weighting model AW-SKDEMI is efficient and effective. AW-LSKDEMI learner has performed poorly due to the ignorance of bandwidth parameters in the kernel methods which results in a relatively larger bias.


## 6. Conclusions and Future Work

In this paper, a novel attribute weighting framework calledAttribute Weighting with Smooth Kernel Density Estimations, simply AW-SKDE framework, has been proposed. The AW-SKDE framework enables the estimation of likelihood to be dominated by attribute weights. Based on AW-SKDE, AW-SKDEMI has been proposed to exploit mutual information. We have conducted experiments on seventeen UCI benchmark data sets and made a comparison of accuracy among the standard NB, AW-SKDEMI, and AW-LSKDEMI. The experimental result proves that our new learner, AW-SKDEMI, is efficient and effective. Also, due to the relatively larger bias in the algorithm of AW-LSKDEMI, it has underperformed.Even though AW-SKDEMI shows comparable results, as shown in Table 3, it does not quite outperform naïve Bayes. In the future work, we plan to improve AW-SKDE framework and investigate more effective attribute weighting methods instead of the weight measurement method with mutual information between attributes and class label.



---

*Source: 170324-2015-10-05.xml*