數據挖掘演算法案例

『壹』 數據挖掘演算法與生活中的應用案例

數據挖掘演算法與生活中的應用案例

如何分辨出垃圾郵件」、「如何判斷一筆交易是否屬於欺詐」、「如何判斷紅酒的品質和檔次」、「掃描王是如何做到文字識別的」、「如何判斷佚名的著作是否出自某位名家之手」、「如何判斷一個細胞是否屬於腫瘤細胞」等等，這些問題似乎都很專業，都不太好回答。但是，如果了解一點點數據挖掘的知識，你，或許會有柳暗花明的感覺。
本文，主要想簡單介紹下數據挖掘中的演算法，以及它包含的類型。然後，通過現實中觸手可及的、活生生的案例，去詮釋它的真實存在。 一般來說，數據挖掘的演算法包含四種類型，即分類、預測、聚類、關聯。前兩種屬於有監督學習，後兩種屬於無監督學習，屬於描述性的模式識別和發現。
有監督學習有監督的學習，即存在目標變數，需要探索特徵變數和目標變數之間的關系，在目標變數的監督下學習和優化演算法。例如，信用評分模型就是典型的有監督學習，目標變數為「是否違約」。演算法的目的在於研究特徵變數（人口統計、資產屬性等）和目標變數之間的關系。
分類演算法分類演算法和預測演算法的最大區別在於，前者的目標變數是分類離散型（例如，是否逾期、是否腫瘤細胞、是否垃圾郵件等），後者的目標變數是連續型。一般而言，具體的分類演算法包括，邏輯回歸、決策樹、KNN、貝葉斯判別、SVM、隨機森林、神經網路等。
預測演算法預測類演算法，其目標變數一般是連續型變數。常見的演算法，包括線性回歸、回歸樹、神經網路、SVM等。
無監督學習無監督學習，即不存在目標變數，基於數據本身，去識別變數之間內在的模式和特徵。例如關聯分析，通過數據發現項目A和項目B之間的關聯性。例如聚類分析，通過距離，將所有樣本劃分為幾個穩定可區分的群體。這些都是在沒有目標變數監督下的模式識別和分析。
聚類分析聚類的目的就是實現對樣本的細分，使得同組內的樣本特徵較為相似，不同組的樣本特徵差異較大。常見的聚類演算法包括kmeans、系譜聚類、密度聚類等。
關聯分析關聯分析的目的在於，找出項目（item）之間內在的聯系。常常是指購物籃分析，即消費者常常會同時購買哪些產品（例如游泳褲、防曬霜），從而有助於商家的捆綁銷售。
基於數據挖掘的案例和應用上文所提到的四種演算法類型（分類、預測、聚類、關聯），是比較傳統和常見的。還有其他一些比較有趣的演算法分類和應用場景，例如協同過濾、異常值分析、社會網路、文本分析等。下面，想針對不同的演算法類型，具體的介紹下數據挖掘在日常生活中真實的存在。下面是能想到的、幾個比較有趣的、和生活緊密關聯的例子。
基於分類模型的案例這裡面主要想介紹兩個案例，一個是垃圾郵件的分類和判斷，另外一個是在生物醫葯領域的應用，即腫瘤細胞的判斷和分辨。
垃圾郵件的判別郵箱系統如何分辨一封Email是否屬於垃圾郵件？這應該屬於文本挖掘的范疇，通常會採用樸素貝葉斯的方法進行判別。它的主要原理是，根據郵件正文中的單詞，是否經常出現在垃圾郵件中，進行判斷。例如，如果一份郵件的正文中包含「報銷」、「發票」、「促銷」等詞彙時，該郵件被判定為垃圾郵件的概率將會比較大。
一般來說，判斷郵件是否屬於垃圾郵件，應該包含以下幾個步驟。
第一，把郵件正文拆解成單片語合，假設某篇郵件包含100個單詞。
第二，根據貝葉斯條件概率，計算一封已經出現了這100個單詞的郵件，屬於垃圾郵件的概率和正常郵件的概率。如果結果表明，屬於垃圾郵件的概率大於正常郵件的概率。那麼該郵件就會被劃為垃圾郵件。
醫學上的腫瘤判斷如何判斷細胞是否屬於腫瘤細胞呢？腫瘤細胞和普通細胞，有差別。但是，需要非常有經驗的醫生，通過病理切片才能判斷。如果通過機器學習的方式，使得系統自動識別出腫瘤細胞。此時的效率，將會得到飛速的提升。並且，通過主觀（醫生）+客觀（模型）的方式識別腫瘤細胞，結果交叉驗證，結論可能更加靠譜。
如何操作？通過分類模型識別。簡言之，包含兩個步驟。首先，通過一系列指標刻畫細胞特徵，例如細胞的半徑、質地、周長、面積、光滑度、對稱性、凹凸性等等，構成細胞特徵的數據。其次，在細胞特徵寬表的基礎上，通過搭建分類模型進行腫瘤細胞的判斷。
基於預測模型的案例這裡面主要想介紹兩個案例。即通過化學特性判斷和預測紅酒的品質。另外一個是，通過搜索引擎來預測和判斷股價的波動和趨勢。
紅酒品質的判斷如何評鑒紅酒？有經驗的人會說，紅酒最重要的是口感。而口感的好壞，受很多因素的影響，例如年份、產地、氣候、釀造的工藝等等。但是，統計學家並沒有時間去品嘗各種各樣的紅酒，他們覺得通過一些化學屬性特徵就能夠很好地判斷紅酒的品質了。並且，現在很多釀酒企業其實也都這么幹了，通過監測紅酒中化學成分的含量，從而控制紅酒的品質和口感。
那麼，如何判斷鑒紅酒的品質呢？
第一步，收集很多紅酒樣本，整理檢測他們的化學特性，例如酸性、含糖量、氯化物含量、硫含量、酒精度、PH值、密度等等。
第二步，通過分類回歸樹模型進行預測和判斷紅酒的品質和等級。
搜索引擎的搜索量和股價波動一隻南美洲熱帶雨林中的蝴蝶，偶爾扇動了幾下翅膀，可以在兩周以後，引起美國德克薩斯州的一場龍卷風。你在互聯網上的搜索是否會影響公司股價的波動？
很早之前，就已經有文獻證明，互聯網關鍵詞的搜索量（例如流感）會比疾控中心提前1到2周預測出某地區流感的爆發。
同樣，現在也有些學者發現了這樣一種現象，即公司在互聯網中搜索量的變化，會顯著影響公司股價的波動和趨勢，即所謂的投資者注意力理論。該理論認為，公司在搜索引擎中的搜索量，代表了該股票被投資者關注的程度。因此，當一隻股票的搜索頻數增加時，說明投資者對該股票的關注度提升，從而使得該股票更容易被個人投資者購買，進一步地導致股票價格上升，帶來正向的股票收益。這是已經得到無數論文驗證了的。
基於關聯分析的案例：沃爾瑪的啤酒尿布啤酒尿布是一個非常非常古老陳舊的故事。故事是這樣的，沃爾瑪發現一個非常有趣的現象，即把尿布與啤酒這兩種風馬牛不相及的商品擺在一起，能夠大幅增加兩者的銷量。原因在於，美國的婦女通常在家照顧孩子，所以，她們常常會囑咐丈夫在下班回家的路上為孩子買尿布，而丈夫在買尿布的同時又會順手購買自己愛喝的啤酒。沃爾瑪從數據中發現了這種關聯性，因此，將這兩種商品並置，從而大大提高了關聯銷售。
啤酒尿布主要講的是產品之間的關聯性，如果大量的數據表明，消費者購買A商品的同時，也會順帶著購買B產品。那麼A和B之間存在關聯性。在超市中，常常會看到兩個商品的捆綁銷售，很有可能就是關聯分析的結果。
基於聚類分析的案例：零售客戶細分對客戶的細分，還是比較常見的。細分的功能，在於能夠有效的劃分出客戶群體，使得群體內部成員具有相似性，但是群體之間存在差異性。其目的在於識別不同的客戶群體，然後針對不同的客戶群體，精準地進行產品設計和推送，從而節約營銷成本，提高營銷效率。
例如，針對商業銀行中的零售客戶進行細分，基於零售客戶的特徵變數（人口特徵、資產特徵、負債特徵、結算特徵），計算客戶之間的距離。然後，按照距離的遠近，把相似的客戶聚集為一類，從而有效的細分客戶。將全體客戶劃分為諸如，理財偏好者、基金偏好者、活期偏好者、國債偏好者、風險均衡者、渠道偏好者等。
基於異常值分析的案例：支付中的交易欺詐偵測採用支付寶支付時，或者刷信用卡支付時，系統會實時判斷這筆刷卡行為是否屬於盜刷。通過判斷刷卡的時間、地點、商戶名稱、金額、頻率等要素進行判斷。這裡面基本的原理就是尋找異常值。如果您的刷卡被判定為異常，這筆交易可能會被終止。
異常值的判斷，應該是基於一個欺詐規則庫的。可能包含兩類規則，即事件類規則和模型類規則。第一，事件類規則，例如刷卡的時間是否異常（凌晨刷卡）、刷卡的地點是否異常（非經常所在地刷卡）、刷卡的商戶是否異常（被列入黑名單的套現商戶）、刷卡金額是否異常（是否偏離正常均值的三倍標准差）、刷卡頻次是否異常（高頻密集刷卡）。第二，模型類規則，則是通過演算法判定交易是否屬於欺詐。一般通過支付數據、賣家數據、結算數據，構建模型進行分類問題的判斷。
基於協同過濾的案例：電商猜你喜歡和推薦引擎電商中的猜你喜歡，應該是大家最為熟悉的。在京東商城或者亞馬遜購物，總會有「猜你喜歡」、「根據您的瀏覽歷史記錄精心為您推薦」、「購買此商品的顧客同時也購買了商品」、「瀏覽了該商品的顧客最終購買了商品」，這些都是推薦引擎運算的結果。
這裡面，確實很喜歡亞馬遜的推薦，通過「購買該商品的人同時購買了**商品」，常常會發現一些質量比較高、較為受認可的書。一般來說，電商的「猜你喜歡」（即推薦引擎）都是在協同過濾演算法（Collaborative Filter）的基礎上，搭建一套符合自身特點的規則庫。即該演算法會同時考慮其他顧客的選擇和行為，在此基礎上搭建產品相似性矩陣和用戶相似性矩陣。基於此，找出最相似的顧客或最關聯的產品，從而完成產品的推薦。
基於社會網路分析的案例：電信中的種子客戶種子客戶和社會網路，最早出現在電信領域的研究。即，通過人們的通話記錄，就可以勾勒出人們的關系網路。電信領域的網路，一般會分析客戶的影響力和客戶流失、產品擴散的關系。
基於通話記錄，可以構建客戶影響力指標體系。採用的指標，大概包括如下，一度人脈、二度人脈、三度人脈、平均通話頻次、平均通話量等。基於社會影響力，分析的結果表明，高影響力客戶的流失會導致關聯客戶的流失。其次，在產品的擴散上，選擇高影響力客戶作為傳播的起點，很容易推動新套餐的擴散和滲透。
此外，社會網路在銀行（擔保網路）、保險（團伙欺詐）、互聯網（社交互動）中也都有很多的應用和案例。
基於文本分析的案例這裡面主要想介紹兩個案例。一個是類似「掃描王」的APP，直接把紙質文檔掃描成電子文檔。相信很多人都用過，這里准備簡單介紹下原理。另外一個是，江湖上總是傳言紅樓夢的前八十回和後四十回，好像並非都是出自曹雪芹之手，這裡面准備從統計的角度聊聊。
字元識別：掃描王APP手機拍照時會自動識別人臉，還有一些APP，例如掃描王，可以掃描書本，然後把掃描的內容自動轉化為word。這些屬於圖像識別和字元識別（Optical Character Recognition）。圖像識別比較復雜，字元識別理解起來比較容易些。
查找了一些資料，字元識別的大概原理如下，以字元S為例。
第一，把字元圖像縮小到標准像素尺寸，例如12*16。注意，圖像是由像素構成，字元圖像主要包括黑、白兩種像素。
第二，提取字元的特徵向量。如何提取字元的特徵，採用二維直方圖投影。就是把字元（12*16的像素圖）往水平方向和垂直方向上投影。水平方向有12個維度，垂直方向有16個維度。這樣分別計算水平方向上各個像素行中黑色像素的累計數量、垂直方向各個像素列上的黑色像素的累計數量。從而得到水平方向12個維度的特徵向量取值，垂直方向上16個維度的特徵向量取值。這樣就構成了包含28個維度的字元特徵向量。
第三，基於前面的字元特徵向量，通過神經網路學習，從而識別字元和有效分類。
文學著作與統計：紅樓夢歸屬這是非常著名的一個爭論，懸而未決。對於紅樓夢的作者，通常認為前80回合是曹雪芹所著，後四十回合為高鶚所寫。其實主要問題，就是想確定，前80回合和後40回合是否在遣詞造句方面存在顯著差異。
這事讓一群統計學家比較興奮了。有些學者通過統計名詞、動詞、形容詞、副詞、虛詞出現的頻次，以及不同詞性之間的相關系做判斷。有些學者通過虛詞（例如之、其、或、亦、了、的、不、把、別、好），判斷前後文風的差異。有些學者通過場景（花卉、樹木、飲食、醫葯與詩詞）頻次的差異，來做統計判斷。總而言之，主要通過一些指標量化，然後比較指標之間是否存在顯著差異，藉此進行寫作風格的判斷。

以上是小編為大家分享的關於數據挖掘演算法與生活中的應用案例的相關內容，更多信息可以關注環球青藤分享更多干貨

『貳』 數據挖掘 聚類演算法概述

文 | 宿痕
來源 | 知乎
本篇重點介紹聚類演算法的原理，應用流程、使用技巧、評估方法、應用案例等。具體的演算法細節可以多查閱相關的資料。聚類的主要用途就是客戶分群。
1.聚類 VS 分類
分類是「監督學習」，事先知道有哪些類別可以分。

聚類是「無監督學習」，事先不知道將要分成哪些類。

舉個例子，比如蘋果、香蕉、獼猴桃、手機、電話機。
根據特徵的不同，我們聚類會分為【蘋果、香蕉、獼猴桃】為水果的一類，和【手機、電話機】為數碼產品的一類。
而分類的話，就是我們在判斷「草莓」的時候，把它歸為「水果」一類。
所以通俗的解釋就是：分類是從訓練集學習對數據的判斷能力，再去做未知數據的分類判斷；而聚類就是把相似的東西分為一類，它不需要訓練數據進行學習。
學術解釋：分類是指分析資料庫中的一組對象，找出其共同屬性。然後根據分類模型，把它們劃分為不同的類別。分類數據首先根據訓練數據建立分類模型，然後根據這些分類描述分類資料庫中的測試數據或產生更恰當的描述。
聚類是指資料庫中的數據可以劃分為一系列有意義的子集，即類。在同一類別中，個體之間的距離較小，而不同類別上的個體之間的距離偏大。聚類分析通常稱為「無監督學習」。
2.聚類的常見應用
我們在實際情況的中的應用會有：
marketing：客戶分群
insurance：尋找汽車保險高索賠客戶群
urban planning：尋找相同類型的房產
比如你做買家分析、賣家分析時，一定會聽到客戶分群的概念，用標准分為高價值客戶、一般價值客戶和潛在用戶等，對於不同價值的客戶提供不同的營銷方案；

還有像在保險公司，那些高索賠的客戶是保險公司最care的問題，這個就是影響到保險公司的盈利問題；
還有在做房產的時候，根據房產的地理位置、價格、周邊設施等情況聚類熱房產區域和冷房產區域。

3.k-means
（1）假定K個clusters（2）目標：尋找緊致的聚類
a.隨機初始化clusters

b.分配數據到最近的cluster

c.重復計算clusters

d.repeat直到收斂

優點：局部最優
缺點：對於非凸的cluster有問題
其中K=？
K<=sample size
取決於數據的分布和期望的resolution
AIC，DIC
層次聚類避免了這個問題
4.評估聚類
魯棒性？
聚類如何，是否過度聚合？
很多時候是取決於聚合後要干什麼。
5.case案例
case 1：賣家分群雲圖

作者：宿痕 授權轉載
原文鏈接：http：//zhuanlan.hu.com/dataman/20397891

『叄』 數據挖掘十大演算法-

整理里一晚上的數據挖掘演算法，其中主要引自wiki和一些論壇。發布到上作為知識共享，但是發現Latex的公式轉碼到網頁的時候出現了丟失，暫時沒找到解決方法，有空再回來填坑了。

——編者按

一、 C4.5

C4.5演算法是由Ross Quinlan開發的用於產生決策樹的演算法[1]，該演算法是對Ross Quinlan之前開發的ID3演算法的一個擴展。C4.5演算法主要應用於統計分類中，主要是通過分析數據的信息熵建立和修剪決策樹。

1.1 決策樹的建立規則

在樹的每個節點處，C4.5選擇最有效地方式對樣本集進行分裂，分裂規則是分析所有屬性的歸一化的信息增益率，選擇其中增益率最高的屬性作為分裂依據，然後在各個分裂出的子集上進行遞歸操作。

依據屬性A對數據集D進行分類的信息熵可以定義如下：

劃分前後的信息增益可以表示為：

那麼，歸一化的信息增益率可以表示為：

1.2 決策樹的修剪方法

C4.5採用的剪枝方法是悲觀剪枝法(Pessimistic Error Pruning，PEP)，根據樣本集計運算元樹與葉子的經驗錯誤率，在滿足替換標准時，使用葉子節點替換子樹。

不妨用K表示訓練數據集D中分類到某一個葉子節點的樣本數，其中其中錯誤分類的個數為J，由於用估計該節點的樣本錯誤率存在一定的樣本誤差，因此用表示修正後的樣本錯誤率。那麼，對於決策樹的一個子樹S而言，設其葉子數目為L(S)，則子樹S的錯誤分類數為：

設數據集的樣本總數為Num，則標准錯誤可以表示為：

那麼，用表示新葉子的錯誤分類數，則選擇使用新葉子節點替換子樹S的判據可以表示為：

二、KNN

最近鄰域演算法(k-nearest neighbor classification, KNN)[2]是一種用於分類和回歸的非參數統計方法。KNN演算法採用向量空間模型來分類，主要思路是相同類別的案例彼此之間的相似度高，從而可以藉由計算未知樣本與已知類別案例之間的相似度，來實現分類目標。KNN是一種基於局部近似和的實例的學習方法，是目前最簡單的機器學習演算法之一。

在分類問題中，KNN的輸出是一個分類族群，它的對象的分類是由其鄰居的「多數表決」確定的，k個最近鄰居（k為正整數，通常較小）中最常見的分類決定了賦予該對象的類別。若k = 1，則該對象的類別直接由最近的一個節點賦予。在回歸問題中，KNN的輸出是其周圍k個鄰居的平均值。無論是分類還是回歸，衡量鄰居的權重都非常重要，目標是要使較近鄰居的權重比較遠鄰居的權重大，例如，一種常見的加權方案是給每個鄰居權重賦值為1/d，其中d是到鄰居的距離。這也就自然地導致了KNN演算法對於數據的局部結構過於敏感。

三、Naive Bayes

在機器學習的眾多分類模型中，應用最為廣泛的兩種分類模型是決策樹模型(Decision Tree Model)和樸素貝葉斯模型(Naive Bayesian Model，NBC)[3]。樸素貝葉斯模型發源於古典數學理論，有著堅實的數學基礎，以及穩定的分類效率。同時，NBC模型所需估計的參數很少，對缺失數據不太敏感，演算法也比較簡單。

在假設各個屬性相互獨立的條件下，NBC模型的分類公式可以簡單地表示為：

但是實際上問題模型的屬性之間往往是非獨立的，這給NBC模型的分類准確度帶來了一定影響。在屬性個數比較多或者屬性之間相關性較大時，NBC模型的分類效率比不上決策樹模型；而在屬性相關性較小時，NBC模型的性能最為良好。

四、CART

CART演算法(Classification And Regression Tree)[4]是一種二分遞歸的決策樹，把當前樣本劃分為兩個子樣本，使得生成的每個非葉子結點都有兩個分支，因此CART演算法生成的決策樹是結構簡潔的二叉樹。由於CART演算法構成的是一個二叉樹，它在每一步的決策時只能是「是」或者「否」，即使一個feature有多個取值，也是把數據分為兩部分。在CART演算法中主要分為兩個步驟：將樣本遞歸劃分進行建樹過程；用驗證數據進行剪枝。

五、K-means

k-平均演算法(k-means clustering)[5]是源於信號處理中的一種向量量化方法，現在則更多地作為一種聚類分析方法流行於數據挖掘領域。k-means的聚類目標是：把n個點（可以是樣本的一次觀察或一個實例）劃分到k個聚類中，使得每個點都屬於離他最近的均值（此即聚類中心）對應的聚類。

5.1 k-means的初始化方法

通常使用的初始化方法有Forgy和隨機劃分(Random Partition)方法。Forgy方法隨機地從數據集中選擇k個觀測作為初始的均值點；而隨機劃分方法則隨機地為每一觀測指定聚類，然後執行「更新」步驟,即計算隨機分配的各聚類的圖心，作為初始的均值點。Forgy方法易於使得初始均值點散開，隨機劃分方法則把均值點都放到靠近數據集中心的地方；隨機劃分方法一般更適用於k-調和均值和模糊k-均值演算法。對於期望-最大化(EM)演算法和標准k-means演算法，Forgy方法作為初始化方法的表現會更好一些。

5.2 k-means的標准演算法

k-means的標准演算法主要包括分配(Assignment)和更新(Update)，在初始化得出k個均值點後，演算法將會在這兩個步驟中交替執行。

分配(Assignment)：將每個觀測分配到聚類中，使得組內平方和達到最小。

更新(Update)：對於上一步得到的每一個聚類，以聚類中觀測值的圖心，作為新的均值點。

六、Apriori

Apriori演算法[6]是一種最有影響的挖掘布爾關聯規則頻繁項集的演算法，其核心是基於兩階段頻集思想的遞推演算法。該關聯規則在分類上屬於單維、單層、布爾關聯規則。Apriori採用自底向上的處理方法，每次只擴展一個對象加入候選集，並且使用數據集對候選集進行檢驗，當不再產生匹配條件的擴展對象時，演算法終止。

Apriori的缺點在於生成候選集的過程中，演算法總是嘗試掃描整個數據集並盡可能多地添加擴展對象，導致計算效率較低；其本質上採用的是寬度優先的遍歷方式，理論上需要遍歷次才可以確定任意的最大子集S。

七、SVM

支持向量機(Support Vector Machine, SVM)[7]是在分類與回歸分析中分析數據的監督式學習模型與相關的學習演算法。給定一組訓練實例，每個訓練實例被標記為屬於兩個類別中的一個或另一個，SVM訓練演算法創建一個將新的實例分配給兩個類別之一的模型，使其成為非概率二元線性分類器。SVM模型是將實例表示為空間中的點，這樣映射就使得單獨類別的實例被盡可能寬的明顯的間隔分開。然後，將新的實例映射到同一空間，並基於它們落在間隔的哪一側來預測所屬類別。

除了進行線性分類之外，SVM還可以使用所謂的核技巧有效地進行非線性分類，將其輸入隱式映射到高維特徵空間中，即支持向量機在高維或無限維空間中構造超平面或超平面集合，用於分類、回歸或其他任務。直觀來說，分類邊界距離最近的訓練數據點越遠越好，因為這樣可以縮小分類器的泛化誤差。

八、EM

最大期望演算法(Expectation–Maximization Algorithm, EM)[7]是從概率模型中尋找參數最大似然估計的一種演算法。其中概率模型依賴於無法觀測的隱性變數。最大期望演算法經常用在機器學習和計算機視覺的數據聚類（Data Clustering）領域。最大期望演算法經過兩個步驟交替進行計算，第一步是計算期望(E)，利用對隱藏變數的現有估計值，計算其最大似然估計值；第二步是最大化(M)，最大化在E步上求得的最大似然值來計算參數的值。M步上找到的參數估計值被用於下一個E步計算中，這個過程不斷交替進行。

九、PageRank

PageRank演算法設計初衷是根據網站的外部鏈接和內部鏈接的數量和質量對網站的價值進行衡量。PageRank將每個到網頁的鏈接作為對該頁面的一次投票，被鏈接的越多，就意味著被其他網站投票越多。

演算法假設上網者將會不斷點網頁上的鏈接，當遇到了一個沒有任何鏈接出頁面的網頁，這時候上網者會隨機轉到另外的網頁開始瀏覽。設置在任意時刻，用戶到達某頁面後並繼續向後瀏覽的概率，該數值是根據上網者使用瀏覽器書簽的平均頻率估算而得。PageRank值可以表示為：

其中，是被研究的頁面集合，N表示頁面總數，是鏈接入頁面的集合，是從頁面鏈接處的集合。

PageRank演算法的主要缺點是的主要缺點是舊的頁面等級會比新頁面高。因為即使是非常好的新頁面也不會有很多外鏈，除非它是某個站點的子站點。

十、AdaBoost

AdaBoost方法[10]是一種迭代演算法，在每一輪中加入一個新的弱分類器，直到達到某個預定的足夠小的錯誤率。每一個訓練樣本都被賦予一個權重，表明它被某個分類器選入訓練集的概率。如果某個樣本點已經被准確地分類，那麼在構造下一個訓練集中，它被選中的概率就被降低；相反，如果某個樣本點沒有被准確地分類，那麼它的權重就得到提高。通過這樣的方式，AdaBoost方法能「聚焦於」那些較難分的樣本上。在具體實現上，最初令每個樣本的權重都相等，對於第k次迭代操作，我們就根據這些權重來選取樣本點，進而訓練分類器Ck。然後就根據這個分類器，來提高被它分錯的的樣本的權重，並降低被正確分類的樣本權重。然後，權重更新過的樣本集被用於訓練下一個分類器Ck[，並且如此迭代地進行下去。

AdaBoost方法的自適應在於：前一個分類器分錯的樣本會被用來訓練下一個分類器。AdaBoost方法對於雜訊數據和異常數據很敏感。但在一些問題中，AdaBoost方法相對於大多數其它學習演算法而言，不會很容易出現過擬合現象。AdaBoost方法中使用的分類器可能很弱（比如出現很大錯誤率），但只要它的分類效果比隨機好一點（比如兩類問題分類錯誤率略小於0.5），就能夠改善最終得到的模型。而錯誤率高於隨機分類器的弱分類器也是有用的，因為在最終得到的多個分類器的線性組合中，可以給它們賦予負系數，同樣也能提升分類效果。

引用

[1] Quinlan, J. R. C4.5: Programs for Machine Learning. Morgan Kaufmann Publishers, 1993.

[2] Altman, N. S. An introction to kernel and nearest-neighbor nonparametric regression. The American Statistician. 1992, 46 (3): 175–185. doi:10.1080/00031305.1992.10475879

[3] Webb, G. I.; Boughton, J.; Wang, Z. Not So Naive Bayes: Aggregating One-Dependence Estimators. Machine Learning (Springer). 2005, 58 (1): 5–24. doi:10.1007/s10994-005-4258-6

[4] decisiontrees.net Interactive Tutorial

[5] Hamerly, G. and Elkan, C. Alternatives to the k-means algorithm that find better clusterings (PDF). Proceedings of the eleventh international conference on Information and knowledge management (CIKM). 2002

[6] Rakesh Agrawal and Ramakrishnan Srikant. Fast algorithms for mining association rules in large databases. Proceedings of the 20th International Conference on Very Large Data Bases, VLDB, pages 487-499, Santiago, Chile, September 1994.

[7] Cortes, C.; Vapnik, V. Support-vector networks. Machine Learning. 1995, 20 (3): 273–297. doi:10.1007/BF00994018

[8] Arthur Dempster, Nan Laird, and Donald Rubin. "Maximum likelihood from incomplete data via the EM algorithm". Journal of the Royal Statistical Society, Series B, 39 (1):1–38, 1977

[9] Susan Moskwa. PageRank Distribution Removed From WMT. [October 16, 2009]

[10] Freund, Yoav; Schapire, Robert E. A Decision-Theoretic Generalization of on-Line Learning and an Application to Boosting. 1995. CiteSeerX: 10.1.1.56.9855

『肆』 數據挖掘的經典演算法

1. C4.5：是機器學習演算法中的一種分類決策樹演算法，其核心演算法是ID3演算法。
2. K-means演算法：是一種聚類演算法。
3.SVM：一種監督式學習的方法，廣泛運用於統計分類以及回歸分析中
4.Apriori ：是一種最有影響的挖掘布爾關聯規則頻繁項集的演算法。
5.EM：最大期望值法。
6.pagerank：是google演算法的重要內容。
7. Adaboost:是一種迭代演算法，其核心思想是針對同一個訓練集訓練不同的分類器然後把弱分類器集合起來，構成一個更強的最終分類器。
8.KNN:是一個理論上比較成熟的的方法，也是最簡單的機器學習方法之一。
9.Naive Bayes：在眾多分類方法中，應用最廣泛的有決策樹模型和樸素貝葉斯（Naive Bayes）
10.Cart：分類與回歸樹，在分類樹下面有兩個關鍵的思想，第一個是關於遞歸地劃分自變數空間的想法，第二個是用驗證數據進行減枝。
關聯規則規則定義
在描述有關關聯規則的一些細節之前，我們先來看一個有趣的故事： 尿布與啤酒的故事。
在一家超市裡，有一個有趣的現象：尿布和啤酒赫然擺在一起出售。但是這個奇怪的舉措卻使尿布和啤酒的銷量雙雙增加了。這不是一個笑話，而是發生在美國沃爾瑪連鎖店超市的真實案例，並一直為商家所津津樂道。沃爾瑪擁有世界上最大的數據倉庫系統，為了能夠准確了解顧客在其門店的購買習慣，沃爾瑪對其顧客的購物行為進行購物籃分析，想知道顧客經常一起購買的商品有哪些。沃爾瑪數據倉庫里集中了其各門店的詳細原始交易數據。在這些原始交易數據的基礎上，沃爾瑪利用數據挖掘方法對這些數據進行分析和挖掘。一個意外的發現是：跟尿布一起購買最多的商品竟是啤酒！經過大量實際調查和分析，揭示了一個隱藏在尿布與啤酒背後的美國人的一種行為模式：在美國，一些年輕的父親下班後經常要到超市去買嬰兒尿布，而他們中有30%～40%的人同時也為自己買一些啤酒。產生這一現象的原因是：美國的太太們常叮囑她們的丈夫下班後為小孩買尿布，而丈夫們在買尿布後又隨手帶回了他們喜歡的啤酒。
按常規思維，尿布與啤酒風馬牛不相及，若不是藉助數據挖掘技術對大量交易數據進行挖掘分析，沃爾瑪是不可能發現數據內在這一有價值的規律的。
數據關聯是資料庫中存在的一類重要的可被發現的知識。若兩個或多個變數的取值之間存在某種規律性，就稱為關聯。關聯可分為簡單關聯、時序關聯、因果關聯。關聯分析的目的是找出資料庫中隱藏的關聯網。有時並不知道資料庫中數據的關聯函數，即使知道也是不確定的，因此關聯分析生成的規則帶有可信度。關聯規則挖掘發現大量數據中項集之間有趣的關聯或相關聯系。Agrawal等於1993年首先提出了挖掘顧客交易資料庫中項集間的關聯規則問題，以後諸多的研究人員對關聯規則的挖掘問題進行了大量的研究。他們的工作包括對原有的演算法進行優化，如引入隨機采樣、並行的思想等，以提高演算法挖掘規則的效率；對關聯規則的應用進行推廣。關聯規則挖掘在數據挖掘中是一個重要的課題，最近幾年已被業界所廣泛研究。

『伍』 數據挖掘核心演算法之一--回歸

數據挖掘核心演算法之一--回歸
回歸，是一個廣義的概念，包含的基本概念是用一群變數預測另一個變數的方法，白話就是根據幾件事情的相關程度，用其中幾件來預測另一件事情發生的概率，最簡單的即線性二變數問題(即簡單線性)，例如下午我老婆要買個包，我沒買，那結果就是我肯定沒有晚飯吃;復雜一點就是多變數(即多元線性，這里有一點要注意的，因為我最早以前犯過這個錯誤，就是認為預測變數越多越好，做模型的時候總希望選取幾十個指標來預測，但是要知道，一方面，每增加一個變數，就相當於在這個變數上增加了誤差，變相的擴大了整體誤差，尤其當自變數選擇不當的時候，影響更大，另一個方面，當選擇的倆個自變數本身就是高度相關而不獨立的時候，倆個指標相當於對結果造成了雙倍的影響)，還是上面那個例子，如果我丈母娘來了，那我老婆就有很大概率做飯;如果在加一個事件，如果我老丈人也來了，那我老婆肯定會做飯;為什麼會有這些判斷，因為這些都是以前多次發生的，所以我可以根據這幾件事情來預測我老婆會不會做晚飯。
大數據時代的問題當然不能讓你用肉眼看出來，不然要海量計算有啥用，所以除了上面那倆種回歸，我們經常用的還有多項式回歸，即模型的關系是n階多項式;邏輯回歸(類似方法包括決策樹)，即結果是分類變數的預測;泊松回歸，即結果變數代表了頻數;非線性回歸、時間序列回歸、自回歸等等，太多了，這里主要講幾種常用的，好解釋的(所有的模型我們都要注意一個問題，就是要好解釋，不管是參數選擇還是變數選擇還是結果，因為模型建好了最終用的是業務人員，看結果的是老闆，你要給他們解釋，如果你說結果就是這樣，我也不知道問什麼，那升職加薪基本無望了)，例如你發現日照時間和某地葡萄銷量有正比關系，那你可能還要解釋為什麼有正比關系，進一步統計發現日照時間和葡萄的含糖量是相關的，即日照時間長葡萄好吃，另外日照時間和產量有關，日照時間長，產量大，價格自然低，結果是又便宜又好吃的葡萄銷量肯定大。再舉一個例子，某石油產地的咖啡銷量增大，國際油價的就會下跌，這倆者有關系，你除了要告訴領導這倆者有關系，你還要去尋找為什麼有關系，咖啡是提升工人精力的主要飲料，咖啡銷量變大，跟蹤發現工人的工作強度變大，石油運輸出口增多，油價下跌和咖啡銷量的關系就出來了(單純的例子，不要多想，參考了一個根據遙感信息獲取船舶信息來預測糧食價格的真實案例，感覺不夠典型，就換一個，實際油價是人為操控地)。
回歸利器--最小二乘法，牛逼數學家高斯用的(另一個法國數學家說自己先創立的，不過沒辦法，誰讓高斯出名呢)，這個方法主要就是根據樣本數據，找到樣本和預測的關系，使得預測和真實值之間的誤差和最小;和我上面舉的老婆做晚飯的例子類似，不過我那個例子在不確定的方面只說了大概率，但是到底多大概率，就是用最小二乘法把這個關系式寫出來的，這里不講最小二乘法和公式了，使用工具就可以了，基本所有的數據分析工具都提供了這個方法的函數，主要給大家講一下之前的一個誤區，最小二乘法在任何情況下都可以算出來一個等式，因為這個方法只是使誤差和最小，所以哪怕是天大的誤差，他只要是誤差和裡面最小的，就是該方法的結果，寫到這里大家應該知道我要說什麼了，就算自變數和因變數完全沒有關系，該方法都會算出來一個結果，所以主要給大家講一下最小二乘法對數據集的要求：
1、正態性：對於固定的自變數，因變數呈正態性，意思是對於同一個答案，大部分原因是集中的;做回歸模型，用的就是大量的Y~X映射樣本來回歸，如果引起Y的樣本很凌亂，那就無法回歸
2、獨立性：每個樣本的Y都是相互獨立的，這個很好理解，答案和答案之間不能有聯系，就像擲硬幣一樣，如果第一次是反面，讓你預測拋兩次有反面的概率，那結果就沒必要預測了
3、線性：就是X和Y是相關的，其實世間萬物都是相關的，蝴蝶和龍卷風(還是海嘯來著)都是有關的嘛，只是直接相關還是間接相關的關系，這里的相關是指自變數和因變數直接相關
4、同方差性：因變數的方差不隨自變數的水平不同而變化。方差我在描述性統計量分析裡面寫過，表示的數據集的變異性，所以這里的要求就是結果的變異性是不變的，舉例，腦袋軸了，想不出例子，畫個圖來說明。(我們希望每一個自變數對應的結果都是在一個盡量小的范圍)
我們用回歸方法建模，要盡量消除上述幾點的影響，下面具體講一下簡單回歸的流程(其他的其實都類似，能把這個講清楚了，其他的也差不多)：
first，找指標，找你要預測變數的相關指標(第一步應該是找你要預測什麼變數，這個話題有點大，涉及你的業務目標，老闆的目的，達到該目的最關鍵的業務指標等等，我們後續的話題在聊，這里先把方法講清楚)，找相關指標，標准做法是業務專家出一些指標，我們在測試這些指標哪些相關性高，但是我經歷的大部分公司業務人員在建模初期是不靠譜的(真的不靠譜，沒思路，沒想法，沒意見)，所以我的做法是將該業務目的所有相關的指標都拿到(有時候上百個)，然後跑一個相關性分析，在來個主成分分析，就過濾的差不多了，然後給業務專家看，這時候他們就有思路了(先要有東西激活他們)，會給一些你想不到的指標。預測變數是最重要的，直接關繫到你的結果和產出，所以這是一個多輪優化的過程。
第二，找數據，這個就不多說了，要麼按照時間軸找(我認為比較好的方式，大部分是有規律的)，要麼按照橫切面的方式，這個就意味橫切面的不同點可能波動較大，要小心一點;同時對數據的基本處理要有，包括對極值的處理以及空值的處理。
第三， 建立回歸模型，這步是最簡單的，所有的挖掘工具都提供了各種回歸方法，你的任務就是把前面准備的東西告訴計算機就可以了。
第四，檢驗和修改，我們用工具計算好的模型，都有各種假設檢驗的系數，你可以馬上看到你這個模型的好壞，同時去修改和優化，這里主要就是涉及到一個查准率，表示預測的部分裡面，真正正確的所佔比例;另一個是查全率，表示了全部真正正確的例子，被預測到的概率;查准率和查全率一般情況下成反比，所以我們要找一個平衡點。
第五，解釋，使用，這個就是見證奇跡的時刻了，見證前一般有很久時間，這個時間就是你給老闆或者客戶解釋的時間了，解釋為啥有這些變數，解釋為啥我們選擇這個平衡點(是因為業務力量不足還是其他的)，為啥做了這么久出的東西這么差(這個就尷尬了)等等。
回歸就先和大家聊這么多，下一輪給大家聊聊主成分分析和相關性分析的研究，然後在聊聊數據挖掘另一個利器--聚類。