Encontrar um número conhecido de centros circulares que maximize o número de pontos a uma distância fixa

10

Eu tenho um conjunto de dados 2D em que desejo encontrar os centros de um número especificado de centros de círculos ( ) que maximizam o número total de pontos dentro de uma distância especificada ( ).RNR

por exemplo, eu tenho 10.000 pontos de dados e quero encontrar os centros de círculos que capturam o máximo de pontos possível dentro de um raio de . Os 5 centros e o raio de 10 são dados previamente, não derivados dos dados.N = 5 R = 10(Xi,Yi)N=5R=10

A presença de um ponto de dados dentro de um círculo é uma proposição binária ou / ou. Se , não há diferença de valor para um ponto a 11 unidades de distância vs. 100 unidades de distância, pois ambos são> 10. Da mesma forma, por estar dentro do círculo, não há valor extra em estar perto do centro vs. . Um ponto de dados está em um dos círculos ou sai.R=10

Existe um bom algoritmo que pode ser usado para resolver esse problema? Isso parece relacionado às técnicas de agrupamento, mas, em vez de minimizar a distância média, a função "distance" é 0 se o ponto estiver dentro de de qualquer um dos pontos e 1 caso contrário.NRN

Minha preferência seria encontrar uma maneira de fazer isso em R, mas qualquer abordagem seria apreciada.

colonel.triq
fonte
A sobreposição de círculos é permitida?
curious_cat
11
Essa é essencialmente uma operação de vizinhança (ou focal) em um conjunto de dados raster. Seria bom verificar o site do GIS para ver se ele foi respondido e examinar os pacotes R para realizar análises de varredura.
21713 Andy
11
A sobreposição de círculos é permitida, mas os pontos de dados cobertos por ambos os círculos não serão contados duas vezes. Obrigado pelo ponteiro para operação vizinha / focal em conjuntos de dados raster. Vou procurar algo nesse sentido.
colonel.triq
@ Andy W Embora as operações focais estivessem naturalmente envolvidas em uma solução, essa questão está além da experiência da comunidade GIS, IMHO, porque é realmente um problema de otimização (bastante difícil). Não é uma grade simples para encontrar o máximo de uma grade focal. Eu recomendaria mantê-lo aqui por um tempo e, se nenhuma solução satisfatória surgir, migrar para um site orientado à programação.
whuber
.... ou migrando para math.overflow? Eles podem ter algumas idéias sobre isso também.
curious_cat

Respostas:

1

Este é um problema de variação k-significa. O raio dos centros não importa, desde que sejam assumidos iguais.

Ligações:

Ele colocará os centros dos círculos em locais de maior probabilidade dos pontos.

Procedimento clássico dos meios K:

  1. definir contagem de cluster para 5
  2. coloque cada ponto em um cluster aleatório
  3. para cada cluster, calcule a posição média
  4. para cada ponto, calcule a distância para cada nova posição média
  5. associar a associação ao cluster mais próximo
  6. repita até concluir (iterações, alteração de posição ou outra métrica de erro)

Opções:

  • Você pode usar um pouco de relaxamento depois das 3, onde traduz lentamente a posição média para a nova posição.
  • este é um sistema discreto, para que não converja perfeitamente. Às vezes acontece e você pode terminar quando os pontos param de mudar de associação, mas às vezes eles apenas se mexem um pouco.
  • Se você está criando seu próprio código (como a maioria das pessoas deveria), pode usar os meios k do POR acima como ponto de partida e fazer alguma variação no EM informada pela porcentagem de pontos exclusiva e completamente abrangida pelos círculos.

Por que o K-significa ataca o problema:

  • É o equivalente a ajustar um Modelo de Mistura Gaussiano, onde as covariâncias dos componentes são iguais. Os centros dos componentes da mistura serão localizados nas posições de maior expectativa de pontos. As curvas de probabilidade constante serão círculos. Este é o algoritmo EM, por isso possui convergência assintótica. As associações são difíceis, não fáceis.
  • Penso que, se a suposição fundamental do modelo de mistura de componentes de igual variância for razoavelmente "próxima", o que quer que isso signifique, então esse método será adequado. Se você distribuir pontos aleatoriamente, é menos provável que se ajuste bem.

Deve haver algum análogo de um "Poisson inflado zero" onde haja um componente não gaussiano que capte a distribuição uniforme.

Se você quisesse "ajustar" o seu modelo e estivesse confiante de que havia pontos de amostra suficientes, poderia inicializar com o k-means e, em seguida, fazer um ajustador de k-means aumentado que remove os pontos fora dos raios dos círculos da competição. Isso perturbaria levemente os círculos que você tem, mas pode ter um desempenho ligeiramente melhorado, dados os dados.

EngrStudent
fonte
Você poderia, por favor, ser um pouco mais explícito sobre como o K-means resolve esse problema?
whuber
Obrigado pela sugestão. Ainda não está claro para mim que a abordagem K-means resolve o problema? Considere o exemplo de três grupos de dados gerados normais (0,1), em que os centros são deslocados em 5 unidades ou mais. Os centros K-means dariam a densidade máxima. Agora, corte alguns dos pontos com "furos", para que os dados a menos de 0,5 dos centros sejam removidos. O K-means ainda mostrará os mesmos centros, mas se você estiver tentando obter cobertura máxima para N = 3, R = 0,5, essa claramente não é a resposta certa (porque os orifícios das rosquinhas não contêm dados). Estou entendendo mal alguma coisa?
amigos estão
Analisarei mais sua pergunta para obter uma resposta melhor quando tiver tempo. Eu gosto de permitir pesos negativos. Às vezes, é possível lidar com rosquinhas de dados e polinômios racionais radiais.
EngrStudent
0

Alguém provavelmente tem um algoritmo formal melhor, mas aqui está uma abordagem de força bruta (um hack?). Eu usaria um dos algoritmos de bin hexagonal para calcular um histograma 2D. Como hexbinem R.

Eu usaria um tamanho hexagonal que circunscreveria seu círculo de raio R e depois classificaria nas N caixas superiores. Se você tiver Ncaixas distantes distantes, ótimo. Agora, uma maneira é mover o círculo localmente em uma escala 2 * R (nas direções x e y) do centro dos hexágonos de densidade superior. As densidades computacionais podem otimizar aproximadamente a posição localmente. Isso explica o fato de que os hexágonos não eram uma janela móvel em relação a uma origem fixa.

Se todas as caixas principais estiverem próximas, você precisará ter uma maneira mais inteligente de mover seus círculos nessa vizinhança.

Note que posso pensar em vários casos de esquina onde uma estratégia tão ingênua falhará espetacularmente. No entanto, apenas um ponto de partida.

Enquanto isso, espero que alguém tenha um algoritmo melhor.

curious_cat
fonte
11
Algo assim pode resolver o problema, pelo menos aproximadamente, em um círculo. (Isso pode ser feito facilmente usando contagens focais com um GIS.) Mas isso não resolverá o problema de múltiplos círculos.
whuber
@ whuber: Que tal resolver um círculo e depois largar todos os pontos que estão dentro desse círculo e depois repetir o algoritmo original? Você pode ver situações em que isso falharia?
11383
R=10,N=20 0,1 1,2,20,21,28.,29,30,31,32.,39.,40.28.,29,30,31,32.0 0,1 1,220,21,28.,29,3030,31,32.,39.,40.
@whuber: Verdade. Você está certo. Embora, dependendo da estrutura dos pontos de entrada em alguns casos (muitos?), As soluções gananciosas e não gananciosas possam ser idênticas ou próximas? Eu não sei.
Curious_cat
@ whuber: O problema parece principalmente nos limites. E se (um pouco como eu mencionei na minha resposta) se move a janela +Re -Rem seguida, coloca todas as soluções viáveis em uma pilha e seleciona entre eles. Por 1Dexemplo, no seu exemplo ao bater 28,29,30,31,32, ele deslizaria a janela até 18-28e 38-48procuraria todas as soluções viáveis. Então, dentro desses, pode-se procurar combinações máximas de obtenção de pontos. Não tem certeza se isso ajudaria? Estou tentando ver se meu algoritmo ingênuo pode ser recuperado? :)
curious_cat