Basic Linear Algebra : Principal Component Analysis

Principle Component Analysis (PCA) เป็น algorithm ที่ถูกหยิบมาใช้งานบ่อย โดยเฉพาะเรื่อง dimension reduction การทำความรู้จักกับ PCA ต้องอาศัยหลายเรื่องประกอบกัน ได้แก่ eigen vector, eigen value, covariance หรือ correlation matrix, diagonization of symmetric matrix เป็นต้น

ทบทวน

คุณสมบัติสำคัญของ symmetric matrix

1) ให้ A เป็น symmetric matrix ขนาด \( 3 \times 3 \), \( \begin{bmatrix}1&2&3\\2&1&3\\3&3&1 \end{bmatrix} \)

หา eigen values และ eigen vector มาเขียนคู่อันดับ \( (\lambda,\vec{v}) \) ได้เป็น \[ (6.3589, \begin{bmatrix} -0.5544\\-0.5544\\-0.6207 \end{bmatrix}), (-1.0000,\begin{bmatrix}-0.7071\\0.7071\\0.0000 \end{bmatrix}), (-2.3589, \begin{bmatrix}-0.4389\\-0.4389\\0.7840 \end{bmatrix}) \] จะเห็นว่า \( \lambda_1 \geq \lambda_2 \geq \lambda_3 \)

2) ถ้า V เป็น matrix ที่เกิดจากการนำเอา eigen vector ทำเป็น column vector แล้ว V เป็น orthogonal matrix พิสูจน์ได้จาก \( V^T \cdot V = I\) \[ \begin{align*} V &= \begin{bmatrix} 0.5544& -0.7071& -0.4389\\ -0.5544& 0.7071& -0.4389\\ -0.6207& 0.0000& 0.7840 \end{bmatrix} \\\\ V^T &= \begin{bmatrix} -0.5544& -0.5544& -0.6207\\ -0.7071& 0.7071& 0.0000\\ -0.4389& -0.4389& 0.7840 \end{bmatrix} \\\\ V^T \cdot V &= \begin{bmatrix} 1& 0& 0\\ 0& 1& 0\\ 0& 0& 1 \end{bmatrix} \end{align*} \]

เมื่อเราสนใจในสิ่งใดสิ่งหนึ่งและมีการเก็บข้อมูล เราสามารถเลือกรูปแบบในการจัดเก็บข้อมูลได้หลายแบบ แต่แบบที่สามารถนำมาใช้ทำ PCA ได้คือรูปแบบที่เรียกว่า matrix แต่ละ column เรียกว่า dimension หรือ feature แต่ละแถวเรียกว่า observation

ตัวอย่างข้อมูลจาก Iris dataset (https://archive.ics.uci.edu/ml/datasets/iris) มี 4 dimension มีจำนวน 150 observations เพื่อให้เห็นภาพง่าย จะนำมาเพียง 2 dimensions คือ Petal Length และ Petal Width มาสร้างเป็นเมตริกซ์ \( X \in \Re^{150 \times 2} \) \[ X = \begin{bmatrix} 1.4&0.2\\ 1.4&0.2\\ 1.3&0.2\\ 1.5&0.2\\ 1.4&0.2\\ 1.7&0.4\\ 1.4&0.3\\ 1.5&0.2\\ \vdots&\vdots \end{bmatrix} \]

หาค่ากลางของแต่ละ column vector (dimension) 0ได้เป็น \( \bar{X} = \begin{bmatrix}3.7587&1.1987 \end{bmatrix}\) นำไปลบออกจาก \( X \) \[ \begin{align*} X_c &= X - \bar{X} \\ X_c &= \begin{bmatrix} 1.4&0.2\\ 1.4&0.2\\ 1.3&0.2\\ 1.5&0.2\\ 1.4&0.2\\ 1.7&0.4\\ 1.4&0.3\\ 1.5&0.2\\ \vdots&\vdots \end{bmatrix} - \begin{bmatrix} 3.7587&1.1987\\ 3.7587&1.1987\\ 3.7587&1.1987\\ 3.7587&1.1987\\ 3.7587&1.1987\\ 3.7587&1.1987\\ 3.7587&1.1987\\ 3.7587&1.1987\\ \vdots&\vdots \end{bmatrix} \end{align*} \]

รูปที่ 1 แสดง scatter plot ของ X (ซ้ายมือ) และ \(X_c\) (ขวามือ)

\( X_c \) คือการย้ายตำแหน่ง (translation) \(X \) ให้มาอยู่ที่จุดศูนย์กลางเท่านั้น (to be central) ไม่มีการปรับแต่งค่าข้อมูล

สร้าง covariance matrix ของ \(X_c\) [4] \[ \begin{align*} \Sigma &= \frac{1}{150} X_c^T \cdot X_c \\\\ \Sigma &=\begin{bmatrix} 3.0924& 1.2877 \\ 1.2877& 0.5785 \end{bmatrix} \end{align*} \]

ข้อสังเกตุ : \(\Sigma \) เป็น symmetric matrix

หา eigen values และ eigen vector ของ \(\Sigma \) [2] นำมาเขียนเป็นคู่อันดับ ได้ดังนี้ \[ \begin{align*} (\lambda_1,\vec{v_1}) &= ( 3.6350,\begin{bmatrix}0.9215\\0.3883\end{bmatrix}) \\ (\lambda_2,\vec{v_2}) &= ( 0.0360,\begin{bmatrix}-0.3883\\0.9215\end{bmatrix}) \end{align*} \]

นำเอา eigen vector ทั้งสองมา plot ทับลงบน scatter plot ของ \( X_c \) ลูกศรสีแดงแทน eigen vector \( \vec{v_1} \) ลูกศรสีน้ำเงินแทน eigen vector \( \vec{v_2} \) (รูปที่ 2 ซ้ายมือ)

ขอให้สังเกตุว่าทิศทางของ eigen vector บอกทิศทางของ data variance [2] \( \vec{v_1} \) ชี้ไปในทางทีข้อมูลมี variation มากที่สุด ในขณะที่ \( \vec{v_2} \) ชีไปในทางทีข้อมูลมี variation น้อยกว่า

\[ \begin{bmatrix}0.9215\\0.3883\end{bmatrix}^T \cdot \begin{bmatrix}-0.3883\\0.9215\end{bmatrix} = 0 \] เมื่อนำเอา eigen vector ทั้งสองมาหา inner product ได้ค่าเป็น 0 นั่นคือ eigen vectors ตั้งฉากต่อกัน จึงถือว่าเป็นอิสระต่อกัน (lineary independent) สามารถนำมาใช้เป็น basis ของ vector space ใหม่ได้

ให้ \( V_\text{new} \) เราสามารถ project \( X_c \) ไปยัง vector space ที่มี eigen vector \(v_1,v_2 \) เป็น basis ได้โดยการทำ dot product ดังนี้ [7] \[ \begin{align*} V_{\text{new}} = X_c \cdot \begin{bmatrix}\vec{v_1}&\vec{v_2} \end{bmatrix} \tag{1} \end{align*} \]

รูปที่ 2 scatter plot ของ \( X_c\) ร่วมกับ eigen vector (ซ้ายมือ) และ scatter plot ของ \( X_c\) project บน eigen vectors

เมื่อเอา \( V_{\text{new}} \) มา plot ลงบน plane เดียวกับ \(X_c \) ผลที่ได้แสดงในรูปที่ 2 ขวามือ ซึ่งก็คือการหมุน (rotation) \( X_c \) ผลที่ตามมาจากการหมุนคือ \( V_{\text{new}} \) ไม่แสดง correlation ระหว่าง dimension เหมือนกับที่เห็นใน \(X_c \)

การเป็นอิสระต่อกันระหว่า diemension มีความสำคัญต่อการวิเคราะห์ข้อมูล dimension ที่มีความสัมพันธ์ต่อกันแสดงออกมาในค่า covariance เมื่อมีความสัมพันธ์ต่อกันแล้วการเปลี่ยนแปลงใน dimension หนึ่งจะส่งผลต่อ dimension อื่นด้วย ความหมายของ dimension มีการซ้อนทับกัน จึงมองว่าเป็นการดีที่จะทำการรวบ dimension ที่มีความสัมพันธ์ต่อกันเข้าด้วยกัน การรวมนี้จะเกิดขึ้นมากน้อยเพียงใดบอกได้จากค่าของ eigen values เมื่อนำมารวมกับ eigen vector ก็ทำให้เราทราบทั้งขนาดของการรวมและทิศทางของการรวม ข้อมูลเดิมที่ project ลงบน eigen vector ที่คู่กับ eigen value ที่มากที่สุดจะเรียกว่า first principal component ที่ project ลงบน eigen vector ที่มีค่า eigen value รองลงไปเรียก second principal component หากมี dimension มากกว่านี้ ก็จะเรียกแบบนี้ไปเรื่อย ๆ โดยจำนวน dimension ที่เกิดขึ้นใน vector space ใหม่นี้จะมีค่าไม่เกิน rank ของ \(X_c\)

สรุปขั้นตอนการทำงาน

1.ย้ายตำแหน่งข้อมูลมายังศูนย์กลาง (data translation) โดยการนำมาลบด้วยค่าเฉลี่ยของแต่ละ dimension
2. สร้าง covariance matrix (หรือใช้ correlation matrix ได้)
3. หา eigen value และ eigen vector จาก covariance matrix โดย eigen vector ที่มี eigen value มากที่สุดเรียกว่า first principal component
4. project ข้อมูลลงไป principal component มีผลเช่นเดียวกับการ rotate ข้อมูลตาม principal component ซึ่งก็คือ linear combination ระหว่างข้อมูลเดิมกับข้อมูลใหม่

ผลที่ได้ในขั้นตอนสุดท้ายคือข้อมูลที่อยู่ใน basis ใหม่ที่ข้อมูลมีการจัดลำดับความสำคัญที่วัดด้วยค่าของ variance นี่คือครึ่งทางแรกของเรื่อง PCA ในตอนต่อไปจะกล่าวถึงการนำเอาPCA ไปใช้ในการทำ dimension reduction หรือ feature extraction