Áp dụng phương pháp trích chọn đặc trưng để nâng cao hiệu quả phân lớp khi khai phá dữ liệu lớn

n luơn là chỗ dựa tinh thần vững chắc cho tơi.” Hà Nội, tháng 05 năm 2009. Sinh viên Trần Phương Nhung ht t p : / / e t r i t h u c . v n Tĩm tắt khĩa luận Trong khĩa luận này tơi áp dụng thuật tốn di truyền (Genetic Algorithm) để bước đầu cải tiến hiệu quả phân lớp của phương pháp minimax probability machine (MPM). Phần đầu tơi xin giới thiệu tổng quan về khái niệm khai phá dữ liệu. Tiếp đĩ, tơi sẽ trình bày về cơ sở lý thuyết của thuật tốn di truyền và phương pháp phân lớp minimax probability machine. Cuối cùng, tơi sẽ mơ tả chi tiết về quá trình xây dựng hệ thống cĩ ứng dụng thuật tốn di truyền trong phân lớp minimax probability machine để chuẩn đốn bệnh ung thư. Mơ hình phân lớp mới này sẽ được chạy thử trên một số cơ sở dữ liệu lớn và đưa ra những số liệu thống kê để cĩ thể thấy được hiệu quả của hệ thống so với phương pháp phân lớp chỉ sử dụng MPM. ht t p : / / e t r i t h u c . v n Mục lục Chương 1: Giới thiệu về khai phá dữ liệu ...................................................................... 10 1.1. Khai phá dữ liệu là gì? ......................................................................................... 10 1.2. Tại sao phải tiến hành khai phá dữ liệu? ............................................................. 10 1.3. Quá trình khai phá dữ liệu ................................................................................... 11 1.4. Kiến trúc điển hình của một hệ khai phá dữ liệu ................................................. 13 1.5. Các bài tốn khai phá dữ liệu điển hình .............................................................. 14 1.6. Các lĩnh vực liên quan đến khai phá dữ liệu........................................................ 16 1.7. Các ứng dụng điển hình của khai phá dữ liệu...................................................... 17 1.8. Các thách thức với khai phá dữ liệu .................................................................... 17 1.9. Kết luận ................................................................................................................ 18 Chương 2: Trích chọn thuộc tính phù hợp .................................................................... 19 2.1. Giới thiệu ............................................................................................................. 19 2.2. Mơ hình trong bài tốn trích chọn ....................................................................... 20 2.2.1. Các mơ hình trong trích chọn ........................................................................... 20 2.2.2. ðánh giá hai mơ hình Filter và Wrapper ......................................................... 22 2.2.2.1. Filter .......................................................................................................... 22 2.2.2.2. Mơ hình Wrapper ...................................................................................... 22 2.3. Một số kỹ thuật xử lý ........................................................................................... 23 2.3.1. Bộ sinh tập con (Feature Subset Generator) .................................................... 23 2.3.2. Bộ đánh giá tập con đặc trưng (Feature Subset Evaluator) ............................. 24 2.3.3. Thuật tốn học điều khiển (Central Machine learning Algorithm) ................. 25 2.4. Kết luận ................................................................................................................ 25 Chương 3: Genetic Algorithms ....................................................................................... 27 3.1. Giới thiệu ............................................................................................................... 27 3.2. ðộng lực ................................................................................................................. 27 3.3. Thuật giải di truyền ................................................................................................ 28 3.3.1. Nội dung thuật tốn ........................................................................................... 28 3.3.2. Thể hiện các giả thuyết ..................................................................................... 30 3.3.3. Các tốn tử di truyền ......................................................................................... 32 3.3.4. Hàm thích nghi và sự chọn lọc .......................................................................... 34 Chương 4: Minimax Probability Machine ..................................................................... 36 ht t p : / / e t r i t h u c . v n 4.1. Giới thiệu ............................................................................................................... 36 4.2. Nội dung................................................................................................................. 36 4.3. Ưu điểm và nhược điểm của minimax probability machine ................................. 37 4.4. Các phiên bản cải tiến của thuật tốn minimax probability machine .................... 38 4.4.1. Minimum error minimax probability machine (MEMPM) .............................. 38 4.4.2. Biased minimax probability machine (BMPM) ................................................ 39 Chương 5: Phương pháp đề nghị .................................................................................... 41 ht t p : / / e t r i t h u c . v n Danh sách các hình ht t p : / / e t r i t h u c . v n Danh sách các bảng ht t p : / / e t r i t h u c . v n Bảng các từ viết tắt Genetic Algorithm GA Minimax Probability Machine MPM ht t p : / / e t r i t h u c . v n Giới thiệu Những năm gần đây, các hệ thống cơ sở dữ liệu đã đem lại những lợi ích vơ cùng to lớn cho con người. Song hành cùng sự phát triển nhanh chĩng của cơng nghệ thơng tin và những ứng dụng của nĩ trong đời sống, kinh tế và xã hội, lượng dữ liệu thu thập ngày càng nhiều theo thời gian, dẫn đến việc xuất hiện ngày càng nhiều các hệ thống cơ sở dữ liệu cĩ kích thước lớn. Trong xã hội hiện đại, thơng tin được coi như sức mạnh và là yếu tố quyết định thành cơng trong mọi lĩnh vực, do đĩ việc tìm ra thơng tin hữu ích trong khối dữ liệu khổng lồ được xem như mục tiêu hàng đầu của mọi tổ chức và cá nhân. Trong khĩa luận này, tơi sẽ ứng dụng kỹ thuật giảm chiều trong bài tốn trích chọn để nhằm cải thiện hiệu quả phân lớp dữ liệu, nền tảng cho hệ thống chuẩn đốn bệnh ung thư. Hệ thống này sẽ được huấn luyện với tập dữ liệu về các bệnh nhân cĩ từ trước và khi cĩ dữ liệu của bệnh nhân mới, hệ thống sẽ tự động đưa ra chuẩn đốn người đĩ cĩ bị bệnh hay khơng? Tơi sử dụng phương pháp phân lớp Minimax Probability Machine (MPM) kết hợp cùng thuật tốn di truyền (Genetic Algorithm) để xây dựng hệ thống chuẩn đốn này. Với mục đích làm tăng độ chính xác của quá trình phân lớp dữ liệu và giảm thời gian huấn luyện của bộ phân lớp, tơi sử dụng thuật tốn di truyền để giảm chiều của tập dữ liệu ban đầu nhằm tối ưu tập thuộc tính đầu vào cho bộ phân lớp MPM. Kết quả thực nghiệm đã chứng minh rằng phương pháp phân lớp sử dụng thuật tốn di truyền để tối ưu tập thuộc tính cho kết quả tốt hơn phương pháp truyền thống. Nội dung chính của khĩa luận bao gồm sáu chương, với nội dung cụ thể như sau: Chương 1: Giới thiệu về khai phá dữ liệu. Chương này tập trung mơ tả về khai phá dữ liệu (data mining), giới thiệu những bài tốn điển hình trong khai phá dữ liệu cũng như những ứng dụng rộng rãi của lĩnh vực này. Cuối cùng là những thách thức đặt ra cho quá trình khai phá dữ liệu. ht t p : / / e t r i t h u c . v n Chương 2: Trích chọn thuộc tính phù hợp. Nội dung chính của chương nhừm giúp người đọc hiểu về khái niệm trích chọn thuộc tính, những mơ hình trích chọn điển hình và một số kỹ thuật xử lý trong quá trình trích chọn. Chương 3: Genetic Algorithm. Ở chương này, người đọc sẽ được giới thiệu về nội dung và những bước thực hiện của thuật tốn di truyền. Chương 4: Minimax Probability Machine. Chương này sẽ mơ tả phương pháp phân lớp minimax probability machine. Phân tích những mặt mạnh và yếu của phương pháp này để đề ra những cải tiến nhằm nâng cao hiệu quả phân lớp của minimax probability machine. Chương 5: Phương pháp đề nghị. Chương này sẽ mơ tả chi tiết quá trình xây dựng mơ hình phân lớp minimax probability machine kết hợp với thuật tốn di truyền. ðồng thời mơ tả quá trình đánh giá chất lượng, từ đĩ đưa ra những phân tích kỹ thuật và kết luận về hiệu quả của mơ hình. Chương 6: Kết luận. Chương này là phần tổng kết khĩa luận, đồng thời nêu ra những mặt cịn hạn chế trong phương pháp đề nghị và những cơng việc trong tương lai nhằm cải tiến hiệu quả của phương pháp này. ht t p : / / e t r i t h u c . v n Chương 1: Giới thiệu về khai phá dữ liệu 1.1. Khai phá dữ liệu là gì? Cĩ khá nhiều định nghĩa về khai phá dữ liệu (Data mining), nhưng định nghĩa đơn giản nhất thì khai phá dữ liệu là việc trích rút thơng tin hay tri thức mới và cĩ ích từ nguồn dữ liệu khổng lồ. Ngồi ra, khai phá dữ liệu cịn cĩ thể hiểu là trích rút các thơng tin cĩ ích từ những dữ liệu khơng tường minh, hoặc trích rút lấy những thơng tin khơng biết trước và tiềm tàng trong dữ liệu. Cũng cĩ thể hiểu, khai phá dữ liệu là việc phân tích khảo sát một cách tỉ mỉ số lượng lớn dữ liệu bằng các phương pháp tự động hoặc bán tự động nhằm tìm ra các mẫu cĩ ích. Cĩ thể nhận xét rằng, khái niệm khai phá dữ liệu là khá rộng lớn, nhưng khơng phải tất cả mọi cơng việc liên quan đến dữ liệu đều được coi là khai phá dữ liệu, chẳng hạn như những việc xử lý truy vấn đơn giản như tra cứu một số điện thoại, hay thống kê ra những học sinh giỏi của một lớp, thì khơng thể coi đĩ là khai phá dữ liệu. Nhưng những cơng việc như gom nhĩm các tài liệu trả về từ máy tìm kiếm theo từng ngữ cảnh thì lại được xem là khai phá dữ liệu. 1.2. Tại sao phải tiến hành khai phá dữ liệu? Trong những năm gần đây, khai phá dữ liệu trở thành một lĩnh vực nghiên cứu rộng rãi trong ngành cơng nghiệp thơng tin, nguyên nhân chủ yếu là do khối lượng khổng lồ của dữ liệu mà con người tạo ra, đi kèm với nĩ là sự cần thiết biến đổi những dữ liệu đĩ thành tri thức. Thơng tin và tri thức cĩ thể được áp dụng vào nhiều lĩnh vực từ phân tích thị trường tài chính, phát hiện giả mạo, cho đến điều khiển sản xuất và nghiên cứu khoa học. ht t p : / / e t r i t h u c . v n Nhìn vào hai lĩnh vực sinh ra nhiều dữ liệu nhất đĩ là thương mại và khoa học. Trong lĩnh vực thương mại, hàng ngày hàng giờ con người đang tạo ra, thu thập và lưu trữ lại rất nhiều dữ liệu, như dữ liệu web, dữ liệu về thương mại điện tử, dữ liệu về việc thanh tốn tại các cửa hàng và các dữ liệu thanh tốn trong các tài khoản… Tính cạnh tranh trong kinh doanh là rất cao, cho nên việc phân tích dữ liệu để cung cấp dịch vụ tốt hơn, cĩ nhiều tiện ích cho khách hàng, và đĩn bắt chính xác nhu cầu của khách hàng rất quan trọng. Trong lĩnh vực khoa học, dường như lượng dữ liệu sinh ra và thu thập lại cịn lớn hơn nhiều, lên tới hàng GB/giờ, chẳng hạn như dữ liệu từ vệ tinh, từ các ảnh chụp vũ trụ và từ các mơ phỏng thử nghiệm khoa học. Khai phá dữ liệu giúp các nhà khoa học trong việc phân lớp dữ liệu và hỗ trợ trong việc đưa ra các quyết định. Cùng với sự phát triển của khoa học, của ngành cơ sở dữ liệu khơng thể khơng kể đến là sự phát triển của ngành cơng nghiệp máy tính, người ta đã tạo ra những phương tiện lưu trữ lớn hơn, những máy tính rẻ hơn, tốc độ cao hơn, trợ giúp cho quá trình thu thập dữ liệu cũng như khai phá chúng. Trong quá trình tác nghiệp, người ta thường phải đưa ra các quyết định, tuy nhiên, với lượng dữ liệu khổng lồ như thế, người ta khơng thể sử dụng hết, hoặc nếu muốn sử dụng thì phải mất thời gian quá nhiều, như vậy cĩ nguy cơ đánh mất cơ hội. Do đĩ, việc sử dụng máy tính để khai phá dữ liệu nhằm giúp đỡ con người trong cơng việc càng được thúc đẩy mạnh mẽ, làm sao với các dữ liệu đã thu thập được cĩ thể đưa ra một hành động mang lại lợi ích tối đa. 1.3. Quá trình khai phá dữ liệu Ở một gĩc độ nào đĩ, khái niệm khai phá dữ liệu và khai phá tri thức nhiều khi được coi là một. Tuy nhiên, nếu xét kỹ thì khai phá dữ liệu là một bước quan trọng trong khai phá tri thức. Một quá trình phát hiện tri thức trong cơ sở dữ liệu bao gồm các giai đoạn chính sau: (1) Làm sạch dữ liệu (Data Cleaning): Khử nhiều và các dữ liệu mâu thuẫn. ht t p : / / e t r i t h u c . v n (2) Tích hợp dữ liệu (Data Integration): Kết hợp nhiều nguồn dữ liệu khác nhau. (3) Lựa chọn dữ liệu (Data Selection): Chắt lọc lấy những dữ liệu liên quan đến nhiệm vụ phân tích sau này. (4) Biến đổi dữ liệu (Data Transformation): Biến đổi dữ liệu thu được về dạng thích hợp cho quá trình khai phá. (5) Khai phá dữ liệu (Data Mining): Sử dụng những phương pháp thơng minh để khai thác dữ liệu nhằm thu được các mẫu mong muốn. (6) ðánh giá kết quả (Pattern Evaluation): Sử dụng các độ đo để đánh giá kết quả thu được. (7) Biểu diễn tri thức (Knowledge Presentation): Sử dụng các cơng cụ biểu diễn trực quan để biểu diễn những tri thức khai phá được cho người dùng. Tri thức ðánh giá & Trình diễn Lựa chọn & Chuyển dạng Dữ liệu Kho dữ liệu Khai phá dữ liệu Dữ liệu chuyển dạng Mẫu Làm sạch & Tích hợp ht t p : / / e t r i t h u c . v n Hình 1.1. Quá trình phát hiện tri thức trong cơ sở dữ liệu. Quá trình này cĩ thể được lặp lại nhiều lần một hay nhiều giai đoạn dựa trên phản hồi từ kết quả của các giai đoạn sau. 1.4. Kiến trúc điển hình của một hệ khai phá dữ liệu Trong kiến trúc điển hình của một hệ khai phá dữ liệu (hình 1.2), các nguồn dữ liệu cho hệ thống khai phá dữ liệu bao gồm cơ sở dữ liệu, hoặc kho dữ liệu, hoặc World Wide Web, hoặc kho chứa dữ liệu kiểu bất kỳ khác, hoặc tổ hợp các kiểu dữ liệu nĩi trên. Cơ sở tri thức bao chứa các tri thức hiện cĩ về miền ứng dụng, được sử dụng trong thành phần khai phá dữ liệu để tăng tính hiệu quả của thành phần này. Một số tham số của thuật tốn khai phá dữ liệu tương ứng sẽ tinh chỉnh theo tri thức miền sẵn cĩ từ cơ sở tri thức trong hệ thống. Cơ sở tri thức cịn được sử dụng trong việc đánh giá các mẫu đã khai phá được xem chúng cĩ thật sự hấp dẫn hay khơng, trong đĩ cĩ đối chứng với các tri thức đã cĩ trong cơ sở tri thức. Nếu mẫu khai phá được thực sự là hấp dẫn thì được bổ sung vào cơ sở tri thức để phục vụ cho hoạt động tiếp theo của hệ thống. ht t p : / / e t r i t h u c . v n Hình 1.2. Kiến trúc điển hình của hệ thống khai phá dữ liệu. 1.5. Các bài tốn khai phá dữ liệu điển hình Hai mục tiêu chủ yếu của khai phá dữ liệu là dự báo (prediction) và mơ tả (description). Dự báo dùng một số biến hoặc trường trong trong cơ sở dữ liệu để dự đốn về giá trị chưa biết hoặc về giá trị sẽ cĩ trong tương lai của các biến. Mơ tả hướng tới việc tìm ra các mẫu mơ tả dữ liệu. Dự báo và mơ tả được thể hiện thơng qua các bài tốn cụ thể sau: • Mơ tả khái niệm (Summarization) Mục đích của bài tốn là tìm ra các đặc trưng và tính chất của các khái niệm. ðiển hình cho bài tốn này là các bài tốn như tổng quát hĩa, tĩm tắt, các đặc trưng dữ liệu ràng buộc. Giao diện người dùng ðánh giá mẫu khai phá được Thành phần khai phá dữ liệu Phục vụ Cơ sở dữ liệu/ Kho dữ Cơ sở dữ liệu Kho dữ liệu World Wide Kiểu kho chứa thơng tin Cơ sở tri thức Làm sạch, tích hợp và chọn lựa dữ ht t p : / / e t r i t h u c . v n • Quan hệ kết hợp (Dependency relationship) Một trong những vấn đề của phát hiện mối quan hệ là làm rõ ràng và nguyên nhân. Bài tốn tìm luật kết hợp là một đại diện điển hình, thực hiện việc phát hiện ra mối quan hệ giữa các thuộc tính (các biến), cĩ dạng ở phụ thuộc hàm trong cơ sở dữ liệu quan hệ. • Phân lớp (Classification) Phân lớp cịn được gọi là học máy cĩ giám sát (supervised learning). Với một tập các dữ liệu huấn luyện cho trước và sự huấn luyện của con người, các giải thuật phân loại sẽ học ra bộ phân loại (classifier) dùng để phân dữ liệu mới vào trong những lớp (cịn gọi là loại) đã được định trước. Một số phương pháp điển hình là cây quyết định, luật phân lớp, mạng neuron. • Phân cụm (Clustering) Phân cụm cịn được gọi là học máy khơng giám sát (unsupervised learning), thực hiện việc nhĩm dữ liệu thành các lớp mới để cĩ thể phát hiện các mẫu phân bố. Phân cụm chỉ là bái tốn mơ tả hướng tới việc nhận biết một tập hữu hạn các loại hoặc các cụm để mơ tả dữ liệu. Các loại (cụm) cĩ thể rời nhau và tồn phần (tạo nên phân hoạch) hoặc chồng chéo lên nhau. • Phân đoạn (Segmentation) Về bản chất phân đoạn là tổ hợp của phân cụm và phân lớp, trong đĩ phân cụm được tiến hành trước và sau đĩ là phân lớp. • Hồi quy (Regression) Hồi quy là học một hàm ánh xạ dữ liệu nhằm tìm và xác định giá trị thực của một biến. • Mơ hình phụ thuộc (Dependency modeling) ht t p : / / e t r i t h u c . v n Bài tốn xây dựng mơ hình phụ thuộc hướng tới việc tìm ra một mơ hình mơ tả sự phụ thuộc cĩ ý nghĩa giữa các biến. Mơ hình phụ thuộc gồm hai mức: mức cấu trúc của mơ hình mơ tả (thường dưới dạng đồ thị) và mức định lượng. • Phát hiện biến đổi và độ lệch (Change and Deviation Detection) Tập trung vào việc phát hiện hầu hết sự thay đổi cĩ ý nghĩa dưới dạng độ đo đã biết trước hoặc giá trị chuẩn. 1.6. Các lĩnh vực liên quan đến khai phá dữ liệu Khai phá dữ liệu liên quan đến nhiều ngành, nhiều lĩnh vực như thống kê, trí tuệ nhân tạo, cơ sở dữ liệu, thuật tốn học, tính tốn song song và tốc độ cao, thu thập tri thức cho các hệ chuyên gia, quan sát dữ liệu... ðặc biệt khai phá dữ liệu rất gần gũi với lĩnh vực thống kê, sử dụng các phương pháp thống kê để mơ hình dữ liệu và phát hiện các mẫu, luật. Ngân hàng dữ liệu (Data Warehousing) và các cơng cụ phân tích trực tuyến (OLAP – On line Analytical Processing) cũng liên quan chặt chẽ với khai phá dữ liệu. Hình 1.3. Tính đa/ liên ngành của khai phá dữ liệu. Khai phá dữ liệu Hệ thống cơ sở dữ liệu Thống kê Học máy Thuật tốn Các bộ mơn khác Trực quan hĩa ht t p : / / e t r i t h u c . v n Các kỹ thuật truyền thống khơng cịn thích hợp với các loại dữ liệu bị lỗi, bị nhiễu hay dữ liệu nhiều chiều và các hệ dữ liệu tự nhiên phân tán hay hỗn tạp. Do đĩ khi kết hợp với nhau, hình thành lĩnh vực mới, đĩ là khai phá dữ liệu. 1.7. Các ứng dụng điển hình của khai phá dữ liệu Ứng dụng của khai phá dữ liệu được chia thành hai lớp chính bao gồm các ứng dụng phân tích – hỗ trợ ra quyết định và lớp các lĩnh vực ứng dụng khác. • Lớp các ứng dụng trong phân tích dữ liệu và hỗ trợ ra quyết định bao gồm các ứng dụng trong: - Thơng tin thương mại: Phân tích dữ liệu Marketing, khách hàng; Phân tích đầu tư; Phê duyệt cho vay vốn hay phát hiện gian lận. - Thơng tin kỹ thuật: ðiều khiển và lập trình lịch; Quản trị mạng. - Bảo hiểm y tế. - Viễn thơng. - Thể thao • Lớp các lĩnh vực ứng dụng điển hình khác được kể đến là khai phá văn bản, khai phá Web, khai phá dữ liệu sinh học và khai phá dữ liệu dịng. 1.8. Các thách thức với khai phá dữ liệu • Cơ sở dữ liệu lớn. • Số chiều lớn. • Thay đổi dữ liệu và tri thức cĩ thể làm cho các mẫu đã phát hiện khơng cịn phù hợp. • Dữ liệu bị thiếu hoặc bị nhiễu. ht t p : / / e t r i t h u c . v n • Quan hệ giữa các trường phức tạp. • Giao tiếp với người sử dụng và kết hợp với các tri thức đã cĩ. • Tích hợp với các hệ thống khác … 1.9. Kết luận Qua các vấn đề đã trình bày, chúng ta nhận thấy với một lượng dữ liệu thực tế nhỏ và với mục đích bài tốn cụ thể nhưng ta cĩ thể tiếp cận theo nhiều hướng khác nhau của cùng một phương pháp khai phá dữ liệu và đạt được kết quả khác nhau, điều đĩ càng làm sáng tỏ khả năng ứng dụng thực tế to lớn đồng thời với những thách thức đối với kỹ thuật khai phá dữ liệu trong các bài tốn kinh tế - xã hội và trong nhiều lĩnh vực khác. ht t p : / / e t r i t h u c . v n Chương 2: Trích chọn thuộc tính phù hợp 2.1. Giới thiệu Trích chọn đặc trưng (Feature Selection) là phương pháp chọn ra một tập con tốt nhất từ tập các đặc trưng đầu vào bằng cách lọai bỏ những đặc trưng cĩ rất ít hoặc khơng cĩ thơng tin dự đốn. Trích chọn đặc trưng cĩ vai trị quan trọng trong việc chuẩn bị và lựa chọn dữ liệu cho quá trình khai phá dữ liệu. Nĩ sẽ làm giảm kích cỡ của khơng gian đặc trưng, loại bỏ dư thừa hay nhiễu của dữ liệu. Phương pháp này cĩ thể tìm chính xác những tập con đặc trưng cĩ khả năng dự đốn, do đĩ giúp cải thiện đáng kể kết quả thu được trong các mơ hình phân lớp. Về cơ bản, quá trình trích chọn đặc trưng bao gồm bốn bước cơ bản: sinh tập con (subset generation), đánh giá tập con (subset evaluation), điều kiện dừng quá trình trích chọn (stopping criterion) và kết quả (result validation). Hình 2.1. Bốn bước cơ bản trong quá trình trích chọn các thuộc tính phù hợp. Subset generation là một thủ tục tìm kiếm. Về cơ bản, nĩ sinh ra một tập con của tập các đặc trưng để đánh giá. Giả sử cĩ N đặc trưng trong tập dữ liệu gốc, thì số lượng các Subset Generation Subset Evaluation Result Validation Stopping Criterion YES NO Goodness of Subset Subset Original Set ht t p : / / e t r i t h u c . v n tập con tiềm năng là 2n. Vì một tập con tối ưu các điểm đặc trưng khơng phải là duy nhất nên số lượng các tập con cĩ thể thỏa mãn là rất lớn, do đĩ quá trình tìm kiếm trong trích chọn đặc trưng sẽ tốn nhiều thời gian và cơng sức. Mỗi tập con được sinh ra cần phải được đánh giá và so sánh với những tập con tốt nhất đã được tìm thấy trước. Nếu tập con tìm thấy sau là tốt hơn thì nĩ sẽ được thay thế cho tập con tốt nhất trước đây. Nếu khơng cĩ một điều kiện dừng hợp lý thì quá trình tìm kiếm các tập con tốt nhất sẽ được xem như là vơ hạn. Một quá trình trích chọn đặc trưng cĩ thể dừng khi thỏa mãn một trong những điều kiện đánh giá sau: (a) chọn đủ số lượng đã được xác định trước của tập đặc trưng, (b) thỏa mãn số lần đã được xác định trước của quá trình lặp lại. (c) ở một khía cạnh (điều kiện) nào đĩ tập con mới được đánh giá là khơng tốt hơn tập con trước, (d) tập con được bộ đánh giá cho là tốt nhất. 2.2. Mơ hình trong bài tốn trích chọn 2.2.1. Các mơ hình trong trích chọn Trích chọn đặc trưng thật sự là lý tưởng trong lựa chọn tập con đặc trưng tối ưu từ một tập ứng cử để mơ tả khái niệm mục tiêu trong hệ thống học. ðộ tốt của một tập con đặc trưng cĩ thể được đánh giá qua nhiều cách khác nhau, nhờ đĩ mà cĩ nhiều mơ hình khác nhau được đưa ra trong phương pháp trích chọn. ðiển hình là hai mơ hình: Filter và Wrapper. Hình 2.2. Mơ hình Filter 1 2 Filter 3 A ht t p : / / e t r i t h u c . v n Hình 2.3. Mơ hình Wrapper Giải thích hình vẽ: A: Tập đặc trưng đầu vào. 1: Bộ sinh tập con (Feature Subset Generator). 2: Bộ đánh giá (Feature Subset Evaluator). 3: Các thuật tốn học máy (Followed Machine learning Algorithm) 4: Thuật tốn học máy điều khiển (Central Machine learning Algorithm). Mơ hình Filter đánh giá mỗi cá thể bằng một vài tiêu chuẩn, rồi chọn ra tập con các thuộc tính cĩ độ đánh giá cao nhất. Nhìn chung, Filter coi tiến trình của trích chọn thuộc tính như tiến trình thực thi trước, sau đĩ mới sử dụng thuật tốn để phân lớp. Wrapper sử dụng một thuật tốn tìm kiếm để đánh giá tập con các thuộc tính coi như là một nhĩm hơn là một cá thể riêng lẻ. Mơ hình Wrapper được đặt vào trung tâm của một thuật tốn máy học cụ thể. Nĩ đánh giá độ tốt của những tập con đặc trưng tùy theo độ chính xác học của tập con, điều này xác định thơng qua tỷ lệ. Những thuật tốn tìm kiếm cũng sử dụng hàm đánh giá kinh nghiệm (heuristics) để hướng dẫn việc tìm kiếm tập trung vào các đối tượng cĩ triển vọng. 1 2 4 Wrapper Model 3 A ht t p : / / e t r i t h u c . v n 2.2.2. ðánh giá hai mơ hình Filter và Wrapper 2.2.2.1. Filter • Ưu điểm: - Khơng cĩ xử lý học máy trong quá trình lựa chọn các đặc trưng. - Dễ dàng nhận diện và thời gian tiêu thụ ít hơn mơ hình Wrapper. • Nhược điểm: - Hiệu suất sản sinh các tập con đặc trưng là khơng đảm bảo vì nĩ thường đánh giá một tập con đặc trưng chỉ dựa trên đặc trưng nhỏ thiên về nguyên lý mà khơng tính tới độ chính xác của kết quả học máy. - Kết quả thu được bị giảm sút về độ chính xác học ở những giai đoạn sau vì các hàm đánh giá hiện thời được sử dụng thường thiên về giá trị ở một vài phạm vi, do đĩ sẽ khơng đánh giá một cách khách quan tầm quan trọng của các đặc trưng. 2.2.2.2. Mơ hình Wrapper • Ưu điểm: - ðảm bảo hiệu suất của kết quả học hơn mơ hình Filter. • Nhược điểm: - Ít được sử dụng hơn mơt hình Filter trên thực tế vì:
Tiến trình học tốn kém về thời gian đến mức thời gian thực hiện đưa ra bởi một thuật tốn sử dụng mơ hình Wrapper là khơng chấp nhận được.
Với một hệ thống kích thước cực lớn, mơ hình này khơng thực tế do phạm vi của nĩ buộc phải thu nhỏ lại trước khi thuật tốn học máy được áp dụng. ht t p : / / e t r i t h u c . v n
Kết quả đánh giá của mơ hình phụ thuộc nhiều vào thuật tốn học máy điều khiển. 2.3. Một số kỹ thuật xử lý 2.3.1. Bộ sinh tập con (Feature Subset Generator) Tùy từng chiến lược cụ thể, bộ sinh tập con sẽ tạo ra những tập con đặc trưng từ một tập đầu vào tương ứng. ðầu ra của bộ sinh sẽ xác định thuật tốn trích chọn đặc trưng của việc tìm đường và tìm kiếm phạm vi trong một khơng gian đặc trưng tương ứng. Nĩi chung, bộ sinh cĩ hai chiến lược để sản sinh ra những tập con đặc trưng: • ðầy đủ (Completely): Một bộ khởi tạo đầy đủ cĩ thể sản sinh ra tất cả các tập con từ một tập đặc trưng đầu vào, do vậy phạm vi tìm kiếm của chiến lược này là NP đầy đủ, tuy nhiên điều này khơng phải lúc nào cũng chứng tỏ tìm kiếm vét cạn là cần thiết trong thực tế, bởi vì một số cơng nghệ như: đường biên và rẽ nhánh cĩ thể được áp dụng để lược bớt phạm vi tìm kiếm tốt nhất. Bởi vậy nếu là thuật tốn trích chọn với bộ khởi tạo đầy đủ, thực nghiệm chỉ ra rằng khơng gian tìm kiếm lớn nhất là O(2k). Mà đối với hầu hết những hệ thống học máy thực, điều này là khơng cần thiết phải đánh giá tất cả những tập con từ một tập đặc trưng tương ứng. Thường thì, thuật tốn trích chọn với bộ khởi tạo đầy đủ cĩ thể tìm ra một tập con đặc trưng tối ưu của hệ thống học máy nhưng địi hỏi thời gian thực thi phức tạp. Liu H. [12] đã đưa ra bộ khởi tạo đầy đủ đặc biệt mà sản sinh một cách ngẫu nhiên ra những tập con đặc trưng dựa vào thuật tốn Las Vegas (LV). Thuật tốn LV cĩ thể tìm kiếm trên tồn bộ khơng gian đáp án rồi sau đĩ đưa ra kết quả tối ưu đảm bảo. Tuy nhiên khác với những bộ khởi tạo đầy đủ khác, đối với một ứng dụng thực tế, khả năng thực thi của bộ khởi tạo Liu là hồn tồn thay đổi, nĩ phụ thuộc nhiều vào quá trình phân chia dữ liệu ngẫu nhiên trong tồn bộ hệ thống học máy. • Kinh nghiệm (Heuristically): ðể lược bớt khơng gian tìm kiếm, bộ khởi tạo kinh nghiệm sản sinh ra các tập con đặc trưng dựa vào những kinh nghiệm chiến lược nào đĩ. Cĩ ba kỹ thuật tìm kiếm tập con điển hình là: ht t p : / / e t r i t h u c . v n - Lựa chọn tiến (Forward Selection): các tập con đặc trưng được khởi tạo trước hết là rỗng (null), sau đĩ liên tục gán những tính năng tốt nhất hiện thời cho tập con đĩ cho đến khi khơng cịn tính năng nào nữa hay các điều kiện thực thi đưa ra đã được tiếp nhận hết. - Lược bỏ lùi (Backward Elimination): Các tập con đặc trưng được khởi tạo trước hết là đầy đủ các đặc trưng, sau đĩ loại bỏ lần lượt những đặc trưng kém nhất hiện thời từ các tập con đĩ, cho đến khi khơng cịn đặc trưng nào hoặc các điều kiện thực thi đưa ra đã được triệt tiêu hết. - Lựa chọn hai hướng (Bi – direction Selection): các tập con đặc trưng được khởi tạo trước hết là rỗng, đầy, hoặc sản sinh ngẫu nhiên một tập con đặc trưng, sau đĩ liên tục hoặc là gán tính năng tốt nhất hiện thời cho tập con đĩ hoặc là triệt tiêu tính năng kém nhất từ các tập con đĩ. ðể từ đĩ đưa ra những giá trị định hướng tốt nhất ở mỗi lần lặp lại đĩ. Quá trình tiếp tục cho tới khi tất cả điều kiện được đưa ra từ trước đã được tiếp nhận hết. Bộ phận khởi tạo kinh nghiệm giảm thiểu phạm vi tìm kiếm đa thức số mũ, do đĩ giảm thời gian thực hiện thuật tốn phức tạp trong phương pháp trích chọn. Tuy nhiên, thuật tốn chỉ đưa ra một lượng nhỏ kết quả tối ưu, khi thực hiện tìm đường và tìm kiếm phạm vi của bộ phận khởi tạo, kết quả này được đảm bảo thơng qua những thuật tốn này. 2.3.2. Bộ đánh giá tập con đặc trưng (Feature Subset Evaluator) Hiệu suất của một tập con đặc trưng được đánh giá dựa trên cơ sở nào đĩ mà bộ đánh giá đạt được. Bộ đánh giá của những mơ hình thuật tốn khác nhau là khác nhau. Bộ đánh giá của mơ hình Filter thường là các hàm đánh giá, trong khi của mơ hình Wrapper là độ học chính xác đạt được bởi quá trình thực thi thuật tốn học máy điều khiển trên hệ thống học. • Hàm đánh giá ht t p : / / e t r i t h u c . v n Những hàm đánh giá điển hình dùng để đo đạc và phân biệt khả năng phân lớp của những đặc điểm khác nhau trên các mẫu. Thực tế, các hàm đánh giá khác nhau thường được dùng hiện nay như: xấp xỉ chất lượng (Approximation Quality), độ quan trọng của thuộc tính (Feature Importance), trọng số của thuộc tính (Feature Weight) … • Học chính xác Trong mơ hình Wrapper, để ước lượng độ học máy chính xác, trước hết, các mẫu của hệ thống học phải được chia ngẫu nhiên làm hai hệ thống con, chẳng hạn như: hệ thống huấn luyện và hệ thống kiểm tra, trong đĩ, cấu trúc của hai hệ thống con cĩ cùng đặc điểm và được tạo ra bởi bộ sinh; sau đĩ thuật tốn học m._.