Lähimmät naapurit (K-Nearest Neighbors)

K-lähimmän naapurin (KNN) algoritmi on ei-parametrinen, valvotun oppimisen algoritmi, jota käytetään luokittelu- ja regressiotehtäviin koneoppimisessa. Se perustuu läheisyyden käsitteeseen olettaen, että samankaltaiset havainnot sijaitsevat lähellä toisiaan. KNN on laiska oppimisalgoritmi, eli se ei vaadi koulutusvaihetta, vaan tekee ennusteita tallentamalla koko koulutusaineiston ja käyttämällä sitä uusien havaintojen luokan tai arvon määrittämiseen. Algoritmi ennustaa testiaineiston havaintopisteen tuloksen tunnistamalla ‘k’ koulutusaineiston lähintä pistettä ja päättelee tuloksen näiden naapureiden perusteella. Tämä menetelmä on hyvin intuitiivinen ja jäljittelee ihmisen havainnointistrategioita, jotka perustuvat uuden tiedon vertaamiseen aiempiin esimerkkeihin.

Kuinka KNN toimii

KNN etsii annetulle kyselypisteelle ‘k’ lähintä havaintoa ja käyttää näitä naapureita ennusteen tekemiseen.

• Luokittelutehtävissä algoritmi liittää kyselypisteen siihen luokkaan, joka esiintyy useimmin sen ‘k’ lähimmän naapurin joukossa, eli käyttää enemmistöäänestystä. Enemmistöäänestys KNN:ssä voidaan ymmärtää “pluraaliäänestyksenä” usean luokan tapauksessa, jolloin kyselypiste liitetään siihen luokkaan, jolla on suurin määrä naapureita, vaikka se ei muodostaisi ehdotonta enemmistöä.
• Regressiotehtävissä arvo ennustetaan laskemalla ‘k’ lähimmän naapurin arvojen keskiarvo.

Läheisyyden ja samankaltaisuuden periaatteet, jotka ovat keskeisiä ihmisen havainnoinnissa, ovat myös KNN:n toiminnan ytimessä, sillä lähekkäin olevien havaintojen oletetaan olevan samankaltaisia ja siten saavan samanlaisia tuloksia.

Etäisyysmittarit

KNN käyttää erilaisia etäisyysmittareita lähimpien naapureiden määrittämiseen, ja niiden valinta on ratkaisevaa algoritmin suorituskyvylle:

• Euklidinen etäisyys: Suora etäisyys kahden pisteen välillä moniulotteisessa avaruudessa, yleisesti käytetty jatkuville muuttujille. Tämä on yleisin etäisyysmittari KNN:ssä ja erityisen hyödyllinen, kun data on tiheää ja jatkuvaa.
• Manhattan-etäisyys: Tunnetaan myös taksietäisyytenä; laskee etäisyyden summaamalla kahden pisteen koordinaattien itseisarvoiset erot. Tämä on hyödyllinen tilanteissa, joissa liikkuminen on rajoitettu ortogonaalisiin suuntiin, kuten ruutukuvioisella reitillä.
• Minkowskin etäisyys: Yleistetty muoto sekä euklidisesta että manhattan-etäisyydestä, parametrina ‘p’. Kun p=1, kyseessä on manhattan-etäisyys ja kun p=2, kyseessä on euklidinen etäisyys. Tämä etäisyysmittari tarjoaa joustavuutta valitun ‘p’-arvon mukaan.
• Hammingin etäisyys: Käytetään kategoriselle datalle; laskee kahden binäärivektorin erimielisten bittien lukumäärän. Tämä on erityisen hyödyllinen binääriluokittelutehtävissä, joissa muuttujat ovat binääriarvoisia.

Oikean ‘k’-arvon valinta

Parametri ‘k’ KNN:ssä määrittää, kuinka monta naapuria otetaan huomioon. Oikean ‘k’-arvon valinta on tärkeää:

• Pieni ‘k’ voi aiheuttaa ylisovittamista, jolloin malli on liian herkkä koulutusaineiston kohinalle ja oppii virheellisiä kuvioita, jotka eivät yleisty.
• Suuri ‘k’ voi johtaa alisovittamiseen, jolloin malli yleistää liikaa ja jättää huomiotta tärkeitä kuvioita, mikä heikentää ennustetarkkuutta.
• Yleensä ‘k’ valitaan ristivalidoinnin avulla ja sen tulisi olla pariton luku, jotta luokittelussa vältetään tasatulokset. ‘k’-arvolla on merkittävä vaikutus mallin tarkkuuteen ja se määritetään usein empiirisesti.

Edut ja haitat

Edut

• Yksinkertainen ja intuitiivinen: Helppo ymmärtää ja toteuttaa, joten se sopii hyvin aloittelijoille. KNN:n yksinkertaisuus perustuu sen suoraviivaiseen tapaan vertailla testihavaintoja tallennettuihin esimerkkeihin.
• Ei koulutusvaihetta: KNN ei vaadi erillistä koulutusvaihetta, vaan tekee ennusteet tallennetun aineiston avulla. Mallia voi päivittää lisäämällä uusia havaintoja aineistoon.
• Monipuolinen: Soveltuu sekä luokittelu- että regressiotehtäviin ja sitä voidaan käyttää laajasti eri aloilla. KNN soveltuu myös moniluokkaluokitteluun.

Haitat

• Laskennallisesti raskas: Koska jokainen uusi havainto verrataan koko aineistoon, algoritmi voi olla hidas ja vaatia paljon resursseja etenkin suurilla aineistoilla. KNN:n aikavaativuus on O(n), missä n on havaintojen määrä.
• Herkkä poikkeaville arvoille: Poikkeavat arvot voivat vaikuttaa merkittävästi ennusteisiin, sillä nämä poikkeamat voivat vääristää tuloksia erityisesti, kun ‘k’ on pieni.
• Ulottuvuuden kirous: Korkeissa ulottuvuuksissa algoritmin suorituskyky heikkenee, koska havaintojen väliset etäisyydet menettävät merkitystään. Kun ulottuvuuksien määrä kasvaa, avaruuden tilavuus kasvaa ja data harvenee, mikä vaikeuttaa lähimpien naapureiden löytämistä.

Käyttökohteet

KNN:ää käytetään monilla aloilla sen yksinkertaisuuden ja tehokkuuden vuoksi:

• Suosittelujärjestelmät: Käytetään tuotteiden tai sisällön suosittelemiseen käyttäjille samankaltaisten käyttäjien mieltymysten perusteella. KNN auttaa tunnistamaan samankaltaisia käyttäjiä tai kohteita piirteiden samankaltaisuuden perusteella.
• Kuvioiden tunnistus: Hyödynnetään käsinkirjoituksen tunnistuksessa ja muissa kuvioiden tunnistustehtävissä, joissa kuvat voidaan luokitella pikseliarvojen samankaltaisuuden perusteella.
• Datan imputointi: Hyödyllinen puuttuvien arvojen täyttämisessä aineistossa arvioimalla ne samankaltaisten havaintojen perusteella, näin säilytetään aineiston eheys.
• Rahoitus ja terveydenhuolto: Sovelletaan osakemarkkinoiden ennustamiseen, riskinarviointiin ja lääketieteelliseen diagnostiikkaan analysoimalla historiallisten tietojen samankaltaisuuksia. Terveydenhuollossa KNN voi ennustaa diagnooseja vertaamalla potilaan oireita aiempiin tapauksiin.

Toteutus Pythonilla

KNN voidaan toteuttaa esimerkiksi scikit-learn -kirjastolla Pythonissa. Tässä on perusesimerkki KNN:n käytöstä luokitteluun:

from sklearn.neighbors import KNeighborsClassifier
from sklearn.model_selection import train_test_split
from sklearn.datasets import load_iris
from sklearn.metrics import accuracy_score

# Ladataan aineisto
iris = load_iris()
X, y = iris.data, iris.target

# Jaetaan aineisto opetus- ja testijoukkoihin
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42)

# Alustetaan KNN-luokittelija k=3
knn = KNeighborsClassifier(n_neighbors=3)

# Sovitetaan malli
knn.fit(X_train, y_train)

# Ennustetaan
y_pred = knn.predict(X_test)

# Arvioidaan tarkkuus
accuracy = accuracy_score(y_test, y_pred)
print(f"Accuracy: {accuracy:.2f}")

Lähimmät naapurit (KNN) tieteellisessä tutkimuksessa

K-lähimmän naapurin (KNN) algoritmi on keskeinen menetelmä monilla aloilla, kuten multimediahaun, datalouhinnan ja koneoppimisen parissa, erityisesti suurten aineistojen yhteydessä.

Merkittäviä tutkimusartikkeleita:

• “Approximate k-NN Graph Construction: a Generic Online Approach”, Wan-Lei Zhao ym.:
  Esittelee tehokkaan menetelmän sekä likimääräiseen k-lähimmän naapurin hakuun että graafien rakentamiseen. Artikkelissa kuvataan dynaaminen ja monipuolinen ratkaisu, joka soveltuu erilaisiin datakokoihin ja -ulottuvuuksiin sekä tukee online-päivityksiä, joita monissa muissa menetelmissä ei ole. Lue lisää.

• “Parallel Nearest Neighbors in Low Dimensions with Batch Updates”, Magdalen Dobson ja Guy Blelloch:
  Esittelee rinnakkaisia algoritmeja, joissa yhdistetään kd-puu ja Morton-järjestys zd-puurakenteeksi, optimoitu matalille ulottuvuuksille. Tekijät osoittavat menetelmänsä nopeammaksi kuin aiemmat algoritmit ja saavuttavat huomattavia nopeutuksia rinnakkaisprosessoinnilla. Zd-puu tukee ainutlaatuisesti rinnakkaisia eräpäivityksiä, mikä on uutta k-lähimmän naapurin tietorakenteissa. Lue lisää.

• “Twin Neural Network Improved k-Nearest Neighbor Regression”, Sebastian J. Wetzel:
  Tarkastelee uutta lähestymistapaa k-lähimmän naapurin regressioon käyttäen kaksosneuroverkkoja. Menetelmä keskittyy regressiotavoitteiden erojen ennustamiseen, mikä parantaa suorituskykyä perinteisiin neuroverkkoihin ja k-lähimmän naapurin regressiomenetelmiin verrattuna pienillä ja keskisuurilla aineistoilla. Lue lisää.