一屎飘、基本信息
??題目：Efficient algorithms for mining outliers from large data sets
??期刊/會議：ACM SIGMOD
??年份：2000
??引用次數(shù)：1866
二票唆、論文總結(jié)
2.1 研究方向
??大數(shù)據(jù)異常檢測煞额。
2.2 寫作動機(jī)
??以前的異常檢測方法大多是基于統(tǒng)計方法拓哟，但是數(shù)據(jù)的分布往往是未知的绷柒，與假設(shè)不符哈街。本文認(rèn)可了一種異常點的定義方式蛉签，并用基于距離的方式查找異常點幔摸。
2.3 創(chuàng)新之處
??首先采用聚類的方式將數(shù)據(jù)聚成若干類摸柄，計算每個簇中樣本點的k近鄰距離的上下界，將距離過小的簇刪除掉既忆，以減少計算量驱负。
2.4 實現(xiàn)思路
??首先定義異常點，首先對所有樣本點計算k近鄰距離患雇，k近鄰距離最大的前n個點認(rèn)為是異常點跃脊。
- 對原始數(shù)據(jù)使用BIRCH聚類
聚類方法有很多，作者采用BIRCH是因為它的速度比較快苛吱，適合處理大數(shù)據(jù)酪术。 - 計算每個簇中樣本點的k近鄰距離的上下界
作者定義了公式計算簇與簇之間的最短和最長距離，交叉計算每兩個簇（簇中至少有k個樣本點）之間的最短距離和最長距離翠储。對每個簇绘雁，取最大的最長距離和最短距離作為該簇k近鄰距離的上下界。 - 刪除距離過小的簇援所，將剩下的簇包含的樣本點作為候選點
將包含樣本點數(shù)量大于n的簇對應(yīng)的最短距離進(jìn)行降序排列庐舟，取最小值作為閾值，然后將所有簇的最長距離與閾值作比較住拭，刪掉小于閾值的簇挪略，剩下的簇包含的樣本點作為候選點 - 在候選點中尋找異常點
對每個點都計算k近鄰距離，然后降序排列废酷，最大的前n個點當(dāng)做異常點瘟檩，可以使用R-tree或kd-tree建立索引進(jìn)行加速。
