ネガティブパターンをマイニングするためのテクニックとは？基本手法と計算上の課題

ネガティブパターンマイニングの基本的な手法

頻出しないパターン（ネガティブパターン）をマイニングするために最初に考案された手法では、各項目を対称的な二値変数として扱います。トランザクションデータに負の項目（ネガティブアイテム）を追加することで、データを二値化することが可能です。これは、元のデータを正と負の両方の項目を含むトランザクションへと変換する操作に相当します。こうして拡張されたトランザクションに対して、Aprioriなどの既存の頻出項目集合生成アルゴリズムを適用すれば、一部の負の項目集合（ネガティブアイテムセット）を導き出すことができます。

この手法が有効に機能する条件

ただし、このアプローチが実用的なのは、ごく少数の変数だけを対称的な二値変数として扱う場合、すなわち、わずかな項目の否定のみを含む負のパターンを対象とする場合に限られます。すべての項目を対称的な二値変数として扱おうとすると、以下の理由により計算が極めて困難になります。

1. 項目数の倍増による探索空間の爆発

各項目に対応する負の項目を追加すると、項目の総数は2倍になります。その結果、探索すべき項目集合の格子構造は、元のデータセットの項目数を d とすると、2^d どころではない、はるかに大きなサイズへと膨れ上がります。

2. 支持度ベースの枝刈りの非効率化

負の項目を追加すると、支持度に基づく枝刈りはもはや効率的に機能しません。任意の変数 x について、x または x’（否定）のいずれかの支持度は必ず50%以上になるためです。したがって、支持度の閾値を50%という高い水準に設定したとしても、半数の項目が頻出項目となってしまいます。

閾値をさらに低く設定した場合には、より多くの項目、さらにはそれらを含む項目集合まで頻出と判定されます。Aprioriが採用している支持度ベースの枝刈り手法は、大多数の項目集合の支持度が低い場合にこそ効果を発揮するため、この状況下では頻出項目集合の数が指数関数的に増加してしまいます。

3. トランザクション幅の増大

負の項目を追加すると、各トランザクションの幅（長さ）も増大します。元のデータセットに d 個の項目が存在すると仮定しましょう。マーケットバスケット分析のような疎なデータセットでは、各トランザクションの幅は通常 d よりもはるかに小さいのが普通です。

そのため、最大トランザクション幅 w_max によって制約される頻出項目集合の最大サイズも、相対的に小さくなります。ところが、負の項目を含めると、ある項目はトランザクション内に「存在する」か「存在しない」かのどちらか一方しかあり得ないため、トランザクションの幅は d まで増加します。

最大トランザクション幅が w_max から d へと拡大することで、生成される頻出項目集合の数は急激に増加します。その結果、既存のアルゴリズムの多くは、このような大規模なデータセットに適用すると破綻してしまう傾向があります。

計算コストの問題と代替アプローチ

前述の総当たり（ブルートフォース）的なアプローチは、膨大な数の正と負のパターンについて支持度を算出する必要があるため、計算コストが非常に高額になります。そこで、データセットに負の項目を追加する代わりに、対応する正の項目の支持度に基づいて負の項目集合の支持度を導出するという、別のアプローチが検討されています。