´ ´I SILNYCH ´ ˚ Z LEKA ´ ˇ ´ DOLOVAN VZORU RSK YCH ˇ ´ICH DAT SEKVENCN ˇ J. Kl´ema∗ , T. Holas∗ , F. Zelezn´ y∗ and F. Karel∗ ∗
Gerstnerova laboratoˇr, katedra kybernetiky, ˇ Cesk´e vysok´e uˇcen´ı technick´e, Technick´a 2, ˇ a republika 166 27 Praha, Cesk´
{klema,zelezny}@labe.felk.cvut.cz, {holast1,karelf1}@fel.cvut.cz Abstract:
´ Uvod
Sekvenˇ cn´ı data jsou d˚ uleˇ zit´ ym zdrojem l´ ekaˇ rsk´ ych znalost´ı. Tato specifick´ a data mohou vznikat ˇ radou r˚ uzn´ ych zp˚ usob˚ u. V tomto ˇ cl´ anku na pˇ r´ıkladu konkr´ etn´ı studie prezentujeme obecn´ e postupy pro jejich dolov´ an´ı. Jde o preventivn´ı dlouhodobou studii atheroskler´ ozy – data jsou v´ ysledkem dvˇ e dek´ ady trvaj´ıc´ıho sledov´ an´ı v´ yvoje rizikov´ ych faktor˚ u a pˇ ridruˇ zen´ ych jev˚ u. Hlavn´ım c´ılem je identifikovat ˇ cast´ e sekvenˇ cn´ı vzory, tj. opakuj´ıc´ı se ˇ casov´ e jevy, a studovat jejich moˇ znou souvislost s objeven´ım jedn´ e ze sledovan´ ych kardiovaskul´ arn´ıch nemoc´ı. Z ˇ sirˇ s´ı ˇ sk´ aly dostupn´ ych metod se soustˇ red´ıme na induktivn´ı logick´ e programov´ an´ı, kter´ e potenci´ aln´ı vzory vyjadˇ ruje ve formˇ e rys˚ u v predik´ atov´ e logice prvn´ıho ˇ r´ adu. Rysy jsou nejprve automaticky extrahov´ any a n´ aslednˇ e sdruˇ zov´ any do pravidel, kter´ a pˇ redstavuj´ı v´ ystupn´ı formu z´ıskan´ e znalosti. Navrˇ zen´ y postup je porovn´ an s tradiˇ cnˇ ejˇ s´ımi metodami publikovan´ ymi dˇ r´ıve. Jde o metodu posuvn´ ych oken a epizodn´ı pravidla.
L´ekaˇrsk´e datab´ aze obsahuj´ı velk´e mnoˇzstv´ı informac´ı o pacientech a jejich klinick´ ych vyˇsetˇren´ıch. Komplexn´ı vztahy a vzory skrytˇe obsaˇzen´e v tˇechto datech mohou pˇrin´est dosud nezn´ am´e znalosti. Vyuˇzitelnost tˇechto znalost´ı byla prok´ az´ ana celou ˇradou ˚ uspˇeˇsn´ ych medic´ınsk´ ych aplikac´ı metod dolov´ an´ı dat. Hlavn´ı tˇeˇziˇstˇe tˇechto aplikac´ı spoˇc´ıvalo ve vyuˇzit´ı atributov´ ych metod uˇcen´ı (attributevalued learning, AVL). Tyto metody jsou vˇsak omezeny na data, ve kter´ ych je kaˇzd´ y objekt, v naˇsem pˇr´ıpadˇe pacient, pops´ an pevnou mnoˇzinou pˇredem dan´ ych vlastnost´ı, tj. atribut˚ u. Nˇekdy je tato podm´ınka splnˇena pˇr´ımo, jindy postaˇc´ı dom´enovˇe nez´ avisl´ a metoda pˇredzpracov´ an´ı dat (napˇr. selekce atribut˚ u). St´ ale vˇsak existuje velk´e mnoˇzstv´ı u ´loh, u kter´ ych je pˇrevod na AVL reprezentaci netrivi´ aln´ı a specifick´ y. Ad-hoc pˇrevod je pak ˇcasovˇe n´ aroˇcn´ y, vyˇzaduje souˇcasnˇe u ´ˇcast l´ekaˇre a informatika, ˇcasto s nejist´ ym praktick´ ym v´ ysledkem. Je proto vhodn´e aplikovat techniky, kter´e mohou pracovat se sekvenˇcnˇe-relaˇcn´ımi daty pˇr´ımo. Tento ˇcl´ anek diskutuje a vytˇeˇzuje ˇcasovˇesekvenˇcn´ı data, kter´ a obvykle vyˇzaduj´ı komplexn´ı pˇredzpracov´ an´ı. Pod pojmem sekvence ch´ apeme ˇcasovou posloupnost ud´ alost´ı. Kaˇzd´ a ud´ alost m´ a pˇriˇrazen´ y typ a je pops´ ana hodnotou spolu s ˇcasovou zn´ amkou. Cel´ a datab´ aze pak m˚ uˇze obsahovat jednu nebo v obecn´em pˇr´ıpadˇe v´ıce nez´ avisl´ ych sekvenc´ı. Protoˇze plat´ı, ˇze v´ıce nez´ avisl´ ych sekvenc´ı jednoho typu je moˇzn´e pˇrev´est na sekvenci jedinou, nen´ı toto dˇelen´ı u ´plnˇe podstatn´e. Koneˇcn´ ym c´ılem je nalezen´ı siln´ ych vzor˚ u, za kter´e povaˇzujeme ˇcasto se opakuj´ıc´ı charakteristick´e ˇretˇezce ud´ alost´ı (podsekvence) a posouzen´ı jejich moˇzn´eho vztahu s c´ılovou ud´ alost´ı. Typickou c´ılovou ud´ alost´ı v l´ekaˇrsk´e aplikaci je projev nemoci nebo prokazateln´ a zmˇena zdravotn´ıho stavu pacienta. Konkr´etnˇe se zamˇeˇr´ıme na data STULONG [1], dlouhodobou 20-ti letou preventivn´ı studii muˇz˚ u stˇredn´ıho vˇeku. Studie obsahuje data, jeˇz jsou v´ ysledkem sledov´ an´ı pˇribliˇznˇe 1400 muˇz˚ u. Hlavn´ım z´ amˇerem projektu bylo odhalit rizikov´e faktory
Sequential data represent an important source of automatically mined and potentially new medical knowledge. They can originate in various ways. Within the presented domain they come from a longitudinal preventive study of atherosclerosis – the data consist of series of long-term observations recording the development of risk factors and associated conditions. The intention is to identify frequent sequential patterns having any relation to an onset of any of the observed cardiovascular diseases. This paper focuses on application of inductive logic programming. The prospective patterns are based on first-order features automatically extracted from the sequential data. The features are further grouped in order to reach final complex patterns expressed as rules. The presented approach is also compared with the approaches published earlier (windowing, episode rules).
atheroskler´ ozy. Data jsou ze sv´e podstaty multirelaˇcn´ı, skl´ adaj´ı se ze 4 z´ akladn´ıch relac´ı. V ˇcase se vyv´ıjej´ıc´ı u ´daje jsou uloˇzeny v tabulce vyˇsetˇren´ı (Control), kter´ a zaznamen´ av´ a u jednotliv´ ych osob r˚ uznˇe dlouh´e s´erie vyˇsetˇren´ı. Kaˇzd´e vyˇsetˇren´ı pak shrnuje konstantn´ı soubor hodnot rizikov´ ych veliˇcin spolu s nimi souvisej´ıc´ımi doplnkov´ ymi u ´daji. Pˇr´ıkladem rizikov´ ych faktor˚ u jsou veliˇciny BMI (Body Mass Index), krevn´ı tlak nebo biochemick´ a vyˇsetˇren´ı (cholesterol, triglyceridy), doplnkov´ ymi u ´daji jsou napˇr´ıklad fyzick´ a aktivita v zamˇestn´ an´ı a jej´ı zmˇeny, zp˚ usob dopravy do pr´ ace, uˇz´ıv´ an´ı l´ek˚ u apod. Data o jednom muˇzi odpov´ıdaj´ı z logick´eho hlediska jedn´e sekvenci ud´ alost´ı r˚ uzn´eho typu. Nˇekteˇr´ı muˇzi byli sledov´ ani po dobu nˇekolika let (nˇekolik m´ alo vyˇsetˇren´ı), u jin´ ych m´ ame k dispozici aˇz 20 vyˇsetˇren´ı – d´elka sekvenc´ı se tedy m˚ uˇze liˇsit velmi v´ yraznˇe. V neposledn´ı ˇradˇe jsou zaznamen´ ana a ˇcasovˇe oznaˇcena pozorov´ an´ı spojen´ a s projevy kardiovaskul´ arn´ıch nemoc´ı nebo pˇr´ımo jejich diagn´ oza. Vˇedeck´ y c´ıl v´ yˇse zm´ınˇen´e studie m˚ uˇze b´ yt formulov´ an v jazyce sekvenˇcn´ıho dolov´ an´ı dat n´ asleduj´ıc´ım zp˚ usobem. C´ılem je identifikovat ˇcast´e sekvenˇcn´ı vzory maj´ıc´ı prokazatelnou souvislost s objeven´ım nˇekter´eho ze sledovan´ ych kardiovaskul´ arn´ıch onemocnˇen´ı (KO). Pro zjednoduˇsen´ı uvedeme moˇzn´e pˇr´ıklady vzor˚ u v kontextu cel´ ych pravidel, vˇse v pˇrirozen´em jazyce: (1) jestliˇze BMI v ˇcase kles´ a a pot´e znovu roste zat´ımco krevn´ı tlak st´ ale roste pak je jak´ekoli KO pravdˇepodobnˇejˇs´ı, (2) jestliˇze BMI v ˇcase roste a hladina HDL cholesterolu je n´ızk´ a pak je jak´ekoli KO pravdˇepodobnˇejˇs´ı. Studie STULONG byla jednou z u ´loh hromadnˇe ˇreˇsen´ ych v r´ amci konference ECML/PKDD zamˇeˇren´e na probl´emy strojov´eho uˇcen´ı a dolov´ an´ı dat. Na dan´e t´ema byla publikov´ ana velk´ a ˇrada pˇr´ıspˇevk˚ u, z nichˇz se ovˇsem pouze nˇekolik zab´ yvalo sekvenˇcn´ım dolov´ an´ım dat. [3] pˇredstavuje pˇredzpracov´ an´ı ˇcasov´ ych dat metodou posuvn´eho okna, tj. ad-hoc metodou vytv´ aˇrej´ıc´ı trendov´e atributy pomoc´ı agregaˇcn´ıch oken. [5] doluje epizodn´ı pravidla univerz´ aln´ım n´ astrojem WinMiner. Vedle probl´emov´e nez´ avislosti lze metodu charakterizovat t´ım, ˇze automaticky vyhled´ av´ a optim´ aln´ı velikost ˇcasov´eho okna v jehoˇz rozsahu se vyhled´ avaj´ı opakuj´ıc´ı se sekvence ud´ alost´ı. V tomto textu prezentujeme alternativn´ı pˇr´ıstup vhodn´ y pro multirelaˇcn´ı probl´emy a aplikovateln´ y i pro sekvenˇcn´ı data strukturovan´ a jako ve STULONG studii – induktivn´ı logick´e programov´ an´ı (ILP). Pˇredstav´ıme obecn´ y n´ astroj RSD [4] pro relaˇcn´ı vytv´ aˇren´ı rys˚ u identifikuj´ıch v´ yznamn´e podskupiny v datech a aplikujeme jej na uvedenou dom´enu. Hledan´e vzory budou vyj´ adˇreny formou rys˚ u predik´ atov´e logiky prvn´ıho ˇra ´du a budou automaticky extrahov´ any ze sekvenˇcn´ıch dat. Uˇziteˇcnost tˇechto rys˚ u bude vyhodnocena AVL uˇcen´ım, rysy budou pouˇzity k vytv´ aˇren´ı komplexn´ıch struktur (for-
mul´ı) popisuj´ıc´ıch koneˇcn´e vzory. Hlavn´ı pˇr´ınos ˇcl´ anku spoˇc´ıv´ a v prohlouben´ı studia vyuˇzit´ı metod ILP pˇri dolov´ an´ı sekvenˇcn´ıch dat, nov´em zp˚ usobu aplikace RSD a obecn´em porovn´ an´ı v´ ysledk˚ u s alterantivn´ımi metodami pubˇ anek porovn´ likovan´ ymi dˇr´ıve. Cl´ av´ a dosaˇzen´e v´ ysledky z hlediska jednoduchosti, srozumitelnosti a znovupouˇzitelnosti v podobn´ ych u ´loh´ ach. RSD: Relational Subgroup Discovery Relaˇcn´ı uˇcen´ı pravidel je typicky pouˇz´ıv´ ano pˇri ˇreˇsen´ı klasifikaˇcn´ıch a predikˇcn´ıch u ´loh. Pˇredchoz´ı v´ yzkum STULONG dat vˇsak prok´ azal [3], ˇze nalezen´e vzory (a zcela zˇrejmˇe ani ty potenci´ alnˇe skryt´e) nejsou dostateˇcn´e ke spolehliv´e klasifikaci sledovan´ ych muˇz˚ u do tˇr´ıd. Jejich apriorn´ı dˇelen´ı na zdrav´e a nemocn´e (KO), popˇr´ıpadˇe do jemnˇejˇs´ıch kategori´ı podle typu nemoci, nen´ı na z´ akladˇe nahromadˇen´ ych dat moˇzn´e. Je evidentn´ı, ˇze u ´loha by mˇela b´ yt formulov´ ana jako identifikace zaj´ımav´ ych podskupin (subgroup discovery). Na vstupu je populace objekt˚ u (individu´ı, muˇz˚ u stˇredn´ıho vˇeku) popsan´ ych hodnotou jejich c´ılov´e vlastnost´ı (KO) spolu s hodnotami veliˇcin, kter´e je d´ ale charakterizuj´ı. V´ ystupem jsou podmnoˇziny dan´e populace, kter´e jsou statisticky “nejzaj´ımavˇejˇs´ı”: lze je jednoznaˇcnˇe charakterizovat, jsou co nejvˇetˇs´ı (obsahuj´ı co nejv´ıce objekt˚ u) a maj´ı co nejm´enˇe vyv´ aˇzen´e rozdˇelen´ı vzhledem k c´ılov´e vlastnosti. Jejich definice pˇritom vych´ az´ı ze sekvenˇcn´ıch vzor˚ u odr´ aˇzej´ıc´ıch ˇcasov´ y v´ yvoj rizikov´ ych faktor˚ ua pˇridruˇzen´ ych veliˇcin. RSD [4] umoˇznuje pˇrechod mezi relaˇcn´ım pravidlov´ ym uˇcen´ım a identifikac´ı zaj´ımav´ ych podskupin. N´ astroj je zaloˇzen na tˇechto principech: u ´pln´ a konstrukce rys˚ u prvn´ıho ˇra ´du, eliminace irelevantn´ıch rys˚ u, implementace relaˇcn´ıho pravidlov´eho uˇcen´ı, aplikace algoritmu v´ aˇzen´eho pokryt´ı a heuristick´e vyuˇzit´ı vah objekt˚ u pro stanoven´ı relativn´ı pˇresnosti algoritmu. Proces uˇcen´ı m˚ uˇze b´ yt zjednoduˇsen do n´ asleduj´ıc´ıch krok˚ u. Nejprve konstruujeme samotn´e rysy, tj. konjunkce liter´ al˚ u dostupn´ ych v r´ amci dan´e dom´eny. Jejich kl´ıˇcovou vlastnost´ı je schopnost definovat podskupiny charakterizovan´e o dva odstavce v´ yˇse. Pot´e jsou rysy sdruˇzov´ any do pravidel, jejichˇz kritick´ a vlastnost je velmi podobn´ a. Dodateˇcn´ ym poˇzadavkem je dostateˇcn´e pokryt´ı, tj. pravidlo by mˇelo b´ yt splnˇeno co nejvˇetˇs´ım poˇctem dosud nepokryt´ ych objekt˚ u (detaily lze nal´ezt v [4, 6]). Dolov´ an´ı STULONG dat Proveditelnost, sloˇzitost, rozliˇsen´ı Jako nejpˇrirozenˇejˇs´ı pˇr´ıstup k dolov´ an´ı STULONG dat se jev´ı vyhled´ av´ an´ı libovoln´ ych sekvenˇcn´ıch rys˚ u, potaˇzmo vzor˚ u. Jeden rys by tak mohl pokr´ yvat sekvenci libovoln´e d´elky a souˇcasnˇe by mohl
b´ yt v´ıcetypov´y, tj. sdruˇzovat ud´ alosti odliˇsn´ ych typ˚ u (v pˇr´ıpadˇe STULONG dat r˚ uzn´e rizikov´e faktory apod.). Dva pˇr´ıklady takov´ ych sekvenc´ı/rys˚ u ˇ jsou uvedeny na Obr´ azku 1. Casov´ e vztahy jsou modelov´ any bin´ arn´ımi predik´ aty a f ter1 , a f ter2 , ..., a f tern – predik´ aty vyjadˇruj´ı, ˇze druh´ a ud´ alost nastala 1, 2 nebo n vyˇsetˇren´ı po ud´ alosti prvn´ı – a simultaneous – kter´ y postihuje souˇcasn´e ud´ alosti z jednoho vyˇsetˇren´ı. Tyto predik´ aty by mohly b´ yt d´ ale doplnˇeny o ˇradu zobecnˇen´ı predik´ atu a f ter, napˇr. druh´ a ud´ alost nastala v libovoln´em vyˇsetˇren´ım n´ asleduj´ıc´ım vyˇsetˇren´ı, v nˇemˇz se objevila ud´ alost prvn´ı. Podotknˇeme, ˇze pˇrestoˇze vyˇsetˇren´ı nejsou v ˇcase zcela pravideln´ a, v r´ amci zjednoduˇsen´ı je v tomto textu povaˇzujeme za kaˇzdoroˇcn´ı. Abychom minimalizovali f´ azi pˇredzpracov´ an´ı dat, spojit´e veliˇciny mohou b´ yt diskretizov´ any pomocn´ ymi predik´ aty (napˇr. weight cat(X, small) :- X < 64.). Tento pˇr´ıstup nav´ıc pˇrin´ aˇs´ı vˇetˇs´ı variabilitu definice ud´ alost´ı, protoˇze za ud´ alost m˚ uˇze b´ yt teoreticky povaˇzov´ ana pˇr´ımo hodnota veliˇciny (weight(checkupi, 71)) nebo kategorie (weight(checkupi , X), weight cat(X, xsmall)). Zjednoduˇsen´ a textov´ a reprezentace rysu m˚ uˇze b´ yt n´ asleduj´ıc´ı: feature(ID,PAT):-checkup(PAT,Time1), checkup(PAT,Time2), after1 (Time1,Time2), syst(Time1,V1), syst_cat(V1,low), syst(Time2,V2), syst_cat(V2,high).
Rys je splnˇen pro vˇsechny objekty/muˇze maj´ıc´ı dvˇe pˇr´ımo po sobˇe n´ asleduj´ıc´ı vyˇsetˇren´ı, v nichˇz se hodnota systolick´eho krevn´ıho tlaku mˇen´ı z kategorie ”low” do kategorie ”high”. Rys postihuje dvˇe ud´ alosti, kaˇzd´ a z tˇechto ud´ alost´ı je pops´ ana tˇremi predik´ aty (definuj´ıc´ıch pacienta/ˇcas, typ ud´ alosti a kategorii). Obˇe ud´ alosti jsou nav´ıc spojeny ˇcasov´ ym predik´ atem. V´ yˇse naznaˇcen´ a variabilita kandid´ atsk´ ych rys˚ u a sekvenc´ı je jistˇe ˇza ´douc´ı z hlediska teoretick´eho rozsahu koneˇcn´e znalosti. Nicm´enˇe, naznaˇcen´ a variabilita v´ yraznˇe zvˇetˇsuje stavov´ y prostor sekvenc´ı a ohroˇzuje praktickou proveditelnost jeho prohled´ av´ an´ı. Poˇcet kandid´ atsk´ ych sekvenc´ı m˚ uˇze b´ yt pˇr´ıliˇs velk´ y a znemoˇznit tak vytvoˇren´ı koneˇcn´ ych pravidel v u ´nosn´em ˇcase. Pˇredpokl´ adejme, ˇze pracujeme s a veliˇcinami, z nichˇz kaˇzd´ a m˚ uˇze nab´ yvat v r˚ uzn´ ych hodnot, maxim´ aln´ı d´elka sekvence necht je l. Celkov´ y poˇcet jednotypov´ ych sekvenc´ı pak je O(ns ) = a vl+1 , zat´ımco poˇcet v´ıcetypov´ ych sekvenc´ı m˚ uˇze b´ yt aˇz O(ni ) = (av)l+1 . Je zˇrejm´e, ˇze poˇcet sekvenc´ı roste exponenci´ alnˇe s jejich maxim´ aln´ı d´elkou. V´ ypoˇcet je jeˇstˇe sloˇzitˇejˇs´ı pokud uvaˇzujeme rysy. V´ yˇse uveden´ y pˇr´ıklad demonstroval, ˇze d´elka rysu n´ asobnˇe pˇrekraˇcuje d´elku sekvence, protoˇze kaˇzd´ a ud´ alost je reprezentov´ ana nˇekolika predik´ aty a ud´ alosti mus´ı b´ yt vz´ ajemnˇe ˇcasovˇe sv´ az´ any. Technick´ a v´ ypoˇcetn´ı sloˇzitost pˇritom opˇet roste exponenci´ alnˇe s maxim´ aln´ı povolenou d´elkou rysu (udanou
v predik´ atech). V jist´em smyslu tedy mohutnost prohled´ avan´eho prostoru rys˚ u pˇrekraˇcuje mohutnost p˚ uvodn´ıho prostoru sekvenc´ı, protoˇze nelze automaticky rozliˇsit mezi smyslupln´ ymi rysy a tˇemi, kter´e nedopov´ıdaj´ı ˇza ´dn´e existuj´ıc´ı sekvenci 1 . Z v´ yˇse uveden´eho plyne nutnost omezit d´elku rys˚ u a t´ım i sekvenc´ı, souˇcasnˇe je tak´e vhodn´e volit rozumn´ y poˇcet veliˇcin i jejich hodnot. V´ıcetypov´e rysy jsou v´ ypoˇcetnˇe velmi n´ aroˇcn´e. Odhadnˇeme poˇcet kandid´ atsk´ ych sekvenc´ı v dom´enˇe STULONG. Poˇcet vyˇsetˇren´ı kol´ıs´ a mezi 1 a 21, pˇribliˇznˇe u 80% muˇz˚ u bylo provedeno 5 nebo v´ıce vyˇsetˇren´ı – z tohoto d˚ uvodu se zd´ a rozumn´ ym omezen´ım maxim´ aln´ı d´elka sekvence 5 ud´ alost´ı. Nejsignifikantnˇejˇs´ıch rizikov´ ych faktor˚ u je 5 (systolick´ y a diastolick´ y tlak (SYST, DIAST), hladina cholesterolu v mg%(CHLSTMG), hladina triglycerid˚ u v mg%(TRIGLMG) a BMI), byly u nich zjiˇstˇeny des´ıtky r˚ uzn´ ych hodnot. Tomu odpov´ıdaj´ı des´ıtky miliard kandid´ atsk´ ych sekvenc´ı. V d˚ usledku toho je tˇreba redukovat poˇcet veliˇcin (pˇripomenme, ˇze celkovˇe jich jsou des´ıtky, i kdyˇz r˚ uzn´e d˚ uleˇzitosti), coˇz ovlivnuje informovanost o vztahu mezi veliˇcinami (lze uvaˇzovat opakovan´e bˇehy s r˚ uzn´ ymi mnoˇzinami veliˇcin). Zkr´ acen´ı sekvenc´ı omezuje rozliˇsen´ı v ˇcasov´e oblasti. Sn´ıˇzen´ı poˇctu hodnot jednotliv´ ych veliˇcin naopak redukuje rozliˇsen´ı v oblasti datov´e. V´ıcetypov´ a povaha sekvenc´ı tak m˚ uˇze b´ yt vidˇena sp´ıˇse jako pˇrek´ aˇzka neˇz ˇza ´douc´ı vlastnost ˇreˇsen´ı. Souˇcasnˇe ovˇsem plat´ı, ˇze pˇres v´ yraznou v´ ypoˇcetn´ı n´ aroˇcnost jde o nov´ y zp˚ usob zpracov´ an´ı sekvenˇcn´ıch dat (viz. [2]). V souvislosti s n´ım jsou vyv´ıjeny nov´e a efektivnˇejˇs´ı algoritmy pro vytv´ aˇren´ı v´ıcetypov´ ych pravidel. V naˇsem textu je koneˇcn´e ˇreˇsen´ı pops´ ano v n´ asleduj´ıc´ıch dvou sekc´ıch. Pˇredstavuje ekvilibrium mezi mohutnost´ı prohled´ avan´ ych stavov´ ych prostor˚ u, rozsahem jazyka vzor˚ u a sloˇzitost´ı pˇredzpracov´ an´ı spojen´eho s vytv´ aˇren´ım ˇ sen´ı je zaloˇzeno na myˇsapriorn´ı znalosti o u ´loze. Reˇ lence rozdˇelen´ı dat do tˇr´ı disjunktn´ıch ˇcasov´ ych oken. Pˇredzpracov´ an´ı dat Zp˚ usob pˇredzpracov´ an´ı dat m˚ uˇze v´ yraznˇe ovlivnit efektivitu pouˇzit´ı RSD. Nutn´ ym syntaktick´ ym krokem je rutinn´ı pˇrevod dat z obvykl´ ych relaˇcn´ıch tabulek do predik´ atov´e formy. Souˇcasnˇe je tˇreba doplnit jazykov´e deklarace, opˇet v predik´ atov´e logice. Pro tento u ´ˇcel byl vytvoˇren extern´ı konverzn´ı program v jazyce Java. Vstupem jsou data ve form´ atu CSV, v´ ystupem pak soubory .pl (data – objekty a jejich c´ılov´ a vlastnost, ˇcasov´e u ´daje o vyˇsetˇren´ıch a hodnoty sledovan´ ych veliˇcin pro jednotliv´ a vyˇsetˇren´ı) 1 RSD v ˇ za ´dn´em pˇr´ıpadˇe negeneruje libovoln´e rysy, tj. libovoln´e konjunkce liter´ al˚ u. Prostor rys˚ u je automaticky redukov´ an t´ım, ˇze kaˇzd´ a promˇenn´ a mus´ı b´ yt alespon jednou definov´ ana jako vstupn´ı, rysy nesm´ı b´ yt rozloˇziteln´e, predik´ aty mohou b´ yt definovan´e jako antisymetrick´e apod. Sloˇzitost v´ ypoˇctu je tak´e pˇr´ımo ovlivniteln´ a apriorn´ı znalost´ı, kter´ a m˚ uˇze formulovat predik´ aty vysok´e u ´rovnˇe omezuj´ıc´ı prostor rys˚ u.
feature(ID,PAC):-checkup(PAC,Time1), trendsyst(Time1,big_increase).
Figure 1: V´ıcetypov´e sekvence v Prologu
a .b (apriorn´ı znalost – ˇcasov´e predik´ aty, definice ˇcasov´e sekvence a v´ yˇcet moˇzn´ ych element˚ u, z nichˇz se budou skl´ adat rysy) [6]. Z logick´eho hlediska lze pˇredzpracov´ an´ı dat rozdˇelit do tˇr´ı z´ akladn´ıch krok˚ u: (1) pˇrevod do predik´ atov´e formy, vyuˇziteln´e jako k´ od jazyka Prolog, (2) pˇr´ıpadn´ a diskretizace veliˇcin, (3) konstrukce nov´ ych trendov´ ych (tj. ˇcasov´ ych) veliˇcin. Prvn´ı krok byl v z´ asadˇe zm´ınˇen v prvn´ım odstavci, dalˇs´ı dva jiˇz pˇr´ımo ovlivnuj´ı efektivitu bˇehu RSD. Vˇenujme se nejprve diskretizaci. V pˇredchoz´ı sekci bylo pˇredvedeno, jak lze diskretizaci prov´est pˇr´ımo v predik´ atov´e logice. Jedn´ a se pravdˇepodobnˇe o nejmetodiˇctˇejˇs´ı a logicky elegantn´ı ˇreˇsen´ı, kter´e ovˇsem souˇcasnˇe sniˇzuje efektivitu generov´ an´ı rys˚ u t´ım, ˇze prodluˇzuje jejich nutnou d´elku. Z tohoto d˚ uvodu je vhodn´e veliˇciny diskretizovat pˇredem (v´ yˇse zm´ınˇen´ y Java k´ od). V pˇr´ıpadˇe dat STULONG byly generov´ any veliˇciny: NORMBMI, NORMSYST (NORMDIAST), NORMCHLSTMG a NORMTRIGLMG. Vznikly diskretizac´ı p˚ uvodn´ıch veliˇcin BMI, SYST, DIAST, CHLSTMG a TRIGLMG. Transformace byla provedena ekvidistantn´ı diskretizac´ı do tˇr´ı interval˚ u oznaˇcen´ ych jako “low”, “medium” a “high”2. Konstrukce rys˚ u m˚ uˇze b´ yt d´ ale zjednoduˇsena pˇredpˇripraven´ım kr´ atkodob´ ych trendov´ ych veliˇcin. Veliˇciny TRENDBMI, TRENDSYST (TRENDDIAST), TRENDCHLSTMG, TRENDTRIGLMG transformuj´ı origin´ aln´ı data do formy vyjadˇruj´ıc´ı rychlost zmˇen kl´ıˇcov´ ych rizikov´ ych faktor˚ u v ˇcase. Moˇzn´e hodnoty “trendov´ ych” veliˇcin jsou “down2”, “down”, “flat”, “up”, a “up2”, znamenaj´ıc´ı “prudk´ y pokles”, “pokles”, “beze zmˇeny”, “n´ ar˚ ust”, a “prudk´ y n´ ar˚ ust” pˇr´ısluˇsn´ ych origin´ aln´ıch veliˇcin mezi dvˇema sousedn´ımi vyˇsetˇren´ımi. Zjednoduˇsen´ı rys˚ u je zˇrejm´e. Rys plat´ıc´ı pro kaˇzd´eho pacienta, jenˇz m´ a dvˇe n´ asledn´ a mˇeˇren´ı systolick´eho krevn´ıho tlaku se zmˇenou z kategorie ”low” do kategorie ”high”, vyj´ adˇren´ y jin´ ym zp˚ usobem v pˇredchoz´ı sekci, bude nyn´ı vypadat takto: 2 Zp˚ usob diskretizace je vhodn´e volit po dohodˇe s expertem. V dan´e u ´loze pˇripad´ a v u ´vahu i vˇetˇs´ı poˇcet kategori´ı, popˇr. jin´ a diskretizaˇcn´ı metoda – frekvenˇcn´ı diskretizace do kategori´ı o stejn´em poˇctu objekt˚ u nebo lok´ aln´ı metody zohlednuj´ıc´ı kaˇzd´eho z muˇz˚ u oddˇelenˇe).
D´elka rysu poklesla ze 7 na 2. Kompaktnˇejˇs´ı z´ akladn´ı predik´ aty umoˇzn´ı pracovat s delˇs´ımi sekvencemi ud´ alost´ı a vˇseobecnˇe vyˇsˇs´ım datov´ ym i ˇcasov´ ym rozliˇsen´ım pˇri stejn´e mohutnosti prohled´ avac´ıho prostoru. Cenou je sloˇzitˇejˇs´ı pˇredzpracov´ an´ı a nutnost apriori rozhodnout o struktuˇre pouˇzit´ ych z´ akladn´ıch stavebn´ıch predik´ at˚ u. Na z´ avˇer se zm´ın´ıme o c´ılov´e veliˇcinˇe KO. Studie je koncipov´ ana tak, ˇze kardiovaskul´ arn´ı onemocnˇen´ı se m˚ uˇze objevit pouze v posledn´ım vyˇsetˇren´ı. Tj. po jeho diagn´ oze je muˇz z preventivn´ı studie vyˇrazen a pˇreveden do l´eˇcebn´eho reˇzimu. Proto lze tak´e obecnˇe pˇredpokl´ adat, ˇze d˚ uleˇzitost vyˇsetˇren´ı v ˇcase roste. C´ılov´ a veliˇcina KO je bin´ arn´ım atributem vyjadˇruj´ıc´ım u dan´eho muˇze v´ yskyt ˇci absenci kardiovaskul´ arn´ıho onemocnˇen´ı na konci jeho ˇrady vyˇsetˇren´ı (0 – zdr´ av, 1 – nemocen). Koneˇcn´e parametry experimentu Pˇredzpracov´ an´ı dat navrˇzen´e v pˇredchoz´ı sekci v´ yraznˇe redukuje d´elku rysu pˇri zachov´ an´ı komplexity a rozliˇsen´ı modelovan´ ych sekvenc´ı. K dokonˇcen´ı n´ avrhu experimentu je tˇreba definovat vztah rizikov´ ych faktor˚ u a c´ılov´e KO veliˇciny. D´elka origin´ aln´ıch sekvenc´ı se pohybuje od 1 do 21, pr˚ umˇern´ a d´elka je 8. Jednotliv´e homogenn´ı sekvence (SYST, BMI atd.) byly rozdˇeleny do tˇr´ı disjunktn´ıch oken nazvan´ ych begin, middle, end. End okno zahrnuje vˇzdy posledn´ı 4 ud´ alosti, middle pokr´ yv´ a 4 pˇredchoz´ı ud´ alosti a begin okno zahrnuje zbytek – vˇsechny ud´ alosti od prvn´ıho vyˇsetˇren´ı aˇz k middle oknu. Kaˇzd´ y rys postihuje ud´ alosti z jedin´eho okna a ˇ reprzentuje sekvenci maxim´ aln´ı d´elky 2. Casov´ e predik´ aty a f teri uveden´e v teoretick´em u ´vodu byly nahrazeny bin´ arn´ımi predik´ aty a f ter beg, a f ter mid a a f ter end. Ty definuj´ı, ˇze druh´ a ud´ alost nastala v libovoln´em ˇcase n´ asleduj´ıc´ım po ˇcase vyˇsetˇren´ı prvn´ı ud´ alosti, pˇriˇcemˇz musela nastat ve stejn´em oknˇe (beg znaˇc´ı poˇca ´teˇcn´ı okno atd.). Kaˇzd´e pravidlo m˚ uˇze b´ yt tvoˇreno nejv´ yˇse 3mi rysy. Pravidlo, a t´ım i koneˇcn´ y vzor, tedy m˚ uˇze celkovˇe postihnout sekvenci o 6 ud´ alostech 3 r˚ uzn´ ych typ˚ u. Konkr´etn´ı pˇr´ıklady nalezen´ ych pravidel lze nal´ezt v n´ aleduj´ıc´ı sekci. Jak plyne z pˇredchoz´ıho v´ ykladu, poˇcty ud´ alost´ı a typ˚ u se mohou liˇsit experimet od experimentu a z´ avis´ı na zp˚ usobu formulace u ´lohy. V jin´e dom´enˇe mohou b´ yt zcela jin´e. Kl´ıˇcem je pamˇetov´ a a v´ ypoˇcetn´ı realizovatelnost. V´ysledky Tato sekce pˇredkl´ ad´ a vybran´e v´ ysledky ve formˇe pravidel a jejich interpretac´ı. Zaˇcnˇeme n´ asleduj´ıc´ım pravidlem: tˇ rı ´da:0, spol:0.968, pok:0.156, zdvih:1.308
f(7369,A):-checkup(A,B), normsyst(B,medium), trendbmi(B,flat), trendsyst(B,up). f(3068,A):-checkup(A,B), checkup(A,C), after_mid(C,B), trendbmi(C,flat). f(1158,A):-checkup(A,B), checkup(A,C), after_beg(C,B), normtriglmg(B,low), trendtriglmg(C,up2).
Pravidla maj´ı stejnou syntaxi jako klasick´ a rozhodovac´ı pravidla, tedy Podm´ınka ⇒ Tˇr´ıda, kde Podm´ınka (premisa) m´ a tvar “objekt souˇcasnˇe splnuje vˇsechny uveden´e rysy” a Tˇr´ıda (v´ ysledek) vyjadˇruje “c´ılov´ a veliˇcina KO m´ a pro objekt hodnotu”. Rozd´ıl mezi identifikac´ı zaj´ımav´ ych podskupin a klasifikac´ı spoˇc´ıv´ a v tom, ˇze pravidla nejsou pouˇzit´ a k disjunktn´ımu dˇelen´ı objekt˚ u do tˇr´ıd, ale k porozumˇen´ı sledovan´e dom´enˇe. M˚ uˇzeme je ch´ apat i jako asociaˇcn´ı pravidla Ant ⇒ Suc, spojuj´ıc´ı dva jevy, antecedent a sukcedent. K hodnocen´ı kvality pravidel pouˇz´ıv´ ame kvantifik´ atory (m´ıry) zn´ am´e pr´ avˇe z oblasti asociaˇcn´ıch pravidel. Popis pravidla, uveden´ y vˇzdy na prvn´ı ˇra ´dce, reprezentuje n´ asleduj´ıc´ı u ´daje. Tˇr´ıda 0 oznaˇcuje pravidlo odkazuj´ıc´ı na muˇze bez KO, tˇr´ıda 1 naopak signalizuje muˇze s KO v posledn´ım vyˇsetˇren´ı. Pokryt´ı (pok) (nˇekdy tak´e oznaˇcov´ ano jako Podpora) proporcion´ alnˇe vyjadˇruje kolik objekt˚ u pravidlo splnuje, pok = n(Ant)/n, kde n(Ant) je poˇcet objekt˚ u splnuj´ıc´ıch podm´ınku, n je celkov´ y poˇcet objekt˚ u. Pravidla s mal´ ym pokryt´ım (napˇr. 5% a m´enˇe, z´ aleˇz´ı ovˇsem i na celkov´em poˇctu objekt˚ u) ˇcasto nejsou br´ ana v u ´vahu. To proto, ˇze popisovan´ y vztah m˚ uˇze b´ yt pouze n´ ahodnou odchylkou ve sledovan´em vzorku. Spolehlivost (spol) spol = n(Ant ∩ Suc)/n(Ant) je m´ırou d˚ uvˇeryhodnosti a pˇresnosti pravidla. Vyjadˇruje proporcion´ alnˇe kolik z objekt˚ u splnuj´ıc´ıch podm´ınku splnuje i z´ avˇer. Zdvih je definov´ an zdvih = spol/pa , kde pa = n(Suc)/n je apriorn´ı pravdˇepodobnost tˇr´ıdy pravidla. Zdvih vyjadˇruje kolikr´ at je dan´e pravidlo lepˇs´ı neˇzli pravidlo n´ ahodn´e, kter´e zachov´ av´ a apriorn´ı rozdˇelen´ı objekt˚ u do tˇr´ıd. Vˇsechny uveden´e kvantifik´ atory jsou maximalizaˇcn´ı. Poˇzadujeme tedy pravidla, kter´ a adresuj´ı co nejv´ıce objekt˚ u. Souˇcasnˇe plat´ı, ˇze se mnoˇzina tˇechto objekt˚ u v rozdˇelen´ı podle c´ılov´e vlastnosti co nejv´ıce liˇs´ı od u ´pln´e mnoˇziny. Zb´ yvaj´ıc´ı ˇra ´dky pravidla jsou v´ yˇctem rys˚ u tvoˇr´ıc´ıch antecedent, tedy podm´ınku. Vˇsechny uveden´e rysy, v naˇsem konkr´etn´ım pˇr´ıkladu 3, mus´ı b´ yt splnˇeny souˇcasnˇe. Prvn´ı rys vyjadˇruje, ˇze dan´ y muˇz mˇel vyˇsetˇren´ı se stˇredn´ım systolick´ ym tlakem, tento tlak mu ale vzrostl a souˇcasnˇe nerostlo jeho BMI. Druh´ y rys popisuje objekt se dvˇema vyˇsetˇren´ımi B a C ve stˇredn´ım oknˇe dlouhodob´eho pozorov´ an´ı. Vyˇsetˇren´ı C nastalo pˇred vyˇsetˇren´ım B a muˇz pˇri nˇem vyk´ azal konstantn´ı BMI. U tohoto rysu je zˇrejm´e, ˇze vyˇsetˇren´ı B nen´ı d˚ uleˇzit´e a slouˇz´ı pouze k ˇcasov´emu urˇcen´ı vyˇsetˇren´ı C. Povˇsimnˇeme si, ˇze n´ ami definovan´ y jazyk kv˚ uli omezen´ı stavov´eho prostoru u ´lohy neobsahuje predik´ at typu belongs(C, mid), kter´ y by ukotvil vyˇsetˇren´ı C ve stˇredn´ım ˇcasov´em
oknˇe pˇr´ımo. V konkr´etn´ım rysu pak vyˇsetˇren´ı C nem˚ uˇze b´ yt posledn´ım vyˇsetˇren´ım stˇredn´ı ˇca ´sti (mus´ı b´ yt n´ asledov´ ano B), coˇz je vˇsak sp´ıˇse d˚ usledkem v´ yˇse uveden´eho jazykov´eho omezen´ı. Tˇret´ı rys ˇr´ık´ a, ˇze objekt m´ a dvˇe vyˇsetˇren´ı B a C v u ´vodn´ı ˇca ´sti sv´e sekvence. C pˇredch´ az´ı B. Nejprve tedy prudce rostou trygliceridy a n´ aslednˇe je jejich u ´roven opˇet n´ızk´ a. Pokud cel´ y popis shrneme a interpretujeme zjednoduˇsenˇe dojdeme k tomuto popisu. N´ aˇs muˇz mˇel ve vzd´ alen´e minulosti prudk´ y n´ ar˚ ust triglycerid˚ u n´ asledovan´ y jejich normalizac´ı na n´ızk´e u ´rovni. Ve stˇredn´ı ˇcasti pozorov´ an´ı bylo jeho BMI stabilizov´ ano. Kdykoli v jeho sledov´ an´ı pak doˇslo k tomu, ˇze stˇredn´ı systolick´ y tlak d´ ale rostl beze zmˇen BMI. Muˇz s touto charakteristikou m´ a zhruba o 30% vyˇsˇs´ı ˇsanci3 , ˇze neonemocn´ı kardiovaskul´ arn´ı nemoc´ı, neˇz pr˚ umˇern´ y muˇz ze studie. Pod´ıvejme se na dalˇs´ı pravidlo: tˇ rı ´da:1, spol:0.615, pok:0.049, zdvih:2.367 f(4380,A):-checkup(A,B), checkup(A,C), after_end(C,B),normsyst(B,high),trendbmi(C,flat). f(4124,A):-checkup(A,B),checkup(A,C), after_end(C,B),normbmi(B,medium),trendchlstmg(C,up2). f(4439,A):-checkup(A,B),checkup(A,C), after_end(C,B),normsyst(B,high),trendchlstmg(C,up2).
Pravidlo m´ a velmi dobr´ y zdvih, na druhou stranu nem´ a velk´e pokryt´ı. Jde tedy o siln´e pravidlo plat´ıc´ı pro mal´ y poˇcet objekt˚ u. Vˇsechny popsan´e ud´ alosti nast´ avaj´ı na konci sekvence vyˇsetˇren´ı, dle definice oken nejd´ele 3 vyˇsetˇren´ı pˇred pˇr´ıpadn´ ym objeven´ım KO. Popsan´ı muˇzi maj´ı setrval´ y stav BMI n´ asledovan´ y vysokou hodnotou systolick´eho tlaku, prudce rostouc´ı hladinu cholesterolu n´ asledovanou stˇredn´ı hodnotou BMI a vysok´ ym systolick´ ym tlakem. Tito muˇzi maj´ı o 137% vyˇsˇs´ı pravdˇepodobnost brzk´eho objeven´ı kardiovaskul´ arn´ı nemoci neˇz pr˚ umˇer ve studii. Pokud pravidlo porovn´ ame s obecnˇe zn´ am´ ymi l´ekaˇrsk´ ymi znalostmi, je zˇrejm´e, ˇze je s nimi v souladu. Vysok´ y krevn´ı tlak a rostouc´ı cholesterol jsou jevy pˇrisp´ıvaj´ıc´ı k poruch´ am kardiovaskul´ arn´ıho syst´emu. Pod´ıvejme se podrobnˇeji na podporu posledn´ıho pravidla z pohledu re´ aln´e velikosti popisovan´e skupiny muˇz˚ u. Pokryt´ı 0.049 implikuje pˇri 800 objektech 39 muˇz˚ u. Apriorn´ı pravdˇepodobnost tˇr´ıdy 1 v datech je 26%. V n´ ahodnˇe vybran´e skupinˇe 39 muˇz˚ u tedy nejpravdˇepodobnˇeji bude 10 nemocn´ ych. Ve skupinˇe definovan´e pravidlem je 24 nemocn´ ych. Uvaˇzujeme-li binomick´e pravdˇepodobnostn´ı rozdˇelen´ı, pravdˇepodobnost, ˇze se v n´ ahodnˇe vybran´e skupinˇe 39 muˇz˚ u objev´ı 24 a v´ıce nemocn´ ych, je pouze 2.6e−6 . Tato pravdˇepodobnost nen´ı vysok´ a, mus´ıme ale uvaˇzovat i opakovan´e pokusy. Pˇri prohled´ av´ an´ı stavov´eho prostoru statisticky testujeme velk´e mnoˇzstv´ı r˚ uzn´ ych rys˚ u a pravidel. Relaˇcn´ı uˇcen´ı m˚ uˇze b´ yt vyuˇzito i pro nesekvenˇcn´ı data. V tomoto pˇr´ıpadˇe je aplikace zjednoduˇsena o ˇcasov´e predik´ aty ˇci pˇredzpracov´ an´ı trendov´ ych 3 Urˇ ceno
podle zdvihu, p = (zdvih − 1) · 100%.
veliˇcin. V´ ysledkem aplikace pak je mj. n´ asleduj´ıc´ı pravidlo: tˇ rı ´da:0, spol:0.910, pok:0.084, zdvih:1.230 f(9745,A):-liquors(A,none). f(9737,A):-beer(A,more_than_1_liter).
Pravidlo vyjadˇruje, ˇze pij´ aci piva, kteˇr´ı souˇcasnˇe nepij´ı lik´ery s velk´ ym obsahem alkoholu, maj´ı o 23% sn´ıˇzen v´ yskyt KO. Porovn´ ame-li tuto tˇr´ıdu pravidel s pravidly vytv´ aˇren´ ymi statistick´ ym ˇci asociaˇcn´ım uˇcen´ım, dojdeme k z´ avˇeru, ˇze v´ ysledky se v´ yraznˇe neliˇs´ı (stejn´e pravidlo jiˇz bylo nalezeno dˇr´ıve). V´ yhodou induktivn´ıho relaˇcn´ıho uˇcen´ı je vˇsak to, ˇze sekvenˇcn´ı a nesekvenˇcn´ı rysy mohou b´ yt snadno a pˇrirozenˇe kombinov´ any. Pˇr´ıklad kombinovan´eho pravidla je uveden zde: tˇ rı ´da:1 spol:0.568, pok:0.055, zdvih:2.185 f(9738,A):-beer(A,occasionally). f(8453,A):-checkup(A,B),normchlstmg(B,medium), trendchlstmg(B,flat). f(3787,A):-checkup(A,B),checkup(A,C),after_mid(C,B), trendtriglmg(B,down2),trendtriglmg(C,flat).
Pravidlo m˚ uˇze b´ yt slovnˇe pops´ ano takto. Obˇcasn´ı konzumenti piva s norm´ aln´ı hladinou cholesterolu a prudk´ ym poklesem triglycerid˚ u v krvi maj´ı o 118% vyˇsˇs´ı ˇsanci, ˇze se u nich rozvine KO. Pokryt´ı pravidla opˇet nen´ı vysok´e. Pokud spoj´ıme znalost z´ıskanou posledn´ımi dvˇema pravidly s pˇr´ıbuznou znalost´ı obecnou m˚ uˇzeme usoudit, ˇze dobrou prevenc´ı KO je nep´ıt tvrd´ y alkohol a pˇrestat kouˇrit (coˇz je obecn´ a znalost). Zaj´ımavou informac´ı hodnou podrobnˇejˇs´ıho l´ekaˇrsk´eho zv´ aˇzen´ı je, ˇze pit´ı piva nen´ı ˇskodliv´e ani ve vˇetˇs´ım mnoˇzstv´ı, pokud souˇcasnˇe nekles´ a hladina triglycerid˚ u. Table 1: Parametry nejsilnˇejˇs´ıch nalezen´ ych pravidel Class
Spolehlivost
Pokryt´ı
Zdvih
0
0.9
0.32
1.22
0
0.95
0.2
1.28
0
0.97
0.16
1.31
0
0.90
0.15
1.22
0
0.91
0.08
1.23
0
0.97
0.13
1.31
0
0.95
0.05
1.29
0
1.0
0.07
1.35
1
0.45
0.17
1.73
1
0.47
0.13
1.81
1
0.47
0.1
1.8
1
0.57
0.06
2.19
1
0.62
0.05
2.37
1
0.7
0.03
2.68
V Tabulce 1 je uveden pˇrehled nejsilnˇejˇs´ıch nalezen´ ych pravidel. Zaznamen´ any jsou pouze je-
jich kvalitativn´ı charakteristiky, vˇsechna zaj´ımav´ a pravidla nelze z prostorov´ ych d˚ uvod˚ u rozeb´ırat podrobnˇe. Tabulka vˇsak m˚ uˇze b´ yt vod´ıtkem k obecn´emu posouzen´ı s´ıly nalezen´ ych pravidel. Z obecn´eho hlediska plat´ı, ˇze pravidla s vˇetˇs´ım pokryt´ım maj´ı menˇs´ı zdvih a naopak. Protoˇze skupina zdrav´ ych muˇz˚ u je vˇetˇs´ı (muˇz˚ u bez KO jsou necel´e tˇri ˇctvrtiny), pravidla na ni zamˇeˇren´ a maj´ı vˇetˇs´ı pokryt´ı a menˇs´ı zdvih. U nemocn´e skupiny je tomu pr´ avˇe naopak. Pokud pravidla porovn´ ame s obecnou l´ekaˇrskou znalost´ı, zjist´ıme, ˇze jsou s n´ı ve vˇetˇsinˇe pˇr´ıpad˚ u v souladu. Menˇsina pravidel je pak l´ekaˇri hodnocena jako zaj´ımav´ a ˇci pˇrekvapiv´ a. Pouze nˇekolik pravidel bylo hodnoceno spornˇe. Diskuse Generovan´ a pravidla jsou dostateˇcnˇe siln´ ym v´ yrazov´ ym prostˇredkem k detailn´ımu popisu ˇcasov´ ych vazeb mezi veliˇcinami. Souˇcasnˇe plat´ı, ˇze d´ıky generalizaci nejsou n´ achyln´ a k vyhled´ av´ an´ı sekvenc´ı odpov´ıdaj´ıc´ıch n´ ahodn´emu ˇsumu. Drobn´e odchylky v hodnot´ ach veliˇcin nejsou povaˇzov´ any za trendy. Pro exaktn´ı dom´eny, kde i drobn´e zmˇeny mohou b´ yt v´ yznamn´e (lze si pˇredstavit napˇr´ıklad fyziku), by zp˚ usob pˇredzpracov´ an´ı a apriorn´ı znalost musely b´ yt opˇet pˇrizp˚ usobeny charakteru dat. Z obecn´eho hlediska je omezen´ım umˇel´e rozdˇelen´ı ˇcasov´e osy do tˇr´ı oken, coˇz nem´ a jasn´e fyziologick´e opodstatnˇen´ı. Hlavn´ım d˚ uvodem je omezen´ı sloˇzitosti prohled´ av´ an´ı. Metoda je zamˇeˇrena na vyhled´ av´ an´ı lok´ aln´ıch vzor˚ u, resp. omezen´ ych podskupin. Pravidla nejsou urˇcena ke konstrukci glob´ aln´ıho modelu, coˇz potvrzuje v´ ysledek zkusm´e klasifikace – klasifikaˇcn´ı pˇresnost nepˇrekon´ av´ a klasick´e algoritmy uˇcen´ı (rozhodovac´ı stromy, bayesovsk´e sitˇe apod.) nevyuˇz´ıvaj´ıc´ı trendov´ ych atribut˚ u, tj. sekvenˇcn´ı informaci. Aˇckoli sekvenˇcn´ı informace pro dan´ a data nezpˇresnuje glob´ aln´ı model je zˇrejm´e, ˇze relaˇcn´ı uˇcen´ı sekvenˇcn´ıch pravidel vyhled´ av´ a zaj´ımav´e vzory. Tyto vzory by standardn´ımi metodami, jako jsou tradiˇcn´ı asociaˇcn´ı pravidla, z˚ ustaly opomenuty. Vzhledem k tomu, ˇze sekvenˇcn´ı rysy m˚ uˇzeme libovolnˇe kombinovat s rysy ne-sekvenˇcn´ımi (tj. volnˇe smˇeˇsovat okamˇzit´ a a ˇcasovˇe promˇenn´ a data), jde o zobecnˇen´ı tradiˇcn´ıho asociaˇcn´ıho uˇcen´ı. Jako u kaˇzd´e metody dolov´ an´ı dat jsou pˇredzpracov´ an´ı, formulace apriorn´ı znalosti i koneˇcn´ y v´ ysledek probl´emovˇe z´ avisl´e. Nejde ale o ad-hoc postup, protoˇze metoda definuje jasn´e komunikaˇcn´ı rozhran´ı s uˇzivatelem, jehoˇz jazyk je dostateˇcnˇe bohat´ ym v´ yrazov´ ym prostˇredkem pro pˇrizp˚ usoben´ı se u ´loze. Porovnejme popsanou relaˇcn´ı metodu s jej´ımi pˇr´ım´ ymi sekvenˇcn´ımi alternativami aplikovan´ ymi dˇr´ıve. Metoda pevn´ ych ˇci posuvn´ ych oken je jednoduch´ ym a ˇcasto pouˇz´ıvan´ ym postupem pˇredzpracov´ an´ı sekvenˇcn´ıch dat. V pˇr´ıpadˇe pevn´ ych
oken sekvenci rozdˇel´ıme do nˇekolika disjunktn´ıch ˇca ´st´ı. Posuvn´e okno naopak generuje vz´ ajemnˇe se pˇrekr´ yvaj´ıc´ı podsekvence. V obou pˇr´ıpadech jsou hodnoty veliˇcin zachycen´ ych v oknˇe pˇrevedeny na veliˇciny agregovan´e a analyzov´ any tradiˇcn´ım atributov´ ych uˇcen´ım (AVL). V pˇr´ıpadˇe STULONG dat byla jako agregaˇcn´ı funkce zvolena line´ arn´ı regrese, kl´ıˇcovou veliˇcinou byl tedy line´ arn´ı trend. Aplikace posuvn´eho okna pevn´e d´elky je v [3]. Aˇckoli metoda v dan´e u ´loze pˇrinesla velmi dobr´e v´ ysledky (napomohla mj. k objeven´ı vztahu mezi poˇctem vyˇsetˇren´ı a KO), projevila se souˇcasnˇe jej´ı ˇcasov´ a n´ aroˇcnost a probl´emov´ a z´ avislost. Ot´ azky typu ’jak´ a je optim´ aln´ı d´elka okna?’ nebo ’je linearizace vhodnou metodou generalizace pˇri vytv´ aˇren´ı vzor˚ u?’ mus´ı b´ yt zvaˇzov´ any a experiment´ alnˇe ˇreˇseny. WinMiner [5] je naproti tomu zcela obecn´ y n´ astroj pro vyhled´ av´ an´ı epizodn´ıch pravidel – vzor˚ u, kter´e mohou b´ yt extrahov´ any z teoreticky libovolnˇe dlouh´e sekvence. Pˇri jeho aplikaci je ovˇsem tˇreba ˇreˇsit ot´ azky velmi podobn´e ot´ azk´ am ˇreˇsen´ ym v pˇr´ıpadˇe induktivn´ıho logick´eho programov´ an´ı. Konkr´etnˇe, data mus´ı b´ yt diskretizov´ ana, protoˇze syst´em pracuje se symbolick´ ymi sekvencemi. Abychom mohli pracovat s v´ıcetypov´ ymi vzory, koneˇcn´ a abeceda symbol˚ u mus´ı odliˇsit rizikov´e faktory, resp. ud´ alosti r˚ uzn´ ych typ˚ u. Mnoˇzina sekvenc´ı odpov´ıdaj´ıc´ıch jednotliv´ ym muˇz˚ um je pˇrevedena na sekvenci jedinou a to tak, aby ˇcasov´e zn´ amky pˇriˇrazen´e ud´ alostem jednoznaˇcnˇe oddˇelovaly jednotliv´e muˇze. Tj. posledn´ı ud´ alost pˇredchoz´ıho muˇze m´ a takovou ˇcasovou zn´ amku, kter´ a nikdy nedovol´ı ji zaˇradit do stejn´eho okna s prvn´ı ud´ alost´ı muˇze n´ asleduj´ıc´ıcho. Z d˚ uvodu v´ ypoˇcetn´ı sloˇzitosti mus´ı b´ yt pomˇernˇe v´ yrazn´e omezena maxim´ aln´ı d´elka okna, ve kter´em vzory vyhled´ av´ ame. Opˇet plat´ı, ˇze sloˇzitost roste exponenci´ alnˇe s maxim´ aln´ı d´elkou okna. Sekvenˇcn´ı vzory nalezen´e pomoc´ı RSD a WinMineru jsou v´ yznamovˇe podobn´e. Hlavn´ı odliˇsnost spoˇc´ıv´ a v moˇznosti RSD pˇredstanovit v´ ysledn´ y tvar vzoru pomoc´ı apriorn´ı znalosti. WinMiner vyhled´ av´ a univerz´ aln´ı tˇr´ıdu vzor˚ u, tj. libovolnou dostateˇcnˇe ˇcasto se opakuj´ıc´ı sekvenci symbol˚ u. Pˇresnˇejˇs´ı definice tˇr´ıdy vyhled´ avan´ ych vzor˚ u pˇrin´ aˇs´ı vedle specializace i sn´ıˇzen´ı pamˇetov´e n´ aroˇcnosti a urychlen´ı v´ ypoˇctu. Na druhou stranu vyˇzaduje z´ akladn´ı znalost predik´ atov´e logiky. Z´ avˇ er Tento ˇcl´ anek prezentuje induktivn´ı logick´e programov´ an´ı jako n´ astroj dolov´ an´ı sekvenˇcn´ıch dat. Relaˇcn´ı uˇcen´ı nen´ı prioritnˇe pouˇzito k anal´ yze dat rozpt´ ylen´ ych ve v´ıce tabulk´ ach, ale na individu´ alnˇe orientovan´ a data. V tˇech jsou jednotliv´e objekty pops´ any r˚ uzn´ ym poˇctem transakc´ı charakterizovan´ ych ˇcasov´ ymi u ´daji. C´ılem je souˇcasn´e vyhled´ an´ı vztah˚ u mezi poloˇzkami (veliˇcinami) a
transakcemi. Praktick´e uplatnˇen´ı metody je demonstrov´ ano na pˇr´ıkladu identifikace rizikov´ ych faktor˚ u atheroskler´ ozy. D˚ uraz je pˇritom kladen na efekt ˇcasov´ ych zmˇen tˇech veliˇcin, o jejichˇz absolutn´ı hodnotˇe je zn´ amo, ˇze ovlivnuje kardiovaskul´ arn´ı syst´em. Podˇ ekov´ an´ı ˇ Tento v´ yzkum vznikl v r´ amci programu MSM 6840770012 ”Transdisciplinary Biomedical Engineering Research II.” podporovan´eho Ministerstvem ˇskolstv´ı a grantu 1ET101210513 ”Relational Machine Learning for Analysis of Biomedical Data” podˇ porovan´eho Ceskou akademi´ı vˇed. Studie STULONG byla realizov´ ana na II. intern´ı klinice, 1. l´ekaˇrsk´e fakulty UK a Vˇseobecn´e fakultn´ı nemocnice, U nemocnice 2, Praha 2 pod veden´ım prof. MUDr. F.Boud´ıka, DrSc., MUDr. M.Tomeˇckov´e, CSc. a doc. MUDr. J.Bultase, CSc. Vˇetˇsina dat byla pˇrevedena do elektronick´e podoby v r´ amci evropsk´eho projektu Managing Uncertainity in Medicine programu Copernicus na pracoviˇsti EuroMISE (Evropsk´eho centra medic´ınks´e informatiky, statistiky a epidemiologie) Karlovy univerzity a Akademie vˇed (pod veden´ım prof. RNDr. J.Zv´ arov´e, DrSc.). Anal´ yza dat vznikla za podpory ˇ ˇ LN 00B 107. grantu MSMT CR References [1] EUROMISE, Stulong – epidemiological study of atherosclerosis. Internet site address: http://euromise.vse.cz/challenge2004/index.html. [2] Guil, F., Bosch, A., and Marin, R. TSET: Algorithm for mining frequent temporal patterns. In Proc. of ECML/PKDD’04 Workshop on Knowledge Discovery in Data Streams - A Collaborative Effort in Knowledge Discovery, pages 65–74, 2004. ´ kova ´ , L., Karel, F., and [3] Kl´ ema, J., Nova ˇ ˇ ´ nkova ´ , O. Trend analysis in stulong St epa data. In Proc. of ECML/PKDD’04 Discovery Challenge - A Collaborative Effort in Knowledge Discovery. Prague: Univ. of Economics, 2004. ˇ ´ , F., and Flach, P. [4] Lavrac, N., Zelezn y RSD: Relational subgroup discovery through first-order feature construction. In Matwin and Sammut, editors, Proc. 12th Int. Conf. on Inductive Logic Programming, 2002. [5] Meger, N., Leschi, C., Lucas, N., and Rigotti, C. Mining episode rules in stulong dataset. In Proc. of ECML/PKDD’04 Discovery Challenge - A Collaborative Effort in Knowledge Discovery. Prague: Univ. of Economics, 2004. ˇ ´ , F. RSD user’s manual. Available at: [6] Zelezn y http://labe.felk.cvut.cz/ zelezny/rsd/rsd.pdf.
