基于商逼近的粒计算优化问题研究

In granular computing, complex information generally is massive, heterogeneous and non-equilibrium distributed. When solving problem of this kind of information, one crucial issue is how to organize information reasonably and disentangle right information from falsehood to satisfy the target solving. For a specific target problem solving, approximation method can be obtained by using quotient space chain. Thus we can handle complex information, discover hidden knowledge, and reveal the inherent laws of things and events. However, under the background of big data, it is impracticable to construct a complete coarse-to-fine quotient space chain due to high complexity. So we must optimize the quotient space approximation..Related researches have shown that near-global-optimal approximation solution could be obtained when the problem’s target function is submodular. This study aims to obtain the solution of quotient space approximation by using submodular optimization function, analyze the problems which could be generated from the process of the quotient space problem solving, explore the error boundary of the problem solving process and give an efficient algorithm for the granulation of problem. Moreover, we will also analyze the error of the algorithm theoretically, and give a granulation selection criterion under a suitable given solution precision. Technically, submodular-based quotient approximation method and its corresponding error boundary will be discussed. Research results will be able to provide scientific support for the efficient utilization of big data.

面对海量、异构、非平衡分布且动态变化的复杂信息的问题求解，如何合理组织信息，去伪存真获取满足目标求解的信息，是粒计算必须解决的首要问题。通过商空间链，可得到特定目标求解的逼近方法，由此可完成处理复杂信息，发现隐含知识，揭示事物和事件内在规律的任务。但在数据规模增大的情况下，构建由粗到细完整的商空间链，以此确定满足目标的合适粒，复杂度太高，因此必须提升和优化商逼近。.相关研究表明，如果问题的目标函数具有子模性，可获得接近全局最优的近似解。本研究拟通过子模函数的优化方法求解商逼近的目标，分析商逼近过程中的相关问题，给出粒化近似的误差界，并提供易于改进、便于理解的高性能粒化算法。在理论上，完成逼近过程中算法误差的理论分析，解决商逼近合适粒层即满足问题求解精度的合适粒度这一关键问题；在技术上，给出基于子模优化的商逼近方法和对应的误差界。研究成果可为大数据的有效利用和挖掘提供科学支撑。

对海量、异构、非平衡分布且动态变化的复杂信息的问题求解，常用的粒计算方法是从特征提取、属性划分和精确建模的角度进行研究。利用信息的从粗到细的粒变换的商空间链，结合子模函数的优化理论，获取复杂信息的问题求解并给出商空间链的合适粒层、误差界和泛化能力分析还未见相关的讨论。本项目基于子模函数优化理论对基于商空间的问题求解展开研究。.（1）基于子模函数优化理论构建商空间链的理论研究。项目首先结合子模函数优化理论来构建商空间链，并对商逼近过程的逼近精度问题展开研究，证明了商空间可保持目标函数的子模性。.（2）基于子模函数优化理论构建商空间链问题求解的性能分析。研究项目研究证明，在商空间链目标函数具有子模性质的条件下，可利用简单的贪心策略构建最优商空间链，逼近过程中最大误差界为[1-(1-1/e)-1]。.（3）理论模型的应用研究。利用商空间链的多粒度问题求解的逼近能力。将其应用于若干实际问题的求解。首先针对复杂网络的多粒度结构特征，研究了多粒度社团结构的网络表示学习其及高阶表示方法。其次，对多粒度下用户影响力优化模型进行了研究，通过表示学习方法，挖掘用户交互行为中的显示信息和隐式信息，深入挖掘了用户偏好，促进了推荐精度的提升。对质量约束关系的服务组合优化问题，研究了基于任务粒化的质量约束感知服务组合优化方法。验证每种QoS聚合方式均具有子模态性质以及多属性服务组合问题的效用函数仍具有子模态性质，保证了基于任务粒化优化方法的完备性；通过质量约束建模，利用任务间的隶属度进行任务粒化实现原问题的有效分解，降低了问题求解规模。此外，项目还利用网络的多粒度表示与分析，研究了商逼近情况下的最大流分析问题、社团发现、链路预测问题。结合多粒度问题求解的思想，研究了低质数据的若干学习问题和生物医学数据处理中的若干问题。