相関ルール学習

相関ルール学習は、大規模データベース内の変数間の興味深い関係を発見するためのルールベースの機械学習手法です。これは、興味深さの尺度を使用して、データベースで発見された強力なルールを識別することを目的としています。 ^[1]さまざまなアイテムを含む任意のトランザクションでは、相関ルールは、特定のアイテムがどのようにまたはなぜ接続されているかを決定するルールを発見することを目的としています。

強いルールの概念に基づいて、Rakesh Agrawal、Tomasz Imieliński、Arun Swami ^[2]は、スーパーマーケットのPOSシステムで記録された大規模な取引データ内の製品間の規則性を発見するための相関ルールを導入しました。たとえば、スーパーマーケットの販売データで見つかったルールは、顧客が玉ねぎとジャガイモを一緒に購入した場合、ハンバーグも購入する可能性が高いことを示しています。このような情報は、プロモーション価格や製品の配置などのマーケティング活動に関する決定の基礎として使用できます。 ${\displaystyle \{\mathrm {onions,potatoes} \}\Rightarrow \{\mathrm {burger} \}}$

上記のマーケット バスケット分析の例に加えて、相関ルールは現在、Web 使用状況マイニング、侵入検知、連続生産、バイオインフォマティクスなど、多くのアプリケーション領域で使用されています。シーケンス マイニングとは対照的に、相関ルール学習では通常、トランザクション内またはトランザクション間のアイテムの順序は考慮されません。

関連ルールアルゴリズム自体はさまざまなパラメータで構成されており、データマイニングの専門知識を持たない人にとっては実行が難しく、理解するのが難しいルールが多くあります。^[3]

^{Agrawal、Imieliński、Swami [2]}によるオリジナルの定義によれば、関連ルールマイニングの問題は次のように定義されます。

をアイテムと呼ばれるn 個のバイナリ属性の集合とします。 ${\displaystyle I=\{i_{1},i_{2},\ldots ,i_{n}\}}$

をデータベースと呼ばれるトランザクションの集合とします。 ${\displaystyle D=\{t_{1},t_{2},\ldots ,t_{m}\}}$

D内の各トランザクションには一意のトランザクション ID があり、 I内の項目のサブセットが含まれています。

ルールは次の形式の含意として定義されます。

${\displaystyle X\Rightarrow Y}$、 どこ。${\displaystyle X,Y\subseteq I}$

Agrawal、Imieliński 、 Swami ^[2]では、集合と単一の項目の間でのみルールが定義されています。${\displaystyle X\Rightarrow i_{j}}$${\displaystyle i_{j}\in I}$

すべてのルールは、アイテムセットとも呼ばれる 2 つの異なるアイテムセットXとYで構成されます。ここで、Xは前提または左側 (LHS)、Y は 結果または右側 (RHS)と呼ばれます。前提はデータ内で見つかるアイテムであり、結果は前提と組み合わせたときに見つかるアイテムです。このステートメントは、多くの場合、 if X then Yと読み取られます。ここで、前提 ( X ) はifであり、結果 ( Y ) はthenです。これは、理論上、データセットでX が発生するたびに、Y も発生することを意味します。 ${\displaystyle X\Rightarrow Y}$

相関ルールは、頻繁な if-then パターンをデータで検索し、サポートと信頼性の特定の基準を使用して最も重要な関係を定義することによって作成されます。サポートは、指定されたデータにアイテムが出現する頻度の証拠であり、信頼性は if-then ステートメントが真であると判断される回数によって定義されます。ただし、使用できる 3 番目の基準があります。これはリフトと呼ばれ、期待される信頼性と実際の信頼性を比較するために使用できます。リフトは、if-then ステートメントが真であると判断される回数を示します。

関連ルールは、2 つ以上のアイテムによって作成されるアイテムセットから計算するために作成されます。データからのすべての可能なアイテムセットを分析してルールを作成すると、ルールが多すぎて意味をなさなくなります。そのため、関連ルールは通常、データによって適切に表現されるルールから作成されます。

特定の分析や結果を見つけるために使用できるデータマイニング手法は数多くあります。たとえば、分類分析、クラスタリング分析、回帰分析があります。^[4]どの手法を使用するかは、データで何を探しているかによって異なります。関連ルールは主に、分析や顧客行動の予測を見つけるために使用されます。分類分析の場合、質問、決定、行動の予測に使用される可能性が最も高くなります。^[5]クラスタリング分析は、データ内の関係性について仮定がない場合に主に使用されます。^[5]回帰分析は、多数の独立変数から連続従属変数の値を予測する場合に使用されます。^[5]

利点

相関ルールを使用すると、データ セット間の相関関係や共起関係を理解するのに役立つパターンを見つけるなど、多くの利点があります。相関ルールを使用する非常に良い実世界の例は、医療です。医療では、患者の診断に相関ルールを使用します。多くの病気が同様の症状を共有するため、患者を診断する際には、考慮すべき変数がたくさんあります。相関ルールを使用すると、医師は過去の症例の症状の関係を比較することで、病気の条件付き確率を判断できます。^[6]

欠点

しかし、アソシエーションルールには、マイニングアルゴリズムの適切なパラメータとしきい値設定を見つけるなど、さまざまな欠点もあります。しかし、発見されたルールの数が多いという欠点もあります。その理由は、ルールが関連性のあるものであると確実に見つかるわけではないだけでなく、アルゴリズムのパフォーマンスが低下する可能性があるためです。実装されたアルゴリズムには、変数とパラメータが多すぎる場合があります。データマイニングの概念がよくわからない人にとっては、理解に苦しむ可能性があります。^[7]

閾値

アソシエーション ルールを使用する場合、サポートと信頼度のみを使用する可能性が高くなります。ただし、これは、ユーザーが指定した最小サポートとユーザーが指定した最小信頼度を同時に満たす必要があることを意味します。通常、アソシエーション ルールの生成は、適用する必要がある 2 つの異なるステップに分割されます。

1. データベース内にあるすべての頻繁なアイテムセットを見つけるための最小サポートしきい値。
2. ルールを作成するために見つかった頻繁なアイテムセットに対する最小信頼しきい値。

サポートしきい値は30%、信頼しきい値は50%です

左側の表は元の整理されていないデータで、右側の表はしきい値別に整理されています。この場合、アイテム C はサポートと信頼性の両方のしきい値を上回っているため、1 位になっています。アイテム A はしきい値がぴったりであるため、2 位になっています。アイテム D はサポートのしきい値を満たしていますが、信頼性のしきい値は満たしていません。アイテム B はサポートと信頼性のどちらのしきい値も満たしていないため、最後になっています。

データベース内のすべての頻出アイテムセットを見つけることは、すべてのデータを調べてすべての可能なアイテムセットからすべての可能なアイテムの組み合わせを見つける必要があるため、簡単な作業ではありません。 可能なアイテムセットの集合はI上のべき集合で、サイズは です。もちろん、これは有効なアイテムセットとは見なされない空集合を除外することを意味します。 ただし、べき集合のサイズは、べき集合I内にあるアイテムの数nで指数関数的に増加します。サポートの下方閉包特性^{[2] [8]} (反単調性^[9]とも呼ばれる)を使用すると、効率的な検索が可能になります。 これにより、頻出アイテムセットとそのすべてのサブセットも頻出であることが保証され、したがって、頻出アイテムセットのサブセットとして低頻度アイテムセットが存在しないことになります。 この特性を利用して、効率的なアルゴリズム (例: Apriori ^[10]および Eclat ^[11] ) はすべての頻出アイテムセットを見つけることができます。 ${\displaystyle 2^{n}-1}$

概念を説明するために、スーパーマーケットのドメインからの小さな例を使用します。表 2 は、アイテムを含む小さなデータベースを示しています。各エントリの値が 1 の場合、対応するトランザクションにアイテムが存在することを意味し、値が 0 の場合、そのトランザクションにアイテムが存在しないことを意味します。アイテムのセットは です。 ${\displaystyle I=\{\mathrm {milk,bread,butter,beer,diapers,eggs,fruit} \}}$

スーパーマーケットのルールの例としては、バターとパンを購入した場合、顧客は牛乳も購入する、というものがあります。 ${\displaystyle \{\mathrm {butter,bread} \}\Rightarrow \{\mathrm {milk} \}}$

すべての可能なルールのセットから興味深いルールを選択するために、重要性と関心のさまざまな尺度に対する制約が使用されます。最もよく知られている制約は、サポートと信頼性の最小しきい値です。

をアイテムセット、を関連ルール、T を特定のデータベースのトランザクションのセット とします。${\displaystyle X,Y}$${\displaystyle X\Rightarrow Y}$

注: この例は非常に小さいです。実際のアプリケーションでは、ルールが統計的に有意であるとみなされるには、数百のトランザクションのサポートが必要であり、^{[引用が必要]}、データセットには数千または数百万のトランザクションが含まれることがよくあります。

サポートは、アイテムセットがデータセットに出現する頻度を示します。

^{この例では、 [12]}と書くことでサポートを説明しやすくなります。ここで、AとBはトランザクション内で同時に発生する別々のアイテムセットです。 ${\displaystyle {\text{support}}=P(A\cap B)={\frac {({\text{number of transactions containing }}A{\text{ and }}B)}{\text{ (total number of transactions)}}}}$

表2を例に挙げると、アイテムセットは全トランザクションの20%（5トランザクション中1トランザクション）で発生するため、サポートは1/5=0.2となります。Xのサポート引数は前提条件の集合であるため、大きくなるにつれて（より包括的になるのではなく）より制限的になります。^[13]${\displaystyle X=\{\mathrm {beer,diapers} \}}$

さらに、アイテムセットは全トランザクションの 20% にも出現するため、 1/5 = 0.2のサポートを持ちます。${\displaystyle Y=\{\mathrm {milk,bread,butter} \}}$

前提と結論を使用すると、データ マイナーは、データセット全体と比較して、複数のアイテムが一緒に購入されることのサポートを判断できます。たとえば、表 2 は、牛乳を購入したらパンを購入する場合のサポートが 0.4 または 40% であることを示しています。これは、5 つのトランザクションのうち 2 つで、牛乳とパンの両方が購入されているためです。この例のようにデータセットが小さい場合、サンプル数が少ないと強い相関関係を確認するのは困難ですが、データセットが大きくなると、サポートを使用して、スーパーマーケットの例で 2 つ以上の製品間の相関関係を見つけることができます。

最小サポートしきい値は、どのアイテムセットが優先されるか、または興味深いかを判断するのに役立ちます。

表 3 でサポートしきい値を ≥ 0.4 に設定すると、サンプルは最小しきい値の 0.4 を満たさないため削除されます。最小しきい値は、サンプルがデータセット内で重要または興味深いと判断するのに十分なサポートまたは信頼性がない場合にサンプルを削除するために使用されます。 ${\displaystyle \{\mathrm {milk} \}\Rightarrow \{\mathrm {eggs} \}}$

興味深いサンプルを見つけるもう 1 つの方法は、(サポート) × (信頼度) の値を見つけることです。これにより、データ マイナーは、データセット内で強調表示されるほどサポートと信頼度が高いサンプルを確認し、サンプルを詳しく調べて項目間の接続に関する詳細情報を見つけることができます。

サポートはデータセット全体と比較して製品間のつながりを見つけるのに役立ちますが、信頼性は 1 つ以上のアイテムと別のアイテム間のつながりを調べます。以下の表は、表 4 の情報を使用して信頼性値を導き出し、サポートとサポート × 信頼性の比較と対比を示しています。

Tに関するXのサポートは、データセット内のアイテムセットXを含むトランザクションの割合として定義されます。トランザクションを で表すと、iはトランザクションの一意の識別子、tはそのアイテムセットであり、サポートは次のように記述できます。 ${\displaystyle (i,t)}$

${\displaystyle \mathrm {support\,of\,X} ={\frac {|\{(i,t)\in T:X\subseteq t\}|}{|T|}}}$

この表記法は、アイテムとアイテムセットが上記のスーパーマーケットの例ほど簡単ではない、より複雑なデータセットを定義するときに使用できます。サポートが使用できる他の例としては、病気を引き起こすために集合的に作用する遺伝子変異のグループを見つけること、アップグレードオファーに反応する加入者の数を調査すること、ドラッグストアで一緒に購入されない製品を見つけることなどがあります。^[12]

信頼度は、 Xを満たすすべてのトランザクションのうち、 Yも満たすトランザクションの割合です。^[14]

Tに関して、相関ルールの信頼度値（ と表記されることが多い）は、存在するX値の合計量に対するXとY の両方を含むトランザクションの比率であり、ここでXは前提であり、Yは結果です。 ${\displaystyle X\Rightarrow Y}$

信頼度は条件付き確率 の推定値として解釈することもできる。条件付き確率とは、トランザクションにLHSも含まれているという条件下で、トランザクション内でルールのRHSが見つかる確率である。^{[13] [15]}${\displaystyle P(E_{Y}|E_{X})}$

一般的には次のように表現されます。

${\displaystyle \mathrm {conf} (X\Rightarrow Y)=P(Y|X)={\frac {\mathrm {supp} (X\cup Y)}{\mathrm {supp} (X)}}={\frac {{\text{number of transactions containing }}X{\text{ and }}Y}{{\text{number of transactions containing }}X}}}$

この式は、データセット内のトランザクションXとYの共起を、 Xのみを含むトランザクションに対する比率で計算することで、信頼性を計算できることを示しています。つまり、 XとYの両方のトランザクション数を、 X のみのトランザクション数で割ることになります。

たとえば、表 2 は、データセット内で信頼度が であるルールを示しています。これは、顧客がバターとパンを購入するたびに、牛乳も購入することを示しています。この特定の例は、バターとパンの両方を含むトランザクションに対してルールが 100% 正しいことを示しています。ただし、ルール の信頼度は です。これは、果物が購入される回数の 67% で卵が購入されることを示しています。この特定のデータセット内では、果物は合計 3 回購入され、そのうち 2 回は卵の購入です。 ${\displaystyle \{\mathrm {butter,bread} \}\Rightarrow \{\mathrm {milk} \}}$${\displaystyle {\frac {1/5}{1/5}}={\frac {0.2}{0.2}}=1.0}$${\displaystyle \{\mathrm {fruit} \}\Rightarrow \{\mathrm {eggs} \}}$${\displaystyle {\frac {2/5}{3/5}}={\frac {0.4}{0.6}}=0.67}$

大規模なデータセットの場合、信頼度の最小しきい値、またはパーセンテージのカットオフは、項目の関係を判断するのに役立ちます。この方法を表 2 の一部のデータに適用すると、要件を満たさない情報が削除されます。表 4 は、信頼度の最小しきい値が 0.5 (50%) である関連ルールの例を示しています。信頼度が 0.5 未満のデータはすべて省略されます。しきい値を生成すると、最も頻繁に共起する項目を強調することで、データの調査が進むにつれて項目間の関連が強くなることができます。この表では、表 3 の信頼度情報を使用してサポート × 信頼度の列を実装しています。この列では、1 つの概念だけでなく、信頼度とサポートの両方を介して項目間の関係が強調表示されます。サポート × 信頼度によるルールのランク付けは、特定のルールの信頼度をそのサポートに掛け合わせたもので、項目間の関係をより深く理解するために実装されることが多いです。

全体として、相関ルール マイニングで信頼度を使用することは、データの関係を意識させる優れた方法です。信頼度の最大の利点は、アイテムの共起を特定のルール内の先行条件の総発生と比較するため、セット内の特定のアイテム間の関係を強調することです。ただし、信頼度は、相関ルール マイニングのすべての概念に最適な方法ではありません。信頼度を使用することの欠点は、関連性について複数の異なる見解を提供しないことです。たとえば、サポートとは異なり、信頼度はデータセット全体と比較した特定のアイテム間の関係の観点を提供しないため、たとえば、牛乳とパンは信頼度で 100% 発生する可能性がありますが、サポートは 0.4 (40%) しかありません。このため、関係を定義するために 1 つの概念だけに絶えず依存するのではなく、サポート × 信頼度などの他の観点を確認することが重要です。

ルールのリフトは次のように定義され ます。

${\displaystyle \mathrm {lift} (X\Rightarrow Y)={\frac {\mathrm {supp} (X\cup Y)}{\mathrm {supp} (X)\times \mathrm {supp} (Y)}}}$

または、観測された支持度と、XとYが独立している場合に期待される支持度の比。

たとえば、ルールのリフトは です。 ${\displaystyle \{\mathrm {milk,bread} \}\Rightarrow \{\mathrm {butter} \}}$${\displaystyle {\frac {0.2}{0.4\times 0.4}}=1.25}$

ルールのリフトが 1 の場合、前提の発生確率と結果の発生確率は互いに独立していることを意味します。2 つのイベントが互いに独立している場合、その 2 つのイベントを含むルールを導くことはできません。

リフトが 1 より大きい場合、これら 2 つの発生が相互に依存している度合いがわかり、それらのルールは将来のデータ セットの結果を予測するのに役立つ可能性があります。

リフトが 1 未満の場合、アイテムは互いに代替可能であることがわかります。つまり、1 つのアイテムの存在は他のアイテムの存在に悪影響を及ぼし、その逆も同様です。

リフトの価値は、ルールのサポートとデータセット全体の両方を考慮することです。^[13]

[赤]

規則の確信は次のように定義される。[ 16 ^]${\displaystyle \mathrm {conv} (X\Rightarrow Y)={\frac {1-\mathrm {supp} (Y)}{1-\mathrm {conf} (X\Rightarrow Y)}}}$

たとえば、ルールの確信度は で、X と Y が独立している場合に X が Y なしで発生すると予想される頻度 (つまり、ルールが誤った予測を行う頻度) を誤った予測の観測頻度で割った比率として解釈できます。この例では、確信度値 1.2 は、Xと Y の関連が純粋にランダムな偶然である場合、ルールが誤っている頻度が 20% 増加する (1.2 倍) ことを示しています。 ${\displaystyle \{\mathrm {milk,bread} \}\Rightarrow \{\mathrm {butter} \}}$${\displaystyle {\frac {1-0.4}{1-0.5}}=1.2}$${\displaystyle \{\mathrm {milk,bread} \}\Rightarrow \{\mathrm {butter} \}}$

信頼度に加えて、ルールの 興味深さを測る他の尺度も提案されています。一般的な尺度には次のようなものがあります。

• 全信任^[17]
• 集団の力^[18]
• レバレッジ^[19]

Tanら^[20]とHahsler ^[21]は、さらにいくつかの尺度を提示し比較しています。ユーザーが知っていることをモデル化できる技術を探すこと（そしてこれらのモデルを興味深さの尺度として使用すること）は、現在「主観的興味深さ」という名前で活発な研究動向となっています。

相関ルールの概念は、特に1993年のAgrawalらの論文^[2]によって普及しました。この論文は、2021年4月現在、Google Scholarによると23,790件以上の引用を獲得しており、データマイニング分野で最も引用されている論文の1つです。しかし、現在「相関ルール」と呼ばれているものは、 Petr Hájekら^[23 ]が開発した一般的なデータマイニング手法であるGUHAに関する1966年の論文^{[22]ですでに紹介されています。}

最小サポートと信頼度をすべての関連ルールを見つけるために使用した初期（1989年頃）の例としては、特徴ベースモデリングフレームワークがあり、これはユーザーが定義した制約を超えるすべてのルールを見つけるものでした。[ ^24]${\displaystyle \mathrm {supp} (X)}$${\displaystyle \mathrm {conf} (X\Rightarrow Y)}$

関連性を発見するための標準的な方法の 1 つの制限は、関連性があるように見えるアイテムのコレクションを探すために膨大な数の可能性のある関連性を検索すると、多くの偽の関連性が見つかるリスクが高いことです。これらは、データ内で予期しない頻度で共起するアイテムのコレクションですが、偶然にのみ発生します。たとえば、10,000 個のアイテムのコレクションを検討していて、左側に 2 つのアイテム、右側に 1 つのアイテムを含むルールを探しているとします。このようなルールは約 1,000,000,000,000 個あります。有意水準 0.05 で独立性の統計テストを適用すると、関連性がない場合にルールを受け入れる可能性は 5% しかないことを意味します。関連性がないと仮定すると、それでも 50,000,000,000 個のルールが見つかると予想されます。統計的に健全な関連性の発見^{[25] [26]}はこのリスクを制御し、ほとんどの場合、偽の関連性を発見するリスクをユーザーが指定した有意水準まで低減します。

関連ルールを生成するためのアルゴリズムが数多く提案されています。

よく知られているアルゴリズムとしては、Apriori、Eclat、FP-Growth などがありますが、これらは頻繁なアイテムセットをマイニングするためのアルゴリズムであるため、仕事の半分しかこなせません。データベースで見つかった頻繁なアイテムセットからルールを生成するには、その後に別のステップを実行する必要があります。

Apriori は、頻出アイテム セットのマイニングと相関ルールの学習のために、1994 年に R. Agrawal と R. Srikant によって考案されました。データベース内の頻出アイテムを識別し、それらのアイテム セットが十分に頻繁に出現する限り、それらをより大きなアイテム セットに拡張することで処理が進められます。頻出アイテム セットのプロパティに関する事前知識を使用するため、このアルゴリズムの名前は Apriori です。

概要: Apriori は「ボトムアップ」アプローチを使用します。このアプローチでは、頻出サブセットが一度に 1 項目ずつ拡張され (候補生成と呼ばれる手順)、候補のグループがデータに対してテストされます。アルゴリズムは、それ以上の拡張が成功しなくなると終了します。Apriori は、幅優先探索とハッシュ ツリー構造を使用して、候補アイテム セットを効率的にカウントします。長さ のアイテム セットから長さ の候補アイテム セットを生成します。次に、まれなサブ パターンを持つ候補をプルーニングします。下方閉包補題によれば、候補セットには、頻出する長さ のアイテム セットがすべて含まれます。その後、トランザクション データベースをスキャンして、候補の中から頻出アイテム セットを決定します。

例:各行が、アルファベットの文字でラベル付けされた特定の組み合わせの変異を持つ癌サンプルであると仮定します。たとえば、行に {a, c} がある場合、これは変異 'a' と変異 'c' の影響を受けていることを意味します。

ここで、各文字の出現回数をカウントして、頻出アイテム セットを生成します。これは、サポート値の検索とも呼ばれます。次に、最小サポートしきい値を選択してアイテム セットを整理します。このアルゴリズムのパスでは、3 を選択します。

すべてのサポート値が 3 以上なので、プルーニングは行われません。頻出アイテム セットは {a}、{b}、{c}、および {d} です。この後、入力セット内の突然変異のペアをカウントしてプロセスを繰り返します。

ここで、最小サポート値を 4 にして、剪定後に {a, d} のみが残るようにします。次に、頻繁なアイテム セットを使用して、トリプレットの組み合わせを作成します。次に、入力セット内の突然変異のトリプレットの発生をカウントして、プロセスを繰り返します。

アイテムが 1 つしかないため、次の 4 つ組の組み合わせのセットは空になり、アルゴリズムは停止します。

利点と制限:

Apriori にはいくつかの制限があります。候補生成により候補セットが大きくなる可能性があります。たとえば、10^4 の頻繁な 1 項目セットは、10^7 の候補 2 項目セットを生成します。また、このアルゴリズムはデータベースを頻繁にスキャンする必要があり、具体的には n+1 回のスキャンが必要です (n は最長パターンの長さ)。Apriori は Eclat アルゴリズムよりも低速です。ただし、データセットが大きい場合、Apriori は Eclat に比べてパフォーマンスが優れています。これは、Eclat アルゴリズムではデータセットが大きすぎると tid リストがメモリに対して大きくなりすぎるためです。FP-growth は Apriori と Eclat よりもパフォーマンスが優れています。これは、FP-growth アルゴリズムには候補生成やテストがなく、コンパクトなデータ構造を使用し、データベース スキャンが 1 回しかないためです。^[27]

Eclat ^[11] (別名ECLAT、Equivalence Class Transformationの略) は、頻出アイテムセット格子グラフを深さ優先探索(DFS) 方式でトラバースするバックトラッキングアルゴリズムです。Aprioriアルゴリズムで使用される幅優先探索(BFS) トラバーサルでは、アイテムセットをチェックする前にそのサブセットをすべてチェックすることになりますが、DFS トラバーサルでは、より大きなアイテムセットをチェックし、下向きに閉じる特性により、一部のサブセットのサポートのチェックを省くことができます。さらに、DFS は BFS よりも空間計算量が少ないため、メモリ使用量もほぼ確実に少なくなります。

これを説明するために、頻出アイテムセット {a, b, c} があるとします。DFS は頻出アイテムセット格子のノードを次の順序でチェックします: {a} → {a, b} → {a, b, c}。この時点で、下方閉包特性により、{b}、{c}、{a, c}、{b, c} はすべてサポート制約を満たすことがわかります。BFS は、最終的にチェックする前に、{a, b, c} の各サブセットを探索します。アイテムセットのサイズが大きくなるにつれて、そのサブセットの数は組み合わせ爆発を起こします。

局所性を高める特性を持つため、順次実行と並列実行の両方に適しています。^{[28] [29]}

FPは頻繁なパターンを意味します。^[30]

最初のパスでは、アルゴリズムはトランザクションのデータセット内の項目 (属性と値のペア) の出現回数をカウントし、これらのカウントを「ヘッダー テーブル」に格納します。2 番目のパスでは、トランザクションをトライに挿入して FP ツリー構造を構築します。

各トランザクションのアイテムは、ツリーを迅速に処理できるように、挿入する前にデータセット内の頻度の降順で並べ替える必要があります。各トランザクションで最小サポート要件を満たさないアイテムは破棄されます。多くのトランザクションが最も頻繁に使用されるアイテムを共有する場合、FP ツリーはツリーのルート近くで高い圧縮率を実現します。

メイン データセットのこの圧縮バージョンを再帰的に処理すると、候補アイテムを生成してデータベース全体に対してテストする (アプリオリ アルゴリズムの場合のように) のではなく、頻繁に使用されるアイテム セットが直接増加します。

成長は、ヘッダー テーブルの下部、つまりサポートが最も小さい項目から始まり、その項目で終わるすべてのソート済みトランザクションが検索されます。この項目を と呼びます。 ${\displaystyle I}$

に射影された元の FP ツリーである新しい条件付きツリーが作成されます。射影されたツリー内のすべてのノードのサポートが再カウントされ、各ノードは子の数の合計を取得します。最小サポートを満たさないノード (およびサブツリー) は削除されます。 を条件とする個々の項目が最小サポートしきい値を満たさなくなると、再帰的な成長は終了します。結果として得られるルートから へのパスは頻繁な項目セットになります。このステップの後、処理は元の FP ツリーの次にサポートが少ないヘッダー項目で続行されます。 ${\displaystyle I}$${\displaystyle I}$${\displaystyle I}$

再帰プロセスが完了すると、すべての頻繁なアイテムセットが見つかり、関連ルールの作成が始まります。^[31]

ASSOC手順^{[32]は、高速}ビット文字列操作を使用して一般化された相関ルールをマイニングするGUHA法です。この方法でマイニングされた相関ルールは、aprioriによって出力されるものよりも一般的です。たとえば、「アイテム」は論理積と論理和の両方で接続でき、ルールの前提と結果の関係は、aprioriのように最小のサポートと信頼度を設定することに制限されません。サポートされている関心尺度の任意の組み合わせを使用できます。

OPUSはルール発見のための効率的なアルゴリズムであり、ほとんどの代替アルゴリズムとは対照的に、最小サポートなどの単調または反単調制約を必要としません。^[33]当初は固定された結果のルールを見つけるために使用されていましたが^{[33] [34]、}その後、結果が任意の項目であるルールを見つけるように拡張されました。^[35] OPUS検索は、人気のあるMagnum Opus関連付け発見システムの中核技術です。

相関ルールマイニングに関する有名な話は、「ビールとおむつ」の話です。スーパーマーケットの買い物客の行動に関する調査によると、おむつを購入する顧客（おそらく若い男性）はビールも購入する傾向があることがわかりました。この逸話は、日常のデータから予期しない相関ルールが見つかる例として人気を博しました。この話がどの程度真実であるかについてはさまざまな意見があります。^[36]ダニエル・パワーズは次のように述べています。^[36]

1992 年、テラデータの小売コンサルティング グループのマネージャーである Thomas Blischok 氏と彼のスタッフは、約 25 の Osco Drug ストアからの 120 万のマーケット バスケットの分析を準備しました。類似性を識別するためにデータベース クエリが開発されました。分析により、「午後 5 時から 7 時の間に消費者がビールとおむつを購入していることがわかった」。Osco のマネージャーは、ビールとおむつの関係を利用して、棚でこれらの製品を近くに配置することはしませんでした。

マルチリレーション関連ルール（MRAR）：各項目が複数の関係を持つ可能性がある関連ルールです。これらの関係は、エンティティ間の間接的な関係を示します。最初の項目が 3 つの関係live in、nearly、humidで構成されている次の MRAR を考えてみましょう。「湿潤気候タイプの都市の近くに住んでいて、20 歳未満の人の健康状態は良好です。」このような関連ルールは、RDBMS データまたはセマンティック ウェブ データから抽出できます。^[37]${\displaystyle \implies }$

コントラストセット学習は連合学習の一種である。コントラストセット学習者は、サブセット間での分布が有意に異なるルールを使用する。 ^{[38] [39]}

加重クラス学習は連想学習の別の形式であり、データ マイニング結果の消費者にとっての特定の問題に焦点を当てるために、クラスに重みを割り当てることができます。

高次パターン発見は、複雑な現実世界のデータに固有の高次（多元的）パターンやイベントの関連性を捉えることを容易にする。 ^[40]

K 最適パターン検出は、各パターンがデータ内に頻繁に出現することを要求する関連ルール学習の標準的なアプローチに代わる方法を提供します。

近似頻出アイテムセットマイニングは頻出アイテムセットマイニングの緩和版であり、一部の行のアイテムの一部が0になることを許可します。^[41]

一般化関連ルール階層分類法（概念階層）

定量的関連ルールカテゴリおよび定量的データ

間隔データ関連ルール（例：年齢を5歳刻みの範囲に分割する）

シーケンシャルパターンマイニングは、 シーケンスデータベース内のminsup（最小サポートしきい値）シーケンス以上に共通するサブシーケンスを検出します。minsupはユーザーが設定します。シーケンスは、トランザクションの順序付きリストです。 ^[42]

サブスペースクラスタリングは、高次元データのクラスタリングの特定のタイプであり、多くのバリエーションにおいて、特定のクラスタリングモデルの下方閉包特性に基づいています。^[43]

ACEデータマイニングスイートの一部として出荷されるWarmrは、一次関係ルールの関連ルール学習を可能にします。^[44]

• シーケンスマイニング
• 生産システム（コンピュータサイエンス）
• 学習分類システム
• ルールベースの機械学習

• 相関ルールに関する注釈付き参考文献は、2017 年 2 月 19 日にM. Hahsler によってWayback Machineにアーカイブされました。