《數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)(第2版)》第10章模型選擇與模型評(píng)估

第10章模型選擇與模型評(píng)估

《數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)》(第2版)數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)(第2版)(43-2)模型選擇與模型評(píng)估

生成若干數(shù)據(jù)模型后，需要依據(jù)模型對(duì)數(shù)據(jù)的解釋能力或預(yù)測(cè)能力，確定一個(gè)最優(yōu)的模型。本章介紹模型選擇和模型評(píng)估方法。主要討論啟發(fā)式方法，數(shù)據(jù)重用技術(shù)，以及模型選擇和驗(yàn)證的解析方法，具體包括：模型的過(guò)擬合沒(méi)有天生優(yōu)越的分類(lèi)器模型、模型選擇和模型評(píng)估自助法Occam剃刀最小描述長(zhǎng)度準(zhǔn)則信息準(zhǔn)則比較分類(lèi)器的方法聚類(lèi)評(píng)估數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)(第2版)(43-3)模型的過(guò)擬合分類(lèi)模型的誤差有兩類(lèi)：訓(xùn)練誤差（trainingerror）：也稱為再代入誤差（resubstitutionerror），是訓(xùn)練樣本上的誤分類(lèi)比例。泛化誤差（generalizationerror）：是模型在未知樣本上的期望誤差。一個(gè)好的分類(lèi)模型應(yīng)該同時(shí)具有低訓(xùn)練誤差和低泛化誤差。如果分類(lèi)模型A擬合訓(xùn)練數(shù)據(jù)較好，但與另一個(gè)擬合訓(xùn)練數(shù)據(jù)相對(duì)較差的分類(lèi)模型B相比，模型A具有更高的泛化誤差，則稱模型A過(guò)擬合。例，以二維數(shù)據(jù)為例解釋過(guò)擬合。在圖10.1二維數(shù)據(jù)集合中，數(shù)據(jù)點(diǎn)屬于兩類(lèi)：標(biāo)記為“o”的數(shù)據(jù)由三個(gè)獨(dú)立的正態(tài)分布產(chǎn)生，1200個(gè)。標(biāo)記為“+”的數(shù)據(jù)由均勻分布產(chǎn)生。1800個(gè)。隨機(jī)選取30%用于訓(xùn)練決策樹(shù)，其余70%用于測(cè)試。為說(shuō)明過(guò)擬合現(xiàn)象，對(duì)完全生長(zhǎng)的決策樹(shù)進(jìn)行不同程度的剪枝。圖10.2顯示了不同節(jié)點(diǎn)數(shù)的決策樹(shù)的訓(xùn)練誤差和測(cè)試誤差。數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)(第2版)(43-4)模型的過(guò)擬合模型擬合不足(modelunderfitting):訓(xùn)練誤差和測(cè)試誤差都較大。決策樹(shù)生長(zhǎng)不充分模型過(guò)擬合(modeloverfitting):訓(xùn)練誤差繼續(xù)降低，測(cè)試誤差增大。決策樹(shù)的規(guī)模過(guò)于復(fù)雜數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)(第2版)(43-5)模型的過(guò)擬合

圖10.3給出了兩顆具有不同規(guī)模的決策樹(shù)，節(jié)點(diǎn)少的決策樹(shù)具有較高訓(xùn)練誤差，但具有較低的測(cè)試誤差，而節(jié)點(diǎn)多的決策樹(shù)出現(xiàn)過(guò)擬合。導(dǎo)致過(guò)擬合的因素：存在噪聲數(shù)據(jù)缺少典型樣本數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)(第2版)(43-6)沒(méi)有天生優(yōu)越的分類(lèi)器考慮兩類(lèi)問(wèn)題：設(shè)訓(xùn)練集D由模式xi以及與之相應(yīng)的類(lèi)別標(biāo)簽yi=，i=1，，n，yi由待學(xué)習(xí)的未知目標(biāo)函數(shù)F(x)給出，即yi

=F(xi)。多數(shù)情況下，F(xiàn)(x)都含有隨機(jī)成分，相同的輸入被分到不同的類(lèi)別中，導(dǎo)致非零貝葉斯錯(cuò)誤率。令H表示假設(shè)集或待學(xué)習(xí)的可能參數(shù)集合。

h(x)H是特定的假設(shè)，如，神經(jīng)網(wǎng)絡(luò)中的量化權(quán)值、泛函模型中的參數(shù)或者樹(shù)中的決策集合等等。設(shè)P(h)表示算法訓(xùn)練后產(chǎn)生假設(shè)h的先驗(yàn)概率。

P(hD)表示在數(shù)據(jù)集D上訓(xùn)練后產(chǎn)生假設(shè)h的概率。對(duì)于確定性學(xué)習(xí)算法，P(hD)在單一假設(shè)h外，處處為零。最近鄰和決策樹(shù)對(duì)于隨機(jī)算法，P(hD)可能是一個(gè)分布。神經(jīng)網(wǎng)絡(luò)令E表示0-1損失函數(shù)或其他損失函數(shù)的誤差。數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)(第2版)(43-7)沒(méi)有天生優(yōu)越的分類(lèi)器評(píng)判學(xué)習(xí)算法的泛化性能：關(guān)于所有可能目標(biāo)求和的誤差期望值。顯然，固定訓(xùn)練集D上期望誤差率，與以輸入的概率P(x)為權(quán)、學(xué)習(xí)算法P(hD)與真實(shí)后驗(yàn)P(FD)“匹配”的情況的加權(quán)和有關(guān)。如果沒(méi)有關(guān)于P(FD)的先驗(yàn)知識(shí)，不能檢驗(yàn)任何特定的學(xué)習(xí)算法P(hD)，包括其泛化性能。當(dāng)真實(shí)函數(shù)是F(x)，第k個(gè)候選學(xué)習(xí)算法的概率是Pk(h(x)D)時(shí)，非訓(xùn)練集的期望誤差率是：數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)(第2版)(43-8)沒(méi)有天生優(yōu)越的分類(lèi)器定理10.1：（沒(méi)有免費(fèi)的午餐，Nofreelunch，NFL）任給兩個(gè)學(xué)習(xí)算法P1(hD)和P2(hD)，下列命題正確，且與樣本分布P(x)及訓(xùn)練點(diǎn)個(gè)數(shù)n無(wú)關(guān)：(1)對(duì)所有目標(biāo)函數(shù)F求平均，有1[EF,n]-2[EF,n]=0；(2)任意固定的訓(xùn)練集D，對(duì)所有F求平均，有1[EF,D]-2[EF,D]=0；(3)對(duì)所有先驗(yàn)P(F)求平均，有1[En]-2[En]=0；(4)任意固定的訓(xùn)練集D，對(duì)所有先驗(yàn)P(F)求平均，有1[ED]-2[ED]=0.NFL定理表明：使用哪種算法完成分類(lèi)任務(wù)，取決于問(wèn)題本質(zhì)特征，而不是數(shù)據(jù)挖掘者對(duì)哪個(gè)算法更熟悉。研究和試圖說(shuō)明某種算法具有天生的優(yōu)越性是沒(méi)有意義的。當(dāng)面對(duì)一個(gè)新的分類(lèi)問(wèn)題時(shí)：(1)應(yīng)該關(guān)注事務(wù)的本質(zhì)先驗(yàn)信息、數(shù)據(jù)分布、訓(xùn)練樣本數(shù)量、代價(jià)或獎(jiǎng)勵(lì)函數(shù)等。(2)根據(jù)以上關(guān)于問(wèn)題的“信息”，選擇適當(dāng)?shù)姆诸?lèi)算法。數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)(第2版)(43-9)沒(méi)有天生優(yōu)越的分類(lèi)器例10.1：二值數(shù)據(jù)的NFL

假設(shè)輸入矢量由三個(gè)二值特征構(gòu)成，給定目標(biāo)函數(shù)F(x)，如表10.1。假設(shè)學(xué)習(xí)算法1認(rèn)為每個(gè)模式除非被訓(xùn)練過(guò)，否則就屬于類(lèi)1；學(xué)習(xí)算法2認(rèn)為每個(gè)模式除非被訓(xùn)練過(guò)，否則就屬于類(lèi)2。當(dāng)訓(xùn)練數(shù)據(jù)集D含有三個(gè)樣本時(shí)，兩個(gè)算法分別給出假設(shè)h1和h2。計(jì)算非訓(xùn)練誤差率為1[EF,D]=0.4和2[EF,D]=0.6.數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)(第2版)(43-10)沒(méi)有天生優(yōu)越的分類(lèi)器假定沒(méi)有關(guān)于F(x)的先驗(yàn)信息。所有目標(biāo)函數(shù)平等。要全面地比較算法，必須對(duì)所有與訓(xùn)練數(shù)據(jù)一致的目標(biāo)函數(shù)求平均。與訓(xùn)練數(shù)據(jù)集D中三個(gè)模式一致的不同目標(biāo)函數(shù)一共有25個(gè)，確實(shí)存在另一個(gè)目標(biāo)函數(shù)G，其關(guān)于非訓(xùn)練數(shù)據(jù)的輸出是表中F(x)的取反，也即G(x)=(1,-1,1,1,-1,1,-1,-1)′,而1[EG,D]=0.6和2[EG,D]=0.4，也即F和G使得算法1和算法2的性能相反，從而對(duì)定理10.1的(2)中公式的貢獻(xiàn)相抵消。任何一個(gè)二值分類(lèi)學(xué)習(xí)算法如果不在某些問(wèn)題上付出相等的負(fù)的性能代價(jià)，則不可能在所關(guān)心的問(wèn)題上得到等量的正的性能。如果沒(méi)有限定一定要使用某種特定的算法解決問(wèn)題，那么，我們所能做的就是在期望遇到的問(wèn)題和不期望遇到的問(wèn)題之間做一些性能折中。學(xué)習(xí)算法必須做一些與問(wèn)題相關(guān)的“假設(shè)”，也就是偏置（bias）。即使是非常流行而且理論堅(jiān)實(shí)的算法，也會(huì)在學(xué)習(xí)算法與問(wèn)題后驗(yàn)不“匹配”的情況下表現(xiàn)不佳。僅僅熟悉有限的幾種分類(lèi)算法，并不能解決所有分類(lèi)問(wèn)題。數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)(第2版)(43-11)模型、模型選擇和模型評(píng)估模型可以定義為對(duì)輸入輸出之間聯(lián)系的一種描述。這種描述可以用不同方式形式化。例如分類(lèi)器、神經(jīng)網(wǎng)絡(luò)、決策樹(shù)、產(chǎn)生式規(guī)則、數(shù)學(xué)方程等。模型、分類(lèi)器和估計(jì)子基本上含義相同。分類(lèi)器是用于分類(lèi)目的的數(shù)據(jù)模型：給定新的輸入，分類(lèi)器依據(jù)訓(xùn)練結(jié)果將其劃分到某一個(gè)類(lèi)中。估計(jì)子來(lái)自于統(tǒng)計(jì)學(xué)，定義為樣本值的函數(shù)，是計(jì)算參數(shù)的一種方法。估計(jì)模型時(shí)所必需的獨(dú)立的信息項(xiàng)的數(shù)目稱為模型的自由度。選擇簡(jiǎn)潔模型，在若干表現(xiàn)良好的模型中，選擇參數(shù)數(shù)目少的模型。模型誤差指真實(shí)值和模型輸出值之間的絕對(duì)誤差或平方誤差。當(dāng)由數(shù)據(jù)生成一個(gè)模型時(shí)，稱之為模型擬合數(shù)據(jù)。不僅需要檢驗(yàn)?zāi)Ｐ偷臄M合優(yōu)度（擬合誤差），而且需要檢驗(yàn)?zāi)Ｐ偷念A(yù)測(cè)優(yōu)度（預(yù)測(cè)誤差）。在生成的若干模型中擇優(yōu)的過(guò)程稱為模型選擇(modelselection)。數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)(第2版)(43-12)模型、模型選擇和模型評(píng)估構(gòu)建數(shù)據(jù)模型的方法有三類(lèi)：無(wú)監(jiān)督學(xué)習(xí)監(jiān)督學(xué)習(xí)半監(jiān)督學(xué)習(xí)模型評(píng)估方法：(1)根據(jù)可用數(shù)據(jù)的種類(lèi)以及能否計(jì)算誤差，對(duì)模型評(píng)估技術(shù)進(jìn)行分類(lèi)。根據(jù)方法內(nèi)在本質(zhì)劃分模型評(píng)估技術(shù)：數(shù)據(jù)重用技術(shù)，或稱為重采樣技術(shù)。廣泛應(yīng)用于評(píng)估監(jiān)督學(xué)習(xí)模型。簡(jiǎn)單劃分交叉驗(yàn)證自助法啟發(fā)式方法方法：不是形式化的，是最簡(jiǎn)單、常使用的方法。簡(jiǎn)潔模型奧坎姆剃刀解析方法：是形式化的，但不夠?qū)嵱?。最小描述長(zhǎng)度Aikake信息準(zhǔn)則貝葉斯信息準(zhǔn)則興趣度度量方法：模擬數(shù)據(jù)用戶所使用的模型評(píng)估過(guò)程，這類(lèi)方法較新且較流行。(2)按照模型選擇的方法。評(píng)估擬合優(yōu)度的方法評(píng)估預(yù)測(cè)優(yōu)度的方法。

數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)(第2版)(43-13)模型、模型選擇和模型評(píng)估偏倚與方差偏倚度量模型與問(wèn)題“匹配”的準(zhǔn)確度，高偏倚意味著更差的匹配；方差度量“匹配”的精確度，高方差意味著更弱匹配。對(duì)于給定的均方誤差，偏倚和方差之間存在“守恒律”的形式。假如有先驗(yàn)信息，可以創(chuàng)建出具有不同均方誤差的分類(lèi)器。評(píng)估模型的擬合優(yōu)度和預(yù)測(cè)優(yōu)度，必須首先計(jì)算誤差。誤差分為兩部分：偏倚和方差。(1)偏倚(Bias)是通過(guò)增加樣本容量也無(wú)法降低的誤差。偏倚也稱系統(tǒng)誤差，包括：測(cè)量誤差：無(wú)法消除的試驗(yàn)誤差樣本誤差：樣本可能沒(méi)有正確地產(chǎn)生于分布，從而沒(méi)有正確地描述數(shù)據(jù)。通過(guò)計(jì)算某些參數(shù)的估計(jì)值的數(shù)學(xué)期望和真實(shí)值之差得出偏倚：數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)(第2版)(43-14)模型、模型選擇和模型評(píng)估均方誤差（meansquareerror，MSE）其中方差為總體方差的無(wú)偏估計(jì)或總體方差的有偏估計(jì)(2)方差：由給定有限樣本導(dǎo)致的附加誤差。有偏估計(jì)量具有非零偏倚無(wú)偏估計(jì)具有零偏倚。最小化MSE可以得到具有恰當(dāng)偏倚和方差的模型。圖10.5中y軸表示偏倚/方差/MSE的值，x軸表示估計(jì)子/模型的復(fù)雜度/數(shù)據(jù)規(guī)模。數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)(第2版)(43-15)模型、模型選擇和模型評(píng)估擬合優(yōu)度和預(yù)測(cè)優(yōu)度，也即訓(xùn)練誤差和測(cè)試誤差。過(guò)度訓(xùn)練通常意味著數(shù)據(jù)過(guò)擬合。當(dāng)將過(guò)度訓(xùn)練的神經(jīng)網(wǎng)絡(luò)應(yīng)用于測(cè)試數(shù)據(jù)時(shí)，其預(yù)測(cè)/泛化誤差通常較大。數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)(第2版)(43-16)簡(jiǎn)單劃分和交叉驗(yàn)證簡(jiǎn)單劃分：為評(píng)估模型，將可用數(shù)據(jù)簡(jiǎn)單地劃分為兩部分：訓(xùn)練數(shù)據(jù)和測(cè)試數(shù)據(jù)，訓(xùn)練數(shù)據(jù)用于擬合模型，測(cè)試數(shù)據(jù)用于評(píng)估模型的預(yù)測(cè)優(yōu)度。隨機(jī)地通過(guò)一個(gè)經(jīng)驗(yàn)公式，抽取約1/2或2/3數(shù)據(jù)用于訓(xùn)練。特點(diǎn)：高偏倚、低方差。交叉驗(yàn)證：令n表示訓(xùn)練數(shù)據(jù)集中數(shù)據(jù)點(diǎn)的數(shù)目，將全部數(shù)據(jù)分為k個(gè)等規(guī)模的子集，使用k-1個(gè)部分進(jìn)行訓(xùn)練，余下的那一部分用于測(cè)試，并計(jì)算預(yù)測(cè)誤差(預(yù)測(cè)優(yōu)度)。重復(fù)這一過(guò)程k次，得到k次結(jié)果的平均值。常用的是10折交叉驗(yàn)證，數(shù)據(jù)集被分為10個(gè)子集，最終預(yù)測(cè)誤差為10次預(yù)測(cè)誤差的平均值。特點(diǎn):低偏倚和高方差。簡(jiǎn)單劃分用于數(shù)據(jù)集規(guī)模較大的情況。交叉驗(yàn)證用于數(shù)據(jù)集較小且難于處理的情況。數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)(第2版)(43-17)自助法(Bootstrap)自助法：用于給出模型誤差的非參數(shù)估計(jì)。為計(jì)算估計(jì)子的置信區(qū)間，從總體中按等規(guī)模抽取B次采樣，每次采樣包含n個(gè)樣本。(1)由總體有放回地抽取容量為n的B個(gè)采樣，稱得到的每一個(gè)采樣為自助法采樣。(2)對(duì)每一個(gè)自助法采樣調(diào)整現(xiàn)有模型，評(píng)估各自助法采樣的擬合優(yōu)度(誤差)，通過(guò)平均B個(gè)自助法采樣上的相應(yīng)統(tǒng)計(jì)量的估計(jì)值，可以計(jì)算出偏倚和方差的自助法估計(jì)：為利用自助法計(jì)算預(yù)測(cè)優(yōu)度，將自助法抽樣作為訓(xùn)練集，原始數(shù)據(jù)集作為測(cè)試集。用模型擬合所有自助法抽樣，計(jì)算在原始數(shù)據(jù)上的預(yù)測(cè)誤差。數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)(第2版)(43-18)Occam剃刀在給定論域，觀測(cè)現(xiàn)象的最簡(jiǎn)單解釋?zhuān)Ｐ停┦亲羁赡苷_的。給定若干模型，應(yīng)該選擇更“緊湊”的模型。由更小數(shù)目規(guī)則構(gòu)成規(guī)則的平均長(zhǎng)度比其他模型中的規(guī)則平均長(zhǎng)度更短許多機(jī)器學(xué)習(xí)算法使用了Occam剃刀啟發(fā)式方法。問(wèn)題：已經(jīng)用其生成模型，但還要用其進(jìn)行模型選擇。在某些情況下，Occam剃刀可能是完全錯(cuò)誤的。無(wú)論是“避免過(guò)擬合”技術(shù)，還是最小描述長(zhǎng)度原理，都沒(méi)有固有的優(yōu)越性，這類(lèi)技術(shù)對(duì)分類(lèi)器的形式或參數(shù)施加一種“偏愛(ài)”或“偏置”（bias）。這些技術(shù)僅在其恰好與問(wèn)題“匹配”時(shí)才是有益的。決定因素是學(xué)習(xí)算法與問(wèn)題的“匹配”，而不是“避免過(guò)擬合”本身。數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)(第2版)(43-19)最小描述長(zhǎng)度準(zhǔn)則Rissanen給出最小描述長(zhǎng)度原理（MinimumDescriptionLengthPrinciple，MDL）。MDL：如果系統(tǒng)能夠用輸入和與之相應(yīng)的輸出數(shù)據(jù)定義，則最差情形(最長(zhǎng)）下，可以使用全部數(shù)據(jù)描述這一系統(tǒng)（數(shù)據(jù)的最長(zhǎng)/最小的壓縮模型)。MDL原理表明，理論（模型/假設(shè)）的復(fù)雜度可以通過(guò)理論本身的編碼位數(shù)與使用該理論表達(dá)數(shù)據(jù)的編碼位數(shù)之和度量。給定一組模型，選擇最小化和：

L(h,D)=L(M)+L(D|M)的模型。即，其中L(M)為描述模型的長(zhǎng)度（位數(shù)），L(D|M)為使用模型M編碼描述數(shù)據(jù)的長(zhǎng)度。用貝葉斯的觀點(diǎn)解釋最小描述長(zhǎng)度原理：最優(yōu)假設(shè)h*是使得后驗(yàn)概率最大的那個(gè)假設(shè)。數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)(第2版)(43-20)最小描述長(zhǎng)度準(zhǔn)則香農(nóng)最優(yōu)編碼理論：串x可以-log2P(x)為代價(jià)下界進(jìn)行傳輸或表示。關(guān)于過(guò)擬合問(wèn)題：具有較大L(M)值的復(fù)雜模型很容易構(gòu)建，該模型具有較小的L(D|M)值，過(guò)擬合數(shù)據(jù)。具有較小L(M)值的簡(jiǎn)單模型也很容易構(gòu)建，該模型具有較大的L(D|M)值，擬合數(shù)據(jù)不足。假定生成了兩個(gè)解釋/擬合數(shù)據(jù)一樣好的兩個(gè)不同模型，MDL原理提示應(yīng)選擇較簡(jiǎn)單的模型。相互聯(lián)系：MDL原理和貝葉斯方法之間的聯(lián)系。MDL原理可以看成Occam剃刀的形式化。數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)(第2版)(43-21)Akaike信息準(zhǔn)則Akaike信息準(zhǔn)則（AkaikeInformationCriterion，AIC）和Bayesian信息準(zhǔn)則（BayesianInformationCriterion，BIC）是兩種統(tǒng)計(jì)學(xué)度量，用于在使用不同參數(shù)個(gè)數(shù)的模型間進(jìn)行模型選擇，這些模型彼此相關(guān)。要估計(jì)預(yù)測(cè)誤差E，訓(xùn)練誤差TrE易于計(jì)算，但是，由于測(cè)試向量不一定與訓(xùn)練向量一致，TrE通常過(guò)于樂(lè)觀，作為修正，需要估計(jì)樂(lè)觀的誤差Eop，并計(jì)算樣本內(nèi)誤差（in-sampleerror）如下：

E=TrE+EopAIC定義如下：

(10.14)

其中l(wèi)ogL是極大對(duì)數(shù)似然，即

(10.15)

Pθ(Y)是包含真實(shí)密度的密度族，是θ的極大似然估計(jì)，d是模型參數(shù)個(gè)數(shù)。數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)(第2版)(43-22)Akaike信息準(zhǔn)則如果生成了一族可以調(diào)整參數(shù)α的模型，則AIC重寫(xiě)為

(10.16)方差var2定義為

(10.17)AIC(α)是測(cè)試誤差曲線的估計(jì)，選擇最小化該函數(shù)的模型為最佳模型。數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)(第2版)(43-23)Bayesian信息準(zhǔn)則BIC定義：

(10.18)對(duì)于方差為var2的高斯分布，BIC可以寫(xiě)為：

(10.19)選擇最小化BIC的模型為最優(yōu)模型。因?yàn)閷?duì)更復(fù)雜模型加重懲罰，所以BIC偏好于簡(jiǎn)單模型。當(dāng)樣本規(guī)模N趨于無(wú)窮時(shí)，BIC將選擇正確的那個(gè)模型，而AIC將選擇一個(gè)過(guò)于復(fù)雜的模型。對(duì)于有限樣本，BIC將傾向于選擇過(guò)于簡(jiǎn)單的模型。此時(shí)，使用AIC是明智的策略。數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)(第2版)(43-24)比較分類(lèi)器的方法考慮一對(duì)分類(lèi)模型MA和MB。假設(shè)MA在包含30個(gè)記錄的檢驗(yàn)集上的準(zhǔn)確率達(dá)到85%，而MB在包含5000個(gè)記錄的不同檢驗(yàn)集上達(dá)到75%的準(zhǔn)確率。根據(jù)這些信息，是否可以斷定MA比MB更好呢？(1)估計(jì)準(zhǔn)確率的置信區(qū)間為確定置信區(qū)間，需要建立支配準(zhǔn)確率度量的概率分布。通過(guò)將分類(lèi)任務(wù)用伯努利實(shí)驗(yàn)建模來(lái)推導(dǎo)置信區(qū)間。預(yù)測(cè)檢驗(yàn)記錄類(lèi)標(biāo)號(hào)的任務(wù)可看作是二項(xiàng)式實(shí)驗(yàn)。給定包含N個(gè)記錄的檢驗(yàn)集，令X是被模型正確預(yù)測(cè)的記錄數(shù)，p是模型真正準(zhǔn)確率。通過(guò)把預(yù)測(cè)任務(wù)用二項(xiàng)式實(shí)驗(yàn)建模，X服從均值為Np、方差為Np(1-p)的二項(xiàng)分布。可以證明經(jīng)驗(yàn)準(zhǔn)確率也是均值為p、方差為Np(1-p)的二項(xiàng)分布。盡管可以用二項(xiàng)分布來(lái)估計(jì)acc的置信區(qū)間，但是當(dāng)N充分大時(shí)，通常用正態(tài)分布來(lái)近似。根據(jù)推導(dǎo)出acc的置信區(qū)間為：數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)(第2版)(43-25)比較分類(lèi)器的方法其中Zα/2和Z1-α/2分別是在置信水平1-α下由標(biāo)準(zhǔn)正態(tài)分布得到的上界和下界。因?yàn)闃?biāo)準(zhǔn)正態(tài)分布關(guān)于Z=0對(duì)稱，于是有Zα/2=Z1-α/2。重新整理不等式，得到p的置信區(qū)間如下：下表給出了在不同置信水平下Zα/2的值：數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)(第2版)(43-26)比較分類(lèi)器的方法例：考慮一個(gè)模型，它在100個(gè)檢驗(yàn)記錄上具有80%的準(zhǔn)確率。在95%的置信水平下，模型的真實(shí)準(zhǔn)確率的置信區(qū)間是什么？根據(jù)上面的表格，95%的置信水平對(duì)應(yīng)于Zα/2=1.96。將其帶入公式得到置信區(qū)間為（71.1%，86.7%）。下表給出了隨著記錄數(shù)N的增大所產(chǎn)生的置信區(qū)間。注意，隨著N的增大，置信區(qū)間變得更加緊湊。數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)(第2版)(43-27)比較分類(lèi)器的方法(2)比較兩個(gè)模型的性能考慮模型M1和M2，在兩個(gè)獨(dú)立的檢驗(yàn)集D1和D2上進(jìn)行評(píng)估，令n1、n2分別表示D1和D2中的記錄數(shù)。另外，假設(shè)M1在D1上的錯(cuò)誤率為e1，M2在D2上錯(cuò)誤率為e2。目標(biāo)是檢驗(yàn)e1與e2

的觀察差是否是統(tǒng)計(jì)顯著的。假設(shè)n1和n2都充分大，e1和e2可以使用正態(tài)分布來(lái)近似。如果用d=e1-e2表示錯(cuò)誤率的觀測(cè)差，則d服從均值為dt、方差為的正態(tài)分布。d的方差為：其中和是錯(cuò)誤率的方差。最后，在置信水平1-α下，可以證明實(shí)際差dt的置信區(qū)間由下式給出：數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)(第2版)(43-28)比較分類(lèi)器的方法例：模型MA在N1=30個(gè)檢驗(yàn)記錄上的錯(cuò)誤率e1=0.15，而MB在N2=5000個(gè)檢驗(yàn)記錄上的錯(cuò)誤率e1=0.25。錯(cuò)誤率的觀察差d=|0.15-0.25|=0.1。在此例中，使用雙側(cè)檢驗(yàn)來(lái)檢查dt=0還是dt≠0。錯(cuò)誤率觀察差的估計(jì)方差計(jì)算如下：或。把該值代入，得到在95%的置信水平下，dt的置信區(qū)間如下：

由于該區(qū)間包含0，可以斷言在95%的置信水平下，該觀察差不是統(tǒng)計(jì)顯著的。數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)(第2版)(43-29)比較兩種分類(lèi)法的性能假設(shè)用k折交叉驗(yàn)證比較兩類(lèi)分類(lèi)算法的性能。把數(shù)據(jù)集D劃分為k個(gè)大小相等的部分。使用每類(lèi)分類(lèi)算法，在k-1份數(shù)據(jù)上構(gòu)建模型，并在剩余的劃分塊上進(jìn)行檢驗(yàn)，重復(fù)這個(gè)步驟k次，每次使用不同的劃分進(jìn)行檢驗(yàn)。令Mij表示分類(lèi)技術(shù)Li在第j次迭代產(chǎn)生的模型，每對(duì)模型M1j和M2j在相同的劃分j上進(jìn)行檢驗(yàn)。分別用e1j和e2j表示錯(cuò)誤率，在第j折上的錯(cuò)誤率之差可以記作dj=e1j-e2j。如果k充分大，則dj服從于均值為(錯(cuò)誤率的真實(shí)差)、方差為的正態(tài)分布。觀察差的總方差用下式估計(jì)：其中，是平均差。用t分布計(jì)算的置信區(qū)間：系數(shù)t(1-α),k-1可以通過(guò)兩個(gè)參數(shù)（置信水平1-α和自由度k-1）查概率表得到。數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)(第2版)(43-30)比較兩種分類(lèi)法的性能例：假設(shè)兩個(gè)分類(lèi)算法產(chǎn)生的模型的準(zhǔn)確率估計(jì)差的均值等于0.05，標(biāo)準(zhǔn)差等于0.002。如果使用30折交叉驗(yàn)證估計(jì)準(zhǔn)確率，則在95%置信水平下，真實(shí)準(zhǔn)確率差為：

因?yàn)橹眯艆^(qū)間不包括0，兩個(gè)分類(lèi)算法的觀察差是統(tǒng)計(jì)顯著的。數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)(第2版)(43-31)聚類(lèi)評(píng)估由于數(shù)據(jù)集特征和輸入?yún)?shù)值不同，不同聚類(lèi)算法的表現(xiàn)也不同。若聚類(lèi)算法參數(shù)設(shè)置得不合適，可能會(huì)得出對(duì)原始數(shù)據(jù)集擬合得不好的劃分模式，從而導(dǎo)致錯(cuò)誤的決策。圖10.7(a)由3個(gè)簇組成的數(shù)據(jù)集(b)給定簇個(gè)數(shù)為4時(shí)K-均值算法的結(jié)果聚類(lèi)評(píng)估：令C為X上應(yīng)用聚類(lèi)算法所導(dǎo)致的聚類(lèi)結(jié)構(gòu)。外部準(zhǔn)則：按照獨(dú)立抽取結(jié)構(gòu)來(lái)評(píng)價(jià)C，它在X上引入一個(gè)預(yù)測(cè)，來(lái)影響對(duì)X的聚類(lèi)結(jié)構(gòu)的認(rèn)識(shí)?？梢杂脕?lái)測(cè)量可用數(shù)據(jù)符合指定結(jié)構(gòu)的程度。內(nèi)部準(zhǔn)則：按包含X向量本身的數(shù)據(jù)來(lái)評(píng)價(jià)C，例如相似矩陣。相對(duì)準(zhǔn)則：通過(guò)與其它聚類(lèi)結(jié)構(gòu)比較來(lái)評(píng)價(jià)C，這種聚類(lèi)結(jié)構(gòu)應(yīng)用同樣的聚類(lèi)算法，但不同的參數(shù)值，或X的其它聚類(lèi)算法。數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)(第2版)(43-32)聚類(lèi)評(píng)估假設(shè)檢驗(yàn)令H0和H1分別是原假設(shè)和備選假設(shè)，H1:θ≠θ0，H0:θ=θ0。令

為對(duì)應(yīng)檢驗(yàn)統(tǒng)計(jì)量q的顯著性水平為ρ的置信區(qū)間，Θ1為在假設(shè)H1下θ的所有可能取值。該檢驗(yàn)的能量函數(shù)定義為：

對(duì)于指定的θΘ1，W(θ)是可選θ下的檢驗(yàn)?zāi)芰俊(θ)是參數(shù)向量值為θ時(shí)q處于臨界區(qū)域的可能性。這是H0被拒絕時(shí)做出正確決定的可能性。能量函數(shù)可用于比較兩個(gè)不同的統(tǒng)計(jì)檢驗(yàn)。在可選假設(shè)下能量大的檢驗(yàn)總是首選的。兩類(lèi)與統(tǒng)計(jì)檢驗(yàn)相關(guān)的錯(cuò)誤：假設(shè)H0為真。如果

，H0將被拒絕。出現(xiàn)錯(cuò)誤的概率是ρ。當(dāng)它為真并接受H0的可能性是1-ρ。假設(shè)H0為假。如果

，H0將被接受。出現(xiàn)錯(cuò)誤的概率是1-W(θ)，它依賴于θ的值。

最終決定拒絕還是接受H0，部分依賴于前述問(wèn)題，也依賴于其它因素，比如錯(cuò)誤決定的代價(jià)。數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)(第2版)(43-33)聚類(lèi)評(píng)估假設(shè)H0下統(tǒng)計(jì)量q的概率密度函數(shù)(probabilitydensityfunction,pdf)有一個(gè)唯一的最大值，區(qū)域是一條半直線，或者是兩條半直線。見(jiàn)圖10.8。圖10.8(a)雙尾指數(shù)的置信區(qū)間,(b)右尾指數(shù)的置信區(qū)間,(c)左尾指數(shù)的置信區(qū)間其中是零假設(shè)H0下q的ρ臨界值數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)(第2版)(43-34)聚類(lèi)評(píng)估

在實(shí)踐中，很難獲得給定假設(shè)下統(tǒng)計(jì)量q的pdf的準(zhǔn)確形狀。用仿真技術(shù)評(píng)價(jià)pdf的方法：(1)MonteCarlo技術(shù)

使用計(jì)算機(jī)生成足夠數(shù)量的人造數(shù)據(jù)來(lái)仿真這個(gè)過(guò)程。對(duì)于每一個(gè)人造數(shù)據(jù)集Xi（即r），計(jì)算已定義的指數(shù)qi（即q）?；诿總€(gè)數(shù)據(jù)集Xi的qi值，都可以創(chuàng)建一個(gè)散點(diǎn)圖。這個(gè)散點(diǎn)圖是該指數(shù)的概率密度函數(shù)的近似。

假設(shè)已經(jīng)使用指數(shù)q的r個(gè)值生成了散點(diǎn)圖。右尾檢驗(yàn)：如果數(shù)據(jù)集的q值大于(小于)人造數(shù)據(jù)集Xi中(1-ρ)·r個(gè)qi值，則拒絕（接受）H0。左尾檢驗(yàn)：如果數(shù)據(jù)集的q值小于(大于)人造數(shù)據(jù)集Xi中ρ·r個(gè)qi值，則拒絕（接受）H0。雙尾檢驗(yàn)：如果數(shù)據(jù)集的q值大于人造數(shù)據(jù)集Xi中(ρ/2)·r個(gè)qi值，且小于(1-ρ/2)·r個(gè)qi值，則拒絕（接受）H0。數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)(第2版)(43-35)聚類(lèi)評(píng)估

在實(shí)踐中，很難獲得pdf的準(zhǔn)確形狀。一般采用仿真技術(shù)評(píng)價(jià)pdf：(1)MonteCarlo技術(shù)

使用計(jì)算機(jī)生成足夠數(shù)量的人造數(shù)據(jù)來(lái)仿真這個(gè)過(guò)程。對(duì)于每一個(gè)人造數(shù)據(jù)集Xi（即r），計(jì)算已定義的指數(shù)qi（即q）?；诿總€(gè)數(shù)據(jù)集Xi的qi值，都可以創(chuàng)建一個(gè)散點(diǎn)圖。這個(gè)散點(diǎn)圖是該指數(shù)的概率密度函數(shù)的近似。

假設(shè)已經(jīng)使用指數(shù)q的r個(gè)值生成了散點(diǎn)圖。右尾檢驗(yàn)：如果數(shù)據(jù)集的q值大于(小于)人造數(shù)據(jù)集Xi中(1-ρ)·r個(gè)qi值，則拒絕（接受）H0。左尾檢驗(yàn)：如果數(shù)據(jù)集的q值小于(大于)人造數(shù)據(jù)集Xi中ρ·r個(gè)qi值，則拒絕（接受）H0。雙尾檢驗(yàn)：如果數(shù)據(jù)集的q值大于人造數(shù)據(jù)集Xi中(ρ/2)·r個(gè)qi值，且小于(1-ρ/2)·r個(gè)qi值，則拒絕（接受）H0。(2)自助法（Bootstrap）自助法建立一種可選方法來(lái)應(yīng)對(duì)數(shù)據(jù)量有限的問(wèn)題。思想：根據(jù)一個(gè)未知參數(shù)來(lái)確定未知pdf的參數(shù)。通過(guò)對(duì)X取樣，創(chuàng)建幾個(gè)偽造的數(shù)據(jù)集X1,...,Xr。用替代的方法應(yīng)對(duì)數(shù)據(jù)量有限的問(wèn)題，以提高對(duì)pdf參數(shù)估計(jì)的精確度。數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)(第2版)(43-36)聚類(lèi)評(píng)估（一）外部準(zhǔn)則與依據(jù)直覺(jué)創(chuàng)建的數(shù)據(jù)獨(dú)立劃分P進(jìn)行比較。比較相似矩陣Pm與劃分P。1、聚類(lèi)結(jié)構(gòu)C與劃分P的比較

考慮C={C1...Cm}是數(shù)據(jù)集X的一個(gè)聚類(lèi)結(jié)構(gòu)，P＝{P1...Ps}是數(shù)據(jù)的一個(gè)給定劃分。數(shù)據(jù)集合的點(diǎn)對(duì)（Xv，Xu）：

SS：屬于C的同一個(gè)簇，且屬于劃分P的同一個(gè)組。

SD：屬于C的同一個(gè)簇，且屬于P不同組。

DS：屬于C的不同簇，且屬于劃分P的同一個(gè)組。

DD：屬于C的不同簇，且屬于劃分P的不同組。現(xiàn)假設(shè)a、b、c、d分別是SS、SD、DS、DD點(diǎn)對(duì)的數(shù)目，那么a+b+c+d=M是數(shù)據(jù)集中所有點(diǎn)對(duì)的最大數(shù)目，即M＝N（N-1）/2，其中N是數(shù)據(jù)集中點(diǎn)的總數(shù)。一組測(cè)量C和P的相似度的指數(shù)：

Rand統(tǒng)計(jì)量：R=(a+d)/M

Jaccard系數(shù)：J=a/(a+b+c)以上兩個(gè)指數(shù)得到0到1之間的值，當(dāng)m=s時(shí)取到最大值。數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)(第2版)(43-37)聚類(lèi)評(píng)估FolkesandMallows指數(shù)：

(10.32)

其中m1=(a+b)，m2=(a+c)。上述三個(gè)指數(shù)，取值越大，則C和P的相似度越大。HubertsГ統(tǒng)計(jì)量：

(10.33)

該指數(shù)值越大，X和Y的相似度越大。正態(tài)Г統(tǒng)計(jì)量：

(10.34)

其中X(i,j)和Y(i,j)分別是要比較的矩陣X和Y的i行j列元素，而μx,μy,σx,σy分別是X和Y的均值和方差。該指數(shù)的取值介于-1到1之間。數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)(第2版)(43-38)聚類(lèi)評(píng)估計(jì)算這些指數(shù)的概率密度函數(shù)的蒙特卡羅技術(shù)：①

For

i=1tor

生成：在X的域上生成具有N個(gè)向量（點(diǎn)）的數(shù)據(jù)集Xi，從而生成的向量與數(shù)據(jù)集X具有相同維數(shù)。分配：把Xi的每個(gè)向量yj,i按照劃分P，分配給數(shù)據(jù)集的第j個(gè)組xj。運(yùn)行：對(duì)每個(gè)Xi，使用相同的聚類(lèi)算法，生成結(jié)構(gòu)C。令Ci為所生成的聚類(lèi)結(jié)構(gòu)。計(jì)算：為P和Ci計(jì)算給定指數(shù)q的q(Ci)值

EndFor②創(chuàng)建r個(gè)有效性指數(shù)值q(Ci)的散點(diǎn)圖(在for循環(huán)中計(jì)算)。在繪出給定統(tǒng)計(jì)指數(shù)的概率密度函數(shù)的近似圖形之后，比較統(tǒng)計(jì)指數(shù)值q和q(Ci)的值qi。這里的q指數(shù)可以使用指數(shù)R、J、FM、Г。

數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)(第2版)(43-39)聚類(lèi)評(píng)估2、比較相似矩陣P與劃分P可以把劃分P看成一個(gè)映射：

g:X

{1，...，n}.假設(shè)矩陣