Luận văn thạc sĩ: Xây dựng hệ trợ giúp ra quyết định trong công tác tuyển sinh đại học hệ từ xa tại viện đại học mở Hà Nội

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

Thêm vào BST

Báo xấu

132
lượt xem 27
download

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

Xây dựng hệ trợ giúp ra quyết định trong công tác tuyển sinh đại học hệ từ xa tại viện đại học mở Hà Nội nhằm hỗ trợ phòng đào tạo, ban giám hiệu nhà trường và lãnh đạo các đơn vị....đưa ra những chiến lược phát triển hơp lý.

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ĩ: Xây dựng hệ trợ giúp ra quyết định trong công tác tuyển sinh đại học hệ từ xa tại viện đại học mở Hà Nội

-1- B GIÁO D C VÀ ĐÀO T O Đ I H C ĐÀ N NG VŨ CA GIÁP XÂY D NG H TR GIÚP RA QUY T Đ NH TRONG CÔNG TÁC TUY N SINH Đ I H C H T XA T I VI N Đ I H C M HÀ N I 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 - Năm 2012
-1- 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: TS. NGUY N NG C CHÂU Ph n bi n 2: GS.TS. NGUY N THANH THU Lu n văn ñư c b o v trư c 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 04 tháng 03 năm 2012. 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
-1- M Đ U 1. Lý do ch n ñ tài Hi n nay, kinh t th gi i ñang chuy n nhanh sang kinh t tri th c, v i s ñóng góp c a các ngành có ch t lư ng tri th c cao như: công ngh thông tin, công ngh sinh h c, công ngh nano,… Trong xu th h i nh p v i th gi i, Vi t Nam không th ñ ng ngoài dòng ch y c a hư ng phát tri n này, v i th c t là nhu c u nhân l c c a các thành ph n kinh t trong c nư c và nhu c u h c t p c a l c lư ng lao ñ ng r t l n (ph l c 1) [22]. Tuy nhiên, trong hoàn c nh kinh t ñ t nư c còn nhi u khó khăn, m c dù ñã ưu tiên trích m t t l ngân sách qu c gia khá cao cho giáo d c ñào t o, nhưng v n không th ñáp ng ñư c nhu c u v cơ s v t ch t, trang thi t b , giáo trình,… cho các trư ng ñ i h c, cao ñ ng,… Vì v y ch trương xã h i hóa giáo d c ñ huy ñ ng m i ngu n l c cho giáo d c, ñào t o là m t hư ng ñi t t y u c a Nhà nư c ta trong th i ñi m hi n nay. Trong b i c nh ñó, Vi n Đ i h c M Hà N i (VĐHMHN) ñã ñư c thành l p ngày 03/11/1993 theo quy t ñ nh 535/TTg c a Th tư ng Chính ph . V i nhi m v chính tr là liên k t v i các trư ng Đ i h c, Cao ñ ng và các Trung tâm Giáo d c thư ng xuyên t i các t nh, thành ph trên c nư c ñ ñào t o và phát tri n ñ i h c h T xa, nh m ñào t o ngu n nhân l c có ch t lư ng ph c v cho s nghi p phát tri n kinh t xã h i, ñ c bi t là s nghi p Công nghi p hóa - Hi n ñ i hóa c a ñ t nư c trong giai ño n hi n nay và lâu dài. Qua quá trình phát tri n, ñ n nay nhà trư ng ñã tuy n sinh cho h t xa ñư c 85.759 h c viên (ph c l c 3a), s h c viên ñã t t nghi p 23.741 (ph c l c 3b), s h c viên ñang theo h c 41.928 (ph l c 2). Đ ñ t ñư c nh ng thành t u này là nh s quan tâm, ch ñ o sát sao c a B Giáo d c và Đào t o, s ph n ñ u không ng ng c a t p th lãnh
-2- ñ o, giáo viên, cán b công nhân viên Vi n Đ i h c M Hà N i trong su t nh ng năm tháng qua. Nh ng thành t u mà nhà trư ng ñ t ñư c là r t ñáng khích l . Tuy nhiên, v n còn ñó nh ng t n t i c n kh c ph c trong công tác qu n lý, ñào t o và nh t là công tác tuy n sinh. Qua s li u th ng kê cho th y, s lư ng tuy n sinh c a VĐHMHN t năm 2007 ñ n năm 2010 ngày càng gi m d n (ph l c 3a) [8]. Đ gi i quy t v n ñ khó khăn trong công tác tuy n sinh, ngoài vi c ñ m b o ch t lư ng ñào t o, m r ng mã ngành thì VĐHMHN c n ph i tăng cư ng ñ u tư cho vi c qu ng bá hình nh nhà trư ng, nh m tăng cư ng tính c nh tranh ñ i v i các trư ng có tuy n sinh h t xa (ph l c 2). Ngoài ra, nhà trư ng c n chú tr ng phát tri n liên k t ñào t o và m r ng ñ a bàn tuy n sinh. Tính ñ n th i ñi m này, VĐHMHN ñã thi t l p 68 tr m ñào t o t xa ñóng trên ñ a bàn c a trên 30 t nh/thành ph , t o thành m ng lư i tr i dài t Tây B c ñ n Tây Nguyên và Nam B nh m ph c v nhu c u h c t p ñông ñ o c a ngư i dân t thành th ñ n nông thôn, t mi n núi ñ n h i ñ o (ph l c 4) [24]. Tuy nhiên, k t qu c a vi c ñ u tư này v n chưa ñ t ñư c như mong mu n, s lư ng các ñ t tuy n sinh th t b i (không ñ s lư ng h c viên ñ m l p) t i các ñ a bàn liên k t ñào t o v n còn m c cao (ph l c 5), d n ñ n nh ng h u qu không như mong mu n là uy tín, thương hi u c a nhà trư ng b nh hư ng, kinh phí ñ u tư cho công tác tuy n sinh t n kém (ph l c 6), nh hư ng không nh ñ n cơ h i h c t p c a ngư i dân. Qua nghiên c u ñánh giá, nhà trư ng ñã rút ra m t s nguyên nhân chính d n ñ n vi c tuy n sinh th t b i trong th i gian qua: Ngành tuy n sinh chưa phù h p v i nhu c u c a ngư i h c; vùng mi n, ñ c thù phát tri n kinh t -xã h i t i ñ a phương.
-3- Chưa có bi n pháp nghiên c u, ñánh giá m c ñ c nh tranh c a các trư ng Kh năng th ng kê, ñi u tra và ñánh giá s li u liên quan ñ n quá trình ñào t o nói chung và tuy n sinh nói riêng c a nhà trư ng, c a các ñ a phương liên k t trong nh ng năm qua còn h n ch . Do ñó, chưa có cái nhìn bao quát, xuyên su t d n ñ n vi c quy t ñ nh ñ a ñi m, ngành tuy n sinh chưa phù h p,… ñây là nguyên nhân chính c a v n ñ th t b i trong công tác tuy n sinh. Chưa ng d ng CNTT ñ tr giúp cho công tác ra quy t ñ nh trong khâu xác ñ nh ngành ngh khi tuy n sinh. Đ góp ph n tăng cư ng ch t lư ng quy t ñ nh trong vi c ch n ngành ngh tuy n sinh, thì vi c ng d ng công ngh thông tin vào công tác này là t t y u vì: Môi trư ng ng d ng CNTT ñang phát tri n m nh t i VĐHMHN. Các d li u v ngư i h c (nhu c u, tài chính, năng l c,…), ñ nh hư ng phát tri n kinh t - xã h i, ngành ngh ưu tiên phát tri n t i ñ a bàn tuy n sinh,... r t nhi u và ña d ng. Vì v y, n u không ng d ng CNTT, cán b chuyên trách tuy n sinh c a nhà trư ng và c a ñ a phương khó lòng n m v ng, t ng h p ñ có nh ng thông tin h u ích ph c v ra quy t ñ nh ñúng ñ n, k p th i. Chính vì nh ng lý do trên, tôi quy t ñ nh ch n ñ tài “Xây d ng h tr giúp ra quy t ñ nh trong công tác tuy n sinh Đ i h c h T xa t i Vi n Đ i h c M Hà N i” nh m h tr cho phòng ñào t o, ban giám hi u nhà trư ng và lãnh ñ o các ñơn v liên k t có m t cách ñánh giá bao quát v hi u qu tuy n sinh, ñào t o trong nh ng năm qua. T ñó có bi n pháp kh c ph c các m t còn h n ch nh m ñưa ra nh ng chi n lư c phát tri n h p lý trong th i gian ñ n. Ngoài ra, h th ng còn giúp ñưa ra các quy t ñ nh nhanh chóng, k p th i khi ch n ngành ngh
-4- tuy n sinh, góp ph n gi m thi u s lư ng các ñ t tuy n sinh th t b i c a nhà trư ng ñã t ng x y ra trong th i gian qua. 2. M c tiêu và nhi m v nghiên c u M c tiêu mà ñ tài hư ng ñ n là xây d ng và áp d ng có hi u qu cho vi c tr giúp ra quy t ñ nh trong công tác tuy n sinh ñ i h c h T xa t i Vi n Đ i h c M Hà N i. Đ th c hi n m c ñích ý tư ng ñ ra c n nghiên c u và ti n hành tri n khai các n i dung như sau: Tìm hi u, phân tích th c tr ng công tác tuy n sinh c a nhà trư ng và các ñơn v liên k t ñ ñ ra gi i pháp h p lý trong vi c xây d ng và tri n khai h th ng. Nghiên c u các thu t toán liên quan ñ n cây quy t ñ nh. Phân tích, ñánh giá và tri n khai áp d ng thu t toán C4.5 ñ ng d ng trong công tác tuy n sinh. Áp d ng cơ s lý thuy t n n t ng ñ xây d ng và tri n khai ng d ng. 3. Đ i tư ng và ph m vi nghiên c u T yêu c u c a ñ tài, ta xác ñ nh ñư c ñ i tư ng và ph m vi nghiên c u c a ñ tài c th như sau: Đ i tư ng nghiên c u: H c viên ñang theo h c ho c ñã t t nghi p ra trư ng. Nhu c u xã h i ñ i v i các ngành mà nhà trư ng tuy n sinh Quy trình tuy n sinh ñ i h c h T xa. S phát tri n v quy mô ñào t o h t xa c a các trư ng khác. Các v n ñ v lý thuy t tr giúp quy t ñ nh ñ ñ ra gi i pháp ng d ng vào h th ng tr giúp quy t ñ nh ph c v công tác tuy n sinh. Ph m vi nghiên c u: S li u th ng kê v công tác tuy n sinh, ñào t o c a nhà trư ng trong 10 năm g n ñây. S li u th ng kê v tình hình h c viên sau khi t t nghi p.
-5- Nghiên c u v ñ c thù vùng mi n, các thành ph n kinh t -xã h i ñ i v i các ñ a phương tuy n sinh. Nghiên c u lý thuy t tr giúp quy t ñ nh, xây d ng ng d ng d a trên ch ñ là tên ñ tài ñã ñư c ñ t. 4. Phương pháp nghiên c u Đ ng d ng m c tiêu và nhi m v c a lu n văn, tôi k t h p hai phương pháp nghiên c u, ñó là: 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 tuy n sinh, ñào t o ñ i h c h T xa c a nhà trư ng. 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 ñ tr giúp vi c l p trình, xây d ng ng d ng. Th ng kê, phân tích các s li u th c t trong công tác tuy n sinh. Ki m tra, th nghi m và ñưa ra nh n xét, ñánh giá k t qu ñ t ñư c. 5. K t qu ñ t ñư c Đ xu t ñư c gi i pháp k thu t, xây d ng ñư c chương trình th c hi n vi c tr giúp quy t ñ nh trong công tác tuy n sinh. H th ng ñơn gi n, d s d ng và có tính linh ho t. Đưa ra quy t ñ nh m t cách nhanh chóng, t i ưu và có giá tr cho ngư i s d ng. 6. Ý nghĩa khoa h c và th c ti n V m t khoa h c Đ tài s ñưa ra m t phương th c ng d ng cây quy t ñ nh trong công tuy n sinh, t o ti n ñ cho nh ng nghiên c u ng d ng trong công tác tuy n sinh sau này.
-6- V m t th c ti n Đ tài s ng d ng các công c , ngôn ng l p trình ñ xây d ng h th ng tr giúp công tác tuy n sinh. 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 phòng Đào t o, ban giám hi u nhà trư ng, cho lãnh ñ o các ñơn v liên k t. Tri n khai h th ng t i Vi n Đ i h c M Hà N i và các ñơn v liên k t nh m ph c v t t yêu c u trong công tác tuy n sinh. 7. B c c lu n văn Sau ph n m ñ u, gi i thi u…, n i dung chính c a lu n văn ñư c chia thành 3 chương như sau: Chương 1, trình bày cơ s lý thuy t làm n n t ng ñ xây d ng ng d ng, bao g m: H tr giúp quy t ñ nh, các mô hình toán h c thư ng dùng trong các bài toán ra quy t ñ nh. Cây quy t ñ nh và gi i thu t C4.5 xây d ng cây quy t ñ nh. Chương 2, tìm hi u, gi i thi u và phân tích th c tr ng công tác tuy n sinh t i nhà trư ng, nêu nh ng v n ñ h n ch và ñ xu t gi i pháp kh c ph c, ñó là gi i pháp ng d ng cây quy t ñ nh ñ gi i quy t bài toán ñ t ra. Chương 3, trình bày chi ti t v mô hình ki n trúc t ng th c a h th ng và phương pháp xây d ng ng d ng. Ti n hành k ch b n th nghi m trên s li u th c t , sau ñó ñánh giá k t qu ñ t ñư c và kh năng tri n khai ng d ng trên toàn h th ng. Cu i cùng là ph n ñánh giá, k t lu n và hư ng phát tri n c a ñ tài.
-7- CHƯƠNG 1 CƠ S LÝ THUY T 1.1. H TR GIÚP QUY T Đ NH 1.1.1. M ñ u 1.1.2. Khái ni m h tr giúp quy t ñ nh 1.1.3. Quá trình ra quy t ñ nh 1.1.4. Các thành ph n c a h tr giúp quy t ñ nh 1.2. RA QUY T Đ NH TRONG QU N LÝ 1.2.1. M ñ u 1.2.2. Các phương pháp ra quy t ñ nh trong qu n lý 1.2.2.1. Ra quy t ñ nh theo c u trúc c a v n ñ 1.2.2.2. Ra quy t ñ nh theo tính ch t c a v n ñ 1.2.2.3. Ra quy t ñ nh trong ñi u ki n r i ro 1.2.2.4. Ra quy t ñ nh ña y u t 1.2.3. Các bư c c a quá trình ra quy t ñ nh 1.2.4. Bài toán ra quy t ñ nh 1.3. CÂY QUY T Đ NH 1.3.1. Gi i thi u chung 1.3.2. Phân l p d li u d a trên các ki u cây quy t ñ nh 1.3.3. Gi i thu t cơ b n xây d ng cây quy t ñ nh 1.3.4. Ch n thu t toán C4.5 xây d ng cây quy t ñ nh 1.4. THU T TOÁN C4.5 1.4.1. Gi i thi u 1.4.2. Gi i thu t C4.5 xây d ng cây quy t ñ nh t trên xu ng
-8- 1.4.2.1. Thu t toán C4.5 Function xay_dung_cay(T) { 1. ; 2. If Then Else ; 3. For Do ; 4. ; 5. If Then ; 6. For
-9- 1.4.2.3. Ch n thu c tính phân lo i t t nh t 1.4.2.4. Entropy ño tính thu n nh t c a t p ví d 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 bit 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 [7]. 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. Entropy có giá tr n m trong kho ng [0..1]. Entropy(S) = 0: t p 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 hu n luy n, trong ñó thu c tính phân lo i có hai giá tr , gi s là âm (-) và dương (+). Trong ñó: 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+ log2 p+ - p- log2 p- 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à: c Entropy(S) ≡ ∑ − p i log 2 p i i=1
-10- 1.4.2.5. Lư ng thông tin thu ñư c ño m c ñ gi m Entropy mong ñ i 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 (hay ñ l i thông tin), 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: SV Gain(S, A) = Entropy(S) − ∑ Entropy(S V ) V∈Value(A) S Giá tr Value (A) là t p các giá tr có th cho thu c tính A, và Sv là t p con c a S mà A nh n giá tr v. 1.4.2.6. T su t l i ích Gain Ratio Khái ni m ñ l i thông tin Gain có xu hư ng ưu tiên các thu c tính có s lư ng l n các giá tr . N u thu c tính D có giá tr riêng bi t cho m i b ng ghi (thu c tính Ngày b ng d li u trên), thì Entropy(S, D) = 0, như v y Gain(S, D) s ñ t giá tr c c ñ i. Rõ ràng, m t phân vùng như v y thì vi c phân lo i là vô ích. Thu t toán C4.5, m t c i ti n c a ID3, m r ng cách tính Information Gain thành Gain Ratio ñ c g ng kh c ph c s thiên l ch. Gain Ratio ñư c xác ñ nh b i công th c sau: Gain(S, A) GainRatio( S, A) = SplitInfor mation(S, A) V i SplitInformation(S, A) chính là thông tin do phân tách c a A trên cơ s giá tr c a thu c tính phân lo i S. Công th c tính như sau:
-11- Ai Ai SplitInfor mation(S, A) = − ∑ log 2 i∉ V alue ( S ) |A| |A | Trong ñó: Value(S) là t p các giá tr c a thu c tính S Ai là t p con c a t p A ng v i thu c tính S = giá tr là vi 1.4.3. Phương pháp ñánh giá m c ñ hi u qu 1.4.4. Chuy n cây v d ng lu t 1.4.5. ng d ng t p lu t CHƯƠNG 2 PHÂN TÍCH TH C TR NG CÔNG TÁC TUY N SINH T I VI N Đ I H C M HÀ N I 2.1. GI I THI U V VI N Đ I H C M HÀ N I 2.2. CÔNG TÁC TUY N SINH Đ I H C H T XA 2.2.1. Quy trình tuy n sinh 2.2.2. Mô hình tuy n sinh 2.2.3. M c tiêu tuy n sinh 2.2.4. Th c tr ng tuy n sinh 2.2.5. V n ñ tr giúp quy t ñ nh 2.2.6. Gi i pháp xây d ng h th ng tr giúp quy t ñ nh. 2.3. NG D NG CÂY QUY T Đ NH 2.3.1. Lư ng hóa d li u ñ ñưa vào thu t toán C4.5 2.3.2. Phân tích d li u Qua phân tích ph n th c tr ng công tác tuy n sinh, ta th y có nhi u y u t nh hư ng ñ n công tác tuy n sinh. Tuy nhiên, chúng ta chú tr ng phân tích nh ng y u t chính sau: Chuyên ngành ñào t o (CNDT): Các ngành nhà trư ng có tuy n sinh
-12- Nhu c u xã h i (NCXH): S li u ñi u tra nhu c u c a xã h i ñ i v i các ngành d ki n tuy n sinh. T l b h c (TLBH): S li u th ng kê t l b h c c a h c viên qua qua các năm ñào t o. C nh tranh (CT): Có hay không có s c nh tranh trong công tác tuy n sinh c a các trư ng khác. Các y u t trên chính là t p thu c tính, d a vào t p thu c tính này ñ d ñoán giá tr cho thu c tính ñích Quy t ñ nh. Đ thu n ti n trong vi c hu n luy n cây quy t ñ nh, ñ i v i các thu c tính có các giá tr so sánh, ta ti n hành r i r c hóa và ký hi u hóa các giá tr c a chúng. Nhu c u xã h i: N u nhu c u xã h i
-13- TT NCDT NCXH TLBH (%) CT QD 7 QTKD 80..100 32- THAP YES 8 KT 120+ 32..42 CAO YES 9 LKT 120+ 32..42 CAO YES 10 QTKD 80..100 32..42 CAO NO 11 KT 120+ 42+ CAO Y/N 12 LKT 120+ 42+ CAO Y/N 13 QTKD 80..100 32..42 THAP Y/N 14 KT 101..120 32- CAO Y/N 15 LKT 101..120 32- CAO Y/N 16 QTKD 80..100 42+ CAO NO 17 KT 101..120 32..42 CAO Y/N 18 LKT 101..120 32..42 CAO Y/N 19 QTKD 80..100 42+ THAP NO 20 KT 101..120 42+ CAO NO 21 LKT 101..120 42+ CAO NO 22 QTKD 101..120 32- CAO Y/N 23 KT 101..120 32- THAP YES 24 LKT 101..120 32- THAP YES 25 QTKD 101..120 32..42 CAO Y/N 26 KT 101..120 32..42 THAP YES 27 LKT 101..120 32..42 THAP YES 28 QTKD 101..120 42+ CAO NO 29 KT 101..120 42+ THAP Y/N 30 LKT 101..120 42+ THAP Y/N 31 QTKD 101..120 32- THAP YES 32 KT 80..100 32- CAO YES 33 LKT 80..100 32- CAO YES 34 QTKD 101..120 32..42 THAP YES 35 KT 80..100 32..42 CAO NO 36 LKT 80..100 32..42 CAO NO 37 QTKD 101..120 42+ THAP Y/N
-14- TT NCDT NCXH TLBH (%) CT QD 38 KT 80..100 32..42 THAP Y/N 39 LKT 80..100 32..42 THAP Y/N 40 QTKD 120+ 32- CAO YES 41 KT 80..100 42+ THAP NO 42 LKT 80..100 42+ THAP NO 43 QTKD 120+ 32..42 CAO YES 44 KT 80- 32- THAP NO 45 LKT 80- 32- THAP NO 46 QTKD 120+ 42+ CAO Y/N 47 KT 80- 32..42 CAO NO 48 LKT 80- 32..42 CAO NO 49 QTKD 120+ 42+ THAP YES 50 LKT 80..100 42+ THAP NO T ví d trên, áp d ng thu t thu t toán C4.5 cho t p d li u hu n luy n ñ xây d ng cây quy t ñ nh cho bài toán tuy n sinh. 2.3.3. Tri n khai gi i thu t C4.5 xây d ng cây quy t ñ nh Đ xây d ng cây quy t ñ nh ta ph i xác ñ nh nút g c ñ phân tách cây. Thu c tính có ñ l i thông tin l n nh t s ñư c ch n làm nút g c. G i S là t p thu c tính ñích. Có t t c 50 ví d , trong ñó YES xu t hi n trong t p thu c tính ñích 19 l n, NO 16 l n và Y/N 15 l n. Áp d ng công th c tính Entropy, ta có: Entropy(S) = -(19/50)log2(19/50)-(16/50)log2(16/50)- (15/50)log2(15/50) = 1.58 Đ i v i thu c tính “Chuyên ngành ñào t o”, ta tính Entropy c a các t p con S ñư c chia b i các giá tr c a thu c tính “Chuyên ngành ñào t o” như b ng sau:
-15- B ng 2.4. B ng Entropy(S) phân theo CNDT S QD CNDT Entropy lư ng YES NO Y/N QTKD 17 7 5 5 1.57 KT 16 6 5 5 1.58 LKT 17 6 6 5 1.58 Entropy c a S ñ i v i thu c tính “Chuyên ngành ñào t o” là: Entropy(S,CNDT) = (17/50) x 1.57 + (16/50) x 1.58 + (17/50) x 1.58 = 1.58 Đ l i thông tin tương ng là: Gain(S,CNDT) = Entropy(S) - Entropy(S,CNDT) = 1.58 - 1.58 = 0.00 T su t l i ích Gain Ratio: SplitInfor(S,CNDT) = - (17/50) x log2(17/50) - (16/50) x log2(16/50) - (17/50) x log2(17/50) = 1.58 GainRatio(S,CNDT) = Gain(S,CNDT)/SplitInfor(S,CNDT) = = 0.00/1.58 = 0.00 M t cách tương t , ta tính ñ l i thông tin Gain và t su t l i ích Gain Ratio c a các thu c tính còn l i B ng 2.5. Đ l i thông tin c a thu c tính “Nhu c u xã h i” S QD NHCH Entropy lư ng YES NO Y/N 80- 5 0 5 0 0.00 80..100 15 4 8 3 1.46 101..120 18 6 3 9 1.46 120+ 12 9 0 3 0.00
-16- B ng 2.6. Đ l i thông tin c a thu c tính “T l b h c” S QD TLBH Entropy lư ng YES NO Y/N 32- 16 10 3 3 1.33 32..42 17 6 5 6 1.58 42+ 17 3 8 6 1.48 B ng 2.7. Đ l i thông tin c a thu c tính “C nh tranh” S QD TLBH Entropy lư ng YES NO Y/N CAO 27 9 9 9 1.58 THAP 23 10 7 6 1.55 Ti p theo, ta so sánh k t qu tính GainRatio c a các thu c tính B ng 2.8. B ng so sánh k t qu tính GainRatio c a các thu c tính Thu c tính Gain SplitInfor GainRatio CNDT 0.00 1.58 0.00 NCXH 0.62 1.88 0.33 TLBH 0.11 1.58 0.07 CT 0.01 1.00 0.01 Ta nh n th y GainRatio(S,NCXH) = 0.33 ñ t giá tr l n nh t, do ñó thu c tính nhu c u xã h i có kh năng phân lo i t t nh t. Chính vì v y ta s ch n thu c tính này làm nút g c phân tách cây. Ta có cây quy t ñ nh c p 1 như hình v sau: NCXH 80- 80..100 101..120 120+ NO ? ? ? Hình 2.3. Cây quy t ñ nh c p 1
-17- ng v i giá tr NCXH = 80- có Entropy = 0. Do ñó, t i nhánh này s là nút có phân l p là NO. Đ i v i các nhánh còn l i (NCXH = 80..100; NCXH = 101..120; NCXH = 120+), ta ti p t c v n d ng thu t toán ñ tìm thu c tính làm nút c a cây. Xét nhánh NCXH =80..100 B ng 2.9. B ng d li u trư ng h p NCXH = 80..100 TT NCDT NCXH TLBH CT QD 1 QTKD 80..100 32- CAO YES 2 QTKD 80..100 32- THAP YES 3 QTKD 80..100 32..42 CAO NO 4 QTKD 80..100 32..42 THAP Y/N 5 QTKD 80..100 42+ CAO NO 6 QTKD 80..100 42+ THAP NO 7 KT 80..100 32- CAO YES 8 LKT 80..100 32- CAO YES 9 KT 80..100 32..42 CAO NO 10 LKT 80..100 32..42 CAO NO 11 KT 80..100 32..42 THAP Y/N 12 LKT 80..100 32..42 THAP Y/N 13 KT 80..100 42+ THAP NO 14 LKT 80..100 42+ THAP NO 15 LKT 80..100 42+ THAP NO G i S1 là t p thu c tính ñích. Áp d ng công th c tính Entropy ta có: Entropy(S1) = -(3/15) x log2(3/15)-(9/15) x log2(9/15)-(3/15) x log2(3/15) = 1.37 Ti p theo ta l n lư t tính Gain c a các thu c tính như ñã tính ph n trên, k t qu như sau:
-18- B ng 2.10. Đ l i thông tin c a thu c tính “CNDT” QD Gain S Entropy Entropy CNDT (S1,CN lư ng YES NO Y/N (i) (CNDT) DT) QTKD 6 2 3 1 1.46 KT 4 1 2 1 1.50 1.44 0.01 LKT 5 1 3 1 1.37 B ng 2.11. Đ l i thông tin c a thu c tính “TLBH” QD Gain S Entropy Entropy TLBH (S1,TL lư ng YES NO Y/N (i) (TLBH) BH) 32- 4 4 0 0 0.00 32..42 6 0 3 3 0.00 0.00 0.93 42+ 5 0 5 0 0.00 B ng 2.12. Đ l i thông tin c a thu c tính “CT” S QD Entropy Entropy Gain CT lư ng YES NO Y/N (i) (CT) (S1,CT) CAO 7 3 4 0 0.00 0.75 0.71 THAP 8 1 4 3 1.41 Ti p theo ta tính SplitInfor và GainRatio c a các thu c tính, k t qu như sau: B ng 2.13. K t qu tính SplitInfor và GainRatio Thu c tính Gain SplitInfor GainRatio CNDT 0.02 1.57 0.01 TLBH 1.46 1.57 0.93 CT 0.71 1.00 0.71 Qua b ng so sánh k t qu trên, ta th y GainRatio(S1,TLBH) = 0.93 ñ t giá tr l n nh t, do ñó t i nhánh này ta ch n thu c tính TLBH ñ làm nút phân tách cây.