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

【文章來源】：煙臺(tái)大學(xué)山東省

【文章頁數(shù)】：83 頁

【學(xué)位級(jí)別】：碩士

【部分圖文】：

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

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

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

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



本文編號(hào)：2978394