Számítástudományi és Információelméleti Tanszék

Témakiírás

A legközelebbi társ módszer komplexitási problémái

A statisztikus alakfelismerés egyik legelterjedtebb módszerénél úgy történik egy ismeretlen kategóriájú alakzat beazonosítása, hogy egy adott n elemszámú halmazban, a tananyagban, kiválasztják a hozzá egy adott d metrika szerint legközelebb álló elemet. A keresés műveletének költségeit csökkenteni lehet, ha a tananyagot a „felesleges” elemekkel megritkítjuk, illetve a tananyagból kisebb elemszámú prototípus halmazt szerkesztünk az osztályozáshoz. Az osztályozás költségei úgy is csökkenthetők, ha kizárási kritériumokat alkalmazunk. Ilyenkor a legközelebbi társ meghatározásához n metrikaszámolásnál jóval kevesebb művelet is elegendő. A témakörhöz tartoznak még olyan eljárások is, amelyek adott tananyaghoz segítenek kiválasztani a legalkalmasabb d távolságfüggvényt.

Irodalom:

1. Devroye, L., Györfi, L., Lugosi, G.: A Probabilistic Theory of Pattern Recognition, (Springer-Verlag, New York), (1996)
2. Duda, R. O., Hart, P.: Pattern classification and Sceene Analysis, (Wiley, New York), (1974)
3. Fukunaga, K.: Introduction to Statistical Pattern Recognition, (Academic press, New York), (1976)
4. Ketskeméty, L.: A tananyag előfeldolgozásai a legközelebbi társ módszerhez, P.h.D. értekezés, http://www.szit.bme.hu/~kela/ketskemety.pdf , (2003)

Szükséges nyelvtudás: angol.

Dr. Ketskeméty László
egyetemi adjunktus
28-97
kela@szit.bme.hu