Resumo do livro 'Data Mining: Um Guia Prático'

O livro Data Mining: Um Guia Prático, de Ronaldo Goldschmidt e Emmanuel Lopes Passos, me foi indicado por um professor da universidade. Eu o li no começo de 2014, em cerca de duas semanas, vez que é bem sucinto (tem menos de 300 páginas).

O conteúdo é bem básico (afinal, é um livro introdutório) e didático, e está dividido em cinco capítulos. Pessoalmente, gostei mais dois capítulos 3 e 4, visto que são bem densos e o tudo é bem explicado. Por outro lado, detestei o capítulo 5, e acredito que nem deva ser lido, pois não é bem explicado e chega a ser confuso.

Apesar de o livro já ser antigo, muitos dos conceitos apresentados ainda são válidos, logo vale a leitura.

Minhas notas pessoais

1 - Introdução

• KDD: Knowledge Discovery in Databases.

• Dado -> Informação -> Conhecimento

• Hierarquia:
  • Dados: itens elementares captados por recursos da Tecnologia da Informação.
  • Informação: dado processado, com significado e contexto bem definido.
  • Conhecimento: padrão ou conjunto de padrões cuja formulação pode envolver e relacionar dados e informações.

• Etapas do KDD: Pré-processamento -> Mineração de dados -> Pós-processamento

• Regras:
  • Padrão reconhecido pelo homem. Ex:

    SE RENDA >= t
    ENTÃO CLIENTE = NÃO NEGLIGENTE
    SENÃO CLIENTE = NEGLIGENTE
    

  • Acurácia: avalia a qualdiade de uma regra. É a proporção dos casos que satisfazem ao antecedente e ao consequente em relação ao número de casos que satisfazem somente ao antecedente da regra.

2 - O processo de KDD

• Uma aplicação é composta por:
  • Problema, caracterizado por:
    • Conjunto de dados; pressupõe-se que organizados em uma estrutura tabular bidimensional.
    • Especialista no domínio da aplicação; pessoa ou grupo que conhece o assunto e o ambiente onde será realizado o processo de KDD.
    • Objetivos da aplicação, compreendendo as características a serem esperadas do módulo de conhecimento a ser produzido ao final do processo. A precisão mínima é um exemplo de característica
  • Recursos disponíveis para a solução do problema. Destacam-se o especialista em KDD, as ferramentas computacionais de KDD e a plataforma computacional (hardware) disponível.
  • Os resultados obtidos a partir da aplicação dos recursos no problema. Eles compreendem:
    • Modelo de conhecimento: abstração que descreve algum conjunto de dados, avaliado em relação aos objetivos da aplicação.
    • Históricos sobre como os modelos de conhecimento foram gerados.
• O KDD é caracterizado como um processo composto por três etapas operacionais básicas:
  • Pré-processamento: captação, organização e tratamento de dados.
  • Mineração de dados: busca efetiva por conhecimentos úteis.
    • Descoberta de associação: busca por itens que frequentemente ocorrem de forma simultânea.
    • Classificação: mapeia um conjunto de registros em um conjunto de rótulos categóricos predefinidos, denomidados classes.
    • Clusterização: separa os registros em clusters com propriedades comuns, mas sem rótulos predefinidos.
    • Sumarização: procura e identifica características comuns entre conjuntos de dados.
    • Detecção de desvios.
    • Descoberta de sequências.
  • Pós-processamento: tratamento do conhecimento obtido na mineração de dados.
• Classificação de uma aplicação de KDD:
  • Validação de hipóteses postuladas.
  • Descoberta de conhecimento.
• O analista humano é o elemento central do KDD.

3 - Etapas do processo de KDD

• Variáveis de um problema (atributos) podem ser classificadas em:
  • Nominais ou categóricas: utilizadas para atribuir rótulos a objetos; não ordenável.
  • Discretas: semelhantes às nominais, porém ordenáveis e com um valor que possui algum significado.
  • Contínuas: variáveis quantitativas cujos valores possuem uma seleção de ordem entre si; finitas ou infinitas; dados numéricos.
• Pré-processamento
  • Captação, ordenação, tratamento e preparação dos dados para a etapa de mineração.
  • Seleção de dados.
• Seleção de dados
  • Compreende a identificação de quais informações, dentre as bases de dados existentes, devem ser efetivamente consideradas durante o processo de KDD.
  • É comum a congregação de dados em uma única tabela de um DB relacional.
  • Redução de dados horizontal: caracterizada pela escolha de casos.
    • Segmentação do banco de dados: escolhe-se um ou mais atributos para segmentar o banco de dados (ex.: usando WHERE em SQL).
    • Eliminação direta de casos: uma variação da segmentação, são especificados os casos que devem ser eliminados (ex: usando DELETE em SQL).
    • Amostragem aleatória: sorteia-se um número preestabelecido de registros, de forma a diminuir o conjunto resultante.
    • Agregação de informações: informações com um grande nível de detalhe (ex: compras de um cliente) são agrupadas em informações com menos detalhes (ex: total de compras).
  • Redução de dados vertical
    • Dado um conjunto \(S =\{A1, A2, ..., An\}\), deve-se identificar qual das \(2 ^ n\) combinações entre os atributos (A) deve ser considerada no processo de KDD.
    • Os atributos são eliminados ou substituídos, de forma a encontrar um mínimo de atributos em que a informação original seja preservada.
    • Abordagens
      • Abordagem independente de modelo: atributos são selecionados sem considerar o algoritmo de mineração.
      • Abordagem dependente de modelo: o algoritmo de mineração é experimentado em cada conjunto de atributos e os resultados são avaliados.
    • Estratégias clássicas
      • Forward selection: a cada iteração é adicionado ao subconjunto dos atributos candidatos algum que tenha maximizado uma medida de qualidade avaliada.
  • Redução de valores
    • Consiste em reduzir o número de valores distintos em determinados atributos, o que pode melhorar o desempenho do algoritmo de mineração.
    • Redução de valores nominais: um especialista no domínio define uma hierarquia entre os atributos (logradouro ⊂ bairro ⊂ cidade) ou entre valores (sandália ⊂ calçado, tênis ⊂ calçado, bermuda ⊂ roupa).
    • Redução de valores contínuos ou discretos: os dados são agrupados em células de mesma cardinalidade; reduzidos por suas medianas; reduzidos por suas médias; reduzidos pelo limite das células; arredondados ou agrupados em relação a seus valores (clusterização).
• Limpeza
  • Envolve uma verificação da consistência das informações, correção de possíveis erros, preenchimento ou eliminação de valores desconhecidos e redundantes e eliminação de valores não pertencentes ao domínio.
  • Valores divergentes -> outliers
  • Funções de limpeza
    • Limpeza de informações ausentes
      • Exclusão de casos: excluem do conjunto de dados as tuplas que possuam pelo menos um atributo vazio.
      • Preenchimento manual de valores: geralmente é inviável; pode ser implementado por meio de pesquisas junto às fontes de dados originais.
      • Preenchimento com valores globais constantes: consiste em substituir todos os valores ausentes de um atributo por um valor como “NULL”.
      • Preenchimento com medidas estatísticas: alternativa a valores constantes, pode se utilizar a média para atributos numéricos e a moda para atributos categóricos.
      • Preenchimento com métodos de mineração de dados: modelos preditivos são construídos de forma a seguir os valores mais prováveis a serem utilizados no preenchimento dos valores ausentes.
    • Limpeza de inconsistências: consite na identificação e eliminação de valores inconsistentes em conjuntos de dados.
      • Exclusão de dados: exclui do conjunto de dados as tuplas que possuem pelo menos uma inconsistência. Ex.: clientes menores de 21 anos para os quais tenha sido concedido crédito.
      • Correção de erros: manualmente ou em lote, quando em ambientes relacionais.
      • Limpeza de valores não pertencentes ao domínio: é um caso particular da limpeza de inconsistências, e demanda conhecimento prévio do domínio de cada atributo.
• Codificação
  • Representa a forma como os dados serão representados durante o projeto de KDD, de forma a atender às necessidades específicas dos algoritmos de mineração.
  • Codificação numérica-categórica
    • Mapeamento direto: consiste na substituição de valores numéricos por valores categóricos.
      • 1 -> M
      • 0 -> F
    • Mapeamento em intervalos (discretização): do domínio de uma varíável numérica é divido em intervalos.
  • Codificação categórica-numérica
    • Representação binária padrão: cada valor categórico é associado a um valor de 1 a N representado por uma cadeira de digitos binários.
      • Casado -> 001
      • Solteiro -> 010
      • Viúvo -> 100
    • Representação binária 1-de-N: o código 1-N tem um comprimento igual ao número de categorias discretas permitidas para a variável.
      • Casado -> 00001
      • Solteiro -> 00010
      • Viúvo -> 00100
    • Representação binária por temperatura: geralmente utilizada quando os valores discretos estão relacionados de algum modo.
      • Fraco -> 0001
      • Regular -> 0011
      • Bom -> 0111
• Enriquecimento
  • Consiste em agregar mais informações aos registros existentes para que estes forneçam mais elementos para o processo de descoberta de conhecimento.
  • Operações mais utilizadas:
    • Pesquisas: captação de novas informações junto às fontes originais.
    • Consulta a bases de dados externas: consiste na incorporação de informações fornecidas por outros sistemas.
• Normalização de dados
  • Consiste em ajustar a escala dos valores de cada atributo de forma que os valores fiquem em pequenos intervalos, tais como de -1 a 1 ou de 0 a 1.
  • Normalização linear: considera os valores mínimo e máximo de cada atributo no ajuste da escala. Mapeia os valores de um atributo no intervalo fechado de 0 até 1.
  • Normalização por desvio padrão (Z-score, zero mean): considera a posição média dos valores de um atributo, assim como seus graus de dispersão.
  • Normalização pela soma dos elementos: o valor do atributo a ser normalizado é dividido pela soma de todos os valores de tal atributo. Há a desvantagem de alguns valores tornarem-se muito pequenos.
  • Normalização pelo valor máximo dos elementos: cada valor do atributo a ser normalizado é divido pelo valor máximo entre estes.
  • Normalização por escala decimal: é deslocado o ponto decimal do valor a ser normalizado. O número de casas depende do maior valor absoluto do valor em questão.
• Construção de atributos
  • Consiste em gerar novos atributos a partir de atributos existentes. Ex: DataNasc - AnoAtual = Idade
• Correção de prevalência
  • Corrige um eventual desequilíbrio na distribuição de registros com determinadas características.
  • Utilizado principalmente em problemas de classificação, de forma a “aumentar a importância” de classes com menos amostras.
• Partição do conjunto de dados
  • A qualidade dos modelos de conhecimento deve ser avaliada, não podendo ser utilizados os dados utilizados na criação do modelo.
  • O conjunto de dados deve ser partcionado em conjunto de treinamento (para construção do modelo) e em conjunto de testes.
  • Métodos de partição
    • Holdout: os registros são divididos aleatóriamente em p porcento para treinamento e em 1 - p para teste.
    • K-fold cross validation: um conjunto de dados com N elementos é dividido em K subconjuntos disjuntos (folds), com aproximadamente o mesmo número de elementos (N/K).
    • Stratified K-fold cross validation: similar ao anterior, porém é considerada a proporção de cada classe na amostragem. Útil em problemas de classificação.
    • Leave-one-out: caso particular do K-fold onde cada subconjunto K possui um único registro.
    • Bootstrap: o conjunto de treinamento é gerado a partir de N sorteios aleatórios com reposição a partir do conjunto de dados original (com N registros). O conjunto de teste é composto pelos elementos não sorteados. Os conjuntos são gerados e usados na avaliação do modelo, sendo repetido diversas vezes para estimar uma média de desempenho do algoritmo.
• Mineração de dados
  • Compreende a aplicação de algoritmos sobre os dados, procurando abstrair conhecimento (modelos de conhecimento).
  • Medida de interesse: ordenação e filtragem de padrões de acordo com o grau de interesse nestes; seleção de conjuntos de padrões que satisfaçam à condições predeterminadas.
    • Medidas de interesse objetivas: baseadas na estrutura dos padrões e nas estatísticas relacionadas.
    • Medidas de interesse subjetivas: crenças dos especialistas no domínio em relação aos dados e aos modelos de conhecimento gerados. Ex: surpresa, contradições (em relações ao modelo esperado).
  • Um conjunto de dados pode ser interpretado como um conjunto de pontos num espaço n-dimensional, e a similaridade entre dois pontos é dada pela sua distância. Quanto menor a distância, maior a similaridade.
  • Alguns algoritmos aprendem os relacionamentos eventualmente existentes entre os dados.
    • Aprendizado supervisionado: um modelo de conhecimento é abstraído a partir dos dados apresentados na forma de pares ordenados (entrada e saída desejados);
    • Aprendizado não-supervisionado: não há informações sobre a saída desejada.
• Pós-processamento
  • Envolve a visualização, análise e interpretação do modelo de conhecimento gerado pela mineração de dados.
  • Nesta etapa, o especialista em KDD e o especialista em domínio de aplicação avaliam os resultados e definem novas alternativas de investigação de dados.
  • Simplificação do modelo de conhecimento: consiste em remover detalhes do modelo de forma a torná-lo menos complexo, sem perda de informação relevante.
    • Regras são cortadas levando-se em conta sua precisão e abrangência.
    • Dado um modelo de conhecimento composto por regras na forma X -> Y, onde X e Y são predicados:
      1. Precisão da regra: percentual de registros que, ao satisfazerem o antecedente da regra, também satisfazem o consequente.
      2. Abrangência da regra: percetual de registros que, ao satisfazerem o consequente da regra, também satisfazem o antecedente.
    • O grau de entropia de um conjunto de atributos expressa o grau de complexidade da informação contida nele.
  • Transformações de modelo de conhecimento: baseiam-se na conversão da forma de representação de um modelo. Ex: transformar uma árvore de decisão em regras.
  • Organização e apresentação de dados: técnicas de visualização de dados estimulam a percepção e a inteligência humana, aumentando a capacidade de entendimento e associação de novos padrões, oferecendo subsídios para a escolha dos passos seguintes de KDD.

4 - Tarefas de KDD

• Uma tarefa de KDD equivale a uma operação de KDD que pertença à etapa de mineração de dados.
  • Tarefa primária: não pode ser desmembrada em tarefas menores.
  • Tarefa composta: pode ser desmembrada em tarefas menores.
• Descoberta de associações
  • Consiste em encontrar conjuntos de itens que ocorram simultaneamente e de forma frequente num banco de dados.
    • Exemplo: produtos vendidos frequentemente de forma conjunta.
      • Leite -> Pão
      • Pão & Manteiga -> Café
      • “A compra de um conjunto de itens do antecedente da regra tem a propensão de levar à compra do conjunto de itens do consequente”.
  • Regra de associação:
    • X -> Y, tal que X ∩ Y != Ø
    • A intersecção vazia assegura que não sejam extraídas regras óbvias que indiquem que um item está associado à ele próprio.
  • Uma associação é considerada frequente se o número de vezes em que a união de conjuntos de itens X e Y ocorrer em relação ao número total de transações do banco de dados for superior a uma frequência mínima (suporte mínimo);
  • Confiança mínima: expressa a qualidade de uma regra, indicando o quanto a ocorrência do antecedente pode assegurar a ocorrência do consequente.
    • K-itemset: todo conjunto com K itens (2-itemset, 3-itemset, etc);
      • Leite -> Pão: 2-itemset
• Descoberta de associações generalizadas
  • Busca associações em um maior nível de abstração.
    • Camisa -> Sapato (nenhuma abstração)
    • Roupa -> Sapato (abstração à esquerda da regra)
    • Roupa -> Calçado (abstração à esquerda e à direita da regra)
• Descoberta de sequências
  • Considera o aspecto temporal entre os registros de um banco de dados.
  • Os padrões a serem descobertos são analisados em várias transações, em ordem cronológica, logo são chamados de padrões intertransação.
    • Exemplo: análise do histórico de itens comprados por consumidores ao longo de determinado período.
• Descoberta de sequências generalizadas
  • Utiliza a hierarquia e a abstração eventualmente existentes em cada aplicação.
• Classificação
  • Busca por uma função que permita associar corretamente cada registro X(i) de um banco de addos a um único rótulo categórico Y(j), chamado de classe.
  • Cada algoritmo possui um “bias” indutivo que direciona o proceso de seleção dos classificadores, o qual influência na seleção de hipóteses.
  • Completude: capacidade de um classificador em classificar todos os exemplos da base de dados.
  • Consistência: capacidade de um classificador em classificar corretamente os exemplos da base de dados.
• Regressão
  • Busca por funções, lineares ou não, que mapeiem os registros de um banco de dados em valores reais.
  • Exemplos: predição da ma de biomassa em uma floresta; estimativa da probabilidade de um paciente sobreviver dado um conjunto de diagnósticos.
• Sumarização
  • Identificação e apresentação de forma concisa e compreensível das principais características dos dados contidos em um conjunto de dados.
  • Exemplos: características dos assinantes de uma revista que vivem na região sudeste; perfil dos meninos de rua da cidade do Rio de Janeiro.
• Clusterização (agrupamento)
  • Usada para particionar os registros de uma base de dados em subconjuntos ou clusters, nos quais os elementos compartilhem um conjunto de propriedades comuns que os diferenciam de elementos de outros clusters.
  • Objetiva-se maximizar a similaridade intracluster e minimizar a similaridade intercluster.
  • Diferente da Classificação, a Clusterização não possui rótulos predefinidos. Os rótulos são definidos automaticamente, por indução não-supervisionada.
  • Os algoritmos de clusterização geralmente trabalham com as seguintes estruturas de dados:
    • Matriz de dados: as linhas são os objetos, e cada coluna um atributo (p).
    • Matriz de similaridade: cada elemento representa a distância entre pares de objeto i e j. Não é necessário armazenar distâncias repetidas, visto que \(i + j = j + i\).
  • Uma melhor clusterização de dados requer que alguns requisitos sejam atendidos pelos algoritmos que implementam tal tarefa:
    • Descobrir clusters com forma aleatória.
    • Identificar clusters de tamanho variado.
    • Aceitar variáveis contínuas, discretas e nominais.
    • Ser insensível à ordem de apresentação dos objetos.
    • Trabalhar com objetos com qualquer número de dimensões (atributos).
    • Ser escalável para lidar com qualquer quantidade de objetos.
    • Fornecer resultados interpretáveis e utilizáveis.
    • Ser robusto na presença de ruídos
    • Exigir o mínimo de conhecimento para determinar parâmetros de entrada.
    • Aceitar restrições.
    • Encontrar o número adequado de clusters.
  • Métodos de particionamento dividem a base de dados em K grupos, com K objetos sendo o centro dos K clusters. O usuário define K. Os objetos são dividos entre os clusters de acordo com a medida de similaridade adotada:
    • K-means: é utilizada a média dos objetos que pertencem ao cluster em questão (centro de gravidade).
    • K-medoids: é escolhido como o representante do cluster o objeto que mais se aproxima de seu centro de gravidade (medoid).
  • Os métodos de clusterização por particionamento tentam fazer os clusters tão compactos e separados quanto possível.
  • Os algoritmos de clusterização hierárquicos criam uma representação hierárquica da base de dados através de dendogramas. O dendograma pode ser criado através de uma abordagem aglomerativa (bottom-up, das folhas para a raiz) ou divisiva (top-down, da raiz para as folhas).
• Previsão de séries temporais
  • Uma série temporal é um conjunto de observações de um fenômeno ordenadas no tempo.
  • A análise de séries temporais permite a criação de modelos voltados à previsão de valores futuros.
  • Há quatro tipos principais de movimentos utilizados na caracterização de séries temporais:
    • Movimentos de tendência: indicam a direção geral na qual o gráfico da série temporal se move ao longo do tempo.
    • Movimentos cíclicos: referem-se às oscilações de uma curva, periódicas ou não.
    • Movimentos sazonais: ocorrem devido a eventos que se repetem de tempos em tempos.
    • Movimentos irregulares ou randômicos: são influenciados por eventos que ocorrem de forma aleatória (chuvas intensas, calor forte, etc).
  • A busca por similaridade em séries temporais envolve a identificação de sequências de dados que apresentem pouca variação em relação ao padrão apresentado. Pode-se utilizar a combiação de sequências e a aproximaão de sequências.
• Detecção de desvios
  • Objetiva identificar mudanças em padrões anteriormente percebidos. É muito útil na detecção de fraudes.
  • Busca identificar padrões com pouca incidência e que sejam suficientemente distintos dos valores normalmente registrados.
  • São especificados limites de tolerância, e os valores que os ultrapassam são chamados de outliers.
• Clusterização -> Classificação
• Encadeia as tarefas, sendo aplicável onde os dados não estejam enquadrados em classes específicas.

• Os dados são agrupados em função de sua similaridade, e cada rótulo do cluster passsa a ser considerado como uma classe. Em seguida, algoritmos de classificação são aplicados.

• Clusterização -> Sumarização
  • Encadeia as tarefas, sendo aplicável onde o conjunto completo de registros do banco de dados disponha de pouca similaridade entre seus elementos.

5 - Métodos de mineração de dados

• Um método de KDD pode requerer o cumprimento de precondições antes de sua execução. Uma plano de ação de KDD válido é toda uma sequência de métodos de KDD onde são atendidas as precondições para executar cada tarefa. Ex: P01: Preenchimento moda -> Normalização linear -> Codificação binária -> Backpropagation

• Métodos baseados em redes neurais
  • Redes neurais artificiais (RNAs)
    • Modelos matemáticos inspirados nos princípios de funcionamento de neurônios biológicos e na estrutura do cérebro.
    • Têm capacidade de adquirir, armazenar e utilizar conhecimento experimental.
    • Características: aprendizado por experiência, busca paralela endereçamento de conteúdo, generalização de conteúdo, associação entre padrões, abstração de características de um conjunto, robustez e degradação natural.
    • Numa RNA, os neurônios são organizados em cadamas, e conectados por “pesos”. Ex: Camada de entrada -> Camadas escondidas -> Camada de saída
  • Os elementos básicos de um neurônio artificial:
    • Conexão entre os processadores: a cada conexão de entrada, existe um valor real, denomidado peso sináptico, que determina o efeito desta entrada sobre o neurônio.
    • Regra de propagação: é a forma como as entradas provenientes de outros neurônios artificiais são bomaindas aos pesos sinápticos de determinado neurônio.
    • Função de ativação: determina o novo valor de estado de ativação de um neurônio artificial a partir de seu potencial de ativação
  • Uma rede neural pode ser recorrente (suas saídas são realimentadas para suas entradas, definindo uma “memória”), ou não-recorrentes.
  • Existem dois tipos de processamento em RNAs:
    • Aprendizado ou etapa de treinamento: engloba a atualização de pesos sinápticos para a aquisição a partir dos dados.
  • As RNAs devem passar por uma fase de treinamento, o qual pode ser supervisionado ou não-supervisionado.
    • Treinamento supervisionado: necessita de um par de vetores composto por um vetor de entrada e por um vetor alvo que se deseja ter como saído. O vetor de entrada é aplicado, a saída é calculada e, por fim, comparada ao vetor de saída. A saída é retroalimentada e os pesos são atualizados de acordo com um algoritmo, até que os níveis de erro tornem-se baixos.
    • Treinamento não-supervisionado: não quer vetor-alvo para as saídas, modificando os pesos da rede de modo a produzir saídas consistentes (vetores de entrada similares com vetores de saída similares);
    • Backpropagation
      • É um algoritmo supervisionado aplicado em problemas de Classificação, Regressão e previsão de séries temporais.
      • Tem como objetivo minimizar a função de erro entre a saída gerada pela rede neural e a saída desejada, utilizando o método do gradiente descendente.
    • Kohonen: é uma rede neural auto-organizável, cujo treinamento não é supervisionado. Pode ser aplicada na clusterização e na detecção de regularidades.
• Métodos baseados em instâncias
  • O método, ao processar um novo registro, leva em consideração as instâncias (ou registros) existentes na base de dados.
  • K-Nearest Neighbors (K-NN): utilizado em tarefas de Classificação; não requer treinamento.
• Métodos estatísticos
  • Classificador Bayesiano Ingênuo (probabilidade condicional).
  • K-means: clusterização.
  • K-modes: variação do K-means para dados categóricos (nominais).
  • K-prototypes: avalia valores numéricos e categóricos.
  • K-medoids: baseia-se na localização do objeto mais central do cluster.
• Métodos específicos
  • Apriori: usado para determinar regras de associação.
• Métodos baseados em indução de árvores de decisão
  • C4.5: usado em problemas de Classificação.
• Métodos baseados em fuzzy logic
  • Wang-Mendel: previsão de séries temporais.