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:
- 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),
- 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.
