Algoritmen til nærmeste naboer ( k-NN) er en metrisk algoritme til automatisk objektklassificering eller regression .
I tilfælde af brug af metoden til klassificering tildeles objektet den klasse, der er den mest almindelige blandt naboerne til dette element, hvis klasser allerede er kendte. I tilfælde af brug af metoden til regression tildeles objektet gennemsnitsværdien af objekterne tættest på det, hvis værdier allerede er kendte.
Algoritmen kan anvendes på prøver med et stort antal attributter (flerdimensionelle). For at gøre dette, før du anvender, skal du definere afstandsfunktionen ; den klassiske version af en sådan funktion er den euklidiske metrik [1] [2] .
Forskellige attributter kan have forskellige intervaller af repræsenterede værdier i prøven (for eksempel er attribut A repræsenteret i intervallet fra 0,1 til 0,5, og attribut B er repræsenteret i intervallet fra 1000 til 5000), derefter er afstandsværdierne kan være meget afhængig af attributter med større intervaller. Derfor er dataene normalt underlagt normalisering. I klyngeanalyse er der to hovedmåder at normalisere data på: minimax normalisering og Z-normalisering.
Minimax normalisering udføres som følger:
,i dette tilfælde vil alle værdier ligge i området fra 0 til 1; diskrete binære værdier er defineret som 0 og 1.
Z-normalisering:
hvor er standardafvigelsen ; i dette tilfælde vil de fleste af værdierne falde inden for området .
Nogle væsentlige attributter kan være vigtigere end andre, så en vis vægt kan tildeles hver attribut (f.eks. beregnet ved hjælp af en testprøve og variansfejloptimering). Således vil hver attribut blive tildelt en vægt , så værdien af attributten falder inden for området (for normaliserede værdier ved brug af minimax-metoden). For eksempel, hvis en attribut tildeles en vægt på 2,7, vil dens normaliserede vægtede værdi ligge i området
Med en vægtet metode tages der ikke kun hensyn til antallet af bestemte klasser, der faldt i området, men også deres afstand fra den nye værdi.
For hver klasse bestemmes en nærhedsscore:
,hvor er afstanden fra den nye værdi til objektet .
Hvilken klasse har en højere nærhedsværdi, den klasse tildeles det nye objekt.
Ved hjælp af metoden kan du beregne værdien af en af attributterne for det klassificerede objekt baseret på afstandene fra objekterne, der faldt ind i området og de tilsvarende værdier af den samme attribut for objekterne:
,hvor er det -th objekt, der faldt ind i området, er værdien af attributten for det givne objekt , er det nye objekt og er -th attribut for det nye objekt.
Machine learning og data mining | |
---|---|
Opgaver | |
At lære med en lærer | |
klyngeanalyse | |
Dimensionalitetsreduktion | |
Strukturel prognose | |
Anomali detektion | |
Grafer sandsynlighedsmodeller | |
Neurale netværk | |
Forstærkende læring |
|
Teori | |
Tidsskrifter og konferencer |
|