Analiza Sintactica a Biosemnalelor
CUPRINS
CUPRINS ……………………………………………………………………………….. 2
INTRODUCERE ………………………………………………………………………. 4
CAPITOLUL 1: NOȚIUNI DE ANATOMIE ȘI FIZIOLOGIE A
CORDULUI …………………………………………………………… 5
1.1. CONFIGURAȚIA EXTERNĂ ……………………………………. 5
1.2. CONFIGURAȚIA INTERNĂ …………………………………….. 5
1.3. CICLUL CARDIAC ………………………………………………….. 6
1.4. ACTIVITATEA ELECTRICĂ A CORDULUI …………….. 6
1.5. ACTIVITATEA MECANICĂ A CORDULUI ……………… 8
1.6. ELECTROCARDIOGRAFIE ……………………………………… 9
1.6.1. GENERALITĂȚI ………………………………………………… 9
1.6.2. DERIVAȚIILE STANDARD ……………………………….. 10
1.6.3. DERIVAȚIILE UNIPOLARE ALE MEMBRELOR .. 10
1.6.4. DERIVAȚIILE UNIPOLARE ALE MEMBRELOR,
AUGUMENTATE ………………………………………………. 11
1.6.5. DERIVAȚIILE PRECORDIALE …………………………….. 12
1.6.6. DERIVAȚIILE ESOFAGIENE ………………………………… 13
1.6.7. SCHEMA BLOC A ELECTROCARDIOGRAFULUI … 13
CAPITOLUL 2: NOȚIUNI DE ANALIZĂ SINTACTICĂ ……….. 14
2.1. STRUCTURA ȘIRURILOR ……………………………………….. 14
2.1.1 ALFABET, CONCATENARE, ȘIR ………………………. 14
2.1.2. COMPARAREA ȘIRURILOR ………………………………. 15
2.2. STRUCTURI SINTACTICE REGULATE …………………… 21
2.2.1. DEFINIȚII …………………………………………………………… 21
2.2.2. GENERAREA UNEI FRAZE DE CĂTRE O
GRAMATICĂ ……………………………………………………… 22
2.2.3. GRAMATICI REGULATE. AUTOMATE FINITE …. 23
2.2.4. DECIZIA ÎN STRUCTURILE SINTACTICE
REGULATE ………………………………………………………… 28
2.2.5. ÎNVĂȚAREA STRUCTURILOR REGULATE ………. 31
2.2.6. MODELE SINTACTICE REGULATE PONDERATE 35
2.3. STRUCTURI DE ARBORI ………………………………………… 35
2.3.1. DEFINIȚII. PROPRIETĂȚI ELEMENTARE …………. 36
2.3.2. NUMEROTAREA PRIN DOMENIU AL ARBORELUI
SAU LEXICOGRAFICĂ ………………………………………. 39
2.3.3. DISTANȚA ÎNTRE ARBORI ……………………………….. 39
2.3.4. GRAMATICI ALE ARBORILOR …………………………. 39
2.4. STRUCTURI DE GRAFURI ………………………………………. 41
2.4.1. PREZENTARE …………………………………………………….. 41
2.4.2. NOȚIUNI ELEMENTARE ALE TEORIEI
GRAFURILOR ……………………………………………………. 41
2.4.3. REFACEREA UNUI GRAF PRINTR-UN ARBORE ..42
2.4.4. IZOMORFISMUL ÎNTRE GRAFURI ȘI INCLUZIUNEA
GRAFURILOR …………………………………………………….. 42
2.4.5. REPREZENTAREA ȘI REZOLVAREA
PROBLEMELOR PRIN GRAFURI DE STĂRI ………. 43
CAPITOLUL 3: ANALIZA SINTACTICĂ A SEMNALELOR ECG
3.1. INTRODUCERE ……………………………………………………….. 44
3.2. DEFINIȚII ………………………………………………………………… 45
3.3. IDENTIFICATOARE SINTACTICE ………………………….. 46
3.4. LIMBAJELE STOHASTICE ȘI ANALIZA SINTACTICĂ 53
3.5. DEDUCEREA GRAMATICALĂ ……………………………….. 55
3.6. EXEMPLE ………………………………………………………………… 55
3.6.1. ANALIZA SINTACTICĂ A PRESIUNII SANGUINE ÎN
CAROTIDĂ …………………………………………………………. 55
3.6.2. ANALIZA SINTACTICĂ A ECG ………………………….. 58
CAPITOLUL 4: EXEMPLU DE ABORDARE SINTACTICĂ ÎN
ECG ……………………………………………………………… 61
4.1. INTRODUCERE ………………………………………………………………… 61
4.2. FORME ȘI PARAMETRII AI FORMELOR ÎN ECG …… 62
4.3. ABORDAREA SINTACTICĂ ÎN RECUNOAȘTEREA
UNDELOR ECG ……………………………………………………… 63
4.3.1. SELECȚIA FORMELOR PRIMITIVE …………………. 63
4.3.2. EXTRAGEREA FORMELOR PRIMITIVE …………… 64
4.3.3. REPREZENTARE LINGVISTICĂ ……………………….. 65
4.3.4. GRAMATICA FORMELOR ………………………………… 65
4.4. IMPLEMENTARE …………………………………………………. 67
4.5. CONCLUZII ………………………………………………………….. 68
ANEXE
BIBLIOGRAFIE
BIBLIOGRAFIE
[1] Arnon Cohen – Biomedical Signal Processing
[2] R.A. Wagner – Order-n correction for Regular Languages, CACM, vol.17, nr.5 (1974)
[3] E.M. Gold – Complexity of Automation Identification from given data Information and Control, nr.20 (1978)]
[4] M. Gondran, M. Minoux – Graphes et algorithmes, Eyroles (1979)
[5] S.A. Boorman, D. C. Olivier – Metrics on spaces of finite trees, Jurnal de Psihologie Matematică, nr.10 (1973)
[6] B. Monjardet – Metrics on partially ordered sets, Universite Paris V et Centre de Math. Sociales
[7] S.M. Selkow – The tree-to-tree editing problem, Information Processing Letters vol.6 nr.6 (1977)
[8] B. Levine – Derivatives of tree sets with applications to grammatical inference, IEEE Tr on PAMI, vol.PAMI 3 nr.3 (1981)
[9] L. Miclet – Methodes structurelles pour la reconnaissance des formes, Eyrolles (1984)
[10] E. Skordalakis – Syntactic ECG Processing, Pattern Recognition, vol.19, nr.4 (1986)
[11] P. Trahanias, E. Skordalakis – Syntactic Pattern Recognition of the ECG, IEEE Transaction on Pattern Analysis and Machine Intelligence, vol.12, nr.7 (iulie 1990)
[12] M. Ghinea, V. Firețeanu – Matlab, Calcul numeric – Grafică – Aplicații
=== Capitol 1 ===
CAPITOLUL 1
NOȚIUNI DE ANATOMIE ȘI FIZIOLOGIE A CORDULUI
1.1. CONFIGURAȚIA EXTERNĂ
Cordul este un organ muscular, cavitar, situat în cavitatea toracică între plămâni, deasupra diafragmului, în spatele plastronului sterno-costal și în fața coloanei vertebrale.
1.2. CONFIGURAȚIA INTERNĂ
Cordul este împărțit în patru cavități de doi pereți numiți septuri (figura 1.1). Septul longitudinal împarte inima în două părți: inima dreaptă (venoasă), respectiv inima stângă (arterială). Septul transversal împarte fiecare inimă în două cavități: atriu – spre baza inimii, respectiv ventricul – spre vârful inimii. Partea septului longitudinal dintre atrii se numește sept interatrial (sept ia) și cea dintre ventriculi, sept interventricular (sept iv). Septul transversal se numește sept atrio-ventricular (sept av) [1].
Fig.1.1.
1.3. CICLUL CARDIAC
Cordul poate fi considerat ca un sistem electric care generează stimuli, plus un sistem mecanic care răspunde la stimuli prin contracții. Aceste două sisteme lucrează ritmic.
Ciclul cardiac (revoluția cardiacă) reprezintă totalitatea proceselor ce decurg sinergic în sens transversal și succesiv în plan longitudinal în inimă, pornind de la un moment dat și până la apariția unui moment identic.
Activitatea electrică a inimii pe parcursul unui ciclu cardiac cuprinde generarea unui stimul în nodulul sino-atrial și transmiterea lui în întregul miocard, având ca efect depolarizarea și apoi repolarizarea țesutului contractil într-o secvență bine precizată: a) depolarizarea atrială, b) repolarizarea atrială, c) conducerea excitației prin sistemul joncțional atrio-ventricular, d) depolarizarea ventriculară, e) repolarizarea ventriculară, f) diastola electrică generală.
Activitatea mecanică a inimii pe parcursul unui ciclu cardiac cuprinde contracția și apoi relaxarea țesutului contractil atrial și ventricular, într-o secvență bine precizată, având ca efect forțarea circulației sângelui în arborele vascular: a) sistola atrială, b) diastola atrială, c) sistola ventriculară, d) diastola ventriculară, e) diastola generală.
1.4. ACTIVITATEA ELECTRICĂ A CORDULUI
Activitatea electrică a cordului este determinată de activitatea țesutului specific (ca și cauză) și a țesutului contractil (ca efecte), bazat pe o parte a proprietăților fundamentale ale cordului.
1) Funcția cronotropă (automatismul) constă în capacitatea țesutului specific de a se autoexcita, generând spontan și ritmic stimuli.
Evoluția potențialului de acțiune al celulelor de țesut specific prezintă o fază suplimentară (figura 1.2): după încheierea repolarizării apare o creștere spontană, lentă, a diferenței de potențial de la valoarea potențialului de repaus spre valoarea potențialului de prag, numită depolarizare diastolică spontană (DS); la atingerea valorii de prag apare depolarizarea – repolarizarea; apoi fenomenul se repetă ritmic.
Fig.1.2.
Automatismul este prezent la toate nivelele țesutului specific, dar cu ritmuri diferite: 60 ori/min … 80 ori/min pentru nodulul sino-atrial; 40 ori/min … 60 ori/min pentru nodulul atrio-ventricular; aproximativ 40 ori/min pentru fasciculul His; 20 ori/min … 30 ori/min pentru rețeaua Purkinje.
În cazul nefuncționării / funcționării incorecte a centrului de ritm superior sau al întreruperii conducerii stimulului, se impune ritmul următorului centru.
2) Funcția dromotropă (conductibilitatea) constă în capacitatea țesutului specific de a conduce stimulii spre țesutul contractil.
3) Funcția batmotropă (excitabilitatea) constă în capacitatea țesuturilor specific și contractil de a răspunde la stimuli naturali și electrici, depolarizându-se. Potențialul de acțiune PA pentru o fibră miocardică este prezentat în fig.1.3.
Fig.1.3.
O caracteristică foarte importantă este inexcitabilitatea periodică: după excitarea celulei miocardice, aceasta intră într-o fază refractară până la sfârșitul repolarizării, cu următoarele faze (fig.1.3): a) perioada refractară absolută (PRA), în care celula nu răspunde la nici un nou stimul; b) perioada refractară relativă (PRR), în care celula răspunde incomplet numai la stimuli de intensitate mare; c) perioada de excitabilitate supranormală (PES), în care celula răspunde la stimuli de intensitate mai mică decât pragul de excitație. Ultima perioadă este vulnerabilă, un stimul în această perioadă putând produce tulburări grave (de exemplu fibrilație ventriculară).
Pe ansamblul inimii rezultă următoarele faze de activitate electrică, identificabile pe electrocardiograma normală (fig.1.4):
Fig.1.4.
– depolarizarea atrială este reprezentată de unda P;
– depolarizarea ventriculară este reprezentată de complexul QRS (undele Q, R și S);
– repolarizarea atrială este mascată de complexul QRS;
– repolarizarea ventriculară este reprezentată de unda T;
– din cauze necunoscute poate să mai apară unda U.
Între două unde succesive se definesc segmente: PQ, ST, TP.
Între două repere ale traseului electrocardiografic se definesc intervale: P-Q, Q-T, S-T, P-P, R-R.
1.5. ACTIVITATEA MECANICĂ A CORDULUI
4) Funcția inotropă (contractilitatea) constă în capacitatea țesutului contractil de a se contracta atunci când este excitat.
Pe ansamblul inimii rezultă următoarele faze de activitate mecanică a inimii pe durata unui ciclu cardiac:
– sistola atrială reprezintă punerea sub tensiune a atriilor, apoi expulzarea sângelui din atrii în ventriculi;
– sistola ventriculară reprezintă punerea sub tensiune a ventriculilor, apoi expulzarea sângelui din ventriculi în artere;
– diastola atrială reprezintă relaxarea atriilor, apoi umplerea lor cu sânge din vene;
– diastola ventriculară reprezintă relaxarea ventriculilor, apoi umplerea lor cu sânge din atrii;
– diastola generală reprezintă suprapunerea dintre cele două diastole.
1.6. ELECTROCARDIOGRAFIE
Electrocardiografia (ECG, EKG) reprezintă tehnica de investigare a activității electrice cardiace în timp (“grafie” – reprezentare grafică a semnalului, “scopie” – vizualizare).
Semnalul ECG este un semnal bioelectric cu amplitudini în domeniul 0,1 mVvv … 2 mVvv (pentru măsurători la suprafața corpului) și spectru de frecvențe de 0,05 Hz … 100 Hz (aproximativ, dependent de aplicație).
1.6.1.GENERALITĂȚI
Într-o primă aproximație, inima poate fi reprezentată printr-o sursă de tensiune variabilă în timp sau ca un dipol variabil (vectorul cardiac) într-un mediu conductor. Vectorul cardiac este considerat cu origine fixă (în centrul electric al inimii) și cu direcție, sens și mărime variabile în timp.
Vectorul cardiac este studiat prin proiecții ale sale într-un sistem de trei planuri ortogonale numite planuri fundamentale (figura 1.5): frontal – xOy, transversal – xOz și sagital – yOz.
Fig.1.5.
În ECG proiectarea vectorului cardiac se face pe anumite drepte, numite derivații, situate în planurile fundamentale și determinate de cele două puncte ale corpului în care se plasează electrozii.
Tipuri de derivații:
1) Derivații:
– bipolare – se măsoară diferența dintre două potențiale ale câmpului electric cardiac,
– unipolare – se măsoară diferența dintre un potențial al câmpului electric cardiac și un potențial considerat nul sau de referință.
2) Derivații:
– directe – electrozii sunt plasați pe / în inimă,
– indirecte – electrozi plasați pe suprafața corpului.
3) Derivații:
– frontale – în planul xOy;
– transversale – în planul xOz,
– sagitale – în planul yOz.
4) Derivații:
– ale membrelor – electrozii sunt aplicați pe membre, potențialul este același, indiferent de punctul de aplicare al electrodului pe membru,
– ale toracelui – electrozii sunt aplicați pe torace, potențialul depinde de punctul de aplicare al electrodului.
1.6.2. DERIVAȚIILE STANDARD
Derivațiile standard (figura 1.6) sunt derivații bipolare, indirecte, în planul frontal, ale membrelor:
– derivația DI = LA – RA, între brațul stâng și brațul drept,
– derivația DII = LF – RA, între piciorul stâng și brațul drept,
– derivația DIII = LF – LA, între piciorul stâng și brațul stâng.
Fig.1.6
1.6.3. DERIVAȚIILE UNIPOLARE ALE MEMBRELOR
Derivațiile unipolare ale membrelor (figura 1.7) sunt derivații unipolare, indirecte, în planul frontal, ale membrelor:
– derivația VR = RA – VW, între brațul drept și un potențial de referință, VW;
– derivația VL = LA – VW, între brațul stâng și VW;
– derivația VF = LF – VW, între piciorul stâng și VW.
Fig.1.7
Potențialul de referință VW (Wilson) se obține prin medierea celor trei potențiale ale membrelor:
.
Rezultă:
.
1.6.4. DERIVAȚIILE UNIPOLARE ALE MEMBRELOR, AUGUMENTATE
Derivațiile unipolare ale membrelor, augumentate (figura 1.8) sunt derivații unipolare, indirecte, în planul frontal, ale membrelor:
– derivația aVR = RA – VWGR, între brațul drept și un potențial de referință, VWGR;
– derivația aVL = LA – VWGL, între brațul stâng și un alt potențial de referință, VWGL;
– derivația aVF = LF – VWGF, între piciorul stâng și un alt potențial de referință, VWGF.
Fig.1.8
Potențialele de referință VWG (Wilson – Goldberger) se obțin prin medierea celor două potențiale ale membrelor care nu sunt aplicate la intrarea ““ a amplificatorului. Rezultă:
,
Rezultă că proiecțiile acestor derivații în triunghiul lui Einthoven sunt pe aceleași direcții ca VR, VL, VF, dar amplificate, din care cauză sunt preferate.
1.6.5. DERIVAȚIILE PRECORDIALE
Derivațiile precordiale (figura 1.9) sunt derivații unipolare, indirecte, în planul transversal, ale toracelui:
– derivațiile
, i = 1, 2, … , 6,
între electrodul Ei și potențialul Wilson, VW.
Fig.1.9
1.6.6. DERIVAȚIILE ESOFAGIENE
Derivațiile esofagiene sunt derivații unipolare, indirecte, în plan sagital, ale toracelui:
– derivațiile
,
între electrodul Ex și potențialul Wilson, VW unde x reprezintă distanța, exprimată în centimetri, de la arcada dentară până la electrodul – sondă, introdus prin esofag.
În general se folosesc derivațiile DI, DII, DIII, aVR, aVL, aVF, V1, V2, V3, V4, V5 și V6.
1.6.7. SCHEMA BLOC A ELECTROCARDIOGRAFULUI
Schema bloc de principiu a unui electrocardioscop (pentru vizualizare) / electrocardiograf (pentru înregistrare) este prezentată în figura 1.10. (pentru un canal de culegere).
Fig.1.10
Blocul de recoltare, BR, cuprinde electrozii amplasați pe corpul subiectului și firele de legătură. Repetorii de intrare, RI, asigură o impedanță de intrare mare. Selectorul de derivații, SD, selectează una dintre derivațiile realizate. Generatorul de semnal de test, GST, furnizează un impuls dreptunghiular de 1 mV utilizat pentru etalonare. Preamplificatorul diferențial, PAD, realizează o primă amplificare a semnalului util. Blocul de izolare, I…ZO, asigură izolarea galvanică a circuitului de pacient de restul echipamentului. Blocul de amplificare și filtrare, A+F, realizează amplificarea necesară comandării blocului următor (reglabilă în trepte și continuu), încadrarea semnalului în banda de frecvențe semnificativă (0,05 Hz … 100 Hz) și rejecția zgomotului (filtrare oprește – bandă pe 35 Hz … 45 Hz pentru rejecția artefactelor musculare, filtru ac pe 50 Hz pentru rejecția rețelei). Osciloscopul, OSC, respectiv înregistratorul grafic, IG, permit vizualizarea, respectiv înregistrarea pe hârtie a traseului ECG.
=== Capitol 2 ===
CAPITOLUL 2
NOȚIUNI DE ANALIZĂ SINTACTICĂ
2.1. STRUCTURA ȘIRURILOR
Cea mai simplă descriere structurală este reprezentarea formei de studiat ca un șir ordonat de componente elementare. Prezența sau absența acestor componente, ca și poziția lor relativă, caracterizează forma globală. Compararea a două astfeI de descrieri permite masurarea asemănării dintre forme și deci o tehnică de recunoaștere.
2.1.1 ALFABET, CONCATENARE, ȘIR
Definiția 1: Se numește alfabet, X, un ansamblu finit. Elementele sale, numite litere, se vor nota cu a, b, c, …( În recunoașterea formei, literele alfabetului sunt formele elementare distincte rezultate din preprocesare).
Definiția 2: Se numește frază în X, x, un șir ordonat de elemente din X, reprezentat prin simpla juxtapunere (concatenare) a acestor elemente.
Definiția 3: Lungimea frazei, |x|, este numărul de elemente pe care le are fraza. Terminologia nu este bine fixată. În teoria limbajelor, o literă poate fi numită și simbol, o frază poate fi numită ”cuvânt” (mai corect, deoarece este alcatuită din litere) sau ”șir” sau “listă” . În continuare, termenii de ”șir” și ”frază” vor reprezenta același lucru.
Exemplu: Alfabet: X = {a, b, c}. Frază în X: x = b c a a b. Lungimea frazei este |x|= 5.
Definiția 4: Fraza vidă, X, este șirul de litere de lungime nulă.
Notație: Se noteaza convențional fraza: x=aa…a=an .
Definiția 5: Ansamblul frazelor din X se noteaza cu X*. Ansamblul frazelor din X se notează cu X+.
Definiția 6: X* permite operația internă asociativă de concatenare, definită prin:
Fie x, y є X* cu x=x1…xn, y=y1…ym . Atunci z = x y = x1…xny1…ym є X Această operație nu este în general comutativă și are λ ca element neutru.
Definiția 7: y є X* se numește subfrază a frazei x є X* dacă există în X* 2 fraze u și v astfel încât: x = u y v. u se numește prefix și v se numește sufix.
2.1.2. COMPARAREA ȘIRURILOR
În cazul în care o formă de studiat a fost descrisă cu un șir, pentru a o putea recunoaște, trebuie comparată cu prototipuri descrise în același mod. O asffel de comparație necesită algoritmi al căror scop este de a furniza o măsură a asemănării între două șiruri scrise cu același alfabet.
Nu se pot folosi comparații prea directe, cum ar fi distanța Hamming (aceasta presupune că lungimea celor două șiruri este identică, ceea ce în general nu se întâmplă). În continuare se prezintă doi algoritmi mai supli, unul pentru a testa incluziunea unui șir în altul, celălaIt care măsoară costul minimal pentru a transforma un șir în altul.
a) Incluziunea șirurilor
Introducere
În procesarea structurală a datelor, este util să se poată testa rapid dacă șirul y, de lungime l, este un subșir al șirului x, de lungime n. Aceasta permite, de exemplu, extragerea dintr-o frontiera a tuturor părților asemănătoare cu un prototip dat, sau evidențierea unei părți de formă caracteristică într-un semnal. Mai general, se poate realiza o codare mai abstractă a formei y, descompunând-o în subșiruri tipice. Acest tip de algoritm (”string pattern matching”) folosește un fel de corelație binară, deplasând, în manieră mai mult sau mai puțin explicită, o fereastră corespunzând lui y pe șirul x. Soluția cea mai rapidă cunoscută este ”en moyenne de complexite sous – lineaire par rapport a n”. Aici se prezintă metoda lui Morris și Pratt, care este de complexitate liniară.
Principiul algoritmului
Fie y = b1 … bl subfraza care s-ar putea găsi în fraza x = a1… an. x și y sunt fraze din același alfabet, cu n ≥ l. În esență, se manipulează un pointer P, a cărui valoare indică lungimea celui mai lung prefix al lui y recunoscut ca subfrază a lui x. Se introduce pentru început elementul a1 al lui x. Dacă a1 = b1, atunci P = 1 și dacă a1≠b1, atunci P = 0. Apoi se introduce a2. Presupunem că dupa ce am introdus a1 … ak, s-a identificat prefixul b1 … bj; al lui y. Atunci, valoarea pointeruiui este P = j. Dacă ak+1 = bj+1, atunci P = j + 1. Dacă ak+1 ≠ bj+1, atunci trebuie să i se dea lui P o valoare i < j, astfel încât:
ak+1 = bi;
b1 … bj este un sufix al lui a1 … ak
b1 … bj este cel mai Iung prefix al lui y = b1 … bl care satisface cele două proprietăți precedente.
Schematic, aceasta revine la a trece de la situația:
la situația:
(Convenția grafică este că literele care sunt situate pe aceeași verticală în schemă sunt identice).
De exemplu:
x=abaabaabb…
y=baabb…
baabba…
Avem aici: k = 5, j = 4, i = 5.
Se adeverește că, cunoscând j, indicele i poate fi dedus o dat pentru totdeauna cu ajutorul unei funcții care nu depinde decât de y. Calculul se face prin recurență în modul următor:
f(1) = 0, pentru că o întrerupere în aceast etapă nu poate duce decât la începutul lui y.
Dacă se cunosc f(1), f(2), …, f(j), cu f(j) = i – 1, se spune ca b1 … bj+1; este cel mai mare sufix al lui b1 … bj care este un prefix al Iui b1 … bl.
Deci, dacă bj+1 ≠ bi, se va căuta, aplicând de m ori f lui j, să se găsească unul din cele două rezultate de mai jos:
f(m)(j) = u și bu+1 = bj+1,
f(m)(j) = 0 și bj+1 ≠ b1.
În cazul 1), s-a găsit cel mai mare sufix al lui b1 … bj+1, care este un prefix al lui b1 … bl , el conține u + 1 eIemente, deci f(j + 1) = u +1.
În cazul 2), nici un sufix al lui b1 … bj+1, nu este prefix al lui b1 … bl, el conține u + 1 elemente, deci f(j + 1) = 0.
Algoritmul de calcul al lui f se scrie astfel:
f(1): 0
Pentru j: = 2 …
se face u: = f(j – 1)
Atât timp cât bj ≠ bu+1, și u > 0 ;
se face u: = f(u)
Dacă bj ≠ bu+1 , și u =0
se face f(j): = 0
alffel se face f(j): = u + 1
Funcționarea algoritmului
Se reprezintă fraza y printr-un graf în care tranzițiile sunt marcate cu litere și nodurile sunt marcate cu valoarea lui P. Pentru exemplul:
y=aabbaab
Se calculează funcția f, care în acest caz are valorile:
i 1234567
f(i) 0100123
Se adaugă la graf tranzițiile induse de f. De exemplu, f(4) = 0: se adaugă săgeata care leagă nodul 4 la nodul 0. În plus, se adaugă la starea 0 o buclă care are ca obiect literele din X care nu se află pe arcul dintre nodurile 0 și 1 (”starturi false”) . Se obține în acest caz:
Apoi se încearcă să se parcurgă o suită de tranziții adiacente, pornind de la starea 0, pentru a se ajunge la starea 7. Suita acestor tranziții trebuie să producă suita de litere din fraza x.
Suita de noduri parcurse este următoarea:
a b a a b a a b b a a b
0→1 0→1→2→3 1→2→3→4→5→6→7
↓ ↓
0 0
Nodul de sosire este nodul 7. Deci y este subfrază a lui x.
Alți algoritmi
Din aceeași familie, există algoritmi care calculează cel mai lung subșir comun între doua șiruri. Alți algoritmi caută cea mai lungă secvența y în x (numită ”motiv”), astfel încat:
x=uy2x
ceea ce poate servi la evidențierea regularităților.
b) Distanțe între șiruri
Introducere
O măsură mai sofisticată a asemănării între șiruri trebuie să facă să intervină o distanță non – binară între literele alfabetului, adică trebuie să poată să atribuie o contribuție ponderată confuziei dintre două elemente constitutive ale unei forme, după asemănarea locală a acestor elemente. În plus, ea trebuie să se elibereze de constrângerea lungimii egale, care este nereală. Aceste caracteristici sunt îndeplinite de algoritmul optimal de corecție a unui șir într-altul, creat de Wagner și Fischer, care definește distanța de editare între șiruri. În cazul în care optimalitatea teoretică nu este necesară, ci viteza de calcul este importantă, pot fi utilizate metodele de comparare dinamica. Se va prezenta un exemplu dupa prezentarea algoritmului lui Wagner și Fischer.
Calculul ”distanței de editare” cu algoritmul Wagner – Fischer
Se definesc trei operații elementare posibile, a căror combinare va permite transformarea unui șir în altul. Aceste operații se aplică literelor alfabetului și li se atribuie un cost individual. Aceste operații sunt:
• substituția: a→b cost γ(a, b),
• inserția: λ→a cost γ(λ, a),
• anularea: a →λ cost γ(a, λ).
Astfel, fraza x = a b poate fi transformată în y = b a c prin următoarele operații elementare:
(λ→c), (b →λ,), (c→b), (λ→c)
care dau următoarea succesiune de fraze:
a b, c a b, c a, b a, b a c.
Transformarea totală are un cost:
γ(λ, c) + γ(b, λ) + γ(c, b) + γ(λ, c).
Se definește distanța de editare δ(x, y) între două fraze x și y ca fiind costul șirului de transformări elementare cel mai rentabil pentru a transforma x în y (aceasta distanță se numește ”distanța Levenstein” în teoria codării).
Pentru a calcula δ(x, y) evitând o explozie combinatorie inutilă, este necesară impunerea unei constrângeri naturale:
δ(a, b) = γ(a, b).
Altfel spus, modalitatea cea mai simplă de a transforma șirul a în șirul b trebuie sa fie pur și simplu schimbarea literei a în litera b. Acest lucru este echivalent cu inegalitatea triunghiulară:
γ(a, b) + γ(b, c) ≥ γ(a, c). Condiția impusă este ca funcția y sa fie într-adevăr o distanță. Această condiție permite găsirea transformării cu un cost minirnal într-un subansamblu finit, printr-un algoritm simplu. Se definește deci un tip de transformare particulară, numită urmă, corespunzând schemei următoare:
x =a1 a2 a3 … an
│
y = b1 b2 … bn-1 bn
Literele legate de o linie indică o operație de substituție. Cele nelegate indică o inserție sau o distrugere. Se impune în plus într-o urmă ca două linii sa nu se intersecteze și, în particular, ca să nu plece sau să nu ajungă la aceeași literă.
Aici x este transformat în y prin operațiile:
(a1→b1), (a2→λ,), (a3→b2),…,(an→bn-1), (λ→bn).
Se poate demonstra acum proprietatea fundamentală pe care se bazează algoritmul.
Proprietate: Costul unei transformări cu cost rninimal între două fraze este egal cu costul unei urme cu cost minimal între cele două fraze. Demonstrația se bazează pe proprietatea de distanță impusă matricii.
Forma particulară a urmelor permite apoi inducerea unei relații de recurență pentru transformarea cu cost minimal. Notăm:
x=a1 …an,
y=b1 … bm,
x(i) = a … ai,
│D(i – 1, j – 1) + γ(ai, bj)
D(i, j) = Min │D(i – 1, j)+ γ(ai, λ,)
│D(i, j – 1) + γ(λ, bj)
Demonstrația se bazează pe forma particulară a urmelor, care permite să se procedeze de la stânga la dreapta pas cu pas, pentru că liniile urmelor nu se intersectează. Aditivitatea criteriului de cost în raport cu costurile elementare permite utilizarea unei metode de programare dinamică, tradusă de formula de recurență indicată. Algoritmul de calcul al lui δ este:
1) D(0.0) = 0
2) Pentru i: =1,2, …, n
Se face D(i, 0): = D(i – 1,0) + γ(ai, λ)
3) Pentru j: =1, 2, …, m
Se face D(0, j): = D(0, j – 1) + γ(λ, bj)
4) Pentru i: =1,2, …, n
Pentru j: =1,2, …, m
Se face m1 = D(i – 1, j – 1) + γ(ai, bj)
m2 = D(i – 1, j) + γ(ai, λ)
m3 = D(i , j) + γ(λ, bj)
D(i, j) = Min(m1, m2, m3)
5) Distanța de editare este δ(x, y) = D(n, m)
Compararea dinamică
Ansamblul metodelor de comparare dinamică poate fi privit ca o parte a algoritmilor generali de cercetare heuristică în grafuri de stări. Ele sunt prezentate aici de manieră independentă, deoarece pot fi privite și ca metode suboptimale analoage cu metoda Wagner și Fisher.
Dispunem de două șiruri:
x= a1…an
y= b1…bm
Ideea este de a umple matricea D( i, j) ]n care elementul curent indică distanța (optimală, dacă este posibil) între:
x(i) a1…an și
y(j) b1…bm, impunând constrângeri, explicite sau nu, indicilor elementelor care se calculează. Aceste constrângeri permit reducerea timpului de calcul al algoritmului optimal, care este proporțional cu nm.
Reprezentarea problemei se poate face trasând un plan (i, j) și căutând un traseu discret de la (1, 1) la (n, m), așa cum se arată în figura 2.3. Acest traseu va indica cuplajul între indicii celor două șiruri care corespund corespondenței cea mai rentabilă.
Fig.2.1.
Diferența între constrângerile de cuplaj impuse aici și cele cerute pentru algoritmul precedent constă in faptul că aici o literă poate corespunde la mai multe din cealaltă frază și nici o literă nu este transformată în literă vidă. Bineînțeles, se impune ca curba de legătură să fie monotonă și continuă și capetele ei să fie punctele (1, 1) și (n, m). O curbă de legătură (”warping function” sau funcție de deformație) este deci constituită din segmente orizontale, verticale sau diagonale. Algoritmul de comparare dinamică (”dynamic pattern matching”) poate fi descris ca o optimizare locală a distanței cumulate dintre cele două fraze.
Notăm cu d(i, j) distanța între elementele ai și bj ale alfabetului si cu D(i, j) distanța cumulată, calculată între x(i) și y(j). Forma cea mai simplă a aIgoritmului constă în a calcula:
D(i, J – 1)+ d(i, J)
D(i,j)=Min D(i – 1,j – 1)+2 d(i,j).
D(i – 1, j)+ d(i, j)
Dacă se dorește evitarea calculului tuturor valorilor lui D, se poate restrânge calculul la un culoar diagonal, de exemplu: j – r ≤ i ≤ j + r. Distanța între x și y va fi:
Acest tip de algoritm a fost utitizat în mod constant, începând cu 1970, în recunoașterea vorbirii.
Alți algoritmi
Algoritmul Wagner – Fischer a fost generalizat astfel încat să accepte o transformare eIementară suplimentară, cea de permutare a două litere adiacente. Ordinul de mărime a complexității acestui algoritm rămâne neschimbat.
2.2. STRUCTURI SINTACTICE REGULATE
Se prezintă un instrument care permite crearea unei familii de fraze pe baza unui alfabet: gramaticile formale. Au fost introduse prima dată de N. Chomsky (1956) în scopul modelării limbajelor naturale, dar, paradoxal, s-au dovedit mult mai utile în analiza limbajelor de programare și recunoașterea formei.
Din acest punct de vedere, o gramatică formală este o ”mașină” de construit fraze care au toate în comun o anumită structură. Această structură comună trebuie să permită clasificarea formelor corespunzând frazelor ca aparținând aceleiași clase. Astfel, în anumite cazuri, acestor modele li se pot asocia algoritmi de analiză rapidă care pot decide dacă o anumită frază poate fi produsă de o anumită gramatică.
Se vor prezenta în acest capitol cele mai simple gramatici formale: gramaticile regulate și instrumentele de analiză asociate: automatele finite.
2.2.1. DEFINIȚII
Definiția 1: Se numește limbaj pe un alfabet X orice parte a lui X’.
Exemple:
L = {x є X* /│x│par}
L = {x є {a, b} / numărul de a în X = numărul de b in X}
L = {a, aa, aaa}
L={λ}
L=Φ
Definiția 2: Produsul sau concatenarea a două limbaje se definește prin:
LL = {xy│ x є L1, y є L2}.
Exemplu:
L = {a, abc}
L = {bcd, d}
L1L2 = {abcd, ad, abcbcd}
Definiția 3. Inchiderea unui limbaj L, notată L*, se definește prin:
L0 ={λ},
Ln = L Ln-1, n ≥1,
L* =U Ln, n≥0.
Se definește de asemenea: L+ ULn LL* L*L, n ≥ 1,
Pentru a reprezenta comod anumite limbaje infinite cu un număr finit de simboluri matematice, dispunem de gramatici formale care ierarhizează ansamblul de limbaje după complexitatea structurii lor sintactice.
Definiția 4. Se numește gramatică:
G = (X, V, S, P),
unde X este alfabetul în care sunt scrise frazele limbajului generat, V este un alfabet auxiliar sau nonterminal, S este un element al lui V numit axiomă, P este un ansamblu de reguli de producție.
O regulă de producție este de forma:
α→β
unde α є (V U X)* V (V U X)* ? și β є (V U X)*.
2.2.2. GENERAREA UNEI FRAZE DE CĂTRE O GRAMATICĂ
Fie γє (V u X)*. Se spune că γ este rescrisă în δ de regula α→β când se poate descompune γ in forma:
γ=γ1αγ2
γ=γ1βγ2
Atunci se notează: γ=>δ .
Deci o regulă de productie permite transformarea anumitor fraze scrise în (X U V) în alte fraze.
Procedeul generativ asociat gramaticii constă în a porni de la axioma S și a o rescrie ca o frază γ1 cu una din regulile lui P. Apoi a rescrie γ1 ca γ2 cu una din regulile lui P etc. Dacă o frază γn este compusă doar din simboluri ale lui X, ea nu mai poate fi rescrisă, prin definiția unei reguli de producție. Atunci se spune că ea aparține limbajului generat de G.
S=> γ1=> γ2=>…=> γn є X* sau S=>* γi, i = 1, …, n unde γn є L(G).
Exemplu :
G = (X, V, S, P)
X = {a, b}
V = {S, A}
P: S aS (1)
S bA (2)
bA bbA (3)
A a (4)
2.2.3. GRAMATICI REGULATE. AUTOMATE FINITE
a) Gramatici regulate
Definiția 5: O gramatică se numește regulată atunci când regulile ei de producție sunt de forma: A →aB sau A→ a,
unde: A, B є V, a є X.
Exemplu:
O frază generată de G este:
S → aS → aaS → aabA → aaba
Se poate constata că:
L(G) = {anbm a │ n ≥ 0, m ≥ 1}.
Un limbaj generat de o gramatică regulată se numește limbaj regulat. Gramaticile, respectiv limbajele regulate se numesc și raționale sau Kleene sau de stări finite. Proprietățile limbajelor regulate sunt mai ușor de descris folosind un formalism echivalent gramaticilor regulate, cel al automatelor finite.
b) Automate finite
Definitia 6: Se numește automat finit: A = (X, Q, δ, q0, Q’)
unde: X este un alfabet, Q este un ansamblu finit de stări, q0 є Q este starea inițială, Q’ Q este ansamblul de stări finale, δ: Q x X → Q este funcția de tranziție.
Reprezentare grafică:
O stare q se reprezintă grafic:
O tranziție q’= δ(q, a):
Starea inițială q0:
O stare finală qF є Q’:
Limbaj acceptat de un automat finit
Un automat finit servește la definirea unui limbaj pe X. Se numește configurație cuplul (q, x) unde q є Q și x є X.
Se spune că configurația (q, x) generează configurația (q, x) și se notează: (q, x) → (q1, x1) când: x = ax1 și δ(q, a) = q1.
Dacă:
(q, x) →( q1,x1) →…→(qn,xn),l
aceasta se notează:
(q, x) →* (qn, xn)
Limbajul acceptat de automatul A = (X, Q, δ, q0, Q’) este definit de: L(A) = {x є X*: (q0, x) → (qF, λ) și qF є Q’}.
Deci o frază x = a1 a1 …an este acceptată de A dacă, pornind de la starea inițială, se pot găsi in graful lui A un șir de arcuri ce poartă succesiv literele a1 a1 …an și care conduce la o stare finală.
Extinzând notația, se poate scrie:
(q, x)→* (q’,λ), unde x є X*, în forma:
δ(q, x) = q’, ceea ce revine la:
δ(q, a1 a1 …an) = δ(… δ( δ(q, a1), a2), …), an).
În continuare se consideră doar automatele cu toate stările accesibile. adică:
√ q є Q, З x є X* a.î. δ(q0, x) = q sau
√ q є Q, З x є X* a.î. δ(q0, x) →* (q, λ).
Automate incomplet specificate
În cazul în care funcția δ nu este definită pe întregul Q x X, automatul se numește incomplet specificat sau incomplet. În acest caz el poate fi completat, fără a modifica limbajul pe care il acceptă, adăugând o stare nonterminală qp. Această stare este adeseori denumită stare puț sau stare pubelă. Pentru orice tranziție δ(q, a) nedefinită se impune în acest caz:
δ(q, a1)= q0 și, în plus,
√ x є X, b(qp, a) = qp, qp ¢ Q’,
ceea se reprezintă grafic prin:
Automate nedeterministe
O extensie a definiției automatelor finite poate fi făcută în cazul în care δ ia valori din P(Q), mulțimea elementelor lui Q, adică atunci când funcția de tranziție e o aplicație multivocă.
Se spune atunci că automatul este nedeterminist: unei perechi (a,q)X∙Q îi corespunde o mulțime de stări.
Grafic:
δ(q,a)=(q1,q2)
Un automat nedeterminist acceptă un limbaj în mod analog unui automat determinist, definind simplu succesiunile de configurații astfel:
(q,x)→ (q1,x1)
unde: x=a∙x1
q1=δ(q,a)
Totuși, analiza sintactică a unei fraze printr-un automat nedeterminist este mai complexă decât dacă automatul este determinist (trebuie păstrate în memorie alternativele caracteristice ale tranzițiilor multiple). Se dispune aici de o teoremă importantă:
Fie un limbaj L astfel încât L=L(A), unde A este un automat finit nedeterminist. Există atunci A`, automat finit determinist astfel încât L=L(A`).
Algoritmul practic de determinare a unui automat finit constă în a crea o funcție de tranziție δ` pornind de la definiția lui A`. Există totuși stări ale lui Q’, ele nefiind accesibile lui A`. Se construiesc succesiv stările necesare, plecând de la q0’= și urmând definiția lui δ`. În majoritatea cazurilor numărul acestor stări este mai mic de .
În cazul automatelor finite nedeterministe, analiza unei fraze din X* poate duce la ambiguități.
Definiția 7: Se spune că o frază din X* este ambiguă pentru un automat finit dacă ea este acceptată în cel puțin două cazuri distincte de acest automat.
Nici o frază din X* nu este ambiguă pentru un automat determinist.
Gramatica regulată și automatul finit
Corespondența dintre gramatica regulată și automatul finit este directă: starea inițială a automatului corespunde axiomei gramaticii; cele 2 alfabete sunt identice; regulile de producere corespund funcției de tranziție în modul următor:
A aB
A a
Dacă se dorește, în plus, ca funcția δ să fie specificată în întregime, se poate introduce o stare pubelă. Automatul finit construit plecând de la gramatica regulată, în general nu este determinist.
Se obține direct rezultatul următor:
Familia limbajelor (într-un alfabet X) recunoscute de un automat finit e aceeași cu cea a limbajelor (pe X) create de o gramatică regulată.
Proprietățile limbajelor regulate
Principalele proprietăți algebrice ale limbajelor regulate sunt: închiderea pentru: reuniune, produs, conjugare, intersecție, complementare.
Toate limbajele finite sunt regulate.
Automate derivate
Fie A=(X,Q,δ,Q’) un automat finit și P=(P1,…Pr) o partiție a lui Q.
Definiția 8: Se numește automat derivat din A pentru partiția P, automatul finit: A’=(X,P,ν,P0,R)
unde: i) P0 є P a.î. q0 є P0
ii) R= { Pi є P│ Э qj є Q’, qj є Pi }
iii) ν(Pi, a) = Pj, dacă Э qk є PI și qk є Pj a.î. δ(qk, a) = qe
Un automat derivat este, deci, construit amestecând stările automatului inițial; aceasta operație stă la baza metodelor de analiză gramaticală regulată.
O proprietate importantă a automatelor derivate care rezultă direct din definiție:
Fie A un automat finit și A’ un automat derivat din A. Pentru o partiție oarecare de stări ale lui A, avem:
L(A)L(A’).
c) Reprezentarea limbajelor prin expresii regulate
Expresiile regulate sunt un formalism ce permit definirea părților raționale ale unei mulțimi X*, adică familia limbajelor raționale pe X. Teorema lui Kleene asigură că familia limbajelor raționale e aceeași cu cea a limbajelor regulate.
Expresii regulate
Fie 2 alfabete disjuncte, X și X’={+,*,Φ,(,)}.
Definiția 9: O frază α pe XX’ este o expresie regulată dacă și numai dacă: 1) α є X sau α = Φ
2) α se scrie într-unul din modurile:
(β+γ) sau (βγ) sau (β*),
cu β și γ expresii regulate din X.
O expresie regulată α reprezintă un limbaj Lα pe X prin intermediul următoarelor convenții:
1. Limbajul notat cu Φ este limbajul vid.
2. Limbajul notat cu a este limbajul │a│
3. L(β+γ) = LβULγ; L(βγ) = LβLγ; Lβ*= (Lβ)*
Pentru a simplfica scrierea expresiilor regulate, se desfac din paranteze adoptând următoarele priorități în ordine descrescătoare pentru operații: operația de conjugare, produs, reuniune.
În plus, se va confunda adesea, prin abuz de notații, o expresie regulată α și limbajul Lα pe care îl reprezintă, care va fi notat α.
Expresiile regulate definesc așadar o familie de limbaje.
Un astfel de limbaj se numește limbaj rațional pe X sau parte rațională în X. Aceste limbaje eventual infinite sunt reprezentate printr-o notație prescurtată, care nu e un sistem de rescriere cum e ăn cazul reprezentării printr-o gramatică.
Proprietățile algebrice ale acestei femilii de limbaje pot fi rezumate prin următoarea proprietate ce decurge direct din definiție:
Familia limbajelor raționale e cea mai mică familie închisă pentru cele trei operații: produs, reuniune, conjugare.
Teorema lui Kleene [9]
Orice limbaj regulat e rațional.
Comparând aceste proprietăți cu cele ale limbajelor regulate se constată că orice limbaj rațional e regulat; un șir de automate permite găsirea unui automat finit care acceptă același limbaj ca al celui reprezentat printr-o expresie regulată oarecare. Teorema fundamentală a limbajelor regulate asigură totodată și reciproca.
Existența a 2 tipuri diferite de reprezentare a limbajelor regulate, gramaticile regulate și automatele finite pe de o parte, și expresiile regulate pe de altă parte, conduc la punerea problemei trecerii efective de la o reprezentare la alta pentru un limbaj dat. Regulile de trecere sunt rezultatul definițiilor prezentate mai sus, dar realizările algoritmice sau practice pot fi prezentate în mod diferit.
● Fie un limbaj regulat L și un automat finit A astfel încât L=L(A). Se caută o expresie regulată α reprezentând un limbaj Lα astfel încât L(A) = Lα.
Construirea lui α se poate face utilizând direct o demonstrație a teoremei lui Kleene printr-o recurență asupra indicilor stărilor automatului. Acest algoritm e cunoscut ca algoritmul lui Mc Naughton și Yamada [9].
Proprietățile expresiilor regulate furnizează o altă metodă, în care se utilizează rezolvarea directă a ecuațiilor scrise cu variabile care sunt expresii regulate, folosind teorema lui d’Arben [3]. Acest algoritm permite găsirea lui L(A) (în mod) direct ca o soluție a unui astfel de sistem de ecuații.
● Problema inversă e de a găsi un automat A astfel încât L(A) = Lα, atunci când se cunoaște expresia regulată α.
Construcția teoretică nu oferă dificultăți pentru că proprietățile de închidere ale limbajelor regulate permit construirea de automate care recunosc reuniunea, produsul,etc. a două limbaje recunoscute de automatele date. Se știe, în plus, să se construiască un automat care recunoaște un limbaj redus la o literă a alfabetului. Un șir de astfel de construcții urmărind structura lui α permite, astfel, reconstituirea automatului A care recunoaște limbajul Lα. În practică, aceasta e adesea foarte complexă. Ginsburg [3] propune o construcție puțin diferită, care permite o trecere simplă de la o expresie regulată la un graf de tranziție care e un automat finit al cărui alfabet are cuvântul vid λ. Se poate apoi regăsi un automat finit corespunzând acestui graf de tranziție.
O altă modalitate o reprezintă extragerea directă din α a stărilor lui A, o dată cu funcția sa de tranziție. Se construiește pentru aceasta un ansamblu (care e finit) de derivate din α, fiecare corespunzând unei stări a lui α. Relațiile între aceste derivate furnizează structura lui A. Aceasta e o construcție reciprocă a rezultatelor ecuațiilor utilizate pentru problema inversă. De notat asemănarea dintre această problemă și cea a realizării circuitelor secvențiale care posedă numeroase soluții algoritmice.
2.2.4. DECIZIA ÎN STRUCTURILE SINTACTICE REGULATE
Se admite, în ipoteza recunoașterii sintactice a formelor, că o clasă de forme e reprezentată printr-un model gramatical, adică (,) că formele (reprezentate prin fraze) ce aparțin aceleași clase pot fi create prin modelul matematic indicat. Acesta este principiul de bază al metodelor sintactice.
Pentru a se face o decizie de operare, trebuie să se poată decide dacă o formă dată aparține unei clase date. Altfel spus, în reprezentare gramaticală, dacă o frază dată poate fi creată printr-o gramatică dată. Această problemă a analizei sintactice a fost studiată temeinic de informaticieni, în particular la algoritmurile de compilare.
Un sistem pur de recunoaștere sintactică se prezintă în modul următor: are n clase de forme reprezentate prin gramaticile G1…Gn.
O frază x găsită (apărută) trebuie clasată. Se face analiza sintactică a lui n pe G1…Gn și se obțin n răspunsuri binare la întrebarea: “Fraza x poate fi creată prin gramatica Gi?”.
G1 ———— 0 sau 1
x G2 ———— 0 sau 1
:
Gn ———— 0 sau 1
În cazul în care toate răspunsurile sunt negative (respingere) sau în cazul în care un răspuns și numai unul e pozitiv, decizia e simplă. În schimb, mai multe răspunsuri pozitive conduc la indecizie. Se observă, în acest caz, limitele procedeului, pentru că e puțin probabil să avem clase suficient bine separate pe de o parte și suficient de bine modelate pe de altă parte, astfel ca aceste ambiguități să apară rar. Se vor căuta deci algoritmi mai supli, redând o potrivire non-binară a frazei la gramatică. În cazul regulat poate fi făcută o generalizare a distanței de editare între fraze, problemă studiată în următorul paragraf.
Un alt caz este acela în care datele de intrare nu se prezintă ca o frază ci ca o multitudine potențială de fraze (adesea numită latice). Este cazul când segmentarea formei de intrare e făcută în mod suplu și etichetarea fiecărui segment printr-o literă a alfabetului nu este unică. Un bun exemplu este cel al recunoașterii unui cuvânt printr-un sistem de recunoaștere a fonemelor (sunete elementare).
Pentru a analiza o asemenea latice de fraze printr-o gramatică regulată, o abordare combinatorie simplă este prea grosieră. Se utilizează metode de parcurgere euristică a grafului, care se bazează totdeauna pe tehnica de bază a analizei sintactice.
Analiza sintactică a limbajelor regulate
Problema analizei sintactice, adică să se decidă dacă o frază dată aparține sau nu unui limbaj definit printr-o gramatică dată G, se rezolvă simplu în cazul în care G este regulat sau când limbajul este reprezentat printr-un automat.
Algoritmul este următorul pentru un automat complet specificat:
Fie x = a1 a2… an є N
Fie A= ( X, Q, δ, q0, Q’)
Se construiesc următoarele stări:
q1=δ(q0,a1)
q2=δ(q0,a2)
:
qn=δ(qn-1,an)
Dacă qn є Q’, atunci << x є L(A) >>:= ADEVĂRAT
Dacă qn ¢ Q’, atunci << x є L(A) >>:= FALS
Dacă automatul nu e complet specificat, algoritmul va fi:
Pentru i: 0 la n-1:
Dacă δ(qi,ai+1) nu există
Atunci << x є L(A) >>:= FALS
Altfel Dacă i = n-1
Atunci Dacă qi+1 є Q’
Atunci << x є L(A) >>:= ADEVĂRAT
Altfel << x є L(A) >>:= FALS
Distanța dintre o frază și o gramatică regulată
Extensiile analizei sintactice propuse pentru recunoașterea formelor au dus, în ceea ce privește gramaticile regulate, la calculul unei distanțe între frază și gramatică, adică a numărului minim de modificări suportate de frază pentru ca ea să fie acceptată de gramatică. Un algoritm (Wagner) calculează modificările suportate de frază pentru a fi transformată cu cel mai mic cost într-o frază a limbajului creat prin gramatică. Este cel mai perfecționat proces de analiză sintactică regulată tolerant la erori.
Se presupune așadar un automat finit ale cărui stări sunt notate aici: S,T,R,etc și numerotate de la 0 la n, starea de rang 0 fiind inițial: o frază α=α1…αn scrisă pe un alfabet X este dată.
Se definesc, ca în cazul distanței între fraze modificările posibile între fraze: inserția, substituția, distrugerea. Fiecare va fi afectată de o pondere unitară. Distanța lui α la automat va fi deci numărul minim de operații suportate de α pentru ca α1…αn să fie o succesiune de etichete a unei căi ducând de la o stare inițială a automatului la o stare finală (pe scurt: pentru ca α să ducă de la o stare inițială la o stare finală). Se va defini la început pentru orice stare S: F(j,S), pentru j=1,…,n, ca numărul minim de operații ce tansformă α1…αn într-ofrază ducând de la starea inițială la S.
Un raționament de programare dinamică asigură deci că:
F(j,S)=MinT{F(j-1,T)+V(t,s,αj)}
unde V(t,s,αj) este costul minim pentru a transforma caracterul αj într-un șir ducând la starea T din starea S.
Dacă P(T,S) se numește lungimea uneia din cele mai scurte căi (în număr de arcuri) între T și S și L(T,S,a) valorând 1 dacă litera a aparține uneia dintre aceste căi, și 0 dacă nu, atunci avem:
V(T,S,a)=1 dacă T=S
= P(T,S)-L(T,S,a) dacă nu
Lungimea celor mai scurte căi între T și S se poate calcula cu ecuația: pk*1=Min(pk(T,S),pk(T,K,1)+pk(K+1,S), unde pk(T,S) este lungimea uneia din cele mai scurte căi între T și S trecând prin stări de rang inferior sau egal cu K.
În decursul calculului lui P(T,S) se poate determina și valoarea lui L(T,S,a). la finele calculului, dacă Q este mulțimea de stări finale a automatului, distanța căutată între α și acest automat devine: MinSєQF(n,S).
Exemplu de aplicare a algoritmului lui Wagner [2]:
Automatul:
*Fraza: α = aaa
2.2.5. ÎNVĂȚAREA STRUCTURILOR REGULATE
Generalități ale inferenței gramaticale
În recunoașterea sintactică a formelor, învățarea modelelor de clase este o problemă esențială. Pusă în termeni de limbaj și gramatici, se poate enunța astfel:
Este posibil ca, pornind de la o mulțime I finită de fraze (model de învățare) să se găsească o gramatică G care acceptă I, adică astfel încât: IL(G)?
Această problemă este cunoscută sub numele de inferență gramaticală.
Trebuie notat că numai inferența gramaticală nu rezolvă toate problemele puse prin învățarea sintactică. În sprijinul distanțelor între fraze, de exemplu, se pot utiliza metode de clasificare automată, și astfel se poate extrage un rezultat din fiecare clasă, ceea ce constituie o altă metodă de învățare.
Pe de altă parte, definiția nu ține cont de comportamentul relativ al claselor și nu propune decât o învățare clasă cu clasă. Ori, este mai de dorit să se caute, prin învățare, modele gramaticale de clase ale căror limbaje se suprapun cât mai puțin posibil.
Model complet
Așa cum a fost pusă, problema inferenței admite o infinitate de soluții; una dintre ele, trivială, este gramatica universală Gu, al cărei limbaj acceptat este X*, dacă X este alfabetul pe care I este scrisă. Sub formă de automat finit se scrie:
Se observă că la X se pot adăuga oricâte litere se dorește, păstrându-se gramatica universală astfel creată în soluțiile la problema inferenței.
O altă soluție, numită gramatică canonică maximală, notată GCM(I), este una din cele ale căror limbaj creat este egal cu I. Se dă construcția sa într-un exemplu:
I = {a, bc, abc, ababc}.
În același mod se pot readăuga la GCM(I) tranziții oarecare purtând litere din X, sau din afara lui X, fără să se iasă din mulțimea de soluții. Aceasta pentru a se evita infinitatea de posibilități, fără interes, care se impune modelului pentru a fi complet, prin raportarea la gramatica propusă ca soluție.
Definiția 10: Un model se va numi structural complet (sau simplu complet) raportat la o gramatică G(X,V,P,S) dacă:
IL(G)
Alfabetul în care e scris I este identic cu X
Toate regulile din P sunt folosite cel puțin o dată într-o generație de fraze din X.
Folosind această condiție, problema de inferență gramaticală devine:
Pentru un model I găsim o gramatică (sau toate gramaticile) astfel încât:
1) IL(G)
2) I este complet raportându-se la G
Această restricție va permite găsirea de algoritmi de enumerare a soluțiilor, în particular în cazul regulat. Totodată, numărul lor e întotdeauna prea mare în raport cu mărimea modelului.
Teoria inferenței regulate
Cu ajutorul ipotezelor făcute la modelul complet și utilizând noțiunea de automat derivat, se dispune de un rezultat permanent de enumerare a soluțiilor regulate la o problemă de inferență. Deoarece asta e în cazul gramaticilor regulate, se utilizează indiferent dacă reprezentarea se face sub formă de gramatică sau de automat finit, după cum corespund notațiile.
Teoremă:
O condiție necesară și suficientă ca un automat finit A să fie soluție la problema de inferență:
IL(A)
I complet pentru A,
este ca A să fie derivat al automatului canonic maximal ACM(I).
Dacă se consideră un model I conținând N litere, numărul de stări al ACM(I) este de ordinul N, și acesta este numărul de soluții de ordinul numărului de partiții al unei mulțimi cu N elemente, pentru că automatul derivat e asociat unei partiții de stări al ACM(I).
Acest număr este dat prin recurență:
E(0)=1
E(N)=Ej
Ordin de mărime: E(10)~105
E(15)~1015
Această mulțime de soluții e structurată în latice, deoarece și mulțimea partițiilor unui ansamblu finit e structurată în latice, și deci ea posedă un element mai mare, aici Gu, și unul mai mic, GCM(l).
Teoretic, problema de inferență e deci rezolvată pentru gramaticile regulate: s-a găsit mulțimea de gramatici soluții pentru care modelul e structural complet, și în plus s-a pus în evidență o structură simplă pe această mulțime. În același timp într-un caz real al inferenței, la problemele de recunoaștere a formelor, nu e operatoriu să se dispună de un ansamblu de soluții; se caută efectiv dintre ele un singur mod, cunoscut explicit, de utilizare realmente în algoritmi, în care intervine.
Se pune astfel problema de a alege dintr-un număr foarte mare de soluții. A priori toate gramaticile soluții pot fi rezultate ale acestei alegeri. Trebuie, dacă se urmărește utilizarea mai eficientă a numărului de posibilități, să se dea un criteriu care se va putea evalua pe toate gramaticile soluții. Acest criteriu va fi introdus din exterior și forma sa depinde de constrângeri suplimentare care se doresc a fi impuse soluției.
El nu va fi întotdeauna sub forma explicită a unei funcții calculabile printr-o gramatică, dar se va prezenta eventual ca un algoritm permițând alegerea unei soluții din toate posibilitățile. În consecință, utilizarea unui criteriu explicit se lovește de un număr prea mare de gramatici pe care trebuie să le calculeze. Pentru un model chiar modest, numărul de gramatici soluție devine repede prea mare pentru a putea estima, pentru fiecare dintre ele, valoarea criteriului într-un timp rezonabil. Se va recurge la euristici ce permit pe de o parte reducerea numărului de gramatici ce pot fi reținute ca soluție, și pe de altă parte la alegerea unei soluții din această mulțime redusă. Aceste euristici sunt algoritmi de înaintare (parcurs) în structura gramaticilor soluție, care aleg un șir de astfel de gramatici, evaluând treptat mersul criteriului (în mod explicit sau nu), și decizând, fie să continue mersul, fie să aleagă ca soluție gramatica curentă. Denumirea de euristică provine din faptul că, prin astfel de procedeu, nu e sigură extragerea gramaticii ce optimizează criteriul. Atunci când criteriul nu e calculat în mod explicit, optimalitatea soluției e imposibil de evaluat individual, dar se poate evalua global, prin învățare, eficacitatea medie a unei euristici.
Algoritmi de inferență regulată
Se prezintă 3 algoritmi de inferență regulată, unul bazat pe o euristică derivată din lema conjugării, ceilalți 2 pe confuzia stărilor gramaticii canonice maximale.
Algoritmul uvkw
Se studiază aici traseele recursive într-un model caracteristic gramaticii care l-a creat. Se face ipoteza că se poate detecta, în cazul gramaticilor regulate, presupunând că modelul conține fraze suficient de lungi comparativ cu numărul de stări ale gramaticii căutate; în acest caz se spune că se poate aplica lema conjugării și deci că astfel de recursiuni se manifestă în model prin repetarea de subfraze.
Algoritmul propune cercetarea frazelor care se repetă în model, pentru ca apoi să se facă ipoteza că acestea sunt create efectiv prin mai multe treceri succesive ale aceleiași bucle a automatului corespunzător. Această ipoteuă este apoi verificată, pentru a cerne cazurile în care această buclă nu a fost parcursă de mai multe ori succesiv în generația de fraze. Atunci când o recursie a fost astfel reperată, se efectuează o etapă de inferență rescriind modelul.
Acesta e formalismul expresiilor regulate care permite această rescriere; se poate astfel conduce o succesiune de astfel de etape de inferență, în care oprirea e decisă de către automat.
Modelul e deci rescris de mai multe ori, de fiecare dată sub forma unei expresii regulate ce include precedenta. Rezultatul e, prin urmare, o expresie regulată reprezentând un limbaj regulat găsit prin inferență. O gramatică regulată ce acceptă acest limbaj poate fi deci calculată pentru a încheia procesul de inferență.
Această metodă se adaptează bine structurilor repetitive și, cu ajutorul adaptării diverșilor parametri, poate servi la pretratarea unui model, înainte de intrare, după o primă analiză a repetiților sale, într-o altă metodă de inferență care cercetează structurile mai complexe.
Algoritmii de k-finale
Această metodă de inferență stă la baza multor lucrări pentru că ea utilizează o euristică simplă de amestecare a stărilor. Metoda constă în a căuta în stările gramaticii canonice maximale (sau a unei gramatici canonice oarecare) relația lui k-echivalent. Un mod simplu de a realiza aceasta este utilizarea algoritmului de minimizare a gramaticilor regulate și de a opri cursul rutării pentru o valoare arbitrară a parametrului k; partiția pe stările gramaticii canonice indusă prin relația lui k-echivalent produce o gramatică derivată care e soluția căutată.
Se dorește ca acest algoritm să poată infera o soluție pentru fiecare valoare a lui k cuprinsă între 0 și (|Q|-2) unde Q este mulțimea stărilor gramaticii canonice utilizate. Numărul soluțiilor pe care le poate descoperi este foarte mic, ceea ce înseamnă că euristica de parcurs a structurii de gramatici propune puține alegeri.
În general, parametrul k este foate sensibil, adică de la o valoare la alta, el poate produce modificări importante pe limbajele inferate. Din experiențele realizate în inferență folosind această metodă se pot trage câteva concluzii: cele mai bune rezultate se obțin pentru modele compuse din fraze scurte și pentru valori ale lui k vecine valorii maxime.
În general, această metodă rar dă soluții cară să pară satisfăcătoare, mai ales din cauza sensibilități a parametrului său. Metoda e și mai puțin adaptată la problemele de recunoaștere a formelor, unde gramatica căutată trebuie să tindă să generalizeze proprietășâțile globale ale modelului. Această metodă descrie mai degrabă comportarea de la finalul frazelor; ea dă prioritate mare finalurilor la introducerea regulilor gramaticii inferate. Ea este utilizată datorită simplității de transpunere în practică.
Alipirea finalurilor
Această metodă o generealizează pe cea de k-finale bazându-se pe proprietatea că un automat poate fi reconstituit pornind de la mulțimile |Q|-1 finale ale stărilor sale. Ideea constă în a regrupa stările gramaticii canonice maximale comparându-le parcurgând mulțimile lor de finale. Se utilizează pentru aceasta o distanță între fraze și un algoritm de clasificare ierarhică. Rezultatele sunt superioare celor ale algoritmilor precedenți, dar și complexitatea calculelor e superioară.
2.2.6. MODELE SINTACTICE REGULATE PONDERATE
Abordarea sintactică dezvoltată până în prezent face o ipoteză implicită: toate formele unei clase contribuie în același mod la limbajul pe care îl formează, și gramatica asociată acesti limbaj le crează pe toate fără a face distincție între particularitățile sale. Cu toate acestea, în practică, unele dintre ele se pot produce mai frecvent. În acest caz se pot utiliza probabilitățile în decizia de recunoaștere. Se va căuta printre gramaticile G1…Gn cea care, pentru fraza x, va avea probabilitatea:
P(Gi|x)≥ P(Gj|x) , i≠j
Aplicarea regulii lui Bayes obligă să se definească:
P(x) : probabilitatea de apariție a frazei x
P(Gi) : probabilitatea a priori a clasei I
P(x|Gi) : probabilitatea ca fraza x să fie creată prin gramatica Gi
2.3. STRUCTURI DE ARBORI
Introducere
Reprezentarea datelor sub formă de arbori permite păstrarea unei informații structurale, fie de tip concret (geometric în cazul desenelor și imaginilor), fie de tip abstract (relații ierarhice între elementele primitive). În recunoașterea formelor aceste modele sunt foarte utile; proprietățile lor permit folosirea eficace a algoritmilor.
Utilizarea lor specifică va pune aceleași probleme ca pentru toate modelele folosite la recunoașterea formelor: cum se compară două forme codate printr-un arbore? Cum se reprezintă o familie de forme? Cum se decide cărei familii aparșine o formă?
Se aduc răspunsuri la aceste întrebări, pe de o parte prin introducerea metodelor de calcul a distanțelor între arbori, și pe de altă parte prin definirea modelelor generative pe aceste structuri (gramatici de arbori), care se pretează la analiza sintactică și la inferență.
2.3.1. DEFINIȚII. PROPRIETĂȚI ELEMENTARE
Arborii ca grafuri particulare
Definiția 1: Se numește graf, perechea (X, U) unde
X este o mulțime de vârfuri sau de noduri,
U este o mulțime de perechi ordonate de vârfuri, numite arce, ale căror elemente se numesc origine și extremitate.
Grafic, un nod se reprezintă printr-o cifră sau literă în interiorul unui cerc, și un arc printr-o linie cu săgeată.
Exemplu:
Graful (X, U) cu:
X = {A, B, C, D}
U = {(A, B), (A, C), (C, A), (B, D), (D, C)}
se reprezintă astfel:
Definiția 2: Se numește semitreaptă interioară a unui nod, numărul de arcuri avănd acest nod la extremitate; semitreaptă exterioară, numărul de arcuri ce au acest nod la origine; treaptă, suma celor două semitrepte.
Definiția 3: În general, un graf e orientat. Dacă U are întotdeauna elementul (A, B), când el are elementil (B, A), se spune că graful este neorientat. Reprezentarea grafică este în acest caz:
Definiția 4: Se spune că două noduri sunt adiacente dacă există un arc care le unește.
Definiția 5: Un drum de lungime n este un șir de noduri S0, S1,…, Sn, astfel încât k [0, n-1], Sk și Sk+1 sunt adiacente.
Definiția 6: Un graf este conex dacă pentru oricare pereche (A, B) cu vârfuri distincte, există cel puțin un drum de origine A și extremitate B.
Definiția 7: Un ciclu este un drum cu aceeași origine și extremitate și nu conține decât o singură dată fiecare din nodurile sale.
Definiția 8: Un arbore este un graf neorientat căruia îi corespunde oricare din definițiile următoare:
este conex dar fără proprietatea de a forma un arc oarecare;
este conex și are n vârfuri și (n-1) arce;
există un drum și numai unul între oricare pereche de vârfuri diferite
are n vârfuri, (n-1) arce și mici un ciclu.
Exemplu de arbore:
Demonstrația echivalenței acestor definiții se găsește în [4]
Definiția 9: Se numește arborescență de rădăcină A, un graf orientat căruia îi corespunde una din următoarele definiții:
nu conține nici un ciclu, și pentru toate vârfurile BA există un drum de la A la B.
este conex și există un vârf A cu semitreapta interioară nulă, iar pentru celelalte vârfuri aceasta 1.
Exemplu de arborescență de rădăcină A:
b) Arborii ca structură ierarhică
Un alt mod de definire a arborelui este să îl considerăm ca o frază recursivă adică, ca o concatenare de subarbori. Din acest punct de vedere avem următoarea definiție.
Definiția 10: Un arbore e o mulțime finită de noduri, astfel încât:
● există în X un element distinct A, numit vârful arborelui;
● dacă există alte noduri, acestea sunt grupate în mulțimi disjuncte X1, X2, …, Xm, care sunt de asemenea arbori, al căror element distinct este legat la A printr-un arc.
O arborescență răspunde la aceeași definiție, cu condiția ca arcul să fie orientat și să aibă A drept origine.
Se spune că un nod S este “fiu” (descendent) alt altui nod T când S este rădăcină a unui subarbore al lui T. Reciproc, T este “părinte” al lui S. Nodurile “frați” sunt “fii” (descendenți) ai aceluiași “părinte”.
Atunci când ordinea lor trebuie luată în calcul, se spune că arborele este ordonat. Un arbore ordonat este deci o frază recursivă, considerând concatenarea ca o alipire de subarbori cu rădăcina comună. O frază e un arbore cu rădăcina fictivă, neavând decât subarbori reduși la vârf.
Nivelul rădăcină al unui arbore este prin definiție egal cu 1. Dacă un nod este de nivel n eventualii lui fii sunt de nivel (n-1).
Definiția 13: Se spune că un arbore e etichetat atunci când există o aplicație a mulțimii nodurilor sale într-un alfabet A. Altfel spus, fiecare din nodurile sale are o etichetă aparținând lui A.
Parcursul în arbori
Definiția 14: Un algoritm de parcurs în arbore e o procedură care furnizează ca rezultat lista de noduri ale arborelui, fără să se omită nici repetițiile. Acesta e deci un procedeu care ordonează în totalitate această mulțime de noduri.
Se dispune de două relații de ordine parțiale între nodurile unui arbore: odinea de descendență și ordinea de ascendență. Cele două ordine se numesc uzual postordine (ordine postfixată) și preordine (ordine prefixată). Ordinea prefixată corespunde următoarei definiții recursive:
─ examinarea rădăcinii;
─ parcurgerea în ordine prefixată a primului subarbore al rădăcinii;
─ parcurgerea în ordine prefixată a ultimului subarbore al rădăcinii.
Ordinea postfixată are următoarea definiție recursivă:
─ parcurgerea în ordine prefixată a primului subarbore al rădăcinii;
─ parcurgerea în ordine prefixată a ultimului subarbore al rădăcinii.
O altă ordine, ce respectă în mod egal ambele ordini parțiale ale structurii de arbori, este ordinea (parcurgerea) în lățime. Aceasta se definește recursiv:
─ se examinează nodurile de nivel 1 de la stânga la dreapta;
─ se examinează nodurile de nivel n de la stânga la dreapta.
2.3.2. NUMEROTAREA PRIN DOMENIU AL ARBORELUI SAU LEXICOGRAFICĂ
Un mod de a numerota nodurile unui arbore, ce permite respectarea diferitelor ordine parțiale citate, este cel al domeniului de arbori; acesta permite reconstituirea structurii pornind de la o listă (nu neapărat ordonată) de etichete numerice compuse. Acest mod se interpretează simplu ca o ordine lexicografică. Prin definiție, un domeniu de arbori este un limbaj pe un alfabet N* de numere naturale întregi, unde concatenarea e notată prin simbolul “.”.
Definiția 15: este un domeniu al arborelui dacă și numai dacă:
D este finit;
b є D și a < b => a є D
a, m є D => a.n є D pentru 1 ≤ n ≤ m, cu m și n є D
Interpretarea acestui domeniu al arborelui permite să se atribuie în mod biunivoc un element al lui D la fiecare nod corespondent al structurii arborelui. Un domeniu al arborelui permite, deci, să se transpună o structură ierarhică în termen de limbaj.
2.3.3. DISTANȚA ÎNTRE ARBORI
La fel ca în cazul structurilor de șiruri, tehnica mai simplă de folosire a arborilor constă în a defini o categorie de metrică între acești arbori. În acest domeniu se pot distinge două tipuri de lucrări: matematicienii au definit pe de o parte metrici pe mulțimi ordonate parțial (aceștia se aplică la arbori), sau au propus distanțe între hipergrafuri (în care arborii sunt un caz particular). Aceste lucrări se referă doar la arborii la care doar frunzele sunt etichetate, și sunt aplicate în particular la compararea rezultatelor algoritmilor de clasificare ierarhică pe o mulțime de date. Acest subiect e detaliat în [5]. Al doilea tip de lucrări se referă la generalizarea distanțelor de tipul Wagner ale arborilor etichetați. Din punct de vedere al recunoașterii formelor această abordare este mai promițătoare decât cea anterioară. În literatura de specialitate se întâlnesc mai mulți algoritmi bazați pe această abordare, cum ar fi: algoritmul lui Selkow și algoritmul lui Lu [7].
2.3.4. GRAMATICI ALE ARBORILOR
E util să se extindă sistemele generatoare de fraze pentru a defini limbajele arborilor, ale mulțimilor de arbori cu structură comună. O soluție simplă este să se dea reguli de construcție descendentă de la nivele de plecare ale rădăcinii până la ramuri, rescriind o ramură provizorie (afectată de o etichetă aparținând unui alfabet auxiliar) sub forma unui subarbore. La sfârșit toqte nodurile sunt etichetate pe un alfabet terminal. Un astfel de sistem generator e o generalizare a gramaticilor formale și a fost numită gramatică de arbori. Pentru a defini un astfel de sistem de rescriere trebuie să se stabilească o corespondență între eticheta susceptibilă să marcheze un nod și numărul posibil de descendenți ai acestui nod.
Un element a al alfabetului X al etichetelor va fi deci caracterizat prin mulțimea sa de trepte posibile: r(a) = {r1, r2, …, rn}. Aceasta înseamnă că un nod cu eticheta a poate avea un număr de descendenți aleși din mulțimea {r1, r2, …, rn}. Mulțimea (X, r) se numește alfabet de trepte.
Definiția 15: O gramatică de arbori e un cuadruplu (V, r, P, S), unde V = N U X este alfabet al gramaticii compuse dintr-un alfabet auxiliar N și un alfabet terminal X, N și X disjuncte;
(V, r) este un alfabet de trepte
P e o mulțime de reguli de producție de forma Ti → Tj, unde Ti și Tj arbori;
S є Tv e mulțimea arborilor inițiali, cu Tv mulțimea de arbori etichetați pe V.
Recunoașterea prin automate de arbori
Pentru a continua analogia cu sistemele de rescriere a șirurilor, alături de gramaticile de arbori (procedeu generator), mai trebuie definite și automatele de arbori (procedeu de recunoaștere), mod în care se poate decide apartenența unui arbore dat la familia de arbori generați printr-o gramatică de arbori. Un astfel de automat va porni de la o mulțime de ramuri, și va căuta să reconstruiască rădăcina aplicând inversele regulilor de producție ale gramaticilor asociate.
Definiția 16: Un automat de arbori este un cuadruplu (X,Q,F,{fa│aєX}), unde
X e un alfabet terminal,
Q e o mulțime de stări,
F e o mulțime de stări finale incluse în Q,
fa e o aplicație a lui Qn în Q, cu n є r(a).
O astfel de mașină are pe arborele de analizat o funcționare paralelă ce poate fi descrisă simplu în modul următor: Automatul afectează o stare inițială (stare particulară a lui Q) pe fiecare ramură a arborelui. Toate drumurile spre rădăcină sunt explorate simultan, prin examinarea unui nod și a succesorilor săi. Dacă mulțimea de stări deja afectate la succesorii unui nod R cu eticheta a este un element din Qn în aplicația fa, atunci se afectează starea corespunzătoare a acestei aplicații la starea R. Procedeul se termină fie prin imposibilitatea etichetării nodurilor (eșec), fie când rădăcina e etichetată cu o stare Q-F (eșec), sau cu o stare F (reușită: arborele poate fi creat prin gramatica asociată automatului).
Inferența gramaticilor de arbori
Analogia cu modelele gramaticale clasice se continuă pentru gramaticile arborilor la tehnicile de învățare. Au fost dezvoltate metode de inferență inspirate, ca și în cazul metodelor generative, din din structurile sintactice regulate. Prin urmare, se caută detectarea simetriilor în modelul de învățare (ca în cazul metodei uvkw prezentată în paragraful 2.2.5.). Primei tehnici îi sunt asociați algoritmii lui Bhargava și Fu, și ai lui Gonzales și Thomason [9] , iar celei de-a doua tehnici, algoritmul lui Levine [14]. Acesta din urmă, pe lângă suportul teoretic, prezintă avantajul generalizării anterioarelor două.
2.4. STRUCTURI DE GRAFURI
2.4.1. PREZENTARE
Studiul modelelor matematice structurale generale i-a condus pe cercetătorii în recunoașterea formelor la studierea grafurilor. Aceste instrumente sunt efectiv imediat utilizabile pentru descrierea relațiilor prin o mulțime de obiecte (de exemplu, forme primitive). În plus, datorită proprietăților lor matematice și algoritmice, se utilizează într-o mare varietate de probleme.
În analiza sintactică, grafurile sunt utilizate mai mult ca elemente de descriere, decât ca modele ce permit realmente o învățare și o decizie. Se prezintă câteva aspecte algoritmice ale teoriei grafurilor ce pot revela utilitatea lor în recunoașterea formelor; problema izomorfismului (distanța binară); enumerarea vârfurilor (parcursul) și altele.
2.4.2. NOȚIUNI ELEMENTARE ALE TEORIEI GRAFURILOR
1) Fiind dat un graf G = (X, U), fiecărui arc i se asociază un număr real l(U) numit lungimea arcului. Se spune că G este evaluat prin l.
Acest cuvânt, lungime, nu trebuie înțeles în sensul său direct (deși el poate exprima o realitate metrică). Valoarea sa reprezintă tăria relației între două noduri corespondente (asemănare, complementaritate, etc).
2) Fie . Subgraful creat prin A este graful GA ale cărui vârfuri sunt elemente din A și ale cărui elemente sunt arcuri din G, având cele două extremități în A.
3) Fie . Graful parțial creat prin V este graful mulțimii de vârfuri X și ale cărui arcuri sunt cele din V (se elimină cele din U-V).
4) Un graf complet este atunci când pentru orice pereche de vârfuri există cel puțin un arc între ele.
2.4.3. REFACEREA UNUI GRAF PRINTR-UN ARBORE
Un arbore de refacere a unui graf G=(X,U) este un graf parțial T=(X,U) al lui G fără ciclu (acesta e deci un arbore). Căutarea unui arbore de refacere se realizează prin rețele de relații neredundante (prin tranzitivitate) între elementele primitive, care reprezintă nodurile. Un caz concret e acela în care se caută extragerea dintre toți arborii de refacere a celui cu pondere minimă (care are vârfurile și arcurile cele mai mici). În literatura de specialitate sunt descriși mai mulți algoritmi pentru această problemă. Complexitatea lor e în funcție de |X| și |U|.
2.4.4. IZOMORFISMUL ÎNTRE GRAFURI ȘI INCLUZIUNEA GRAFURILOR
În recunoașterea formelor, problema izomorfismului între grafuri constă în a recunoaște dacă două forme sunt reprezentate în același mod în ambele modele. Acesta e cel mai simplu tip de decizie care se poate face în acest formalism. Problema se formulează în modul următor:
Fie 2 grafuri: Gx =(X,Ux) și Gy =(X,Uy).
Ele sunt izomorfe dacă există o corespondență biunivocă:
f:X→Y astfel încât (u, w) єVx <=> (f(u), f(w)) єVy.
Algoritmul ce permite să se determine dacă 2 grafuri sunt izomorfe este combinatoriu: el constă în a căuta toate corespondențele licite și a testa pentru fiecare dacă există izomorfism. Prin licit se înțelege o corespondență astfel încât nodurile asociate să aibă aceleași semitrepte interioare și exterioare. Acest lucru permite reducerea considerabilă a numărului de teste ce ar fi trebuit făcute.
Trebuie întâi verificată condiția necesară pentru izomorfism:|Vx| =|Vx|. Se alege apoi X ca graf de referință, în care nodurile sunt numerotate de la 1 la n.se notează Gx(k) subgrafuldin X construit din nodurile {1,…,k}, pentru 0≤k≤n. Algoritmul se face în sensul creșterii parametrului k. Presupunem că s-a găsit un subgraf Gy din Y, având mulțimea de noduri S, izomorf la Gx(k). Se va căuta să se extindă acest izomorfism la Gx(k+1), căutând un nod în Vy-S, cu readăugare la S. Dacă e posibil se continuă acest procedeu, dacă nu, se revine la Gx(k-1). S-a utilizat aici o procedură recursivă numită ISO. Mai există o procedură utilizată, numită MATCH, care verifică dacă o corespondență e licită sau nu, în sensul definit mai sus.
O versiune mai suplă a testului de izomorfism constă în a găsi toate subgrafurile lui GB care sunt izomorfe cu GA. Această problemă e cunoscută sub denumirea de izomorfism de subgrafuri sau incluziune de subgrafuri.
Interesul, în recunoașterea formelor, este de a putea compara două reprezentări printr-un criteriu mai puțin strict decât egalitatea, și de exemplu prin extragerea de subarbori caracteristici ai formelor elementare dintr-un graf mare ce modelează o formă complexă. În legătură cu această problemă s-au făcut numeroase studii [6].
2.4.5. REPREZENTAREA ȘI REZOLVAREA PROBLEMELOR PRIN GRAFURI DE STĂRI
Se prezintă pe scurt o metodologie de reprezentare și rezolvare a problemelor a căror importanță a crescut în aplicațiile de recunoaștere a formelor. Aceste metode stau la baza inteligenței artificiale [4] și se utilizează la problemele jocurilor, la rezolvarea problemelor combinatorii (simulare, puzzle), etc. Generalitatea și puterea lor au permis aplicarea lor și în domenii apriori mai puțin adaptate. Prezintă avantaje și la recunoașterea formelor.
Fundamental, reprezentarea căutată este cea a unui graf, ale cărui noduri figurează toate stările posibile ale datelor de tratat, un arc semnificând că se poate trece de la o stare la alta printr-o transformare elementară. Se caută să se unească un nod de plecare, ce reprezintă problema de rezolvat, cu un nod de sosire, ce reprezintă problema rezolvată. Problema de analiză sintactică e echivalentă deci cu cea de căutare a unui drum, în acest graf, între nodul de plecare și nodul de sosire.
Se tinde spre o generalizate a acestui tip de reprezentare, pentru că e suficient să se definească stările și liniile de trecere ce permit legătura. Se mai poate defini costul aplicației la fiecare linie, adică o lungime pentru fiecare arc; problema se rezolvă în principal printr-un algoritm de căutare a unui drum mai scurt între două noduri ale unui graf [6].
De fapt, adevăratul avantaj al acestui mod de reprezentare nu constă în această utilizare clasică a teoriei grafurilor. În majoritatea cazurilor practice graful reprezentat posedă un număr mare de noduri, motiv pentru care sunt imposibil de reprezentat algoritmii clasici de căutare a celui mai scurt drum. Deoarece în memorie nu se păstrează toate nodurile ci doar o mică parte se pune problema dacă e posibil să se găsească un drum (și dacă se poate cel mai scurt) într-un graf pentru care la un moment dat nu se găsesc în memorie decât o parte din noduri. Aici se poate revela puterea acestei reprezentări, pentru că această problemă se rezolvă într-o manieră completă în teorie și adesea eficace în practică.
Decodarea secvențială (sau metoda de cost uniform [9]) este o metodă de căutare a celui mai scurt drum între un vârf de plecare și unul din vârfurile de sosire, care nu necesită în principiu examinarea tuturor nodurilor din graf și nici stocarea lor în memorie.
=== Capitol 3 ===
CAPITOLUL 3
ANALIZA SINTACTICĂ A SEMNALELOR ECG
3.1. INTRODUCERE
Recunoașterea semnalului și a formei cunoaște doua abordări. În cea teoretic – decizională sau discriminantă, semnalul este reprezentat de un set de trăsături specifice ale semnalului. Metoda sintactică sau structurală utilizează informația structurală pentru a defini și a clasifica formele.
Metoda sintactică pare să aibă un bun potențial în analiza biosemnalele complexe, deoarece are capacitatea de a mânui structura. Metoda se apropie de cea folosită de interpretorul uman, care observă structura formei de undă pentru a stabili diagnosticul.
Metoda sintactică se mai numește și lingvistică sau structurală sau gramaticală, datorită analogiei cu sintaxa unui limbaj. O formă este descrisă de relațiile dintre simple subforme din care ea e compusă. Regulile ce descriu compoziția subformelor sunt similare cu regulile gramaticale din lingvistică.
Pentru a clasifica un semnal in câteva clase cunoscute, structura fiecărei clase trebuie învățată. Într-un mod de invățare supervizată, sunt furnizate eșantioane cunoscute de semnale din fiecare clasă, astfel încât trăsăturile (primitivele) și regulile de combinare a lor în semnalul dat (gramatica) pot fi estimate. Acestea sunt memorate de sistem. Pentru a fi analizat și clasificat, un semnal necunoscut este preprocesat, în scopul reducerii zgomotului, apoi sunt extrase primitivete lui. Clasificarea se face aplicând sintaxa fiecărei clase. Semnalul este introdus în clasa a carei sintaxă se potrivește cel mai bine. Schema bloc a unui sistem de recunoaștere sintactică a semnalelor este prezentată în fig. 3.1.
Fig.3.1. Schema bloc a unui sistem de recunoaștere sintactică a semnalelor
3.2. DEFINIȚII
Descrierea structurii semnalului este realizată de gramatici sau reguli sintactice. Gramatica poate fi utilizată de asemenea pentru a descrie toate semnalele (propoziții) ce aparțin unei anumite clase (limbaj). De obicei, o clasă este reprezentată de un set dat de semnale cunoscute (set de antrenare). Este necesară estimarea gramaticii generatoare a clasei pornind de la setul de antrenare (deducere gramaticală).
Notând cu G gramatica ce poate modela sursa care generează setul de semnale, toate propozițiile care pot fi generate de ea constituie un set L(G) ce constituie limbajul generat de G. G e de forma:
G= (VN, VT, R, σ) (3.1)
unde:
VN e un set de simboluri nonterminale (cuvinte sau variabile) ale lui G;
VT e un set de simboluri terminale;
o e simbolul de start;
R e un set finit de reguli de rescriere sau de producții, notate: “α→β”, unde α și β sunt șiruri.
Notații introduse pentru analiza sintactică:
1. α→β simbolul ”→” înseamnă ”poate fi rescris ca” și e numit producție;
2. xn înseamnă ”x scris de n ori”, unde x e un șir;
3. │x│ înseamnă lungimea șirului, adică numărul de simboluri în șirul x;
4. VT* e setul tuturor șirurilor de lungime finită ce pot fi generate utilizând setul VT.
Gramaticile sunt de 4 tipuri:
Gramatici nerestricționate (tip 0), gramatici fară restricții asupra rezultatelor; sunt prea generale și nu sunt aplicate des.
2. Gramatici sensibile la context (tip 1), gramatici în care rezultatele sunt reduse la forma:
(3.2)
unde și . Limbajele generate sunt numite limbaje sensibile la context.
3. Gramatici insensibile la context (tip 2), gramatici în care rezultatele sunt reduse la forma:
(3.3)
unde și . Aici β îl înlocuiește pe A independent de contextul în care apare A. Limbajele generate sunt numite limbaje insensibile la context.
4. Gramatici cu stări finite sau gramatici sistematice (tip 3), gramatici în care rezultatele sunt reduse la forma:
A→aB sau A→b (3.4)
unde A,BVN și a,bVT. (toate sunt simboluri singulare, nu șiruri).
O altă modalitate de a descrie gramatica de stări finite este prin diagrama stărilor de tranziție. Diagrama constă din noduri și căi. Nodurile corespund stărilor, adică simbolurilor nonterminale. Un nod special corespunde stării terminale. Căile leagî diverse noduri, corespunzând producțiilor posibile.
3.3. IDENTIFICATOARE SINTACTICE
Semnalele testate sunt reprezentate sub formă de șiruri generate de o gramatică. Fiecare clasă de semnale are propria ei gramatică. Identificatorul are sarcina de a determina care gramatică a produs șirul necunoscut. Considerăm cazul în care sunt date clasele wi, i = 1,2, …, M, fiecare cu gramatica proprie Gi. Procesul numit analiză sintactică este cel care decide dacă șirul necunoscut x aparține unuia dintre limbajele L(Gi), i = 1,2, …, M. Dacă el decide că xL(Gj), atunci x este clasificat în wj.
Considerăm întâi recunoașterea șirurilor utilizând automate. De interes sunt automatul finit, utilizat la recunoașterea gramaticilor cu stări finite și automatul ”push-down”, utilizat la recunoașterea gramaticilor insensibile la context.
A. Automate cu stări finite
Un automat cu stări finite determinist, A, este de forma:
A = (Σ,Q,δ,q0,F) (3.5)
unde Σ este alfabetul (un set final de simboluri de intrare), Q este setul final de stări, σ este operatorul de cartare, q0 este starea de start și F este un set de stări finale.
Funcționarea automatului poate fi privită ca cea a unui dispozitiv care citește date de pe o bandă. Dispozitivul este inițial în starea q0. Secvența x, înregistrată pe bandă este citită simbol după simbol. Dispozitivul trece în altă stare conform operatorului de cartare:
δ(q1,ξ)=q2, ξΣ (3.6.A)
adică automatul este în starea q1 și dupa citirea simbolului ξ trece în starea q2. Șirul x este acceptat de automatul A dacă, după citirea întregului șir, automatul este într-una din stările finale. Operația de transformare (3.6.A) poate fi extinsă pentru a include șiruri. Asffel, șirul x este acceptat de automatul A dacă:
δ(q0,x) = p pentru un pF, (3.6.B)
adică, dacă pornind din starea q0 și scanând întregul șir x, automatul va trece într-o serie de stări care se va încheia în starea p, care este o stare finală.
De observat că stările finale sunt reprezentate prin două cercuri concentrice.
Un FSA (”finite state automaton”) nedeterminist este la fel ca cel determinist, exceptând faptul că transformarea δ(q,ξ) este un set de stări și nu o unică stare, așa cum rezultă din ecuația (3.6). Astfel, pentru un FSA nedeterminist:
δ(q1,ξ)={q1,q2…qn} (3.7)
Ecuația descrie transformarea unui automat nedeterminist ln starea q, după citirea simbolului ξ. Automatul va trece într-una din stările q1,q2,…,qn. Se presupune că automatul alege întotdeauna starea corectă în care trece.
Se poate demonstra că pentru orice FSA nedeterminist care acceptă un set de șiruri, L, există un automat determinist care recunoaște același set de șiruri. De asemenea, pentru orice gramatică cu stări finite, G, există un FSA care recunoaște limbajul generat de G.
Exemplul.3.1: Considerăm semnalul ECG din figura 3.2.a, cu primitivele din figura 3.2.b.
Fig.3.2. O reprezentare sintactică a ECG: [a.] modelul ECG;
[b.] un set de primitive.
O gramatică ce descrie semnalul ECG normal este dată de:
G= (VN, VT, R, σ), unde:
VN ={σ,A,B,C,D,E,F,G,H}
VT=(q,qrs,t,b)
R: (1) σ →p·A
(2) A→qrs· C (3) A→b·B
(4) B→ qrs· C
(5) C→b·D
(6) D→t·F (7) D→b·E
(8) E→t·F
(9) F→b·G
(10) G→b (11) G→b·H (12) G→p·A
(13) H →b (14) H →b·σ (15) H →p·A
ECG normal este definit aici ca având structura de bază (p qrs b t b) cu variații normale ce pot include un b intre p și qrs, un b între qrs și t și unul sau doua b-uri intre t și următorul p. Automatul cu stări finite deterministic care recunoaște ECG normal este prezentat in figura 3.3. Starea qT reprezintă starea terminală.
Fig.3.3. FSA determinist pentru analiza ECG
B. Automate ”Push – Down” insensibile la context
Limbajele insensibile Ia context definite de ecuația 3.3 nu pot fi recunoscute de FSA. Pentru astfel de limbaje se poate utiliza un automat ”Push – Down” (PDA). Un PDA este similar cu un FSA la care se adauga o stivă cu stocare în jos. Stocarea în stivă este de tip ”primul intrat – ultimul ieșit”. Șirurile pot fi stocate in stivă astfel încât primul simbol este in vârf. Automatul citește întotdeauna simbolul din vârful stivei. Stiva se presupune că are o capacitate infinită. Un PDA este prezentat schematic în figura 3.4. PDA nedeterminist M este de forma:
M = (Σ, Q, Γ, δ, q0, Z0, F) (3.8)
unde Σ, Q, q0 și F sunt aceleași ca în ecuația 3.5, Γ este un set finit de simboluri împinge – jos și Z0 є Γ este un simbol de start care apare inițial in stivă. Operatorul δ(q,ξ,Z) este operatorul de cartare:
δ(q,ξ,Z) = {(q1, γ1), (q2, γ2), …, (qm, γm) } (3.9)
unde q, q1, q2,…,qm є Q sunt stări, ξ є Z este un simbol de intrare, Z este simbolul curent in vârful stivei și γ1,γ2,…,γm є Γ sunt șiruri ale stivei împinge – jos.
Fig.3.4. Automat ”Push – Down”
Transformarea (ecuația 3.9) se interpretează astfel: controlul este în starea q, cu simbolul Z în vârful stivei și simbolul de intrare ξ este citit din șirul de intrare. Controlul va alege una din perechile (qi, γi), i = 1,2, …, m, de exempIu (qj,γj). El va înlocui în stivă simbolul Z cu șirul γi, astfel încât cel mai din stânga simbol apare în vârful stivei, apoi va trece în starea qj și va citi următorul simbol din șirul de intrare.
Dacă ξ= γ(simbolul nul), atunci, independent de șirul de intrare, automatul, în starea q, va înlocui Z cu γj în stivă și va rămâne în starea q. Când γj = X, simbolul din vârful stivei este șters. Dacă automatul ajunge la o stare δ(qi,ξ,ξ ,), adică dacă simbolul din vârful stivei se potrivește, simbolul de intrare ξ este scos din stivă, expunând următorul simbol din stivă, η cu urmatoarea transformare δ(qi,γ,η). Dacă automatul atinge o combinație de stare, intrare și simboIuri de stare pentru care nici o transformare nu este definită, el se oprește și rejectează intrarea. Acceptarea șirurilor de catre PDA poate fi exprimată în două moduri:
(1) Automatul citește toate simboIurile din șirul de intrare fără a fi oprit și după citirea ultimului simbol de intrare este mutat într-o stare q care aparține setului final F;
(2) Automatul citește toate simbolurile de intrare fără a fi oprit. Transformarea luată dupa citirea ultimului simbol de intrare mută automatul într-o stare q є Q cu stivă goală, adică γ = λ. Acest tip de acceptare se numește ”acceptare cu “stocare goală”. Pentru acest caz este convenabil să se definească setul de stări finale ca fiind setul nul F = Φ.
În majoritatea aplicațiilor de procesare sintactică a semnalului, se dă o clasă de semnale (prin intermediul primitivelor și al gramaticii) și trebuie proiectat un sistem de recunoaștere a acestei clase. S-a demonstrat că pentru oricare gramatică insensibilă la context G există un PDA care recunoaște limbajul L(G). Reciproca este, de asemenea, adevarată.
Considerăm cazul în care se dă o gramatică insensibilă la context G și se dorește obfinerea unui PDA care o recunoaște. Un algoritm relativ simplu este următorul:
Fie G = (VN, VT, R, σ) această gramatică. Un PDA ce recunoaște L(G) este A = (VT, {q0}, Γ, δ, q0, Φ) cu simbolurile impinge – jos Γ obținute ca reuniune a lui VN și VT și cu transformările σ obținute din producțiile R cu:
Dacă A → α este în R, atunci δ(q0, λ, A) → {(q0, α)}, unde α este un șir și λ este șirul nul.
(2) Pentru fiecare terminal a în VT,
δ(q0,a,a) → {(q0,λ)}
C. Translația controlată sintactic simplă
Deseori, este necesar să se transforme un șir generat de o gramatică într-un alt șir, în alt limbaj. O astfel de transformare, bazată pe gramaticile insensibile la context, fundamentale, se numește translație controlată sintactic. Cu ajutorul translatorilor controlați sintactic simpli, un șir de intrare poate fi transformat (clasificat) într-un șir de ieșire, în plus la faptul că este recunoscut.
Cel mai simplu translator este traductorul finit nedeterministic dat de:
AT = (Σ, Q, Λ, δ, q0, F) (3.10)
unde Σ, Q, q0 și F sunt aceeași ca în ecuația (3.5), Λ este alfabetul de ieșire finit și δ este operatorul de cartare. Translatorul poate fi privit
ca un FSA care are în plus o banda de ieșire pe care este înscrisa transformarea de ieșire.
Exemplul 3.2: Diagrama de stare a unui traductor pentru analiza ECG este dată în figura 3.5:
Fig.3.5. Traductor finit pentru analiza ECG
Acest traductor nu realizează doar recunoașterea ECG normal, ci și clasificarea fiecărui ECG în normal (N) sau anormal (An). În fiecare pas la ieșire se înscrie un simbol ”N” sau ”An”. De exemplu, șirul de intrare pbqrsbbtbbb va fi recunoscut de traductor, care va înscrie secvența N9 la ieșire. Șirul de intrare pbbqrsbbtbbb va produce secvența N2An8 la ieșire. Orice șir de intrare care a fost transformat într-un șir de ieșire cu cel puțin un simbol ”An”, este clasificat ca anormal.
Translația controlată sintactic insensibilă la context, neuniformă, necesită traductoare mai sofisticate. Un traductor PDA nedeterminist este similar ca structură cu traductorul finit, la care se adaugă o stivă impinge – jos.
D. Analiza sintactică
Există tehnici generale de determinare a secvenței producțiilor utilizate pentru a obține un șir dat, din limbajul L(G) insensibil la context. Aceste tehnici se numesc tehnici de analiză sintactică. Se cunosc două modalități de analiză a unui șir x. Analiza ”de jos în sus” pornește de la șirul x și aplică producțiile lui G, în mod invers, în scopul obținerii simboluiui de start σ. Analiza ”de sus în jos” pornește de la simbolul σ și prin aplicarea producțiilor lui G încearcă să ajungă la șirul x. Au fost dezvoltați algoritmi de analiză eficienți, cum ar fi algoritmul Cock – Yonger – Kasami.
3.4. LIMBAJELE STOHASTICE ȘI ANALIZA SINTACTICĂ
Cel mai adesea procesarea semnalului se face într-un mediu stohastic. Se introduc zgomot și erori fie din cauza naturii stohastice a semnalului de analizat, fie din cauza proceselor de achiziție și de extragere a primitivelor. Clasele semnalelor de analizat se pot suprapune, în sensul că un anumit semnal poate aparține mai multor clase. Limbajele stohastice se folosesc pentru a rezolva astfel de probleme. Dacă n gramatici, Gi, i = 1, 2, …, n, reprezinta șirul (semnalul) x, trebuie cunoscute probabilitățile condiționale p(x I Gi ), i = 1, 2, …, n. Se consideră că gramatica ce a produs șirul x este cea pentru care p(x I Gj ) este maximă.
Într-o gramatică stohastică, se atribuie valori de probabilitate diferitelor producții. Gramatica stohastică este setul: G = {VN, VT, R, P, σ}, unde VN, VT, R și σ sunt cele din ecuația (3.1), iar P este setul de probabilită’i atribuite producțiilor lui R. Vom considera aici doar gramatici stohastice nerestricționate, corecte. Într-o astfel de gramatică, probabilitatea asociată unei producții nu depinde de producțiile anterioare. Considerăm un nonterminaI T pentru care sunt m producții: Ti→α1, Ti→α2,…, Ti→αm. Producțiilor li s-au asociat probabilitațile Pij, j = 1, 2, …, m. O gramatică stohastică corectă are:
pentru oricare i. (3.11)
Gramaticile stohastice sunt împărțite în patru categorii, ca și gramaticile nonstohastice (ecuațiiIe 3.2 și 3.3). De aceea vorbim de gramatici și limbaje stohastice insensibile la context și de gramatici și limbaje stohastice cu stări finite.
A. Identificatoare stohastice
Gramaticile stohastice cu stări finite pot fi recunoscute de un automat stohastic finit. Automatul este definit de:
AT = (Σ, Q, δ, q0, F, P) (3.12)
unde Σ, Q, q0 și F sunt aceeași ca în ecuația (3.5), P este setul de probabilitați și δ este operatorul de cartare căruia îi sunt atribuite probabilitățile. Automatul stohastic finit operează într-un mod similar cu FSA, exceptând faptul că tranziția de la o stare la alta este un proces aleator cu anumite probabilități. Pentru un automat nerestricționat, probabilitațile nu depind de stările anterioare.
Exemplul 3.3. Considerăm FSA din figura 3.3, proiectat pentru a recunoaște ECG normal. Considerăm că există o probabilitate de 0,1 ca unda T să lipseasca. Automatul proiectat pentru a recunoaște semnalul este o modificare a FSA. Diagrama stărilor de tranziție este prezentată în figura 3.6:
Fig.3.6
Se observă că a mai fost adăugată o cale între stările qD și qG și fiecărei căi i s-a asociat un simbol de intrare și o probabilitate. Când automatul este în starea g și simbolul de intrare este b, el poate trece (cu probabilitatea 0,9) în starea qE sau (cu probabilitatea 0,1) în starea qG. Stările de tranziție stohastice ale automatului sunt următoarele:
δ(q0,p)={qA}; p(qA / p, q0)=1
δ(qA,b)={qB}; p(qB / b, qA)=1
δ(qA,qrs)={qC}; p(qC / qrs, qA)=1
δ(qB,qrs)={qC}; p(qC / qrs, qB)=1
δ(qC,b)={qD}; p(qD / b, qC)=1
δ(qD,b)={qE,qG}; p(qE / b, qD)=1
p(qG / b, qD)=1
δ(qD,t)={qF}; p(qF / t, qD)=1
δ(qF,b)={qG}; p(qG / b, qF)=1
δ(qG,b)={qH}; p(qH / b, qG)=1
δ(qG,p)={qA}; p(qA / p, qG)=1
δ(qH,b)={q0}; p(q0 / pb, qH)=1
PDA stohastice sunt proiectate pentru a recunoaște limbaje stohastice insensibile la context: acestea sunt generalizări ale PDA nedeterministe. Limbajele stohastice controlate sintactic, simple, pot fi recunoscute de translatori stohastici controlați sintactic.
3.5. DEDUCEREA GRAMATICALĂ
Pană acum, am considerat că gramaticile care generează semnalele de recunoscut sunt date. Automatele utilizate pentru recunoaștere sau translație necesită cunoașterea gramaticii. Însă în majoritatea cazurilor practice gramaticile nu sunt date. În general, se dă un anumit număr de eșantioane de semnal care aparțin unei aceleiași clase. Acestea sunt date de ”profesor” și se consideră ca o parte a setului de fnvățare. Considerând că toate eșantioanele au fost generate de o aceeași gramatică, este necesar să se determine acea gramatică (sau orice altă gramatică care poate genera setul). Problema se numește deducere gramaticală. Deoarece nu există o interrelație unică între L(G) și G, este posibil ca deducerea gramaticală să nu ofere soluții unice.
Deducerea gramaticală este definită astfel: se dă un set finit de
propoziții, S+, care aparține lui L(G); eventual, se mai dă un alt set de propoziții, S-, care aparține lui (toate propozițiile care nu aparțin lui L(G)); utilizând această informație,se cere să se deducă gramatica G.
Procedura de deducere depinde de cantitatea de informație inclusă în S+. Dacă S+ include toate propozițiile posibile, adică S+=L(G), el se numește complet. Dacă S+ este incomplet, dar fiecare regulă de rescriere a lui G este utilizată la generarea a cel puțin un șir în S+, se numește structural complet.
Au fost dezvoltați algoritmi de deducere pentru gramatici cu stări finite, insensibile Ia context și stohastice insensibile la context. Subiectul este în creștere de importanță.
3.6. EXEMPLE
3.6.1. Analiza sintactică a presiunii sanguine în carotidă
Monitorizarea detaliată a presiunii sanguine arteriale este foarte importantă în îngrijirea bolnavilor critic. Presiunea arterială poate fi monitorizată folosind un traductor de presiune, introdus într-o arteră prin intermediul unui cateter. Unda monitorizată este puternic corelată cu activitatea dinamică a inimii. O formă de undă de presiune tipică este prezentată în figura 3.7.
Unda poate fi divizată în două părți corespunzând fazelor sistolică și diastolică ale inimii. Principalele trăsături ale undei de presiune sunt: o creștere mare și rapida a presiunii la începutul sistolei, până la atingerea unui maxim (uneori cu o oscilație), urmată de o scădere a presiunii. Faza sistolică se încheie cu închiderea valvei aortice. Apoi presiunea crește datorită complianței aortei. Minimul presiunii prezent la sfârșitul sistolei se numește crestătură dicrotică.
Fig.3.7. Unda de presiune sanguină în carotidă și arborele relațional
Unda poate fi divizată în două părți corespunzând fazelor sistolică și diastolică ale inimii. Principalele trăsături ale undei de presiune sunt: o creștere mare și rapida a presiunii la începutul sistolei, până la atingerea unui maxim (uneori cu o oscilație), urmată de o scădere a presiunii. Faza sistolică se încheie cu închiderea valvei aortice. Apoi presiunea crește datorită complianței aortei. Minimul presiunii prezent la sfârșitul sistolei se numește crestătură dicrotică.
Artera carotidă este principala arteră care aprovizionează creierul, deci analiza presiunii în ea este de maximă importanță. Au fost sugerate metode sintactice de analiză. Stockman și Kanal au folosit un set de antrenare de 20 de unde de presiune pentru a testa algoritmul de analiză. Din 158 de unde analizate, 125 au fost corect recunoscute. Primitivele alese pentru a descrie semnalul au fost:
LLP o linie lungă cu panta pozitivă mare
MLP o linie de Iungime medie cu pantă pozitivă mare
MLN o linie de lungime medie cu pantă negativă mare
MP o linie de lungime medie cu pantă pozitivă
MN o linie de lungime medie cu pantă negativă
TE o linie lungă cu pantă negativă medie
HR o linie scurtă aproximativ orizontală
WPP parabolă largă,
NPP parabolă fngustă, vârf
WPV parabolă largă, vale
NPV parabolă îngustă, vale
RPM partea dreaptă a maximului de parabolă
LPM partea stângă a maximului de parabolă
O sistolă tipică poate conține următoarele primitive: LLP, WPP, WPV, WPP, MLN. O diastolă tipică poate conține: NPP, WPP, TE.
O gramatică insensibilă la context care descrie semnalul este:
G = (VN, VT, R, (puls)), (3.13)
unde:
VN = {(puls), (sistolă), (diastolă), (maxim), (M1), (M2), (M3), (undă dicrotică), (undă pozitivă), (undă negativă)
VT = {LLP, MLP, MLN, MP, MN, TE, HR, WPP, NPP, WPV, NPV, RPM, LPM}
R: (puls) → (sistolă) (diastolă)
(sistolă) → LLP (maxim) MLN
(maxim) → (M1) (M2) (M3)
(maxim) → MP (M3)
(maxim) → (M1) MN
(diastolă) → TE
(diastolă) → (unda dicrotică) TE
(undă dicrotică) → WPP
(undă dicrotică) → HR
(undă dicrotică) → NPP
(undă dicrotică) → NPP WPP
(M1) → LPM
(M1) → (undă pozitivă)
(M2) → WPV
(WI2) → (undă negativă)
(M3) → RPM
(M3) → WPP
(undă pozitivă) → WPP
(undă pozitivă) → WPP MLN
(undă negativă) → NPV
(undă negativă) → NPV MLP.
Câteva dintre undele care aparțin lui L(G) sunt următoarele: {LLP, MP, RPM, MLN, WPP, TE}, {LLP, LPM, WPV, RPM, MLN, HR, TE}, {LLP, WPP, MLN, MN, MLN, TE}.
3.6.2. Analiza sintactică a ECG
Au fost dezvoltați mai multi algoritmi sintactici pentru analiza ECG, în special pentru detecția QRS. Un algoritm simplu de detecție sintactică QRS, implementat pe un echipament portabil, de dimensiuni reduse, a fost dezvoltat de Furno și Tompkins. FSA conceput este:
A = (Σ, Q, δ, q0, {qQ, qN}) (3.14)
unde:
Σ= {normup, normdown, zero, other}
Q = {q0, q1, q2, qQ, qN }
Cele două stări terminale, q0 și qN, corespund complexului QRS, respectiv zgomotului. Regulile de tranziție a stărilor pentru A sunt:
δ(q0,normup) → {q1}
δ(q0,zero) → {q0}
δ(q0,other) → {qN}
δ(q1,normdown) → {q2}
δ(q1,other) → {qN}
δ(q2,normup) → {qQ}
δ(q2,other) → {qN}
Diagrama starilor de tranziție a automatului A este prezentată în figura 3.8:
Fig.3.8. Diagrama stărilor de tranziție a automatului A, pentru analiza ECG
Primitivele (normup, normdown, zero si other) se calculează după cum urmează. Semnalul ECG, x(t), este eșantionat cu perioada de eșantionare T. Derivata lui x(t) este aproximată cu prima diferență, s(k):
Eșantioanele {s(k)} sunt grupate împreună în secvențe. Fiecare secvență constă din eșantioane consecutive cu același semn.
Considerăm de exemplu cazul în care s(n -1)<0 și s(n)>0. O nouă secvență de prime diferențe pozitive este generată:
{s(n), s(n+ 1),…, s(m)J, (3.15)
unde s(m+1) este primul eșantion care este din nou negativ. Două numere sunt asociate secvenței dată de ecuația (3.15), lungimea secventei, SL și suma secventei, SM:
SL = m – n+1
(3.16)
Utilizând praguri predeterminate pentru SL și SM se extrag primitivele. Algoritmul operează în aproximativ de 10 ori timpul real.
Belforte & al. au propus un algoritm mai complex pentru detecția sintactică a QRS. S-au utilizat 3 derivații ECG. S-au calculat primele diferențe ale celor 3 semnale (ecuația 3.18), obținând si(k), i = 1, 2, 3. Pentru a extrage primitivele s-a utilizat energia primelor diferențe, sI2(k), i = 1, 2, 3. S-a determinat un prag pentru energie și s-au luat în considerație impulsurile peste acest prag. Valoarea maximă a unui impuls a fost notată cu ã, iar durata lui (cat este peste prag) cu đ. Cantitățile ã și đ au fost cuantizate brut folosind tabelul 3.1, obținându-se primitivele a, b, c.
Tab.3.1.Extragerea primitivelor pentru detecția QRS
Vârfurile au fost considerate ca aparținând unor evenimente diferite de fiecare dată când intervalul dintre ele a fost mai mare de 80 ms. Șirurile au fost astfel separate de sfârșitul simbolului șir, w.
Impulsurile de deasupra pragului pot proveni de la un complex QRS sau pot reprezenta zgomot. Un șir de la derivația i, care poate fi rezultatul unui complex QRS va fi numit ipoteză QRS și se notează Q. A fost dedusă o gramatică din eșantioane de învățare care întotdeauna au apărut cu complexe QRS, notată GQ. O altă gramatică, GZ, a fost introdusă ca reprezentând șiruri care în setul de învățare uneori au fost din complexe QRS, alteori nu. Cele două gramatici sunt date de:
GQ = {VNQ, VTQ, RQ, QRS} (3.17)
unde:
VNQ =(U1, U2, U3, U4, QRS}
Vq= {a, b,c}
RQ: QRS → bU1; QRS → cU2; QRS → aU4;
U1 → cU2; U1 → bU3; U1 → aU4;
U2 → bU1; U2 → cU2; U2 → aU4;
U3 → cU2; U3 → aU4; U3 → bU4;
U4 → aU4; U4 → bU4; U4 → cU4;
U4 → a; U4 → b; U4 → c;
și:
GZ={VNZ, VTZ, RZ, Z}
unde:
VNZ={Y1, Y2, Z} (3.18)
VTZ={b, c}
RZ: Z → cY1; Z → cY1;
Y1 → cY1; Y1 → bY2;
Y2 → cY2; Y2 → b;
De exemplu, șirurile {bcbcaa}, {bn}, (bcnaa} sunt generate de GQ și {cbb}, (bcnb} sunt generate de GZ.
Regula sugerată de Belforte & al. pentru recunoașterea unui eveniment QRS este urmatoarea. Fie Qi, i = 1, 2, 3, o ipoteză QRS emisă sub controlul gramaticii GQ în intervalul de timp {ti1, ti2}, unde i reprezintă numărul derivației. Fie, de asemenea, Zj, j = 1, 2, 3, ipoteza emisa sub controlul gramaticii GZ în intervalul de timp {tj1, tu2}. Pentru o derivație dată și un interval de timp dat, doar o ipoteză poate fi emisă, deoarece gramaticile GQ și GZ generează limbaje disjuncte.
Ipotezele Qi și Zj, i, j = 1, 2, 3, ale căror intervale de timp se suprapun parțial, se folosesc pentru a determina prezența sau absența unui complex QRS. Regula de decizie sugerată este:
h = Qi Λ (Qj V Zj), i, j = 1, 2, 3,. i ≠ j (1.19)
unde Λ și V sunt operatorii logici ”și” și ”sau inclusiv”. Un QRS este declarat dacă h = 1. Algoritmul a fost testat în timp real cu o bază de date de 620 QRS-uri de la 16 subiecți sănătoși și bolnavi, cu erori (alarme false) mai mici de 0,5% .
=== Capitol 4 ===
CAPITOLUL 4
EXEMPLU DE ABORDARE SINTACTICĂ ÎN ECG
4.1. INTRODUCERE
Electrocardiograma (ECG) este un instrument de diagnostic de uz larg în practica clinică. ECG pot fi divizate în trei categorii: 1) ECG de repaus, înregistrată de la pacienți ambulatorii în repaus, în scopul stabilirii rapide și simple a stării cardiace a pacienților sau al monitorizării efectelor tratamentelor. 2) ECG de efort, înregistrată de la pacienți care efectuează o anumită activitate (predefinită), pentru evidențierea prezenței / absenței unei boli coronariene. 3) ECG pentru monitorizarea aritmiilor, înregistrată de la pacienți în stare critică în unități de supraveghere intensivă sau pentru pacienți ambulatorii, în scopul detecției aritmiilor.
Interpretarea ECG este efectuată de medic, care aplică o procedură vizuală ce poate fi divizată în două etape. În prima etapă, el recunoaște anumite forme caracteristice ale ECG (unde, complexe, segmente, etc) și măsoară parametrii lor (durate, amplitudini, etc). În a doua etapă, el interpretează ECG utilizând rezultatele primei etape în conexiune cu un set prestabilit de criterii de diagnostic empirice.
Încercările de automatizare a procesului de interpretare ECG au început la sfarșitul anilor 50. Actualmente, majoritatea sistemelor de procesare ECG utilizate încearcă să imite cardiologul. Astfel, aceste sisteme îndeplinesc două sarcini distincte. Prima este o recunoaștere a formelor și măsurarea parametrilor lor. A doua este o sarcină de recunoaștere și este cea mai dificilă.
Există 3 abordări: 1) abordarea non-sintactică folosește tehnici de procesare clasică a semnalului (filtre adaptive, circuite basculante cu prag, corelație cu șablon, analiza spectrală, etc) și tehnici euristice. 2) abordarea sintactică folosește tehnici din domeniul recunoașterii sintactice a formei. 3) abordarea hibridă este o combinație a celorlalte două și folosește tehnici din domeniul inteligenței artificiale.
Sistemul computerizat de procesare a ECG, la fel ca și cel manual, realizează două funcții distincte. Prima se ocupă de recunoașterea formelor și măsurarea parametrilor, iar a doua este o funcție de interpretare, ce utilizează rezultatele furnizate de prima funcție. Partea mai complicată este cea de recunoaștere a formelor și de măsurare a parametrilor lor. Pentru automatizarea acestei funcții s-au folosit metode nonsintactice, sintactice și hibride.
Deși metoda sintactică pare foarte potrivită pentru problema de recunoaștere a formelor ECG și măsurare a parametrilor, nu s-au făcut progrese prea mari în acest domeniu. În încercările făcute au fost atacate doar anumite aspecte specifice ale acestei probleme. Astfel, au fost descrise gramatici insensibile la context, pentru recunoașterea vârfurilor în ECG; pentru detectarea complexelor QRS au fost propuse gramatici liniare și de atribut; pentru detectarea aritmiei ventriculare s-au folosit gramatici insensibile la context; pentru analiza aritmiei sunt descrise automate cu stări finite; s-a studiat metoda sintactică pentru filtrarea formelor ECG.
Acest capitol prezintă aplicarea metodei sintactice la problema legată de recunoașterea formelor ECG și măsurarea parametrilor. Sunt descrise și soluții la problemele de selecție a formelor primitive, extragere a formelor primitive, reprezentare lingvistică și exprimare a gramaticii de forme.
4.2. FORME ȘI PARAMETRII AI FORMELOR ÎN ECG
ECG este un biosemnal datorat activității electrice ale inimii omului și care se transmite la suprafața corpului. Captarea acestui semnal se poate face în diverse moduri. În prezent se utilizează două sisteme diferite. Primul este sistemul cu 12 derivații care captează 12 semnale subcomponente numite derivațiile I, II, III, AVR, AVL, AVF, V1, V2, V3, V4, V5 și V6. Primele șase sunt captate cu ajutorul electrozilor de pe membre, iar celelalte șase cu electrozii de pe piept. Al doilea sistem este sistemul cu 3 derivații, care înregistrează 3 semnale subcomponente numite X, Y și Z. Fiecare derivație este compusă dintr-un anumit număr de cicluri cardiace. Un ciclu cardiac tipic este prezentat în figura 4.1.
Formele electrocardiografice ce alcătuiesc un ciclu cardiac și care trebuie recunoscute sunt complexele, segmentele interunde și intervalele cardiace. Există 3 complexe: complexul P, complexul QRS, complexul T. parametrii ce trebuie măsurați la aceste forme sunt: 1) amplitudinea și durata complexelor și a unora din undele componente, 2) durata segmentelor interunde și a intervalelor cardiace. În consecință, trebuie realizate două tipuri de măsurători: măsurarea timpului și măsurarea amplitudinii. În plus, complexele QRS trebuie clasificate. În majoritatea cazurilor, acestea aparțin unei clase, dar există cazuri în care aparțin mai multor clase.
Figura 4.1: Ciclul cardiac și formele sale
4.3. ABORDAREA SINTACTICĂ ÎN RECUNOAȘTEREA UNDELOR ECG
Selecția formelor primitive
În recunoașterea sintactică a formei, problema se reduce la analiza formelor cu o gramatică ce descrie formele de interes. Primul pas în formularea unei gramatici a formei este determinarea unui set de forme primitive, cu ajutorul cărora pot fi descrise formele de interes. Al doilea pas este formularea gramaticii în sine. În cazul ECG, prima etapă are două subetape. În prima subetapă, se selectează patternurile primitive care compun undele EGG. în a doua, se aleg simbolurile primitive (terminale) pentru gramatica formei. Această selecție se bazează pe caracteristicile formelor primitive alese în prima subetapă.
De cele mai multe ori, unica primitivă a fost segmentul de linie. Astfel, fiecare undă ECG este considerată ca o concatenare de segmente de linie. Motive: acest tip de primitive este ușor de procesat; segmentele de linie pot fi ușor codate ca simboluri terminale într-o gramatică a formei care descrie ECG folosind caracteristici ca pantă, lungime, etc. În literatura de specialitate au mai fost propuse ca forme primitive și triunghiurile. Primele sunt de nivel mic, în timp ce triunghiurile sunt dificil de extras.
În lucrarea de față am ales ca forme primitive vârful, segmentul de linie dreaptă și segmentul parabolic, deoarece complexele sunt formate din vârfuri, iar segmentele au forma de linie dreaptă sau de parabolă.
Forma vârfului este prezentată în figura 4.2:
Figura 4.2: Reprezentarea unui vârf
Această formă e acea parte din semnal care e demarcată de trei puncte caracteristice: limita stângă a vârfului, extremitatea vârfului și respectiv limita dreaptă a vârfului. Totalitatea punctelor dintre limita stângă a vârfului și extremitatea vârfului formează brațul stâng al vârfului. Totalitatea punctelor dintre extremitatea vârfului și limita dreaptă a vârfului formează brațul drept al vârfului. În cele ce urmează vârfurile vor fi simbolizate cu P1, P2, …, cu Pi este notat vârful i. În formă digitală fiecare derivație a ECG se reprezintă cu y1, y2, …, yn, unde yi este amplitudinea în microvolți a eșantionului i.
Fiecărei forme primitive i se asignează un set de atribute. Valorile acestor atribute sunt calculate în cadrul fazei de extragere a primitivelor și sunt utilizate în cadrul procesului de recunoaștere. Acestea contribuie atât la recunoașterea formelor cât și la măsurarea parametrilor formelor. Adică, se utilizează și în scop calitativ și în scop cantitativ.
Fiecărui vârf Pi i se atașează un set de șapte atribute, set simbolizat: {xlk, ylk, xmk, ymk, xrk, yrk, ek}, unde:
(xlk, ylk) reprezintă marginea stângă a vârfului Pk,
(xmk, ymk) reprezintă maximul vârfului Pk,
(xrk, yrk) reprezintă marginea dreaptă a vârfului Pk,
ek reprezintă energia vârfului Pk, definită astfel:
, p=xlk+1, q=xrk.
Un set de patru atribute se atașează fiecărui segment de linie dreaptă sau parabolă. Acest set se simbolizează: {xlS, ylS, xrS, yrS}, unde:
(xlS, ylS) reprezintă punctul de start al segmentului S,
(xrS, yrS) reprezintă punctul de sfârșit al segmentului S.
4.3.2. Extragerea formelor primitive
Metoda dezvoltată pentru extragerea formelor primitive a fost prezentată în [1]. Metoda se focalizează pe extragerea vârfurilor. Vârfurile zgomotoase sunt recunoscute direct utilizând un set de criterii stabilite empiric. Vârfurile reale sunt recunoscute prin eliminarea vârfurilor zgomotoase din setul total de vârfuri. Algoritmul dezvoltat pentru calcularea limitelor vârfului se bazează pe presupunerea apriori că local, curbura este maximă în aceste puncte. În calcul se execută următorii patru pași: 1) se stabilește un interval de căutare, 2)punctele date din acest interval se aproximează cu o funcție cubică, 3)curbura k se calculează în fiecare punct t din interval cu formula și 4) punctul din acest interval în care curbura are valoarea maximă este luat ca punct limită.
Extragerea segmentelor se bazează pe limitele anterior calculate ale vârfurilor, care sunt și limite ale segmentelor în sensul următor: dacă limita dreaptă a vârfului Pi este foarte aproape de limita stângă a vârfului Pi+1, atunci nu există segment între vârfurile Pi și Pi+1, altfel există un segment care are ca limită stângă limita dreaptă a vârfului Pi, și ca limită dreaptă limita stângă a vârfului Pi+1. Ulterior se poate decide dacă segmentul este liniar sau parabolic.
4.3.3. Reprezentare lingvistică
Pentru codarea formelor de undă ECG a fost adoptat alfabetul de simboluri: Σ = {K+, K-, E, Π}, unde K+ reprezintă vârf pozitiv, K- vârf negativ, E segment de linie dreaptă, Π segment parabolic. Astfel o undă de formă EKG se reprezintă lingvistic sub forma unui string de simboluri din alfabetul Σ. Fiecărui simbol i se asociază valorile atributelor corespunzătoare.
4.3.4. Gramatica formelor
În recunoașterea sintactică a formelor, funcția de recunoaștere este esențial redusă la faptul ca analiza gramaticală a reprezentării lingvistice a formelor să fie recunoscută cu un analizor ce utilizează o gramatică stabilită, numită “gramatica formelor”. Gramatica formelor descrie formele ce trebuie recunoscute într-un mod formal, și formularea gramaticii formelor este totdeauna problema crucială în aplicațiile de recunoaștere aformelor, abordate sintactic.
În cazul electrocardiogramei, unde există un număr mare de morfologii diferite ale formelor, și unde din cauza zgomotului se pot găsi alte morfologii, și unde trebuie măsurați diverși parametri, ca model pentru gramatica formelor sunt necesare gramatici puternice, capabile să descrie atât sintaxa cât și semantica. Datorită puterii lor de descriere a caracteristicilor structurale și statistice, gramaticile de atribut sunt selectate în această lucrare, ca model pentru formularea gramaticii de forme pentru ECG. Alte motive, comune oricărei abordări statistice a recunoașterii formelor, pentru această alegere sunt următoarele: 1) prin introducerea de atribute în simboluri (terminale și nonterminale) se reduce complexitatea gramaticală rezultând o creștere a vitezei de analiză gramaticală; 2) tehnologia procesării gramaticii de atribute este destul de avansată, existând multe implementări de evaluatori. O descriere generală a gramaticii de atribute poate fi găsită în literatura de specialitate.
Pentru descrierea undelor de formă ECG, s-a formulat o gramatică de forme, bazată pe gramaticile de atribute, utilizând cunoașterea a priori a structurii ECG. Această gramatică de forme este dată în [11]. Ea recunoaște formele electrocardiografice și măsoară parametrii lor necesari în faza de recunoaștere a formelor și măsurare a parametrilor din cadrul unui sistem de procesare ECG. Realizează de asemenea și clasificarea complexelor QRS.
Gramatica de forme a fost formulată în așa fel încât să poată fi folosită pentru a analiza atât șiruri de intrare fără erori, cât și șiruri de intrare cu erori. Gramatica este capabilă să facă față erorilor datorate vârfurilor zgomotoase din segmentele interunde, recunoscute în timpul fazei de extragere a primitivelor ca reale. Regulile sintactice sunt scrise în așa fel încât să se aplice mai întâi alternativele pentru șiruri de intrare fără erori. Dacă nu se ajunge la nici o soluție, atunci se aplică alternativele care presupun prezența unor vârfuri eronate (zgomotoase).
Atributele simbolurilor terminale (forme primitive) sunt de asemenea utilizate ca atribute sintetizate pentru simboluri nonterminale. În plus, alte 11 atribute sunt folosite pentru simbolurile nonterminale:
Unele din cele mai importante funcții ale gramaticii de forme din [11], sunt descrise pe scurt mai jos.
1) Detecția și Recunoașterea QRS: O serie de n (1≤n≤7) vârfuri consecutive e recunoscută drept complex QRS dacă:
a), unde ε1 este o valoare de prag.
b)Unghiul dintre brațul drept al vârfului i și brațul stâng al vârfului i+1, i=1(1)n-1, este mai mic decât ε2, unde ε2 este o valoare de prag.
Primul criteriu, care e similar cu transformarea nelineară a energiei în timp scurt utilizată de unii cercetători, e adoptat aici datorită potrivirii sale cu abordarea sintactică și pentru că oferă rezultate bune. Punctele eșantion luate în sumă sunt cele corespunzătoare complexelor QRS, în timp ce un număr constant de eșantioane e utilizat în transformare.
Criteriul unghiului previne amestecarea vârfurilor complexelor P sau T cu complexele QRS.
Morfologia QRS-urilor e determinată de alternativa regulii sintactice care potrivește QRS-urile.
2) Detecția și recunoașterea P,T: Unu sau două vârfuri sunt recunoscute ca și complexe P sau T prin compararea lățimii și amplitudinii lor cu pragurile ε1 respectiv ε2, în funcție de regula sintactică cu care au fost evaluate. Acestea sunt deosebite de alte vârfuri (zgomotoase) prin compararea energiilor lor. Vârfurile zgomotoase în regiunea dintre două complexe QRS trebuie să aibă energie mai mică decât energia complexelor P și T în acea regiune. Alternativa regulii sintactice care potrivește formele P și T specifică morfologia ei. De notat că complexele P și T care apar înainte de primul și după ultimul complex QRS nu sunt recunoscute. Acest lucru simplifică gramatica.
3) Clasificarea complexelor QRS: Clasificarea complexelor QRS se realizează cu algoritmul celui mai apropiat vecin. Distanța dintre un complex QRS dat și o clasă dată de complexe QRS se calculează ca media distanțelor dintre complexul QRS dat și fiecare complex QRS din clasa dată. În calculul distanței se iau în considerare ambele caracteristici, atât cea morfologică (structurală), cât și cea cantitativă (statistică). Caracteristicile statistice utilizate sunt durata normalizată și amplitudinea normalizată. Caracteristicile morfologice, în calculul distanței dintre două complexe, sunt luate în considerare prin alinierea complexelor astfel încât ele să coincidă cât mai bine.
4.4. IMPLEMENTARE
Metoda sintactică de rezolvare a problemei de recunoaștere a fomelor și măsurare a parametrilor ECG, așa cum a fost descrisă mai sus, a fost implementată cu un sistem numit SERAMS (Syntactic ECG Recognition And Measurement System). Structura acestuia se prezintă în figura 4.3:
Figura 4.3.: Structura sistemului SERAMS
Componenta de achiziție ECG este responsabilă pentru achiziția a câte unui ECG în formă digitală. Componenta de extragere primitive extrage primitivele fiecărei unde de formă ECG și le codează astfel încât fiecare undă de formă este transformată în șir de simboluri (reprezentare lingvistică), fiecare simbol fiind însoțit de un set de valori de atribute. Componenta de evaluare a gramaticii de atribut are la o intrare gramatica din Apendix, iar la cealaltă reprezentarea lingvistică (împreună cu atributele ei) a undei de formă. Aceasta recunoaște formele electrocardiografice ale acestei unde de formă și le măsoară parametri. În final, componenta formator de ieșire a acestui sistem formează rezultatele recunoașterii și măsurării.
4.5. CONCLUZII
În aplicația descrisă în acest capitol, referitoare la abordarea sintactică a recunoașterii formelor ECG și măsurării parametrilor lor, s-au obținut rezultate inferioare comparativ cu rezultatele obținute prin unele implementări nonsintactice. Dar trebuie luat în considerare faptul că abordarea sintactică e un domeniu mai nou și, folosind implementări îmbunătățite s-ar putea obține rezultate mai bune.
S-a constatat că modulul de extragere a formelor primitive în unele nu delimitează foarte bine marginile vârfului. Această eroare se propagă în următoarele etape. Eliminând această deficiență s-ar putea îmbunătății considerabil performanța acestei abordări. Cu toate acestea doar o mică parte din vârfurile zgomotoase n-au fost rejectate, fiind confundate cu vârfurile reale. Nu s-au constatat erori datorate gramaticii, rar fiind observate omiteri sau recunoașteri incorecte ale complexelor.
În afară de acuratețe, abordarea sintactică posedă câteva caracteristici importante care o recomandă: simplitate, claritate, ușor de înțeles, ușurință în a modifica programul ce implementează metoda. În afară de operațiile de extragere a primitivelor și de intrare/ieșire, restul abordării nu e codat ci specificat. Avem aici un caz de programare semiautomată. Acesta e marele avantaj al abordării sintactice. Dacă se găsesc metode de îmbunătățire a acurateții rezultetelor, atunci abordarea sintactică va fi superioară celei nonsintactice.
=== INTRO ===
INTRODUCERE
Dezvoltarea rapidă a tehnicii în domeniul electronic și informatic a determinat apariția a noi specializări la granița dintre inginerie și celelalte științe.
Electronica medicală este un domeniu tânăr ce a profitat din plin, astăzi neexistând sisteme de diagnostic decât asistate de aparatură dedicată sau calculatoare. Acestea permit procesarea în scopul diagnosticării a semnalelor bioelectrice, afișarea și înregistrarea grafică. Baze de date complexe conținând mostre de semnale permit compararea și stabilirea diagnosticului în cel mai scurt timp.
Această lucrare se prezintă ca un studiu biliografic referitor la metode de analiză sintactică cu exemplificare pe analiza elactrocardiogramei
Alături de acestea există tehnici de mediere temporală și în domeniul frecvență, detecție wavelet, procesare punctuală, care nu fac însă subiectul acestei lucrări.
Proiectul este structurat astfel:
Capitolul 1 prezintă câteva noțiuni generale de anatomie și fiziologie a cordului. Se prezintă de tehnica de investigare a activității electrice a inimii,electricardiografia.
Capitolul 2 este vast, conținând metode sintactice de recunoaștere a formelor și de analiză a semnalelor. Este structurat pe subcapitole în care se prezintă noțiuni despre structurile de șiruri, structurile sintactice regulate, structurile de arbori și grafuri.
Capitolul 3 cuprinde noțiuni de analiză sintactică a semnalelor cu exemplificări pe semnale electrocardiografice.
Capitolul 4 prezintă un exemplu de abordare sintactică în domeniul recunoașterii și a procesării semnalelor ECG.
Programul efectiv și rezultatul simulării sunt atașate în anexă pentru a putea fi verificate.
În faza finală, proiectul se constituie atât ca aplicație pentru laboratorul de electronică medicală cât și ca lucrare știițifică.
Copyright Notice
© Licențiada.org respectă drepturile de proprietate intelectuală și așteaptă ca toți utilizatorii să facă același lucru. Dacă consideri că un conținut de pe site încalcă drepturile tale de autor, te rugăm să trimiți o notificare DMCA.
Acest articol: Analiza Sintactica a Biosemnalelor (ID: 131249)
Dacă considerați că acest conținut vă încalcă drepturile de autor, vă rugăm să depuneți o cerere pe pagina noastră Copyright Takedown.