常見數(shù)據(jù)挖掘算法分析

• 概述
  • 一般認(rèn)為，數(shù)據(jù)挖掘領(lǐng)域所使用的方法均屬于機器學(xué)習(xí)算法、深度學(xué)習(xí)算法和數(shù)據(jù)挖掘算法。
  • 一般認(rèn)為，數(shù)據(jù)挖掘領(lǐng)域的問題主要有分類、回歸、聚類、推薦、圖像識別、預(yù)測。
  • 一般認(rèn)為，數(shù)據(jù)挖掘領(lǐng)域所牽扯到的底層知識有“概率論”、“數(shù)論”、“統(tǒng)計學(xué)”、“線性代數(shù)”、“數(shù)字圖像處理”、“機器學(xué)習(xí)理論基礎(chǔ)”、“高等數(shù)學(xué)”。當(dāng)然，你也不一定很清楚原理，事實上很多數(shù)據(jù)挖掘師會用算法，但未必解釋的清楚自己用的算法。
• 挖掘思路
  • 一般來說，當(dāng)我們遇到一個問題，完成了數(shù)據(jù)探索和數(shù)據(jù)預(yù)處理（其實你就已經(jīng)完成了70%的工作），接下來的任務(wù)就是挖掘建模。
  • 通常明確問題類型之后，我們首先選擇普遍認(rèn)同的算法，如SVM（支持向量機）、GBDT（梯度提升樹）、Adaboost（這個玩機器學(xué)習(xí)的都知道是什么）等，當(dāng)然也有很多現(xiàn)在熱門的深度算法可供選擇，神經(jīng)網(wǎng)絡(luò)會是個不錯的方法。
  • 當(dāng)然，如果你說，我想找一個最好的方法，這是不可能的。挖掘建模，沒有最好的模型只有最合適的模型，例如很多標(biāo)準(zhǔn)化特征值的單標(biāo)簽問題選擇K-近鄰算法會是個很高效的選擇（盡管K-近鄰只是機器學(xué)習(xí)的一個入門算法，但是存在就是合理）。
  • 如果一個問題很吃精度，那么交叉驗證各個認(rèn)為可能合適的算法應(yīng)該是個不錯的選擇，當(dāng)然要保證每個算法參數(shù)合適得到最優(yōu)解。
  • 但是，很多時候，問題往往不是很需求精度，這時候一個相對“比較好”的算法就足夠了，那么如何判斷一個算法是否達(dá)到我的需求呢，這就要求你必須知道每個算法的優(yōu)缺點，這就是我接下來想說的東西。
• 常用算法及其優(yōu)缺點
  • 首先，在機器學(xué)習(xí)算法中有兩個常見問題：
    • 欠擬合。這是由于模型過于簡單產(chǎn)生了估計不準(zhǔn)確形成偏差（bias）。
    • 過擬合。這是由于模型太過復(fù)雜而帶來的更大的變化空間和不確定性形成方差（variance）。
      • 定義
        • 所謂過擬合（Overfit），是這樣一種現(xiàn)象：一個假設(shè)在訓(xùn)練數(shù)據(jù)上能夠獲得比其他假設(shè)更好的擬合，但是在訓(xùn)練數(shù)據(jù)外的數(shù)據(jù)集上卻不能很好的擬合數(shù)據(jù)。此時我們就叫這個假設(shè)出現(xiàn)了overfit的現(xiàn)象。
      • 產(chǎn)生原因
        • 出現(xiàn)這種現(xiàn)象的主要原因是訓(xùn)練數(shù)據(jù)中存在噪音或者訓(xùn)練數(shù)據(jù)太少。
      • 解決方法
        • 增大數(shù)據(jù)量。
        • 減少feature個數(shù)（人工定義留多少個feature或者算法選取這些feature）。
        • 正則化（留下所有的feature，但對于部分feature定義其parameter非常小）。
        • 交叉驗證。
    • 對于小訓(xùn)練集，高偏差&低方差的分類器（eg.樸素貝葉斯）要比低偏差&高方差的分類器（eg.KNN）的優(yōu)勢大，因為后者會過擬合。但是隨著訓(xùn)練集的增大，模型數(shù)據(jù)的預(yù)測能力就越強，偏差就會越低，此時低偏差&高方差分類器就表現(xiàn)出其優(yōu)勢，此時高偏差&低方差分類器已經(jīng)不足以提供準(zhǔn)確的模型了。
  • 樸素貝葉斯（NB）
    • 模型類別
      • 分類模型
    • 生成式模型，也就是說需要計算特征和類型的聯(lián)合概率分布，它很簡單，因為你不過是在計數(shù)而已。（我在之前的博客介紹過）它有一個獨立性假設(shè)，假設(shè)特征之間獨立分布，這就導(dǎo)致其收斂速度快于一般的判別模型，所以只需要少量訓(xùn)練集數(shù)據(jù)。即使這個獨立假設(shè)不成立，它還是有巨大功效。是由于獨立假設(shè)，直接忽略特征之間的相互作用，無法利用特征冗余。
    • 優(yōu)點
      • 發(fā)源于數(shù)論，分類效率穩(wěn)定。
      • 小規(guī)模數(shù)據(jù)表現(xiàn)極好，能處理多分類任務(wù)，適合增量式訓(xùn)練。
      • 對缺失數(shù)據(jù)不敏感，算法簡單，常用于文本分類（典型的是垃圾郵件過濾）。
    • 缺點
      • 需要計算先驗概率。
      • 對輸入數(shù)據(jù)形式敏感。
      • 分類決策存在錯誤率。
  • 邏輯回歸（Logistic Regression）
    • 模型類別
      • 分類模型
    • 判別式模型，一個分類模型。同時不需要像樸素貝葉斯那樣考慮特征是否相關(guān)，有很多正則化的方法（L0，L1，L2）。與決策樹和SVM相比還能得到一個不錯的概率解釋，甚至可以輕松地利用新數(shù)據(jù)來更新模型（在使用在線梯度下降算法時）。如果需要一個概率架構(gòu)（例如，簡單地調(diào)節(jié)分類閾值，指明不確定性，或者是獲得置信區(qū)間），或者需要將在以后的業(yè)務(wù)中將更多的訓(xùn)練數(shù)據(jù)快速地整合到模型中去，那么毫無疑問，選擇邏輯回歸。
    • 優(yōu)點
      • 實現(xiàn)簡單，廣泛使用于工業(yè)問題中。
      • 分類時計算量非常小，速度很快，存儲資源低。
      • 便利地觀測樣本概率分?jǐn)?shù)。
      • 對邏輯回歸而言，多重共線性不是問題，它可以結(jié)合L2正則化來解決該問題。
    • 缺點
      • 當(dāng)特征空間很大時，邏輯回歸性能較差。
      • 易欠擬合，準(zhǔn)確度不高。
      • 不能很好處理大量多類特征或變量。
      • 只能處理二分類問題。
      • 對于非線性特征，需要進(jìn)行轉(zhuǎn)換（畢竟是一個線性回歸模型）。
  • 最近鄰算法（KNN）
    • 模型類別
      • 分類模型
      • 回歸模型
      • 一個通俗易懂的分類方法，求出每一個測試樣本和訓(xùn)練樣本之間的距離（根據(jù)歐式距離或者曼哈頓距離等），選取與測試樣本距離最近的k個訓(xùn)練樣本數(shù)據(jù)，進(jìn)行投票得到最后的分類結(jié)果。如何選擇一個合適的k值，這取決于數(shù)據(jù)集。一般來說，選擇較大的k值能夠減小噪聲的影響，但會使得類別之間的界限變得模糊。一個較好的k值可以通過各種啟發(fā)式技術(shù)獲取，如交叉驗證。噪聲和非相關(guān)性特征的存在會使得k近鄰算法的準(zhǔn)確性減小。KNN具有較強的一致性結(jié)果，隨著數(shù)據(jù)趨于無限，算法保證錯誤率不會超過貝葉斯算法錯誤率的兩倍，對于一些好的k值，KNN保證錯誤率不會超過貝葉斯理論誤差率。
      • 優(yōu)點
        • 理論成熟，思想簡單，既可以做分類又可以做回歸。
        • 可用于非線性分類。
        • 訓(xùn)練時間復(fù)雜度僅為O(n)。
        • 對數(shù)據(jù)沒有假設(shè)，準(zhǔn)確度高，對離群值不敏感（outlier）。
      • 缺點
        • 計算量大。
        • 樣本不平衡問題（即有些類別的樣本數(shù)量多，有些類別的樣本數(shù)量少）。
        • 需要大量內(nèi)存。
  • 線性回歸（Linear Regression）
    • 模型類別
      • 回歸模型
    • 用于回歸，不同于邏輯回歸用于分類。其基本思想是用梯度下降法對最小二乘法形式的誤差函數(shù)進(jìn)行優(yōu)化，當(dāng)然也可以用正規(guī)方程組（normalequation）直接求得參數(shù)的解。具體有LR（線性回歸）和LWLR（局部加權(quán)線性回歸）兩種計算式，公式在我專門回歸的博客中敘述，其中LWLR是一種非參數(shù)模型，因為每次進(jìn)行回歸計算都要遍歷訓(xùn)練樣本至少一次。
    • 優(yōu)點
      • 實現(xiàn)簡單，計算簡單。
    • 缺點
      • 無法擬合非線性數(shù)據(jù)。
  • 決策樹
    • 模型類別
      • 分類模型
      • 回歸模型
    • 利用特征值的選擇區(qū)間建立的一個樹形結(jié)構(gòu)。決策樹學(xué)習(xí)一般三個步驟：特征選擇、決策樹的生成和決策樹的修剪。關(guān)于決策樹有很多經(jīng)典算法（ID3，C4.5，CART）。它易于解釋。它可以毫無壓力地處理特征間的交互關(guān)系并且是非參數(shù)化的，不必?fù)?dān)心異常值或者數(shù)據(jù)是否線性可分（舉個例子，決策樹能輕松處理好類別A在某個特征維度x的末端，類別B在中間，然后類別A又出現(xiàn)在特征維度x前端的情況）。它的缺點之一就是不支持在線學(xué)習(xí)，于是在新樣本到來后，決策樹需要全部重建。另一個缺點就是容易出現(xiàn)過擬合，但這也就是諸如隨機森林RF（或提升樹boostedtree）之類的集成方法的切入點。另外，隨機森林經(jīng)常是很多分類問題的贏家，它訓(xùn)練快速并且可調(diào)，同時你無須擔(dān)心要像支持向量機那樣調(diào)一大堆參數(shù)，所以在以前都一直很受歡迎。
    • 優(yōu)點
      • 計算簡單，易于理解，可解釋性強。
      • 比較適合處理有缺失屬性的樣本。
      • 能夠處理不相關(guān)特征。
      • 在短時間內(nèi)能對大數(shù)據(jù)源做出可行且效果良好的結(jié)果。
    • 缺點
      • 容易發(fā)生過擬合（隨機森林有效減少過擬合）。
      • 忽略數(shù)據(jù)之間的相關(guān)性。
      • 對于那些各類別樣本數(shù)量不一致的數(shù)據(jù)，在決策樹當(dāng)中,信息增益的結(jié)果偏向于那些具有更多數(shù)值的特征（只要是使用了信息增益，都有這個缺點，如RF）
  • Adaboost
    • 模型類別
      • 分類模型
    • Adaboost是一種加和模型，每個模型都是基于上一次模型的錯誤率來建立的，過分關(guān)注分錯的樣本，而對正確分類的樣本減少關(guān)注度，逐次迭代之后，可以得到一個相對較好的模型。其核心是通過訓(xùn)練集得到不同的弱分類器，集合起來，構(gòu)成強分類器。是一種典型的boosting算法。
    • 優(yōu)點
      • 是一種有很高精度的分類器。
      • 可以使用各種方法構(gòu)建子分類器，Adaboost算法提供的是框架。
      • 當(dāng)使用簡單分類器時，計算出的結(jié)果是可以理解的，并且弱分類器的構(gòu)造極其簡單。
      • 簡單，不用做特征篩選。
      • 不容易發(fā)生過擬合。
    • 缺點
      • 對離群值比較敏感。
  • 支持向量機（SVM）
    • 模型類別
      • 判別模型
      • 分類模型
      • 回歸模型
    • 高準(zhǔn)確率，為避免過擬合提供了很好的理論保證，而且就算數(shù)據(jù)在原特征空間線性不可分，只要給個合適的核函數(shù)，它就能運行得很好。在超高維的文本分類問題中特別受歡迎。可惜內(nèi)存消耗大，難以解釋，運行和調(diào)參也有些煩人，而隨機森林卻剛好避開了這些缺點，相對而言更加實用。
    • 優(yōu)點
      • 可以解決高維問題，即大型特征空間。
      • 能夠處理非線性特征的相互作用。
      • 無需依賴整個數(shù)據(jù)。
      • 可以提高泛化能力。
    • 缺點
      • 當(dāng)觀測樣本很多時，效率并不是很高。
      • 對非線性問題沒有通用解決方案，有時候很難找到一個合適的核函數(shù)。
      • 對缺失數(shù)據(jù)敏感。
      • 對于核的選擇也是有技巧的（libsvm中自帶了四種核函數(shù)：線性核、多項式核、RBF以及sigmoid核）：
        • 第一，如果樣本數(shù)量小于特征數(shù)，那么就沒必要選擇非線性核，簡單的使用線性核就可以了；
        • 第二，如果樣本數(shù)量大于特征數(shù)目，這時可以使用非線性核，將樣本映射到更高維度，一般可以得到更好的結(jié)果；
        • 第三，如果樣本數(shù)目和特征數(shù)目相等，該情況可以使用非線性核，原理和第二種一樣。
        • 對于第一種情況，也可以先對數(shù)據(jù)進(jìn)行降維，然后使用非線性核，這也是一種方法。
  • 人工神經(jīng)網(wǎng)絡(luò)
    • 模型類別
      • 使用范圍廣
    • 具體敘述，可以查看我專門關(guān)于人工神經(jīng)網(wǎng)絡(luò)博客。
    • 優(yōu)點
      • 分類的準(zhǔn)確度高。
      • 并行分布處理能力強,分布存儲及學(xué)習(xí)能力強。
      • 對噪聲神經(jīng)有較強的魯棒性和容錯能力，能充分逼近復(fù)雜的非線性關(guān)系。
      • 具備聯(lián)想記憶的功能。
    • 缺點
      • 神經(jīng)網(wǎng)絡(luò)需要大量的參數(shù)，如網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)、權(quán)值和閾值的初始值。
      • 不能觀察之間的學(xué)習(xí)過程，輸出結(jié)果難以解釋，會影響到結(jié)果的可信度和可接受程度。
      • 學(xué)習(xí)時間過長,甚至可能達(dá)不到學(xué)習(xí)的目的。
  • K-Means聚類
    • 模型類別
      • 聚類模型
    • 無監(jiān)督學(xué)習(xí)算法，在沒有訓(xùn)練集的條件下將特征接近的歸為一類。
    • 優(yōu)點
      • 算法簡單，容易實現(xiàn)。
      • 對處理大數(shù)據(jù)集，該算法是相對可伸縮的和高效率的，因為它的復(fù)雜度大約是O(nkt)，其中n是所有對象的數(shù)目，k是簇的數(shù)目,t是迭代的次數(shù)。通常k<<n。這個算法通常局部收斂。
      • 算法嘗試找出使平方誤差函數(shù)值最小的k個劃分。當(dāng)簇是密集的、球狀或團狀的，且簇與簇之間區(qū)別明顯時，聚類效果較好。
    • 缺點
      • 對數(shù)據(jù)類型要求較高，適合數(shù)值型數(shù)據(jù)。
      • 可能收斂到局部最小值，在大規(guī)模數(shù)據(jù)上收斂較慢。
      • K值比較難以選取。
      • 對初值的簇心值敏感，對于不同的初始值，可能會導(dǎo)致不同的聚類結(jié)果。
      • 不適合于發(fā)現(xiàn)非凸面形狀的簇，或者大小差別很大的簇。
      • 對于”噪聲”和孤立點數(shù)據(jù)敏感，少量的該類數(shù)據(jù)能夠?qū)ζ骄诞a(chǎn)生極大影響。

• 幾個常見算法對比

  • 簡述幾種常用算法的對比，具體算法的選擇需要根據(jù)數(shù)據(jù)集情況和算法優(yōu)缺點自行判斷選擇。
  • 樸素貝葉斯與邏輯回歸對比
    • 相同點
      • 都是對條件概率建模，對求得的不同類的分類結(jié)果有很好的解釋性，而不像SVM和神經(jīng)網(wǎng)絡(luò)解釋性不高。
    • 不同點
      • 在有相關(guān)性特征的數(shù)據(jù)上的學(xué)習(xí)，邏輯回歸好一些。邏輯回歸不會在特征是否相關(guān)上有局限性，它總是能找到一個最優(yōu)的參數(shù)。
      • 樸素貝葉斯的好處是不需要優(yōu)化參數(shù)，它可以直接得到一個計數(shù)表來計算需要的最終結(jié)果。然而，邏輯回歸需要學(xué)習(xí)這樣一個參數(shù)，然后去預(yù)測。
      • 樸素貝葉斯在小規(guī)模數(shù)據(jù)集上的表現(xiàn)很好，隨著數(shù)據(jù)的增多，特征維度的增加，邏輯回歸的效果更好，這是因為樸素貝葉斯是生成式模型，在有先驗的情況下模型能夠把數(shù)據(jù)訓(xùn)練的更好，而邏輯回歸屬于判別式模型，目標(biāo)驅(qū)動化，不去建模聯(lián)合概率，通過訓(xùn)練數(shù)據(jù)直接預(yù)測輸出，因此在數(shù)據(jù)足夠多的情況下能夠得到更好一些的效果。
  • 邏輯回歸與SVM的對比
    • 不同點
      • LR采用log損失，SVM采用Hinge損失。
      • LR對異常值敏感，SVM對異常值不敏感。
      • 在訓(xùn)練集較小時，SVM較適用，而LR需要較多的樣本。
      • LR模型找到的那個超平面，是盡量讓所有點都遠(yuǎn)離他，而SVM尋找的那個超平面，是只讓最靠近中間分割線的那些點盡量遠(yuǎn)離，即只用到那些支持向量的樣本。
      • 對非線性問題的處理方式不同，LR主要靠特征構(gòu)造，必須組合交叉特征，特征離散化。SVM也可以這樣，還可以通過kernel。
  • GBDT與隨機森林的對比
    • 相同點
      • 都是由多棵樹組成。
      • 最終的結(jié)果都是由多棵樹一起決定。
    • 不同點
      • 組成隨機森林的樹可以是分類樹，也可以是回歸樹；而GBDT只由回歸樹組成。
      • 組成隨機森林的樹可以并行生成；而GBDT只能是串行生成。
      • 對于最終的輸出結(jié)果而言，隨機森林采用多數(shù)投票等；而GBDT則是將所有結(jié)果累加起來，或者加權(quán)累加起來。
  • bagging與boosting的對比
    • 不同點
      • 二者的主要區(qū)別是 取樣方式不同 。bagging采用 均勻取樣 ，而Boosting根據(jù)錯誤率來取樣，因此boosting的分類精度要優(yōu)于Bagging。bagging的訓(xùn)練集的選擇是隨機的，各輪訓(xùn)練集之間相互獨立，而boostlng的各輪訓(xùn)練集的選擇與前面各輪的學(xué)習(xí)結(jié)果有關(guān)；bagging的各個預(yù)測函數(shù)沒有權(quán)重，而boosting是有權(quán)重的；bagging的各個預(yù)測函數(shù)可以并行生成，而boosting的各個預(yù)測函數(shù)只能順序生成。對于象神經(jīng)網(wǎng)絡(luò)這樣極為耗時的學(xué)習(xí)方法。bagging可通過并行訓(xùn)練節(jié)省大量時間開銷。
      • bagging和boosting都可以有效地提高分類的準(zhǔn)確性。在大多數(shù)數(shù)據(jù)集中，boosting的準(zhǔn)確性比bagging高。在有些數(shù)據(jù)集中，boosting會引起退化---過擬合（Overfit）。
      • Boosting思想的一種改進(jìn)型AdaBoost方法在郵件過濾、文本分類方面都有很好的性能。
      • Gradient boosting（又叫Mart, Treenet)：Boosting是一種思想，Gradient Boosting是一種實現(xiàn)Boosting的方法，它主要的思想是，每一次建立模型是在之前建立模型損失函數(shù)的梯度下降方向。損失函數(shù)(loss function)描述的是模型的不靠譜程度，損失函數(shù)越大，則說明模型越容易出錯。如果我們的模型能夠讓損失函數(shù)持續(xù)的下降，則說明我們的模型在不停的改進(jìn)，而最好的方式就是讓損失函數(shù)在其梯度（Gradient)的方向上下降。

• 一般算法選擇思路

  • 首當(dāng)其沖應(yīng)該選擇的就是邏輯回歸，如果它的效果不怎么樣，那么可以將它的結(jié)果作為基準(zhǔn)來參考，在基礎(chǔ)上與其他算法進(jìn)行比較；
  • 然后試試決策樹（隨機森林）看看是否可以大幅度提升你的模型性能。即便最后你并沒有把它當(dāng)做為最終模型，你也可以使用隨機森林來移除噪聲變量，做特征選擇； 　　- 如果特征的數(shù)量和觀測樣本特別多，那么當(dāng)資源和時間充足時（這個前提很重要），使用SVM不失為一種選擇。 　　通常情況下：[GBDT>=SVM>=RF>=Adaboost>=Others]，現(xiàn)在深度學(xué)習(xí)很熱門，很多領(lǐng)域都用到，它是以神經(jīng)網(wǎng)絡(luò)為基礎(chǔ)的。 　　- 算法固然重要，但好的數(shù)據(jù)卻要優(yōu)于好的算法，設(shè)計優(yōu)良特征是大有裨益的。假如你有一個超大數(shù)據(jù)集，那么無論你使用哪種算法可能對分類性能都沒太大影響（此時就可以根據(jù)速度和易用性來進(jìn)行抉擇）。
• 補充說明
  • 參考文獻(xiàn)
    • 《數(shù)據(jù)挖掘常用算法優(yōu)缺點分析》
    • 原文作者參考文獻(xiàn)
      • [1] https://en.wikipedia.org/wiki/Bias%E2%80%93variance_tradeoff
      • [2] http://blog.echen.me/2011/04/27/choosing-a-machine-learning-classifier/
      • [3] http://www.csuldw.com/2016/02/26/2016-02-26-choosing-a-machine-learning-classifier/
    • 原文中有不少錯誤，已經(jīng)改正，但可能任然存在說明性錯誤。

總結(jié)

以上是生活随笔為你收集整理的数据分析与挖掘理论-常用算法对比(纯理论较枯燥)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。