分類算法簡介

一、決策樹
決策樹是用于分類和預測的主要技術之一，決策樹學習是以實例為基礎的歸納學習算法，它著眼于從一組無次序、無規則的實例中 推理出以決策樹表示的分類規則。構造決策樹的目的是找出屬性和類別間的關系，用它來預測將來未知類別的記錄的類別。它采用自頂向下的遞歸方式，在決策樹的 內部節點進行屬性的比較，并根據不同屬性值判斷從該節點向下的分支，在決策樹的葉節點得到結論。
主要的決策樹算法有ID3、C4.5（C5.0）、CART、PUBLIC、SLIQ和SPRINT算法等。它們在選擇測試屬性采用的技術、生成的決策樹的結構、剪枝的方法以及時刻，能否處理大數據集等方面都有各自的不同之處。
決策樹的優點：
1、 決策樹易于理解和解釋.人們在通過解釋后都有能力去理解決策樹所表達的意義。
2、 對于決策樹，數據的準備往往是簡單或者是不必要的.其他的技術往往要求先把數據一般化，比如去掉多余的或者空白的屬性。
3、能夠同時處理數據型和常規型屬性。其他的技術往往要求數據屬性的單一。
4、決策樹是一個白盒模型。如果給定一個觀察的模型，那么根據所產生的決策樹很容易推出相應的邏輯表達式。
5、易于通過靜態測試來對模型進行評測。表示有可能測量該模型的可信度。
6、在相對短的時間內能夠對大型數據源做出可行且效果良好的結果。
7、可以對有許多屬性的數據集構造決策樹。
8、決策樹可很好地擴展到大型數據庫中，同時它的大小獨立于數據庫的大小。
決策樹的缺點：
1、 對于那些各類別樣本數量不一致的數據，在決策樹當中,信息增益的結果偏向于那些具有更多數值的特征。
2、決策樹處理缺失數據時的困難。
3、過度擬合問題的出現。
4、忽略數據集中屬性之間的相關性。


 二、貝葉斯
貝 葉斯（Bayes）分類算法是一類利用概率統計知識進行分類的算法，如樸素貝葉斯（Naive Bayes）算法。這些算法主要利用Bayes定理來預測一個未知類別的樣本屬于各個類別的可能性，選擇其中可能性最大的一個類別作為該樣本的最終類別。 由于貝葉斯定理的成立本身需要一個很強的條件獨立性假設前提，而此假設在實際情況中經常是不成立的，因而其分類準確性就會下降。為此就出現了許多降低獨立 性假設的貝葉斯分類算法，如TAN（Tree Augmented Na?ve Bayes)算法，它是在貝葉斯網絡結構的基礎上增加屬性對之間的關聯來實現的。
優點：
1、樸素貝葉斯模型發源于古典數學理論，有著堅實的數學基礎，以及穩定的分類效率。
2、NBC模型所需估計的參數很少，對缺失數據不太敏感，算法也比較簡單。
缺點：
1、理論上，NBC模型與其他分類方法相比具有最小的誤差率。但是實際上并非總是如此，這是因為NBC模型假設屬性之間相互獨立，這個假設在實際應用中 往往是不成立的（可以考慮用聚類算法先將相關性較大的屬性聚類），這給NBC模型的正確分類帶來了一定影響。在屬性個數比較多或者屬性之間相關性較大 時，NBC模型的分類效率比不上決策樹模型。而在屬性相關性較小時，NBC模型的性能最為良好。
2、需要知道先驗概率。
3、分類決策存在錯誤率


  三、人工神經網絡
人工神經網絡 （Artificial Neural Networks，ANN）是一種應用類似于大腦神經突觸聯接的結構進行信息處理的數學模型。在這種模型中，大量的節點（或稱”神經元”，或”單元”）之 間相互聯接構成網絡，即”神經網絡”，以達到處理信息的目的。神經網絡通常需要進行訓練，訓練的過程就是網絡進行學習的過程。訓練改變了網絡節點的連接權 的值使其具有分類的功能，經過訓練的網絡就可用于對象的識別。   
目前，神經網絡已有上百種不同的模型，常見的有BP網絡、徑向基RBF網 絡、Hopfield網絡、隨機神經網絡（Boltzmann機）、競爭神經網絡（Hamming網絡，自組織映射網絡）等。但是當前的神經網絡仍普遍存 在收斂速度慢、計算量大、訓練時間長和不可解釋等缺點。
人工神經網絡的優點：分類的準確度高,并行分布處理能力強,分布存儲及學習能力強，對噪聲神經有較強的魯棒性和容錯能力，能充分逼近復雜的非線性關系，具備聯想記憶的功能等。
人工神經網絡的缺點：神經網絡需要大量的參數，如網絡拓撲結構、權值和閾值的初始值；不能觀察之間的學習過程，輸出結果難以解釋，會影響到結果的可信度和可接受程度；學習時間過長,甚至可能達不到學習的目的。     

四、k-近鄰
k-近鄰(kNN，k-Nearest Neighbors)算法是一種基于實例的分類方法。該方法就是找出與未知樣本x距離最近的k個訓練樣本，看這k個樣本中多數屬于哪一類，就把x歸為那一 類。k-近鄰方法是一種懶惰學習方法，它存放樣本，直到需要分類時才進行分類，如果樣本集比較復雜，可能會導致很大的計算開銷，因此無法應用到實時性很強 的場合。
KNN算法的優點：
1、簡單、有效。
2、重新訓練的代價較低（類別體系的變化和訓練集的變化，在Web環境和電子商務應用中是很常見的）。
3、計算時間和空間線性于訓練集的規模（在一些場合不算太大）。
4、由于KNN方法主要靠周圍有限的鄰近的樣本，而不是靠判別類域的方法來確定所屬類別的，因此對于類域的交叉或重疊較多的待分樣本集來說，KNN方法較其他方法更為適合。
5、該算法比較適用于樣本容量比較大的類域的自動分類，而那些樣本容量較小的類域采用這種算法比較容易產生誤分。
KNN算法缺點：
1、 KNN算法是懶散學習方法（lazy learning,基本上不學習），一些積極學習的算法要快很多。
2、類別評分不是規格化的（不像概率評分）。

3、輸出的可解釋性不強，例如決策樹的可解釋性較強。

4、該算法在分類時有個主要的不足是，當樣本不平衡時，如一個類的樣本容量很大，而其他類樣本容量很小時，有可能導致當輸入一個新樣本時，該樣本的K個 鄰居中大容量類的樣本占多數。該算法只計算“最近的”鄰居樣本，某一類的樣本數量很大，那么或者這類樣本并不接近目標樣本，或者這類樣本很靠近目標樣本。 無論怎樣，數量并不能影響運行結果。可以采用權值的方法（和該樣本距離小的鄰居權值大）來改進。
5、計算量較大。目前常用的解決方法是事先對已知樣本點進行剪輯，事先去除對分類作用不大的樣本。


 
五、支持向量機
支持向量機（SVM，Support Vector Machine）是Vapnik根據統計學習理論提出的一種新的學習方法[43] ，它的最大特點是根據結構風險最小化準則，以最大化分類間隔構造最優分類超平面來提高學習機的泛化能力，較好地解決了非線性、高維數、局部極小點等問題。 對于分類問題，支持向量機算法根據區域中的樣本計算該區域的決策曲面，由此確定該區域中未知樣本的類別。
SVM的優點：
1、可以解決小樣本情況下的機器學習問題。
2、可以提高泛化性能。
3、可以解決高維問題。
4、可以解決非線性問題。
5、可以避免神經網絡結構選擇和局部極小點問題。
SVM的缺點：
1、對缺失數據敏感。
2、對非線性問題沒有通用解決方案，必須謹慎選擇Kernelfunction來處理。

 
六、基于關聯規則的分類
關 聯規則挖掘是數據挖掘中一個重要的研究領域。近年來，對于如何將關聯規則挖掘用于分類問題，學者們進行了廣泛的研究。關聯分類方法挖掘形如 condset→C的規則，其中condset是項(或屬性-值對)的集合，而C是類標號，這種形式的規則稱為類關聯規則（class association rules，CARS）。關聯分類方法一般由兩步組成：第一步用關聯規則挖掘算法從訓練數據集中挖掘出所有滿足指定支持度和置信度的類關聯規則；第二步使 用啟發式方法從挖掘出的類關聯規則中挑選出一組高質量的規則用于分類。屬于關聯分類的算法主要包括CBA[44] ，ADT[45] ，CMAR[46] 等。
 
七、集成學習（Ensemble Learning）
實際應用的復雜性和數據的多樣性往往使得單一的分類方法不夠有效。因此，學者們對多種分類方法的融合即集成學習進行了廣泛的研究。集成學習已成為國際機器學習界的研究熱點，并被稱為當前機器學習四個主要研究方向之一。
集 成學習是一種機器學習范式，它試圖通過連續調用單個的學習算法，獲得不同的基學習器，然后根據規則組合這些學習器來解決同一個問題，可以顯著的提高學習系 統的泛化能力。組合多個基學習器主要采用（加權）投票的方法，常見的算法有裝袋[47] （Bagging），提升/推進[48, 49] （Boosting）等。
集成學習由于采用了投票平均的方法組合多個分類器，所以有可能減少單個分類器的誤差，獲得對問題空間模型更加準確的表示，從而提高分類器的分類準確度。
 

八、遺傳算法
遺傳算法的優點：
1、與問題領域無關切快速隨機的搜索能力。
2、搜索從群體出發，具有潛在的并行性，可以進行多個個體的同時比較，魯棒性好。
3、搜索使用評價函數啟發，過程簡單。
4、使用概率機制進行迭代，具有隨機性。
5、具有可擴展性，容易與其他算法結合。
遺傳算法的缺點：
1、遺傳算法的編程實現比較復雜,首先需要對問題進行編碼,找到最優解之后還需要對問題進行解碼,
2、另外三個算子的實現也有許多參數,如交叉率和變異率,并且這些參數的選擇嚴重影響解的品質,而目前這些參數的選擇大部分是依靠經驗.沒有能夠及時利用網絡的反饋信息,故算法的搜索速度比較慢，要得要較精確的解需要較多的訓練時間。
3、算法對初始種群的選擇有一定的依賴性，能夠結合一些啟發算法進行改進。

九、Adaboosting方法
1、 adaboost是一種有很高精度的分類器。
2、可以使用各種方法構建子分類器，Adaboost算法提供的是框架。
3、當使用簡單分類器時，計算出的結果是可以理解的。而且弱分類器構造極其簡單。
4、簡單，不用做特征篩選。
5、不用擔心overfitting。

十、Rocchio的優點
Rocchio算法的突出優點是容易實現，計算（訓練和分類）特別簡單，它通常用來實現衡量分類系統性能的基準系統，而實用的分類系統很少采用這種算法解決具體的分類問題。



以 上簡單介紹了各種主要的分類方法，應該說其都有各自不同的特點及優缺點。對于數據庫負載的自動識別，應該選擇哪種方法呢？用來比較和評估分類方法的標準 [50] 主要有：
（1）預測的準確率。模型正確地預測新樣本的類標號的能力；
（2）計算速度。包括構造模型以及使用模型進行分類的時間；
（3）強壯性。模型對噪聲 數據或空缺值數據正確預測的能力；
（4）可伸縮性。對于數據量很大的數據集，有效構造模型的能力；
（5）模型描述的簡潔性和可解釋性。模型描述愈簡潔、愈 容易理解，則愈受歡迎。