馬磊，羅川*，李天瑞，陳紅梅

基于模糊粗糙集的無監(jiān)督動態(tài)特征選擇算法

馬磊1，羅川1*，李天瑞2，陳紅梅2

（1.四川大學(xué) 計(jì)算機(jī)學(xué)院，成都 610065； 2.西南交通大學(xué) 計(jì)算機(jī)與人工智能學(xué)院，成都 611756）（ ? 通信作者電子郵箱cluo@scu.edu.cn）

動態(tài)特征選擇算法能夠大幅提升處理動態(tài)數(shù)據(jù)的效率，然而目前基于模糊粗糙集的無監(jiān)督的動態(tài)特征選擇算法較少。針對上述問題，提出一種特征分批次到達(dá)情況下的基于模糊粗糙集的無監(jiān)督動態(tài)特征選擇（UDFRFS）算法。首先，通過定義偽三角范數(shù)和新的相似關(guān)系在已有數(shù)據(jù)的基礎(chǔ)上進(jìn)行模糊關(guān)系值的更新過程，從而減少不必要的運(yùn)算過程；其次，通過利用已有的特征選擇結(jié)果，在新的特征到達(dá)后，使用依賴度判斷原始特征部分是否需要重新計(jì)算，以減少冗余的特征選擇過程，從而進(jìn)一步提高特征選擇的速度。實(shí)驗(yàn)結(jié)果表明，UDFRFS相較于靜態(tài)的基于依賴度的無監(jiān)督模糊粗糙集特征選擇算法，在時(shí)間效率方面能夠提升90個(gè)百分點(diǎn)以上，同時(shí)保持較好的分類精度和聚類表現(xiàn)。

特征選擇；模糊粗糙集；動態(tài)數(shù)據(jù)；無監(jiān)督特征選擇；依賴度

0 引言

特征選擇是模式識別中一種非常重要的預(yù)處理手段，通過去除不相關(guān)和冗余的特征，達(dá)到精簡樣本集合、提高后續(xù)識別過程的效率并提升精度的目的。粗糙集作為一種重要的特征選擇模型，由Pawlak［1］提出，主要用于處理不完整、不精確的數(shù)據(jù)；但是粗糙集只能處理分類型變量，無法處理實(shí)際生活中廣泛存在的連續(xù)型變量。Dubois等［2］將粗糙集理論和模糊集理論［3］結(jié)合，提出了模糊粗糙集理論。在該理論中，通過將等價(jià)關(guān)系替換為模糊相似關(guān)系，彌補(bǔ)了粗糙集只能處理分類型變量的缺點(diǎn)。此后，大量基于模糊粗糙集理論的特征選擇算法被提出。An等［4］結(jié)合了相對測量和模糊粗糙集，提出一種新的特征選擇方法，以解決數(shù)據(jù)集的類密度差異較大時(shí)模糊粗糙集理論無法有效評估樣本的分類不確定性的問題。Chen等［5］提出一種基于超圖的模糊粗糙集特征選擇算法，從而提升該算法在大規(guī)模數(shù)據(jù)集下的時(shí)間性能，并在精簡特征集合的基礎(chǔ)上獲得了較好的分類精度。Yang等［6］提出一種噪聲感知模糊粗糙集算法，相較于傳統(tǒng)的基于模糊粗糙集的特征選擇算法，該算法的抗噪聲特性更好。

大數(shù)據(jù)時(shí)代的數(shù)據(jù)規(guī)模越來越龐大，各領(lǐng)域每時(shí)每刻都在產(chǎn)生新的數(shù)據(jù)。針對數(shù)據(jù)體量龐大的問題，一系列基于粗糙集及其擴(kuò)展模型模糊粗糙集的方法被提出。章夏杰等［7］提出一種Spark平臺下的分布式粗糙集屬性約簡算法，通過引入改進(jìn)鯨魚優(yōu)化算法實(shí)現(xiàn)特征選擇功能，并將該算法并行化，使它在大數(shù)據(jù)環(huán)境下可以充分利用集群優(yōu)勢，提高算法的運(yùn)行速度。危前進(jìn)等［8］提出一種基于粗糙集的多目標(biāo)并行屬性約簡算法，該算法將粗糙集理論和蟻群優(yōu)化算法相結(jié)合，通過MapReduce平臺并行化，從而實(shí)現(xiàn)更好的時(shí)間效率，以應(yīng)對大規(guī)模數(shù)據(jù)。但是這些數(shù)據(jù)不斷更新?lián)Q代，通常是分批到達(dá)的，呈現(xiàn)動態(tài)性。如果使用靜態(tài)算法，將舊數(shù)據(jù)和新數(shù)據(jù)一起重新處理，就無法有效利用之前的特征選擇結(jié)果，導(dǎo)致產(chǎn)生較大的時(shí)間代價(jià)。為了解決該問題，研究者提出一系列動態(tài)特征選擇算法。Yang等［9］提出一種基于關(guān)系矩陣的動態(tài)模糊粗糙集特征選擇算法，并分開討論單個(gè)新樣本和多個(gè)新樣本到達(dá)的情況；相較于靜態(tài)算法，該算法的時(shí)間效率更高。Wan等［10］從特征相關(guān)關(guān)系出發(fā)，提出一種基于模糊依賴度的動態(tài)模糊粗糙集特征選擇算法。該算法考慮了交互關(guān)系、條件特征與決策類的關(guān)系和特征權(quán)重隨特征子集變化的動態(tài)變化。Ni等［11］在模糊粗糙集的基礎(chǔ)上通過引入包含代表性樣本的關(guān)鍵實(shí)例集，在新的樣本到達(dá)時(shí)選擇并補(bǔ)充新的特征；由于關(guān)鍵實(shí)例集遠(yuǎn)小于整個(gè)數(shù)據(jù)集，該特征選擇算法能有效減少冗余計(jì)算。程玉勝等［12］提出一種基于粗糙集的數(shù)據(jù)流多標(biāo)記分布特征選擇算法，以處理流特征數(shù)據(jù)的特征選擇問題。通過特征和標(biāo)記之間的相關(guān)性、特征和特征之間的相關(guān)性這兩個(gè)標(biāo)準(zhǔn)形成候選特征集合，使得該算法在特征動態(tài)更新的背景下能夠保持較好的性能。曾藝祥等［13］提出一種基于層次類別鄰域粗糙集的在線流特征選擇算法，該算法使用經(jīng)過改進(jìn)的粗糙集模型（鄰域粗糙集），并基于層次依賴度提出了3個(gè)在線特征評價(jià)函數(shù)，使得該算法能處理在線流特征數(shù)據(jù)。

上述特征選擇算法主要在有監(jiān)督的情況下完成，然而在現(xiàn)實(shí)生活中，存在較多不能明確知道樣本所屬類別的無標(biāo)簽數(shù)據(jù)。無監(jiān)督特征選擇算法作為一種能夠在不需要類標(biāo)簽信息的情況下識別和選擇相關(guān)特征手段，被應(yīng)用在許多研究領(lǐng)域［14］。在基于粗糙集及其擴(kuò)展模型模糊粗糙集的無監(jiān)督特征選擇領(lǐng)域，Velayutham等［15］基于粗糙集模型提出一種基于依賴度的無監(jiān)督特征選擇算法。此后，Velayutham等［16］又提出一種基于信息熵的粗糙集無監(jiān)督特征選擇算法。與有監(jiān)督特征選擇算法相比，這些特征選擇算法將重點(diǎn)從條件屬性和決策屬性之間的關(guān)系，轉(zhuǎn)移至條件屬性之間的關(guān)系上。在模糊粗糙集領(lǐng)域，Mac Parthaláin等［17］基于依賴度、邊界區(qū)域、關(guān)系矩陣和替代模糊分辨方法，提出基于模糊粗糙集的無監(jiān)督特征選擇（Unsupervised Fuzzy-Rough Feature Selection， UFRFS）算法；Yuan等［18］使用模糊粗糙集處理無監(jiān)督混合數(shù)據(jù)，以依賴度為基礎(chǔ)定義屬性的重要度，作為特征選擇的基準(zhǔn)；Ganivada等［19］將模糊粗糙集和神經(jīng)網(wǎng)絡(luò)相結(jié)合，提出一種用于識別數(shù)據(jù)顯著特征的粒狀神經(jīng)網(wǎng)絡(luò)，以達(dá)到特征選擇的目的。

目前，基于模糊粗糙集的無監(jiān)督特征選擇算法主要是靜態(tài)特征選擇算法，在動態(tài)數(shù)據(jù)集上的研究則較少，而靜態(tài)特征選擇算法存在兩方面的問題：1）對于某個(gè)備選特征，有監(jiān)督特征選擇算法只需要計(jì)算該特征和決策屬性的度量性指標(biāo)，但無監(jiān)督特征選擇算法需要計(jì)算該特征和其他所有條件屬性的度量性指標(biāo)，運(yùn)算量大幅增加；2）在新的數(shù)據(jù)到達(dá)后，依然只能在所有數(shù)據(jù)的基礎(chǔ)上重新計(jì)算，無法有效利用之前的結(jié)果。本文提出了一種基于模糊粗糙集的無監(jiān)督動態(tài)特征選擇（Unsupervised Dynamic Fuzzy-Rough set based Feature Selection， UDFRFS）算法，該算法通過定義偽三角范數(shù)和新的相似關(guān)系，從而加快度量性指標(biāo)的計(jì)算過程，利用之前的特征選擇結(jié)果，在新的數(shù)據(jù)集到達(dá)后，減少對原始特征的冗余運(yùn)算，從而加快特征選擇的速度。在9組數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明，該算法與靜態(tài)算法和同類基于依賴度的特征選擇算法相比，在新的特征被加入數(shù)據(jù)集時(shí)能夠獲得更好的時(shí)間效率，同時(shí)保持較好的分類精度和聚類表現(xiàn)。

1 基礎(chǔ)知識

1.1　模糊粗糙集

對于模糊相似關(guān)系采用以下定義。

基于依賴度的模糊粗糙集的特征選擇過程如算法1所示。

算法1 基于依賴度的模糊粗糙集的特征選擇算法。

8） end if

10） end

1.2　基于模糊粗糙集的無監(jiān)督特征選擇

同算法1，對于無監(jiān)督的情況，依然可以通過定義一個(gè)基于依賴度的模糊粗糙集的特征選擇算法進(jìn)行特征選擇。

算法2 UFRFS。

7） end if

8） end

2 基于模糊粗糙集的無監(jiān)督動態(tài)特征選擇

在大數(shù)據(jù)時(shí)代，數(shù)據(jù)通常以分批次的形式到達(dá)。如果采用如UFRFS算法等靜態(tài)算法處理這些數(shù)據(jù)，可能造成較大的時(shí)間開銷。而動態(tài)特征選擇算法保留之前數(shù)據(jù)的計(jì)算結(jié)果，之后的計(jì)算均在這些結(jié)果的基礎(chǔ)上進(jìn)行，能夠有效降低算法的時(shí)間復(fù)雜度。

2.1　無監(jiān)督動態(tài)特征選擇下的模糊相似度、三角范數(shù)和三角余范數(shù)

證明 1）由式（3）～（4）可知：

由定理1可知，在增加屬性的情況下，新的模糊關(guān)系值和舊的模糊關(guān)系值之間沒有等量關(guān)系，不能直接用于加速運(yùn)算過程。在計(jì)算模糊關(guān)系值的時(shí)候需要使用三角范數(shù)，如果能將它擴(kuò)展，得到一個(gè)等量關(guān)系，就可以在已有基礎(chǔ)上更新模糊關(guān)系值，加快運(yùn)算速度。

證明 1）由式（14）和式（16）可知：

移項(xiàng)即可得到上述性質(zhì)。 證畢。

2）由式（14）和式（16）可知：

1）當(dāng)一個(gè)特征被加入當(dāng)前約簡集合，只需要運(yùn)用定理2的性質(zhì)2）添加該特征。

2）當(dāng)一個(gè)特征被從當(dāng)前約簡集合中去掉，只需要運(yùn)用定理2的性質(zhì)1）刪除該特征。

2.2　無監(jiān)督動態(tài)特征選擇下的向下近似

由2.1節(jié)可知，當(dāng)新的特征到達(dá)時(shí)，可以利用在原始數(shù)據(jù)集上計(jì)算的模糊關(guān)系值，增量地計(jì)算新的模糊關(guān)系值，從而降低算法的時(shí)間復(fù)雜度，但是沒有有效利用之前計(jì)算過程中產(chǎn)生的依賴度信息或特征子集信息。本節(jié)將針對此部分進(jìn)行探討。

定理4表明當(dāng)新的特征到達(dá)時(shí)，向下近似保持不變或者變大。結(jié)合式（12）～（13）可以通過推導(dǎo)得出以下結(jié)論：

特征選擇時(shí)，可以先保留原始屬性集合計(jì)算所產(chǎn)生的依賴度。在新的特征到達(dá)后，對于之前已經(jīng)計(jì)算過的部分，根據(jù)算法2，僅考慮依賴度小于1的特征。由此可以得出結(jié)論：

1）依賴度等于1的原始特征依然不被包含在約簡集合中，可以直接跳過，僅更新相似關(guān)系矩陣。

2）依賴度小于1的原始特征，現(xiàn)在有可能不在約簡集合中，需要計(jì)算。如果依賴度依然小于1，則直接跳過，僅更新相似關(guān)系矩陣；否則從該特征開始，后續(xù)所有的依賴度等于1的原始特征也需要重新計(jì)算。

3）新的特征直接重新計(jì)算依賴度。

2.3　特征分批次到達(dá)情況下基于模糊粗糙集的無監(jiān)督動態(tài)特征選擇

由2.1和2.2節(jié)，可以得到基于模糊粗糙集的無監(jiān)督動態(tài)特征選擇（UDFRFS）算法。

算法3 UDFRFS。

10） else

12） end if

13） end if

14） end

20） end if

21） end

3 實(shí)驗(yàn)與結(jié)果分析

3.1　實(shí)驗(yàn)數(shù)據(jù)

本文實(shí)驗(yàn)將針對UDFRFS算法的運(yùn)行時(shí)間、特征子集大小、分類精度和聚類表現(xiàn)進(jìn)行分析。實(shí)驗(yàn)數(shù)據(jù)集為9個(gè)來自UCI（https：//archive.ics.uci.edu/datasets）和TSC（Time Series Classification）（http：//www.timeseriesclassification.com/）的數(shù)據(jù)集，如表1所示。本文選取了UDFRFS算法的靜態(tài)版本UFRFS算法［17］、基于模糊粗糙集的無監(jiān)督屬性約簡（Fuzzy Rough-based Unsupervised Attribute Reduction， FRUAR）算法［18］和基于模糊粗糙集的無監(jiān)督和不完整數(shù)據(jù)的特征選擇（feature Selection for Unsupervised and Incomplete data based on Fuzzy Rough sets， SUIFR）算法［22］作為對比算法。

表1　數(shù)據(jù)集詳情

3.2　實(shí)驗(yàn)設(shè)計(jì)

實(shí)驗(yàn)在一臺配備了Intel Core i7-9700 CPU @ 3.00 GHz中央處理器和32 GB內(nèi)存的計(jì)算機(jī)上進(jìn)行，使用IntelIJ IDEA環(huán)境，語言平臺是Scala，分類精度和聚類表現(xiàn)的數(shù)據(jù)使用Weka平臺得到。

本文算法在特征動態(tài)變化的層面上優(yōu)化原始算法，因此將根據(jù)特征劃分各數(shù)據(jù)集，得到實(shí)驗(yàn)中所用的動態(tài)數(shù)據(jù)集。

表1中的每個(gè)數(shù)據(jù)集都將被劃分為兩個(gè)部分：原始的基礎(chǔ)數(shù)據(jù)集和原始的增量數(shù)據(jù)集。每次實(shí)驗(yàn)首先打亂數(shù)據(jù)集以排除偶然性，其次根據(jù)以下兩組實(shí)驗(yàn)的具體要求，從第0個(gè)特征開始，選擇符合條件數(shù)量的特征及其所對應(yīng)的列，作為原始的基礎(chǔ)數(shù)據(jù)集；剩下的部分作為原始的增量數(shù)據(jù)集。

實(shí)驗(yàn)將分為兩組：

1）不同基礎(chǔ)數(shù)據(jù)集大小對比實(shí)驗(yàn)。根據(jù)特征劃分，將數(shù)據(jù)集的90%作為原始的基礎(chǔ)數(shù)據(jù)集，剩下的10%作為原始的增量數(shù)據(jù)集。將原始的基礎(chǔ)數(shù)據(jù)集等量劃分成9份，首先選取第1份作為第1次實(shí)驗(yàn)使用的基礎(chǔ)數(shù)據(jù)集；其次，基于上一次實(shí)驗(yàn)所使用的基礎(chǔ)數(shù)據(jù)集，每次實(shí)驗(yàn)都按順序再選取一份進(jìn)行組合，從而產(chǎn)生9個(gè)大小依次增加的最終使用的基礎(chǔ)數(shù)據(jù)集，分別對應(yīng)9次實(shí)驗(yàn)。每次實(shí)驗(yàn)時(shí)，從原始的增量數(shù)據(jù)集中隨機(jī)選取50%的數(shù)據(jù)，作為當(dāng)次實(shí)驗(yàn)的增量數(shù)據(jù)集。

因?yàn)閁DFRFS算法需要使用基礎(chǔ)數(shù)據(jù)集的約簡結(jié)果作為輸入，所以在每次實(shí)驗(yàn)中，首先將基礎(chǔ)數(shù)據(jù)集在靜態(tài)版本的UFRFS算法上運(yùn)行一次，保存約簡結(jié)果，作為后續(xù)運(yùn)算的輸入。其次，對于所有算法，將基礎(chǔ)數(shù)據(jù)集和增量數(shù)據(jù)集結(jié)合為一個(gè)新的數(shù)據(jù)集，作為當(dāng)次實(shí)驗(yàn)需要使用到的數(shù)據(jù)集。

一次完整的實(shí)驗(yàn)需要在不同大小的數(shù)據(jù)集上運(yùn)行上述的實(shí)驗(yàn)組1）9次，實(shí)驗(yàn)組2）10次。對于每個(gè)數(shù)據(jù)集，都運(yùn)行10次完整實(shí)驗(yàn)，將每次實(shí)驗(yàn)得到的結(jié)果取平均值作為實(shí)驗(yàn)結(jié)果。在分類精度方面，選取了近鄰算法（-Nearest Neighbor，NN）（=3）、樸素貝葉斯算法（Naive Bayes， NB）和分類與回歸樹（Classification And Regression Tree， CART）這3種分類算法作為基準(zhǔn)；在聚類表現(xiàn)方面，采用-means聚類算法作為基準(zhǔn)。采用10次十折交叉驗(yàn)證（10×10-fold cross-validation）進(jìn)行實(shí)驗(yàn)，將得到結(jié)果的平均值作為實(shí)驗(yàn)結(jié)果。

3.3　實(shí)驗(yàn)結(jié)果與分析

3.3.1運(yùn)行時(shí)間

表2～3分別為3種算法在不同大小的基礎(chǔ)數(shù)據(jù)集和不同增量數(shù)據(jù)集上的運(yùn)行時(shí)間對比。其中：“TRR”表示本文算法占對比算法運(yùn)行時(shí)間的百分比；“—”表示該算法的運(yùn)行時(shí)間過長，沒有產(chǎn)生實(shí)驗(yàn)結(jié)果（由19次實(shí)驗(yàn)組成的一次完整的實(shí)驗(yàn)中，運(yùn)行前5次實(shí)驗(yàn)就已經(jīng)超過了7 h）。

從表2可以看出，相較于UFRFS，本文算法的TRR指標(biāo)在每個(gè)數(shù)據(jù)集上均低于10%，表明本文算法在每個(gè)數(shù)據(jù)集的平均執(zhí)行時(shí)間都少于靜態(tài)版本的10%，即本文算法在運(yùn)行效率方面均提升了90個(gè)百分點(diǎn)以上，即使是在特征數(shù)較多的Olive Oil和SCADI數(shù)據(jù)集，以及樣本數(shù)較多的Waveform數(shù)據(jù)集上依然能夠保持良好的表現(xiàn)。FRUAR和SUIFR這兩個(gè)算法更關(guān)注特征之間的關(guān)系，本文算法在每次循環(huán)的時(shí)候不考慮之前過程中已經(jīng)被剔除的特征，但是本文算法也考慮這一部分，因此這兩個(gè)算法的時(shí)間效率比本文算法更低。

3.3.2特征子集大小和分類精度

表4為4種算法運(yùn)行后所形成的特征子集大小的對比?？梢钥闯?，UDFRFS的特征子集大小和UFRFS完全一致。這是因?yàn)閁DFRFS基于UFRFS改進(jìn)，均基于一致的特征選擇手段，UDFRFS通過利用之前得到的中間結(jié)果加速模糊相似關(guān)系和依賴度的計(jì)算，而這些加速過程并不會影響結(jié)果。FRUAR在大部分?jǐn)?shù)據(jù)集上和前兩種算法的表現(xiàn)相近，在SAP、Divorce、Ionosphere和German上得到的特征子集略大，但是在Olive Oil、SCADI、Sonar和Wdbc上擁有更小的特征子集大小。在上述方面，F(xiàn)RUAR略微優(yōu)于UDFRFS和UFRFS，特別是在特征數(shù)較多的Olive Oil和SCADI上。但是FRUAR的時(shí)間消耗較高。對于SUIFR，它采用了高斯核作為計(jì)算模糊關(guān)系值的標(biāo)準(zhǔn)，在大部分情況下，該算法的特征子集都要遠(yuǎn)小于除Ionosphere外的其他算法。但是，特征選擇并不是特征子集越小越好，過多刪除特征也意味著有用信息的缺失會更加嚴(yán)重。

表5～7分別為經(jīng)過4種算法進(jìn)行特征選擇之后所得到的數(shù)據(jù)集在NN、NB和CART這3種分類算法下的分類精度對比，其中，“RAW1”表示沒有經(jīng)過特征選擇的原始數(shù)據(jù)集的分類精度?？梢钥闯觯琔DFRFS的分類精度和UFRFS完全一致，原因在前面已經(jīng)有所講述。FRUAR的分類精度和前兩種算法相近，在SCADI上取得了更好的效果，但是在Olive Oil和Wdbc上的效果更差。SUIFR和FRUAR在大部分情況下表現(xiàn)相近，但在SCADI、Divorce、Wdbc和German上的表現(xiàn)較差，原因是過小的特征子集雖然能夠減少后續(xù)實(shí)際使用該數(shù)據(jù)集進(jìn)行模式識別等任務(wù)時(shí)耗費(fèi)的時(shí)間，但也會因有用信息缺失過多，導(dǎo)致分類精度降低。需要注意的是，在Olive Oil上，不同算法的表現(xiàn)差異較大，這是因?yàn)樵摂?shù)據(jù)集只有30個(gè)樣本，但是卻有570個(gè)特征，并且從特征選擇的結(jié)果可以得知，該數(shù)據(jù)集包含有大量的冗余特征，這顯然影響了分類結(jié)果。

表2　不同大小基礎(chǔ)數(shù)據(jù)集上不同算法的運(yùn)行時(shí)間對比

表3　不同大小增量數(shù)據(jù)集上不同算法的運(yùn)行時(shí)間對比

表4　不同算法的特征子集大小對比

表5　不同算法在KNN下的分類精度對比 單位：%

表6　不同算法在NB下的分類精度對比 單位：%

表7　不同算法在CART下的分類精度對比 單位：%

3.3.3聚類表現(xiàn)

作為無監(jiān)督特征選擇算法，有必要對比它們在聚類算法下的表現(xiàn)。本節(jié)選用對數(shù)似然（log likelihood）作為評價(jià)指標(biāo)。使用的數(shù)據(jù)集的基本屬性如表1所示。

表8為不同算法在不同大小基礎(chǔ)數(shù)據(jù)集和不同大小增量數(shù)據(jù)集上的對數(shù)似然對比，“RAW2”表示沒有經(jīng)過特征選擇的原始數(shù)據(jù)集的對數(shù)似然。從表8的實(shí)驗(yàn)結(jié)果可以看出，除了少部分?jǐn)?shù)據(jù)集（如SAP和Wdbc），在大部分?jǐn)?shù)據(jù)集上使用這幾種特征選擇算法，聚類質(zhì)量均有不同程度的提高。在Olive Oil上，雖然UDFRFS和UFRFS得到的特征選擇后的數(shù)據(jù)集完全一樣，但個(gè)別實(shí)驗(yàn)結(jié)果存在差異，導(dǎo)致最后的平均結(jié)果有所不同，推測原因是計(jì)算過程中產(chǎn)生了誤差。

表8　不同算法在各數(shù)據(jù)集上的對數(shù)似然對比

4 結(jié)語

本文提出了一種特征分批次到達(dá)情況下基于模糊粗糙集的無監(jiān)督動態(tài)特征選擇算法，該算法通過定義偽三角范數(shù)和新的相似關(guān)系，從而加快無監(jiān)督動態(tài)特征選擇算法中模糊關(guān)系值和依賴度的計(jì)算過程，使得算法在特征分批次到達(dá)的情況下能在保證較好的特征選擇效果、分類精度和聚類表現(xiàn)的情況下大幅提升算法的時(shí)間效率，并在針對特征增加這一類型的動態(tài)數(shù)據(jù)集上取得了一定效果。未來將把該特征選擇算法應(yīng)用在其他類型的動態(tài)數(shù)據(jù)集上，探索在特征減少、樣本增加、樣本減少和特征值改變等情況下的可行性，使得算法具有更好的可擴(kuò)展性。此外，將進(jìn)一步在保證算法的執(zhí)行效率不受影響的情況下，提升該算法的特征選擇質(zhì)量，使得經(jīng)過該算法選擇得到的特征子集更小，經(jīng)過特征選擇后的數(shù)據(jù)集也能夠獲得更高的分類精度和更好的聚類性能。

[1] PAWLAK Z. Rough sets［J］. International Journal of Computing and Information Sciences， 1982， 11（5）： 341-356.

[2] DUBOIS D， PRADE H. Rough fuzzy sets and fuzzy rough sets［J］. International Journal of General Systems， 1990， 17（2/3）： 191-209.

[3] ZADEH L A. Fuzzy sets［J］. Information and Control， 1965， 8（3）： 338-353.

[4] AN S， LIU J， WANG C， et al. A relative uncertainty measure for fuzzy rough feature selection［J］. International Journal of Approximate Reasoning， 2021， 139： 130-142.

[5] CHEN J， MI J， LIN Y. A graph approach for fuzzy-rough feature selection［J］. Fuzzy Sets and Systems， 2020， 391： 96-116.

[6] YANG X， CHEN H， LI T， et al. A noise-aware fuzzy rough set approach for feature selection［J］. Knowledge-Based Systems， 2022， 250： No.109092.

[7] 章夏杰，朱敬華，陳楊. Spark下的分布式粗糙集屬性約簡算法［J］. 計(jì)算機(jī)應(yīng)用， 2020， 40（2）： 518-523.（ZHANG X J， ZHU J H， CHEN Y. Distributed rough set attribute reduction algorithm under Spark［J］. Journal of Computer Applications， 2020， 40（2）： 518-523.）

[8] 危前進(jìn)，魏繼鵬，古天龍，等. 粗糙集多目標(biāo)并行屬性約簡算法［J］. 軟件學(xué)報(bào)， 2022， 33（7）： 2599-2617.（WEI Q J， WEI J P， GU T L， et al. Multi-objective parallel attribute reduction algorithm in rough set［J］. Journal of Software， 2022， 33（7）： 2599-2617.）

[9] YANG Y， CHEN D， WANG H， et al. Fuzzy rough set based incremental attribute reduction from dynamic data with sample arriving［J］. Fuzzy Sets and Systems， 2017， 312： 66-86.

[10] WAN J， CHEN H， LI T， et al. Dynamic interaction feature selection based on fuzzy rough set［J］. Information Sciences， 2021， 581： 891-911.

[11] NI P， ZHAO S， WANG X， et al. Incremental feature selection based on fuzzy rough sets［J］. Information Sciences， 2020， 536： 185-204.

[12] 程玉勝，陳飛，王一賓. 基于粗糙集的數(shù)據(jù)流多標(biāo)記分布特征選擇［J］. 計(jì)算機(jī)應(yīng)用， 2018， 38（11）： 3105-3111， 3118.（CHENG Y S， CHEN F， WANG Y B. Feature selection for multi-label distribution learning with streaming data based on rough set［J］. Journal of Computer Applications， 2018， 38（11）： 3105-3111， 3118.）

[13] 曾藝祥，林耀進(jìn)，范凱鈞，等. 基于層次類別鄰域粗糙集的在線流特征選擇算法［J］. 南京大學(xué)學(xué)報(bào)（自然科學(xué)版）， 2022， 58（3）： 506-518.（ZENG Y X， LIN Y J， FAN K J， et al. Online streaming feature selection method based on hierarchical class neighborhood rough set［J］. Journal of Nanjing University （Natural Sciences）， 2022， 58（3）： 506-518.）

[14] SOLORIO-FERNáNDEZ S， CARRASCO-OCHOA J A， MARTíNEZ-TRINIDAD J F. A review of unsupervised feature selection methods［J］. Artificial Intelligence Review， 2020， 53（2）： 907-948.

[15] VELAYUTHAM C， THANGAVEL K. Unsupervised quick reduct algorithm using rough set theory［J］. Journal of Electronic Science and Technology， 2011， 9（3）： 193-201.

[16] VELAYUTHAM C， THANGAVEL K. A novel entropy based unsupervised feature selection algorithm using rough set theory［C］// Proceeding of the 2012 International Conference on Advances in Engineering， Science and Management. Piscataway： IEEE， 2012： 156-161.

[17] MAC PARTHALáIN N， JENSEN R. Unsupervised fuzzy-rough set-based dimensionality reduction［J］. Information Sciences， 2013， 229： 106-121.

[18] YUAN Z， CHEN H， LI T， et al. Unsupervised attribute reduction for mixed data based on fuzzy rough sets［J］. Information Sciences， 2021， 572： 67-87.

[19] GANIVADA A， RAY S S， PAL S K. Fuzzy rough sets， and a granular neural network for unsupervised feature selection［J］. Neural Networks， 2013， 48： 91-108.

[20] BEG I， ASHRAF S. Similarity measures for fuzzy sets［J］. Applied and Computational Mathematics， 2009， 8（2）： 192-202.

[21] PAP E. Pseudo-analysis in engineering decision making［M］// RUDAS I J， FODOR J， KACPRZYK J. Towards Intelligent Engineering and Information Technology， SCI 243. Berlin： Springer， 2009： 3-16.

[22] WANG L， PENG L， ZHANG G. Attribute reduction for incomplete and unsupervised data based on fuzzy rough sets［C］// Proceeding of the 16th International Conference on Intelligent Systems and Knowledge Engineering. Piscataway： IEEE， 2021： 674-679.

Fuzzy-rough set based unsupervised dynamic feature selection algorithm

MA Lei1， LUO Chuan1*， LI Tianrui2， CHEN Hongmei2

（1，，610065，；2，，611756，）

Dynamic feature selection algorithms can improve the time efficiency of processing dynamic data. Aiming at the problem that there are few unsupervised dynamic feature selection algorithms based on fuzzy-rough sets， an Unsupervised Dynamic Fuzzy-Rough set based Feature Selection （UDFRFS） algorithm was proposed under the condition of features arriving in batches. First， by defining a pseudo triangular norm and new similarity relationship， the process of updating fuzzy relation value was performed on the basis of existing data to reduce unnecessary calculation. Then， by utilizing the existing feature selection results， dependencies were adopted to judge if the original feature part would be recalculated to reduce the redundant process of feature selection， and the feature selection was further speeded up. Experimental results show that compared to the static dependency-based unsupervised fuzzy-rough set feature selection algorithm， UDFRFS can achieve the time efficiency improvement of more than 90 percentage points with good classification accuracy and clustering performance.

feature selection; fuzzy-rough set; dynamic data; unsupervised feature selection; dependency

This work is partially supported by National Natural Science Foundation of China （62076171）， Natural Science Foundation of Sichuan Province （2022NSFSC0898）.

MA Lei， born in 1997， M. S. candidate. His research interests include feature selection.

LUO Chuan， born in 1987， Ph. D.， associate professor. His research interests include data mining， granular computing.

LI Tianrui， born in 1969， Ph. D.， professor. His research interests include data mining， granular computing.

CHEN Hongmei， born in 1971， Ph. D.， professor. Her research interests include data mining， granular computing.

1001-9081（2023）10-3121-08

10.11772/j.issn.1001-9081.2022101543

2022?10?17；

2022?11?28；

國家自然科學(xué)基金資助項(xiàng)目（62076171）；四川省自然科學(xué)基金資助項(xiàng)目（2022NSFSC0898）。

馬磊（1997—），男（回族），四川成都人，碩士研究生，主要研究方向：特征選擇； 羅川（1987—），男，河南固始人，副教授，博士，主要研究方向：數(shù)據(jù)挖掘、粒計(jì)算； 李天瑞（1969—），男，福建莆田人，教授，博士，CCF會員，主要研究方向：數(shù)據(jù)挖掘、粒計(jì)算； 陳紅梅（1971—），女，四川成都人，教授，博士，CCF會員，主要研究方向：數(shù)據(jù)挖掘、粒計(jì)算。

TP301.6

A

2022?11?30。