Pós-processamento de regras de associação via redes e propagação de rótulos

• Ano de defesa: 2015
• Autor(a) principal: Padua, Renan de
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Biblioteca Digitais de Teses e Dissertações da USP
• Palavras-chave em Português: Association rules; Label propagation; Networks; Poda; Pós-processamento; Pos-processing; Programação de rótulos; Prune; Redes; Regras de associação
• Link de acesso: http://www.teses.usp.br/teses/disponiveis/55/55134/tde-14102016-165710/

Dentre as técnicas de mineração existentes encontra-se a associação, responsável por identificar relações que ocorrem no conjunto de dados. Embora a associação seja uma das técnicas mais utilizadas, a quantidade de padrões extraídos pode vir a sobrecarregar o usuário de tal maneira que encontrar algo interessante dentre a imensidão de padrões obtidos passa a ser um novo desafio. Para solucionar esse problema, uma grande parte dos trabalhos relacionados à associação está voltada a etapa de pós-processamento. Esses trabalhos geralmente propõem abordagens de pós-processamento que visam, segundo determinada estratégia, facilitar a busca pelos padrões interessantes ao domínio. Nos últimos anos, essas abordagens têm incluído no processo o conhecimento e/ou interesse do usuário sobre o domínio. Contudo, nas abordagens atualmente existentes, o usuário deve, por meio de algum formalismo descrever explicitamente seu conhecimento e/ou interesse, requerendo do usuário um tempo considerável, podendo levar, inclusive, a especificações incompletas e/ou incorretas. Além disso, na maioria das vezes, o usuário não tem ideia do que é provavelmente interessante, nem a partir de quais relações iniciar a busca. Nota-se, portanto, que um dos desafios dessas abordagens é considerar o conhecimento e/ou interesse do usuário. Além disso, é necessário considerar também o número de regras que o usuário analisará. A análise de regras feita por um especialista é custosa e, na maioria dos casos, o usuário quer explorar as regras geradas sem limitar a exploração ao conhecimento que ele já possui. Portanto, é importante que o usuário avalie o menor número de regras possível e, com base nessa avaliação, abordagens de pós-processamento consigam o auxiliar na busca pelas regras que ele poderá considerar interessante. Para tanto, é proposto neste trabalho que o pós-processamento seja tratado como um problema de classificação semissupervisionada transdutiva, uma vez que permite que o usuário rotule, considerando classes pré-definidas (por exemplo, \"Interessante\" ou \"Não Interessante\"), apenas algumas regras do conjunto a ser explorado para que todas as outras regras sejam automaticamente rotuladas. Além disso, por meio da definição dos rótulos de algumas regras, é possível capturar implicitamente o conhecimento e/ou interesse do usuário sobre o domínio. Para tanto, é necessário que as regras sejam modeladas de maneira a permitir: (a) selecionar as regras a serem rotuladas pelo usuário a fim de capturar implicitamente seu conhecimento e/ou interesse; (b) propagar os rótulos das regras já classificadas pelo usuário a todas as outras regras não rotuladas. Desse modo, neste trabalho, as regras foram modeladas via redes, uma vez que: (i) uma vasta quantidade de medidas de exploração de redes pode ser utilizada, em conjunto com as informações fornecidas pelo usuário, a fim de viabilizar o item (a); (ii) algoritmos de propagação de rótulos podem ser utilizados a fim de viabilizar o item (b). Diante do apresentado, ressalta-se que as contribuições deste trabalho estão na capacidade de se extrair o conhecimento e/ou interesse do usuário de acordo com as características da base de dados e direcionar sua exploração sem a necessidade de se definir previamente o que será explorado. Além disso, os resultados obtidos demonstram a capacidade da PARLP em direcionar o usuário para o conhecimento considerado interessante, reduzindo, para tanto, a quantidade de regras a serem exploradas. Por fim, este trabalho contribui também para demonstrar que é possível tratar o pós-processamento de regras de associação como um problema de propagação de rótulos.