1

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 プロセスについて知りました。しかし、これが前のコードでどのように実装されているかわかりません。temp を使用した理由 isExists と isContained はどのように役立つのでしょうか? コードのこれら 2 つの部分で正確に何が起こっているのでしょうか?

4

2 に答える 2

3

まず、2 つのループがあります。

for (int i = 0 ; i

これらのループは、指定されたサイズの項目セットの各ペアを一緒に比較するために使用されます。この Apriori の実装について最初に気付くのは、項目セットが字句順に並べられている場合、各項目セットを互いに比較する必要がないため、効率的ではないということです。早めに止めることができます。しかし、このコードにはこの最適化がありません。

このコードの 2 つ目の大きな問題は、候補が文字列として格納されていることです。整数の配列として格納する方がはるかに効率的です。項目セットを "," を含む文字列として保存し、それらを個別の数値に分割することは、メモリと実行時間を浪費する非常に悪い設計上の決定です。データ マイニング アルゴリズムの場合、実装は可能な限り効率的である必要があります。私の意見では、これはあなたが見ているコードが初心者によって書かれたことを意味します。

あなたの質問について、変数「temp」は新しい候補を格納するために使用されます。候補は 2 つの項目セットの連結であることを思い出してください。2 つのアイテムセットを結合するには、1 つを除くすべてのアイテムを共有していることを確認する必要があります。たとえば、ABC と ABD の 2 つのアイテムセットがある場合、これら 2 つのアイテムセットは ABCD となる新しい候補を生成します。ただし、2 つの項目セットに複数の異なる項目がある場合は、それらを結合しないでください。それが、あなたが私に示したコードが によってやろうとしていることです。

効率的な Apriori の実装を見たい場合は、私のWeb サイト(http://www.philippe-fournier-viger.com/spmf/) をチェックしてください。効率的な Java 実装をいくつか提供しています。効率的な C++ 実装が必要な場合は、http: //fimi.ua.ac.be/src/を参照してください。

于 2011-10-23T12:17:59.013 に答える