?
摘要?????? 本文介紹了在數(shù)據(jù)挖掘中數(shù)據(jù)分類的幾個主要分類方法，包括：貝葉斯分類、決策樹分類、感知器分類，及其各自的優(yōu)勢與劣勢。并對于分類問題中出現(xiàn)的高維效應(yīng)，介紹了兩種通用的解決辦法。
關(guān)鍵詞?? 數(shù)據(jù)分類? 貝葉斯分類? 決策樹分類? 感知器分類
?
?
引言
數(shù)據(jù)分類是指按照分析對象的屬性、特征，建立不同的組類來描述事物。數(shù)據(jù)分類是數(shù)據(jù)挖掘的主要內(nèi)容之一，主要是通過分析訓(xùn)練數(shù)據(jù)樣本，產(chǎn)生關(guān)于類別的精確描述。這種類別通常由分類規(guī)則組成，可以用來對未來的數(shù)據(jù)進(jìn)行分類和預(yù)測。分類技術(shù)解決問題的關(guān)鍵是構(gòu)造分類器。
一．?dāng)?shù)據(jù)分類
數(shù)據(jù)分類一般是兩個步驟的過程：
第1步：建立一個模型，描述給定的數(shù)據(jù)類集或概念集（簡稱訓(xùn)練集）。通過分析由屬性描述的數(shù)據(jù)庫元組來構(gòu)造模型。每個元組屬于一個預(yù)定義的類，由類標(biāo)號屬性確定。用于建立模型的元組集稱為訓(xùn)練數(shù)據(jù)集，其中每個元組稱為訓(xùn)練樣本。由于給出了類標(biāo)號屬性，因此該步驟又稱為有指導(dǎo)的學(xué)習(xí)。如果訓(xùn)練樣本的類標(biāo)號是未知的，則稱為無指導(dǎo)的學(xué)習(xí)（聚類）。學(xué)習(xí)模型可用分類規(guī)則、決策樹和數(shù)學(xué)公式的形式給出。
第2步：使用模型對數(shù)據(jù)進(jìn)行分類。包括評估模型的分類準(zhǔn)確性以及對類標(biāo)號未知的元組按模型進(jìn)行分類。
常用的分類規(guī)則挖掘方法
分類規(guī)則挖掘有著廣泛的應(yīng)用前景。對于分類規(guī)則的挖掘通常有以下幾種方法，不同的方法適用于不同特點(diǎn)的數(shù)據(jù)：
1．貝葉斯方法
2．決策樹方法
3．人工神經(jīng)網(wǎng)絡(luò)方法
4．約略集方法
5．遺傳算法
分類方法的評估標(biāo)準(zhǔn)：
準(zhǔn)確率：模型正確預(yù)測新數(shù)據(jù)類標(biāo)號的能力。
速度：產(chǎn)生和使用模型花費(fèi)的時間。
健壯性：有噪聲數(shù)據(jù)或空缺值數(shù)據(jù)時模型正確分類或預(yù)測的能力。
伸縮性：對于給定的大量數(shù)據(jù)，有效地構(gòu)造模型的能力。
可解釋性：學(xué)習(xí)模型提供的理解和觀察的層次。
影響一個分類器錯誤率的因素
(1) 訓(xùn)練集的記錄數(shù)量。生成器要利用訓(xùn)練集進(jìn)行學(xué)習(xí)，因而訓(xùn)練集越大，分類器也就越可靠。然而，訓(xùn)練集越大，生成器構(gòu)造分類器的時間也就越長。錯誤率改善情況隨訓(xùn)練集規(guī)模的增大而降低。
(2) 屬性的數(shù)目。更多的屬性數(shù)目對于生成器而言意味著要計算更多的組合，使得生成器難度增大，需要的時間也更長。有時隨機(jī)的關(guān)系會將生成器引入歧途，結(jié)果可能構(gòu)造出不夠準(zhǔn)確的分類器（這在技術(shù)上被稱為過分?jǐn)M合）。因此，如果我們通過常識可以確認(rèn)某個屬性與目標(biāo)無關(guān)，則將它從訓(xùn)練集中移走。
(3) 屬性中的信息。有時生成器不能從屬性中獲取足夠的信息來正確、低錯誤率地預(yù)測標(biāo)簽（如試圖根據(jù)某人眼睛的顏色來決定他的收入）。加入其他的屬性（如職業(yè)、每周工作小時數(shù)和年齡），可以降低錯誤率。
(4) 待預(yù)測記錄的分布。如果待預(yù)測記錄來自不同于訓(xùn)練集中記錄的分布，那么錯誤率有可能很高。比如如果你從包含家用轎車數(shù)據(jù)的訓(xùn)練集中構(gòu)造出分類器，那么試圖用它來對包含許多運(yùn)動用車輛的記錄進(jìn)行分類可能沒多大用途，因為數(shù)據(jù)屬性值的分布可能是有很大差別的。
評估方法
有兩種方法可以用于對分類器的錯誤率進(jìn)行評估，它們都假定待預(yù)測記錄和訓(xùn)練集取自同樣的樣本分布。
(1) 保留方法(Holdout)：記錄集中的一部分（通常是2/3）作為訓(xùn)練集，保留剩余的部分用作測試集。生成器使用2/3 的數(shù)據(jù)來構(gòu)造分類器，然后使用這個分類器來對測試集進(jìn)行分類，得出的錯誤率就是評估錯誤率。
雖然這種方法速度快，但由于僅使用2/3 的數(shù)據(jù)來構(gòu)造分類器，因此它沒有充分利用所有的數(shù)據(jù)來進(jìn)行學(xué)習(xí)。如果使用所有的數(shù)據(jù)，那么可能構(gòu)造出更精確的分類器。
(2) 交叉糾錯方法(Cross validation)：數(shù)據(jù)集被分成k 個沒有交叉數(shù)據(jù)的子集，所有子集的大小大致相同。生成器訓(xùn)練和測試共k 次；每一次，生成器使用去除一個子集的剩余數(shù)據(jù)作為訓(xùn)練集，然后在被去除的子集上進(jìn)行測試。把所有得到的錯誤率的平均值作為評估錯誤率。
交叉糾錯法可以被重復(fù)多次(t)，對于一個t 次k 分的交叉糾錯法，k ＊t 個分類器被構(gòu)造并被評估，這意味著交叉糾錯法的時間是分類器構(gòu)造時間的k ＊t 倍。增加重復(fù)的次數(shù)意味著運(yùn)行時間的增長和錯誤率評估的改善。我們可以對k 的值進(jìn)行調(diào)整，將它減少到3 或5，這樣可以縮短運(yùn)行時間。然而，減小訓(xùn)練集有可能使評估產(chǎn)生更大的偏差。
通常Holdout 評估方法被用在最初試驗性的場合，或者多于5000 條記錄的數(shù)據(jù)集；交叉糾錯法被用于建立最終的分類器，或者很小的數(shù)據(jù)集。
?
二．貝葉斯分類
貝葉斯分類方法是一種具有最小錯誤率的概率分類方法，可以用數(shù)學(xué)公式的精確方法表示出來，并且可以用很多種概率理論來解決。
設(shè)（Ω,Θ,P）為概率空間，Ai∈Θ（i=1,2,…,n）為Ω的一個有窮剖分，且P(Ai)>0 (i=1,2,…,n)，則對任意B∈Θ且P(B)>0，有
?
?
P(Ai|B)=???
?
分類有規(guī)則分類和非規(guī)則分類，貝葉斯分類是非規(guī)則分類，它通過訓(xùn)練集訓(xùn)練而歸納出分類器，并利用分類器對沒有分類的數(shù)據(jù)進(jìn)行分類。
貝葉斯分類的特點(diǎn)
貝葉斯分類具有如下特點(diǎn)：
(1)
貝葉斯分類并不把一個對象絕對地指派給某一類，而是通過計算得出屬于某一類的概率，具有最大概率的類便是該對象所屬的類；
(2)
一般情況下在貝葉斯分類中所有的屬性都潛在地起作用，即并不是一個或幾個屬性決定分類，而是所有的屬性都參與分類；
(3)
貝葉斯分類對象的屬性可以是離散的、連續(xù)的，也可以是混合的。
貝葉斯定理給出了最小化誤差的最優(yōu)解決方法，可用于分類和預(yù)測。理論上，它看起來很完美，但在實際中，它并不能直接利用，它需要知道證據(jù)的確切分布概率，而實際上我們并不能確切的給出證據(jù)的分布概率。因此我們在很多分類方法中都會作出某種假設(shè)以逼近貝葉斯定理的要求。
?
三．決策樹分類
決策樹（
Decision Tree
）又稱為判定樹，是運(yùn)用于分類的一種樹結(jié)構(gòu)。其中的每個內(nèi)部結(jié)點(diǎn)（
internal node
）代表對某個屬性的一次測試，每條邊代表一個測試結(jié)果，葉結(jié)點(diǎn)（
leaf
）代表某個類（
class
）或者類的分布（
class distribution
），最上面的結(jié)點(diǎn)是根結(jié)點(diǎn)。決策樹分為分類樹和回歸樹兩種，分類樹對離散變量做決策樹，回歸樹對連續(xù)變量做決策樹。
構(gòu)造決策樹是采用自上而下的遞歸構(gòu)造方法。決策樹構(gòu)造的結(jié)果是一棵二叉或多叉樹，它的輸入是一組帶有類別標(biāo)記的訓(xùn)練數(shù)據(jù)。二叉樹的內(nèi)部結(jié)點(diǎn)（非葉結(jié)點(diǎn)）一般表示為一個邏輯判斷，如形式為
(a = b)
的邏輯判斷，其中
a
是屬性，
b
是該屬性的某個屬性值；樹的邊是邏輯判斷的分支結(jié)果。多叉樹（
ID3
）的內(nèi)部結(jié)點(diǎn)是屬性，邊是該屬性的所有取值，有幾個屬性值，就有幾條邊。樹的葉結(jié)點(diǎn)都是類別標(biāo)記。
使用決策樹進(jìn)行分類分為兩步：
第
1
步：利用訓(xùn)練集建立并精化一棵決策樹，建立決策樹模型。這個過程實際上是一個從數(shù)據(jù)中獲取知識，進(jìn)行機(jī)器學(xué)習(xí)的過程。
第
2
步：利用生成完畢的決策樹對輸入數(shù)據(jù)進(jìn)行分類。對輸入的記錄，從根結(jié)點(diǎn)依次測試記錄的屬性值，直到到達(dá)某個葉結(jié)點(diǎn)，從而找到該記錄所在的類。
問題的關(guān)鍵是建立一棵決策樹。這個過程通常分為兩個階段：
(1)
建樹（
Tree Building
）：決策樹建樹算法見下，可以看得出，這是一個遞歸的過程，最終將得到一棵樹。
(2)
剪枝（
Tree Pruning
）：剪枝是目的是降低由于訓(xùn)練集存在噪聲而產(chǎn)生的起伏。
決策樹方法的評價。
優(yōu)點(diǎn)
與其他分類算法相比決策樹有如下優(yōu)點(diǎn)：
(1)
速度快：計算量相對較小，且容易轉(zhuǎn)化成分類規(guī)則。只要沿著樹根向下一直走到葉，沿途的分裂條件就能夠唯一確定一條分類的謂詞。
(2)
準(zhǔn)確性高：挖掘出的分類規(guī)則準(zhǔn)確性高，便于理解，決策樹可以清晰的顯示哪些字段比較重要。
缺點(diǎn)
一般決策樹的劣勢：
(1)
缺乏伸縮性：由于進(jìn)行深度優(yōu)先搜索，所以算法受內(nèi)存大小限制，難于處理大訓(xùn)練集。一個例子：在
Irvine
機(jī)器學(xué)習(xí)知識庫中，最大可以允許的數(shù)據(jù)集僅僅為
700KB
，
2000
條記錄。而現(xiàn)代的數(shù)據(jù)倉庫動輒存儲幾個
G-Bytes
的海量數(shù)據(jù)。用以前的方法是顯然不行的。
(2)
為了處理大數(shù)據(jù)集或連續(xù)量的種種改進(jìn)算法（離散化、取樣）不僅增加了分類算法的額外開銷，而且降低了分類的準(zhǔn)確性，對連續(xù)性的字段比較難預(yù)測，當(dāng)類別太多時，錯誤可能就會增加的比較快，對有時間順序的數(shù)據(jù)，需要很多預(yù)處理的工作。
但是，所用的基于分類挖掘的決策樹算法沒有考慮噪聲問題，生成的決策樹很完美，這只不過是理論上的，在實際應(yīng)用過程中，大量的現(xiàn)實世界中的數(shù)據(jù)都不是以的意愿來定的，可能某些字段上缺值（
missing values
）；可能數(shù)據(jù)不準(zhǔn)確含有噪聲或者是錯誤的；可能是缺少必須的數(shù)據(jù)造成了數(shù)據(jù)的不完整。
另外決策樹技術(shù)本身也存在一些不足的地方，例如當(dāng)類別很多的時候，它的錯誤就可能出現(xiàn)甚至很多。而且它對連續(xù)性的字段比較難作出準(zhǔn)確的預(yù)測。而且一般算法在分類的時候，只是根據(jù)一個屬性來分類的。
在有噪聲的情況下，完全擬合將導(dǎo)致過分?jǐn)M合（
overfitting
），即對訓(xùn)練數(shù)據(jù)的完全擬合反而不具有很好的預(yù)測性能。剪枝是一種克服噪聲的技術(shù)，同時它也能使樹得到簡化而變得更容易理解。另外，決策樹技術(shù)也可能產(chǎn)生子樹復(fù)制和碎片問題。
?
四．感知器分類
感知器是由具有可調(diào)節(jié)的鍵結(jié)值以及閾值的單一個類神經(jīng)元所組成，它是各種類神經(jīng)網(wǎng)絡(luò)中，最簡單且最早發(fā)展出來的類神經(jīng)網(wǎng)絡(luò)模型，通常被用來作為分類器使用。感知器的基本組成元件為一個具有線性組合功能的累加器，后接一個硬限制器而成，如圖
4.1
所示。