数据聚类问题中的一类张量优化方法研究

The task of data clustering is to divide items into meaningful or useful groups according to the features of the corresponding data. It is useful in data mining and data processing, and it provides a powerful tool for the study of biomedical science, meteorology, image processing and so on..The project aims to establish a class of hypergraph related tensor optimization methods for unsupervised and semi-supervised clustering problems. The main contents of our study are as follows: (1) With the aid of relaxation techniques, such as Lagrangian relaxation, linear programming relaxation and so on, we establish continuous tensor optimization models for the clustering problems and study the theoretical properties of the new models. (2) By employing the tensor structure and the cutting edge achievements of the relative optimization problems, we propose efficient optimization algorithms for the new models, and analyze the theoretical properties and numerical performances of the algorithms. (3) The new tensor optimization models and algorithms are applied to image processing problems. On the basis of the features of real life problems, we improve the new optimization models and algorithms. Finally, we produce application software for image processing problems.

数据聚类的任务是根据数据特征将事物划分成有意义或有用的簇(组)。它是数据挖掘和数据分析的重要手段，为生物医学、气象科学、图像处理等领域的研究提供了强有力的工具。. 本项目旨在给出一类基于超图的张量优化方法，以求解无监督聚类问题和半监督聚类问题。项目的主要研究内容是：(1)通过拉格朗日松弛、线性规划松弛等技术建立求解这两类问题的连续张量优化模型，并研究它们的理论性质；(2)结合张量的结构特征和相关优化问题的最新研究成果，建立新模型的高效优化算法，并对算法进行理论分析和数值分析；(3)用新的张量优化模型和算法研究图像处理问题。根据实际问题的特点完善模型和算法，最终形成面向应用的软件。

数据聚类研究的是如何根据事物之间的相似度和内在联系对事物进行分类。它是进行数据处理的重要手段，在机器学习、计算机视觉、图像处理、信息论以及控制等领域都有重要应用。. 本项目主要研究无监督聚类和部分事物带有标签的半监督聚类两类问题。我们主要研究工作如下: (1) 我们定义了超图的Laplacian张量，并借助该Laplacian张量给出了 无监督聚类问题的分割费用函数，建立正交约束优化模型。根据正交约束优化算法的研究成果，给出求解该模型的算法和算法的理论分析。同时，我们说明了超图的连通度和该Laplacian张量特征值之间的联系。数值实验表明，该方法能有效地求解图像分割、运动分割等图像处理中的问题。 (2)在无监督聚类研究的基础上，我们通过添加合适的正则项的方式，给出了半监督聚类问题的张量优化模型，并提出了Stiefel流形上的梯度投影算法进行求解。理论分析证明了算法的收敛性。进一步，我们将该方法用于求解图像处理中的分类问题。通过数值实验结果对比说明利用标签信息的半监督聚类方法比无监督聚类方法的聚类准确率更高。 (3) 超图的聚类问题与超图对应的张量特征值和特征向量密切相关。我们给出了超图相关张量的乘法运算的快速高效算法，并分别提出了基于信赖域方法和三次正则方法的求解算法，给出了两种算法的收敛性分析，通过数值实验说明了两种算法的特色和优势。另外，我们对利用Lanczos方法求解三次正则子模型的算法复杂度进行了理论分析，给出了Lanczos方法求得的最优值与原子问题的最优值之间的误差界。