基于粗糙集的動態特征選擇算法研究

董雪

關鍵詞：粗糙集；動態；特征選擇；信息量；可分辨矩陣；正域

１ 引言

所謂特征選擇，顧名思義是從原始特征空間中篩選與任務相關的特征，剔除無關、冗余及噪聲特征等［１］。 在大數據時代下，由于信息量急速增加，數據集的構成具有動態變化和不確定性的特征，傳統特征選擇方法普遍面臨不能適應的問題［２］。 粗糙集理論作為一種數據分析理論，是一種處理不精確、不確定與不完全數據的數學方法，被廣泛應用于知識發現、模式識別、生物學及數據挖掘等領域，使得應用粗糙集理論解決數據特征選擇面臨的上述不確定性問題成為可能。 本文主要對粗糙集理論下的動態特征選擇方法進行研究和分析，總結現有的動態特征選擇方法，并對動態特性選擇發展趨勢進行預測。

２ 相關概念

２．１ 粗糙集

信息系統 Ｓ ＝ （Ｕ，Ａ，Ｖ，ｆ），其中 Ｕ ＝ ｛ ｘ１ ，ｘ２ ，…，ｘｎ ｝是對象集，Ｘ?Ｕ，Ｕ ｜ Ａ 是 Ｕ 的一個劃分，Ｘ 的上下近似分別定義為

２．２ 基于粗糙集的動態特征選擇框架

與靜態數據不同，動態數據常常在變化，且動態特征選擇的算法實現難度更高。 基于粗糙集的動態特征選擇是指對動態變化的數據進行特征選擇。 目前，相關研究大都是基于增量方法來處理動態數據的變化，即充分利用歷史信息，提高特征選擇效率。 動態特征選擇框架如圖 １ 所示，相關學者研究的算法屬于框架中的搜索策略步驟。

３ 粗糙集背景下動態特征選擇算法

基于動態特征的選擇，若仍使用經典的非增量特征選擇來處理，則會導致運行速度較慢，因此，學者設計了許多增量特征選擇算法去解決動態變化數據特征選擇的問題，歸納總結出動態特征選擇算法分為三類，即基于可分辨矩陣的動態特征選擇［４］、基于信息表示的動態特征選擇［５］ 和基于正區域的動態特征選擇［６］

３．１ 。 基于可分辨矩陣的動態特征選擇方法

３．１．１ 基本思路

主要思路是“以不變應萬變”，即針對數據每次的變化，不須重新計算可分辨矩陣，只須在原來的可分辨矩陣上增加或刪除列，并對新矩陣進行核特征的修正，可以大大減少計算量。 在實際應用中，將增加的新樣本與原有樣本比較， 可分辨矩陣隨之增加列（行），對其他元素沒有影響。

３．１．２ 研究進展

可分辨矩陣可以標識條件屬性與決策屬性之間的關系，自張春英等提出基于粗集理論中的可分辨矩陣的動態特征提取算法后，滕寶等［７］基于 Ｓ?粗集和可分辨矩陣提出一種動態特征選擇算法，用來解決單向特征遷移集合的動態變化問題，但由于每添加一個樣本就需要掃描一次可分辨矩陣，使算法的搜索空間大大增加。 基于此，錢文彬等［８］提出一種快速的動態特征選擇矩陣算法，構造了簡化矩陣，有效地縮小了算法的搜索空間；ＷＥＩ 等［９］ 基于可分辨矩陣，提出一種增量式動態屬性特征選擇； ＦＥＬＩＸ 等［１０］ 提出基于二進制的差別矩陣，使差別矩陣元素由 ０ 和 １ 組成，把存儲空間縮小至原來的一半；ＸＵ 等［１１］ 更進一步地提出基于 ０?１ 整數規劃的動態特征選擇算法；在許多情況下，數據集往往通過引入一組數據而不是逐個引入單個對象來擴展，ＭＡ 等［１２］提出一種壓縮的二進制可分辨矩陣，很好地解決了這個問題；景運革［１３］ 基于知識粒度提出一種高效動態特征選擇算法，在此基礎上，提出針對刪除式動態變化的特征選擇原理及算法；在大數據時代下，隨著數據的維度不斷增加，計算也隨之復雜，ＺＨＯＵ 等把多維數據劃分為多個子集，利用現有子集及它們的核進行計算，避免重復計算，降低了時間復雜度。

３．２ 基于信息 。 表示的動態特征選擇方法

３．２．１ 基本思路

根據知識信息量或者屬性重要度以及信息熵依次剔除無關特征，利用新增的對象對原有的信息量進行修正，利用原有的信息量的結果遞歸計算信息系統變化后的信息量，并有效利用上一次的特征選擇結果很快地求出新的特征選擇。

３．２．２ 研究進展

在信息系統不斷變化的情況下，劉山等［１４］ 利用新增對象對原有信量進行修正，對原有信息量的結果進行遞歸計算，縮減了計算量，提高了效率；對于不確定信息系統，陳亮等［１５］定義了一種等價關系，以等價類決定屬性的條件信息量來定義屬性的重要度；針對多個對象被添加到一個決策表，ＬＩＡＮＧ 等［１６］ 提出一種基于信息熵的分組增量粗特征選擇算法；王永生等［１７］以信息粒度為啟發信息，提出一種使得提取效果有較好傳承性的動態特征提取算法；對于不完備信息系統，大多數學者集中于研究動態增加時的特征選擇。 基于此，董惠玉［１８］ 提出一種不完備信息系統的減少式特征選擇算法；當只考慮已選特征和類別之間的動態變化信息量時，會使得特征選擇的分類準確率下降，陳永波等［１９］ 結合已選特征與候選特征的交互相關性來選擇相關特征，與此同時，剔除無關特征和冗余特征，提出一種基于動態相關性的特征選擇算法．

３．３ 基于正區域的動態特征選擇方法

３．３．１ 基本思路

此類方法不需要建立可分辨矩陣，只對等價類進行劃分，降低了時間和空間復雜度。 首先計算原始數據和動態數據的正域，然后依據兩種重要度及特征選擇搜索策略分別設計相應的特征提取算法，最后基于啟發性動態特征選擇算法，即依據特征重要度來選擇特征子集的元素。 比較動態數據提取特征前后的重要度變化情況，變化越大，說明重要度越高，就將該特征加入特征子集中，反之則不加。

３．３．２ 研究進展

最初相關學者僅基于信息系統的不可分辨等價關系來規定正域，隨著粗糙集的逐漸成熟，有學者提出了很多基于粗糙集的動態特征選擇算法，如張春英等［２０］針對集合元素的遷入與遷出，提出雙向概率 ＰＳ?粗糙集，并在此基礎上提出一種動態三支決策，有效提高提取特征的效率；但粗糙集只能直接處理離散化的數據，連續型數據進行離散化處理時會造成信息損失，ＳＵＮ 等［２１］ 根據模糊集只關注知識模糊性這一特點，提出了模糊決策粗糙集模型，為動態特征選擇提供一個可以直接處理連續型數據的模型；在此啟發下，針對大規模直覺模糊信息系統數據量大、特征維數高、動態性強等特點，ＺＨＡＮＧ 等［２２］ 基于直覺模糊粗糙集的相似關系和廣義動態抽樣理論，提出了一種廣義的動態特征選擇算法，同時解決了直覺模糊粗糙集無法處理大數據集的問題。

３．４ 三種方法的適用類型及優缺點

基于可分辨矩陣的動態特征選擇方法、基于信息表示的動態特征選擇方法和基于正區域的動態特征選擇方法的適用類型及優缺點對比［２３］如表 １ 所列。

４ 發展趨勢

針對動態數據中樣本對象動態變化、特征維度動態變化及特征值的動態變化三種變化情形，可以設計出多種不同的算法。 基于此，可以考慮如何利用上述三種動態特征選擇方法設計針對性算法，使效率更高。 在大數據環境下，很多信息系統是不完備的，但目前針對不完備的動態信息系統進行特征提取研究較少，這是目前動態特征選擇的一大發展趨勢。 由于模糊集具有只對知識的模糊性感興趣的良好特性，因此，如何更好地利用粗糙集理論與模糊集理論的高效結合也是動態特征選擇的又一研究方向。

５ 結束語

隨著學者的不斷探索和研究，動態特征選擇算法越來越多，但由于數據的多樣性及復雜性，使得現有算法性能不佳，動態數據特征選擇方法仍面臨巨大挑戰。