6-2 Methods for Recognition Rate Estimate (挐vw)

[english][all]

(請注意：中文版本並未隨英文版本同步更新！)

本節說明在分類器的設計過程中，如何預估其辨識率或錯誤率。

「內部測試錯誤率」（inside test error）又稱為「重新帶入錯誤率」（resubstitution error）或「表面錯誤率」（apparent error rate），指的是使用全部的資料進行訓練以設計分類器，之後再以同一組資料進行測試。此方式雖然充分運用每一筆資料來進行分類器設計，但因為測試資料和訓練資料是同一份，所得到的辨識率會偏高（錯誤率偏低），這種「球員兼裁判」之的錯誤率，並不具客觀性。

舉例來說，如果我們使用 1-NNR 為分類器，再使用內部錯誤率估測法，所得到的辨識率就是 100%（錯誤率為 0%），很明顯地，這是過於樂觀的結果，因此內部錯誤率估測法的結果只能姑且聽之，參考性比較低，我們只能將之視為實際錯誤率的下限值（或是實際辨識率的上限值）。一般而言，我們使用內部錯誤率來進行初步檢測，如果一個分類器的內部錯誤率已經很高，代表有下列兩種可能：

• 分類器設計方法有錯誤。
• 設計資料有錯誤，特徵向量並沒有分類的鑑別能力。

當然，這只是一個基本的檢測，內部錯誤率過高，表示可能有上述兩種錯誤，但是內部錯誤率若很低，並非代表分類器或資料正確，此時還必須靠「外部測試錯誤率」（outside test error）來進行進一步的檢定，如下所述。

為了避免「球員兼裁判」之嫌，最簡單的方式便是在進行錯誤率預估之時，將資料切成設計資料 design set）和測試資料 test set，我們可以使用 DS 來進行分類器的設計，然後使用 TS 來進行辨識率的測試，此種辨識率稱為「外部測試錯誤率」（outside test error）或「遮蔽式錯誤率」（holdout error）。此種方法的特性如下：

• 由於設計資料和測試資料完全不相同，因此所得到的辨識率較為客觀。
• 在現實的例子中，資料量是有限的，外部測試錯誤率卻必須切出一部分的資料進行錯誤測試，因而將導致設計出的分類器錯誤率較高。
• 一般而言，訓練資料的資料量越大，分類器的精確度越高。因此我們可用外部錯誤率來估測分類器設計的參數，然後使用相同的參數以及全部的樣本資料，來設計一個完整的分類器。

我們可以將外部測試錯誤率做進一步的延伸，先將所有資料等切成兩份 A 與 B，在第一次預估時以 A 為訓練資料、B 為測試資料，但在第二次預估時，改以以 B 為訓練資料、A 為測試資料；最後再求這兩次預估的平均錯誤率，稱為「雙向式外部錯誤率」（two-way outside test error）或 two-fold cross validation。 使用前述的 two-fold cross validation 時，由於使用的設計資料量大約只有樣本資料的一半，因此得到的辨識率會偏低。為了更有效地預估辨識率，我們可以將資料切成 m 個子集合 S₁, S₂, ..., S_m，每個集合所包含的資料個數大約相等，並滿足下列條件：

• S = S₁∪S₂∪...∪S_m
• |S₁| = |S₂| = ... = |S_m|
• S_i∩S_j = φ (empty set) whenever i≠j.
• The class distribution of each S_j, i=1 to m, should be as close as possible to that of the original dataset S.

然後以下列方式來估測辨識率：

1. 以 S_i 為測試資料，以剩餘的資料 S-S_i 設計分類器，再以 S_i 對這個分類器進行測試，得到外部測試辨識率。
2. 重複上述的步驟，直到得到每個子集合 S_i 的辨識結果，並計算整體辨識率。

上述的方法稱為 m-fold cross validation，所得到的錯誤率稱為輪迴錯誤率。

Example 1: rreViaCv01.m

dataSet=prData('iris'); m=5; cvOpt=cvDataGen('defaultOpt'); cvOpt.foldNum=m; cvOpt.cvDataType='full'; cvData=cvDataGen(dataSet, cvOpt); foldNum=length(cvData); % Actual no. of folds for i=1:foldNum [qcPrm, logProb1, tRr(i)]=qcTrain(cvData(i).TS); tSize(i)=length(cvData(i).TS.output); [computedClass, logProb2, vRr(i)]=qcEval(cvData(i).VS, qcPrm); vSize(i)=length(cvData(i).VS.output); end tRrAll=dot(tRr, tSize)/sum(tSize); vRrAll=dot(vRr, vSize)/sum(vSize); plot(1:foldNum, tRr, '.-', 1:foldNum, vRr, '.-'); xlabel('Folds'); ylabel('Recog. rate (%)'); legend('Training RR', 'Validating RR', 'location', 'northOutside', 'orientation', 'horizontal'); fprintf('Training RR=%.2f%%, Validating RR=%.2f%%\n', tRrAll*100, vRrAll*100); Training RR=97.83%, Validating RR=97.33%

Since this type of performance evaluation using cross-validation is used often, we have created a function to serve this purpose, as shown in the next example where 10-fold cross-validation is applied to IRIS dataset:

Example 2: perfCv4qc01.m

DS=prData('iris'); showPlot=1; foldNum=10; classifier='qc'; [vRrAll, tRrAll]=perfCv(DS, classifier, [], foldNum, showPlot); fprintf('Training RR=%.2f%%, Validating RR=%.2f%%\n', tRrAll*100, vRrAll*100); Training RR=98.07%, Validating RR=98.00%

當 m 越來越大時，所需要的計算量也會越來越大，因此我們可以視實際情況（樣本資料量大小、分類器設計的計算時間）來決定 m 的值，說明如下：

• m 的最小值是 2，此時輪迴錯誤率即等於前一節所介紹的雙向外部錯誤率。
• m 的最大值等於樣本資料的個數，此時輪迴錯誤率就變成下面所要介紹的「一次挑一個錯誤率」。

「"一次挑一個"錯誤率」（leave-one-out error rate）是樣式辨認中最常被用到的錯誤率預估方法，因為每個測試資料都沒有參與分類器的設計，因此也是一種較為公平、客觀的錯誤率預估方式。整個錯誤率預估演算過程又稱鐮刀式流程（jackknife procedure），其主要步驟如下所述：

1. 先從資料集中取出一筆資料 x_i，以剩餘的資料設計分類器，再以 x_i 對這個分類器進行測試。
2. 重複上述的步驟，直到得到每一筆資料的辨識結果，並計算整體 LOO 錯誤率或 LOO 辨識率。

由上述方法可以看出，LOO 辨識率的特性如下：

• 由於每一筆資料都被用於當成一次測試資料，因此對於整體資料的使用率可說是達到最極致。
• 若有 n 筆資料，則在此過程中，必須設計 n 個分類器，如果 n 很大或是分類器的設計需要大量計算（例如 GMM 或是類神經網路等），此種錯誤率估測方式就會耗費大量計算時間，曠日廢時。

也由於計算量太大，因此我們通常只使用簡單的分類器，例如 KNNC，來估測 LOO 錯誤率，並進而推斷樣本資料的特徵是否能夠足夠的鑑別能力。在下面這個範例中，我們使用一組亂數來產一組包含四個類別的樣本資料，然後利用 knncLoo 指令來計算 1-NNR 所產生的 LOO，並將辨識錯誤的資料點打上「x」號，以便檢查，如下：

Example 3: knncLoo01.m

DS=prData('random2'); dsScatterPlot(DS); knncPrm.k=1; plotOpt=1; [recogRate, computed, nearestIndex]=knncLoo(DS, knncPrm, plotOpt);

讀者可以改變上述的 k 值，就可以得到 KNNC 在不同的 k 值的辨識結果。

---

Data Clustering and Pattern Recognition (資料分群與樣式辨認)