.410 智能系统学报 第6卷 果，此类图能更自然地表达数据间的关系，且能从理 力，但其算法是应用在网络社区发现问题中的，在点 论上保证图的稀疏性，其缺点依然是构图的时间耗 集聚类问题上，尚需推广和验证， 费太大 4.3复杂性与扩充性问题 总的来看，尽管新的构图方法具有一些好的特 快速求解稀疏矩阵的特征值和特征向量的主要 性，但考虑到其时间耗费巨大，不及近邻图或者互 算法是Arnoldi或者Lanczos算法，其他快速方法几 为k近邻图经济实用.近来的一些理论研究已经着 乎都是它们的变体，关于特征空间求解方法的总结 眼于讨论k的界，即k大于多少时可以保证k近邻 可参看文献72]. 图的连通性.例如，针对包含足够多数据点的平面泊 以非归一化谱聚类为例，即求解Lx=入x,采用 松分布数据，Xue和Kumer6]证明了当k≥ Lanczos算法求解的时间复杂性分析如下，设图的总 5.1774×logn时k近邻图连通的概率为1.Balister 边数为m,考虑典型的稀疏矩阵（即满足m与节点 等人[]进一步证明了更紧的界，即当≥ 数n成线性关系)，特征方程左边需要O(m)次操 0.5139×logn时，k近邻图连通的概率为1，Brito等 作，右边需要O(n)次操作，共O(m+n)次操作.再 人[利用蒙特卡罗仿真得出了一些实证的参数，这 考虑上Lanczos算法的迭代次数O(n),求解一个二 些结果为参数k的选取提供了一定的依据， 分问题的时间约为O(n2).于是，重复二分谱聚类问 σ是高斯核参数，许多研究者都将其设为一个 题的时间复杂性约为O(n'log n),解决k路谱聚类 全局值31，其取值范围一般满足‖x-‖>σ> 问题约为O(m),空间复杂性为O(n2),只有采用 0,通过加入参数σ，将原始的相似关系映射到其他 优化方法存储稀疏矩阵，才能降低其空间复杂性和 空间.考虑到机器的计算精度，过小的σ会导致相 时间复杂性 似图不连通，然而，全局设定σ的值实际上在一些 些改进的谱算法试图更快速实现该类算法， 情况下并不是理想的方法.文献[19]探讨了自适应 如Fowlkes等人[]运用Nystrom近似方法避免计算 设定局部参数的方式，能够更加恰当地描述节点间 整个相似矩阵，Dhillon等人[741提出了一种不使用特 的邻域关系，其表达式如下： 征向量的方法，Yan等人[51基于局部K-means聚类 0g=exp(-‖x:-x‖2/(o0)). 或者随机投影树来快速近似谱聚类.这些方法虽然 式中：σ：取点i与其第K个邻近点之间的距离，σ 改善了扩充性问题，但是损失了精度，而且没有讨论 类似.K是一个独立的参数，从几何意义上讲，它是 空间复杂性方面的瓶颈问题然而不论采取何种特 嵌入空间的数据维数的函数，K的选取较σ更容易. 征求解方法，当面对大规模的数据集时，都可能会遭 该方法对于常用的人工数据（如环形嵌套的簇结 遇空间上的瓶颈。考虑最坏的情况，也即非稀疏矩 构、簇间密度不同的问题等)的处理效果较好. 阵，设数据规模n=10,采用邻接矩阵表示法或者 4.2簇数估计问题 拉氏矩阵表示法，由于每个浮点型实数需要占据 自动估计簇数的研究大体上可以分为2类.一种 4Byte,则大约需要占用40GB的存储空间. 方法是通过分析特征值.文献[3]分析了在理想状况 文献[24]提出了一种并行谱聚类算法，既考虑 下（簇与簇之间的距离为无穷远）的簇数估计方法：对 了存储空间的并行使用问题，也考虑到了并行分布 于归一化相似矩阵，特征值为1的个数严格地对应着 式计算的问题.他们首先将n个数据实例分配到p 簇数.然而实际的情况没有这么简单，一种可选的方 个机器节点上，然后用最小磁盘/0方法在每个机 法是分析特征值缺口(eigen-gap)m,在部分应用中， 器节点上计算本地数据实例与所有数据实例之间的 此方法是有效的，但是其缺乏理论根据，而且缺口往 相似度.这2步与分布式特征求解和分布式参数调 往可大可小，难以取舍.文献[71]提出将相似矩阵的 整结合起来，大大加速了聚类速度，其快速求解的算 特征值大于1的个数作为簇数的方法，实质上就是一 法采用的是较流行的ARPACK及其并行版本PAR 种特征值缺口法.另一种更好的方法是分析特征向 PACK6].通过十万数量级上的文本分类和图像分 量，如文献[19]通过引入旋转矩阵和一个优化目标来 类的实证研究，表明了提出的算法有效地改善了谱 发现最佳簇数.实验表明，该方法在一些复杂的合成 聚类算法难以扩充到大规模数据集的问题。可见，若 数据集和图像分割应用上是有效的 要解决大规模数量级的谱聚类问题，需要借助于并 值得注意的是，以上这些方法要么是基于谱来 行算法。 估计簇数，要么是基于新的优化目标来估计簇数.而 4.4半监督谱学习 直接基于图割优化目标来确定簇数的研究尚少.虽 通常，与分类问题本身无关的特征会使得大多 然Newman[]提出的重复二分谱算法具有这种能 数的谱聚类算法的性能大打折扣.几乎所有谱聚类