1

小さなデータ相関ルールマインにおもちゃのAprioriアルゴリズムを実装するには、すべてのサブセットを返す関数が必要です。

サブセットの長さはパラメータで指定されますi。この関数を一般化する必要がありますi。1または2の場合は簡単で、一般的なパターンを見ることができます。重複を防ぐために順序が課されているi長さのタプルのリストです。i

def all_subsets(di,i):
        if i == 1:
                return di
        elif i == 2:
                return [(d1,d2) for d1 in di for d2 in di if d1 < d2]
        else:
                return [ ... ]

iリスト内包表記、ジェネレーター、またはいくつかの「関数型プログラミング」の概念を使用して、このネストされたループパターンを簡潔に一般化するにはどうすればよいですか？

iある種の関数のリストを考えていましたが、ネストされたループを一般化する方法がよくわかりません。ヒントや完全な回答は素晴らしいものとして扱われます。

4

4 に答える 4

4

独自にロールアウトする代わりに、を使用できますitertools.combinations()。

于 2013-03-02T13:09:11.517 に答える
1

その後、あなたはアプリオリをしていません。

Aprioriでは、k = 1を除いて、サイズkのすべてのサブセットを列挙することはありません。

それより大きいサイズでは、に従って組み合わせを作成Apriori-Genします。

これははるかに効率的で、実際には少なくともすべての組み合わせを手動で作成するのと同じくらい簡単です。

これが例です。次のアイテムセットが頻繁に見つかったと仮定します。

 ABCD
 ABCF
 ABEF
 ABDF
 ACDF
 BCDF

次に、aprioriは単一の候補のみを作成します（プレフィックスルールによる！）：

 ABC + D   - ABC + D + F
 ABC + F   /

次に、他のサブセットも頻繁に検出されたかどうかを確認します。

 BCDF
 ACDF
 ABDF

それらはすべて前のラウンドにあったので、この候補は生き残り、データセットに対する次の線形スキャンでテストされます。

Aprioriは、サイズkのすべてのサブセットをチェックする必要はなく、以前の知識を前提として、頻繁にチェックする可能性があるサブセットのみをチェックすることを目的としています。

于 2013-03-02T14:59:50.223 に答える
1

コメントで、ここのコードは不透明であると述べています。しかし、それはおそらくcombinationsあなたが目指している種類の関数を実装するための最良の方法であり、理解する価値があるので、それを詳細に説明しようと思います。

基本的な考え方は、シーケンスと選択するアイテムの数が与えられた場合、各組み合わせを、与えられたシーケンスへのインデックスのシーケンスとして表すことができるということです。たとえば、リスト['a', 'b', 'c', 'd', 'e']があり、そのリストから2つの値のすべての組み合わせを生成するとします。

私たちの最初の組み合わせは次のようになります...

['a', 'b', 'c', 'd', 'e']
  ^    ^

...そしてインデックスのリストで表されます[0, 1]。次の組み合わせは次のようになります。

['a', 'b', 'c', 'd', 'e']
  ^         ^

そして、インデックスのリストで表されます[0, 2]。

2番目のキャレットが最後に到達するまで、最初のキャレットを所定の位置に保ちながら、2番目のキャレットを前方に動かし続けます。次に、最初のキャレットをインデックス1に移動し、2番目のキャレットをインデックスに戻すことでプロセスを「リセット」します2。

['a', 'b', 'c', 'd', 'e']
       ^    ^

次に、このプロセスを繰り返し、2番目のキャレットを最後まで前方に移動してから、最初のキャレットを1つ前方に移動し、2番目をリセットします。

次に、インデックスのリストを操作して、これを行う方法を理解する必要があります。これは非常に簡単であることがわかります。最終的な組み合わせは次のようになります。

['a', 'b', 'c', 'd', 'e']
                 ^    ^

そして、これのインデックス表現はになります[3, 4]。これらはインデックスの可能な最大値であり、に等しくなりますi + n - r。ここiで、はリスト内の位置、nは値の数（5この場合）、rは選択肢の数（2この場合）です。したがって、特定のインデックスがこの値に達するとすぐに、それ以上になることはなく、「リセット」する必要があります。

それを念頭に置いて、コードの段階的な分析を次に示します。

def combinations(iterable, r):
    pool = tuple(iterable)
    n = len(pool)

まず、上記の例に基づいて入力すると、上記poolの文字のリストがタプルに変換されn、プール内のアイテムの数になります。

if r > n:
    return

nアイテムリストからアイテムを置き換えることなく選択することはできないnので、その場合は単に戻ります。

indices = range(r)

これで、最初の組み合わせ（）に初期化されたインデックスができました[0, 1]。だから私たちはそれを生み出します：

yield tuple(pool[i] for i in indices)

次に、無限ループを使用して残りの組み合わせを生成します。

while True:

ループ内では、最初にインデックスのリストをさかのぼって、まだ最大値に達していないインデックスを検索します。上記の式（i + n - r）を使用して、特定のインデックスの最大値を決定します。最大値に達していないインデックスが見つかった場合は、ループから抜け出します。

    for i in reversed(range(r)):
        if indices[i] != i + n - r:
            break

見つからない場合は、すべてのインデックスが最大値になっていることを意味するため、反復処理が完了します。（これはあまり知られていないfor-else構造を使用します。elseブロックは、forループが正常に終了した場合にのみ実行されます。）

    else:
        return

これで、インデックスiをインクリメントする必要があることがわかりました。

    indices[i] += 1

さらに、後のインデックスiはすべて最大値になっているため、リセットする必要があります。

    for j in range(i+1, r):
        indices[j] = indices[j-1] + 1

これで次のインデックスのセットがあるので、別の組み合わせを生成します。

    yield tuple(pool[i] for i in indices)

このアプローチにはいくつかのバリエーションがあります。別の方法では、インデックスを逆方向に進む代わりに、前に進み、そのインデックスと次のインデックスの間に「ギャップ」がある最初のインデックスをインクリメントし、下位のインデックスをリセットします。

最後に、これを再帰的に定義することもできますが、実用的には、再帰的な定義はおそらくそれほど効率的ではありません。

于 2013-03-02T15:00:10.497 に答える
0

Okay here is my rolled own version :

def all_subsets(source,size):
        index = len(source)
        index_sets = [()]
        for sz in xrange(size):
                next_list = []
                for s in index_sets:
                        si = s[len(s)-1] if len(s) > 0 else -1
                        next_list += [s+(i,) for i in xrange(si+1,index)]
                index_sets = next_list
        subsets = []
        for index_set in index_sets:
                rev = [source[i] for i in index_set]
                subsets.append(rev)
        return subsets

Yields:

>>> Apriori.all_subsets(['c','r','i','s'],2)
[['c', 'r'], ['c', 'i'], ['c', 's'], ['r', 'i'], ['r', 's'], ['i', 's']]
于 2013-03-02T14:44:06.083 に答える