數據挖掘---分類:基本概念、決策樹、與模型評估

分類：基本概念、決策樹與模型評估 分類任務就是確定對象屬于那個預定義的目標類。就是通過學習得到一個目標函數f,把每個屬性集映射到一個預先定義的類標號y. 一、預備知識 分類任務的輸入數據是記錄的集合，每條記錄稱為實例，用元組（x,y)表示，其中x是屬性的集合，y是一個特殊的集合。  描述性建模：分類模型可以作為解釋性工具,用于區分不同類中的對象. 預測性建模:分類模型還可以用于預測未知記錄的類標號. 二.解決分類問題的一般方法 分類法的例子包括決策樹法、基于規則的分類法、神經網絡、支持向量機和樸素貝葉斯分類法。 分類模型的性能根據模型正確和錯誤預測的檢驗記錄計數進行評估，這些計數存放在稱作混淆矩陣的表格中。準確性=正確預測數/預測總數。 差錯率：錯誤預測數/預測總數。 三。決策樹歸納 1。決策樹工作原理 樹中包換三種結點： 根結點：它沒有入邊，但有零條或多條出邊。 內部結點：恰有一條入邊和兩條或多條出邊。 葉結點：恰有一條入邊，但沒有出邊。 其中，每個葉結點都賦予一個類標號，非終結點（包括根結點和內部結點）包含屬性測試條件，用以分開具有不同特性的記錄。一旦構造了決

策樹，對檢驗記錄進行分類就是直截了當的，從樹的根結點出發，將測試條件用于檢驗記錄，根據測試結果選擇適當的分支，沿著該分支或者

達到另一個內部結點，使用新的測試條件或者達到一個葉結點，葉結點的類稱號就被賦值給該檢驗記錄。 2。如何建立決策樹 對于給定的屬性集，可以構造的決策樹數目達指數級，找出最佳的決策樹在計算上是不可行的，所以通常采用貪心算法，采取一系列局部最優

決策來構造決策樹。Hunt算法就是其中一種。 *Hunt算法 Hunt算法通過將訓練記錄相繼劃分成較純的子集，以遞歸方式建立決策樹。 決策樹歸納設計問題必須解決以下兩個問題：如何分裂訓練記錄和如何停止分裂過程。 3。表示屬性測試條件的方法 二元屬性：二元屬性的測試條件產生兩個可能的輸出。 標稱屬性：由于標稱有多個屬性值，它的測試條件可以用兩種方法表示，多路劃分和二元劃分（如：CART方法） 充數屬性：也可以產生二元或多路劃分。 連續屬性：測試條件可以具有二元輸出的比較測試（A<v)或(A>=v)，也可以是具有形如：vi<=A<vi+1來劃分輸出的范圍查詢。 4。選擇最佳劃分的度量 為了確定測試條件的效果，需要比較父結點（劃分前）的不純程度和子女結點（劃分后）的不純程度，它們的差越大，測試條件的效果就越好

。 5。決策樹歸納的特點： *決策樹歸納是一種構建分類模型的非參數方法。 *找到最佳的決策樹是NP完全問題。 *已開發的構建決策樹技術不需要昂貴的計算代價。 *決策樹相對容易解釋，特別是小型的決策樹。 *決策樹是學習離散值函數的典型代表。 *決策樹對于噪聲有良好的魯棒性。 *冗余屬性不會對決策的準確率造成不利的影響。 *存在著數據碎片的問題。 *子樹可能在決策樹中重復多次。 四。模型的過分擬合 分類模型的誤差大致分為兩種：訓練誤差和泛化誤差。一個好的分類模型不僅要能夠很好地擬合訓練數據，而且對未知樣本也要能準確地分類

。然而，對訓練集數據擬合太好的模型，其泛化誤差可能比具有較高訓練誤差的模型高，這就是所謂的模型過分擬合。 1。噪聲導致的過分擬合 也就是訓練集中有被錯誤分類的記錄。 2。缺乏代表性樣本導致的過分擬合 3。過分擬合與多重比較過程 要增加一個屬性測試條件，是從候選的屬性集中挑一個使得增益大于某個閾值的一個屬性，這樣算法就會在模型上增加一些欺騙性的結點，導

致過分擬合。 4。泛化誤差估計 *使用再代入估計：假設訓練數據集可以很好的代表整體數據，因而可以使用訓練誤差提供對泛化誤差的樂觀估計。 *結合模型復雜度：如前所述，模型越是復雜，出現過分擬合的幾率就越高，因此我們更喜歡較為簡單的模型。這種策略與Occam剃刀或節儉原

則一致，Occam剃刀：給定兩個具有相同泛化誤差的模型，較簡單的模型比較復雜的模型更可取。 五。評估分類器的性能 1。保持方法：將被標記的原始數據劃分成兩個不相交的集合，分別稱為訓練集和檢驗集，在訓練集上歸納分類模型，在檢驗集上評估模型的性

能。 2。隨機二次抽樣：可以多次重復保持方法來改進對分類器性能的估計。 3。交叉驗證：每個記錄用于訓練的次數相同，并且用于檢驗恰好一次。