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

Question

我正在做一个简单的协同过滤（CF），具体是物品对物品的协同过滤。举个例子，我有一个很大的字典，里面有N个商品，字典的键是商品的名字，值是购买这些商品的顾客列表：

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

我还有一个小函数，用来计算每个商品之间顾客的相似度，比如说商品1和商品2之间的相似度：

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相似度表，估计需要10万小时。有没有比这种暴力计算更好的算法？其实每个商品只需要最前面的几个结果。

Answer 1

这其实和@Jim Mischel的回答是一个意思，就是建立一个明确的反向索引，不过这里没有建立一个明确的NxN矩阵，而是实现了一个具体的方案，而不是只是一个系统的草图。

当顾客数量很大时（比如说100万），性能就不是很好（大约需要20秒来进行3次相似度检查），不过数据是随机的。可以推测，实际顾客的购买数据中会有更多的相关性，随机性会少一些。

首先，生成一些用于测试的合成数据：

import random
import operator

NUM_CUSTOMERS = 10000
NUM_ITEMS = 1000
MIN_PER_CUST = 2
MAX_PER_CUST = 10
NUM_INTEREST = 10

customers = ["customer_{}".format(num) for num in xrange(1, NUM_CUSTOMERS+1)]
items = ["item_{}".format(num) for num in xrange(1, NUM_ITEMS+1)]

customer_items = {
    customer: random.sample(items, random.randint(MIN_PER_CUST, MAX_PER_CUST))
    for customer in customers}

item_customers = {}
for customer, this_items in customer_items.iteritems():
    for item in this_items:
        item_customers.setdefault(item, [])
        item_customers[item].append(customer)

然后定义几个函数：

def similarity(item1, item2):
    item1_set = set(item_customers[item1])
    item2_set = set(item_customers[item2])

    num_common = len(item1_set.intersection(item2_set))
    num_total = len(item1_set.union(item2_set))

    return float(num_common) / num_total

def similarity_for(item):
    to_check = {
        itm for customer in item_customers[item]
            for itm in customer_items[customer] }
    to_check.discard(item)
    rankings = {
        item2: similarity(item, item2)
        for item2 in to_check }
    return sorted(rankings.iteritems(), key=operator.itemgetter(1), reverse=True)

最后，运行它：

for index, item in enumerate(sorted(random.sample(items, 3))):
    rankings = similarity_for(item)
    print "check {}; {} (of {}):".format(index, item, len(rankings))
    for item_other, ranking in rankings[:NUM_INTEREST]:
        print "  {}: {}".format(item_other, ranking)

得到的结果看起来像这样：

% python /tmp/similarity.py
check 0; item_121 (of 309):
  item_520: 0.0283018867925
  item_361: 0.027027027027
  item_536: 0.0265486725664
  item_637: 0.0238095238095
  item_515: 0.020202020202
  item_750: 0.019801980198
  item_960: 0.0192307692308
  item_25: 0.0190476190476
  item_548: 0.018691588785
  item_841: 0.018691588785
check 1; item_714 (of 298):
  item_162: 0.0285714285714
  item_491: 0.0272727272727
  item_617: 0.0265486725664
  item_949: 0.0260869565217
  item_788: 0.0192307692308
  item_446: 0.0190476190476
  item_558: 0.018691588785
  item_606: 0.0181818181818
  item_177: 0.0181818181818
  item_577: 0.018018018018
check 2; item_991 (of 352):
  item_758: 0.0298507462687
  item_204: 0.025
  item_85: 0.0247933884298
  item_769: 0.024
  item_501: 0.0232558139535
  item_860: 0.0227272727273
  item_408: 0.0225563909774
  item_480: 0.0223880597015
  item_73: 0.0220588235294
  item_593: 0.021897810219

Answer 2

创建一个倒排索引，内容包括：

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