国内外关于场景分割的方法多以聚类分析为主，而聚类分析是机器学习的经典问题[1]。聚类可以分为无监督聚类和半监督聚类，无监督聚类是通过抽取数据中的“潜在”结构，将相似数据组成类或类的层次结构，不需要任何先验和假设， 在现有的无监督聚类算法中， K-均值聚类[1]作为一种基于中心的聚类算法，是最简单、使用最普遍的方法之一。它在紧凑的超球形分布的数据集上有很好的性能，然而当数据结构是非凸的，或数据点彼此交叠严重时， K-均值算法往往会失效，而且算法利用迭代最优化方法寻找最优解，因而不能保证收敛到全局最优解。60144

近期出现的一种无监督聚类算法——谱聚类[2~8]克服了K-均值算法的缺点，具有识别非凸分布聚类的能力，适合于求解实际问题，而且实现简单，不会陷入局部最优解，且能避免数据的过高维数所造成的奇异性问题。谱聚类算法已经成功地应用于语音识别、视频分割、图像分割、文本挖掘等领域，表现出极大的潜力。

谱聚类的思想来源于谱图的划分，它将数据聚类问题看成是一个无向图的多路划分问题。然后定义一个划分依据,最优化这一判断，使得同一类内的点具有较高的相似性，不相同类之间的点具有较低的相似性。由于图划分判据的最优解是个NP难的问题，一个有效的求解方法就是考虑问题的连续放松形式[3]，将相似性图表示为一个矩阵，矩阵的特征值和特征向量提供了关于数据结构的全局信息，这样可以将原问题转换为求解矩阵的特征值和特征向量的问题，这类算法统称为谱聚类算法。

在图像分割中，图像中的某个点和其周围邻域中的点具有相同类别属性的概率较大。论文网 这一特性称为图像的空间一致特性，以往K均值、FCM等聚类算法采用的是Bag of Features的思想，没有利用图像像素点在空间上的依赖关系。近来，基于空间一致特性的图像分割越来越受到关注[7,9,10] 。 Dhillon证明了谱聚类和权核K均值的等价性问题[11]，从这种等价性出发，对于图像中某点的邻域像素施加某种空间约束，提出了一种基于空间约束机制的谱聚类算法用于图像分割，取得了较好的分割效果。

随着激光雷达越来越广泛地应用于机器人领域，点云数据的理解问题变得越来越重要。提供空间数据聚类方法把点云数据分割成有意义的独立子集是点云数据理解中比较关键的一步。空间点云聚类问题可以定义为：给出一个空间点集，寻找一个划分规则，将该空间点集划分为一些子集，使每个子集中的点在划分规则下相似。

针对任意数据集，常用的聚类方法有：基于划分的方法，如k-means算法、k-medoid算法[12]、X-means算法[13]等；基于层次的方法，如BIRCH算法[14]、CURE算法[15]等；基于密度的方法；基于网格的方法，如Optigrid算法[16]；基于模型的方法，如COBWEB算法[17]；基于点云密度变化以及空间分布特征的聚类算法[18]。其中，有些聚类算法是在一定的限定条件下对时间进行聚类的，例如k-means算法需要预先设定类别个数等。针对2维图像聚类问题提出了一些算法，但是这些算法都不完全适用于3维空间数据集。基于以上原因，需要针对雷达获取的点云数据在智能机器人领域的应用特点设计适用的聚类算法。