Efficient Implementation of the Apriori Algorithm using Pandas

Beer and Diapers

In the case studies of association algorithms, the most frequently mentioned story is "Beer and Diapers." The story originated in the 1990s at Walmart supermarkets in the United States. Supermarket managers discovered that "beer and diapers, two seemingly unrelated items, often appeared in the same shopping basket." After analysis, it turned out that in American families with infants, mothers usually stayed home to look after the baby while young fathers went to the supermarket to buy diapers. While buying diapers, the fathers would often pick up beer for themselves. Thus, the phenomenon occurred where beer and diapers appeared together frequently. Consequently, Walmart tried placing beer and diapers in the same area, allowing young fathers to find both items simultaneously. The result was quite successful!

(Note: The authenticity of this story is often questioned, but regardless, it has become a famous and simple case for introducing association analysis.)

Apriori Algorithm

How can we find association rules like "Beer and Diapers" from a large number of purchase records? There are many association analysis algorithms, and the simplest is likely the Apriori algorithm (though its efficiency is not high, it is excellent as an introductory algorithm). This article will not introduce the detailed content of the Apriori algorithm because there is already too much similar content online, and the existing material is quite good. Recommended reading:

• https://en.wikipedia.org/wiki/Association_rule_learning

• http://hackerxu.com/2014/10/18/apriori.html

Python Implementation

After several days of debugging, I finally implemented a relatively efficient Apriori script using Python. Of course, the "efficiency" here refers to the Apriori algorithm itself and does not involve improvements to the algorithm’s logic. The script utilizes the Pandas library to minimize code length while maintaining operational efficiency. Readers will find that the code here is shorter and more efficient than many Apriori implementations found online (not limited to Python).

The code is compatible with both Python 2.x and 3.x, provided that Pandas is installed. This code can basically handle association analysis problems with tens of thousands of records and dozens of candidate items, though patience is required for the execution to complete.

Algorithm Efficiency Issues

The running time of the Apriori algorithm depends on many factors, such as the volume of data, the minimum support (though it has little to do with minimum confidence), and the number of candidate items. Taking market basket analysis as an example: first, the running time depends directly on the number of shopping records N, but the relationship with N is merely linear. Second, the minimum support is almost decisive; it significantly affects the running time, though its impact must be analyzed case by case. Furthermore, it largely determines the number of rules ultimately generated. Finally, the number of candidate items k (i.e., how many unique products appear across all shopping records) is also decisive. If k itself is large, the subsequent joins will result in itemsets of size k^2, k^3, \dots (approximately), which has a fatal impact on speed.

Therefore, while the logic of the Apriori algorithm is simple, its efficiency is not high.

Code

# -*- coding: utf-8 -*-
from __future__ import print_function
import pandas as pd

# Load data
d = pd.read_csv('apriori.txt', header=None, dtype = object)

print('\nConverting raw data to 0-1 matrix...')
import time
start = time.clock()
ct = lambda x : pd.Series(1, index = x)
b = map(ct, d.as_matrix())
d = pd.DataFrame(list(b)).fillna(0)
d = (d==1)
end = time.clock()
print('\nConversion complete, time taken: %0.2f seconds' % (end-start))
print('\nStarting search for association rules...')
del b

support = 0.06 # Minimum support
confidence = 0.75 # Minimum confidence
ms = '--' # Connector to distinguish elements, e.g., A--B. Ensure this doesn't exist in raw data.

# Custom connection function to implement L_{k-1} to C_k join
def connect_string(x, ms):
    x = list(map(lambda i:sorted(i.split(ms)), x))
    l = len(x[0])
    r = []
    for i in range(len(x)):
        for j in range(i,len(x)):
            if x[i][:l-1] == x[j][:l-1] and x[i][l-1] != x[j][l-1]:
                r.append(x[i][:l-1]+sorted([x[j][l-1],x[i][l-1]]))
    return r

# Function to find association rules
def find_rule(d, support, confidence):
    import time
    start = time.clock()
    result = pd.DataFrame(index=['support', 'confidence']) # Define output results

    support_series = 1.0*d.sum()/len(d) # Support series
    column = list(support_series[support_series > support].index) # Initial filtering by support
    k = 0

    while len(column) > 1:
        k = k+1
        print('\nPerforming search No. %s...' % k)
        column = connect_string(column, ms)
        print('Count: %s...' % len(column))
        sf = lambda i: d[i].prod(axis=1, numeric_only = True) # Function to calculate new support

        # Create join data. This step is the most time and memory consuming.
        # For large datasets, consider parallel computing optimization.
        d_2 = pd.DataFrame(list(map(sf,column)), index = [ms.join(i) for i in column]).T

        support_series_2 = 1.0*d_2[[ms.join(i) for i in column]].sum()/len(d) # Calculate joined support
        column = list(support_series_2[support_series_2 > support].index) # New round of support filtering
        support_series = support_series.append(support_series_2)
        column2 = []
        
        for i in column: # Traverse possible inferences, e.g., is {A,B,C} A+B-->C or B+C-->A?
            i = i.split(ms)
            for j in range(len(i)):
                column2.append(i[:j]+i[j+1:]+i[j:j+1])
        
        cofidence_series = pd.Series(index=[ms.join(i) for i in column2]) # Define confidence series
        
        for i in column2: # Calculate confidence series
            cofidence_series[ms.join(i)] = support_series[ms.join(sorted(i))]/support_series[ms.join(i[:len(i)-1])]
        
        for i in cofidence_series[cofidence_series > confidence].index: # Confidence filtering
            result[i] = 0.0
            result[i]['confidence'] = cofidence_series[i]
            result[i]['support'] = support_series[ms.join(sorted(i.split(ms)))]

    result = result.T.sort(['confidence','support'], ascending = False) # Organize and output results
    end = time.clock()
    print('\nSearch complete, time taken: %0.2f seconds' % (end-start))
    print('\nResults are:')
    print(result)
    
    return result

find_rule(d, support, confidence).to_excel('rules.xls')

Test dataset: apriori.txt

Execution results:

When reprinting, please include the original address: https://kexue.fm/archives/3380

For more detailed reprinting matters, please refer to: Scientific Space FAQ