principal component analysis la gi

Trong trang này:

• 1. Giới thiệu
• 2. Một chút toán
  • 2.1. Norm 2 của ma mãnh trận
  • 2.2. Biễu thao diễn vector trong những hệ hạ tầng không giống nhau
  • 2.3. Trace
  • 2.4. Kỳ vọng và ma mãnh trận hiệp phương sai
    • 2.4.1. Dữ liệu một chiều
    • 2.4.2. Dữ liệu nhiều chiều
• 3. Principal Component Analysis
• 4. Các bước triển khai PCA
• 5. Thảo luận
• 6. Tài liệu tham lam khảo

1. Giới thiệu

Dimensionality Reduction (giảm chiều dữ liệu), như và được nhắc một vài ba lượt nhập blog, là một trong những trong mỗi nghệ thuật cần thiết nhập Machine Learning. Các feature vectors trong những Việc thực tiễn rất có thể với số chiều rất rộng lớn, cho tới vài ba ngàn. Bên cạnh đó, con số những điểm tài liệu cũng thông thường rất rộng lớn. Nếu triển khai tàng trữ và đo lường thẳng bên trên tài liệu với số độ cao này thì tiếp tục gặp gỡ trở ngại cả về sự tàng trữ và vận tốc đo lường. Vì vậy, hạn chế số chiều tài liệu là một trong những bước cần thiết trong vô số nhiều Việc. Đây cũng khá được xem là một cách thức nén tài liệu.

Bạn đang xem: principal component analysis la gi

Dimensionality Reduction, phát biểu một cơ hội đơn giản và giản dị, là sự đi kiếm một hàm số, hàm số này lấy nguồn vào là một trong những điểm tài liệu ban sơ \(\mathbf{x} \in \mathbb{R}^D\) với \(D\) rất rộng lớn, và tạo nên một điểm tài liệu mới mẻ \(\mathbf{z} \in \mathbb{R}^K\) với số chiều \(K < D\).

Và như thông thường lệ, tôi tiếp tục trình diễn một cách thức đơn giản và giản dị nhất trong những thuật toán Dimensionality Reduction dựa vào một quy mô tuyến tính. Phương pháp này mang tên là Principal Component Analysis (PCA), tức Phân tích bộ phận chính. Phương pháp này dựa vào để ý rằng tài liệu thông thường ko phân bổ tình cờ nhập không khí tuy nhiên thường phân bổ ngay sát những đường/mặt đặc trưng nào là cơ. PCA đánh giá một tình huống đặc trưng Lúc những mặt mày đặc trưng cơ với dạng tuyến tính là những không khí con cái (subspace).

Bài viết lách này giành cho nhiều đối tượng người sử dụng người hâm mộ không giống nhau:

• Nếu bạn phải ôn tập dượt lại những kỹ năng và kiến thức về hệ song lập tuyến tính, kỳ vọng, phương sai, ma mãnh trận hiệp phương sai, chúng ta có thể hiểu Mục 2.

• Nếu mình thích hiểu xuất xứ, ý tưởng phát minh đứng sau PCA, vì sao PCA lại được triển khai như thế, chúng ta có thể tìm kiếm được ở Mục 3.

• Nếu các bạn không thích cút thâm thúy nhập toán tuy nhiên chỉ việc hiểu quá trình triển khai PCA, chúng ta có thể cho tới tức thì Mục 4.

• Nếu các bạn không thích hiểu quá trình triển khai tuy nhiên chỉ mong muốn biết hàm số triển khai PCA, một vài ba phần mềm của PCA, và rất có thể tăng những phần không ngừng mở rộng của PCA, chúng ta có thể thấy PCA phần 2 hữu ích, dự trù được trình làng tại đây một tuần.

• Nếu tôi là chúng ta, tôi tiếp tục hiểu không còn cả bài bác.

Trước Lúc cút nhập cụ thể của PCA, tất cả chúng ta nằm trong điểm lại một ít về Đại số tuyến tính và Thống kê.

2. Một chút toán

2.1. Norm 2 của ma mãnh trận

Chúng tớ vẫn thông thường nhắc nhiều cho tới norm mang lại vector tuy nhiên ko thực sự thao tác nhiều với norm của ma mãnh trận (ngoài Frobenius norm). Trong mục này, tất cả chúng ta tiếp tục thích nghi với một lớp những norm mang lại ma mãnh trận được khái niệm dựa vào norm của vector. Lớp những norms này còn được gọi là Induced Norms.

Giả sử hàm số \(||\mathbf{x}||_{\alpha}\) là một trong những norm ngẫu nhiên của vector \(\mathbf{x}\). Ứng với norm này, khái niệm norm ứng mang lại ma mãnh trận \(\mathbf{A}\): \[ ||\mathbf{A}||_{\alpha} = \max_{\mathbf{x}} \frac{||\mathbf{Ax}||_{\alpha}}{||\mathbf{x}||_{\alpha}} \]

chú ý rằng ma mãnh trận \(\mathbf{A}\) rất có thể ko vuông và số cột của chính nó vày với số chiều của \(\mathbf{x}\). Như vậy, bạn dạng thân thiện việc đo lường norm của ma mãnh trận là sự giải một Việc tối ưu. Chú ý rằng hàm tối ưu đối với cả tử số và khuôn số là những norm bên trên vectors.

Chúng tớ tiếp tục quan hoài nhiều hơn nữa cho tới norm 2. Norm 2 của ma mãnh trận được khái niệm là: \[ ||\mathbf{A}||_2 = \max_{\mathbf{x}} \frac{||\mathbf{Ax}||_2}{||\mathbf{x}||_2} ~~~ (1) \]

Nhận thấy rằng nếu như \(\mathbf{x}\) là nghiệm của Việc tối ưu \((1)\) thì \(k\mathbf{x}\) cũng chính là nghiệm với \(k\) là một số trong những thực không giống ko ngẫu nhiên. Không rơi rụng tính tổng quát tháo, tớ rất có thể fake sử khuôn số vày 1. Khi cơ, Việc tối ưu \((1)\) rất có thể được viết lách bên dưới dạng: \[ ||\mathbf{A}||_2 = \max_{||\mathbf{x}||_2 = 1} ||\mathbf{Ax}||_2 ~~~ (2) \] Nói cách tiếp theo, tớ cần thiết đi kiếm \(\mathbf{x}\) sao cho: \[ \begin{eqnarray} \mathbf{x} &=& \text{argmax}_{\mathbf{x}} ||\mathbf{Ax}||_2^2 & \newline \text{s.t.: } && ||\mathbf{x}||_2^2 = 1 & (3) \end{eqnarray} \] Ở trên đây, những norm 2 và được bình phương lên nhằm tách vết căn bậc nhị. Bài toán \((3)\) rất có thể được giải vày Phương pháp nhân tử Lagrange vì thế buộc ràng là một trong những phương trình.

Lagrangian của Bài toán \((3)\) là: \[ \mathcal{L}(\mathbf{x}, \lambda) = ||\mathbf{Ax}||_2^2 + \lambda (1 - ||\mathbf{x}||_2^2) \]

Nghiệm của Việc \((3)\) tiếp tục thoả mãn hệ phương trình: \[ \begin{eqnarray} \frac{\partial \mathcal{L}}{\partial \mathbf{x}} &=& 2\mathbf{A}^T\mathbf{Ax} - 2\lambda \mathbf{x} = \mathbf{0} & (4)\newline \frac{\partial \mathcal{L}}{\partial \lambda} &=& 1 - ||\mathbf{x}||_2^2 = 0 & (5) \end{eqnarray} \]

Từ \((4)\) tớ có: \[ \mathbf{A}^T\mathbf{Ax} = \lambda\mathbf{x} ~~~~ (6) \] Điều này suy đi ra rằng \(\lambda\) là một trong những trị riêng biệt của \(\mathbf{A}^T\mathbf{A}\) và \(\mathbf{x}\) là một trong những vector riêng biệt ứng với trị riêng biệt cơ. Tiếp tục nhân nhị vế của \((6)\) với \(\mathbf{x}^T\) nhập phía trái, tớ có: \[ \mathbf{x}^T\mathbf{A}^T\mathbf{Ax} = \lambda \mathbf{x}^T\mathbf{x} = \lambda \] Nhận thấy rằng vế trái ngược đó là \(||\mathbf{Ax}||_2^2\) đó là hàm tiềm năng nhập \((3)\). Vậy hàm tiềm năng đạt độ quý hiếm rộng lớn nhất lúc \(\lambda\) đạt độ quý hiếm lớn số 1. Nói cách tiếp theo, \(\lambda\) đó là trị riêng biệt lớn số 1 của \(\mathbf{A}^T\mathbf{A}\) hoặc đó là singular value lớn số 1 của ma mãnh trận \(\mathbf{A}\).

Như vậy, norm 2 của một ma mãnh trận đó là singular value lớn số 1 của ma mãnh trận cơ. Và nghiệm của Việc \((3)\) chủ yếu một là right-singular vector ứng với singular value cơ.

Với lý luận tương tự động, tất cả chúng ta rất có thể suy đi ra rằng bài bác toán: \[ \min_{||\mathbf{x}||_2 =1} \mathbf{x}^T\mathbf{A}^T\mathbf{A}\mathbf{x} \]

có nghiệm là vector riêng biệt ứng với trị riêng biệt nhỏ nhất của \(\mathbf{A}^T\mathbf{A}\). Khi cơ, hàm số đạt độ quý hiếm nhỏ nhất vày chủ yếu trị riêng biệt nhỏ nhất này.

2.2. Biễu thao diễn vector trong những hệ hạ tầng không giống nhau

Trong không khí \(D\) chiều , toạ phỏng của từng điểm được xác lập dựa vào một hệ toạ phỏng nào là cơ. Tại những hệ toạ phỏng không giống nhau, phân biệt là toạ phỏng của từng điểm cũng không giống nhau.

Tập phù hợp những vector \(\mathbf{e}_1, \dots, \mathbf{e}_D\) tuy nhiên từng vector \(\mathbf{e}_d\) với đích một trong những phần tử không giống 0 ở bộ phận loại \(d\) và thành phần cơ vày 1, được gọi là hệ hạ tầng đơn vị chức năng (hoặc hệ đơn vị) nhập không khí \(D\) chiều. Nếu xếp những vector \(\mathbf{e}_d, d = 1, 2, \dots, D\) theo như đúng trật tự cơ, tớ sẽ tiến hành ma mãnh trận đơn vị chức năng \(D\) chiều.

Mỗi vector cột \(\mathbf{x} = [x_1, x_2, \dots, x_D] \in \mathbb{R}^D\), màn trình diễn của chính nó nhập hệ đơn vị chức năng là:

\[ \mathbf{x} = x_1 \mathbf{e}_1 + x_2 \mathbf{e}_2 + \dots + x_D\mathbf{e}_D \]

Giả sử với cùng 1 hệ hạ tầng không giống \(\mathbf{u}_1, \mathbf{u}_2, \dots, \mathbf{u}_D\) (các vector này song lập tuyến tính), vậy thì màn trình diễn của vector \(\mathbf{x}\) nhập hệ hạ tầng mới mẻ này còn có dạng:

\[ \mathbf{x} = y_1 \mathbf{u}_1 + y_2 \mathbf{u}_2 + \dots + y_D\mathbf{u}_D = \mathbf{U}\mathbf{y} \]

\(\mathbf{U}\) là ma mãnh trận tuy nhiên cột loại \(d\) của chính nó đó là vector \(\mathbf{u}_d\). Lúc này, vector \(\mathbf{y}\) đó là màn trình diễn của \(\mathbf{x}\) nhập hệ hạ tầng mới mẻ. Sở những số \(y_d, d = 1, 2, \dots, D\) là có một không hai vì thế \(\mathbf{y}\) rất có thể tính được bằng: \[ \mathbf{y} = \mathbf{U}^{-1} \mathbf{x} ~~~ (7) \] với để ý rằng \(\mathbf{U}\) là ma mãnh trận khả nghịch ngợm vì thế những cột của chính nó song lập tuyến tính.

Trong những ma mãnh trận vào vai trò như hệ hạ tầng \(\mathbf{U}\), những ma mãnh trận trực gửi gắm, tức \(\mathbf{U}^T\mathbf{U} = \mathbf{I}\), được quan hoài nhiều hơn nữa vì thế nghịch ngợm hòn đảo của bọn chúng đó là gửi vị của chúng:

\[ \mathbf{U}^{-1} = \mathbf{U}^T \] Khi cơ, \(\mathbf{y}\) nhập \((7)\) rất có thể được xem một cơ hội thời gian nhanh chóng:

\[ \mathbf{y} = \mathbf{U}^{T} \mathbf{x} \] từ cơ suy ra: \(y_i = \mathbf{x}^T \mathbf{u}_i = \mathbf{u}_i^T\mathbf{x}, i= 1, 2, \dots, D\).

Có thể nhận biết rằng vector \(\mathbf{0}\) được màn trình diễn như nhau vào cụ thể từng hệ hạ tầng. Hình 1 bên dưới đó là 1 ví dụ về sự gửi hệ cơ sở:

Hình 1: Chuyển thay đổi toạ phỏng trong những hệ hạ tầng không giống nhau.

Việc quy đổi hệ hạ tầng dùng ma mãnh trận trực gửi gắm rất có thể được xem như 1 quy tắc xoay trục toạ phỏng. Nhìn theo dõi một cách tiếp theo, đó cũng đó là một quy tắc xoay vector tài liệu theo hướng ngược lại.

2.3. Trace

Hàm số trace xác lập bên trên tập dượt những ma mãnh trận vuông được dùng thật nhiều nhập tối ưu vì thế những đặc điểm đẹp nhất của chính nó. Hàm trace trả về tổng những thành phần bên trên lối chéo cánh của một ma mãnh trận vuông.

Các đặc điểm cần thiết của hàm trace, với fake sử rằng những ma mãnh trận nhập hàm trace là vuông và những quy tắc nhân ma mãnh trận triển khai được:

• \(\text{trace}(\mathbf{A}) = \text{trace}(\mathbf{A}^T)\)

• \(\text{trace}(k\mathbf{A}) = k\text{trace}(\mathbf{A})\) với \(k\) là một số trong những ngẫu nhiên.

• \(\text{trace}(\mathbf{AB}) = \text{trace}(\mathbf{BA})\)

• \(||\mathbf{A}||_F^2 = \text{trace}(\mathbf{A}^T\mathbf{A}) = \text{trace}(\mathbf{A}\mathbf{A}^T)\) với \(\mathbf{A}\) là ma mãnh trận ngẫu nhiên, rất có thể ko vuông.

• \(\text{trace}(\mathbf{A}) = \sum_{i = 1}^D \lambda_i \) với \(\mathbf{A}\) là một trong những ma mãnh trận vuông và \(\lambda_i, i = 1, 2, \dots, N\) là toàn cỗ những trị riêng biệt của chính nó, rất có thể phức hoặc lặp. Việc minh chứng đặc điểm này rất có thể được dựa vào ma mãnh trận đặc thù của \(\mathbf{A}\) và ấn định lý Viète. Tôi xin xỏ được bỏ lỡ.

2.4. Kỳ vọng và ma mãnh trận hiệp phương sai

2.4.1. Dữ liệu một chiều

Cho \(N\) độ quý hiếm \(x_1, x_2, \dots, x_N\). Kỳ vọng và phương sai của cục tài liệu này được khái niệm là:

\[ \begin{eqnarray} \bar{x} &=& \frac{1}{N}\sum_{n=1}^N x_n = \frac{1}{N}\mathbf{X1}\newline \sigma^2 &=& \frac{1}{N} \sum_{n=1}^N (x_n - \bar{x})^2 \end{eqnarray} \] với \(\mathbf{1} \in \mathbb{R}^N\) là vector cột chứa chấp toàn thành phần 1. Kỳ vọng đơn giản và giản dị là khoảng nằm trong của toàn cỗ những độ quý hiếm. Phương sai là khoảng nằm trong của bình phương khoảng cách kể từ từng điểm cho tới kỳ vọng. Phương sai càng nhỏ thì những điểm tài liệu càng ngay sát với kỳ vọng, tức những điểm tài liệu càng giống như nhau. Phương sai càng rộng lớn thì tớ phát biểu tài liệu càng với tính phân giã. Ví dụ về kỳ vọng và phương sai của tài liệu một chiều rất có thể được thấy nhập Hình 2a).

Căn bậc nhị của phương sai, \(\sigma\) còn được gọi là phỏng nghiêng chuẩn chỉnh (standard deviation) của tài liệu.

2.4.2. Dữ liệu nhiều chiều

Cho \(N\) điểm tài liệu được màn trình diễn vày những vector cột \(\mathbf{x}_1, \dots, \mathbf{x}_N\), Lúc cơ, vector kỳ vọng và ma trận hiệp phương sai của toàn cỗ tài liệu được khái niệm là:

\[ \begin{eqnarray} \bar{\mathbf{x}} &=& \frac{1}{N} \sum_{n=1}^N \mathbf{x}_n \newline \mathbf{S} &=& \frac{1}{N}\sum_{n=1}^N (\mathbf{x}_n - \bar{\mathbf{x}})(\mathbf{x}_n - \bar{\mathbf{x}})^T = \frac{1}{N}\hat{\mathbf{X}}\hat{\mathbf{X}}^T \end{eqnarray} \] Trong cơ \(\hat{\mathbf{X}}\) được tạo nên bằng phương pháp trừ từng cột của \(\mathbf{X}\) cút \(\bar{\mathbf{x}}\): \[ \hat{\mathbf{x}}_n = \mathbf{x}_n - \bar{\mathbf{x}} \]

Các công thức này khá tương đương với những công thức mang lại tài liệu một chiều phía bên trên. Có một vài ba điểm lưu ý:

• Ma trận hiệp phương sai là một trong những ma mãnh trận đối xứng, không chỉ có vậy, nó là một trong những ma mãnh trận nửa xác lập dương.

• Mọi thành phần bên trên lối chéo cánh của ma mãnh trận hiệp phương sai là những số ko âm. Chúng cũng đó là phương sai của từng chiều của tài liệu.

  Xem thêm: service pack là gì

• Các thành phần ngoài lối chéo cánh \(s_{ij}, i \neq j\) thể hiện nay sự đối sánh thân thiện bộ phận loại \(i\) và loại \(j\) của tài liệu, còn được gọi là hiệp phương sai. Giá trị này rất có thể dương, âm hoặc vày 0. Khi nó vày 0, tớ bảo rằng nhị bộ phận \(i, j\) nhập tài liệu là ko đối sánh (uncorrelated).

• Nếu ma mãnh trận hiệp phương sai là ma mãnh trận lối chéo cánh, tớ với tài liệu trọn vẹn ko đối sánh trong số những chiều.

Ví dụ về tài liệu ko đối sánh và đối sánh được mang lại nhập Hình 2bc).

3. Principal Component Analysis

Cách đơn giản và giản dị nhất nhằm hạn chế chiều tài liệu kể từ \(D\) về \(K < D\) là chỉ hội tụ lại \(K\) thành phần quan trọng nhất. Tuy nhiên, việc thực hiện này chắc chắn rằng không hẳn rất tốt vì thế tất cả chúng ta không biết xác lập bộ phận nào là là cần thiết rộng lớn. Hoặc nhập tình huống xấu xa nhất, lượng vấn đề tuy nhiên từng bộ phận đem là như nhau, loại bỏ đi bộ phận nào thì cũng dẫn theo việc rơi rụng một lượng vấn đề rộng lớn.

Tuy nhiên, nếu như tất cả chúng ta rất có thể màn trình diễn những vector tài liệu ban sơ nhập một hệ hạ tầng mới mẻ tuy nhiên trong hệ hạ tầng mới mẻ cơ, tầm quan liêu trọng trong số những bộ phận là không giống nhau rõ ràng rệt, thì tất cả chúng ta rất có thể bỏ lỡ những bộ phận không nhiều cần thiết nhất.

Lấy một ví dụ về sự với nhị camera đặt điều người sử dụng để có thể chụp một quả đât, một camera đặt điều phía đằng trước người và một camera đặt điều bên trên đầu. Rõ ràng là hình hình họa chiếm được kể từ camera đặt điều phía đằng trước người đem nhiều vấn đề rộng lớn đối với hình hình họa nom kể từ phía bên trên đầu. Vì vậy, tấm hình chụp kể từ phía bên trên đầu rất có thể được bỏ lỡ tuy nhiên không tồn tại rất nhiều vấn đề về dáng vẻ của những người cơ bị rơi rụng.

PCA đó là cách thức đi kiếm một hệ hạ tầng mới mẻ sao mang lại vấn đề của tài liệu đa phần triệu tập ở một vài ba toạ phỏng, phần sót lại chỉ mang trong mình 1 lượng nhỏ vấn đề. Và làm cho đơn giản và giản dị nhập đo lường, PCA tiếp tục tìm hiểu một hệ trực chuẩn chỉnh nhằm thực hiện hạ tầng mới mẻ.

Giả sử hệ hạ tầng trực chuẩn chỉnh mới mẻ là \(\mathbf{U}\) và tất cả chúng ta mong muốn hội tụ lại \(K\) toạ phỏng nhập hệ hạ tầng mới mẻ này. Không rơi rụng tính tổng quát tháo, fake sử này đó là \(K\) bộ phận trước tiên. Quan sát Hình 3 bên dưới đây:

Hình 3: Ý tưởng chủ yếu của PCA: Tìm một hệ trực chuẩn chỉnh mới mẻ sao mang lại nhập hệ này, những bộ phận cần thiết nhất trực thuộc \(K\) bộ phận trước tiên.

Quan sát hình vẽ bên trên với hạ tầng mới mẻ \(\mathbf{U} = [\mathbf{U}_K, \bar{\mathbf{U}}_K]\) là một trong những hệ trực chuẩn chỉnh với \(\mathbf{U}_K\) là ma mãnh trận hoá công vày \(K\) cột trước tiên của \(\mathbf{U}\). Với hạ tầng mới mẻ này, ma mãnh trận tài liệu rất có thể được viết lách thành: \[ \mathbf{X} = \mathbf{U}_K \mathbf{Z} + \bar{\mathbf{U}}_K \mathbf{Y} ~~~~ (8) \] Từ trên đây tớ cũng suy ra:

\[ \begin{eqnarray} \left[ \begin{matrix} \mathbf{Z} \newline \mathbf{Y} \end{matrix} \right] = \left[ \begin{matrix} \mathbf{U}_K^T \newline \bar{\mathbf{U}}_K^T \end{matrix} \right]\mathbf{X} \Rightarrow \begin{matrix} \mathbf{Z} = \mathbf{U}_K^T \mathbf{X} \newline \mathbf{Y} = \bar{\mathbf{U}}_K^T\mathbf{X} \end{matrix} \end{eqnarray} ~~~~ (9) \]

Mục đích của PCA là đi kiếm ma mãnh trận trực gửi gắm \(\mathbf{U}\) sao mang lại phần rộng lớn vấn đề được hội tụ lại ở đoạn greed color \(\mathbf{U}_K \mathbf{Z}\) và phần red color \(\bar{\mathbf{U}}_K\mathbf{Y}\) sẽ tiến hành lược quăng quật và thay cho vày một ma mãnh trận ko tùy thuộc vào từng điểm tài liệu. Nói cách tiếp theo, tớ tiếp tục xấp xỉ \(\mathbf{Y}\) vày một ma mãnh trận với toàn cỗ những cột là như nhau. Chú ý rằng những cột này rất có thể tùy thuộc vào tài liệu training tuy nhiên ko tùy thuộc vào tài liệu test, những các bạn sẽ thấy rõ ràng rộng lớn Lúc lập trình sẵn tuy nhiên tôi tiếp tục trình diễn nhập bài bác tiếp theo. Gọi từng cột này đó là \(\mathbf{b}\) và rất có thể coi nó là bias, Lúc cơ, tớ tiếp tục xấp xỉ:

\[ \mathbf{Y} \approx \mathbf{b1}^T \] Trong cơ \(\mathbf{1}^T\in \mathbb{R}^{1 \times N}\) là vector mặt hàng với toàn cỗ những thành phần vày 1. Giả sử đang được tìm kiếm được \(\mathbf{U}\), tớ cần thiết tìm hiểu \(\mathbf{b}\) thoả mãn: \[ \mathbf{b} = \text{argmin}_{\mathbf{b}} ||\mathbf{Y} - \mathbf{b1}^T||_F^2 = \text{argmin}_{\mathbf{b}} ||\bar{\mathbf{U}}_K^T\mathbf{X} - \mathbf{b1}^T||_F^2 \]

Giải phương trình đạo hàm theo dõi \(\mathbf{b}\) của hàm tiềm năng vày 0: \[ (\mathbf{b1}^T - \bar{\mathbf{U}}_K^T\mathbf{X})\mathbf{1} = 0 \Rightarrow N\mathbf{b} = \bar{\mathbf{U}}_K^T \mathbf{X1} \Rightarrow \mathbf{b} = \bar{\mathbf{U}}_K^T \bar{\mathbf{x}} \]

Như vậy, việc đo lường tiếp tục thuận tiện rất nhiều nếu như vector kỳ vọng \(\bar{\mathbf{x}} = \mathbf{0}\). Việc này rất có thể đạt được nếu như tức thì từ trên đầu, tất cả chúng ta trừ từng vector tài liệu cút vector kỳ vọng của toàn cỗ tài liệu. Đây đó là quá trình trước tiên của PCA.

Với độ quý hiếm \(\mathbf{b}\) tìm kiếm được này, tài liệu ban sơ sẽ tiến hành xấp xỉ với:

\[ \mathbf{X} \approx \tilde{\mathbf{X}} = \mathbf{U}_K \mathbf{Z} + \bar{\mathbf{U}}_K \bar{\mathbf{U}}_K^T\bar{\mathbf{x}}\mathbf{1}^T ~~~ (10) \]

Kết phù hợp \((8), (9), (10)\) tớ khái niệm hàm rơi rụng non chủ yếu như sau: \[ J = \frac{1}{N} || \mathbf{X} - \tilde{\mathbf{X}}||_F^2 = \frac{1}{N} ||\bar{\mathbf{U}}_K \bar{\mathbf{U}}_K^T \mathbf{X} - \bar{\mathbf{U}}_K \bar{\mathbf{U}}_K^T \bar{\mathbf{x}}\mathbf{1}^T||_F^2 ~~~~ (11) \]

Chú ý rằng, nếu như những cột của một ma mãnh trận \(\mathbf{V}\) tạo nên trở nên một hệ trực chuẩn chỉnh thì với cùng 1 ma mãnh trận \(\mathbf{W}\) ngẫu nhiên, tớ luôn luôn có: \[ ||\mathbf{VW}||_F^2 = \text{trace} (\mathbf{W}^T\mathbf{V}^T\mathbf{V} \mathbf{W}) = \text{trace}(\mathbf{W}^T\mathbf{W}) = ||\mathbf{W}||_F^2 \]

Vì vậy hàm rơi rụng non nhập \((11)\) rất có thể viết lách lại thành: \[ \begin{eqnarray} J &=& \frac{1}{N} || \bar{\mathbf{U}}_K^T (\mathbf{X} - \bar{\mathbf{x}}\mathbf{1})^T||_F^2 = \frac{1}{N} ||\bar{\mathbf{U}}_K^T\hat{\mathbf{X}} ||_F^2& \newline &=& \frac{1}{N} ||\hat{\mathbf{X}}^T \bar{\mathbf{U}}_K ||_F^2 = \frac{1}{N}\sum_{i = K+1}^D ||\hat{\mathbf{X}}^T\mathbf{u}_i ||_2^2& \newline &=& \frac{1}{N} \sum_{i=K+1}^D \mathbf{u}_i^T\hat{\mathbf{X}}\hat{\mathbf{X}}^T \mathbf{u}_i& \newline &=& \sum_{i=K+1}^D \mathbf{u}_i^T\mathbf{S} \mathbf{u}_i & (12) \end{eqnarray} \]

Với \(\hat{\mathbf{X}} = \mathbf{X} - \bar{\mathbf{x}}\mathbf{1}^T\) là tài liệu đang được chuẩn chỉnh hoá và với \(\mathbf{S}\) là ma mãnh trận hiệp phương sai của tài liệu. Ta gọi ma mãnh trận này \(\hat{\mathbf{X}}\) là zero-corrected data hoặc dữ liệu và được chuẩn chỉnh hoá. cũng có thể nhận biết \(\hat{\mathbf{x}}_n = \mathbf{x}_n - \bar{\mathbf{x}}\).

Công việc sót lại là tìm hiểu những \(\mathbf{u}_i\) nhằm rơi rụng non là nhỏ nhất. Trước không còn, tất cả chúng ta với cùng 1 phán xét thú vị. Nhắc lại khái niệm ma mãnh trận hiệp phương sai \(\mathbf{S} = \frac{1}{N} \hat{\mathbf{X}}^T\hat{\mathbf{X}}\). Với ma mãnh trận \(\mathbf{U}\) trực gửi gắm ngẫu nhiên, thay cho \(K = 0\) nhập \((12)\) tớ có:

\[ \begin{eqnarray} L &=& \sum_{i=1}^D \mathbf{u}_i^T\mathbf{Su}_i = \frac{1}{N} ||\hat{\mathbf{X}}^T\mathbf{U}||_F^2 \newline &=& \frac{1}{N} \text{trace}(\hat{\mathbf{X}}^T\mathbf{U} \mathbf{U}^T \hat{\mathbf{X}}) & (12) \newline &=& \frac{1}{N} \text{trace} (\hat{\mathbf{X}}^T \hat{\mathbf{X}}) & (13) \newline &=& \frac{1}{N} \text{trace} (\hat{\mathbf{X}} \hat{\mathbf{X}}^T) & (14) \newline &=& \text{trace} (\mathbf{S}) = \sum_{i=1}^D \lambda_i & (16) \end{eqnarray} \]

Với \(\lambda_1 \geq \lambda_2 \geq \dots \geq \lambda_D \geq 0\) là những trị riêng biệt của ma mãnh trận nửa xác lập dương \(\mathbf{S}\). Chú ý rằng những trị riêng biệt này là thực và ko âm.

Như vậy \(L\) ko tùy thuộc vào cơ hội lựa chọn ma mãnh trận trực gửi gắm \(\mathbf{U}\) và vày tổng những thành phần bên trên lối chéo cánh của \(\mathbf{S}\). Nói cách tiếp theo, \(L\) đó là tổng của những phương sai theo dõi từng bộ phận của tài liệu ban sơ.

Vì vậy, việc ít nhất hàm rơi rụng non \(J\) được mang lại vày \((13)\) tương tự với việc tối đa: \[ F = L - J = \sum_{i=1}^K \mathbf{u}_i \mathbf{S} \mathbf{u}_i^T \]

Định lý 1: \(F\) đạt độ quý hiếm lớn số 1 vày \(\sum_{i=1}^K \lambda_i\) Lúc \(\mathbf{u}_i\) là những vector riêng biệt với norm 2 vày 1 ứng với những trị riêng biệt này. Tất nhiên, tất cả chúng ta luôn nhớ ĐK trực gửi gắm trong số những \(\mathbf{u}_i\).

Chú ý rằng \(\lambda_i, i = 1, \dots, K\) đó là \(K\) trị riêng biệt lớn số 1 của ma mãnh trận hiệp phương sai \(\mathbf{S}\). Trị riêng biệt lớn số 1 \(\lambda_1\) của ma mãnh trận này còn được gọi là Thành phần chủ yếu loại nhất (First Principal Component), trị riêng biệt loại nhị \(\lambda_2\) còn được gọi là Thành phần chủ yếu loại hai, etc. Chính chính vì vậy, cách thức này mang tên gọi là Phân tích bộ phận chính - Principal Component Analysis. Ta chỉ hội tụ lại \(K\) bộ phận chủ yếu của tài liệu Lúc mong muốn hạn chế số chiều tài liệu. Để với ánh nhìn trực quan liêu rộng lớn, tất cả chúng ta nằm trong theo dõi dõi Hình bên dưới đây:

Hình 4: PCA bên dưới tầm nhìn Thống kê. PCA rất có thể được xem là cách thức đi kiếm một hệ hạ tầng trực chuẩn chỉnh vào vai trò một quy tắc xoay, sao mang lại nhập hệ hạ tầng mới mẻ này, phương sai theo dõi một số trong những chiều nào là này đó là rất rất nhỏ, và tớ rất có thể bỏ lỡ.

Trong không khí ban sơ với những vector hạ tầng black color \(\mathbf{e}_1, \mathbf{e}_2\), phương sai theo dõi từng chiều tài liệu đều rộng lớn. Trong không khí mới mẻ với những vector hạ tầng red color \(\mathbf{u}_1, \mathbf{u}_2\), phương sai theo hướng loại nhị \(\hat{\sigma}_2\) rất rất nhỏ đối với \(\hat{\sigma}_1\). Như vậy nghĩa là lúc chiếu tài liệu lên \(\mathbf{u}_2\) tớ được những điểm rất rất ngay sát nhau và ngay sát với kỳ vọng theo hướng cơ. Trong tình huống này, kỳ vọng theo dõi từng chiều vày 0 nên tớ rất có thể thay cho thế toạ phỏng theo hướng \(\mathbf{u}_2\) vày 0. Rõ ràng là nếu như tài liệu với phương sai càng nhỏ theo dõi một chiều nào là cơ thì Lúc xấp xỉ chiều cơ vày một hằng số, sai số xẩy ra càng nhỏ. PCA thực tế là đi kiếm một quy tắc xoay ứng với cùng 1 ma mãnh trận trực gửi gắm sao mang lại nhập hệ toạ phỏng mới mẻ, tồn bên trên những chiều với phương sai nhỏ tuy nhiên tớ rất có thể quăng quật qua; tớ chỉ việc hội tụ lại những chiều/thành phần không giống cần thiết rộng lớn. Như đang được minh chứng phía trên, tổng phương sai theo dõi từng chiều nhập hệ hạ tầng nào thì cũng là như nhau và vày tổng những trị riêng biệt của ma mãnh trận hiệp phương sai. Vì vậy, PCA còn được xem là cách thức hạn chế số chiều tài liệu tuy nhiên tạo được tổng phương sai sót lại là lớn số 1.

Tôi tiếp tục bỏ lỡ phần minh chứng của Định lý 1. Tuy nhiên, cũng nêu một vài ba ý nhằm độc giả rất có thể hình dung:

Khi \(K = 1\). Ta cần thiết giải bài bác toán: \[ \begin{eqnarray} \max_{\mathbf{u}_1} &\mathbf{u}_1^T\mathbf{S} \mathbf{u}_1 \newline \text{s.t.:} &||\mathbf{u}_1||_2 = 1 \end{eqnarray} \]

Như đang được nhắc ở phía bên trên, hàm tiềm năng đạt độ quý hiếm lớn số 1 vày \(\lambda_1\) Lúc \(\mathbf{u}_1\) là một trong những vector riêng biệt của ma mãnh trận hiệp phương sai \(\mathbf{S}\) ứng với trị riêng biệt \(\lambda_1\). Vậy ấn định lý đích với \(K = 1\)

Giả sử \(\mathbf{u}_1\) đang được là vector riêng biệt ứng với trị riêng biệt lớn số 1 của \(\mathbf{S}\) thế thì nghiệm \(\mathbf{u}_2\) của Việc tối ưu: \[ \begin{eqnarray} \max_{\mathbf{u}_2} &\mathbf{u}_2^T\mathbf{S} \mathbf{u}_2 &\newline \text{s.t.} &||\mathbf{u}_2||_2 = 1 & (21)\newline & \mathbf{u}_2^T \mathbf{u}_1 = 0 & \end{eqnarray} \] là một vector riêng biệt của \(\mathbf{S}\) ứng với trị riêng biệt rộng lớn loại nhị \(\lambda_2\) của chính nó. Chú ý rằng \(\lambda_2\) rất có thể vày \(\lambda_1\) nếu như không khí riêng biệt ứng với \(\lambda_1\) với số rank to hơn 1.

Nhận ấn định này rất có thể được minh chứng vày cách thức nhân tử Lagrange. Thật vậy, Lagrangian của Việc \((21)\) là: \[ \mathcal{L}( \mathbf{u}_2, \nu_1, \nu_2) = \mathbf{u}_2^T\mathbf{S} \mathbf{u}_2 + \nu_1\mathbf{u}_1^T\mathbf{u}_2 + \nu_2(1 - \mathbf{u}_2^T\mathbf{u}_2) \]

Ta cần thiết giải hệ phương trình đạo hàm của \(\mathcal{L}\) theo dõi từng đổi mới vày 0: \[ \begin{eqnarray} \frac{\partial \mathcal{L}}{\partial \mathbf{u}_2} &=& 2 \mathbf{Su}_2 + \nu_1 \mathbf{u}_1 - 2\nu_2\mathbf{u}_2 = 0 & (22)\newline \frac{\partial \mathcal{L}}{\partial \nu_1} &=& \mathbf{u}_1^T \mathbf{u}_2 = 0 & (23)\newline \frac{\partial \mathcal{L}}{\partial \nu_2} &=& 1 - \mathbf{u}_2^T \mathbf{u}_2 = 0 &(24)\newline \end{eqnarray} \]

Nhân cả nhị vế của \((22)\) với \(\mathbf{u}_1^T\) nhập phía trái tớ có: \[ 2\mathbf{u}_1^T\mathbf{Su}_2 + \nu_1 = 0 \] Vì \(\mathbf{Su}_1 = \lambda_1 \mathbf{u}_1 \Rightarrow \mathbf{u}_1^T\mathbf{Su}_2 = \lambda_1 \mathbf{u}_1^T\mathbf{u}_2 = 0\). Từ cơ suy đi ra \(\nu_1 = 0\) và \((22)\) thời điểm này tương tự với: \[ \mathbf{Su}_2 = \nu_2\mathbf{u}_2 \Rightarrow \mathbf{u}_2^T\mathbf{S} \mathbf{u}_2 = \nu_2 \] Vậy \(\mathbf{u}_2\) là một trong những vector riêng biệt của \(\mathbf{S}\) ứng với \(\nu_2\). Và nhằm hàm tiềm năng đạt độ quý hiếm lớn số 1, \(\nu_2\) cần thiết càng rộng lớn càng chất lượng tốt. Như vậy dẫn theo \(\nu_2\) cần là trị riêng biệt loại nhị của \(\mathbf{S}\).

Lập luận tương tự động, tớ rất có thể minh chứng được: Nếu \(\mathbf{u}_i, i = 1, 2, \dots, k-1\) là những vector riêng biệt ứng với trị riêng biệt rộng lớn loại \(i\) của ma mãnh trận nửa xác lập dương \(\mathbf{S}\), không chỉ có vậy, \(k-1\) vector riêng biệt này tạo nên trở nên một hệ trực chuẩn chỉnh, thế thì:

\[ \begin{eqnarray} \max_{\mathbf{u}_k} & \mathbf{u}_k^T\mathbf{Su}_k \newline \text{s.t.} & \mathbf{u}_k^T\mathbf{u}_k = 1; \newline & \mathbf{u}_k^T\mathbf{u}_i = 1, i = 1,\dots, k -1 \end{eqnarray} \] bằng đích với trị riêng biệt tiếp sau \(\lambda_k\) bên trên \(\mathbf{u}_k\) là vector riêng biệt ứng với trị riêng biệt này.

4. Các bước triển khai PCA

Từ những tư duy phía bên trên, tớ rất có thể tóm lược lại quá trình nhập PCA như sau:

1. Tính vector kỳ vọng của toàn cỗ dữ liệu: \[ \bar{\mathbf{x}} = \frac{1}{N} \sum_{n=1}^N \mathbf{x}_n \]
2. Trừ từng điểm tài liệu cút vector kỳ vọng của toàn cỗ dữ liệu: \[ \hat{\mathbf{x}}_n = \mathbf{x}_n - \bar{\mathbf{x}} \]
3. Tính ma mãnh trận hiệp phương sai: \[ \mathbf{S} = \frac{1}{N}\hat{\mathbf{X}}\hat{\mathbf{X}}^T \]
4. Tính những trị riêng biệt và vector riêng biệt với norm vày 1 của ma mãnh trận này, bố trí bọn chúng theo dõi trật tự hạn chế dần dần của trị riêng biệt.
5. Chọn \(K\) vector riêng biệt ứng với \(K\) trị riêng biệt lớn số 1 nhằm thiết kế ma mãnh trận \(\mathbf{U}_K\) với những cột tạo nên trở nên một hệ trực gửi gắm. \(K\) vectors này, còn được gọi là những bộ phận chủ yếu, tạo nên trở nên một không khí con cái gần với phân bổ của tài liệu ban sơ đang được chuẩn chỉnh hoá.
6. Chiếu tài liệu ban sơ đang được chuẩn chỉnh hoá \(\hat{\mathbf{X}}\) xuống không khí con cái tìm kiếm được.
7. Dữ liệu mới mẻ đó là toạ phỏng của những điểm tài liệu bên trên không khí mới mẻ. \[ \mathbf{Z} = \mathbf{U}_K^T\hat{\mathbf{X}} \]

Dữ liệu ban sơ rất có thể tính được xấp xỉ theo dõi tài liệu mới mẻ như sau: \[ \mathbf{x} \approx \mathbf{U}_K\mathbf{Z} + \bar{\mathbf{x}} \]

Các bước triển khai PCA rất có thể được coi nhập Hình bên dưới đây:

Hình 5: Các bước triển khai PCA.

5. Thảo luận

Vì nội dung bài viết đã tương đối nhiều năm, tôi xin xỏ lưu giữ phần sót lại của PCA mang lại nội dung bài viết tiếp sau. Trong bài bác cho tới, tất cả chúng ta nằm trong thảo luận về quan hệ thân thiện PCA và SVD, lập trình sẵn PCA, một vài ba phần mềm và không ngừng mở rộng của SVD. Mời chúng ta đón hiểu.

6. Tài liệu tham lam khảo

[1] Principal component analysis - Wikipedia

Xem thêm: what do rabbit holes look like

[2] A tutorial on Principal Components Analysis

[3] Bishop, Christopher M. “Pattern recognition and Machine Learning.”, Springer (2006). Chapter 12. (book)