Redes neurais de maneira fácil (Parte 18): Regras de associação

Conteúdo

• Introdução
• 1. Regras de associação
• 2. Algoritmo Apriori
• 3. Algoritmo FP-Grows
• Considerações finais
• Referências

Introdução

À medida que a quantidade de informações a serem analisadas aumenta, aumenta também o interesse pelo método de aprendizado não supervisionado. Nos últimos artigos desta série, já vimos algoritmos de agrupamento e redução de dimensionalidade, que estão relacionados a métodos de aprendizado não supervisionado. Neste artigo, continuamos nosso estudo de métodos de aprendizado não supervisionado. E o convido a aprender sobre outro tipo de problema a resolver, a análise das regras de associação. Este tipo de tarefa foi primeiramente formulado no varejo para analisar cestas de compras, como uma busca dos conjuntos de itens mais frequentes. Atualmente, algoritmos para resolver este tipo de problemas são amplamente utilizados em vários campos. Vejamos as possibilidades de usar esses algoritmos na negociação.

1. Regras de associação

A análise de regras de associação faz parte das tarefas aplicadas de mineração de dados e é uma das principais delas, pois permite identificar correlações entre os dados em bancos de dados volumosos.

Esse tipo de tarefa foi formulado e definido pela primeira vez no varejo. Quando os profissionais de marketing se depararam com a questão de quais benefícios comerciais podiam ser derivados da análise de um grande banco de dados de operações em dinheiro, ou seja, de caixa. Enquanto anteriormente apenas as vendas totais eram analisadas, a análise das receitas de caixa dos clientes abriu novos horizontes. Uma vez que permitiu analisar conjuntos separados de produtos adquiridos pelos clientes.

O primeiro algoritmo foi criado por um grupo de desenvolvedores da IBM em 1993. E foram formulados os principais postulados, que formaram a base de todo um grupo de algoritmos.

Antes de tudo, as regras encontradas com algoritmos devem ser muito frequentes. Ou seja, não devem ser aleatórias e devem ser repetidas pelo menos um determinado número de vezes na base de dados analisada. Para ser confirmadas na prática, por assim dizer. E do ponto de vista estatístico, a amostra de transações que contenha tal regra deve ser representativa. Para atender a esse requisito, todos os algoritmos de busca de regras de associação possuem um parâmetro de suporte mínimo (MinSup - minimal support), que indica em frações de "1" a razão entre a frequência de ocorrência da regra e o número total de transações no amostra analisada.

E aqui precisamos entender que, tendo um conjunto de 3 características A, B e C, de acordo com as regras da combinatória, sem levar em consideração a posição dos elementos, podemos obter 7 conjuntos diferentes contendo de 1 a 3 dessas características. À medida que o número de características aumenta, também aumenta o número de combinações possíveis. E levando em consideração o volume de bancos de dados, o recálculo direto da frequência de ocorrência de cada conjunto de características se torna uma tarefa bastante dispendiosa, muitas vezes até irreal. É por esse motivo que os autores tiraram proveito da propriedade anti-monotônica.

Se apenas um conjunto de características A ocorrer no banco de dados, então sua frequência será igual à frequência da própria característica A. Se o número de conjuntos encontrados for maior, sua frequência só poderá ser menor. Uma vez que o número total de suas ocorrências na amostra analisada será igual ao número de ocorrências da característica A. Assim, se a frequência de ocorrência de qualquer característica for menor que o suporte mínimo, então, consequentemente, a frequência de todas as variantes possíveis de conjuntos contendo essa característica será menor que o suporte mínimo. Assim, basta calcular a frequência de ocorrência de cada característica para eliminar uma parte significativa dos conjuntos aleatórios, que não têm valor prático para nós.

Como se pode ver, aqui os algoritmos de busca de regras de associação são muito diferentes de todos os algoritmos considerados anteriormente. Anteriormente, tentávamos aproveitar ao máximo todos os dados disponíveis. Em seguida, os algoritmos de busca de regras de associação filtravam imediatamente as características aleatórias (ruído).

O segundo parâmetro utilizado em todos os algoritmos para busca de regras de associação é o grau mínimo de confiança na regra (MinConf - minimal confidence). Que também é indicado em frações de 1. Para explicar este parâmetro, deve-se dizer que cada regra consiste em 2 partes: uma premissa e uma consequência. Tanto a premissa quanto a consequência podem consistir em uma característica ou em todo um conjunto de características. No caso geral, a regra parece que, se a premissa for verdadeira, muitas vezes haverá uma consequência.

Observe aqui que a probabilidade de haver uma 'consequência' quando há uma 'premissa' não é 100%. Todavia a probabilidade mínima de ocorrência de uma "consequência" é definida pelo parâmetro MinConf. É quando esse parâmetro é atendido que a regra é considerada válida e é armazenada no array de regras. Definido como a relação entre a frequência da regra e a frequência com que a premissa aparece.

2. Algoritmo Apriori

Provavelmente um dos algoritmos mais famosos para encontrar regras de associação é o algoritmo Apriori, que foi proposto por Rakesh Agrawal e Ramakrishnan Srikant em 1994. O algoritmo é baseado em um processo iterativo de busca dos padrões mais frequentes no banco de dados. Com a subsequente extração das regras dentre os padrões selecionados.

Para entender melhor, vejamos o funcionamento do algoritmo em um pequeno exemplo de 10 transações com 5 caraterísticas.

ID da transação	Conteúdo
T1	BCDE
T2	BCD
T3	B
T4	BCD
T5	D
T6	ACD
T7	BCDE
T8	BCE
T9	CDE
T10	AD

Introduzimos no problema as constantes do suporte mínimo 0,3 e o grau de confiança mínimo 0,7 (30% e 70%, respectivamente).

Deve ser entendido que todos os algoritmos para busca de regras de associação funcionam com arrays binários. Portanto, para começar, vamos apresentar os dados acima na forma de uma tabela binária.

ID da transação	A	B	C	D	E
T1	0	1	1	1	1
T2	0	1	1	1	0
T3	0	1	0	0	0
T4	0	1	1	1	0
T5	0	0	0	1	0
T6	1	0	1	1	0
T7	0	1	1	1	1
T8	0	1	1	1	0
T9	0	0	1	1	1
T10	1	0	0	1	0

A partir desta tabela, é fácil calcular que a caraterística A ocorre apenas 2 vezes e seu suporte é de 0,2 ou 20%. Da mesma forma, calculamos o suporte para as caraterísticas restantes: B — 0.6, C — 0.7, D — 0.8, E — 0.4. Como se pode ver, apenas a caraterísticaA não atende ao requisito mínimo de suporte e a excluímos do processamento adicional por causa da propriedade anti-monotônica.

Dos elementos restantes, fazemos candidatos para padrões que ocorrem com frequência. Na etapa anterior, identificamos caraterísticas que ocorrem com frequência. E de acordo com o algoritmo, definimos conjuntos de 2 caraterísticas como candidatos: BC, BD, BE, CD, CE, DE.

Agora precisamos iterar em todo o banco de dados e determinar o suporte para cada um dos candidatos selecionados.

ID da transação	BC	BD	BE	CD	CE	DE
T1	1	1	1	1	1	1
T2	1	1	0	1	0	0
T3	0	0	0	0	0	0
T4	1	1	0	1	0	0
T5	0	0	0	0	0	0
T6	0	0	0	1	0	0
T7	1	1	1	1	1	1
T8	1	0	1	0	1	0
T9	0	0	0	1	1	1
T10	0	0	0	0	0	0

Como se pode ver, o suporte de todos os nossos candidatos cumpre as condições mínimas de suporte: BC — 0.5, BD — 0.4, BE — 0.3, CD — 0.6, CE — 0.4, DE — 0.3. Mas esta situação nem sempre é possível. Ao resolver problemas práticos, alguns candidatos são mais propensos a serem eliminados.

Em seguida, continuamos o processo iterativo e desta vez compilamos conjuntos candidatos de 3 caraterísticas. Para fazer isso, pegamos os padrões frequentes selecionados na iteração anterior e combinamos pares que diferem em apenas um elemento. Assim, determinamos 4 candidatos: BCD, BCE, BDE, CDE.

E de acordo com o algoritmo Apriori, novamente temos que percorrer todo o banco de dados e determinar o suporte para todos os novos candidatos.

ID da transação	BCD	BCE	BDE	CDE
T1	1	1	1	1
T2	1	0	0	0
T3	0	0	0	0
T4	1	0	0	0
T5	0	0	0	0
T6	0	0	0	0
T7	1	1	1	1
T8	0	1	0	0
T9	0	0	0	1
T10	0	0	0	0

Como resultado, receberemos o seguinte suporte para nossos candidatos: BCD — 0.4, BCE — 0.3, BDE — 0.2, CDE — 0.3. Nesta iteração, o suporte para o conjunto BDE não atende ao requisito mínimo de suporte e o excluímos. Os candidatos restantes passam para o status de padrões frequentes.

Na próxima iteração, compilamos conjuntos candidatos de 4 caraterísticas. Nesse caso, a partir dos padrões selecionados na iteração anterior, podemos fazer apenas um candidato BCDE. Mas antes de percorrermos todo o banco de dados novamente para calcular o suporte para este candidato, vamos dar uma olhada em seu componente BDE. Na última iteração, eliminamos esse candidato porque seu suporte era 0,2, que está abaixo do requisito mínimo de suporte de 0,3. Portanto, conforme a propriedade anti-monotônica, o suporte do candidatoBCDE não pode ultrapassar 0,2. E isso está abaixo do nível mínimo de suporte.

Como não temos mais candidatos, paramos o processo de busca de padrões frequentes e passamos para o segundo subprocesso, isto é, determinamos as regras a partir dos padrões frequentes selecionados. Para fazer isso, vamos dividir os padrões selecionados em uma premissa e uma consequência. Em seguida, determinamos o grau de confiança para cada regra e o comparamos com o nível mínimo de confiança exigido.

Construiremos as regras sequencialmente para cada item e conjunto. Como no primeiro estágio filtramos todos os padrões com a característica A (seu suporte abaixo do requisito mínimo), começamos a definir as regras com a caraterística B.

Dentre os padrões selecionados, escolhemos todos aqueles que contêm o item em análise. Dos padrões, extrairemos a caraterística B para a consequência, e o resto será a premissa. E determinaremos o grau de confiança para cada regra criada.

O nível de confiança da regra demonstra a probabilidade com que uma consequência aparece quando a premissa é formada. Não precisamos passar por todo o banco de dados novamente para identificá-lo. Basta dividir o suporte do padrão completo pelo suporte da premissa, que já contamos na etapa de seleção de padrões frequentes.

Patrão	Premissa	Suporte	Regra
BC (0.5)	C (0.7)	0.71	C -> B
BD (0.4)	D (0.8)	0.50	D -> B
BE (0.3)	E (0.4)	0.75	E -> B
BCD (0.4)	CD (0.6)	0.67	CD -> B
BCE (0.3)	CE (0.4)	0.75	CE -> B

As regras D -> B e CD -> B não atendem ao requisito mínimo de suporte de 0,7 e as excluímos.

Definimos outras regras de maneira semelhante.

Patrão	Premissa	Suporte	Regra
BC (0.5)	B (0.6)	0.83	B -> C
CD (0.6)	D (0.8)	0.75	D -> C
CE (0.4)	E (0.4)	1.00	E -> C
BCD (0.4)	BD (0.4)	1.00	BD -> C
BCE (0.3)	BE (0.3)	1.00	BE -> C
CDE (0,3)	DE (0.3)	1.00	DE -> C
CD (0.6)	C (0.7)	0.86	C -> D
DE (0.3)	E (0.4)	0.75	E -> D
BCD (0.4)	BC (0.5)	0.80	BC -> D
CDE (0,3)	CE (0.4)	0.75	CE -> D

Revisamos um dos algoritmos mais conhecidos para buscar regras de associação - o Apriori. Mas devo dizer que, apesar de sua simplicidade e popularidade, agora poucas pessoas o usam na prática. A questão é que, como pode ser visto, o gargalo do método considerado são as múltiplas passagens pelo banco de dados para avaliar os suportes de candidatos a padrões frequentes. À medida que o volume de bancos de dados analisados cresce, isso se torna cada vez mais um problema. É praticamente resolvido no algoritmo a seguir. O que requer apenas 2 passagens pelo banco de dados, independente de seu tamanho e do número de caraterísticas analisadas.

3. Algoritmo FP-Grows

Proponho considerar uma solução para os problemas acima usando o exemplo de um dos algoritmos mais rápidos para busca de regras de associação, o FP-Grows (Frequent Pattern - Grows). Devido às peculiaridades da construção do algoritmo, no seu processo de execução, todos os elementos da amostra de treinamento são percorridos apenas 2 vezes. O algoritmo não contempla outras chamadas da amostra de treinamento.

Como o algoritmo acima para procurar regras de associação, o algoritmo FP-Grows pode ser dividido condicionalmente em 2 subtarefas:

1. Encontrar padrões que ocorrem com frequência. No algoritmo em consideração, chama-se construir uma árvore FP.
2. Definir regras.

O algoritmo começa filtrando características aleatórias. Para fazer isso, de forma semelhante ao algoritmo anterior, realizamos a primeira passagem por todo o conjunto de treinamento e calculamos o suporte para cada caraterística. Depois disso, removemos todos as caraterísticas, cuja frequência é menor que o suporte mínimo.

As demais caraterísticas estão disposta em ordem decrescente de seus suportes. Para o exemplo acima, obtemos uma série:

D (0.8) -> C (0.7) -> B (0.6) -> E(0.4) 

Em seguida, é realizada a construção (crescimento) da árvore FP. Para fazer isso, realizamos a segunda passagem pela amostra de treinamento. Ao mesmo tempo, em cada transação, pegamos apenas as características que ocorrem com frequência organizadas em ordem decrescente de suportes e construímos um caminho em nossa árvore. Assim, o nó com suporte máximo estará na raiz da árvore e o nó com suporte mínimo será sua folha. Ao mesmo tempo, criamos um contador para cada nó. E, na primeira iteração, atribuímos o valor 1 ao contador (ou 1/N, onde N é o tamanho da amostra de treinamento).

Em seguida, pegamos a próxima transação do banco de dados. Da mesma forma, construímos um caminho para ela. E vamos adicioná-la à nossa árvore. Para fazer isso, a partir da raiz da árvore, verificamos o caminho com ramificações já existentes. Na parte de repetir o caminho da raiz, simplesmente aumentamos o contador de nós existentes. Para a nova peça, criamos uma ramificação.

O ciclo de iterações é repetido até completar todo o conjunto de treinamento. Para o exemplo acima, obteremos a seguinte árvore FP.

Devo dizer que, com um alto grau de probabilidade, podem ser encontrados caminhos que diferem da própria raiz. E eles podem ser dois:

• construção de bosque,
• criação de um determinado nó raiz que une toda a amostra.

É bastante óbvio que no início do processo de crescimento da árvore FP, novos nós serão criados na maior parte do tempo. Mas à medida que progredimos na amostra de treinamento, chegaremos a aumentar os contadores dos nós existentes sem criar novas ramificações. O destaque desse algoritmo é que, no processo de construção de uma árvore, podemos compactar a amostra de treinamento em tamanhos que podemos operar facilmente na RAM do computador sem acessar o banco de dados.

O trabalho adicional para a definição de regras é feito com a árvore FP, sem referência ao banco de dados inicial.

As regras são construídas para todas as características em ordem crescente de suporte.

Deixe-me lembrá-lo de que, no primeiro estágio, removemos todos as características com frequência menor que a especificada, e agora nossa árvore contém apenas caraterísticas que ocorrem com frequência. Além disso, ao construir a árvore, classificamos as características em ordem decrescente. Isso significa que as caraterísticas com suporte mínimo são folhas.

Assim que definirmos as regras com as caraterísticas que tenham o menor suporte, passaremos das folhas para a raiz da árvore. Também aqui é observado um nexo causal que ainda não está explicitamente estabelecido. O algoritmo assume que características com menos suporte aparecem como resultado de uma combinação de características com mais suporte.

Mas voltando ao nosso algoritmo de definição de regras. Pegamos a caraterística com menos suporte e encontramos todos os caminhos na árvore FP que levam a essa caraterística. A primeira coisa a que prestamos atenção ao selecionar caminhos é a frequência de ocorrência da caraterística desejada ao formar um padrão a partir das características do caminho. O critério para a seleção do caminho é a relação entre o suporte da característica no caminho e o suporte do nó anterior. Essa relação deve ser pelo menos o nível mínimo de confiança da regra.

No exemplo acima, a caraterística E tem menos suporte. Existem 3 caminhos que levam a ela em nossas árvores FP: DCBE (0.2), DCE (0.1), CBE(0.1). Nenhum desses caminhos atende ao requisito mínimo de suporte. E 2 deles não atendem ao requisito mínimo de confiança. Portanto, não podemos criar uma única regra para a característica E. Devo dizer que isso é confirmado pelos resultados obtidos como resultado do trabalho do algoritmo Apriori. 

Removemos as folhas E de nossa árvore e obtemos o seguinte visual de nossa árvore FP abaixo.

O próximo elemento analisado será a característica B. Ela tem o menor suporte dos demais. Existem 3 maneiras para ela: DCB (0.4), B (0.1), CB (0.1).

Nos caminhos de suporte selecionados, a cada característica que precede a analisada é atribuído o suporte da característica analisada no caminho correspondente.

A partir dos caminhos selecionados, uma lista de características participantes é formada e o suporte para cada um deles é determinado. Observe que o suporte é definido como a razão entre o número de ocorrências de um característica nos caminhos selecionados e o número total de registros na amostra de treinamento original. Assim, o novo suporte de cada característica não pode exceder o suporte inicial da característica ou o suporte da característica em análise (para o qual as regras são definidas).

Aqui também removemos as características com suporte inferior ao mínimo. E construímos as caraterísticas restantes em ordem decrescente de suporte.

Em nosso exemplo, obtemos С (0.5), D (0.4).

Observe que, como calculamos o suporte para características com base apenas nos caminhos selecionados, os valores resultantes podem diferir muito dos iniciais. Como resultado desse fator, alguns características podem ser eliminadas e sua ordem na nova hierarquia será alterada.

Além disso, de acordo com a nova hierarquia, construímos uma nova árvore privada a partir dos caminhos selecionados. O algoritmo para construir uma árvore não difere do algoritmo para construir uma árvore FP descrito acima.

Os galhos da árvore privada construída serão as premissas da regra, cuja consequência será nossa caraterística analisada.

Após construir a árvore privada, removemos os nós da caraterística analisada da árvore FP inicial. O truque é que analisamos a característica com suporte mínimo. Isso significa que todos os nós que contêm esse característica são folhas da árvore FP. Consequentemente, sua remoção não terá efeito sobre os caminhos das outras características (logo acima falamos de nexo de causalidade).

Além disso, ao remover gradativamente as características analisadas, reduzimos gradativamente nossa árvore FP. Reduzindo assim o volume para a posterior busca de caminhos na análise das seguintes características. E isso afeta o desempenho geral do algoritmo.

Da mesma forma, criamos regras para cada característica na hierarquia da árvore FP original.

Observe que só podemos criar regras para características que na árvore FP é precedida por pelo menos uma característica raiz. Para características raiz, não podemos criar regras, pois não temos nada para atribuir à premissa. Claro, exceto pela visita de um potencial comprador à loja. Se ele veio à loja, então ele vai comprar alguma coisa. E provavelmente será um dos itens mais vendidos da loja. Mas isso já está além do escopo do algoritmo visto hoje.

Considerações finais

Neste artigo, conhecemos outro tipo de tarefas resolvidas por métodos de aprendizado não supervisionado, em particular a busca por regras de associação. Vimos 2 algoritmos para procurar regras de associação: Apriori e FP-Grows. Mas há muitos mais. Infelizmente, não consigo encaixar todo o tópico em um artigo, apenas aspectos teóricos. No próximo artigo, consideraremos a construção prática de um algoritmo para busca de regras de associação usando MQL5. E vamos avaliar seu desempenho ao resolver um problema de negociação prático.

Referências

1. Redes neurais de maneira fácil (Parte 14): agrupamento de dados
2. Redes neurais de maneira fácil (Parte 15): agrupamento de dados via MQL5
3. Redes neurais de maneira fácil (Parte 16): uso prático do agrupamento
4. Redes neurais de maneira fácil (Parte 17): redução de dimensionalidade
5. Fast Algorithms for Mining Association Rules
6. Mining Frequent Patterns without Candidate Generation