Группировка чисел на основе вхождений?

Question

Учитывая следующие три последовательности чисел, я хотел бы выяснить, как группировать числа, чтобы найти самые близкие отношения между ними.

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

Я не уверен, что алгоритм (ы) Я ищу званых, но мы можем увидеть более сильные отношения с некоторыми из чисел, чем с другими.

Эти цифры появляются вместе дважды:

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

Вместе раз:

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

Так, например, мы можем видеть, что должно быть отношения между 1, 2, & 3, так как все они появляются вместе, по крайней мере в два раза. Вы также можете сказать, что 3 & 4 тесно связаны, так как они также появляются дважды. Однако алгоритм может выбрать [1,2,3] (более [3,4]), так как это более крупная группировка (более включено).

Мы можем сформировать любой из следующих групп, если мы будем придерживаться число наиболее часто используемых вместе в группе:

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

Если дубликаты будут разрешены, вы могли бы даже в конечном итоге со следующими группами:

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

Я не могу сказать, какая группировка наиболее «правильная», но все четыре из этих комбо все находят разные способы полуправильной группировки чисел. Я не ищу определенную группу - просто общий алгоритм кластера, который работает достаточно хорошо и легко понять.

Уверен, что есть много других способов использовать число встречаемости, чтобы сгруппировать их. Каким будет хороший алгоритм группировки баз данных? Предпочтительны образцы в Go, Javascript или PHP.

Answer 1

Как уже упоминалось, i t о клике. Если вам нужен точный ответ, вы столкнетесь с проблемой максимальной клики, которая будет NP-полной. Итак, все ниже имеет смысл, только если алфавит ваших символов (цифр) имеет разумный размер. В этом случае смирительной вперед, не очень оптимизированный алгоритм для максимальной Clique задачи в псевдокоде будет

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 

Из-Go мой язык выбора здесь является реализация

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 
} 

И здесь вы можете см. его работы https://play.golang.org/p/ZiJfH4Q6GJ и играть с входными данными. Но еще раз, этот подход предназначен для разумного размера алфавита (и входных данных любого размера).

Answer 2

Каждая из трех последовательностей может быть понята как clique в multigraph. Внутри клики каждая вершина связана с каждой другой вершиной.

На следующем графике представлен пример с краями в каждой клике, окрашенной в красный, синий и зеленый цвета соответственно.

Как уже было показано, мы можем классифицировать пары вершин по числу ребер между ними. На иллюстрации мы видим, что четыре пары вершин связаны двумя ребрами, а четыре другие пары вершин связаны одним ребром.

Мы можем продолжить классификацию вершин в соответствии с количеством кликов, в которых они отображаются. В некотором смысле мы ранжируем вершины в соответствии с их связностью. Вершина, которая появляется в кликах k, может рассматриваться как связанная с той же степенью, что и другие вершины, которые появляются в кликах k. На изображении мы видим три группы вершин: вершина 3 появляется в трех кликах; вершины 1, 2 и 4 кажутся в двух кликах; вершина 5 появляется в одной клике.

В приведенной ниже программе Go вычисляется классификация ребер, а также классификация вершин. Вход в программу содержит в первой строке число вершин n и количество клик m.Предположим, что вершины нумеруются от 1 до n. Каждая из последующих строк ввода m представляет собой список вершин, принадлежащих клике, в пространстве. Таким образом, экземпляр проблема, данные в вопросе представлен этот вход:

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

Соответствующий выход:

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 

А вот программа 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 3

Эта проблема часто возникает в контексте разработки правил при анализе данных о продажах. (Какие предметы покупаются вместе? Поэтому их можно разместить рядом друг с другом в супермаркете)

Один класс алгоритмов, с которыми я столкнулся, - Association Rule Learning. И одним неотъемлемым шагом является поиск частых наборов предметов, который соответствует вашей задаче. Один алгоритм - Apriori. Но при поиске этих ключевых слов вы можете найти гораздо больше.

Answer 4

Было бы лучше, если бы вы описали цель такой группировки. Если нет, я могу попытаться предложить простые (как мне кажется) подход, и он будет наиболее ограниченным. Это не подходит, если вам нужно подсчитать огромное количество широко распространенных (например, 1, 999999, 31) или больших или неположительных чисел. вы можете изменить число наборов в позициях массива следующим образом:

|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 

здесь вы можете увидеть в строке +, что наиболее частой комбинацией является [3], то [1,2] и [4], а затем [5] , также можно указать и выделить cooccurence различных комбинаций

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