BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƢỜNG ĐẠI HỌC VINH BÙI THỊ HẢO LUẬN VĂN THẠC SỸ TỐN HỌC XÍCH MARKOV TRONG PHẦN MỀM THỐNG KÊ R Chuyên ngành LÝ THUYẾT XÁC SUẤT VÀ THỐNG KÊ TOÁN HỌC NGHỆ AN – 2015 BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƢỜNG ĐẠI HỌC VINH LUẬN VĂN THẠC SỸ TỐN HỌC XÍCH MARKOV TRONG PHẦN MỀM THỐNG KÊ R Chuyên ngành: LÝ THUYẾT XÁC SUẤT VÀ THỐNG KÊ TOÁN HỌC Mã số: 60.46.01.06 Ngƣời hƣớng dẫn : TS NGUYỄN TRUNG HÒA Ngƣời thực hiên: BÙI THỊ HẢO NGHỆ AN – 2015 MỤC LỤC MỞ ĐẦU CHƢƠNG I : KIẾN THỨC CHUẨN BỊ 1.1 Xích Markov 1.1.1 Định nghĩa chung 1.1.2 Tính chất phân lớp trạng thái 1.1.3 Ví dụ minh họa 1.2 Giới thiệu R 1.2.1 Giới thiệu phần mềm R 1.2.2 Một số hƣớng dẫn mở đầu R 10 CHƢƠNG II XỬ LÍ XÍCH MARKOV TRONG R 21 2.1 Cấu trúc gói xích Markov 21 2.1.1 Tạo đối tƣợng xích Markov 21 2.1.2 Xử lí đối tƣợng xích Markov 23 2.2 Xác suất với đối tƣợng Markovchain 27 2.3 Phân tích thống kê 36 2.3.1 Mô 36 2.3.2 Ƣớc lƣợng 36 2.3.3 Dự báo 38 2.4 Ứng dụng vào mô hình dự báo thời tiết 39 2.4.1 Mơ hình Land of Oz 39 2.4.2 Mô hình Alofi Island Rainfall 40 KẾT LUẬN 42 TÀI LIỆU THAM KHẢO 43 MỞ ĐẦU Lí chọn đề tài Đầu kỉ XX, nhà Toán học tiếng ngƣời Nga A.A.Markov đƣa mơ hình Tốn học để mô tả chuyển động phần tử chất lỏng bình kín Sau mơ hình đƣợc phát triển mang tên “ Quá trình Markov” Nhiều mơ hình ngẫu nhiên Kinh tế, Kĩ thuật, Dân số học, Di truyền học đƣợc dựa sở q trình Markov Xích Markov trƣờng hợp riêng q trình Markov ta đánh số đƣợc trạng thái R ngôn ngữ lập trình mã nguồn mở cho phép giải khối lƣợng lớn tốn phân tích thống kê đồ thị Ngôn ngữ R đƣợc bổ sung phát triển từ ngơn ngữ lập trình S, đƣợc sáng tạo Ross Ihaka Robert Gentleman đại học Auckland, New Zealand vào năm 1995 Các toán thống kê phổ biến nhƣ hồi quy tuyến tính phi tuyến, kiểm định thống kê cổ điển, phân tích chuỗi thời gian,… thực R Nhận thấy hỗ trợ tuyệt vời phần mềm R việc khai thác ứng dụng xích Markov nên tơi chọn đề tài “XỬ LÝ XÍCH MARKOV TRONG R” nhằm mục đích khai thác sâu mối liên hệ chặt chẽ Toán học thực tiễn sống Mục đích nghiên cứu - Tìm hiểu xích Markov với thời gian rời rạc - Tìm hiểu phần mềm R - Tìm hiểu cách sử dụng R để tính tốn tốn liên quan đến xích Markov Phƣơng pháp nghiên cứu - Phân tích tổng hợp tài liệu - Trao đổi với giáo viên hƣớng dẫn - Thực hành R với ví dụ số Cấu trúc luận văn Luận văn bao gồm chƣơng: Chương I: Kiến thức chuẩn bị Nội dung chƣơng gồm hai phần chính: Phần đầu giới thiệu khái niệm xích Markov với thời gian rời rạc (viết tắt DTMC) với khái niệm liên quan (khơng gian trạng thái xích, bƣớc nhảy, xác suất chuyển, xích Markov theo thời gian) tính chất Phần sau giới thiệu phần mềm R với số hƣớng dẫn cách tải cài đặt với thao tác sử dụng R (khởi động, ngừng chạy, đặt tên đối tƣợng, cách định dạng R ) Chương II: Xử lí xích Markov phần mềm R Chƣơng giới thiệu cấu trúc gói xích Markov (cách tạo xử lí đối tƣợng xích Markov); cú pháp đƣợc sử dụng đối tƣợng xích Markov để thực phân tích xác suất; hàm cú pháp gói phù hợp để mơ dự đốn DTMC; đồng thời ứng dụng xích Markov việc dự đốn thời tiết dƣới hỗ trợ phần mềm R Luận văn hồn thành trƣờng Đại học Vinh Có đƣợc luận văn này, tác giả xin bày tỏ lòng biết ơn chân thành sâu sắc tới Tiến sĩ Nguyễn Trung Hồ trực tiếp hƣớng dẫn, dìu dắt giúp đỡ tác giả suốt trình triển khai, nghiên cứu hoàn thành đề tài Xin chân thành cảm ơn thầy giáo khoa Tốn – trƣờng Đại Học Vinh giảng dạy, truyền đạt kiến thức khoa học cho tác giả năm tháng qua Xin chân thành cảm ơn gia đình, BGH trƣờng THPT Tân Kỳ – Tân Kỳ Nghệ An bạn học viên lớp cao học 21 Toán chuyên nghành Lý thuyết Xác suất Thống kê Toán trƣờng Đại Học Vinh động viên giúp đỡ tác giả suốt q trình học tập hồn thiện luận văn CHƢƠNG I : KIẾN THỨC CHUẨN BỊ 1.1 Xích Markov 1.1.1 Định nghĩa chung Một xích Markov với thời gian rời rạc (discrete time Markov chain, viết tắt DTMC) dãy biến ngẫu nhiên X , X , , X n , đƣợc đặc trƣng tính Markov Tính Markov đƣợc hiểu phân phối trạng thái X n 1 phụ thuộc vào trạng thái X n mà không phụ thuộc vào trạng thái trƣớc X n1 , X n2 , , X (cịn đƣợc gọi tính trí nhớ) Nghĩa : P( X n1  xn1 | X  x1 , X  x2 , , X n  xn )  P( X n1  xn1 | X n  xn ) (1) Tập hợp trạng thái S  s1 , s2 , , sr ,  X n hữu hạn đếm đƣợc đƣợc gọi không gian trạng thái xích Sự thay đổi xích từ trạng thái sang trạng thái khác đƣợc gọi chuyển trạng thái bước nhảy Xác suất p ij thay đổi từ s i đến s j qua bƣớc nhảy đƣợc gọi xác suất chuyển pij  P( X  s j | X  si ) (2) Xác suất chuyển từ s i đến s j qua n bƣớc đƣợc kí hiệu pij(n ) pij( n)  P ( X n  s j | X  si ) (3) Một DTMC đƣợc gọi theo thời gian tính chất đƣợc phƣơng trình (4) dƣới đƣợc thỏa mãn: P( X n1  s j | X n  si )  P( X n  s j | X n1  si ) (4) Tính theo thời gian nói xác suất chuyển dọc theo thời gian không đổi Nếu xích Markov theo thời gian   p ij  P( X k 1  s j | X k  si )  (n)   pij  P( X n  k  s j | X k  si ) (5) với k Phân phối xác suất việc chuyển từ trạng thái sang trạng thái đƣợc biểu diễn ma trận chuyển P  ( pij ) i , j , phần tử vị trí (i, j ) biểu diễn xác suất chuyển p ij Ví dụ: Nếu r  ma trận chuyển P đƣợc thể bởi:  p11 P   p 21  p31 p12 p 22 p32 p13  p 23  p33  Phân phối trạng thái đƣợc viết dƣới dạng véc tơ hàng ngẫu nhiên x (có nghĩa x i  1, xi  ) Chẳng hạn, trạng thái thời i xích s x  (0 0) Từ ta có quan hệ x (1) x ( 0) x (1)  x (0) P suy viết x ( 2)  x (0) P x ( n)  x (0) P n (n ) (n  0) véc tơ x phân phối trạng thái xích đƣợc dự báo sau n bƣớc 1.1.2 Tính chất phân lớp trạng thái Một trạng thái s j đƣợc gọi kết xuất từ trạng thái s i (viết si  s j ) hệ thống đƣợc trạng thái s i có xác suất dƣơng để đạt đến (n) trạng thái s j thời điểm định, nghĩa tồn n  để pij  Nếu si  s j s j  si s i s j đƣợc gọi liên thông Một lớp liên thông đƣợc định nghĩa tập trạng thái liên thông với Một DTMC đƣợc tạo thành hay nhiều lớp liên thông DTMC đƣợc tạo lớp liên thông đƣợc gọi tối giản Một lớp liên thơng đƣợc gọi đóng khơng có trạng thái lớp tới đƣợc trạng thái ngồi lớp Nếu pii  si đƣợc gọi trạng thái hấp thụ (absorbing) Một trạng thái hấp thụ tƣơng ứng với lớp liên thơng đóng đƣợc tạo nên Dạng tắc ma trận chuyển DTMC ma trận khối, lớp liên thơng đóng đƣợc thể nơi bắt đầu ma trận chéo Trạng thái s i đƣợc gọi có chu kì k i lặp lại trạng thái s i phải trải qua bội k i bƣớc Điều có nghĩa ki  UCLN{n : P( X n  si | X  si )  0} Nếu ki  trạng thái s i đƣợc gọi khơng tuần hồn Ngƣợc lại k i  trạng thái s i tuần hồn với chu kỳ k i Nói cách khác, s i đƣợc gọi tuần hồn gặp lại sau số k i  cố định (các) bƣớc (hoặc bội k i ), ngƣợc lại khơng tuần hồn s j thuộc lớp liên thơng chúng có chu kì k i Từ đó, trạng thái DTMC tối giản có tính tuần hồn Tính tuần hồn đƣợc coi tính tuần hồn DTMC Có thể để phân tích thời điểm đạt đến trạng thái định Lần qua từ trạng thái si tới thạng thái s j số Tij bƣớc đƣợc lấy xích lần đạt đến trạng thái sj, với giả thiết Nếu trạng thái s i X  si Phân phối xác suất Tij đƣợc xác định phƣơng trình (6) hij( n)  PTij  n  PX n  s j , X n1  s j , , X  s j | X  si  (6) thấy đƣợc tính đệ quy cách dùng phƣơng trình (7) cho hij( n )  pij : hij( n )   p kS  s j ik hkj( n1) (7) Nếu định nghĩa lần qua ta đặt si  s j , ta thu đƣợc lần quay lại Ti  inf n  : X n  si | X  si  Một trạng thái s i đƣợc gọi hồi quy chắn đƣợc thấy thời điểm sau xuất phát trạng thái s i , có nghĩa PTi   | X  si   Ngƣợc lại s i đƣợc gọi tạm thời có xác suất dƣơng cho xích chẳng quay lại s i , nghĩa PTi   | X  si   Cho xích Markov theo thời gian với ma trận chuyển P , phân phối dừng z véc tơ hàng ngẫu nhiên mà z = z.P với  z j  i z j  Nếu DTMC X n  tối giản tuần hồn có j phân phối giới hạn phân phối phân phối dừng Từ đó, P ma trận chuyển xích cỡ k  k z  ( z1 , z , , z k ) véc tơ riêng P cho k z i 1 i  ta có lim P n  Z n Z ma trận có tất hàng z Phân phối dừng X n  đƣợc biểu diễn z 1.1.3 Ví dụ minh họa Ta xem xét ví dụ số sau Giả sử có DTMC với khơng gian trạng thái tập hợp trạng thái S  s1 ; s ; s3 , với ma trận chuyển  0.5 0.2 0.3 P  0.15 0.45 0.4 0.25 0.35 0.4 Trong P, p11  0.5 xác suất để X nhận trạng thái s1 với điều kiện X trạng thái s1 , tƣơng tự cho giá trị khác Từ dễ dàng thấy xích tối giản từ trạng thái thơng tin (nó đƣợc tạo thành lớp thông tin) Giả sử trạng thái thời chuỗi X  s , nghĩa x ( 0)  0 0 xác suất chuyển trạng thái sau bƣớc tính nhƣ sau: x (1)  0.5 0.2 0.3  0 00.15 0.45 0.4  0.15 0.45 0.4 0.25 0.35 0.4  0.5 0.2 0.3 x ( n )  x ( n 1) P  x ( 2)  x (1) P  0.15 0.45 0.40.15 0.45 0.4 0.25 0.35 0.4  0.2425 0.3725 0.385 Chẳng hạn ta muốn tìm xác suất trạng thái s3 sau bƣớc P( X  s3 | X  s2 )  0.385 1.2 Giới thiệu R 1.2.1 Giới thiệu phần mềm R R ngôn ngữ lập trình mã nguồn mở mơi trƣờng phần mềm cho tính tốn thống kê đồ thị Ngơn ngữ R đƣợc bổ sung phát triển từ ngôn ngữ lập trình S, đƣợc sáng tạo Ross Ihaka Robert Gentleman đại học Auckland, New Zealand vào năm 1995 sau đƣợc phát triển nhóm phát triển R R chạy đƣợc nhiều hệ điều hành : Windows, Linux, Macos,… Các trạng thái hấp thụ đƣợc định nghĩa cách thức absorbingStates Hàm khóa đƣợc sử dụng Feres (2007) (và hàm xích Markov) commclassKernel, đƣợc gọi nhƣ dƣới đây: Hàm commclassrKernel trả đƣợc ma trận chuyển cấp n trả danh sách gồm hai mục: C, ma trận kề hiển thị với trạng thái s j (ở hàng) trạng thái nằm lớp liên thông s j (đánh dấu 1) v, véc tơ nhị phân thể trạng thái s j trạng thái tạm thời (0) trạng thái ì (1) Các hàm đƣợc sử dụng hàm nội khác mà cách thức summary cho đối tƣợng markovchain làm việc Ví dụ, ma trận đƣợc sử dụng Feres (2007) đƣợc sử dụng làm điển hình cho mục đích hàm Tất trạng thái có liên quan đến lớp tạm thời đƣợc đặt tên “transient” cách thức cụ thể đƣợc viết để xuất trạng thái Các bảng liệt kê từ Feres (2007) đƣợc chuyển thể thành cách thức canonicForm mà biến xích Markov thành dạng tắc Hàm is.accessible cho phép tìm hiểu xem liệu trạng thái s j truy cập đƣợc từ trạng thái s i hay không, nghĩa liệu xác suất để đƣợc từ s i đến s j có lớn không Hàm trả giá trị logic True False Trong Mục 1.1.2 thấy rằng, DTMC tối giản tất trạng thái có chu kỳ Hàm period trả chu kỳ DTMC, với điều kiện tối giản Ví dụ sau để tìm chu kỳ DTMC tối giản không tối giản phƣơng tiện hàm is.irreducible đó, cách thức period đƣợc sử dụng để tính chu kỳ xích Ví dụ xích Markov đƣợc tìm thấy trang web Mathematica (Wolfram Research 2013) đƣợc sử dụng đƣợc vẽ hình Hình Vẽ xích Markov Xích Markov MathematicaMC đƣợc tạo bởi:  Các lớp đóng : o c d o e  Lớp tạm thời : o a b  Xích Markov khơng tối giản  Trạng thái đáng ý : e Feres (2007) cung cấp đoạn mã để tính thời điểm đến (trong vòng 1, 2, ,n bƣớc) cho trạng thái ban đầu i Danh sách lệnh MATLAB chuyển vào R mà hàm firstPassage dựa đƣợc sử dụng nhƣ dƣới trả xác suất để trạng thái i quay lại lần gần sau n thời điểm, biết trạng thái ban đầu “nắng” Từ kết nhận đƣợc, ta kết luận với xác suất 0.121 để có ngày mƣa quay lại sau ngày, với trạng thái ban đầu nắng 2.3 Phân tích thống kê Bảng liệt kê hàm cách thức đƣợc thực gói giúp nhận diện, mơ dự báo DTMC Mục đích Hàm Hàm trả chuỗi Markov phù hợp với dãy cho markovchainFit Cách thức để tìm dự báo từ markovchain markovchainList Hàm để lấy mẫu từ đối tƣợng markovchain markovchain List predict rmarkovchain Bảng 5: Các hàm thống kê Markovchain 2.3.1 Mô Mô dãy ngẫu nhiên từ DTMC dễ dàng nhờ hàm rmarkovchain Đoạn mã sau tạo năm trạng thái thời tiết theo mcWeather dƣới trình ngẫu nhiên 2.3.2 Ƣớc lƣợng Một xích Markov theo thời gian đƣợc tạo nên từ liệu cho Sau trình bày hai cách thức đƣợc thực phiên gói markovchain: ƣớc lƣợng hợp lý cực đại, ƣớc lƣợng hợp lý cực đại với việc làm trơn Laplace Phƣơng trình (8) dƣới ƣớc lƣợng hợp lý cực đại (MLE) phần tử p ij , nij số lần dãy chuyển từ trạng thái  X t  si  sang trạng thái X t 1  s j , mẫu số tổng số lần dãy chuyển từ trạng thái X t 1  s j  sang trạng thái  X t 1  su  với u: pˆ ijMLE  nij k  niu (8) u 1 Phƣơng pháp làm trơn Laplace dạng ƣớc lƣợng hợp lý cực đại (MLE), n ij đƣợc thay n ij   (xem phƣơng trình (9)) với  tham số ổn định dƣơng tùy ý pˆ ijLS  nij   k  niu    u 1 (9) Cả hai MLE tiếp cận Laplace đƣợc dựa hàm createSequenceMatrix chuyển dãy liệu (kí tự ) vào bảng, cho thấy ( X t  i, X t 1  j ) phân bố mẫu, nhƣ mã dƣới đây: Một vấn đề xảy mẫu chứa thể trạng thái (chẳng hạn X  ) mà mẫu nằm cuối chuỗi liệu, mang đến hàng tồn số (khơng có mẫu để ƣớc lƣợng phân phối có điều kiện dịch chuyển) Trong trƣờng hợp ma trận chuyển đƣợc ƣớc lƣợng p  , j  / k với k trạng thái 2.3.3 Dự báo Các dự báo n bƣớc thu đƣợc cách sử dụng cách thức predict đƣợc viết cách rõ ràng cho đối tƣợng markovchain Dự báo mode phân phối có điều kiện X t 1 từ X t  s j , s j thể cuối DTMC (thuần không nhất) Dự đoán thời tiết ngày từ đối tƣợng markovchain đƣợc thực nhƣ sau, giả định thời tiết ngày cuối “sunny” ( nắng) 2.4 Ứng dụng vào mơ hình dự báo thời tiết Mục ứng dụng DTMC lĩnh vực dự báo thời tiết Xích Markov cung cấp mơ hình đơn giản để dự báo thời tiết ngày cho điều kiện khí tƣợng Ứng dụng đƣợc biết đến với tên gọi “Land of Oz example” J.G.Kemeny, J.L.Snell G.L.Thompson (1974), “Alofi Island Rainfall” P.J.Avery D.A.Henderson (1999) 2.4.1 Mơ hình Land of Oz Land of Oz thừa nhận khơng có điều kiện thời tiết lí tƣởng cho tất cả: thời tiết tuyết mƣa thƣờng xun, khơng có hai ngày đẹp hàng Hãy xem xét ba trạng thái thời tiết : mƣa, đẹp tuyết Giả sử ma trận chuyển nhƣ sau: Nếu ngày hôm ngày đẹp trời, véc tơ hàng ngẫu nhiên tƣơng ứng 0  (0, 1, 0) dự báo sau 1, ngày đƣợc cho bởi: Nhƣ thấy từ 1 , Land of Oz hôm ngày đẹp trời, ngày mai mƣa tuyết với xác suất Một tuần sau đó, dự báo đƣợc tính nhƣ sau: Các trạng thái ổn định xích đƣợc tính cách thức steadyStates Lƣu ý rằng, từ ngày thứ bảy trở đi, xác suất đƣợc dự báo trạng thái ổn định xích chúng khơng phụ thuộc vào điểm khởi đầu, nhƣ đoạn mã sau: 2.4.2 Mơ hình Alofi Island Rainfall Dữ liệu lƣợng mƣa hàng ngày Alofi Island đƣợc ghi nhận năm từ ngày tháng năm 1987 đến ngày 31 tháng 12 năm 1989 đƣợc phân lớp thành ba trạng thái : “0” (khơng có mƣa), “1-5” (từ khác đến mm) “6+” (hơn 5mm) Các số liệu tƣơng ứng đƣợc cung cấp gói Markovchain Ma trận chuyển đƣợc ƣớc lƣợng nhƣ sau: Phân phối lƣợng mƣa dài hạn thu đƣợc cách thức steadyStates KẾT LUẬN Luận văn tập trung nghiên cứu xích Markov với thời gian rời rạc, cách sử dụng R để tính tốn tốn liên quan đến xích Markov đạt đƣợc kết nhƣ sau: * Cài đặt sử dụng phần mềm R ví dụ số * Cài thêm gói phần mềm R để phục vụ cho việc xử lí xích Markov * Tạo đối tƣợng xích Markov xử lí đối tƣợng phần mềm R * Sử dụng phần mềm R để thực phân tích xác suất đối tƣợng xích Markov * Nêu đƣợc ứng dụng xích Markov việc dự báo thời tiết nhờ sử dụng phần mềm R Mặc dù cố gắng nỗ lực nghiêm túc việc nghiên cứu học hỏi, song hạn chế mặt thời gian chuyên môn nên kết đạt đƣợc hạn chế Rất mong đƣợc góp ý, bổ sung thầy, để luận văn đƣợc hoàn thiện TÀI LIỆU THAM KHẢO [1] Bùi Quang Hà, Nguyễn Trung Kiên, Tìm hiểu R, Đại học sƣ phạm Hà Nội, 1-28 [2] Nguyễn Văn Tuấn, Phân tích số liệu biểu đồ R, Garvan Institute of Medical Research Sydney, Australia, – 41 [3] Feres R (2007) Notes for Math 450 MATLAB Listings for Markov Chains URL http://www.math.wustl.edu/~feres/Math450Lect04.pdf [4] Giorgio Alfredo Spedicato, Easy Handling Discrete Time Markov Chains, February 21, 2015, 2-24 [5] Giorgio Alfredo Spedicato, Mirko Signorelli, The markovchain Package: A Package for Easily Handling Discrete Markov Chains in R, http://cran.r-project.org/web/packages/markovchain/vignettes/an _introduction_to_markovchain_package.pdf, 37 [6] Montgomery J (2009) Communication Classes URL http://www.ssc wisc.edu/~jmontgom/commclasses.pdf ... R để phục vụ cho việc xử lí xích Markov * Tạo đối tƣợng xích Markov xử lí đối tƣợng phần mềm R * Sử dụng phần mềm R để thực phân tích xác suất đối tƣợng xích Markov * Nêu đƣợc ứng dụng xích Markov. .. Spedicato, Mirko Signorelli, The markovchain Package: A Package for Easily Handling Discrete Markov Chains in R, http://cran .r- project.org/web/packages/markovchain/vignettes/an _introduction_to_markovchain_package.pdf,... dòng lệnh R, vào Packages Load package chọn đến gói cần dùng CHƢƠNG II XỬ LÍ XÍCH MARKOV TRONG R 2.1 Cấu trúc gói xích Markov 2.1.1 Tạo đối tƣợng xích Markov Gói Markov chain đƣợc tải R dịng lệnh