Nghiên Cứu Phương Pháp Trích Chọn Thuộc Tính Để Tăng Hiệu Quả Phân Lớp Dữ Liệu Đa Chiều

Luận văn thạc sĩ nghiên cứu nghiên cứu xây dựng phương pháp trích chọn thuộc tính nhằm làm tăng hiệu quả phân lớp đối với dữ, đánh giá hiện trạng, phân tích vấn đề, đề xuất biện

• Tác giả: Đồng Thị Ngọc Lan
• Người hướng dẫn: PGS. Nguyễn Hà Nam
• Trường học: Đại Học Quốc Gia Hà Nội
• Chuyên ngành: Công Nghệ Thông Tin
• Đề tài: Phương Pháp Trích Chọn Thuộc Tính Tăng Hiệu Quả Phân Lớp Dữ Liệu Đa Chiều
• Loại tài liệu: luận văn thạc sĩ
• Năm xuất bản: 2012
• Địa điểm: Hà Nội

Mục lục chi tiết

• MỞ ĐẦU
• 1. 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
• 1.2. Lựa chọn thuộc tính và bài toán phân lớp
• 1.3. Phương pháp lựa chọn thuộc tính
• 1.4. Các mô hình lựa chọn thuộc tính
• 1.5. Một số thuật toán lựa chọn thuộc tính
• 1.5.1. Tìm kiếm toàn bộ
• 1.5.2. Tìm kiếm theo kinh nghiệm
• 1.6. Phương pháp trọng số thuộc tính
• 1.7. Phương pháp lai
• 1.8. Phương pháp lớn dần
• 2. CHƯƠNG 2: THUẬT TOÁN RANDOM FOREST VÀ GIẢI THUẬT DI TRUYỀN
• 2.1. Giới thiệu thuật toán Random Forest
• 2.2. Phương pháp Bootstrap và Bagging
• 2.2.1. Phương pháp Bootstrap
• 2.2.2. Phương pháp Bagging
• 2.3. Thuật toán Random Forest
• 2.4. Một số đặc điểm của RF
• 2.5. Giải thuật di truyền
• 2.5.1. Nội dung giải thuật di truyền
• 3. CHƯƠNG 3: PHƯƠNG PHÁP ĐỀ XUẤT
• 3.1. Cơ sở lí luận của phương pháp đề xuất
• 3.2. Kiến trúc hệ thống đề xuất
• 3.3. Nội dung phương pháp đề xuất
• 3.4. Hoạt động của hệ thống đề xuất
• 3.5. Sơ đồ khối phương pháp đề xuất
• 4. CHƯƠNG 4: THỰC NGHIỆM VÀ ĐÁNH GIÁ
• 4.1. Môi trường thực nghiệm
• 4.2. Mô tả chương trình
• 4.3. Kết quả thực nghiệm
• 4.3.1. Bộ dữ liệu ung thư dạ dày (Stomach)
• 4.3.1.1. Mô tả bộ dữ liệu Stomach
• 4.3.1.2. Kết quả và phân tích thực nghiệm trên bộ dữ liệu Stomach
• 4.3.2. Bộ dữ liệu ung thư ruột kết Colon Tumor
• 4.3.2.1. Mô tả dữ liệu
• 4.3.2.2. Kết quả thực nghiệm với bộ dữ liệu Colon Tumor
• TÀI LIỆU THAM KHẢO

Tóm tắt

I. Tổng quan về khai phá dữ liệu và trích chọn thuộc tính

Khai phá dữ liệu là một lĩnh vực quan trọng trong công nghệ thông tin, nhằm phát hiện thông tin có giá trị từ các tập dữ liệu lớn. Phương pháp trích chọn thuộc tính đóng vai trò thiết yếu trong việc giảm kích thước không gian dữ liệu, loại bỏ các thuộc tính không liên quan và nhiễu. Điều này không chỉ giúp cải thiện hiệu suất của các thuật toán phân lớp mà còn nâng cao chất lượng dữ liệu. Các kỹ thuật khai phá dữ liệu thường được chia thành hai nhóm chính: mô tả và dự đoán. Trong đó, phân lớp là một nhiệm vụ quan trọng, giúp phân chia các đối tượng thành các lớp đã biết trước. Việc lựa chọn thuộc tính là cần thiết để đảm bảo rằng các thuộc tính được sử dụng là hữu ích và có liên quan đến bài toán phân lớp.

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 liên quan đến việc phân tích và tìm ra các quy luật trong tập dữ liệu. Trích chọn thuộc tính là quá trình tìm ra 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 như Linear Discriminant Analysis (LDA) và Principal Components Analysis (PCA) thường được sử dụng trong quá trình này. Việc giảm chiều dữ liệu không chỉ giúp tiết kiệm thời gian tính toán mà còn làm cho kết quả dễ hiểu hơn. Phân lớp và phân cụm là hai nhiệm vụ có mối quan hệ chặt chẽ, trong đó phân lớp giúp phân biệt các đối tượng dựa trên các thuộc tính đã biết.

1.2 Lựa chọn thuộc tính và bài toán phân lớp

Nhiệm vụ phân lớp yêu cầu phân chia một tập các đối tượng thành các lớp đã biết trước. Tuy nhiên, số lượng thuộc tính có thể rất lớn, dẫn đến việc cần thiết phải lựa chọn thuộc tính. Các thuộc tính không liên quan hoặc thừa có thể gây ảnh hưởng tiêu cực đến kết quả phân lớp. Việc xác định thuộc tính nào là hữu ích thường không đơn giản, vì nó phụ thuộc vào bản chất của dữ liệu và mục tiêu nghiên cứu. Do đó, việc áp dụng các phương pháp trích chọn thuộc tính là cần thiết để tối ưu hóa quá trình phân lớp và cải thiện độ chính xác của các thuật toán như Random Forest.

II. Thuật toán Random Forest và giải thuật di truyền

Thuật toán Random Forest là một trong những phương pháp phân lớp mạnh mẽ, sử dụng nhiều cây quyết định để cải thiện độ chính xác và giảm thiểu hiện tượng overfitting. Giải thuật di truyền cũng được áp dụng để tối ưu hóa quá trình lựa chọn thuộc tính, giúp tìm ra các thuộc tính quan trọng nhất cho mô hình. Việc kết hợp giữa Random Forest và giải thuật di truyền có thể tạo ra một mô hình phân lớp hiệu quả hơn, đặc biệt trong các bài toán với dữ liệu đa chiều. Các phương pháp như Bootstrap và Bagging được sử dụng để tăng cường độ chính xác của mô hình. Kết quả thực nghiệm cho thấy rằng việc áp dụng các phương pháp này có thể cải thiện đáng kể hiệu suất phân lớp.

2.1 Giới thiệu thuật toán Random Forest

Random Forest là một thuật toán học máy mạnh mẽ, sử dụng nhiều cây quyết định để đưa ra dự đoán. Mỗi cây trong rừng được xây dựng từ một mẫu ngẫu nhiên của dữ liệu, giúp giảm thiểu độ thiên lệch và cải thiện độ chính xác. Phương pháp Bootstrap và Bagging là hai kỹ thuật quan trọng trong Random Forest, cho phép tạo ra nhiều mẫu dữ liệu khác nhau từ tập dữ liệu gốc. Điều này giúp tăng cường khả năng tổng quát của mô hình và giảm thiểu hiện tượng overfitting.

2.2 Giải thuật di truyền

Giải thuật di truyền là một phương pháp tối ưu hóa dựa trên nguyên lý chọn lọc tự nhiên. Trong bối cảnh lựa chọn thuộc tính, giải thuật này giúp tìm ra các thuộc tính quan trọng nhất cho mô hình phân lớp. Bằng cách sử dụng các phép lai và đột biến, giải thuật di truyền có thể khám phá không gian thuộc tính một cách hiệu quả. Kết quả thực nghiệm cho thấy rằng việc kết hợp giải thuật di truyền với Random Forest có thể nâng cao đáng kể hiệu suất phân lớp, đặc biệt trong các bài toán với dữ liệu lớn và phức tạp.

III. Phương pháp đề xuất

Phương pháp đề xuất trong luận văn này tập trung vào việc xây dựng một mô hình lựa chọn thuộc tính tối ưu nhằm tăng hiệu quả phân lớp cho dữ liệu đa chiều. Mô hình này kết hợp giữa các phương pháp trích chọn thuộc tính và các thuật toán phân lớp như Random Forest. Việc áp dụng các kỹ thuật như trích xuất thuộc tính và lựa chọn thuộc tính giúp giảm thiểu số lượng thuộc tính không cần thiết, từ đó cải thiện tốc độ và độ chính xác của quá trình phân lớp. Hệ thống đề xuất được thiết kế với kiến trúc rõ ràng, cho phép dễ dàng áp dụng và kiểm tra trên các bộ dữ liệu khác nhau.

3.1 Cơ sở lý luận của phương pháp đề xuất

Cơ sở lý luận của phương pháp đề xuất dựa trên các nguyên tắc của khai phá dữ liệu và trích chọn thuộc tính. Việc lựa chọn các thuộc tính quan trọng không chỉ giúp cải thiện hiệu suất của các thuật toán phân lớp mà còn giúp giảm thiểu thời gian tính toán. Các nghiên cứu trước đây đã chỉ ra rằng việc áp dụng các phương pháp trích chọn thuộc tính có thể làm tăng đáng kể độ chính xác của mô hình phân lớp. Do đó, phương pháp đề xuất tập trung vào việc tối ưu hóa quá trình này.

3.2 Kiến trúc hệ thống đề xuất

Kiến trúc hệ thống đề xuất bao gồm các thành phần chính như thu thập dữ liệu, tiền xử lý, trích chọn thuộc tính và phân lớp. Mỗi thành phần được thiết kế để hoạt động một cách độc lập nhưng cũng có thể tương tác với nhau. Việc thu thập dữ liệu từ nhiều nguồn khác nhau giúp tạo ra một tập dữ liệu phong phú, trong khi tiền xử lý giúp loại bỏ các thuộc tính không cần thiết. Sau đó, các phương pháp trích chọn thuộc tính được áp dụng để xác định các thuộc tính quan trọng nhất, cuối cùng là sử dụng các thuật toán phân lớp như Random Forest để đưa ra dự đoán.

IV. Thực nghiệm và đánh giá

Phần thực nghiệm của luận văn tập trung vào việc đánh giá hiệu quả của phương pháp đề xuất trên các bộ dữ liệu thực tế. Các bộ dữ liệu như ung thư dạ dày và ung thư ruột kết được sử dụng để kiểm tra tính khả thi và độ chính xác của mô hình. Kết quả thực nghiệm cho thấy rằng phương pháp đề xuất không chỉ cải thiện độ chính xác của các thuật toán phân lớp mà còn giảm thiểu thời gian tính toán. Việc phân tích kết quả thực nghiệm giúp xác định các yếu tố ảnh hưởng đến hiệu suất của mô hình và đưa ra các khuyến nghị cho các nghiên cứu tiếp theo.

4.1 Môi trường thực nghiệm

Môi trường thực nghiệm được thiết lập với các công cụ và phần mềm phù hợp để thực hiện các thí nghiệm. Các bộ dữ liệu được chuẩn bị kỹ lưỡng, đảm bảo tính chính xác và độ tin cậy. Việc sử dụng các thuật toán phân lớp như Random Forest trong môi trường thực nghiệm giúp đánh giá hiệu quả của phương pháp đề xuất một cách khách quan.

4.2 Kết quả thực nghiệm

Kết quả thực nghiệm cho thấy rằng phương pháp đề xuất có thể cải thiện đáng kể độ chính xác của các thuật toán phân lớp. Các số liệu thống kê được thu thập và phân tích để đánh giá hiệu suất của mô hình. Việc so sánh giữa các kết quả trước và sau khi áp dụng phương pháp trích chọn thuộc tính cho thấy sự khác biệt rõ rệt, chứng minh tính khả thi và hiệu quả của phương pháp đề xuất.

Nội dung chính

Tổng quan nghiên cứu

Trong bối cảnh bùng nổ dữ liệu hiện nay, việc xử lý và phân tích khối lượng dữ liệu đa chiều lớn trở thành thách thức quan trọng trong lĩnh vực công nghệ thông tin. Theo ước tính, các bộ dữ liệu trong nhiều lĩnh vực như y tế, tài chính, và khoa học sinh học có thể chứa hàng nghìn đến hàng trăm nghìn thuộc tính, trong khi số lượng mẫu phân tích lại rất hạn chế (vài chục đến vài trăm). Điều này gây khó khăn cho các thuật toán phân lớp truyền thống do hiệu suất giảm sút và độ chính xác không đảm bảo. Vấn đề đặt ra là làm thế nào để trích chọn các thuộc tính đặc trưng, loại bỏ các thuộc tính dư thừa và nhiễu nhằm nâng cao hiệu quả phân lớp.

Mục tiêu nghiên cứu của luận văn là xây dựng một phương pháp trích chọn thuộc tính tối ưu, kết hợp thuật toán giải thuật di truyền và thuật toán Random Forest, nhằm giảm kích thước dữ liệu đầu vào mà vẫn giữ được hoặc nâng cao độ chính xác phân lớp. Phạm vi nghiên cứu tập trung trên dữ liệu đa chiều, đặc biệt là các bộ dữ liệu y sinh như ung thư dạ dày và ung thư ruột kết, với thời gian thực hiện nghiên cứu năm 2012 tại Trường Đại học Công nghệ, Đại học Quốc gia Hà Nội.

Nghiên cứu có ý nghĩa quan trọng trong việc cải thiện tốc độ xử lý và độ chính xác của các thuật toán phân lớp trên dữ liệu lớn, góp phần nâng cao hiệu quả khai phá tri thức trong các lĩnh vực ứng dụng như y học, xử lý dữ liệu web, và nhận dạng mẫu. Các chỉ số đánh giá hiệu quả bao gồm độ chính xác phân lớp, thời gian huấn luyện và kiểm thử, cũng như độ ổn định của mô hình qua nhiều lần chạy thử.

Cơ sở lý thuyết và phương pháp nghiên cứu

Khung lý thuyết áp dụng

Luận văn dựa trên các lý thuyết và mô hình chính sau:

• Khai phá dữ liệu (Data Mining): Quá trình phát hiện tri thức có giá trị từ các tập dữ liệu lớn, trong đó trích chọn thuộc tính đóng vai trò quan trọng trong tiền xử lý dữ liệu để giảm chiều và loại bỏ nhiễu.

• Lựa chọn thuộc tính (Feature Selection): Quá trình chọn ra tập con thuộc tính tối ưu từ tập thuộc tính ban đầu nhằm nâng cao hiệu quả phân lớp. Các mô hình lựa chọn thuộc tính gồm Filter, Wrapper và Embedded, trong đó phương pháp Wrapper được sử dụng trong nghiên cứu để kết hợp chặt chẽ với thuật toán học máy.

• Thuật toán Random Forest (RF): Thuật toán phân lớp dựa trên tập hợp các cây quyết định, sử dụng kỹ thuật bagging và bootstrap để giảm phương sai và tăng độ chính xác. RF có khả năng xử lý dữ liệu có số lượng thuộc tính lớn và cung cấp đánh giá mức độ quan trọng của từng thuộc tính.

• Giải thuật di truyền (Genetic Algorithm - GA): Thuật toán tối ưu ngẫu nhiên dựa trên cơ chế chọn lọc tự nhiên, lai ghép và đột biến, được sử dụng để tìm kiếm tập con thuộc tính tối ưu trong không gian tìm kiếm lớn.

Các khái niệm chính bao gồm: độ chính xác phân lớp, kiểm chứng chéo (cross-validation), độ thích nghi (fitness) trong GA, và chỉ số Gini trong RF.

Phương pháp nghiên cứu

Nguồn dữ liệu sử dụng gồm hai bộ dữ liệu thực tế về bệnh ung thư dạ dày (137 mẫu, 119 thuộc tính) và ung thư ruột kết, được thu thập từ các trung tâm nghiên cứu y sinh. Dữ liệu được chia ngẫu nhiên thành tập huấn luyện (70%) và kiểm tra (30%).

Phương pháp nghiên cứu bao gồm:

• Xây dựng mô hình lựa chọn thuộc tính: Sử dụng thuật toán đề xuất kết hợp GA và RF theo mô hình Wrapper. Thuật toán sinh ra các bộ thuộc tính con, đánh giá độ thích nghi bằng RF với kỹ thuật kiểm chứng chéo 5 lần, tính trọng số cho từng thuộc tính dựa trên độ thích nghi của các bộ thuộc tính chứa nó, rồi chọn ra tập thuộc tính tối ưu.

• Phân tích và đánh giá: Thực hiện nhiều lần chạy thử (khoảng 20 lần) với các tham số khác nhau (số cây RF từ 100 đến 1000), đo lường độ chính xác phân lớp, thời gian huấn luyện và kiểm thử, độ lệch chuẩn để đánh giá tính ổn định.

• Timeline nghiên cứu: Nghiên cứu được thực hiện trong năm 2012, với các bước từ tổng quan lý thuyết, xây dựng thuật toán, thực nghiệm trên bộ dữ liệu thực tế, đến phân tích kết quả và đề xuất giải pháp.

Kết quả nghiên cứu và thảo luận

Những phát hiện chính

1. Hiệu quả phân lớp tăng rõ rệt sau khi trích chọn thuộc tính: Trên bộ dữ liệu ung thư dạ dày, độ chính xác phân lớp trung bình của RF tăng từ khoảng 79% (số cây 100) lên đến 82% khi số cây tăng lên 1000. Sau khi áp dụng phương pháp trích chọn thuộc tính đề xuất, độ chính xác phân lớp được cải thiện thêm khoảng 3-5%, đạt mức trên 85%.

2. Giảm số lượng thuộc tính đáng kể: Phương pháp đề xuất đã giảm số lượng thuộc tính từ 119 xuống còn khoảng 10-20% số thuộc tính ban đầu mà vẫn duy trì hoặc nâng cao độ chính xác phân lớp. Điều này giúp giảm thời gian huấn luyện và kiểm thử trung bình từ vài phút xuống còn khoảng 1-2 phút, tiết kiệm tài nguyên tính toán.

3. Tính ổn định của mô hình được cải thiện: Độ lệch chuẩn của độ chính xác phân lớp giảm dần khi số cây RF tăng, chứng tỏ mô hình chạy ổn định. Kết quả kiểm chứng chéo 5 lần cho thấy phương pháp đề xuất có độ tin cậy cao với sai số nhỏ.

4. So sánh với các phương pháp truyền thống: So với việc sử dụng RF trực tiếp trên toàn bộ thuộc tính, phương pháp kết hợp GA và RF cho kết quả phân lớp tốt hơn từ 3-7% tùy bộ dữ liệu, đồng thời giảm đáng kể thời gian xử lý.

Thảo luận kết quả

Nguyên nhân chính của sự cải thiện là do phương pháp đề xuất đã loại bỏ được các thuộc tính dư thừa và nhiễu, giúp thuật toán RF tập trung vào các thuộc tính có ý nghĩa phân lớp cao. Việc sử dụng GA để sinh các bộ thuộc tính con và đánh giá bằng RF theo mô hình Wrapper giúp tìm kiếm hiệu quả trong không gian thuộc tính lớn mà không cần duyệt toàn bộ tập con.

Kết quả phù hợp với các nghiên cứu gần đây trong lĩnh vực khai phá dữ liệu và học máy, cho thấy sự kết hợp giữa thuật toán tối ưu ngẫu nhiên và thuật toán phân lớp ensemble là hướng đi hiệu quả cho bài toán trích chọn thuộc tính trên dữ liệu đa chiều.

Dữ liệu có thể được trình bày qua các biểu đồ so sánh độ chính xác phân lớp và thời gian chạy giữa bộ dữ liệu gốc và bộ dữ liệu sau khi trích chọn thuộc tính, cũng như bảng thống kê chi tiết các chỉ số trung bình, lớn nhất, nhỏ nhất và độ lệch chuẩn.

Đề xuất và khuyến nghị

1. Áp dụng phương pháp trích chọn thuộc tính kết hợp GA và RF trong các hệ thống phân tích dữ liệu đa chiều nhằm nâng cao hiệu quả phân lớp, đặc biệt trong các lĩnh vực y sinh, tài chính và xử lý ngôn ngữ tự nhiên. Thời gian thực hiện đề xuất trong vòng 6-12 tháng, do các tổ chức nghiên cứu và phát triển phần mềm.

2. Tối ưu tham số thuật toán Random Forest như số lượng cây, số thuộc tính chọn tại mỗi nút để cân bằng giữa độ chính xác và thời gian xử lý, áp dụng trong giai đoạn huấn luyện mô hình. Khuyến nghị thực hiện song song với quá trình trích chọn thuộc tính.

3. Phát triển công cụ tự động hóa quy trình trích chọn thuộc tính tích hợp thuật toán đề xuất, hỗ trợ người dùng không chuyên về kỹ thuật có thể dễ dàng áp dụng trên dữ liệu thực tế. Thời gian phát triển dự kiến 12-18 tháng, do các nhóm phát triển phần mềm và chuyên gia dữ liệu thực hiện.

4. Mở rộng nghiên cứu áp dụng trên các bộ dữ liệu đa dạng hơn như dữ liệu hình ảnh, âm thanh, và dữ liệu thời gian thực để đánh giá tính tổng quát và khả năng mở rộng của phương pháp. Thời gian nghiên cứu tiếp theo khoảng 1-2 năm, do các viện nghiên cứu và trường đại học thực hiện.

Đối tượng nên tham khảo luận văn

1. Nhà nghiên cứu và sinh viên ngành Công nghệ Thông tin, Khoa học Dữ liệu: Nắm bắt kiến thức về trích chọn thuộc tính và thuật toán Random Forest, áp dụng trong các đề tài nghiên cứu và luận văn.

2. Chuyên gia phân tích dữ liệu và kỹ sư học máy: Áp dụng phương pháp đề xuất để cải thiện hiệu quả mô hình phân lớp trên dữ liệu thực tế, tiết kiệm tài nguyên tính toán.

3. Các tổ chức y tế và nghiên cứu sinh học: Sử dụng phương pháp để phân tích dữ liệu gene, hình ảnh y học nhằm hỗ trợ chẩn đoán và nghiên cứu bệnh lý.

4. Nhà phát triển phần mềm và công cụ khai phá dữ liệu: Tích hợp thuật toán trích chọn thuộc tính vào các sản phẩm phần mềm nhằm nâng cao khả năng xử lý dữ liệu lớn và đa chiều.

Câu hỏi thường gặp

1. Phương pháp trích chọn thuộc tính này có áp dụng được cho dữ liệu phi cấu trúc không?
   Phương pháp chủ yếu áp dụng cho dữ liệu có cấu trúc dạng bảng với các thuộc tính rõ ràng. Với dữ liệu phi cấu trúc như hình ảnh hay văn bản, cần tiền xử lý để chuyển đổi thành dạng đặc trưng phù hợp trước khi áp dụng.

2. Làm thế nào để xác định số lượng cây tối ưu trong thuật toán Random Forest?
   Số lượng cây được chọn dựa trên thử nghiệm thực nghiệm, thường bắt đầu từ 100 đến 1000 cây. Số cây quá ít có thể làm giảm độ chính xác, quá nhiều làm tăng thời gian tính toán mà không cải thiện đáng kể kết quả.

3. Kiểm chứng chéo (cross-validation) được thực hiện như thế nào trong nghiên cứu?
   Nghiên cứu sử dụng kiểm chứng chéo 5 lần, chia dữ liệu huấn luyện thành 5 phần, mỗi lần dùng 4 phần để huấn luyện và 1 phần để kiểm thử, đảm bảo đánh giá chính xác và ổn định của mô hình.

4. Phương pháp đề xuất có thể áp dụng cho các bài toán phân lớp đa lớp không?
   Có thể áp dụng, tuy nhiên cần điều chỉnh thuật toán và tham số phù hợp với số lượng lớp và tính chất dữ liệu để đảm bảo hiệu quả phân lớp.

5. Thời gian thực thi của phương pháp đề xuất có phù hợp với các ứng dụng thời gian thực không?
   Phương pháp phù hợp với các ứng dụng xử lý dữ liệu lớn không yêu cầu phản hồi tức thì. Với ứng dụng thời gian thực, cần tối ưu thêm hoặc kết hợp với các kỹ thuật giảm chiều dữ liệu nhanh hơn.

Kết luận

• Luận văn đã nghiên cứu và xây dựng thành công phương pháp trích chọn thuộc tính kết hợp giải thuật di truyền và thuật toán Random Forest nhằm nâng cao hiệu quả phân lớp trên dữ liệu đa chiều.

• Phương pháp giúp giảm đáng kể số lượng thuộc tính cần xử lý, đồng thời cải thiện độ chính xác phân lớp và tính ổn định của mô hình.

• Thực nghiệm trên bộ dữ liệu ung thư dạ dày và ung thư ruột kết cho thấy kết quả khả quan với độ chính xác phân lớp tăng từ 79% lên trên 85% và giảm thời gian xử lý trung bình xuống còn khoảng 1-2 phút.

• Các đề xuất về tối ưu tham số, phát triển công cụ tự động và mở rộng ứng dụng được đưa ra nhằm nâng cao tính ứng dụng thực tế của phương pháp.

• Khuyến khích các nhà nghiên cứu và chuyên gia trong lĩnh vực công nghệ thông tin, y sinh và khoa học dữ liệu tiếp tục phát triển và ứng dụng phương pháp trong các bài toán phân lớp phức tạp hơn.

Áp dụng phương pháp vào các bộ dữ liệu thực tế khác, phát triển phần mềm hỗ trợ và công bố kết quả nghiên cứu để đóng góp vào cộng đồng khoa học.

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

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. z 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 z 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) z 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à z 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.