シーケンシャル例外テクニックとは？仕組みと4つの主要概念を解説

シーケンシャル例外テクニックの概要

シーケンシャル例外テクニック（Sequential Exception Technique：逐次例外法）は、人間が「同種とみなされる一連のオブジェクトの中から異常なものを見分ける」プロセスを模倣した外れ値検出の手法です。データに内在する冗長性（暗黙的冗長性）を活かして異常を検出できる点が大きな特徴です。

サブセット列の構築

n 個のオブジェクトからなるデータセット D が与えられると、まず 2 ≤ m ≤ n を満たすような部分集合の列 {D₁, D₂, ..., D_m} を構築します。各部分集合は次の包含関係を満たします。

$$\mathrm{D_{j−1}\subset D_{j}\:\:where\: D_{j}\subseteq D}$$

続いて、系列内の各部分集合間で非類似度（dissimilarity）を評価していきます。この手法を理解するうえで重要になるのが、以下の4つの概念です。

主要な構成概念

1. 例外集合（Exception Set）

逸脱や外れ値の集合を指します。「そのオブジェクト群を取り除くことで、残りの集合における非類似度が最も大きく減少する」という条件を満たす最小の部分集合として定義されます。

2. 非類似度関数（Dissimilarity Function）

オブジェクト間の計量的距離（メトリック距離）を必要としない関数です。与えられたオブジェクトの集合に対して、オブジェクト同士が似ているほど低い値を返し、非類似性が高いほど高い値を返します。

部分集合の非類似度は、系列内で直前の部分集合に基づいて漸増的に計算されます。たとえば n 個の数値からなる部分集合 {x₁, ..., x_n} の場合、集合内の数値の分散を非類似度関数として利用できます。

$$\mathrm{\frac{1}{n}\displaystyle\sum\limits_{i=1}^n (x_{i}-x^{'})^2}$$

ここで x^' は集合内の n 個の数値の平均値です。

文字列を扱う場合には、それまでに観測されたすべてのパターンをカバーできるパターン文字列（ワイルドカード文字などを含む）を非類似度関数として採用できます。D_j−1 内の文字列をカバーしていたパターンが、D_j に新しく現れた文字列をカバーできなくなったとき、非類似度は増加します。

3. 基数関数（Cardinality Function）

一般に、与えられた集合に含まれる複数のオブジェクトの個数を数える関数です。

4. スムージング係数（Smoothing Factor）

系列内の各部分集合に対して計算される関数です。元のオブジェクト集合からその部分集合を取り除いたときに、非類似度がどれだけ減少するかを評価します。この値は集合の基数（要素数）によって重み付けされ、スムージング係数が最も大きくなる部分集合が例外集合と判定されます。

計算量とアルゴリズムのポイント

例外集合を厳密に求める問題は NP 困難（NP-hard）、つまり計算量の面で扱いにくい問題になり得ます。そこで実用的には、計算的に実行可能な逐次方式が採用されます。このアプローチであれば線形時間アルゴリズムで処理を実行できます。

具体的には、現在の部分集合とその補集合とを比較して非類似度を評価するのではなく、解析対象となる一連の部分集合をあらかじめ選択します。そして各部分集合について、系列内で直前の部分集合と比較した相対的な非類似度の差分を判定していきます。この設計により、大規模データでも効率的に外れ値の検出が可能になります。