学步园

注：本算法的实现仅仅适用于小规模数据集的实验与测试，不适合用于工程应用

算法假定训练数据各属性列的值均是离散类型的。若是非离散类型的数据，需要首先进行数据的预处理，将非离散型的数据离散化。

算法中使用到了DecimalCaculate类，该类是java中BigDecimal类的扩展，用于高精度浮点数的运算。该类的实现同本人转载的一篇博文：对BigDecimal常用方法的归类中的Arith类相同。

算法实现的代码如下

package Bayes;<br /> import java.util.ArrayList;<br /> import java.util.HashMap;<br /> import java.util.Map;<br /> import util.DecimalCalculate;<br /> /**<br /> * 贝叶斯主体类<br /> * @author Rowen<br /> * @qq 443773264<br /> * @mail luowen3405@163.com<br /> * @blog blog.csdn.net/luowen3405<br /> * @data 2011.03.15<br /> */<br /> public class Bayes {<br /> /**<br /> * 将原训练元组按类别划分<br /> * @param datas 训练元组<br /> * @return Map<类别，属于该类别的训练元组><br /> */<br /> Map<String, ArrayList<ArrayList<String>>> datasOfClass(ArrayList<ArrayList<String>> datas){<br /> Map<String, ArrayList<ArrayList<String>>> map = new HashMap<String, ArrayList<ArrayList<String>>>();<br /> ArrayList<String> t = null;<br /> String c = "";<br /> for (int i = 0; i < datas.size(); i++) {<br /> t = datas.get(i);<br /> c = t.get(t.size() - 1);<br /> if (map.containsKey(c)) {<br /> map.get(c).add(t);<br /> } else {<br /> ArrayList<ArrayList<String>> nt = new ArrayList<ArrayList<String>>();<br /> nt.add(t);<br /> map.put(c, nt);<br /> }<br /> }<br /> return map;<br /> }</p> <p> /**<br /> * 在训练数据的基础上预测测试元组的类别<br /> * @param datas 训练元组<br /> * @param testT 测试元组<br /> * @return 测试元组的类别<br /> */<br /> public String predictClass(ArrayList<ArrayList<String>> datas, ArrayList<String> testT) {<br /> Map<String, ArrayList<ArrayList<String>>> doc = this.datasOfClass(datas);<br /> Object classes[] = doc.keySet().toArray();<br /> double maxP = 0.00;<br /> int maxPIndex = -1;<br /> for (int i = 0; i < doc.size(); i++) {<br /> String c = classes[i].toString();<br /> ArrayList<ArrayList<String>> d = doc.get(c);<br /> double pOfC = DecimalCalculate.div(d.size(), datas.size(), 3);<br /> for (int j = 0; j < testT.size(); j++) {<br /> double pv = this.pOfV(d, testT.get(j), j);<br /> pOfC = DecimalCalculate.mul(pOfC, pv);<br /> }<br /> if(pOfC > maxP){<br /> maxP = pOfC;<br /> maxPIndex = i;<br /> }<br /> }<br /> return classes[maxPIndex].toString();<br /> }<br /> /**<br /> * 计算指定属性列上指定值出现的概率<br /> * @param d 属于某一类的训练元组<br /> * @param value 列值<br /> * @param index 属性列索引<br /> * @return 概率<br /> */<br /> private double pOfV(ArrayList<ArrayList<String>> d, String value, int index) {<br /> double p = 0.00;<br /> int count = 0;<br /> int total = d.size();<br /> ArrayList<String> t = null;<br /> for (int i = 0; i < total; i++) {<br /> if(d.get(i).get(index).equals(value)){<br /> count++;<br /> }<br /> }<br /> p = DecimalCalculate.div(count, total, 3);<br /> return p;<br /> }<br /> }<br />

算法测试类：

package Bayes;<br /> import java.io.BufferedReader;<br /> import java.io.IOException;<br /> import java.io.InputStreamReader;<br /> import java.util.ArrayList;<br /> import java.util.StringTokenizer;<br /> /**<br /> * 贝叶斯算法测试类<br /> * @author Rowen<br /> * @qq 443773264<br /> * @mail luowen3405@163.com<br /> * @blog blog.csdn.net/luowen3405<br /> * @data 2011.03.15<br /> */<br /> public class TestBayes {<br /> /**<br /> * 读取测试元组<br /> * @return 一条测试元组<br /> * @throws IOException<br /> */<br /> public ArrayList<String> readTestData() throws IOException{<br /> ArrayList<String> candAttr = new ArrayList<String>();<br /> BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));<br /> String str = "";<br /> while (!(str = reader.readLine()).equals("")) {<br /> StringTokenizer tokenizer = new StringTokenizer(str);<br /> while (tokenizer.hasMoreTokens()) {<br /> candAttr.add(tokenizer.nextToken());<br /> }<br /> }<br /> return candAttr;<br /> }</p> <p> /**<br /> * 读取训练元组<br /> * @return 训练元组集合<br /> * @throws IOException<br /> */<br /> public ArrayList<ArrayList<String>> readData() throws IOException {<br /> ArrayList<ArrayList<String>> datas = new ArrayList<ArrayList<String>>();<br /> BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));<br /> String str = "";<br /> while (!(str = reader.readLine()).equals("")) {<br /> StringTokenizer tokenizer = new StringTokenizer(str);<br /> ArrayList<String> s = new ArrayList<String>();<br /> while (tokenizer.hasMoreTokens()) {<br /> s.add(tokenizer.nextToken());<br /> }<br /> datas.add(s);<br /> }<br /> return datas;<br /> }</p> <p> public static void main(String[] args) {<br /> TestBayes tb = new TestBayes();<br /> ArrayList<ArrayList<String>> datas = null;<br /> ArrayList<String> testT = null;<br /> Bayes bayes = new Bayes();<br /> try {<br /> System.out.println("请输入训练数据");<br /> datas = tb.readData();<br /> while (true) {<br /> System.out.println("请输入测试元组");<br /> testT = tb.readTestData();<br /> String c = bayes.predictClass(datas, testT);<br /> System.out.println("The class is: " + c);<br /> }<br /> } catch (IOException e) {<br /> e.printStackTrace();<br /> }<br /> }<br /> }<br />

训练数据：

youth high no fair no<br /> youth high no excellent no<br /> middle_aged high no fair yes<br /> senior medium no fair yes<br /> senior low yes fair yes<br /> senior low yes excellent no<br /> middle_aged low yes excellent yes<br /> youth medium no fair no<br /> youth low yes fair yes<br /> senior medium yes fair yes<br /> youth medium yes excellent yes<br /> middle_aged medium no excellent yes<br /> middle_aged high yes fair yes<br /> senior medium no excellent no

对原训练数据进行测试，测试如果如下：

请输入测试元组<br /> youth high no fair<br /> The class is: no<br /> 请输入测试元组<br /> youth high no excellent<br /> The class is: no<br /> 请输入测试元组<br /> middle_aged high no fair<br /> The class is: yes<br /> 请输入测试元组<br /> senior medium no fair<br /> The class is: yes<br /> 请输入测试元组<br /> senior low yes fair<br /> The class is: yes<br /> 请输入测试元组<br /> senior low yes excellent<br /> The class is: yes<br /> 请输入测试元组<br /> middle_aged low yes excellent<br /> The class is: yes<br /> 请输入测试元组<br /> youth medium no fair<br /> The class is: no<br /> 请输入测试元组<br /> youth low yes fair<br /> The class is: yes<br /> 请输入测试元组<br /> senior medium yes fair<br /> The class is: yes<br /> 请输入测试元组<br /> youth medium yes excellent<br /> The class is: yes<br /> 请输入测试元组<br /> middle_aged medium no excellent<br /> The class is: yes<br /> 请输入测试元组<br /> middle_aged high yes fair<br /> The class is: yes<br /> 请输入测试元组<br /> senior medium no excellent<br /> The class is: no<br />

测试结果显示14个测试实例中有13个分类是正确的，正确率为93%，说明算法能够给出一个准确的预测与分类，但是算法还需改进以提高正确率。

改进的可选方法之一：

为避免单个属性值对分类结果的权重过大，例如当某属性值在某一类中出现0次时，该属性值就决定了测试实例已经不可能属于该类了，这就可能会造成误差，因此在计算概率时可能进行如下改进：

将原先的P(X_k|C_i)=|X_k| / |C_i| 改为 P(X_k|C_i)=(|X_k|+mp)
/ (|C_i|+m)，其中m可设定为训练元组的个数，p为等可能假设的先验概率。