Algoritmo de “não classificação” / homogeneidade dos dados

8

Na tentativa de não reinventar uma roda, estou perguntando se alguém tem ideias sobre um algoritmo de homogeneidade de dados. Um breve exemplo:

Meus dados têm vários elementos, talvez como

  1. Número
  2. Cor
  3. Fruta
  4. Carta

Existem cerca de 100 desses elementos em uma matriz. O algoritmo precisa classificar os elementos para que quaisquer 2 entradas com o mesmo número sejam espaçadas uma da outra o máximo possível, e o mesmo com cores, frutas etc. Também seria bom se eu pudesse priorizar os elementos. Parece que você nunca chegaria a 100%, então você daria um número de passes para fazer, confira o resultado e tente mais passes.

Eu não ficaria surpreso se há algo aqui que simplesmente funciona que eu não tenho google-fu suficiente para encontrar.

ExoByte
fonte
Você já tentou algo como pesquisa genética ?
30711 David Weiser
3
Você escreve como um falante nativo de inglês, então trabalhe um pouco na redação. Remova a palavra "curtir" onde ela não pertence e aprimore suas frases em geral. Além disso, gostaria de dar um exemplo? Eu não entendi completamente sua pergunta.
Job
3
Exemplos são essenciais. Um caso de teste de unidade é crítico para esse tipo de coisa. Um parágrafo de texto não é um caso de teste.
31511 S.Lott

Respostas:

2

Isso meio que me incomodou por um tempo, então eu tive que vir ver se estava resolvido. Aqui está a minha ideia. Do zero, não é uma aplicação de nenhum algoritmo que eu conheço. Esse seria um algoritmo de força bruta bastante caro, mas deveria ser bastante eficaz. Supõe-se que você esteja lidando com o conjunto de dados realmente pequeno que você descreveu (100 linhas de 4 colunas) e esteja trabalhando em computadores modernos com memória RAM suficiente.

Visão geral : usamos um algoritmo recursivo em uma lista classificada para dispersar registros semelhantes à sua distância máxima dentro de registros semelhantes. Após cada chamada, todos os registros com o mesmo pai estão em sua distância máxima. A chamada superior inclui todos os registros. Por isso, desagrega de dentro para fora.

Estruturas de dados :

  • newIndexesé um array<integer>. O índice da matriz é o índice existente da linha. O valor será o novo índice, começa com -1
  • dataé um array<array<string>>. A chave é o índice, a matriz interna é uma representação de string dos valores em uma linha. Não precisa ser uma sequência se você tiver alguma maneira de agrupar seus dados. O primeiro elemento da matriz é aquele com o maior peso.

Classifique datapor ordem de peso. Classifique-o primeiro pela coluna com maior peso, dentro da coluna com o segundo maior peso, etc. O resultado é o inverso do que você deseja. Índice sequencialmente.

Aqui está o algoritmo (no código psudo).

        // siblingCount: On first call is the number of rows in the table,
    //    on recursive calls it is the number of elements with the same parent
    // index: the index of current row in `data` - starts 0
    // depth: The element index - starts 0
    void unsort(int siblingCount, int index, int depth)
    {
        int count = 1;
        string hash = concatColumns(index, depth + 1);
        while ((index + count < data.count) && (hash == concatColumns(index + count, depth + 1)))
        {
            count++;
        }

        if (depth < columnCount)
            unsort(count, index, depth);
        else if (index < data.count)
            unsort(count, index + count, 0);

        int spacing = siblingCount / count;

        for (int i = 0; i < count; i++)
        {
            var offset = 0;
            while ((newIndexes[index + i + offset] > -1) & (index + i + offset + 1 < newIndexes.count))
                offset++;

            if (newIndexes[index + i + offset] > -1) throw new Exception("Shouldn't happen.");

            newIndexes[index + i + offset] = index + spacing * i;
        }
    }

    string concatColumns(int index, int count) // returns count columns concatinated
    {
        // 1,1 = "1"
        // 1,2 = "1, blue"
        // 1,3 = "1, blue, apple"
        return "1, blue, apple";
    } 

Em seguida, aplique os newIndexes aos dados a serem não classificados.

Considerações sobre a abordagem: não testamos isso, mas o armazenamento dos novos Índices e a resolução de conflitos podem ser problemáticos, pois os primeiros índices são atribuídos com base em colunas menos significativas; portanto, se houver muitos conflitos, as colunas mais significativas poderão se agrupar. Pode-se tentar aplicar o deslocamento como positivo primeiro e depois negativo. Ou, possivelmente, faça esse tipo de inserção em uma lista vinculada, em vez de em uma matriz.

Jim McKeeth
fonte
Ah! Eu vejo muito o que você está recebendo aqui. Classifique e segregar com base no tamanho da cadeia de uniformidade. Se isso não funcionar, deve ser bem próximo. Obrigado por sua ajuda e limpeza na pergunta! Espero que eu tente fazer isso na próxima vez que precisar processar esse tipo de dados em setembro.
ExoByte 30/07/11
Deixe-me saber como isso funciona.
Jim McKeeth
4

Isso me lembra um algoritmo de rede que eu vi, a palavra-chave 'tkwikibrowser' 'TouchGraphWikiBrowser', onde os elementos são combinados com um tipo de elástico, mas são como ímãs do mesmo pol.

Eu não sei o que seria a mecânica, puxando no seu caso, mas talvez 'case' seja a palavra-chave certa: os elementos são colocados em um caso e são empurrados para longe da borda do caso e afastados um do outro , mais ainda, se eles tiverem vários atributos em comum.

Eles começam em posições aleatórias, movem-se dependendo da distância da parede e da distância de elementos similares, e buscam uma posição estável.

A fórmula para se afastar pode ser linear ou quadrática à distância, e você pode procurar uma boa fórmula ao vivo, manipulando os valores.

atualizar:

Para o poder de atração, você pode simplesmente assumir o inverso do poder de distração. Portanto, se 2 elementos não compartilharem um único atributo, essa seria a atração máxima.

Usuário desconhecido
fonte
OK, eu vou morder. Eu fiz uma pesquisa no Google no tkwikibrowser e não consegui nada. Você pode criar um link para mais informações?
21911 Jim McKeeth
Você está certo, desculpe, o nome não era TKWiki ..., mas TGWiki ... para TouchGraph, como aqui , mas eu só encontrei essa captura de tela, nenhuma demonstração funcional, onde os nós se movem como elásticos .
desconhecido usuário
3

Use uma ordem aleatória aleatória ou classifique por um hash dos dados concatenados: um bom hash fornece saídas altamente diferentes para entradas semelhantes; portanto, as entradas semelhantes em qualquer dimensão devem ser separadas.

Jon Purdy
fonte
1
Essa parece ser a solução mais fácil, mas agora estou realmente curioso para saber como isso funcionaria com dados do mundo real.
TheLQ
O problema é que, embora o hash semelhante seja diferente, o hash de linhas idênticas produziria o mesmo hash e, em seguida, classificaria como adjacente.
21711 Jim McKeeth
E haverá duplicatas exatas nos dados. Este pode ser um lugar interessante para começar.
ExoByte 29/07
@ Jim McKeeth: Você está certo. Obviamente, você também pode concatenar um índice para diferenciar linhas idênticas por um pequeno número de bits. Você também pode examinar curvas de ordem Z (obtidas trivialmente por intercalação de bits), que distribuem dados lineares espacialmente, de forma que os dados próximos permaneçam assim. Você está procurando uma permutação que produza o inverso disso.
31411 Jon Purdy