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

第10章模型選擇與模型評估

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

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

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

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

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

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

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

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

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

E=TrE+EopAIC定義如下：

(10.14)

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

(10.15)

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

(10.16)方差var2定義為

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(10.32)

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

(10.33)

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

(10.34)

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

For

i=1tor

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

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

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

g:X

{1，...，n}.假設矩陣