[發明專利]基于三支決策和距離的離群點檢測方法

有效

• 申請號: 201410583274.8
• 申請日: 2014-10-28
• 公開（公告）號: CN104317908B
• 公開（公告）日: 2018-08-17
• 發明（設計）人: 徐久誠;劉洋洋;孫林;徐瑾;靳瑞霞;徐天賀;張倩倩;李曉艷
• 申請（專利權）人: 河南師范大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 暫無信息
• 代理人: 暫無信息

本發明公開了基于三支決策和距離的離群點檢測方法：S1接收輸入的數據集為信息系統S，S中包含m個對象和若干個條件屬性；S2獲取數據集中每個對象的k近鄰距離和；S3對所有對象的k近鄰距離和進行歸一化處理，并將經過歸一化的結果作為三支決策的條件概率；S4建立兩個最優化目標；S5通過解最優化問題1，得到所需參數k的值為k′；S6選擇歸一化結果作為三支決策的條件概率；S7解最優化問題2，得出閾值α，γ，β，進行三支決策劃分得到正域和邊界域；S8判斷正域是否為空；S9正域為空，結束本流程；S10正域不為空，輸出正域對象，將邊界域中的對象作為新的數據集；S11歸一化新數據集的k近鄰距離和k＝k′，作為新的三支決策條件概率，轉到步驟S7。

技術領域

本發明屬于數據處理技術領域，具體涉及一種基于三支決策和距離的離群點檢測方法。

背景技術

三支決策是決策粗糙集的核心思想之一，它將傳統的正域(POS)、負域(NEG)二支決策語義擴展為正域(POS)、邊界域(BND)和負域(NEG)的三支決策語義，認為邊界域(BND)也是一類可行的決策，這與人類智能在處理決策問題時的方法是一致的。三支決策依據閾值α，β對數據集進行三支劃分，利用決策風險損失最優化作為優化目標，可以求得閾值α，β。

離群點檢測是數據挖掘技術的重要研究領域之一，用來發現數據集中明顯偏離于其他數據、不滿足數據的一般行為或模式的數據。這些數據對象叫做離群點，也叫做孤立點。離群點檢測算法分為基于統計、深度、聚類、距離和密度的方法。其中，基于距離的方法由于算法思想直觀，易于實現而得到廣泛的研究和應用。基于距離的離群點概念和挖掘方法最早由Knorr和Ng(E.Knorr and R.Ng，Algorithms for mining distance-basedoutliers in large datasets，Proceedings of the 24th VLDB Conference New York，USA，392-403，1998.)提出，如果數據集合S中至少有P部分對象與對象O的距離大于d，則對象O是一個帶參數P和d的基于距離的離群點，即DB(p，d)。后來，Ramaswamy等(SridharRamaswamy，Rajeev Rastogi，and Kyuseok Shim，Efficient algorithms for miningoutliers from large data sets，ACM SIGMOD Record，2000，29(2)：427-438.)提出了一個新的基于距離的離群點定義，即基于距離的第k最近鄰(kth Nearest Neighbor)離群點挖掘方法，Angiulli和Pizzuti(Fabrizio Angiulli and Clara Pizzuti，Outlier miningin large high-dimensional data sets，IEEE Transactions on Knowledge and DataEngineering，2005，17(2)：203-215.)提出了HilOut算法，用權重w_k(p)表示對象p與其k個最近鄰居的距離之和。顯然w_k(p)比D_k(p)更精確地度量了p的鄰域的稀疏程度。離群點檢測算法可以描述為：計算數據集D中每個數據點的離群因子w_k(p)，將其按從大到小降序排列，離群因子最高的前n個點就是所求的離群點，即Top-n離群點。

基于距離(Distance-Based)的離群點檢測方法不需要事先了解數據的分布模式，同時可以適用于任意維度的數據集，但是需要用戶選取合理的參數以保證算法的效果。例如Top-n離群點檢測方法中存在參數n與k，參數n與k值的選擇會明顯影響算法產生的實際性能和檢測結果。即使是采用同一個算法，由于被處理的數據集特征不同，n與k值的選擇也沒有可借鑒性，通常n與k值的選擇都是依靠用戶經驗和大量實驗來決定。本發明主要針對Top-n離群點檢測算法中需要人為確定的參數n和k，提出相應的改進方法，以避免參數n和k的人為確定對檢測效果的影響，回避Top-n離群點檢測方法中參數n與k選擇困難的問題。

發明內容