PALMA junior
Úloha o triedičke ovocia

Autorské riešenie
[stiahni triedicka_riesenie.py]

• Počet riešiteľov: 27 /  =  %

• Úspešnosť riešenia: 5,27 / 7 = 75 %

Toto je zaujímavá úloha, pretože na základe niekoľkých konkrétnych prípadov chceme naučiť počítač rozhodovať sa - klasifikovať neznáme ovocie.

Aby sme lepšie pochopili, ako má klasifikácia fungovať, pozrime sa bližšie na samotný dataset. Je to zoznam trojíc: [hmotnosť, farba, druh ovocia]. Z pohľadu na tento dataset nevidno žiadne zaujímavé vzťahy. Ak si však dáta vizualizujeme pomocou grafu, význam dát sa ukáže.

Z grafu vidíme, že jednotlivé kusy ovocia rovnakého druhu sa nachádzajú vedľa seba. Majú podobnú hmotnosť a aj podobnú farbu. Ak do grafu vložíme nejaké neznáme ovocie, vieme na základe jeho blízkeho okolia určiť, ktorý druh ovocia to pravdepodobne bude.

Z pohľadu na graf môžeme usudzovať, že neznáme ovocie (sivý krúžok) je buď malá nezrelá slivka alebo veľká prezretá čerešňa. Pre konečné rozhodnutie vyberieme nejaký, vopred určený počet bodov z grafu, ktoré sú k neznámemu ovociu najbližšie. To ovocie, ktoré bude v tomto výbere zastúpené najviac, určí druh neznámeho ovocia. Ak vyberieme 10 najbližších bodov, prevládajú medzi nimi slivky. Neznáme ovocie preto kategorizujeme ako slivku.

Samotná implementácia tohto postupu môže vyzerať nasledovne: 

def vypocitaj_odlisnost(ovocie1, ovocie2):
    rozdiel_hmotnost = ovocie1[0] - ovocie2[0])
    rozdiel_farba = ovocie1[1] - ovocie2[1]
    vzdialenost = (rozdiel_hmotnost ** 2 + rozdiel_farba ** 2) ** 0.5
    return vzdialenost

def urci_ovocie(data, nezname_ovocie, n):
    odlisnosti = []
    for ovocie in data:
        odlisnost = vypocitaj_odlisnost(ovocie, nezname_ovocie)
        odlisnosti.append((odlisnost, ovocie[2]))
    odlisnosti.sort()
    n_tica = [odlisnost[1] for odlisnost in odlisnosti[:n]]

    # najdenie najpocetnejsieho ovocia verzia 1
    naj_pocet = 0
    naj_ovocie = ''
    for ovocie in ['hruška', 'jablko', 'marhuľa', 'čerešňa', 'slivka']:
        aktualny_pocet = n_tica.count(ovocie)
        if aktualny_pocet > naj_pocet:
            naj_ovocie = ovocie
            naj_pocet = aktualny_pocet

    # najdenie najpocetnejsieho ovocia verzia 2
    pocty_ovoci = {}
    for ovocie in n_tica:
        pocty_ovoci[ovocie] = 1 + pocty_ovoci.get(ovocie, 0)
    naj_pocet = 0
    naj_ovocie = ''
    for ovocie, pocet in pocty_ovoci.items():
        if pocet > naj_pocet:
            naj_pocet = pocet
            naj_ovocie = ovocie

    # vratenie vysledku
    return naj_ovocie 

Vytvorili sme si pomocnú funkciu vypocitaj_odlisnosti, ktorá vypočíta odlišnosť dvoch ovocí ako vzdialenosť ich pozícii v grafe, kde na osi x je hmotnosť ovocia a na osy y jeho farba. Tu sme využili Pytagorovu vetu.

Vo funkcii urci_ovocie najskôr vypočítame pre každé ovocie z datasetu jeho odlišnosť od neznámeho ovocia. Zoznam týchto odlišností si usporiadame a do n-tice vyberieme n tých názvov ovocí, ktoré sú k neznámemu ovociu najpodobnejšie.

Posledným krokom je zistiť, ktorý názov sa v tejto n-tici vyskytuje najčastejšie.  Najčastejšie sa vyskytujúci názov v n-tici určí aj druh neznámeho ovocia.

Všimnime si dve rôzne verzie pre nájdenie najpočetnejšieho ovocia v n-tici. V prvej verzii musíme vopred vedieť, aké druhy ovocí uvažujeme a pre každý druh spočítame počet jeho výskytov v n-tici. V druhej verzii názvy uvažovaných ovocí zisťujeme priebežne a ich počty uchovávame v slovníku.

Myšlienka, ktorú sme aplikovali v automatickej linke na rozpoznávanie ovocia má svoje pomenovanie: algoritmus k-najbližších susedov. Je to algoritmus strojového učenia, ktorý sa používa na rozpoznávanie vzorov.

Tento algoritmus je citlivý na to, v akom rozsahu sú jednotlivé merané hodnoty. Ak by sme napríklad hmotnosť merali v gramoch a farbu ako číslo z intervalu <0, 1>, hmotnosť by bola takmer výlučne určujúcim faktorom pri klasifikácii. Preto aj v našom príklade sme parametre (hmotnosť, farba) nastavili tak, aby ich hodnoty boli v približne rovnakom rozsahu. 

Problém môže spôsobiť aj to, ak do datasetu zaradíme nejaký nepodstatný parameter, napr. vzdialenosť dodávateľa od závodu. Algoritmus nedokáže odlíšiť nepodstatné parametre od podstatných. Preto sme v tejto úlohe zvolili len tie parametre, ktoré sú podstatné pre rozlíšenie druhu ovocia.

S počtom prvkov v n-tici je tiež možné experimentovať. Príliš malá hodnota (napr. 1) môže spôsobiť, že rozpoznávanie bude príliš nestabilné. Ak bude v datasete jeden chybný bod a my klasifikujeme neznámy prvok vedľa neho, výsledok bude chybný. Nestabilná by bola aj kategorizácia ovocí, ktoré by boli na pomedzí medzi dvoma skupinami (napr. hrušky a jablká). Na druhej strane, príliš veľká hodnota spôsobí to, že začneme ignorovať menšinové zoskupenia a veľkú časť neznámych vzoriek budeme klasifikovať ako najpočetnejší prípad v datasete. V praxi môžeme začať hodnotou, ktorá je rovná odmocnine z počtu prvkov datasetu. V našom prípade má dataset 100 prvkov, preto do n-tíc budeme zaraďovať 10 najbližších susedov. Následne môžeme testovať ako a či sa zvýši úspešnosť rozpoznávania pre väčšie alebo menšie hodnoty.

Vaše zaujímavé riešenia a najčastejšie chyby

Táto úloha nebola ťažká na pochopenie. Aj keď sa úloha dala vyriešiť pomocou základných riadiacich (cykly, podmienky, funkcie) a dátových (zoznamy) štruktúr, niektorí z vás siahli aj po slovníkoch, množinách alebo moduloch jazyka Python. Vo všeobecnosti to nie je problém a skôr to vítame ak to použijete rozumne a efektívne. Všimli sme si však, že dátové štruktúry nevyužívate vždy efektívne, čo je škoda. Dátové štruktúry majú svoje metódy. Ak sa ich naučíte používať efektívne, ušetria vám množstvo programátorskej práce.