5. Phương pháp luận nghiên cứu
2.4 Công nghệ lựa chọn chức năng
Khẳ năng thu thập và tạo ra dữ liệu nhiểu ngày càng tốt hơn. Đó là nhờ vào tiến bộ trong công nghệ phần cứng máy tính để lưu trữ dữ liệu và công nghệ phần mềm quản lý dữ liệu.
Khai phá dữ liệu đã có một sức hấp dẫn lớn đổi với các nhà nghiên cứu hệ thống thông tin trong những năm gần đây, khẳ năng xử lý một khối lƣợng lớn dữ liệu để biến các dữ liệu đó thành kiến thức và các sáng chế có tính hữu dụng.
Chất lƣợng của dữ liệu, khối lƣợng dữ liệu lớn, dữ liệu kém chất lƣợng, không tin cậy, dư thừa, các tạp chất nhiễu; tất cả các hệ số đã ảnh hưởng đến quá trình rút trích kiến thức và huấn luyện sẽ khó khăn hơn.
Các chuyên gia trong lĩnh vực học máy và khai phá dữ liệu đã chỉ ra rằng chất lƣợng phân lớp ( nhƣ độ chính xác) giảm khi tập dữ liệu chứa nhiều chức năng không liên quan tới quá trình tiên đoán. Ví dụ, chất lƣợng của cây quyết định C4.5 tạo ra sai lệch lên tới 24.3 % bởi 3 chức năng không liên quan. Tuy nhiên, sai số giảm tới 11.1% nếu ta bỏ qua các chức năng không liên quan [39]. Thuật toán k lân cận gần nhất ( k-NN) làm giảm các thuộc tính không liên quan và kích thước tập huấn luyện nên chính xác sẽ tăng theo hàm mũ của các thuộc tính không liên quan [28].
Vì thế, các nhà nghiên cứu đã nhận thấy sự cần thiết phải tạo ra dữ liệu chính xác hơn từ một khối lượng lớn các bản ghi dữ liệu bằng việc sử dụng các phương thức lựa chọn chức năng. Lựa chọn chức năng hay tổ hợp các tập con thuộc tính là một quá trình nhận diện và sử dụng các thuộc tính liên quan nhất và loại ra các thuộc tính không liên qua và trùng lặp có thể [3].
Các biến, các chức năng, các đầu vào, hay việc lựa chọn các thuộc tính đã trở thành tâm điểm của sự chú ý của các nhà nghiên cứu trong rất nhiều các lĩnh vực ở đó số lƣợng các trường hợp và thuộc tính là rất lớn.
Mục đích của lựa chọn chức năng là để nhận đƣợc số lƣợng các chức năng ít hơn số lƣợng các chức năng nguyên gốc trong tập dữ liệu để nâng cao độ chính xác về việc tiên đoán, và tăng nhanh tốc độ phân lớp, và lờ đi các chức năng không liên quan hay ít quan trọng, nâng cao chất lƣợng dữ liệu, tránh việc đòi hỏi quá trùng kít dữ liệu ( over fitting), và hỗ trợ để giải quyết vấn đề của việc gia tăng một khối lƣợng lớn dữ liệu có thể và làm thế nào để sử dụng nó một cách có hiệu quả.
Các bài báo nghiên cứu đã chỉ ra rằng các công nghệ lựa chọn chức năng có thể đƣợc phân chia dựa theo thuật toán suy diễn và nó hoạt động thế nào với công cụ lựa chọn chức năng. Theo đó, các công nghệ lựa chọn chức năng có thể đƣợc chia thành 3 loại: Các phương pháp lọc, các phương pháp nhúng, các phương pháp Wrapper [34].
2.4.1 Công nghệ lựa chọn chức năng Wrapper
Các tiếp cận Wrapper đƣợc đề xuất bởi Kohavi và Paeger vào năm 1994 ở phòng nghiên cứu trí tuệ nhân tạo (AI) thuộc trường đại học Stanford [17]. Các phương pháp Wrapper, thuật toán lựa chọn chức năng đƣợc đặt bọc quanh thuật toán học. Quá trình bắt đầu với một việc tìm kiếm tập con có liên quan của các thuộc tính bằng việc sử dụng thuật toán học. Thuật toán học tự nó đƣợc sử dụng để đánh giá các tập con chức năng nhận đƣợc bởi việc tìm kiếm.
Hình 2-10 chỉ ra thuật toán lựa chọn chức năng Wrapper
Hình 2-10 Thuật toán lựa chọn chức năng Wrapper
Thuật toán học đƣợc coi nhƣ là một hộp đen mà ta không cần chỉnh sửa. Thuật toán học đánh giá các tập con chức năng nhận được bởi phương pháp tìm kiếm. Thuật toán chọc nhận đƣợc một giả thuyết về chất lƣợng và sự liên quan của một tập con chức năng cụ thể. Tập con chức năng với giá trị ƣớc lƣợng cao nhất đƣợc lựa chọn để trở thành tập cuối cùng để dựa vào đó nó sẽ chạy thuật toán học. Bước cuối cùng là để đánh giá mô hình dựa trên tập dữ liệu mới ( chƣa đƣợc sử dụng bởi quá trình tìm kiếm) để bảo đảm sự độc lập giữa quá trình học và quá trình kiểm tra. Kết quả là độ chính xác ƣớc lƣợng bằng việc sử dụng tập con chức năng liên quan cao nhất trên thuật toán học mong muốn [18].
Bảng 2-3 chỉ ra các điểm mạnh và yếu của việc sử dụng phương pháp lựa chọn chức năng Wrapper cũng như các ví dụ về các phương pháp đang sử dụng cách tiếp cận wrapper.
Bảng 2-3: Các điểm mạnh và yếu của phương pháp lựa chọn chức năng Wrapper
Điểm mạnh Điểm yếu Các ví dụ
Dễ dàng sử dụng và
triển khai Rủi do của việc do yêu cầu quá trùng kít ( over fitting)
Lựa chọn tuần tự thuận
Tương tác với bộ phân
lớp học Chuyên sâu về sử dụng
máy điện toán ƣớc lƣợng tuần tự ngƣợc
Phụ thuộc vào chức năng của các mô hình
2.4.2 Công nghệ lựa chọn các đặc điểm đặc trƣng chọn lọc
Các công nghệ chọn lọc kiểm tra dấu hiệu của các đặc điểm đặc trƣng bằng việc khảo sát các đặc tính của các thuộc tính thực của dữ liệu. Trong phần lớn các trường hợp, việc phân hạng chức năng đƣợc tính toán, và các đặc điểm đặc trƣng xếp hạng thấp đƣợc bị lờ đi trong quá trình học [34].
Sau cùng, các tập con, các đặc điểm đặc trƣng xếp hạng cao đƣợc sử dụng nhƣ một tập huấn luyện cho thuật toán phân lớp. Sự khác biệt chính của chọn lọc so với wrapper là chọn lọc lờ đi thuật toán học trong quá trinh tìm kiếm tập con các đặc điểm đặc trƣng.
Hình dưới chỉ ra cách tiếp cận chọn lọc. Nó chỉ ra việc trích chọn ra tập con các đặc điểm đặc trƣng là hoàn toàn độc lập với bộ phân lớp học.
Một số điểm mạnh của công nghệ chọn lọc bao gồm:
Chúng có thể đƣợc thực hiện trên tập cơ sở dữ liệu lớn nó chứa đựng một số lƣợng lớn các thuộc tính và các trường hợp, tính toán đơn giản, nhanh so với các phương thức nhúng và wrapper. và chúng độc lập với thuật toán phân lớp. Bên cạnh sự độc lập giữa các bộ chọn lọc và bộ phân lớp học, thì việc lựa chọn đặc điểm đặc trƣng cần đƣợc thực hiện chỉ duy nhất một lần và sau đó các bộ phân lớp khác có thể đƣợc sử dụng để đánh giá tập con. Mặt khác, sự độc lập giữa các phương pháp chọn lọc và các thuật toán học có thể gây ra độ chính xác trong việc phân lớp thấp hơn [34].
Bảng 2-4 khái quát các điểm mạnh chính và các thách thức của phương pháp chọn lọc và một số ví dụ của phương pháp chọn lọc phổ biến
Các điểm đặc trƣng đầu vào
Lựa chọn các tập con đặc điểm đặc trƣng
Thuật toán quy nạp
Bảng 2-4 Khái quát các điểm mạnh chính và các thách thức của phương pháp chọn lọc
Điểm mạnh Điểm yếu Các ví dụ áp dụng
Tương đối nhanh Lờ đi sự phụ thuộc vào các
đặc điểm đặc trưng Phương pháp Lựa chọn đặc điểm đặc trƣng dựa trên sự tương quan
Có tính co dãn Lờ đi sự tương tác với bộ
phân lớp Phương pháp Relief
Độc lập với bộ phân lớp
2.4.3 Công nghệ chọn đặc điểm đặc trƣng nhúng
Các phương pháp nhúng (EM) biến đổi từ các phương pháp lựa chọn đặc điểm đặc trưng khác bằng cách phối hợp giữa phương pháp lựa chọn đặc điểm đặc trưng và các phương pháp phân lớp.
Trong phương pháp wrapper, bộ phân lớp được sử dụng để đo lường chất lượng của các tập dữ liệu con của các đặc điểm đặc trƣng mà không căn thiệp vào cấu trúc của bộ phân lớp.
Trái ngược với chọn lọc và các cách tiếp cận wrapper, các phương pháp lựa chọn đặc điểm đặc trƣng nhúng và quá trình học không tách rời nhau [26].
Quá trình tìm tập con dữ liệu tối ƣu đƣợc kết hợp vào trong việc xây dựng bộ phân lớp. Chi phí tính toán EM thì rẻ hơn các phương pháp wrapper và một sự thật là có một sự tương tác giữa bộ phân lớp và EM.
Bảng 2-5 Các điểm mạnh và điểm yếu của việc sử dụng phương pháp EM
Điểm mạnh Điểm yếu Các ví dụ ứng dụng
Tương tác với bộ phân lớp
Lựa chọn phụ thuộc vào bộ phân lớp
Cây quyết định Tính toán các bài toán
phức tạp tốt hơn phương pháp wrapper
Phương pháp Naive Bayes theo trọng số
2.4.4 Công nghệ lựa chọn đặc điểm đặc trƣng tăng tin IG
Phương pháp sự tăng tin được đề xuất để xấp xỉ chất lượng của từng thuộc tính sử dụng cách tính entropy bằng cách ước lượng sự khác nhau giữa entropy trước và entropy
sau [19]. Đây là một trong những phương pháp xếp hạng thuộc tính đơn giản nhất và thường được sử dụng trong việc phân loại hoá các văn bản. Nếu x là một thuộc tính và c là lớp, công thức sau tính entropy của lớp trước khi quan sát các thuộc tính
log2 x
H x P x P x (2-11)
Trong đó P c là hàm xác xuất theo biến c. Entropy có điều kiện của c khi đã biết x (entropy sau) đƣợc biểu diễn bởi:
(2-12) Lượng thông tin thu được ( sự khác nhau giữa entropy trước và entropy sau) được biểu diễn bởi công thức sau:
(2-13)
(2-14)
Phương pháp phân tích thành phần chính (PCA)
Mục đích của PCA là để giảm kích thước tập cơ sở dữ liệu nó chứa đựng một số lớn các thuộc tính tương quan nhau bằng việc biến đổi không gian thuộc tính gốc thành không gian thuộc tính tính mới trong đó các thuộc tính không tương quan nhau.
Thuật toán sau đó xếp hạng sự thay đổi giữa tập dữ liệu gốc và tập dữ liệu mới. Các thuộc tính đƣợc biến đổi với sự thay đổi nhiều nhất đƣợc giữ lại và sẽ loại bỏ các thuộc tính còn lại.
Ngoài việc quan trọng đƣợc nhấn mạnh ở trên PCA để thẩm định cho các tập dữ liệu chƣa đƣợc giám sát bởi vì nó chƣa đƣợc gán nhãn lớp.