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

Question

我正在做一个简单的协同过滤（CF）。它是一个项目对项目CF。 例如，我有一个包含N个项目的巨型dict，其中key是产品名称，value是购买它们的客户列表：

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

我还有一个小函数，可以计算每个项目之间客户的相似性，例如第1项与第2项之间的相似性：

^{pr2}$

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

现在每个项目的运行时间为2分钟（N约为300万）。生成一个完整的N*N相似性表需要100000个小时。有比这种暴力方法更好的算法吗？每个项目只需要前几个结果。在

Answer 1

创建一个反向索引，该索引具有：

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

然后您可以：

1. 查找商品以获得购买该商品的顾客名单
2. 查找每个客户以获得客户购买的项目列表

你每件物品的时间应该从2分钟减少到2秒以内。在

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

更多细节

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

^{pr2}$

Answer 2

这与@Jim Mischel的回答基本相同，即构建一个显式的反向索引，但不构建显式的NxN矩阵，它是整个系统的实现而不是草图。在

对于大量的NUM_客户（比如1000000个），它的性能不是很好（对于3个类似的检查，大约20秒），但是数据是随机的。据推测，实际客户购买数据中的相关性会更高，随机性也会更少。在

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

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)

然后定义几个函数：

^{pr2}$

然后，运行它：

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