logo-IBA logo-MU © Institut biostatistiky a analýz INVESTICE DO ROZVOJE VZDĚLÁVÁNÍ logo-MU ANALÝZA A KLASIFIKACE DAT prof. Ing. Jiří Holčík, CSc. logo-IBA logo-MU © Institut biostatistiky a analýz VIII. ANALÝZA HLAVNÍCH KOMPONENT levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz ZAČÍNÁME þ þANALÝZA HLAVNÍCH KOMPONENT þPRINCIPAL COMPONENT ANALYSIS (PCA) þ þROZKLAD PODLE VLASTNÍCH ČÍSEL þSINGULAR VALUE DECOMPOSITION (SVD) þ þKarhunenova-Loevova transformace levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz ZAČÍNÁME þextrakce příznaků - hledání zobrazení (optimálního) Z, které transformuje původní m rozměrný prostor (obraz) na prostor (obraz) n rozměrný (m ³ n); þnalezení vhodné transformace – potřeba optimalizačního kritéria: èobrazy v novém prostoru budou aproximovat původní obrazy ve smyslu minimální střední kvadratické odchylky; èobrazy v novém prostoru budou minimalizovat odhad pravděpodobnosti chyby levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz ZAČÍNÁME þaby byla úloha řešitelná, hledáme zobrazení v oboru lineárních zobrazení þ levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz ZAČÍNÁME þaby byla úloha řešitelná, hledáme zobrazení v oboru lineárních zobrazení þ þJak poznáme lineární zobrazení? levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz ZAČÍNÁME þaby byla úloha řešitelná, hledáme zobrazení v oboru lineárních zobrazení þ þJak poznáme lineární zobrazení? þ levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz TEORIE þpředpokládejme, že je dáno K obrazů a nechť existuje m příznakových veličin, které tyto obrazy charakterizují. Tedy k-tý obraz je vyjádřen m rozměrným sloupcovým vektorem yk Î Y m, k=1,…,K. þaproximujme nyní kterýkoliv obraz yk lineární kombinací n ortonormálních vektorů ei (m ³ n) þ(J) þ levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz TEORIE þkoeficienty cki lze považovat za velikost i-té souřadnice vektoru yk vyjádřeného v novém systému souřadnic s bází ei, i=1,2,…,n, tj. platí þ þpoužijeme-li jako kritérium minimální střední kvadratické odchylky, pak je þ þ levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz TEORIE þpak pomocí dříve uvedených vztahů pro xk a cki dostaneme þ þ þstřední kvadratická odchylka pro všechny obrazy yk, k=1,…,K je þ þ þ þ þ levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz TEORIE þpak pomocí dříve uvedených vztahů pro xk a cki dostaneme þ þ þstřední kvadratická odchylka pro všechny obrazy yk, k=1,…,K je þ þ þ þ (je tedy závislá na volbě bázového systému ei) þ levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz TEORIE þdiskrétní konečný rozvoj podle vztahu (J) s bázovým systémem ei, optimálním podle kritéria minimální střední kvadratické chyby nazýváme diskrétní Karhunenův – Loevův rozvoj; þaby střední kvadratická odchylka podle výše uvedeného vztahu byla minimální, musí být odečítaná hodnota na pravé straně rovnice maximální. levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz TEORIE þmusíme tedy maximalizovat výraz þ þ þ je autokorelační matice řádu m. Protože je symetrická a semidefinitní, jsou její vlastní čísla λi, i=1,…,m, reálná a nezáporná a vlastní vektory vi, jsou buď ortonormální, nebo je můžeme ortonormalizovat (v případě násobných vlastních čísel). levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz TEORIE þuspořádáme-li vlastní čísla sestupně podle velikosti, tj. þλ1 ³ λ2 ³ … ³ λm ³ 0 þ a podle toho očíslujeme i odpovídající charakteristické vektory, lze dokázat, výe uvedený výraz dosahuje maxima, jestliže platí þei = vi, i=1,…,n þ a pro velikost maxima je þ levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz TEORIE þpro minimální střední kvadratickou odchylku tedy platí levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz TEORIE þv některých případech je vhodnější vektory yk před aproximací centrovat se střední hodnotou þ þ a místo s obrazem yk počítáme s jeho centrovanou verzí . þ Postup výpočtu se nemění, ale místo autokorelační matice používáme disperzní matici ve tvaru þ levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz GEOMETRICKÁ INTERPRETACE levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz PŘÍKLAD þPředpokládejme, že množinu obrazů Y 3 tvoří dva obrazové vektory y1 = (1, 1, 1)T a y2 = (2, 2, 2)T. Pomocí Karhunenova – Loevova rozvoje najděme novou souřadnicovou soustavu, která umožní popsat oba vektory s minimální střední kvadratickou odchylkou. þ levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz PŘÍKLAD þautokorelační matice: þ þ þ þvlastní čísla: þ þ þ(2,5 - l)3 + 2,53 + 2,53 – 3.2,52.(2,5 - l) = 0 þl3 – 7,5l2 = 0 Þ l1 = 7,5 a l2,3 = 0. þ þ þ levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz PŘÍKLAD þvlastní vektory: [k - l.I].x = 0. þPro l1 = 7,5 dostáváme lineární soustavu tří rovnic þ þ þ þkterá obsahuje pouze dvě lineárně nezávislé rovnice a tedy její parametrické řešení je þ þ þpro t = 1 je k vlastnímu číslu l1 vlastní vektor þx1 = (1, 1, 1)T, þ levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz PŘÍKLAD þpro l2,3 = 0 þ þ þ þx1 = - x2 - x3; x2 = t a x3 = u. þParametry t a u volíme tak, aby vlastní vektory byly navzájem ortogonální, þpro x2 např. t = 1 a u = 1, pak x2 = (-2, 1, 1)T a þpro x3 např. t = -1 a u = 1 a tedy x3 = (0, -1, 1)T. þ levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz Protože je nová souřadnicová soustava ortogonální, promítaly by se oba obrazové vektory při odstranění osy x1 do počátku. A konečně, vzhledem k tomu, že chybu popisu obrazových vektorů e2 vyjadřujeme pomocí střední kvadratické odchylky, je tato chyba rovna což je právě l1. PŘÍKLAD þProtože body y1 a y2 leží na vrcholech krychlí s hranami o délce 1, resp. 2 protilehlých k počátku, je jejich vzdálenost od počátku a tím i souřadnice ve směru x1 rovna délce prostorové úhlopříčky, tj. d1 = Ö3 v případě vektoru y1, resp. d2 = Ö12 v případě vektoru y2. þ Co by se stalo, kdybychom odstranili souřadnici x1? levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz VLASTNOSTI þpři daném počtu n členů rozvoje poskytuje ze všech možných aproximací nejmenší střední kvadratickou odchylku; þpři použití disperzní matice jsou transformované souřadnice nekorelované; pokud se výskyt obrazů řídí normálním rozložením zajišťuje nekorelovanost i jejich nezávislost; þvliv každého členu uspořádaného rozvoje se zmenšuje s jeho pořadím; þzměna požadavků na velikost střední kvadratické odchylky nevyžaduje přepočítávat celý rozvoj, nýbrž jen změnit počet jeho členů. levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz ROZDĚLENÍ DO TŘÍD þJak se změní podmínky, když obrazy y budou vymezeny jako části spojitého obrazového prostoru Y m? þVýskyt obrazů v jednotlivých klasifikačních třídách bude popsán podmíněnými hustotami pravděpodobnosti p(y|ωr), r=1,2,…,R a apriorní pravděpodobnost klasifikačních tříd bude P(ωr). þ V tom případě autokorelační matice bude levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz ROZDĚLENÍ DO TŘÍD þdisperzní matice þ þ þ kde þ þ nebo vztahem levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz ROZDĚLENÍ DO TŘÍD þ kde střední hodnota μ je vážený průměr středních hodnot všech tříd, tj. 002.jpg levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU © Institut biostatistiky a analýz þPříprava nových učebních materiálů þoboru Matematická biologie þje podporována projektem ESF þč. CZ.1.07/2.2.00/07.0318 þ„VÍCEOBOROVÁ INOVACE STUDIA MATEMATICKÉ BIOLOGIE“ INVESTICE DO ROZVOJE VZDĚLÁVÁNÍ logo-MU