, Project Systems Analyst
Mineração emFluxos Contínuos de DadosOrlando da Silva Juniorosilva[at]ufabc.edu.br 2.
Agenda• Introdução• Fluxos de dados• Processamento de fluxos de dados• Mineração em fluxos de dados• Aplicações• Referências 3.
Objetivo• Apresentar os principais conceitos da mineração em fluxos contínuos de dados • Fundamentos • Técnicas • Aplicações 4.
Motivação• A mineração em fluxos de dados consiste na utilização de técnicas de aprendizado de máquina para explorar fluxos de dados• Os fluxos de dados são gerados em diversos contextos tecnológicos • Telecomunicações • Energia • Astronomia e meteorologia • Computação e suas aplicações • Internet • Detecção • Monitoramento e supervisão• Objetivo: minerar padrões, processar consultas e computar estatísticas sobre os fluxos de dados em tempo real 5.
Fluxos de Dados• Um fluxo de dados é uma sequência contínua e ordenada de itens em tempo real (Golab e Özsu, 2003) • Não é possível controlar a ordem em que esses itens chegam • Não é viável armazenar a totalidade desse fluxo localmente• Características: • Enorme volume de dados • Os dados trafegam em altas velocidades • Tráfego em tempo real FENÔMENO DOS FLUXOS DE DADOS Transmitir Computar Armazenar 6.
Fluxos de Dados• Os fluxos de dados são contínuos e gerados em ambientes dinâmicos de alta velocidade que mudam como tempo• Por essas características, as técnicas atuais não conseguem tratar desses fluxos• São necessárias novas técnicas que criem modelos de decisão que sejam capazes de: • Incorporar novas informações • Esquecer dados desatualizados • Detectar mudanças e se autoadaptarem às novas informações 7.
Métodos para Processamento deFluxos de Dados• Os métodos para processamento de fluxos de dados são focados na manutenção do controle do fluxo• Na mineração de dados, os métodos para processamento de fluxos de dados são tratados conforme a abordagem adotada (Gaber, Zaslavsky e Krishnaswamy, 2005): • Técnicas baseadas em dados: a ideia central é examinar apenas um subconjunto de um conjunto de dados completo, ou transformar os dados em uma representação de dados de menor tamanho aproximado • Técnicas baseadas em tarefas: a ideia é alcançar soluções eficientes em tempo e espaço 8.
Técnicas de Processamento de Fluxos deDados Baseadas em Dados• As técnicas baseadas em dados referem-se (Gaber, Zaslavsky e Krishnaswamy, 2005): • À sumarização do conjunto de dados total; ou • À escolha de um subconjunto de dados do fluxo de entrada para ser analisado• As principais técnicas são: • Amostragem • Balanceamento de carga • Sketching • Estruturas de dados sinópticas • Agregação 9.
Técnicas de Processamento de Fluxos deDados Baseadas em Dados• Amostragem • Processo de escolha probabilística de um item de dado ser processado ou não (Gaber, Zaslavsky e Krishnaswamy, 2005) • Limites da taxa de erro do cálculo são dados como uma função da taxa de amostragem • O problema da amostragem está no tamanho desconhecido do conjunto de dados• Balanceamento de carga • Processo de remoção de sequências de fluxos • É difícil de ser usado para mineração de dados porque remove pedaços dos fluxos de dados que poderiam representar padrões de interesse (Gaber, Zaslavsky e Krishnaswamy, 2005)• Sketching • É uma técnica de amostragem aleatória que sumariza o fluxo de dados usando uma pequena porção de memória (Babcock et al., 2002) • Assim como o balanceamento de carga, é difícil de ser usado na mineração de dados (Gaber, Zaslavsky e Krishnaswamy, 2005) 10.
Técnicas de Processamento de Fluxos deDados Baseadas em Dados• Estruturas de dados sinópticas • São estruturas que representam os dados • As técnicas que utilizam essas estruturas sumarizam o fluxo de entrada e produzem uma resposta aproximada (Gaber, Zaslavsky e Krishnaswamy, 2005) • Análise de wavelets, histogramas, quantis e momentos de frequência• Agregação • Calcula medidas estatísticas, as quais sumarizam o fluxo de entrada (Gaber, Zaslavsky e Krishnaswamy, 2005) • Esta técnica pode ser usada no contexto da mineração de dados 11.
Mineração em Fluxos de Dados• A evolução dos volumes de dados tornaram inviável a criação de um modelo de aprendizado preciso e consistente• Em muitos casos, essa evolução está relacionada ao alto fluxo de informações que trafegam entre as aplicações• Os SGBDs tradicionais não são projetados para o carregamento rápido e contínuo de dados de modo individual (Babcock et al., 2002)• A mineração de dados tradicional pode tratar de grandes volumes de dados, mas não de dados que trafegam continuamente• É necessário criar novas técnicas que trabalhem com dados que variam ao longo do tempo e que criem um modelo de aprendizado preciso e consistente. 12.
Mineração em Fluxos de Dados• A mineração em fluxos de dados preocupa-se com a extração de estruturas de conhecimento representadas em fluxos não- estacionários de informação (Gaber, Zaslavsky e Krishnaswamy, 2005)• A ideia geral das técnicas é criar algoritmos que coletem informações sobre o fluxo de dados em uma única passada (𝑂(𝑛)) • Restrições: limitação de recursos computacionais (CPU e memória) • Resultado: modelo de aprendizado atualizado dos dados 13.
Mineração em Fluxos de DadosAlgoritmo genérico de mineração em fluxos de dadosEntrada: fluxo de dados (sequência de dados 𝐴: 1 … 𝑁 → 𝑅2 )Saída: modelo de aprendizado1 Sumarizar pequena porção do conjunto de dados2 Transformar essa pequena parcela em dados de treinamento3 Avaliar os dados de treinamento em tempo real4 Descartar os dados5 Colher novas amostras e repetir o processo 14.
Simulação do algoritmo VFDT • 100 milhões de exemplos • Acurácia média de 98,13%• Aprendizado a cada 100 000 instâncias • Conclusão em 17min43s 15.
Técnicas de Mineração em Fluxos deDados• Existem diversas técnicas e algoritmos que realizam a extração de estruturas de conhecimento em fluxos de informação• Essas técnicas juntam características da mineração de dados tradicional e da análise de fluxos de dados• Técnicas: • Classificação • Agrupamento • Contagem de frequências • Análise de séries temporais 16.
Classificação em Fluxos de Dados• A classificação dos fluxos visa criar um modelo de classificação atualizado• O modelo é criado no decorrer do processo de classificação, ou seja, enquanto os dados seguirem continuamente o fluxo adentro (dados de entrada)• Principais técnicas: • Very Fast Decision Tree (VFDT) • Online Information Network (OLIN) • LWClass (Lightweight Classification) • CluStream (basedo em On Demand Classification) 17.
Very Fast Decision Tree (VFDT)• É uma árvore de decisão para fluxos de dados baseada nas árvores de Hoeffding (Domingos e Hulten, 2005) • Usa o limite estatístico de Hoeffding• A ideia geral do VFDT é escolher atributos de corte ótimos a partir de pequenas amostras• As árvores de Hoeffding escolhem os melhores atributos através de pontos de corte • Os pontos de corte definem os melhores atributos correntes da árvore durante o processamento 18.
Very Fast Decision Tree (VFDT)VFDTEntrada: atributos discretos ou contínuos (𝑥1 , 𝑥2 , 𝑥3 , … , 𝑥 𝑝 )Saída: árvore de decisão1 Calcular estatísticas suficientes de um pequeno conjunto de exemplos2 Estimar o mérito de cada atributo (usar algum parâmetro estatístico)3 Utilizar o limite de Hoeffding para garantir que o melhor atributo é o melhor • 𝜺 representa o limite de Hoeffding 1 𝑅2 ln • 𝟏 − 𝜹 é a probabilidade de se escolher 𝜀= 𝛿 corretamente o melhor atributo 2𝑛 • 𝒏 é a quantidade de exemplos da amostra 19.
Agrupamento em Fluxos de Dados• No agrupamento de fluxos, as técnicas focam-se na criação de algoritmos de uma única passada que coletem informações sobre o fluxo de dados• Para coletar as informações das janelas de tempo do fluxo, os algoritmos exploram técnicas de: • Exploração de micro-clustering • Agregação limitada • Aproximação• Principais técnicas: • K-mediana para fluxos (diversas abordagens) • Very Fast K-means (VFKM) • STREAM e LOCALSEARCH • Algoritmos baseados em tarefas 20.
Aplicações• Diamond Eye (Burl et al, 1999) • Desenvolvido pela NASA • O objetivo do projeto é habilitar sistemas de computação remotos e cientistas a extrair padrões de objetos espaciais em fluxos de imagens de tempo real • Primeira aplicação de análise de fluxos focada em mineração de dados 21.
Aplicações• MobiMine (Kargupta et al., 2002) • Aplicação de monitoramento do mercado de ações • É o primeiro sistema de mineração de fluxos de dados ubíquo (cliente/servidor) • Roda em um PDA • As diferentes interações entre o servidor e o PDA são exibidas na tela do PDA 22.
Aplicações• VEDAS (Kargupta et al., 2004) • Vehicle Data Stream Mining System • Sistema ubíquo de mineração de dados (usa um PDA) • Monitoramento contínuo • Extração de padrões • Fluxos de dados gerados a partir de veículos guiados em movimento • Uma abordagem de aglomeração foi utilizada para analisar o comportamento do motorista 23.
Principais Tópicos de Pesquisa• Tratamento do fluxo contínuo dos dados• Limitações dos requisitos de memória• Minimização do consumo de energia de dispositivos móveis• Modelagem das mudanças dos resultados de mineração sobre o tempo 24.
Referências• (Golab e Özsu, 2003) Data Stream Management Issues – A Survey• (Gaber, Zaslavsky e Krishnaswamy, 2005) Mining Data Streams: A Review• (Babcock et al., 2002) Models and Issues in Data Stream Systems• (Domingos e Hulten, 2000) Mining High-Speed Data Streams• (Burl et al, 1999) Diamond Eye: A distributed architecture for image data mining• (Kargupta et al., 2002) MobiMine: Monitoring the Stock Market from a PDA• (Kargupta et al., 2004) VEDAS: A Mobile and Distributed Data Stream Mining System for Real-Time Vehicle Monitoring Recommended