生物信息学课程设计 贝叶斯算法编程实现.doc

算法课程设计报告（算法编程实现类） 贝叶斯算法编程实现院 系 部 门： 重庆邮电大学 学 生 学 号： * 学 生 姓 名： * 指 导 教 师： * 生物信息学院制2013年5月第一部分 贝叶斯算法研究背景、特点与发展31.1 贝叶斯算法研究背景31.2 贝叶斯算法特点31.3 贝叶斯算法发展3第二部分 算法分析与程序流程图设计32.1、基于对问题的分析42.2、基于对问题的java算法分析42.2、程序流程图设计5第三部分 实现设计语言选择与算法编程实现53.1、java算法实现5第四部分 程序测试与结果分析104.1程序测试104.2结果分析11第五部分 总结与心得体会115.1总结与心得体会11第六部分 参考文献126.1参考文献（2个）12第一部分 贝叶斯算法研究背景、特点与发展1.1 贝叶斯算法研究背景贝叶斯分类算法是统计学分类方法，它是一类利用概率统计知识进行分类的算法。在许多场合，朴素贝叶斯(nave bayes，nb)分类算法可以与决策树和神经网络分类算法相媲美，且方法简单、分类准确率高、速度快。由于贝叶斯定理假设一个属性值对给定类的影响独立于其它属性的值，而此假设在实际情况中经常是不成立的，因此其分类准确率可能会下降。为此，就出现了许多降低独立性假设的贝叶斯分类算法，如tan(tree augmented bayes network)算法。1.2 贝叶斯算法特点和决策树模型相比，朴素贝叶斯模型发源于古典数学理论，有着坚实的数学基础，以 及稳定的分类效率。同时，nbc模型所需估计的参数很少，对缺失数据不太敏感，算法也比较简单。理论上，nbc模型与其他分类方法相比具有最小的误差率。 但是实际上并非总是如此，这是因为nbc模型假设属性之间相互独立，这个假设在实际应用中往往是不成立的，这给nbc模型的正确分类带来了一定影响。在属 性个数比较多或者属性之间相关性较大时，nbc模型的分类效率比不上决策树模型。而在属性相关性较小时，nbc模型的性能最为良好。1.3 贝叶斯算法发展贝叶斯分类理论有最初的朴素贝叶斯于em算法，灰色关系继续发展为基于改进em的朴素贝叶斯分类理论。第二部分 算法分析与程序流程图设计2.1、基于对问题的分析对问题进行分析，设x是类标号未知的数据样本，设h为某种假的，如数据养本x属于某特定的类c。对与分类问题，希望确定p(h|x)，即给定观测数据样本x，假定h成立的概率。贝叶斯定理给出了如下计算p(h|x)的简单有效的方法：p（h|x）=p（x|h）p（h）/p（x）其中p（h）称为先验概率，p（x|h）表示假设h成立时观查到x的概率。p（h|x）表示后验概率。每一个样本数据用一个n维特征向量x=x1，x2，x3，xn表示，分别描述具有n个属性a1，a1，an的样本的n个度量。假定有m个类c1，c2，cm，给定一个未知数据样本x（即没有类编号），分类器将预测x属性与最高后验概率的类。也就是说，朴素贝叶斯分类将未知样本分配给ci（1=ip（cj|x），j=1，2,m，j不等于i这样最大的p（ci|x）对应的类ci称为最大后验假定。由于p（x）对于所有类是常数，只需要p（x|ci）p（ci）最大即可。注意假设不是等概率的，那么类的先验概率可以用p（ci）=si/s计算，其中si是类ci的训练样本数，而s是训练样本总数。p（x|ci）=2.2、基于对问题的java算法分析首先需要将所有的训练数据读入到arraylistarraylist对象集合中去，其中每一条训练数据对应一个arraylist对象集合。同理用readtestdata()将测试元组读如arraylist对象集合中去。下面就需要将arraylistarraylist中的每一组训练元组按照类别属性分开，保存到mapstring, arraylistarraylist对象中去用三重for循环来计算测试元组中每一属性所在每一个类别中概率的之积，并返回最大积所对应的类别名称。2.2、程序流程图设计第三部分 实现设计语言选择与算法编程实现3.1、java算法实现package org.decimalcalculate;import java.math.bigdecimal;public class decimalcalculate private static final int def_div_scale = 10;/ 这个类不能实例化private decimalcalculate() public static double add(double v1, double v2) bigdecimal b1 = new bigdecimal(double.tostring(v1);bigdecimal b2 = new bigdecimal(double.tostring(v2);return b1.add(b2).doublevalue();public static double sub(double v1, double v2) bigdecimal b1 = new bigdecimal(double.tostring(v1);bigdecimal b2 = new bigdecimal(double.tostring(v2);return b1.subtract(b2).doublevalue();public static double mul(double v1, double v2) bigdecimal b1 = new bigdecimal(double.tostring(v1);bigdecimal b2 = new bigdecimal(double.tostring(v2);return b1.multiply(b2).doublevalue();public static double div(double v1, double v2) return div(v1, v2, def_div_scale);public static double div(double v1, double v2, int scale) if (scale 0) throw new illegalargumentexception(the scale must be a positive integer or zero);bigdecimal b1 = new bigdecimal(double.tostring(v1);bigdecimal b2 = new bigdecimal(double.tostring(v2);return b1.divide(b2, scale, bigdecimal.round_half_up).doublevalue();public static double round(double v, int scale) if (scale 0) throw new illegalargumentexception(the scale must be a positive integer or zero);bigdecimal b = new bigdecimal(double.tostring(v);bigdecimal one = new bigdecimal(1);return b.divide(one, scale, bigdecimal.round_half_up).doublevalue();public static float convertstofloat(double v) bigdecimal b = new bigdecimal(v);return b.floatvalue();public static int convertstoint(double v) bigdecimal b = new bigdecimal(v);return value();public static long convertstolong(double v) bigdecimal b = new bigdecimal(v);return b.longvalue();public static double returnmax(double v1, double v2) bigdecimal b1 = new bigdecimal(v1);bigdecimal b2 = new bigdecimal(v2);return b1.max(b2).doublevalue();public static double returnmin(double v1, double v2) bigdecimal b1 = new bigdecimal(v1);bigdecimal b2 = new bigdecimal(v2);return b1.min(b2).doublevalue();public static int compareto(double v1, double v2) bigdecimal b1 = new bigdecimal(v1);bigdecimal b2 = new bigdecimal(v2);return pareto(b2);package org.decimalcalculate;import java.io.bufferedreader;import java.io.ioexception;import java.io.inputstreamreader;import java.util.arraylist;import java.util.stringtokenizer;import org.bayes.*;public class testbayes public arraylist readtestdata() throws ioexception arraylist candattr = new arraylist();bufferedreader reader = new bufferedreader(new inputstreamreader(system.in);string str = ;while (!(str = reader.readline().equals() stringtokenizer tokenizer = new stringtokenizer(str);while (tokenizer.hasmoretokens() candattr.add(tokenizer.nexttoken();return candattr;public arraylistarraylist readtupledata() throws ioexception arraylistarraylist datas = new arraylistarraylist();bufferedreader reader = new bufferedreader(new inputstreamreader(system.in);string str = ;while (!(str = reader.readline().equals() stringtokenizer tokenizer = new stringtokenizer(str);arraylist s = new arraylist();while (tokenizer.hasmoretokens() s.add(tokenizer.nexttoken();datas.add(s);return datas;public static void main(string args) testbayes tb = new testbayes();arraylistarraylist datas = null;arraylist testt = null;bayes bayes = new bayes();try system.out.println(请输入训练数据集：);datas = tb.readtupledata();while (true) system.out.println(请输入测试元组：);testt = tb.readtestdata();string c = bayes.calculateprobabilityofclass(datas, testt);system.out.println(the class is: + c); catch (ioexception e) e.printstacktrace();package org.bayes;import java.util.arraylist;import java.util.hashmap;import java.util.map;import org.decimalcalculate.*;public class bayes mapstring, arraylistarraylist accordingdateofclasstosort(arraylistarraylist datas) mapstring, arraylistarraylist map = new hashmapstring, arraylistarraylist();arraylist t = null;string c = ；for (int i = 0; i datas.size(); i+) t = datas.get(i);c = t.get(t.size() - 1);if (map.containskey(c) map.get(c).add(t); else arraylistarraylist nt = new arraylistarraylist();nt.add(t);map.put(c, nt);return map;public string calculateprobabilityofclass(arraylistarraylist datas, arraylist testt) mapstring, arraylistarraylist doc = this.accordingdateofclasstosort(datas);object classes = doc.keyset().toarray();double maxp = 0.00;int maxpindex = -1;for (int i = 0; i doc.size(); i+) string c = classesi.tostring();arraylistarraylist d = do