Jacques RobinCIn-UFPE

Arquiteturas de software Arquiteturas de software e linguagens de consultas parae linguagens de consultas para

descoberta de conhecimento em descoberta de conhecimento em BDBD

Especificação de uma tarefa Especificação de uma tarefa de descoberta de conhecimentode descoberta de conhecimento

1. Seleção dos dados relevantes:• qual fonte de dados? quais indivíduos ou grupos de indivíduos?

quais atributos? quais relações?• fácil com consultas SQL ou MDX (MultiDimensional eXpression)

2. Viés de aprendizagem:• qualquer método de mineração explora espaço de hipótese

potencialmente imenso• viés: especificação prévia de um sub-espaço alvo muito menor• ex, regras de associação com atributos obrigatórios na

premissa ou na conclusão, com número de premissas ou conclusões dado...

3. Métodos de mineração:• qual tipo de conhecimento (árvore de decisão? regras de

classificação? regras de associação?)• qual algoritmos de mineração (C4.5? PRISM?)

Especificação de uma tarefa Especificação de uma tarefa de descoberta de conhecimentode descoberta de conhecimento

4. Medida de interesse das estruturas de conhecimento mineradas:• Medida de legibilidade/interpretabilidade L:

concisão codificadas diretamente em termos de conceitos padrões da área

• Medida de confiança/acurácia C: ex, C(A B) = | A B | / | A |

• Medida de utilidade/aplicabilidade S: ex, S(A B) = | A B | / | DB |

• Medida de novidade N: com respeito a outras estrutura já mineradas com respeito a expectativa codificada como conhecimento prévio

• Interesse de estrutura I(E) = f( L, C, S, N)• Apresenta apenas estruturas de interesse superior a algum

limiar L: I(E) L

Da ta c ub eDe c isio n tre e

Ba r c ha rtPie c ha rt

CB

Ac la ss

yo ung

o ld 7861374

hig h lo winc o m e

ag

e

c la ss C

c la ss Bc la ss A

inc o m e ?

a g e ?

lo whig h

yo ung o ld

c la ss A

c la ss B

c la ss C

c la ss A

c la ss B

c la ss C

a g e

yo ung

o ld c o unt

hig h

1,402

786 2,188

lo w

1,038

1,374 2,412

A

1,402

0 1,402

B

1,038

0 1,038

C

0

2,160 2,160

inc o m e c la ss

C ro ssta b

Ta b le

a g e

yo ung yo ung o ld o ld

hig h lo w hig h lo w

A B C C

1,402 1,038 786 1,374

inc o m e c la ss c o unt

a g e (X, Ò yo ung Ó ) a nd inc o m e (X, Ò hig hÓ ) 5> c la ss(X, Ò AÓ ) a g e (X,Ò yo ung Ó ) a nd inc o m e (X, Ò lo wÓ ) 5> c la ss(X, Ò BÓ ) a g e (X, Ò o ld Ó ) 5> c la ss(X, Ò C Ó )

Rule s

Especificação de Especificação de uma tarefa uma tarefa

de descoberta de de descoberta de conhecimentoconhecimento

5. Formato de apresentação:• tabelas• histogramas, pizzas• gráficos 2D, gráficos 3D• texto, hipertexto• composição hipermídia

de vários formatos

Entrada, saída e parâmetros do Entrada, saída e parâmetros do processo de descoberta de processo de descoberta de

conhecimentoconhecimento

Base de dados

Conhecimentoprévio

Viés deaprendizagem

Medida deinteresse

Método demineração

Formato deapresentação

Interfacesde

entrada

Algoritmos de mineração

Especificaçãodos dadosrelevantes

Interfacesde

saída

Interface de controle

Conhecimentodescoberto

KDSE:Knowledge DiscoverySupport Environment

Dimensões descritivas da tipologia Dimensões descritivas da tipologia das arquiteturas de ambientes de KDDdas arquiteturas de ambientes de KDD

Variedade dos serviços implementados:• horizontal: numero de passos suportados no processo de KDD• vertical: diversidade das técnicas para cada passos

Grau de integração dos serviços implementados Abertura da arquitetura:

• controle: via GUI, via API para software externo, via linguagem de consulta declarativa, via regras declarativas

• entrada: via arquivo flat, via API para BD relacional, para data mart multidimensional, para BD não convencionais

• saída: via GUI, via arquivo exportado, via API para BD, via API para software externo

• código: fonte disponível ? orientado a objetos (linguagem, engenharia de software)? componentes reutilizáveis ?

Integração do KDSE com SGBD e SGBCIntegração do KDSE com SGBD e SGBC

SGBD

SGBC

KDSE

API

Arquivo

Arquivo

Arquivo

GUI

SGBCSemIntegração

ComIntegração

SoltaSGBD

SGBC

KDSEGUI

SGBC

API

API

API

API Software externo

IntegraçãoApertada

SGBD

KDSE

SGBD

KDSE SGBC

SGBDrelacional

Weka

Arquivo

Arquivo

GUI

API

API Software externo

Arquitetura do WekaArquitetura do Weka

Código:• fonte disponíveis (GNU license freeware)• hierarquia de interfaces e classes 100% Java

ServidorOLAP

Arquitetura do DBMinerArquitetura do DBMiner

Limitações:• implementado em C++• código fonte proprietário escondido• sem API para comunicação externa• interação apenas através do GUI

API

Algoritmosde mineração

APISGBDrelacional

GUI

InterpretadorDMQL

DBMiner

Arquitetura do Inteligent Miner da IBMArquitetura do Inteligent Miner da IBM

Interface dousuário

Visualizador

Definidor de Dados

Minerador Resultados

Biblioteca deProcessamento

Kernelminerador

ResultadosAPI (load)

ResultadosAPI (save)

Ferramentasde Exportação

Arquivos flat

Acesso a dados

Ambiente da camada API

CLIENTE

MetaDados

Base demining

Base dedados

Base dedados

SERVIDOR

Arquitetura do MATRIKSArquitetura do MATRIKS

Funcionalidades de uma linguagem Funcionalidades de uma linguagem declarativa de consulta para KDDdeclarativa de consulta para KDD

Especificar:• Dados relevantes:

idealmente baseado em linguagens de consulta de SGBD

• Tipo de conhecimento a minerar• Algoritmo(s) de mineração a usar• Conhecimento prévio:

idealmente baseado em linguagem de representação do conhecimento

• Viés de aprendizagemsobre o espaço de hipótese a explorar idealmente baseado em linguagem de representação do

conhecimento

• Medidas e limiar de interesse do conhecimento a apresentar• Técnica de validação a usar e divisão dos dados entre conjuntos

de treinamento e conjuntos de teste: simples treinar e testar, validação cruzada, leave-one-out, bootstrap

• Formato da apresentação do conhecimento minerado

Linguagens de consultas declarativas de Linguagens de consultas declarativas de descoberta de conhecimentodescoberta de conhecimento

Ainda:• próprio a cada KDSE, i.e.,

não existe padrão• ausente da imensa maioria

dos KDSE• quando presente

geralmente limitado a: um ou dois passos no

processo de KDD um ou dois tipos de

conhecimento a minerar não integrado com SQL ou

MDX

Principais:• Data Mining Query Language

(DMQL) do DBMiner grande variedade de tipo de

conhecimento integrado com SQL e MDX

• OLE DB for Data Mining do SQL Server 2000 da Microsoft

apenas 3 tipos de conhecimento

integrado com SQL mas aparentemente não com MDX !?

limitado demais para pegar como padrão de fato

DMQL: DMQL: especificação dos dados especificação dos dados relevantesrelevantes

use database database_name, | use data warehouse data_warehouse_name

from relation(s)/cube(s) [where condition] in relevance to att_or_dim_list order by order_list group by grouping_list having condition

DMQL: DMQL: especificação do tipo de especificação do tipo de conhecimento a minerarconhecimento a minerar

Caracterização:• Mine_Knowledge_Specification  ::=

mine characteristics [as pattern_name] analyze measure(s)

Discriminação:• Mine_Knowledge_Specification  ::=

mine comparison [as pattern_name] for target_class where target_condition  {versus contrast_class_i  where contrast_condition_i}  analyze measure(s)

Associação:• Mine_Knowledge_Specification  ::=

mine associations [as pattern_name]

DMQL: DMQL: especificação do tipo de especificação do tipo de conhecimento a minerar (cont.)conhecimento a minerar (cont.)

Classificação:• Mine_Knowledge_Specification  ::=

mine classification [as pattern_name] analyze classifying_attribute_or_dimension

Evolução:• Mine_Knowledge_Specification  ::=

mine prediction [as pattern_name] analyze prediction_attribute_or_dimension {set {attribute_or_dimension_i= value_i}}

DMQL: DMQL: especificação das especificação das hierarquias conceituaishierarquias conceituais

Uso de hierarquia:use hierarchy <hierarchy> for

<attribute_or_dimension>

Definição de hierarquias:define hierarchy time_hierarchy

on date as [date,month quarter,year]

define hierarchy age_hierarchy for age on customer as

level1: {young, middleAged, senior} < level0: alllevel2: {20, ..., 39} < level1: younglevel2: {40, ..., 59} < level1: middleAgedlevel2: {60, ..., 89} < level1: senior

define hierarchy age_hierarchy for age on customer as {age_category(1), ..., age_category(5)} := cluster(default, age, 5) < all(age)

define hierarchy profit_margin_hierarchy on item as level_1: low_profit_margin < level_0: all if (price - cost)< $50level_1: medium-profit_margin < level_0:

all if ((price - cost) > $50)

and ((price - cost) <= $250)) level_1: high_profit_margin < level_0: all if (price - cost) > $250

DMQL: especificação das medidas de DMQL: especificação das medidas de interesse e do formato de apresentaçãointeresse e do formato de apresentação

Medidas de interesse:• with <interest_measure_name>  

threshold = threshold_value• exemplos:

with support threshold = 0.05 with confidence threshold = 0.7

Formato: • display as <result_form>

Granularidade:• Multilevel_Manipulation  ::=   roll up on

attribute_or_dimension | drill down on attribute_or_dimension | add attribute_or_dimension | drop attribute_or_dimension

DMQL: exemplo de consultaDMQL: exemplo de consulta

use database AllElectronics_db use hierarchy location_hierarchy for B.addressmine characteristics as customerPurchasing analyze count% in relevance to C.age, I.type, I.place_made from customer C, item I, purchases P, items_sold S, works_at W,

branchwhere I.item_ID = S.item_ID and S.trans_ID = P.trans_ID

and P.cust_ID = C.cust_ID and P.method_paid = ``AmEx'' and P.empl_ID = W.empl_ID and W.branch_ID = B.branch_IDand B.address = ``Canada" and I.price >= 100

with noise threshold = 0.05 display as table

OLE DB for Data MiningOLE DB for Data Mining