Free Press

Uma tarefa envolvendo aprendizagem de máquina pode não ser linear, mas tem um número de passos bem conhecidos:

• Definição de problema.
• Preparação de dados.
• Aprendizagem de um modelo subjacente.
• Melhorar o modelo subjacente através de avaliações quantitativas e qualitativas.
• Apresentar o modelo.

Uma boa maneira de chegar a um novo problema é trabalhar através da identificação e definição do problema da melhor maneira possível e aprender um modelo que capte informações significativas a partir dos dados. Embora os problemas no Reconhecimento de Padrões e Aprendizagem de Máquina possam ser de vários tipos, eles podem ser amplamente classificados em três categorias:

• Aprendizagem supervisionada:
  O sistema é apresentado com exemplos de entradas e suas saídas desejadas, dados por um “professor”, e o objetivo é aprender uma regra geral que mapeia entradas para saídas.
• Aprendizagem sem supervisão:
  Não são dadas etiquetas ao algoritmo de aprendizagem, deixando-o por si só para encontrar estrutura em suas entradas. A aprendizagem sem supervisão pode ser um objectivo em si (descobrir padrões ocultos nos dados) ou um meio para um fim (aprendizagem de características).
• Reinforcement Learning:
  Um sistema interage com um ambiente dinâmico no qual deve realizar um determinado objectivo (como conduzir um veículo ou jogar um jogo contra um adversário). O sistema é fornecido feedback em termos de recompensas e punições à medida que navega no seu espaço problemático.

Entre aprendizagem supervisionada e não supervisionada está a aprendizagem semi-supervisionada, onde o professor dá um sinal de treino incompleto: um conjunto de treino com algumas (muitas vezes muitas) das saídas alvo em falta. Vamos focar na aprendizagem não supervisionada e agrupamento de dados neste blog post.

Aprendizagem não supervisionada

Em alguns problemas de reconhecimento de padrões, os dados de formação consistem num conjunto de vectores de entrada x sem quaisquer valores alvo correspondentes. O objetivo em tais problemas de aprendizagem não supervisionada pode ser descobrir grupos de exemplos similares dentro dos dados, onde é chamado de clustering, ou determinar como os dados são distribuídos no espaço, conhecido como estimativa de densidade. Para colocar em termos mais simples, para um espaço n-sampled x1 a xn, não são fornecidas etiquetas de classe verdadeiras para cada amostra, portanto conhecidas como aprendizagem sem professor..

Aulas com aprendizagem não supervisionada:

• A aprendizagem não supervisionada é mais difícil em comparação com as tarefas de aprendizagem supervisionada..
• Como sabemos se os resultados são significativos uma vez que não há etiquetas de resposta disponíveis?
• Deixe o especialista olhar para os resultados (avaliação externa)
• Definir uma função objectiva no agrupamento (avaliação interna)

Porquê a aprendizagem não supervisionada é necessária apesar destes problemas?

• Anular grandes conjuntos de dados é muito dispendioso e por isso podemos rotular apenas alguns exemplos manualmente. Exemplo: Reconhecimento da Fala
• Existem casos em que não sabemos em quantas/quais classes estão os dados divididos. Exemplo: Data Mining
• Pode ser que queiramos usar o clustering para obter alguma visão da estrutura dos dados antes de desenhar um classificador.

Aprendizagem Sem Supervisão pode ser ainda classificada em duas categorias:

• Aprendizagem Paramétrica Sem Supervisão
  Neste caso, assumimos uma distribuição paramétrica dos dados. Assume-se que os dados da amostra provêm de uma população que segue uma distribuição de probabilidade baseada em um conjunto fixo de parâmetros. Teoricamente, em uma família normal de distribuições, todos os membros têm a mesma forma e são parametrizados por média e desvio padrão. Isso significa que se você conhece a média e o desvio padrão, e que a distribuição é normal, você sabe a probabilidade de qualquer observação futura. O Aprendizado Paramétrico Sem Supervisão envolve a construção de Modelos Mistos Gaussianos e a utilização do algoritmo de Expectativa-Maximização para prever a classe da amostra em questão. Este caso é muito mais difícil que o aprendizado supervisionado padrão porque não há etiquetas de resposta disponíveis e, portanto, não há medida correta de precisão disponível para verificar o resultado.
• Aprendizado Não Paramétrico Sem Supervisão
  Na versão não paramétrica do aprendizado sem supervisão, os dados são agrupados em clusters, onde cada cluster (esperançosamente) diz algo sobre categorias e classes presentes nos dados. Este método é comumente usado para modelar e analisar dados com pequenos tamanhos de amostra. Ao contrário dos modelos paramétricos, modelos não paramétricos não requerem que o modelador faça qualquer suposição sobre a distribuição da população, e por isso são às vezes referidos como um método sem distribuição.

O que é Clustering?

Clustering pode ser considerado o mais importante problema de aprendizagem não supervisionada; assim, como qualquer outro problema deste tipo, ele trata de encontrar uma estrutura em uma coleção de dados não rotulados. Uma definição vaga de clustering poderia ser “o processo de organização de objetos em grupos cujos membros são semelhantes de alguma forma”. Um cluster é portanto uma coleção de objetos que são “semelhantes” entre eles e são “diferentes” dos objetos pertencentes a outros clusters.

>

Austering baseado na distância.

Dado um conjunto de pontos, com uma noção de distância entre pontos, agrupando os pontos em algum número de clusters, de tal forma que

• distâncias internas (dentro do cluster) as distâncias devem ser pequenas i.Os membros dos agrupamentos são próximos/similares entre si.
• distâncias externas (intra-agrupamento) devem ser grandes, ou seja, os membros dos diferentes agrupamentos são diferentes.

As Metas do Agrupamento

O objetivo do agrupamento é determinar o agrupamento interno em um conjunto de dados não rotulados. Mas como decidir o que constitui um bom agrupamento? Pode ser demonstrado que não existe um critério absoluto “melhor” que seria independente do objetivo final do agrupamento. Consequentemente, é o usuário que deve fornecer esse critério, de tal forma que o resultado do agrupamento se adapte às suas necessidades.

>

>

Na imagem acima, como sabemos qual é a melhor solução de agrupamento?

Para encontrar uma solução particular de clustering , precisamos definir as medidas de similaridade para os clusters.

Medidas de Proximidade

Para clustering , precisamos definir uma medida de proximidade para dois pontos de dados. Proximidade aqui significa quão semelhantes/dissimilares as amostras são em relação umas às outras.

• Medida de similaridade S(xi,xk): grande se xi,xk são semelhantes
• Dissimilaridade(ou distância) medida D(xi,xk): pequeno se xi,xk forem semelhantes

Existem várias medidas de semelhança que podem ser usadas.

• Vetores: Distância Cosina

>

• Sets: Distância Jaccard

Pontos: Euclidean Distance
q=2

Uma medida de proximidade “boa” é MUITO dependente da aplicação. Os clusters devem ser invariantes sob as transformações “naturais” ao problema. Além disso, enquanto o agrupamento não é aconselhado a normalizar dados que são extraídos de múltiplas distribuições.

Algoritmos de clustering

Algoritmos de clustering podem ser classificados como listados abaixo:

• Clustering Exclusivo
• Overlapping Clustering
• Clustering Hierárquico
• Clustering Probabilístico

No primeiro caso os dados são agrupados de forma exclusiva, de modo que se um determinado ponto de dados pertence a um cluster definido, então ele não poderia ser incluído em outro cluster. Um exemplo simples disso é mostrado na figura abaixo, onde a separação de pontos é feita por uma linha reta em um plano bidimensional.

Pelo contrário, o segundo tipo, o agrupamento sobreposto, usa conjuntos difusos para agrupar dados, de modo que cada ponto pode pertencer a dois ou mais agrupamentos com diferentes graus de adesão. Neste caso, os dados serão associados a um valor de associação apropriado.

Um algoritmo de agrupamento hierárquico é baseado na união entre os dois clusters mais próximos. A condição inicial é realizada através da definição de cada ponto de dados como um cluster. Após algumas iterações, ele chega aos clusters finais desejados.

Finalmente, o último tipo de clustering usa uma abordagem completamente probabilística.

Neste blog vamos falar sobre quatro dos algoritmos de clustering mais utilizados:

• K significa
• Fuzzy K significa
• Austering hierárquico
• Mistura de Gaussians

Cada um destes algoritmos pertence a um dos tipos de clustering listados acima. Enquanto K significa um exclusivo algoritmo de clustering, Fuzzy K significa um algoritmo de clustering sobreposto, Hierarquical clustering é óbvio e por último Mixture of Gaussians é um algoritmo probabilístico de clustering. Iremos discutir sobre cada método de agrupamento nos parágrafos seguintes.

K-Means Clustering

K-means é um dos mais simples algoritmos de aprendizagem não supervisionada que resolve o bem conhecido problema de agrupamento. O procedimento segue uma forma simples e fácil de classificar um determinado conjunto de dados através de um certo número de clusters (assumir k clusters) fixados a priori. A idéia principal é definir centros k, um para cada cluster. Estes centros devem ser colocados de uma forma inteligente devido à localização diferente causa resultados diferentes. Portanto, a melhor escolha é colocá-los o mais longe possível um do outro. O passo seguinte é tomar cada ponto pertencente a um determinado conjunto de dados e associá-lo ao centróide mais próximo. Quando nenhum ponto está pendente, o primeiro passo é completado e uma grupagem antecipada é feita. Neste ponto precisamos recalcular k novos centróides como baricentros dos clusters resultantes do passo anterior. Depois de termos estes k novos centróides, uma nova ligação tem de ser feita entre os mesmos pontos do conjunto de dados e o novo centróide mais próximo. Um laço foi gerado. Como resultado deste laço podemos notar que os k centróides mudam a sua localização passo a passo até que não haja mais mudanças. Em outras palavras, os centróides não se movem mais.

Finalmente, este algoritmo visa minimizar uma função objetiva, neste caso uma função de erro ao quadrado. A função objetiva

>

>

>

>

where

>

>

>

>>

>>

>

é uma medida de distância escolhida entre um ponto de dados xi e o centro de agrupamento cj, é um indicador da distância dos n pontos de dados dos seus respectivos centros de agrupamento.

O algoritmo é composto pelos seguintes passos:

• Let X = {x1,x2,x3,……..,xn} ser o conjunto de pontos de dados e V = {v1,v2,…….,vc} ser o conjunto de centros.
• Selecionar aleatoriamente ‘c’ centros de agrupamento.
• Calcular a distância entre cada ponto de dados e os centros de agrupamento.
• Atribuir o ponto de dados ao centro de cluster cuja distância do centro de cluster é mínima de todos os centros de cluster.
• Recalcular o novo centro de cluster usando:

Onde, ‘ci’ representa o número de pontos de dados no ith cluster.

• Recalcular a distância entre cada ponto de dados e os novos centros de cluster obtidos.
• Se nenhum ponto de dados foi reatribuído então pare, caso contrário repita a partir do passo 3).

Embora se possa provar que o procedimento sempre terminará, o algoritmo k significa que não necessariamente encontrará a configuração mais ótima, correspondente ao mínimo da função objetivo global. O algoritmo também é significativamente sensível aos centros de cluster inicialmente seleccionados aleatoriamente. O algoritmo k significaans pode ser executado várias vezes para reduzir este efeito.

K significaans é um algoritmo simples que foi adaptado a muitos domínios problemáticos. Como vamos ver, é um bom candidato para extensão para trabalhar com vectores de características difusas.

O procedimento k significaans pode ser visto como um algoritmo ganancioso para dividir as n amostras em k clusters de forma a minimizar a soma das distâncias ao quadrado para os centros de cluster. Ele tem alguns pontos fracos:

• A forma de inicializar as médias não foi especificada. Uma maneira popular de começar é escolher aleatoriamente k das amostras.
• Pode acontecer que o conjunto de amostras mais próximo de mi esteja vazio, de modo que mi não possa ser atualizado. Este é um problema que precisa ser tratado durante a implementação, mas é geralmente ignorado.
• Os resultados dependem do valor de k e não há uma forma ideal de descrever um melhor “k”.

Este último problema é particularmente problemático, uma vez que muitas vezes não temos forma de saber quantos clusters existem. No exemplo mostrado acima, o mesmo algoritmo aplicado aos mesmos dados produz os seguintes 3 meios de clustering. É melhor ou pior que os 2 meios de clustering?

Felizmente não existe uma solução teórica geral para encontrar o número ideal de clusters para um dado conjunto de dados. Uma abordagem simples é comparar os resultados de múltiplas execuções com diferentes classes de k e escolher a melhor de acordo com um determinado critério, mas precisamos ter cuidado porque o aumento de k resulta em valores menores de funções de erro por definição, mas também aumenta o risco de sobreajuste.

Fuzzy K-Means Clustering

No fuzzy clustering, cada ponto tem uma probabilidade de pertencer a cada cluster, em vez de pertencer completamente a apenas um cluster, como é o caso nos meios tradicionais de k. Os k-meios difusos tentam lidar especificamente com o problema onde os pontos estão um pouco entre centros ou são ambíguos, substituindo a distância pela probabilidade, o que, claro, poderia ser alguma função da distância, como ter probabilidade relativa ao inverso da distância. Fuzzy k-means usa um centróide ponderado com base nessas probabilidades. Os processos de inicialização, iteração e terminação são os mesmos que os usados nos k-meios. Os clusters resultantes são melhor analisados como distribuições probabilísticas do que como uma atribuição dura de etiquetas. Deve-se perceber que k significa é um caso especial de fuzzy k significaans quando a função de probabilidade utilizada é simplesmente 1 se o ponto de dados estiver mais próximo de um centróide e 0 caso contrário.

O algoritmo fuzzy k significaans é o seguinte:

• Assumir um número fixo de clusters K.
• Inicialização: Inicializar aleatoriamente os k-means μk associados aos clusters e calcular a probabilidade de cada ponto de dados Xi ser um membro de um dado cluster K,
  P(PointXiHasLabelK|Xi,K).
• Iteração: Recalcular o centróide do cluster como o centróide ponderado dadas as probabilidades de adesão de todos os pontos de dados Xi :

• Terminação: Iterar até à convergência ou até ser atingido um número de iterações especificado pelo utilizador (a iteração pode estar presa a alguns máximos ou mínimos locais)

Para uma melhor compreensão, podemos considerar este simples exemplo mono-dimensional. Dado um determinado conjunto de dados, suponhamos que o represente como distribuído em um eixo. A figura abaixo mostra isto:

Vejamos a figura, podemos identificar dois clusters nas proximidades das duas concentrações de dados. Iremos nos referir a eles usando ‘A’ e ‘B’. Na primeira abordagem mostrada neste tutorial – o algoritmo k significa – associamos cada ponto de dados a um centroide específico; portanto, esta função de afiliação pareceu assim:

Na abordagem Fuzzy k significa, em vez disso, o mesmo dado ponto de dados não pertence exclusivamente a um cluster bem definido, mas pode ser colocado de forma intermédia. Neste caso, a função de associação segue uma linha mais suave para indicar que cada ponto de dados pode pertencer a vários clusters com diferentes extensões de associação.

>

Na figura acima, o ponto de dados mostrado como um ponto marcado em vermelho pertence mais ao cluster B do que ao cluster A. O valor 0,2 de ‘m’ indica o grau de adesão a A para tal ponto de dados.

Algoritmos hierárquicos de clustering

Dados um conjunto de N itens a serem agrupados, e uma matriz de distância N*N (ou similaridade), o processo básico de agrupamento hierárquico é este:

• Inicie atribuindo cada item a um cluster, de modo que se você tiver N itens, você agora tem N clusters, cada um contendo apenas um item. Deixe as distâncias (semelhanças) entre os clusters iguais às distâncias (semelhanças) entre os itens que contêm.
• Conheça o par de clusters mais próximo (mais semelhante) e funda-os em um único cluster, de modo que agora você tenha um cluster a menos.
• Compute as distâncias (semelhanças) entre o novo cluster e cada um dos clusters antigos.
• Repita as etapas 2 e 3 até que todos os itens sejam agrupados em um único cluster de tamanho N.

Clustering as a Mixture of Gaussians

Há outra forma de lidar com os problemas de clustering: uma abordagem baseada em modelos, que consiste em utilizar certos modelos para clusters e tentar otimizar o ajuste entre os dados e o modelo.

Na prática, cada cluster pode ser matematicamente representado por uma distribuição paramétrica, como um gaussiano. Todo o conjunto de dados é, portanto, modelado por uma mistura dessas distribuições.
Um modelo de mistura com alta probabilidade tende a ter as seguintes características:

• distribuições de componentes têm altos “picos” (os dados em um cluster são apertados);
• o modelo de mistura “cobre” bem os dados (padrões dominantes nos dados são capturados pelas distribuições de componentes).

Principais vantagens do agrupamento baseado em modelos:

• Técnicas de inferência estatística bem estudadas disponíveis;
• flexibilidade na escolha da distribuição de componentes;
• obter uma estimativa de densidade para cada agrupamento;
• uma classificação “suave” está disponível.

Mistura de Gaussians
O método de agrupamento mais utilizado deste tipo é baseado na aprendizagem de uma mistura de Gaussians:

Um modelo de mistura é uma mistura de distribuições de k componentes que fazem colectivamente uma distribuição de mistura f(x):

O αk representa a contribuição do kth componente na construção de f(x). Na prática, a distribuição paramétrica (por exemplo, gaussianos), é frequentemente utilizada, uma vez que muito trabalho tem sido feito para compreender o seu comportamento. Se você substituir cada fk(x) por um gaussiano você obtém o que é conhecido como um modelo de mistura gaussiana (GMM).

O Algoritmo EM

Expectação-Maximização assume que seus dados são compostos de múltiplas distribuições normais multivariadas (note que esta é uma suposição muito forte, em particular quando você fixa o número de clusters!). Como alternativa, EM é um algoritmo para maximizar uma função de probabilidade quando algumas das variáveis do seu modelo não são observadas (ou seja, quando você tem variáveis latentes).
Você pode perguntar, se estamos apenas tentando maximizar uma função, por que não usamos apenas a maquinaria existente para maximizar uma função. Bem, se você tentar maximizar isso pegando as derivadas e colocando-as a zero, você verá que em muitos casos as condições de primeira ordem não têm uma solução. Há um problema de galinha e ovo que para resolver para os parâmetros do seu modelo você precisa saber a distribuição dos seus dados não observados; mas a distribuição dos seus dados não observados é uma função dos parâmetros do seu modelo.

Expectação-Maximização tenta contornar isto adivinhando iterativamente uma distribuição para os dados não observados, depois estimando os parâmetros do modelo maximizando algo que é um limite inferior na função de probabilidade real, e repetindo até a convergência:

O algoritmo de Expectativa-Maximização

• Inicie com o palpite para os valores dos parâmetros do seu modelo
• E-step: Para cada datapoint que tenha valores ausentes, use sua equação de modelo para resolver para a distribuição dos dados ausentes dado seu palpite atual dos parâmetros do modelo e dado os dados observados (note que você está resolvendo para uma distribuição para cada valor ausente, não para o valor esperado). Agora que temos uma distribuição para cada valor em falta, podemos calcular a expectativa da função de probabilidade em relação às variáveis não observadas. Se o nosso palpite para o parâmetro do modelo estava correto, esta probabilidade esperada será a probabilidade real dos nossos dados observados; se os parâmetros não estavam corretos, será apenas um limite inferior.
• M-step: Agora que temos uma função de probabilidade esperada sem variáveis não observadas, maximize a função como faria no caso totalmente observado, para obter uma nova estimativa dos parâmetros do seu modelo.
• Repetir até à convergência.

Problemas associados ao clustering

Há uma série de problemas com o clustering. Entre eles:

>

• A manipulação com grande número de dimensões e grande número de itens de dados pode ser problemática devido à complexidade do tempo;
• A eficácia do método depende da definição de “distância” (para o clustering baseado na distância). Se uma medida de distância óbvia não existe, devemos “defini-la”, o que nem sempre é fácil, especialmente em espaços multidimensionais;
• o resultado do algoritmo de agrupamento (que em muitos casos pode ser arbitrário por si só) pode ser interpretado de diferentes maneiras.

Possíveis Aplicações

Os algoritmos de clustering podem ser aplicados em muitos campos, por exemplo:

• Marketing: encontrando grupos de clientes com comportamento semelhante dada uma grande base de dados de dados de clientes contendo as suas propriedades e registos de compras anteriores;
• Biologia: classificação de plantas e animais dadas as suas características;
• Seguros: identificação de grupos de segurados com alto custo médio de sinistros; identificação de fraudes;
• Estudos de terremotos: agrupamento de epicentros de terremotos observados para identificar zonas perigosas;
• World Wide Web: classificação de documentos; agrupamento de dados de weblog para descobrir grupos de padrões de acesso similares.