根据事件分组数字？
给出以下三个数字序列，我想弄清楚如何对数字进行分组以find它们之间最密切的关系。
1,2,3,4 4,3,5 2,1,3 ... 我不确定我要找的algorithm是什么，但是我们可以看到一些数字与其他数字的关系更强。
这些数字一起出现两次：
1 & 2 1 & 3 2 & 3 3 & 4
一起一次：
1 & 4 2 & 4 3 & 5 4 & 5
例如，我们可以看到1, 2, & 3之间必须有一个关系1, 2, & 3因为它们至less出现两次。 你也可以说3 & 4是密切相关的，因为它们也出现两次。 然而，该algorithm可能会select[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]
我不能说哪个分组是最“正确”的，但是这四个组合都能find不同的方式来半正确地分组数字。 我不是在寻找一个特定的分组 – 只是一个通用的集群algorithm，运行相当好，很容易理解。
我相信还有很多其他的方式来使用发生次数来分组。 什么将是一个很好的基本分组algorithm？ Go，Javascript或PHP中的示例是首选。
正如已经提到的那样，它是关于派系的。 如果你想要确切的答案，你将面临最大集团问题是NP完成。 所以下面所有的只有在你的符号（数字）的字母大小合理时才有意义。 在这种情况下，跨代转发，对于伪代码中的最大团问题将不是非常优化的algorithm
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是我select的语言，所以这里是实现
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和玩input数据。; 但再一次，这种方法是合理大小的字母表（和任何大小的input数据）。
你的三个序列中的每一个都可以被理解为多图中的一个集团 。 在一个派系内，每个顶点都连接到其他顶点。
下面的图表分别代表您的示例，每个分类中的边缘分别用红色，蓝色和绿色表示。
正如您已经表明的那样，我们可以根据它们之间的边的数量来对顶点对进行分类。 在图中，我们可以看到，四对顶点分别由两条边连接，另外四对顶点分别由一条边连接。
我们可以根据它们出现的派系的数量继续分类顶点。 在某种意义上，我们根据它们的连通性对顶点进行sorting。 出现在k派系中的一个顶点可以被认为与在k派系中出现的其他顶点的连接程度相同。 在图像中，我们看到三组顶点：顶点3出现在三个派系中; 顶点1,2和4分别出现在两个派系中; 顶点5出现在一个派系。
下面的Go程序计算边缘分类以及顶点分类。 程序的input在第一行包含顶点数n和小数m 。 我们假设顶点从1到n编号。 每个后续的m行input都是一个空格分隔的属于一个集团的顶点列表。 因此，问题中给出的问题实例是由这个input表示的：
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") } }
在分析销售数据时，这个问题经常出现在规则挖掘的背景下。 （哪些项目是一起购买的呢？所以他们可以在超市里放在一起）
我遇到的一类algorithm是关联规则学习 。 一个固有的步骤是find与您的任务相匹配的频繁项目集 。 一种algorithm是Apriori 。 但是在search这些关键字时可以find更多。
你描述这样一个分组的目标会更好。 如果没有，我可能会试图build议简单（我认为）的方法，并且最撒谎。 如果您需要计算大量的广泛传播（如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; }
