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.

\[\bar{x_j}=\frac{1}{N_j}\sum_{x\in V_j}x\]

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ę

\[g_j(x)=-\|x-\bar{x_j}\| \, \textrm{ dla } j=1,2\]

Jeśli przyjmiemy normę euklidesową, dla której zachodzi

\[\|x\|=\sqrt{x^{T}x}\]

to po opuszczeniu pierwiastka otrzymujemy

\[g_j(x)=\left(x-\bar{x_j}^{T}\right)\left(x-\bar{x_j}\right)=-x^Tx+x^T\bar{x_j}+\bar{x_j}^Tx-\bar{x_j}^T\bar{x_j} \, \textrm{ dla } j=1,2\]

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

(1)\[g_j(x)=\left(x-\bar{x_j}^{T}\right)\left(x-\bar{x_j}\right)=2\bar{x_j}^Tx-\bar{x_j}^T\bar{x_j} \, \textrm{ dla } j=1,2.\]

Podstawiając \(w_j^1=2\bar{x_j}^T\) oraz \(w_j^0=\bar{x_j}^T\bar{x_j}\) otrzymujemy

\[g_j(x)=w_j^1x+w_k^0 \textrm{ dla } j=1,2.\]

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

\[\begin{split}\phi_{minodl}(x)=k, \textrm{ jeśli } \forall_{j=1,2, j\neq k} \quad g_k(x)>g_j(x)\end{split}\]

gdzie

\[\begin{split}g_j(x)&=&2\bar{x_j}^Tx-\bar{x_j}^T\bar{x_j} \, \textrm{ dla } j=1,2\\ \bar{x_j}&=&\frac{1}{N_j}\sum_{x\in V_j}x\end{split}\]

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

\[g_{ij}(x)=g_j(x)-g_j(x)=0\]

postać funkcji dyskryminacyjnych (1) otrzymujemy równanie powierzchni decyzyjnej rozdzielającej klasy \(i\) oraz \(j\)

\[g_{ij}(x)=2\left(\bar{x}_i^T-\bar{x}_j^T\right)x+\bar{x}_j^T\bar{x}_j-\bar{x}_i^T\bar{x}_i.\]

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

  1.  \(\mathbf{for} \ j=1 \ \mathbf{to} \ L \ \mathbf{do}\)
  2.  \(\qquad \bar{x}_j=\frac{1}{N_j}\sum_{x\in V_j}x\)
  3.  \(\qquad g_j=2\bar{x}_j^T-\bar{x}_j^T\bar{x}_j\)
  4.  \(y=\mathop{\rm arg\,max}_{1\leq k\leq L} {g_j}\)
Następna część - Klasyfikator kNN