(57)【要約】  アウトライア検出が行われるデータセットのデータ記録の基準セットのそれぞれのサンプルに関するランダムカットツリーが生成される。特定のランダムカットツリーを構築するために、反復分割技法が使用され、この技法では、その値域に基づいて、データ記録の所定セットが分割される属性が選択される。新しく受信されたストリームのデータ記録に関して、ランダムカットツリーを必ずしも変更することなく、特定のランダムカットツリーにあるデータ記録を表すノードの潜在的な挿入位置に少なくとも部分的に基づき、アウトライアスコアが決定される。【選択図】図１
2019505912.tif 000002
【特許請求の範囲】
【請求項１】
プロバイダネットワークに実装されるネットワークアクセス可能な分析サービスの１つ以上のコンピューティングデバイスを備えるシステムであって、前記１つ以上のコンピューティングデバイスは、
データセットのデータ記録の基準セットのそれぞれのサンプルに対応する１つ以上のランダムカットツリーを生成することであって、前記データ記録の個々の１つは複数の属性の値を備え、特定のサンプルに対応する特定のランダムカットツリーの生成は、
前記特定の属性の値域に少なくとも部分的に基づいて前記複数の属性のうちの１つの特定の属性を選択することと、
前記特定の属性に選択された分割値で前記特定のサンプルの少なくとも一部分を分割することと、
のうちの１つ以上の反復を備える、前記生成することと、
前記基準セットに含まれていない特定のデータ記録を取得することに応じて、前記特定のデータ記録のために計算されたアウトライアスコアを記憶することであって、前記アウトライアスコアの前記計算は、前記特定のランダムカットツリーに関する前記特定のデータ記録に対して識別された潜在的な挿入位置に少なくとも部分的に基づく、前記記憶することと、
を行うように構成される、システム。
【請求項２】
前記データセットの前記データ記録は観測記録を備え、前記１つ以上のコンピューティングデバイスは、
ストリーミングデータソースの前記観測記録にアウトライア検出を行うために、プログラマチックインターフェースを介してクライアントから要求を受信することであって、アウトライア検出を行う前記要求は選択されたクエリ言語で定式化され、前記要求は時間窓を示すパラメータを示し、前記時間窓に関して前記アウトライア検出が行われることになる、前記受信することと、
前記ストリーミングデータソースの観測記録の基準セットを収集することと、
確率的ストリームサンプル更新アルゴリズムに従って、前記特定のランダムカットツリーに対応する前記サンプルが前記特定の観測記録を含むという判定に応じて、前記特定の観測記録を表すノードを前記特定のランダムカットツリーに挿入することと、
前記アウトライアスコアが結果報告基準を満たすという判定に応じて、前記アウトライアスコアの指標を前記クライアントに提供することとを行うように構成される、請求項１に記載のシステム。
【請求項３】
前記特定の観測記録を表す前記ノードを前記特定のランダムカットツリーに挿入するために、前記１つ以上のコンピューティングデバイスは、
（ａ）前記特定のランダムカットツリーのルートノードから開始する走査中に前記特定のランダムカットツリーの特定のノードに到達することであって、前記特定のノードは前記複数の属性の第１の属性に関して行われる以前のランダム分割計算に対応する属性値の境界ボックスを表す、前記到達することと、（ｂ）前記特定の観測記録が前記境界ボックスの範囲外にあると判定することに応じて、
前記境界ボックスに表される前記複数の属性の選択された属性に関してランダム分割計算を行うことと、
前記ランダム分割計算の結果に少なくとも部分的に基づいて、（ａ）前記特定の観測記録を表すノードが前記特定のノードの新しい子ノードとして追加されるか、または（ｂ）前記特定のノードの異なる子ノードを含む経路に沿って前記特定のランダムカットツリーの走査を継続するかどうかを決定するように構成される、請求項２に記載のシステム。
【請求項４】
前記１つ以上のコンピューティングデバイスは、
前記特定のランダムカットツリーに対応する前記サンプルが前記特定の観測記録を含むという前記判定の後に、
異なる観測記録を表す葉ノードを前記特定のランダムカットツリーから削除することと、
前記葉ノードの前記親ノードを前記葉ノードの兄弟ノードに置換することと、
前記兄弟ノードの新しい位置と、前記特定のランダムカットツリーのルートノードとの間の経路上にある１つ以上のノードのそれぞれの境界ボックスを調整することと、
を行うように構成される、請求項２または３に記載のシステム。
【請求項５】
前記１つ以上のコンピューティングデバイスは
（ａ）前記潜在的な挿入位置に対応するスパース性指標、（ｂ）前記潜在的な挿入位置及び前記特定のランダムカットツリーの１つ以上の他のノードに関して計算されたそれぞれの距離指標、または（ｃ）前記潜在的な挿入位置に対応する置換指標のうちの１つ以上に少なくとも部分的に基づいて前記アウトライアスコアを計算するように構成される、請求項２〜４のいずれか１項に記載のシステム。
【請求項６】
ストリームのデータ記録にアウトライア検出を行うことを決定することであって、前記データ記録の個々の１つは複数の属性の値を備える、前記決定することと、
前記ストリームのデータ記録の基準セットのそれぞれのサンプルに対応する１つ以上のランダムカットツリーを生成することであって、特定のサンプルに対応する特定のランダムカットツリーの生成は、
前記特定の属性の値域に少なくとも部分的に基づいて前記複数の属性のうちの１つの特定の属性を選択することと、
前記特定の属性に選択された分割値で前記特定のサンプルの少なくとも一部を分割することと、
のうちの１つ以上の反復を備える、前記生成することと、
前記基準セットに含まれていない特定のデータ記録を取得することに応じて、
前記特定のデータ記録のために計算されたアウトライアスコアを記憶することであって、前記アウトライアスコアは前記特定のランダムカットツリーに関する前記特定のデータ記録に対して識別された潜在的な挿入位置に少なくとも部分的に基づき、前記アウトライアスコアは前記特定のランダムカットツリーを変更することなく計算される、前記記憶することと、
を１つ以上のコンピューティングデバイスによって行うことを備える、方法。
【請求項７】
（ａ）前記潜在的な挿入位置に対応するスパース性指標、（ｂ）前記潜在的な挿入位置及び前記特定のランダムカットツリーの１つ以上のノードに関して計算されたそれぞれの距離指標、または（ｃ）前記潜在的な挿入位置に対応する置換指標、のうちの１つ以上に少なくとも部分的に基づいて前記アウトライアスコアを計算すること、
を前記１つ以上のコンピューティングデバイスによって行うことをさらに備える、請求項６に記載の方法。
【請求項８】
前記基準セットに含まれていない第２のデータ記録を取得することに応じて、
前記特定のランダムカットツリーに関する前記第２のデータ記録に対して識別された潜在的な挿入位置に少なくとも部分的に基づいて、前記第２のデータ記録に対応する第２のアウトライアスコアを計算することと、
サンプル更新アルゴリズムに従って、前記サンプル更新アルゴリズムは、（ａ）ランダムサンプル更新アルゴリズムまたは（ｂ）加重サンプル更新アルゴリズムのうちの１つ以上を備え、
前記第２のデータ記録を前記特定のランダムカットツリーに挿入することと、
選択されたデータ記録を前記特定のランダムカットツリーから削除することと、
を前記１つ以上のコンピューティングデバイスによって行うことをさらに備える、請求項６または７のいずれかに記載の方法。
【請求項９】
前記特定のランダムカットツリー内で第２のデータ記録の前記潜在的な挿入位置が閾値より深い深さにあるという判定に少なくとも部分的に基づいて、前記特定のランダムカットツリーを前記閾値より深い深さまで走査することなく、第２のデータ記録に第２のアウトライアスコアを割り当てること、
を前記１つ以上のコンピューティングデバイスによって行うことをさらに備える、請求項６〜８のいずれか１項に記載の方法。
【請求項１０】
第２のストリームのデータ記録にアウトライア検出を行うことを決定することであって、前記第２のストリームの前記データ記録の個々の１つは第２の複数の属性の値を備える、前記決定することと、
前記第２のストリームのデータ記録の第２の基準セットに対応する１つ以上のランダムカットツリーを生成する前に、前記第２の基準セットの少なくともサブセットを事前処理することであって、前記事前処理は、（ａ）前記第２の複数の属性の１つ以上の属性の未処理の値を正規化すること、（ｂ）前記第２の基準セットの複数のデータ記録の内容を集計することによって導出した記録を生成すること、（ｃ）選択されたスライド窓サイズを伴うシングリング技法を使用して、単一の属性から複数の次元のデータを生成すること、または（ｄ）変換関数を前記第２の複数の属性の特定の非数値属性の値に適用し、導出された数値を取得すること、のうちの１つ以上を備える、前記事前処理することと、
を前記１つ以上のコンピュータデバイスによって行うことをさらに備える、請求項６〜９のいずれか１項に記載の方法。
【請求項１１】
知識ベース入力に少なくとも部分的に基づいて、（ａ）前記基準セットのサイズ、（ｂ）前記特定のサンプルのサイズ、（ｃ）生成すべきランダムカットツリーの数、（ｄ）前記アウトライアスコアを割り当てるために使用される距離パラメータ（ｅ）前記アウトライアスコアを割り当てるために使用されるスパース性パラメータ、（ｆ）他の属性に対する前記特定の属性に割り当てる加重であって、前記アウトライアスコアは前記加重に少なくとも部分的に基づく、前記加重、（ｇ）前記特定のランダムカットツリーを更新するために使用される時間置換パラメータ、または（ｈ）アウトライアスコアに関する通知閾値であって、前記通知閾値は前記アウトライアスコアに関する通知を１つ以上の宛先に提供すべきかどうかを判定するために使用される、前記通知閾値、のうちの１つ以上を決定すること、
を前記１つ以上のコンピューティングデバイスによって行うことをさらに備える、請求項６〜１０のいずれか１項に記載の方法。
【請求項１２】
（ａ）前記基準セットのサイズ、（ｂ）前記特定のサンプルのサイズ、（ｃ）生成すべきランダムカットツリーの数、（ｄ）前記アウトライアスコアを割り当てるために使用される距離パラメータ（ｅ）前記アウトライアスコアを割り当てるために使用されるスパース性パラメータ、（ｆ）他の属性に対する前記特定の属性に割り当てる加重であって、前記アウトライアスコアは前記加重に少なくとも部分的に基づく、前記加重、（ｇ）前記特定のランダムカットツリーを更新するために使用される時間置換パラメータ、または（ｈ）アウトライアスコアに関する通知閾値であって、前記通知閾値は前記アウトライアスコアに関する通知を１つ以上の宛先に提供すべきかどうかを判定するために使用される、前記通知閾値、のうちの１つ以上の指標をクライアントからプログラマチックインターフェースを介して受信すること
を前記１つ以上のコンピューティングデバイスによって行うことをさらに備える、請求項６〜１１のいずれか１項に記載の方法。
【請求項１３】
前記１つ以上のコンピューティングデバイスは、バッチモード動作及びリアルタイムストリーミング動作を実施する機械学習サービスの複数の実行プラットフォームを含み、
永続的なレポジトリで前記ストリームの前記データ記録の少なくともサブセットを記憶することと、
前記ストリームの少なくとも１つのデータ記録を受信する前に、前記ストリームの１つ以上のデータ記録のそれぞれのアウトライアスコアをクライアントに提供することと、
前記それぞれのアウトライアスコアが提供された後に追加のデータ記録の受信を無効にするために前記ストリームを閉鎖することと、
データ記録の前記サブセットにバッチモードアウトライア検出動作を行うことであって、前記バッチモードアウトライア検出動作は前記それぞれのアウトライアスコアが前記クライアントに提供された後に少なくとも１つのランダムカットツリーを更新することを備える、検出動作を行うことと、
を前記１つ以上のコンピューティングデバイスによって行うことをさらに備える、請求項６〜１２のいずれか１項に記載の方法。
【請求項１４】
前記アウトライアスコアが閾値基準を満たすと判定することに応じて、前記アウトライアスコアを示す通知を、プログラマチックインターフェースを介してクライアントに提供すること、
を前記１つ以上のコンピューティングデバイスによって行うことをさらに備える、請求項６〜１３のいずれか１項に記載の方法。
【請求項１５】
前記１つ以上のコンピューティングデバイスの少なくとも１つのコンピューティングデバイスは、（ａ）電子商取引ウェブサイトまたは（ｂ）プロバイダネットワークのうちの１つ以上に関連する監視ツールのサブコンポーネントを備える、請求項６〜１４のいずれか１項に記載の方法。
【発明の詳細な説明】
【背景技術】
【０００１】
データストレージのコストが年々減少し、コンピューティングインフラストラクチャの様々な要素の相互接続機能が向上するにつれ、多様なタイプのアプリケーションに関するますます多くのデータが潜在的に収集されて分析される可能性がある。航空機エンジン、自動車、健康管理デバイスまたは複合機械内の様々な場所に埋め込まれたセンサから収集されたデータの分析は、予防保全、事前の健康関連アラート、効率性向上及びコスト削減などの多数の目的のために使用され得る。オンライン小売業者のウェブサイトから収集されたストリーミングデータは、異なる倉庫場所に格納する必要がある様々な製品の量に関する決定など、より賢明な決定を行うために使用することができる。マシンサーバに関して収集されたデータはさらに、サーバの不具合を防止するために分析されてよい。
【０００２】
ストリーミングデータ量の増加は商用ハードウェアの使用の増加と同時に（いくつかの場合では、恐らく商用ハードウェアの使用の増加により）発生した。商用ハードウェアに対する仮想技術の出現により、多数のタイプのアプリケーションに対して大規模なコンピューティングリソースを管理できるという利点が得られ、これにより、複数のカスタマは、様々なコンピューティングリソースを効率的かつ安全に共有することができる。例えば、仮想技術により、複数のユーザ間で単一の物理的なコンピューティングマシンを共有することが可能となり得、これは、単一の物理的なコンピューティングマシンによってホストされる１つ以上の仮想マシンを各ユーザに提供することによって行われる。各仮想マシンは、別個の論理コンピューティングシステムとして作動するソフトウェアシミュレーションとみなすことができ、これは、ユーザが所与のハードウェアコンピューティングリソースの唯一の操作者及び管理者であるという錯覚をユーザに与えるものであり、同時に、様々な仮想マシン間のアプリケーションの分離及びセキュリティも提供する。いくつかの大規模な組織は、コンピューティングプラットフォームに加え、仮想技術を使用して構築された様々なタイプのストレージサービスをさらに提供する。係るストレージサービスを使用すると、所望の可用性レベル及び永続性レベルを優れた費用対効果で維持しながら、大量のストリーミングデータを記憶することができる。所与の物理的なストレージデバイスは、多数の異なるサービスカスタマのデータ記録を保持するために使用される可能性がある。
【０００３】
作成可能なストリーミングデータの量が増加するにつれ、ストリーミングデータと協働する分析ツールの必要性も増加している。例えば、一部のセキュリティ関連アプリケーションまたは健康関連アプリケーションでは、データのアウトライア（つまり、例外的なデータ記録またはデータパターン）を非常に高速に識別する機能が重要となり得る。残念ながら、係るタスクを長年開発してきた機械学習及び統計アルゴリズムのうちの多くは、主に静的データセットを考慮に入れて設計されてきた。その結果、大量のストリーム内にある異常データを効率的に識別することは、依然として困難な課題である。
【図面の簡単な説明】
【０００４】
【図１】少なくともいくつかの実施形態による、ストリーミングデータ記録にアウトライア検出を行い得るシステム環境例を例示する。
【図２】少なくともいくつかの実施形態による、一対のアウトライアを有する２属性観測記録のストリーム及びアウトライア検出アルゴリズムの高レベルな概要の簡単な例を提供する。
【図３】少なくともいくつかの実施形態による、いくつかの観測記録のアウトライア状態を結果的に変化させ得る、ストリーミング観測記録属性値の分布の経時的なシフトの一例を示す。
【図４】少なくともいくつかの実施形態による、ランダムカットツリーを使用してデータセットからアウトライアを識別する技法の初期ステップを集合的に示す。
【図５】少なくともいくつかの実施形態による、ランダムカットツリーを使用してデータセットからアウトライアを識別する技法の初期ステップを集合的に示す。
【図６】少なくともいくつかの実施形態による、ランダムカットツリー内の観測記録を表すノードが観測記録のアウトライア状態の指標として使用され得るツリー深さのシナリオ例を示す。
【図７】少なくともいくつかの実施形態による、ストリーミングデータセットに対して確率的に作成及び更新され得るランダムカットツリーのセット例を示す。
【図８】少なくともいくつかの実施形態による、ストリーミングデータセット内のアウトライアを識別するための距離及びスパース性指標の使用を示す。
【図９】少なくともいくつかの実施形態による、ストリーミングデータのアウトライア検出アルゴリズムで利用され得る範囲ベースの分割技法を示す。
【図１０】少なくともいくつかの実施形態による、ツリーに使用されるサンプルに新しい観測記録を挿入した結果として潜在的に生成され得るランダムカットツリー例を示す。
【図１１】少なくともいくつかの実施形態による、ツリーに使用されるサンプルから観測記録を削除した結果として生成されるランダムカットツリーへの変更例を示す。
【図１２】少なくとも一部の実施形態による、ストリーミングデータ及び静的データセットの分析を行い得る機械学習サービスを示す。
【図１３】少なくともいくつかの実施形態による、ストリーミング観測記録のためのアウトライア検出アルゴリズムを実施するために実行され得る動作の態様を示す。
【図１４】少なくともいくつかの実施形態で使用され得るコンピューティングデバイスの例を示すブロック図である。
【発明を実施するための形態】
【０００５】
実施形態が、いくつかの実施形態及び例示の図面の例として本明細書に記載されている一方で、当業者は、実施形態が記載される実施形態または図面に限定されないことを認識するであろう。図面及び詳細な説明は、開示された特定の形態に実施形態を限定するものではないことが理解されるべきであり、それとは反対に、その意図は、添付の特許請求の範囲によって定められる趣旨及び範囲にある全ての修正、均等物及び代替物を包含するものである。本明細書で使用する見出しは、構成上の目的のためだけにあり、説明または特許請求の範囲を制限するために使用されることを意味しない。本出願全体に使用される場合、「ｍａｙ」という語は、必須の意味（つまり、「しなければならない」という意味）よりもむしろ、許容的な意味（つまり、それを行う可能性があるという意味）で使用される。同様に、「ｉｎｃｌｕｄｅ」、「ｉｎｃｌｕｄｉｎｇ」及び「ｉｎｃｌｕｄｅｓ」という語は、「を含むがこれらに限定されない」を意味する。特許請求の範囲で使用される場合、「ｏｒ」という用語は包含的なｏｒとして使用され、排他的なｏｒとしては使用されない。例えば、「少なくともｘ、ｙまたはｚのうちの１つ」という句は、ｘ、ｙ及びｚのうちのいずれか１つならびにそれらの任意の組み合わせを意味する。
【０００６】
ストリーミングデータセット内のアウトライアまたは異常な記録を検出するための方法及び装置の様々な実施形態を説明する。本明細書で使用する「ストリーム」または「ストリーミングデータセット」という用語は、１つ以上のデータプロデューサによって生成され、０以上のデータ消費者によってアクセスされ得る一連の記録を指し、各記録は、１つ以上の属性の値を表す一連のバイト数とみなされる。ストリームの記録は、本明細書の観測記録、観測値、ポイントまたはデータ記録とも呼ばれることがあり、データプロデューサは、ストリーミングデータソースと呼ばれることがある。ストリーム管理及び分析サービス（ＳＭＡＳ）は、プログラマチックインターフェース（例えば、アプリケーションプログラミングインターフェース（ＡＰＩ）、ウェブページもしくはウェブサイト、グラフィカルユーザインターフェースまたはコマンドラインツール）を提供して、ストリームの作成、構成及び削除を可能にし得る。プログラマチックインターフェースはさらに、いくつかの実施形態では、ストリームデータ記録の送信、記憶、分析、変換及び／または検索を可能にし得る。いくつかの係る実施形態では、例えば、多数のサービスコンポーネントの間で拡張可能な方法でストリーム管理作業負荷を分散可能にする様々な分割ポリシに基づいて、サービスを実行するために、計算ソース、記憶ソース及びネットワークリソースの動的にプロビジョニングされたセットを使用してよい。
【０００７】
少なくともいくつかの実施形態では、ＳＭＡＳのクライアントは、ＳＭＡＳプログラマチックインターフェースを使用して、指定されたストリーム内の例外的または異常な観測記録の検出を要求してよい。（係る記録を指すために、本明細書では用語「アウトライア」及び「異常値」を同義語として使用してよい。）係る要求に応じて、サービスは、様々な実施形態では、ストリームの観測記録にランダムカットフォレストベースの技法を使用する効率的なアウトライア検出アルゴリズムを適用した結果を提供し得る。ランダムカットフォレストは、選択された数のランダムカットツリーを備えてよく、その各々は、サンプルの観測記録の属性値に関する再帰的ランダム分割技法を使用して、観測記録のそれぞれのサンプルに対して構築される。係るツリーは、一連のランダムカット上に構築されるため、範囲ランダムカットツリーと呼ばれることがあり、それぞれの軸平行ランダムカットは、その次元の範囲に比例する確率で選択される。以下にさらに詳細に述べる通り、アルゴリズムは、ランダムカットフォレストの少なくともいくつかのツリーを変更することなく、所与の観測記録（観測記録の異常性または例外性の程度を示す定量的指標）に関するアウトライアスコアを生成することができ得る。例えば、ノードが所与の観測記録を表す所定のツリー内の潜在的な位置を識別するために、確率的な「偽の」挿入動作を実行してよく、潜在的な位置の様々な特性（例えば、ツリーのルートノードに関する潜在的な位置の深さまたは距離、近傍の他のノード数、及び／または以下に述べる他のツリーノードからの潜在的な位置の距離）を基に、アウトライアスコアを決定してよい。ツリーが実際に更新されても（以下に述べる通り確率論的手法を使用して行われてよい）、ツリーの大部分が変更されないように、通常は小さなサブツリーのみに影響を与える効率的な技法が使用されてよい。いくつかの場合、葉ノードまでツリーを走査することなく、または正確な挿入位置を決定することなく、アウトライアスコアを生成してよい。これは、例えば、アウトライアスコアは、あるノードがツリー内に位置する深さに少なくとも部分的に基づいている場合があり、アウトライアスコアは、記録の挿入深さが一部の閾値よりも大きいという判定に基づいて、所与の観測記録に割り当てられ得るためである。本明細書の残りの部分では、記録を表すノードをツリーに挿入する動作は、単にツリーに「記録を挿入する」と呼ばれることがあり、同様に、ツリーから「記録を削除する」という句は、記録を表すノードをツリーから削除する動作を指すために使用され得ることに留意されたい。
【０００８】
各ツリーは、少なくともいくつかの実施形態では、ストリームの観測記録の動的に更新されたサンプルを表してよい。様々な実施形態では、選択された確率的ストリームサンプル更新技法（例えば、ランダム更新技法または加重更新技法）を使用して、所与のランダムカットツリーに対して新しい観測記録（つまり、アウトライア分析がまだ行われていない記録）をサンプル内に含めるべきかどうかを決定してよい。特定のランダムカットツリーに使用されるサンプルを更新する決定が行われた場合、少なくともいくつかの実施形態では、ツリー全体を再作成することなく、新しい観測記録を表すノードをツリーに追加してよい。同様に、係る実施形態では、ツリー全体を再構築することなく、除去対象となる観測記録（サンプル内で新しい観測記録を表すノードと置換される）を表す様々なノードをツリーから削除してよい。いくつかの実施形態では、ノードは、その「年齢」、つまり、ノードがツリーに挿入されてからどのくらいの時間が経過したか、またはそのノードがツリーに挿入されてからどのくらいの数の観測記録が追加されたかに少なくとも部分的に基づいて、ツリーから削除するノードが選択され得る。
【０００９】
アウトライア検出アルゴリズムの結果は、異なる実施形態では、いくつかの異なる形式のいずれかで示されてよい。例えば、一実施形態では、ストリームの様々な観測記録に対してアウトライアスコアが生成されてよく、係るスコアが計算される全ての記録のスコアをクライアントに提供してよい。所与の記録のスコアは、以下でさらに詳細に説明する通り、例えば、フォレストの様々なランダムカットツリーにおいて観測記録を表すノードが挿入されたであろう（または確率的サンプル更新技法の結果に応じて実際に挿入される）平均ツリー深度、観測記録に関連するスパース性指標、観測記録に関連する距離指標等のいくつかの要因の任意の組み合わせに基づき得る。他の実施形態では、サービスは、閾値報告基準を満たす観測記録に関してクライアントに通知し得る。例えば、アウトライアスコアが０．０〜１．０の範囲で生成され、１．０が極端に例外的なまたは異常な記録を表し、０．０がインライヤまたは通常の記録を表す場合、一実施形態では、サービスは、アウトライアスコアが０．７より大きい観測記録（または他の何らかの選択された閾値）に関してのみクライアントに通知し得る。いくつかの実施形態では、アウトライアスコアが選択された閾値を満たす記録は、単にアウトライアまたは異常値として分類されてよく、残りの記録はインライヤまたは正常な記録として分類されてよい。係る実施形態では、その解釈が少なくとも検討中となっている数値スコアを提供する代わりに、サービスは、所与の観測記録に対してバイナリ結果を単に提供してよい。「この記録はアウトライア」または「この記録はインライヤ（つまり、アウトライアではない）」という文と同等の文を、アウトライア検出を実行中のクライアントに提供してよい。異なる観測記録に対して生成されたアウトライアスコア（及び／または対応するバイナリ結果）は、例えば、後の傾向分析のために記憶または記録してよい。別の実施形態では、記録はそのアウトライアスコアに従ってランク付け（またはソート）されてよい。
【００１０】
一実施形態では、ＳＱＬ（Ｓｔｒｕｃｔｕｒｅｄ  Ｑｕｅｒｙ  Ｌａｎｇｕａｇｅ）のバージョンまたはいくつかの他の一般的に使用されるクエリ言語に少なくとも部分的に基づいたプログラマチックインターフェースがＳＭＡＳによって実装され、クライアントは、自身が取得したい結果の詳細を指定でき得る。例えば、観測記録の属性値の一部または全てをアウトライアスコアとともに表示すべきかどうか、受信した観測記録に異常値検出を行うべき時間窓及びその他などが挙げられる。様々な人の心拍数情報及び運動指標（１分あたりの歩数など）を含む健康センサ記録のストリームの異常値を分析するシナリオ例を考える。係るシナリオでは、ランダムカットフォレストベースの技法を使用してアウトライアスコアを取得するために、次のようなＳＱＬ文を含む要求が発行され得る。
この要求例では、各人物に対して２０分の時間窓で生成されたセンサ記録のアウトライアスコアが（ランダムカットツリーが構築されたｓｅｎｓｏｒＩＤ、ｈｅａｒｔｒａｔｅ及びｓｔｅｐｓＰｅｒＭｉｎｕｔｅなどの属性値とともに）要求者に提供される。アウトライア検出を表すために使用されるトークン、キーワード等の厳密なセットは、ＳＱＬのようなシンタックスがサポートされている様々な実施形態では、上に示すセットとは異なり得ることに留意されたい。いくつかの実施形態では、ＳＱＬ以外のデータベースクエリ言語を利用してよいか、またはデータベースに必ずしも紐づけられていないクエリインターフェースを使用してよい。
【００１１】
所定の観測記録セットにおいてアウトライアを構成する定義（記録が以前に収集された記録の静的セットの一部であるか、または予測不可能なストリームの一部であるかにかかわらず）は常に明確であるとは限らない。少なくともいくつかの実施形態では、アウトライアスコアを決定するため、またはアウトライアまたは非アウトライアとして所与の観察記録を分類するために使用される定義または数式は、デフォルトでまたはプログラム要求に応じてクライアントに提供され得る。上に述べた通り、所与の観測記録のいくつかの特徴は、異常値スコアまたはバイナリ異常定義、ならびに他の観測記録からの所与の観測記録の距離（例えば、ユークリッド距離）において考慮されてよく、これには、所与の観測記録の近傍における他の観測記録の希少性またはスパース性が含まれる。所与のストリームの観測記録の属性値の統計的分布は、時間の経過と共に変化することがあり、例えば、時間Ｔ１でアウトライアとみなされる記録（例えば、時間Ｔ１まで分析された観測記録に基づく）はもはやアウトライアではない場合があるか、または暫定期間に到着した記録を基に、その多くが後の（Ｔ１＋ｄｅｌｔａ１）アウトライアである場合がある。いくつかの実施形態では、アウトライア状態または所与の観測記録のスコアは、記憶されたストリーム記録の様々なセットに関して様々な時間で再評価されてよい。アウトライア検出アルゴリズムの結果が閾値を超えるマージン分変化する場合、いくつかの実施形態では、その変化に関してクライアントに通知してよい。
【００１２】
少なくとも１つの実施形態では、ストリームの観測記録は、リアルタイムで（例えば、記録がＳＭＡＳでアクセス可能になった直後に）最初に検査され、後にバッチモードでアウトライアを再検査してよい。例えば、ＳＭＡＳは、プロバイダネットワーク環境のより一般的な機械学習サービスのサブコンポーネントとして実装されてよい。概して、インターネット及び／または他のネットワークを介して、分散したクライアントセットにアクセス可能な（様々なタイプのマルチテナント及び／またはシングルテナントのクラウドベースのコンピューティングサービスまたはストレージサービスなど）１つ以上のサービスを提供するために企業または公共部門組織などのエンティティによって設定されたネットワークは、本明細書ではプロバイダネットワークと呼ばれ得る。プロバイダネットワークは、「パブリッククラウド」環境とも呼ばれることがある。所与のプロバイダネットワークは、プロバイダによって提供されるインフラストラクチャ及びサービスを実装、構成及び配信するために必要な、物理的及び／または仮想化コンピュータサーバ、ストレージデバイス、ネットワーク機器及びその他の集合体など、様々なリソースプールをホストする多数のデータセンタを含み得る。大規模なプロバイダネットワーク内では、いくつかのデータセンタは、他よりも様々な都市、州または国に配置されてよく、いくつかの実施形態では、所与のアプリケーションに割り当てられたリソースはいくつかの係る場所に配置され、所望レベルの可用性、耐障害性及び性能を達成し得る。いくつかの実施形態では、プロバイダネットワークの機械学習サービスは、観測記録の静的な集合に関するバッチジョブと、ストリーミングデータのリアルタイムタスクとの両方を処理するように設計されてよい。所与のストリームの記録は、それらが受信された後にリポジトリに記憶されてよい。アウトライア検出は、上で概説したランダムカットフォレスト技法を使用してストリーム上でリアルタイムに実行されてよく、スコアが生成され次第、クライアントにそれぞれのアウトライアスコアが提供される。後のある時点で、ストリームを閉鎖してよく、またはストリームの少なくとも一区分または論理的なサブセットを閉鎖して、追加の観測が受信されないようにしてよい。次いで、リポジトリに記憶された記録は、バッチモードのアウトライア検出アルゴリズムを使用して再分析されてよく、バッチモード動作の結果はクライアントに提供されてよい。少なくとも１つの実施形態では、既に収集されたストリームのデータの一部のサブセットに対してバッチモード処理が実行されている間に、ストリームは記録を受信し続けてよい。いくつかの実施形態では、バッチモードアルゴリズムはさらにランダムカットフォレストを使用してよく、以前にリアルタイム分析に使用された同じツリーのいくつかは、バッチモードアルゴリズムの動作中に更新されてよい。他の実施形態では、リアルタイム分析に使用された手法とは異なる手法をバッチモード分析に使用してよい。少なくとも１つの実施形態では、機械学習サービスは、ストリーミングデータに関してのみリアルタイム分析をサポートしてよいが、ストリームに対するバッチモード動作はサポートできない。
【００１３】
少なくとも１つの実施形態では、ストリームの未処理の観測記録は、ランダムカットフォレスト技法を使用して分析する前に事前処理されてよい。例えば、１つ以上の属性の未処理の値を正規化すること、観測記録のいくつかの内容を集計することによって導出された記録を生成すること、または変換関数を特定の非数値属性に適用して導出された数値を取得することを含む、任意の数の事前処理技法を様々な実施形態で使用してよい。例えば、属性の標準偏差は履歴記録に基づいて計算されてよく、将来のストリーミング記録におけるその属性値は、何らかの属性が幾何学的距離に過度に影響を及ぼさないように標準偏差で除算されてよい。
【００１４】
別の実施形態では、単一の数値属性を事前処理して複数の数値属性を生成してよい。数値属性の最新の値の曲線形状は、窓の長さｗを過去の値にわたりスライドすることによって取得されてよい。このプロセスはシングリングとして知られており、１次元のデータをｗ次元のデータに変換する。シングリングされた空間の異常値は例外的な曲線を表す。
【００１５】
アウトライア検出アルゴリズムの多数の異なるパラメータのそれぞれの値は、様々な実施形態において選択される必要があり得る。係るパラメータは、例えば、初期のランダムカットフォレストを生成するために使用されることになるストリームの観測記録の基準セットのサイズ、フォレストに含まれるランダムカットツリーの数、個々のツリーに使用されるサンプルのサイズなどを含み得る。アウトライアスコア計算のための数式または方程式に関して、ツリー深さパラメータ、距離パラメータ及び／またはスパース性パラメータは、少なくともいくつかの実施形態において選択される必要があり得る。いくつかの実施形態では、所定の観測記録がアウトライアであるかどうかを判定するときに、例えば、他の属性に対するある属性の相対的重要度を示す、他の属性とは異なる加重をいくつかの属性に割り当ててよく、係る属性の加重をアルゴリズムのパラメータと考えてよい。一実施形態では、時間窓または類似の時間置換パラメータを使用して、例えば、観測記録をサンプルから置換することに関してツリーを更新してよく、より最近受信した観測記録には、古い観測記録よりもサンプルに含まれる高確率が割り当てられ得る。アウトライア検出アルゴリズムの他のパラメータは、例えば、任意の所与のアウトライアスコアに関する通知が提供または生成されるかどうかを決定するために使用される通知閾値、またはアウトライアまたはインライヤとしての観測記録のバイナリ分類に使用される特定の境界スコアを示すアウトライア指定閾値を含み得る。
【００１６】
少なくともいくつかの実施形態では、ＳＭＡＳまたは機械学習サービスの知識ベースの入力に基づいて、１つ以上のパラメータ値を選択してよい。例えば、同様のデータセットに対して過去に上手く動作したパラメータ値を再使用してよい。例えば、１つの実施形態では、所与のストリーム上のアウトライア検出アルゴリズムによって生成された１つ以上のアウトライアスコアまたは他の結果の主観的評価を提供するために、プログラマチックインターフェースをクライアントに提供してよい。主観的な評価情報は、未処理または処理済みの形式であり、知識ベースの入力として記憶されてよい。後に、その知識ベース入力を使用して異なるストリームのアウトライア検出に使用されるパラメータを調整または識別してよい（あるいは、クライアントによって評価が提供されたデータストリームの新着記録のパラメータをさらに変更してよい）。一実施形態では、いくつかのパラメータは、例えば、ＳＭＡＳプログラマチックインターフェースを介してクライアントに供給されてよい。クライアントは、統計または機械学習の専門家である必要はないが、一部のクライアントは、観測記録の内容に関する分野固有の専門知識を基に、１つ以上のアルゴリズムパラメータ（サンプルの一時的な置換パラメータまたは異なる属性の相対的な重要性を示す加重など）に関するガイダンスを提供可能であってよい。
【００１７】
システム環境例
図１は、少なくともいくつかの実施形態による、ストリーミングデータ記録にアウトライア検出を行い得るシステム環境例を示す。図示の通り、システム１００は、拡張可能な階層アーキテクチャに従って組織されたストリーム管理及び分析サービス（ＳＭＡＳ）１０２の様々なリソースを含み、ＳＭＡＳはストリーミングデータの受信、記憶、分析及び読み取りアクセスの提供を行うそれぞれのサブシステムを伴う。図示の実施形態では、ＳＭＡＳ１０２は、インジェスチョンサブシステム１０４、ストレージサブシステム１０６、検索サブシステム１０８、制御プレーンサブシステム１１０及び分析サブシステム１９０を備え得る。各サブシステムのリソースは、図示の実施形態にある他のサブシステムとは関係なく拡大または縮小され得る。例えば、実行中の分析アルゴリズムが追加の計算能力を必要とする場合、他のサブシステムにおいてリソースを変更することなく、より多くのサーバを分析サブシステム１９０に追加してよい。一般的に、様々なクライアントは、異常検出だけでなく、プロバイダネットワーク環境内のそれぞれのアプリケーションに対してＳＭＡＳを使用してよい。いくつかの実施形態では、ＳＭＡＳは任意の複雑性のワークフローでパイプライン化されたアプリケーションを構築するために使用されてよく、例えば、１つのストリームから生成された処理結果は第２のストリームの入力データ記録を形成してよく、第２のストリームは第３のストリーム、第４のストリーム及びその他のストリームの入力データを生成するために処理されてよい。係る各ストリームの内容は、例えば、未処理及び／または処理済みのストリーム記録を多数のノードで複製することによって永続的な方法で記憶され、所望レベルの可用性及びデータ永続性を提供してよい。
【００１８】
概して、サブシステム１０４、１０６、１０８、１１０及び１９０のそれぞれは１つ以上のノードまたはコンポーネントを含んでよく、これらは、例えば、プロバイダネットワークの様々なサーバまたはホストでインスタンス化された実行可能なスレッドまたはプロセスのそれぞれを使用して実装される。インジェスチョンサブシステム１０４のノードは、データプロデューサ１５８から特定のデータストリームのデータ記録を取得または受信するように（例えば、制御サブシステム１１０のノードによって）構成されてよく、各インジェスチョンノード１６０はストレージサブシステム１０６の対応するノードに受信したデータ記録を渡してよい。１５８Ａ〜１５８Ｃなどのデータプロデューサ１５８は、多様なタイプのデータソースを含んでよく、例えば、様々な実施形態では、センサアレイ、ウェブアプリケーションのログ、セキュリティカメラ及びその他が挙げられる。ストレージサブシステムノード１６１（例えば、１６１Ａまたは１６１Ｂ）は、ストリームに対して選択された永続性ポリシに従って、様々なタイプのストレージデバイス（例えば、ソリッドステートドライブ（ＳＳＤ）、回転磁気ディスクベースのデバイスまたは揮発性メモリデバイス）のいずれかにデータ記録を保存し得る。検索サブシステム１０８のノード１６２（例えば、１６２Ａまたは１６２Ｂ）は、１６５Ａまたは１６５Ｂなどの外部データ消費者（例えば、処理済みのストリームデータが入力として提供される先のアプリケーションを含み得る）及び／または分析サブシステム１９０の分析ノード１９４Ａなどの内部データ消費者からの読み出し要求に応答し得る。分析ノード１９４（１９４Ａなど）は、例えば、ＳＭＡＳクライアント１６６から受信された指定されたストリームに関する要求に対する応答を提供するために、様々な実施形態において多数の異なるタイプの統計または機械学習アルゴリズムを実行または実装するように構成され得る。制御サブシステム１１０は、ストリームの作成または削除、ストリームの分割及びその他の管理動作を総括的に担う、ノード１６８Ａなどの、多数の制御ノード１６８を含み得る。
【００１９】
所与のストリームは、いくつかの実施形態では、パーティション（シャードとも呼ばれ得る）に細分化されてよい。図示の実施形態では、１つ以上のノードのそれぞれのセットは、ストリームの各パーティションに対して、例えば、少なくともインジェスチョンサブシステム、ストレージサブシステム及び検索サブシステムに関して指定されてよい。例えば、ストリームＳ１のパーティション０にインジェスチョンノード１６０Ａを設定してよく、ストリームＳ１のパーティション１にインジェスチョンノード１６０Ｂを設定してよい、などである。同様に、１つ以上のストレージサブシステムノード１６１を各パーティションに設定してよく、検索ノード１６２Ａのそれぞれのセットを各パーティションにも設定してよい。いくつかの実施形態では、分析サブシステム１９０のリソースのそれぞれのサブセットをそれぞれのストリームパーティションに割り当ててもよい。
【００２０】
図１に図示する実施形態では、ＳＭＡＳクライアント１６６は管理プログラマチックインターフェース１６４の１つ以上のセットを利用して、制御プレーンサブシステム１１０と相互作用し得る。同様に、データプロデューサ１５８は、プロデューサプログラマチックインターフェース１６７を使用してデータ記録を送信してよく、データ消費者は、消費者プログラマチックインターフェース１６５を使用して、記憶された記録を読み出してよい。いくつかのクライアント１６６は、分析インターフェース１９２を使用して、それらのストリームのデータ分析要求を送信してよい。様々な実施形態におけるストリームデータ記録の送信、記憶されたストリームデータ記録の検索、分析要求及び／または管理動作の要求に使用され得るＡＰＩ（アプリケーションプログラミングインターフェイス）の特定の数例がさらに図１に示されている。例えば、データプロデューサ１５８は、「ｐｕｔＲｅｃｏｒｄ」ＡＰＩを使用して、指定されたストリーム（または指定ストリームの指定パーティション）にデータ記録を送信してよい。少なくともいくつかの実施形態では、ＳＭＳによって記憶された各データ記録にシーケンシングインジケータ（シーケンス番号など）を関連付けてよく、所与のストリームの記録は、シーケンス番号順またはランダムな順序で検索可能であってよい。「ｇｅｔＩｔｅｒａｔｏｒ」ＡＰＩは、図示の実施形態では、ストリームまたはパーティション内の開始位置または開始シーケンス番号を示すためにデータ消費者によって使用されてよく、「ｇｅｔＮｅｘｔＲｅｃｏｒｄｓ」ＡＰＩは、イテレータの現在の位置から順番に記録を検索するために使用されてよい。図示の実施形態、例えば、イテレータを確立する必要がないランダムアクセスでは、「ｇｅｔＲｅｃｏｒｄ」ＡＰＩをさらにサポートしてよい。制御プレーンＡＰＩまたは管理ＡＰＩには、例えば、「ｃｒｅａｔｅＳｔｒｅａｍ」（新しいストリームを構築する）、「ｄｅｌｅｔｅＳｔｒｅａｍ」（既存のストリームを削除する）、「ｄｅｓｃｒｉｂｅＳｔｒｅａｍｓ」（指定ストリームのプロパティを表示する）などが含まれてよい。
【００２１】
ストリームデータ分析に関しては、例えば、受信した観測記録の数、記録到着率、データの現在の合計サイズ、これまでに受信された観測記録の様々な数値属性の平均または分散等などの、指定ストリームに関する高レベルの統計を取得するために、「ｇｅｔＳｔａｔｉｓｔｉｃｓ」ＡＰＩを呼び出してよい。「ｇｅｔＯｕｔｌｉｅｒＳｃｏｒｅｓ」ＡＰＩは、様々な観測記録の異常の程度を示すスコアを取得するために呼び出されてもよく、「ｌｉｓｔＯｕｔｌｉｅｒｓ」ＡＰＩは、（例えば、ＳＭＡＳまたはクライアントによって決定された閾値アウトライアスコアに基づいて）アウトライアとして分類された観測記録を取得するために使用されてよい。いくつかの実施形態では、分析サブシステム１９０で実施されるアウトライア検出アルゴリズムの結果を取得するために、ＳＱＬまたはいくつかの他の周知のクエリインターフェースに基づくインターフェースが利用されてよい。図１に示すＡＰＩ以外のストリーム指向ＡＰＩは様々な実施形態で利用されてよい。少なくともいくつかの実施形態では、ＡＰＩ以外のプログラマチックインターフェース（例えば、ウェブベースのコンソール、グラフィカルユーザインターフェース及び／またはコマンドラインツールなどのウェブページ）が使用され得ることに留意されたい。
【００２２】
様々な実施形態では、プログラム分析インターフェース１９２のうちの１つを呼び出すことにより、１つ以上のデータプロデューサ１５８から観測記録が収集されている（または収集中の）所与のストリームの観測記録にアウトライア検出を行うことがＳＭＡＳに知らされ得る。これに応答して、ＳＭＡＳはまず、図示の実施形態において、指定されたストリーミングデータソースから観測記録の基準セットを収集し得る。観測記録の基準セットは、各ツリーが基準セットの特定のサンプルまたはサブセットに対応するランダムカットツリーの初期集合を生成するために使用されてよい。ツリーの葉ノードはそれぞれの観測記録に対応し得、葉以外のノードは観測記録のグループ（または葉以外のノードの子孫ノードによって表される観測記録の属性値の「境界ボックス」）を表す。ランダムカットツリーの集合は、ランダムカットフォレストとも呼ばれ得る。さまざまな実施形態においてツリーが構築され得る方法の詳細及び例を以下に示す。
【００２３】
一般的に、ツリーの構築方法に起因して、ツリー内の所与の観測記録のノードの位置または深さは、観測記録のアウトライアの程度を示し得る。図６に例示し、以下にさらに詳細に述べる通り、少なくともいくつかの実施形態では、深さの浅いツリーで生成される葉ノード（すなわち、ツリーのルートに近い）に対する観測記録は、対象の観測記録の母集団に関して、葉ノードが深い深さにある観測記録よりも異常または例外的となる傾向にある。その結果、ツリー内の対応するノードの位置に少なくとも部分的に基づいて、アウトライアスコア（例えば、０〜１または０〜１００の範囲の実数であり、値が高いほどより異常な記録を表す）を計算するか、または観測記録に割り当ててよい。例えば、一実施形態では、所与の観測記録の基準セットのそれぞれのサンプルに対して１０本のツリーが構築され、所与の観測記録が１０本のツリーのうちの３本にたまたま表示された場合、それらの３本のツリー全体にわたる観測記録の深さと、残りの７本のツリーに偽って記録が挿入される深さとを平均化して、アウトライアスコアを生成してよい。他の実施形態では、アウトライアスコアを計算するときに、観測記録の近隣のスパース性（例えば、観測記録がＮ個の属性を含む場合、その属性に対応するＮ次元空間においてその近くに他に観測記録がいくつあるか）及び／またはサンプルの他の観測記録からの観測記録の距離（例えば、ユークリッド距離）を考慮してよい。
【００２４】
記録の基準セットを使用して、所与のストリームについて最初のランダムカットフォレストが構築された後、分析サブシステム１９０は、新しい観測記録が到着すると、その記録の分析を開始し得る。フォレストがＴツリーを含むシナリオの例を考える。新しい観測記録ＯＲ１がアクセス可能になると、いくつかの実施形態では、各ツリーへのＯＲ１の「偽の」挿入を試みてよい。偽の挿入（詳細は以下に提供する）の間に、ＯＲ１が実際に挿入されたツリー内のＯＲ１を表すノードの位置が決定されてよく、Ｔツリー内のノードの偽の挿入位置が集合的に使用されて、ＯＲ１の全体のアウトライアスコアが計算されてよい。いくつかの実施形態では、分析が実行されているクライアント１６６の設定に応じて、アウトライアスコアは計算後すぐにクライアントに提供されてよく、例えば、ＯＲ１の受信に関してリアルタイムに提供されてよい。初期のアウトライアスコアは、ＯＲ１が受信された時点で利用可能な情報に基づいて計算可能なだけである（かつ、将来の観測記録内容を予測することはできない）ため、リアルタイムでクライアントに提供される情報は、所与の時点においてのみ利用可能な最良の分析を表し得ることに留意されたい。以下に述べる通り、いくつかのシナリオでは、例えば、ストリームの観測記録の属性値の分布の時変傾向に基づいて、所与の観測記録のアウトライア状態またはスコアが後に再計算された場合、それらは実際に変化することがある。
【００２５】
少なくともいくつかの実施形態では、ツリーに使用されるサンプル、したがってツリー自体は、新しい観測記録が到着するときに確率的に更新されてよい。いくつかの実施形態では、均一に分布した乱数を使用して、所与の新しい観測記録が、以前に包含された観測記録を所与のサンプルＳと置換すべきかどうかを決定し得るランダムサンプル更新アルゴリズムを使用してよい。他の実施形態では、所与の観測記録を含むかどうかは依然として確率的に決定されるが、例えば、一般的に、最近の観測であるほど古い観測記録よりもサンプルに含まれる可能性が高い（したがって、ランダムフォレスト内に表われる）加重ランダムサンプル更新アルゴリズムを使用してよいが、所与の観測記録を含めるという決定はやはり確率的に行われてよい。観測記録ＯＲ１をツリーに挿入する決定が行われた場合、ＯＲ１を表すノードは、以前に「偽の」挿入動作で識別された位置に挿入されてよく、選択されたノードはツリーのサンプルサイズを維持するために削除されてよい。いくつかの実施形態では、確率的ストリームサンプル更新アルゴリズムを使用して、新しい観測記録のアウトライアスコアを取得する前に（後ではない）新しい観測記録を挿入するかどうかに関する決定を行ってよく、例えば、観測記録を挿入すべきでないという決定が早期に行われた場合にのみ「偽の」挿入を行ってよい。一実施形態では、時間窓または観測記録カウント窓を使用してよく、ここでは、所与の時点ＰＴ１において、指定された時間間隔（ＰＴ１〜デルタ１、ＰＴ１）内で受信された観測記録のみを分析してアウトライアを識別するか、または最近受信したＮ個の観測記録のみを分析してアウトライアを識別する。
【００２６】
アウトライア検出アルゴリズムの概要
図２は、少なくともいくつかの実施形態による、一対のアウトライアを有する２属性観測記録のストリーム及びアウトライア検出アルゴリズムの概要の簡単な例を提供する。タイムライン２００は、ストリームの１２の観測記録またはポイントＰ０１〜Ｐ１２の相対的な到着時間を示し、それぞれは２つの数値属性Ａ１及びＡ２の値を備える。図示の通り、ストリームの観測記録の到着間隔は異なることがあり、いくつかの観測記録（Ｐ０８及びＰ０９など）は同時またはほぼ同時に到着し得る。クラッタを避けてアウトライア検出に関連する概念を例示するために、非常に小さい記録ストリームが示されていることに留意されたい。
【００２７】
グラフ２０５は、１２のポイントＰ０１〜Ｐ１２のＡ１値及びＡ２値のプロットを示す。Ａ１値は水平軸に沿って左から右に増加し、Ａ２値は垂直軸に沿って下から上に増加する。直感的には、Ｐ０５及びＰ１０を除く全ての観測記録は、それらの属性値において互いに非常に近接しているようにみえる（したがって、総称してインライヤクラスタ２１０とラベル付けされる）が、Ｐ０５及びＰ１０はアウトライアまたは異常値のようにみえる。アウトライア検出アルゴリズムの概要をフローチャート２５０に示しており、その目的とは、Ｐ０１〜Ｐ１２のいずれかなどの所与の観測記録が到着した後に、可能な限り早急に、その観測記録をインライヤクラスタ２１０のメンバとして分類すべきか、あるいはアウトライアであることを示すスコアを割り当てるべきかを識別することである。
【００２８】
要素２５１に示す通り、アルゴリズムの初期段階において、観測記録の基準セットがストリームから収集されてよい（図２のタイムライン２００に関して示された観測記録の数は、有用な基準セットを提供するには小さすぎることに留意）。その基準セットから、いくつかのより小さいサンプルが選択されてよく、例えば、分割属性の完全にランダムな選択の代わりに以下に説明される範囲ベースの分割属性選択を使用して、各サンプルに対してそれぞれのランダムカットツリーを構築してよい。この初期段階が完了した後、図示の実施形態では、各ツリー（要素２５５）へのそれぞれの「偽の」挿入に基づいて、新しく受信された観測記録ごとにアウトライアスコアが生成され得る。「偽の」挿入では、ツリーを実際に変更することなく、観測記録を表すノードの潜在的な挿入位置が見つかるまで、ルートから開始してツリーを走査し得る。潜在的な挿入位置の位置または深さに基づいて、観測記録のアウトライアスコアを各ツリー（またはいくつかの選択された数のツリー）に関して決定してよく、次いで、（例えば、平均スコアを取得することによって）異なるツリーの全てのアウトライアスコアを集計し、そのポイントの全体または最終的なアウトライアスコアに達してよい。この最終スコアは、ストリームが分析されているクライアントの報告設定及び／またはスコア永続性設定に応じて、任意には１つ以上の宛先に報告されてよい、及び／または永続ストレージに記憶されてよい。要素２５９に示す通り、０以上のツリーは、所与の観測記録を実際に挿入することによって（及びサンプルサイズを変更しないようにノードを削除することによって）確率的に更新してよい。本明細書において「真の」挿入と呼ばれるこれらのタイプの挿入は、少なくともいくつかの実施形態において、通常、アウトライアスコア計算に使用される「偽の」挿入よりも頻繁に行われることはない。新しいノードを所与のツリーに挿入することは、ツリーを最初から再作成することなく、以下でさらに詳細に説明する通り、ツリーのノードのサブセットを再構成することを伴うことがあり、したがって、各挿入がツリー全体を再構築する必要がある場合よりも効率的であり得る。要素２５５及び２５９に対応する動作は、新しい観測記録のために、例えば、図示の実施形態でストリームが終了するまで繰り返されてよい。時間の経過に伴い、ツリーの多くのノードが置換されるにつれてツリーが変化し、ツリーの内容（したがって、ツリーから派生したアウトライアスコア）は、より昔に到着した観測記録よりも、最近の観測記録をより厳密に表す傾向にある。
【００２９】
時変アウトライア状態
図３は、少なくともいくつかの実施形態による、いくつかの観測記録のアウトライア状態を結果的に変化させ得る、ストリーミング観測記録属性値の分布の経時的なシフトの一例を示す。図２と同様に、観測記録が２つの属性Ａ１及びＡ２の値を含むストリーミングデータセットの異常値について検査する。グラフ３０５Ａは、時間Ｔ１の時点でのストリームの最新の１２の観測記録の分布を示し、グラフ３０５Ｂは、後の時間Ｔ２の時点における最新の１２の観測記録の分布を示す。グラフ３０５Ａにおいて、観測記録Ｐ０５及びＰ１０は異常値またはアウトライア３０６Ａ及び３０６Ｂとみなされてよく、観測記録Ｐ１０、Ｐ０２、Ｐ０３、Ｐ０４、Ｐ０６、Ｐ０７、Ｐ０８、Ｐ０９、Ｐ１１及びＰ１２はインライヤクラスタ３１０Ａのメンバとみなされてよい。
【００３０】
矢印３２５で示すように、図示の実施形態では、Ｔ１後にＡ１及びＡ２の値に対応する２次元空間内の観測記録の位置にはシフト傾向がみられる。Ｔ１の後にさらに１０の観測記録が受信された後、最新の１２の観測記録の分布はグラフ３０５Ｂに示されるものに変化した。現在、Ｐ１０はもはや異常値ではなく、代わりに、Ｐ１０は、Ｐ１０、Ｐ１３、Ｐ１４、Ｐ１５、Ｐ１６、Ｐ１８、Ｐ１９、Ｐ２０及びＰ２１を備える現在のインライヤクラスタの一部である。Ｐ１７は新しいアウトライア３０６Ｆのようにみえる。さらに、１２の観測記録の現在のグループに関して、Ｐ１１及びＰ１２は、ラベル３０６Ｄ及び３０６Ｅに示す通り、アウトライアとしてもみえる。ゆえに、Ｐ１１及びＰ１２のアウトライア状態は、時間Ｔ１とＴ２との間で変化した。追加的に、Ｐ１０の状態はさらに、時間Ｔ１のアウトライアから時間Ｔ２のインライヤに変化した。
【００３１】
いくつかの実施形態では、上に述べた通り、様々な観測記録のアウトライアスコアが、リアルタイムまたはほぼリアルタイム、つまり、スコアが最初に計算されるとすぐに、または計算の直後に（例えば、上述のランダムカットツリーベースの技法を使用して）クライアントまたは他の宛先に提供される。ゆえに、例えば、図３に示すシナリオの場合が起こり得ることがあり、このシナリオは、Ｐ１１のアウトライアスコアが時間（Ｔ１＋デルタ１）でクライアントに送信または表示されてよく、ここでデルタ１は（Ｔ２−Ｔ１）と比較して小さい。時間（Ｔ１＋デルタ１）では、Ｐ１１のスコアは比較的低くなり得るため、Ｐ１１はインライヤとみなされ得る。図３に示す例では、Ｔ２の直後にＰ１１のアウトライアスコアが再計算された場合、スコアは（Ｔ１＋デルタ１）よりもはるかに高くなることがあり、これは、アウトライアとしてのＰ１１の新しい状態を示す。いくつかの実装形態では、所与の観測記録のアウトライアスコアまたは状態は、ストリームを分析するエンティティによって１回だけ報告されることがある。他の実装では、所与の観測記録のアウトライアスコアは、数回、例えば、リアルタイムで１回及びその後に少なくとも１回にわたり再計算及び／または報告されることがある。いくつかの実施形態では、ストリームの観測記録は、それらが到着するとリアルタイムでアウトライアについて分析されてよく、バッチモードで実行され得る後の再分析のためにリポジトリに保存されてよい。いくつかのアプリケーションでは、係る反復または反復アウトライア検出技法は、観測ソースの挙動の段階的な傾向を把握することが重要な場合があるため、非常に役立つことがある。
【００３２】
ランダムカットツリー構築の概要及び例
上に示した通り、様々な実施形態で利用されるアウトライア検出アルゴリズムは、ランダムカットツリーの異形を利用してよく、ここでは、分割が行われる属性が属性値の範囲またはスパンに基づいて選択されてよく、所与の記録のアウトライアスコアは、近隣のスパース性及び他のポイントからの距離を含むいくつかの要因に基づき得る。「分割」及び「ランダムカット」という用語は、本明細書では区別なく使用されてよく、観測記録の属性または次元の１つに従って選択された境界値に基づいてデータ記録のセットをより小さいサブセットに分割することを指す。アウトライア状態に寄与する要因と分割属性選択の範囲ベースの異形を説明する前に、ランダムツリーに関する基本概念及びアウトライア分析におけるそれらの使用について説明することは役立ち得る。
【００３３】
図４及び図５は、少なくともいくつかの実施形態による、ランダムカットツリーを使用してデータセットからアウトライアを識別する技法の初期ステップを集合的に示す。例示したシナリオの例では、３５の記録を備える２次元データセットが使用され、データセットは初期ステップに対応する期間中は変更されないものとみなされる。各記録には２つの数値属性Ａｔｔｒ１及びＡｔｔｒ２の値が含まれ、記録の分布は、Ａｔｔｒ１値が水平軸上で左から右に増加し、Ａｔｔｒ２値が垂直軸上で下から上に増加するようにプロットされている。Ａｔｔｒ１及びＡｔｔｒ２値の２次元空間内の「境界ボックス」ＡＢＣＤには、３５のポイントが全て含まれている。図４に示すような２属性記録の所与のセットでは、境界ボックスは、（Ａｔｔｒ１ｍａｘ−Ａｔｔｒ１ｍｉｎ）に（Ａｔｔｒ２ｍａｘ−Ａｔｔｒ２ｍｉｎ）を乗算することによって形成された領域に相当し、ここで、Ａｔｔｒ１ｍａｘは記録中のＡｔｔｒ１の最大値であり、Ａｔｔｒ１ｍｉｎは記録中のＡｔｔｒ１の最小値であり、Ａｔｔｒ２ｍａｘは記録中のＡｔｔｒ２の最大値であり、Ａｔｔｒ２ｍｉｎは記録中のＡｔｔｒ２の最小値である。（Ａｔｔｒ１ｍａｘ−Ａｔｔｒ１ｍｉｎ）はＡｔｔｒ１の「範囲」または「スパン」と呼ばれ得、（Ａｔｔｒ２ｍａｘ−Ａｔｔｒ２ｍｉｎ）はＡｔｔｒ２の「範囲」または「スパン」と呼ばれ得る。境界ボックス（任意の所望の次元数まで拡張してよい）の概念は、ランダムカットツリーに関連する動作を述べるときに本明細書で広く使用されてよい。
【００３４】
記録のためにランダムカットツリーを構築する第１のステップでは、（例えば、全ての属性の中からランダムに、または以下に述べる属性の値の範囲に基づいて）特定の属性を、記録が分割される属性として選択してよい。図４の分割Ｓ１では、属性Ａｔｔｒ１が第１の分割属性として選択され、Ａｔｔｒ１のＸ１の値（例えば、Ａｔｔｒ１の範囲内でランダムに選択される）が、記録を２つのより小さいサブセットに細分化するために使用される。第１のサブセットは境界ボックスＧＥＦＤに対応し、第２のサブセットは境界ボックスＨＢＪＫに対応する。分析される全ての記録を含む境界ボックスＡＢＣＤは、「レベル０」の境界ボックスと呼ばれてよく、対応するランダムカットツリー内のルートノードによって表されてよい。子境界ボックスＧＥＦＤ及びＨＢＪＫは、「レベル１」の境界ボックスと呼ばれることがあり、それぞれがランダムカットツリーのルートのそれぞれの子ノードによって表されてよい。（８つの記録の集合に対応する完全なツリーの構成例が図６に示され、以下に説明される。）
【００３５】
レベル１の境界ボックスが識別された後、ランダム分割のプロセスは、レベル１の境界ボックスに再帰的に適用され、図５に示す通り、レベル２の境界ボックスを生成してよい。レベル１の境界ボックスＧＥＦＤに関して、ランダム分割Ｓ２−ａがＡｔｔｒ２軸上で実行されてよく、図示の例では分割値Ｙ１が実行される。その結果、レベル２の境界ボックスＧＬＭＮ及びＯＰＦＱが生成されてよく、対応するノードがランダムカットツリーに追加されてよい。同様に、ランダム分割Ｓ２−ｂを境界ボックスＨＢＪＫ上で実行してよく、ここではＡｔｔｒ２もたまたま分割属性として選択されるが、異なる分割値Ｙ２が選択される。その結果、レベル２の境界ボックスＨＷＴＲ及びＵＶＪＺが生成されてよく、ツリー深さが２（つまり、ルートノードから２ホップ）の対応ノードが作成されてよい。様々な実施形態では、単一の記録のみを含む（したがって、これ以上分割することができない）境界ボックスが生成されるまで、各境界ボックスを再帰的に分割するプロセスを繰り返してよい。いくつかの実施形態では、ツリーは、選択された深さまでしか、例えば、サンプルサイズの対数に比例する深さまたは固定された定数までしか構築できない。係るシナリオでは、選択された深さの葉ノードは、個々の記録ではなく、境界ボックスを表すことがある。係るツリーの刈り込みは、選択された深さを超える位置に挿入されるであろうノードに関しては、対応するデータ記録がアウトライアを表さないので、選択された深さを超えてツリーを拡張する必要はないという仮定の下で行われてよい。ツリーが構築された後、いくつかの実施形態では、様々な観測記録を表す葉ノードのそれぞれの深さが計算され、観測記録のアウトライアスコアを計算するために使用されてよい。図６に示す通り、ランダムカットツリーを構築するプロセスは確率的であるが、一般的に、異常なポイントはツリーの上位の葉ノード（ルートに近い）に相当する傾向がある。
【００３６】
図６は、少なくともいくつかの実施形態による、ランダムカットツリー内の観測記録を表すノードが観測記録のアウトライア状態の指標として使用され得るツリー深さのシナリオ例を示す。８つの観測記録Ｐ０１〜Ｐ０７の集合のランダムカットツリー６０２が示されている。各観測には、２つの数値属性Ａｔｔｒ１及びＡｔｔｒ２のそれぞれの値が含まれている。この例に含まれる少数の記録では、Ａｔｔｒ１に関しては、ほとんどの記録が値域９〜１１に集まり、Ｐ６は８５のＡｔｔｒ１を有するアウトライアであること、ならびにＡｔｔｒ２に関しては、ほとんどの記録が１９〜２２の値域に集まり、Ｐ３は７５のＡｔｔｒ２値を有するアウトライアであることは、比較的容易に（ツリーを構築しなくても）判断される。
【００３７】
ツリー６０２のルートノードは、８つ全ての記録を表す境界ボックスに対応する。Ａｔｔｒ２は、その範囲（７５−１９）／（（７５−１９）＋（８５−９））に比例する確率で第１の分割属性として選択される。ルートの境界ボックス内のＡｔｔｒ２の範囲は１９〜７５で、分割値５０はその範囲内から選択される。その結果、ツリー深さ１では、Ａｔｔｒ２値が５０未満の７つの観測値を有するノード６０３Ｂと、１つの観測値（Ｐ３）を有するノード６０３Ｐの２つのノードが作成される。葉以外のノード（つまり、２つ以上の観測記録を表すノード）を分割するプロセスは、ノード６０３Ｂ及びその子ノードに関して継続される。Ａｔｔｒ１は第２の分割に対して選択された属性であり、第２の分割に対して値３０が選択され、その結果、Ｐ６を表す葉以外のノード６０３Ｑが作成される。レベル３ではＡｔｔｒ１がたまたま分割属性として再び選択され、１０．５の分割値が９から１１のＡｔｔｒ１範囲から選択され、結果として葉以外のノード６０３Ｄ及び６０３Ｅとなる。最終的に、各観測記録に対して葉ノードが作成される。観測記録に対応する葉ノードの深さ（ルートから葉ノードに到達するのに必要なホップ数）は以下の通りである。Ｐ０、Ｐ２、Ｐ５及びＰ７はそれぞれ深さ５に位置し、Ｐ１及びＰ４は深さ４に位置し、Ｐ６は深さ２に位置し、Ｐ３は深さ１に位置する。ゆえに、ツリー６０２は、アウトライア（Ｐ３及びＰ６）に対応するノードが、インライヤである観測値を表すノードよりも浅い深さ（ルートに近い）で終わる一例を提供する。当然ながら、分割属性がランダムに選択され、分割値が対応する属性値の範囲内からランダムにさらに選択される場合、一部のアウトライアが一部のインライヤよりも深いところにたまたま配置される場合が時にあり得る。しかしながら、十分に大きい数のランダムカットツリーが構築された場合、一般的に（ノードが表現されている全てのツリーに関する）ノードの平均ツリー深さは、対応する観測記録のアウトライア状態と負の相関を示す傾向にあり得、つまり、平均深さが浅いほど、観測値がアウトライアである可能性が高くなり得る。
【００３８】
ストリーミングデータのための効率的に更新されたランダムカットフォレスト
上に示した通り、少なくともいくつかの実施形態では、例えば、データセットのそれぞれのサンプルまたはサブセットから複数のランダムカットツリーを構築してよく、所与のデータ記録のアウトライアスコアは、２つ以上のツリーを使用して（その観測記録がたまたま表われている全てのツリーから）取得してよい。図７は、少なくともいくつかの実施形態による、ストリーミングデータセットに対して確率的に作成及び更新され得るランダムカットツリーのセット例を示す。図示の実施形態では、例えば、ストリームにアウトライア検出を行う要求が受信された後に、観測記録の基準セットを収集してよい。その基準セットから、Ｓａｍｐ０、Ｓａｍｐ１及びＳａｍｐ２などのそれぞれのサンプルを、例えば、リザーバサンプリングを使用して取得してよい。基準セットの任意の所与の観測値は、任意の所与のサンプルで必ずしも表される必要はない。いくつかのシナリオでは、一部の観測記録がいずれのサンプルにも表されない場合が起こり得る。
【００３９】
各サンプルに関して、ランダムカットツリーの対応する異形を構成してよい。図９の文脈で以下に述べる通り、これらの異形ツリーの構築中に、次の分割属性としてある属性を選択する場合、分割される境界ボックス内の異なる（潜在的に既に正規化されている）属性の相対範囲またはスパンを考慮に入れてよいため、より大きな範囲の値を有する属性は分割属性として優先的に選択される傾向があり得る。係るツリーは、本明細書では範囲ベースのランダムカットツリーと呼ばれ得る。範囲ベースの分割属性選択を使用して、それぞれＳａｍｐ０、Ｓａｍｐ１及びＳａｍｐ２に対応するＲＣＴ０、ＲＣＴ１及びＲＣＴ２を生成してよい。各サンプルは、対応するルート境界ボックスを表してよく、例えば、境界ボックスＢＢ０−０はＳａｍｐ０の観測記録に対応し、ＢＢ１−０はＳａｍｐ１の観測記録に対応するなどであってよい。範囲ベースの分割手法の使用及び分割される第１の親ノードとしてのルートノードの使用により、いくつかの実施形態では、サンプルの全ての観測記録に対してそれぞれの葉ノードが作成されるまで、より小さな境界ボックスを表すノードを再帰的に生成してよい。他の実施形態では、ツリー生成は、例えば、より深い深さに追加されたノードはアウトライアである可能性が低いという仮定の下で、いくつかの選択された深さで終了してよく、よって、ツリーのノード間で計測することができるが、覚えておく必要はない。所与のストリームに対して（または静的データセットに対して）生成されたＲＣＴ０、ＲＣＴ１及びＲＣＴ２などのランダムカットツリーは、総称してランダムカットフォレストと呼ばれ得る。いくつかの場合、ツリーが生成される前に（例えば、個々の属性の値を正規化するために）変換関数を観測記録に適用してよい。
【００４０】
初期バージョンのＲＣＴが基準セットから生成された後、それらを使用して、基準セットのメンバではない新しい観測記録のアウトライアスコアを割り当ててよい。新しい観測記録が受信されると、各ツリーに対して少なくとも２種類の動作が行われてよい。動作のうちの１つのセットは、「偽の」挿入と呼ばれることがあり、新しい観測記録がそのＲＣＴのサンプルに追加されることになった場合、所与のＲＣＴにおける新しい観測記録を表すことになるノードの位置は、以下でさらに詳細に説明する挿入アルゴリズムを使用して決定され得る。係る潜在的な挿入位置は、いくつかの実施形態では、ツリーのいずれかを実際に変更することなく、フォレストの各ツリーに対して識別されてよい。異なるツリーの潜在的な挿入位置は、新しい観測記録のためのアウトライアスコアを生成するために集合的に使用されてよい。一般的に、異常な観測記録は分離している傾向にあり（つまり、葉ノードによって表される）、図示の実施形態では、平均的にＲＣＴのルートにより近接している。いくつかの実施形態では、アウトライアスコアは、アウトライア検出が実行されているクライアント及び／または永続的なリポジトリに記憶されているクライアントに提供されてよい。
【００４１】
動作の第２のセットは、新しい観測記録に関するものであり（これは、偽の挿入の場合、少なくとも一部の前に行われてよく、偽の挿入の少なくとも一部の後に行われてよく、または偽の挿入の少なくとも一部と並行して行われてよい）、所与のＲＣＴ、確率的ストリームサンプル更新アルゴリズムを使用して、新しい観測記録が実際にそのＲＣＴに使用されているサンプルに挿入されるべきかどうかを決定し得る。例えば、ストリームに１０のＲＣＴが作成されている場合、（偽の挿入とは対照的に「真の」挿入動作において）所与の観測記録をサンプルに挿入すべきかどうかについて、１０の独立した決定が行われてよく、１つの決定は各ツリーに対して行われる。いくつかの実施形態では、均一なランダム分布ベースのストリームサンプル更新アルゴリズムを使用してよく、このアルゴリズムでは、任意の新しい観測記録がサンプル内に以前に含まれた観測記録を置き換える確率は、サンプルｋのサイズをこれまで収集した全記録数で除算した結果となる。リザーバサンプリングと呼ばれるこの手法は、サイズｋである全ての記録サブセットが選択される可能性を等しく備えていることを保証する。他の実施形態では、加重ストリームサンプル更新アルゴリズムを使用してよく、このアルゴリズムでは、例えば、より新しい観測記録には、サンプルへの包含に関して、古い観測記録よりも高い加重または優先度が割り当てられる。観測記録をＲＣＴのうちの１つに対応するサンプルに挿入する決定が行われた場合、少なくともいくつかの実施形態では、対応する以前に挿入された観測ノードを選択してサンプルから除去してよいため、サンプルサイズは経時的に変化しない。挿入された観測記録を表すノードは、（偽の挿入が挿入決定の前に行われる場合）偽の挿入のために識別された挿入位置に配置されてよい。他の実施形態では、サンプルサイズは経時的に変化し得る。ツリーを完全に再構成することなくＲＣＴに新しい観測記録用のノードを挿入するために使用され得る効率的な確率論的技法は、以下でさらに詳細に説明される。少なくともいくつかの実施形態では、所与のＲＣＴ（例えば、偽の挿入、ツリー固有のアウトライアスコア計算、真の挿入及び／または削除）に行われる動作は、他のＲＣＴに対する動作と並行して行われ得る。
【００４２】
アウトライア状態に寄与する要因
異なる実施形態では、観測記録をアウトライアとして指定するために、または所与の観測記録にアウトライアスコアを生成するために使用される正確な閾値及び統計的特性は変化し得る。図８は、少なくともいくつかの実施形態による、ストリーミングデータセット内のアウトライアを識別するための距離及びスパース性指標の使用を示す。図示のシナリオ例では、それぞれが２次元観測分布空間８０１内でいくつかの（それらのクラスタの他の記録に関して）「類似している」観測記録をそれぞれ含むクラスタ８４０Ａ、８４０Ｂ及び８４０Ｃ、ならびにクラスタに属していない２つの観測記録８０２Ａ及び８０２Ｂを示す。
【００４３】
アウトライアの形状定義が図示の実施形態において使用されてよく、これは、広い空き空間にある少数の記録、つまり、Ｓ０の外側にある最も近い小さな基数の記録Ｓ０のセットが少なくとも距離Ｌほど離れていることをとらえている。係る定義によれば、Ｓの記録のサブセットＳ０は、（ａ）Ｓ０の基数（記録数）がｊ以下である場合かつ（ｂ）Ｓ０内のいずれかのポイントと（Ｓ−Ｓ０）内のいずれかの記録との間の最小距離がＬを超える場合、（ｊ，Ｌ）−アウトライアであると考えられ得る。（（Ｓ−Ｓ０）の表記はＳ０にいないＳの記録の表記を示す）。これらのうち第１の条件はスパース性基準と呼ばれることがあり、第２の条件は距離基準と呼ばれることがある。
【００４４】
図８に図示するシナリオでは、ノード８０２Ａ及び８０２Ｂは、係る小さい基数グループＳ０を構成してよい。図８に示す観測記録のために構築されたＲＣＴ内の８０２Ａ及び８０２Ｂを表すノードは、例えば、両方とも同じ親ノードＰＮ１の子ノードであってよく、したがって、近隣グループまたは共通祖先グループ８１０のメンバとみなされてよい。アウトライア定義のパラメータｊが２に設定され、８０２Ａ及び８０２Ｂを表すノードのクラスタ８４０Ａ、８４０Ｂまたは８４０Ｃの記録のいずれかからの最小距離が、何らかの選択されたＬ値を超える場合、（例えば、ユークリッド距離８０５Ａ、８０５Ｂ及び８０５Ｃが全てＬを超える場合）、定義に従って、８０２Ａ及び８０２Ｂは（２，Ｌ）のアウトライアとして指定され得る。異なる実施形態では、異なるストリームについて、例えば、ストリームについて収集された、いくつかの初期統計に基づいて、及び／または知識ベース入力に基づいて、スパース性パラメータｊ及び距離パラメータＬのそれぞれの値を選択してよい。いくつかの実施形態では、所与の観測記録に関連する偽の挿入動作の一環として、距離及びスパース性指標を、観測記録を表すノードについて計算し、両方の指標に基づいてアウトライアスコアを計算してよい。
【００４５】
一実施形態では、ノード置換指標（図８には図示せず）を使用してアウトライアスコアを計算してよい。大まかには、ノード置換指標の目的とは、アウトライアスコアが計算される新しいノードの挿入によって生じる、既存のノードの位置への総変化量を把握することであり得る。例えば、ツリーの最上部付近に挿入されるノードは、通常、既存のノードの大きいサブセットを（例えば、ルートから１つの追加のホップまたはエッジによって）置換させ、ツリーの最下位レベル付近に挿入されるノードは、通常、既存のノードの小さいサブセットを置換させる。以前に述べた通り、ルート付近に追加される傾向にあるノードは、例外的または異常である可能性が高い。その結果、偽の挿入によって生じる他のノードの合計置換（各ノードとルートとの間のホップまたはエッジの合計追加数の和）を使用して、偽の挿入が行われているノードのアウトライアスコアを取得してよい。いくつかの実装では、偽の挿入によって生じる全ての既存のノード間の平均置換変化など、他の置換関連指標を使用してよい。様々な実施形態では、アウトライアスコアを計算するために以下の要因／指標の１つ以上の任意の組み合わせ、つまり、新しい観測記録のための潜在的な挿入位置の深さ、他のノードからの潜在的な挿入ノードの距離及び／または潜在的な挿入ノードに関連する置換指標を使用してよい。
【００４６】
範囲ベースの分割
以前に述べた通り、ランダムカットツリーの構築中または変更中に、いくつかの分割またはランダムカットを行ってよい。これに沿って観測記録をアルゴリズムの任意のポイントで分割することになる属性が、全ての属性の中から完全にランダムに選択される場合、これはいくつかの準最適な分割（つまり、アウトライアの分離の実質的な進展に相当しない分割）をもたらし得る。代わりに、少なくともいくつかの実施形態では、さらにデータ駆動型の分割属性選択技法を使用してよく、これは、分割属性選択決定においてランダム性の要素を依然として保持しながら、属性の相対範囲を考慮するものである。図９は、少なくともいくつかの実施形態による、ストリーミングデータのアウトライア検出アルゴリズムで利用され得る範囲ベースの分割技法を示す。
【００４７】
図示の実施形態では、２属性観測記録９１０の所与のセットを分割するための２つの選択肢が示されている。各観測記録は、それぞれの属性Ａｔｔｒ１及びＡｔｔｒ２の値を含む。Ａｔｔｒ１値は水平軸に沿って左から右に増加し、Ａｔｔｒ２値は下から上に増加する。記録間の最小Ａｔｔｒ１値は０であり、最大値は１００である。対照的に、Ａｔｔｒ２値の範囲は０〜１５である。記録はＡｔｔｒ１（アウトライアＰｊが１つある）に対して２つのクラスタを形成するが、Ａｔｔｒ２の次元ではかなり均一に分布している。
【００４８】
分割属性としてＡｔｔｒ２が選択された場合、図９の分割９０１（分割値Ｙ１を有する）に示すように、これは、アウトライアＰｊを分離するためにＡｔｔｒ１に沿って分割するほど有用ではない可能性がある。実際、単にランダムな分割属性を選択したためにＡｔｔｒ２が分割属性として複数回選択され続けた場合、Ｐｊに対応する葉ノードを生成するためには、より多数の分割が必要になり得る。対照的に、分割属性としてＡｔｔｒ１を選択する確率が増加すると、Ｐｊを表す葉ノードを作成するのにかかる時間（及び生成されるツリーレベルの数）が短縮される可能性がある。分割属性の選択にこのタイプの知的バイアスを導入する１つの方法は、各属性の範囲（最大値−最小値）を考慮し、より高い範囲を有する属性に高い確率の選択を割り当てることである。係る範囲ベースの属性選択技法は、例えば、偽の挿入動作中及び／または真の挿入動作中に、ストリームの観測記録の基準セットからランダムカットツリーの初期セットを生成するために、様々な実施形態で使用してよい。図９に示す例では、Ａｔｔｒ１は０〜１００の範囲を有し、Ａｔｔｒ２は０〜１５の範囲を有するので、範囲の合計は（１００−０）＋（１５−０）または１１５である。Ａｔｔｒ１が選択される確率が（全ての属性の合計範囲に対して）その範囲に比例しており、選択された属性を識別するために０〜１１５の乱数が選択される場合、分割属性として確率（１００／１１５）でＡｔｔｒ１が選択されることがあり、例えば、分割値Ｘ１を有する分割Ｓ２が生じる。少なくとも１つの実施形態では、単一のランダム選択により、分割属性及び分割値の選択が生じ得る。例えば、乱数４５が０〜１１５の範囲から選択された場合、これは（Ａｔｔｒ１＝４５）の分割値が使用されることになることを示すことがあり、乱数１０７が選択される場合、これは分割値（Ａｔｔｒ２＝（１０７−１００）＝７）が使用されることになることを示すことがある。同様に、分割またはランダムカットが行われるアルゴリズムの各段階において、少なくともいくつかの実施形態では（分割される記録セット内の）各属性の相対的な範囲が考慮され得る。
【００４９】
当然ながら、所与のストリームの未処理の観測記録内では、収集されているデータのセマンティクスに基づいて、いくつかの属性が他の属性よりもはるかに小さい範囲を有する場合があり得る。例えば、１つの属性は個人の正規の教育年数を表し、別の属性は個人の年間所得を表すことがあり得る。正規の教育年数は、一般的にはかなり小さい範囲（例えば、０〜２０程度）であり得るが、収入はより大幅に変化する可能性がある（例えば、通貨によって０〜１０，０００，０００程度）。係るシナリオでは、アウトライア分析を行う前に、未処理の観測記録を事前処理してよい。例えば、各値を１つの実装で観測された、いくつかの未処理の値の標準偏差で除算することによって属性値を正規化してよい。
【００５０】
ノードの挿入及び削除
前に示した通り、確率的アルゴリズムは、様々な実施形態においてランダムカットツリーに使用されるサンプルを更新するために使用されてよい。いくつかの実施形態ではランダムな更新ポリシを選択してよく、このポリシでは、任意の所与の観測記録がサンプルに保持されている確率は、サンプルが最初に構成された後に到着する任意の他の観測記録の確率に等しい。他の実施形態では時間加重サンプル更新アルゴリズムを使用してよく、このアルゴリズムでは、所与の観測記録が保持される確率が経時的に減少する、つまり、一般的に、新しい観測ほどサンプルに組み込まれる可能性が高い。いくつかの実施形態では、他の加重サンプル更新ポリシ（例えば、時間的な加重ではなくクライアントが割り当てた加重に基づき、挿入確率が記録に割り当てられる）を使用してよい。所与の観測記録を特定のサンプルに挿入することが決定されると（サンプルサイズを変更しないように、選択された観測記録の削除を伴うこともある）、様々な実施形態では、サンプルのランダムカットツリーを最初から再構築する必要のないノード挿入技法が利用され得る。代わりに、係る挿入中にいくつかのサブツリーを移動させ、いくつかの葉以外のノードの境界ボックスを変更してよい。少なくとも１つの実施形態では、この効率的な更新アルゴリズムは、偽の挿入動作中に及び真の挿入中にも潜在的な挿入位置を識別するために使用され得る。偽の挿入の場合はツリーへの変更が保存されず（例えば、永続的になる）、真の挿入の場合は変更が保存される点において、偽の挿入は真の挿入と異なり得る。確率的サンプル更新アルゴリズムにより、結果的に所与の観測記録についてツリーを更新しないという決定が行われた場合、偽の挿入中に行われたツリーへの変更は、様々な実施形態において破棄され得る。アルゴリズムにより結果的にツリーを更新する決定が行われた場合、偽の挿入に対応する変更は永続的になるだろう。
【００５１】
いくつかの実施形態で使用される効率的な挿入アルゴリズムは、以下の通り説明され得る。記録またはポイントｐを挿入するには、ランダムカットツリーのルートから開始して、ｐを含む境界ボックスを計算する。ｐが古い境界ボックス内にある場合、境界ボックスは変更されない。そして、ｐが含まれないときと同じように、ｐの挿入に関して同じランダム分割決定（つまり、属性選択及び分割値選択）を行う。ｐの追加によって境界ボックスが変化する場合、（例えば、前述の範囲ベースの分割属性選択及びランダム分割値選択を使用して）新しいランダム分割決定が行われる。この新しい分割は、同じノードで分割が以前に実行された属性とは異なる属性に関して行われてよい。例えば、境界ボックスＢＢ１を有する所与のノードＮ１において、以前の属性Ａｔｔｒ１の値に分割が行われ、新しいノードｐがＢＢ１の範囲外となる場合、（例えば、様々な属性の範囲を考慮して）別のランダム分割計算を行ってよく、異なる分割属性Ａｔｔｒ２を選択してよい。新たに計算された分割が古い境界ボックスの範囲内となる場合、新たに計算された分割は無視され、ｐは元のツリーに（ｐを含む分割と一致する子ノードの方向に）下がる。新しい分割値が古い境界ボックスの範囲外となる場合、ｐを１つの子にし、別の子は現在のノード（分割されているノード）になる。その後、境界ボックスをルートまで調整する。上に要約した挿入アルゴリズムのステップは、より正式には以下の通り説明され得る。
【００５２】
アルゴリズム挿入ステップ
１．観測記録Ｓ’及び対応するランダムカットツリーＴのセットがある。各観測記録はｄ次元または属性を有する。新しい観測記録ｐを挿入して変更したツリーＴ’を生成する。
２．Ｓ’が空の場合、ｐをルートとして含む単一ノードのツリーに戻る。
３．それ以外の場合、Ｓ’は境界ボックスＢ（Ｓ’）＝［ｘ1l，ｘ1h］ｘ［ｘ2l，ｘ2h］ｘ…［ｘdl，ｘdh］を有し、ここで上付き文字ｌ及びｈは対応する属性の低値及び高値を表す。
４．全ての次元ｉに、ｙil＝ｍｉｎ｛ｘil，ｐi｝及びｙih＝ｍａｘ｛ｘih，ｐi｝を実行する。
５．０〜Σi（ｙih−ｙil）の間の乱数を選択する。
６．この値ｒは範囲ベースの分割決定に相当する。
７．ｒベースの分割がＳ’及びｐを分離する場合、変更されたツリーＴ’の第１の分割として使用する。新しい葉以外のノードをツリーＴ’に追加し、葉以外のノードの１つの子はｐを表すノードであり、他のノードはｒを使用して分割されたノードである。
８．ｒベースの分割がＳ’及びｐを分離しない場合、ｒベースの分割を破棄し、ツリーを下方向に走査し、Ｓ’で既存のカットを行う。この選択された子ノードは異なる境界ボックスＢ（Ｓ’’）を表す。手順はＢ（Ｓ’’）で表される。
９．いずれかの場合（つまり、ｒベースの分割によるＳ’及びｐの分離の有無）では、Ｔ’の境界ボックスを必要に応じて調整する。
【００５３】
図１０は、少なくともいくつかの実施形態による、ツリーに使用されるサンプルに新しい観測記録を挿入した結果として潜在的に生成され得るランダムカットツリー例を示す。図示のシナリオでは、観測記録がそれぞれ単一の整数属性を含むデータセットに対応するランダムカットツリーが構築される。図１０では、挿入動作１００４によって生じる可能性のある１つの結果が示されており、この動作は属性値４０を有する記録を元のツリー１００２に挿入することに対応する。ツリーのノードのサブセットのみが示され、下位レベルのサブツリーＳｔ１、Ｓｔ２、Ｓｔ３及びＳｔ４を表す三角形が示されている。各ツリーノードの境界ボックスに対応するそれぞれの属性範囲（例えば、ルートノードの場合は［０，１００］）が示され、分割値は、子ノードに繋がるエッジに使用されるラベルに示されている。例えば、分割属性値５０がルートノードで使用されており、ルートからの１つのエッジは「＜＝５０」にラベル付けされ、別のエッジは「＞５０」にラベル付けされる。
【００５４】
挿入アルゴリズムは、１次元の境界ボックス［０，１００］を有するツリー１００２のルートで開始する。挿入されることになる記録は４０の値を有し、これはルート境界ボックスの範囲内にあるため、ルートノードに関して行われるランダムな分割が結果的にルートにおける変化を生じさせ得ることはない。ルートの子ノードのうちの１つが走査のために選択される。図１０では、ノード［０，３０］は、挿入されることになる値４０が該当する分割値域（＜＝５０）に対応するため選択される。ノード［０，３０］で表される最大値（３０）は、挿入されることになるノードの値４０よりも小さいため、［０，４０］の範囲でランダム分割が行われる。このランダム分割（図示の例では３５であり、エッジラベル「＜＝３５」及び「＞３５」によって示される）は、たまたまこの範囲内［３０，４０］にある、つまり、［０，３０］をルートとするサブツリーと新しいノード［４０］を分離する。その結果、新しい葉以外のノード１０３０が、代替的な結果ツリー１００５内の元の［０，３０］ノードを置換する。この新しい葉以外のノード１０３０Ａの１つの子は［４０］を表す葉ノードであり、この新しいノードの他の子は元のノード［０、３０］であり、これはその子孫ノードとともに１レベル下に移動する。新しい葉以外のノード１０３０の境界ボックス値は、その子孫が０〜４０の間の範囲に及ぶことを示すために［０，４０］に設定される。
【００５５】
図１０の例に示す通り、挿入アルゴリズムはツリー全体を再構成する必要はない。代わりに、ノードのサブセットをグループとして（例えば、ツリーの下位レベルに）移動させてよく、新しい葉ノードを元のツリーに追加してよく、新しい葉ノードを各挿入に追加してよい。このような挿入手法は、新しいノードのほとんど（ほとんどのノードがアウトライアではないと仮定して）が結果的にツリーのより深い地点で変更されるだけであるため、ツリー全体を再作成するよりもはるかに安価であり得る。
【００５６】
前に述べた通り、少なくともいくつかの実施形態では、ツリーが更新されると、範囲ベースのランダムカットツリーに対応するサンプルサイズが一定に保たれてよく、これは、各挿入が対応する削除を伴い得ることを意味する。異なる実施形態では、削除は挿入の前または後のいずれかで行われてよい。図１１は、少なくともいくつかの実施形態による、ツリーに使用されるサンプルから観測記録を削除した結果として生成されるランダムカットツリーへの変更例を示す。削除アルゴリズムは、以下のように要約され得る。ツリーＴ及び削除される記録ｐを考慮して、ｐに対応する葉ノードＬＮを見つける。その後、その葉ノードＬＮが削除され、ＬＮの兄弟ノードがツリーの１つ上のレベルに上がり、元々ＬＮの親ノードであったノードを置換する。ルートに向かう経路上にあるノードの境界ボックスを調整してよい。
【００５７】
元のツリー１２０２では、削除動作１２０４の対象ノードに対応する葉ノードは、親ノード［４０，８０］及び兄弟ノード［７０，８０］を有する。削除アルゴリズムに従って、葉ノード［４０］は削除され、兄弟ノードは１つ上のレベルに上がる。次に、兄弟ノードの新しい位置とルートとの間の経路が走査され、対応する境界ボックスが更新される。例えば、元のツリーにある境界ボックス［４０，１００］を有するノードは、変更された削除後のツリー１２０３の［７０，１００］に更新される。図１０及び図１１に示す実施形態では、挿入も削除もツリーの再構築を必要としない。代わりに、各挿入または削除動作は、通常、少数のノードにしか影響を与え得ない。
【００５８】
機械学習サービス
いくつかの実施形態では、上記のストリーミングデータのアウトライア検出アルゴリズムは、前に述べた通り、プロバイダネットワークの機械学習サービスで実施してよい。図１２は、少なくとも一部の実施形態による、ストリーミングデータ及び静的データセットの分析を行い得る機械学習サービスを示す。システム１３００は、上述のアウトライア検出アルゴリズムの計算のためにサーバプール１３８５からサーバを利用し得るリアルタイム分析マネジャ１３８１を含む、拡張可能な機械学習サービスの様々なコンポーネントを含む。いくつかの実施形態では、機械学習サービスはプロバイダネットワークで実装されてよく、機械学習サービスに使用されるリソースは、いくつかの異なるデータセンタ間で分散されてよい。
【００５９】
図示の実施形態では、様々なタイプの分析のための入力データは、少なくとも２つのタイプのソース、つまり、バッチデータレポジトリ１３３０及びストリーミングデータソース１３３１から取得され得る。リアルタイム分析マネジャ１３８１に加えて、機械学習サービス（ＭＬＳ）は、図示の実施形態において、要求ハンドラ１３８０、知識ベース１３２２及びアーティファクトリポジトリ１３２０を備え得る。知識ベース１３２２は、様々なデータセットのアウトライア検出アルゴリズム（及び他のアルゴリズム）を使用する前例で取得された事柄を表す入力が増加する集合を表してよく、アウトライア検出のためのアルゴリズムパラメータの選択など、リアルタイム分析マネジャ１３８１によって行われる決定のいくつかを誘導するために使用され得る。前に述べた通り、生成すべきランダムカットツリーの数、対応するサンプルのサイズ、サンプル更新パラメータなど、いくつかのパラメータ値を所与のアウトライア検出要求に対して選択する必要があり得る。アーティファクトレポジトリ１３２０は、アウトライア検出動作の中間結果及び／または最終結果、選択されたパラメータの値などを記憶するために使用されてよい。
【００６０】
１つ以上のプログラマチックインターフェース１３６１のセットは、図示の実施形態におけるクライアント１３６４との相互作用のために機械学習サービスで実装されてよい。インターフェースは、例えば、１つ以上のウェブベースのコンソールまたはウェブページ、アプリケーションプログラミングインタフェース（ＡＰＩ）、コマンドラインツール、グラフィカルユーザインターフェース（ＧＵＩ）などを含み得る。インターフェース１３６１を使用して、クライアント１３６４は、例えば、指定されたストリーミングデータソース１３３１から記録を取得することができるストリームの記録にアウトライア検出を行う要求を送信し得る。データソースは、例えば、ネットワークアドレス、データベースアドレス及び／またはストレージデバイスアドレスなどのアクセス情報を提供することによって、識別され得る。いくつかの実装では、ＳＱＬベースのプログラマチックインターフェースをプログラマチックインターフェース１３６１に含めてよく、クライアントは、馴染みのある使い易いインターフェースを使用してアウトライア検出要求（及び係る要求に対応する表示結果）を送信することができる。
【００６１】
概して、ストリームのデータ記録は、カテゴリ属性、テキスト属性、ブール属性及びその他などの数値属性及び非数値属性を含む多数の属性を備え得る。いくつかの実施形態では、アウトライア検出は、数値属性のみを備えるストリームに限定されてよい。つまり、ストリームの記録に非数値属性が含まれている場合、ＭＬＳはアウトライア検出を実行する要求を拒否してよい。他の実施形態では、アウトライア検出アルゴリズムが適用される前に、（例えば、入力記録ハンドラ１３６０及び／または特徴プロセッサ１３６２において）所与のストリームの未処理のデータ記録が事前処理されてよく、係る事前処理は、ビニングまたは他の類似の手法を使用して、少なくともいくつかの非数値属性から派生した数値属性を生成することを含み得る。係る実施形態では、アウトライア検出は、ストリームの未処理のデータ記録ではなく、事前処理されたデータセットに行われてよい。他のタイプの事前処理は、属性値の正規化、データ記録のグループまたはサブシーケンスを結合記録に集計すること及びその他など、様々な実施形態で実装してもよい。
【００６２】
インターフェース１３６１を介してＭＬＳとプログラム的に相互作用するときに、クライアント１３６４は、様々な実施形態において、アウトライア検出を行うときに考慮され得る多数の設定または要件を示してよい。例えば、クライアントは、アウトライア検出アルゴリズムの１つ以上のパラメータの好適な値（構築するランダムカットツリーの数、サンプルのサイズなど）及び／またはＭＬＳで使用される閾値を示し、報告する結果を決定してよい。１つのクライアント１３６４は、スコアが生成される全てのデータ記録についてのアウトライアスコアを（例えば、属性値と共に）表示することを望むことがあり、別のクライアントは、システムが定義したか、またはクライアントが指定した閾値を超えるアウトライアスコアを有する記録について通知されることのみを望むことがある。クライアントは、記録（例えば、ツリーに使用されるサンプル内で古い記録を新しい記録に置換するかどうか、及びその方法を決定するために使用される、時間的な置換パラメータ）または個々の属性に加重を割り当ててもよい。いくつかの実施形態では、（例えば、範囲ベースの選択に加えて、またはその代わりに）分割属性を選択するために、クライアントの観点から異なる属性の主観的重要性を示し得る属性固有の加重を使用してよい。一部のクライアント１３６４は、単にストリーミングデータのソースを示し、分析及び報告の決定をＭＬＳに任せてよい。関係する統計に精通しているか、またはストリーム記録が収集されている主題または分野の専門家である他のクライアントは、アウトライア検出の決定に関してより詳細な指針または設定を提供してよい。
【００６３】
ＭＬＳの管理プレーンまたは制御プレーン部分は、クライアント要求１３１１を受け入れる要求ハンドラ１３８０を含んでよく、クライアント要求がリアルタイム分析またはバッチモード分析に関係するかどうかを判定し、要求された分析の性質に応じて異なる動作を行う。ストリーミングデータのアウトライア検出要求などのリアルタイム要求は、リアルタイム分析マネジャ１３８１に渡してよい。バッチモード動作の場合、要求ハンドラは、矢印１３１２で示す通り、対応するジョブオブジェクトをバッチジョブ待ち行列１３４２に挿入してよい。一般的に、ＭＬＳの制御プレーンは、（要求ハンドラ、リアルタイム分析マネジャ、作業負荷分配戦略セレクタ、１つ以上のジョブスケジューラ、指標コレクタ及び他のサービスとのインターフェースとして機能するモジュールを含む）複数のコンポーネントを含むことがあり、総称してＭＬＳマネジャと呼ばれることもある。ＭＬＳのデータプレーンは、例えば、少なくともプール（複数可）１３８５のサーバのサブセット、入力データセットを記憶するために使用されるストレージデバイス、中間結果または最終結果（これらの一部は、ＭＬＳアーティファクトレポジトリの一部であり得る）ならびにクライアント入力データ及び結果を転送するために使用されるネットワーク経路を含んでよい。
【００６４】
所与のバッチジョブオブジェクトは、プログラマチックインターフェース１３６１の呼び出しの結果として行われるべき１つ以上の動作を示すことがあり、所定のジョブのスケジューリングは、場合によっては、少なくとも以前に生成されたジョブの動作のサブセットの完了成功に応じる場合がある。一実施形態では、クライアントは、バッチモードで（例えば、リアルタイムの代わりに、またはリアルタイムで行うアウトライア分析に加えて）、ストリームの記録にアウトライア検出を行うことを要求してよい。係るシナリオでは、矢印１３３２で示すように、ストリームデータの一部または全てを、バッチデータレポジトリに記憶してよい。バッチモードのアウトライア検出が行われる前に、場合によっては、所与のストリームを閉鎖してさらに記録してよい。他の場合では、保存された古いストリーム記録のバッチモード分析を、リアルタイム分析と同時に新たな到着データに行ってよい。各バッチモード分析は、図示の実施形態の対応するジョブオブジェクトによって表されてよい。
【００６５】
少なくともいくつかの実装において、ジョブ待ち行列１３４２は、ジョブが待ち行列から削除されるためには所与のジョブの依存性要件が満たされなければならないというさらなる制約付きで、先入れ先出し（ＦＩＦＯ）待ち行列として管理されてよい。いくつかの実施形態では、いくつかの異なるクライアントに作成されたジョブが、単一の待ち行列内に入れられてよく、他の実施形態では、複数の待ち行列が維持されてよい（例えば、使用されるプロバイダネットワークの各データセンタ内に１つの待ち行列、またはＭＬＳ顧客当たり１つの待ち行列）。図示の実施形態において、要求１３１１の送信に関して非同期的に、依存性要件が満たされた次のジョブは、矢印１３１３に示されるように、ジョブ待ち行列１３４２から削除されてよく、作業負荷分配戦略を含む処理計画は、ジョブのために識別されてよい。前に述べた通り、ＭＬＳ制御プレーンのコンポーネントでもあり得る作業負荷分配戦略層１３７５は、ジョブのより低いレベルの動作が１つ以上のコンピューティングサーバ（例えば、プール１３８５から選択されたサーバ）間で分配される方式、及び／またはジョブのために分析もしくは操作されたデータが、１つ以上のストレージデバイスもしくはサーバ間で分配される方式を判定してよい。矢印１３３５で示すように、いくつかの実施形態では、例えば、アウトライア検出アルゴリズムのために使用するサーバセットの識別に役立てるために、作業負荷分散戦略層１３７５はさらに、リアルタイム分析マネジャ１３８１によって利用されてよい。例えば、アウトライア検出アルゴリズムの少なくとも１つの実施形態の部分は並列的な方式で実装されてよい（例えば、使用されているランダムカットツリーの数に少なくとも部分的に基づいて及び／またはプール１３８５で利用可能な空のサーバの数に基づいて、並列的に使用するサーバ数を選択する）。いくつかの実装では、それぞれの実行プラットフォームにおいて様々なツリーを処理してよい。処理計画が生成され、バッチジョブまたはリアルタイム分析のために利用されるリソースの適切なセットが識別された後、識別されたリソースに動作がスケジュールされてよい。いくつかのバッチジョブまたはリアルタイム分析の結果は、いくつかの実施形態では、矢印１３４７によって示されるように、レポジトリ１３２０内のＭＬＳアーティファクトとして記憶されてよい。
【００６６】
図１２に示す実施形態では、クライアント１３６４は、例えば、読み取り要求１３１８を送信することによって、リポジトリ１３２０に記憶されたアーティファクトの少なくともサブセットを見ることができ得る。リアルタイムストリーム分析１３９５の結果（例えば、様々なストリームデータ記録のアウトライアスコア）は、いくつかの実施形態では、インターフェース１３６１を介してサーバプール１３８５からクライアント１３６４に利用可能になり得る。図示の実施形態では、クライアントから受信した入力に基づいて、知識ベース１３１７に入力を追加してよく、矢印１３１７で示すように、少なくともいくつかの実施形態では、クライアントは知識ベース入力を見ることもできる。いくつかの実施形態では、特徴処理仕様のための比較的簡易な言語がサポートされてよく、ＭＬＳクライアントは、データセットへの適用を望む様々な特徴処理ステップを示す「レシピ」を作成することができる。係るレシピは、テキスト形式で指定されてよく、次いで必要に応じて、例えば、特徴プロセッサ１３６２などで、異なるリソースセットの異なるデータセットで再使用することができる実行可能な形式にコンパイルされてよい。アルゴリズムライブラリ１３６３は、様々なタイプの回帰及び分類アルゴリズム、ニューラルネットワークアルゴリズム及び確率的勾配降下アルゴリズムなどのアウトライア検出技法に加え、多様な機械学習、統計及びデータ分析アルゴリズムを含んでよい。少なくとも一実施形態では、ＭＬＳは、入力記録処理、機能処理のため、またはＭＬＳによって元々サポートされている追加の機械学習アルゴリズムを実装するために、例えば、クライアントが自身のモジュール（ユーザ定義機能として定義され得る）を提供または登録し得るよう、拡張可能に設計され得る。
【００６７】
いくつかの実施形態では、アウトライア検出のための上記のランダムカットフォレストベースの技法は、必ずしもストリームの一部ではないデータセットに適用され得ることに留意されたい。例えば、任意の大型または小型のデータセット内のアウトライアが特定されてよく、あるいは技法を使用して静的データセットの様々なデータ記録に対するアウトライアスコアを計算してよい。さらに、様々な実施形態では、技法は必ずしも機械学習サービスまたはストリーム分析サービスで実施される必要はなく、代わりに係るネットワークにアクセス可能なサービスと提携していない１つ以上のコンピューティングデバイスで実施されてよい。一実施形態では、ランダムカットフォレストベースのアウトライア検出アルゴリズムは、プロバイダネットワークまたはクラウドベースのリソースを利用することなく実装されてよい。別の実施形態では、ランダムカットフォレストベースのアウトライア検出アルゴリズムは、電子商取引ウェブサイトの動作またはプロバイダネットワークのリソース使用レベルに関連する指標を継続的に収集するツールなど、大規模な監視ツールのサブコンポーネントとして実装されてよい。例えば、電子商取引ウェブサイトの場合、１分間あたりの様々な製品の視聴者数、１分間あたりのカタログに追加される製品数等などの指標記録は、アウトライア検出が行われるストリーミングデータを形成してよい。プロバイダネットワークのリソースの使用の場合、連続ベースで収集され、アウトライアのために分析されるストリーミングデータは、特定のストレージサービスにおける１分間当たりのストレージ書き込み回数または読み出し回数、様々な物理サーバまたは仮想サーバからの１分間当たりのネットワーク要求数、様々なサーバで選択された間隔で収集されたＣＰＵ利用率及びその他などの指標が含まれ得る。
【００６８】
アウトライア検出方法
図１３は、少なくともいくつかの実施形態による、ストリーミング観測記録のためのアウトライア検出アルゴリズムを実施するために実行され得る動作の態様を示す。要素１４０１に示す通り、指定されたストリームの記録にアウトライア分析または検出を行うべきであるという決定は、例えば、クライアントから受信した要求に基づいて、または単に分析サービスによって提供されたストリーミングデータのデフォルト統計分析の一部として行われ得る。アウトライア検出アルゴリズムのいくつかのパラメータの値は、例えば、クライアントによって示される設定、ストリームが分析されるべき分析サービスまたは機械学習サービスの知識ベース入力を基に、またはデフォルト設定を使用して、選択され得る（要素１４０４）。パラメータには、例えば、初期の範囲ベースのランダムカットツリーを構築するために収集される基準セットの記録サイズ、構築されるツリーの数、ツリーに使用すべきサンプルサイズ、アウトライアスコア生成のための距離及びスパース性パラメータ、サンプル更新アルゴリズムパラメータ（例えば、重み付けされていないランダム選択を使用してサンプルメンバを置換すべきかどうか、または、どの記録をサンプルに含めるべきかを決定するときに、いくつかの記録を他の記録よりも重み付けすべきかどうか）、個々の属性（例えば、クライアントの視点から記録を特徴付ける際に、いくつかの属性の他の属性に対する相対的な重要性を示す）またはデータ記録、アウトライアスコア／状態を報告するための通知閾値などに割り当てられる加重などを含み得る。
【００６９】
ストリームのデータ記録の基準セットを収集してよく（要素１４０７）、基準セットのそれぞれのサンプルから範囲ベースのランダムカットツリー（ＲＣＴ）の初期セットを生成してよい（要素１４１０）。ツリーを構築するために確率的反復分割戦略を使用してよく、この戦略では、ツリーノードの境界ボックスは、選択された次元または属性に沿って様々な段階で分割されてよく、所与の段階での次元または属性は、その段階で分割すべき記録内にある属性値の範囲に少なくとも部分的に基づいて選択されてよい。例えば、ストリーム記録の集合を分割するときに２つの属性Ａｔｔｒ１とＡｔｔｒ２の間の選択が行われ、Ａｔｔｒ１値が集合の１００〜２００の間で変化し、Ａｔｔｒ２値が１０〜２０の間で変化する場合、Ａｔｔｒ１を分割属性として選択する確率を、（２００−１００）／（（２００−１００）＋（２０−１０））または１００／１１０に設定してよい。他の実施形態では、属性範囲の他の機能を使用して分割属性を選択してよい。例えば、所与の属性を選択する確率は、その範囲の対数に比例し得る。いくつかの実施形態では、例えば、ツリー内のノードの深さ、ノードの相対的な分離などに基づいて、それぞれのアウトライアスコアをツリーの初期セットのノードに割り当ててよい。
【００７０】
ツリーの初期セットが構築された後、それらは、ストリームの以前には表示されなかった新しいデータ記録に関するアウトライア検出を行うために使用されてよい。現在のツリーのセットで表されていないストリームＯＲ−ｎｅｗの次の記録が受信されると（要素１４１３）、２つのタイプの動作、つまり、（ａ）アウトライアスコア計算（ツリーの一部または全てへの「偽の」挿入を伴い得る）及び（ｂ）ツリーの一部または全てへの実際のノードの挿入及び削除を伴い得るサンプル更新を行ってよく、確率的ツリー更新アルゴリズムに従って行われ得る。これらの２つのタイプの動作が行われる順序は、様々な実施形態に応じて変化してよく、または２つの種類の動作が並行して行われてよい。図１３に図示する実施形態では、各ツリーは、一度に１つずつ考慮されてよく、所与のツリーに関して局所的なアウトライアスコアがＯＲ−ｎｅｗに割り当てられてよく、そのツリーに対してサンプル更新を行うべきかどうかに関する決定を行ってよく、次いで、ＯＲ−ｎｅｗを表す新しいノードを挿入する決定が行われた場合には、ツリーを更新してよい。他の実施形態では、ツリーを更新するかどうかに関する決定は、局所的なアウトライアスコアが計算される前に行われ得るため、実際のまたは真の挿入が行われない場合にのみ、「偽の」挿入が必要となり得る。
【００７１】
ＯＲ−ｎｅｗに関して処理されていない次のツリーＲＣＴ−ｊが選択された後（要素１４１６）、ＲＣＴ−ｊのために、「偽の」挿入で決定されたＲＣＴ−ｊのＯＲ−ｎｅｗを表すノードの潜在的な位置に基づいて、ＯＲ−ｎｅｗに対する局所的または単一ツリーのアウトライアスコアを計算してよい（要素１４１９）。偽の挿入はさらに、１つ以上のランダムな分割動作を伴ってよく、分割属性は、以前に述べたその値域に少なくとも部分的に基づいて選択される。図示の実施形態では、「偽の」挿入によって生じる変更は保存できないか、または永続的になるという点において、「偽の」挿入は真の挿入とは異なり得る。局所的なアウトライアスコアは、いくつかの実施形態では、潜在的な挿入位置の１つ以上の特徴の組み合わせ、例えば、ツリー内の対応するノードの深さ、隣接ノードのスパース性（例えば、潜在的に挿入されたノードに関して共通する親または祖先を有するノード）、及び／または潜在的に挿入されたノードからの他のノードの最小距離に基づき得る。少なくとも１つの実施形態では、必ずしも葉ノードまでツリーを走査することなく、または潜在的に挿入されるノードの正確な位置を決定することなく、局所的またはツリーレベルのアウトライアスコアをＯＲ−ｎｅｗに対して生成してよい。例えば、スコアは、ＯＲ−ｎｅｗを表すノードが閾値よりも深い深さに挿入されることを（偽の挿入中に）決定することに単に基づいて割り当てられてよい。一実装では、例えば、深さ１０の閾値が使用されてよく、ツリーの１０のレベルが走査されていても、葉ノードが挿入されていない記録には、単純に低いアウトライアスコアが割り当てられてよい。
【００７２】
確率的ストリームサンプル更新アルゴリズムは、ＲＣＴ−ｊへの実際の挿入をＯＲ−ｎｅｗに対して行うべきかどうか（要素１４２２）、つまり、ＲＣＴ−ｊに対応するサンプルがＯＲ−ｎｅｗを含むべきかどうかを決定するために呼び出され得る。前に述べた通り、いくつかの実施形態では、サンプル内にＯＲ−ｎｅｗなどの所与の記録が含まれる確率は、記録の到着時間または到達シーケンスとは無関係であり得るが、他の実施形態では、新しい記録であるほど古い記録よりもサンプル内に含まれる高確率が割り当てられ得る。ＯＲ−ｎｅｗを含む決定が行われた場合、削除される記録を表す犠牲ノードが識別されてよく、サンプルサイズを変更しないようにするために対応する削除と共に、真の挿入（これにより、結果的に以前に識別された潜在的な挿入位置にノードが挿入され得る）が行われてよい（要素１４２５）。挿入が削除に対して行われる順序は、様々な実装形態によって変わり得る。確率的サンプル更新アルゴリズムが、ＲＣＴ−ｊが更新されていないことを示し（要素１４２２に対応する動作においてさらに検出される）、追加のツリーが検査されたままである場合（要素１４２８で検出される）、要素１４１６〜１４２８に対応する動作は次のツリーに対して繰り返されてよい。全てのツリーがＯＲ−ｎｅｗに関して検査された後、全体的なアウトライアスコアはツリー毎のスコアから決定されてよい（要素１４３１）。例えば、いくつかの実装では、ツリー毎のスコアの算術平均、幾何平均または中央値を使用して、全体的なアウトライアスコアを生成してよい。スコアは、永続リポジトリに記憶されてもよい、及び／またはクライアントに提供されてもよい。クライアントの報告または通知指標を基に、クライアントにアウトライア検出が行われている。いくつかの実施形態では、生成されたアウトライアスコアに関するフィードバックをクライアントから取得してよい。例えば、クライアントが、ストリーミングデータが収集されている分野の専門知識に基づいて、所与の記録に割り当てられた高いアウトライアスコアに賛同しない場合、クライアントは意見の不一致を示し得る（おそらく説明を提供する）。分析品質の係るフィードバックまたは評価は、いくつかの実施形態では、知識ベースに記憶されてよい、及び／またはアウトライア検出アルゴリズムのパラメータを変更するために使用されてよい。少なくとも１つの実施形態では、クライアントが全てのデータ記録に対してアウトライアスコアを必ずしも生成することを望まない場合がある。その代わりに、クライアントは、指定された観測値に対してのみアウトライアの結果を提供するように要求し得る。係るシナリオの１つでは、アウトライア検出を担う分析サービスは、やはり上述のランダムカットツリーを構築及び更新し得るが、特定の要求が受信された記録にのみスコアを割り当て得る。
【００７３】
様々な実施形態では、図１３に示す動作のいくつかは、図に示した順序とは異なる順序で実施されてよいか、または連続的ではなく並列的に行われてよいことに留意されたい。例えば、（マシン学習サーバなどの）実行プラットフォームの十分なセットが利用可能であると仮定して、いくつかの実施形態では、所与のツリーに関連する計算を、異なるツリーに関連する計算と並列的に行ってよい。追加的には、図１３に示す動作のいくつかは、１つ以上の実装に必要なくなり得る。
【００７４】
使用事例
ストリーミングデータ記録に迅速かつ効率的にアウトライア検出を行う上記の技法は、様々な環境において有用であり得る。高速で到着する記録内で異常または例外的なデータを識別することは、不正検出、侵入検出、ハードウェアシステム、電化製品または自動車及びその他などの潜在的な故障への事前対応にとって不可欠であり得る。小売業者は、述べたアウトライア検出アルゴリズムを使用して、受注率の低下を分離し、それに応じて対応することができ得る。多数の健康関連アプリケーションはさらに、例えば、心臓発作前の例外的な心臓の挙動、糖尿病などの疾患が重症になる前の例外的な血液化学レベル及びその他を識別するなど、係る技法の恩恵を得ることがある。機械学習サービスまたはストリーム分析サービスが実装されるプロバイダネットワークのリソースを使用することにより、大量のコンピューティングリソースを柔軟な方式でアウトライア検出に専念させることができ得、これまでの経験から得た知識を共有して後続のアウトライア分析で得られる結果を改善することができ得る。いくつかの場合、アウトライア検出アルゴリズムは、電子商取引ウェブサイト及び／またはプロバイダネットワークに関連する大型の監視設備またはツールのサブコンポーネントとして実施されてよい。係るツールで検出されたアウトライアは、例えば、リソースの負荷または非応答サービスなどの潜在的に厄介な状況に対して迅速な（さらには事前の）応答を生成するのに役立ち得る。
【００７５】
例示的なコンピュータシステム
少なくともいくつかの実施形態では、アウトライア検出（例えば、リアルタイム分析マネジャ、実行プラットフォーム及び機械学習サービスの他のコンポーネント、またはストリーム管理及び分析システムの様々なコンポーネントを含む）のための上記の１つ以上の技法を実装するサーバは、１つ以上のコンピュータアクセス可能媒体を含むか、または１つ以上のコンピュータアクセス可能媒体にアクセスするように構成される汎用コンピュータシステムを含み得る。図１４は、係る汎用コンピューティングデバイス９０００を示す。例示の実施形態では、コンピューティングデバイス９０００は、入力／出力（Ｉ／Ｏ）インターフェース９０３０を介して、システムメモリ９０２０（不揮発性及び揮発性メモリモジュールの両方を備えてよい）に連結される、１つ以上のプロセッサ９０１０を含む。コンピューティングデバイス９０００は、Ｉ／Ｏインターフェース９０３０に連結されるネットワークインターフェース９０４０をさらに含む。
【００７６】
様々な実施形態では、コンピューティングデバイス９０００は、１つのプロセッサ９０１０を含むユニプロセッサシステム、またはいくつかのプロセッサ９０１０（例えば、２つ、４つ、８つまたは別の好適な数）を含むマルチプロセッサシステムであってよい。プロセッサ９０１０は、命令を実行することが可能な任意の好適なプロセッサであってよい。例えば、様々な実施形態では、プロセッサ９０１０は、ｘ８６、ＰｏｗｅｒＰＣ、ＳＰＡＲＣもしくはＭＩＰＳ  ＩＳＡ、または任意の他の好適なＩＳＡなどの様々な命令セットアーキテクチャ（ＩＳＡ）のうちのいずれかを実装する、汎用または埋め込みプロセッサであってよい。マルチプロセッサシステムにおいて、プロセッサ９０１０の各々は、同じＩＳＡを一般的に実装し得るが、必ずしもそうでなくてもよい。いくつかの実装では、グラフィックス処理ユニット（ＧＰＵ）は、従来のプロセッサの代わりに、またはそれに加えて使用されてよい。
【００７７】
システムメモリ９０２０は、プロセッサ（複数可）９０１０によってアクセス可能な命令及びデータを記憶するように構成されてよい。少なくともいくつかの実施形態では、システムメモリ９０２０は、揮発性及び不揮発性部分の両方を備えてよく、他の実施形態では、揮発性メモリのみが使用されてよい。様々な実施形態では、システムメモリ９０２０の揮発性部分は、静的ランダムアクセスメモリ（ＳＲＡＭ）、同時性動的ＲＡＭまたは任意の他のタイプのメモリなどの任意の好適なメモリ技術を使用して実装されてよい。システムメモリの不揮発性部分（例えば、１つ以上のＮＶＤＩＭＭを備え得る）に関して、いくつかの実施形態では、ＮＡＮＤ−フラッシュデバイスを含むフラッシュベースのメモリデバイスが使用されてよい。少なくともいくつかの実施形態では、システムメモリの不揮発性部分は、スーパーキャパシタまたは他の電力貯蔵装置（例えば、バッテリ）などの電源を含んでよい。様々な実施形態では、メモリスタベースの抵抗ランダムアクセスメモリ（ＲｅＲＡＭ）、３次元ＮＡＮＤ技術、強誘電ＲＡＭ、磁気抵抗ＲＡＭ（ＭＲＡＭ）または様々なタイプの相変化メモリ（ＰＣＭ）のうちのいずれかが、少なくともシステムメモリの不揮発性部分に対して使用されてよい。例示の実施形態では、上記のそれらの方法、技法及びデータなどの１つ以上の所望の機能を実装するプログラム命令及びデータは、コード９０２５及びデータ９０２６として、システムメモリ９０２０内に記憶されるように示されている。
【００７８】
一実施形態では、Ｉ／Ｏインターフェース９０３０は、プロセッサ９０１０、システムメモリ９０２０、ネットワークインターフェース９０４０、または様々なタイプの永続的及び／または揮発性ストレージデバイスなどの他の周辺インターフェース間のＩ／Ｏトラフィックを調整するように構成されてよい。いくつかの実施形態では、Ｉ／Ｏインターフェース９０３０は、１つのコンポーネント（例えば、システムメモリ９０２０）からのデータ信号を、別のコンポーネント（例えば、プロセッサ９０１０）による使用に好適な形式に変換するように、任意の必要なプロトコル、タイミングまたは他のデータ変換を行なってよい。いくつかの実施形態では、Ｉ／Ｏインターフェース９０３０は、例えば、Ｌｏｗ  Ｐｉｎ  Ｃｏｕｎｔ（ＬＰＣ）バス、ペリフェラル・コンポーネント・インターコネクト（ＰＣＩ）バス規格またはユニバーサルシリアルバス（ＵＳＢ）規格の異形などの様々なタイプの周辺バスを通じて取り付けられるデバイスに対するサポートを含んでよい。いくつかの実施形態では、Ｉ／Ｏインターフェース９０３０の機能は、例えば、ノースブリッジ及びサウスブリッジなどの２つ以上の別個のコンポーネントに分割されてよい。また、いくつかの実施形態では、システムメモリ９０２０へのインターフェースなどのＩ／Ｏインターフェース９０３０の機能性のうちのいくつかまたは全ては、プロセッサ９０１０に直接組み込まれてよい。
【００７９】
ネットワークインターフェース９０４０は、データが、コンピューティングデバイス９０００と、例えば、図１〜図１３に例示されるような他のコンピュータシステムまたはデバイスなどの、ネットワーク（１つもしくは複数）９０５０に取り付けられる他のデバイス９０６０との間で交換可能になるように構成されてよい。様々な実施形態では、ネットワークインターフェース９０４０は、例えば、イーサネット（登録商標）ネットワークのタイプなどの任意の好適な有線または無線の一般的なデータネットワークを介した通信をサポートしてよい。追加的に、ネットワークインターフェース９０４０は、アナログ音声ネットワークもしくはデジタルファイバ通信ネットワークなどの電気通信／テレフォニネットワークを介した、ファイバチャネルＳＡＮなどのストレージエリアネットワークを介した、または任意の他の好適なタイプのネットワーク及び／またはプロトコルを介した通信をサポートしてよい。
【００８０】
いくつかの実施形態では、システムメモリ９０２０は、対応する方法及び装置の実施形態を実装するための図１〜図１３に関する上記のプログラム命令及びデータを記憶するように構成される、コンピュータアクセス可能な媒体の一実施形態であってよい。しかしながら、他の実施形態では、プログラム命令及び／またはデータは、異なるタイプのコンピュータアクセス可能媒体において、受信、送信または記憶されてよい。概して、コンピュータアクセス可能媒体は、Ｉ／Ｏインターフェース９０３０を介してコンピューティングデバイス９０００に連結される、磁気もしくは光媒体、例えば、ディスクもしくはＤＶＤ／ＣＤなどの非一時的記憶媒体またはメモリ媒体を含んでよい。非一時的コンピュータアクセス可能記憶媒体はまた、システムメモリ９０２０または別のタイプのメモリとして、コンピューティングデバイス９０００のいくつかの実施形態に含まれてよい、ＲＡＭ（例えば、ＳＤＲＡＭ、ＤＤＲ  ＳＤＲＡＭ、ＲＤＲＡＭ、ＳＲＡＭ等）、ＲＯＭなどの任意の揮発性または不揮発性媒体を含んでよい。さらに、コンピュータアクセス可能媒体は、送信媒体を含んでよいか、あるいは、ネットワーク及び／または無線リンクなどの通信媒体を介して伝送される電気、電磁気もしくはデジタル信号などの信号が、例えば、ネットワークインターフェース９０４０を介して実装されてよい。図１４に例示されるものなどの複数のコンピューティングデバイスのうちの一部分または全ては、様々な実施形態において、記載される機能性を実装するために使用されてよく、例えば、様々な異なるデバイス及びサーバ上で実行するソフトウェアコンポーネントが、機能性を提供するために協働してよい。いくつかの実施形態では、記載される機能性の一部分は、汎用コンピュータシステムを使用して実装されることに加えて、またはその代わりに、ストレージデバイス、ネットワークデバイスまたは特殊目的コンピュータシステムを使用して実装されてよい。「コンピューティングデバイス」という用語は、本明細書で使用される場合、少なくとも全てのこれらのタイプのデバイスを指し、これらのタイプのデバイスに限定されない。
【００８１】
結論
本開示の実施形態は、以下の条項を鑑みて説明することができる。
【００８２】
１．プロバイダネットワークに実装されるネットワークアクセス可能な分析サービスの１つ以上のコンピューティングデバイスを備えるシステムであって、前記１つ以上のコンピューティングデバイスは、プログラマチックインターフェースを介して、ストリーミングデータソースの観測記録にアウトライア検出を行う要求をクライアントから受信することであって、前記観測記録の個々の１つは複数の属性の値を備える、前記受信することと、前記ストリーミングデータソースの観測記録の基準セットを収集することと、観測記録の前記基準セットのそれぞれのサンプルに対応する複数のランダムカットツリーを生成することであって、特定のサンプルに対応する特定のランダムカットツリーの生成は、前記特定の属性の値域に少なくとも部分的に基づいて前記複数の属性のうちの特定の属性を選択することと、前記特定の属性に選択された分割値で前記特定のサンプルの少なくとも一部分を分割することとのうちの１つ以上の反復を備える、前記生成することと、前記基準セットに含まれていない特定の観測記録を取得することに応じて、前記特定のランダムカットツリーに関する前記特定の観測記録に対して識別された潜在的な挿入位置に少なくとも部分的に基づき、前記特定の観測記録のアウトライアスコアを計算することと、確率的ストリームサンプル更新アルゴリズムに従って、前記特定のランダムカットツリーに対応する前記サンプルが前記特定の観測記録を含むという判定に応じて、前記特定の観測記録を表すノードを前記特定のランダムカットツリーに挿入することと、前記アウトライアスコアが結果報告基準を満たすという判定に応じて、前記アウトライアスコアの基準指標を前記クライアントに提供することと、を行うように構成される、前記システム。
【００８３】
２．前記特定の観測記録を表す前記ノードを前記特定のランダムカットツリーに挿入するために、前記１つ以上のコンピューティングデバイスは、（ａ）前記特定のランダムカットツリーの前記ルートノードから開始する走査中に前記特定のランダムカットツリーの特定のノードに到達することであって、前記特定のノードは前記複数の属性の第１の属性に関して行われる以前のランダム分割計算に対応する属性値の境界ボックスを表す、前記到達することと、（ｂ）前記特定の観測記録が前記境界ボックスの範囲外にあると判定することに応じて、前記境界ボックスに表される前記複数の属性の選択された属性に関してランダム分割計算を行うことと、前記ランダム分割計算の前記結果に少なくとも部分的に基づいて、（ａ）前記特定の観測記録を表すノードが前記特定のノードの新しい子ノードとして追加されるか、または（ｂ）前記特定のノードの異なる子ノードを含む経路に沿って前記特定のランダムカットツリーの走査を継続するかどうかを決定するように構成される、条項１に記載のシステム。
【００８４】
３．前記１つ以上のコンピューティングデバイスは、前記特定のランダムカットツリーに対応する前記サンプルが前記特定の観測記録を含むという前記判定の後に、異なる観測記録を表す葉ノードを前記特定のランダムカットツリーから削除することと、前記葉ノードの前記親ノードを前記葉ノードの兄弟ノードに置換することと、前記兄弟ノードの前記新しい位置と、前記特定のランダムカットツリーの前記ルートノードとの間の前記経路上にある１つ以上のノードのそれぞれの境界ボックスを調整することと、を行うように構成される、条項１または２のいずれかに記載のシステム。
【００８５】
４．前記１つ以上のコンピューティングデバイスは（ａ）前記潜在的な挿入位置に対応するスパース性指標、（ｂ）前記潜在的な挿入位置及び前記特定のランダムカットツリーの１つ以上の他のノードに関して計算されたそれぞれの距離指標、または（ｃ）前記潜在的な挿入位置に対応する置換指標のうちの１つ以上に少なくとも部分的に基づいて前記アウトライアスコアを計算するように構成される、条項１〜３のいずれかに記載のシステム。
【００８６】
５．アウトライア検出を行うための前記要求は選択されたクエリ言語で定式化され、前記要求は、時間窓を示すパラメータを示し、前記時間窓に対して前記アウトライア検出が行われる、条項１〜４のいずれかに記載のシステム。
【００８７】
６．ストリームのデータ記録にアウトライア検出を行うことを決定することであって、前記データ記録の個々の１つは複数の属性の値を備える、前記決定することと、前記ストリームのデータ記録の基準セットのそれぞれのサンプルに対応する１つ以上のランダムカットツリーを生成することであって、特定のサンプルに対応する特定のランダムカットツリーの生成は、前記特定の属性の値域に少なくとも部分的に基づいて前記複数の属性の特定の属性を選択することと、前記特定の属性に選択された分割値で前記特定のサンプルの少なくとも一部を分割することとのうちの１つ以上の反復を備える、前記生成することと、前記基準セットに含まれていない特定のデータ記録を取得することに応じて、前記特定のデータ記録のために計算されたアウトライアスコアを記憶することであって、前記アウトライアスコアは前記特定のランダムカットツリーに関する前記特定のデータ記録に対して識別された潜在的な挿入位置に少なくとも部分的に基づき、前記アウトライアスコアは前記特定のランダムカットツリーを変更することなく計算される、前記記憶することと、を１つ以上のコンピューティングデバイスによって行うことを備える、方法。
【００８８】
７．（ａ）前記潜在的な挿入位置に対応するスパース性指標、（ｂ）前記潜在的な挿入位置及び前記特定のランダムカットツリーの１つ以上のノードに関して計算されたそれぞれの距離指標、または（ｃ）前記潜在的な挿入位置に対応する置換指標、のうちの１つ以上に少なくとも部分的に基づいて前記アウトライアスコアを計算することを前記１つ以上のコンピューティングデバイスによって行うことをさらに備える、条項６に記載の方法。
【００８９】
８．前記基準セットに含まれていない第２のデータ記録を取得することに応じて、前記特定のランダムカットツリーに関する前記第２のデータ記録に対して識別された潜在的な挿入位置に少なくとも部分的に基づいて、前記第２のデータ記録に対応する第２のアウトライアスコアを計算することと、サンプル更新アルゴリズムに従って、前記第２のデータ記録を前記特定のランダムカットツリーに挿入することと、選択されたデータ記録を前記特定のランダムカットツリーから削除することと、を前記１つ以上のコンピューティングデバイスによって行うことをさらに備える、条項６または７のいずれかに記載の方法。
【００９０】
９．前記サンプル更新アルゴリズムは、（ａ）ランダムサンプル更新アルゴリズム、または（ｂ）加重サンプル更新アルゴリズムのうちの１つ以上を備える、条項８に記載の方法。
【００９１】
１０．前記特定のランダムカットツリー内で前記第２のデータ記録の前記潜在的な挿入位置が閾値より深い深さにあるという判定に少なくとも部分的に基づいて、前記特定のランダムカットツリーを前記閾値より深い深さまで走査することなく、第２のデータ記録に第２のアウトライアスコアを割り当てることを、前記１つ以上のコンピューティングデバイスによって行うことをさらに備える、条項６〜９のいずれかに記載の方法。
【００９２】
１１．第２のストリームのデータ記録にアウトライア検出を行うことを決定することであって、前記第２のストリームの前記データ記録の個々の１つは第２の複数の属性の値を備える、前記決定することと、前記第２のストリームのデータ記録の第２の基準セットに対応する１つ以上のランダムカットツリーを生成する前に、前記第２の基準セットの少なくともサブセットを事前処理することであって、前記事前処理は、（ａ）前記第２の複数の属性の１つ以上の属性の未処理の値を正規化すること、（ｂ）前記第２の基準セットの複数のデータ記録の内容を集計することによって導出した記録を生成すること、（ｃ）選択されたスライド窓サイズを伴うシングリング技法を使用して、単一の属性から複数の次元のデータを生成すること、または（ｄ）変換関数を前記第２の複数の属性の特定の非数値属性の値に適用し、導出された数値を取得すること、のうちの１つ以上を備える、前記事前処理することと、を前記１つ以上のコンピュータデバイスによって行うことをさらに備える、条項６〜１０のいずれかに記載の方法。
【００９３】
１２．知識ベース入力に少なくとも部分的に基づいて、（ａ）前記基準セットのサイズ、（ｂ）前記特定のサンプルのサイズ、（ｃ）生成すべきランダムカットツリーの数、（ｄ）前記アウトライアスコアを割り当てるために使用される距離パラメータ（ｅ）前記アウトライアスコアを割り当てるために使用されるスパース性パラメータ、（ｆ）他の属性に対する前記特定の属性に割り当てる加重であって、前記アウトライアスコアは前記加重に少なくとも部分的に基づく、前記加重、（ｇ）前記特定のランダムカットツリーを更新するために使用される時間置換パラメータ、または（ｈ）アウトライアスコアに関する通知閾値であって、前記通知閾値は前記アウトライアスコアに関する通知を１つ以上の宛先に提供すべきかどうかを判定するために使用される、前記通知閾値、のうちの１つ以上を決定することを前記１つ以上のコンピューティングデバイスによって行うことをさらに備える、条項６〜１１のいずれかに記載の方法。
【００９４】
１３．（ａ）前記基準セットのサイズ、（ｂ）前記特定のサンプルのサイズ、（ｃ）生成すべきランダムカットツリーの数、（ｄ）前記アウトライアスコアを割り当てるために使用される距離パラメータ（ｅ）前記アウトライアスコアを割り当てるために使用されるスパース性パラメータ、（ｆ）他の属性に対する前記特定の属性に割り当てる加重であって、前記アウトライアスコアは前記加重に少なくとも部分的に基づく、前記加重、（ｇ）前記特定のランダムカットツリーを更新するために使用される時間置換パラメータ、または（ｈ）アウトライアスコアに関する通知閾値であって、前記通知閾値は前記アウトライアスコアに関する通知を１つ以上の宛先に提供すべきかどうかを判定するために使用される、前記通知閾値、のうちの１つ以上の指標をクライアントからプログラマチックインターフェースを介して受信することを前記１つ以上のコンピューティングデバイスによって行うことをさらに備える、条項６〜１２のいずれかに記載の方法。
【００９５】
１４．前記１つ以上のコンピューティングデバイスは、バッチモード動作及びリアルタイムストリーミング動作を実施する機械学習サービスの複数の実行プラットフォームを含み、永続的なレポジトリで前記ストリームの前記データ記録の少なくともサブセットを記憶することと、前記ストリームの少なくとも１つのデータ記録を受信する前に、前記ストリームの１つ以上のデータ記録のそれぞれのアウトライアスコアをクライアントに提供することと、前記それぞれのアウトライアスコアが提供された後に追加のデータ記録の受信を無効にするために前記ストリームを閉鎖することと、データ記録の前記サブセットにバッチモードアウトライア検出動作を行うことであって、前記バッチモードアウトライア検出動作は前記それぞれのアウトライアスコアが前記クライアントに提供された後に少なくとも１つのランダムカットツリーを更新することを備える、前記検出動作を行うことと、を前記１つ以上のコンピューティングデバイスによって行うことをさらに備える、条項６〜１３のいずれかに記載の方法。
【００９６】
１５．前記アウトライアスコアが閾値基準を満たすと判定することに応じて、前記アウトライアスコアを示す通知を、プログラマチックインターフェースを介してクライアントに提供することを前記１つ以上のコンピューティングデバイスによって行うことをさらに備える、条項６〜１４のいずれかに記載の方法。
【００９７】
１６．前記１つ以上のコンピューティングデバイスの少なくとも１つのコンピューティングデバイスは、（ａ）電子商取引ウェブサイトまたは（ｂ）プロバイダネットワークのうちの１つ以上に関連する監視ツールのサブコンポーネントを備える、条項６〜１５のいずれかに記載の方法。
【００９８】
１７．プログラム命令を記憶する非一時的なコンピュータアクセス可能な記憶媒体であって、１つ以上のプロセッサで実行されると、データセットのデータ記録の基準セットのそれぞれのサンプルに対応する１つ以上のランダムカットツリーを生成することであって、前記データ記録の個々の１つは複数の属性の値を備え、特定のサンプルに対応する特定のランダムカットツリーを生成することは、前記特定の属性の値域に少なくとも部分的に基づいて前記複数の属性の特定の属性を選択することと、前記特定の属性に選択された分割値で前記特定のサンプルの少なくとも一部を分割することとのうちの１つ以上の反復を備える、前記生成することと、前記データセットの特定のデータ記録を取得することであって、前記特定のデータ記録は前記基準セットに含まれない、前記取得することと、前記特定のデータ記録のために計算したアウトライアスコアを記憶することであって、前記アウトライアスコアの前記計算は前記特定のランダムカットツリーに関する前記特定のデータ記録に対して識別された潜在的な挿入位置に少なくとも部分的に基づく、前記記憶することと、を行う、前記非一時的なコンピュータアクセス可能な記憶媒体。
【００９９】
１８．前記命令は、前記１つ以上のプロセッサによって実行されたときに、前記潜在的な挿入位置と前記特定のランダムカットツリーのルートノードとの間のノード数に少なくとも部分的に基づいて、前記アウトライアスコアを計算する、条項１７に記載の非一時的なコンピュータアクセス可能な記憶媒体。
【０１００】
１９．前記１つ以上のランダムカットツリーは第２のランダムカットツリーを含み、前記命令は、前記１つ以上のプロセッサで実行されると、前記基準セットに含まれていない第２のデータ記録を取得することに応じて、確率的サンプル更新アルゴリズムに従って、前記第２のデータ記録に対応するノードを前記特定のランダムカットツリーに挿入し、第３のデータ記録に対応するノードを前記特定のランダムカットツリーから削除し、前記第２のデータ記録を表すノードが前記第２のランダムカットツリーに挿入すべきでないことを決定する、条項１７または１８のいずれかに記載の非一時的なコンピュータアクセス可能な記憶媒体。
【０１０１】
２０．前記命令は、前記１つ以上のプロセッサで実行されると、（ａ）前記第３のデータ記録に対応する前記ノードが前記特定のランダムカットツリーに追加されたときからの経過時間、または（ｂ）前記第３のデータ記録に対応する前記ノードが前記特定のランダムカットツリーに追加された後に前記特定のランダムカットツリーに追加されたノード数、のうちの１つ以上に少なくとも部分的に基づいて、前記特定のランダムカットツリーから削除する前記第３のデータ記録を選択する、条項１９に記載の非一時的なコンピュータアクセス可能な記憶媒体。
【０１０２】
２１．前記命令は、前記１つ以上のプロセッサで実行されると、プログラマチックインターフェースを介してクライアントから受信された入力に少なくとも部分的に基づいて、前記クライアントによる前記アウトライアスコアの評価を示す入力を知識ベースに記憶し、１つ以上の追加のデータ記録のそれぞれのアウトライアスコアを決定するために使用される１つ以上のパラメータの値を識別するために前記入力を検査する、条項１９に記載の非一時的なコンピュータアクセス可能な記憶媒体。
【０１０３】
様々な実施形態は、命令の受信、送信もしくは記憶、及び／またはコンピュータアクセス可能媒体に関する前述の説明に従って実行されたデータをさらに含んでよい。概して、コンピュータアクセス可能媒体は、磁気媒体または光学式媒体、例えば、ディスクまたはＤＶＤ／ＣＤ−ＲＯＭ、ＲＡＭ（例えば、ＳＤＲＡＭ、ＤＤＲ、ＲＤＲＡＭ、ＳＲＡＭ等）、ＲＯＭ等の揮発性媒体もしくは不揮発性媒体等のストレージ媒体またはメモリ媒体と、ネットワーク及び／または無線リンクなどの通信媒体を介して伝えられる電気信号、電磁信号またはデジタル信号などの送信媒体または送信信号と、を含んでよい。
【０１０４】
本明細書で図面に例示され説明される様々な方法は、本方法の実施形態例を表す。本方法は、ソフトウェア、ハードウェアまたはこれらの組み合わせで実装されてよい。方法の順序は、変更されてよく、様々な要素が、追加、再順位付け、組み合わせ、除外、変更等されてよい。
【０１０５】
様々な修正及び変更は、本開示の利益を得る当業者にとって明らかである通り行われてよい。全ての係る修正及び変更を包含し、したがって、上記の説明は、制限的な意味よりもむしろ、例示的とみなされることが意図される。
【図１】
2019505912.tif 000003
【図２】
2019505912.tif 000004
【図３】
2019505912.tif 000005
【図４】
2019505912.tif 000006
【図５】
2019505912.tif 000007
【図６】
2019505912.tif 000008
【図７】
2019505912.tif 000009
【図８】
2019505912.tif 000010
【図９】
2019505912.tif 000011
【図１０】
2019505912.tif 000012
【図１１】
2019505912.tif 000013
【図１２】
2019505912.tif 000014
【図１３】
2019505912.tif 000015
【図１４】
2019505912.tif 000016
【国際調査報告】
2019505912.tif 000017
2019505912.tif 000018
2019505912.tif 000019