3

指定された購入イベントのリスト (customer_id,item)

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

アイテムが別のアイテムと一緒に購入された回数を示すデータ構造を構築しようとしています。同時購入ではなく、データ保存を始めてから購入。結果は次のようになります

{
       hammer : {screwdriver : 1, nails : 2}, 
  screwdriver : {hammer : 1, screws : 1, nails : 1}, 
       screws : {screwdriver : 1, nails : 1}, 
        nails : {hammer : 1, screws : 1, screwdriver : 1}
}

ハンマーを釘で 2 回購入したこと (人 1、3)、ドライバーを 1 回購入したこと (人 1)、ネジをドライバーで 1 回購入したこと (人 3)、などを示します。

私の現在のアプローチは

users = dict ここで、userid がキーで、購入したアイテムのリストが値です

usersForItem = dict ここで itemid がキーで、アイテムを購入したユーザーのリストが値です

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

したがって、この時点で、誰が何を購入したか、および誰が何を購入したかという 2 つの口述があります。ここがややこしいところです。usersForItem に値が設定されたので、これをループ処理し、アイテムを購入した各ユーザーをループ処理して、ユーザーの他の購入を調べます。私は、これが最も Pythonic な方法ではないことを認識しています。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

これを行うことができるより効率的な方法はありますか？また、この種の操作に適切な学名があれば教えていただきたいです。

編集: 同時に一緒に購入されたアイテムに購入を制限していないという事実を含めるように明確にしました. アイテムはいつでも購入できます。

4

4 に答える 4

3

すべての可能なペアを事前に計算する必要がありますか? それを怠惰に、つまりオンデマンドで行うとしたらどうでしょうか。

これは、2D マトリックスとして表すことができます。行は顧客に対応し、列は製品に対応します。

各エントリは 0 または 1 で、列に対応する製品が行に対応する顧客によって購入されたかどうかを示します。

各列を (約 5000) の 0 と 1 のベクトルとして見ると、2 つの製品が一緒に購入された回数は、対応するベクトルのドット積にすぎません!

したがって、最初にこれらのベクトルを計算してから、必要に応じて内積を遅延して計算できます。

内積を計算するには:

ここで、0 と 1 のみを持つベクトルの適切な表現は、基本的にビットマップである整数の配列です。

5000 エントリの場合、79 個の 64 ビット整数の配列が必要になります。

したがって、そのような配列が 2 つある場合、共通する 1 の数を数える必要があります。

2 つの整数に共通するビット数をカウントするには、まずビットごとの AND を実行し、次に結果の数値に設定されている 1 の数をカウントします。

これには、次のように、ルックアップ テーブルまたはいくつかのビットカウント メソッドを使用できます (Python がそれらをサポートするかどうかはわかりません): http://graphics.stanford.edu/~seander/bithacks.html

したがって、アルゴリズムは次のようになります。

  • 製品ごとに 79 個の 64 ビット整数の配列を初期化します。

  • 顧客ごとに、購入した製品を見て、対応する製品でその顧客に適したビットを設定します。

  • 一緒に購入した顧客の数を知る必要がある 2 つの製品のクエリが与えられた場合は、上記のように内積を取ります。

これはかなり速いはずです。

さらなる最適化として、顧客をグループ化することを検討できます。

于 2010-06-24T14:03:49.277 に答える
2 
events = """\
1-hammer 
1-screwdriver 
1-nails 
2-hammer 
2-nails 
3-screws 
3-screwdriver 
4-nails 
4-screws""".splitlines()
events = sorted(map(str.strip,e.split('-')) for e in events)

from collections import defaultdict
from itertools import groupby

# tally each occurrence of each pair of items
summary = defaultdict(int)
for val,items in groupby(events, key=lambda x:x[0]):
    items = sorted(it[1] for it in items)
    for i,item1 in enumerate(items):
        for item2 in items[i+1:]:
            summary[(item1,item2)] += 1
            summary[(item2,item1)] += 1

# now convert raw pair counts into friendlier lookup table
pairmap = defaultdict(dict)
for k,v in summary.items():
    item1, item2 = k
    pairmap[item1][item2] = v

# print the results    
for k,v in sorted(pairmap.items()):
    print k,':',v

与えます:

hammer : {'nails': 2, 'screwdriver': 1}
nails : {'screws': 1, 'hammer': 2, 'screwdriver': 1}
screwdriver : {'screws': 1, 'nails': 1, 'hammer': 1}
screws : {'nails': 1, 'screwdriver': 1}

(これは、購入イベントごとにアイテムをグループ化する最初の要求に対処します。ユーザーごとにグループ化するには、イベント リストの最初のキーをイベント番号からユーザー ID に変更するだけです。)

于 2010-06-24T16:27:57.827 に答える
1

統計を取得するたびに、上記のすべてのソリューションがデータベース全体をかき回してカウントを取得するのを見るのはかなり奇妙です。

データをフラットなインデックスに保持し、特定のアイテムの結果のみを一度に 1 つずつ取得することをお勧めします。アイテム数が多いと、より効率的になります。

from collections import defaultdict
from itertools import groupby

class myDB:
    '''Example of "indexed" "database" of orders <-> items on order'''
    def __init__(self):
        self.id_based_index = defaultdict(set) 
        self.item_based_index = defaultdict(set)

    def add(self, order_data):
        for id, item in order_data:
            self.id_based_index[id].add(item)
            self.item_based_index[item].add(id)

    def get_compliments(self, item):
        all_items = []
        for id in self.item_based_index[item]:
            all_items.extend(self.id_based_index[id])
        gi = groupby(sorted(all_items), lambda x: x)
        return dict([(k, len(list(g))) for k, g in gi])

使用例：

events = """1-hammer 
    1-screwdriver 
    1-nails 
    2-hammer 
    2-nails 
    3-screws 
    3-screwdriver 
    4-nails 
    4-screws"""

db = myDB()
db.add(
    [ map(str.strip,e.split('-')) for e in events.splitlines() ]
    )
# index is incrementally increased 
db.add([['5','plunger'],['5','beer']])

# this scans and counts only needed items
assert db.get_compliments('NotToBeFound') == {}
assert db.get_compliments('hammer') == {'nails': 2, 'hammer': 2, 'screwdriver': 1}
# you get back the count for the requested product as well. Discard if not needed.

これはすべて楽しいことですが、真剣に、実際のデータベース ストレージを使用してください。インデックス作成は既に任意の DB エンジンに組み込まれているため、SQL の上記のコードはすべて次のようになります。

select
    p_others.product_name,
    count(1) cnt
from products p
join order_product_map opm
    on p.product_id = opm.product_id
join products p_others
    on opm.product_id = p_others.product_id
where p.product_name in ('hammer')
group by p_others.product_name
于 2010-06-24T20:26:00.757 に答える
1

ポールの答えがベストかもしれませんが、ここで私が昼休みに思いついたものを示します (確かにテストされていませんが、それでも楽しい思考のエクササイズです)。私のアルゴリズムの速さ/最適化がわからない. 個人的には、NoSQL データベースである MongoDB のようなものを検討することをお勧めします。

# 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
于 2010-06-24T17:15:01.200 に答える