Luận văn:Nghiên cứu giải thuật di truyền ứng dụng vào giải một số bài toán thống kê

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

Thêm vào BST

Báo xấu

209
lượt xem 63
download

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

Giải thuật di truyền là một kỹ thuật của khoa học máy tính nhằm tìm kiếm giải pháp thích hợp cho các bài toán tối ưu tổ hợp (combinatorial optimization). Giải thuật di truyền là một phân ngành của giải thuật tiến hóa vận dụng các nguyên lý của tiến hóa như di truyền, đột biến, chọn lọc tự nhiên, và trao đổi chéo.

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 giải thuật di truyền ứng dụng vào giải một số bài toán thống kê

1 B GIÁO D C VÀ ĐÀO T O Đ I H C ĐÀ N NG H MINH ĐÍCH NGHIÊN C U GI I THU T DI TRUY N NG D NG VÀO GI I M T S BÀI TOÁN TH NG KÊ 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
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. Lê Văn Sơn Ph n bi n 1: TS. Huỳnh H u Hưng Ph n bi n 2: PGS.TS. Đoàn Văn Ban 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 15 tháng 10 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.
3 M Đ U 1. Lý do ch n ñ tài Trong nh ng năm g n ñây, k thu t l p trình ti n hóa là m t trong nh ng k thu t l p trình r t phát tri n trong lĩnh v c trí tu nhân t o. M t công th c tương t v i công th c n i ti ng c a N.Wirth ñưa ra trong l p trình c u trúc ñư c áp d ng cho k thu t l p trình ti n hóa: C u trúc d li u + Gi i thu t di truy n = chương trình ti n hóa Thu t ng chương trình ti n hóa là m t trong nh ng khái ni m ñư c dùng ñ ch các chương trình máy tính có s d ng thu t toán tìm ki m và t i ưu hóa d a trên “nguyên lý ti n hóa t nhiên”. Ta g i chung các thu t toán như v y là thu t toán ti n hóa. Có m t s thu t toán ti n hóa ñư c công b : - Quy ho ch ti n hóa – EP, do D.B.Pogel ñ xu t. - Chi n lư c ti n hóa, do T.Baeck, F.H.Hofmeister và H.P.Schwefel ñ xu t. - Thu t gi i di truy n, do D.E.Golberg ñ xu t, ñư c L.Davis và Z.Michalevicz phát tri n. Trong ph m vi lu n văn ch nghiên c u l p trình ti n hóa thông qua gi i thu t di truy n và ng d ng vào gi i quy t hai l p bài toán phân tích d li u th ng kê. 2 . Đ i tương và ph m vi nghiên c u 2.1. Đ i tư ng nghiên c u Đ i tư ng nghiên c u c a ñ tài g m: - Gi i thu t di truy n - Phân l p d li u b ng các hàm phân bi t tuy n tính - Phân tích h i qui 2.2. Ph m v nghiên c u ng d ng gi i thu t di truy n ñ thi t k gi i thu t tìm giá tr Min (Max) c a hàm nhi u bi n làm công c ñ gi i các bài toán th ng kê ñ ra trong lu n văn. C th là hai bài toán: - Bài toán phân tích d li u h i qui tuy n tính. - Bài toán phân l p d li u b ng t p các hàm phân bi t tuy n tính. 3. M c ñích ñ tài
4 M c ñích c a ñ tài là mu n tìm m t cách ti p c n m i b ng thu t gi i di truy n ñ gi i m t s l p bài toán thu c lĩnh v c th ng kê, ñ ng th i cũng mu n ch ng minh tính năng vư t tr i c a gi i thu t di truy n trong vi c tìm l i gi i cho nhi u d ng bài toán khác nhau. 4. M c tiêu, ý nghĩa ñ tài Nghiên c u và ng d ng gi i thu t di truy n vào hai l p bài toán thu c lĩnh v c th ng kê là bài toán h i quy tuy n tính và bài toán phân l p d li u d a trên các hàm phân lo i tuy n tính. K t qu c a bài toán mang l i v a có tính năng c a m t h th ng máy h c, giúp d báo, tính toán, phân l p các d li u không ñư c h c v a có ý nghĩa ñ xu t và ñ t ñư c k t qu kh quan v m t phương pháp phân l p d li u cũng như vi c thi t l p các mô hình toán h c và phân tích tương quan cho các s li u th c nghi m dùng trong nghiên c u khoa h c. Đ i v i thu t gi i di truy n, ý tư ng xuyên su t nh t c a nó là mô ph ng quá trình ti n hóa t nhiên ñ áp d ng tìm ki m l i gi i cho m t bài toán trên máy tính. Vi c áp d ng gi i thu t di truy n ñ gi i quy t hai l p bài toán nói trên là m t phương pháp ti p c n m i, tinh t ñ gi i quy t m t s l p bài toán trong lĩnh v c th ng kê là nh ng bài toán t n r t nhi u công s c cho thao tác tính toán ñ tìm ra l i gi i cho bài toán. 5. C u trúc lu n văn N i dung chính c a lu n văn ñư c trình bày trong 4 chương : Chương 1. Cơ s lý thuy t v gi i thu t di truy n Chương 2. ng d ng gi i thu t di truy n tìm c c tr c a hàm nhi u bi n Chương 3. Phân l p d li u b ng các hàm phân bi t tuy n tính Chương 4. Bài toán h i quy CHƯƠNG 1. CƠ S LÝ THUY T V THU T GI I DI TRUY N 1.1. KHÁI NI M Gi i thu t di truy n(GA) là gi i thu t tìm ki m, ch n l a các gi i pháp t i ưu ñ gi i quy t các bài toán th c t khác nhau, d a trên cơ ch ch n l c c a di truy n h c: t t p l i gi i ban ñ u, thông qua nhi u bư c ti n hoá, hình thành
5 t p l i gi i m i phù h p hơn, và cu i cùng tìm ra l i gi i t i ưu nh t. Gi i thu t di truy n d a trên quan ñi m cho r ng quá trình ti n hoá c a t nhiên là quá trình hoàn h o nh t, h p lý nh t và t nó ñã mang tính t i ưu. Ý tư ng chính c a gi i thu t di truy n là thay vì ch phát sinh m t l i gi i ban ñ u chúng ta s phát sinh m t lúc nhi u l i gi i cùng lúc. Sau ñó, trong s l i gi i ñư c t o ra, ch n ra nh ng l i t t nh t ñ làm cơ s phát sinh ra nhóm các l i gi i sau v i nguyên t c càng v sau càng t t hơn. Quá trình c th ti p di n cho ñ n khi tìm ñư c l i gi i t i ưu ho c x p x t i ưu. 1.2. GI I THU T DI TRUY N 1.2.1 Đ nh nghĩa : GA ñư c ñ nh nghĩa là m t b 7: GA=( I, Ψ , Ω,s, t, µ, λ ) : • I=Bt: Không gian tìm ki m l i gi i c a bài toán. • Ψ :I → R: Ký hi u c a hàm thích nghi (Eval function). • Ω : Ký hi u cho t p các phép toán di truy n. • S: I µ+λ → Iµ ký hi u cho thao tác ch n; gi l i µ cá th . t: I → {True, false} là tiêu chu n d ng. ϖ • • µ , λ : l n lư t là s cá th trong th h cha m và th h con cháu. 1.2.2. Nh ng quá trình ti n hóa c a gi i thu t : 1.2.2.1. Quá trình lai ghép (Cross Over): Phép lai: Là quá trình hình thành nhi m s c th m i trên cơ s các nhi m s c th cha m b ng cách ghép m t hay nhi u ño n gen c a hai (hay nhi u) nhi m s c th cha-me v i nhau, phép lai ñư c th c hi n v i xác su t pc 1.2.2.2. Quá trình tái sinh (Preproduction) và l a ch n (Selection): Tái sinh: Là quá trình trong ñó các cá th ñư c sao chép d a trên cơ s ñ thích nghi c a nó. Phép l a ch n: Là quá trình lo i b các cá th x u trong qu n th , ch gi l i trong qu n th các cá th t t 1.2.2.3. Quá trình ñ t bi n (Mutation):
6 Đ t bi n là hi n tư ng cá th con mang m t s tính tr ng không có trong mã di truy n c a cha-m . 1.2.3. T ng quát v gi i thu t di truy n : Hình 1.1 Gi i thu t di truy n t ng quát 1.2.4. Tính h i t trong gi i thu t di truy n Cho GA=( I , Ψ , Ω, s, t , µ , λ ) n u các ñi u ki n sau th a: • I là không gian h u h n, ñ m ñư c; • L i gi i t i ưu a* ∈ I Thì gi i thu t s d ng và l i gi i tìm ñư c chính là l i gi i t i ưu a* 1.2.5. Nguyên lý ho t ñ ng c a c a gi i thu t : • Bư c 1: Ch n m t s tư ng trưng cho toàn b các l i gi i • Bư c 2: Ch ñ nh cho m i l i gi i m t ký hi u. Ký hi u có th là m t dãy các bits 0, 1 hay dãy s th p phân • Bư c 3: Tìm hàm s thích nghi và tính h s thích nghi • Bư c 4: T c hi n tái sinh và ch n. • Bư c 5: Tính h s thích nghi cho các cá th m i, i l i m t s nh t ñ nh các cá th tương ñ i t t.
7 • Bư c 6: N u chưa tìm ñư c l i gi i t i ưu hay tương ñ i t t nh t, quay l i bư c 4 ñ tìm l i gi i m i. • Bư c 7: K thúc gi i thu t và báo cáo k t qu tìm ñư c. Hình 1.2 Sơ ñ t ng quát c a gi i thu t di truy n 1.2.6. Xây d ng mô hình gi i thu t di truy n nâng cao : Hình 1.3 Mô hình gi i thu t di truy n nâng cao
8 1.3. S K T H P GI A DI TRUY N VÀ LEO Đ I. 1.3.1 Khái ni m: Sau khi tìm ñư c l i gi i t i ưu c a bài toán thì v n ñ còn l i là ph i chính xác hóa nghi m t i ưu v a tìm ñư c, mà thu t toán leo ñ i l i ch cho phép tìm ñư c gi i pháp t i ưu c c b . 1.3.2. K t h p di truy n và leo ñ i • Bư c 1: Ch y gi i thu t di truy n cho ñ n khi cá th th h m i không t t hơn nhi u so v i th h trư c. • Bư c 2: Gán n cá th t t nh t c a gi i thu t di truy n cho n ñi m xu t phát c a gi i thu t leo ñ i. • Bư c 3: Ch y gi i thu t leo ñ i tìm ñư c l i gi i t i ưu CHƯƠNG 2. NG D NG GI I THU T DI TRUY N TÌM C C TR C A HÀM NHI U BI N 2.1. Đ T V N Đ Hi n nay có r t nhi u phương pháp gi i quy t bài toán t i ưu hàm s , nhưng các phương pháp ch d ng l i nh ng l p bài toán v i nh ng thông tin rõ ràng. Do ñó, vi c tìm ra m t phương pháp m i ñ gi i bài toán t i ưu hàm nhi u bi n t ng quát là c n thi t. Nhưng ñ gi i quy t l p hai bài toán trong lu n văn này thì ph i có m t công c c n thi t ph i thi t k là bài toán tìm c c tr (giá tr Max hay Min) c a m t hàm s nhi u bi n mà m i bi n có th nh n các giá tr s n m trên m t mi n con ho c toàn mi n s th c (t − ∞ ñ n + ∞ ). 2.2. BI U DI N BI N Cho m t hàm nhi u bi n y = f ( x1 , x 2 ,..., x n ) v i xi ∈ Di = [ a i ,bi ] ⊆ R . Đ bi u di n xi (i=1,…,n) sao cho có th th c hi n các phép toán di truy n m t cách hi u qu , thì ta bi u di n xi b ng chu i bit nh phân. Gi s xi là m t s th c có k ch s th p phân sau d u ch m. Thì giá tr bi − a i c a xi là: x i = a i + decimal(U) 2m − 1 i
9 2.3. CÁC GIÁ TR L A CH N TRONG GI I THU T DI TRUY N 2.3.1. L a ch n kích thư c c a qu n th Đ ñ m b o kích thư c qu n th không quá l n ñ ng th i cũng giúp tăng hi u qu và tính chính xác c a gi i thu t khi hàm s có s bi n l n, thì ta nên ch n kích thư c qu n th ph thu c vào s bi n c a hàm s : µ = 100 +10 *NumVar (NumVar là s bi n c a hàm s ). 2.3.2. L a ch n s l n ti n hóa c a gi i thu t Đ ñ m b o tính chính xác c a gi i thu t ta ch n s l n ti n hóa NumGen = 100 + 10 * NumVar (NumVar là s bi n c a hàm s ). 2.3.3. L a ch n xác su t lai ghép S k t h p các l i gi i cha m t o sinh các cá th m i trong gi i thu t di truy n b ng toán t lai ghép 2.3.4. L a ch n xác su t ñ t bi n Xác su t ñ t bi n PM= 1 . GenSize 2.3.5. L a ch n kho ng giá tr c a các bi n Xác ñ nh ñư c kho ng giá tr c a x thu c kho ng [a,b] nào ñó. V i l p bài toán trong lu n văn thì m i bi n xi s thu c [ − ∞,+∞ ]. Nhưng trong máy tính, m i ki u d li u ñư c khai báo cho bi n có giá tr khác nhau, giá tr ∞ có th ñư c quy ư c b ng giá tr l n nh t c a ki u d li u ñó. 2.4. HÀM ĐO Đ THÍCH NGHI (EVAL FUNCTION) 2.4.1. Ánh x giá tr hàm m c tiêu f(x) sang giá tr thích nghi (Eval) - N u bài toán t i ưu là tìm c c ti u c a m t hàm ñánh giá g(x) thì ta xây d ng như sau: C − g ( x) khi g(x) < C Max f ( x) =  Max 0 Trong cac truong hop khac - N u bài toán t i ưu là tìm c c ñ i c a m t hàm ñánh giá g(x) thì ta xây d ng như sau:
10 C + g ( x ) khi g(x) + C Min > 0 f ( x) =  Min 0 Trong cac truong hop khac Trong ñó CMax, CMin là m t tham s ñ u vào. 2.4.2. Đi u ch nh ñ thích nghi • G i G là ñ t t c a cá th , ñ thích nghi c a cá th theo phương pháp ñi u ch nh tuy n tính ñư c xác ñ nh theo quy t c sau: F=a*G+b • Giá tr ñ thích nghi cu i cùng này l i n m trong ño n[0,1]. 2.5 CÁC PHÉP TOÁN DI TRUY N 2.5.1. Kh i t o qu n th ban ñ u Begin for i:=0 to PopSize-1 do for j:=0 to GenSize-1 do QuanThe.CaThe[i][j]:=Flip(0.5); End; Flip(0.5) là hàm t o các ng u nhiên 0 và 1 v i xác su t 50% Hình 2.3 Đo n mã gi minh h a cho thao tác kh i t o qu n th 2.5.2. Phép ch n cá th (Selection) S d ng phương pháp thông d ng là quy t c ch n theo bàn Roulete. Quá trình này ñư c th c hi n theo các bư c: • Bư c 1: Tính ñ thích nghi cho t ng cá th trong qu n th . • Bư c 2: Tính t ng ñ thích nghi c a t t c các cá th • Bư c 3: Phát sinh m t s ng u nhiên p n m trong kho ng t 0 ñ n t ng ñ thích nghi c a qu n th . • Bư c 4: Tr v cá th ñ u tiên mà ñ thích nghi c a nó và ñ thích nghi c a các cá th khác nhau trong qu n th trư c ñ y. 2.5.3. Phép lai ghép (CrossOver)
11 Phép lai ñư c th c hi n trên hai cá th cha m ñư c ch n v i xác su t pc ∈ [0, 1] và ñư c th c hi n theo nhi u cách khác nhau. • Lai ghép ñơn ñi m • Lai ghép ña ñi m CHƯƠNG 3. PHÂN L P D LI U B NG CÁC HÀM PHÂN BI T TUY N TÍNH 3.1 PHÂN L P D LI U 3.1.1 Khái ni m Khi phân tích d li u, thư ng d a vào m t s tiêu chu n hay các ñ i lư ng khác nhau v b n ch t. Ví d : Khi phân lo i b nh nhân m c m t ch ng b nh nào ñó thì c n căn c vào m t s tiêu chu n (huy t áp, các xét nghi m, ch p X quang,…) c a ngư i ñó và các b nh ñã có. Khi xác ñ nh ñư c các d ki n liên quan ñ n nh ng ch tiêu ñã ch n, chúng ta có th d ñoán ñư c kh năng ch n ñoán b nh c a b nh nhân ñó ñó v i ñ chính xác cao. Thay vì nghiên c u trên t p d li u l n thì sau khi phân l p d li u ta s ti n hành phân tích trên các t p d li u nh hơn mà m i t p d li u này có m t s tính ch t ñ c thù tùy thu c vào các ch tiêu l a ch n ñ phân nhóm t p d li u thu th p ban ñ u. 3.1.2. Các bư c ñ gi i quy t bài toán phân l p Bư c 1: H c (training). Bư c 2 : Ki m tra và ñánh giá. 3.1.3. Hàm phân l p tuy n tính Hàm phân l p tuy n tính có ranh gi i phân l p là 1 siêu ph ng, vì v y nó ch phân tách ñư c 2 l p. Ví d : Xét hàm tuy n tính phân tách Rn thành 2 n a không gian (half- space). Đ cho ti n, ta gán w1 = +1, w2 =-1, lu t phân l p khi s d ng hàm phân l p tuy n tính là:
12 f(x) = θ((w, x) -b) (3.1) + 1, t ≥ 0 θ( t ) =  (3.2)  − 1, t < 0 Trong ñó, f(x) là hàm phân l p, θ(t) là hàm ngư ng (threshold function), (w, x) là tích vô hư ng c a w, x, w là tr ng s (weight) trên các t a ñ /ñ c trưng c a x, b là ngư ng (threshold). 3.2. HÀM PHÂN BI T TUY N TÍNH VÀ M T QUY T Đ NH 3.2.1. Đ nh nghĩa: Hàm phân bi t tuy n tính là m t hàm s nh n m t vector ñ u vào x và gán nó cho m t trong c l p. Hàm phân bi t tuy n có d ng: k g(x) = W0 + W1 X1 + W2 X 2 + ... + Wk X k = W0 + ∑ Wi X i = W t X + W0 (3.3) i =1 Trong ñó: W = (W1, W2, ..., Wk) là vectơ tr ng s và W0 ñư c g i là tr ng s n n hay ngư ng. X = (X1, X2, ... Xk) là các bi n ñ c l p. 3.2.2. Trư ng h p phân hai l p N u lo i d li u phân thành hai l p thì phương trình (1) tr thành : g(X) = W0 + W1X1 (3.4) D a vào hàm phân bi t (2) s phân chia d li u thành hai l p ñư c th c hi n d a trên quy t ñ nh sau: Quy t ñ nh là thành ph n d li u thu c vào W1 n u ta có g(X) > 0 và quy t ñ nh là W2 n u g(X) < 0. Trư ng h p g(X)= 0 WtX1 + W0 = WtX2 + W0 hay Wt(X1 – X2) = 0 (3.5) Do ñó khi g(X) > 0 thì X ñư c gán ñ n W1 (X n m trên R1), ngư c l i thì X ñư c gán ñ n W2 (X n m trên R2). Khi X thu c R1 thì ta có th nói X thu c ph n dương c a H và khi X thu c R2 thì ta có th nói X thu c ph n âm c a H. Hàm phân bi t tuy n tính g(X) ch ra kho ng cách ñ i s t X ñ n siêu ph ng H. Vì v y, có l cách ñơn gi n nh t là bi u di n X theo bi u th c sau: W (3.6) X = Xp + r Trong ñó: W • Xp là hình chi u chu n c a X trên H.
13 • r là kho ng cách ñ i s t X ñ n siêu ph ng H. Hình 3.2 M t quy t ñ nh tuy n tính H xác ñ nh b i g(X) = WtX + W0, và chia không gian thành 2 n a không gian R1(g(X)>0) và R2(g(X)
14 1  X   1  y=  1 =   (3.10)  ...      X   X k  y ñư c g i là vectơ gia tăng ñ c tính. Tương t vectơ gia tăng tr ng s có th ñư c vi t dư i d ng sau:  W0   W   W0  a =  1 =   (3.11)  ...      W    Wk  Hình 3.5 Minh h a chuy n ñ i to ñ t không gian X-2 sang không gian y-3 chi u 3.3. T NG BÌNH PHƯƠNG SAI S T I TI U 3.3.1 Trong trư ng h p phân hai l p (The Two-Category Case) Gi s có m t t p h p n m u y1, y2, ..., yn Trong ñó m t s m u ñư c gán nhãn W1 và m t s ñư c gán nhãn W2. Đ xác ñ nh vectơ tr ng s a trong hàm phân bi t tuy n tính g(X) = aty. M u yi ñư c phân l p chính xác n u aty > 0 và ñư c gán nhãn là W1 ngư c l i thì yi ñư c gán nhãn là W2. V y, ta ñã thay th vi c tìm gi i pháp cho m t t p h p các b t phương trình tuy n tính b i tìm gi i pháp cho m t t p h p các phương trình tuy n tính.
15  y10 y11 L y1k   b1       y 20 y 21 L y 2 k  a0   b2   M   (3.12) M M M   a1   M    =   hay Ya = b  M M M M   M   M       M  a   M M M M   k   y y n1 L y nk  b   n0   n Ta có th vi t (12) dư i d ng: a = Y-1b (N u Y là ma tr n kh ngh ch) do ñó, ta có th tìm vectơ tr ng s a sao cho sai s Y*a và b là c c ti u. G i vectơ e là: e = Ya – b (3.13) Thì ta c n ph i tìm vectơ a sao cho: 2 J (a) s = Ya- b = (Ya − b) t (Ya − b) = ∑ (a t y i − bi ) 2 (3.14) Đ tìm c c ti u c a t ng bình phương các sai s thì ta tìm b ng phương pháp ñ o hàm: n ∇J s (a ) = ∑ 2(a t y i − b i ) y i = 2Y t ( Ya − b) (3.15) i =1 Cho phương trình ñ t giá tr 0 và gi i ra ta ñư c ñi u ki n: YtYa = Ytb (3.16) V y ta ch c n tìm nghi m a th a mãn phương trình (3.16) là ñ . Gi i ra ta ñư c : a = (YtY)-1 Ytb = Y*b (3.17) * t -1 t Y = (Y Y) Y (3.18) 3.3.2. Trong trư ng h p phân nhi u l p: Ta có: g i ( X ) = W t X + Wi 0 v i i = 1, 2, …, c Đ t y(X) là m t vectơ k+1 chi u c a các hàm X và khi ñó, g i ( X ) = ait y i=1, 2, …, c (3.19) Khi ñó, X ñư c gán cho l p Wi n u gi(X) > gj(X) v i ∀ j ≠ i Lúc này t n t i m t t p h p các vectơ tr ng s ai (i = 1, 2, …,c) sao cho n um u yk ∈ Yk thì a it y k > a tj y k ∀ j ≠ i (3.20) Xem bài toán như là c bài toán con, m i bài toán con là m i bài toán phân lo i 2 nhóm. Nghĩa là ñ i v i bài toán con th i tr ng s s tìm vectơ tr ng s ai là k t qu c a h phương trình:
16  a it y = 1 ∀i ∈ Yt  t (3.21)  a i y = −1 ∀i ∉ Yt Ma tr n Y trong trư ng h p t ng quát s là m t ma tr n c p (nx(k+1)) c a các m u ñư c xét. Gi s Y ñư c phân ho ch có d ng:  Y1    Y = Y2  (3.22)  M     Yc  Tương t g i A là ma tr n c p ((k+1) x c) c a các vectơ tr ng s có d ng t ng quát là: A = [a1 a2 … a c] (3.23) Ma tr n B là ma tr n c p (n x c) có d ng  B1  B  B =  2 (3.24) M     Bc  Theo cách phát tri n c a ma tr n bình phương l i (YA – B)t (YA – B) khi ñó là k t qu c a phương trình: A = Y* B (3.25) Bây gi , vi c tìm c hàm phân bi t tuy n tính th c hi n theo các bư c sau: Bư c 1: Tìm các vectơ tr ng s ai theo phương pháp MSE thõa h phương trình:  a i y = 1 ∀i ∈ Yi t (3.26)  t  ai y = 0 ∀i ∉ Yi Bư c 2: S d ng k t qu c a bư c 1, gán m u yk cho nhóm Wi, n u y k v i ∀i ≠ t t ai yk > aj j 3.3.3. Qui trình th c hi n chương trình phân l p d li u Bư c 1: Nh p d li u g m m t t p m u ng u nhiên ( X1 , X1 ,..., X1 ) , 1 2 k ( X1 , X 2 ,..., X 2 ) , …, ( X1 , X n ,..., X n ) thu ñư c t quan sát lưu tr dư i d ng 2 2 k n 2 k b ng d li u.
17 Bư c 2: Tìm ư c lư ng c a các h s c a các vectơ tr ng s ai b ng thu t toán di truy n Bư c 3: V ñ th minh h a cho k t qu c a s phân l p. Bư c 4: Cho m t b các giá tr ( X1 , X * ,..., X * ) xác ñ nh xem m u này * 2 k s thu c vào l p nào trong các phân nhóm. CHƯƠNG 4. PHÂN TÍCH H I QUY 4.1. D N NH P Hi n nay các v n ñ trong khoa h c, k thu t hay nh ng lĩnh v c khác trong th c t , có liên quan ñ n vi c xác ñ nh m i liên h gi a m t t p h p các tiêu chu n hay các ñ i lư ng (các bi n) khác nhau v b n ch t. Chúng ta có th làm rõ b n ch t c a hi n tư ng hay s vi c c n nghiên c u ñ tìm ra quy lu t và d ñoán. D ng ñơn gi n là, phương trình h i quy: Y = b0 + b1X1 + b2X2 + b3X3 + ... + bkXk (4.1) 4.2. Ư C LƯ NG CÁC MÔ HÌNH TOÁN H C 4.2.1. Ư c lư ng các mô hình toán h c Các bư c ñ ư c lư ng mô hình toán h c bao g m: Bư c 1: Mô hình hóa ñ i tư ng nghiên c u ñ ti n hành thu th p s li u th c nghi m. • Bư c 2: D ñoán mô hình toán h c d a trên cơ s các s li u ñã thu th p ñư c trong quá trình nghiên c u. • Bư c 3: Xác ñ nh các h s c a mô hình toán h c • Bư c 4: Ki m ñ nh s phù h p c a mô hình toán ñã d ñoán. 4.2.2. Mô hình hóa ñ i tư ng nghiên c u G i X1, X2 ..., Xk là các nguyên nhân tác ñ ng gây nên h u qu hay k t qu Y thì hàm Y = f(X1, X2, ..., Xk) → Y. 4.2.3. Xây d ng mô hình toán h c 4.2.3.1. Phương pháp “ñ th th c nghi m” và “tuy n tính hóa”:
18 Mô hình toán h c có th d ñoán nh ñ th th c nghi m ñư c phác h a t các s li u thu t p ñư c. 4.2.3.2.D ñoán mô hình toán h c b ng phương pháp suy lu n: Ch ng h n, mô hình gradient m t ñ hay n ng ñ có th d ñoán ñư c là Y=aX + b, v i b là m t ñ hay n ng ñ trung tâm xu t phát ñi m, X là kho ng cách t trung tâm ñó ñ n ñi m ñang xét. ñây, X có th ñư c thay th b ng các X X 2 ñ i di n c a nó như lnX, 10 , e , X ,... 4.2.4. Tìm các h s c a mô hình toán h c Hai phương pháp thư ng ñư c s d ng là : - Phương pháp t i thi u hóa t ng bình phương sai s - Phương pháp Moment. 4.2.5. Ki m ñ nh và ñánh giá m c ñ phù h p c a mô hình toán h c Mô hình toán h c Y = b0 + b1X1 + b2X2 + ... + bkXk hay Y* - Y = b1 (X1 - X ) + b2 (X2 - X ) + ... + bK (Xk - X ) 4.3. PHƯƠNG PHÁP T I TI U HÓA T NG BÌNH PHƯƠNG SAI S (MINIMUM SUM SQUARED METHOD) 4.3.1. Phương pháp t i ti u hóa t ng bình phương sai s Phương pháp bình phương t i thi u là phương pháp chu n ñ c th hoá mô hình h i quy tuy n tính và ư c lư ng các thông s chưa bi t và tuân theo 4 gi thi t sau ñây: 1. Các bi n ñ c l p xi không ph i là các bi n ng u nhiên. 2. Kỳ v ng toán c a thành ph n sai s (εi) b ng 0, t c là E[εi]=0 3. Có tính thu n nh t - phương sai c a thành ph n sai s c ñ nh, t c là var(εi) = σ2 4. Không có t tương quan, t c là cov(εi, εj) = 0, (i ≠ j) N u f có d ng phi tuy n thì ta s ti n hành tuy n tính hóa mô hình toán h c trư c khi ti n hành phân tích. Khi ñó, phương trình h i quy s có d ng như phương trình (2):
19 Y = ϕ(X1, X2, ..., Xk) = f(X1,X2,...,Xk; b0, b1,...,b) (4.2) Hay Y = b0 + b1X1 + b2X2 + b3X3 + ... bkXk (4.3) N u giá tr Y h i quy, hoàn toàn trùng kh p v i giá tr Y th c nghi m. Khi ñó, ta có : Y = b0 + b1X1 + b2X2 + b3X3 + ... bkXk+e (4.4) n Qe = ∑ (Yi − Yi* ) 2 (4.5) i =1 Đ tìm các tham s b0, b1, ... bk ta l y ñ o hàm riêng c a Qe theo các bi n b0, b1, ... bk, cho các giá tr ñ o hàm này b ng 0, ta có h phương trình sau:  ∂ (Qe )  ∂(b ) = 0  0  ∂ (Qe ) (4.6)  =0  ∂ (b1 ) ... ...   ∂ (Qe )  ∂ (b ) = 0  k 4.3.2. Tìm giá tr c a các h s h i quy b ng thu t gi i di truy n Đ xác ñ nh các giá tr c a các h s h i quy b0, b1, ,,, bk chúng ta s d ng công c tìm giá tr t i thi u c a hàm nhi u bi n b ng thu t gi i di truy n ñã ñư c trình bày trong chương 2 ñ tìm giá tr c c tiêu g n ñúng c a Qe. T ñó xác ñ nh ñư c các giá tr ư c lư ng c a các tham s b0, b1, ..., bk c a phương trình h i quy tuy n tuy n. 4.4. Ư C LƯ NG H I QUY TUY N TÍNH 4.4.1. Ư c lư ng H i quy tuy n tính ñơn Cho hai ñ i lư ng h i quy tuy n tính ng u nhiên X và Y , khi ñó mô hình h i quy tuy n tính ñơn t ng quát có d ng: Y = b0 + b1X
20 Trong ñó b0 và b1 ñư c xác ñ nh như sau: n n ∑ (x − x)( yi − y) ∑ (x y − n x y) b1 = i i i ; b0 = y − b1 x i =1 2 = i =1 n n ∑ (x i − x) ∑ (x 2 i − nx2 ) i =1 i =1 Vi c phân tích h i quy d a trên mô hình toán h c ñư c th c hi n như sau: • Bư c 1: Tìm giá tr c c ti u c a m t hàm nhi u bi n s (hai bi n) b ng thu t gi i di truy n ñ xác ñ nh các h s h i quy b0, b1 c a mô hình toán h c và giá tr g n ñúng c a Qe. • Bư c 2: Ki m ñ nh s phù h p theo các công th c: 2 n n 1 n  (4.7) Q x = ∑ (X i − X) 2 = ∑ Xi2 −  ∑ X i  i =1 i =1 n  i=1  2 n 1 n  n (4.8) QY = ∑ (Yi − Y) = ∑ Y −  ∑ Yi  2 i 2 i =1 i=1 n  i=1  n Qe = ∑ (Yi − Yi* ) 2 (4.9) i =1 2 n n 1 n  (4.10) Q Y* = ∑ (Yi* − Y) 2 = ∑ (Yi* )2 −  ∑ Yi  i =1 i =1 n  i=1  Q Y = Q Y* + Q e (4.11) (n − 2)QY* (4.12) F(1,n − 2) = Qe QR Q (4.13) r =R = = 1− e QY QY B ng 4.1 B ng ki m ñ nh & ñánh giá m c ñ phù h p c a mô hình toán h c Y = b0 + b1X Ngu n bi n lư ng Đ t do T ng các bình phương Bi n lư ng Q Y* Qe H i quy 1 S2 = (n − 2) Sai s ng u nhiên n-2 Qe