Bài giảng Khai phá dữ liệu - Chương 5: Phân lớp dữ liệu

Chia sẻ: Nguyễn Thị Hiền Phúc | Ngày: | Loại File: PPTX | Số trang:34

Thêm vào BST

Báo xấu

60
lượt xem 8
download

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

Bài giảng cung cấp cho người học các kiến thức: Phân lớp dữ liệu. Hi vọng đây sẽ là một tài liệu hữu ích dành cho các bạn sinh viên đang theo học môn dùng làm tài liệu học tập và nghiên cứu.

Chủ đề:

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

Lưu

Nội dung Text: Bài giảng Khai phá dữ liệu - Chương 5: Phân lớp dữ liệu

TRƯỜNG ĐẠI HỌC HÀNG HẢI VIỆT NAM KHOA CÔNG NGHỆ THÔNG TIN BÀI GIẢNG MÔN HỌC KHAI PHÁ DỮ LIỆU CH ƯƠN G 5 : P HÂ N LƠP ́ D Ữ LIỆU Gi ản g v iê n : Th S . N g u y ễn V ươn g Th ịn h B ộ m ô n : H ệ t h ốn g t h ô n g t in H ải P h ò n g ,
Th ô n g t in v ề g i ản g v iê n Họ và tên Nguyễn Vương Thịnh Đơn vị công tác Bộ môn Hệ thống thông tin – Khoa Công nghệ thông tin Học vị Thạc sỹ Chuyên ngành Hệ thống thông tin Cơ sở đào tạo Trường Đại học Công nghệ - Đại học Quốc Gia Hà Nội Năm tốt nghiệp 2012 Điện thoại 0983283791 Email thinhnv@vimaru.edu.vn Website cá nhân http://scholar.vimaru.edu.vn/thinhnv 2
Th ô n g t in v ề h ọc p h ần Tên học phần Khai phá dữ liệu Tên tiếng Anh Data Mining Mã học phần 17409 Số tín chỉ 03 tín chỉ Số tiết lý thuyết 39 tiết (13 tuần x 03 tiết/tuần) Số tiết thực hành 10 tiết (05 tuần x 02 tiết/tuần) Bộ môn phụ trách Hệ thống thông tin P H ƯƠN G P HÁP H ỌC TẬP, N GHIÊN CỨU v N g h e g i ản g , t h ảo lu ận , t ra o đ ổi v ới g i ản g v iê n t rê n l ớp . P H ƯƠTNựG P n g HÁP h iê n Đ c ứ ÁNu tH GIÁ à i li ệu v à là m b à i t ập ở n h à . v v S V p h ải t h a m d ự ít n h ất 7 5 % t h ời g ia n . v Có 0 2 b à i k i ểm t ra v i ết g i ữa h ọc p h ần ( X = X2 = ( L1 + L2 ) /2 ) . 3 v Th i k ết t h ú c h ọc p h ần b ằn g h ìn h t h ức t r ắc n g h i ệm k h á c h q u a n t rê n m á y t ín h ( Z = 0 . 5 X + 0 . 5 Y) .
Tài liệu tham khảo 1. Jiawei Han and Micheline Kamber, D a t a Min in g Co n c e p t s a n d Te c h n iq u e s , Elsevier Inc, 2006. 2. Ian H. Witten, Eibe Frank, D a t a Min in g – P ra c t ic a l Ma c h in e Le a rn in g To o ls a n d Te c h n iq u e s ( t h e s e c o n d e d it io n ) , Elsevier Inc, 2005 (sử dụng kèm với công cụ Weka). 3. Elmasri, Navathe, Somayajulu, Gupta, Fundamentals of Database Systems (the 4th Edition), Pearson Education Inc, 2004. 4. Hà Quang Thụy, Phan Xuân Hiếu, Đoàn Sơn, Nguyễn Trí Thành, Nguyễn Thu Trang, Nguyễn Cẩm Tú, Giáo trình Khai phá dữ liệu Web, NXB Giáo dục, 2009 4
5
Công cụ phần mềm hỗ trợ Phần mềm Weka được phát triển bởi nhóm nghiên cứu của trường Đại h ọc Wa ik a t o ( N e w Ze a la n d ) t ừ n ă m 1 9 9 9 . Có t h ể d o w n lo a d v ề t ại đ ịa c h ỉ: h t t p ://w w w . c s . w a ik a t o . a c . n z /m l/w e k a /d o w n lo a d in g . h t m l 6
CHƯƠNG 5: PHÂN LỚP DỮ LIỆU 5.1. KHÁI NIỆM VỀ PHÂN LỚP DỮ LIỆU 5.2. PHÂN LỚP DỰA TRÊN XÁC SUẤT CÓ ĐIỀU KIỆN (Phân lớp Bayes – Naive Bayesian Classification) 5.3. PHÂN LỚP DỰA TRÊN CÂY QUYẾT ĐỊNH 5.4. XÂY DỰNG MÔ HÌNH PHÂN LỚP VỚI WEKA 7
5.1. KHÁI NIỆM VỀ PHÂN LỚP DỮ LIỆU Cho tập các lớp C = {C1, C2,…, Cm} và tập dữ liệu D = {X1, X2 ,…, Xn} Phân lớp dữ liệu là sự phân chia các đối tượng dữ liệu vào các lớp. Về bản chất đây quá trình ánh xạ mỗi đối tượng Xj ∈ D tương ứng với một lớp Ci ∈ C. X C1 1 X C2 2 X C 3 . . 3 . . . . Xn C 1 Xn m D C 8 f: D → C hay c = f(X) (với X∈ D và c∈
 Mỗi ánh xạ được gọi là một mô hình phân lớp (Classification Model). ⟹ Làm sao để xây dựng mô hình phân lớp? Thông qua quá trình huấn luyện dựa trên tập dữ liệu học (học có giám sát – supervised learning) 9
Xây dựng mô hình B1: Chọn một tập ví dụ mẫu (gồm các đối tượng đã được phân lớp): Dexam = D1 ∪ D2 ∪ … ∪ Dm trong đó Di = {X|(X ∈ D)∧ (X ⟶ Ci)} i=1,..,m B2: Tách Dexam thành 02 tập: v Tập dữ liệu học Dtrain v Tập dữ liệu kiểm tra Dtest 2 Hiển nhiên Dexam = Dtrain ∪ Dtest và th1ường thì người ta tách sao cho: Dtrain = Dexam Dtest = Dexam 3 3 B3: Dùng Dtrain để xây dựng mô hình (xác định tham số). Có nhiều loại mô hình phân lớp như: Bayes, cây quyết định, luật phân lớp,… B4: Dùng Dtest để kiểm tra, đánh giá mô hình xây dựng được. B5: Chọn mô hình có chất lượng nhất. Sử dụng mô hình Cho X ∈ D (là tập dữ liệu chưa phân lớp) ⟹ Xác định lớp của X 10
5 . 2 . P HÂN LỚP D ỰA TRÊN XÁC S U ẤT CÓ Đ IỀU KIỆN (Naive Bayes Classifier) 5.2.1. Xác suất có điều kiện và công thức Bayes  Gọi X là một bộ dữ liệu (data tuple). Theo ngôn ngữ xác suất, X được xem là một biến cố (evidence).  Gọi H là một giả thuyết (hypothesis): bộ X thuộc về lớp Ci. ⟹ Cần xác định P(H|X): xác suất xảy ra H khi đã xuất hiện X (hay xác suất để X thuộc về lớp Ci nếu như đã biết các thuộc tính của X). Nhãn phân lớp X được xác định thông qua tập giá trị của các thuộc tính 11
• P ( H| X) là x á c s u ất c ó đ i ều k i ện c ủa H đ ối v ới X ( x á c x u ất x ảy ra H k h i b i ết X x ảy ra ) . V í d ụ: X = ( a g e = 3 5 y e a r s o ld , in c o m e = $ 4 0 , 0 0 0 ) , H = ( b u y _c o m p u t e r = Ye s ) P ( H| X ) = P ( b y _c o m p u t e r = y e s | a g e = 3 5 y e a rs o ld , in c o m e = $ 4 0 , 0 0 0 ) ⟹ X á c s u ất đ ể m ột n g ười 3 5 t u ổi c ó t h u n h ập $ 4 0 , 0 0 0 m u a m á y t ín h • P ( X| H) là x á c s u ất c ó đ i ều k i ện c ủa X đ ối v ới H ( x á c s u ất x ảy ra X k h i b i ết H x ảy ra ) . V í d ụ: P ( X | H) = P(a g e = 3 5 y e a rs o ld , in c o m e = $ 4 0 , 0 0 0 | b u y _c o m p u t e r= y e s ) ⟹ X á c s u ất đ ể m ột n g ười m u a m á y t ín h c ó đ ộ t u ổi là 3 5 v à t h u n h ập là $ 4 0 , 0 0 0 . • P ( X) là x á c s u ất t iê n n g h i ệm c ủa X. V í d ụ: P ( X ) = P ( a g e = 3 5 y e a rs o ld , in c o m e = $ 4 0 , 0 0 0 ) ⟹ X á c s u ất đ ể t ìm t h ấy t r o n g t ập d ữ li ệu đ a n g x é t m ột n g ười c ó đ ộ 12 t u ổi là 3 5 v à t h u n h ập là $ 4 0 , 0 0 0 . • P ( H) là x á c s u ất t iê n n g h i ệm c ủa H.
Cô n g t h ức Ba y e s : P( X | H ) P( H ) P( H | X ) = P( X ) Th o m a s Ba y e s ( 1 7 0 2 – 1761) 13
5 . 2 . 2 . P h â n l ớp d ữ li ệu d ựa t rê n x á c s u ất c ó đ i ều k i ện ( p h â n l ớp Ba y e s ) B ộ p h â n l ớp Ba y e s h o ạt đ ộn g n h ư s a u : 1. Ch o D là t ập d ữ li ệu h ọc g ồm c á c b ộ v à n h ã n l ớp t ươn g ứn g ( đ ã đ ược p h â n l ớp ) . M ỗi b ộ đ ược b i ểu d i ễn b ởi m ột v e c t o r n c h i ều X = ( x 1 , x 2 , …, x n ) t r o n g đ ó x i là g iá t r ị t ươn g ứn g v ới t h u ộc t ín h A i ( i = 1 , 2 , …, n ) . T ập D i = { X | ( X ∈ D )∧ (X ⟶ Ci) } là t ập c á c b ộ t r o n g D t h u ộc v ề l ớp Ci. 2. Giả sử có m lớp C1, C2,…, Cm. Bộ X được dự đoán là thuộc về lớp Ci khi và chỉ khi: P(Ci|X) > P(Cj|X) với mọi j ≠ i và 1 ≤ j ≤ m (X thuộc về lớp mà xác suất có điều kiện khi biết X là lớn nhất) ⟹ Đi tìm lớp Ci trong số m lớp sao cho P(Ci|X) là lớn nhất. 3. P(X) là giống nhau với tất cả các lớp nên theo công thức Bayes thì P(Ci|X) lớn nhất tương ứng vớPi (C tích Di P(X|Ci)P(Ci) lớn nhất ⟹ Đi tìm Ci sao cho tích P(X| i ) = Ci)P(Ci) là lớn nhất (i = 1, 2,…, m). D 4. Ta có thể tính: n P( X | Ci ) = P ( xk | Ci ) = P( x1 | Ci ) P ( x2 | Ci )...P ( xn | Ci ) và nếu coi n thuộc tính c k =1 ủa X là độc lập thì: { X ' | ( X '( Ak ) = xk )Λ( X ' D i )} 14 P( xk | Ci ) = Di
Ch ú ý : v N ếu k h ô n g t ín h đ ược P ( Ci ) t h ì c ó t h ể c o i P ( C1 ) = P ( C2 ) = … = P ( Cm ) v à b à i t o á n q u y v ề t ìm l ớp Ci t ro n g s ố m l ớp s a o c h o P ( X| Ci) c ó g iá t ri l ớn n h ất . v N ếu t ồn t ại P ( x k | Ci) = 0 t h ì c ó t h ể á p d ụn g h i ệu c h ỉn h La p a c e { X ' | ( X '( Ak ) = xk )Λ( X ' �D i )} v à c ô n g t h ức t ín h c ủa P ( x k | Ci) đ ược h i ệu c h ỉn h n h ư s a u : +1 P( xk | Ci ) = Di + q q : s ố g iá t r ị k h á c n h a u c ủa A k 15
Ví d ụ: Ch o t ập d ữ li ệu h ọc g ồm c á c b ộ d ữ li ệu đ ã đ ược p h â n l ớp n h ư s a u : Áp d ụn g p h â n l ớp Ba y e s h ã y d ự đ o á n b ộ d ữ li ệu 16 t h u ộc l ớp n à o ?
Có 0 2 l ớp d ữ li ệu t ươn g ứn g v ới b u y s _c o m p u t e r = y e s v à b u y s _c o m p u t e r = n o Suy ra : T ươn g t ự: 17 ⟹ X t h u ộc l ớp d ữ li ệu t ươn g ứn g v ới
5 . 3 . P HÂN LỚP D ỰA TRÊN CÂY QUYẾT Đ định 5.3.1. Mô hình phân lớp cây quyết ỊN H  Cây quyết định (decision tree) là một mô hình phân lớp điển hình.  Cây quyết định bao gồm: v Các nút trong: biểu diễn cho một thuộc tính được kiểm thử (test). v Các nút lá: nhãn/mô tả của một lớp (class label). v Nhánh: xuất phát từ một nút trong, phản ánh kết quả của một phép thử trên thuộc tính tương ứng. Married yes no Salary Acct Balance < 20K >= 50K >= 5K >= 20K 5K < Age < 50K good risk poor risk poor risk < 25 >= 25 18 fair risk fair risk good risk
 Có thể dễ dàng chuyển đổi từ mô hình cây quyết định sang mô hình lu ật p h â n l ớp bằng cách: đi từ nút gốc cho tới nút lá, mỗi đường đi tương ứng với một luật phân lớp. Married yes no Salary Acct Balance < 20K >= 50K >= 5K >= 20K 5K < Age < 50K good risk poor risk poor risk < 25 >= 25 fair risk fair risk good risk 1. If (Married = yes) And (Salary > 20K) Then Class = poor risk 2. If (Married = yes) And (50K > Salary >= 20K) Then Class = fair risk 3. If (Married = yes) And (Salary >= 50K) Then Class = good risk 4. If (Married = no) And (Acct Balance < 5K) Then Class = poor risk 5. If (Married = no) And (Acct Balance >= 5K) And (Age < 25) Then Class = 19 fair risk 6. If (Married = no) And (Acct Balance >= 5K) And (Age >= 25) Then Class =
Married yes no Salary Acct Balance < 20K >= 50K >= 5K >= 20K 5K < Age < 50K good risk poor risk poor risk < 25 >= 25 fair risk fair risk good risk Name Age Married Salary Acct Class Name Age Married Salary Acct Class Balance Balance Alice 19 yes 30K 6K ? Alice 19 yes 30K 6K fair risk Pike 28 no 60K 7K ? Pike 28 no 60K 7K good risk Tom 35 yes 10K 10K ? Tom 35 yes 10K 10K poor risk Peter 24 no 20K 8K ? Peter 24 no 20K 8K fair risk Lucas 40 no 20K 3K ? Lucas 40 no 20K 3K poor risk 20