1、數(shù)據(jù)挖掘十大算法1 HYPERLINK /600009052/note/472629892 /600009052/note/472629892數(shù)據(jù)挖掘十大經(jīng)典算法國際權(quán)威的學(xué)術(shù)組織 the IEEE International Conference on Data Mining （ICDM） 2006年 12 月評選出 了數(shù)據(jù)挖掘領(lǐng)域的十大經(jīng)典算法：C4.5, k-Means, SVM, Apriori, EM, PageRank, AdaBoost, kNN, Naive Bayes, and CART.不僅僅是選中的十大算法，其實參加評選的18種算法，實際上隨便拿出一種來都可以稱得上是經(jīng)典

2、 算法，它們在數(shù)據(jù)挖掘領(lǐng)域都產(chǎn)生了極為深遠(yuǎn)的影響。1C45C4.5算法是機器學(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)致算法的低效。The k-means algorithm 即 K-Means 算

3、法k-means algorithm算法是一個聚類算法，把n的對象根據(jù)他們的屬性分為k個分割，k n。它與處 理混合正態(tài)分布的最大期望算法很相似，因為他們都試圖找到數(shù)據(jù)中自然聚類的中心。它假設(shè)對象屬 性來自于空間向量，并且目標(biāo)是使各個群組內(nèi)部的均方誤差總和最小。Support vector machines支持向量機，英文為Support Vector Machine，簡稱SV機（論文中一般簡稱SVM）。它是一種盈督 式孥者的方法，它廣泛的應(yīng)用于統(tǒng)計分類以及回歸分析中。支持向量機將向量映射到一個更高維的空 間里，在這個空間里建立有一個最大間隔超平面。在分開數(shù)據(jù)的超平面的兩邊建有兩個互相平行的超

4、 平面。分隔超平面使兩個平行超平面的距離最大化。假定平行超平面間的距離或差距越大，分類器的 總誤差越小。一個極好的指南是C.J.C Burges的模式識別支持向量機指南。van der Walt和 Barnard將支持向量機和其他分類器進(jìn)行了比較。The Apriori algorithmApriori算法是一種最有影響的挖掘布爾關(guān)聯(lián)規(guī)則頻繁項集的算法。其核心是基于兩階段頻集思想的遞 推算法。該關(guān)聯(lián)規(guī)則在分類上屬于單維、單層、布爾關(guān)聯(lián)規(guī)則。在這里，所有支持度大于最小支持度 的項集稱為頻繁項集，簡稱頻集。最大期望(EM)算法在統(tǒng)計計算中，最大期望(EM，Expectation-Maximizat

5、ion)算法是在概率(probabilistic)模型中尋 找參數(shù)最大似然估計的算法，其中概率模型依賴于無法觀測的隱藏變量(Latent Variabl)。最大期望 經(jīng)常用在機器學(xué)習(xí)和計算機視覺的數(shù)據(jù)集聚(Data Clustering)領(lǐng)域。PageRankPageRank是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背后的概念是， 每

6、個到頁面的鏈接都是對該頁面的一次投票，被鏈接的越多，就意味著被其他網(wǎng)站投票越多。這個就 是所謂的鏈接流行度”一衡量多少人愿意將他們的網(wǎng)站和你的網(wǎng)站掛鉤。PageRank這個概念引自 學(xué)術(shù)中一篇論文的被引述的頻度即被別人引述的次數(shù)越多，一般判斷這篇論文的權(quán)威性就越高。AdaBoostAdaboost是一種迭代算法，其核心思想是針對同一個訓(xùn)練集訓(xùn)練不同的分類器(弱分類器)，然后把這 些弱分類器集合起來，構(gòu)成一個更強的最終分類器(強分類器)。其算法本身是通過改變數(shù)據(jù)分布來 實現(xiàn)的，它根據(jù)每次訓(xùn)練集之中每個樣本的分類是否正確，以及上次的總體分類的準(zhǔn)確率，來確定每 個樣本的權(quán)值。將修改過權(quán)值的新數(shù)據(jù)集送

7、給下層分類器進(jìn)行訓(xùn)練，最后將每次訓(xùn)練得到的分類器最 后融合起來，作為最后的決策分類器。kNN: k-nearest neighbor classificationK最近鄰(k-Nearest Neighbor，KNN)分類算法，是一個理論上比較成熟的方法，也是最簡單的機器學(xué) 習(xí)算法之一。該方法的思路是：如果一個樣本在特征空間中的k個最相似(即特征空間中最鄰近)的樣 本中的大多數(shù)屬于某一個類別，則該樣本也屬于這個類別。Naive Bayes在眾多的分類模型中，應(yīng)用最為廣泛的兩種分類模型是決策樹模型(Decision Tree Model)和樸素貝葉 斯模型(Naive Bayesian Mode

8、l，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模型的性能最為良好。CART:分類與回歸樹CART, Classification and Regression Trees在分

9、類樹下面有兩個關(guān)鍵的思想。第一個是關(guān)于遞歸地 劃分自變量空間的想法；第二個想法是用驗證數(shù)據(jù)進(jìn)行剪枝。數(shù)據(jù)挖掘十大經(jīng)典算法(1)C45機器學(xué)習(xí)中，決策樹是一個預(yù)測模型；他代表的是對象屬性與對象值之間的一種映射關(guān)系。樹中每個 節(jié)點表示某個對象，而每個分叉路徑則代表的某個可能的屬性值，而每個葉結(jié)點則對應(yīng)從根節(jié)點到該 葉節(jié)點所經(jīng)歷的路徑所表示的對象的值。決策樹僅有單一輸出，若欲有復(fù)數(shù)輸出，可以建立獨立的決 策樹以處理不同輸出。從數(shù)據(jù)產(chǎn)生決策樹的機器學(xué)習(xí)技術(shù)叫做決策樹學(xué)習(xí)，通俗說就是決策樹。決策樹學(xué)習(xí)也是數(shù)據(jù)挖掘中一個普通的方法。在這里，每個決策樹都表述了一種樹型結(jié)構(gòu)，他由他的 分支來對該類型的對象依靠

10、屬性進(jìn)行分類。每個決策樹可以依靠對源數(shù)據(jù)庫的分割進(jìn)行數(shù)據(jù)測試。這 個過程可以遞歸式的對樹進(jìn)行修剪。當(dāng)不能再進(jìn)行分割或一個單獨的類可以被應(yīng)用于某一分支時，遞 歸過程就完成了。另外，隨機森林分類器將許多決策樹結(jié)合起來以提升分類的正確率。決策樹同時也可以依靠計算條件概率來構(gòu)造。決策樹如果依靠數(shù)學(xué)的計算方法可以取得更加理想的效 果。決策樹是如何工作的 決策樹一般都是自上而下的來生成的。選擇分割的方法有好幾種，但是目的都是一致的：對目標(biāo)類嘗試進(jìn)行最佳的分割。從根到葉子節(jié)點都有一條路徑，這條路徑就是一條規(guī)則。決策樹可以是二叉的，也可以是多叉的。對每個節(jié)點的衡量：1）通過該節(jié)點的記錄數(shù)2）如果是葉子節(jié)點的話

11、，分類的路徑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)造樹的過程中， 需

12、要對數(shù)據(jù)集進(jìn)行多次的順序掃描和排序，因而導(dǎo)致算法的低效。此外，C4.5只適合于能夠駐留于 內(nèi)存的數(shù)據(jù)集，當(dāng)訓(xùn)練集大得無法在內(nèi)存容納時程序無法運行。來自搜索的其他內(nèi)容：C4.5算法是機器學(xué)習(xí)算法中的一種分類決策樹算法，其核心算法是ID3算法.分類決策樹算法是從大量事例中進(jìn)行提取分類規(guī)則的自上而下的決策樹.根：學(xué)習(xí)的事例集.枝：分類的判定條件.葉：分好的各個類.4.3.2 ID3 算法1.概念提取算法CLS初始化參數(shù)C=E,E包括所有的例子,為根.IF C中的任一元素e同屬于同一個決策類則創(chuàng)建一個葉子節(jié)點YES終止.ELSE依啟發(fā)式標(biāo)準(zhǔn)，選擇特征Fi=V1,V2,V3,. Vn并創(chuàng)建判定節(jié)點劃分C

13、為互不相交的N個集合C1,C2,C3,. ,Cn；對任一個Ci遞歸.2. ID3算法隨機選擇C的一個子集W (窗口).調(diào)用CLS生成W的分類樹DT(強調(diào)的啟發(fā)式標(biāo)準(zhǔn)在后).順序掃描C搜集DT的意外(即由DT無法確定的例子).組合W與已發(fā)現(xiàn)的意外，形成新的W.重復(fù)2)到4),直到無例外為止.啟發(fā)式標(biāo)準(zhǔn)：只跟本身與其子樹有關(guān),采取信息理論用熵來量度.熵是選擇事件時選擇自由度的量度,其計算方法為freq(Cj,S)/|S|;INFO(S)= - SUM( P*LOG(P) ) ;SUM()函數(shù)是求 j 從 1 到 n 和.Gain(X)=Info(X)-Infox(X);Infox(X)=SUM(

14、(|Ti|/|T|)*Info(X);為保證生成的決策樹最小,ID3算法在生成子樹時，選取使生成的子樹的熵(即Gain(S)最小的的特征來 生成子樹.4.3.3: ID3算法對數(shù)據(jù)的要求所有屬性必須為離散量.所有的訓(xùn)練例的所有屬性必須有一個明確的值.相同的因素必須得到相同的結(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ù)量,

15、C4.5對其排序并分成不同的集合后按照ID3算法當(dāng)作離散量進(jìn)行處理， 但結(jié)論屬性的值必須是離散值.2)訓(xùn)練例的因素屬性值可以是不確定的，以？表示,但結(jié)論必須是確定的3.對已生成的決策樹進(jìn)行裁剪，減小生成樹的規(guī)模.數(shù)據(jù)挖掘十大經(jīng)典算法(2) k-meansk-means algorithm算法是一個聚類算法，把n的對象根據(jù)他們的屬性分為k個分割，k = 0軟間隔1995年，Corinna Cortes與Vapnik提出了一種改進(jìn)的最大間隔區(qū)方法，這種方法可以處理標(biāo)記錯誤 的樣本。如果可區(qū)分正負(fù)例的超平面不存在，則軟邊界將選擇一個超平面盡可能清晰地區(qū)分樣本， 同時使其與分界最清晰的樣本的距離最大化

16、。這一成果使術(shù)語支持向量機(或SVM)得到推廣。 這種方法引入了松馳參數(shù)日以衡量對數(shù)據(jù)xi的誤分類度。隨后，將目標(biāo)函數(shù)與一個針對非0日的懲罰函數(shù)相加，在增大間距和縮小錯誤懲罰兩大目標(biāo)之間進(jìn)行 權(quán)衡優(yōu)化。如果懲罰函數(shù)是一個線性函數(shù)，則等式(3)變形為數(shù)據(jù)挖掘十大經(jīng)典算法(4)AprioriApriori算法是一種最有影響的挖掘布爾關(guān)聯(lián)規(guī)則頻繁項集的算法。其核心是基于兩階段頻 集思想的遞推算法。該關(guān)聯(lián)規(guī)則在分類上屬于單維、單層、布爾關(guān)聯(lián)規(guī)則。在這里，所有支 持度大于最小支持度的項集稱為頻繁項集，簡稱頻集。Apriori演算法所使用的前置統(tǒng)計量包括了：最大規(guī)則物件數(shù)：規(guī)則中物件組所包含的最大物件數(shù)量

17、最小支援：規(guī)則中物件或是物件組必預(yù)符合的最低案例數(shù)最小信心水準(zhǔn)：計算規(guī)則所必須符合的最低信心水準(zhǔn)門檻該算法的基本思想是：首先找出所有的頻集，這些項集出現(xiàn)的頻繁性至少和預(yù)定義的最小支 持度一樣。然后由頻集產(chǎn)生強關(guān)聯(lián)規(guī)則，這些規(guī)則必須滿足最小支持度和最小可信度。然后 使用第1步找到的頻集產(chǎn)生期望的規(guī)則，產(chǎn)生只包含集合的項的所有規(guī)則，其中每一條規(guī)則 的右部只有一項，這里采用的是中規(guī)則的定義。一旦這些規(guī)則被生成，那么只有那些大于用 戶給定的最小可信度的規(guī)則才被留下來。為了生成所有頻集，使用了遞推的方法。Apriori算法的兩大缺點：1.可能產(chǎn)生大量的候選集;2.可能需要重復(fù)掃描數(shù)據(jù)庫。數(shù)據(jù)挖掘十大經(jīng)典

18、算法(5) EM在統(tǒng)計計算中，最大期望(EM，Expectation-Maximization)算法是在概率(probabilistic)模型中尋 找參數(shù)最大似然估計的算法，其中概率模型依賴于無法觀測的隱藏變量(Latent Variabl)。最大期望 經(jīng)常用在機器學(xué)習(xí)和計算機視覺的數(shù)據(jù)集聚(Data Clustering)領(lǐng)域。最大期望算法經(jīng)過兩個步驟交 替進(jìn)行計算，第一步是計算期望(E)，也就是將隱藏變量象能夠觀測到的一樣包含在內(nèi)從而計算最 大似然的期望值；另外一步是最大化(M)，也就是最大化在E步上找到的最大似然的期望值從而 計算參數(shù)的最大似然估計。M步上找到的參數(shù)然后用于另外一個E步計

19、算，這個過程不斷交替進(jìn)行。最大期望過程說明我們用表示能夠觀察到的不完整的變量值，用表示無法觀察到的變量值，這樣和一起組成了 完整的數(shù)據(jù)。可能是實際測量丟失的數(shù)據(jù)，也可能是能夠簡化問題的隱藏變量，如果它的值能夠知 道的話。例如，在混合模型(Mixture Model)中，如果產(chǎn)生樣本的混合元素成分已知的話最大似然 公式將變得更加便利(參見下面的例子)。估計無法觀測的數(shù)據(jù) 讓代表矢量e：定義的參數(shù)的全部數(shù)據(jù)的概率分布（連續(xù)情況下）或者概率集聚函數(shù)（離散情況下）， 那么從這個函數(shù)就可以得到全部數(shù)據(jù)的最大似然值，另外，在給定的觀察到的數(shù)據(jù)條件下未知數(shù)據(jù)的 條件分布可以表示為：數(shù)據(jù)挖掘十大經(jīng)典算法（6）

20、 PageRankPageRank是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ù)

21、越多，一般判斷這篇論文的權(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ū)，人們

22、忙于爭奪、交換甚至銷售鏈接，它是過去幾年來人們關(guān)注的焦點，以至于Google 修改了他的系統(tǒng)，并開始放棄某些類型的鏈接。比如，被人們廣泛接受的一條規(guī)定，來自缺乏內(nèi)容的 link farm”（鏈接工廠）網(wǎng)站的鏈接將不會提供頁面的PageRank，從PageRank較高的頁面得到鏈接 但是內(nèi)容不相關(guān)（比如說某個流行的漫畫書網(wǎng)站鏈接到一個叉車規(guī)范頁面），也不會提供頁面的 PageRanko Google選擇降低了 PageRank對更新頻率，以便不鼓勵人們不斷的對其進(jìn)行監(jiān)測。Google PageRank 一般一年更新四次，所以剛上線的新網(wǎng)站不可能獲得PR值。你的網(wǎng)站很可能在相 當(dāng)長的時間里面看不到

23、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)識 Page

24、Rank在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)頁就能獲

25、得較高的價值。重要網(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)和信賴，那么它的排名就 高。這就是P

26、age 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ù)第一次迭代排

27、名算出第二次的排 名。他們兩人從理論上證明了不論初始值如何選取，這種算法都保證了網(wǎng)頁排名的估計值能收斂到他 們的真實值。值得一提的事，這種算法是完全沒有任何人工干預(yù)的。理論問題解決了，又遇到實際問題。因為互聯(lián)網(wǎng)上網(wǎng)頁的數(shù)量是巨大的，上面提到的二維矩陣從理論 上講有網(wǎng)頁數(shù)目平方之多個元素。如果我們假定有十億個網(wǎng)頁，那么這個矩陣就有一百億億個元素。 這樣大的矩陣相乘，計算量是非常大的。拉里和謝爾蓋兩人利用稀疏矩陣計算的技巧，大大的簡化了 計算量，并實現(xiàn)了這個網(wǎng)頁排名算法。今天Google的工程師把這個算法移植到并行的計算機中，進(jìn) 一步縮短了計算時間，使網(wǎng)頁更新的周期比以前短了許多。我來Google

28、后，拉里(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)做個博士論文?！彼椭x爾蓋就這樣發(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ù)

29、雜、完善了許多。但是網(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)頁重要

30、性的一種方法。在揉合了諸如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 會每月一次遍歷和更

31、新(重新索引)你的網(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ù)的重視程度并不意味

32、著你因此可以不求策略地與任何網(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值，它就顯得微不足道 了?，F(xiàn)在讓我們來看看這個PR分值的計算公式：PR(A)=(1- d)+d(PR(t1)/C(t1)+.+PR(tn)/C(tn)公式 解釋：其中PR(A)表示的是從一個外部鏈接

33、站點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更多的分值。可是，

34、如 果網(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在你

35、的網(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

36、，Yahoo和Looksmart尤為器重。 特別是對DMOZo 一個網(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對其目錄更新后，你就能看到

37、你的PR值會有什么變化了。 如果你的網(wǎng)站為Yahoo和Looksmart所收錄，那么你的PR值會得到顯著提升。如果你的網(wǎng)站是非商 業(yè)性質(zhì)的或幾乎完全是非商業(yè)性質(zhì)的內(nèi)容，那么你可以通過使你的網(wǎng)站為著名的網(wǎng)絡(luò)目錄 Looksmart所收錄。Looksmart也是從Zeal網(wǎng)絡(luò)目錄獲得非商業(yè)搜索列表。Google PR值的更新周期是多長時間？一般情況下PR值更新的周期是2.53個月！最近一次PR更新是2008年1月中旬。PageRank相關(guān)算法總結(jié)：PageRank基本思想：如果網(wǎng)頁T存在一個指向網(wǎng)頁A的連接，則表明T的所有者認(rèn)為A比較重要，從而把T 的一部分重要性得分賦予A。這個重要性得分值為：P

38、R (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)頁的歧視。Topic-Sensitive PageRank (主題敏感的 PageRank)基本思想：針對PageRank對主題的忽略而提出。核心思想：通過離線計算出一個PageR

39、ank向量集 合，該集合中的每一個向量與某一主題相關(guān)，即計算某個頁面關(guān)于不同主題的得分。主要分為兩個階 段：主題相關(guān)的PageRank向量集合的計算和在線查詢時主題的確定。優(yōu)點：根據(jù)用戶的查詢請求和相關(guān)上下文判斷用戶查詢相關(guān)的主題(用戶的興趣)返回查詢結(jié)果準(zhǔn)確 性高。不足：沒有利用主題的相關(guān)性來提高鏈接得分的準(zhǔn)確性。Hilltop基本思想：與PageRank的不同之處：僅考慮專家頁面的鏈接。主要包括兩個步驟：專家頁面搜索和 目標(biāo)頁面排序。優(yōu)點：相關(guān)性強，結(jié)果準(zhǔn)確。不足：專家頁面的搜索和確定對算法起關(guān)鍵作用，專家頁面的質(zhì)量決定了算法的準(zhǔn)確性，而專家頁面 的質(zhì)量和公平性難以保證；忽略了大量非專家頁

40、面的影響，不能反應(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)上排名采用惡意點

41、擊和輸入關(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月被授予美國專利。如今它在G

42、oogle所有算法中依然是至關(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ù)

43、網(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)那

44、些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排名之所

45、以大受追捧，是由于它并非只使用關(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的青睞。數(shù)據(jù)挖掘十大經(jīng)典算法(7) AdaBoostAdaboost是一種迭代算法，其核心思想是針對同一個訓(xùn)練集訓(xùn)練不同的分類器(弱分類器

46、)，然后把這 些弱分類器集合起來，構(gòu)成一個更強的最終分類器(強分類器)。其算法本身是通過改變數(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)簽問題、

47、大類 單標(biāo)簽問題，回歸問題。它用全部的訓(xùn)練樣本進(jìn)行學(xué)習(xí)。該算法其實是一個簡單的弱分類算法提升過程，這個過程通過不斷的訓(xùn)練，可以提高對數(shù)據(jù)的分類能 力。整個過程如下所示：先通過對N個訓(xùn)練樣本的學(xué)習(xí)得到第一個弱分類器；將 分錯的樣本和其他的新數(shù)據(jù)一起構(gòu)成一個新的N個的訓(xùn)練樣本，通過對這個樣本的學(xué)習(xí)得到第 二個弱分類器；將和都分錯了的樣本加上其他的新樣本構(gòu)成另一個新的N個的訓(xùn)練樣本，通過對這個樣本的學(xué) 習(xí)得到第三個弱分類器；最終經(jīng)過提升的強分類器。即某個數(shù)據(jù)被分為哪一類要通過，的多數(shù)表決。2.3 Adaboost(Adaptive Boosting)算法對于boosting算法，存在兩個問題：如何調(diào)

48、整訓(xùn)練集，使得在訓(xùn)練集上訓(xùn)練的弱分類器得以進(jìn)行;如何將訓(xùn)練得到的各個弱分類器聯(lián)合起來形成強分類器。針對以上兩個問題，adaboost算法進(jìn)行了調(diào)整：使用加權(quán)后選取的訓(xùn)練數(shù)據(jù)代替隨機選取的訓(xùn)練樣本，這樣將訓(xùn)練的焦點集中在比較難分的訓(xùn)練 數(shù)據(jù)樣本上；將弱分類器聯(lián)合起來，使用加權(quán)的投票機制代替平均投票機制。讓分類效果好的弱分類器具有較 大的權(quán)重，而分類效果差的分類器具有較小的權(quán)重。Adaboost算法是Freund和Schapire根據(jù)在線分配算法提出的，他們詳細(xì)分析了 Adaboost算法錯誤 率的上界，以及為了使強分類器達(dá)到錯誤率，算法所需要的最多迭代次數(shù)等相關(guān)問題。與Boosting 算法不同

49、的是，adaboost算法不需要預(yù)先知道弱學(xué)習(xí)算法學(xué)習(xí)正確率的下限即弱分類器的誤差，并 且最后得到的強分類器的分類精度依賴于所有弱分類器的分類精度，這樣可以深入挖掘弱分類器算法 的能力。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個弱分類器按一定

50、的權(quán)重疊加(boost)起來，得到最終想 要的強分類器。Adaboost算法的具體步驟如下：給定訓(xùn)練樣本集，其中分別對應(yīng)于正例樣本和負(fù)例樣本；為訓(xùn)練的最大循環(huán)次數(shù)；初始化樣本權(quán)重，即為訓(xùn)練樣本的初始概率分布；第一次迭代：訓(xùn)練樣本的概率分布下，訓(xùn)練弱分類器：(2)計算弱分類器的錯誤率：選取，使得最小更新樣本權(quán)重：最終得到的強分類器：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í)算法得到一個錯誤率為的弱分類器，對于這個算法定義的

51、弱學(xué)習(xí)算法，對 所有的，都有，而這個錯誤率的上限并不需要事先知道，實際上。每一次迭代，都要對權(quán)重進(jìn)行更 新。更新的規(guī)則是：減小弱分類器分類效果較好的數(shù)據(jù)的概率，增大弱分類器分類效果較差的數(shù)據(jù)的 概率。最終的分類器是個弱分類器的加權(quán)平均。數(shù)據(jù)挖掘十大經(jīng)典算法(8) kNN鄰近算法KNN 算法的決策過程 k-Nearest Neighbor algorithm左圖中，綠色圓要被決定賦予哪個類，是紅色三角形還是藍(lán)色四方形？如果K=3,由于紅色三角形所 占比例為2/3，綠色圓將被賦予紅色三角形那個類，如果K=5，由于藍(lán)色四方形比例為3/5，因此綠 色圓被賦予藍(lán)色四方形類。K最近鄰(k-Nearest

52、Neighbor，KNN)分類算法，是一個理論上比較成熟的方法，也是最簡單的機器學(xué) 習(xí)算法之一。該方法的思路是：如果一個樣本在特征空間中的k個最相似(即特征空間中最鄰近)的樣 本中的大多數(shù)屬于某一個類別，則該樣本也屬于這個類別。KNN算法中，所選擇的鄰居都是已經(jīng)正確 分類的對象。該方法在定類決策上只依據(jù)最鄰近的一個或者幾個樣本的類別來決定待分樣本所屬的類 別。KNN方法雖然從原理上也依賴于極限定理，但在類別決策時，只與極少量的相鄰樣本有關(guān)。由 于KNN方法主要靠周圍有限的鄰近的樣本，而不是靠判別類域的方法來確定所屬類別的，因此對于 類域的交叉或重疊較多的待分樣本集來說，KNN方法較其他方法更為

53、適合。KNN算法不僅可以用于分類，還可以用于回歸。通過找出一個樣本的k個最近鄰居，將這些鄰居的屬 性的平均值賦給該樣本，就可以得到該樣本的屬性。更有用的方法是將不同距離的鄰居對該樣本產(chǎn)生 的影響給予不同的權(quán)值(weight)，如權(quán)值與距離成正比。該算法在分類時有個主要的不足是，當(dāng)樣本不平衡時，如一個類的樣本容量很大，而其他類樣本容量 很小時，有可能導(dǎo)致當(dāng)輸入一個新樣本時，該樣本的K個鄰居中大容量類的樣本占多數(shù)。因此可以采 用權(quán)值的方法(和該樣本距離小的鄰居權(quán)值大)來改進(jìn)。該方法的另一個不足之處是計算量較大，因 為對每一個待分類的文本都要計算它到全體已知樣本的距離，才能求得它的K個最近鄰點。目前

54、常用 的解決方法是事先對已知樣本點進(jìn)行剪輯，事先去除對分類作用不大的樣本。該算法比較適用于樣本 容量比較大的類域的自動分類，而那些樣本容量較小的類域采用這種算法比較容易產(chǎn)生誤分。數(shù)據(jù)挖掘十大經(jīng)典算法(9) Naive Bayes貝葉斯分類器貝葉斯分類器的分類原理是通過某對象的先驗概率，利用貝葉斯公式計算出其后驗概率，即該對象屬 于某一類的概率，選擇具有最大后驗概率的類作為該對象所屬的類。目前研究較多的貝葉斯分類器主 要有四種，分別是：Naive Bayes、TAN、BAN和GBN。貝葉斯網(wǎng)絡(luò)是一個帶有概率注釋的有向無環(huán)圖，圖中的每一個結(jié)點均表示一個隨機變量，圖中兩結(jié)點 間若存在著一條孤，則表示

55、這兩結(jié)點相對應(yīng)的隨機變量是概率相依的，反之則說明這兩個隨機變量是 條件獨立的。網(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的取值來自于類集合(cl , c2，cm)，還包含一組結(jié)點X = ( Xl , X2，Xn)，表示用于分類的特征。對于貝葉斯網(wǎng)絡(luò)分類 器，若某一待分類的樣本D，其分類特征值為x

56、= ( xl , x2，x n)，則樣本D屬于類別ci的概 率 P( C = ci | Xl = xl , X2 = x 2 , . , Xn = x n)，( i = 1 ,2 , . , m)應(yīng)滿足下式：P( C = ci | X = x) = Max P( C = cl | 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

57、= 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ù)先已

58、知類的過程。數(shù)據(jù)分類問題的解決是一個兩步過程：第一步， 建立一個模型，描述預(yù)先的數(shù)據(jù)集或概念集。通過分析由屬性描述的樣本(或?qū)嵗瑢ο蟮?來構(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)生一個分類。在分類問題中使用決策

59、 樹模型有很多的優(yōu)點，決策樹便于使用，而且高效；根據(jù)決策樹可以很容易地構(gòu)造出規(guī)則，而規(guī)則通 常易于解釋和理解；決策樹可很好地擴展到大型數(shù)據(jù)庫中，同時它的大小獨立于數(shù)據(jù)庫的大?。粵Q策 樹模型的另外一大優(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 模型與其他分類方法相比具有最小的誤差率。但是實際上并非總是如此，這是

60、因為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