Chào mừng đến với BIS Đăng nhập | Đăng ký | Trợ giúp
trong Tìm kiếm

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

Bài cuối 09-11-2012 09:26 PM của bexiugc. 8 trả lời.
Trang 1 trong số 1 (9 nội dung)
Sắp xếp bài viết: Trước Tiếp theo
  • 12-11-2011 04:34 PM

    • chucnv
    • 10 thành viên năng nổ nhất
    • Tham gia 12-05-2008
    • Điểm 10,255

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

    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:

     

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

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

    xi 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 x1 và x2 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 (f2) lớn hơn so với f1 (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 



    • Điểm chủ đề: 80
  • 12-12-2011 01:17 PM trả lời

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

    Lâu rồi mới thấy anh Post bài mới.
    Bài viết thấy hay nhưng khó quá anh ah. Hướng dẫn chi tiết rồi mà em đọc vẫn thấy " Không kiểm soát" được. Có lẽ kiến thức thống kê và toán của em còn tệ quá (phải upgrade mới hiểu được).
     
    • Điểm chủ đề: 20
  • 12-18-2011 03:15 PM trả lời

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

    Chào anh Chức
    Em là sinh viên cao học, đang muốn sử dụng phương pháp phân tích phân biệt nhưng không biết. Thấy anh viết bài, em mừng quá.
    Vậy, anh có thể cho em biết thêm về bản chất của phân tích này, hiện nay phần mềm nào được sửu dụng và cách thực hiện như thế nào?
    Mong em cho em biết một ví dụ cụ thể mà anh đã làm nhé.
    Cám ơn anh trước.
    • Điểm chủ đề: 35
  • 12-19-2011 09:40 AM trả lời

    • chucnv
    • 10 thành viên năng nổ nhất
    • Tham gia 12-05-2008
    • Điểm 10,255

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

    Chào em,
    Phân tích khác biệt (Discriminant Analysis) có 2 nhiệm vụ chính là:
    Dùng để trích chọn thuộc tính (Feature extraction) và trích chọn mẫu (Sample Extraction): Đây là nhiệm vụ ở khâu tiền xử lý dữ liệu.Ví dụ là có một tập dữ liệu thô "Raw" ban đầu. có thể lọc ra  một tập các thuộc tính hay tập các mẫu dùng cho việc xây dựng Model sao cho không làm giảm chất lượng của Model
    Nhiệm vụ thứ 2 của Phân tích khác biệt là dùng trong phân lớp như bài viết trên đã trình bày
    Hiện nay, một số các phần mềm đã triển khai kỹ thuật này như SPSS, BI Tools của MS, XLSTAT,...
     
    • Điểm chủ đề: 20
  • 12-30-2011 09:03 AM trả lời

    • NguyenNT
    • 200 thành viên năng nổ nhất
    • Tham gia 12-30-2011
    • Điểm 70

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

    Chào anh, hiện em đang tìm hiểu về lĩnh vực này, có vài thắc mắc mong anh giải đáp giúp:
    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 ạ?
     Cảm ơn anh nhiều!
    • Điểm chủ đề: 35
  • 12-30-2011 10:51 AM trả lời

    • chucnv
    • 10 thành viên năng nổ nhất
    • Tham gia 12-05-2008
    • Điểm 10,255

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

    Chào NguyenNT,
    Việc chọn thuật toán nào để xây dựng Mining Model phụ thuộc rất nhiều yếu tố như Yêu cầu về độ chính xác, qui mô, tính dễ triển khai, dễ hiểu và phù hợp với cấu trúc dữ liệu của Training Data.
    Trong các bài toán về Image processing thường sử dụng kỹ thuật Neural Network vì kỹ thuật này có độ chính xác cao, có khả năng xử lý dữ liệu lớn và giải quyết được nhiều vấn đề như Clustering, Classification,  ...
    • Điểm chủ đề: 20
  • 09-09-2012 09:15 AM trả lời

    • bexiugc
    • 200 thành viên năng nổ nhất
    • Tham gia 09-09-2012
    • Điểm 55

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

    Thưa anh! Vậy anh có thể nõi rõ hơn cho em biết về ứng dụng của DA được k anh?
    Ngoài ứng dụng trong bài toán phân lớp ra DA còn ứng dụng cho mục đích gì k ạ?
     
     
    • Điểm chủ đề: 35
  • 09-11-2012 06:39 PM trả lời

    • chucnv
    • 10 thành viên năng nổ nhất
    • Tham gia 12-05-2008
    • Điểm 10,255

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

    Chào em,
    Ngoài ứng dụng trong phân lớp dữ liệu, DA còn được dùng trong vấn đề làm giảm số chiều của dữ liệu (Data Reduction).
    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.
    • Điểm chủ đề: 35
  • 09-11-2012 09:26 PM trả lời

    • bexiugc
    • 200 thành viên năng nổ nhất
    • Tham gia 09-09-2012
    • Điểm 55

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

    Dạ em cám ơn anh nhiều!
    Anh có thể cho em hỏi thêm là: trong bài toán phân lớp của DA ngoài phương pháp Linear Discriminant Analysis thì mình có thể sử phương pháp Bayesphương pháp hồi quy Logistic không?
    Hai phương pháp này có nằm trong ứng dụng cho bài toán phân lớp của DA không hay đã là một lĩnh vực khác vậy anh?
    Em đang làm đề tài cao học về " Phân tích Phân Biệt (DA) và ứng dụng" em dự định sẽ đi theo hướng là bài toán phân lớp như bài viết của anh. Em định là sẽ sử dụng 3 phương pháp đó là: LDA, Bayes và Hồi quy logistic như em đã trình bày ở trên sau đó em sẽ ứng dụng vào lĩnh vực y học để phân loại bệnh ( trong ứng dụng này em sẽ sử dụng ca 3 phương pháp và so sánh kết quả) bằng phần mềm SPSS. Anh xem giúp em là nếu em làm như vậy là có khả thi và hợp lý không?
            Đề cương của em như sau:

    BÀI TOÁN PHÂN LỚP CỦA PHÂN TÍCH PHÂN BIỆT

    2.1 Phân tích phân biệt tuyến tính Fisher (FLDA)

        2.1.1 Trường hợp hai tổng thể

        2.1.2 Trường hợp nhiều hơn hai tổng thể

    2.2 Phân tích phân biệt bằng phương pháp hồi quy Logistic

       2.2.1 Khái niệm

       2.2.2 Hồi quy logictis đơn

       2.2.3 Hồi quy logictis bội

    2.3 Phân tích phân biệt bằng phương pháp Bayes

       2.3.1 Khái niệm

       2.3.2 Trường hợp hai tổng thể

       2.3.3 Trường hợp nhiều hơn hai tổng thể

    Em mong được sự giúp đỡ của anh!!!
     
    • Điểm chủ đề: 20
Trang 1 trong số 1 (9 nội dung)
Powered by Community Server (Commercial Edition), by Telligent Systems