【摘要】：離群檢測也稱異常點(diǎn)檢測,是數(shù)據(jù)挖掘領(lǐng)域很有意義的熱點(diǎn)問題之一,在很多方面都有廣泛應(yīng)用,如入侵行為、欺詐行為、醫(yī)學(xué)上疾病前期的征兆等.基于k-近鄰的算法能夠很好的運(yùn)用到大數(shù)據(jù)集上,因此在基于距離和基于密度的離群檢測技術(shù)方面得到廣泛應(yīng)用.然而k-近鄰算法的時間復(fù)雜度為O(N~2),隨著數(shù)據(jù)集規(guī)模的增加,時間開銷大大增加.基于最小生成樹的聚類算法在使用Prim或者Kruskal算法構(gòu)建最小生成樹時空間復(fù)雜度和時間復(fù)雜度均為O(N~2),聚類結(jié)果依賴于用戶參數(shù)的選擇,而且容易漏檢稠密簇中的局部離群點(diǎn).針對以上問題,融合基于密度和基于聚類方法的優(yōu)勢,提出一種新的離群檢測方法.該方法具有以下優(yōu)點(diǎn):(1)計(jì)算k-近鄰的時間復(fù)雜度為O(kN)(kN);(2)構(gòu)建最小生成樹的時間復(fù)雜度為O(NlogN);(3)自適應(yīng)識別聚類數(shù)目;(4)能夠檢測出多種類型的離群數(shù)據(jù).最后通過大量實(shí)驗(yàn)驗(yàn)證了文中所提的KDNS算法,FkNN算法和ADC算法的有效性.實(shí)驗(yàn)結(jié)果表明,相對于現(xiàn)有算法,文中算法可以大幅度降低時間復(fù)雜度并顯著提高離群檢測率.
[Abstract]:Outlier detection, also known as outlier detection, is one of the most significant hot issues in the field of data mining. It is widely used in many fields, such as intrusion, fraud, medical symptoms of pre-disease, and so on. The algorithm based on k-nearest neighbor can be well applied to big data set, so it is widely used in outlier detection based on distance and density. However, the time complexity of k- nearest neighbor algorithm is O (N ~ (2). With the increase of data set size, the time cost increases greatly. The clustering algorithm based on minimum spanning tree is O (NN2) in space complexity and time complexity when using Prim or Kruskal algorithm to construct the minimum spanning tree. The clustering result depends on the choice of user parameters. Moreover, it is easy to miss the local outliers in dense clusters. To solve the above problems, a new outlier detection method is proposed by combining the advantages of density-based and clustering based methods. The advantages of this method are as follows: (1) the time complexity of O (kN) (kN); (_ 2 is O (kN) (kN); (_ 2) and the time complexity of constructing minimum spanning tree is O (NlogN); (_ 3); (4) it can detect many kinds of outlier data. Finally, the effectiveness of the proposed KDNS algorithm, FkNN algorithm and ADC algorithm is verified by a large number of experiments. The experimental results show that the proposed algorithm can greatly reduce the time complexity and improve the outlier detection rate compared with the existing algorithms.
【作者單位】： 西安交通大學(xué)軟件學(xué)院;
【基金】：國家自然基金項(xiàng)目(61473220) 陜西省自然基金項(xiàng)目(S2015YFJM2129)資助~~
【分類號】：TP311.13

【相似文獻(xiàn)】

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

9 王倩;楊京燕;孟璐;;基于改進(jìn)的蟻群算法和最小生成樹的配電網(wǎng)重構(gòu)[A];中國智能電網(wǎng)學(xué)術(shù)研討會論文集[C];2011年

10 王海濤;李建;葛啟;朱洪;;內(nèi)點(diǎn)帶權(quán)的最小生成樹的近似算法[A];2005年全國理論計(jì)算機(jī)科學(xué)學(xué)術(shù)年會論文集[C];2005年

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

1 劉露;異質(zhì)信息網(wǎng)絡(luò)中離群點(diǎn)檢測方法研究[D];吉林大學(xué);2017年

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 鄧璇;數(shù)據(jù)流挖掘關(guān)鍵技術(shù)研究與實(shí)現(xiàn)[D];電子科技大學(xué);2015年

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

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

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

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

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

，

本文編號：2376107