将字典转换为稀疏矩阵

Question

我有一个字典，其中键为用户id，值为该用户喜欢的电影ID列表，其中#unique_users = 573000，# unique_movies =16000。

{1: [51, 379, 552, 2333, 2335, 4089, 4484], 2: [51, 379, 552, 1674, 1688, 2333, 3650, 4089, 4296, 4484], 5: [783, 909, 1052, 1138, 1147, 2676], 7: [171, 321, 959], 9: [3193], 10: [959], 11: [131,567,897,923],..........}

现在我想将其转换为矩阵，以用户ID作为行，以电影ID作为列，值为1表示用户喜欢该电影。即它将是573000*16000的矩阵。

最终，我需要将此矩阵与其转置相乘，以获得维度为(#unique_movies,#unique_movies)的共现矩阵。

另外，如果X是(500000,12000)大小的矩阵，则X'*X操作的时间复杂度将是什么？

- chirag yadav

Answer 1

我认为你可以构建一个空的dok_matrix，并填充值。然后对其进行转置，并将其转换为csr_matrix以进行高效矩阵乘法。

import numpy as np
import scipy.sparse as sp
d = {1: [51, 379, 552, 2333, 2335, 4089, 4484], 2: [51, 379, 552, 1674, 1688, 2333, 3650, 4089, 4296, 4484], 5: [783, 909, 1052, 1138, 1147, 2676], 7: [171, 321, 959], 9: [3193], 10: [959], 11: [131,567,897,923]}

mat = sp.dok_matrix((573000,16000), dtype=np.int8)

for user_id, movie_ids in d.items():
    mat[user_id, movie_ids] = 1

mat = mat.transpose().tocsr()
print mat.shape

- Zichen Wang

---

但是那么for循环将会有57300次迭代，因为这就是字典中不同用户的数量。 - chirag yadav

@chiragyadav 我认为这应该是高效的，因为你已经在字典中索引了你的数据，并且dok_matrix对于逐步构建矩阵是高效的。 - Zichen Wang

我在考虑为每个用户创建一个数组，将其初始化为0，并使用字典中的索引填充为1。最后将该数组作为新行附加到矩阵中。 - Ma0

@Zichen Wang 感谢您指出。movies_ids 也不需要在区间(0，#unique_ids)内。 - chirag yadav

@chiragyadav 你可能想要找出行和列的最大索引，然后构建稀疏矩阵。 - Zichen Wang

Answer 2

df = {1: [51, 379, 552, 2333, 2335, 4089, 4484], 2: [51, 379, 552, 1674, 1688, 2333, 3650, 4089, 4296, 4484], 5: [783, 909, 1052, 1138, 1147, 2676], 7: [171, 321, 959], 9: [3193], 10: [959], 11: [131,567,897,923],..........}
df2 = pd.DataFrame.from_dict(df, orient='index')
df2 = df2.stack().reset_index()
df2.level_1=1
df2.pivot(index='level_0',columns=0,values='level_1').fillna(0)

这将字典转换为数据框，然后堆叠以获取单独的用户ID和电影ID列，然后将所有未使用的列level_1的值设置为1。最后一个语句创建了一个填充不存在组合的零的透视表。

- user3404344

Answer 3

你可以一次性创建 csr_matrix（像这样的格式：csr_matrix((data, (row_ind, col_ind))）。以下是如何执行此操作的代码片段。

import scipy.sparse as sp
d = {0: [0,1], 1: [1,2,3], 
     2: [3,4,5], 3: [4,5,6], 
     4: [5,6,7], 5: [7], 
     6: [7,8,9]}
row_ind = [k for k, v in d.items() for _ in range(len(v))]
col_ind = [i for ids in d.values() for i in ids]
X = sp.csr_matrix(([1]*len(row_ind), (row_ind, col_ind))) # sparse csr matrix

您可以使用矩阵X来后续查找共现矩阵（即X.T * X）（感谢github @daniel-acuna）。我猜想有一种更快的方法将列表字典转换为row_ind，col_ind。

- titipata