First,ReviewNaiveBayesianclass whosefunction is maximum (Duda&Hart.1973).IfEisthe example,and f(E)isthe discriminant function corresponding to the ith class, the chosen class Cis the one forwhich1(1)fr(E)>fE)Vi+hSuppose an example is a vector of a attributes, as is typically the case in classification ap-plications.Let ik be the value ofattributeA, in the example, P(X)denote theprobabilityofX,and P(YX)denote theconditional probability ofY givenX.Then onepossible setofdiscriminantfunctionsis(2)f;(E)= P(C) II P(A,=Ujn/C).j=1
First, Review Naïve Bayesian
C4.5BayesGaussData Set72.5±5.8673.0±6.16Audiology73.0±6.190.5±2.2184.3±3.8195.3±1.2Annealing71.3±4.3670.1±6.8§Breastcancer71.6±4.778.9±2.5185.9±2.13Credit84.5±1.899.2±0.1188.0±1.46Chess endgames88.0±1.475.2±2.1673.5±3.4574.5±2.4DiabetesNaive73.4±4.9164.7±6.31Echocardiogram69.1±5.450.6±8.2163.9±8.76Glass61.9±6.284.1±2.8177.5±4.31Heart disease81.9±3.4Bayesian is85.2±4.0679.2±4.31Hepatitis85.3±3.779.3±3.7185.1±3.81Horse colic80.7±3.797.9±0.4199.1±0.2197.5±0.3HypothyroidSurprisingly93.9±1.9692.6±2.76Iris93.2±3.578.1±7.91Labor88.7±10.6691.3±4.940.9±16.3546.8±13.36Good. Why?46.8±13.3Lung cancer54.8±5.5165.9±4.41Liverdisease63.0±3.362.9±6.56LED61.2±8.4662.9±6.581.1±4.8675.0±4.2181.6±5.9Lymphography70.0±5.2167.2±5.03Post-operative64.7±6.887.9±7.0674.3±7.8187.9±7.0Promoters44.2±5.5635.9±5.81Primary tumor44.2±5.568.2±3.7670.6±2.91Solarflare68.5±3.063.0±8.3169.1±7.46Sonar69.4±7.6100.0±0.0695.0±9.03Soybean100.0±0.095.4±0.6693.4±0.8195.4±0.6Splice junctions91.2±1.7696.3±1.3191.2±1.7Voting records5
Naïve Bayesian is Surprisingly Good. Why?
Independence TestNaive Bayesian's good performance may be due toindependence of attributes?Modeling independence of attributes Am and A,D)is zero when completely independentDOislargeifdependent
Independence Test n Naïve Bayesian’s good performance may be due to independence of attributes? n Modeling independence of attributes Am and An n D() is zero when completely independent n D() is large if dependent
How to measure independence? H(A/C): the once the class C is given, how much is Agiven?Inotherwords,howrandomisAonceCisgiven We know randomness can be measured in Entropy Entropy is -p*log(p), and then summed over all possiblevaluesThus, to measure the dependence of A on C, we canlook at each value Ci of C, such that under Ci,Find the entropy of A.Then, sum overall possible Ci
How to measure independence? n H(A|C): the once the class C is given, how much is A given? n In other words, how random is A once C is given n We know randomness can be measured in Entropy n Entropy is –p*log(p), and then summed over all possible values n Thus, to measure the dependence of A on C, we can look at each value Ci of C, such that under Ci, n Find the entropy of A n Then, sum over all possible Ci
Measuring dependencyWindyPlayFALSEnoExample:C=Playattribute,TRUEnoA=Windy Attribute*yesFALSEC1=yes, C2=noPr(C=Yes)=9/14*yesFALSEWhen C=C1 (Play=yes)*yesFALSEA=True: 3 countsA=False:6countsTRUEnoPr(A=TrueandC=C1)=3/14*yesTRUEPr(A=FalseandC=C1)=6/14WhenC=C2(no)FALSEnoPr(A=TrueandC=C2)=3/14*yesFALSEPr(A=FalseandC=C2)=2/14H(A/C)=9/14*[(-*yesFALSE3/14)log(3/14)-*yes(6/14)log(6/14)]+5/14*[-TRUE3/14log(3/14)-2/14log(2/14))*yesTRUE*yesFALSETRUEno
Measuring dependency n Example: C=Play attribute, A=Windy Attribute n C1=yes, C2=no n Pr(C=Yes)=9/14 n When C=C1 (Play = yes) n A=True: 3 counts n A=False: 6 counts n Pr(A=True and C=C1)=3/14 n Pr(A=False and C=C1)=6/14 n When C=C2 (no) n Pr(A=True and C=C2)=3/14 n Pr(A=False and C=C2)=2/14 n H(A|C)=9/14*[(- 3/14)log(3/14)- (6/14)log(6/14)]+5/14*[- 3/14log(3/14)-2/14log(2/14)] Windy Play FALSE no TRUE no FALSE *yes FALSE *yes FALSE *yes TRUE no TRUE *yes FALSE no FALSE *yes FALSE *yes TRUE *yes TRUE *yes FALSE *yes TRUE no