从一组Python列表中找到共同元素最多的两个列表 - Python / Pandas

3

问题:

我有多个长度不同的python列表,所有列表中只包含整数。

如何找到具有最多公共元素的2个列表?

示例输入:

list1 = [234, 982, 908, 207, 456, 284, 473]
list2 = [845, 345, 765, 678]
list3 = [120, 542, 764, 908, 217, 778, 999, 326, 456]

# thousands more lists ...

示例输出:

# 2 most similar lists:

list400, list6734

注意:我不是要找到列表中最常见的元素,只想知道哪两个列表最相似,即共同元素最多。我也不关心单个元素的相似度,一个元素要么在两个列表中都存在,要么不存在。

背景:

我有一个数据集,表示哪些用户在平台上点赞了某些帖子。如果两个用户都喜欢同一篇帖子,则它们的共同点赞分数为1。如果两个用户喜欢相同的10篇帖子,则它们的共同点赞分数为10。我的目标是找出具有最高共同点赞分数的两个用户。

我已经将数据(从CSV文件)加载到pandas数据框中,每一行表示用户和帖子之间的点赞关系:

索引 用户ID 帖子ID
0 201 234
1 892 908
2 300 825

等等,还有成千上万行。

我的方法是按用户ID对数据进行分组,然后将每个用户的帖子连接成单个行/列,作为逗号分隔的字符串:

df = df[df['user id'].duplicated(keep=False)]
df['post id'] = df['post id'].astype(str)
df['liked posts'] = df.groupby('user id')['post id'].transform(lambda x: ','.join(x))
df = df.drop(columns=['post id'])
df = df[['user id', 'liked posts']].drop_duplicates()

得到的数据框如下:

索引 用户ID 喜欢的帖子
0 201 234,789,267, ...
1 892 908,734,123, ...
2 300 825,456,765, ...

等等,这里用户ID是唯一的行标识符...

因此,我的问题是:我需要找出数据框中在“喜欢的帖子”列中具有最多共同数字的行,并返回具有最高common_like_score的2个用户。

如果有更好的解决方案,请也分享一下。


1
Pandas 可能不是执行此计算的最佳库。相反,我建议将所有数据转换为集合,获取每两个集合的并集,并找到最大的并集。 - Andrew Mascillaro
谢谢@AndrewMascillaro,你能分享一个实际操作的例子吗? - AJ8
1
请参考 @tdelaney 的解决方案进行实现。 - Andrew Mascillaro
1
每当我想到社交媒体时,我总是会想到图论。具体来说,问题是找到两点之间长度为n的路径数。我在下面发布了自己的解决方案,但可能还有其他更快的方案可以尝试。 - Akilan Manivannan
3个回答

4

由于这些是可变长度列表,因此 Pandas(喜欢使用大小相同的列)可能不是最好的工具。在纯 Python 中,您可以将这些列表转换为集合,然后使用集合交集计数来查找最常见的项。这将是集合中最常见的,如果列表包含多个相同的整数副本,则可能与列表不同。

我想出的代码有点复杂,因为它只在中间进行了一次转换到集合。但我认为它很容易阅读...(我希望如此)。

import itertools

list1 = [234, 982, 908, 207, 456, 284, 473]
list2 = [845, 345, 765, 678]
list3 = [120, 542, 764, 908, 217, 778, 999, 326, 456]
lists = [list1, list2, list3]

# intermediate sets for comparison
sets = [(set(l),i) for i,l in enumerate(lists)]

# list of in-common count for each combo of two "sets"
combos = [(len(a[0] & b[0]), a, b) for a,b in itertools.combinations(sets, 2)]
combos.sort()

# most in-common "sets"
most = combos[-1][1:]

# dereferenced
most1, most2 = lists[most[0][1]], lists[most[1][1]]

print(most1, most2)

2
这似乎是图论的一个完美应用。如果我们将每个用户和帖子都想象成一个节点,并将每个用户连接到他们所喜欢的帖子,我们可以对图进行变换,得到一个矩阵,显示所有用户的common_like_score。此时,获取得分最高的一对应该很容易。
在图论中,“找到两个节点之间长度为n的路径数”是一个众所周知且已解决的问题。
以下是了解该理论的一些好的参考链接:
  1. https://www.geeksforgeeks.org/find-the-number-of-paths-of-length-k-in-a-directed-graph/
  2. https://cp-algorithms.com/graph/fixed_length_paths.html
基本上,如果您将此数据表示为一个邻接矩阵,那么您可以对该矩阵进行平方运算,以获取每个用户的喜爱度分数!
这是我的实现代码:
import numpy as np

#Create an adjacency matrix
users = df["user id"].unique()
combined = np.concatenate((users, df["post id"].unique()), axis=0)
combined_dict = dict()
i = 0
for c in combined:
    combined_dict[c] = i
    i += 1

n = len(combined)-1
M = np.zeros((n+1, n+1))

for pair in df.itertuples():
    M[combined_dict[pair._1], combined_dict[pair._2]] = 1
    M[combined_dict[pair._2], combined_dict[pair._1]] = 1
M = np.asmatrix(M)


#Square the matrix to get scores of all users
scores = M*M

#Slice matrix to only include users
user_count = len(users)
scores = scores[0:user_count, 0:user_count]

#Remove paths between same user
for i in range(user_count):
    scores[i, i] = 0

print(scores)

运行此代码将生成一个矩阵,如下所示(不包含用户标签):
User 1 User 2 User 3 User 4
User 1 0 2 1 0
User 2 2 0 1 1
User 3 1 1 0 0
User 4 0 1 0 0
此时,查找最大用户对应该是轻而易举的(我加粗了得分最高的2)。作为额外的奖励,您还可以获得任何用户对的分数,并随意查询它们。

值得一提的是,如果您不想自己编写所有代码,您也可以使用像NetworkX这样的库来为您完成此操作。 - Akilan Manivannan

1

由于您只关心共同元素的计数,因此可以创建虚拟变量,然后使用点积获取所有用户比较的共享元素数量。然后我们找到最大值。

示例数据

import pandas as pd
import numpy as np

df = pd.DataFrame({'user id': list('ABCD'),
                   'liked_posts': ['12,14,141', '12,14,141,151',
                                   '1,14,151,15,1511', '2,4,1411,141']})

代码

# Dummies for each post
arr = df['liked_posts'].str.get_dummies(sep=',')
#   1  12  14  141  1411  15  151  1511  2  4
#0  0   1   1    1     0   0    0     0  0  0
#1  0   1   1    1     0   0    1     0  0  0
#2  1   0   1    0     0   1    1     1  0  0
#3  0   0   0    1     1   0    0     0  1  1 

# Shared counts. By definition symmetric
# diagonal -> 0 makes sure we don't consider same user with themself.
arr = np.dot(arr, arr.T)
np.fill_diagonal(arr, 0)

df1 = pd.DataFrame(index=df['user id'], columns=df['user id'], data=arr)
#user id  A  B  C  D
#user id            
#A        0  3  1  1
#B        3  0  2  1
#C        1  2  0  0
#D        1  1  0  0

# Find user pair with the most shared (will only return 1st pair in case of Ties)
df1.stack().idxmax()
#('A', 'B')

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接