機(jī)器學(xué)習(xí)-樸素貝葉斯學(xué)習(xí)-原理分析與C語言代碼實(shí)現(xiàn)

1、數(shù)據(jù)挖掘課程大作業(yè)題 目： 機(jī)器學(xué)習(xí)-樸素貝葉斯 班 級： 信管2014-2班 指導(dǎo)教師： 汪傳建 日期:2017年11月21日機(jī)器學(xué)習(xí)-樸素貝葉斯學(xué)習(xí)原理分析與 C 語言代碼實(shí)現(xiàn)一，任務(wù)介紹本文介紹樸素貝葉斯學(xué)習(xí)的基本原理以及其算法實(shí)現(xiàn)的 C 語言代碼。樸素貝葉斯學(xué)習(xí)也叫樸素貝葉斯分類器，它是根據(jù)貝葉斯法則進(jìn)行學(xué)習(xí)的一種算法。貝葉斯法則是條件概率相互計算的法則，即在已知 P(A|B)的情況下怎么計算 P(B|A)。P(A|B)是條件概率，表示在條件 B 成立的條件下條件 A 發(fā)生的概率，貝葉斯法則的表達(dá)式如下： 即在條件 A 成立的條件下條件 B 發(fā)生的概率，等于條件 B 成立的條件下條件

2、A 發(fā)生的概率，乘以條件 B 發(fā)生的概率，再除以條件 A 發(fā)生的概率。樸素貝葉斯學(xué)習(xí)器(分類器)就是需要計算在某個樣例條件下，計算每個目標(biāo)屬性項(xiàng)發(fā)生的概率,然后選出概率最大的目標(biāo)屬性。舉例說明，假設(shè)現(xiàn)在我們在已知某一天氣候的情況下(用 weather 表示)，需要確定是否打網(wǎng)球(用 yes 和 no 表示)。樸素貝葉斯分類器就是要計算在已知 weather 的條件下，打網(wǎng)球的概率 P(yes|weather)和 P(no|weather)，如果前者大于后者，就去打網(wǎng)球，否則就不去打網(wǎng)球。二，樸素貝葉斯學(xué)習(xí)器的原理說明根據(jù)前面的介紹，樸素貝葉斯學(xué)習(xí)器就是需要計算在已知?dú)夂虻那闆r下，分別計算出打網(wǎng)

3、球的概率和不打網(wǎng)球得概率，然后選擇概率大者作為最終的學(xué)習(xí)(分類)結(jié)果。在這里，氣候 weather 用四個屬性表示，分別是 Outlook(天氣)、Temperature(溫度)、Humidity(濕度)和Wind(風(fēng)強(qiáng)度)。先用貝葉斯公式表示為： 稱 vMAP 為在給定實(shí)例的屬性值(weather 的各屬性值)下，得到的最可能的目標(biāo)值，也就是條件概率最大的值。其中 V=yes,no，也就是說 vM AP 為目標(biāo)屬性集 V 中各取值(yes 或 no)的概率最大的。樸素貝葉斯學(xué)習(xí)器即使根據(jù)上面的公式推導(dǎo)而來?，F(xiàn)在我們根據(jù)貝葉斯法則重寫上面的公式：要作一些相應(yīng)的假定，即給定目標(biāo)值時，各屬性值之間

4、的相互條件獨(dú)立。我們把 weather 用Outlook, Temperature , Humidity ,Wind表示，把式重寫為：根據(jù)假定，給定目標(biāo)值時，某氣候下的概率就等于給定該目標(biāo)值時各屬性的概率的乘積：P(Outlook,Temperature,Humidity,Wind|vj) =P(Outlook|vj)*P(Temperature|Vj)*P(Humidity|vj)*P(Wind|vj)5把式帶入式中就得到我們要求的樸素貝葉斯的表達(dá)式： 三，示例為了能更進(jìn)一步了解樸素貝葉斯學(xué)習(xí)的原理，我們用一個示例來加以說明。該示例用表1 中的數(shù)據(jù)作為訓(xùn)練樣例，然后根據(jù)表達(dá)式 6 對測試樣例

5、進(jìn)行樸素貝葉斯分類，測試樣例如下：weather=Outlook=sunny,Temperature=cool,Humidity=high,Winds=strong;DayOutlookTemperatureHumidityWindPlayTennisDlSunnyHotHighWeakNoD2SunnyHotHighStrongNoD3OvercastHotHighWeakYesD4RainMildHighWeakYesD5RainCoolNormalWeakYesD6RainCoolNormalStrongNoD7OvercastCoolNormalStrongYesD8SunnyMild

6、HighWeakNoD9SunnyCoolNormalWeakYesDl0RainMildNormalWeakYesDl1SunnyMildNormalStrongYesDl2OvercastMildHighStrongYesDl3OvercastHotNormalWeakYesDl4RainMildHighStrongNo表 1：樸素貝葉斯學(xué)習(xí)起使用的訓(xùn)練樣例我們先計算 P(Vj)的值，Vj 有兩個值，yes 和 no：P(yes)=9/14=0.643，P(no)=5/14=0.357。然后分別計算在目標(biāo)屬性為 yes 和 no 時，測試樣例的各個屬性的條件概率。注意，我們在計算各個屬性的

7、條件概率時，采用了 m-估計的方法計算。比如在計算 P(sunny|yes)(目標(biāo)屬性為 yes，Outlook 的屬性值為 Sunny 的概率)時，按普通的計算方法：P(sunny|yes)=nc/n=2/9，nc=2 是在訓(xùn)練樣例中目標(biāo)屬性為 yes 的條件下 Outlook=sunny的樣例數(shù)，n=9 是訓(xùn)練樣例中目標(biāo)屬性值為 yes 的樣例數(shù)；但是按 m_估計的方法，計算出的概率是：P(sunny|yes)=(nc+m*p)/(n+m)=(2+14*0.33)/(9+14)，nc=2 和 n=9 代表的意思和上一樣，m=14 代表訓(xùn)練樣例總數(shù)，p=0.33 代表在屬性 Outlook

8、下共有個屬性值，所以這個先驗(yàn)概率就等于 1/3。選擇 m-估計的原因是為了避免當(dāng)訓(xùn)練樣例數(shù)量較小時，訓(xùn)練樣例中有可能沒有測試樣例中列出的某些屬性值，也就是上面的 nc=0，如果按照普通的方法，采用公式nnc ，計算出的條件概率(比如 P(sunny|yes)就會等于，這樣，根據(jù)式計算出的條件概率因?yàn)槭窍喑说膎c +m p關(guān)系，其值也會為，這樣就會出現(xiàn)對訓(xùn)練樣例過擬合的情況。而 m-估計采用公式 n+m 的形式，就可以避免出現(xiàn)過擬合的情況，m 取值一般為訓(xùn)練樣例的總數(shù)，p 的值如果某個屬性有 k 個可能值，則 p=1/k，如上面 P(sunny|yes)中，因?yàn)?Outlook 有個可能值，所以

9、 p=1/3。有了條件概率的計算公式，我們就可計算出式中的所有項(xiàng)的值：P(sunny|yes)=0.290;P(cool|yes)=0.333;P(high|yes)=0.435;P(strong|yes)=0.435;P(sunny|no)=0.403;P(cool|no)=0.298;P(high|no)=0.579;P(strong|no)=0.526;所以根據(jù)式：P(vj=yes)=P(yes)* P(sunny|yes)* P(cool|yes)* P(high|yes)* P(strong|yes)=0.0117; P(vj=no)=P(no)* P(sunny|no)* P(co

10、ol|no)* P(high|no)* P(strong|no)=0.0131。所以，該測試樣例的樸素貝葉斯分類結(jié)果為 PlayTennis=no，因條件概率 P(vj=no)大于條件概率 P(vj=yes)。如果把這兩個概率進(jìn)行歸一化處理，則 P(vj=yes)=0.473，P(vj=no)=0.528。四，樸素貝葉斯學(xué)習(xí)器代碼樸素貝葉斯學(xué)習(xí)器的代碼很簡單，先訓(xùn)練樣例統(tǒng)計各個屬性的概率，然后根據(jù)測試樣例的各個屬性值取出對應(yīng)的概率，并相乘即可，測試結(jié)果如下：樸素貝葉斯學(xué)習(xí)器完整代碼如下：/樸素貝葉斯學(xué)習(xí)器算法 C 語言代碼實(shí)現(xiàn)/Copyright:wxh5055#include /天氣類型 t

11、ypedef enum _outlooksunny,overcast, rain_outlook;/溫度類型 typedef enum _temperaturehot,mild, cool _temperature;/濕度類型 typedef enum _humidityhigh, normal_humidity;/風(fēng)強(qiáng)度類型 typedef enum _windweak, strong_wind;/目標(biāo)屬性typedef enum _targetAttributeyes, no_targetAttribute;/訓(xùn)練實(shí)例#define TRAIN_NUM14/定義 14 個訓(xùn)練實(shí)例#defi

12、ne ATTR_NUM4/每個訓(xùn)練實(shí)例有 4 個屬性int trainSampleATTR_NUM+1=sunny, hosunny, hot , high, strong, no ,/2overcast, hot , high, weak, yes,/3rain, mild, high, weak, yes,/4rain, cool, normal, weak, yes,/5rain, cool, normal, strong, no ,/6overcast, cool, normal, strong, yes,/7sunny, mild, high, weak, no ,/8sunny,

13、cool, normal, weak, yes,/9rain, mild, normal, weak, yes,/10sunny, mild, normal, strong, yes,/11overcast, mild, high, strong, yes,/12overcast, hot , normal, weak, yes,/13rain, mild, high, strong, no ,/14t , high, weak, no ,/1;/需要分類的新實(shí)例 int newSanpleATTR_NUM=sunny,cool,high,strong;/m-估計的每個屬性對應(yīng)的先驗(yàn)概率 fl

14、oat prePATTR_NUM=(float)0.333,(float)0.333,(float)0.50,(float)0.50; /m-估計的 m 值等于訓(xùn)練樣例數(shù)#define m TRAIN_NUM/計算訓(xùn)練樣例集的正樣本數(shù)和負(fù)樣本數(shù)/輸入訓(xùn)練樣例集/輸出訓(xùn)練樣例集的正樣本數(shù)和負(fù)樣本數(shù) void CalcPosAndNegNum(int *pPosNum,int *pNegNum)int i;/取出訓(xùn)練樣例/先清 0 *pPosNum=0; *pNegNum=0;for(i=0;iTRAIN_NUM;i+)/trainSample 為訓(xùn)練樣例首地址，每個訓(xùn)練樣本共有 ATTR_NUM

15、 個屬性/根據(jù)目標(biāo)屬性地址存儲的 yes 或 no 值來增加 pPosNum 或 pNegNum if(trainSampleiATTR_NUM=yes)(*pPosNum)+;else(*pNegNum)+; return; /樸素貝葉斯學(xué)習(xí)器算法程序 void NaiveBayes(void) int i,j,cntY,cntN; /存儲訓(xùn)練樣例目標(biāo)屬性為yes和no的樣本數(shù) int posNum,negNum; /存儲目標(biāo)值yes和no的概率 float PVyes,PVno,PVyesTemp,PVnoTemp; /存儲目標(biāo)值為yes時需分類的每個屬性的概率 float PAttrYe

16、sATTR_NUM; /存儲目標(biāo)值為no時需分類的每個屬性的概率 float PAttrNoATTR_NUM; /計算訓(xùn)練樣例集的正樣本數(shù)和負(fù)樣本數(shù) CalcPosAndNegNum(&posNum,&negNum); /計算目標(biāo)值yes的概率 PVyes=(float)posNum/(float)TRAIN_NUM; /計算目標(biāo)值no的概率 PVno=(float)negNum/(float)TRAIN_NUM; /計算目標(biāo)值分別為yes和no時各個需分類屬性對應(yīng)的概率 for(j=0;jATTR_NUM;j+) /清0計數(shù)變量 cntY=0; cntN=0; for(i=0;iTRAIN_

17、NUM;i+) /統(tǒng)計目標(biāo)值為yes時各個需分類的屬性在訓(xùn)練樣例中的個數(shù) if(trainSampleiATTR_NUM=yes) /如果訓(xùn)練樣例的目標(biāo)屬性是yes /且該訓(xùn)練樣例的屬性值和需要分類的樣例的屬性值相等,則計數(shù) if(trainSampleij=newSanplej) cntY+; /統(tǒng)計目標(biāo)值為no時各個需分類的屬性在訓(xùn)練樣例中的個數(shù) else if(trainSampleiATTR_NUM=no) /如果訓(xùn)練樣例的目標(biāo)屬性是no /且該訓(xùn)練樣例的屬性值和需要分類的樣例的屬性值相等,則計數(shù) if(trainSampleij=newSanplej) cntN+; /計算目標(biāo)值為yes時需分類的各個屬性的概率 PAttrYesj=(float)cntY+(floa