Dimensionality Reduction: PCA, SVD & Factor Analysis（非考試範圍）

1. 點解要做 Dimensionality Reduction（Slide 2–3）

Chapter 2 講 data preprocessing 時已經提過 curse of dimensionality：attributes 越多，data 喺 space 入面就越 sparse，distance 同 density 嘅意義會變弱，計算量亦都會增加。呢章介紹三種方法，用少量新 attributes 代替原本好多個 attributes：

• Principal Components Analysis (PCA)
• Singular Value Decomposition (SVD)
• Factor Analysis (FA)

2. PCA 嘅目標同 Problem Formulation（Slide 3–4）

Slide 嘅定義：

The goal of PCA is to find a new set of attributes [called principal components (PCs), which are linear combinations of the original attributes] that better captures the variability of the data.

PCA 有三個好處（Appealing characteristics）：

1. 佢傾向搵出 data 入面最強嘅 patterns（strongest patterns）。
2. 好多時，一小部分（small fraction）新 attributes 已經可以捕捉到 data 大部分 variability。
3. 假設 noise 比 patterns 弱，捨棄最後嗰幾個 PCs 就可以去走大部分 noise（eliminate much of the noise）。

Problem formulation（Slide 4）：

• 任何兩個唔同嘅 PCs 之間 covariance 都係 0。
• 第一個 PC 要盡量捕捉最多 variability。
• 第二個 PC 要同第一個 PC orthogonal，喺呢個 constraint 之下再捕捉最多剩餘嘅 variability。
• 第 $k$ 個 PC 要同之前 $k-1$ 個 PCs orthogonal，喺呢個 constraint 之下再捕捉最多剩餘嘅 variability。

3. Mathematical Details：Eigen-decomposition of $S$（Slide 5–6）

Data matrix $D$ 係一個 $n \times p$ matrix，$n$ 係 observations 數目，$p$ 係 attributes 數目。Slide 嘅原句係：

PCA is ALL about eigen-decomposition of the sample covariance matrix $S$ of the data.

如果 $D$ 已經 preprocess 過，令每個 attribute 嘅 mean 都係 0（centering），咁：

跟住對 $S$ 做 eigen-decomposition（Slide 6）：

• $S$ 嘅 eigenvalues 係 $\lambda_1, \lambda_2, \dots, \lambda_p$，由大至細排列：$\lambda_1 \ge \lambda_2 \ge \dots \ge \lambda_p$。
• 對應嘅 eigenvectors 係 $v_1, v_2, \dots, v_p$。$(\lambda_i, v_i)$ 叫做第 $i$ 個 eigenpair。
• 第一個 PC 係 $D v_1$，第二個 PC 係 $D v_2$，如此類推。

每個 eigenvector $v_i$ 係一個 $p \times 1$ 嘅 weight vector。佢話你知原有 $p$ 個 attributes 每個佔幾多比重，所以 $D v_i$ 就係「原有 attributes 嘅 linear combination」，符合 Slide 3 嘅定義。

4. PC 嘅重要性質（Slide 7）

1. 任何兩個唔同嘅 PCs，covariance 都係 0（uncorrelated）。
2. 第 $i$ 個 PC 嘅 variance 等於 $\lambda_i$。
3. 原有 attributes 嘅 variance 總和等於 $\sum \lambda_i$，亦等於全部 PCs 嘅 variance 總和。所以 data 嘅 total variability 冇損失。
4. 最大 eigenvalue 對應嘅 eigenvector 指向 data variance 最大嘅方向（variance $= \lambda_1$）。第二大 eigenvalue 對應嘅 eigenvector 同第一個 orthogonal，指向剩餘 variance 最大嘅方向（variance $= \lambda_2$），如此類推。

Worked example（自製，用嚟理解）

以下係一個已經 centered 嘅細 dataset，$n = 4$，$p = 2$：

兩個 column 嘅 sum 都係 0，所以確實係 centered。Eigenvalues 由 $|S - \lambda I| = 0$ 求：$(\tfrac{10}{3}-\lambda)^2 = (\tfrac{8}{3})^2$，所以 $\lambda_1 = 6$，$\lambda_2 = \tfrac{2}{3}$。

對應嘅 unit eigenvectors 係 $v_1 = \tfrac{1}{\sqrt2}(1, 1)^T$ 同 $v_2 = \tfrac{1}{\sqrt2}(-1, 1)^T$。

• PC1 $= Dv_1 = \tfrac{1}{\sqrt2}(3, 3, -3, -3)^T$，佢嘅 variance 係 $\tfrac{1}{3}\cdot 4 \cdot \tfrac{9}{2} = 6 = \lambda_1$ ✔
• Total variance $= \tfrac{10}{3} + \tfrac{10}{3} = \tfrac{20}{3} = 6 + \tfrac{2}{3}$ ✔，total variability 冇損失。
• PC1 解釋嘅比例 $= \dfrac{6}{20/3} = 90\%$。如果準則係「保留 90% variability」，用 1 個 PC 就夠，即係由 2D 降到 1D。

5. 2D 例子（Slide 8）

Slide 用 1000 個 two-dimensional data points，展示 PCA transformation 之前同之後嘅樣。

6. 揀幾多個 PCs？Covariance 定 Correlation？（Slide 9）

原本有 $p$ 個 attributes，PCA 就可以產生 $p$ 個 PCs。做 data mining 時，通常只用頭幾個 PCs。至於要用幾多個，Slide 嘅答案係：It depends on your application. 一般有兩種方法：

1. Cumulative proportion of variance：保留足夠嘅 PCs，令佢哋捕捉到大部分 variability（例如 90%）：
   $$\text{揀最細嘅 } k \text{，令 } \frac{\lambda_1 + \dots + \lambda_k}{\lambda_1 + \dots + \lambda_p} \ge 0.9$$
2. Scree plot：x 軸係 PC 編號，y 軸係 $\lambda_i$（或者 proportion of variance），然後揀曲線出現 elbow（由急跌轉為平）嘅位置。Slide 註明詳情見 Tutorial 8。

例如 $\lambda = (4.0, 2.5, 0.8, 0.4, 0.3)$，total 係 8.0。Cumulative proportion 依次係 50%、81.25%、91.25%、96.25%、100%，所以用 90% 準則就揀 $k = 3$。Scree plot 喺 $\lambda_3$ 之後變平，elbow 大約喺第 3 個 PC，兩種方法嘅答案一致。

Correlation matrix $R$：如果 attributes 嘅 scale 同 variance 相差好遠，有時會用 $R$ 代替 $S$ 做 PCA。原因係 PCA 追求最大 variance，如果唔處理，scale 最大嗰個 attribute（例如以「元」計嘅收入，對比以「年」計嘅年齡）會霸佔 PC1。用 $R$ 做 PCA，等同先將每個 attribute 做 Z-score standardize，再用 $S$ 做 PCA。

# 參考用 scikit-learn 示範（唔係 lecture code）
from sklearn.preprocessing import StandardScaler
from sklearn.decomposition import PCA

Z = StandardScaler().fit_transform(X)      # 先 standardize，即係用 R 做 PCA
pca = PCA(n_components=0.90)               # 保留 90% variability
X_new = pca.fit_transform(Z)               # n × k
print(pca.explained_variance_)             # λ_1, λ_2, …
print(pca.explained_variance_ratio_.cumsum())
print(pca.components_)                     # 每一行係一個 eigenvector v_i

7. Singular Value Decomposition（Slide 10–12）

Slide 10 指出，只要每個 variable 嘅 mean 已經減咗，PCA 就同對 data matrix 做 SVD 係等價嘅。不過，從 SVD 角度理解 dimensionality reduction 都好有用，因為有時唔適合減 mean，特別係 data 比較 sparse 嘅時候。

SVD 直接分解 $n \times p$ 嘅 data matrix $D$（Slide 11）：

• $\sigma_i$：singular values，由大至細排列，放喺 diagonal matrix $\Sigma$。
• $V$ 嘅 columns $v_1, \dots, v_p$ 叫 right singular vectors。
• $U$ 嘅 columns 叫 left singular vectors。

要得到一個只有 $k$ 個 attributes 嘅新 data matrix（Slide 12），就用頭 $k$ 個 right singular vectors：

每一項 $\sigma_i u_i v_i^T$ 都係一個 rank-1 matrix。$D$ 係呢啲「層」疊加出嚟嘅結果，而 $\sigma_i$ 越大，嗰一層越重要。只保留頭 $k$ 層，就係保留最主要嘅結構。

8. SVD 嘅應用：Document Data（Slide 13）

• Document data 一般都係 sparse 嘅。
• Data matrix 係 document-term matrix：每一行係一份 document，每一列係一個 term（word）。
• 對 document-term matrix 做 SVD，可以睇到某類 documents 嘅「common terms」。

點解唔先減 mean？因為減 mean 之後，原本大量嘅 0 會變成非 0，matrix 就唔再 sparse，儲存同計算成本都會大增。所以 sparse data 會直接做 SVD，呢個亦係 Slide 10 講嘅原因。呢個方法喺 text mining 叫做 Latent Semantic Analysis (LSA)，scikit-learn 嘅實作係 TruncatedSVD。

9. Factor Analysis：概念同 Motivation（Slide 14–17）

同 PCA 嘅根本分別（Slide 14）：

• PCA / SVD：新 attributes 係原有 variables 嘅 linear combinations，即係 新 = f(舊)。
• FA：將原有 variables 表示成少量 hidden / latent attributes 嘅 linear combinations，即係 舊 = f(隱藏因素)。

Motivation 1（Slide 15）：有啲 data objects 嘅特徵好難直接量度（hard to measure directly），但似乎同一啲可以量度嘅特徵有關，例如：

• Intelligence 同各類 IQ tests 嘅表現。
• 運動員喺唔同項目嘅表現，同佢嘅 speed 同 strength。

如果可以搵到少量 attributes 去歸納原有 attributes，就可以同時做到 dimensionality reduction，又可以加深對 data 嘅理解。

Motivation 2（Slide 16）：亦可以從 covariance 或 correlation matrix 嘅角度理解。假設有一組 attributes 同其他 attributes 嘅 correlation 唔高，但組內嘅 attributes 之間 correlation 好強，可能係因為佢哋量度緊同一個 underlying quantity（latent variable）。咁樣就應該搵一個 underlying attribute 去總結每一組。

Decathlon 例子（Slide 17）：Decathlon（十項全能）有 10 個項目。著重 speed 嘅項目（100m、200m、400m……）之間，運動員嘅表現差唔多；著重 strength 嘅項目亦一樣。所以可以假設，運動員喺任何一個項目嘅表現，都係由項目本身嘅性質，加上 speed 同 strength 兩個 underlying factors 決定。Factor Analysis 就係要搵出呢種關係。

10. Factor Analysis 嘅 Mathematical Formulation（Slide 18–20）

設 $z = (z_1, z_2, \dots, z_p)$ 係 $p$ 個 standardized（Z-score normalized）observable variables：

設 $f_1, f_2, \dots, f_k$ 係 $k$ 個 latent / hidden factors。佢哋就係新 attributes，每個 object 都有自己嘅值。Slide 18 嘅 $k$-factor analysis model 係以圖片顯示。根據 Slide 19 嘅符號（$\lambda_{ij}$、$\epsilon_i$）同教科書，model 嘅形式係：

名詞解釋（Slide 19）：

名詞	意思
Common factors $f_j$	每個原有 attribute 嘅值都由全部 latent factors 共同決定，所以叫 common factors。
Factor loading $\lambda_{ij}$	第 $j$ 個 factor 對第 $i$ 個 attribute 嘅重要性。
Specific / unique factor $\epsilon_i$	Error term，代表第 $i$ 個 attribute 入面 common factors 解釋唔到嘅部分。

Slide 20：FA 會 estimate factor loadings，然後就可以 estimate 每個 observation 喺 latent factors 上嘅值。如果原本 data matrix $D$ 係 $n \times p$，新 data matrix $F$ 就係 $n \times k$。

Decathlon 例子：$z_{100m} \approx 0.9 f_{speed} + 0.1 f_{strength} + \epsilon$，$z_{shot\,put} \approx 0.1 f_{speed} + 0.85 f_{strength} + \epsilon$。睇 loadings 就知道每個 factor 代表咩意思（呢啲數字只係示意，唔係 slide 數據）。

自我測驗 Self-test

Q1. 用一句說話講 PCA 嘅目標，同埋列出佢三個 appealing characteristics。

搵一組新 attributes（principal components），佢哋係原有 attributes 嘅 linear combinations，而且更能捕捉 data 嘅 variability。三個 characteristics：(1) 傾向搵出 strongest patterns；(2) 一小部分新 attributes 已經可以捕捉大部分 variability；(3) 因為 noise 比 patterns 弱，可以去走大部分 noise。

Q2. 第二個 PC 要滿足咩條件？

同第一個 PC orthogonal（covariance 係 0），喺呢個 constraint 之下捕捉最多剩餘 variability。

Q3. Centered data 嘅 $D$ 係 $100 \times 5$。$S$ 嘅 size 係幾多？公式係咩？可以產生幾多個 PCs？

$S = \frac{1}{99} D^TD$，size 係 $5 \times 5$。可以產生 $p = 5$ 個 PCs。

Q4. $S$ 嘅 eigenvalues 係 $5, 3, 1.5, 0.5$。Total variance 係幾多？PC2 嘅 variance 係幾多？要保留 90% variability 需要幾多個 PCs？

Total variance $= 5 + 3 + 1.5 + 0.5 = 10$。PC2 嘅 variance $= \lambda_2 = 3$。Cumulative proportion 依次係 50%、80%、95%，所以需要 $k = 3$。

Q5. 幾時應該用 correlation matrix $R$ 代替 $S$ 做 PCA？點解？

當 attributes 嘅 scale 同 variance 相差好遠時。PCA 追求最大 variance，scale 大嘅 attribute 會霸佔頭幾個 PCs。用 $R$ 等同先將每個 attribute standardize，令每個 attribute 都有平等地位。

Q6. $D = U\Sigma V^T$ 入面，邊啲係 right singular vectors？點樣得到 $k$ 維嘅新 data？

$V$ 嘅 columns $v_1, \dots, v_p$ 係 right singular vectors，$U$ 嘅 columns 係 left singular vectors。新 data 係 $D_{SVD} = D[v_1, \dots, v_k]$，size 係 $n \times k$。

Q7. PCA 同 SVD 幾時等價？點解 document-term matrix 偏向直接用 SVD？

當每個 variable 嘅 mean 已經減咗，兩者就等價（$v_i$ 相同，$\lambda_i = \sigma_i^2/(n-1)$）。Document-term matrix 好 sparse，減 mean 之後大量 0 會變成非 0，破壞 sparsity，所以直接對 $D$ 做 SVD 會比較好。

Q8. PCA 同 Factor Analysis 喺「linear combination」方向上有咩分別？

PCA / SVD：新 attributes 係原有 variables 嘅 linear combinations。FA：原有 variables 表示成少量 latent factors 嘅 linear combinations（$z = \Lambda f + \epsilon$），方向啱啱相反。

Q9. 喺 FA model 入面，$\lambda_{ij}$、$f_j$ 同 $\epsilon_i$ 分別叫咩，代表咩？

$\lambda_{ij}$：factor loading，第 $j$ 個 factor 對第 $i$ 個 attribute 嘅重要性。$f_j$：common factor，即係 latent attribute。$\epsilon_i$：specific / unique factor，代表第 $i$ 個 attribute 入面 common factors 解釋唔到嘅部分。

Q10. 用 decathlon 解釋 FA 嘅 motivation。

10 個項目嘅表現睇得到，但 speed 同 strength 睇唔到。著重 speed 嘅項目之間表現相近，著重 strength 嘅項目亦一樣。所以可以假設每個項目嘅表現由項目性質加兩個 latent factors（speed、strength）決定。FA 可以將 10 個 variables 減到 2 個 factors，同時令人更了解 data。

一頁總結 Cheat sheet