基于知識(shí)粗糙熵的快速屬性約簡(jiǎn)算法

王小雪 殷鋒 楊雅雯

收稿日期：2023-06-18；修回日期：2023-08-07? 基金項(xiàng)目：國(guó)家自然科學(xué)基金資助項(xiàng)目（61105061）；國(guó)家社會(huì)科學(xué)基金資助項(xiàng)目-重大招標(biāo)項(xiàng)目（19ZDA284）；四川省科技資助項(xiàng)目-重點(diǎn)研發(fā)項(xiàng)目（2023YFN0026）；四川省教育信息技術(shù)研究資助項(xiàng)目（DSJ2022036）；成都市哲學(xué)社會(huì)科學(xué)規(guī)劃資助項(xiàng)目（2022BS027）；西南民族大學(xué)中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)資金資助項(xiàng)目（2022SZL20）

作者簡(jiǎn)介：王小雪（1992—），女（仫佬族），貴州凱里人，碩士研究生，主要研究方向?yàn)榇植诩蛿?shù)據(jù)挖掘；殷鋒（1972—），男（侗族）（通信作者），貴州榕江人，教授，碩導(dǎo)，博士，主要研究方向?yàn)槿斯ぶ悄芎蛿?shù)據(jù)挖掘等（yf_eagle@swun.edu.cn）；楊雅雯（2000—），女（回族），山東德州人，碩士研究生，主要研究方向?yàn)樯鐣?huì)網(wǎng)絡(luò)分析和數(shù)據(jù)挖掘．

摘? 要：針對(duì)基于正域的屬性約簡(jiǎn)算法在約簡(jiǎn)過(guò)程中存在重復(fù)計(jì)算屬性相對(duì)重要度從而導(dǎo)致算法效率低的問(wèn)題，從屬性度量和搜索策略的角度提出基于知識(shí)粗糙熵的快速屬性約簡(jiǎn)算法。首先，在決策信息系統(tǒng)中通過(guò)引入知識(shí)距離提出知識(shí)粗糙熵以度量知識(shí)的粗糙程度；其次，利用知識(shí)粗糙熵作為屬性顯著度的評(píng)價(jià)標(biāo)準(zhǔn)來(lái)評(píng)估單個(gè)屬性的重要程度；最后，利用屬性重要度對(duì)所有條件屬性進(jìn)行排序，且通過(guò)屬性依賴度刪除冗余屬性，從而實(shí)現(xiàn)快速約簡(jiǎn)。在六個(gè)公開(kāi)數(shù)據(jù)集上將所提算法與其他三種算法在運(yùn)行效率和分類精度上進(jìn)行對(duì)比實(shí)驗(yàn)。結(jié)果表明，該算法的運(yùn)行效率比其他三種算法分別提高了83.24%，28.77%和59.92%；在三種分類器中，分類精度分別平均提高了0.83%、0.63%和1.37%。因此，所提算法在保證分類性能的同時(shí)，能以更快的速度獲得約簡(jiǎn)。

關(guān)鍵詞：粗糙集；屬性約簡(jiǎn)；知識(shí)距離；屬性重要度

中圖分類號(hào)：TP18??? 文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001-3695（2024）02-025-0488-05

doi：10.19734/j.issn.1001-3695.2023.06.0258

Fast attribute reduction algorithm based on knowledge rough entropy

Wang Xiaoxue，Yin Feng，Yang Yawen

（School of Computer Science & Engineering，Southwest Minzu University，Chengdu 610041，China）

Abstract：In order to address the problem of low algorithm efficiency caused by repeated calculation of the relative importance of attributes in the attribute reduction algorithm based on positive region，this paper proposed a fast attribute reduction algorithm based on knowledge rough entropy from the perspectives of attribute measurement and search strategy.Firstly，it introduced knowledge rough entropy into decision information systems by incorporating knowledge distance to measure the degree of knowledge roughness.Next，it employed knowledge rough entropy as the criterion for evaluating the significance of attributes，assessing the importance of individual attributes.Finally，it ranked all attributes based on attribute importance，and eliminated redundant attributes through dependency，so as to achieve rapid attribute reduction.The proposed algorithm was compared with other three algorithms in terms of running efficiency and classification accuracy on six publicly available datasets.The results demonstrate that the proposed algorithm improves running efficiency by 83.24%，28.77%，and 59.92% respectively compared to other three algorithms.Among the three classifiers，the classification accuracy increases on average by 0.83%，0.63%，and 1.37% respectively.Therefore，the proposed algorithm is able to achieve attribute reduction more quickly while ensuring classification performance.

Key words：rough set；attribute reduction；knowledge distance；attribute importance

0? 引言

屬性約簡(jiǎn)在粗糙集理論中扮演著重要的角色［1］，其主要目標(biāo)是在保持相同分類能力的前提下刪除不重要的屬性，以優(yōu)化數(shù)據(jù)表、提高計(jì)算效率和分類性能。該技術(shù)已廣泛應(yīng)用于多個(gè)領(lǐng)域，如文本分類［2］、基因數(shù)據(jù)表達(dá)［3］、入侵檢測(cè)［4］等。

在粗糙集理論中，屬性約簡(jiǎn)通常使用貪心啟發(fā)式搜索［5］來(lái)獲取約簡(jiǎn)。然而隨著數(shù)據(jù)量的增加，該方法的計(jì)算時(shí)間也會(huì)顯著增加。為解決這一問(wèn)題，研究者們提出不同改進(jìn)算法以提高計(jì)算效率。Qian等人［6，7］首先提出基于正向近似的快速約簡(jiǎn)算法，在迭代過(guò)程中通過(guò)減少正域中的樣本來(lái)加快算法的執(zhí)行速度。該方法被進(jìn)一步擴(kuò)展到不完備有序模糊粗糙集［8］、模糊粗糙集［9］、不完備決策粗糙集［10］和多尺度信息系統(tǒng)［11］的快速屬性約簡(jiǎn)算法的研究工作中。在基于正向近似加速搜索策略的基礎(chǔ)上，Shu等人［12］利用區(qū)分和不可區(qū)分關(guān)系度量屬性顯著度，從屬性度量的角度提出一種新的快速屬性約簡(jiǎn)方法。盡管前述研究成果在縮減屬性評(píng)估時(shí)間和提高計(jì)算效率方面取得了進(jìn)展，但相對(duì)重要度的計(jì)算次數(shù)并沒(méi)有減少。在屬性約簡(jiǎn)過(guò)程中，屬性重要度的計(jì)算次數(shù)是決定運(yùn)行效率的一個(gè)關(guān)鍵因素。因此，Liang等人［13］進(jìn)一步通過(guò)減少迭代過(guò)程中的樣本和冗余屬性實(shí)現(xiàn)快速約簡(jiǎn)。該搜索策略被擴(kuò)展到更復(fù)雜的模型，如序信息系統(tǒng)［14］和集值信息系統(tǒng)［15］。前述快速屬性約簡(jiǎn)算法主要采用基于樣本的搜索策略，在迭代過(guò)程中通過(guò)減少樣本的比較次數(shù)來(lái)提升算法效率。由于他們使用前向選擇策略來(lái)獲取最優(yōu)特征子集，在不斷選擇相對(duì)重要屬性的約簡(jiǎn)過(guò)程中都需要對(duì)屬性進(jìn)行重復(fù)排序，當(dāng)數(shù)據(jù)規(guī)模較大時(shí)還是具有較高時(shí)間復(fù)雜度。所以，本文在前述基于正域的屬性約簡(jiǎn)算法的基礎(chǔ)上進(jìn)行改進(jìn)，旨在提升屬性約簡(jiǎn)的效率。

建立合理有效的屬性評(píng)價(jià)函數(shù)是屬性約簡(jiǎn)的核心步驟，其在很大程度上會(huì)影響約簡(jiǎn)的計(jì)算效率、所選屬性子集的分類泛化性能以及算法的搜索策略。為此，學(xué)者們提出許多屬性顯著度評(píng)價(jià)函數(shù)，如熵［16～18］、知識(shí)粒度［19，20］、距離［21，22］等。而將知識(shí)距離［23，24］用于屬性約簡(jiǎn)的研究不多，考慮到知識(shí)距離可用于刻畫(huà)兩個(gè)知識(shí)空間的差異或相似度，因此利用知識(shí)距離來(lái)評(píng)價(jià)屬性的顯著度是一個(gè)值得研究的課題。

綜上，本文從屬性度量和搜索策略的角度，提出基于知識(shí)粗糙熵的快速屬性約簡(jiǎn)算法（fast attribute reduction algorithm based on knowledge rough entropy，F(xiàn)ARKRE）。文獻(xiàn)［23，24］首次提出基于鄰域信息粒的知識(shí)距離，但不適用于經(jīng)典粗糙集模型，不具有擴(kuò)展性。因此，在前期相關(guān)工作［25，26］基礎(chǔ)上，本文提出知識(shí)粗糙熵用于評(píng)價(jià)條件屬性的重要程度。由于該方法只需對(duì)條件屬性計(jì)算一次屬性重要度，且在每次迭代過(guò)程中只需要計(jì)算一次正域，所以很大程度上可以減少屬性重要度的計(jì)算次數(shù)，從而提升算法效率。實(shí)驗(yàn)結(jié)果表明，F(xiàn)ARKRE算法是有效的，尤其是對(duì)于大規(guī)模數(shù)據(jù)和高維數(shù)據(jù)，這為復(fù)雜數(shù)據(jù)的快速屬性約簡(jiǎn)算法提供了新途徑。

1? 基于正域的屬性重要度

定義1［6］? 設(shè)S=（U，C∪D）為一個(gè)決策信息系統(tǒng)，其中U={x1，x2，…，xn}為對(duì)象的有限非空論域，C={c1，c2，…，cm}為條件屬性的有限非空集合，D=j5i0abt0b為決策屬性。c∈C存在一個(gè)映射c：U→Vc，Vc表示屬性c的值域，則

IND（C）={（x，y）∈U2|c（x）=c（y），c∈C}（1）

［x］C={y∈U|（x，y）∈IND（C）}（2）

U/C={［x］C|x∈U}（3）

其中：IND（C）為等價(jià)關(guān)系；［x］C為等價(jià)類；U/C為論域上的一個(gè)劃分。

定義2［6］? 設(shè)S=（U，C∪D）為一個(gè)決策信息系統(tǒng)，若BC，XU，則上近似和下近似分別定義為

B（X）={x∈U|［x］B∩X≠}（4）

B（X）={x∈U|［x］BX}（5）

其中：正域POSB（X）=B（X）表示根據(jù)屬性集B判斷肯定屬于X元素的集合。

定義3［6］? 設(shè)S=（U，C∪D）為一個(gè)決策信息系統(tǒng)，若BC，則依賴度定義為

rB（D）=|POSB（D）||U|（6）

定義4［6］? 設(shè)S=（U，C∪D）為一個(gè)決策信息系統(tǒng)，若BC，a∈B，則屬性a關(guān)于決策D的內(nèi)部屬性重要度定義為

Siginner1（a，B，D）=rB（D）-rB-{a}（D）（7）

內(nèi)部屬性重要度主要用于核屬性的計(jì)算。若Siginner1（a，B，D）＞0，則說(shuō)明屬性a是必要的，且為核屬性。若Siginner1（a，B，D）=0，則說(shuō)明屬性a不是必要的。

定義5［6］? 設(shè)S=（U，C∪D）為一個(gè)決策信息系統(tǒng)，若BC，a∈C-B，則屬性a關(guān)于決策D的外部屬性重要度定義為

Sigouter1（a，B，D）=rB∪{a}（D）-rB（D）（8）

外部屬性重要度是用于選擇候選屬性的一個(gè)指標(biāo)，它在迭代過(guò)程中起著重要的作用。在每次搜索約簡(jiǎn)過(guò)程中，選擇具有最大外部重要度的屬性，并將其添加到約簡(jiǎn)中，直至滿足算法的停止條件。

2? 基于知識(shí)粗糙熵的屬性重要度

由于文獻(xiàn)［23，24］所提出的知識(shí)距離不適用于傳統(tǒng)粗糙集模型，所以本文在前期基礎(chǔ)上進(jìn)行改進(jìn)，提出知識(shí)粗糙熵用于度量傳統(tǒng)粗糙集模型中屬性的重要程度。為證明知識(shí)粗糙熵作為度量屬性重要度的合理性，分別證明其具有非負(fù)性、對(duì)稱性和單調(diào)性。

屬性約簡(jiǎn)的目的是保留劃分能力、逼近能力強(qiáng)的屬性，去除不重要的屬性，知識(shí)粗糙熵可以度量知識(shí)的粗糙程度和屬性的劃分能力。若屬性的劃分能力越強(qiáng)，則知識(shí)就越精細(xì)。因此，在搜索約簡(jiǎn)的過(guò)程中，需要選擇那些使得知識(shí)更精細(xì)的屬性。

定義6［24］? 設(shè)S=（U，C∪D）為一個(gè)決策信息系統(tǒng)，若A，BC，U/A={SA（xi）|xi∈U}，U/B={SB（xi）|xi∈U}，則U/A和U/B之間的知識(shí)距離定義為

D（U/A，U/B）=1|U|∑|U|i=1|SA（xi）⊕SB（xi）||U|（9）

其中：|SA（xi）⊕SB（xi）|=|SA（xi）∪SB（xi）|-|SA（xi）∩SB（xi）|。D（U/A，U/B）主要用于表示兩個(gè)劃分之間的差異性。若D（U/A，U/B）的值越大，說(shuō)明U/A和U/B之間的差異就越大；反之，就越小。

定義7? 設(shè)S=（U，C∪D）為一個(gè)決策信息系統(tǒng)，若U/A={A1，A2，…，Am}，σ={x1，x2，…，x|U|}，其中AC，σ=U為論域上最粗的劃分，則U/A的知識(shí)粗糙熵定義為

KRE（U/A，σ）=

∑mi=1|Ai∪U|-|Ai∩U||Ai∪U|

|Ai∩U|（10）

若KRE（U/A，σ）的值越小，說(shuō)明U/A越接近最粗的劃分，即U/A就越粗糙，意味著屬性集A對(duì)論域的劃分能力越弱。若KRE（U/A，σ）的值越大，說(shuō)明U/A越精細(xì)，也就意味著屬性集A對(duì)論域的劃分能力越強(qiáng)。

定理1? 設(shè)S=（U，C∪D）為一個(gè)決策信息系統(tǒng)，若AC，U/A={A1，A2，…，Am}，則KRE（U/A，σ）≥0。

證明? 由于|Ai∪U|≥|Ai∩U|，根據(jù)式（10），KRE（U/A，σ）≥0成立。

定理2? 設(shè)S=（U，C∪D）為一個(gè)決策信息系統(tǒng)，若AC，U/A={A1，A2，…，Am}，則KRE（U/A，σ）=KRE（σ，U/A）。

證明? 由于|Ai∪U|=|U∪Ai|，|Ai∩U|=|U∩Ai|，根據(jù)式（10），KRE（U/A，σ）=KRE（σ，U/A）成立。

定理3? 設(shè)S=（U，C∪D）為一個(gè)決策信息系統(tǒng)，若BAC，U/A={A1，A2，…，Am}，U/B={B1，B2，…，Bn}，則KRE（U/A，σ）≥KRE（U/B，σ）。

證明? 由于BA，有U/AU/B。根據(jù)已知條件U/B至少存在一個(gè)B1可以細(xì)分為U/A中的A1和A2。為簡(jiǎn)單化，本文假設(shè)只有B1可細(xì)分為A1和A2，從而有B1=A1∪A2，根據(jù)式（10）有

KRE（U/B，σ）-KRE（U/A，σ）=

1|U|（|U|-|B1||U||B1|-|U|-|A1||U||A1|-|U|-|A2||U||A2|）=

1|U|（|U|-|B1||U||B1|-|U|-（|A1|+|A2|）|U|（|A1|+|A2|）-

2|A1||A2||U|）=1|U|（|U|-|B1||U||B1|-|U|-|B1||U||B1|-

2|A1||A2||U|）=1|U|（-2|A1||A2||U|）≤0

根據(jù)計(jì)算可知，KRE（U/A，σ）≥KRE（U/B，σ）成立。

由定理1～3可知，知識(shí)粗糙熵的定義滿足非負(fù)性、對(duì)稱性和單調(diào)性。其性質(zhì)證明了知識(shí)粗糙熵作為屬性重要度評(píng)價(jià)標(biāo)準(zhǔn)的合理性。

定義8? 設(shè)S=（U，C∪D）為一個(gè)決策信息系統(tǒng)，若AC，U/A={A1，A2，…，Am}，U/D={D1，D2，…，Dn}，則屬性集A近似決策屬性D的知識(shí)粗糙熵定義為

KRE（U/A（D），σ）=1|U|∑ri=1|U|-|Ai||U||Ai|（11）

其中：U/A（D）=U/A∩U/D={A1，A2，…，Ar}。

定義9? 設(shè)S=（U，C∪D）為一個(gè)決策信息系統(tǒng)，若aC，U/a={A1，A2，…，Am}，U/D={D1，D2，…，Dn}，則屬性a的屬性重要度定義為

Sig2（a，D）=KRE（U/a（D），σ）-KRE（U/a，σ）（12）

其中：Sig2（a，D）表示屬性a的重要度，同時(shí)也表征條件屬性的劃分能力和逼近決策的能力。若Sig2（a，D）的值越大，則說(shuō)明屬性a越不重要，意味著屬性a的劃分能力和逼近決策的能力越弱；若Sig2（a，D）的值越小，則說(shuō)明屬性a越重要，意味著屬性a的劃分能力和逼近決策的能力越強(qiáng)。

3? 基于知識(shí)粗糙熵的快速屬性約簡(jiǎn)算法

根據(jù)基于知識(shí)粗糙熵的屬性重要度定義，本文提出一種基于知識(shí)粗糙熵結(jié)合依賴度的多度量約束的快速屬性約簡(jiǎn)算法。首先，根據(jù)基于知識(shí)粗糙熵的屬性重要度計(jì)算每個(gè)條件屬性的重要度；其次，根據(jù)重要度大小按照降序?qū)蝹€(gè)條件屬性進(jìn)行排序；最后，根據(jù)保持依賴度不變的思想依次刪除屬性重要度為0的條件屬性。

算法1? 基于知識(shí)粗糙熵的快速屬性約簡(jiǎn)算法（FARKRE）

輸入：決策信息系統(tǒng)S=（U，C∪D）。

輸出：一個(gè)約簡(jiǎn)R。

a） 初始化R←。

b）for each a∈C

根據(jù)式（12），計(jì)算a∈C的屬性重要度Sig2（a，D）。

end for

c）根據(jù)Sig2（a，D）值的大小對(duì)條件屬性按照降序排序，得到Sort（C）。

d）R←Sort（C）。

e）根據(jù)式（6），計(jì)算依賴度rR（D）。

f）for each a in Sort（C） do

Siginner1（a，R，D）=rR（D）-rR-{a}（D）；

if Siginner1（a，R，D）=0 then

R←R-{a}；

end if

end for

g）返回R。

在FARKRE算法中，步驟a）初始化的時(shí)間復(fù)雜度為O（1），步驟b）計(jì)算Sig2（a，D）的時(shí)間復(fù)雜度為O（|U|×|C|），步驟c）和d）的總時(shí)間復(fù)雜度為O（|U|×log |C|），步驟e）計(jì)算屬性依賴度的時(shí)間復(fù)雜度為O（|U|2），步驟f）利用依賴度作為終止條件來(lái)搜索約簡(jiǎn)的時(shí)間復(fù)雜度為O（|U|2×|C|）。經(jīng)過(guò)分析可得到FARKRE算法的時(shí)間復(fù)雜度為O（|U|2×|C|）。

本文從理論上分析了FARKRE算法的時(shí)間復(fù)雜度，并與經(jīng)典的基于正域的屬性約簡(jiǎn)算法（forward greedy attribute reduction algorithm，F(xiàn)GAR）［5］、基于正向近似集的加速約簡(jiǎn)算法（accelerating reduction approach for IDT using positive approximation set，ARIPA）［10］、基于條件信息熵的屬性約簡(jiǎn)算法（algorithm of attribute reduction based on conditional entropy in interval-valued ordered decision table，ARCE）［18］的時(shí)間復(fù)雜進(jìn)行比較，如表1所示。

由表1可知，四種算法的時(shí)間復(fù)雜度一樣。相比之下FARKRE算法的優(yōu)勢(shì)在于以下三點(diǎn)：

a）FARKRE算法采用先對(duì)條件屬性重要度進(jìn)行預(yù)評(píng)估，再依次刪除冗余屬性的搜索策略。其他三種算法都是以核屬性為初始集合集來(lái)搜索約簡(jiǎn)，當(dāng)數(shù)據(jù)規(guī)模較大時(shí)，核屬性的計(jì)算很耗時(shí)。

b）由于FARKRE算法明確了搜索方向，能有效減少迭代過(guò)程中屬性重要度的計(jì)算次數(shù)，所以具有更高的計(jì)算效率。

c）約簡(jiǎn)結(jié)果不僅保持了依賴度不變，還選擇了劃分能力、逼近能力較強(qiáng)的屬性。

例1? 表2為一個(gè)關(guān)于某些病人的決策信息系統(tǒng)S=（U，C∪D） ，其中U={x1，x2，…，x8}為論域，共有8個(gè)病人。C={c1，c2，c3}為3個(gè)條件屬性的屬性集，其中c1表示頭痛，c2表示肌肉痛，c3表示體溫；D=j5i0abt0b為單個(gè)決策屬性，表示流感。屬性值“Y”“N”“Nor”“H”“VH”分別表示“是”“否”“正?！薄案摺薄昂芨摺?。

根據(jù)算法1，約簡(jiǎn)的過(guò)程如下：

首先，根據(jù)式（12）分別計(jì)算c1、c2、c3的屬性重要度，得到：

Sig2（c1，D）=0.25，Sig2（c2，D）=0.312 5，Sig2（c3，D）=0.125

其次，根據(jù)屬性重要度按照從大到小進(jìn)行排序，得到R={c2，c1，c3}。

最后，再根據(jù)保持依賴度不變的思想，在迭代過(guò)程中刪除重要度為0的非必要屬性，保留重要度不為0的必要屬性。

第一次迭代，從R中刪除屬性c2，計(jì)算Siginner1（c2，R，D） 得到r{c2，c1，c3}（D）-r{c1，c3}（D）=0，因此刪除屬性c2。

第二次迭代，從R中刪除屬性c1，計(jì)算Siginner1（c1，R，D） 得到r{c1，c3}（（D）-r{c3}（D）＞0，因此保留屬性c1。

第三次迭代，從R中刪除屬性c3，計(jì)算Siginner1（c3，R，D） 得到r{c1，c3}（D）-r{c1}（D）＞0，因此保留屬性c3。

根據(jù)算法1得到一個(gè)約簡(jiǎn)R={c1，c3}，與其他三種算法所得結(jié)果一樣。根據(jù)約簡(jiǎn)結(jié)果可知，在表2的決策信息系統(tǒng)中，“體溫”最重要，其次是“頭痛”，“肌肉痛”是不重要的。也就是說(shuō)，在根據(jù)病人特征（條件屬性）來(lái)判斷一個(gè)病人是否患流感時(shí)，可以不用考慮“肌肉痛”。由此可見(jiàn)，所得約簡(jiǎn)結(jié)果比較符合實(shí)際情況，驗(yàn)證了本文所提屬性重要度度量方法的合理性和有效性，以及FARKRE算法在實(shí)際應(yīng)用中的可行性。

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

4.1? 實(shí)驗(yàn)設(shè)置

本文從UCI數(shù)據(jù)集網(wǎng)站下載了六組數(shù)據(jù)集，并將其用于算法性能的測(cè)試，數(shù)據(jù)詳細(xì)信息如表3 所示。實(shí)驗(yàn)所使用環(huán)境為64 bit Windows 11系統(tǒng)，處理器為AMD Ryzen 7 6800H，內(nèi)存為16 GB，軟件為Python 3.9。

FARKRE與FGAR、ARIPA和ARCE算法進(jìn)行對(duì)比，比較分析的評(píng)價(jià)指標(biāo)分別是運(yùn)行時(shí)間、約簡(jiǎn)長(zhǎng)度和分類精度。對(duì)比實(shí)驗(yàn)分為三組。

第一組實(shí)驗(yàn)：對(duì)比不同算法的運(yùn)行時(shí)間與約簡(jiǎn)長(zhǎng)度。

第二組實(shí)驗(yàn)：對(duì)比不同算法對(duì)于樣本規(guī)模和消耗時(shí)間之間的關(guān)系。

第三組實(shí)驗(yàn)：采用十折交叉驗(yàn)證法，對(duì)比不同算法獲得的約簡(jiǎn)在支持向量機(jī)（support vector machine，SVM）、K-最鄰近（K-nearest-neighbor，KNN）、隨機(jī)森林（random forest，RF）三種分類器中的平均分類精度。

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

對(duì)于本文實(shí)驗(yàn)結(jié)果，時(shí)間保留2位小數(shù)，平均分類精度保留3位小數(shù)，并以加粗的形式表示該結(jié)果優(yōu)于其他算法的結(jié)果。

4.2.1? 運(yùn)行時(shí)間和約簡(jiǎn)長(zhǎng)度對(duì)比

四種算法在六組數(shù)據(jù)集上的運(yùn)行時(shí)間和約簡(jiǎn)長(zhǎng)度的對(duì)比如表4和5所示。根據(jù)表4可知，除了在數(shù)據(jù)集mushroom 上，ARCE 算法的運(yùn)行時(shí)間最短，F(xiàn)ARKRE算法在其余五組數(shù)據(jù)集上的運(yùn)行時(shí)間均低于其他三種算法。在數(shù)據(jù)維度最大的數(shù)據(jù)集TUANDROMD上，F(xiàn)GAR、ARIPA和ARCE算法的運(yùn)行時(shí)間為FARKRE算法的7.46倍、1.64倍和2.28倍。在數(shù)據(jù)規(guī)模最大的數(shù)據(jù)集connect-4上，F(xiàn)GAR、ARIPA和ARCE算法的運(yùn)行時(shí)間為FARKRE算法的6.11倍、1.36倍和2.59倍。在mushroom、letter、shuttle和connect-4這四組數(shù)據(jù)集上，它們的數(shù)據(jù)規(guī)模呈遞增關(guān)系。在這四組數(shù)據(jù)集中數(shù)據(jù)規(guī)模最小的mushroom上，F(xiàn)ARKRE算法運(yùn)行效率不如ARCE 算法，但當(dāng)數(shù)據(jù)規(guī)模增大時(shí)，F(xiàn)ARKRE算法運(yùn)行效率較ARCE 算法具有明顯優(yōu)勢(shì)。

經(jīng)計(jì)算和分析可知，在這六組數(shù)據(jù)集上，F(xiàn)ARKRE算法運(yùn)行效率整體優(yōu)于FGAR、ARIPA和ARCE算法，且FARKRE算法在大規(guī)模數(shù)據(jù)和高維數(shù)據(jù)上表現(xiàn)更佳。

根據(jù)表5可知，在數(shù)據(jù)集SCADI、mushroom上，ARCE算法獲得更短的約簡(jiǎn)。在其他數(shù)據(jù)集中，四種算法得到的約簡(jiǎn)長(zhǎng)度一樣。這表明本文算法是可行的，能有效剔除不必要的屬性。

4.2.2? 樣本規(guī)模和消耗時(shí)間之間關(guān)系對(duì)比

圖1展示了樣本數(shù)量在不斷增加的情況下， FGAR、ARIPA、ARCE和FARKRE四種算法運(yùn)行時(shí)間的變化趨勢(shì)。在每個(gè)子圖中，橫坐標(biāo)代表樣本的規(guī)模，縱坐標(biāo)代表運(yùn)行時(shí)間。本文將每個(gè)數(shù)據(jù)集的樣本平均劃分為10等份，并依次添加1份作為測(cè)試算法時(shí)間消耗的數(shù)據(jù)集。

根據(jù)圖1可知，在樣本規(guī)模不斷增大的情況下，算法的執(zhí)行時(shí)間呈現(xiàn)上升趨勢(shì)。在圖（a）（b）中可看到，隨著樣本規(guī)模的逐漸增加，F(xiàn)ARKRE算法運(yùn)行時(shí)間始終低于其他三種算法。在圖（d）（e）中可看到，當(dāng)樣本規(guī)模較小時(shí)，ARCE算法的運(yùn)行時(shí)間最短。但當(dāng)樣本規(guī)模逐漸增大時(shí)，F(xiàn)ARKRE算法的運(yùn)行時(shí)間低于ARCE算法。由此更進(jìn)一步驗(yàn)證FARKRE算法在大規(guī)模、高維數(shù)據(jù)上具有一定的優(yōu)勢(shì)。

4.2.3? 分類精度對(duì)比

對(duì)于FGAR、ARIPA、ARCE和FARKRE算法獲得的約簡(jiǎn)結(jié)果，通過(guò)SVM、KNN和RF三種分類模型對(duì)分類精度進(jìn)行對(duì)比，對(duì)比結(jié)果分別如表6～8所示。

根據(jù)表6可知，只有在數(shù)據(jù)集TUANDROMD和letter上，F(xiàn)ARKRE算法在SVM中的分類精度低于FGAR、ARIPA和ARCE算法，在其余數(shù)據(jù)集上，F(xiàn)ARKRE算法的分類精度不低于其他三種算法。在這六組數(shù)據(jù)集上，F(xiàn)ARKRE算法的分類精度比其他三種算法分別提高0.71%、0.71%和1.06%。

由表7可知，在數(shù)據(jù)集TUANDROMD、mushroom和letter上，F(xiàn)ARKRE算法在KNN中的分類精度低于FGAR、ARIPA和ARCE算法，在其余數(shù)據(jù)集上FARKRE算法的分類精度不低于其他三種算法。在這六組數(shù)據(jù)集上，F(xiàn)ARKRE算法的分類精度比他三種算法分別提高0.46%、0.46%和0.96%。

由表8可知，在數(shù)據(jù)集Tuandromd上，F(xiàn)ARKRE算法在RF中的分類精度低于FGAR和ARIPA算法。在數(shù)據(jù)集letter上，F(xiàn)ARKRE算法的分類精度低于其他三種算法。在其余數(shù)據(jù)集上FARKRE算法的分類精度不低于其他三種算法。在這六組數(shù)據(jù)集上，F(xiàn)ARKRE算法的分類精度比其他三種算法分別提高1.42%，1.42%和1.28%

根據(jù)上述三組實(shí)驗(yàn)結(jié)果及分析可知，F(xiàn)ARKRE算法不僅在計(jì)算效率上優(yōu)于FGAR、ARIPA和ARCE算法，而且在三種分類器中分類性能的差異也表明其有效性和可行性。

5? 結(jié)束語(yǔ)

為提升屬性約簡(jiǎn)算法的效率，本文提出知識(shí)粗糙熵，并基于此提出一種多度量約束的快速屬性約簡(jiǎn)算法——FARKRE算法。該算法在循環(huán)搜索約簡(jiǎn)過(guò)程中減少了對(duì)屬性重要度的計(jì)算次數(shù)，具有更高的計(jì)算效率。在數(shù)值實(shí)驗(yàn)中，本文使用公開(kāi)數(shù)據(jù)集，通過(guò)比較FARKRE、FGAR、ARIPA和ARCE四種算法的性能來(lái)驗(yàn)證本文算法的效率和有效性。通過(guò)三組實(shí)驗(yàn)的對(duì)比結(jié)果表明FARKRE算法能有效剔除冗余屬性，且在計(jì)算效率和分類精度方面優(yōu)于其他三種算法。

FARKRE算法雖然在分類性能上優(yōu)于改進(jìn)前的算法，但在某些數(shù)據(jù)集中分類精度較低。因此，在下一步的研究工作中主要分為兩方面。首先，對(duì)FARKRE算法進(jìn)行優(yōu)化，以獲得更高的分類精度；其次，將知識(shí)距離引入其他類型的粗糙集模型中，如區(qū)間值、集值等，以更高效率地獲得高分類性能的約簡(jiǎn)。

參考文獻(xiàn)：

［1］周濤，陸惠玲，任海玲，等.基于粗糙集的屬性約簡(jiǎn)算法綜述［J］.電子學(xué)報(bào)，2021，49（7）：1439-1449.（Zhou Tao，Lu Huiling，Ren Hailing，et al.A review of attribute reduction algorithms based on rough sets［J］.Acta Electronica Sinica，2021，49（7）：1439-1449.）

［2］Fan Xiaodong，Chen Xiangyue，Wang Changzhong，et al.Margin attri-bute reductions for multi-label classification［J］.Applied Intelligence，2022，52（6）：6079-6092.

［3］Liu Keyu，Li Tianrui，Yang Xibei，et al.Hierarchical neighborhood entropy based multi-granularity attribute reduction with application to gene prioritization［J］.International Journal of Approximate Reasoning，2022，148：57-67.

［4］Luo Jan，Wang Huajun，Li Yanmei，et al.Intrusion detection system based on genetic attribute reduction algorithm based on rough set and neural network［J］.Wireless Communications and Mobile Computing，2022，2022：1-10.

［5］Hu Xiaohua，Cercone N.Learning in relational databases：a rough set approach［J］.Computational Intelligence，1995，11（2）：323-338.

［6］Qian Yuhua，Liang Jiye，Pedrycz W，et al.Positive approximation：an accelerator for attribute reduction in rough set theory［J］.Artificial Intelligence，2010，174（9-10）：597-618.

［7］Qian Yuhua，Liang Jiye，Pedrycz W，et al.An efficient accelerator for attribute reduction from incomplete data in rough set framework［J］.Pattern Recognition，2011，44（8）：1658-1670.

［8］Qian Wenbin，Shu Wenhao.Attribute reduction in incomplete ordered information systems with fuzzy decision［J］.Applied Soft Computing，2018，73：242-253.

［9］Ni Peng，Zhao Suyun，Wang Xizhao，et al.PARA：a positive-region based attribute reduction accelerator［J］.Information Sciences，2019，503：533-550.

［10］Yan Tao，Han Chongzhao，Zhang Kaitong，et al.An accelerating reduction approach for incomplete decision table using positive approximation set［J］.Sensors，2022，22（6）：2211.

［11］陳曼如，張楠，童向榮，等.基于多尺度屬性粒策略的快速正域約簡(jiǎn)算法［J］.計(jì)算機(jī)應(yīng)用，2019，39（12）：3426-3433.（Chen Manru，Zhang Nan，Tong Xiangrong，et al.Fast positive domain reduction algorithm based on multi-scale attribute granular strategy［J］.Journal of Computer Applications，2019，39（12）：3426-3433.）

［12］Shu Wenhao，Qian Wenbin.A fast approach to attribute reduction from perspective of attribute measures in incomplete decision systems［J］.Knowledge-Based Systems，2014，72：60-71.

［13］Liang Jiye，Mi Junrong，Wei Wei，et al.An accelerator for attribute reduction based on perspective of objects and attributes［J］.Know-ledge-Based Systems，2013，44：90-100.

［14］Du Wensheng，Hu Baoqing.A fast heuristic attribute reduction approach to ordered decision systems［J］.European Journal of Operational Research，2018，264（2）：440-452.

［15］陳曼如，張楠，童向榮，等.集值信息系統(tǒng)的快速正域約簡(jiǎn)［J］.智能系統(tǒng)學(xué)報(bào)，2019，14（3）：471-478.（Chen Manru，Zhang Nan，Tong Xiangrong，et al.Fast positive domain reduction of set-valued information systems［J］.Journal of Intelligent Systems，2019，14（3）：471-478.）

［16］Gao Can，Lai Zhihui，Zhou Jie，et al.Granular maximum decision entropy-based monotonic uncertainty measure for attribute reduction［J］.International Journal of Approximate Reasoning，2019，104：9-24.

［17］Zhang Qinli，Chen Yiying，Zhang Gangqiang，et al.New uncertainty measurement for categorical data based on fuzzy information structures：an application in attribute reduction［J］.Information Sciences，2021，580：541-577.

［18］張曉燕，匡洪毅.區(qū)間值序決策表的條件熵屬性約簡(jiǎn)［J］.山西大學(xué)學(xué)報(bào)：自然科學(xué)版，2023，46（1）：101-107.（Zhang Xiaoyan，Kuang Hongyi.Conditional entropy attribute reduction of interval valued order decision table［J］.Journal of Shanxi University ：Na-tural Science Edition，2023，46（1）：101-107.）

［19］Chen Yan，Wang Pingxin，Yang Xibei，et al.Granular ball guided selector for attribute reduction［J］.Knowledge-Based Systems，2021，229：107326.

［20］Zhang Chucai，Dai Jianhua，Chen Jiaolong.Knowledge granularity based incremental attribute reduction for incomplete decision systems［J］.International Journal of Machine Learning and Cyberne-tics，2020，11（5）：1141-1157.

［21］Hu Meng，Tsang E C C，Guo Yanting，et al.Attribute reduction based on overlap degree and k-nearest-neighbor rough sets in decision information systems［J］.Information Sciences，2022，584：301-324.

［22］Wang Changzhong，Huang Yang，Shao Mingwen，et al.Fuzzy rough set-based attribute reduction using distance measures［J］.Know-ledge-Based Systems，2019，164：205-212.

［23］Qian Yuhua，Liang Jiye，Dang Chuangyin，et al.Knowledge distance in information systems［J］.Journal of Systems Science and Systems Engineering，2007，16（4）：434-449.

［24］Qian Yuhua，Liang Jiye，Dang Chuangyin.Knowledge structure，knowledge granulation and knowledge distance in a knowledge base［J］.International Journal of Approximate Reasoning，2009，50（1）：174-188.

［25］Yang Jie，Wang Guoyin，Zhang Qinghua.Knowledge distance measure in multi-granulation spaces of fuzzy equivalence relations［J］.Information Sciences，2018，448-449：18-35.

［26］Yang Jie，Wang Guoyin，Zhang Qinghua，et al.Knowledge distance measure for the multigranularity rough approximations of a fuzzy concept［J］.IEEE Trans on Fuzzy Systems，2020，28（4）：706-717.