11 Apriori
関連項目
11.1 Aprioriとは
Aprioriについて学習します。
Aprioriは、高頻度項目セット内で別の項目が存在する場合に、ある項目が存在する確率を計算します。
項目数が多い問題領域で頻度の低いイベントを含む相関を見つけるために相関ルール・マイニングを使用することはお薦めしません。Aprioriは、頻度が最小支持度のしきい値を超えるパターンを発見します。したがって、頻度の低いイベントを含む相関を見つけるためには、最小支持度をかなり低くしてアルゴリズムを実行する必要があります。しかし、このようにすると、特に項目数が多いときに、列挙される項目セットの数が極端に多くなります。このような場合、実行時間が著しく長くなります。データに多くの属性が含まれるときに頻度の低いイベントを見つけるには、分類や異常検出の方が最適な方法です。
11.2 相関ルールと高頻度項目セット
Aprioriアルゴリズムは、高頻度項目セット内の項目間の確率的な関係を表すルールを計算します。たとえば、A、BおよびCを含む高頻度項目セットから、「トランザクションにAとBが含まれる場合、Cも含まれる可能性が高い」というルールが導出されます。
相関ルールは、項目または項目のグループがある確率で別の項目の存在を示すことを表します。ターゲットを予測するデシジョン・ツリー・ルールとは異なり、相関ルールは単に相関関係を表します。
11.2.1 前件と後件
相関ルールのIFコンポーネントは、前件と呼ばれます。THENコンポーネントは、後件と呼ばれます。前件と後件は結合しておらず、共通の項目を持ちません。
Oracle Data Miningでは、前件に1つ以上の項目を、後件に1つの項目を持つ相関ルールをサポートしています。
11.3 Apriori用のデータ準備
相関モデルは、トランザクショナル・データを使用するように設計されています。トランザクショナル・データでは、ケースIDと各ケースの値の間に1対多関係が存在します。各ケースIDと値のペアは、個別のレコード(行)に指定されます。
11.3.1 ネイティブ・トランザクショナル・データとスター・スキーマ
11.3.2 項目と集合
トランザクショナル・データで、項目の集合は、各ケースに関連付けられます。集合には、理論上、集合のメンバーとして可能なすべてのものが含まれます。たとえば、1つのマーケット・バスケット・トランザクションにおいて、理論上は、すべての製品を購入できます。ただし、実際は、考えられるすべての項目のごく一部のみが1つのトランザクションに存在し、マーケット・バスケットのアイテムはその店舗で入手できるごく一部の項目のみを表します。
11.3.3 スパース・データ
スパース性を通じて項目の欠損について学習します。
集合内で複数の項目が欠損している場合はデータがスパースであることがわかります。項目の欠損は、NULL値が存在する場合と、単に欠損している場合があります。
トランザクショナル・データ内のNULLは、既知であるがトランザクションには存在しない値を表すものとみなされます。たとえば、数百個ある商品のうち3つの商品が、1回のトランザクションで購入されたとします。購入されなかった商品は既知の商品ですが、トランザクションには含まれていません。
Oracle Data Miningでは、トランザクショナル・データにスパース性が想定されます。Aprioriアルゴリズムは、スパース・データの処理に対して最適化されています。
ノート:
Aprioriは自動データ準備の影響を受けません。
11.3.4 サンプリングの向上
相関ルール(AR)では、RiondatoとUpfalの研究に基づいて、パフォーマンスが保証された適切なサンプル・サイズを使用できます。
ARアルゴリズムは、次の入力値からサンプル・サイズを計算します。
-
データセットのdインデックス
-
絶対誤差ε
-
信頼度γ
dインデックスは、最小でも長さがdで少なくともd個のトランザクションがデータセッに含まれるように最大整数dとして定義されます。これは、Vapnik-Chervonenkis(VC)次元の上限です。ARアルゴリズムは、データセット内のすべてのトランザクションの長さをスキャンしてデータセットのdインデックスを計算します。
ユーザーは、絶対誤差のεパラメータと信頼度のγパラメータを指定します。大きなdインデックス、小さなAR支持度、小さなεまたは大きなγは、サンプル・サイズが大きくなる要因となる可能性があります。サンプル・サイズは、近似AR(サンプリングから取得)の支持度と信頼度の両方の絶対誤差が、確率(または信頼度)が少なくともγである正確なARと比較してε未満であることを理論的に保証します。このドキュメントでは、このサンプル・サイズはAR固有のサンプル・サイズと呼ばれます。
11.3.4.1 サンプリングの実装
サンプル・サイズは、ユーザーがサンプリングをオン(ODMS_SAMPLING
をODMS_SAMPLING_ENABLE
に設定)にし、サンプル・サイズを指定しない(ODMS_SAMPLE_SIZE
が未指定)場合にのみ計算されます。
使用上のノート
-
ODMS_SAMPLING
が未指定であるか、ODMS_SAMPLING_DISABLE
が設定されている場合、ARのサンプリングは実行されず、正確なARが取得されます。 -
ODMS_SAMPLING
にODMS_SAMPLING_ENABLE
が設定されていて、ODMS_SAMPLE_SIZE
に正の整数に指定されている場合は、ユーザー指定のサンプル・サイズ(ODMS_SAMPLE_SIZE
)が使用されます。サンプリングは、ARアルゴリズムを実行する前の、全般的なデータ準備段階で実行されます。AR固有のサンプル・サイズは計算されません。近似ARが取得されます。 -
ODMS_SAMPLING
にODMS_SAMPLING_ENABLE
が設定され、ODMS_SAMPLE_SIZE
が指定されてない場合、AR固有のサンプル・サイズが計算され、ARアルゴリズムでサンプリングが実行されます。近似ARが取得されます。ノート:
算出されたAR固有のサンプル・サイズがデータセット内のトランザクションの合計サイズ以上となる場合、サンプリングは実行されず、正確なARが取得されます。
ARのサンプル・サイズの見当が付かない場合は、ODMS_SAMPLE_SIZE
を未指定のままとし、サンプリング・パラメータに適切な値を指定するにとどめ、ARアルゴリズムに適切なAR固有のサンプル・サイズを計算させることをお薦めします。
11.4 相関ルールの計算
相関分析の最初のステップは、項目セットを列挙します。項目セットとは、トランザクション内の2つ以上の項目のあらゆる組合せのことです。
11.4.1 項目セット
項目セットについて学習します。
1つの項目セットに含める項目の最大数はユーザーが指定します。最大数を2にした場合は、2項目から構成されるすべての組合せがカウントされます。最大数が2を超える場合は、2項目から構成されるすべての組合せ、3項目から構成されるすべての組合せ、以降指定した最大数の項目から構成されるすべての組合せがカウントされます。
次の表は、次の例に示したトランザクションから得られた項目セットの一覧です(ここでは、項目セットの項目の最大数を3に設定したものとします)。
表11-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) |
例11-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
11.4.2 高頻度項目セット
高頻度項目セットおよびサポートについて学習します。
相関ルールは項目セットに基づいて計算されます。可能性のあるすべての項目セットからルールが生成された場合、非常に多くのルールが存在することになり、意味のあるルールが得られないことがあります。また、モデルの作成に長い時間がかかる場合もあります。そのため、通常は、データ内での発生頻度が高い項目セットのみを使用してルールを生成する方が望ましいと言えます。高頻度項目セットとは、ユーザーが指定した最小頻度で発生する項目セットのことです。
最小頻度の項目セットの支持度は、相関ルール用に使用される項目セット数を制限するための割合であり、ユーザーが指定します。項目セットは、ルールの基盤として使用されるためには、全トランザクションにおいて少なくともこの割合で出現する必要があります。
次の表は、表11-1の項目セットのうち、支持度が66%を超える高頻度項目セットをまとめたものです。
表11-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% |
関連項目
11.4.3 例: 高頻度項目セットからのルールの計算
高頻度項目セットからのルールの計算の例。
次の表に、「相関」で計算した項目セットおよび高頻度項目セットを示します。高頻度項目セットは、67%の最小支持度で発生する項目セットであり、3つのトランザクションのうち少なくとも2つにこの項目セットが含まれている必要があります。
表11-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) |
表11-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」というルールの信頼度はどのくらいでしょうか。
表11-3から、次のことがわかります。
-
3つのトランザクションにはすべてBが含まれている(3/3または100%)。
-
2つのトランザクションのみにBとCの両方が含まれている(2/3または67%)。
-
したがって、ルール「Bの場合、C」の信頼度は、67/100または67%である。
次の表に、表11-4の高頻度項目セットから導出できるルールを示します。
表11-5 高頻度項目セットとルール
高頻度項目セット | ルール | 確率(前件と後件) /確率(前件) | 信頼度 |
---|---|---|---|
(B,C) |
|
|
|
(B,D) |
|
|
|
(B,E) |
|
|
|
(C,E) |
|
|
|
(D,E) |
|
|
|
(B,C,E) |
|
|
|
(B,D,E) |
|
|
|
最小信頼度が70%の場合、これらの高頻度項目セットについて10のルールが生成されます。最小信頼度が60%の場合、16のルールが生成されます。
ヒント:
モデルの作成時間を短縮し、生成されるルールの数を減らすには、最小信頼度の値を大きくします。
関連項目
11.4.4 集計
集計は、ユーザーが集計する相関ルール・モデルを選択する各項目に関連する数量を指します。
複数の集計が存在する可能性があります。たとえば、ユーザーは利益および数量の両方を集計するモデルを指定できます。
11.4.5 例: 集計の計算
次の例は、集計の概念を示します。
食料品店データの集計の計算
食料品店に次のデータがあるとします。
表11-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です。
11.5 相関ルールの評価
最小支持度と最小信頼度の使用によって、相関モデルの作成が左右されます。支持度と信頼度は、相関モデルで生成されるルールの質を評価するための主要なメトリックでもあります。また、Oracle Data Miningでは相関ルールのリフトがサポートされています。これらの統計上の測度は、ルールのランク付けに使用できるので予測に役立ちます。
11.5.2 最小サポート数
最小サポート数は、各ルールが満たす必要のあるトランザクションの最小しきい値を定義します。
トランザクションの数が不明な場合、サポート割合のしきい値パラメータを適切に設定するのが難しい場合があります。このため、サポートはトランザクション数で表すこともできます。ここで、使用されている2つのしきい値のうち大きい方を使用して、希少な項目セットを除外します。デフォルトは1
で、この基準が適用されないことを示します。
11.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)
11.5.4 逆確信度
ルールの逆確信度は、ルールが発生するトランザクションの数を後件が発生するトランザクションの数で割ったものとして定義されています。
逆確信度は結果が頻繁であるために発生するルールを排除します。デフォルトは0
です。
11.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未満のルールでは、偶然以上に購入を確実に予測できないため、支持度と信頼度が高くても、実際の組合せ購入の確率は示されません。
ヒント:
モデルの作成時間を短縮し、単純なルールを生成するには、ルールの最大長の値を小さくします。
ヒント:
モデルの作成時間を短縮し、生成されるルールの数を減らすには、最小支持度の値を大きくします。