3
\$\begingroup\$

Not having found a satisfactory association rules implementation in Python, I set out to code my own. The code below runs reasonably quickly, but the groceries dataset used for testing is peanuts compared to the actual transactions dataset I'll be using in production (think hundreds of thousands of transactions). I'm looking for any performance improvements. Most of the objects iterated over for creating itemset frequencies are sets, but is there anything else in Python I should be thinking of, speed-wise, that's relevant to the code below? I think the final list comprehension maybe could use some improvement, but I haven't had any luck with multiprocessing.Pool yet.

import operator
from itertools import combinations
from bs4 import BeautifulSoup
import urllib2

# separate into support_count and support
def support_count(items):
    '''
    Let transactions be a list of transactions, n_transactions be the number of elements in that list, and X be an itemset.

    In pseudocode, support_count(X) - support count for an itemset of length 1:

    count = 0
    For t in transactions:
        if X is an element of t:
            count += 1
    return count

    support_count((X,Y)) - support count for an itemset of length two:
    count = 0
    For t in transactions:
        if X or Y is an element of t:
            count += 1
    return count
    '''
    # if str, then we know we're looking for the support of one item
    if type(items) is str:
        # if type(items) is str then we know we're searching 
        # for support_count for one item and can use rows_indiv (list of sets of words)
        spec_rows = rows_indiv   
        count = sum([1 for row in spec_rows if items in row])
    # if tuple, then we know we're looking for the support rule between two items
    elif type(items) is tuple:
        if items[0] == items[1]:
            return None
        else:
            # use rows_all_type_combos to satisfy or condition...
            # either the whole tuple is in a given transaction t, or we see if at least one of the elements is in t
            spec_rows = rows_all_type_combos
            # if any of the elements in items are in a row, count that row
            count = sum([1 for row in spec_rows if any([item in row for item in items])])
    return count

def vocab(tuples_set):
    return {word for t in tuples_set for word in t}

url = 'https://raw.githubusercontent.com/stedy/Machine-Learning-with-R-datasets/master/groceries.csv'
open_url = urllib2.urlopen(url)
soup = BeautifulSoup(open_url).encode("ascii")

# list of strings
rows = [row for row in soup.split('\n')]

# global
n_rows = len(rows)

# set of all items in transactions
items = {item for trans in rows for item in trans.split(',')}

# create all possible combinations of elements in items
# should be factorial(len(items))/(factorial(r) * factorial(len(items) - r)) number of elements in pairs list below
pairs = [(a,b) for (a,b) in combinations(items, 2)]

#### two options ####
# One: one support function for tuples and string. support_master()
# used to look up tuples and individual items
rows = [set(row.split()) for row in rows]

# Two: keep one support function for tuples, and one support function for individuals.... support_tuple() and support_indiv()
# used for looking up tuples
rows_tuple = [set((a, b) for a in row for b in row) for row in rows]

# each row is set of elements... used for looking up quickly an individual word
# used for looking up individual items
rows_indiv = [set(a) for a in rows]

rows_all_type_combos = []
for row in rows_tuple:
    row_vocab = vocab(row)
    row_to_append = list(row)
    for word in row_vocab:
        row_to_append.append(word)
    rows_all_type_combos.append(row_to_append)

for idx, row in enumerate(rows_all_type_combos):
    rows_all_type_combos[idx] = set(rows_all_type_combos[idx])

# support for all pairs of items
res = [(p, support_count(p)) for p in pairs]
\$\endgroup\$
  • 2
    \$\begingroup\$ Have you run your code with python -m cProfile script_name.py to see where it spends most of the time? \$\endgroup\$ – Graipher Sep 28 '16 at 8:00
  • 2
    \$\begingroup\$ Welcome to Code Review! Please do not update the code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers. \$\endgroup\$ – Mathias Ettinger Sep 28 '16 at 13:38
2
\$\begingroup\$

One simple improvement will be to realize that sum can take a generator expression. It does not need an intermediate list which will take up a lot of memory if the number of transactions becomes large. Same goes for any, which will even use short-circuit evaluation in that case. So you can write:

count = sum(1 for row in spec_rows if items in row)

and

count = sum(1 for row in spec_rows if any(item in row for item in items))

Secondly, your specs rows_indiv seem to be used exactly once (and have the length of the number of entries). You could make it a generator to save a lot of space (and time for memory allocation).

rows_indiv = (set(a) for a in rows)

On the other hand, this is not true for rows_all_type_combos, because some of the list's members are being re-assigned in the for loop after its construction.

\$\endgroup\$
  • \$\begingroup\$ Using a generator expression for sum and any works great, but when I turn rows_indiv and rows_all_type_combos into generators, all of my values for support_count() become zeros, as if the elements in those expressions are not being iterated over. See above code changes if you'd like. \$\endgroup\$ – blacksite Sep 28 '16 at 13:03
  • 1
    \$\begingroup\$ @GBR24 For rows_all_type_combos this makes sense, because after looking at the code again, you do use it more than once (after the first time the iterator will be exhausted). \$\endgroup\$ – Graipher Sep 29 '16 at 11:44
  • \$\begingroup\$ So, generators are really only used once? What does it mean for a generator to be exhausted? \$\endgroup\$ – blacksite Sep 29 '16 at 11:54
  • 1
    \$\begingroup\$ @not_a_robot It should mean that every element of the iterator has been used. Technically it means that the generator raised a StopIteration exception, sginaling that it does not have any more items. (This is how the for loop knows when to stop.) \$\endgroup\$ – Graipher Sep 29 '16 at 15:25
  • 1
    \$\begingroup\$ @not_a_robot So yes, whenever you get an element from a generator it calls next on them. And since they don't have any memory of their past state, only their current, they don't know how to reset if they are exhausted. You will have to generate a new generator (possibly with the same code, in a function) in that case. \$\endgroup\$ – Graipher Sep 29 '16 at 15:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.