How to Speed Up the Apriori Framework Based On to Generate Only Association Rules Which Consequents (Right Hand Side) Are One Element of the Data Set?

user_4915693 0
Viewed 2080

I have a csv file with 600 000 rows and 15 columns "Col1, Col2 ... COl15". I want to generate association rules where only the right hand side has only values from col15. I am using the apriori implementation from here

It calculates the minSupport for each itemset this way : 

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

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)
        #print itemSet

        for item in itemSet:
            #print "I am here", list(item)


            for transaction in transactionList:
                if item.issubset(transaction):
                    freqSet[item] += 1
                    localSet[item] += 1
        print "Done half"
        for item, count in localSet.items():
            support = float(count)/len(transactionList)

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

        return _itemSet

But for the many rows I have, it would take a lot of time, Since I want the RHS to be constrained to only having values from a specific column(Col15), can I make the implementation faster by somehow cutting down on the frequent itemsets? One of the other ways is to filter the rules at the end, but it would have the same time complexity. Or is there some other implementation/library which helps me speed up things?

apriori machine-learning data-mining python
2 Answers

  1. Split your data set, based on the value in your column 15, which will be your right hand side RHS. So if you have 5 different values in that column, you get 5 data sets now. Remove the last column each, which is constant now.

  2. Compute frequent itemsets (not association rules) on the other columns only, by Apriori on each subset (faster!). But you will still need a much better implementation than that random github version you linked. It only needs FIMs, not rules!

  3. Compose frequent itemset with partition key into an association rule, (FIS -> RHS) and evaluate like an association rule with your preferred metric.

This is a lot faster, because it will not generate frequent itemsets that span multiple col15 keys. Within each partition, all remaining data is relevant for your objective. Plus, it works with unmodified Apriori FIM generation.

user_10603500

no. there is no way to speed up the complexity of the apriori framework in order to generate association rules with only one specific element of the data set as the consequent. however you could speed up the computing time a bit.

the apriori framework consists of two steps. first step is to generate the frequent itemsets. second step is to generate of these frequent itemsets the association rules. to speed up the framework there is little use to look into the generation of the association rules. the bulk of the complexity of the apriori algorithm lies within the extraction of the frequent itemsets.

the apriori algorithm extracts frequent itemsets in the following way:

  1. uniquify all items
  2. get of those uniquify items all 1 length frequent itemsets
  3. combine those 1 length frequent itemsets to 2 length itemsets
  4. get of those 2 length itemsets all 2 length frequent itemsets
  5. combine those n length frequent itemsets to n+1 length itemsets
  6. get of those n+1 itemsets all n+1 frequent itemsets
  7. repeat 5. and 6. until there are no frequent itemsets to get out of the n+1 combined itemsets

of those generated n+1 length frequent itemsets the association rules are generated. the generation of the association rules is fairly simple:

  1. combine the frequent itemsets to association rules
  2. check the generated association rule against the confidence level
  3. if the association rule lies over the confidence level it is a strong association rule and therefore a valid association rule

the element of the data set which is supposed to be the consequent of all generated association rules is in the following called x.

first step in order to speed up the computation is to cutomize step 1 the extraction of the frequent itemsets. in step 1.2 is the 1 length frequent itemset {(x)} to be removed from the result set of 1 lenght frequent itemsets. if the element is not be extacted as a frequent itemset in step 1.2 the algorithm is supposed to stop. because then there can not be association rules with the element as a consequent. an association rule consists of n length frequent itemsets.

therefore the result of step 1 the extraction of the frequent itemsets contains only those n length frequent itemsets which are suitable to be an antecedent for an association rule which consequent can only be {(x)}. these are those frequent itemsets which does not contain {(x)}. and this saves computational time because there is one 1 length frequent itemset less of which are n length itemsets are to be combined and to be checked against the support level if the itemset is a frequent itemset.

second step in order to speed up the computation is to cutomize step 2 the generation of the association rules. in step 2.1 are only association rules to be generated which have as the consequent {(x)}. the assoction can be formed like take the result of the frequent itemsets extraction and combine each frequent itemset as the antecedent with {(x)} as the consequent to an association rule. therefore an association rule would like ({(n length frequent itemset)} -> {(x)}).

but to really speed up the computation use another alorithm to extract the freuqent itemsets. the fp-growth algorithm is already a way faster. the fastest algorithm to extraxt freuquent itemsets is up to date the prepost+ algorithm.

a neat python library with algorithms to extract frequent itemsets is this one.

tl;dr: complexity stays the same. computing time can be improved. overall another faster algorithm should be used instead of the apriori like the fp-growth.

user_57677440
Related