陶汉　李星

摘要：在這个大数据时代，我们时常与数据打着交道。通常我们可以用一个向量来表示一个数据样本，数据的维度就是向量的维度。比如我们常见的二维数据、三维数据可以直观地可视化。有的数据维度非常高，比如描述人脸、声音等的数据样本它们的维度就通常高达上百。通过简单的欧式聚类来进行数据样本的分类，在低纬度数据样本中大多有良好的分类结果。但是在高维数据的分类问题中，基于欧式距离的分类方法通常都会失效。所以针对高纬度数据的分类提出一种简单有效的方法是具有一定意义的。该文的创新点在于：针对不同维度数据的子空间分类以及多流形分类问题， 该文提出了“种子生长模型”较好地解决了该问题。 该模型在通过模拟种子的非线性传播与生长的同时，加以生长规则的限制， 使得与种子具有较高相似性的样本被不断地归类，其他的样本点逐渐成为新的 种子，种子再不断更新与生长，最终完成分类。该模型具有较强的一般性与适 应性，能够较好地解决不同维度样本的子空间分类与多流形分类问题。

关键词：数据分类；高维数据；生长算法

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2017）05-0005-02

1 研究背景

数据的分析和处理方法成为了诸多问题成功解决的关键。高纬度的数据分类不能简单地用基于欧式距离分类。常见的方法已经有的是谱聚类方法、各种基于流型学习的方法，它们大多对于高纬度的数据分类有着较好的结果。本文从数据样本中数据本身的相似性出发，从“区域生长算法”中得到启发，提出一种“种子生长算法”来实现高纬度数据样本的分类。传统的生长算法的思路大致是以下几步：

1）初始化开始，找到第1个还没有归属的像素， 并且设该像素为（x0， y0）；

2）迭代开始，以（x0， y0）为中心， 考虑（x0， y0）的8邻域像素（x， y）如果（x0， y0）满足生长准则， 将（x， y）与（x0， y0）合并（在同一区域内）， 同时将（x， y）压入堆栈；

3）从堆栈中取出一个像素，把它当做（x0， y0）返回到步骤2；

4）当堆栈为空时！返回到步骤1；

5）重复步骤1-4直到图像中的每个点都有归属时。生长结束。

传统生长算法的规则主要关键是种子的选取和相似度判定准则的设计，其中种子可以人工随机选取也可以通过一些具体问题具体分析的方法来选取，相似度主要是灰度值或者其他打分函数，同时阈值的选取也会影响最终分类的结果，所以说最后还有一个调参的过程。

数据与方法：

本算法的基本思路是在数据集中，选出起始点，从该点开始模拟种子生长过程。算法不断地将相似点归为一类，最终完成所有的数据点分类。下图是算法概要：

在初始化阶段，本算法第一步是选取一个边缘点作为初始点（称为种子点S0），其余的点是未分类点集合。在未分类点中，选出一个最近的点作为初始的下一个种子候选点Sc。S0与Sc构成的向量称为中心向量。这是初始步骤。最为关键的是迭代步骤，对于当前的种子点来说，点分为已分类、未分类、已淘汰。只要一个新的未分类点纳入已分类中，当前就会形成一个种子向量，即由新分类点与新的种子点形成的向量。该算法的核心内容就是比较种子向量与中心向量的相似度来判定候选点是否应该分类。根据具体问题具体分析，本文的相似度评价指标采取了向量夹角、向量距离或者法向量，如图所示。等到迭代结束之后，所有点的状态分为已分类、已淘汰时，迭代结束。意味着所有已分类点与初始的种子点被分为一类。特别注意的是，此处应选取边缘点作为初始种子，以控制种子生长方向，使得种子能够在 该流形上有规律地生长。最后不断进行迭代，直到完成所有的分类点。图2是算法的流程：

本文将该算法运用到了三维立体数据、多维人脸数据中。实验结果表明，该算法简单有效，有着良好的分类结果。

2 实验结果

下图分别是三维立体数据与多维人脸数据的分类结果：

如图所示，本算法对一个三维的立体梯台进行了准确地分类。通过运用上述的算法，成功地将梯台的上顶、下顶、区别进行分类。在验证的过程中，我们也使用了二维直线、二维曲线的数据集。最终结果都表明有良好的分类结果。

人脸数据的每一个样本是描述像素的高维数据，它不能直接显示在三维坐标轴中。同样运用上诉算法，采用了中心向量与种子向量法向量的考量标准，分类结果准确。

3 结论与展望

针对高维数据分类问题，本文提出了一种简单有效的算法，通过给定样本集U的不同特点，修改种子生长规则以及调整模型参数，增强模型对数据的适应性，对大部分问题，均得到了较好的分类结果。总的来说该模型具有优点：1）能适应低维度数据和高维度数据；2）能适应不同密度的样本数据；3）对某些问题如人脸识别，轨迹特征有较好效果 待改进之处：1）不能解决过于复杂的数据集；2）后处理过程可以再更为优化。

参考文献：

[1] 刘向阳.多流形数据建模及其应用[D].上海：上海交通大学，2011.

[2] 谈超.增量流形学习方法研究[D].上海：同济大学，2014.

[3] 申中华，潘永惠，王士同.有监督的局部保留投影降维算法， 2008，21（2）：233-234.

[4] Liu G， Lin Z， Yan S， et al. Robust recovery of subspace structures by low-rank representation. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2013， 35（1）：171–184.

[5] Elhamifar E， Vidal R. Sparse subspace clustering： Algorithm， theory， and applications. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2013，35（11）：2765–2781.

[6] Wang Y， Jiang Y， Zhou Z. Spectral clustering on multiple manifolds. IEEE Transactions on Neural Networks， 22（7）：1149–1161， 2011.

[7] Cheng B， Liu G， Wang J， et al. Multi-task low rank affinity pursuit for image segmentation， ICCV， 2011.