基于覆盖的区间概念格动态压缩原理与实现

doi:10.6040/j.issn.1671-9352.1.2014.207

山东大学学报（理学版） ›› 2014, Vol. 49 ›› Issue (08): 15-21.doi: 10.6040/j.issn.1671-9352.1.2014.207

基于覆盖的区间概念格动态压缩原理与实现

张春英, 王立亚, 刘保相

河北联合大学理学院, 河北唐山 063009

收稿日期:2014-06-02 修回日期:2014-07-08 出版日期:2014-08-20 发布日期:2014-09-24
通讯作者: 王立亚（1987-），女，硕士研究生，研究方向为概念格与数据挖掘.E-mail：wang_liya@126.com E-mail:wang_liya@126.com
作者简介:张春英（1969-），女，博士，教授，研究方向为概念格、人工智能、多关系数据挖掘等.E-mail：zchunying@heuu.edu.cn
基金资助:
国家自然科学基金资助项目（61370168）；河北省自然科学基金资助项目（A2011209046，F2012209019）

Dynamic reduction theory for interval concept lattice based on covering and its realization

ZHANG Chun-ying, WANG Li-ya, LIU Bao-xiang

College of Science, Hebei United University, Tangshan 063009, Hebei, China

Received:2014-06-02 Revised:2014-07-08 Online:2014-08-20 Published:2014-09-24

摘要/Abstract

摘要： 针对区间概念格的复杂结构以及基于现有建格算法构建的区间概念格存在概念冗余问题，本文直接从形式背景出发，对区间概念格进行动态压缩的方法，减少了区间概念结点的冗余度。为了保证概念压缩后仍能体现概念之间的关联关系，首先给出了基于形式背景的二元关系对的相似度及关系上的覆盖近邻空间的定义；其次，通过定义区间概念压缩算子，得到了压缩概念，并证明了压缩后的概念集是压缩前概念集的子集；基于覆盖的近邻空间及压缩算子，进一步构建了区间概念格的动态压缩模型。可以根据相似类阈值大小控制区间概念格中的结点数量，实现区间概念格的动态压缩，最后通过实例验证了模型的正确性以及压缩的高效性。

关键词: 覆盖近邻空间, 区间概念格, 关系相似度

Abstract: The structure of interval concept lattice is complex and the lattice built by the existing construction algorithm has the problem of concept redundancy. To reduce the redundancy of interval concepts, a dynamic reduction method for interval concept lattice is put forward which starts from a formal context directly. Firstly, the similarity degree of the binary relations and covering-neighborhood-space are defined which could ensure that the compressed lattice still can reflect the relationship between concepts. Secondly, according to the reduction operators, the compressed concept is acquired. Thirdly, it is proved that the reduced interval concept set is a subset of the original. Then, it built the dynamic reduction model for interval concept lattice based on the covering-neighborhood-space and reduction operators. The number of concepts in lattice is controlled by the threshold value of similarity class which can realize the dynamic of reduction. Finally, the correctness of model and the high efficiency of reduction are shown by a case study.

Key words: interval concept lattice, similarity degree of relationship, covering-neighborhood-space

中图分类号:

TP301.6

张春英, 王立亚, 刘保相. 基于覆盖的区间概念格动态压缩原理与实现[J]. 山东大学学报（理学版）, 2014, 49(08): 15-21.

ZHANG Chun-ying, WANG Li-ya, LIU Bao-xiang. Dynamic reduction theory for interval concept lattice based on covering and its realization[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2014, 49(08): 15-21.

参考文献

[1] WILLE R. Restructuring lattice theory: an approach based on hierarchies of concepts[M]//Formal Concept Analysis Lecture Notes in Computer Science. Reidel I. Boston: D. Reidel Publishing Company, 1982: 445-470.
[2] 杨海峰,张继福.粗糙概念格及构造算法[J].计算机工程与应用,2007,43(24):172-175. YANG Haifeng,ZHANG Jifu. Rough concept lattice and construction arithmetic[J]. Computer Engineering and Applications, 2007, 43(24):172-175.
[3] 刘宗田,强宇,周文,等. 一种模糊概念格模型及其渐进式构造算法[J].计算机学报,2007,30:184-188. LIU Zongtian, QIANG Yu, ZHOU Wen, et al. A fuzzy concept lattice model and its incremental construction algorithm[J]. Chinese Journal of Computers, 2007, 30:184-188.
[4] 张继福,张素兰.加权概念格及其渐进式构造[J].模式识别与人工智能,2005,18(2):171-176. ZHANG Jifu, ZHANG Sulan, ZHENG Lian. Weighted concept lattice and incremental construction[J]. Pattern Recognition and Artificial Intelligence, 2005, 18(2):171-176.
[5] 刘保相,张春英.一种新的概念格结构--区间概念格[J].计算机科学,2012,39(8):273-277. LIU Baoxiang, ZHANG Chunying. New concept lattice structure--interval concept lattice[J]. Computer Science, 2012, 39(8):273-277.
[6] CHUNG K S K, VOGEL D. Complexity reduction in lattice based information retrieval[J]. Information Retrieval, 2005, 8:285-299.
[7] ZHANG Wenxiu, Wei Ling, Qi Jianjun. Attribute reduction in concept lattice based on discernibility matrix[C]//SLEZAK D. Lecture Notes in Artificial Intelligence Proceedings of RSFDGrC. Canada: Springer, 2005: 157-165.
[8] 王霞,张文修.概念格的属性约简与属性特征[J].计算机工程与应用,2008,44(12):1-4. WANG Xia, ZHANG Wenxiu. Attribute reduction in concept lattices and attribute characteristics[J]. Computer Engineering and Applications,2 008, 44(12):1-4.
[9] KUMAR A C, SPRINIVAS S. Concept lattice reduction using K-means clustering[J]. Expert Systems with Applications, 2010, 37(3):2696-2704.
[10] 魏玲,李强.面向属性概念格基于覆盖的压缩[J].电子科技大学学报,2012,41(2):299-304. WEI Ling, LI Qiang. Covering-based reduction of property-oriented concept lattices[J]. Journal of University of Electronic Science and Technology of China, 2012, 41(2):299-304.
[11] 陈永平,杨思春.面向对象概念格的压缩[J].计算机工程与应用,2013,49(19):119-122. CHEN Yongping, YANG Sichun. Reduction of object-oriented concept lattices[J]. Computer Engineering and Applications, 2013, 49(19):119-122.
[12] 张春英, 王立亚. 基于属性集合幂集的区间概念格L^β_α的渐进式生成算法[J].计算机应用研究,2014,31(3):731-734. ZHANG Chunying, WANG Liya. Incremental construction algorithm based on attribute power set for interval concept lattice L^β_α[J]. Application Research of Computers, 2014, 31(3):731-734.
[13] ZHU William. Relationship between generalized rough sets based on binary and covering[J]. Information Science, 2009, 179:210-225.

多维度评价

Viewed

Full text

Abstract

Cited

Shared

Discussed

基于覆盖的区间概念格动态压缩原理与实现

Dynamic reduction theory for interval concept lattice based on covering and its realization

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 5

多维度评价

本文评价

推荐阅读 0

[1]	齐平, 王福成, 王必晴. 一种基于图模型的可信云资源调度算法[J]. 山东大学学报（理学版）, 2018, 53(1): 63-74.
[2]	谢建民,姚兵,赵廷刚. 广义太阳图S_m,n奇优雅标号算法及实现[J]. 山东大学学报（理学版）, 2016, 51(4): 79-85.
[3]	郑向伟,刘弘 . 一种多样性引导的两阶段多目标微粒群算法[J]. J4, 2008, 43(11): 5-10 .
[4]	宋乐辉,陈月辉,潘萌 . 动态系统的演化建模[J]. J4, 2008, 43(11): 27-30 .
[5]	袁晓航,杜小勇 . iRIPPER——一种改进的基于规则学习的文本分类算法[J]. J4, 2007, 42(11): 66-68 .