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

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. Если вам нужны эффективные реализации c ++, посмотрите: http://fimi.ua.ac.be/src/.