基于子模函数优化的知识约简研究

Traditional knowledge reduction methods focus on the approximation of concepts and classification. As data environment changing, researchers pay more attention to the computing problems of knowledge reduction. Knowledge reduction is essentially an optimization problem of sparse attribute space. Investigating knowledge reduction from the view of optimization facilitates implementing high-performance reduction algorithms for modern data applications. However, because the objective functions of knowledge reduction are generally non-convex and discrete, it is difficult to solve the reduction problem through directly applying optimization method. It is interesting that if the reduction objective function is submodular, we can optimize the reduction objective efficiently and obtain accurate results. This project expects to remodel and investigate knowledge reduction process from the perspective of submodular function optimization. The research issues involve the following aspects: analyzing the submodularity of reduction objective functions, improving and designing the reduction algorithms based on submodular optimization theory and the implementation of optimization-based reduction algorithms. The research work targets at the computing problems of knowledge reduction and thus provides theoretical foundation and solutions for the application of knowledge reduction in challenging data environments. Besides solving the computing problems of reduction, this investigation will also enrich the theory of submodular optimization and expand its application in the field of symbolic machine learning.

经典知识约简方法关注概念或分类的近似表示，随着数据环境的改变，知识约简的计算问题开始引发关注。知识约简本质上是属性空间的稀疏优化问题，从优化角度研究知识约简有助于设计实现高性能约简算法并促进其数据应用。然而由于约简目标函数的非凸、离散性，通过优化方法直接对约简目标求解是非常困难的。如果约简目标函数具有子模性质，就可以通过便捷的优化方法求解约简目标并获得较高精度的结果。项目将从子模函数优化角度对知识约简问题重新建模并进行系统研究，研究内容包括约简目标函数子模性质分析，基于子模函数优化理论的约简算法改进与设计，优化约简算法的数据应用等方面。研究议题与知识约简在现代数据挖掘中面临的关键计算问题相对应，由此从优化角度为复杂数据环境下应用知识约简提供了理论支持和解决方案。从子模优化角度重新审视知识约简，不仅有助于解决知识约简计算问题，并且可以丰富子模优化理论并拓展其在符号机器学习领域中的应用。

项目的研究目的在于从子模函数优化角度对知识约简问题进行系统研究。研究内容包括约简目标函数的子模性质分析，基于子模函数优化理论的约简算法改进与设计，优化约简算法的数据应用等方面。项目的既定研究目标已经完成，主要研究进展包括：对经典粗糙集模型与邻域粗糙集模型表示的多种知识约简算法的约简目标函数进行形式化建模，并论证分析其子模性质；依据子模优化理论对传统多种知识约简算法进行改进和效率优化，基于邻域粗糙集模型与经典粗糙集模型提出了多种高效串行、并行约简算法；将优化约简算法应用于数据挖掘与图像分析领域，实现大规模决策规则提取与影像语义特征提取。项目从非凸、离散函数优化角度研究知识约简问题，有助于解决知识约简方法面对复杂数据应用时的计算局限难题。研究成果可应用于大规模、复杂类型数据分析，从优化角度为复杂数据环境下的知识约简应用提供理论支持。