如何用Python高效地基于交易数据创建用户图？

Question

我正在尝试使用Python的networkx库来创建用户之间的关系图。我的原始数据是单个支付交易，其中包含用户、支付工具、IP地址等信息。我的节点是用户，如果两个用户共享同一个IP地址，我就会创建连接。

从这些交易数据中，我创建了一个Pandas数据框，里面存储了唯一的[用户, IP]对。为了创建连接，我需要找到[user_a, user_b]这样的对，前提是这两个用户共享一个IP。我们把这个数据框叫做'df'，它有'用户'和'IP'这两列。

我一直遇到内存问题，尝试了几种不同的解决方案。作为参考，原始交易列表大约有50万条，包含大约13万用户，3万IP，可能还有3000万条连接。

1. 将df与自身连接，排序对并去重（这样[X, Y]和[Y, X]就不会都显示为唯一对）。

   df_pairs = df.join(df, how='inner', lsuffix='l', rsuffix='r')
   df_sorted_pairs = [np.sort([df_pairs['userl'][i], df_pairs['userr'][i]]) for i in range(len(df_pairs))]
   edges = np.asarray(pd.DataFrame(df_sorted_pairs).drop_duplicates())
   

   这个方法效果不错，但很快就出现了内存错误，因为将一个表与自身连接会迅速增加数据量。

2. 创建一个矩阵，用户作为行，IP作为列，矩阵中的元素如果该用户在这个IP上有交易就标记为1，否则为0。然后用X.dot(X.transpose())得到一个方阵，元素(i,j)表示用户i和用户j共享了多少个IP。

   user_list = df['user'].unique()
   ip_list = df['ip'].unique()
   df_x = pd.DataFrame(index=user_list, columns=ip_list)
   df_x.fillna(0, inplace=True)
   for row in range(len(df)):
       df_x[df['ip'][row]][df['user'][row]] = 1
   df_links = df_x.dot(df_x.transpose())
   

   这个方法非常有效，除非len(ip_list)大于5000。仅仅创建一个50万行x20万列的空数据框就会出现内存错误。

3. 暴力破解。逐个遍历用户。对于每个用户，找到不同的IP。对于每个IP，找到不同的用户。这样得到的用户就与当前遍历的用户有连接。将这个[用户1, 用户2]的列表添加到连接的主列表中。

   user_list = df['user'].unique()
   ip_list = df['ip'].unique()
   links=[]
   for user in user_list:
       related_ip_list = df[df['user'] == user]['ip'].unique()
       for ip in related_ip_list:
           related_user_list = df[df['ip'] == ip]['user'].unique()
           for related_user in related_user_list:
               if related_user != user:
                   links.append([user, related_user])
   

   这个方法可行，但非常慢。它运行了3个小时，最后还是出现了内存错误。因为在这个过程中连接一直在保存，所以我可以检查它的大小——大约2300万条连接。

任何建议都非常感谢。我是不是已经深入到“巨量数据”中，传统的方法不再适用了？我原以为50万条交易不算“巨量数据”，但我想存储一个13万x3万的矩阵或创建一个3000万元素的列表确实很大？

Answer 1

我觉得你的问题在于，使用矩阵表示法并不合适：

首先，从内存使用的角度来看，你的做法非常低效。比如，你创建了一个充满零的矩阵，这些零需要在内存中分配空间。与其在内存中为一个不存在的连接分配一个零，不如干脆不在内存中放任何东西。你在用线性代数的数学方法来解决问题，这样会占用很多内存。（你的矩阵里有130,000乘以30,000的元素，数量非常庞大，但实际上你只关心3000万条链接）

我非常理解你的感受，因为pandas是我学的第一个库，我也曾试图用pandas解决几乎所有问题。不过随着时间的推移，我发现矩阵方法并不适合很多问题。

在numpy里有一个“稀疏矩阵”的概念，但我们先不讨论这个。

让我给你推荐另一种方法：

使用一个简单的默认字典：

from collections import defaultdict

# a dict that makes an empty set if you add a key that doesnt exist
shared_ips = defaultdict(set)

# for each ip, you generate a set of users
for k, row in unique_user_ip_pairs.iterrows():
    shared_ips[row['ip']].add(row['user'])

#filter the the dict for ips that have more than 1 user
shared_ips = {k, v for k, v in shared_ips.items() if len(v) > 1}

我不确定这是否能100%解决你的问题，但注意它的效率：

这最多只会让你最初的唯一用户-IP对的内存使用量翻倍。但你可以得到哪些IP是被哪些用户共享的信息。

大教训是：

如果矩阵中的大多数单元格表示相同类型的信息，当你遇到内存问题时，不要使用矩阵方法

我见过很多用pandas解决的问题，其实可以用Python内置的简单类型，比如dict、set、frozenset和Counters来解决。尤其是那些从MATLAB、R或Excel等统计工具转到Python的人，更容易犯这个错误（他们确实喜欢表格）。我建议大家尽量不要把pandas当作自己首选的内置库...