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

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.

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

聚类线性回归问题(Clusterwise Linear Regression Problem)是数据挖掘领域的一个重要研究方向。它研究的主要问题是将一个拥有多种线性模式的数据集按照不同的模式聚类，并计算每一个聚类的线性回归函数。聚类线性回归问题的数学模型是一个目标函数高度非凸非光滑的非线性最优化问题。本项目的主要研究内容是设计求解聚类线性回归问题的全局最优化算法。研究内容主要分为两个部分：一是设计结合启发式算法和确定性算法的全局最优化算法，二是设计基于非光滑最优化理论的全局最优化算法。在本项目的资助下，目前项目团队已经开发出了一个求解目标函数为大规模非凸非光滑函数的全局最优化算法，并已经将该算法应用于股市指数预测。聚类线性回归问题在实际中有非常重要的应用。比如，在市场分割或市场细分问题中，商家需要根据搜集到的数据把顾客分为具有不同特点的消费群体，并找出各消费群体所遵循的一些规律；在证劵交易中，玩家们需要对之前的交易数据按某种相似性进行分类，并寻找出其中的规律，从而为自身的决策提供依据；在医疗诊断过程中，医生要把病人的检查数据和训练数据进行比对，从而诊断出患者所患疾病的具体类型。本项目的研究成果对促进聚类线性回归问题的实际应用具有很重要的科学意义。