Nghiên Cứu Phương Pháp Trích Chọn Đặc Trưng Bằng Giải Thuật Random Forest

Luận văn thạc sĩ kỹ thuật phân tích vnu uet nghiên cứu xây dựng phương pháp trích chọn đặc trưng dựa trên giải thuật phân lớp random, đánh giá thực trạng, chỉ ra hạn chế, đề xuất

• Tác giả: Nguyễn Cương
• Người hướng dẫn: TS. Nguyễn Hà Nam
• Trường học: Trường Đại học Công nghệ - Đại học Quốc gia Hà Nội
• Chuyên ngành: Công nghệ thông tin
• Đề tài: Nghiên cứu, Xây dựng Phương pháp Trích chọn Đặc trưng dựa trên Giải thuật Phân lớp Random Forest
• Loại tài liệu: Luận văn thạc sĩ
• Năm xuất bản: 2010
• Địa điểm: Hà Nội

Mục lục chi tiết

• LỜI MỞ ĐẦU
• 1. CHƯƠNG 1: TỔNG QUAN
• 1.1. Phát hiện tri thức và khai phá dữ liệu
• 1.2. Chọn lựa thuộc tính (CLTT) và vai trò của CLTT trong KDD
• 1.3. Chọn lựa thuộc tính và bài toán phân lớp
• 2. CHƯƠNG 2: TRÍCH CHỌN THUỘC TÍNH
• 2.1. Chiến lược tìm kiếm
• 2.2. Các chiến lược tìm kiếm
• 2.3. Tiêu chuẩn chọn lựa
• 2.4. Đo lường thông tin
• 2.5. Đo lường khoảng cách
• 2.6. Đo lường phụ thuộc
• 2.7. Đo lường độ đồng nhất
• 2.8. Đo lường chính xác
• 2.9. Mô hình Filter và Wrapper
• 2.9.1. Mô hình Wrapper
• 2.9.2. Mô hình Filter
• 3. CHƯƠNG 3: MỘT SỐ GIẢI THUẬT TRÍCH CHỌN THUỘC TÍNH
• 3.1. Tìm kiếm toàn bộ
• 3.2. Phương pháp Focus
• 3.3. Phương pháp ABB
• 3.4. Tìm kiếm theo kinh nghiệm
• 3.5. Phương pháp LVF
• 3.6. Phương pháp LVW
• 3.7. Phương pháp trọng số thuộc tính
• 3.8. Phương pháp lai
• 3.9. Phương pháp lớn dần
• 4. CHƯƠNG 4: GIẢI THUẬT RANDOM FOREST
• 4.1. Bootstrap và Bagging
• 4.2. Một số điểm cần chú ý của giải thuật Random Forest
• 4.3. Thuộc tính quan trọng
• 5. CHƯƠNG 5: PHƯƠNG PHÁP HỌC MÁY ĐỀ XUẤT
• 5.1. Một số kỹ thuật sử dụng trong phương pháp đề xuất
• 5.2. Kiểm chứng chéo (cross-validation)
• 5.3. Phân lớp Native Bayes
• 5.4. Sơ đồ khối và mô hình phương pháp học máy đề xuất
• 5.5. Mô tả phương pháp học máy đề xuất
• 6. CHƯƠNG 6: KẾT QUẢ THỰC NGHIỆM
• 6.1. Dữ liệu Madelon
• 6.2. Mô tả bộ dữ liệu Madelon
• 6.3. Kết quả thực nghiệm với bộ dữ liệu Madelon
• 6.4. Bộ dữ liệu Colon Turmo
• 6.5. Mô tả bộ dữ liệu Colon Turmo
• 6.6. Kết quả thực nghiệm với bộ dữ liệu Colon Turmo
• DANH MỤC TÀI LIỆU THAM KHẢO

Tóm tắt

I. Tổng quan về Phương Pháp Trích Chọn Đặc Trưng Dựa Trên Giải Thuật Random Forest

Phương pháp trích chọn đặc trưng dựa trên giải thuật Random Forest đã trở thành một công cụ quan trọng trong lĩnh vực học máy. Giải thuật này không chỉ giúp cải thiện độ chính xác của mô hình mà còn giảm thiểu chi phí tính toán. Random Forest hoạt động dựa trên nguyên lý kết hợp nhiều cây quyết định để đưa ra dự đoán chính xác hơn. Việc trích chọn đặc trưng là một bước quan trọng trong quy trình khai thác dữ liệu, giúp loại bỏ các thuộc tính không cần thiết và tập trung vào những yếu tố quan trọng nhất.

1.1. Khái niệm về Random Forest và ứng dụng trong học máy

Random Forest là một giải thuật học máy mạnh mẽ, được sử dụng rộng rãi trong phân loại và hồi quy. Giải thuật này hoạt động bằng cách xây dựng nhiều cây quyết định và kết hợp kết quả của chúng để đưa ra dự đoán cuối cùng. Ứng dụng của Random Forest rất đa dạng, từ phân loại hình ảnh đến dự đoán rủi ro tín dụng.

1.2. Tại sao cần trích chọn đặc trưng trong học máy

Trích chọn đặc trưng giúp giảm thiểu độ phức tạp của mô hình, cải thiện tốc độ tính toán và tăng cường độ chính xác. Việc loại bỏ các thuộc tính không cần thiết giúp mô hình dễ dàng hơn trong việc học và giảm thiểu hiện tượng overfitting.

II. Vấn đề và Thách thức trong Trích Chọn Đặc Trưng

Mặc dù phương pháp trích chọn đặc trưng dựa trên Random Forest mang lại nhiều lợi ích, nhưng vẫn tồn tại một số thách thức. Một trong những vấn đề chính là việc xác định thuộc tính nào là quan trọng nhất. Ngoài ra, việc xử lý dữ liệu không đồng nhất và thiếu dữ liệu cũng là những thách thức lớn trong quá trình này.

2.1. Các vấn đề thường gặp trong trích chọn đặc trưng

Các vấn đề như dữ liệu không đồng nhất, thiếu dữ liệu và sự phụ thuộc giữa các thuộc tính có thể ảnh hưởng đến hiệu quả của quá trình trích chọn. Việc xác định thuộc tính quan trọng cũng có thể gặp khó khăn do sự tương tác phức tạp giữa các thuộc tính.

2.2. Giải pháp cho các thách thức trong trích chọn đặc trưng

Sử dụng các kỹ thuật như kiểm chứng chéo (cross-validation) và các phương pháp thống kê có thể giúp cải thiện độ chính xác trong việc xác định thuộc tính quan trọng. Ngoài ra, việc áp dụng các mô hình học sâu cũng có thể giúp giải quyết một số vấn đề liên quan đến dữ liệu không đồng nhất.

III. Phương Pháp Trích Chọn Đặc Trưng Dựa Trên Random Forest

Phương pháp trích chọn đặc trưng dựa trên Random Forest sử dụng các chỉ số như độ quan trọng của thuộc tính để xác định các thuộc tính cần thiết cho mô hình. Các thuộc tính có độ quan trọng cao sẽ được giữ lại, trong khi các thuộc tính có độ quan trọng thấp sẽ bị loại bỏ. Điều này giúp tối ưu hóa mô hình và cải thiện hiệu suất.

3.1. Cách thức hoạt động của Random Forest trong trích chọn đặc trưng

Random Forest sử dụng một tập hợp các cây quyết định để đánh giá độ quan trọng của từng thuộc tính. Mỗi cây sẽ đưa ra một dự đoán và kết quả cuối cùng sẽ là sự kết hợp của tất cả các dự đoán này. Độ quan trọng của thuộc tính được tính toán dựa trên sự giảm thiểu độ chính xác khi thuộc tính đó bị loại bỏ.

3.2. Các kỹ thuật tối ưu hóa mô hình với Random Forest

Các kỹ thuật như điều chỉnh tham số (hyperparameter tuning) và sử dụng các phương pháp ensemble có thể giúp cải thiện hiệu suất của mô hình Random Forest. Việc tối ưu hóa số lượng cây và độ sâu của cây cũng là những yếu tố quan trọng trong việc nâng cao độ chính xác.

IV. Ứng Dụng Thực Tiễn của Phương Pháp Trích Chọn Đặc Trưng

Phương pháp trích chọn đặc trưng dựa trên Random Forest đã được áp dụng thành công trong nhiều lĩnh vực khác nhau, từ y tế đến tài chính. Trong y tế, nó được sử dụng để phân loại bệnh nhân dựa trên các đặc điểm sinh học. Trong tài chính, nó giúp dự đoán rủi ro tín dụng và phát hiện gian lận.

4.1. Ứng dụng trong lĩnh vực y tế

Trong lĩnh vực y tế, Random Forest được sử dụng để phân tích dữ liệu bệnh nhân và dự đoán các bệnh lý tiềm ẩn. Việc trích chọn đặc trưng giúp xác định các yếu tố nguy cơ chính, từ đó hỗ trợ bác sĩ trong việc đưa ra quyết định điều trị.

4.2. Ứng dụng trong lĩnh vực tài chính

Trong lĩnh vực tài chính, phương pháp này giúp phân tích hành vi khách hàng và dự đoán rủi ro tín dụng. Việc trích chọn đặc trưng giúp cải thiện độ chính xác của các mô hình dự đoán, từ đó giảm thiểu rủi ro cho các tổ chức tài chính.

V. Kết Luận và Tương Lai của Phương Pháp Trích Chọn Đặc Trưng

Phương pháp trích chọn đặc trưng dựa trên Random Forest đã chứng minh được hiệu quả trong nhiều ứng dụng thực tiễn. Tương lai của phương pháp này hứa hẹn sẽ còn phát triển hơn nữa với sự tiến bộ của công nghệ học máy và trí tuệ nhân tạo. Việc kết hợp Random Forest với các kỹ thuật học sâu có thể mở ra nhiều cơ hội mới trong việc khai thác dữ liệu.

5.1. Xu hướng phát triển trong nghiên cứu

Nghiên cứu về Random Forest và trích chọn đặc trưng đang ngày càng được quan tâm. Các nghiên cứu mới sẽ tập trung vào việc cải thiện độ chính xác và hiệu suất của mô hình, cũng như ứng dụng trong các lĩnh vực mới.

5.2. Tương lai của học máy và trích chọn đặc trưng

Tương lai của học máy sẽ chứng kiến sự phát triển mạnh mẽ của các phương pháp trích chọn đặc trưng. Việc kết hợp các kỹ thuật học sâu với Random Forest có thể tạo ra những mô hình mạnh mẽ hơn, giúp giải quyết các bài toán phức tạp trong khai thác dữ liệu.

Trích đoạn nội dung tài liệu

Chương 1: Tổng quan Trang 16 LUAN VAN CHAT LUONG download : add [e-mail] Chương 2: Trích chọn thuộc tính Trích chọn thuộc tính được xem như là sự tổng hợp của ba thành phần chính: (1)Tìm kiếm, Đánh ra, Chọn lựa mô hình.1 dưới đây [3] thể hiện trích chọn thuộc tính theo 3 thành phần nói trên. 1: Ba thành phần chính của chọn lựa thuộc tính: Chiến lược tìm kiếm, Đánh giá, Chọn lựa mô hình 2. Chiến lược tìm kiếm Chọn lựa thuộc tính có thể được xem dưới góc độ như là một vấn đề tìm kiếm, trong đó mỗi bước trong không gian tìm kiếm xác định ra một tập con thuộc tính liên quan. Giả sử ta có một tập dữ liệu với 3 thuộc tính (A1, A2, A3).

Một mảng nhị phân mà mỗi thành phần của mảng được thiết lập là 1 nếu thuộc tính có chỉ số tương ứng trong mảng nhị phân được chọn. Nếu mảng có giá trị (1, 1, 1) có nghĩa là cả 3 thuộc tính được chọn và (1, 0, 0) có nghĩa là chỉ thuộc tính A1 được chọn. Do đó, sẽ có tất cả 2N tập con có thể có, trong đó N là số lượng thuộc tính của tập dữ liệu. Trong trường hợp có 3 thuộc tính sẽ có tất cả 8 trạng thái (tập con).

Một tập con tối ưu thường nằm đâu đó giữa điểm đầu và điểm cuối cây. Câu hỏi đặt ra ở đây là: Chúng ta nên bắt đầu tìm kiếm từ đâu. Vấn đề sẽ rất đơn giản nếu không gian tìm kiếm nhỏ. Tuy nhiên, trên thực tế không gian tìm kiếm thường rất lớn (2N), bắt đầu từ câu hỏi “Đâu là điểm tìm Chương 2: Trích chọn thuộc tính Trang 17 LUAN VAN CHAT LUONG download : add [e-mail] kiếm phù hợp” sẽ xuất hiện các câu hỏi khác: Chiến lược tìm kiếm phù hợp là gì ?.

Trên thực tế chiến lược tìm kiếm lại bị ảnh hưởng bởi hướng tìm kiếm, dưới đây chúng ta sẽ lần lượt xem xét hướng tìm kiếm và chiến lược tìm kiếm. Hướng tìm kiếm Giả sử chúng ta ban đầu chưa có một khái niệm cụ thể nào về tập thuộc tính tối ưu trong không gian tìm kiếm, thì sẽ không có sự khác biệt trong việc xác định điểm xuất phát nên bắt đầu từ đâu (một tập rỗng hay một tập đủ các thuộc tính). Do đó, đối với phần lớn các vấn đề trong tìm kiếm thì trung bình thời gian để 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. Tuy nhiên, hướng tìm kiếm lại có mối liên hệ chặt chẽ trong việc tạo ra tập con thuộc tính.

Một phương pháp tìm kiếm là tìm ra tập con tối ưu bắt đầu từ một tập rỗng các thuộc tính (Ví dụ: Sequential Forward Generation), phương pháp còn lại là tìm ra tập con tối ưu bằng cách lần lượt loại bỏ các thuộc tính ít quan trọng từ một tập đủ các thuộc tính ban đầu (Ví dụ: Sequential Backward Generation). Sequential forward generation (SFG): Được bắt đầu bằng một tập rỗng các thuộc tính, Sselect. Ở mỗi lần tìm kiếm một thuộc tính được thêm vào tập Sselect (do đó gọi là tuần tự). Trong mỗi lần tìm kiếm dựa trên một số tiêu chí, một thuộc tính tốt nhất trong số các thuộc tính chưa được chọn lựa sẽ được chọn để 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 thuộc tính trong tập thuộc tính ban đầu được thêm vào Sselect. Một danh sách xếp hạng các thuộc tính được tạo ra theo trình tự thời gian các thuộc tính được thêm vào tập Sselect. Nếu ta biết trước một số thông tin về số lượng thuộc tính liên quan, thì một cách đơn giản chúng ta có thể chọn m thuộc tính đầu tiên trong danh sách xếp hạng. Sequential backward generation (SBG): Được bắt đầu với một tập đủ các thuộc tính, tại mỗi lần tìm kiếm dựa vào một số tiêu chí nào đó, một thuộc tính ít quan trọng sẽ bị loại bỏ.

Do đó, các thuộc tính trong tập thuộc tính sẽ dần dần bị loại bỏ cho tới khi trong tập thuộc tính chỉ còn lại một thuộc tính. Một danh sách xếp hạng các thuộc tính theo thời gian bị loại bỏ từ thấp đến cao được tạo ra. Thuộc tính bị loại bỏ cuối cùng sẽ là thuộc tính quan trọng nhất. SBG và SFG là hai phương pháp bổ xung cho nhau vì đôi khi tìm ra thuộc tính quan trọng nhất là dễ dàng hơn so với tìm ra thuộc tính ít quan trọng và ngược lại.

Nếu trong trường hợp tồn tại một tập thuộc tính tối ưu mà tập thuộc tính này lại không nằm trong khu vực giữa của không gian tìm kiếm, thì việc chúng ta 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 tối ưu. Một cách trực quan, Chương 2: Trích chọn thuộc tính Trang 18 LUAN VAN CHAT LUONG download : add [e-mail] chúng ta thấy rằng phương pháp này sẽ chạy nhanh hơn phương pháp tìm kiếm theo một hướng. Dưới đây, ta sẽ sem xét phương pháp này. Birectional Generation(BG): Được bắt đầu ở cả hai hướng trong không gian tìm kiếm, ví dụ hai quá trình tìm kiếm được thực hiện đồng thời.

Quá trình tìm kiếm sẽ dừng lại khi gặp một trong hai trường hợp sau: (1) Khi một trong hai chiều tìm kiếm tìm được tập m thuộc tính tốt nhất trước khi đi đến điểm giữa trong không gian tìm kiếm, hoặc (2) Cả hai chiều tìm kiếm đến điểm giữa trong không gian tìm kiếm. Nếu giả sử giả thuyết là chúng ta hoàn toàn chưa có thông tin về m thuộc tính tốt nhất là đúng thì trong mọi trường hợp, tìm kiếm theo một chiều sẽ mất một nửa thời gian để đi đến điểm giữa của không gian tìm kiếm. Phương pháp BG sẽ tránh được nhược điểm trên. Random Generation(RG): Bắt đầu tìm kiếm theo một hướng ngẫu nhiên.

Thêm hay loại bỏ bớt một thuộc tính cũng được thực hiện một cách ngẫu nhiên. RG cố gắng tránh việc gặp tối ưu địa phương do việc cố định chỉ đi theo một chiều nào đó trong việc tạo ra tập thuộc tính tối ưu. Không giống như FSG hay FBG, kích cỡ của tập con thuộc tính được tạo ra tiếp theo không được xác định. Tuy nhiên, chúng ta có thể thấy được xu hướng của số lượng thuộc tính được chọn là tăng lên hay giảm đi.

Các chiến lược tìm kiếm Trong trường hợp số lượng thuộc tính (N) là nhỏ thì không gian tìm kiếm là không lớn. Tuy nhiên không gian tìm kiếm sẽ tăng theo hàm mũ khi N tăng do mối quan hệ S=2N, trong đó S là không gian tìm kiếm với N thuộc tính và 2 biểu thị việc chọn hay không chọn một thuộc tính. Câu hỏi về chiến lược tìm kiếm nào được chọn đặt ra trong trường hợp không gian tìm kiếm là lớn. Cũng cần lưu ý rằng trong một không gian tìm kiếm nếu tìm kiếm càng nhiều (càng kỹ) có nghĩa là sẽ tìm được một tập con tốt hơn.

Tuy nhiên, tìm kiếm nhiều có nghĩa là sẽ mất nhiều thời gian và nguồn lực mà chúng ta lại thường luôn hạn chế về nguồn lực. Do vậy, mục đích là tìm được một tập con tối ưu nhất có thể trong thời gian ít nhất có thể. 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ộ (Exhausive/Complete Search): Đây là phương pháp tìm tất cả các khả năng có thể của các tập con sau đó tìm một tập con tối ưu nhất.

Nhìn chung, độ phức tạp không gian của phương pháp này (số lượng tập con cần tạo ra) là O(2N). Nếu chúng ta biết được hướng tìm kiếm, thì không gian tìm kiếm là (N0) + (N1) + …+ (NM), trong đó M là số lượng thuộc tính 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 đó. Chương 2: Trích chọn thuộc tính Trang 19 LUAN VAN CHAT LUONG download : add [e-mail] Tìm kiếm theo kinh nghiệm (Heuristic Search): Như tên gọi của phương pháp, phương pháp tìm kiếm theo kinh nghiệm được triển khai trong khi tìm kiếm, điều này tránh được việc tìm kiếm một cách khô cứng, máy móc (brute-force search) nhưng phương pháp này cũng đi cùng với nguy cơ không tìm được các tập con tối ưu. Độ phức tạp không gian của phương pháp tìm kiếm theo kinh nhiệm là đường đi nối từ điểm bắt đầu đến điểm kết thúc (điểm tìm ra tập con tối ưu).

Độ dài tối đa của đường đi này là N và số lượng tập con được tạo ra là O(N). Phương pháp tìm kiếm theo kinh nghiệm cho ra kết quả nhanh hơn so với phương pháp tìm kiếm toàn bộ, do phương pháp này chỉ tìm kiếm theo một đường đi cụ thể và tìm ra một tập con gần tối ưu. Tìm kiếm không xác đinh(Nondeterministic Search): Không giống như hai chiến lược tìm kiếm được trình bày ở trên, chiến lược này tìm kiếm tập con kế tiếp theo kiểu ngẫu nhiên. Có hai đặc điểm chính của chiến lược tìm kiếm này: (1) Chúng ta không cần phải đợi cho đến khi tìm kiếm kết thúc; và (2) Chúng ta không biết khi nào tập tối ưu được xuất hiện mặc dù chúng ta biết rằng tại mỗi bước có một tập tốt hơn xuất hiện.2 dưới đây thể hiện mối quan hệ giữa hướng tìm kiếm và chiến lược tìm kiếm.

X thể hiện sự kết hợp giữa chiến lược tìm kiếm và hướng tìm kiếm là không khả thi. Chiến lược tìm kiếm Hướng tìm kiếm Toàn bộ Kinh nghiệm Không xác định SFG √ √ × SBG √ √ × BG √ √ × RG × √ √ Bảng 2. 1 : Chiến lược tìm kiếm và hướng tìm kiếm 2. Tiêu chuẩn chọn lựa Tất cả các chiến lược tìm kiếm đều có nhu cầu đánh giá một thuộc tính hoặc một tập con thuộc tính để xác định thuộc tính/tập con đó là tốt hay không tốt.

Việc đánh giá này thường là phức tạp và có nhiều chiều đánh giá. Ví dụ, đánh giá có thể được đo lường theo những khía cạnh (1) Các thuộc tính được chọn lựa có làm tăng độ chính Chương 2: Trích chọn thuộc tính Trang 20 LUAN VAN CHAT LUONG download : add [e-mail] xác của bộ phân lớp hay không và (2) Các thuộc tính được chọn lựa có giúp làm đơn giản các kết quả học do đó sẽ các kết quả này có thể dễ dàng để hiểu hay không… Dưới đây là một số đo lường thường được sử dụng trong trích chọn thuộc tính. Đo lường thông tin Thông tin là một cách đo lường độ không ổn định của người nhận tin khi một người nhận tất cả các tin nhắn. Nếu người nhận tin biết được tin nhắn nào đang đến thì sự ngạc nhiên (uncertainty) của anh ta sẽ thấp.