1. 概要
  2. アルゴリズム
  3. Apriori

14 Apriori

Aprioriアルゴリズムを使用して相関ルールを計算する方法を学習します。

関連項目

14.1 Aprioriとは

Aprioriを使用して項目数が多い頻度の低いイベントを含む相関を見つける方法を学習します。

相関の機械学習の問題は、次の下位問題に分解できます。

  • 指定した最小頻度で発生する一連のトランザクションですべての項目の組合せを見つける。これらの組合せは高頻度項目セットと呼ばれます。

  • 高頻度項目セット内で見込まれる項目の同時発生性を表すルールを計算する。

Aprioriは、高頻度項目セット内に別の項目が存在する場合に、ある項目が存在する確率を計算します。

項目数が多い問題領域で頻度の低いイベントを含む相関を見つけるために相関ルール機械学習を使用することはお薦めしません。Aprioriは、頻度が最小支持度のしきい値を超えるパターンを発見します。したがって、頻度の低いイベントを含む相関を見つけるためには、最小支持度をかなり低くしてアルゴリズムを実行する必要があります。しかし、このようにすると、特に項目数が多いときに、列挙される項目セットの数が極端に多くなります。このような場合、実行時間が著しく長くなります。データに多くの属性が含まれている場合の頻度の低いイベントの検出には、分類や異常検出の方が適しています。

Aprioriの作成プロセスはパラレル実行をサポートします。

関連項目

14.2 相関ルールと高頻度項目セット

Aprioriアルゴリズムは、高頻度項目セット内の項目間の確率的な関係を表すルールを計算します。たとえば、A、BおよびCを含む高頻度項目セットから、「トランザクションにAとBが含まれる場合、Cも含まれる可能性が高い」というルールが導出されます。

相関ルールは、項目または項目のグループがある確率で別の項目の存在を示すことを表します。ターゲットを予測するディシジョン・ツリー・ルールとは異なり、相関ルールは単に相関関係を表します。

14.2.1 前件と後件

Aprioriアルゴリズムでの前件と後件について明確に説明します。

相関ルールのIFコンポーネントは、前件と呼ばれます。THENコンポーネントは、後件と呼ばれます。前件と後件は結合しておらず、共通の項目を持ちません。

Oracle Machine Learning for SQLでは、前件に1つ以上の項目を、後件に1つの項目を持つ相関ルールがサポートされています。

14.2.2 信頼度

ルールは、関連する信頼度(前件が発生した場合に後件が発生する条件付き確率)を持ちます。ルールの最小信頼度を指定できます。

14.3 Apriori用のデータ準備

相関モデルは、トランザクショナル・データを使用するように設計されています。トランザクショナル・データでは、ケースIDと各ケースの値の間に1対多関係が存在します。各ケースIDと値のペアは、個別のレコード(行)に指定されます。

14.3.1 ネイティブ・トランザクショナル・データとスター・スキーマ

トランザクショナル・データの格納形式について学習します。

トランザクショナル・データは、一意ではないケースID列および値列を使用するネイティブ・トランザクショナル形式で格納するか、スター・スキーマなどの他の構成で格納することができます。データは、ネイティブ・トランザクショナル形式で格納されていない場合、Aprioriアルゴリズムによって処理するためにネストした列に変換する必要があります。

関連項目

14.3.2 項目と集合

トランザクショナル・データで、項目の集合は、各ケースに関連付けられます。集合には、理論上、集合のメンバーとして可能なすべてのものが含まれます。たとえば、1つのマーケット・バスケット・トランザクションにおいて、理論上は、すべての製品を購入できます。ただし、実際は、考えられるすべての項目のごく一部のみが1つのトランザクションに存在し、マーケット・バスケットのアイテムはその店舗で入手できるごく一部の項目のみを表します。

14.3.3 スパース・データ

Aprioriアルゴリズムでのスパース・データの使用方法を理解します。

集合内で複数の項目が欠損している場合はデータがスパースであることがわかります。項目の欠損は、NULL値が存在する場合と、単に欠損している場合があります。

トランザクショナル・データ内のNULLは、既知であるがトランザクションには存在しない値を表すものとみなされます。たとえば、数百個ある商品のうち3つの商品が、1回のトランザクションで購入されたとします。購入されなかった商品は既知の商品ですが、トランザクションには含まれていません。

Oracle Machine Learning for SQLでは、トランザクショナル・データがスパースであることが想定されています。Aprioriアルゴリズムは、スパース・データの処理に対して最適化されています。

ノート:

Aprioriは自動データ準備の影響を受けません。

関連項目

14.3.4 サンプリングの向上

相関ルール(AR)では、RiondatoとUpfalの研究に基づいて、パフォーマンスが保証された適切なサンプル・サイズを使用できます。

ARアルゴリズムは、次の入力値からサンプル・サイズを計算します。

  • データセットのdインデックス

  • 絶対誤差ε

  • 信頼度γ

dインデックスは、最小でも長さがdで少なくともd個のトランザクションがデータセッに含まれるように最大整数dとして定義されます。これは、Vapnik-Chervonenkis(VC)次元の上限です。ARアルゴリズムは、データセット内のすべてのトランザクションの長さをスキャンしてデータセットのdインデックスを計算します。

ユーザーは、絶対誤差のεパラメータと信頼度のγパラメータを指定します。大きなdインデックス、小さなAR支持度、小さなεまたは大きなγは、サンプル・サイズが大きくなる要因となる可能性があります。サンプル・サイズは、近似AR(サンプリングから取得)の支持度と信頼度の両方の絶対誤差が、確率(または信頼度)が少なくともγである正確なARと比較してε未満であることを理論的に保証します。このドキュメントでは、このサンプル・サイズはAR固有のサンプル・サイズと呼ばれます。

14.3.4.1 サンプリングの実装

サンプル・サイズは、ユーザーがサンプリングをオン(ODMS_SAMPLINGをODMS_SAMPLING_ENABLEに設定)にし、サンプル・サイズを指定しない(ODMS_SAMPLE_SIZEが未指定)場合にのみ計算されます。

使用上のノート

  1. ODMS_SAMPLINGが未指定であるか、ODMS_SAMPLING_DISABLEが設定されている場合、ARのサンプリングは実行されず、正確なARが取得されます。

  2. ODMS_SAMPLINGにODMS_SAMPLING_ENABLEが設定されていて、ODMS_SAMPLE_SIZEに正の整数に指定されている場合は、ユーザー指定のサンプル・サイズ(ODMS_SAMPLE_SIZE)が使用されます。サンプリングは、ARアルゴリズムを実行する前の、全般的なデータ準備段階で実行されます。AR固有のサンプル・サイズは計算されません。近似ARが取得されます。

  3. ODMS_SAMPLINGにODMS_SAMPLING_ENABLEが設定され、ODMS_SAMPLE_SIZEが指定されてない場合、AR固有のサンプル・サイズが計算され、ARアルゴリズムでサンプリングが実行されます。近似ARが取得されます。

    ノート:

    算出されたAR固有のサンプル・サイズがデータセット内のトランザクションの合計サイズ以上となる場合、サンプリングは実行されず、正確なARが取得されます。

ARのサンプル・サイズの見当が付かない場合は、ODMS_SAMPLE_SIZEを未指定のままとし、サンプリング・パラメータに適切な値を指定するにとどめ、ARアルゴリズムに適切なAR固有のサンプル・サイズを計算させることをお薦めします。

関連項目:

使用可能なモデル設定のリストと解説は、『Oracle Database PL/SQLパッケージおよびタイプ・リファレンス』を参照してください。

ノート:

モデル設定と同じ意味でハイパーパラメータという用語も使用されます。

14.4 相関ルールの計算

相関分析の最初のステップは、項目セットを列挙します。項目セットとは、トランザクション内の2つ以上の項目のあらゆる組合せのことです。

14.4.1 項目セット

項目セットについて学習します。

1つの項目セットに含める項目の最大数はユーザーが指定します。最大数を2にした場合は、2項目から構成されるすべての組合せがカウントされます。最大数が2を超える場合は、2項目から構成されるすべての組合せ、3項目から構成されるすべての組合せ、以降指定した最大数の項目から構成されるすべての組合せがカウントされます。

次の表は、次の例に示したトランザクションから得られた項目セットの一覧です(ここでは、項目セットの項目の最大数を3に設定したものとします)。

表14-1 項目セット

トランザクション 項目セット

11

(B,D) (B,E) (D,E) (B,D,E)

12

(A,B) (A,C) (A,E) (B,C) (B,E) (C,E) (A,B,C) (A,B,E) (A,C,E) (B,C,E)

13

(B,C) (B,D) (B,E) (C,D) (C,E) (D,E) (B,C,D) (B,C,E) (B,D,E) (C,D,E)

例14-1 サンプル・トランザクショナル・データ

TRANS_ID   ITEM_ID
---------  -------------------
11         B
11         D
11         E
12         A
12         B
12         C
12         E
13         B
13         C
13         D
13         E

14.4.2 高頻度項目セット

高頻度項目セットおよび支持度について学習します。

相関ルールは項目セットに基づいて計算されます。可能性のあるすべての項目セットからルールが生成された場合、非常に多くのルールが存在することになり、意味のあるルールが得られないことがあります。また、モデルの作成に長い時間がかかる場合もあります。そのため、通常は、データ内での発生頻度が高い項目セットのみを使用してルールを生成する方が望ましいと言えます。高頻度項目セットとは、ユーザーが指定した最小頻度で発生する項目セットのことです。

最小頻度の項目セットの支持度は、相関ルール用に使用される項目セット数を制限するための割合であり、ユーザーが指定します。項目セットは、ルールの基盤として使用されるためには、全トランザクションにおいて少なくともこの割合で出現する必要があります。

次の表は、表14-1の項目セットのうち、支持度が66%を超える高頻度項目セットをまとめたものです。

表14-2 高頻度項目セット

高頻度項目セット トランザクション サポート

(B,C)

2/3

67%

(B,D)

2/3

67%

(B,E)

3/3

100%

(C,E)

2/3

67%

(D,E)

2/3

67%

(B,C,E)

2/3

67%

(B,D,E)

2/3

67%

関連項目

14.4.3 例: 高頻度項目セットからのルールの計算

高頻度項目セットからのルールの計算の例。

次の表に、「相関」で計算した項目セットおよび高頻度項目セットを示します。高頻度項目セットは、67%の最小支持度で発生する項目セットであり、3つのトランザクションのうち少なくとも2つにこの項目セットが含まれている必要があります。

表14-3 項目セット

トランザクション 項目セット

11

(B,D) (B,E) (D,E) (B,D,E)

12

(A,B) (A,C) (A,E) (B,C) (B,E) (C,E) (A,B,C) (A,B,E) (A,C,E) (B,C,E)

13

(B,C) (B,D) (B,E) (C,D) (C,E) (D,E) (B,C,D) (B,C,E) (B,D,E) (C,D,E)

表14-4 最小支持度67%の高頻度項目セット

項目セット トランザクション サポート

(B,C)

12および13

67%

(B,D)

11および13

67%

(B,E)

11、12および13

100%

(C,E)

12および13

67%

(D,E)

11および13

67%

(B,C,E)

12および13

67%

(B,D,E)

11および13

67%

ルールは条件付き確率を表しています。ルールの信頼度は、項目が同時に発生する確率を前件の発生確率で除算して計算されます。

たとえば、B (前件)が存在する場合、C (後件)も存在する可能性はどのくらいでしょうか。「Bの場合、C」というルールの信頼度はどのくらいでしょうか。

表14-3から、次のことがわかります。

  • 3つのトランザクションにはすべてBが含まれている(3/3または100%)。

  • 2つのトランザクションのみにBとCの両方が含まれている(2/3または67%)。

  • したがって、ルール「Bの場合、C」の信頼度は、67/100または67%である。

次の表に、表14-4の高頻度項目セットから導出できるルールを示します。

表14-5 高頻度項目セットとルール

高頻度項目セット ルール 確率(前件と後件) /確率(前件) 信頼度

(B,C)
  • (Bの場合C)
  • (Cの場合B)
  • 67/100
  • 67/67
  • 67%
  • 100%

(B,D)
  • (Bの場合D)
  • (Dの場合B)
  • 67/100
  • 67/67
  • 67%
  • 100%

(B,E)
  • (Bの場合E)
  • (Eの場合B)
  • 100/100
  • 100/100
  • 100%
  • 100%

(C,E)
  • (Cの場合E)
  • (Eの場合C)
  • 67/67
  • 67/100
  • 100%
  • 67%

(D,E)
  • (Dの場合E)
  • (Eの場合D)
  • 67/67
  • 67/100
  • 100%
  • 67%

(B,C,E)
  • (BおよびCの場合E)
  • (BおよびEの場合C)
  • (CおよびEの場合B)
  • 67/67
  • 67/100
  • 67/67
  • 100%
  • 67%
  • 100%

(B,D,E)
  • (BおよびDの場合E)
  • (BおよびEの場合D)
  • (DおよびEの場合B)
  • 67/67
  • 67/100
  • 67/67
  • 100%
  • 67%
  • 100%

最小信頼度が70%の場合、これらの高頻度項目セットについて10のルールが生成されます。最小信頼度が60%の場合、16のルールが生成されます。

ヒント:

モデルの作成時間を短縮し、生成されるルールの数を減らすには、最小信頼度の値を大きくします。

関連項目

14.4.4 集計

集計とは、ユーザーが相関ルール・モデルの集計のために選択した各項目に関連付けられた数量のことです。

複数の集計が存在する可能性があります。たとえば、ユーザーは利益および数量の両方を集計するモデルを指定できます。

14.4.5 例: 集計の計算

この例では、顧客の食料品の購入および利益データを使用して集計する方法を示します。

食料品店データの集計の計算

食料品店に次のデータがあるとします。

表14-6 食料品店データ

顧客 品目A 品目B 品目C 品目D
顧客1 購入(利益$5.00) 購入(利益$3.20) 購入(利益$12.00) 該当なし
顧客2 購入(利益$4.00) 該当なし 購入(利益$4.20) 該当なし
顧客3 購入(利益$3.00) 購入(利益$10.00) 購入(利益$14.00) 購入(利益$8.00)
顧客4 購入(利益$2.00) 該当なし 該当なし 購入(利益$1.00)

各顧客のバスケットはトランザクションとして参照できます。店舗のマネージャは、特定の相関ルールの存在だけでなく、そのようなルールが存在した場合に集計される利益に関心があります。

この例では、関連ルールの1つは、顧客1と顧客3に対して(A, B)=>Cとなります。このルールとともに、店のマネージャは次の情報に関心がある可能性があります。

  • このルールに現れる品目Aの利益合計

  • このルールに現れる品目Bの利益合計

  • このルールに現れる後件Cの利益合計

  • ルールに現れるすべての品目の利益合計

このルールに対しては、品目Aの利益は$5.00 + $3.00 = $8.00で、品目Bの利益は $3.20 + $10.00 = $13.20で、後件Cの利益は$12.00 + $14.00 = $26.00で、前件項目セット(A, B)については、$8.00 + $13.20 = $21.20です。ルール全体として、利益は$21.20 + $26.00 = $47.40です。

関連項目

14.4.6 包含ルールと除外ルール

相関で使用される包含ルールおよび除外ルールを説明します。

包含ルールでは、ユーザーはリストの少なくとも1つの項目が必ず戻されるルールに表示されるように項目のリストを提供できます。除外ルールでは、ユーザーはリストの項目が戻されるルールに1つも表示されないように項目のリストを提供できます。

注意:

各相関ルールには前件と後件の両方が含まれるため、1つの包含ルールのセットまたは除外ルールのセットを前件に指定して、別の包含ルールのセットまたは除外ルールのセットを後件に指定することができます。包含ルールと除外ルールは相関ルールに対しても定義できます。

関連項目

14.4.7 集計のパフォーマンスへの影響

集計関数は、さらに多くのメモリー使用とさらに長い実行時間を必要とします。

項目ごとに、ユーザーが集計対象の複数の列を指定できます。追加データをバッファするには、必要なメモリー量が増加し、集計値を計算するには、時間がさらにかかります。

14.5 相関ルールの評価

支持度と信頼度を使用することで相関ルールを評価します。

最小支持度と最小信頼度の使用によって、相関モデルの作成が左右されます。支持度と信頼度は、相関モデルで生成されるルールの質を評価するための主要なメトリックでもあります。また、Oracle Machine Learning for SQLでは相関ルールのリフトがサポートされています。これらの統計上の測度は、ルールのランク付けに使用できるので予測に役立ちます。

14.5.1 支持度

ルールの支持度は、そのルールにある項目が同時に発生する頻度を示します。たとえば、トランザクションの40%で、シリアルと牛乳が同時に発生するとします。この場合、次に示すルールの支持度はそれぞれ40%となります。 

cereal implies milk
milk implies cereal

支持度は、全トランザクションの合計数に対する、前件と後件のすべての項目が含まれるトランザクションの割合です。

次のように確率記法で支持度を表すことができます。

support(A implies B) = P(A, B)

14.5.2 最小支持度数

最小サポート数によって、各ルールで満たされる必要がある、トランザクションでの最小しきい値が定義されます。

トランザクションの数が不明な場合、サポート割合のしきい値パラメータを適切に設定するのが難しい場合があります。このため、サポートはトランザクション数で表すこともできます。ここで、使用されている2つのしきい値のうち大きい方を使用して、希少な項目セットを除外します。デフォルトは1で、この基準が適用されないことを示します。

関連項目

14.5.3 信頼度

ルールの信頼度は、同一のトランザクションで前件と後件の両方が発生する確率を示します。

前件が存在する場合に後件が存在する条件付き確率です。たとえば、50のトランザクションにシリアルが含まれており、50のうち40のトランザクションには牛乳も含まれているとします。この場合、ルールの信頼度は次のようになります。 

cereal implies milk with 80% confidence

信頼度は、前件を含むトランザクションの数に対する、ルールの支持度の割合です。

次のように確率記法で信頼度を表すことができます。

confidence (A implies B) = P (B/A), which is equal to P(A, B) / P(A)

関連項目

14.5.4 逆確信度

ルールの逆確信度は、ルールが発生するトランザクションの数を後件が発生するトランザクションの数で割ったものとして定義されています。

逆確信度では、結果が高頻度であるために発生するルールがなくなります。デフォルトは0です。

関連項目

14.5.5 リフト

ルールが有効であるかどうかを決定するには、支持度と信頼度の両方を使用する必要があります。ただし、これらの測度が高くても、有益でないルールが生成される場合もあります。次に例を示します。 

Convenience store customers who buy orange juice also buy milk with 
a 75% confidence. 
The combination of milk and orange juice has a support of 30%.

このルールは一見、優れているように思われ、多くの場合、問題はありません。信頼度も支持度も高いルールとなっています。ただし、コンビニエンス・ストアの顧客が一般に90%の確率で牛乳を購入する場合を考えます。その場合、オレンジ・ジュースを購入する顧客は実際、一般の顧客より牛乳を購入する可能性が低くなります。

こうしたルールの質を評価するには、3つ目の測度が必要です。リフトは、それぞれの支持度を持つ前件と後件のランダムな同時発生に対するルールの強度を示します。リフトにより、改良度(前件を前提とする後件の確率の増加)に関する情報が得られます。リフトは次のように定義されます。

(Rule Support) /(Support(Antecedent) * Support(Consequent))

これは、後件の支持度で除算した項目の組合せの信頼度として定義することもできます。この牛乳の例で、顧客の40%がオレンジ・ジュースを購入すると仮定すると、改良度は次のようになります。

30% / (40% * 90%)

この値は0.83で、これは1未満の改良度です。

改良度が1未満のルールでは、偶然以上に購入を確実に予測できないため、支持度と信頼度が高くても、実際の組合せ購入の確率は示されません。

ヒント:

モデルの作成時間を短縮し、単純なルールを生成するには、ルールの最大長の値を小さくします。

ヒント:

モデルの作成時間を短縮し、生成されるルールの数を減らすには、最小支持度の値を大きくします。