[發明專利]一種基于CUDA的屬性約簡方法

有效

• 申請號: 201810006829.0
• 申請日: 2018-01-04
• 公開（公告）號: CN108197656B
• 公開（公告）日: 2020-07-28
• 發明（設計）人: 李天瑞;胡云蒙;陳紅梅;胡節
• 申請（專利權）人: 西南交通大學
• 主分類號: G06K9/62
• 分類號: G06K9/62
• 代理公司: 成都盈信專利代理事務所(普通合伙) 51245
• 代理人: 崔建中

1.一種基于CUDA的屬性約簡方法，其特征在于，包括

步驟1：去除數據集中含有缺失值的數據對象，離散化連續的屬性，生成決策表S＝(U,C∪D)，其中U＝{x₁,x₂,…,x_n}代表對象集，C＝{c₁,c₂,…,c_m}代表條件屬性集，D代表決策屬性集，n為對象的數量，m為條件屬性的數量；

步驟2：計算U關于決策D的劃分U/Ind(D)＝{D₁,D₂,...D_d}，Ind(D)表示對象在決策屬性集D上的不可分辨關系，f_a(x)和f_a(y)分別是對象x和對象y在決策屬性a上的取值；將U/Ind(D)＝{D₁,D₂,...D_d}映射到決策布爾矩陣，生成n行d列的決策布爾矩陣F_n×d＝(d_ij)_n×d∈{0,1}，其中

步驟3：設定候選的條件屬性集計算B的條件布爾矩陣E_e×n，其中B＝{b₁,b₂,…b_p}且p≤m；包括

步驟3.1：分配GPU顯存空間，將CPU端的決策表S＝(U,C∪D)拷貝到GPU；

步驟3.2：在GPU端采用CUDA的Thrust庫，將對象集U＝{x₁,x₂,…,x_n}按照B＝{b₁,b₂,…b_p}的取值在GPU端并行排序，生成排序后的序列T＝{x₁′，x₂′，…，x_n′}和排序后的對象標號L＝{l₁,l₂,…,l_n}，其中l_i∈{1,2,…n}表示x_i′唯一的標識號；

步驟3.3：在GPU端啟動CUDA的kernel核函數，使用多線程并行掃描排序后的序列T，判斷相鄰對象是否在候選的條件屬性集B上滿足不可分辨關系，生成T＝{x₁′，x₂′，…，x_n′}關于B的布爾向量G＝{g₁,g₂,…,g_n}，其中

其中f_c(x)和f_c(y)分別是對象x和對象y在條件屬性c上的取值；

步驟3.4：將布爾向量G＝{g₁,g₂,…,g_n}和對象標號L＝{l₁,l₂,…,l_n}從GPU端拷貝到CPU端；

步驟3.5：在CPU端計算U關于候選的條件屬性集B的劃分U/Ind(B)＝{E₁,E₂,…,E_e}，生成關于候選的條件屬性集B的e行n列的條件布爾矩陣E_e×n＝(e_ij)_e×n∈{0,1}，其中

步驟4：計算候選的條件屬性集B的屬性重要度評價函數Θ(D|B)，包括

步驟4.1：分配GPU顯存空間，將條件布爾矩陣E_e×n和決策布爾矩陣F_n×d從CPU端拷貝到GPU端；在GPU端采用CUDA的cuSPARSE稀疏矩陣運算庫，并行計算相交矩陣K_e×d＝E_e×n×F_n×d＝(k_ij)_e×d，其中k_ij＝|E_i∩D_j|，|·|表示集合的基數；

步驟4.2：將屬性重要度評價函數分解為的形式，在GPU端啟動CUDA的kernel核函數，使用多線程并行計算每個評價子函數θ(ij)，包括基于正域θ^PR(ij)、基于Shannon熵θ^SCE(ij)、基于互補熵θ^LCE(ij)和基于組合熵θ^CCE(ij)評價子函數，如下：

其中K_ij＝E_i∩D_j，|·|表示集合的基數，d表示決策屬性的取值數量；

步驟4.3：在GPU端啟動CUDA的kernel核函數，使用多線程對所有的評價子函數θ(ij)進行并行求和操作，得到候選的條件屬性集B的屬性重要度評價函數

步驟5：初始化約簡集C_Attr＝C，其中C_Attr為中間局部變量；對任意的條件屬性c_i∈C，計算屬性重要度評價函數Θ(D|C-{c_i})；對任意的條件屬性c_i∈C，計算條件屬性c_i的內部屬性重要度Sig^inner(c_i,C,D)；如果Sig^inner(c_i,C,D)＞0，則將條件屬性c_i添加到約簡集Reduct中，并且從C_Attr中刪除條件屬性c_i，即Reduct＝Reduct∪{c_i}，C_Attr＝C_Attr-{c_i}；

步驟6：計算屬性重要度評價函數Θ(D|Reduct)，如果||Θ(D|Reduct)-Θ(D|C)||＜ε，則得到最終的約簡集Reduct，否則繼續；其中ε為預先設定的閾值；

步驟7：對任意的條件屬性c_i∈C_Attr，計算屬性重要度評價函數Θ(D|Reduct∪{c_i})；對任意的條件屬性c_i∈C_Attr，計算條件屬性c_i的外部屬性重要度Sigo^ut^er(c_i,Reduct,D)；選擇外部屬性重要度最高的作為最優屬性c_j＝argmax{Sig^outer(c_i,Reduct,D)}；將最優屬性c_j添加到約簡集Reduct中，并且從C_Attr中刪除最優屬性c_j對應的條件屬性c_i，即Reduct＝Reduct∪{c_i},C_Attr＝C_Attr-{c_i}，之后跳轉到步驟6。

2.如權利要求1所述的一種基于CUDA的屬性約簡方法，其特征在于，所述步驟3.5還包括，將條件布爾矩陣E_e×n保存為CSR壓縮存儲格式。