[發(fā)明專利]一種基于多種支撐點的度量空間離群檢測方法

在審

• 申請?zhí)枺?/td>: 201710695785.2
• 申請日: 2017-08-15
• 公開（公告）號: CN107480258A
• 公開（公告）日: 2017-12-15
• 發(fā)明（設(shè)計）人: 許紅龍;戎海武;何敏藩;文翰;楊勇
• 申請（專利權(quán)）人: 佛山科學(xué)技術(shù)學(xué)院
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 廣州嘉權(quán)專利商標(biāo)事務(wù)所有限公司44205
• 代理人: 王國標(biāo)

技術(shù)領(lǐng)域

本發(fā)明涉及數(shù)據(jù)挖掘領(lǐng)域，更具體地說涉及一種基于多種支撐點的度量空間離群檢測方法。

背景技術(shù)

離群點是數(shù)據(jù)集中與眾不同的數(shù)據(jù)點，其表現(xiàn)與其它點如此不同，以至于使人懷疑這些數(shù)據(jù)并非隨機的偏差，而是由另外一種完全不同的機制所產(chǎn)生的。離群點也稱異常點或者異常對象。離群點檢測也稱為異常檢測、偏差檢測或離群點挖掘，它就是按照一定的算法把數(shù)據(jù)集中的離群點檢測出來。換言之，離群點檢測就是挖掘海量數(shù)據(jù)中極少數(shù)與主流數(shù)據(jù)顯著不同的點。

傳統(tǒng)的離群檢測技術(shù)，大多數(shù)是面向多維空間的，僅適用于多維數(shù)據(jù)，對于圖像、音頻視頻、蛋白質(zhì)等復(fù)雜數(shù)據(jù)類型無可奈何。僅有的少數(shù)離群檢測方法基于度量空間，適用于大多數(shù)數(shù)據(jù)類型，但是卻存在著索引效率低下，離群檢測速度較慢等問題，其中以iORCA算法以及HIOD算法最為常用。

所述iORCA算法是本領(lǐng)域代表性算法，該算法隨即選取數(shù)據(jù)集一對象作為支撐點，然后計算所有對象與支撐點的距離，再按降序排序，從而建立簡單索引，檢測離群點時，便是基于該索引，相當(dāng)于按照與支撐點的距離，從遠到近檢測。

上述iORCA算法缺點在于僅僅使用一個支撐點，在節(jié)省建立索引時間的同時卻導(dǎo)致了數(shù)據(jù)空間的扭曲，降低了索引質(zhì)量，不能很好地發(fā)揮剪枝效率，而且該算法并未提供支撐點選取算法，所選取的支撐點是隨即選取的，離群檢測效果部穩(wěn)定，最后該算法只用一個終止規(guī)則來判斷是否停止檢測離群點，未能發(fā)揮度量空間三角不等性作用來進一步減少距離計算次數(shù)。

所述HIOD算法針對iORCA算法中數(shù)據(jù)扭曲和忽略稀疏區(qū)域的問題而提出的，該算法首先選取兩個支撐點以減少數(shù)據(jù)扭曲，然后用Hilbert曲線降維以建立索引，同時優(yōu)先檢測稀疏區(qū)域，并運用基于距離三角不等性的多個剪枝規(guī)則減少距離計算次數(shù)，提高檢測速度。

上述HIOD算法克服了iORCA算法的缺點，但是該算法只選取一種支撐點同時達到密集支撐點和邊緣支撐點目標(biāo)，建立索引時間較長。

發(fā)明內(nèi)容

本發(fā)明要解決的技術(shù)問題是：提供一種快速的基于多種支撐點的度量空間離群檢測方法。

本發(fā)明解決其技術(shù)問題的解決方案是：

一種基于多種支撐點的度量空間離群檢測方法，所述方法包括以下步驟：

選擇距離函數(shù)步驟：根據(jù)數(shù)據(jù)集的數(shù)據(jù)類型，選擇相應(yīng)的距離函數(shù)；

支撐點選取步驟：讀取數(shù)據(jù)集，在數(shù)據(jù)集中選取密集支撐點以及邊緣支撐點，所述密集支撐點與邊緣支撐點不重復(fù)；

建立索引步驟：分別計算數(shù)據(jù)集中所有對象與密集支撐點的距離，記為第一距離，按第一距離從大到小順序排序，形成一維索引，分別計算數(shù)據(jù)集中所有對象與邊緣支撐點的距離，記為第二距離，以第一距離和第二距離作為坐標(biāo)，形成支撐點空間；

離群檢測步驟：將所述一維索引劃分成多個數(shù)據(jù)塊，并對所述數(shù)據(jù)塊逐塊進行離群點檢測。

作為上述技術(shù)方案的進一步改進，所述支撐點選取步驟中選取密集支撐點包括以下步驟：

從數(shù)據(jù)集中隨機選取一個對象作為第一基準(zhǔn)點；

計算數(shù)據(jù)集中所有對象與第一基準(zhǔn)點的距離，記為第三距離；

按照第三距離大小對數(shù)據(jù)集中的所有對象進行排序，并將所述數(shù)據(jù)集劃分成多個數(shù)據(jù)段，每個數(shù)據(jù)段中對象的數(shù)量相等；

計算每個數(shù)據(jù)段的距離增量，距離增量最小的數(shù)據(jù)段記為最密集區(qū)域；

計算所述最密集區(qū)域的中點，記為密集支撐點。

作為上述技術(shù)方案的進一步改進，所述支撐點選取步驟中選取邊緣支撐點包括以下步驟：

設(shè)置支撐點數(shù)量閾值，設(shè)置邊緣支撐點集并初始化為空集；

在數(shù)據(jù)集中隨機選取一個對象作為第二基準(zhǔn)點；

計算數(shù)據(jù)集中除邊緣支撐點集以外所有對象與邊緣支撐點集的距離，記為第四距離，選取第四距離最大的對象作為下一個邊緣支撐點并添加到邊緣支撐點集中，判斷邊緣支撐點集中對象的數(shù)目是否等于支撐點數(shù)量閾值，如果是，完成邊緣支撐點選取，如果不是，重復(fù)此步驟；

通過所述距離函數(shù)，計算邊緣支撐點集中各個邊緣支撐點與密集支撐點的距離，若邊緣支撐點與密集支撐點距離為零，刪除該邊緣支撐點，返回上一個步驟，繼續(xù)選取下一個邊緣支撐點并將其添加到邊緣支撐點集中，直到邊緣支撐點集中對象的數(shù)目等于支撐點數(shù)量閾值且邊緣支撐點集中各個邊緣支撐點與密集支撐點的距離均不為零；

邊緣支撐點選取完成后，將所述第二基準(zhǔn)點從邊緣支撐點集中刪除。

作為上述技術(shù)方案的進一步改進，所述離群檢測步驟包括以下步驟：