Chương 1: Tổng quan về bài toán cần giải quyết 1.1 Giới thiệu Ngày nay nhờ sự phát triển mạnh mẽ của khoa học kỹ thuật mà chúng ta phải tiếp nhận và giải quyết với khối dữ liệu ngày càng lớn, có thể lên tới hàng nghìn tỷ các đối tượng và hàng nghìn các thuộc tính. Câu hỏi đặt ra ở đây là liệu có phải “càng nhiều có nghĩa là càng tốt?”. Câu trả lời cũng có thể là “Đúng” và cũng có thể là “Sai”. Trả lời là “Đúng” là vì ít nhất thì chúng ta cũng có thể nhận được những gì mà chúng ta mong muốn.
Còn câu trả lời là “Sai” vì khi có sự hiện diện của quá nhiều dữ liệu thì cũng tương đương với việc là “không có dữ liệu” nếu việc truy nhập dữ liệu không hiệu quả. Như vậy thì “nhiều” cũng có thể là “ít”. Dữ liệu trong mọi lĩnh vực như kinh tế, xã hội. sẽ trở thành vô nghĩa nếu không có phương pháp xử lý đồng nghĩa với không khai thác được các thông tin quan trọng của nó.
Bởi vì sự tích lũy dữ liệu đã trở thành thói quen nên phải có kỹ thuật lựa chọn dữ liệu phù hợp với tốc độ thu thập dữ liệu. Hơn thế nữa, với khối lượng lớn dữ liệu được sinh ra từ các máy tính hoặc từ các thiết bị khác tương đương, phải được xử lý một cách tự động để chúng ta có thể kiểm soát và chế ngự được chúng. Số lượng bản ghi cũng như kích thước của từng bản ghi được lưu trữ rất nhanh và lớn gây khó khăn trong việc lưu trữ và xử lý,… nên người ta đã đưa ra một số giải pháp như: xử lý song song, tìm ra các mẫu đặc trưng, tìm ra các thuộc tính đặc trưng. Hướng nghiên cứu của luận văn là tìm ra các thuộc tính đặc trưng hay còn gọi là lựa chọn thuộc tính (feature selection).
Phương pháp này được giới thiệu từ những năm 1970 trong các tài liệu về xác suất thống kê, học máy và khai phá dữ liệu, trong cả bài toán nhận dạng mẫu. Những năm trở lại đây, do nhu cầu giảm chiều số liệu ngày càng cao nên có rất nhiều các nghiên cứu về lựa chọn thuộc tính, lĩnh vực này phát triển mạnh mẽ cả về chiều rộng lẫn chiều sâu. Bằng chứng là chúng ta có thể tìm thấy trong rất nhiều bài báo, tạp chí hoặc trong các hội thảo gần đây. Các nghiên cứu bắt đầu từ lựa chọn thuộc tính giám sát cổ điển mở rộng đến lựa chọn thuộc tính không giám sát và bán giám sát, cả đến việc lựa chọn các kiểu thuộc tính khác như thuộc tính “nguyên nhân” và “cấu trúc”.
Một số nghiên cứu xét đến các loại dữ liệu khác như high-throughput, văn bản hoặc ảnh và có cả ước lượng lựa chọn thuộc tính… [1].2 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 7 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com các dữ liệu và sử dụng các kỹ thuật để tìm ra các mẫu hình có tính chính quy 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 (Kownledge Discovery in Database – KDD) để 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 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 mẫu hay các mô hình từ dữ liệu. 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ưong 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 suất khai phá dữ liệu, kiểm soát được kết quả của thuật toán.
Khai phá dữ liệu chủ yếu tập trung vào 3 nhiệm vụ chính sau: 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 (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 8 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com phân vào trong cùng một lớp tên 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 đó, trích chọn ra các luật IF-THEN để đư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. 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à 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. Do đó, chúng ta phải tìm các thuộc tính cần thiết nhiều nhất mà chúng ta có thể nghĩ đến thậm chí chúng có thể là các thuộc tính dư thừa hoặc không liên quan. Chúng ta chỉ có thể biết được thuộc tính nào là liên quan sau khi chúng ta nghiên cứu bộ số liệu đã được thu thập.
Một tác nghiệp có thể yêu cầu dữ liệu từ nhiều nguồn khác nhau. Nếu dữ liệu từ mỗi nguồn là lớn thì sau khi nối các nguồn dữ liệu trên chúng ta sẽ có một bộ dữ 9 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com liệu khổng lồ. Nếu chúng ta biết được các thuộc tính liên quan thì chúng ta có thể giải quyết được vấn đề trên nhưng trên thực tế chúng ta thường không biết trước các thuộc tính nào là thuộc tính liên quan. 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ó nhiều thuộc tính thông thường có nghĩa là cần nhiều thực thể, vì vậy chúng ta cần đảm bảo các ràng buộc thống kê giữa các thực thể trong các lớp khác nhau, 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 hoặc dẫn đến hiện tượng overfitting trong mô hình, Thêm vào đó với sự có mặt của dữ liệu thừa hoặc dữ liệu không liên quan có thể làm cho bộ phân lớp trở lên phức tạp hơn.
Điều này là gây ra những khó khăn không cần thiết cho chúng ta trong việc diễn giải các kết quả học được từ tập huấn luyện.