algorithm - grupo - ¿Agrupa números basados en ocurrencias?

option title attribute

Question

Dadas las siguientes tres secuencias de números, me gustaría descubrir cómo agrupar los números para encontrar las relaciones más cercanas entre ellos.

1,2,3,4
4,3,5
2,1,3
...

No estoy seguro de cómo se llaman los algoritmos que estoy buscando, pero podemos ver relaciones más fuertes con algunos de los números que con otros.

Estos números aparecen juntos dos veces:

1 & 2
1 & 3
2 & 3
3 & 4

Juntos una vez:

1 & 4
2 & 4
3 & 5
4 & 5

Entonces, por ejemplo, podemos ver que debe haber una relación entre 1, 2, & 3 ya que todos aparecen juntos al menos dos veces. También podría decir que 3 & 4 están estrechamente relacionados ya que también aparecen dos veces. Sin embargo, el algoritmo podría elegir [1,2,3] (más de [3,4] ) ya que es una agrupación más grande (más inclusiva).

Podemos formar cualquiera de las siguientes agrupaciones si pegamos los números usados ​​con mayor frecuencia en un grupo:

[1,2,3] & [4,5]
[1,2]   & [3,4]   & [5]
[1,2]   & [3,4,5]
[1,2]   & [3,4]   & [5]

Si se permiten duplicados, incluso podría terminar con los siguientes grupos:

[1,2,3,4] [1,2,3] [3,4] [5]

No puedo decir qué agrupación es más "correcta", pero los cuatro de estos combos encuentran formas diferentes de agrupar los números de forma semi-correcta. No estoy buscando una agrupación específica, solo un algoritmo de clúster general que funciona bastante bien y es fácil de entender.

Estoy seguro de que hay muchas otras maneras de usar el conteo de ocurrencias para agruparlos también. ¿Cuál sería un buen algoritmo de agrupación base para estos? Se prefieren las muestras en Go, Javascript o PHP.

Answer 1

Cada una de sus tres secuencias se puede entender como una clique en un multigraph . Dentro de una camarilla, cada vértice está conectado a cada otro vértice.

El siguiente gráfico representa su caso de muestra con los bordes en cada camarilla de color rojo, azul y verde, respectivamente.

Como ya lo ha demostrado, podemos clasificar pares de vértices de acuerdo con el número de bordes entre ellos. En la ilustración, podemos ver que cuatro pares de vértices están conectados por dos bordes cada uno, y otros cuatro pares de vértices están conectados por un borde cada uno.

Podemos continuar clasificando vértices según la cantidad de camarillas en que aparecen. En cierto sentido, estamos clasificando vértices según su conexión. Se puede pensar que un vértice que aparece en k cliques está conectado en el mismo grado que otros vértices que aparecen en k cliques. En la imagen, vemos tres grupos de vértices: el vértice 3 aparece en tres cliques; los vértices 1, 2 y 4 aparecen en dos cliques; el vértice 5 aparece en una camarilla.

El programa Go a continuación calcula la clasificación de borde y la clasificación de vértices. La entrada al programa contiene, en la primera línea, el número de vértices n el número de cliques m . Suponemos que los vértices están numerados de 1 a n . Cada una de las siguientes líneas de entrada es una lista de vértices separados por espacios que pertenecen a una camarilla. Por lo tanto, la instancia de problema dada en la pregunta está representada por esta entrada:

5 3
1 2 3 4
4 3 5
2 1 3

El resultado correspondiente es:

Number of edges between pairs of vertices:
    2 edges: (1, 2) (1, 3) (2, 3) (3, 4)
    1 edge:  (1, 4) (2, 4) (3, 5) (4, 5)

Number of cliques in which a vertex appears:
    3 cliques: 3
    2 cliques: 1 2 4
    1 clique:  5

Y aquí está el programa Go:

package main

import (
        "bufio"
        "fmt"
        "os"
        "strconv"
        "strings"
)

func main() {
        // Set up input and output.
        reader := bufio.NewReader(os.Stdin)
        writer := bufio.NewWriter(os.Stdout)
        defer writer.Flush()

        // Get the number of vertices and number of cliques from the first line.
        line, err := reader.ReadString(''/n'')
        if err != nil {
                fmt.Fprintf(os.Stderr, "Error reading first line: %s/n", err)
                return
        }
        var numVertices, numCliques int
        numScanned, err := fmt.Sscanf(line, "%d %d", &numVertices, &numCliques)
        if numScanned != 2 || err != nil {
                fmt.Fprintf(os.Stderr, "Error parsing input parameters: %s/n", err)   
                return
        }

        // Initialize the edge counts and vertex counts.
        edgeCounts := make([][]int, numVertices+1)
        for u := 1; u <= numVertices; u++ {
                edgeCounts[u] = make([]int, numVertices+1)
        }
        vertexCounts := make([]int, numVertices+1)

        // Read each clique and update the edge counts.
        for c := 0; c < numCliques; c++ {
                line, err = reader.ReadString(''/n'')
                if err != nil {
                        fmt.Fprintf(os.Stderr, "Error reading clique: %s/n", err)
                        return
                }
                tokens := strings.Split(strings.TrimSpace(line), " ")
                clique := make([]int, len(tokens))
                for i, token := range tokens {
                        u, err := strconv.Atoi(token)
                        if err != nil {
                                fmt.Fprintf(os.Stderr, "Atoi error: %s/n", err)
                                return
                        }
                        vertexCounts[u]++
                        clique[i] = u
                        for j := 0; j < i; j++ {
                                v := clique[j]
                                edgeCounts[u][v]++
                                edgeCounts[v][u]++
                        }
                }
        }

        // Compute the number of edges between each pair of vertices.
        count2edges := make([][][]int, numCliques+1)
        for u := 1; u < numVertices; u++ {
                for v := u + 1; v <= numVertices; v++ {
                        count := edgeCounts[u][v]
                        count2edges[count] = append(count2edges[count],
                                []int{u, v})
                }
        }
        writer.WriteString("Number of edges between pairs of vertices:/n")
        for count := numCliques; count >= 1; count-- {
                edges := count2edges[count]
                if len(edges) == 0 {
                        continue
                }
                label := "edge"
                if count > 1 {
                        label += "s:"
                } else {
                        label += ": "
                }
                writer.WriteString(fmt.Sprintf("%5d %s", count, label))
                for _, edge := range edges {
                        writer.WriteString(fmt.Sprintf(" (%d, %d)",
                                edge[0], edge[1]))
                }
                writer.WriteString("/n")
        }

        // Group vertices according to the number of clique memberships.
        count2vertices := make([][]int, numCliques+1)
        for u := 1; u <= numVertices; u++ {
                count := vertexCounts[u]
                count2vertices[count] = append(count2vertices[count], u)
        }
        writer.WriteString("/nNumber of cliques in which a vertex appears:/n")
        for count := numCliques; count >= 1; count-- {
                vertices := count2vertices[count]
                if len(vertices) == 0 {
                        continue
                }
                label := "clique"
                if count > 1 {
                        label += "s:"
                } else {
                        label += ": "
                }
                writer.WriteString(fmt.Sprintf("%5d %s", count, label))
                for _, u := range vertices {
                        writer.WriteString(fmt.Sprintf(" %d", u))
                }
                writer.WriteString("/n")
        }
}

Answer 2

Como ya se mencionó, se trata de camarilla. Si quiere una respuesta exacta, se enfrentará al Problema de cliqueo máximo, que es NP-completo. Entonces, todo lo que sigue tiene sentido solo si el alfabeto de sus símbolos (números) tiene un tamaño razonable. En este caso, el algoritmo de estrecho avance, no muy optimizado para el Problema Máximo de la Camada en el pseudo-código sería

Function Main
    Cm ← ∅                   // the maximum clique
    Clique(∅,V)              // V vertices set
    return Cm
End function Main

Function Clique(set C, set P) // C the current clique, P candidat set
    if (|C| > |Cm|) then
        Cm ← C
    End if
    if (|C|+|P|>|Cm|)then
        for all p ∈ P in predetermined order, do
            P ← P / {p}
            Cp ←C ∪ {p}
            Pp ←P ∩ N(p)        //N(p) set of the vertices adjacent to p
            Clique(Cp,Pp)
        End for
    End if
End function Clique

Debido a Go es mi lenguaje de elección aquí es la implementación

package main

import (
    "bufio"
    "fmt"
    "sort"
    "strconv"
    "strings"
)

var adjmatrix map[int]map[int]int = make(map[int]map[int]int)
var Cm []int = make([]int, 0)
var frequency int


//For filter
type resoult [][]int
var res resoult
var filter map[int]bool = make(map[int]bool)
var bf int
//For filter


//That''s for sorting
func (r resoult) Less(i, j int) bool {
    return len(r[i]) > len(r[j])
}

func (r resoult) Swap(i, j int) {
    r[i], r[j] = r[j], r[i]
}

func (r resoult) Len() int {
    return len(r)
}
//That''s for sorting


//Work done here
func Clique(C []int, P map[int]bool) {
    if len(C) >= len(Cm) {

        Cm = make([]int, len(C))
        copy(Cm, C)
    }
    if len(C)+len(P) >= len(Cm) {
        for k, _ := range P {
            delete(P, k)
            Cp := make([]int, len(C)+1)
            copy(Cp, append(C, k))
            Pp := make(map[int]bool)
            for n, m := range adjmatrix[k] {
                _, ok := P[n]
                if ok && m >= frequency {
                    Pp[n] = true
                }
            }
            Clique(Cp, Pp)

            res = append(res, Cp)
            //Cleanup resoult
            bf := 0
            for _, v := range Cp {
                bf += 1 << uint(v)
            }
            _, ok := filter[bf]
            if !ok {
                filter[bf] = true
                res = append(res, Cp)
            }
            //Cleanup resoult
        }
    }
}
//Work done here

func main() {
    var toks []string
    var numbers []int
    var number int


//Input parsing
    StrReader := strings.NewReader(`1,2,3
4,3,5
4,1,6
4,2,7
4,1,7
2,1,3
5,1,2
3,6`)
    scanner := bufio.NewScanner(StrReader)
    for scanner.Scan() {
        toks = strings.Split(scanner.Text(), ",")
        numbers = []int{}
        for _, v := range toks {
            number, _ = strconv.Atoi(v)
            numbers = append(numbers, number)

        }
        for k, v := range numbers {
            for _, m := range numbers[k:] {
                _, ok := adjmatrix[v]
                if !ok {
                    adjmatrix[v] = make(map[int]int)
                }
                _, ok = adjmatrix[m]
                if !ok {
                    adjmatrix[m] = make(map[int]int)
                }
                if m != v {
                    adjmatrix[v][m]++
                    adjmatrix[m][v]++
                    if adjmatrix[v][m] > frequency {
                        frequency = adjmatrix[v][m]
                    }
                }

            }
        }
    }
    //Input parsing

    P1 := make(map[int]bool)


    //Iterating for frequency of appearance in group
    for ; frequency > 0; frequency-- {
        for k, _ := range adjmatrix {
            P1[k] = true
        }
        Cm = make([]int, 0)
        res = make(resoult, 0)
        Clique(make([]int, 0), P1)
        sort.Sort(res)
        fmt.Print(frequency, "x-times ", res, " ")
    }
    //Iterating for frequency of appearing together
}

Y aquí puedes ver que funciona https://play.golang.org/p/ZiJfH4Q6GJ y jugar con datos de entrada. Pero una vez más, este enfoque es para un alfabeto de tamaño razonable (y datos de entrada de cualquier tamaño).

Answer 3

Este problema a menudo surge en el contexto de minería de reglas al analizar datos de ventas. (¿Qué artículos se compran juntos? Para que puedan colocarse uno al lado del otro en el supermercado)

Una clase de algoritmos que encontré es el aprendizaje de reglas de asociación . Y un paso inherente es encontrar conjuntos de elementos frecuentes que coincidan con su tarea. Un algoritmo es Apriori . Pero puedes encontrar mucho más cuando buscas esas palabras clave.

Answer 4

Sería mejor que describa el objetivo de dicha agrupación. Si no, puedo intentar sugerir el enfoque simple (como creo), y lo más limeted. No es adecuado si necesita contar una gran cantidad de números ampliados (como 1, 999999, 31) o grandes o no positivos. puede reorganizar los conjuntos de números en posiciones de arreglo de la siguiente manera:

  |1|2|3|4|5|6|  - numers as array positions
==============
*1|1|1|1|1|0|0| *1     
*2|0|0|1|1|1|0| *2   
*4|1|1|1|0|0|0| *4
==============
 +|2|2|3|2|1|0  - just a counters of occurence
 *|5|5|7|3|2|0  - so for first column number 1 mask will be: 1*1+1*4 = 5 

aquí puedes ver en + fila que la combinación más frecuente es [3], luego [1,2] y [4] y luego [5], también puedes indicar y distinguir la coocurrencia de diferentes combinaciones

    function grps(a) {
      var r = [];
      var sum = []; var mask = [];
      var max = 0;
      var val;
      for (i=0; i < a.length; i++) {
        for (j=0; j < a[i].length; j++) {
          val = a[i][j]; 
          //r[i][val] = 1;
          sum[val] = sum[val]?sum[val]+1:1; 
          mask[val] = mask[val]?mask[val]+Math.pow(2, i):1;
          if (val > max) { max = val; }
        }
      }
      for (j = 0; j < max; j++){
        for (i = 0; i < max; i++){            
          r[sum[j]][mask[j]] = j;
        }
      }
      return r;
    }