Efficient Apriori Algorithm Implementation with Pandas

用Pandas实现高效的Apriori算法 苏剑林 · 2015-07-02 · Machine Learning Python data mining association analysis

Latest update: Efficient Apriori Algorithm Implementation with Numpy

I've recently been doing some data mining work, which led me to read up on the Apriori algorithm. Since this isn't an area I'd normally touch, I wasn't familiar with it before, but now that I've run into it at work, I had no choice but to sit down and study it properly. Apriori is an algorithm for finding association rules — that is, discovering plausible logical relationships hidden in a large batch of data. For example, "condition A + condition B" might strongly imply "condition C" (A + B --> C), which is exactly what an association rule looks like. Concretely, a customer who buys product A will often also buy product B (though the reverse — buying B implying buying A — need not hold), or in a more complex case, customers who buy both A and B are quite likely to also buy C (again, not necessarily the other way around). With this kind of information in hand, we can bundle certain products together for sale and thereby increase revenue. The algorithms used to discover such association rules are called association analysis algorithms.

Beer and Diapers

Beer and Diapers

Among the classic examples of association analysis, the most often-cited one is surely "beer and diapers." The story dates back to 1990s Walmart in the United States, where store managers noticed that "beer and diapers — two seemingly unrelated products — frequently turned up together in the same shopping cart." Upon investigation, it turned out that in American households with a baby, it was usually the mother who stayed home to look after the child, while the young father went out to the supermarket to buy diapers. While he was there buying diapers, he'd often pick up some beer for himself as well, which is why these two seemingly unrelated items kept showing up together in the same basket. As a result, Walmart tried placing beer and diapers in the same aisle, so that young fathers could find both items at once. And indeed, the results were quite impressive! more

(Note: the veracity of this story has been questioned, but regardless, it has become a famous and easy-to-understand example for introducing association analysis.)

The Apriori Algorithm

How do we find association rules like "beer and diapers" from a large collection of purchase records? There are many association analysis algorithms out there, the simplest of which is probably Apriori (admittedly not very efficient, but still a solid choice as an introductory algorithm). This post won't go into the details of the Apriori algorithm itself, since there's already plenty of good material on the topic online. Recommended reading:

https://zh.wikipedia.org/zh-cn/关联式规则

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

Python Implementation

After several days of debugging, I finally implemented a reasonably efficient Apriori script in Python. Of course, "efficient" here is relative to the Apriori algorithm itself — I haven't made any improvements to the algorithm's underlying logic. The implementation makes use of the Pandas library, and manages to keep the code about as short as possible while still preserving good runtime performance. As readers will notice, this implementation is both shorter and faster than most Apriori implementations found online (in any language, not just Python).

The code is compatible with both Python 2.x and 3.x, provided Pandas is installed. It can handle data mining tasks involving tens of thousands of records and a few dozen candidate items — though, naturally, you'll need some patience while it runs.

On the Efficiency of the Algorithm

The running time of the Apriori algorithm depends on many factors — the amount of data, the minimum support threshold (though not really on the minimum confidence threshold), the number of candidate items, and so on. Taking market basket analysis as an example: first, the running time obviously depends directly on the number of purchase records $N$, but the relationship with $N$ is only linear. Second, the minimum support threshold is almost decisive — it has a significant impact on running time, though exactly how much depends on the specific problem, and it also largely determines how many rules end up being generated. Finally, there's the number of candidate items $k$ — that is, the total number of distinct products appearing across all the basket records. This factor is also decisive: if $k$ itself is fairly large, then as items get combined in successive rounds, the number of itemsets grows roughly as $k^2$, $k^3$... , which has a devastating effect on speed.

So while the idea behind Apriori is simple, its efficiency leaves much to be desired.

Code

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

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

print(u'\n转换原始数据至0-1矩阵...')
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(u'\n转换完毕，用时：%0.2f秒' %(end-start))
print(u'\n开始搜索关联规则...')
del b

support = 0.06 #最小支持度
confidence = 0.75 #最小置信度
ms = '--' #连接符，用来区分不同元素，如A--B。需要保证原始表格中不含有该字符

#自定义连接函数，用于实现L_{k-1}到C_k的连接
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

#寻找关联规则的函数
def find_rule(d, support, confidence):
    import time
    start = time.clock()
    result = pd.DataFrame(index=['support', 'confidence']) #定义输出结果

    support_series = 1.0*d.sum()/len(d) #支持度序列
    column = list(support_series[support_series > support].index) #初步根据支持度筛选
    k = 0

    while len(column) > 1:
        k = k+1
        print(u'\n正在进行第%s次搜索...' %k)
        column = connect_string(column, ms)
        print(u'数目：%s...' %len(column))
        sf = lambda i: d[i].prod(axis=1, numeric_only = True) #新一批支持度的计算函数

        #创建连接数据，这一步耗时、耗内存最严重。当数据集较大时，可以考虑并行运算优化。
        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) #计算连接后的支持度
        column = list(support_series_2[support_series_2 > support].index) #新一轮支持度筛选
        support_series = support_series.append(support_series_2)
        column2 = []
        
        for i in column: #遍历可能的推理，如{A,B,C}究竟是A+B-->C还是B+C-->A还是C+A-->B？
            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]) #定义置信度序列
        
        for i in column2: #计算置信度序列
            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: #置信度筛选
            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) #结果整理，输出
    end = time.clock()
    print(u'\n搜索完成，用时：%0.2f秒' %(end-start))
    print(u'\n结果为：')
    print(result)
    
    return result

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

Test dataset: apriori.txt

Sample output:

apriori