-
摘要: 针对影响概念格应用的重要问题—即使是一个小规模数据集也会产生大量的形式概念,文中提出了可以满足关系覆盖的用对象(属性)概念分解形式背景对应的布尔矩阵的新方法.用这种方法原对象属性间的二元关系可以用数量在对象(属性)概念个数以内的概念表达出来,成为概念格因子.文中给出了概念格因子生成的基本原理及其算法.通过分析三维CAD零件模型功能表面间的关系构建零件工程图结构模型,并将其映射为形式背景,从而完成概念格因子到零件关键结构的应用.最后,实例演示了概念格因子在基于零件工程图结构模型的零件CAD模型检索中的运用.Abstract: A small set of data can result in a very large number of formal concepts. With regard to this important topic, we propose an objects (attributes) concept based approach to factor Boolean matrix for the formal context in this paper. We show that the original binary relations between objects and attributes can be represented by the objects (attributes) concept matrices whose total number of concepts (factors) does not exceed the number of objects (attributes) concepts. We propose an algorithm to generate the factors. This method relies on the fundamental finite factorization property of binary matrix factorization which we proposed and proved. After analyzing the function relation between the surfaces of the 3D CAD part models, building up the engineering drawing structure model, and mapping it to the formal context, we apply concept lattice factorization to the key parts structures. Experiments on parts CAD model retrieval have shown the competency and effectiveness of the concept lattice factorization.1) 本文责任编委 刘跃虎
-
表 1 一个形式背景
Table 1 An example of formal context
$a$ $b$ $c$ $d$ $e$ 1 $\times$ $\times$ 2 $\times$ $\times$ $\times$ 3 $\times$ $\times$ $\times$ $\times$ 4 $\times$ $\times$ 表 2 功能表面二元领域关系(1)
Table 2 Two-dimensional domain relation of functional surface (1)
同轴, 平行 关系含义 分离 相遇 重叠 共点 字母标记 $s$ $m$ $o$ $c$ 图示 表 3 功能表面二元领域关系(2)
Table 3 Two-dimensional domain relation of functional surface (2)
同轴, 平行 关系含义 分离 相遇 重叠 共点 字母标记 $s$ $m$ $o$ $c$ 图示 $l\parallel m$ $1\perp b$ $!\perp b$ $0\odot m$ $\sharp\odot s$ $C_{1} $ 0 $1$ 1 1 0 $C_{2}$ 0 1 0 1 0 $C_{3} $ 0 0 1 0 0 $P_{1}$ 0 0 0 1 1 $P_{2}$ 0 0 0 1 1 $P_{3}$ 1 1 0 0 0 $P_{4}$ 0 1 0 0 0 $H$ 1 0 0 0 0 表 5 模型库中部分零件与模型一的相似度值
Table 5 Similarity value of part and model 1 in the model base
表 6 模型库中部分零件与模型二的相似度值
Table 6 Similarity value of part and model 2 in the model base
表 7 在模型库中搜索的与模型一相似的零件与耗时
Table 7 The parts and time consuming that are similar to model 1 in the model base
表 8 在模型库中搜索的与模型二相似的零件与耗时
Table 8 The parts and time consuming that are similar to model 2 in the model base
-
[1] Belohlavek R, Macko J. Selecting important concepts using weights. In:Proceedings of the 2011 ICFCA. LNCS (LNAI), Heidelberg:Springer, 2011, 6628:65-80 [2] Rice M D, Siff M. Clusters, concepts, and pseudometrics. Electronic Notes in Theoretical Computer Science, 2001, 40:323-346 doi: 10.1016/S1571-0661(05)80060-X [3] Kumar C A, Srinivas S. Concept lattice reduction using fuzzy K-Means clustering. Expert Systems with Applications, 2010, 37(3):2696-2704 http://d.old.wanfangdata.com.cn/NSTLQK/NSTL_QKJJ0218648021/ [4] Li J H, Kumar C A, Mei C L, Wang X Z. Comparison of reduction in formal decision contexts. International Journal of Approximate Reasoning, 2017, 80:100-122 doi: 10.1016/j.ijar.2016.08.007 [5] 陈雪, 魏玲, 钱婷.基于AE-概念格的决策形式背景属性约简.山东大学学报:理学版, 2017, 52(12):95-103 http://d.old.wanfangdata.com.cn/Periodical/sddxxb201712015Chen Xue, Wei Ling, Qian Ting. Attribute reduction in formal decision contexts based on AE-concept lattices. Journal of Shandong University (Natural Science), 2017, 52(12):95-103 http://d.old.wanfangdata.com.cn/Periodical/sddxxb201712015 [6] Singh P K, Ch A K. A note on constructing fuzzy homomorphism map for a given fuzzy formal context. In:Proceedings of the 3rd International Conference on Soft Computing for Problem Solving. New Delhi, India:Springer, 2013. 845-855 [7] Shao M W, Leung Y, Wang X Z, Wu W Z. Granular reducts of formal fuzzy contexts. Knowledge-Based Systems, 2016, 114(15):156-166 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=e9ab4c8384f60c9c0741d7cad48f0179 [8] Konecny J, Krupka M. Block relations in formal fuzzy concept analysis. International Journal of Approximate Reasoning, 2016, 73:27-55 doi: 10.1016/j.ijar.2016.02.004 [9] Dias S M, Vieira N J. A methodology for analysis of concept lattice reduction. Information Sciences, 2017, 396:202-217 doi: 10.1016/j.ins.2017.02.037 [10] Konecny J. On attribute reduction in concept lattices:methods based on discernibility matrix are outperformed by basic clarification and reduction. Information Sciences, 2017, 415-416:199-212 doi: 10.1016/j.ins.2017.06.013 [11] Singh P K, Cherukuri A K, Li J H. Concepts reduction in formal concept analysis with fuzzy setting using Shannon entropy. International Journal of Machine Learning and Cybernetics, 2017, 8(1):179-189 doi: 10.1007/s13042-014-0313-6 [12] Babin M A, Kuznetsov S O. Approximating concept stability. In:Proceedings of the 10th International Conference on Formal Concept Analysis. Leuven, Belgium:Springer, 2012. 7-15 [13] Dias S M, Vieira N J. Applying the JBOS reduction method for relevant knowledge extraction. Expert Systems with Applications, 2013, 40(5):1880-1887 doi: 10.1016/j.eswa.2012.10.010 [14] Li J L, He Z Y, Zhu Q L. An entropy-based weighted concept lattice for merging multi-source geo-ontologies. Entropy, 2013, 15(6):2303-2318 http://d.old.wanfangdata.com.cn/OAPaper/oai_doaj-articles_ba198225a414207ba74504f7a21ccc9d [15] Kang X P, Li D Y, Wang S G, Qu K S. Formal concept analysis based on fuzzy granularity base for different granulations. Fuzzy Sets and Systems, 2012, 203:33-48 doi: 10.1016/j.fss.2012.03.003 [16] Li C P, Li J H, He M. Concept lattice compression in incomplete contexts based on K-medoids clustering. International Journal of Machine Learning and Cybernetics, 2016, 7(4):539-552 doi: 10.1007/s13042-014-0288-3 [17] Martin T P, Rahim N H A, Majidian A. A general approach to the measurement of change in fuzzy concept lattices. Soft Computing, 2013, 17(12):2223-2234 doi: 10.1007/s00500-013-1095-6 [18] Singh P K, Cherukuri A K, Li J H. Knowledge representation using interval-value fuzzy formal concept lattice. Soft Computing, 2016, 20(4):1485-1502 doi: 10.1007/s00500-015-1600-1 [19] Aswani Kumar Ch., Dias S M, Vieira N J. Knowledge reduction in formal contexts using non-negative matrix factorization. Mathematics and Computers in Simulation, 2015, 109:46-63 doi: 10.1016/j.matcom.2014.08.004 [20] Keprt A, Snášel V. Binary factor analysis with help of formal concepts. In:Proceedings of the 2004 International Workshop on Concept Lattices and their Applications. Ostrava, Czech Republic:CLA, 2004. 27-36 [21] Belohlavek R, Vychodil V. Discovery of optimal factors in binary datavia a novel method of matrix decomposition. Journal of Computer and System Sciences. 2010, 76(1):3-20 http://www.sciencedirect.com/science/article/pii/S0022000009000415 [22] 张运超, 陈靖, 王涌天.一种融合重力信息的快速海量图像检索方法.自动化学报, 2016, 42(10):1501-1511 http://www.aas.net.cn/CN/abstract/abstract18937.shtmlZhang Yun-Chao, Chen Jing, Wang Yong-Tian. Large-scale image retrieval based on a fusion of gravity aware orientation information. Acta Automatica Sinica, 2016, 42(10):1501-1511 http://www.aas.net.cn/CN/abstract/abstract18937.shtml [23] 姚拓中, 左文辉, 宋加涛, 应宏微.结合物体先验和空域约束的室内空域布局推理.自动化学报, 2017, 43 (8):1402-1411 http://www.aas.net.cn/CN/abstract/abstract19114.shtmlYao Tuo-Zhong, Zuo Wen-Hui, Song Jia-Tao, Ying Hong-Wei. Estimating spatial layout of cluttered rooms by using object prior and spatial constraints. Acta Automatica Sinica, 2017, 43(8):1402-1411 http://www.aas.net.cn/CN/abstract/abstract19114.shtml [24] Huang L, Guo S S, Tang H T, Li L, Ding K. Design of automatic parting in calibrator CAD for plastic profile extrusion dies via feature recognitions. International Journal of Advanced Manufacturing Technology, 2017, 88(5-8):1319-1331 doi: 10.1007/s00170-016-8852-5 [25] Tao S Q. 3D CAD model retrieval based on the softassign quadratic assignment algorithm. Multimedia Tools Applications. 2018, 77(13):16249-16265 doi: 10.1007/s11042-017-5197-5 [26] 张开兴, 杭晟煜, 赵秀艳, 王金星, 宋正河, 刘贤喜.面向设计重用的三维CAD模型局部结构检索方法.农业机械学报, 2017, 48(7):405-412, 375 http://d.old.wanfangdata.com.cn/Periodical/nyjxxb201707052Zhang Kai-Xing, Hang Sheng-Yu, Zhao Xiu-Yan, Wang Jin-Xing, Song Zheng-He, Liu Xian-Xi. Effective subpart retrieval method of 3D CAD models for design reuse. Transactions of the Chinese Society for Agricultural Machinery, 2017, 48(7):405-412, 375 http://d.old.wanfangdata.com.cn/Periodical/nyjxxb201707052 [27] 林昕. 三维CAD模型的形状特征提取与检索[博士学位论文]. 中国科学技术大学, 中国, 2017Lin Xin. The Shape Feature Extraction and Retrieval of Three Dimensional CAD Models[Ph.D. dissertation], Zhejiang University, China, 2017 [28] 潘翔, 王学成, 张三元.基于等距二分图的三维模型局部对齐.计算机辅助设计与图形学学报, 2016, 28(3):480-487 doi: 10.3969/j.issn.1003-9775.2016.03.014Pan Xiang, Wang Xue-Cheng, Zhang San-Yuan. 3D partial correspondence based on isometric bipartite graph. Journal of Computer-Aided Design & Computer Graphics, 2016, 28(3):480-487 doi: 10.3969/j.issn.1003-9775.2016.03.014 [29] 白静.基于扩展特征树的三维CAD模型相似评价.计算机集成制造系统, 2014, 20(2):267-275 http://d.old.wanfangdata.com.cn/Periodical/jsjjczzxt201402005Bai Jing. 3D CAD model similarity assessment based on extended feature tree. Computer Integrated Manufacturing Systems, 2014, 20(2):267-275 http://d.old.wanfangdata.com.cn/Periodical/jsjjczzxt201402005 [30] 徐静, 董雁.零件工程图结构检索方法.机械工程学报, 2011, 47 (20):191-198 http://d.old.wanfangdata.com.cn/Periodical/jxgcxb201120029Xu Jing, Dong Yan. Structure retrieval method for part engineering drawing. Journal of Mechanical Engineering, 2011, 47(20):191-198 http://d.old.wanfangdata.com.cn/Periodical/jxgcxb201120029 [31] 朱文博, 吴新仁, 甘屹.基于形状拆分的机械零件三维模型检索.图学学报, 2015, 36(1):35-40 doi: 10.3969/j.issn.2095-302X.2015.01.007Zhu Wen-Bo, Wu Xin-Ren, Gan Yi. 3D model retrieval of mechanical parts based on shape split. Journal of Graphics, 2015, 36(1):35-40 doi: 10.3969/j.issn.2095-302X.2015.01.007 [32] 皇甫中民, 张树生, 闫雒恒.鱼群启发的三维CAD模型聚类与检索.计算机辅助设计与图形学学报, 2016, 28(8):1373-1382, 1392 doi: 10.3969/j.issn.1003-9775.2016.08.020Huangfu Zhong-Min, Zhang Shu-Sheng, Yan Luo-Heng. 3D CAD model clustering and retrieval inspired by fish swarm. Journal of Computer-Aided Design & Computer Graphics, 2016, 28(8):1373-1382, 1392 doi: 10.3969/j.issn.1003-9775.2016.08.020 [33] 刘志文, 王耀侦, 庞枫骞, 李衡.基于自适应视距投影和类词典的三维模型检索.计算机工程与设计, 2016, 37(10):2744-2749 http://d.old.wanfangdata.com.cn/Periodical/jsjgcysj201610031Liu Zhi-Wen, Wang Yao-Zhen, Pang Feng-Qian, Li Heng. Adaptive visual distance rendering and class vocabularies based 3D model retrieval. Computer Engineering and Design, 2016, 37(10):2744-2749 http://d.old.wanfangdata.com.cn/Periodical/jsjgcysj201610031 [34] Gao S M, Shah J J. Automatic recognition of interacting machining features based on minimal condition subgraph. Computer-Aided Design, 1998, 30(9):727-739 doi: 10.1016/S0010-4485(98)00033-5 [35] El-Mehalawi M, Miller R A. A database system of mechanical components based on geometric and topological similarity. Part Ⅱ:indexing, retrieval, matching, and similarity assessment. Computer-Aided Design, 2003, 35(1):95-105 http://www.sciencedirect.com/science/article/pii/S0010448501001786 [36] Ma L J, Huang Z D, Wang Y W. Automatic discovery of common design structures in CAD models. Computers & Graphics, 2010, 34(5):545-555 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=36953e1b1ebf35c3bd15af03a21fc627 [37] Zhang J, Xu Z J, Li Y, Jiang S S, Wei N N. Generic face adjacency graph for automatic common design structure discovery in assembly models. Computer-Aided Design, 2013, 45(8-9):1138-1151 doi: 10.1016/j.cad.2013.04.003 [38] Tao S Q, Huang Z D, Zuo B Q, Peng Y P, Kang W R. Partial retrieval of CAD models based on the gradient flows in Lie group. Pattern Recognition, 2012, 45(4):1721-1738 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=f36f1ca331c79851af297ccd4721a77f [39] Chu C H, Hsu Y C. Similarity assessment of 3D mechanical components for design reuse. Robotics and Computer-Integrated Manufacturing, 2006, 22(4):332-341 doi: 10.1016/j.rcim.2005.07.005 [40] 徐静, 董雁.基于区域分割的零件三维模型检索方法.计算机辅助设计与图形学学报, 2017, 29(5):929-938 doi: 10.3969/j.issn.1003-9775.2017.05.018Xu Jing, Dong Yan. 3D part model retrieval method based on surface region decomposition. Journal of Computer-Aided Design & Computer Graphics, 2017, 29(5):929-938 doi: 10.3969/j.issn.1003-9775.2017.05.018 [41] Tao S Q, Wang S T, Chen A H. 3D CAD solid model retrieval based on region segmentation. Multimedia Tools and Applications, 2017, 76(1):103-121 doi: 10.1007/s11042-015-3033-3 [42] Sun Y, Ye S W, Sun Y, Kameda T. Improved algorithms for exact and approximate Boolean matrix decomposition. In:Proceedings of the 2015 IEEE International Conference on Data Science and Advanced Analytics. Paris, France:IEEE, 2015. 1-14 [43] Ganter B, Wille R. Formal Concept Analysis:Mathematical Foundations. Springer-Verlag New York, Inc. 1999. [44] Belohlavek R, Vychodil V. Discovery of optimal factors in binary data via a novel method of matrix decomposition. Journal of Computer and System Sciences, 2010, 76(1):3-20 doi: 10.1016/j.jcss.2009.05.002 [45] Belohlavek R, Vychodil V. Factorization of matrices with grades. Fuzzy Sets and Systems, 2015, 292:85-97 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=b5b67c6c3412da38e901fd2daea0788a [46] Belohlavek R, Trnecka M. From-below approximations in Boolean matrix factorization:geometry and new algorithm. Journal of Computer and System Sciences, 2015, 81(8):1678-1697 doi: 10.1016/j.jcss.2015.06.002 [47] 董雁, 徐静.基于装配结构相似的零件三维模型检索方法.机械工程学报, 2009, 45(4):273-280 http://d.old.wanfangdata.com.cn/Periodical/jxgcxb200904047Dong Yan, Xu Jing. Part 3D model retrieval method based on assembly structure similarity. Journal of Mechanical Engineering, 2009, 45(4):273-280 http://d.old.wanfangdata.com.cn/Periodical/jxgcxb200904047 [48] 王瑞霞, 彭国华.基于黎曼流形稀疏编码的图像检索算法.自动化学报, 2017, 43(5):778-788 http://www.aas.net.cn/CN/abstract/abstract19055.shtmlWang Rui-Xia, Peng Guo-Hua. An image retrieval method with sparse coding based on Riemannian manifold. Acta Automatica Sinica, 2017, 43(5):778-788 http://www.aas.net.cn/CN/abstract/abstract19055.shtml [49] 石俊飞, 刘芳, 林耀海, 刘璐.基于深度学习和层次语义模型的极化SAR分类.自动化学报, 2017, 43 (2):215-226 http://www.aas.net.cn/CN/abstract/abstract19010.shtmlShi Jun-Fei, Liu Fang, Lin Yao-Hai, Liu Lu. Polarimetric SAR image classification based on deep learning and hierarchical semantic model. Acta Automatica Sinica, 2017, 43(2):215-226 http://www.aas.net.cn/CN/abstract/abstract19010.shtml