Particionamento de dados

O particionamento de dados (ou clustering de dados em inglês) é um método de análise de dados . Visa dividir um conjunto de dados em diferentes “pacotes” homogêneos, no sentido de que os dados de cada subconjunto compartilham características comuns, que na maioria das vezes correspondem a critérios de proximidade ( similaridade de computador ) que definimos. Pela introdução de medidas e classes de distância entre objetos.

Para obter um bom particionamento, é necessário ao mesmo tempo:

minimizar a inércia intraclasse para clusters ( Cluster English) o mais homogêneo possível;
maximizar a inércia entre classes para obter subconjuntos bem diferenciados.

Vocabulário

A comunidade científica francófona usa diferentes termos para designar esta técnica.
A palavra inglesa clustering é comumente usada. Também falamos frequentemente sobre métodos de agrupamento . Freqüentemente, é feita uma distinção entre métodos "hierárquicos" e "particionados" .

Agrupamento não supervisionado

“ Unsupervised clustering ”, também chamado de classificação não supervisionada, é um processo que reúne dados semelhantes. O facto de não ser supervisionado significa que as técnicas de aprendizagem de máquina permitirão encontrar certas semelhanças para poder classificar os dados de uma forma mais ou menos autónoma.

Este tipo de análise permite ter um perfil dos diferentes grupos. Isso, portanto, torna possível simplificar a análise dos dados, destacando as semelhanças e as diferenças e, assim, reduzindo o número de variáveis nos dados. Essa técnica não é usada apenas no campo da genética, mas também permite, por exemplo, listar potenciais clientes durante uma campanha publicitária.

Agrupamento hierárquico ou de dendrograma

A " hierarquia de agrupamento " é outra técnica de classificação. Desta vez, o parâmetro comparado é decidido com antecedência. Então, uma vez escolhido o parâmetro de comparação, calcula-se a distância euclidiana [9]. Para fazer isso, usamos sua definição dada pela equação (1).

${\ displaystyle \ | ab \ | _ {2} = {\ sqrt {\ sum _ {i} \ left (a_ {i} -b_ {i} \ right) ^ {2}}} \ qquad \ qquad \ qquad (1)}$

Então, é suficiente conectar os indivíduos mais próximos uns dos outros, dois a dois, até que um diagrama em árvore chamado dendrograma seja formado .

Os dendrogramas podem ser lidos da seguinte forma: para saber o nível de proximidade entre 2 indivíduos, você deve olhar para o eixo y; quanto mais a ligação entre dois indivíduos é feita em uma ordenada alta, menos eles serão semelhantes do ponto de vista do parâmetro observado. Além disso, se quisermos conhecer os indivíduos observados, devemos olhar para o eixo x.

Dependendo da taxa de proximidade que desejamos, é possível formar um certo número de grupos.

Mapa de calor

Um mapa de calor é uma representação gráfica de dados estatísticos em uma matriz bidimensional, que usa a técnica de "agrupamento hierárquico" . Os dados são representados em uma escala conectando duas cores, como uma cor fria e uma cor quente, daí o nome mapa de calor ou preto e branco.

A cor da grade representa o valor do parâmetro usado para vincular as amostras. A convenção pode ser adotada de que quanto mais quente a cor (por exemplo, vermelho), maior será a proximidade.

Diferentes métodos de classificação podem ser usados, por exemplo, um agrupamento de acordo com características conhecidas ou uma classificação de acordo com um parâmetro externo.

Em que contexto pode ser útil fazer um mapa de calor?

Esta técnica de relacionar dois conjuntos de dados classificados com uma medida em comum pode ser usada em muitos campos. Por exemplo, durante o laboratório, os dados são medidas de genes, os dois conjuntos são os pacientes e os genes, a ordenação vem dos dendrogramas , e isso permite localizar facilmente, graficamente, categorias de pacientes ligadas a categorias de genes em risco. O mesmo conceito pode ser usado em mapas de calor.

Em geral, pode ser utilizado para qualquer análise descritiva, desde que seja necessário analisar um conjunto de dados muito grande para ser analisado manualmente e que corresponda ao tipo de dados esperado por um mapa de calor. Por exemplo, a técnica poderia ser usada para classificar pontes, , Ou para determinar quais características macroscópicas (mm-μm), associadas a composições de materiais (nm, moléculas), têm as propriedades mais interessantes; e estes são apenas exemplos.

Interesse e aplicações

O particionamento de dados é um método de agrupamento (diferente da classificação supervisionada quando os dados para aprendizagem já estão rotulados) e, portanto, às vezes referido como tal.

Aplicativos: geralmente existem três tipos:

a segmentação de um banco de dados ; ele pode ser usado para discretizar um banco de dados.
A segmentação também pode permitir condensar ou comprimir os dados de uma base de dados espacial (ou seja, reduzir o tamanho dos pacotes de dados a serem processados, no conjunto de dados considerado); por exemplo, em uma imagem aérea ou de satélite, um GIS pode tratar florestas , campos , prados , estradas , pântanos , etc. de maneira diferente. aqui considerados subespaços homogêneos. Um tratamento mais refinado pode então ser aplicado a subconjuntos dessas classes (por exemplo: decídua, conífera, artificial, floresta natural, etc.).
OLAP é um método que facilita a indexação de tais bancos de dados;
a classificação (subgrupos, subpopulações dentro do banco de dados), por exemplo, um banco de dados de cliente para gerenciamento de relacionamento com o cliente ;
a extração de conhecimento , que geralmente é feita sem propósito priori (fator serendipidade , útil para geração de hipóteses ou modelagem preditiva) para trazer conjuntos e subconceitos possivelmente indistinguíveis naturalmente.

Formalização

Para particionar os dados, assume-se que esses dados estão organizados em uma matriz em que cada linha corresponde a um indivíduo (ou observação) e cada coluna corresponde a um preditor (ou variável). Notamos o número de indivíduos e o número de preditores: desta forma, a matriz é de tamanho ${\ textstyle X}$ ${\ textstyle N}$ ${\ textstyle p}$ ${\ textstyle X}$ ${\ textstyle N \ times p}$

X=(x11...xp1⋮⋮x1NÃO...xpNÃO){\ displaystyle X = \ left ({\ begin {array} {ccc} x_ {1} ^ {1} & ... & x_ {p} ^ {1} \\\ vdots && \ vdots \\ x_ {1 } ^ {N} & ... & x_ {p} ^ {N} \\\ end {array}} \ right)} ${\ displaystyle X = \ left ({\ begin {array} {ccc} x_ {1} ^ {1} & ... & x_ {p} ^ {1} \\\ vdots && \ vdots \\ x_ {1 } ^ {N} & ... & x_ {p} ^ {N} \\\ end {array}} \ right)}$

O objetivo de um algoritmo de particionamento é encontrar os "melhores" grupos de indivíduos. Para isso nos damos uma dessemelhança entre os indivíduos e (respectivamente, linha e de ). ${\ textstyle d (x ^ {i}, x ^ {i '})}$ ${\ displaystyle x ^ {i} = (x_ {1} ^ {i}, ..., x_ {p} ^ {i})}$ ${\ displaystyle x ^ {i '} = (x_ {1} ^ {i'}, ..., x_ {p} ^ {i '})}$ $eu$ $eu '$ $X$

Observe o número de grupos que queremos formar. Isso equivale a encontrar uma função de atribuição que minimiza uma função de custo. ${\ displaystyle K \ geqslant 2}$ ${\ displaystyle C: [\! [1, N] \!] \ longrightarrow [\! [1, K] \!]}$

Uma função de custo clássica é a variação dentro do cluster :

C(VS)=∑k=1K∑VS(eu)=k∑VS(eu′)=kd(xeu,xeu′){\ displaystyle W (C) = \ sum _ {k = 1} ^ {K} \ sum _ {C (i) = k} \ sum _ {C (i ') = k} d (x ^ {i} , x ^ {i '})} ${\ displaystyle W (C) = \ sum _ {k = 1} ^ {K} \ sum _ {C (i) = k} \ sum _ {C (i ') = k} d (x ^ {i} , x ^ {i '})}$ Existem outras funções de custo (por exemplo, o índice de Dunn , o índice de Davies-Bouldin ou o índice de Calinski-Harabasz ). Eles podem ser usados para avaliar a qualidade da classificação.

Algoritmos

Existem vários métodos de particionamento de dados, incluindo:

Métodos baseados em centróide , como os algoritmos k- means ou k- meedóide ;
Métodos de agrupamento hierárquico ;
Da expectativa dos algoritmos de maximização (EM) ;
Algoritmos baseados em densidade, como DBSCAN ou OPTICS ;
Métodos conexionistas, como mapas auto-adaptativos .

Esses métodos são implementados em muitos softwares de mineração de dados .

Veja também

Bibliografia

Anil K. Jain, MN Murty, PJ Flynn, " Data Clustering: a Review ", ACM Computing Surveys , vol. 31, n o 3,Setembro de 1999. DOI : 10.1145 / 331499.331504
EM. Chen, J. Han e PS Yu, " Data mining: uma visão geral de uma perspectiva de banco de dados ", IEEE Transactions on Knowledge and Data Engineering , vol. 8, n o 6, p. 866-883 , 1996.
AK Jain, “ Data clustering: 50 years beyond K-means ”, Pattern Recognition Letters , vol. 31, n o 8, p. 651-666 ,junho de 2010.

Notas e referências

Berkhin, 2002.
(em) " Clustering Indexes " em cran.r-project.org ,novembro de 2017(acessado em 8 de junho de 2019 )