Luận văn thạc sĩ: Ứng dụng hệ trợ giúp quyết định phục vụ công tác đền bù giải tỏa đất đai tại thành phố Đà Nẵng

Chia sẻ: Sdfas Vfdtg | Ngày: | Loại File: PDF | Số trang:26

Thêm vào BST

Báo xấu

83
lượt xem 20
download

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

Ứng dụng hệ trợ giúp quyết định phục vụ công tác đền bù giải tỏa đất đai tại thành phố Đà Nẵng nhằm triển khai áp dụng có hiệu quả công tác hỗ trợ ra quyết định trong đề bù giải tỏa đất đai.

Chủ đề:

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

Lưu

Nội dung Text: Luận văn thạc sĩ: Ứng dụng hệ trợ giúp quyết định phục vụ công tác đền bù giải tỏa đất đai tại thành phố Đà Nẵng

- 1- B GIÁO D C VÀ ĐÀO T O Đ I H C ĐÀ N NG H PHƯ C DUY NG D NG H TR GIÚP QUY T Đ NH PH C V CÔNG TÁC Đ N BÙ GI I TO Đ T ĐAI T I THÀNH PH ĐÀ N NG Chuyên ngành: KHOA H C MÁY TÍNH Mã s : 60.48.01 TÓM T T LU N VĂN TH C SĨ K THU T Đà N ng - 2010
- 2- Công trình ñư c hoàn thành t i Đ I H C ĐÀ N NG Ngư i hư ng d n khoa h c: PGS.TS. Phan Huy Khánh Ph n bi n 1: PGS.TS. Võ Trung Hùng Ph n bi n 2: PGS.TS. Lê M nh Th nh Lu n văn ñư c b o v t i H i ñ ng ch m Lu n văn t t nghi p Th c sĩ k thu t h p t i Đ i h c Đà N ng vào ngày 16 tháng 12 năm 2010. * Có th tìm hi u Lu n văn t i: - Trung tâm Thông tin - H c li u, Đ i h c Đà N ng - Trung tâm H c li u, Đ i h c Đà N ng.
- 3- M Đ U 1. Lý do ch n ñ tài Hòa cùng v i s phát tri n chung c a ñ t nư c v kinh t - xã h i, thành ph Đà N ng là m t trong nh ng thành ph tr , năng ñ ng và ñ y sáng t o trong công tác ch nh trang, quy ho ch ñô th . Vì v y vi c quy ho ch cơ s h t ng nh m ñáp ng v công tác ch nh trang ñô th là m t v n ñ mà Lãnh ñ o thành ph r t quan tâm. M t trong nh ng công tác h t s c quan tr ng và c c kỳ nh y c m trong công tác quy ho ch, ch nh trang ñô th ñó là công tác ñ n bù gi i t a. Tuy nhiên, v i m t khu v c c n ñ n bù gi i t a có di n tích l n vì th s lư ng h sơ khi ñ n bù gi i t a r t nhi u khi n công tác ñ n bù gi i t a ñôi khi gi i quy t không k p th i, quá t i d n ñ n thi u sót và ñ c bi t r t khó khăn trong vi c ñ n bù và b trí tái ñ nh cư. Bên c nh ñó, vi c ñưa ra quy t ñ nh xem xét ñ n bù gi i t a cho nhi u h sơ cùng m t th i ñi m là v n ñ r t nan gi i và vô cùng ph c t p d d n ñ n nh ng quy t ñ nh chưa th t s th a ñáng. Trong quy trình ñ n bù gi i t a khâu quan tr ng nh t và nh y c m nh t, ñ ng th i gây nh hư ng l n nh t ñ i v i quy n l i c a ngư i dân ñó chính là vi c ra quy t ñ nh b trí ñ t tái ñ nh cư cho các h trong khu v c b gi i t a. Trư ng h p nào thì s ñư c b trí ñ n bù Lô ñ t chính, Lô ñ t ph , Chung cư hay k t h p m t trong nh ng k t qu trên. Vì v y m t trong nh ng gi i pháp h u hi u nh t nh m kh c ph c các v n ñ nêu trên là ti n hành tri n khai xây d ng m t h th ng tr giúp ra quy t ñ nh trong công tác ñ n bù gi i t a. Đó là m t h th ng ñư c thi t k giúp cho lãnh ñ o ñơn v , lãnh ñ o thành ph n m b t ñư c m t cách t ng quát v tình hình ñ n bù nh m ñưa ra nh ng quy t
- 4- ñ nh có tính công b ng và chính xác cao liên quan ñ n công tác ñ n bù gi i t a t i ñơn v . Chính vì nh ng lý do nêu trên, tôi quy t ñ nh ch n ñ tài: “ ng d ng h tr giúp quy t ñ nh ph c v công tác ñ n bù gi i t a ñ t ñai t i thành ph Đà N ng” v i mong mu n ñóng góp thêm m t gi i pháp nh m h tr cho lãnh ñ o xem xét, gi i quy t nhu c u ñ n bù gi i t a ngày càng ph c t p và c p thi t c a thành ph nói chung và c a các ñơn v có ch c năng ñ n bù gi i t a nói riêng. 2. M c ñích nghiên c u Nh m tri n khai áp d ng có hi u qu cho công tác h tr ra quy t ñ nh trong ñ n bù gi i t a ñ t ñai t i Ban Qu n lý d án công trình ñư ng B ch Đ ng Đông, qu n Sơn Trà, thành ph Đà N ng. 3. Đ i tư ng và ph m vi nghiên c u Đ i tư ng nghiên c u Tìm hi u công tác ñ n bù gi i t a t i Ban Qu n lý d án công trình ñư ng B ch Đ ng Đông ñ ñ ra gi i pháp nh m ñem l i hi u qu cao hơn. Phân tích quy trình, nghiên c u k t qu trư c ñây t i ñơn v ñ ñ ra phương th c, cách th c xây d ng và tri n khai h th ng. Ph m vi nghiên c u ng d ng thu t toán ID3 ñ xây d ng cây quy t ñ nh ph c v công tác ñ n bù gi i t a. ng d ng, ph c v cho lãnh ñ o và Phòng chuyên môn trong công tác ñ n bù gi i t a t i Ban Qu n lý d án công trình ñư ng B ch Đ ng Đông. 4. Phương pháp nghiên c u Phương pháp nghiên c u lý thuy t Nghiên c u tài li u, ngôn ng và các công ngh có liên quan. T ng h p, thu th p các tài li u v công tác ñ n bù gi i t a.
- 5- Phương pháp nghiên c u th c nghi m Phân tích yêu c u th c t c a bài toán và áp d ng các thu t toán có liên quan ñ h tr vi c l p trình, xây d ng ng d ng. Quan sát th c t , th c nghi m công tác ñ n bù gi i t a. 5. K t qu d ki n Phân tích, tìm hi u ñư c công tác ñ n bù gi i t a. Đ ra gi i pháp và s d ng cây quy t ñ nh trong vi c xây d ng h th ng h tr ra quy t ñ nh trong công tác ñ n bù gi i t a. 6. Ý nghĩa khoa h c và th c ti n c a ñ tài V m t lý thuy t Tìm hi u quy trình, quy ñ nh, nguyên t c c a công tác ñ n bù gi i t a trên ñ a bàn thành ph . Đ xu t gi i pháp tri n khai ng d ng Cây quy t ñ nh vào trong h th ng ñ n bù gi i t a. V m t th c ti n S n ph m s là h th ng ph c v ñ c l c, k p th i và có ñ chính xác cao cho các cán b lãnh ñ o, cán b qu n lý, các cán b làm công tác chuyên môn trong lĩnh v c ñ n bù gi i t a. 7. C u trúc c a lu n văn N i dung chính c a lu n văn này ñư c chia thành ba chương v i n i dung như sau: Chương 1: Nghiên c u h tr giúp quy t ñ nh và h th ng h tr quy t ñ nh thông minh. Chương 2: Phân tích d li u, tính toán và tri n khai ng d ng cây quy t ñ nh vào bài toán ñ n bù gi i t a t i ñơn v . Chương 3: Ti n hành cài ñ t, cho ho t ñ ng th nghi m, nh n xét và ñánh giá, hi n th k t qu minh h a c a chương trình.
- 6- CHƯƠNG 1 NGHIÊN C U CÁC H TR GIÚP QUY T Đ NH 1.1. H TR GIÚP QUY T Đ NH 1.1.1. T ng quan v H tr giúp quy t ñ nh 1.1.2. Vai trò, ch c năng c a h tr giúp quy t ñ nh 1.1.3. C u trúc c a H tr giúp quy t ñ nh 1.1.3.1. Qu n lý d li u 1.1.3.2. Qu n lý mô hình 1.1.3.3. Qu n lý d a trên ki n th c 1.1.3.4. Giao di n ngư i dùng 1.1.4. Các lo i h th ng tr giúp quy t ñ nh 1.1.4.1. H tr giúp quy t ñ nh nhóm 1.1.4.2. H tr giúp quy t ñ nh m c xí nghi p 1.1.4.3. H qu n tr ki n th c 1.2. H TH NG H TR QUY T Đ NH THÔNG MINH 1.2.1. T ng quan v Trí tu nhân t o 1.2.2. Tri th c và các phương pháp suy di n 1.2.2.1. Tri th c 1.2.2.2. Các d ng bi u di n tri th c 1.2.2.3. Các phương pháp suy di n 1.2.3. Cây quy t ñ nh 1.2.3.1. T ng quan v cây quy t ñ nh 1.2.3.2. Các ki u cây quy t ñ nh 1.2.3.3. Phân l p d li u b ng cây quy t ñ nh Cây quy t ñ nh là m t trong nh ng hình th c mô t d li u tr c quan nh t, d hi u nh t ñ i v i ngư i dùng. C u trúc c a m t cây quy t ñ nh bao g m các nút và các nhánh. Nút dư i cùng ñư c g i là nút lá, trong mô hình phân l p d li u chính là các giá tr c a các nhãn l p
- 7- (g i t t là nhãn). Các nút khác nút lá ñư c g i là các nút con, ñây còn là các thu c tính c a t p d li u, hi n nhiên các thu c tính này ph i khác thu c tính phân l p. M i m t nhánh c a cây xu t phát t m t nút P nào ñó ng v i m t phép so sánh d a trên mi n giá tr c a nút ñó. Nút ñ u tiên ñư c g i là nút g c c a cây. 1.2.3.4. Gi i thu t hu n luy n cây quy t ñ nh cơ b n Gi i thu t quy n p cây ID3 là gì ? Gi i thu t quy n p cây ID3 là m t gi i thu t h c ñơn gi n nhưng t ra thành công trong nhi u lĩnh v c. ID3 là m t gi i thu t hay vì cách bi u di n tri th c h c ñư c c a nó, ti p c n c a nó trong vi c qu n lý tính ph c t p, x lý d li u nhi u. Gi i thu t ID3 xây d ng cây quy t ñ nh: Function Tree_ID3(t p_ví_d , t p_thu c_tính) begin if m i ví d trong t p_ví_d ñ u n m trong cùng m t l p then return m t nút lá ñư c gán nhãn b i l p ñó else if t p_thu c_tính là r ng then return nút lá ñư c gán nhãn b i tuy n c a t t c các l p trong t p_ví_d else begin ch n m t thu c tính P, l y nó làm g c cho cây hi n t i; xóa P ra kh i t p_thu c_tính; v i m i giá tr V c a P begin t o m t nhánh c a cây gán nhãn V; Đ t vào phân_vùngV các ví d trong t p_ví_d có giá tr V t i thu c tính P;
- 8- G i Tree_ID3(phân_vùngV, t p_thu c_tính), g n k t qu vào nhánh V end end end 1.2.3.5. Thu c tính phân lo i t t nh t Entropy ño tính thu n nh t c a t p hu n luy n Khái ni m Entropy c a m t t p S ñư c ñ nh nghĩa trong Lý thuy t thông tin là s lư ng mong ñ i các bít c n thi t ñ mã hóa thông tin v l p c a m t thành viên rút ra m t cách ng u nhiên t t p S. Trong trư ng h p t i ưu, mã có ñ dài ng n nh t. Theo lý thuy t thông tin, mã có ñ dài t i ưu là mã gán –log2p bits cho thông ñi p có xác su t là p. Trong trư ng h p S là t p ví d , thì thành viên c a S là m t ví d , m i ví d thu c m t l p hay có m t giá tr phân lo i. N u s lư ng giá tr phân lo i là 2 (phân lo i nh phân), Entropy có giá tr n m trong kho ng [0..1], Entropy(S) = 0 => t p ví d S ch toàn ví d thu c cùng m t lo i, hay S là thu n nh t. Entropy(S) = 1 => t p ví d S có các ví d thu c các lo i khác nhau v i ñ pha tr n là cao nh t. 0 < Entropy(S) < 1 => t p ví d S có s lư ng ví d thu c các lo i khác nhau là không b ng nhau. Đ ñơn gi n ta xét trư ng h p các ví d c a S ch thu c lo i âm (-) ho c dương (+). Cho trư c: T p S là t p d li u rèn luy n, trong ñó thu c tính phân lo i có hai giá tr , gi s là âm (-) và dương (+) * p+ là ph n các ví d dương trong t p S * p- là ph n các ví d âm trong t p S Khi ñó, Entropy ño ñ pha tr n c a t p S theo công th c sau: Entropy(S ) = - p+ log2p+ − p− log2p−
- 9- M t cách t ng quát hơn, n u các ví d c a t p S thu c nhi u hơn hai lo i, gi s là có c giá tr phân lo i thì công th c Entropy t ng quát là [13]: c Entropy ( S ) = ∑ i =1 - pi log2 pi Lư ng thông tin thu ñư c ño m c ñ gi m Entropy Entropy là m t s ño ño ñ pha tr n c a m t t p ví d , bây gi chúng ta s ñ nh nghĩa m t phép ño hi u su t phân lo i các ví d c a m t thu c tính. Phép ño này g i là lư ng thông tin thu ñư c, nó ñơn gi n là lư ng gi m Entropy mong ñ i gây ra b i vi c phân chia các ví d theo thu c tính này. M t cách chính xác hơn, Gain(S,A) c a thu c tính A, trên t p S, ñư c ñ nh nghĩa như sau [13]: | Sv | Gain(S,A) = Entropy(S) - ∑ v∈values ( A ) | S | Entropy(Sv) trong ñó values(A) là t p h p có th có các giá tr c a thu c tính A, và Sv là t p con c a S ch a các ví d có thu c tính A mang giá tr v. 1.2.3.6. Tìm ki m không gian gi thuy t trong ID3 Cũng như các phương pháp h c quy n p khác, ID3 cũng tìm ki m trong m t không gian các gi thuy t m t gi thuy t phù h p v i t p d li u rèn luy n. Không gian gi thuy t mà ID3 tìm ki m là m t t p h p các cây quy t ñ nh có th có. 1.2.4. Đánh giá hi u su t và t p lu t c a cây quy t ñ nh 1.2.4.1. Đánh giá hi u su t c a cây quy t ñ nh 1.2.4.2. Chuy n cây v các d ng lu t
- 10- CHƯƠNG 2 NG D NG CÂY QUY T Đ NH TRONG CÔNG TÁC Đ N BÙ GI I T A 2.1. KH O SÁT HI N TR NG 2.1.1. Gi i thi u v h th ng t ch c ñơn v 2.1.2. Phân tích quy trình và th c tr ng công tác ñ n bù gi i t a 2.1.3. Gi i pháp xây d ng và k ch b n h th ng h tr ra quy t ñ nh 2.2. TRI N KHAI NG D NG CÂY QUY T Đ NH 2.2.1. Phân tích d li u Di n tích (Dientich): Đây là di n tích ñ t b thu h i cho vi c gi i t a. Đ có th áp d ng cho gi i thu t ID3, ta c n r i r c hóa các giá tr này. D a vào các giá tr di n tích trong t p d li u, ta có th chia nó thành các kho ng sau: dư i 100 m2 (100-), t 100 m2 ñ n dư i 200 m2 (100+), t 200 m2 ñ n dư i 300 m2 (200+), t 300 m2 tr lên (300+). Như v y, t p các giá tr c a di n tích ñ t ñư c mô t như sau: Dientich = {100-; 100+; 200+; 300+} Nhân kh u (Nhankhau): s lư ng ngư i s ng t i h b gi i t a. Do ñó, t p các giá tr c a Nhân kh u ñư c cho như sau: Nhankhau = {8- ; 8+} Giá tr ñ n bù (Giatridenbu): Đây là s ti n mà nhà nư c ñ n bù cho h b gi i t a và ph thu c vào khu ñ t c a h gia ñình, nhà c a xây trên ñó, v t li u, ... Như v y, t p giá tr c a thu c tính Giá tr ñ n bù là: Giatridenbu = {50-; 50+; 100+; 150+; 300+} Ngu n g c (Nguongoc): th hi n ngu n g c v m nh ñ t và ngôi nhà, c a h gia ñình. T ñó, t p các giá tr c a thu c tính Ngu n g c là: Nguongoc = {TKP; CN}
- 11- Quy t ñ nh ñ n bù (Quyetdinh): Đây là quy t ñ nh mà Ban ñ n bù gi i t a th c hi n tương ng v i h sơ c a t ng h b gi i t a. T p giá tr c a Quy t ñ nh ñ n bù ñư c th hi n như sau: Quyetdinh = {Chinh; Phu; Chinh_cc; Chinh_phu} T b ng ch a t p d li u, b ng cách r i r c hóa các thu c tính, ta thu ñư c d li u ch a các giá tr r i r c dư i ñây. B ng 2.2. T p d li u hu n luy n sau khi r i r c hóa Dien Giatri Nhan Nguon STT tich denbu Quyetdinh khau goc (m2) (tri u ñ ng) 1 100+ 8+ 100+ TKP Chinh_cc 2 100- 8- 100+ TKP Chinh 3 100- 8- 150+ CN Chinh 4 100+ 8- 100+ CN Chinh 5 100+ 8- 150+ TKP Chinh 6 100+ 8- 50- CN Phu 7 100- 8- 50- TKP Phu 8 100- 8+ 100+ TKP Chinh 9 100+ 8- 50- TKP Phu 10 100+ 8- 50+ CN Phu 11 300+ 8+ 300+ TKP Chinh_phu 12 200+ 8+ 300+ CN Chinh_phu 13 200+ 8+ 300+ TKP Chinh_phu 14 100+ 8+ 150+ TKP Chinh_cc 15 100- 8+ 50+ TKP Chinh_cc 16 100+ 8+ 50+ TKP Chinh_cc
- 12- 2.2.2. Tri n khai gi i thu t ID3 Cây quy t ñ nh ñư c xây d ng b ng cách m r ng cây xu t phát t nút g c. Nút g c ñư c ñ t tên là nút 1, và ng v i m c 0 c a cây. Các nút con c a nút g c s ng v i m c 1, và ti p t c như v y. Thu c tính dùng ñ phân tích nút hi n th i. N u nút hi n th i là nút lá, thu c tính s b ng r ng. N u nút hi n th i không ph i là nút lá, nó s ch a tên các nút con xu t phát t nút hi n th i, cũng như các giá tr tương ng c a thu c tính dùng ñ phân tích nút hi n th i. N u là nút lá thì có thêm quy t ñ nh ñ u ra t i nút hi n th i. Ngư c l i, n u không ph i là nút lá thì không có ch a thông tin này. 2.2.3. Xây d ng cây quy t ñ nh Ta s b t ñ u vi c xây d ng cây quy t ñ nh t nút g c. Trư c tiên, t i nút g c s ch a toàn b d li u hu n luy n. Ta th y r ng, t i nút g c, t p S ch a các giá tr không ñ ng nh t. Rõ ràng t p S này không ñ ng nh t, hay Entropy khác không. Do ñó, ta c n ph i phân tích nút g c này ra thành các nút con v i m c ñích là kì v ng c a Entropy c a t p S s nh hơn. Trư c h t, Entropy c a t p S ñư c tính như sau: B ng 2.3. B ng s li u th hi n cách tính Entropy c a t p S S (Quyetdinh) S lư ng pi -pi.log2(pi) Entropy(S) Chinh 5 5/16 0.5244 Phu 4 4/16 0.5000 1.9772 Chinh_phu 3 3/16 0.4528 Chinh_cc 4 4/16 0.5000 Ti p theo ta s tính kì v ng c a Entropy c a t p S khi bi t trư c t ng thu c tính còn l i. V i m i t p con này, ta cũng tính ñư c t l (pi) c a các giá tr c a m c tiêu, và t ñó tính Entropy tương ng gi ng như trên. K t qu ñư c tóm t t b ng sau.
- 13- B ng 2.4. Entropy c a các t p con c a S phân chia theo thu c tính Di n tích pi S Dientich Chinh Chinh Entropy lư ng Chinh Phu phu cc 100- 5 3/5 1/5 0 1/5 1.3710 100+ 8 2/8 3/8 0 3/8 1.5613 200+ 2 0 0 1 0 0 300+ 1 0 0 1 0 0 Kì v ng c a Entropy c a t p S ñ i v i thu c tính di n tích là: EDientich = 5/16*1.3710+8/16 * 1.5613+2/16 * 0 +1/16 * 0=1.2091 Do ñó, ñ l i thông tin tương ng là: G(S,Dientich) = Entropy(S)-EDientich =1.9772-1.2091= 0.7681 M t cách tương t , ta tính ñư c kì v ng c a Entropy c a t p S ñ i v i thu c tính Nhân kh u, và ñ l i thông tin tương ng là: ENhankhau = 8/16*1 + 8/16*1.4056 = 1.2028 G(S,Nhankhau)= 1.9772 - 1.2028 = 0.7744 B ng 2.6. Entropy c a các t p con c a S theo thu c tính Giá tr ñ n bù pi Giatri S Chinh Chinh Entropy denbu lư ng Chinh Phu phu cc 50- 3 0 1 0 0 0 50+ 3 0 1/3 0 2/3 0.9183 100+ 4 3/4 0 0 1/4 0.8113 150+ 3 2/3 0 0 1/3 0.9183 300+ 3 0 0 1 0 0 V i thu c tính Giatridenbu, ta có: EGiatridenbu = 3/16*0+3/16*0.9183+4/16*0.8113 +3/16*0.9183+3/16*0 = 0.5472 G(S,Giatridenbu) = 1.9772 - 0.5472 = 1.4300
- 14- V i thu c tính Nguongoc, ta có k t qu sau: ENguongoc = 11/16*1.9363+5/16*1.5219 = 1.8068 G(S,Nguongoc) = 1.9772 - 1.8068 = 0.1704 K t qu so sánh c a b n thu c tính ñư c tóm t t b ng sau: B ng 2.8. B ng so sánh s li u c a 4 thu c tính Di n Nhân kh u Ngu n g c Giá tr tích ñ n bù Kì v ng 1.2091 1.2028 1.8068 0.5472 c a Entropy Đ l i 0.7681 0.7744 0.1704 1.4300 thông tin So sánh b n thu c tính Dientich, Nhankhau, Giatridenbu và Nguongoc, ta th y Giatridenbu cho ñ l i thông tin l n nh t, và ng v i kì v ng c a Entropy là nh nh t. Nói cách khác, thu c tính Giatridenbu có kh năng phân lo i t t nh t; do ñó, ta ch n thu c tính này làm thu c tính ñ phân lo i nút g c c a cây quy t ñ nh. Như v y, t i nút ñ u tiên c a cây quy t ñ nh, cây quy t ñ nh ñư c phân tích nh vào thu c tính Giatridenbu như sau: Giatridenbu 50- 50+ 100+ 150+ 300+ Phu ? ? ? Chinh_phu Hình 2.5. Cây quy t ñ nh ñư c tri n khai ñ n m c 1 Theo hình trên, t i các nút Phu và Chinh_phu, ta có Entropy b ng 0; nên ñó s là hai nút lá. Vi c phát tri n cây quy t ñ nh s d ng l i 2 nút này. V i các trư ng h p khác c a Giatridenbu, ta c n ti p t c xem xét các thu c tính khác ñ m r ng cây quy t ñ nh.
- 15- Ta ti p t c th c hi n gi i thu t ID3 ñ tìm ra thu c tính nào s ñư c s d ng v i các trư ng h p 50+, 100+, 150+ c a Giatridenbu. V i Giatridenbu = 50+, ta có t p d li u con như sau: B ng 2.9. B ng s li u tương ng v i giá tr ñ n bù = 50+ Dientich Nhankhau Nguongoc Quyetdinh 100+ 8- CN Phu 100- 8+ TKP Chinh_cc 100+ 8+ TKP Chinh_cc G i S1 là t p ch a các giá tr c a thu c tính Quyetdinh v i t p con này. Khi ñó, Entropy c a t p S1 là: Entropy(S1) = -1/3*log2(1/3) -2/3*log2(2/3) = 0.9183 M t cách tương t , ta tóm t t quá trình tính toán cho các thu c tính trong các b ng sau. B ng 2.10. Entropy c a các t p con c a S1 phân chia theo thu c tính Di n tích pi Dientich S lư ng Entropy Phu Chinh_cc 100- 1 0 1 0 100+ 2 1/2 1/2 1 Kì v ng c a Entropy c a t p S1: EDientich = 1/3*0+2/3*1 = 0.6667 Đ l i thông tin: G(S1,Dientich) = 0.9183-0.6667=0.2516 B ng 2.11. Entropy c a các t p con c a S1 theo thu c tính Nhân kh u pi Nhankhau S lư ng Entropy Phu Chinh_cc 8- 1 1 0 0 8+ 2 0 1 0
- 16- Kì v ng c a Entropy c a S1 và ñ l i thông tin ñư c tính như sau: ENhankhau = 1/3*0+2/3*0 = 0 G(S1,Nhankhau) = 0.9183-0 = 0.9183 Kì v ng c a Entropy c a S1 và ñ l i thông tin ñ i v i thu c tính Nguongoc ñư c tính như sau: ENguongoc = 2/3*0+1/3*0 = 0 G(S1,Nguongoc) = 0.9183-0 = 0.9183 V i Giatridenbu = 100+, ta có t p d li u con như sau: B ng 2.13. B ng s li u tương ng v i giá tr ñ n bù = 100+ Dientich Nhankhau Nguongoc Quyetdinh 100+ 8+ TKP Chinh_cc 100- 8- TKP Chinh 100- 8+ TKP Chinh 100+ 8- CN Chinh G i S2 là t p ch a các giá tr c a thu c tính Quyetdinh v i t p con này. Khi ñó, Entropy c a t p S2 là: Entropy(S2) = -1/4*log2(1/4) -3/4*log2(3/4) = 0.8113 M t cách tương t , ta xét ñ l i thông tin v i các thu c tính khác nhau như sau. B ng 2.14. Entropy c a các t p con c a S2 phân chia theo thu c tính Di n tích pi Dientich S lư ng Entropy Chinh Chinh_cc 100- 2 1 0 0 100+ 2 1/2 1/2 1 Kì v ng c a Entropy c a S2: EDientich = 2/4*1+2/4*0 = 0.5 Đ l i thông tin: G(S2,Dientich) = 0.8113 - 0.5 = 0.3113
- 17- M t cách tương t , ta thu ñư c k t qu ñ i v i thu c tính Nhankhau: ENhankhau = 2/4*0 + 2/4*1 = 0.5 G(S2,Nhankhau) = 0.8113 - 0.5 = 0.3113 Tương t , ta thu ñư c k t qu ñ i v i thu c tính Nguongoc: ENguongoc = 3/4*0.9183 + 1/4*0 = 0.6887 G(S2,Nguongoc) = 0.8113 - 0.6887 = 0.1226 V i Giatridenbu = 150+, ta có t p d li u con như sau: B ng 2.17. B ng s li u tương ng v i giá tr ñ n bù = 150+ Dientich Nhankhau Nguongoc Quyetdinh 100- 8- CN Chinh 100+ 8- TKP Chinh 100+ 8+ TKP Chinh_cc G i S3 là t p ch a các giá tr c a thu c tính Quyetdinh v i t p con này. Khi ñó, Entropy c a t p S3 là: Entropy(S3) = -1/3*log2(1/3) -2/3*log2(2/3) = 0.9183 Ta xét t ng thu c tính. B ng 2.18. Entropy c a các t p con c a S3 phân chia theo thu c tính Di n tích pi Dientich S lư ng Entropy Chinh Chinh_cc 100- 1 1 0 0 100+ 2 1/2 1/2 1 Kì v ng Entropy c a S3: EDientich = 1/3*0 + 2/3*1 = 0.6667 Đ l i thông tin: G(S3,Dientich) = 0.9183 - 0.6667 = 0.2516 Kì v ng c a Entropy c a S3: ENhankhau = 1/3*0 + 2/3*0 = 0 Đ l i thông tin: G(S3,Nhankhau) = 0.9183 - 0 = 0.9183 Kì v ng c a Entropy c a S3: ENguongoc= 1/3*0 + 2/3*1 = 0.6667 Đ l i thông tin: G(S3,Nguongoc) = 0.9183 - 0.6667 = 0.2516
- 18- Thu c tính Nhankhau cũng ñư c ch n ñ m r ng cây quy t ñ nh v i trư ng h p Giatridenbu = 150+. Cây quy t ñ nh bây gi s là: Giatridenbu 50- 50+ 100+ 150+ 300+ Phu Nhankhau Nhankhau Nhankhau Chinh_phu 8- 8+ 8- 8+ 8- 8+ Phu Chinh_cc Chinh ? Phu Chinh_cc Hình 2.6. Cây quy t ñ nh ñư c tri n khai ñ n m c 2. Như v y m c th hai, ta thu ñư c thêm năm nút lá (có entropy b ng 0). Ta s ti p t c phát tri n cây quy t ñ nh t i nút ñư c ñánh d u h i (?), v i t p d li u con như sau: B ng 2.21. B ng s li u tương ng v i nhân kh u >=8 Dientich Nguongoc Quyetdinh 100+ TKP Chinh_cc 100- TKP Chinh Ta d dàng nh n th y, n u ch n Dientich làm thu c tính phân lo i ti p theo ta s có Entropy b ng không. Ngư c l i, thu c tính Nguongoc cho Entropy khác không (1/2). Do ñó, thu c tính Dientich s ñư c ch n ñ phát tri n cây quy t ñ nh, và nó cũng s d ng l i sau nút này (vì có Entropy = 0). ñây, ta chú ý thu c tính Dientich. V i thu c tính này ch có 2 giá tr , 100- và 100+, cho t p con khác r ng. V i các giá tr
- 19- 200+ và 300+, ta không tìm ñư c quy t ñ nh c th d a trên d li u hu n luy n. Đ gi i quy t v n ñ này, có th có hai cách sau. Th nh t, gán lá "nul" cho các trư ng h p này (c th ñây là trư ng h p Dientich b ng 200+ và 300+). Khi ñó, cây quy t ñ nh s không ñưa ra ñư c quy t ñ nh n u ñi ñ n nút này. Th hai, các nút này ñư c gán cho l p có nhi u trư ng h p rơi vào nh t (xu t phát t cây con tương ng) [14]. Trong trư ng h p này, cây quy t ñ nh s gi i quy t ñư c t t c các tình hu ng. Ngoài ra, nó cũng cho k t qu hoàn toàn chính xác ñ i v i d li u hu n luy n. ñây, ta s l a ch n cách x lý th hai, nghĩa là ñ m b o ñư c là cây quy t ñ nh s luôn cho ñư c quy t ñ nh ñ u ra, ñ ng th i cũng th hi n chính xác d li u hu n luy n. Giatridenbu 50- 50+ 100+ 150+ 300+ Phu Nhankhau Nhankhau Nhankhau Chinh_phu 8- 8+ 8- 8+ 8- 8+ Phu Chinh_cc Chinh Dientich Phu Chinh_cc 100- 100+ 200+ 300+ Chinh Chinh_cc Chinh_cc Chinh_cc Hình 2.8. Cây quy t ñ nh ñư c xây d ng t CSDL hu n luy n trên
- 20- 2.3. NH N XÉT, ĐÁNH GIÁ 2.3.1. Nh n xét v cây quy t ñ nh ñ n bù gi i t a Trư c h t, cây quy t ñ nh ñư c xây d ng trên th hi n t t t t c các trư ng h p trong cơ s d li u hu n luy n. Ta cũng th y r ng không ph i t t c các trư ng h p ñ u ph i duy t qua toàn b các thu c tính ñ ñi ñ n quy t ñ nh. M t s trư ng h p ch c n 1 ho c 2 thu c tính là ñ ñ xác ñ nh quy t ñ nh ñ u ra. T ñó, ta th y m t ưu ñi m c a phương pháp cây quy t ñ nh là không nh t thi t ph i bi t t t c các thu c tính c a m i trư ng h p ñ có th quy t ñ nh. Hay nói m t cách khác, cây quy t ñ nh có th cho quy t ñ nh ngay c ñ i v i nh ng trư ng h p mà d li u không ñ y ñ . 2.3.2. Đánh giá v cây quy t ñ nh ñ n bù gi i t a Sau khi phân tích, nh n xét, bây gi chúng tôi th ti n hành ki m tra, ñánh giá m t s trư ng h p gi i t a khác. V i d li u hu n luy n ban ñ u g m có 16 trư ng h p, chúng tôi ch n ra th 8 trư ng h p ng u nhiên ñ ki m tra. ñây ta quan tâm ñ n k t qu quy t ñ nh gi i t a ñ n bù do Ban Qu n lý d án công trình ñư ng B ch Đ ng Đông ñưa ra và k t qu quy t ñ nh d a vào cây quy t ñ nh xây d ng trên. Ta th y trong 87.5% trư ng h p ñ n bù, cây quy t ñ nh ñưa ra quy t ñ nh hoàn toàn phù h p v i quy t ñ nh c a Ban Qu n lý d án công trình ñư ng B ch Đ ng Đông. Trong 12.5% còn l i, cây quy t ñ nh cho k t qu l ch ñôi chút so v i k t qu c a Ban Qu n lý d án công trình ñư ng B ch Đ ng Đông. Tóm l i vi c xây d ng cây quy t ñ nh v i k t qu ñư c ki m th như trên ñ t 87.5% là m t con s tương ñ i t t và ch p nh n ñư c. Nó s là h th ng tr giúp ñ c l c cho Lãnh ñ o, ngư i làm chuyên môn trong công tác ñ n bù gi i t a.