Bdtjtk

I am reading about association analysis in book titled Machine learning in action. Following code is given in book

The k-2 thing may be a little confusing. Let’s look at that a little
further. When you were creating {0,1} {0,2}, {1,2} from {0}, {1}, {2},
you just combined items. Now, what if you want to use {0,1} {0,2},
{1,2} to create a three-item set? If you did the union of every set,
you’d get {0, 1, 2}, {0, 1, 2}, {0, 1, 2}. That’s right. It’s the same
set three times. Now you have to scan through the list of three-item
sets to get only unique values. You’re trying to keep the number of
times you go through the lists to a minimum. Now, if you compared the
first element {0,1} {0,2}, {1,2} and only took the union of those that
had the same first item, what would you have? {0, 1, 2} just one time.
Now you don’t have to go through the list looking for unique values.

def aprioriGen(Lk, k): #creates Ck

    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] # Join sets if first k-2 items are equal

            L1.sort(); L2.sort()

            if L1==L2:

                retList.append(Lk[i] | Lk[j])

    return retLis

Suppose i am calling above function

Lk = [frozenset({2, 3}), frozenset({3, 5}), frozenset({2, 5}), frozenset({1, 3})]



k = 3



aprioriGen(Lk,3)

I am geting following output

[frozenset({2, 3, 5})]

I think there is bug in above logic since we are missing other combinations like {1,2,3}, {1,3,5}. Isn't it? Is my understanding right?

I think you are following the below link, Output set depends on the minSupport what we pass.

http://adataanalyst.com/machine-learning/apriori-algorithm-python-3-0/

If we reduce the minSupport value to 0.2, we get all sets.

Below is the complete code

# -*- coding: utf-8 -*-

"""

Created on Mon Dec 31 16:57:26 2018



@author: rponnurx

"""



from numpy import *



def loadDataSet():

    return [[1, 3, 4], [2, 3, 5], [1, 2, 3, 5], [2, 5]]



def createC1(dataSet):

    C1 = 

    for transaction in dataSet:

        for item in transaction:

            if not [item] in C1:

                C1.append([item])



    C1.sort()

    return list(map(frozenset, C1))#use frozen set so we

                            #can use it as a key in a dict  



def scanD(D, Ck, minSupport):

    ssCnt = {}

    for tid in D:

        for can in Ck:

            if can.issubset(tid):

                if not can in ssCnt: 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



dataSet = loadDataSet()

print(dataSet)



C1 = createC1(dataSet)



print(C1)



#D is a dataset in the setform.



D = list(map(set,dataSet))

print(D)



L1,suppDat0 = scanD(D,C1,0.5)

print(L1)



def aprioriGen(Lk, k): #creates Ck

    retList = 

    print("Lk")

    print(Lk)

    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: #if first k-2 elements are equal

                retList.append(Lk[i] | Lk[j]) #set union

    return retList



def apriori(dataSet, minSupport = 0.5):

    C1 = createC1(dataSet)

    D = list(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)#scan DB to get Lk

        supportData.update(supK)

        L.append(Lk)

        k += 1

    return L, supportData



L,suppData = apriori(dataSet,0.2)



print(L)

Output:
[[frozenset({5}), frozenset({2}), frozenset({4}), frozenset({3}), frozenset({1})], [frozenset({1, 2}), frozenset({1, 5}), frozenset({2, 3}), frozenset({3, 5}), frozenset({2, 5}), frozenset({1, 3}), frozenset({1, 4}), frozenset({3, 4})], [frozenset({1, 3, 5}), frozenset({1, 2, 3}), frozenset({1, 2, 5}), frozenset({2, 3, 5}), frozenset({1, 3, 4})], [frozenset({1, 2, 3, 5})], ]

Thanks,
Rajeswari Ponnuru