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