3.8 Algoritmus K-najbližšieho suseda (kNN)

Tréningová súprava

Algoritmus k-najbližšieho suseda je klasifikačný algoritmus, ktorý hovorí, že najprv zafixujeme počet susedov (okolitých inštancií) k na konkrétnu hodnotu a potom určíme, koľko k-najbližších susedov je červených a modrých: červený sused je inštancia patriaca do červenej triedy a modrý sused je inštancia patriaca do modrej triedy. Napríklad, ak zafixujeme číslo k na 3, traja najbližší susedia zeleného kruhu sú vo vnútri plného kruhu. K dispozícii sú dva červené trojuholníky a jeden modrý štvorec.

Ďalej, algoritmus k-najbližšieho suseda hovorí, že nová inštancia, nová dvojica bodiek sa pridá do triedy početnejšieho suseda: ak sú červení susedia početnejší, hovoríme, že nová inštancia patrí do červenej triedy, a podobne, ak sú modrí susedia početnejší, hovoríme, že nová inštancia patrí do modrej triedy. Môžete si to predstaviť aj ako príslovie "s kým si, to je to, kto si" vo svete strojového učenia.

V našom príklade, keď je hodnota k stanovená na 3, dospejeme k záveru, že by sme mali priradiť zelený kruh k červenej triede, pretože máme dvoch červených susedov a jedného modrého suseda.

Pozrime sa, čo sa stane, ak číslo k opravíme na 5. Na obrázku je táto štvrť znázornená prerušovaným kruhom. Keďže teraz existujú tri modré štvorce a dva červené trojuholníky, záver by bol, že zelený kruh by mal byť spojený s modrou triedou.

 Táto časť je spárovaná s cvičením 8 a Jupyter Notebook 08-k-nearest_neighbors.ipynb. Ak chcete obsah ďalej sledovať, kliknite na odkaz a potom na tlačidlo na otvorenie obsahu v Google Collab. Ak si poznámkové bloky prezeráte v lokálnom počítači, vyhľadajte poznámkový blok s rovnakým názvom v obsahu a spustite ho. Podrobnejšie pokyny nájdete v  časti Hands-on Zone a v praktickej  lekcii Jupyter Notebook.

Sprievodný materiál obsahuje spomínanú sadu bodov a aplikáciu, v ktorej môžete preskúmať, čo sa stane, ak zvolíte inú hodnotu čísla k. Keďže algoritmus sa musí rozhodnúť, ktorých susedov je viac, je rozumné zvoliť nepárne hodnoty čísla k.

Všimnite si, že okrem počtu susedov k závisí výsledok algoritmu aj od toho, ako meriame vzdialenosti k susedom! Aby sme našli najbližších susedov, musíme nejako zmerať vzdialenosť k nim.

Doteraz sme sa stretli so vzdialenosťou nazývanou euklidovská vzdialenosť. Euklidovská vzdialenosť medzi bodmi \(A\) a \(B\) sa vypočíta ako dĺžka dĺžok spájajúcich body \(A\) a \(B\). Napríklad pre body \(A =(0,0)\) a \(B =(3,4)\) sa euklidovská vzdialenosť vypočíta ako \(\sqrt{(3 − 0)^2 +(4 − 0)^2} = 5\)

Euklidovská vzdialenosť

Existuje aj mnoho ďalších vzdialeností. Môže vás napríklad zaujať vzdialenosť Manhattanu. Na rozdiel od euklidovskej vzdialenosti, ktorá počíta "preponu" trojuholníka definovaného bodmi \(A\) a \(B\) a \(O\) (ak sa budeme riadiť predchádzajúcim obrázkom), vzdialenosť Manhattan vypočíta súčet "nôh" tohto trojuholníka. Pre body \(A\) a \(B\) by hodnota vzdialenosti Manhattan bola \(| 3 − 0 | + | 4 − 0 | = 7\).

Akú vzdialenosť zvolíme, závisí od povahy úlohy a významu, ktorý majú atribúty, s ktorými pracujeme. Vo všeobecnosti môžeme vyskúšať viac vzdialeností a vybrať si tú, pri ktorej dosiahneme najlepšie výsledky. O tom si povieme neskôr. Je dôležité poznamenať, že funkcia musí spĺňať určité matematické vlastnosti, aby mohla byť deklarovaná ako vzdialenosť, takže nie každá funkcia môže byť užitočná.

 Rovnako ako iné algoritmy strojového učenia, aj algoritmus x-najbližšieho suseda sa trénuje cez trénovaciu množinu. Je zaujímavé poznamenať, že fáza učenia v tomto algoritme je v skutočnosti obmedzená len na ukladanie súboru údajov. V iných algoritmoch, ako je lineárna regresia alebo logistická regresia, sme videli, že v tejto fáze sa hodnoty niektorých parametrov, ktoré sa objavujú v modeli, vypočítavajú hľadaním funkcie minimálnej chyby. Algoritmus x-najbližšieho suseda taký nie je. Mapovanie, ktoré sa učíme Nie je to o konkrétnej funkcii, je to o samotných údajoch a krokoch, ktoré je potrebné urobiť. Preto je bežné nazývať modely, ktoré majú túto vlastnosť, neparametrické modely.

Algoritmus k-najbližšieho suseda vykonáva všetku prácu počas aplikácie, t.j. Rozhodnite sa, do ktorej triedy nová inštancia patrí. Keď potrebujeme klasifikovať novú inštanciu, najprv vypočítame vzdialenosť novej inštancie od všetkých inštancií v trénovacom súbore údajov. Ďalej triedime tieto vzdialenosti od najmenších po najväčšie. Prvých k vzdialeností (pretože sú to vzdialenosti k k k najbližším susedom) a vyberieme inštancie z tréningovej sady, na ktorú sa vzťahujú. Naďalej sledujeme, čo sa deje v priestore ich pamiatok a hľadáme najpočetnejšie pamiatky, teda najväčšiu triedu. Ako sme videli v úvodnom príklade, nová inštancia by mala byť spojená s triedou, ktorá je najpočetnejšia.

Tento algoritmus sa dá ľahko implementovať, takže si vyhrňme rukávy a začnime!

Predstavme si, že pracujeme s množinou údajov, ktoré sme doteraz používali, a že každá inštancia má tvar \((x1, x2, mark)\), kde \(mark\) je hodnota 0 pre červenú alebo 1 pre modrú.

Na meranie vzdialenosti medzi inštanciami použijeme funkciu euklidsko_rastojanje, ktorá je definovaná nasledujúcim blokom kódu:

def euclidean_distance(instance1, instance2):
  return np.sqrt((instance1[0]-instance2[0])**2 + (instance1[1]-instance2[1])**2)

Samotný algoritmus x-najbližšieho suseda je reprezentovaný nasledujúcim blokom kódu:

def kNN(k, instances, new_instance, classes={0: 'red', 1: 'blue'}):

  # first, calculate the distances between the new instance and all instances in the dataset
  distances = [euclidean_distance(instance, new_instance) for instance in instances]

  # then sort the distances, extract the k smallest ones and the corresponding instances
  # declare them as neighbors
  neighbors = np.argsort(distances)[0:k]

  # then read the labels of the neighbors and count them
  neighbor_labels = [instances[neighbor][2] for neighbor in neighbors]
  label_counts = np.bincount(neighbor_labels)

  # the label of the new instance will be the label of the most frequent neighbor
  label = np.argmax(label_counts)

  return classes[label]

V ňom, ako sme už diskutovali, vykonávame nasledujúce kroky:

1. Vypočítame vzdialenosť od novej inštancie ku všetkým inštanciám v množine údajov.
2. A potom ich dáme uprostred noci a potom ich dáme do tmy.
3. A my sme tí, ktorí majú právo byť susedmi.
4. V súbore izolovaných susedov počítame najpočetnejšie,
5. Dospeli sme k záveru, že nová inštancia patrí do triedy najpočetnejšieho suseda.

Ešte sa musíme naučiť, ako zvoliť najlepšiu hodnotu čísla k. O tom si povieme v ďalšej lekcii.

Show answer

Show answer