[發明專利]用于流數據的離群值檢測

有效

• 申請號: 201780005917.2
• 申請日: 2017-01-06
• 公開（公告）號: CN108475287B
• 公開（公告）日: 2022-05-13
• 發明（設計）人: N·米施拉;D·布里克;S·古哈;O·J·斯科瑞沃斯
• 申請（專利權）人: 亞馬遜科技公司
• 主分類號: G06F16/215
• 分類號: G06F16/215;G06N20/00;G06F16/2458;G06N5/00
• 代理公司: 中國貿促會專利商標事務所有限公司 11038
• 代理人: 鄒丹

1.一種用于計算針對數據記錄的離群值得分的系統，所述系統包括：

在提供商網絡處實施的網絡可訪問分析服務的一個或多個計算裝置；

其中所述一個或多個計算裝置被配置為：

產生對應于數據集的數據記錄的基線集的相應樣本的一個或多個隨機切割樹，其中所述數據記錄中的個別數據記錄包括多個屬性的值，其中產生對應于特定樣本的特定隨機切割樹包括以下操作的一次或多次迭代：

至少部分基于特定屬性在所述特定樣本上的值范圍的大小大于所述多個屬性中的一個或多個其它屬性在所述特定樣本上的值范圍的大小來選擇所述多個屬性中的所述特定屬性；以及

在針對所述特定屬性選擇的分割值上分割所述特定樣本的至少一部分；以及

響應于獲得不包括在所述基線集中的特定數據記錄，至少部分基于在所述特定隨機切割樹內為所述特定數據記錄識別出的可能的插入位置來計算針對所述特定數據記錄的離群值得分。

2.根據權利要求1所述的系統，其中所述數據集的所述數據記錄包括觀察記錄，并且其中所述一個或多個計算裝置還被配置為：

經由程序設計接口從客戶端接收對流數據源的所述觀察記錄執行離群值檢測的請求，其中所述執行離群值檢測的請求用選定的查詢語言明確表達，并且其中所述請求指示表明時間窗的參數，將關于所述時間窗執行所述離群值檢測；

收集所述流數據源的觀察記錄的基線集；

響應于根據概率流樣本更新算法確定對應于所述特定隨機切割樹的所述樣本將包括特定觀察記錄，將表示所述特定觀察記錄的節點插入到所述特定隨機切割樹中；以及

響應于確定所述離群值得分滿足結果報告標準，將所述離群值得分的指示提供給所述客戶端。

3.根據權利要求2所述的系統，其中為將表示所述特定觀察記錄的所述節點插入到所述特定隨機切割樹中，所述一個或多個計算裝置被配置為：

響應于(a)在從所述特定隨機切割樹的根節點開始的遍歷期間到達所述特定隨機切割樹的特定節點，其中所述特定節點表示對應于關于所述多個屬性中的第一屬性執行的較早隨機分割計算的屬性值的邊界框，以及(b)確定所述特定觀察記錄落在所述邊界框外，

關于在所述邊界框中呈現的所述多個屬性中的選定屬性執行隨機分割計算；以及

至少部分基于所述隨機分割計算的結果，確定(a)表示所述特定觀察記錄的節點是否被添加作為所述特定節點的新子節點或(b)所述特定隨機切割樹的遍歷是否將沿著包括所述特定節點的不同子節點的路徑繼續。

4.根據權利要求2或3所述的系統，其中所述一個或多個計算裝置被配置為：

在確定對應于所述特定隨機切割樹的所述樣本將包括所述特定觀察記錄之后，

從所述特定隨機切割樹刪除表示不同的觀察記錄的葉節點；

用所述葉節點的兄弟節點替換所述葉節點的父節點；以及

調整在所述兄弟節點的新位置與所述特定隨機切割樹的根節點之間的路徑上的一個或多個節點的相應的邊界框。

5.根據權利要求2或3所述的系統，其中所述一個或多個計算裝置被配置為：

至少部分基于以下各項中的一個或多個來計算所述離群值得分：(a)對應于所述可能的插入位置的稀疏性度量，(b)關于所述可能的插入位置和所述特定隨機切割樹的一個或多個其它節點計算出的相應的距離度量，或(c)對應于所述可能的插入位置的位移度量。