K-närmsta grannar

Algoritmen k-närmsta grannar (KNN) är en icke-parametrisk, övervakad inlärningsalgoritm som används för klassificerings- och regressionsuppgifter inom maskininlärning. Den bygger på närhetsprincipen och antar att liknande datapunkter ligger nära varandra. KNN är en lat inlärningsalgoritm, vilket innebär att den inte kräver någon träningsfas utan gör förutsägelser genom att lagra hela träningsdatamängden och använda den för att avgöra klassen eller värdet på nya datapunkter. Algoritmen förutsäger utfall för en testdatapunkt genom att identifiera de ‘k’ träningsdatapunkter som ligger närmast testdatan och drar slutsatsen baserat på dessa grannar. Metoden är mycket intuitiv och efterliknar mänskliga perceptionsstrategier som bygger på att jämföra ny data med kända exempel.

Så fungerar KNN

KNN fungerar genom att identifiera de ‘k’ närmaste datapunkterna till en given frågepunkt och använder dessa grannar för att göra en förutsägelse.

• Vid klassificeringsuppgifter tilldelar algoritmen frågepunkten den klass som är vanligast bland dess ‘k’ närmaste grannar, vilket kallas majoritetsomröstning. Majoritetsomröstning i KNN kan ses som “pluralitetsomröstning” vid flera klasser, där frågepunkten tilldelas klassen med flest grannar, även om det inte utgör en absolut majoritet.
• Vid regressionsuppgifter förutsäger den värdet genom att ta medelvärdet av de ‘k’ närmaste grannarnas värden.

Närhets- och likhetsprinciperna, som är centrala för mänsklig perception, är också grundläggande för hur KNN fungerar, eftersom datapunkter som ligger nära varandra i egenskapsrymden antas vara mer lika och därmed sannolikt har liknande utfall.

Avståndsmått

För att bestämma de närmaste grannarna använder KNN olika avståndsmått, vilka är avgörande för dess prestanda:

• Euklidiskt avstånd: Den raka linjens avstånd mellan två punkter i ett flerdimensionellt rum, vanligt för kontinuerliga variabler. Det är det vanligaste avståndsmåttet för KNN och särskilt användbart när data är tät och kontinuerlig.
• Manhattan-avstånd: Kallas även taxiavstånd, och beräknar avståndet genom att summera de absoluta skillnaderna mellan två punkters koordinater. Det är användbart i rutnätsliknande miljöer där rörelser är begränsade till ortogonala riktningar.
• Minkowski-avstånd: En generalisering av både euklidiskt och manhattan-avstånd, parametriserad av ‘p’. Om p=1 blir det manhattan-avstånd, och om p=2 blir det euklidiskt avstånd. Detta avståndsmått ger flexibilitet beroende på valt ‘p’.
• Hamming-avstånd: Används för kategorisk data och räknar antalet avvikande bitar mellan två binära vektorer. Detta är särskilt användbart vid binära klassificeringsproblem där attributen har binära värden.

Att välja rätt ‘k’-värde

Parametern ‘k’ i KNN står för antalet grannar att ta hänsyn till. Det är avgörande att välja rätt ‘k’:

• Ett litet ‘k’ kan leda till överanpassning, där modellen blir för känslig för brus i träningsdata och fångar upp mönster som inte generaliseras.
• Ett stort ‘k’ kan leda till underanpassning, där modellen blir för generell och ignorerar viktiga mönster, vilket ger sämre prediktiv prestanda.
• Vanligtvis väljs ‘k’ genom korsvalidering och bör vara ett udda tal för att undvika oavgjort vid klassificering. Valet av ‘k’ kan ha stor inverkan på modellens noggrannhet och avgörs ofta empiriskt.

Fördelar och nackdelar

Fördelar

• Enkel och intuitiv: Lätt att förstå och implementera, vilket gör den lämplig för nybörjare. KNN:s enkelhet ligger i dess direkta tillvägagångssätt att jämföra testexempel med lagrade exempel.
• Ingen träningsfas: KNN kräver ingen explicit träningsfas, utan gör förutsägelser med hjälp av den lagrade datamängden. Modellen kan alltså uppdateras enkelt genom att lägga till nya datapunkter.
• Mångsidig: Kan användas för både klassificering och regression, och har bred tillämpning inom olika områden. Den är även användbar vid multilabel-klassificering.

Nackdelar

• Beräkningsintensiv: Eftersom den kräver att varje ny datapunkt jämförs med hela datamängden kan den vara långsam och resurskrävande, särskilt vid stora datamängder. Tidskomplexiteten för KNN är O(n), där n är antalet träningsprover.
• Känslig för avvikare: Förekomsten av avvikare kan påverka förutsägelserna avsevärt, eftersom dessa avvikande punkter kan snedvrida resultaten, särskilt när ‘k’ är litet.
• Dimensionsförbannelsen: I högdimensionella rum kan algoritmens prestanda försämras då avstånden mellan datapunkter blir mindre meningsfulla. När dimensionerna ökar ökar också rummets volym, vilket gör att data blir gles. Denna gleshet gör det svårt för KNN att hitta närmaste grannar effektivt.

Användningsområden

KNN används inom många områden tack vare sin enkelhet och effektivitet:

• Rekommendationssystem: Används för att rekommendera produkter eller innehåll till användare baserat på preferenser hos liknande användare. KNN kan identifiera liknande användare eller objekt genom att utvärdera egenskapernas likhet.
• Mönsterigenkänning: Används vid handskriftsigenkänning och andra mönsterigenkänningsuppgifter, där den kan klassificera bilder utifrån pixelvärdens likhet.
• Dataimputation: Användbar för att fylla i saknade värden i datamängder genom att uppskatta dem utifrån liknande datapunkter, vilket bevarar datamängdens integritet.
• Finans och hälsa: Används vid aktiemarknadsprognoser, riskbedömning och medicinsk diagnostik genom att analysera likheter i historisk data. Inom hälso- och sjukvård kan den förutsäga patientdiagnoser genom att jämföra symtom mot kända fall.

Implementering i Python

KNN kan implementeras med bibliotek som scikit-learn i Python. Här är ett grundläggande exempel på användning av KNN för klassificering:

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

# Ladda dataset
iris = load_iris()
X, y = iris.data, iris.target

# Dela upp data i tränings- och testmängd
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42)

# Initiera KNN-klassificerare med k=3
knn = KNeighborsClassifier(n_neighbors=3)

# Träna modellen
knn.fit(X_train, y_train)

# Gör förutsägelser
y_pred = knn.predict(X_test)

# Utvärdera noggrannhet
accuracy = accuracy_score(y_test, y_pred)
print(f"Accuracy: {accuracy:.2f}")

K-närmsta grannar (KNN) inom vetenskaplig forskning

K-närmsta grannar (KNN) är en grundläggande algoritm som används inom flera områden såsom multimedieinformationsåtervinning, datautvinning och maskininlärning, särskilt i samband med stora datamängder.

Anmärkningsvärda forskningsartiklar:

• “Approximate k-NN Graph Construction: a Generic Online Approach” av Wan-Lei Zhao m.fl.:
  Presenterar en effektiv metod för både approximativ k-närmsta grannar-sökning och grafkonstruktion. Artikeln visar en dynamisk och genomförbar lösning för att hantera olika dataskalor och dimensioner, med stöd för onlineuppdateringar som inte är möjliga i många befintliga metoder. Läs mer.

• “Parallel Nearest Neighbors in Low Dimensions with Batch Updates” av Magdalen Dobson och Guy Blelloch:
  Introducerar parallella algoritmer som kombinerar kd-träd och Mortonordning till en zd-trädstruktur, optimerad för lågdimensionell data. Författarna visar att deras metod är snabbare än existerande algoritmer och uppnår betydande hastighetsökningar med parallell bearbetning. Zd-trädet stödjer unikt parallella batch-dynamiska uppdateringar, vilket är först inom k-närmsta grannar-datastrukturer. Läs mer.

• “Twin Neural Network Improved k-Nearest Neighbor Regression” av Sebastian J. Wetzel:
  Utforskar ett nytt tillvägagångssätt för k-närmsta grannar-regression med hjälp av tvillingneuronätverk. Metoden fokuserar på att förutsäga skillnader mellan regressionsmål, vilket ger förbättrad prestanda jämfört med traditionella neuronätverk och k-närmsta grannar-regressionsmetoder på små till medelstora datamängder. Läs mer.