- Nghiên cứu, xây dựng phương pháp trích chọn thuộc tính nhằm làm tăng hiệu quả phân lớp. - đối với dữ liệu đa chiều. - Abstract: Tổng quan về khai phá dữ liệu và trích chọn thuộc tính. - Cơ sở dữ liệu Content. - CHƢƠNG 1: TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU VÀ TRÍCH CHỌN THUỘC TÍNH. - 1.1 Giới thiệu khai phá dữ liệu và trích chọn thuộc tính. - Khai phá dữ liệu là một khái niệm ra đời từ những cuối những năm 80 của thế kỷ trước. - Trong khai phá dữ liệu thì phương pháp trích chọn thuộc tính đóng một vai trò quan trọng trong tiền xử lý số liệu. - Trong nhiệm vụ làm giảm chiều dữ liệu chúng ta cần phân biệt hai khái nhiệm sau:. - Trích chọn thuộc tính (Feature Extraction):. - Chọn lựa thuộc tính (Feature Selection):. - Phân cụm và phân lớp:Phân lớp và phân cụm là hai nhiệm vụ có mối quan hệ tương đối gần nhau trong khai phá dữ liệu. - Đối với người sử dụng các kết quả của khai phá dữ liệu họ chỉ mong muốn có một cách giải thích đơn giản là tại sao có các kết quả phân lớp đó, thuộc tính nào ảnh hưởng đến kết quả khai phá dữ liệu…Tuy nhiên, bằng các tham số phân lớp rất khó để có thể diễn giải các tri thức đó theo cách mà người sử dụng có thể dễ dàng hiểu được. - Lựa chọn thuộc tính và bài toán phân lớp. - Tập đối tượng cần phân lớp được đặc trưng bởi một tập các thuộc tính chứa các thông tin cần thiết liên quan đến các lớp, trong đó mỗi tập các thuộc tính được đại diện bởi một tập các thuộc tính – giá trị. - Với một tập dữ liệu bao gồm một tập các đối tượng đã được phân lớp (thường gọi là tập tập huấn) nhiệm vụ đặt ra là từ tập huấn luyện cho trước xây dựng một bộ phân lớp cho các dữ liệu tương tự. - Vấn đề đặt ra đối với bài toán phân lớp là số lượng các thuộc tính thường rất lớn nhưng các thuộc tính không liên quan hoặc thừa có thể có những ảnh hưởng tiêu cực đối với các giải thuật phân lớp. - Các thuộc tính/dữ liệu thừa hoặc không liên quan có thể là nguyên nhân dẫn đến việc học của giải thuật không được chính xác.. - 1.3 Phƣơng pháp lựa chọn thuộc tính. - Có thể định nghĩa lựa chọn thuộc tính là một quá trình tìm ra một tập con các thuộc tính từ M tập thuộc tính của tập dữ liệu N ban đầu, như vậy phải xác định tiêu chuẩn lựa chọn thuộc tính. - Lựa chọn thuộc tính có thể dựa vào các mô hình, các chiến lược tìm kiếm, thước đo chất lượng thuộc tính và ước lượng.Có ba loại mô hình như Filter, Wrapper, Embedded.. - Ước lượng của việc chọn lựa thuộc tính bao gồm hai nhiệm vụ: một là so sánh. - hai giai đoạn: trước và sau khi lựa chọn thuộc tính. - Hai là so sánh hai thuật toán lựa chọn thuộc tính [3].. - Tóm lại lựa chọn thuộc tính được xem như là sự tổng hợp của ba thành phần chính: tìm kiếm, đánh giá, chọn lựa mô hình.. - 1.4 Một số thuật toán lựa chọn thuộc tính. - Các thuật toán lựa chọn thuộc tính được xét dưới góc độ chiến lược tìm kiếm nào được sử dụng trong giải thuật đó: Tìm kiếm toàn bộ, Tìm kiếm theo kinh nghiệm và Tìm kiếm xác suất. - Ngoài ra chúng ta cũng nghiên cứu một vài phương pháp khác: phương pháp trọng số thuộc tính (feature weighting method), phương pháp lai (hybrid method) và phương pháp lớn dần (incremental method).. - Phƣơng pháp trọng số thuộc tính 1.4.5. - Random Forest (rừng ngẫu nhiên) là phương phân lớp thuộc tính được phát triển bởi Leo Breiman tại đại học California, Berkeley. - Breiman cũng đồng thời là đồng tác giả của phương pháp CART (Classification and Regression Trees) được đánh giá là một trong 10 phương pháp khai phá dữ liệu kinh điển. - Một mẫu gồm B tập dữ liệu, mỗi tập dữ liệu gồm n phần tử được chọn lựa ngẫu nhiên từ D với sự thay thế (giống như bootstrap). - Trong đó Random Forest có một số thuộc tính mạnh như:. - (2) Thuật toán giải quyết tốt các bài toán có nhiều dữ liệu nhiễu.. - (4) Có những sự ước lượng nội tại như độ chính xác của mô hình phỏngđoán hoặc độ mạnh và liên quan giữa các thuộc tính.. - Dữ liệu out-of-bag được sử dụng để ước lượng lỗi tạo ra từ việc kết hợp các kết quả từ các cây tổng hợp trong random forest cũng như dùng để ước tính độ quan trọng thuộc tính (variable important).. - 2.4.2 Thuộc tính quan trọng. - Việc thực hiện các tính toán để xác định thuộc tính quan trọng trong RF cũng gần như tương tự việc sử dụng OOB để tính toán lỗi trong RF. - Cách thực hiện như sau: Giả sử chúng ta cần xác định “thuộc tính quan trọng” của thuộc tính thứ thứ m. - Đầu tiên tính ROOB, sau đó hoán vị ngẫu nhiên các giá trị của thuộc tính m trong dữ liệu OOB, lần lượt “gửi” các giá trị này xuống cây và “đếm” số các dự đoán đúng ta gọi việc tính toán này đối với thuộc tính là Rperm.. - Độ quan trọng thuộc tính được tính như sau:. - Trong trường hợp giá trị của thuộc tính quan trọng trên mỗi cây là độc lập thì chúng ta có thể tính được lỗi chuẫn (standard error) của ROOB – Rperm. - Chương này luận văn trình bày phương pháp học máy nhằm tìm ra bộ thuộc tính tối ưu từ tập các thuộc tính của bộ số liệu cho trước, đó là sử dụng giải thuật tựa giải thuật di truyền (Genetic-Algorithm) kết hợp với thuật toán rừng ngẫu nhiên (Random Forest).. - Chương này mô tả phương pháp đề xuất như là cách tiếp cận theo wrapper để tìm ra các thuộc tính tối ưu, loại bỏ các thuộc tính dư thừa.. - Tạo ra các bộ thuộc tính con từ tập thuộc tính ban đầu bằng phương pháp kết hợp việc chọn ngẫu nhiên với việc phân bố đều các thuộc tính.. - Không thực hiện việc lai ghép, đột biến để tạo ra các bộ thuộc tính mới mà thực hiện việc đánh giá các bộ thuộc tính, dựa vào đó đánh giá các thuộc tính để chọn ra các thuộc tính có độ phù hợp cao.. - Dùng thuật toán học để làm tiêu chí đánh giá độ thích hợp của các bộ thuộc tính.. - Bƣớc 1: Tạo ra m bộ thuộc tính từ tập n thuộc tích ban đầu.. - Mỗi bộ chứa 2*n/m thuộc tính. - o n/m thuộc tính đều nhau o n/m thuộc tính ngẫu nhiên. - Bƣớc 2: Tính thang điểm ƣớc lƣợng cho từng bộ thuộc tính - Dùng RF tính thang điểm ước lượng cho các bộ thuộc tính.. - Được tập các giá trị ước lượng f(i) (i=1,..,m) Bƣớc 3: Tính ranking theo trọng số của từng thuộc tính.. - Trọng số của mỗi thuộc tính i được tính theo công thức:. - k ij = 0 nếu thuộc tính thứ i không được chọn trong bộ thuộc tính thứ j k ij = 1 nếu thuộc tính thứ i được chọn trong bộ thuộc tính thứ j Bƣớc 4: Xây dựng tập mới gồmp% thuộc tính tốt nhất. - Điều kiện dừng a) số thuộc tính <. - Tập dữ liệu ban đầu được phân chia ngẫu nhiên thành hai tập: Tập dữ liệu huấn luyện và Tập dữ liệu kiểm tra.. - Tập dữ liệu huấn luyện cho qua Phần 1. - Dữ liệu huấn luyện là bảng có kích cỡ m x n, với n là số thuộc tính ban đầu và m là số bản ghi. - Mỗi bảng là một tập con các thuộc tính của bộ dữ liệu ban đầu.. - Bước 2: Đánh giá độ thích nghi của mỗi bộ thuộc tính mới bằng việc áp dụng thuật toán học máy random forest. - Bước 3: Sau đó, với mỗi thuộc tính của bộ thuộc tính ban đầu ta tính được độ phù hợp (trọng số)w của mỗi thuộc tính theo công thức:. - Với j=1,..,n tương ứng với n thuộc tính đầu tiên. - Fitness i là độ phù hợp của bộ thuộc tính thứ i trong m bộ thuộc tính mới. - k nhận giá trị 1 nếu thuộc tính thứ j được chọn và nhận giá trị 0 nếu thuộc tính j không được chọn trong bộ thuộc tính i.. - Bước 4: Thực hiện sắp xếp n thuộc tính theo thứ tự giảm dần của trọng số w j . - Lấy p% các thuộc tính được theo thứ tự từ trên xuống dưới ta được một bộ thuộc tính mới gồm (n*p)/100 thuộc tính.. - Bộ thuộc tính này lại lặp lại các bước trên cho đến khi thu được một bộ thuộc tính có số thuộc tính đạt ngưỡng nào đó hoăc số lần lặp xác định. - Kết thúc quá trình hoạt động ở Phần 1: thu được bộ thuộc tính có độ phù hợp cao nhất. - Lấy tất cả bản ghi của bộ số liệu ban đầu nhưng chỉ với các thuộc tính vừa tìm được ở Phần 1, chia làm hai phần: huấn luyện và kiểm tra. - Tập dữ liệu huấn luyện mới được sử dụng để huấn luyện cho RF.. - Chuẩn hóa lại dữ liệu theo cấu trúc xác định trước.. - Tính độ phù hợp của bộ dữ liệu inpData với hệ số kiểm chứng chéo là CrV.. - Hàm proccess có chức năng lựa chọn ra tập các thuộc tính tối ưu nhất từ tập dữ liệu đầu vào InpData.. - m là tham số xác định số bộ thuộc tính trong mỗi lần phân chia.. - p xác định số thuộc tính loại bỏ sau mỗi lần chọn lựa. - Tính % đoàn nhận đúng, thời gian chạy của RunNum lần chạy RF với số lượng cây là TreeNum trên bộ thuộc tính ban đầu và bộ thuộc tính tối ưu mới tìm được.. - 4.3.1 Bộ dữ liệu ung thƣ dạ dày(Stomach) 4.3.1.1 Mô tả bộ dữ liệu Stomach. - Bộ dữ liệu Stomach Cancer gồm 137 bản ghi, mỗi bản ghi có 119 thuộc tính. - Các bản ghi trong bộ dữ liệu được phân thành hai lớp ký hiệu là normal (bệnh nhân bình thường) và cancer (bệnh nhân bị ung thư).. - 4.3.1.2 Kết quả và phân tích thực nghiệm trên bộ dữ liệu Stomach. - Hình 4.7 Biểu đồ so sánh kết quả chạy RF 20 lần trên bộ dữ liệu mới và bộ dữ liệu ban đầu với số cây bằng . - Hình 4.8 Biểu đồ so sánh thời gian chạy trung bình của 20 lần chạy RF trên bộ dữ liệu mới và bộ dữ liệu ban đầu với số cây bằng . - Ta thấy tỉ lện đoán nhận của RF với bộ thuộc tính mới tăng lên rõ ràng, ước tính tăng khoảng 5%, trung bình thuật toán RF cho kết quả đoán nhận là 78%, còn RF mới cho kết quả là 83%.. - Tỉ lệ đoán nhận trên bộ thuộc tính mới tăng lên cho thấy bộ thuộc tính mới đã loại bỏ được một số thuộc tính nhiễu, thuộc tính dư thừa. - Còn thời gian giảm đi là vì số lượng thuộc tính đã giảm xuống tương đối nhiều, cụ thể từ 119 thuộc tính ban đầu, sau khi lựa chọn bộ thuộc tính mới còn là 36 thuộc tính, như vậy số thuộc tính đã giảm khoảng 69% số thuộc tính ban đầu. - Tuy nhiên, để tìm ra một bộ thuộc tính mới chúng ta đã tiêu tốn một khoảng thời gian tương đối lớn. - Với bộ dữ liệu Stomach chúng ta mất khoảng 20 phút để tìm ra được một bộ thuộc tính tối ưu hơn, và với các bộ dữ liệu lớn hơn thì thời gian đó lại tăng lên, nhưng chúng ta chỉ mất thời gian 1 lần tìm bộ thuộc tính tối ưu. - Sau đó, tất cả các bài toán sử dụng bộ dữ liệu này khi thực thi trên bộ thuộc tính mới sẽ giảm thời gian tính toán trên tất cả các lần chạy. - 4.3.2 Bộ dữ liệu ung thƣ ruột kết Colon Turmo 4.3.2.1 Mô tả dữ liệu. - Hình 4.13 Kết quả chạy RF 20 lần trên bộ thuộc tính Colon Tumor ban đầu và sau khi tối ưu với số cây lần lượt là . - Hình 4.14 Biểu đồ so sánh thời gian huấn luyện trung bình của 20 lần chạy RF trên bộ dữ liệu Colon Tumor mới và bộ dữ liệu Colon Tumor ban đầu với số cây bằng . - Hình 4.15 Biểu đồ so sánh thời gian kiểm tra trung bình của 20 lần chạy RF trên bộ dữ liệu Colon Tumor mới và bộ dữ liệu Colon Tumor ban đầu với số cây bằng . - Kết quả thực nghiệm 20 lần trên bộ dữ liệu Colon Tumor với số cây lần lượt là cũng giống như kết quả thực nghiệm với bộ dữ liệu Stomach. - Rõ ràng so tỉ lệ đoán nhận của RF với bộ thuộc tính mới cao hơn tương đối so với bộ thuộc tính cũ, ước tính tăng khoảng 10%, trung bình thuật toán RF cho kết quả đoán nhận là 78%, còn RF mới cho kết quả là 89%. - Còn thời gian giảm đi là vì số lượng thuộc tính đã giảm xuống tương đối nhiều, cụ thể từ 2000 thuộc tính ban đầu, sau khi lựa chọn bộ thuộc tính mới còn là 600 thuộc tính, như vậy số thuộc tính đã giảm khoảng 70% số thuộc tính ban đầu. - Trong khuôn khổ của luận văn tôi đã tìm hiểu cơ sở lý thuyết và một số thuật toán áp dụng giải bài toán trích chọn thuộc tính phù hợp bằng cách giảm chiều dữ liệu. - Tôi cũng đã tập trung nghiên cứu về thuật toán Random Forest và phương pháp tiền xử lý dữ liệu. - Từ những tìm hiểu này tôi đề xuất hướng cải tiến nhằm tìm ra bộ thuộc tính tối ưu nhỏ nhất để tăng hiệu quả của thuật toán phân lớp.. - Từ những kết quả thực nghiệm trên bộ dữ liệu Colon Turmo, chúng ta thấy kết quả tương đổi ổn định và tốt. - [1] Nguyễn Hà Nam Tối ưu hóa KPCA bằng GA để chọn các thuộc tính đặc trưng nhằm tăng hiệu quả phân lớp của thuật toán Random Forest", Tạp chí Khoa học ĐHQGHN, Khoa học Tự nhiên và Công nghệ, số 25, tr