Khai Phá Dữ Liệu-Các kỹ thuật phân lớp và dự đoán

Chia sẻ: Trần Ngọc Phương | Ngày: | Loại File: PDF | Số trang:55

Thêm vào BST

Báo xấu

230
lượt xem 69
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Đối với một tập các ví dụ/bản ghi ( instances/records) – gọi là tậộ ập ụ g ) gọ ập huấn luyện/học (training/learning set). Mỗi bản ghi được biểu diễn bằng một tập các thuộc tính, trong đó có một thuộc tính phân lớp (class attribute). Tìm/học một hàm cho thuộc tính phân lớp (hàm phân lớp) đối với các giá trị của các thuộc tính khác.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Khai Phá Dữ Liệu-Các kỹ thuật phân lớp và dự đoán

Khai Phá Dữ Liệu Nguyễn Nhật Quang quangnn-fit@mail.hut.edu.vn Viện Công nghệ Thông tin và Truyền thông Trường Đại học Bách Khoa Hà Nội Năm học 2010-2011
Nội dung môn học: Giới thiệu về Khai phá dữ liệu Giới thiệu về công cụ WEKA Tiền xử lý dữ liệu Phát hiện các luật kết hợp Các kỹ thuật phân lớp và dự đoán thu phân và Phân lớp bằng phương pháp học Bayes Học cây quyết định Các kỹ thuật phân nhóm Khai Phá Dữ Liệu 2
Bài toán phân lớp Bài toán phân lớp (Classification) Đối với một tập các ví dụ/bản ghi (instances/records) – gọi là tập huấn luyện/học (training/learning set) Mỗi bản ghi được biểu diễn bằng một tập các thuộc tính, trong đó có một thuộc tính phân lớp (class attribute) Tìm/học một hàm cho thuộc tính phân lớp (hàm phân lớp) đối với các giá trị của các thuộc tính khác Sử dụng một tập các ví dụ khác với các ví dụ học để kiểm tra độ chính xác của hàm phân lớp học được – gọi là là tập kiểm thử (test set) ki th (test set) Thông thường, tập dữ liệu ban đầu được chia thành 2 tập (không giao nhau): training set (để học hàm phân lớp) và test set (để ki kiểm thử hàm phân lớp học được) th hàm phân đượ Khai Phá Dữ Liệu 3
Phân lớp vs. Dự đoán Bài toán phân lớp (Classification problem) Học một hàm mục tiêu có giá trị rời rạc (a discrete-valued target hà tiê di function) Miền giá trị: một tập các nhãn lớp (class labels) xác địn trước Với mỗi ví dụ cần phân loại, hệ thống xác định nhãn lớp của nó Bài toán dự đoán/hồi quy (Prediction/regression problem) Học một hàm mục tiêu có giá trị liên tục (a continuous-valued target function) Mi Miền giá trị: tập các giá trị số thực (real numbers) th Với mỗi ví dụ cần dự đoán, hệ thống xác định giá trị dự đoán của nó Khai Phá Dữ Liệu 4
Học có vs. không có giám sát Học có giám sát (supervised learning) Mỗi ví dụ học gồm 2 phần: mô tả (biểu diễn) của ví dụ học, và ph mô và nhãn lớp (hoặc giá trị đầu ra mong muốn) của ví dụ học đó Bài toán học phân lớp (classification problem) D_train = {(, )} {(< Bài toán học dự đoán/hồi quy (prediction/regression problem) D_train = {(, )} Học không có giám sát (unsupervised learning) Mỗi ví dụ học chỉ chứa mô tả (biểu diễn) của ví dụ học đó - mà không có bất kỳ thông tin nào về nhãn lớp hay giá trị đầu ra mong nào giá muốn của ví dụ học đó Bài toán học phân cụm (Clustering problem) Tập học D_train = {()} {(< Khai Phá Dữ Liệu 5
Các khái niệm cơ bản về xác suất Giả sử chúng ta có một thí nghiệm (ví dụ: đổ một quân xúc sắc) mà kết quả của nó mang tính ngẫu nhiên (phụ thuộc vào khả năng có thể xảy ra) Không gian các khả năng S. Tập hợp tất cả các kết quả có thể xảy ra Ví dụ: S= {1,2,3,4,5,6} đối với thí nghiệm đổ quân xúc sắc thí nghi đổ quân xúc {1 Sự kiện E. Một tập con của không gian các khả năng Ví dụ: E= {1}: kết quả quân súc xắc đổ ra là 1 Ví dụ: E= {1,3,5}: kết quả quân súc xắc đổ ra là một số lẻ Không gian các sự kiện W. Không gian (thế giới) mà các kết quả của sự kiện có thể xảy ra Ví dụ: W bao gồm tất cả các lần đổ súc xắc Biến ngẫu nhiên A. Một biến ngẫu nhiên biểu diễn (diễn đạt) một sự ki kiện, và có một mức độ về khả năng xảy ra sự kiện này và có độ kh ra ki này Khai Phá Dữ Liệu 6
Biểu diễn xác suất P(A): “Phần của không gian (thế giới) mà trong đó A là đúng” Không gian sự kiện (không gian của tất cả các giá trị có thể xảy ra Không gian mà trong đó A là của A) đúng Không gian mà gian mà trong đó A là sai [http://www.cs.cmu.edu/~awm/tutorials] Khai Phá Dữ Liệu 7
Các biến ngẫu nhiên Bool Một biến ngẫu nhiên Bool có thể nhận một trong 2 giá trị đúng (true) hoặc sai (false) ho sai Các tiên đề • 0 ≤ P(A) ≤ 1 • P(true)= 1 • P(false)= 0 • P(A V B)= P(A) + P(B) - P(A ∧ B) Các hệ quả qu • P(not A)≡ P(~A)= 1 - P(A) • P(A)= P(A ∧ B) + P(A ∧ ~B) P(A P(A B) Khai Phá Dữ Liệu 8
Các biến ngẫu nhiên nhiều giá trị Một biến ngẫu nhiên nhiều giá trị có thể nhận một trong số k (>2) giá trị {v1,v2,…,vk} P ( A = vi ∧ A = v j ) = 0 if i ≠ j P(A=v1 V A=v2 V ... V A=vk) = 1 i P( A = v1 ∨ A = v2 ∨ ... ∨ A = vi ) = ∑ P( A = v j ) j =1 k ∑ P( A = v ) = 1 j j =1 i P(B ∧ [A = v1 ∨ A = v2 ∨ ... ∨ A = vi ]) = ∑ P( B ∧ A = v j ) j =1 [http://www.cs.cmu.edu/~awm/tutorials] Khai Phá Dữ Liệu 9
Xác suất có điều kiện (1) P(A|B) là phần của không gian (thế giới) mà trong đó A là đúng, với điều kiện (đã biết) là B đúng ki bi là Ví dụ •A: Tôi sẽ đi đá bóng vào ngày mai •B: Trời sẽ không mưa vào ngày mai •P(A|B): Xác suất của việc tôi sẽ đi đá bóng vào ngày mai nếu (đã biết rằng) trời sẽ không mưa (vào ngày mai) Khai Phá Dữ Liệu 10
Xác suất có điều kiện (2) P( A, B) Định nghĩa: ngh P( A | B) = P( B) Không Các hệ quả: gian gian mà trong P(A,B)=P(A|B).P(B) đó B đúng P(A|B)+P(~A|B)=1 Không gian mà k trong đó A đúng ∑ P( A = v | B) = 1 i i =1 Khai Phá Dữ Liệu 11
Các biến độc lập về xác suất (1) Hai sự kiện A và B được gọi là độc lập về xác suất nếu xác suất của sự kiện A là như nhau đối với các trường hợp: • Khi sự kiện B xảy ra, hoặc • Khi sự kiện B không xảy ra, hoặc ki ra ho • Không có thông tin (không biết gì) về việc xảy ra của sự kiện B Ví dụ •A: Tôi sẽ đi đá bóng vào ngày mai •B: Tuấn sẽ tham gia trận đá bóng ngày mai •P(A|B) = P(A) → “Dù Tuấn có tham gia trận đá bóng ngày mai hay không cũng không ảnh hưởng tới quyết định của tôi về việc đi đá bóng ngày mai.” đị tôi bó Khai Phá Dữ Liệu 12
Các biến độc lập về xác suất (2) Từ định nghĩa của các biến độc lập về xác suất P(A|B)=P(A), chúng ta thu được các luật như sau chúng ta thu đượ các lu nh sau P(A|B) • P(~A|B) = P(~A) • P(B|A) = P(B) • P(A,B) = P(A). P(B) • P(~A,B) = P(~A). P(B) • P(A,~B) = P(A). P(~B) • P(~A,~B) = P(~A). P(~B) Khai Phá Dữ Liệu 13
Xác suất có điều kiện với >2 biến P(A|B,C) là xác suất của A đối với (đã biết) B và C B C Ví dụ • A: Tôi sẽ đi dạo bờ sông vào sáng mai A • B: Thời tiết sáng mai rất đẹp P(A|B P(A|B,C) • C: Tôi sẽ dậy sớm vào sáng mai Tôi • P(A|B,C): Xác suất của việc tôi sẽ đi dạo dọc bờ sông vào sáng mai, nếu (đã biết rằng) thời tiết sáng mai rất đẹp và tôi sẽ dậy sớm vào sáng mai Khai Phá Dữ Liệu 14
Độc lập có điều kiện Hai biến A và C được gọi là độc lập có điều kiện đối với bi biến B, nếu xác suất của A đối với B bằng xác suất của A xác su xác su đối với B và C Công thức định nghĩa: P(A|B,C) = P(A|B) Ví dụ • A: Tôi sẽ đi đá bóng vào ngày mai • B: Trận đá bóng ngày mai sẽ diễn ra trong nhà • C: Ngày mai trời sẽ không mưa • P(A|B,C)=P(A|B) → Nếu biết rằng trận đấu ngày mai sẽ diễn ra trong nhà, thì xác suất của việc tôi sẽ đi đá bóng ngày mai không phụ thuộc vào th ti vào thời tiết Khai Phá Dữ Liệu 15
Các quy tắc quan trọng của xác suất Quy tắc chuỗi (chain rule) • P(A,B) = P(A|B).P(B) = P(B|A).P(A) P(A|B) P(B|A) • P(A|B) = P(A,B)/P(B) = P(B|A).P(A)/P(B) • P(A,B|C) = P(A,B,C)/P(C) = P(A|B,C).P(B,C)/P(C) P(A P(A|B = P(A|B,C).P(B|C) Độ Độc lập về xác suất và độc lập có điều kiện xác su và độ có ki • P(A|B) = P(A); nếu A và B là độc lập về xác suất • P(A,B|C) = P(A|C).P(B|C); nếu A và B là độc lập có điều độ có P(A|C).P(B|C) kiện đối với C • P(A1,…,An|C) = P(A1|C)…P(An|C); nếu A1,…,An là độc lập có có điều kiện đối với C ki đố Khai Phá Dữ Liệu 16
Định lý Bayes P ( D | h).P(h) P(h | D) = P( D) P(h): Xác suất trước (prior probability) của giả thiết (vd: phân lớp) h P(D): Xác suất trước của sự kiện tập dữ liệu D được quan sát P(D|h): Xác suất của sự kiện tập dữ liệu D được quan sát, nếu biết rằng giả thiết h là đúng P(h|D): Xác suất (có điều kiện) của giả thiết h là đúng, nếu Xác su (có ki gi thi biết rằng tập dữ liệu D được quan sát → Các phương pháp suy diễn dựa trên xác suất sẽ sử dụng xác suất có điều kiện (posterior probability) này! xác su có ki probability này! Khai Phá Dữ Liệu 17
Định lý Bayes – Ví dụ (1) Giả sử chúng ta có tập dữ liệu sau (dự đoán 1 người có chơi tennis)? Ngày Ngoài trời Nhiệt độ Độ ẩm Gió Chơi tennis N1 Nắng Nóng Cao Yếu Không N2 Nắng Nóng Cao Mạnh Không N3 Âm u Nóng Cao Yếu Có N4 Mưa Bình thường Cao Yếu Có N5 Mưa Mát mẻ Bình thường Yếu Có N6 Mưa Mát mẻ Bình thường Mạnh Không N7 Âm u Mát mẻ Bình thường Mạnh Có N8 Nắng Bình thường Cao Yếu Không N9 Nắng Mát mẻ Bình thường Yếu Có N10 Mưa Bình thường Bình thường Yếu Có N11 Nắng Bình thường Bình thường Mạnh Có N12 Âm u Bình thường Cao Mạnh Có [Mitchell, 1997] Khai Phá Dữ Liệu 18
Định lý Bayes – Ví dụ (2) Giả thiết h: Anh ta chơi tennis Tập dữ liệu D: Ngoài trời là nắng và Gió là mạnh li Ngoài tr Gió Xác suất P(h): Xác suất rằng anh ta chơi tennis (bất kể Ngoài trời như thế nào và Gió ra sao) Xác suất P(D): Xác suất rằng Ngoài trời là nắng và Gió là mạnh P(D|h): Xác suất rằng Ngoài trời là nắng và Gió là mạnh, nếu biết rằng anh ta chơi tennis P(h|D) Xác su P(h|D): Xác suất rằng anh ta chơi tennis, nếu biết rằng anh ta ch tennis bi Ngoài trời là nắng và Gió là mạnh Giá trị xác suất có điều kiện này sẽ được dùng để dự đoán xem anh ta có chơi tennis hay không? Khai Phá Dữ Liệu 19
Cực đại hóa xác suất có điều kiện Với một tập các giả thiết (các phân lớp) có thể H, hệ thống học sẽ tìm giả thiết có thể xảy ra nhất (the most probable hypothesis) h(∈H) đối với các dữ liệu quan sát được D Giả thiết h này được gọi là giả thiết cực đại hóa xác suất có điều kiện (maximum a posteriori – MAP) hMAP = arg max P(h | D) h∈H P( D | h).P (h) (bởi định lý Bayes) = arg max hMAP P( D) h∈H (P(D) là như nhau hMAP = arg max P( D | h).P(h) đối với các giả thiết h) h∈H Khai Phá Dữ Liệu 20