UM MÉTODO BASEADO EM PARTICIONAMENTO HORIZONTAL PARA MINERAÇÃO DE PADRÕES FREQUENTES EM TABELAS DE HORÁRIOS

Abstract

Timetables associate the beginning and the end of activities. These activities are associated with several attributes that may be aware of an allocation of times in the table. The timetables that represent origin and destination or duration of activities can be improved from association rules (ARs) between the attributes of the table. That said, analyzing the timetables is an important task, as it brings the opportunity to discover valuable information that improves management processes, forecasting the transport network, among other examples. Meanwhile, frequent pattern mining is a technique used to support such type of discovery. However, functional dependencies of the attributes derived from the origin-destination matrix are intrinsic properties present in timetables. Such functional dependencies compromise the search for patterns in timetables in both the number of association rules (ARs) generated and the computational cost. Several of these ARs refer to the same information. Redundancy removal techniques can reduce the number of ARs. However, these techniques are designed to be used only after mining finishes, which increases the computational cost of finding useful ARs. This work presents the Timetable Pattern Mining (T-mine), a novel method for frequent pattern mining that improves knowledge discovery in timetables. We evaluated T-mine using Brazilian Flight Data and compared T-mine with the direct application of frequent pattern mining approaches with and without functional dependencies. Our experiments indicate that T-mine has a lower computational cost (less execution time and less memory allocation) than other approaches.

Tabelas de horários associam o início e o término de atividades. A essas atividades estão associados diversos atributos que podem ter conhecimento quanto a alocação de horários da tabela. As tabelas de horários que representam origem e destino ou tempo de duração de determinadas atividades podem ser melhoradas a partir de regras de associação (RAs) entre os atributos da tabela. Isso posto, analisar tabelas de horários é uma tarefa importante, pois traz a oportunidade de descobrir informações valiosas que aprimoram processos de gestão, previsão da rede de transporte, dentre outros exemplos. Enquanto isso, a mineração de padrões frequentes é uma técnica usada para apoiar esse tipo de descoberta. Entretanto, existem propriedades intrínsecas presentes nas tabelas de horários. São as dependências funcionais entre o atributo que caracteriza primariamente a atividade planejada com os seus demais atributos. Tais dependências funcionais comprometem a busca por padrões nas tabelas de horários tanto no número de RAs geradas, quanto no custo computacional. Várias dessas RAs referem-se às mesmas informações. As técnicas de remoção de redundância podem reduzir o número de RAs. No entanto, essas técnicas são projetadas para serem usadas somente após o término da mineração, o que aumenta o custo computacional de encontrar RAs úteis. Este trabalho apresenta o Timetable Pattern Mining (T-mine), um novo método para mineração de padrões frequentes que melhora a descoberta de conhecimento em tabelas de horários. Avaliamos o T-mine usando dados de voos brasileiros e comparamos o T-mine com a aplicação direta de abordagens de mineração de padrões frequentes com e sem dependências funcionais. Nossos experimentos indicam que o T-mine apresenta um menor custo computacional (menor tempo de execução e menor alocação de memória) do que outras abordagens.