Luận văn:Nghiên cứu ứng dụng khai phá dữ liệu trong phân tích số liệu dân cư

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

Thêm vào BST

Báo xấu

144
lượt xem 36
download

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

Khai thác dữ liệu (data mining) là quá trình khám phá các tri thức mới và các tri thức có ích ở dạng tiềm năng trong nguồn dữ liệu đã có.Khai thác dữ liệu (data mining) là quá trình khám phá các tri thức mới và các tri thức có ích ở dạng tiềm năng trong nguồn dữ liệu đã có.Khai thác dữ liệu (data mining) là quá trình khám phá các tri thức mới và các tri thức có ích ở dạng tiềm năng trong nguồn dữ liệu đã có....

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:Nghiên cứu ứng dụng khai phá dữ liệu trong phân tích số liệu dân cư

B GIÁO D C VÀ ĐÀO T O Đ I H C ĐÀ N NG NGUY N T N PHƯƠNG NGHIÊN C U NG D NG KHAI PHÁ D LI U TRONG PHÂN TÍCH S LI U DÂN CƯ 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 2011
-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.TSKH TR N QU C CHI N Ph n bi n 1: PGS.TS. PHAN HUY KHÁNH Ph n bi n 2: GS.TS. NGUY N THANH THU 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 10 tháng 9 năm 2011. 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 Trong vài th p niên g n ñây, cùng v i s thay ñ i và phát tri n không ng ng c a ngành công ngh thông tin, lu ng thông tin ñư c chuy n t i mau l ñ n chóng m t, ư c tính c kho ng 20 tháng lư ng thông tin trên th gi i l i tăng g p ñôi. Nh ng ngư i ra quy t ñ nh trong các t ch c tài chính, thương m i, khoa h c…không mu n b sót b t c thông tin nào, h thu th p, lưu tr t t c m i thông tin vì cho r ng trong nó n ch a nh ng giá tr nh t ñ nh nào ñó. Hi n nay lư ng d li u mà con ngư i thu th p và lưu tr trong các kho d li u là r t l n, nh ng k thu t truy n th ng không ñ kh năng làm vi c v i d li u thô, không th phân tích b ng tay vì ph i t n r t nhi u th i gian ñ khám phá ra thông tin có ích, ph n l n d li u chưa bao gi ñư c phân tích như nh n ñ nh c a Usama Fayyad:“H sâu kh năng sinh ra d li u và kh năng s d ng d li u”. Gi i pháp duy nh t giúp phân tích t ñ ng kh i lư ng d li u l n ñó là k thu t phát hi n tri th c và khai phá d li u (KDD - Knowledge Discovery and Data Mining). K thu t phát hi n tri th c và khai phá d li u ñã và ñang ñư c nghiên c u ng d ng r ng trên toàn th gi i, v i k thu t KDD, tác gi mu n nghiên c u ng d ng trong phân tích s li u dân cư Vi t Nam ñ phát hi n nh ng tri th c v tăng trư ng dân s . V n ñ tăng trư ng dân s quá nhanh Vi t Nam trong nh ng th p niên g n ñây ñư c s quan tâm r t l n c a các c p lãnh ñ o, ñi n hình là vi c chính ph Vi t Nam ñưa ra chính sách k ho ch hoá gia ñình “M i gia ñình ch có 1 ho c 2 con”. Đã có nhi u bi n pháp x lý nh ng gia ñình vi ph m chính sách k ho ch hoá gia ñình, nhưng qua ñ t th ng kê dân s g n ñây nh t vào năm 2009 còn r t nhi u gia ñình
-2- vi ph m chính sách k ho ch hoá gia ñình (sinh trên 2 con). Nh ng gia ñình vi ph m chính sách có nh ng ñ c ñi m chung nào? V i lư ng l n d li u thu th p ñư c qua m i ñ t th ng kê dân s t i Vi t Nam, vi c ng d ng khai phá d li u trong phân tích s li u dân cư là c n thi t ñ phát hi n nh ng ñ c ñi m chung v các gia ñình vi ph m chính sách k ho ch hoá gia ñình, h tr lãnh ñ o ban dân s k ho ch hoá gia ñình các c p ñưa ra bi n pháp phù h p, tôi quy t ñ nh ch n ñ tài: “Nghiên c u ng d ng khai phá d li u trong phân tích s li u dân cư”. 2. M c ñích nghiên c u M c ñích c a ñ tài là tìm hi u các k thu t khai phá d li u, nghiên c u ng d ng k thu t khai phá d li u trong phân tích s li u dân cư, nh m phát hi n các ñ c ñi m chung c a nh ng gia ñình vi ph m chính sách k ho ch hóa gia ñình, h tr cho các c p lãnh ñ o có nh ng nh n ñ nh ñ ñưa ra bi n pháp phù h p. 3. Đ i tư ng và ph m vi nghiên c u - Tìm hi u lý thuy t v phát hi n tri th c và khai phá d li u - Qu n lí và t ch c lưu tr cơ s d li u t s li u th ng kê dân s t i t nh Qu ng Nam. - Nghiên c u m t s mã ngu n m áp d ng trong khai phá d li u. - Áp d ng k thu t khai phá d li u trên cơ s d li u lưu tr . 4. Phương pháp nghiên c u - Thu th p s li u th ng kê dân s t ngu n d li u th ng kê dân s t i t nh Qu ng Nam - Ch n phương pháp khai phá d li u thích h p. - L a ch n công ngh cài ñ t chương trình.
-3- - Phân tích và ki m ñ nh k t qu ñ t ñư c. 5. Ý nghĩa khoa h c và th c ti n - Cung c p m t cách nhìn t ng quan v phát hi n tri th c và khai phá d li u. - Áp d ng các thu t toán khai phá d li u trên cơ s d li u th ng kê dân s Vi t Nam. (D li u thu th p t ngu n d li u th ng kê dân s t i t nh Qu ng Nam) - Tìm ra các ñ c ñi m chung c a nh ng gia ñình vi ph m chính sách k ho ch hóa gia ñình h tr các nhà lãnh ñ o có nh ng nh n ñ nh c th . - Chương trình ñư c s d ng cho lãnh ñ o ban dân s k ho ch hóa gia ñình các c p. 6. C u trúc c a lu n văn Chương 1: Gi i thi u khái ni m, tính ch t, các bư c trong quá trình khai phá d li u. Phương pháp, d ng cơ s d li u có th khai phá và nh ng thách th c trong quá trình khai phá d li u. Chương 2: Trình bày khái ni m và các bư c trong quá trình khai phá d li u b ng lu t k t h p, trình bày thu t toán Apriori. Trình bày khái ni m và các bư c trong quá trình khai phá d li u b ng cây quy t ñ nh, trình bày thu t toán C4.5 Chương 3: Xây d ng h th ng cây quy t ñ nh trong phân tích s li u dân cư.
-4- CHƯƠNG 1 NGHIÊN C U T NG QUAN V KHAI PHÁ D LI U 1.1. GI I THI U CHUNG V KHÁM PHÁ TRI TH C VÀ KHAI PHÁ D LI U Hi n nay, lư ng d li u mà con ngư i thu th p, lưu tr trong các kho d li u là r t l n, nh ng k thu t truy n th ng không ñ kh năng làm vi c v i d li u thô. V y làm th nào chúng ta có th trích l c ñư c nh ng thông tin có ích t m t kho d li u r t l n. Đ gi i quy t v n ñ ñó, k thu t khám phá tri th c trong cơ s d li u ñã ra ñ i. 1.2. QUÁ TRÌNH KHÁM PHÁ TRI TH C Hình 1.1: Các bư c trong quá trình khám phá tri th c. 1.3. QUÁ TRÌNH KHAI PHÁ D LI U Hình 1.2: Quá trình khai phá d li u
-5- 1.4. CÁC PHƯƠNG PHÁP KHAI PHÁ D LI U 1.4.1. Theo quan ñi m c a h c máy 1.4.2. Theo các l p bài toán c n gi i quy t 1.5. CÁC D NG CƠ S D LI U CÓ TH KHAI PHÁ - Cơ s d li u quan h - Cơ s d li u ña chi u - Cơ s d li u giao tác - Cơ s d li u quan h - hư ng ñ i tư ng - D li u không gian và th i gian - Cơ s d li u ña phương ti n … 1.6. M T S THÁCH TH C TRONG KHAI PHÁ D LI U - Các cơ s d li u l n - S chi u l n (s thu c tính c a d li u quá nhi u) - Thay ñ i d li u và tri th c - D li u b thi u ho c nhi u - Quan h gi a các trư ng ph c t p - Giao ti p gi a ngư i s d ng v i các tri th c ñã có - Tích h p v i các h th ng khác… 1.7. K T LU N Quá trình nghiên c u t ng quan v khai phá d li u giúp chúng ta hi u ñư c các bư c trong qui trình khai phá d li u, phương pháp, d ng d li u có th khai phá và nh ng v n ñ c n gi i quy t trong khai phá d li u.
-6- CHƯƠNG 2 KHAI PHÁ D LI U B NG LU T K T H P VÀ PHÂN L P 2.1 KHAI PHÁ D LI U B NG LU T K T H P 2.1.1. Khái ni m v t p ph bi n và lu t k t h p Trư c khi ñi vào tìm hi u k thu t khai thác d li u b ng lu t k t h p, ta có m t s khái ni m cơ b n như sau: H ng m c (Item): là m t thu c tính nào ñó (i k ) c a ñ i tư ng ñang xét trong cơ s d li u. ( ik : k ∈ { ...m}, v i m là s thu c tính 1 c a ñ i tư ng). T p các h ng m c (Itemset) I = {i1 , i2 ,..., im }: là t p h p các thu c tính c a ñ i tư ng ñang xét trong cơ s d li u. Giao d ch (transaction): là t p các h ng m c trong cùng m t ñơn v tương tác, m i giao d ch ñư c x lý m t cách nh t quán mà không ph thu c vào các giao d ch khác. Cơ s d li u giao d ch D: là t p các giao d ch mà m i giao d ch ñư c ñánh nhãn v i m t ñ nh danh duy nh t (cơ s d li u giao d ch D = { 1 , T 2 ,..., T n } T i ⊆ I ). T , M t giao d ch T ∈ D h h m t t p X ⊆ I n u nó ch a t t c các m c c a X. Đ h tr (supp) c a t p các h ng m c X trong cơ s d li u giao d ch D là t l gi a s các giao d ch ch a X trên t ng s giao d ch trong D. Supp( X ) = T ng s giao d ch ( 2.1) S lư ng giao d ch ch a X T p các h ng m c ph bi n X hay t p ph bi n là t p các h ng m c có ñ h tr tho mãn ñ h tr t i thi u (minsupp) (minsupp là m t giá tr do ngư i dùng xác ñ nh trư c).
-7- N u t p m c X có Supp ( X ) ≥ minsupp thì ta nói X là m t t p các m c ph bi n. T p ph bi n t i ñ i là t p ph bi n và không t n t i t p nào bao nó là t p ph bi n. T p ph bi n ñóng là t p ph bi n và không t n t i t p nào bao nó có cùng ñ h tr như nó. V n ñ khám phá lu t k t h p ñư c phát bi u như sau: Cho trư c 2 thông s ñ h tr θ và ñ tin c y β . Đánh s t t c các m u trong D có ñ h tr và ñ tin c y l n hơn hay b ng θ và β tương ng. Lu t k t h p cho bi t ph m vi mà trong ñó s xu t hi n các m c X nào ñó trong các giao d ch c a cơ s d li u giao d ch D s kéo theo s xu t hi n t p nh ng m c Y cũng trong giao d ch ñó. M i lu t k t h p ñư c ñ c trưng b i hai thông s là ñ h tr và ñ tin c y (supp, conf). Lu t k t h p X → Y t n t i m t ñ tin c y confidence (c/conf). Đ tin c y conf ñư c ñ nh nghĩa là kh năng giao d ch T h tr X thì cũng h tr Y. Ta có công th c tính ñ tin c y conf như sau: Supp ( X ∪ Y ) Conf ( X → Y ) = (2.2) Supp ( X ) Khai phá d li u b ng lu t k t h p phân thành hai bài toán con : Bài toán 1: Tìm t t c các t p m c mà có ñ h tr l n hơn ñ h tr t i thi u do ngư i dùng xác ñ nh. Các t p m c tho mãn ñ h tr t i thi u ñư c g i là các t p m c ph bi n. Bài toán 2 : Dùng các t p m c ph bi n ñ sinh ra các lu t mong mu n. Ý tư ng chung là n u g i XY và X là các t p m c ph bi n, thì chúng ta có th xác ñ nh lu t n u X → Y v i t l ñ tin c y : Conf ( X → Y ) = Supp ( XY ) ( 2.3) Supp ( X )
-8- N u conf(X → Y) ≥ minconf thì lu t k t h p X → Y ñư c gi l i (Lu t này s tho mãn ñ h tr t i thi u vì X là ph bi n). Các tính ch t c a t p m c ph bi n Tính ch t 1: V i X và Y là t p các m c, n u X ⊆Y thì : Supp ( X ) ≥ Supp ( Y ) . Đi u này là rõ ràng vì t t c các giao d ch c a D h tr Y thì cũng h tr X. Tính ch t 2 : M t t p ch a m t t p không ph bi n thì cũng là t p không ph bi n. N u t p m c X không có ñ h tr t i thi u trên D nghĩa là Supp ( X ) < minsupp thì m i t p Y ch a t p X s không ph i là m t t p ph bi n vì Supp (Y ) ≤ Supp ( X ) < minsupp (theo tính ch t 1) Tính ch t 3: Các t p con c a t p ph bi n cũng là t p ph bi n. N u t p m c Y là t p ph bi n trên D, nghĩa là Supp (Y ) ≥ minsupp thì t p con X c a Y là t p ph bi n trên D vì Supp ( X ) ≥ Supp (Y ) > minsupp. Các tính ch t c a lu t k t h p Tính ch t 1: N u X → Z và Y → Z thì X ∪ Y → Z chưa ch c x y ra vì chúng còn ph thu c vào ñ h tr c a m i trư ng h p. Tính ch t 2: N u X ∪ Y → Z thì X → Z và Y → Z chưa ch c x y ra vì chúng còn ph thu c vào ñ tin c y trong m i trư ng h p. Tính ch t 3: N u X → Y và Y → Z thì X → Z chưa ch c x y ra vì chúng còn ph thu c vào ñ tin c y. Tính ch t 4:
-9- N u A → ( L − A) không tho mãn ñ tin c y c c ti u thì lu t B → ( L − B ) cũng không th a mãn, v i các t p tho L, A, B và B ⊆ A ⊂ L. 2.1.2. Các ng d ng khai thác t p ph bi n và lu t k t h p 2.1.3. M t s hư ng ti p c n trong khai thác lu t k t h p 2.1.4. Thu t toán khai phá d li u b ng lu t k t h p 2.1.4.1. Qui trình khai phá d li u b ng lu t k t h p Bư c 1. Tìm t t c các t p ph bi n theo ngư ng minsupp Bư c 2. T o ra các lu t t các t p ph bi n. Đ i v i t p ph bi n S, t o ra các t p con khác r ng c a S. V i m i t p con khác r ng A c a S: Lu t A → ( S − A) là lu t k t h p c n tìm n u Conf ( A → ( S − A)) = Supp( S ) / Supp( A) ≥ minconf. 2.1.4.2. Thu t toán Apriori khai phá d li u b ng lu t k t h p Bài toán ñ t ra: - Tìm t t c các t p m c có ñ h tr minsupp cho trư c. - S d ng các t p m c ph bi n ñ sinh ra các lu t k t h p v i ñ tin c y minconf cho trư c. * Quá trình th c hi n ñ tìm t t c các t p m c ph bi n v i minsupp cho trư c: Bư c 1: Th c hi n nhi u l n duy t l p ñi l p l i, trong ñó t p k- m c ñư c s d ng cho vi c tìm t p (k + 1)-m c. Bư c 2 : Các l n duy t sau s d ng k t qu tìm ñư c bư c trư c ñó ñ sinh ra các t p m c ng viên, ki m tra ñ ph bi n các ng viên trên cơ s d li u và lo i b các ng viên không ph bi n Bư c 3 : Th c hi n l p ñ tìm L3, …., Lk cho ñ n khi không tìm th y t p m c ph bi n nào n a.
- 10 - Gi i thu t Apriori Các ký hi u : Lk : t p t t c k-m c ph bi n (t c t p t t c k-m c có ñ h tr l n hơn ñ h tr t i thi u ). M i ph n t c a t p này có 2 trư ng : t p m c (itemset) và s m u tin h tr (support-count). Ck : T p t t c k-m c ng viên, m i ph n t trong t p này cũng có 2 trư ng là t p m c (itemset) và s m u tin h tr (support-count). |D| : T ng s giao d ch trên D. Count: Bi n ñ ñ m t n su t xu t hi n c a t p m c ñang xét tương ng, giá tr kh i t o b ng 0. N i dung thu t toán Apriori ñư c trình bày như sau: Input: T p các giao d ch D, ñ h tr t i thi u minsupp Output: L- t p m c ph bi n trong D Thu t toán: L1={ t p 1-m c ph bi n}// tìm t p ph bi n 1 h ng m c For (l n lư t duy t các m u tin t ñ u ñ n cu i trong t p Lk) do Begin Ck+1=apriori-gen(Lk);//sinh ra t p ng viên (k+1) h ng m c For (m i m t giao d ch T ∈ D ) do //duy t csdl ñ tính support Begin CT=subset(Ck+1, T); //l y t p con c a T là ng viên trong Ck+1 For (m i m t ng viên c ∈ CT ) do c.count++; //tăng b ñ m t n su t 1 ñơn v end; c.count Lk+1 = {c ∈ C k +1 ≥ minsupp} |D| End; Return ∪ k Lk
- 11 - + Trong giai ño n th nh t ñ m support cho các m c và gi l i các m c mà supp c a nó l n hơn ho c b ng minsupp. + Trong các giai ño n th k ( k ≥ 1 ), m i giai ño n g m có 2 pha: Trư c h t t t c các t p Ti trong t p Lk ñư c s d ng ñ sinh ra các t p ng viên Ck+1, b ng cách th c hi n hàm Apriori_gen. Ti p theo CSDL D s ñư c quét ñ tính ñ h tr cho m i ng viên trong Ck+1. Thu t toán sinh t p ng viên c a hàm Apriori_gen v i ñ i s Lk s cho k t qu là t p h p c a t t c các Lk+1. Thu t toán hàm Apriori_gen Input: t p m c ph bi n Lk có kích thư c k-m c Output: t p ng viên Ck+1 Thu t toán: Function apriori-gen(Lk: t p m c ph bi n có kích thư c k) Begin For (m i Ti ∈ Lk) do For (m i Tj ∈ Lk) do Begin If (Ti và Tj ch khác nhau 1 h ng m c) then C= Ti ∪ Tj ;// h p Ti v i Tj sinh ra ng viên c If subset(c, Lk) then //ki m tra t p con không ph bi n c trong Lk Remove (c)// xoá ng viên c Else C k +1 = C k +1 ∪ {c}; // k t t p c vào Ck+1 End; Return Ck+1 End;
- 12 - 2.2 KHAI PHÁ D LI U B NG PHÂN L P D LI U 2.2.1. Khái ni m s phân l p Phân l p d li u là k thu t d a trên t p hu n luy n ñ phân l p d li u m i. • M c ñích: Gán các m u vào các l p v i ñ chính xác cao nh t ñ d ñoán nh ng nhãn phân l p cho các b d li u m i. • Đ u vào: M t t p các m u d li u hu n luy n, v i m t nhãn phân l p cho m i m u d li u. • Đ u ra: Mô hình cây quy t ñ nh d a trên t p hu n luy n và nh ng nhãn phân l p. 2.2.2. Quá trình phân l p 2.2.3. Phân l p b ng phương pháp quy n p cây quy t ñ nh 2.2.3.1. Khái ni m cây quy t ñ nh 2.2.3.2. T o cây quy t ñ nh T o cây quy t ñ nh bao g m 2 giai ño n: T o cây và t a cây - T o cây: th i ñi m b t ñ u t t c nh ng m u hu n luy n ñ u g c, sau ñó phân chia m u d a trên các thu c tính ñư c ch n. - T a cây: là xác ñ nh và xóa nh ng nhánh mà có ph n t h n lo n ho c nh ng ph n t n m ngoài các l p cho trư c. 2.2.3.3. S d ng cây quy t ñ nh Ki m tra giá tr thu c tính c a t ng nút b t ñ u t nút g c c a cây quy t ñ nh và suy ra các lu t tương ng. * Thu t toán quy n p cây quy t ñ nh: 1. Cây ñư c xây d ng ñ quy t trên xu ng dư i. 2. th i ñi m b t ñ u, t t c nh ng m u hu n luy n g c. 3. Thu c tính ñư c phân lo i theo giá tr . 4. Nh ng m u hu n luy n ñư c phân chia ñ quy d a trên thu c tính mà nó ch n l a.
- 13 - 5. Ki m tra nh ng thu c tính ñư c ch n d a trên n n t ng c a heuristic ho c m t ñ nh lư ng th ng kê. 2.2.3.4. Gi i thu t qui n p cây quy t ñ nh C4.5 Ý tư ng gi i thu t C4.5 như sau: Đ u vào: M t t p h p các m u hu n luy n. M i m u hu n luy n bao g m các thu c tính v i giá tr phân lo i c a nó. Đ u ra: Cây quy t ñ nh có kh năng phân lo i ñúng ñ n các m u hu n luy n và cho c các b chưa g p trong tương lai. Gi i thu t: Function induce_tree (t p_m u_hu n_luy n, t p_thu c_tính) begin if m i m u trong t p_m u_hu n_luy n ñ 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_m u_hu n_luy n 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; //(thu c tính P có ñ ño GainRatio l n nh t ) 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ùng V các m u trong t p_m u_hu n_luy n có giá tr V t i thu c tính P; G i induce_tree(phân_vùngV, t p_thu c_tính) //g n k t qu vào nhánh V end end end
- 14 - 2.2.3.5. M t s v n ñ c n gi i quy t trong vi c phân l p d li u * Vi c ch n thu c tính nào ñ phân chia các m u? Ta có th ch n b t kỳ thu c tính nào làm nút c a cây, ñi u này có kh năng xu t hi n nhi u cây quy t ñ nh khác nhau cùng bi u di n m tt pm u Thu c tính ñư c ch n là thu c tính cho ñ ño t t nh t, có l i nh t cho quá trình phân l p. Đ ño ñ ñánh giá ch t lư ng phân chia là ñ ño ñ ng nh t. • Information Gain • Information Gain Ratio • Gini Index • X2 – s th ng kê b ng ng u nhiên • G – th ng kê (statistic) * Đi u ki n ñ d ng vi c phân chia: 1. T t c nh ng m u hu n luy n thu c v cùng m t l p. 2. Không còn thu c tính còn l i nào ñ phân chia ti p. 3. Không còn m u nào còn l i. * Đ l i thông tin (Information Gain) trong cây quy t ñ nh: Information Gain (Gain): là ñ i lư ng ñư c s d ng ñ l a ch n thu c tính có ñ l i thông tin l n nh t ñ phân l p. Đ ño Information Gain ñư c tính d a vào 2 ñ ño info (I) và entropy (E). Info là ñ ño thông tin kỳ v ng ñ phân l p m t m u trong t p d li u. Gi s cho P, N là hai l p và S là t p d li u ch a p ph n t c a l p P và n ph n t c a l p N. Kh i lư ng thông tin c n ñ quy t ñ nh m t m u tùy ý trong S thu c l p P ho c N ñư c ñ nh nghĩa như sau: p p n n I ( p , n) = − log 2 − log 2 (2.6) p+n p+n p+n p+n
- 15 - Entropy là khái ni m ñ ño tính thu n nh t c a m t t p hu n luy n. Gi s r ng s d ng thu c tính A ñ phân ho ch t p h p S thành nh ng t p h p {S1, S2, ... ,Sv}. N u Si ch a nh ng pi m u c a l p P và ni m u c a N, entropy hay thông tin mong ñ i c n ñ phân l p nh ng ñ i tư ng trong t t c các cây con Si là: i + n v p E ( A ) = ∑ i I ( p , n ) (2.7) p + n i i i=1 Đ l i thông tin nh n ñư c b i vi c phân nhánh trên thu c tính A là: Gain ( A ) = I ( p , n ) − E ( A ) ( 2.8) Ta nh n th y ñ ño Gain có xu hư ng ch n các thu c tính có nhi u giá tr , tuy nhiên thu c tính có nhi u giá tr không ph i lúc nào cũng cho vi c phân l p t t nh t, vì v y ta c n chu n hóa ñ ño Gain, vi c ch n thu c tính không ch d a vào ñ ño Gain mà còn ph thu c vào ñ ño GainRation. SplitInfo là ñ ño thông tin trung bình c a t ng thu c tính, ñ h n ch xu hư ng ch n thu c tính có nhi u giá tr , thông tin trung bình c a thu c tính A ñư c tính: v D j D j SplitInfo(A) = − ∑ log 2 ( ) ( 2.9) j =1 D D Vi c ch n thu c tính ñ phân nhánh d a vào ñ ño GainRation GainRatio(A) = Gain(A) / SplitInfo(A) ( 2.10) Đây là công th c tính ñ ño GainRatio cho thu c tính A trên cơ s d li u D, sau ñó ta ch n thu c tính nào có ñ ño GainRatio l n nh t ñ phân l p theo thu c tính ñó. * V n ñ quá kh p trong phân l p * V n ñ phân l p cây quy t ñ nh trong cơ s d li u l n
- 16 - 2.3 K T LU N Hai phương pháp khai phá d li u b ng lu t k t h p và phân l p mà chúng ta tìm hi u trên ñây, m i phương pháp có các thu t toán ñi n hình, chúng ti p c n khai phá d li u khác nhau, m i phương pháp có ưu và khuy t ñi m riêng tùy thu c vào d ng d li u, mi n d li u, kh i lư ng d li u...Như chúng ta ñã phân tích trên, ưu ñi m khai phá d li u b ng phương pháp phân l p d li u ñ i v i kh i lư ng d li u l n, chính vì th mà chúng ta áp d ng thu t toán C4.5 ñ phân l p d li u dân cư. Thu t toán này là 1 trong s 10 thu t toán “n i ti ng nh t – best known” trong Data Mining, ñư c trao ph n thư ng t i ICDM’06-Hong Kong. CHƯƠNG 3 NG D NG TRONG PHÂN TÍCH S LI U DÂN CƯ 3.1 MÔ T BÀI TOÁN Qua kh o sát th c t , vi c thu th p d li u dân cư trên toàn qu c ñư c th c hi n theo chu kỳ 5 năm và có m t s ñ a phương còn th c hi n vi c kh o sát và c p nh t thư ng xuyên theo t ng tháng, t ng quí, t ng năm nh m th ng kê dân s theo ñ tu i, gi i tính, trình ñ văn hóa, m c ñ tăng trư ng dân s ...theo t ng vùng và trên c nư c. Đây là công vi c c n thi t, giúp các nhà lãnh ñ o có nh n ñ nh nên h tr nh ng y u t nào và h n ch nh ng y u t nào, t o ñi u ki n thu n l i n ñ nh xã h i và phát tri n ñ t nư c. V i mong mu n ng d ng khai phá d li u trong phân tích s li u dân cư ñ tìm ra nh ng ñ i tư ng thư ng hay vi ph m k ho ch hóa gia ñình, h tr cho ban lãnh ñ o DS-KHHGĐ các c p t p trung v n ñ ng, tuyên truy n và giáo d c cho nh ng ñ i tư ng có th vi ph m k ho ch hóa gia ñình góp ph n th c hi n chi n lư c dân s cho giai
- 17 - ño n t i ñ t k t qu t t hơn. Tác gi ñã thu th p m t kh i lư ng l n thông tin qua các cu c t ng ñi u tra dân s , th c hi n phân tích, lưu tr d li u dư i h qu n tr CSDL quan h SQL Server 2005 và s d ng thu t toán C4.5 khai phá d li u b ng mô hình cây quy t ñ nh. 3.2 PHÂN TÍCH VÀ THI T K H TH NG Xác ñ nh các th c th Mô hình th c th k t h p(ERD) Mô hình th c th k t h p Chuy n mô hình ERD thành mô hình quan h Theo phân tích d li u lưu tr và m i quan h c a các b ng cơ s d li u ñ ng th i qua kh o sát th c t , ta th y vi c có vi ph m hay không vi ph m k ho ch hóa gia ñình ph thu c vào nhi u thu c tính
- 18 - khác nhau. Như trình ñ h c v n, khu v c sinh s ng, thu nh p, gi i tính c a con… Xét các thu c tính: 1. Trình ñ h c v n (TH cơ sơ, TH ph thông, THCN) 2. Khu v c sinh s ng (Thành th , Nông thôn, Mi n núi) 3. Thu nh p (Th p, Trung bình, Cao) 4. Gi i tính c a 2 con (1 trai 1 gái, 2 trai, 2 gái) T d li u lưu tr ta rút trích các m u d li u theo b ng sau: B ng3.3 M t s m u d li u trong cơ s d li u dân cư (S) STT H và tên Trình ñ h c v n Thu nh p Nơi Gi i tính Vi ph m 1 Hà Lương TH ph thông Trung bình Thành th 1 trai, 1 gái Không 2 Ph m Văn Chánh TH cơ s Cao Nông thôn 2 gái Có 3 Nguy n Công Tr ng TH ph thông Trung bình Mi n núi 1 trai, 1 gái Không 4 Võ Bé TH CN tr lên Th p Thành th 2 trai Không 5 Lê Thanh Tùng TH ph thông Th p Thành th 2 gái Có 6 Đ Ng c Thái TH cơ s Trung bình Nông thôn 2 trai Có 7 Nguy n Long TH CN tr lên Th p Mi n núi 2 gái Có 8 Trương Ng c L c TH ph thông Cao Thành th 2 gái Không 9 Nguy n Hưu Tuân TH cơ s Th p Mi n núi 2 trai Có 10 Lê Thanh Tùng TH cơ s Cao Mi n núi 1 trai, 1 gái Không 11 Nguy n Minh K TH ph thông Th p Nông thôn 2 trai Không 12 Lê Văn Th ng TH CN tr lên Cao Nông thôn 1 trai, 1 gái Không 13 Huỳnh Thi Chung TH ph thông Th p Thành th 2 trai Không 14 Ph m Th Hoang TH Ph thông Trung bình Mi n núi 2 gái Có 15 Đoàn Văn Ng TH cơ s Th p Nông thôn 1 trai, 1 gái Có 16 Ph m Hùng TH CN tr lên Cao Mi n núi 2 gái Không 17 Võ Trung Thông TH CN tr lên Th p Thành th 1 trai, 1 gái Không 18 Lê Đ c Sơn TH ph thông Cao Nông thôn 2 trai Không 19 A Vi t Ngai TH cơ s Th p Mi n núi 1 trai, 1 gái Có 20 Ph m Văn C m TH cơ s Cao Nông thôn 1 trai, 1 gái Không Đ xây d ng cây quy t ñ nh, t i m i nút c a cây thì thu t toán ñ u ño lư ng thông tin nh n ñư c trên các thu c tính và ch n thu c tính có lư ng thông tin t t nh t làm nút phân tách trên cây nh m ñ ñ t ñư c cây có ít nút nhưng có kh năng d ñoán cao.