Evaluating motor development

Antes de explicar o procedimento de eliminac¸˜ao das regras redundantes e mostrar quais tipos de regras ser˜ao exclu´ıdas, algumas definic¸˜oes s˜ao necess´arias. Considere X→ Y, X’ → Y como regras de associac¸˜ao, em que X’ ´e um superconjunto de X.

Definic¸˜ao 4 Uma regra de associac¸˜ao X’→ Y ´e uma Super-Regra Antecedente (super antece-

dent rule - super AR) se ela possui os mesmos itens no consequente e se seu antecedente X’ ´e um superconjunto de um antecedente X. Por outro lado, uma regra de associac¸˜ao X→ Y ´e

uma Sub-Regra Antecedente (sub antecedente rule - sub AR) se existe outra regra com o mesmo consequente e se X ´e um subconjunto de X’.

6.2 Algoritmo de Regras de Associac¸˜ao 75

Tabela 6.4: Exemplo de regras de associac¸˜ao para a Tabela 6.2.

N´umero Regra de Associac¸˜ao

1 atletaGanhaTrofeu(X, super bowl)→ atletaJogaEsporte(X, Futebol Americano) 2 atletaJogaLiga(X, nfl)→ atletaJogaEsporte(X, Futebol Americano) 3 atletaGanhaTrofeu(X, super bowl), atletaJogaLiga(X, nfl)→ atletaJogaEsporte(X,

Futebol Americano)

4 atletaJogaEsporte(X, Futebol Americano)→ atletaJogaLiga(X, nfl) 5 atletaJogaEsporte(X, Futebol Americano)→ atletaJogaLiga(X, nfl), atletaJogaTime(X,

pittsburgh steelers)

6 atletaJogaEsporte(X, Futebol Americano), atletaJogaTime(X, pittsburgh steelers)→

atletaJogaLiga(X, nfl)

Todas as super-regras antecedentes s˜ao super-regras, mas nem todas super-regras s˜ao

super-regras antecedentes.

Considere-se a tabela 6.4 que traz poss´ıveis regras de associac¸˜ao a partir dos itemsets da tabela 6.2. A regra 3 ´e uma super-regra antecedente das regras 1 e 2, e a regra 6 ´e uma super-

regra antecedenteda regra 4. No entanto, a regra 5 ´e uma super-regra, mas n˜ao uma super AR. Para ser uma super AR, a regra tem que ter mais de um item, pelo menos, no antecedente, o que n˜ao ´e o caso da regra 5.

O algoritmo de eliminac¸˜ao de regras redundantes consiste em remover super-regras antece-

dentes. Contudo, ele somente retira a regra do conjunto de regras de associac¸˜ao se ele encontra todas as suas poss´ıveis sub-regras antecedentes da super AR. Pelo exemplo da tabela 6.4, a regra 3 pode ser eliminada uma vez que as regras 2 e 3 s˜ao todas as suas poss´ıveis sub-regras antecedentes. No entanto, a regra 6 n˜ao pode ser retirada pois somente uma de suas poss´ıveis sub ARs foi gerada. Para popular uma BC, uma sub AR ´e mais eficiente do que sua super AR, o que justifica a eliminac¸˜ao da super AR.

Os exemplos da tabela 6.4 representam apenas super ARs contendo dois itens no lado do antecedente. Dessa forma, o algoritmo procura por sub-regras antecedentes de 1-itemset no lado do antecedente. Por´em, o que ocorre nos casos em que a super AR possua 3 itens (3- itemset) ou mais no seu antecedente? Para o caso de 3 itens no antecedente da super AR, devem existir sub ARs com 1 ou 2-itemsets no lado do antecedente, por exemplo. Para solucionar esse problema, o algoritmo calcula todas as poss´ıveis combinac¸˜oes de sub ARs conforme a equac¸˜ao 6.1, a qual representa o c´alculo matem´atico de uma combinac¸˜ao simples. O Algoritmo 5 mostra o pseudo-c´odigo desse m´etodo.

Combinac¸ ˜ao(n, k) = n!

6.2 Algoritmo de Regras de Associac¸˜ao 76

Algoritmo 5: Algoritmo de Eliminac¸˜ao de Regras Redundantes Entrada: listaDeRegras

Sa´ıda: listaDeRegrasSemRedundancia

1 todasCombinac¸˜oes = f also;

2 para i= 0 a numeroDeRegras − 1 fac¸a 3 regraAtual= getAssociationRule(i);

4 todasCombinac¸˜oes = encontreTodasComb(regraAtual); 5 se !(todasCombinac¸˜oes) ent˜ao

6 listaDeRegrasSemRedundancia.add(regraAtual); 7 fim

8 todasCombinac¸˜oes = f also; 9 fim

Para uma melhor compreens˜ao, considere a tabela 6.5 como exemplo. Na primeira linha, existe uma super-regra antecedente de 4 itens (4-itemset) no lado antecedente da regra. O algoritmo tem in´ıcio tentando encontrar todas as possibilidades de sub-regras antecedentes com 1 item (1-itemset). Pela equac¸˜ao 6.1, n ´e o tamanho de itens no antecedente da super AR, e k ´e o tamanho itens no antecedente da sub AR. Logo, existem 4 poss´ıveis sub ARs de 1-itemset no antecedente. Por´em, somente 3 regras foram geradas, e a super AR de 4-itemset no antecedente ainda n˜ao pode ser eliminada. A seguir, o algoritmo continua a procurar por todas as poss´ıveis combinac¸˜oes de sub ARs de tamanho 2 no lado do antecedente da regra. Para o exemplo da tabela 6.5, todas as 6 possibilidades foram geradas. Assim, a regra da primeira linha pode ser eliminada. Esse ´e um exemplo de super AR considerada redundante.

Se forem consideradas as regras com 3 itens no lado antecedente como super ARs, ambas s˜ao eliminadas. A regra a,b,c → e possui todas as possibilidades de sub ARs de tamanho 1 no antecedente, e a,b,d → e possui todas as possibilidades de tamanho 2. Para o primeiro caso, o algoritmo comec¸a investigando as possibilidades de sub ARs de tamanho 1. Como encontra todas as possibilidades nessa etapa, o algoritmo termina o procedimento e remove a regra do conjunto final de regras. J´a para a regra a,b,d→ e, o algoritmo s´o encontra todas as possibilidades de regras com suas sub ARs de tamanho 2, realizando uma iterac¸˜ao a mais.

A principal tarefa do algoritmo ´e encontrar todas as possibilidades sub ARs de tamanho 1 at´e (n-1) no lado antecedente, onde n ´e o tamanho do antecedente da super AR corrente (encontreTodasComb no Algoritmo 5). Caso todas as poss´ıveis combinac¸˜oes forem encontradas com 1-itemset, o algoritmo retira a regra de associac¸˜ao do conjunto. Caso contr´ario, ele tenta encontrar todas as possibilidades de sub ARs de 2-itemsets, e assim por diante.

Se forem comparadas as regras geradas pelo m´etodo aqui proposto e por algoritmos de FCIs e MFIs, ´e mais prov´avel que as super-regras sejam geradas nestes, enquanto aquele prop˜oe

6.2 Algoritmo de Regras de Associac¸˜ao 77

Tabela 6.5: Exemplo para eliminar regras super antecedentes

Tamanho do

Antecedente Regra de Associac¸˜ao N´umero de combinac¸˜oes 4 a,b,c,d→ e -

3 a,b,c→ e / a,b,d → e 4 2 a,b→ e / a,c → e / a,d → e / b,c →

e / b,d→ e / c,d → e 6 1 a→ e / b → e / c → e 4

elimin´a-las, mantendo as sub ARs m´ınimas, que s˜ao mais eficazes para popular grandes BCs. Por exemplo, se algoritmos de FCIs MFIs descobrirem somente o itemset (a,b,c,d,e) como closed e m´aximo, ele s´o poderia popular a BC com o valor e se todos os outros itens aparecerem na mesma instˆancia na base de dados. Contudo, ao utilizar a t´ecnica de eliminac¸˜ao de regras redundantes descrita neste trabalho, a regra a,b,c,d→ e ´e eliminada, resultando somente nas sub ARs de tamanho 2 no lado antecedente como descrito anteriormente. Dessa forma, quando uma das seis possibilidades de sub ARs estiver presente em uma instˆancia, o algoritmo preenche o conjunto de dados com o valor de e quando necess´ario. Isso contribui para popular grandes BCs compostas por valores ausentes mais do que quando usadas regras de associac¸˜ao extra´ıdas por algoritmos de FCIs e MFIs.