Research On The Algorithoms For Visualizing Concept Lattice Using Tree Structure Based On Sub-lattice Merging

In the era of information explosion, it's significant to study how to visualize the diverse data source which growing rapidly. To make use of correlative information in the data for assisting visualization effectively has become a hot spot in current research.There are two problems using the corrective information in the data to make visualization through our study. Firstly, the current situation is that the expressions of data structure which is stored in the interior use tree structure to organize data information, although it's clear when browsing the hierarchy, but this kind of structure has only one access when finding files from the root to the target. It would probably make users backtrack many times in the process of obtaining the target file when the users are not sure about the path. Secondly, in this respect vitalization, because the tree structure does not support multipath retrieval, so lots of researches has begun to pay attention to concept lattice structure that expressed in Hasse diagram as a graphical representation. The concept lattice builds concept hierarchy structure based on the data set of binary relation between objects and attributes, not only supports multipath retrieval, and it also has the advantage of displaying interconnectedness between the objects. Therefore the concept lattice is applied to information retrieval system for improving the query, limiting the search space, recommending related documents and browsing the document collection especially. But browsing concept lattices becomes a problem as the number of clusters grows significantly with the number of objects and attributes. It's easy to produce edge crossover phenomenon when browsing concept lattice in the two-dimensional layout and cause visual confusion which leading to target information missing for users. In three dimensional layout the concept lattice also has to face huge amount of data, and the nodes makes the cross correlation with showing chaos, so that users get lost in the vast amounts of data.To solve above problems, the author puts forward to store data information using concept lattice for its advantage of expression in data correlation relations and visualize the information in tree structure for its advantage of clear hierarchy in visualization. When a user finds a determinate or vague target object and wants to look over more about the object, the author suggests that using a sub-context, generated by the object and comprised of a small amount of objects and attributes, to build a sub-lattice. The sub-lattice presents the relationship between the objects and it will help users locate the position of target information more precisely. The following researches are based on the Formal Concept Analysis(FCA) theory.(1) To improve the visualization algorithm of using tree structure instead of concept lattice, and put forward the multipath retrieval algorithm named Lattice-to-Tree. First of all, each object and attribute in the concept lattice maps to the tree node, rather than by using the methods of pruning and the reduction of object or attribute to handle the concept lattice structure; Secondly, to the edges that on behalf of the relationship between father concepts and son concepts in concept lattice, no longer do simple one-to-one mapping, but to compute the difference set of attribute sets between father concepts and son concepts, and set inclusion relation mutually for the attributes in the difference set. Then map the generated inclusion relation respectively to the relations between nodes and child nodes in the tree structure.(2) To make research into the sub-lattice generation algorithm based on an object or attribute, and put forward Sub-lattice Merge algorithm. Firstly, calculate each sub-context generated by each object and let the user set threshold of the objects number when displaying. Secondly, according to the given threshold and the object number of each sub-context, the objects in the concept lattice can be divided into no-merging object and merging object. When a user want to check out the relationship of objects, the no-merging object will build a sub-lattice based on its generated sub-context to display, and the merging object would display its sub-lattice through making a combination with the sub-lattice generated by the no-merging object.Finally, we apply the implementation of the two algorithms into a designed system of Music File Management to verify the accuracy and effectiveness of research results. At the same time, when apply the Lattice-to-Tree algorithm to browse objects, the effect of implementation are more suitable for users and in line with their habits. By displaying the lattice structure with correlative objects in the form of sub-lattice merging, not only makes it compact in structure, but also is helpful for users to find the relationship between objects.