›
›

Khai phá dữ liệu - Chương 4: Phân loại dữ liệu

ppt 51 trang vanle 1130
Download
Bạn đang xem 20 trang mẫu của tài liệu "Khai phá dữ liệu - Chương 4: Phân loại dữ liệu", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pptkhai_pha_du_lieu_chuong_4_phan_loai_du_lieu.ppt

Nội dung text: Khai phá dữ liệu - Chương 4: Phân loại dữ liệu

  1. Chương 4: Phân loại dữ liệu Khai phá dữ liệu (Data mining) 1
  2. Nội dung 4.1. Tổng quan về phân loại dữ liệu 4.2. Phân loại dữ liệu với cây quyết định 4.3. Phân loại dữ liệu với mạng Bayesian 4.4. Phân loại dữ liệu với mạng Neural 4.5. Các phương pháp phân loại dữ liệu khác 4.6. Tĩm tắt 2
  3. 4.0. Tình huống 1 Marital Taxable Tid Refund Evade Status Income 1 Yes Single 125K No 2 No Married 100K No 3 No Single 70K No ( 4 Yes Married 120K No Ơng A Tid = 100) 5 No Divorced 95K Yes cĩ khả năng trốn 6 No Married 60K No thuế??? 7 Yes Divorced 220K No 8 No Single 85K Yes 9 No Married 75K No 10 No Single 90K Yes 10 3
  4. 4.0. Tình huống 2 Với thơng tin của một applicant A, xác định liệu ngân hàng cĩ cho A vay khơng? 4
  5. 4.0. Tình huống 3 Khĩa MãSV MơnHọc1 MơnHọc2 TốtNghiệp 2004 1 9.0 8.5 Cĩ 2004 2 6.5 8.0 Cĩ 2004 3 4.0 2.5 Khơng 2004 8 5.5 3.5 Khơng 2004 14 5.0 5.5 Cĩ 2005 90 7.0 6.0 Cĩ 2006 24 9.5 7.5 Cĩ 2007 82 5.5 4.5 Khơng 2008 47 2.0 3.0 Khơng Làm sao xác định liệu sinh viên A sẽ tốt nghiệp? 5
  6. 4.0. Tình huống Cho trước tập huấn luyện (training set), dẫn ra mơ tả về class A và class B? Cho trước mẫu/đối tượng mới, làm sao xác định class cho mẫu/đối tượng đĩ? Liệu class đĩ cĩ thực sự phù hợp/đúng cho mẫu/đối tượng đĩ? 6
  7. 4.1. Tổng quan về phân loại dữ liệu Phân loại dữ liệu (classification) ◼ Dạng phân tích dữ liệu nhằm rút trích các mơ hình mơ tả các lớp dữ liệu hoặc dự đốn xu hướng dữ liệu ◼ Quá trình gồm hai bước: Bước học (giai đoạn huấn luyện): xây dựng bộ phân loại (classifier) bằng việc phân tích/học tập huấn luyện Bước phân loại (classification): phân loại dữ liệu/đối tượng mới nếu độ chính xác của bộ phân loại được đánh giá là cĩ thể chấp nhận được (acceptable) y = f (X) với y là nhãn (phần mơ tả) của một lớp (class) và X là dữ liệu/đối tượng - Bước học: X trong tập huấn luyện, một trị y được cho trước với X → xác định f - Bước phân loại: đánh giá f với (X’, y’) và X’ <> mọi X trong tập huấn luyện; nếu acceptable thì dùng f để xác định y’’ cho X’’ (mới) 7
  8. 4.1. Tổng quan về phân loại dữ liệu BướcBước học/huấnphân loại luyện(đánh giá và áp dụng) 8
  9. 4.1. Tổng quan về phân loại dữ liệu Phân loại dữ liệu ◼ Dạng học cĩ giám sát (supervised learning) desired state X response Y Environment Teacher actual + response Learning - System S error signal 9
  10. 4.1. Tổng quan về phân loại dữ liệu Các giải thuật phân loại dữ liệu ◼ Phân loại với cây quyết định (decision tree) ◼ Phân loại với mạng Bayesian ◼ Phân loại với mạng neural ◼ Phân loại với k phần tử cận gần nhất (k-nearest neighbor) ◼ Phân loại với suy diễn dựa trên tình huống (case- based reasoning) ◼ Phân loại dựa trên tiến hố gen (genetic algorithms) ◼ Phân loại với lý thuyết tập thơ (rough sets) ◼ Phân loại với lý thuyết tập mờ (fuzzy sets) 10
  11. 4.2. Phân loại dữ liệu với cây quyết định Cơ sở dữ liệu khách hàng AllElectronics dùng cho bước học 11
  12. 4.2. Phân loại dữ liệu với cây quyết định Cây quyết định (decision tree) – mơ hình phân loại ◼ Node nội: phép kiểm thử (test) trên một thuộc tính ◼ Node lá: nhãn/mơ tả của một lớp (class label) ◼ Nhánh từ một node nội: kết quả của một phép thử trên thuộc tính tương ứng Cây quyết định học được từ CSDL huấn luyện AllElectronics 12
  13. 4.2. Phân loại dữ liệu với cây quyết định Giải thuật xây dựng cây quyết định ◼ ID3, C4.5, CART (Classification and Regression Trees – binary decision trees) 13
  14. 4.2. Phân loại dữ liệu với cây quyết định 14
  15. 4.2. Phân loại dữ liệu với cây quyết định Đặc điểm của giải thuật ◼ Giải thuật tham lam (khơng cĩ quay lui), chia để trị, đệ qui, từ trên xuống ◼ Độ phức tạp với tập huấn luyện D gồm |D| phần tử (đối tượng), mỗi phần tử gồm n thuộc tính O(n*|D|*log|D|) ▪ Mỗi thuộc tính ứng với mỗi mức (level) của cây. ▪ Cho mỗi mức của cây, |D| phân tử huấn luyện được duyệt qua. ◼ In-memory → ??? 15
  16. 4.2. Phân loại dữ liệu với cây quyết định Attribute_selection_method ◼ Phương thức dùng heuristic để chọn tiêu chí rẽ nhánh tại một node, i.e. phân hoạch tập huấn luyện D thành các phân hoạch con với các nhãn phù hợp Xếp hạng mỗi thuộc tính Thuộc tính được chọn để rẽ nhánh là thuộc cĩ trị số điểm (score) lớn nhất Độ đo chọn thuộc tính phân tách (splitting attribute): information gain, gain ratio, gini index 16
  17. 4.2. Phân loại dữ liệu với cây quyết định A là thuộc tính phân tách (splitting attribute). 17
  18. 4.2. Phân loại dữ liệu với cây quyết định Độ đo Information Gain ◼ Dựa trên lý thuyết thơng tin (information theory) của Claude Shannon về giá trị (nội dung thơng tin) của tin ◼ Thuộc tính tương ứng với information gain lớn nhất sẽ được chọn làm splitting attribute cho node N. Node N là node hiện tại cần phân hoạch các phần tử trong D. Splitting attribute đảm bảo sự trùng lắp (impurity)/ngẫu nhiên (randomness) ít nhất giữa các phân hoạch tạo được. Cách tiếp cận này giúp tối thiểu số phép thử (test) để phân loại một phần tử. 18
  19. 4.2. Phân loại dữ liệu với cây quyết định Độ đo Information Gain ◼ Lượng thơng tin cần để phân loại một phần tử trong D (= Entropy của D): Info(D) pi: xác suất để một phần tử bất kỳ trong D thuộc về lớp Ci với i = 1 m Ci,D: tập các phần tử của lớp Ci trong D m Info(D) = − pi log 2 ( pi ) i=1 pi =| Ci,D | / | D | 19
  20. 4.2. Phân loại dữ liệu với cây quyết định Độ đo Information Gain ◼ Lượng thơng tin cần để phân loại một phần tử trong D dựa trên thuộc tính A: InfoA(D) Thuộc tính A dùng phân tách D thành v phân hoạch {D1, D2, , Dj, , Dv}. Mỗi phân hoạch Dj gồm |Dj| phần tử trong D. Lượng thơng tin này sẽ cho biết mức độ trùng lắp giữa các phân hoạch, nghĩa là một phân hoạch chứa các phần tử từ một lớp hay nhiều lớp khác nhau. Mong đợi: InfoA(D) càng nhỏ càng tốt. v | Dj | InfoA (D) =  *Info(Dj ) j=1 | D | 20
  21. 4.2. Phân loại dữ liệu với cây quyết định Độ đo Information Gain ◼ Information gain chính là độ sai biệt giữa trị thơng tin Info(D) ban đầu (trước phân hoạch) và trị thơng tin mới InfoA(D) (sau phân hoạch với A). Gain(A) = Info(D) − InfoA(D) 21
  22. 4.2. Phân loại dữ liệu với cây quyết định Gain(age)=0.246 bits Gain(income)? Gain(student)? Gain(credit_rating)? → Splitting attribute? 22
  23. 4.2. Phân loại dữ liệu với cây quyết định Độ đo Gain Ratio: GainRatio(A) ◼ Dùng với C4.5 ◼ Giải quyết vấn đề một thuộc tính được dùng tạo ra rất nhiều phân hoạch (thậm chí mỗi phân hoạch chỉ gồm 1 phần tử). ◼ Chuẩn hố information gain với trị thơng tin phân tách (split information): SplitInfoA(D) ◼ Splitting attribute A tương ứng với trị GainRatio(A) là trị lớn nhất. v | D | | D | j j SplitInfoA (D) = − *log 2 j=1 | D | | D | Gain(A) GainRatio(A) = SplitInfoA (D) 23
  24. 4.2. Phân loại dữ liệu với cây quyết định SplitInfoincome(D) Gain(income) = 0.029 GainRatio(income) = 0.029/0.926 = 0.031 GainRatio(age)? GainRatio(student)? GainRatio(credit_rating)? → Splitting attribute? 24
  25. 4.2. Phân loại dữ liệu với cây quyết định Độ đo Gini Index ◼ Dùng với CART ◼ Sự phân tách nhị phân (binary split) cho mỗi thuộc tính A A SA? SA là một tập con gồm một hay v-1 trị thuộc tính A. ◼ Gini index của một thuộc tính là trị nhỏ nhất tương ứng với v một tập con SA từ 2 – 2 tập con. ◼ Splitting attribute tương ứng với gini index nhỏ nhất để tối đa hĩa sự suy giảm về độ trùng lắp giữa các phân hoạch. 25
  26. 4.2. Phân loại dữ liệu với cây quyết định Giniincome {low,high} = Giniincome {medium} = 0.315 Giniincome {medium,high} = Giniincome {low} = 0.300 → Giniincome {medium,high}/{low}=0.300 Giniage {youth,senior}/{middle_aged} = 0.375 Ginistudent=0.367 Ginicredit_rating=0.429 → Splitting attribute? 26
  27. 4.2. Phân loại dữ liệu với cây quyết định Xây dựng cây quyết định từ cơ sở dữ liệu huấn luyện AllElectronics ◼ Dùng độ đo Information Gain ◼ Dùng độ đo Gain Ratio ◼ Dùng độ đo Gini Index → Các cây quyết định học được giống nhau??? → Tiến hành đánh giá và phân loại với các cây quyết định học được 27
  28. 4.3. Phân loại dữ liệu với mạng Bayesian Dựa trên định lý của Bayes ◼ Phân loại Nạve Bayesian Giả định: độc lập cĩ điều kiện lớp (class conditional independence) ◼ Phân loại Bayesian belief networks Phương pháp phân loại dựa trên xác suất 28
  29. 4.3. Phân loại dữ liệu với mạng Bayesian Reverend Thomas Bayes (1702-1761) 29
  30. 4.3. Phân loại dữ liệu với mạng Bayesian Định lý Bayes Cho một RID, RID thuộc về lớp “yes” (buys_computer = yes) ◼ X: một tuple/đối tượng (evidence) ◼ H: giả thuyết (hypothesis) X thuộc về lớp C. X X được xác định bởi trị của các thuộc tính. 30
  31. 4.3. Phân loại dữ liệu với mạng Bayesian Định lý Bayes ◼ P(H|X): posterior probability Xác suất cĩ điều kiện của H đối với X. Ví dụ: P(buys_computer=yes|age=young, income=high) là xác suất mua máy tính của khách hàng cĩ tuổi “young” và thu nhập “high”. ◼ P(X|H): posterior probability Xác suất cĩ điều kiện của X đối với H. Ví dụ: P(age=young, income=high|buys_computer=yes) là xác suất khách hàng mua máy tính cĩ tuổi “young” và thu nhập “high”. ▪ P(age=young, income=high|buys_computer=yes) = 0 ▪ P(age=young, income=high|buys_computer=no) = 2/5 = 0.4 31
  32. 4.3. Phân loại dữ liệu với mạng Bayesian Định lý Bayes ◼ P(H): prior probability Xác suất của H Ví dụ: P(buys_computer=yes) là xác suất mua máy tính của khách hàng nĩi chung. ▪ P(buys_computer=yes) = 9/14 = 0.643 ▪ P(buys_computer=no) = 5/14 = 0.357 ◼ P(X): prior probability Xác suất của X Ví dụ: P(age=young, income=high) là xác suất khách hàng cĩ tuổi “young” và thu nhập “high”. ▪ P(age=young, income=high) = 2/14 = 0.143 32
  33. 4.3. Phân loại dữ liệu với mạng Bayesian Định lý Bayes ◼ P(H), P(X|H), P(X) cĩ thể được tính từ tập dữ liệu cho trước. ◼ P(H|X) được tính từ định lý Bayes. P(X | H)P(H) P(H | X ) = P(X ) P(buys_computer=yes|age=young, income=high) = P(age=young, income=high|buys_computer=yes)P(buys_computer=yes)/P(age=young, income=high) = 0 P(buys_computer=no|age=young, income=high) = P(age=young, income=high|buys_computer=no)P(buys_computer=no)/P(age=young, income=high) = 0.4*0.357/0.143 = 0.9986 33
  34. 4.3. Phân loại dữ liệu với mạng Bayesian Cho trước tập dữ liệu huấn luyện D với mơ tả (nhãn) của các lớp Ci, i=1 m, quá trình phân loại một tuple/đối tượng X = (x1, x2, , xn) với mạng Bayesian như sau: ◼ X được phân loại vào Ci nếu và chỉ nếu P(Ci|X) > P(Cj|X) với 1 i P(X | C )P(C ) P(C | X ) = i i i P(X ) → Tối đa hĩa P(Ci|X) (i.e. chọn Ci nếu P(Ci|X) là trị lớn nhất) → Tối đa hĩa P(X|Ci)P(Ci) → P(C1) = P(C2) = = P(Cm) hoặc P(Ci) = |Ci,D|/|D| 34
  35. 4.3. Phân loại dữ liệu với mạng Bayesian n P(X | Ci ) =  P(xk | Ci ) = P(x1 | Ci )* P(x2 | Ci )* * P(xn | Ci ) k=1 P(X|Ci) được tính với giả định class conditional independence. xk, k = 1 n: trị thuộc tính Ak của X P(xk|Ci) được tính như sau: ◼ Ak là thuộc tính rời rạc. P(xk|Ci) = |{X’|x’k = xk  X’ Ci}|/|Ci,D| ◼ Ak là thuộc tính liên tục. P(xk|Ci) tuân theo một phân bố xác suất nào đĩ (ví dụ: phân bố Gauss). 35
  36. 4.3. Phân loại dữ liệu với mạng Bayesian Nếu P(xk|Ci) = 0 thì P(X|Ci) = 0!!! ◼ Ban đầu P(xk|Ci) = |{X’|x’k = xk  X’ Ci}|/|Ci,D| ◼ Laplace (Pierre Laplace, nhà tốn học Pháp, 1749-1827) P(xk|Ci) = (|{X’|x’k = xk  X’ Ci}|+1)/(|Ci,D| + m) ◼ z-estimate P(xk|Ci) = (|{X’|x’k = xk  X’ Ci}| + z*P(xk))/(|Ci,D| + z) 36
  37. 4.3. Phân loại dữ liệu với mạng Bayesian C1 = {X’|X’.buys_computer = yes} C2 = {X’’|X’’.buys_computer = no} → X C 1 37
  38. 4.4. Phân loại dữ liệu với mạng Neural Mạng Neural sinh học 38
  39. 4.4. Phân loại dữ liệu với mạng Neural Quá trình xử lý thơng tin tại một neuron của mạng Neural nhân tạo 39
  40. 4.4. Phân loại dữ liệu với mạng Neural Mạng neural feed-forward đa tầng 40
  41. 4.4. Phân loại dữ liệu với mạng Neural Giải thuật học lan truyền ngược (Backpropagation) cĩ giám sát 41
  42. 4.4. Phân loại dữ liệu với mạng Neural 42
  43. 4.4. Phân loại dữ liệu với mạng Neural Output vector Errj = O j (1−O j ) Errk wjk Output nodes k  j = j + (l)Errj wij = wij + (l)ErrjOi Hidden nodes Errj = Oj (1−Oj )(Tj −Oj ) wij 1 O j = 1+ e−I j Input nodes I j =  wijOi + j i Input vector: xi 43
  44. 4.4. Phân loại dữ liệu với mạng Neural 44
  45. 4.4. Phân loại dữ liệu với mạng Neural 45
  46. 4.4. Phân loại dữ liệu với mạng Neural 46
  47. 4.5. Các phương pháp phân loại dữ liệu khác Phân loại k-nn (k-nearest Unknown record neighbor) ◼ Cho trước tập dữ liệu huấn luyện D với các lớp, phân loại record/object X vào các lớp dựa vào k phần tử tương tự với X nhất (dùng luật số đơng: majority vote) ◼ Phụ thuộc Độ đo khoảng cách để xác định sự tương tự. Trị k, số phần tử láng giềng → k <= |D|1/2 47
  48. 4.5. Các phương pháp phân loại dữ liệu khác Chọn độ đo 2 ◼ Độ đo Euclidean d( p,q) =  ( p − q ) i i i Chọn trị k ◼ Nếu k quá nhỏ thì kết quả dễ bị ảnh hưởng bởi nhiễu. ◼ Nếu k quá lớn thì nhiều phần tử láng giềng chọn được cĩ thể đến từ các lớp khác. k quá lớn! X 48
  49. 4.5. Các phương pháp phân loại dữ liệu khác X X X (a) 1-nearest neighbor (b) 2-nearest neighbor (c) 3-nearest neighbor X MINUS X MINUS X PLUS hay X PLUS ? 49
  50. 4.6. Tĩm tắt Classification với Decision trees ◼ ID3, C4.5, CART Classification với mạng Bayesian ◼ Dựa trên lý thuyết xác suất thống kê Classification với mạng Neural K-nn classification ◼ Dựa trên khoảng cách 50
  51. Hỏi & Đáp 51