分布優(yōu)勢數(shù)據(jù)集的矩陣增量屬性約簡算法

摘要：傳統(tǒng)屬性約簡算法不能有效解決動態(tài)數(shù)據(jù)屬性約簡問題，尋求高效動態(tài)數(shù)據(jù)屬性約簡算法是目前人工智能領域研究的熱點。本文在動態(tài)分布優(yōu)勢數(shù)據(jù)集中引入矩陣優(yōu)勢條件熵和優(yōu)勢矩陣，探討基于優(yōu)勢條件熵的矩陣增量屬性約簡方法。首先，定義了分布數(shù)據(jù)集的優(yōu)勢矩陣和優(yōu)勢條件熵；其次，通過分析分布數(shù)據(jù)集添加對象的過程，提出了優(yōu)勢矩陣的增量更新原理和融合機制；然后，給出了基于優(yōu)勢條件熵的矩陣增量約簡方法。最后，利用6組UCI（University of California Irvine）優(yōu)勢數(shù)據(jù)集進行實驗，用于驗證增量屬性約簡算法的高效性。實驗結果表明：與非增量屬性約簡算法相比，由增量屬性約簡算法計算約簡的運行時間縮短了85.6%。所以，本文所給出的矩陣增量屬性約簡算法是求解動態(tài)分布優(yōu)勢數(shù)據(jù)集屬性約簡的快速有效方法。

關鍵詞：分布優(yōu)勢數(shù)據(jù)集；增量技術；屬性約簡；優(yōu)勢條件熵；優(yōu)勢數(shù)據(jù)集矩陣

中圖分類號：TP391 文獻標志碼：A 文章編號：0253-2395（2025）01-0158-11

0 引言

波蘭科學研究者Pawlak 提出的粗糙集理論是一種新的數(shù)學工具［1］，主要用來處理不一致、不精確和不相容的數(shù)據(jù)問題。該理論在處理上述問題時，不需要任何先驗知識，且處理效率較高，所以很多學者已經(jīng)把它運用到數(shù)據(jù)挖掘和知識發(fā)現(xiàn)等領域。

屬性約簡是粗糙集理論中的一個重要研究內(nèi)容，它通過刪除決策表中的容冗信息，減少數(shù)據(jù)特征，提高數(shù)據(jù)計算效率，是數(shù)據(jù)預處理的重要工具。一些學者在經(jīng)典粗糙集模型上提出了一些屬性約簡算法［2-7］，并利用它們對數(shù)據(jù)進行預處理，取得了一定的效果。但是由于經(jīng)典粗糙集模型對沒有偏序關系的數(shù)據(jù)集通過上下近似集來逼近目標決策，不能有效處理具有偏序關系的數(shù)據(jù)集。

為了克服這個缺陷，Greco 等提出了優(yōu)勢粗糙集模型［8］來解決具有偏序關系的數(shù)據(jù)挖掘等問題。通過向上聯(lián)合或者向下聯(lián)合來逼近目標決策。為了進一步完善優(yōu)勢粗糙集模型，許多研究者對優(yōu)勢粗糙集模型進行了擴展。梁美社等為了有效處理直覺模糊偏序關系數(shù)據(jù)規(guī)則獲取問題，提出了廣義優(yōu)勢直覺模糊粗糙集模型［9］。Yang 等提出了一種新的優(yōu)勢粗糙集模型用來處理不完備區(qū)間值信息系統(tǒng)的問題［10］。上述的工作可以有效處理靜態(tài)偏序數(shù)據(jù)挖掘和知識發(fā)現(xiàn)問題，但是在處理動態(tài)偏序數(shù)據(jù)挖掘問題時，效率不是很高。

增量學習方法能夠有效利用先前的結果，減少重復計算量，極大地提高計算性能，特別適應動態(tài)數(shù)據(jù)環(huán)境。很多學者提出了大量增量方法，并利用這些方法解決動態(tài)數(shù)據(jù)近似集的更新［11-14］和屬性約簡的更新問題［15-19］。在增量屬性約簡方面：Liang 等針對多個對象增加到數(shù)據(jù)集中，探討了信息熵的更新機制，提出了群增量屬性約簡算法［20］。Jing 等針對多個對象增加到數(shù)據(jù)集中，探討了知識粒度的更新機制，設計了基于知識粒度的屬性約簡算法［21］。桑彬彬等針對單個對象增加到優(yōu)勢數(shù)據(jù)集中，分析了優(yōu)勢條件信息熵的更新原理，提出了基于信息熵屬性約簡方法［22］。Shu 等針對不完備信息系統(tǒng)中屬性變化的問題，提出了基于正區(qū)域的增量屬性約簡算法［23］。Zeng 等針對一些對象增加到混合數(shù)據(jù)中如何快速更新約簡問題，提出了增量屬性約簡算法［24］。陳寶國等針對不完備有序數(shù)據(jù)動態(tài)變化如何快速更新約簡問題，提出了混合有序數(shù)據(jù)增量約簡算法［25］。Sang等針對優(yōu)勢鄰域粗糙集數(shù)據(jù)更新問題，提出了基于優(yōu)勢條件熵的增量屬性約簡算法［26］。

矩陣運算由于表達直觀，計算簡單，操作方便，是數(shù)據(jù)預處理的有效工具。為了解決分布優(yōu)勢數(shù)據(jù)集動態(tài)增加導致的屬性約簡計算時間長，效率低下的問題，本文將優(yōu)勢矩陣與優(yōu)勢條件熵相結合，提出分布優(yōu)勢數(shù)據(jù)集的矩陣增量屬性約簡算法，該算法首先定義了分布數(shù)據(jù)集的優(yōu)勢矩陣和優(yōu)勢條件熵，并將優(yōu)勢矩陣引入優(yōu)勢條件熵中，然后分析分布數(shù)據(jù)集添加對象的過程，給出優(yōu)勢矩陣的增量更新原理和融合機制，進而設計分布優(yōu)勢數(shù)據(jù)集的矩陣增量屬性約簡算法，最后通過UCI 數(shù)據(jù)集實驗驗證了分布優(yōu)勢數(shù)據(jù)集的矩陣增量屬性約簡算法的高效性。

1 優(yōu)勢粗糙集的基本理論

在本節(jié)，我們將介紹優(yōu)勢粗糙集的相關理論和知識［27］。

1.1 優(yōu)勢粗糙集的基礎知識

3.1 仿真實驗數(shù)據(jù)集和實驗環(huán)境

在實驗過程中，本節(jié)將從機器學習網(wǎng)站上選取6 個UCI 優(yōu)勢數(shù)據(jù)集作為實驗的數(shù)據(jù)，6 個UCI優(yōu)勢數(shù)據(jù)集的詳細情況敘述如表1 所示，其中3 個數(shù)據(jù)集屬性值的類型是整型數(shù)據(jù)，1 個數(shù)據(jù)集屬性值的類型是浮點型數(shù)據(jù)，2 個數(shù)據(jù)集屬性值的類型是整型數(shù)據(jù)和字符串數(shù)據(jù)混合組成，由于個別數(shù)據(jù)集在實驗中不能直接處理，所以需要對上述數(shù)據(jù)集進行預處理。對于數(shù)據(jù)集中存在少量缺失值問題，我們在實驗中直接刪除缺失值；對于數(shù)據(jù)集中條件屬性和決策屬性存在字符串的值，我們按照字符串的優(yōu)劣賦予大小不同的數(shù)值，相同的字符串賦予相同的數(shù)值。另外，本文編寫代碼對預處理過的數(shù)據(jù)集按照決策屬性類型對相對應的數(shù)據(jù)進行比較分析，實驗結果驗證了它們是具有優(yōu)勢關系的數(shù)據(jù)集。仿真實驗硬件環(huán)境為：Intel（R）Core（TM） i5-5200U CPU（Central ProcessingUnit） @ 2.2 GHz，內(nèi)存2.0 GB。仿真實驗軟件環(huán)境為：Eclipse 3.7，操作系統(tǒng)是Win10 64 位。

3.2 屬性約簡結果比較

為了驗證算法2 計算性能的有效性，本文做了大量仿真實驗。為了實驗操作方便，本文假設分布優(yōu)勢數(shù)據(jù)集由3 個子優(yōu)勢數(shù)據(jù)集組成。實驗過程如下：本文把表1 中的每個優(yōu)勢數(shù)據(jù)集中的對象集按50%，50% 比例分成兩個優(yōu)勢數(shù)據(jù)集，把其中一個優(yōu)勢數(shù)據(jù)集分成3 個子優(yōu)勢數(shù)據(jù)集，看成分布優(yōu)勢數(shù)據(jù)集，然后把另一個優(yōu)勢數(shù)據(jù)集添加到任意1 個子優(yōu)勢數(shù)據(jù)集中，然后利用算法2 和算法1 去計算分布優(yōu)勢數(shù)據(jù)集的屬性約簡和運行時間。為了讓運行時間具有一定的可靠性和穩(wěn)定性，所以本文把5 次計算的時間取平均值作為計算約簡的運行時間。屬性約簡結果和運行時間的結果如表2 所示。

在表2 中，分布優(yōu)勢數(shù)據(jù)集的算法1 與算法2 所獲得約簡的結果基本上是相同的，但是算法1的運行時間遠遠大于算法2 的運行時間，說明了分布優(yōu)勢數(shù)據(jù)集的增量屬性約簡算法在處理動態(tài)分布優(yōu)勢數(shù)據(jù)集的約簡問題上具有較強的計算性能。

3.3 運行時間比較

為了驗證算法2 在運行時間上優(yōu)于算法1，本文做了大量仿真實驗。實驗具體過程如下：在3.2節(jié)分布優(yōu)勢數(shù)據(jù)集的基礎上，把另一優(yōu)勢數(shù)據(jù)集的對象集按20%，40%，60%，80%，100% 比例分成5 份，然后依次把每一份數(shù)據(jù)增加到任意1 個子優(yōu)勢數(shù)據(jù)集中。實驗結果如圖1 所示。

在圖1 中，隨著增加對象數(shù)量的增加，算法1 和算法2 計算約簡的時間也會增加，算法2 運行時間增長幅度較小，而算法1 運行時間增長幅度更大，說明算法2（分布優(yōu)勢數(shù)據(jù)的增量屬性約簡算法）能極大提高動態(tài)分布優(yōu)勢數(shù)據(jù)集屬性約簡的效率。

3.4 仿真實驗分類精確度比較

通過大量實驗驗證算法2 和算法1 所計算約簡的有效性，本文做了大量仿真實驗。實驗具體過程如下：利用3.2 節(jié)獲得分布優(yōu)勢數(shù)據(jù)集的屬性約簡，然后通過10 折交叉驗證法及貝葉斯分類法來計算算法1 和算法2 所獲得約簡的分類精確度。實驗結果如表3 所示。

在表3 中，算法1 和算法2 所獲得約簡的分類精確度基本上是相同的，說明分布優(yōu)勢數(shù)據(jù)集的增量屬性約簡算法可以有效處理分布優(yōu)勢數(shù)據(jù)集添加多個對象時動態(tài)更新屬性約簡的問題。

4 結束語

本文以動態(tài)分布優(yōu)勢數(shù)據(jù)集為研究對象，利用分布優(yōu)勢條件信息熵為屬性約簡的度量單位，探討了分布優(yōu)勢數(shù)據(jù)集優(yōu)勢關系矩陣的增量更新原理，提出了分布優(yōu)勢數(shù)據(jù)集的增量屬性約簡方法。最后采用UCI 數(shù)據(jù)集進行了大量實驗并對測試結果進行比較分析，分析結果驗證了分布優(yōu)勢數(shù)據(jù)集的增量屬性約簡算法能夠極大地提高動態(tài)分布優(yōu)勢數(shù)據(jù)集屬性約簡的效率。今后將繼續(xù)研究分布優(yōu)勢數(shù)據(jù)集屬性和對象變化的增量屬性約簡算法。

參考文獻：

[1] PAWLAK Z. Rough Sets[J]. Int J Comput Inf Sci， 1982，11（5）： 341-356. DOI： 10.1007/bf01001956.

[2] 徐巖柏， 景運革. 多源數(shù)據(jù)矩陣增量約簡算法[J]. 計算機工程與應用， 2022， 58（3）： 195-200. DOI： 10.3778/j.issn.1002-8331.2008-0188.

XU Y B， JING Y G. Matrix-based Incremental ReductionApproach of Multi-resource Data[J]. Comput EngAppl， 2022， 58（3）： 195-200. DOI： 10.3778/j. issn. 1002-8331.2008-0188.

[3] LIANG J Y， WANG F， DANG C Y， et al. An EfficientRough Feature Selection Algorithm with a MultigranulationView[J]. Int J Approx Reason， 2012， 53（6）：912-926. DOI： 10.1016/j.ijar.2012.02.004.

[4] WANG C Z， WANG Y， SHAO M W， et al. Fuzzy RoughAttribute Reduction for Categorical Data[J]. IEEE TransFuzzy Syst， 2020， 28（5）： 818-830. DOI： 10.1109/TFUZZ.2019.2949765.

[5] SANG B B， XU W H， CHEN H M， et al. Active AntinoiseFuzzy Dominance Rough Feature Selection UsingAdaptive K-nearest Neighbors[J]. IEEE Trans FuzzySyst， 2023， 31（11）： 3944-3958. DOI： 10.1109/TFUZZ.2023.3272316.

[6] SANG B B， YANG L， CHEN H M， et al. Fuzzy RoughFeature Selection Using a Robust Non-linear VagueQuantifier for Ordinal Classification[J]. Expert Syst Appl，2023， 230： 120480. DOI： 10.1016/j.eswa.2023.120480.

[7] 胡凱欣， 馬建敏， 劉權芳. 對象導出三支概念格的矩陣粗糙熵約簡[J]. 山西大學學報（自然科學版）， 2024.DOI： 10.13451/j.sxu.ns.2024028.

HU K X， MA J M， LIU Q F. Matrix Rough EntropybasedReductions of Object-Induced Three-Way ConceptLattices[J]. J Shanxi Univ Nat Sci Ed， 2024. DOI：10.13451/j.sxu.ns.2024028.

[8] GRECO S， MATARAZZO B， SLOWINSKI R. RoughApproximation of a Preference Relation by DominanceRelations[J]. Eur J Oper Res， 1999， 117（1）： 63-83. DOI：10.1016/s0377-2217（98）00127-1.

[9] 梁美社， 米據(jù)生， 趙天娜. 廣義優(yōu)勢多粒度直覺模糊粗糙集及規(guī)則獲取[J]. 智能系統(tǒng)學報， 2017， 12（6）： 883-888. DOI： 10.11992/tis.201706034.

LIANG M S， MI J S， ZHAO T N. Generalized Dominance-based Multi-granularity Intuitionistic FuzzyRough Set and Acquisition of Decision Rules[J]. CAAITrans Intell Syst， 2017， 12（6）： 883-888. DOI： 10.11992/tis.201706034.

[10] YANG X B， YU D J， YANG J Y， et al. DominancebasedRough Set Approach to Incomplete IntervalvaluedInformation System[J]. Data Knowl Eng， 2009，68（11）： 1331-1347. DOI： 10.1016/j.datak.2009.07.007.

[11] LUO C， LI T R， CHEN H M， et al. Incremental Approachesfor Updating Approximations in Set-valuedOrdered Information Systems[J]. Knowl Based Syst，2013， 50： 218-233. DOI： 10.1016/j.knosys.2013.06.013.

[12] LI S Y， LI T R， LIU D. Incremental Updating Approximationsin Dominance-based Rough Sets Approach underthe Variation of the Attribute Set[J]. Knowl Based Syst，2013， 40： 17-26. DOI： 10.1016/j.knosys.2012.11.002.

[13] JING Y G， LI T R， HUANG J F， et al. An IncrementalAttribute Reduction Approach Based on KnowledgeGranularity under the Attribute Generalization[J]. Int JApprox Reason， 2016， 76： 80-95. DOI： 10.1016/j.ijar.2016.05.001.

[14] 賀青青， 馬建敏， 丁娜. 形式背景上基于矩陣信息熵的矩陣熵約簡[J]. 南京大學學報（自然科學）， 2023， 59（1）： 98-106. DOI： 10.13232/j.cnki.jnju.2023.01.010.

HE Q Q， MA J M， DING N. Matrix Information EntropyBased Matrix Entropy Reduction in Formal Contexts[J]. J Nanjing Univ Nat Sci， 2023， 59（1）： 98-106. DOI：10.13232/j.cnki.jnju.2023.01.010.

[15] QIAN J， MIAO D Q， ZHANG Z H， et al. Hybrid Approachesto Attribute Reduction Based on Indiscernibilityand Discernibility Relation[J]. Int J Approx Reason，2011， 52（2）： 212-230. DOI： 10.1016/j.ijar.2010.07.011.

[16] WANG S， LI T R， LUO C， et al. A Novel Approach forEfficient Updating Approximations in Dynamic OrderedInformation Systems[J]. Inf Sci， 2020， 507： 197-219. DOI： 10.1016/j.ins.2019.08.046.

[17] JING Y G， LI T R， FUJITA H， et al. An Incremental AttributeReduction Method for Dynamic Data Mining[J]. InfSci， 2018， 465： 202-218. DOI： 10.1016/j.ins.2018.07.001.

[18] 張義宗， 王磊， 徐陽. 屬性集變化下序決策信息系統(tǒng)的增量屬性約簡算法[J]. 南京大學學報（自然科學），2023， 59（5）： 813-822. DOI： 10.13232/j. cnki. jnju.2023.05.009.

ZHANG Y Z， WANG L， XU Y. Incremental AttributeReduction Algorithm for Ordered Decision InformationSystems with the Change of Attribute Set[J]. J NanjingUniv Nat Sci， 2023， 59（5）： 813-822. DOI： 10.13232/j.cnki.jnju.2023.05.009.

[19] JING Y G， LI T R， FUJITA H， et al. An Incremental AttributeReduction Approach Based on KnowledgeGranularity with a Multi-granulation View[J]. Inf Sci，2017， 411： 23-38. DOI： 10.1016/j.ins.2017.05.003.

[20] LIANG J Y， WANG F， DANG C Y， et al. A Group IncrementalApproach to Feature Selection Applying Rough SetTechnique[J]. IEEE Trans Knowl Data Eng， 2014， 26（2）：294-308. DOI： 10.1109/TKDE.2012.146.

[21] JING Y G， LI T R， LUO C， et al. An Incremental Approachfor Attribute Reduction Based on KnowledgeGranularity[J]. Knowl Based Syst， 2016， 104： 24-38.DOI： 10.1016/j.knosys.2016.04.007.

[22] 桑彬彬， 陳留中， 陳紅梅， 等. 優(yōu)勢關系粗糙集增量屬性約簡算法[J]. 計算機科學， 2020， 47（8）： 137-143.DOI： 10.11896/jsjkx.190700188.

SANG B B， CHEN L Z， CHEN H M， et al. MatrixbasedApproach for Calculating Knowledge Granulationand Its Application in Attribute Reduction[J]. ComputEng Sci， 2020， 47（8）： 137-143. DOI： 10.11896/jsjkx.190700188.

[23] SHU W H， SHEN H. Updating Attribute Reduction inIncomplete Decision Systems with the Variation of AttributeSet[J]. Int J Approx Reason， 2014， 55（3）： 867-884. DOI： 10.1016/j.ijar.2013.09.015.

[24] ZENG A P， LI T R， LIU D， et al. A Fuzzy Rough SetApproach for Incremental Feature Selection on HybridInformation Systems[J]. Fuzzy Sets Syst， 2015， 258： 39-60. DOI： 10.1016/j.fss.2014.08.014.

[25] 陳寶國， 陳磊， 鄧明， 等. 基于不完備混合序信息系統(tǒng)的增量式屬性約簡[J]. 工程科學與技術， 2024， 56（1）：65-81. DOI： 10.15961/j.jsuese.202201214.

CHEN B G， CHEN L， DENG M， et al. Incremental AttributeReduction Algorithm Based on Incomplete HybridOrder Information System[J]. Adv Eng Sci， 2024，56（1）： 65-81. DOI： 10.15961/j.jsuese.202201214.

[26] SANG B B， CHEN H M，YANG L， et al. IncrementalFeature Selection Using a Conditional Entropy Basedon Fuzzy Dominance Neighborhood Rough Sets[J].IEEE T Fuzzy Syst. 2022， 30（6）： 1683-1697. DOI：10.1109/TFUZZ.2021.3064686.

[27] 劉清. Rough 集及Rough 推理[M]. 北京： 科學出版社，2001.

LIU Q. Rough Set and Rough Reasoning[M]. Beijing：Science Press， 2001.

28] HU Q H， GUO M Z， YU D R， et al. Information Entropyfor Ordinal Classification[J]. Sci China Inf Sci， 2010， 53（6）： 1188-1200. DOI： 10.1007/s11432-010-3117-7.

基金項目：國家自然科學基金（61703363）；山西省基礎研究計劃項目（201801D121148）；運城學院數(shù)據(jù)挖掘與工業(yè)智能應用科研創(chuàng)新團隊（YCXYTD-202402）；運城學院科研項目（321701）