正在加载图片...
.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[]提出的重复二分谱算法具有这种能 数的谱聚类算法的性能大打折扣.几乎所有谱聚类
<<向上翻页向下翻页>>
©2008-现在 cucdc.com 高等教育资讯网 版权所有