phần mở đầu, mục lục, kết luận và tài liệu tham khảo, nội dung chính của luận án này đƣợc chia thành 03 chƣơng, cụ thể nhƣ sau: 5 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Chƣơng 1: Phần đầu giới thiệu về lý thuyết cơ bản liên quan tới rút gọn đặc trƣng, lựa chọn đặc trƣng và trích xuất đặc trƣng, đồng thời điểm lại một số nghiên cứu gần đây. Sau phần phân tích, đánh giá là kết luận của chƣơng. Chƣơng 2: Đề xuất một hàm đánh giá đặc trƣng và áp dụng chiến lƣợc tìm kiếm theo kinh nghiệm dựa trên hàm đánh giá này nhằm nâng hiệu quả của việc lựa chọn đặc trƣng. Sau khi trình bày về quy trình, giải pháp đề xuất, luận án áp dụng phƣơng pháp đề xuất cho bộ dữ liệu tín dụng.
Phần còn lại của chƣơng thực hiện thực nghiệm trên các bộ dữ liệu tín dụng và so sánh kết quả với một số phƣơng pháp lựa chọn đặc trƣng khác. Chƣơng 3: Đề xuất một phƣơng pháp trích xuất đặc trƣng dựa trên việc xây dựng một hàm nhân mới trên cơ sở kết hợp một số hàm nhân cơ bản nhằm biến đổi không gian đặc trƣng phù hợp với miền dữ liệu. Sau khi trình bày về quy trình, phƣơng pháp đề xuất, phƣơng pháp đề xuất đƣợc tiến hành trênbốn bộ dữ liệu ung thƣ. Việc thực nghiệm và so sánh với một số kỹ thuật khác đƣợc thực hiện ở phần còn lại của chƣơng.
6 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Chƣơng 1. TỔNG QUAN VỀ RÚT GỌN ĐẶC TRƢNG Hầu hết các lĩnh vực khoa học và công nghệ ngày nay đều đòi hỏi phân tích dữ liệu nhằm bóc tách các tri thức hữu ích giúp cải tiến hay nâng cao hiệu quả của các lĩnh vực này. Dữ liệu quan sát và thu thập đƣợc từ những ứng dụng trong thực tế thƣờng chứa nhiều thông tin nhiễu, dƣ thừa, đặc biệt vớitập dữ liệu có số lƣợng thuộc tính lớn cóthể dẫn tới việc tốn kém tài nguyên khiáp dụng kỹ thuật phân tích dữ liệu, và nhiều trƣờng hợp không thể thực hiện đƣợc. Xuất phát từ nhu cầu thực tiễn đó, các kỹ thuật rút gọn đặc trƣng đƣợc nghiên cứu và phát triển để giải quyết những vấn đề trên.
Nội dung chƣơng này nhằm giới thiệu tổng quan về vấn đề rút gọn đặc trƣng và điểm lại một số hƣớng nghiên cứu về rút gọn đặc trƣng tiêu biểu hiện nay. Phần cuối của chƣơng sẽ đƣa ra một số phân tích, đánh giá một số kỹ thuật rút gọn đặc trƣng thƣờng đƣợc áp dụng hiện nay.1 Rút gọn đặc trƣng Rút gọn đặc trƣng đƣợc hiểu là quá trình thu gọn hoặc biến đổi không gian biểu diễn dữ liệu ban đầu thành một không gian con hoặc một không gian mới có số đặc trƣng nhỏ hơn không gian ban đầu mà vẫn giữ đƣợc các đặc tính của dữ liệu gốc. Trong nhiều trƣờng hợp, tập dữ liệu ban đầu có chứa nhiều đặc trƣng không liên quan cho sự mô tả bản chất của hiện tƣợng mà ta quan tâm, khi đó có thể loại bỏ các đặc trƣng không liên quan này và chỉ giữ lại các đặc trƣng quan trọng. Có hai phƣơng pháp để rút gọn đặc trƣng gồm lựa chọn đặc trƣng và trích xuất đặc trƣng.2 Lựa chọn đặc trƣng - Lựa chọn đặc trưng (Feature Selection): chọn lựa một tập con các đặc trƣng từ các đặc trƣng ban đầu mà không có sự thay đổi về giá trị của đặc trƣng.1 Lựa chọn đặc trƣng.
7 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Lựa chọn đặc trƣng là một trong những phƣơng pháp hết sức tự nhiên để giải quyết vấn đề loại bỏ các đặc trƣng dƣ thừa, trùng lặp và không liên quan trong dữ liệu. Kết quả của lựa chọn đặc trƣng là một tập con các đặc trƣng từ tập đặc trƣng ban đầu nhƣng vẫn đảm bảo các tính chất của dữ liệu gốc. Lựa chọn đặc trƣng giúp: (1) cải tiến hiệu năng (về tốc độ, khả năng dự đoán, và đơn giản hóa mô hình); (2) trực quan hóa dữ liệu cho việc lựa chọn mô hình; (3) giảm chiều và loại bỏ nhiễu.1 Mục tiêu của lựa chọn đặc trưng Mục tiêu chính của lựa chọn đặc trƣng là xác định các đặc trƣng quan trọng và loại bỏ các đặc trƣng không liên quan hoặc không phù hợp. Các thuật toán lựa chọn đặc trƣng khác nhau sẽ có thể có các mục tiêu khác nhau.
Một số mục tiêu thƣờng đƣợc sử dụng: - Tìm ra tập con các đặc trƣng có kích cỡ nhỏ nhất có thể, mà nó là cần và đủ cho việc phân tích dữ liệu (cụ thể ở đây là phân lớp) - Chọn một tập con có M đặc trƣng từ một tập gồm N đặc trƣng ban đầu (M<N), trong đó giá trị của hàm mục tiêu đƣợc tối ƣu trên tập con kích cỡ M. - Chọn một tập con các đặc trƣng nhằm cải tiến độ chính xác dự đoán hoặc làm giảm kích cỡ của tập dữ liệu mà không làm giảm độ chính xác dự đoán của bộ phân lớp.2 Phân loại các kỹ thuật lựa chọn đặc trưng Dựa vào tính sẵn có của thông tin nhãn lớp (label), kỹ thuật lựa chọn đặc trƣng có thể đƣợc chia thành ba loại: phƣơng pháp có giám sát, bán giám sát, và không giám sát. Thông tin nhãn có sẵn của lớp giúp cho các thuật toán lựa chọn đặc trƣng có giám sát lựa chọn đƣợc các đặc trƣng phù hợp. Khi chỉ có một số ít dữ liệu đã đƣợc gán nhãn, có thể sử dụng lựa chọn đặc trƣng bán giám sát, trong đó có thể tận dụng đƣợc lợi thế của cả dữ liệu đƣợc gán nhãn và dữ liệu không đƣợc gán nhãn.
Hầu hết các thuật toán lựa chọn đặc trƣng bán giám sátđều dựa trên việc xây dựng ma trận tƣơng tự và lựa chọn các đặc trƣng phù hợp nhất với ma trận tƣơng tự đó. 8 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.3 Các thành phần chính của lựa chọn đặc trưng Liu và Motoda[59] chỉ ra ba thành phần chính của lựa chọn đặc trƣng là: (1) Chiến lƣợc tìm kiếm tập con, (2) Hƣớng tìm kiếm hay nguyên tắc lựa chọn, bổ sung, loại bỏ hoặc thay đổi đặc trƣng trong quá trình tìm kiếm, và (3) Tiêu chí đánh giá các tập con khác nhau.2 dƣới đây thể hiện lựa chọn đặc trƣng theo 3 thành phần nói trên. Tiêu chí đánh giá Chính xác Nhất quán Toàn bộ Kinh nghiệm Không xác định Cơ bản Chiến lƣợc tìm kiếm Tiến Lùi Ngẫu nhiên Hƣớng tìm kiếm Hình 1.2 Ba thành phần chính của lựa chọn đặc trƣng[59] (1) Chiến lƣợc tìm kiếm Do số tập con là 2N nên không gian tìm kiếm sẽ tăng theo hàm mũ khi N tăng lên. Không gian tìm kiếm sẽ là tƣơng đối nhỏ khi số lƣợng đặc trƣng N là nhỏ.
Khi không gian tìm kiếm lớn thì chiến lƣợc tìm kiếm đƣợc sử dụng sẽ ảnh hƣởng lớn tới hiệu năng của nó. Kết quả tìm kiếm phụ thuộc vào việc lựa chọn chiến lƣợc tìm kiếm. Mục tiêu là tìm đƣợc một tập con các đặc trƣng tối ƣu trong thời gian ít nhất có thể theo các tiêu chí cho trƣớc. Các chiến lƣợc tìm kiếm có thể đƣợc chia thành 3 nhóm dƣới đây.
Tìm kiếm toàn bộ (chiến lược vét cạn): trong chiến lƣợc này, tất cả các khả năng có thể của các tập con sẽ đƣợc kiểm tra. Kết quả cuối cùng một tập con tốt 9 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com nhất theo tiêu chí tìm kiếm. Độ phức tạp không gian của chiến lƣợc này trong trƣờng hợp tổng quát nhất là 𝛰 2𝑁. Khi biết trƣớc đƣợc hƣớng tìm kiếm, thì không 𝑁 gian tìm kiếm sẽ là 0 + 𝑁1 + ⋯ + 𝑀 𝑁 Trong đó, M là số lƣợng đặc trƣng tối thiểu của một tập con thỏa mãn một số tiêu chí đánh giá nào đó.
Tìm kiếm theo kinh nghiệm: là quá trình tìm kiếm sử dụng hàm đánh giá để hƣớng dẫn sự tìm kiếm. Mục tiêu của hàm đánh giá nhằm xác định theo kinh nghiệm định hƣớng để tìm đƣợc tập con tối ƣu. Chiến lƣợc tìm kiếm theo kinh nghiệm chỉ thực hiện theo một lộ trình cụ thể và tìm ra một tập con gần tối ƣu nên nó cho kết quả nhanh hơn so với chiến lƣợc tìm kiếm vét cạn. Tìm kiếm không xác định: chiến lƣợc này khác với hai chiến lƣợc kể trên ở chỗ nó tìm kiếm tập con kế tiếp một cách ngẫu nhiên.
Chiến lƣợc này thƣờng đƣợc áp dụng trong không gian tìm kiếm khá lớn và tồn tại nhiều giá trị tối ƣu cục bộ. Ƣu điểm chính là của chiến lƣợc này là tránh đƣợc các tối ƣu cục bộ và tƣơng đối dễ cài đặt. (2)Hƣớng tìm kiếm Việc tìm kiếm tập con các đặc trƣng tối ƣu trong không gian tìm kiếm có thể bắt đầu từ một tập rỗng sau đó lần lƣợt thêm từng đặc trƣng hoặc bắt đầu từ một tập đủ các đặc trƣng rồi loại bỏ từng đặc trƣng. Với việc tìm kiếm nhƣ vậy thì thời gian trung bình để tìm ra tập con tối ƣu giữa các hƣớng tìm kiếm khác nhau không có sự khác biệt.
Việc tạo ra tập con các đặc trƣng có mối liên hệ chặt chẽ với hƣớng tìm kiếm. Tìm kiếm tiến tuần tự(Sequential Forward Generation-SFG): Bắt đầu từ một tập rỗng các đặc trƣng Sselect Tại mỗi bƣớc tìm kiếm, dựa trên một số tiêu chí nhất định, một đặc trƣng đƣợc thêm vào tập Sselect. Quá trình tìm kiếm này sẽ dừng lại khi tất cả các đặc trƣng trong tập đặc trƣng ban đầu đƣợc thêm vào Sselect. Kết quả là một danh sách xếp hạng các đặc trƣng đƣợc tạo ra theo thứ tự đƣợc thêm vào Sselect.
Tìm kiếm lùi tuần tự (Sequential Backward Generation-SBG): Bắt đầu với một tập đủ các đặc trƣng. Tại mỗi bƣớc tìm kiếm dựa vào một số tiêu chí nào đó, 10 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com một đặc trƣng ít quan trọng nhất sẽ bị loại bỏ. Các đặc trƣng trong tập đặc trƣng sẽ dần bị loại bỏ cho tới khi trong tập đặc trƣng chỉ còn lại một đặc trƣng. Kết quả là một danh sách xếp hạng các đặc trƣng theo thứ tự bị loại đƣợc tạo ra.
SBG và SFG là hai phƣơng pháp bổ sung cho nhau vì đôi khi tìm ra đặc trƣng quan trọng nhất là dễ dàng hơn so với tìm ra đặc trƣng ít quan trọng và ngƣợc lại. Tìm kiếm theo hai hướng (Birectional Generation-BG): Nếu trong trƣờng hợp tập đặc trƣng tối ƣu không nằm trong khu vực giữa của không gian tìm kiếm, thì việc bắt đầu tìm kiếm từ cả hai phía của không gian tìm kiếm là giải pháp phù hợp. Quá trình tìm kiếm sẽ đƣợc bắt đầu từ hai hƣớng một cách đồng thời.