非光滑聚类线性回归问题的全局算法

Clusterwise linear regression is an important subject of data mining, its core problem is to cluster a data set with multiple patterns and find a linear regression function for each cluster. The scale of clusterwise linear regression problem is generally huge because of the massive amount of points in the data set; thus, the key issue of solving clusterwise linear regression problem is to reduce the scale of problem and computational cost. This project focus on the application of nonsmooth optimization theories and algorithms on clusterwise linear regression. In order to reduce the scale of the problem, we separate the clusterwise linear regression problem into incremental phases whose number of clusters increase gradually and present a nonsmooth nonconvex optimization model for each pahse. In order to globally solve the nonsmooth nonconvex optimization problems presented in each phase, we develop a hybrid method which combines metaheuristic strategies and deterministic methods. This project will finally present a hybrid global optimization method for clusterwise linear regression problems and we will apply this method to some test and pratical data sets collected from medicine, industry, economy, and so on.

聚类线性回归问题是数据挖掘的一个重要研究方向，其研究的主要问题是把一个具有多种模式的复杂数据集聚类，并找到每一个聚类的线性回归函数。数据集中大量的数据点使得聚类线性回归问题的规模非常庞大；因此，求解聚类线性回归问题的关键是如何降低问题的规模和计算量。本项目主要研究如何运用非凸非光滑全局最优化的理论和算法来解决聚类线性回归问题。为了减小问题的规模，我们把原聚类线性回归问题分解为一系列聚类数不断增加的不同阶段，并给出每一个阶段的非凸非光滑优化模型。我们运用求解全局最优化问题的混合算法来计算此非凸非光滑优化问题的全局最优解，混合算法是由启发式策略和确定性算法结合设计而成。本项目最终会设计出求解聚类线性回归问题全局最优解的混合算法，并将算法运用到一些测试数据集和在医学、证劵、经济等领域产生的数据集中。