MINERAÇÃO DE DADOS APLICADA A DOCUMENTOS DO PORTAL DA TRANSPARÊNCIA DO GOVERNO FEDERAL

C ENTRO F EDERAL DE E DUCAÇÃO T ECNOLÓGICA DE M INAS G ERAIS C URSO DE E NGENHARIA DE C OMPUTAÇÃO

MINERAÇÃO DE DADOS APLICADA A DOCUMENTOS DO PORTAL DA TRANSPARÊNCIA DO GOVERNO FEDERAL

A NDRÉ L UIZ S ILVEIRA H ERCULANO

Orientadora: Prof. Dr. Cristina Duarte Murta

B ELO H ORIZONTE D EZEMBRO DE 2014

A NDRÉ L UIZ S ILVEIRA H ERCULANO

MINERAÇÃO DE DADOS APLICADA A DOCUMENTOS DO PORTAL DA TRANSPARÊNCIA DO GOVERNO FEDERAL

C ENTRO F EDERAL DE E DUCAÇÃO T ECNOLÓGICA DE M INAS G ERAIS C URSO DE E NGENHARIA DE C OMPUTAÇÃO B ELO H ORIZONTE D EZEMBRO DE 2014

i

C ENTRO F EDERAL DE E DUCAÇÃO T ECNOLÓGICA DE M INAS G ERAIS C URSO DE E NGENHARIA DE C OMPUTAÇÃO AVALIAÇÃO DO T RABALHO DE C ONCLUSÃO DE C URSO

Aluno: André Luiz Silveira Herculano Título do trabalho: Mineração de Dados Aplicada a Documentos do Portal da Transparência do Governo Federal Data da defesa: 17 de Dezembro de 2014 Horário: 14:00h Local da defesa: CEFET-MG Campus II, prédio 17, sala 401

O presente Trabalho de Conclusão de Curso foi avaliado pela seguinte banca:

Prof. Dr. Cristina Duarte Murta- Orientadora Departamento de Computação Centro Federal de Educação Tecnológica de Minas Gerais Prof. Dr. Anísio Mendes Lacerda - Membro da banca de avaliação Departamento de Computação Centro Federal de Educação Tecnológica de Minas Gerais Prof. Dr. Edson Marchetti da Silva - Membro da banca de avaliação Departamento de Computação Centro Federal de Educação Tecnológica de Minas Gerais

ii

Dedico esse trabalho a Deus, por nunca me abandonar, à minha família, por me dar toda a base necessária e à minha namorada, por ser o meu porto seguro.

iii

Agradecimentos

Gostaria de agradecer à minha família, por ter me incentivado sempre, mesmo em momentos difíceis. Agradeço aos amigos e companheiros de trabalho José Francisco, Gustavo Carvalho, Germano Teixeira, dentre outros, que fizeram com que essa jornada fosse mais divertida. Sou grato à todos do setor NTIC (antigo DGO) do CEFET-MG, em especial ao Cássio, pela oportunidade de trabalho, aprendizado e amizade. Por último, mas não menos importante, gostaria de agradecer à minha orientadora Prof. Cristina Duarte Murta por ter acreditado no meu potencial e por sua exigência, sem dúvida responsável pela qualidade do presente trabalho.

iv

“Se você quer ir rápido, vá sozinho. Se você quer ir longe, vá acompanhado.” (Provérbio Africano)

v

Resumo Com o crescimento da capacidade de armazenamento, bases de dados grandes tornaramse comum nas empresas e organizações. Na área de Mineração de Dados, são estudadas e desenvolvidas técnicas específicas para lidar com grandes conjuntos de dados de forma eficiente, com o intuito de extrair informações relevantes. O presente trabalho expõe, de forma geral, as três grandes áreas da Mineração de Dados, mineração de padrões frequentes, classificação de dados e agrupamento. Para cumprir com esse objetivo, aplicamos uma técnica de cada área citada na base de dados disponível no Portal da Transparência do Governo Federal. Como resultado, obtivemos regras de associação — que nos informaram à respeito da data e valores do auxílio financeiro à estudantes pagos pelo MEC — modelo de classificação — uma árvore de decisão que classificou os pagamentos entre MEC e MCTI — e, por fim, agrupamentos — que agruparam os gastos cujos valores eram discrepantes em relação aos demais. Palavras-chave: mineração de dados; padrões frequentes; classificação; agrupamento; portal da transparência.

vi

Abstract Big databases are becoming common in the enterprise scenario with the increasing of storage capacity. In order to extract information from huge volumes of data, specific techniques that handle big data sets in a efficient way are being studied and developed in Data Mining. The current work explains, in a general way, the three big fields of Data Mining, frequent pattern mining, data classification and clustering. To achieve our goal, we ran one technique from each cited field on a data set about the direct expenses of the Brazilian government, available at Portal da Transparência — an open data initiative from the Federal government of Brazil. We achieved as results association rules — that clarify about the dates and amounts paid to students as an aid by MEC — , classification model — a decision three which can classify the tuples between MEC and MCTI — and clusters — that grouped together the entries with a outstanding amount paid compared to the others. Keywords: data mining; frequent pattern mining; data classification; clustering; portal da transparência.

vii

Lista de Figuras

Figura 1 Figura 2 Figura 3 Figura 4 Figura 5 Figura 6 Figura 7

– – – – – – –

Figura 8 – Figura 9 – Figura 10 – Figura 11 – Figura 12 – Figura 13 – Figura 14 – Figura 15 – Figura 16 – Figura 17 – Figura 18 – Figura 19 – Figura 20 –

Problemas que ocasionam má qualidade dos dados . . . . . . . . . . Formas de pré-processamento . . . . . . . . . . . . . . . . . . . . . . . Uso de histograma na redução de dados . . . . . . . . . . . . . . . . . Conceito de monotonicidade . . . . . . . . . . . . . . . . . . . . . . . Representação dos passos do algoritmo Apriori . . . . . . . . . . . . Representação do processo de classificação . . . . . . . . . . . . . . . Exemplo de uma árvore de decisão para a classificação de animais entre mamíferos e não mamíferos. . . . . . . . . . . . . . . . . . . . . Exemplo de partições possíveis no método de separação de uma árvore de decisão. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Exemplo de árvore de decisão antes e depois da poda . . . . . . . . . Exemplo do funcionamento do método k-means. . . . . . . . . . . . . Agrupamentos das unidades federais . . . . . . . . . . . . . . . . . . Pré-processamento da fase de mineração de padrões frequentes . . . Pré-processamento da fase de classificação dos dados . . . . . . . . . Distribuição dos registros entre MEC e MCTI . . . . . . . . . . . . . . Distribuição dos registros entre os meses de 2013 . . . . . . . . . . . . Distribuição dos registros entre os intervalos de valores . . . . . . . . Árvore de decisão para classificar pagamentos entre MEC e MCTI . . Pré-processamento da fase de agrupamento . . . . . . . . . . . . . . . Dois agrupamentos encontrados no conjunto de dados . . . . . . . . Três agrupamentos encontrados no conjunto de dados . . . . . . . .

viii

6 7 10 12 13 15 16 18 20 26 30 43 49 50 51 51 52 54 55 56

Lista de Tabelas

Tabela 1 – Conjunto de transações. . . . . . . . . . . . . . . . . . . . . . . . . . . Tabela 2 – Resumo das métricas descritivas para os dados categóricos dos gastos diretos de janeiro de 2013. . . . . . . . . . . . . . . . . . . . . . . . . . Tabela 3 – Resumo das métricas descritivas para os dados não categóricos dos gastos diretos de janeiro de 2013. . . . . . . . . . . . . . . . . . . . . . Tabela 4 – Resumo das métricas descritivas para os dados categóricos dos gastos diretos de 2013. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Tabela 5 – Resumo das métricas descritivas para os dados não categóricos dos gastos diretos de 2013. . . . . . . . . . . . . . . . . . . . . . . . . . . . Tabela 6 – Métricas da base de dados antes e depois da remoção do valores outliers e extremos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Tabela 7 – Sumário de métricas dos agrupamentos encontrados pelo algoritmo k-means . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Tabela 8 – Sumário de métricas dos agrupamentos encontrados pelo algoritmo k-means . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

ix

13 34 34 35 36 50 53 55

Lista de Quadros

Quadro 1 – Glossário das colunas do arquivo de gastos diretos disponibilizado no portal da transparência. . . . . . . . . . . . . . . . . . . . . . . . . Quadro 2 – Glossário das siglas de cada ministério. . . . . . . . . . . . . . . . .

x

62 63

Lista de Algoritmos

Algoritmo 1 – Algoritmo para a construção de uma árvore de decisão para o conjunto de registros D . . . . . . . . . . . . . . . . . . . . . . . .

17

Algoritmo 2 – Algoritmo k-means. . . . . . . . . . . . . . . . . . . . . . . . . . .

26

xi

Lista de Abreviaturas e Siglas

CGU

Controladoria Geral da União

MD

Mineração de Dados

KDD

Knowledge Discovery in Databases

MEC

Ministério da Educação

MCTI

Ministério da Ciência, Tecnologia e Inovação

MTE

Ministério do Trabalho e Emprego

xii

Sumário

1 – Introdução . . . . . . . . . . . . . 1.1 Caracterização do Problema 1.2 Motivação . . . . . . . . . . 1.3 Objetivos . . . . . . . . . . . 1.4 Estrutura do Texto . . . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

1 1 2 3 3

2 – Fundamentação Teórica . . . . . . . . . . . . . . . . . . . . . . 2.1 Tipos de Dados . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Pré-processamento . . . . . . . . . . . . . . . . . . . . . . 2.2.1 Limpeza dos Dados . . . . . . . . . . . . . . . . . . 2.2.2 Integração de Múltiplas Bases de Dados . . . . . . 2.2.3 Redução de Dados . . . . . . . . . . . . . . . . . . 2.3 Mineração de Padrões Frequentes e Regras de Associação 2.3.1 Formalização dos Conceitos Envolvidos . . . . . . 2.3.2 Algoritmo Apriori . . . . . . . . . . . . . . . . . . 2.3.3 Métodos de Avaliação de Padrões . . . . . . . . . 2.4 Classificação . . . . . . . . . . . . . . . . . . . . . . . . . . 2.4.1 Indução por Árvore de Decisão . . . . . . . . . . . 2.4.2 Avaliação do Modelo de Classificação . . . . . . . 2.5 Agrupamento . . . . . . . . . . . . . . . . . . . . . . . . . 2.5.1 Requisitos e Características . . . . . . . . . . . . . 2.5.2 Classificação dos Métodos de Agrupamento . . . 2.5.3 Métodos de Particionamento . . . . . . . . . . . . 2.5.4 Avaliando os Métodos de Agrupamento . . . . . .

. . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . .

4 4 5 6 8 9 9 10 11 14 14 16 20 22 22 24 25 27

3 – Trabalhos Relacionados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

29

4 – Metodologia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.1 Delineamento da Pesquisa . . . . . . . . . . . . . . . . . . . . . 4.2 Coleta de Dados . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3 Pré-processamento e Análise Descritiva dos Dados . . . . . . . 4.4 Aplicação e Funcionamento do Programa Apriori . . . . . . . 4.5 Aplicação e Funcionamento de Modelos de Árvore de Decisão 4.5.1 WEKA . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.5.2 Pré-processamento . . . . . . . . . . . . . . . . . . . . . 4.5.3 Classificador J48 . . . . . . . . . . . . . . . . . . . . . . .

32 32 32 32 36 37 38 39 40

xiii

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

4.6

Aplicação e Funcionamento do Algoritmo K-Means . . . . . . . . . . . .

5 – Análise dos Resultados . . . . . . . . . . . . . 5.1 Mineração de Padrões Frequentes . . . . . 5.2 Classificação . . . . . . . . . . . . . . . . . 5.2.1 Resultados do Pré-processamento 5.2.2 Resultados Árvore de Decisão . . . 5.3 Agrupamento . . . . . . . . . . . . . . . . 5.4 Síntese dos Resultados . . . . . . . . . . .

. . . . . . .

42 42 48 48 52 53 56

6 – Conclusão e Trabalhos Futuros . . . . . . . . . . . . . . . . . . . . . . . . . . .

58

Referências . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

59

Apêndices

61

APÊNDICE A–Glossário do Arquivo de Gastos Diretos . . . . . . . . . . . . .

62

APÊNDICE B – Glossário das Siglas de Cada Ministério do Brasil . . . . . . . .

63

xiv

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

41

1

1 Introdução

Nesse capítulo é feita a contextualização do trabalho explicitando-se a caracterização do problema a ser tratado, a motivação em se aplicar técnicas de Mineração de Dados aos dados disponíveis no Portal da Transparência, a apresentação dos objetivos do trabalho, o escopo do tema a ser discutido e, por fim, a estrutura do texto.

1.1

Caracterização do Problema

Organizações mantêm diariamente petabytes de conteúdo dos mais diversos, desde transações financeiras, registros médicos, leituras de sensores sísmicos, histórico de buscas na Web, até a posição geográfica de nossos smartphones ao longo do tempo. Temos uma quantidade crescente de dados, porém nossa capacidade analítica se mostra não suficiente para lidar com tamanha quantidade de dados. Tal situação vem sendo descrita como rica em dados mas pobre em informação (HAN et al., 2011, p. 5). O rápido crescimento do poder de armazenamento superou a nossa capacidade de análise sem o auxílio de ferramentas adequadas para esse propósito. Sem essas ferramentas, as bases de dados se tornam “tumbas de dados”, arquivos que são raramente analisados e, com isso, decisões importantes são tomadas, não com base em informações geradas por esses dados mas pela intuição de um gerente ou diretor. Dado o tamanho e a diversidade dessas bases de dados se faz imprescindível a sistematização no tratamento desses conjuntos de bytes para que informações bem como as conexões e os relacionamentos entre elas sejam mais facilmente extraídas e, assim, possam auxiliar no processo de tomada de decisão. Fazendo-se uma analogia com a mineração do ouro, em que a pedra bruta é escavada e tratada até que algo valioso seja extraído, a Mineração de Dados provê técnicas que tem como objetivo tratar grandes bases de dados para buscar padrões, regras e conexões que construam informações relevantes e possam guiar o processo de tomada de decisão. Na literatura, a Mineração de Dados é considerada apenas um passo, ainda que imprescindível, em um processo maior chamado Descoberta de Conhecimento. Para (ELSMARI; NAVATHE, 2010, p. 1036) a Descoberta de Conhecimento é executada em seis passos: seleção, limpeza, enriquecimento, transformação e mineração dos dados e, finalmente, apresentação. No entanto, o termo Mineração de Dados está sendo popularizado pela mídia e pelos profissionais da área e em alguns casos assume o papel do processo da descoberta de conhecimento como um todo, ou ainda, o processo de extrair informações relevantes de grandes bases de dados.

Capítulo 1. Introdução

2

É importante ressaltar a importância de dois termos da definição de Mineração de Dados acima: informações relevantes e grandes bases de dados. Segundo Cios et al. (2007, p. 3), informação relevante deve ser compreensível, válida, inédita e útil. Informações irrelevantes são aquelas que demandem uma quantidade grande de regras e passos para serem entendidas, não podem ser reproduzidas ou validadas, já são conhecidas na indústria ou comunidade (com exceção de casos em que se quer validar os resultados já conhecidos) ou, ainda, aquelas que não trazem nenhuma utilidade para o usuário final tendo como ponto de vista o domínio estudado. Mineração de Dados deve focar no tratamento eficiente de grandes bases de dados. A empresa AT&T lida com mais de 300 milhões de ligações diárias de mais de 100 milhões de usuários, o Wal-Mart mantém registro de 21 milhões de transações diariamente em suas lojas ao redor do mundo (CIOS et al., 2007, p. 4), esses são exemplos da escala em que a mineração de dados é utilizada. O Portal da Transparência do Governo Federal é uma iniciativa da ControladoriaGeral da União, lançada em novembro de 2004 (CGU (Controladoria Geral da União), 2014) em uma tentativa de aumentar a transparência com os gastos de recursos públicos. Os dados divulgados no Portal da Transparência são de responsabilidade dos ministérios e outros órgãos do Poder Executivo Federal (CGU (Controladoria Geral da União), 2014) e a Controladoria Geral da União fica, então, responsável por reunir e disponibilizar essas informações no Portal. No site é possível ter acesso à informações como as receitas previstas, lançadas e realizadas pelo Governo Federal, Participação e Controle Social, Informações sobre Gastos Diretos do Governo Federal: contratação de obras, serviços e compras governamentais, dentre outros.

1.2

Motivação

Em Março de 2014, o Portal da Transparência mantinha 1.702.803.410 registros (CGU (Controladoria Geral da União), 2014). Manipular esses dados tendo em vista a escalabilidade e o desempenho demanda a aplicação de técnicas engenhosas como as estudadas na MD. O estudo dos dados disponíveis no Portal da Transparência é motivado pelos benefícios que advêm dessa análise como a fiscalização do cumprimento do orçamento público, o entendimento por parte da população a respeito da destinação dada aos recursos públicos, maior conhecimento dos diversos programas sociais oferecidos pelo Governo Federal e seus órgãos, entre outros. As técnicas de MD aplicadas aos dados do Portal da Transparência podem prover diversas análises como, por exemplo, classificar os orgãos 1 dispostos na base 1

Entidades do Governo Federal como por exemplo, o MEC, o MCTI, entre outros.

Capítulo 1. Introdução

3

de dados por gastos, predizer qual será a despesa total de uma determinada entidade em um mês específico com base em seu histórico, identificar o não cumprimento de regras públicas, entre outras. Dessa forma, decisões podem ser tomadas com base nas informações retiradas sistematicamente dos dados estudados e não mais baseadas na intuição ou conhecimento, por vezes superficial, de uma só pessoa ou comitê, que pode estar sujeito à toda a sorte de interferências e prejulgamentos. Ainda assim, é fundamental o conhecimento profundo, sintático e semântico, dos dados estudados para que seja definido a relevância da informação extraída e dos padrões encontrados.

1.3

Objetivos Os objetivos desse trabalho são:

• Obter uma visão geral da área de mineração de dados; • Aplicar três técnicas de mineração de dados à base de dados do Portal da Transparência, mais especificamente, referente aos gastos diretos de 2013. Essas técnicas são das seguintes áreas: mineração de padrões frequentes, classificação e agrupamento. A realização do trabalho nos permitiu ampliar os conhecimentos não só na área de mineração de dados mas também dos gastos disponibilizados no Portal da Transparência. Ao final do trabalho foi possível encontrar regras de associação entre os gastos, classificar os registros entre MEC e MCTI, tendo como parâmetro a data e o valor do pagamento e, finalmente, pudemos também agrupar as despesas de acordo com o valor pago.

1.4

Estrutura do Texto

O presente trabalho está dividido em 6 capítulos. O próximo capítulo apresenta toda a fundamentação teórica necessária para a execução do trabalho, abrangendo a fase de preprocessamento, técnicas de mineração de padrões frequentes, classificação e, por fim, agrupamento. O Capítulo 3 apresenta alguns trabalhos que discutem aplicações práticas das técnicas descritas na fundamentação teórica. No capítulo seguinte, Capítulo 4, é descrita a metodologia adotada nos experimentos. O Capítulo 5 discute os resultados obtidos e, por último, no Capítulo 6 é feita conclusão e algumas indicações para trabalhos futuros.

4

2 Fundamentação Teórica

Esse capítulo apresenta as definições de termos utilizados ao longo do trabalho bem como oferece uma visão geral dos conceitos e técnicas de mineração de dados abordados no mesmo. Os tipos de dados, o pré-processamento e as técnicas de mineração de padrões frequentes, classificação e agrupamento, serão os principais tópicos descritos.

2.1

Tipos de Dados

O primeiro passo na busca por informações provenientes de uma base de dados é entender que tipo de dados estamos lidando. Nesse primeiro passo devemos ser capazes de responder perguntas como: Quais são os tipos de atributos que compõem os campos de dados? Quais são os possíveis valores que esses atributos podem assumir? Esses valores são discretos ou contínuos? Existe alguma maneira de melhor representálos para que possamos extrair melhor o sentido do dados? Qual é a distribuição dos valores? Para tal, devemos aplicar técnicas de Estatística Descritiva como medidas de tendência central (moda, média e mediana) e medidas de variabilidade (variância, desvio padrão, coeficiente de variação). Essas medidas serão de grande utilidade durante a fase de pré-processamento e também na decisão de quais técnicas e algoritmos aplicar à base de dados com objetivo de extrair essa ou aquela informação. É assumido que o leitor já domine tais técnicas e, portanto, suas explicações estão fora do escopo deste trabalho. Definimos como objeto de dado uma entidade, por exemplo, o registro de um cliente em um banco de dados de uma loja de comércio eletrônico. Objetos de dados (também chamados somente de objetos) são descritos por atributos, são características desse objeto de dado, por exemplo, o nome do cliente, seu CPF, dentre outros. Conjunto de todos os atributos que descrevem o objeto de dados é chamado de vetor de atributos. Um atributo pode ser divido em nominal, binário, ordinal e numérico. Atributos nominais são atributos que cujos valores são simbólicos que representem nomes ou ainda classes para o atributo. Seguindo o exemplo do objeto de dado cliente, um possível atributo nominal seria cidade de nascimento. Podem também possuir valores numéricos em que, nesse caso, não representem números em si mas classes para um objeto. Os valores de atributos nominais, ao contrário dos atributos ordinais, não possuem em si um sentido de ordenação (MORETTIN; BUSSAB, 2010). Atributos binários são aqueles que podem assumir necessariamente dois valores como por exemplo, fumante ou não fumante, casado ou solteiro. Usualmente, tais atributos são valorados com 0 ou 1, representando a ausência ou presença de uma determinada

Capítulo 2. Fundamentação Teórica

5

característica. Atributos ordinais são similares aos atributos nominais porém seus valores dão um sentido de ordenação ao atributo. Por exemplo, o grau de instrução de um cliente, que pode assumir os valores fundamental, médio e superior, indicando uma ordem entre eles, porém a magnitude entre valores sucessivos não é conhecida. Atributos numéricos são quantitativos (em oposição aos demais que são qualitativos) e assumem valores reais ou inteiros e, por serem numéricos, pode-se calcular medidas estatísticas como média, mediana, entre outras, enquanto que nos demais tipos de atributos, somente a moda e frequência podem ser calculadas (HAN et al., 2011, p.3944).

2.2

Pré-processamento

Bases de dados do mundo real não raro contêm inconsistências como dados de registros já deletados, discrepâncias como erros de medição e ainda redundâncias como dados agregados entre outros. A má qualidade dos dados analisados leva a más conclusões; e por isso, se faz necessária a sistematização no tratamento inicial dos dados antes da aplicação das técnicas de mineração de dados. Além do mais, quando os usuários acreditam que os dados analisados contém erros, são discrepantes ou de má qualidade, tendem a não confiar nas informações resultantes do processo de mineração de dados. A definição da qualidade dos dados difere de autor para autor. Porém, em sua maioria, é possível observar que os problemas a serem resolvidos nessa fase da mineração de dados são a minimização (idealmente a eliminação) da imprecisão (valores errados ou que desviam do esperado), da não completude (valores em branco ou atributos que contenham somente dados agregados) e da inconsistência (referências a registros deletados, por exemplo) dos dados. Han cita ainda a não sequência temporal, falta de credibilidade e a não interpretabilidade dos dados, como problemas a serem solucionados nessa fase (HAN et al., 2011, p.84). Para Rahm e Do (2000), os problemas que ocasionam a má qualidade dos dados podem ser classificados em problemas de uma fonte ou de múltiplas fontes de dados que, em seguida, são divididos em nível de instância e nível de esquema. Para uma fonte de dados, problemas no nível de esquema, reflete a má projeção do esquema de dados, enquanto no nível de instância os problemas estão nos registros. Já no contexto de múltiplas fontes de dados, no nível de esquema, os problemas surgem devido a heterogeneidade entre os diferentes esquemas, enquanto que no nível de instância os problemas têm origem na inconsistência entre as múltiplas bases de dados. Essa classificação está esquematizada na Figura 1. O tratamento inicial dos dados é conhecido como pré-processamento e envolve

Capítulo 2. Fundamentação Teórica

6

Figura 1 – Problemas que ocasionam má qualidade dos dados

Fonte: Adaptado de Rahm e Do (2000, p.3)

os passos de: limpeza, em que inconsistências são removidas (ou tratadas seguindo algum critério) —integração, passo no qual diferentes bases de dados são integradas para gerar uma base só —redução, em que a base de dados é reduzida de maneira que a análise seja mais rápida sem que se perca informação —transformação dos dados, operação que acontece também durante os demais passos seja para normalizar os dados, formatar atributos como datas, entre outros. Na Figura 2, estão representados esses passos do pré-processamento, que serão discutidos nas subseções seguintes.

2.2.1

Limpeza dos Dados

A limpeza dos dados lida com a remoção de erros e inconsistências da base de dados a ser minerada. Tais erros existem devido a uma infinidade de razões como mal funcionamento de um sensor em uma fábrica, erro de digitação em um formulário online, informação não verdadeira proposital (um cliente decide mentir sobre sua idade em uma pesquisa, por exemplo), dentre outros. Há também os casos em que a informação é faltante como um campo deixado em branco, algum erro ao salvar um arquivo, dentre outros. Esses erros podem ser tratados das seguintes formas: • Ignorar a tupla: geralmente usado quando o valor do atributo que se está estudando não está presente, assumindo que a tarefa de mineração envolve classificação. Essa técnica deve ser usada com cuidado uma vez que ignorando-se uma tupla, a informação associada aos atributos que estão presentes é perdida. • Usar uma constante global: caso o atributo sexo de uma tupla esteja faltando, pode-se preencher com o valor “Desconhecido”, por exemplo. Apesar de simples, essa abordagem pode levar os algoritmos de mineração a resultados errados visto que muitas tuplas podem possuir esse valor em comum e, por isso, confundidos como tendo algo em comum.

Capítulo 2. Fundamentação Teórica

7

Figura 2 – Formas de pré-processamento

Fonte: Adaptado de Han et al. (2011, p.87)

• Usar uma medida de tendência central: pode-se usar o valor da média para dados cuja distribuição de valores é simétrica ou a mediana, caso contrário. • Preencher com o valor mais provável: aplicando-se técnicas como regressão, árvores de decisão, dentre outras, é possível estimar um valor provável para o atributo faltante, baseando-se nos demais atributos. Vale lembrar, porém, que nas três últimas abordagens descritas acima é introduzida uma informação nova ao dataset dando, assim, margem para mais erros de interpretação da análise resultante do processo de mineração. No caso em que os valores estão presentes porém são discrepantes é possível aplicar técnicas para suavizar essa discrepância como a regressão, em que tentam conformar os valores conhecidos em uma função matemática; compartimentação, processo em que os dados são divididos em conjuntos, ou bins, e o valor do atributo suavizado será a média dos valores do respectivo grupo e, por fim, análise de outliers, em que os valores são agrupados com base em sua similaridade e os elementos que não pertencerem a nenhum grupo são considerados outliers.

Capítulo 2. Fundamentação Teórica

8

A limpeza dos dados começa com a detecção de anomalias e, para tal, se faz necessário o conhecimento sintático e estatístico da base de dados, isto é, é preciso que se conheça os metadados. É nesse ponto que se utiliza as métricas descritivas e de variação extraídas da base como média, mediana, moda, valores máximo e mínimo, coeficiente de variação, dentre outros. O conhecimento sintático diz respeito ao esquema da base de dados, isto é, qual é a política para tuplas duplicadas, atributos em branco, etc. É um processo iterativo que envolve dois passos —detecção de anomalias e transformação dos dados —e que em cada iteração é susceptível a introdução de mais erros, segundo (JERMYN et al., 1999) devido ao não registro das decisões de limpeza, falta de metodologia, entre outros.

2.2.2

Integração de Múltiplas Bases de Dados

Não raro se quer minerar dados provenientes de múltiplas bases de dados e com isso nos deparamos com o problema de integração entre essas bases. O tratamento adequado dessa integração pode não somente eliminar dados redundantes como também reduzir inconsistências e elevar a qualidade da informação extraída pelos algoritmos de mineração de dados. Durante a fase de integração são encontrados algumas dificuldades como o problema de identificação, que consiste em mapear os diferentes esquemas e modelos de objetos do mundo real para um só esquema. Por exemplo, em um banco de dados o atributo que mantém o nome de um cliente é chamado nome_cli e em uma segunda base de dados é chamado cli_name; ou em um esquema o tipo de pagamento assume os valores “X” e “Y” e em outro esquema são valorados com “I” e “J”. Dados redundantes são causados por agregação entre atributos, tabelas não normalizadas (uma prática comum em banco de dados para diminuir o número de operações de junção entre tabelas) e apresentam problema para o processo de mineração de dados uma vez que o número de registros da base de dados aumenta, demandando mais tempo de computação e possivelmente alterando o resultado final do processo de Mineração. Algumas redundâncias podem ser detectadas com o uso de análise de correlação, em que, dados dois ou mais atributos, tal análise avalia se esses atributos estão ou não correlacionados. Para atributos nominais é usado o teste de correlação χ2 (qui quadrático), para atributos numéricos pode-se usar o coeficiente de correlação ou a covariância relacionada aos dois atributos. Ainda na fase de integração, deve-se detectar e resolver conflitos de valores. Por exemplo, em uma base de dados o atributo peso é representado por quilograma enquanto em uma outra base o mesmo atributo é representado em libras, ou duas universidades que mantêm as notas dos alunos usando métricas diferentes, uma usa a escala de F até A e a outra usa de 0 a 100. Esse processo é relacionado à fase de limpeza

Capítulo 2. Fundamentação Teórica

9

dos dados discutido na Subseção 2.2.1.

2.2.3

Redução de Dados

A fase de redução de dados pode ser aplicada para obter uma representação do dataset muito menor em volume porém que mantenha, tanto quanto for possível, suas características. Isto é, aplicando-se as técnicas de mineração de dados na base de dados reduzida se produzirá resultados parecidos àqueles que seriam obtidos usando-se a base de dados original. Os dados podem ser reduzidos com relação à sua dimensão ou em número de tuplas. Redução em dimensão é o processo de se extrair os atributos, dimensões que mais contribuem para o processo de análise. Essa redução pode ser feita usando-se transformada discreta de onda, técnica de processamento de sinais que quando aplicada à um vetor de atributos X, resulta em um vetor (geralmente esparso) X’ de coeficientes de onda (HAN et al., 2011, p.100). Pode-se usar, também, a Análise de Componente Principal, técnica que visa produzir um vetor base de dimensão r que melhor captura a variância dos dados (ZAKI; JR., 2014, p.208). Por fim, pode-se ainda fazer a seleção de um subconjunto de atributos com algumas técnicas cujo objetivo principal é achar o conjunto mínimo de atributos tal que a distribuição probabilística dos dados em suas classes seja a mais próxima possível da distribuição original. Como objetivo, essa última técnica leva a um número menor de atributos a serem apresentados nos resultados finais das técnicas de mineração de dados, facilitando, então, o entendimento dos padrões encontrados. A redução em número de tuplas pode ser obtida através do uso de histograma em que, de modo geral, são criados grupos de valores do atributo de interesse e os dados, então, dispostos nesses grupos, como ilustrado na Figura 3. Para reduzir o número de tuplas da base de dados são usadas também técnicas estatísticas de amostragem ou ainda a agregação de valores. Por exemplo, em uma base de dados que mantém o histórico de vendas por dia, essas vendas são agregadas em vendas por ano e a análise usa, então, somente esse último resultado.

2.3

Mineração de Padrões Frequentes e Regras de Associação

Em muitas aplicações deseja-se saber o quão frequente dois ou mais objetos aparecem em conjunto (ZAKI; JR., 2014). Considere por exemplo um website que mantém o histórico de páginas acessadas no servidor. Dado o histórico, o administrador do website gostaria de saber se existem conjuntos de páginas que são acessadas com mais

Capítulo 2. Fundamentação Teórica

10

Figura 3 – Uso de histograma na redução de dados

Fonte: Própria

frequência para avaliar o padrão de navegação de seus usuários. Outro exemplo, e o mais famoso na literatura, é o caso do carrinho de compras1 em que são analisados as compras feitas por clientes em um supermercado e, através do uso de técnicas de mineração de padrões frequentes é possível observar, por exemplo, que em 90% das compras em que os itens pão e manteiga aparecem, o item leite também está presente. Com essa informação, o gerente do supermercado pode, por exemplo, colocar esses três itens próximos uns aos outros para maior comodidade do cliente. Os padrões encontrados na base de dados são representados da seguinte forma: {p˜ ao, manteiga} ⇒ leite [suporte = 15%, confiança = 90%]

(1)

Em que o suporte e confiança medem o interesse da regra. Um suporte de 15% nos diz que em 15% de todas as transações analisadas, os itens pão, manteiga e leite aparecem juntos enquanto a confiança de 90% nos diz que em 90% das compras em que pão, manteiga estão juntos, o item leite também é comprado.

2.3.1

Formalização dos Conceitos Envolvidos

Seja I = {i1 , i2 , ..., id } o conjunto de todos os itens disponíveis na base de dados e T = {t1 , t2 , ..., tN } o conjunto de todas as transações de forma que ti contém um subconjunto de I de tamanho k denominado conjunto-k ou k-itemsets, essa última denominação usada no presente trabalho, devida a maior adoção na literatura nacional e estrangeira Sejam A e B subconjuntos não vazios de I. Uma regra de associação é uma implicação do tipo A ⇒ B com suporte e confiança tais que:

1

market baskets

suporte(A ⇒ B) = P (A ∪ B)

(2)

confiança(A ⇒ B) = P (A|B)

(3)

Capítulo 2. Fundamentação Teórica

11

A mineração de padrões frequentes e de regras de associação, é um processo de duas fases. Na primeira fase é a busca por todos os itemsets frequentes que satisfaçam o valor de suporte mínimo preestabelecido. Em um segundo momento, deve-se gerar todas as regras de associação chamadas regras fortes, isto é, que satisfaçam os valores de suporte e confiança mínimos conhecidos previamente. A procura por todos os itemsets frequentes torna-se um problema devido a quantidade enorme de subconjuntos de itens que cresce com complexidade fatorial. Por exemplo, um itemset de tamanho 100,

= 100 1-itemsets frequentes: {a1 }, {a2 }, ..., {a100 }; 100 {a1 , a2 , ..., a100 }, contém 100 1 2 2-itemsets frequentes: {a1 , a2 }, {a1 , a3 }, ..., {a99 , a100 }; e assim por diante. No total, o número de itemsets frequentes é:       100 100 100 + + ... + = 2100 − 1 ≈ 1.27 × 1030 . (4) 1 2 100

2.3.2

Algoritmo Apriori

Para superar o problema de analisar grandes quantidades de combinações de itemsets na geração de itemsets frequentes, o algoritmo Apriori utiliza um princípio (chamado princípio de Apriori) que diz que “se um itemset é frequente, então todos os seus subconjuntos devem também ser frequentes”(TAN et al., 2005, p. 333, tradução nossa, itálico nosso.) É fácil perceber que, por exemplo, se o conjunto A = {a, b, c} é um itemset frequente, então toda transação que contém o conjunto A deve, necessariamente, conter os subconjuntos {a, b}, {a, c}, {b, c}, {a}, {b} e {c}, tornando-os, assim, frequentes também. De maneira análoga, se um sub-itemset é não frequente, então, seus superitemsets são, também, não frequentes. Com essa propriedade, é possível descartar da análise itemsets que não sejam frequentes levando também em consideração a definição de monotonicidade que, segundo Tan et al. (2005, p.334), dado um conjunto de itens I e o conjunto J de todas as combinações possíveis dos elementos de I, a medida f é monótona se: ∀X, Y ∈ J : (X ⊆ Y ) → f (X) ≤ f (Y ) (5) Isto é, para todo subconjunto de Y, a medida f (X) (em nosso contexto, a medida de suporte do conjunto X) não deve exceder a medida f (Y ). Vejamos o exemplo da Figura 4. Na primeira iteração são gerados todos os 1itemsets frequentes, {a}, {b}, {c}, {d} e {e}. Na segunda iteração são buscadas todas os candidatos a 2-itemsets, isto é, todas as transações que contêm uma combinação dois a dois dos 1-itemsets encontrados na iteração anterior. Ainda na segunda iteração, durante a fase de geração de itemsets frequentes, é verificado que o itemset {a, b} não é frequente, ou seja, não satisfazem os valores de suporte e confiança mínimos. Dessa forma, podemos descartar todo e qualquer itemset que contenha o elemento {a, b} pois tal itemset deve ser, necessariamente, um superconjunto de {a, b} e, como {a, b} não é frequente, seus superconjuntos são, também, não frequentes.

Capítulo 2. Fundamentação Teórica

12

Figura 4 – Conceito de monotonicidade

Fonte: Adaptado de Tan et al. (2005, p.335)

O algoritmo funciona da seguinte maneira: primeiro o conjunto de todos os 1itemsets são armazenados em C1 , juntamente com suas respectivas medidas de suporte. O conjunto L1 armazena todos os itens de C1 considerados frequentes, isto é, que têm o suporte maior do que o mínimo exigido. No próximo passo, o conjunto L1 é usado para encontrar o conjunto de 2-itemsets frequentes L2 , e assim por diante, até que não seja mais possível encontrar o conjunto de k-itemsets (conjunto vazio). O processo de encontrar Lk para k ≥ 2 se dá em dois passos, o passo de junção e o passo de poda, explicitados no exemplo a seguir. Considere o conjunto de transações da Tabela 1 e o suporte mínimo requerido igual a 2. A representação esquemática de cada iteração do algoritmo está ilustrada na Figura 5. Na primeira iteração é feita a busca pelos 1-itemsets e suas respectivas medidas de suporte para a construção do conjunto de candidatos a itemsets frequentes C1 e feita a poda dos elementos que não atingem o suporte mínimo estipulado de 2. Nesse exemplo, nenhum elemento é podado na primeira iteração. Na segunda iteração, em um primeiro momento, é feita a junção dos elementos de L1 consigo mesmo, isto é, L1 × L1 , para a construção dos candidatos a 2-itemsets C2 Logo após, são filtrados os elementos de C2 que não atingem o suporte mínimo para a construção de L2 . Na terceira iteração é feita a junção de L2 com L2 para a produção de C3 , que resultaria em C3 = {{I1, I2, I3}, {I1, I2, I5}, {I1, I3, I5}, {I2, I3, I4}, {I2, I3, I5}, {I2, I4, I5}}. Porém, uma vez que os subconjuntos {I1, I4}, {I3, I4}, {I3, I5} e {I4, I5} foram podados por não atingirem o suporte mínimo, nenhum superconjunto que contenha

Capítulo 2. Fundamentação Teórica

13

Tabela 1 – Conjunto de transações. TID Lista de itens T100 I1, I2, I5 T200 I2, I4 T300 I2, I3 T400 I1, I2, I4 T500 I1, I3 T600 I2, I3 T700 I1, I3 T800 I1, I2, I3, I5 T900 I1, I2, I3 Fonte: Adaptado de Han et al. (2011, p.250)

Figura 5 – Representação dos passos do algoritmo Apriori

Fonte: Adaptado de Han et al. (2011, p.251)

esses subconjuntos podados será também um itemset frequente. C3 , então, torna-se {{I1, I2, I3}, {I1, I2, I5}} (aplicação do princípio Apriori). A quarta iteração geraria C4 = {{I1, I2, I3, I5}}. Porém, o itemset {I2, I3, I5} não é frequente (não está presente em L3 ) sendo assim podado para C4 = ∅, dando término ao algoritmo.

Capítulo 2. Fundamentação Teórica

2.3.3

14

Métodos de Avaliação de Padrões

A maioria dos algoritmos de mineração de padrões usa as medidas de suporte e confiança como critério de avaliação das regras de associação. Porém, ao minerar bases de dados grandes na busca de padrões frequentes pode-se ter como resultado um conjunto muito grande de regras de associação, especialmente quando usamos um suporte baixo. Nem sempre as medidas de suporte e confiança serão o bastante para definir se uma regra é útil (chamada também de regra forte) —aquela que satisfaz o suporte e confiança mínimos —ou inútil. Para se ter mais informação à respeito do quão interessante é uma regra de associação podemos usar medidas de correlação, de forma que uma regra de associação passa, agora, a ser: {A} ⇒ B [suporte, confiança, correlação]

(6)

Podem ser usadas medidas de correlação como: • χ2 =

P (observado−esperado)2

• lift(A, B) =

esperado P (A∪B) P (A)P (B)

Ou ainda: • all confidence dado por all conf(A, B) =

suporte(A∪B) ; max{suporte(A),suporte(B)}

• max confidence em que, max conf(A, B) = max{P (A|B), P (B|A)}; • medida de Kulczynski definida como Kulc(A, B) = 12 (P (A|B) + P (B|A)). Essa última sendo recomendada por Han et al. (2011, p.271).

2.4

Classificação

Classificação é a tarefa de, através de um modelo, designar objetos a uma categoria predefinida. Por exemplo, identificar se um e-mail é considerado spam ou legítimo, diagnosticar se um conjunto de células é benignas ou não a partir de uma tomografia, dentre outros. Formalmente, “classificação é a tarefa de definir uma função objetivo f que mapeia cada conjunto de atributos x para uma das classes predefinidas”(TAN et al., 2005, p. 146, tradução nossa.). Expandindo essa definição, o conjunto de atributos pode conter qualquer tipo de valores, contínuos ou discretos, enquanto o atributo classe deve ser, necessariamente, discreto. É isso que distingue o processo de classificação

Capítulo 2. Fundamentação Teórica

15

Figura 6 – Representação do processo de classificação

Fonte: Adaptado de Tan et al. (2005, p.146)

da conhecida regressão, em que a saída da função objetivo é mapeada para um valor contínuo. A definição original está ilustrada na Figura 6. Em geral, técnicas de mineração de dados que envolvem classificação são executadas em dois grandes passos: construção de um modelo de classificação, ou ainda, o passo de aprendizado, e o passo de classificação, em que o modelo construído é usado para predizer a classe dos dados de entrada. A fase de aprendizado, também chamada de fase de treino, é dada pela análise de uma amostra da base de dados em que cada tupla X é representada pelo vetor de atributos de dimensão n X = (x1 , x2 , ..., xn ) e o atributo classe já é previamente conhecido. Essas tuplas são então chamadas de tuplas de treinamento, ou conjunto de treinamento. Pelo fato de que as classes das tuplas de treinamento já serem conhecidas no início do processo de treinamento, esse tipo de aprendizado é chamado de “aprendizado supervisionado” ao contrário do processo de Agrupamento estudado na seção Seção 2.5, em que o aprendizado é dado de maneira não supervisionada e cujo único dado conhecido previamente é o número de grupos desejado no fim do processo de mineração. A segunda fase, a fase de classificação, é onde o modelo construído será usado para predizer a classe dos novos dados. Primeiro é feita uma predição do quão preciso o modelo é, usando outro conjunto de tuplas, distinto do conjunto de treinamento, cujas classes são conhecidas, conjunto esse chamado de conjunto de teste. Se faz necessário o uso de outro conjunto devido a possibilidade de ocorrer o overfitting, situação em que o modelo se torna muito bom para prever as classes do conjunto de treinamento porém não tão preciso para outro conjunto de dados. A medida da precisão do modelo se dá calculando a porcentagem de acertos em relação ao número de predições que o modelo obteve para o conjunto de teste.

Capítulo 2. Fundamentação Teórica

2.4.1

16

Indução por Árvore de Decisão

Uma árvore de decisão é um modelo de classificação construído na forma de um fluxograma em que os nós internos dessa árvore representam condições enquanto os nós folhas representam o valor do atributo classe ao que estamos tentando enquadrar as tuplas. Árvores de decisão são populares uma vez que não envolvem conhecimento específico do domínio dos dados, tornando-as ideais para a descoberta exploratória de conhecimento, além de contarem com o fato de que sua representação é, em geral, simples e de fácil entendimento, como mostra a Figura 7. Na literatura os três métodos Figura 7 – Exemplo de uma árvore de decisão para a classificação de animais entre mamíferos e não mamíferos.

Fonte: Adaptado de Tan et al. (2005, p.151)

de construção de árvores de decisão mais estabelecidos são os algoritmos ID3, Iterative Dichotomiser, concebido por J. Ross Quinlan entre 1970 e 1980 e expandido por E. B. Hunt, J. Marin e P. T. Stone, seu sucessor C4.5, proposto por Quinlan, considerado o algoritmo de benchmark no ramo de classificação e, por fim, CART proposto por um conjunto de estatísticos L. Breiman, J. Friedman, R. Olshen e C. Stone e publicado em (BREIMAN et al., 1984). Seja Dt o conjunto de todas as tuplas de treinamento associadas ao nó t e y = {y1 , y2 , ..., yc } o conjunto das diferentes classes possíveis. A construção recursiva de uma árvore de decisão, em alto nível, consiste nos seguintes passos:

Capítulo 2. Fundamentação Teórica

17

• Passo 1: Se todas as tuplas em Dt pertencem a uma mesma classe então o nó t se torna um nó folha cuja classe tem o valor yt . • Passo 2: Se Dt contém tuplas que pertencem a classes diferentes então é chamado um método de separação que irá determinar qual atributo (atributo de divisão) melhor classifica as tuplas de Dt , bem como o valor que as divide em grupos (ponto de divisão). Um nó é criado para cada saída do método de separação e as tuplas de Dt são distribuídas de acordo com o atributo e o ponto de divisão. O algoritmo é, então, chamado recursivamente para cada nó criado. O algoritmo um pouco mais detalhado está representado em Algoritmo 1. Algoritmo 1: Algoritmo para a construção de uma árvore de decisão para o conjunto de registros D GeraArvoreDecisao(D, lista_atributos, metodo_separacao) Input: Partição de dados D, o conjunto de todos os atributos candidatos lista_atributos, método de separação metodo_separacao Output: Uma árvore de decisão crie um nó N ; if tuplas em D são todas da mesma classe, C then return N como um nó folha cuja classe é C; end if lista_atributos está vazia then return N como um nó folha cuja classe é a classe da maioria dos elementos de D; end criterio_separacao ← execute metodo_separacao(D, lista_atributos); atribui ao nó N o critério de separacao criterio_separacao; if atributo_separacao é discreto e divisões múltiplas são permitidas then lista_atributos ← lista_atributos − atributo_separacao; end foreach saída j de criterio_separacao do D_j ← conjunto de tuplas de D que satisfazem o critério j; if D_j é vazio then adicione um nó folha em N com a classe da maioria das tuplas em D; end else adicione a N o nó retornado por GeraArvoreDecisao(D_j, lista_atributos); end end return N ; Podemos notar que um ponto crucial na criação de uma árvore de decisão é o parâmetro, aqui denominado metodo_separacao, que tem a função de nos informar o atributo que melhor separa as tuplas de D em grupos, ou partições, que idealmente pertençam à mesma classe. No caso de o atributo de separação, provido pelo método

Capítulo 2. Fundamentação Teórica

18

de separação, ser contínuo ou a árvore de decisão restrita a ser binária, o método de separação deve, também, nos informar o ponto de separação ou os subconjuntos de separação. Dado o conjunto de atributos A, os possíveis cenários de partição estão ilustrados na Figura 8. Figura 8 – Exemplo de partições possíveis no método de separação de uma árvore de decisão.

Fonte: Adaptado de Han et al. (2011, p.334)

Um atributo é considerado melhor ou pior no critério de separação de acordo com algumas medidas como o ganho de informação ou o índice Gini. O ganho de informação usa o conceito de entropia, que representa a quantidade média de informação necessária para se classificar uma tupla pertencente ao conjunto D. Seja pi a probabilidade de uma tupla, pertencente ao conjunto D, ser da classe Ci . A entropia de D é calculada da seguinte forma: c X Info(D) = − pi log2 (pi ). (7) i=1

A quantidade de informação necessária para se classificar as tuplas de D em grupos puros, isto é, grupos cujos elementos pertencem a somente uma classe, é calculada da seguinte forma: v X |Dj | InfoA (D) = × Info(D). (8) |D| j=1 O ganho de informação é, finalmente, a diferença entre a quantidade de informação requerida para se classificar D e a quantidade de informação requerida para se classificar D após o particionamento pelo atributo A: Ganho(A) = Info(D) − InfoA (D).

(9)

Capítulo 2. Fundamentação Teórica

19

Ao usar o ganho de informação como medida de separação durante a construção da árvore de indução deseja-se que em cada nó seja escolhido o atributo A que oferece o maior valor de Ganho(A). O índice Gini é calculado de forma similar, porém diz respeito a quão impuro um conjunto D é. Entenda-se por impuro o conjunto que contém tuplas pertencentes a mais de uma classe. Dado o conjunto D e pi a probabilidade de uma tupla pi , pertencente a esse grupo, ser da classe Ci , o índice Gini é definido por: Gini(D) = 1 −

m X

p2i ,

(10)

i=1

O índice Gini considera a separação binária para cada atributo, isto é, para o atributo A, a regra de separação será do tipo A ∈ SA , dessa forma, para cada atributo com v valores diferentes, existem 2v combinações diferentes de subgrupos possíveis. Por exemplo, o atributo salário, que possui 3 valores possíveis {baixo, medio, alto} os possíveis subgrupos são, {baixo, medio, alto}, {baixo, medio}, {baixo, alto}, {medio, alto}, {baixo}, {medio}, {alto} e {}. Os conjuntos {baixo, medio, alto} e {} são desconsiderados por não trazer nenhuma classificação útil, temos um total de (2v − 2)/2 maneiras possíveis de se obter duas partições de D. O índice Gini então é calculado de acordo com a Equação (11). GiniA (D) =

|D1 | |D2 | Gini(D1 ) + Gini(D2 ). |D| |D|

(11)

Quando usado na construção de uma árvore de decisão, é desejado que se escolha o atributo A cujo índice Gini seja mínimo, uma vez que representa a “impureza” das partições realizadas. Quando o atributo a ser considerado na separação é um atributo de valor contínuo, primeiro os valores são ordenados de forma crescente2 e então o ponto de separação considerado é o ponto intermediário entre dois valores contínuos, isto é: ai + ai+1 2

(12)

Dessa forma, para o atributo A que contenha v valores distintos serão considerados v − 1 pontos de separação. Essa regra para lidar com atributos contínuos é válida para ambas as medidas Ganho de Informação e índice Gini. Construída a árvore de decisão, muitos ramos da árvore refletem anomalias do conjunto de treinamento devido a ruído ou outliers. Por isso, é feita a poda da árvore de decisão. Na Figura 9, vemos um exemplo de poda de árvore de decisão. A subárvore que começa no nó representado por A3 ? é podada e assume o valor Classe B. 2

A ordenação é requerida por motivos de desempenho, uma vez que com o conjunto ordenado é preciso somente uma leitura do conjunto D para determinar o ponto de separação.

Capítulo 2. Fundamentação Teórica

20

Figura 9 – Exemplo de árvore de decisão antes e depois da poda

Fonte: Adaptado de Han et al. (2011, p.345)

É possível realizar a poda de duas formas. Uma abordagem faz a predição se um ramo deve ou não ser criado, interrompendo um nó de se ramificar caso os subgrupos destinados à essa subárvore não satisfaçam alguma medida de interesse (Ganho de Informação, índice Gini, dentre outros) preestabelecidos. A dificuldade nessa abordagem se encontra em determinar bons valores para essas medidas de interesse. Uma segunda abordagem é podar a árvore de decisão após a sua construção, “[...] a qual requere maior custo computacional porém, em geral, leva a uma árvore de decisão mais confiável” Han et al. (2011, p.346, tradução nossa).

2.4.2

Avaliação do Modelo de Classificação

Com um modelo de classificação construído não raro deseja-se estimar o quão próximo da realidade esse modelo está, em outras palavras, o quão preciso o modelo criado será na classificação de novas tuplas. Pode-se, ainda, querer comparar diferentes métodos de classificação, requerendo assim métricas que descrevam a precisão do modelo criado. Para esse fim, consideremos as seguintes definições: • TP: Número de tuplas positivas, isto é, tuplas que pertençam à classe de interesse (exemplo portadores_cancer = sim); • TN: Número de tuplas negativas, aquelas que não pertencem à classe de interesse; • PV: Número de positivos verdadeiros, aqueles corretamente classificados como positivos;

Capítulo 2. Fundamentação Teórica

21

• NV: Número de negativos verdadeiros, aqueles corretamente classificados como negativos; • FP: Número de falsos positivos, aqueles erroneamente classificados como positivos; • FN: Número de falsos negativos, aqueles erroneamente classificados como negativos. A exatidão de um modelo de classificação, isto é, a porcentagem de tuplas corretamente classificadas, também conhecida pelo nome de taxa de reconhecimento, é calculada por: TP + TN (13) exatidão = P +N Nem sempre a taxa de reconhecimento nos dará uma boa descrição do comportamento do modelo de classificação. Tomando, por exemplo, problemas em que as tuplas não são uniformemente distribuídas em todas as classes, como detecção de fraudes, em que somente uma minoria se enquadra na classe positiva de fraude, ou ainda, problemas de diagnóstico médico, em que um número pequeno será diagnosticado com a doença em relação ao universo de amostras. Nesses casos, uma taxa de reconhecimento de, por exemplo, 97% pode parecer bastante satisfatória. Mas, e se somente 3% das amostras realmente tinha a doença (amostras positivas) e o modelo não as previu corretamente enquanto que previu 100% das amostras negativas? Para esses casos, há outras métricas que visam diminuir essa falta de informação, como a sensibilidade e a especificidade, definidas por: TP sensibilidade = (14) P TN . (15) N Ainda, é possível calcular a precisão de um modelo de classificação, bem como sua revocação: TP precisão = (16) TP + FP especificidade =

TP . (17) TP + FN Ainda assim, uma medida de precisão perfeita de 1.0 obtida pelo modelo sobre a classe C, nos diz que todas as tuplas que o modelo previu como classe C eram, de fato, da classe C. Porém, não nos diz nada a respeito das tuplas que eram da classe C e o modelo previu as classificou em outra classe. Da mesma forma, a revocação perfeita de 1.0 somente nos informa que todas as tuplas que eram da classe C foram classificadas como tal porém, não nos informa sobre quantas outras tuplas, que não pertencem a classe revocação =

Capítulo 2. Fundamentação Teórica

22

C, foram classificadas nessa classe. Para juntar essas duas medidas em uma só, foram desenvolvidas as medidas F e Fβ , definidas por: 2 × precisão × revocação precisão + revocação

(18)

(1 + β 2 ) × precisão × revocação . β 2 × precisão + revocação

(19)

F =

Fβ =

A medida F é, segundo Han et al. (2011, p.369), a média harmônica entre a precisão e a revocação. E as medidas de Fβ mais comumente usadas são a F2 que dá duas vezes mais importância para a revocação do que a precisão e a F0.5 que dá peso duas vezes maior à precisão em relação a revocação.

2.5

Agrupamento

Agrupar é a atividade de formar grupos em que os elementos de um grupo têm alta semelhança entre si e pouca semelhança com os elementos que estão fora do grupo. Isto é, agrupar é maximizar a similaridade intergrupal e minimizar a similaridade intragrupal. Diferentemente da classificação, no agrupamento a classe da tupla analisada não é conhecida previamente e será, então, descoberta ao fim do processo de agrupamento. É com frequência chamada de classificação automática e na área de machine learning é conhecida ainda, como aprendizado não supervisionado, que “aprende” por observação enquanto que a classificação é conhecida como uma forma de aprendizado supervisionado, dada por exemplos (HAN et al., 2011, p.445).

2.5.1

Requisitos e Características

Na mineração de dados o desafio tem sido o tratamento eficiente e escalável de grandes bases de dados bem como a efetividade de métodos para agrupar formas complexas (não convexas), agrupar objetos com um alto número de atributos e, por fim, agrupar objetos com tipos de atributos variados como nominais, numéricos, binários dentre outros, ao mesmo tempo. Nessa área, são levantados os seguintes requisitos para algoritmos de agrupamento: • Escalabilidade: a maioria dos métodos de agrupamento lida bem com conjuntos de algumas centenas de objetos; porém, bases de dados com milhões ou até bilhões de objetos não são mais incomuns no mercado. Por isso, é essencial que se preocupe com a escalabilidade de tais métodos.

Capítulo 2. Fundamentação Teórica

23

• Habilidade para agrupar diferentes tipos de dados: alguns métodos de agrupamento são projetados especificamente para tratar somente um tipo de dados, seja ele numérico, binário, etc. No entanto, o caso mais frequente é quando temos elementos com os mais variados atributos e queremos classificá-los levando-os em consideração ao mesmo tempo. Mais recentemente, são estudados métodos para agrupar estruturas ainda mais complexas como grafos, imagens, sequências, entre outros. • Agrupar formas não convexas: em sua maioria, algoritmos de agrupamento usam medidas de similaridade entre os objetos calculadas em um espaço euclidiano e, assim, tendem a formar grupos cuja forma é esférica. Porém, em alguns casos, agrupamentos esféricos não são adequados ao problema que se quer resolver como, por exemplo, em detecção de caracteres de variadas formas em uma imagem. • Minimizar o conhecimento do domínio: ainda que as técnicas de agrupamento sejam conhecidas como uma forma de aprendizado automático, se faz necessário algum conhecimento sobre os dados para que se possa definir, por exemplo, o número de grupos as quais se deseja agrupar os objetos. Esse conhecimento prévio é visto como uma desvantagem e há alguns métodos que visam sua eliminação. • Robustez: com frequência os algoritmos de agrupamento usam medidas de tendência central e, por isso, se tornam susceptíveis à valores discrepantes ou faltantes. Minimizar essa susceptibilidade é um foco de algumas técnicas de agrupamento. • Cálculo incremental: por tratar de grandes bases de dados, reagrupar os objetos a todo instante em que um objeto for inserido, modificado ou removido da base se torna muito custoso e algumas técnicas visam o cálculo dos agrupamentos de uma forma incremental. • Lidar com número alto de atributos: em mineração de documentos como páginas Web, por exemplo, um objeto de dados muitas vezes contém um vetor de atributos esparso, com muitos zeros, levando a resultados de agrupamentos de baixa qualidade. Assim, se faz necessário o estudo de algoritmos específicos para esses casos. Além dos aspectos observados acima, podemos ainda analisar os algoritmos de agrupamento em relação as seguintes características: • Critério de partição: particionar os elementos de tal forma que todos os grupos estejam no mesmo nível hierárquico, por exemplo, designar grupos de clientes para diferentes gerentes, ou formar grupos e subgrupos hierárquicos; por exemplo,

Capítulo 2. Fundamentação Teórica

24

em mineração de páginas Web podemos dividi-las em páginas de esporte, ciência, etc. e as páginas de esporte, por sua vez, divididas em páginas de futebol, basquete, entre outros. • Separação dos grupos: podem ser mutuamente exclusivas, em que os elementos pertencem a um, e somente um, grupo ou os agrupamentos podem ter sobreposições. • Medida de similaridade: grupos são formados calculando-se a distância entre os objetos em um dado espaço geométrico (o caso mais comum é o espaço euclidiano), porém existem algoritmos que adotam outro tipo de medida de similaridade, baseados em densidade ou bayesiano. • Espaço dos atributos: muitas vezes, em objetos com um número alto de atributos, apenas uma porção desses atributos é de fato relevante para o agrupamento. Alguns algoritmos restringem o espaço de atributos utilizados, analisando somente parte do objeto.

2.5.2

Classificação dos Métodos de Agrupamento

Podemos ainda classificar os métodos de agrupamento em métodos de particionamento, hierárquicos e baseado em densidade. • Métodos de Particionamento: dado um conjunto de N objetos, os algoritmos dessa classe dividem o conjunto em k grupos, com k ≤ N, dispostos em um mesmo nível hierárquico e, em geral, são mutuamente exclusivos (essa última restrição algumas vezes é relaxada para um particionamento fuzzy). Partem de um número k de partições iniciais e tentam melhorar os agrupamentos usando a técnica de realocação iterativa, em que os elementos são realocados de grupo em grupo e as medidas de similaridade recalculadas até que um ótimo local seja encontrado (uma vez que o ótimo global seria computacionalmente impeditivo de ser calculado devido ao grande número de combinações entre os elementos).Alguns algoritmos dessa classe são o k-means, k-medoide e PAM (Partitioning Around Medeoids) • Métodos hierárquicos: constroem estruturas do tipo árvore com os agrupamentos formados, sendo que essa construção pode ser divisiva, top-down, em que um grande grupo é formado e então dividido diversas vezes até que se satisfaça uma função objetivo, ou aglomerativa, bottom-up, diversos grupos, mais especializados, são formados e baseando-se na similaridade com os demais é feita a junção entre eles até que se satisfaça uma função objetivo. Sofrem do fato de que uma vez que um grupo é formado ou dividido, essa decisão não pode ser desfeita. Tal decisão é em geral tomada para tentar diminuir o custo computacional de se

Capítulo 2. Fundamentação Teórica

25

calcular as medidas de similaridade entre os grupos. Na literatura consultada, os algoritmos hierárquicos mais discutidos são o AGNES (AGlomerative NESting), DIANA (DIvisive ANAlysis) e o BIRCH (Multiphase Hierarchical Clustering); • Métodos Baseados em Densidade: os métodos de particionamento e hierárquicos, dados o seu uso baseado em distâncias euclidianas, somente podem encontrar grupos de forma esférica e, sendo assim, não são aplicáveis para alguns problemas do mundo real. Métodos baseados em Densidade superam essa limitação calculando a similaridade não mais baseado na distância entre os objetos mas usando os conceitos de densidade de acessibilidade e densidade de conectividade. Exemplos de algoritmos baseados em densidade são o DBSCAN (Density-Based Clustering Based on Connect Regions with High Density), o OPTICS (Ordering Points to Identify the Clustering Structure) e o DENCLUE (Clustering Based on Density Distribution Funcions).

2.5.3

Métodos de Particionamento

Os métodos de particionamento são as formas mais simples e fundamentais dentre os métodos de agrupamento. Têm como parâmetros de entrada um conjunto de tuplas D de tamanho n, k, o número de agrupamentos a serem descobertos e, por fim, o algoritmo de particionamento. Os agrupamentos são formados com o objetivo de maximizar a similaridade entre os objetos internos e minimizar a similaridade entre objetos de grupos distintos. Seja o conjunto de tuplas D contendo n objetos em um espaço Euclidiano, métodos de particionamento devem distribuir esses objetos em k agrupamentos3 C1 , ..., Ck em que Ci ⊂ D e Ci ∩ Cj = ∅ para (i ≤ i, j ≤ k). Uma função objetivo é usada para se medir a qualidade do particionamento de tal forma que maximize a similaridade intragrupal e minimize a intergrupal. Uma possível abordagem para métodos de particionamento é baseada no conceito de que um grupo é representado por um único elemento denominado centroide e a medida de qualidade desse agrupamento é dada por: E=

k X X

dist(p, ci )2

(20)

i=1 p∈Ci

Em que p representa o ponto no espaço do objeto p, ci o ponto no espaço do centroide de Ci , ou ainda, a representação de Ci e dist(p, ci ) a distância espacial entre dois pontos p e ci . Dessa forma, a Equação (20) tem E como a soma dos quadrados dos erros entre todos os objetos presentes no agrupamento Ci e seu centroide Ci . 3

Conhecidos na literatura por clusters.

Capítulo 2. Fundamentação Teórica

26

Essa abordagem é extremamente custosa computacionalmente uma vez que enumerar todos os agrupamentos possíveis em D e calcular sua similaridade é mostrado ser um problema NP-difícil de complexidade O(ndk+1 log n) para k agrupamentos de dimensão (número de atributos) d e n objetos (HAN et al., 2011, p. 452). Uma heurística possível para esse problema de particionamento é a chamada k-means. O método k-means, representado pelo Algoritmo 2, escolhe aleatoriamente k objetos do conjunto D e, agora, o centroide do agrupamento Ci passa a ser a média dos objetos contidos em Ci . Os objetos restantes em D são designados para o agrupamento cuja distância entre o objeto e o centroide é mínima. Uma vez que os grupos estão formados, o algoritmo calcula novamente a média para cada grupo e seus objetos são rearranjados de acordo com a nova média calculada. O algoritmo para quando os agrupamentos permanecem estáveis, isto é, os novos agrupamentos são os mesmos em relação aos agrupamentos da iteração anterior. Como exemplo, temos a Figura 10 em que, no quadro a), temos o grupo inicial, cujos centroides foram são escolhidos aleatoriamente, já no quadro b) são recalculados os centroides para cada agrupamento e os elementos rearranjados de acordo com sua similaridade em relação aos novos centroides e, por fim, no quadro c), os agrupamentos ficam estáveis, isto é, não mudam mais, caracterizando o critério de parada para o algoritmo. Algoritmo 2: Algoritmo k-means. Input: Conjunto de dados contendo n objetos D, k número de agrupamentos desejados Output: Um conjunto de k agrupamentos escolha aleatoriamente k objetos de D para representar os centróides iniciais; repeat distribua os objetos de acordo com as médias dos objetos e dos agrupamentos; atualize a média de cada grupo; until até que não haja mudança;

Figura 10 – Exemplo do funcionamento do método k-means.

Fonte: Adaptado de Han et al. (2011, p.453)

Capítulo 2. Fundamentação Teórica

27

O método k-means não garante a convergência global, isto é, não garante que os agrupamentos formados são os melhores possíveis e só pode ser aplicado quando a médias dos atributos dos objetos podem ser calculadas. No caso em que os objetos tenham atributos nominais, é possível utilizar o método k-modas em que ao invés da média é usada a moda para o cálculo de similaridade. O método k-means não é recomendado na descoberta de agrupamentos de tamanhos muito discrepantes ou não convexos e é sensível à presença de outliers por utilizar medidas de tendência central.

2.5.4

Avaliando os Métodos de Agrupamento

Com os agrupamentos construídos, não raro desejamos medir a qualidade dos agrupamentos ou, ainda, comparar diferentes técnicas de agrupamentos. Para esse fim, se faz necessário analisar três aspectos importantes: • Tendência de agrupamento: Dado um conjunto de dados se é pertinente medir se existe uma estrutura não aleatória presente nos dados, ou seja, aplicando-se métodos para encontrar agrupamentos nesse conjunto de dados resultará em grupos não aleatórios; • Determinar o número de agrupamentos para um conjunto de dados: Apesar de alguns métodos de agrupamento, como o k-means por exemplo, requererem o número de agrupamentos como parâmetro inicial, deseja-se saber que número representa um bom número de agrupamentos a serem encontrados; • Medidas de qualidade do agrupamento: Muitas vezes é possível confrontar os agrupamentos atingidos com agrupamentos conhecidos ou, caso não exista tais agrupamentos, são usados métodos chamados métodos intrínsecos, que medem, basicamente, o quão separados são os agrupamentos uns dos outros; Para se calcular a tendência de agrupamento pode-se utilizar a Estatística de Hopkins, que mede o quão aleatória uma variável é distribuída no espaço, definida da seguinte forma: 1. Retire n amostras p1 , ..., pn de do conjunto de dados D e encontre o vizinho mais próximo de pi em D, tal que: xi = minv∈D {dist(pi , v)}.

(21)

2. Retire n amostras q1 , ..., qn e para cada qi encontre o vizinho mais próximo em D − qi , tal que: yi = minv∈D,v6=qi {dist(qi , v)}. (22)

Capítulo 2. Fundamentação Teórica

28

3. A estatística de Hopkins é, então: Pn

yi i=1 P n i=1 xi + i=1

H = Pn

yi

.

(23)

P P Se D for uniformemente distribuído então, ni=1 xi será próximo de ni=1 yi e, assim, H será aproximadamente 0,5. Porém, a distribuição de D seja bastante irregular P P então, ni=1 yi tende a ser substancialmente menor que ni=1 xi e H, dessa forma, próximo de 0. Essa informação é útil de maneira que estatística de Hopkins pode ser usada como limiar calculada para diferentes agrupamentos, em que um valor de H > 0, 5 indica que o conjunto D tem agrupamentos estatisticamente desinteressantes, uma vez que H > 0, 5 representa grande uniformidade dos objetos de D. Em relação ao aspecto de estimar um bom número de agrupamentos, Han et al. (2011, p.486) discute o uso de uma regra simples, obtida experimentalmente, que p nos diz para usar k = n2 para um conjunto de dados que tenha n objetos. Assim, é √ esperado que cada agrupamento contenha 2n elementos.

29

3 Trabalhos Relacionados

O Portal da Transparência tem sido explorado por diversos autores com os objetivos mais variados como a análise da governança, detecção de anomalias, entre outros. O Portal foi lançado em 2004 e, desde 2008, a Controladoria Geral da União, através do órgão Observatório da Despesa Pública, vem estudando os gastos dos Cartões de Pagamento do Governo Federal, os chamados cartões corporativos. Em um trabalho publicado em 2009 (SILVA et al., 2009) aplicou-se técnicas de Mineração de Dados (em específico, mineração de regras de associação) e foram encontrados, dentre um total de 155 regras de associação, gastos com aluguel de carro para viagens pessoais e outras irregularidades. Em um artigo publicado em 2011, pesquisadores da CGU, descrevem o emprego de Mineração de Dados na detecção de cartéis em licitações públicas (SILVA; RALHA, 2010) utilizando agentes de mineração em um sistema multiagente. A dificuldade em se encontrar grupos de empresas suspeitos de praticar cartéis reside em dois pontos chave: analisar as diversas combinações possíveis entre empresas envolvidas em licitações se torna computacionalmente impraticável e, muitas vezes, a atuação de cartéis extrapola o escopo de apenas um órgão da Administração Pública Federal. Os dados analisados no trabalho citado acima, são provenientes de um outro portal de dados governamentais abertos chamado Compras Governamentais (MPOG (Ministério do Planejamento, Orçamento e Gestão), 2014) em que são disponibilizados os dados de licitações públicas. Ainda nesse artigo, os autores modelaram os dados em uma matriz em que uma linha corresponderia a uma licitação, cada coluna à um fornecedor e o valor do item aij , dessa matriz, um atributo booleano e assumindo verdadeiro caso a empresa j tenha participado da licitação i. Os autores, então, usaram duas abordagens na mineração das regras de associação. No primeiro momento, o algoritmo Apriori (Subseção 2.3.2) foi aplicado sobre toda a base de dados. A segunda abordagem emprega algoritmos de agrupamento para primeiro agrupar fornecedores que atuem em conjunto e, então, aplicar o algoritmo Apriori em cada grupo descoberto para encontrar as regras de associação. Os grupos encontrados estão ilustrados na Figura 11, em que estão agrupadas as unidades federais nas quais grupos de fornecedores atuam conjuntamente. A segunda abordagem se mostrou mais apropriada uma vez que, em geral, os cartéis acontecem em grupos regionais e dificilmente têm abrangência nacional, segundo especialistas da CGU. Ao fim do trabalho, diversas regras de associação davam indícios de práticas irregulares como rodízio de licitações e simulação de concorrência, por exemplo.

Capítulo 3. Trabalhos Relacionados

30

Figura 11 – Agrupamentos das unidades federais

Fonte: Silva e Ralha (2010, p.11) No ano de 2008, uma empresa ganhou nove licitações em um mesmo órgão, concorrendo com outra empresa que não ganhou nenhuma das licitações em que ambas participaram. O detalhe é que as nove licitações perdidas pela segunda empresa foram exatamente as únicas licitações da base de dados em que ela participou. O total de vitórias da primeira empresa na base de dados era de apenas 12, mostrando que não se tratava de um grande fornecedor. Segundo o especialista, essa regra aponta fortes características de cartelização e simulação de concorrência. (SILVA; RALHA, 2010, p.16).

Em uma outra regra descoberta, foram apontados três fornecedores que participaram conjuntamente de 22 licitações. No entanto, cada um desses fornecedores já haviam participado em mais de 100 licitações, ou seja, tratavam-se apenas de grandes fornecedores que, por coincidência, participaram de algumas licitações em conjunto. Podemos perceber que a descoberta de conhecimento no processo de MD depende fortemente do conhecimento do domínio do problema. De outra forma, a interpretação dos dados se dá de forma errônea e pode produzir conclusões que não refletem a realidade. Em um trabalho publicado em 2009 (CARVALHO et al., 2009) os autores exploram a importância do KDD no processo de compras governamentais. No trabalho, foram analisados dados relativos ao período de 2004 a 2008 do Portal ComprasNet (atual ComprasGovernamentais) e foram encontrados alguns padrões que vão contra os princípios relativos às compras governamentais como: • Realização de aquisições por dispensa de licitação de um mesmo fornecedor destacando-se a inexistência de competitividade, favorecimento de fornecedores e direcionamento de resultados;

Capítulo 3. Trabalhos Relacionados

31

• Realização de aquisições por dispensa de licitação de um mesmo material várias vezes em um mesmo ano indicando o fracionamento de licitações; Observando os trabalhos citados, podemos compreender melhor a importância da análise detalhada dos dados disponibilizados no Portal da Transparência. Devido ao grande número de dados, a aplicação de métodos da Mineração de Dados torna-se atraente no sentido de que são projetados tendo em vista a performance ao lidar com grandes bases de dados.

32

4 Metodologia

O presente capítulo apresenta como foi feita a coleta e análise descritiva dos dados e o uso dos algoritmos escolhidos nas áreas de mineração de regras de relacionamento, classificação por árvore de decisão e agrupamento. Em cada área citada descrevemos também a fase de pré-processamento necessária para a execução dos experimentos.

4.1

Delineamento da Pesquisa

Para executar o trabalho selecionamos uma técnica de cada área (citada acima) tendo como critério a sua simplicidade e aplicabilidade no meio acadêmico. Para a área de mineração de regras de relacionamento o algoritmo escolhido foi o Apriori, na área de classificação escolhemos o algoritmo C4.5 e, por fim, na área de agrupamento escolhemos o K-Means. Os resultados são, então, analisados e discutidos no Capítulo 5.

4.2

Coleta de Dados

A coleta de dados é feita através do download dos arquivos disponíveis no portal da transparência1 . Os arquivos estão organizados por categorias e ano de exercício que, por sua vez, está divididos em meses. Decidimos estreitar nossa pesquisa nos dados referentes aos de Gastos Diretos. Escolhemos também trabalhar com os dados referentes ao ano de 2013 (13648631 registros) por julgarmos que os dados coletados durante um ano seriam suficientes para o desenvolvimento do trabalho. Devido às restrições de tempo para a apresentação do trabalho, optamos por utilizar os dados do período de Janeiro de 2013 (626.147 registros) na execução do presente trabalho e na análise preliminar dos resultados. Portanto, todos os dados analisados são referentes ao arquivo 201301_GastosDiretos.csv.

4.3

Pré-processamento e Análise Descritiva dos Dados

Em um primeiro momento é desejável que tenhamos informações à respeito da base de dados estudada. Informações como, por exemplo: estão todos os atributos preenchidos? Quais são os valores máximo e mínimo que cada coluna pode assumir? 1

Os dados do presente trabalho foram encontrados na URL

Capítulo 4. Metodologia

33

No caso de um atributo numérico, quais são as principais medidas estatísticas, valor mínimo, valor máximo e média? Os dados sobre gastos diretos estão dispostos em arquivos no formato CSV, comma separated value, contendo 25 colunas, sendo elas: Código Órgão Superior, Nome Órgão Superior, Código Órgão Subordinado, Nome Órgão Subordinado, Código Unidade Gestora, Nome Unidade Gestora, Código Grupo Despesa, Nome Grupo Despesa, Código Elemento Despesa, Nome Elemento Despesa, Código Função, Nome Função, Código Subfunção, Nome Subfunção, Código Programa, Nome Programa, Código Ação, Nome Ação, Linguagem Cidadã, Código Favorecido, Nome Favorecido, Número Documento, Gestão Pagamento, Data Pagamento e Valor Pagamento. Para mais informações sobre o significado de cada coluna, vide Apêndice A. Na pré-análise dos arquivos, nos deparamos com dois problemas. O primeiro foi a dificuldade de leitura da base original pois os arquivos usam a codificação de texto WINDOWS-1252 e a representação de caracteres especiais como letras acentuadas, por exemplo, ficava prejudicada ou, até mesmo, causava erros na execução de alguns scripts. O outro problema encontrado foi a presença de dois caracteres especiais —\r ( carriage return ) e o caractere nulo \000 —que também ocasionavam erro no resultado final dos scripts utilizados. Para resolver esses problemas foram utilizados os seguintes comandos: • LC_ALL=C tr -d "[\000\r]" < base/201301_GastosDiretos.csv > base/201301_GastosDiretos_sem_char_especiais.csv

• iconv -f WINDOWS-1252 -t UTF-8 201301_GastosDiretos.csv > 201301_GastosDiretos_utf.csv O primeiro retira os caracteres especiais do arquivo original, criando um segundo arquivo chamado 201301_GastosDiretos_sem_char_especiais.csv. Nesse arquivo é usado o comando iconv para transformar sua codificação original WINDOWS1252 para a codificação UTF-8 gerando, assim, um terceiro arquivo chamado de 201301_GastosDiretos_sem_char_especiais_utf.csv. Para saber se os atributos estavam completos, isto é, se havia algum valor em cada coluna do arquivo, geramos, para cada coluna, uma matriz associativa cujo índice do elemento dessa matriz representa o valor encontrado na coluna e o elemento representa a frequência daquele valor. Com isso fomos capazes de encontrar as colunas que continham o valor “vazio” e sua frequência, isto é, quantos registros estavam com essa determinada coluna vazia. Por fim, a completude de cada coluna foi então calculada

Capítulo 4. Metodologia

34

usando a equação: Completude = 1 −

Frequência de valores vazios × 100 Número de registros

(24)

A Tabela 2 contém o resumo das métricas calculadas para os dados categóricos, todos do tipo textual. Para os dados não categóricos, Data Pagamento e Valor Pagamento, além de calcular a completude e a média (somente para o campo Valor ), extraímos os valores máximo e mínimo que cada atributo assumiu. O resumo dessas métricas está contido na Tabela 3. Diversas análises podem ser feitas com base nessas Tabela 2 – Resumo das métricas descritivas para os dados categóricos dos gastos diretos de janeiro de 2013. Coluna

Nome da coluna

Moda

1 2 3

Código Órgão Superior Nome Órgão Superior Código Orgão Subordinado

4

Nome Orgão Subordinado

5

Código Unidade Gestora

6

Nome Unidade Gestora

7 8 9 10 11 12 13 14 15

Código Grupo Despesa Nome Grupo Despesa Código Elemento Despesa Nome Elemento Despesa Código Função Nome Função Código Subfunção Nome Subfunção Código Programa

16

Nome Programa

17 18 19 20

Código Ação Nome Ação Linguagem Cidadã Código Favorecido

26000 MINISTÉRIO DA EDUCAÇÃO 26291 FUND.COORD.DE APERF.DE PESSOAL NIVEL SUPERIOR 154003 FUND.COORD.DE APERF.DE PESSOAL NIVEL SUPERIOR 3 Outras Despesas Correntes 18 Auxílio Financeiro a Estudantes 12 Educação 364 Ensino Superior 2032 Educação Superior - Graduação, Pós-Graduação, Ensino, Pesquisa e Extensão 487 Concessão de Bolsas de Estudos Bolsas de Estudos no País 00000000000191 BANCO DO BRASIL SA [DIRECAO GERAL] 2013OB800192 15279 07/01/2013

21

Nome Favorecido

22 23 24

Número Documento Gestão Pagamento Data Pagamento

Frequência da moda 381.746 381.746 125.072

Completude 100% 100% 100%

125.072

100%

125.072

100%

125.072

100%

593.909 593.909 241.477 241.477 359.566 359.566 198.079 198.079 197.618

100% 100% 100% 100% 100% 100% 100% 100% 100%

197.618

100%

79.215 79.215 79.215 2.443

100% 100% 26,36% 100%

2.443

100%

27.222 74.021 63.385

100% 100% 100%

Fonte: Própria

Tabela 3 – Resumo das métricas descritivas para os dados não categóricos dos gastos diretos de janeiro de 2013. Coluna 24 25

Nome da coluna Data Pagamento Valor Pagamento

Média N.A.2 R$ 21.005,27

Máximo 31/01/2013 R$ 100.000.000,00

Mínimo 02/01/2013 R$ 0,01

Completude 100% 100%

Fonte: Própria

tabelas. Por exemplo, da Tabela 2 vemos que o Ministério da Educação tem frequência 2

Não se aplica

Capítulo 4. Metodologia

35

de 381.746, isto é, está presente em 60,97% de todos os pagamentos referentes ao mês de Janeiro de 2013, lembrando que o referido período possui 626.147 registros. Um outro ponto interessante a se observar na mesma tabela é a completude da coluna 19, Linguagem Cidadã. A completude representa o número relativo de registros (linhas no arquivo) que continham alguma informação na respectiva coluna. Nesse caso, podemos observar que somente 26,36% dos registros (aproximadamente 105 mil registros) tinham o atributo Linguagem Cidadã, o que não representou prejuízo para a nossa análise, visto que a coluna 19 é apenas uma descrição mais amigável do programa governamental envolvido no pagamento. Da Tabela 3 podemos observar que os pagamentos começaram no dia 02 de Janeiro, sendo que o menor valor pago foi 1 centavo e o maior valor foi R$100 milhões. Repetimos o mesmo processo novamente porém, dessa vez, analisamos os dados do ano de 2013 inteiro. Os resultados obtidos foram similares em relação a Janeiro como pode ser visto na Tabela 4, para dados categóricos, e na Tabela 5, para dados não categóricos. Tabela 4 – Resumo das métricas descritivas para os dados categóricos dos gastos diretos de 2013. Coluna

Nome da coluna

Moda

1 2 3

Código Órgão Superior Nome Órgão Superior Código Orgão Subordinado

4

Nome Orgão Subordinado

5

Código Unidade Gestora

6

Nome Unidade Gestora

7 8 9 10 11 12 13 14 15

Código Grupo Despesa Nome Grupo Despesa Código Elemento Despesa Nome Elemento Despesa Código Função Nome Função Código Subfunção Nome Subfunção Código Programa

16

Nome Programa

17

Código Ação

18

Nome Ação

19 20

Linguagem Cidadã Código Favorecido

21

Nome Favorecido

22 23 24

Número Documento Gestão Pagamento Data Pagamento

26000 MINISTÉRIO DA EDUCAÇÃO 26291 FUND.COORD.DE APERF.DE PESSOAL NIVEL SUPERIOR 154003 FUND.COORD.DE APERF.DE PESSOAL NIVEL SUPERIOR 3 Outras Despesas Correntes 18 Auxílio Financeiro a Estudantes 12 Educação 364 Ensino Superior 2032 Educação Superior - Graduação, Pós-Graduação, Ensino, Pesquisa e Extensão 20RK Funcionamento de Instituições Federais de Ensino Superior Bolsas de Estudos no País 00000000000191 BANCO DO BRASIL SA [DIRECAO GERAL] 2013OB809649 00001 14/11/2013

Fonte: Própria 3

Não se aplica

Frequência da moda 7.627.434 7.627.434 1.525.804

Completude 100% 100% 100%

1.525.804

100%

1.525.804

100%

1.525.804

100%

13.126.668 13.126.668 5.968.579 5.968.579 7.308.947 7.308.947 4.249.374 4.249.374 4.245.549

100% 100% 100% 100% 100% 100% 100% 100% 100%

4.245.549

100%

1.664.765

100%

1.664.765

100%

79.215 130.442

26,36% 100%

130.442

100%

37.228 3.087.724 375.047

100% 100% 100%

Capítulo 4. Metodologia

36

Tabela 5 – Resumo das métricas descritivas para os dados não categóricos dos gastos diretos de 2013. Coluna 24 25

Nome da coluna Data Pagamento Valor Pagamento

Média N.A.3 R$ 400,00

Máximo 31/01/2013 R$ 400.000.000.000,00

Mínimo 02/01/2013 R$ 0,01

Completude 100% 100%

Fonte: Própria

Apesar de similares, alguns pontos chamam a atenção. A completude da coluna 19, Linguagem Cidadã, se manteve exatamente a mesma para Janeiro de 2013 e também para o ano inteiro, indicando que há uma proporção que foi respeitada entre pagamentos que têm o campo 19 preenchido e os pagamentos que não o tem. Outro ponto interessante é o valor máximo pago pelo governo federal, passando de aproximadamente R$ 100 milhões para R$ 400 bilhões, elevando a média de valores pagos de R$ 21 mil para R$ 165 mil, aproximadamente.

4.4

Aplicação e Funcionamento do Programa Apriori

Na área de mineração de padrões frequentes, decidimos usar o algoritmo Apriori devido à sua relativa simplicidade de entendimento quando comparado aos demais algoritmos de mineração de padrões frequentes e também devido ao fato de ser um algoritmo já consolidado, pois foi criado em 1994 e ainda hoje é utilizado como benchmark na área (GILLMEISTER; CAZELLA, 2007). A implementação do algoritmo escolhida foi a feita por Christian Borgelt por fazer parte de programas de mineração de dados bem estabelecidos no mercado como, por exemplo, o Clementine da IBM e também pela boa documentação4 oferecida que inclui, dentre outras coisas, o pseudocódigo do algoritmo Apriori e uma explicação geral sobre mineração de regras de associação. Na página do autor5 é possível encontrar os códigos fonte bem como os executáveis, para as plataformas UNIX e Windows. O programa implementado por Borgelt espera um arquivo de entrada em que cada linha representa uma transação (tupla). As linhas são separadas por um caractere delimitador (no nosso caso tab) e cada elemento representa o valor de um atributo. Abaixo, um exemplo de entrada no formato esperado: pão manteiga leite pão leite manteiga leite maçã ... ... ... 4 5

A documentação pode ser encontrada em Página de download do programa Apriori implementado por Christian Borgelt

Capítulo 4. Metodologia

37

O programa gera como saída um arquivo com as regras de associação encontradas (quando usada a opção -tr) da seguinte forma: A