http:sina//blog.sina.co...

来源：蜘蛛抓取(WebSpider) 时间：2011-09-16 18:50 标签： 新浪博客


 其实并不是为用而用而是不得鈈用。  目前在研究领域碰到的很多基础问题都是NP-hard的找一个比较好的近似演算法要费很大的精力；就算找到多项式的近似方法，也会出现實际使用上仍然太慢/解陷入局部极小等问题

 比如说用K-means聚类，建模本身已经够简单了但它是NP-hard的，用传统的EM迭代作近似解会陷入局部极小

 反之，SVD理论上只有唯一解演算法速度相对又快，并且有大量理论结果及周边性质支持可以算是一个很理想地能将NP-hard问题“靠”上去的模型；它的另一个好处是，作为带约束二次规划的一种特殊情况它对运算式为二次的目标函数的“相容性”比较好，“靠”所要求的数學技巧不高任何人，任何方向都能拿来试试

Spectral Clustering，中文通常称为“谱聚类”由于使用的矩阵的细微差别，谱聚类实际上可以说是一“类”算法

2）由于抓住了主要矛盾，忽略了次要的东西因此比传统的聚类算法更加健壮一些，对于不规则的误差数据不是那么敏感而且 performance 吔要好一些。许多实验都证明了这一点事实上，在各种现代聚类算法的比较中K-means 通常都是作为 baseline 而存在的。

3）计算复杂度比 K-means 要小特别是茬像文本数据或者平凡的图像数据这样维度非常高的数据上运行的时候。

1）根据数据构造一个 Graph Graph 的每一个节点对应一个数据点，将相似的點连接起来并且边的权重用于表示数据之间的相似度。把这个 Graph 用邻接矩阵的形式表示出来记为 W 。

2)把每一列元素加起来得到N 个数把它們放在对角线上（其他地方都是零），组成一个N*N的矩阵记为D 。并令L = D - W

3)求出L的前k个特征值（在本文中，除非特殊说明否则“前k个”指按照特征值的大小从小到大的顺序）以及对应的特征向量。

4)把这k个特征（列）向量排列在一起组成一个N*k的矩阵将其中每一行看作k维空间中嘚一个向量，并使用 K-means 算法进行聚类聚类的结果中每一行所属的类别就是原来 Graph 中的节点亦即最初的N个数据点分别所属的类别。

1）只需要数據的相似度矩阵就可以了这个是显然的，因为 Spectral Clustering 所需要的所有信息都包含在W中不过一般W并不总是等于最初的相似度矩阵——回忆一下， 昰我们构造出来的 Graph 的邻接矩阵表示通常我们在构造 Graph 的时候为了方便进行聚类，更加强到“局部”的连通性亦即主要考虑把相似的点连接在一起，比如我们设置一个阈值，如果两个点的相似度小于这个阈值就把他们看作是不连接的。另一种构造 Graph 的方法是将 n 个与节点最楿似的点与其连接起来

2)抓住了主要矛盾，忽略了次要的东西Performance 比传统的 K-means 要好。实际上 Spectral Clustering 是在用特征向量的元素来表示原来的数据并在这種“更好的表示形式”上进行 K-means 。

3)计算复杂度比 K-means 要小这个在高维数据上表现尤为明显。例如文本数据通常排列起来是维度非常高（比如，几千或者几万）的稀疏矩阵对稀疏矩阵求特征值和特征向量有很高效的办法，得到的结果是一些 k 维的向量（通常 k 不会很大）在这些低维的数据上做 K-means 运算量非常小。但是对于原始数据直接做 K-means 的话虽然最初的数据是稀疏矩阵，但是 K-means 中有一个求 Centroid 的运算就是求一个平均值：许多稀疏的向量的平均值求出来并不一定还是稀疏向量，事实上在文本数据里，很多情况下求出来的 Centroid 向量是非常稠密这时再计算向量之间的距离的时候，运算量就变得非常大直接导致普通的 K-means 巨慢无比，而 Spectral Clustering 等工序更多的算法则迅速得多的结果


 为什么先做降维再做K-means，效果会更好呢
 另外，有趣的是K-means可以用PCA来做近似解  K-means是说找到K个点，使得所有点到这K个点的距离平方和最小；
 而SVD是说找到一个子空间使嘚所有点到这个子空间的距离平方和最小。  于是这两者就建立了联系K-means便relax到SVD上去了。

    谱聚类(Spectral Clustering, SC)是一种基于图论的聚类方法——将带权无向图劃分为两个或两个以上的最优子图使子图内部尽量相似，而子图间距离尽量距离较远以达到常见的聚类的目的。其中的最优是指最优目标函数不同可以是割边最小分割——如图1的Smallest cut(如后文的Min cut)， 也可以是分割规模差不多且割边最小的分割——如图1的Best cut(如后文的Normalized cut)

    这样，谱聚類能够识别任意形状的样本空间且收敛于全局最优解其基本思想是利用样本数据的相似矩阵(拉普拉斯矩阵)进行特征分解后得到的特征向量进行聚类。

    如果要将item做聚类常常想到k-means聚类方法，复杂度为o(tknm)t为迭代次数，k为类的个数、n为item个数、m为空间向量特征数：

    如果我们计算出item與item之间的相似度便可以得到一个只有item的相似矩阵，进一步将item看成了Graph(G)中Vertex(V)，歌曲之间的相似度看成G中的Edge(E)这样便得到我们常见的图的概念。

邻接矩阵：Eeij表示vi和vi的边的权值，E为对称矩阵对角线上元素为0，如图2-2

1.2 特征值与L矩阵

    先考虑一种最优化图像分割方法，以二分为例將图cut为S和T两部分，等价于如下损失函数cut(S, T)如公式1所示，即最小(砍掉的边的加权和)

    假设二分成两类，S和T用q(如公式2所示)表示分类情况，且q滿足公式3的关系用于类标识。

    其中D为对角矩阵行或列元素的和，L为拉普拉斯矩阵

1、 L为对称半正定矩阵，保证所有特征值都大于等于0；

2、 L矩阵有唯一的0特征值其对应的特征向量为1。

    离散求解q很困难如果将问题松弛化为连续实数值，由瑞利熵的性质知其二将你型的最尛值就是L的特征值们(最小值第二小值，......最大值分别对应矩阵L的最小特征值，第二小特征值......，最大特征值且极值q相应的特征向量处取得，请参见瑞利熵(Rayleigh quotient))

写到此，不得不对数学家们致敬将cut(S,T)，巧妙地转换成拉普拉斯矩阵特征值(向量)的问题将离散的聚类问题，松弛为連续的特征向量最小的系列特征向量对应着图最优的系列划分方法。剩下的仅是将松弛化的问题再离散化即将特征向量再划分开，便鈳以得到相应的类别如将图3中的最小特征向量，按正负划分便得类{A,B,C}和类{D,E,F,G}。在K分类时常将前K个特征向量，采用kmeans分类

    2、k与聚类个数并非要求相同，可从第4节的相关物理意义中意会；

    3、在前k个特征向量中第一列值完全相同(迭代算法计算特征向量时，值极其相近)kmeans时可以刪除，同时也可以通过这一列来简易判断求解特征值(向量)方法是否正确常常问题在于邻接矩阵不对称。

图3 图的L矩阵的特征值与特征向量

    茬kmeans等其它聚类方法中很难刻划类的大小关系，局部最优解也是无法回避的漏病当然这与kmeans的广泛使用相斥——原理简单。

    计算方法可矗接由计算L的最小特征值(特征向量)，求解

    Normarlized cut，目标是同时考虑最小化cut边和划分平衡以免像图1中的cut出一个单独的H。衡量子图大小的标准是：子图各个端点的Degree之和

PS：这也是常常在人们的博客中，A说谱聚类为求最大K特征值(向量)B说谱聚类为求最小K个特征值(向量的原因)。

第一步：数据准备生成图的邻接矩阵；

第二步：归一化普拉斯矩阵；

第三步：生成最小的k个特征值和对应的特征向量；

第四步：将特征向量kmeans聚類(少量的特征向量)；

    可见不管是L、L’都与E联系特别大。如果将E看成一个高维向量空间也能在一定程度上反映item之间的关系。将E直接kmeans聚类嘚到的结果也能反映V的聚类特性，而谱聚类的引入L和L’是使得G的分割具有物理意义

    上述对将E当成向量空间矩阵，直观地看符合我们的认知但缺乏理论基础；而L(L’等)的引入，如第2节所述使得计算具有理论基础，其前k个特征向量也等价于对L(L’等)的降维。

    因而聚类就是为圖的划分找了理论基础能达到降维的目的。

    在前面的博文中已经详述是一种基于图论的聚类方法，简单形象且理论基础充分在社交網络中广泛应用。本文将讲述进一步扩展其应用场景:首先是User-Item协同聚类即spectral coclustering，之后再详述谱聚类的进一步优化

    在数据分析中，聚类是最常見的一种方法对于一般的聚类算法(kmeans, spectral clustering, gmm等等)，聚类结果都类似图1所示能挖掘出数据之间的类簇规律。

即使对于常见的数据User-Item评分矩阵(常见于各社交平台的数据之中例如音乐网站的用户-歌曲评分矩阵，新闻网站的用户-新闻评分矩阵电影网站的用户-电影评分矩阵等等)，如表1所礻在聚类分析中，也常常将数据计算成User-User的相似度关系或Item-Item的相似度关系计算方法诸如应用Jaccard距离，将User或Item分别当成Item或User的特征再在此基础上計算欧氏距离、cos距离等等。

    但是如果能聚类成如图2中的coclustering关系将User和Item同时聚类，将使得数据结果更具意义即在音乐网站中的用户和歌曲coclustering结果表明，某些用户大都喜欢某类歌曲同时这类歌曲也大都只被这群用户喜欢着。这样不管是用于何种场景(例如歌曲推荐)，都将带来极夶的益处

对于A的二部图，只存在Item与User之间的邻接边在Item(User)之间不存在邻接边。再用谱聚类原理——将带权无向图划分为两个或两个以上的最優子图使子图内部尽量相似，而子图间距离尽量距离较远这样的聚类结果将Cut尽量少的边，分割出User和Item的类如果类记Ci(U,I)为第i个由特定的User和Item組成的类，由谱聚类原理Cut掉的Ci边为中的User或Item与其它类Cj(j≠i)的边，且其满足某种最优Cut方法简单地说，Cut掉的User到其它类Cj(j≠i)的Item的边可理解为这些User與其它Item相似关系较小；同样Cut掉的Item到其它类Cj(j≠i)的User的边，可理解为这些Item与其它User相似关系较小这正好满足coclusering的定义。

2 谱聚类的半监督学习

    假设有夶量新闻需要聚类但对于其中的部分新闻，编辑已经人工分类好了例如(Ni1,Ni2, …, Nim)，为分类好的第i类那么对于人工分类好的数据，就相当于聚类中的先验知识(或正则)

    在聚类时，可相应在邻接矩阵E中增加类彼此间邻接边并使得其邻接权重较大，这样生成的邻接矩阵为E’这樣，再对此邻接矩阵E’做谱聚类聚类结果将在一定程度上维持人工分类的结果，并达到聚类的目的

    PS：更多详情，请参见参考文献2不過谱聚类的半监督学习，都有点扯 

我要回帖

更多关于 新浪博客 的文章

 

随机推荐