A mineração de dados é um campo multidisciplinar que inclui áreas de IA, Estatística, Reconhecimento de Padrões, entre outros. A tarefa de minerar dados permite extrair pa drões ou conhecimentos interessantes de BD, os quais são uteis para auxiliar na tomada de decisão em vários domínios de aplicações, tais como a análise de mercado, diagnósticos médicos, controle de produção, jogos, etc [67]. A mineração de dados pode ser classificada em duas categorias: descritiva e preditiva. A mineração descritiva encontra padrões e pro priedades que frequentemente estão presentes no dados analisados, enquanto a mineração preditiva realiza indução nos dados de modo a extrair modelos preditivos que possam ser usados para efetuar predições do comportamento de novos dados [6 8].
Esta seção apresenta 3 técnicas de mineração de dados, sendo uma descritiva e duas preditivas, que foram utilizadas para o desenvolvimento deste trabalho.
2.3.7.1 Mineração de Padrões Frequentes
Mineração de padrões frequentes é um tipo de mineração descritiva que extrai padrões que ocorrem frequentemente numa BD. Geralmente, esses padrões representam informa ções potencialmente úteis, não triviais e previamente desconhecidas pelos especialistas do domínio. O problema de minerar padrões frequentes de um BD pode ser descrito como: dado uma BD D contendo as transações T\, ...,Tn, encontre todos os padrões P
que estão presentes em pelo menos numa fração s dessas transações. A fração s é denomi nada de suporte mínimo, o qual pode representar a frequência absoluta (valor absoluto) ou a frequência relativa com que as transações ocorrem na BD. Cada transação Ti na BD corresponde a uma tupla na BD [69]. No modelo original de mineração de padrões frequentes, proposto em [70], o problema de encontrar relacionamento (ou associações) entre os itens de uma BD foi proposto como sendo um “segundo estágio” do processo de mineração, o qual é derivado dos itens frequentes desta BD. Neste modelo, inicialmente é feita uma mineração descritiva e, a partir dos padrões frequentes encontrados na BD, é feito uma mineração preditiva com o objetivo de encontrar relacionamentos entre os itens que representam esses padrões, os quais poderiam ser usados para analisar e predizer o comportamento de novos dados.
Neste trabalho entretanto, foi aplicado apenas o “primeiro” estágio da mineração pro posta em [70], o qual obtém os itens frequentes de uma determinada BD. Tais itens descrevem a frequência com que determinadas características ocorrem na BD.
56 Capítulo 2. Fundamentos Teóricos e Estado da Arte 2.3.7.2 Mineração de Regras de Exceção
Extrair conhecimento interessante a partir grande quantidade de dados é uma das principais preocupações da mineração de dados. Uma classe de conhecimento que atrai muito a atenção das pesquisas na área são as regras de exceção [71], [72], [73], [74], [75] [76], [77]. Uma exceção pode ser definida como algo diferente da maioria, que contradiz o senso comum e geralmente representa algum conhecimento interessante.
As regras de exceção permitem que a precisão de regras gerais sejam otimizadas, uma vez que representam conhecimentos excepcionais e interessantes não representados pelas regras gerais. Uma regra de exceção pode ser expressa pela combinação de uma regra geral e associado a essa regra, uma exceção. Enquanto a regra geral representa o conhecimento comum, a regra de exceção representa conhecimentos locais que contradizem esse conhecimento. O conceito de localidade das regras de exceção está relacionado ao fato delas serem obtidas a partir de situações especiais que o conhecimento geral não foi capaz de representar, e de serem usadas para complementá-lo. Uma regra geral possui alto valor de suporte e confiança, enquanto regras de exceção possuem baixo suporte e confiança semelhante às regras gerais [76]. O suporte representa a frequência relativa com que as instâncias cobertas por uma regra ocorrem na BD e a confiança representa a precisão de cobertura dessa regra.
A mineração de regras de exceção foi proposta por Hussain [76], o qual define uma regra de exceção de acordo com o apresentado na Tabela 3, onde A e B representam um item ou um conjunto de itens e B também representa disjunções não vazias de restrições sobre os itens. Por exemplo, se houver uma regra geral “se a pessoa está desempregada,
então não lhe é dado crédito” (A ^ X ), uma exceção seria “ se a pessoa está desempregada e seu cônjuge está empregado, então lhe é dado crédito” (A A B ^ —X ). Neste caso,
a regra “ seu cônjuge está empregado, então lhe é dado crédito” (B ^ —X ) representa uma regra de referência, a qual explica a exceção. Regras de referência podem ter baixo suporte e/ou baixa confiança e são regras difíceis de serem descobertas (mineradas).
Tabela 3 - Estrutura das regras com exceções proposta por Hussain.
A ^ X Regra geral:
alto suporte, alta confiança.
A A B ^ —X Regra de exceção:
baixo suporte, alta confiança.
B ^ —X Regra de referência:
baixo suporte e/ou baixa confiança.
Um conjunto de regras isoladas é pouco intuitivo e dificulta o entendimento de qualquer problema. Geralmente os indivíduos expressam o conhecimento em termos de padrões gerais e casos especiais. Desse modo, o par de regras [regra geral, regra de referência], que formam as exceções são mais confortáveis e familiares no que diz respeito as necessidades
de entendimento desses indivíduos, sendo que as regras gerais são verificadas primeiro e exceções à essas regras são modeladas como um posterior refinamento do conhecimento induzido pela regra geral. Exceções podem, por exemplo, representar posições raras de damas sobre o tabuleiro, as quais quando identificadas podem conduzir o jogo para uma situação de vitória.
O conceito de regras de exceção proposto por Hussain é utilizado neste trabalho para tratar o baixo desempenho da RN em alocar os agentes em algumas situações especiais do jogo.
2.3.7.3 Mineração de Árvore de Decisão - C4.5
Árvore de Decisão (A D ) é um dos métodos mais utilizados da literatura de mineração de dados para tratar problemas de classificação. Este método pertence a família de algoritmos “ dividir para conquistar ”, o qual divide um conjunto de treinamento, até que cada subconjunto obtido deste particionamento contenha apenas exemplo de uma mesma classe [78]. A construção de uma AD pode ser descrita como um procedimento recursivo, o qual divide o conjunto de dados em subconjuntos de exemplos cada vez mais puros em relação a uma determinada classe. Sua estrutura é composta por: nós folhas, que correspondem as classes do problema; nós de decisão, os quais correspondem aos nós internos da árvore responsáveis por testar as condições sobre os atributos e; arestas, que conectam os nós de decisão que satisfazem determinadas condições até a classe que os representam [67]. Para classificar um novo exemplo numa AD, um caminho é traçado a partir do nó raiz (neste caso, representa um nó de decisão), descendo pelas arestas de acordo com os resultados das condições, até chegar em um nó folha, que representa a classe de predição do exemplo [6 8]. Uma AD pode ser facilmente mapeada em um
conjunto de regras, transformando cada ramo da árvore (cada caminho da raiz até um dos nós folha) em uma regra. As regras traduzidas são disjuntas, de modo que apenas uma única regra dispara quando um novo exemplo é classificado. Tais árvores apresentam como principal vantagem estruturas simples e de grande legibilidade, as quais podem ser facilmente entendidas e usadas diretamente pelo usuário. O grande representante desse grupo é o algoritmo C4.5.
O C4.5 foi proposto por Quilan [79] como um melhoramento do algoritmo ID3 [80]. As principais vantagens do C4.5 em relação ao seu sucessor são: lida com atributos contínuos e com valores desconhecidos; lida com problemas em que os atributos possuem custos diferenciados; utiliza a medida gain ratio (razão do ganho) para selecionar o atributo que melhor divide os exemplos, gerando árvores mais precisas e menos complexas; efetua pós poda nas árvores geradas. O C4.5 é um dos métodos de AD mais consagrados na literatura, o qual é considerado um padrão na comparação de algoritmos de aprendizagem simbólica. Este algoritmo têm obtido ótimos resultados em problemas de classificação ao longo de décadas.