[發明專利]一種基于聚類的離群點檢測方法

在審

• 申請號: 201510848176.7
• 申請日: 2015-11-27
• 公開（公告）號: CN105512206A
• 公開（公告）日: 2016-04-20
• 發明（設計）人: 劉文婷
• 申請（專利權）人: 河海大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 南京縱橫知識產權代理有限公司 32224
• 代理人: 朱妃;董建林

1.一種基于聚類的離群點檢測方法，其特征在于，包括以下步驟：

1)獲取數據集并采用改進的k_means聚類算法計算出k個類簇；

2)對k個類簇進行劃分，劃分生成大類簇集BC和小類簇集SC；

依據每個類簇|C_i|(i＝1,2…k)包含的數據對象個數對k個類簇進行排序，將包 含的數據對象個數大于設定閾值的類簇劃分入大類簇集BC，包含的數據對象 個數小于設定閾值的類簇劃分入小類簇集SC；

3)基于大小類簇的方法分別計算大類簇集內大類簇和小類簇集內小類簇 中數據對象的離群因子，匯總形成離群因子序列；

4)基于離群因子序列確定離群數據。

2.根據權利要求1所述的一種基于聚類的離群點檢測方法，其特征在于， 所述步驟1)獲取數據集并采用改進的k_means聚類算法計算出k個類簇，具體 包括以下步驟：

1-1)獲取數據集D；

數據集用D＝{x₁,x₂,…,x_i,…,x_n}，i＝1,2…n表示，其中，n為數據集D大小，x_i為數據集中的數據對象；

1-2)采用最大最小聚類方法，初始化m個聚類中心；

1-2-a)根據式(1)計算數據集D中任意數據對象x_i到樣本中心的距離d_i， 形成距離樣本；

di=Σj=1,i≠jn||xi-x‾||---(1)]]>

其中，x_i數據對象，i＝1,2…n，為樣本中心、即為數據集中所有數據對 象樣本的均值，樣本中心的計算公式為

從距離樣本中選取與樣本中心相距的距離為下限值的第一樣本x_a，作為第 一個初始聚類中心o₁；

1-2-b)當初始化m＝2時，從數據集中除第一樣本x_a、選出與第一樣本x_a相 距的距離為上限值的第二樣本x_b作為第二個初始聚類中心o₂；

1-2-c)當初始化m＝3時，從數據集中除第一樣本x_a和第二樣本x_b、計算任 意數據對象x_i到第一樣本x_a和第二樣本x_b的距離分別為d_ia和d_ib，取d_i為d_ia和d_ib中的下限值、即d_i＝min(d_ia,d_ib)；

遍歷數據集中除第一樣本x_a和第二樣本x_b外其余數據對象，形成除第一樣 本x_a和第二樣本x_b外的數據對象距離集d_i(i≤n,i≠a,i≠b)；

從d_i(i≤n,i≠a,i≠b)中選取上限值、即獲得對應的數據對象x_c作為 第三個聚類中心o₃；

1-2-d)當初始化m≤k時，針對已經獲得的k-1個初始聚類中心，計算未被 作為聚類中心的數據對象x_j到每一聚類中心的距離d_jp(p＝1,2…,k-1)，取d_j為 d_jp中的下限值、即d_j＝min(d_j1,d_j2,…,d_j(k-1))，其中，j＝1,2…n；

遍歷數據集中未被作為聚類中心的數據對象，形成除k-1個初始聚類中心 外的數據對象距離集，并從中選取距離上限值對應的數據對象x_q作為第m個聚 類中心o_m；

1-3)采用改進的k_means聚類算法，計算出k個類簇；

1-3-1)選擇聚類數搜索范圍[k_min,k_max]，其中，k_min＝2，n為數據 集D大小；

1-3-2)Fork＝k_mintok_max，即循環執行如下操作，

1-3-2a)按照步驟1-2)的方法初始化k個初始聚類中心o_k；

1-3-2b)采用k_means聚類算法，對數據集中每個數據對象x_p，找出與數 據對象x_p相距的距離為下限值的聚類中心o_i，并將數據對象x_p分配到聚類中心 o_i所標明的類簇C_i中；

1-3-2c)計算聚類結果指標值SILHOUETTE；

1-3-3)當指標值為上限值時，其所對應的指標值k值即為所需選定的聚類 數，所對用的聚類則為所需選定的聚類；

其中，指標值為上限值、即

a(t)表示類簇C_j的數據對象t與類簇C_j中所有數據對象的平均距離，令 d(t,C_i)表示類簇C_j的數據對象t與另一類簇C_i中所有數據對象的平均距離，則 b(t)＝min{d(t,C_i)},i＝1,2,…,k且k≠j。