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

有效

• 申請?zhí)枺?/td>: 201810006829.0
• 申請日: 2018-01-04
• 公開（公告）號: CN108197656B
• 公開（公告）日: 2020-07-28
• 發(fā)明（設(shè)計）人: 李天瑞;胡云蒙;陳紅梅;胡節(jié)
• 申請（專利權(quán)）人: 西南交通大學(xué)
• 主分類號: G06K9/62
• 分類號: G06K9/62
• 代理公司: 成都盈信專利代理事務(wù)所(普通合伙) 51245
• 代理人: 崔建中

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

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

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

步驟3：設(shè)定候選的條件屬性集計算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′}和排序后的對象標(biāo)號L＝{l₁,l₂,…,l_n}，其中l(wèi)_i∈{1,2,…n}表示x_i′唯一的標(biāo)識號；

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

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

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

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

步驟4：計算候選的條件屬性集B的屬性重要度評價函數(shù)Θ(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|，|·|表示集合的基數(shù)；

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

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

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

步驟5：初始化約簡集C_Attr＝C，其中C_Attr為中間局部變量；對任意的條件屬性c_i∈C，計算屬性重要度評價函數(shù)Θ(D|C-{c_i})；對任意的條件屬性c_i∈C，計算條件屬性c_i的內(nè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：計算屬性重要度評價函數(shù)Θ(D|Reduct)，如果||Θ(D|Reduct)-Θ(D|C)||＜ε，則得到最終的約簡集Reduct，否則繼續(xù)；其中ε為預(yù)先設(shè)定的閾值；

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

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