K-nærmeste naboer

K-nærmeste-naboer (KNN) er en klassifikationsalgoritme baseret på tanken om, at to dataprøvers numeriske værdier vil være tæt på hinanden, hvis de er fra samme klasse. K'et i navnet hentyder til det antal naboer, man tager med i klassificeringen. Kigger man eksempelvis på de nærmeste 3 naboer, er det en 3-nærmeste-naboer klassifikator.

Algoritme

Eksempel på KNN. Der søges at klassificere den grønne cirkel til en af klasserne symboliseret ved enten den blå firkant eller røde trekant. Ved: 1NN fås, at den tilhører rød trekant. 3NN fås, at den tilhører rød trekant. 5NN fås, at den tilhører blå firkant.

Til klassificering af en dataprøve beregnes for hver dataprøve i datasættet den euklidiske (Eller andre former) distance. For de k dataprøver, hvor distancen er lavest, vælges den klasse, hvor der er flest forekomster i de nærmeste dataprøver.

Valg af k

Ved valg af et lavt k vil klassifikatoren være følsom overfor støj, hvilket især kan ses i meget støjfulde datasæt. Vælges et højt k kan det risikeres, at der ofte vil vælges den klasse, som der er flest af i datasættet.

Valget af det optimale kt kan ikke foretages deterministisk. Der findes dog algoritmer til at finde gode løsninger. Eksempelvis findes cross-validation.

Vægtning af data

For at overkomme problemet med, at KNN er modtagelig overfor støj, kan man vægte distancen, således at de dataprøver der minder mest om den, man ønsker at klassificere, vil vægte mere end de, der minder mindre om den, man klassificerer. En hyppigt benyttet metode er at vægte distancen som det inverse: vægt = 1/distance.

Dette ændrer algoritmen til, at man lægger alle vægtene sammen for derefter at tage den, der har højest summeret vægt.

Problemer med KNN

• KNN er en doven klassifikator. Dette vil sige, at hele datasættet skal gennemgås hver gang, der skal klassificeres, hvor andre algoritmer lærer mønstre.
• Ved mange dimensioner falder kvaliteten af KNN. Antager man, at man har 10 datafeatures, der ligger i intervallet 0-9, vil der være 10 billioner mulige kombinationer af dataene. I sådan et tilfælde kan man overveje en dimensionalitetsreduktion, før man benytter KNN.

Eksterne henvisninger

• Implementering af KNN i C++.
• Implementering i Java (Webside ikke længere tilgængelig).