本文選題：離群檢測 + 度量空間��； 參考：《計算機(jī)學(xué)報》2017年12期

【摘要】：大數(shù)據(jù)的價值實現(xiàn),歸根到底還是依賴于數(shù)據(jù)挖掘技術(shù).而在很多領(lǐng)域中,海量數(shù)據(jù)的非常規(guī)模式往往更具分析價值.離群檢測,也叫異常檢測,是用于挖掘海量數(shù)據(jù)中非常規(guī)模式的一項關(guān)鍵技術(shù),廣泛應(yīng)用于網(wǎng)絡(luò)入侵檢測、公共衛(wèi)生、醫(yī)療監(jiān)控等領(lǐng)域.基于索引的離群檢測算法通常具有較高的檢測速度,然而現(xiàn)有的大多數(shù)基于索引的檢測算法并非完全基于距離,導(dǎo)致通用性降低.較高的抽象能力使得度量空間具有比多維空間更廣泛的適用范圍,在其基礎(chǔ)上設(shè)計的算法具有更高的通用性.而最新的度量空間基于索引的離群檢測算法iORCA算法通過隨機(jī)選取支撐點,基于數(shù)據(jù)到單支撐點的距離建立索引,并應(yīng)用終止規(guī)則(Stopping rule)以期提前結(jié)束離群檢測并得到正確的結(jié)果,多數(shù)情況下該機(jī)制起到加快檢測速度的重要作用.然而iORCA算法未提供支撐點選取算法導(dǎo)致檢測結(jié)果不穩(wěn)定,且未能充分利用距離三角不等性減少距離計算次數(shù).針對這些問題,文中指出基于距離的離群點定義應(yīng)結(jié)合使用完全基于距離的離群檢測算法,以確保算法的通用性,由此提出了度量空間離群檢測的概念.在此基礎(chǔ)上明確了支撐點選取的兩大目標(biāo),即邊緣支撐點和密集支撐點,并提出基于多種支撐點的度量空間離群檢測算法VPOD.考慮到兩個支撐點選取目標(biāo)難以同時達(dá)到,VPOD算法分別予以選取,在近似的密集區(qū)域選取支撐點,即密集支撐點,對應(yīng)使用終止規(guī)則,然后用FFT(Farthest-First Traversal)算法另選取若干支撐點,即邊緣支撐點,與數(shù)據(jù)集計算距離而形成支撐點空間,利用距離三角不等性,使距離計算次數(shù)顯著減少,從而提高檢測速度.實驗表明該算法能在可接受的時間范圍內(nèi)建立索引,并能高效檢測離群點,加速比達(dá)2.05,最高達(dá)3.54,距離計算次數(shù)平均減少51.14%,最高達(dá)89.46%,同時保持對多種常見的基于距離的離群點定義的兼容.
[Abstract]:Big data's value realization, in the final analysis still depends on the data mining technology. In many fields, unconventional patterns of massive data are often more analytical. Outlier detection, also called anomaly detection, is a key technology used to mine irregular patterns of massive data. It is widely used in network intrusion detection, public health, medical monitoring and other fields. Indexes based outlier detection algorithms usually have a high detection speed, but most of the existing indexing based detection algorithms are not completely based on distance, which leads to the reduction of generality. Because of its high abstract ability, the metric space has a wider range of applications than the multidimensional space, and the algorithm designed on the basis of it has a higher universality. The most recent outlier detection algorithm based on index in metric space, iORCA algorithm, establishes index based on the distance from data to single support point by randomly selecting support points, and applies termination rule to stop detection in order to finish outlier detection in advance and get correct results. In most cases, this mechanism plays an important role in accelerating the detection speed. However, the iORCA algorithm does not provide the support point selection algorithm, which leads to the instability of the detection results, and does not make full use of the distance triangulation to reduce the number of distance calculations. Aiming at these problems, this paper points out that the definition of outlier based on distance should be combined with a completely distance-based outlier detection algorithm to ensure the generality of the algorithm, and the concept of metric spatial outlier detection is proposed. On this basis, two major targets of support point selection, namely edge support point and dense support point, are defined, and VPOD, a metric spatial outlier detection algorithm based on multiple support points, is proposed. Considering that it is difficult to select two support points at the same time, we select the support points in the approximate dense area, that is, the dense support points, and then use the termination rule, and then select several other support points using the FFT(Farthest-First training algorithm. That is, the edge support point forms the support point space by calculating the distance from the data set. By using the distance triangle inequality, the distance calculation times are significantly reduced, and the detection speed is improved. Experiments show that the algorithm can build index in acceptable time range, and can detect outliers efficiently. Accelerating Prida 2.05, with a maximum of 3.54, reduces the number of distance calculations by an average of 51.14 and reaches a maximum of 89.46, while maintaining compatibility with a variety of common distance-based outliers.
【作者單位】： 佛山科學(xué)技術(shù)學(xué)院數(shù)學(xué)與大數(shù)據(jù)學(xué)院;深圳大學(xué)計算機(jī)與軟件學(xué)院廣東省普及型高性能計算機(jī)重點實驗室;南開大學(xué)化學(xué)學(xué)院;
【基金】：國家“八六三”高技術(shù)研究發(fā)展計劃項目基金(2015AA015305) 國家自然科學(xué)基金委-廣東聯(lián)合項目(U1301252,U1501254) 廣東省重點實驗室建設(shè)情況考評項目(2017B030314073) 廣東省自然科學(xué)基金(2015A030313636) 深圳市科技計劃項目(CXZZ20140418182638764)資助~~
【分類號】：TP311.13

【相似文獻(xiàn)】

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

1 魏藜,宮學(xué)慶,錢衛(wèi)寧,周傲英;高維空間中的離群點發(fā)現(xiàn)[J];軟件學(xué)報;2002年02期

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

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

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

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

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

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

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

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

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

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

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

2 連鳳娜;吳錦林;薛永生;;一種改進(jìn)的基于距離的離群挖掘算法[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 劉文遠(yuǎn);李振平;王寶文;裴繼輝;;一種多維數(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:高效準(zhǔn)確的子空間局部離群點發(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 劉露;異質(zhì)信息網(wǎng)絡(luò)中離群點檢測方法研究[D];吉林大學(xué);2017年

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

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

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

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

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

7 萬家強(qiáng);基于連通性的離群檢測與聚類研究[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 鄧璇;數(shù)據(jù)流挖掘關(guān)鍵技術(shù)研究與實現(xiàn)[D];電子科技大學(xué);2015年

6 周瑩瑩;利用離群點檢測改進(jìn)協(xié)同過濾推薦算法[D];南京郵電大學(xué);2015年

7 張友強(qiáng);基于選擇性集成學(xué)習(xí)的離群點檢測研究[D];青島科技大學(xué);2016年

8 關(guān)皓文;基于離群點檢測方法的醫(yī)保異常發(fā)現(xiàn)[D];山東大學(xué);2016年

9 朱杰;基于帶時間約束頻繁路徑的離群軌跡檢測[D];蘇州大學(xué);2016年

10 馬菲;局部離群點檢測算法的研究[D];淮北師范大學(xué);2016年

，

本文編號：1852120