Fornece uma introdução oportuna e importante à análise de cluster fuzzy, seus métodos e usos. Descreve sistematicamente diversas técnicas de agrupamento difuso para que o leitor possa escolher o método mais adequado para resolver seu problema. Há uma revisão de literatura boa e muito abrangente sobre o assunto, reconhecimento de imagens, classificação de cobertura, análise de dados e derivação de regras. Os exemplos são suficientemente ilustrativos e eficazes. os resultados foram testados.
Este é o livro mais detalhado sobre agrupamento difuso, por isso é recomendado para cientistas da computação, matemáticos, engenheiros - qualquer pessoa envolvida em análise de dados e processamento de imagens. Também será útil para estudantes que trabalham na área de ciências da computação.

Tag ,

O trabalho é dedicado a um dos métodos da teoria do reconhecimento de padrões – análise de cluster.

As principais ideias da análise de cluster são apresentadas de forma concisa e algumas áreas de sua aplicação na pesquisa em mineração são mostradas. Os métodos de agrupamento descritos podem ser usados ​​em problemas reais. Nos algoritmos, a parte computacional é considerada com detalhes suficientes.

Apesar de a análise de cluster ser uma ferramenta de classificação eficaz e conveniente, e também muito comum na pesquisa prática, existem muito poucas publicações sobre este tema em russo e as existentes são pouco informativas. Esta brochura destaca algumas das questões fundamentais da análise de cluster.

Para pesquisadores, dissertações e especialistas que atuam na área de análise estatística multivariada.

Tag ,

O tema do livro é uma revisão do estado da teoria e da prática da aplicação da "análise de cluster". Este método apresenta todas as vantagens do método de agrupamento combinacional, e não está isento de sua principal desvantagem - a dispersão de materiais, o que abre amplas perspectivas para a aplicação do método em questão na análise estatística, na classificação de objetos, no estudo de relacionamentos, tipificação de amostra, etc. O livro se distingue pela completude, acessibilidade e, juntamente com a brevidade da apresentação. O livro é destinado a estatísticos, economistas, bem como sociólogos, demógrafos, biólogos e outros especialistas. Reproduzido na grafia original do autor da edição de 1977 (editora Statistica).

Tag ,

Os temas de investigação vão desde a análise da morfologia dos roedores mumificados na Nova Guiné ao estudo dos resultados da votação dos senadores norte-americanos, da análise das funções comportamentais das baratas congeladas quando são descongeladas, ao estudo da distribuição geográfica. de certos tipos de líquen em Saskatchewan.

Esta explosão de publicações teve um enorme impacto no desenvolvimento e aplicação da análise de cluster. Mas, infelizmente, também existem lados negativos. O rápido crescimento das publicações sobre análise de cluster levou à formação de agrupamentos de usuários e, como consequência, à criação de jargões utilizados apenas pelos agrupamentos que os criaram (Blashfield e Aldenderfer, 1978; Blashfield, 1980).

A formação do jargão pelos cientistas sociais é evidenciada, por exemplo, por uma variedade de terminologias relacionadas ao método de Ward. O "método Ward" é denominado de forma diferente na literatura. Pelo menos mais quatro de seus nomes são conhecidos: "método de variância mínima", "método de soma de erro quadrático", "minimização de agrupamento hierárquico" e "HGROUP". Os dois primeiros nomes referem-se simplesmente ao critério cujo ótimo é determinado pelo método de Ward, enquanto o terceiro está relacionado à soma dos erros quadráticos, que é uma transformação monotônica do traço da matriz W, a matriz de covariância intragrupo. Finalmente, o nome comumente usado "HGROUP" é o nome de um programa de computador popular que implementa o método de Ward (Veldman, 1967).

A formação de jargões dificulta o desenvolvimento de conexões interdisciplinares, impede a comparação efetiva da metodologia e dos resultados da aplicação da análise de cluster em diferentes áreas da ciência, leva a esforços desnecessários (reinvenção dos mesmos algoritmos) e, por fim, não dá novos aos usuários uma compreensão profunda dos métodos que escolheram (Blashfield e Aldenderfer, 1978). Por exemplo, um estudo de ciências sociais (Rogers e Linden, 1973) comparou três métodos diferentes de agrupamento utilizando os mesmos dados. Eles chamaram esses métodos da seguinte forma: “agrupamento hierárquico”, “agrupamento hierárquico ou HCG” e “análise de cluster”. E nenhum desses nomes era familiar aos métodos de agrupamento. Um usuário iniciante de programas de análise de cluster ficará confuso com todos os nomes existentes e não será capaz de associá-los a outras descrições de métodos de agrupamento. Usuários experientes se encontrarão em uma posição difícil ao comparar suas pesquisas com trabalhos semelhantes. Podemos estar indo a extremos, mas o jargão é um problema sério.

Nos últimos anos, o desenvolvimento da análise de cluster abrandou um pouco, a julgar pelo número de publicações e pelo número de disciplinas onde este método é aplicado. Pode-se dizer que atualmente a psicologia, a sociologia, a biologia, a estatística e algumas disciplinas técnicas estão entrando na fase de consolidação em relação à análise de cluster.

O número de artigos que elogiam as virtudes da análise de cluster está diminuindo gradativamente. Ao mesmo tempo, há cada vez mais trabalhos nos quais a aplicabilidade de vários métodos de agrupamento é comparada nos dados de controle. Na literatura, mais atenção tem sido dada às aplicações. Muitos estudos visam desenvolver medidas práticas para testar a validade dos resultados obtidos por meio da análise de cluster. Tudo isso atesta tentativas sérias de criar uma teoria estatística razoável de métodos de agrupamento.

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.2 Distância entre objetos (métrica)

2.3Densidade 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

"A análise de cluster é um conjunto de métodos matemáticos projetados para formar grupos relativamente "remotos" uns dos outros de objetos "próximos" de acordo com informações sobre distâncias ou conexões (medidas de proximidade) entre eles. É semelhante em significado aos termos: automático classificação, 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. Várias 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 construir e testar hipóteses e teorias científicas. Assim, no meu trabalho, considero necessário considerar as questões da análise de cluster (a base da análise de cluster), bem como considerar a sua terminologia e dar alguns exemplos de utilização deste método tendo o processamento de dados como objetivo principal.

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 nas mais diversas áreas científicas: química, biologia, medicina, arqueologia, história, geografia, economia, filologia, etc. O livro de VV 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 durante as últimas três décadas, embora os primeiros trabalhos que mencionassem métodos de cluster tenham surgido há bastante tempo. O antropólogo polonês K. Chekanowski apresentou a ideia de “classificação estrutural”, que continha a ideia principal da análise de cluster - a alocação de grupos compactos de objetos.

Em 1925, o hidrobiólogo soviético P.V. Terentyev desenvolveu o chamado "método de correlação das Plêiades", 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 originalmente chamada de “análise de cluster”. No início da década de 1950, publicações de R. Lewis, E. Fix e J. Hodges apareceram sobre algoritmos hierárquicos de análise de cluster. Um impulso notável para o desenvolvimento do trabalho sobre análise de cluster foi dado pelo trabalho de R. Rosenblatt sobre o 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 caracterizem 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, na opinião dos autores, pode esclarecer se estes grupos correspondem a espécies biológicas diferentes. Assim, Sokal e Sneath assumiram que revelar a estrutura de distribuição dos objetos em grupos ajuda a estabelecer o processo de formação dessas estruturas. E a diferença e semelhança de organismos de diferentes aglomerados (grupos) podem servir de base para a compreensão do processo evolutivo em curso e a elucidação do seu mecanismo.

Nos 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 - sobre métodos hierárquicos. Uma contribuição significativa para o desenvolvimento de métodos de análise de cluster foi feita por cientistas nacionais - E.M. Braverman, A.A. Dorofeyuk, I.B. Muchnik, L.A. Rastrigin, Yu.I. Em particular, nos anos 60-70. Numerosos algoritmos desenvolvidos pelos matemáticos de Novosibirsk N.G. Zagoruiko, V.N. Elkina e G.S. Lbov gozaram de grande popularidade. São algoritmos conhecidos como FOREL, BIGFOR, KRAB, NTTP, DRET, TRF, etc. Com base nesses pacotes, foi criado um pacote de software OTEX especializado. 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.

Até certo ponto, 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, COPRA-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 que usam 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 são as razões de um interesse tão tempestuoso por este 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 inviável. A segunda razão é que a ciência moderna se baseia cada vez mais na classificação nas suas construções. Além disso, este processo está cada vez mais aprofundado, 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 - o aprofundamento de conhecimentos especiais conduz inevitavelmente a um aumento do número de variáveis ​​​​tidas em consideração na análise de determinados objetos e fenómenos. Como resultado, a classificação subjectiva, 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 agrupamento ainda não se tornou um método de pesquisa bastante popular e difundido.

2 TERMINOLOGIA

2. 1 OBJETO E SINAL

Vamos primeiro introduzir conceitos como objeto e signo. 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 disponíveis para o pesquisador estudar é chamado de amostra ou conjunto de amostras. 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".

Sinal (sinônimos - propriedade, variável, característica; inglês - variável - variável.) - é uma propriedade específica do 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 essas características numéricas contínuas (escalas), vários recursos 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 de variáveis ​​ordinais (escalas). Tais signos são caracterizados pela propriedade de ordenar essas grandezas. Estes incluem os estágios de uma doença específica, faixas etárias, pontuações de conhecimento dos alunos, a escala de magnitude do terremoto Richter de 12 pontos, etc.

2) O segundo grupo de características discretas não possui tal ordem e é denominado características nominais (da palavra "nominal" - amostra) ou características de classificação. Um exemplo de tais sinais pode 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 nomes.

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

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

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 (não negatividade da distância)

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 (distinguibilidade de objetos não idênticos)

5. Se d ij = 0, então i = j (indistinguibilidade 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 maneiras diferentes de calcular a distância entre objetos. Além do termo “distância”, outro termo é frequentemente encontrado na literatura - “métrica”, 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 objetos;

· 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 dois sinais quantitativos, a distância d ij será igual ao comprimento da hipotenusa de um triângulo retângulo, que liga dois pontos em um 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 peso 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, i e j, respectivamente, podem assumir valores de 1 a 5. Também é óbvio que o número de todas as distâncias pares possíveis será 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 da propriedade de simetria que d ij = d ji para qualquer i e j. Aqueles. a distância entre os objetos #1 e #2 é igual à distância entre os objetos #2 e #1.

A expressão para a distância euclidiana é muito semelhante à chamada distância de potência generalizada de Minkowski, na qual outro valor é usado em vez de dois em potências. No caso geral, este valor é indicado pelo símbolo “p”.

Para 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 “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 módulos das diferenças das características correspondentes dos objetos. Deixando p tender ao infinito, obtemos a métrica de "dominância", ou Sup-métrica:

que também pode ser representado como 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, 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 vetores de coluna de valores variáveis ​​​​para os i-ésimos e j-ésimos 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 a matriz comum de variância-covariância intragrupo é indicada. Um símbolo -1 acima S significa que você precisa 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 incompatibilidades nos valores dos recursos correspondentes para os i-ésimos e j-ésimos objetos considerados.

2. 3 DENSIDADE E LOCALIDADE DOS CLUSTERS

O principal objetivo da análise de cluster é encontrar grupos de objetos semelhantes entre si na 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 de um cluster. Esta propriedade nos permite definir um cluster como um cluster de pontos em um espaço multidimensional que é relativamente denso em comparação com outras regiões deste espaço que não contêm nenhum ponto ou contêm um pequeno número de observações. Em outras palavras, quão compacto é esse cluster, ou vice-versa, 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 compacidade, a 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 as observações estiverem do centro do aglomerado, maior será a densidade do aglomerado. E vice-versa, quanto maior a dispersão da distância, mais esparso é esse aglomerado e, conseqüentemente, existem pontos localizados tanto próximos ao centro do aglomerado quanto bastante distantes do centro do aglomerado.

A próxima propriedade dos clusters é o seu tamanho. O principal indicador do tamanho de um cluster é o seu “raio”. Esta propriedade reflete mais completamente o tamanho real do cluster se o cluster considerado for redondo 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, separabilidade. Caracteriza o grau de sobreposição e afastamento mútuo dos clusters entre si em um espaço multidimensional. Por exemplo, considere a distribuição de 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 características das propriedades reflexivas de diferentes formas de eritrócitos, estudadas por microscopia eletrônica.

Imagem 1

Vemos que o cluster 1 tem o tamanho mínimo, enquanto 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 seções suficientemente grandes de espaço vazio do cluster 2 e do cluster 3. Enquanto os clusters 2 e 3 se sobrepõem parcialmente. É interessante o fato de que o cluster 1 tem 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. É óbvio que para tal análise visual é necessário ter todas as observações da amostra projetadas 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 objetos originais de pesquisa, 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 algoritmo ou outro 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, a variedade de possibilidades é ainda maior 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 uma certa quantidade de espaço multidimensional e consistem em muitos pontos. Na análise de cluster, as distâncias entre clusters são amplamente utilizadas, calculadas com base no princípio do vizinho mais próximo (vizinho mais próximo), centro de gravidade, vizinho mais distante (vizinho mais distante), medianas. Quatro métodos são mais amplamente utilizados: ligação única, ligação completa, ligação média e método de Ward. No método de link único, um objeto será anexado a um cluster já existente se pelo menos um dos elementos do cluster tiver o mesmo nível de similaridade que o objeto que está sendo unido. Para o método de links completos, um objeto é anexado a um cluster somente se a similaridade entre o candidato à inclusão e qualquer um dos elementos do cluster não for inferior a um determinado limite. Para o método de conexão média, existem diversas modificações, que são algum compromisso entre conexão única e completa. Eles calculam o valor médio da similaridade do candidato à inclusão com todos os objetos do cluster existente. A anexaçã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 de 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 particionamento em cada etapa. O popular método Ward é construído de forma a otimizar a variância mínima das distâncias intracluster. Na primeira etapa, cada cluster consiste em um objeto, devido ao qual a dispersão intracluster das distâncias é igual a 0. Por este método, são combinados aqueles objetos que dão o incremento mínimo de dispersão, como resultado este método tende a gerar clusters hiperesféricos.

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

Os mais amplamente utilizados 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, consistindo em apenas um elemento. Sem o uso de tecnologia computacional poderosa, a implementação da análise de dados de cluster é muito problemática.

A escolha da métrica é feita pelo pesquisador. Após calcular a matriz de distância, o processo começa aglomerações (do latim agglomero – anexo, acumulo), passando sequencialmente passo a passo. Na primeira etapa deste processo, duas observações iniciais (monoclusters) com a menor distância entre elas são combinadas em um cluster, que já consiste em dois objetos (observações). Assim, em vez dos antigos N ​​monoclusters (clusters constituídos por 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, vários métodos de combinação de clusters N-2 são possíveis. Isso ocorre porque um desses clusters já contém dois objetos. Por esse motivo, surgem duas questões principais:

· como calcular as coordenadas de tal agrupamento de dois (e ainda mais de dois) objetos;

· como calcular a distância para tais clusters de "poliobjetos" a partir de "monoclusters" e entre clusters de "poliobjetos".

Em última análise, estas questões determinam a estrutura final dos clusters resultantes (a estrutura dos clusters significa a composição dos clusters individuais e a sua posição relativa num 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 escolhidos para calcular as coordenadas de um cluster composto por vários objetos e do método para calcular as distâncias entre clusters, é possível recombinar 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 de métodos hierárquicos aglomerativos ao final do trabalho pode fornecer dois gráficos principais para visualizaçã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 em duas variáveis.

Agendar1

O eixo vertical de tal gráfico é o eixo da distância entre clusters, e os números de objetos - casos usados ​​na análise - são marcados ao longo do eixo horizontal. Pode-se observar neste dendograma que os objetos nº 1 e nº 2 são primeiro combinados em um cluster, pois a distância entre eles é a menor e é igual a 1. Essa fusão é exibida no gráfico por uma linha horizontal conectando os segmentos verticais saindo 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. Além disso, na segunda etapa, o objeto nº 3, designado como C_3, se junta a este cluster, que já inclui dois objetos. O próximo passo é mesclar os objetos nº 4 e nº 5, cuja distância entre eles é igual a 1,41. E na última etapa, o cluster de objetos 1, 2 e 3 é combinado 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) é maior que 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 é 1,41.

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

Gráfico 2

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

Gráfico 3 Parte ampliada do gráfico nº 2 acima

Pode-se observar que o objeto 44 é um monocluster que se combina com o cluster direito na penúltima etapa, e então, na última etapa, todas as observações são combinadas em um cluster.

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

Gráfico 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 destas tabelas, para evitar confusão, é utilizada uma terminologia diferente para designar as observações iniciais - monoclusters, e os clusters reais constituídos por 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" - caso. Para demonstrar a dependência da estrutura do cluster na escolha da métrica e na escolha do algoritmo de união do cluster, apresentamos a seguir um dendograma correspondente ao algoritmo de conexão completa. E aqui vemos que o objeto nº 44 é mesclado com o restante da seleção na última etapa.

Gráfico 5

Agora vamos compará-lo com outro diagrama obtido usando o método de link único nos mesmos dados. Em contraste com o método de conexão completa, pode-se observar que este método gera longas cadeias de objetos conectados sequencialmente entre si. Porém, nos três casos, podemos dizer que dois grupos principais se destacam.

Gráfico 6

Prestemos atenção também ao fato de que em todos os três casos o objeto nº 44 se une como um monocluster, embora em etapas diferentes do processo de agrupamento. A seleção de tais monoclusters é um bom meio de detectar observações anômalas, chamadas de outliers. Vamos deletar este objeto "suspeito" nº 44 e realizar o cluster novamente. Obtemos o seguinte dendograma:

Gráfico 7

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

3. 2 RECURSOS DOS MÉTODOS DE CLUSTERING ITERATIVO

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 desejado de clusters finais, que geralmente é denotado como “k”. Assim como nos métodos de cluster hierárquico, o usuário pode escolher um ou outro tipo de métrica. Diferentes algoritmos do método k-means também diferem na forma de escolher os centros iniciais de determinados clusters. 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, a escolha de um determinado número k de pontos iniciais é feita aleatoriamente, e esses pontos iniciais (cluster grains) podem posteriormente ser refinados em diversas etapas. Existem 4 etapas principais de tais métodos:

· selecionar ou atribuir k observações que serão 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 versões deste método, o usuário pode definir um valor numérico do critério, que é 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, também é possível definir o número máximo de iterações ou atingir um determinado número, geralmente bastante pequeno, com o qual é comparada a mudança na distância para todos os centros do cluster. Esta configuração é comumente chamada 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 os dados anteriores. O número de clusters procurados 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 é 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 McKean k-means aplicáveis ​​a 70 amostras de teste.

Variáveis

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

Tabela 3. Revisão detalhada dos dados no exemplo de três clusters.

Variável	Grupo #1	Grupo #2	Grupo #3

Gráfico 8

A análise dos valores médios das variáveis ​​de cada cluster permite-nos concluir que, de acordo com a característica 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 a característica X2, o primeiro cluster apresenta o valor mais baixo, enquanto o 2º e o 3º cluster apresentam valores médios superiores e 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 tabela a seguir de análise ANOVA dos resultados do agrupamento em dois clusters também mostra a necessidade de rejeitar a hipótese nula sobre a igualdade das médias do 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 acabou sendo superior a 5%.

Tabela 4. Tabela de análise de dispersão 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	Grupo #1	Grupo #2

Gráfico 9.

Caso o pesquisador não consiga determinar antecipadamente o número mais provável de clusters, ele é obrigado a repetir os cálculos, definindo um número diferente, semelhante ao feito acima. E então, comparando os resultados obtidos entre si, pare em uma das opções de cluster mais aceitáveis.

4 . CLUSTERING DE RECURSOS

Além de agrupar observações individuais, também existem algoritmos de agrupamento de recursos. Um dos primeiros métodos é o método de correlação das Plêiades Terentiev P.V. Imagens primitivas de tais Plêiades 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 encontraram uma correlação. Vários programas para agrupamento de objetos e recursos possuem procedimentos separados. Por exemplo, no pacote SAS para clustering de recursos, o procedimento VARCLUS (de VARiable - variável e CLUSter - cluster) é usado, enquanto a análise de cluster de observações é realizada por outros procedimentos - FASTCLUS e CLUSTER. A construção de um dendograma em ambos os casos é realizada através do procedimento TREE (árvore).

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

Gráfico 10. Dendogramaagrupando 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 desses pares, que é muito próxima de zero, indica sua forte relação de pares. Já para o par X11 e X12 o valor da distância entre clusters é muito maior e gira em torno de 300 unidades. Finalmente, uma distância muito grande entre os clusters esquerdo (X1-X10) e direito (X11-X12), igual a aproximadamente 1150 unidades, indica que a relação entre estes dois grupos de características é mínima.

5. ESTABILIDADE E QUALIDADE DO CLUSTERING

Obviamente, seria absurdo levantar a questão de quão absoluta é esta ou aquela classificação obtida com a ajuda de métodos de análise de cluster. Quando o método de agrupamento é alterado, 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 vários 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 verificar a estabilidade de uma solução de agrupamento pode ser dividir aleatoriamente a amostra inicial em duas partes aproximadamente iguais, agrupar ambas as partes e então comparar os resultados. Uma forma mais demorada envolve a exclusão sequencial do primeiro objeto no início e o agrupamento dos demais (N - 1) objetos. Além disso, realizando sequencialmente este procedimento, com exceção do segundo, terceiro, etc. objetos, a estrutura de todos os N clusters obtidos é analisada. Outro algoritmo para verificar a estabilidade envolve reprodução múltipla, duplicação da amostra original de N objetos e, em seguida, combinação de todas as amostras duplicadas em uma grande amostra (população pseudo-geral) e extração aleatória dela de uma nova amostra de N objetos. Depois disso, é realizado o agrupamento desta amostra, em seguida é extraída uma nova amostra aleatória e realizado novamente o agrupamento, etc. Também é bastante trabalhoso.

Não há menos problemas ao avaliar a qualidade do clustering. São conhecidos alguns algoritmos para otimizar soluções de cluster. Os primeiros trabalhos que continham formulações do critério de minimização da variância intracluster e de um algoritmo (do tipo k-means) para encontrar a solução ótima surgiram na década de 50. Em 1963 O artigo de J. Ward também apresentou um algoritmo hierárquico de otimização 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 afirmar 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 favor da conclusão sobre a otimalidade do agrupamento, também há resultados positivos da verificação dos momentos preditivos da solução obtida já 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 entre si. Neste caso, deve-se dar preferência à opção para a qual uma linha plana de tal incremento é observada desde o primeiro passo até vários penúltimos passos com um aumento vertical acentuado neste gráfico nos últimos 1-2 passos do agrupamento.

CONCLUSÕES

Em meu trabalho, tentei mostrar não apenas a complexidade desse tipo de análise, mas também as capacidades ideais 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. Considero também não sem importância a aceitabilidade das tecnologias informáticas nesta análise, o que permite tornar o processo de processamento dos resultados menos demorado e, assim, permite que se preste mais atenção à correcção da amostragem para análise.

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

Há ainda maior especificidade no uso da análise de cluster em relação a objetos que são descritos apenas por características qualitativas. Neste caso, os métodos de digitalização preliminar de características qualitativas e análise de cluster com novas características são bastante bem-sucedidos. No meu trabalho mostrei que a análise de cluster fornece muitas informações novas e originais tanto no caso de sua aplicação em sistemas suficientemente estudados, quanto no estudo de sistemas com estrutura desconhecida.

Deve-se notar também que a análise de agrupamento tornou-se indispensável na pesquisa evolutiva, 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) Aivazyan S. A., Enyukov I. S., Meshalkin L. D. Sobre a estrutura e conteúdo do pacote de software para análise estatística aplicada // Algoritmo 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ômica e 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. Botryology of botryology // 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) Duran 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 fuzzy 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 II, Gostilin NI, Frenkel' AA Em 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.--Cap. 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 multidimensional aplicada.--M., 1983.

15) Eeremaa R. Teoria geral de projeto de sistemas de cluster e algoritmos para encontrar suas representações numéricas: Proceedings of the Computing Center of TSU.--Tartu, 1978.

16) Yastremsky BS Obras Selecionadas.--M.: Estatísticas, 1964.

Documentos semelhantes

Os objetivos da segmentação de mercado nas atividades de marketing. A essência da análise de cluster, as principais etapas da sua implementação. Selecione como medir distância ou medida de similaridade. Métodos de agrupamento hierárquicos e não hierárquicos. Avaliação de confiabilidade e confiabilidade.

relatório, adicionado em 11/02/2009


Os principais indicadores da situação financeira da empresa. 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 a avaliação financeira e econômica do empreendimento.

tese, adicionada em 09/10/2013


Execute análises de cluster de empresas usando Statgraphics Plus. Construção de uma equação de regressão linear. Cálculo de coeficientes de elasticidade por 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. Âmbito 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 forma moderna de previsão. Um modelo baseado em ARIMA para descrever séries temporais estacionárias e não estacionárias na resolução de problemas de agrupamento. Modelos AR autorregressivos e aplicação de correlogramas.

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


Características dos diferentes tipos de métricas. Método do vizinho mais próximo 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 final, adicionado em 08/03/2015


Características da indústria da construção no Território de Krasnodar. Previsão do desenvolvimento da construção habitacional. Métodos e ferramentas modernas de análise de cluster. Métodos estatísticos multidimensionais 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 hierárquica. Desenvolvimento de um programa de busca do empréstimo hipotecário ideal.

trabalho final, 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 dos métodos 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 final, 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.

O termo "análise de cluster" foi usado pela primeira vez pelo psicólogo americano Robert Trion no trabalho de mesmo nome em 1930. Apesar disso, os termos "cluster" e "análise de cluster" são percebidos pelos falantes nativos como novos, o que é observado por Alexander Khrolenko, que conduziu uma análise de corpus do uso do lexema "cluster": "a maioria dos autores que usam este termo pagam 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 é em si um algoritmo específico, mas existe uma tarefa que precisa ser resolvida. Mark Ereshefsky observa em seu trabalho "A Escassez da Hierarquia Linear" que a análise de cluster é um dos três tipos de classificação de objetos no mundo, junto 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 de diferentes níveis: desde lógicas (paradigmáticas e sintagmáticas, por exemplo) até formação de palavras e conexões 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 determinação da 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 marca registrada do agrupamento como método de classificação é a ausência de classes especificadas. O agrupamento de documentos é uma tarefa de recuperação de informações. Ao contrário da categorização de texto, ela não inclui categorias ou conjuntos de treinamento predefinidos. Os clusters e os relacionamentos entre eles são "extraídos automaticamente dos documentos, e os documentos são anexados 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 compartilhar um agrupamento de características, 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 pesquisados
• 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 análise de cluster "suave" e difusa, 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. Nurgaliyeva observa que o método hierárquico “parece ser o mais adequado para resolver problemas linguísticos” (Nurgaliyeva, p. 1), pois permite ver e analisar a estrutura do fenômeno em estudo.

ANÁLISE DE CLUSTER NOS PROBLEMAS DE PREVISÃO SOCIOECONÔMICA

Introdução à análise de cluster.

Ao analisar e prever fenómenos socioeconómicos, o investigador frequentemente se depara com a multidimensionalidade da sua descrição. Isto acontece ao resolver o problema da segmentação do mercado, construindo uma tipologia de países de acordo com um número suficientemente grande de indicadores, prevendo a situação do 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 da comunicação.

Às vezes, a abordagem de análise de cluster é referida na literatura como 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 foi definido o tema da análise de cluster e sua descrição foi feita 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 aplicados nos mais diversos casos, mesmo nos casos em que se trata de um agrupamento simples, em que tudo se resume à formação de grupos de acordo com a semelhança quantitativa.

A grande vantagem da análise de cluster é que ela permite particionar objetos não por um parâmetro, mas por todo um conjunto de recursos. 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-nos considerar um conjunto de dados iniciais de natureza quase arbitrária. Isto é de grande importância, por exemplo, para previsões conjunturais, quando os indicadores apresentam formas variadas que dificultam o uso de abordagens econométricas tradicionais.

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

A análise de cluster é de grande importância 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 é possível destacar os períodos em que os valores dos indicadores correspondentes foram bastante próximos, bem como determinar os grupos de séries temporais cujas dinâmicas são mais semelhantes.

A análise de cluster pode ser usada ciclicamente. Nesse caso, o estudo é realizado até que os resultados desejados sejam alcançados. Ao mesmo tempo, cada ciclo aqui pode fornecer informações que podem mudar bastante a direção e as abordagens de futuras aplicações da análise de cluster. Este processo pode ser representado como um sistema de feedback.

Nos problemas de previsão socioeconómica, é muito promissor combinar a análise de cluster com outros métodos quantitativos (por exemplo, com análise de regressão).

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 particionamento selecionados. Ao reduzir a matriz de dados inicial para uma forma mais compacta, certas distorções podem ocorrer e as características individuais de objetos individuais também podem ser perdidas devido à sua substituição pelas características dos valores generalizados dos parâmetros do cluster. Ao classificar objetos, muitas vezes a possibilidade de ausência de quaisquer valores de cluster no conjunto considerado é ignorada.

Na análise de cluster considera-se que:

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

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.

O problema da análise de cluster.

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

Por exemplo, deixe G incluir n países, cada um dos quais é caracterizado pelo PIB per capita (F1), o número M de carros por 1.000 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 e assim por diante. O desafio é desagregar os países por nível de desenvolvimento.

A solução para o problema da análise de cluster são partições que satisfaçam um certo critério de otimalidade. Este critério pode ser algum 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 intragrupo dos desvios quadrados pode ser tomada 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 i-ésimo e j-ésimo objetos cairiam no mesmo cluster quando a distância (distância) entre os pontos Xi e Xj fosse pequena o suficiente e cairiam em clusters diferentes quando essa distância fosse grande o suficiente. Assim, entrar 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(Xi , Xj) ³ 0, para todos Xi e Xj de Ep

b) d(Xi, Xj) = 0 se e somente se Xi = Xj

c) d(Xi, Xj) = d(Xj, Xi)

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(Xi, Xj) para Xi e Xj é denominado distância entre Xi e Xj e equivale à distância entre Gi e Gj de acordo com as características selecionadas (F1, F2, F3, ..., Fp).

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, enquanto a norma lp cobre as funções de distância 1, 2, 3,.

Sejam n medidas X1, X2,..., Xn representadas como uma matriz de dados p ´n:

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

O conceito oposto à distância é o conceito de similaridade 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(Xi, Xj)<1 для Хi¹ Хj

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

3) S(Xi, Xj) = S(Xj, Xi)

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

O valor de 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. Detenhamo-nos em alguns deles (os métodos fornecidos a seguir são geralmente chamados de métodos de variância mínima).

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

1) O 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 algum valor limite S. Em termos da distância euclidiana d, isso significa que a distância entre dois pontos (objetos) de o cluster não deve exceder algum valor limite h. Assim, h determina o diâmetro máximo permitido de um subconjunto formando um cluster.

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

Cada objeto é considerado um cluster de um ponto. 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 de outro for mínima. O procedimento consiste em n - 1 etapas e resulta em partições que correspondem a todas as partições possíveis no método anterior para quaisquer valores limite.

3) Método da palavra.

Neste método, a soma dos quadrados dos desvios intragrupo é utilizada como função objetivo, 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, são combinados dois clusters que levam ao aumento mínimo na função objetivo, ou seja, soma dos quadrados intragrupo. 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 clustering prossegue passo a passo em cada uma das n–1 etapas combina dois clusters G e p tendo o valor mínimo d2ij Se n1 for muito maior que n2, então os centros de união de dois clusters estão próximos um do outro e as características do segundo cluster são praticamente ignoradas quando os clusters são combinados. Às vezes, esse método também é chamado de método de grupos ponderados.

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 estão de certa forma 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, você pode obter um cluster composto por n objetos e coincidindo com o conjunto inicial Ι = (Ι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). Com a ajuda de Ι i e Ι j formamos um novo cluster

(Ιi, Ιj). Construa 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

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

Inicialmente, a distância foi determinada apenas entre clusters de um único elemento, mas também é necessário determinar as distâncias entre clusters contendo mais de um elemento. Isso pode ser feito de várias maneiras e, dependendo do método escolhido, obtemos algoritmos de análise de cluster com propriedades diferentes. Pode-se, por exemplo, definir 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 se pode definir di+j,k como o mínimo destas duas distâncias:

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

Assim, é descrito o primeiro passo da operação do algoritmo hierárquico aglomerativo. Os próximos passos são os mesmos.

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 determina um algoritmo específico. Por exemplo, com 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 =

Neste 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, de modo 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 de conversão de distância assume a forma:

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

Este será o chamado algoritmo do “vizinho mais próximo”, que permite selecionar clusters de formato arbitrariamente complexo, desde que 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 agrupados são dadas. Em alguns casos, isso é verdade. Porém, apenas os objetos e suas características são especificados, e a 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 atributo 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 "city-block".

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

onde mi ,mj ,di ,dj são a média e a raiz dos desvios quadráticos médios para as características i e j, respectivamente. O valor 1 - r pode servir como medida da diferença entre as características. 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, um número m de clusters pode ser escolhido a priori. Porém, no caso geral, esse número é determinado no processo de divisão do conjunto em clusters.

Estudos foram realizados por Fortier e Solomon, e descobriu-se que o número de clusters deve ser considerado 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 viáveis ​​no conjunto de todas as partições possíveis. A dispersão total será tanto maior quanto maior for a fração b de partições admissíveis. Fortier e Solomon desenvolveram uma tabela na qual é possível encontrar o número de partiçõ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, como medida de heterogeneidade, não de dispersão medida é usada, 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) é a mudança na função correspondente. Por exemplo, somas de 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 é identificar os saltos determinados pela transição de fase de um estado de objetos fortemente acoplado para um fracamente acoplado.

1.6 Dendogramas.

O método mais conhecido de representação de uma matriz de distância ou similaridade é baseado na ideia de um dendograma ou diagrama de árvore. O dendograma pode ser definido como uma representação gráfica dos resultados do processo de agrupamento sequencial, que é realizado em termos de uma matriz de distâncias. Com o auxílio de um dendograma, é possível representar gráfica ou geometricamente o procedimento de agrupamento, desde que este procedimento opere apenas com elementos da matriz de distância ou similaridade.

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

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 no nível de proximidade igual a 0,9. Os objetos D e E são combinados em um nível de 0,8. Agora temos 4 clusters:

O tipo de dendograma depende da escolha da medida de similaridade ou distância entre o objeto e o cluster e do método de agrupamento. O ponto mais importante é a escolha de uma medida de similaridade ou de distância entre um objeto e um 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 por uma combinação consistente de elementos iniciais e uma 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, a partir do qual se forma uma sequência de grupos de divisão.

Os algoritmos de análise de cluster possuem hoje uma boa implementação de software que permite resolver problemas da mais alta 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 ​​mudem em escalas comparáveis.

A heterogeneidade das unidades de medida e a consequente impossibilidade de uma expressão razoável dos valores dos vários indicadores na mesma escala leva ao facto de a distância entre os pontos, reflectindo a posição dos objectos no espaço das suas propriedades, acabar depender de uma escala escolhida arbitrariamente. Para eliminar a heterogeneidade da medição dos dados iniciais, todos os seus valores são preliminarmente normalizados, ou seja, são expressos através da razão desses valores para um determinado valor que reflete certas propriedades deste 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 uma determinada observação separa 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 a comparação de observações de diferentes distribuições. 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 de uma observação fornece informações mais específicas sobre a sua localização.

Observe que os métodos de normalização significam o reconhecimento de todas as características como equivalentes do ponto de vista de elucidar a 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 normalização, atribuir a cada um dos indicadores um peso que reflectisse a sua importância no processo de estabelecimento de semelhanças e diferenças entre objectos.

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

indicadores generalizados de desenvolvimento socioeconómico - 9 pontos;

indicadores de distribuição setorial da população ocupada - 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 gastos públicos – 4 pontos;

indicadores “econômicos militares” - 3 pontos;

indicadores sociodemográficos - 4 pontos.

As estimativas dos especialistas foram relativamente estáveis.

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

Muitas vezes, na resolução de tais problemas, não se utiliza um, mas dois cálculos: o primeiro, em que todos os sinais são considerados equivalentes, o segundo, onde são atribuídos pesos diferentes de acordo com os valores médios das estimativas dos especialistas.

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

Vamos considerar algumas aplicações de análise de cluster.

A divisão dos países em grupos de acordo com o nível de desenvolvimento.

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

Cada um dos países atua nesta consideração como um objeto caracterizado por determinados valores de 31 indicadores. Conseqüentemente, eles podem ser representados como pontos em um espaço de 31 dimensões. 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 consideraçã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 o par de economias nacionais incluídas na matriz de similaridade, cuja distância entre elas é a menor. Estas serão obviamente as economias mais semelhantes e semelhantes. Na consideraçã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 sejam 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. Linhas e colunas correspondentes às distâncias de um par de países incluídos na união a todos os demais são descartadas da matriz de similaridade original, mas são adicionadas uma linha e uma coluna contendo a distância entre o cluster obtido pela uniã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. Por outras palavras, o grupo combinado de países é tratado como um todo com características aproximadamente iguais à média das características dos seus países constituintes.

O segundo passo da análise é considerar uma matriz assim transformada com 64 linhas e colunas. Novamente, identifica-se um par de economias cuja distância é de menor importância, e elas, tal como no primeiro caso, são reunidas. Neste caso, a menor distância pode ser tanto entre um par de países, como entre qualquer país e a uniã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 ao restante dos recursos; além disso, na matriz modificada, um par de objetos mais próximos é revelado. A análise continua até o esgotamento completo da matriz (ou seja, até que todos os países sejam reunidos). Os resultados generalizados da análise matricial podem ser representados 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 complicado do que o esquema em que aparecem apenas cinco economias nacionais. Esta árvore inclui 65 níveis de acordo com o número de objetos correspondentes. 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 mais próximos em termos do tipo geral de economias nacionais. No terceiro nível, é anotado o próximo rácio de par de países mais semelhante (como já mencionado, ou um novo par de países, ou um novo país e um par já identificado de países semelhantes podem estar neste rácio). E assim por diante 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 (sem os EUA)

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

2. A divisão dos países segundo o critério de proximidade cultural.

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

Os seguintes grupos de países foram obtidos por meio de agrupamento:

Árabe;

Oriente médio;

Escandinavo;

Falante de alemão;

Falante de inglês;

Românico Europeu;

Latino Americano;

Extremo Oriente.

3. Desenvolvimento de uma previsão 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 da conjuntura das commodities, contribuindo para a facilitação e simplificação dos procedimentos computacionais, garantindo maior compacidade dos resultados obtidos mantendo a precisão exigida. A utilização da análise de cluster permite dividir todo o conjunto inicial de indicadores de mercado em grupos (clusters) de acordo com os critérios relevantes, 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 das tarefas de previsão baseia-se no uso de análise de cluster.

Por exemplo, a tarefa de desenvolver uma previsão do 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

Estoques de produtores de zinco:

X14 - no mundo

X16 - Europa

X17 - outros países

Estoques de consumo de zinco:

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ção 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. As relações foram analisadas com base em uma matriz de coeficientes de correlação pareados. Aqui foi aceita a hipótese da distribuição normal dos indicadores da conjuntura analisados. É claro que os rij não são o único indicador possível da relação dos indicadores utilizados. A necessidade de utilizar a análise de cluster neste problema 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 para 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 o excesso do número de valores observados sobre 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 volumosa de coeficientes de correlação. Com a ajuda da análise de cluster, todo o conjunto de variáveis ​​​​de mercado pode ser dividido em grupos de 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 aplicado um dos algoritmos de análise de cluster hierárquica aglomerativa. A cada passo, o número de clusters é reduzido em um devido à união ótima, em certo sentido, de dois grupos. O critério de adesão é a alteração da função correspondente. Em função disso, foram utilizados 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, incluindo um elemento cada. O processo de agrupamento começa com a união desse par de clusters, o que leva a um aumento mínimo na soma dos desvios quadrados. Isto requer estimar a soma dos desvios quadrados para cada uma das possíveis uniões de cluster. Na próxima etapa, os valores das somas dos desvios quadrados já são considerados para os clusters, e assim por diante. 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, pode-se perceber um salto (um ou mais) em sua dinâmica, que pode ser interpretado como uma característica do número de grupos “objetivamente” existentes na população estudada. No exemplo acima, os saltos ocorreram quando o número de clusters era 7 e 5. Além disso, o número de grupos não deveria ser reduzido, 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 no sentido econômico e mais relacionadas ao critério de mercado selecionado – neste caso, com as cotações do zinco na London Metal Exchange. Esta abordagem permite salvar uma parte significativa das informações contidas no conjunto original de indicadores iniciais da conjuntura.