python - 生成 N*N 矩阵的高效算法

Question

我正在做一个简单的协同过滤 (CF)。它是一个项目到项目的 CF。例如，我有一个包含 N 项的巨大字典，其中键是产品名称，值是购买它们的客户列表:

d={
item1:[customer1,customer3,customer7], 
item2:[customer3, customer5],
...
itemN:[customerX...customerY]
}

我还有一个小函数可以计算每个项目之间的客户相似度，例如item1 与 item2:

def littlefunction(...):

    #convert them to a set
    item1=set(d['item1'])
    item2=set(d['item2'])

    commonCustomer=item1.intersect(item2)
    totalCustomer=item1.union(item2)

    similarity=float(len(commonCustomer))/len(totalCustomer)

为了获得每个指定项目的最相似项目，我必须扫描，并计算 N 次相似度，然后排序。所以对于 N 项，复杂度是 O(N*N)。

每个项目的运行时间现在是 2 分钟(N 大约 = 300 万)。生成一个完整的 N*N 相似度表需要 100,000 小时。有比这种蛮力方法更好的算法吗？每个项目只需要前几个结果。

Answer 1

创建一个倒排索引:

customer1: [item1, item3, item8, ...]
customer2: [item7, item8, item74, ...]

然后你可以:

1. 查找商品以获得购买该商品的客户列表
2. 查找每个客户以获取客户购买的商品列表

每个项目的时间应该从 2 分钟减少到不到 2 秒。

第二个索引需要更多内存，但您并没有复制数据。如果内存有问题，您可以将其存储在一个简单的数据库中，并且仍然比您当前使用的 N^2 算法快得多。

更多详情

您想创建一个 N*N 矩阵来显示任意两个项目之间的相似性。使用我的技术，您可以执行以下操作:

Create an N*N matrix, and initialize it to 0.
for each item
  Get the list of customers who bought the item (from your item-to-customer index).
  Create an empty dictionary of related items
  for each customer in that list
    for each item that the customer bought
      update the dictionary (add new item, or increase count)
    end for
  end for
  You now have a dictionary that contains the related items,
  and how many customers bought each one. You can update the matrix row
  for the current item from that dictionary.
end for