[english ][all ] (請注意:中文版本並未隨英文版本同步更新! )
Slides
最近鄰居分類法 (nearest neighbor classification,簡稱 NNC)所根據的基礎是「物以類聚」,換句話說,同一類的物件應該會聚集在一起,換成數學語言來說,也就是同一類別的物件,若以高度空間中的點來表示,則這些點的距離應該會比較接近。因此,那麼對於一個未知類別的一筆資料,我們只要找出來在訓練資料中和此筆資料最接近的點,就可以判定此筆資料的類別應該和最接近的點的類別是一樣的。最近鄰居分類法是一個最直覺的分類法,在測試各種分類器時,幫被當成是最基礎的分類器,以便和其他更複雜的分類器進行效能比較。
我們也可以使用數學的語言來描述最近鄰居分類法。對於一個特定的分類問題,假設我們已經收集到一組包含類別資訊的訓練資料,共有 n 筆資料,可以表示如下:
$$\{(\mathbf{x}_i, y_i), (\mathbf{x}_2, y_2), \dots, (\mathbf{x}_n, y_n)\}$$
其中 (x i , yi ) 代表第 i 筆資料(x i 是特徵向量,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 所形成,其過程如下:
由訓練資料產生 Delauny triangles。
找出每一個三角形的中垂線,這些中垂線即可行程 Voronoi diagram。
根據資料類別,決定每一個 cell 所屬的類別。
不同類別的 cell,其共有邊界即可形成最近鄰居分類法的決策邊界。
The following example demonstrates the decision boundary formed by 1NNC:
Example 2: knncPlot02.m DS=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.m DS=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 在下列兩種情況會發生問題:
當訓練資料量很大時,或是資料維度很高時,尋找最近鄰居可能要花很多時間。
當訓練資料含有很多雜訊時,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)的情況,此時有兩種作法:
k 值的選取,盡量不要出現在投票時會有兩個第一名的情況,例如,當類別個數等於 3 時,k 的值可以選取 4 或 7 或 10 等。
另外,我們也可以在這最近的 k 個鄰居中,以距離的遠近來表示投票的權重,這就是所謂的 distance-weighted KNNC,這是一個比較合理的作法。
Data Clustering and Pattern Recognition (資料分群與樣式辨認)