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
ĐẠ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
ĐẠ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
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
i
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….
ii
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.
1.4.
Bài toán dự báo xu thế thị trường chứng khoán...........................................9
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
iii
2.1.
2.2.
2.3.
2.4.
Định nghĩa ..................................................................................................12
Cấu trúc ......................................................................................................12
Các kiểu cây quyết định .............................................................................13
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
Rút ra quy tắc phân lớp từ cây quyết định..................................................18
Các thuật toán trong cây quyết định...........................................................19
Quá trình tạo cây quyết định ......................................................................21
2.6.
2.7.
2.8.
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
Mô hình dự báo tài chính............................................................................32
Thiết kế cây quyết định cho dữ liệu thời gian thực....................................33
3.3.
3.4.
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
iv
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.
4.2.
Môi trường thực nghiệm.............................................................................41
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
v
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
vi
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
vii
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
1
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
2
-
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
3
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
4
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
Thuật toán phân lớp
Mô hình
Dữ liệu học
phân lớp
Hình 1-0: Bước 1 Học để xây dựng mô hình phân lớp
5
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
Mô hình phân lớp
Dữ liệu mới
Dữ liệu kiểm chứng
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)
6
Thuật toán phân lớp
Quy tắc phân lớp
Dữ liệu huấn
luyện
Tên
Tuổi
Thu nhập
Đánh giá
tiền gửi
Tốt
Sandy Jones
Bill Lee
<=30
<=30
Thấp
Thấp
Rất tốt
Rất tốt
Tốt
Nếu tuổi = “31…40” và
thu nhập = “cao” đánh
giá tiền gửi = “rất tốt”
Coutnay fox
Susan Lake
Claire Phips
…….
31….40 Cao
>40
Trung bình
31….40 Trung bình
Tốt
….
……
…..
Hình 1-2: Ví dụ về học mô hình
Dữ liệu kiểm
Quy tắc phân lớp
Tên
Tuổi
Thu nhập Đánh
tiền gửi
Cao Tốt
giá
Dữ liệu mới
Frank Jones >40
Sylvia Crest <=30
John Henri, 31…40
Thấp
Cao
…..
Tốt
High Đánh giá tiền gửi?
Anne Yee
…..
31….40
……
Rất tốt
……
Rất tốt
Hình 1-3 : Ví dụ về phân lớp dữ liệu
7
“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ị
8
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
d p x
dxp
= f (x, x',..., x( p−1)
)
(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
d2 x
dt2
dx
= f (x, )
dt
(1.1)
9
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:
d2x
dt2
x(j+1)−2x(j)+x(j−1)
|j =
+o(h2)
(1.2)
(1.3)
h2
dx
dt
x( j) − x( j − 1)
| j =
+ o(h)
h
Từ đó ta có được hàm sau
x(j)−x(j−1)
⎡
⎤
x(j+1)=h2 f x(j),
+2x(j)−x(j−1)+o(h3)
(1.4)
⎢
⎣
⎥
⎦
h
Có thể viết hàm trên thành một hàm tổng quát sau:
x(j+1)=F(x(j),x(j−1),h)
(1.5)
(1.6)
Tổng quát hóa đến phần tử thứ p, ta có hàm tổng quát sau:
x(j+1)=F(x(j),x(j−1),....,x(j−p+1),h)
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ở
10
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
11
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
Nút gốc
Nút trong
Nút lá
Nút lá
Nút lá
Hình 2-0: Biểu diễn cấu trúc cây quyết định
12
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:
13
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)
m
Info (D) = -
p .log p
i
(2.0)
∑
i
2
i=1
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
|Ci , D |
p =
(2.1)
i
| D |
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:
v
D
Info A (D) =
j Info(Dj )
(2.2)
∑
D
j=1
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
14
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:
v
| Dj |
| D |
| Dj |
| D |
SplitInfo (D) =
×log2 (
)
(2.4)
∑
A
j=1
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( A)
GainRatio( A) =
(2.5)
SplitInfo( A)
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:
m
G in i ( D ) = 1 −
( p i ) 2
(2.6)
∑
i = 1
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:
| C
|
i , D
p i
=
(2.7)
| D |
15
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:
| D |
| D2 |
| D |
1
GiniA (D) =
Gini(D ) +
Gini(D2 )
(2.8)
1
| D |
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]
16
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
17
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
Tuổi
<=30
31…4
Sinh viên
Có
Tỷ lệ tiền gửi
sai
đúng
Có
Không
Có
Không
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:
18
IF tuổi=”<=30” AND sinh_vien = “sai”
IF tuoi = “<=30” AND sinh_vien = “đúng”
IF tuoi = “31…40”
THEN mua_may_tinh= “sai”
THEN mua_may_tinh = “đúng”
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
19
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
CLS
Tỷ lệ sử dụng
9%
ID3
4.5%
C4.5
54.55%
9%
C5.0
CART
40.9%
4.5%
Random Tree
Random Forest
9%
20
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
21
Tải về để xem bản đầy đủ
74 trang
05/05/2025
2040
Bạn đang xem 30 trang mẫu của tài liệu "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", để tải tài liệu gốc về máy hãy click vào nút Download ở trên.
File đính kèm:
- khoa_luan_ung_dung_mo_hinh_hoc_may_tien_tien_nham_tang_cuong.pdf
