图形学:矩阵的第二个特征向量为何能用来分类

g
gooog
楼主 (北美华人网)
刚刚开始学习离散学和图像学。有个问题需要请教一下。
假设一个图形中有N个节点,组成一个N*N的相似矩阵(A)。 为什么矩阵A的第二个特征向量能用来分类?
mincut spectral partition
如果有详细的推导材料,请推荐。多谢。
r
redpearl
在这个板上问这种问题?
g
gokgs
牛!
千渔千寻
回复 1楼gooog的帖子
至少给个推倒过程让人家看看第二个特征向量是什么吧
P
Pelosi
在这个板上问这种问题?
redpearl 发表于 2022-08-16 11:44

P
Pelosi
在这个板上问这种问题?
redpearl 发表于 2022-08-16 11:44

g
gooog
回复 1楼gooog的帖子
至少给个推倒过程让人家看看第二个特征向量是什么吧
千渔千寻 发表于 2022-08-16 12:03

A x = lamda x lamda = {lamda1, lamda2, lamda3...lamdan} lamda1=0 x1=1
x2={x21,x22,x23,....x2n} 这个x2为什么可以用来给A代表的n个节点,分类?
千渔千寻
回复 1楼gooog的帖子
买买提到了以后,想问学术难度,就苦逼了。
w
wswsn
在这个板上问这种问题?
redpearl 发表于 2022-08-16 11:44

马工智商最高
P
Pelosi
回复 1楼gooog的帖子
至少给个推倒过程让人家看看第二个特征向量是什么吧
千渔千寻 发表于 2022-08-16 12:03



“特征”一词译自德语的eigen,由希尔伯特在1904年首先在这个意义下使用(赫尔曼·冯·亥姆霍兹在更早的时候也在类似意义下使用过这一概念)。eigen一词可翻译为“自身的”,“特定于...的”,“有特征的”或者“个体的”—这强调了特征值对于定义特定的变换上是很重要的。
在数学上,特别是线性代数中,对于一个给定的方阵 A {\displaystyle A} ,它的特征向量(eigenvector,也译固有向量本征向量) v {\displaystyle v} 经过这个线性变换[a]之后,得到的新向量仍然与原来的 v {\displaystyle v} 保持在同一条直线上,但其长度或方向也许会改变。即
A v = λ v {\displaystyle Av=\lambda v}
λ {\displaystyle \lambda } 为标量,即特征向量的长度在该线性变换下缩放的比例,称 λ {\displaystyle \lambda } 为其特征值(eigenvalue,也译固有值本征值)。如果特征值为正,则表示 v {\displaystyle v} 在经过线性变换的作用后方向也不变;如果特征值为负,说明方向会反转;如果特征值为0,则是表示缩回零点。但无论怎样,仍在同一条直线上。图1给出了一个以著名油画《蒙娜丽莎》为题材的例子。在一定条件下(如其矩阵形式为实对称矩阵的线性变换),一个变换可以由其特征值和特征向量完全表述,也就是说:所有的特征向量组成了这向量空间的一组基底。
一个特征空间(eigenspace)是具有相同特征值的特征向量与一个同维数的零向量的集合,可以证明该集合是一个线性子空间,比如 E λ = { u ∈ V ∣ A u = λ u } {\displaystyle \textstyle E_{\lambda }=\{u\in V\mid Au=\lambda u\}} 即为线性变换 A {\displaystyle A} 中以 λ {\displaystyle \lambda } 为特征值的特征空间

千渔千寻
回复 6楼Pelosi的帖子
还给的德文的,没诚意
P
Pelosi
回复 6楼Pelosi的帖子
还给的德文的,没诚意
千渔千寻 发表于 2022-08-16 12:14


这方面都是德国人发明的啊.
特征这个单词的英语 就是从德语过来的啊!!
同志

P
Pelosi
回复 6楼Pelosi的帖子
还给的德文的,没诚意
千渔千寻 发表于 2022-08-16 12:14

eigen 在德语里 就是 自己的, 自身的意思.
英语 直接采用了德语 这个单词.

g
gooog


“特征”一词译自德语的eigen,由希尔伯特在1904年首先在这个意义下使用(赫尔曼·冯·亥姆霍兹在更早的时候也在类似意义下使用过这一概念)。eigen一词可翻译为“自身的”,“特定于...的”,“有特征的”或者“个体的”—这强调了特征值对于定义特定的变换上是很重要的。
在数学上,特别是线性代数中,对于一个给定的方阵 A {\displaystyle A} ,它的特征向量(eigenvector,也译固有向量本征向量) v {\displaystyle v} 经过这个线性变换[a]之后,得到的新向量仍然与原来的 v {\displaystyle v} 保持在同一条直线上,但其长度或方向也许会改变。即
A v = λ v {\displaystyle Av=\lambda v}
λ {\displaystyle \lambda } 为标量,即特征向量的长度在该线性变换下缩放的比例,称 λ {\displaystyle \lambda } 为其特征值(eigenvalue,也译固有值本征值)。如果特征值为正,则表示 v {\displaystyle v} 在经过线性变换的作用后方向也不变;如果特征值为负,说明方向会反转;如果特征值为0,则是表示缩回零点。但无论怎样,仍在同一条直线上。图1给出了一个以著名油画《蒙娜丽莎》为题材的例子。在一定条件下(如其矩阵形式为实对称矩阵的线性变换),一个变换可以由其特征值和特征向量完全表述,也就是说:所有的特征向量组成了这向量空间的一组基底。
一个特征空间(eigenspace)是具有相同特征值的特征向量与一个同维数的零向量的集合,可以证明该集合是一个线性子空间,比如 E λ = { u ∈ V ∣ A u = λ u } {\displaystyle \textstyle E_{\lambda }=\{u\in V\mid Au=\lambda u\}} 即为线性变换 A {\displaystyle A} 中以 λ {\displaystyle \lambda } 为特征值的特征空间


Pelosi 发表于 2022-08-16 12:14

多谢!
以n=2为例子。
我们可以在二维空间,来表示一个向量v。假设x的横坐标是3,纵坐标是4. 请问,我们如何在这样的二维空间里,表示一个矩阵呢?
假设这个矩阵A是 [2 0
0 1]
这个矩阵A乘以v,其实所做的就是把x轴拉长2倍。y轴不变。
我们有没有办法,把这个矩阵A在数轴上形象的表示出来?
l
lingling7
Spectral clustering 本来的solution 是binary vector/matrix,可能是np Hard, 记不清了,但是做real value relaxation 后的solution会用到eigenvector 。而且矩阵随便一个矩阵,有要求的。
g
gooog
Spectral clustering 本来的solution 是binary vector/matrix,可能是np Hard, 记不清了,但是做real value relaxation 后的solution会用到eigenvector 。而且矩阵随便一个矩阵,有要求的。
lingling7 发表于 2022-08-16 12:21

对。我就是想寻找这个证明过程。 如何证明,第二个特征向量,其实就是spectral clustering的结果。
l
lingling7
你找spectral clustering 的paper来读呀,或者normalized cut,都差不多的。
g
gooog
你找spectral clustering 的paper来读呀,或者normalized cut,都差不多的。
lingling7 发表于 2022-08-16 12:24

请问,non-normalized cut,有论文推荐吗? 是1976年的 Fiedler那篇?
c
coalpilerd
https://towardsdatascience.com/spectral-clustering-aba2640c0d5b
是第二个特征值, 不是第二个特征向量.
l
lingling7
只知道normalized cut, 搜j Malik
铲屎官
回复 7楼的帖子
不大明白你写的,A是一个nxn矩阵,x是特征向量,Ax=lambda x中的lambda就是一个特征值,但你这里说lambda是一个n维向量,那么lambda x就成了一个数,而Ax是一个n维向量,不明白。如果你想弄清楚特征值和特征向量的意义,下面这个帖子说得蛮清楚的,希望对你有帮助。 https://www.zhihu.com/question/21874816?utm_id=0
你去一亩三分地上问,那边专业人士多。


g
gooog
回复 7楼gooog的帖子
不大明白你写的,A是一个nxn矩阵,x是特征向量,Ax=lamda x中的lamda就是一个特征值,但你这里说lamda是一个n维向量,那么lamda x就成了一个数,而Ax是一个n维向量,不明白。如果你想弄清楚特征值和特征向量的意义,下面这个帖子说得蛮清楚的,希望对你有帮助。 https://www.zhihu.com/question/21874816?utm_id=0



铲屎官 发表于 2022-08-16 12:33

lamda是一维的数值。但是lamda有n个。 x是n维的向量。x也有n个。我用的是v,表示这个x。
n
nickbear

Pelosi 发表于 2022-08-16 12:11

你连题目都看不懂还是别往上凑了,继续贴旅游图比较适合你
k
keynorth01
回复 1楼gooog的帖子
要从矩阵计算的基本原理开始理解,科学的东西都是大同小异。
相似矩阵的第一个eigenvector, 一般都是level, 平均值。声音学里就是平均响频,平均分贝。图像学就是平均亮度,平均光谱波长。股市里就是大盘。华人上就是平均收入水平。
第二个eigenvector,一般就是linear slope, 代表从高到低的difference, 可以用来排序,分类等等。声学里的dynamic range。图像学里的对比度,色差。股市里的high beta vs. low beta。华人上富婆vs贫困线下。
信息压缩最重要的就是这两个,再往后就基本不是linear的了,重要性逐步下降,主要用来细分。
l
lingling7
对的,eigenvector 是基于相似矩阵的hamonics. 如果你的相似矩阵是循环矩阵,相应的eigenvector 就Fourier basis, ranking from low frequency to high frequency
n
nickbear
找本讲spectual clustering书或者课件就有 https://www.cs.cmu.edu/~aarti/Class/10701/slides/Lecture21_2.pdf 简单的说mincut问题可以定义为一个优化问题,这个优化问题可以转化为一个矩阵方程的解
g
gooog
回复 1楼gooog的帖子
要从矩阵计算的基本原理开始理解,科学的东西都是大同小异。
相似矩阵的第一个eigenvector, 一般都是level, 平均值。声音学里就是平均响频,平均分贝。图像学就是平均亮度,平均光谱波长。股市里就是大盘。华人上就是平均收入水平。
第二个eigenvector,一般就是linear slope, 代表从高到低的difference, 可以用来排序,分类等等。声学里的dynamic range。图像学里的对比度,色差。股市里的high beta vs. low beta。华人上富婆vs贫困线下。
信息压缩最重要的就是这两个,再往后就基本不是linear的了,重要性逐步下降,主要用来细分。
keynorth01 发表于 2022-08-16 12:37

能详细说说,怎么从股市里提出第二特征向量,然后预测股市的未来走向?
g
gooog
找本讲spectual clustering书或者课件就有 https://www.cs.cmu.edu/~aarti/Class/10701/slides/Lecture21_2.pdf 简单的说mincut问题可以定义为一个优化问题,这个优化问题可以转化为一个矩阵方程的解
nickbear 发表于 2022-08-16 12:41

多谢大牛帮助。
m
magicflute
回复 1楼gooog的帖子
要从矩阵计算的基本原理开始理解,科学的东西都是大同小异。
相似矩阵的第一个eigenvector, 一般都是level, 平均值。声音学里就是平均响频,平均分贝。图像学就是平均亮度,平均光谱波长。股市里就是大盘。华人上就是平均收入水平。
第二个eigenvector,一般就是linear slope, 代表从高到低的difference, 可以用来排序,分类等等。声学里的dynamic range。图像学里的对比度,色差。股市里的high beta vs. low beta。华人上富婆vs贫困线下。
信息压缩最重要的就是这两个,再往后就基本不是linear的了,重要性逐步下降,主要用来细分。
keynorth01 发表于 2022-08-16 12:37

太赞了 牛
千渔千寻
回复 24楼keynorth01的帖子
你这个第一vector怎么定义的?
lamda绝对值大小降序排列的第一个eigenvector么?
图像主成分分析的最大eigenvalue的eigenvector也有这种性质么?
g
genia
回复 1楼gooog的帖子
不就是切瓜吗? 搞得这么复杂
竖着切第一特征向量方向, 横着切第二特征向量方向
c
cafe1123
回复 1楼gooog的帖子
要从矩阵计算的基本原理开始理解,科学的东西都是大同小异。
相似矩阵的第一个eigenvector, 一般都是level, 平均值。声音学里就是平均响频,平均分贝。图像学就是平均亮度,平均光谱波长。股市里就是大盘。华人上就是平均收入水平。
第二个eigenvector,一般就是linear slope, 代表从高到低的difference, 可以用来排序,分类等等。声学里的dynamic range。图像学里的对比度,色差。股市里的high beta vs. low beta。华人上富婆vs贫困线下。
信息压缩最重要的就是这两个,再往后就基本不是linear的了,重要性逐步下降,主要用来细分。
keynorth01 发表于 2022-08-16 12:37

不懂装懂。