获取具有最多共同项的两个实例

Question

获取具有最多共同项的两个实例

3

我正试图分析一组卡车及其携带物品的数据库，以找出哪两辆卡车最相似（即共享最多物品的卡车）。我有一个类似于这样的CSV文件：

truck_id | item_id
13       | 85394 *
16       | 294 *
13       | 294 *
89       | 3115
89       | 85394
13       | 294
16       | 85394 *
13       | 3115

在上面的例子中，16和13是最相似的货车，因为它们都有 294 和 85394 两个属性。

整个代码太长，所以我提供伪代码来解释我的操作：

truck_items = {}

#1
loop over the csv:
    add to truck_items a truck_id and an ARRAY with the items each truck has

#2
go over each truck in the truck_items dictionary, and compare their array to all other arrays
to get the count of similar items

#3
create a 'most_similar' key in the dictionary.

#4
check in most_similar what are the two trucks with most similarity.

那么最终我会得到像这样的东西：

{
  13: [16, 2] // truck_1_id: [truck_2_id, number_similar_items]
  89: ...
}

我知道这不是最有效的方法，因为我会多次遍历列表，这样做并不好。是否有更有效的方法？

- uber

3个回答

1

使用groupby来收集给定卡车的所有记录。对于每个组，制作一个零件编号的集合。创建一个新的数据框架来存储这些数据：

truck_id | items
13       | {85394, 294, 3115}
16       | {294, 85394}
89       | {3115, 85394}

现在你需要将这个DF与自身进行完整的叉积；过滤掉自引用和重复项（例如13-16和16-13）。如果你使用truck_id_left < truck_id_right进行乘积（具体实现语法取决于你使用的包），你只会得到唯一的对。在这些卡车对中，只需取其项目的交集即可。

trucks | items
(13, 16)       | {85394, 294}
(13, 89)       | {3115}
(16, 89)       | {85394}

然后在该交叉点上找到具有max值的行。

你能处理这些步骤吗？它们都包含在PANDAS教程中。

- Prune

2

如果OP不使用pandas或者不想用pandas去完成一个微不足道的任务，他们可以通过defaultdict(set)来实现相同的功能（所以只用内置工具：collections.defaultdict和itertools.product），而且可能需要更少的代码行数（甚至在数据库查询层面）。 - DeepSpace

嗯...这是 len，对于任何序列类型都是如此。 - Prune

-1

这里有一个看起来可能有效的解决方案：

我正在使用pandas作为我的主要数据容器，这样做可以使这类事情更容易。

import pandas as pd
from collections import Counter

这里我正在创建一个类似的数据集

#creating toy data
df = pd.DataFrame({'truck_id':[1,1,2,2,2,3,3],'item_id':[1,7,1,7,5,2,2]})

看起来像这样

   item_id  truck_id
0        1         1
1        7         1
2        1         2
3        7         2
4        5         2
5        2         3
6        2         3

我正在重新格式化它，为每辆卡车列出物品清单

#making it so each row is a truck, and the value is a list of items
df = df.groupby('truck_id')['item_id'].apply(list)

看起来像这样：

truck_id
1       [1, 7]
2    [1, 7, 5]
3       [2, 2]

现在我正在创建一个函数，给定一个类似于之前的数据框，计算两辆卡车上相似物品的数量。

def get_num_similar(df, id0, id1):
    #drops duplicates from each truck, so there's only one of each item in each truck
    #combining those lists together, so it's a list of items in both trucks
    comp = [*list(set(df.loc[id0])), *list(set(df.loc[id1]))]

    #getting how many items of each exist (should be 1 or 2)
    quants = dict(Counter(comp))

    #getting how many similar items are carried
    num_similar = len([quant for quant in quants.values() if quant > 1])

    return num_similar

运行这个：

print(get_num_similar(df, 1, 2))

输出结果为2，非常准确。现在只需迭代要分析的所有卡车组，就可以计算出哪些卡车共享最多的物品。

- Warlax56

请注意，这可能不是完美的，您可以直接在pandas中进行相似性计数，这将更快。尽管如此，考虑到交通部门的速度，我认为这个解决方案可能还不错。 - Warlax56

无论如何，这并没有回答问题。你提供了一个接受id0和id1作为参数的函数，而OP问的是如何找到这些id0和id1。 - DeepSpace

2

你的高评分很有道理。我没有意识到这是一场比赛，你应该休息一下。此外，它确实可以运行；我只是说它可能需要改进。"可能可以工作"这种说法非常被动攻击性，也不必要。这是一个完全自愿的、社区为基础的网站；像那样的负面评论是不应该存在的。请删除它，我也会删除我的评论。 - Warlax56

此外，不用说，“可能有效”是指“可能适用于操作者的使用情况”。 - Warlax56

SO是一个问答网站。发布答案的全部意义在于它对OP特定的用例是有效的（而不是可能有效的）。我从未写过这个答案是糟糕的或者与“竞争”相关的任何东西，只是质疑你的写作：“似乎它可能有效”。如果它有效，为什么还要提到它“可能”有效呢？ - DeepSpace

整个项目都是用伪代码提供的，这意味着我无法保证它在操作者的使用情况下能否正常工作，而且问题的语气有些随意，所以我的回答也是如此。此外，这并不是 stack overflow 的全部意义。Stack overflow 的目的是成为一个高质量答案的存储库，这些答案易于参考和理解。虽然这是问答的产物，但问答并不是 stack overflow 的全部。如果我的回答让您感到不满，我很抱歉，但简短、精英主义的评论是这个网站上普遍存在的问题，“可能有效”的评论就是其中之一。 - Warlax56

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- DeepSpace · Accepted Answer

非pandas解决方案，利用内置工具如collections.defaultdict（可选）和itertools.product（也是可选的，但如果数据集足够大，将帮助您将一些计算/循环推向C级别，这将有益处）。

我认为逻辑本身就是不言自明的。

from collections import defaultdict
from itertools import product

trucks = [
    (13, 294),
    (13, 294),
    (13, 3115),
    (13, 85394),
    (16, 294),
    (16, 85394),
    (89, 3115),
    (89, 85394),
]

d = defaultdict(set)
for truck, load in trucks:
    d[truck].add(load)


li = [({'truck': k1, 'items': v1},
       {'truck': k2, 'items': v2})
       for (k1, v1), (k2, v2) in product(d.items(), repeat=2)
       if k1 != k2]

truck_1_data, truck_2_data = max(li, key=lambda e: len(e[0]['items'] & e[1]['items']))
print(truck_1_data['truck'], truck_2_data['truck'])

输出

13 16

可以说更易读的版本：

...

li = [{k1: v1,
       k2: v2}
      for (k1, v1), (k2, v2) in product(d.items(), repeat=2)
      if k1 != k2]

def dict_values_intersection_len(d):
    values = list(d.values())
    return len(values[0] & values[1])


truck_1, truck_2 = max(li, key=dict_values_intersection_len)
print(truck_1, truck_2)

同时也输出

13 16