Análise de Sinal Fisiológico usando Métodos Não Lineares

Análise de Sinal Fisiológico usando Métodos não Lineares João Manuel Monteiro dos Santos Mestrado em Ciência de Computadores Departamento de Ciência de Computadores 2015 Orientador Luís Filipe Coelho Antunes, Professor Associado Faculdade de Ciências da Universidade do Porto Coorientador Cristina Maria Nogueira da Costa Santos, Professora Auxiliar Faculdade de Medicina da Universidade do Porto Todas as correções determinadas pelo júri, e só essas, foram efetuadas. O Presidente do Júri, Porto, ______/______/_________ Para os meus Pais e Av´os 3 Agradecimentos Gostaria de agradecer, de uma forma geral, a todos os que de certa forma me acompanharam e ajudaram a que este trabalho pudesse ser realizado. Em particular, e em primeiro lugar, quero agradecer ao Professor Lu´ıs Antunes por me ter proposto este trabalho e por me ter dado a oportunidade de trabalhar com ele. A sua simpatia, disponibilidade, apoio e m´etodos de trabalho proporcionaram a que todas as etapas de concretiza¸c˜ao desta disserta¸c˜ao fossem realizadas com enorme satisfa¸c˜ao, alegria e grande aprendizagem. Em segundo lugar, o meu agradecimento vai para a Professora Cristina Santos, que sempre se mostrou dispon´ıvel para ajudar na an´alise de resultados, propor sugest˜oes e ter proporcionado a oportunidade de assistir `as suas aulas. As pessoas a quem eu mais devo, por me terem proporcionado uma educa¸c˜ao de excelˆencia e oportunidade de ingressar no ensino superior s˜ao os meus pais. A eles devo tudo o que sou hoje. Quero agradecer ao meu irm˜ao Rui, essencialmente por ter ajudado os pais nas tarefas dom´esticas durante o per´ıodo em que estive menos dispon´ıvel. ` A Rita, um muito obrigado pela empatia demonstrada, paciˆencia que teve comigo, e por me ter ajudado a corrigir erros presentes na disserta¸c˜ao. Quero tamb´em agradecer `a Teresa Henriques pela ajuda que forneceu na realiza¸c˜ao da tese, atrav´es n˜ao s´o dos seus trabalhos, como tamb´em pela disponibilidade demonstrada. Por fim, uma palavra de agradecimento ao Lu´ıs Maia, pelo tempo disponibilizado na instala¸c˜ao de software necess´ario para a realiza¸c˜ao da tese. 4 Resumo Numa sociedade onde a procura de novas t´ecnicas de avalia¸c˜ao de sinais fisiol´ogicos se tornou evidente, o bem-estar de um beb´e `a nascen¸ca ´e sem d´uvida uma prioridade. Por isso, e por forma a tentar diminuir a mortalidade e morbilidade de um feto, a an´alise de cardiotocogramas atrav´es do estudo de tra¸cados de batimento card´ıaco fetal ´e cada vez mais uma realidade. Nesta tese, tivemos como objetivo analisar os tra¸cados de batimento card´ıaco fetal, procurando caracter´ısticas biol´ogicas que estejam relacionadas de certa forma com a compress˜ao de ficheiros. Para isso, foi comparado o desempenho de trˆes compressores diferentes (bzip2, gzip e paq8l) e avaliado se a utiliza¸c˜ao da t´ecnica de wavelets traz algum benef´ıcio no estudo de tra¸cados de batimento card´ıaco fetal. Por fim, foi utilizado o algoritmo CompLearn e a respetiva ´arvore de classifica¸c˜ao no processo de clustering dos tra¸cados. A menos da capacidade de compress˜ao, os trˆes diferentes compressores apresentaram comportamentos semelhantes na an´alise de tra¸cados obtidos entre as semanas 24 e 40 da gravidez. Not´amos, em geral, uma maior compress˜ao dos tra¸cados de fetos considerados patol´ogicos, um comportamento similar entre g´eneros com exce¸c˜ao da semana 27 para os tra¸cados de fetos considerados normais, e uma diferen¸ca de comportamento nos patol´ogicos ap´os as 36 semanas de gravidez. Observ´amos um crescimento est´avel da taxa de compress˜ao nos tra¸cados de fetos com peso normal `a nascen¸ca ao contr´ario daqueles que est˜ao abaixo do percentil 3, onde se nota um crescimento inst´avel. A t´ecnica wavelet, a partir de um conjunto de dados pr´e-categorizado em Normal, Suspeito e Patol´ogico, atrav´es do pH do cord˜ao umbilical `a nascen¸ca, n˜ao trouxe grandes benef´ıcios. Por´em, resultados positivos foram obtidos na predi¸c˜ao de prematuridade usando a wavelet daubechies. Para avaliarmos o CompLearn foram feitos dois testes. Dividimos o conjunto de dados pelo pH do cord˜ao umbilical e atrav´es da variabilidade curta dos tra¸cados. Verific´amos 5 n˜ao haver rela¸c˜ao entre o pH e a compress˜ao, ao contr´ario da variabilidade curta, onde tra¸cados com variabilidade curta inferior a 30 e superior a 70 foram separados com sucesso pelo algoritmo e a ´arvore de classifica¸c˜ao. 6 Abstract In a society where the search for new evaluation techniques of physiological signals has become a reality, the well being of a baby is without a doubt a priority. Therefore, and in a way to decrease the mortality and morbidity of a baby born, the cardiotocograms’ analyses through the study of heart rate frequency tracings is increasingly something to take in account. In this thesis, we wanted to analyse the fetal heart rate frequency tracings, searching for biological characteristics that are related with data compression. For that, we compared the performances of three different compressors: bzip2, gzip and paq8l. It was also analyzed if the usage wavelet trasforms would be beneficial for the study of tracings of fetus heart rate compared to normal data compression. At last, we used the CompLearn algorithm and its classification tree in the process of clustering the tracings organized either by the pH of the umbilical cord at birth or the short term variability (STV) of the tracings. Despite of the compression power difference between the three tested compressors, all of them performed quite similarly in the analyes of traces obtained between week 24 and 40 of gestation. Also, we noticed a slightly better compression of traces considered pathologic, a similar behaviour was noted between genders with the exception for week 27 for the normal tracings, and a different behaviour for pathologic tracings after week 36 of pregnancy. A stable growth throughout gestation time was observed in the compression ratio of fetus tracings whose weight at birth was considered normal, however an unstable growth is noticeable for those below weight, namely those under percenile 3. The wavelet technique was not very helpful using a dataset divided in Normal, Suspect and Pathologic tracings by pH. However, positive results were achieved predicting prematurity of fetuses using the daubechies wavelet. To evaluate CompLearn two different tests were done. One in which the dataset was 7 divided by pH of the umbilical cord and the other by short term variability (STV). We verified that there was no relation between compression used in CompLearn and pH. On the other hand, the algorithm successfully clustered tracings with low STV and high STV. 8 Conte´udo Resumo 5 Abstract 7 Lista de Figuras 14 1 Introdu¸c˜ao 15 1.1 Estruturadatese.............................. 18 2 CompLearn 19 2.1 Defini¸c˜oes e Introdu¸c˜ao T´ecnica . . . . . . . . . . . . . . . . . . . . . . 21 2.1.1 FinitoeInfinito........................... 21 2.1.2 Strings eLinguagens........................ 21 2.1.3 C´odigos Instantˆaneos e Univocamente Decifr´aveis . . . . . . . . 21 2.2 M´aquinasdeTuring............................. 23 2.3 Complexidade de Kolmogorov . . . . . . . . . . . . . . . . . . . . . . . 24 2.3.1 Complexidade de Kolmogorov condicionada . . . . . . . . . . . 25 2.3.2 Aleatoriedade e Compress˜ao . . . . . . . . . . . . . . . . . . . . 25 2.3.3 Universalidade de K . . . . . . . . . . . . . . . . . . . . . . . . 26 2.3.4 K vs Probabilidade Cl´assica . . . . . . . . . . . . . . . . . . . . 26 2.3.5 Incomputabilidade da Complexidade de Kolmogorov . . . . . . 28 9 CAP´ ITULO 1. INTRODUC¸ ˜ AO 16 Figura 1.1: Diagrama de certeza-concordˆancia proposto por Stacy. A an´alise computacional de cardiotocogramas fornece parˆametros quantitativos que muito dificilmente s˜ao percet´ıveis ao olho humano. O Sisporto ´e um programa desenvolvido nas ´ultimas duas d´ecadas que tem como fun¸c˜ao uma an´alise automatizada dos tra¸cados n˜ao s´o em tempo real como tamb´em armazena os dados de forma a que possam ser processados posteriormente. Os conjuntos de dados trabalhados nesta disserta¸c˜ao provieram do Sisporto. Resumidamente, e apenas para introduzir conceitos relevantes para esta tese, a an´alise dos tra¸cados ´e feita da seguinte forma: ´e considerado um ponto de variabilidade curta (STV) anormal quando a diferen¸ca entre dois sinais adjacentes ´e menor que 1 bpm (linhas vermelhas na parte superior da Figura 1.2). A m´edia do STV e a percentagem de pontos com STV anormal s˜ao calculados e ´e poss´ıvel a sua visualiza¸c˜ao na parte inferior da Figura 1.2. Quando a diferen¸ca entre o m´aximo e o m´ınimo, num intervalo de 60 segundos centrado no ponto sem acelera¸c˜oes ou desacelera¸c˜oes, n˜ao excede os 5 bpm, ´e considerado um ponto de variabildade longa (LTV) anormal. As m´edias de STV e LTV e a percentagem de pontos com STV anormal e LTV anormal s˜ao calculados e ´e poss´ıvel a sua visualiza¸c˜ao na parte inferior da Figura 1.2 [5]. CAP´ ITULO 1. INTRODUC¸ ˜ AO 17 Figura 1.2: An´alise de um cardiotocograma pelo Sisporto. Na defini¸c˜ao de estado patol´ogico s˜ao tidas duas abordagens: uma usando o pH do cord˜ao umbilical `a nascen¸ca e outra usando o´ındice Apgar. O pH do cord˜ao umbilical ´e um indicador de acidemia fetal e geralmente varia entre 7,05 e 7,4 sendo indicador de bem-estar quando superior a 7,2. O ´ındice Apgar ´e um sistema de avalia¸c˜ao feito ao primeiro e quinto minutos ap´os o parto onde cinco sinais vitais s˜ao avaliados numa escala de 0 a 2, Appearence (cor da pele), Pulse (frequˆencia card´ıaca), Grimace (resposta a est´ımulos), Activity (t´onus muscular) e Respiration (respira¸c˜ao ou choro). Nesta disserta¸c˜ao, o Apgar usado foi ao quinto minuto. Em 2005, um novo m´etodo de clustering usando compress˜ao foi introduzido por Cilibrasi e Vit´anyi [6] e obteve bons resultados em ´areas distintas como m´usica, an´alise de tr´afego na internet, gen´omica, etc [5]. ´ E o objetivo desta disserta¸c˜ao procurar rela¸c˜oes entre as caracter´ısticas dos tra¸cados de batimento card´ıaco fetal e a compress˜ao. Definimos como taxa de compress˜ao a raz˜ao entre o tamanho do ficheiro comprimido e o ficheiro original. Foi tamb´em definido r´acio de compress˜ao (CR) o inverso da taxa de compress˜ao, isto ´e, a propor¸c˜ao entre o tamanho do ficheiro original e a respetiva vers˜ao comprimida. CAP´ ITULO 1. INTRODUC¸ ˜ AO 18 1.1 Estrutura da tese No cap´ıtulo 2 ser˜ao abordados os conceitos primordiais intr´ınsecos `a compress˜ao de ficheiros, mencionando conceitos de Teoria de Informa¸c˜ao, m´aquinas de Turing e complexidade de Kolmogorov. Ser´a aqui definida a Distˆancia de Compress˜ao Normalizada, conceito importante na descri¸c˜ao do algoritmo CompLearn. Toda esta sec¸c˜ao foi baseada no trabalho de Rudi Cilibrasi [1]. No cap´ıtulo 3 ser˜ao dadas a conhecer as wavelets, uma t´ecnica recente desenvolvida com base nas transformadas de Fourier. Estes dois cap´ıtulos representam assim o estado da arte. A an´alise dos resultados obtidos ser´a feita no cap´ıtulo 4, e ser´a dividida em trˆes sec¸c˜oes. Em 4.1 ser˜ao comparados os resultados dos compressores gzip, bzip2 e paq8l na compress˜ao de tra¸cados e respetivas rela¸c˜oes com o desenvolvimento do feto e diferen¸cas entre g´eneros, tempo de gesta¸c˜ao e peso da crian¸ca `a nascen¸ca. No subcap´ıtulo 4.2, ir´a ser avaliado se a utiliza¸c˜ao das transformadas wavelets traz benef´ıcios na an´alise de batimento card´ıaco fetal e por fim, em 4.3, ir´a ser comparado o algoritmo CompLearn (e respetiva ´arvore de classifica¸c˜ao) com o pH do cord˜ao umbilical do beb´e `a nascen¸ca e a variabilidade curta do tra¸cado durante o cardiotocograma. Cap´ıtulo 2 CompLearn H´a mais de 30 anos que se desenvolve software com o objetivo de comprimir dados e novos modelos para quase todo o tipo de ficheiros tˆem aparecido. At´e h´a bem pouco tempo, o interesse nesta tecnologia era direcionado para a diminui¸c˜ao de espa¸co em disco ou custos de transmiss˜ao de dados, mas, ultimamente, uma nova abordagem tem surgido. Aqui, pretendemos abordar este novo conceito que visa usar compressores no sentido de nos ajudarem no processo de clustering, que neste trabalho s˜ao tra¸cados de batimento card´ıaco fetal. Enquanto grande parte das pessoas est´a familiarizada com o conceito de compress˜ao de ficheiros, uma propriedade menos conhecida dita que a combina¸c˜ao de dois ou mais ficheiros concatenados, produzindo um ficheiro muito maior antes da compress˜ao, muitas vezes gera melhores r´acios de compress˜ao comparada com a compress˜ao individual desses mesmos ficheiros. Esta propriedade ´e v´alida para programas como o tar ou pkzip. O conceito chave subjacente ´e que se dois ficheiros s˜ao muito semelhantes, ent˜ao o tamanho da vers˜ao comprimida desses ficheiros aglomerados ser´a bem menor que a soma dos ficheiros comprimidos separadamente. Por outro lado, se os ficheiros n˜ao tiverem nada em comum, este m´etodo n˜ao trar´a vantagem nenhuma e o seu resultado ser´a semelhante `a soma das vers˜oes comprimidas. Esta ideia bastante intuitiva tem tido resultados surpreendentes, mesmo usando compressores muito simples. No exemplo da Figura 2.1, foi retirado ADN mitocondrial de mam´ıferos e testado este m´etodo. Primeiro foi constru´ıda uma matriz, chamada a matriz de distˆancias, que calcula o qu˜ao semelhante cada par de ficheiros ´e. Esta distˆancia resulta da compara¸c˜ao dos ficheiros comprimidos mencionada atr´as. Depois foi constru´ıda uma ´arvore de acordo com essas distˆancias. Os resultados obtidos foram 19 CAP´ ITULO 2. COMPLEARN 20 excecionais (ver [1]). Figura 2.1: ´ Arvore filogen´etica constru´ıda usando ADN mitocondrial de mam´ıferos [1]. Este procedimento ´e bastante simples e pode ser usado em diversas ´areas. Com base nestas ideias, foi desenvolvido o CompLearn. Este software pode ser usado para classifica¸c˜ao ou clustering. O primeiro requer exemplos introduzidos pelo especialista. Clustering n˜ao requer nenhuma informa¸c˜ao `a priori e refere-se `a organiza¸c˜ao dos objetos em grupos. Aqui, ´e usado um cluster hier´arquico chamado quartet method que procura a ´arvore que mais se ajusta ao problema, onde objetos semelhantes estar˜ao pr´oximos, ao contr´ario daqueles que menos semelhan¸cas apresentam. Este m´etodo ´e n˜ao-determin´ıstico e tenta encontrar uma solu¸c˜ao num razo´avel intervalo de tempo, sacrificando alguma efic´acia. Como faz uso de n´umeros ”aleat´orios”, os resultados obtidos sofrem algumas varia¸c˜oes para o mesmo conjunto de dados. Na pr´oxima sec¸c˜ao abordaremos alguma da terminologia e teoria por tr´as deste m´etodo. Na sec¸c˜ao 2.2 ser˜ao dadas no¸c˜oes de m´aquinas de Turing e complexidade de Kolmogorov e na sec¸c˜ao 3 introduziremos a distˆancia de compress˜ao normalizada (NCD). CAP´ ITULO 2. COMPLEARN 21 2.1 Defini¸c˜oes e Introdu¸c˜ao T´ecnica Esta sec¸c˜ao tem o objetivo de familiarizar o leitor acerca de conceitos e nota¸c˜ao relevantes para o trabalho. Para informa¸c˜ao mais detalhada, o leitor deve ver [1, 7, 8]. 2.1.1 Finito e Infinito Podemos dividir o dom´ınio dos objetos matem´aticos em duas grandes categorias: os objetos finitos e o infinitos. Os primeiros s˜ao aqueles que podem ser delimitados enquanto os infinitos s˜ao sempre maiores do que qualquer poss´ıvel fronteira. Por exemplo, o conjunto dos divisores de um certo n´umero ´e finito, mas o conjunto de todos os n´umeros primos ´e infinito, embora seja poss´ıvel, em teoria, escrever um programa que consiga gerar todos esses n´umeros, supondo que se tem tempo e mem´oria ilimitada. A ideia de que conjuntos embora infinitos possam ser gerados por programas finitos ´e importante. 2.1.2 Strings e Linguagens Um alfabeto ´e simplesmente um conjunto de s´ımbolos usados para formar uma linguagem. Uma string ´e uma lista ordenada de 0 ou mais s´ımbolos de um alfabeto pr´edefinido, que neste trabalho ´e constitu´ıdo apenas pelos s´ımbolos 0 e 1, pois podemos codificar qualquer alfabeto num alfabeto bin´ario, da mesma forma que um byte ´e codificado em bits. Tem-se que Σ = {0,1}´e o alfabeto a ser usado e Σ∗constitui o espa¸co de todas as possibilidades de strings, incluindo a string vazia. Para uma dada string x,|x| representa o seu comprimento, em bits. 2.1.3 C´odigos Instantˆaneos e Univocamente Decifr´aveis Diz-se que uma string y´e prefixo de xse pudermos escrever x=yz, para um z diferente da string vazia. Um conjunto diz-se livre de prefixos (ou instantˆaneo) se nenhum elemento do conjunto for prefixo de outro. Os elementos de um conjunto livre de prefixos s˜ao chamados de palavras c´odigo. Os c´odigos instantˆaneos tˆem a vantagem de serem facilmente decifr´aveis porque os limites de cada palavra c´odigo est˜ao bem definidos, n˜ao dando hip´oteses a ambiguidades. CAP´ ITULO 2. COMPLEARN 22 Consideremos o conjunto dos naturais e a sua representa¸c˜ao bin´aria. De acordo com a Figura 2.2, notam-se dois n´umeros de comprimento 1, 4 de comprimento 2, e por a´ı fora. No entanto, existem menos palavras c´odigo livres de prefixo para cada comprimento. Assintoticamente, existem menos palavras c´odigo livres de prefixo de tamanho n do que 2npalavras fonte de tamanho n. Figura 2.2: Exemplo dos primeiros onze naturais, respetivas representa¸c˜oes bin´arias e tamanho da string [1]. Esta observa¸c˜ao ´e v´alida para c´odigos de prefixo arbitr´arios. A quantifica¸c˜ao desta intui¸c˜ao para um conjunto numer´avel e um c´odigo instantˆaneo arbitr´ario leva-nos a uma rela¸c˜ao designada como Desigualdade de Kraft: Lema Seja n1, n2, . . . , nkuma sequˆencia finita ou infinita de naturais. Existe um c´odigo instantˆaneo para esta sequˆencia como comprimentos do seu c´odigo bin´ario se e s´o se X k 2−nk≤1.(2.1) Queremos codificar elementos de um determinado conjunto de forma a que aquando da descodifica¸c˜ao estes sejam reconstruidos univocamente. A estes c´odigos damos o nome de univocamente decifr´aveis. Todo o c´odigo livre de prefixos ´e univocamente decifr´avel, embora o contr´ario nem sempre aconte¸ca. Isto ´e importante porque significa que se pode substituir qualquer c´odigo univocamente decifr´avel por um instantˆaneo sem que o conjunto dos tamanhos das palavras c´odigo se altere. CAP´ ITULO 2. COMPLEARN 23 Um c´odigo univocamente decifr´avel diz-se completo se a adi¸c˜ao de qualquer nova palavra c´odigo ao conjunto de palavras c´odigo resulta num c´odigo que j´a n˜ao ´e univocamente decifr´avel. Isto tem uma rela¸c˜ao muito pr´oxima com a desigualdade de Kraft pois acontece quando a igualdade se verifica. Sejam l1, l2, . . . palavras c´odigo de um c´odigo univocamente decifr´avel completo. Seja qx= 2−lx. Por defini¸c˜ao, temos que Pxqx= 1. Ent˜ao qxpode ser pensado como sendo a fun¸c˜ao massa de probabilidade correspondente a uma distribui¸c˜ao Q para uma vari´avel aleat´oria X. Diz-se que Q ´e a distribui¸c˜ao correspondente para l1, l2, . . . . Desta forma, cada c´odigo completo univocamente decifr´avel ´e mapeado numa ´unica distribui¸c˜ao de probabilidade. ´ E claro que isto ´e uma correspondˆencia meramente formal, pois podemos codificar elementos de um conjunto usando um c´odigo que corresponde a uma distribui¸c˜ao q, onde o resultado ´e distribu´ıdo segundo p6=q. Mas se o conjunto for distribu´ıdo segundo p, ent˜ao o c´odigo correspondente a p´e, em m´edia, o c´odigo que atinge a compress˜ao ´otima. Em particular, qualquer fun¸c˜ao massa de probabilidade p est´a relacionada com o c´odigo de prefixo de Shannon-Fano, de modo que o n´umero esperado de bits por palavra c´odigo transmitida ´e o mais baixo poss´ıvel para qualquer c´odigo de prefixo. Este c´odigo codifica a palavra xnuma palavra c´odigo de tamanho lx=dlog 1 p(x)e, onde P(X=x) = p(x), de tal forma que o tamanho esperado da palavra c´odigo transmitida seja Pxp(x) log 1 p(x)=H(X), a entropia de Shannon, que ser´a referida mais `a frente. 2.2 M´aquinas de Turing Esta sec¸c˜ao serve como prepara¸c˜ao para posteriormente ser introduzido o conceito de complexidade de Kolmogorov. Informalmente, a complexidade de Kolmogorov de uma string ´e o programa mais curto que a imprime e depois p´ara. Para tornar esta defini¸c˜ao mais precisa, usam-se as m´aquinas Turing universais, que s˜ao uma representa¸c˜ao matem´atica abstrata de um computador. S˜ao uma generaliza¸c˜ao e uma simplifica¸c˜ao de m´aquinas computacionais determin´ısticas. Uma m´aquina de Turing recebe como parˆametro de entrada uma cadeia de caracteres (que pode ser visto como um programa) e seguindo um certo conjunto de regras imprime o resultado desse programa. Tal como existem linguagens de programa¸c˜ao universais, i.e. linguagens onde ´e poss´ıvel escrever um compilador para qualquer outra linguagem, tamb´em existem m´aquinas de Turing Universais, que conseguem simular qualquer outra m´aquina. De uma forma geral, uma m´aquina de Turing consiste em: •uma fita dividida em c´elulas, cada uma preenchida por um s´ımbolo de um CAP´ ITULO 2. COMPLEARN 24 alfabeto finito (que cont´em um s´ımbolo que denota espa¸co em branco). ´ E assumido que a fita ´e extens´ıvel em ambos os lados tanto quanto necess´ario e que as c´elulas n˜ao escritas s˜ao constitu´ıdas pelo s´ımbolo branco; •um apontador que se movimenta para a esquerda e direita (um passo) e que consegue ler e escrever. No estado inicial situa-se no s´ımbolo n˜ao branco mais `a esquerda; •um registador de estados que armazena o estado da m´aquina, incluindo o estado inicial e final. O n´umero de estados ´e finito; •uma fun¸c˜ao de transi¸c˜ao que ir´a indicar para onde mover o apontador, que s´ımbolo escrever e em que estado se ir´a encontrar, com base no s´ımbolo de leitura e estado atual. Quando a fun¸c˜ao devolver o estado final, a m´aquina p´ara. Como interessam apenas os programas que retornam uma string finita, isto ´e programas que n˜ao entram em ciclo, dizemos que a fun¸c˜ao de transi¸c˜ao apenas est´a definida para programas que n˜ao resultem nestes loops. Para al´em disso, olhamos apenas para m´aquinas de Turing cujos programas formam c´odigos livre de prefixos, ou seja, nenhuma palavra do c´odigo ´e prefixo de outra. Isto ´e feito para evitarmos o problema da subaditividade na Complexidade de Kolmogorov. 2.3 Complexidade de Kolmogorov Formalmente, definimos Complexidade de Kolmogorov K, como uma fun¸c˜ao un´aria que mapeia a string xnum inteiro e est´a implicitamente condicionada a uma M´aquina de Turing Φ: KΦ(x) =    min{|p|: Φ(p) = x}, ∞,se p n˜ao existe. Por outras palavras, e como j´a foi dito, K´e o tamanho do programa mais pequeno que imprime xe p´ara. Esta rela¸c˜ao ´e identificada como KΦ(x). Na pr´atica, queremos usar uma m´aquina de Turing o mais gen´erica poss´ıvel. Exige-se que o conjunto de programas forme um conjunto livre de prefixo. N˜ao existe perda de generalidade porque qualquer m´aquina de Turing universal consegue simular outra, segundo o Teorema da Invariˆancia. CAP´ ITULO 2. COMPLEARN 25 2.3.1 Complexidade de Kolmogorov condicionada O conceito de complexidade de Kolmogorov condicionada ´e um pouco mais dif´ıcil de perceber. Esta forma da fun¸c˜ao K, definida como K(z|y) espera n˜ao um argumento mas sim dois. Podemos defini-la como o tamanho, em bits, do menor programa que imprime zdada uma codifica¸c˜ao. Podemos entender ycomo o input inicial da fita. A ideia ´e que se ytiver muita informa¸c˜ao acerca de z, ent˜ao K(z|y)K(z), mas se y ezn˜ao estiverem relacionados, teremos K(z|y)≈K(z). 2.3.2 Aleatoriedade e Compress˜ao O objetivo de Kolmogorov com este trabalho era obter uma defini¸c˜ao formal de sequˆencia aleat´oria e observou que algumas sequˆencias bin´arias poderiam ser comprimidas segundo um algoritmo. Como se constata, K fornece um meio para caracterizar sequˆencias aleat´orias. Contrariamente ao que se possa pensar, sequˆencias aleat´orias n˜ao s˜ao simplesmente sequˆencias onde padr˜oes n˜ao sejam discern´ıveis. Existem regularidades estat´ısticas que podem ser observadas e provadas, mas a dificuldade encontrase simplesmente em express´a-las. Podemos definir aleatoriedade da seguinte forma: diz-se que uma string ´e k-aleat´oria se e s´o se K(x)>|x|−k. Esta rela¸c˜ao expressa a ideia que strings aleat´orias n˜ao s˜ao compress´ıveis. Olhemos para o n´umero π. Se nos focarmos nas casas decimais e estendermos o n´umero infinitamente, a string parece ser aleat´oria, mas sendo poss´ıvel escrever um programa que imprima os algarismos deste n´umero, esta ideia de que o π´e aleat´orio cai por terra. Esta produ¸c˜ao de um programa (finito) que gera uma sequˆencia infinita implica uma certa regularidade nos dados com grande probabilidade. Argumentos mostram que o n´umero de programas pass´ıveis de serem altamente comprimidos ´e bastante reduzido. Em particular, o r´acio de programas comprim´ıveis em apenas k bits n˜ao ´e mais do que 2−k. Para uma string de tamanho mtemos 2m possibilidades. Se considerarmos codifica¸c˜oes de tamanho mde uma fonte de string de tamanho n > m, ent˜ao temos no m´aximo 2mstrings diferentes codificadas de um total de 2n. Ent˜ao, o r´acio de strings pass´ıveis de compress˜ao por n−mbits ´e no m´aximo 2m−ndo total. CAP´ ITULO 2. COMPLEARN 32 at´e que apare¸ca um tal que C(z0) = C(x), resultando em z0=x. Pela unicidade de descompress˜ao, temos que C(y|x) ´e o n´umero extra de bits exigidos para descrever y ap´os a descri¸c˜ao de x.´ E intuitivo que a informa¸c˜ao comprimida condicional C(y|x) satisfaz a desigualdade triangular C(y|x)≤C(y|z) + C(z|x).(2.13) Lema Um compressor normal satisfaz a propriedade de subaditividade: C(xy)≤ C(x) + C(y). Esta propriedade ´e claramente exigida para uma compress˜ao vi´avel porque um compressor deve poder usar informa¸c˜ao presente em xpara comprimir y. Tal como referido anteriormente, alguma imprecis˜ao poder´a surgir na fronteira entre xey, mas ser´a insignificante para xeysuficientemente grandes. 2.4.3 Distˆancia de Informa¸c˜ao Normalizada Em [7] a distˆancia de informa¸c˜ao E(x, y) foi introduzida e definida como o tamanho do programa mais curto que dado input ximprime y. Os autores mostraram que a menos de uma quantidade logar´ıtmica, E(x, y) = max{K(x|y), K(y|x)}. Mostraram tamb´em que E(x, y) ´e uma m´etrica, embora com algumas viola¸c˜oes das desigualdades mencionadas. Em [8], a vers˜ao normalizada de E(x, y), chamada distˆancia de informa¸c˜ao normalizada (NID) foi definida como sendo: NID(x, y) = max{K(x|y), K(y|x)} max{K(x), K(y)}(2.14) Esta medida ´e tamb´em uma m´etrica. Se dois objetos forem similares de acordo com uma determinada caracter´ıstica descrita por uma distˆancia admiss´ıvel normalizada em particular, ent˜ao tamb´em ser˜ao similares no que toca a NID. ´ E de notar que diferentes pares de objetos poder˜ao ter caracter´ısticas dominantes diferentes. Ainda assim, similaridades dominantes como essas ser˜ao detetadas pela NID. Infelizmente, como esta m´etrica ´e baseada na complexidade de Kolmogorov, n˜ao ´e comput´avel pelo que uma aproxima¸c˜ao ter´a de ser feita. No que toca ao denominador da equa¸c˜ao 2.14, dado compressor C, a transforma¸c˜ao ´e trivial pois ´e simplesmente max{C(x), C(y)}. Por outro lado, o numerador ´e mais dif´ıcil. Pode ser reescrito como max{K(x, y)− CAP´ ITULO 2. COMPLEARN 33 K(x), K(x, y)−K(y)}, com uma certa precis˜ao logar´ıtmica. O termo K(x, y) representa o tamanho do programa mais curto para o par (x, y). Como na pr´atica ´e mais f´acil usar a concatena¸c˜ao xy ou yx, a menos de uma imprecis˜ao logar´ıtmica temos K(x, y) = K(xy) = K(yx). Seguindo a referˆencia de Steven Rooij, podemos aproximar o numerador a min{C(xy), C(yx)}−min{C(x), C(y)}. Como compressores baseados em codifica¸c˜ao por blocos s˜ao sim´etricos quase por defini¸c˜ao, e experiˆencias com compressores baseados em fluxos (PPMZ, gzip) mostram apenas alguns desvios da simetria, a ferramenta CompLearn apenas usa C(xy) em vez de min{C(xy), C(yx)}. O resultado da aproxima¸c˜ao de NID usando um compressor C ´e chamado de distˆancia de compress˜ao normalizada (NCD) (e ser´a formalizada posteriormente). No sentido de preencher a lacuna existente entre a teoria e a pr´atica, a teoria de NCD ir´a ser desenvolvida baseada em axiomas j´a mencionados. Ser´a mostrado que NCD ´e uma m´etrica de similaridade semi-universal relativo a um compressor normal C. 2.4.4 Distˆancia de Compress˜ao Aqui vamos definir distˆancia de compress˜ao baseada num compressor normal e indicar que ´e uma distˆancia admiss´ıvel. Na aplica¸c˜ao desta abordagem, ´e necess´aria uma aproxima¸c˜ao partindo de um compressor C do ”mundo real”muito menos poderoso. Este compressor aproxima a distˆancia de informa¸c˜ao E(x, y), baseada em complexidade de Kolmogorov, pela distˆancia de compress˜ao definida como EC(x, y) = C(xy)−min{C(x), C(y)},(2.15) onde C(xy) ´e o tamanho dos ficheiros concatenados x e y ap´os a compress˜ao. Lema Se C ´e um compressor normal, EC(x, y) + O(1) ´e uma distˆancia admiss´ıvel. Lema Se C ´e um compressor normal, ent˜ao EC(x, y)satisfaz as (des)igualdades m´etricas at´e uma precis˜ao logar´ıtmica. Lema Se C ´e um compressor normal, ent˜ao E+ C= max{C(x), C(y)} 2.4.5 Distˆancia de Compress˜ao Normalizada A aproxima¸c˜ao da distˆancia de informa¸c˜ao normalizada (equa¸c˜ao 2.14) usando um compressor C, que por outras palavra ´e a vers˜ao normalizada da distˆancia admiss´ıvel EC(x, y), ´e chamada de distˆancia de compress˜ao normalizada ou NCD: CAP´ ITULO 2. COMPLEARN 34 NCD(x, y) = C(xy)−min{C(x), C(y)} max{C(x), C(y)}(2.16) O valor de NCD varia entre [0,1 + ] e representa o qu˜ao diferentes dois objetos s˜ao. Quanto mais pr´oximo de 0, mais similares s˜ao. A presen¸ca de deve-se a pequenas imprecis˜oes, mas para a maioria dos algoritmos de compress˜ao usuais, ´e improv´avel encontrar  > 0.1. Teorema Se um compressor ´e normal, ent˜ao NCD ´e uma distˆancia admiss´ıvel normalizada que satisfaz as (des)igualdades m´etricas, isto ´e, uma m´etrica de similaridade. Semi-Universalidade: A motiva¸c˜ao para o desenvolvimento do NCD foi estudada em [8]. Toda a distˆancia admiss´ıvel que expressa similaridade de acordo com uma determinada caracter´ıstica e que possa ser computada, ´e minorada pela NID. Notemos que cada caracter´ıstica dos dados d´a origem a uma similaridade e, reciprocamente, cada similaridade pode ser entendida como uma express˜ao de alguma caracter´ıstica. Infelizmente, a pr´atica de NCD fica aqu´em desta teoria em pelo menos trˆes aspetos: •A universalidade de NID ´e garantida apenas para sequˆencias indefinidamente longas. A partir do momento que se consideram strings de comprimento n, ´e apenas universal no que diz respeito a distˆancias admiss´ıveis normalizadas que sejam ”simples”de computar, onde ”simples”significa que s˜ao comput´aveis por programas de comprimento logar´ıtmico em n. •A complexidade de Kolmogorov n˜ao ´e comput´avel e, de certa forma, n˜ao ´e poss´ıvel calcular o qu˜ao distante ´e a NCD da NID. •Para a aproxima¸c˜ao da NCD s˜ao usados programas de compress˜ao como o gzip, bzip2,PPMD ou paq8l. Enquanto uma melhor compress˜ao de uma string ir´a aproximar melhor o valor da complexidade de Kolmogorov, isto n˜ao se verifica com NCD. Devido `a sua forma de constru¸c˜ao, ´e teoricamente poss´ıvel que enquanto todos os objetos de uma f´ormula sejam melhor comprimidos, esse progresso n˜ao seja uniforme em todos os objetos e assim, o valor de NCD desviase de NID. CAP´ ITULO 2. COMPLEARN 35 2.5 Ferramenta CompLearn Temos como objetivo aplicar o algoritmo NCD do CompLearn a ficheiros de batimento card´ıaco fetal. A cada par de ficheiros ´e calculado o NCD construindo assim uma matriz, chamada de matriz de distˆancias. As entradas dessa matriz ser˜ao as distˆancias entre cada par de tra¸cados, isto ´e, o qu˜ao similares eles s˜ao. Sendo esta uma forma mais compacta de reunir informa¸c˜ao, estamos em condi¸c˜oes de aplicar algoritmos de clustering. Como j´a referido, o CompLearn utiliza o m´etodo dos quartetos exatos que produz uma ´arvore tern´aria em que as folhas representam os ficheiros e os ramos representam similaridades entre os mesmos. Em cada passo, o algoritmo tende a aperfei¸coar a ´arvore modificando as sub-´arvores. A cada ´arvore resultante est´a associado um valor de S(t) que indica o qu˜ao bem representada est´a a matriz pela ´arvore. Infelizmente, sendo o m´etodo da constru¸c˜ao da ´arvore um problema NP-hard, n˜ao ´e escal´avel, impedindo na pr´atica de ser usado para n´umeros de objetos desej´aveis. Cap´ıtulo 3 T´ecnicas de compress˜ao com perdas Com o avan¸co tecnol´ogico, tem existido um crescimento exponencial dos dados digitais obtidos atrav´es de sinais fisiol´ogicos medidos em exames como o eletrocardiograma (ECG), eletroencefalograma (EEG), cardiotocograma (CTG), etc. Isto fez com que um armazenamento e transmiss˜ao eficientes destes dados fossem uma prioridade [9]. Por um lado, temos uma grande quantidade de dados a armazenar o que leva a um grande volume de informa¸c˜ao. Por outro, t´ecnicas de transmiss˜ao, atrav´es de canais de comunica¸c˜ao, permitem a peritos aceder a essa informa¸c˜ao com uma boa rela¸c˜ao custo-benef´ıcio. Por isso, ´e reconhecida a necessidade de boas t´ecnicas de compress˜ao de dados provenientes dos sinais fisiol´ogicos, no sentido de reduzir a quantidade de bits de informa¸c˜ao necess´arios para armazenar e transmitir o sinal [10]. Para al´em disso, notou-se uma necessidade de obter mais informa¸c˜ao do sinal do que aquela existente `a primeira vista (dom´ınio temporal), informa¸c˜ao que muitas vezes se encontra na an´alise de frequˆencia [2]. Cientistas e engenheiros que trabalham com dados obtidos do mundo real sabem que os sinais n˜ao existem sem ru´ıdo. Em condi¸c˜oes ideais, o ru´ıdo pode decrescer para n´ıveis onde poder´a ser desprez´ıvel, enquanto que o sinal aumenta para n´ıveis significativos. Infelizmente, o sinal ´e corrompido por ru´ıdo mais vezes do que o desejado e tem de ser removido para que o sinal seja analisado. A primeira quest˜ao que se coloca ´e: Ser´a que esta remo¸c˜ao do ru´ıdo dever´a ser feita no dom´ınio do sinal original (espa¸co-tempo) ou num outro dom´ınio? Neste ´ultimo caso, v´arias t´ecnicas tˆem sido estudadas, atrav´es das transformadas de Fourier, ou mais recentemente, das transformadas wavelet, entre outras [11]. A compress˜ao de sinal pode ser lossy ou lossless. Usando um algoritmo de compress˜ao lossless, a informa¸c˜ao comprimida pode ser usada para recriar na totalidade a informa¸c˜ao original e nenhum dado ´e perdido no processo. Este tipo de compress˜ao ´e 36 CAP´ ITULO 3. T´ ECNICAS DE COMPRESS ˜ AO COM PERDAS 37 tamb´em conhecido por entropy coding. Este nome prov´em do facto do sinal comprimido ser geralmente mais aleat´orio que o original, pois padr˜oes s˜ao removidos aquando da compress˜ao. Embora a compress˜ao lossless seja ´util na reconstru¸c˜ao exata, geralmente n˜ao atinge o r´acio de compress˜ao esperado. Na compress˜ao lossy, o sinal original n˜ao pode ser reconstruido na sua totalidade. A raz˜ao por tr´as disto ´e que muitos dos detalhes do sinal, n˜ao sendo importantes para an´alise, podem ser descartados. O r´acio de compress˜ao aqui atingido ´e normalmente superior, em troca de alguma informa¸c˜ao que ´e perdida. ´ E neste campo que se incluem os m´etodos mencionados, as transformadas de Fourier e as transformadas wavelet [12]. Nesta disserta¸c˜ao ser´a feita uma introdu¸c˜ao `as Transformadas de Fourier, pela importˆancia que tˆem, e posteriormente introduziremos as wavelets, que s˜ao o nosso objeto de estudo. 3.1 Transformada de Fourier A transformada de Fourier ´e um dos m´etodos tradicionais mais conhecidos no processamento de sinal digital com aplica¸c˜oes em an´alise de frequˆencias, an´alise de sinal, etc. Fourier representou aproxima¸c˜oes de fun¸c˜oes usando combina¸c˜oes de senos e cossenos. O primeiro passo ´e transformar uma fun¸c˜ao com dom´ınio temporal numa fun¸c˜ao de dom´ınio de frequˆencia. O sinal pode ent˜ao ser analisado porque os coeficientes de Fourier da fun¸c˜ao transformada representam a contribui¸c˜ao de cada seno e cosseno em cada frequˆencia existente. Quando os pares ordenados, que representam a fun¸c˜ao de input, est˜ao igualmente espa¸cados (como por exemplo, em intervalos de tempo), dizemos que estamos perante uma Transformada de Fourier Discreta (DFT). Sendo este o caso de todos os nossos dados de input, apenas nos vamos debru¸car sobre a variante discreta destas transformadas. Uma sequˆencia de dados x0, ..., xN−1de tamanho N, ´e transformada numa sequˆencia de n´umeros complexos, de periodicidade N, atrav´es da seguinte equa¸c˜ao: Xk= N−1 X n=0 xne−2πikn N(3.1) CAP´ ITULO 3. T´ ECNICAS DE COMPRESS ˜ AO COM PERDAS 38 Os valores de Xks˜ao os coeficientes usados na fun¸c˜ao de aproxima¸c˜ao. Por outro lado, a transformada inversa (IDFT) executa o processo inverso, isto ´e, transforma uma fun¸c˜ao de dom´ınio de frequˆencia, numa de dom´ınio temporal: Xn=1 N N−1 X n=0 Xke−2πikn N(3.2) A DFT tem propriedades de simetria quase iguais `as existentes nas Transformadas de Fourier Cont´ınuas. Adicionalmente, a equa¸c˜ao (3.2) ´e de c´alculo f´acil pois ´e muito parecida com a equa¸c˜ao (3.1). Podemos ter dois tipos de sinal, estacion´ario e n˜ao-estacion´ario. No primeiro caso, todas as frequˆencias existentes n˜ao se alteram com o tempo (Figura 3.1). No segundo, essas frequˆencias alteram-se (Figura 3.2). Como exemplo deste ´ultimo, temos o sinal Chirp, demonstrado na Figura 3.3. Aqui, reparamos que embora as fun¸c˜oes no dom´ınio temporal sejam diferentes, quando transformadas para o espetro de frequˆencia tornam-se iguais. Levanta-se uma quest˜ao: Em que tempo ocorre cada um dos componentes de frequˆencia? As transformadas de Fourier n˜ao conseguem responder, apenas nos informam quais componentes de frequˆencia existem no sinal. A informa¸c˜ao de tempo e frequˆencia n˜ao podem ser vistas ao mesmo tempo (Princ´ıpio da Incerteza de Heisenberg). Figura 3.1: Exemplo de sinal estacion´ario (2Hz + 10Hz + 20Hz). Muitos dos sinais existentes s˜ao n˜ao-estacion´arios, mas temos a necessidade de saber quando ´e que determinada frequˆencia ocorre. Uma solu¸c˜ao encontrada (Dennis Gabor, 1946) foi a Transformada de Fourier de curto termo (STFT). Esta t´ecnica consiste CAP´ ITULO 3. T´ ECNICAS DE COMPRESS ˜ AO COM PERDAS 39 Figura 3.2: Exemplo de sinal n˜ao estacion´ario (2Hz (0.0 a 0.4) + 10Hz (0.4 a 0.7) + 20Hz (0.7 a 1)). Figura 3.3: Sinais Chirp. numa an´alise espectral dependente do tempo: a fun¸c˜ao ´e particionada em intervalos, de forma a que o espectro possa ser considerado constante (estacion´ario) no interior de cada um deles. Uma varia¸c˜ao da transformada de Fourier ´e ent˜ao aplicada a cada intervalo. Infelizmente esta t´ecnica tem alguns problemas. O intervalo definido mant´em-se inalterado durante todo o processo e isso provoca um dilema. Se for escolhido um intervalo pequeno (boa resolu¸c˜ao temporal) teremos uma fraca resolu¸c˜ao de frequˆencia. Por outro lado, se a janela for demasiado extensa, a resolu¸c˜ao temporal ser´a fraca (Figura 3.4). CAP´ ITULO 3. T´ ECNICAS DE COMPRESS ˜ AO COM PERDAS 40 Figura 3.4: Rela¸c˜ao intervalo tempo-frequˆencia. Por norma, ´e desejada uma abordagem mais flex´ıvel onde seja poss´ıvel variar a dimens˜ao da janela com o objetivo de determinar mais precisamente o tempo ou a frequˆencia [13]. No caso da fun¸c˜ao ser n˜ao-peri´odica, o somat´orio das fun¸c˜oes seno e cosseno n˜ao representa o sinal com grande precis˜ao. Podemos, no entanto, estender artificialmente o sinal de modo a que se torne peri´odico mas isso iria requerer uma continuidade adicional nas extremidades. A transformada de Fourier por janelas (WFT) ´e uma solu¸c˜ao ao problema da representa¸c˜ao de fun¸c˜oes n˜ao-peri´odicas. Esta alternativa pode ser usada para obter mais informa¸c˜ao do sinal no que toca tanto ao tempo como `a frequˆencia. Neste caso, o sinal ´e cortado em sec¸c˜oes e em cada uma delas ´e analisada a frequˆencia. Quando existem transi¸c˜oes brutas no sinal, os dados s˜ao manipulados de forma a que essas sec¸c˜oes convirjam para zero [14]. Este efeito ´e conseguido atrav´es de uma fun¸c˜ao peso que tem menos ˆenfase nas extremidades do que no centro da janela. Para aproximar uma fun¸c˜ao por amostras, e aproximar o integral de Fourier pela DFT, requer-se a aplica¸c˜ao de uma matriz cuja ordem ´e o n´umero de pontos na amostra, n. Como multiplicar uma matriz n×npor um vetor tem um custo de n2opera¸c˜oes, o problema torna-se muito dispendioso `a medida que a amostra aumenta. Mas, se as amostras estiverem uniformemente espa¸cadas, ent˜ao a matriz de Fourier pode ser fatorizada num produto de apenas algumas matrizes e o resultado pode ser aplicado a um vetor num total de opera¸c˜oes de ordem nlog n. Esta ´e a chamada transformada r´apida de Fourier (FFT) [9, 15, 16]. CAP´ ITULO 3. T´ ECNICAS DE COMPRESS ˜ AO COM PERDAS 41 3.2 Transformada Wavelet Existem v´arias boas raz˜oes para usar wavelets na aproxima¸c˜ao de fun¸c˜oes. Conseguem detetar bem dados com descontinuidades [2]. S˜ao simples, pr´aticas, r´apidas e facilmente adapt´aveis a espa¸cos e frequˆencias n˜ao-homog´eneos. S˜ao extens´ıveis a grandes dimens˜oes e aplic´aveis a v´arios tipo de problemas tais como estima¸c˜ao de densidade, an´alise de imagem, processamento de sinal, etc [17]. Esta t´ecnica tem, tamb´em, sido muito eficaz na remo¸c˜ao de ru´ıdo em sinal, estimando a s´erie real de uma s´erie corrompida por ru´ıdo eletr´onico ou de eventos externos como: vento, vibra¸c˜oes, varia¸c˜oes de temperatura, varia¸c˜oes de humidade, etc [18]. Isto ´e ´util para fins de previs˜ao usando diretamente as s´eries temporais geradas atrav´es da decomposi¸c˜ao da wavelet [19]. Por todas estas raz˜oes, as wavelets tˆem sido usadas nas mais diversas ´areas como por exemplo: astronomia, ac´ustica, engenharia nuclear, processamento de imagem e sinal, ciˆencia de computadores, neurofisiologia, m´usica, ´otica, fractais, previs˜ao de terramotos, radar, vis˜ao humana e aplica¸c˜oes matem´aticas puras. Um exemplo de sucesso no uso desta t´ecnica foi quando o FBI se deparou com a problem´atica de ter uma base de dados de impress˜oes digitais com cerca de 30 milh˜oes de entradas, e a crescer. O custo de manuten¸c˜ao come¸cava a ser insuport´avel. Com a aplica¸c˜ao das wavelets, conseguiram atingir um r´acio de compress˜ao de 15:1, um resultado bem melhor que a tradicional compress˜ao JPEG [2]. 3.2.1 Perspetiva Hist´orica O desenvolvimento da an´alise de wavelets conheceu origens diferentes ao longo da hist´oria. Muito do trabalho desenvolvido foi feito antes da d´ecada de 30 do s´eculo passado. Tudo come¸cou com o trabalho desenvolvido por Joseph Fourier (1807) com as suas teorias de an´alise de frequˆencia, onde afirmou que qualquer fun¸c˜ao peri´odica de per´ıodo 2π´e a soma da sua s´erie de Fourier: a0+∞ X k=1 (akcos kx +bksin kx) (3.3) Os coeficientes a0,akebks˜ao calculados da seguinte forma: CAP´ ITULO 3. T´ ECNICAS DE COMPRESS ˜ AO COM PERDAS 48 Uma das diferen¸cas mais relevantes entre as duas transformadas ´e que as fun¸c˜oes seno e cosseno s˜ao definidas em todo o dom´ınio, enquanto que as wavelet s˜ao de suporte compacto, isto ´e, definidas num intervalo (localizadas no tempo). Esta propriedade, juntamente com a localiza¸c˜ao da frequˆencia das wavelets, faz com que fun¸c˜oes e operadores wavelet, quando transformados para o dom´ınio wavelet, facilitem a dete¸c˜ao de caracter´ısticas importantes atrav´es de coeficientes de valor absoluto alto (sparseness). Isto resulta num n´umero variado de aplica¸c˜oes ´uteis como compress˜ao de dados, dete¸c˜ao de propriedades em imagens, e remo¸c˜ao de ru´ıdo em s´eries temporais. Na an´alise de Fourier, temos perda da informa¸c˜ao no tempo quando ´e feita a transforma¸c˜ao para o dom´ınio da frequˆencia. A falta de localiza¸c˜ao do sinal no tempo permite apenas uma an´alise do comportamento global dos sinais. Para sinais estacion´arios, esta caracter´ıstica n˜ao ´e muito importante. No entanto, quando o sinal cont´em caracter´ısticas n˜ao estacion´arias ou transit´orias, tais como tendˆencias e mudan¸cas abruptas, a transformada de Fourier apresenta uma s´eria desvantagem. Uma forma de olhar para a diferen¸ca da resolu¸c˜ao tempo-frequˆencia entre as duas t´ecnicas ´e atrav´es da cobertura das fun¸c˜oes base no plano tempo-frequˆencia [25]. Na transformada de Fourier, um quadrado com uma certa largura truncando as fun¸c˜oes seno e cosseno forma uma janela que ´e igual em tamanho em todas frequˆencias. Isto faz com que a resolu¸c˜ao da an´alise seja a mesma em todos os locais do plano tempofrequˆencia. Uma vantagem da transformada wavelet ´e que essa janela n˜ao ´e constante. Para isolar descontinuidades, seria ´util ter fun¸c˜oes base de tamanho pequeno, enquanto para obter an´alises de frequˆencia detalhada, fun¸c˜oes base longas s˜ao desej´aveis. Uma maneira de obter isto ´e ter fun¸c˜oes base de alta-frequˆencia pequenas e outras de baixa-frequˆencia que sejam longas [16]. Outra vantagem na an´alise wavelet ´e que os coeficientes tˆem um parˆametro local. Isto ´e necess´ario para distinguir coeficientes diferentes no mesmo n´ıvel, o que contrasta com a transformada de Fourier onde a informa¸c˜ao acerca das frequˆencias mais relevantes na s´erie ´e obtida, mas ´e dif´ıcil distinguir onde est˜ao presentes. De notar, como dito anteriormente, que a WFT tamb´em consegue detetar propriedades locais, pois a transformada de Fourier discreta ´e aplicada a pequenas partes da s´erie. Akin (2002) comparou os dois m´etodos aplicando-os na an´alise de sinais de eletrocardiograma cerebral e sugere que o m´etodo wavelet ofereceu melhores resultados [18]. CAP´ ITULO 3. T´ ECNICAS DE COMPRESS ˜ AO COM PERDAS 49 Figura 3.6: Compara¸c˜ao da resolu¸c˜ao tempo-frequˆencia entre as diferentes transformadas. Na transformada de Fourier de curto termo nota-se um tamanho da janela independente da resolu¸c˜ao tempo-frequˆencia, ao contr´ario da transformada wavelet onde o tamanho dessa janela se altera de acordo com a resolu¸c˜ao [2]. 3.2.4 Transformada Wavelet Discreta A transformada wavelet cont´ınua (CWT) ´e ´util, por exemplo, na constru¸c˜ao de um gr´afico de trˆes eixos (tempo, escala/n´ıvel e uma outra, normalmente representado por cores ou diferentes n´ıveis de brilho) chamado de escalograma, pois a janela de an´alise ´e dimensionada e posicionada em qualquer posi¸c˜ao. Esta flexibilidade permite a cria¸c˜ao de uma imagem mais suave e agrad´avel na visualiza¸c˜ao tanto em tempo como em escala (an´alogo `a frequˆencia). A CWT ´e uma transformada redundante porque a janela de an´alise pode sobrepor-se. De facto, CWT ´e considerada infinitamente redundante. Por outro lado, DWT ´e uma transformada n˜ao redundante. Foi desenvolvida para que houvesse uma correspondˆencia de um para um entre a informa¸c˜ao no dom´ınio do sinal e no dom´ınio da transformada. Esta correspondˆencia ´e ´util na reconstru¸c˜ao do sinal, mas as janelas de an´alise s˜ao fixas tanto no tempo como em escala, fazendo com que o escalograma n˜ao seja t˜ao satisfat´orio para an´alise visual do sinal [2]. CAP´ ITULO 3. T´ ECNICAS DE COMPRESS ˜ AO COM PERDAS 50 Figura 3.7: Escalograma: Compara¸c˜ao entre CWT e DWT. Por outro lado, DWT tem enorm´ıssimas vantagens, em compara¸c˜ao com CWT: ´e capaz de reduzir significativamente o tempo de computa¸c˜ao; ´e de f´acil implementa¸c˜ao e fornece informa¸c˜ao suficiente tanto para an´alise como para reconstru¸c˜ao do sinal; analisa o sinal decompondo-o em informa¸c˜ao aproximada e detalhada [2]. Temos ent˜ao um sinal que ´e transformado, atrav´es de DWT (e da escolha de uma fun¸c˜ao base wavelet), de um dom´ınio temporal para um dom´ınio de tempo-frequˆencia. ´ E utilizada uma decomposi¸c˜ao em m´ultiplos n´ıveis onde o sinal ´e inicialmente decomposto em aproxima¸c˜ao e detalhe conforme a ´arvore representada a seguir. CAP´ ITULO 3. T´ ECNICAS DE COMPRESS ˜ AO COM PERDAS 51 Figura 3.8: ´ Arvore de decomposi¸c˜ao wavelet. Em D1estar˜ao representadas as frequˆencias mais altas. Para i > 1, em Diteremos as representa¸c˜oes das frequˆencias cada vez mais pequenas [2]. Os valores do output s˜ao chamados de coeficientes. Os coeficientes de baixo valor absoluto s˜ao considerados ru´ıdo, e os de alto valor absoluto tˆem associada muita informa¸c˜ao comparativamente `a quantidade de ru´ıdo. Num segundo passo, s˜ao anulados todos os coeficientes abaixo de um certo valor pr´e-definido, chamado de threshold, enquanto que os restantes coeficientes permanecer˜ao inalterados (hard threshold) ou sofrer˜ao um soft threshold. O ´ultimo passo ´e a aplica¸c˜ao da transformada inversa (IDWT), que vai reconstruir o sinal [26]. A express˜ao (3.7) tem uma variante discreta. Por uma quest˜ao de facilidade na explica¸c˜ao do m´etodo, vamos reescrever a equa¸c˜ao da m˜ae-wavelet, fazendo uma mudan¸ca de vari´avel da seguinte forma: 1 √j= 2j∗ 2(3.20) onde j* ´e a nova vari´avel de escala/resolu¸c˜ao. Continuemos, por´em, a chamar-lhe j, e a equa¸c˜ao da m˜ae wavelet fica ψj,k(x)=2j 2ψ(2jx−k) (3.21) Um ponto de come¸co na tentativa de pereber as wavelets ´e atrav´es das suas fun¸c˜oes base. Tal como Fourier fazia uso das fun¸c˜oes seno e cosseno, uma transformada wavelet tem uma fun¸c˜ao m˜ae, ψ(x), e uma fun¸c˜ao pai, φ(x) (mencionadas na equa¸c˜ao (3.7)). Estas fun¸c˜oes est˜ao relacionadas atrav´es das seguintes equa¸c˜oes: ψ(x) = X k∈Z gk√2φ(2x−k).(3.22) CAP´ ITULO 3. T´ ECNICAS DE COMPRESS ˜ AO COM PERDAS 52 φ(x) = X k∈Z hk√2φ(2x−k).(3.23) O conjunto de coeficientes {gk}cont´em os filtros passa-altas (tendem a manter as altas frequˆencias e a eliminar frequˆencias baixas) associados a uma fun¸c˜ao wavelet definida. Usando ambas as fun¸c˜oes, ´e poss´ıvel representar uma s´erie discreta representada em (3.7), reescrita da seguinte forma: f(x) = c0,0φ0,0(x) + X kX j>0 dj,kψj,k(x) (3.24) Tal como j´a foi referido, os ´ındices k e j est˜ao associados `a transla¸c˜ao e escala, respetivamente. Referem-se ao posicionamento e n´ıvel de detalhe dos coeficientes ao longo do sinal. O conceito de n´ıvel de detalhe ´e muito importante nas wavelets. Para a DWT, o comprimento da s´erie a analisar tem de ser uma potˆencia de dois. Numa s´erie de comprimento 2Jexistem Jdiferentes n´ıveis de detalhe, variando entre 0 e J−1, onde o n´ıvel J cont´em a s´erie original e a escala J−1 os melhores coeficientes de escala. Quando j= 0 temos a fun¸c˜ao base o mais esticada poss´ıvel, cobrindo a s´erie na sua totalidade. Consequentemente, nesse n´ıvel teremos apenas um coeficiente. ´ E claro que, representar toda a s´erie com um s´o coeficiente ´e uma aproxima¸c˜ao muito fraca. Se, em vez disso, j= 1, a fun¸c˜ao wavelet vai cobrir apenas metade da s´erie e isto vai resultar em dois coeficientes. Naturalmente, os detalhes da s´erie estar˜ao mais bem representados do que quando j= 0. Este processo continua, duplicando o n´umero de coeficientes `a medida que o valor de j aumenta, ate que j=J. O pr´oximo passo ´e perceber como ´e que estes coeficientes s˜ao calculados. Este processo ´e conhecido como algoritmo de pirˆamide. Primeiro s˜ao calculados os coeficientes referentes ao pai-wavelet e, posteriormente, os referentes `a m˜ae-wavelet. Os primeiros, {cj,k}, s˜ao conhecidos como os coeficientes smooth e s˜ao usados para representar o n´ıvel da s´erie. S˜ao gerados atrav´es de um processo similiar ao da weighted moving average, da seguinte forma: cj−1,k =X n hn−2kcj,n.(3.25) Os coeficientes wavelet {hk}, que s˜ao an´alogos aos pesos da moving average, s˜ao filtros passa-baixas (tendem a eliminar altas frequˆencias e a manter frequˆencias baixas). CAP´ ITULO 3. T´ ECNICAS DE COMPRESS ˜ AO COM PERDAS 53 Estes s˜ao espec´ıficos a cada base wavelet usada na transformada. O n´umero de coeficientes tamb´em varia consoante a base usada. No entanto, todas tˆem de obedecer `a propriedade Pkh2 k= 1. Como se vˆe a partir da equa¸c˜ao (3.25), os coeficientes de uma certa escala s˜ao calculados a partir dos coeficientes de escala superior. Os coeficientes associados `a m˜ae-wavelet s˜ao chamados coeficientes de detalhe. S˜ao usados para representar a diferen¸ca entre a s´erie e os coeficiente cj,k. S˜ao calculados da seguinte forma: dj−1,k =X n gn−2kcj,n.(3.26) Embora pare¸cam muito similares aos coeficientes associados ao pai-wavelet, existem algumas diferen¸cas importantes. Primeiro, os coeficientes hk, que s˜ao filtros passabaixas, foram substitu´ıdos pelos filtros passa-altas gj,k. Estes s˜aos os mesmo coeficientes usados na equa¸c˜ao (3.22). Estes dois conjuntos de coeficientes est˜ao relacionados da seguinte forma: gk= (−1)kh1−k.(3.27) A introdu¸c˜ao de sinais negativos no filtro d´a aos coeficientes de detalhe capacidade de mostrar mais detalhe em como o processo est´a a mudar e em como a s´erie difere da representa¸c˜ao dos coeficientes smooth. Outra caracter´ıstica a real¸car ´e que tanto na equa¸c˜ao (3.25) como na equa¸c˜ao (3.26), apenas os coeficientes smooth s˜ao usados. Isto significa que apenas estes s˜ao necess´arios na deriva¸c˜ao dos coeficientes smooth e detalhe para o pr´oximo n´ıvel de decomposi¸c˜ao. Este procedimento est´a sumariado na figura seguinte. ` A medida que a transformada ´e executada, os coeficientes de detalhe s˜ao guardados, ao contr´ario dos coeficientes smooth (exceto no n´ıvel mais baixo). Isto acontece porque a s´erie pode ser representada usando apenas estes coeficientes, como representado na equa¸c˜ao (3.24). Figura 3.9: Estrutura de computa¸c˜ao dos coeficientes wavelet CAP´ ITULO 3. T´ ECNICAS DE COMPRESS ˜ AO COM PERDAS 54 A computa¸c˜ao n˜ao tem obrigatoriamente de ser executada para todo o n´ıvel j. No entanto, o coeficiente smooth do ´ultimo n´ıvel calculado ter´a de ser guardado. ` A primeira vista, parece perdermos informa¸c˜ao importante por apenas guardarmos os coeficientes de detalhe (e um smooth), mas tal n˜ao ´e verdade. Os coeficientes smooth apenas descrevem o n´ıvel da s´erie. Durante a an´alise, esta caracter´ıstica n˜ao ´e muito relevante comparada com caracter´ısticas como quebras, saltos, etc. Estes detalhes est˜ao presentes nos coeficientes de detalhe [18]. Este algoritmo eficiente requer apenas O(n) opera¸c˜oes (ver Mallat [27]). Uma abordagem alternativa na constru¸c˜ao dos coeficientes ´e atraves de matrizes. Como o algoritmo piramidal consiste basicamente em s´eries de multiplica¸c˜oes, adi¸c˜oes e subtra¸c˜oes, n˜ao ser´a muito dif´ıcil de imaginar o mesmo ser conseguido atrav´es da multiplica¸c˜ao de matrizes. Dado um conjunto de dados f1, ..., fn, com n= 2J, que formam um vetor coluna f, existe uma matriz ortogonal W (n×n) tal que a transformada discreta wavelet θjk ´e dada por θ=Wf, (3.28) onde θ´e o n-vetor dos coeficientes da wavelet discreta θjk, j = 0, ..., J −1 e k= 1, ..., 2j. A transformada inversa pode ser representada da seguinte forma: f=WTθ(3.29) Usando a f´ormula da transformada da inversa, ´e poss´ıvel notar que as linhas de W correspondem `a discretiza¸c˜ao da m˜ae-wavelet em v´arias escalas e transla¸c˜oes diferentes. Donoho e Johnstone [28] notaram a seguinte aproxima¸c˜ao: √nWj,k(i)≈2j 2ψ(2jt−k), t =i n,(3.30) onde Wj,k(i) ´e o i-´esimo elemento da linha (j,k) de W. Pode ser visto que o coeficiente θjk quantifica a contribui¸c˜ao das fun¸c˜oes de base Wj,k que est˜ao localizadas num intervalo de tamanho 2−je frequˆencia 2j. Dito de outro modo, θjk indica a quantidade de sinal `a volta de 2−je perto da frequˆencia 2j[17]. O vetor θcont´em todos os coeficientes de detalhe de todos os n´ıveis e o coeficiente de aproxima¸c˜ao do n´ıvel mais baixo, tendo ent˜ao comprimento n e a informa¸c˜ao necess´aria para reconstruir a s´erie. Como este m´etodo envolve a multiplica¸c˜ao de uma matriz, vai requerer O(n2) opera¸c˜oes, sendo assim um processo mais lento do que aquele visto com o algoritmo piramidal que devolve exatamente a mesma informa¸c˜ao. A raz˜ao para isto acontecer ´e que muitos dos coeficientes da matriz tˆem de facto valor nulo, o que implica que as suas opera¸c˜oes n˜ao sejam necess´arias [18]. CAP´ ITULO 3. T´ ECNICAS DE COMPRESS ˜ AO COM PERDAS 55 3.2.5 Fun¸c˜oes Base Um fator importante a ter em conta quando se fala em an´alise por wavelets ´e o da escolha da fun¸c˜ao base. N˜ao existindo uma escolha perfeita para todos os casos, as v´arias ´areas de aplica¸c˜ao tˆem feito escolhas diferentes [29]. Para uma fun¸c˜ao poder ser usada na an´alise wavelet, tem de satisfazer certas propriedades. Iremos descrever algumas delas (ver VidaKovic (1999) para mais detalhes). A an´alise wavelet tem de permitir uma decomposi¸c˜ao em v´arias escalas. Isto s´o ´e poss´ıvel se a fun¸c˜ao pai-wavelet puder ser constru´ıda no n´ıvel 0 atrav´es duma combina¸c˜ao linear de fun¸c˜oes de n´ıvel 1, isto ´e, φ0,0=X k hkφ1,k(x),(3.31) onde {hk}s˜ao os filtros j´a mencionados atr´as. ´ E tamb´em necess´ario que a base seja normalizada e ortogonal. No primeiro temos de garantir que X k hk=√2,(3.32) enquanto para a ortogonalidade temos < φj,k(x), φi,l(x)>=Zφj,k(x)φi,l(x)dx =δijδlk.(3.33) Uma consequˆencia disto ´e que os coeficientes de filtro tamb´em tˆem de ser ortogonais, satisfazendo X k hkhk−2l=δl,(3.34) e quando temos l= 0, fica X k h2 k= 1.(3.35) Se optarmos pela perspetiva matricial, o que esta propriedade garante ´e que WTW=WW T=I(3.36) A base wavelet mais simples que existe ´e a Haar (Haar, 1910). Esta wavelet foi a primeira a ser usada, e tem como fun¸c˜ao wavelet e fun¸c˜ao de escala as seguintes defini¸c˜oes, respetivamente: CAP´ ITULO 3. T´ ECNICAS DE COMPRESS ˜ AO COM PERDAS 56 ψ(x) =        −1x∈[0,1 2[ 1x∈[1 2,1[ 0 caso contr´ario φ(x) = (1x∈[0,1] 0 caso contr´ario A simplicidade deste wavelet significa que ´e ideal na demonstra¸c˜ao de princ´ıpios b´asicos no que toca ao processo de transformada. A equa¸c˜ao de escala (3.23), ´e muito simples para esta wavelet e os filtros associados a esta base s˜ao constru´ıdos da seguinte forma φ(x) = φ(2x) + φ(2x−1) =1 √2√2φ(x) + 1 √2√2φ(2x−1),(3.37) onde se deduzem h=1 √21 1, g =1 √21 −1(3.38) Quando estes filtros s˜ao aplicados nas equa¸c˜oes (3.25) e (3.26), os c´alculos s˜ao simplesmente uma soma ou subtra¸c˜ao dividida pela raiz de dois. Como demonstra¸c˜ao, vamos aplicar o DWT a uma s´erie de comprimento 8 (isto significa que temos J= 3 n´ıveis de coeficientes. A primeira linha representa a s´erie original e as linhas seguintes s˜ao os respetivos coeficientes aplicando a wavelet Haar. Enquanto os coeficientes smooth dum determinado n´ıvel s˜ao simplesmente a soma dos pares correspondentes do n´ıvel superior, os de detalhe s˜ao a diferen¸ca entre eles. Notamos que cada linha foi multiplicada por √2 para facilitar a visualiza¸c˜ao dos c´alculos. CAP´ ITULO 3. T´ ECNICAS DE COMPRESS ˜ AO COM PERDAS 57 c3,k =32513628 √2c2,k = 5 6 9 10 √2d2,k = 1 4 −3−6 2c1,k = 11 19 2d1,k =−1−1 2√2c0,k = 30 2√2d0,k =−8 A aproxima¸c˜ao `a s´erie original, usando a equa¸c˜ao (3.24), fica f=15 √2φ0,0−4 √2ψ0,0−1 2ψ1,0−1 2ψ1,1+ (3.39) 1 √2ψ2,0+4 √2ψ2,1−3 √2ψ2,2−6 √2ψ2,3 Embora esta wavelet proporcione exemplos f´aceis de entender, e ´e a ´unica wavelet capaz de criar fun¸c˜oes perfeitamente sim´etricas ou assim´etricas que tenham um suporte compacto, tem a limita¸c˜ao de ser pouco regular [18, 29] Apenas nos anos oitenta, novas fam´ılias de wavelets foram desenvolvidas, aumentando assim o n´umero de fun¸c˜oes base dispon´ıvel. O grupo de wavelets desenvolvido por Daubechies (1998) ´e possivelmente o mais usado hoje em dia. Cada wavelet tem um certo n´umero de momentos de fuga, que pode variar entre 1 e 10, e para cada est˜ao associados dois coeficientes de filtro. Podemos representar cada wavelet como Dj (j ´e o n´umero de coeficientes) ou dbi (i ´e o n´umero de momentos). O momento de fuga refere-se `a capacidade da wavelet de representar comportamento polinomial ou informa¸c˜ao no sinal. Por exemplo, db1 (que ´e a wavelet Haar), facilmente representa fun¸c˜oes constantes; db2 facilmente representa constantes e fun¸c˜oes lineares, etc. Formalmente, ´e dito que tem m momentos de fuga se satisfizer Zxlψ(x)dx = 0,para l= 0, ..., m −1.(3.40) Se uma wavelet com m momentos de fuga for usada para analisar uma fun¸c˜ao polinomial de ordem m, ent˜ao todos os coeficientes de detalhe ser˜ao zero. Isto ´e ´util se a CAP´ ITULO 4. AN ´ ALISE DE RESULTADOS 64 sores, assim como analisar certas caracter´ısticas do feto tais como o g´enero, peso, se o nascimento foi prematuro e se o estado de sa´ude `a nascen¸ca ´e considerado normal ou n˜ao. Os resultados foram divididos por semana e os gr´aficos contˆem as m´edias da taxa de compress˜ao para cada uma dessas semanas. Para este conjunto de dados, al´em do pr´e-processamento j´a referido, e em virtude de nem todos os tra¸cados terem o mesmo comprimento, decidimos uniformizar de forma a que todos tivessem apenas 10 minutos de tra¸cado, o que equivale a 2400 entradas por ficheiro. Numa primeira fase, foram selecionados os tra¸cados referentes aos fetos considerados normais ap´os o parto, atrav´es do ´ındice Apgar. Tal como previsto, a compress˜ao por parte do compressor paq8l ´e maior comparativamente ao gzip e bzip2, obtendo assim taxa de compress˜ao menor (Figura 4.1). Figura 4.1: M´edias da taxa de compress˜ao, por semana, usando os trˆes compressores. Por outro lado, como seria de esperar, o tempo e mem´oria necess´arios para a compress˜ao s˜ao muito mais elevados no caso do compressor paq8l. De seguida foi dividido o conjunto de dados em dois grupos: Os tra¸cados de beb´es considerados saud´aveis `a nascen¸ca, e aqueles considerados patol´ogicos (com base no pH do cord˜ao umbilical `a nascen¸ca). Pela an´alise da Figura 4.2 notamos n˜ao s´o que os compressores comportam-se de forma quase idˆentica, mas tamb´em uma maior capacidade de compress˜ao, salvo exce¸c˜oes, nos tra¸cados de fetos patol´ogicos, embora a dinˆamica ao longo das semanas entre os dois grupos seja similar. CAP´ ITULO 4. AN ´ ALISE DE RESULTADOS 65 Figura 4.2: Gr´afico das m´edias da taxa de compress˜ao semanais dos tra¸cados dos fetos considerados normais e patol´ogicos usando os trˆes compressores. CAP´ ITULO 4. AN ´ ALISE DE RESULTADOS 66 Com o mesmo conjunto de dados, dividindo o grupo por g´enero, not´amos que a menos da diferen¸ca da taxa de compress˜ao j´a mencionada, os trˆes compressores comportamse de forma similar para cada um dos g´eneros. De salientar uma diferen¸ca substancial entre os g´eneros na semana 27 (Figura 4.3). Figura 4.3: Gr´afico das m´edias da taxa de compress˜ao semanais, por g´enero, dos tra¸cados dos fetos considerados normais usando os trˆes compressores. O mesmo foi feito para os fetos considerados patol´ogicos e embora o comportamento dos compressores seja similar, not´amos uma diferen¸ca no comportamento a partir da semana 36 entre os g´eneros (Figura 4.4). CAP´ ITULO 4. AN ´ ALISE DE RESULTADOS 67 Figura 4.4: Gr´afico das m´edias da taxa de compress˜ao semanais, por g´enero, dos tra¸cados dos fetos considerados patol´ogicos usando os trˆes compressores. No que toca `a prematuridade do parto, dividimos o dataset em tra¸cados cujo parto foi prematuro ou n˜ao (definimos como prematuro o beb´e que tivesse nascido at´e `as 36 semanas). Verific´amos que em todos os compressores, a taxa de compress˜ao era maior nos prematuros, notando-se maiores oscila¸c˜oes nos pr´e-termo (Figura 4.5). CAP´ ITULO 4. AN ´ ALISE DE RESULTADOS 68 Figura 4.5: Gr´afico das m´edias da taxa de compress˜ao semanais, dos tra¸cados dos fetos considerados prematuros e n˜ao prematuros usando os trˆes compressores. A ´ultima caracter´ıstica analisada foi o peso `a nascen¸ca. Esta vari´avel foi analisada em quatro diferentes variantes: os beb´es cujo peso `a nascen¸ca ´e considerado normal, aqueles com peso abaixo de um certo percentil, isto ´e, percentil 3 (p3) e percentil 10 (p10) e os que se encontram entre os dois. Mais uma vez, a menos da diferen¸ca do poder de compress˜ao, os 3 compressores comportam-se de forma similar. Not´amos uma certa estabilidade na evolu¸c˜ao dos CAP´ ITULO 4. AN ´ ALISE DE RESULTADOS 69 tra¸cados considerados normais, ao contr´ario dos restantes. De salientar as grandes diferen¸cas registadas na semana 30 onde enquanto a taxa dos tra¸cados normais e p3 s˜ao similares, os tra¸cados p10 e ”entre p3 e p10”s˜ao muito mais baixos (Figura 4.6). CAP´ ITULO 4. AN ´ ALISE DE RESULTADOS 70 Figura 4.6: Rela¸c˜ao entre o peso do beb´e `a nascen¸ca e a taxa de compress˜ao dos tra¸cados ao longo da gravidez usando os 3 compressores, onde p3 indica o percentil 3 e p10 o percentil 10. CAP´ ITULO 4. AN ´ ALISE DE RESULTADOS 71 4.2 An´alise Wavelets Em virtude de n˜ao termos notado uma clara vantagem no uso de um compressor em detrimento de outro na sec¸c˜ao anterior, a compress˜ao realizada nos testes desta sec¸c˜ao foi feita pelo compressor paq8l. Os primeiros testes realizados com a t´ecnica das wavelets consistiu numa base de dados com 67 tra¸cados do per´ıodo anteparto, dos quais 48 normais, 10 patol´ogicos e 9 suspeitos, de acordo com uma an´alise `a posteriori por parte dos especialistas que avaliaram o bem estar do beb´e `a nascen¸ca atrav´es do pH do cord˜ao umbilical. Para cada grupo foram calculados os r´acios de compress˜ao sem wavelets e com a aplica¸c˜ao das mesmas. Para isso us´amos as wavelets Haar, Daubechies e Coiflet, aplicando sempre o threshold universal. Pela an´alise da Figura 4.7 not´amos uma similaridade no comportamento das wavelets Daubechies e Coiflet, ao contr´ario da wavelet Haar. Neste ´ultimo caso, encontr´amos acentua¸c˜oes nas diferen¸cas entre os r´acios de compress˜ao essencialmente para os tra¸cados considerados normais, como se pode ver na Figura 4.8. CAP´ ITULO 4. AN ´ ALISE DE RESULTADOS 72 Figura 4.7: Gr´aficos de compara¸c˜ao entre o r´acio de compress˜ao sem utiliza¸c˜ao de wavelets e com a utiliza¸c˜ao das wavelets Daubechies, Coiflet e Haar para tra¸cados normais (N), suspeitos (MSA) e patol´ogicos (NA), onde os tra¸cados azuis representam o r´acio de compress˜ao sem wavelet e os vermelhos com o wavelet respetivo CAP´ ITULO 4. AN ´ ALISE DE RESULTADOS 73 Figura 4.8: Gr´aficos de caixa com a compara¸c˜ao entre o r´acio de compress˜ao das wavelets Daubechies, Coiflet e Haar para tra¸cados normais (N), suspeitos (MSA) e patol´ogicos (NA) No sentido de avaliar melhor o desempenho da wavelet Haar, fizemos o mesmo teste mas para um conjunto de dados maior consistindo em 5877 tra¸cados de categoria normal, 120 de categoria suspeito e 34 da categoria patol´ogico. O que observ´amos (Figura 4.9) foi um comportamento muito semelhante n˜ao s´o entre as diferentes categorias como tamb´em na utiliza¸c˜ao ou n˜ao das wavelets. Foi tamb´em testada a substitui¸c˜ao do threshold universal por um threshold constante de valor absoluto CAP´ ITULO 4. AN ´ ALISE DE RESULTADOS 80 Figura 4.15: Gr´afico de caixa de tra¸cados obtidos no per´ıodo intraparto. R´acios de compress˜ao sem (CR) e com o uso de wavelets (Haar e Daubechies usando threshold universal) 4.3 An´alise CompLearn O objetivo desta sec¸c˜ao ´e avaliar o comportamento do CompLearn na an´alise dos tra¸cados de batimento card´ıaco fetal. De um dataset com um total de 14812 entradas, foram selecionados os tra¸cados referentes `a semana 37 da gravidez no sentido de garantir que todos os fetos estavam nas mesmas condi¸c˜oes, isto ´e, 3522 tra¸cados. Em virtude da ´arvore resultante do algoritmo do CompLearn requerer tempo exponencial em rela¸c˜ao ao n´umero de entradas, tivemos de restringir este n´umero nos testes que CAP´ ITULO 4. AN ´ ALISE DE RESULTADOS 81 se seguem. Em primeiro lugar test´amos se o algoritmo seria capaz de distinguir os tra¸cados cujo pH do cord˜ao umbilical `a nascen¸ca eram muito baixos dos muito altos. Posteriormente foi feito o mesmo mas para a variabilidade curta. 4.3.1 CompLearn vs pH Foram selecionados 19 tra¸cados cujo pH do beb´e `a nascen¸ca era inferior a 7 e outros tantos com pH superior a 7.2. O objetivo era percebe se o CompLearn tinha a capacidade de classificar os 38 tra¸cados nestes dois grupos. Como se vˆe pela Figura 4.16, a compress˜ao n˜ao est´a relacionada com o pH do cord˜ao umbilical medido `a nascen¸ca. CAP´ ITULO 4. AN ´ ALISE DE RESULTADOS 82 Figura 4.16: ´ Arvore de classifica¸c˜ao do Complearn para 38 tra¸cados onde 19 s˜ao de beb´es cujo pH do cord˜ao umbilical `a nascen¸ca era inferior a 2, e outros 19 superior a 2.2 4.3.2 CompLearn vs Variabilidade Curta Foram selecionados 40 tra¸cados, metade dos quais com variabilidade curta inferior a 20 enquanto na outra metade a variabilidade curta ´e superior a 70. Como se pode ver na Figura 4.17, o CompLearn facilmente distingue os dois grupos. CAP´ ITULO 4. AN ´ ALISE DE RESULTADOS 83 Figura 4.17: ´ Arvore criada pelo CompLearn para tra¸cados com diferentes variabilidades curtas (20 a verde e 70 a laranja) CAP´ ITULO 4. AN ´ ALISE DE RESULTADOS 84 No entanto, se adicionarmos 20 tra¸cados cuja variabilidade curta ronda os 50, o algoritmo j´a n˜ao tem resultados t˜ao promissores, mas ainda assim algo satisfat´orios (Figura 4.18). Figura 4.18: ´ Arvore criada pelo Complearn para tra¸cados com diferentes variabilidades curtas (20 a verde, 50 a azul, 70 a laranja) Podemos assim concluir que de certa forma a compress˜ao est´a relacionada com a variabilidade curta de um tra¸cado. Cap´ıtulo 5 Conclus˜ao Os resultados obtidos na disserta¸c˜ao de doutoramento [30] foram encorajadores e desta forma, nesta disserta¸c˜ao, pretendeu-se avaliar o interesse e utilidade de compressores com perdas (wavelets) na dete¸c˜ao de anomalias usando a compress˜ao. A quest˜ao de investiga¸c˜ao fundamental desta disserta¸c˜ao era averiguar se as perdas desses compressores teriam correspondˆencia com o ru´ıdo inerente no sinal fisiol´ogico e desta forma o m´etodo de classifica¸c˜ao por compress˜ao seria mais fi´avel. Numa primeira fase do trabalho us´amos compressores sem perdas para determinar a evolu¸c˜ao dos fetos ao longo do tempo (semanas) a n´ıvel de complexidade/compress˜ao dos tra¸cados de batimento card´ıaco fetal. Para tal, usamos trˆes compressores diferentes e todos apresentaram a mesma dinˆamica a menos de diferen¸cas de escala. Efetuamos a mesma an´alise para tentar detetar diferen¸cas entre sexos, no entanto a dinˆamica parece ter um comportamento an´alogo para ambos os sexos. Depois estudamos a possibilidade de existirem diferen¸cas entre os fetos com um bom vs mau outcome (pH do cord˜ao umbilical) e, para este dataset, verficou-se um maior poder de compress˜ao para os tra¸cados patol´ogicos ao longo de quase todas as semanas de gesta¸c˜ao. Relativamente aos grupos de fetos pr´e-termo (habitualmente definido como nascer com 36 ou menos semanas) e termo normal, detet´amos neste conjunto de dados, diferen¸cas na dinˆamica ao longo das semanas de gesta¸c˜ao, o que significa que a compress˜ao pode ser um bom indicador para esta vari´avel. Por fim, relativamente `as diferen¸cas de peso (percentil 3, percentil 10, entre o percentil 3 e o 10, e os normais) foram detetadas diferen¸cas na dinˆamica dos v´arios grupos o que mais uma vez nos leva a acreditar que a compress˜ao pode ser um bom preditor desta vari´avel. De forma a suportar estes resultados, achamos relevante validar de forma mais rigorosa estes resultados aplicando as mesmas t´ecnicas num conjunto de dados maior e usando metodologia 85 CAP´ ITULO 5. CONCLUS ˜ AO 86 estat´ıstica para a compara¸c˜ao dos grupos. De seguida us´amos fun¸c˜oes wavelet (que podem ser vistas como compressores com perdas) para comparar a sua efic´acia neste tipo de abordagem relativamente aos compressores sem perdas, mais uma vez na analise de batimento card´ıaco fetal. O dataset que us´amos foi constru´ıdo em [31] e pretendia-se agrupar os tra¸cados em normal, suspeito e patol´ogico. Os resultados pareciam prometedores para o caso da wavelet haar, no entanto ap´os usarmos esta mesma wavelet num dataset de maior dimens˜ao tal n˜ao foi o caso. Uma poss´ıvel explica¸c˜ao para estes resultados pode ser baseada no facto de os 3 clusters terem sido definidos com base no pH do cord˜ao umbilical que no primeiro estudo foi rigorosamente recolhido e no dataset com mais dados n˜ao, pois foram obtidos diretamente do sistema de informa¸c˜ao do hospital. Estud´amos tamb´em a utilidade das wavelets na predi¸c˜ao de fetos prematuros com base nos tra¸cados `a semana 30. Neste caso, sab´ıamos que a compress˜ao sem perdas o conseguia fazer com significado estat´ıstico, mas com base nas wavelets conseguiu-se melhorar a qualidade da predi¸c˜ao relativamente aos compressores sem perdas. Como trabalho futuro pretendemos avaliar quais as fun¸c˜oes wavelet que melhor se adaptam a este tipo de dados. Ser´a tamb´em interessante estudar os m´etodos de remo¸c˜ao de ru´ıdo (denoising), i.e., threshold e mais uma vez ajustar ao tipo de dados em causa. Relativamente ao m´etodo CompLearn, selecion´amos um conjunto de tra¸cados da semana 37 e tent´amos estudar qual a caracter´ıstica dos tra¸cados que estava a ser explorada pelo m´etodo. Conclu´ımos que a variabilidade curta dos tra¸cados ´e o principal fator no clustering usando o CompLearn. Para trabalho futuro pretendemos criar uma implementa¸c˜ao do algoritmo CompLearn com base nas wavelets. Sugerimos ainda tentar aplicar estes m´etodos a outros sinais fisiol´ogicos e outros m´etodos de data mining cl´asicos em substitui¸c˜ao da 2afase do CompLearn de forma a tornar o m´etodo mais c´elere. Bibliografia [1] Rudi Cilibrasi. Statistical inference through data compression. ILLC Dissertation Series DS-2007-01, 2007. [2] F. Qiao. Introduction to wavelets - a tutorial. Texas Southern University, Jan 2005. [3] Trisha Geenhalgh Paul E Plsek. The challenge of complexity in health care. 323:625-628, BMJ 2001. [4] A. Costa-Pereira J. Bernardes. Admission cardiotocography. 361(9370)pp.1741, Lancet, 2003. [5] Vit´anyi L. Antunes C. Santos, J. Bernardes. Clustering fetal heart rate tracings by compression. Special Track on Data Mining, the 19th IEEE International Symposium on Computer-Based Medical Systems, 2006. [6] P. Vit´anyi R. Cilibrasi. Clustering by compression. IEEE Transactions on Information Theory, 2005, 51(4) pp.1523-45. [7] M. Li P.M.B. Vit´anyi C.H. Bennett, P. G´acs and W. Zurek. Information distance. IEEE Transactions on Information Theory, 44(4):1407-1424, 1998. [8] X. Li B. Ma M. Li, X. Chen and P.M.B. Vit´anyi. The similarity metric. Proc. 14th ACMSIAM Symposium on Discrete Algorithms, 2003. [9] S.N. Talbar S.O. Rajankar. An optimized transform for ecg signal compression. ACEEE Int. J. on Signal and Image Processing, Vol.1, No.5, Dec 2010. [10] Mohammed Abo-Zahhad. Ecg signal compression using discrete wavelet transform. [11] Carl Taswell. The what, how, and why of wavelet shrinkage denoising. Computational Toolsmiths, Stanford, CA 94309-9925, Jan 1999. 87 BIBLIOGRAFIA 88 [12] Amina Khatun M. Mozammel Hoque Chowdhury. Image compression using discrete wavelet transform. IJCSI International Journal of Computer Science Issues, Vol.9, No.4, Jul 2012. [13] Luiz Antonio Lopez. Transformadas de wavelet e l´ogica fuzzy na inspe¸c˜ao por eddy-current em tubos de geradores de vapor de centrais nucleares. IPEN, Autarquia Associada `a Universidade de S˜ao Paulo, 2002. [14] G. Kaiser. A friendly guide to wavelets. pp. 44-45. [15] W. Press et al. Numerical recipes in fortran, cambridge university press, new york. pp. 498-499, 1992. [16] Amara Grasp. An introdution to wavelets. IEEE Computational Science and Engineering, Vol.2, No.2, Summer 1995. [17] G. P. Nason. Choice of the threshold parameter in wavelet function estimation. Department of Mathematics, University of Bristol, Bristol BS8 1TW, UK, 1995. [18] Tim Park. An introdution to wavelets and wavelet de-noising. ISBN: 978-09891305-4-7, 2014. [19] C. Deuschle S. Schluter. Using wavelets for time series forecasting: Does it pay off? Econstor, 2010. [20] Y. Meyer. Wavelets: Algorithms and applications. Society for Industrial and Aplied Mathematics, Philadelphia, pp. 13-31, 101-105, 1995. [21] W. Dally. Wavelet compression on imagine. Stanford University, Apr 2002. [22] I. Daubechies. Ten lectures on wavelets. SIAM, 1992. [23] Y. Meyer. Wavelets and operators. IEEE Transactions on Acoustics, Speech and Signal Processing 34 (1986), 434-441. [24] B. Vidakovic. Basics of wavelet transforms. Bayesian Statistics: Handouts, Handout 20, ISyE8843A. [25] C. Herley M. Vetterli. Wavelets and filter banks: Theory and design. IEEE Transactions on Signal Processing, 1992. [26] Anjum Khan B. Ismail. Image de-noising with a new threshold value using wavelets. Journal of Data Science 10(2012), 259-270. BIBLIOGRAFIA 89 [27] T. P. Barnwell M. J. T. Smith. Exact reconstruction techniques for tree-structured subband coders. IEEE Trans. Pattn Anal. Mach. Intell 11, 674-693, 1989. [28] I. M. Johnstone D. L. Donoho. Ideal spatial adaptation by wavelet shrinkage. Biometrika, June 1992. [29] Xu Zhenzhen Tam Ning. The application of wavelet threshold de-noising in mobile oxygen saturation monitoring software. Lancaster University, 2011. [30] Teresa Henriques. Assessing Complexity of Physiological Interactions. PhD thesis. [31] D. Ayres-de-Campos J. Bernardes H. Gon¸calves, A. P. Rocha. Linear and nonlinear fetal heart rate analysis of normal and acidemic fetuses in the minutes preceding delivery. Med Biol Eng Comput. 2006 Oct;44(10):847-55.