Abordagens de Mineração de Dados Multi Relacionalrosalvo.oliveira/Disciplinas/2012_2/...as...

Abordagens de Mineração de Dados Multi Relacional

Rosalvo Neto

Roteiro

1. Introdução

2. Motivação

3. Tipos de Abordagens

4. Classificação das abordagens

5. Descrição das abordagens

6. Estudo comparativo

Introdução

• Os dados estão contidos em banco de dados Relacionais;

• Muitas Relações;

• Muitos atributos;

• Muitas tuplas;

• Como extrair as informações de forma eficiente?

Motivação

50% - 80%

Source: excerpt of Fayyad et al. 1996

Tipos de abordagens

Proposicionalização Mineração de dados Multi Dimensional

Proposicionalização

Table 01 Table 02 Table N Table...

Result Table

AI Algorithm

Intelligent Systems

Mineração de dados Multi Relacional

Table 01 Table 02 Table N Table...

AI Algorithm

Intelligent Systems

Classificação das Abordagens Existentes

Multi Relacional Data Mining

Multi Dimensional DM

Proposicionalização ILP

Graph Mining

TupleID Propagation

Multi view Learning

LINUS DINUS

RelAggs FOIL CrossMine

CMVV

Inductive Logic Programming (ILP)

Indutive Logic Program (ILP) é um subcampo da área de aprendizagem de máquina que utiliza a programação em lógica como uma representação uniforme para exemplos, base de conhecimento e hipóteses

Inductive Logic Programming (ILP)

O problema de aprendizado em ILP é normalmente especificado como segue:

Dado: uma base de conhecimento B, expressa como um conjunto de definições de predicados, exemplos positivos E+ e exemplos negativos E-

Procurar: procurar uma hipótese H tal que o erro de h seja minimizado em exemplos futuros

Inductive Logic Programming (ILP)

Em ILP, h é usualmente um conjunto de clausulas de lógica de primeira ordem, e novos exemplos serão classificados como pertencente a classe positiva se e somente se ele é coberto por todas as clausulas de h.

LINUS

O LINUS é uma abordagem de Inductive Logic Program (ILP) que incorpora existentes sistemas de aprendizagem atributo-valor.

A ideia é transformar um problema descrito em ILP dentro da forma proposicional e resolver o problema através da aprendizagem de regras proposicionais.

LINUS Exemplos de treinamento Relações

filha (sue,eve). Pos progenitor (eve,sue). feminino (ann). masculino (pat).

filha (ann,pat). pos progenitor (ann,tom). feminino (sue). masculino (tom).

filha (tom,ann). Neg progenitor (pat,ann). feminino (eve).

filha (eve,ann). neg progenitor (tom,sue).

Variáveis Características proposicionais

X Y F(x) F(y) M(x) M(y) P(x,

x)

P(x, y) P(y,

x)

P(y,

y)

Classe

Sue Eve 1 1 0 0 0 0 1 0 Pos

Ann Pat 1 0 0 1 0 0 1 0 Pos

Tom Ann 0 1 1 0 0 0 1 0 Neg

Eve ann 0 1 0 0 0 0 0 0 Neg

RelAggs

Em sua abordagem é aplicada a ideia de agregação, comumente utilizada na área de Data WareHouse.

Exemplo

Cliente Parcela

RelAggs

Graph Mining

Mineração baseada em grafos é uma técnica que extrai as informações a partir de dados representados na forma de grafos estruturados. Um grafo pode ser definido pela equação G={V,E}, onde

V ={v1,v2,v3,…vn} é o conjunto ordenado de vértices do grafo e

E={e1,e2,e3,……..en} é o conjunto das bordas do grafo

Graph Mining

A C

B

A C

B

Propagation ID

Este é método faz a transferência de informação entre as diferentes relações por meio de junções virtuais;

Este método mostra-se menos custoso do realizar a

junção física tanto em termos de tempo quanto espaço;

Quando deseja-se realizar uma predição então

propaga-se os identificadores entre duas relações;

Propagation ID

Multi View Learning

A abordagem de classificação de múltiplas visões opera diretamente no banco de dados relacional com métodos convencionais de mineração de dados.

Multi View Learning

A abordagem é composta por cinco etapas:

1- Information Propagation Stage

2- Aggregation Stage

3- Multiple Views Construction Stage

4- View Validation Stage

5- View Combination Stage

Comparative Study between

Propositionalization and Multi

Relational Data Mining on a

Relational Database

Rosalvo Neto Paulo Jorge Adeodato Ana Carolina Salgado

Murilo Boratto

Outline

1. Objectives

2. Related Work

3. Compared Approaches

4. Database

5. Experimental Methodology

6. Results

7. Conclusions and Future Works

Objective

Performance Comparison:

- Propositionalization X Multi Relational Data Mining

- Binary Classification

- Database Benchmark (PKDD 1999)

- Credit Risk Domain

Related Work

Early Studies Recent Studies

Comparative Study between the same

approach

Comparative Study between different

approaches

Compared Approach - RELAGGS (RELational AGGregationS)

Compared Approach - Correlation-based Multiple View Validation

Source: excerpt of Guo and Viktor 2006

Database

Experimental Methodology

Cross Validation k-fold

Neural Network - MultiLayer Perceptron (MLP)

Kolmogorov-Smirnov Curve (KS)

Paired t-student test

Results

µd = µ1 − µ2 upper limit p-value

0,0805 ∞ 0,0181

Paired t-test result

Null Hypothesis:

Alternative Hypothesis:

Conclusions and Future Work

- There is indicative of Propositionalization outperforms Multi Relational Data Mining in Credit Risk Domain

- Domain Driven Data Mining (D3M)

- Investigate the performance of others AI Algorithms and others databases of the same domain