Subgroup Discovery driven by a
Property of Interest
Paulo J Azevedo
INESC-Tec, HASLab
Departamento de Informática
1
Subgroup Mining
Subgroup Mining
• Objectivo: Detecção de subpopulações em que os
valores de uma propriedade em estudo se desviem do
expectável
• i.e. desvio em relação a uma população referência, por
exemplo a população geral em estudo.
• Representação deste fenómeno usando padrões
específicos: tipicamente regras.
• Exemplos:
• Sex=female  Wage: mean=$7.9 (overall mean=$9.02)
• non-smoker & wine-drinker  life-expectancy=85
(overall mean=80)
Subgroup Mining
2
Pattern Mining
• Procurar padrões (relações entre os elementos atómicos
que constituem os dados) interessantes/surpreendentes.
• Padrões <=> estrutura nos dados.
• Tipicamente representem associação/coocorrência/correlação/etc entre elementos atómicos dos
dados. Métodos de extracção por força bruta.
– Exemplo: Motifs em dados de sequências de DNA – fragmentos
de DNA fortemente conservados (alta incidência) ao longo de
diferentes genes.
• Vários tipos de padrões:
–
–
–
–
–
Termos frequentes (regras de associação),
Sequências e Motifs
Grafos
Séries Temporais
etc.
Subgroup Mining
3
Regras de Associação
• Problema típico:
1 1901,1881,199,901
2 901,1661
3 676,199,177,100
…..
…
120099 78,1881,199,8
Número da
transacção
• O marketing da cadeia de
Hipermercados pretende
fazer um estudo de
comportamento de compras.
• Tem acesso aos dados
representativos dos “cestos
de compras” (basket data)
item
901 & 199  1881 (s=0.3,conf=0.9)
• Medidas de interesse:
• incidência (suporte)
• Previsibilidade (confiança)
4
Subgroup Mining
Medidas de Interesse
•
•
•
•
•
Tipicamente recorre-se a uma medida de incidência para definir quais
as associações relevantes.
A mais popular é o suporte (contagem) dos itemsets i.e. associações
As regras são qualificadas por uma medida de interesse
(previsibilidade, solidez ou força da regra).
Normalmente é usada a confiança (probabilidade condicional) =
s(AC)/s(A)
Assim, a regra de associação:
901 & 199  1881 (s=0.3,conf=0.9)
•
Deve ser lida como: a compra conjunta dos produtos 901, 199 e 1881
ocorre em 30% das transacções. Por outro lado, verifica-se que 90%
das transacções que contêm 901 e 199 também contêm o produto
1881.
•
Outra leitura: 90% da sub-população definida pelos produtos 901 e 199
consomem 1881.
•
esta e
O utilizador fornece valores limites para a Relevante
pesquisa:para
suporte
palestra pois vamos falar de
confiança mínimos.
detecção de subgrupos
Subgroup Mining
5
Podemos ver o problema pela perspectiva do
espaço de pesquisa (de termos frequentes) a
explorar
ABCD
Seta indica
inclusão
matemática
Itemset
ABC
AB
ABD
AC
A
ACD
AD
B
BCD
BC
C
BD
CD
D
Item
6
Subgroup Mining
Algoritmos
• Extracção de termos frequentes (itemsets)
i.e. associações (alta complexidade computacional)
• Geração de regras (baixa complexidade)
• Selecção de regras “interessantes”
Primeiro problema exaustivamente estudado pela
comunidade com centenas de contribuições.
Algoritmo seminal: Apriori [Agrawal&Srikant94].
Faz uso da propriedade de anti-monotonia do
suporte:
Se X ⊆ Y então s(X) ≥ s(Y)
7
Subgroup Mining
Aplicação da Propriedade Anti-monótona
ABCD
ABC
AB
ABD
AC
A
ACD
AD
B
BCD
BC
C
BD
CD
D
Infrequente
8
Subgroup Mining
Cálculo de termos frequentes
• Estratégias bottom-up: Apriori-like
– Vários passagens pela base de dados
– Geração de “candidatos”
• Estratégias depth-first
– Uso de representações verticais dos dados
e.g. listas de ocorrências, bitmaps, diff-sets,
etc.
– Melhores oportunidades de pruning
– Adequada para obter algoritmos “rule-based”
9
Subgroup Mining
Graph Mining
• Extracção de fragmentos (subgrafos) significativos (frequentes) de
uma base de dados de grafos.
• Possíveis aplicação na web e em redes sociais em geral.
• Enumeras aplicações em dados biológicos. Exemplo de Unfolding:
10
Subgroup Mining
Graph Mining
• Exemplo de identificação de um subgrafo que persiste ao longo do
processo descrito anteriormente
11
Subgroup Mining
Séries Temporais
• Time Series(TS): um formato de dados comum em
diversos domínios (biologia, física, mercado de títulos,
network monitoring,…),
• Colecção de observações feitas sequencialmente ao
longo do tempo. Tipicamente os dados representam uma
propriedade numérica.
• Tópico em grande expansão (e.g. indexing, clustering,
classification, …)
• Mining previously unknown patterns;
– Episodes : subsequences that repeat in an unique and longer
sequence;
– Motifs : subsequences that repeat in several related sequences;
12
Subgroup Mining
Motifs & Episodes
Motifs
Episodes
13
Subgroup Mining
Expectations…
Can
Canbe
bedeceived!!!!!!!!
deceived!!!!!!!!
Subgroup Mining
14
Factores de Interesse
• Número de regras derivadas é facilmente
insustentável (explosão combinatória)!
• e.g. dados de retalho
– 3182 produtos (items)
– 23182 número de regras possíveis!
– #regras com <= 4 items no antecedente > 1016
– Alta probabilidade de improvável coocorrência real i.e serem falsas descobertas !
15
Subgroup Mining
Falsas Descobertas
• Queremos identificar associações que
ocorrem nos fenómenos que dão origem
aos dados em estudo.
• O intensivo processo de procura
associado à derivação de regras de
associação resulta num alto risco de
falsas descobertas:
– i.e. associações que aparentam existir na
amostra em estudo mas que não ocorrem no
fenómeno que lhe dá origem.
16
Subgroup Mining
Exemplos
• Suporte (frequência) dos items de uma regra
pode ser prevista assumindo a independência de
um subconjunto deles:
homem & miopia & óculos  cancro_próstata
(homem & cancro_próstata ) versus (miopia & óculos)
• Regras redundantes: (items no antecedente
explicam outros items)
Ex: grávida  retenção_de_liquidos e
grávida & mulher  retenção_de_liquidos
Descartar regra redundante x  y se:
Ǝz ∈ x : s(x  y) = s(x - z  y)
• Regras não Produtivas:
homem & psa_alta & diabetes  cancro_próstata
homem & psa_alta
 cancro_próstata
Subgroup Mining
conf=0.84
17
conf=0.85
Regras Significantes
• Medir a significância do ganho preditivo da
especialização. [Webb2007]
• Regra
ant  cnq conf = v1
é significante se
anti  ant : anti  cnq conf  vi
todos os valores (v1 – vi) são estatisticamente
18
significativos.
Subgroup Mining
Regras Significantes
• Aplicar teste de hipótese durante o processo de
pesquisa para determinar significância e.g. teste
exacto de Fisher.
• Com um p-value exacto podemos controlar o
problema das múltiplas hipóteses (inflação do erro
tipo I):
– Para um valor crítico α e n regras a derivar, a
probabilidade
de obter uma falsa descoberta
n
é 1 – (1 – α)
– Necessidade de ajustar o valor crítico (α)
• Com este tipo de filtros controlamos o sobreajustamento (overfitting) do modelo. Regras mais
específicas tem de produzir uma mais valia.
19
Subgroup Mining
Framework
• Derivação de subgrupos usando um
algoritmo de extracção de regras de
associação.
• Algoritmo rule-based.
• Detecção de desvios (interesse) à custa
de testes de significância estatística.
• Controle de especialização (overfitting)
usando o mesmo tipo de teste estatístico.
• Vários tipos de regras dependendo da
aplicação específica.
20
Subgroup Mining
Detecção de Subgrupos
• Derivar regras para identificar subpopulações
interessantes que ocorrem nos dados em
estudo
caracteristicas_descritores_do_subgrupo  poi
• Propriedade de interesse (poi) pode ser um
atributo categórico ou numérico, uma
expressão de restrição ou até um contraste.
• Várias estatísticas associadas às regras
21
Subgroup Mining
Propriedades de interesse
Numéricas
• Quantitative Association Rules [Aumann&Lindell2003]
• e.g:
fumador=n & consumo_vinho=s  espera_vida=85 (overall=80)
Sex=female  Wage: mean=$7.9 (overall = $9.02)
• Interessa da regra determinado por teste comparativo entre média da
poi do subgrupo e a médio do seu complemento.
• Impact Rules [Webb2001]
– Interesse determinado pelo impacto da regra
– Impact(Regra) = [avg(Regra) – avg(po_geral)] x sup(ant(Regra))
Subgroup Mining
22
Regras de Distribuição
[Jorge&Azevedo2007]
• O consequente é uma distribuição,
• Possibilita a análise de distribuições segundo parâmetros tipo
Skewness (grau de assimetria) e Kurtosis (grau de
afunilamento)
•
Uso do teste Kolmogorov-Smirnov, para avaliar se regra é
interessante.
•
Noção de interesse: Regra é interessante se o p-value do
Distribuição geral
da população
Distribuição do
subgrupo da regra
ks-test(apriori,rules-dist) < α
• Especialização das subpopulações também controlado por
um teste de KS (KS-improvement).
• Várias aplicações
Subgroup Mining
23
Case Study
• Descripitive data mining
– dataset: Determinants of Wages from the 1985 Current Population
Survey in the United States, a.k.a. Wages
– property of interest: WAGE
• Rule discovery
–
–
–
–
min-sup=0.1, KS-int=0.95
numerical attributes in the antecedent were pre-discretized
compact internal representation of rules
rules can be output as text or graphically
24
Subgroup Mining
Uso de Regras de Distribuição
• antecedente
– Indivíduos com 13 a 15
de formação escolar
– Não são do sul dos
EUA
• consequente
– wage (rendimento/h):
distribuição é melhor
que população geral
mas continua
concentrada nos
mesmo intervalo.
25
Subgroup Mining
Uso de Regras de Distribuição
• antecedente
– Refinamento do anterior
– Raça é caucasiana
• consequente
– Melhoria da distribuição
em relação à regra
anterior.
– regra passa o teste de
KS-improvement em
relação à anterior.
– Rendimentos continuam
concentrados no mesmo
intervalo.
26
Subgroup Mining
Uso de Regras de Distribuição
• antecedente
– jovens
• consequente
– Baixo rendimento,
muito concentrado.
– Sugere algumas
modas secundárias.
27
Subgroup Mining
Max Leverage Rules
• [Jorge&Azevedo2011]
• Regras do tipo:
ant  A ϵ I,
onde I é o intervalo que define o máximo valor de
leverage (add value) de A para o antecedente ant,
onde A é a nossa poi.
• Regras derivadas da regra de distribuição correspondente.
• Intervalos que maximizam leverage /(added value) são obtidos
do teste KS.
• AV(A  C) = conf(AC) – sup(C).
28
Subgroup Mining
Max Leverage Rules
Exemplo
(Cov=0.226 Lev=0.148 AV=0.653 Conf=0.922)
HP=(132.5-inf) & Ncy=(5.5-inf) & Year=(-inf-79.5]  MPG < 18
A regra declara que carros com potência (HP) acima de 132.5, mais de 5 cilindros
(Ncy) e ano de construção (Year) antes de 1980 tendem a ter um desempenho (MPG)
inferior a 18 quando comparados com um carro genérico (população total).
Um carro genérico tem muito menor probabilidade de ter tão mau desempenho. Na
verdade, a probabilidade de um carro genérico ter tão baixo desempenho é 65,3%
(Added Value) abaixo da probabilidade do carro descrito pela regra.
29
Subgroup Mining
Regras de Contrastes
• Rules for Contrast Sets [Azevedo2010]
• Descrever a diferença entre grupos de contraste.
• Um conjunto de contraste é uma conjunção de
características que descreve uma subpopulação
que ocorre com diferentes proporções ao longo
dos diferentes grupos.
• Exemplo de contraste de indivíduos entre grupos:
– a diferentes instâncias temporais (total de vendas em
1998 versus 1999),
– diferentes localizações (encontrar características
distintas da localização do gene x no DNA humano
em relação ao DNA dos ratos),
– ao longo de diferentes classes (diferenças entre
loiras e morenas).
30
Subgroup Mining
Regras de Contraste
• As características da subpopulação a encontrar
(contrast sets) são interessantes (significativas) se as
proporções da ocorrência desses indivíduos ao longo
dos diferentes grupos for significativamente distinta.
• i.e. subpopulação não independente de pertença ao
grupo. Significância obtida por um teste de Fisher.
Gsup = 0.17191 | 0.04121 p = 1.1110878451E-017
Gsup = 0.17191 | 0.01681 p = 3.0718399575E-040
Sup(CS) = 0.03097
education=Doctorate >> education=Masters
education=Doctorate >> education=Bachelors
 workclass=State-gov & class > 50K.
• Controle de especialização do contrast set
implementada usando o mesmo teste de Fisher.
Subgroup Mining
31
Sumário
• Subgroup Mining para a detecção de
desvios em subpopulações.
• Várias aplicações e.g. census,
bioinformática, etc
• Processo de Pattern mining controlado
pela propriedade de interesse em estudo.
• Exemplo com regras de associação como
motor gerador de subgrupos interessantes
em relação a uma poi.
32
Subgroup Mining