Bài giảng Công nghệ tri thức và ứng dụng - Phần 3: Khai mỏ dữ liệu và khám phá tri thức - Chương 6: Máy học và khám phá tri thức

ao(Cao) = (0/2,2/2) = (0,1) VC.Cao(T.B) = (2/3,1/3) VC.Cao(Thaáp) = (1/3,2/3)   VC.Naëng (Nheï) = (1/2,1/2) VC.Naëng (T.B) = (1/3,2/3) VC.Naëng (Naëng) = (1/3,2/3)   VKem (Coù) = (3/3,0/3) = (1,0) VKem (Khoâng) = (3/5,2/5) III.4 Học dựa trên cây định danh (tt) Nhö vaäy thuoäc tính maøu toùc coù soá vector ñôn vò nhieàu nhaát neân seõ ñöôïc choïn ñeå phaân hoaïch. Phaân hoaïch theo toùc vaøng (Pvaøng) laø coøn chöùa nhöõng ngöôøi chaùy naéng vaø khoâng chaùy naéng. Tieáp tuïc phaân hoaïch taäp naøy. Tính vector ñaëc tröng töông töï ñoái vôùi caùc thuoäc tính coøn laïi (chieàu cao, caân naëng, duøng kem). Trong phaân hoaïch Pvaøng, taäp döõ lieäu cuûa chuùng ta coøn laïi laø : III.4 Học dựa trên cây định danh (tt) III.4 Học dựa trên cây định danh (tt) VC.Cao(Cao) = (0/1,1/1) = (0,1) VC.Cao(T.B) = (1/1,0/1) = (1,0) VC.Cao(Thaáp) = (1/2,1/2)   VC.Naëng (Nheï) = (1/2,1/2) VC.Naëng (T.B) = (1/2,1/2) VC.Naëng (Naëng) = (0,0)   VKem (Coù) = (0/2,2/2) = (0,1) VKem (Khoâng) = (2/2,0/2) = (1,0) III.4 Học dựa trên cây định danh (tt) 2 thuoäc tính duøng kem vaø chieàu cao ñeàu coù 2 vector ñôn vò. Tuy nhieân, soá phaân hoaïch cuûa thuoäc tính duøng kem laø ít hôn neân ta choïn phaân hoaïch theo thuoäc tính duøng kem. Caây ñònh danh cuoái cuøng: III.4 Học dựa trên cây định danh (tt) Độ đo hỗn loạn: Thay vì phaûi xaây döïng caùc vector ñaëc tröng nhö phöông phaùp cuûa Quinlan, öùng vôùi moãi thuoäc tính daãn xuaát ta chæ caàn tính ra ñoä ño hoãn loaïn vaø löïa choïn thuoäc tính naøo coù ñoä ño hoãn loaïi laø thaáp nhaát. Coâng thöùc tính nhö sau: bt laø toång soá phaàn töû coù trong phaân hoaïch bj laø toång soá phaàn töû coù thuoäc tính daãn xuaát A coù giaù trò j. bri : toång soá phaàn töû coù thuoäc tính daãn xuaát A coù giaù trò j vaø thuoäc tính muïc tieâu coù giaù trò i. c. Phát sinh tập luật (Maøu toùc vaøng) vaø (coù duøng kem)  khoâng chaùy naéng (Maøu toùc vaøng) vaø (khoâng duøng kem)  chaùy naéng (Maøu toùc naâu)  khoâng chaùy naéng (Maøu toùc ñoû)  chaùy naéng Vấn đề tiếp theo là tối ưu tập luật (tham khảo phần tối ưu hóa CSTT) III.4 Học dựa trên cây định danh (tt) III.6 Tiếp cận mạng Neural Maïng neural laø thuaät ngöõ noùi ñeán moät phöông phaùp giaûi quyeát vaán ñeà – baøi toaùn treân maùy tính moâ phoûng theo hoaït ñoäng cuûa caùc teá baøo thaàn kinh trong naõo boä. Maïng neural nhaân taïo laø söï moâ phoûng caáu truùc cuûa maïng neural sinh hoïc. Maïng neural nhaân taïo ñöôïc taïo thaønh bôûi söï noái keát giöõa raát nhieàu ñôn vò thaàn kinh goïi laø perceptron. III.6 Tiếp cận mạng Neural   Caùc haøm truyeàn thöôøng ñöôïc söû duïng:   Haøm logistic (hay coøn goïi laø haøm Sigma)  Haøm hyperbol Haøm tang-hyperbol III.6 Tiếp cận mạng Neural (tt) III.6 Tiếp cận mạng Neural (tt) Mô hình minh họa mạng neural 1 lớp III.6 Tiếp cận mạng Neural (tt) Mô hình minh họa mạng neural tổng quát III.6 Tiếp cận mạng Neural (tt) 1. Mạng lan truyền (Feed Forward) Nguyên tắc xác định giá trị Output của node 5: a5 	= f (W3,5a3 + W4,5a4) 	= f (W3,5 f(W1,3a1 + W2,3a2) + W4,5 f(W1,4a1 + W2,4a2)) III.6 Tiếp cận mạng Neural (tt) 2. Mạng Hopfield Mạng Hopfield hoạt động tương tự hoạt động một bộ nhớ kết hợp có: Wi,j = Wj,i +3 -2 -1 +1 +2 +1 -1 +1 -1 +3 -1 +3 -2 -1 +1 +2 +1 -1 +1 -1 +3 -1 III.5 Tiếp cận mạng Neural (tt) 3. Mạng Perceptron III.5 Tiếp cận mạng Neural (tt) Mạng Perceptron input output Xi Wi,j Oj Perceptron đơn lẻ Wi = Wi + *Xi Wi = Wi - *Xi : hệ số học T - O O T : đầu ra mong muốn O: đầu ra của mạng III.6 Tiếp cận mạng Neural (tt) Khả năng phân chia tuyến tính trong mạng Perceptron I2 I1 0 0 1 I2 I1 0 0 1 1 I2 I1 0 0 1 ? (a) I1 and I2 (b) I1 or I2 (c) I1 xor I2 III.6 Tiếp cận mạng Neural (tt) Hạn chế của mạng Perceptron - Năm 1969, Minsky và Papert đã phân tích và chứng minh sự thất bại của mạng Perceptron với bài toán XOR. III.6 Tiếp cận mạng Neural (tt) Xét từng trường hợp: Nếu [I1, I2]=[0,0] thì y(I1, I2)=0  W1*0 + W2*0 0 Nếu [I1, I2]=[0,1] thì y(I1, I2)=1  W1*0 + W2*1      W1 Nếu [I1, I2]=[1,0] thì y(I1, I2)=1  W1*1 + W2*0      W2 Nếu [I1, I2]=[1,1] thì y(I1, I2)=0  W1*1 + W2*1 W1 + W2 Rõ ràng không thể tìm được W1, W2,  thỏa mãn 4 bất đẳng thức trên. Mô hình Perceptron không thể tìm ra lời giải trong trường hợp này vì hàm XOR không phải là hàm ngưỡng tuyến tính. III.6 Tiếp cận mạng Neural (tt) Ví dụ minh họa việc học của mạng Perceptron: Khởi tạo trọng số: w1=1; w2=0; w3=0; w4=0; w5=1 III.6 Tiếp cận mạng Neural (tt) Dự đoán lần thứ nhất đối với mẫu “Cây Iris A” Perceptron dự đoán “Loài” có kết quả là 1 so với kết quả đúng là -1 Cập nhật trọng số mạng ( : Tỉ lệ học nên chọn nhỏ, ở đây ta chọn  = 0.05) Nếu kết quả “Loài” là 1 so với kết quả đúng là -1 III.6 Tiếp cận mạng Neural (tt) Các trọng số này dùng để luyện cho những mẫu kế tiếp Điều kiện dừng: Tất cả các mẫu đã được dự đoán đúng. Dừng sau một số bước lặp do người dùng quyết định. III.6 Tiếp cận mạng Neural (tt) Nhận xét:	Cập nhật trọng số sao cho tối tiểu sai lệch. Nếu kết quả “Loài” là 1 so với kết quả đúng là -1 Nếu kết quả “Loài” là -1 so với kết quả đúng 1 (1) wixi góp phần làm cho > 0. Trọng số mới là wi  wi - *xi. Vì thế bước kế tiếp cho cùng mẫu dữ liệu ta được ( wi - *xi )*xi = wixi – r*xi2 0 then tăng O 	else giảm O Bước 2: Cập nhật giá trị ma trận trọng số 	Wj = Wj + * xj*Err. ( là hệ số học) Bước 3: Lặp lại bước 1 và 2 cho đến khi Err Cho ra Ok sai lệch với kết quả mong muốn yk. Sai lệch của mẫu thứ k là Ek: Ek = ½*(yk - Ok)2 = ½(yk – f(wT x))2 III.6 Tiếp cận mạng Neural (tt) Sai lệch của tất cả các mẫu: Cập nhật trọng số: theo hướng cực tiểu hóa sai lệch : là hệ số học III.6 Tiếp cận mạng Neural (tt) Ví dụ minh họa cho phương pháp lan truyền ngược Chọn hàm truyền: III.6 Tiếp cận mạng Neural (tt) Các unit input Các unit ẩn Các unit output xk Wk,j hj Wj, i Oi a b o 1 2 3 4 0 0 III.6 Tiếp cận mạng Neural (tt) Khởi tạo các trọng số có giá trị ngẫu nhiên nhỏ W0a = 0.0	Trọng số cột giá trị -1 trong đơn vị ẩn a W1a = 0.1	Trọng số trong đơn vị ẩn a từ giá trị nhập thứ 1 W2a = -0.1	Trọng số trong đơn vị ẩn a từ giá trị nhập thứ 2 W3a = -0.1	Trọng số trong đơn vị ẩn a từ giá trị nhập thứ 3 W4a = 0.0	Trọng số trong đơn vị ẩn a từ giá trị nhập thứ 4 III.6 Tiếp cận mạng Neural (tt) W0b = 0.0	Trọng số cột giá trị -1 trong đơn vị ẩn b W1b = -0.1	Trọng số trong đơn vị ẩn b từ giá trị nhập thứ 1 W2b = 0.2	Trọng số trong đơn vị ẩn b từ giá trị nhập thứ 2 W3b = 0.1	Trọng số trong đơn vị ẩn b từ giá trị nhập thứ 3 W4b = -0.1	Trọng số trong đơn vị ẩn b từ giá trị nhập thứ 4 W0o = 0.1	Trọng số cột giá trị -1 trong đơn vị xuất o Wao = 0.2	Trọng số cột trong đơn vị ẩn b từ đơn vị ẩn a Wbo = -0.1	Trọng số cột trong đơn vị ẩn b từ đơn vị ẩn b III.6 Tiếp cận mạng Neural (tt) Bước 1: Dự đoán Đối với “cây Iris A” đầu tiên ta tính giá trị xuất của nút ẩn a oa 	= f (w0a + w1ax1 + w2ax2 + w3ax3 + w4ax4) 	= f (0.0 + 0.1*4.7 + (-0.1)*3.2 + (-0.1)*1.3 + 0.0*0.2) 	= f (0.02) = 1/(1 + e -0.02) = 0.5050 Tương tự với nút ẩn b ob	= f (w0b + w1bx1 + w2bx2 + w3bx3 + w4bx4) 	= f (0.0 + (-0.1)*4.7 + 0.2*3.2 + 0.1*1.3 + (-0.1)*0.2) 	= f (0.28) = 1/(1 + e -0.28) = 0.5695 III.6 Tiếp cận mạng Neural (tt) Cuối cùng ta tính giá trị xuất cho nút xuất o oo	= f (w0o + waooa + wboob) 	= f (0.1 + 0.2*0.5050 + (-0.1)*0.5695) 	= f (0.1440) = 1/(1 + e –0.1440) = 0.5359  Giá trị dự đoán cho “cây Iris A” là 0.5359 III.6 Tiếp cận mạng Neural (tt) Bước 2: Xác định sai lệch Dùng kỹ thuật lan truyền ngược (back propagation) Với 	to	: giá trị xuất mong muốn 	oo	: giá trị xuất thật Sai lệch cần tính cho nút xuất o: o = oo(1 - oo)(to - oo) Sai lệch cần tính cho nút ẩn h từ o là: oh(1-oh)who o Trong ví dụ đang xét “cây Iris A” có t0 = 0. Sai lệch của nút xuất o: o=o0(1-o0)(t0-o0)=0.5359*(1-0.5359)*(0-0.5359) = -0.1333 III.6 Tiếp cận mạng Neural (tt) Sai lệch của nút ẩn a: a 	= oa(1-oa)wao o = 0.5050*(1-0.5050)*0.2*(-0.1333) 	= -0.0067 Sai lệch của nút ẩn b: b 	= ob(1-ob)wbo o = 0.5695*(1-0.5695)*(-0.1)*(-0.1333) 	= 0.0032 III.6 Tiếp cận mạng Neural (tt) Bước 3: Bước cập nhật trọng số Chọn tỉ lệ học  = 0.1 w0a = w0a + *a *1 = 0.0 + 0.1*(-0.0067)*1 = -0.0007 w1a = w1a + *a *x1 = 0.1 + 0.1*(-0.0067)*4.7 = 0.0969 w2a = w2a + *a * x2 = -0.1 + 0.1*(-0.0067)*3.2 = -0.1021 w3a = w3a + *a * x3 = -0.1 + 0.1*(-0.0067)*1.2 = -0.1009 w4a = w4a + *a * x4 = 0.0 + 0.1*(-0.0067)*0.2 = -0.0001 w0b = w0b + *b *1 = 0.0 + 0.1*(0.0032)*1 = 0.0003 w1b = w1b + *b *x1 = -0.1 + 0.1*(0.0032)*4.7 = -0.0985 w2b = w2b + *b * x2 = 0.2 + 0.1*(0.0032)*3.2 = 0.2010 w3b = w3b + *b * x3 = 0.1 + 0.1*(0.0032)*1.2 = 0.1004 w4b = w4b + *b * x4 = -0.1 + 0.1*(0.0032)*0.2 = -0.0999 w0o = w0o + *o*1 = 0.1 + 0.1*(-0.1333)*1 = 0.0867 wao = wao + *o * oa = 0.2 + 0.1*(-0.1333)*0.5050 = 0.1933 wbo = wbo + *o * ob = -0.1 + 0.1*(-0.1333)*0.5695 = -0.1076 Tất cả các trọng số này sẽ dùng cho các mẫu kế tiếp. III.6 Tiếp cận mạng Neural (tt) III.6 Tiếp cận mạng Neural (tt) Thử tính cho “cây Iris A” thêm một bước kế tiếp, có kết quả: Oa = f (-0.0007 + 0.0969*4.7 + (-0.1021)*3.2 + 	(-0.1009)*1.3 + (-0.0001)*0.2) = f (-0.0032) = 0.4992 Ob = f (0.0003 + -(0.0985)*4.7 + 0.2010*3.2 + 	0.1004*1.3 + (-0.0999)*0.2) = f (0.2911) = 0.5724 Oo= f (0.0867 + 0.1933*0.4992 + (-0.1076)*0.5724) = f (0.1440) = 0.5304 Kết quả, ta thấy 0.5304 gần về 0 (kết quả mong muốn) so với kết quả của bước trước đó là 0.5359. III.6 Tiếp cận mạng Neural (tt) Tóm tắt giải thuật Cho trước K mẫu dữ liệu : với xk = (x1k, x2k, …, xnk) và yk  R, k = 1, …, K. Bước 1: chọn trước giá trị  > 0 và Emax >0. Bước 2: khởi tạo ngẫu nhiên w, bắt đầu với mẫu thứ nhất k = 1 và gán sai lệch E = 0. Bước 3: bắt đầu quá trình học, gán x = xk , y = yk. Đầu ra của mạng neuron tính theo: 	 	 III.6 Tiếp cận mạng Neural (tt) trong đó ok là giá trị ra của lớp ẩn, được tính bởi: Bước 4: cập nhật trọng số neuron đầu ra: với Bước 5: cập nhật trọng số của neuron ẩn (cho l = 1, …., L) III.6 Tiếp cận mạng Neural (tt) Bước 6: tính sai lệch bằng cách cộng thêm sai lệch hiện tại Bước 7: nếu k Emax gán E = 0 và bắt đầu một chu kỳ học mới bằng cách trở lại Bước 3.