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

在審

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

1.一種基于多種支撐點(diǎn)的度量空間離群檢測方法，其特征在于，所述方法包括以下步驟：

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

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

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

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

2.根據(jù)權(quán)利要求1所述的一種基于多種支撐點(diǎn)的度量空間離群檢測方法，其特征在于，所述支撐點(diǎn)選取步驟中選取密集支撐點(diǎn)包括以下步驟：

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

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

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

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

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

3.根據(jù)權(quán)利要求2所述的一種基于多種支撐點(diǎn)的度量空間離群檢測方法，其特征在于，所述支撐點(diǎn)選取步驟中選取邊緣支撐點(diǎn)包括以下步驟：

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

在數(shù)據(jù)集中隨機(jī)選取一個對象作為第二基準(zhǔn)點(diǎn)，添加到邊緣支撐點(diǎn)集中；

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

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

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

4.根據(jù)權(quán)利要求3所述的一種基于多種支撐點(diǎn)的度量空間離群檢測方法，其特征在于，所述離群檢測步驟包括以下步驟：

將所述一維索引劃分成多個對象數(shù)量相同的數(shù)據(jù)塊；

設(shè)置離群度閾值，并初始化為0，按順序逐個讀取每個數(shù)據(jù)塊；

如果當(dāng)前數(shù)據(jù)塊中第一個對象不可能為離群點(diǎn)，結(jié)束檢測，輸出離群點(diǎn)；

如果當(dāng)前數(shù)據(jù)塊中存在可能為離群點(diǎn)的對象，按順序逐個檢測當(dāng)前數(shù)據(jù)塊對象，從待檢測對象所在數(shù)據(jù)塊的中位對象開始以螺旋順序搜索待檢測對象的k最近鄰，直到覆蓋整個一維索引，并將判斷為不可能是離群點(diǎn)的對象從當(dāng)前數(shù)據(jù)塊中移除，直到當(dāng)前數(shù)據(jù)塊中的所有對象都處理完畢后更新離群點(diǎn)和離群度閾值，并讀取下一個數(shù)據(jù)塊；

當(dāng)所有數(shù)據(jù)塊處理完成后，輸出離群點(diǎn)。