Chương 1 cũng đưa ra một số đánh giá về những điểm mạnh và điểm yếu của cây quyết định trong mô hình phân lớp dữ liệu. Ngoài ra, chương 1 còn giới thiệu một số giải thuật đã và đang được sử dụng rộng rãi trong các mô hình phân lớp hiện nay. Một số mục quan trọng như mục tiêu, đối tượng, phạm vi nghiên cứu và phát biểu bài toán của luận văn cũng đã được trình bày trong chương 1.5 VÀ GIẢI THUẬT RANDOM FOREST 2. Tổng quan Giải thuật C4.5 là một giải thuật học máy bằng cây quyết định được phát triển bởi Ross Quinlan.Ross Quinlan đã phát triển giải thuật C4.5 với khoảng 9000 dòng lệnh C.
Cây quyết định được tạo ra bởi C4.5 có thể được sử dụng cho bài toán phân lớp [20].5 đã có nhiều cải tiến so với giải thuật ID3 như: Cho phép xử lý cả các thuộc tính tiếp diễn và rời rạc Xử lý được những thiếu sót trong training data với những giá trị thiếu Hỗ trợ việc xử lý cắt cây (pruning tree) sau khi tạo Giải thuật J48 là một bản cài đặt giải thuật C4.5 được sử dụng với công cụ Weka và là một phiên bản được viết bằng Java.5 là giải thuật phân lớp dữ liệu dựa trên cây quyết định hiệu quả và phổ biến trong những ứng dụng xử lý và thao tác với những tập dữ liệu có kích thước nhỏ.5 phù hợp với những cơ sở dữ liệu nhỏ, và có khả năng sắp xếp lại dữ liệu tại mỗi node trong quá trình phát triển cây quyết định.5 chọn thuộc tính phân loại tốt nhất Trong quá trình xây dựng cây quyết định, tác vụ quan trọng nhất là ta cần chọn thuộc tính tốt nhất để phân hoạch dữ liệu. Trong quá trình xây dựng cây, ta cần tiến hành phân hoạch dữ liệu sao cho kết quả thu được cây nhỏ nhất, điều này sẽ phụ thuộc vào việc chọn thuộc tính sinh ra các nút thuần khiết nhất. Ở đây ta tìm hiểu và sử dụng giải thuật học máy dựa trên cây quyết định tiêu biểu là giải thuật C4. Dưới đây là công thức (2.1): k I S Pi log 2 Pi (2.1) i 1 11 Dưới đây là công thức tính độ đo hỗn loạn (2.2) i 1 S Độ lợi thông tin (informartion gain) khi chọn thuộc tính A phân hoạch dữ liệu S thành v phần được tính theo công thức (2.3) Tuy nhiên, khi dữ liệu có thuộc tính có nhiều giá trị hơn các thuộc tính khác, độ lợi thông tin tăng trên các thuộc tính có nhiều giá trị phân hoạch.
Giả sử khi sử dụng thuộc tính A phân hoạch dữ liệu S thành v phần, thông tin của phân phối dữ liệu được tính như công thức (2.4): v Si Si P S log 2 ( 2.4) i 1 S S Và tỉ số độ lợi được tính như công thức (2. Xử lý những giá trị thiếu trong C4.5 Trong quá trình xử lý các tệp dữ liệu, từ những bài toán đơn giản cho đến những bài toán phức tạp, không thể tránh khỏi việc có dữ liệu thiếu (missing data) trong tệp dữ liệu. Dữ liệu thiếu là giá trị của thuộc tính không có do lỗi trong quá trình nhập bản ghi vào cơ sở dữ liệu (có thể nhập qua biểu mẫu ứng dụng hoặc nhập trực tiếp vào cơ sở dữ liệu). Khi đó độ đo độ lợi thông tin của test B giảm vì chúng ta không phân được lớp nào từ các case trong S0 và được tính theo công thức 2.
Ƣu nhƣợc điểm của cây quyết định trong phân lớp dữ liệu 2. Ưu điểm của cây quyết định - Cho phép sinh ra các quy tắc dễ hiểu: Một trong những điểm mạnh của cây quyết định là khả năng sinh ra các quy tắc, những quy tắc này sau đó có thể dễ dàng chuyển đổi được sang dạng tiếng anh, hoặc chuyển thành các câu lệnh SQL. Từ đó sẽ khiến cho quá trình phân lớp trở nên dễ hiểu và dễ mô tả hơn. - Hỗ trợ khả năng tính toán dễ dàng trong quá phân lớp: Các giải thuật được sử dụng để tạo ra cây quyết định thường tạo ra những cây với số phân nhánh thấp và các test đơn giản tại từng node.
Điều này trở thành một ưu điểm nổi trội của cây quyết định, bởi lẽ trong môi trường thương mại, các mô hình dự đoán thường được sử dụng để phân lớp với số lượng dữ liệu cực lớn, thậm chí lên đến hàng tỉ bản ghi. Nhược điểm của cây quyết định Mặc dù có nhiều ưu điểm như đã mô tả ở phần trên, cây quyết định vẫn tồn tại một số điểm yếu. Một trong những điểm yếu nhất của cây quyết định là nó không tỏ ra thích hợp khi thực hiện những bài toán với mục tiêu là dự đoán giá trị của thuộc tính liên tục như doanh số, thu nhập, lãi suất v.v… - Gặp khó khăn hoặc phát sinh lỗi nếu có quá nhiều lớp. Đối với cây quyết định, nếu có quá nhiều lớp thì có thể xảy ra lỗi.
Ngoài ra một số cây quyết định lại chỉ phù hợp khi tiến hành những bài toán phân lớp nhị phân. - Tốn kém khi đào tạo. Khi ta quyết định sử dụng cây quyết định, ta sẽ cần phải chấp nhận sẽ tốn kém hay đắt về mặt tính toán, vì tại mỗi node ta cần tính toán một độ đo trên từng thuộc tính. Giải thuật Random Forest 2.
Giới thiệu tổng quan về giải thuật Random Forest Random Forest là một giải thuật học máy thông dụng thuộc kiểu học có giám sát. Trong đó, thay vì chỉ dựa vào duy nhất một cây quyết định, giải thuật Random Forest sẽ tiến hành dự đoán trên từng cây và dựa trên những dự đoán chiếm ưu thế, nó sẽ dự đoán ra kết quả cuối cùng (final output). Điều quan trọng: Số lượng cây trong rừng càng nhiều, thì độ chính xác sẽ càng cao, và càng hạn chế được vấn đề overfiting. Minh họa cơ chế làm việc của giải thuật Random Forest (Nguồn: https://www.com/machine-learning-random-forest-algorithm) 2.
Lý do sử dụng Random Forest Có một số lý do giải thích tại sao ta nên sử dụng giải thuật Random Forest: Thời gian để thực hiện training ít hơn so với các giải thuật khác. Giải thuật Random Forest đưa ra dự đoán kết quả với độ chính xác cao, đồng thời hiệu quả ngay cả với các tệp dữ liệu lớn. 14 Có độ chính xác cao, thậm chí cho phép duy trì độ chính xác ngay cả khi có một lượng lớn dữ liệu bị thiếu. Giảm thiểu độ rủi ro của vấn đề overfitting 2.
Cơ chế làm việc của giải thuật Random Forest Giải thuật Random Forest thực hiện trong hai giai đoạn. Giai đoạn đầu tiên là tạo ra rừng ngẫu nhiên (random forest) bằng cách kết hợp N cây quyết định, giai đoạn thứ hai là đưa ra dự đoán cho từng cây được tạo ra trong giai đoạn đầu. Tiến trình làm việc của giải thuật Random Forest bao gồm các bước như sau: Bước 1: Chọn ngẫu nhiên các samples từ tập dữ liệu đào tạo (training set) Bước 2: Xây dựng các cây quyết định được kết hợp với các training data được chọn Bước 3: Tiến hành voting bằng cách chia trung bình Bước 4: Chọn kết quả dự đoán được vote nhiều nhất để làm kết quả dự đoán cuối cùng. Quá trình kết hợp của nhiều mô hình này còn được gọi là Ensemble.
Ensemble sử dụng hai phương pháp sau: Bagging: Tạo ra một tập con dữ liệu đào tạo khác từ tập dữ liệu đào tạo với sự thay thế. Kết quả cuối cùng được dựa trên giá trị voting chủ yếu. Boosting: Kết hợp các weak learners vào các strong learners bằng cách tạo ra các mô hình tuần tự, nhờ đó mô hình cuối cùng có độ chính xác cao nhất. Ví dụ: ADA BOOST, XG BOOST 15 Hình 2.
Biểu diễn về hai phƣơng pháp Bagging và Boosting (Nguồn: https://www.com/tutorials/machine-learning-tutorial/random-forest-algorithm) Giải thuật Random Forest sử dụng phương pháp Bagging. Bagging còn được biết đến với tên là Bootstrap Aggregation được sử dụng bởi giải thuật Random Forest. Quá trình này bắt đầu với bất kỳ dữ liệu gốc ngẫu nhiên nào. Sau khi sắp xếp, dữ liệu này sẽ được tổ chức thành các samples còn được gọi là Bootstrap Sample.
Quá trình này còn được gọi là Bootstraping. Biểu diễn phƣơng pháp Bagging (Nguồn: https://www.com/tutorials/machine-learning-tutorial/random-forest-algorithm) 2. Những đặc điểm thiết yếu của giải thuật Random Forest - Tính lung tung: Mỗi cây có một thuộc tính duy nhất, có các đặc điểm và tính đa dạng liên quan đến các cây khác. - Tính song song: Ta hoàn toàn có thể sử dụng CPU để xây dựng random forest vì mỗi cây được tạo một cách tự động từ các dữ liệu và tính năng khác nhau.
- Phân chia dữ liệu đào tạo-kiểm tra (Train-Test split): Trong giải thuật Random Forest, ta không cần phải phân biệt giữa dữ liệu cho việc đào tạo và dữ liệu cho test, bởi lẽ cây quyết định sẽ không bao giờ nhìn thấy quá 30% dữ liệu. - Tính ổn định (stability): Kết quả cuối cùng được dựa trên phương pháp Bagging, điều đó có nghĩa là kết quả được dựa trên majority voting hoặc giá trị trung bình. Ứng dụng của giải thuật Random Forest Giải thuật Random Forest có thể được sử dụng trong các lĩnh vực sau: Ngân hàng: Nhận diện rủi ro của các khoản vay. Giúp ngân hàng đưa ra quyết định hoặc phân biệt xem có nên cho khách hàng vay hay không.
Ngoài ra giải thuật cũng giúp phát hiện ra những kẻ lừa đảo. Y dược và chăm sóc sức khỏe: Nhận diện xu hướng dịch bệnh và rủi ro của bệnh. Các chuyên gia y tế có thể sử dụng các hệ thống ứng dụng random forest để 17 giúp chẩn đoán bệnh nhân. Các bệnh nhân được chẩn đoán bằng cách xem lại lịch sử điều trị của họ, để từ đó đưa ra đề xuất sử dụng thuốc cho các bệnh nhân.
Chứng khoán: Các chuyên gia tài chính có thể sử dụng giải thuật Random Forest để nhận diện tiềm năng thị trường của các cổ phiếu. Giải thuật cũng cho phép họ nhớ lại về diễn biến của các cổ phiếu trước đó. Thương mại điện tử: Giúp các hãng dự đoán được sở thích của các khách hàng dựa trên hành vi tiêu thụ trong quá khứ của họ. Khi nào không sử dụng Random Forest Giải thuật Random Forest không phù hợp sử dụng trong những tình huống sau: Ngoại suy: Hồi quy Random Forest không lý tưởng đối với dữ liệu ngoại suy.
Không giống như hồi quy tuyến tính vốn sử dụng những quan sát đã có sẵn để dự đoán các giá trị vượt ra miền các quan sát [17]. Dữ liệu thưa thớt: Random Forest không cung cấp kết quả tốt khi dữ liệu bị thưa thớt. Trong trường hợp này, đối tượng của các đặc trưng và các bootstrap sample sẽ có một khoảng trống bất biến. Điều này sẽ dẫn đến sự không hiệu quả, từ đó sẽ tác động đến kết quả.