• 
    

    
    

      99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看 ?

      基于插值的高維稀疏數(shù)據(jù)離群點檢測方法*

      2020-06-22 12:50:02陳旺虎張禮智梁小燕高雅瓊
      計算機工程與科學 2020年6期
      關鍵詞:離群高維插值

      陳旺虎,田 真,張禮智,梁小燕,高雅瓊

      (西北師范大學計算機科學與工程學院, 甘肅 蘭州 730070)

      1 引言

      數(shù)據(jù)驅(qū)動方法在規(guī)律發(fā)掘、趨勢預測中發(fā)揮著越來越重要的作用。由于數(shù)據(jù)質(zhì)量對數(shù)據(jù)分析的結(jié)果有很大的影響,在對數(shù)據(jù)進行分析前,往往需要過濾原始數(shù)據(jù)集中存在的異常數(shù)據(jù)。離群點通常被認為是偏離其他對象的個體,以至于人們懷疑是由另一種機制產(chǎn)生的[1]。因此,離群點子集往往與其余數(shù)據(jù)表現(xiàn)得不一致[2]。離群點檢測是異常數(shù)據(jù)檢測中的核心問題[2],具有重要的研究意義。

      監(jiān)督學習是當前應用較為廣泛的一類離群點檢測方法[3 - 5]。但是,在實際的離群點檢測任務中,異常樣本的提供或者選擇往往存在一定的難度。 如果樣本對于離群點特征的覆蓋不夠,則嚴重影響此類方法的檢測準確率。無監(jiān)督的離群點檢測方法由于不依賴于標簽數(shù)據(jù),與有監(jiān)督的方法相比,其使用條件更為寬松,可應用性也更強。在無監(jiān)督的離群點監(jiān)測中,基于聚類的方法一直以來是一個重要的研究分支。在此類方法中,當前的研究方法大多依靠不同的策略,通過改進初始聚類中心等手段來不斷改善聚類效果,從而提高離群點檢測的準確率。

      然而,從數(shù)據(jù)的空間分布角度來看,高維數(shù)據(jù)很多時候具有稀疏性。因此,基于距離或者密度思想的聚類,容易導致一些非離群點數(shù)據(jù)被排除在聚類所獲得的各個簇中,降低了離群點的召回率。另一方面,增加距離或者密度閾值雖然可以在一定程度上提高離群點的召回率,但又容易導致離群點數(shù)據(jù)與正常數(shù)據(jù)的交織,降低離群點檢測的準確率。綜上,本文針對高維稀疏數(shù)據(jù),基于空間數(shù)據(jù)插值的思想,引入空間樣本的遺傳變異策略,試圖探索一種無監(jiān)督的離群點檢測方法。

      后續(xù)的內(nèi)容安排如下:第2節(jié)對當前的相關工作進行了介紹和分析;第3節(jié)提出了一種基于插值的高維稀疏數(shù)據(jù)離群點檢測方法,并在第4節(jié)中,對基于遺傳算法的插值方法進行深入分析;第5節(jié)在對實驗結(jié)果分析的基礎上,對所提方法進行了比對評價;最后,在第6節(jié)中,給出了本文的結(jié)論以及對將來工作的展望。

      2 相關工作

      有監(jiān)督的離群點檢測方法通常從樣本數(shù)據(jù)中學習并建立正常樣本或者離群樣本的模型。通過建立假設模型h(x)并確定閾值ρ,當給定樣本x,若h(x) ≥ρ,則認為x是正常樣本,否則認為其是離群值,而離群值在很多情況下也被認為是異常樣本,并且閾值ρ往往根據(jù)經(jīng)驗誤差設置[5]?,F(xiàn)有的大多數(shù)離群點檢測方法都可認為是基于該框架的,針對假設模型具體構(gòu)建方法不同,演化出了不同的有監(jiān)督離群點檢測,代表性的工作包括文獻[5 - 8]。

      通常來講,基于監(jiān)督學習的離群點檢測方法具有較高的準確率,但其準確率對于樣本的數(shù)量和標注質(zhì)量仍具有很高的依賴性。從某種程度上看,樣本的數(shù)量和標注質(zhì)量,決定了此類方法的檢測效果。然而,大量樣本的標注是一項很有挑戰(zhàn)性的工作,這對于有監(jiān)督的離群點檢測造成了諸多困難。在很多情況下,也限制了此類方法的實際應用。

      非監(jiān)督離群點檢測方法通常不需要樣本標注,與基于監(jiān)督學習的離群點檢測方法相比,其應用條件更為寬松。常見的一種思路是通過參數(shù)化或非參數(shù)化方法估計訓練樣本的密度模型,并設置相應的密度閾值,通過判斷局部的密度來確定離群點[9]。當前的無監(jiān)督離群點檢測方法中,比較有代表性的包括基于相對密度估計的檢測方法、基于模型的檢測方法和基于支撐域的檢測方法。

      基于相對密度的離群點檢測方法可以有效地解決數(shù)據(jù)對象密度分布不均勻的問題[10]。在基于相對密度估計的方法中最具代表的是LOF(Local Outlier Factor)算法[11],然而,這種方法有時對參數(shù)很敏感,并且密度估計方法對目標類數(shù)據(jù)的稀疏區(qū)域很難做出正確的判斷。

      基于模型的檢測方法根據(jù)模型可分為3種類型。點重構(gòu)方法利用樣本點到最近聚類中心的距離作為重構(gòu)誤差來進行離群檢測,代表性工作包括基于K-means[12]和K-center[13]的離群點檢測。平面重構(gòu)方法利用最近鄰超平面的距離作為離群點檢測的重構(gòu)誤差。正是考慮到點重構(gòu)方法難以描述平面簇數(shù)據(jù),Bradley等人[14]提出了K-plane clustering算法,類似工作還包括基于曲線、曲面和子空間重構(gòu)的離群點檢測方法。主成分分析PCA(Principal Component Analysis)[15]就是一種基于線性降維的方法,也可以通過擴展在非線性環(huán)境中使用(例如在文獻[16]中提出的KPCA(Kernel PCA)方法)。PCA的另一種非線性擴展基于主曲線[17],根據(jù)數(shù)據(jù)中每個點的重構(gòu)誤差以及一定經(jīng)驗誤差約束下設定的閾值,構(gòu)造以主曲線為中心的柱形數(shù)據(jù)描述。

      由于在實際的離群點檢測應用中,通常只有一種類型的樣本,Scholkopf[18]利用單分類SVM提出了一種基于支撐域離群點檢測的方法。該方法為避免受到噪聲數(shù)據(jù)和孤點數(shù)據(jù)的影響,不嚴格要求訓練樣本到球體中心的距離的平方小于或等于R2,但大于R2的點將受到懲罰。在此基礎上,Tax等[19]提出了支持向量數(shù)據(jù)的描述。

      上述無監(jiān)督的離群點檢測方法,為本文的研究奠定了很好的基礎。但是,在樣本數(shù)量有限的情況下,數(shù)據(jù)的空間分布表現(xiàn)出很高的稀疏性,給基于密度、模型以及支撐域的離群點檢測造成了很大的困難。事實上,高維樣本在空間分布上往往具有天然的稀疏性。然而在當前的研究中,針對高維稀疏數(shù)據(jù)的離群點檢測關注不多。因此,本文引入高維數(shù)據(jù)空間的插值思想,試圖探索一種針對高維稀疏數(shù)據(jù)的離群點檢測方法ODGA(Outlier Detection for Genetic Algorithm )。

      3 基于插值的稀疏數(shù)據(jù)離群點檢測

      通常認為,離群點對象與其他對象存在較大的差異,以至于可懷疑其是由另一種機制產(chǎn)生的。因此,離群點檢測可被用于異常數(shù)據(jù)的檢測。假設對所有樣本數(shù)據(jù)進行了聚類,則每一簇中的樣本具有相似的特征,而樣本點與質(zhì)心的距離超出一定范圍時,將很難被歸入到任何一個簇中,可認為該樣本的產(chǎn)生機制可能與絕大多數(shù)樣本存在差異,從而在很大概率上屬于離群點。

      無監(jiān)督聚類方法簡單,依賴條件寬松。其中,K-means是具有代表性的基于距離的聚類算法,是當前應用最為廣泛的聚類算法之一。K-means以距離作為樣本相似性的評價依據(jù),距離越近,認為樣本的相似性越高,其可認為是尋找緊湊的、獨立的簇。因此,本文的離群點檢測方法首先基于K-means聚類,通過判斷樣本點是否大于一定的閾值來檢測離群點。

      然而,由于K-means算法以距離平均值作為聚類中心,并將其應用到下一次迭代中,當聚類中心是噪聲點或孤立點時,將使得聚類中心偏離數(shù)據(jù)集的密集區(qū)域。因此,如果數(shù)據(jù)集包含大量孤立點或噪聲數(shù)據(jù),聚類結(jié)果受噪聲或孤立點的影響較大,導致聚類結(jié)果不準確甚至不正確,從而導致分離出來的離群數(shù)據(jù)與正確的離群數(shù)據(jù)產(chǎn)生較大偏差。如果直接用傳統(tǒng)K-means算法進行離群點檢測勢必會導致大量的離群點影響聚類結(jié)果,從而使得無法有效分離出離群值和正常值,在檢測出越多的離群點的同時增大正常點的損失。當樣本數(shù)據(jù)比較稀疏時,這種情況表現(xiàn)得更為突出。

      因此,本文在借鑒K-means算法的基本思想的基礎上,引入空間數(shù)據(jù)的插值思想,盡量阻止稀疏數(shù)據(jù)在聚類的時候被合并,以提高離群點的檢測效果。該方法的基本思想如下所示:

      (1)將所有樣本作為現(xiàn)有樣本集中的初始總體,隨機選取初始聚類中心完成一輪聚類。

      (2)在聚類產(chǎn)生的簇中,依靠適應度函數(shù)找出子簇中聚類效果最差的一個類。

      (3)對上述類的樣本空間進行插值,并進入下一輪聚類。

      (4)在最終的聚類結(jié)果中,與質(zhì)心的距離過大的樣本點被認為是可能的理論點。

      ODGA方法的偽代碼可描述如下:

      輸入?yún)?shù):k,path,column,n,Runtimes,Gtimes,geneticrate。

      1.variarate=readConfiguration();

      2.foreachi

      3.Initializedata() ;// 初始化數(shù)據(jù)

      4.scope=k_means(K,path,column,n);

      5.forj

      6.Genetic_Algorithm(scope,geneticrate,variarate,column,n); /*遺傳變異算法*/

      7.j++;

      8.endfor

      9.k_means(k,path,column,n);

      10.Statistic(k,i); // 統(tǒng)計實驗結(jié)果

      11.i++;

      12.endfor

      1.functionk_means(k,path,column,n)

      2.scope=Getscope(path,column);/*scope是一個二維數(shù)組,其值為數(shù)據(jù)中每個屬性的取值范圍*/

      3.central=Greatingrandomcentral(scope,k);/*隨機獲得簇中心*/

      4.whileIstabilized()do

      5.classify(central,path);//按照簇中心分簇

      6.central=Findnewcentral();//尋找簇中心

      7.endwhile

      8.returnscope

      9.endfunction

      4 基于遺傳算法的稀疏數(shù)據(jù)插值

      由于遺傳算法是一種全局優(yōu)化算法,因此選擇遺傳算法對K-means聚類算法進行優(yōu)化。與傳統(tǒng)的優(yōu)化方法(枚舉、啟發(fā)式等)相比,遺傳算法以生物進化為原型,具有較好的收斂性,具有計算時間短、魯棒性強等優(yōu)點。將遺傳算法應用于本文方法的最大優(yōu)點是在高維稀疏樣本集的離群點檢測中,彌補了數(shù)據(jù)信息不完整的不足。通過合理產(chǎn)生新數(shù)據(jù)樣本來增加數(shù)據(jù)密度,幫助找到更有利的質(zhì)心。

      遺傳算法是一種模擬自然環(huán)境中生物遺傳和進化過程的自適應全局優(yōu)化概率搜索算法。遺傳算法將搜索的變量看作有限長度的字符串,這些字符串被稱為染色體,這些字符串的單個元素或特征被稱為基因,基因的值被稱為等位基因[20]。在ODGA方法中,我們使用二進制編碼方式,將每條數(shù)據(jù)視為一條染色體,每條染色體由L個基因組成,其中基因L表示屬性。在二進制情況下,編碼染色體的每一位都被初始化為隨機的0或1。

      本文使用了單點交叉與固定交叉概率pc,這意味著群體首先隨機配對,然后隨即設置交叉點,最后選擇配對的2條染色體之間的部分基因進行交換。在單點交叉中,在對應點處將2個“父母”切割一次,并且交換切割后的基因片段。突變是為了有助于在后代染色體中引入多樣性,通過修改一些基因引入新的遺傳結(jié)構(gòu)。在二進制情況下可以通過以小概率反轉(zhuǎn)每個基因的值來完成簡單的突變,通常突變概率pm由pm=1/L得到,其中L為染色體長度。

      構(gòu)造恰當?shù)倪m應度函數(shù)對優(yōu)化算法的性能具有重要的影響,本文使用類內(nèi)距離與類間距離的比值來定義適應度。顯然,如果每個類之間的距離越大,同一類內(nèi)的距離越小,適應度函數(shù)值越小,則聚類效果越好。

      如果將每個集群總體的樣本集表示為xc,s0,s1,…,sm-1為集群xc中的數(shù)據(jù)。

      每個簇內(nèi)的平均距離dc(x)表示為:

      其中,c表示質(zhì)心,m表示集群樣本數(shù)。適應度函數(shù)為:

      其中,ki,j表示類間距,n表示簇的個數(shù),

      本文通過遺傳變異和聚類這2個階段的融合迭代,對原始數(shù)據(jù)的稀疏部分進行了插值處理,利用這些新數(shù)據(jù)填充原始樣本集的稀疏部分,改善了稀疏數(shù)據(jù)在進行聚類的時候容易被合并的問題,在得到更好的聚類結(jié)果后再進行離群點的檢測。該部分的偽代碼描述如下所示:

      1.functionGenetic_Algorithm(scope,geneticrate,variation,column,Gafile,Tfile)

      2.gedata[][]=readData(Gafile,geneticrate);

      3.parents[2][]=nextParents(gedata);

      4.an=getAttributionNumber();

      5.whileparents≠nulldo

      6.crosspoint=random(0,an)//an表示數(shù)據(jù)的維度

      7.newdata[][]=regroup(parents,crosspoint);

      8.writeData(newdata,Tfile);

      9.parents[2][]=nextParents(gedata);

      10.endwhile

      11.whilei

      12.variapoint=random(0,an);

      13.varieddata[i][variapoint]=random(scope[0][variapoint],scope[1]variapoint);

      14.writeData(newdata,Tfile);

      15.parents[2][]=nextParents(gedata);

      16.endwhile

      17.endfunction

      5 實驗分析

      為驗證本文方法對高維稀疏數(shù)據(jù)中離群點的檢測效果,從UCI公共數(shù)據(jù)集[21]中選取了Lymphography、WBC、Ionosphere和Parkinson 4個數(shù)據(jù)集,對文中方法的有效性進行了實驗分析,同時與當前的離群點檢測方法進行了對比分析。需要說明的是,由于當前沒有公認的離群點檢測的公共數(shù)據(jù)集,通常的做法是對機器學習數(shù)據(jù)集進行采樣,將離群點數(shù)量控制在總數(shù)據(jù)量的5%左右。本實驗最終選擇和構(gòu)造的離群點檢測的數(shù)據(jù)集如表1所示。

      Table 1 Outlier detection sample dataset表1 離群點檢測樣本數(shù)據(jù)集構(gòu)成

      以Lymphography數(shù)據(jù)集為例,共包含148個實例,每個實例由18個屬性描述。該數(shù)據(jù)集總共有4類標簽,分別表示該樣本描述的個體的淋巴為正常、轉(zhuǎn)移、惡性和纖維化4種情況。與文獻[22]類似,最小的2個類中的實例數(shù)僅占數(shù)據(jù)集中實例數(shù)的4.05%,其中的樣本將被認為是離群點,相應地,其他2個類中的實例被認為是正常樣本值。WBC、Ionosphere、Parkinson 3個數(shù)據(jù)集中的離群點標注采用了相同的方法。

      從某種角度來看,離群點檢測可被看作二分類問題。如果將離群點看作是異常值,其余點則為正常值,檢測方法就可以作為一個分類器將所有數(shù)據(jù)分為異常和正常2類。而對于二分類問題,樣本可以分為真陽性(TP)、假陽性(FP)、真陰性(TN)和假陰性(FN),由此可得出表2所示的混淆矩陣?;诨煜仃嚳梢杂嬎惴诸惼鞯臏蚀_率,而準確率越高,則認為分類結(jié)果越好。因此,該指標也可用于評價異常檢測方法的準確性,其計算方法如下所示:

      Table 2 Confusion matrix表2 混淆矩陣

      ORC(Outlier Removal Clustering)[23]、FindCBLOF(Find Cluster-Based Local Outlier Factor)[23]和ODC(Outlier Detection based Clusering)[22]方法都是基于改進的聚類算法的異常檢測方法,本文在Lymphography數(shù)據(jù)集上,對上述3種方法與本文方法從分類器的角度進行了比較,如表3所示。從圖1可以看出,本文方法ODGA的準確率為83.11%,而ODC、FindCBLOF、ORC 3種方法的準確率分別為66.22%,63.51%,50%,ODGA的準確率(Accuracy)明顯高于其他3種方法的。

      Table 3 Test results of four approaches表3 4種方法的檢測結(jié)果

      Figure 1 Comparison of accuracy圖1 準確率對比

      如果以TPrate表示陽性樣本被分成陽性樣本的比例,F(xiàn)Prate表示陰性樣本被分成陰性樣本的比例,則Euc可用以表示分類器在ROC圖上與理想分類器之間的距離,Euc值越小表明分類器越好。也就是說,可以用Euc表示離群點檢測方法的檢測精確度(Precision),其中:

      圖2表明,與其他3種方法相比,ODGA方法的Euc值最小,并且明顯優(yōu)于其他3種方法,進一步說明本文方法具有更好的分類效果。

      Figure 2 Comparison of classification precision圖2 分類精確度對比

      由于ODGA基于K-means聚類,并引入了插值思想,來提高稀疏數(shù)據(jù)的離群點檢測效果,實驗中,將ODGA與傳統(tǒng)的基于K-means的離群點檢測方法進行了比對分析。另外ODC[21]是典型的基于改進的K-means的離群點檢測方法。該方法首先將每個點分配給距離最近的質(zhì)心,如果檢測到離群值,則將其從數(shù)據(jù)集中刪除,并且當作離群點另外存儲,接下來重新計算質(zhì)心,直到?jīng)]有樣本點從一個類移動到另一個類中時,迭代停止。該方法界定離群點時采用了如下原則:當樣本點與質(zhì)心之間的距離是該簇中所有樣本點與質(zhì)心距離平均值的固定倍數(shù)時,則認為該點為離群點。因此,本文對ODGA方法與ODC方法進行了進一步的比對分析。

      鑒于Lymphography數(shù)據(jù)集不需要采樣就符合我們對離群點占比全部數(shù)據(jù)的5%的要求,本部分實驗中使用了Lymphography數(shù)據(jù)集。如圖3所示,橫坐標表示檢測后被標記為離群點的所有點的數(shù)量,縱坐標表示召回率??梢钥吹?,當K-means方法找到所有真正的離群點(召回率為100%)時,共標記出110個離群點,其中誤判104個點;ODC方法共標記28個,誤判22個。ODGA方法一共將13個樣本點標記為離群點,其中只有7個點被誤判。從這個角度來看,ODGA方法的檢測準確率明顯優(yōu)于基于K-means的離群點檢測方法和ODC方法的。

      Figure 3 Recall comparison of three algorithm圖3 3種方法的召回率比較

      由于K-means算法初始聚類中心是隨機選取的,因此每個算法的初始質(zhì)心都會發(fā)生變化。我們將ODC、ORC和FindCBLOF應用于Lymphography數(shù)據(jù)集10次,初始簇中心均不同,且都是在數(shù)據(jù)集中隨機選取,實驗表明這些離群點基本全都位于每個簇中距離質(zhì)心較遠的位置。如圖4所示,ORC方法[23]在被認為是離群點的40個點中準確找到6個實際的離群點;FindCBLOF方法[23]在被標記為離群點的30個點中找到6個真正的離群點;ODC方法[22]在標記的28個點中找到6個真實的離群點。然而,ODGA方法僅標記了13條數(shù)據(jù)為離群點,并包含有全部的6個離群點。由此可以得到結(jié)論,與其他3種方法相比,本文方法不僅達到了100%的召回率(查找所有稀疏類實例),而且最大限度地縮小了標識離群點的范圍。

      Figure 4 Comparison of outlier detection approaches on Lymphography dataset圖4 在Lymphography數(shù)據(jù)集上離群點檢測方法的比較

      為了觀察在面對不同數(shù)據(jù)集時,本文方法是否還能保持較好的檢測效率。針對表1中的WBC、Ionosphere和Parkinson 3個數(shù)據(jù)集,對本文方法進行了進一步的測試。從圖5可以看出,在WBC數(shù)據(jù)集上,被標記為離群點的46條數(shù)據(jù)中涵蓋所有正確的離群點,Ionosphere數(shù)據(jù)集和Parkinson數(shù)據(jù)集上本文方法同樣均表現(xiàn)良好。

      Figure 5 Test ODGA on multiple datasets圖5 在多個數(shù)據(jù)集上測試ODGA

      綜合上述實驗分析,通過利用遺傳算法對原始樣本數(shù)據(jù)集的稀疏部分進行插值處理,解決了稀疏數(shù)據(jù)在聚類時容易被合并的問題,明顯改善了聚類效果,從而提高了離群點檢測的準確率和精確度。

      6 結(jié)束語

      本文探討了一種適用于高維稀疏數(shù)據(jù)集的離群點檢測方法。該方法借鑒生物學中種群繁衍的規(guī)律,引入插值思想,解決了K-means聚類中稀疏數(shù)據(jù)容易被合并的問題。實驗表明,該方法能夠有效檢測出離群點。

      在將來的工作中,我們將進一步探索檢測到的離群點的生成機制。

      猜你喜歡
      離群高維插值
      基于Sinc插值與相關譜的縱橫波速度比掃描方法
      一種改進的GP-CLIQUE自適應高維子空間聚類算法
      測控技術(2018年4期)2018-11-25 09:46:48
      基于加權(quán)自學習散列的高維數(shù)據(jù)最近鄰查詢算法
      電信科學(2017年6期)2017-07-01 15:44:37
      一種改進FFT多譜線插值諧波分析方法
      基于四項最低旁瓣Nuttall窗的插值FFT諧波分析
      離群數(shù)據(jù)挖掘在發(fā)現(xiàn)房產(chǎn)銷售潛在客戶中的應用
      一般非齊次非線性擴散方程的等價變換和高維不變子空間
      離群的小雞
      高維Kramers系統(tǒng)離出點的分布問題
      應用相似度測量的圖離群點檢測方法
      安丘市| 金溪县| 太仓市| 江达县| 巴里| 卓资县| 沾化县| 莆田市| 上饶县| 亳州市| 江城| 颍上县| 资中县| 阳城县| 岳西县| 小金县| 阳泉市| 凤凰县| 桐梓县| 杨浦区| 河东区| 铁岭市| 水城县| 达州市| 柘荣县| 布尔津县| 抚顺县| 惠东县| 辉南县| 天柱县| 玉龙| 寿阳县| 庄浪县| 蕲春县| 淮滨县| 平湖市| 钟祥市| 瓦房店市| 泗阳县| 疏勒县| 墨玉县|