Apriori Algorithm

• Download demo - 19.9 KB
• Download source code - 43.4 KB

Introduction

In data mining, Apriori is a classic algorithm for learning association rules. Apriori is designed to operate on databases containing transactions (for example, collections of items bought by customers, or details of a website frequentation).

Other algorithms are designed for finding association rules in data having no transactions (Winepi and Minepi), or having no timestamps (DNA sequencing).

Overview

The whole point of the algorithm (and data mining, in general) is to extract useful information from large amounts of data. For example, the information that a customer who purchases a keyboard also tends to buy a mouse at the same time is acquired from the association rule below:

Keyboard -> Mouse [support = 6%, confidence = 70%]

Support: The percentage of task-relevant data transactions for which the pattern is true.

Support (Keyboard -> Mouse) =

Confidence: The measure of certainty or trustworthiness associated with each discovered pattern.

Confidence (Keyboard -> Mouse) =

The algorithm aims to find the rules which satisfy both a minimum support threshold and a minimum confidence threshold (Strong Rules).

• Item: article in the basket.
• Itemset: a group of items purchased together in a single transaction.

How Apriori Works

1. Find all frequent itemsets:
• Get frequent items:
• Items whose occurrence in database is greater than or equal to the min.support threshold.
• Get frequent itemsets:
• Generate candidates from frequent items.
• Prune the results to find the frequent itemsets.
2. Generate strong association rules from frequent itemsets
• Rules which satisfy the min.support and min.confidence threshold.

High Level Design

Low Level Design

Using the Code

Tricky Part 1: Generating Candidates

private Dictionary<string, double> GenerateCandidates(Dictionary<string, 
                                   double> dic_FrequentItems)
{
    Dictionary<string, double> dic_CandidatesReturn = new Dictionary<string, double>();
    for (int i = 0; i < dic_FrequentItems.Count - 1; i++)
    {
        string strFirstItem = Alphabetize(dic_FrequentItems.Keys.ElementAt(i));
        for (int j = i + 1; j < dic_FrequentItems.Count; j++)
        {
            string strSecondItem = Alphabetize(dic_FrequentItems.Keys.ElementAt(j));
            string strGeneratedCandidate = GetCandidate(strFirstItem, strSecondItem);
            if (strGeneratedCandidate != string.Empty)
            {
                strGeneratedCandidate = Alphabetize(strGeneratedCandidate);
                double dSupport = GetSupport(strGeneratedCandidate);
                dic_CandidatesReturn.Add(strGeneratedCandidate, dSupport);
            }
        }
    }
    return dic_CandidatesReturn;
}

private string GetCandidate(string strFirstItem, string strSecondItem)
{
    int nLength = strFirstItem.Length;
    if (nLength == 1)
    {
        return strFirstItem + strSecondItem;
    }
    else
    {
        string strFirstSubString = strFirstItem.Substring(0, nLength - 1);
        string strSecondSubString = strSecondItem.Substring(0, nLength - 1);
        if (strFirstSubString == strSecondSubString)
        {
            return strFirstItem + strSecondItem[nLength - 1];
        }
        else
            return string.Empty;
    }
}

Tricky Part 2: Generating Rules

private List<clssRules> GenerateRules()
{
    List<clssRules> lstRulesReturn = new List<clssRules>();
    foreach (string strItem in m_dicAllFrequentItems.Keys)
    {
        if (strItem.Length > 1)
        {
            int nMaxCombinationLength = strItem.Length / 2;
            GenerateCombination(strItem, nMaxCombinationLength, ref lstRulesReturn);
        }
    }
    return lstRulesReturn;
}

private void GenerateCombination(string strItem, int nCombinationLength, 
             ref List<clssRules> lstRulesReturn)
{
    int nItemLength = strItem.Length;
    if (nItemLength == 2)
    {
        AddItem(strItem[0].ToString(), strItem, ref lstRulesReturn);
        return;
    }
    else if (nItemLength == 3)
    {
        for (int i = 0; i < nItemLength; i++)
        {
            AddItem(strItem[i].ToString(), strItem, ref lstRulesReturn);
        }
        return;
    }
    else
    {
        for (int i = 0; i < nItemLength; i++)
        {
            GetCombinationRecursive(strItem[i].ToString(), strItem, 
                          nCombinationLength, ref lstRulesReturn);
        }
    }
}

private string GetCombinationRecursive(string strCombination, string strItem, 
               int nCombinationLength, ref List<clssRules> lstRulesReturn)
{
    AddItem(strCombination, strItem, ref lstRulesReturn);
    char cLastTokenCharacter = strCombination[strCombination.Length - 1];
    int nLastTokenCharcaterIndex = strCombination.IndexOf(cLastTokenCharacter);
    int nLastTokenCharcaterIndexInParent = strItem.IndexOf(cLastTokenCharacter);
    char cNextCharacter;
    char cLastItemCharacter = strItem[strItem.Length - 1];
    if (strCombination.Length == nCombinationLength)
    {
        if (cLastTokenCharacter != cLastItemCharacter)
        {
            strCombination = strCombination.Remove(nLastTokenCharcaterIndex, 1);
            cNextCharacter = strItem[nLastTokenCharcaterIndexInParent + 1];
            string strNewToken = strCombination + cNextCharacter;
            return (GetCombinationRecursive(strNewToken, strItem, 
                    nCombinationLength, ref lstRulesReturn));
        }
        else
        {
            return string.Empty;
        }
    }
    else
    {
        if (strCombination != cLastItemCharacter.ToString())
        {
            cNextCharacter = strItem[nLastTokenCharcaterIndexInParent + 1];
            string strNewToken = strCombination + cNextCharacter;
            return (GetCombinationRecursive(strNewToken, strItem, 
                    nCombinationLength, ref lstRulesReturn));
        }
        else
        {
            return string.Empty;
        }
    }
}

Example

A database has five transactions. Let the min sup = 50% and min con f = 80%.

Solution

Step 1: Find all Frequent Itemsets

Frequent Itemsets

{A}   {B}   {C}   {E}   {A C}   {B C}   {B E}   {C E}   {B C E}

Step 2: Generate strong association rules from the frequent itemsets

Lattice

Closed Itemset: support of all parents are not equal to the support of the itemset.

Maximal Itemset: all parents of that itemset must be infrequent.

Keep in mind:

Itemset {c} is closed as support of parents (supersets) {A C}:2, {B C}:2, {C D}:1, {C E}:2 not equal support of {c}:3.

And the same for {A C}, {B E} & {B C E}.

Itemset {A C} is maximal as all parents (supersets) {A B C}, {A C D}, {A C E} are infrequent.

And the same for {B C E}.

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)