Khóa luận Ứng dụng mô hình học máy tiên tiến nhằm tăng cường khả năng dự báo xu thế của thị trường chứng khoán

1 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Đinh Thị Thùy Trang ỨNG DỤNG MÔ HÌNH HỌC MÁY TIÊN TIẾN NHẰM TĂNG CƯỜNG KHẢ NĂNG DỰ BÁO XU THẾ CỦA THỊ TRƯỜNG CHỨNG KHOÁN KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY Ngành: Công nghệ thông tin HÀ NỘI - 2010 2 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Đinh Thị Thùy Trang ỨNG DỤNG MÔ HÌNH HỌC MÁY TIÊN TIẾN NHẰM TĂNG CƯỜNG KHẢ NĂNG DỰ BÁO XU THẾ CỦA THỊ TRƯỜNG CHỨNG KHOÁN KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY Ngành: Công nghệ thông tin Cán bộ hướng dẫn: TS. Nguyễn Hà Nam HÀ NỘI-2010 i LỜI CẢM ƠN “Để hoàn thành khóa luận này, tôi xin gửi lời cảm ơn tới các thầy, cô giáo trong trường Đại học Công nghệ - Đại học Quốc gia Hà Nội. Các thầy cô đã dạy bảo, chỉ dẫn và luôn tạo điều kiện tốt nhất cho tôi học tập trong suốt quá trình học đại học đặc biệt là trong thời gian làm khóa luận tốt nghiệp Tôi xin bày tỏ lòng biết ơn sâu sắc tới thầy giáo TS. Nguyễn Hà Nam, thầy đã tận tình hướng dẫn tôi trong năm học vừa qua. Tôi cũng thầm biết ơn những người bạn của mình, các bạn đã luôn ở bên tôi, giúp đỡ và cho tôi những ý kiến đóng góp quý báu trong học tập cũng như trong cuộc sống. Cuối cùng, tôi xin gửi tới bố mẹ và toàn thể gia đình lòng biết ơn và tình cảm yêu thương nhất. Con xin dành tặng bố mẹ kết quả mà con đã đạt được trong suốt bốn năm học đại học. Con cảm ơn bố mẹ nhiều và cả các em nữa.” Hà nội, ngày 20/05/2010 ii Tóm tắt khóa luận Ngày nay, cách thức kiếm tiền và sử dụng đồng tiền của các nhà đầu tư cũng có nhiều thay đổi. Hầu hết mọi người đều đầu tư vào chứng khoán, họ cho rằng đó là một cách đầu tư thông minh và những đồng tiền ấy là đồng tiền thông minh. Nhưng thị trường chứng khoán luôn có những yếu tố bất ngờ không theo ý muốn chủ quan của ai, có lúc tăng nhanh sau đó giảm một cách đột ngột, có lúc thì liên tục tăng mà chưa có dấu hiệu giảm xuống.…Do vậy dự đoán được xu thế của thị trường chứng khoán là một vấn đề quan trọng đầu tư tài chính. Thị trường sẽ diễn biến ra sao, đầu tư vào chứng khoán ở thời điểm này có được hay không, phụ thuộc rất nhiều vào kết quả dự đoán của chúng ta chính xác ra sao Trong khóa luận này, tôi xin giới thiệu một kỹ thuật được sử dụng nhiều trong khai phá dữ liệu, có hiệu quả cao trong dự đoán, xây dựng mô hình dự báo đơn giản, nhanh chóng và dễ hiểu. Đó là mô hình cây quyết định, khóa luận đã tìm hiểu cấu trúc, hoạt động của cây quyết định, các độ đo dùng để chia cắt các thuộc tính và các thuật toán đặc biệt là thuật toán C4.5 mà khóa luận sử dụng để xây dựng cây. Từ đó, thiết kế mô hình cây quyết định cho dữ liệu thời gian thực (time series) áp dụng trong dự báo xu thế của thị trường chứng khoán được trình bày chi tiết. Khóa luận đã thực nghiệm trên dữ liệu VnIndex và đã thu được những kết quả bước đầu Từ khóa: data mining, decision tree, time series, stock trend prediction, weka…. iii MỤC LỤC LỜI CẢM ƠN.................................................................................................................i TÓM TẮT KHÓA LUẬN .............................................................................................ii  MỤC LỤC ................................................................................................................... iii  DANH MỤC HÌNH VẼ ...............................................................................................vi  DANH MỤC BẢNG BIỂU .........................................................................................vii  Chương 1. Giới thiệu các kiến thức cơ!Äở......................................................................1  1.1.  Khai phá dự liệu ...........................................................................................1  1.1.1. Khai phá dữ liệu là gì ..............................................................................1  1.1.2.  Quá trình khai phá dữ liệu ........................................................................1  1.1.3.  Các phương pháp khai phá dữ liệu...........................................................2  1.1.4.  Sự cần thiết phải có khai phá dữ liệu .......................................................2  1.1.5.  Một số khó khăn gặp phải khi xây dựng quá trình khai phá dữ liệu........3  1.1.6.  Các lĩnh vực ứng dụng .............................................................................4  1.2.  Phân lớp và dự báo .......................................................................................4  1.2.1.  Định nghĩa ................................................................................................4  1.2.2.  Các bước để phân lớp và dự báo ..............................................................5  1.2.3.  Độ chính xác trong phân lớp và dự báo ...................................................8  1.2.4.  Một số bài toán phân lớp và dự báo điển hình .........................................8  1.3.  Bài toán dự báo xu thế thị trường chứng khoán ...........................................9  1.4.  Nội dung và cấu trúc của khóa luận ...........................................................10  Chương 2. Tổng quan về cây quyết định .....................................................................12  iv 2.1.  Định nghĩa ..................................................................................................12  2.2.  Cấu trúc ......................................................................................................12  2.3.  Các kiểu cây quyết định .............................................................................13  2.4.  Các độ đo sử dụng để xác định điểm chia tốt nhất.....................................13  2.4.1.  Độ lợi thông tin (Information Gain).......................................................14  2.4.2.  Độ đo tỷ lệ Gain (Gain ratio)..................................................................15  2.4.3.  Chỉ số Gini (Gini index) .........................................................................15  2.5.  Cắt tỉa cây (thu gọn cây).............................................................................17  2.6.  Rút ra quy tắc phân lớp từ cây quyết định..................................................18  2.7.  Các thuật toán trong cây quyết định...........................................................19  2.8.  Quá trình tạo cây quyết định ......................................................................21  2.8.1.  Khả năng học và tổng quát hóa ..............................................................21  2.8.2.  Các phương pháp huấn luyện cây ..........................................................21  2.9.  Giải thuật C4.5............................................................................................22  Tổng kết ...................................................................................................................25  Chương 3.Mô hình cây quyết định trong dự báo xu thế của thị trường chứng khoán.27  3.1.  Giới thiệu chung về dữ liệu thời gian thực.................................................27  3.1.1.  Các thành phần của dữ liệu thời gian thực .............................................27  3.1.2.  Các phương pháp làm trơn .....................................................................29  3.2.  Dữ liệu chứng khoán ..................................................................................30  3.3.  Mô hình dự báo tài chính............................................................................32  3.4.  Thiết kế cây quyết định cho dữ liệu thời gian thực ....................................33  3.4.1.  Tập hợp dữ liệu.......................................................................................33  3.4.2.  Tiền xử lý dữ liệu ...................................................................................34  3.4.3.  Phân hoạch dữ liệu .................................................................................34  v 3.4.4.  Mô hình hóa cây quyết định ...................................................................36  3.4.5.  Tiêu chuẩn đánh giá................................................................................37  3.4.6.  Triển khai................................................................................................40  Tổng kết ...................................................................................................................40  Chương 4. Thực nghiệm ..............................................................................................41  4.1.  Môi trường thực nghiệm.............................................................................41  4.2.  Xây dựng cơ sở dữ liệu...............................................................................42  4.2.1.  Dữ liệu chứng khoán ..............................................................................42  4.2.2.  Xây dựng dữ liệu cho mô hình ...............................................................42  4.3.  Thực nghiệm mô hình cây quyết định cho dữ liệu thời gian thực .............47  4.3.2.  Đánh giá mô hình ...................................................................................50  4.3.3.  Lựa chọn mô hình tốt nhất......................................................................51  4.4.  Một số mô hình khác ..................................................................................55  4.4.1.  Mô hình mạng nơ ron .............................................................................56  4.4.2.  Mô hình SVM (support vector machine) ...............................................59  Kết luận....................................................................................................................62  Kết quả đạt được của luận văn.............................................................................62  Hướng nghiên cứu tiếp theo.................................................................................62  PHỤ LỤC-MỘT SỐ THUẬT NGỮ ANH –VIỆT......................................................63  TÀI LIỆU THAM KHẢO ...........................................................................................64  vi DANH MỤC HÌNH VẼ Hình 1-0: Bước 1 Học để xây dựng mô hình phân lớp.................................................5  Hình 1-1: Bước 2 Kiểm tra và đánh giá.........................................................................6  Hình 1-2: Ví dụ về học mô hình ....................................................................................7  Hình 1-3 : Ví dụ về phân lớp dữ liệu .............................................................................7  Hình 2-0: Biểu diễn cấu trúc cây quyết định ...............................................................12  Hình 2-1: Một cây quyết định miêu tả khái niệm “mua máy tính” .............................18  Hình 3-0: Thành phần xu hướng dài hạn .....................................................................28  Hình 3-1: Thành phần mùa ..........................................................................................28  Hình 3-2: Thành phần chu kỳ ......................................................................................29  Hình 3-3: Mô hình cây quyết định dự báo chứng khoán ............................................32  Hình 3-5: Tỷ lệ kích thước của tập huấn luyện và tập kiểm chứng.............................35  Hình 4-0: Giao diện chính của weka ...........................................................................42  Hình 4-1: Dữ liệu chứng khoán thu được từ sàn chứng khoán....................................43  Hình 4-2: (a) Một trong số những dữ liệu huấn luyện từ 1/2008-12/2008..................45  (b) Một trong số những bộ kiểm chứng từ 1/2009-3/2009 ..........................45  Hình 4-3: Một trong những file dữ liệu đầu ra của chương trình ................................45  Hình 4-4: Lệnh đọc file CSV và chuyển thành file ARFF ..........................................46  Hình 4-5: Dữ liệu dưới định dạng arff trong weka......................................................47  Hình 4-6: Lệnh huấn luyện dữ liệu..............................................................................49  Hình 4-8: Lệnh đánh giá dựa trên tập kiểm chứng ......................................................50  Hình 4-12: (a) Cấu trúc một nơ ron .............................................................................57  (b) Cấu trúc mạng nơ ron...........................................................................57  vii DANH MỤC BẢNG BIỂU Hình 2-2: Kết quả của cuộc khảo sát..................................................................................21  Hình 3-4: Tổ chức dữ liệu của mô hình..............................................................................34  Hinh 3-6: Bảng ma trận 2 x 2 .............................................................................................39  Hình 4-7: Kết quả qua các lần huấn luyện .........................................................................49  Hình 4-9: Kết quả đánh giá trên tập kiểm chứng ...............................................................51  Hình 4-10: Kết quả khi thay đổi các tham số -C, -M .........................................................54  Hình 4-11: Kết quả khi huấn luyện lại mô hình với tham số tốt nhất ................................55  Hình 4-13: So sánh kết quả giữa Mạng nơ ron và cây quyết định .....................................59  Hình 4-14: So sánh kết quả giữa mô hình Support vector machine và cây quyết định .....60  1 Chương 1. Giới thiệu các kiến thức cơ sở 1.1. Khai phá dự liệu 1.1.1 . Khai phá dữ liệu là gì Khai phá dữ liệu là việc khám phá tri thức trong các cơ sở dữ liệu, là một quá trình trích xuất những thông tin ẩn, trước đây chưa biết và có khả năng hữu ích, dưới dạng các quy luật, ràng buộc, quy tắc trong cơ sở dữ liệu [1]. 1.1.2. Quá trình khai phá dữ liệu Một quá trình KPDL bao gồm năm giai đoạn chính 1) Tìm hiểu nghiệp vụ và dữ liệu : nghiên cứu kiến thức về lĩnh vực sẽ áp dụng, bao gồm cả cấu trúc về hệ thống và tri thức, các nguồn tài liệu hiện hữu, ý nghĩa, vai trò và tầm quan trọng của các thực thể dữ liệu 2) Chuẩn bị dữ liệu: sử dụng các kỹ thuật tiền xử lý để biến đổi và cải thiện chất lượng dữ liệu để thích hợp với những yêu cầu của các giải thuật học. Bước này thường chiếm phần lớn thời gian của toàn bộ quá trình khai phá dữ liệu 3) Mô hình hóa dữ liệu: lựa chọn kỹ thuật phù hợp để giải quyết các vấn đề đặt ra. Các bài toán được phân loại vào một trong những nhóm bài toán chính trong khai phá dữ liệu dựa trên đặc tả của chúng. 4) Hậu xử lý và đánh giá mô hình: các kết quả được biến đổi từ dạng học thuật sang dạng phù hợp với nghiệp vụ và dễ hiểu hơn cho người dùng. Kinh nghiệm cho thấy, các mẫu và các mô hình tìm thấy không phải lúc nào cũng đáng quan tâm và có thể trực tiếp sử dụng được ngay. Vì vậy, quá trình khai phá dữ liệu cần thiết lặp đi lặp lại với việc đánh giá tri thức đã thu được. 5) Triển khai tri thức: các mô hình được đưa vào hệ thống thông tin thực tế dưới dạng các modun hỗ trợ việc đưa ra quyết định. Trong một số trường hợp, người ta có thể sử dụng tri thức phát hiện được mà không cần phải đưa vào một hệ thống máy tính. Mặc khác, người sử dụng lại mong muốn tri thức đã tìm được có thể được đưa vào máy tính và được khai thác bằng một số chương trình. Đưa các kết quả đã thu được vào sử dụng trong thực tế là mục tiêu cuối cùng của một quá trình khai phá dữ liệu 2 Mối quan hệ chặt chẽ giữa các giai đoạn trong quá trình khai phá dữ liệu là rất quan trọng cho việc nghiên cứu trong khai phá dữ liệu. Quá trình này có thể được lặp lại nhiều lần một hay nhiều giai đoạn dựa trên phản hồi từ kết quả của các giai đoạn sau. Tham gia chính trong quá trình KPDL là các nhà tư vấn và phát triển chuyên nghiệp trong lĩnh vực KPDL 1.1.3. Các phương pháp khai phá dữ liệu 1) Phân lớp (classification) : với một tập các dữ liệu huấn luyện cho trước và sự huấn luyện của con người, các giải thuật phân loại sẽ lọc ra bộ phân loại dùng để phân dữ liệu mới vào trong những lớp đã được định trước. Một số phương pháp điển hình là cây quyết định, mạng nơ ron…. 2) Hồi qui (Regression) : là học một hàm ánh xạ dữ liệu nhằm tìm và xác định giá trị thực của một biến 3) Phân cụm (Clustering): thực hiện việc nhóm dữ liệu thành các lớp mới để có thể phát hiện các mẫu phân bố. 4) Tổng hợp (Summarization): Tìm ra các đặc trưng và tính chất của các khái niệm. Ví dụ như tổng quát hóa, tóm tắt, các đặc trưng dữ liệu ràng buộc 5) Mô hình ràng buộc (Dependency modeling): tìm ra một mô hình mô tả sự phụ thuộc có ý nghĩa giữa các biến. Mô hình ràng buộc gồm hai mức: mức cấu trúc của mô hình mô tả và mức định lượng 6) Dò tìm biến đổi và độ lệch (change and deviation dectection) : phát hiện sự thay đổi có ý nghĩa dưới dạng độ đo đã biết trước hoặc giá trị chuẩn 1.1.4. Sự cần thiết phải có khai phá dữ liệu Có rất nhiều lý do khiến chúng ta cần phải có khai phá dữ liệu, một số lý do tiêu biểu đó là: - Nhiều tổ chức, trong một thời gian dài đã thu thập được một lượng lớn dữ liệu, họ phải làm gì với những dữ liệu này? - Người ta thu thập và lưu trữ dữ liệu vì nghĩ rằng có thể thu được những thông tin có giá trị từ những dữ liệu này 3 - Trong kinh doanh, thu giữ các dữ liệu về thị trường, đối thủ cạnh tranh và về khách hàng. Trong các ngành sản xuất, thu giữ các dữ liệu về hiệu suất, tối ưu hóa các cơ hội, cũng như nguyên tắc cải tiến các quy trình và các rắc rối gặp phải - Chỉ có một lượng nhỏ dữ liệu đã thu thập được phân tích - Với ý nghĩ tiếp tục phân thu thập dữ liệu để không bỏ qua điều gì đó quan trọng, mà dữ liệu này lại không được phân tích gây ra tốn kém - Các phương pháp phân tích dữ liệu cổ điển tỏ ra không còn mấy phù hợp khi lượng dữ liệu lên - Nhiều khi người phân tích dữ liệu không phải là những chuyên gia về dữ liệu, đó đó cần phải có công cụ để họ thực hiện công việc phân tích dữ liệu - Trong môi trường cạnh tranh việc phát hiện ngay những dấu hiệu bất thường và nhanh chóng đưa ra quyết định phù hợp là điều hết sức quan trọn 1.1.5. Một số khó khăn gặp phải khi xây dựng quá trình khai phá dữ liệu Trong quá trình khai phá dữ liệu chúng ta luôn gặp phải những trở ngại, chúng ta phải tìm cách khắc phục và vượt qua những trở ngại này để thu được kết quả mong muốn. Một trong những khó khăn cơ bản đó là: - Kích thước lớn: Không chỉ có nhiều bản ghi trong cơ sở dữ liệu mà trong các bảng cũng có rất nhiều thuộc tính, vì thế kích thước của vấn đề lớn. Một tập dữ liệu có kích thước lớn làm tăng không gian tìm kiếm theo cách bùng nổ tổ hợp. Hơn nữa, sẽ làm tăng khả năng làm cho thuật toán khai phá dữ liệu tìm ra những mẫu sai, không có giá trị khái quát. Để giải quyết vấn đề, người ta sử dụng phương pháp làm giảm kích thước ảnh hưởng đến vấn đề và sử dụng tri thức ưu tiên (có trước) để nhận ra và loại bỏ những trường không liên qua - Hiện tượng quá khớp: Khi thuật toán tìm kiếm tham số tốt nhất cho một mô hình cụ thể sử dụng một tập dữ liệu học hạn chế, có thể xảy ra hiện tượng dữ liệu quá khớp, làm cho mô hình kém hiệu quả trên tập dữ liệu thử. Giải quyết vấn đề này sử dụng phương pháp kiểm tra chéo, thực hiện theo đúng các nguyên tắc và chiến lược thống kê phức tạp khác - Tri thức và dữ liệu thay đổi: Dữ liệu thay đổi nhanh chóng có thể làm cho các mô hình tìm thấy trước đây không còn giá trị. Hơn nữa, các trường đã được chọn trong 4 một ứng dụng cơ sở dữ liệu cụ thể có thể bị thay đổi, bị xóa, hay được thêm vào. Giải pháp có thể sử dụng là tăng cường phương thức cho việc cập nhật các mô hình và xem sự thay đổi như là một cơ hội cho việc khám phá bằng cách sử dụng chúng một cách thích hợp để chỉ tìm phải kiếm lại cho các mô hình bị thay đổi. - Dữ liệu bị nhiễu và bị mất. Vấn đề này đặc biệt hay xảy ra trong các cơ sở dữ liệu thương mại, dữ liệu của các thuộc tính quan trọng có thể bị mất nếu cơ sở dữ liệu không được thiết kết để dành cho mục đích khai phá. Để giải quyết vấn đề này chúng ta phải tăng cường sử dụng những chiến lược thống kê phức tạp để phát hiện ra những trường hợp thông tin ẩn và sự phụ thuộc giữa chúng - Tính hiểu được của các mô hình: Trong rất nhiều ứng dụng, việc tìm ra được điều gì dễ hiểu hơn đối với con người là rất quan trọng. Có thể biểu diễn bằng đồ thị, ngôn ngữ tự nhiên, và các kỹ thuật cho việc trực quan hóa dữ liệu - ….. 1.1.6. Các lĩnh vực ứng dụng Theo J.Han và M.Kamber, ứng dụng của khai phá dữ liệu được chia thành hai lớp chính bao gồm lớp các ứng dụng phân tích dữ liệu - hỗ trợ quyết định và lớp các lĩnh vực ứng dụng khác Lớp các ứng dụng trong phân tích dữ liệu và hỗ trợ quyết định bao gồm các ứng dụng trong phân tích và quản lý thị trường, phân tích và quản lý rủi ro, khám phá ngoại lai và các mẫu không hữu ích. Dữ liệu trong các ứng dụng này là khá phong phú có được từ các giao dịch thẻ tín dụng, nghiên cứu đời sống cộng đồng… Lớp các lĩnh vực ứng dụng điển hình khác bao gồm khai phá Text, khai phá web, khai phá dữ liệu dòng, khai phá dữ liệu sinh học… Sự phát triển nhanh chóng của khai phá dữ liệu làm cho miền ứng dụng lĩnh vực ngày càng thêm phong phú và đa dạng 1.2. Phân lớp và dự báo 1.2.1. Định nghĩa Phân lớp và dự báo là hai hình thức phân tích dữ liệu được sử dụng để rút ra những 5 mô hình miêu tả lớp dữ liệu quan trọng hoặc dự báo xu thế dữ liệu trong tương lai. Trong khi phân lớp dự đoán các nhãn lớp đã được xác định rõ ràng thì mô hình dự báo thực hiện chức năng trên những giá trị liên tục. Lấy ví dụ, một mô hình phân lớp được xây dựng để phân loại ứng dụng cho vay ngân hàng là an toàn hay mạo hiểm, trong khi một mô hình dự báo được xây dựng để dự báo lượng thiết bị máy tính được mua bởi các khách hàng tiền năng dựa vào thu nhập và nghề nghiệp của họ Nhiều phương pháp phân lớp và dự báo đã được giới thiệu bởi các nhà nghiên cứu trong lĩnh vực học máy, hệ chuyên gia, thống kê…. 1.2.2. Các bước để phân lớp và dự báo Phân lớp dữ liệu gồm hai bước xử lý chính: Bước 1: Học (training) xây dựng một mô hình xác định một tập các lớp dữ liệu. Mô hình này được xây dựng bằng cách phân tích các bộ dữ liệu của một cơ sở dữ liệu, mỗi bộ dữ liệu được xác định bởi giá trị của các thuộc tính vào một lớp được xác định trước. Bước này được xem là học có giám sát, các mẫu huấn luyện thuộc về là biết trước và số lớp dữ liệu cũng được biết trước. Những bộ dữ liệu được phân tích để xây dựng mô hình phân lớp được lấy từ trong tập dữ liệu học hay dữ liệu huấn luyện. Mô hình đưa ra sau khi phân tích xong tập dữ liệu huấn luyện thường có dạng là những quy tắc phân lớp, cây quyết định hay các công thức toán học Hình 1-0: Bước 1 Học để xây dựng mô hình phân lớp Dữ liệu học Thuật toán phân lớp Mô hình phân lớp 6 Bước 2: Kiểm tra và đánh giá, bước này sử dụng mô hình phân lớp đã được xây dựng ở bước 1 vào việc phân lớp. Đánh giá độ chính xác của mô hình hay bộ phân lớp, bằng cách sử dụng một tập các mẫu đã được phân lớp lớp để thử (test) gọi là bộ thử (test set). Những mẫu này được chọn ngẫu nhiên và độc lập với các mẫu đã được học ở bước 1 gọi là mẫu thử (test sample). Độ chính xác của một mô hình phân lớp dựa trên bộ thử là tỷ lệ những mẫu thử được phân lớp đúng bằng mô hình phân lớp đó. Nếu độ chính xác của một mô hình được xem xét có thể chấp nhận được thì mô hình đó được dùng để phân lớp cho các bộ dữ liệu hoặc các đối tượng trong tương lai Tin cậy Hình 1-1: Bước 2 Kiểm tra và đánh giá Lấy ví dụ, cho một cơ sở dữ liệu về thông tin tiền gửi của khách hàng, quy tắc phân lớp có thể được học để phân biệt khách hàng có loại tiền gửi được đánh giá tốt hay rất tốt (hình 1.2 ). Quy tắc có thể được sử dụng để phân loại các mẫu dữ liệu về sau, cũng như cung cấp những hiểu biết tốt hơn về nội dung của cơ sở dữ liệu Từ những quy tắc đã học được từ việc phân tích dữ liệu khách hàng đã tồn tại có thể được sử dụng để dự báo tiền gửi của khách hàng mới hoặc khách hàng về sau (hình 1.3) Dữ liệu kiểm chứng Mô hình phân lớp Dữ liệu mới 7 Hình 1-2: Ví dụ về học mô hình John Henri, 31…40 High Đánh giá tiền gửi? Rất tốt Hình 1-3 : Ví dụ về phân lớp dữ liệu Tên Tuổi Thu nhập Đánh giá tiền gửi Sandy Jones Bill Lee Coutnay fox Susan Lake Claire Phips ……. <=30 <=30 31….40 >40 31….40 …. Thấp Thấp Cao Trung bình Trung bình …… Tốt Rất tốt Rất tốt Tốt Tốt ….. Tên Tuổi Thu nhập Đánh giá tiền gửi Frank Jones Sylvia Crest Anne Yee ….. >40 <=30 31….40 …… Cao Thấp Cao ….. Tốt Tốt Rất tốt …… Dữ liệu huấn luyện Thuật toán phân lớp Quy tắc phân lớp Nếu tuổi = “31…40” và thu nhập = “cao” đánh giá tiền gửi = “rất tốt” Dữ liệu kiểm chứng Quy tắc phân lớp Dữ liệu mới 8 “Dự báo khác biệt với phân lớp ở chỗ nào?” Dự báo có thể xem như việc xây dựng và sử dụng mô hình để đánh giá một lớp ví dụ chưa được gán nhãn, hoặc để đánh giá giá trị hay khoảng giá trị của một thuộc tính trong một ví dụ đã cho có thể có. Theo cách này, phân lớp và hồi quy là hai loại quan trọng của dự báo vấn đề phân lớp được sử dụng để dự báo những giá trị rời rạc hoặc dùng vào việc chỉ tên, trong khi hồi quy được sử dụng để dự báo những giá trị liên tục hoặc đã được sắp xếp. Tuy nhiên, theo quan điểm của chúng ta, việc sử dụng dự báo để tiên đoán những nhãn lớp như là phân lớp và sử dụng dự báo để dự đoán những giá trị liên tục (tức là sử dụng kỹ thuật hồi quy) vẫn hay được sử dụng hơn. Quan điểm này thường cũng được chấp nhận trong khai phá dữ liệu [2, 20]. 1.2.3. Độ chính xác trong phân lớp và dự báo Độ chính xác trong phân lớp và dự báo được đo bằng ước lượng tỷ lệ sai: - Phân hoạch: Huấn luyện và kiểm tra đối với những tập dữ liệu lớn. Dùng hai tập dữ liệu độc lập, tập huấn luyện bằng 2/3 tập dữ liệu, tập kiểm tra bằng 1/3 tập huấn luyện - Kiểm tra chéo: Dùng với những tập dữ liệu vừa, chia tập dữ liệu thành k mẫu con, sử dụng k-l mẫu con làm tập huấn luyện và một mẫu con làm tập kiểm tra—kiểm tra chéo k thành phần - Bootstrapping: Dùng với những tập dữ liệu nhỏ, xóa đi một – leave-one-out 1.2.4. Một số bài toán phân lớp và dự báo điển hình • Những người có nguy cơ cao, trung bình hoặc thấp với một loại bệnh tật nào đó • Các đối tượng hiện lên màn hình radar tương ứng với các vật thể như xe cộ, người, tòa nhà hay cây cối • Những người có vẻ giống, hơi giống hoặc không giống với tội phạm • Những ngôi nhà có thể tăng giá, giảm giá hoặc giữ giá trong vòng 1 năm tới • Độ chính xác của thời tiết (mưa) của ngày tiếp theo trong dự báo thời tiết (chính xác cao, có vẻ đúng, không đúng, hầu như sai) • Các khách hàng có vẻ muốn hoặc không muốn mua một sản phẩm nào đó trong siêu thị 9 1.3. Bài toán dự báo xu thế thị trường chứng khoán Các hệ thống tài chính thường là những hệ thống rất phức tạp vì vậy rất khó có thể dự đoán được dữ liệu của nó. Ví dụ như thị trường chứng khoán, việc dự đoán được sự lên xuống của thị trường chứng khoán quả là không đơn giản. Tính phi tuyến tính của thị trường chứng khoán kèm theo sự mù quáng của các nhà đầu tư làm cho việc dự đoán thị trường chứng khoán rất phức tạp và khó khăn. Vì vậy, việc làm thế nào để dự đoán tốt thị trường chứng khoán trở nên rất thú vị đối với các nhà nghiên cứu và phân tích Để dự đoán được xu thế của thị trường chứng khoán, chúng ta phải thừa nhận rằng có một số luật cơ bản có thể được lặp đi lặp lại trong thị trường chứng khoán. Các luật này ẩn trong lịch sử dữ liệu. Từ khía cạnh toán học, các luật này là các hàm quan hệ. Đối tượng của dự đoán chính là tìm ra các luật này và mô tả chúng. Những dự đoán của hệ thống phi tuyến động có thể được chuyển đổi thành vấn đề dự đoán chuỗi thời gian thực. Những nghiên cứu trước chỉ ra rằng, để dự đoán dữ liệu chuỗi thời gian phi tuyến tính thì sử dụng cây quyết định là một phương pháp hiệu quả. Chính vì lẽ đó, cây quyết định là mô hình tốt để dự đoán xu thế của thị trường chứng khoán. Ngày nay có rất nhiều nghiên cứu trên lĩnh vực này, nhưng trong những nghiên cứu đó, thị trường chứng khoán có thể không được phân tích từ khía cạnh toán học, vì thế mà cơ sở toán học của phương pháp này không được công khai. Vì vậy để giải quyết bài toán tốt hơn, trước hết, cần đưa ra mô tả toán học của thị trường chứng khoán. Với một hệ thống động, sự phát triển của nó có thể được mô tả bằng phương trình vi phân ( 1)( , ',..., ) p p p d x f x x x dx −= (1.0) Nếu một biến trạng thái của quá trình này là lời giải cho phương trình ở trên, thì hệ thống có thể được mô hình hóa thành một vài chuỗi thời gian của biến này 2 2 ( , ) d x dxf x dt dt = (1.1) 10 Giả sử rằng nghiệm của phương trình là một chuỗi thời gian với bước h, x(j), j = 1 ~ n, và sau đó mô hình của hệ thống có thể được thực hiện với các phép tính, lời giải của phương trình vi phân bình thường ở trên. Các đáp án của hệ số vi phân tại j của phương trình trên được thay thế bởi sự khác nhau dưới đây: 2 2 2 2 ( 1) 2 ( ) ( 1)| ( )j d x x j x j x j o h dt h + − + −= + (1.2) ( ) ( 1)| ( )j dx x j x j o h dt h − −= + (1.3) Từ đó ta có được hàm sau 2 3( ) ( 1)( 1) ( ), 2 ( ) ( 1) ( )x j x jx j h f x j x j x j o h h − −⎡ ⎤+ = + − − +⎢ ⎥⎣ ⎦ (1.4) Có thể viết hàm trên thành một hàm tổng quát sau: ( 1) ( ( ), ( 1), )x j F x j x j h+ = − (1.5) Tổng quát hóa đến phần tử thứ p, ta có hàm tổng quát sau: ( 1) ( ( ), ( 1),...., ( 1), )x j F x j x j x j p h+ = − − + (1.6) Các khía cạnh chính của hàm nói trên để xác nhận hàm quan hệ F. Vì hệ thống áp dụng chức năng giao dịch phi tuyến tính, thế nên những vấn đề phức tạp về phi tuyến tính có thể được giải quyết rất tốt trong cây quyết định. Dựa vào lý thuyết cơ bản về cây quyết định, từ đó ta xây dựng mô hình cây quyết định cho bài toán dự báo xu thế chứng khoán [7]. 1.4. Nội dung và cấu trúc của khóa luận Với nội dung trình bày những lý thuyết cơ bản về mô hình cây quyết định cho dữ liệu chứng khoán – dữ liệu thời gian thực (time series) và áp dụng vào bài toán dự báo sự lên xuống của thị trường chứng khoán. Khóa luận được tổ chức theo cấu trúc như sau: Chương 1: Giới thiệu các kiến thức cơ sở 11 Giới thiệu sơ lược về khai phá dữ liệu, bài toán phân lớp và dự báo và bài toán dự báo cho lĩnh vực chứng khoán được phân tích dưới khía cạnh toán học giúp ta chọn hướng giải quyết tốt nhất cho bài toán là sử dụng mô hình học máy – mô hình cây quyết định. Chương này giới thiệu những gì mà khóa luận nghiên cứu từ đó thông qua việc trình bày về nội dung và cấu trúc của khóa luận. Chương 2: Tổng quan về cây quyết định Chương hai đi vào giới thiệu một cách tổng quát nhất về cây quyết định, cấu trúc và hoạt động của cây quyết định, các độ đo dùng để tìm điểm chia cắt thuộc tính tốt nhất, các thuật toán dùng để xây dựng cây quyết định và giới thiệu kỹ thuật toán C4.5. Với những kiến thức cơ bản này, người đọc sẽ hiểu được phần nào cấu trúc, hoạt động cũng như những ưu nhược điểm của cây quyết định từ đó có thể xây dựng được mô hình phù hợp cho từng bài toán Chương 3: Mô hình cây quyết định cho dữ liệu chứng khoán – dữ liệu time series trong bài toán dự báo xu thế thị trường chứng khoán Chương này giới thiệu dữ liệu thời gian thực (time series), dữ liệu chứng khoán trong bài toán dự báo chứng khoán. Qua đó xây dựng mô hình xử lý bài toán và thiết kế chi tiết mô hình cây quyết định, cách thực hiện từng bước trong thiết kế mô hình cây quyết định Chương 4: Thực nghiệm Giới thiệu sơ lược về phần mềm mã nguồn mở weka – công cụ mà khóa luận sử dụng để xây dựng mô hình dự báo xu thế chứng khoán, xây dựng mô hình, đánh giá mô hình dựa trên các độ đo xác định, từ đó chọn được mô hình tốt nhất cho bộ dữ liệu mà tác giả sử dụng. Trong chương này, tác giả cũng giới thiệu hai mô hình khác và có điều chỉnh tham số của hai mô hình này để cho ra kết quả tốt nhất rồi so sánh với kết quả tốt nhất của mô hình mà tác giả đã dùng Chương 5: Kết luận Chương này tổng kết lại những gì đã đạt được và chưa đạt được. Từ đó nêu lên những kết quả hướng tới, hướng nghiên cứu và phát triển tiếp theo của luận văn này 12 Chương 2. Tổng quan về cây quyết định 2.1. Định nghĩa Cây quyết định (decision tree) là một trong những hình thức mô tả dữ liệu trực quan nhất, dễ hiểu nhất đối với người dùng. Trong lĩnh vực học máy, cây quyết định là một kiểu mô hình dự báo (prediction model), nghĩa là ánh xạ từ các quan sát về một sự vật/hiện tượng tới các kết luận về giá trị mục tiêu của sự vật/hiện tượng [20]. 2.2. Cấu trúc Một cây quyết định là một sơ đồ có cấu trúc dạng cây bao gồm các nút và các nhánh. Nút dưới cùng được gọi là nút lá, trong mô hình phân lớp dữ liệu chính là các giá trị của các nhãn lớp (gọi tắt là nhãn). Các nút khác nút lá được gọi là các nút trong tương ứng với một biến, đây còn là các thuộc tính của tập dữ liệu, hiển nhiên các thuộc tính này phải khác thuộc tính phân lớp. Mỗi một nhánh của cây xuất phát từ một nút trong nào đó ứng với một phép so sánh dựa trên miền giá trị của nút đó. Nút đầu tiên được gọi là nút gốc của cây Hình 2-0: Biểu diễn cấu trúc cây quyết định Nút gốc Nút trong Nút lá Nút lá Nút lá Nhánh 13 Cây quyết định có thể được mô tả như là sự kết hợp của các kỹ thuật toán học và tính toán nhằm hỗ trợ việc mô tả, phân loại và tổng quát hóa một tập dữ liệu cho trước Dữ liệu được cho dưới dạng các bản ghi có dạng: (x, y) = (x1, x2, x3….xk, y) Biến phụ thuộc y là biến mà chúng ta cần tìm hiểu, phân loại hay tổng quát hóa x1, x2, x3…. là các biến sẽ giúp ta thực hiện công việc đó. 2.3. Các kiểu cây quyết định Cây quyết định còn có hai tên khác: Cây hồi quy (Regression tree): ước lượng các hàm có giá trị là số thực thay vì được sử dụng cho các nhiệm vụ phân loại. Ví dụ: ước tính giá một ngôi nhà hoặc khoảng thời gian một bệnh nhân nằm viện Cây phân loại (Classification tree): nếu y là một biến phân loại như: giới tính (nam hay nữ), kết quả của một trận đâu (thắng hay thua) 2.4. Các độ đo sử dụng để xác định điểm chia tốt nhất Như phần trên đã phân tích thì các tiêu chí để đánh giá tìm điểm chia là rất quan trọng, chúng được xem là một tiêu chuẩn “heuristic” để phân chia dữ liệu. Ý tưởng chính trong việc đưa ra các tiêu chí trên là làm sao cho các tập con được phân chia càng trở nên “trong suốt” (tất cả các bộ thuộc về cùng một nhãn) càng tốt. Cho một tập dữ liệu D, một tập các nhãn Ci (i >=1 và i <= m với m là số nhãn), định nghĩa các khái niệm sau: Ci, D: là tất cả các bộ dữ liệu có nhãn lớp Ci trong D |D|: là tổng số bộ dữ liệu của tập dữ liệu D |Ci, D|: là tổng số bộ dữ liệu của tập dữ liệu D có nhãn lớp Ci Với các khái niệm trên, thông thường người ta sẽ sử dụng ba tiêu chỉ sau để đánh giá chọn điểm chia: 14 2.4.1. Độ lợi thông tin (Information Gain) Độ đo này dựa trên cơ sở lý thuyết thông tin của nhà toán học Claude Shannon, độ đo này xác định giá trị của nội dung mà các thông tin sở hữu trong một loạt các thông điệp. Độ đo này phụ thuộc vào độ đo sự hỗn loạn của tập dữ liệu và thông tin có được sau khi phân lớp • Đo sự hỗn loạn của tập dữ liệu (entropy) Info (D) = - 2 1 .log m i i i p p = ∑ (2.0) Với pi là xác suất của một bộ bất kỳ trên D thuộc về nhãn Ci | , | | |i iC Dp D = (2.1) Có thể xem công thức Info(D) như một hàm tính giá trị trung bình trên lượng thông tin nhằm xác định nhãn của một bộ bất kỳ trong tập D • Độ đo thông tin có được sau khi phân lớp Giả sử phân chia các bộ trong D trên một thuộc tính A bất kỳ, để không mất tính tổng quát có thể xem A có các giá trị phân biệt {a1, a2, a3, …, av}. Nếu thuộc tính A được sử dụng để chia thành v tập con, những tập con này sẽ tương ứng với các nhánh con của nút hiện tại. Độ đo thông tin có được sau khi phân lớp theo v tập con trên sẽ được tính như sau: Info A (D) = 1 ( ) v j j j D Info D D= ∑ (2.2) Với |Dj| là tổng số bộ dữ liệu được phân chia vào tập con thứ j Độ đo Gain được xác định là sự khác biệt giữa thông tin gốc (thông tin khi chưa phân lớp) và thông tin mới (thông tin sau khi đã phân lớp). Thông tin có được bởi việc phân nhánh trên thuộc tính A là: Gain (A) = Info(D) – InfoA(D) (2.3) Nói một cách khác, độ đo Gian cho biết được lượng thông tin thu được khi phân lớp, thuộc tính nào có độ đo Gain lớn nhất sẽ được chọn làm ứng cử viên để phân chia. Việc chọn thuộc tính theo tiêu chí độ đo Gian lớn nhất tương đượng với việc muốn tìm được 15 một phân hoạch sao cho việc phân lớp là tốt nhất hay nói cách khác lượng thông tin cần thiết để hoàn thành việc phân lớp ( thể hiện qua giá trị là nhỏ nhất) 2.4.2. Độ đo tỷ lệ Gain (Gain ratio) Theo các nghiên cứu thì độ đo Gain thích hợp trong trường hợp các thuộc tính có nhiều giá trị hiện hành (dĩ nhiên các giá trị này phải thuộc miền giá trị, ví dụ với 100 mẩu tin có 80 giá trị khác nhau của thuộc tính khi sử dụng phép chiếu lên thuộc tính). Độ đo tỷ lệ Gain (Gain ratio) được mở rộng từ độ đo Gain, được định nghĩa như sau: 2 1 | | | | ( ) log ( ) | | | | v j j A j D D SplitInfo D D D= = ×∑ (2.4) Công thức SplitInfoA (D) cho biết thông tin tiềm ẩn được tạo ra bằng cách chia tập D trong v tập con. Với mỗi tập con được tạo ra, tính toán tỷ lệ của số bộ trong tập con này so với tổng số bộ dữ liệu trong tập D. Khi đó, độ đo tỷ lệ Gain sẽ được tính theo công thức sau: ( )( ) ( ) Gain AGainRatio A SplitInfo A =     (2.5) Tất cả thuộc tính sẽ được tính toán độ đo tỷ lệ Gain, thuộc tính nào có độ đo tỷ lệ Gain lớn nhất sẽ được chọn làm thuộc tính phân chia. 2.4.3. Chỉ số Gini (Gini index) Chỉ số Gini được sử dụng trong thuật toán CART. Trái ngược với độ đo Gain, chỉ số Gini là độ đo về tính “không trong suốt” của tập dữ liệu. Chỉ số Gini của một tập dữ liệu D được định nghĩa như sau: 2 1 ( ) 1 ( ) m i i G i n i D p = = − ∑ (2.6) Với m là tổng số nhãn lớp, pi là xác suất để một bộ bất kỳ trong D thuộc về một nhãn Ci, được tính như sau: , | | | | i D i C p D = (2.7) 16 Chỉ số Gini thường sẽ được tính toán dựa trên giả định về một tập dữ liệu D được phân chia nhị phân thành hai tập con. Đầu tiên xét trường hợp thuộc tính A bất kỳ trong D có kiểu dữ liệu rời rạc, khi dùng phép chiếu sẽ thu được v = {a1, a2, …., av} giá trị khác nhau. Để xác định điểm chia tốt nhất của A, kiểm tra tất cả tập con có thể tạo được từ v giá trị phân biệt trên, mỗi tập con tạm gọi là SA là một điều kiện kiểm tra nhị phân dạng A € SA. Như vậy với v giá trị khác nhau ta sẽ có 2v – 2 tập con, trong đó tập rỗng và tập toàn phần v = {a1, a2, ….,av} sẽ không được xét đến. Như vậy tiến hành lặp qua tất cả các tập con này, mỗi lần lặp sẽ phân chia tập giá trị v thành hai tập con v1 và v2 riêng biệt thỏa điều kiện rời rạc toàn phần (hội v1 và v2 chính là tập v và phần giao là tập rỗng). Với hai tập con v1 và v2 này tương ứng tập con D cũng được phân chia thành hai tập con D1 (các bộ có giá trị thuộc tính A € v1) và D2 (các bộ có giá trị thuộc tính A € v2) theo, Gini (D) sẽ được tính như sau: 1 2 1 2 | | | |( ) ( ) ( ) | | | |A D DGini D Gini D Gini D D D = + (2.8) Khác với độ đo Gain, ta chọn chỉ số Gini nhỏ nhất với mong muốn sau khi phân chia dữ liệu sẽ làm giảm tính không trong suốt của tập D nhiều nhất. Đối với các giá trị liên tục thì đầu tiên phải sắp xếp các giá trị này, sau đó tất cả các giá trị cũng sẽ được tính toán chỉ số Gini và cũng chọn ra giá trị nào có thuộc tính Gini nhỏ nhất. Cũng giống như độ đo Gain, chỉ số Gini thông thường cũng được tính cho điểm giữa của hai giá trị liên tục nằm liền kề nhau. Lúc này tập D sẽ được chia làm hai tập D1 là các bộ dữ liệu thỏa điều kiện giá trị thuộc tính A nhỏ hơn hoặc bằng giá trị điểm giữa và D2 thỏa điều kiện giá trị thuộc tính A lớn hơn giá trị điểm giữa. Mục tiêu của chỉ số Gini là càng làm giảm tính không trong suốt của dữ liệu càng nhiều càng tốt, giá trị giảm trừ này thực hiện qua công thức: Ugini (A) = Gini(D) – GiniA(D) (2.9) Lưu ý Gini (D) là một con số cố định, chính vì mục đích chọn điểm chia sao cho Ugini(A) là lớn nhất nên bắt buộc chọn thuộc tính A sao cho GiniA(D) là nhỏ nhất [3] [19] 17 2.5. Cắt tỉa cây (thu gọn cây) Khi xây dựng cây quyết định, cấu trúc của một cây quyết định là một vấn đề quan trọng cần xem xét, có thể các nhánh sẽ phản ánh những dị thường trong dữ liệu thử do nhiễu hay dữ liệu không liên quan. Cắt nhánh hay không cắt nhánh cây có thể làm thay đổi hiệu quả học từ các tập dữ liệu. Cắt nhánh làm giảm kích thước của cây do loại bỏ bớt các nhánh thừa trong quá trình xây dựng cây do đó làm giảm sự phức tạp của kết quả phân lớp và độ chính xác của dự báo cũng tốt hơn Phương thức này thông thường sử dụng độ đo thống kê để loại bỏ những nhánh ít tin cậy nhất, nhìn chung sẽ mang lại kết quả phân lớp nhanh hơn và cải thiện được độ tin cậy của cây để giải quyết vấn đề phân lớp bị độc lập với dữ liệu thử Nhìn chung có hai phương pháp thu gọn cây như sau: Phương pháp thu gọn cây trước: Cây được thu gọn bằng cách tạm dừng quá trình dựng cây sớm (tức là bằng cách quyết định không tiếp tục phân chia tập con ví dụ đào tạo ở nút hiện tại nhỏ hơn nữa), do dừng việc phân chia sớm này, nút đó sẽ trở thành một lá, lá này có thể chứa đựng lớp xuất hiện nhiều nhất trong số các tập mẫu con hay phân bố xác suất của các mẫu Khi xây dựng một cây, các độ đo như ý nghĩa thống kê, lợi ích thông tin,… có thể được sử dụng để đánh giá độ tốt của việc chia cắt. Nên việc phân hoạch các mẫu tại nút đó có kết quả nằm ở bên dưới một ngưỡng định trước nào đó thì sẽ không phân chia tiếp các tập con nữa. Tuy nhiên để chọn được một ngưỡng phù hợp là một việc làm khó. Ngưỡng cao sẽ mang lại một cây quá đơn giản, trong khi ngưỡng thấp có thể mang lại một cây quá chi tiết Phương pháp rút gọn cây sau: Thực hiện loại bỏ các nhánh khỏi một cây đã được xây dựng xong. Một nút của cây được rút gọn bằng cách loại bỏ các nhánh của nó. Nút thấp nhất không bị thu gọn sẽ trở thành lá và được gán nhãn bằng nhãn lớp xuất hiện nhiều nhất trong số các nhánh của nó trước đó. Với mỗi nút không phải là lá trong cây, thuật toán sẽ tính toán tỷ lệ lỗi mong muốn xảy ra nếu cây con tại nút đó không bị cắt cụt bằng việc sử dụng tỷ lệ lỗi cho mỗi nhánh, được kết hợp bởi lỗi lớn hơn tỷ lệ lỗi mong muốn thì cây con đó được giữ lại, nếu không thì nó sẽ bị loại bỏ. Sau khi sinh ra một tập 18 các cây đã được cắt gọn theo từng nấc, một loạt các phép thử độc lập được sử dụng để đánh giá sự chính xác của mỗi cây này. Cây quyết định nào mà có tỷ lệ lỗi thấp nhất sẽ được ưu tiên chọn Chúng ta cũng có thể sử dụng xen kẽ hai phương pháp thu gọn cây trước và thu gọn cây sau trong quá trình thu gọn cây. Thu gọn cây đòi hỏi nhiều tính toán hơn thu gọn cây trước, song thông thường nó mang lại cây quyết định tin cậy hơn 2.6. Rút ra quy tắc phân lớp từ cây quyết định “Chúng ta có thể rút ra được quy tắc phân lớp từ cây quyết định? Nếu có thì như thế nào?” Tri thức biểu diễn trong cây quyết định có thể được rút ra và biểu diễn dưới hình thức của quy tắc phân lớp IF-THEN. Một quy tắc được tạo rat hay thế cho một đường dẫn tới một nút lá. Mỗi một cặp thuộc tính-giá trị theo một hướng đi cụ thể hình thành phần đầu của quy tắc (phần “IF”). Nút lá chứa lớp dự đoán, hình thành phần sau của quy tắc (phần “THEN”). Quy tắc IF-THEN có thể làm cho người đọc dễ hiểu, đặc biệt trong trường hợp cây lớn. Ví dụ cây quyết định sau Hình 2-1: Một cây quyết định miêu tả khái niệm “mua máy tính” Ta có thể chuyển đổi thành quy tắc phân lớp có dạng IF-THEN bằng cách lần theo đường dẫn từ gốc đến từng nút lá như sau: Tuổi Sinh viên Tỷ lệ tiền gửi Có Có Không Có Không <=30 31…4 Rất tốt Tốt >40 đúngsai 19 IF tuổi=”<=30” AND sinh_vien = “sai” THEN mua_may_tinh= “sai” IF tuoi = “<=30” AND sinh_vien = “đúng” THEN mua_may_tinh = “đúng” IF tuoi = “31…40” THEN mua_may_tinh = “sai” IF tuoi = “>40” AND ty_le_tien_gui = “rất tốt” THEN mua_may_tinh = “sai” IF tuoi = “>40” AND ty_le_tien_gui = “tốt” THEN mua_may_tinh = “đúng” Một quy tắc có thể được thu gọn bằng cách loại bỏ một số điều kiện ở phần đầu của quy tắc, điều này không làm cải tiến độ chính xác ước lượng của quy tắc. Với mỗi lớp, các quy tắc trong một lớp sau đó có thể được xếp loại theo độ chính xác ước lượng của chúng. Vì thế khả năng một mẫu thử đã cho sẽ không thỏa mãn phần đầu của mọi quy tắc, một quy tắc mặc định được gán cho đa số các lớp, thông thường cũng được thêm vào tập quy tắc kết quả 2.7. Các thuật toán trong cây quyết định Cây quyết định là một trong những giải pháp trực quan và hữu hiệu để mô tả quá trình phân lớp dữ liệu. Do cây quyết định rất hữu dụng nên đã có nhiều nghiên cứu để xây dựng nó mà nổi bật là các thuật toán học quy nạp như CARD, ID3, C45….. Các thuật toán trên đều dựa trên một thuật toán cơ bản để xây dựng cây chỉ khác nhau ở tiêu chuẩn/thuộc tính phân chia và độ đo để lựa chọn. Thuật toán ID3 (Iterative Dichotomiser 3) do Quinlan Ross giới thiệu vào năm 1986 [11]. Nó dựa trên thuật toán Hunt và sử dụng độ lợi thông tin (Gain) để lựa chọn thuộc tính phân lớp các đối tượng. Ý tưởng cơ bản của giải thuật ID3 là để xây dựng cây quyết định bằng việc sử dụng một cách tìm kiếm từ trên xuống trên những tập hợp cho trước để kiểm tra mỗi thuộc tính tại mỗi nút của cây, thuộc tính nào có độ lợi thông tin (Gain) lớn nhất sẽ được chọn để phân chia đối tượng. Quá trình này được thực hiện một cách đệ quy cho đến khi tập đối tượng tại một cây con đã trở nên thuần nhất, tức là nó chỉ chứa các đối tượng thuộc về cùng một lớp. Lớp này sẽ trở thành một lá của cây. Thuật toán C4.5 là một cải tiến của thuật toán ID3, do Quinlan Ross phát triển vào năm 1993, sử dụng độ đo tỷ lệ gain làm tiêu chuẩn chia cắt [11]. Khi số lượng các trường 20 hợp nhỏ hơn một ngưỡng nào đó thì nó bị cắt khỏi cây. Lỗi cắt tỉa được tính toán sau khi mở rộng cây. C4.5 có thể xử lý các thuộc tính số. Thuật toán CART (classification and regression trees) do Breiman phát triển vào năm 1984, gồm cả phân lớp và hồi quy cây [11]. Phân lớp trong CART dựa trên việc chia cắt nhị phân các thuộc tính, sử dụng độ đo gini để lựa chọn thuộc tính chia cắt. Cắt tỉa cây trong CART được thực hiện bằng cách sử dụng một phần của tập dữ liệu huấn luyện. CART sử dụng cả thuộc tính kiểu số và thuộc tính rõ ràng trong xây dựng cây quyết định và có khả năng xử lý với các thuộc tính lỗi. CART khác với các thuật toán khác, nó sử dụng phân tích hồi quy để giúp quá trình hồi quy của cây. Những đặc điểm phân tích hồi quy được sử dụng trong dự đoán một biến phụ thuộc trong một tập hợp các biến dự đoán trong một khoảng thời gian (Breiman, 1984) [11]. Nó sử dụng nhiều biến độc lập làm tiêu chuẩn chia cắt như chỉ số gini, symgin…và một trong nhiều biến để xác định điểm chia tốt nhất và dữ liệu được sắp xếp ở mọi nút.Các tiêu chí kết hợp chia cắt tuyến tính được sử dụng trong suốt quá trình phân tích hồi quy. Salford systems đã thực hiện phiên bản của CART gọi là CARTR sử dụng mã ban đầu của Breiman (1984) [11]. CARTR mở rộng những đặc tính và khả năng phân lớp và dự đoán chính xác của cây với những dữ liệu thiếu Trong [13], hai tác giả Matthew N.Anyanwu và Sajjan G.Shiva đã xem xét khoảng 30 bài báo để khảo sát xem trong một loạt các thuật toán của cây quyết định thì thuật toán nào hay được sử dụng nhất. Thuật toán Tỷ lệ sử dụng CLS 9% ID3 4.5% C4.5 54.55% C5.0 9% CART 40.9% Random Tree 4.5% Random Forest 9% 21 SLIQ 27.27% ……… …… Hình 2-2: Kết quả của cuộc khảo sát Theo như cuộc khảo sát trên thì thuật toán C4.5 là thuật toán được sử dụng nhiều nhất, sau đó là thuật toán CART. Thuật toán CART sử dụng độ đo gini để xác định điểm chia còn thuật toán C4.5 sử dụng độ đo tỷ lệ gain. Kiểm tra trên CART luôn là nhị phân, nhưng trên C4.5 cho phép hai hay nhiều giá trị thuộc tính. CART cắt nhánh cây dùng một mô hình chi phí phức tạp qua các tham số được ước lượng bằng cách kiểm tra chéo (cross-validation), C4.5 dùng một giải thuật để xác định một giá trị nhận được từ một giới hạn nhị phân đáng tin cậy. Do đó kết quả phân lớp khi sử dụng thuật toán C4.5 sẽ tốt hơn, nhanh hơn thuật toán CART. Trong luận văn này, tôi sử dụng thuật toán C4.5 để xây dựng mô hình cây quyết định cho bài toán phân lớp 2.8. Quá trình tạo cây quyết định 2.8.1. Khả năng học và tổng quát hóa Có thể nói đặc trưng cơ bản nhất của cây quyết định là khả năng học và tổng quát hóa. Trong kỹ thuật học máy dùng cây quyết định được gọi là học bằng cây quyết định, hay chỉ gọi với cái tên ngắn gọn là cây quyết định Học: là khả năng mà cây quyết định có thể phân loại chính xác những mẫu đã được huấn luyện Tổng quát hóa: là khả năng cây có thể nhận biết được những mẫu chưa từng được huấn luyện. Chính khả năng này tạo nên sức mạnh của mạng 2.8.2. Các phương pháp huấn luyện cây Huấn luyện cây: là quá trình tạo cây sao cho khả năng học và tổng quát hóa mà nó đạt được là cao nhất. Bản chất của việc làm này là tính toán lượng thông tin nhận được trên các thuộc tính và chọn thuộc tính tương ứng có lượng thông tin tối đa làm nút phân 22 tách trên cây. Hai kiểu huấn luyện mạng phổ biến là học có giám sát (supervised learing) và học không có giám sát (unsupervised learing) Hoc có giám sát: là phương pháp học thực hiện một công việc nào đó dưới sự giám sát của một thầy giáo. Học có giám sát yêu cầu nhà phân tích dữ liệu xác định một thuộc tính đích hay biến phụ thuộc. Sau đó xem xét toàn bộ dữ liệu để cố gắng tìm ra những mẫu hoặc các mối quan hệ giữa các thuộc tính độc lập (dự báo) và thuộc tính phụ thuộc. Học có giám sát sử dụng dữ liệu trong quá khứ để xây dựng mô hình và sử dụng mô hình này để phân lớp dữ liệu mới và dự báo các lớp thành viên hay lớp giá trị Học không có giám sát: là phương pháp học để thực hiện một công việc nào đó mà không cần bất kỳ sự giám sát nào Các nghiên cứu và thực nghiệm cho thấy rằng: phương pháp học có giám sát là phương pháp huấn luyện phổ biến và hiệu quả đối với cây quyết định Một cây quyết định có thể được học bằng cách lần lượt chia (đệ quy) một tập dữ liệu thành các tập dữ liệu con, một tập con được tạo thành chủ yếu từ các phần tử của cùng một lớp Tại mỗi nút của cây thì các thuật toán đều tính lượng thông tin nhận được trên các thuộc tính và chọn thuộc tính tương ứng có lượng thông tin tối đa làm nút phân tách trên cây-tức là thuộc tính chia tập mẫu thành các lớp mà mỗi lớp có một phân loại duy nhất hay ít nhất thuộc tính phải có triển vọng đạt được điều này, nhằm để đạt được cây có ít nút nhưng có khả năng dự đoán cao. Quá trình đệ quy hoàn thành khi không thể tiếp tục thực hiện việc chia tách được nữa hay đầu ra thực tế của cây gần với đầu ra mong muốn nhất 2.9. Giải thuật C4.5 Giải thuật cây quyết định C4.5 là phương pháp học có giám sát. Cho một tập dữ liệu các thuộc tính được định giá trị mà trong đó, mỗi trường hợp được mô tả bằng tập hợp các thuộc tính và thuộc về một trong các lớp riêng biệt, C4.5 học một ánh xạ từ các giá trị thuộc tính đến các lớp học có thể được áp dụng để phân loại cho dữ liệu mới, trường hợp chưa được biết trước đó 23 C4.5 không chỉ là một giải thuật, mà nhiều hơn nữa còn là bộ các giải thuật: C4.5 cắt nhánh, C4.5 không cắt nhánh. Do cắt nhánh làm giảm kích thước của cây do loại bỏ bớt các nhánh thừa trong quá trình xây dựng cây do đó làm giảm sự phức tạp của kết quả phân lớp và độ chính xác của dự báo cũng tốt hơn. Nên trong khóa luận này, tôi sử dụng giải thuật C4.5 cắt nhánh Giải thuật phân lớp sử dụng C4.5 cắt nhánh FormTree (T) (1) ComputerClassFrequency(T) (2) If OneClass or FewCases Return a leaf; Create a decision node N; (3) For Each Attribute A ComputeGain (A); (4) N.test=AttributeWithBestGain; (5) If(N.test is continuous) Find Threshold; (6) For Each T’ in the splitting of T (7) If(T’ is Empty) Child of N is a leaf else (8) Child of N = FormTree(T’); (9) ComputeErrors of N; Return N; 24 Giải thuật này có thể được mô tả theo một cách khác nhau như sau: [5] Cho một tập S các trường hợp, C4.5 đầu tiên khởi tạo một cây dùng giải thuật chia để trị như: • Nếu tất cả các trường hợp trong S đều cùng một lớp hay tập S nhỏ, cây chỉ có một nút lá với nhãn là nhãn của đa số trong tập S. • Ngược lại, chọn kiểm tra dựa trên một thuộc tính có hai hay nhiều giá trị thuộc tính. Thực hiện việc tính toán kiểm tra này xác định được gốc của cây và cùng với sự phân hoạch tập S thành các tập con tương ứng S1, S2,…theo giá trị mỗi thuộc tính của thuộc tính vừa xét chọn. Áp dụng đệ qui cho mỗi tập con vừa được tạo. • Thông thường có nhiều kiểm tra để có thể được chọn ở bước cuối này. C4.5 dùng hai tiêu chuẩn heuristics để xếp hạng ưu tiên các thuộc tính được chọn: độ lợi thông tin (information gain) và tỉ lệ gain (gain ratio). • Các thuộc tính có thể là kiểu loại, kiểu số và các thuộc tính này xác định dạng của việc kiểm tra các giá trị thuộc tính. Cho một thuộc tính A kiểu số có dạng {A ≤h, A>h} với ngưỡng h được xác định bằng cách xếp thứ thự tập S dựa trên thuộc tính A và chọn cắt phân hoạch giữa các giá trị liên tiếp và chọn giá trị cao nhất theo chuẩn đánh giá được dùng như nêu trên. Nếu A là một thuộc tính giá trị rời rạc thì mặc định sẽ có mỗi giá trị thuộc tính cho mỗi bước đánh giá, nhưng một chọn lựa cho phép nhóm hai hay nhiều tập con với mỗi giá trị thuộc tính cho mỗi bước kiểm tra. • Cây ban đầu sau đó được cắt nhánh để tránh ‘overfitting’. Giải thuật cắt nhánh dựa trên một ước lượng thiểu số của tỉ lệ các lỗi có liên quan đến tập N trường hợp. Tập E không thuộc về các lớp đa số. Thay vì E/N, giải thuật C4.5 xác định một giới hạn trên của một phân phối nhị thức khi sự kiện E được quan sát trong N mẫu thử, một tham số riêng được sử dụng thường có giá trị là 0.25. • Cắt nhánh được lan truyền từ lá đến gốc của cây. Lỗi ước lượng tại nút lá với N 25 trường hợp và E lỗi là N lần tỉ lệ lỗi thiêu số như nêu trên. Cho mỗi cây con, C4.5 thêm các lỗi được ước lượng của các nhánh và so sánh nó với cây con được thay thế bới một lá; nếu kết quả sau cùng không cao hơn kết quả trước đó, cây con bị cắt. Tương tự, C4.5 kiểm tra các lỗi ước lượng nếu cây con được thay bằng một nhánh của nó và khi điều này tồn tại và có ích, cây được sửa đổi lại. Quá trình cắt nhánh được hoàn tất xuyên qua cây. Tổng kết Như vậy, ta đã biết một cây quyết định gồm những thành phần nào, các độ đo, các thuật toán dùng trong quyết định. Tóm lại, để xây dựng được một cây quyết định, chúng ta cần nắm vững những khái niệm sau: • Cấu trúc của một cây quyết định: nút lá, nhánh • Độ đo sử dụng để xác định điểm chia để xây dựng được một cây tối ưu So với các phương pháp khai phá dữ liệu khác, cây quyết định là phương pháp có một số ưu điểm sau: • Cây quyết định dễ hiểu. Người ta có thể hiểu mô hình cây quyết định sau khi được giải thích ngắn • Việc chuẩn bị dữ liệu cho một cây quyết định là cơ bản hoặc không cần thiết. Các kỹ thuật khác thường đòi hỏi chuấn hóa dữ liệu, cần tạo các biến phụ và loại bỏ các giá trị rỗng • Cây quyết định có thể xử lý cả dữ liệu có giá trị bằng số và dữ liệu có giá trị là tên thể loại. Các kỹ thuật khác thường chuyên để phân tích các bộ dữ liệu chỉ gồm một loại biến. Chẳng hạn, các luật quan hệ chỉ có thể dùng cho các biến tên, trong khi mạng nơ-ron chỉ có thể dùng cho các biến có giá trị bằng số • Cây quyết định là một mô hình hộp trắng. Nếu có thể quan sát một tình huống cho trước trong một mô hình, thì có thể dễ dàng giải thích điều kiện đó bằng logic Boolean. Mạng nơ-ron là một ví dụ về mô hình hộp đen, do lời giải thích cho kết quả quá phức tạp để có thể hiểu được • Có thể thẩm định một mô hình bằng các kiểm tra thống kê. Điều này làm cho ta có thể tin tưởng vào mô hình 26 • Cây quyết định có thể xử lý tốt một lượng dữ liệu lớn trong thời gian ngắn. Có thể dung máy tính cá nhân để phân tích các lượng dữ liệu lớn trong thời gian đủ ngắn để cho phép các nhà chiến lược đưa ra quyết định dựa trên phân tích của cây quyết định 27 Chương 3. Mô hình cây quyết định trong dự báo xu thế của thị trường chứng khoán 3.1. Giới thiệu chung về dữ liệu thời gian thực Định nghĩa: Dữ liệu thời gian thực hay chuỗi tuần tự theo thời gian (time series) là một chuỗi các giá trị của một đại lượng nào đó được ghi nhận là tuần tự theo thời gian [6, 15]. Những tập dữ liệu chuỗi thời gian rất lớn, xuất hiện trong nhiều lĩnh vực khác nhau như y khoa, kỹ thuật, kinh tế, tài chính.... Ví dụ: Số lượng hàng hóa được bán ra trong 12 tháng năm 2008 của một công ty. Các giá trị của chuỗi tuần tự theo thời gian của đại lượng X được kí hiệu là X1, X2, ….Xt,….Xn. với Xt là giá trị của X tại thời điểm t 3.1.1. Các thành phần của dữ liệu thời gian thực Các nhà thống kê thương chia chuỗi tuần tự theo thời gian thành 4 thành phần: • Thành phần xu hướng dài hạn (long-term trend componet) • Thành phần mùa (seasional componet) • Thành phần chu kỳ (cyclical componet) • Thành phần bất thường (irregular componet) Thành phần xu hướng dài hạn Thành phần này dùng để chỉ xu hướng tăng hay giảm của đại lượng X trong thời gian dài. Về mặt đồ thị thành phần này có thể biểu diễn bởi một đường thẳng thay một đường cong tròn (Smooth curve) 28 Hình 3-0: Thành phần xu hướng dài hạn Thành phần mùa Thành phần này dùng để chỉ xu hướng tăng hay giảm của đại lượng X tính theo mùa trong năm (có thể tính theo tháng trong năm) Ví dụ: Lượng tiêu thụ chất đốt sẽ tăng vào mùa đông và giảm vào mùa hè, ngược lại, lượng tiêu thụ xăng sẽ tăng vào mùa hè và giảm vào mùa đông Lượng tiêu thụ đồ dùng học tập sẽ tăng vào mùa khai trường Đồ thị: Hình 3-1: Thành phần mùa Thành phần chu kỳ Thành phần này chỉ sự thay đổi của đại lượng X theo chu kỳ. Thành phần này khác thành phần chu kỳ ở chỗ chu kỳ của đại lượng X kéo dài hơn 1 năm. Để đánh giá thành phần này các giá trị của chuỗi tuần tự theo thời gian được quan sát hàng năm 29 Ví dụ: Lượng dòng chảy đến hồ Trị An từ năm 1959 – 1985 Hình 3-2: Thành phần chu kỳ Thành phần bất thường Thành phần này dùng để chỉ sự thay đổi bất thường của các giá trị trong chuỗi tuần tự theo thời gian. Sự thay đổi này không thể dự đoán bằng các số liệu kinh nghiệm trong quá khứ, về mặt bản chất thành phần này không có tính chu kỳ. 3.1.2. Các phương pháp làm trơn Trong nhiều chuỗi tuần tự theo thời gian, thành phần mùa và thành phần bất thường thay đổi quá lớn dẫn tới việc xác định giá trị của thành phần xu hướng và thành phần chu kỳ gặp nhiều khó khăn. Để giải quyết vấn đề này, người ta có thể giảm nhỏ các giá trị thay đổi quá lớn của thành phần mùa và bất thường bằng các phương pháp làm trơn. Tôi xin giới thiệu hai phương pháp làm trơn đơn giản gồm: phương pháp trung bình dịch chuyển (moving average) và phương pháp làm trơn bằng hàm số mũ (exponential smoothing methods) Phương pháp trung bình dịch chuyển Nội dung của phương pháp này là thay thế giá trị quan sát Xt bằng giá trị Xt* là giá trị trung bình của chính nó với m giá trị trước nó và m giá trị sau nó: * 1 2 1 m t t j j m X X m +=− = + ∑ (3.0) 30 * 1 1... ... 2 1 t m t m t t m t m t X X X X XX m − − + + − ++ + + + + += + (3.1) Xt*: là giá trị dịch chuyển của 2m + 1 điểm Ví dụ: nếu m = 2, giá trị trượt trung bình của 5 điểm là * 2 1 1 2 5 t t t t t t X X X X XX − − + ++ + + += (3.2) Nếu t = 3 thì: * 1 2 4 53 5t X X X X XX + + + += (3.3) Phương pháp làm trơn bằng hàm số mũ đơn giản Phương pháp làm trơn bằng hàm số mũ đơn giản được tiến hành dựa trên sự xem xét liên tục của các giá trị trong quá khứ, dựa trên trung bình có trọng số của chuỗi dữ liệu. Trọng số có giá trị càng nhỏ khi nó càng cách xa điểm dự báo.Với ý nghĩa như vậy ta có: Vậy ta có: (1 )t t tX X Xα α= + − với 0 1,α α≤ ≤ là hệ số làm trơn (3.4) 3.2. Dữ liệu chứng khoán Dữ liệu chúng ta sử dụng là dữ liệu thời gian thực (time series). Đặc điểm chính để phân biệt dữ liệu có phải là thời gian thực hay không đó chính là sự tồn tại của cột thời gian được đính kèm trong đối tượng quan sát [12, 17]. Nói cách khác, dữ liệu thời gian thực là một chuỗi các giá trị quan sát của biến Y: 31 Mục đích chính của việc phân tích chuỗi thời gian thực là thu được một mô hình dựa trên các giá trị trong quá khứ của biến quan sát y1, y2, y3, …, yt-1, yt cho phép ta có thể dự đoán được giá trị của biến Y trong tương lai, tức là có thể dự đoán được các giá trị yt+1, …., yn. Trong bài toán của chúng ta, dữ liệu chứng khoán được biết tới như một chuỗi thời gian đa dạng bởi có nhiều thuộc tính cùng được ghi tại một thời điểm nào đó. Với dữ liệu đang xết, các thuộc tính là: Open, High, Low, Close, Volume Open: Giá cổ phiếu tại thời điểm mở cửa trong ngày High: Giá cổ phiếu cao nhất trong ngày Low: Giá cổ phiếu thấp nhất trong ngày Close: Giá cố phiểu được niêm yết tại thời điểm đóng cửa sàn giao dịch Volume: Khối lượng giao dịch cổ phiếu (bán, mua) trong ngày 32 3.3. Mô hình dự báo tài chính Hình 3-3: Mô hình cây quyết định dự báo chứng khoán M: Số phần tử nhỏ nhất mà một nút lá có C: Ngưỡng dùng cho việc cắt tỉa Mô hình gồm hai quá trình sau: Tập huấn luyện Xây dựng mô hình â Cây quyết định Mô hình Cây quyết định Tập kiểm chứng M, C Đánh giá Mô hình tốt nhất Dữ liệu kiểm tra Dự đoán 33 Huấn luyện mạng (training): Đầu vào của cây quyết định là các thiết lập của các tham số ban đầu như số nhánh mà các nút lá có thể có, một ngưỡng nào đó để cắt tỉa cây, tập huấn luyện (training set),….Khi có được mô hình cây quyết định đã được huấn luyện, chúng ta đưa tập dữ liệu kiểm chứng vào để đánh giá mô hình vừa xây dựng được, đồng thời điều chỉnh các tham số của mô hình để thu được một mô hình cây quyết định tốt nhất phục vụ dự báo. Cắt nhánh nằm nâng cao khả năng dự đoán và phân lớp của cây quyết định Dự đoán (forecasting): Sau khi kết thúc quá trình 1, ta sẽ thu được một mô hình cây quyết định với các tham số tốt nhất. Khi đó, ta dùng bộ dữ liệu kiểm tra (testing set) để đưa ra giá trị dự báo cho thị trường chứng khoán 3.4. Thiết kế cây quyết định cho dữ liệu thời gian thực Không có một phương pháp chung nào để xác định cấu trúc phù hợp của cây quyết định cho từng bài toán. Việc thiết kế cây quyết định có thành hay không phụ thuộc vào sự hiểu biết rõ ràng về vấn đề, có thể dựa vào thực nghiệm hoặc kinh nghiệm trong lĩnh vực đó Tương tự như quá trình khai phá dữ liệu cơ bản, để đạt được kết quả trong khai phá và thành công trong việc phân tích dữ liệu thì khi thiết kế cây dữ liệu cũng thực hiện theo sáu bước sau 1. Tập hợp dữ liệu 2. Xử lý dữ liệu 3. Thiết lập tập huấn luyện, tập kiểm thử, tập kiểm tra 4. Mô hình hóa cây quyết định 5. Tiêu chuẩn đánh giá 6. Triển khai 3.4.1. Tập hợp dữ liệu Các dữ liệu về chứng khoán của các công ty có thể thu thập được khá nhiều nguồn như: trung tâm giao dịch chứng khoán Hà Nội (www.hastc.org.vn), Sở giao dịch chứng khoán HCM (www.hsx.com), và một số trang khác như : www.vietstock.com, www.finalcial.yahoo.com, www.cafef.vn. 34 3.4.2. Tiền xử lý dữ liệu Dữ liệu được xử lý trước khi đưa vào sử dụng trong mô hình. Như đã giới thiệu trong chương 2, ngoài số nút, số nhánh của cây, ta cần xác định đầu vào và đầu ra của cây. Với bài toán dự báo dữ liệu thời gian thực, đầu ra là giá trị dự đoán cho thời điểm t+1, đầu vào là giá trị k ngày trước đó (với k cho trước và tùy thuộc vào từng bài toán) t(n) t(-1) t(n-2) …. t(n-k) Với bài toán này, ta tổ chức dữ liệu thời gian lùi với các cột đầu là giá trị lần lượt của k ngày trước đó được sắp xếp lùi dần theo thời gian t và cột cuối cùng là dự đoán T1 T2 Tk Tk+1 Class t(1) t(2) … t(k) t(k+1) Tang/Giam t(2) t(3) … t(k+1) t(k+2) Tang/Giam t(3) t(4) … T(k+2) t(k+3) Tang/Giam … … … … … … t(n) t(n+1) … t(n +k) t(n+k + 1) Tang/Giam Hình 3-4: Tổ chức dữ liệu của mô hình Khi xử lý dữ liệu, chúng ta nên xây dựng một vài bộ dữ liệu để xây dựng mô hình và thay đổi các tham số khai phá để cố gắng xây dựng các mô hình tốt nhất hay hiệu quả nhất 3.4.3. Phân hoạch dữ liệu Sau khi chuẩn hóa dữ liệu, chúng ta chia dữ liệu thành hai tập: tập huấn luyện (training set), tập kiểm chứng (validation test). Hai tập dữ liệu này được để trên hai bảng khác nhau. Tập huấn luyện thường là tập lớn nhất chiếm khoảng 70% tập dữ liệu ban đầu sử dụng để huấn luyện mô hình. Tập kiểm chứng chiếm khoảng 30% tập dữ liệu ban đầu 35 dùng để đánh giá mô hình được chọn có thật sự tốt hay không và để tìm ra được tham số tốt nhất cho mô hình Hiện tượng overfiting xảy ra khi cây được tạo ra có thể quá khít với dữ liệu huấn luyện. Việc quá khít có thể xảy ra trong những trường hợp quá nhiều nhánh, một số có thể phản ánh sự dị thường vì những phần tử hỗn loạn (noise) hoặc những phần tử nằm ngoài phân lớp (outlier). Kết quả nhận được thiếu chính xác đối với những mẫu chưa thấy. Với cây quyết định, số nhánh và kích thước tập huấn luyện có ảnh hưởng quyết định đến nguy cơ overfiting [21]. Để ngăn chặn nguy cơ overfitting (hiện tượng khả năng học của mạng là rất tốt nhưng khả năng tổng quát hóa của mạng là kém, tức là mạng dự đoán tốt với những dữ liệu đã được huấn luyện nhưng lại tỏ ra kém hiệu quả khi dữ liệu mới vào mô hình) thì người ta phân chia tập huấn luyện thành tập dữ liệu huấn luyện (2/3) và dữ liệu thử nghiệm (1/3), sử dụng sự đánh giá chéo. Cũng có một cách khác là sử dụng tất cả dữ liệu để huấn luyện nhưng áp dụng kiểm tra thống kê để định lượng khi nào mở rộng hoặc tỉa bớt một nút để có thể cải thiện toàn bộ sự phân phối Dữ liệu kiểm chứng Dữ liệu huấn luyện Hình 3-5: Tỷ lệ kích thước của tập huấn luyện và tập kiểm chứng 36 3.4.4. Mô hình hóa cây quyết định Lựa chọn độ đo để tìm thuộc tính chia cắt tốt nhất Chỉ rõ độ đo dùng để đo sự không thuần nhất cho cây quyết định: entropy, gain hay gini. Thông thường các thuật toán trong cây quyết định đã trình bày trong mục 2.7 đều lựa chọn một độ đo nào đó để tìm một giá trị chia cắt tốt nhất. Ví dụ như ID3 chọn độ đo là entropy, C4.5 chọn độ đo Gain Ratio, CART chọn độ đo là gini…. Hầu như tất cả các thuật toán đều tính độ chia cắt trên tất cả các thuộc tính đầu vào, sau đó tùy từng độ đo để tìm một thuộc tính có giá trị thích hợp: gain lấy thuộc tính có giá trị lớn nhất, gini lấy thuộc tính có giá trị nhỏ nhất. .…. Số nhánh trên một nút lá Nếu số nhánh này càng lớn thì cây sinh ra sẽ rộng, chiều cao của cây sẽ giảm xuống và ngược lại. Thông thường, mọi người đặt giá trị này là 2 để đỡ phải tìm số nhánh phù hợp cho cây. Nhưng như thế, nó có thể làm cho sự tương tác trong dữ liệu kém đi, đối với những dữ liệu lớn có thể sẽ tạo ra một cây với kích thước lớn, làm giảm khả năng học của cây. Bohanec và Bratko (1994) [12] xây dựng một cây quyết định để quyết định xem vị trí nào của con cờ trắng trên bàn cờ là hợp pháp. Họ đã chứng minh được rằng, khi xây dựng cây quyết định với 4 nhánh thì độ chính xác là 98.45%, với 5 nhánh là 99.57%, với 11 nhánh thì độ chính xác là lớn nhất 100%. Như vậy, lớn gấp đôi về số nhánh nhưng độ chính xác chỉ nhỏ hơn dưới 0.5%. Ngưỡng sử dụng cho việc cắt tỉa Nếu giá trị này càng nhỏ thì cây sinh ra sẽ được cắt càng nhiều và sẽ không tiếp tục phân chia nếu số lượng bản ghi nhỏ hơn giá trị này. Mặc định giá trị này là 0.25 Cắt nhánh Tránh overfitting và làm giảm những nhánh thừa không ảnh hưởng đến kết quả phân lớp trên dữ liệu huấn luyện, chúng ta sử dụng cắt nhánh trong quá trình lớn lên của cây. Có hai giá trị để chọn là “true” hoặc “false”. Mặc định là cây được cắt nhánh 37 3.4.5. Tiêu chuẩn đánh giá Do sự phụ thuộc thời gian giữa các mẫu, các thủ tục đánh giá mô hình dự đoán thời gian thực sẽ khác nhau xuất phát từ mô hình chuẩn. Các mô hình gần đây thường được xây dựng dựa trên chiến lược tái lấy mẫu. Ví dụ như chiến lược kiểm chứng chéo (Cross- Validation) – là việc phân nhóm một mẫu dữ liệu thành các mẫu con để cho việc phân tích ban đầu chỉ dựa trên tập mẫu con đơn, còn các mẫu còn lại được giữ kín để dùng cho việc xác nhận và kiểm chứng lại lần phân tích đầu tiên đó, hoặc hoạt động bằng cách lấy mẫu ngẫu nhiên từ dữ liệu gốc chưa được sắp xếp. Mục đích của phương pháp luận này cho dữ liệu thời gian thực có thể dẫn tới những tình huống không mong muốn như sử dụng các mẫu quan sát ở tương lai cho các biến với mục đích huấn luyện, hoặc đánh giá mô hình với dữ liệu trong quá khứ. Để tránh những vấn đề này, tôi chia dữ liệu thành các cửa sổ thời gian, có được mô hình huấn luyện với thời gian trong quá khứ và kiểm tra nó với khoảng thời gian sau đó. Mục đích chính của bất kỳ chiến lược đánh giá nào là độ chính xác của mô hình dự đoán đạt được một giá trị đáng tin cậy nào đó. Nếu như sự đánh giá của chúng ta đáng tin cậy, chúng ta hoàn toàn có thể tin tưởng rằng giá trị dự đoán sẽ không lệch nhiều so với kết quả thực tế khi ta đưa dữ liệu mới vào mô hình Thiết lập thời gian khởi tạo t là thời gian bắt đầu giai đoạn kiểm chứng. Dữ liệu với thời gian trước t dùng để huấn luyện mô hình dự đoán, còn dữ liệu có được sau thời điểm t sẽ được sử dụng để kiểm chứng hiệu quả của mô hình đó Đầu tiên ta phải thu được mô hình đánh giá với dữ liệu trước thời điểm t và sau đó kiểm tra mô hình với dữ liệu sau thời điểm t. Chúng ta có thể sử dụng chiến lược cửa sổ, đầu tiên là Growing window [10]. 38 Hoặc có thể sử dụng Sliding window [10] Những hướng tiếp cận cửa sổ trên rất phù hợp khi chúng ta sử dụng dữ liệu mới vào để kiểm tra mô hình, thời gian khi đó là liên tục. Tuy nhiên chúng yêu cầu một lượng lớn mô hình. Mặc dù còn tồn tại những thay đổi trung gian, trong nghiên cứu này ta sẽ áp dụng chiến lược mô hình đơn để đơn giản quá trình kiểm tra mô hình. Tuy nhiên, chiến 1. Cho chuỗi Rh(1),Rh(2), . . . ,Rh(n) và thời gian t (t < n) 2. Xây dựng mô hình dự đoán với tập dữ liệu huấn luyện Rh(1),Rh(2), . . . ,Rh(t−1) 3. LẶP a. Dự đoán giá trị của Rh(t) b. Ghi lại tỉ lệ lỗi dự đoán c. Thêm Rh(t) vào tập huấn luyện d. Xây dựng mô hình mới với tập huấn luyện mới e. Đặt t = t + 1 4. ĐẾN KHI t = n 1. Cho chuỗi Rh(1),Rh(2), . . . ,Rh(n), thời gian t và kích thước cửa sổ w 2. Xây dựng mô hình với tập dữ liệu huấn luyện Rh(t−w−1), . . . ,Rh(t−1) 3. LẶP a. Dự đoán giá trị cho Rh(t) b. Ghi lại tỉ lệ lỗi dự đoán c. Thêm Rh(t) vào tập huấn luyện và xóa Rh(t−w−1) ra khỏi tập huấn luyện d. Xây dựng mô hình mới với tập huấn luyện mới e. Đặt t = t + 1 4. ĐẾN KHI t = n 39 lược cửa sổ có thể giúp ta đạt được những kết quả tốt hơn về sau, vì vậy với những ứng dụng thực tế, những điều này không nên bỏ qua. Khi có quyết định thiết lập thử nghiệm, ta vẫn phải chọn công thức tỉ lệ lỗi sẽ sử dụng để đánh giá mô hình. Đồng thời, chúng ta cũng phải đề cập đến những giới hạn lỗi tương quan như chuẩn trung bình bình phương sai số (root mean squared error – RMSE) [19], cung cấp chỉ số lỗi tương quan của mô hình được tính như trong công thức (3.5) Đặt At = Giá trị thực ở thời điểm t (quan sát t) Ft = Giá trị dự báo ở thời điểm t n = số lượng quan sát sử dụng trong dự báo 2( )t tA FRMSE n −= ∑ (3.5) Trong kỹ thuật phân tích dữ liệu thời gian thực (time series) sử dụng cây quyết định, có một phương pháp điển hình là sử dụng một ma trận nhầm lẫn (confusion matrix) [11] . Confusion matrix bao gồm số trường hợp phân lớp đúng, số trường hợp phân lớp sai trong mỗi lớp. Những trường hợp phân lớp đúng của mỗi lớp nằm trên đường chéo chính của ma trận còn những trường hợp khác sẽ là phân lớp sai trong mỗi lớp. Trong trường hợp chúng ta có 2 lớp thì kích cỡ của ma trân là 2 x 2 như hình vẽ dưới đây Giá trị thực sự Giá trị dự đoán Tăng Giảm Tăng Giảm m11 m12 m21 m22 m10 m20 m01 m02 m Hinh 3-6: Bảng ma trận 2 x 2 Trong đó: m là tổng số trường hợp dự đoán có trong tập dữ liệu m11 là số dự đoán lớp“Tăng” và m22 là số dự đoán lớp “Giảm” là đúng m12 là số dự đoán lớp “Tăng” và m21 là số dự đoán “Giảm” là sai 40 Dựa trên ma trân này, chúng ta có thể tính được các độ đo dùng để đánh giá mô hình như độ chính xác của mô hình cũng như tỷ lệ các nhãn đã dự đoán sai Độ chính xác (Accuracy): phần trăm số trường hợp dự đoán đúng Accuracy = 11 22 11 12 21 22 m m m m m m + + + + (3.6) Misclassification rate là tỷ lệ giữa các lớp dự đoán sai so với tổng số các trường hợp phân lớp Misclassification rate = 12 21 11 12 21 22 m m m m m m + + + + (3.7) 3.4.6. Triển khai Triển khai được coi như là bước cuối cùng của việc thiết kế mô hình cây quyết định, nhưng thực tế yêu cầu việc triển khai phải được chú ý trước khi tập hợp dữ liệu. Dữ liệu, tiêu chuẩn đánh giá, thời gian huấn luyện đều phải được định hướng trong mô trường mà cây quyết định sẽ triển khai. Hầu hết các nhà cung cấp phần mềm cây quyết định đều cung cấp một mô hình đã được huấn luyện trong chương trình hoặc trong file cấu hình. Nếu không có sẵn phần mềm, cây quyết định cũng có thể được tạo ra dễ dàng khi hiểu kiến trúc của nó, số nhánh tối thiểu trên một nút lá, một ngưỡng dùng để cắt tỉa cây… Một ưu điểm của mô hình cây quyết định là khả năng thích ứng với sự thay đổi của môi trường qua sự huấn luyện tuần hoàn. Khi mô hình được triển khai, hiệu năng của mô hình sẽ giảm dần nếu không được huấn luyện lại nhưng không có nghĩa hiệu năng sẽ được duy trì như các biến độc lập. Do đó phải thường xuyên huấn luyện lại mô hình trong suốt quá trình thử nghiệm trên mô hình cuối cùng 3.5. Tổng kết Mục đích của chương này là giới thiệu cách thiết kế một mô hình dự báo chứng khoán. Thiết kế gồm 6 bước: (1) Tập hợp dữ liệu, (2) xử lý dữ liệu, (3) phân hoạch dữ liệu, (4) mô hình hóa cây quyết định, (5) tiêu chuẩn đánh giá, (6) triển khai. Với cách thiết 41 kế chi tiết cho từng bước đã chỉ ra ở trên, bạn đọc có thể tự xây dựng mô hình cây quyết định cho ứng dụng của mình. Chương 4. Thực nghiệm 4.1. Môi trường thực nghiệm Mô hình được cài đặt bằng phần mềm weka.3.6.1 chạy trên nền hệ điều hành window 7, máy tính tốc độ corei3 2.13 GHz, bộ nhớ 2GB RAM Nói một cách ngắn gọn, weka là môi trường thử nghiệm khai phá dữ liệu do các nhà khoa học thuộc trường đại học waitako, là từ viết tắt của Waitako Environment for Knowledge Analysis, khởi xướng và được sự đóng góp của rất nhiều nhà nghiên cứu trên thế giới. Weka là một gói phần mềm mã nguồn mở được viết bằng ngôn ngữ java, cung cấp công cụ trực quan và sinh động cho sinh viên và người ngoài ngành công nghệ thông tin tìm hiểu về khai phá dữ liệu. Nó bao gồm một tập lớn các công cụ và thuật toán học máy dùng để phân tích và xây dựng mô hình dự đoán. Giao diện chính của weka có cho phép người dùng có thể chọn lựa 4 kiểu giao diện khác nhau để thao tác [1, 14] o Explorer : giao diện đồ họa, cho phép truy xuất vào tất cả tiện ích của nó bằng cách sử dụng trình lựa chọn và thay đổi các tham số o Knowledge Flow: cho phép thiết kế, cấu hình cho xử lý dòng dữ liệu. o Experimenter: cho phép tự động xử lý dễ dàng phân loại, lọc với các tham số khác nhau o Simlpe CLI: cho phép truy xuất thông qua các câu lệnh 42 Hình 4-0: Giao diện chính của weka Có thể tải phần mềm và tài liệu hướng dẫn tại trang web Trong khóa luận này này, tôi sử dụng giao diện CLI để thực nghiệm trên tập dữ liệu fpt_stock bởi các tính năng ưu việt mà weka cung cấp cũng như hỗ trợ giải thuật cây quyết định C4.5 4.2. Xây dựng cơ sở dữ liệu 4.2.1. Dữ liệu chứng khoán Dữ liệu tài chính của các công ty được niêm yết giá công khai trên các sàn giao dịch chứng khoán và trên internet. Có thể thu thập được dữ liệu tài chính của các công ty niêm yết giá trên sàn giao dịch ở khá nhiều trang như: trung tâm giao dịch chứng khoán Hà Nội (www.hastc.org.vn), Sở giao dịch chứng khoán HCM (www.hsx.com), và một số trang khác như: www.viestock.com, www.finalcial.yahoo.com, www.cafef.vn, Khóa luận đã thu thập được dữ liệu chứng khoán của sàn giao dịch chứng khoán HCM, dữ liệu giao dịch của công ty fpt từ năm 2008 đến 31/3/2010. Ta sẽ sử dụng chỉ số vnindex thu thập được từ năm 2008 đến năm 2010 của công ty fpt để tiến hành thực nghiệm mô hình Sau khi xử lý dữ liệu, loại bỏ các thông tin nhiễu, thiếu thông tin và không cần thiết. Dữ liệu có thể được lưu trong một file txt hoặc csv. 4.2.2. Xây dựng dữ liệu cho mô hình Dữ liệu thu được từ các sàn giao dịch chứng khoán bao gồm rất nhiều thông tin như giá mở cửa (open), giá đóng cửa (close), giá cao nhất trong ngày (high), giá thấp nhất (low), khối lượng giao dịch (volume)…Tất cả các thông tin đều trợ giúp một phần khi xây 43 dựng mô hình dự báo nhưng để đơn giản trong khóa luận tôi chỉ sử dụng giá đóng cửa trong các phiên giao dịch. Hình 4-1: Dữ liệu chứng khoán thu được từ sàn chứng khoán Để đảm bảo tính ngẫu nhiên của dữ liệu và tránh tình trạng sử dụng dữ liệu của tương lai để huấn luyện hoặc dữ liệu của quá khứ để kiểm chứng mô hình. Tôi chia bộ dữ liệu của năm 2008-2010 thành 10 bộ dữ liệu, mỗi bộ dữ liệu gồm 12 tháng khác nhau lấy một cách ngẫu nhiên tuần tự dùng để huấn luyện mô hình và lấy dữ liệu của 3 tháng kế tiếp để làm tập dữ liệu kiểm chứng. Tôi đã viết một chương trình bằng C/C++ để lấy giá đóng cửa của các phiên giao dịch trong các bộ dữ liệu và chuyển về dữ liệu dưới dạng ma trận như đã trình bày ở mục 3.4.2 44 Đầu vào của chương trình là các file dữ liệu sau khi đã tách ra từng bộ dữ liệu có dạng như sau: (a) 45 (b) Hình 4-2: (a) Một trong số những dữ liệu huấn luyện từ 1/2008-12/2008 (b) Một trong số những bộ kiểm chứng từ 1/2009-3/2009 Chương trình sẽ lấy giá đóng cửa của các phiên giao dịch sau đó chuyển về dữ liệu dưới dạng bảng với các T1, T2, …., T20 là giá cổ phiếu của 20 ngày giao dịch trong quá khứ, T1 là ngày gần với ngày cần dự đoán nhất, rồi tính toán xem với các giá cổ phiếu trong giai đoạn được đưa ra ấy tăng hay giảm và đưa ra kết luận ở trường Class ở file đầu ra. File đầu ra được lưu dưới định dạng .csv có dạng Hình 4-3: Một trong những file dữ liệu đầu ra của chương trình Sau khi xử lý xong dữ liệu, ta đưa dữ liệu vào trong weka. Weka CLI cung cấp một số lệnh để đọc hoặc chuyển sang định dạng chuẩn mà gói weka thường xử lý (.arff), các lệnh đó là: Weka.core.converters.CSVLoader: đọc dữ liệu có định dạng CSV Weka.core.converters.C45Loader: đọc dữ liệu có định dạng C4.5 46 Hình 4-4: Lệnh đọc file CSV và chuyển thành file ARFF Sau khi thực hiện những câu lệnh này, dữ liệu trong file csv được đưa vào trong weka và chuyển sang định sạng .arff để sử dụng cho việc huấn luyện mô hình. Hình sau mô tả dữ liệu sau khi đã đưa vào trong weka - java weka.core.converters.CSVLoader F:\fpt_train_1.csv > F:\fpt_train_1.arff - java weka.core.converters.CSVLoader F:\fpt_validation_1 > F:fpt_validation_1.arff - …… 47 Hình 4-5: Dữ liệu dưới định dạng arff trong weka Dữ liệu này khi đưa vào mô hình cây quyết định sẽ dự báo giá đóng cửa của ngày hôm sau phụ thuộc vào 20 ngày trước đó. 4.3. Thực nghiệm mô hình cây quyết định cho dữ liệu thời gian thực Với bài toán dự báo thị trường chứng khoán, có hai cách xây dựng mô hình cây quyết định như sau: Một là, ta xây dựng mô hình với mục đích dự đoán giá cổ phiếu của ngày thứ t+1 tăng hay giảm khi biết giá cố phiếu của n ngày trước đó: t, t-1, t-2, …., t-n+1. Sau đó dựa 48 vào kết quả dự báo này như một gợi ý để nhà đầu tư đưa ra các quyết định giao dịch của riêng mình Hai là, ta xây dựng hệ thống đoán nhận giúp người dùng đưa ra quyết định trực tiếp. Theo hướng tiếp cận này, ta sẽ có tập mẫu các giá trị đầu ra: “mua”, “bán”, “giữ lại”. Hệ thống sẽ đoán nhận ngày thứ t+1 sẽ thuộc giao dịch nào, nó giống như bài toán phân loại mẫu vậy. Thị trường chứng khoán là thị trường rất nhạy cảm và bị tác động bởi nhiều yếu tố, với dữ liệu thu thập được và thời gian hạn hẹp, khóa luận chọn hướng tiếp cận đầu tiên cho nghiên cứu của mình 4.3.1. Mô hình dự báo tài chính thời gian thực Sử dụng dữ liệu đã được xây dựng sẵn ở trên, dùng các tập huấn luyện fpt_train_1.arff, fpt_train_2.arff, …., fpt_train_10.arff để huấn luyện mô hình và các tập kiểm tra tương ứng fpt_validatoion_1.arff, ……,fpt_validation_10.arff để kiểm thử mô hình. Ta sử dụng lệnh phân lớp dùng cây quyết định với 10 bộ dữ liệu đã xử lý để thu được mô hình dự báo giá chứng khoán như sau: - Bộ dữ liệu thứ 1 java weka.classifiers.trees.J48 –C 0.25 –M 2 –t F:\fpt_train_1.arff -d F:\fpt_1.model - Bộ dữ liệu thứ 2 java weka.classifiers.trees.J48 –C 0.25 –M 2 –t F:\fpt_train_2.arff -d F:\fpt_2.model - …. - Bộ dữ liệu thứ 10 java weka.classifiers.trees.J48 –C 0.25 –M 2 –t F:\fpt_train_10.arff -d F:\fpt_10.model 49 Hình 4-6: Lệnh huấn luyện dữ liệu Trong các lệnh huấn luyện trên, tôi cung cấp tập dữ liệu đầu vào là các tập huấn luyện đã xử lý fpt_train_1.arff, fpt_train_2.arff, ….fpt_train_10.arff và các tập kiểm chứng fpt_validatoion_1.arff, ……, fpt_validation_10.arff với các tham số mặc định của phân lớp bằng cây quyết định trong weka. Số phần tử nhỏ nhất trên một nút lá (-M) là 2 và ngưỡng sử dụng cho việc cắt tỉa (-C) là 0.25. Kết quả của quá trình phân lớp được lưu ra các file như fpt_1.model, fpt_2.model, …., fpt_10.model. Tập hợp kết quả của các lần huấn luyện, ta có bảng sau Tập dữ liệu Thời gian xây dựng mô hình (s) Accuracy (%) Missclassification (%) fpt_train_1 0.03 98.2063 1.7937 fpt_train_2 0.02 98.6175 1.3825 fpt_train_3 0.03 97.7578 2.2422 fpt_train_4 0.03 98.2063 1.7937 fpt_train_5 0.02 99.1071 0.8929 fpt_train_6 0.02 99.1189 0.8811 fpt_train_7 0.02 99.1228 0.8772 fpt_train_8 0.02 99.1228 0.8772 fpt_train_9 0.02 97.807 2.193 fpt_train_10 0.02 97.8261 2.1739 Kết quả trung bình 0.023 98.4893 1.5107 Hình 4-7: Kết quả qua các lần huấn luyện Kết quả này cho chúng ta biết, độ chính xác của các trường hợp phân lớp trên tập dữ liệu huấn luyện trung bình là 98.4893% và có 1.5107% các trường hợp phân lớp sai. Thời gian trung bình để huấn luyện các mô hình là 0.023s 50 4.3.2. Đánh giá mô hình Chúng ta thường quan tâm xem xét độ chính xác trong dự đoán xu hướng của thị trường chứng khoán. Ví dụ như giá trị dự đoán của một ngày sau tăng hay giảm. Như đã giới thiệu trong mục 3.4.5, chúng ta sử dụng ma trận nhầm lẫn (confusion matrix) để tính cách độ đo như độ chính xác (accuracy), misclassification. Ta sử dụng Accuracy để ước lượng độ chính xác của mô hình trong việc dự đoán thị trường chứng khoán là tăng hay giảm. Misclassfication sử dụng cho những dự đoán sai so với dữ liệu thực tế Trong weka CLI, sau khi huấn luyện mô hình thông qua tập training, chúng ta cung cấp các tập kiểm chứng vào mô hình huấn luyện để xác định Accuracy và misclassification Hình 4-8: Lệnh đánh giá dựa trên tập kiểm chứng Kiểm thử mô hình với 10 bộ dữ liệu kiểm chứng và 10 mô hình đã xây dựng được chúng ta có kết quả đánh giá trên tập kiểm chứng như sau: - Bộ dữ liệu thứ 1 java weka.classifiers.trees.J48 -l F:\fpt_1.model –T F:\fpt_validation_1.arff - Bộ dữ liệu thứ 2 java weka.classifiers.trees.J48 –l F:\fpt_2.model –T F:\fpt_validation_2.arff - …. - Bộ dữ liệu thứ 10 java weka.classifiers.trees.J48 –l F:\fpt_10.model–T F:\fpt_validation_10.arff 51 Tập kiểm chứng Accuracay (%) Misclassification (%) fpt_validation_1 48.6486 51.3514 fpt_validation _2 85.3659 14.6341 fpt_validation _3 90.2439 9.7561 fpt_validation _4 100 0 fpt_validation _5 93.3333 6.6667 fpt_validation _6 93.4783 6.5217 fpt_validation _7 100 0 fpt_validation _8 100 0 fpt_validation _9 79.5455 20.4545 fpt_validation _10 58.6957 41.3043 Kết quả trung bình 84.9311 15.0689 Hình 4-9: Kết quả đánh giá trên tập kiểm chứng Từ kết quả trên ta thấy rằng, hiệu năng của mô hình cây quyết định không phải là hằng số, nó thay đổi với các bộ dữ liệu khác nhau hay nói cách khác nó thay đổi theo các tháng khác nhau 4.3.3. Lựa chọn mô hình tốt nhất Trong các phần trước, khóa luận đã xây dựng một một vài mô hình hồi quy có thể được sử dụng để dự đoán giá đóng cửa của chỉ số vnindex một ngày sau thời điểm t nào đó. Đồng thời, khóa luận cũng đã đưa ra một vài đại lượng nhằm đánh giá mô hình. Khi có được đánh giá cho các mô hình, bài toán sử dụng mô hình tốt nhất để dự báo Chúng ta không cần thiết phải sử dụng các loại mô hình khác nhau. Đó có thể là các mô hình với cùng kỹ thuật khai phá dữ liệu nhưng các tham số khi sử dụng lại khác nhau. Ví dụ như mô hình cây quyết định được giới thiệu ở trên, có ít nhất hai tham số tham có thể tác động: số nút nhỏ nhất trên một nút lá, nhân tố dùng để chia cắt . Những thiết lập tham số khác nhau dẫn đến các mô hình cây quyết định khác nhau. Câu hỏi đặt ra là làm thế nào có được bộ tham số tốt nhất là một vấn đề lựa chọn mô hình. 52 Chúng ta đã mô tả một vài hệ số thống kê có thể đánh giá mô hình dự đoán chứng khoán. Tuy nhiên, các thiết lập thử nghiệm để đánh giá mô hình lại có vai trò quyết định. Việc thiết lập này bao gồm việc chia dữ liệu thành hai phần: huấn luyện và thử nghiệm. Để lựa chọn mô hình, ta sẽ phân chia tập huấn luyện thành hai phần: một phần để lấy được các tập tham số của mô hình (tập train) và một phần khác để chọn ra tập tham số tốt nhất (tập kiểm chứng –validation set). Sau khi có được bộ tham số tốt nhất này, chúng ta sẽ xây dựng được mô hình tốt nhất. Sử dụng mô hình này cho toàn bộ tập huấn luyện (training set), kể cả phần dữ liệu kiểm chứng (validation set) Đầu tiên ta minh họa chiến lược lựa chọn mô hình bằng cách sử dụng nó để tìm ra những thiết lập ban đầu tốt nhất cho từng kỹ thuật khai phá dữ liệu riêng biệt. Tất cả các kỹ thuật khai phá dữ liệu đều có một vài biến bạn có thể thay đổi để có được kết quả tốt nhất. Thậm chí có một vài công cụ còn tự động thay đổi các biến này để có kết quả tốt nhất Trong bài toán này, ta sẽ thiết lập một số thay đổi cho hai biến minNumObj (-M) và confidenceFactor (-C) của cây quyết định. • minNumObj (-M) là nhánh tối thiểu trên một nút lá, nếu giá trị này càng lớn thì cây bị cắt thành nhiều nhánh. Mặc định trong weka CLI là 2 • confidenceFactor (-C) là một ngưỡng sử dụng cho việc cắt tỉa, nếu giá trị này nhỏ thì cây sinh ra sẽ được cắt càng nhiều. Mặc định trong weka CLI là 0.25 Trong luận văn này, tôi tiến hành thay đổi các tham số -M và -C với 10 bộ dữ liệu huấn luyện kết hợp với tập kiểm chứng để tìm ra các độ chính xác (Accuracy) và chuẩn trung bình bình phương sai số (root mean squared error) để đánh giá mô hình thu được. Mô hình cho kết quả tốt nhất là mô hình có độ chính xác là lớn nhất và hệ số RMSE là nhỏ nhất Bộ tham số (C, M) Accuracy (%) RMSE (0.01, 1) 89.12427 0.25059 (0.01, 2) 89.12427 0.25964 53 (0.01, 3) 79.12427 0.34199 (0.01, 4) 78.03731 0.35424 (0.01,5) 77.81004 0.35634 (0.01, 7) 72.25953 0.41067 (0.01, 10) 66.57771 0.44587 (0.05, 1) 89.12427 0.25053 (0.05, 2) 89.12427 0.25958 (0.05, 3) 89.12427 0.28272 (0.05, 4) 89.12427 0.28272 (0.05, 5) 88.897 0.28488 (0.05, 7) 83.34649 0.34549 (0.05, 10) 66.57771 0.44592 (0.1, 1) 89.12427 0.25072 (0.1, 2) 89.12427 0.25977 (0.1, 3) 89.12427 0.28272 (0.1, 4) 89.12427 0.28272 (0.1, 5) 88.897 0.28482 (0.1, 7) 83.34649 0.34549 (0.1, 10) 66.57771 0.44592 (0.25, 1) 88.07164 0.271 (0.25, 2) 88.0716 0.28005 (0.25,3) 90.0334 0.25026 (0.25,4) 89.8061 0.2782 (0.25,5) 89.5788 0.2803 (0.25,7) 83.3465 0.34612 54 (0.25,10) 66.5777 0.44592 (0.4,1) 88.0716 0.271 (0.4,2) 88.0716 0.2827 (0.4,3) 89.8061 0.2557 (0.4,4) 89.8061 0.27823 (0.4,5) 89.5788 0.28033 (0.4,7) 83.3465 0.3461 (0.4,10) 66.0857 0.4524 (0.5,1) 88.0716 0.271 (0.5,2) 88.0716 0.28271 (0.5,3) 89.8061 0.25572 (0.5,4) 89.1539 0.281 (0.5,5) 88.9266 0.2831 (0.5,7) 83.3465 0.3461 (0.5,10) 66.0857 0.45237 Hình 4-10: Kết quả khi thay đổi các tham số -C, -M Thiết lập tham số -C với các giá trị 0.01, 0.05, 0.1, 0.25, 0.4, 0.5, tham số -M với các giá tri 1, 2, 3, 4, 5, 7, 10 kết quả thu được trên hình 4-10, các kết quả không khác xa nhau là mấy chỉ trừ các bộ tham số có số nhánh là 7 và 10 thì kết quả bị lệch nhiều. Kết quả có accuracy lớn nhất là 90.0334 và RMSE nhỏ nhất là 0.25026 ứng với C = 0.25 và M = 3 Như vậy ta đã tìm ra bộ tham số tốt nhất với C=0.25, M=3, xây dựng lại mô hình cây quyết định với bộ tham số ở trên ta thu được kết quả như sau 55 Tập dữ liệu Thời gian huấn luyện (s) Accuracy trên tập huấn luyện (%) Accuracy trên tập kiểm chứng(%) RMSE fpt_train_1 0.03 97.8571 100 0 fpt_train _2 0.05 98.9209 93.3333 0.2582 fpt_train _3 0.03 98.5915 93.4783 0.2597 fpt_train _4 0.04 99.2982 100 0.1267 fpt_train _5 0.03 97.9239 100 0 fpt_train _6 0.03 97.9522 81.8182 0.3859 fpt_train _7 0.04 96.587 63.0435 0.5853 fpt_train _8 0.03 96.2329 81.8182 0.4134 fpt_train _9 0.04 97.2603 89.4737 0.3135 fpt_train _10 0.04 96.6216 97.3684 0.1599 Trung bình 0.029 97.7246 90.0334 0.25026 Hình 4-11: Kết quả khi huấn luyện lại mô hình với tham số tốt nhất Khi xây dựng mô hình với bộ tham số tốt nhất thì độ chính xác trên tập kiểm chứng tăng 5.1023% so với độ chính xác của tập kiểm chứng khi huấn luyện mô hình với tham số mặc định 4.4. Một số mô hình khác Trong khai phá dữ liệu có nhiều kỹ thuật để xây dựng mô hình dự đoán khác nhau, mỗi kỹ thuật đều có những thiết lập, hỗ trợ và điểm mạnh riêng. Mục đích chính của tất cả các phương pháp là dự đoán giá trị của tương lai sử dụng dữ liệu của quá khứ. Vậy sử dụng phương pháp nào sẽ cho mô hình dự đoán tốt nhất ?. Trong khóa luận này tôi xin giới hiệu hai mô hình của hai kỹ thuật khác cho bài toán của mình, và lấy kết quả để đánh giá với mô hình cây quyết định mà tôi đã xây dựng 56 trong những phần trước để thấy được kỹ thuật nào là tốt cho dự đoán. Ta sử dụng dữ liệu vnindex đã qua xử lý ở phần trước, kết quả của hai mô hình này tương ứng với kết quả trung bình trên 10 bộ dữ liệu kiểm chứng (validation set) như trong mô hình cây quyết định ở trên để thuật lợi cho việc đánh giá. Đồng thời sử dụng độ chính xác (Accuracy), RMSE và thời gian huấn luyện để đánh giá kết quả giữa các mô hình 4.4.1. Mô hình mạng nơ ron Mạng nơ ron là một trong những phương pháp mô hình hóa tập trung vào các bài toán phi tuyến, do đó được lựa chọn nhiều trong bài toán dự báo tài chính. Mạng nơ ron là mạng các phần tử (gọi là nơ ron) kết nối với nhau thông qua các liên kết (gọi là trọng số liên kết) để thực hiện một công việc cụ thể nào đó [7] Mạng nơ ron có thể được xem như là một mô hình toán học: Y = F(X) với X là vector số liệu vào và Y là vector số liệu ra. Chỉ cần đưa vào mạng một tập hợp mẫu dữ liệu, trong quá trình học thì mạng có khả năng phát hiện những đặc trưng, rằng buộc này trong quá trình sử dụng mạng Mạng nơ ron thực hiện nhiệm vụ của mình thông qua các thao tác: nhận đầu vào từ các nơ ron trước nó, xử lý đầu vào bằng cách nhân mỗi đầu vào này với trọng số liên kết tương ứng và tính tổng các tích thu được rồi đưa qua một hàm truyền, sau đó gửi kết quả cuối cùng cho các nơ ron tiếp theo hoặc đưa ra output Khả năng học của mạng nơ ron chủ yếu dựa trên kỹ thuật lan truyền ngược sai số (backpropagation). Việc huấn luyện mạng với thuật toán lan truyền ngược sai số gồm hai pha ngược chiều nhau: quá trình truyền thẳng (lan truyền xuôi) và quá trình lan truyền ngược 57 (a) (b) Hình 4-12: (a) Cấu trúc một nơ ron (b) Cấu trúc mạng nơ ron Khi huấn luyện mạng trong weka, có ba tham số chính làm thay đổi độ chính xác của mô hình huấn luyện là Số vòng lặp (training time): tỷ lệ thuận với hiệu suất của mạng nhưng đến một mức nào đó nó sẽ gây ra hiện tượng học vẹt (over learning) sẽ bỏ qua trạng thái tối ưu. Giá trị mặc định trong weka là 500. Số lớp ẩn (hiddenLayers):được tính theo công thức a = (số trường hợp + số lớp) / 2 Tốc độ học (learningRate): cũng ảnh hưởng đến hiệu suất của mạng đối với số vòng lặp xác định. Giá trị tham số này càng nhỏ thì mạng hiệu chỉnh trọng số càng chậm. Nhưng muốn đạt đến trạng thái tối ưu thì ta phải tăng số vòng lặp nhiều hơn. Giá trị mặc định trong weka là 0.3 Như vậy, ta sẽ xây dựng mô hình mạng với các giá trị của các tham số: tốc độ học = 0.7, số vòng lặp 600, số tầng ẩn a 58 Tập dữ liệu Thời gian huấn luyện (s) Accuracy trên tập huấn luyện (%) Accuracy trên tập kiểm chứng (%) RMSE NR DS NR DS NR DS NR DS fpt_train_1 4.69 0.03 96.0714 97.857 1 100 100 0.0256 0 fpt_train_2 4.07 0.05 97.1223 98.920 9 93.3333 93.333 3 0.2398 0.2582 fpt_train_3 4.18 0.03 96.831 98.591 5 93.4783 93.478 3 0.2517 0.2597 fpt_train_4 4.51 0.04 97.193 99.298 2 100 100 0.0072 0.1267 fpt_train_5 4.4 0.03 95.1557 97.923 9 100 100 0 0 fpt_train_6 4.6 0.03 96.9283 97.952 2 84.0909 81.818 2 0.3857 0.3859 fpt_train_7 4.48 0.04 96.587 96.587 73.913 63.043 5 0.4832 0.5853 fpt_train_8 4.29 0.03 97.2603 96.232 9 77.2727 81.818 2 0.4746 0.4134 fpt_train_9 4.39 0.04 96.5753 97.260 3 89.4737 89.473 7 0.3242 0.3135 fpt_train_1 0 4.37 0.04 97.973 96.621 6 97.3684 97.368 4 0.1621 0.1599 trung bình 4.398 0.029 96.7697 97.724 6 90.8930 3 90.033 4 0.23541 0.2502 6 59 Hình 4-13: So sánh kết quả giữa Mạng nơ ron và cây quyết định Từ công thức ( 3-5), ta thấy rõ: mẫu số của biểu thức là không đổi. Độ lệch chuẩn bình phương (RMSE) nhỏ hơn tức là giá trị dự đoán gần với giá trị thực sự của dữ liệu hơn. Với cùng các bộ dữ liệu, nếu dựa vào kết quả trung bình thì ta sẽ thấy rằng mô hình mạng nơ ron có hệ số RMSE nhỏ hơn mô hình cây quyết định một lượng là 0.01519 nhưng nhìn trên từng bộ dữ liệu thì có tới 5 bộ dữ liệu khi huấn luyện bằng cây quyết định có hệ số RMSE cao hơn khi huấn luyện bằng mạng nơ ron và 1 bộ dự liệu có RMSE ở cả hai mô hình bằng nhau. Xét về thời gian xây dựng mô hình thì cây quyết định đưa ra mô hình nhanh gấp 151 lần so với mạng nơ ron, độ chính xác khi phân lớp trên tập huấn luyện sử dụng cây quyết định cũng cao hơn so với mạng nơ ron. 4.4.2. Mô hình SVM (support vector machine) SVM là một phương pháp máy học tương đối mới nhiều ứng dụng thành công trong lĩnh vực khai phá dữ liệu đặc biệt là trong bài toán dự báo thời gian thực. SVM được nhận định là phương pháp phân lớp nhanh, giải quyết vấn đề overfiting rất tốt và có thể xử lý hiệu quả với bài toán dữ liệu có số chiều lớn Tư tưởng chính của SVM là chuyển tập mẫu từ không gian biểu diễn Rn của chúng sang một không gian Rd có số chiều lớn hơn. Trong không gian Rd, tìm một số siêu phẳng tối ưu để phân hoạch tập mẫu này dựa trên phân lớp của chúng, cũng có nghĩa là tìm ra miền phân bố của từng lớp trong không gian Rn để từ đó xác định được phân lớp của một mẫu cần dự đoán Khi xây dựng mô hình với SVM, chúng ta cần phải chọn các tham số tốt nhất cho thuật toán. SMO (Sequential minimal optimization) - thuật toán tối ưu tuần tự là thuật toán tối ưu dành riêng cho phương pháp SVM do J.Platt đưa ra vào năm 1988. Thuật toán có 3 tham số làm thay đổi độ chính xác của mô hình [8] Hệ số phức tạp (Complexity factor): Quyết định sự cân bằng giữa lỗi tối thiểu của mô hình trên dữ liệu huấn luyện và trên mô hình phức tạp. Giá trị mặc định trong weka là C = 1.0. Để đẩm bảo tính ổn định của quá trình huấn luyện, giá tri của tham số C càng lớn càng tốt, ví dụ C = 100 [8]. 60 Epsilon: là một thiết lập SVM ứng dụng để xây dựng mô hình hồi quy. Giá trị của epsilon ảnh hưởng đến số lượng vector hỗ trợ vì vậy gián tiếp ảnh hưởng đến sự cân bằng giữa mô hình phức tạp và tổng quát. Dung sai: độ lệch lớn nhất của một tiêu chuẩn hội tụ. Nếu giá trị này lớn thì quá trình xây dựng mô hình sẽ nhanh hơn nhưng độ chính xác sẽ thấp hơn. Giá trị mặc định là 0.001 Ta sẽ xây dựng mô hình SVM với các thiết lập tham số C = 100, P (epsilon) = 1.0E- 12, L (dung sai) = 0.001 Tập dữ liệu Thời gian huấn luyện Accuracy trên tập huấn luyện(%) Accuracy trên tập kiểm chứng (%) RMSE SVM DS SVM DS SVM DS SVM DS fpt_train_1 0.35 0.03 89.6429 97.8571 100 100 0 0 fpt_train_2 0.21 0.05 91.3669 98.9209 93.3333 93.3333 0.2582 0.2582 fpt_train_3 0.14 0.03 91.9014 98.5915 93.4783 93.4783 0.2554 0.2597 fpt_train_4 0.05 0.04 97.193 99.2982 100 100 0 0.1267 fpt_train_5 0.15 0.03 95.8478 97.9239 100 100 0 0 fpt_train_6 0.11 0.03 95.9044 97.9522 75 81.8182 0.5 0.3859 fpt_train_7 0.06 0.04 95.9044 96.587 65.2174 63.0435 0.5898 0.5853 fpt_train_8 0.07 0.03 95.8904 96.2329 84.0909 81.8182 0.3989 0.4134 fpt_train_9 0.25 0.04 92.8082 97.2603 89.4737 89.4737 0.3244 0.3135 fpt_train_10 0.21 0.04 92.9054 96.6216 97.3684 97.3684 0.1622 0.1599 trung bình 0.16 0.029 93.9365 97.7246 89.796 90.0334 0.24889 0.25026 Hình 4-14: So sánh kết quả giữa mô hình SVM và cây quyết định Xét về thời gian xây dựng mô hình, độ chính xác (Accuracy) trên tập huấn luyện, và trên tập kiểm chứng thì mô hình cây quyết định đều cao hơn so với SVM. Riêng có hệ số 61 RMSE thì khi nhìn vào kết quả trung bình ta có thể thấy mô hình SVM có kết quả thấp hơn so với mô hình cây quyết định là 0.00137 nhưng xét trên từng tập dữ liệu thì có tới 5 bộ dữ liệu khi sử dụng mô hình cây quyết định thì kết quả RMSE cao hơn so với SVM và có tới 2 bộ dữ liệu có kết quả bằng nhau khi sử dụng mô hình cây quyết định và mô hình SVM Như vậy, về cơ bản thì mô hình cây quyết định là một mô hình tương đối tốt đối với dữ liệu thời gian thực. Độ chính xác khi xây dựng mô hình trên tập huấn luyện rất cao, cao hơn hẳn mô hình mạng nơ ron và SVM và thời gian xây dựng mô hình rất rất nhanh giúp nhà đầu tư có nhiều thời gian suy nghĩ trước khi quyết định hơn. Phần lớn các bộ dữ liệu có kết quả dự đoán gần với giá trị thực hơn so với mô hình mạng nơ ron và SVM 62 Kết luận Kết quả đạt được của luận văn Khai phá dữ liệu hiện nay là một hướng nghiên cứu còn khá mới mẻ, thu hút sự quan tâm không chỉ của giới CNTT mà còn của nhiều ngành khoa học khác. Ngày nay có nhiều phương pháp và các thuật toán kinh điển, tạo nên một bức tranh hết sức sôi động về lĩnh vực nghiên cứu còn khá mới mẻ này. Thông qua việc tìm hiểu, tiếp thu những kiến thức cơ bản và kết quả của một số công trình nghiên cứu mới được công bố gần đây, tôi đã trình bày một cách tương đối đầy đủ và có hệ thống về các vấn đề liên quan đến khai phá dữ liệu nói chung và khai phá dữ liệu bằng cây quyết định nói riêng. Áp dụng khai phá dữ liệu bằng cây quyết định vào bài toán dự báo xu thế thị trường chứng khoán, trong khóa luận tôi đã lấy giá đóng cửa qua các phiên giao dịch của công ty fpt để làm thực nghiệm. Đặc biệt đã đi sâu phân tích, đánh giá và so sánh với một số phương pháp khác Tuy nhiên do việc hạn chế về thời gian, kinh nghiệm nên kết quả thực nghiệm vẫn chưa thực sự thuyết phục, mặc dù phương pháp và kỹ thuật mà luận văn trình bày là hoàn toàn khả thi, đó chính là điểm hạn chế của luận văn này Hướng nghiên cứu tiếp theo Khai phá dữ liệu nói chung và khai phá dữ liệu bằng cây quyết định nói riêng hiện nay vẫn là vấn đề nghiên cứu và triển khai mang tính thời sự. Những vấn đề dưới đây sẽ là nội dung nghiên cứu tiếp theo của luận văn này