局部視角下的鄰域粒度及其屬性約簡(jiǎn)

摘" 要： 在基于粗糙集的粒計(jì)算中，鄰域粒度是常見(jiàn)的信息粒化表現(xiàn)之一.鄰域粒度在不同條件屬性之間存在一定差異，如果條件屬性生成的鄰域粒度越細(xì)，那么該條件屬性對(duì)樣本的區(qū)分性越強(qiáng).條件屬性在全局樣本上生成的鄰域粒度，即在全局視角下，會(huì)存在一些局限性，例如多個(gè)條件屬性可能會(huì)生成相同或相似的鄰域粒度，這樣不利于對(duì)條件屬性作進(jìn)一步區(qū)分.為了彌補(bǔ)這樣的缺陷，首先從局部視角出發(fā)，提出了局部鄰域粒度的概念.與全局視角生成的鄰域粒度不同，計(jì)算局部鄰域粒度首先對(duì)全部樣本進(jìn)行分割，然后對(duì)分割后的樣本分別計(jì)算鄰域粒度.其次，基于局部鄰域粒度提出了一種屬性約簡(jiǎn)改進(jìn)算法，該算法主要思想是以局部鄰域粒度為準(zhǔn)則，在選擇條件屬性時(shí)剔除對(duì)樣本區(qū)分性較弱的條件屬性.在UCI數(shù)據(jù)集上選取12組數(shù)據(jù)集，在兩種不同的度量條件下，提出的算法與另外兩種算法進(jìn)行對(duì)比實(shí)驗(yàn).實(shí)驗(yàn)結(jié)果表明，與另外兩種算法相比，文中算法在分類(lèi)準(zhǔn)確率和分類(lèi)穩(wěn)定性上都有明顯優(yōu)勢(shì).

關(guān)鍵詞： 屬性約簡(jiǎn)；鄰域粒度；鄰域粗糙集；局部鄰域粒度

中圖分類(lèi)號(hào)：TP18"" "文獻(xiàn)標(biāo)志碼：A""""" 文章編號(hào)：1673-4807（2024）05-092-08

DOI：10.20061/j.issn.1673-4807.2024.05.014

收稿日期： 2023-08-26""" 修回日期： 2021-04-29

基金項(xiàng)目： 國(guó)家自然科學(xué)基金項(xiàng)目（62006099， 62076111）；浙江省海洋大數(shù)據(jù)挖掘與應(yīng)用重點(diǎn)實(shí)驗(yàn)室開(kāi)放課題（OBDMA202104）

作者簡(jiǎn)介： 徐天喜（1999—）， 男，碩士研究生

*通信作者： 宋晶晶（1990—），女，博士， 副教授， 研究方向?yàn)槟：?、粗糙集、粒?jì)算. E-mail： songjingjing108@163.com

引文格式： 徐天喜，宋晶晶，陳建軍，等.局部視角下的鄰域粒度及其屬性約簡(jiǎn)［J］.江蘇科技大學(xué)學(xué)報(bào)（自然科學(xué)版），202 38（5）：92-99.DOI：10.20061/j.issn.1673-4807.2024.05.014.

Neighborhood granularity and attribute reduction from a local perspective

XU Tianxi1，SONG Jingjing1*，CHEN Jianjun1，XU Taihua1， 2

（1.School of Computer， Jiangsu University of Science and Technology， Zhenjiang 212003， China）

（2.Key Laboratory of Marine Big Data Mining amp; Application， Zhejiang Ocean University， Zhoushan 316022， China）

Abstract：In granular computing based on rough sets， neighborhood granularity based on neighborhood relationships is one representation of information granulation. The neighborhood granularity generated by different conditional attributes， and finer neighborhood granularity can result in a stronger differentiation of samples by the conditional attributes. However， previous research has mostly focused on the global perspective of neighborhood granularity generated by conditional attributes on the whole sample set， which may have limitations. For example， multiple conditional attributes may generate similar neighborhood granularities， making it difficult to differentiate the conditional attributes further. To fill the gap， this paper proposes the concept of local neighborhood granularity from a local perspective. Different from global neighborhood granularity， firstly the whole sample set is partitioned when calculating local neighborhood granularity and then the neighborhood granularity computed for each partition. Based on local neighborhood granularity， this paper proposes an attribute reduction algorithm that uses local neighborhood granularity as a criterion and remove conditional attributes having weak discriminative power for the samples when selecting conditional attributes. The proposed algorithm is compared with other algorithms using two different metric criteria in experiments performed on 12 UCI datasets. The experimental results show that the proposed algorithm has significant advantages in classifying accuracy and stability compared with the other algorithms.

Key words：attribution reduction， neighborhood granularity， neighborhood rough set， local neighborhood granularity

粗糙集理論［1］是一種處理不確定信息的數(shù)學(xué)工具，在數(shù)據(jù)挖掘、人工智能等領(lǐng)域受到學(xué)者們的廣泛關(guān)注.但是，最初的粗糙集理論不適用于處理連續(xù)型數(shù)據(jù)，因此，對(duì)粗糙集模型進(jìn)行了擴(kuò)展.文獻(xiàn)［2］結(jié)合粗糙集理論和模糊集理論提出模糊粗糙集理論，模糊粗糙集理論將粗糙集理論中的等價(jià)關(guān)系替換為模糊相似關(guān)系.文獻(xiàn)［3］針對(duì)粗糙集模型的基本假設(shè)為單尺度問(wèn)題提出了Wu-Leung模型，使得粗糙集理論可在不同尺度下對(duì)數(shù)據(jù)進(jìn)行表示、分析和決策.

為了進(jìn)一步拓展粗糙集的應(yīng)用范圍，文獻(xiàn)［4］基于鄰域關(guān)系，提出了鄰域粗糙集.從粒計(jì)算的角度來(lái)看，鄰域可以有效并且直觀地解釋信息粒和信息粒化的過(guò)程從而得到許多學(xué)者的青睞.隨著對(duì)鄰域粗糙集的深入研究，發(fā)現(xiàn)鄰域粗糙集可能面臨著兩種挑戰(zhàn)：挑戰(zhàn)一在于鄰域半徑對(duì)整個(gè)鄰域粗糙集模型影響較大.文獻(xiàn)［5］發(fā)現(xiàn)在數(shù)據(jù)的原始標(biāo)簽下，鄰域半徑對(duì)鄰域關(guān)系的分辨能力的影響過(guò)于苛刻，于是結(jié)合無(wú)監(jiān)督和半監(jiān)督學(xué)習(xí)任務(wù)中的偽標(biāo)簽策略提出了基于偽標(biāo)簽鄰域關(guān)系的偽標(biāo)簽鄰域粗糙集.為了解決無(wú)監(jiān)督下的鄰域關(guān)系可能導(dǎo)致鄰域信息不一致或不精確的問(wèn)題，文獻(xiàn)［6］提出了有監(jiān)督下鄰域信息?；呗?，通過(guò)類(lèi)內(nèi)半徑和類(lèi)外半徑從鄰域中刪除不同標(biāo)簽樣本.文獻(xiàn)［7］提出粒球粗糙集模型，實(shí)現(xiàn)了自適應(yīng)信息粒化.挑戰(zhàn)二在于鄰域粗糙集在處理大規(guī)模數(shù)據(jù)集時(shí)計(jì)算復(fù)雜度較高.文獻(xiàn)［8］基于局部粗糙集提出局部鄰域粗糙集模型，該模型在處理大規(guī)模數(shù)據(jù)集時(shí)，具有顯著的算法效率優(yōu)勢(shì).文獻(xiàn)［9］采用鄰域粒度壓縮了候選條件屬性的空間，雖然一定程度上提高了約簡(jiǎn)算法的執(zhí)行效率，但是仍然避免不了對(duì)條件屬性的迭代計(jì)算.文獻(xiàn)［10］采用鄰域粒度從細(xì)粒度到粗粒度的方式對(duì)條件屬性進(jìn)行預(yù)排序，省去了對(duì)條件屬性的迭代計(jì)算，提高了算法的執(zhí)行效率.

文中從局部的視角提出局部鄰域粒度的概念，基于局部鄰域粒度，同時(shí)結(jié)合排序思想設(shè)計(jì)一種新的屬性約簡(jiǎn)算法.不同于全局鄰域粒度的計(jì)算方法，在計(jì)算局部鄰域粒度時(shí)，需要將一個(gè)樣本集分割為多份，得到多個(gè)樣本子集.根據(jù)樣本的決策屬性將樣本集進(jìn)行分割，然后在每個(gè)樣本子集上計(jì)算鄰域粒度.與全局鄰域粒度相比，局部鄰域粒度可以更詳細(xì)地體現(xiàn)條件屬性間的差別，有利于提高約簡(jiǎn)算法的分類(lèi)準(zhǔn)確率和分類(lèi)穩(wěn)定性.

1" 背景知識(shí)

1.1" 鄰域粗糙集

在鄰域粗糙集中，可以用一個(gè)二元組DS=lt;U，AT∪j5i0abt0bgt;表示一個(gè)決策系統(tǒng)，U={x1，x2，…，xn}是所有樣本的非空有限集合，被稱(chēng)為論域，AT是條件屬性的集合，AAT，由A誘導(dǎo)的不可分辨關(guān)系表示為INDA={x，y∈U2：a∈A，ax=a（y）}，d是決策屬性.根據(jù)決策屬性將論域劃分為n個(gè)等價(jià)類(lèi)，表示為U/INDd={X1，X2，…，Xn}.

定義1［4］" 給定一個(gè)決策系統(tǒng)DS=lt;U，AT∪j5i0abt0bgt;，AAT，x，y∈U，樣本x，y之間歐式距離SA（x，y）為：

SA（x，y）=" ∑a∈A（a（x）-a（y））2（1）

定義2［4］" 給定一個(gè)決策系統(tǒng)DS=lt;U，AT∪j5i0abt0bgt;，AAT，σ是給定的鄰域半徑，由條件屬性子集A生成的鄰域關(guān)系 RA為：

RA={（x，y）∈U2|SA（x，y）≤σ}（2）

xi∈U，根據(jù)鄰域關(guān)系RA可以得到xi的鄰域RA（xi），RAxi={xj∈U：（xi，xj）∈RA}.

定義3［4］" 給定一個(gè)決策系統(tǒng)DS=lt;U，AT∪j5i0abt0bgt;，AAT，等價(jià)類(lèi)Xn關(guān)于條件屬性子集A的上下近似集合定義為：

NA（Xn）={x∈U：RA（x）∩Xn≠}

NA（Xn）={x∈U：RA（x）Xn}（3）

1.2" 相對(duì)鄰域自信息

在鄰域粗糙集中，上近似集合中樣本的信息往往會(huì)被忽略.文獻(xiàn)［11］不僅考慮了下近似集合中樣本的信息，而且利用了易被忽略的上近似集合中樣本的信息，提出了相對(duì)鄰域自信息，使構(gòu)造出的度量函數(shù)更加全面.

定義4［11］" 給定一個(gè)決策系統(tǒng)DS=lt;U，AT∪j5i0abt0bgt;，d是決策屬性，AAT，等價(jià)類(lèi)Xn關(guān)于條件屬性子集A的決策精度μA（Xn）和粗糙度VA（Xn）分別為：

μA（Xn）=NA（Xn）NA（Xn）

VA（Xn）=1-μA（Xn）（4）

式中：NA（Xn）為下近似集合中的樣本數(shù)量；NA（Xn）為上近似集合中的樣本數(shù)量；μA（Xn）和VA（Xn）的取值范圍都為［0，1］.

定義5［11］" 給定一個(gè)決策系統(tǒng)DS=lt;U，AT∪j5i0abt0bgt;，Xn∈U/INDd，AAT，相對(duì)鄰域自信息定義為：

IA（Xn）=-VA（Xn）log μA（Xn）

IA（d）=∑ni=1IA（Xn）（5）

IA（Xn）表示的是等價(jià)類(lèi)Xn關(guān)于條件屬性子集A的相對(duì)鄰域自信息，所有等價(jià)類(lèi)的相對(duì)鄰域自信息的和就構(gòu)成了整個(gè)決策系統(tǒng)的相對(duì)鄰域自信息IA（d），當(dāng)IA（d）等于0時(shí)，U中的所有樣本都可以通過(guò)條件屬性子集A完全分類(lèi)到它們各自的類(lèi)別中.從相對(duì)鄰域自信息的定義可以看出，相對(duì)鄰域自信息不僅包含上近似集合中樣本的信息還包含下近似集合中樣本的信息.同時(shí)，如果一個(gè)條件屬性子集的相對(duì)鄰域自信息越小，說(shuō)明該條件屬性子集越有助于樣本分類(lèi).

1.3" 鄰域判別指數(shù)

定義6［5］" 給定一個(gè)決策系統(tǒng)DS=lt;U，AT∪j5i0abt0bgt;，AAT，條件屬性子集A的鄰域判別指數(shù)定義為：

NDIAd=logRARA∩INDd（6）

式中：RA表示由條件屬性子集A生成的鄰域中的樣本數(shù)量，RA∩INDd表示條件屬性子集A生成的鄰域與決策屬性d生成的不可分辨關(guān)系INDd的交集中的樣本數(shù)量.

NDIA（d）代表鄰域關(guān)系的判別能力，NDIA（d）指數(shù)越小，鄰域關(guān)系的判別能力越強(qiáng)，當(dāng)NDIA（d）為0時(shí)，U中的所有樣本都可以通過(guò)條件屬性子集A完全分類(lèi)到它們各自的類(lèi)別中.

1.4" 屬性約簡(jiǎn)

屬性約簡(jiǎn)［6，9］原始條件屬性基礎(chǔ)之上，刪除一些冗余的條件屬性，進(jìn)而對(duì)數(shù)據(jù)進(jìn)行降維，降低了后續(xù)學(xué)習(xí)的復(fù)雜性，提高學(xué)習(xí)器的泛化能力，所以被廣泛應(yīng)用于機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘等領(lǐng)域.文獻(xiàn)［12］總結(jié)了屬性約簡(jiǎn)的一般形式，如定義7.

定義7［12］" 給定一個(gè)決策系統(tǒng)DS=lt;U，AT∪j5i0abt0bgt;，AAT，Cρ是關(guān)于度量ρ的約束條件，包容度ε，若A滿(mǎn)足以下條件，則稱(chēng)A是關(guān)于Cρ的一個(gè)約簡(jiǎn).

（1） A滿(mǎn)足約束條件Cρ.

（2） A′A，A′不滿(mǎn)足約束條件.

根據(jù)不同的度量構(gòu)建約束條件時(shí)，一般情況下要考慮度量的正相關(guān)性和負(fù)相關(guān)性.如果度量ρ是正相關(guān)的，則度量值越高越好.例如，近似質(zhì)量［4］，此時(shí)Cρ通常表示為ρ（A）ρ（AT）·ε；如果度量ρ是負(fù)相關(guān)的，則度量值越低越好.例如上面介紹的相對(duì)鄰域自信息，此時(shí)Cρ通常表示為ρ（A）·ε≤ρ（AT），其中ε是包容度，是為了防止約束條件過(guò)于嚴(yán)苛，導(dǎo)致約簡(jiǎn)過(guò)程中刪除過(guò)多屬性而設(shè)置的.

基于屬性約簡(jiǎn)的一般形式采用不同類(lèi)型的搜索算法，貪心搜索算法因其較快的迭代速度，較低的時(shí)間復(fù)雜度而受到學(xué)者們的關(guān)注［9］.算法1介紹了前向貪心屬性約簡(jiǎn)算法求解過(guò)程.

算法1：前向貪心屬性約簡(jiǎn)算法

輸入：一個(gè)決策系統(tǒng)DS=lt;U，AT∪j5i0abt0bgt;，度量ρ.

輸出：約簡(jiǎn)集合red.

（1）初始化，令red=；

（2）While red不滿(mǎn)足約束條件Cρ do

（3）a∈AT-red，計(jì)算ρ（red∪{a}）；

（4）找出當(dāng)前迭代過(guò)程中一個(gè)合適的條件屬性b∈AT-red；

（5）red=red∪；

（6）計(jì)算ρ（red）；

（7）End while

（8）Return red.

在算法1執(zhí)行過(guò)程中，首先將約簡(jiǎn)集合初始化為空集合，根據(jù)度量選擇合適的屬性，直至整個(gè)約簡(jiǎn)集合滿(mǎn)足對(duì)應(yīng)的約束條件，然后返回約簡(jiǎn)集合，最后算法結(jié)束.

算法1在每次迭代的過(guò)程中，需要對(duì)候選池中所有條件屬性進(jìn)行評(píng)估，這種方式顯然是費(fèi)時(shí)的.在求解約簡(jiǎn)的過(guò)程中，考慮在最壞的情況下，條件屬性集合AT中的每個(gè)條件屬性都需要被評(píng)估，所以算法1的時(shí)間復(fù)雜度為O（U2·AT2）.

1.5" 全局鄰域粒度

在粒計(jì)算理論中，粒度這一概念通常反映了信息?；某潭?目前對(duì)粒度的語(yǔ)義解釋?zhuān)?］分為：

（1） 基于參數(shù)的粒度.粒度與指定的參數(shù)密切相關(guān).一般情況下，較小的參數(shù)值會(huì)生成更加精細(xì)的粒度.例如，在鄰域粗糙集中，較小的鄰域半徑可以生成較小的樣本鄰域，因此將獲得更細(xì)的粒度.

（2） 基于屬性的粒度.通常來(lái)說(shuō)，如果屬性的區(qū)分性越強(qiáng)，那么該屬性就會(huì)生成更精細(xì)的粒度.例如，在鄰域粗糙集中，相同的鄰域半徑下，不同條件屬性集合所生成的粒度可能是不同的.當(dāng)條件屬性的個(gè)數(shù)越多，粒度值越小，樣本間的區(qū)分度就越大.

（3） 基于樣本的粒度.不同樣本集之間的粒度是有所不同的.例如，在5折交叉驗(yàn)證中，將原始樣本均分為5組不同的訓(xùn)練集和測(cè)試集，這一過(guò)程產(chǎn)生了5種信息?；慕Y(jié)果，因?yàn)槊拷M的樣本集所包含的測(cè)試集和訓(xùn)練集是明顯不同的.

基于鄰域關(guān)系生成的粒度既體現(xiàn)了基于參數(shù)的粒度，又體現(xiàn)了基于屬性的粒度［9］.下面將介紹關(guān)于全局鄰域粒度的相關(guān)定義和性質(zhì).

定義8［10］" 給定一個(gè)決策系統(tǒng)DS=lt;U，AT∪j5i0abt0bgt;，AAT，全局鄰域粒度定義為：

GA（U）=∑xn∈URA（xn）U2（7）

式中：RA（xn） 為xn鄰域中的樣本數(shù)量；U為整個(gè)樣本集的樣本數(shù)量；GA（U）的取值范圍為［1U，1］.GA（U）反映某一條件屬性子集在全局樣本上生成的鄰域粒度粗細(xì).換句話說(shuō)，GA（U）的值越小，代表?xiàng)l件屬性子集生成的鄰域粒度越細(xì)，該條件屬性子集越有助于對(duì)樣本進(jìn)行區(qū)分.GA（U）的值越大，代表?xiàng)l件屬性子集生成的鄰域粒度越粗，該條件屬性子集越不利于對(duì)樣本進(jìn)行區(qū)分.

根據(jù)定義 在相同樣本下，根據(jù)不同條件屬性生成的鄰域粒度大小對(duì)條件屬性進(jìn)行區(qū)分.文獻(xiàn)［10］基于全局鄰域粒度提出了一種對(duì)條件屬性預(yù)排序的算法.該算法先在整個(gè)樣本集上，求出每個(gè)條件屬性生成的全局鄰域粒度，然后依據(jù)這些粒度值對(duì)條件屬性進(jìn)行升序排列.在屬性約簡(jiǎn)的過(guò)程中，先考慮全局鄰域粒度較細(xì)的條件屬性，并且這一算法避免了算法1中會(huì)對(duì)條件屬性迭代計(jì)算的缺點(diǎn)，因此降低了屬性約簡(jiǎn)算法的時(shí)間復(fù)雜度.算法2將詳細(xì)介紹該算法流程.

算法2：基于全局鄰域粒度的屬性約簡(jiǎn)算法

輸入：一個(gè)決策系統(tǒng)DS=lt;U，AT∪j5i0abt0bgt;，度量ρ，鄰域半徑σ.

輸出：約簡(jiǎn)集合red.

（1） 初始化，令red=；

（2） ak∈AT，計(jì)算Gak（U）；

（3） 根據(jù)步驟2計(jì)算的鄰域粒度對(duì)條件屬性進(jìn)行升序排序：a a …，ak；

（4） While red不滿(mǎn)足約束條件Cρ do

（5） For i=" …，k do

（6） red=red∪{ai}

（7） If red滿(mǎn)足約束條件Cρ then

（8） Break;

（9） Else if then

（10） 返回步驟6；

（11） End if

（12） End for

（13） End while

（14） Return red.

在算法2中，條件屬性集合AT中的所有條件屬性都已經(jīng)預(yù)先進(jìn)行了排序，在求解約簡(jiǎn)的過(guò)程中，只需要依次將條件屬性放入約簡(jiǎn)集合中.在最壞的情況下，條件屬性集合AT中的所有條件屬性都需要進(jìn)行評(píng)估，因此算法2的時(shí)間復(fù)雜度為O（U2·AT）.

2" 局部鄰域粒度屬性約簡(jiǎn)

2.1" 局部鄰域粒度

從全局的角度出發(fā)往往會(huì)忽略局部的細(xì)節(jié)，在利用全局鄰域粒度進(jìn)行屬性約簡(jiǎn)的過(guò)程中，可能會(huì)存在多個(gè)不同的條件屬性生成相同或相似的鄰域粒度，這樣會(huì)對(duì)屬性約簡(jiǎn)造成一定的困擾.

定義9" 給定一個(gè)決策系統(tǒng)DS=lt;U，AT∪j5i0abt0bgt;，AAT，Xn∈U/INDd，條件屬性子集A在某一等價(jià)類(lèi)Xn樣本上生成的局部鄰域粒度：

LGAXn=∑xn∈XnRAxnXn2（8）

式中：Xn為等價(jià)類(lèi)Xn樣本的數(shù)量；LGA（Xn）的取值范圍為［1Xn，1］.

局部鄰域粒度LGA（Xn），反映了條件屬性子集在不同等價(jià)類(lèi)樣本上生成鄰域粒度的粗細(xì).LGA（Xn）的值越小，說(shuō)明該條件屬性子集在某個(gè)等價(jià)類(lèi)樣本上生成的鄰域越細(xì)，該條件屬性子集就越有利于樣本間的區(qū)分.用例1來(lái)說(shuō)明全局鄰域粒度與局部鄰域粒度的區(qū)別.

例1.以UCI公開(kāi)數(shù)據(jù)集中選取的“Iris”數(shù)據(jù)集為例，Iris數(shù)據(jù)集擁有150個(gè)樣本，5個(gè)屬性，其中包括4個(gè)條件屬性、1個(gè)決策屬性.決策屬性分為3種，每種樣本的個(gè)數(shù)為50個(gè).在此數(shù)據(jù)集上取相同的鄰域半徑（取0.01），觀察各條件屬性在全局樣本上生成的全局鄰域粒度與在各個(gè)決策類(lèi)樣本上生成的局部鄰域粒度之間粒度的區(qū)別.

表1是各個(gè)條件屬性在全局樣本下生成的鄰域粒度，表2是各個(gè)條件屬性在不同決策類(lèi)樣本上生成的局部鄰域粒度.觀察表 條件屬性a2和a 兩者的鄰域粒度分別為0.078" 0.077" 那么在這種情況下，以全局的角度觀察兩個(gè)條件屬性對(duì)樣本的區(qū)分程度是相似的.以局部的角度去觀察，表2中，條件屬性a2和a4在等價(jià)類(lèi)X1上生成的鄰域粒度分別為0.098" 0.368" 并且a2生成的粒度明顯比a4生成的要細(xì).因此在局部視角下，a2對(duì)樣本的區(qū)分能力更強(qiáng)，所以在屬性約簡(jiǎn)的過(guò)程中應(yīng)該優(yōu)先選擇條件屬性a2.

2.2" 局部鄰域粒度屬性約簡(jiǎn)算法

為了彌補(bǔ)不同條件屬性可能會(huì)在全局樣本上生成相同或相似的鄰域粒度這樣的缺陷，提出局部鄰域粒度的相關(guān)概念，并結(jié)合算法2的排序思想，設(shè)計(jì)了新的屬性約簡(jiǎn)算法，文中簡(jiǎn)稱(chēng)算法3.在算法3中通過(guò)對(duì)樣本的分割，構(gòu)造多個(gè)樣本子集，從而對(duì)不同條件屬性的鄰域粒度進(jìn)行更加詳細(xì)的對(duì)比.

算法3：基于局部鄰域粒度的屬性約簡(jiǎn)算法

輸入：一個(gè)決策系統(tǒng)DS=lt;U，AT∪j5i0abt0bgt;，度量ρ，鄰域半徑σ.

輸出：約簡(jiǎn)集合red.

（1） 初始化，令red=；

（2） For Xi in U/INDd do

（3） ak∈AT，計(jì)算LGak（Xi）；

（4） End for

（5） For ak in AT do

（6） ak∈AT，MLGak=min（LGak（Xi））；

（7） End for

（8） 根據(jù)步驟6計(jì)算的MLGak對(duì)條件屬性進(jìn)行升序排序：a a …，ak；

（9） While red不滿(mǎn)足約束條件Cρ do

（10） For i=" …，k do

（11） red=red∪{ai}

（12） If red滿(mǎn)足約束條件Cρ then

（13） Break;

（14） Else if then

（15） 返回步驟11；

（16）" End if

（17） End for

（18） End while

（19） Return red.

算法3在求解約簡(jiǎn)的過(guò)程中同樣預(yù)先對(duì)條件屬性進(jìn)行了排序，在最壞的情況下，條件屬性集合AT中的所有條件屬性都需要進(jìn)行評(píng)估，因此算法3的時(shí)間復(fù)雜度為O（U2·AT）.

例2.用一個(gè)簡(jiǎn)單的例子對(duì)算法3的流程進(jìn)行說(shuō)明.以表2中在Iris數(shù)據(jù)集上求得的局部鄰域粒度為例，以鄰域判別指數(shù)為度量，算法3的具體過(guò)程如下：

（1） 令約簡(jiǎn)集合red=.

（2） 根據(jù)公式（6）計(jì)算NDIAT（d）=0.

（3） 計(jì)算各個(gè)條件屬性在每類(lèi)樣本上的鄰域粒度大小.

（4） 選擇每個(gè)條件屬性最小的鄰域粒度值為：a1=0.064" a2=0.096" a3=0.068" a4=0.126 4.

（5） 對(duì)條件屬性進(jìn)行排序：a a a a4.

（6） 將條件屬性a1加入到約簡(jiǎn)集合red之中，此時(shí)red={a1}，計(jì)算NDIred（d）=1.736" NDIred（d）·0.95 =1.649" 所以NDIred（d）·0.95gt;NDIAT（d），不滿(mǎn)足約束條件，所以繼續(xù)選擇條件屬性.

（7） 將條件屬性a3加入到約簡(jiǎn)集合red之中，此時(shí)red={a1，a3}，計(jì)算NDIred（d）=1.386" NDIred（d）·0.95 =1.317" 所以NDIred（d）·0.95gt;NDIAT（d），不滿(mǎn)足約束條件，所以繼續(xù)選擇條件屬性.

（8） 將條件屬性a2加入到約簡(jiǎn)集合red之中，此時(shí)red={a1，a3，a2}，計(jì)算NDIred（d）= NDIred（d）·0.95 = 所以NDIred（d）·0.95=NDIAT（d），滿(mǎn)足約束條件，所以停止選擇條件屬性.

（9） 返回約簡(jiǎn)集合red={a1，a3，a2}.

3" 實(shí)驗(yàn)分析

為了驗(yàn)證所提出算法的有效性，從UCI數(shù)據(jù)集（https：∥archive-beta.ics.uci.edu/）上選取12組數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，數(shù)據(jù)集的具體描述如表 實(shí)驗(yàn)均采用MATLAB R2017a實(shí)現(xiàn)，操作系統(tǒng)為Windows 1 CPU為Intel Core i7-8750H，內(nèi)存為16.00 GB.

3.1" 分類(lèi)準(zhǔn)確率對(duì)比

實(shí)驗(yàn)采用K最近鄰（K-nearest neighbor，KNN）（K=3）和支持向量機(jī)（support vector machine，SVM）（默認(rèn)參數(shù)）兩種分類(lèi)器分別對(duì)所求得的約簡(jiǎn)的分類(lèi)性能進(jìn)行測(cè)試.根據(jù)以往的經(jīng)驗(yàn)，為防止過(guò)大的鄰域半徑導(dǎo)致保留過(guò)多冗余條件屬性，鄰域半徑取0.02～0. 步長(zhǎng)為0.0 共10個(gè)半徑，包容度ε取0.95.在每個(gè)半徑下，進(jìn)行10折交叉驗(yàn)證，每一輪使用9折樣本求得約簡(jiǎn)結(jié)果后，使用剩下的樣本進(jìn)行分類(lèi)測(cè)試，最終對(duì)每個(gè)半徑下的平均分類(lèi)準(zhǔn)確率取平均值，其結(jié)果分別如表4和表5.

表4和表5分別是3種不同算法在鄰域判別指數(shù)（表中簡(jiǎn)稱(chēng)判別指數(shù)）和相對(duì)鄰域自信息（表中簡(jiǎn)稱(chēng)自信息）為度量下的準(zhǔn)確率.在3種算法的對(duì)比實(shí)驗(yàn)結(jié)果中，實(shí)驗(yàn)最優(yōu)的結(jié)果已被加粗顯示，以便觀察實(shí)驗(yàn)結(jié)果.通過(guò)對(duì)比表4和表5所描述的結(jié)果，可以發(fā)現(xiàn)：

（1） 文中提出的算法3在決策屬性類(lèi)別較多的樣本集有比較好的表現(xiàn)，以表4中有10種決策屬性類(lèi)別的“Cardiotocography（ID：2）”為例，在表4中3種算法采用兩種不同的不確定性度量進(jìn)行約束，算法1和算法2在鄰域判別指數(shù)下的所求得約簡(jiǎn)對(duì)應(yīng)的KNN分類(lèi)準(zhǔn)確率分別為0.615 7和0.628" 算法3對(duì)應(yīng)的KNN分類(lèi)準(zhǔn)確率為0.635 2.

（2） 通過(guò)觀察表4和表 不論是以鄰域判別指數(shù)還是以相對(duì)鄰域自信息構(gòu)造約束，算法3在KNN分類(lèi)器和SVM分類(lèi)器上擁有最好的平均分類(lèi)準(zhǔn)確率.以表5中的SVM平均分類(lèi)準(zhǔn)確率為例，算法1和算法2在鄰域判別指數(shù)下的所求得的約簡(jiǎn)對(duì)應(yīng)的平均SVM分類(lèi)準(zhǔn)確率分別為0.807 9和0.811" 算法3對(duì)應(yīng)的平均SVM分類(lèi)準(zhǔn)確率為0.814 4.

上述對(duì)實(shí)驗(yàn)結(jié)果的觀察分析是在相同的不確定性度量下對(duì)比不同算法之間的分類(lèi)準(zhǔn)確率.換個(gè)角度，觀察相同算法在不同的不確定性度量的分類(lèi)準(zhǔn)確率差別.

算法2和算法3在SVM分類(lèi)器下對(duì)不同的度量擁有相同的分類(lèi)準(zhǔn)確率，以表5中的數(shù)據(jù)集“Heart（statlog）（ID：9）”為例，算法3在以鄰域判別指數(shù)為約束的情況下，KNN的分類(lèi)準(zhǔn)確率為0.788" 在相對(duì)鄰域自信息為約束的KNN分類(lèi)準(zhǔn)確率同樣是0.788 9.這種情況可能有以下兩種原因造成的.

首先，可能是鄰域判別指數(shù)和相對(duì)鄰域自信息這兩種度量之間存在相似性，兩種度量都是負(fù)相關(guān)的，意味著兩者都是度量值越低，表明條件屬性分類(lèi)能力越強(qiáng).

其次，算法2和算法3在約簡(jiǎn)過(guò)程中都是根據(jù)條件屬性的鄰域粒度提前對(duì)其進(jìn)行排序，選擇條件屬性時(shí)不會(huì)受度量的影響.但是算法1是根據(jù)度量值挑選合適的條件屬性，所以在約簡(jiǎn)過(guò)程中會(huì)受到不同度量的影響.這也從側(cè)面反映算法2和算法3面對(duì)不同的度量時(shí)可能會(huì)有更好的穩(wěn)定性.

3.2" 分類(lèi)穩(wěn)定性對(duì)比

分類(lèi)穩(wěn)定性［13］是一種對(duì)約簡(jiǎn)后條件屬性的分類(lèi)穩(wěn)定性的衡量方法，例如執(zhí)行兩次約簡(jiǎn)算法，兩次約簡(jiǎn)結(jié)果在分類(lèi)器上預(yù)測(cè)結(jié)果完全一致，則該約簡(jiǎn)算法的分類(lèi)穩(wěn)定性就是1.分類(lèi)穩(wěn)定性越高，則代表后續(xù)學(xué)習(xí)結(jié)果越穩(wěn)定.

為確保實(shí)驗(yàn)的有效性，同樣使用10折交叉驗(yàn)證法進(jìn)行實(shí)驗(yàn).表6和表7分別描述的是各算法在兩種不同的度量下求出的約簡(jiǎn)結(jié)果，在KNN分類(lèi)器和SVM分類(lèi)器的分類(lèi)穩(wěn)定性對(duì)比.通過(guò)對(duì)比表6和表7所描述的結(jié)果，可以發(fā)現(xiàn)：

（1） 當(dāng)條件屬性較多時(shí)，文中提出的算法3擁有較高的分類(lèi)穩(wěn)定性.以表6中有6 401個(gè)屬性的“DrivFace（ID：4）”為例，算法1和算法2在鄰域判別指數(shù)下的所求得的約簡(jiǎn)對(duì)應(yīng)的KNN分類(lèi)穩(wěn)定性分別為0.989 0和0.995" 算法3對(duì)應(yīng)的KNN分類(lèi)穩(wěn)定性為0.996 0.算法1和算法2在相對(duì)鄰域自信息下所求得的約簡(jiǎn)對(duì)應(yīng)的KNN分類(lèi)穩(wěn)定性分別為0.979 5和0.988" 算法3所對(duì)應(yīng)的KNN分類(lèi)穩(wěn)定性為0.991 0.

（2） 相比算法 算法2和算法3在大多數(shù)據(jù)集上擁有更高的分類(lèi)穩(wěn)定性，在表7中，以數(shù)據(jù)集“Heart（statlog）（ID：9）”為例，算法2和算法3在相對(duì)鄰域自信息下所求得的約簡(jiǎn)對(duì)應(yīng)的SVM分類(lèi)穩(wěn)定性分別為0.933 2和0.945" 算法1對(duì)應(yīng)的SVM分類(lèi)穩(wěn)定性為0.899 8.就平均穩(wěn)定性而言，算法3與其他算法相比也具有優(yōu)勢(shì)，算法1和算法2在鄰域判別指數(shù)下的所求得的約簡(jiǎn)對(duì)應(yīng)的平均SVM分類(lèi)穩(wěn)定性分別為0.975 4和0.974" 算法3的對(duì)應(yīng)的平均穩(wěn)定性為0.976 4.

相較于算法1和算法2而言，文中提出的基于局部鄰域粒度的算法3在大多數(shù)的數(shù)據(jù)集上，不論是以鄰域判別指數(shù)還是相對(duì)鄰域自信息為度量，都有著較高的分類(lèi)準(zhǔn)確率和分類(lèi)穩(wěn)定性.

4" 結(jié)論

文中從局部的視角出發(fā)，觀察不同條件屬性在局部樣本上的鄰域粒度的差別，發(fā)現(xiàn)不同條件屬性在全局生成的鄰域粒度相同或相似的時(shí)候，其在局部樣本上生成的鄰域粒度差異較大.這就意味著相較于全局鄰域粒度而言，局部鄰域粒度可以更好的進(jìn)行屬性約簡(jiǎn).實(shí)驗(yàn)表明，提出的算法3在提高分類(lèi)器的準(zhǔn)確率和分類(lèi)穩(wěn)定性上都有著不錯(cuò)的效果.

文中僅使用了兩種不確定性度量進(jìn)行求解，下一步可以嘗試其他不確定性度量來(lái)驗(yàn)證算法的有效性，例如近似質(zhì)量等.算法3是根據(jù)鄰域粒度觀察不同條件屬性的差異，下一步可以考慮在相同條件屬性下通過(guò)粒度考慮樣本之間的差別.

參考文獻(xiàn)（References）

［1］" PAWLAK Z. Roughsets［J］.International Journal of Intelligent Systems，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）：191-209.

［3］" WU W， LEUNG Y. Theory and applications of granular labeled partitions in multi-scale decision tables［J］. Information Sciences， 2011， 181（18）：3878-3897.

［4］" HU Qinghua， YU Daren， LIU Jinfu， et al. Neighborhood rough set based heterogeneous feature subset selection［J］. Information Sciences， 2008， 178（18）：3577-359.

［5］" YANG Xibei， LIANG Shaochen， YU Hualong， et al. Pseudo-label neighborhood rough set： Measures and attributereductions［J］. International Journal of Approximate Reasoning， 2019， 105：112-129.

［6］" LIU Keyu， YANG Xibei， YU Hualong， et al. Supervised information granulation strategy for attribute redction［J］. International Journal of Machine Learning and Cybernetics，2020，11：2149-2163.

［7］" XIA Shuyin， ZHANG Hao， LI Wenhua， et al. GBRS： A novel rough set algorithm for fast adaptive attribute reduction in classification［J］.IEEE Transactions on Knowledge and Data Engineering，2022，34（3）：1231-1242.

［8］" WANG Qi， QIAN Yuhua， LIANG Xinyan， et al. Local neighborhood roughset［J］.Knowledge-Based Systems， 2018， 153：53-64.

［9］" 張昭琴，徐泰華，鞠恒榮，等.基于粒度的加速求解約簡(jiǎn)策略［J］.南京理工大學(xué)學(xué)報(bào)（自然科學(xué)版），2021，45（4）：401-408.

［10］" BA Jing， WANG Pingxin， YANG Xibei， et al. Glee： A granularityfilter for feature selection［J］. Engineering Applications of" Artificial Intelligence， 2023， 122：106080.

［11］" WANG Changzhong， HUANG Yang， SHAO Mingwen， et al. Feature selection based on neighborhood self-information［J］. IEEE Transactions on Cybernetics， 2020， 50（9）：4031-4042.

［12］" YAO Yiyu， ZHAO Yan， WANG Jue. On reduct construction algorithms［C］∥Transactions on Computational Science II. Berlin： Springer， 2008： 100-117.

［13］" YANG Xibei， YAO Yiyu. Ensemble selector for attribute reduction［J］.Applied Soft" Computing，2018，70：1-11.

（責(zé)任編輯：曹莉）