近年來,隨著各類智能移動設備的廣泛普及,社交網絡、網上購物、移動支付、位置服務等新興應用不斷涌現,各類海量大數據被采集和處理,而面向這些大數據的挖掘分析服務已儼然成為一大獨具特色的新興產業(yè)。異常檢測作為數據挖掘最重要的任務之一,在網絡監(jiān)控、信用卡欺詐等各種應用領域都被認為是至關重要的內容。此外,在實際生活中,數據分布往往是傾斜的,而局部異常檢測能夠有效解決數據傾斜分布下的異常檢測問題,在很多應用領域具有較好的檢測效果。因此,局部異常檢測在學術界和工業(yè)界都受到了越來越多的關注,本文為了更加高效快速地檢測出海量大數據中的異常對象,提出了兩個基于密度的局部異常檢測方法,主要研究內容如下:（1）在面向靜態(tài)大數據異常檢測方面,提出了一種快速的top-n局部異常點檢測算法,融合索引結構和多層LOF上界設計了多粒度的剪枝策略,以快速發(fā)現top-n局部異常點。首先,提出了四個更接近真實LOF值的上界,以避免直接計算LOF值,并對它們的計算復雜度進行了理論分析;其次,結合索引結構和UB1、UB2上界,提出了兩層的Cell剪枝策略,不僅采用全局Cell剪枝策略,還引入了基于Cell內部數據對象分布的局部剪... 

【文章來源】：煙臺大學山東省

【文章頁數】：83 頁

【學位級別】：碩士

【部分圖文】：

圖３．１兩與ｄｉ５ｔ（ｇ，ｏ）的關系示例??

３＿基子密度的ｔｏｐ＊局部異常點快速襝測算濃??索引和ＬＯＦ上界的剪枝方法，無需對每個數據對象進行計算即可剪枝掉高密度ｇ域??內的所有數據對象。??基于Ｃｅｌｌ的全局剪枝．對于某一高密度區(qū)域內的數據對象，如果能夠保證所有??數據對象的ＬＯＦ值上界小于臨界值ｃ／，則該區(qū)域內的所有數據對象都可以直接??被剪枝掉。給定邊長／ｅ？ｓｉｄｅ，將整個數據空間按照／？；＿為單位長度劃分，得到的每??個子空間劃分稱為一個Ｃｅｌｌ，如圖３．３所示，包括了?９個Ｃｅｌｌ，中間Ｃｅｌｌ記為Ｃ。??考慮使甩上界冊咖），給定一個高密度的Ｃｅｌｌ?如果對于Ｖｐ?ｅ?Ｃ，Ｌ＾（ｐ）?＜?ｃｔ，??則該Ｃｅｌｌ中所有的數據對象都可以直接被剪枝掉Ｄ??引理３．１〔基于Ｃｅｌｌ的全局剪枝）．給定一個Ｃｅｌｌ，記為Ｃ，?ＬＯＦ剪枝臨界值成??如果Ｃ包含的數據對象多于々個，弁且其邊長Ｚｅｎｓｉｄｅ?Ｓ?為數據的維度），??那么Ｃ中所有的數據對象可以直接被剪枝。??證明．由定理?３．１?可知，ＬＯＦ（ｐ）?Ｓ?ｆ／Ｓｊｐ）?＝?ｄｉｓｔｆｃｒ＾／ｊｊＡ＾ｐ）卜?ｃｐｍｉｎ］，只：需??證明Ｖｐ?Ｇ?Ｃ，ｆ／ＳＪｐ）幺?Ｃｔ即可，也就是證明ｄｉｓｔｆｃｒ（ｐ）／｜ｉＶｆｃ（ｐ）丨幺?Ｃｔ＊?ｃｐｍｉｎ．。??，．．．Ｂ，??ｌｅｎｓｉｄｅ?－?？?ｒｊ?？?２＾ｄｎｅｒｉｓｉｄｅ??ｒｊ?＊?？??圖３．３?．暴矛Ｃｅｌｌ素：引的剪枝示例??由于Ｃ包括多于Ａ？個對象，所以對于任一對象ｐ?ｅ?Ｃ都可以在Ｃｅｌｌ對角線Ｗ?＊??Ｚｅｎｓｉｄｅ范圍內找到眾近鄰，即ｄｉｓｔｆｃ（ｐ）?Ｓ?Ｗ?＊?Ｚｅｎｓｉｄｅ；對于ｐ的眾近鄰，在：最壞情??況下．，都可以在

?煙臺大＿碩士學位論文???如果ｉｅｎｓｉｄｅ?幺?ｃｔ?＊?ｃｐｍｉｎ／２Ｖ＾，則?２Ｖ＾?＊?Ｚｅｎｓｉｄｅ?幺?ｃｔ?＊?ｃｐｍｉｎ，那么??ｄｉｓｔｋｒ（ｐ）／＼Ｎｋ（ｐ）＼?＜ｃｔ＊?ｃｐｍｉｎ〇??？?－?＊?？??？?？?？?？?？??Ｊ?？?＊??＾１?９??？?＾４?參??圖３．４區(qū)域劃分示例??傳統(tǒng)Ｃｅｌｌ劃分方法將整個數據空間按照全局的邊長劃分，從引理３．１可知，高??密度區(qū)域的剪枝條件除了與Ｃｅｌｌ內的數據對象數量有關，還要求Ｃｅｌｌ的邊長不大于??ｃｔ＊ｃｐｍｉｎ／（２Ｖ＾）。很麗，該邊長條伴與ｃｐｍｉｎ較小時．，將嚴童影響被剪枝掉的高??密度Ｅ域的數量。??基于上述考慮，本章采用文獻［５０］提出的均勻區(qū)域生成方法，首先將整個數據??集按照數據對象分布劃分成幾個相對獨立的數據分布相對均勻的區(qū)域，每個區(qū)域獨??自處理數據對象，即分區(qū)自治。具體的劃分方法分為兩步，１）首先將整個數據空間??看成根節(jié)點，然后按照二叉樹迭代地劃分數據空間，直到每個葉子節(jié)點至少包括々??個數據對象且不可再分；２）從葉子節(jié)點向上合并節(jié)點，如果兩個子節(jié)點內部數據對??象間最小的距離ｃｐ＾ｉｎ和ｃｐ＾ｉｎ的大小比例小于ｄｉｆｆ，即??ｍａｘ｛ｃｐ＾ｉｎ，?ｃｐ＾ｊＪ／ｍｉｎｔｃｐ＾ｊ＾ｃｐ＾ｎ｝?＜?ｄｉ／／，則合弁這兩個子節(jié)點，直到不能再向??上合并，一個獨立的區(qū)域被生成。通過設定適：３的比例＾■，可以將兩個分布相似??的子節(jié)點合并，■此，可以得到相對分布均勻的區(qū)域。如圖３．４所示，根據數據密??度分布生成４個均勻．區(qū)域，每個區(qū)域內即可采用一個ｃＰ］＾ｉｎｉ行基于Ｃｅｌｌ的全局剪??枝策略。??雖

【參考文獻】：
期刊論文
[1]一種基于快速k-近鄰的最小生成樹離群檢測方法[J]. 朱利,邱媛媛,于帥,原盛.  計算機學報. 2017(12)
[2]不確定數據基于密度的局部異常點檢測[J]. 曹科研,欒方軍,孫煥良,丁國輝.  計算機學報. 2017(10)
[3]促進大數據發(fā)展行動綱要[J].   成組技術與生產現代化. 2015(03)
[4]BOD:一種高效的分布式離群點檢測算法[J]. 王習特,申德榮,白梅,聶鐵錚,寇月,于戈.  計算機學報. 2016(01)
[5]基于動態(tài)網格的數據流離群點快速檢測算法[J]. 楊宜東,孫志揮,朱玉全,楊明,張柏禮.  軟件學報. 2006(08)



本文編號：2978394