Группировка чисел на основе вхождений?
Учитывая следующие три последовательности чисел, я хотел бы выяснить, как группировать числа, чтобы найти самые близкие отношения между ними.
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.
Ответы
Ответ 1
Как уже упоминалось о клике. Если вам нужен точный ответ, вы столкнетесь с проблемой максимальной клики, которая будет NP-полной. Итак, все ниже имеет смысл, только если алфавит ваших символов (цифр) имеет разумный размер. В этом случае прорывный, не очень оптимизированный алгоритм для максимальной проблемы клики в псевдокоде будет
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 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 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 и воспроизводит входные данные. Но еще раз этот подход подходит для разумного размера алфавита (и входных данных любого размера).
Ответ 2
Каждая из трех последовательностей может быть понята как clique в multigraph. Внутри клики каждая вершина связана с каждой другой вершиной.
Следующий график представляет ваш пример с краями в каждой клике, цветной красный, синий и зеленый соответственно.
![Multigraph with five vertices and three cliques]()
Как вы уже показали, мы можем классифицировать пары вершин в соответствии с количеством ребер между ними. На иллюстрации мы видим, что четыре пары вершин связаны двумя ребрами, а четыре другие пары вершин связаны одним ребром.
Мы можем продолжить классификацию вершин в соответствии с количеством кликов, в которых они отображаются. В некотором смысле мы ранжируем вершины в соответствии с их связностью. Вершина, которая появляется в кликах k, может рассматриваться как связанная с той же степенью, что и другие вершины, которые появляются в k cliques. На изображении мы видим три группы вершин: вершина 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")
}
}
Ответ 3
Эта проблема часто возникает в контексте разработки правил при анализе данных о продажах. (Какие предметы покупаются вместе, поэтому их можно разместить рядом друг с другом в супермаркете)
Один класс алгоритмов, с которыми я столкнулся, - Обучение правилам ассоциации. И один неотъемлемый шаг - поиск частых наборов предметов, который соответствует вашей задаче. Один алгоритм Apriori. Но при поиске этих ключевых слов вы можете найти гораздо больше.
Ответ 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],
также вы можете указать и отличить кокурятельность различных комбинаций
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;
}
