從小白視角了解<資料挖掘十大算法>

目錄

• 算法分類
• 一、PageRank
  • 原理
  • 比喻說明
• 二、Apriori（關聯分析）
• 三、AdaBoost
• 四、C4.5（決策樹）
• 五、CART（決策樹）
• 六、樸素貝葉斯（條件機率）
• 七、SVM
• 八、KNN（聚類）
• 九、K-Means（聚類）
• 十、EM（聚類）

連接配接分析：PageRank

關聯分析：Apriori

分類算法：C4.5，樸素貝葉斯，SVM，KNN，Adaboost，CART

聚類算法：K-Means，EM

當一篇論文被引用的次數越多，證明這篇論文的影響力越大。

一個網頁的傳入連結越多，傳入連結越優質，網頁的品質越高

網頁影響力=阻尼影響力+所有傳入連結集合頁面的權重影響力之和
           

• 一個網頁的影響力：所有傳入連結的頁面的權重影響力之和
• 一個網頁對其他網頁的影響力貢獻為：自身影響力/對外連結數量

• 使用者并不都是按照跳轉連結的方式來上網，還有其他的方式，比如直接輸入網址通路，

  是以需要設定阻尼因子，代表了使用者按照跳轉連結來上網的機率

1. 微網誌

   一個人的微網誌粉絲數不一定等于他的實際影響力，還需要看粉絲的品質如何。

   如果是僵屍粉沒什麼用，但如果是很多大V或者明星關注，影響力很高。

2. 店鋪的經營

   顧客比較多的店鋪品質比較好，但是要看看顧客是不是托。

3. 興趣

   在感興趣的人或事身上投入了相對多的時間，對其相關的人事物也會投入一定的時間。

   那個人或事，被關注的越多，它的影響力/閱聽人也就越大。

關于阻尼因子

1. 通過你的鄰居的影響力來評判你的影響力，但是如果不能通過鄰居來通路你，并不代表你沒有影響力，因為可以直接通路你，是以引入阻尼因子的概念
2. 海洋除了有河流流經，還有雨水，但是下雨是随機的

3. 提出阻尼系數，還是為了解決某些網站明明存在大量對外連結（傳入連結），但是影響力卻非常大的情形。

   對外連結例子：hao123導航網頁，對外連結極多傳入連結極少

   傳入連結例子：百度谷歌等搜尋引擎，傳入連結極多對外連結極少。

關聯關系挖掘，從消費者交易記錄中發掘商品與商品之間的關聯關系

1.支援度

某個商品組合出現的次數與總次數之間的比例

5次購買，4次買了牛奶，牛奶的支援度為4/5=0.8

5次購買，3次買了牛奶+面包，牛奶+面包的支援度為3/5=0.6

2.置信度

購買了商品A，有多大機率購買商品B，A發生的情況下B發生的機率是多少

買了4次牛奶，其中2次買了啤酒，(牛奶->啤酒)的置信度為2/4=0.5

買了3次啤酒，其中2次買了牛奶，(啤酒->牛奶)的置信度為2/3-0.67

3.提升度

衡量商品A的出現，對商品B的出現 機率提升的程度

提升度(A->B)=置信度(A->B)/支援度(B)
           

提升度>1，有提升； 提升度=1，無變化； 提升度<1，下降

4.頻繁項集

項集：可以是單個商品，也可以是商品組合

頻繁項集是支援度大于最小支援度（Min Support）的項集

計算過程

1. 從K=1開始，篩選頻繁項集。
2. 在結果中，組合K+1項集，再次篩選
3. 循環1、2步。直到找不到結果為止，K-1項集的結果就是最終結果。

擴充：FP-Growth 算法

Apriori 算法需要多次掃描資料庫，性能低下，不适合大資料量

FP-growth算法，通過建構 FP 樹的資料結構，将資料存儲在 FP 樹中，隻需要在建構 FP 樹時掃描資料庫兩次，後續處理就不需要再通路資料庫了。

啤酒和尿不濕擺在一起銷售

沃爾瑪通過資料分析發現，美國有嬰兒的家庭中，一般是母親在家照顧孩子，父親去超市買尿不濕。

父親在購買尿不濕時，常常會順便搭配幾瓶啤酒來犒勞自己，于是，

超市嘗試推出了将啤酒和尿不濕擺在一起的促銷手段，這個舉措居然使尿不濕和啤酒的銷量都大幅增加。

簡單的說，多個弱分類器訓練成為一個強分類器。

将一系列的弱分類器以不同的權重比組合作為最終分類選擇

1. 初始化基礎權重
2. 獎權重矩陣，通過已的分類器計算錯誤率，選擇錯誤率最低的為最優分類器
3. 通過分類器權重公式，減少正确樣本分布，增加錯誤樣本分布，得到新的權重矩陣和目前k輪的分類器權重
4. 将新的權重矩陣，帶入上面的步驟2和3，重新計算權重矩陣
5. 疊代N輪，記錄每一輪的最終分類器權重，得到強分類器

1. 利用錯題提升學習效率

   做正确的題，下次少做點，反正都會了

   做錯的題，下次多做點，集中在錯題上

   随着學習的深入，做錯的題會越來越少

2. 合理跨界提高盈利

   蘋果公司，軟硬結合，占據了大部分的手機市場利潤，兩個領域的知識結合起來産生新收益

決策就是對于一個問題，有多個答案，選擇答案的過程就是決策。

C4.5算法是用于産生決策樹的算法，主要用于分類

C4.5使用資訊增益率做計算（ID3算法使用資訊增益做計算）

C4.5選擇最有效地方式對樣本集進行分裂，分裂規則是分析所有屬性的資訊增益率

資訊增益率越大，意味着這個特征分類的能力越強，我們就要優先選擇這個特征做分類

挑西瓜

拿到一個西瓜，先判斷它的紋路，如果很模糊，就認為這不是好瓜，如果它清晰，就認為它是一個好瓜，如果它稍稍模糊，就考慮它的密度，密度大于某個值，就認為它是好瓜，否則就是壞瓜。

CART：Classification And Regression Tree，中文叫分類回歸樹，即可以做分類也可以做回歸。

什麼是分類樹、回歸樹？

分類樹：處理離散資料，也就是資料種類有限的資料，輸出的是樣本的類别 。

回歸樹：可以對連續型的數值進行預測，輸出的是一個數值，數值在某個區間内都有取值的可能。

回歸問題和分類問題的本質一樣，都是針對一個輸入做出一個輸出預測，其差別在于輸出變量的類型

• CART分類樹

  與C4.5算法類似，隻是屬性選擇的名額是基尼系數。

  基尼系數反應了樣本的不确定度，基尼系數越小，說明樣本之間的差異性小，不确定程度低。

  分類是一個不确定度降低的過程，CART在構造分類樹的時候會選擇基尼系數最小的屬性作為屬性的劃分。

• CART 回歸樹

  采用均方誤差或絕對值誤差為标準，選取均方誤差或絕對值誤差最小的特征

• 分類：預測明天是陰、晴還是雨
• 回歸：預測明天的氣溫是多少度

樸素貝葉斯是一種簡單有效的常用分類算法，計算未知物體出現的條件下各個類别出現的機率，取機率最大的分類

假設輸入的不同特征之間是獨立的，基于機率論原理，通過先驗機率P(A)、P(B)和條件機率推算出後機率出P(A|B)

P(A)：先驗機率，即在B事件發生之前，對A事件機率的一個判斷。

P(B|A)：條件機率，事件 B 在另外一個事件 A 已經發生條件下的發生機率

P(A|B)：後驗機率，即在B事件發生之後，對A事件機率的重新評估。

給病人分類

症狀	職業	疾病
打噴嚏	護士	感冒
	農夫	過敏
頭痛	建築勞工	腦震蕩
	教師

給定一個新病人，是一個打噴嚏的建築勞工，計算他患感冒的機率

SVM： Support Vector Machine，中文名為支援向量機，是常見的一種分類方法，最初是為二分類問題設計的，在機器學習中，SVM 是有監督的學習模型。

什麼是有監督學習和無監督學習 ？

有監督學習：即在已有類别标簽的情況下，将樣本資料進行分類。

無監督學習：即在無類别标簽的情況下，樣本資料根據一定的方法進行分類，即聚類，分類好的類别需要進一步分析後，進而得知每個類别的特點。

找到具有最小間隔的樣本點，然後拟合出一個到這些樣本點距離和最大的線段/平面。

硬間隔：資料是線性分布的情況，直接給出分類

軟間隔：允許一定量的樣本分類錯誤。

核函數：非線性分布的資料映射為線性分布的資料。

1.分隔桌上一堆紅球和籃球

用一根線将桌上的紅球和藍球分成兩部分

2.分隔箱子裡一堆紅球和籃球

用一個平面将箱子裡的紅球和藍球分成兩部分

機器學習算法中最基礎、最簡單的算法之一，既能分類也能回歸，通過測量不同特征值之間的距離來進行分類。

計算待分類物體與其他物體之間的距離，對于K個最近的鄰居，所占數量最多的類别，預測為該分類對象的類别

計算步驟

1. 根據場景，選取距離計算方式，計算待分類物體與其他物體之間的距離
2. 統計距離最近的K個鄰居
3. 對于K個最近的鄰居，所占數量最多的類别，預測為該分類對象的類别

近朱者赤，近墨者黑

K-means是一個聚類算法，是無監督學習，生成指定K個類，把每個對象配置設定給距離最近的聚類中心

1.随機選取K個點為分類中心點

2.将每個點配置設定到最近的類，這樣形成了K個類

3.重新計算每個類的中心點。比如都屬于同一個類别裡面有10個點，那麼新的中心點就是這10個點的中心點，一種簡單的方式就是取平均值。

1.選老大

大家随機選K個老大，誰離得近，就是那個隊列的人（計算距離，距離近的人聚合在一起）

随着時間的推移，老大的位置在變化（根據算法，重新計算中心點），直到選出真正的中心老大（重複，直到準确率最高）

2.Kmeans和Knn的差別

Kmeans開班選老大，風水輪流轉，直到選出最佳中心老大

Knn小弟加隊伍，離那個班相對近，就是那個班的

EM 的英文是 Expectation Maximization，是以 EM 算法也叫最大期望算法，也是聚類算法的一種。

EM和K-Means的差別：

1. EM是計算機率，KMeans是計算距離。
2. EM屬于軟聚類，同一樣本可能屬于多個類别；而K-Means屬于硬聚類，一個樣本隻能屬于一個類别。是以前者能夠發現一些隐藏的資料。

先估計一個大機率的可能參數，然後再根據資料不斷地進行調整，直到找到最終的确認參數

菜稱重。

很少有人用稱對菜進行稱重，再計算一半的分量進行平分。

大部分人的方法是：

1. 先分一部分到碟子 A 中，再把剩餘的分到碟子 B 中
2. 觀察碟子 A 和 B 裡的菜是否一樣多，哪個多就勻一些到少的那個碟子裡
3. 然後再觀察碟子 A 和 B 裡的是否一樣多，重複下去，直到份量不發生變化為止。

到這裡，10大算法都已經說完了，其實一般來說，常用算法都已經被封裝到庫中了，隻要new出相應的模型即可，關于如何用模型進行資料挖掘，可以看資料挖掘的葵花寶典