Xem mẫu
- 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.
nguon tai.lieu . vn
