谱聚类算法入门教程（三）—— 求f^TLf的最小值

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了谱聚类算法入门教程（三）—— 求f^TLf的最小值，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含6804字，纯文字阅读大概需要10分钟。

内容图文

文章目录

• 1. 求$f^TLf$的导数
• 2. $f$ 的定义
• 3. 求解 $arg \min \limits_{f \in \R^6} f^TLf$
• 5. 拓展到 k > 2
• 6. 正则拉普拉斯矩阵
• 7. RatioCut 和 Ncut

在上一篇博客中，我们知道目标函数变为 $arg \min \limits_{f \in \R^6} f^TLf$argf∈R6min?fTLf，即找到一个$f$f，使得 $f^TLf$fTLf 取得最小值

这篇博客将通过求导的方式取得目标函数的最小值。

1. 求$f^TLf$fTLf的导数

目标函数的未知量为$f$f，那么 $f^TLf$fTLf 的导数可以表示为$\displaystyle \frac{\partial}{\partial f} f^TLf$?f??fTLf。

这里为了方便证明，使用一个二维向量作为例子，推广到更高维空间也是一样的，即假设 $f^T = [f_1 \space \space f_2]$fT=[f1?  f2?]，$L = \left[\begin{matrix} a_{11} & a_{12} \\ a_{21} & a_{22} \end{matrix}\right]$L=[a11?a21??a12?a22??]

故：

$\begin{aligned}\displaystyle \frac{\partial}{\partial f} f^TLf &= \displaystyle \frac{\partial}{\partial f} \left[ \begin{matrix} f_1 & f_2 \end{matrix}\right] \left[\begin{matrix}a_{11} & a_{12} \\ a_{21} & a_{22}\end{matrix}\right] \left[\begin{matrix}f_{1}\\ f_{2}\end{matrix}\right] \\ & = \displaystyle \frac{\partial}{\partial f} \left[ \begin{matrix} f_1 & f_2 \end{matrix}\right] \left[\begin{matrix}a_{11}f_1 + a_{12}f_2 \\ a_{21}f_1 + a_{22}f_2 \end{matrix}\right] \\ & = \displaystyle \frac{\partial}{\partial f} a_{11}f_1^2 + a_{12}f_1f_2 + a_{21}f_1f_2 + a_{22}f_2^2 \\ & = \displaystyle \left[ \begin{matrix}\displaystyle \frac{\partial}{\partial f_1} a_{11}f_1^2 + a_{12}f_1f_2 + a_{21}f_1f_2 + a_{22}f_2^2 \\ \displaystyle \frac{\partial}{\partial f_2} a_{11}f_1^2 + a_{12}f_1f_2 + a_{21}f_1f_2 + a_{22}f_2^2\end{matrix} \right] \\ & = \left[ \begin{matrix}2a_{11}f_1 + a_{12}f_2 + a_{21}f_2 \\ a_{12}f_1 + a_{21}f_1 + 2a_{22}f_2 \end{matrix} \right] \\ & = \displaystyle \left[ \left[ \begin{matrix}a_{11} & a_{12} \\ a_{21} & a{22}\end{matrix}\right] + \left[ \begin{matrix}a_{11} & a_{21} \\ a_{12} & a{22}\end{matrix}\right]\right]\left[ \begin{matrix}f_{1} \\ f_{2} \end{matrix}\right] \\ & = \displaystyle (L+L^T)f \end{aligned}$?f??fTLf?=?f??[f1??f2??][a11?a21??a12?a22??][f1?f2??]=?f??[f1??f2??][a11?f1?+a12?f2?a21?f1?+a22?f2??]=?f??a11?f12?+a12?f1?f2?+a21?f1?f2?+a22?f22?=?????f1???a11?f12?+a12?f1?f2?+a21?f1?f2?+a22?f22??f2???a11?f12?+a12?f1?f2?+a21?f1?f2?+a22?f22??????=[2a11?f1?+a12?f2?+a21?f2?a12?f1?+a21?f1?+2a22?f2??]=[[a11?a21??a12?a22?]+[a11?a12??a21?a22?]][f1?f2??]=(L+LT)f?

根据拉普拉斯矩阵的定义我们可以知道拉普拉斯矩阵是对称矩阵¹，因此 $L^T = L$LT=L，原式可以转化为：

$\begin{aligned}\displaystyle \frac{\partial}{\partial f} f^TLf &= (L+L^T)f \\ &=2Lf\end{aligned}$?f??fTLf?=(L+LT)f=2Lf?

2. $f$f 的定义

在求解目标函数之前，我们回忆一下我们一开始给出的 $f$f 的定义：

$f_i = \begin{cases} \sqrt{\displaystyle \frac{1}{|A|}} & k_i \in A \\ \space \space \space \space \space 0 & k_i \in \bar{A} \end{cases}$fi?=????∣A∣1??     0?ki?∈Aki?∈Aˉ?

该定义满足：$f^Tf = I$fTf=I，$I$I 为单位矩阵

• Frobenius norm(Frobenius 范数)

Frobenius 范数，简称F-范数，是一种矩阵范数，记为$||·||_F$∣∣?∣∣F?。矩阵 A 的Frobenius范数定义为矩阵A各项元素的绝对值平方的总和，即

$||A||_F = \displaystyle \sqrt{\sum_{i=1}^m\sum_{j=1}^n|a_{i,j}|^2} = \sqrt{tr(A^TA)}$∣∣A∣∣F?=i=1∑m?j=1∑n?∣ai,j?∣2?=tr(ATA)?

3. 求解 $arg \min \limits_{f \in \R^6} f^TLf$argf∈R6min?fTLf

上面关于$f$f 的定义中，可以知道$f^Tf = I$fTf=I，故$f^Tf - I = 0$fTf?I=0

$f^TLf$fTLf 的导数（$\lambda$λ为某个常数）：

$\begin{aligned}\displaystyle \frac{\partial}{\partial f} f^TLf &= \displaystyle \frac{\partial}{\partial f} f^TLf - \lambda(f^Tf-I) \\ &= \displaystyle \frac{\partial}{\partial f}[ f^TLf-\lambda f^Tf + \lambda]\end{aligned}$?f??fTLf?=?f??fTLf?λ(fTf?I)=?f??[fTLf?λfTf+λ]?

由上面第一点的关于导数的讨论中，可以知道：$ \frac{\partial}{\partial f} f^TLf = 2Lf$

故上面的导数可以转化为：

$\begin{aligned}\displaystyle \frac{\partial}{\partial f} f^TLf = 2Lf-\lambda 2f \end{aligned}$?f??fTLf=2Lf?λ2f?

若$2Lf=\lambda 2f$2Lf=λ2f，即$Lf = \lambda f$Lf=λf，则导数为0，此时取到极点

根据特征值和特征向量的定义：若$Lx =\lambda x$Lx=λx，则 $x$x 为矩阵$L$L的特征向量，$\lambda$λ 为特征值

即当$f$f 为$L$L的特征向量时取得极值。

我们再对导数求导，可得：$\displaystyle \frac{\partial^2}{\partial f^2} f^TLf = 2L$?f2?2?fTLf=2L，因为$L$L 为拉普拉斯矩阵，根据拉普拉斯矩阵的定义，$L$L 为半正定矩阵，故导数的导数大于0，导数递增，极值即为最小值。

所以，$arg \min \limits_{f \in \R^6} f^TLf$argf∈R6min?fTLf 在 $f$f 取最小特征值对应的特征向量时取得最小值。

不过，当$f$f 取得特征向量的时候，未必满足一开始 $f$f 的定义（最重要的是未必满足约束条件$f^Tf = I$fTf=I，因为这是推导出最小值的关键），因此通常对$L$L的特征向量进行k-means聚类分析，生成一个最接近特征向量的向量。

以我们在教程（二）的简单的例子为例，一个计算特征向量的在线网站

取特征值 5 为例（这里最小的特征值6是最小特征值，不过从特征向量可以看出特征值5的分类更明显），从这6个数（0.3587, 0.3149, 0.3145, -0.4513, -0.5149, -0.4521）的分布可以将其分为两类，前三个为一类，后三个为一类，这符合我们一开始从图上看出来的结果，此时：

$f = \left[ \begin{matrix} \displaystyle \frac{1}{\sqrt{3}} \\ \displaystyle \frac{1}{\sqrt{3}} \\ \displaystyle \frac{1}{\sqrt{3}} \\ 0 \\ 0 \\ 0 \end{matrix}\right]$f=??????????????3?1?3?1?3?1?000???????????????

5. 拓展到 k > 2

前面我们的假设一直是 k=2，如果需要不仅分为两类$A$A 和 $\bar{A}$Aˉ，而是多个聚类，我们可以取 k 个特征向量，然后对这 k 个特征向量组成的矩阵进行k-means聚类分析，原理和上面是类似的。

6. 正则拉普拉斯矩阵

在之前的讨论中，一直使用的是普通的拉普拉斯矩阵，实际情况中，经常使用的是正则拉普拉斯矩阵，可以提高数据之间的可比性。

正则拉普拉斯矩阵的定义：

$L_{sys} = D^{-1/2}LD^{-1/2} = I - D^{-1/2}WD^{-1/2}$Lsys?=D?1/2LD?1/2=I?D?1/2WD?1/2

$L_{rw} = D^{-1}L = I - D^{-1}W$Lrw?=D?1L=I?D?1W

$L_{sys}$Lsys?和$L_{rw}$Lrw?都是拉普拉斯矩阵的一种。

正则拉普拉斯矩阵的性质：

(λ，u)是$L_{rw}$Lrw?的特征值和特征向量，当且仅当(λ，$D^{1/2}u$D1/2u)是$L_{sym}$Lsym?的特征值和特征向量

7. RatioCut 和 Ncut

在上面的讨论中，用于衡量聚类分析优异的函数为：

$R = \displaystyle \sum_{i,j = 1}^{n}w_{i,j}(f_i-f_j)^2$R=i,j=1∑n?wi,j?(fi??fj?)2

在实际操作中，为了避免聚类效果不佳，常使用两种方法来聚类分析：RatioCut和Ncut，具体可以参考博客：https://www.cnblogs.com/pinard/p/6221564.html，基本原理和上面的证明过程是一致的，这里就不赘述了，啦啦啦。

---

1. 拉普拉斯矩阵 ??

内容总结

以上是互联网集市为您收集整理的谱聚类算法入门教程（三）—— 求f^TLf的最小值全部内容，希望文章能够帮你解决谱聚类算法入门教程（三）—— 求f^TLf的最小值所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---