Research On The Algorithm Of Binary Relation Decrement For Concept Lattice With Limited Memory

As a method of concept clustering,concept lattice(also called formal concept analysis)has been proved to be beneficial to machine learning,information retrieval and knowledge discovery.In practical applications,formal context that generates concept lattice changes over time.As a result,a large number of redundant objects,attributes,or binary relationships between objects and attributes occur and lead to increasement of ineffective concepts in concept lattice.Removing these ineffective concepts is propitious to reduce the size of the concept lattice,thereby helping to acquire knowledge faster and more accurately.At present,most of the research scholars focus on the gradual decrement of the object or attribute maintenance work and there is little research on the maintenance work of the binary relationship granularity.In order to reduce the size of the concept lattice and improve the structural efficiency of the concept lattice,a new method of concept lattice maintenance based on binary relation decrement is proposed in this thesis.Unlike the traditional concept lattice based on the new form context,the method obtains a new concept lattice by adjusting the original concept lattice,thus saving a lot of time of construction.In this thesis,we first analyze the correspondence of nodes and change rules of edges between the original concept lattice and the new concept lattice.On this basis,we propose a bottom-up and breadth-first binary relation decrement algorithm of concept lattice.The algorithm can handle the binary relation decrement in any position in formal context.To a certain extent,it has been proved that the construction efficiency of concept lattice can be significantly improved through this algorithm compared with the traditional algorithmHowever,when the concept lattice is too large to be fully loaded into memory,the small-scale concept lattice maintenance algorithm based on the binary relation decrement is no longer applicable.Therefore,in order to solve the problem of effective maintenance of concept lattice in the situation of memory overflow whenthe concept lattices are loaded,this thesis proposes a maintenance algorithm based on external memory when memory space is limited.The algorithm divides the concept lattice according to the concept cluster,and uses the least recently used scheduling strategy to release the unwanted concept nodes in the memory and transfers the required concept blocks from the external memory,which effectively reduces the memory consumption and solves the problem of memory deficiency and finally provides protection for the application of concept lattice.In this thesis,two aspects of theory and experimental results show this method can ensure effective maintenance of concept lattices with smaller memory consumption and time cost in condition of limited memory resources.