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

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

策樹，對檢驗記錄進行分類就是直截了當(dāng)?shù)?，從樹的根結(jié)點出發(fā)，將測試條件用于檢驗記錄，根據(jù)測試結(jié)果選擇適當(dāng)?shù)姆种В刂摲种Щ蛘?

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

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

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

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

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

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

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