Phần mở đầu giới thiệu tên luận văn và trình bày lí do chọn đề tài của luận văn cũng nhƣ xác định mục tiêu, đối tƣợng, phạm vi và phƣơng pháp nghiên cứu của luận văn. o Chƣơng 1: Trình bày các vấn đề cơ sở lý thuyết của luận văn, tổng quan về khai phá dữ liệu và trích chọn thuộc tính. o Chƣơng 2: Trình bày nội dung chính của thuật toán phân lớp sử dụng trong luận văn là thuật toán Random Forest. o Chƣơng 3: Trình bày phƣơng pháp đề xuất và hƣớng giải quyết của luận văn.
o Chƣơng 4: Trình bày quá trình thực nghiệm và đánh giá kết quả thực nghiệm. o Kết luận: Phần này trình bày những vấn đề đã đƣợc giải quyết trong luận văn, những vấn đề còn tồn tại và hƣớng giải quyết trong thời gian tới. LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 8 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. Nó bao hàm một loạt các kỹ thuật nhằm phát hiện các thông tin có giá trị tiềm ẩn trong tập các dữ liệu lớn.
Về bản chất, khai phá dữ liệu liên quan đến việc phân tích các dữ liệu và sử dụng các kỹ thuật để tìm ra các quy luật trong tập dữ liệu. Năm 1989, Fayyad, Piatestsky-Shapiro và Smyth đã dùng khái niệm Phát hiện tri thức trong cơ sở dữ liệu (Knowledge Discovery in Database – KDD) [14] để chỉ toàn bộ quá trình phát hiện các tri thức có ích từ các tập dữ liệu lớn. Trong đó, khai phá dữ liệu là một bƣớc đặc biệt quan trọng trong toàn bộ quá trình, sử dụng các giải thuật đặc biệt để chiết xuất ra các đặc trƣng từ dữ liệu [14]. 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.
Phƣơng pháp trích chọn sẽ giúp giảm kích cỡ của không gian dữ liệu đặc trƣng, loại bỏ những thuộc tính không liên quan và những thuộc tính nhiễu. Phƣơng pháp này có ảnh hƣởng ngay lập tức đến các ứng dụng nhƣ thuật toán tăng tốc độ khai phá dữ liệu, cải thiện chất lƣợng dữ liệu và vì vậy tăng hiệu xuất khai phá dữ liệu, kiểm soát đƣợc kết quả của thuật toán. Các kĩ thuật khai phá dữ liệu thƣờng đƣợc chia thành 2 nhóm chính: - Kĩ thuật khai phá dữ liệu mô tả: có nhiệm vụ mô tả về các tính chất hoặc các đặc tính chung của dữ liệu trong CSDL hiện có. Các kĩ thuật này gồm có: phân cụm (clustering), tóm tắt (summerization), trực quan hóa (visualiztion), phân tích sự phát triển và độ lệch (Evolution and deviation analyst), phân tích luật kết hợp (association rules).
- Kĩ thuật khai phá dữ liệu dự đoán: có nhiệm vụ đƣa ra các dự đoán dựa vào các suy diễn trên dữ liệu hiện thời. Các kĩ thuật này gồm có: phân lớp (classification), hồi quy (regression). Tuy nhiên, luận văn tập trung tìm hiểu 3 nhiệm vụ chính sau [12]: Giảm chiều dữ liệu: Giảm chiều dữ liệu là việc làm giảm chiều của không gian tìm kiếm dữ liệu, giảm chi phí thu thập và lƣu trữ dữ liệu, nâng cao hiệu quả của việc khai phá dữ liệu và làm đơn giản hóa các kết quả khai phá dữ 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): Trích chọn thuộc tính là việc tìm ra một tập thuộc tính mới từ tập thuộc tính ban đầu nhằm nâng cao hiệu suất tính toán và độ chính xác phân lớp.
Các kỹ thuật trích chọn thuộc tính thƣờng liên quan đến các phép biến đổi phi tuyến (non-linear). Linear discriminant analysis LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 9 (LDA) và principal components analysis (PCA) là hai kỹ thuật phổ biến dùng trong trích chọn thuộc tính. Chọn lựa thuộc tính (Feature Selection): Chọn lựa thuộc tính là việc chọn ra một tập thuộc tính con từ tập thuộc tính ban đầu sao cho các tập thuộc tính con này thể thể hiện tốt nhất chức năng của một hệ thống quy nạp, chẳng hạn nhƣ một hệ thống phân lớp. Việc tìm kiếm một tập con thuộc tính tối ƣu thƣờng là rất khó và rất nhiều các vấn đề của chọn lựa thuộc tính là thuộc về lớp các bài toán NP-hard.
Tuy nhiên, chọn lựa thuộc tính lại đƣợc sử dụng rộng rãi trong giảm chiều dữ liệu vì các kết quả dựa trên các thuộc tính đƣợc chọn lựa từ tập thuộc tính ban đầu thƣờng dễ dàng lý giải hơn so với một tập các thuộc tính đƣợc biến đổi từ tập thuộc tính ban đầu. 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. Một lớp là một tập các đối tƣợng có cùng một số đặc điểm hoặc mối quan hệ nào đó, tất cả các đối tƣợng trong lớp này đƣợc phân vào trong cùng một tên lớp nhằm mục đích là để phân biệt với các lớp khác. Một cụm là một tập các đối tƣợng tƣơng tự nhau về mặt vị trí.
Các cụm thƣờng đƣợc tạo ra nhằm mục đích để sau đó tiến hành phân lớp các đối tƣợng. Trích chọn luật: Trích chọn luật tìm kiếm và đƣa ra dữ liệu bằng cách tất cả các dữ liệu đƣợc đƣa ra dựa trên các suy diễn/các quyết định mà các suy diễn/quyết định này đƣợc xây dựng từ các tri thức thu thập đƣợc từ 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. Do đó, việc tìm ra các luật IF-THEN nhằm đƣa ra các thông tin có giá trị là một cách diễn giải đơn giản và dễ hiểu nhất đối với ngƣời sử dụng.
Có thể phân loại chọn luật thành hai kiểu chính. Một kiểu liên quan đến việc tìm ra mối quan hệ giữa các thuộc tính đầu vào và các lớp nhãn ở đầu ra trong tập dữ liệu đã đƣợc gán nhãn. Kiểu chọn luật còn lại là việc khai phá các luật quan hệ (association rule), đây là việc tìm ra các mối quan hệ giữa các thuộc tính trong tập dữ liệu và điều này hoàn toàn không phụ thuộc vào lớp nhãn ở đầu ra [27]. Các kỹ thuật trích chọn ra luật quan hệ thƣờng đƣợc ứng dụng nhằm tìm kiếm các mối liên hệ giữa các đối tƣợng trong dữ liệu phiên.
Khai phá các luật quan hệ có thể đƣợc áp dụng để phân tích hành vi khách hàng trong siêu thị. Ví dụ một khách hàng mua bơ cũng sẽ mua bánh mì với một xác suất nhất định nào đó. Khai phá dữ liệu thƣờng đƣợc xem nhƣ là một giai đoạn trong chu trình phát hiện tri thức và khai phá dữ liệu. Các giai đoạn khác trong chu trình này bao gồm: a) LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 10 Kho dữ liệu, b) chọn lựa các dữ liệu đích, c) làm sạch dữ liệu, d) giảm chiều dữ liệu, e) chọn lựa mô hình phù hợp, f) khai phá dữ liệu, g) nhận xét và trình bày kết quả, h) kiểm tra các kết quả có đƣợc.
Một cách đơn giản có thể hiểu nhƣ sau: kho dữ liệu cho phép dữ liệu đƣợc thu thập từ nhiều nguồn dữ liệu khác nhau và ở nhiều định dạng khác nhau và nguồn dữ liệu này đƣợc sử dụng trong một ứng dụng cụ thể; chọn lựa các dữ liệu đích nhằm tạo ra một dữ liệu cụ thể dùng cho ứng dụng; làm sạch số liệu nhằm loại bỏ nhiễu và các giá trị bất thƣờng; giảm chiều dữ liệu nhằm chuyển dữ liệu thành một dạng dữ liệu phù hợp với ứng dụng; chọn lựa mô hình là chọn một giải thuật phù hợp; khai phá dữ liệu nhằm tìm ra các thông tin cần quan tâm; nhận xét và trình bày kết quả là việc giải thích các kết quả có đƣợc; kiểm tra các kết quả có đƣợc là việc chuyển các kết quả thành một dạng có thể kiểm tra lại và sử dụng lại [27]. Nếu xem xét các quá trình của chu trình khai phá dữ liệu trong ngữ cảnh của chọn lựa thuộc tính, chúng có thể đƣợc tổng hợp thành 4 bƣớc cơ bản sau [12, 10, 28, 23]: 1) Kho dữ liệu (Data warehousing) - dữ liệu từ các nguồn khác nhau đƣợc tổng hợp, lƣu trữ lại, 2)Tiền xử lý (Pre-processing) (các bƣớc b, c, và d) – chọn lựa các dữ liệu phù hợp cho một ứng dụng cụ thể, 3) Khai phá dữ liệu (Data ming) (các bƣớc e và f) – một giải thuật phai phá dữ liệu đƣợc chọn lựa và áp dụng trên bộ số liệu thu đƣợc ở bƣớc 2, 4) Hậu xử lý (Post-processing) (các bƣớc g và h) – Các tri thức thu đƣợc từ bƣớc 3 đƣợc chọn lựa, nhóm… sao cho chúng có thể dễ dàng hiểu và sử dụng.2 Lựa chọn thuộc tính và bài toán phân lớp Nhiệm vụ cơ bản của việc phân lớp là phân chia một tập các đối tƣợng thành n-hữu hạn lớp đã biết trƣớc. 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 có thể rất lớn do những lý do sau: Dữ liệu đƣợc thu thập không đơn giản chỉ phục vụ cho một tác nghiệp cụ thể chẳng hạn nhƣ khai phá dữ liệu. Do đó, đối với một ứng dụng cụ thể bộ dữ liệu có thể có rất nhiều các thuộc tính thừa hoặc không phù hợp. Đôi khi thậm chí nếu chúng ta biết các thuộc tính đƣợc thiết kế cho một tác nghiệp cụ thể thì thuộc tính nào là thuộc tính có liên quan thƣờng không đƣợc biết. Điều này là do bản chất của nghiên cứu.
Chúng ta tiến hành thực nghiệm và LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 11 thu thập số liệu vì chúng ta muốn biết nhiều hơn lĩnh vực mà chúng ta muốn tìm hiểu và chúng ta thông thƣờng không có một ý niệm chính xác về các thuộc tính cần thiết.