Literatura de análise de cluster. Ministério da Educação e Ciência da Federação Russa

Enviar seu bom trabalho na base de conhecimento é simples. Use o formulário abaixo

Estudantes, estudantes de pós-graduação, jovens cientistas que utilizam a base de conhecimento em seus estudos e trabalhos ficarão muito gratos a você.

Introdução

1. História da “análise de cluster”

2. Terminologia

2.1Objeto e recurso

2.2Distância entre objetos (métrica)

2.3 Densidade e localidade dos clusters

2.4 Distância entre clusters

3. Métodos de agrupamento

3.1Características dos métodos aglomerativos hierárquicos

3.2Características dos métodos de agrupamento iterativo

4. Agrupamento de recursos

5. Estabilidade e qualidade do clustering

Bibliografia

INTRODUÇÃO

“Análise de cluster é um conjunto de métodos matemáticos projetados para formar grupos de objetos relativamente “distantes” uns dos outros, “próximos” uns dos outros, com base em informações sobre distâncias ou conexões (medidas de proximidade) entre eles. O significado é semelhante aos termos: classificação automática, taxonomia, reconhecimento de padrões sem professor." Esta definição de análise de cluster é fornecida na última edição do Dicionário Estatístico. Na verdade, “análise de cluster” é um nome generalizado para um conjunto bastante grande de algoritmos usados para criar uma classificação. Diversas publicações também usam sinônimos para análise de cluster, como classificação e particionamento. A análise de cluster é amplamente utilizada na ciência como meio de análise tipológica. Em qualquer atividade científica, a classificação é um dos componentes fundamentais, sem o qual é impossível a construção e teste de hipóteses e teorias científicas. Assim, no meu trabalho, meu principal objetivo é considerar as questões da análise de cluster (os fundamentos da análise de cluster), bem como considerar sua terminologia e dar alguns exemplos de utilização deste método no processamento de dados.

1. HISTÓRIA DA “ANÁLISE DE CLUSTER”

Uma análise de publicações nacionais e estrangeiras mostra que a análise de cluster é utilizada em uma ampla variedade de campos científicos: química, biologia, medicina, arqueologia, história, geografia, economia, filologia, etc. O livro de V. V. Nalimov “Modelo Probabilístico de Linguagem” descreve o uso da análise de cluster no estudo de 70 amostras analíticas. A maior parte da literatura sobre análise de cluster apareceu nas últimas três décadas, embora os primeiros trabalhos que mencionavam métodos de cluster tenham surgido há bastante tempo. O antropólogo polonês K. Czekanovsky apresentou a ideia de “classificação estrutural”, que continha a ideia principal da análise de cluster - a identificação de grupos compactos de objetos.

Em 1925, o hidrobiólogo soviético P.V. Terentyev desenvolveu o chamado “método de correlação de galáxias”, destinado a agrupar características correlacionadas. Este método deu impulso ao desenvolvimento de métodos de agrupamento por meio de gráficos. O termo “análise de cluster” foi proposto pela primeira vez por Trion. A palavra "cluster" é traduzida do inglês como "cacho, pincel, cacho, grupo". Por esse motivo, esse tipo de análise foi inicialmente chamada de “análise de grupo”. No início dos anos 50, surgiram publicações de R. Lewis, E. Fix e J. Hodges sobre algoritmos hierárquicos para análise de cluster. Um impulso notável ao desenvolvimento do trabalho sobre análise de cluster foi dado pelo trabalho de R. Rosenblatt em um dispositivo de reconhecimento (perceptron), que lançou as bases para o desenvolvimento da teoria do “reconhecimento de padrões sem professor”.

O impulso para o desenvolvimento de métodos de agrupamento foi o livro "Princípios de Taxonomia Numérica", publicado em 1963. dois biólogos - Robert Sokal e Peter Sneath. Os autores deste livro partiram do facto de que para criar classificações biológicas eficazes, o procedimento de agrupamento deve garantir a utilização de vários indicadores que caracterizam os organismos em estudo, avaliar o grau de semelhança entre esses organismos e garantir a colocação de organismos semelhantes. no mesmo grupo. Neste caso, os grupos formados devem ser suficientemente “locais”, ou seja, a semelhança dos objetos (organismos) dentro dos grupos deve exceder a semelhança dos grupos entre si. A análise posterior dos grupos identificados, segundo os autores, pode determinar se esses grupos correspondem a espécies biológicas diferentes. Assim, Sokal e Snit assumiram que identificar a estrutura de distribuição dos objetos em grupos ajuda a estabelecer o processo de formação dessas estruturas. E as diferenças e semelhanças entre organismos de diferentes aglomerados (grupos) podem servir de base para a compreensão do processo evolutivo ocorrido e a elucidação de seu mecanismo.

Durante esses mesmos anos, muitos algoritmos foram propostos por autores como J. McKean, G. Ball e D. Hall usando métodos k-means; G. Lance e W. Williams, N. Jardine e outros - usando métodos hierárquicos. Cientistas nacionais também deram uma contribuição significativa para o desenvolvimento de métodos de análise de cluster - E.M. Braverman, A.A. Dorofeyuk, I.B. Muchnik, L.A. Rastrigin, Yu.I. Zhuravlev, I.I. Eliseeva e outros. Em particular, nos anos 60-70. Numerosos algoritmos desenvolvidos pelos matemáticos de Novosibirsk NG Zagoruiko, VN Elkina e GS Lbov eram muito populares. São algoritmos conhecidos como FOREL, BIGFOR, KRAB, NTTP, DRET, TRF, etc. Com base nesses pacotes, foi criado um pacote de software especializado OTEKS. Não menos interessantes produtos de software PPSA e Class-Master foram criados pelos matemáticos de Moscou S.A. Aivazyan, I.S. Enyukov e B.G. Mirkin.

Em vários graus, os métodos de análise de cluster estão disponíveis na maioria dos pacotes estatísticos nacionais e estrangeiros mais conhecidos: SIGAMD, DataScope, STADIA, SOMI, PNP-BIM, SORRA-2, SITO, SAS, SPSS, STATISTICA, BMDP, STATGRAPHICS , GENSTAT, S-PLUS, etc. É claro que, 10 anos após a publicação desta revisão, muita coisa mudou, surgiram novas versões de muitos programas estatísticos e surgiram programas completamente novos, usando novos algoritmos e um poder de computação bastante aumentado. No entanto, a maioria dos pacotes estatísticos utiliza algoritmos propostos e desenvolvidos nos anos 60-70.

Segundo estimativas aproximadas de especialistas, o número de publicações sobre análise de cluster e suas aplicações em diversas áreas do conhecimento dobra a cada três anos. Quais as razões para um interesse tão intenso neste tipo de análise? Objetivamente, existem três razões principais para este fenômeno. Este é o surgimento de uma poderosa tecnologia de computação, sem a qual a análise de cluster de dados reais é praticamente impossível de implementar. A segunda razão é que a ciência moderna depende cada vez mais da classificação nas suas construções. Além disso, este processo aprofunda-se cada vez mais, pois paralelamente a isso ocorre uma crescente especialização do conhecimento, o que é impossível sem uma classificação suficientemente objetiva.

A terceira razão é que o aprofundamento do conhecimento especializado conduz inevitavelmente a um aumento do número de variáveis tidas em conta na análise de determinados objetos e fenómenos. Como resultado, a classificação subjetiva, que anteriormente se baseava num número relativamente pequeno de características tidas em conta, muitas vezes revela-se pouco fiável. E a classificação objetiva, com um conjunto cada vez maior de características de objetos, requer o uso de algoritmos complexos de agrupamento, que só podem ser implementados com base em computadores modernos. Foram estas razões que deram origem ao “boom dos clusters”. No entanto, entre médicos e biólogos, a análise de cluster ainda não se tornou um método de pesquisa bastante popular e difundido.

2 TERMINOLOGIA

2. 1 OBJETO E RECURSO

Vamos primeiro introduzir conceitos como objeto e atributo. Objeto - do latim objectum - sujeito. Em relação à química e à biologia, por objetos entendemos assuntos específicos de pesquisa que são estudados por meio de métodos físicos, químicos e outros. Tais objetos podem ser, por exemplo, amostras, plantas, animais, etc. Um determinado conjunto de objetos à disposição do pesquisador para estudo é denominado amostra ou população amostral. O número de objetos em tal população é geralmente chamado de tamanho da amostra. Normalmente, o tamanho da amostra é indicado pela letra latina "n" ou "N".

Atributo (sinônimos - propriedade, variável, característica; inglês - variável - variável.) - representa uma propriedade específica de um objeto. Essas propriedades podem ser expressas como valores numéricos ou não numéricos. Por exemplo, a pressão arterial (sistólica ou diastólica) é medida em milímetros de mercúrio, o peso em quilogramas, a altura em centímetros, etc. Tais sinais são quantitativos. Em contraste com estas características numéricas contínuas (escalas), diversas características podem ter valores discretos e descontínuos. Por sua vez, tais características discretas são geralmente divididas em dois grupos.

1) O primeiro grupo são as variáveis de classificação, ou como também são chamadas, variáveis ordinais (escalas). Tais características têm a propriedade de ordenar esses significados. Estes incluem os estágios de uma doença específica, faixas etárias, pontuações de conhecimento dos alunos, uma escala de 12 pontos de magnitudes de terremotos de acordo com Richter, etc.

2) O segundo grupo de características discretas não possui tal ordenação e é denominado características nominais (da palavra “nominal” - amostra) ou características de classificação. Um exemplo de tais sinais poderia ser a condição do paciente - “saudável” ou “doente”, o sexo do paciente, o período de observação - “antes do tratamento” e “após o tratamento”, etc. Nestes casos, costuma-se dizer que tais características pertencem à escala de nomenclatura.

Os conceitos de objeto e atributo são geralmente chamados de matriz “Propriedade do objeto” ou “Atributo do objeto”. A matriz será uma tabela retangular composta por valores de características que descrevem as propriedades da amostra de observações estudada. Neste contexto, uma observação será registrada como uma linha separada composta pelos valores das características utilizadas. Um recurso separado em tal matriz de dados será representado por uma coluna que consiste nos valores desse recurso para todos os objetos da amostra.

2. 2 DISTÂNCIA ENTRE OBJETOS (MÉTRICAS)

Vamos apresentar o conceito de “distância entre objetos”. Este conceito é uma medida integral da semelhança dos objetos entre si. A distância entre objetos no espaço de recursos é um valor d ij que satisfaz os seguintes axiomas:

1. d ij > 0 (distância não negativa)

2. d ij = d ji (simetria)

3. d ij + d jk > d ik (desigualdade triangular)

4. Se d ij não for igual a 0, então i não é igual a j (discernibilidade de objetos não idênticos)

5. Se d ij = 0, então i = j (indiscernibilidade de objetos idênticos)

É conveniente representar a medida de proximidade (semelhança) de objetos como o inverso da distância entre objetos. Numerosas publicações dedicadas à análise de cluster descrevem mais de 50 métodos diferentes para calcular a distância entre objetos. Além do termo “distância”, outro termo é frequentemente encontrado na literatura - “métrico”, que implica um método para calcular uma determinada distância. A mais acessível para percepção e compreensão no caso de características quantitativas é a chamada “distância euclidiana” ou “métrica euclidiana”. A fórmula para calcular essa distância é:

Esta fórmula usa a seguinte notação:

· d ij - distância entre o i-ésimo e o j-ésimo objeto;

· x ik - valor numérico da k-ésima variável para o i-ésimo objeto;

· x jk - valor numérico da k-ésima variável para o j-ésimo objeto;

· v - o número de variáveis que descrevem objetos.

Assim, para o caso v=2, quando temos apenas duas características quantitativas, a distância d ij será igual ao comprimento da hipotenusa do triângulo retângulo, que liga dois pontos no sistema de coordenadas retangulares. Esses dois pontos corresponderão às i-ésima e j-ésima observações da amostra. Freqüentemente, em vez da distância euclidiana usual, seu quadrado d 2 ij é usado. Além disso, em alguns casos, é utilizada uma distância euclidiana “ponderada”, no cálculo da qual são utilizados coeficientes de ponderação para termos individuais. Para ilustrar o conceito da métrica euclidiana, usamos um exemplo simples de treinamento. A matriz de dados mostrada na tabela abaixo consiste em 5 observações e duas variáveis.

tabela 1

Matriz de dados de cinco amostras observadas e duas variáveis.

Usando a métrica euclidiana, calculamos a matriz de distâncias interobjetos, composta pelos valores d ij - a distância entre o i-ésimo e o j-ésimo objetos. No nosso caso, i e j são o número do objeto, observação. Como o tamanho da amostra é 5, então i e j podem assumir valores de 1 a 5, respectivamente. Também é óbvio que o número de todas as distâncias pares possíveis será igual a 5*5=25. Na verdade, para o primeiro objeto estas serão as seguintes distâncias: 1-1; 1-2; 1-3; 1-4; 1-5. Para o objeto 2 também haverá 5 distâncias possíveis: 2-1; 2-2; 2-3; 2-4; 2-5, etc. Porém, o número de distâncias diferentes será inferior a 25, pois é necessário levar em consideração a propriedade de indistinguibilidade de objetos idênticos - d ij = 0 para i = j. Isso significa que a distância entre o objeto nº 1 e o mesmo objeto nº 1 será zero. As mesmas distâncias zero serão para todos os outros casos i = j. Além disso, segue-se da propriedade de simetria que d ij = d ji para qualquer i e j. Aqueles. a distância entre os objetos nº 1 e nº 2 é igual à distância entre os objetos nº 2 e nº 1.

A expressão para a distância euclidiana lembra muito a chamada distância de Minkowski de potência generalizada, na qual outra quantidade é usada em potências em vez de dois. Em geral, este valor é denotado pelo símbolo “p”.

Quando p = 2 obtemos a distância euclidiana usual. Portanto, a expressão para a métrica generalizada de Minkowski tem a forma:

A escolha de um valor específico do expoente de potência “p” é feita pelo próprio pesquisador.

Um caso especial da distância de Minkowski é a chamada distância de Manhattan, ou “distância cidade-quarteirão”, correspondente a p=1:

Assim, a distância de Manhattan é a soma dos valores absolutos das diferenças entre as características correspondentes dos objetos. Deixando p ir para o infinito, obtemos a métrica de “dominância”, ou Sup-métrica:

que também pode ser representado na forma d ij = max| x ik - x jk |.

A métrica Minkowski é na verdade uma grande família de métricas, incluindo as métricas mais populares. No entanto, também existem métodos para calcular a distância entre objetos que são fundamentalmente diferentes das métricas de Minkowski. A mais importante delas é a chamada distância de Mahalanobis, que possui propriedades bastante específicas. Expressão para esta métrica:

Aqui através X eu E X j os vetores coluna de valores variáveis para os i-ésimo e j-ésimo objetos são indicados. Símbolo T em expressão (X eu - X j ) T denota a chamada operação de transposição vetorial. Símbolo S denota a matriz geral de variância-covariância dentro do grupo. Um símbolo -1 acima S significa que é necessário inverter a matriz S . Ao contrário da métrica de Minkowski e da métrica euclidiana, a distância de Mahalanobis através da matriz de variância-covariância S associados a correlações de variáveis. Quando as correlações entre as variáveis são zero, a distância de Mahalanobis equivale ao quadrado da distância euclidiana.

No caso de utilização de características qualitativas dicotômicas (com apenas dois valores), a distância de Hamming é amplamente utilizada

igual ao número de discrepâncias entre os valores dos recursos correspondentes para os i-ésimo e j-ésimo objetos em consideração.

2. 3 DENSIDADE E LOCALIDADE DOS CLUSTERS

O principal objetivo da análise de cluster é encontrar grupos de objetos semelhantes entre si em uma amostra. Suponhamos que por alguns dos métodos possíveis obtivemos tais grupos - clusters. Propriedades importantes dos clusters devem ser observadas. Uma dessas propriedades é a densidade de distribuição de pontos, observações dentro do cluster. Esta propriedade permite-nos definir um cluster como um cluster de pontos num espaço multidimensional, relativamente denso em comparação com outras áreas deste espaço, que ou não contém nenhum ponto ou contém um pequeno número de observações. Em outras palavras, quão compacto é um determinado cluster ou, inversamente, quão esparso ele é? Apesar da evidência suficiente desta propriedade, não existe uma forma inequívoca de calcular tal indicador (densidade). O indicador de maior sucesso que caracteriza a compactação e densidade de “empacotamento” de observações multidimensionais em um determinado cluster é a dispersão da distância do centro do cluster até pontos individuais do cluster. Quanto menor for a dispersão desta distância, quanto mais próximas do centro do aglomerado estiverem as observações, maior será a densidade do aglomerado. E vice-versa, quanto maior a dispersão da distância, mais esparso é o cluster dado e, portanto, existem pontos localizados tanto próximos ao centro do cluster quanto bastante distantes do centro do cluster.

A próxima propriedade dos clusters é o seu tamanho. O principal indicador do tamanho do cluster é o seu “raio”. Esta propriedade reflete mais completamente o tamanho real do cluster se o cluster em questão tiver uma forma redonda e for uma hiperesfera em um espaço multidimensional. No entanto, se os aglomerados tiverem formas alongadas, então o conceito de raio ou diâmetro não reflete mais o verdadeiro tamanho do aglomerado.

Outra propriedade importante de um cluster é sua localidade e separabilidade. Caracteriza o grau de sobreposição e distância mútua dos clusters entre si no espaço multidimensional. Por exemplo, considere a distribuição dos três clusters no espaço de recursos novos e integrados na figura abaixo. Os eixos 1 e 2 foram obtidos por método especial a partir de 12 sinais das propriedades reflexivas de diferentes formas de eritrócitos, estudados por microscopia eletrônica.

Imagem 1

Vemos que o cluster 1 tem o tamanho mínimo e os clusters 2 e 3 têm tamanhos aproximadamente iguais. Ao mesmo tempo, podemos dizer que a densidade mínima e, portanto, a dispersão máxima da distância, é característica do cluster 3. Além disso, o cluster 1 é separado por áreas bastante grandes de espaço vazio tanto do cluster 2 quanto do cluster 3. Enquanto os clusters 2 e 3 se sobrepõem parcialmente. Também é interessante que o cluster 1 tenha uma diferença muito maior do 2º e do 3º cluster ao longo do eixo 1 do que ao longo do eixo 2. Pelo contrário, os clusters 2 e 3 diferem aproximadamente igualmente entre si tanto ao longo do eixo 1 quanto ao longo do eixo 2. Obviamente , para tal análise visual é necessário projetar todas as observações da amostra em eixos especiais nos quais as projeções dos elementos do cluster serão visíveis como clusters separados.

2. 4 DISTÂNCIA ENTRE CLUSTERS

Num sentido mais amplo, os objetos podem ser entendidos não apenas como os objetos originais de estudo, apresentados na matriz de “propriedades do objeto” como uma linha separada, ou como pontos individuais em um espaço de características multidimensional, mas também como grupos separados de tais pontos. , unidos por um ou outro algoritmo em um cluster. Nesse caso, surge a questão de como entender a distância entre tais acúmulos de pontos (clusters) e como calculá-la. Neste caso, as possibilidades são ainda mais diversas do que no caso de calcular a distância entre duas observações num espaço multidimensional. Este procedimento é complicado pelo fato de que, diferentemente dos pontos, os clusters ocupam um certo volume de espaço multidimensional e consistem em muitos pontos. Na análise de cluster, as distâncias entre clusters são amplamente utilizadas, calculadas de acordo com o princípio do vizinho mais próximo, centro de gravidade, vizinho mais distante e medianas. Os quatro métodos mais utilizados são ligação única, ligação completa, ligação média e método de Ward. No método de link único, um objeto será unido a um cluster já existente se pelo menos um dos elementos do cluster tiver o mesmo nível de similaridade que o objeto unido. Para o método de ligação completa, um objeto é adicionado a um cluster somente se a similaridade entre um candidato à inclusão e qualquer um dos elementos do cluster não for inferior a um certo limite. Existem várias modificações no método do enlace médio que constituem um compromisso entre o enlace único e o enlace completo. Eles calculam o valor médio da similaridade de um candidato à inclusão com todos os objetos do cluster existente. A união é realizada quando o valor médio de similaridade encontrado atinge ou excede um determinado limite. O mais comumente utilizado é a média aritmética da similaridade entre os objetos do cluster e o candidato à inclusão no cluster.

Muitos dos métodos de cluster diferem entre si porque seus algoritmos calculam vários funcionais de qualidade de partição em cada etapa. O popular método Ward foi projetado para otimizar a variância mínima das distâncias intra-cluster. Na primeira etapa, cada cluster consiste em um objeto, devido ao qual a dispersão intracluster das distâncias é igual a 0. Usando este método, são combinados aqueles objetos que dão um aumento mínimo na dispersão, como resultado este método tende a gerar clusters hiperesféricos.

Tentativas repetidas de classificar métodos de análise de cluster levam a dezenas ou até centenas de classes diferentes. Essa diversidade é gerada por um grande número de métodos possíveis para calcular a distância entre observações individuais, um número igualmente grande de métodos para calcular a distância entre clusters individuais no processo de agrupamento e diversas estimativas da otimização da estrutura final do cluster.

Os mais difundidos em pacotes estatísticos populares são dois grupos de algoritmos de análise de cluster: métodos aglomerativos hierárquicos e métodos de agrupamento iterativo.

3. MÉTODOS DE AGRUPAMENTO

3. 1 CARACTERÍSTICAS DOS MÉTODOS AGLOMERATIVOS HIERÁRQUICOS

Em algoritmos hierárquicos aglomerativos, que são mais frequentemente usados em pesquisas biomédicas reais, inicialmente todos os objetos (observações) são considerados como clusters separados e independentes, constituídos por apenas um elemento. Sem o uso de tecnologia de computação poderosa, a implementação da análise de dados de cluster é muito problemática.

A escolha da métrica é feita pelo próprio pesquisador. Após calcular a matriz de distância, o processo começa aglomerações (do latim agglomero - adiciono, acumulo), passando sequencialmente passo a passo. Na primeira etapa deste processo, duas observações iniciais (monoclusters), entre as quais existe uma distância mínima, são combinadas em um cluster, composto por dois objetos (observações). Assim, em vez dos antigos N monoclusters (clusters consistindo em um objeto), após a primeira etapa haverá N-1 clusters, dos quais um cluster conterá dois objetos (observações), e N-2 clusters ainda consistirão em apenas um objeto. Na segunda etapa, são possíveis vários métodos de combinação de clusters N-2 entre si. Isso ocorre porque um desses clusters já contém dois objetos. Por esse motivo, surgem duas questões principais:

· como calcular as coordenadas de um aglomerado de dois (e mais de dois) objetos;

· como calcular a distância até tais clusters “multi-objectos” a partir de “mono-clusters” e entre clusters “multi-objectos”.

Estas questões determinam, em última análise, a estrutura final dos clusters finais (a estrutura dos clusters significa a composição dos clusters individuais e sua localização relativa no espaço multidimensional). Várias combinações de métricas e métodos para calcular as coordenadas e distâncias mútuas de clusters dão origem a uma variedade de métodos de análise de cluster. Na segunda etapa, dependendo dos métodos selecionados para calcular as coordenadas de um cluster composto por vários objetos e do método de cálculo das distâncias entre clusters, é possível mesclar novamente duas observações separadas em um novo cluster ou juntar uma nova observação para um cluster que consiste em dois objetos. Por conveniência, a maioria dos programas para métodos hierárquicos aglomerativos pode fornecer dois gráficos principais para visualização após a conclusão. O primeiro gráfico é chamado de dendrograma (do grego dendron - árvore), refletindo o processo de aglomeração, a fusão de observações individuais em um único cluster final. Vamos dar um exemplo de dendograma de 5 observações para duas variáveis.

Agendar1

O eixo vertical de tal gráfico representa o eixo da distância entre clusters, e o eixo horizontal indica o número de objetos - casos utilizados na análise. A partir deste dendograma fica claro que os objetos nº 1 e nº 2 são primeiro combinados em um cluster, uma vez que a distância entre eles é mínima e igual a 1. Esta fusão é exibida no gráfico por uma linha horizontal conectando os segmentos verticais emergentes dos pontos marcados como C_1 e C_2. Prestemos atenção ao fato de que a própria linha horizontal passa exatamente no nível da distância entre clusters igual a 1. Então, na segunda etapa, o objeto nº 3, designado como C_3, é adicionado a este cluster, que já inclui dois objetos. A próxima etapa envolve a fusão dos objetos nº 4 e nº 5, cuja distância entre eles é 1,41. E na última etapa, o cluster de objetos 1, 2 e 3 é mesclado com o cluster de objetos 4 e 5. O gráfico mostra que a distância entre esses dois penúltimos clusters (o último cluster inclui todos os 5 objetos) é superior a 5 , mas menor que 6, pois a linha horizontal superior que conecta os dois penúltimos clusters passa em um nível aproximadamente igual a 7, e o nível de conexão dos objetos 4 e 5 é igual a 1,41.

O dendograma abaixo foi obtido através da análise de um conjunto de dados reais composto por 70 amostras químicas processadas, cada uma delas caracterizada por 12 características.

Cronograma 2

O gráfico mostra que na última etapa, quando os dois últimos clusters se fundiram, a distância entre eles é de cerca de 200 unidades. Pode-se observar que o primeiro cluster inclui muito menos objetos do que o segundo cluster. Abaixo está uma seção ampliada do dendograma, na qual os números de observação, designados como C_65, C_58, etc., são claramente visíveis. (da esquerda para a direita): 65, 58, 59, 64, 63, 57, 60, 62, 56, 44, 94, etc.

Gráfico 3 Seção ampliada do gráfico nº 2 acima

Pode-se ver que o objeto 44 é um monoaglomerado que se une na penúltima etapa com o aglomerado direito e então na última etapa todas as observações são combinadas em um aglomerado.

Outro gráfico construído em tais procedimentos é um gráfico de mudanças nas distâncias entre clusters em cada etapa de fusão. Abaixo está um gráfico semelhante para o dendograma acima.

Cronograma 4

Em vários programas é possível exibir em forma tabular os resultados da combinação de objetos em cada etapa do agrupamento. Na maioria dessas tabelas, para evitar confusão, uma terminologia diferente é usada para denotar as observações iniciais - monoclusters, e os clusters reais que consistem em duas ou mais observações. Nos pacotes estatísticos em inglês, as observações iniciais (linhas da matriz de dados) são designadas como “caso”. Para demonstrar a dependência da estrutura do cluster na escolha da métrica e na escolha do algoritmo de combinação de clusters, apresentamos a seguir um dendograma correspondente ao algoritmo de conexão completo. E aqui vemos que o objeto nº 44 é mesclado com o restante da seleção na última etapa.

Cronograma 5

Agora vamos compará-lo com outro diagrama obtido usando o método de link único para os mesmos dados. Em contraste com o método de conexão completa, é claro que este método gera longas cadeias de objetos ligados uns aos outros sequencialmente. No entanto, nos três casos podemos dizer que existem dois grupos principais.

Cronograma 6

Observemos também que em todos os três casos, o objeto nº 44 se junta como um monocluster, embora em etapas diferentes do processo de agrupamento. A identificação de tais monoclusters é um bom meio de detectar observações anômalas, chamadas outliers. Vamos excluir esse objeto "suspeito" nº 44 e realizar o clustering novamente. Obtemos o seguinte dendograma:

Cronograma 7

Pode-se observar que o efeito “cadeia” foi preservado, assim como a divisão em dois grupos locais de observações.

3. 2 CARACTERÍSTICAS DOS MÉTODOS DE CLUSTERIZAÇÃO ITERATIVOS

Entre os métodos iterativos, o método mais popular é o método k-means de McKean. Ao contrário dos métodos hierárquicos, na maioria das implementações deste método o próprio usuário deve especificar o número necessário de clusters finais, que geralmente é denotado como “k”. Assim como nos métodos de cluster hierárquico, o usuário pode selecionar um ou outro tipo de métrica. Diferentes algoritmos do método k-means também diferem na maneira como selecionam os centros iniciais dos clusters especificados. Em algumas versões do método, o próprio usuário pode (ou deve) especificar tais pontos iniciais, seja selecionando-os a partir de observações reais, seja especificando as coordenadas desses pontos para cada uma das variáveis. Em outras implementações deste método, um determinado número k de pontos iniciais é selecionado aleatoriamente, e esses pontos iniciais (cluster seed) podem posteriormente ser refinados em vários estágios. Existem 4 etapas principais de tais métodos:

· k observações são selecionadas ou designadas para serem os centros primários dos clusters;

· se necessário, são formados clusters intermediários atribuindo cada observação aos centros de cluster especificados mais próximos;

· depois de atribuir todas as observações a clusters individuais, os centros primários dos clusters são substituídos pelas médias dos clusters;

· a iteração anterior é repetida até que as mudanças nas coordenadas dos centros do cluster se tornem mínimas.

Em algumas variantes deste método, o usuário pode especificar um valor numérico do critério, interpretado como a distância mínima para seleção de novos centros de cluster. Uma observação não será considerada candidata a um novo centro de cluster se a sua distância ao centro de cluster substituído exceder o número especificado. Este parâmetro é denominado “raio” em alguns programas. Além deste parâmetro, é possível definir o número máximo de iterações ou atingir um determinado número, geralmente bastante pequeno, com o qual a mudança na distância para todos os centros do cluster é comparada. Este parâmetro é geralmente chamado de "convergência" porque reflete a convergência do processo de agrupamento iterativo. Abaixo apresentamos alguns dos resultados obtidos usando o método McKean k-means para dados anteriores. O número de clusters necessários foi inicialmente definido como 3 e depois como 2. A primeira parte contém os resultados de uma análise de variância unidirecional, na qual o número do cluster atua como um fator de agrupamento. A primeira coluna contém uma lista de 12 variáveis, seguida de somas de quadrados (SS) e graus de liberdade (gl), depois o teste F de Fisher e na última coluna o nível de significância “p” alcançado.

Tabela 2 Dados obtidos pelo método McKean k-means, aplicável às 70 amostras estudadas.

Variáveis

Como se pode verificar nesta tabela, rejeita-se a hipótese nula de igualdade de médias nos três grupos. Abaixo está um gráfico dos valores médios de todas as variáveis para clusters individuais. Essas mesmas médias de agrupamento das variáveis são fornecidas abaixo em forma de tabela.

Tabela 3. Exame detalhado dos dados utilizando o exemplo de três clusters.

Variável	Cluster nº 1	Cluster nº 2	Cluster nº 3

Cronograma 8

A análise dos valores médios das variáveis de cada cluster permite-nos concluir que, segundo o atributo X1, os clusters 1 e 3 apresentam valores próximos, enquanto o cluster 2 apresenta um valor médio muito inferior ao dos outros dois clusters. Pelo contrário, de acordo com o atributo X2, o primeiro cluster apresenta o valor mais baixo, enquanto o 2º e o 3º cluster apresentam valores médios mais elevados e mais próximos. Para as características X3-X12, os valores médios no cluster 1 são significativamente maiores do que nos clusters 2 e 3. A seguinte tabela de análise de variância dos resultados do agrupamento em dois clusters também mostra a necessidade de rejeitar a hipótese nula de igualdade de médias de grupo para quase todas as 12 características, com exceção da variável X4, para a qual o nível de significância alcançado foi superior a 5%.

Tabela 4. Tabela de análise de variância dos resultados do agrupamento em dois clusters.

Variáveis

Abaixo está um gráfico e uma tabela de médias de grupo para o caso de agrupamento em dois clusters.

Tabela 5. Tabela para o caso de agrupamento em dois clusters.

Variáveis	Cluster nº 1	Cluster nº 2

Cronograma 9.

Caso o pesquisador não consiga determinar antecipadamente o número mais provável de clusters, ele é obrigado a repetir os cálculos, especificando um número diferente deles, à semelhança do que foi feito acima. E então, comparando os resultados obtidos entre si, escolha uma das opções de cluster mais aceitáveis.

4 . CLUSTERING DE RECURSOS

Além de agrupar observações individuais, também existem algoritmos para agrupar recursos. Um dos primeiros métodos é o método de correlação de galáxias de P. V. Terentyev. Imagens primitivas de tais galáxias podem frequentemente ser encontradas em publicações biomédicas na forma de um círculo pontilhado com setas conectando sinais para os quais os autores descobriram uma correlação. Vários programas possuem procedimentos separados para agrupar objetos e recursos. Por exemplo, no pacote SAS, o procedimento VARCLUS (de VARiable - variável e CLUSter - cluster) é usado para agrupar características, enquanto a análise de cluster de observações é realizada por outros procedimentos - FASTCLUS e CLUSTER. Em ambos os casos, o dendograma é construído utilizando o procedimento TREE (árvore).

Nos demais pacotes estatísticos, a seleção dos elementos para agrupamento – objetos ou feições – é feita no mesmo módulo. Expressões que incluem o valor de certos coeficientes que refletem a força do relacionamento para um par de recursos são frequentemente usadas como métrica ao agrupar recursos. Neste caso, é muito conveniente para recursos com força de conexão igual a um (dependência funcional) considerar a distância entre recursos igual a zero. Na verdade, com uma conexão funcional, o valor de uma característica pode ser usado para calcular com precisão o valor de outra característica. À medida que a força da conexão entre os recursos diminui, a distância aumenta proporcionalmente. Abaixo está um gráfico que mostra o dendograma para combinar os 12 recursos que foram usados acima no agrupamento das 70 amostras analíticas.

Gráfico 10. Dendogramaagrupamento de 12 recursos.

Como pode ser visto neste dendograma, estamos lidando com dois agrupamentos locais de características: X1-X10 e X11-X12. O grupo de características X1-X10 é caracterizado por um valor bastante pequeno de distâncias entre clusters, não excedendo aproximadamente 100 unidades. Aqui também vemos alguns subgrupos emparelhados internos: X1 e X2, X3 e X4, X6 e X7. A distância entre as características destes pares, que é muito próxima de zero, indica a sua forte relação entre pares. Já para o par X11 e X12, a distância entre clusters é muito maior e é de cerca de 300 unidades. Finalmente, a distância muito grande entre os clusters esquerdo (X1-X10) e direito (X11-X12), igual a aproximadamente 1150 unidades, sugere que a relação entre estes dois grupos de características é mínima.

5. ESTABILIDADE E QUALIDADE DA CLUSTERIZAÇÃO

Obviamente, seria absurdo levantar a questão de quão absoluta é esta ou aquela classificação obtida por meio de métodos de análise de cluster. Ao alterar o método de agrupamento, a estabilidade se manifesta no fato de que dois clusters são claramente visíveis nos dendrogramas.

Como uma das formas possíveis de verificar a estabilidade dos resultados da análise de cluster, pode ser utilizado o método de comparação dos resultados obtidos para diferentes algoritmos de cluster. Outras formas são o chamado método bootstrap proposto por B. Efron em 1977, os métodos “jackknife” e “sliding control”. O meio mais simples de testar a robustez de uma solução de agrupamento seria dividir aleatoriamente a amostra original em duas partes aproximadamente iguais, agrupar ambas as partes e depois comparar os resultados. Uma maneira mais trabalhosa envolve excluir sequencialmente o primeiro objeto primeiro e agrupar os objetos restantes (N - 1). Em seguida, realizando sequencialmente este procedimento com exceção do segundo, terceiro, etc. objetos, a estrutura de todos os N clusters resultantes é analisada. Outro algoritmo de teste de robustez envolve propagação múltipla, duplicando a amostra original de N objetos, depois combinando todas as amostras duplicadas em uma grande amostra (pseudopopulação) e extraindo aleatoriamente uma nova amostra de N objetos dela. Depois disso, é realizado o agrupamento desta amostra, em seguida, uma nova amostra aleatória é extraída e o agrupamento é realizado novamente, etc. Este também é um caminho bastante trabalhoso.

Não há menos problemas ao avaliar a qualidade do clustering. Existem muitos algoritmos para otimizar soluções de cluster. Os primeiros trabalhos que continham formulações de um critério para minimizar a variância intra-cluster e um algoritmo (como k-means) para encontrar uma solução ótima surgiram na década de 50. Em 1963 O artigo de J. Ward também descreveu um algoritmo de otimização hierárquica semelhante. Não existe um critério universal para otimizar uma solução de cluster. Tudo isso dificulta ao pesquisador a escolha da solução ótima. Em tal situação, a melhor forma de estabelecer que a solução de cluster encontrada é ótima nesta fase do estudo é apenas a consistência desta solução com as conclusões obtidas por meio de outros métodos de estatística multivariada.

A conclusão sobre a otimalidade do agrupamento também é apoiada pelos resultados positivos do teste dos momentos preditivos da solução obtida em outros objetos de estudo. Ao usar métodos hierárquicos de análise de cluster, podemos recomendar a comparação de vários gráficos de mudanças passo a passo na distância entre clusters. Neste caso, deve-se dar preferência à opção para a qual existe uma linha plana de tal incremento desde o primeiro passo até vários penúltimos passos com um aumento vertical acentuado deste gráfico nos últimos 1-2 passos do agrupamento.

CONCLUSÕES

No meu trabalho procurei mostrar não só a complexidade deste tipo de análise, mas também as capacidades ótimas de processamento de dados, pois muitas vezes para a precisão dos resultados é necessário utilizar de dezenas a centenas de amostras. Este tipo de análise ajuda a classificar e processar os resultados. Penso também que não deixa de ser importante que a tecnologia informática seja aceitável nesta análise, o que permite tornar o processo de processamento dos resultados menos trabalhoso e, assim, permite-nos prestar mais atenção à correta seleção das amostras para análise.

Existem sutilezas e detalhes no uso da análise de cluster que aparecem em casos individuais específicos e não são imediatamente visíveis. Por exemplo, o papel da escala de características pode ser mínimo ou pode ser dominante em vários casos. Nesses casos, é necessário utilizar transformações de variáveis. Isto é especialmente eficaz ao usar métodos que produzem transformações não lineares de recursos que geralmente aumentam o nível geral de correlações entre recursos.

Há ainda maior especificidade na utilização da análise de cluster em relação a objetos que são descritos apenas por características qualitativas. Nesse caso, os métodos de digitalização preliminar de características qualitativas e de realização de análise de cluster com novas características são bastante bem-sucedidos. Em meu trabalho, mostrei que a análise de cluster fornece muitas informações novas e originais tanto quando aplicada a sistemas suficientemente estudados quanto ao estudar sistemas com estrutura desconhecida.

Deve-se notar também que a análise de agrupamento tornou-se indispensável nos estudos evolutivos, permitindo a construção de árvores filogenéticas mostrando caminhos evolutivos. Esses métodos também são amplamente utilizados em programas de pesquisa científica em química física e analítica.

BIBLIOGRAFIA

1) Ayvazyan S. A., Enyukov I. S., Meshalkin L. D. Sobre a estrutura e conteúdo de um pacote de software para análise estatística aplicada // Algorítmico e software para análise estatística aplicada. - M., 1980.

2) Ayvazyan S. A., Bezhaeva Z. I., Staroverov O. V. Classificação de observações multidimensionais... - M.: Estatísticas, 1974.

3) Becker V. A., Lukatskaya M. L. Sobre a análise da estrutura da matriz de coeficientes de acoplamento // Questões de modelagem e previsão econômico-estatística na indústria. - Novosibirsk, 1970.

4) Braverman E. M., Muchnik I. B. Métodos estruturais de processamento de dados... - M.: Nauka, 1983.

5) Voronin Yu. A. Teoria da classificação e suas aplicações. - Novosibirsk: Nauka, 1987.

6) Bom I. J. Botriologia de botryologia // Classificação e cluster. - M.: Mir, 1980.

7) Dubrovsky S.A. Análise estatística multivariada aplicada - M.: Finanças e Estatística, 1982.

8) Durand N., Odell P. Análise de cluster... - M.: Estatísticas, 1977.

9) Eliseeva I. I., Rukavishnikov V. S. Agrupamento, correlação, reconhecimento de padrões... - M.: Estatísticas, 1977.

10) Zagoruiko N. G. Métodos de reconhecimento e sua aplicação. - M.: Rádio Soviética, 1972.

11) Zade L. A. Conjuntos desfocados e sua aplicação em reconhecimento de padrões e análise de cluster // Classificação e cluster. - M.: Mir, 1980.

12) Kildishev G. S., Abolentsev Yu. I. Agrupamentos multidimensionais... - M.: Estatísticas, 1978.

13) Raiskaya I. I., Gostilin N. I., Frenkel A. A. Sobre uma maneira de verificar a validade do particionamento na análise de cluster.//Aplicação da análise estatística multivariada em economia e avaliação da qualidade do produto.--Ch. P. Tartu, 1977.

14) Shurygin A. M. Distribuição de distâncias e diferenças entre pontos // Software e suporte algorítmico para análise estatística multivariada aplicada. - M., 1983.

15) Eeremaa R. Teoria geral de projeto de sistemas de cluster e algoritmos para encontrar suas representações numéricas: Procedimentos do Centro de Computação da TSU. - Tartu, 1978.

16) Yastremsky B. S. Obras selecionadas - M.: Estatísticas, 1964.

Documentos semelhantes

Objetivos de segmentação de mercado nas atividades de marketing. A essência da análise de cluster, as principais etapas da sua implementação. Selecionar um método de medição de distância ou uma medida de similaridade. Métodos de agrupamento hierárquicos e não hierárquicos. Avaliando confiabilidade e validade.

relatório, adicionado em 02/11/2009

Principais indicadores da situação financeira do empreendimento. A crise na empresa, suas causas, tipos e consequências. Métodos e ferramentas modernas de análise de cluster, características de sua utilização para avaliação financeira e econômica de um empreendimento.

tese, adicionada em 09/10/2013

Realização de análise de cluster de empreendimentos utilizando o programa Statgraphics Plus. Construção de uma equação de regressão linear. Cálculo de coeficientes de elasticidade utilizando modelos de regressão. Avaliação da significância estatística da equação e do coeficiente de determinação.

tarefa, adicionada em 16/03/2014

Construção de regressões tipológicas para grupos individuais de observações. Dados espaciais e informações temporais. Áreas de aplicação da análise de cluster. O conceito de homogeneidade de objetos, propriedades da matriz de distância. Realizando regressão tipológica.

apresentação, adicionada em 26/10/2013

Criação de modelos e métodos combinados como método moderno de previsão. Modelo baseado em ARIMA para descrever séries temporais estacionárias e não estacionárias ao resolver problemas de agrupamento. Modelos AR autorregressivos e aplicações de correlogramas.

apresentação, adicionada em 01/05/2015

Características de vários tipos de métricas. O método dos vizinhos mais próximos e suas generalizações. Algoritmo do vizinho mais próximo. Método da janela Parzen. Classificador métrico generalizado. O problema de escolher uma métrica. Manhattan e distância euclidiana. Medida de cosseno.

trabalho do curso, adicionado em 08/03/2015

Características da indústria da construção na região de Krasnodar. Previsão de desenvolvimento de construção habitacional. Métodos e ferramentas modernas para análise de cluster. Métodos estatísticos multivariados para diagnosticar a situação econômica de uma empresa.

tese, adicionada em 20/07/2015

Características dos empréstimos hipotecários no exemplo da região de Bryansk. Revisão de métodos matemáticos de tomada de decisão: avaliações de especialistas, comparações sequenciais e pareadas, análise de hierarquias. Desenvolvimento de um programa para encontrar o empréstimo hipotecário ideal.

trabalho do curso, adicionado em 29/11/2012

Áreas de aplicação da análise de sistemas, seu lugar, papel, objetivos e funções na ciência moderna. O conceito e conteúdo das técnicas de análise de sistemas, seus métodos informais. Características de métodos de pesquisa heurística e especializada e características de sua aplicação.

trabalho do curso, adicionado em 20/05/2013

Desenvolvimento e investigação de métodos econométricos tendo em conta as especificidades dos dados económicos e de acordo com as necessidades da ciência e prática económica. Aplicação de métodos e modelos econométricos para análise estatística de dados económicos.

Este livro é dedicado a uma das abordagens mais promissoras nesse sentido para a análise de processos e fenômenos multidimensionais - a análise de cluster.

A análise de cluster é um método de agrupamento de objetos multidimensionais, baseado na representação dos resultados de observações individuais por pontos de um espaço geométrico adequado, seguida da identificação de grupos como “aglomerados” desses pontos. Na verdade, “cluster” em inglês significa “cacho”, “cacho (de uvas)”, “cacho (de estrelas)”, etc. Este termo se encaixa extraordinariamente bem na terminologia científica, já que sua primeira sílaba corresponde ao tradicional o termo “ classe”, e a segunda parece indicar sua origem artificial. Não temos dúvidas de que a terminologia da análise de cluster substituirá todos os construtos anteriormente utilizados para este fim (reconhecimento não supervisionado de padrões, estratificação, taxonomia, classificação automática, etc.). O potencial da análise de cluster é óbvio para resolver, digamos, os problemas de identificação de grupos de empresas que operam em condições semelhantes ou com resultados semelhantes, grupos homogéneos da população em vários aspectos da vida ou estilo de vida em geral, etc.

A análise de cluster surgiu como uma direção científica em meados dos anos 60 e vem se desenvolvendo rapidamente desde então, sendo um dos ramos de crescimento mais intenso da ciência estatística. Basta dizer que o número de monografias apenas sobre análise de cluster, publicadas até o momento em diferentes países, é medido na casa das centenas (enquanto, digamos, em um método tão “merecido” de análise estatística multivariada como análise fatorial, dificilmente é possível contar várias dezenas de livros). E isso é perfeitamente compreensível. Afinal, estamos falando na verdade de modelar a operação de agrupamento, uma das mais importantes não só na estatística, mas em geral – tanto na cognição quanto na tomada de decisão.

Várias monografias foram publicadas em nosso país dedicadas ao estudo de problemas socioeconômicos específicos usando a análise de cluster (1), a metodologia para usar a análise de cluster na pesquisa socioeconômica (2), a metodologia de análise de cluster como tal ( 3) (Fundamentos da análise estatística)

O livro proposto por I. D. Mandel é, por assim dizer, perpendicular a esta classificação: o seu conteúdo está ligado a cada uma destas três áreas.

O objetivo do livro é resumir o estado atual da análise de cluster, analisar as possibilidades de seu uso e tarefas para desenvolvimento posterior. Este plano por si só não pode deixar de despertar respeito: a análise imparcial e a generalização exigem muito trabalho, erudição, coragem e são muito menos valorizadas pela comunidade científica do que a promoção e desenvolvimento dos seus próprios desígnios. (No entanto, o livro também contém desenvolvimentos originais do autor relacionados à análise “intensional” e à dualidade de classificações.)

O alcance desse objetivo está associado tanto às vantagens do livro quanto às suas desvantagens. As vantagens incluem:

· elaboração metodológica dos conceitos de homogeneidade, agrupamento e classificação, tendo em conta a multidimensionalidade dos fenómenos e processos;

· uma revisão sistemática de abordagens e métodos de análise de cluster (incluindo até 150 algoritmos específicos);

· apresentação da tecnologia e resultados de comparação experimental de procedimentos de análise de cluster; Este livro é dedicado a uma das abordagens mais promissoras nesse sentido para a análise de processos e fenômenos multidimensionais - a análise de cluster.

Estas vantagens determinam o lugar independente do livro de I. D. Mandel entre outras publicações.

As deficiências do livro são a ambiguidade de algumas recomendações e a falta de uma análise sistemática da utilização de métodos de análise de cluster em aplicações socioeconómicas específicas de assuntos. É verdade que este último se deve ao uso insuficiente da análise de cluster nesta área.

O livro fornece um trampolim, cujo uso facilita o progresso na questão mais difícil de qualquer teoria – o uso prático das ferramentas que ele fornece.

BG Mirkin

Universidade: VZFEI

Ano e cidade: Moscou 2008

1. Introdução. O conceito de método de análise de cluster.

2. Descrição da metodologia de utilização da análise de cluster. Exemplo de teste de resolução de problemas.

4. Lista de referências utilizadas

Introdução. O conceito de método de análise de cluster.

A análise de cluster é um conjunto de métodos que permitem classificar observações multidimensionais, cada uma delas descrita por um conjunto de características (parâmetros) X1, X2,…, Xk.

O objetivo da análise de cluster é a formação de grupos de objetos semelhantes, normalmente chamados de clusters (classe, táxon, condensação).

A análise de cluster é uma das áreas da pesquisa estatística. Ocupa um lugar particularmente importante nos ramos da ciência associados ao estudo de fenômenos e processos de massa. A necessidade de desenvolver métodos de análise de cluster e sua utilização é ditada pelo fato de ajudarem a construir classificações com base científica e a identificar conexões internas entre unidades da população observada. Além disso, métodos de análise de cluster podem ser utilizados para compactar informações, o que é um fator importante no contexto de constante aumento e complexidade dos fluxos de dados estatísticos.

Os métodos de análise de cluster permitem resolver os seguintes problemas:

Realizar classificação de objetos levando em consideração características que refletem a essência e a natureza dos objetos. A resolução de tal problema, via de regra, leva ao aprofundamento do conhecimento sobre a totalidade dos objetos classificados;

Verificar as suposições feitas sobre a presença de alguma estrutura no conjunto de objetos estudados, ou seja, procurar uma estrutura existente;

Construção de novas classificações para fenómenos pouco estudados, quando é necessário estabelecer a presença de ligações dentro de uma população e tentar introduzir-lhe estrutura (1, pp. 85-86).

2. Descrição da metodologia de aplicação da análise de cluster. Exemplo de teste de resolução de problemas.

A análise de cluster permite que n objetos caracterizados por k características sejam divididos em grupos homogêneos (clusters). A homogeneidade dos objetos é determinada pela distância p(xi xj), onde xi = (xi1,…., xik) e xj= (xj1,…, xjk) são vetores compostos pelos valores de k características do i -ésimo e j-ésimo objetos, respectivamente.

Para objetos caracterizados por características numéricas, a distância é determinada pela seguinte fórmula:

p(xi , xj) = √ ∑(x1m-xjm) 2 (1)*

Objetos são considerados homogêneos se p(xi xj)< p предельного.

Uma representação gráfica da união pode ser obtida usando uma árvore de união de cluster - um dendograma. (2. Capítulo 39).

Caso de teste (exemplo 92).


Volume de vendas

Vamos classificar esses objetos usando o princípio do “vizinho mais próximo”. Vamos encontrar as distâncias entre objetos usando a fórmula (1)*. Vamos preencher a tabela.

Vamos explicar como a tabela é preenchida.

Na intersecção da linha i com a coluna j, é indicada a distância p(xi xj) (o resultado é arredondado para duas casas decimais).

Por exemplo, na intersecção da linha 1 e coluna 3 a distância p(x1, x3) = √(1-6) 2 +(9-8) 2 ≈ 5,10 é indicada, e na intersecção da linha 3 e coluna 5 a distância p(x3, x5) = √ (6-12) 2 + (8-7) 2 ≈ 6,08. Como p(xi, xj) = p(xj,xi), a parte inferior da tabela não precisa ser preenchida.

Apliquemos o princípio do “vizinho mais próximo”. Encontramos na tabela a menor das distâncias (se houver várias dessas distâncias, escolha qualquer uma delas). Isso é p 1,2 ≈ p 4,5 = 2,24. Seja p min = p 4,5 = 2,24. Então podemos combinar os objetos 4 e 5 em um grupo, ou seja, as colunas 4 e 5 combinadas terão o menor dos números correspondentes nas colunas 4 e 5 da tabela de distâncias original. Fazemos o mesmo com as linhas 4 e 5. Obtemos uma nova tabela.

Encontramos na tabela resultante a menor das distâncias (se houver várias delas, escolha qualquer uma delas): p min = p 1,2 = 2,24. Então podemos combinar os objetos 1,2,3 em um grupo, ou seja, a coluna combinada 1,2,3 conterá o menor dos números correspondentes das colunas 1 e 2 e 3 da tabela de distâncias anterior. Fazemos o mesmo com as linhas 1, 2 e 3. Obtemos uma nova tabela.

Obtivemos dois clusters: (1,2,3) e (4,5).

3. Resolvendo problemas para o teste.

Problema 85.

Condições: Cinco unidades de produção são caracterizadas por duas características: volume de vendas e custo médio anual dos ativos fixos.


Volume de vendas
Custo médio anual de ativos fixos

Solução: Vamos encontrar as distâncias entre objetos usando a fórmula (1)* (arredondando para duas casas decimais):

р 1,1 = √ (2-2) 2 + (2-2) 2 = 0

р 1,2 = √ (2-5) 2 + (7-9) 2 ≈ 3,61

р 1,3 = √ (2-7) 2 + (7-10) 2 ≈ 5,83

p 2,2 = √ (5-5) 2 + (9-9) 2 =0

р 2,3 = √ (5-7) 2 + (9-10) 2 ≈ 2,24

p 3,4 = √ (7-12) 2 + (10-8) 2 ≈5,39

p 3,5 = √ (7-13) 2 + (10-5) 2 ≈ 7,81

р 4,5 = √ (12-13) 2 + (8-5) 2 ≈ 3,16

Com base nos resultados do cálculo, preencha a tabela:

Apliquemos o princípio do “vizinho mais próximo”. Para fazer isso, encontramos a menor das distâncias na tabela (se houver várias dessas distâncias, selecione qualquer uma delas). Isso é p 2,3=2,24. Seja p min = p 2,3 = 2,24, então podemos mesclar os objetos das colunas “2” e “3”, e também mesclar as linhas dos objetos “2” e “3”. Na nova tabela, inserimos os menores valores da tabela original nos grupos combinados.

Na nova tabela encontramos a menor das distâncias (se houver várias delas, selecione qualquer uma delas). Isso é p 4,5 = 3,16. Seja p min = p 4,5 = 3,16, então podemos mesclar os objetos das colunas “4” e “5”, e também mesclar as linhas dos objetos “4” e “5”. Na nova tabela, inserimos os menores valores da tabela original nos grupos combinados.

Na nova tabela encontramos a menor das distâncias (se houver várias delas, selecione qualquer uma delas). Isto é p 1, 2 e 3 = 3,61. Seja p min = p 1, 2 e 3 = 3,61, então podemos mesclar os objetos de coluna "1" e "2 e 3" e também mesclar linhas. Na nova tabela, inserimos os menores valores da tabela original nos grupos combinados.

Obtemos dois clusters: (1,2,3) e (4,5).

O dendograma mostra a ordem de seleção dos elementos e as distâncias mínimas correspondentes p min.

Responder: Como resultado da análise de cluster usando o princípio do “vizinho mais próximo”, foram formados 2 clusters de objetos semelhantes: (1,2,3) e (4,5).

Problema 211.

Condições: Cinco unidades de produção são caracterizadas por duas características: volume de vendas e custo médio anual dos ativos fixos.


Volume de vendas
Custo médio anual de ativos fixos

Classifique esses objetos usando o princípio do “vizinho mais próximo”.

Solução: Para resolver o problema, apresentamos os dados da tabela original. Vamos determinar as distâncias entre os objetos. Vamos classificar os objetos de acordo com o princípio do “vizinho mais próximo”. Apresentamos os resultados na forma de um dendograma.


Volume de vendas
Custo médio anual de ativos fixos

Usando a fórmula (1)* encontramos as distâncias entre objetos:

p 1,1 =0, p 1,2 =6, p 1,3 =8,60, p 1,4 =6,32, p 1,5 =6,71, p 2,2 =0, p 2 ,3 =7,07, p 2,4 =2, p 2,5 =3,32, p 3,3 = 0, p 3,4 =5,10, p 3,5 =4,12, p 4 ,4 =0, p 4,5 =1, p 5,5 =0.

Apresentamos os resultados na tabela:

O menor valor das distâncias na tabela é p 4,5=1. Seja p min = p 4,5 = 1, então podemos mesclar os objetos das colunas “4” e “5”, e também mesclar as linhas dos objetos “4” e “5”. Na nova tabela, inserimos os menores valores da tabela original nos grupos combinados.

O menor valor das distâncias na nova tabela é p 2, 4 e 5=2. Seja p min = p 2, 4 e 5=2, então podemos mesclar os objetos das colunas “4 e 5” e “3”, e também mesclar as linhas dos objetos “4 e 5” e “3”. Na nova tabela, inserimos os menores valores da tabela nos grupos combinados.

O menor valor das distâncias na nova tabela é p 3,4,5=2. Seja p min = p 3,4,5=2, então podemos mesclar os objetos das colunas “3,4,5” e “2”, e também mesclar as linhas dos objetos “3,4,5” e “2”. Na nova tabela, inserimos os menores valores da tabela nos grupos combinados.

ou faça login no site.

Importante! Todos os Testes submetidos para download gratuito destinam-se à elaboração de um plano ou base para o seu próprio trabalho científico.

Amigos! Você tem uma oportunidade única de ajudar estudantes como você! Se nosso site o ajudou a encontrar o emprego que você precisa, então você certamente entende como o emprego que você adiciona pode facilitar o trabalho de outras pessoas.

Se o trabalho do Teste, na sua opinião, for de má qualidade, ou se você já viu esse trabalho, avise-nos.

ANÁLISE DE CLUSTER EM TAREFAS DE PREVISÃO SOCIOECONÔMICA

Introdução à análise de cluster.

Ao analisar e prever fenômenos socioeconômicos, o pesquisador muitas vezes se depara com a multidimensionalidade de sua descrição. Isto ocorre ao resolver o problema da segmentação do mercado, construindo uma tipologia de países com base num número bastante grande de indicadores, prevendo as condições de mercado para bens individuais, estudando e prevendo a depressão económica e muitos outros problemas.

Os métodos de análise multivariada são a ferramenta quantitativa mais eficaz para estudar processos socioeconômicos descritos por um grande número de características. Isso inclui análise de cluster, taxonomia, reconhecimento de padrões e análise fatorial.

A análise de cluster reflete mais claramente as características da análise multivariada na classificação, análise fatorial - no estudo dos relacionamentos.

Às vezes, a abordagem de análise de cluster é chamada na literatura de taxonomia numérica, classificação numérica, reconhecimento de autoaprendizagem, etc.

A análise de cluster encontrou sua primeira aplicação na sociologia. O nome análise de cluster vem da palavra inglesa cluster – grupo, acumulação. Pela primeira vez em 1939, o tema da análise de cluster foi definido e descrito pelo pesquisador Trion. O principal objetivo da análise de cluster é dividir o conjunto de objetos e características em estudo em grupos ou clusters homogêneos no sentido apropriado. Isso significa que o problema de classificação dos dados e identificação da estrutura correspondente está sendo resolvido. Os métodos de análise de cluster podem ser utilizados nos mais diversos casos, mesmo nos casos em que se trata de agrupamento simples, em que tudo se resume à formação de grupos com base na similaridade quantitativa.

A grande vantagem da análise de cluster é que ela permite dividir objetos não de acordo com um parâmetro, mas de acordo com todo um conjunto de características. Além disso, a análise de cluster, ao contrário da maioria dos métodos matemáticos e estatísticos, não impõe quaisquer restrições ao tipo de objetos em consideração e permite considerar uma variedade de dados iniciais de natureza quase arbitrária. Isto é de grande importância, por exemplo, para prever a situação do mercado, quando os indicadores têm uma forma diversificada, dificultando a utilização de abordagens econométricas tradicionais.

A análise de cluster permite considerar uma quantidade bastante grande de informações e reduzir e compactar drasticamente grandes quantidades de informações socioeconômicas, tornando-as compactas e visuais.

A análise de cluster é importante em relação a conjuntos de séries temporais que caracterizam o desenvolvimento económico (por exemplo, condições económicas gerais e de mercadorias). Aqui você pode destacar períodos em que os valores dos indicadores correspondentes foram bastante próximos, e também determinar grupos de séries temporais cujas dinâmicas são mais semelhantes.

A análise de cluster pode ser usada iterativamente. Nesse caso, a pesquisa é realizada até que os resultados desejados sejam alcançados. Além disso, cada ciclo aqui pode fornecer informações que podem mudar bastante a direção e as abordagens para a aplicação posterior da análise de cluster. Este processo pode ser representado como um sistema de feedback.

Nas tarefas de previsão socioeconómica, a combinação da análise de cluster com outros métodos quantitativos (por exemplo, análise de regressão) é muito promissora.

Como qualquer outro método, a análise de agrupamentos tem certas desvantagens e limitações: Em particular, a composição e o número de agrupamentos dependem dos critérios de partição selecionados. Ao reduzir a matriz de dados original para uma forma mais compacta, certas distorções podem ocorrer e as características individuais de objetos individuais podem ser perdidas devido à sua substituição pelas características de valores generalizados dos parâmetros do cluster. Ao classificar objetos, a possibilidade de ausência de quaisquer valores de cluster na população considerada é muitas vezes ignorada.

Na análise de cluster considera-se que:

a) as características selecionadas permitem, em princípio, a desejada divisão em clusters;

b) as unidades de medida (escala) são escolhidas corretamente.

A escolha da escala desempenha um grande papel. Normalmente, os dados são normalizados subtraindo a média e dividindo pelo desvio padrão para que a variância seja igual a um.

Problema de análise de cluster.

A tarefa da análise de cluster é, com base nos dados contidos no conjunto X, dividir o conjunto de objetos G em m (m é um número inteiro) clusters (subconjuntos) Q1, Q2, ..., Qm, de modo que cada objeto Gj pertence a um e apenas um subconjunto da partição e de modo que os objetos pertencentes ao mesmo cluster são semelhantes, enquanto os objetos pertencentes a clusters diferentes são heterogêneos.

Por exemplo, deixe G incluir n países, qualquer um dos quais é caracterizado pelo PIB per capita (F1), o número M de carros por 1 mil pessoas (F2), consumo de eletricidade per capita (F3), consumo de aço per capita (F4) , etc. Então X1 (vetor de medição) é um conjunto de características especificadas para o primeiro país, X2 para o segundo, X3 para o terceiro, etc. O objetivo é categorizar os países por nível de desenvolvimento.

A solução para o problema de análise de cluster são partições que satisfaçam algum critério de otimalidade. Este critério pode ser algum tipo de funcional que expressa os níveis de desejabilidade de várias partições e agrupamentos, que é chamado de função objetivo. Por exemplo, a soma dos desvios quadrados dentro do grupo pode ser considerada como a função objetivo:

onde xj representa as medidas do j-ésimo objeto.

Para resolver o problema da análise de cluster, é necessário definir o conceito de similaridade e heterogeneidade.

É claro que os objetos i-ésimo e j-ésimo cairiam em um cluster quando a distância (afastamento) entre os pontos Xi e Xj fosse pequena o suficiente e cairiam em clusters diferentes quando essa distância fosse grande o suficiente. Assim, cair em um ou diferentes grupos de objetos é determinado pelo conceito de distância entre Xi e Xj de Ep, onde Ep é um espaço euclidiano p-dimensional. Uma função não negativa d(Xi, Xj) é chamada de função distância (métrica) se:

a) d(Хi, Хj) ³ 0, para todos Хi e Хj de Ep

b) d(Хi, Хj) = 0, se e somente se Хi = Хj

c) d(Хi, Хj) = d(Хj, Хi)

d) d(Xi, Xj) £ d(Xi, Xk) + d(Xk, Xj), onde Xj; Xi e Xk são quaisquer três vetores de Ep.

O valor d(Хi, Хj) para Хi e Хj é denominado distância entre Хi e Хj e equivale à distância entre Gi e Gj de acordo com as características selecionadas (F1, F2, F3, ..., Fр).

As funções de distância mais comumente usadas são:

1. Distância euclidiana d2(Хi, Хj) =

2. l1 - norma d1(Хi, Хj) =

3. Supremo - norma d¥ (Хi, Хj) = sup

k = 1, 2, ..., p

4. lp - norma dр(Хi, Хj) =

A métrica euclidiana é a mais popular. A métrica l1 é a mais fácil de calcular. A norma suprema é fácil de calcular e inclui um procedimento de ordenação, e a norma lp cobre as funções de distância 1, 2, 3,.

Sejam n dimensões X1, X2,..., Xn representadas como uma matriz de dados de tamanho p ´n:

Então a distância entre pares de vetores d(Хi, Хj) pode ser representada como uma matriz simétrica de distâncias:

O conceito oposto à distância é o conceito de semelhança entre objetos Gi. e Gj. Uma função real não negativa S(Хi ; Хj) = Sij é chamada de medida de similaridade se:

1) 0 £ S(Хi, Хj)<1 для Хi¹ Хj

2) S(Хi, Хi) = 1

3) S(Хi, Хj) = S(Хj, Хi)

Pares de valores de medidas de similaridade podem ser combinados em uma matriz de similaridade:

O valor Sij é chamado de coeficiente de similaridade.

1.3. Métodos de análise de cluster.

Hoje existem muitos métodos de análise de cluster. Vejamos alguns deles (os métodos fornecidos abaixo são geralmente chamados de métodos de variância mínima).

Seja X uma matriz de observações: X = (X1, X2,..., Xu) e o quadrado da distância euclidiana entre Xi e Xj é determinado pela fórmula:

1) Método de conexões completas.

A essência deste método é que dois objetos pertencentes ao mesmo grupo (cluster) têm um coeficiente de similaridade menor que um determinado valor limite S. Em termos da distância euclidiana d, isso significa que a distância entre dois pontos (objetos) do cluster não deve exceder um determinado valor limite h. Assim, h define o diâmetro máximo permitido do subconjunto que forma o cluster.

2) Método de distância local máxima.

Cada objeto é tratado como um cluster de ponto único. Os objetos são agrupados de acordo com a seguinte regra: dois clusters são combinados se a distância máxima entre os pontos de um cluster e os pontos do outro for mínima. O procedimento consiste em n - 1 etapas e o resultado são partições que coincidem com todas as partições possíveis no método anterior para quaisquer valores limite.

3) Método do Word.

Neste método, utiliza-se como função objetivo a soma intragrupo dos desvios quadrados, que nada mais é do que a soma dos quadrados das distâncias entre cada ponto (objeto) e a média do cluster que contém esse objeto. Em cada etapa, dois clusters são combinados que levam a um aumento mínimo na função objetivo, ou seja, soma dos quadrados dentro do grupo. Este método visa combinar clusters próximos.

4) Método centróide.

A distância entre dois clusters é definida como a distância euclidiana entre os centros (médias) desses clusters:

d2 ij = (`X – `Y)Т(`X – `Y) O agrupamento ocorre passo a passo em cada uma das n–1 etapas, dois clusters G e p são combinados, tendo um valor mínimo d2ij Se n1 for muito maior que n2, então os centros de fusão dos dois clusters estão próximos um do outro e as características do segundo cluster são praticamente ignoradas ao combinar clusters. Este método às vezes também é chamado de método de grupo ponderado.

1.4 Algoritmo de agrupamento sequencial.

Considere Ι = (Ι1, Ι2, … Ιn) como um conjunto de clusters (Ι1), (Ι2),…(Ιn). Vamos escolher dois deles, por exemplo, Ι i e Ι j, que em certo sentido estão mais próximos um do outro e combiná-los em um cluster. O novo conjunto de clusters, já composto por n-1 clusters, será:

(Ι1), (Ι2)…, (Ι i, Ι j),…, (Ιn).

Repetindo o processo, obtemos conjuntos sucessivos de clusters consistindo em (n-2), (n-3), (n–4), etc. aglomerados. Ao final do procedimento, pode-se obter um cluster composto por n objetos e coincidindo com o conjunto original Ι = (Ι1, Ι2,… Ιn).

Como medida de distância, tomamos o quadrado da métrica euclidiana di j2. e calcule a matriz D = (di j2), onde di j2 é o quadrado da distância entre

Ι1	Ι2	Ι3	….	Não
Ι1	0	d122	d132	….	d1n2
Ι2	0	d232	….	d2n2
Ι3	0	….	d3n2
….	….	….
Não	0

Seja a distância entre Ι i e Ι j mínima:

di j2 = min (di j2, i ¹ j). Usando Ι i e Ι j formamos um novo cluster

(Ι eu, Ι j). Vamos construir uma nova matriz de distância ((n-1), (n-1))

(Ι eu, Ι j)	Ι1	Ι2	Ι3	….	Não
(Ι eu; Ι j)	0	de j21	do j22	de j23	….	de j2n
Ι1	0	d122	d13	….	d12n
Ι2	0	de j21	….	d2n
Ι3	0	….	d3n
Não	0

As (n-2) linhas da última matriz são retiradas da anterior e a primeira linha é recalculada. Os cálculos podem ser reduzidos ao mínimo se pudermos expressar di j2k,k = 1, 2,…, n; (k ¹ i ¹ j) através dos elementos da matriz original.

Inicialmente, a distância é determinada apenas entre clusters de um único elemento, mas é necessário determinar as distâncias entre clusters contendo mais de um elemento. Isto pode ser feito de diversas maneiras, e dependendo do método escolhido, obtemos algoritmos de análise de cluster com propriedades diferentes. Você pode, por exemplo, colocar a distância entre o cluster i + j e algum outro cluster k igual à média aritmética das distâncias entre os clusters i e k e os clusters j e k:

di+j,k = ½ (dik + djk).

Mas também podemos definir di+j,k como o mínimo destas duas distâncias:

di+j,k = min (di k + dj k).

Assim, é descrita a primeira etapa do algoritmo hierárquico aglomerativo. As etapas subsequentes são semelhantes.

Uma classe bastante ampla de algoritmos pode ser obtida se a seguinte fórmula geral for usada para recalcular distâncias:

di+j,k = A(w) min(dik djk) + B(w) max(dik djk), onde

UMA(w) = se dik £ djk

A(w) = se dik > djk

B(w) = se dik £ djk

B(w) = se dik > djk

onde ni e nj são o número de elementos nos clusters i e j, e w é um parâmetro livre, cuja escolha é determinada por um algoritmo específico. Por exemplo, quando w = 1 obtemos o chamado algoritmo de “conexão média”, para o qual a fórmula para recalcular distâncias assume a forma:

di+j,k =

Nesse caso, a distância entre dois clusters em cada etapa do algoritmo acaba sendo igual à média aritmética das distâncias entre todos os pares de elementos em que um elemento do par pertence a um cluster e o outro a outro.

O significado visual do parâmetro w fica claro se colocarmos w®¥. A fórmula para recalcular distâncias assume a forma:

di+j,k = min (di,k djk)

Este será o chamado algoritmo do “vizinho mais próximo”, que permite identificar clusters de qualquer formato complexo, desde que as diferentes partes de tais clusters estejam conectadas por cadeias de elementos próximos uns dos outros. Neste caso, a distância entre dois clusters em cada etapa do algoritmo acaba sendo igual à distância entre os dois elementos mais próximos pertencentes a esses dois clusters.

Muitas vezes assume-se que as distâncias iniciais (diferenças) entre os elementos que estão sendo agrupados são dadas. Em alguns problemas isso é realmente verdade. Porém, apenas os objetos e suas características são especificados, e uma matriz de distância é construída com base nesses dados. Dependendo se as distâncias entre objetos ou entre as características dos objetos são calculadas, diferentes métodos são usados.

No caso da análise de agrupamento de objetos, a medida de diferença mais comum é o quadrado da distância euclidiana

(onde xih, xjh são os valores do h-ésimo recurso para os i-ésimo e j-ésimo objetos, e m é o número de características), ou a própria distância euclidiana. Se os recursos receberem pesos diferentes, esses pesos poderão ser levados em consideração ao calcular a distância

Às vezes, a distância é usada como medida de diferença, calculada pela fórmula:

que são chamados: distância "Hamming", "Manhattan" ou "quarteirão".

Uma medida natural da semelhança das características dos objetos em muitas tarefas é o coeficiente de correlação entre eles

onde mi, mj, di, dj são a média e os desvios padrão das características i e j, respectivamente. Uma medida da diferença entre as características pode ser o valor 1 - r. Em alguns problemas, o sinal do coeficiente de correlação é insignificante e depende apenas da escolha da unidade de medida. Neste caso, ô1 - ri j ô é utilizado como medida da diferença entre as características

1.5 Número de clusters.

Uma questão muito importante é o problema de escolher o número necessário de clusters. Às vezes você pode escolher m número de clusters a priori. Porém, no caso geral, esse número é determinado no processo de divisão do conjunto em clusters.

A pesquisa de Fortier e Solomon foi conduzida e foi determinado que o número de clusters deve ser adotado para atingir a probabilidade de que a melhor partição seja encontrada. Assim, o número ideal de partições é uma função de uma dada fração b das melhores ou, em certo sentido, partições admissíveis no conjunto de todas as partições possíveis. Quanto maior a proporção b de partições admissíveis, maior será o espalhamento total. Fortier e Solomon desenvolveram uma tabela que pode ser usada para encontrar o número de divisões necessárias. S(a,b) dependendo de aeb (onde a é a probabilidade de que a melhor partição seja encontrada, b é a proporção das melhores partições no número total de partições). Além disso, a medida de heterogeneidade não é a medida de dispersão, mas a medida de adesão introduzida por Holzenger e Harman. A tabela de valores S(a,b) é fornecida abaixo.

Tabela de valores S(a,b)

BA	0.20	0.10	0.05	0.01	0.001	0.0001
0.20	8	11	14	21	31	42
0.10	16	22	29	44	66	88
0.05	32	45	59	90	135	180
0.01	161	230	299	459	689	918
0.001	1626	2326	3026	4652	6977	9303
0.0001	17475	25000	32526	55000	75000	100000

Muitas vezes, o critério de combinação (o número de clusters) é uma mudança na função correspondente. Por exemplo, a soma dos desvios quadrados:

O processo de agrupamento deve corresponder aqui a um aumento mínimo consistente no valor do critério E. A presença de um salto acentuado no valor de E pode ser interpretada como uma característica do número de clusters que existem objetivamente na população em estudo.

Portanto, a segunda maneira de determinar o melhor número de clusters se resume a identificar saltos determinados pela transição de fase de um estado de objetos fortemente ligado para um estado de ligação fraca.

1.6 Dendogramas.

O método mais conhecido para representar uma matriz de distância ou similaridade é baseado na ideia de um dendograma ou diagrama de árvore. Um dendograma pode ser definido como uma representação gráfica dos resultados de um processo de agrupamento sequencial, que é realizado em termos de uma matriz de distância. Usando um dendograma, você pode representar gráfica ou geometricamente um procedimento de agrupamento, desde que este procedimento opere apenas em elementos da matriz de distância ou similaridade.

Existem muitas maneiras de construir dendogramas. No dendograma, os objetos estão localizados verticalmente à esquerda, e os resultados do agrupamento estão localizados à direita. Os valores de distância ou similaridade correspondentes à estrutura dos novos clusters são representados ao longo de uma linha horizontal no topo dos dendogramas.

A Figura 1 mostra um exemplo de dendograma. A Figura 1 corresponde ao caso de seis objetos (n=6) e k características (features). Os objetos A e C são os mais próximos e, portanto, são combinados em um cluster com um nível de proximidade de 0,9. Os objetos D e E são combinados no nível 0.8. Agora temos 4 clusters:

O tipo de dendograma depende da escolha da medida de similaridade ou distância entre um objeto e um cluster e do método de agrupamento. O ponto mais importante é a escolha da medida de similaridade ou medida de distância entre o objeto e o cluster.

O número de algoritmos de análise de cluster é muito grande. Todos eles podem ser divididos em hierárquicos e não hierárquicos.

Algoritmos hierárquicos estão associados à construção de dendogramas e são divididos em:

a) aglomerativo, caracterizado pela combinação sequencial de elementos iniciais e correspondente diminuição no número de clusters;

b) divisível (divisível), em que o número de clusters aumenta, a partir de um, resultando na formação de uma sequência de grupos de divisão.

Os algoritmos de análise de cluster hoje possuem uma boa implementação de software, o que permite resolver problemas da maior dimensão.

1.7 Dados

A análise de cluster pode ser aplicada a dados de intervalo, frequências e dados binários. É importante que as variáveis variem em escalas comparáveis.

A heterogeneidade das unidades de medida e a consequente impossibilidade de expressar validamente os valores dos vários indicadores na mesma escala levam ao facto de as distâncias entre os pontos que reflectem a posição dos objectos no espaço das suas propriedades acabarem por depender de um escala escolhida arbitrariamente. Para eliminar a heterogeneidade na medição dos dados iniciais, todos os seus valores são pré-normalizados, ou seja, são expressos através da razão desses valores para um determinado valor que reflete certas propriedades de um determinado indicador. A normalização dos dados iniciais para análise de cluster às vezes é realizada dividindo os valores iniciais pelo desvio padrão dos indicadores correspondentes. Outra forma é calcular a chamada contribuição padronizada. Também é chamada de contribuição Z.

A contribuição Z mostra quantos desvios padrão separam uma determinada observação da média:

Onde xi é o valor desta observação, é a média, S é o desvio padrão.

A média das contribuições Z é zero e o desvio padrão é 1.

A padronização permite que observações de diferentes distribuições sejam comparadas. Se a distribuição de uma variável for normal (ou próxima do normal) e a média e a variância forem conhecidas ou estimadas a partir de amostras grandes, então a contribuição Z para uma observação fornece informações mais específicas sobre a sua localização.

Observe que os métodos de padronização significam o reconhecimento de todas as características como equivalentes em termos de determinação da semelhança dos objetos em consideração. Já foi referido que, em relação à economia, o reconhecimento da equivalência de vários indicadores nem sempre parece justificado. Seria desejável, juntamente com a padronização, atribuir a cada um dos indicadores um peso que refletisse a sua importância no estabelecimento das semelhanças e diferenças dos objetos.

Nesta situação, é necessário recorrer a um método de determinação dos pesos dos indicadores individuais - um inquérito a especialistas. Por exemplo, ao resolver o problema de classificação dos países por nível de desenvolvimento econômico, os resultados de uma pesquisa com 40 importantes especialistas de Moscou sobre os problemas dos países desenvolvidos foram usados em uma escala de dez pontos:

indicadores generalizados de desenvolvimento socioeconómico – 9 pontos;

indicadores de distribuição setorial da população empregada – 7 pontos;

indicadores de prevalência de mão de obra contratada – 6 pontos;

indicadores que caracterizam o elemento humano das forças produtivas – 6 pontos;

indicadores de desenvolvimento das forças produtivas materiais – 8 pontos;

indicador de despesas governamentais – 4 pontos;

Indicadores “económicos-militares” – 3 pontos;

indicadores sociodemográficos – 4 pontos.

As avaliações dos especialistas foram relativamente estáveis.

As avaliações de especialistas fornecem uma certa base para determinar a importância dos indicadores incluídos num determinado grupo de indicadores. A multiplicação dos valores normalizados dos indicadores pelo coeficiente correspondente à pontuação média da avaliação permite calcular as distâncias entre os pontos que refletem a posição dos países no espaço multidimensional, tendo em conta o peso desigual das suas características.

Muitas vezes, na resolução de tais problemas, utilizam-se não um, mas dois cálculos: o primeiro, em que todas as características são consideradas equivalentes, o segundo, onde são atribuídos pesos diferentes de acordo com os valores médios das avaliações periciais.

1.8. Aplicação de análise de cluster.

Vejamos algumas aplicações de análise de cluster.

Divisão dos países em grupos por nível de desenvolvimento.

Foram estudados 65 países de acordo com 31 indicadores (rendimento nacional per capita, percentagem da população empregada na indústria, poupança per capita, percentagem da população empregada na agricultura, esperança média de vida, número de automóveis por 1 mil habitantes, número de forças armadas por 1 milhão de habitantes, a participação do PIB da indústria em%, a participação do PIB da agricultura em%, etc.)

Cada país atua nesta consideração como um objeto caracterizado por determinados valores de 31 indicadores. Conseqüentemente, eles podem ser representados como pontos no espaço tridimensional. Tal espaço é geralmente chamado de espaço de propriedades dos objetos em estudo. A comparação da distância entre estes pontos refletirá o grau de proximidade dos países em questão, a sua semelhança entre si. O significado socioeconómico desta compreensão de similaridade significa que os países são considerados quanto mais semelhantes, menores são as diferenças entre os mesmos indicadores com os quais são descritos.

O primeiro passo dessa análise é identificar um par de economias nacionais consideradas na matriz de similaridade, cuja distância entre elas seja a menor. Estas serão obviamente as economias mais semelhantes e semelhantes. Na discussão que se segue, ambos os países são considerados um único grupo, um único cluster. Assim, a matriz original é transformada de modo que seus elementos se tornem as distâncias entre todos os pares possíveis não de 65, mas de 64 objetos - 63 economias e um cluster recém-transformado - uma união condicional dos dois países mais semelhantes. Da matriz de similaridade original são retiradas linhas e colunas correspondentes às distâncias do par de países incluídos na fusão a todos os demais, mas são adicionadas uma linha e uma coluna contendo a distância entre o cluster obtido durante a fusão e os demais países.

Assume-se que a distância entre o cluster recém-obtido e os países é igual à média das distâncias entre estes e os dois países que compõem o novo cluster. Ou seja, o grupo combinado de países é considerado como um todo com características aproximadamente iguais à média das características dos países nele incluídos.

O segundo passo da análise é considerar a matriz assim transformada com 64 linhas e colunas. Novamente, identifica-se um par de economias cuja distância é a menos significativa, e elas, tal como no primeiro caso, são reunidas. Neste caso, a menor distância pode ser entre um par de países, ou entre qualquer país e a associação de países obtida na fase anterior.

Outros procedimentos são semelhantes aos descritos acima: em cada etapa, a matriz é transformada de forma que duas colunas e duas linhas contendo a distância aos objetos (pares de países ou associações - clusters) reunidos na etapa anterior sejam excluídas dela ; as linhas e colunas excluídas são substituídas por uma coluna e linha contendo as distâncias das novas junções aos objetos restantes; então o par de objetos mais próximos é identificado na matriz modificada. A análise continua até que a matriz esteja completamente esgotada (ou seja, até que todos os países sejam combinados em um todo). Os resultados generalizados da análise matricial podem ser apresentados na forma de uma árvore de similaridade (dendograma), semelhante à descrita acima, com a única diferença de que a árvore de similaridade, que reflete a proximidade relativa de todos os 65 países que estamos considerando, é muito mais complexo do que o diagrama em que aparecem apenas cinco economias nacionais. Esta árvore, de acordo com o número de objetos comparados, inclui 65 níveis. O primeiro nível (inferior) contém pontos correspondentes a cada país separadamente. A ligação destes dois pontos no segundo nível mostra um par de países que estão mais próximos em termos do tipo geral de economia nacional. No terceiro nível, é anotado o próximo rácio semelhante de países entre pares (como já mencionado, este rácio pode conter um novo par de países ou um novo país e um par já identificado de países semelhantes). E assim sucessivamente até o último nível, no qual todos os países estudados atuam como um conjunto único.

Como resultado da aplicação da análise de cluster, foram obtidos os seguintes cinco grupos de países:

Grupo afro-asiático;

grupo latino-asiático;

grupo latino-mediterrâneo;

grupo de países capitalistas desenvolvidos (excluindo EUA)

A introdução de novos indicadores para além dos 31 indicadores aqui utilizados, ou a substituição dos mesmos por outros, conduz naturalmente a alterações nos resultados da classificação dos países.

2. Divisão dos países segundo o critério de semelhança de cultura.

Como você sabe, o marketing deve levar em consideração a cultura dos países (costumes, tradições, etc.).

Através do agrupamento, foram obtidos os seguintes grupos de países:

Árabe;

Oriente médio;

Escandinavo;

Falante de alemão;

Falante de inglês;

Românico Europeu;

Latino Americano;

Do Extremo Oriente.

3. Desenvolvimento de uma previsão das condições do mercado de zinco.

A análise de cluster desempenha um papel importante na fase de redução do modelo económico e matemático do mercado de commodities, ajudando a facilitar e simplificar os procedimentos computacionais, garantindo maior compacidade dos resultados obtidos, mantendo a precisão necessária. A utilização da análise de cluster permite dividir todo o conjunto inicial de indicadores de mercado em grupos (clusters) de acordo com critérios adequados, facilitando assim a seleção dos indicadores mais representativos.

A análise de cluster é amplamente utilizada para modelar as condições de mercado. Na prática, a maioria dos problemas de previsão depende do uso de análise de cluster.

Por exemplo, a tarefa de desenvolver uma previsão para o mercado de zinco.

Inicialmente, foram selecionados 30 indicadores-chave do mercado global de zinco:

X1 - tempo

Números de produção:

X2 - no mundo

X4 - Europa

X5 - Canadá

X6 - Japão

X7 - Austrália

Indicadores de consumo:

X8 - no mundo

X10 - Europa

X11 - Canadá

X12 - Japão

X13 - Austrália

Reservas de zinco dos fabricantes:

X14 - no mundo

X16 - Europa

X17 - outros países

Reservas de zinco dos consumidores:

X18 - nos EUA

X19 - na Inglaterra

X10 - no Japão

Importação de minérios e concentrados de zinco (mil toneladas)

X21 - nos EUA

X22 - no Japão

X23 - na Alemanha

Exportação de minérios e concentrados de zinco (mil toneladas)

X24 - do Canadá

X25 - da Austrália

Importação de zinco (mil toneladas)

X26 - nos EUA

X27 - para a Inglaterra

X28 - na Alemanha

Exportações de zinco (mil toneladas)

X29 - do Canadá

X30 - da Austrália

Para determinar dependências específicas, foi utilizado o aparato de análise de correlação e regressão. A análise das relações foi realizada com base em uma matriz de coeficientes de correlação pareados. Aqui foi aceita a hipótese sobre a distribuição normal dos indicadores de mercado analisados. É claro que os rij não são o único indicador possível da relação entre os indicadores utilizados. A necessidade de utilizar a análise de cluster nesta tarefa se deve ao fato de que o número de indicadores que afetam o preço do zinco é muito grande. É necessário reduzi-los por uma série de razões:

a) falta de dados estatísticos completos sobre todas as variáveis;

b) uma acentuada complicação dos procedimentos computacionais quando um grande número de variáveis é introduzido no modelo;

c) o uso ideal de métodos de análise de regressão requer que o número de valores observados exceda o número de variáveis em pelo menos 6 a 8 vezes;

d) o desejo de utilizar variáveis estatisticamente independentes no modelo, etc.

É muito difícil realizar tal análise diretamente sobre uma matriz relativamente complicada de coeficientes de correlação. Usando a análise de cluster, todo o conjunto de variáveis de mercado pode ser dividido em grupos de tal forma que os elementos de cada cluster estejam fortemente correlacionados entre si, e os representantes de diferentes grupos sejam caracterizados por uma correlação fraca.

Para resolver este problema, foi utilizado um dos algoritmos de análise de cluster hierárquica aglomerativa. A cada passo, o número de clusters é reduzido em um devido à combinação ideal, em certo sentido, de dois grupos. O critério para fusão é uma mudança na função correspondente. Como tal função, utilizamos os valores das somas dos desvios quadrados calculados pelas seguintes fórmulas:

(j = 1, 2,…,m),

onde j é o número do cluster, n é o número de elementos no cluster.

rij - coeficiente de correlação de pares.

Assim, o processo de agrupamento deve corresponder a um aumento mínimo sequencial no valor do critério E.

Na primeira etapa, o array de dados inicial é apresentado como um conjunto composto por clusters, cada um incluindo um elemento. O processo de agrupamento começa com a combinação de tal par de clusters, o que leva a um aumento mínimo na soma dos desvios quadrados. Isso requer estimar a soma dos valores dos desvios quadrados para cada uma das possíveis combinações de cluster. Na próxima etapa, os valores das somas dos desvios quadrados são considerados para clusters, etc. Este processo será interrompido em alguma etapa. Para fazer isso, você precisa monitorar o valor da soma dos desvios quadrados. Considerando uma sequência de valores crescentes, percebe-se um salto (um ou vários) em sua dinâmica, o que pode ser interpretado como uma característica do número de grupos “objetivamente” existentes na população em estudo. No exemplo dado, os saltos ocorreram quando o número de clusters era 7 e 5. O número de grupos não deve ser reduzido ainda mais, porque isso leva a uma diminuição na qualidade do modelo. Após a obtenção dos clusters, são selecionadas as variáveis mais importantes do ponto de vista económico e mais relacionadas com o critério selecionado da situação do mercado - neste caso, com cotações de zinco da London Metal Exchange. Esta abordagem permite-nos preservar uma parte significativa da informação contida no conjunto original de indicadores de mercado iniciais.

O termo “análise de cluster” foi usado pela primeira vez pelo psicólogo americano Robert Tryon em seu trabalho homônimo em 1930. Apesar disso, os termos “cluster” e “análise de cluster” são percebidos pelos falantes nativos como novos, conforme observado por Alexander Khrolenko, que conduziu uma análise de corpus do uso do lexema “cluster”: “a maioria dos autores que usam este termo prestam atenção à sua novidade” (Khrolenko, 2016, p. 106)

A análise de cluster inclui muitos algoritmos de classificação diferentes, cujo objetivo é organizar as informações em clusters. É importante lembrar que a análise de cluster não é um algoritmo específico em si, mas sim um problema que precisa ser resolvido. Em seu trabalho “A Escassez da Hierarquia Linear”, Mark Ereshefsky observa que a análise de cluster é um dos três tipos de classificação de objetos no mundo circundante, juntamente com o essencialismo e a classificação histórica.

Em linguística, o princípio de descrição do cluster implica, além da análise das unidades incluídas neste cluster, também a análise das relações dentro delas. Podem ser conexões em diferentes níveis: desde conexões lógicas (paradigmáticas e sintagmáticas, por exemplo) até conexões formativas de palavras e fonéticas.

F. Brown identifica as seguintes etapas da análise de cluster (Brown):

1. Selecionar uma medida e produzir as medidas, critérios ou entidades necessárias a serem classificadas
2. Definindo a medida de similaridade
3. Formulação de regras para determinar a ordem de formação do cluster
4. Aplicando regras para formar clusters

Deve-se notar que o terceiro ponto levanta questões, uma vez que a característica distintiva do agrupamento como método de classificação é a ausência de classes específicas. O agrupamento de documentos é uma tarefa de recuperação de informações. Ao contrário da categorização de texto, não envolve categorias predefinidas ou um conjunto de treinamento. Os clusters e as relações entre eles são “extraídos automaticamente dos documentos, e os documentos são atribuídos sequencialmente a esses clusters” (Golub, pp. 52-53). Mark Ereshefsky apresenta a análise de cluster como um método de classificação. Ele acredita que “todas as formas de análise de agrupamento são baseadas em duas suposições: os membros de um grupo taxonômico devem ter um agrupamento de características em comum, e essas características não podem aparecer em todos ou em apenas um membro desse grupo”. (Ereshefsky, p. 15)

Em seu trabalho “Abordagem de cluster em análise linguística” (Nurgalieva, 2013) N.Kh. Nurgalieva identifica quatro tarefas principais de análise de cluster:

1. Desenvolvimento de uma tipologia ou classificação
2. Explorando esquemas conceituais úteis para agrupar objetos
3. Apresentação de hipóteses baseadas nos dados estudados
4. Testar hipóteses ou estudos para determinar se os tipos (grupos) identificados de uma forma ou de outra estão realmente presentes nos dados disponíveis

Todos os métodos de análise de cluster podem ser divididos em análise de cluster “hard” e clara, quando cada objeto pertence a um cluster ou não, e em análise de cluster “suave” e fuzzy, quando cada objeto pertence a algum grupo com um certo grau de probabilidade.

Os métodos de análise de cluster também são divididos em hierárquicos e não hierárquicos. Os métodos hierárquicos implicam a presença de grupos aninhados, ao contrário dos métodos não hierárquicos. Nurgalieva observa que o método hierárquico “parece ser o mais adequado para resolver problemas linguísticos” (Nurgalieva, p. 1), pois permite ver e analisar a estrutura do fenômeno em estudo.

Portal para escolares. Autopreparação

Enviar seu bom trabalho na base de conhecimento é simples. Use o formulário abaixo

Documentos semelhantes

ARTIGOS RELACIONADOS