根据出现次数对数字进行分组？
Grouping numbers based on occurrences?
给定以下三个数字序列，我想弄清楚如何对数字进行分组以找到它们之间最接近的关系。
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]
我不能说哪个分组最 "correct"，但是所有这四个组合都找到了半正确分组数字的不同方法。我不是在寻找特定的分组 - 只是一个运行良好且易于理解的通用聚类算法。
我相信还有很多其他方法可以使用出现次数来对它们进行分组。对于这些，什么是好的基础分组算法？ Go 中的示例，Javascript 或 PHP 是首选。
你的三个序列中的每一个都可以理解为一个clique in a multigraph。在团内，每个顶点都与其他每个顶点相连。
下图表示您的示例案例，每个派系中的边分别为红色、蓝色和绿色。
正如您已经展示的那样，我们可以根据顶点对之间的边数对它们进行分类。在图中，我们可以看到四对顶点分别由两条边连接，另外四对顶点分别由一条边连接。
我们可以继续根据顶点出现的团数对顶点进行分类。在某种意义上，我们是根据顶点的连通性对顶点进行排序。出现在 k 团中的顶点可以被认为与出现在 k 团中的其他顶点具有相同的连接度。在图像中，我们看到三组顶点：顶点 3 出现在三个团中；顶点 1、2 和 4 分别出现在两个团中；顶点 5 出现在一个集团中。
下面的 Go 程序计算边分类和顶点分类。程序的输入在第一行包含顶点数 n 和团数 m。我们假设顶点的编号从 1 到 n。每个后续的 m 行输入都是一个 space-separated 属于一个团的顶点列表。因此，问题中给出的问题实例由这个输入表示：
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")
}
}
如前所述，它是关于派系的。如果你想要准确的答案，你将面临 NP-complete 的最大派系问题。因此，只有当您的符号（数字）的字母表具有合理的大小时，以下所有内容才有意义。在这种情况下，伪代码中针对最大派系问题的直截了当的优化算法将是
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 并可以使用输入数据。但是再一次，这种方法适用于合理大小的字母表（以及任何大小的输入数据）。
这个问题经常出现在分析销售数据的规则挖掘场景中。 （哪些东西是一起买的？所以在超市可以并排摆放）
我遇到的一个 class 算法是 Association Rule Learning. And one inherent step is finding frequent itemsets which matches your task. One algorithm is Apriori。但是搜索这些关键字时，您可以找到更多。
最好描述一下这样一个分组的目标。如果不是，我可能会尝试建议简单（如我所想）的方法，并且最简单。如果您需要计算大量分布广泛（如 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;
}
给定以下三个数字序列，我想弄清楚如何对数字进行分组以找到它们之间最接近的关系。
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]
我不能说哪个分组最 "correct"，但是所有这四个组合都找到了半正确分组数字的不同方法。我不是在寻找特定的分组 - 只是一个运行良好且易于理解的通用聚类算法。
我相信还有很多其他方法可以使用出现次数来对它们进行分组。对于这些，什么是好的基础分组算法？ Go 中的示例，Javascript 或 PHP 是首选。
你的三个序列中的每一个都可以理解为一个clique in a multigraph。在团内，每个顶点都与其他每个顶点相连。
下图表示您的示例案例，每个派系中的边分别为红色、蓝色和绿色。
正如您已经展示的那样，我们可以根据顶点对之间的边数对它们进行分类。在图中，我们可以看到四对顶点分别由两条边连接，另外四对顶点分别由一条边连接。
我们可以继续根据顶点出现的团数对顶点进行分类。在某种意义上，我们是根据顶点的连通性对顶点进行排序。出现在 k 团中的顶点可以被认为与出现在 k 团中的其他顶点具有相同的连接度。在图像中，我们看到三组顶点：顶点 3 出现在三个团中；顶点 1、2 和 4 分别出现在两个团中；顶点 5 出现在一个集团中。
下面的 Go 程序计算边分类和顶点分类。程序的输入在第一行包含顶点数 n 和团数 m。我们假设顶点的编号从 1 到 n。每个后续的 m 行输入都是一个 space-separated 属于一个团的顶点列表。因此，问题中给出的问题实例由这个输入表示：
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")
}
}
如前所述，它是关于派系的。如果你想要准确的答案，你将面临 NP-complete 的最大派系问题。因此，只有当您的符号（数字）的字母表具有合理的大小时，以下所有内容才有意义。在这种情况下，伪代码中针对最大派系问题的直截了当的优化算法将是
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 并可以使用输入数据。但是再一次，这种方法适用于合理大小的字母表（以及任何大小的输入数据）。
这个问题经常出现在分析销售数据的规则挖掘场景中。 （哪些东西是一起买的？所以在超市可以并排摆放）
我遇到的一个 class 算法是 Association Rule Learning. And one inherent step is finding frequent itemsets which matches your task. One algorithm is Apriori。但是搜索这些关键字时，您可以找到更多。
最好描述一下这样一个分组的目标。如果不是，我可能会尝试建议简单（如我所想）的方法，并且最简单。如果您需要计算大量分布广泛（如 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;
}