Observatório de dados/Partições

Partições agrupamentos sistemáticos e classificações Partição de A em A1, ... , A6
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:

1. nenhuma "célula" $C_{i}$ está vazia.
2. A união das células $C_{i}$ reproduz o todo $C$.
3. 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:

1. $A_{1}\neq \emptyset$,   $A_{2}\neq \emptyset$.     Nenhuma "célula" está vazia.
2. $A=A_{1}\cup A_{2}$.     A união das células reproduz o todo.
3. $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:

1. $C_{i}\neq \emptyset$.
2. $C=C_{0}\cup C_{1}\cup C_{2}\cup \dots C_{k}$
3. $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.

Partição vista como mosaico.

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

População de uma escola

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

População do Brasil

O território brasileiro é subdividido em regiões que são subdivididas em estados. Ver dataset completo.

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).

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".

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