基于拟阵思想的概念格建造和约简之研究

This project researches the construction and reduction on concept lattice with the idea of matroid theory. The main content is as follows: ①A transversal matroid is produced with the assistance of the relationships between all the common attributes for an object subset and the attribute subset owned by every object in the above object subset. Using the relationships between the transversal matroid and object subsets, the classification properties of transversals, all the intents and the hierarchical order among them will be obtained. ②Relative to a concept lattice, there is a map from attribute set to object set. According to the complement map and the dual map of the above map with the relationships between the concept lattice of original context and the complement concept latttice, and dual concept lattice, we discover all the extents and the hierarchical order among the extents. ③Considering the matrix representation of a context and the incidence matrix of a matroid with matrix theory and geometry theory, we attain all the concepts and the hierarchical order among them. ④Similarly to ①, it follws a transversal matroid. Utilizing some geometric properties of characteristic sets relative to this matroid, and the relationships between rough set and this matroid, we may find out the characterizations of all the removable atttributes. ⑤A partition matroid is explored with vector properties of attribute set in 0-1 context. Applying the characteristic sets of this matroid, some properties of vector spaces, and the relationships between rough set and matrix, we reveal the characteristics of all the removalble attributes. This project presents new thoughts and approaches to the construction and reduction of concept lattice. All the results are necessary and important to the study and application for searching out the relationships and clustering among data.

引入拟阵论的思想和方法，研究概念格的建造和约简。主要内容如下：①通过对象子集共有属性与该子集中每个对象拥有属性之间的关系，得到一个横贯拟阵。利用该拟阵与对象子集的关系，以及横贯所具有的分类性质，得到所有内涵及其层次关系。②利用与概念格有关的属性集到对象集上的映射之补映射、对偶映射，以及原形式背景的概念格与其补概念格、对偶概念格之间的联系，得到全体外延和层次关系。③通过形式背景的矩阵表示与拟阵的关联矩阵，利用矩阵及其几何特性，得到概念的全体及其层次关系。④类似①得到一个横贯拟阵，利用此拟阵的特征集族的几何性质、与粗糙集的关系，发现可删除属性的特征。⑤通过属性集在0-1背景中的向量性质，建立剖分拟阵，利用该拟阵的特征族、向量空间的性质、粗糙集与矩阵的关系，找到可删除属性的特征。本项目为概念格的建造和约简提供新的理论与方法，在用概念格发现数据的关系和聚类的理论研究与应用方面都具有重要意义。

概念格的建造和约简已被证实是NP问题，所以寻找新的研究方法是概念格理论发展必经之路。本项目利用拟阵论在贪婪算法中的优势地位，将拟阵论融入到概念格理论研究中，主要进行以下研究并得到相应结果。①对于经典拟阵的拓广形式—区间广义拟阵，直接给出其相应的贪婪算法的具体表述。为挖掘更多概念格理论中的算法，将贪婪算法在更为广泛的领域—偏序集理论中进行研究，得到用偏序集构建拟阵的方法。除贪婪算法之外，还研究组合优化其他算法，为概念格知识提取方法上奠定了基础。②建立了一些新的“广义”拟阵结构，为拟阵论用于概念格知识提取提供更多操作平台。对于经典形式背景，研究简单拟阵与概念格之间的对应关系，得到用拟阵建造相应的概念格，以及用概念格构造拟阵的方法。③因为概念格是完备格，在同构意义下几何格决定简单拟阵，而几何格由其原子族决定，因此研究了几何格与原子完备格和分类格之间的关系，并解决2002年的一个公开问题。研究拟阵与图、贪婪算法的关系，得到用图论获得经典形式背景上属性约简的算法。在模糊形式背景中，利用有向图得到属性约简的可行和有效算法；用加权图寻找到所有经典-模糊概念的算法。还研究三支决策在概念格建造中的应用，得到三支概念与经典概念之间的关系，以及区间中智模糊概念格的知识提取算法。④研究如何将得到的理论成果应用到生物信息的提取中，得到了生物聚类和分类的提取方法。此应用说明理论成果的正确性和实用性。所有成果丰富了概念格理论，促进了拟阵论的发展，对社会进步具有推进作用。