Editar distância entre duas partições

17

Eu tenho duas partições de [1n] e estou procurando a distância de edição entre elas.

Com isso, desejo encontrar o número mínimo de transições únicas de um nó em um grupo diferente necessário para passar da partição A para a partição B.

Por exemplo, a distância de {0 1} {2 3} {4}dentro {0} {1} {2 3 4}seria dois

Após a pesquisa, deparei-me com este documento, mas a) não tenho certeza se eles estão levando em consideração a ordem dos grupos (algo com o qual não me importo) à distância b) não tenho certeza de como ele funciona ec) Não há referências.

Qualquer ajuda apreciada

zenna
fonte
5
Qual você consideraria a distância entre {0 1 2 3} e {0 1} {2 3}? Seria 2? Em segundo lugar, não vejo por que "gráficos" entram em cena. Parece que você tem duas partições de [n] e deseja calcular uma distância entre elas.
Suresh Venkat
Sim, seriam dois. De fato, essas são partições definidas nos nós de um gráfico (ou seja, uma partição de gráfico). Provavelmente isso não é importante para a solução, mas esse é o problema que estou tentando resolver, por isso mencionei.
Zenna
3
Se o gráfico for irrelevante, remova todas as referências a "gráficos" e "nós" da sua pergunta; não ajuda, distrai.
Jukka Suomela
A distância de edição não pode ser definida em termos da distância na estrutura da partição?
Tegiri Nenashi
@Tegiri - É de fato a distância geodésica na treliça dos partititons. Infelizmente, a computação dessa estrutura para qualquer conjunto de cardinalidade muito superior a 10 é intratável.
Zenn 31/08

Respostas:

21

Esse problema pode ser transformado no problema de atribuição , também conhecido como problema de correspondência bipartida ponderada máxima.

Observe primeiro que a distância de edição é igual ao número de elementos que precisam ser alterados de um conjunto para outro. Isso é igual ao número total de elementos menos o número de elementos que não precisam ser alterados. Portanto, encontrar o número mínimo de elementos que não mudam é equivalente a encontrar o número máximo de vértices que não mudam.

Deixe e B = { B 1 , B 2 , . . . , B l } ser partições de [ 1 , 2 , . . . , n ] . Além disso, sem perda de generalidade, deixar k l (permitida porque e d i tA={A1,A2,...,Ak}B={B1,B2,...,Bl}[1,2,...,n]kl ). Então deixe B l + 1 , B l + 2 , ..., B k todos os conjuntos vazios. Então, o número máximo de vértices que não são alterados é:edit(A,B)=edit(B,A)Bl+1Bl+2Bk

maxfi=1k|AiBf(i)|

onde é uma permutação de .[ 1 , 2 , . . . , K ]f[1,2,...,k]

Esse é exatamente o problema de atribuição em que os vértices são , ..., , , ..., e as arestas são pares com peso. Isso pode ser resolvido no tempo .A k B 1 B k ( A i , B j ) | A iB j | O ( | V | 2 log | V | + | V | | E | )A1AkB1Bk(Ai,Bj)|AiBj|O(|V|2log|V|+|V||E|)

bbejot
fonte
Você poderia nomear o algoritmo, o que dá complexidade a esse tempo, por favor?
D-503
Acredito que @bbejot está se referindo ao algoritmo sucessivo de caminho mais curto (com a sub-rotina Dijkstra implementada usando pilhas de fibonacci).
19419 Wei
Levei muito tempo para analisar isso porque não sou uma pessoa de matemática, mas obrigado. Passei muito tempo pesquisando e essa foi a única coisa que pude encontrar que mostrou como converter o problema da distância da partição no problema de atribuição - ou em qualquer algoritmo que eu pudesse chamar de uma biblioteca Python. (A parte mais difícil para mim foi descobrir como usar scipy.optimize.linear_sum_assignment e, em seguida, para configurar as matrizes com base nestas instruções.)
Sigfried
Eu precisava tornar os pesos negativos. Caso contrário, scipy.optimize.linear_sum_assignment me fornecerá 0 para tudo.
Sigfried
2

Veja o PDF deste artigo

http://www.ploscompbiol.org/article/info:doi/10.1371/journal.pcbi.0030160

A definição da distância de edição é exatamente o que você precisa, eu acho. A partição 'referência' seria (arbitrária) uma das suas duas partições, a outra seria simplesmente a outra. Também contém citações relevantes.

Best, Rob

Roubar
fonte
Obrigado Rob. No entanto, a menos que esteja faltando alguma coisa, essa é uma distância de edição definida em termos de movimentos de divisão e mesclagem. Estes são bem estudados e, como o artigo indica, a variação da informação é uma medida teórica da informação. No entanto, estou interessado em transições de movimento de elemento único.
Zenna 31/08/11
1

Ideia irritadiça da manhã de domingo que pode ou não estar correta:

Wlog, seja a partição com mais conjuntos, a outra. Primeiro, atribua nomes diferentes aos pares aos seus conjuntos . Em seguida, encontre a melhor nomenclatura para os conjuntos pelas seguintes regras:P 2 n 1 ( S ) Σ P 1 n 2 ( S ) P 2P1P2n1(S)ΣP1n2(S)P2

  • S P 2 S S ' S 'P 1n2(S):=n1(S) para com máximo entre todos os ; escolha aquele que criar o mínimo de conflitos, se várias opções forem possíveis.SP2SSSP1
  • Se agora para alguns , atribua aquele que compartilha menos elementos com , o nome do conjunto em ele compartilha o segundo maior número de elementos, ou seja, compete pelo nome do conjunto.S S S , n 1 ( S ) = n 2 ( S ) P 1n2(S)=n2(S)SSS,n1 1(S)=n2(S)P1 1
  • Se a regra anterior não puder ser aplicada, verifique se os dois conjuntos podem competir pelo nome de outros conjuntos com os quais compartilham menos elementos (eles ainda podem ter mais elementos de algum que os conjuntos aos quais foi atribuído seu nome!). Em caso afirmativo, atribua esse nome ao de que compartilha mais elementos com o respectivo conjunto cujo nome eles podem competir; o outro mantém o nome anteriormente conflitante. S , S SP1 1S,S
  • Itere este procedimento até que todos os conflitos sejam resolvidos. Como não possui menos conjuntos que , existem nomes suficientes.P 2P1 1P2

Agora, você pode considerar as cadeias de bits de seus elementos em qualquer partição, ou seja, e ( com ). Então, a quantidade desejada é , ou seja, a distância de Hamming entre as seqüências de bits.w 2 = N 2 ( 1 ) n 2 ( n ) n j ( i ) = n j ( S ) , i S P j d H ( w 1 , w 2 )W1 1=n1 1(1 1)n1 1(n)W2=n2(1 1)n2(n)nj(Eu)=nj(S),EuSPjdH(W1 1,W2)

Rafael
fonte