數據挖掘中的分類算法研究

文/孟磊 劉靜萍

當前，我們所處的時代是數據爆炸式增長的時代，來自于社會生產、工程、醫療、商業及科學研究領域的數據每天都在增長。這些數據類型多樣、數據量巨大、價值密度低、增長速度快, 只有對這些數據進行合理的組織和分析才能發掘其背后的應用價值[1]。數據挖掘的誕生就是為了對海量數據進行分析、分類并提取有價值的信息，為研究者做出進一步預測和判斷提供數據基礎[2]。分類是數據挖掘中一個重要的研究領域，其研究內容是在一群已經知道類別標號的樣本中，訓練一種分類器，讓其能夠對某種未知的樣本進行分類。分類算法的分類過程就是建立一種分類模型來描述預定的數據集或概念集，通過分析由屬性描述的數據庫元組來構造模型。分類的目的就是使用分類器對新的數據集進行劃分，其主要涉及分類規則的準確性、過擬合、矛盾劃分的取舍等。解決分類問題的方法很多，單一的分類方法主要包括：決策樹、貝葉斯、神經網絡、K近鄰、支持向量機和基于關聯規則的分類等，另外還有用于組合單一分類方法的集成學習算法，如Bagging和Boosting等。

常用分類算法分析

從大量歷史數據中挖掘并找出隱含的規律是分類算法的特性之一，可用于預測或者分析。更具體地說，分類是構建一個函數，輸入樣本數據，輸出可期望的結果。分類的目標是使學到的函數很好地適用于“新樣本”，而不僅僅是在訓練樣本上表現得很好。學到的函數適用于新樣本的能力，稱為泛化能力。

樸素貝葉斯分類

樸素貝葉斯分類(NBC)是以貝葉斯定理為基礎并且假設特征條件之間相互獨立的方法。先通過已給定的訓練集，以特征詞之間獨立作為前提假設，學習從輸入到輸出的聯合概率分布，再基于學習到的模型，輸入X求出使得后驗概率最大的輸出Y。

設有樣本數據集D={d1,d2,…,dn}，對應樣本數據的特征屬性集為X={x1,x2,…xd}，類變量為Y={y1,y2,…,ym}, 即D可以分為ym類別。其中x1,x2,…xd相互獨立且隨機，則Y的先驗概率為Pprior=P(Y), Y的后驗概率為Ppost=P(Y|X)，由樸素貝葉斯算法可得，后驗概率可以由先驗概率Pprior=P(Y)、證據P(X)類條件概率P(Y|X)計算出：

樸素貝葉斯基于各特征之間相互獨立，在給定類別為y的情況下，上式可以進一步表示為下式：

由以上兩式可以計算出后驗概率為：

由于P(X)的大小是固定不變的，因此在比較后驗概率時，只比較上式的分子部分即可。因此可以得到一個樣本數據屬于類別yi的樸素貝葉斯計算：

樸素貝葉斯方法的特點是結合先驗概率和后驗概率，既避免了只使用先驗概率的主觀偏見，也避免了單獨使用樣本信息的過擬合現象。樸素貝葉斯發源于古典數學理論，有著堅實的數學基礎。該算法是基于條件獨立性假設的一種算法，當條件獨立性假設成立時，利用貝葉斯公式計算出其后驗概率，即該對象屬于某一類的概率，選擇具有最大后驗概率的類作為該對象所屬的類。該算法的優點是：邏輯簡單，易于實現，算法所需估計的參數很少；算法對缺失數據不太敏感，具有較小的誤差分類率；算法性能穩定，健壯性比較好。缺點是：在屬性個數比較多或者屬性之間相關性較大時，NBC模型的分類效果相對較差；算法是基于條件獨立性假設的，在實際應用中很難成立，故會影響分類效果。

K近鄰

K近鄰(K-Nearest Neighbor，KNN)分類算法是一個理論上比較成熟的方法，也是最簡單的機器學習算法之一。該方法的思路是：在特征空間中，如果一個樣本附近的K個最近（即特征空間中最鄰近）樣本的大多數屬于某一個類別，則該樣本也屬于這個類別。

如圖1所示，有兩類不同的樣本數據，分別用紅色的小正方形和綠色的圓形表示，而圖正中間的藍色的菱形所標示的數據則是待分類的數據。也就是說，現在，我們不知道藍色的數據是從屬于哪一類（紅色小正方形或者是綠色圓形）。下面，我們就要解決這個問題：給這個藍色的菱形分類。

圖1 K近鄰算法示意

如果K=3，藍色菱形最近的3個鄰居是1個綠色圓形和2個紅色小正方形，少數從屬于多數，基于統計的方法，判定藍色的待分類點屬于紅色的正方形一類。如果K=6，藍色菱形最近的5個鄰居是2個紅色正方形和3個綠色的圓形，少數從屬于多數，基于統計的方法，判定藍色的待分類點屬于綠色的圓形一類。

因此，我們看到，當無法判定當前待分類點是從屬于已知分類中的哪一類時，依據統計學的理論看它所處的位置特征，衡量它周圍鄰居的權重，而把它歸為或分配到權重更大的那一類。這就是K近鄰算法的核心思想。該算法的優點是：算法簡單，有效適用于樣本容量比較大的類域的自動分類；主要依靠周圍有限的鄰近的樣本，而不是依靠判別類域的方法來確定所屬類別的，因此對于類域的交叉或重疊較多的待分樣本集來說，KNN方法較其他方法更為適合。缺點是：算法計算量較大，算法需要事先確定K值；算法輸出的可解釋不強；算法對樣本容量較小的類域很容易產生誤分。

支持向量機

支持向量機（Support Vector Machines, SVM）是一種二分類模型，它的基本模型是定義在特征空間上的間隔最大的線性分類器，間隔最大使它有別于感知機。SVM還包括核技巧，這使它成為實質上的非線性分類器。SVM的學習策略就是間隔最大化，可形式化為一個求解凸二次規劃的問題，也等價于正則化的合頁損失函數的最小化問題。SVM的學習算法就是求解凸二次規劃的最優化算法。

SVM學習的基本想法是求解能夠正確劃分訓練數據集并且幾何間隔最大的分離超平面，如圖2所示。對于線性可分的數據集來說，這樣的超平面有無窮多個（即感知機），但是幾何間隔最大的分離超平面卻是唯一的。

圖2 SVM算法示意

在分類問題中給定輸入數據和學習目標X={X1,X2,…XN}，y={y1,y2,…,yN}，其中輸入數據的每個樣本都包含多個特征并由此構成特征空間而學習目標為二元變量表示負類和正類。若輸入數據所在的特征空間存在作為決策邊界的超平面，將學習目標按正類和負類分開，并使任意樣本的點到平面距離大于等于1。

則稱該分類問題具有線性可分性，w, b參數分別為超平面的法向量和截距。滿足該條件的決策邊界實際上構造了2個平行的超平面作為間隔邊界以判別樣本的分類：

所有在上間隔邊界上方的樣本屬于正類，在下間隔邊界下方的樣本屬于負類。兩個間隔邊界的距離被定義為邊距，位于間隔邊界上的正類和負類樣本為支持向量。

SVM算法是建立在統計學習理論基礎上的機器學習方法，通過學習算法，SVM可以自動尋找出對分類有較好區分能力的支持向量，由此構造出的分類器可以最大化類與類的間隔，因而有較好的適應能力和較高的分準率。該算法的優點是：有很高的分準率和泛化性能；能很好地解決高維問題，對小樣本情況下的分類問題效果較好。缺點是：對缺失數據敏感，對非線性問題沒有通用解決方案，得謹慎選擇核函數來處理。

分類器的創建

分類算法在生產和生活中有很多應用場景，如：日常事務[3][4]、醫療[5]、交通運輸[6]、建筑工程[7]、金融[8]等領域。分類算法的應用極大地提高了相關領域的工作效率，節省了大量的人力資源。本節闡述了樸素貝葉斯、K近鄰和SVM三種算法在日常生活中的應用。

對數據集進行分析

要在程序中使用這些數據集，需要了解數據的詳細信息。通常數據集由數據集名稱、實例個數、屬性個數、屬性名稱和分類名稱構成。本文的實驗部分選用了UCI數據集中的三種，分別是紅酒數據集、鳶尾花數據集和乳腺癌數據集。這三組數據集都可以用來做分類測試，其屬性如表1所示。

表1 數據集屬性表

以鳶尾花數據集為例，數據集打開后可以看到文本的排列：每行5個數以逗號分隔，共150行，每行的前4列分別對應4個屬性值，而最后一列為每個數據所屬類別。

生成訓練數據集和測試數據集

在創建分類算法模型時，需要對模型進行評判，否則無法知道模型的分類是否準確。因此必須將數據集分為兩個部分：一部分稱為訓練數據集，用以學習數據的特征屬性，這部分數據需要人工標定，為數據生成標簽；另一部分稱為測試數據集，用來檢驗模型的性能如何，不需要人工標定。

Python中的 scikit-am機器學習庫中，有一個 train_test_split 函數，可以把數據集拆分成訓練集和測試集。其工作原理是： train_test_split函數將數據集進行隨機排列，在默認情況下將其中75%的數據及所對應的標簽劃歸到訓練數據集，并將其余25%的數據和所對應的標簽劃歸到測試數據集。

使用分類算法建模

對分類算法建模可以用Python中scikit-learn機器學習庫中的分類器，也可以自己編程建模。本節采用樸素貝葉斯算法，以紅酒數據集作為測試集和訓練集進行建模，來說明算法的建模過程，如圖3所示。

圖3 樸素貝葉斯分類的流程

對新樣本分類進行預測

分類模型建好之后，就可以用于對新的樣本分類進行預測。不過在此之前，最好先用測試數據集對模型進行打分，這就是創建測試數據集的目的。測試數據集不參與建模，但是可以用模型對測試數據集進行分類，然后和測試數據集中的樣本實際分類進行對比，當吻合度越高，模型的得分會越高，說明模型的預測越準確，滿分是1.0。

Python仿真結果分析

本文的實驗部分選擇了三種算法和三組數據集，將不同的數據集分成訓練集和測試集，用訓練集來構建分類器，并用測試集來驗證分類器的準確率。

表2是三種算法在三種數據集上的分類準確率情況。

表2 三種算法的分類準確率

從表2中的數據可以看到，三種算法在數據集的分類上準確率都較高。其中高斯樸素貝葉斯分類器在符合正態分布的數據集上分類準確率最高；K近鄰分類器分類準確率對數據集的依賴性最強，也即模型的泛化能力是最弱的；本文中支持向量機分類器的內核為RBF（徑向基函數）內核，在三種算法中分類效果最為穩定，模型的泛化能力是三種分類器中最強的。

本文通過對數據挖掘分類算法中的三種經典算法，樸素貝葉斯算法、K近鄰算法和SVM算法的深入研究和對比發現：樸素貝葉斯依據概率論的原理建模，算法邏輯簡單，易于實現，對缺失數據不太敏感，具有較小的誤差分類率，但是在屬性個數比較多或者屬性之間相關性較大時，NBC 模型的分類效果相對較差。K近鄰算法是最簡單的分類算法，缺點是算法計算量較大，需要事先確定K值。SVM算法有很高的分準率和泛化性能，能很好地解決高維問題，對小樣本情況下的分類問題效果較好，缺點是對缺失數據敏感，對非線性問題沒有通用解決方案，得謹慎選擇核函數來處理。本文的實驗部分選用了三組數據集來驗證三種算法的分類準確率，實驗結果表明,三種算法都能很好地解決分類問題，但都有一定的局限性，在具體應用中需要根據算法在特定數據集上的優勢和劣勢選擇相應的算法去解決。