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 set
s, 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]
python -m cProfile script_name.py
to see where it spends most of the time? \$\endgroup\$