基于粗糙集的動(dòng)態(tài)特征選擇算法研究

董雪

關(guān)鍵詞：粗糙集；動(dòng)態(tài)；特征選擇；信息量；可分辨矩陣；正域

１ 引言

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

２ 相關(guān)概念

２．１ 粗糙集

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

２．２ 基于粗糙集的動(dòng)態(tài)特征選擇框架

與靜態(tài)數(shù)據(jù)不同，動(dòng)態(tài)數(shù)據(jù)常常在變化，且動(dòng)態(tài)特征選擇的算法實(shí)現(xiàn)難度更高。 基于粗糙集的動(dòng)態(tài)特征選擇是指對(duì)動(dòng)態(tài)變化的數(shù)據(jù)進(jìn)行特征選擇。 目前，相關(guān)研究大都是基于增量方法來(lái)處理動(dòng)態(tài)數(shù)據(jù)的變化，即充分利用歷史信息，提高特征選擇效率。 動(dòng)態(tài)特征選擇框架如圖 １ 所示，相關(guān)學(xué)者研究的算法屬于框架中的搜索策略步驟。

３ 粗糙集背景下動(dòng)態(tài)特征選擇算法

基于動(dòng)態(tài)特征的選擇，若仍使用經(jīng)典的非增量特征選擇來(lái)處理，則會(huì)導(dǎo)致運(yùn)行速度較慢，因此，學(xué)者設(shè)計(jì)了許多增量特征選擇算法去解決動(dòng)態(tài)變化數(shù)據(jù)特征選擇的問(wèn)題，歸納總結(jié)出動(dòng)態(tài)特征選擇算法分為三類，即基于可分辨矩陣的動(dòng)態(tài)特征選擇［４］、基于信息表示的動(dòng)態(tài)特征選擇［５］ 和基于正區(qū)域的動(dòng)態(tài)特征選擇［６］

３．１ 。 基于可分辨矩陣的動(dòng)態(tài)特征選擇方法

３．１．１ 基本思路

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

３．１．２ 研究進(jìn)展

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

３．２ 基于信息 。 表示的動(dòng)態(tài)特征選擇方法

３．２．１ 基本思路

根據(jù)知識(shí)信息量或者屬性重要度以及信息熵依次剔除無(wú)關(guān)特征，利用新增的對(duì)象對(duì)原有的信息量進(jìn)行修正，利用原有的信息量的結(jié)果遞歸計(jì)算信息系統(tǒng)變化后的信息量，并有效利用上一次的特征選擇結(jié)果很快地求出新的特征選擇。

３．２．２ 研究進(jìn)展

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

３．３ 基于正區(qū)域的動(dòng)態(tài)特征選擇方法

３．３．１ 基本思路

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

３．３．２ 研究進(jìn)展

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

３．４ 三種方法的適用類型及優(yōu)缺點(diǎn)

基于可分辨矩陣的動(dòng)態(tài)特征選擇方法、基于信息表示的動(dòng)態(tài)特征選擇方法和基于正區(qū)域的動(dòng)態(tài)特征選擇方法的適用類型及優(yōu)缺點(diǎn)對(duì)比［２３］如表 １ 所列。

４ 發(fā)展趨勢(shì)

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

５ 結(jié)束語(yǔ)

隨著學(xué)者的不斷探索和研究，動(dòng)態(tài)特征選擇算法越來(lái)越多，但由于數(shù)據(jù)的多樣性及復(fù)雜性，使得現(xiàn)有算法性能不佳，動(dòng)態(tài)數(shù)據(jù)特征選擇方法仍面臨巨大挑戰(zhàn)。