基于变分原理的数据聚类模型的数学理论与计算方法

The proposed research focus on variational principle based methods for data clustering, with both theory and algorithm development involved. Existing data clustering methods are mostly developed from statistical models. The proposed research adopt graph-based models, which models the data set as an undirected weighted graph, with each vertex represent a data, and the weight for each edge characterizes the affinity between the pair of data. We compare the data-clustering problem with the well-studied image segmentation models. We draw connection between these two topics, by defining similar energy functionals on the graph as those defined on images for image segmentation. We look for the continuous version of the energy functionals, and solve the optimization algorithms under continuous setting, with both numerical optimization and partial differential equation techniques. Another important aspect of this research is the modeling of data clustering with graph cut, and using non-local operators that appear in partial differential equations to find continuous version of the energy functional for graph cut.

本研究项目着眼于基于变分原理的数据聚类模型的数学理论与计算方法。数据聚类在计算机科学中被广泛研究，产生了许多基于统计模型的方法。而本研究基于图表示的聚类算法，将整个数据集抽象成一个无向有权图（un-directed weighted graph），每个高维数据视为图的顶点，数据点之间的相似度由边的权重刻画。数据聚类问题转化为图论中的关于图分割（graph cut）的问题。通过将图分割问题同图像处理中的分割问题类比，我们研究定义图上的能量泛函，通过将离散的问题连续化，利用连续优化方法和偏微分方程数值解方法求解能量泛函的最优化问题，从而解决图分割问题。本研究还将从建模角度讨论如何将数据聚类问题转化为合适的图分割问题，以及利用偏微分方程非局部算子将图上的运算以恰当方式连续化。

我们利用图上定义的非局部的梯度算子，将非局部全变差作为正则项和数据驱动的区域拟合项（region force）引入Potts模型，通过极小化该能量泛函求解数据聚类问题。我们构造数据和概率模型驱动的region force项，并在迭代算法中提取出分类结果中高“置信度”的点作为先验信息加入到region force项中，从而提高了结果的稳定性。受到偏微分方程数值解的快速算法启发，我们在图网络分割和图像分割中设计基于多重网格和区域分解的快速算法。本项研究利用连续变量的能量泛函研究图上的聚类模型，具有与许多现有的研究思路不同的特点。首先，在构造能量泛函时不再局限于离散数学的方法，而借鉴直观上相近的物理模型和统计方法。其次，我们在研究图网络半监督聚类问题上首次利用“两步法”从初步分类的结果中筛选出高置信度的分类点，作为新的训练数据加入到模型中，从而得到“小样本学习”的效果。第三，我们提出的最小化能量泛函问题是典型的最优化问题在偏微分方程数值解中有着大量快速并行算法，但是尚未在图上的模型中见到。我们利用所提出的全变分模型的特点，将多重网格和区域分解这两种求解偏微分方程的算法用于图网络和图像处理问题。