Házi feladat

Általános leírás

Törekedj arra, hogy szép, áttekinthető kódot írj! Úgy oldd meg a feladatokat, hogy függvényeket használsz a megoldáshoz! A felhasznált függvényekben ne történjen konzolra való kiírás!

Mindegyik feladatban nagyon fontos, hogy bár egyetlen inputfájlt kapsz, úgy írd meg a programod, hogy bármilyen, a feladatkiírásnak megfelelő inputfájllal működjön!

3.100-I Nőszirmok felismerése – K legközelebbi szomszéd

Egy botanikus olyan programot szeretne, amely egy nőszirom két mért adatából megbecsüli, melyik fajhoz tartozik. Ehhez ismert fajú virágok méréseit adja meg. A feladatod a K legközelebbi szomszéd módszerének, angolul K-nearest neighbors (KNN) algoritmusnak a megvalósítása.

1. Milyen adatokból dolgozunk?

A híres Iris-adathalmaz nőszirmok adatait tartalmazza. A három lehetséges faj: Iris-setosa (borzas nőszirom), Iris-versicolor (foltos nőszirom) és Iris-virginica (virginiai nőszirom). Az eredeti adatok négy méretet tartalmaznak; ebben a feladatban kizárólag a szirom hosszát és szélességét használjuk, mindkettőt centiméterben. Az angol oszlopnevekben ezek a petal length és petal width adatok; a sepal kezdetű adatokkal (ezek a csészelevelekről szólnak) most nem dolgozunk.

A mellékelt fájl a scikit-learn Iris-változatának két megfelelő oszlopát és fajcímkéjét tartalmazza: összesen 150 virágot, fajonként 50-et. Az eredeti sorrendet megtartottuk. Ezek a program által ismert, felcímkézett példák: a tanítóadatok.

Az input.txt UTF-8 kódolású, első sora fejléc. A mezőket pontosvessző választja el; a tizedeselválasztó pont. Minden további sor egy virágot ír le:

Sziromhossz;Sziromszelesseg;Faj
1.4;0.2;Iris-setosa
1.4;0.2;Iris-setosa
1.3;0.2;Iris-setosa

Ez csak a fájl eleje; a teljes fájl mindhárom faj adatait tartalmazza. A két méret pozitív valós szám. A faj a három felsorolt szöveg egyike. Nincs hiányzó adat. A sorok ismétlődhetnek: két azonos mérés két külön virágot is jelenthet, ezért ne távolítsd el az ismétlődéseket! Ugyanolyan mérési párhoz akár eltérő faj is tartozhat. Az algoritmus ne építsen arra, hogy a fájlban éppen 150 virág vagy fajonként 50 sor van! Legalább egy adatsor mindig szerepel a bemenetben.

2. Hogyan lesz egy virágból pont?

Jelölje x a szirom hosszát, y a szirom szélességét! Egy 4,8 cm hosszú és 1,8 cm széles sziromhoz a (4,8; 1,8) pontot rendeljük. Ez nem a növény helye a kertben, hanem a két mért tulajdonság helye egy koordináta-rendszerben.

A setosa pontjai elkülönülő csoportot alkotnak. A versicolor és virginica pontjai részben átfedik egymást. A közeli pontok tehát gyakran ugyanahhoz a fajhoz tartoznak, de nem mindig. Erre a hasonlóságra épít a KNN. Az új virág helyét is felrajzolhatnánk; azt vizsgáljuk, mely ismert virágok helyezkednek el hozzá közel.

Talált online eloszlásábra: Petal length against petal width, by species. A fenti, magyar feliratú ábra saját szerkesztésű, és pontosan a mellékelt fájlt mutatja.

3. Mit jelent a „legközelebbi”?

Egyetlen adatnál, például jegyátlagnál, elég volt két szám különbségének abszolút értéke. Itt két adat eltérését kell egyszerre figyelembe venni. Legyen az új virág pontja P = (x₁; y₁), egy ismert virágé Q = (x₂; y₂)!

Menjünk P-ből először vízszintesen Q alá vagy fölé, majd függőlegesen Q-ig! A két lépés merőleges egymásra. A megtett vízszintes és függőleges szakasz a derékszögű háromszög két befogója, a P-t Q-val közvetlenül összekötő szakasz pedig az átfogó.

1. A vízszintes befogó hossza: a = |x₂ − x₁|.
2. A függőleges befogó hossza: b = |y₂ − y₁|.
3. A Pitagorasz-tétel szerint: d² = a² + b².
4. A távolság nemnegatív, ezért: d = √(a² + b²).

d(P, Q) = √((x₂ − x₁)² + (y₂ − y₁)²)

Ez az euklideszi távolság: a két pontot összekötő egyenes szakasz hossza. A négyzetre emelés miatt a képletben már nem szükséges külön abszolút értéket venni: egy negatív és az ellentettje ugyanazt a négyzetet adja. Az sem változtat az eredményen, ha P és Q sorrendjét felcseréljük.

Számoljunk végig egy példát! Az új mérés P = (4,0; 1,0), az ismert mérés Q = (4,3; 1,4). A hosszúságeltérés 0,3 cm, a szélességeltérés 0,4 cm. Így:

d = √((4,3 − 4,0)² + (1,4 − 1,0)²)
= √(0,3² + 0,4²) = √(0,09 + 0,16) = √0,25 = 0,5 cm

Nem a két eltérést adjuk össze: a 0,3 + 0,4 = 0,7 a két befogón vezető út hossza lenne. A feladatban az átlós, közvetlen távolság kell. Programozáskor a négyzetet például dx * dx, a gyökvonást C#-ban Math.Sqrt(...) adja. A ^ jel C#-ban nem hatványozás!

4. A K legközelebbi szomszéd algoritmusa

A K azt mondja meg, hány közeli ismert virágot kérdezünk meg. A virágok nem fizikailag szomszédok: a mért tulajdonságaik alapján azok. Minden kiválasztott virág egy szavazatot ad a saját fajára.

1. Olvasd be az ismert példákat! Minden virágnál tárold a két méretet és a fajt.
2. Kérd be az új virág két méretét és K-t! Az új virág faját nem kérjük be: éppen ezt szeretnénk megbecsülni.
3. Számíts távolságot minden ismert virághoz! Minden sorhoz külön d érték tartozik.
4. Rendezd az ismert virágokat a kiszámított távolság szerint növekvően! Az elején lesznek a leginkább hasonló mérések. A méreteket, fajt és távolságot együtt mozgasd!
5. Vedd az első K rekordot! Csak ezek szavaznak. Nem az első K sort vesszük az eredeti fájlból, és nem fajonként K szomszédot keresünk.
6. Számold meg a fajonkénti szavazatokat! A legtöbb szavazatot kapó faj lesz a becslés. Ehhez nem szükséges a szavazatok több mint felét megszereznie.

Például ha K = 5 mellett a szomszédok fajai rendre versicolor, virginica, virginica, versicolor, virginica, akkor a virginica 3, a versicolor 2 szavazatot kap. A becsült faj virginica. A közelség a kiválasztásnál számít; ebben a változatban mind az öt kiválasztott szomszéd szavazata egyformán egyet ér.

Ha az új mérés megegyezik egy ismert méréssel, a távolság 0. Ez teljesen helyes. A 0 távolságú mintákat is a szokásos szabály szerint kezeljük; nem osztunk a távolsággal, és nem állunk meg automatikusan az első ilyen mintánál.

5. Holtversenyek – a feladat pontos szabályai

Kétféle egyezés fordulhat elő. Ezekre a következő szabályokat használd:

• Azonos távolság: a bemeneti fájlban előbb szereplő virág kerüljön előre. Ehhez tárold az adatsorok 1-től kezdődő sorszámát is; a fejléc nem számít adatsornak. Pontosan K szomszédot válassz akkor is, ha a K-adik helyen több azonos távolságú virág van.
• Azonos szavazatszám: a legtöbb szavazatot kapó fajok közül az nyerjen, amelynek a legközelebbi kiválasztott szomszédja előrébb szerepel a rendezett listában. Vagyis a rendezett K elemű listában az első olyan virág faja nyer, amely a szavazatszám szerinti holtversenyben részt vesz.

A páratlan K nem garantál egyértelmű eredményt három faj esetén: öt szomszéd szavazatai például 2–2–1 arányban is megoszolhatnak. A fenti holtversenyszabályok a feladatban választott szabályok; más KNN-megvalósítások máshogyan is dönthetnek.

6. Megoldandó feladatok

Minden részfeladat előtt írd ki a sorszámát! A KNN-t saját függvényekkel valósítsd meg, kész gépi tanulási osztályozót ne használj! A numerikus adatokhoz használj valós típust, például double-t.

1. Olvasd be a fájlt, és írd ki az ismert virágok teljes számát, valamint a fajonkénti darabszámokat!
2. Kérd be egy ismeretlen nőszirom sziromhosszát és sziromszélességét centiméterben, valamint K értékét! A méretek pozitív valós számok legyenek, K pedig 1 és a beolvasott virágok száma közötti egész szám. Hibás érték esetén kérd be újra az adott adatot! A konzolon és a fájlban is tizedespontot használunk; a program működése ne függjön a gép területi beállításától.
3. Készíts függvényt, amely két mérési pár euklideszi távolságát adja vissza! Számítsd ki az új virág távolságát minden ismert virágtól!
4. Rendezéssel válaszd ki a K legközelebbi szomszédot! Írd ki távolság szerint rendezve az adatsorszámukat, a két méretüket, fajukat és távolságukat! A távolságot négy tizedesjeggyel jelenítsd meg, de a rendezést és a kiválasztást kerekítetlen értékekkel végezd!
5. Írd ki mindhárom faj szavazatszámát, majd a becsült fajt! A szavazás eredményét külön függvény határozza meg a kiválasztott szomszédokból.
6. Ugyanarra az új virágra végezd el a besorolást K = 1, 3, 5 és 7 mellett is, azokkal az értékekkel, amelyek nem nagyobbak a fájl adatsorainak számánál! Írd ki K-t, a becsült fajt és a győztes faj szavazatszámát! Minden kísérletben ugyanazt a tanítóhalmazt használd; az új virágot ne add hozzá! A távolságokat nem szükséges újraszámolni és a listát újrarendezni.

7. Ellenőrző példa a mellékelt teljes fájlhoz

Új virág: sziromhossz = 4.8 cm, sziromszélesség = 1.8 cm, K = 5. Az első öt szomszéd:

Szavazatok: setosa 0, versicolor 1, virginica 4. A becslés Iris-virginica. K = 1 mellett viszont a 71. adatsor dönt, így a becslés versicolor. Ez jól mutatja, hogy ugyanaz a két mérés nem mindig határozza meg egyértelműen a fajt, és a választott K is befolyásolhatja az eredményt.

8. Mit érdemes megérteni a módszerről?

Kicsi K: nagyon helyi döntést hozunk; K = 1 esetén egyetlen példa dönt, ezért egy szokatlan vagy hibás mérés is nagy hatással lehet. Nagy K: több példa szavaz, de távolabbi, kevésbé hasonló virágok is bekerülnek. Ha K az összes minta száma, már minden virág szavaz, és a közeli környezet szerepe elvész.

A fajneveket ismerjük a tanítóadatoknál, ezért ez felügyelt osztályozás: példákból következtetünk egy új példány címkéjére. Nem a virágok csoportjait fedezzük fel címkék nélkül, és nem az átlagos sziromméretet keressük. A KNN egyszerű változata megőrzi a példákat, és az új virág megadásakor hasonlít hozzájuk.

A program becslést ad, nem bizonyítja a valódi fajt. A 4/5 szavazat például a kiválasztott minták aránya, nem igazolt 80%-os valószínűség. Ha egy új mérés messze esik minden ismert virágtól, a program akkor is kiír egy fajt, de ez a döntés kevésbé megalapozott lehet. Ebből a három címkéből választ; egy teljesen más növényfajt nem tud önállóan felismerni.

Ebben a feladatban a két nyers, centiméterben megadott adat euklideszi távolságát használjuk, átskálázás nélkül. A nagyobb számszerű eltérés jobban növeli a távolságot. Más mértékegységek vagy nagyon eltérő adattartományok esetén a skálázást külön meg kellene gondolni; még az azonos mértékegység sem jelenti azt, hogy a két tulajdonság szóródása azonos.

A pontosság tisztességes vizsgálatához külön, a keresésben nem használt, de ismert fajú tesztvirágokra volna szükség. Egy tanítópont önmagához mért 0 távolsága nem bizonyít jó általánosítást. Ez most nem külön programozási részfeladat, de segít helyesen értelmezni az eredményt.

Források és ábrák

• UCI: Iris – az adathalmaz leírása.
• scikit-learn: Iris plants dataset; a mellékelt fájl a telepített scikit-learn Iris-változatából készült, a sziromoszlopok kiválasztásával. Egyes történeti Iris-változatok néhány adatban eltérnek; az ellenőrző példa a mellékelt fájlra vonatkozik.
• scikit-learn: Nearest Neighbors Classification.
• Talált online pontdiagram a két sziromadatról.

A beágyazott pontdiagram és Pitagorasz-ábra saját szerkesztésű. Az ábrák az oldal részei, megjelenítésükhöz nincs szükség internetre.