Legközelebbi szomszéd osztályozók

Legközelebbi szomszéd osztályozók
Vissza	5. fejezet - Osztályozás: Alternatív módszerek	Előre

A 4.3. ábrán látható osztályozási keretrendszer egy kétlépcsős eljárást foglal magába: (1) egy induktív lépést, amelyben az adatokból egy osztályozási modellt alkotunk, és (2) egy deduktív lépést a modell tesztesetekre való alkalmazásához. A döntési fák és szabályalapú osztályozók mohó tanulók (eager learners), mivel ezeket egy olyan modell megtanulására tervezték, amely az input attribútumokat az osztálycímkére képezi le, amint a tanulóadatok rendelkezésre állnak. Egy ellenkező stratégia a modellezési folyamat késleltetése lenne addig, amíg nem kell osztályozni a teszteseteket. Az ezt a stratégiát alkalmazó módszereket lusta tanulóknak (lazy learners) nevezzük. A lusta tanulókra egy példa a Rote osztályozó (Rote classifier), amely az összes tanulóadatot memorizálja, és csak akkor osztályoz, ha a tesztpéldány attribútumai pontosan illeszkednek egy tanulóesetre. A módszer egy nyilvánvaló hátulütője az, hogy bizonyos tesztesetek nem osztályozhatók, mivel nem egyeznek meg a tanulóesetek egyikével sem.

A módszer rugalmasabbá tételének egy módja a teszteset attribútumaihoz viszonylag hasonló valamennyi tanulóeset megkeresése. Ezek az esetek, amelyeket legközelebbi szomszédoknak (nearest neighbors) nevezünk, felhasználhatók a teszteset osztálycímkéjének meghatározásához. A legközelebbi szomszédok használatának indoklását legjobban a következő mondás szemlélteti: ``Ha valami úgy totyog, mint egy kacsa, úgy hápog, mint egy kacsa és úgy néz ki, mint egy kacsa, akkor az valószínűleg egy kacsa.'' A legközelebbi szomszéd osztályozó minden egyes esetet egy adatpontként reprezentál egy d -dimenziós térben, ahol d az attribútumok száma. Egy adott teszteset esetén a 67. oldalon a 2.4. szakaszban leírt szomszédsági mértékek valamelyikével kiszámítjuk annak közelségét a tanulóhalmaz összes többi adatpontjához. Egy adott z eset k -legközelebbi szomszédja azt a k pontot jelenti, amelyek a legközelebb vannak z -hez.

5.7. ábra - Egy példány 1-, 2- és 3-legközelebbi szomszédja

Az 5.7. ábra a körök középpontjában lévő adatpont 1-, 2- és 3- legközelebbi szomszédját szemlélteti. Egy adatpontot a szomszédainak osztálycímkéje alapján osztályozunk. Abban az esetben, ha a szomszédoknak egynél több címkéje van, az adatpontot a legközelebbi szomszédok többségi osztályához rendeljük hozzá. Az 5.7. (a) ábrán az adatpont 1-legközelebbi szomszédja egy negatív eset. Ezért az adatpontot a negatív osztályhoz rendeljük hozzá. Ha három legközelebbi szomszéd van az 5.7. (c) ábrán látható módon, akkor a szomszédság két pozitív és egy negatív esetet tartalmaz. A többségi szavazási sémával az adatpontot a pozitív osztályhoz rendeljük hozzá. Holtverseny esetén (lásd az 5.7. (b) ábrát) az adatpont osztályozásához véletlenszerűen választhatjuk valamelyik osztályt.

A fent leírtak k helyes megválasztásának fontosságát hangsúlyozzák. Ha k túl kicsi, akkor a legközelebbi szomszéd osztályozó a tanulóadatokban jelenlevő zaj miatt hajlamos lehet a túlillesztésre. Másrészt viszont, ha k túl nagy, akkor a legközelebbi szomszéd osztályozó rosszul osztályozhatja a tesztpéldányt, mivel a legközelebbi szomszédok listája a szomszédságtól messzi adatpontokat is tartalmazhat (lásd az 5.87. ábrát).

5.8. ábra - k -legközelebbi szomszéd osztályozás nagy k esetén

Algoritmus

A legközelebbi szomszéd osztályozás egy magas szintű összefoglalását adjuk meg az 5.2. algoritmusban. Az algoritmus kiszámítja minden z=(x',y') teszteset és (x,y)∈D tanulóeset távolságát (vagy hasonlóságát) a D z legközelebbi szomszéd lista meghatározásához. Az ilyen számítás költséges lehet nagyszámú tanulóeset esetén. Azonban hatékony indexelési eljárások állnak rendelkezésre, amelyek csökkentik az egyes tesztesetek legközelebbi szomszédainak megkereséséhez szükséges számítási mennyiséget.

5.2. algoritmus. A k -legközelebbi szomszéd osztályozó algoritmus

1: Legyen k a legközelebbi szomszédok száma és D a tanulóesetek halmaza

2: for minden z=(x',y') tesztesetre do

3: Számítsuk ki a d(x',x) távolságot z és minden (x,y)∈D eset között

4: D z ⊆D , a z -hez legközelebbi k tanulóeset halmazának kiválasztása

5: y' = argmax v ∑ ( x i , y i )∈ D z I(v= y i )

6: end for

Ha megkaptuk a legközelebbi szomszéd listát, a tesztesetet a legközelebbi szomszédok többségi osztálya alapján osztályozzuk:

Többségi szavazás: y'= argmax v ∑ ( x i , y i )∈ D z I(v= y i ), (5.7)

ahol v egy osztálycímke, y i egy legközelebbi szomszéd osztálycímkéje, I(⋅) pedig az indikátorfüggvény, amely 1 értéket ad akkor, ha az argumentuma igaz, nullát egyébként.

A többségi szavazási módszernél minden szomszéd ugyanolyan hatással van az osztályozásra. Ez érzékennyé teszi az algoritmust k megválasztására, amint azt az 5.7. ábra mutatja. Egy mód k hatásának mérséklésére, ha minden egyes x i legközelebbi szomszéd hatását a távolságának megfelelően súlyozzuk: w i =1/d (x', x i ) 2 . Ennek következtében a z -től távoli tanulóeseteknek csekélyebb hatása van az osztályozásra a z közelében találhatókhoz képest. A távolsággal súlyozott szavazási séma használata esetén az osztálycímke az alábbi módon határozható meg:

Távolsággalsúlyozott szavazás: y'= argmax v ∑ ( x i , y i )∈ D z w i ×I(v= y i ). (5.8)

A legközelebbi szomszéd osztályozó jellemzői

A legközelebbi szomszéd osztályozó jellemzőit alább foglaljuk össze:

A legközelebbi szomszéd osztályozás része egy sokkal általánosabb, példányalapú tanulás (instance-based learning) nevű módszernek, amely konkrét tanulópéldányokat használ predikció végzéséhez anélkül, hogy az adatokból származó absztrakcióra (vagy modellre) lenne szüksége. A példányalapú tanuló algoritmusokhoz egy szomszédsági mérték szükséges a példányok hasonlóságának vagy távolságának meghatározásához, valamint egy osztályozási függvény, amely más példányokhoz közelsége alapján visszaadja egy tesztpéldány előrejelzett osztályát.
A lusta tanulók, mint például a legközelebbi szomszéd osztályozók, nem igényelnek modellépítést. A tesztesetek osztályozása azonban elég költséges lehet, mivel külön-külön kell kiszámolnunk a teszt- és a tanulóesetek közelségét. Ezzel szemben a mohó tanulók gyakran fordítják számítási erőforrásaik jelentős részét modellépítésre. A modell megépítése után a tesztesetek osztályozása már rendkívül gyors.
A legközelebbi szomszéd osztályozók lokális információk alapján végeznek előrejelzést, míg a döntési fák és a szabályalapú osztályozók a teljes input térre illeszkedő globális modellt próbálnak találni. Mivel a döntéshozatal lokálisan történik a osztályozás során, kis k értékek esetén a legközelebbi szomszéd osztályozók elég érzékenyek a zajra.
A legközelebbi szomszéd osztályozók tetszőleges formájú döntési határt elő tudnak állítani. Az ilyen határok a modellek egy rugalmasabb reprezentálását biztosítják a döntési fákhoz és szabályalapú oszályozókhoz képest, amelyek gyakran egyenesekkel leírható döntési határokra korlátozottak. A legközelebbi szomszéd osztályozók döntési határának nagy a változékonysága is, mivel a tanulóesetek összetételétől függenek. A legközelebbi szomszédok számának növelése csökkentheti az ilyen változékonyságot.
A legközelebbi szomszéd osztályozók hibás előrejelzéseket adhatnak, hacsak nem végezzük el a megfelelő előfeldolgozási lépéseket a szomszédsági mértéken és az adatokon. Tegyük fel például, hogy emberek egy csoportját akarjuk osztályozni olyan attribútumok alapján, mint például a (méterben mért) magasság és (fontban mért) testsúly. A magasság attribútum kis változékonyságú, 1,5 m és 1,85 m közötti, míg a testsúly attribútum 90 és 250 font között változhat. Ha nem vesszük figyelembe az attribútumok skáláját, akkor a testsúlykülönbségek erőteljesen befolyásolhatják a szomszédsági mértéket.