Příprava a klasifikace biomedicínských dat. Marcel Jiřina

Příprava a klasifikace biomedicínských dat Marcel Jiřina

Osnova

Příprava dat Klasifikace a regrese Hodnocení kvality klasifikace (regrese) Vlastnosti dat ve vysocedimenzionálních prostorech

Příprava dat

Analýza biomedicínských dat

Problémy při zpracování biomedicínských dat

Dat bývá většinou málo Zastoupení tříd není vyvážené Častý výskyt chybějících údajů

Důležitost

Špatná klasifikace může vést k závažným důsledkům

Proto je třeba věnovat zvýšenou pozornost předzpracování dat

např. chybná klasifikace závažného onemocnění výběr dat, normalizace a transformace dat, výběr příznaků (proměnných), problém chybějících nebo špatných dat

a následnému vyhodnocení získaných výsledků

Příprava dat

Úprava dat do standardního formátu datové množiny

Předzpracování dat

Normalizace

lineární normalizace

xnorm = a min + (a max

x − xmin − a min ) xmax − xmin

normalizace na nulový průměr a jednotkový rozptyl

xnorm =

střední hodnota µ směrodatná odchylka

x−µ

σ

σ

nelineární změna měřítka

x norm

x = k 10


Výpočet příznaků

jaké příznaky budeme počítat je na nás vycházíme z charakteru řešené úlohy čím více příznaků, tím lépe (máme větší možnost z nich vybírat ty vhodné) některé příznaky nemusíme počítat, ale získáme je přímo měřením


Výběr příznaků

Ze souboru příznaků počítaných pro každý vzor vybíráme ty příznaky, které jsou maximálně „diskriminující“, tj. jsou důležité pro rozlišení vzorů.

Korelace Statistické testy Entropie Dopředný výběr Zpětný výběr Genetické algoritmy

Korelace

Pearsonův korelační koeficient

ρ X ,Y =

cov( X , Y )

σ Xσ Y

=

E{( X − µ X )(Y − µY )}

σ Xσ Y

Korelační a kovarianční matice rozptyl (σ ) 2

ρ ( X1, X 2 ) L ρ ( X1, X n )  1  ρ ( X , X )  ρ 1 ( X , X ) 2 1 2 n  ρ=   M O M   1 ρ ( X n , X1 ) ρ ( X n , X 2 ) L 

 D ( X 1) C ( X , X ) 2 1 C =   M  C ( X n , X 1 )

C ( X 1, X 2 ) D(X 2) C(X n, X 2)

L O L

C ( X 1, X n )  C ( X 2 , X n )   M  D(X n) 

Korelace

Korelace = vzájemný lineární vztah mezi veličinami +1 značí zcela přímou závislost, −1 značí zcela nepřímou závislost

Metody výběrů příznaků

Používají se pro výběr vhodných vstupů (příznaků) z množiny všech možných dostupných vstupů. Vesměs jsou postaveny na principu výběru různých kombinací vstupů a vyhodnocení jejich vhodnosti. Pro každou vybranou množinu vstupů se provede odhad úspěšnosti, jakou by bylo možné s těmito vstupy dosáhnout.

Dopředný výběr

Vybereme jeden (např. první) příznak a ve všech vzorech nahradíme jeho hodnoty průměrem hodnot daného příznaku Takto sestavená množina je předložena jednoduchému klasifikátoru resp. regresnímu algoritmu k natrénování Takto natrénovaný klasifikátor/regresní algoritmus je ohodnocen z hlediska dosažené kvality. Celý postup zafixování jednoho vybraného příznaku je opakován pro všechny příznaky. Ze všech ohodnocení (chyb) vybereme tu nejmenší a jí odpovídající příznak. Čím větší je chyba, tím hodnotnější je příslušný příznak (významně se podílí na rozhodování), a proto ho už nadále ponecháme jako vybraný. Celý proces opakujeme pro zbývající příznaky. Ze všech zpracovávaných kombinací vstupů vybereme nakonec tu nejlepší. Zpětný výběr probíhá obdobně, ale „odzadu“. Nemusíme ale dosáhnout stejných výsledků!

Dopředný a zpětný výběr s využitím lineární regresní rovnice

Myšlenka

Pokud použijeme všechny proměnné (příznaky), dostaneme velmi přesnou regresní rovnici, ale výpočetně to bude velmi náročné. Naopak pokud bude proměnných málo, bude úloha výpočetně jednoduchá, ale ztratíme přesnost regrese. Hledáme tedy kompromis mezi těmito dvěma krajními extrémy.


Dopředný výběr

Při dopředném výběru začínáme s minimální regresní rovnicí, do které postupně přidáváme jednotlivé proměnné tak dlouho, až dosáhneme uspokojivé kvality. Pořadí v jakém proměnné přidáváme můžeme určit např. s pomocí korelačních koeficientů jako míry důležitosti proměnných, které nebyly do rovnice ještě zahrnuty


Dopředný výběr - postup

Nejprve vybereme ten příznak, který je nejvíce korelován s výstupem Sestavíme odpovídající lineární regresní rovnici. Zaznamenáme reziduální hodnoty, které jsou dány rozdílem mezi skutečnými danými hodnotami a touto lineární regresní rovnicí. Za další vhodný příznak (ze všech zbývajících příznaků) vybíráme ten, který je nejvíce korelován s těmito reziduálními hodnotami. Celý proces opakujeme tak dlouho, dokud nedosáhneme požadované kvality.


Zpětný výběr - postup

Vycházíme z lineární regresní rovnice, která byla spočítána na základě všech vstupů (příznaků). Spočítáme hodnoty částečných F-testů pro každou proměnnou a to tak, že každou tuto proměnnou uvažujeme jako by vstupovala do lineární regresní rovnice jako poslední. Nejmenší hodnota těchto částečných F-testů je porovnána s daným předem stanoveným prahem (hladinou významnosti) a pokud je pod tímto prahem, pak je vyřazena z dalších výpočtů. Přepočítáme lineární regresní rovnici na základě zbývajících proměnných, tj. vypočteme hodnoty částečných F-testů a ty následně porovnáme s prahem. Celý proces opakujeme tak dlouho dokud nezůstanou všechny vypočítané hodnoty částečných F-testů nad zvoleným prahem.

Výběr příznaků pomocí genetických algoritmů

GA jsou optimalizační algoritmy inspirované evolučními principy živých organizmů V GA se vychází z počáteční populace, se kterou se provádí výběr, křížení a mutace GA vybírá z populace nejlépe hodnocené jedince pomocí tzv. fitness funkce a s nimi provádí dále křížení a mutaci s cílem získat ještě lepší jedince Mutace zajišťuje rozmanitost řešení, ale její přehnaně časté použití může poškodit dobrá řešení. Křížení kombinuje části jedinců s cílem získat lepšího jedince na základě výběru lepších částí obou křížených jedinců. Křížením lze vytvořit nové jedince s novými vlastnostmi.

Příprava dat

Rozdělení dat na trénovací, validační a testovací

Trénovací mn. – známý výstup → učení klasifikátoru Validační mn. – známý výstup, ale klasifikátoru ho neposkytneme (porovnání výsledku klasifikace s reálným výstupem) → validace Testovací mn. – známý výstup, měříme úspěšnost klasifikátoru

Nejčastěji rozdělení dostupných dat (vzorů) v poměru 2:1:1.

Rozpoznávání a klasifikace

Problém přeučení (overfitting) – přehnaný důraz na přesnost


Křížová validace (cross-validation)

extrém: leave-one-out

Bootstrapping – výběr (vzorkování) s opakováním

Vyrovnávání skupin

Obecně je snaha mít všechny skupiny stejně početné

Vynechání nadpočetných vzorů Vygenerování nových vzorů

Hodnocení kvality klasifikace (regrese)

Hodnocení kvality klasifikace

ROC křivka

Receiver Operating Characteristics z průběhu resp. plochy pod vynesenou křivkou můžeme usuzovat na kvalitu klasifikace resp. klasifikátoru senzitivita =

pocet TP pocet TP + pocet FN

„TP“

„FP“ specificita =

pocet TN pocet TN + pocet FP

Hodnocení kvality klasifikace

Citlivost (Sensitivity) = TP / (TP + FN), Specificita (Specificity) = TN / (FP + TN), Pozitivní hodnotu predikce (Positive predictive value) = TP / (TP + FP), Negativní hodnotu predikce (Negative predictive value) = TN / (FN + TN), Efektivita (Efficiency) = (TP + TN) / (TP + TN + FP + FN)

TP – true positive, TN – true negative, FP – false positive, FN – false negative

http://www.anaesthetist.com/mnm/stats/roc/Findex.htm

Graf zisku (Gains Chart) a graf navýšení (Lift Chart)

Zisk/navýšení je mírou dokonalosti modelu. Navýšení (Lift) je vyjádřeno jako poměr mezi výsledky získanými s pomocí modelu a bez něj. Kumulativní graf zisku a graf navýšení jsou vizuální prostředky pro ohodnocení kvality modelu. Oba grafy obsahují základní úroveň (baseline). Čím větší je plocha mezi základní úrovní a modelem (zisk/navýšení), tím je model lepší.


Příklad: Chceme obeslat naše zákazníky a zjistit jejich reakce. Naším úkolem je zjistit výhodnost oslovení zákazníků s ohledem na jejich reakce. Víme, že v průměru 20 % oslovených zákazníků bude reagovat na naši nabídku. Pokud oslovíme 100000 zákazníků, získáme reakce od 20000 zákazníků.


Jsme ale schopni sestavit přesnější (predikční) model a to uspořádat zákazníky podle jejich vůle reagovat:

procentuální množství reakcí

Graf zisku (Gains Chart)

základní úroveň (baseline)

procento kontaktovaných zákazníků

navýšení

Graf navýšení (Lift Chart)

základní úroveň (baseline) procento kontaktovaných zákazníků

Klasifikace dat


Dílčí kroky při klasifikaci dat

předzpracování dat (filtrace, doplnění chybějících dat, normalizace) výpočet příznaků výběr příznaků (podle směrodatnosti navržených příznaků) rozdělení dat na trénovací, validační a testovací trénování klasifikátoru hodnocení kvality klasifikace

Srovnání různých klasifikačních (regresních) algoritmů

K-NN (K-nearest neighbors)

Klasifikace podle nejmenší vzdálenosti

Bayesův klasifikátor

Klasifikace podle nejmenší chyby P (ω j | x) =

p ( x | ω j ) P (ω j ) p ( x)

p ( x) = ∑ p ( x | ωi ) P (ωi )

ωj P(ω j ) p (ω j | x )

p( x | ω j )

i

indikátory tříd apriorní pravděpodobnost aposteriorní pravděpodobnost podmíněné hustoty pravděpodobnosti

Bayesův klasifikátor

Odhad podmíněné hustoty pravděpodobnosti

parametrické metody – známe tvar rozdělení, neznáme parametry neparametrické metody – neznáme nic ☺, odhadujeme celý tvar rozdělení, např. metoda Parzenových okének

Support Vector Machine - SVM

Princip

Rozděluje data pomocí diskriminační funkce – otázka je, jak tuto funkci najít.

Lineární klasifikátor

Nelineární klasifikátor (např. právě SVM)

Principem SVM je najít takové nelineární transformační funkce (kernels), které převedou nelineárně separabilní prostor dat na lineárně separabilní

Klasifikační a regresní stromy –

Klasifikační a regresní stromy (Classification & Regression Trees – CART, C&RT) Analytické metody, které slouží pro klasifikaci a regresi.

–

Princip: Postupné hierarchické rozdělování prostoru dat na podskupiny tak, aby v listech vytvářeného stromu byly (homogenní) skupiny dat náležející (v případě klasifikace) jedné třídě.


Klasifikační stromy

Též název rozhodovací stromy (decision trees). Založeny na postupném rozdělování prostoru příznaků (podobně jako při hledání v botanickém klíči). Zařazují objekt do odpovídající třídy na základě příznaků (princip klasifikace) Jednoduché, rychlé Snadná vizualizace → dobrá interpretace výsledků Odolnější vůči odlehlým a chybějícím hodnotám. Nekladou žádné podmínky na typ pravděpodobnostního rozdělení sledovaných veličin.

Klasifikační a regresní stromy


Regresní stromy

Oproti klasifikačním stromům se neodhaduje diskrétní veličina (kategorický výstup) (jejíž rozdělení se uvnitř identifikovaných skupin – uzlů – znázorňuje pomocí histogramů), ale spojitá veličina. Spojitá veličina (spojitý výstup) se prokládá hodnotami uvnitř skupiny – uzlu – normálním rozdělením a počítá se jeho průměr a rozptyl (znázorňují se v jednotlivých uzlech stromu). Při predikci, se prochází stromem od kořene až do jednoho z terminálních uzlů (listů) a výsledkem predikce pro daný objekt je průměr pro daný uzel (průměr hodnot závislé veličiny těch případů z trénovací množiny, které patří do tohoto uzlu). Výsledkem pak je „schodovitá“ (po částech konstantní) predikce.



CHAID stromy

Chi-squared Automatic Interaction Detector (automatický detektor interakcí využívající test chí-kvadrát). Nebinární stromy - z jednoho uzlu mohou vyrůstat více než dva další uzly (jsou obecně širší než CART stromy). Pro klasifikační problémy se v každém kroku určuje nejlepší další dělení prostřednictvím testu chí-kvadrát. Pro regresní problémy se místo chí-kvadrátu používá F-test. Všechny spojité prediktory jsou nejprve diskretizovány tak, aby každá skupina obsahovala přibližně stejný počet hodnot. Pro kategoriální prediktory jsou jednotlivé skupiny definovány zcela přirozeně.

CHAID stromy

Vlastní vytváření CHAID stromu probíhá tak, že se identifikované kategorie ve všech vstupních proměnných začnou procházet a kontroluje se, zda se některé z nich nedají v rámci jedné proměnné sloučit (zda má takové dělení významný vliv na závislou proměnnou). Následně se pro dělení cyklicky vybírají ty proměnné, jejichž rozdělení přinese nejvyšší užitek. Dělení se zastaví v okamžiku, kdy neexistuje žádná proměnná, jejíž rozdělení by přineslo užitek větší než určitá prahová hranice.

CHAID stromy

CHAID stromy

CHAID stromy

Úplné CHAID stromy (Exhaustive CHAID) Modifikace základního CHAID algoritmu. Provádí se úplné slučování a testování proměnných (vyšší časová náročnost). Následně se provádí výběr a rozdělení proměnných stejně jako u klasické CHAID metody. Výhodou úplné CHAID metody je možnost dosáhnout lepších výsledků.

Random Forests (RF)

Leo Breiman, 2001 Pro klasifikační i regresní úlohy Plná kontrola nad klíčovými faktory RF (parametry, složitost stromů, max. počet stromů, ukončovací podm...) Možnost testovacího vzorku, rozsáhlé výstupy, export do C/C++ atd.

Random Forests (RF)

Kolekce jednoduchých stromů,kde každý strom je modelem klasifikační/regresní úlohy s více příznaky (prediktory) a jedním výstupem (závislé prom.) RF se skládá z libovolného počtu (kolekce) stromů, které se podílí na hlasováním na finální třídě (klasifikace) nebo průměrují výstupy (regrese). RF náhodně vybírá podmnožiny příznaků (prediktorů, proměnných) (s opakováním) z původní množiny dat. Optimální velikost podmnožiny příznaků je log2M+1, kde M je počet vstupů. Mohou kombinovat více kategoriálních i číselných proměnných. Kategorické proměnné jsou kódovány schématem 1 z N. RF si poradí i s chybějícími (špatnými) hodnotami.

Boosting Trees (BT)

Friedman,1999 Hastie, Tibshirani, & Friedman, 2001 Pro klasifikační i regresní úlohy Plná kontrola nad klíčovými faktory BT (parametry, složitost stromů, max. počet stromů, ukončovací podm...) Možnost testovacího vzorku, rozsáhlé výstupy, export do C/C++ atd.

Boosting Trees (BT)

BT jsou založeny na tzv. boostingu. Boosting = generování více (klasifikačních, regresních) modelů a jejich složení (kombinace) na základě vah tak, aby vznikl z vnějšího pohledu jediný výsledný model. Boosting vychází z tzv. Kernsovy otázky: Může se skupina slabých žáků jako celek chovat jako dobrý žák?

Boosting Trees (BT)

Generujeme jednoduché klasifikační/regresní stromy (např. C&RT, CHAID), kde každý následující strom je motivován k tomu aby byl trénován na neúspěšných vzorech předcházejícího jednoduchého stromu. Malé větvení stromů, typicky 3 vrcholy. Principiálně se vytváří regresní stromy. Pro klasifikační úlohu se generují regresní stromy pro každou třídu zvlášť.

Boosting Trees (BT)

každému vzoru přiřadíme stejnou (nejčastěji jednotkovou) váhu (váhy vzorů budou mít rovnoměrné rozdělení) váha určuje šanci, s jakou bude vzor vybrán vezmeme množinu trénovacích dat (buď celou nebo častěji náhodný výběr z této množiny) na této množině natrénujeme klasifikační nebo regresní C&RT nebo CHAID strom chceme aby strom byl jednoduchý a ani nemusí být příliš dobrý, např. v případě klasifikace stačí, aby byl lepší než „házení korunou“, tj. pravděpodobnost správného výsledku byla ostře větší než 0,5.

Boosting Trees (BT)

nalezený strom vyzkoušíme na trénovacích/testovacích datech a podle toho jak dobrý jsme dostali výsledek pro daný vstupní vzor, přiřadíme tomuto vzoru odpovídající váhu váha je tím větší, čím horší jsme dostali odpověď a naopak váha určuje pravděpodobnost, s jakou bude vzor v další iteraci vybrán, tj. vzory, pro které byla odpověď dobrá mají menší šanci, že budou v dalším kole vybrány a naopak vzory, které vedly ke špatným výsledkům (odpovědím) mají větší šanci, že budou vybrány (tentokrát už rozdělení vah není rovnoměrné) opět provedeme náhodný výběr se zohledněním vah a pokračujeme v další iteraci, tj. trénování dalšího (nového) stromu

Boosting Trees (BT)

v každém kroku dostáváme nový strom, který má velkou šanci být lepší než ten předchozí (protože se zaměřuje na vzory, které předchozí algoritmy nepodchytily tak dobře) celý iterační proces opakujeme tak dlouho, až dosáhneme požadované přesnosti klasifikace/regrese výsledný „strom“ je potom složen ze stromů každé iterace, přičemž odpovědi jednotlivých stromů jsou vhodně kombinovány, např. váženy nebo získávány hlasováním Pozn.:

Váhy vzorům můžeme přiřazovat přímým vážením vzorů, pomocí cenové matice nebo pomocí apriorních pravděpodobností.

Boosting Trees (BT)

Shluková analýza

Cíl: nalézt shluky (skupiny bodů), které si jsou vzájemně blízké (ve smyslu nějaké vzdálenosti) Snaha najít „kompaktní“ shluky Shluky jsou reprezentovány centry (vektory)

Míry

míra podobnosti mezi dvěma obrazy míra podobnosti mezi dvěma shluky míra kvality rozdělení obrazů do shluků (kriteriální funkce) metoda nejbližších sousedů, nejvzdálenějších sousedů, centroidní metoda, ...

Shluková analýza

p=2/3

p=3/2

Shluková analýza

Metody shlukové analýzy

metody iterativní optimalizace (nehierarchické) přesouváme obrazy mezi shluky a sledujeme hodnotu kriteriální funkce snaha najít extrém kriteriální funkce lokální optimalizace – málokdy globálně optimální k-means (metoda nejbližších těžišť), EM, SOM, ...

metody hierarchického shlukování shora-dolů (divizní) zdola-nahoru (anglomerativní) dendrogram – grafické vyjádření podobnosti

Shluková analýza

Metoda nejbližších těžišť (k-means)

Shluková analýza

EM shlukování EM – Expectation-Maximization Předpoklad

„měkká“ metoda shlukování – více překrývajících se shluků v průběhu shlukování Předpokládá se směs několika rozdělení:

Optimalizace

Normální Log-normální Poissonovo

Cílem je najít umístění shluků s těmito rozděleními.

Shluková analýza

Porovnání k-means a EM shlukování

Shluková analýza

Hierarchické shlukování

Rozdělení dat v prostoru

Dendrogram

Shluková analýza

Dendrogram

Vlastnosti dat ve vysocedimenzionálních prostorech

Vlastnosti dat ve vysocedimenz. prostorech

Motivace

Kvalita klasifikace je založena na znalosti rozdělení vzorů v prostoru. Metoda k nejbližších sousedů (k-NN), Bayesův klasifikátor, ...

Metoda k nejbližších sousedů

Hustota rozdělení je odhadována na základě poměru počtu k nejbližších sousedů k objemu koule, která je opisuje. Jednoduché a mnohdy to stačí, ale není respektováno rozdělení dat v prostoru.


Vlastnosti dat v prostoru

79 %

52 % vzdálenost

vzdálenost

dimenze

dimenze


p=2/3

p=3/2


Okrajový jev

Závislost k-tého nejbližšího souseda, od kterého se začíná projevovat okrajový jev, na dimenzi prostoru


Snaha pochytit reálné rozdělení dat v prostoru → to povede ke zlepšené klasifikaci. Předpoklad:

Každý bod (vzor) v prostoru přispívá k celkové pravděpodobnosti, že uvažovaný (klasifikovaný) vzor patří do dané třídy. Vliv daného vzoru je tím věší, čím je blíže ke klasifikovanému vzoru ... ... takže vliv vzorů klesá se vzdáleností od klasifikovaného vzoru.


Hustota pravděpodobnosti a distribuční funkce

Zkoumáme hustotu v jednotlivých „slupkách“. Z nich získáme hustotu pravděpodobnosti i distrib. funkci.


Předpoklad: Ideální případ je, kdy vzory jsou v prostoru rozděleny rovnoměrně. V případě, že tomu tak není, tak se snažíme dané rozdělení převést na rovnoměrné. To lze uskutečnit vhodnou změnou měřítka. v našem případě používáme vztah rq, kde q je vhodný exponent (může to být i funkce)

Klasifikace dat

Předpokládejme, že první nejbližší soused (vzor) má váhu 1, druhý váhu ½, třetí váhu 1/3, čtvrtý váhu ¼ atd. Pravděpodobnost, že vzor x patří do třídy c, pokud itý vzor je ze stejné třídy je vyjádřena vztahem 1 p ( x | c, i ) = K i

Celkový vliv všech sousedních vzorů je dán vztahem k

k

1 p ( x | c, k ) = ∑ p ( x | c , i ) = K ∑ i =1( c ) i =1( c ) i

Klasifikace dat

Pro jednu třídu (součet konečné harmonické řady) k

1 Sc = ∑ i =1( c ) i

Celkový vliv všech sousedních vzorů je dán vztahem N

1 S =∑ i =1 i

Pravděpodobnost, že vzor x patří do třídy c lze odhadnout vztahem Sc p ( x | c) = S

Klasifikace dat

Klasifikace dat

1.00

Signal Acceptance

0.80

0.60

0.40

Data w3p0-200 .. Tau decay for Higgs boson search

0.20

Bold blue - SUM 1/i L1 method Thin red, magenta, orange, yellow - Statistica 7 NN, different networks Lone diamond - cuts method used in physics Black - GMDH

0.00 0.00

0.20

0.40

0.60

Background Acceptance (error)

0.80

1.00

Klasifikace dat

Srovnání klasifikačních schopností uvedené metody na reálných datech.

Klasifikace dat

Vlastnosti se mění s použitou metrikou. Nejlepší výsledky jsou s L1 metrikou. S každou vyšší metrikou se výsledky zhoršují. Výhodou práce se vzdálenostmi je to, že jsme přešli z n-dimenzionálního prostoru do 1-dimenzionálního prostoru. Nejsou problémy s dimenzionalitou ... ... nicméně za cenu částečné ztráty informace o reálném prostorovém uspořádání vzorů.

Příprava a klasifikace biomedicínských dat. Marcel Jiřina

Recommend Documents