摘要 粒計(jì)算和知識約簡是知識發(fā)現(xiàn)和數(shù)據(jù)挖掘的兩個(gè)重要課題?;谛畔⒘Q芯坎粎f(xié)調(diào)決策形式背景的屬性約簡的定義和方法。首先,利用對象概念的內(nèi)涵定義對象集上的擬序關(guān)系,并研究其相關(guān)性質(zhì)。然后,利用擬序類定義分布函數(shù)和最大部分函數(shù),進(jìn)而提出不協(xié)調(diào)決策形式背景的(最大)分布協(xié)調(diào)集和(最大)分布約簡的定義。最后,定義不協(xié)調(diào)決策形式背景的(最大)分布辨識矩陣及(最大)分布辨識公式,基于辨識矩陣給出(最大)分布協(xié)調(diào)集的判定定理,并提出計(jì)算分布約簡和最大分布約簡的方法。
關(guān)鍵詞 信息粒;不協(xié)調(diào)決策形式背景;分布約簡;最大分布約簡;辨識矩陣
中圖分類號:TP301 DOI:10.16152/j.cnki.xdxbzr.2024-04-011
Distribution reduction of inconsistent formal decisioncontexts based on information granules
WANG Xia, LI Junyu, WU Weizhi
Abstract Granular computing and knowledge reduction are two important topics in knowledge discovery and data mining. Based on information granules, this paper studies the definition and method of attribute reduction for inconsistent formal decision contexts. First, a quasi-ordering relation on the object set is defined and its related properties are studied too. Then, a distribution function and a maximum distribution function are defined using the quasi-ordering classes. Moreover, a distribution reduct and a maximum distribution reduct are proposed for the inconsistent formal decision context. Finally, a (maximum) distribution discernibility matrix and the corresponding distribution discernibility functions are introduced into the inconsistent formal decision context. And the judgment theorems of the (maximum) distribution consistent set are given to calculate all the distribution reducts and the maximum distribution reducts.
Keywords information granule; inconsistent formal decision context; distribution reduct; maximum distribution reduct; discernibility matrix
粒度計(jì)算是知識表示和數(shù)據(jù)挖掘中的一個(gè)基本問題。粒是粒計(jì)算的一個(gè)基本概念,它是以不可區(qū)分性、相似性或功能性標(biāo)準(zhǔn)聚集在一起的一簇對象[1]。而粒計(jì)算的主要研究方向有粒的構(gòu)建、解釋及粒的表示。文獻(xiàn)[2]將粒的概念引入到形式概念分析中,構(gòu)建了形式背景的信息粒和對象粒。形式概念分析[3]是由德國數(shù)學(xué)Wille于1982年提出的,其基本概念為形式背景和形式概念。形式背景是一個(gè)三元組,它由對象集、屬性集和二元關(guān)系構(gòu)成,其中二元關(guān)系指定了哪些對象具有哪些屬性。而形式概念是由一個(gè)對象集 (稱為外延)和一個(gè)屬性集(稱為內(nèi)涵)構(gòu)成,其中內(nèi)涵恰好是由外延中的對象共同具有的那些屬性組成,外延恰好是由共同具有內(nèi)涵中所有屬性的那些對象組成。特別地,由單個(gè)對象生成的形式概念稱為對象概念,而所有對象概念的集合是反映概念格結(jié)構(gòu)的信息粒,并稱對象概念的外延集為概念格的對象粒[2]。基于對象粒,文獻(xiàn)[2]還提出了形式背景的粒約簡。一個(gè)粒約簡是保持形式背景的所有對象粒不變的一個(gè)極小屬性子集。
文獻(xiàn)[2-25]從不同的角度或根據(jù)不同的目的研究了形式背景的屬性約簡。其中文獻(xiàn)[16-22]在帶有決策的形式背景中引入了形式背景的幾種協(xié)調(diào)性的概念,并進(jìn)一步研究了協(xié)調(diào)決策形式背景的不同屬性約簡方法。文獻(xiàn)[23]基于不協(xié)調(diào)決策形式背景提出了分布約簡和最大分布約簡的概念。文獻(xiàn)[24]在多粒度決策形式背景中引入?yún)f(xié)調(diào)粒度層的信息熵及條件信息熵,提出協(xié)調(diào)粒度約簡方法、最粗協(xié)調(diào)粒度約簡方法、最細(xì)協(xié)調(diào)粒度約簡方法及其實(shí)現(xiàn)算法。文獻(xiàn)[25]定義了多源決策形式背景及其屬性約簡。在實(shí)際問題中,由于預(yù)測能力、數(shù)據(jù)中的噪聲等各種因素導(dǎo)致很多決策形式背景是不協(xié)調(diào)的。由于不協(xié)調(diào)性,從決策形式背景中提取有用的信息會(huì)變得更加復(fù)雜和困難。而屬性約簡可以使隱藏在決策形式背景中的知識更加清晰,使決策形式背景的知識表示更加簡潔,使規(guī)則集對決策形式背景的適應(yīng)性更強(qiáng)。Wu等[2]基于對象粒提出了協(xié)調(diào)決策形式背景的屬性約簡方法,但是并未研究不協(xié)調(diào)決策形式背景的屬性約簡的相關(guān)問題。在不協(xié)調(diào)決策形式背景下通常需要構(gòu)造恰當(dāng)?shù)暮瘮?shù)借此對形式背景進(jìn)行約簡。
本文首先利用對象粒定義決策形式背景上的分布函數(shù)和最大分布函數(shù),進(jìn)而研究對象粒下不協(xié)調(diào)決策形式背景的(最大)分布約簡的定義及方法。
3 結(jié)語
由對象概念可以生成所有的形式概念,因此,對象概念構(gòu)成的集合稱為概念格的信息粒,它包含了形式背景的本質(zhì)信息?;谛畔⒘?梢詫π问奖尘耙约皫в袥Q策的協(xié)調(diào)形式背景進(jìn)行屬性約簡,從而達(dá)到簡化形式背景的目的。同樣地,利用信息粒也可以對不協(xié)調(diào)決策形式背景進(jìn)行簡化。本文考慮不協(xié)調(diào)的決策形式背景的約簡問題。通過對象集上的擬序關(guān)系引入了對象粒下不協(xié)調(diào)決策形式背景的(最大)分布約簡,提出了兩種計(jì)算約簡的方法以及(最大)分布協(xié)調(diào)集的判定定理。
參考文獻(xiàn)
[1]ZADEH L A. Toward a theory of fuzzy information granulation and its centrality in human reasoning and fuzzy logic[J]. Fuzzy Sets and Systems, 1997,90(2): 111-127.
[2]WU W Z, LEUNG Y, MI J S. Granular computing and knowledge reduction in formal contexts[J]. IEEE Transactions on Knowledge and Data Engineering, 2009, 21(10): 1461-1474.
[3]GANTER B, WILLE R. Formal concept analysis: Mathematical foundations[M].New York: Springer-Verlag, 1999.
[4]張文修, 仇國芳. 基于粗糙集的不確定決策[M]. 北京: 清華大學(xué)出版社, 2005.
[5]ZHANG W X, WEI L, QI J J. Attribute reduction theory and approach to concept lattice[J]. Science in China Series F: Information Sciences, 2005, 48(6): 713-726.
[6]WANG X, MA J M. A novel approach to attribute reduction in concept lattices[J]. Lecture Notes in Artificial Intelligence, 2006, 4062: 522-529.
[7]WANG X. Approaches to attribute reduction in concept lattices based on rough set theory[J]. International Journal of Hybrid Information Technology, 2012, 5(2): 67-80.
[8]WAN Q, WEI L. Attribute reduction based on property pictorial diagram[J]. Scientific World Journal, 2014: 109706.
[9]DIAS S M, VIEIRA N J. Concept lattices reduction: Definition, analysis and classification[J]. Expert Systems with Applications, 2015, 42(20): 7084-7097.
[10]賀明利, 魏玲. 基于優(yōu)勢關(guān)系的序形式背景約簡[J]. 計(jì)算機(jī)科學(xué), 2015, 42(6): 46-49.
HE M L, WEI L. Reduction of ordered formal context based on dominance relation[J]. Computer Science, 2015, 42(6): 46-49.
[11]LI T J, LI M Z, GAO Y. Attribute reduction of concept lattice based on irreducible elements[J]. International Journal of Wavelets, Multiresolution and Information Processing, 2013, 11(6):1350046.
[12]馬文勝, 侯錫林. 形式概念分析中的同效關(guān)系與概念約簡[J].計(jì)算機(jī)科學(xué), 2023, 50(4): 63-76.
MA W S, HOU X L. Same effect relation and concept reduction in formal concept analysis[J]. Computer Science, 2023, 50(4): 63-76.
[13]AKRAM M, NAWAZ H S, DEVECI M. Attribute reduction and information granulation in Pythagorean fuzzy formal contexts[J]. Expert Systems with Applications, 2023, 222: 119794.
[14]李同軍, 徐珍珍, 吳明瑞, 等. 經(jīng)典-經(jīng)典變精度概念格的一種屬性約簡[J].西北大學(xué)學(xué)報(bào)(自然科學(xué)版),2022, 52(5): 765-773.
LI T J, XU Z Z, WU M R, et al. An attribute reduction of crisp-crisp variable threshold concept lattices[J]. Journal of Northwest University (Natural Science Edition), 2022, 52(5): 765-773.
[15]LI J H, MEI C L, LV Y J. Knowledge reduction in decision formal contexts[J]. Knowledge-Based Systems, 2011, 24(5): 709-715.
[16]LI L J, MI J S, XIE B. Attribute reduction based on maximal rules in decision formal context[J]. International Journal of Computational Intelligence Systems, 2014, 7(6): 1044-1053.
[17]WEI L, QI J J, ZHANG W X. Attribute reduction theory of concept lattice based on decision formal contexts[J]. Science in China Series F: Information Sciences, 2008, 51(7): 910-923.
[18]PEI D, MI J S. Attribute reduction in decision formal context based on homomorphism[J]. International Journal of Machine Learning and Cybernetics, 2011, 2: 289-293.
[19]LI J H, MEI C L, LV Y J. Knowledge reduction in formal decision contexts based on an order-preserving mapping[J]. International Journal of General Systems, 2012, 41(2): 143-161.
[20]李進(jìn)金, 張燕蘭, 吳偉志, 等. 形式背景與協(xié)調(diào)決策形式背景屬性約簡與概念格生成[J]. 計(jì)算機(jī)學(xué)報(bào), 2014, 37(8): 1768-1774.
LI J J, ZHANG Y L, WU W Z, et al. Attribute reduction for formal context and consistent decision formal context and concept lattice generation[J]. Chinese Journal of Computers, 2014, 37(8): 1768-1774.
[21]WANG X, WU W Z. Approximate reduction in inconsistent formal decision contexts[C]∥2012 IEEE International Conference on Granular Computing. Hangzhou, China: IEEE, 2012: 1-6.
[22]WANG X. Construction of a unified model for formal contexts and formal decision contexts[J]. International Journal of Database Theory and Application, 2014, 7(2): 81-90.
[23]LI J Y, WANG X, WU W Z, et al. Attribute reduction in inconsistent formal decision contexts based on congruence relations[J]. International Journal of Machine Learning and Cybernetics, 2017, 8:81-94.
[24]李金海, 周新然. 多粒度決策形式背景的屬性約簡[J]. 模式識別與人工智能, 2022, 35(5): 387-400.
LI J H, ZHOU X R. Attribute reduction in multi-granularity formal decision contexts[J].Pattern Recognition and Artificial Intelligence, 2022, 35(5): 387-400.
[25]魏玲, 王振, 錢婷, 等. 多源決策形式背景的屬性約簡[J].陜西師范大學(xué)學(xué)報(bào)(自然科學(xué)版), 2019, 47(5): 57-63.
WEI L, WANG Z, QIAN T, et al. The attribute reduction of multi-source formal decision contexts[J]. Journal of Shaanxi Normal University (Natural Science Edition), 2019, 47(5): 57-63.
(編 輯 張 歡)
收稿日期:2023-10-20
基金項(xiàng)目:國家自然科學(xué)基金(12371466)
第一作者:王霞,女,博士,副教授,從事形式概念分析與粒計(jì)算相關(guān)研究,bblylm@126.com。