データ分析の知識: 相関分析アルゴリズム Apriori

以前、ショッピングバスケット分析についての記事を書きました。その中で、C5.0 と Apriori アルゴリズムについて触れましたが、これらのアルゴリズムの意味については詳しく説明しませんでした。昨日は、アソシエーション分析の理論的な部分について書きました。今日は、アソシエーション分析アルゴリズムの 1 つである Apriori アルゴリズムについてお話します。データ アナリストは使い方さえ知っていればよく、長くて退屈な理論を気にする必要はないとよく言われます。実際、私はまだ必要だと思います。アルゴリズムを設計する必要はありませんが、アルゴリズムを習得して慣れていれば、そのアルゴリズムを制御して使用するのに非常に役立ちます。また、各アルゴリズムには、空間と時間の複雑さ、使用上の制約など、使用上の制限があります。最も典型的なケースは、元のデータのコピーがあり、データ処理後にアルゴリズムシミュレーション分析を実行することです。しかし、このとき、どのようなデータを処理する必要があるのか​​、どのように処理するのかという疑問が生じます。これには、操作できるデータ形式やタイプなど、使用しているアルゴリズムに精通している必要があります。たとえば、GRI アルゴリズムでは、使用するデータをファクト テーブルの形式で保存する必要があります。このようなアルゴリズムの機能は、アルゴリズムの理解と把握のレベルに基づいている必要があります。

アプリオリアルゴリズム

この名前は、アルゴリズムが事前の知識に基づいていることに由来しています。前回見つかった頻出アイテムを使用して、今回頻出アイテムを生成します。 Apriori は、関連分析における中核となるアルゴリズムです。

Aprioriアルゴリズムの特徴

数値変数ではなく、カテゴリ変数のみを処理できます。

データの保存は、トランザクション データ形式 (トランザクション テーブル) またはファクト テーブル形式 (表形式データ) で行うことができます。

アルゴリズムの中核は、関連ルールの生成効率を向上させるように設計されています。

アプリオリの考え方

前に述べたように、有効なルールと見なされるためには、信頼度とサポートがしきい値の範囲を満たす必要があります。実際のプロセスでは、大量のデータに直面することがよくあります。単純な検索だけであれば、多くのルールが表示され、そのかなりの部分が無効なルールであり、効率が非常に低くなります。Apriori は、頻繁なアイテム セットを生成し、頻繁なアイテム セットに基づいてルールを生成して効率を向上させます。

上記は、頻繁なアイテム セットの生成と頻繁なアイテム セットに基づくルールの生成という、Apriori アルゴリズムの 2 つのステップを表しています。

では、頻繁なアイテムセットとは何でしょうか?

頻繁なアイテムセットとは、アイテム A を含むアイテムセット C であり、そのサポートは指定されたサポート以上です。この場合、C(A) は頻繁なアイテムセットであり、1 つのアイテムを含む頻繁なアイテムセットは頻繁な 1 アイテムセット (つまり L1) と呼ばれます。

頻繁なアイテムセットを決定する理由は何ですか?

先ほど述べたように、サポートは指定したサポートよりも大きくなければなりません。つまり、サポートのレベル自体が関連分析の結果が普遍的であるかどうかを表すため、後で生成されるルールが一般的に代表的な項目のセットから生成されることを確信できます。

頻繁なアイテムセットを見つけるにはどうすればいいですか?

ここでは説明しません。例を挙げるだけで誰もが理解できるでしょう。相関ルールをマイニングするための高速アルゴリズムの例

Apriori による頻繁なアイテムセットの検索プロセスは反復的なプロセスであり、各プロセスは候補セット Ck (頻繁なアイテムセットになる可能性のあるアイテムの組み合わせ) の生成、候補セット Ck に基づくサポートの計算、および Lk の決定という 2 つのステップで構成されます。

Apriori の検索戦略は、少数のプロジェクトから始めて、徐々に複数のプロジェクトを含むプロジェクト セットを検索することです。

データは次のとおりです。

データベースに保存されているデータ形式を見ると、メンバー 100 が 1、3、4 の 3 つの製品を購入したことがわかります。そのため、対応するコレクション フォームは右の図に示されています。次に、候補セット C1 に基づいて、下の図に示すように、頻出アイテム セット L1 を取得します。この表では、{4} のサポートは 1 で、設定したサポートは 2 です。サポートが指定された最小サポートしきい値以上の場合は、L1 になります。ここで、{4} は L1 のメンバーにはなりません。したがって、4 を含むその他のアイテム セットは頻出アイテム セットではないと判断し、それ以上の判断は行いません。

この時点で、L1 が最大サポートの基準を満たしていることがわかります。そのため、次の反復では、L1 に基づいて C2 を生成します (4 は考慮されなくなります)。この時点で、右の図に示すように、候補セット C2 (L1*L1 の組み合わせに基づく) が確立されます。 C2 の各セットによって得られるサポートは、下の左の図に示すように、元のデータの組み合わせの数に対応します。

このとき、2回目の反復では、{1 2} {1 5}のサポートが1のみであり、しきい値より低いため破棄されます。以降の反復では、{1 2} {1 5}の組み合わせが出現しても、考慮されません。

L2 から候補セット C3 を取得します。では、この反復で {1 2 3} { 1 3 5} はどこに行ったのでしょうか? 前述のように、{1 2} {1 5} の組み合わせは考慮されません。これら 2 つのアイテム セットは頻出アイテム セット L3 になることができないためです。この時点では、L4 は候補セット L4 を構成できないため、停止します。

上記のプロセスを一文で説明すると、Lk 自身の接続を通じて候補セットを継続的に形成し、不要な部分を削除することです。

頻繁なアイテムセットに基づいて単純な関連ルールを生成する

Apriori の関連ルールは頻繁なアイテム セットに基づいて生成されるため、これらのルールのサポートが普遍性と説得力を持って指定されたレベルに達することが保証されます。