朴素贝叶斯算法分析及java 实现

1. 先引入一个简单的例子


一、病人分类的例子

让我从一个例子开始讲起,你会看到贝叶斯分类器很好懂,一点都不难。

某个医院早上收了六个门诊病人,如下表。

  症状  职业   疾病
  打喷嚏 护士   感冒
  打喷嚏 农夫   过敏
  头痛  建筑工人 脑震荡
  头痛  建筑工人 感冒
  打喷嚏 教师   感冒
  头痛  教师   脑震荡
现在又来了第七个病人,是一个打喷嚏的建筑工人。请问他患上感冒的概率有多大?

根据贝叶斯定理:

 P(A|B) = P(B|A) P(A) / P(B)
可得

P(感冒|打喷嚏x建筑工人)

    = P(打喷嚏x建筑工人|感冒) x P(感冒)
    / P(打喷嚏x建筑工人)
假定"打喷嚏"和"建筑工人"这两个特征是独立的,因此,上面的等式就变成了
   P(感冒|打喷嚏x建筑工人)
    = P(打喷嚏|感冒) x P(建筑工人|感冒) x P(感冒)
    / P(打喷嚏) x P(建筑工人)
这是可以计算的。
  P(感冒|打喷嚏x建筑工人)
    = 0.66 x 0.33 x 0.5 / 0.5 x 0.33
    = 0.66

因此,这个打喷嚏的建筑工人,有66%的概率是得了感冒。同理,可以计算这个病人患上过敏或脑震荡的概率。比较这几个概率,就可以知道他最可能得什么病。

这就是贝叶斯分类器的基本方法:在统计资料的基础上,依据某些特征,计算各个类别的概率,从而实现分类。

二、朴素贝叶斯分类器的公式

假设某个体有n项特征(Feature),分别为F1、F2、...、Fn。现有m个类别(Category),分别为C1、C2、...、Cm。贝叶斯分类器就是计算出概率最大的那个分类,也就是求下面这个算式的最大值:

 P(C|F1F2...Fn)
  = P(F1F2...Fn|C)P(C) / P(F1F2...Fn)
由于 P(F1F2...Fn) 对于所有的类别都是相同的,可以省略,问题就变成了求

 P(F1F2...Fn|C)P(C)
的最大值。

朴素贝叶斯分类器则是更进一步,假设所有特征都彼此独立,因此

 P(F1F2...Fn|C)P(C)
  = P(F1|C)P(F2|C) ... P(Fn|C)P(C)
上式等号右边的每一项,都可以从统计资料中得到,由此就可以计算出每个类别对应的概率,从而找出最大概率的那个类。

虽然"所有特征彼此独立"这个假设,在现实中不太可能成立,但是它可以大大简化计算,而且有研究表明对分类结果的准确性影响不大。

下面再通过两个例子,来看如何使用朴素贝叶斯分类器。



2. 举例说明(采用打球的例子)
通过上面的例子我们知道,朴素贝叶斯训练阶段要做的事情就是求: P(F1|C)P(F2|C) ... P(Fn|C)P(C)

2.1 下面以打球的例子分析:

datafile/naivebayes/train/in/weather.nominal.arff
#存放做决策的属性,一般是或否
@decision
yes,no
@attribute outlook {sunny, overcast, rainy}
@attribute temperature {hot, mild, cool}
@attribute humidity {high, normal}
@attribute windy {TRUE, FALSE}
@data
sunny,hot,high,FALSE,no
sunny,hot,high,TRUE,no
overcast,hot,high,FALSE,yes
rainy,mild,high,FALSE,yes
rainy,cool,normal,FALSE,yes
rainy,cool,normal,TRUE,no
overcast,cool,normal,TRUE,yes
sunny,mild,high,FALSE,no
sunny,cool,normal,FALSE,yes
rainy,mild,normal,FALSE,yes
sunny,mild,normal,TRUE,yes
overcast,mild,high,TRUE,yes
overcast,hot,normal,FALSE,yes
rainy,mild,high,TRUE,no

2.2训练阶段要做的事情就是求出以下各个值的概率:(先放结果再分析)

datafile/naivebayes/train/out/trainresult.arff

@decision P(yes) {0.6428571428571429}
@decision P(no) {0.35714285714285715}
@data
P(outlook=sunny|yes),0.2222222222222222
P(outlook=sunny|no),0.6
P(outlook=overcast|yes),0.4444444444444444
P(outlook=overcast|no),0.0
P(outlook=rainy|yes),0.3333333333333333
P(outlook=rainy|no),0.4
P(temperature=hot|yes),0.2222222222222222
P(temperature=hot|no),0.4
P(temperature=mild|yes),0.4444444444444444
P(temperature=mild|no),0.4
P(temperature=cool|yes),0.3333333333333333
P(temperature=cool|no),0.2
P(humidity=high|yes),0.3333333333333333
P(humidity=high|no),0.8
P(humidity=normal|yes),0.6666666666666666
P(humidity=normal|no),0.2
P(windy=TRUE|yes),0.3333333333333333
P(windy=TRUE|no),0.6
P(windy=FALSE|yes),0.6666666666666666
P(windy=FALSE|no),0.4
</pre></div><h2>2.3上面的各个概率计算过程如下:</h2><p></p><pre code_snippet_id="408634" snippet_file_name="blog_20140627_4_590110" name="code" class="html">P(yes)=9/14 (在训练集中,yes出现9次,总数是14 )
P(no)=5/14
P(outlook=sunny|yes)=2/9(同时为sunny和yes的记录出现了2次,而yes总数出现了9次)
P(outlook=sunny|no)=3/5 (同时为sunny和no的记录出现了3次,no出现了5次)
其它的计算一样,这里不例举了。

2.4  测试:

求 (sunny,hot,high,FALSE) 属于yes还是no呢?

为了显示好看,把(sunny,hot,high,FALSE) 用1来表示

计算方法如下:

属于yes的概率(其它这里严格意义的概率,因为没有除以分母)

P(1|yes)= P(yes)*P(sunny|yes)*P(hot|yes)*P(high|yes)*P(FALSE|yes)=0.6428571428571429*0.2222222222222222*0.2222222222222222*0.3333333333333333*0.6666666666666666=0.007(约等)
P(1|no)=0.027
显然它属于no的概率大一点,判定它为no.


2.5 零频问题

以上计算没有考虑零频问题,实际的计算中应该避免零频问题,即在每个项计数时加1。


3.数学语言描述

关于数学公式的描述,这位大牛写得非常详细,建议大家看一看。

http://www.cnblogs.com/leoo2sk/archive/2010/09/17/naive-bayesian-classifier.html

3.1贝叶斯定理:

朴素贝叶斯算法分析及java 实现

3.2 推导

  朴素贝叶斯分类的正式定义如下:

      1、设朴素贝叶斯算法分析及java 实现为一个待分类项,而每个a为x的一个特征属性。

      2、有类别集合朴素贝叶斯算法分析及java 实现

      3、计算朴素贝叶斯算法分析及java 实现

      4、如果朴素贝叶斯算法分析及java 实现,则朴素贝叶斯算法分析及java 实现

      那么现在的关键就是如何计算第3步中的各个条件概率。我们可以这么做:

      1、找到一个已知分类的待分类项集合,这个集合叫做训练样本集。

      2、统计得到在各类别下各个特征属性的条件概率估计。即朴素贝叶斯算法分析及java 实现

      3、如果各个特征属性是条件独立的,则根据贝叶斯定理有如下推导:

      朴素贝叶斯算法分析及java 实现

      因为分母对于所有类别为常数,因为我们只要将分子最大化皆可。又因为各特征属性是条件独立的,所以有:

      朴素贝叶斯算法分析及java 实现

5.测试结果

下面结果对各项统计加1,为了避免零频问题。

sunny,hot,high,FALSE   判断的结果是:no	      --参考数值是:0.059
overcast,mild,high,TRUE   判断的结果是:yes	      --参考数值是:0.028
overcast,hot,normal,FALSE   判断的结果是:yes	      --参考数值是:0.052
rainy,mild,high,TRUE   判断的结果是:no	      --参考数值是:0.059
在实际中应随机抽取80%数据作为样本集,20%作为测试集,本例没考虑这点。


4.JAVA实现

详细源码请到我的Github上下载:

https://github.com/Bellonor/myHadoopProject/tree/master/com.homework/src/sequence/machinelearning/naivebayes/sequence/machinelearning/naivebayes/bayesdemo

时间匆忙,写例子为讲解。代码中各种漏洞请各位指出。谢谢!

以下仅给出训练部分的代码:

package sequence.machinelearning.naivebayes.bayesdemo;
import java.io.BufferedReader;
import java.io.File;
import java.io.FileOutputStream;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
import java.util.LinkedList;
/**
 * 案例:http://www.cnblogs.com/zhangchaoyang/articles/2586402.html
 * @author Jamas
 *  也参考了这篇文章:http://www.cnblogs.com/leoo2sk/archive/2010/09/17/naive-bayesian-classifier.html
 */
public class Train {

    public static LinkedList<String> lisatt = new LinkedList<String>(); // 存储属性的名称:outlook,temperature,humidity,windy
    public static LinkedList<ArrayList<String>> lisvals = new LinkedList<ArrayList<String>>(); //outlook:sunny,overcast,rainy 存储每个属性的取值,属性的特征
    public static LinkedList<String[]> listdata = new LinkedList<String[]>();; // 原始数据
   
    public static final String patternString = "@attribute(.*)[{](.*?)[}]";
    //存储分类,比如,是,否。再比如:检测SNS社区中不真实账号,是真实用户还是僵尸用户
    public static LinkedList<String> sort=new LinkedList<String>();
	
    //计算P(F1|C)P(F2|C)...P(Fn|C)P(C),并保存为文本文件 
    /**
     * 为了避免零频问题,对每个计数加1,只要数量足够大,加1是可以忽略的
     * @throws IOException
     */
    public void CountProbility() throws IOException{
    	
        String src="datafile/naivebayes/train/out/trainresult.arff";
        delfile(src);
        File file=new File(src);
        if(file.exists())
            file.createNewFile();
        FileOutputStream out=new FileOutputStream(file,true);
        Map<String,Integer> map=new HashMap<String,Integer>();
    	//先计算判定结果的概率,保存为文件
    	for(int i=0;i<sort.size();i++){
            //第一个for对取出sort,第二个for对data中的sort进行计数
    		//避免零频问题,对各项计数加1
    		Integer sum=1;
            String sortname=sort.get(i);
            Double probability=0.0;
            
            for(int j=0;j<listdata.size();j++){
    			String[] line=listdata.get(j);
    			if(line[line.length-1].equals(sortname)){
    				sum=sum+1;
    			}
     	    }
    		map.put(sortname, sum);
    		probability=Double.valueOf(sum)/Double.valueOf(listdata.size());
    		//写入文件
    		StringBuffer sb=new StringBuffer();
            sb.append("@decision P("+sortname+") {"+probability.toString()+"}\n");//如果不加"/n"则不能实现换行。
            System.out.print(sb.toString());
            
            out.write(sb.toString().getBytes("utf-8"));
    	}
    	out.write("@data\n".getBytes("utf-8"));
    	System.out.print("@data\n");
    	//先计算判定结果的概率,保存为文件
    	//out.close(); //到最后写完的时候再关闭
    	//分别统计P(F1|C)P(F2|C)...P(Fn|C)的个数,参考:http://www.ruanyifeng.com/blog/2013/12/naive_bayes_classifier.html
    	 //对属性进行循环
        for(int i=0;i<lisatt.size();i++){
        	
        	String attname=lisatt.get(i);
        	List<String> lisval=lisvals.get(i);
        	//对属性的特征进行循环
        	for(int j=0;j<lisval.size();j++){
        		String attval=lisval.get(j);
        		//先取出sort(yes 还是no情况)
        		for(int n=0;n<sort.size();n++){
        			//避免零频问题,对各项计数加1
        			Integer sum=1;
                    String sortname=sort.get(n);
                    Double probability=0.0;
                    
                    //取出数据集进行for
                    for(int k=0;k<listdata.size();k++){
            			String[] line=listdata.get(k);
            			if(line[line.length-1].equals(sortname)&&line[i].equals(attval)){
            				sum=sum+1;
            			}
             	    }
                    
            		probability=Double.valueOf(sum)/Double.valueOf(map.get(sortname));
            		//写入文件
            		StringBuffer sb=new StringBuffer();
                    sb.append("P("+attname+"="+attval+"|"+sortname+"),"+probability+"\n");//如果不加"/n"则不能实现换行。
                    System.out.print(sb.toString());
                    out.write(sb.toString().getBytes("utf-8"));
        		}
        		
        	}
        }
        out.close();
    }
    
    
    
    //读取arff文件,给attribute、attributevalue、data赋值
    public void readARFF(File file) {
        try {
            FileReader fr = new FileReader(file);
            BufferedReader br = new BufferedReader(fr);
            String line;
            Pattern pattern = Pattern.compile(patternString);
            while ((line = br.readLine()) != null) {
            	if (line.startsWith("@decision")) {
                   line = br.readLine();
                        if(line=="")
                            continue;
                        String[] type = line.split(",");
                        for(int i=0;i<type.length;i++){
                        	sort.add(type[i].trim());
                        }
                }
            	Matcher matcher = pattern.matcher(line);
                if (matcher.find()) {
                	lisatt.add(matcher.group(1).trim());
                    String[] values = matcher.group(2).split(",");
                    ArrayList<String> al = new ArrayList<String>(values.length);
                    for (String value : values) {
                        al.add(value.trim());
                    }
                    lisvals.add(al);
                } else if (line.startsWith("@data")) {
                    while ((line = br.readLine()) != null) {
                        if(line=="")
                            continue;
                        String[] row = line.split(",");
                        listdata.add(row);
                    }
                } else {
                    continue;
                }
            }
            br.close();
        } catch (IOException e1) {
            e1.printStackTrace();
        }
    }
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		Train train=new Train();
		train.readARFF(new File("datafile/naivebayes/train/in/weather.nominal.arff"));
		train.CountProbility();
		
	}
	public void delfile(String filepath){
		   File file=new File(filepath);   
		       if(file.exists())   
		      {   
		           //file.createNewFile(); 
				   file.delete();   
		       }    

	   }
}


朴素贝叶斯算法分析及java 实现,布布扣,bubuko.com

朴素贝叶斯算法分析及java 实现

上一篇:LeetCode-Sort List(Python)


下一篇:Java-集合--Java集合排序