经典的十个机器学习算法
1、C4.5
機(jī)器學(xué)習(xí)中，決策樹是一個預(yù)測模型；他代表的是對象屬性與對象值之間的一種映射關(guān)系。樹中每個節(jié)點表示某個對象，而每個分叉路徑則代表的某個可能的 屬性值，而每個葉結(jié)點則對應(yīng)從根節(jié)點到該葉節(jié)點所經(jīng)歷的路徑所表示的對象的值。決策樹僅有單一輸出，若欲有復(fù)數(shù)輸出，可以建立獨立的決策樹以處理不同輸 出。
從數(shù)據(jù)產(chǎn)生決策樹的機(jī)器學(xué)習(xí)技術(shù)叫做決策樹學(xué)習(xí),?通俗說就是決策樹。
決策樹學(xué)習(xí)也是數(shù)據(jù)挖掘中一個普通的方法。在這里，每個決策樹都表述了一種樹型結(jié)構(gòu)，他由他的分支來對該類型的對象依靠屬性進(jìn)行分類。每個決策樹可 以依靠對源數(shù)據(jù)庫的分割進(jìn)行數(shù)據(jù)測試。這個過程可以遞歸式的對樹進(jìn)行修剪。?當(dāng)不能再進(jìn)行分割或一個單獨的類可以被應(yīng)用于某一分支時，遞歸過程就完成了。 另外，隨機(jī)森林分類器將許多決策樹結(jié)合起來以提升分類的正確率。
決策樹同時也可以依靠計算條件概率來構(gòu)造。決策樹如果依靠數(shù)學(xué)的計算方法可以取得更加理想的效果。
決策樹是如何工作的
決策樹一般都是自上而下的來生成的。
選擇分割的方法有好幾種，但是目的都是一致的：對目標(biāo)類嘗試進(jìn)行最佳的分割。
從根到葉子節(jié)點都有一條路徑，這條路徑就是一條“規(guī)則”。
決策樹可以是二叉的，也可以是多叉的。
對每個節(jié)點的衡量：
1)????????通過該節(jié)點的記錄數(shù)
2)????????如果是葉子節(jié)點的話，分類的路徑
3)????????對葉子節(jié)點正確分類的比例。
有些規(guī)則的效果可以比其他的一些規(guī)則要好。
由于ID3算法在實際應(yīng)用中存在一些問題，于是Quilan提出了C4.5算法，嚴(yán)格上說C4.5只能是ID3的一個改進(jìn)算法。相信大家對ID3算法都很.熟悉了，這里就不做介紹。
????C4.5算法繼承了ID3算法的優(yōu)點，并在以下幾方面對ID3算法進(jìn)行了改進(jìn)：
????1)?用信息增益率來選擇屬性，克服了用信息增益選擇屬性時偏向選擇取值多的屬性的不足；
????2)?在樹構(gòu)造過程中進(jìn)行剪枝；
????3)?能夠完成對連續(xù)屬性的離散化處理；
????4)?能夠?qū)Σ煌暾麛?shù)據(jù)進(jìn)行處理。
????C4.5算法有如下優(yōu)點：產(chǎn)生的分類規(guī)則易于理解，準(zhǔn)確率較高。其缺點是：在構(gòu)造樹的過程中，需要對數(shù)據(jù)集進(jìn)行多次的順序掃描和排序，因而導(dǎo)致算法的低效。此外，C4.5只適合于能夠駐留于內(nèi)存的數(shù)據(jù)集，當(dāng)訓(xùn)練集大得無法在內(nèi)存容納時程序無法運行。
來自搜索的其他內(nèi)容：
C4.5算法是機(jī)器學(xué)習(xí)算法中的一種分類決策樹算法,其核心算法是ID3算法.?
??分類決策樹算法是從大量事例中進(jìn)行提取分類規(guī)則的自上而下的決策樹.?
??????決策樹的各部分是:?
????????????根:???學(xué)習(xí)的事例集.?
????????????枝:???分類的判定條件.?
????????????葉:???分好的各個類.?
§4.3.2?????ID3算法?
??1.概念提取算法CLS?
1)?????初始化參數(shù)C={E},E包括所有的例子,為根.?
2)???????IF?????C中的任一元素e同屬于同一個決策類則創(chuàng)建一個葉子?????
??????????????節(jié)點YES終止.?
??????????ELSE?????依啟發(fā)式標(biāo)準(zhǔn),選擇特征Fi={V1,V2,V3,．．．Vn}并創(chuàng)建?
??????????????????????判定節(jié)點?
劃分C為互不相交的N個集合C1,C2,C3,．．．,Cn；?
3)?????對任一個Ci遞歸.?
2.?????ID3算法?
1)?????隨機(jī)選擇C的一個子集W???(窗口).?
2)?????調(diào)用CLS生成W的分類樹DT(強(qiáng)調(diào)的啟發(fā)式標(biāo)準(zhǔn)在后).?
3)?????順序掃描C搜集DT的意外(即由DT無法確定的例子).?
4)?????組合W與已發(fā)現(xiàn)的意外,形成新的W.?
5)?????重復(fù)2)到4),直到無例外為止.?
啟發(fā)式標(biāo)準(zhǔn):?
??????只跟本身與其子樹有關(guān),采取信息理論用熵來量度.?
??????熵是選擇事件時選擇自由度的量度,其計算方法為?
??????????????P???=???freq(Cj,S)/|S|;?
??????INFO(S)=???-???SUM(???P*LOG(P)???)???;???????SUM()函數(shù)是求j從1到n和.?
??????Gain(X)=Info(X)-Infox(X);?
??????Infox(X)=SUM(???(|Ti|/|T|)*Info(X);?
為保證生成的決策樹最小,ID3算法在生成子樹時,選取使生成的子樹的熵(即Gain(S))最小的的特征來生成子樹.?
§4.3.3:???ID3算法對數(shù)據(jù)的要求?
1.?????所有屬性必須為離散量.?
2.?????所有的訓(xùn)練例的所有屬性必須有一個明確的值.?
3.?????相同的因素必須得到相同的結(jié)論且訓(xùn)練例必須唯一.?
§4.3.4:???C4.5對ID3算法的改進(jìn):?
??????1.?????熵的改進(jìn),加上了子樹的信息.?
????????????Split_Infox(X)=???-???SUM(?????(|T|/|Ti|???)???*LOG(|Ti|/|T|)?????);?
????????????Gain???ratio(X)=?????Gain(X)/Split???Infox(X);?
2.?????在輸入數(shù)據(jù)上的改進(jìn).?
????????1)?
因素屬性的值可以是連續(xù)量,C4.5對其排序并分成不同的集合后按照ID3算法當(dāng)作離散量進(jìn)行處理,但結(jié)論屬性的值必須是離散值.?
??????2)???訓(xùn)練例的因素屬性值可以是不確定的,以???????表示,但結(jié)論必須是確定的?
??????3.?????對已生成的決策樹進(jìn)行裁剪,減小生成樹的規(guī)模.
2、The?k-means?algorithm
???k-means?algorithm算法是一個聚類算法，把n的對象根據(jù)他們的屬性分為k個分割，k?<?n。它與處理混合正態(tài)分布的最大期望算法很相似，因為他們都試圖找到數(shù)據(jù)中自然聚類的中心。它假設(shè)對象屬性來自于空間向量，并且目標(biāo)是使各個群組內(nèi)部的均方誤差總和最小。
假設(shè)有k個群組Si,?i=1,2,...,k。μi是群組Si內(nèi)所有元素xj的重心，或叫中心點。
k平均聚類發(fā)明于1956年，?該算法最常見的形式是采用被稱為勞埃德算法(Lloyd?algorithm)的迭代式改進(jìn)探索法。勞埃德算法首先把輸入點分成k個初始化分組，可以是隨機(jī)的或者使用一些啟發(fā)式數(shù)據(jù)。然后計算每組的中心點，根據(jù)中心點的位置把對象分到離它最近的中心，重新確定分組。繼續(xù)重復(fù)不斷地計算中心并重新分組，直到收斂，即對象不再改變分組（中心點位置不再改變）。
勞埃德算法和k平均通常是緊密聯(lián)系的，但是在實際應(yīng)用中，勞埃德算法是解決k平均問題的啟發(fā)式法則，對于某些起始點和重心的組合，勞埃德算法可能實際上收斂于錯誤的結(jié)果。（上面函數(shù)中存在的不同的最優(yōu)解）
雖然存在變異，但是勞埃德算法仍舊保持流行，因為它在實際中收斂非常快。實際上，觀察發(fā)現(xiàn)迭代次數(shù)遠(yuǎn)遠(yuǎn)少于點的數(shù)量。然而最近，David?Arthur和Sergei?Vassilvitskii提出存在特定的點集使得k平均算法花費超多項式時間達(dá)到收斂。
近似的k平均算法已經(jīng)被設(shè)計用于原始數(shù)據(jù)子集的計算。
從算法的表現(xiàn)上來說，它并不保證一定得到全局最優(yōu)解，最終解的質(zhì)量很大程度上取決于初始化的分組。由于該算法的速度很快，因此常用的一種方法是多次運行k平均算法，選擇最優(yōu)解。
k平均算法的一個缺點是，分組的數(shù)目k是一個輸入?yún)?shù)，不合適的k可能返回較差的結(jié)果。另外，算法還假設(shè)均方誤差是計算群組分散度的最佳參數(shù)。
3、SVM
支持向量機(jī)，英文為Support?Vector?Machine，簡稱SV機(jī)（論文中一般簡稱svm）。它是一種監(jiān)督式學(xué)習(xí)的方法，它廣泛的應(yīng)用于統(tǒng)計分類以及回歸分析中。
支持向量機(jī)屬于一般化線性分類器.他們也可以認(rèn)為是提克洛夫規(guī)范化（Tikhonov?Regularization）方法的一個特例.這族分類器的特點是他們能夠同時最小化經(jīng)驗誤差與最大化幾何邊緣區(qū).因此支持向量機(jī)也被稱為最大邊緣區(qū)分類器。在統(tǒng)計計算中，最大期望（EM）算法是在概率（probabilistic）模型中尋找參數(shù)最大似然估計的算法，其中概率模型依賴于無法觀測的隱藏變量（Latent?Variabl）。最大期望經(jīng)常用在機(jī)器學(xué)習(xí)和計算機(jī)視覺的數(shù)據(jù)集聚（Data?Clustering）領(lǐng)域。最大期望算法經(jīng)過兩個步驟交替進(jìn)行計算，第一步是計算期望（E），也就是將隱藏變量象能夠觀測到的一樣包含在內(nèi)從而計算最大似然的期望值；另外一步是最大化（M），也就是最大化在?E?步上找到的最大似然的期望值從而計算參數(shù)的最大似然估計。M?步上找到的參數(shù)然后用于另外一個?E?步計算，這個過程不斷交替進(jìn)行。
Vapnik等人在多年研究統(tǒng)計學(xué)習(xí)理論基礎(chǔ)上對線性分類器提出了另一種設(shè)計最佳準(zhǔn)則。其原理也從線性可分說起，然后擴(kuò)展到線性不可分的情況。甚至擴(kuò)展到使用非線性函數(shù)中去，這種分類器被稱為支持向量機(jī)(Support?Vector?Machine,簡稱SVM)。支持向量機(jī)的提出有很深的理論背景。支持向量機(jī)方法是在近年來提出的一種新方法。
SVM的主要思想可以概括為兩點：?(1)?它是針對線性可分情況進(jìn)行分析，對于線性不可分的情況，通過使用非線性映射算法將低維輸入空間線性不可分的樣本轉(zhuǎn)化為高維特征空間使其線性可分，從而使得高維特征空間采用線性算法對樣本的非線性特征進(jìn)行線性分析成為可能；(2)?它基于結(jié)構(gòu)風(fēng)險最小化理論之上在特征空間中建構(gòu)最優(yōu)分割超平面，使得學(xué)習(xí)器得到全局最優(yōu)化,并且在整個樣本空間的期望風(fēng)險以某個概率滿足一定上界。
在學(xué)習(xí)這種方法時，首先要弄清楚這種方法考慮問題的特點，這就要從線性可分的最簡單情況討論起，在沒有弄懂其原理之前，不要急于學(xué)習(xí)線性不可分 等較復(fù)雜的情況，支持向量機(jī)在設(shè)計時，需要用到條件極值問題的求解，因此需用拉格朗日乘子理論，但對多數(shù)人來說，以前學(xué)到的或常用的是約束條件為等式表示 的方式，但在此要用到以不等式作為必須滿足的條件，此時只要了解拉格朗日理論的有關(guān)結(jié)論就行。
介紹
支持向量機(jī)將向量映射到一個更高維的空間里，在這個空間里建立有一個最大間隔超平面。在分開數(shù)據(jù)的超平面的兩邊建有兩個互相平行的超平面。分隔超平面使兩個平行超平面的距離最大化。假定平行超平面間的距離或差距越大，分類器的總誤差越小。一個極好的指南是C.J.C?Burges的《模式識別支持向量機(jī)指南》。van?der?Walt?和?Barnard?將支持向量機(jī)和其他分類器進(jìn)行了比較。
動機(jī)
?
有很多個分類器(超平面）可以把數(shù)據(jù)分開，但是只有一個能夠達(dá)到最大分割。我們通常希望分類的過程是一個機(jī)器學(xué)習(xí)的過程。這些數(shù)據(jù)點并不需要是中的點，而可以是任意(統(tǒng)計學(xué)符號)中或者?(計算機(jī)科學(xué)符號)?的點。我們希望能夠把這些點通過一個n-1維的超平面分開，通常這個被稱為線性分類器。有很多分類器都符合這個要求，但是我們還希望找到分類最佳的平面，即使得屬于兩個不同類的數(shù)據(jù)點間隔最大的那個面，該面亦稱為最大間隔超平面。如果我們能夠找到這個面，那么這個分類器就稱為最大間隔分類器。
問題定義
設(shè)樣本屬于兩個類，用該樣本訓(xùn)練svm得到的最大間隔超平面。在超平面上的樣本點也稱為支持向量.我們考慮以下形式的樣本點
其中ci為1或?1?--用以表示數(shù)據(jù)點屬于哪個類.??是一個p???(統(tǒng)計學(xué)符號),?或?n???(計算機(jī)科學(xué)符號)?維向量，其每個元素都 被縮放到[0,1]或[-1,1].縮放的目的是防止方差大的隨機(jī)變量主導(dǎo)分類過程.我們可以把這些數(shù)據(jù)稱為“訓(xùn)練數(shù)據(jù)”，希望我們的支持向量機(jī)能夠通過 一個超平面正確的把他們分開。超平面的數(shù)學(xué)形式可以寫作
根據(jù)幾何知識，我們知道向量垂直于分類超平面。加入位移b的目的是增加間隔.如果沒有b的話，那超平面將不得不通過原點，限制了這個方法的靈活性。
由于我們要求最大間隔，因此我們需要知道支持向量以及（與最佳超平面）平行的并且離支持向量最近的超平面。我們可以看到這些平行超平面可以由方程族：
來表示。
如果這些訓(xùn)練數(shù)據(jù)是線性可分的，那就可以找到這樣兩個超平面，在它們之間沒有任何樣本點并且這兩個超平面之間的距離也最大.通過幾何不難得到這兩個超平面之間的距離是?2/|w|，因此我們需要最小化?|w|。同時為了使得樣本數(shù)據(jù)點都在超平面的間隔區(qū)以外，我們需要保證對于所有的?i?滿足其中的一個條件
這兩個式子可以寫作：
原型
現(xiàn)在尋找最佳超平面這個問題就變成了在(1)這個約束條件下最小化|w|.這是一個二次規(guī)劃QP(quadratic?programming)最優(yōu)化中的問題。
更清楚的，它可以表示如下：
最小化,?滿足。
1/2?這個因子是為了數(shù)學(xué)上表達(dá)的方便加上的。
對偶型(Dual?Form)
把原型的分類規(guī)則寫作對偶型，可以看到分類器其實是一個關(guān)于支持向量（即那些在間隔區(qū)邊緣的訓(xùn)練樣本點）的函數(shù)。
支持向量機(jī)的對偶型如下：??并滿足αi?>?=?0
軟間隔
1995年,?Corinna?Cortes?與Vapnik?提出了一種改進(jìn)的最大間隔區(qū)方法，這種方法可以處理標(biāo)記錯誤的樣本。如果可區(qū)分正負(fù)例的超平面不存在，則“軟邊界”將選擇一個超平面盡可能清晰地區(qū)分樣本，同時使其與分界最清晰的樣本的距離最大化。這一成果使術(shù)語“支持向量機(jī)”（或“SVM”）得到推廣。這種方法引入了松馳參數(shù)ξi以衡量對數(shù)據(jù)xi的誤分類度。
隨后，將目標(biāo)函數(shù)與一個針對非0ξi的懲罰函數(shù)相加，在增大間距和縮小錯誤懲罰兩大目標(biāo)之間進(jìn)行權(quán)衡優(yōu)化。如果懲罰函數(shù)是一個線性函數(shù)，則等式(3)變形為
4、Apriori算法
Apriori算法是一種最有影響的挖掘布爾關(guān)聯(lián)規(guī)則頻繁項集的算法。其核心是基于兩階段頻集思想的遞推算法。該關(guān)聯(lián)規(guī)則在分類上屬于單維、單層、布爾關(guān)聯(lián)規(guī)則。在這里，所有支持度大于最小支持度的項集稱為頻繁項集，簡稱頻集。
Apriori演算法所使用的前置統(tǒng)計量包括了：
?最大規(guī)則物件數(shù)：規(guī)則中物件組所包含的最大物件數(shù)量
?最小支援：規(guī)則中物件或是物件組必頇符合的最低案例數(shù)
?最小信心水準(zhǔn)：計算規(guī)則所必須符合的最低信心水準(zhǔn)門檻
該算法的基本思想是：首先找出所有的頻集，這些項集出現(xiàn)的頻繁性至少和預(yù)定義的最小支持度一樣。然后由頻集產(chǎn)生強(qiáng)關(guān)聯(lián)規(guī)則，這些規(guī)則必須滿足最小支持度和最小可信度。然后使用第1步找到的頻集產(chǎn)生期望的規(guī)則，產(chǎn)生只包含集合的項的所有規(guī)則，其中每一條規(guī)則的右部只有一項，這里采用的是中規(guī)則的定義。一旦這些規(guī)則被生成，那么只有那些大于用戶給定的最小可信度的規(guī)則才被留下來。為了生成所有頻集，使用了遞推的方法。
可能產(chǎn)生大量的候選集,以及可能需要重復(fù)掃描數(shù)據(jù)庫，是Apriori算法的兩大缺點。
5、最大期望(EM)算法
在統(tǒng)計計算中，最大期望（EM，Expectation–Maximization）算法是在概率（probabilistic）模型中尋找參數(shù)最大似然估計的算法，其中概率模型依賴于無法觀測的隱藏變量（Latent?Variabl）。最大期望經(jīng)常用在機(jī)器學(xué)習(xí)和計算機(jī)視覺的數(shù)據(jù)集聚（Data?Clustering）領(lǐng)域。最大期望算法經(jīng)過兩個步驟交替進(jìn)行計算，第一步是計算期望（E），也就是將隱藏變量象能夠觀測到的一樣包含在內(nèi)從而計算最大似然的期望值；另外一步是最大化（M），也就是最大化在?E?步上找到的最大似然的期望值從而計算參數(shù)的最大似然估計。M?步上找到的參數(shù)然后用于另外一個?E?步計算，這個過程不斷交替進(jìn)行。
最大期望過程說明
我們用??表示能夠觀察到的不完整的變量值，用??表示無法觀察到的變量值，這樣??和??一起組成了完整的數(shù)據(jù)。?可能是實際測量丟失的數(shù)據(jù)，也可能是能夠簡化問題的隱藏變量，如果它的值能夠知道的話。例如，在混合模型（Mixture?Model）中，如果“產(chǎn)生”樣本的混合元素成分已知的話最大似然公式將變得更加便利（參見下面的例子）。
估計無法觀測的數(shù)據(jù)
讓??代表矢量?θ:??定義的參數(shù)的全部數(shù)據(jù)的概率分布（連續(xù)情況下）或者概率集聚函數(shù)（離散情況下），那么從這個函數(shù)就可以得到全部數(shù)據(jù)的最大似然值，另外，在給定的觀察到的數(shù)據(jù)條件下未知數(shù)據(jù)的條件分布可以表示為：
6、PageRank
PageRank是Google算法的重要內(nèi)容。2001年9月被授予美國專利，專利人是Google創(chuàng)始人之一拉里·佩奇（Larry?Page）。因此，PageRank里的page不是指網(wǎng)頁，而是指佩奇，即這個等級方法是以佩奇來命名的。
Google的?PageRank根據(jù)網(wǎng)站的外部鏈接和內(nèi)部鏈接的數(shù)量和質(zhì)量倆衡量網(wǎng)站的價值。PageRank背后的概念是，每個到頁面的鏈接都是對該頁面的一次投票，被鏈接的越多，就意味著被其他網(wǎng)站投票越多。這個就是所謂的“鏈接流行度”——衡量多少人愿意將他們的網(wǎng)站和你的網(wǎng)站掛鉤。PageRank這個概念引自學(xué)術(shù)中一篇論文的被引述的頻度——即被別人引述的次數(shù)越多，一般判斷這篇論文的權(quán)威性就越高。
Google有一套自動化方法來計算這些投票。Google的PageRank分值從0到?10；PageRank為10表示最佳，但非常少見，類似里氏震級（Richter?scale），PageRank級別也不是線性的，而是按照一種指數(shù)刻度。這是一種奇特的數(shù)學(xué)術(shù)語，意思是PageRank4不是比PageRank3好一級——而可能會好6到7倍。因此，一個PageRank5的網(wǎng)頁和PageRank8的網(wǎng)頁之間的差距會比你可能認(rèn)為的要大的多。
PageRank較高的頁面的排名往往要比PageRank較低的頁面高，而這導(dǎo)致了人們對鏈接的著魔。在整個SEO社區(qū)，人們忙于爭奪、交換甚至銷售鏈接，它是過去幾年來人們關(guān)注的焦點，以至于Google修改了他的系統(tǒng)，并開始放棄某些類型的鏈接。比如，被人們廣泛接受的一條規(guī)定，來自缺乏內(nèi)容的“link?farm”（鏈接工廠）網(wǎng)站的鏈接將不會提供頁面的PageRank，從PageRank較高的頁面得到鏈接但是內(nèi)容不相關(guān)（比如說某個流行的漫畫書網(wǎng)站鏈接到一個叉車規(guī)范頁面），也不會提供頁面的PageRank。Google選擇降低了PageRank對更新頻率，以便不鼓勵人們不斷的對其進(jìn)行監(jiān)測。
Google?PageRank一般一年更新四次，所以剛上線的新網(wǎng)站不可能獲得PR值。你的網(wǎng)站很可能在相當(dāng)長的時間里面看不到PR值的變化，特別是一些新的網(wǎng)站。PR值暫時沒有，這不是什么不好的事情，耐心等待就好了。
為您的網(wǎng)站獲取外部鏈接是一件好事，但是無視其他SEO領(lǐng)域的工作而進(jìn)行急迫的鏈接建設(shè)就是浪費時間，要時刻保持一個整體思路并記住以下幾點：
·Google的排名算法并不是完全基于外部鏈接的
·高PageRank并不能保證Google高排名
·PageRank值更新的比較慢，今天看到的PageRank值可能是三個月前的值
因此我們不鼓勵刻意的去追求PageRank，因為決定排名的因素可以有上百種。盡管如此，PageRank還是一個用來了解Google對您的網(wǎng)站頁面如何評價的相當(dāng)好的指示，建議網(wǎng)站設(shè)計者要充分認(rèn)識PageRank在Google判斷網(wǎng)站質(zhì)量中的重要作用，從設(shè)計前的考慮到后期網(wǎng)站更新都要給予PageRank足夠的分析，很好的利用。我們要將PageRank看作是一種業(yè)余愛好而不是一種信仰。
---------------------------------------------------------------------------------------------------------------------
通過對由超過?50,000?萬個變量和?20?億個詞匯組成的方程進(jìn)行計算，PageRank?能夠?qū)W(wǎng)頁的重要性做出客觀的評價。PageRank?并不計算直接鏈接的數(shù)量，而是將從網(wǎng)頁?A?指向網(wǎng)頁?B?的鏈接解釋為由網(wǎng)頁?A?對網(wǎng)頁?B?所投的一票。這樣，PageRank?會根據(jù)網(wǎng)頁?B?所收到的投票數(shù)量來評估該頁的重要性。
此外，PageRank?還會評估每個投票網(wǎng)頁的重要性，因為某些網(wǎng)頁的投票被認(rèn)為具有較高的價值，這樣，它所鏈接的網(wǎng)頁就能獲得較高的價值。重要網(wǎng)頁獲得的?PageRank（網(wǎng)頁排名）較高，從而顯示在搜索結(jié)果的頂部。Google?技術(shù)使用網(wǎng)上反饋的綜合信息來確定某個網(wǎng)頁的重要性。搜索結(jié)果沒有人工干預(yù)或操縱，這也是為什么?Google?會成為一個廣受用戶信賴、不受付費排名影響且公正客觀的信息來源。
－－－－－－－－－－－－－－－
其實簡單說就是民主表決。打個比方，假如我們要找李開復(fù)博士，有一百個人舉手說自己是李開復(fù)。那么誰是真的呢？也許有好幾個真的，但即使如此誰又是大家真正想找的呢？:-)?如果大家都說在?Google?公司的那個是真的，那么他就是真的。
在互聯(lián)網(wǎng)上，如果一個網(wǎng)頁被很多其它網(wǎng)頁所鏈接，說明它受到普遍的承認(rèn)和信賴，那么它的排名就高。這就是?Page?Rank?的核心思想。?當(dāng)然?Google?的?Page?Rank?算法實際上要復(fù)雜得多。比如說，對來自不同網(wǎng)頁的鏈接對待不同，本身網(wǎng)頁排名高的鏈接更可靠，于是給這些鏈接予較大的權(quán)重。Page?Rank?考慮了這個因素，可是現(xiàn)在問題又來了，計算搜索結(jié)果的網(wǎng)頁排名過程中需要用到網(wǎng)頁本身的排名，這不成了先有雞還是先有蛋的問題了嗎？
Google?的兩個創(chuàng)始人拉里·佩奇?（Larry?Page?）和謝爾蓋·布林?(Sergey?Brin)?把 這個問題變成了一個二維矩陣相乘的問題，并且用迭代的方法解決了這個問題。他們先假定所有網(wǎng)頁的排名是相同的，并且根據(jù)這個初始值，算出各個網(wǎng)頁的第一次 迭代排名，然后再根據(jù)第一次迭代排名算出第二次的排名。他們兩人從理論上證明了不論初始值如何選取，這種算法都保證了網(wǎng)頁排名的估計值能收斂到他們的真實 值。值得一提的事，這種算法是完全沒有任何人工干預(yù)的。
理論問題解決了，又遇到實際問題。因為互聯(lián)網(wǎng)上網(wǎng)頁的數(shù)量是巨大的，上面提到的二維矩陣從理論上講有網(wǎng)頁數(shù)目平方之多個元素。如果我們假定有十 億個網(wǎng)頁，那么這個矩陣就有一百億億個元素。這樣大的矩陣相乘，計算量是非常大的。拉里和謝爾蓋兩人利用稀疏矩陣計算的技巧，大大的簡化了計算量，并實現(xiàn) 了這個網(wǎng)頁排名算法。今天?Google?的工程師把這個算法移植到并行的計算機(jī)中，進(jìn)一步縮短了計算時間，使網(wǎng)頁更新的周期比以前短了許多。
我來?Google?后，拉里?(Larry)?在和我們幾個新員工座談時，講起他當(dāng)年和謝爾蓋(Sergey)?是怎么想到網(wǎng)頁排名算法的。他說："當(dāng)時我們覺得整個互聯(lián)網(wǎng)就像一張大的圖（Graph)，每個網(wǎng)站就像一個節(jié)點，而每個網(wǎng)頁的鏈接就像一個弧。我想，互聯(lián)網(wǎng)可以用一個圖或者矩陣描述，我也許可以用這個發(fā)現(xiàn)做個博士論文。"?他和謝爾蓋就這樣發(fā)明了?Page?Rank?的算法。
網(wǎng)頁排名的高明之處在于它把整個互聯(lián)網(wǎng)當(dāng)作了一個整體對待。它無意識中符合了系統(tǒng)論的觀點。相比之下，以前的信息檢索大多把每一個網(wǎng)頁當(dāng)作獨立的個體對待，很多人當(dāng)初只注意了網(wǎng)頁內(nèi)容和查詢語句的相關(guān)性，忽略了網(wǎng)頁之間的關(guān)系。?
今天，Google?搜索引擎比最初復(fù)雜、完善了許多。但是網(wǎng)頁排名在?Google?所有算法中依然是至關(guān)重要的。在學(xué)術(shù)界,?這個算法被公認(rèn)為是文獻(xiàn)檢索中最大的貢獻(xiàn)之一，并且被很多大學(xué)引入了信息檢索課程?(Information?Retrieval)?的教程。?
如何提高你網(wǎng)頁的?PR?值？
什么是PR值呢??PR值全稱為PageRank，PR是英文Pagerank?的縮寫形式，Pagerank取自Google的創(chuàng)始人LarryPage，它是Google排名運算法則（排名公式）的一部分，Pagerank是?Google對網(wǎng)頁重要性的評估，是Google用來衡量一個網(wǎng)站的好壞的唯一標(biāo)準(zhǔn)。PageRank(網(wǎng)頁級別)是Google用于評測一個網(wǎng)頁“重要性”的一種方法。在揉合了諸如Title標(biāo)識和Keywords標(biāo)識等所有其它因素之后，Google通過PageRank來調(diào)整結(jié)果，使那些更具“重要性”的網(wǎng)頁在搜索結(jié)果中另網(wǎng)站排名獲得提升，從而提高搜索結(jié)果的相關(guān)性和質(zhì)量。?PR值的級別從1到10級，10級為滿分。PR值越高說明該網(wǎng)頁越受歡迎。Google把自己的網(wǎng)站的PR值定到10，這說明Google這個網(wǎng)站是非常受歡迎的，也可以說這個網(wǎng)站非常重要。Google大受青睞的另一個原因就是它的網(wǎng)站索引速度。向Google提交你的網(wǎng)站直到為Google收錄，一般只需兩個星期。如果你的網(wǎng)站已經(jīng)為Google收錄，那么通常Google會每月一次遍歷和更新(重新索引)你的網(wǎng)站信息。不過對于那些PR值?(Pagerank)較高的網(wǎng)站，Google索引周期會相應(yīng)的短一些。一個PR值為1的網(wǎng)站表明這個網(wǎng)站不太具有流行度，而PR值為7到10則表明這個網(wǎng)站非常受歡迎。PR值最高為10，一般PR值達(dá)到4，就算是一個不錯的網(wǎng)站了。那么PR值都受那些因素影響呢？下面我們一起來看看。
第一：網(wǎng)站外部鏈接的數(shù)量和質(zhì)量
在計算網(wǎng)站排名時，Pagerank會將網(wǎng)站的外部鏈接數(shù)考慮進(jìn)去。并不能說一個網(wǎng)站的外部鏈接數(shù)越多其PR值就越高，如果這樣的話，一個網(wǎng)站盡可能獲得最多的外部鏈接就OK了，有這種想法是錯誤的。Google對一個網(wǎng)站上的外部鏈接數(shù)的重視程度并不意味著你因此可以不求策略地與任何網(wǎng)站建立連接。這是因為Google并不是簡單地由計算網(wǎng)站的外部鏈接數(shù)來決定其等級。Google的?Pagerank系統(tǒng)不單考慮一個網(wǎng)站的外部鏈接質(zhì)量，也會考慮其數(shù)量。這個問題看來很有復(fù)雜。首先讓我們來解釋一下什么是阻尼因數(shù)(damping?factor)。阻尼因素就是當(dāng)你投票或鏈接到另外一個站點時所獲得的實際PR分值。阻尼因數(shù)一般是0.85。當(dāng)然比起你網(wǎng)站的實際PR值，它就顯得微不足道了。?
現(xiàn)在讓我們來看看這個PR分值的計算公式：PR(A)=(1-?d)+d(PR(t1)/C(t1)+...+PR(tn)/C(tn))?公式解釋：其中PR(A)表示的是從一個外部鏈接站點t1上，依據(jù)Pagerank?系統(tǒng)給你的網(wǎng)站所增加的PR分值；PR(t1)表示該外部鏈接網(wǎng)站本身的PR分值；C(t1)則表示該外部鏈接站點所擁有的外部鏈接數(shù)量。大家要謹(jǐn)記：一個網(wǎng)站的投票權(quán)值只有該網(wǎng)站PR分值的0.85，?
那么，是不是說對一個網(wǎng)站而言，它所擁有的較高網(wǎng)站質(zhì)量和較高PR分值的外部鏈接數(shù)量越多就越好呢？錯，因為－Google的Pagerank系統(tǒng)不單考慮一個網(wǎng)站的外部鏈接質(zhì)量，也會考慮其數(shù)量.比方說，對一個有一定PR值的網(wǎng)站X來說，如果你的網(wǎng)站Y是它的唯一一個外部鏈接，那么Google就相信網(wǎng)站X將你的網(wǎng)站Y視做它最好的一個外部鏈接，從而會給你的網(wǎng)站Y更多的分值。可是，如果網(wǎng)站X?上已經(jīng)有49個外部鏈接，那么Google就相信網(wǎng)站X只是將你的網(wǎng)站視做它第50個好的網(wǎng)站。因而你的外部鏈接站點上的外部鏈接數(shù)越多，你所能夠得到的?PR分值反而會越低，它們呈反比關(guān)系。
說它對是因為－一般情況下，一個PR分值大于等于6的外部鏈接站點，可顯著提升你的PR分值。但如果這個外部鏈接站點已經(jīng)有100個其它的外部鏈接時，那你能夠得到的PR分值就幾乎為零了。同樣，如果一個外部鏈接站點的PR值僅為2，但你卻是它的唯一一個外部鏈接，那么你所獲得的PR值要遠(yuǎn)遠(yuǎn)大于那個PR值為6，外部鏈接數(shù)為100的網(wǎng)站。?
而且這個0.85的權(quán)值平均分配給其鏈接的每個外部網(wǎng)站。?
第二：Google在你的網(wǎng)站抓取的頁面數(shù)
Google在你的網(wǎng)站抓取的頁面數(shù)，數(shù)目越多，Pagerank值越高。但通常Google?并不會主動抓取你的網(wǎng)站的所有頁面，尤其是網(wǎng)址里帶有“?”的動態(tài)鏈接，Google不主動，那就要我們主動了，最笨的辦法是把網(wǎng)站所有的頁面都提交給?Google，但我想沒有誰真會這么做，但頁面不多的話可以試試。更好的辦法是制作一個靜態(tài)Html頁面，通常被稱作“網(wǎng)站地圖”或“網(wǎng)站導(dǎo)航”，它里面包含你要添加的所有網(wǎng)址，然后把這個靜態(tài)頁面提交給Google。
第三：網(wǎng)站被世界三大知名網(wǎng)站?DMOZ，Yahoo和Looksmart?收錄
眾所周知，Google的Pagerank系統(tǒng)對那些門戶網(wǎng)絡(luò)目錄如DMOZ，Yahoo和?Looksmart尤為器重。特別是對DMOZ。一個網(wǎng)站上的DMOZ鏈接對Google的Pagerank?來說，就好像一塊金子一樣珍貴。如果你的網(wǎng)站為ODP收錄，則可有效提升你的頁面等級。向ODP提交你的站點并為它收錄，其實并不是一件難事，只是要多花點時間而已。只要確保你的網(wǎng)站提供了良好的內(nèi)容，然后在ODP合適的目錄下點擊"增加站點"，按照提示一步步來就OK了。至少要保證你的索引頁(INDEX?PAGE)被收錄進(jìn)去。所以，如果你的網(wǎng)站內(nèi)容涉及完全不同的幾塊內(nèi)容，你可以把每個內(nèi)容的網(wǎng)頁分別向ODP提交－不過請記住"欲速則不達(dá)"。等到?Google對其目錄更新后，你就能看到你的PR值會有什么變化了。如果你的網(wǎng)站為Yahoo和Looksmart所收錄，那么你的PR值會得到顯著提升。如果你的網(wǎng)站是非商業(yè)性質(zhì)的或幾乎完全是非商業(yè)性質(zhì)的內(nèi)容，那么你可以通過zeall.com使你的網(wǎng)站為著名的網(wǎng)絡(luò)目錄Looksmart所收錄。?Looksmart也是從Zeal網(wǎng)絡(luò)目錄獲得非商業(yè)搜索列表。?
Google?PR值的更新周期是多長時間？
一般情況下PR值更新的周期是2.5～3個月！最近一次PR更新是2008年1月中旬。?
PageRank相關(guān)算法總結(jié)：
1.PageRank
基本思想：如果網(wǎng)頁T存在一個指向網(wǎng)頁A的連接，則表明T的所有者認(rèn)為A比較重要，從而把T的一部分重要性得分賦予A。這個重要性得分值為：PR（T）/C(T)
其中PR（T）為T的PageRank值，C(T)為T的出鏈數(shù)，則A的PageRank值為一系列類似于T的頁面重要性得分值的累加。
優(yōu)點：是一個與查詢無關(guān)的靜態(tài)算法，所有網(wǎng)頁的PageRank值通過離線計算獲得；有效減少在線查詢時的計算量，極大降低了查詢響應(yīng)時間。
不足：人們的查詢具有主題特征，PageRank忽略了主題相關(guān)性，導(dǎo)致結(jié)果的相關(guān)性和主題性降低；另外，PageRank有很嚴(yán)重的對新網(wǎng)頁的歧視。
2.Topic-Sensitive?PageRank（主題敏感的PageRank）
基本思想：針對PageRank對主題的忽略而提出。核心思想：通過離線計算出一個?PageRank向量集合，該集合中的每一個向量與某一主題相關(guān)，即計算某個頁面關(guān)于不同主題的得分。主要分為兩個階段：主題相關(guān)的PageRank向量集合的計算和在線查詢時主題的確定。
優(yōu)點：根據(jù)用戶的查詢請求和相關(guān)上下文判斷用戶查詢相關(guān)的主題（用戶的興趣）返回查詢結(jié)果準(zhǔn)確性高。
不足：沒有利用主題的相關(guān)性來提高鏈接得分的準(zhǔn)確性。
3.Hilltop
基本思想：與PageRank的不同之處：僅考慮專家頁面的鏈接。主要包括兩個步驟：專家頁面搜索和目標(biāo)頁面排序。
優(yōu)點：相關(guān)性強(qiáng)，結(jié)果準(zhǔn)確。
不足：專家頁面的搜索和確定對算法起關(guān)鍵作用，專家頁面的質(zhì)量決定了算法的準(zhǔn)確性，而專家頁面的質(zhì)量和公平性難以保證；忽略了大量非專家頁面的影響，不能反應(yīng)整個Internet的民意；當(dāng)沒有足夠的專家頁面存在時，返回空，所以Hilltop適合對于查詢排序進(jìn)行求精。
那么影響google?PageRank的因素有哪些呢?
1?與pr高的網(wǎng)站做鏈接:
2?內(nèi)容質(zhì)量高的網(wǎng)站鏈接
3加入搜索引擎分類目錄
4?加入免費開源目錄
5?你的鏈接出現(xiàn)在流量大、知名度高、頻繁更新的重要網(wǎng)站上
6google對DPF格式的文件比較看重。
7安裝Google工具條
8域名和tilte標(biāo)題出現(xiàn)關(guān)鍵詞與meta標(biāo)簽等
9反向連接數(shù)量和反向連接的等級
10Google抓取您網(wǎng)站的頁面數(shù)量
11導(dǎo)出鏈接數(shù)量
PageRank科學(xué)排名遏止關(guān)鍵字垃圾
目前，五花八門的網(wǎng)站為爭奪網(wǎng)上排名采用惡意點擊和輸入關(guān)鍵字垃圾的手段來吸引網(wǎng)民的眼球，無論對于互聯(lián)網(wǎng)企業(yè)還是互聯(lián)網(wǎng)用戶，這都不是一個好現(xiàn)象。
為了解決這樣的問題，Google?創(chuàng)始人之一拉里.佩奇（Larry?Page）發(fā)明了一種算法PageRank，是由搜索引擎根據(jù)網(wǎng)頁之間相互的超鏈接進(jìn)行計算的網(wǎng)頁排名。它經(jīng)常和搜索引擎優(yōu)化有關(guān)。PageRank?系統(tǒng)目前被Google?用來體現(xiàn)網(wǎng)頁的相關(guān)性和重要性，以便科學(xué)排名，遏止關(guān)鍵字垃圾。
PageRank這個概念引自一篇學(xué)術(shù)論文的被媒體轉(zhuǎn)載的頻度，一般被轉(zhuǎn)載的次數(shù)越多，這篇論文的權(quán)威性就越高，價值也就越高。PageRank是1998年在斯坦福大學(xué)問世的，2001
年9?月被授予美國專利。如今它在?Google?所有算法中依然是至關(guān)重要的。在學(xué)術(shù)界,?這個算法被公認(rèn)為是文獻(xiàn)檢索中最大的貢獻(xiàn)之一，并且被很多大學(xué)引入了信息檢索課程(Information?Retrieval)?的教程。
PageRank?通過對由超過?5?億個變量和?20?億個詞匯組成的方程進(jìn)行計算，能科學(xué)公正地標(biāo)識網(wǎng)頁的等級或重要性。PR級別為1到10，PR值越高說明該網(wǎng)頁越重要。例如：一個PR?值為1?的網(wǎng)站表明這個網(wǎng)站不太具有流行度，而PR?值為7到10則表明這個網(wǎng)站極其重要。PageRank級別不是一般的算術(shù)級數(shù)，而是按照一種幾何級數(shù)來劃分的。PageRank3?不是比PageRank2?好一級，而可能會好到數(shù)倍。
PageRank根據(jù)網(wǎng)站的外部鏈接和內(nèi)部鏈接的數(shù)量和質(zhì)量來衡量網(wǎng)站的價值。?PageRank的概念是，每個到頁面的鏈接都是對該頁面的一次投票，被鏈接得越多，就意味著被其他網(wǎng)站投票越多。Google?有一套自動化方法來計算這些投票，但Google?的排名算法不完全基于外部鏈接。PageRank?對來自不同網(wǎng)頁的鏈接會區(qū)別對待，來自網(wǎng)頁本身排名高的鏈接更受青睞，給這些鏈接有較大的權(quán)重。
同時，Google?不只是看一個網(wǎng)站的投票數(shù)量，或者這個網(wǎng)站的外部鏈接數(shù)量。它會對那些投票的網(wǎng)站進(jìn)行分析。如果這些網(wǎng)站的PR?值比較高，則其投票的網(wǎng)站可從中受益。因此，Google?的技術(shù)專家提醒人們，在建設(shè)網(wǎng)站的外部鏈接時，應(yīng)盡可能瞄準(zhǔn)那些PR?值高且外部鏈接數(shù)又少的網(wǎng)站。這樣的外部鏈接站點越多，你的PR?值就會越高，從而使得你的Google?排名得到顯著提升。
PageRank的另一作用是對關(guān)鍵字垃圾起到巨大的遏制作用。眼下，一些垃圾網(wǎng)站為了提高點擊率，用一些與站點內(nèi)容無關(guān)的關(guān)鍵字垃圾壯聲威，比如用明星的名字、用公共突
發(fā)事件稱謂等。這些網(wǎng)頁的目的或是為了騙取廣告點擊，或是為了傳播病毒。還有一些無賴式的博客評論也從中攪局，在網(wǎng)上招搖過市，騙取網(wǎng)民的注意力，這也被網(wǎng)絡(luò)技術(shù)人員
視為垃圾。
PageRank目前使用一種基于信任和名譽的算法幫助遏止關(guān)鍵字垃圾，它忽視這些關(guān)鍵字垃圾的存在，以網(wǎng)頁相互鏈接評級別論高低。Google?排名之所以大受追捧，是由于它并非
只使用關(guān)鍵字或代理搜索技術(shù)，?而是將自身建立在高級的網(wǎng)頁級別技術(shù)基礎(chǔ)之上。別的搜索引擎提供給搜索者的是多種渠道值為?8?的網(wǎng)站信息得來的一個粗略的搜索結(jié)果，而Google?提供給它的搜索者的則是它自己產(chǎn)生的高度精確的搜索結(jié)果。這就是為什么網(wǎng)站管理員會千方百計去提高自己網(wǎng)站在Google?的排名了。
PageRank一般一年更新四次，所以剛上線的新網(wǎng)站不可能獲得PR?值。不過PR?值暫時沒有，并不是什么不好的事情，耐心等待就能得到Google?的青睞。
7、AdaBoost
Adaboost是一種迭代算法，其核心思想是針對同一個訓(xùn)練集訓(xùn)練不同的分類器(弱分類器)，然后把這些弱分類器集合起來，構(gòu)成一個更強(qiáng)的最終分類器?(強(qiáng)分類器)。其算法本身是通過改變數(shù)據(jù)分布來實現(xiàn)的，它根據(jù)每次訓(xùn)練集之中每個樣本的分類是否正確，以及上次的總體分類的準(zhǔn)確率，來確定每個樣本的權(quán)值。將修改過權(quán)值的新數(shù)據(jù)集送給下層分類器進(jìn)行訓(xùn)練，最后將每次訓(xùn)練得到的分類器最后融合起來，作為最后的決策分類器。使用adaboost分類器可以排除一些不必要的訓(xùn)練數(shù)據(jù)特徵，并將關(guān)鍵放在關(guān)鍵的訓(xùn)練數(shù)據(jù)上面。
目前，對adaboost算法的研究以及應(yīng)用大多集中于分類問題，同時近年也出?現(xiàn)了一些在回歸問題上的應(yīng)用。就其應(yīng)用adaboost系列主要解決了:?兩類問題、?多類單標(biāo)簽問題、多類多標(biāo)簽問題、大類單標(biāo)簽問題，回歸問題。它用全部的訓(xùn)練樣本進(jìn)行學(xué)習(xí)。
該算法其實是一個簡單的弱分類算法提升過程，這個過程通過不斷的訓(xùn)練，可以提高對數(shù)據(jù)的分類能力。整個過程如下所示：
1.?先通過對N個訓(xùn)練樣本的學(xué)習(xí)得到第一個弱分類器?；
2.?將?分錯的樣本和其他的新數(shù)據(jù)一起構(gòu)成一個新的N個的訓(xùn)練樣本，通過對這個樣本的學(xué)習(xí)得到第二個弱分類器?；
3.?將?和?都分錯了的樣本加上其他的新樣本構(gòu)成另一個新的N個的訓(xùn)練樣本，通過對這個樣本的學(xué)習(xí)得到第三個弱分類器?；
4.?最終經(jīng)過提升的強(qiáng)分類器?。即某個數(shù)據(jù)被分為哪一類要通過?，?……的多數(shù)表決。
2.3?Adaboost(Adaptive?Boosting)算法
對于boosting算法，存在兩個問題：
1.?如何調(diào)整訓(xùn)練集，使得在訓(xùn)練集上訓(xùn)練的弱分類器得以進(jìn)行；
2.?如何將訓(xùn)練得到的各個弱分類器聯(lián)合起來形成強(qiáng)分類器。
針對以上兩個問題，adaboost算法進(jìn)行了調(diào)整：
1.?使用加權(quán)后選取的訓(xùn)練數(shù)據(jù)代替隨機(jī)選取的訓(xùn)練樣本，這樣將訓(xùn)練的焦點集中在比較難分的訓(xùn)練數(shù)據(jù)樣本上；
2.?將弱分類器聯(lián)合起來，使用加權(quán)的投票機(jī)制代替平均投票機(jī)制。讓分類效果好的弱分類器具有較大的權(quán)重，而分類效果差的分類器具有較小的權(quán)重。
Adaboost算法是Freund和Schapire根據(jù)在線分配算法提出的，他們詳細(xì)分析了Adaboost算法錯誤率?的上界，以及為了使強(qiáng)分類器?達(dá)到錯誤率，算法所需要的最多迭代次數(shù)等相關(guān)問題。與Boosting算法不同的是，adaboost算法不需要預(yù)先知道弱學(xué)習(xí)算法學(xué)習(xí)正確率的下限即弱分類器的誤差，并且最后得到的強(qiáng)分類器的分類精度依賴于所有弱分類器的分類精度，?這樣可以深入挖掘弱分類器算法的能力。
Adaboost算法中不同的訓(xùn)練集是通過調(diào)整每個樣本對應(yīng)的權(quán)重來實現(xiàn)的。開始時，每個樣本對應(yīng)的權(quán)重是相同的，即?其中?n?為樣本個數(shù)，在此樣本分布下訓(xùn)練出一弱分類器?。對于分類錯誤的樣本，加大其對應(yīng)的權(quán)重；而對于分類正確的樣本，降低其權(quán)重，這樣分錯的樣本就被突出出來，從而得到一個新的樣本分布。在新的樣本分布下，再次對弱分類器進(jìn)行訓(xùn)練，得到弱分類器。依次類推，經(jīng)過?T?次循環(huán)，得到?T?個弱分類器，把這?T?個弱分類器按一定的權(quán)重疊加（boost）起來，得到最終想要的強(qiáng)分類器。
Adaboost算法的具體步驟如下：
1.?給定訓(xùn)練樣本集?，其中?分別對應(yīng)于正例樣本和負(fù)例樣本；?為訓(xùn)練的最大循環(huán)次數(shù)；
2.?初始化樣本權(quán)重?，即為訓(xùn)練樣本的初始概率分布；
3.?第一次迭代：
(1)?訓(xùn)練樣本的概率分布?下，訓(xùn)練弱分類器：
(2)?計算弱分類器的錯誤率：
(3)?選取?，使得?最小
(4)?更新樣本權(quán)重：
(5)?最終得到的強(qiáng)分類器：
Adaboost算法是經(jīng)過調(diào)整的Boosting算法，其能夠?qū)θ鯇W(xué)習(xí)得到的弱分類器的錯誤進(jìn)行適應(yīng)性調(diào)整。上述算法中迭代了?次的主循環(huán)，每一次循環(huán)根據(jù)當(dāng)前的權(quán)重分布對樣本x定一個分布P， 然后對這個分布下的樣本使用若學(xué)習(xí)算法得到一個錯誤率為?的弱分類器?，對于這個算法定義的弱學(xué)習(xí)算法，對所有的?，都有，而這個錯誤率的上限并不需要事 先知道，實際上。每一次迭代，都要對權(quán)重進(jìn)行更新。更新的規(guī)則是：減小弱分類器分類效果較好的數(shù)據(jù)的概率，增大弱分類器分類效果較差的數(shù)據(jù)的概率。最終的 分類器是個弱分類器的加權(quán)平均。
8、k-nearest?neighbor?classification
鄰近算法
KNN算法的決策過程 k-Nearest?Neighbor?algorithm?
右圖中，綠色圓要被決定賦予哪個類，是紅色三角形還是藍(lán)色四方形？如果K=3，由于紅色三角形所占比例為2/3，綠色圓將被賦予紅色三角形那個類，如果K=5，由于藍(lán)色四方形比例為3/5，因此綠色圓被賦予藍(lán)色四方形類。
K最近鄰(k-Nearest?Neighbor，KNN)分類算法，是一個理論上比較成熟的方法，也是最簡單的機(jī)器學(xué)習(xí)算法之一。該方法的思路是：如果一個樣本在特征空間中的k個最相似(即特征空間中最鄰近)的樣本中的大多數(shù)屬于某一個類別，則該樣本也屬于這個類別。KNN算法中，所選擇的鄰居都是已經(jīng)正確分類的對象。該方法在定類決策上只依據(jù)最鄰近的一個或者幾個樣本的類別來決定待分樣本所屬的類別。?KNN方法雖然從原理上也依賴于極限定理，但在類別決策時，只與極少量的相鄰樣本有關(guān)。由于KNN方法主要靠周圍有限的鄰近的樣本，而不是靠判別類域的方法來確定所屬類別的，因此對于類域的交叉或重疊較多的待分樣本集來說，KNN方法較其他方法更為適合。
KNN算法不僅可以用于分類，還可以用于回歸。通過找出一個樣本的k個最近鄰居，將這些鄰居的屬性的平均值賦給該樣本，就可以得到該樣本的屬性。更有用的方法是將不同距離的鄰居對該樣本產(chǎn)生的影響給予不同的權(quán)值(weight)，如權(quán)值與距離成正比。
該算法在分類時有個主要的不足是，當(dāng)樣本不平衡時，如一個類的樣本容量很大，而其他類樣本容量很小時，有可能導(dǎo)致當(dāng)輸入一個新樣本時，該樣本的K個鄰居中大容量類的樣本占多數(shù)。因此可以采用權(quán)值的方法（和該樣本距離小的鄰居權(quán)值大）來改進(jìn)。該方法的另一個不足之處是計算量較大，因為對每一個待分類的文本都要計算它到全體已知樣本的距離，才能求得它的K個最近鄰點。目前常用的解決方法是事先對已知樣本點進(jìn)行剪輯，事先去除對分類作用不大的樣本。該算法比較適用于樣本容量比較大的類域的自動分類，而那些樣本容量較小的類域采用這種算法比較容易產(chǎn)生誤分。
9、貝葉斯分類器
貝葉斯分類器的分類原理是通過某對象的先驗概率，利用貝葉斯公式計算出其后驗概率，即該對象屬于某一類的概率，選擇具有最大后驗概率的類作為該對象所屬的類。目前研究較多的貝葉斯分類器主要有四種，分別是：Naive?Bayes、TAN、BAN和GBN。
貝葉斯網(wǎng)絡(luò)是一個帶有概率注釋的有向無環(huán)圖，圖中的每一個結(jié)點均表示一個隨機(jī)變量,圖中兩結(jié)點間若存在著一條弧，則表示這兩結(jié)點相對應(yīng)的隨機(jī)變量是概率相依的，反之則說明這兩個隨機(jī)變量是條件獨立的。網(wǎng)絡(luò)中任意一個結(jié)點X?均有一個相應(yīng)的條件概率表(Conditional?Probability?Table，CPT)，用以表示結(jié)點X?在其父結(jié)點取各可能值時的條件概率。若結(jié)點X?無父結(jié)點,則X?的CPT?為其先驗概率分布。貝葉斯網(wǎng)絡(luò)的結(jié)構(gòu)及各結(jié)點的CPT?定義了網(wǎng)絡(luò)中各變量的概率分布。
貝葉斯分類器是用于分類的貝葉斯網(wǎng)絡(luò)。該網(wǎng)絡(luò)中應(yīng)包含類結(jié)點C，其中C?的取值來自于類集合(?c1?,?c2?,?...?,?cm)，還包含一組結(jié)點X?=?(?X1?,?X2?,?...?,?Xn)，表示用于分類的特征。對于貝葉斯網(wǎng)絡(luò)分類器，若某一待分類的樣本D，其分類特征值為x?=?(?x1?,?x2?,?...?,?x?n)?，則樣本D?屬于類別ci?的概率P(?C?=?ci?|?X1?=?x1?,?X2?=?x?2?,?...?,?Xn?=?x?n)?，(?i?=?1?,2?,?...?,?m)?應(yīng)滿足下式：
P(?C?=?ci?|?X?=?x)?=?Max{?P(?C?=?c1?|?X?=?x)?,?P(?C?=?c2?|?X?=?x?)?,?...?,?P(?C?=?cm?|?X?=?x?)?}
而由貝葉斯公式：
P(?C?=?ci?|?X?=?x)?=?P(?X?=?x?|?C?=?ci)?*?P(?C?=?ci)?/?P(?X?=?x)
其中，P(?C?=?ci)?可由領(lǐng)域?qū)＜业慕?jīng)驗得到,而P(?X?=?x?|?C?=?ci)?和P(?X?=?x)?的計算則較困難。
應(yīng)用貝葉斯網(wǎng)絡(luò)分類器進(jìn)行分類主要分成兩階段。第一階段是貝葉斯網(wǎng)絡(luò)分類器的學(xué)習(xí)，即從樣本數(shù)據(jù)中構(gòu)造分類器，包括結(jié)構(gòu)學(xué)習(xí)和CPT?學(xué)習(xí)；第二階段是貝葉斯網(wǎng)絡(luò)分類器的推理，即計算類結(jié)點的條件概率，對分類數(shù)據(jù)進(jìn)行分類。這兩個階段的時間復(fù)雜性均取決于特征值間的依賴程度，甚至可以是?NP?完全問題，因而在實際應(yīng)用中，往往需要對貝葉斯網(wǎng)絡(luò)分類器進(jìn)行簡化。根據(jù)對特征值間不同關(guān)聯(lián)程度的假設(shè)，可以得出各種貝葉斯分類器，Naive?Bayes、TAN、BAN、GBN?就是其中較典型、研究較深入的貝葉斯分類器。
樸素貝葉斯
分類是將一個未知樣本分到幾個預(yù)先已知類的過程。數(shù)據(jù)分類問題的解決是一個兩步過程：第一步,建立一個模型，描述預(yù)先的數(shù)據(jù)集或概念集。通過分析由屬性描述的樣本（或?qū)嵗?#xff0c;對象等）來構(gòu)造模型。假定每一個樣本都有一個預(yù)先定義的類，由一個被稱為類標(biāo)簽的屬性確定。為建立模型而被分析的數(shù)據(jù)元組形成訓(xùn)練數(shù)據(jù)集，該步也稱作有指導(dǎo)的學(xué)習(xí)。
在眾多的分類模型中，應(yīng)用最為廣泛的兩種分類模型是決策樹模型(Decision?Tree?Model)和樸素貝葉斯模型（Naive?Bayesian?Model，NBC）。 決策樹模型通過構(gòu)造樹來解決分類問題。首先利用訓(xùn)練數(shù)據(jù)集來構(gòu)造一棵決策樹，一旦樹建立起來，它就可為未知樣本產(chǎn)生一個分類。在分類問題中使用決策樹模型 有很多的優(yōu)點，決策樹便于使用，而且高效；根據(jù)決策樹可以很容易地構(gòu)造出規(guī)則，而規(guī)則通常易于解釋和理解；決策樹可很好地擴(kuò)展到大型數(shù)據(jù)庫中，同時它的大 小獨立于數(shù)據(jù)庫的大小；決策樹模型的另外一大優(yōu)點就是可以對有許多屬性的數(shù)據(jù)集構(gòu)造決策樹。決策樹模型也有一些缺點，比如處理缺失數(shù)據(jù)時的困難，過度擬合 問題的出現(xiàn)，以及忽略數(shù)據(jù)集中屬性之間的相關(guān)性等。
和決策樹模型相比，樸素貝葉斯模型發(fā)源于古典數(shù)學(xué)理論，有著堅實的數(shù)學(xué)基礎(chǔ)，以及穩(wěn)定的分類效率。同時，NBC模型所需估計的參數(shù)很少，對缺失數(shù)據(jù)不太敏感，算法也比較簡單。理論上，NBC模型與其他分類方法相比具有最小的誤差率。但是實際上并非總是如此，這是因為NBC模型假設(shè)屬性之間相互獨立，這個假設(shè)在實際應(yīng)用中往往是不成立的，這給NBC模型的正確分類帶來了一定影響。在屬性個數(shù)比較多或者屬性之間相關(guān)性較大時，NBC模型的分類效率比不上決策樹模型。而在屬性相關(guān)性較小時，NBC模型的性能最為良好。
樸素貝葉斯模型：
----
Vmap=arg?max?P(?Vj?|?a1,a2...an)
Vj屬于V集合
其中Vmap是給定一個example,得到的最可能的目標(biāo)值.
其中a1...an是這個example里面的屬性.
這里面,Vmap目標(biāo)值,就是后面計算得出的概率最大的一個.所以用max?來表示
----
貝葉斯公式應(yīng)用到?P(?Vj?|?a1,a2...an)中.
可得到?Vmap=?arg?max?P(a1,a2...an?|?Vj?)?P(?Vj?)?/?P?(a1,a2...an)
又因為樸素貝葉斯分類器默認(rèn)a1...an他們互相獨立的.
所以P(a1,a2...an)對于結(jié)果沒有用處.?[因為所有的概率都要除同一個東西之后再比較大小,最后結(jié)果也似乎影響不大]
可得到Vmap=?arg?max?P(a1,a2...an?|?Vj?)?P(?Vj?)
然后
"樸素貝葉斯分類器基于一個簡單的假定：給定目標(biāo)值時屬性之間相互條件獨立。換言之。該假定說明給定實力的目標(biāo)值情況下。觀察到聯(lián)合的a1,a2...an的概率正好是對每個單獨屬性的概率乘積：?P(a1,a2...an?|?Vj?)?=?Π?i?P(?ai|?Vj?)
....
樸素貝葉斯分類器：Vnb?=arg?max?P(?Vj?)?Π?i?P?(?ai?|?Vj?)
"
Vnb?=?arg?max?P?(?Vj?)
此處Vj?(?yes?|?no?)，對應(yīng)天氣的例子。
10、分類與回歸樹
如果一個人必須去選擇在很大范圍的情形下性能都好的、同時不需要應(yīng)用開發(fā)者付出很多的努力并且易于被終端用戶理解的分類技術(shù)的話，那么Brieman,?Friedman,?Olshen和Stone（1984）提出的分類樹方法是一個強(qiáng)有力的競爭者。我們將首先討論這個分類的過程，然后在后續(xù)的節(jié)中我們將展示這個過程是如何被用來預(yù)測連續(xù)的因變量。Brieman等人用來實現(xiàn)這些過程的程序被稱為分類和回歸樹（CART,?Classification?and?Regression?Trees）方法。
分類樹
在分類樹下面有兩個關(guān)鍵的思想。第一個是關(guān)于遞歸地劃分自變量空間的想法；第二個想法是用驗證數(shù)據(jù)進(jìn)行剪枝。
遞歸劃分
讓我們用變量y表示因變量（分類變量），用x1,?x2,?x3,...,xp表示自變量。通過遞歸的方式把關(guān)于變量x的p維空間劃分為不重疊的矩形。這個劃分是以遞歸方式完成的。首先，一個自變量被選擇，比如xi和xi的一個值si，比方說選擇si把p維空間為兩部分：一部分是p維的超矩形，其中包含的點都滿足xi<=si，另一個p維超矩形包含所有的點滿足xi>si。接著，這兩部分中的一個部分通過選擇一個變量和該變量的劃分值以相似的方式被劃分。這導(dǎo)致了三個矩形區(qū)域（從這里往后我們把超矩形都說成矩形）。隨著這個過程的持續(xù)，我們得到的矩形越來越小。這個想法是把整個x空間劃分為矩形，其中的每個小矩形都盡可能是同構(gòu)的或“純”的。“純”的意思是（矩形）所包含的點都屬于同一類。我們認(rèn)為包含的點都只屬于一個類（當(dāng)然，這不總是可能的，因為經(jīng)常存在一些屬于不同類的點，但這些點的自變量有完全相同的值）。
1.?C4.5
C4.5算法是機(jī)器學(xué)習(xí)算法中的一種分類決策樹算法,其核心算法是ID3算法.??C4.5算法繼承了ID3算法的優(yōu)點，并在以下幾方面對ID3算法進(jìn)行了改進(jìn)：
1)?用信息增益率來選擇屬性，克服了用信息增益選擇屬性時偏向選擇取值多的屬性的不足；
????2)?在樹構(gòu)造過程中進(jìn)行剪枝；
????3)?能夠完成對連續(xù)屬性的離散化處理；
????4)?能夠?qū)Σ煌暾麛?shù)據(jù)進(jìn)行處理。
C4.5算法有如下優(yōu)點：產(chǎn)生的分類規(guī)則易于理解，準(zhǔn)確率較高。其缺點是：在構(gòu)造樹的過程中，需要對數(shù)據(jù)集進(jìn)行多次的順序掃描和排序，因而導(dǎo)致算法的低效。
2.?The?k-means?algorithm?即K-Means算法
k-means?algorithm算法是一個聚類算法，把n的對象根據(jù)他們的屬性分為k個分割，k?<?n。它與處理混合正態(tài)分布的最大期望算法很相似，因為他們都試圖找到數(shù)據(jù)中自然聚類的中心。它假設(shè)對象屬性來自于空間向量，并且目標(biāo)是使各個群組內(nèi)部的均方誤差總和最小。
3.?Support?vector?machines
支持向量機(jī)，英文為Support?Vector?Machine，簡稱SV機(jī)（論文中一般簡稱SVM）。 它是一種監(jiān)督式學(xué)習(xí)的方法，它廣泛的應(yīng)用于統(tǒng)計分類以及回歸分析中。支持向量機(jī)將向量映射到一個更高維的空間里，在這個空間里建立有一個最大間隔超平面。 在分開數(shù)據(jù)的超平面的兩邊建有兩個互相平行的超平面。分隔超平面使兩個平行超平面的距離最大化。假定平行超平面間的距離或差距越大，分類器的總誤差越小。 一個極好的指南是C.J.C?Burges的《模式識別支持向量機(jī)指南》。van?der?Walt?和?Barnard?將支持向量機(jī)和其他分類器進(jìn)行了比較。
4.?The?Apriori?algorithm
Apriori算法是一種最有影響的挖掘布爾關(guān)聯(lián)規(guī)則頻繁項集的算法。其核心是基于兩階段頻集思想的遞推算法。該關(guān)聯(lián)規(guī)則在分類上屬于單維、單層、布爾關(guān)聯(lián)規(guī)則。在這里，所有支持度大于最小支持度的項集稱為頻繁項集，簡稱頻集。?
5.?最大期望(EM)算法
在統(tǒng)計計算中，最大期望（EM，Expectation–Maximization）算法是在概率（probabilistic）模型中尋找參數(shù)最大似然估計的算法，其中概率模型依賴于無法觀測的隱藏變量（Latent?Variabl）。最大期望經(jīng)常用在機(jī)器學(xué)習(xí)和計算機(jī)視覺的數(shù)據(jù)集聚（Data?Clustering）領(lǐng)域。
6.?PageRank
PageRank是Google算法的重要內(nèi)容。2001年9月被授予美國專利，專利人是Google創(chuàng)始人之一拉里·佩奇（Larry?Page）。因此，PageRank里的page不是指網(wǎng)頁，而是指佩奇，即這個等級方法是以佩奇來命名的。?
PageRank根據(jù)網(wǎng)站的外部鏈接和內(nèi)部鏈接的數(shù)量和質(zhì)量倆衡量網(wǎng)站的價值。PageRank背后的概念是，每個到頁面的鏈接都是對該頁面的一次投票，被鏈接的越多，就意味著被其他網(wǎng)站投票越多。這個就是所謂的“鏈接流行度”——衡量多少人愿意將他們的網(wǎng)站和你的網(wǎng)站掛鉤。PageRank這個概念引自學(xué)術(shù)中一篇論文的被引述的頻度——即被別人引述的次數(shù)越多，一般判斷這篇論文的權(quán)威性就越高。
7.?AdaBoost
Adaboost是一種迭代算法，其核心思想是針對同一個訓(xùn)練集訓(xùn)練不同的分類器(弱分類器)，然后把這些弱分類器集合起來，構(gòu)成一個更強(qiáng)的最終分類器?(強(qiáng)分類器)。其算法本身是通過改變數(shù)據(jù)分布來實現(xiàn)的，它根據(jù)每次訓(xùn)練集之中每個樣本的分類是否正確，以及上次的總體分類的準(zhǔn)確率，來確定每個樣本的權(quán)值。將修改過權(quán)值的新數(shù)據(jù)集送給下層分類器進(jìn)行訓(xùn)練，最后將每次訓(xùn)練得到的分類器最后融合起來，作為最后的決策分類器。
8.?kNN:?k-nearest?neighbor?classification
K最近鄰(k-Nearest?Neighbor，KNN)分類算法，是一個理論上比較成熟的方法，也是最簡單的機(jī)器學(xué)習(xí)算法之一。該方法的思路是：如果一個樣本在特征空間中的k個最相似(即特征空間中最鄰近)的樣本中的大多數(shù)屬于某一個類別，則該樣本也屬于這個類別。?
9.?Naive?Bayes
在眾多的分類模型中，應(yīng)用最為廣泛的兩種分類模型是決策樹模型(Decision?Tree?Model)和樸素貝葉斯模型（Naive?Bayesian?Model，NBC）。?樸素貝葉斯模型發(fā)源于古典數(shù)學(xué)理論，有著堅實的數(shù)學(xué)基礎(chǔ)，以及穩(wěn)定的分類效率。同時，NBC模型所需估計的參數(shù)很少，對缺失數(shù)據(jù)不太敏感，算法也比較簡單。理論上，NBC模型與其他分類方法相比具有最小的誤差率。但是實際上并非總是如此，這是因為NBC模型假設(shè)屬性之間相互獨立，這個假設(shè)在實際應(yīng)用中往往是不成立的，這給NBC模型的正確分類帶來了一定影響。在屬性個數(shù)比較多或者屬性之間相關(guān)性較大時，NBC模型的分類效率比不上決策樹模型。而在屬性相關(guān)性較小時，NBC模型的性能最為良好。
10.?CART:?分類與回歸樹
CART,?Classification?and?Regression?Trees。?在分類樹下面有兩個關(guān)鍵的思想。第一個是關(guān)于遞歸地劃分自變量空間的想法；第二個想法是用驗證數(shù)據(jù)進(jìn)行剪枝。
轉(zhuǎn)載于:https://www.cnblogs.com/roland1982/p/3855856.html
總結(jié)
以上是生活随笔為你收集整理的经典的十个机器学习算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 对数据库连接池的理解
- 下一篇： AngularJs-指令和指令之间的交互