生物信息學(xué)課程設(shè)計(jì) 貝葉斯算法編程實(shí)現(xiàn)

1、算法課程設(shè)計(jì)報(bào)告（算法編程實(shí)現(xiàn)類）貝葉斯算法編程實(shí)現(xiàn)院 系 部 門： 重慶郵電大學(xué)學(xué) 生 學(xué) 號(hào)：*學(xué) 生 姓 名：*指 導(dǎo) 教 師：*生物信息學(xué)院制2013年5月第一部分 貝葉斯算法研究背景、特點(diǎn)與發(fā)展31.1 貝葉斯算法研究背景31.2 貝葉斯算法特點(diǎn)31.3 貝葉斯算法發(fā)展3第二部分 算法分析與程序流程圖設(shè)計(jì)32.1、基于對(duì)問題的分析42.2、基于對(duì)問題的java算法分析42.2、程序流程圖設(shè)計(jì)5第三部分 實(shí)現(xiàn)設(shè)計(jì)語言選擇與算法編程實(shí)現(xiàn)53.1、java算法實(shí)現(xiàn)5第四部分 程序測(cè)試與結(jié)果分析104.1程序測(cè)試104.2結(jié)果分析11第五部分 總結(jié)與心得體會(huì)115.1總結(jié)與心得體會(huì)11第六部

2、分 參考文獻(xiàn)126.1參考文獻(xiàn)（2個(gè)）12第一部分 貝葉斯算法研究背景、特點(diǎn)與發(fā)展1.1 貝葉斯算法研究背景貝葉斯分類算法是統(tǒng)計(jì)學(xué)分類方法，它是一類利用概率統(tǒng)計(jì)知識(shí)進(jìn)行分類的算法。在許多場(chǎng)合，樸素貝葉斯(Naïve Bayes，NB)分類算法可以與決策樹和神經(jīng)網(wǎng)絡(luò)分類算法相媲美，且方法簡單、分類準(zhǔn)確率高、速度快。由于貝葉斯定理假設(shè)一個(gè)屬性值對(duì)給定類的影響?yīng)毩⒂谄渌鼘傩缘闹担思僭O(shè)在實(shí)際情況中經(jīng)常是不成立的，因此其分類準(zhǔn)確率可能會(huì)下降。為此，就出現(xiàn)了許多降低獨(dú)立性假設(shè)的貝葉斯分類算法，如TAN(tree augmented Bayes network)算法。1.2 貝葉斯算法特點(diǎn)和決

3、策樹模型相比，樸素貝葉斯模型發(fā)源于古典數(shù)學(xué)理論，有著堅(jiān)實(shí)的數(shù)學(xué)基礎(chǔ)，以 及穩(wěn)定的分類效率。同時(shí)，NBC模型所需估計(jì)的參數(shù)很少，對(duì)缺失數(shù)據(jù)不太敏感，算法也比較簡單。理論上，NBC模型與其他分類方法相比具有最小的誤差率。 但是實(shí)際上并非總是如此，這是因?yàn)镹BC模型假設(shè)屬性之間相互獨(dú)立，這個(gè)假設(shè)在實(shí)際應(yīng)用中往往是不成立的，這給NBC模型的正確分類帶來了一定影響。在屬 性個(gè)數(shù)比較多或者屬性之間相關(guān)性較大時(shí)，NBC模型的分類效率比不上決策樹模型。而在屬性相關(guān)性較小時(shí)，NBC模型的性能最為良好。1.3貝葉斯算法發(fā)展貝葉斯分類理論有最初的樸素貝葉斯于EM算法，灰色關(guān)系繼續(xù)發(fā)展為基于改進(jìn)EM的樸素貝葉斯分類理

4、論。第二部分 算法分析與程序流程圖設(shè)計(jì)2.1、基于對(duì)問題的分析對(duì)問題進(jìn)行分析，設(shè)X是類標(biāo)號(hào)未知的數(shù)據(jù)樣本，設(shè)H為某種假的，如數(shù)據(jù)養(yǎng)本X屬于某特定的類C。對(duì)與分類問題，希望確定P(H|X)，即給定觀測(cè)數(shù)據(jù)樣本X，假定H成立的概率。貝葉斯定理給出了如下計(jì)算P(H|X)的簡單有效的方法：P（H|X）=P（X|H）P（H）/P（X）其中P（H）稱為先驗(yàn)概率，P（X|H）表示假設(shè)H成立時(shí)觀查到X的概率。P（H|X）表示后驗(yàn)概率。每一個(gè)樣本數(shù)據(jù)用一個(gè)n維特征向量X=x1，x2，x3，xn表示，分別描述具有n個(gè)屬性A1，A1，An的樣本的n個(gè)度量。假定有m個(gè)類C1，C2，Cm，給定一個(gè)未知數(shù)據(jù)樣本X（即沒有

5、類編號(hào)），分類器將預(yù)測(cè)X屬性與最高后驗(yàn)概率的類。也就是說，樸素貝葉斯分類將未知樣本分配給Ci（1<=i<=m），當(dāng)且僅當(dāng)P（Ci|X）>P（Cj|X），j=1，2,m，j不等于i這樣最大的P（Ci|X）對(duì)應(yīng)的類Ci稱為最大后驗(yàn)假定。由于P（X）對(duì)于所有類是常數(shù)，只需要P（X|Ci）P（Ci）最大即可。注意假設(shè)不是等概率的，那么類的先驗(yàn)概率可以用P（Ci）=si/s計(jì)算，其中si是類Ci的訓(xùn)練樣本數(shù)，而s是訓(xùn)練樣本總數(shù)。P（X|Ci）=2.2、基于對(duì)問題的java算法分析首先需要將所有的訓(xùn)練數(shù)據(jù)讀入到ArrayList<ArrayList<String>>

6、;對(duì)象集合中去，其中每一條訓(xùn)練數(shù)據(jù)對(duì)應(yīng)一個(gè)ArrayList<String>對(duì)象集合。同理用readTestData()將測(cè)試元組讀如ArrayList<String>對(duì)象集合中去。下面就需要將ArrayList<ArrayList<String>>中的每一組訓(xùn)練元組按照類別屬性分開，保存到Map<String, ArrayList<ArrayList<String>>>對(duì)象中去用三重for循環(huán)來計(jì)算測(cè)試元組中每一屬性所在每一個(gè)類別中概率的之積，并返回最大積所對(duì)應(yīng)的類別名稱。2.2、程序流程圖設(shè)計(jì)第三部分 實(shí)現(xiàn)

7、設(shè)計(jì)語言選擇與算法編程實(shí)現(xiàn)3.1、java算法實(shí)現(xiàn)package org.decimalcalculate;import java.math.BigDecimal;publicclass DecimalCalculate privatestaticfinalintDEF_DIV_SCALE = 10;/ 這個(gè)類不能實(shí)例化private DecimalCalculate() publicstaticdouble add(double v1, double v2) BigDecimal b1 = new BigDecimal(Double.toString(v1);BigDecimal b2 =

8、new BigDecimal(Double.toString(v2);return b1.add(b2).doubleValue();publicstaticdouble sub(double v1, double v2) BigDecimal b1 = new BigDecimal(Double.toString(v1);BigDecimal b2 = new BigDecimal(Double.toString(v2);return b1.subtract(b2).doubleValue();publicstaticdouble mul(double v1, double v2) BigD

9、ecimal b1 = new BigDecimal(Double.toString(v1);BigDecimal b2 = new BigDecimal(Double.toString(v2);return b1.multiply(b2).doubleValue();publicstaticdouble div(double v1, double v2) returndiv(v1, v2, DEF_DIV_SCALE);publicstaticdouble div(double v1, double v2, intscale) if (scale < 0) thrownew Illeg

10、alArgumentException("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();publicstaticdouble round(double v, int scale) if (sc

11、ale < 0) thrownew 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();publicstaticfloat convertsToFloa

12、t(double v) BigDecimal b = new BigDecimal(v);return b.floatValue();publicstaticint convertsToInt(double v) BigDecimal b = new BigDecimal(v);return Value();publicstaticlong convertsToLong(double v) BigDecimal b = new BigDecimal(v);return b.longValue();publicstaticdouble returnMax(double v1, doub

13、le v2) BigDecimal b1 = new BigDecimal(v1);BigDecimal b2 = new BigDecimal(v2);return b1.max(b2).doubleValue();publicstaticdouble returnMin(double v1, double v2) BigDecimal b1 = new BigDecimal(v1);BigDecimal b2 = new BigDecimal(v2);return b1.min(b2).doubleValue();publicstaticint compareTo(double v1, d

14、ouble 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.*;publ

15、ic class TestBayes public ArrayList<String> readTestData() throws IOException ArrayList<String> candAttr = new ArrayList<String>();BufferedReader reader = new BufferedReader(new InputStreamReader(System.in);String str = ""while (!(str = reader.readLine().equals("&quo

16、t;) StringTokenizer tokenizer = new StringTokenizer(str);while (tokenizer.hasMoreTokens() candAttr.add(tokenizer.nextToken();return candAttr;public ArrayList<ArrayList<String>> readTupleData() throws IOException ArrayList<ArrayList<String>> datas = new ArrayList<ArrayList&

17、lt;String>>();BufferedReader reader = new BufferedReader(new InputStreamReader(System.in);String str = ""while (!(str = reader.readLine().equals("") StringTokenizer tokenizer = new StringTokenizer(str);ArrayList<String> s = new ArrayList<String>();while (tokeniz

18、er.hasMoreTokens() s.add(tokenizer.nextToken();datas.add(s);return datas;public static void main(String args) TestBayes tb = new TestBayes();ArrayList<ArrayList<String>> datas = null;ArrayList<String> testT = null;Bayes bayes = new Bayes();try System.out.println("請(qǐng)輸入訓(xùn)練數(shù)據(jù)集：&quo

19、t;);datas = tb.readTupleData();while (true) System.out.println("請(qǐng)輸入測(cè)試元組：");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.A

20、rrayList;import java.util.HashMap;import java.util.Map;import org.decimalcalculate.*;public class Bayes Map<String, ArrayList<ArrayList<String>>> accordingDateOfClassToSort(ArrayList<ArrayList<String>> datas) Map<String, ArrayList<ArrayList<String>>> m

21、ap = new HashMap<String, ArrayList<ArrayList<String>>>();ArrayList<String> 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 ArrayList<ArrayList<String>>

22、; nt = new ArrayList<ArrayList<String>>();nt.add(t);map.put(c, nt);return map;public String calculateProbabilityOfClass(ArrayList<ArrayList<String>> datas, ArrayList<String> testT) Map<String, ArrayList<ArrayList<String>>> 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();ArrayList<ArrayList<String>> d = doc.get(c);double pOfC = DecimalCalculate.div(d.size(), datas.size(), 3);f