数据挖掘与分析课程笔记（Chapter 20）

数据挖掘与分析课程笔记

• 参考教材：Data Mining and Analysis : MOHAMMED J.ZAKI, WAGNER MEIRA JR.

文章目录

0. 数据挖掘与分析课程笔记（目录）
1. 数据挖掘与分析课程笔记（Chapter 1）
2. 数据挖掘与分析课程笔记（Chapter 2）
3. 数据挖掘与分析课程笔记（Chapter 5）
4. 数据挖掘与分析课程笔记（Chapter 7）
5. 数据挖掘与分析课程笔记（Chapter 14）
6. 数据挖掘与分析课程笔记（Chapter 15）
7. 数据挖掘与分析课程笔记（Chapter 20）
8. 数据挖掘与分析课程笔记（Chapter 21）

---

---

Chapter 20: Linear Discriminant Analysis

Set up：$\mathbf{D}=\{({\mathbf{x}}_i,y_i){\}}_{i=1}^n$， 其中 $y_i=1,2$（或 $\pm 1$ 等）， D 1 = { x i ∣ y i = 1 } \mathbf{D}_1=\{\mathbf{x}_i|y_i=1 \} D1​={xi​∣yi​=1}， D 2 = { x i ∣ y i = 2 } \mathbf{D}_2=\{\mathbf{x}_i|y_i=2 \} D2​={xi​∣yi​=2}

Goal：寻找向量 $\mathbf{w}\in {\mathbb{R}}^d$ （代表直线方向）使得 ${\mathbf{D}}_1,{\mathbf{D}}_2$ 的“平均值”距离最大且“总方差”最小。

20.1 Normal LDA

设 $\mathbf{w}\in {\mathbb{R}}^d,{\mathbf{w}}^T\mathbf{w}=1$，则 ${\mathbf{x}}_i$ 在 $\mathbf{w}$ 方向上的投影为 ${\mathbf{x}}_i^{\prime }=\left(\frac{{\mathbf{w}}^T{\mathbf{x}}_i}{{\mathbf{w}}^T\mathbf{u}}\right)\mathbf{w}=a_i\mathbf{w},a_i={\mathbf{w}}^T{\mathbf{x}}_i$

则 ${\mathbf{D}}_1$ 中数据在 $\mathbf{w}$ 上的投影平均值为：（$|{\mathbf{D}}_1|=n_1$）
$$m_1:=\frac{1}{n_1}\sum _{{\mathbf{x}}_i\in {\mathbf{D}}_1}{a}_i={\mathbf{\mu }}_1^T\mathbf{w}$$
投影平均值等于平均值的投影。

类似地： ${\mathbf{D}}_2$ 中数据在 $\mathbf{w}$ 上的投影平均值为：
$$m_2:=\frac{1}{n_2}\sum _{{\mathbf{x}}_i\in {\mathbf{D}}_2}{a}_i={\mathbf{\mu }}_2^T\mathbf{w}$$
目标之一：寻找 $\mathbf{w}$ 使得 $(m_1-m_2{)}^2$ 最大。

对于 ${\mathbf{D}}_i$，定义：
$$s_i^2=\sum _{{\mathbf{x}}_k\in {\mathbf{D}}_i}(a_k-m_i{)}^2$$
注意：$s_i^2=n_i{\sigma }_i^2(|D_i|=n_i)$

Goal：Fisher LDA目标函数：
$$\underset{\mathbf{w}}{\max }J(\mathbf{w})=\frac{(m_1-m_2{)}^2}{s_1^2+s_2^2}$$
注意：$J(\mathbf{w})=J(w_1,w_2,\cdots ,w_d)$
( m 1 − m 2 ) 2 = ( w T ( μ 1 − μ 2 ) ) 2 = w T ( ( μ 1 − μ 2 ) ( μ 1 − μ 2 ) T ) w = w T B w

(m1​−m2​)2​=(wT(μ1​−μ2​))2=wT((μ1​−μ2​)(μ1​−μ2​)T)w=wTBw​

$\mathbf{B}$ 被称为类间扩散矩阵

s 1 2 = ∑ x i ∈ D 1 ( a i − m 1 ) 2 = ∑ x i ∈ D 1 ( w T x i − w T μ 1 ) 2 = ∑ x i ∈ D 1 ( w T ( x i − μ 1 ) ) 2 = w T ( ∑ x i ∈ D 1 ( x i − μ 1 ) ( x i − μ 1 ) T ) w = w T S 1 w

s12​​=xi​∈D1​∑​(ai​−m1​)2=xi​∈D1​∑​(wTxi​−wTμ1​)2=xi​∈D1​∑​(wT(xi​−μ1​))2=wT(xi​∈D1​∑​(xi​−μ1​)(xi​−μ1​)T)w=wTS1​w​

${\mathbf{S}}_1$ 被称为 ${\mathbf{D}}_1$ 的扩散矩阵 ${\mathbf{S}}_1=n_1{\Sigma }_1$

类似地，$s_2^2={\mathbf{w}}^T{\mathbf{S}}_2\mathbf{w}$

令 $\mathbf{S}={\mathbf{S}}_1+{\mathbf{S}}_2$，则
$$\underset{\mathbf{w}}{\max }J(\mathbf{w})=\frac{(m_1-m_2{)}^2}{s_1^2+s_2^2}=\frac{{\mathbf{w}}^T\mathbf{Bw}}{{\mathbf{w}}^T\mathbf{Sw}}$$

注意：
$$\frac{d}{d\mathbf{w}}J(\mathbf{w})=\frac{2\mathbf{Bw}({\mathbf{w}}^T\mathbf{Sw})-2\mathbf{Sw}({\mathbf{w}}^T\mathbf{Bw})}{({\mathbf{w}}^T\mathbf{Sw}{)}^2}=0$$
即有：
B w ( w T S w ) = S w ( w T B w ) B w = S w ⋅ w T B w w T S w B w = J ( w ) ⋅ S w ( ∗ )

Bw(wTSw)BwBw​=Sw(wTBw)=Sw⋅wTSwwTBw​=J(w)⋅Sw(∗)​
若 ${\mathbf{S}}^{-1}$ 存在，则
$${\mathbf{S}}^{-1}\mathbf{Bw}=J(\mathbf{w})\cdot \mathbf{w}$$
故要求最大 $J(\mathbf{w})$ ，只需 ${\mathbf{S}}^{-1}\mathbf{B}$ 的最大特征值，$\mathbf{w}$ 为其特征向量。

☆ 不求特征向量求出 $\mathbf{w}$ 的方法

将 $\mathbf{B}=({\mathbf{\mu }}_1-{\mathbf{\mu }}_2)({\mathbf{\mu }}_1-{\mathbf{\mu }}_2{)}^T$ 代入 $(\ast )$ 得
( μ 1 − μ 2 ) ( μ 1 − μ 2 ) T w = J ( w ) ⋅ S w S − 1 ( μ 1 − μ 2 ) [ ( μ 1 − μ 2 ) T w J ( w ) ] = w

(μ1​−μ2​)(μ1​−μ2​)TwS−1(μ1​−μ2​)[J(w)(μ1​−μ2​)Tw​]​=J(w)⋅Sw=w​
故只需计算 ${\mathbf{S}}^{-1}({\mathbf{\mu }}_1-{\mathbf{\mu }}_2)$，再单位化。

20.2 Kernel LDA：

事实1：如果 $\left({\mathbf{S}}_{\varphi }^{-1}{\mathbf{B}}_{\varphi }\right)\mathbf{w}=\lambda \mathbf{w}$，那么 $\mathbf{w}=\sum _{j=1}^n{a}_j\varphi ({\mathbf{x}}_j)$，证明见讲稿最后两页。

令 $\mathbf{a}=(a_1,\cdots ,a_n{)}^T$ 是“事实1”中的向量。

下面将 $\underset{\mathbf{w}}{\max }J(\mathbf{w})=\frac{(m_1-m_2{)}^2}{s_1^2+s_2^2}=\frac{{\mathbf{w}}^T{\mathbf{B}}_{\varphi }\mathbf{w}}{{\mathbf{w}}^T{\mathbf{S}}_{\varphi }\mathbf{w}}$ 的问题转化为 $\max G(\mathbf{a})$ s.t. 使用 $\mathbf{K}$ 能求解。

注意到：
m i = w T μ i ϕ = ( ∑ j = 1 n a j ϕ ( x j ) ) T ( 1 n i ∑ x i ∈ D i ϕ ( x k ) ) = 1 n i ∑ j = 1 n ∑ x k ∈ D i a j ϕ ( x j ) T ϕ ( x k ) = 1 n i ∑ j = 1 n ∑ x k ∈ D i a j K ( x j , x k ) = a T m i

mi​=wTμiϕ​​=(j=1∑n​aj​ϕ(xj​))T(ni​1​xi​∈Di​∑​ϕ(xk​))=ni​1​j=1∑n​xk​∈Di​∑​aj​ϕ(xj​)Tϕ(xk​)=ni​1​j=1∑n​xk​∈Di​∑​aj​K(xj​,xk​)=aTmi​​
其中，
m i = 1 n i ( ∑ x k ∈ D i K ( x 1 , x k ) ∑ x k ∈ D i K ( x 2 , x k ) ⋮ ∑ x k ∈ D i K ( x n , x k ) ) n × 1 \mathbf{m}_{i}=\frac{1}{n_{i}}\left(

∑xk∈DiK(x1,xk)∑xk∈DiK(x2,xk)⋮∑xk∈DiK(xn,xk)" role="presentation">∑xk∈DiK(x1,xk)∑xk∈DiK(x2,xk)⋮∑xk∈DiK(xn,xk)$$\begin{array}{c}\sum _{{\mathbf{x}}_k\in {\mathbf{D}}_i}K\left({\mathbf{x}}_1,{\mathbf{x}}_k\right)\\ \sum _{{\mathbf{x}}_k\in {\mathbf{D}}_i}K\left({\mathbf{x}}_2,{\mathbf{x}}_k\right)\\ ⋮\\ \sum _{{\mathbf{x}}_k\in {\mathbf{D}}_i}K\left({\mathbf{x}}_n,{\mathbf{x}}_k\right)\end{array}$$

\right)_{n\times 1} mi​=ni​1​⎝ ⎛​xk​∈Di​∑​K(x1​,xk​)xk​∈Di​∑​K(x2​,xk​)⋮xk​∈Di​∑​K(xn​,xk​)​⎠ ⎞​n×1​
故
( m 1 − m 2 ) 2 = ( w T μ 1 ϕ − w T μ 2 ϕ ) 2 = ( a T m 1 − a T m 2 ) 2 = a T ( m 1 − m 2 ) ( m 1 − m 2 ) T a = a T M a

(m1−m2)2=(wTμ1ϕ−wTμ2ϕ)2=(aTm1−aTm2)2=aT(m1−m2)(m1−m2)Ta=aTMa" role="presentation">(m1−m2)2=(wTμϕ1−wTμϕ2)2=(aTm1−aTm2)2=aT(m1−m2)(m1−m2)Ta=aTMa$$\begin{array}{rl}{\left(m_1-m_2\right)}^2& ={\left({\mathbf{w}}^T{\mathit{\mu }}_1^{\varphi }-{\mathbf{w}}^T{\mathit{\mu }}_2^{\varphi }\right)}^2\\ & ={\left({\mathbf{a}}^T{\mathbf{m}}_1-{\mathbf{a}}^T{\mathbf{m}}_2\right)}^2\\ & ={\mathbf{a}}^T\left({\mathbf{m}}_1-{\mathbf{m}}_2\right){\left({\mathbf{m}}_1-{\mathbf{m}}_2\right)}^T\mathbf{a}\\ & ={\mathbf{a}}^T\mathbf{M}\mathbf{a}\end{array}$$

(m1​−m2​)2​=(wTμ1ϕ​−wTμ2ϕ​)2=(aTm1​−aTm2​)2=aT(m1​−m2​)(m1​−m2​)Ta=aTMa​
（$\mathbf{M}$ 被称为核类间扩散矩阵）
s 1 2 = ∑ x i ∈ D 1 ∥ w T ϕ ( x i ) − w T μ 1 ϕ ∥ 2 = ∑ x i ∈ D 1 ∥ w T ϕ ( x i ) ∥ 2 − 2 ∑ x i ∈ D 1 w T ϕ ( x i ) ⋅ w T μ 1 ϕ + ∑ x i ∈ D 1 ∥ w T μ 1 ϕ ∥ 2 = ( ∑ x i ∈ D 1 ∥ ∑ j = 1 n a j ϕ ( x j ) T ϕ ( x i ) ∥ 2 ) − 2 ⋅ n 1 ⋅ ∥ w T μ 1 ϕ ∥ 2 + n 1 ⋅ ∥ w T μ 1 ϕ ∥ 2 = ( ∑ x i ∈ D 1 a T K i K i T a ) − n 1 ⋅ a T m 1 m 1 T a = a T ( ( ∑ x i ∈ D 1 K i K i T ) − n 1 m 1 m 1 T ) a = a T N 1 a

s12=∑xi∈D1‖wTϕ(xi)−wTμ1ϕ‖2=∑xi∈D1‖wTϕ(xi)‖2−2∑xi∈D1wTϕ(xi)⋅wTμ1ϕ+∑xi∈D1‖wTμ1ϕ‖2=(∑xi∈D1‖∑j=1najϕ(xj)Tϕ(xi)‖2)−2⋅n1⋅‖wTμ1ϕ‖2+n1⋅‖wTμ1ϕ‖2=(∑xi∈D1aTKiKiTa)−n1⋅aTm1m1Ta=aT((∑xi∈D1KiKiT)−n1m1m1T)a=aTN1a" role="presentation">s21=∑xi∈D1∥∥wTϕ(xi)−wTμϕ1∥∥2=∑xi∈D1∥∥wTϕ(xi)∥∥2−2∑xi∈D1wTϕ(xi)⋅wTμϕ1+∑xi∈D1∥∥wTμϕ1∥∥2=⎛⎝∑xi∈D1∥∥∥∥∑j=1najϕ(xj)Tϕ(xi)∥∥∥∥2⎞⎠−2⋅n1⋅∥∥wTμϕ1∥∥2+n1⋅∥∥wTμϕ1∥∥2=(∑xi∈D1aTKiKTia)−n1⋅aTm1mT1a=aT((∑xi∈D1KiKTi)−n1m1mT1)a=aTN1a$$\begin{array}{rl}{s}_1^2& =\sum _{{\mathbf{x}}_i\in {\mathbf{D}}_1}{\Vert {\mathbf{w}}^T\varphi \left({\mathbf{x}}_i\right)-{\mathbf{w}}^T{\mathit{\mu }}_1^{\varphi }\Vert }^2\\ & =\sum _{{\mathbf{x}}_i\in {\mathbf{D}}_1}{\Vert {\mathbf{w}}^T\varphi \left({\mathbf{x}}_i\right)\Vert }^2-2\sum _{{\mathbf{x}}_i\in {\mathbf{D}}_1}{\mathbf{w}}^T\varphi \left({\mathbf{x}}_i\right)\cdot {\mathbf{w}}^T{\mathit{\mu }}_1^{\varphi }+\sum _{{\mathbf{x}}_i\in {\mathbf{D}}_1}{\Vert {\mathbf{w}}^T{\mathit{\mu }}_1^{\varphi }\Vert }^2\\ & =\left(\sum _{{\mathbf{x}}_i\in {\mathbf{D}}_1}{\Vert \sum _{j=1}^n{a}_j\varphi {\left({\mathbf{x}}_j\right)}^T\varphi \left({\mathbf{x}}_i\right)\Vert }^2\right)-2\cdot n_1\cdot {\Vert {\mathbf{w}}^T{\mathit{\mu }}_1^{\varphi }\Vert }^2+n_1\cdot {\Vert {\mathbf{w}}^T{\mathit{\mu }}_1^{\varphi }\Vert }^2\\ & =\left(\sum _{{\mathbf{x}}_i\in {\mathbf{D}}_1}{\mathbf{a}}^T{\mathbf{K}}_i{\mathbf{K}}_i^T\mathbf{a}\right)-n_1\cdot {\mathbf{a}}^T{\mathbf{m}}_1{\mathbf{m}}_1^T\mathbf{a}\\ & ={\mathbf{a}}^T\left(\left(\sum _{{\mathbf{x}}_i\in {\mathbf{D}}_1}{\mathbf{K}}_i{\mathbf{K}}_i^T\right)-n_1{\mathbf{m}}_1{\mathbf{m}}_1^T\right)\mathbf{a}\\ & ={\mathbf{a}}^T{\mathbf{N}}_1\mathbf{a}\end{array}$$

s12​​=xi​∈D1​∑​∥ ∥​wTϕ(xi​)−wTμ1ϕ​∥ ∥​2=xi​∈D1​∑​∥ ∥​wTϕ(xi​)∥ ∥​2−2xi​∈D1​∑​wTϕ(xi​)⋅wTμ1ϕ​+xi​∈D1​∑​∥ ∥​wTμ1ϕ​∥ ∥​2=⎝ ⎛​xi​∈D1​∑​∥ ∥​j=1∑n​aj​ϕ(xj​)Tϕ(xi​)∥ ∥​2⎠ ⎞​−2⋅n1​⋅∥ ∥​wTμ1ϕ​∥ ∥​2+n1​⋅∥ ∥​wTμ1ϕ​∥ ∥​2=(xi​∈D1​∑​aTKi​KiT​a)−n1​⋅aTm1​m1T​a=aT((xi​∈D1​∑​Ki​KiT​)−n1​m1​m1T​)a=aTN1​a​
类似地，令 ${\mathbf{N}}_2=\left(\sum _{{\mathbf{x}}_i\in {\mathbf{D}}_2}{\mathbf{K}}_i{\mathbf{K}}_i^T-n_2{\mathbf{m}}_2{\mathbf{m}}_2^T\right)$

则 $s_1^2+s_2^2={\mathbf{a}}^T({\mathbf{N}}_1+{\mathbf{N}}_2)\mathbf{a}={\mathbf{a}}^T\mathbf{Na}$

故：$J(\mathbf{w})=\frac{{\mathbf{a}}^T\mathbf{Ma}}{{\mathbf{a}}^T\mathbf{Na}}:=G(\mathbf{a})$

类似 20.1，$\mathbf{Ma}=\lambda \mathbf{Na}$

• 若 ${\mathbf{N}}^{-1}$ 存在，${\mathbf{N}}^{-1}\mathbf{Ma}=\lambda \mathbf{a}$，$\lambda$ 取 ${\mathbf{N}}^{-1}\mathbf{M}$ 的最大特征值，$\mathbf{a}$ 是相应的特征向量。

• 若 ${\mathbf{N}}^{-1}$ 不存在，MATLAB 求广义逆

最后考查 ${\mathbf{w}}^T\mathbf{w}=1$，即

( ∑ j = 1 n a j ϕ ( x j ) ) T ( ∑ i = 1 n a i ϕ ( x i ) ) = 1 ∑ j = 1 n ∑ i = 1 n a j a i ϕ ( x j ) T ϕ ( x i ) = 1 ∑ j = 1 n ∑ i = 1 n a j a i K ( x i , x j ) = 1 a T K a = 1

(j=1∑n​aj​ϕ(xj​))T(i=1∑n​ai​ϕ(xi​))j=1∑n​i=1∑n​aj​ai​ϕ(xj​)Tϕ(xi​)j=1∑n​i=1∑n​aj​ai​K(xi​,xj​)aTKa​=1=1=1=1​
求出 ${\mathbf{N}}^{-1}\mathbf{M}$ 的特征向量 $\mathbf{a}$ 后，$\mathbf{a}\leftarrow \frac{\mathbf{a}}{\sqrt{{\mathbf{a}}^T\mathbf{Ka}}}$ 以保证 ${\mathbf{w}}^T\mathbf{w}=1$

---