統(tǒng)計計算算法

《統(tǒng)計計算算法》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在應(yīng)用文檔-天天文庫。

1、分類算法-----決策樹常用的分類算法包括：決策樹分類法，樸素的貝葉斯分類算法(nativeBayesianclassifier)、基于支持向量機(SVM)的分類器，神經(jīng)網(wǎng)絡(luò)法，k-最近鄰法(k-nearestneighbor，kNN)，模糊分類法等等。監(jiān)督學(xué)習(xí)與無監(jiān)督學(xué)習(xí)機器學(xué)習(xí)發(fā)展到現(xiàn)在，一般劃分為監(jiān)督學(xué)習(xí)(supervisedlearning)，半監(jiān)督學(xué)習(xí)(semi-supervisedlearning)以及無監(jiān)督學(xué)習(xí)(unsupervisedlearning)三類。常見的分類算法屬于監(jiān)督學(xué)習(xí)，聚類則屬于無監(jiān)督學(xué)習(xí)而在支持向量機導(dǎo)論一書給監(jiān)督學(xué)習(xí)下的定義是：當(dāng)樣例是輸入/輸出對給出時，

2、稱為監(jiān)督學(xué)習(xí)，有關(guān)輸入/輸出函數(shù)關(guān)系的樣例稱為訓(xùn)練數(shù)據(jù)。而在無監(jiān)督學(xué)習(xí)中，其數(shù)據(jù)不包含輸出值，學(xué)習(xí)的任務(wù)是理解數(shù)據(jù)產(chǎn)生的過程。第一部分、決策樹學(xué)習(xí)1.1、什么是決策樹機器學(xué)習(xí)中，決策樹是一個預(yù)測模型；他代表的是對象屬性與對象值之間的一種映射關(guān)系。樹中每個節(jié)點表示某個對象，而每個分叉路徑則代表的某個可能的屬性值，而每個葉結(jié)點則對應(yīng)從根節(jié)點到該葉節(jié)點所經(jīng)歷的路徑所表示的對象的值。決策樹僅有單一輸出，若欲有復(fù)數(shù)輸出，可以建立獨立的決策樹以處理不同輸出。從數(shù)據(jù)產(chǎn)生決策樹的機器學(xué)習(xí)技術(shù)叫做決策樹學(xué)習(xí),通俗點說就是決策樹，說白了，這是一種依托于分類、訓(xùn)練上的預(yù)測樹，根據(jù)已知預(yù)測、歸類未來。來理論的太過抽

3、象，下面舉兩個淺顯易懂的例子：第一個例子那么這個可以用下圖表示女孩的決策邏輯：第二個例子此例子來自TomM.Mitchell著的機器學(xué)習(xí)一書：小王的目的是通過下周天氣預(yù)報尋找什么時候人們會打高爾夫，他了解到人們決定是否打球的原因最主要取決于天氣情況。而天氣狀況有晴，云和雨；氣溫用華氏溫度表示；相對濕度用百分比；還有有無風(fēng)。如此，我們便可以構(gòu)造一棵決策樹，如下（根據(jù)天氣這個分類決策這天是否合適打網(wǎng)球）：上述決策樹對應(yīng)于以下表達式：（Outlook=Sunny^Humidity<=70）V（Outlook=Overcast）V（Outlook=Rain^Wind=Weak）1.2、ID3算法1.

4、2.1、決策樹學(xué)習(xí)之ID3算法ID3算法是一個由RossQuinlan發(fā)明的用于決策樹的算法:越是小型的決策樹越優(yōu)于大的決策樹（besimple簡單理論）。盡管如此，該算法也不是總是生成最小的樹形結(jié)構(gòu)，而是一個啟發(fā)式算法。從信息論知識中我們知道，期望信息越小，信息增益越大，從而純度越高。ID3算法的核心思想就是以信息增益度量屬性選擇，選擇分裂后信息增益最大的屬性進行分裂。該算法采用自頂向下的貪婪搜索遍歷可能的決策樹空間。Step1:“哪一個屬性將在樹的根節(jié)點被測試”開始；Step2:使用統(tǒng)計測試來確定每一個實例屬性單獨分類訓(xùn)練樣例的能力，分類能力最好的屬性作為樹的根結(jié)點測試，Step3:為根

5、結(jié)點屬性的每個可能值產(chǎn)生一個分支，并把訓(xùn)練樣例排列到適當(dāng)?shù)姆种е?。Step4：重復(fù)這個過程，用每個分支結(jié)點關(guān)聯(lián)的訓(xùn)練樣例來選取在該點被測試的最佳屬性。下圖所示即是用于學(xué)習(xí)布爾函數(shù)的ID3算法概要：1.2.2、哪個屬性是最佳的分類屬性1、信息增益的度量標(biāo)準(zhǔn)：熵熵：它刻畫了任意樣例集的純度。給定包含關(guān)于某個目標(biāo)概念的正反樣例的樣例集S，那么S相對這個布爾型分類的熵為：上述公式中，p+代表正樣例，比如在本文開頭第二個例子中p+則意味著去打羽毛球，而p-則代表反樣例，不去打球(在有關(guān)熵的所有計算中我們定義0log0為0)。舉例來說，假設(shè)S是一個關(guān)于布爾概念的有14個樣例的集合，它包括9個正例和5個

6、反例（我們采用記號[9+，5-]來概括這樣的數(shù)據(jù)樣例），那么S相對于這個布爾樣例的熵為：Entropy（[9+，5-]）=-（9/14）log2（9/14）-（5/14）log2（5/14）=0.940。So，根據(jù)上述這個公式，我們可以得到：S的所有成員屬于同一類，Entropy(S)=0；S的正、反樣本的數(shù)量相等，Entropy(S)=1；S的正反樣本的數(shù)量不等，熵介于0，1之間，如下圖所示：信息論中對熵的一種解釋，熵確定了要編碼集合S中任意成員的分類所需要的最少二進制位數(shù)。更一般地，如果目標(biāo)屬性具有c個不同的值，那么S相對于c個狀態(tài)的分類的熵定義為：Pi為子集合中不同性(而二元分類即正樣

7、例和負(fù)樣本)的樣例的比例。2、信息增益度量期望的熵降低2、信息增益Gain(S,A)定義定義屬性分類訓(xùn)練數(shù)據(jù)的效力的度量標(biāo)準(zhǔn)。簡單的說，一個屬性的信息增益就是由于使用這個屬性分割樣例而導(dǎo)致的期望熵降低(或者說，樣本按照某屬性劃分時造成熵減少的期望)。更精確地講，一個屬性A相對樣例集合S的信息增益Gain(S,A)被定義為：其中Values(A)是屬性A所有可能值的集合，是S中屬性A的值為v的子集。換句話來講，