1

我有一个包含多个字符串标签的主表：

["A", "B", "C", "D"]
["A", "C", "D", "G"]
["A", "F", "G", "H"]
["A", "B", "G", "H"]
...

当我创建一个新行并插入第一个标签（例如“A”）时，我想通过查看现有行来获得与之相关的最常见标签的建议。

换句话说，我想知道每个标签（例如“A”）的相关标签的频率，并获得按最频繁排序的相关标签列表。

例如：

"A".get_most_frequently_related_tags()
= {"G": 3, "B": 2, "C": 2, "H": 2}

我的方法是迭代主表并动态创建一个包含以下内容的新表：

[ tag, related_tag, freq ]
[ "A", "B", 2 ]
[ "A", "G", 3 ]
[ "A", "H", 2 ]
...

然后只选择带有标签“A”的行来提取有序的哈希[related_tag: freq]。

这是最好的方法吗？我不知道是否有更好的算法（或使用机器学习？）...

4

2 回答 2

1

我建议使用每个标签一行的映射，而不是每对一行（标签，相关标签）的新表，但是这一行将标签映射到所有相关标签（及其频率）的整个列表。

大多数编程语言在其标准库中都有一个标准“映射”：在 C++ 中，它是std::mapor std::unordered_map; 在 Java 中，它是接口java.util.Map，实现为java.util.HashMapor java.util.TreeMap；在 python 中，它是dict.

这是python中的解决方案。该映射是用 实现的collections.defaultdict，它将每个标签映射到一个collections.Counter，这是用来计算频率的 Python 工具。

from collections import Counter, defaultdict

table = [
    ["A", "B", "C", "D"],
    ["A", "C", "D", "G"],
    ["A", "F", "G", "H"],
    ["A", "B", "G", "H"],
]

def build_frequency_table(table):
    freqtable = defaultdict(Counter)
    for row in table:
        for tag in row:
            freqtable[tag].update(row)
    for c,freq in freqtable.items():
        del freq[c]
    return freqtable

freqtable = build_frequency_table(table)
print( freqtable )
# defaultdict(<class 'collections.Counter'>,
#   {'A': Counter({'G': 3, 'B': 2, 'C': 2, 'D': 2, 'H': 2, 'F': 1}),
#    'B': Counter({'A': 2, 'C': 1, 'D': 1, 'G': 1, 'H': 1}),
#    'C': Counter({'A': 2, 'D': 2, 'B': 1, 'G': 1}),
#    'D': Counter({'A': 2, 'C': 2, 'B': 1, 'G': 1}),
#    'G': Counter({'A': 3, 'H': 2, 'C': 1, 'D': 1, 'F': 1, 'B': 1}),
#    'F': Counter({'A': 1, 'G': 1, 'H': 1}),
#    'H': Counter({'A': 2, 'G': 2, 'F': 1, 'B': 1})})

print(freqtable['A'].most_common())
# [('G', 3), ('B', 2), ('C', 2), ('D', 2), ('H', 2), ('F', 1)]
于 2022-01-29T10:09:11.833 回答
0

我已经尝试在 C# 中找到解决方案。我不能在性能方面为这种方法辩护，但 1）它服务于目的（至少对于不太大的输入）；2) 我个人觉得这是一个有趣的挑战。

正如在Stef的回答中一样，创建了一个字典，可用于查找任何想要的标签，以查看所有标签的相关标签，按频率排序。

我已将字典创建放在扩展方法中：

public static IDictionary<string, List<(string Tag, int Count)>> AsRelatedTagWithFrequencyMap
    (this IEnumerable<IEnumerable<string>> relatedTags)
{
    return relatedTags
        .SelectMany(row => row
            .Select(targetTag =>
                (TargetTag: targetTag,
                RelatedTags: row.Where(tag => tag != targetTag))))
        .GroupBy(relations => relations.TargetTag)
        .ToDictionary(
            grouping => grouping.Key,
            grouping => grouping
                .SelectMany(relations => relations.RelatedTags)
                .GroupBy(relatedTag => relatedTag)
                .Select(grouping => (RelatedTag: grouping.Key, Count: grouping.Count()))
                .OrderByDescending(relatedTag => relatedTag.Count)
                .ToList());
}

它的用法如下：

var tagsUsedWithTags = new List<string[]>
{
    new[] { "A", "B", "C", "D" },
    new[] { "A", "C", "D", "G" },
    new[] { "A", "F", "G", "H" },
    new[] { "A", "B", "G", "H" }
};

var relatedTagsOfTag = tagsUsedWithTags.AsRelatedTagWithFrequencyMap();

打印字典内容：

foreach (var relation in relatedTagsOfTag)
{
    Console.WriteLine($"{relation.Key}: [ {string.Join(", ", relation.Value.Select(related => $"({related.Tag}: {related.Count})"))} ]");
}

A：[（G：3），（B：2），（C：2），（D：2），（H：2），（F：1）]
B：[（A：2），（C : 1), (D: 1), (G: 1), (H: 1) ]
C: [ (A: 2), (D: 2), (B: 1), (G: 1) ]
D : [ (A: 2), (C: 2), (B: 1), (G: 1) ]
F: [ (A: 1), (G: 1), (H: 1) ]
G: [ (A: 3), (H: 2), (C: 1), (D: 1), (F: 1), (B: 1) ]
H: [ (A: 2), (G: 2) , (F: 1), (B: 1)]

于 2022-01-29T16:36:45.953 回答