Klasyfikator minimalno-odległościowy¶
Bardzo prostym i intuicyjnym klasyfikatorem jest klasyfikator minimalno-odległościowy. Klasyfikator minimalno-odległościowy zakłada, że każda z klas jest reprezentowana przez jeden typowy dla niej obiekt. W roli tego reprezentanta najczęściej występuje środek (średnia arytmetyczna) obiektów z danej klasy, tzn.
gdzie \(V_j\) oznacza podzbiór zbioru uczącego złożony z elementów należących do klasy \(C_j\), natomiast \(N_j\) oznacza liczebność tego podzbioru. Algorytm przydziela wektor \(x\) do tej klasy, dla której odległość wektora \(x\) od jej reprezentanta jest najmniejsza, w sensie przyjętej metryki.
Rozpatrzmy funkcję
Jeśli przyjmiemy normę euklidesową, dla której zachodzi
to po opuszczeniu pierwiastka otrzymujemy
Ponieważ pierwszy składnik powyższego równania nie zależy od numeru klasy, może on zostać pominięty. W rezultacie otrzymujemy następujący, ogólny wzór na funkcję dyskryminacyjne klasyfikatora minimalno-odległościowego
Podstawiając \(w_j^1=2\bar{x_j}^T\) oraz \(w_j^0=\bar{x_j}^T\bar{x_j}\) otrzymujemy
Przy założeniu normy euklidesowej funkcje dyskryminacyjne są liniowe. Ostatecznie klasyfikator minimalno-odległościowy \(\phi_{minodl}\) możemy zdefiniować w następujący sposób
gdzie
Zatem klasyfikator minimalno-odległośiowy przypisuje wektorowi \(x\) tą klasę, dla której odległość wektora x od środka klasy jest najmniejsza. Podstawiając do wzoru
postać funkcji dyskryminacyjnych (1) otrzymujemy równanie powierzchni decyzyjnej rozdzielającej klasy \(i\) oraz \(j\)
Z powyższego wzoru wynika, że powierzchnia rozdzielająca jest hiperpłaszczyzną prostopadłą do wektora łączącego środki klas, które rozdziela.
Algorytm 1 Klasyfikator minimalno-odległościowy
Dane: zbiór uczący \(X_{train}=\{(x_i,y_i):x_i\in X, y_i\in C=\{-1,1\}\}\), \(x\) - klasyfikowany obiekt
Wyniki: \(y\in\{1,2\}\) - etykieta klasy
- \(\mathbf{for} \ j=1 \ \mathbf{to} \ L \ \mathbf{do}\)
- \(\qquad \bar{x}_j=\frac{1}{N_j}\sum_{x\in V_j}x\)
- \(\qquad g_j=2\bar{x}_j^T-\bar{x}_j^T\bar{x}_j\)
- \(y=\mathop{\rm arg\,max}_{1\leq k\leq L} {g_j}\)