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

有效

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

本發明公開了一種基于CUDA的屬性約簡方法，包括如下步驟：首先分析屬性重要度評價函數的特點，將評價函數分解成可并行計算的評價子函數；其次結合CUDA編程模型，設計了多個CUDA kernel核函數，采用多線程的方式實現了條件屬性劃分和評價子函數的并行計算，通過并行規約的方法合并所有評價子函數得到屬性重要度；最后利用內部屬性重要度來選擇不可或缺的屬性，利用外部屬性重要度來完成前向貪心搜索過程中最優屬性的選擇。本發明以數據并行的策略充分利用了GPU的計算資源，加快了屬性約簡的速度，提高了屬性約簡方法的效率。

技術領域

本發明涉及特征選擇領域，尤其是一種基于CUDA的屬性約簡方法。

背景技術

隨著高維數據的不斷積累增多，如多媒體圖像視頻、航天航空數據、生物特征、金融時間序列等，特征選擇成為機器學習、數據挖掘和模式識別中的重要預處理步驟。在實際的應用中，獲得數據后通常先進行特征選擇，然后再訓練模型。特征選擇能夠剔除不相關和冗余的特征，減少特征個數，從而大大減少了計算和存儲開銷，同時提高了機器學習的效率。另一方面，選取出真正有用的特征簡化了模型，一定程度上增強了學習結果的可理解性。

1982年，一種非常有效的、可用于數據處理的軟計算工具，粗糙集理論被波蘭學者Z.Pawlak提出。該方法能夠有效地處理具有不確定、不完全、不精確關系的數據，現已被廣泛的應用于特征選擇方法，并逐漸發展成一套重要的特征選擇理論框架?；诖植诩碚摰奶卣鬟x擇，也稱為屬性約簡，它是在保持原始數據的屬性區分能力不變的前提下，選擇具有最小特征(屬性)數的特征子集。

傳統的屬性約簡方法在數據量較少時是可行的，但是當面對的數據樣本多、緯度高時，由于空間和計算能力的限制，傳統方法往往很低效甚至無法處理，如何有效地改進屬性約簡方法的效率已成為迫切需要解決的問題。近年來，面向大規模數據進行屬性約簡得到了越來越多學者的關注。2003年Wang等把大的數據集劃分成小數據集，分配到不同的客戶機上并行計算約簡，最后得到所有約簡。2009年肖大偉等將并行計算的思想融入于基于粗糙集理論的快速屬性約簡中，將屬性約簡任務劃分到多個處理器中同時處理，從而大大提高了屬性約簡的效率。2010年Yang將決策表分為分割為多個子決策表，利用MapReduce并行計算框架并行計算每個子決策表的約簡，然后匯總各個約簡，最后再刪除冗余的屬性，由于子決策表之間沒有互相交換信息，所以不能保證并行約簡的結果和串行約簡的結果相同。2013年Zhang等在Hadoop云平臺上實現了基于四種不同屬性重要度的并行啟發式屬性約簡方法，并行約簡的結果和串行約簡的結果相同。2014年Qian等在MapReduce并行計算環境下，通過并行計算等價類和并行計算屬性重要度來加速屬性約簡方法。2015年Qian等討論了不同粒度層次下分層決策表之間的關系，實現了數據和任務并行的屬性約簡方法。2016年Zhang等為了減少Hadoop HDFS文件讀寫的耗時，在基于內存的并行計算平臺Spark下，通過數據并行的方式實現了一個特征子集的重要度的并行計算，通過多線程任務并行的方式實現了多個特征子集重要度的并行計算，同時從粒度計算的角度加速了等價類的求解過程。

現存的高效的屬性約簡方法均通過Hadoop或Spark集群將任務分發到多個節點來實現并行計算，計算節點越多，并行化程度越高。但是由于其高昂的成本以及復雜的架構使得其使用范圍有限，在單機或者少量計算節點上仍然無法快速地進行約簡。為此，本發明使用CUDA編程模型，將CPU串行計算和GPU并行計算相融合，實現了GPU的高性能計算能力和CPU的分支運算能力相結合，充分利用了硬件資源，即使在單機環境下也能快速進行屬性約簡。

發明內容

鑒于現有的屬性約簡方法存在的問題，本發明的目的是提供一種以數據并行的策略充分利用GPU計算資源，提高屬性約簡效率的方法。

實現本發明目的的技術方案如下：

一種基于CUDA的屬性約簡方法，包括