Análise Combinatória
Formando a base para o estudo da Probabilidade
A análise combinatória é um ramo da matemática que estuda técnicas que nos ajudam a resolver problemas relacionados com contagem e organização. Na probabilidade, ela irá contribuir no processo de redução da incerteza sobre a ocorrência de certos eventos de interesse.
Por que isso é importante para mim?
O processo de análise combinatória pode nos ajudar a obter o espaço amostral de um evento aleatório. Tal conceito se refere ao total de possibilidades dado um número de n de elementos, possibilidades essas que são essenciais para o cálculo da probabilidade. Além disso, a probabilidade de um evento acontecer pode impactar diretamente em decisões que você ou o negócio tomam.
Você também pode utilizar a análise combinatória em problemas do dia a dia. Imagine que você deseja combinar features entre si para gerar novas visando alimentar um modelo de Machine Learning. Você possui 30 features numéricas e deseja multiplicar grupos de 3 features para tentar capturar um novo padrão nos dados. Você estima que uma quantidade maior que 820 novas features poderia travar a sua máquina. Quantas colunas diferentes você poderia usar para gerar as combinações sem que a sua máquina trave?
Pare um pouco e pense na resolução. Irei disponibilizar a resposta ao final do artigo.
Princípio básico da contagem
O princípio básico da contagem nos diz que um experimento pode gerar m resultados diferentes. Considerando que um segundo experimento também ocorra, gerando n resultados possíveis, o número de resultados possíveis entre m e n é mn.
Além disso, o princípio básico pode ser demonstrado enumerando os resultados possíveis de cada elemento m.
Imagine que cada sênior da área de dados da sua empresa possui juniores sob sua orientação. Durante a confraternização no final do ano, a empresa decidiu que sortearia uma dupla para levar um prêmio para casa. Levando em consideração que existem 4 seniores na empresa e cada um orienta 2 juniores diferentes, quantas escolhas possíveis para os vencedores podem feitas?
Pelo que foi apresentado, temos 4 resultados possíveis para o sênior e 2 resultados possíveis para o júnior. Logo, teríamos 8 duplas diferentes possíveis para serem sorteadas.
Vamos um pouco além. Agora imagine que você está no grupo do sênior 1. Qual seria a probabilidade da sua dupla ser sorteada na cerimônia?
Para responder, vamos enumerar cada combinação sênior-júnior possível e visualizar o espaço amostral para entender melhor a probabilidade do evento de interesse acontecer.
Sabendo que o número total de possibilidades é de 8, e que dentre essas possibilidades, em apenas 1 você vence, logo:
A probabilidade da sua dupla ser sorteada é de 12.5%.
Generalizando o princípio básico da contagem
Ao generalizarmos, o princípio básico da contagem diz que o número total de possibilidades entre m elementos se dá pela multiplicação das possibilidades de cada elemento no conjunto m.
Vejamos um exemplo. Uma consultoria recebeu um grande investimento e com isso decidiu criar uma área de dados para apoiar o negócio. Após uma rodada de contratações, 6 Engenheiros de Dados, 4 Cientistas de Dados, 3 Analistas de Dados e 1 Engenheiro de Machine Learning foram contratados. Quantas equipes diferentes podem ser formadas dado que se deve ter apenas 1 profissional de cada carreira na equipe?
Percebam que nós temos 4 elementos: Engenheiros de Dados, Cientistas de Dados, Analistas de Dados e Engenheiros de Machine Learning. Destes, o número de engenheiros possíveis que podem assumir uma vaga no time é de 6, o de cientistas 4, o de analistas 3 e o de engenheiro de machine learning 1. Multiplicando as possibilidades de cada elemento do conjunto, teríamos 72 times possíveis.
Permutações
Permutações nos ajudam a encontrar a quantidade total de maneiras de ordenar um número n de elementos. É possível calcular a quantidade de permutações possíveis de um elemento por meio de n! (n fatorial).
Imagine que você é o líder do time de dados na sua empresa. O seu superior te passou 6 projetos importantes para que fossem desenvolvidos pelo seu time. Depois de uma reunião com o time, vocês não chegaram a um consenso sobre quais projetos priorizar. Após isso, você decidiu levar o problema para que o seu superior pudesse te ajudar. Em reunião com o mesmo, você explicou que existiam n maneiras diferentes de ordenar os projetos em uma fila de prioridade. Qual o número n de ordenações que você citou para o seu superior?
Dado que temos 6 elementos diferentes, teríamos 720 maneiras diferentes de ordenar os projetos.
A situação acima nos atende perfeitamente quando temos elementos diferentes. Quando temos a repetição de alguns elementos, a abordagem muda um pouco. Vamos para uma demonstração com a palavra MIM.
Caso fosse feito como no exemplo anterior, usando o número de elementos para n!, teríamos 6 (3 fatorial) formas de ordenar as letras da palavra MIM. E sim, conforme a figura acima, temos 6 formas diferentes de ordenar as letras, mas só é possível diferenciar três delas, pois a letra M, que se repete duas vezes, acaba contribuindo para a formação de elementos iguais.
Para contornar esse problema e obter apenas a quantidade de ordenações diferentes, devemos dividir o fatorial da quantidade total de elementos pelo produto dos fatoriais da quantidade de vezes que cada elemento repetido aparece.
Vamos voltar ao exemplo anterior e buscar o número de combinações diferentes possíveis. Sabemos que o número total de combinações pode ser obtido através do fatorial do número total de elementos (n!). Além disso, sabemos que temos 1 elemento (a letra M) que se repete duas vezes. Logo, temos apenas 3 combinações diferentes.
Vamos a um exemplo mais complexo. Quantas ordenações possíveis eu poderia obter da palavra PARALELEPIPEDO (ignore o acento na letra i)?
A primeira vista, temos 14 elementos que formam a palavra, onde quatro letras se repetem, 3 letras p, 2 letras a, 2 letras l e 3 letras e. Logo, teríamos 605,404,800 maneiras diferentes de ordenar as letras sem que hajam repetições.
Combinação
Usamos combinações quanto estamos interessados em descobrir a quantidade de diferentes grupos com um número preestabelecido de r elementos que um número total de n elementos conseguem formar. Com isso, temos que a quantidade total de n grupos que é possível formar com r elementos é igual ao fatorial da quantidade total de elementos n (n!) dividido pelo produto entre o fatorial da diferença entre n e r e o fatorial da quantidade r de elementos do grupo.
Vejamos um exemplo. O time de dados da sua empresa, liderado por você, recebeu uma solicitação urgente da área de Marketing pedindo para que uma base de clientes fosse segmentada para uma futura campanha. Entretanto, o seu time, composto por 6 pessoas, já estava trabalhando em outro projeto. Para realizar todas as entregas, você decide alocar 2 pessoas do time para segmentar as bases para o Marketing e o restante permaneceria no projeto atual. Quantas duplas possíveis para lidar com o projeto de segmentação você consegue formar com os integrantes do seu time?
Analisando a questão, vemos que temos 6 elementos e com eles devemos verificar quantos grupos de 2 pessoas são possíveis formar. Logo, substituindo as variáveis na fórmula, teríamos 15 grupos diferentes de duas pessoas que seriam possíveis formar com as 6 pessoas do time.
Voltando ao desafio
Antes de resolvermos, recomendo que você volte ao início e tente responder com base nas sessões anteriores. Caso queira apenas a solução, vamos lá.
O método de resolução é fácil de se identificar: combinação. Entretanto, não basta apenas aplicar a fórmula com os valores mostrados na pergunta. Para a solução, é necessário realizar um processo iterativo, usando um número total de elementos que varia entre 3 e 30. Vejamos quantas combinações de 3 elementos seriam possíveis usando os 30 totais.
4060 combinações ultrapassam com folga o limite estabelecido de 820 novas features, ou seja, usar as 30 features está fora de questão. Após iterar um pouco mais sobre o valor total de elementos, vamos chegar ao número ideal de 18 features, que podem gerar 816 combinações diferentes.
Conclusão
Construir uma base sólida é importante quando falamos de probabilidade e estatística, pois isso irá permitir que o aluno compreenda tópicos mais avançados com uma maior facilidade. A análise combinatória faz parte dessa base, tornando-se uma ferramenta importante para o entendimento da probabilidade. Convido você a ir mais a fundo, pois o exposto aqui foi apenas a base.
Para mais conteúdos como esse, me siga aqui ou se conecte comigo através do LinkedIn.
