Aprioriアルゴリズムの複雑さは何ですか？

Aprioriアルゴリズムの計算の複雑さは、次の要因によって影響を受ける可能性があります-

サポートしきい値 −サポートしきい値を下げると、アイテムセットが高くなり、頻繁に表示されます。これは、より高い候補アイテムセットを作成してカウントする必要があるため、アルゴリズムの計算の複雑さに悪影響を及ぼします。

頻繁なアイテムセットの最大サイズも、サポートのしきい値を低くして改善することに影響します。頻繁なアイテムセットの最大サイズが向上するにつれて、データセットに対してより多くのパスを作成するためのアルゴリズムが必要になります。

アイテム数（ディメンション） −いくつかのアイテムの数が増えると、アイテムのサポート数を節約するためにより多くのスペースが必要になります。データの次元とともに複数の頻繁なアイテムも増加する場合、アルゴリズムによって生成される候補アイテムセットの数が多いため、計算値とI/O値が増加します。

トランザクション数 − Aprioriにより、アルゴリズムはデータセットに対して繰り返しパスを作成し、トランザクション数が増えると実行時間が向上します。

平均トランザクション幅 −密なデータセットの場合、平均トランザクション幅が大きくなる可能性があります。これは、頻繁なアイテムセットの最大サイズが平均トランザクション幅の増加に伴って増加するなど、2つの方法でAprioriアルゴリズムの複雑さに影響します。トランザクション幅が増加し、より高いアイテムセットがトランザクションに含まれます。これにより、サポートカウント中に実装される複数のハッシュツリートラバーサルが増加します。

頻繁なlアイテムセットの生成 −トランザクションごとに、トランザクションに存在する各アイテムのサポートカウントを更新する必要があります。 wが平均トランザクション幅であることを考慮すると、この操作にはO（Nw）時間が必要でした。ここで、Nはトランザクションの総数です。

候補の生成 −候補のkアイテムセットを作成できます。頻繁な（k-1）アイテムセットのペアを組み合わせて、共通の最小k-2アイテムがあるかどうかを判断します。各結合操作は、最大でk-2の等式比較に必要です。最良のシナリオでは、各結合ステップにより、実行可能な候補kアイテムセットが作成されます。

最悪のシナリオでは、アルゴリズムは、前の反復で見つかった頻繁な（k-1）アイテムセットの各ペアを組み合わせる必要があります。したがって、頻繁なアイテムセットをマージするための完全なコストは

$$ \ mathrm {\ displaystyle \ sum \ Limits_ {k =2} ^ w \ :( k-2）| C_ {k} | <\：Cost \：of \：merging \：<\ displaystyle \ sum \ Limits_ {k =2} ^ w \ :( k-2）| F_ {k} -1 | ^ 2} $$

候補アイテムセットを保存するために、候補生成中にハッシュツリーも生成されます。ツリーの最大深度はkであるため、ハッシュツリーに候補アイテムセットを入力するためのコストはO（$ \ mathrm {\ displaystyle \ sum \ Limits_ {k =2} ^ w \：k | C_ {k} | } $）。

候補の剪定中に、各候補kアイテムセットのk-2サブセットが頻繁にあることを確認する必要があります。ハッシュツリーで候補を表示するためのコストはO（k）であるため、候補の剪定ステップにはO（$ \ mathrm {\ displaystyle \ sum \ Limits_ {k =2} ^ w \：k | C_ {k}）が必要でした。 |} $）時間。