Class Apriori

pattern/vector/__init__.py:1209–1259

# Based on: https://gist.github.com/1423287

class Apriori(object):
    
    def __init__(self):
        self._candidates = []
        self._support = {}
    
    def C1(self, sets):
        """ Returns the unique features from all sets as a list of (hashable) frozensets.
        """
        return [frozenset([v]) for v in set(chain(*sets))]

    def Ck(self, sets):
        """ For the given sets of length k, returns combined candidate sets of length k+1.
        """
        Ck = []
        for i, s1 in enumerate(sets):
            for j, s2 in enumerate(sets[i+1:]):
                if set(list(s1)[:-1]) == set(list(s2)[:-1]):
                    Ck.append(s1 | s2)
        return Ck
        
    def Lk(self, sets, candidates, support=0.0):
        """ Prunes candidate sets whose frequency < support threshold.
            Returns a dictionary of (candidate set, frequency)-items.
        """
        Lk, x = {}, 1.0 / (len(sets) or 1) # relative count
        for s1 in candidates:
            for s2 in sets:
                if s1.issubset(s2):
                    Lk[s1] = s1 in Lk and Lk[s1]+x or x
        return dict((s, f) for s, f in Lk.items() if f >= support)

    def __call__(self, sets, support=0.5):
        """ Returns a dictionary of (set(features), frequency)-items.
            The given support (0.0-1.0) is the relative amount of documents
            in which a combination of feature must appear.
        """
        C1 = self.C1(sets)
        L1 = self.Lk(sets, C1, support)
        self._candidates = [L1.keys()]
        self._support = L1
        while True:
            # Terminate when no further extensions are found.
            if len(self._candidates[-1]) == 0:
                break
            # Extend frequent subsets one item at a time.
            Ck = self.Ck(self._candidates[-1])
            Lk = self.Lk(sets, Ck, support)
            self._candidates.append(Lk.keys())
            self._support.update(Lk)
        return self._support
        
apriori = Apriori()