Observatório de dados/Partições

Partições agrupamentos sistemáticos e classificações Partição de A em A₁, ... , A₆
Validade	Neste curso e alguns textos
Contexto:	classif. estatística

Denominamos agrupamento sistemático dos elementos de um conjunto $C$ , ou partição de $C$ em k partes, ao processo de definir dois ou mais subconjuntos $C_{i}$ tais que esses subconjuntos formem um "mosaico" de k células ( $C_{1},C_{2},...,C_{i},...,C_{k}$ ). Um mosaico, como nas ilustrações desta página, pode ser caracterizado por suas propriedades, e estas propriedades descritas em linguagem de conjuntos:

nenhuma "célula" $C_{i}$ está vazia.
A união das células $C_{i}$ reproduz o todo $C$ .
As células $C_{i}$ não se sobrepõe, são disjuntas entre si.

Exemplo. Um conjunto de letras A={a,b,c,d,f} pode ser subdividido em $A_{1}=\{a,b\}$ e $A_{2}=\{c,d,f\}$ . Os subconjuntos $A_{i}$ possuem todas as características de um mosaico:

$A_{1}\neq \emptyset$ , $A_{2}\neq \emptyset$ . Nenhuma "célula" está vazia.
$A=A_{1}\cup A_{2}$ . A união das células reproduz o todo.
$A_{1}\cap A_{2}=\emptyset$ . As células não se sobrepõe, são disjuntas entre si.

Uma definição mais genérica é oferecida abaixo, assim como uma definição análoga para multiconjuntos. Os exemplos em seguida também ajudam a compreender melhor a definição.

Definição para conjuntos

A partição de $C$ em k partes é formada por subconjuntos $C_{i}\subset C$ , com $i\in \{0,1,\dots k\}$ , tais que:

$C_{i}\neq \emptyset$ .
$C=C_{0}\cup C_{1}\cup C_{2}\cup \dots C_{k}$
$C_{0}\cap C_{1}=\emptyset$ ; $C_{0}\cap C_{2}=\emptyset$ ; $\dots$ ; $C_{k-1}\cap C_{k}=\emptyset$ .

Resumidamente, os subconjuntos $C_{i}$ formam uma partição de C quando: são disjuntos entre si; a sua união reproduz C; e cada subconjunto tem pelo menos um elemento. Os exemplos abaixo ajudam a compreender melhor a definição.

Intuição e visualização

Visualmente, se imaginarmos elementos como pontos no plano, os agrupamentos $C_{i}$ formam um mosaico, cobrindo completamente a superfície original, sem buracos nem interseções.

Na ilustração a superfície original, que faz papel do conjunto $C$ da definição, é um retângulo, e cada célula colorida do mosaico faz papel de classe $C_{i}$ .

Podemos imaginar que cada polígono do mosaico possa ser novamente particionado em células menores, formando sub-mosaicos, ou seja, subclasses. A relação classe-subclasse forma uma hierarquia, como no mapa do Brasil (ilustrado mais abaixo) onde podemos ter primeiro uma divisão do território nacional em regiões, depois a subdivisão dessas regiões em estados.

Motivação

... Vimos nas atividades ... e ... que os elementos de um conjunto podem ser bastante distintos, o que nos leva a dividir os mesmos em "tipos" agrupados por semelhança ... Por exemplo ao medir folhas vimos que não faz sentido usar o mesmo critério de medida para todas, nem comparar folhas com medidas obtidas de critérios diferentes...

... É bastante comum, nas mais diversas áreas da Ciência e Tecnologia, o problema de se reduzir a diversidade de tipos de elementos em um conjunto, resolvendo esse problema com o estabelecimento de regras de classificação...

... pelas aplicações e motivações entendemos melhor o porque da definição ... Não faz sentido por exemplo definir uma classificação com menos de duas classes... Não faz sentido ter mais classes do que elementos ... etc.

Características da classificação

... outras características de uma classificação podem ser demandas ... definindo elas mais formalmente...

Domínio de uma classe

... uma classificação $K_{i}$ tem domínios $D_{i}$ quando podemos dizer que $K_{i}=\{x\in D_{i}\}$ ... Necessariamente $D_{i}\subset D$ , onde D é o domínio de C. No caso de multiconjuntos ...

Classificação de sequências e multiconjuntos

Quando se tratando de multiconjunto, deve-se tomar certo cuidado ao estabelecer domínios, e então acrescentar uma quarta propriedade, de que os domínios das classes-multiconjunto também são distintos. ... similarmente numa sequência ...

Uniformidade das classes

Conforme o tipo de elemento do conjunto $C$ pode-se exigir mais uma importante propriedade das classes $K_{i}$ , que é a uniformidade entre elas. O critério de uniformidade pode ser imposto aos elementos do domínio, ou diretamente aos elementos da classe:

classes uniformes: uma classificação $K_{i}$ será dita "uniforme" quando todas elas satisfazem a propriedade de uniformização, $\forall K_{i}PropriedadeX(K_{i})=True$ . Exemplo: obrigar que todas as classes tenham mesmo número de elementos, $\forall K_{i},n(K_{i})=q$ .

classes com domínio uniforme: uma classificação $K_{i}$ com domínios $D_{i}$ , com todos os domínios satisfazendo uma mesma propriedade $\forall D_{i}PropriedadeX(D_{i})=True$ . Exemplo: obrigar que todas os domínios das classes tenham mesmo número de elementos, $\forall D_{i},n(D_{i})=q$ .

classes uniformes com domínios uniformes: duas propriedades, uma para uniformização do domínio e outra para uniformização dos elementos. $K_{i}=\{x\in D_{i}|PropriedadeX(K_{i})\land PropriedadeY(D_{i})\}$

Hieraraquia entre classes

....

Classificação binária e múltipla

... quando existem apenas duas classes K1 e K2, dizemos que a classificação é binária... Quando são mais, é múltipla (multiclasse)... Os mecanismos de classificação múltipla sempre podem ser definidos a partir da binária.

Ocupação das partições: princíṕiop do pombal

A inspiração para o nome do princípio: pombos em suas caixas. Aqui n = 10 e k = 9. Como $\lceil 10/9\rceil =\lceil 1,11\rceil =2$ , temos pelo menos uma caixa com 2 ou mais pombos.

Fazemos uso do princípio do pombal quando desejamos contabilizar o número máximo de elementos das partições, quando tentamos distribuir elementos de forma "o mais uniforme possível" entre elas.

Seja "n" o número de objetos distintos a serem guardados em "k" recipientes.
Pode-se afirmar com certeza que pelo menos um recipiente conterá

\lceil n/k\rceil

ou mais objetos,
onde

\lceil x\rceil

denota o menor inteiro igual ou superior a x (função teto).

Na notação utilizada para os agrupamentos podemos dizer que, havendo $n$ amostras agrupadas em partições $C_{k}$ de um conjunto C (com i=1..k), deve haver não menos que $\lceil n/k\rceil$ amostras em pelo menos uma dessas partições $C_{k}$ .

Uma das consequências é que devemos reduzir o valor de k (consequentemente aumentando $n(C_{k})$ em média) até que seja satisfatória a aproximação $\lceil n/k\rceil \sim \lfloor n/k\rfloor$ .
Por exemplo $100\sim 101$ é satisfatória, já os valores 4 e 5 não podem ser tão bem aproximados.

Nota: o termo "aproximação satisfatória" pode ser quantificado, ainda que de maneira arbitrária. Podemos supor que "10% ou menos de diferença" é satisfatório. 100 e 101 diferem em apenas 1%; 4 e 5 diferem em mais de 20%,

{\frac {2\times (101-100)}{101+100}}={\frac {2}{201}}\approx 1\%

.

{\frac {2\times (5-4)}{5+4}}={\frac {2}{9}}\approx 22\%

.

Em partições realizadas para fins de classificação uniforme, tipicamente em dados estatísticos, quando k é alto (muitos grupos) criam-se falsos valores modais: a estatística requer agrupamentos sem "efeito pombal" na sua moda.

Exemplos

Exemplo 1 – Números e naipes

Seja S = {1, ♠, 2, ♥, 3, ♦, ♣} um conjunto de símbolos. São nítidos em S dois subjuntos de elementos com bastante afinidade,
os dígitos, D={1,2,3}, e os naipes, N={♠, ♥, ♦, ♣}. Juntos D e N formam uma partição em S pois:

os subconjuntos D e N não são vazios. $D\neq \emptyset$ e $N\neq \emptyset$
a união de D com N forma S. $S=D\cup N$
a interseção de D com N é vazia. $D\cap N=\emptyset$

População de uma escola

Os exemplos a seguir são relativos à abstração de uma escola como sendo um conjunto de pessoas.

Exemplo 2.1 – Escola como conjunto de pessoas organizadas por função

Suponhamos uma escola com seus alunos, professores e funcionários: a escola é um conjunto $E$ de pessoas, com subconjuntos $K_{P}$ dos professores, $K_{A}$ dos alunos, e $K_{O}$ dos outros funcionários (que não são professores). Os subconjuntos são classes $K_{i}$ com i={"P", "A", "O"}, pois satisfazem as propriedades:

$K_{i}\neq \emptyset$
$E=K_{P}\cup K_{A}\cup K_{O}$
$K_{P}\cap K_{A}\cap K_{O}=\emptyset$

Exemplo 2.2 – Escola como conjunto de pessoas organizadas por gênero

A escola pode ser vista apenas como conjunto de pessoas do sexo masculino ou feminino. A escola é um conjunto $E$ de pessoas, com subconjuntos $K_{M}$ pessoas do sexo masculino, e $K_{F}$ de pessoas do sexo feminino. Os subconjuntos são classes $K_{i}$ com i={"M", "F"}, pois satisfazem as propriedades:

$K_{i}\neq \emptyset$
$E=K_{M}\cup K_{F}$
$K_{M}\cap K_{F}=\emptyset$

Exemplo 2.3 – Escola como conjunto de pessoas organizadas por gênero e função

A escola pode ser vista com mais detalhe com um particionamento de ambos, gênero e função. Os subconjuntos
são classes $K_{i}$ com i={"PM", "PF", "AM", "AF", "OM", "OF"}, pois satisfazem as propriedades:

$K_{i}\neq \emptyset$
$E=K_{PM}\cup K_{PF}\cup K_{AM}\cup K_{AF}\cup K_{OM}\cup K_{OF}$
$K_{PM}\cap K_{PF}\cap K_{AM}\cap K_{AF}\cap K_{OM}\cap K_{OF}=\emptyset$

População do Brasil

Os exemplos a seguir são relativos à abstração do Brasil como sendo um conjunto de moradores, ou seja, usando o critério do Censo do IBGE, que estabelece as pessoas como "domiciliados". O IBGE também estabelece critérios para garantir que, mesmo em casos ambíguos, a mesma pessoa não seja contada duas vezes em cidades diferentes (ex. numa tem família e na outra tem trabalho certas épocas do ano).

Exemplo 3 – Estados do Brasil

Todo país tem sua representação no mapa como um polígono, as linhas de fronteira do país. Dentro destas linhas são traçadas as subdivisões, que no Brasil convencionamos como estados (AM, AP, ... DF, MG, RJ, SP, RS, etc. ). Os subconjuntos são classes $K_{i}$ com $i\in \{AM,AP,\dots \}$ , pois satisfazem as propriedades:

$K_{i}\neq \emptyset$
$BR=K_{AM}\cup K_{AP}\cup K_{DF}\cup \dots$
$K_{AM}\cap K_{AM}=\emptyset$ ; $K_{AM}\cap K_{DF}=\emptyset$ ; ...; $K_{SP}\cap K_{TO}=\emptyset$ .

Exemplo 4 – Macro-regiões do Brasil

No Brasil foi também convencionado que o território nacional pode ser subdividido em macro-regiões, e elas foram um mosaico no mapa da nação. As regiões Norte, Nordeste, Sudeste, Centroeste e Sul foram destacadas por diferentes cores na ilustração ao lado, e notamos que de fato formam uma classificação $K_{i}$ com $i\in \{Norte,Nordeste,\dots \}$

$K_{i}\neq \emptyset$
$BR=K_{Norte}\cup K_{Nordeste}\cup K_{Centroeste}\cup K_{Sudeste}\cup K_{Sul}$
$K_{Norte}\cap K_{Nordeste}=\emptyset$ ; $K_{Norte}\cap K_{Centroeste}=\emptyset$ ; ...; $K_{Sudeste}\cap K_{Sul}=\emptyset$ .

Além disso os cada região é composta por um conjunto de estados, de modo que existe uma hierarquia de classes entre as macro-regiões e os estados.

Exemplo 5 – Hierarquia entre Macro-regiões e estados do Brasil

Cada macro-região brasileira é composta por um conjunto de estados,

$K_{Norte}=K_{AM}\cup K_{AC}\cup \dots$
$K_{Sudeste}=K_{SP}\cup K_{MG}\cup K_{RJ}\cup \dots$
...

de modo que existe uma hierarquia de classes entre as macro-regiões e os estados.

NOTA: sempre que existe uma hierarquia, podemos adotar uma definição alternativa para a classe-mãe, transformando ela num conjunto de conjuntos, ao invés de tomar diretamente a população como elemento. Exemplo: $K_{Norte}=\{K_{AM},K_{AC},\dots \}$ ... Essa opção por vezes causa confusão, de modo que é importante estabelecer o referencial de elemento de uma hierarquia.

Análise combinatória

Para avaliar ou quantificar todas as possíveis maneiras de se particionar um conjunto, é preciso recorrer à Análise Combinatória e métodos mais sofisticados de descrição das "famílias de partições".

Exemplo 6 – Partições em um conjunto com 5 elementos

A ilustração ao lado mostra as 52 maneiras possíveis de se realizar partições sobre um conjunto X de 5 elementos. Uma região colorida indica um subconjunto de X, formando um membro da partição envolvente. Os pontos não coloridos indicam subconjuntos de um elemento. A primeira partição mostrada contém cinco subconjuntos de um elemento; a última partição contém um subconjunto com cinco elementos.

Supondo o caso de X={1,2,3,4,5} teremos então, pela ilustração:

na primeira linha a partição é formada pelos subconjuntos {1}, {2}, {3}, {4} e {5};
na segunda linha, o primeiro caso por {1,2}, {3}, {4} e {5};
na quarta linha, o primeiro caso por {1,2,4}, {3} e {5};
na última linha pelo próprio X, uma partição composta de uma só parte: inválida nas aplicações usuais (ver definição), mas ainda válida em análise combinatória, para garantir a consistência e simplicidade dos cálculos.

O número de maneiras possíveis de se realizar partições distintas sobre o um conjunto pode ser obtido por contagem, mas, como verenos é mais prático usar uma função pronta para isso. Vejamos os casos mais simples:

n(C) #Partições Explicação

0 1 o conjunto vazio, por consistência, tem a partição {}, contendo o elemento vazio.

1 1 um conjunto contendo um só elemento, tem uma só partição, que é ele mesmo.

2 2 seja C={1,2}, as partições possíveis são {1}, {2} e {1,2}.

4 15 seja C={1,2,3,4}, as partições possíveis são {1},{2},{3},{4}, {1,2},{3},{4}, ... e {1,2,3,4}

5 52 ilustrado acima.

... ... ...

Essa sequência cresce rapidamente, e é conhecida como número de Bell, e bem documentada como sequência inteira OEIS:A000110. A função geradora dessa sequência é duplamente exponencial, tendo como parâmetro n(C),

B(n)=e^{e^{n}-1}.

Definição para multiconjuntos

Em um multiconjunto M, por analogia à partição de conjuntos, define-se que seus sub-multiconjuntos $M_{i}\subset M$ .
Eles formam partição de M em k partes se, para $i\in \{0,1,\dots k\}$ tivermos

1.

M_{i}\neq \emptyset

2.

M=\biguplus _{i\in I}M_{i}

3.

M_{i}\cap M_{j}=\emptyset ~~~~~\forall j\neq i

.

Só difere da partição de conjuntos, ligeiramente, na segunda propriedade, pois num contexto de dados, onde se visa a preservação da informação, é requerida a soma das multiplicidades.
Nota: em estatística os agrupamentos $M_{i}$ são denominados classes e é requerido que sejam representativos de intervalos uniformes.

Exemplos de partições de multiconjuntos

Sacola de palavras

... ver w:en:Bag-of-words_model ... Modela-se um documento textual qualquer como multiconjunto de suas palavras. Neste caso o documento é um mosaico e cada célula tem um só elemento, a palavra...

Ver também

Teoria dos Conjuntos (agrupamentos sistemáticos)
Exercicios, parte 1
Partição de multiconjuntos