Объяснение алгоритма априори

Question

Я нашел реализацию алгоритма Apriori в Интернете, но есть кое-что, чего я не могу понять. Я надеюсь, что кто-нибудь может мне помочь.

# region----- Apriori-gen
//Generates Candidate Itemsets
static ArrayList AprioriGen (ArrayList L)
{
    ArrayList Lk = new ArrayList ();    //List to store generated Candidate Itemsets
    Regex r = new Regex (",");
    for (int i = 0 ; i <L.Count ; i++)
    {
        string [] subL1 = r.Split (L [i]. ToString ());
        for (int j = i+1 ; j <L.Count ; j++)
        {
            string [] subL2 = r.Split (L [j]. ToString ());
            // Compare two items in L, and set them in temp
            string temp = L [j]. ToString ();   //store two key sets
            for (int m = 0; m <subL1.Length; m++)
            {
                bool subL1mInsubL2 = false;
                for (int n = 0; n <subL2.Length; n++)
                {
                    if (subL1 [m] == subL2 [n]) subL1mInsubL2 = true;
                }
                if (subL1mInsubL2 == false) temp = temp + "," + subL1 [m];
            }

            // If temp contains the entry for L in the (itemset size +1)
            //and the focus is not with the candidates seeking the same items set temp
            string [] subTemp = r.Split (temp);
            if (subTemp.Length == subL1.Length + 1)
            {
                bool isExists = false;
                for (int m = 0; m <Lk.Count; m++)
                {
                    bool isContained = true;
                    for (int n = 0; n <subTemp.Length; n++)
                    {
                        if (!Lk[m].ToString().Contains(subTemp [n]) ) isContained = false;
                    }
                    if (isContained == true) isExists = true;
                }
                if (isExists == false) Lk.Add(temp);
            }
        }
    }
    return Lk;
}
# endregion----- Apriori-gen

Теперь я знаю процесс Apriori Gen, где мы превращаем наборы в более крупные наборы, объединяя их. Но я не вижу, как это реализовано в предыдущем коде. Почему мы использовали темп? Как isExists и isContained помогают нам? Что происходит именно в этих двух частях кода?

Answer 1

Во-первых, есть две петли:

для (int i = 0; i

Эти циклы используются для сравнения каждой пары наборов элементов заданного размера вместе. Первое, что я заметил в этой реализации Apriori, это то, что она неэффективна, потому что, если наборы элементов упорядочены по лексическому принципу, вам не нужно сравнивать каждый набор элементов друг с другом. Вы можете остановиться раньше. Но этот код не имеет этой оптимизации.

Вторая большая проблема, которую я вижу с этим кодом, заключается в том, что кандидаты хранятся в виде строк. Было бы намного эффективнее хранить его как массив целых чисел. Хранение набора элементов в виде String, включая "," и разделение их на отдельные числа - это очень плохое проектное решение, которое приведет к потере памяти и времени выполнения. Для алгоритма интеллектуального анализа данных реализация должна быть максимально эффективной. На мой взгляд, это означает, что код, который вы просматриваете, был написан новичком.

По поводу вашего вопроса, переменная "temp" используется для хранения нового кандидата. Напомним, что кандидатом является объединение двух наборов элементов. Чтобы объединить два набора элементов, вы должны убедиться, что они разделяют все элементы, кроме одного. Например, если у вас есть два набора элементов ABC и ABD, эти два набора элементов сгенерируют новых кандидатов, которые будут ABCD. Но если два набора элементов содержат более одного элемента, их не следует объединять. Вот что пытается сделать код, который вы мне показываете.

Если вы хотите взглянуть на какую-то эффективную реализацию Apriori, вы можете проверить мой сайт (http://www.philippe-fournier-viger.com/spmf/), я предоставлю несколько эффективных реализаций Java. Если вам нужны эффективные реализации на С ++, посмотрите: http://fimi.ua.ac.be/src/.

Answer 2

Описание: Простая реализация априорного алгоритма на Python

Применение:

$python apriori.py -f DATASET.csv -s minSupport  -c minConfidence

$python apriori.py -f DATASET.csv -s 0.15 -c 0.6

import sys

from itertools import chain, combinations
from collections import defaultdict
from optparse import OptionParser


def subsets(arr):
    """ Returns non empty subsets of arr"""
    return chain(*[combinations(arr, i + 1) for i, a in enumerate(arr)])


def returnItemsWithMinSupport(itemSet, transactionList, minSupport, freqSet):
        """calculates the support for items in the itemSet and returns a subset
       of the itemSet each of whose elements satisfies the minimum support"""
        _itemSet = set()
        localSet = defaultdict(int)

        for item in itemSet:
                for transaction in transactionList:
                        if item.issubset(transaction):
                                freqSet[item] += 1
                                localSet[item] += 1

        for item, count in localSet.items():
                support = float(count)/len(transactionList)

                if support >= minSupport:
                        _itemSet.add(item)

        return _itemSet


def joinSet(itemSet, length):
        """Join a set with itself and returns the n-element itemsets"""
        return set([i.union(j) for i in itemSet for j in itemSet if len(i.union(j)) == length])


def getItemSetTransactionList(data_iterator):
    transactionList = list()
    itemSet = set()
    for record in data_iterator:
        transaction = frozenset(record)
        transactionList.append(transaction)
        for item in transaction:
            itemSet.add(frozenset([item]))              # Generate 1-itemSets
    return itemSet, transactionList


def runApriori(data_iter, minSupport, minConfidence):
    """
    run the apriori algorithm. data_iter is a record iterator
    Return both:
     - items (tuple, support)
     - rules ((pretuple, posttuple), confidence)
    """
    itemSet, transactionList = getItemSetTransactionList(data_iter)

    freqSet = defaultdict(int)
    largeSet = dict()
    # Global dictionary which stores (key=n-itemSets,value=support)
    # which satisfy minSupport

    assocRules = dict()
    # Dictionary which stores Association Rules

    oneCSet = returnItemsWithMinSupport(itemSet,
                                        transactionList,
                                        minSupport,
                                        freqSet)

    currentLSet = oneCSet
    k = 2
    while(currentLSet != set([])):
        largeSet[k-1] = currentLSet
        currentLSet = joinSet(currentLSet, k)
        currentCSet = returnItemsWithMinSupport(currentLSet,
                                                transactionList,
                                                minSupport,
                                                freqSet)
        currentLSet = currentCSet
        k = k + 1

    def getSupport(item):
            """local function which Returns the support of an item"""
            return float(freqSet[item])/len(transactionList)

    toRetItems = []
    for key, value in largeSet.items():
        toRetItems.extend([(tuple(item), getSupport(item))
                           for item in value])

    toRetRules = []
    for key, value in largeSet.items()[1:]:
        for item in value:
            _subsets = map(frozenset, [x for x in subsets(item)])
            for element in _subsets:
                remain = item.difference(element)
                if len(remain) > 0:
                    confidence = getSupport(item)/getSupport(element)
                    if confidence >= minConfidence:
                        toRetRules.append(((tuple(element), tuple(remain)),
                                           confidence))
    return toRetItems, toRetRules


def printResults(items, rules):
    """prints the generated itemsets sorted by support and the confidence rules sorted by confidence"""
    for item, support in sorted(items, key=lambda (item, support): support):
        print "item: %s , %.3f" % (str(item), support)
    print "\n------------------------ RULES:"
    for rule, confidence in sorted(rules, key=lambda (rule, confidence): confidence):
        pre, post = rule
        print "Rule: %s ==> %s , %.3f" % (str(pre), str(post), confidence)


def dataFromFile(fname):
        """Function which reads from the file and yields a generator"""
        file_iter = open(fname, 'rU')
        for line in file_iter:
                line = line.strip().rstrip(',')                         # Remove trailing comma
                record = frozenset(line.split(','))
                yield record


if __name__ == "__main__":

    optparser = OptionParser()
    optparser.add_option('-f', '--inputFile',
                         dest='input',
                         help='filename containing csv',
                         default=None)
    optparser.add_option('-s', '--minSupport',
                         dest='minS',
                         help='minimum support value',
                         default=0.15,
                         type='float')
    optparser.add_option('-c', '--minConfidence',
                         dest='minC',
                         help='minimum confidence value',
                         default=0.6,
                         type='float')

    (options, args) = optparser.parse_args()

    inFile = None
    if options.input is None:
            inFile = sys.stdin
    elif options.input is not None:
            inFile = dataFromFile(options.input)
    else:
            print 'No dataset filename specified, system with exit\n'
            sys.exit('System will exit')

    minSupport = options.minS
    minConfidence = options.minC

    items, rules = runApriori(inFile, minSupport, minConfidence)

    printResults(items, rules)

Answer 3

def subsets(arr): """ Возвращает непустые подмножества arr""" return Chain(*[combinations(arr, i + 1) for i, a in enumerate(arr)])

def returnItemsWithMinSupport(itemSet, transactionList, minSupport, freqSet): """вычисляет поддержку элементов в itemSet и возвращает подмножество itemSet, каждый из элементов которого удовлетворяет минимальной поддержке""" _itemSet = set() localSet = defaultdict( инт)

      for item in itemSet:
    for transaction in transactionList:
        if item.issubset(transaction):
            freqSet[item] += 1
            localSet[item] += 1

for item, count in localSet.items():
    support = float(count) / len(transactionList)

    if support >= minSupport:
        _itemSet.add(item)

return _itemSet