Apriori algorithm explanation

I found an implementation for the Apriori algorithm on the Interne开发者_如何学Pythont but there is something I can't understand in it. I hope one could help me out.

# region----- Apriori-gen
//Generates Candidate Itemsets
static ArrayList AprioriGen (ArrayList L)
{
    ArrayList Lk = new ArrayList ();    //List to store generated Candidate Itemsets
    Regex r = new Regex (",");
    for (int i = 0 ; i <L.Count ; i++)
    {
        string [] subL1 = r.Split (L [i]. ToString ());
        for (int j = i+1 ; j <L.Count ; j++)
        {
            string [] subL2 = r.Split (L [j]. ToString ());
            // Compare two items in L, and set them in temp
            string temp = L [j]. ToString ();   //store two key sets
            for (int m = 0; m <subL1.Length; m++)
            {
                bool subL1mInsubL2 = false;
                for (int n = 0; n <subL2.Length; n++)
                {
                    if (subL1 [m] == subL2 [n]) subL1mInsubL2 = true;
                }
                if (subL1mInsubL2 == false) temp = temp + "," + subL1 [m];
            }

            // If temp contains the entry for L in the (itemset size +1)
            //and the focus is not with the candidates seeking the same items set temp
            string [] subTemp = r.Split (temp);
            if (subTemp.Length == subL1.Length + 1)
            {
                bool isExists = false;
                for (int m = 0; m <Lk.Count; m++)
                {
                    bool isContained = true;
                    for (int n = 0; n <subTemp.Length; n++)
                    {
                        if (!Lk[m].ToString().Contains(subTemp [n]) ) isContained = false;
                    }
                    if (isContained == true) isExists = true;
                }
                if (isExists == false) Lk.Add(temp);
            }
        }
    }
    return Lk;
}
# endregion----- Apriori-gen

Now I know of the Apriori Gen process where we make itemsets into larger item sets by joining them together. But I can't see how this is implemented in the previous code. Why did we use temp? How do isExists and isContained help us? What's going on exactly in these two parts of code?

First, there is two loops:

for (int i = 0 ; i

These loops are used to compare each pairs of itemsets of a given size together. The first thing that I notice about this Apriori implementation is that it is not efficient because if the itemsets are lexically ordered, then you don't need to compare each itemset with each other. You can stop earlier. But this code does not have this optimization.

The second big problem that I see with this code is that the candidates are stored as Strings. It would be much more efficient to store it as an array of Integers. Storing the itemset as String including "," and spliting them to separate numbers is a very bad design decision, that will waste memory and execution time. For a data mining algorithm, the implementation should be as efficient as possible. In my opinion, this means that the code that you are looking at has been written by a novice.

About your question, the variable "temp" is used to store a new candidate. Remind that a candidate is the concatenation of two itemsets. To combine two itemsets, you need to check that they share all items except one. For example, if you have two itemsets ABC and ABD, these two itemsets will generate a new candidates that will be ABCD. But if two itemsets have more than one different item, you should not combine them. That is what the code that you show me is trying to do by .

If you want to look at some efficient Apriori implementation, you can check my website (http://www.philippe-fournier-viger.com/spmf/ ), I provide some efficient Java implementations. If you want some efficient c++ implementations, then look at : http://fimi.ua.ac.be/src/ .

Description : Simple Python implementation of the Apriori Algorithm

Usage:

$python apriori.py -f DATASET.csv -s minSupport  -c minConfidence

$python apriori.py -f DATASET.csv -s 0.15 -c 0.6

import sys

from itertools import chain, combinations
from collections import defaultdict
from optparse import OptionParser


def subsets(arr):
    """ Returns non empty subsets of arr"""
    return chain(*[combinations(arr, i + 1) for i, a in enumerate(arr)])


def returnItemsWithMinSupport(itemSet, transactionList, minSupport, freqSet):
        """calculates the support for items in the itemSet and returns a subset
       of the itemSet each of whose elements satisfies the minimum support"""
        _itemSet = set()
        localSet = defaultdict(int)

        for item in itemSet:
                for transaction in transactionList:
                        if item.issubset(transaction):
                                freqSet[item] += 1
                                localSet[item] += 1

        for item, count in localSet.items():
                support = float(count)/len(transactionList)

                if support >= minSupport:
                        _itemSet.add(item)

        return _itemSet


def joinSet(itemSet, length):
        """Join a set with itself and returns the n-element itemsets"""
        return set([i.union(j) for i in itemSet for j in itemSet if len(i.union(j)) == length])


def getItemSetTransactionList(data_iterator):
    transactionList = list()
    itemSet = set()
    for record in data_iterator:
        transaction = frozenset(record)
        transactionList.append(transaction)
        for item in transaction:
            itemSet.add(frozenset([item]))              # Generate 1-itemSets
    return itemSet, transactionList


def runApriori(data_iter, minSupport, minConfidence):
    """
    run the apriori algorithm. data_iter is a record iterator
    Return both:
     - items (tuple, support)
     - rules ((pretuple, posttuple), confidence)
    """
    itemSet, transactionList = getItemSetTransactionList(data_iter)

    freqSet = defaultdict(int)
    largeSet = dict()
    # Global dictionary which stores (key=n-itemSets,value=support)
    # which satisfy minSupport

    assocRules = dict()
    # Dictionary which stores Association Rules

    oneCSet = returnItemsWithMinSupport(itemSet,
                                        transactionList,
                                        minSupport,
                                        freqSet)

    currentLSet = oneCSet
    k = 2
    while(currentLSet != set([])):
        largeSet[k-1] = currentLSet
        currentLSet = joinSet(currentLSet, k)
        currentCSet = returnItemsWithMinSupport(currentLSet,
                                                transactionList,
                                                minSupport,
                                                freqSet)
        currentLSet = currentCSet
        k = k + 1

    def getSupport(item):
            """local function which Returns the support of an item"""
            return float(freqSet[item])/len(transactionList)

    toRetItems = []
    for key, value in largeSet.items():
        toRetItems.extend([(tuple(item), getSupport(item))
                           for item in value])

    toRetRules = []
    for key, value in largeSet.items()[1:]:
        for item in value:
            _subsets = map(frozenset, [x for x in subsets(item)])
            for element in _subsets:
                remain = item.difference(element)
                if len(remain) > 0:
                    confidence = getSupport(item)/getSupport(element)
                    if confidence >= minConfidence:
                        toRetRules.append(((tuple(element), tuple(remain)),
                                           confidence))
    return toRetItems, toRetRules


def printResults(items, rules):
    """prints the generated itemsets sorted by support and the confidence rules sorted by confidence"""
    for item, support in sorted(items, key=lambda (item, support): support):
        print "item: %s , %.3f" % (str(item), support)
    print "\n------------------------ RULES:"
    for rule, confidence in sorted(rules, key=lambda (rule, confidence): confidence):
        pre, post = rule
        print "Rule: %s ==> %s , %.3f" % (str(pre), str(post), confidence)


def dataFromFile(fname):
        """Function which reads from the file and yields a generator"""
        file_iter = open(fname, 'rU')
        for line in file_iter:
                line = line.strip().rstrip(',')                         # Remove trailing comma
                record = frozenset(line.split(','))
                yield record


if __name__ == "__main__":

    optparser = OptionParser()
    optparser.add_option('-f', '--inputFile',
                         dest='input',
                         help='filename containing csv',
                         default=None)
    optparser.add_option('-s', '--minSupport',
                         dest='minS',
                         help='minimum support value',
                         default=0.15,
                         type='float')
    optparser.add_option('-c', '--minConfidence',
                         dest='minC',
                         help='minimum confidence value',
                         default=0.6,
                         type='float')

    (options, args) = optparser.parse_args()

    inFile = None
    if options.input is None:
            inFile = sys.stdin
    elif options.input is not None:
            inFile = dataFromFile(options.input)
    else:
            print 'No dataset filename specified, system with exit\n'
            sys.exit('System will exit')

    minSupport = options.minS
    minConfidence = options.minC

    items, rules = runApriori(inFile, minSupport, minConfidence)

    printResults(items, rules)