MONOGRAFIA - Universidade dos Açores

UNIVERSIDADE DOS AÇORES
-DEPARTAMENTO DE MATEMÁTICAMONOGRAFIA
“Métodos Estatísticos e de I.O. utilizados em Sistemas de
Apoio à Decisão (SAD’s)”
Aluna:
Tânia Cristina de Lima Fernandes
2002/2003
Índice
INTRODUÇÃO ........................................................................................................................3
CAPÍTULO I ............................................................................................................................5
1.1. Breve história dos SAD’s: .................................................................................................5
1.2. O problema da definição: .................................................................................................7
1.3. Campos de aplicação:........................................................................................................8
1.4. Técnicas estatísticas e de IO usadas em SAD’s:..............................................................9
CAPÍTULO II .........................................................................................................................13
2.1. Definição ...........................................................................................................................13
2.2. Abordagens ......................................................................................................................15
2.3. Técnicas de estatística e IO .............................................................................................16
CAPÍTULO III .......................................................................................................................23
3.1. Análise Exploratória de Dados.......................................................................................23
3.2. OLAP (On-line Analytic Processing).............................................................................23
3.3. Séries temporais e técnicas de previsão:........................................................................25
CAPÍTULO IV........................................................................................................................31
4.1. Definição:..........................................................................................................................31
4.2. Como se constroem?........................................................................................................32
4.3. Algoritmos ........................................................................................................................33
4.4. Exemplo ............................................................................................................................35
CAPÍTULO V .........................................................................................................................37
CONCLUSÃO.........................................................................................................................39
GLOSSÁRIO ..........................................................................................................................40
BIBLIOGRAFIA REFERENCIADA ...................................................................................41
BIBLIOGRAFIA CONSULTADA .......................................................................................43
ANEXO I .................................................................................................................................45
ANEXO II................................................................................................................................46
II.1. CHAID.............................................................................................................................46
II.2. CART...............................................................................................................................47
II.3. QUEST ............................................................................................................................48
ANEXO III ..............................................................................................................................50
Monografia
Introdução
Devido à rápida evolução da tecnologia, cada vez mais dados relativos a transações
comerciais, hábitos de consumo, exames médicos, clima, e outros tipos de registo estão a ser
acumulados por empresas e organizações em geral. Este manancial de informação, quando
aproveitado de forma eficaz, desempenha um papel fundamental no sucesso dessas empresas
e organizações, afinal vivemos numa sociedade tecnológica onde a informação acumulada é
muito valiosa. Já não é uma novidade a divulgação de vendas de bases de dados como forma
de aumentar o activo das empresas.
Assim, num mundo onde a rapidez e eficácia da tomada de decisão determina a vida ou
a morte de uma empresa, torna-se cada vez mais necessário o recurso a tecnologias como os
Sistemas de Apoio à Decisão. Estes sistemas, têm como objectivo último a melhoria da
eficiência do processo de tomada de decisão através da fusão da intuição e experiência
humanas com um sistema informático. Desde a sua criação, os Sistemas de Apoio à Decisão
têm se revelado de grande utilidade em campos como a Economia, a Agricultura, a Medicina
e outros. Pelo facto de utilizarem técnicas e algoritmos de Estatística e Investigação
Operacional no tratamento e análise dos dados em que se baseiam as decisões considerou-se
interessante a realização de um levantamento de algumas das mais utilizadas. O resultado é
apresentado neste trabalho. Aprofundou-se o estudo das técnicas que se revelaram de maior
interesse: o Data Mining, o On-Line Analytical Processing (OLAP) e as Árvores de Decisão
ou Classificação.
Este trabalho está estruturado nma Introdução, cinco capítulos e conclusão. No primeiro
capítulo apresentam-se uma definição de Sistema de Apoio à Decisão e os resultados da
recolha efectuada. No Capítulo II exploram-se algumas das técnicas de Data Mining. No
Capítulo III desenvolvem-se os métodos associados ao OLAP. O Capítulo IV aborda
sucintamente as Árvores de Decisão ou Classificação. Adicionou-se ainda um quinto capítulo
onde se referem alguns dos softwares mais utilizados na aplicação das três ferramentas
estudadas a um conjunto de dados e é realizada uma breve análise de alguns.
Pág. 3
Monografia
Pág. 4
Monografia
Capítulo I
Este capítulo tem por objectivo introduzir o conceito de Sistema de Apoio à Decisão, a
que a partir de agora chamaremos apenas SAD, referir os campos de conhecimento em que
estes são usados como ferramenta de trabalho e apresentar o resultado da recolha de técnicas
estatísticas e de Investigação Operacional que neles são utilizadas.
Comecemos por fazer uma breve análise da evolução dos SAD’s, desde o seu
surgimento até à actualidade.
1.1. Breve história dos SAD’s:
O conceito de apoio à decisão surgiu a partir de estudos teóricos sobre a tomada de
decisão em organizações e trabalho técnico em sistemas informáticos interactivos, realizados
nas décadas de 1950 e 60, no Carnegie Institute of Technology e no MIT.
Só a partir de meados da década de 1960 se tornou viável o desenvolvimento de
sistemas de informação em grande escala, pois a capacidade de armazenamento de dados em
computadores aumentara com a construção de mainframes mais poderosos. Assim, surgiram
sistemas de gestão de informação (MIS – Management Information Systems) que se
destinavam a fornecer aos gestores de grandes companhias relatórios periódicos, estruturados,
baseados em dados contabilísticos.
Durante a década de 1970 foram editados livros e um conjunto de artigos que
estabeleceram as bases teóricas deste campo de pesquisa. Em 1974, Gordon Davis definiu
Management Information System como um sistema integrado com o objectivo de
“providenciar informação para apoiar as operações, gestão e tomada de decisão numa
organização” [POWE02a]. Em 1975, J.D.C. Little desenvolveu um SAD, a que chamou
Brandaid, com o objectivo de auxiliar a tomada de decisões nas várias fases de lançamento de
um produto [POWE02a]. Nessa década, surgiram os sistemas de apoio à decisão para
executivos (EIS – Executive Information Systems), sistemas informáticos criados para
satisfazer as necessidades de informação dos executivos, proporcionando-lhes acesso rápido a
dados actualizados e a relatórios de gestão, possuindo ainda ferramentas de comunicação,
burótica e de análise.
Pág. 5
Monografia
No final da década, tinham sido já desenvolvidos diversos sistemas de informação
interactivos que ajudavam a resolução de problemas semi-estruturados, com base em dados e
modelos, e que eram designados Sistemas de Apoio à Decisão. Já se reconhecia a capacidade
dos SAD’s de trabalhar com dados espaciais, multidimensionais, documentos, apoiar
operações, gestão financeira e tomada de decisões estratégicas. Utilizavam-se diversos
modelos e técnicas nos SAD’s, inclusive optimização e simulação.
Na década de 1980, pesquisadores desenvolveram software para o apoio à decisão em
grupos (GDSS – Group Decision Support Systems). Os EIS evoluíram de SAD’s construídos
para um só utilizador e orientados por modelos para, com o desenvolvimento de Data
Warehouses1 e On-Line Analytical Processing2 (OLAP), passarem a integrar uma categoria
mais alargada de SAD’s orientados para os dados.
Nos anos 90, surgiu o conceito de Business Intelligence (BI), que resultou da tentativa
de ligar informações de vendas com dados recolhidos por scanner através de um SAD. “BI
descreve um conjunto de conceitos e métodos para melhorar a tomada de decisão
empresarial através da utilização de sistemas de apoio baseados em dados” [POWE02a] que
são SAD’s orientados para os dados. Com a evolução das tecnologias os mainframes foram
substituídos por servidores com menor volume e maiores capacidades. Surgiram novas
ferramentas de OLAP que foram integradas em SAD’s. Em meados da década, com a
popularização da World Wide Web, abriu-se uma nova dimensão de pesquisa, nomeadamente,
o desenvolvimento de SAD’s baseados neste novo ambiente de trabalho.
O quadro seguinte sumaria a evolução do conceito de SAD ao longo das últimas décadas:
1
2
Ver definição na página 8.
Ver definição na página 7.
Pág. 6
Monografia
Evolução dos SAD’s
1960
MIS e relatórios
estruturados
Pesquisa em sistemas
interactivos
Desenvolvimento
teórico
1970
1980
1990
Brandaid
1ª Bibliografia
Data Warehouses
MDS
GDSS
OLAP
EIS
RDBMS
Data Mining
Expert systems
Tabela 1: Evolução dos SAD’s (Adaptado de [POWE02b], p.2).
Esta é apenas uma síntese da curta história dos SAD’s, pois com a acelerada evolução
das tecnologias este é um campo em constante mutação.
1.2. O problema da definição:
Devido à rápida evolução tecnológica que ocorreu nas últimas décadas, ainda não existe
um consenso entre os diversos especialistas relativamente à definição de SAD, por isso,
apresentaremos as que consideramos mais completas:
Segundo Bill Inmon, um SAD é “um sistema usado para apoiar decisões de gestão.
Normalmente envolve a análise de muitas unidades de dados de uma forma heurística. Como
regra, o processamento por um SAD não envolve a actualização de dados” [INMO99].
Por outro lado, Henry Lucas afirma que um “SAD é um sistema baseado em computador
que auxilia o processo de tomada de decisão utilizando dados e problemas não estruturados”
[CHAV01].
Podemos assim definir SAD através da síntese das duas definições anteriores, ou seja,
como sistemas informáticos interactivos que auxiliam o processo de tomada de decisão,
relativamente a problemas semi estruturados (mal estruturados ou ainda não estruturados),
através da análise de grandes quantidades de dados. É necessário ter em conta que auxiliar o
processo de tomada de decisão significa mais do que fornecer informação, envolve também
Pág. 7
Monografia
“analisar alternativas, propor soluções, pesquisar o histórico das decisões tomadas, simular
situações, etc.”[CHAV01].
Os SAD’s, quando implementados na forma de software, possuem, em geral, a seguinte
estrutura:
Interface com
o utilizador
Sistema Gestor de
Bases de Dados
Ferramentas
para
tratamento e
gestão de
dados
Sistema Gestor da
Base de Modelos
Dados
externos
Modelos
estratégicos
Modelos tácticos
Dados
internos
Modelos
operacionais
Funções e
subrotinas para
construção de
modelos
Figura 1: Arquitectura de um SAD
A Base de Dados contém a informação em que se baseará a decisão (dados externos e
internos) e ferramentas para gerir e tratar os dados. A Base de Modelos guarda os modelos a
aplicar (estratégicos, tácticos e operacionais) de acordo com o tipo de decisão a tomar,
possuindo ferramentas para gerar modelos que se adaptem a situações novas. O SGBD é o
Sistema Gestor da Base de Dados e o SGBM o Sistema Gestor da Base de Modelos. A ligação
ao utilizador é feita através de uma interface que liga os diversos módulos e facilita as tarefas
de introdução dos dados e apresentação de resultados.
1.3. Campos de aplicação:
As capacidades dos SAD’s enquanto ferramenta de trabalho são amplamente
reconhecidas em diversos campos do conhecimento.
Pág. 8
Monografia
Na actualidade já existem inúmeras aplicações dos SAD’s sendo impossível referi-las
todas. Assim, mencionamos apenas alguns exemplos representativos da diversidade da sua
utilização.
Por exemplo, na gestão empresarial, nas áreas de contabilidade, finanças (planeamento
de dívida, avaliação e investimento imobiliários, planeamento financeiro de pequenas
empresas, etc.), gestão de recursos humanos, marketing, gestão de produção, etc. Na
educação, na governação (planeamento ambiental, desenvolvimento da política económica
nacional), na saúde (distribuição de recursos em organizações de saúde pública.), no
planeamento urbano (gestão de tráfego, gestão do sistema de recolha de resíduos, etc.).
Na medicina, existem SAD’s especializados no auxílio ao diagnóstico de determinadas
doenças.
1.4. Técnicas estatísticas e de IO usadas em SAD’s:
Através de pesquisa realizada na Internet e em diversas fontes bibliográficas físicas
decidimos estudar neste trabalho as seguintes técnicas e tecnologias utilizadas pelos SAD’s no
desempenho das suas funções:
o Data Mining:
O processo de Data Mining é utilizado nos SAD’s com o objectivo de descobrir
informação relevante que esteja oculta nos dados, “consiste na aplicação de técnicas de
estatística e inteligência artificial em grandes bases de dados, para encontrar tendências ou
padrões a fim de apoiar decisões” [FREI01]. O processo de Data Mining é constituído por
três etapas: exploração inicial, construção de um modelo/identificação de padrões e aplicação
do modelo obtido.
O processo de Data Mining envolve técnicas estatísticas como a análise de clusters,
análise de regressão e estatística descritiva. Uma abordagem aprofundada ao Data Mining
será realizada no próximo capítulo.
Pág. 9
Monografia
o Árvores de decisão ou classificação:
As árvores de decisão são um dos métodos mais utilizados pelos SAD’s no tratamento
dos dados para extracção de informação relevante. Podemos definir uma árvore de decisão
como “uma estrutura de dados recursivamente definida como um nó folha, que indica uma
classe, ou um nó de decisão, que contém um teste sobre o valor de um atributo. Para cada um
dos possíveis valores do atributo, tem-se um ramo para uma outra árvore de decisão
(subárvore). Cada subárvore contém a mesma estrutura de uma árvore.
Árvores de decisão dividem o espaço de descrição do problema em regiões disjuntas,
isto é, um exemplo é classificado por apenas um único ramo da árvore” ([LUCE01], p.2).
Apesar de surgir como uma das ferramentas utilizadas em Data Mining na detecção de
padrões, esta técnica será desenvolvida separadamente no capítulo IV.
o Análise Exploratória de Dados e On-Line Analytical Processing (OLAP):
Uma primeira abordagem ao tratamento da informação disponível para a tomada de
decisão é, muitas vezes, a análise exploratória dos dados utilizando a Estatística. Torna-se
assim possível uma melhor compreensão da informação contida nos dados disponíveis, pois é
mais fácil interpretar relações apresentadas num gráfico, numa tabela de dupla entrada ou em
estatísticas descritivas do que numa folha de cálculo com milhares de entradas.
O OLAP é um conjunto de técnicas informáticas que permitem a análise de tendências
em dados definidos de forma multidimensional, transformando-os em informação útil. É
possível encontrar ferramentas OLAP em diversos sectores de uma organização. Por exemplo,
é possível utilizar esta técnica na análise e previsão do volume de vendas, pesquisa de
mercado, para orçar despesas, etc. Este é outro tema a ser desenvolvido posteriormente.
o Data Warehouses:
Actualmente, os Data Warehouses estão muito em voga enquanto ferramenta de
trabalho e, de acordo com Bill Inmon, são: 3“Um conjunto de estruturas de dados orientados
3
“A subject oriented, integrated, non volatile, time variant collection of data design to support management DSS
needs.” [INMO99].
Pág. 10
Monografia
por assunto, integrados, não voláteis e variáveis no tempo para satisfazer as necessidades de
SAD’s.”[INMO99].
Como os Data Warehouses não são propriamente uma técnica, mas sim uma forma de
organização de dados e não utilizam técnicas de IO e de Estatística, não se enquadram neste
trabalho e por isso são apenas referidos.
o Sistemas de Informação Geográfica (Geographical Information Systems GIS):
Pode considerar-se que um GIS é um sistema de apoio à decisão que é capaz de
“recolher, armazenar, manipular e expor graficamente informação geográfica” ([BAPT01],
p.2) referenciada através de um sistema de coordenadas e que a utiliza na resolução de
problemas. Problemas que podem envolver, por exemplo, encontrar a melhor localização para
um dado serviço público, organizar o tráfego numa cidade, etc.
Os GIS “armazenam informação acerca do mundo real como uma colecção de níveis
temáticos que podem ser interligados através da geografia” ([BAPT01], p.15). Quando se
sobrepõe a informação contida em cada um destes níveis, obtém-se a caracterização da
localização de onde se recolheram os dados. Com os GIS torna-se possível expandir a
construção de mapas e a análise geográfica, permitindo a um maior número de pessoas uma
mais fácil interpretação desse tipo de informação para o apoio à decisão.
Estes sistemas envolvem a utilização de técnicas estatísticas como a amostragem, a
análise multivariada, a análise geoestatística e estatística descritiva, e técnicas de IO como os
algoritmos de caminho mais curto e de fluxo máximo, entre outros.
Este tema não será desenvolvido neste trabalho por ter sido abordado numa monografia
anterior referenciada como [BAPT01].
Pág. 11
Monografia
Pág. 12
Monografia
Capítulo II
Neste capítulo consideraremos, de forma aprofundada, as técnicas de Data Mining. Esta
é uma técnica que se encontra já bastante difundida, sendo possível encontrar no mercado de
software diversas ferramentas para a mineração de bases de dados, por exemplo: Clementine
da SPSS, IBM Intelligent Miner for Data, Statistica Data Miner, entre outros4.
2.1. Definição
Comecemos por definir e descrever as diversas etapas do processo.
No capítulo anterior definimos Data Mining como a “aplicação de técnicas de
estatística e inteligência artificial em grandes bases de dados, para encontrar tendências ou
padrões a fim de apoiar decisões” [FREI01]. Assim, o principal objectivo do Data Mining é
construir um modelo capaz de prever o comportamento de um conjunto de variáveis
envolvidas num determinado problema, a partir de um conjunto de dados conhecido a priori
que facilite a determinação da solução.
O processo de Data Mining é composto por três etapas: a exploração inicial, a
construção, validação e a aplicação do modelo obtido. Vejamos o que acontece em cada uma
delas.
2.1.1. Exploração inicial:
Este é um passo muito importante no processo de Data Mining, pois é nesta fase que
se escolhe a amostra que será trabalhada e as variáveis que interessam estudar. Envolve a
selecção, pré-processamento e limpeza, e transformação dos dados.
o Selecção: nesta fase seleccionam-se ou segmentam-se os dados de acordo com
critérios definidos a priori. Por exemplo, escolhem-se as variáveis relevantes
para a resolução do problema e, de forma aleatória, seleccionam-se os registos
que formarão a amostra.
4
Para mais informações sobre software disponível consultar www.kdnuggets.com .
Pág. 13
Monografia
o Pré-processamento e limpeza: é retirada a informação irrelevante para a
resolução do problema, e também a considerada inutilizável (por conter muitos
valores omissos, dados desactualizados, erros tipográficos e ortográficos).
Reconfiguram-se os dados para assegurar a coerência, pois estes podem ter
origem em formatações diferentes (por exemplo, o valor da variável “sexo”
pode ser representado por m/f ou 1/2). Por vezes realçam-se os dados, já que as
diferenças que neles existem podem conter padrões escondidos (este realce
deve ser realizado com cautela para que não se obtenham padrões falsos, que
não são verdadeiramente apoiados pelos dados).
o Transformação: recuperam-se os dados identificados nas fases anteriores,
estruturando-os em tabelas e ficheiros que serão sujeitos ao Data Mining.
Nesta primeira etapa pode ser apenas necessário escolher estimadores para um modelo
de regressão, ou então realizar uma análise estatística mais aprofundada para determinar quais
as variáveis relevantes e que modelos se devem considerar na fase seguinte.
2.1.2. Construção e validação do modelo
Nesta fase, o objectivo é encontrar o modelo que melhor descreve o conjunto de dados
seleccionado. Este modelo pode ser escolhido de entre os modelos guardados na Base de
Modelos do SAD ou gerado pelas ferramentas incorporadas nesse módulo. Existem dois tipos
de modelos, os descritivos e os preditivos. Um modelo descritivo procura facilitar a
compreensão de comportamentos e processos associados, por exemplo, de clientes. Um
modelo preditivo refere-se a uma equação ou a um conjunto de regras que possibilitam a
previsão de um valor desconhecido (variável dependente) a partir de outros valores
conhecidos (variáveis independentes ou explicativas). Frequentemente, os modelos
construídos têm anomalias causadas por erros nos dados usados nessa construção. A essas
anomalias e erros chamamos ruído. Os modelos utilizados podem estar associados a várias
áreas do conhecimento humano, Matemática, Economia, Ciências Sociais, etc.
A validação do modelo pode ser feita pela comparação dos resultados obtidos com a
sua aplicação a um conjunto de dados com resultados previamente conhecidos, por cálculo do
valor dos desvios ou erros encontrados. Ou então, de uma forma cruzada, utilizando uma parte
da amostra para a construção do modelo e o restante para a validação deste.
Pág. 14
Monografia
2.1.3. Aplicação
O modelo escolhido na fase anterior é aplicado a novos dados para classificá-los ou
para que se possam realizar previsões úteis, isto é, os padrões identificados são transformados
no conhecimento que será usado para apoiar o utilizador no processo de tomada de decisão.
2.2. Abordagens
É possível aplicar o Data Mining aos dados de diversas formas. De acordo com Groth,
existem três: aprendizagem supervisionada (classificação), aprendizagem não supervisionada
(clustering) e visualização ([GROT98], p.4).
Definamos cada uma destas abordagens:
o Aprendizagem supervisionada: o sistema recebe classes definidas pelo
utilizador e exemplos para cada uma, como base para a construção do modelo.
Pretende-se que o sistema encontre “uma descrição de cada classe, isto é, as
propriedades comuns aos exemplos” fornecidos. Após a formulação da
descrição, esta e a classe que lhe corresponde passam a formar uma regra de
classificação “que pode ser usada para classificar objectos até então
desconhecidos” [DILL95].
Exemplificando, consideremos o caso de uma empresa que pretende saber qual o tipo de
clientes que pode perder mais facilmente para os seus competidores. Para obter essa
informação, utilizando a aprendizagem supervisionada no processo de Data Mining, a
empresa aplica-o à sua base de dados históricos, considerando como classes os clientes leais,
versus os clientes que preferiram outras empresas que prestam os mesmos serviços. Obtendo
assim um modelo que será usado para prever quais dos novos clientes lhe serão leais e quais
os que preferirão a concorrência.
o Aprendizagem não supervisionada: o sistema realiza a sua aprendizagem
através da observação e descoberta. São-lhe fornecidos objectos, mas “não são
definidas classes de modo que tem de observar os exemplos e reconhecer
padrões (isto é, descrição da classe) por si mesmo. Este processo resulta num
Pág. 15
Monografia
conjunto de descrições de classes, uma para cada classe descoberta no
ambiente” [DILL95].
Para exemplificar, consideremos agora uma empresa que pretende agrupar a informação
guardada sobre os seus clientes de acordo com as suas similaridades. Esta empresa tem por
objectivo compreender que grupos são o melhor alvo das campanhas publicitárias,
aumentando dessa forma a eficácia da comercialização dos seus produtos. Assim, o processo
de Data Mining, utilizando a aprendizagem não supervisionada, seria aplicado à sua base de
dados obtendo uma segmentação dos seus clientes segundo os padrões detectados pelo
sistema (de acordo com o rendimento mensal, o número de filhos e outras variáveis
semelhantes).
o Visualização: como a palavra indica, refere-se à apresentação gráfica da
informação obtida. No entanto, não se limita necessariamente à apresentação
bidimensional recorrendo a gráficos e mapas. A tecnologia permite adicionarlhes diversas “camadas” de informação, obtendo animações tridimensionais
que realçam dados que normalmente passariam despercebidos.
Por exemplo, é possível combinar um mapa onde estão assinalados os locais em que já
estão implementados negócios e o que se pretende iniciar. Associando-o com informação
referente aos transportes que servem a área e dados relevantes da população alvo é possível
obter uma previsão da localização que melhor serve os objectivos propostos.
2.3. Técnicas de estatística e IO
Entre as técnicas utilizadas no processo de Data Mining encontramos as árvores de
decisão ou classificação, a estatística descritiva, a análise de clusters e a análise de regressão.
Apenas estas duas últimas técnicas serão abordadas neste capítulo, as outras serão
aprofundadas posteriormente.
2.3.1. Análise de clusters:
Esta técnica é usada em Data Mining para “separar o conjunto de dados em
componentes que reflictam um padrão consistente de comportamento” [DILL95]. Está
directamente relacionada com a aprendizagem não supervisionada. Pretende-se que as classes
Pág. 16
Monografia
ou clusters encontrados possuam um mínimo de semelhanças entre si, e que entre os
elementos que constituem cada cluster a semelhança seja máxima. Após esta divisão é
possível usar os clusters obtidos como base para uma análise mais detalhada.
De que forma podemos obter esta segmentação do conjunto de dados? Existem
diversos algoritmos que podemos aplicar, classificados como hierárquicos (aglomeração ou
divisão) e não hierárquicos.
Os algoritmos hierárquicos não exigem o conhecimento antecipado do número de
clusters a formar. Considerando um algoritmo aglomerativo, a divisão em clusters é efectuada
através da formação de pares de observações que possuem uma maior semelhança entre si,
mas que ainda não pertencem ao mesmo cluster, de modo a que estas passem a formar um
novo cluster. Posteriormente unem-se os pares mais próximos obtendo menos grupos e com
maior dimensão. Este processo é repetido iterativamente até que todas as observações estejam
reunidas num só cluster.
Os algoritmos não hierárquicos baseiam-se na obtenção de um número predefinido de
clusters, k, que conterão todos os casos observados. Ou seja, em vez de se combinarem grupos
semelhantes entre si de forma hierárquica, procura-se encontrar os k clusters que melhor
solucionam o problema juntando unidades ao grupo mais próximo.
Na prática, verifica-se que a utilização destes dois tipos de algoritmo varia de acordo
com as características do problema e com os objectivos do utilizador. Os algoritmos não
hierárquicos permitem ao utilizador definir o número de classes a formar e um valor para a
distância mínima entre objectos para que estes pertençam a clusters diferentes. O tempo de
computação é normalmente menor, mas pode variar de acordo com a abordagem, pois a
segmentação pode fazer-se com uma só passagem pelos dados ou com múltiplas passagens
(neste caso, a segmentação é realizada na primeira passagem e nas seguintes alguns objectos
podem ser recolocados em clusters diferentes com o objectivo de melhorar a divisão dos
dados).
No caso dos algoritmos hierárquicos, por se realizarem de forma iterativa e
trabalharem com todos os objectos em cada etapa exigem um poder computacional elevado e
mais tempo para obter a segmentação dos dados.
Pág. 17
Monografia
Vejamos agora quais são algumas das formas mais utilizadas para determinar a
distância entre elementos e entre clusters.
o Comparação entre elementos: esta é realizada através do cálculo de um
coeficiente de proximidade entre pares de elementos do conjunto de dados, D.
Este coeficiente pode ser definido como uma aplicação γ de D×D em ℜ,
simétrica e tal que γ(x,y)≤γ(x,x), se γ avalia uma semelhança e γ(x,y)≥γ(x,x), se
γ avalia uma dissemelhança. Representamos os coeficientes de semelhança por
sij e os de dissemelhança por dij. É calculado a partir de uma matriz n×p, onde
nas n linhas temos os elementos a classificar e nas p colunas temos os seus
atributos. Assim, γ, permite-nos obter uma matriz quadrada, real e simétrica,
onde estão organizados os valores em que nos basearemos para agrupar os
elementos em classes.
Alguns dos coeficientes de proximidade mais utilizados sobre matrizes métricas estão
representados na tabela seguinte:
Quadrado da Distância Euclidiana
d ij2 =
∑ (x
d ij =
Distância de Manhattan
p
v =1
− x
iv
p
∑x
v =1
iv
)
2
jv
− x vj
Tabela 2: Coeficientes de proximidade.
Existem ainda coeficientes definidos sobre matrizes lógicas e sobre matrizes de
frequências, mas não os referiremos.
o Comparação
entre
classes:
é
também
necessário
comparar
a
semelhança/dissemelhança entre os clusters formados em cada iteração do
algoritmo de agrupamento e os elementos que ainda não estão incluídos num
cluster. Um critério de agregação é uma aplicação σ definida de P(X)× P(X),
(onde X é o conjunto a classificar e P(X) o conjunto das partes de X), para ℜ e
Pág. 18
Monografia
tal que σ(C1,C2) é o valor da distância entre os clusters C1 e C2. O objectivo é
minimizar a semelhança entre clusters.
Alguns dos critérios mais comuns são o do vizinho mais próximo, o do centróide e o de
Ward.
O critério do vizinho mais próximo utiliza, para matrizes de semelhança, o
coeficiente de comparação:
Γ (C1 , C 2 ) = min {s ij ( x, y ) : x ∈ C1 ∧ y ∈ C 2 }.
Para matrizes de dissemelhança pretende-se o mínimo dos dij’s.
O critério do centróide considera que a distância entre as classes C1 e C2 é dada
pela distância entre os seus centros de gravidade (centróides) c1 =(c11,...,c1n) e
c2=(c21,...,c2n), onde as coordenadas c1i e c2i são dadas pelas médias dos valores
assumidos pela i-ésima variável para os objectos da classe correspondente.
O critério de Ward procura minimizar a soma dos quadrados (WSS) dentro dos
clusters, estimador da variância intra-grupos, dada pela fórmula:
WSS =
∑ ∑ (x
k
n
j
j =1 i =1
ij
− x
)
2
j
.
Onde i representa o número total de clusters e nj o número de elementos no cluster j.
o Interpretação dos resultados: os resultados obtidos podem ser representados,
entre outras formas, por dendogramas. Um dendograma é uma árvore
hierárquica que permite “visualizar a informação em diferentes níveis de
abstracção” ([KARY], p.1) e representa de uma forma simples a sequência de
fusões sucessivas (no caso aglomerativo) que se verificam com a aplicação de
um algoritmo hierárquico da Tabela 2.
1,0
8,0
6,0
4,0
2,0
0,0
a
b
c
d
e
Figura 2: Exemplo de um dendograma em que são classificados cinco elementos.
Pág. 19
Monografia
Como é possível verificar na Figura 2, no início do dendograma temos os n elementos a
classificar constituindo clusters separados, e no fim estão já agrupados num só cluster. O eixo
vertical
representa
o
coeficiente
de
agrupamento
e
permite-nos
saber
a
que
distância/semelhança se formam os clusters. A escala apresentada na figura refere-se a
dissemelhanças.
É fácil concluir que este tipo de representação gráfica permite uma compreensão mais
imediata da forma como os elementos foram agrupados do que, por exemplo, uma tabela.
2.3.2. Análise de regressão
A análise de regressão é utilizada com o objectivo de quantificar as relações de
casualidade existentes entre duas ou mais variáveis, isto é, inferir como as variações de uma
ou mais variáveis independentes afectam uma variável designada por dependente.
A regressão pode ser efectuada de acordo com vários modelos. Temos, por exemplo, o
modelo linear, que é o mais comum, o exponencial, o polinomial, o curvilíneo e o logístico,
entre outros. Escolhe-se o modelo de regressão considerando o tipo e número de variáveis
com que se está a trabalhar. Veremos apenas como funcionam o modelo linear na sua forma
geral e o logístico, pois estão entre os mais utilizados na prática.
O modelo geral de regressão multilinear assume a seguinte forma:
Y = β 1 + β 2 X 2 + ... + β k X k + ε .
Onde Y é a variável dependente e X2,..., Xk são as variáveis independentes. ε é a variável
aleatória que representa o efeito que as variáveis que não são tidas em conta no modelo
têm sobre o comportamento de Y. β1,..., βk são designados por coeficientes de regressão.
Quando se procura fazer corresponder este modelo aos dados, a maior dificuldade é a
estimação dos valores dos coeficientes de regressão. Normalmente, para obter estimadores
confiáveis para esses coeficientes utiliza-se o método dos mínimos quadrados, que não iremos
aprofundar neste trabalho.
Pág. 20
Monografia
Para determinar a qualidade da regressão utiliza-se o coeficiente de determinação
multilinear, R2, que mede a proporção da variação total de Y que é explicada pela
regressão, isto é, pela influência linear das variáveis X2,...,Xk. R2 varia entre 0 e 1, sendo
que 1 corresponde a uma correlação perfeita e 0 a uma total ausência de correlação entre
as variáveis. R2 é calculado através da fórmula seguinte:
∑ (Y
n
R2 =
i =1
i
) − ∑ (Y
∑ (Y − Y )
−Y
n
2
i =1
n
n
^
i
− Y )2
=1−
2
i =1
i
^
∑ (Y
i
− Y )2
∑ (Y
i
−Y
i =1
n
i =1
.
)
2
Vejamos agora o modelo logístico. Este assume a seguinte forma:
E (Y ) =
.
1
⎡ ⎛
1 + exp ⎢ − ⎜⎜ β 0 +
⎣⎢ ⎝
k
∑β
j =1
j
⎞⎤
X j ⎟⎟ ⎥
⎠ ⎦⎥
Onde Y é a variável dependente, β0 é uma constante, X1,...,Xk são as variáveis
independentes e β1,...,βk são os coeficientes de regressão. É necessário chamar a atenção para
o facto de Y ser uma variável dicotomizada, isto é, só assume os valores 0 e 1.
Como Y ∈ {0,1}, por definição de valor esperado, temos:
E ( Y ) = [0 × P ( Y = 0 ) ] + [1 × P ( Y = 1 ) ] = P ( Y = 1 )
.
Assim, podemos representar este modelo pela equação:
P (Y = 1) =
.
1
⎡ ⎛
1 + exp ⎢ − ⎜⎜ β 0 +
⎢⎣ ⎝
k
∑β
j =1
j
⎞⎤
X j ⎟⎟ ⎥
⎠ ⎥⎦
Por estarmos a trabalhar com uma função de probabilidade, com este modelo, temos
sempre a certeza que os valores previstos estão compreendidos entre 0 e 1.
Trabalhando a equação anterior vem:
β0 +
k
∑β
j =1
j
X
j
⎛
P (Y = 1) ⎞
⎟ ⇔ logit ( P = 1) = β 0 +
= log ⎜⎜ −
P
(
Y = 1) − 1 ⎟⎠
⎝
k
∑β
j =1
j
X
j
,
a forma mais popular para escrever a equação deste modelo, pois torna possível utilizar
a regressão linear para estimar valores para os coeficientes de regressão.
Na tabela seguinte apresentamos as equações de outros modelos de regressão:
Pág. 21
Monografia
Y = β 0 + β 1 X + β 2 X 2 + ... + β k X k + ε
Modelo polinomial
(
Y = exp α + β 1 X + ... + β k X k + ε
Modelo exponencial
)
⎛
⎞
β
β
Y = exp ⎜⎜ α + 1 + ... + k + ε ⎟⎟
X1
Xk
⎝
⎠
Modelo “curva S”
Tabela 3: Modelos de regressão.
Nestes modelos, Y é a variável dependente, α e β0 são constantes, β1,...,βk são
coeficientes de regressão, X é a variável dependente e ε é a variável estocástica que descreve o
efeito de variáveis desconhecidas, ou não consideradas, em Y.
É interessante notar que os algoritmos que implementam estas técnicas baseiam-se de
perto na teoria, como diz Thearling em [THEA], na prática existem poucas diferenças entre
as técnicas de estatística e as técnicas clássicas de Data Mining.
Pág. 22
Monografia
Capítulo III
Consideremos agora de que forma é que a Análise Exploratória de Dados e o OLAP
utilizam técnicas estatísticas e de IO para analisar os dados em que se baseiam as decisões
tomadas com o auxílio de SAD’s.
3.1. Análise Exploratória de Dados
A Análise Exploratória de Dados envolve a aplicação de diversas técnicas estatísticas
(mais ou menos complexas de acordo com as características dos dados e do tipo de
informação que se pretende obter) aos dados, com o objectivo de os transformar em
conhecimento que auxilie o decisor no processo de tomada de decisão.
Uma das ferramentas estatísticas mais simples e que permite a obtenção de resultados
facilmente compreensíveis é a Estatística Descritiva, isto é, o cálculo de médias, medianas,
desvios padrão, etc. Existem ainda técnicas de visualização de dados, como a construção de
histogramas, gráficos de barras, diagramas de quartis, tabelas de frequências e/ou de dupla
entrada, entre outras. A Análise de Regressão e a Análise de Clusters são outras abordagens
(já referidas no capítulo anterior) que permitem a extracção de conhecimento dos dados
considerados relevantes. Os testes estatísticos fornecem uma base para apoiar ou refutar
hipóteses definidas empiricamente.
Assim, podemos dizer que com o uso de técnicas estatísticas bastante simples é possível
rentabilizar os dados disponíveis, sumariando-os, representando graficamente relações entre
variáveis e identificando rapidamente tendências pouco usuais que podem ser significativas
para a resolução do problema em consideração.
3.2. OLAP (On-line Analytic Processing)
O que é OLAP? Quando falamos em OLAP referimo-nos a “um conjunto de tecnologias
projectadas para suportar análise e consultas ad hoc” [INFO98], (ou seja, não é necessário
definir à partida critérios de consulta), que são aplicadas a bases de dados organizadas de uma
forma multidimensional.
Pág. 23
Monografia
A estrutura básica de trabalho em OLAP é o cubo. Este cubo é construído para
armazenar os dados considerados relevantes para a análise. Neste, os dados são medidas
numéricas dependentes de um conjunto de dimensões que lhes fornecem um contexto. Por sua
vez, cada dimensão é descrita através de um conjunto de atributos hierarquizados. Podemos
ainda dizer que cada medida numérica é definida de forma única pelas dimensões que a
contextualizam. Normalmente, um cubo OLAP não contém apenas dados. Nele estão também
programados cálculos simples como a contagem de elementos, totais, médias, desvios padrão,
etc.
Para clarificar este encadeamento de conceitos consideremos, a título de exemplo, um
cubo que armazena dados referentes às vendas de uma empresa. Neste cubo, a informação
está estruturada em três dimensões: Data, Produto e Localização. Estas são definidas à custa
de atributos: para a Data temos a data em que a venda foi efectuada (Ano, Mês, Dia), para o
Produto temos os vários produtos que são vendidos pela empresa (Produto, Modelo) e para a
Localização temos a localização geográfica da filial da empresa onde se realizou a venda
(País, Região, Cidade).
Uma dimensão muito importante num cubo OLAP é o tempo. Muitos dos dados que são
trabalhados por empresas e outras entidades não são de interesse sem o registo da data em que
foram recolhidos. Por isso, é importante que uma ferramenta OLAP tenha um calendário
incorporado, seja capaz de efectuar operações como agregar os dados em períodos de tempo
flexíveis (dia, semana, mês, etc.) e trabalhar com séries temporais.
Em OLAP existem quatro tipos de operações utilizadas na análise dos dados. Se
considerarmos a hierarquia das dimensões podemos falar em drill down e roll up, se
quisermos analisar os dados de vários “pontos de vista”, por exemplo, “rodando” o cubo,
usamos as operações slice e dice.
O drill down refere-se à alteração da visualização dos dados de um menor para um
maior nível de detalhe dimensional. O roll up é o inverso, ou seja, passar de um nível mais
resumido para um menos resumido.
Com a operação slice é possível “cortar” o cubo para que o utilizador possa obter uma
visão mais específica dos dados, por exemplo seccionando o cubo para visualizar os dados de
Pág. 24
Monografia
vendas numa determinada data. Dice serve para rodar o cubo para que os dados possam ser
analisados de uma perspectiva diferente, isto é, segundo um outro valor de um mesmo
atributo ou variável.
3.3. Séries temporais e técnicas de previsão:
Uma série temporal é um conjunto de observações realizadas sequencialmente em
períodos de tempo espaçados regularmente.
Porque são de interesse para os decisores? Porque possibilitam a obtenção de previsões
confiáveis. No entanto, é necessário observar que a previsão só é válida se as condições do
passado se mantiverem no futuro.
Na aproximação clássica ao estudo das séries temporais considera-se que estas são
constituídas por quatro componentes: tendência (Tt), ciclo (Ct), sazonalidade (St) e irregular
ou resíduo (I). Que podem ser definidas como:
⇒ Tendência: uma tendência geral de crescimento ou decrescimento.
⇒ Ciclo: flutuações que se repetem ao longo do tempo. Apresentam um período
superior a um ano. Normalmente relacionam-se com o ciclo económico.
⇒ Sazonalidade: flutuações periódicas, mas de período inferior ou igual a um ano, a
que se chama ciclo sazonal.
⇒ Irregular: representa flutuações aleatórias ou “ruído” resultante de acontecimentos
imprevisíveis, não tendo correlação temporal.
Normalmente, estas componentes são relacionadas, numa abordagem multiplicativa,
através da equação:
y t = Tt Ct S t I .
Onde yt é o valor observado da variável descrita pela série temporal. No modelo clássico
assume-se que qualquer valor observado de yt é o resultado da influência conjunta das quatro
componentes. Esta situação pode ser exemplificada da forma indicada na Figura 3.
Pág. 25
Monografia
Sazonalidade (S)
Irregular (I)
1, 2
0,6
1
0,4
0, 8
0,2
0, 6
0
0, 4
Y=T C S I
-0,2
0, 2
-0,4
0
-0,6
15
10
5
1,5
15
1
0
10
0,5
0
5
-0,5
-1
Realidade
0
-1,5
Ciclo (C)
Tendência (T)
Figura 3: As componentes do modelo clássico multiplicativo (Adaptado de [WEIE98], p.715).
Para que se possam efectuar previsões é necessário separar a série nas suas várias
componentes, o que exige o recurso a um conjunto de métodos adequados às características de
cada componente.
Consideremos duas abordagens ao estudo de séries temporais: técnicas de regressão e
técnicas de alisamento.
3.3.1. Técnicas de regressão
Geralmente, a componente mais importante de uma série temporal é a tendência. Assim,
com a utilização de técnicas de regressão procura-se ajustar uma linha que descreva essa
componente dos dados. Normalmente, utilizam-se os modelos de regressão linear, polinomial
e exponencial (o primeiro no caso linear e os outros no caso não linear). Como já falamos de
análise de regressão no capítulo anterior, vamos apenas acrescentar que, para facilitar os
cálculos, os intervalos temporais são substituídos por números naturais, sendo que o primeiro
intervalo recebe o valor 1, o segundo 2 e assim sucessivamente.
Realizar previsões a partir da equação obtida para a componente tendência é simples,
basta fazer a substituição da variável “tempo” pelo período de tempo para que se pretende a
previsão.
Pág. 26
Monografia
3.3.2. Técnicas de alisamento
As técnicas de alisamento procuram eliminar as componentes irregulares e a
sazonalidade. Entre as várias técnicas existentes vejamos como funcionam duas das mais
utilizadas, a média móvel centrada e o alisamento exponencial.
o Média móvel centrada (MMt): neste caso, pretende-se filtrar de forma sistemática as
irregularidades da série facilitando a análise do seu comportamento a médio e longo
prazo. A série temporal inicial é substituída por outra, onde cada ponto é obtido
através do cálculo da média dos valores assumidos pela série original nos N pontos
centrados no período de tempo pretendido, pois cada ponto corresponde a um período
de tempo.
Se o valor escolhido para N for impar, para obtermos um ponto de ordem i da nova série
escolhemos os N pontos da série original de ordem i-N/2 até i+N/2 e calculamos a média
destes N pontos. O valor da média calculada é o valor do ponto de ordem i da nova série.
Assim:
MM t ( N = 2 n + 1) =
y t − n + ... + y t + ... + y t + n
.
N
Se N for par temos de alterar um pouco o método. Seleccionamos dois grupos de N
elementos da série temporal original, para que os últimos N-1 elementos do primeiro grupo
correspondam aos primeiros N-1 elementos do segundo grupo. Calculamos o valor total das
observações para cada um dos grupos. Em seguida, calculamos a média dos dois totais. Por
fim, dividimos por 4 a média calculada. Ou de forma mais simples, calculamos o valor de:
MM t ( N = 2 n ) =
y t − n / 2 + ... + y t + ... + y t + n / 2
.
N
Obtemos assim o valor do novo elemento da série das médias. A ordem de cada novo
ponto corresponde a um período de tempo presente na série original.
Pág. 27
Monografia
A partir desta nova série é possível obtermos as componentes restantes. A tendência
surge através do uso de técnicas de regressão para o cálculo dos coeficientes a e b na
expressão seguinte:
MM t = (Tt = a + bt ) × ε t ,
onde εt é o desvio entre o modelo e os valores da série.
Para a obtenção das outras componentes utilizamos as seguintes expressões:
Ct =
MM t
yt
= St I .
e
Tt
MM t
No caso da sazonalidade é ainda necessário eliminar a componente irregular e recentrar
a série obtida por:
S' j = S j
D
,
D
∑S
j =1
j
onde D representa o período da sazonalidade.
o Alisamento exponencial: neste método considera-se que cada observação da série
original pode ser escrita à custa de uma constante b e de um εt que quantifica o erro da
observação, ou seja, X t = b + ε t . Considera-se, também, que b não sofre grandes
alterações entre observações, mas que pode variar ao longo do tempo. Assim, com o
objectivo de obter o valor de b, calcula-se, de forma ponderada, um novo valor St a
partir das observações anteriores, onde se atribui um peso menor às mais antigas e
maior às mais recentes. A fórmula utilizada recursivamente é:
S t = αX t + (1 − α ) S t −1 .
Onde, St é o valor alisado exponencialmente, St-1 o valor calculado no período de tempo
anterior, Xt o valor observado e α a constante de alisamento. α varia entre 0 e 1. Se α for 0
todos os novos valores calculados são iguais ao valor calculado inicialmente, S0. Se α for 1 as
observações anteriores são ignoradas. A forma mais simples de calcular o valor de α é
Pág. 28
Monografia
utilizando um método de tentativa e erro, ou seja, pesquisando para valores de α escolhidos
do intervalo [0,1] (por exemplo, de 0,1 a 0,9, com intervalos de amplitude 0,1) qual possui um
erro quadrático médio menor para a diferença entre o valor previsto e o valor observado da
série histórica.
Para prevermos o comportamento futuro da série é necessário alterar um pouco a
equação. Passamos a ter:
Pt +1 = αX t + (1 − α ) Pt −1 .
Onde Pt+1 é a previsão para o próximo período de tempo, Xt é o valor observado no
período de tempo actual e Pt-1 o valor que tinha sido previsto para o período de tempo
anterior. α continua a ser a constante de alisamento, mas agora α=1 significa que se prevê que
os valores do próximo período de tempo sejam iguais ao do actual.
3.3.3. Comparação entre modelos distintos
Quando uma série temporal é explicada segundo dois ou mais modelos diferentes é
necessário verificar qual a melhor alternativa. Dois dos critérios usados com esse objectivo
são a média absoluta dos desvios e o erro quadrático médio.
Segundo o critério da média absoluta dos desvios (MAD), o modelo que melhor
descreve a série temporal é o que tem o menor valor para a expressão:
n
MAD =
∑
t =1
^
xt − xt
.
n
^
Onde xt é o valor observado, x t o valor previsto pelo modelo e n o número de períodos
de tempo considerados.
Pelo critério do erro quadrático médio (RQM), o melhor modelo é aquele que tem o
menor valor para a equação:
2
^
⎞
⎛
⎜ xt − xt ⎟
∑
⎠ .
⎝
RQM = t =1
n
n
Pág. 29
Monografia
Onde cada uma das variáveis tem o mesmo significado que as do critério anterior.
Muito mais poderíamos dizer sobre este assunto, mas neste trabalho limitamo-nos a uma
pequena introdução ao tema.
Pág. 30
Monografia
Capítulo IV
As árvores de classificação e decisão são uma técnica utilizada pelos SAD's na
construção de modelos, na classificação de dados, etc. Neste capítulo veremos o que são, qual
o seu interesse e como construi-las.
4.1. Definição:
O que são árvores de classificação/decisão? No primeiro capítulo deste trabalho
definimo-las como "uma estrutura de dados recursivamente definida como um nó folha, que
indica uma classe, ou um nó de decisão, que contém um teste sobre o valor de um atributo.
Para cada um dos possíveis valores do atributo, tem-se um ramo para uma outra árvore de
decisão (subárvore). Cada subárvore contém a mesma estrutura de uma árvore. Árvores de
decisão dividem o espaço de descrição do problema em regiões disjuntas, isto é, um exemplo
é classificado por apenas um único ramo da árvore" ([LUCE01], p.2). É um método de
classificação supervisionado, onde uma variável dependente é explicada à custa de n variáveis
independentes, normalmente não quantitativas.
As árvores de decisão/classificação podem ser usadas com objectivos diferentes, de
acordo com o problema que se pretende resolver, podemos ter por objectivo classificar os
dados referentes a uma população da forma mais eficiente possível ou descobrir qual é a
estrutura de um determinado tipo de problema, compreender quais as variáveis que afectam a
sua resolução e construir um modelo que o solucione. Com uma árvore de
decisão/classificação é possível escolher as variáveis explicativas que realmente nos
interessam para descrever a situação, deixando de lado as menos relevantes.
Esta é uma técnica que pode ser utilizada em diversos campos, por exemplo: na saúde,
combinando informação recolhida através de inquéritos referentes a dados clínicos para
descobrir quais as variáveis que contribuem para a melhoria do sistema de saúde; na análise
de mercados, verificando quais as variáveis associadas com o volume de vendas (preço,
geografia, características dos consumidores, etc.). Para realizar tarefas deste tipo, as árvores
de decisão/classificação são usadas para identificar as pessoas que pertencem a um
determinado grupo alvo, ou ainda para detectar relações entre variáveis que surjam apenas
num subgrupo, especificando-as num modelo formal.
Pág. 31
Monografia
4.2. Como se constroem?
Uma das formas de obtermos uma árvore de decisão/classificação é partir de uma
amostra da população que se pretende classificar (amostra de treino, A), usando esses dados
para construir um modelo para os restantes. Normalmente, esta é seleccionada de forma
aleatória de entre os dados iniciais, para que não exista um enviesamento do modelo de
classificação obtido.
Assim, suponhamos que a nossa amostra pode ser dividida em K classes e seja C o
conjunto de todas essas classes, C={1,2,…,K}. Para classificar os elementos da amostra
utiliza-se uma aplicação que associa cada vector x de X (o espaço de medida), cujas
coordenadas são os valores assumidos pelas variáveis explicativas que descrevem a amostra
para o caso x, a uma classe de C. Podemos definir então a regra de classificação ou
classificador como "uma função d(x) definida em X, que para todo o x∈X, d(x) é igual a um
dos números 1,2,…,K", ou equivalentemente, "uma partição de X em K subconjuntos
disjuntos A1,…,AK, X = U A j tal que, para todo o x∈Aj a classe prevista é a j" ([BREI84],
j∈C
p.4).
Como na prática raramente temos disponíveis os dados referentes à população, ou outras
amostras de tamanho suficientemente grande, os dados de A têm de ser utilizados para
construir d(x) e para estimar o valor do risco de classificação incorrecta, R*(d), associado a d.
A este tipo de estimação chamamos estimação interna. Existem diversas formas de a realizar,
mas apenas referiremos com brevidade o método de validação v-fold.
Neste método, a amostra original é particionada em v subamostras, de dimensões
aproximadas, com uma distribuição associada semelhante à da variável dependente. Numa
primeira etapa, uma das amostras é reservada para o cálculo do erro de classificação (amostra
hold-out), enquanto que as restantes v-1 amostras são utilizadas como base para a construção
das regras de classificação. Este processo repete-se até que cada uma das v amostras tenha
sido utilizada como amostra hold-out. O valor final do erro de classificação é obtido através
da média associada às v medidas de precisão disponíveis.
As árvores de decisão/classificação são obtidas recursivamente, partindo do geral para o
particular. Em cada etapa "um nó é dividido em nós descendentes de modo a que a
Pág. 32
Monografia
heterogeneidade ou diversidade destes nós, no que diz respeito aos valores da variável
dependente, seja mais reduzida que no nó ascendente" ([CARD], p.14).
Muitas vezes obtemos uma árvore que modela os dados de uma forma excessivamente
precisa, ou seja, é demasiado grande ou subdivide excessivamente o conjunto de dados, nesse
caso dizemos que o modelo está sobreajustado. Torna-se assim necessário evitar esta
característica indesejável. Uma forma de o fazermos é através da poda da árvore de
decisão/classificação, isto é, por retirarmos ramos e subárvores que não nos interessam para a
resolução do problema, ou que não têm interesse prático, obtendo uma árvore incompleta.
Existem duas formas de podarmos a árvore: não a deixando crescer até ao fim (forward
prunning) ou então, cortando ramos depois de estar completa (backward prunning). Para
seleccionarmos quais os ramos a podar, calculamos o custo de classificação incorrecta, R*(d),
da árvore completa e depois de o ramo ser retirado. Se este aumentar, não podamos esse ramo,
se permanecer inalterado, o ramo em questão é dispensável. Com a poda obtemos várias
árvores alternativas para modelar o problema. De forma simples podemos dizer que a
selecção da melhor será realizada através do cálculo do erro de previsão, procurando
minimiza-lo.
4.3. Algoritmos
Para obtermos uma árvore de decisão/classificação existem diversos algoritmos a que
podemos recorrer, são eles o CHAID, o CART e o QUEST, entre outros. A sua função é
explicar a variável dependente seleccionando as melhores variáveis explicativas. Vejamos
como funcionam.
CHAID é uma sigla para CHi-squared Automatic Interaction Detector. É possível
aplicar este algoritmo a qualquer tipo de variáveis explicativas. Segmenta os dados avaliando
os valores de uma possível variável explicativa através de um teste de chi-quadrado, se a
variável é nominal, se é contínua, categoriza-a automaticamente e aplica um teste de Fisher.
Se dois valores são estatisticamente semelhantes, são agregados numa classe, mantendo todos
os valores estatisticamente dissemelhantes inalterados. Assim, a melhor variável explicativa é
a que resulta em classes mais homogéneas e dará origem ao primeiro ramo da árvore. Obtém-
Pág. 33
Monografia
se o resto da árvore iterativamente. Este algoritmo não é binário, podendo, por isso, dividir os
dados em mais de dois grupos de cada vez.
CART significa Classification And Regression Trees. Este algoritmo, ao contrário do
anterior, é binário. Para obter o número de divisões possíveis, este algoritmo considera,
quando a variável explicativa tem k valores ordenados, k-1 divisões possíveis, quando a
variável explicativa é nominal, com k categorias, consideram-se 2k-1-1 divisões possíveis. Para
seleccionar a melhor partição dos dados, procura minimizar a impureza dos nós folha, para
isso são utilizadas medidas de impureza como por exemplo, o coeficiente de Gini (G),
L
definido para uma variável nominal com L categorias, G ( N ) = 1 − ∑ p 2 ( I | N ) , onde p(I|N) é
I =1
a probabilidade a priori da classe I se formar no nó N. Cada variável pode ser usada diversas
vezes ao longo do processo de crescimento da árvore.
As árvores obtidas através do algoritmo CART têm, normalmente, muitos níveis, o que
pode tornar pouco eficiente a apresentação dos resultados e tornar as conclusões obtidas a
partir da sua estrutura pouco confiáveis. Este algoritmo apesar de flexível é complexo
tornando a computação dos resultados muito morosa para grandes conjuntos de dados.
O algoritmo QUEST foi criado em1997 e a sigla significa, em inglês, Quick, Unbiasied,
Efficient Statistical Tree, e como o nome indica, é realmente eficiente, as árvores obtidas
estão sujeitas a um menor enviesamento e o tempo de computação é mais reduzido que nos
outros dois algoritmos. Tal como o CART, é binário. No entanto, separa o processo de
selecção das variáveis explicativas do processo de busca da melhor segmentação dos dados
em classes. Pode ser aplicado a qualquer tipo de variáveis explicativas, mas a variável
dependente tem de ser nominal. Se várias das variáveis explicativas possuem o mesmo valor
informativo, então todas têm a mesma probabilidade de ser escolhidas.
Existem diversos critérios de paragem para os vários algoritmos, normalmente basta que
um seja atingido para que a árvore seja considerada completa. Alguns são:
o Todos os casos num nó têm valores idênticos para todas as variáveis explicativas.
o O nó torna-se puro, isto é, todos os casos no nó tomam o valor da variável dependente.
o O número de casos que constituem um nó é inferior a um mínimo especificado a
priori para que um nó continue a ser dividido. ([SPSS98], p.181-2).
Pág. 34
Monografia
Em anexo são apresentados os vários algoritmos referidos neste capítulo.
4.4. Exemplo
O seguinte exemplo foi construído a partir de dados recolhidos e disponibilizados por
Maria Ana Dionísio, aluna do 5º ano do curso de Biologia - Ramo de Biologia Marinha, da
Universidade dos Açores, no âmbito do seu estágio curricular, com o tema “Ecologia,
Biologia e Dinâmica de Populações de microcassiope minor”. Os dados foram recolhidos, de
forma aleatória, entre Outubro de 2001 e Setembro de 2002 no Cerco da Caloura, S. Miguel.
Como se trata de um caranguejo, as variáveis consideradas são o sexo, o comprimento
máximo, a largura máxima, o peso e o comprimento das quelas (pinças mais desenvolvidas).
A árvore seguinte foi gerada utilizando o Answer Tree 2.0 e o algoritmo CART.
A
amostra
recolhida
é
constituída por 717 indivíduos. Para
a
construção
regressão
desta
(assim
árvore
de
designada
por
termos utilizado o algoritmo CART)
utilizou-se uma amostra de treino
constituída por 95% dos indivíduos
recolhidos, seleccionada de forma
aleatória, os restantes 5% ficaram
como amostra de teste. A variável
dependente escolhida foi o sexo, e
de entre as variáveis referidas acima,
o
algoritmo
seleccionou
como
melhores variáveis explicativas o
comprimento
máximo,
o
comprimento da quela esquerda e a
Figura 4: Árvore de Regressão obtida com o AnswerTree 2.0.
largura
máxima
(expressos
em
milímetros).
No primeiro nó temos a descrição da amostra relativamente à variável sexo. 44,04% dos
indivíduos são do sexo feminino, 52,68% são do sexo masculino e a 3,68% não foi possível
determinar o sexo (por serem imaturos).
Pág. 35
Monografia
Em seguida, a amostra foi classificada de acordo com o comprimento máximo dos
indivíduos. Verificou-se que 96,47% têm comprimento máximo superior a 2,247 milímetros
(mm), e desses, 45,5% são fêmeas, 54,05% são machos e 0,46% são imaturos.
Os indivíduos com o comprimento máximo superior a 2,247 mm foram segmentados de
acordo com o comprimento da quela esquerda, sendo que apenas 8,39% têm essa quela com
um comprimento superior a 5,5 mm, ou seja, a maioria dos indivíduos são destros. Dos
indivíduos canhotos, 85,96% são do sexo masculino.
Por fim, os indivíduos com comprimento de quela esquerda inferior ou igual a 5,5 mm
foram divididos de acordo com a sua largura máxima, resultando em 44,62% com largura
inferior ou igual a 5,463 mm e 43,45% com mais de 5,463 mm.
Em anexo, é possível encontrar mais informações sobre a amostra e sobre a construção
desta árvore.
Muito se poderia dizer ainda sobre árvores de classificação e decisão, pois existem
diversas abordagens à sua construção e optimização, no entanto, como o espaço disponível é
limitado ficaremos por aqui.
Pág. 36
Monografia
Capítulo V
Neste capítulo apresentamos os nomes de alguns softwares disponíveis no mercado para
a mineração de dados, para a construção de árvores de classificação ou decisão e algumas
ferramentas de OLAP. Está disponível informação adicional sobre cada uma destas
ferramentas no site www.kdnuggets.com.
Software:
Data Mining
OLAP
Árvores de Classificação e Decisão
Clementine
Power OLAP
Answer Tree
Statistica Data Miner
SPSS for Windows
Knowledge Seeker
Tabela 4: Software para análise de bases de dados.
Falaremos um pouco do Answer Tree 2.0 e do SPSS for Windows 11.5, referindo
brevemente algumas das suas capacidades.
o Answer Tree 2.0: este é um software produzido pela SPSS e destina-se à obtenção de
árvores de decisão ou classificação a partir de bases de dados (folhas de cálculo do
Excel, bases de dados Access, entre outras). Permite a aplicação de qualquer um dos
algoritmos referidos no capítulo anterior. As árvores de decisão ou classificação
podem ser geradas automaticamente pelo programa de acordo com critérios padrão, ou
estes podem ser alterados pelo utilizador, de acordo com o seu conhecimento dos
dados. A sua utilização é relativamente fácil, mas para um bom aproveitamento das
suas capacidades é necessário ler com atenção o manual do fabricante.
o SPSS for Windows 11.5: como o nome indica, este software também é produzido pela
SPSS. É uma poderosa ferramenta estatística, que permite realizar uma exploração
profunda dos dados, trabalhar com séries temporais (embora não enfatize os métodos
de análise referidos anteriormente neste trabalho) e criar cubos de OLAP para analisar
os dados. Apesar de ser necessário um bom conhecimento de Estatística para trabalhar
com este software, o seu uso é bastante intuitivo.
Assim, concluímos esta referência breve a algumas das ferramentas para a exploração de
bases de dados disponíveis hoje no mercado de software, que utilizam as técnicas estudadas
neste trabalho.
Pág. 37
Monografia
Pág. 38
Monografia
Conclusão
Após a realização deste trabalho, considero que este é um tema extremamente
interessante para um aluno de Matemática, pois permite uma melhor compreensão da
aplicação desta disciplina ao mundo real. Infelizmente, devido ao limite imposto pelo número
de páginas previsto, não me foi possível aprofundá-lo tanto quanto gostaria. Assim, penso que
existem ainda muitos aspectos que podem vir a ser alvo de trabalhos futuros, especialmente se
tivermos em conta a muita bibliografia disponível on-line e não só.
Com a pesquisa bibliográfica realizada na Internet descobri aplicações da Matemática
que não julgara possíveis, por exemplo, no campo da Medicina existem já diversos SAD’s,
que recorrem a dados clínicos e a históricos de pacientes, construídos com o objectivo de
auxiliar médicos no diagnóstico de diversas doenças. Assim, posso afirmar que a realização
desta monografia me deu acesso a uma área do conhecimento humano que até agora me era
totalmente desconhecida e que procurarei aprofundar.
Concluo que muitas das técnicas de IO e Estatística, algumas incluídas nesta
monografia, outras não, são ferramentas práticas muito poderosas, quando são utilizadas por
um SAD e/ou mesmo isoladamente. Com a rapidez da evolução da tecnologia e a redução dos
custos de pesquisa e desenvolvimento, espero que o investimento a longo prazo na
implementação das técnicas tratadas neste trabalho no apoio à decisão se torne mais apelativo
para as empresas e organizações, permitindo assim a generalização do seu uso.
Pág. 39
Glossário
Glossário
Burótica: é a aplicação da informática e das novas tecnologias aos trabalhos de
escritório [DLPC01].
Centróide: é o ponto C=(c1, ..., cn) onde cada coordenada ci é a média dos valores da iésima variável para os objectos pertencentes ao cluster (ou classe).
Heurística: refere-se a “conhecimento informal adquirido através do senso comum
[traduzido num algoritmo ou procedimento] (...) de como resolver problemas com eficácia e
eficiência, como planear as fases de resolução de um problema complexo, (...) e assim por
diante.” ([TURB98], p.869).
Matriz de dissemelhanças: é uma matriz cujas entradas são constituídas pelo valor do
coeficiente de dissemelhança, dij, calculado para cada dois casos, com base nas variáveis em
estudo.
Matriz de semelhanças: é semelhante à matriz de dissemelhanças mas em vez de termos
coeficientes de dissemelhança, dij, temos coeficientes de semelhança, sij.
Modelo: uma descrição simples de um sistema, que se adapte aos objectivos definidos
pelo decisor, permitindo que este avalie quantitativamente diversas soluções alternativas para
o problema que deve solucionar.
Padrão: dado um conjunto de factos (dados/informação), F, uma linguagem, L, e
alguma medida de certeza C, um padrão é uma afirmação A em L que descreve as relações
entre o subconjunto FA de F com o valor de certeza c tal que A é de alguma forma mais
simples que a enumeração de todos os factos em FA. [DILL95].
Problema estruturado: problema que surge com frequência e para o qual existem já
métodos de resolução definidos.
Problema não estruturado: um problema complexo, de difícil definição e sem soluções
standard.
Problema semi-estruturado: um problema que é parcialmente estruturado.
Pág. 40
Bibliografia
Bibliografia Referenciada
[BAPT01] BAPTISTA, E., 2001. SIG – Sistemas de Informação Geográfica. Universidade dos
Açores.
[BREI84] BREIMAN, L.; FRIEDMAN, J., OLSHEN, R. & STONE, C., 1984. Classification
and regression trees. Wadsworth & Brooks Advanced Books and Software. ISBN: 0-534-98053-8.
[CARD] CARDOSO, M. s/data. Acetatos do curso de Métodos Quantitativos Aplicados.
[CHAV01] CHAVES, E. & FALSARELLA, O., 2001. Sistemas de Informação e Sistemas de
Apoio à Decisão; www.chaves.com.br/TEXTSELF/COMPUT/sad.htm ; Último Acesso: 04/10/2002;
Última Actualização: 24/09/2001.
[DILL95] DILLY, R., 1995. Data Mining Student Notes, versão 2.0. Queen’s University of
Belfast Parallel Computer Centre.
http://www.pcc.qub.ac.uk/tec/courses/datamining/stu_notes/dm_book_1.html. Último Acesso:
19/12/2002. Última Actualização: 1995.
[DLPC01] 2001. Dicionário da Língua Portuguesa Contemporânea da Academia das Ciências
de Lisboa.Vol. I.Verbo.
[FREI01] FREITAS Jr., O., MARTINS, J., RODRIGUES, A. & BARCIA, R., 2001. Sistema de
Apoio à Decisão usando a tecnologia Data Mining com estudo de caso da Universidade Estadual de
Maringá – I Congresso Brasileiro de Computação – CBComp 2001.
[GROT98] GROTH, R., 1998. Data Mining – A hands-on approach for business professionals.
Prentice Hall. ISBN: 0-13-756412-0.
[INFO98] 1998. Informativo Técnico Nº52;
www.revista.unicamp.br/infotec/informacao/inf52.htm. Último Acesso: 03/02/2002. Última
Actualização: 1998.
[INMO99] INMON, B., 1999. Data Warehousing Glossary of Terms. www.billinmon.com.
Último Acesso: 05/11/2002. Última Actualização: 1999.
[KARY] KARYPIS, G. & ZHAO Y., s/data. Evaluation of hierarchical clustering algorithms
for document datasets. www.cs.umn.edu/~karypis. Último Acesso: 01/02/2003. Última Actualização:
2003.
[LUCE01] LUCENA, P. & DE PAULA, M., 2001. Árvores de Decisão Fuzzy.
www.icmc.sc.usp.br/~percival/. Último Acesso: 11/12/2002. Última Actualização: 2001.
[POWE02a] POWER, D.J, 2002. A brief history of decision support systems, versão 2.4.
www.dssresources.com/history/dsshistory.html. Último Acesso: 17/10/2002. Última Actualização:
13/10/2002.
Pág. 41
Bibliografia
[POWE02b] POWER, D.J, 2002. Decision support systems: concepts and resources for
managers. Capítulo 1. www.dssresources.com. Último Acesso: 13/10/2002. Última Actualização:
13/10/2002.
[SPSS98] 1998. Answer Tree 2.0 User’s Guide. SPSS, Inc. www.spss.com.
[THEA] BERSON, A., SMITH, S. & THEARLING, K.; An Overview of Data Mining
Techniques, in Building Data Mining Applications for CRM.
www.thearling.com/text/dmtechniques/dmtechniques.htm. Último Acesso: 02/06/2003. Última
Actualização: 2003.
[TURB98] TURBAN, E. & ARONSON J., 1998. Decision Support Systems and Intelligent
Systems. Prentice-Hall. ISBN: 0-13-781675-8.
[WEIE98] WEIERS, R., 1998. Introduction to business statistics, 3rd edition. Brooks/Cole
Publishing Company.
Pág. 42
Bibliografia
Bibliografia Consultada
[AMA96] AMARAL, P., 1996. Reconhecimento de padrões.
www.dq.fct.unl.pt/qof/chem9.html. Último Acesso: 31/01/2003. Última Actualização: 1996.
[CHAU97] CHAUDHURI, S. & DAYAL, U., 1997. An Overview of Data Warehousing and
OLAP Technology, in ACM Sigmod Record. Março 1997.
[FORS97] FORSMAN, S., 1997. OLAP Council white paper. www.olapcouncil.org. Último
Acesso: 11/02/2003. Última Actualização: 1997.
[IBM98] BALLARD, C., BELL, R., HERREMAN, D., KIM, E. & VALENCIC, A., 1998. Data
Modelling Techniques for Data Warehousing. Cap.3, Cap. 6. IBMRedbooks. www.redbooks.ibm.com.
[INFO93] 1993. Quality Unbound, in AI Expert. Maio 1993. www.patternwarehouse.com.
Último Acesso: 11/02/2003. Última Actualização: 1995.
[MEND] MENDES, A., s/data. Acetatos da disciplina de Investigação Operacional.
Universidade dos Açores.
[KEEN98] KEENAN, P., 1998. When the question is ‘where’? – integrating geographic
information systems and management science, in OR Insight. Vol.11 Nº1. Janeiro-Março 1998. p.2328.
[SPSS99a] 1999. Answer Tree Algorithm Summary. www.spss.com. Último Acesso:
20/06/2003. Última Actualização: 2003.
[SPSS99b] 1999. Report OLAP: Technology options for decision makers. www.spss.com.
Último Acesso: 20/06/2003. Última Actualização: 2003.
[SPSS01] 2001. Documentação de Apoio do SPSS for Windows 11.0. www.spss.com.
[SPSS1] s/data. Basic applied techniques – choose the right stat to make better decisions.
www.spss.com. Último Acesso: 20/06/2003. Última Actualização: 2003.
[SPSS2] s/data. Data mining and statistics – Gain a competitive advantage. www.spss.com.
Último Acesso: 20/06/2003. Última Actualização: 2003.
[STAT84] 1984. STATISTICA Electronic Textbook. www.statsoft.com . Último Acesso:
02/02/2003. Última Actualização: 2003.
Sites de interesse:
www.dssresources.com
www.dwinfocenter.org
www.itpapers.com
www.spss.com
Pág. 43
Bibliografia
Pág. 44
Anexos
Anexo I
Abaixo apresentamos o algoritmo geral do método hierárquico aglomerativo, adaptado
de [VIVE99], página 20. A distância entre as observações i e j é representada por dij e a
distância entre os clusters i e j por Dij.
1ª etapa:
⇒ Considerar cada entidade como sendo um cluster (isto é, inicialmente Dij=dij).
⇒ Construir a matriz n×n de distância de valores Dij, com base num coeficiente de
comparação.
2ª etapa:
⇒ Encontrar o elemento mais pequeno desta matriz (em caso de igualdade a escolha
torna-se facultativa).
⇒ Se o elemento for, por exemplo, Dkm, unem-se os grupos k e m, sendo o valor de
Dkm designado por coeficiente de clustering.
3ª etapa:
⇒ Calcular a distância entre o novo cluster e cada um dos clusters existentes, através
de um critério de agregação.
⇒ Substituir as filas e as colunas k e m da matriz de distância pela fila/coluna singular
de novos valores de distância, reduzindo, assim, a ordem da matriz de distâncias
em uma unidade.
4ª etapa:
⇒ Repetir as etapas 2 e 3 até existir apenas um cluster.
Observação: Neste algoritmo assume-se que o ponto de partida para a classificação dos
elementos é uma matriz de dissemelhanças entre as n entidades. Se se tratar de uma matriz de
semelhanças, é necessário considerar não o menor, mas o maior elemento, na segunda etapa.
Pág. 45
Anexos
Anexo II
Neste anexo, apresentamos os algoritmos referidos no Capítulo IV, ou seja, o CHAID, o
CART e o QUEST. Os algoritmos apresentados abaixo foram adaptados de [SPSS98],
páginas 185 a 190.
II.1. CHAID
1ª etapa:
⇒ Para
cada variável preditora X, encontrar o par de categorias significativamente
menos diferente (com o maior valor para p) relativamente à variável Y. O método
para calcular p depende do tipo de variável Y.
o Se Y é contínua, usar um teste de Fisher.
o Se Y é nominal, construir uma tabela com as categorias de X nas linhas e as
de Y nas colunas. Usar o teste do chi-quadrado de Pearson.
o Se Y é ordinal, ajustar um modelo de associação a Y. Usar o teste de
“likelihood-ratio”.
2ª etapa:
⇒ Para o par de categorias de X com o maior valor de p, comparar o p com um nível
de significância αagreg escolhido a priori.
o Se p>αagreg, agregar este par numa categoria composta. Como resultado, um
novo conjunto de categorias de X é formado, e o processo volta à primeira
etapa.
o Se p<αagreg, prosseguir para a terceira etapa.
3ª etapa:
⇒ Calcular o valor de p ajustado para as categorias de X e de Y.
4ª etapa:
Pág. 46
Anexos
⇒ Seleccionar a variável preditora X que tem o menor valor de p ajustado (o mais
significativo). Comparar p com um nível de significância αdiv escolhido a priori.
o Se p≤αdiv, dividir o nó no conjunto de categorias de X.
o Se p>αdiv, não dividir o nó. O nó é terminal.
5ª etapa:
⇒ Continuar o processo até que um dos critérios de paragem seja satisfeito.
II.2. CART
1ª etapa:
⇒ Começar
pelo nó raiz, t=1, procurar um ponto de divisão s* no conjunto dos
possíveis candidatos, S, que resulta no maior decréscimo da impureza:
Φ ( s*,1) = max Φ ( s,1) .
s∈S
Então, dividir o nó 1 (t=1) em dois nós, t=2 e t=3, usando o ponto de divisão s*.
2ª etapa:
⇒ Repetir
o processo de busca de um ponto de divisão para t=2 e t=3, e assim
sucessivamente.
3ª etapa:
⇒ Continuar
o processo de crescimento da árvore até que um dos critérios de
paragem seja alcançado.
Observação: A função Φ(s,t) para busca do ponto de divisão s no nó t, para o coeficiente Gini
escreve-se como:
Φ( s, t ) = G (t ) − p E (t E ) − p D (t D ) ,
onde pE é a proporção de casos do nó t que passam a fazer parte do novo nó à esquerda, e pD é
a proporção de casos que passam a fazer parte do novo nó à direita.
Pág. 47
Anexos
II.3. QUEST
1ª etapa:
⇒ Para cada variável preditora X, se X é uma variável nominal categorizada, calcular
o valor de p para um teste de independência do chi-quadrado de Pearson entre X e
a variável categorizada dependente. Se X é contínua ou ordinal, usar o teste F para
calcular o valor de p.
2ª etapa:
⇒ Comparar o menor valor de p com um α ajustado de Bonferroni, pré-especificado.
o Se p<α, então seleccionar a variável preditora correspondente para dividir o
nó. Avançar para a 3ª etapa.
o Se p>α, para cada X contínua ou ordinal, usar o teste de Levene para
variâncias desiguais no cálculo de p.
o Comparar o menor valor de p do teste de Levene com um novo α ajustado de
Bonferroni.
o Se p<α, seleccionar a variável preditora correspondente com o menor valor
de p do teste de Levene para dividir o nó. Avançar para a 3ª etapa.
o Se p>α, seleccionar a variável preditora da 1ª etapa que tem o menor valor de
p (quer do teste de chi-quadrado de Pearson, quer do teste F) para dividir o
nó.
3ª etapa:
⇒ Supor que X é a variável preditora da segunda etapa. Se X é contínua ou ordinal,
avançar para a 4ª etapa. Se X é nominal, transformar X numa variável auxiliar Z e
calcular a maior coordenada discriminante de Z (o objectivo é maximizar as
diferenças entre as categorias da variável dependente).
Pág. 48
Anexos
4ª etapa:
⇒ Se
Y possui apenas duas categorias, avançar para a 5ª etapa. Caso contrário,
calcular a média de X para cada categoria de Y e aplicar um algoritmo de
aglomeração a essas médias para formar duas superclasses de Y.
5ª etapa:
⇒ Aplicar a análise discriminante quadrática para determinar o ponto de divisão do
nó. Note-se que este método produz dois possíveis pontos de divisão, escolher o
que mais se aproxima da média amostral de cada classe.
Observação: O algoritmo QUEST lida separadamente com a selecção de variáveis e a
selecção de pontos de divisão dos nós. O valor de α pré-especificado normalmente é 0,05.
Pág. 49
Anexos
Anexo III
Neste anexo, fornece-se informação adicional sobre a amostra utilizada na construção do
exemplo do Capítulo IV, e sobre o processo de construção da árvore.
Informação sobre a amostra
Indivíduos
(N=717)
Sexo Feminino
299
Sexo Masculino
355
Imaturos
25
Valor mínimo
1,455 mm
Valor médio
4,457 mm
Valor máximo
9,35 mm
Valor mínimo
1,909 mm
Valor médio
5,617 mm
Valor máximo
13,2 mm
Valor mínimo
0,926 mm
Valor médio
3,415 mm
Valor máximo
8,636 mm
Valor mínimo
0,926 mm
Valor médio
3,984 mm
Valor máximo
11,66 mm
Mínimo
0,0007 g
Médio
0,081 g
Máximo
0,789 g
Comprimento máximo
da carapaça
Largura máxima da
Comprimento
Esquerda
carapaça
Direita
das quelas
Peso
Tabela A.1:Informação adicional sobre a amostra de microcassiope minor estudada no Capítulo IV.
Para a construção da árvore de regressão apresentada no Capítulo IV, utilizou-se o
Answer Tree 2.0 da SPSS, e o algoritmo CART. A amostra inicial foi separada em duas, 95%
dos casos passaram a constituir a amostra de treino e 5% foram reservados como amostra de
teste. A medida de impureza escolhida foi o coeficiente de Gini com as probabilidades a
priori calculadas a partir da amostra de treino. Os critérios de paragem foram: no máximo a
árvore gerada teria cinco níveis, para poder ser dividido um nó teria no mínimo três casos, os
Pág. 50
Anexos
nós terminais teriam no mínimo um caso e a alteração do coeficiente de impureza seria, no
mínimo de 0,0001. O erro de classificação total da árvore obtida foi de 0,395 (39,5%).
DEPARTAMENTO DE MATEMÁTICA
Secção de Estatística e Investigação Operacional
Tânia Cristina de Lima Fernandes ©
Fernandes, Tânia C. Lima (2003) “Métodos Estatísticos e
de I.O. utilizados em Sistemas de Apoio à Decisão (SAD’s)”
Monografias da SEIO. Depto. Matemática da Univ. dos
Açores: Ponta Delgada, www.uac.pt/~amendes (ID 54.543)
O trabalho apresentado é da exclusiva responsabilidade da aluna que o assina. O Departamento
de Matemática e a Universidade dos Açores não se responsabilizam por eventuais erros
existentes no mesmo.
Os textos podem ser descarregados livremente, impressos e utilizados para ensino ou estudo
dos temas a que se referem. No entanto, não podem ser copiados ou incluídos noutros trabalhos
académicos ou de qualquer outra natureza, sem o consentimento do autor e a devida referência
completa. Para autorização de cópia parcial ou integral, utilize o endereço de correio electrónico:
[email protected]
Pág. 51