在Python中为创建一个一起评级的项目列表而优化算法

Question

给出购买事件列表（客户编号，商品）

1-hammer
1-screwdriver
1-nails
2-hammer
2-nails
3-screws
3-screwdriver
4-nails
4-screws

我试图构建一个数据结构，它告诉你一件商品和另一件商品一起购买了多少次。不是同时买的，而是我开始保存数据后买的。结果看起来像

^{pr2}$

表示锤子用钉子买了两次（人1、3），螺丝刀买了一次（人1），螺丝刀买了一次（人3），以此类推。。。在

我目前的做法是

users=dict，其中userid是键，购买的项目列表是值

usersfritem=dict，其中itemid是键，购买item的用户列表是值

userlist=对当前项目进行评级的用户的临时列表

pseudo:
for each event(customer,item)(sorted by item):
  add user to users dict if not exists, and add the items
  add item to items dict if not exists, and add the user
----------

for item,user in rows:

  # add the user to the users dict if they don't already exist.
  users[user]=users.get(user,[])

  # append the current item_id to the list of items rated by the current user
  users[user].append(item)

  if item != last_item:
    # we just started a new item which means we just finished processing an item
    # write the userlist for the last item to the usersForItem dictionary.
    if last_item != None:
      usersForItem[last_item]=userlist

    userlist=[user]

    last_item = item
    items.append(item)
  else:
    userlist.append(user)

usersForItem[last_item]=userlist   

所以，在这一点上，我有两个结论-谁买了什么，什么是谁买的。这就是问题的症结所在。现在usersWrite已经填充完毕，我将遍历它，遍历每个购买该项的用户，并查看用户的其他购买行为。我承认这并不是最具Python式的做事方式——我在尝试在使用Python之前确保得到正确的结果（我就是这样）。在

relatedItems = {}
for key,listOfUsers in usersForItem.iteritems():
  relatedItems[key]={}
  related=[]

  for ux in listOfReaders:
    for itemRead in users[ux]:
      if itemRead != key:
        if itemRead not in related:
          related.append(itemRead)
        relatedItems[key][itemRead]= relatedItems[key].get(itemRead,0) + 1    

  calc jaccard/tanimoto similarity between relatedItems[key] and its values

有没有更有效的方法可以让我这样做？另外，如果这种手术有合适的学术名称，我很乐意听到。在

编辑：澄清包括我没有限制购买同时购买的物品。物品可以随时购买。在

Answer 1

保罗的答案也许是最好的，但以下是我在午休时想到的（诚然，这还没有经过测试，但仍然是一个有趣的思考练习）。不确定我的算法是否快速/优化。我个人建议看看类似MongoDB的NoSQL数据库，因为它似乎可以很好地解决此类问题（map/reduce等等）

# assuming events is a dictionary of id keyed to item bought...
user = {}
for (cust_id, item) in events:
    if not cust_id in users:
        user[cust_id] = set()
    user[cust_id].add(item)
# now we have a dictionary of cust_ids keyed to a set of every item
# they've ever bought (given that repeats don't matter)
# now we construct a dict of items keyed to a dictionary of other items
# which are in turn keyed to num times present
items = {}
def insertOrIter(d, k, v):
    if k in d:
        d[k] += v
    else:
        d[k] = v
for key in user:
    # keep track of items bought with each other
    itemsbyuser = []
    for item in user[key]:
        # make sure the item with dict is set up
        if not item in items:
            items[item] = {}
        # as we see each item, add to it others and others to it
        for other in itemsbyuser:
            insertOrIter(items[other], item, 1)
            insertOrIter(items[item], other, 1)
        itemsbyuser.append(item)
# now, unless i've screwed up my logic, we have a dictionary of items keyed
# to a dictionary of other items keyed to how many times they've been
# bought with the first item. *whew* 
# If you want something more (potentially) useful, we just turn that around to be a
# dictionary of items keyed to a list of tuples of (times seen, other item) and
# you're good to go.
useful = {}
for i in items:
    temp = []
    for other in items[i]:
        temp[].append((items[i][other], other))
    useful[i] = sorted(temp, reverse=True)
# Now you should have a dictionary of items keyed to tuples of
# (number times bought with item, other item) sorted in descending order of
# number of times bought together