Phân tích khác biệt với bài toán phân lớp

Nguyễn Văn Chức – chuc1803@gmail.com

Phân tích khác biệt (Discriminant Analysis -DA) là một phương pháp phân tích trong thống kê được dùng rất nhiều trong Data mining để phân loại các đối tượng (object) vào các nhóm dựa trên việc đo lường các đặc trưng của đối tượng. Tùy vào lĩnh vực nghiên cứu mà thuật ngữ Discriminant Analysis còn có nhiều tên gọi khác nhau như pattern recognition, supervised learning, or supervised classification .

Bài viết này giới thiệu phương pháp phân tích sự khác biệt tuyến tính (Linear Discriminant Analysis LDA) dùng để giải quyết bài toán phân lớp (classification) các đối tượng. Trong DA nếu số lớp nhiều hơn 2 được gọi là phân tích đa khác biệt (Multiple Discriminant Analysis -MDA).

Mục đích của DA là tìm cách phân loại các đối tượng (người, sự vật,…) vào một trong hai hay nhiều lớp đã được xác định trước dựa vào các đặt trưng (feature) dùng để mô tả đối tượng (ví dụ như các đặc trưng dùng để mô tả đối tượng khách hàng là giới tính, tuổi, nghề nghiệp, thu nhập,…)

Mục đích chính của phân tích sự khác biệt là:

1.      Tìm tập các thuộc tính tốt nhất để mô tả đối tượng. Vấn đề này còn gọi là trích chọn đặc trưng (Feature Extraction) hay lựa chọn đặc trưng (Feature Selection). Mục đích là phần này là từ tập các thuộc tính mô tả đối tượng ban đầu (thường rất lớn, có thể hàng trăm thuộc tính) tìm ra tập các thuộc tính tốt nhất để biểu diễn cho đối tượng nhằm làm giảm số chiều biểu diễn đối tượng từ đó làm giảm chi phí tính toán của các mô hình khai phá dữ liệu nhưng chất lượng của mô hình không bị giảm đi. Xem bài về trích chọn thuộc tính tại đây (http://bis.net.vn/forums/t/505.aspx)

2.      Tìm một mô hình tốt nhất để phân lớp các đối tượng.

Bài viết này chỉ tập trung vào việc ứng dụng DA để giải quyết bài toán phân lớp trong Data Mining.
Phân tích sự khác biệt tuyến tính (Linear Discriminant Analysis -LDA)

Để dễ hình dung ta xem xét một ví dụ đơn giản sau:

Giả sử ta muốn biết liệu một sản phẩm xà phòng là tốt (good) hay xấu (bad) dựa vào các đo lường trên các đặc trưng như trọng lượng (weight), khối lượng (volume), màu sắc (color), mùi (smell). Đối tượng (object) ở đây là xà phòng và thuộc tính phân lớp (class category attribute) ở đây có hai giá trị là “good” và “bad”. Các đặc trưng của đối tượng còn gọi là biến độc lập (Independent Variable) và thuộc tính phân lớp gọi là biến phụ thuộc (Dependent Variable).

Vì vậy trong phân tích sự khác biệt, biến phụ thuộc (Y) là lớp và biến độc lập (X) là các đặc trưng của đối tượng. Biến phụ thuộc luôn có kiểu là nominal trong khi biến độc lập có thể có kiểu bất kỳ nominal, ordinal, interval hay ratio.

Nếu ta giả sử thêm rằng các lớp có thể tách biệt bởi một hàm tuyến tính, chúng ta có thể sử dụng LDA để xây dựng hàm phân lớp. LDA xây dựng hàm phân lớp dựa trên sự kết hợp tuyến tính giữa các đặc trưng của đối tượng. Nếu chỉ có 2 đặc trưng thì hàm phân loại các lớp là đường (line). Nếu số đặc trưng là 3 thì hàm phân lớp là mặt phẳng (plane). Nếu số đặc trưng  nhiều hơn 3 thì hàm phân lớp là siêu mặt phẳng (hyper - lane)

Công thức LDA (LDA Formula)

LDA sử dụng điều kiện phân lớp để tối thiểu lỗi (Total error of classification -TEC) của mô hình. Nguyên tắc phân lớp đối tượng là gán một đối tượng vào một lớp với xác suất có điều kiện cao nhất (nguyên tắc này gọi là nguyên tắc Bayes, Bayes rule). Xem thêm bài viết ứng dụng lý thuyết Bayes trong phân lớp tại đây: http://bis.net.vn/forums/t/390.aspx

Nếu có g lớp, the Bayes' rule sẽ gán đối tượng x vào lớp i nếu

Cho một tập các đo lường các đặc trưng của x, ta tìm max(P(i|x)) và gán đối tượng x vào lớp i. Tuy nhiên P(i|x) rất khó tính toán. Chúng ta có thể tính P(x|i), tức là xác suất xảy ra x khi đã biết lớp i. Chẳn hạn sau khi đã biết được lớp của sản phẩm xà phòng là good hay bad chúng ta có thể có được các đặc trưng mô tả đối tượng như weight, smell, color,… Nhưng điều ta cần là ngược lại. Có nghĩa là dựa vào các đặc trưng của đối tượng chúng ta phải xác định đối tượng với các đặc trưng đó thuộc lớp nào?

May mắn là trong lý thuyết Bayes có công thức mô tả mối quan hệ giữa 2 xác suất có điều kiện P(i|x) và P(x|i) như sau (CT1):

 Vấn đề là sử dụng CT1 để tính P(i|x) thông qua P(x|i) cũng rất khó triển khai trong thực tế vì để tính được P(x|i) chúng ta cần rất nhiều dữ liệu để tính tần số tương đối của mỗi lớp đối với mỗi đặc trưng của đối tượng.

Để dễ dàng hơn cho việc tính toán, các nhà thống kê và toán học đã tìm ra hàm chuyển đổi gọi là công thức phân tích sự khác biệt tuyến tính (Linear Discriminant Analysis formula) như sau (CT2):

Ví dụ về  Linear Discriminant Analysis

Đây là ví dụ về LDA minh họa về cách sử dụng LDA để phân lớp. Các công thức trên được minh họa tính toán trong MS Excel

Giả sử công ty “ABC” sản xuất sản phẩm rất đắt tiền và chất lượng cao. Sản phẩm được mô tả bởi 2 đặc trưng (feature) đó là Curvature (độ cong) và Diameter (đường kính). Kết quả kiểm soát chất lượng được kiểm tra bởi các chuyên gia được cho trong bảng dưới đây:

Giả sử bạn là cố vấn của công ty “ABC”, bạn được giao nhiệm vụ thiết lập mô hình giúp kiểm tra chất lượng tự động của các sản phẩm của công ty. Bây giờ có sản phẩm với curvature = 2.81 và diameter =5.46 (còn gọi là đối tượng cần xếp lớp, query point) thì kết quả sau khi kiểm tra chất lượng là Passed (đạt) hay Not Passed (không đạt). Nói cách khác là xếp lớp sản phẩm cần kiểm tra vào lớp Passed hay Not Passed.

Bạn có thể giải quyết vấn đề này bằng sử dụng Discriminant Analysis

Các bước tiến hành

Nếu ta vẽ 7 sản phẩm (đối tượng) trên theo 2 đặc trưng curvature (trục x) và diameter (trục y) ta thấy rằng ta có thể vẽ một đường để tách biệt giữa lớp passed (gồm 4 sản phẩm passed) và lớp Not Passed (gồm 3 sản phẩm Not passed). Vấn đề là tìm một đường phân tách 2 lớp và quay các thuộc tính để đạt được khoảng cách giữa các lớp là lớn nhất và khoảng cách giữa các đối tượng trong cùng 1 lớp là nhỏ nhất.

Biểu diễn các đối tượng dưới dạng ma trận như sau:

Ma trận các đặc trưng (independent variables) x. Mỗi dòng biểu diễn 1 đối tượng, mỗi cột biểu diễn 1 feature.

Ma trận các lớp y chứa các lớp của đối tượng (biến phụ thuộc -  dependent variable)

Trong ví dụ này ta có ma trận x và y như sau:

 x^k là dòng thứ k trong ma trận x. ví dụ x³= [3.75               5.65]

g là số các lớp trong y. Trong ví dụ trên ta có g=2

x_i ma trận chứa các đặc trưng của các đối tượng thuộc lớp i. Trong ví dụ trên ta có 2 lớp nên ta tách thành 2 ma trận x₁ và x₂ như sau:

 Ma trận hiệp phương sai của lớp i được tính theo công thức sau:

Nói thêm về hiệp phương sai (covariance): Trong lý thuyết xác suất và thống kê, hiệp phương sai là độ đo sự biến thiên cùng nhau của hai biến ngẫu nhiên (phân biệt với phương sai (variance) - đo mức độ biến thiên của một biến. Nếu 2 biến có xu hướng thay đổi cùng nhau (nghĩa là, khi một biến có giá trị cao hơn giá trị kỳ vòng thì biến kia có xu hướng cũng cao hơn giá trị kỳ vọng), thì hiệp phương sai giữa hai biến này có giá trị dương. Ngược lại, nếu một biến nằm trên giá trị kì vọng còn biến kia có xu hướng nằm dưới giá trị kì vọng, thì hiệp phương sai của hai biến này có giá trị âm. Các biến ngẫu nhiên có hiệp phương sai bằng không được gọi là không tương quan (uncorrelated)

Ma trận hiệp phương sai (covariance matrix) của m biến ngẫu nhiên là một ma trận vuông hạng (m × m), trong đó các phần tử nằm trên đường chéo lần lượt là phương sai tương ứng của các biến này ( chú ý rằng Var(X) = Cov(X,X)), và các phần tử còn lại (không nằm trên đường chéo) là các hiệp phương sai của đôi một hai biến ngẫu nhiên khác nhau.

Xem chi tiết về cách tính covariance matrix tại đây: http://www.aiaccess.net/English/Glossaries/GlosMod/e_gm_covariance_matrix.htm

Trong ví dụ trên ta tính giá trị cho mỗi bộ (r,s) như sau:

 Tổ chức dữ liệu và tính toántrong Excel như sau:

Chú ý một số công thức liên quan đến ma trận là công thức mảng nên phải bấm Ctrl + Shift + Enter để thực hiện.

Theo tính toán thì đối tượng cần phân lớp (Query Point) với curvature = 2.81 và diameter =5.46 được xếp vào lớp 2 (Not passed) vì giá trị Discriminant function của lớp 2 (f₂) lớn hơn so với f₁ (44.085>44.049). Điều đó có nghĩa là sản phẩm được kiểm tra không đạt chất lượng. 

Đồ thị sau cho ta thấy một cách trực quan rằng Query Point thuộc lớp Not Passed 

1. Hiện nay có nhiều phương pháp giải bài toán phân lớp: neural network, cây quyết định, k-means, knn,... Vậy từng phương pháp tương ứng với từng trường hợp nào để áp dụng, vì em nghĩ cùng 1 bài toán không phải dùng giải pháp nào cũng cho ra kết quả hợp lý.
2. Đối với bài toán nhận dạng ảnh và phân lớp, phần lớn tài liệu đều dùng neural network, nếu em dùng cây quyết định thì có gì không hợp lý không anh, em nghĩ việc lựa chọn cách giải phụ thuộc vào cấu trúc dữ liệu của thuộc tính đặc trưng được trích chọn phải không ạ?