簡(jiǎn)述機(jī)器學(xué)習(xí)十大算法的每個(gè)算法的核心思想、工作原理、

1、 5-1 簡(jiǎn)述機(jī)器學(xué)習(xí)十大算法的每個(gè)算法的核心思想、工作原理、適用情況及優(yōu)缺點(diǎn)等。 1）C4.5算法：ID3算法是以信息論為基礎(chǔ)，以信息熵和信息增益度為衡量標(biāo)準(zhǔn)，從而實(shí)現(xiàn)對(duì)數(shù)據(jù)的歸納分類。ID3算法計(jì)算每個(gè)屬性的信息增益，并選取具有最高增益的屬性作為給定的測(cè)試屬性。C4.5算法核心思想是ID3算法，是ID3算法的改進(jìn)，改進(jìn)方面有：1） 用信息增益率來選擇屬性，克服了用信息增益選擇屬性時(shí)偏向選擇取值多的屬性的不足； 2） 在樹構(gòu)造過程中進(jìn)行剪枝3） 能處理非離散的數(shù)據(jù)4） 能處理不完整的數(shù)據(jù) C4.5算法優(yōu)點(diǎn)：產(chǎn)生的分類規(guī)則易于理解，準(zhǔn)確率較高。 缺點(diǎn)：1) 在構(gòu)造樹的過程中，需要對(duì)數(shù)據(jù)集進(jìn)行多

2、次的順序掃描和排序，因而導(dǎo)致算法的低效。 2) C4.5只適合于能夠駐留于內(nèi)存的數(shù)據(jù)集，當(dāng)訓(xùn)練集大得無法在內(nèi)存容納時(shí)程序無法運(yùn)行。 2）K means 算法：是一個(gè)簡(jiǎn)單的聚類算法，把n的對(duì)象根據(jù)他們的屬性分為k個(gè)分割，k < n。 算法的核心就是要優(yōu)化失真函數(shù)J,使其收斂到局部最小值但不是全局最小值。，其中N為樣本數(shù)，K是簇?cái)?shù)，rnk b表示n屬于第k個(gè)簇，uk 是第k個(gè)中心點(diǎn)的值。然后求出最優(yōu)的uk優(yōu)點(diǎn)：算法速度很快缺點(diǎn)是，分組的數(shù)目k是一個(gè)輸入?yún)?shù)，不合適的k可能返回較差的結(jié)果。3）樸素貝葉斯算法：樸素貝葉斯法是基于貝葉斯定理與特征條件獨(dú)立假設(shè)的分類方法。算法的基礎(chǔ)是概率問題，分類原

3、理是通過某對(duì)象的先驗(yàn)概率，利用貝葉斯公式計(jì)算出其后驗(yàn)概率，即該對(duì)象屬于某一類的概率，選擇具有最大后驗(yàn)概率的類作為該對(duì)象所屬的類。樸素貝葉斯假設(shè)是約束性很強(qiáng)的假設(shè)，假設(shè)特征條件獨(dú)立，但樸素貝葉斯算法簡(jiǎn)單，快速，具有較小的出錯(cuò)率。在樸素貝葉斯的應(yīng)用中，主要研究了電子郵件過濾以及文本分類研究。4)K最近鄰分類算法（KNN）分類思想比較簡(jiǎn)單，從訓(xùn)練樣本中找出K個(gè)與其最相近的樣本，然后看這k個(gè)樣本中哪個(gè)類別的樣本多，則待判定的值（或說抽樣）就屬于這個(gè)類別。缺點(diǎn)：1） K值需要預(yù)先設(shè)定，而不能自適應(yīng)2） 當(dāng)樣本不平衡時(shí)，如一個(gè)類的樣本容量很大，而其他類樣本容量很小時(shí)，有可能導(dǎo)致當(dāng)輸入一個(gè)新樣本時(shí)，該樣本的

4、K個(gè)鄰居中大容量類的樣本占多數(shù)。該算法適用于對(duì)樣本容量比較大的類域進(jìn)行自動(dòng)分類。5)EM最大期望算法EM算法是基于模型的聚類方法，是在概率模型中尋找參數(shù)最大似然估計(jì)的算法，其中概率模型依賴于無法觀測(cè)的隱藏變量 。E步估計(jì)隱含變量，M步估計(jì)其他參數(shù)，交替將極值推向最大。EM算法比K-means算法計(jì)算復(fù)雜，收斂也較慢，不適于大規(guī)模數(shù)據(jù)集和高維數(shù)據(jù)，但比K-means算法計(jì)算結(jié)果穩(wěn)定、準(zhǔn)確。EM經(jīng)常用在機(jī)器學(xué)習(xí)和計(jì)算機(jī)視覺的數(shù)據(jù)集聚（Data Clustering）領(lǐng)域。6） PageRank算法是google的頁面排序算法，是基于從許多優(yōu)質(zhì)的網(wǎng)頁鏈接過來的網(wǎng)頁，必定還是優(yōu)質(zhì)網(wǎng)頁的回歸關(guān)系，來判定

5、所有網(wǎng)頁的重要性。（也就是說，一個(gè)人有著越多牛X朋友的人，他是牛X的概率就越大。）優(yōu)點(diǎn)：完全獨(dú)立于查詢，只依賴于網(wǎng)頁鏈接結(jié)構(gòu)，可以離線計(jì)算。缺點(diǎn)：1） PageRank算法忽略了網(wǎng)頁搜索的時(shí)效性。2） 舊網(wǎng)頁排序很高，存在時(shí)間長(zhǎng)，積累了大量的in-links，擁有最新資訊的新網(wǎng)頁排名卻很低，因?yàn)樗鼈儙缀鯖]有in-links。7)AdaBoost Adaboost是一種迭代算法，其核心思想是針對(duì)同一個(gè)訓(xùn)練集訓(xùn)練不同的分類器(弱分類器)，然后把這些弱分類器集合起來，構(gòu)成一個(gè)更強(qiáng)的最終分類器(強(qiáng)分類器)。其算法本身是通過改變數(shù)據(jù)分布來實(shí)現(xiàn)的，它根據(jù)每次訓(xùn)練集之中每個(gè)樣本的分類是否正確，以及上次的總體

6、分類的準(zhǔn)確率，來確定每個(gè)樣本的權(quán)值。將修改過權(quán)值的新數(shù)據(jù)集送給下層分類器進(jìn)行訓(xùn)練，最后將每次訓(xùn)練得到的分類器最后融合起來，作為最后的決策分類器。 整個(gè)過程如下所示：1. 先通過對(duì)N個(gè)訓(xùn)練樣本的學(xué)習(xí)得到第一個(gè)弱分類器 ；2. 將分錯(cuò)的樣本和其他的新數(shù)據(jù)一起構(gòu)成一個(gè)新的N個(gè)的訓(xùn)練樣本，通過對(duì)這個(gè)樣本的學(xué)習(xí)得到第二個(gè)弱分類器 ；3. 將 和 都分錯(cuò)了的樣本加上其他的新樣本構(gòu)成另一個(gè)新的N個(gè)的訓(xùn)練樣本，通過對(duì)這個(gè)樣本的學(xué)習(xí)得到第三個(gè)弱分類器 ；4. 如此反復(fù)，最終得到經(jīng)過提升的強(qiáng)分類器。目前AdaBoost算法廣泛的應(yīng)用于人臉檢測(cè)、目標(biāo)識(shí)別等領(lǐng)域。8） Apriori算法Apriori算法是一種挖掘關(guān)

7、聯(lián)規(guī)則的算法，用于挖掘其內(nèi)含的、未知的卻又實(shí)際存在的數(shù)據(jù)關(guān)系，其核心是基于兩階段頻集思想的遞推算法 。Apriori算法分為兩個(gè)階段：1） 尋找頻繁項(xiàng)集2） 由頻繁項(xiàng)集找關(guān)聯(lián)規(guī)則算法缺點(diǎn)：1） 在每一步產(chǎn)生侯選項(xiàng)目集時(shí)循環(huán)產(chǎn)生的組合過多，沒有排除不應(yīng)該參與組合的元素；2） 每次計(jì)算項(xiàng)集的支持度時(shí)，都對(duì)數(shù)據(jù)庫中 的全部記錄進(jìn)行了一遍掃描比較，需要很大的I/O負(fù)載。9） SVM支持向量機(jī)支持向量機(jī)是一種基于分類邊界的方法。其基本原理是（以二維數(shù)據(jù)為例）：如果訓(xùn)練數(shù)據(jù)分布在二維平面上的點(diǎn)，它們按照其分類聚集在不同的區(qū)域?；诜诸愡吔绲姆诸愃惴ǖ哪繕?biāo)是，通過訓(xùn)練，找到這些分類之間的邊界（直線的稱為線性

8、劃分，曲線的稱為非線性劃分）。對(duì)于多維數(shù)據(jù)（如N維），可以將它們視為N維空間中的點(diǎn)，而分類邊界就是N維空間中的面，稱為超面（超面比N維空間少一維）。線性分類器使用超平面類型的邊界，非線性分類器使用超曲面。支持向量機(jī)的原理是將低維空間的點(diǎn)映射到高維空間，使它們成為線性可分，再使用線性劃分的原理來判斷分類邊界。在高維空間中是一種線性劃分，而在原有的數(shù)據(jù)空間中，是一種非線性劃分。SVM在解決小樣本、非線性及高維模式識(shí)別問題中表現(xiàn)出許多特有的優(yōu)勢(shì)，并能夠推廣應(yīng)用到函數(shù)擬合等其他機(jī)器學(xué)習(xí)問題中。10） CART分類與回歸樹是一種決策樹分類方法，采用基于最小距離的基尼指數(shù)估計(jì)函數(shù)，用來決定由該子數(shù)據(jù)集生成的決策樹的拓展形。如果目標(biāo)變量是標(biāo)稱的，稱為分類樹；如果目標(biāo)