谱聚类的推导.doc_第1页
谱聚类的推导.doc_第2页
谱聚类的推导.doc_第3页
谱聚类的推导.doc_第4页
免费预览已结束，剩余1页可下载查看

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

谱聚类的推导I 两类别谱聚类样本集合，输入空间到特征空间的映射，对应的核函数，假设在特征空间中的样本为规范化的样本，即：。K为对应的核矩阵：定义一个n维样本聚类标示矢量，对应中元素为-1的样本标示为一个类别，+1的样本标示为另一个类别。假定两个类别的样本数量相等，即：选择类间离散度准则进行优化：此准则的意义是寻找一种对样本集合的划分（由标示矢量确定），使得不同类别之间的样本距离平方和最大。其中用到，。由于，因此优化问题等价于最小化：其中第一项与无关，因此优化问题可以表示为矩阵形式：Subject to ，直接求解上述优化问题是一个组合优化问题，属于NP难题。这里对上述问题进行松弛，首先不再要求的元素必须是-1或者+1，同时也不再要求两个类别的样本数相等，而是转而约束的长度为1，这样上述问题可以转化为一个无约束的Raleigh商的优化问题：参考PCA的推导过程，最优矢量为矩阵对应最大特征值的特征矢量。为了最终得到对样本的聚类结果，可以对中的元素阈值化，大于阈值的对应样本为一个类别，小于阈值的对应样本为另一个类别。II 多类别谱聚类令为样本矩阵，每一行一个样本，是一个的矩阵，n为样本数，d为特征维数（可以是无穷）；是一个的指派矩阵，m是聚类的个数，A的每一行中只有一个元素为1，其他元素为0，1的位置表示对应样本被指派到该类别；是一个的对角矩阵，其对角线元素为被指派到对应类别的样本数的倒数，矩阵依赖于矩阵。可以验证维的矩阵的每一列是对应聚类的均值。而维矩阵的每一列为对应样本被指派聚类的均值。选择类内离散度平方误差准则：其中矩阵的范数采用的是Frobinus范数，即所有元素的平方和。这一准则的目标是使的所有的样本到其被指派的聚类中心距离的平方和最小。令为n维的单位矩阵，则有（见附录1），因此：上式第1项与无关，核矩阵，因此优化问题可以转化为：可以验证，令，则变成如下优化问题：Subject to 由于，可以证明（见附录2）：，因此可以对进行优化。分别将和写成行矢量和列矢量的形式：，因此：约束条件表明的列矢量是单位正交矢量，因此引入拉格朗日乘子，建立优化准则函数：对的第k个列矢量求导：其中：，因此有：，所以最优解的m个列是对应于核矩阵最大m个特征值的特征矢量。而最大值为，是由大到小排列的的特征值（参见PCA的推导）。上述结论只是表明可以通过核矩阵的特征值确定聚类的数目，样本的具体类别划分还需要根据相应的特征矢量采用其他方法得到。III 附录1证明：矩阵是一个的矩阵，其主对角线元素是对应样本所属类别（第k类别）样本数的倒数，如果第i个样本和第j个样本属于不同类别，则第(i,j)元素为0，否则为所属类别样本的倒数。矩阵的主对角线元素为，其他的0元素仍为0，非零元素变为。矩阵的主对角元素为：其他的0元素仍然是0，非0元素为：因此有：IV 附录2证明：是一个维的矩阵，是一个维的矩阵：，因此：计算可以得到：其中外层（对k求和）是在对角线上
人人文库> 全部分类> 生活休闲 > 科普知识

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论