Aether_Q

While the number of items in the set is greater than 0:
    Construct a list of candidate itemsets of size k
    Check the data to confirm each itemset is frequent
        For each transaction record tran in the dataset:
            For each candidate itemset can:
                Check if can is a subset of tran:
                    If so, increase the count of can
        For each candidate itemset:
            If its support is not less than the minimum value, retain the itemset
    Return the list of all frequent itemsets
    Retain frequent itemsets and construct a list of candidate itemsets of size k+1
        The second theorem of frequent itemsets: the superset of a non-frequent itemset must also be non-frequent

# Auxiliary functions in the Apriori algorithm

def loadDataSet():
    """
    Create a simple dataset for testing
    """
    return [[1,3,4], [2,3,5], [1,2,3,5], [2,5]]

def creatC1(dataSet):
    """
    Input: dataset dataSet
    Output: C1 is the collection of all candidate itemsets of size 1
    Process: First create an empty list C1 to store all unique item values. Then traverse all transaction records in the dataset. For each record, iterate through each item in the record. If an item is not present in C1, add it to C1. Here, we do not simply add each item, but rather add a list containing only that item. This is done to construct a set for each item, as set operations are needed in the subsequent processing of the Apriori algorithm. Python cannot create a set with only one integer, so we must use a list here (interested readers can try it). This is why we use a large list composed of single-item lists. Finally, sort the large list and map each single-element list to frozenset(), returning a list of frozensets.
    Details: Since the algorithm starts by extracting the candidate itemset list from the input data, a special function is needed to handle this, while subsequent itemset lists are stored in a specific format. The format used here is the frozenset type in Python. A frozenset is a "frozen" set, meaning it is immutable and cannot be modified by the user. It is necessary to use frozenset instead of set type because these sets must be used as dictionary keys later, which frozenset allows but set does not.
    """
    C1 = []
    for transaction in dataSet:
        for item in transaction:
            if not [item] in C1:
                C1.append([item])
                
    C1.sort()
    return map(frozenset, C1)

def scanD(D, Ck, minSupport):
    """
    Input: dataset, candidate itemset list Ck, minimum support minSupport of interest
    Output: This function generates Lk from Ck, and also returns a dictionary containing support values for later use.
    Process: The function first creates an empty dictionary ssCnt, then iterates through all transaction records in the dataset and all candidate sets in C1. If a set in C1 is part of a record, the corresponding count in the dictionary is increased. Here, the keys of the dictionary are the sets. After scanning all items in the dataset and all candidate sets, support needs to be calculated. Sets that do not meet the minimum support requirement will not be output. The function will also first construct an empty list that contains sets meeting the minimum support requirement. The next loop iterates through each element in the dictionary and calculates support. If support meets the minimum support requirement, the dictionary element is added to retList, and the function finally returns the support data of the frequent itemsets.
    Details: You can use the statement retList.insert(0,key) to insert any new set at the beginning of the list. Of course, it doesn't have to be at the beginning; this is just to make the list look organized.
    """
    ssCnt = {}
    for tid in D:
        for can in Ck:
            if can.issubset(tid):
                if not ssCnt.has_key(can): ssCnt[can]=1
                else: ssCnt[can] += 1
    numItems = float(len(D))
    retList = []
    supportData = {}
    for key in ssCnt:
        support = ssCnt[key]/numItems
        if support >= minSupport:
            retList.insert(0, key)
        supportData[key] = support
    return retList, supportData


# Apriori Algorithm

def aprioriGen(Lk, k):
    """
    Input: frequent itemset list Lk, number of elements in itemset k
    Output: candidate itemset Ck
    Example: Input {0}, {1}, {2} will generate {0,1}, {0,2}, and {1,2}
    Process: First create an empty list, then calculate the number of elements in Lk. Next, compare each element in Lk with other elements, which can be done using two for loops. Then, take two sets from the list for comparison. If the first k-2 elements of these two sets are equal, merge these two sets into a set of size k.
    Details: The k-2 part may be confusing. Further discussion will clarify the details. When constructing {0,1}, {0,2}, {1,2} from {0}, {1}, {2}, we are actually combining single items together. Now, if we want to use {0,1}, {0,2}, {1,2} to create three-element itemsets, how should we do it? If we merge every two sets, we would get {0,1,2}, {0,1,2}, {0,1,2}. In other words, the same resulting set would be repeated three times. We need to scan the three-element itemset list to get non-repeating results, and we want to ensure the number of iterations is minimized. Now, if we compare the first element of the sets {0,1}, {0,2}, {1,2} and only perform the merge operation on sets with the same first element, what result do we get? {0,1,2}, and only one operation! This way, we do not need to traverse the list to find non-repeating values.
    """
    retList = []
    lenLk = len(Lk)
    for i in range(lenLk):
        for j in range(i+1, lenLk):
            L1 = list(Lk[i])[:k-2]; L2 = list(Lk[j])[:k-2]
            L1.sort(); L2.sort()
            if L1==L2:
                retList.append(Lk[i] | Lk[j])
    return retList

def apriori(dataSet, minSupport = 0.5):
    """
    Input: dataset dataSet, support minSupport
    Output: L contains the list of frequent itemsets that meet the minimum support, suppData is a dictionary containing the support values of the itemsets
    Process: The function will generate a list of candidate itemsets, which is done by first creating C1 and then reading the dataset to convert it into D (a list of sets). The program uses the map function to map set() to each item in the dataSet list. Next, the scanD() function is used to create L1, and L1 is placed in the list L. L will contain L1, L2, L3, etc. Now that we have L1, we will continue to find L2, L3, etc., which can be done using a while loop that creates a larger list of larger itemsets until the next larger itemset is empty. If this sounds a bit confusing, you will see its workflow shortly. First, use aprioriGen() to create Ck, and then use scanD() based on Ck to create Lk. Ck is a candidate itemset list, and then scanD() will traverse Ck, discarding itemsets that do not meet the minimum support requirement. The Lk list is added to L, while increasing the value of k, and repeating the above process. Finally, when Lk is empty, the program returns L and exits.
    """
    C1 = creatC1(dataSet)
    D = map(set, dataSet)
    L1, supportData = scanD(D, C1, minSupport)
    L = [L1]
    k = 2
    while (len(L[k-2]) > 0):
        Ck = aprioriGen(L[k-2], k)
        Lk, supK = scanD(D, Ck, minSupport)
        supportData.update(supK)
        L.append(Lk)
        k += 1
    return L, supportData


# Association Rule Generation Function

def generateRules(L, supportData, minConf=0.7):
    """
    Input: frequent itemset list, dictionary containing support data of those frequent itemsets, minimum confidence threshold
    Output: generates a list of rules containing confidence, which can later be sorted based on confidence
    Process: This function iterates through each frequent itemset in L and creates a list H1 containing single-element sets for each frequent itemset. Since association rules cannot be constructed from single-element itemsets, the rule construction process starts from itemsets containing two or more elements. If starting from the set {0,1,2}, then H1 should be [{0},{1},{2}]. If the number of elements in the frequent itemset exceeds 2, further merging will be considered. The specific merging can be done through the function rulesFromConseq(), which will be discussed in detail later. If the itemset contains only two elements, the function calcConf() will be used to calculate the confidence value.
    """
    bigRuleList = []
    for i in range(1, len(L)):
        for freqSet in L[i]:
            H1 = [frozenset([item]) for item in freqSet]
            if (i > 1):
                rulesFromConseq(freqSet, H1, supportData, bigRuleList, minConf)
            else:
                calcConf(freqSet, H1, supportData, bigRuleList, minConf)
    return bigRuleList

def calcConf(freqSet, H, supportData, brl, minConf=0.7):
    """
    Purpose: Evaluate rules, calculate the confidence of the rules, and find rules that meet the minimum confidence requirement
    Process: The function will return a list of rules that meet the minimum confidence requirement. To store these rules, an empty list prunedH is created. Next, iterate through all itemsets in H and calculate their confidence values. The confidence calculation uses the support data from supportData. By importing this support data, a lot of computation time can be saved. If a rule meets the minimum confidence value, these rules will be output to the screen. The checked rules will also be returned and used in the next function rulesFromConseq(). At the same time, the list brl will also be filled, which is the bigRuleList checked earlier.
    """
    prunedH = []
    for conseq in H:
        conf = supportData[freqSet]/supportData[freqSet-conseq]
        if conf >= minConf:
            print(freqSet-conseq,'-->',conseq,'conf',conf)
            brl.append((freqSet-conseq, conseq, conf))
            prunedH.append(conseq)
    return prunedH

def rulesFromConseq(freqSet, H, supportData, brl, minConf=0.7):
    """
    Purpose: Generate a candidate rule set
    Process: To generate more association rules from the initial itemset, the rulesFromConseq() function can be used. This function has two parameters: one is the frequent itemset, and the other is the list of elements that can appear on the right side of the rule H. The function first calculates the size m of the frequent set in H. Next, it checks whether the frequent itemset is large enough to remove subsets of size m. If it can be removed, it will be. The aprioriGen() function can be used to generate non-repeating combinations of elements in H. The result will be stored in Hmp1, which is also the H list for the next iteration. Hmp1 contains all possible rules. The calcConf() function can be used to test their confidence to determine whether the rules meet the requirements. If more than one rule meets the requirements, the function rulesFromConseq() will be called iteratively with Hmp1 to determine whether these rules can be further combined.
    """
    m = len(H[0])
    if (len(freqSet) > (m+1)):
        Hmp1 = aprioriGen(H, m+1)
        Hmp1 = calcConf(freqSet, Hmp1, supportData, brl, minConf)
        if (len(Hmp1) > 1):
            rulesFromConseq(freqSet, Hmp1, supportData, brl, minConf)