[發明專利]基于改進的局部異常因子檢測的數據分類方法

在審

• 申請號: 201910368828.5
• 申請日: 2019-05-05
• 公開（公告）號: CN110083665A
• 公開（公告）日: 2019-08-02
• 發明（設計）人: 游子毅
• 申請（專利權）人: 貴州師范大學
• 主分類號: G06F16/28
• 分類號: G06F16/28;G06K9/62
• 代理公司: 貴陽東圣專利商標事務有限公司 52002
• 代理人: 袁慶云

1.基于改進的局部異常因子檢測的數據分類方法，包括以下步驟：

（1）離群因子檢測

根據原始K-means算法在選取聚類中心點時的缺陷，提出了依據數據集中每個數據點的離群因子來排除離群點的方法，得出離群因子的計算公式（I）如下：

（I）

表示為點p的領域點N_k(p)的局部可達密度與點p的局部可達密度之比的平均值；

如果LOF值趨向1，說明p與其領域點的密度相近，p與該領域屬于同一簇的可能性大；LOF越小于1，說明p的密度高于其領域點密度，即p為密集點；相反，LOF越大于1，則p越可能是異常點；

（2）相似性度量

對數據集的每一個屬性如公式（II）進行初步的預處理：

（II）

其中，max(x_ij)表示數據第j列的最大值；

分別根據公式（III）和（IV）計算出數據中每個屬性的熵值與權值：

（III）

（IV）

根據公式（V）計算出來的權值計算數據點之間加權歐式距離：

（V）

（3）初始聚類中心點的選取

挑選出距離聚類中心點較近的部分數據作為初始聚類中心的候選集，具體步驟如下：

Step1：由公式（I）計算出數據中每個數據點的離群因子，并按離群因子值從小到大進行排列形成數據集記為D_L；

Step2：在D_L上選取前a*N（0<a≤1,N為數據集的大小）個數據對象作為初始聚類中心的候選集F（a的大小可自適應調整）；

Step3：計算數據集F中所有數據的中心點c₀，利用相似性度量，找到距離c₀最遠的數據點c₁，把c₁記作第一個初始聚類中心點，再次找到距離c₁最遠的點c₂,將c₂記作第二個初始聚類中心點，建立集合C={c₁,c₂}；

Step4：計算剩余數據對象x_j分別到集合C={c₁,c₂}的加權距離，記作disc₁,disc₂,…，disc_i，找到點c_i+1=max{min(disc_j1,disc_j2，…，disc_ji)，i+1≤k，x_j∈F}，將c_i+1記為第i+1個初始聚類中心點,即C={c₁,c₂,…,c_i+1}；Step5：重復Step 4，直到找到k個初始聚類中心點；

（4）聚類中心的迭代優化

采用離群因子對數據間距離進行加權，具體實現過程如下：

Step1：將當前輪k個聚類中心點加入到候選集F中形成新集合F’，計算出F’中每一個對象的離群因子r_i（i∈F’）,并找出r_i的最大值與最小值；

Step2：利用離差標準化對數據間的離群因子進行標準化，使得新離群因子new_r_i的取值范圍為大于等于1，具體計算見公式（Ⅵ）；

（Ⅵ）

在公式（Ⅵ）中，Max_r表示離群因子最大值，Min_r表示離群因子最小值；

Step3： 計算F’中每一個對象x_j到聚類中心c_i的加權距離disw（x_j,c_i），然后與離群因子new_r_i相乘，見公式（Ⅶ）；

（Ⅶ）

Step4：計算每個對象x_j到聚類中心集C={c₁,c₂,…,c_k}中各點的最小真實距離Min_D_ji,并將對象x_j歸為c_i的類中；

Step5： 計算同一簇中所有對象的均值作為新的聚類中心，更新聚類中心集；

Step6： 重復Step1-Step 5直到聚類中心不再發生變化;

其特征在于：步驟(3)中 Step1的公式（I）計算出數據中每個數據點的離群因子的方法為：

通過自適應調整k距離參數的局部離群因子檢測LOF算法篩選出離群因子較小的數據作為初始聚類中心的候選集，LOF算法的k距離參數由如下公式自適應調整；

（Ⅷ）

其中， num(dataset)表示集合dataset的數據對象個數，β值可根據實際經驗實際地設置為0.03。

2.如權利要求1所述的基于改進的局部異常因子檢測的數據分類方法，其中步驟（4）中Step2的在優化聚類中心迭代階段離群因子優化方法為：

在優化聚類中心迭代階段，利用離差標準化對數據間的離群因子進行標準化，使得新離群因子new_r_i的取值范圍為大于等于1，具體計算見公式（Ⅵ）

（Ⅵ）

在公式（Ⅵ）中，Max_r表示離群因子最大值，Min_r表示離群因子最小值。