Bài giảng Hệ trợ giúp quyết định - Bài 4+5+6: Các mô hình ra quyết định với sự không chắc chắn

Nội dung text: Bài giảng Hệ trợ giúp quyết định - Bài 4+5+6: Các mô hình ra quyết định với sự không chắc chắn

1. HỆ TRỢ GIÚP QUYẾT ĐỊNH Lớp HTTT + Pháp Nămhọc 2009 - 2010
2. Bài 4, 5, 6 – Các mô hình ra quyết định vớisự không chắcchắn TD Khang – ĐHBK Hà Nội 3.3. Các mô hình ra quyết định vớisự không chắcchắn: NỘI DUNG : -Ra quyết định đathuộctinh -Toántử tích hợp -Quanhệ so sánh
3. Mô hình bài toán đathuộc tính, đamục tiêu, đa tiêu chuẩn TD Khang – ĐHBK Hà Nội
4. A/ Ra quyết định đathuộc tính TD Khang – ĐHBK Hà Nội Lựachọn trong số các phương án được đặctrưng bởi nhiềuthuộctính Dạng bảng biểudiễn giá trị củacácphương án tại các thuộctínhtương ứng | Các thuộctính Các phương án | Các giá trị
5. Thuộctính z Chuẩn hoá các giá trị củamộtthuộctính - Đơn điệu: tuyến tính: rij = xij / xj*, vớixj* là giá trị lớnnhất (lợi ích) (nhỏ nhất-thuộc tính giá) trong miền giá trị thuộctínhXj 2 1/2 vectơ: rij = xij / (Σi xij ) 2 0 - Không đơn điệu: rij = exp(-z /2), z= (xij –xj ) / σj - Định tính z Trọng số củacácthuộc tính: wj∈[0,1], Σ wj =1
6. Các phương pháp z Phương pháp TRỘI A1 → A2 (A1 trộihơnA2), nếucácgiátrịđềutốt hơnhoặctương đương ở tấtcả các thuộctính Chọn các ph/án không bị phương án khác trộihơn z HỘI: Mỗithuộctínhđềucógíatrị Ngưỡng, chọn phương án mà mọigíatrị thuộctínhđềutốthơn Ngưỡng tương ứng z TUYỂN: Chọnphương án có ít nhấtmột giá trị tốt hơnNgưỡng tương ứng
7. Các phương pháp z Loạibỏ dần: 1 Xét thuộc tính X1, chọnA = {Ai | xi1 thoả X1} Tiếptục xét các thuộctínhtiếp theo để loạibỏ max z MAXIMAX: li = maxj {xij} max max ChọnAk, nếulk = maxi {li } min z MAXIMIN: li = minj {xij} min min ChọnAk, nếulk = maxi {li }
8. TOPSIS (Technique for Order Prefe- rence by Similarity to Ideal Solution z Quan sát thêm các phương án lý tưởng với các giá trị tốtnhất(xấunhất) ở các thuộctính, sau đó tính khoảng cách và độ tương tự của các phương án so vớicácphương án lý tưởng z Dựavàođó để sắpxếpthứ tự hoặclựachọn
9. TOPSIS (Technique for Order Prefe- rence by Similarity to Ideal Solution z Bước1: chuẩn hoá, đưa các giá trị về rij ∈[0,1] z Bước 2: tính giá trị theo trọng số vij = rij * wj z Bước 3: tính các giảipháplýtưởng A* = (v1*,v2*, ,vm*), vớivj* là giá trị tốtnhấtcủaXj - - - - - A = (v1 ,v2 , ,vm ), vớivj là giá trị tốtnhấtcủaXj z Bước 4: tính khoảng cách 2 1/2 - - 2 1/2 Si* = (Σj (vij-vj*) ) , Si = (Σj (vij-vj ) ) - - z Bước 5: tính độ tương tự: Ci* = Si / (Si*+Si )
10. ELECTRE (Elimination et choix traduisant la realité) z Bước1: chuẩn hoá, đưa các giá trị về rij ∈[0,1] z Bước 2: tính giá trị theo trọng số vij = rij × wj z Bước 3: tính tập phù hợp và không phù hợp C(p,q) = { j | vpj ≥ vqj}, D(p,q) = { j | vpj <vqj} z Bước 4: tính chỉ số phù hợp và không phù hợp Cpq= Σ wj*, vớij*∈C(p,q), Dpq= (Σj* |vpj*-vqj*|) / (Σj |vpj-vqj|), vớij*∈D(p,q), j=1, , m z Bước5;
11. ELECTRE (Elimination et choix traduisant la realité) z Bước5: Tính C, D bằng trung bình các chỉ số Cpq, Dpq Có Ap trộihơnAq, nếuCpq ≥ C và Dpq < D Đồ thị Trội Lõi K của Đồ thị Trội bao gồmcácđỉnh không bịđỉnh nào khác trộihơn, mỗi đỉnh không thuộclõiK đềubị một đỉnh thuộc K trộihơn z Chọncácphương án trong K
12. Xây dựng bảng quyết định TD Khang – ĐHBK Hà Nội -Xácđịnh các thuộctínhđiềukiện ảnh hưởng đến quyết định, các khả năng có thể xảyravớitừng điều kiện Î Cộtcủabảng -Xácđịnh các phương án có thể Î Hàng củabảng - Điền vào các giá trị tương ứng các phương án và thuộctính
13. Ví dụ: Bài toán đầutư TD Khang – ĐHBK Hà Nội Có 3 mặthàngđầutư sảnxuất: Bia rượu, quầnáovàthuốclá. Thông tin về lợi nhuậnphụ thuộc vào tình trạng nềnkinhtế đượcchonhư sau: Đầutư Kinh tế phát triểnKinhtế trì trệ Lạm phát Quần áo 12% 6% 3% Bia rượu 15% 3% -2% Thuốc lá 6,5% 6,5% 6,5% (Nếunềnkinhtế phát triển, đầutư quầnáosẽ sinh lợi 12% ) Mụctiêu: Phải đầutư thế nào để lợi nhuậnlớnnhất sau 1 năm
14. Phân tích TD Khang – ĐHBK Hà Nội
15. Lờigiải TD Khang – ĐHBK Hà Nội Tiếpcậnlạc quan : Lựachọncáitốtnhất trong các cái tốtnhấtcóthể (MaxiMax) - ! Bia rượu Tiếpcận bi quan : Lựachọn cái tốtnhất trong các cái tồinhấtcóthể (MaxiMin) - ! Thuốclá Xử lý mạohiểm: Giảđịnh khả năng kinh tế phát triển được ước tính là 50%, trì trệ là 30% và lạmphátlà 20%. Có thể tính đượcgiátrị kỳ vọng củalợi nhuận khi đầutư -! Quầnáo
16. Nhậnxét TD Khang – ĐHBK Hà Nội Sự không chắcchắn, thiếu thông tin: các cách tiếpcận lạc quan, bi quan, mạohiểm Đamục tiêu: tích hợpcácmục tiêu Bảng quyết địnhkhicóítphương án chọn
17. CÂY QUYẾT ĐỊNH TD Khang – ĐHBK Hà Nội Cây quyết định là mộtcấutrúccây, ánhxạ quan sát về mộtthuộctínhthànhkếtluậnvề giá trị mong đợi củathuộctínhđó Cây gồm các nút quyết định, các nhánh và các lá Mỗi nút quyết định mô tả mộtphépthử X nào đó, mỗi nhánh củanúttương ứng vớimộtkhả năng chọn củaX Mỗilágắnvớimộtnhãnlớp
18. Ví dụ TD Khang – ĐHBK Hà Nội David quảnlýmộtcâulạcbộ Golf, gặpvấn đề về số lượng khách, có ngày có khách đếnchơi, các nhân viên làm không hếtviệc, có ngày không có khách, cácnhânviênlạicónhiềuthờigianrỗi. Do đó David muốndựđoán trước khi nào các khách hàng sẽđếnchơi golf để bố trí nhân viên. Thờitiết đóngvaitròquantrọng
19. Cây quyết định TD Khang – ĐHBK Hà Nội Chơi 9, không 5 TRỜI (Nắng,Mây,Mưa) Chơi 2, không 3 Chơi 4, không 0 Chơi 3, không 2 ĐỘ ẨM ( 70) GIÓ(Đúng,Sai) Chơi 2, không 0 Chơi 0, không 3 Chơi 0, không 2 Chơi 3, không 0 Kếtluận: Nếutrờinhiềumâythìchắcchắncókhách đếnchơi, nếutrờinắng và độ ẩm >70%, hoặctrời mưa, có gió thì không có khách đếnchơi
20. Các công thức TD Khang – ĐHBK Hà Nội m 2 Gini Impurity (sự hỗntạp): IG(i) = 1 - Σ j=1 f(i,j) , với f(i,j) là tầnsuấtgiátrị j tại nút i, IG(i) đạtmin ( =0 ), nếutấtcả các trường hợpcủa nút đềuchỉ nhậnmộtgiátrị Information Gain (độ đo mang tin): m IE(i) = - Σ j=1 f(i,j) log 2 f(i,j), entropy Misclassification Measure (độ đophânlớpsai): IM(i) = 1 - max j f(i,j)
21. Ưu điểmcủa cây quyết định TD Khang – ĐHBK Hà Nội - Đơngiảnvàtrực quan: mọingườicóthể hiểucây quyết định thông qua các giảithíchngắngọn - Không đòi hỏi nhiềuthờigianchuẩnbị dữ liệu, không cầnchuẩnhóa -Cóthể xử lý các kiểudữ liệu khác nhau: số, danh sách, logic, -Sử dụng mô hình "hộptrắng" -Dễ dàng thử lại, đánh giá -Mạnh, hiệuquả, ngay cả vớitậpdữ liệulớn, thờigian xử lý ngắn Î thích hợp cho phân tích ra quyết định
22. Nhậnxét TD Khang – ĐHBK Hà Nội Chuyển thành luật Phân lớp, khai phá dữ liệu Tỉacây(tỉa cây trước-cùngvớidựng cây, tỉa cây sau, sai số tỉacây) , khử nhiễu Bảng quyết định - Cây quyết định - Mạng quyết định (có thêm nút HOẶC)
23. B/ Toán tử tích hợp TD Khang – ĐHBK Hà Nội z Trongquátrìnhraquyết định, ngườitathường phảikếtnhậpnhiều thông tin lại để lấyramộtkết quả tổng quát, ví dụ khi phải xét cùng một lúc nhiều tiêu chuẩn, khi có nhiềuý kiến đánh giá của chuyên gia, z Mộtcáchhìnhthức, nếux1, , xn là nhóm các dữ liệu, thì Agg(x1, ,xn)=a là hàm tích hợp, cho giá trị đầuratheoyêucầu z Toán tử tích hợpnằmgiữa phép toán hộivàphép tuyển
24. Phép hội và phép tuyển TD Khang – ĐHBK Hà Nội Toán tử t-norm (phép hội) t: [0,1] x [0,1] → [0,1] t(x,y) = t(y,x) t(x,y) ≤ t(z,u), ∀x≤y, z≤u t(x, t(y,z)) = t( t(x,y), z) t(x,1) = x Toán tử s-conorm (phép tuyển) s: [0,1] x [0,1] → [0,1] s(x,y) = s(y,x) s(x,y) ≤ s(z,u), ∀x≤y, z≤u s(x, s(y,z)) = s( s(x,y), z) s(x,0) = x Toán tử phủđịnh n: [0,1] → [0,1] thỏamãn n(0) = 1, n(1) = 0 n(x) ≤ n(y), ∀x≥y
25. Tính chất TD Khang – ĐHBK Hà Nội Toán tử tích hợpthường thỏamãnmộtsố tích chấtsau: (1) Giớihạntự nhiên: Khi chỉ có 1 phầntử vào thì kếtquả chính là giá trịđó: Agg(a)=a (2) Tựđồng nhất: Nếu a=Agg(x1, ,xn) thì Agg(x1, ,xn,a)=Agg(x1, ,xn)=a (3) Đơn điệu: Nếuai≤bi ∀i=1 n thì Agg(a1, ,an) ≤ Agg(b1, ,bn) (4) Kếthợp: Agg(x,y,z)=Agg(x,Agg(y,z))=Agg(Agg(x,y),z) (5) Giao hoán: Agg(x1, ,xn)= Agg(X1, ,Xn) với(X1, ,Xn) là mộthoánvị bấtkỳ của(x1, ,xn)
26. Nhậnxét TD Khang – ĐHBK Hà Nội - Toán tử tích hợp không cầnthỏamãntấtcả các tính chất trên, nhưng thường thỏa mãn (1), (2), (3) - Từ tính chất (1), (2) có thể chứng minh đượctính lũy đẳng Agg(a, ,a)=a - Đặta=mini [xi], b=maxi[xi] thì có tính bù trừ được suy ra từ (1), (2), (3): a≤Agg(x1, , xn)≤b - Từ (2), (3), nếu K>Agg(x1, ,xn) thì Agg(x1, ,xn,K) ≥ Agg(x1, ,xn) NếuK<Agg(x1, ,xn) thì Agg(x1, ,xn,K) ≤ Agg(x1, ,xn)
27. Mộtsố lớp các toán tử tích hợp TD Khang – ĐHBK Hà Nội Ngườitathường chia toán tử tích hợp thành nhiềulớp con, các toán tử trong mỗilớplạithỏa mãn thêm mộtsố tính chất đặctrưng củalớp đó. -Lớptoántử tích hợp“trungbình” α α 1/α Agg(x1, ,xn) = ( (x1 + + xn ) / n ) , với α∈R, α≠0 -Lớptoántử tích hợpcótrọng số tuyếntính Aggw(x1, ,xn) = ∑wixi , vớiwi≥0, ∀i và ∑wi=1 Lớptoántử trungbìnhcótrọng số sắpthứ tự (OWA) -Lớpcáctoántử tích hợp Uninorm Agg(a,e) = a
28. Toán tử OWA TD Khang – ĐHBK Hà Nội Mộttoántử OWA n-chiềulàmộtánhxạ f: Rn → R, fw (a1, ,an) = ∑wibi, vớicáctrọng số W = {w1, w2, , wn}, wi≥0, ∀i và ∑wi=1, trong đó(b1, ,bn) là hoán vị không tăng của(a1, ,an)
29. Nhậnxét TD Khang – ĐHBK Hà Nội (1) Toán tử OWA nhận giá trị giữa min và max * * W = {1, 0, , 0}, F (a1, , an) = max {ai} W* = {0, 0, , 1}, F*(a1, , an) = min {ai} Wave = {1/n, 1/n, , 1/n}, Fave (a1, , an) = Σxi / n (2) Toán tử OWA thỏa mãn tính chất giao hoán: Cho {d1, , dn} là một hoán vị bấtkỳ của(a1, , an), ta đềucóF(d1, , dn) = F(a1, , an), ∀ F (3) Toán tử OWA thỏa mãn tính chất đơn điệu: Cho ai ≤ ci, ∀i thì F(a1, , an) = F(c1, , cn) (4) Toán tử OWA thỏa mãn tính chấtlũy đẳng: F(a, ,a) = a
30. Các tiêu chuẩn đánh giá toán tử OWA TD Khang – ĐHBK Hà Nội Tiêu chuẩn Entropy : Sự phân bố củacáctrọng số Disp (W) = - Σ wi.ln wi n Tính HOẶC: Orness (W) = (1 / (n-1)) . Σ i=1 (n-i ) wi Tính VÀ: Andness (W) = 1 - Orness (W) Nếu Orness (W) > 0.5 : nghiêng về phép tuyển Nếu Orness (W) < 0.5 : nghiêng về phép hội
31. Xây dựng vector trọng số từ dữ liệu thựctế TD Khang – ĐHBK Hà Nội i i Giả sử có m bộ dữ liệu, mỗibộ (n+1) số dướidạng (a 1, a 2, i i , a n, y ), 1≤ i ≤m, Cầnxâydựng bộ trọng số W i i i i i i Gọi(b1, b 2, , b n) là hoán vị không tăng của(a1, a 2, , a n), thì để tính W, cầngiảihệ phương trình n ẩnsau: 1 1 1 1 b 1 w1 + b 2 w2 + + b n wn = y 2 2 2 2 b 1 w1 + b 2 w2 + + b n wn = y . . . m m m m b 1 w1 + b 2 w2 + + b n wn = y w1 + w2 + + wn = 1 wi ∈ [0,1]
32. Các họ toán tử OWA TD Khang – ĐHBK Hà Nội Toán tử SO-OWA Toán tử SA-OWA Toán tử S-OWA Toán tử Step-OWA Toán tử Window-OWA Toán tử BADD-OWA
33. C/ Quan hệ so sánh TD Khang – ĐHBK Hà Nội Quan hệ so sánh giá trị giữacácphương án chọn: Quan hệ thứ tự Quan hệưathíchhơn Quan hệ xấpxỉ Quan hệ tương tự Dựavàođó, để sắpthứ tự các phương án
34. Quan hệ nhị phân rõ TD Khang – ĐHBK Hà Nội Cho A là tậpcácphương án chọn, R là quan hệ nhị phân thứ tự yếu, nếuvớia,b ∈A có R (a,b) = 1, nếu a không tồihơnb 0, ngượclại Quan hệ nhị phân thứ tự yếuthỏamãntínhchấtphản xạ R (a,a) = 1
35. Phân chia PIJ TD Khang – ĐHBK Hà Nội Từ quan hệ nhị phân thứ tự yếu R, có thể chia thành 3 quan hệ nhị phân khác là: - P(a,b) = 1, nếua tốthơnb, Quan hệ thứ tự chặt 0, ngượclại P(a,b) ⇔ R(a,b) and not R(b,a) - I(a,b) Quan hệ không khác nhau I(a,b) ⇔ R(a,b) and R(b,a) - J(a,b) Quan hệ không sánh đượcvớinhau J(a,b) ⇔ not R(a,b) and not R(b,a) Lưuý: Từ R(a,b) và R(b,a) có thể tính được P(a,b), P(b,a), I(a,b), J(a,b)
36. Mở rộng cho quan hệ mờ TD Khang – ĐHBK Hà Nội Quan hệ nhị phân mờ nhậngiátrị trong [0,1] Cho A là tậpcácphương án chọn, R là quan hệ thứ tự (mờ), nềuvớia,b∈A, có R(a,b) thể hiệnmức độ đúng củamệnh đề "a không tồihơnb"
37. Cấutrúcthứ tự (P,I,J) trên [0,1] TD Khang – ĐHBK Hà Nội Mở rộng cấu trúc (P,I,J) rõ, ta có: S ( p(x, N(y)), i(x,y) ) = x (vì P∪I=R, với S là phép tuyển) T ( p(x,y), j(x,y) ) = 0 (vì P∩J=∅, với T là phép hội) j(x,y) = i (N(x), N(y)) Như vậy, cầnphảichọn thỏamãn các tính chấttrên
38. Baohàmgiátrị TD Khang – ĐHBK Hà Nội Cho A là tậpcácphương án chọn, mộthọ các ánh xạ Σ = {C}, vớiC: A→[0,1] đượcgọilàmột bao hàm giá trị củaA, nếu supC∈Σ C(a) = 1, ∀a∈A
39. Quan hệ xấpxỉ TD Khang – ĐHBK Hà Nội Cho A là tậpcácphương án chọn, cho bao hàm giá trị Σ={C} của A, thì RΣ(a,b) = supC∈Σ min {C(a), C(b)} đượcgọilàmột quan hệ xấpxỉ Quan hệ xấpxỉ có tính chấtphảnxạ RΣ(a,b) = 1 và đốixứng RΣ(a,b) = RΣ(b,a)
40. Quan hệ tương tự TD Khang – ĐHBK Hà Nội Quan hệ R trên A có tính chấtT-bắccầu(T làmột t-norm), nếu T ( R(a,c), R(c,b) ) ≤ R(a,b) ∀c∈A, ∀a,b∈A Quan hệ R trên A là mộtquanhệ T-tương tự, nếuR là mộtquanhệ xấpxỉ và có tính chấtT-bắccầu Như vậy, quan hệ tương tự có tính chấtphảnxạ, đối xứng và bắccầu
41. Bao đóng bắccầu TD Khang – ĐHBK Hà Nội m m-1 Cho R = R oT R , vớim>1 ^ m Thì R (a,b) = supm R (a,b) là bao đóng bắccầucủaR Ta có: R^ có tính chấtT-bắccầu (VớioT là phép hợp thành Sup-T: Cho R xác đ ịnh trên UxV, S xác định trên VxW, thì (R oT S) (a,c) = supb∈V T ( R(a,b), S(b,c) ) )
42. Quan hệưa thích hơn TD Khang – ĐHBK Hà Nội Choquanhệưathíchhơn R trên tậpphương án chọnA Ta có các hàm cho điểmsauđây: SL(a,R) = Σc∈A\{a} R(a,c) là tổng sựưathíchhơncủa a so vớicácphương án khác SE(a,R) = - Σc∈A\{a} R(c,a) là đổidấutổng sựưa thích hơncủacácphương án khác so vớia SL|E(a,R) = SL(a,R) + SE(a,R)
43. Tính trội, bị trội TD Khang – ĐHBK Hà Nội Từ quan hệưathíchhơnR : AxA→ [0,1], tính được quan hệ trộihơn P P(a,b) = max { R(a,b) - R(b,a), 0 } ∈ [0,1] Ta có các độ đo: -Mức độ không bị trộihơncủa a theo quan hệ R μND (a,R) = minc∈A {1 - P(c,a) } = 1 - maxc∈A P(c,a) -Mức độ không trộihơncủa a theo quan hệ R μNd (a,R) = minc∈A {1 - P(a,c) } = 1 - maxc∈A P(a,c)
44. Ứng dụng TD Khang – ĐHBK Hà Nội Quan hệ xấpxỉ, quan hệ tương tựđược ứng dụng trong các bài toán khai phá dữ liệu, phân lớp, xác định phụ thuộcdữ liệu, Quan hệưathíchhơn, quan hệ trộihơntrongcácbài toán sắpthứ tự, lựachọn, , lấy các độ đoSL(a,R), SE(a,R), SL|E(a,R), μND (a,R) lớnnhất, μNd (a,R) nhỏ nhất
45. Ví dụ TD Khang – ĐHBK Hà Nội Bài toán phân lớp Bài toán sắpthứ tự Bài toán ra quyết định đa tiêu chuẩn
46. Tổng kết TD Khang – ĐHBK Hà Nội Cácmôhìnhraquyết định cho các lớp bài toán khác nhau Chọnlưamôhìnhphùhợp để tăng hiệuquả công việc Tiếptụcnghiêncứuvàpháttriển