用於數據挖掘的分類演算法有哪些，各有何優劣？

11-16

嘗試將quora上的這個回答翻譯了下。第一次翻譯，不好之處請見諒。
What are the advantages of different classification algorithms?

以下是我這些年總結的指南

訓練集有多大？

如果你的訓練集很小，高偏差/低方差的分類器（如樸素貝葉斯）比低偏差/高方差的分類器（如K近鄰或Logistic回歸）更有優勢，因為後者容易過擬合。但是隨著訓練集的增大，高偏差的分類器並不能訓練出非常準確的模型，所以低偏差/高方差的分類器會勝出（它們有更小的漸近誤差）。

你也可以從生成模型與鑒別模型的區別來考慮它們。

某些分類器的優勢

樸素貝葉斯(Naive Bayes, NB)
超級簡單，就像做一些數數的工作。如果條件獨立假設成立的話，NB將比鑒別模型（如Logistic回歸）收斂的更快，所以你只需要少量的訓練數據。即使條件獨立假設不成立，NB在實際中仍然表現出驚人的好。如果你想做類似半監督學習，或者是既要模型簡單又要性能好，NB值得嘗試。

Logistic回歸(Logistic Regression, LR)
LR有很多方法來對模型正則化。比起NB的條件獨立性假設，LR不需要考慮樣本是否是相關的。與決策樹與支持向量機（SVM）不同，NB有很好的概率解釋，且很容易利用新的訓練數據來更新模型（使用在線梯度下降法）。如果你想要一些概率信息（如，為了更容易的調整分類閾值，得到分類的不確定性，得到置信區間），或者希望將來有更多數據時能方便的更新改進模型，LR是值得使用的。

決策樹（Decision Tree, DT）
DT容易理解與解釋（對某些人而言——不確定我是否也在他們其中）。DT是非參數的，所以你不需要擔心野點（或離群點）和數據是否線性可分的問題（例如，DT可以輕鬆的處理這種情況：屬於A類的樣本的特徵x取值往往非常小或者非常大，而屬於B類的樣本的特徵x取值在中間範圍）。DT的主要缺點是容易過擬合，這也正是隨機森林（Random Forest, RF）（或者Boosted樹）等集成學習演算法被提出來的原因。此外，RF在很多分類問題中經常表現得最好（我個人相信一般比SVM稍好），且速度快可擴展，也不像SVM那樣需要調整大量的參數，所以最近RF是一個非常流行的演算法。

支持向量機（Support Vector Machine, SVM）
很高的分類正確率，對過擬合有很好的理論保證，選取合適的核函數，面對特徵線性不可分的問題也可以表現得很好。SVM在維數通常很高的文本分類中非常的流行。由於較大的內存需求和繁瑣的調參，我認為RF已經開始威脅其地位了。

回到LR與DT的問題（我更傾向是LR與RF的問題），做個簡單的總結：兩種方法都很快且可擴展。在正確率方面，RF比LR更優。但是LR可以在線更新且提供有用的概率信息。鑒於你在Square(不確定推斷科學家是什麼，應該不是有趣的化身)，可能從事欺詐檢測：如果你想快速的調整閾值來改變假陽性率與假陰性率，分類結果中包含概率信息將很有幫助。無論你選擇什麼演算法，如果你的各類樣本數量是不均衡的（在欺詐檢測中經常發生），你需要重新採樣各類數據或者調整你的誤差度量方法來使各類更均衡。

但是。。。

更好的數據往往比更好的演算法更重要，提取好的特徵也需要很大的功夫。如果你的數據集非常大，那麼分類演算法的選擇可能對最後的分類性能影響並不大（所以可以根據運行速度或者易用性來選擇）。

如果你很在意分類的正確率，那麼你得嘗試多種分類器，根據交叉驗證的結果來挑選性能最好的。或者，學習下Netflix Prize和Middle Earth, 使用某種集成的方法來組合多個分類器。

直接轉載quora上的回答了

What are the advantages of different classification algorithms?

Here are some general guidelines I"ve found over the years.

How large is your training set?

If your training set is small, high bias/low variance classifiers (e.g., Naive Bayes) have an advantage over low bias/high variance classifiers (e.g., kNN or logistic regression), since the latter will overfit. But low bias/high variance classifiers start to win out as your training set grows (they have lower asymptotic error), since high bias classifiers aren"t powerful enough to provide accurate models.

You can also think of this as a generative model vs. discriminative model distinction.

Advantages of some particular algorithms

Advantages of Naive Bayes: Super simple, you"re just doing a bunch of counts. If the NB conditional independence assumption actually holds, a Naive Bayes classifier will converge quicker than discriminative models like logistic regression, so you need less training data. And even if the NB assumption doesn"t hold, a NB classifier still often performs surprisingly well in practice. A good bet if you want to do some kind of semi-supervised learning, or want something embarrassingly simple that performs pretty well.

Advantages of Logistic Regression: Lots of ways to regularize your model, and you don"t have to worry as much about your features being correlated, like you do in Naive Bayes. You also have a nice probabilistic interpretation, unlike decision trees or SVMs, and you can easily update your model to take in new data (using an online gradient descent method), again unlike decision trees or SVMs. Use it if you want a probabilistic framework (e.g., to easily adjust classification thresholds, to say when you"re unsure, or to get confidence intervals) or if you expect to receive more training data in the future that you want to be able to quickly incorporate into your model.

Advantages of Decision Trees: Easy to interpret and explain (for some people -- I"m not sure I fall into this camp). Non-parametric, so you don"t have to worry about outliers or whether the data is linearly separable (e.g., decision trees easily take care of cases where you have class A at the low end of some feature x, class B in the mid-range of feature x, and A again at the high end). Their main disadvantage is that they easily overfit, but that"s where ensemble methods like random forests (or boosted trees) come in. Plus, random forests are often the winner for lots of problems in classification (usually slightly ahead of SVMs, I believe), they"re fast and scalable, and you don"t have to worry about tuning a bunch of parameters like you do with SVMs, so they seem to be quite popular these days.

Advantages of SVMs: High accuracy, nice theoretical guarantees regarding overfitting, and with an appropriate kernel they can work well even if you"re data isn"t linearly separable in the base feature space. Especially popular in text classification problems where very high-dimensional spaces are the norm. Memory-intensive and kind of annoying to run and tune, though, so I think random forests are starting to steal the crown.

To go back to the particular question of logistic regression vs. decision trees (which I"ll assume to be a question of logistic regression vs. random forests) and summarize a bit: both are fast and scalable, random forests tend to beat out logistic regression in terms of accuracy, but logistic regression can be updated online and gives you useful probabilities. And since you"re at Square (not quite sure what an inference scientist is, other than the embodiment of fun) and possibly working on fraud detection: having probabilities associated to each classification might be useful if you want to quickly adjust thresholds to change false positive/false negative rates, and regardless of the algorithm you choose, if your classes are heavily imbalanced (as often happens with fraud), you should probably resample the classes or adjust your error metrics to make the classes more equal.

But...

Recall, though, that better data often beats better algorithms, and designing good features goes a long way. And if you have a huge dataset, your choice of classification algorithm might not really matter so much in terms of classification performance (so choose your algorithm based on speed or ease of use instead).

And if you really care about accuracy, you should definitely try a bunch of different classifiers and select the best one by cross-validation. Or, to take a lesson from the Netflix Prize and Middle Earth, just use an ensemble method to choose them all!

數據挖掘和機器學習好像差不多……？

//本人小白，為完成老師布置的「路面識別分類問題」，自學opencv，還在摸索。

這篇文章是學習了斯坦福大學《機器學習》、《學習OpenCV》、OpenCV中文文檔以及相關博客總結出來的，自認為已經了解各種分類器的工作原理（涉及數學公式推導部分還很薄弱）才敢動筆。不足之處懇請各位指點。

希望能幫到你。

==============

1. normal_bayes_classifier 樸素貝葉斯分類

OpenCV最簡單的監督學習分類器

這個分類器模型是建立在每一個類別的特徵向量服從正態分布的基礎上的（據說不滿足獨立分布，效果也很好）。

整個分布函數被假設為一個高斯分布，每一類別一組係數。當給定了訓練數據，演算法將會估計每一個類別的向量均值和方差矩陣，然後根據這些進行預測。

特點：如果沒有很多數據，該模型會比很多複雜的模型獲得更好的性能，因為複雜的模型用了太多假設，以致產生欠擬合。

附貝葉斯公式：

2.
k_nearest_neighbors（KNN） K近鄰

這個演算法首先貯藏所有的訓練樣本，然後通過分析（包括選舉，計算加權和等方式）一個新樣本周圍K個最近鄰，然後把新樣本標記為在K近鄰點中頻率最高的類。

這種方法有時候被稱作「基於樣本的學習」，即為了預測，我們對於給定的輸入搜索最近的已知其相應的特徵向量。

特點：簡單有效，但因為需要存儲所有的訓練集，佔用很大內存，速度比較慢。使用該方法前通常訓練集聚類來降低數據大小。

3.
support_vector_machines（SVM）
支持向量機

SVM是一種基於核函數的方法，它通過某些核函數把特徵向量映射到高維空間（一般情況下高維空間上比低維空間上更加線性可分），然後建立一個線性判別函數（或者說是一個高維空間中的能夠區分訓練數據的最優超平面）。

解是最優的在某種意義上是兩類中距離分割面最近的特徵向量和分割面的距離最大化。離分割面最近的特徵向量被稱為」支持向量」，意即其它向量不影響分割面（決策函數）。

註：

1. 當數據集合比較小的時候，支持向量機的效果常常最好。

2. 對於核來說，不僅僅只存在於 SVM 內，對於任意的演算法，只要計算時出現了內積的，都可以用核函數替代，從而提高在高維數據上的性能。

4.
decision_trees 決策樹

決策樹是一個二叉樹。當每個葉節點用類別標識（多個葉子可能有相同的標識）時，它可以表示分類樹；當每個葉節點被分配了一個常量（所以回歸函數是分段常量）時，決策樹就成了回歸樹。

決策樹是從根結點遞歸構造的。用所有的訓練數據（特徵向量和對應的響應）來在根結點處進行分裂。在每個結點處，優化準則（比如最優分裂）是基於一些基本原則來確定的（比如ML中的「純度purity」原則被用來進行分類，方差之和用來進行回歸）。所有的數據根據初始和替代分裂點來劃分給左右子結點（就像在預測演算法里做的一樣）。然後演算法回歸的繼續分裂左右子結點。在以下情況下演算法可能會在某個結點停止：

a) 樹的深度達到了指定的最大值

b) 在該結點訓練樣本的數目少於指定值，比如，沒有統計意義上的集合來進一步進行結點分裂了。

c) 在該結點所有的樣本屬於同一類（或者，如果是回歸的話，變化已經非常小了）

d) 跟隨機選擇相比，能選擇到的最好的分裂已經基本沒有什麼有意義的改進了。

決策樹自身的優點：

a) 計算簡單，易於理解；

b) 適應不同的數據類型（包括類別數據，數值數據，未歸一化的和混合的數據）；

c) 比較適合處理有缺失屬性的樣本；

d) 通過分裂的順序給數據特徵賦不同的重要性；

e) 能夠處理不相關的特徵；

f) 在相對短的時間內能夠對大型數據源做出可行且結果良好的結果；

g) 決策樹構成了其他演算法的基礎（如boosting和隨機數）。

決策樹的缺點：

a) 容易發生過擬合（隨即森林可以很大程度上減少過擬合）；

b) 忽略了數據之間的相關性；

c) 對於那些，各類別樣本數量不一致的數據，在決策樹中，信息增益的結果偏向於那些具有更多數值的特徵（只要使用了信息增益，都有這個特點，如RF）

5.
boosting

Boosting 是個非常強大的學習方法, 它也是一個監督的分類學習方法。它組合許多「弱」分類器來產生一個強大的分類器組。一個弱分類器的性能只是比隨機選擇好一點，因此它可以被設計的非常簡單並且不會有太大的計算花費。將很多弱分類器結合起來組成一個集成的強分類器。

boosting分類器和隨機森林在內部使用了決策樹，所以繼承了決策樹的很多有用的性質（能夠處理混合數據模型、沒有歸一化的數據、特徵丟失）。

AdaBoost演算法如下：

1.
給定N樣本 (xi,yi) 其中

2.
初始化權值

3.
重複 for m = 1,2,…,M:

a) 根據每個訓練數據的wi計算。

b) 計算

c) 更新權值

並歸一化使 Σiwi = 1.

4.
輸出分類器

優點：

簡單，不容易發生過擬合，不用做特徵篩選。

註：opencv執行的boosting演算法是一個兩類分類器（不像決策樹和隨機森林）

6.
random_trees 隨機森林

隨機森林既可以解決回歸問題，也可以解決分類問題。

隨機森林可以通過收集很多樹的子節點對各個類別投票，然後選擇獲得最多投票的類別作為判斷結果。通過計算」森林「的所有子節點的值的平均值來解決回歸問題。

隨機森林建立時的基本子系統也是決策樹。在建立決策樹時會一直繼續下去直到數據純凈。因此，儘管每個樹都很好的學習了訓練數據，但各個樹之間仍有很大不同。我們把這些樹放到一起求平均以消除這些不同（因此叫隨機森林）。

當然，如果所有的樹都相同，隨機森林也沒有很大作用。為了克服這點，隨機森林通過在樹的建立過程中，隨機選擇特徵子集來使各個樹不同。例如，一個目標識別樹可以有很多可能的特徵：顏色，質地，傾斜度等。樹的每個節點可以從這些特徵中隨機的選擇子集，來決定怎樣更好地分裂數據。每個後來的節點都獲得新的、隨機選擇的特徵子集。

優點：

與boosting和決策樹相比，隨機森林可以使用更少的重要變數，獲得最好的預測性能。即我們可以收縮特徵集的大小，在不損失性能的前提下減少計算量和內存使用隨機森林。

7.
neural_networks 神經網路

神經網路是對非線性可分數據的分類方法。

與輸入直接相連的稱為隱藏層（ hidden layer），與輸出直接相連的稱為輸出層（output layer）。

神經網路演算法的一大特點就在於不知道隱藏層計算的東西的意義；另一個特點在於神經網路有比較多的局部最優值，可以通過多次隨機設定初始值然後運行梯度下降演算法獲得最優值。

感覺難在特徵選取。

以下是個迅速的回答：
1. 這個問題本身是個meta-learning，即對方法進行分類-&> 不可能有定論，以上抽樣舉例式的回答是一種回答方式，這裡嘗試從抽象層面進行回答。
2. 總體上總是可以分成高維方法和低維方法。高維亦即非參數模型，低維即參數模型。顯然，非參數方法集之於參數方法集如同無理數集之於有理數集。
3. 參數方法的一個大塊是線性模型，統計中這叫回歸，數學中這叫投影。這反映了一個應用數學式的思路：一開始問題總是無窮維的，然後開始用投影進行降維，同時加上矢量空間假設，而所有非線性的部分全部扔到坐標軸內部。
4. 參數方法的另一個大塊是分布模型，基於似然函數的方法（極大似然）和貝葉斯（先驗x似然=後驗）。分布模型本質也是降維，把問題降到低維度的參數空間里，並且允許樣本誤差的存在。事實上線性模型在統計觀點下也是一個分布模型，應變數的分布。這樣一來回歸的多變性不僅在於投影基矢量的構造，還在於應變數分布的概率模型。這是高於應用數學思想的。
5. 當然還可以有別的參數方法。
6. 非參模型的一些例子前面的回答已經提過不少，如kernel，決策樹，boosting，bootstrap等等等等。

分享一篇：

A Data-Driven Approach to Choosing Machine Learning Algorithms

原文A Data-Driven Approach to Choosing Machine Learning Algorithms - Machine Learning Mastery

數據驅動思想，多做嘗試。

There"s no best algorithms

剛入坑的菜雞，如有錯誤請指出。KNN-近領演算法。最懶惰的學習方法，大概流程就是取一個點，找到離這個點最近的n個點，看哪一個類別最多就預測那一個類別。優勢：易於操作，對於複雜的情況也可以做到可以接受的效果。缺點：訓練集緯度高時，因為高維災難的緣故，表現會很差。當k取太小時極容易過度擬合。
有空再說一下LDA和QDA