[發明專利]一種基于雙向抽樣組合的大規模數據異常識別方法

有效

• 申請號: 201410535911.4
• 申請日: 2014-10-13
• 公開（公告）號: CN104462184B
• 公開（公告）日: 2018-04-10
• 發明（設計）人: 張玉超;鄧波;彭甫陽;李海龍
• 申請（專利權）人: 北京系統工程研究所
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 北京安博達知識產權代理有限公司11271
• 代理人: 徐國文

技術領域

本發明涉及一種異常識別方法，具體涉及一種基于雙向抽樣組合的大規模數據異常識別方法。

背景技術

異常識別(Outlier Detection)，是一種針對數據集中離群樣本點的檢測方法。異常的內涵豐富，可能是噪音、誤差、或是稀有值。在數據挖掘領域，其普遍認可的定義是，一種由其它機制產生，且與大多數觀測值(Observation)相偏離的點。在本文中，與“異常點(Outlier)”相對的點稱為“正常點(Inlier)”。

異常識別作為一種重要的研究方向，已經廣泛在信用卡欺詐識別、疾病診斷和預防、網絡入侵檢測、測量誤差檢驗、稀有價值識別等現實應用中。

(1)基于統計的異常識別方法

從20世紀80年代起，異常識別問題就在統計學領域里得到廣泛研究，通常用戶用某個統計分布對數據點進行建模，再以假定的模型，根據點的分布來確定是否異常。許許多多針對不同分布的異常測試(Discordancy Test)方法發展起來，它們分別適用于不同的情形：①數據分布狀況；②數據分布參數是否已知；③異常數據數量；④異常數據類型(高于或低于一般抽樣值)。這方面比較有代表性的有1967年Mikey，Dunn&Clark提出的基于“均數漂移”模型的單點診斷量，1970年Gentleman&Wilk提出的群組診斷量，1972年Tietjen&Moore提出的單樣本k個離群點的統計量E_k，1985年Marasinghe提出的改進的E_k統計量F_k，1989年Rosner提出的單樣本多個離群檢測方法ESD(Generalized Extreme Studentized Deviate)方法，1991年Paul&Fung改進了ESD方法參數k選擇的主觀性，提出了回歸分析的GESR(Generalized Extreme Studentized DeviateResi2dual)方法。近年來，多樣本的離群檢測方法也得到了一定的發展，總的思路是先盡量得到一個不含離群點的“干凈集”，然后在此基礎上對剩余的其他數據點進行逐步離群檢測。

目前利用統計學研究異常點數據有了一些新的方法，如通過分析統計數據的散度情況，即數據變異指標，來對數據的總體特征有更進一步的了解，對數據的分布情況有所了解，進而通過數據變異指標來發現數據中的異常點數據。常用的數據變異指標有極差、四分位數間距、均差、標準差、變異系數等等，變異指標的值大表示變異大、散布廣；值小表示離差小，較密集。

基于統計的方法識別出來的離群點很可能被不同的分布模型檢測出來，可以說產生這些離群點的機制可能不唯一，解釋離群點的意義時經常發生多義性，這是基于統計方法的一個缺陷。其次，基于統計的方法在很大程度上依賴于待挖掘的數據集是否滿足某種概率分布模型，模型的參數、離群點的數目等對基于統計的方法都有非常重要的意義，而確定這些參數通常都比較困難。為克服這一問題，一些人提出對數據集進行分布擬合，但分布擬合存在兩個問題：①給出的分布可能不適合任一標準分布。②即使存在一個標準分布，分布擬合的過程耗時太長。此外，基于統計的離群識別方法大多只適合于挖掘單變量的數值型數據，目前幾乎沒有多元的不一致檢驗，對于大多數的應用來說，例如圖像和地理數據，數據集的維數卻可能是高維的。實際生活中，以上缺陷都大大限制了基于統計的方法的應用，使得它主要局限于科研計算，方法的可移植性較差。

(2)基于距離的異常識別方法

用什么標準判定一個數據對象是孤立點呢？即便是對給定的距離量度函數，對孤立點也有不同的定義，以下是使用較多的幾個：

1)基于距離的離群點最早是由Knorr和Ng提出的，他們把記錄看作高維空間中的點，離群點被定義為數據集中與大多數點之間的距離都大于某個閾值的點，通常被描述為DB(pct，d_min)，數據集T中一個記錄O稱為離群點，當且僅當數據集T中至少有pct部分的數據與O的距離大于d_min。換一種角度考慮，記M＝N×(l-pct)，離群檢測即判斷與點O距離小于d_min的點是否多于M。若是，則O不是離群點，否則O是離群點。

2)孤立點是數據集中到第k個最近鄰居的距離最大的n個對象；

3)孤立點是數據集中與其k個最近鄰居的平均距離最大的n個對象。