[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()

Share：

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.

Common functions