Aprimorando Processos de Imputação Multivariada de Dados com Workflows

XXIII Simpósio Brasileiro de Banco de Dados

Aprimorando Processos de Imputac¸a˜ o Multivariada de Dados com Workflows Rafael Castaneda1 , Claudia Ferlin3 , Ronaldo Goldschmidt1 , Jorge de Abreu Soares2 , Luis Alfredo V. de Carvalho3 , Ricardo Choren1 1

2

Sec¸a˜ o de Engenharia de Computac¸a˜ o – Instituto Militar de Engenharia (IME) Pc¸a General Tiburcio 80 – 22.290-270 – Rio de Janeiro – RJ – Brazil

CEFET-RJ – Centro Federal de Educac¸a˜ o Tecnol´ogica Celso Suckow da Fonseca Maracan˜a – Rio de Janeiro – RJ – Brazil 3

PESC/COPPE – Universidade Federal do Rio de Janeiro (UFRJ) Caixa Postal 68.511 – 21.941-972 – Rio de Janeiro – RJ – Brazil

Abstract� Knowledge discovery in databases usually face the problem of missing values. Thus there are several preprocessing mechanisms that aim to make data imputation. However, these mechanisms normally deal with univariate cases, i.e. cases that present missing values in only one column. Iterative imputation mechanisms are capable of dealing with cases that present missing values in several columns, imputing values for one column at a time, but offer several implementation possibilities, from which the data analists find it difficult to choose. This paper presents a workflow-based platform to allow the easy setup, experimentation, and analisys of several iterative imputation techniques. It shows the usage of the platform and a sample experiment. Resumo� Uma dificuldade comum aos processos de descoberta de conhecimento em bases de dados e´ a existˆencia de valores ausentes. Neste sentido, existem diversos de mecanismos de pr´e-processamento, com o objetivo de fazer imputac¸a˜ o de valores. Por´em, estes mecanismos normalmente lidam com cen´arios univariados, i.e. a ausˆencia de valores em uma u´ nica coluna. Mecanismos de imputac¸a˜ o iterativa s˜ao capazes de lidar com valores ausentes em diversas colunas, imputando valores em uma coluna por vez, por´em oferecem diversas possibilidades de implementac¸a˜ o e experimentac¸a˜ o, entre as quais analistas de dados muitas vezes tˆem dificuldade em escolher. Este artigo apresenta uma plataforma baseada em workflows capaz de automatizar a configurac¸a˜ o, execuc¸a˜ o, e avaliac¸a˜ o de t´ecnicas de imputac¸a˜ o de dados; e um estudo de caso conduzido sobre duas variac¸o˜ es de um mecanismo de imputac¸a˜ o iterativa, como prova de conceito.

1. Introduc¸a˜ o Diversas bases de dados, tanto na ind´ustria quanto em centros de pesquisa, apresentam a ocorrˆencia de valores ausentes [Farhangfar et al. 2007]. H´a varias causas para este problema, tais como falha humana em processos manuais de entrada de dados, erros de equipamentos e sensores, preenchimento incompleto de formul´arios, falhas e erros em sistemas gerenciadores de bancos de dados, entre outras.

238

XXIII Simpósio Brasileiro de Banco de Dados

Os valores ausentes dificultam a an´alise de dados. Diversos tipos de problemas s˜ao comumente associados com valores ausentes: (i) perda de eficiˆencia em processo de busca; (ii) complicac¸o˜ es com a manipulac¸a˜ o e an´alise dos dados, e; (iii) a diferenc¸a resultante entre uma an´alise de dados completos e incompletos (registros que apresentem v.a.). De um modo geral, existem duas abordagens para lidar com o problema: ignorar os registros com valores ausentes (o que pode levar a an´alises tendeciosas ou inveross´ımeis [Yuan 2008]), ou imput´a-los com novos valores [Farhangfar et al. 2007]. A imputac¸a˜ o de valores ausentes e´ uma tarefa de complexa aplicac¸a˜ o pr´atica, dada a quantidade de m´etodos e algoritmos dispon´ıveis, que v˜ao desde modelos estat´ısticos, a t´ecnicas de inteligˆencia de artificial, ou combinac¸o˜ es de ambos [Farhangfar et al. 2007] [Lakshminarayan et al. 1999]. A figura 1 ilustra este processo:

˜ simples. Figure 1. Processo de imputac¸ao

A maior parte dos m´etodos e pesquisas em imputac¸a˜ o lida exclusivamente com cen´arios de ausˆencia univariada de dados, i.e, cen´arios onde apenas um atributo (ou coluna), apresenta valores ausentes. Com o crescimento do tamanho e da complexidade das bases de dados nos u´ ltimos anos, e´ ingˆenuo acreditar que a ocorrˆencia de casos incompletos se dˆe apenas em um u´ nico atributo da base. Infelizmente, ao tentar aplicar estes m´etodos comuns na resoluc¸a˜ o de problemas de ausˆencia multivariada de dados, surgem uma s´erie de adversidades que impedem sua utilizac¸a˜ o direta [van Buuren et al. 2006]: i Os casos utilizados na predic¸a˜ o de valores ausentes podem eles pr´oprios apresentar valores ausentes (em outros atributos); ii E´ poss´ıvel encontrar casos de dependˆencia circular entre valores ausentes de um mesmo registro; iii A relac¸a˜ o entre um valor ausente e seus preditores se torna complexa e n˜ao-linear; iv A imputac¸a˜ o pode criar casos imposs´ıveis, como o dos “homens gr´avidos”, apresentado por van Buuren [van Buuren et al. 2006]. Existem duas categorias principais para os m´etodos capazes de solucionar problemas de ausˆencia multivariada de dados [van Buuren et al. 2006]: Joint-Modelling e Imputac¸a˜ o Iterativa. Joint-Modelling consiste em utilizar modelos preditivos para estimar todos os valores de uma u´ nica vez, tais como redes Bayesianas. J´a a imputac¸a˜ o iterativa consiste na divis˜ao de um problema multivariado em n problemas univariados, onde cada atributo que apresenta valores ausentes e´ resolvido de maneira independente, por t´ecnicas tradicionais da soluc¸a˜ o de problemas univariados [Gelman and Hill 2006]. Pode-se dizer que a Imputac¸a˜ o Iterativa utiliza uma t´ecnica de divis˜ao e conquista, reduzindo a complexidade geral de um problema multivariado e preservando as caracter´ısticas individuais de cada atributo. Por isto, este m´etodo e´ considerado mais eficiente por diversos autores, p.ex. [Gelman and Raghunathan 2001, Little and Rubin 2003,

239

XXIII Simpósio Brasileiro de Banco de Dados

van Buuren et al. 2006]. No entanto, as t´ecnicas de imputac¸a˜ o iterativa possuem suas pr´oprias limitac¸o˜ es e deficiˆencias, que incentivam a pesquisa de implementac¸o˜ es variantes [Rubin 2003, Royston 2005], aumentando continuamente o universo de explorac¸a˜ o e aplicac¸a˜ o de imputac¸a˜ o iterativa. Estas implementac¸o˜ es variantes possuem caracter´ısticas pr´oprias, gerando resultados possivelmente diferentes para o processo de imputac¸a˜ o em uma mesma base de dados. Assim, seria ideal que o analista pudesse experimentar com diversas implementac¸o˜ es a fim de optar por aquele que produza os melhores resultados. Na vis˜ao dos autores, tal experimentac¸a˜ o envolve quatro passos principais: i Combinar diferentes implementac¸o˜ es de imputac¸a˜ o iterativa; ii Utilizar, onde poss´ıvel, diferentes algoritmos para a resoluc¸a˜ o de cada iterac¸a˜ o (onde o problema se torna univariado); iii Variar os diversos parˆametros de cada algoritmo empregado; iv Avaliar de maneira uniforme os resultados obtidos por cada combinac¸a˜ o u´ nica dos fatores acima; O principal objetivo deste artigo e´ descrever uma plataforma de imputac¸a˜ o baseada em workflows, desenvolvida para automatizar a configurac¸a˜ o, execuc¸a˜ o, e an´alise de diferentes m´etodos de imputac¸a˜ o. Um estudo de caso sobre a comparac¸a˜ o de variac¸o˜ es em uma t´ecnica de imputac¸a˜ o iterativa e´ apresentado para ilustrar a plataforma proposta. O restante deste artigo est´a organizado da seguinte forma. A sec¸a˜ o 2 fala de imputac¸a˜ o iterativa, e motiva a experimentac¸a˜ o sobre duas variac¸o˜ es principais de implementac¸a˜ o. A sec¸a˜ o 3 apresenta a plataforma desenvolvida e como ela possibilita a experimentac¸a˜ o. A sec¸a˜ o 4 apresenta os resultados obtidos pelo estudo de caso para as variac¸o˜ es e a plataforma apresentadas. A sec¸a˜ o 5 ilustra alguns trabalhos relacionados e, finalmente, a sec¸a˜ o 6 apresenta as conclus˜oes.

2. Imputac¸a˜ o Iterativa A imputac¸a˜ o iterativa pode ser considerada uma generalizac¸a˜ o da imputac¸a˜ o univariada, onde a imputac¸a˜ o univariada e´ aplicada para cada atributo da base que apresente valores ausentes. Tomando os atributos com valores ausentes como uma matriz Y com as colunas Y1 , ..., Yk , e o conjunto de casos completos como X, o algoritmo realiza n imputac¸o˜ es univariadas, onde 1 ≤ n ≤ k, utilizando os casos preditores de X [Gelman and Hill 2006]. Este processo e´ ilustrado na figura 2, na qual uma tabela similar a da figura 1 apresenta um padr˜ao de valores ausentes multivariado nos atributos (colunas) 1 e 3. Neste caso, o processo de imputac¸a˜ o e´ conduzido em duas etapas (iterac¸o˜ es) onde cada atributo com valores ausentes e´ tratado como um problema univariado, sendo resolvido de maneira completamente independente do outro. Ao t´ermino das iterac¸o˜ es, os valores imputados para as duas colunas s˜ao utilizados para preencher a base. Esta abordagem apresenta uma s´erie de benef´ıcios que a tornam uma escolha atrativa para o problema de imputac¸a˜ o multivariada de dados. E´ capaz de reduzir a complexidade de um problema multivariado para n problemas univariados, onde n e´ o n´umero de atributos (colunas) com valores ausentes [Gelman and Hill 2006]. Ao fazer isto, torna poss´ıvel a aplicac¸a˜ o de diversas t´ecnicas j´a conhecidas na soluc¸a˜ o de casos univariados, como o algoritmo dos K-vizinhos, redes back propagation, redes Bayesianas, entre outros [Soares 2007, Gelman and Raghunathan 2001, Little and Rubin 2003].

240

XXIII Simpósio Brasileiro de Banco de Dados

˜ iterativa. Figure 2. Processo de imputac¸ao

Uma das principais deficiˆencias desta aplicac¸a˜ o comum da imputac¸a˜ o iterativa reside no fato dos atributos serem imputados de maneira completamente independente, de tal sorte que a imputac¸a˜ o perde quaisquer relac¸o˜ es de interdependˆencia que possivelmente existiam entre os atributos da base [Gelman and Hill 2006], gerando casos de inconsistˆencia, como o problema dos “homens gr´avidos”, apresentado por van Buuren [van Buuren et al. 2006]. Outro problema surge quando a ocorrˆencia de valores ausentes e´ distribu´ıda o suficiente para criar dependˆencias circulares entre os valores ausentes de um mesmo registro, um caso especial denominado ausˆencia co-linear. [Gelman et al. 2007]. A imputac¸a˜ o iterativa com realimentac¸a˜ o, ilustrada como estudo de caso neste artigo, e´ exemplo de uma implementac¸a˜ o variante que re-introduz os valores imputados na base de dados ao final de cada iterac¸a˜ o. Desta forma, os dados descobertos para um atributo s˜ao realimentados na base antes do pr´oximo atributo ser imputado, e n˜ao ao final de todas as iterac¸o˜ es, como no processo original. A expectativa e´ preservar com mais eficiˆencia a correlac¸a˜ o entre os atributos imputados. A figura 3 ilustra este caso. Ao aplicar a realimentac¸a˜ o de valores entre as iterac¸o˜ es obtˆem-se um progressivo enriquecimento do conjunto de treino, que se aproxima da completude a cada iterac¸a˜ o, suavizando os problemas onde h´a uma ampla ocorrˆencia de valores ausentes. Al´em disso, a relac¸a˜ o entre os atributos e´ preservada. N˜ao obstante, valores imputados quase sempre possuem um percentual de erro, e ao reintroduz´ı-los na base durante o processo de iterac¸a˜ o, o analista pode estar na verdade contribuindo para uma propagac¸a˜ o de erros, ao imputar novos valores sobre dados previamente imputados. O estudo de caso apresentado neste artigo e´ uma comparac¸a˜ o entre a imputac¸a˜ o iterativa sem e com realimentac¸a˜ o, a fim de determinar, para as bases de dados estudadas, se a realimentac¸a˜ o de dados e´ capaz de contribuir beneficamente para o processo de imputac¸a˜ o, e em que condic¸o˜ es.

241

XXIII Simpósio Brasileiro de Banco de Dados

˜ iterativa com realimentac¸ao. ˜ Figure 3. Processo de imputac¸ao

3. A Plataforma de Imputac¸a˜ o A organizac¸a˜ o de processos de descoberta de conhecimento em bases de dados em workflows n˜ao e´ novidade. Diversas pesquisas desenvolvem, ou se utilizam, de estruturas de workflow a fim de conduzir processos de KDD.[Fattore and Arrigo 2005] [van der Aalst et al. 2003][Gaaloul et al. 2005] A diferenc¸a para a proposta deste artigo reside no fato de que a plataforma e´ especializada em imputac¸a˜ o de dados, e preparada n˜ao apenas para a conduc¸a˜ o de um u´ nico experimento, mas para ser capaz de automatizar, com o menor esforc¸o poss´ıvel, a configurac¸a˜ o, execuc¸a˜ o e an´alise de diversos experimentos e variac¸o˜ es de experimentos. Os passos necess´arios para o processo de imputac¸a˜ o s˜ao desenvolvidos na forma de componentes, que executam recebendo dados de entrada e gerando dados de sa´ıda. O workflow e´ elaborado atrav´es do encadeamento das entradas e sa´ıdas dos componentes. Esta abordagem torna a implementac¸a˜ o dos algoritmos independente do conhecimento do fluxo geral do processo, e facilita a construc¸a˜ o de diversas variac¸o˜ es estruturais de maneira autom´atica, al´em de suavizar o esforc¸o de implementac¸a˜ o de novos componentes. A figura 4 mostra um diagrama livre, baseado no diagrama de atividades da UML, que ilustra um plano de trabalho com todos os passos necess´arios para realizar um experimento de imputac¸a˜ o iterativa. O fluxo comec¸a com uma base original (todos os valores adequadamente preenchidos). P primeiro passo (Provocar Padr˜ao de Ausˆencia) tem o trabalho de provocar valores

242

XXIII Simpósio Brasileiro de Banco de Dados

˜ iterativa. Figure 4. Processo de worflow para imputac¸ao

ausentes em uma c´opia da base de dados original. O segundo passo (Imputac¸a˜ o Iterativa) dispara um lac¸o que e´ executado enquanto existirem colunas com valores ausentes a serem imputadas. Para cada coluna, o passo 2 invoca o passo 3 (Divis˜ao em Treino/Imputac¸a˜ o), respons´avel por dividir os dados presentes na base em dois conjuntos, um “conjunto de imputac¸a˜ o”, com os registros que apresentam valores ausentes na coluna atual, e outro determinado “conjunto de treino”, utilizado pelos algoritmos de imputac¸a˜ o de valores ausentes como casos de predic¸a˜ o. Uma vez separados, os conjuntos s˜ao enviados para o quarto passo (Imputac¸a˜ o Simples), respons´avel por executar um algoritmo de imputac¸a˜ o capaz de sugerir valores para o conjunto de imputac¸a˜ o, em func¸a˜ o dos casos encontrados no conjunto de treino. Aqui podem ser empregados diversos algoritmos diferentes, como K-Vizinhos, Redes Neuronais Back-Propagation, Expectation-Maximization, entre outros. Independete do algoritmo escolhido, os valores descobertos para cada atributo da base s˜ao armazenados isoladamente, e n˜ao interferem na execuc¸a˜ o das pr´oximas iterac¸o˜ es. Assim que o lac¸o do passo 2 termina, quando n˜ao h´a mais colunas com valores ausentes, ele consolida todos os valores sugeridos em uma c´opia final da base. Por fim, o u´ ltimo passo (An´alise de Resultados) e´ respons´avel por analisar a qualidade do processo de imputac¸a˜ o, para cada combinac¸a˜ o u´ nica de todas as possibilidades acima, comparando as base restauradas por cada combinac¸a˜ o, com a base original. Nesta comparac¸a˜ o s˜ao empregadas medidas estat´ısticas de erro e distˆancia, como a distˆancia relativa, ou o erro m´edio quadr´atico [Chatfield 1992]. 3.1. Imputac¸a˜ o Iterativa com Realimentac¸a˜ o No caso espec´ıfico que este trabalho ilustra, foi conduzida uma comparac¸a˜ o entre a imputac¸a˜ o iterativa com e sem realimentac¸a˜ o de dados. A etapa de realimentac¸a˜ o de dados pode ser considerada um passo adicional sobre o processo tradicional de imputac¸a˜ o iterativa, onde os dados descobertos para um atributo da base, em uma iterac¸a˜ o, s˜ao introduzidos na base antes da pr´oxima iterac¸a˜ o tomar lugar. A fim realizar a imputac¸a˜ o iterativa com realimentac¸a˜ o, a plataforma e´ configurada para adicionar uma nova etapa ao processo. Esta nova etapa e´ respons´avel por introduzir os dados descobertos em uma iterac¸a˜ o na base de dados, antes que a pr´oxima iterac¸a˜ o comece, como pode ser visto na figura 5. Ao considerar um mecanismo de realimentac¸a˜ o para o processo de imputac¸a˜ o

243

XXIII Simpósio Brasileiro de Banco de Dados

˜ iterativa com realimentac¸ao. ˜ Figure 5. Processo de worflow para imputac¸ao

iterativa, surgem algumas quest˜oes. Certamente, uma delas e´ a ordem de imputac¸a˜ o dos atributos, uma vez que a imputac¸a˜ o de uma coluna tem impacto direto na imputac¸a˜ o das pr´oximas. Este trabalho emprega duas ordens de imputac¸a˜ o, respectivamente da coluna com menos valores ausentes para a coluna com mais valores ausentes, e vice-versa. 3.2. Utilizac¸a˜ o da Plataforma O objetivo da plataforma e´ facilitar o processo de experimentac¸a˜ o, que envolve a montagem de diferentes processos, a variac¸a˜ o de algoritmos e a combinac¸a˜ o de diferentes parˆametros, al´em da an´alise e comparac¸a˜ o dos experimentos. A estrutura de workflow facilitar a montagem dos componentes, e flexibiliza a combinac¸a˜ o e variac¸a˜ o de parˆametros. Os componentes do workflow obedecem a uma interface de execuc¸a˜ o e s˜ao acionados atrav´es da passagem de dados e parˆametros de configurac¸a˜ o. A sa´ıda de um ou mais componentes pode ser encadeada como entrada de outro(s), ficando a cargo da plataforma executar o transporte destas informac¸o˜ es entre os passos do workflow. A estrutura funciona sobre dois conceitos principais: (i) planos de workflow (ii) instˆancias de workflow. Um plano de workflow e´ a macro-estrutura do processo de imputac¸a˜ o. Relaciona os componentes envolvidos no processo, as regras de transformac¸a˜ o necess´arias para a execuc¸a˜ o do fluxo, e o(s) algoritmo(s) escolhidos. A figura 6 ilustra um plano elaborado para executar a imputac¸a˜ o iterativa de dados.

˜ Figure 6. Planos de workflow para imputac¸ao.

O plano ilustrado encadeia os componentes, de maneira similar ao esquema conceitual abordado no in´ıcio da sec¸a˜ o. Pode-se notar que este plano utiliza o algoritmo dos K-Vizinhos para a etapa de imputac¸a˜ o. Outros planos poderiam ser montados utilizandose por exemplo, BackPropagation, ou a m´edia simples. A plataforma e´ capaz de lidar

244

XXIII Simpósio Brasileiro de Banco de Dados

com mais de um plano simultaneamente. Ao montar plano cria-se a estrutura de execuc¸a˜ o do fluxo, por´em ainda n˜ao foram delinadas nesta etapa os valores dos parˆametros de configurac¸a˜ o de cada componente ou os dados de entrada. Estas informac¸o˜ es s˜ao utilizadas para a criac¸a˜ o das instˆancias de workflow. Cada plano de workflow possui uma ou mais instˆancias, que s˜ao as diferentes combinac¸o˜ es de dados e parˆametros que podem ser aplicadas aos componentes. Por exemplo, um dos parˆametros do algoritmo dos K-vizinhos, e´ o “K”, n´umero de casos utilizados como predic¸a˜ o. Podem-se configurar diversos n´umeros diferentes para K, e deixar a ferramenta explorar todas as poss´ıveis instˆancias de criac¸a˜ o, resultantes da combinac¸a˜ o de cada valor de K, com cada valor de cada um dos parˆametros, como por exemplo, a ordem de imputac¸a˜ o. Com este mecanismo e´ poss´ıvel executar sem esforc¸o, e de uma u´ nica vez, diversos experimentos diferentes. A figura 7 ilustra o workflow que realiza a Imputac¸a˜ o Iterativa com Realimentac¸a˜ o. Nesta figura, e´ poss´ıvel encontrar um componente adicional, respons´avel pela realimentac¸a˜ o dos dados no experimento, antes que o lac¸o de iterac¸a˜ o termine.

˜ com realimentac¸ao. ˜ Figure 7. Plano de workflow para imputac¸ao

Atualmente estes fluxos s˜ao desenhados atrav´es de arquivos de configurac¸a˜ o simples, onde os componentes podem ser habilitados, e seus parˆametros configurados. A ferramenta inicia buscando os arquivos de configurac¸a˜ o e monta todos os planos e instˆancias poss´ıveis, em func¸a˜ o dos valores encontrados nos arquivos. A configurac¸a˜ o dos planos, instˆancias, parˆametros de configurac¸a˜ o, e dados de entrada pode ser feita de maneira program´atica, atrav´es da utilizac¸a˜ o direta da API da plataforma de workflow, ou atrav´es de arquivos de propriedades, nos quais o usu´ario pode configurar os componentes habilitados no workflow, e indicar a variac¸a˜ o dos diversos parˆametros de configurac¸a˜ o de cada componente. A figura 8 mostra um exemplo de configurac¸a˜ o da tarefa de imputac¸a˜ o com o algoritmo KNN. Os resultados de imputac¸a˜ o s˜ao escritos em disco, no formato de XML (para os valores imputados), e Excel (para o resultado das an´alises). No XML s˜ao persistidos os resultados da execuc¸a˜ o das instˆancias de workflow. Al´em dos pr´oprios valores imputados, todos os parˆametros configurados s˜ao armazenados, como a ordem das colunas, se houve ou n˜ao realimentac¸a˜ o de dados, o algoritmo utilizado para imputac¸a˜ o univariada, entre outros. Estes arquivos XML servem de base para a an´alise de resultados, que confronta os valores imputados com os valores originais atrav´es de medidas estat´ısticas de erro. O produto final da an´alise e´ uma planilha (figura 9) que apresenta o fator de erro

245

XXIII Simpósio Brasileiro de Banco de Dados

˜ do workflow. Figure 8. Trecho do arquivo de configurac¸ao

de imputac¸a˜ o obtido por cada instˆancia diferente.

´ Figure 9. Planilha de analise gerada pela ferramenta.

Desenvolvida em Java, a plataforma procura facilitar a integrac¸a˜ o de novos algoritmos de imputac¸a˜ o, ou tarefas de uso geral. Criar um novo componente para a plataforma significa desenvolver uma classe cuja u´ nica restric¸a˜ o e´ a necessidade de se implementar uma interface provida pela API, que determina uma mesma assinatura para o m´etodo de invocac¸a˜ o de todos os componentes, uma soluc¸a˜ o baseada no padr˜ao de projeto ”Command” [E. et al. 1995]. A figura 10 ilustra o conceito:

Figure 10. Interface a ser implementada pelos componentes

Isto significa que a invocac¸a˜ o das tarefas do workflow s˜ao realizadas de maneira uniforme, por´em, a maneira como a tarefa e´ processada fica a cargo de cada componente, cujas classes podem fornecer implementac¸o˜ es pr´oprias, ou atuar como fachadas para invocac¸a˜ o de componentes prontos ou sistemas legados. E´ necess´ario, al´em de desenvolver as classes, especificar os parˆametros esperados pelo componente, para que a plataforma possa criar corretamente as instˆancias de workflow. Tal especificac¸a˜ o e´ feita em um descritor XML interno. Utilizando esta estrat´egia j´a foi poss´ıvel integrar a` plataforma componentes que

246

XXIII Simpósio Brasileiro de Banco de Dados

Imp. Iterativa sem Realimentac¸a˜ o - 12 Instˆancias Padr˜ao de Ausˆencia Perc. de Ausˆencia Knn - No de Vizinhos MAR 10%,20%,30% 1,3,5,10 Padr˜ao de Ausˆencia MAR

Imp. Iterativa com Realimentac¸a˜ o - 24 Instˆancias Perc. de Ausˆencia Ordem Atributos Knn - No de Vizinhos 10%,20%,30% Menos V.A, Mais V.A 1,3,5,10

ˆ Table 1. Planos e Instancias do Experimento

utilizam, por exemplo, redes-neuronais do framework Java Object Oriented Neural Networks (JOONE) [P. 2007] ou algoritmos gen´eticos do Java Genetic Algorithms Package (JGAP) [N. and Meffert 2007]. 3.3. Resultados Experimentais Os experimentos foram conduzidos sobre duas estruturas de imputac¸a˜ o iterativa, uma sem, e a outra com realimentac¸a˜ o de dados, detalhadas na sec¸a˜ o anterior. Por motivos de escopo, para o estudo de caso deste artigo foram realizados experimentos com um u´ nico algoritmo de imputac¸a˜ o, o dos K-Vizinhos. Ainda, o mecanismo de ausˆencia utilizado para criar as bases foi o Missing-at-Random (MAR) [Little and Rubin 2003], a escolha mais segura para representar os padr˜oes comumente encontrados nos valores ausentes de m´edias e pequenas bases no mercado e na ind´ustria [Song et al. 2005]. A tabela 1 ilustra as diferentes combinac¸o˜ es de parˆametros, e totaliza o n´umero de instˆancias configuradas, executadas, e avalidas pela plataforma de imputac¸a˜ o: Como os experimentos foram conduzidos em trˆes bases de dados diferentes, obt´em-se um total de 108 experimentos. A plataforma s´o precisa ser configurada uma u´ nica vez para cada base de dado diferente, de forma que os 108 experimentos foram conduzidos com 3 execuc¸o˜ es da ferramenta. Este pode ser considerado um n´umero pequeno, dado o escopo do trabalho, por´em demonstra o potencial da utilizac¸a˜ o de workflows a fim de agilizar a experimentac¸a˜ o entre diferentes t´ecnicas de imputac¸a˜ o. Uma vez que a estrutura b´asica dos dois planos de workflow era comum, existe uma garantia de que a u´ nica diferenc¸a entre as implementac¸o˜ es era o fator de realimentac¸a˜ o de dados. Isso garante que as variac¸o˜ es de erro nos experimentos, s˜ao frutos exclusivos da realimentac¸a˜ o. Os gr´aficos a seguir ilustram as taxas de erro obtidas pelo estudo de caso. Neles podem ser encontrados os ´ındices de erro para todas as colunas de cada base, al´em de uma medida “global”. Por limitac¸o˜ es de espac¸o, s˜ao apresentados aqui apenas os experimentos com 30% de valores ausentes. Cada gr´afico apresenta as taxas de erro em pares de barras horizontais, para respectivamente a imputac¸a˜ o iterativa com reuso e sem reuso (menor e´ melhor). O primeiro par de barras representa o erro global, que e´ a m´edia dos erros das colunas. As trˆes bases de dados utilizadas no experimento s˜ao as seguintes: Iris, Breast Cancer e Pima Indians, todas provenientes do reposit´orio de bases para KDD da Universidade da Calif´ornia [Merz and Murphy 1998]. A Iris e´ uma base que possui medidas sobre a largura e o comprimento dos caules e p´etalas de 150 plantas de trˆes esp´ecies diferentes. A Breast Cancer relaciona dados sobre diagn´osticos de cˆancer de mama em

247

XXIII Simpósio Brasileiro de Banco de Dados

pacientes do hospital de Wiscosin. J´a a base Pima cont´em dados sobre o ´ındice de diabetes em mulheres de uma tribo de ´ındios. A base Iris apresenta uma perfeita distribuic¸a˜ o de classes, com 50 plantas de cada esp´ecie, valores muito similares, bem correlacionados e que sofrem poucas variac¸o˜ es entre os diferentes registros e atributos. Como este e´ um cen´ario muito favor´avel para imputac¸a˜ o de dados, as limitac¸o˜ es conhecidas para o m´etodo de imputac¸a˜ o iterativa tradicional n˜ao vieram a` tona, de maneira que a t´ecnica de realimentac¸a˜ o n˜ao consegue realmente contribuir a` abordagem comum, mas apenas quase replic´a-la (figura 11).

Figure 11. Resultados para o experimento na base Iris.

Na base Breast Cancer, a imputac¸a˜ o iterativa com realimentac¸a˜ o apresenta os primeiros sinais de melhoria. As principais colunas beneficiadas foram a Bare Nuclei e a Marginal Adhesion, com uma diferenc¸a de mais de trˆes pontos percentuais erro. Como os atributos nesta base possuem um alto, mas n˜ao o´ bvio, grau de correlac¸a˜ o entre si, a realimentac¸a˜ o de valores foi capaz de fornecer maior consistˆencia a imputac¸a˜ o dos diferentes atributos, apresentando a menor taxa de erros em todos os casos (figura 12).

Figure 12. Resultados para o experimento na base Breast Cancer.

A base Pima e´ um grande desafio para os processos de imputac¸a˜ o, j´a que suas colunas possuem um grau muito fraco de correlac¸a˜ o, dificultando a detecc¸a˜ o de padr˜oes e o aprendizado dos algoritmos de imputac¸a˜ o [Soares 2007]. Neste cen´ario, onde n˜ao j´a n˜ao existe uma consistˆencia entre os diferentes atributos, a realimentac¸a˜ o trouxe poucos benef´ıcios, algumas vezes empatando, ou at´e piorando o desempenho do processo.

248

XXIII Simpósio Brasileiro de Banco de Dados

As u´ nicas ressalvas v˜ao para a dose de soro de insulina (serum insulim) e a concentrac¸a˜ o de glicose no sangue (glicose concentration), onde a realimentac¸a˜ o conseguiu aprimorar o desempenho da imputac¸a˜ o; e o n´umero de vezes em que a mulher ficou gr´avida (pregnant times), atributo provavelmente beneficiado pelo conhecimento pr´evio da idade da pessoa (age), uma vez que estes dois apresentam o maior grau de correlac¸a˜ o em toda a base (figura 13).

Figure 13. Resultados para o experimento na base Pima.

4. Trabalhos Relacionados O Weka [Witten and Frank 2005] e´ sem d´uvida uma das mais conhecidas plataformas de KDD. Possui diversos componentes relacionados a diversas etapas de KDD. Os seus componentes de pr´e-processamento de dados s˜ao denominados filtros, e apesar de fornecer v´arios deles, n˜ao existem algoritmos para lidar com imputac¸a˜ o multivariada de valores ausentes. O Weka fornece ainda diferentes mecanismos de interface, entre eles um mecanismo para experimentac¸a˜ o de componentes, e outro para o desenho de workflows. Na interface de experimentac¸a˜ o o usu´ario pode selecionar um componente, e combinar diversas execuc¸o˜ es do mesmo em diferentes bases de dados, inclusive variando seus parˆametros de configurac¸a˜ o. E´ poss´ıvel, ao final das execuc¸o˜ es, executar um processo de an´alise para fins de comparac¸a˜ o entre os m´etodos. J´a na interface de workflow, o usu´ario pode encadear diversos componentes do Weka de maneira visual, montando o processo de KDD de maneira mais intuitiva. A interface controla as associac¸o˜ es, e s´o permite o encadeamento de componentes cujas entradas e sa´ıdas sejam compat´ıveis. O que difere o Weka da plataforma apresentada e´ que muito embora ele possua mecanismos para experimentac¸a˜ o e desenho de workflows, os dois n˜ao funcionam em conjunto, ou seja, n˜ao e´ poss´ıvel experimentar as combinac¸o˜ es de dados e parˆametros de maneira encadeada, mas apenas em componentes isolados. O Tanagara [Rakotomalala 2005] e´ uma ferramenta que permite a construc¸a˜ o de processos de KDD atrav´es do encadeamento de componentes em uma a´ rvore de execuc¸a˜ o, de maneira similar a um workflow. Possui algoritmos para diversas tarefas, tais como clusterizac¸a˜ o, classificac¸a˜ o e associac¸a˜ o de dados. No aˆ mbito de pr´e-processamento, oferece algoritmos da a´ rea de estat´ıstica capazes de imputar valores, como a regress˜ao linear [Johnston 1972]. Por´em as implementac¸o˜ es apresentadas lidam com cen´arios de ausˆencia multivariada de dados.

249

XXIII Simpósio Brasileiro de Banco de Dados

No que diz respeito a variac¸a˜ o de experimentos, o Tanagara e´ flex´ıvel o suficiente para que se adicionem diferentes variac¸o˜ es de um mesmo componente na a´ rvore de execuc¸a˜ o, como por exemplo, uma entrada para o algoritmo dos K-Vizinhos com K igual 1, e outra com K igual a 3. Isto por´em, e´ menos eficiente do que realiza a plataforma apresentada neste artigo, onde as variac¸o˜ es de parˆametros s˜ao realizadas atrav´es de combinac¸o˜ es autom´aticas entre todos os parˆametros indicados para experimentac¸a˜ o. Para replicar no Tanagara o mesmo efeito encontrado no estudo de caso, onde a ferramenta proposta conduziu 108 experimentos, o usu´ario teria que replicar e definir, de maneira exaustiva, diversos componentes na a´ rvore de execuc¸a˜ o , a fim de modificar apenas um ou dois parˆametros, algo bem mais trabalhoso que as 3 configurac¸o˜ es necess´arias para execuc¸a˜ o da plataforma apresentada. Em relac¸a˜ o ao processo de imputac¸a˜ o, o Sequential Regression Multivariate Imputation (SRMI) foi o primeiro algoritmo a utilizar um mecanismo efetivo de reutilizac¸a˜ o de valores imputados [Lepkowski et al. 2001]. Ele funciona construindo modelos preditivos para cada coluna da base de dados, comec¸ando da coluna com menos valores ausentes para a coluna com mais valores ausentes. A cada iterac¸a˜ o, os valores descobertos pelo modelo preditivo anterior s˜ao aproveitados na gerac¸a˜ o do pr´oximo modelo. Outro trabalho de imputac¸a˜ o multivariada e´ o algoritmo Multivariate Imputation by Chained Equations (MICE) [Oudshoorn et al. 1999]. O MICE trabalha com a construc¸a˜ o de equac¸o˜ es encadeadas, onde a imputac¸a˜ o de um campo e´ considerada uma vari´avel cuja resoluc¸a˜ o e´ dada por uma f´ormula. As equac¸o˜ es para cada vari´avel s˜ao encadeadas, de maneira que a resoluc¸a˜ o de um atributo impacta na resoluc¸a˜ o de outros.

5. Conclus˜ao e Trabalhos Futuros Este artigo apresentou uma plataforma de imputac¸a˜ o capaz de realizar procedimentos de imputac¸a˜ o de dados atrav´es de workflows, e como estudo de caso , o uso da plataforma nas pesquisas de uma variac¸a˜ o da imputac¸a˜ o iterativa que utiliza realimentac¸a˜ o de dados, a fim de suavizar as principais deficiˆencias encontradas na abordagem comum. O m´etodo modificado foi experimentado em trˆes diferentes bases, e comparado com a abordagem tradicional de imputac¸a˜ o iterativa. A plataforma de imputac¸a˜ o foi de grande aux´ılio na conduc¸a˜ o dos testes, automatizando em trˆes u´ nicas execuc¸o˜ es (uma para cada base de dados), a configurac¸a˜ o, conduc¸a˜ o e an´alise de 108 experimentos diferentes. Ao trabalhar com uma estrutura de componentes e fluxos, modificar um experimento se tornou uma tarefa simples e pass´ıvel de automatizac¸a˜ o. Ainda, criar novas variantes de m´etodos j´a incorporados na plataforma se mostrou uma operac¸a˜ o mais segura, pois os componentes re-aproveitados j´a haviam sido testados e utilizados em produc¸a˜ o. Uma vez que toda a estrutura era comum entre os dois m´etodos experimentados, foi poss´ıvel garantir e atestar que a u´ nica diferenc¸a entre o m´etodo proposto e o m´etodo original era o fator de realimentac¸a˜ o de dados. Isto permite a exclus˜ao, nos experimentos, de fatores comuns de incerteza de comparac¸a˜ o, tais como qualidade da implementac¸a˜ o de diferentes algoritmos, diferenc¸as entre linguagens e plataformas de programac¸a˜ o e carregamento dos dados, entre outros. O custo de se replicar todos os experimentos manualmente, ou utilizando os

250

XXIII Simpósio Brasileiro de Banco de Dados

mecanismo comuns de outras ferramentas conhecidas, seria oneroso at´e mesmo para este pequeno estudo de caso. O benef´ıcio da utilizac¸a˜ o de uma estrutura de workflows capaz de automatizar os testes em todos os aspectos (configurac¸a˜ o, execuc¸a˜ o, e an´alise), e´ cada vez maior na medida em que a complexidade dos experimentos cresce. Com a estrutura apresentada, a plataforma foi capaz de atender os requisitos levantados na sec¸a˜ o 1. A criac¸a˜ o de planos , atrav´es da combinac¸a˜ o autom´atica de diferentes estruturas de imputac¸a˜ o iterativa, e algoritmos de imputac¸a˜ o, cobriu os requisitos (i) (ii); as instˆancias, que enumeram diferentes variac¸o˜ es u´ nicas de parˆametros e dados de entrada do workflow, atendeu ao requisito (iii); e por u´ ltimo, a metodologia de an´alise est´atica conduzida final de cada instˆancia atendeu ao requisito (iv). Em relac¸a˜ o ao estudo de caso, os resultados mostram que com a realimentac¸a˜ o de valores, pode-se obter uma melhoria significativa nos casos onde existe correlac¸a˜ o entre as colunas a serem imputadas. Destacaram-se, para as bases experimentadas, as seguintes vantagens no uso de um mecanismo de reutilizac¸a˜ o de valores: i Preservar a consistˆencia de imputac¸a˜ o entre as diferentes colunas, minizando o risco da imputac¸a˜ o de casos incorentes; ii Diminuir progressivamente a ocorrˆencia geral de valores ausentes; Os trabalhos futuros para a plataforma de imputac¸a˜ o envolvem o desenvolvimento de uma interface interativa para a construc¸a˜ o dos planos e instˆancias, a capacidade de lidar com fontes de dados heterogˆeneas, integrac¸a˜ o com componentes de outras ferramentas (como Weka), e suporte para processamento paralelo e/ou distribu´ıdo.

References Chatfield, C. (1992). A commentary on error measures. International Journal of Forecasting, 8(1):100–102. E., G., R., H., R., J., and J., V. (1995). Design patterns: Elements of reusable objectoriented software. Addison Wesley. Farhangfar, A., Kurgan, L., and Pedrycz, W. (2007). A novel framework for imputation of missing values in databases. IEEE Transactions on Systems, Man, and Cybernetics, 37(5):692–709. Fattore, M. and Arrigo, P. (2005). Knowledge discovery and system biology in molecular medicine: An application on neurodegenerative diseases. In Silico Biology, 5(2):199– 208. Gaaloul, W., Alaoui, S., Baina, K., and Godart, C. (2005). Mining workflow patterns through event-data analysis. In SAINT-W ’05: Proceedings of the 2005 Symposium on Applications and the Internet Workshops, pages 226–229, Washington, DC, USA. IEEE Computer Society. Gelman, A. and Hill, J. (2006). Data Analysis Using Regression and Multilevel/Hierarchical Models. Cambridge University Press. Gelman, A., Levy, M., and Abayomi, K. (2007). Diagnostics for multivariate imputations. Social Science Research Network - Social Science Electronic Publishing, Inc.

251

XXIII Simpósio Brasileiro de Banco de Dados

Gelman, A. and Raghunathan, T. (2001). Conditionally specified distributions: An introduction. Statistical Science, 16(3):268–269. Johnston, J. (1972). Econometric methods. McGraw-Hill. Lakshminarayan, K., Harp, S., and Samad, T. (1999). Imputation of missing data in industrial databases. Applied Intelligence, 11(3):259–275. Lepkowski, J., Raghunathan, T., Solenberger, P., and van Hoewyk, J. (2001). A multivariate technique for multiply imputing missing values using a sequence of regression models. Statistics Canada, 27(1):85–95. Little, R. and Rubin, D. (2003). Statistical analysis with missing data. Technometrics, 45:364–365. Merz, C. and Murphy, P. (1998). Uci repository of machine learning databases. University of California, Irvine, Department of Information and Computer Sciences. http://www.ics.uci.edu/ mlearn/MLRepository.html. N., R. and Meffert, K. (2007). http://jgap.sourceforge.net.

Jgap:

The java genetic algorithms package.

Oudshoorn, C., van Buuren, S., and van Rijckevorsel, J. (1999). Flexible multiple imputation by chained equations. Netherlands Organization for Applied Scientific, Technical Report PG/VGZ/99.045. P., M. (2007). Joone: Java object oriented neural engine - the complete guide. http://www.joone.org. Rakotomalala, R. (2005). Tanagra : un logiciel gratuit pour l’enseignement et la recherche. Actes de EGC, 2:697–702. Royston, P. (2005). Multiple imputation of missing values: Update of ice. Stata Journal, 5(2):188–201. Rubin, D. (2003). Nested multiple imputation of nmes via partially incompatible mcmc. Statistica Neerlandica, 57(1):3–18. Soares, J. (2007). Pr´e-Processamento em Minerac¸a˜ o De Dados: Um Estudo Comparativo em Complementc¸a˜ o. PhD thesis, COPPE/UFRJ. Song, Q., Shepperd, M., and Cartwright, M. (2005). A short note on safest default missingness mechanism assumptions. Empirical Software Engineering, 10(3):235–243. van Buuren, S., Brand, J., Groothuis-Oudshoorn, C., and Rubin, D. (2006). Fully conditional specification in multivariate imputation. Statistical Computation and Simulation, 76(12):1049–1064. van der Aalst, W., Weijters, A., and Maruster, L. (2003). Workflow mining: Discovering process models from event logs. Witten, I. H. and Frank, E. (2005). Data Mining: Practical machine learning tools and techniques. Morgan Kaufmann. Yuan, J. (2008). Multiple imputation for missing data: Concepts and new development. SAS Institute Technical Report P267-25.

252