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

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

策樹，對(duì)檢驗(yàn)記錄進(jìn)行分類就是直截了當(dāng)?shù)?，從樹的根結(jié)點(diǎn)出發(fā)，將測(cè)試條件用于檢驗(yàn)記錄，根據(jù)測(cè)試結(jié)果選擇適當(dāng)?shù)姆种?，沿著該分支或?

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

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

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

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

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

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

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