TR NG Đ I H C L C H NG D ĐOÁN K T QU H C T P C A SINH VIÊN TR NG NGH SỬ D NG PH NG PHÁP H I QUY BAYES GIÁO VIÊN H NG D N: TS. HOÀNG TH LAN GIAO H C VIÊN TH C HI N: VẪ TH NG C LIÊN Đ ng Nai, tháng 09/2013 1 N I DUNG TRỊNH BÀY I. T ng quan khai phá d li u và phát hi n tri th c II. H h tr ra quy t đ nh và mô hình h tr quy t đ nh III. Phân tích h i quy IV. D đoán k t qu h c t p d a vƠo lỦ thuy t phơn l p Naive Bayes 2 T NG QUAN KHAI PHÁ D LI U VÀ PHÁT HI N TRI TH C 3 Gi i thi u v khai phá d li u (KPDL)   Khai phá tri thức từ một lượng lớn dữ liệu Sử dụng dữ liệu lịch sử để khám phá những qui tắc và cải thiện những quyết định trong tương lai 4 Quy trình phát hi n tri th c Bước 1: Hình thành, xác định, định nghĩa bài toán Bước 2: Thu thập, tiền xử lý dữ liệu Bước 3: Khai phá dữ liệu rút ra tri thức Bước 4: Phân tích và kiểm định kết quả Bước 5: Sử dụng tri thức phát hiện được Hình 1: Quy trình phát hiện tri thức 5 H H TR RA QUY T Đ NH VÀ MÔ HỊNH H TR QUY T Đ NH 6 H h tr ra quy t đ nh HHTQĐ là những hệ thống máy tính tương tác nhằm giúp những người ra quyết định sử dụng dữ liệu và mô hình để giải quyết các vấn đề không có cấu trúc. Các thƠnh ph n c a h h tr ra quy t đ nh     Phân hệ Quản lý dữ liệu Phân hệ Quản lý mô hình Phân hệ Quản lý dựa vào kiến thức Phân hệ Quản lý giao diện người dùng 7 V n d ng ph ng pháp toán h c để phơn l p d li u  Khái ni m v phân l p – Tiến trình xử lý nhằm xếp các mẫu dữ liệu hay các đối tượng vào một trong các lớp đã được định nghĩa trước. – Kỹ thuật phổ biến nhất của học máy và khai phá dữ liệu. 8  Các b c chính để gi i quy t bƠi toán phơn l p Bước 1: Học (Training): xây dựng mô hình phân lớp Bước 2: Phân lớp (classification): Bước này sử dụng mô hình phân lớp đã được xây dựng ở bước 1 để kiểm tra, đánh giá và thực hiện phân lớp.  Các kỹ thu t phân l p – Phương pháp dựa cây quyết định – Phương pháp dựa trên luật – Phương pháp Naive Bayes – Mạng Neuron – … 9  Ph  ng pháp phơn l p Naive Bayes Đ nh lý Bayes Tính xác suất xảy ra của một sự kiện ngẫu nhiên A khi biết sự kiện liên quan B đã xảy ra. – Xác suất này được ký hiệu là P(A|B) – Đọc là "xác suất của A nếu có B". 10 Theo đ nh lí Bayes, xác su t x y ra A khi bi t B s ph thu c vào 3 y u t :  P(A): Xác suất xảy ra A của riêng nó  P(B): Xác suất xảy ra B của riêng nó.  P(B|A): Xác suất xảy ra B khi biết A xảy ra Khi bi t ba đ i l công th c: ng trên, xác su t c a A khi bi t B cho bởi P BA P A P AB = P B 11 Mô hình phân l p Naive Bayes (NBC)  Mỗi mẫu được biểu diễn bằng X=(x1,x2,…,xn) với các thuộc tính a1, a2, …, an.  Các lớp {C1, C2,…,Cm} cho trước mẫu. NBC gán X vào Ci nếu P(X|Ci)>P(X|Cj) với 1 ≤ j ≤ m, j # i (theo định lý Bayes).  Để phân lớp mẫu chưa biết X, ta tính P(X|Ci)P(Ci) cho từng Ci. NBC gán X vào lớp Ci sao cho P(X|Ci)P(Ci) là l n nh t. 12 Thu t toán Naive Bayes Áp dụng trong bài toán phân loại, các dữ kiện gồm có: - D: tập dữ liệu huấn luyện đã được vector hóa � = � , � , … , �� - Ci: phân lớp i, với i = {1,2,…,m}. - Các thuộc tính độc lập điều kiện đôi một với nhau. Theo định lý Bayes: P X|Ci P Ci P Ci X = P X Theo tính chất độc lập điều kiện: P X Ci = n k= P x k Ci Trong đó: - � �� |�� xác suất thuộc tính thứ k mang giá trị xk khi đã biết X thuộc phân lớp i. 13 Các b  c th c hi n thu t toán phân l p Naive Bayes Bước 1: Huấn luyện Naive Bayes (dựa vào tập dữ liệu), tính P(Ci)và P(Xk|Ci).  Bước 2: Phân lớp Xnew=(x1,x2,…xn). Xnew ta cần tính xác suất thuộc từng phân lớp khi đã biết trước Xnew. Xnew được gán vào lớp có xác suất lớn nhất theo công thức: max � �� �� ∈� � �= � �� �� 14 Ví d : T p d li u m u v k t qu h c t p c a sinh viên TT N i ở Điểm vƠo 1 Nông thôn 2 Gtinh K t qu Trung bình Thấp Nữ Rớt Thành thị Cao Trung bình Nam Đậu 3 Nông thôn Thấp Trung bình Nam Rớt 4 Thành thị Trung bình Trung bình Nữ Đậu 5 Thành thị Trungbình Cao Nữ Đậu 6 Nông thôn Cao Nam Đậu 7 Nông thôn Trungbình Cao Nữ Đậu 8 Thành thị Thấp Thấp Nam Rớt Cao Kinh t Yêu c u: Phân lớp cho một thể hiện mới sau đây X=<Nông thôn, th p, trung bình, nam> (kết quả là Đậu (Đ) hay Rớt (R)). 15 Th c hi n: Bước 1: Ta có 2 lớp Đ=“Đậu”, R= “Rớt”, tổng số mẫu =8   Số mẫu được phân lớp Đ là 5  Xác suất Đậu: P(Đ)=5/8 Số mẫu được phân lớp R là 3  Xác suất Rớt: P(R) =3/8 Đặt X1(lớp Đ) = P Đ   iP X i Đ và X2 (lớp R) = P R iP Xi R X1 = P(Đ).P(Noio = Nongthon|Đ).P(Diemvao = thap|Đ). P(Kinhte = trungbinh|Đ). P(Gioitinh = Nam|Đ) X2 = P(R).P(Noio = Nongthon|R).P(Diemvao = thap|R). P(Kinhte = trungbinh|R). P(Gioitinh = Nam|R) 16 Ta lần lượt tính xác suất của các thuộc tính sau: P(Thành thị| Đ) =3/5 P(Nông thôn| Đ) =2/5 P(Cao| Đ) =2/5 P(Trung bình| Đ)=3/5 P(Thấp| Đ) =0/5 P(Cao| Đ) =3/5 P(Trung bình| Đ)=2/5 P(Thấp| Đ) =0/5 P(Nam| Đ) P(Nữ| Đ) =2/5 =3/5 N iở P(Thành thị| R) =1/3 P(Nông thôn| R) =2/3 Điểm vƠo P(Cao| R) =0/3 P(Trung bình| R)=1/3 P(Thấp| R) =2/3 Kinh t P(Cao| R) =0/3 P(Trung bình| R)=1/3 P(Thấp| R) =2/3 Gtinh P(Nam| R) =2/3 P(Nữ| R) =1/3 17 Bước 2: Phân lớp cho mẫu mới X <Nông thôn, th p, trung bình, nam> Vậy X1(lớp Đ) = 5/8*2/5*0/5*2/5*2/5 = 0 X2(lớp R) = 3/8*2/3*1/3*1/3*2/3 = 0.0123 CNB = max (X1(lớp Đ) ; X2(lớp R)) = X2(lớp R)  X thuộc l p R t nghĩa là với sinh viên sống Nông thôn , điểm vào thấp, kinh tế gia đình là Trung bình và giới tính là nam thì kết quả là R t. 18 M ts u điểm c a ph ng pháp Naive Bayes – Tính xác suất rõ ràng cho các giả định. – Kết hợp nhiều dự đoán của nhiều giả định. – Các thuộc tính trong tập mẫu học phải độc lập với điều kiện. – Độ chính xác thuật toán phân lớp phụ thuộc nhiều vào tập dữ liệu học ban đầu. 19 PHÂN TệCH H I QUY 20 Khái ni m phân tích h i qui Phân tích hồi quy là tìm mối quan hệ phụ thuộc của một biến, được gọi là biến phụ thuộc vào một hoặc nhiều biến khác. Ví d Khi chúng ta cố gắng giải thích tiêu dùng của mọi người, chúng ta có thể sử dụng biến giải thích là thu nhập và độ tuổi. 21 Mô hình h i quy đ n Phương trình hồi quy đơn biến (đường thẳng) có dạng tổng quát: Y=a+bX Trong đó: Y: là biến số phụ thuộc; X: là biến số độc lập; a: là tung độ gốc hay nút chặn; b: độ dốc hay hệ số góc. 22 Mô hình h i qui tuy n tính đa bi n Mô hình hồi qui tuyến tính nhiều chiều có dạng :      Y = α + � X1 + � X2 + … + �� Xk + U Y (biến phụ thuộc): chỉ tiêu phân tích α ( biến độc lập): hệ số chặn. β: hệ số ước lượng. Xi các yếu tố ảnh hưỏng đến năng suất.Với i chạy từ 1 đến k. U là sai số 23 D ĐOÁN K T QU H C T P D A VÀO Lụ THUY T PHÂN L P NAIVE BAYES 24  Bài toán Dựa vào thông tin dữ liệu đầu vào là: – Điểm trung bình của các học kỳ – Thông tin cá nhân: Nơi ở, giới tính, kinh tế gia đình… D đoán k t qu cu i cùng c a sinh viên s đ t đ quá trình đƠo t o. c trong 25 Xây d ng ch ng trình d đoán Phần 1: Thu thập thông tin cần thiết của sinh viên Phần 2: Thực hiện dự đoán kết quả học tập   Bước 1: – Kiểm tra thông tin đầu vào – Trùng bộ huấn luyện thì sẽ cho ra ngay kết quả dự đoán. Bước 2: – Dùng thuật toán phân lớp Naive Bayes để dự đoán. 26 Ch ng trình th c nghi m Trang 1: Trang chủ, thể hiện thông tin hình ảnh của trường 27 Trang 2: Dự đoán kết quả học tập 28 Trang 3: Nhập luật 29 K t qu th c nghi m – Dự đoán kết quả học tập cuối cùng của mình trong suốt quá trình học từ sẽ đó có lộ trình học tốt hơn. – Bộ huấn luyện mẫu còn ít do đó xác suất dự đoán kết quả cũng bị ảnh hưởng. H ng phát triển – Thử nghiệm chương trình và xây dựng bộ huấn luyện mẫu với dữ liệu đầu là điểm các môn học của học kì trước để dự đoán kết quả của học kì sau. 30 TƠi li u tham kh o [1] Hoàng Thị Lan Giao, Giang Hào Côn (2011) - Nghiên cứu ứng dụng thuật toán phân lớp vào bài toán dự đoán rủi ro tín dụng trong ngân hàng và các tổ chức tín dụng - Một số vấn đề chọn lọc của Công nghệ thông tin và truyền thông, Cần Thơ, 7-8 tháng 10 năm 2011. [2] Nguyễn Văn Huy (2009)- Thuật toán Bayes và ứng dụng Khóa luận tốt nghiệp đại học chính quy ngành CNTT. [3] Hệ hỗ trợ ra quyết định http://idoc.vn/tai-lieu/he-ho-tro-ra-quyet-dinh.html [4] Bài giảng Khai phá dữ liệu, trường đại học Hàng Hải (2011) http://www.ebook.edu.vn/?page=1.37&view=22169 [5] Tìm hiểu về luật kết hợp trong khai phá dữ liệu http://baigiang.violet.vn/present/same/entry_id/3541561 31 XIN CHÂN THÀNH C M N QUụ TH Y CỌ VÀ CÁC B N 32