Font Size: a A A

Study Of Algorithms For Attribute Reduction In Concept Lattices

Posted on:2012-06-21Degree:MasterType:Thesis
Country:ChinaCandidate:Q S CengFull Text:PDF
GTID:2248330395955433Subject:Computer software and theory
Abstract/Summary:PDF Full Text Request
Formal concept analysis (FCA) was proposed by Wille R. in1982, which is a dataanalysis tool used in concept discovery, sorting and display. As a kind of efficient andpotential knowledge discovery tool, FCA receives much attention from artificialintelligence field. FCA is widely used in many engineering fields, such as machinelearning, pattern recognition, expert system, computer network, decision analysis anddata mining.One important task of knowledge discovery and data analysis is knowledgereduction. Concept lattices reduction provides a powerful knowledge and data reductiontool for artificial intelligence, knowledge discovery and data mining based on FCA.This thesis introduces general theory of FCA and mainly studies six concept latticereduction (CLR) methods. These methods are CLR method based on attribute feature,CLR method based on discernibility attribute matrix(DAM), CLR method based on newDAM, CLR method based on granule, CLR method based on meet-irreducible conceptand CLR method based on join-irreducible concept.Considering the real executing efficiency of these CLR methods, designing andalgorithm implementation of each CLR method is provided according to concept latticereduction theory. Analysis of time and space complexity and comparing of these CLRalgorithms are made at last in this thesis. The result of experiments indicates that thealgorithm based on attribute feature has quite high reduction efficiency, which is about athousand times faster than the others. The algorithm based on new discernibility matrixis about7times faster than the one based on discernibility matrix and about1.25timesfaster than algorithm based on granule. At the same time, the algorithms based onirreducible element have the same reduction efficiency. The quantitative comparingananlysis of reduction algorithms provide a practical reference value for the study andapplication of concept lattice attribute reduction.
Keywords/Search Tags:Formal Context, Concept Lattice, Attribute Reduction, DiscernibilityMatrix, Irreducible Element
PDF Full Text Request
Related items