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 - Lớp HTTT + Pháp - Năm học 2009 - 2010

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 - Lớp HTTT + Pháp - Năm học 2009 - 2010

1. 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
2. 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ị
3. 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
4. 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
5. 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;
6. 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
7. Phân tích TD Khang – ĐHBK Hà Nội
8. 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
9. 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
10. 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)
11. 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)
12. 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
13. 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)
14. 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)
15. 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
16. 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
17. 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
18. 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"
19. 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
20. 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
21. 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)
22. Ứ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
23. 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