[1] Yang Bin, Xu Baowen, Li Yajun,. Theoretical framework for distributed reduction in concept lattice [J]. Journal of Southeast University (English Edition), 2008, 24 (1): 20-24. [doi:10.3969/j.issn.1003-7985.2008.01.005]
Copy
Theoretical framework for distributed reduction in concept lattice(
)
基于概念格的分布式约简理论框架
)Journal of Southeast University (English Edition)[ISSN:1003-7985/CN:32-1325/N]
- Volumn:
- 24
- Issue:
- 2008 1
- Page:
- 20-24
- Research Field:
- Computer Science and Engineering
- Publishing date:
- 2008-03-30
Info
- Title:
- Theoretical framework for distributed reduction in concept lattice
- 基于概念格的分布式约简理论框架
- Author(s):
- Yang Bin; Xu Baowen; Li Yajun
- School of Computer Science and Engineering, Southeast University, Nanjing 210096, China
- Keywords:
- distributed reduction; knowledge processing; formal context
- PACS:
- TP391
- DOI:
- 10.3969/j.issn.1003-7985.2008.01.005
- Abstract:
- In order to reduce knowledge reasoning space and improve knowledge processing efficiency, a framework of distributed attribute reduction in concept lattices is presented. By employing the idea similar to that of the rough set, the characterization of core attributes, dispensable attributes and unnecessary attributes are described from the point of view of local formal contexts and virtual global contexts.A determinant theorem of attribute reduction is derived.Based on these results, an approach for distributed attribute reduction is presented.It first performs reduction independently on each local context using the existing approaches, and then local reducts are merged to compute reducts of global contexts.An algorithm implementation is provided and its effectiveness is validated.The distributed reduction algorithm facilitates not only improving computation efficiency but also avoiding the problems caused by the existing approaches, such as data privacy and communication overhead.
- 为了缩减知识推理空间, 提高分布式环境下知识处理的效率, 提出分布式概念格属性约简的理论框架.基于粗糙集理论的思想, 从子形式背景和全局形式背景的角度, 刻画了核心属性、相对必要属性和绝对不必要属性的属性特征, 给出属性约简的判定定理.在此基础上, 给出概念格的分布式属性约简方法:首先, 使用现有的约简方法分别计算各子形式背景的约简, 然后, 逐一利用各子背景的约简, 通过合并计算得到全局形式背景的约简.给出了算法的实现并用实例验证了它的有效性.分布式约简有效避免了使用现有方法而引起的数据安全和网络通信等问题, 提高了约简的计算效率.
References:
[1] Wille R.Restructuring lattice theory:an approach based on hierarchies of concepts[C]//Ordered Sets.Dordrecht-Boston:Reidel, 1982:445-470.
[2] Ganter B, Wille R. Formal concept analysis:mathematical foundations[M].Berlin:Springer, 1999:11-18.
[3] Eisenbarth T, Koschke R. Locating features in source code[J].IEEE Transactions on Software Engineering, 2003, 29(3):195-209.
[4] Godin R, Missaoui R, April A.Experimental comparison of navigation in a galois lattice with conventional information retrieval methods[J].Int J Man-Machine Studies, 1993, 38(12):747-767.
[5] Skowron A, Rauszwer C.The discernibility matrices and functions in information systems[C]//Intelligent Decision Support:Handbook of Applications and Advances of the Rough Set Theory.Dordrecht:Kluwer Academic Publishers, 1992:331-362.
[6] Maddouri M.Towards a machine learning approach based on incremental concept formation[J].Intelligent Data Analysis, 2004, 8(3):267-280.
[7] Kent R.Rough concept analysis:a synthesis of rough sets and formal concept analysis[J].Fund Information, 1996, 27(2):169-181.
[8] Yao Y Y.A comparative study of formal concept analysis and rough set theory in data analysis[C]//Proc of the 4th International Conference on Rough Sets and Current Trends in Computing.Heidelberg:Springer-Verlag, 2004:59-68.
[9] Slezak D, Ziarko W.Attribute reduction in the Bayesian version of variable precision rough set model[J].Electr Notes Theor Comput Sci, 2003, 82(4):1-11.
[10] Godin R, Missaoui R, Alaoui H.Incremental concept formation algorithms based on galois lattices[J].Computational Intelligence, 1995, 11(2):246-267.
[11] Zhang Wenxiu, Wei Ling, Qi Jianjun.The theory and approach of attribute reduction in concept lattice[J].Science in China Series E: Informational Science, 2005, 35(6):628-639.(in Chinese)
[12] Shao M W.The reduction for two kinds of generalized concept lattice[C]//Proc of the 4th International Conference on Machine Learning and Cybernetics.Heidelberg:Springer-Verlag, 2005:2217-2222.
[13] Li H R, Zhang W X, Wang H.Classification and reduction of attributes in concept lattices[C]//Proc of IEEE International Conference on Granular Computing. Atlanta, USA, 2006:142-147.
[14] Shen X J, Liu Z T, Zhang Q, et al.Isomorphic generating of concept lattices[C]//Proc of IEEE International Conference on Granular Computing.Beijing, China, 2005:249-252.
[15] Yang B, Xu B W, Li Y J.An incremental approach for attribute reduction in concept lattice[C]//Proc of the 2nd International Conference on Rough Sets and Knowledge Technology.Heidelberg:Springer-Verlag, 2007:451-459.
[16] Hu K, Sui Y, Lu Y, et al.Concept approximation in concept lattice[C]//Proc of the 5th Pacific-Asia Conference.Heidelberg:Springer-Verlag, 2001:167-173.
[17] Agrawal R, Mannila H, Srikant R, et al.Fast discovery of association rules[C]//Advances in Knowledge Discovery and Data Mining.Menlo Park:American Association for Artificial Intelligence, 1996:307-328.
Memo
- Memo:
-
Biographies: Yang Bin(1980—), male, graduate; Xu Baowen(corresponding author), male, doctor, professor, bwxu@seu.edu.cn.
Foundation items: The National Outstanding Young Scientist Foundation by NSFC(No.60425206), the National Natural Science Foundation of China(No.60503020), the Natural Science Foundation of Jiangsu Province(No.BK2006094).
Citation: Yang Bin, Xu Baowen, Li Yajun.Theoretical framework for distributed reduction in concept lattice[J].Journal of Southeast University(English Edition), 2008, 24(1):20-24.