Font Size: a A A

Research On Distributed Treatment Of Concept Lattices And Knowledge Discovery Based On Its Framework

Posted on:2006-03-06Degree:DoctorType:Dissertation
Country:ChinaCandidate:Y LiFull Text:PDF
GTID:1118360155960316Subject:Control theory and control engineering
Abstract/Summary:PDF Full Text Request
The concept lattices with the favorable mathematic properties have been successfully applied in a lot of fields such as Knowledge Discovery, but the time complexity of building concept lattice is a factor restricting the application of formal concept analysis for the completeness of concept lattice. The concept lattice construction is a premise of the application of Formal Concept Analysis (FCA). At present, the incremental formation algorithm of concept lattice has behaved strong vitality and flexibility. Most of such algorithm is object-based approaching algorithm, which is based on adding objects gradually into the lattice being formed, but the attribute-based algorithm has not been reported. However, the context varies in two directions: one is in objects, the other is in attributes. The undistinguishable objects can be distinguished as the increasing attributes, and the distinguishable objects become the same category, as the decreasing attributes. This dissertation suggests a different incremental algorithm of concept lattice construction, which is attribute-based, i.e., the algorithm is based on increasing attributes during the construction process. It not only provides a new approach for building concept lattice, but also resolves the problem of concept lattice update caused by appending new attributes into an existing context of the lattice, in addition establishes the foundation for the horizontal union of concept lattices of distributed contexts.With the increase of formal contexts, the time and space complexity of building concept lattice will sharply increase. It is one of the most important contents for the concept lattice technique to research the new methods and techniques of concept lattice construction. The many algorithms of building concept lattice are aimed at single concept lattice. The Divide-and-conquer Strategy is the effective approach of forming concept lattice. The approach of distributed construction of concept lattice is as follows: First decompose the formal context into many sub-contexts and construct corresponding sublattice, then obtain the concept lattice by combining these sub-lattices.Concept lattice is a representation of relationship between concepts in formal context, and it is corresponding one by one with the formal context, so the distributedtreatment of concept lattice certainly relates to some treatments and operations such as the decomposition and combination of context. Based on the horizontal and vertical combination or apposition and subposition in formal contexts, this dissertation defines two kinds of contexts and lattices, and researches the method of inconsistent contexts treatment, and also proves that the concept lattice of subcontexts horizontally combined is isomorphic to the horizontal union of sublattices of these subcontexts. Using the inherent general-special relation between concepts in sublattice and inheriting the existed incremental algorithm of concept lattice construction and modifying the algorithm, the horizontal union algorithm of multiple concept lattices to construct the concept lattice is presented, which is very suitable for combining many sub-lattices.Data Mining is to extract automatically the usable potential information and knowledge from data, and these information and knowledge express as concept, rule or pattern. The association rule is the main form of knowledge extracted from the database, and which is one of the major goals in the data mining. The rules are usually extracted from frequent itemsets, but the number of frequent itemsets is enormous. There exist many redundant rules during rules are extracted from frequent itemsets. In order to reduce the number of frequent itemsets without loss any useful information, frequent closed itemsets are adopted to extract the minimal non-redundant association rules.Based on careful studying and analyzing the algorithms for mining rules from the frequent closed itemsets and the inherent closure properties in concept lattice, this dissertation carries through the deeply research on extracting the minimal non-redundant rules on the concept lattice. In order to extract the minimal non-redundant rules conveniently, we define the Quantitative Closed Itemset Lattice(QCIL) and find out the key of extracting such rule is to obtain the least itemsets in the set of frequent itemsets with the same tidset which corresponds to the nodes in such lattice, and provide the methods of computing the Set of the Least ITemsets(SLIT) by adopting power set and difference set, and present an innovative algorithm of extracting the association rule, which can directly extract minimal non-redundant association rules from the QCIL. For the sake of more reducing the number of rules to satisfy special requirement of user, this dissertation brings forward the global succinct association rule, and presents the algorithm of extracting such rule using concept lattice.At present, there are a lot of researches on extracting associate rules but a few of...
Keywords/Search Tags:concept lattice, formal context, partial lattice, apposition and subposition, divide-and-conquer strategy, frequent closed itemset, itemset with the same tidset, minimal non-redundant rule, succinct rule, quantitative closed itemset lattice
PDF Full Text Request
Related items