[發明專利]一種基于聚類的分層最近鄰欠采樣方法

在審

• 申請號: 201811233719.4
• 申請日: 2018-10-23
• 公開（公告）號: CN109522936A
• 公開（公告）日: 2019-03-26
• 發明（設計）人: 高欣;梁躍;何楊;劉鑫;井瀟;刁新平
• 申請（專利權）人: 北京郵電大學
• 主分類號: G06K9/62
• 分類號: G06K9/62
• 代理公司: 暫無信息
• 代理人: 暫無信息

1.一種基于聚類的分層最近鄰欠采樣方法，其特征在于，所述方法步驟包括：

(1)利用Kmeans聚類算法得到多數類樣本的肘圖，根據簇數與各個簇畸變程度之和的關系選擇最優聚類的簇數k；

(2)使用Kmeans聚類算法將多數類樣本聚為k簇，從而得到各個簇的中心點及簇內樣本點個數；

(3)根據每個簇內樣本點的數量，進行分層采樣，選取每個簇中心點的最近鄰與少數類樣本合并作為采樣結果。

2.根據權利要求1所述的方法，其特征在于，利用Kmeans聚類算法得到多數類樣本的肘圖，根據簇數與各個簇畸變程度之和的關系選擇最優聚類的簇數k，具體說明如下：使用Kmeans算法對多數類樣本進行聚類，計算各個簇畸變程度之和dist：

其中，k為聚類的簇數，p＝len(第clu_i簇)為第i個簇內樣本點的個數，dist_ij為簇內第j個樣本點x_ij與該簇中心點cen_i的歐式距離，得到聚類簇數k與對應簇畸變程度之和dist的變化關系，在k較小時，隨著k值的增大，畸變程度會隨之減小，每個簇內樣本數量也相應減少，于是各樣本會離所在簇的中心點更近，但是隨著k值繼續增大，畸變程度的減小速度會越來越緩慢，所以在k值增大的過程中，畸變程度減小幅度最大位置所對應的k值就是肘部，即最優聚類的簇數k。

3.根據權利要求1所述的方法，其特征在于，使用Kmeans聚類算法將多數類樣本聚為k簇，從而得到各個簇的中心點及簇內樣本點個數，具體說明為：使用Kmeans聚類算法將多數類聚為k簇，Kmeans算法以歐氏距離作為相似測度，將樣本劃分為k類，采用迭代的方式，得到緊湊且獨立的簇，即簇內樣本具有較高的相似性，而簇間樣本相似性較低，同時得到了各個簇的中心點k_centers：

k_centers＝cen_1，cen_2，…，cen_k

cen_i表示第i個簇的中心點，采用各個簇中心點作為欠采樣時的中心，同時得到樣本的簇標簽k_clusters：

k_clusters＝clu_1，clu_2，…，clu_k

clu_i表示第i個簇的標簽，利用各個簇的中心點和標簽可以計算欠采樣過程中各個簇的取值個數。

4.根據權利要求1所述的方法，其特征在于，根據每個簇內樣本點的數量，進行分層采樣，選取每個簇中心點的最近鄰與少數類樣本合并作為采樣結果，具體說明為：對于每一個聚類簇clu_i，利用分層的思想計算其在多數類樣本中所占的比例p/M，根據少數類樣本的數量計算每個簇內應抽取的樣本數量num，如下所示：

num＝p/M*N

其中，M表示多數類樣本的數量，N表示少數類樣本的數量，使用kNN算法計算該簇中每個樣本點x_ij與該簇中心點cen_i的歐氏距離dist_ij：

其中，n代表樣本特征總數，cen_i_a為第i個簇的中心點在屬性a上的取值，x_ija為該簇內第j個樣本點在屬性a上的取值，將樣本點按照與中心點的距離進行排序，選取距離中心點的num個最近鄰，作為該簇中所采的多數類樣本，將所有簇中抽取的多數類樣本與全部少數類樣本合并，作為采樣結果，即類間平衡的樣本集T。