15 Apriori

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

• Aprioriとは
  Aprioriを使用して項目数が多い頻度の低いイベントを含む相関を見つける方法を学習します。
• 相関ルールと高頻度項目セット
  Aprioriでは、高頻度項目セット内の項目間の確率的な関係を表すルールが計算されて、項目の同時発生の確率が示されます。
• Apriori用のデータ準備
  モデル処理のために、Apriori用のトランザクショナル・データを、ケースIDおよびそれに関連する値に編成することで準備します。
• 相関ルールの計算
  トランザクションからの項目セットを列挙し、相関ルールを計算します。
• 相関ルールの評価
  支持度と信頼度を使用することで相関ルールを評価します。

15.1 Aprioriとは

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

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

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

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

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

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

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

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

Aprioriでは、高頻度項目セット内の項目間の確率的な関係を表すルールが計算されて、項目の同時発生の確率が示されます。

たとえば、A、BおよびCを含む高頻度項目セットから、「トランザクションにAとBが含まれる場合、Cも含まれる可能性が高い」というルールが導出されます。

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

• 前件と後件
  Aprioriアルゴリズムでの前件と後件について明確に説明します。
• 信頼度
  前件が存在する場合に後件が存在する条件付き確率を表す、ルールの最小信頼度を指定します。

15.2.1 前件と後件

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

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

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

15.2.2 信頼度

前件が存在する場合に後件が存在する条件付き確率を表す、ルールの最小信頼度を指定します。

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

15.3 Apriori用のデータ準備

モデル処理のために、Apriori用のトランザクショナル・データを、ケースIDおよびそれに関連する値に編成することで準備します。

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

• ネイティブ・トランザクショナル・データとスター・スキーマ
  Apriori処理用の非ネイティブ・フォーマットを変換して、トランザクショナル・データをネイティブまたはスター・スキーマ形式で格納します。
• 項目と集合
  トランザクショナル・データでは考えられる項目の一部が各ケースに関連付けられるということを説明します。ここでは、店舗での購入パターンについて示します。
• スパース・データ
  トランザクショナル・データは通常はスパースであり、項目の欠損によって示されるのは、NULL値ではなく含まれていないということです。
• サンプリングの向上
  改善されたサンプリング手法を使用して、パフォーマンスが保証されている、相関ルール生成のための適切なサンプル・サイズを判断します。

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

Apriori処理用の非ネイティブ・フォーマットを変換して、トランザクショナル・データをネイティブまたはスター・スキーマ形式で格納します。

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

15.3.2 項目と集合

トランザクショナル・データでは考えられる項目の一部が各ケースに関連付けられるということを説明します。ここでは、店舗での購入パターンについて示します。

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

15.3.3 スパース・データ

トランザクショナル・データは通常はスパースであり、項目の欠損によって示されるのは、NULL値ではなく含まれていないということです。

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

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

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

ノート:

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

15.3.4 サンプリングの向上

改善されたサンプリング手法を使用して、パフォーマンスが保証されている、相関ルール生成のための適切なサンプル・サイズを判断します。

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

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

• 絶対誤差ε

• 信頼度γ

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

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

• サンプリングの実装
  サンプリング設定を指定してサンプル・サイズを決めるか、効率的なルール生成のために、アルゴリズムで計算されたサンプル・サイズを使用します。

15.3.4.1 サンプリングの実装

サンプリング設定を指定してサンプル・サイズを決めるか、効率的なルール生成のために、アルゴリズムで計算されたサンプル・サイズを使用します。

使用上のノート

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固有のサンプル・サイズを計算させることをお薦めします。

関連項目:

使用可能なモデル設定のリストおよび説明は、DBMS_DATA_MINING — 機械学習機能の設定を参照してください。

ノート:

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

15.4 相関ルールの計算

トランザクションからの項目セットを列挙し、相関ルールを計算します。

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

• 項目セット
  トランザクション内の項目の組合せとして項目セットを定義します。それにより、項目セットごとの最大項目数を指定します。
• 高頻度項目セット
  ルールを作成するために、ユーザー指定の最小限度に基づいてフィルタされた、頻繁に購入される品目(項目セット)を識別します。
• 例: 高頻度項目セットからのルールの計算
  高頻度項目セットから相関ルールを計算します。例を使用してルール生成と信頼度計算を示します。
• 集計
  集計とは、ユーザーが相関ルール・モデルの集計のために選択した各項目に関連付けられた数量のことです。
• 例: 集計の計算
  この例では、顧客の食料品購入および利益データを使用して集計する方法を示します。
• 包含ルールと除外ルール
  相関で使用される包含ルールと除外ルールについて説明します。
• 集計のパフォーマンスへの影響
  相関ルールのデータを集計するには、パフォーマンスを円滑にするためにメモリーと処理能力を増やす必要があります。

15.4.1 項目セット

トランザクション内の項目の組合せとして項目セットを定義します。それにより、項目セットごとの最大項目数を指定します。

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

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

表15-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)

例15-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

15.4.2 高頻度項目セット

ルールを作成するために、ユーザー指定の最小限度に基づいてフィルタされた、頻繁に購入される品目(項目セット)を識別します。

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

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

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

表15-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%

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

高頻度項目セットから相関ルールを計算します。例を使用してルール生成と信頼度計算を示します。

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

表15-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)

表15-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」というルールの信頼度はどのくらいでしょうか。

表15-3から、次のことがわかります:

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

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

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

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

表15-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のルールが生成されます。

ヒント:

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

15.4.4 集計

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

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

15.4.5 例: 集計の計算

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

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

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

表15-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です。

15.4.6 包含ルールと除外ルール

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

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

ノート:

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

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

相関ルールのデータを集計するには、パフォーマンスを円滑にするためにメモリーと処理能力を増やす必要があります。

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

15.5 相関ルールの評価

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

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

• 支持度
  トランザクション内の重要な項目セットの特定に役立つように、項目の同時発生の頻度を示す支持度を測定します。
• 最小サポート数
  トランザクション内での項目セットの出現頻度が重要とみなすのに十分な数となるように、最小サポート数を定義します。
• 信頼度
  ルールの信頼度は、同一のトランザクションで前件と後件の両方が発生する確率を示しています。
• 逆確信度
  ルールの逆確信度は、ルールが発生するトランザクションの数を後件が発生するトランザクションの数で割ったものとして定義されています。
• リフト
  リフトを測定してランダムな同時発生に対するルールの強度を評価します。それにより、ルールの予測値が確かになるようにします。

15.5.1 支持度

トランザクション内の重要な項目セットの特定に役立つように、項目の同時発生の頻度を示す支持度を測定します。

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

cereal implies milk
milk implies cereal

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

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

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

15.5.2 最小サポート数

トランザクション内での項目セットの出現頻度が重要とみなすのに十分な数となるように、最小サポート数を定義します。

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

15.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)

15.5.4 逆確信度

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

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

15.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未満のルールでは、偶然以上に購入を確実に予測できないため、支持度と信頼度が高くても、実際の組合せ購入の確率は示されません。

ヒント:

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

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