2
\$\begingroup\$

Let \$I = \{ i_1, i_2, \dots, i_d \}\$ be the set of all possible items, and \$T = \{ t_1, t_2, \dots, t_N \}\$ be the (multi)set of all given transactions, where \$t_i \subseteq I\$ for all \$i \in \{ 1, 2, \dots, N \}\$. We call any such \$t_i\$ an itemset. Given an itemset \$X \subseteq I\$, its support count is $$ \sigma(X) = \big| \{ t_i \colon X \subseteq t_i, t_i \in T \} \big|, $$ or, in other words, the frequency of \$X\$ over all data \$T\$. An association rule is denoted by \$X \longrightarrow Y\$, where \$X \cap Y = \emptyset\$ and \$X,Y \neq \emptyset\$. Informally, an association rule tells us that with high enough probability choosing \$X\$ implies having \$Y\$ as well. For example, $$ \{ \text{diapers}\} \longrightarrow \{ \text{beer, cigarettes, condoms} \}. $$

Support (note the absence of word count) of an itemset \$X\$ is $$ s(X) = \frac{\sigma(X)}{N}, $$ and confidence of an association rule \$X \longrightarrow Y\$ is $$ c(X \longrightarrow Y) = \frac{\sigma(X \cup Y)}{\sigma(X)}. $$ The concept of confidence may be considered to be a statistical probability of taking \$Y\$ having taken \$X\$.

Our association rule data mining task has two parameters and two stages:

  1. Ask the user the value of minimum support and generate all itemsets whose support is no less than the minimum one (such itemsets are colloquially called frequent),
  2. Ask the user the value of minimum confidence and generate all association rules with confidence no less than the lower bound using the frequent itemsets from the above step.

My code is as follows:

AssociationRule.java:

package net.coderodde.mining.associationrules;

import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;
import java.util.Objects;
import java.util.Set;

/**
 * This class holds an association rule and its confidence.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Apr 10, 2016)
 * @param <I> the actual item type.
 */
public class AssociationRule<I> {

    private final Set<I> antecedent = new HashSet<>();
    private final Set<I> consequent = new HashSet<>();
    private double confidence;

    public AssociationRule(Set<I> antecedent, 
                           Set<I> consequent, 
                           double confidence) {
        Objects.requireNonNull(antecedent, "The rule antecedent is null.");
        Objects.requireNonNull(consequent, "The rule consequent is null.");
        this.antecedent.addAll(antecedent);
        this.consequent.addAll(consequent);
        this.confidence = confidence;
    }

    public AssociationRule(Set<I> antecedent, Set<I> consequent) {
        this(antecedent, consequent, Double.NaN);
    }

    public Set<I> getAntecedent() {
        return Collections.<I>unmodifiableSet(antecedent);
    }

    public Set<I> getConsequent() {
        return Collections.<I>unmodifiableSet(consequent);
    }

    public double getConfidence() {
        return confidence;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();

        sb.append(Arrays.toString(antecedent.toArray()));
        sb.append(" -> ");
        sb.append(Arrays.toString(consequent.toArray()));
        sb.append(": ");
        sb.append(confidence);

        return sb.toString();
    }

    @Override
    public int hashCode() {
        return antecedent.hashCode() ^ consequent.hashCode();
    }

    @Override
    public boolean equals(Object obj) {
        AssociationRule<I> other = (AssociationRule<I>) obj;

        return antecedent.equals(other.antecedent) &&
               consequent.equals(other.consequent);
    }
}

FrequentItemsetData.java:

package net.coderodde.mining.associationrules;

import java.util.List;
import java.util.Map;
import java.util.Set;

/**
 * This class holds the result information of a data-mining task.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Sep 14, 2015)
 */
public class FrequentItemsetData<I> {

    private final List<Set<I>> frequentItemsetList;
    private final Map<Set<I>, Integer> supportCountMap;
    private final double minimumSupport;
    private final int numberOfTransactions;

    FrequentItemsetData(List<Set<I>> frequentItemsetList,
                        Map<Set<I>, Integer> supportCountMap,
                        double minimumSupport,
                        int transactionNumber) {
        this.frequentItemsetList = frequentItemsetList;
        this.supportCountMap = supportCountMap;
        this.minimumSupport = minimumSupport;
        this.numberOfTransactions = transactionNumber;
    }

    public List<Set<I>> getFrequentItemsetList() {
        return frequentItemsetList;
    }

    public Map<Set<I>, Integer> getSupportCountMap() {
        return supportCountMap;
    }

    public double getMinimumSupport() {
        return minimumSupport;
    }

    public int getTransactionNumber() {
        return numberOfTransactions;
    }

    public double getSupport(Set<I> itemset) {
        return 1.0 * supportCountMap.get(itemset) / numberOfTransactions;
    }
}

AssociationRuleGenerator.java:

package net.coderodde.mining.associationrules;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Objects;
import java.util.Set;

/**
 * This class implements the algorithm for mining association rules out of 
 * frequent itemsets.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Apr 10, 2016)
 * @param <I> the actual item type.
 */
public class AssociationRuleGenerator<I> {

    public List<AssociationRule<I>> 
        mineAssociationRules(FrequentItemsetData<I> data,
                             double minimumConfidence) {
        Objects.requireNonNull(data, "The frequent itemset data is null.");
        checkMinimumConfidence(minimumConfidence);

        Set<AssociationRule<I>> resultSet = new HashSet<>();

        for (Set<I> itemset : data.getFrequentItemsetList()) {
            if (itemset.size() < 2) {
                // Any association rule requires at least one item in the 
                // antecedent, and at least one item in the consequent. An
                // itemset containing less than two items cannot satisfy this
                // requirement; skip it.
                continue;
            }

            // Generate the basic association rules out of current itemset.
            // An association rule is basic iff its consequent contains only one
            // item.
            Set<AssociationRule<I>> basicAssociationRuleSet = 
                    generateAllBasicAssociationRules(itemset, data);

            generateAssociationRules(itemset,
                                     basicAssociationRuleSet,
                                     data,
                                     minimumConfidence,
                                     resultSet);
        }

        List<AssociationRule<I>> ret = new ArrayList<>(resultSet);

        Collections.sort(ret, (a1, a2) -> { 
                               return Double.compare(a2.getConfidence(),
                                                     a1.getConfidence()); 
        });

        return ret;
    }

    private void generateAssociationRules(Set<I> itemset,
                                          Set<AssociationRule<I>> ruleSet,
                                          FrequentItemsetData<I> data,
                                          double minimumConfidence,
                                          Set<AssociationRule<I>> collector) {
        if (ruleSet.isEmpty()) {
            return;
        }

        // The size of the itemset.
        int k = itemset.size(); 
        // The size of the consequent of the input rules.
        int m = ruleSet.iterator().next().getConsequent().size();

        // Test whether we can pull one more item from the antecedent to 
        // consequent.
        if (k > m + 1) {
            Set<AssociationRule<I>> nextRules =
                    moveOneItemToConsequents(itemset, ruleSet, data);

            Iterator<AssociationRule<I>> iterator = nextRules.iterator();

            while (iterator.hasNext()) {
                AssociationRule<I> rule = iterator.next();

                if (rule.getConfidence() >= minimumConfidence) {
                    collector.add(rule);
                } else {
                    iterator.remove();
                }
            }

            generateAssociationRules(itemset,
                                     nextRules,
                                     data,
                                     minimumConfidence,
                                     collector);
        }
    }

    private Set<AssociationRule<I>> 
        moveOneItemToConsequents(Set<I> itemset, 
                                 Set<AssociationRule<I>> ruleSet,
                                 FrequentItemsetData<I> data) {
        Set<AssociationRule<I>> output = new HashSet<>();
        Set<I> antecedent = new HashSet<>();
        Set<I> consequent = new HashSet<>();
        double itemsetSupportCount = data.getSupportCountMap().get(itemset);

        // For each rule ...
        for (AssociationRule<I> rule : ruleSet) {
            antecedent.clear();
            consequent.clear();
            antecedent.addAll(rule.getAntecedent());
            consequent.addAll(rule.getConsequent());

            // ... move one item from its antecedent to its consequnt.
            for (I item : rule.getAntecedent()) {
                antecedent.remove(item);
                consequent.add(item);

                int antecedentSupportCount = data.getSupportCountMap()
                                                 .get(antecedent);
                AssociationRule<I> newRule = 
                        new AssociationRule<>(
                                antecedent,
                                consequent,
                                itemsetSupportCount / antecedentSupportCount);

                output.add(newRule);

                antecedent.add(item);
                consequent.remove(item);
            }
        }

        return output;
    }

   /**
    * Given a frequent itemset of size {@code n}, generates and returns all 
    * {@code n} possible association rules with consequent of size one.
    * 
    * @param itemset the itemset.
    * @return a set of association rules with consequents of size one.
    */
    private Set<AssociationRule<I>> 
        generateAllBasicAssociationRules(Set<I> itemset,
                                         FrequentItemsetData<I> data) {
        Set<AssociationRule<I>> basicAssociationRuleSet =
                new HashSet<>(itemset.size());

        Set<I> antecedent = new HashSet<>(itemset);
        Set<I> consequent = new HashSet<>(1);

        for (I item : itemset) {
            antecedent.remove(item);
            consequent.add(item);

            int itemsetSupportCount = data.getSupportCountMap().get(itemset);
            int antecedentSupportCount = data.getSupportCountMap()
                                             .get(antecedent);

            double confidence = 1.0 * itemsetSupportCount 
                                    / antecedentSupportCount;

            basicAssociationRuleSet.add(new AssociationRule(antecedent, 
                                                            consequent,
                                                            confidence));
            antecedent.add(item);
            consequent.remove(item);
        }

        return basicAssociationRuleSet;
    }

    private void checkMinimumConfidence(double minimumConfidence) {
        if (Double.isNaN(minimumConfidence)) {
            throw new IllegalArgumentException(
                    "The input minimum confidence is NaN.");
        }

        if (minimumConfidence < 0.0) {
            throw new IllegalArgumentException(
                    "The input minimum confidence is negative: " + 
                    minimumConfidence + ". " +
                    "Must be at least zero.");
        }

        if (minimumConfidence > 1.0) {
            throw new IllegalArgumentException(
                    "The input minimum confidence is too large: " +
                    minimumConfidence + ". " +
                    "Must be at most 1.");
        }
    }
}

AprioriFrequentItemsetGenerator.java:

package net.coderodde.mining.associationrules;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Objects;
import java.util.Set;

/**
 * This class implements the 
 * <a href="https://en.wikipedia.org/wiki/Apriori_algorithm">Apriori algorithm</a> 
 * for frequent itemset generation.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Sep 14, 2015)
 * @param <I> the actual item type.
 */
public class AprioriFrequentItemsetGenerator<I> {

    /**
     * Generates the frequent itemset data.
     * 
     * @param transactionList the list of transactions to mine.
     * @param minimumSupport  the minimum support.
     * @return the object describing the result of this task.
     */
    public FrequentItemsetData<I> generate(List<Set<I>> transactionList, 
                                           double minimumSupport) {
        Objects.requireNonNull(transactionList, "The itemset list is empty.");
        checkSupport(minimumSupport);

        if (transactionList.isEmpty()) {
            return null;
        }

        // Maps each itemset to its support count. Support count is simply the 
        // number of times an itemset appeares in the transaction list.
        Map<Set<I>, Integer> supportCountMap = new HashMap<>();

        // Get the list of 1-itemsets that are frequent.
        List<Set<I>> frequentItemList = findFrequentItems(transactionList,
                                                          supportCountMap,
                                                          minimumSupport);


        // Maps each 'k' to the list of frequent k-itemsets. 
        Map<Integer, List<Set<I>>> map = new HashMap<>();
        map.put(1, frequentItemList);

        // 'k' denotes the cardinality of itemsets processed at each iteration
        // of the following loop.
        int k = 1;

        do {
            ++k;

            // First generate the candidates.
            List<Set<I>> candidateList = 
                    generateCandidates(map.get(k - 1));

            for (Set<I> transaction : transactionList) {
                List<Set<I>> candidateList2 = subset(candidateList,
                                                     transaction);

                for (Set<I> itemset : candidateList2) {
                    supportCountMap.put(itemset,
                                        supportCountMap.getOrDefault(itemset, 
                                                                     0) + 1);
                }
            }

            map.put(k, getNextItemsets(candidateList,
                                       supportCountMap, 
                                       minimumSupport, 
                                       transactionList.size()));

        } while (!map.get(k).isEmpty());

        return new FrequentItemsetData<>(extractFrequentItemsets(map),
                                         supportCountMap,
                                         minimumSupport,
                                         transactionList.size());
    }

    /**
     * This method simply concatenates all the lists of frequent itemsets into
     * one list.
     * 
     * @param  map the map mapping an itemset size to the list of frequent
     *             itemsets of that size.
     * @return the list of all frequent itemsets.
     */
    private List<Set<I>>
        extractFrequentItemsets(Map<Integer, List<Set<I>>> map) {
        List<Set<I>> ret = new ArrayList<>();

        for (List<Set<I>> itemsetList : map.values()) {
            ret.addAll(itemsetList);
        }

        return ret;
    }

    /**
     * This method gathers all the frequent candidate itemsets into a single 
     * list.
     * 
     * @param candidateList   the list of candidate itemsets.
     * @param supportCountMap the map mapping each itemset to its support count.
     * @param minimumSupport  the minimum support.
     * @param transactions    the total number of transactions.
     * @return a list of frequent itemset candidates.
     */
    private List<Set<I>> getNextItemsets(List<Set<I>> candidateList,
                                         Map<Set<I>, Integer> supportCountMap,
                                         double minimumSupport,
                                         int transactions) {
        List<Set<I>> ret = new ArrayList<>(candidateList.size());

        for (Set<I> itemset : candidateList) {
            if (supportCountMap.containsKey(itemset)) {
                int supportCount = supportCountMap.get(itemset);
                double support = 1.0 * supportCount / transactions;

                if (support >= minimumSupport) {
                    ret.add(itemset);
                }
            }
        }

        return ret;
    }

    /**
     * Computes the list of itemsets that are all subsets of 
     * {@code transaction}.
     * 
     * @param candidateList the list of candidate itemsets.
     * @param transaction   the transaction to test against.
     * @return the list of itemsets that are subsets of {@code transaction}
     *         itemset.
     */
    private List<Set<I>> subset(List<Set<I>> candidateList, 
                                Set<I> transaction) {
        List<Set<I>> ret = new ArrayList<>(candidateList.size());

        for (Set<I> candidate : candidateList) {
            if (transaction.containsAll(candidate)) {
                ret.add(candidate);
            }
        }

        return ret;
    }

    /**
     * Generates the next candidates. This is so called F_(k - 1) x F_(k - 1) 
     * method.
     * 
     * @param itemsetList the list of source itemsets, each of size <b>k</b>.
     * @return the list of candidates each of size <b>k + 1</b>.
     */
    private List<Set<I>> generateCandidates(List<Set<I>> itemsetList) {
        List<List<I>> list = new ArrayList<>(itemsetList.size());

        for (Set<I> itemset : itemsetList) {
            List<I> l = new ArrayList<>(itemset);
            Collections.<I>sort(l, ITEM_COMPARATOR);
            list.add(l);
        }

        int listSize = list.size();

        List<Set<I>> ret = new ArrayList<>(listSize);

        for (int i = 0; i < listSize; ++i) {
            for (int j = i + 1; j < listSize; ++j) {
                Set<I> candidate = tryMergeItemsets(list.get(i), list.get(j));

                if (candidate != null) {
                    ret.add(candidate);
                }
            }
        }

        return ret;
    }

    /**
     * Attempts the actual construction of the next itemset candidate.
     * @param itemset1 the list of elements in the first itemset.
     * @param itemset2 the list of elements in the second itemset.
     * 
     * @return a merged itemset candidate or {@code null} if one cannot be 
     *         constructed from the input itemsets.
     */
    private Set<I> tryMergeItemsets(List<I> itemset1, List<I> itemset2) {
        int length = itemset1.size();

        for (int i = 0; i < length - 1; ++i) {
            if (!itemset1.get(i).equals(itemset2.get(i))) {
                return null;
            }
        }

        if (itemset1.get(length - 1).equals(itemset2.get(length - 1))) {
            return null;
        }

        Set<I> ret = new HashSet<>(length + 1);

        for (int i = 0; i < length - 1; ++i) {
            ret.add(itemset1.get(i));
        }

        ret.add(itemset1.get(length - 1));
        ret.add(itemset2.get(length - 1));
        return ret;
    }

    private static final Comparator ITEM_COMPARATOR = new Comparator() {

        @Override
        public int compare(Object o1, Object o2) {
            return ((Comparable) o1).compareTo(o2);
        }

    };

    /**
     * Computes the frequent itemsets of size 1.
     * 
     * @param itemsetList     the entire database of transactions.
     * @param supportCountMap the support count map to which to write the 
     *                        support counts of each item.
     * @param minimumSupport  the minimum support.
     * @return                the list of frequent one-itemsets.
     */
    private List<Set<I>> findFrequentItems(List<Set<I>> itemsetList,
                                           Map<Set<I>, Integer> supportCountMap,
                                           double minimumSupport) {
        Map<I, Integer> map = new HashMap<>();

        // Count the support counts of each item.
        for (Set<I> itemset : itemsetList) {
            for (I item : itemset) {
                Set<I> tmp = new HashSet<>(1);
                tmp.add(item);

                supportCountMap.put(tmp, 
                                    supportCountMap.getOrDefault(tmp, 0) + 1);

                map.put(item, map.getOrDefault(item, 0) + 1);
            }
        }

        List<Set<I>> frequentItemsetList = new ArrayList<>();

        for (Map.Entry<I, Integer> entry : map.entrySet()) {
            if (1.0 * entry.getValue() / itemsetList.size() >= minimumSupport) {
                Set<I> itemset = new HashSet<>(1);
                itemset.add(entry.getKey());
                frequentItemsetList.add(itemset);
            }
        }

        return frequentItemsetList;
    }

    private void checkSupport(double support) {
        if (Double.isNaN(support)) {
            throw new IllegalArgumentException("The input support is NaN.");
        }

        if (support > 1.0) {
            throw new IllegalArgumentException(
                    "The input support is too large: " + support + ", " +
                    "should be at most 1.0");
        }

        if (support < 0.0) {
            throw new IllegalArgumentException(
                    "The input support is too small: " + support + ", " +
                    "should be at least 0.0");
        }
    }
}

Demo.java:

package net.coderodde.mining.associationrules;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Demo {

    public static void main(String[] args) {
        demo();
    }

    private static void demo() {
        AprioriFrequentItemsetGenerator<String> generator =
                new AprioriFrequentItemsetGenerator<>();

        List<Set<String>> itemsetList = new ArrayList<>();

        itemsetList.add(new HashSet<>(Arrays.asList("a", "b")));
        itemsetList.add(new HashSet<>(Arrays.asList("b", "c", "d")));
        itemsetList.add(new HashSet<>(Arrays.asList("a", "c", "d", "e")));
        itemsetList.add(new HashSet<>(Arrays.asList("a", "d", "e")));
        itemsetList.add(new HashSet<>(Arrays.asList("a", "b", "c")));

        itemsetList.add(new HashSet<>(Arrays.asList("a", "b", "c", "d")));
        itemsetList.add(new HashSet<>(Arrays.asList("a")));
        itemsetList.add(new HashSet<>(Arrays.asList("a", "b", "c")));
        itemsetList.add(new HashSet<>(Arrays.asList("a", "b", "d")));
        itemsetList.add(new HashSet<>(Arrays.asList("b", "c", "e")));

        long startTime = System.nanoTime();
        FrequentItemsetData<String> data = generator.generate(itemsetList, 0.02);
        long endTime = System.nanoTime();

        int i = 1;

        System.out.println("--- Frequent itemsets ---");

        for (Set<String> itemset : data.getFrequentItemsetList()) {
            System.out.printf("%2d: %9s, support: %1.1f\n",
                              i++, 
                              itemset,
                              data.getSupport(itemset));
        }

        System.out.printf("Mined frequent itemset in %d milliseconds.\n", 
                          (endTime - startTime) / 1_000_000);

        startTime = System.nanoTime();
        List<AssociationRule<String>> associationRuleList = 
                new AssociationRuleGenerator<String>()
                        .mineAssociationRules(data, 0.4);
        endTime = System.nanoTime();

        i = 1;

        System.out.println();
        System.out.println("--- Association rules ---");

        for (AssociationRule<String> rule : associationRuleList) {
            System.out.printf("%2d: %s\n", i++, rule);
        }

        System.out.printf("Mined association rules in %d milliseconds.\n",
                          (endTime - startTime) / 1_000_000);
    }
}

Any critique is much appreciated.

\$\endgroup\$
1
\$\begingroup\$

Some general comments as I'm not to sure about all of the math.

  • AssociationRule#confidence should be made final to stay consistent with your project. Not using final will confuse the reader on the purpose of your variable.

  • AssociationRule#equals requires a null check and type check before casting to avoid throwing an exception.

    @Override
    public boolean equals(final Object obj) {
        if (obj == this) {
            return true;
        }
        if (!(obj instanceof AssociationRule<I>)) {
            return false;
        }
    
        final AssociationRule<I> other = (AssociationRule<I>) obj;
    
        return antecedent.equals(other.antecedent) &&
               consequent.equals(other.consequent);
    }
    
  • Be very wary of using a Set as the key for a Map. If a key equals or hashCode results change, then the Map behavior will be undefined. This is why in most code you will see immutable objects used as keys. At a minimum make sure your API hides any reference to these keys from your user.

  • AssociationRuleGenerator#mineAssociationRules you can use java 8 streams to get a sorted list instead of making a copy and using the collections library

    return resultSet.stream()
            .sorted((a1, a2) -> Double.compare(a2.getConfidence(), a1.getConfidence()))
            .collect(Collectors.toList());
    

Personal nitpicks:

  • Use final when possible in parameters and local variables. It makes code much easier to understand on the first read when you aren't looking to see if values are replaced.

  • It's very hard to read some of your method signatures. Consider placing your first parameter on a newline when signatures need to be multiline

    private Set<AssociationRule<I>> generateAllBasicAssociationRules(
            final Set<I> itemset,
            final FrequentItemsetData<I> data) {
        ...
    
\$\endgroup\$
0
\$\begingroup\$

I would like to add more details about the AssociationRule#equals method. The order of items in antecedent set may be different from the order of items in the otherAntecedent set, so the actual implementation will return false even if the items are the same, but only the order is different. The same rule applies for consequent set.

Below is my version of equals method (of course, the generic which will replace I must also have equals overridden).

@Override
public boolean equals(Object otherObject) {
    if (!(otherObject instanceof AssociationRule)) {
        return false;
    }
    AssociationRule<I> otherAssociationRule = (AssociationRule<I>) otherObject;
    if (otherAssociationRule.getAntecedent().size() != antecedent.size() ||
            otherAssociationRule.getConsequent().size() != consequent.size()) {
        return false;
    }
    for (I i : antecedent) {
        if (!otherAssociationRule.getAntecedent().contains(i)) {
            return false;
        }
    }
    for (I i : consequent) {
        if (!otherAssociationRule.getConsequent().contains(i)) {
            return false;
        }
    }
    return true;
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.