技術的概要：教師なし外れ値検出のためのランダム化 PCA フォレスト

問題定義

外れ値検出は、データマイニングおよび機械学習における基本的なタスクであり、侵入検知、故障診断、不正検出などの応用において極めて重要である。新規アルゴリズムの氾濫にもかかわらず、包括的な評価によれば、K 近傍法（KNN）や局所外れ値因子（LOF）といった古典的手法が依然として最先端であることが示されている。これらの手法は、正常データと異常データの間の不正確な境界やノイズの存在といった課題を効果的に処理する一方で、正確な最近傍探索の必要性に起因する高い計算複雑性の問題に悩まされている。Isolation Forest（iForest）のような木ベースの手法は効率性を提供するが、ランダムな特徴量選択に依存しており、高次元データの背後にある構造を常に効果的に捉えるとは限らない。計算効率と頑健性のバランスを取りつつ、次元削減を活用しながらも、大域的および局所的な外れ値の両方を検出する能力を犠牲にしない手法が必要とされている。

手法

著者は、ランダム化主成分分析（RPCA）フォレストに基づく新規の教師なし外れ値検出手法を提案する。このアプローチは、元々近似 K 近傍（KNN）探索用に設計された RPCA フォレストを、フォレストの内在的な性質から特定の外れ値スコアを導出することで、外れ値検出に適応させたものである。

中核的コンポーネント

1. RPCA フォレストの構築:

   • この手法は、木のアンサンブルを構築する。iForest がランダムに特徴量を選択するのとは異なり、RPCA フォレストは各ノードでランダム化 PCA（Halko ら、2011）を利用する。
   • 根ノードおよび後続のノードにおいて、データ点は少数の主成分（$p$）を用いて低次元部分空間へ射影される。これにより、元の特性空間の情報価値を保持しつつ次元を削減する。
   • 分割基準: ランダムな切断の代わりに、アルゴリズムは各主成分に対して、平均を中心としたラプラス分布から分割点をサンプリングする。データ点は、$p$ 個の成分全体での多数決に基づき、左または右の子ノードに割り当てられる。
   • 停止基準: 木の成長は、葉ノードに含まれる点数が事前に定義された近傍サイズ（$k$）以下になるまで継続される。

2. 外れ値スコアの定式化:
   提案手法は、クエリ点 $q$ に対して、2 つの異なる基準を組み合わせることで外れ値スコア（$RPCAForestScore$）を定義する。

   • 深さベースの外れ値度（$P(q)$）: 外れ値は木の中で早期に孤立し（浅い深さ）、検出されやすいという観察に基づいている。これは、フォレスト全体にわたって $q$ を含む葉ノードの正規化された逆深さとして計算される。
   • 距離ベースの外れ値度（$\mu_{dist}(q)$）: 元の特性空間において、クエリ点 $q$ と同じ葉ノード内の他のすべての点との間の平均ユークリッド距離として計算される。
   • 最終スコア: 最終スコアは、これら 2 つの成分の積である。
     $$RPCAForestScore(q) = P(q) \times \mu_{dist}(q)$$
     この組み合わせにより、たとえ外れ値が射影により葉内で正常点とグループ化された場合でも、元の空間におけるクラスタ中心からの大きな距離が高異常スコアをもたらすことが保証される。

3. 分類:
   外れ値の閾値は、外れ値の期待される割合を表す汚染パラメータ（$\alpha$）を用いて決定される。スコア分布の $(1-\alpha)$ 分位点を超えるスコアを持つ点は、外れ値としてラベル付けされる。

主要な貢献

• 新規統合: 本論文は、近似最近傍探索と異常検出の間のギャップを埋めるものとして、RPCA フォレストを教師なし外れ値検出に特化して初めて適用した。
• ハイブリッド・スコアリング機構: 構造的な孤立深さ（iForest に類似）と元の特性空間における局所密度/距離（KNN/LOF に類似）の両方を活用する複合的な外れ値スコアを提案し、単一の指標の使用に起因する限界を克服することを目指している。
• ランダム化 PCA による効率性: ランダム化 SVD を採用することで、特に高次元データにおいて高い計算効率を達成する。その複雑性は、完全なデータ次元数ではなく主成分の数に依存する。
• 頑健性: この手法はハイパーパラメータの調整に対して頑健に設計されており、木の数、主成分の数（$p$）、葉のサイズ（$k$）の選択のみを必要とする。

実験結果

著者は、標準的なベンチマークリポジトリから取得した22 の多様なデータセットを用いて手法を評価し、KNN、KNNW、LOF、SLOF、ODIN、DAO、iForest といった古典的および最先端の手法と比較した。性能は、受信者動作特性曲線下面積（AUC）を用いて測定された。

• 性能: RPCA フォレストは、多くのデータセットで優位または第 2 位の性能を示し、他のデータセットでも競争力のある結果を残した。ランダムな特徴量選択を用いる iForest が苦戦した高次元データセットにおいて、特に優れた性能を示した。
• 頑健性: この手法は、主成分の数（$p=1$ および $p=5$）の 2 つの設定のみを使用して競争力のある性能を維持したが、競合する手法は 100 種類の異なるハイパーパラメータ構成でテストされた。これは、提案手法がハイパーパラメータ調整に対して敏感でないことを示唆している。
• アブレーション研究: 深さベース成分と距離ベース成分を分離した実験により、組み合わせスコアが深さベース成分を大幅に上回り、一般的に距離ベース成分単独と同等かそれ以上の性能を示すことが明らかになった。
• 効率性: iForest が依然として最速の手法であったが、RPCA フォレストはデータセットサイズが増加するにつれて KNN ベースの手法よりも著しく優れたスケーラビリティを示し、ビッグデータに適した効率的な実行時間を維持した。
• 観察された限界: 特定のデータセット（ALOI、InternetAds、Annthyroid、Wilt など）において、この手法は低い性能を示した。著者はこれを以下に起因すると帰属している。
  • 少数の主成分（$p=1, 5$）では外れ値を孤立させるのに不十分であった高次元性（InternetAds）。
  • 外れ値が正常点と非常に類似しており、選択された $p$ が提供できる以上の情報を必要としたこと（Annthyroid、Wilt）。
  • 特定の特性抽出を伴うデータセットにおける局所的対大域的な外れ値の性質（ALOI）であり、この場合、局所構造手法（LOF）が大域的射影アプローチを上回った。

意義と主張

本論文は、RPCA フォレストが教師なし外れ値検出のための頑健かつ計算効率的な代替手段を提供すると主張している。その意義は、以下の点にある。

1. 効率性と精度のバランス: 検索をブラックボックスとして扱うのではなく、PCA 射影を介して木の内部構造を利用する「ホワイトボックス」アプローチによる近似近傍探索を提供する。
2. 優れた汎化性能: 多くの新規手法が特定の事例でのみ優れているという問題に対処し、網羅的なハイパーパラメータ最適化を必要とせずに広範なデータセットで競争力のある性能を発揮する。
3. 大域的および局所的な外れ値の両方の検出: 理論的には、この手法は木における早期孤立（大域的な外れ値）と深いノードにおける距離指標（局所的な外れ値）の両方を検出するように設計されているが、著者はクラスター化された異常に対する限界を認めている。

著者は結論として、この手法がすべての外れ値タイプ（特にクラスター化された異常）に対する万能な解決策ではないものの、木ベース手法の計算速度と距離ベース手法の精度との間の好ましいトレードオフを提供し、汎用的な外れ値検出のための強力な選択肢であると述べている。