アイソレーションフォレスト: ビッグデータにおける最高の異常検出アルゴリズム

Isolation Forest または「iForest」は、わずかなパラメータのみで外れ値を検出できる美しくエレガントなアルゴリズムです。元の論文には最も基本的な数学のみが記載されており、一般の人々にも理解しやすいものでした。この記事では、アルゴリズムとその歴史を要約し、実装コードを共有して、iForest が現在ビッグデータに最適な異常検出アルゴリズムである理由を説明します。

iForest がビッグデータ処理に最適な異常検出アルゴリズムである理由

要約すると、同様のアルゴリズムの中で最高のパフォーマンスを発揮します。 iForest の ROC パフォーマンスとさまざまなデータセットに対する精度は、他のほとんどの異常検出アルゴリズムよりも優れています。私は、Python Outlier Detection パッケージの作成者からベンチマーク データを取得し、Excel で行ごとに緑と赤のグラデーションの条件付き書式を使用しました。このデータセットで最もパフォーマンスが良かったアルゴリズムは濃い緑色で表示され、最もパフォーマンスが悪かったアルゴリズムは濃い赤色で表示されます。

緑は「良い」を意味し、赤は「悪い」を意味します。平均値、中央値、標準偏差の色で示されるように、IForest は多くのデータセットと全体的な観点でリードしていることがわかります。画像出典: 著者。データソース: https://pyod.readthedocs.io/en/latest/benchmark.html

私が計算した平均値、中央値、標準偏差の色からわかるように、IForest は多くのデータセットと全体で優れたパフォーマンスを発揮していることがわかります。 precision@N (N 個の最も重要な指標の精度) のパフォーマンスから判断すると、iForest も同様に優れた結果を生成できます。

スケーラビリティ。 iForest は、実証されたパフォーマンスの点では最速のアルゴリズムです。予想どおり、PCA とヒストグラムベースの外れ値検出 (HBOS) はすべてのデータセットで高速です。

k 最近傍アルゴリズム (KNN) は非常に遅く、データ量が増えるにつれて速度も低下します。

私は、1 億のサンプルと 36 個の機能を持つデータセット上に Isolation Forest を正常に構築しました。これには、クラスター環境で数分かかりました。そして、これは sklearn の KNN アルゴリズムではできないことだと私は思います。

アルゴリズムの要点/概要

私は元の 10 ページの論文を次のように簡潔にまとめました。

• 他のほとんどの外れ値検出 (OD) アルゴリズムは、「正常」データの範囲を確立し、この正常範囲に該当しない個人を異常としてラベル付けしようとします。 iForest は、外れ値の暗黙的な特性（共変量セット上で異常な値を持つ）を利用して、外れ値を直接分離します。
• 既存の方法は、計算コストのため、低次元データまたは小さなデータセットにしか使用できません。一例を挙げると、大規模なデータに sklearn.neighbor.KNeighborsClassifier を使用するでしょうか?
• さらに、iForest では必要な定数はわずかで、メモリ要件も低くなっています。つまり、オーバーヘッドが低いということです。特に、各観測値 n は分離されるため、外部ノードの数は n になります。内部ノードの総数は明らかに n-1 なので、ノードの総数は 2n-1 になります。したがって、必要なメモリが制限され、サンプル数 n とともに直線的に増加する理由を理解できます。

孤立したツリー ノードの定義: T は、子ノードを持たないリーフ ノード、または 2 つの子ノード (Tl、Tr) を持つ検証済みの内部ノードのいずれかです。 iTree は、次のプロセスを再帰的に実行して構築します。つまり、特徴 q と分割値 p をランダムに選択して X を分割し、次のいずれかの状況が発生するまで続けます。(i) ツリーが限界の高さに達する、(ii) すべてのサンプルが自分自身のみを含む外部ノードに分離される、(iii) すべてのデータのすべての特徴が同じ値を持つ。

パスの長さ:サンプル x のパスの長さ h(x) は、iTree のルート ノードからリーフ ノードまでのエッジの数を指します。 E(h(x))は、孤立した木の集合におけるh(x)の平均です。この経路長の平均から、式E(h(x))を使用して異常スコアs(x, n)を取得できます: s(x, n) = 2^[^[− E(h(x)) / c(n)]。基本的に、sとE(h(x))の間には単調な関係があります。 （詳細を知りたい方は、記事末尾の付録をご覧ください。両者の関係を説明した図があります）。 c(n) は任意の静的データセットに対して定数であるため、ここでは説明しません。

ユーザーは、分離されたツリーの数と、単一のツリーをトレーニングするためのサブサンプリング サイズという 2 つの変数を設定するだけです。著者らは、ガウス分布を使用して生成されたデータで実験を行い、平均パス長を迅速に収束させるには、少数のツリーと少数のサブサンプリングのみが必要であることを示しました。

サブサンプリング数（サンプルのサンプリング）を小さくすると、スワンピングとマスキングの問題が解決されます。これら 2 つの問題の原因は、異常検出の問題に対して入力データの量が大きすぎることです。スワンピングとは、「正常」なサンプル ポイントが異常なポイントに囲まれているために誤って「異常」とラベル付けされることを指しますが、マスキングはその逆です。つまり、ツリーの構築に使用されるサンプルに外れ値が多数ある場合、正常なデータ ポイントが非常に異常に見えます。著者らはこの現象の例としてマンモグラフィーデータを使用している。

サブサンプリングの数が少ないと、各サブサンプリングに異なる外れ値のセットが含まれるか、外れ値がまったく含まれなくなるため、分離された各ツリーが一意になります。

iForest は外れ値を識別するために距離や密度の測定に依存しないため、計算コストが安く高速です。これで次の話題に移ります。

線形時間計算量、O(n)。非公式には、実行時間は入力サイズに応じてせいぜい直線的に増加することを意味します。これは非常に良い特性です:

アルゴリズムの歴史

知識のある読者は、優れた新しいアイデアの出現からそれが広く適用されるまでには数十年の遅れが生じる可能性があることを知っているでしょう。たとえば、ロジスティック関数は 1845 年に発見され、1922 年に再発見されました (詳細についてはここを参照)。そして、現在になって初めて、データ サイエンティストによってロジスティック回帰に頻繁に使用されるようになりました。新しいアイデアが生まれてからそれが広く採用されるまでの時間は、ここ数十年で短くなっていますが、それでもまだ比較的長い時間です。 iForest は 2008 年に初めて公開されましたが、実用的な商用アプリケーションが登場したのは 2018 年後半になってからでした。 タイムラインは次のとおりです。

• 2008 年 12 月 - iForest のオリジナル論文発表 (論文)
• 2009 年 7 月 - iForest の作者がコード実装を最後に改訂しました (コード)
• 2018 年 10 月 - h2o チームが iForest の Python および R バージョンを実装しました (コード)
• 2019/01 - PyOD が Python の異常検出ツールキットをリリース (コード、論文)
• 2019 年 8 月 - LinkedIn エンジニアリング チームが iForest の Spark/Scala バージョンをリリースしました (コード、プレス リリース)

コードの実装

この記事はビッグデータに関するものなので、AWS クラスター環境を使用しました。ここでは、スキャフォールディング (ソフトウェア品質保証やテスト コードなど) のコードの大部分は省略されています。 AWS クラスター環境の設定にヘルプが必要な場合は、私の記事「SparkSQL 用の効率的な AWS を構築する方法」を参照してください。

EMR クラスターと Jupyter ノートブック

iForest は 36 個の機能を持つ 750 万行のデータを簡単にすばやく処理でき、計算を完了するのに数分しかかからないことがわかりました。

Python(h2o):

 import h2o # h2o は私のデータセットに対して適切にデータを自動クリーニングしますimport pkg_resources##########################################################################################デバッグ/将来の再現性のためにパッケージとバージョンを印刷します## ...
 dists ## ...  データをロード#####################################################################################################h2o.init() # import pyarrow.parquet as pq # parquet ファイルのロードを許可import s3fs # AWSで作業するためs3s3 = s3fs.S3FileSystem()df = pq.ParquetDataset( 's3a://datascience-us-east-1/anyoung/2_processedData/stack_parquetFiles' , filesystem=s3).read_pandas().to_pandas()#入力データが正しくロードされたか確認; きれいに印刷 .shapeprint( '(' + '; ' . join (map( '{:,.0f}' .format,
                          df.shape)) + ')' )#データをサンプリングする必要がある場合df_samp_5M = df.sample(n=5000000, frac=None, replace = False , weights=None, random_state=123, axis=None)# Pandas DataFrame オブジェクトを h2o DataFrame オブジェクトに変換hf = h2o.H2OFrame(df)#ドロップ 主要な  key columnhf = hf.drop ( ' referenceID' , axis=1) # referenceID は後続のコードでエラーを引き起こします#行を省略できます 最初のパスにnasを使用hf_clean = hf.na_omit()#千単位のコンマ区切りで.shapeをきれいに印刷print( '(' + '; ' . join (map( '{:,.0f}' .format,
                          h2o.estimatorsからH2OIsolationForestEstimatorをインポートします
fullX = [ 'v1' ,
 'v2' 、
 'v3' ]# h2o DataFrame を80/20 の train/testに分割train_hf, valid_hf = hf.split_frame(ratios=[.8], seed=123)# iForest 推定器モデルを指定isolation_model_fullX = H2OIsolationForestEstimator(model_id = "isolation_forest_fullX.hex" , seed = 123)
 isolation_model_fullX_cv = H2OIsolationForestEstimator(model_id = "isolation_forest_fullX_cv.hex" 、 seed = 123) # iForest モデルをトレーニングするisolation_model_fullX.train(training_frame = hf、 x = fullX)
 isolation_model_fullX_cv.train(training_frame = train_hf, x = fullX) # モデルを保存する（保存方法がわからない）  負荷  s3から(まだ権限の問題はありません)modelfile = isolation_model_fullX.download_mojo(path= "~/" , get_genmodel_jar= True )print( "モデルは " + modelfile に保存されました)# モデルを予測predictions_fullX = isolation_model_fullX.predict(hf)# 結果を視覚化predictions_fullX[ "mean_length" ].hist()

iForest を使用してラベル付けされたデータを検証すると、データセット内の正常データの分布、異常データの分布、元のデータセットの分布を比較することで、さらに推論を行うことができます。たとえば、次のように元のデータセット内のさまざまな機能の組み合わせを確認できます。

 N =自由度カウ​​ント()
 df[[ 'v1' , 'v2' , 'id' ]].groupby([ 'v1' , 'v2' ]). count () / N
 df[[ 'v1' , 'v3' , 'id' ]].groupby([ 'v1' , 'v3' ]). count () / N
 ...

そして、iForest を使用して得られた正常/異常データセットと比較します。以下のように表示されます。

 ## ...ブールマスク。出力データセットには、次の行が含まれます。  条件を満たす列値##################################################################################mask = hf_X_y_fullX[ "label" ] == 0hf_X_y_fullX_0 = hf_X_y_fullX[mask,:]
 mask = hf_X_y_fullX[ "label" ] == 1hf_X_y_fullX_1 = hf_X_y_fullX[mask,:]# ... フィルターする 明らかに正常なレコードのみを含めます##############################################################################hf_X_y_fullX_ml7 = hf_X_y_fullX[hf_X_y_fullX[ 'mean_length' ] >= 7]
 hf_X_y_fullX_0_ml7 = hf_X_y_fullX_1[hf_X_y_fullX_0[ '平均長さ' ] >= 7]
 hf_X_y_fullX_1_ml7 = hf_X_y_fullX_3[hf_X_y_fullX_1[ 'mean_length' ] >= 7]#########################################################################################################################変換 簡単にカウントしたり使いやすくするためにPandas DataFrameに変更します。########################################################################################hf_X_y_fullX_ml7_df = h2o.as_list(hf_X_y_fullX_ml7, use_pandas = True )
 hf_X_y_fullX_0_ml7_df = h2o.as_list(hf_X_y_fullX_0_ml7、use_pandas = True )
 hf_X_y_fullX_1_ml7_df = h2o.as_list(hf_X_y_fullX_1_ml7, use_pandas = True )########################################################################## Look at counts by combinations of variable levels for inference#########################################################################hf_X_y_fullX_ml7_df[[ 'v1' , 'v2' , 'id' ]].groupby([ 'v1' , 'v2' ]). count ()
 hf_X_y_fullX_0_ml7_df = h2o.as_list(hf_X_y_fullX_0_ml7, use_pandas = True )...#異常なレコードに対して上記を繰り返します: # ...  明らかに異常なレコードのみを含めます#################################################################################hf_X_y_fullX_ml3 = hf_X_y_fullX[hf_X_y_fullX[ 'mean_length' ] < 3]
 hf_X_y_fullX_0_ml3 = hf_X_y_fullX_1[hf_X_y_fullX_0[ '平均長さ' ] < 3]
 hf_X_y_fullX_1_ml3 = hf_X_y_fullX_3[hf_X_y_fullX_1[ 'mean_length' ] < 3]#######################################################################################################################変換 簡単にカウントしたり使いやすくするためにPandas DataFrameに変更します。########################################################################################hf_X_y_fullX_ml3_df = h2o.as_list(hf_X_y_fullX_ml3, use_pandas = True )
 hf_X_y_fullX_0_ml3_df = h2o.as_list(hf_X_y_fullX_0_ml3、use_pandas = True )
 hf_X_y_fullX_1_ml3_df = h2o.as_list(hf_X_y_fullX_1_ml3、use_pandas = True )

上記のコード全体を実装し、データを Excel にエクスポートすると、次のような累積分布関数がすぐに得られました。

0 とマークされたサンプルを表します。これは異常である可能性が高いと考えられます。

参考文献

• FT Liu、KM Ting、Z.-H. Zhou。「Isolation Forests」。第 8 回 IEEE 国際データマイニング会議 (ICDM' 08)、ピサ、イタリア、2008 年、pp.413-422。[code] この論文は、IEEE ICDM'08 の Best Theory/Algorithm Paper Award で第 2 位を獲得しました。
• Zhao, Y., Nasrullah, Z. および Li, Z., 2019.「PyOD: スケーラブルな異常検出のための Python ツールボックス」。機械学習研究ジャーナル (JMLR)、20(96)、pp.1-7。

この記事はLeiphone.comから転載したものです。転載する場合は、Leiphone.com公式サイトにアクセスして許可を申請してください。