大规模数据分析中离散优化问题的理论与算法研究

Logical Analysis of Data (LAD) has been used across numerous application domains because of its strong interpretability and comprehensibility. However, as the scale of datasets becomes larger, it becomes more and more difficult to use LAD. This is due to the key stage in LAD, i.e., pattern generation, which is a combinatorial optimization problem and can be formulated as a 0-1 multilinear program. At present, there are two main issues regarding the research on this model. First, existing linearization methods are not efficient when used to solve the model to global optimum. Second, there lacks research on approximation algorithms and effective metaheuristic algorithms. In order to apply LAD to large-scale datasets, we study pattern generation model with respect to the following two aspects. First, for theory and algorithms on global optimization of pattern generation model, based on polyhedral theory in integer programming, we utilize graph theory to analyze the structures existing in a dataset. Strong valid inequalities can be generated from these structures such that the resulting mixed-integer linear program has less linear constraints and tighter linear programming relaxation, which can boost up the performance of pattern generation. Second, toward the approximation theory and effective metaheuristic algorithms of pattern generation model, we first transform the 0-1 multilinear programming model into a well-studied problem. Then the approximability of the model is investigated and an approximation algorithm will be designed if it exists. Besides, we will come up with an efficient and effective metaheuristic algorithm for the pattern generation model.

逻辑数据分析方法因具有很强的可解释性与可理解性得到广泛应用。而随着数据规模的不断增大，使用该方法变得愈加困难。这缘于该方法的关键步骤，即模式生成。它是一个组合优化问题，可最终归结为一个0-1多重线性规划。目前针对该模型的研究存在两个问题：（1）旨在全局最优的线性化方法求解模型效率不高，（2）缺乏模型的近似算法和有效的元启发式算法研究。为将逻辑数据分析应用在大规模数据上，我们针对模式生成模型开展如下两方面研究：（1）模式生成模型全局最优化理论与算法，基于整数规划中多面体分析理论，以图论作为工具来分析数据间的结构，为模型生成强有效不等式，使得线性化之后的混合整数规划模型拥有更少的线性约束条件和更强的线性松弛，提升模式生成效率；（2）模式生成模型近似理论与元启发式算法，通过将0-1多重线性模型等价转化成研究较多的熟悉问题，探讨模式生成模型的可近似性和近似算法，并设计高效且有效的元启发式算法。

逻辑数据分析是一种监督学习方法，其最终的分类模型具有很强的可解释性和可理解性，这得益于其基本组成部分—模式。因此模式生成就成为了逻辑数据分析的至关重要的一步，对逻辑数据分析方法的研究也主要集中在这个方向。而对于模式生成的研究，目前主流研究集中在基于优化的方法。模式生成是一个NP难问题，可以用统一的优化模型来描述。本项目针对此模型研究如何更有效且高效地进行模式生成。主要研究内容有模式生成模型最优化理论与算法研究以及模式生成模型近似理论与元启发式算法。针对第一个研究，我们发现了三种强有效不等式，这些不等式不仅形式简单并且定义了模型的刻面，即能找到的最强的不等式，也就是说沿着这个方向的研究可以告一段落。进一步地，实验表明这一发现将生成同样模式的速度平均提高了约3倍。针对第二项研究，我们发现模式生成模型是不能被近似的，另外通过对启发式算法的研究，我们发现了逻辑数据分析在对多类数据进行特征选择时的同时节省时间和空间的高效算法。实验表明算法在空间占用上减少了5个数量级，即原来算法空间占用由GB级降低到了KB级。同时，算法在速度上提高了2倍以上。这些研究成果一方面提高了逻辑数据分析的效率，另一方面为分析更大规模的数据提供了可能。

内容获取失败，请点击重试