5-2 K-nearest-neighbor Classifiers

[english][all]

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

Slides

最近鄰居分類法(nearest neighbor classification,簡稱 NNC)所根據的基礎是「物以類聚」,換句話說,同一類的物件應該會聚集在一起,換成數學語言來說,也就是同一類別的物件,若以高度空間中的點來表示,則這些點的距離應該會比較接近。因此,那麼對於一個未知類別的一筆資料,我們只要找出來在訓練資料中和此筆資料最接近的點,就可以判定此筆資料的類別應該和最接近的點的類別是一樣的。最近鄰居分類法是一個最直覺的分類法,在測試各種分類器時,幫被當成是最基礎的分類器,以便和其他更複雜的分類器進行效能比較。

我們也可以使用數學的語言來描述最近鄰居分類法。對於一個特定的分類問題,假設我們已經收集到一組包含類別資訊的訓練資料,共有 n 筆資料,可以表示如下: $$\{(\mathbf{x}_i, y_i), (\mathbf{x}_2, y_2), \dots, (\mathbf{x}_n, y_n)\}$$

其中 (xi, yi) 代表第 i 筆資料(xi 是特徵向量,yi 是類別資訊),那麼對於一筆新的測試資料 x,若根據最近鄰居分類法,最有可能的類別是 $$nnc(\mathbf{x}, 1) = y_p, p = \arg \min_i \| \mathbf{x} - \mathbf{x}_i \|^2.$$

在下面這個範例,我們使用 NNC 於 IRIS 資料,奇數筆資料為訓練資料(training set,或稱為設計資料,design set),偶數筆資料為測試資料(test set),計算得知辨識率為 96%,範例如下:

Example 1: knnc01.m% Get the data set [trainSet, testSet]=prData('iris'); trainNum=size(trainSet.input, 2); testNum =size(testSet.input, 2); fprintf('Use of KNNC for Iris data:\n'); fprintf('\tSize of design set (odd-indexed data)= %d\n', trainNum); fprintf('\tSize of test set (even-indexed data) = %d\n', testNum); trainSet.k=1; computed=knncEval(testSet, trainSet); correctCount=sum(testSet.output==computed); recogRate=correctCount/testNum; fprintf('Recognition rate = %g%%\n', recogRate*100);Use of KNNC for Iris data: Size of design set (odd-indexed data)= 75 Size of test set (even-indexed data) = 75 Recognition rate = 96%

From the above example, the final recognition rate of KNNC for iris dataset is 96%.

在二度空間中,由最近鄰居分類法所形成的決策分界(decision boundary)是由 Voronoi Diagram 所形成,其過程如下:

  1. 由訓練資料產生 Delauny triangles。
  2. 找出每一個三角形的中垂線,這些中垂線即可行程 Voronoi diagram。
  3. 根據資料類別,決定每一個 cell 所屬的類別。
  4. 不同類別的 cell,其共有邊界即可形成最近鄰居分類法的決策邊界。
The following example demonstrates the decision boundary formed by 1NNC:

Example 2: knncPlot02.mDS=prData('3classes'); knncPlot(DS, [], 'decBoundary');

We can also compute the distance to each class for a given input domain, and use the distance to create a posterior-like surface for each class:

Example 3: knncPlot01.mDS=prData('3classes'); knncPrm=knncTrain(DS); knncPrm.k=1; knncPlot(DS, knncPrm, '2dPosterior');

Hint
若要嚐試 Voronoi diagram 的動畫展示,可以進入本書範例程式目錄之下的 cleve 目錄,並執行 vshow.m。此程式碼由知名數學家 Cleve Moler 所提供,特此致謝!

在第一個範例中,我們算出了辨識率是 96%,但是我們並不知道每一個類別的辨識率。若要瞭解每一個類別的辨識率,可以算出「混淆矩陣」(confusion matrix),範例如下:

Example 4: knnc02.m% Get the data set [trainSet, testSet]=prData('iris'); trainNum=size(trainSet.input, 2); testNum =size(testSet.input, 2); trainSet.k=1; computed=knncEval(testSet, trainSet); confMat=confMatGet(testSet.output, computed); opt=confMatPlot('defaultOpt'); opt.className=trainSet.outputName; confMatPlot(confMat, opt);

在上述範例中,左圖既是混淆矩陣 C,其中 C(i, j) 就是代表第 i 類的資料被分到第 j 類的個數,右圖則是對應的辨識百分比。由上圖可以看出,第三類的辨識率較差(92%),第二類次之(96%),而第一類的辨識率最好,可以達到 100%。同時我們也可以看出,第二類和第三類比較容易造成 KNNC 分類器的混淆,因為所有錯誤的發生,都發生在第二類資料有一筆被分到第三類,以及第三類有兩筆資料被分到第二類。

一般而言,如果訓練資料很乾淨,那麼 KNNC 的效果都還可以接受。但是 KNNC 在下列兩種情況會發生問題:

要解決上述問題,一個簡單的方式,就是在使用訓練資料時,先使用 k-means 分群法來求取每個類別的數個代表點,然後再使用這些代表點來進行 KNNC。 在下面這個範例,我們以 IRIS 資料集來進行 KNNC 分類測試,我們先使用 k-means 將前一個範例中的 訓練資料由 75 筆降到 9 筆,然後計算辨識率,範例如下:

Example 5: knncViaKmeans01.m% ====== Get the data set [trainSet, testSet]=prData('iris'); % Get the data set fprintf('Use of KNNC for Iris data:\n'); fprintf('\tSize of design set (odd-indexed data)= %d\n', size(trainSet.input, 2)); fprintf('\tSize of test set (even-indexed data) = %d\n', size(testSet.input, 2)); uniqueClass=unique(trainSet.output); centerNum4eachClass=4; % ====== Perform k-means trainSet2=trainSet; % trainSet2 is the reduced design set after k-means trainSet2.input=[]; trainSet2.output=[]; for i=1:length(uniqueClass) % Compute trainSet2 using k-means index=find(trainSet.output==uniqueClass(i)); thisData=trainSet.input(:, index); center = kMeansClustering(thisData, centerNum4eachClass); trainSet2.input=[trainSet2.input, center]; trainSet2.output=[trainSet2.output, uniqueClass(i)*ones(1, centerNum4eachClass)]; end fprintf('After k-means clustering, size of design set = %d\n', size(trainSet2.input, 2)); % ====== Compute the recognition rate trainSet2.k=1; computed=knncEval(testSet, trainSet2); correctCount=sum(testSet.output==computed); recogRate=correctCount/length(testSet.output); fprintf('Recognition rate = %g%%\n', recogRate*100); % ====== Plot the confusion matrix confMat=confMatGet(testSet.output, computed); opt=confMatPlot('defaultOpt'); opt.className=trainSet.outputName; confMatPlot(confMat, opt);Use of KNNC for Iris data: Size of design set (odd-indexed data)= 75 Size of test set (even-indexed data) = 75 After k-means clustering, size of design set = 12 Recognition rate = 97.3333%

由上述範例可以看出,當 KNNC 比對資料量只有原先資料量的12/75時,辨識率變成 97.33%(第三類分到第二類的錯誤少了兩筆,請見上圖),反而比原先的 96.00% 還好,由此可見 k-means 找出的代表點果然具有代表性,不但降低了資料量及計算量,而且也提高了辨識率。但是,我們並無法事先知道分群數目的最佳值,只能靠窮舉法來測試,請見本章的相關作業。 Since the use of k-means clustering for generating prototypes for each class is commonly adopted in KNNC, we have put the mechanism into a function knncTrain.m. Example follows:

Example 6: knncPlot04.m[trainSet, testSet]=prData('3classes'); knncTrainPrm.method='kMeans'; knncTrainPrm.centerNum4eachClass=4; knncPrm=knncTrain(trainSet, knncTrainPrm); knncPrm.k=1; computed=knncEval(testSet, knncPrm); testSet.hitIndex=find(computed==testSet.output); knncPlot(testSet, knncPrm, 'decBoundary');

It should be noted that the k-means based data reduction is performed on each class sequentially. It only takes intra-class data distribution into consideration. If we want to take inter-class data distribution into consideration for better performance, we can apply LVQ (learning vector quantization) after k-means subsequently. LVQ will be covered in the next section.

如果訓練資料的雜訊很強,這時候若只有使用最近鄰居來決定類別,可能會失之武斷,因此另外一個常見的做法,是先求取最接近的 k 個資料點,再根據對應的 k 個類別資訊來進行投票,來決定最後的類別。這種方法稱為 k 個最近鄰居分類法(k nearest neighbor rule,簡稱 KNNC),也就是以前 k 個最靠近的鄰居來投票決定自己的類別。在下面這個範例,我們使用 KNNC 於 IRIS 資料,並讓 k 的值由 1 變化到 15,然後將辨識率對於 k 值的曲線畫出來,如下:

Example 7: knncRecogVsK01.m% Get the data set [trainSet, testSet]=prData('iris'); designNum=size(trainSet.input, 2); testNum =size(testSet.input, 2); fprintf('Use of KNNC for Iris data:\n'); fprintf('\tSize of design set (odd-indexed data)= %d\n', designNum); fprintf('\tSize of test set (even-indexed data) = %d\n', testNum); fprintf('\tRecognition rates as K varies:\n'); kMax=15; for k=1:kMax trainSet.k=k; computed=knncEval(testSet, trainSet); correctCount=sum(testSet.output==computed); recog(k)=correctCount/testNum; fprintf('\t%d-NNC ===> RR = 1-%d/%d = %.2f%%.\n', k, testNum-correctCount, testNum, recog(k)*100); end plot(1:kMax, recog*100, 'b-o'); grid on; title('Recognition rates of Iris data using K-NNR'); xlabel('K'); ylabel('Recognition rates (%)');Use of KNNC for Iris data: Size of design set (odd-indexed data)= 75 Size of test set (even-indexed data) = 75 Recognition rates as K varies: 1-NNC ===> RR = 1-3/75 = 96.00%. 2-NNC ===> RR = 1-4/75 = 94.67%. 3-NNC ===> RR = 1-3/75 = 96.00%. 4-NNC ===> RR = 1-3/75 = 96.00%. 5-NNC ===> RR = 1-2/75 = 97.33%. 6-NNC ===> RR = 1-2/75 = 97.33%. 7-NNC ===> RR = 1-2/75 = 97.33%. 8-NNC ===> RR = 1-1/75 = 98.67%. 9-NNC ===> RR = 1-4/75 = 94.67%. 10-NNC ===> RR = 1-2/75 = 97.33%. 11-NNC ===> RR = 1-2/75 = 97.33%. 12-NNC ===> RR = 1-3/75 = 96.00%. 13-NNC ===> RR = 1-3/75 = 96.00%. 14-NNC ===> RR = 1-2/75 = 97.33%. 15-NNC ===> RR = 1-2/75 = 97.33%.

由上圖可看出,太大或太小的 k 值,對辨識率都有不良的影響。至於最好的 k 值,完全是取決於資料,並沒有其他好方法來決定。

如果在這 k 個入圍者當中,投票發生「同燈同分」(tie)的情況,此時有兩種作法:


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