[發(fā)明專利]一種大數(shù)據(jù)流中的基于最近鄰的時間敏感性異常檢測方法

有效

• 申請?zhí)枺?/td>: 201910035916.3
• 申請日: 2019-01-15
• 公開（公告）號: CN109871870B
• 公開（公告）日: 2021-05-25
• 發(fā)明（設(shè)計）人: 吳廣君;賈思宇;張磊;趙志慧;李軍
• 申請（專利權(quán)）人: 中國科學(xué)院信息工程研究所
• 主分類號: G06K9/62
• 分類號: G06K9/62
• 代理公司: 北京君尚知識產(chǎn)權(quán)代理有限公司 11200
• 代理人: 余長江

本發(fā)明提供一種大數(shù)據(jù)流中的基于最近鄰的時間敏感性異常檢測方法，屬于大數(shù)據(jù)流、異常檢測技術(shù)領(lǐng)域，核心是一個以LSH抽樣視圖為基礎(chǔ)的統(tǒng)計估計器，滑動窗口使用確定波模型，將估計確定波窗口內(nèi)多個隨機時間區(qū)間的計數(shù)和方差以監(jiān)測數(shù)據(jù)在不同時間區(qū)間的分布，能夠快速尋找大數(shù)據(jù)流中的各數(shù)據(jù)的鄰居，降低計算開銷，無需單獨為每個數(shù)據(jù)保存其鄰居信息，節(jié)省空間占用，提高更新效率，基于時間敏感性能夠快速判斷數(shù)據(jù)分布是否異常以及異常發(fā)生的時間范圍。

技術(shù)領(lǐng)域

本發(fā)明屬于大數(shù)據(jù)流、異常檢測技術(shù)領(lǐng)域，具體涉及一種對時間敏感的異常檢測方法。

背景技術(shù)

數(shù)據(jù)流中的異常檢測是欺詐檢測、計算機網(wǎng)絡(luò)安全、醫(yī)療和公共衛(wèi)生異常檢測等幾個領(lǐng)域的重要任務(wù)。異常檢測的目標是檢測數(shù)據(jù)中行為或者分布與其他數(shù)據(jù)差異很大的數(shù)據(jù)，即離群點。例如在肝部腫瘤檢測中，一旦血液中的甲胎蛋白含量大大超過正常值，那么該患者有極大的可能患有肝癌。異常檢測幫助發(fā)現(xiàn)數(shù)據(jù)中這種不符合期望行為的異常數(shù)據(jù)。

數(shù)據(jù)流是一種特殊數(shù)據(jù)模型，它往往是無限、高速、多維、動態(tài)變化的。數(shù)據(jù)流的新特性給異常檢測帶來了一些必須考慮的問題，例如如何存儲無限的規(guī)模龐大的數(shù)據(jù)，如何使得數(shù)據(jù)處理速度與數(shù)據(jù)流速相匹配，如何處理動態(tài)更新的高維數(shù)據(jù)并且從中獲取關(guān)鍵信息。由于異常定義的固有模糊性，例如如何定義常規(guī)行為，異常與常規(guī)行為不一致程度等，異常檢測仍然不是一個容易的問題?？紤]到數(shù)據(jù)流的新特性，異常檢測問題變得更加復(fù)雜

異常檢測分為監(jiān)督的和無監(jiān)督的檢測。監(jiān)督異常檢測利用機器學(xué)習(xí)算法(例如分類)對標記為異常/非異常的數(shù)據(jù)集進行檢測。然而由于缺少關(guān)于異常與否的標簽信息，監(jiān)督場景在實際應(yīng)用中很少發(fā)生。因此無監(jiān)督的異常檢測更為常見，它不需要任何標簽信息。數(shù)據(jù)流中的無監(jiān)督異常檢測可以大致分為三類：1)基于統(tǒng)計，2)基于聚類和3)基于最近鄰。在基于統(tǒng)計的方法中，目標是學(xué)習(xí)數(shù)據(jù)集的正常情況下的統(tǒng)計模型。此后，不符合該模型的數(shù)據(jù)被標記異常。然而，這種需要關(guān)于數(shù)據(jù)集的基礎(chǔ)分布的先驗知識，對于隨時間動態(tài)變化的數(shù)據(jù)流是不可用的。聚類數(shù)據(jù)流近年來已成為一個有趣的話題，并引起了許多研究人員的關(guān)注并且可以用于數(shù)據(jù)流中的異常檢測。這種方法假定異常數(shù)據(jù)被分到具有少量數(shù)據(jù)或低密度的簇中，或者根據(jù)數(shù)據(jù)點到其最近的簇質(zhì)心的距離來檢測。基于聚類的算法需要足夠長的學(xué)習(xí)過程才能得到較為準確的聚類結(jié)果。基于最近鄰的方法通常基于其自身行為與其近鄰的行為之間的差異來定義點的離群程度。給定數(shù)據(jù)集D和閾值k(k0)，如果數(shù)據(jù)o在D中有少于k個鄰居，則o為離群點。這種方法易于實現(xiàn)，但是無法檢測分布偏離正常情況的異常。目前流行的基于最近鄰的算法有exact-Storm、abstractC、thresh_LEAP、MCOD和approx-Strom，這五種方法的核心是給定鄰居之間的最大距離R，計算滑動窗口內(nèi)數(shù)據(jù)的距離從而計算鄰居數(shù)量。

發(fā)明內(nèi)容

本發(fā)明的目的是提出一種大數(shù)據(jù)流中的基于最近鄰的時間敏感性異常檢測方法，為一種改進的基于近鄰的異常檢測方法(Nearest Neighbors based Time SensitiveAnomaly Detection，NN-TS)，能夠快速尋找大數(shù)據(jù)流中的各數(shù)據(jù)的鄰居，降低計算開銷，無需單獨為每個數(shù)據(jù)保存其鄰居信息，節(jié)省空間占用，提高更新效率，基于時間敏感性能夠快速判斷數(shù)據(jù)分布是否異常以及異常發(fā)生的時間范圍。

為實現(xiàn)上述目的，本發(fā)明采用的技術(shù)方案如下：

一種大數(shù)據(jù)流中的基于最近鄰的時間敏感性異常檢測方法，其步驟包括：

根據(jù)大數(shù)據(jù)流中數(shù)據(jù)的維度確定數(shù)組參數(shù)K和L和閾值參數(shù)α和β，創(chuàng)建一個L行2^K列的二維數(shù)組DW_W，數(shù)組的每一項是一個確定波窗口，初始化生成KL個隨機向量w_ij，用于構(gòu)建算法中的L個哈希函數(shù)；

對到來的大數(shù)據(jù)流中的數(shù)據(jù)，利用上述哈希函數(shù)將數(shù)據(jù)哈希到哈希表即2^K L個確定波窗口內(nèi)，每個哈希函數(shù)對應(yīng)一行；