Embed Size (px)
Citation preview
Aula 2 - Data Warehousing ................................................................................................................................ 3
Aula 3 – Pré-processamento de dados ............................................................................................................ 12
Aula 4 - Online Analytical processing (OLAP) ................................................................................................... 17
Aula 5 – MDX Queries ...................................................................................................................................... 23
Aula 7 – OLAP: indexação e processamento das pesquisas ............................................................................ 25
Aula 6 – Data Mining (visão geral) ................................................................................................................... 31
Aula 8 – Data Mining (algoritmos de treino supervisionados) ........................................................................ 42
Aula 9 – Data Mining (algoritmos de treino) ................................................................................................... 51
Aula 11 – Data Mining (Algoritmos de treino) ................................................................................................. 61
Aula 12 – Data Mining (Métodos Emsemble) .................................................................................................. 65
Aula 13 – Data Mining (Técnicas não supervisionadas) ................................................................................... 67
Tópicos Motivação e aplicações de sistemas de apoio à decisão
Modelação de dados multidimensionais
Data Warehousing
De um modelo de dados multidimensional para Data Warehousing, OLAP e Data Mining
Motivação Disponibilidade de grande volume de dados.
o Sistemas OLTP (Bases de dados), Web, telecomunicações, sensores remotos, imagens de
satélite.
o Excede a capacidade humana de processar todos estes dados.
Transformar dados em informação ou conhecimento.
Terminologia
Ou seja, ferramentas de análise para transformar dados em informação ou conhecimento.
Aplicações
Análise de Mercado
Deteção de fraudes
Análise de Risco
CRM
Marketing direto
Sistemas de vigilância
Bio-informática
Deteção de Spam
Medicina
Etc.
Exemplo Questão: é verdade que as t-shirts com tamanhos maiores se vendem melhor em cores escuras?
OLTP versus OLAP
On-Line Transaction Processing (bases de dados)
On-Line Analytical Processing
Orientado à transação
Leitura e escrita
Manutenção em tempo real
Transações lidam com alguns tuples
Otimização para pequenas transações
Os utilizadores são funcionários, DBA, profissionais de bases de dados
Foca-se no registo de dados
Orientado à análise e registo histórico
Apenas de leitura
Atualização em bloco
As operações lidam com número grande de tuples
Otimização para transações longas
Os utilizadores são trabalhadores com conhecimentos (gestores, executivos e analistas)
Foca-se na exportação de informação
Modelação de dados multidimensionais
Áreas de aplicação:
Data Warehousing
On-line Analytical Processing (OLAP)
Data mining
Qual a razão?
Folhas de cálculo são boas para exibir dados multidimensionais (2D) mas quando se trata de
grandes volumes de dados e esses dados são multidimensionais não são a melhor ferramenta
Bases de dados relacionais não são eficientes a lidarem com cálculos entre linhas ou efetuar a
transposição entre linhas e colunas.
Solução?
Dados na forma de um cubo com medidas sobre factos relativamente a tempo, localização e algum
produto.
Cada célula não vazia representa um facto
Células vazias significam que não existe informação para os valores da dimensão dados
Algumas considerações
É usual representarem-se eventos de negócios em cubos de dados.
Não existe um consenso formal para a modelação de dados multidimensionais.
Os conceitos básicos são factos, medidas e dimensões.
o Outros conceitos incluem hierarquias, atributos descritivos, atributos de dimensão cruzada,
múltiplos e opcionais arcos de convergência.
Modelação Multidimensional
Dimensões Propriedade Facto com um domínio que descreve uma das coordenadas para analisar
As dimensões, usualmente, representam respostas a questões tais como: quando, quem, o quê e
quem
Geralmente, pelo menos uma das dimensões representa tempo
Conceito de hierarquias Representam relações entre os atributos das dimensões
Árvore direta é composta por atributos que descrevem a dimensão cujos arcos modelam as
relações um-para-muitos entre os atributos das dimensões
Determina quais os eventos que podem ser agregados no processo de tomada de decisão
Evento primário
Indica a ocorrência de um facto e determina a melhor relação de granularidade
Eventos secundários
Agregação de eventos primários para sintetizar um conjunto de eventos primários
Factos Eventos que ocorrem no mundo empresarial que são relevantes para o processo de tomada de
decisão.
Eventos dinâmicos, representados na fonte de dados por informações bastante atualizada são
bons candidatos.
Factos de evento
o Modelam eventos do mundo real
Factos Snapshot
o Modelam o estado de um processo de um dado momento
A granularidade é determinada pelos níveis das dimensões
Medidas Propriedades numéricas que descrevem aspetos quantitativos de interesse para análise
o Devem ser numéricas porque são utilizadas em cálculos
o Um facto pode não ter medidas se apenas estivermos interessados na contagem de
eventos
Tipos de medidas Aditiva – os valores podem ser combinados (p.e. somatório) ao longo de cada dimensão
Semi-aditiva – podem ocorrer quando o facto é do tipo snapshot, p.e, não é significativo somar os
níveis de inventário ao longo do tempo mas sim pelas lojas.
Não-aditiva – os valores não podem ser combinados ao longo de cada dimensão, p.e. médias ou
valores percentuais.
Data warehousing “Arquitetura e ferramentas para executivos de negócios para organizar sistematicamente, perceber e
utilizar os seus dados para tomar decisões estratégicas”
Repositório de dados para a consolidação de informação (dados são válidos e consistentes) numa
organização adequada para a análise de dados seletiva.
Autonomia relativamente às bases de dados operacionais
o Os dados aplicacionais encontram-se armazenados separadamente no ambiente
operacional
o Não necessita de processos de transação, recuperação ou mecanismos de controlo
concorrente
Foca-se em modelar e analisar os dados para tomada de decisões
Data Warehouse Armazena informação sobre diversos departamentos ou domínios de negócio
Inclui apenas dados importantes para a tomada de decisão
Integração:
o Geralmente, construída mediante a integração de diversas fontes de dados (heterogéneas)
o Técnicas de limpeza e integração de dados
Dimensão temporal é importante para realizar um estudo de tendências
Não volátil:
o Carregamento dos dados numa fase inicial
o O processamento da query não inclui atualizações nem remoções
Modelação de dados multidimensionais
Data warehouse e Data mart
Data warehouse Data mart
.. para a organização em geral.
Obtém toda a informação de toda a empresa.
Ciclo de implementação é medido em meses ou anos.
… para partes da organização.
Obtém um subconjunto dos dados corporativos que é valioso para determinadas pessoas (gestores)
Ciclo de implementação é medido em semanas.
Os princípios são os mesmos
Diferentes níveis de dados
Outro exemplo de aplicação de DW Uma agência de viagens tem escritórios em diversos países
Os escritórios possuem bases de dados locais mas a informação é acessível a outros escritórios
Existem diferentes modelos de bases de dados
O sistema atual tem problemas no que se refere à redundância e consistência dos dados
É necessário um front-end para a partilha de informações
E um repositório de dados para a análise de informação.
Desenho de Data Warehouse (Mart) Abordagens direcionadas para os dados: a partir da análise das fontes de dados
o Simplifica operações ETL (Extract Transform Load)
o Reduz o tempo despendido para desenhar e implementar a Data Warehouse ou a Data
Mart
o É a abordagem mais comum na prática
Abordagens baseada em requisitos: a partir dos requisitos da informação para os utilizadores finais
o Traz requisitos do utilizador para o conhecimento geral mas requer um esforço significativo
quando na conceção de ETL (Extract Transform Load)
O processo de desenho da Data Warehouse 1. Escolher o modelo de processo de negócio
2. Escolher a granularidade do processo de negócio
a. A granularidade é o nível atómico fundamento dos dados para serem representados numa
tabela de factos, p.e., transações, etc.
3. Desenhar as dimensões que irão ser aplicadas a cada registo da tabela de factos
4. Escolher as medidas que irão preencher cada registo da tabela de factos
Arquitetura do Data Warehouse de três camadas
Aplicações de Data Warehouses
Processamento de informação
o Consultas e relatórios utilizando cross-tables, tabelas, gráficos, etc.
OnLine Analytical Processing (OLAP)
o Análise de dados multidimensionais
Data mining
o Descoberta de conhecimento pela pesquisa de padrões e associações escondidas,
classificação, etc.
OLAP e Data Mining
OLAP Data Mining
Sumarização rápida de agregação de dados
Análise de dados interativa
Baseada em domínios especializados
Focado no negócio
Descoberta automática
Técnicas automáticas para descobrir conhecimento “escondido” interessante
Ampla gama de aplicações: empresarial, estudos sociais e científicos, monitorização e vigilância, etc.
De data warehousing até OLAP e Data mining Data Mining pode ser realizada em bases de dados (incluindo especial, texto, vídeo), ficheiros
grandes, data warehouses, etc.
OLAP é usualmente utilizado em data warehouses
A integração destas tecnologias é interessante:
o Data warehouse fornece grandes quantidades de dados limpos e consistentes que facilitam
o OLAP e Data Mining
o Data warehousing lida com ODBC, JDBC e ligações OLE para aceder às múltiplas fontes de
dados
o OLAP pode fornecer múltiplas e dinâmicas visualizações de dados em diferentes níveis de
abstração para Data Mining
Criando um Data Mart
Tópicos Sumarização de dados
Limpeza de dados
Extração, transformação e carregamento de dados
Redução de dados
Conceitos e domínio Extração, transformação e carregamento (ETL) na Data Warehousing
o Perspetiva do negócio: automação, produtividade
o Focado em limpeza de dados, integração e transformação de múltiplas e heterogéneas
fontes
o Automação é importante
Pré-processamento de dados em Data Mining
o Perspetiva científica: estudos num domínio alargado
o Focado em técnicas estatísticas para limpeza de dados, sumarização e redução
Motivação Hoje em dia, as bases de dados apresentam:
o Tamanhos enormes
o Com dados incompletos: tuples incompletos, falta de atributos de interesse ou que contêm
apenas dados agregados, porque inicialmente essa informação não era considerada
relevante
o Dados com “ruído”: dados incorretos ou “outliers”, devido à inconsistência na convenção
de nomes, erros humanos ou do computador durante a aquisição e registo de dados.
O pré-processamento de dados ajuda a melhorar a qualidade dos dados.
Técnicas
Limpeza de dados Valores em falta
o Ignorer os tuples
o Substituir os valores manualmente
o Utilizer uma “tag” como “desconhecido”
o Utilizar o valor mais provável
Dados com ruído
o Binning (combinação de clusters)
o Regressão
o Agrupamento
Integração de dados Esquema de integração
o Procurar atributos que identificam os mesmos conceitos em diferentes fontes
o Meta-dados e documentação são úteis
Correspondência de objetos
o Utilização de nomes ou valores diferentes para o mesmo objeto (entidade)
Redundância pode ser detetada pela análise de correlação (entre dados numéricos)
Transformação de dados Suavizar para reduzir o “ruído” dos dados na limpeza dos mesmos
Agregação e generalização utilizando hierarquias (idealmente de um cubo de dados)
Normalização para escalar dados de atributos para ficarem num intervalo de dados específico (p.e.,
normalização min-max e normalização z-score)
o normalização Min-Max
o normalização Z-score
Construção do atributo para adicionar novos recursos ao conjunto de dados
Redução de dados • Agregação no cubo de dados
o O cubóide é um cubo criado como mais baixo nível de abstração
o Hierarquias permitem escolher diferentes níveis de abstração
• Seleção de um subconjunto de atributos
o Para detetar e remover atributos ou dimensões que sejam redundantes ou tenham pouca
relevância
o Utilizando testes de significância estatística para determinar o “melhor” e “pior” atributo
• Redução da dimensão ou de atributos
o Análise de componentes principais
• Redução de tuples numerosos utilizando
o Modelos paramétricos (apenas é necessário armazenar os parâmetros em vez dos dados
atuais)
o Modelos não-paramétricos tais como segmentação (clustering), amostragem, histogramas,
etc.
• Discretização
Análise de componentes principais
• Procura K vetores ortogonais de n-dimensões que melhor representam os dados (k<n)
• O procedimento
o Normalizar os dados introduzidos de modo a que cada atributo fique na mesma gama
o Calcular os componentes principais
o Ordenar os componentes principais por ordem decrescente de significância ou “força” (os
eixos mostram primeiro as variâncias maiores)
o Eliminar os componentes mais fracos
Amostragem (Sampling) • Permite representar um conjunto de dados grande através de um subconjunto de dados
aleatório
o Simplesmente a amostra aleatória com (os mesmos tuples podem ser tirados diversas
vezes) ou sem repetição
o Amostra estratificada (os dados são divididos em estratos mutuamente disjuntos e a
amostra é gerada pela amostragem de cada estrato)
• Uma vantagem de amostragem é que o custo é proporcional ao tamanho da amostra, em
oposição com o tamanho do conjunto de dados
Discretização de dados • Para reduzir o número de dados de um dado atributo contínuo pela divisão do intervalo do
alcance do atributo em intervalos.
• Detalhes são perdidos mas os dados poderão ser mais informativos e mais fáceis de interpretar
Sumarização descritiva de dados • É essencial que haja uma imagem geral dos dados para identificar as propriedades típicas e
destacar os dados que devem ser tratados
o Medidas de tendências centrais: média, mediana, moda, etc.
o Medidas de dispersão de dados: quartis e variância
Medidas de tendências centrais
Medidas de dispersão de dados
Variância e desvio-padrão
Boxplots
Tópicos • Desenho físico de Data Warehousing e problemas de implementação
• OLAP
Problemas no desenho de Data Warehouse • Modelos multidimensionais assumem, geralmente, que os únicos componentes dinâmicos num
cubo são os eventos; quando se assume que as dimensões são estáticas
• Problemas no desenho (supôr):
• De ontem para hoje, todos os eventos são referidos para uma configuração antiga de
dimensões (até 01-01-2008)
• Verdade histórica reque redundância
• Ou seja, haveria vendas que tinham sido feitas pelo Paulino, mas apareciam na Alda, e a
transação de 15-06-2008 não teria ninguém como vendedor.
Tipos de dimensão de lenta alteração • Tipo 0: não foi feito esforço para lidar com mudança de dimensões
• Tipo 1: os dados alterados substituem as entradas antigas (não é mantido histórico)
o Alterações causadas pela correção de erros (p.e. um nome mal escrito, …)
• Tipo 2: todo o histórico é armazenado na base de dados
o Requer campos adicionais tais como “intervalo de tempo válido ou “é a linha atual”
• Tipo 3: apenas o valor anterior de uma dimensão é escrita na base de dados
• Tipo 4: armazena todas as alterações históricas numa tabela histórica para cada dimensão
Colunas adicionais • Chaves substitutas
o Adicionar a chave primária à tabela dimensão geridos pelos sistema DW
• Colunas de “limpeza”
o Intervalo de tempo válido: rowStartDate e rowEndDate
o Linha atual: redundante, quando existe um tempo de intervalo válido
o Colunas descritivas (meta dados)
Dimensões degeneradas • A dimensão que consiste num único identificador
• Fácil de implementar e adiciona melhor desempenho (os joins são evitados)
Hirearquias • Hierarquia Pai-filho
o No ROLAP podem ser implementados através de uma FK que referencia um PK na mesma
tabela
• Hierarquias não balanceadas
o Balancear preenchendo os níveis mais baixos
• Hierarquias não “revestidas”
o Inserir valores de preenchimento sempre que um valor não tenha níveis intermédios
Hierarquias não restritas • Relações muitos-para-muitos causam problemas com a respetiva agregação
• O ROLAP inclui tabelas associativas
Representação de dados multidimensionais
Esquema de estrela • Estrutura otimizada para avaliação de pesquisas quando as bases de dados são otimizadas para
avaliação de transações e eliminação de redundância.
• Tabela de Factos
o Composta por valores numéricos e FKs
o nº elevado de registos (armazenamento >90% DW/DM)
• Tabela de Dimensões
o não normalizada
o nº elevado de atributos (usualmente)
o poucos registos comparado com a tabela de Factos
Esquema de floco-de-neve • Algumas dimensões estão normalizadas
o Evita redundância, mas a estrutura é mais complexa e as operações de pesquisa são menos
eficientes (menor desempenho) relativamente a esquema de estrela.
Esquema de constelação • Várias tabelas de factos partilham dimensões comuns
OLAP (Online Analytical Processing) • Tecnologia para explorar a data warehouse e data marts
• Cria cubos de dados multidimensionais para análise de informação
• Fornece operações especializadas para acesso aos cubos de dados
Servidores OLAP • ROLAP (Relational OLAP)
o Utiliza a tecnologia atual de bases de dados relacionais
o É considerada como mais escalável na manipulação de grandes volumes de dados,
especialmente quando as dimensões têm cardinalidade elevada (milhões de registos)
• MOLAP (Multidimensional OLAP)
o Utiliza estruturas de dados específicas e métodos de acesso para tornar mais rápido
operações de análise em conjuntos com grande volume de dados
o Tem tendência a sofre baixo desempenho quando são pesquisas de valores não agregados
(p.e. texto)
• HOLAP (Hybrid OLAP)
o Detalha dados em ROLAP; dados de factos em MOLAP
Operações OLAP • Escavar (Drill-down)
o Navegar do mais genérico até à informação detalhada
• Roll-up
o Navegar do detalhe até à informação genérica
• Slice e Dice
o Selecionar dados (selecionar uma porção de dados)
Slice:
Dice:
• Pivot (rodar)
o Selecionar outra dimensão
Exemplo: cubos de dados • Dimensões: tamanho, cor
• Medidas: count (contador)
Gives the sum of all [valor_recebido]
Gives the sums of [valor_recebido] by [Nome Realizador]
Gives the sums of [valor_recebido] by [Nome Realizador] in 2010
OR
Gives the sums of [valor_recebido] by [Clint Eastwood] and [David Lynch] by [Genero]
use curly braces to designate a set of tuples
Gives the [valor_recebido] for [Id Cinema] between 5 and 10
The colon operator ( : ) uses the natural order of members to create a set
Computes a calculated measure [valor medio] by [Id Cinema]
Use WITH MEMBER to compute new (temporary) measures
Tópicos • Estruturas de dados e métodos de acesso para bases de dados relacionais (visão geral)
• Índices bitmap para bases de dados multidimensionais
• Processamento de pesquisas OLAP
Bases de dados operacionais • Orientado a transações
• Otimizadas para manutenção em tempo real e transações pequenas
o Planos de avaliação das pesquisas
o Métodos de acesso
• As métricas de desempenho são baseadas no nº de páginas de acesso
Estruturas de dados relacionais (ficheiros de dados) • Armazenados em blocos de discos
• Ordenados pela chave primária
• Índice não agrupado: uma entrada por registo na base de dados
• Índice agrupado: uma entrada por bloco na base de dados
Processamento de consultas OLAP • As consultas em estrela têm maior incidência em aplicações DW, OLAP e BI
• Exemplo de uma consulta em estrela:
Processamento de consultas em estrela 1. Avaliar os predicados nas tabelas de dimensões normalizadas (esquema em estrela) ou não
normalizadas (esquema de bloco-de-neve) construir um produto cartesiano com os registos das
dimensões
2. Executar um acesso direto sobre o índice da tabela de facto para o produto cartesiano
a. Para tabelas de facto muito esparsas e com muitas dimensões, esta operação torna-se cara.
3. Soluções: indexação e vistas materializadas
Indexação (ROLAP)
• As tabelas de facto são muito grandes e utilizadas na maioria das pesquisas, tipicamente:
o Criar um índice separado para cada chave da dimensão
o Criar um índice para combinações de chaves de dimensões que são muitas vezes utilizadas
em conjunto
o As tabelas de dimensão também podem ser indexadas
Índices Bitmap Simples
• A B*-tree é um índice eficiente mas para atributos de baixa cardinalidade os índices bitmap são
melhores
• Objetivo: melhorar o desempenho minimizando espaço de armazenamento extra.
• A dispersão dos vetores de bits aumenta com a cardinalidade dos atributos indexados e o nº de
registos.
Índices Bitmap baseados em intervalos
• Os valores dos atributos são particionados num pequeno nº de valores
• Se a distribuição dos valores é desconhecida, os intervalos podem ser preenchidos de forma
irregular, resultando tempos de acesso às pesquisas desconhecidos
• Requer um passo de refinamento para filtrar registos não qualificados
Índices de junção • Um índice de junção representa a pré-computação de uma consulta (query) join
o É capaz de acelerar dramaticamente consultas e
o Pode ser também estendido para incluir atributos descritivos
o Um índice de junção pode armazenar posições de bitmaps em vez de árvores (B-trees)
Processamento de consultas OLAP • As consultas podem ser divididas em:
o Consultas ad-hoc
o Consultas para construir relatórios pré-definidos
Permite pré-computação de agregações
• Uma ordenação arbitrária numa tabela de factos pode requerer muitos acessos a páginas do
disco como o nº de registos na tabela
juntar as tabelas de factos com as dimensões não é eficiente.
Criar Vistas (views) • Protege as aplicações de mudanças no desenho do DW que se encontra em produção
• Utiliza o nome das colunas significativas
• Limpa colunas das vistas
• As vistas podem ser materializadas
o Vista indexada no Microsoft SQL Server
o Vista materializada em Oracle
Materialização de cuboides • Processar grandes agregações multidimensionais em tempo real pode tornar-se extremamente
lento:
o Não materialização: não é processado nenhum tipo de cuboide
o Materialização completa: pré-computa todos os cuboides; geralmente requer muita
quantidade de espaço
o Materialização parcial: pré-computa seletivamente um conjunto de possíveis cuboides
Tabela de factos particionada • Tem um papel importante na escalabilidade dos dados da base de dados da Data Warehouse
• Aumenta a capacidade de gestão de grandes tabelas de factos
o … mas as tabelas de dimensões raramente beneficiam do particionamento
• O particionamento hierárquico preserva a estrutura de dados
Codificação hierárquica • Definição de uma chave hierárquica substituta (hsk) para cada dimensão
Chave hierárquica substituta (Hierarchical surrogate key)
• São transparentes ao utilizador
• Permitem o particionamento da tabela de facto de acordo com os planos de avaliação da
hierarquia das dimensões
• Pode ser explorado para otimizar planos de avaliação de consultas (pode acelerar até um fator
de 20 vezes)
O que é Data Mining? Extração não-trivial de informação não implícita, previamente desconhecida mas potencial
informação de dados.
Exploração e análise, por meios automáticos ou semiautomáticos, de grandes quantidades de
dados para descobrir padrões significativos.
Data Mining é parte integral de KDD (knowledge discovery in databases)
Passos principais desde o pré-processamento de dados até à visualização
de resultados Seleção: obtenção de dados a partir de diferentes fontes (diferentes bases de dados)
Pré-processamento: dados a utilizar podem estar incorretos ou em falta
Transformação: dados poderão que ser transformados para um formato comum
o Os dados podem ser reduzidos/transformados para atingir melhores representações
Data Mining: dependo dos algoritmos aplicados para atingir os resultados desejados
Interpretação/Avaliação: visualização dos resultados dos algoritmos
Data Mining: Origem
Data Mining: Desafios Escalabilidade: capacidade de lidar com grandes quantidades de dados (número grande de objetos)
Dimensão: capacidade de lidar com muitos atributos/características para cada objeto
Dados complexos e heterogéneos: diferentes tipos de atributos
Qualidade dos dados: os dados nem sempre resultam de conjuntos tradicionais de dados
Posse dos dados e distribuição: os dados armazenados são provenientes de diversas organizações
Preservação da privacidade: o desenvolvimento de data Mining tem a capacidade de comprometer
a privacidade dos dados que antes não era possível
Transmissão de dados: extrair informação de uma sequência ordenada de registos de dados
Data Mining: modelos e tarefas
Métodos de previsão (Supervisionado): utiliza algumas variáveis para prever valores futuros ou
desconhecidos de outras variáveis.
Métodos descritivos (não supervisionados): encontra padrões humanos percetíveis que descrevem
os dados
Tarefas: Classificação
Dada uma coleção de registos/objetos (conjunto de treino), cada registo:
o Conjunto de atributos/características de x
o Uma etiqueta (label) – o nome da classe
Fase de treino ou aprendizagem: escolher um modelo (w, x)
Objetivo: registos não vistos devem ser atribuídos a uma classe
Dado um conjunto de teste:
o Estudar a acurácia do modelo (desempenho do classificador).
Geralmente, o conjunto de dados disponível é dividido em conjuntos de treino e
testes
Exemplo
Tarefas: Regressão Prever o valor de uma dada variável contínua y com base em valores de outras variáveis x,
assumindo um modelo linear (ou não-linear) de dependência.
y = wT x + b or y = f (w, x)
Exemplo:
Prever a quantidade de vendas de um novo produto com base em despesas de publicidade.
Tarefas: Particionamento (Clustering) Dado um conjunto de pontos de dados, cada um tendo um conjunto de atributos e uam medida de
semelhança entre eles, encontrar partições (clusters) que:
o Os pontos de dados numa partição são mais semelhantes que noutra
o Pontos de dados em partições separados são menos semelhantes que noutra
Téncicas com base em medidas de semelhança, por exemplo:
o Distância Euclidiana se os atributos são contínuos
o Distância de Hamming se os atributos são binérios
o Etc.
Tipos de atributos/características Atributos qualitativos ou categóricos
o Nomimal: possível diferenciar informação de um objeto de outro (≠, =)
Ex: números
o Ordinal: informação para ordenar objetos (<, >)
Bom, melhor, ótimo, etc.
Atributos numéricos ou quantitativos
o Intervalo: diferença entre os valores é significativa (+, -)
Ex: datas num calendário
o Rácio: ambas as diferenças e rácios são significativas (×, ÷)
Ex: quantidades monetárias, etc.
Atributos quantitativos
o Discreto (um conjunto numerável)
o Contínuo (geralmente, números reais)
Exemplo I: imagem
Uma imagem (ou um bloco) com tamanho NxN pode ser representada como um ponto num espaço
multidimensional.
o Cada ponto é um atributo
o Cada ponto é uma entrada no vetor de características X
o O nº total de atributos N2
Aplicações: reconhecimento facial, reconhecimento de escrita manual
Exemplo II: Classificação de documentos
Os documentos são descritos como vetores
o Cada componente do vetor representa um atributo
o O valor do atributo pode ser um número de ocorrência (ou medidas derivadas do nº de
ocorrências) da palavra no documento
o O conjunto de dados é esparso
Objetos: o modelo Dado um objeto → x descrito por atributos numéricos,
Cada atributo é uma entrada i no vetor
Objetos são pontos no espaço de dimensão N
Cada dimensão representa um atributo distinto
O conjunto de dados (com M objetos) é uma matriz
o Um objeto por linha (matriz M × N) ou
o Um objeto por coluna (matriz N × M)
Dimensão: nº de atributos N
Dispersão: conjuntos de dados quando a maioria de atributos é zero
Qualidade dos Dados Ruído e artefactos: distorção dos valores devido a “ruído”
Outliers: definidos nos diferentes níveis
o Objetos com características que são consideravelmente diferentes que a maior parte de
outros objetos de dados num dado conjunto de dados. Por vezes, é interessante (deteção
de fraudes)
o Valores do atributo podem não ser usuais comparando com os valores típicos
Valores em falta: objetos que não possuem atributos.
o Diversas técnicas: eliminar objetos de dados ou atributos; estimar esses valores em falta;
ignorar os valores durante a análise
Dados duplicados
Valores inconsistentes: valores de atributos que se encontram fora do seu domínio
Pré-processamento de Dados Agregação: combinar um ou mais atributos (ou objetos) em apenas um atributo (ou objeto)
Amosta: lidar com todos os dados deve ser proibitivo (estudos estatísticos utilizam geralmente
amostras com diversas estratégias: aleatório, substitutos, etc.)
Redução da dimensão
Criação de recursos
Seleção de um conjunto de recursos
Discretização e” binarização”: utilizar um conjunto de valores enumerável para represetar um
atributo.
Transformação de atributos: aplicar a função aos dados, tal como e x ou log (x ).
Classificação Binária: avaliação de desempenho Organizar a tabela de confusão com o resultado do conjunto de testes.
onde:
o TP – nº de Verdadeiros positivos
o TN – nº de Verdadeiros negativos
o FN – nº de Falsos negativos (a previsão ou classificador definiu que não pertencia à classe)
o FP – nº de Falsos positivos
As medidas mais conhecidas são:
o Acurácia (accuracy), especificidade (specificity), retorno (recall) e precisão (precision), …
Medidas de desempenho Acurácia: a fração de exemplos classificados corretamente
Especificidade: fração de exemplos negativos classificados corretamente
Retorno (recall): fração de exemplos positivos corretamente classificados.
Precisão (precision): fração de exemplos positivos que tenham sido classificados como positivos
Uma medida combinada: F-measure – é a média harmónica entre precisão e retorno.
Exemplo de medidas de desempenho
Conjuntos de dados não balanceados (nº de elementos de uma classe é maior que outra)
Acurácia não é uma boa medida
Se o nº de positivos é menor que o nº de negativos então a precisão e o retorno são as melhores
medidas
Matriz de confusão deve ser sempre utilizada
No exemplo: a classe positiva tem uma baixa previsão
Avaliação do desempenho dos classificadores Holdout: reserva 2/3 para treino e 1/3 para testes
Sub-amostras aleatórias: repetir o holdou (o desempenho é a média dos diferentes treinos/testes)
Validação cruzada (cross validation): particionar os dados em K conjuntos disjuntos, e em cada
iteração:
o K-fold: treino em K-1 partições, e o teste é na outra partição
o Leave-one-out: K=N, em cada ciclo é percorrido um exemplo diferente para o teste
o Como organizar os dados em partições?
Existem diferentes técnicas: amostras estratificadas é a mais comum
Boostrap: conjuntos de treino são formados por amostras com substituição
Método Holdout
Desempenho: conjunto de teste com N exemplo e C é o nº que foram classificados corretamente.
Acurácia estimada:
Desvio padrão
Intervalo de confiança
Intervalo de confiança
A distribuição padrão Gaussiana (com média zero e desvio padrão unitário)
com 95% de Z está compreendido em [1:96 1:96]
Normalização para a média zero e variância unitária
α = 0.05 → 5% nível de significância
(1 − α) = 0.95 → 95% nível de confiança
Intervalo de confiança: exemplos
Considerando um modelo que devolve uma acurácia de 80%
o Avaliado num teste de 100 ciclos:
Desvio padrão
Intervalo de confiança
(95% CL): 0.8 ± 1.96 × 0.04 −→ [0.72 0.87]
o Avaliado num teste de 1000 ciclos:
Desvio padrão
Intervalo de confiança
(95% CL): 0.8 ± 1.96 × 0.0126 −→ [0.78 0.83]
Validação cruzada K-fold
Conjunto de dados de tamanho N é dividido em K partições
o Conjunto de treino com (K-1) partições o Conjunto de teste com 1 subconjunto (o
que resta) o Repetindo o treino/teste K vezes e o
conjunto de teste ir alternando o As partições são organizadas em
estratificações: garante que cada classe é representada pela mesma proporção do conjunto global
Comparação de classificadores Comparação do desempenho de dois algoritmos de classificação
o Algoritmos são avaliados nos mesmos conjuntos de teste D1, D2 , . . . , Dk
Ex.: por validação cruzada)
o Utlizando o t-test com o objetivo de comparar as médias de ambos os classificadores
H 0 : µ1 = µ2 and H 1 : µ1 = µ2
A diferença no desempenho no mesmo subconjunto é dada por:
o Acurácia (ou erro) dos classificadores A e B no ciclo k
o A diferença dos pares
no ciclo k
Comparação de classificadores: t-test
Área A ≡ (1 − α), nível de confiança
Área P ≡ α, nível de significância
(K-1) graus de liberdade (DF)
Árvores de decisão O espaço de recursos é dividido em regiões únicas de termo sequencial.
Dado i, vetor de características, as decisões sequenciais são realizadas ao longo de um caminho de
nós de uma árvore adequadamente construída.
As decisões são aplicadas às características individuais e as pesquisas realizadas em cada nó são do
tipo:
o É recurso (atributo) xi > a ?, onde a é um limiar pré-escolhido (durante o treino).
Terminologia Uma família de classificadores não-lineares.
Sistemas de decisão em diversos níveis, em que cada classe é sequencialmente rejeitada, até que
finalmente é alcançada a classe aceitável
o Um nó interno é um teste num atributo
o O nó raíz não tem arestas de entrada
o Um ramo representa o resultado do teste de um atributo/recurso
o Um nó folha representa o nome da classe ou a distribuição do nome da classe
o Em cada nó, um atributo é escolhido para dividir, o mais possível, os exemplos de treino em
classes distintas
o Um novo caso é classificado segundo um caminho correspondente a um nó folha
Existem dois passos: construir a árvore (treinando o classificador) e aplicar o modelo aos novos
objetos (testar e classificar)
Um exemplo Árvores de classificação binária ordinária (OBCT)
A decisão baseia-se em:
o Hiperplanos, dividindo o espaço em regiões
o Se são paralelas aos eixos dos espaços
o Outros tipos de partições são possíveis, mas menos usuais
Nós e tipos de atributos
Atributos de valores discretos ou quantitativos: o teste é baseado num valor possível ou em listas
de valores de um atributo.
Atributos de valores contínuos: o teste baseia-se na desigualdade.
Factos de desenho Cada nó, k, está associado com um subconjunto Xk ao conjunto de treino X.
No nó K
o Xk é separado em dois (separações binárias) subconjuntos disjuntos e descendentes
Xk ,N ∩ Xk ,Y = ∅ Xk ,N ∪ Xk ,Y = Xk
onde os subconjuntos correspondem a ramos “Sim” ou “Não”
o O critério de divisão deverá ser adotado para a melhor partição dos Xk
o O critério de paragem da divisão adotado deve controlar o crescimento da árvore e um nó
deve ser declarado como final (folha)
o É necessária uma regra que atribui a cada classe um nó folha (final)
Entropia
Dado um conjunto de eventos e as probabilidades correspondentes, a entropia I é dada por
onde
I é máximo quando pi = pj ∀i , j incerteza do máximo (aleatoriedade).
I é mínimo quando pi = 1, pj = 0 j = i o resultado é já conhecido.
Exemplo:
⇒ EVENT ≡ CLASSES nos conjuntos.
Exemplo de aplicação
Nó raíz ⇒ 14 registos/objetos: 9 com YES e 5 com NO.
A Entropia é
No conjunto de treino: YES apresenta maior probabilidade.
Escolha do atributo OUTLOOK
A entropia “média” da partição com OUTLOOK
Então,
Então,
Então,
Então,
⇒ max (0.25, 0.05, 0.16, 0.04) , indica qual deve ser escolhido.
O procedimento é repetido para cada novo nó
Separar em paragens quando os dados não podem ser mais particionados
Nem todas as folhas devem ser puras. A classe da maioria dos elementos de um subconjunto.
Podar (pruning) Um fator crítico no desenho é o seu tamanho.
Os métodos de poda estão relacionados com o problema da necessidade de ajustar os dados.
Existem duas abordagens comuns:
o Pré-poda: condicionar a construção da árvore através de
Limitar o tamanho
Dividir apenas se um limiar é atingido
o Pós-poda: depois da construção, remover subárvores redundantes para melhorar o
desempenho.
Considerações finais
Vantagens
o Sem custos para a construção
o Extremamente rápido a classificar registos desconhecidos
o Fácil de interpretar em árvores pequenas
o Acurácia é comparável a outras técnicas de classificação para muitos conjuntos de dados
Desvantagens
o Pertencem à classe de classificações instáveis.
o Isto pode ser ultrapassado por um nº de técnicas de nivelamento.
Classificadores KNN
Exemplo
Os atributos (recursos) são medidas.
Medidas de similaridade
Dados dois objetos: x e y
Medidas de similaridade – dados não numéricos
Atributos Nominais (recursos): o domínio subjacente não é ordenado (ex.: cor, tipo sanguíneo)
Similaridade: contagem de correspondências
P – correspondência entre dois objetos com um total de N recursos
Classificador de Bayes Os vetores (objetos) são tratados como vetores aleatórios
Cada atributo I no vetor é uma variável aleatória
Atribuir ao objeto/padrão X a maior probabilidade das
classes disponíveis ω1, ω2 . . . ωM
Aplicação do Teorema de Bayes para calcular as probabilidades “à posteriori”
Assumindo que,
Probabilidade “à priori” P (ωi )
e a probabilidade p(x|ωi )
A evidência
De notar que p(x) é o denominador de P (ωi |x), ∀i portanto, a decisão
Como treinar? O conjunto de treino é utilizado para estimar
o Probabilidade “à priori”: P (ωi ): percentagem de objetos da classe ωi no conjunto de
treino
o A probabilidade p(x|ωi ) para diferentes estratégias
Paramétrica, assumindo distribuições Gaussianas
Não-paramétricas: conjunto de treino é utilizado para estimar diretamente p(x|ωi ).
Classificador Bayes Naïve Assume que os atributos são mutuamente independentes então
O desenho é menos exigente: os conjuntos de treinos podem ser menores.
Tem bom desempenho mesmo quando as independências consideradas são violadas.
Classificador Bayes Naïve – treino
Dado um conjunto de treino: com M objetos distribuídos por C classes:
o M1 pertence a ω1 e M2 a ω2 e assim por diante
Probabilidades “à priori”
(frequência relativa)
Funções de probabilidade
dos atributos
Classificador Bayes Naïve – teste
Dado uma instância/objeto calcular
Exemplo: .
Repetir os procedimentos para todos os atributos
⇒ p(x|ωi ) = p(x1 = 5|ωi )p(x2 =?|ωi ) . . .
Decisão : ⇒ maxi (p(x|ωi )P (ωi ))
Estratégia supervisionada: Regressão Prever um valor de uma dada variável contínua y baseada em valores de outras variáveis x,
assumindo um modelo linear (ou não linear).
y = wT x + b ou y = f (w, x)
Exemplos:
Prever quantidade de vendas de um novo produto baseado em novo marketing
Prever velocidade de vento baseado na temperatura, humidade, pressão do ar, etc.
Esta técnica é largamente utilizada em campos tais como estatística e redes neuronais.
Exemplo: o modelo mais simples Dado um conjunto de dados:
Modelo (descrição vetorial):
Com
Então
Novo x = 15, prevê y = 70
Modelos de regressão Regressão linear simples: prever o valor da variável x sendo dado o valor de x
Regressão linear múltipla: prever y sendo dados os valores de um vetor x = [x1 x2 . . . xN ]T
Regressão baseada em redes neuronais: dados valores de entrada, o resultado da rede é o valor a prever
Regressão polinomial: prever y como função polinomial de x
Modelos de regressão lineares O modelo linear é (caso linear simples é um caso particular quando w tem apenas uma única
entrada)
y = wT x + b
É necessário um conjunto de treino: (xk , yk ), k = 1, . . . K
O somatório do erro quadrático pode ser o critério para pesquisar os parâmetros (w e b).
Formulação da matriz
A matriz do métodos dos mínimos quadrados (K>N)
Onde,
A linha kth de X tem
A linha kth do vetor y tem yk , o valor que o modelo deve prever com xk
w , os valores do modelo
Sistema de equações: mais equações que a variável? Minimizando os mínimos quadrados
Multiplicando ambos os lados por XT
XT Xw = XT y ⇒ Rxx w = rxy
A solução é
Exemplo
Considerar o seguinte
x1 x2 y
−1 1
−1 1
1
−1 −1
1
1
1
1
−1
Calcular os pesos w tais que
y = b + w1x1 + w2x2
A solução dos mínimos quadrados é
y tem apenas dois valores ⇒ uma etiqueta (label)
0.5 − 0.5x1 − 0.5x2 = 0 ⇒ x2 = 1 − x1
A linha verde divide o espaço em duas regiões de modo que
A linha verde é a fronteira de decisão (decision boundary).
Classificação de Dados Gaussianos e de Bayes Assumindo que a função de probabilidade é similar (com médias diferentes).
A fronteira das regiões ocupadas pelos objetos de duas classes é um hiperplano.
Classificadores Lineares: Duas classes de problemas Funções lineares discriminatórias
Parâmetros do classificador:
w e b
Fronteira de decisão (hiperplano) g (x) = 0. Dado um conjunto de treino (objetos e etiquetas)
com objetos (x) e etiquetas (d).
Define uma função de custo para ser minimizada
Escolher um algoritmo para minimizar a função de custo
O mínimo corresponde à solução
Produto de pontos e fronteira de decisão Dados dois vetores: x e w
O produto de pontos de dois vetores (w, x)
wT x = w1x1 + w2 x2 + . . . + wN xN
A fronteira de decisão g (x) = 0 ⇐⇒ wT x + b = 0
Exemplo:
Espaço de dimensão N = 2
Classificadores lineares e algoritmos de treino Exemplos: perceptron, media dos mínimos quadrados (LMS) e máquinas de vetor de suporte (SVM).
Soluções “não-únicas”
o Perceptron – converge se o treino for linearmente separável
o LMS – é baseado na minimização do erro quadrático médio
Solução única
o SVM – é o classificador de margem máxima. O hiperplano que deixa a margem máxima de
ambas as classes
Funções lineares discriminantes: duas classes O resultado do classificador deve rotular as classes.
O resultado atual do classificador, wT x + b, e
Os resultados desejados, pro exemplo,
d = 1 if x ∈ ω1
d = −1 if x ∈ ω2
O conjunto de treino é organizado em pares (x1, d1 ), (x2, d2), . . ..
Algoritmo Perceptron Procedimento iterativo compreendido nos seguintes passos:
1. A iteração n lê um elemento (x )i do conjunto de treino
2. Processa o resultado yi dando o atual w(n)
yi = sign(wT x + wo )
onde a função sign(n) é
3. Compara y com o resultado desejado d.
A regra de atualização para cada peso wn+1 = w(n) + lrate (di − yi )xi
Factos sobre o algoritmo Converge se o problema for linearmente separável
(di − yi ) = 0, ∀i
Quando parar? Atribuir um número máximo de iterações.
Não existem critérios para medir a qualidade da solução.
Método dos mínimo quadrados
Se as classes são linearmente separáveis, o resultado do perceptron resulta em ±1
Se as classes não são linearmente separáveis, devemos calcular os pesos (w, b) que é a diferença
entre :
o O resultado atual do classificador, wT x + b, e
o O resultado desejado, por exemplo,
d = 1 if x ∈ ω1
d = −1 if x ∈ ω2
⇒ para ser pequeno ⇔ a função do CUSTO: J (w, b) = E [(wT x + b − d )2]
Algoritmos iterativos: critério de paragem Atualizar iterações dos parâmetros w = [w0 w1 . . . wN ], with w0 = b
1. N iterações: calcular w = w(n−1) + ∆w
2. Calcular o resultado para todos os pares do conjunto de treino: yk = wT xk
3. Calcular a função de custo J(W)
4. Erro diminui? Sim n ← n + 1 e volta ao passo 1
SVM e treino Objetivo: dadas duas classes linearmente separáveis, desenhar o classificador que deixe uma
margem máxima entre ambas as classes
Margem: cada hiperplano é caraterizado por: o Direção no espaço: w o Posição no espaço: b
Para cada direção w, escolher o hiperplano que deixa a mesma distância dos pontos mais próximos de cada classe.
A margem é duas vezes a distância referida.
A solução encontrada,
Minimizando
sujeito a: wonde o tamanho do conjunto de treino K,
di = ±1
Solução SVM O classificador hiperplano ideal de uma máquina de vetor suporte é única.
Com a otimização, o resultado é dado pelos multiplicadores de Lagrange dos quais
o Parâmetros SVM
.
o Quando λi = 0, o termo não contribui para o somatório.
o Se λi = 0 então di (wT xi + b) − 1 = 0 ⇒ xi encontra-se ao longo do hiperplano paralelo ao
hiperplano decisão dos vetores de suporte.
o O b é calculado utilizado os vetores de suporte (equação anterior)
Após o treino
o Os multiplicadores de Lagrange são o parâmetro para ser armazenado e os produtos dos
pontos tornam-se a chava principal para a manipulação dos dados (solução mais geral) ou
calcular w.
SVM: trabalhar com produtos de pontos Depois do “treino”, dado um novo objeto z forma dual do classificador linear é
Ks – Número de vetores de suporte λi = 0. Durante a fase de teste é necessário.
o Os vetores de suporte xi para determinar
o A complexidade da fase de teste é dependente do número de vetores de suporte (número
de produtos de pontos calculado)
Com outras abordagens o conjunto de treino não é necessário durante a fase de teste.
SVM: Problemas separáveis não-lineares
Os vetores de treino pertencem a uma de três possíveis categorias:
o Fora da margem dos quais se encontram classificados corretamente
(ξ = 0) o Dentro da margem dos quais se
encontram classificados corretamente
(0 < ξ < 1)
o Os que estão mal classificados (ξ > 1)
SVM (com C): treino Utilizando a forma dual onde as operações dos dados são produtos de pontos
o Treino pela maximização
o Sujeito a
Multiplicadores de Lagrange: 0 ≤ λi ≤ C
Os multiplicadores de Lagrange estão agora delimitados
Depois do treino, os multiplicadores de Lagrange estão relacionados com os vetores
o Dentro da margem ou mal classificados têm λi = C
No entanto, têm uma contribuição forte na solução final w
SVM: soluções
Tamanho do conjunto de treino: K = 250
SVM e C No caso linear, a margem depende da distribuição dos dados enquanto que no caso não-linear a variável
C controla a largura da margem (Classificadores de margens suaves).
C grande: forte penalização para os erros de classificação, pelo que a margem diminui.
Como utilizar SVM Treino SVM
o Escolher um kernel apropriado. Isto pressupõe implicitamente uma mapeamento para um
espaço maior a nível dimensional (ainda desconhecido).
o Definir os parâmetros do kernel e de C
o A escolha dos parâmetros é, geralmente, guiada por:
Validação cruzada de k-passos
o As maiores limitações do SVM é a carga computacional.
Teste SVM
o A complexidade depende do número de vetores de suporte
Problema multi-classes (c classes): o usual é olhar para o problema como dois problemas de classes
c (um contra todos)
SVM treino: outras considerações Geralmente, o treino é em modo de carga (batch), mas o maior problema é o alto custo computacional.
Devido a isso, são utilizadas diversas técnicas de decomposição.
o Começar com um subconjunto aleatório (do conjunto ativo) que caiba em memória. Aumenta a
otimização.
o Os vetores de suporte que resultam permanecem no conjunto ativo, enquanto os outros são
substituídos por novos (de fora do conjuntos).
o Repetir o procedimento.
O procedimento acima garante que a função custo diminui.
O algoritmo de Otimização minimal sequencial (SMO) é um exemplo que se aplica a um conjunto ativo
de duas amostras.
Redes neurais
Redes neurais: propriedades Modelo computacional, baseado na estrutura do cérebro
o Composto por um grande nº de elementos simples e de processamento altamente
interligados (neurónio)
o Cada neurónio tem múltiplas entradas e uma saída
o Cada neurónio trabalha em paralelo
o Os pesos das ligações são elementos adaptáveis
o Tolerância a falhas: um neurónio pode degradar-se sem comprometer o sistema global
Redes neurais: o neurónio
Função linear de ativação:
Funções não-lineares de ativação:
Redes neurais: perceptron Problemas de classificação binária
Dado um vetor de entrada (x), o resultado é positivo ou negativo
O w vai determinar o hiperplano que divide o espaço em duas regiões
O treino é apenas um algoritmo simples iterativo
O algoritmo converge se o problema for linearmente separável
O perceptron é o elemento básico de processamento das RN (NN)
Perceptron multi-classe de uma camada
Problemas de multi-classes
Neurónios de saída: um por classe
Cada unidade implementa uma função discriminante.
Decisão: um novo vetor de dados ωk é atribuído
à classe se yk > yj , ∀j = k
Para resolver problemas de separação não-lineares, a rede deve:
o Ter camadas ocultas
o Unidades ocultas devem ter funções de ativação não-lineares
Treinar redes multi-camada
Modos de operação
As redes têm duas maneiras de operar:
Feedforward – consiste em apresentar um padrão para as unidades de entrada e de passagem (ou
alimentação) dos sinais através da rede, com o objetivo de obter resultados.
Backpropagate – a aprendizagem supervisionada consiste em apresentar um padrão de entrada e
ir modificando os parâmetros (pesos) para minimizar a diferença entre o resultado calculado e o
desejado.
Treino Definir os parâmetros do algoritmo de treino
Inicialmente escolher aleatoriamente os pesos (Wk) para cada camada k
Objetivo: atualizar os pesos de modo a que o resultado do ANN seja consistente com os rótulos da
classe dos exemplos de treino.
Função de custo:
J (W ) = E [(yi − di )2] então
onde é o gradiente
Algoritmo Backprogation: começando com os pesos da última camada , em seguida, regressa ao
primeiro
A função custo tem um mínimo local
As principais filosofias:
Modo carga (batch)
o Os gradientes da última camada são calculados assim que todos os dados de treino
apareçam ao algoritmo, ou seja, somando todos os termos de erro.
Modo padrão ou modo online: os gradientes são calculados cada vez que um par de dados do
treino apareça. Estes gradientes são baseados em sucessivos erros individuais.
Outras questões:
Evitar o ajuste elevado e o treino intensivo: um problema que também pode acontecer noutros
algoritmos (por exemplo, árvores de decisão).
Considerações Antes do treino: definir a arquitetura da rede:
o o número de camadas ocultas (nenhuma ou uma, as escolhas mais comuns)
o o número de unidades nas camadas ocultas
o o número de entradas é o número de recursos
o o número de resultados em problemas de classificação é, geralmente, o número de classes
INPUT: 45 pixels and OUTPUT: 10 classes
Métodos Emsemble
Ideia: fornecer diversas soluções para o mesmo problema, e podermos combiná-las.
Construir um conjunto de classificadores a partir dos dados de treino
O rótulo da classe de objetos desconhecidos surge a partir da combinação de decisões de todos os
classificadores.
“Ensacar” (Bagging)
Fase de treino Ensacar ou agregação de bootstrap: pega em objetos do conjunto de treino cm substituição
Criar vários conjuntos de treino (tamanho é igual ao original) amostra bootstrap
Para cada amostra bootstrap (Bi ) um classificador (Ci ) é treinado
Florestas aleatórias (Random Tree) É um ensamble de árvores de decisão. Cada árvore de decisão é treinada
o Cria-se a amostra bootstrap do conjunto de treino
o Seleciona-se um subconjunto m(<< d) de recursos como potenciais nós de corte
o m é constante em todas as árvores
o não existe corte nas árvores
Testar um novo exemplo
o uma decisão é tomada através da votação entre as árvores de decisão
Boosting Um procedimento interativo para alterar, de uma forma adaptada, a distribuição dos dados de
treino, centrando-se nos objetos mal classificados
o Inicialmente, a todos os N exemplos de treino são atribuídos pesos iguais
o Ao contrário do “ensacar” (bagging), os pesos podem ser alterados no final do ciclo de
boost
Objeto 4: d ifícil classificar, por isso é mais provável que seja escolhido outra vez nas rondas seguintes.
Adaboost Trata-se de um algoritmo iterativo: treina ft , t = 1 . . . T , sendo dado o desempenho anterior dos
classificadores (fracos)
o A cada passo t
Modifica a distribuição da amostra de treino para favorecer exemplos difíceis (de
acordo com os classificadores fracos anteriores)
Treina um novo classificador fraco ft
Seleciona o novo peso αt através da otimização do critério global STOP quando for
impossível encontrar um classificador fraco que satisfaça a condição inicial
o Classificador final é a combinação ode todos os T classificadores
O classificador global pode lidar com milhares de recursos apesar de ter algumas
centenas de exemplos de treino
Motivation Information Technology allows the collection of large amounts of data.
Clustering goal: discovering structure in collections of data
o Marketing: finding clusters of clients with similar buying behavior.
o Medical: finding patients with similar symptoms.
o Document retrieval: finding documents with similar contents (travels, ...).
o Image retrieval: finding images with similar contents (sport, ...).
Clustering is an unsupervised technique
o no labeled data exploitation of similarities (or differences) between data points(objects).
Clustering: assumptions versus outcomes In clustering or unsupervised learning no training data, with class labeling, is available. The goal becomes:
Group the data into a number of sensible clusters (groups).
This unravels similarities and differences among the available data.
o To perform clustering of a data set, a clustering criterion must be adopted.
Different clustering criteria lead, in general, to different clusters.
Clustering: Applications Different Fields:
Engineering
Bioinformatics
Social Sciences
Medicine Data
Web Mining
Different motivations for clustering
Data reduction. All data vectors within a cluster are substituted (represented) by the
corresponding cluster representative. Hypothesis generation
Hypothesis testing
Prediction based on groups.
Clustering and Subjectivity
Depending on
the similarity measure the clustering criterion
the clustering algorithm
Different clusters may result, Subjectivity is a reality to live with from now on.
Clustering task stages Proximity Measure: This quantifies the term similar or dissimilar.
Clustering Criterion: This consists of a cost function or some type of rules.
Clustering Algorithm: This consists of the set of steps followed to reveal the structure, based on
the similarity measure and the adopted criterion.
Validation of the results. Interpretation of the results.
Categories of Clustering Algorithms Main Categories
Partition- based clustering:
o the number of clusters is usually pre-defined.
o an objective function is usually optimized.
Hierarchical- based clustering: successive development of clusters
o starting either by one cluster (with entire data set) or by clusters with single data points.
o applying a criterion to either splitting or merging the existent clusters
Density Based models:
o Model- based clustering: a mixture of probability clustering
Assuming a probability model for the data
Estimate the parameters of the probability functions with the data.
Types of Proximity measures o Objects: Given two data points xi and xj , the measure deals with the two points (i , j ).
o Sets: Given two data groups X = x1 , x2, . . . and Y = y1 , y2, . . . the measure addresses X and Y
or characteristics of the sets.
Partition-based Clustering: Hard clustering o Hard Clustering: Each point belongs to a single cluster. Given
X = x1 , x2 , x3 , . . . xN
o An m-clustering of X , is defined as the partition of X into m subsets (clusters), C1, C2 , . . . , Cm , so
that
Ci = ∅
∪C1 ∪ C2 . . . ∪ Cm = X
Ci ∩ Cj = ∅, i = j
o Data in Ci are more similar to each other and less similar to the data in the rest of the clusters.
Quantifying the terms similar-dissimilar depends on the types of clusters that are expected to
underlie the structure of X.
Partition Based-Clustering: fuzzy clustering o Fuzzy clustering: Each point belongs to all clusters up to some degree. A fuzzy clustering of X into
m clusters is characterized by m functions
Where µj are membership functions. Each xi belongs to any cluster ”up to some degree”, depending on
the value of µj (xi ).
o close to 1, high grade of membership xi to cluster j
o close to 0, low grade of membership xi to cluster j
Proximity measures (vectors): examples Each data example(object) is a vector
Comparing two vectors x, y:
Proximity measure d (x, y)
o Dissimilarity large: x and y are different
o Similarity large: x and y are similar
Proximity measures and data types Real or integer: euclidian distance; Manhattan (city block);
cossine distance etc.
o Normalization of the attributes (z-score).
o Binary Variables: Measures based on the contingency table
dissimilarity 1
r +s
q+r +s +t
number of ”negative” (0) not
important
Categorial: Normalized Hamming distance (normalized number of matches). Example: color
names
Ordinal: euclidian distance; Manhattan (city block); cossine distance etc. Often: normalization
to [0 1].
Example: Excellent, Good and so on
Mixed type attributes: the global proximity measure d (i , j ) a combination of measures applied
individually to each attribute
where δn
Partition-Based Algorithms K-means (apenas este será visto)
K-medoids
Fuzzy c-means
Kernel K-Means
K means
Partitional clustering approach
Each cluster is associated with a centroid (center point)
Each point is assigned to the cluster with the closest centroid
Number of clusters, K, must be specified
The basic algorithm is very simple
K means: Objective function
Given K clusters and a data set with N elements, the objective function is minimized
where uki element of the K × N partition matrix U and ck is the centroid of cluster k . The entries of U
are binary
uki = 1 if element i belongs to cluster k
uki = 0 if element i does not belong to cluster k
K means: implementation issues
Initial centroids are often chosen randomly. The centroid is (typically) the mean of the points in
the cluster.
Clusters produced vary from one run to another.
Closeness is measured by Euclidean distance, cosine similarity, correlation, etc.
K-means will converge for common similarity measures mentioned above. Most of the
convergence happens in the first few iterations.
Often the stopping condition is changed to until relatively few points change clusters
K-means has problems when
clusters are of differing sizes or densities
when the data contains outliers.
Alternative : K-Medoids Algorithm: average (centroid) substituted by median (medoid)
K means: example I
Different initializations: different solutions
Kernel K-means
Clustering the data after mapping to an higher dimensional space
X = x1, . . . , xN ⇒ Φ = φ(x1 ), . . . , φ(xN )
Using kernel function to compute dot products
k (x, y) = φT (x)φ(y)
the square of Euclidian distance turns manageable
d (φ(x), φ(y)) = (φ(x) − φ(y))T (φ(x) − φ(y))
For instance using RBF kernel the expression simplifies
d (φ(x), φ(y)) = φT (x)φ(x) − 2φT (x)φ(y) + φT (y)φ(y) = 2 − k (x, y)
Therefore all steps of K-means can be applied only that the centroid is never explicitly computed.
Example: Kernel K-Means
Proximity functions between sets
The goal is to compare data sets Functions based on vector mea- sures: any two vectors in two dis- tinct sets
min proximity function
max proximity function
average proximity function
centroid proximity function
Hierarchical clustering A set of nested clusters organized as a hierarchical tree. Can be visualized
as a dendrogram. A tree like diagram that records the sequences of merges or splits
or use Venn diagram. Similarities are not represented quantitatively
Types of hierarchical clustering Two main types of hierarchical clustering
Agglomerative:
o Start with the points as individual clusters
o At each step, merge the closest pair of clusters until only one cluster (or k clusters) left
Divisive:
o Start with one, all-inclusive cluster
o At each step, split a cluster until each cluster contains a point(or there are k clusters)
Traditional hierarchical algorithms use similarity or distance matrix
Merge or split one cluster at a time
Hierarchical clustering: Agglomerative More popular hierarchical clustering technique . Basic algorithm is straightforward:
Compute the proximity matrix: matrix with value of similarity function between pairs of
points.
Let it each data point be a cluster
Repeat
Merge the two closest clusters
Update the proximity matrix
Until only a single cluster remains
Key operation is the computation of the proximity of two clusters
Different approaches to defining the distance between clusters distinguish the different
algorithms
Hierarchical clustering: illustration
Hierarchal Clustering: Algorithms AGNES- AGglomerative NESting.
Application of minimum proximity function based on euclidian distance
DIANA -DIvisive ANAlysis.
Maximum proximity function based on euclidian distance
Hierarchal Clustering: remarks and constraints Time and space requirements:
Storage: O (N 2) space, N is the number of points.
Time: O (N 3 ). There are N steps and at each step the size, N 2, proximity matrix must be
updated and searched
Once a decision is made to combine two clusters, it cannot be undone
No objective function is directly minimized
Different schemes have problems with one or more of the following:
Sensitivity to noise and outliers
Difficulty handling different sized clusters and convex shapes
Breaking large clusters
Density- Based Clustering Density-based methods- clusters are formed based on the density of data points.
Given data point xk the -Neighborhood is
Nt (xk ) = x|d (x, xk ) ≤
If neighborhood is highly populated card (Nt (xk ) ≥ Nth
Yes: xk - Core Point No: xk - Border Point
Example: Nth = 5
q, CORE point
p, BORDER point
Density-Reachable: xi is density reachable
xi belongs to Nt (xk ) and
card (Nt (xk )) ≥ Nth
Key idea: find a chain of points
xk , xk +1 , . . . xi
where xk +1 is density-reachable from xk , and so on
p is density-reachable point from q
Clustering: Validation Compactness. Measuring how close the elements in a cluster are. Intra-cluster distances
Separability. Measuring how distinct the clusters are. Inter-cluster distances Davies- Bouldin index:
given cluster Ωi with centroid ci
Distance between centroids, minimum distances between the elements of two clusters, and so on
Other indexes: Dunn separation, Xie-Benie
Clustering and Neural Networks (SOM) Self-Organizing Feature Maps (SOM) developed by Kohonen are neural networks organized as a
grid (1D, 2D or 3D) of neurons
Goal: Show high-dimensional data in a low-dimensional structure maintaining topological
properties of the data.
Input of the neural network : data x = [x1x2 . . . xN ]T .
(i,j) refers to the position of the neuron in the grid. Connections
w(i , j ) = [w1(i , j )w2 (i , j ) . . . wn (i , j )]T
The output (i , j ) neuron is y (i , j ) = d (w(i , j ), x), usually d (.) is the Euclidian distance.
SOM: learning rule Competitive Learning or Winner-Take-All. Biologically inspired rule: neurons compete among themselves for
activation and only winners fire and strengthen its weights according.
Competition: the neuron whose w is close to the input
(i0, j0 ) = min(i ,j ) d (x, w(i , j ))
Updating rule: the winner (and usually its neighbhors) update the weights
o A function that defines neighborhood
Φ(i , j , i0, j0) = exp(−β[(i − i0)2 + (j − j0 )2]) Updating the weights
wnew (i , j ) = wold (i , j ) − ηΦ(i , j , i0, j0)(x − wold )
Learning terminates either by specifying the number (tmax ) of iterations or once there is no significant
changes in w
The value of Φ depends on the distance to the winner
Further remarks
Usually neighborhood size decreases with number of (t )iterations: β changes with t .
Learning rate η might also change along the iterations
SOM: example Clustering newspaper articles of 6 different sections of newspaper
Each Neuron is labeled with the majority classed of the associated inputs.
clusters of each category form continuous groups relative positions of different categories give
additional information: metro is related to other categories
