Pytanie Grupowanie liczb na podstawie wystąpień?


Biorąc pod uwagę następujące trzy sekwencje liczb, chciałbym dowiedzieć się, jak pogrupować liczby, aby znaleźć najbliższe relacje między nimi.

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

Nie jestem pewien, do jakiego algorytmu (ów) szukam, ale widzimy silniejsze relacje z niektórymi liczbami niż z innymi.

Te liczby pojawiają się razem dwa razy:

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

Razem raz:

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

Na przykład widzimy, że musi istnieć relacja między 1, 2, & 3 ponieważ wszystkie pojawiają się razem co najmniej dwa razy. Możesz też tak powiedzieć 3 & 4 są blisko spokrewnione, ponieważ pojawiają się również dwukrotnie. Jednak algorytm może wybrać [1,2,3] (koniec [3,4]), ponieważ jest to większa grupa (więcej).

Możemy utworzyć dowolne z następujących grup, jeśli najczęściej używamy numerów w grupie:

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

Jeśli duplikaty są dozwolone, możesz nawet skończyć z następującymi grupami:

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

Nie mogę powiedzieć, które grupowanie jest najbardziej "poprawne", ale wszystkie cztery z tych kombinacji znajdują różne sposoby na pół-poprawne grupowanie liczb. Nie szukam konkretnego ugrupowania - po prostu ogólny algorytm klastra, który działa dość dobrze i jest łatwy do zrozumienia.

Jestem pewien, że istnieje wiele innych sposobów wykorzystania liczby wystąpień do ich grupowania. Jaki byłby dobry algorytm grupowania bazowego? Preferowane są sample w Go, Javascript lub PHP.


34
2018-04-18 17:53


pochodzenie


Nazywa się to klastrem korelacyjnym. Utwórz wykres o numerach 1 .. 5 jako węzłach, zważ krawędzie, ile razy para pojawi się razem. Jestem pewien, że istnieją algorytmy, ale nie jest to tak uporządkowany i dobrze zdefiniowany problem. - Edward Doolittle
Nie śledzę, jak przybywasz do ostatecznego wyjścia. Mówisz, że "może wytworzyć dowolne z poniższych ugrupowań"; który jest najbardziej poprawny i dlaczego? Czy naprawdę chcesz algorytmu, który może arbitralnie wygenerować jeden z 4 sprzecznych wyników? - Patrick M
Myślę, że to interesujące pytanie, ale jest bardzo niejasne. Twoje dane wejściowe wydają się być serią list całkowitych o różnych rozmiarach. Czym dokładnie jest wynik, którego szukasz? Drzewo liczb, kolejna seria list, ile razy każda liczba może pojawić się na wyjściu itp.? - Elliot Nelson
Musisz podać swoje dane wejściowe i pożądane dane nieco bardziej formalnie, zanim uzyskasz użyteczną odpowiedź. - Asad Saeeduddin
W swoim ostatnim przykładzie, możesz wyjaśnić, co dokładnie masz na myśli przez , operator? Wydaje się, że nie używasz tego, żeby oznaczać, co zwykle oznacza. Wygląda na to, że używasz , oznacza OR, które zwykle jest reprezentowane przez symbol | lub + - slebetman


Odpowiedzi:


Jak już wspomniano, chodzi o kliszę. Jeśli chcesz uzyskać dokładną odpowiedź, napotkasz problem maksymalnego kliknięcia, który jest NP-zupełny. Więc wszystkie poniżej mają sens tylko wtedy, gdy alfabet twoich symboli (liczb) ma rozsądny rozmiar. W tym przypadku nie byłoby optymalnego algorytmu dla Maximum Clique Problem w pseudo-kodzie

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

Ponieważ "Go" jest moim językiem wyboru, jest to implementacja

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
}

I tutaj możesz zobaczyć, że to działa https://play.golang.org/p/ZiJfH4Q6GJ i baw się danymi wejściowymi. Ale jeszcze raz podejście to dotyczy alfabetu o rozsądnej wielkości (i danych wejściowych dowolnej wielkości).


10
2018-04-23 00:50



To wygląda na odpowiedź, której szukałem. Może to trochę za mało (pozwalając 1&2 pokazywać się w koderze 3x, 2x i 1x), ale jest to bardzo ładny algorytm. - Xeoncross
@Xeoncross Dodałem trochę filtra kwitnienia, by trochę posprzątać play.golang.org/p/ZiJfH4Q6GJ I oczywiście możesz wybrać własną reprezentację wyników. - Uvelichitel


Każda z twoich trzech sekwencji może być rozumiana jako klika w multigraf. Wewnątrz kliki każdy wierzchołek jest połączony z każdym innym wierzchołkiem.

Poniższy wykres przedstawia przypadek próbki z krawędziami w każdym klika w kolorze czerwonym, niebieskim i zielonym, odpowiednio.

Multigraph with five vertices and three cliques

Jak już pokazano, możemy sklasyfikować pary wierzchołków zgodnie z liczbą krawędzi między nimi. Na ilustracji widać, że cztery pary wierzchołków są połączone po dwiema krawędziami, a cztery pozostałe pary wierzchołków są połączone po jednej krawędzi.

Możemy dalej klasyfikować wierzchołki zgodnie z liczbą kliknięć, w których się pojawiają. W pewnym sensie pozycjonujemy wierzchołki zgodnie z ich połączeniem. Werteks, który pojawia się w k klik można uważać za połączone z tym samym stopniem, co inne wierzchołki, które się pojawiają k klik. Na obrazie widzimy trzy grupy wierzchołków: wierzchołek 3 pojawia się w trzech klikach; wierzchołki 1, 2 i 4 każda występują w dwóch klikach; wierzchołek 5 pojawia się w jednej klikce.

Poniższy program Go oblicza klasyfikację krawędzi oraz klasyfikację wierzchołków. Dane wejściowe do programu zawierają, w pierwszym wierszu, liczbę wierzchołków n i liczba klik m. Zakładamy, że wierzchołki są ponumerowane od 1 do n. Każdy z kolejnych m linie wejściowe to rozdzielona spacjami lista wierzchołków należących do kliki. Tak więc instancja problemu podana w pytaniu jest reprezentowana przez to wejście:

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

Odpowiadający wynik to:

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

A oto program 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")
        }
}

31
2018-04-22 02:28



"W pewnym sensie pozycjonujemy wierzchołki zgodnie z ich połączeniem"... Podczas gdy jest to dobre pokrewne badanie - w rzeczywistości nie zajmuje się problemem grupowania danych wejściowych - po prostu oblicza meta-dane dotyczące danych wejściowych, które może pomóc w rzeczywistym grupowaniu / klastrach. To świetny start (+1), ale rozważ następujące dane wejściowe. - Xeoncross


Problem ten często pojawia się w kontekście wydobywania reguł przy analizie danych sprzedażowych. (Które przedmioty są kupowane razem? Więc mogą być umieszczone obok siebie w supermarkecie)

Jedną z klas algorytmów, które spotkałem, jest Nauka o zasadach stowarzyszenia. I nieodłącznym krokiem jest znalezienie częste zestawy przedmiotów który pasuje do twojego zadania. Jest jeden algorytm Apriori. Ale można znaleźć o wiele więcej podczas wyszukiwania tych słów kluczowych.


3
2018-04-23 08:14





Byłoby lepiej, gdybyś opisał cel takiego grupowania. Jeśli nie, mogę spróbować zasugerować podejście simples (jak sądzę) i thow większość limeted. Nie nadaje się, jeśli trzeba liczyć ogromną ilość szeroko rozłożonych (np. 1, 999999, 31) lub dużych lub niepozostawiających numerów. możesz zmienić układ liczb w pozycjach tablicowych, jak na przykład:

  |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 

tutaj możesz zobaczyć w wierszu +, że najczęściej używana kombinacja to [3], a następnie [1,2] i [4], a następnie [5], możesz także wskazać i odróżnić koincydencję różnych kombinacji

    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;
    }

1
2018-04-27 09:59