本文選題：離群點檢測 + 分布式計算�。� 參考：《計算機學(xué)報》2016年01期

【摘要】：離群點檢測是數(shù)據(jù)管理領(lǐng)域中的熱點問題之一,在許多方面都有著廣泛應(yīng)用,如信用卡詐騙、網(wǎng)絡(luò)入侵檢測、環(huán)境監(jiān)測等.目前現(xiàn)有的離群點檢測算法大多針對集中式的處理環(huán)境.但隨著數(shù)據(jù)規(guī)模的不斷增長,傳統(tǒng)的集中式算法處理效率受限,無法滿足用戶日益增長的需求.針對上述問題,文中提出了一種新型的分布式離群點檢測算法.首先,在數(shù)據(jù)存儲階段(即預(yù)處理),提出了BDSP(Balance Driven Spatial Partitioning)數(shù)據(jù)劃分算法.該算法可以有效地均衡每個計算節(jié)點的工作負載,并實現(xiàn)良好的過濾效果.此外,為劃分所得到的每個塊設(shè)計了一種全新的編碼方式,可以快速地確定塊與塊之間的相鄰關(guān)系,降低網(wǎng)絡(luò)開銷.基于BDSP算法,提出了BOD(BDSP-based Outlier Detection)分布式離群點檢測算法.該算法包括2個步驟:在每個計算節(jié)點本地,利用R樹索引進行批量過濾,快速地計算離群點并得到本地候選集;利用BDSP中提供的塊編碼確定需要相互通信的節(jié)點,使用少量的網(wǎng)絡(luò)開銷得到最終結(jié)果.最后,通過大量實驗驗證了文中所提出的BDSP和BOD算法的有效性.實驗結(jié)果表明,相對于現(xiàn)有算法,文中算法可以顯著地提高計算效率并大幅降低網(wǎng)絡(luò)開銷.
[Abstract]:Outlier detection is one of the hot issues in the field of data management. It is widely used in many fields, such as credit card fraud, network intrusion detection, environmental monitoring and so on. At present, most of the existing outlier detection algorithms are focused on centralized processing environment. However, with the increasing of data scale, the efficiency of traditional centralized algorithms is limited, which can not meet the increasing needs of users. To solve the above problems, a new distributed outlier detection algorithm is proposed. Firstly, the BDSP(Balance Driven Spatial partitioning algorithm is proposed in the data storage stage (i.e. preprocessing). The algorithm can effectively balance the workload of each computing node and achieve a good filtering effect. In addition, a new coding method is designed for each block, which can quickly determine the relationship between blocks and reduce the network overhead. Based on BDSP algorithm, a distributed outlier detection algorithm based on BOD(BDSP-based Outlier Detection is proposed. The algorithm includes two steps: using R-tree index to filter outliers quickly and get local candidate set at each computing node local, and using block coding provided in BDSP to determine nodes that need to communicate with each other. Use a small amount of network overhead to get the final result. Finally, the effectiveness of the proposed BDSP and BOD algorithms is verified by a large number of experiments. Experimental results show that the proposed algorithm can significantly improve the computational efficiency and significantly reduce the network overhead compared with the existing algorithms.
【作者單位】： 東北大學(xué)信息科學(xué)與工程學(xué)院;
【基金】：國家“九七三”重點基礎(chǔ)研究發(fā)展規(guī)劃項目基金(2012CB316201) 國家自然科學(xué)基金面上項目(61033007,61472070)資助
【分類號】：TP311.13

【相似文獻】

相關(guān)期刊論文 前10條

1 薛安榮;姚林;鞠時光;陳偉鶴;馬漢達;;離群點挖掘方法綜述[J];計算機科學(xué);2008年11期

2 李存華;;l_∞度量意義下的離群點檢測[J];淮海工學(xué)院學(xué)報(自然科學(xué)版);2008年02期

3 李昕;顏學(xué)峰;;融合離群點判別的穩(wěn)態(tài)檢測方法及其應(yīng)用[J];華東理工大學(xué)學(xué)報(自然科學(xué)版);2009年01期

4 封海岳;薛安榮;;基于重疊模塊度的社區(qū)離群點檢測[J];計算機應(yīng)用與軟件;2013年05期

5 王柏鈞,王力勤;《穩(wěn)健回歸與離群點檢測》介紹[J];成都氣象學(xué)院學(xué)報;1989年04期

6 黃添強;秦小麟;葉飛躍;;基于方形鄰域的離群點查找新方法[J];控制與決策;2006年05期

7 熊君麗;;高維空間下基于密度的離群點探測算法實現(xiàn)[J];現(xiàn)代電子技術(shù);2006年15期

8 黃添強;秦小麟;王欽敏;;空間離群點的模型與跳躍取樣查找算法[J];中國圖象圖形學(xué)報;2006年09期

9 陳光平;葉東毅;;一種改進的離群點檢測方法[J];福州大學(xué)學(xué)報(自然科學(xué)版);2007年03期

10 薛安榮;鞠時光;;基于空間約束的離群點挖掘[J];計算機科學(xué);2007年06期

相關(guān)會議論文 前9條

1 張鋒;常會友;;茫然第三方支持的隱私保持離群點探測協(xié)議[A];第二十四屆中國數(shù)據(jù)庫學(xué)術(shù)會議論文集（研究報告篇）[C];2007年

2 連鳳娜;吳錦林;薛永生;;一種改進的基于距離的離群挖掘算法[A];第二十四屆中國數(shù)據(jù)庫學(xué)術(shù)會議論文集（技術(shù)報告篇）[C];2007年

3 梁雪琴;劉紅生;代秀梅;周亞芬;;聚類離群點挖掘技術(shù)在內(nèi)部審計信息化中的應(yīng)用——一個來自商業(yè)銀行信用卡審計的實例[A];全國內(nèi)部審計理論研討優(yōu)秀論文集(2013)[C];2014年

4 于浩;王斌;肖剛;楊曉春;;基于距離的不確定離群點檢測[A];第26屆中國數(shù)據(jù)庫學(xué)術(shù)會議論文集（A輯）[C];2009年

5 許龍飛;熊君麗;段敏;;基于粗糙集的高維空間離群點發(fā)現(xiàn)算法研究[A];第二十屆全國數(shù)據(jù)庫學(xué)術(shù)會議論文集（技術(shù)報告篇）[C];2003年

6 劉文遠;李振平;王寶文;裴繼輝;;一種多維數(shù)據(jù)的離群點檢測算法[A];2007年全國第十一屆企業(yè)信息化與工業(yè)工程學(xué)術(shù)會議論文集[C];2007年

7 魏藜;錢衛(wèi)寧;周傲英;;HOT:尋找高維空間中的離群點[A];第十八屆全國數(shù)據(jù)庫學(xué)術(shù)會議論文集（研究報告篇）[C];2001年

8 周紅福;錢衛(wèi)寧;魏藜;周傲英;;EDOLOIS:高效準確的子空間局部離群點發(fā)現(xiàn)[A];第二十屆全國數(shù)據(jù)庫學(xué)術(shù)會議論文集（研究報告篇）[C];2003年

9 魏藜;錢衛(wèi)寧;周傲英;;SLOT:基于估計的高效子空間局部離群點發(fā)現(xiàn)[A];第十九屆全國數(shù)據(jù)庫學(xué)術(shù)會議論文集（研究報告篇）[C];2002年

相關(guān)博士學(xué)位論文 前10條

1 楊鵬;離群檢測及其優(yōu)化算法研究[D];重慶大學(xué);2010年

2 林海;離群檢測及離群釋義空間查找算法研究[D];重慶大學(xué);2012年

3 薛安榮;空間離群點挖掘技術(shù)的研究[D];江蘇大學(xué);2008年

4 楊茂林;離群檢測算法研究[D];華中科技大學(xué);2012年

5 金義富;高維稀疏離群數(shù)據(jù)集延伸知識發(fā)現(xiàn)研究[D];重慶大學(xué);2007年

6 雷大江;離群檢測與離群釋義算法研究[D];重慶大學(xué);2012年

7 萬家強;基于連通性的離群檢測與聚類研究[D];重慶大學(xué);2014年

8 唐向紅;數(shù)據(jù)流離群點檢測研究[D];華中科技大學(xué);2010年

9 劉靖;復(fù)雜數(shù)據(jù)類型的離群檢測方法研究[D];華南理工大學(xué);2014年

10 湯俊;基于可疑金融交易識別的離群模式挖掘研究[D];武漢理工大學(xué);2007年

相關(guān)碩士學(xué)位論文 前10條

1 韓紅霞;基于距離離群點的分析與研究[D];江蘇大學(xué);2007年

2 黃馨玉;基于鄰域重心變化的離群點檢測算法研究[D];遼寧大學(xué);2015年

3 程百球;基于EP模式的離群點發(fā)現(xiàn)[D];安慶師范學(xué)院;2015年

4 歐陽根平;Hadoop云平臺下基于離群點挖掘的入侵檢測技術(shù)研究[D];電子科技大學(xué);2015年

5 連鳳娜;離群點挖掘及其內(nèi)涵知識發(fā)現(xiàn)研究[D];廈門大學(xué);2008年

6 姚林;離群點快速挖掘算法的研究[D];江蘇大學(xué);2008年

7 夏勇;聚類分析和離群點識別技術(shù)研究及其應(yīng)用[D];哈爾濱工程大學(xué);2008年

8 馬良齋;基于屬性權(quán)重的局部離群點挖掘算法研究[D];蘭州大學(xué);2010年

9 王雪英;離群點預(yù)處理及檢測算法研究[D];西南交通大學(xué);2009年

10 吳迪;高維空間中基于空間劃分的離群點挖掘算法研究[D];河北工程大學(xué);2010年

，

本文編號：1798738