Algoritmo para segmentação de dados de sequência

Eu tenho uma grande sequência de vetores de comprimento N. Preciso de algum algoritmo de aprendizado não supervisionado para dividir esses vetores em segmentos M.

Por exemplo:

O K-means não é adequado, porque coloca elementos semelhantes de locais diferentes em um único cluster.

Atualizar:

Os dados reais são assim:

Aqui, vejo três clusters: [0..50], [50..200], [200..250]

Atualização 2:

Usei k-means modificados e obtive este resultado aceitável:

Fronteiras dos clusters: [0, 38, 195, 246]

Por favor, veja o meu comentário acima e esta é a minha resposta de acordo com o que entendi da sua pergunta:

Como você afirmou corretamente, você não precisa de Clustering, mas de Segmentação . Na verdade, você está procurando pontos de mudança em suas séries temporais. A resposta realmente depende da complexidade dos seus dados. Se os dados são tão simples quanto o exemplo acima, você pode usar a diferença de vetores que ultrapassa os pontos de mudança e definir um limite para detectar esses pontos como abaixo: Como você vê, por exemplo, um limite de 20 (ou seja, e ) detectará os pontos. Obviamente, para dados reais, você precisa investigar mais para encontrar os limites.$dx<-20$$dx>20$

Pré-processando

Observe que há uma troca entre a localização exata do ponto de mudança e o número exato de segmentos, ou seja, se você usar os dados originais, encontrará os pontos de mudança exatos, mas todo o método é sensível ao ruído, mas se você suavizar seus sinais primeiro, você pode não encontrar as mudanças exatas, mas o efeito do ruído será muito menor, conforme mostrado nas figuras abaixo:

Conclusão

Minha sugestão é suavizar seus sinais primeiro e optar por um método simples de agrupamento (por exemplo, usando GMM s) para encontrar uma estimativa precisa do número de segmentos nos sinais. Dada essa informação, você pode começar a encontrar pontos de mudança limitados pelo número de segmentos encontrados na parte anterior.

Espero que tudo tenha ajudado :)

Boa sorte!

ATUALIZAR

Felizmente, seus dados são bem diretos e limpos. Eu recomendo fortemente algoritmos de redução de dimensionalidade (por exemplo, PCA simples ). Eu acho que revela a estrutura interna dos seus clusters. Depois de aplicar o PCA aos dados, você pode usar k-significa muito, muito mais fácil e mais preciso.

Uma solução séria (!)

De acordo com seus dados, vejo que a distribuição generativa de diferentes segmentos é diferente, o que é uma grande chance para você segmentar suas séries temporais. Veja isto (original , arquivo , outra fonte ), que provavelmente é a melhor e mais avançada solução para o seu problema. A principal idéia por trás deste artigo é que, se diferentes segmentos de uma série temporal forem gerados por diferentes distribuições subjacentes, você poderá encontrar essas distribuições, defini-las como a verdade fundamental para sua abordagem de agrupamento e encontrar clusters.

Por exemplo, assuma um vídeo longo no qual os primeiros 10 minutos em que alguém anda de bicicleta, nos segundos 10 minutos em que ele está correndo e no terceiro em que está sentado. você pode agrupar esses três segmentos diferentes (atividades) usando essa abordagem.

Sabe-se que o cluster K-means fornece mínimos locais, dependendo da sua inicialização inicial dos centros de cluster.

No entanto, a segmentação k-means pode, eu acho, ser resolvida globalmente, pois não permitimos nada na busca da solução.

Pude ver pelos seus comentários que você conseguiu alcançar uma segmentação. Você poderia dar algum feedback, por favor? Sua solução é a melhor solução? Ou você se contentou com uma solução boa o suficiente?

Apenas como sugestão: você pode tentar usar o algoritmo DBSCAN, pois ele geralmente funciona muito melhor do que o K-means para clustering

Caso contrário, se você quiser tentar algo novo para agrupar e aprender algumas coisas interessantes, sugiro que tente alguma Análise de Dados Topológicos através de diagramas persistentes. Vou deixar aqui uma introdução fácil e agradável :)

https://towardsdatascience.com/persistent-homology-with-examples-1974d4b9c3d0