Lựa chọn thuộc tính trong khai phá dữ liệu

tropy) tiên nghiệm và giá trị kỳ vọng của độ bất định hậu nghiệm của thuộc tính quyết định D khi đã biết X. Thuộc tính X được coi là tốt hơn thuộc tính Y nếu lượng thông tin thu thêm được từ X lớn hơn lượng thông tin thu thêm được từ Y. Số đo độ phụ thuộc (dependency - hay còn gọi là số đo độ tương quan). Số đo này đánh giá khả năng dự đoán của một thuộc tính đối với giá trị của một thuộc tính khác. Trong hai thuộc tính điều kiện X và Y, thuộc tính nào tương quan mạnh hơn với thuộc tính quyết định D thì nó sẽ được ưu tiên lựa chọn. Số đo độ tương quan giữa hai thuộc tính cũng Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 23 được mở rộng để đánh giá sự phụ thuộc giữa một thuộc tính vào một số thuộc tính khác. Số đo độ nhất quán (consistency). Đây là một tiêu chuẩn mới, gần đây thường được sử dụng vào việc đánh giá lựa chọn thuộc tính. Khác với các số đo khác, tiêu chuẩn này gắn kết chặt chẽ với tập dữ liệu huấn luyện. Số đo độ nhất quán là tỷ lệ các bộ dữ liệu (đối tượng) nhất quán trong tập dữ liệu. Tập thuộc tính được chọn là tập nhỏ nhất bảo đảm được tỷ lệ dữ liệu nhất quán theo ngưỡng quy định bởi người sử dụng. b) Tiêu chuẩn phụ thuộc Trong học luật phân lớp (học có giám sát), mục đích đầu tiên của là cực tiểu hóa sai số dự báo. Do đó, sai số dự báo (hay độ chính xác của dự báo) thường được chọn làm tiêu chuẩn (phụ thuộc) để đánh giá các tập con thuộc tính. Như đã nói ở trên, tiêu chuẩn phụ thuộc luôn được sử dụng trong cách tiếp cận wrapper. Việc lựa chọn các thuộc tính được tiến hành thông qua việc áp dụng một thuật phân lớp, nên tập con thuộc tính chọn được sẽ có khả năng dự báo rất cao. Tuy vậy, việc sử dụng tiêu chuẩn phụ thuộc để lựa chọn thuộc tính sẽ tiêu tốn nhiều thời gian tính toán. 2.2.3. Ứng dụng của các kỹ thuật lựa chọn thuộc tính Nhiều hệ thống thông tin trong nhiều lĩnh vực đã nhận thấy rõ lợi ích của việc lựa chọn thuộc tính nhằm giảm bớt số chiều của dữ liệu trong các cơ sở dữ liệu có kích thước lớn. Hình 1.3 dưới đây trình bày một số lĩnh vực áp dụng quan trọng của các kỹ thuật lựa chọn thuộc tính. Những giải thuật lựa chọn đặc trưng thường được ứng dụng để tối ưu hóa hiệu quả phân lớp của các hệ thống nhận dạng tự động, nhất là khi số cá thể mẫu trong tập huấn luyện có hạn. Thông thường, độ chính xác của một thuật phân lớp Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 24 học được sẽ bị giảm khi sử dụng quá nhiều thuộc tính. Ví dụ như trong chuẩn đoán khối u ác tính, do có quá nhiều thuộc tính, độ chính xác của việc nhận biết khối u ác tính của các bác sĩ chuyên khoa qua chỉ vào khoảng 65% đến 85%. Với việc ứng dụng các giải thuật lựa chọn thuộc tính, hiện nay các những hệ thống nhận dạng tự động khối u có thể đạt kết quả phân loại khối u chính xác đến 95%. Lựa chọn thuộc tính Nhận dạng ảnh Phân loại văn bản Kiểm tra hệ thống Phân cụm Tin-sinh-học Qui nạp luật If ... ... then X If ... ... then Y If ... ... then Z Hình 2.4: Các lĩnh vực ứng dụng của lựa chọn thuộc tính Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 25 Trong những năm gần đây, dữ liệu có tính cấu trúc thu được từ các phân tích về gen người gia tăng nhiều lần. Điều này tạo ra nhiều cơ hội đồng thời cũng là những thách thức đối với những nhà khoa học trí tuệ nhân tạo. Do công nghệ phân tích gen ngày càng phát triển, trong một thí nghiệm, người ta có thể phân tích tới hàng ngàn, thậm chí cả chục ngàn cấu trúc. Vấn đề đặt ra là làm sao có thể phân biệt giữa người bị ung thư và người khỏe mạnh dựa trên hiện trạng cấu trúc gen có kích rất lớn. Để giải quyết vấn đề này, người ta đã áp dụng các kỹ thuật lựa chọn thuộc tính, rút gọn đáng kể kích thước các cấu trúc gen trong tập dữ liệu huấn luyện. Cũng có thể nêu một áp dụng khác nữa của lựa chọn thuộc tính trong tin- sinh-học, đó là để hình thành các giả thuyết về mối quan hệ giữa các đặc trưng hóa học của các phân tử và sự hoạt động của nó, từ đó đưa ra dự đoán về vị trí, phát hiện các chỗ nối giữa hai miền mã hóa và không mã hóa của AND. Cách tiếp cận chung đối với vấn đề biểu diễn tri thức sao cho mang tính mô tả và dễ hiểu đối với con người là sử dụng các luật dạng if-then. Thế nhưng, trong nhiều lĩnh vực thực tiễn, con người thường rất thiếu những luật có tính hệ thống và về cùng một loại được cung cấp bởi chuyên gia. Cần phải học luật từ các ví dụ. Để có thể làm tăng quá trình quy nạp luật, rút gọn tính phức tạp của các luật thu được, đòi hỏi phải rút gọn thuộc tính. Rút gọn thuộc tính cho phép giảm số chiều của một tập dữ liệu kích thước lớn mà chỉ làm mất đi một lượng thông tin tối thiểu cần thiết cho viêc học luật. Nhờ đó, rút gọn thuộc tính giúp ta loại bỏ những dữ liệu dư thừa, đơn giản hóa công việc thiết kế và cài đặt các thuật học. Ngoài ra, nhờ số thuộc tính được rút gọn, việc học luật sẽ tiêu tốn ít thời gian hơn, kết quả thu được trong nhiều trường hợp cũng tốt hơn. Hiện nay, nhiều hệ thống đo đạc suy luận đã được xây dựng sử dụng phương pháp luận căn cứ vào dữ liệu. Các mô hình suy đoán giá trị của các Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 26 thuộc tính đích cài đặt bên trong hệ thống được xây dựng sử dụng dữ liệu thu thập được theo thời gian thực. Điều đó làm cho các hệ thống suy luận chịu ảnh hưởng nhiều bởi chất lượng dữ liệu. Khi giải quyết các vấn đề phức tạp, chẳng hạn như kiểm tra độ tin cậy hay chẩn đoán lỗi của các dây chuyền sản xuất công nghiệp, ta thường phải đối mặt với rất nhiều thuộc tính, trong đó có những thuộc tính dư thừa. Việc phải đo đạc cả những thuộc tính như vậy sẽ rất tốn kém. Trong trường hợp này, rõ ràng phải áp dụng các kỹ thuật rút gọn hiệu quả, loại bỏ các thuộc tính dư thừa, lựa chọn các thuộc tính liên quan nhiều nhất cho việc xây dựng một mô hình xử lý có độ tin cậy, chính xác cao. Phân cụm văn bản là việc phân chia các tài liệu tương tự thành các cụm. Mỗi văn bản là một tập hợp lớn các từ. Điều này dẫn đến không gian các thuộc tính mô tả có số chiều rất cao, cũng như sự phân tán của dữ liệu, ảnh hưởng lớn đến độ hiệu quả của các thuật phân cụm. Để có được các thuật phân cụm khả thi trong phân loại văn bản, các kỹ thuật trích lọc, cũng như lựa chọn thuộc tính đã được nhiều hãng phần mềm áp dụng. Giống như phân cụm, phân loại văn bản coi các tài liệu như là những tập hợp các từ ngữ. Để phân loại văn bản, người ta tiến hành kiểm tra, trích lọc các từ khóa và đánh giá chúng theo một tiêu chí nào đó, chẳng hạn tần số xuất hiện. Vì số từ khóa trích lọc được thường có tới hàng chục ngàn, các kỹ thuật rút gọn số chiều cần phải được áp dụng. Gần đây, các thuật rút gọn thuộc tính đã được ứng dụng thành công trong phân loại trang web và phân loại dấu sách (bookmark). 2.3. Kết luận chƣơng 2 Mục đích của rút gọn thuộc tính là làm giảm số chiều của không gian thuộc tính, loại bỏ dữ liệu dư thừa, không liên quan. Rút gọn thuộc tính đóng vai trò quan trọng trong bước tiền xử lý dữ liệu cũng như trong quá trình khai phá. Kết Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 27 quả rút gọn thuộc tính ảnh hưởng trực tiếp đến hiệu quả thực hiện các nhiệm vụ khai phá: Gia tăng tốc độ, cải thiện chất lượng, tính dễ hiểu của các kết quả thu được. Trong chương 2 này, chúng tôi đã trình bày khái quát về nội dung, các phương pháp và quy trình giải quyết vấn đề lựa chọn thuộc tính. Một số ứng dụng quan trọng của lựa chọn thuộc tính cũng đã được bàn tới ở cuối chương. Chương 3 tiếp theo dành cho việc nghiên cứu một số thuật toán rút gọn thuộc tính điển hình. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 28 CHƢƠNG 3 MỘT SỐ THUẬT TOÁN LỰA CHỌN THUỘC TÍNH ĐIỂN HÌNH Như đã biết mục đích chính của lựa chọn thuộc tính là làm sao giảm kích thước dữ liệu, chính vì điều này nên khi nghiên cứu các kỹ thuật lựa chọn thuộc tính có nghĩa là đi nghiên cứu một số phương pháp để làm thế nào có thể rút gọn dữ liệu một cách tối ưu nhất mà không làm thay đổi ngữ nghĩa của dữ liệu. Chương 3 này dành cho việc nghiên cứu một số thuật toán lựa chọn thuộc tính điển hình. Các thuật toán được trình bày theo ba nhóm chính: các thuật toán kiểu filter, các thuật toán kiểu wrapper và một số thuật toán khác. Các thuật toán này thường được sử dụng để lựa chọn thuộc tính giải quyết các vấn đề phân cụm và phân lớp trong khai phá dữ liệu. 3.1. Các thuật toán theo cách tiếp cận filter Để minh họa hoạt động của các thuật toán kiểu filter nêu trong phần này, một tập dữ liệu ví dụ cho trong bảng 3.1 dưới đây sẽ được sử dụng. Tập dữ liệu được chọn làm ví dụ này chỉ chứa các giá trị nhị phân, đó là nhằm đáp ứng những yêu cầu khác nhau của các thuật toán sẽ được trình bày. Trong luận văn này, từ đây về sau C ký hiệu tập các thuộc tính điều kiện, D ký hiệu tập các thuộc tính quyết định (thuộc tính nhãn lớp). 3.1.1 Thuật toán RELIEF Đây là thuật toán lựa chọn thuộc tính đầu tiên được xây dựng theo cách tiếp cận lọc (filter). Trong quá trình thực hiện, RELEF sẽ tính toán cho mỗi Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 29 Bảng 3.1: Tập dữ liệu ví dụ thuộc tính một trọng số phù hợp (relevance weight) phản ánh khả năng phân biệt các nhãn lớp của nó. Thuộc tính được chọn sẽ là thuộc tính có trọng số phù hợp vượt mức quy định. Thuật toán này là như sau: RELIEF(O, c, it s, ). O: tập tất cả các đối tượng c : số các thuộc tính điều kiện its: số bước lặp : giá trị ngưỡng đối với trọng số (1) R ← { } (2) Wa, Wa ←0 (3) for i = 1...it s (4) chọn ngẫu nhiên một đối tượng x từ tập tất cả các đối tượng O (5) tính nearHit và nearMiss của x (6) for j = 1...c (7) Wj ←Wj − diff(x j , nearH it j )/ it s + diff(x j , nearMiss j )/ it s (8) for j = 1...c (9) if Wj ≥ ; R ←R { j} (10) return R Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 30 Tham số đầu tiên mà người sử dụng phải cung cấp cho RELIEF là its. Tham số này chỉ ra số bước lặp, tức là số đối tượng mẫu được chọn liên tiếp để tính toán các trọng số. Tại mỗi lần lấy mẫu, một đối tượng x được chọn ngẫu nhiên rồi tính các giá trị nearHit và nearMiss của nó. nearHit là đối tượng có cùng nhãn lớp với x và gần x nhất, còn nearMiss là đối tượng gần x nhất nhưng không có cùng nhãn lớp với x. Độ gần nhau được đánh giá dựa trên khoảng cách giữa các đối tượng xác định như sau: Khoảng cách giữa hai đối tượng o và x là số tất cả các thuộc tính có giá trị khác nhau trên o và x, 1 ( , ) ( , ) C i i i dist o x diff o x với 1 ( , ) 0 i i i i i i o x diff o x o x Để sử dụng RELIEF, người sử dụng còn phải cung cấp một tham số thứ hai, đó là mức thích hợp tối thiểu mà mỗi thuộc tính được chọn phải đáp ứng. Có thể thấy, RELIEF sẽ là thuật toán lựa chọn thuộc tính không hiệu quả nếu tập dữ liệu có các thuộc tính điều kiện tương quan chặt chẽ với nhau và chúng đều cho trọng phù hợp cao như nhau. Hiện nay, RELIEF đã được một số tác giả phát triển cho phép lựa chọn thuộc tính từ cả các tập dữ liệu không nhất quán, có nhiễu và có nhiều nhãn lớp. Một tập dữ liệu được gọi là không nhất quán nếu chứa các cặp đối tượng mâu thuẫn nhau, nghĩa là các cặp đối tượng có cùng các giá thuộc tính điều kiện nhưng lại có nhãn lớp khác nhau. Áp dụng RELIEF vào tập dữ liệu ví dụ như sau: Chọn ngẫu nhiên một đối tượng, chẳng hạn đối tượng 0. Trong trường hợp này ta có nearHit là đối tượng 5 và nearMiss là đối tượng 12. Với mỗi thuộc tính j, trọng số phù hợp của nó Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 31 được cập nhật dần bằng một giá trị phụ thuộc vào sự khác nhau giữa xj và nearHit, cũng như sự khác nhau giữa xj và nearMiss. Cụ thể là tại lần chọn ngẫu nhiên một đối tượng thứ i, trọng số phù hợp của thuộc tính j sẽ là: Wj := Wj − diff(x j , nearH it j )/ it s + diff(x j , nearMiss j )/ it s . Quá trình cứ tiếp tục cho đến khi số bước lặp đạt tới giới hạn quy định its. Thuộc tính sẽ được thêm vào tập các thuộc tính lựa chọn nếu trọng số phù hợp của nó không thấp hơn mức yêu cầu Chạy RELIEF trên tập dữ liệu ví dụ với its = 100 và = 0 thu được tập cuối cùng các thuộc tính lựa chọn là {a,d,e,f }. Như vậy, ta đã loại bỏ được hai thuộc tính dư thừa là b và c. Với tập con gồm bốn thuộc tính được lựa chọn {a,d,e,f }, tính nhất quán của tập dữ liệu ban đầu vẫn được bảo tồn. Tuy nhiên, có thể thấy tập thuộc tính được chọn này vẫn còn có thể được thu gọn hơn bằng cách loại bỏ thêm thuộc tính e. 3.1.2. Thuật toán FOCUS Focus là một thuật toán rút gọn thuộc tính cũng được xây dựng theo cách tiếp cận filter. Thuật toán này áp dụng phương pháp tìm kiếm từng bước ưu tiên độ rộng từ thấp đến cao trong số tất cả các tập con của các thuộc tính để tìm ra tập con nhỏ nhất mà vẫn bảo tồn được tính nhất quán của tập dữ liệu huấn luyện. Tựa code của FOCUS là như sau: FOCUS(O, c). O: tập tất cả các đối tượng; c: số các thuộc tính điều kiện; (1) R ← { } (2) for num = 1...c (3) for mỗi tập con L có cỡ num (4) cons = Độnhấtquán(L, O) (5) if cons == true Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 32 (6) R ←L (7) return R (8) else continue Với mỗi giá trị num = 1, … , c , FOCUS kiến tạo tất cả các tập con thuộc tính cỡ num (tập con gồm num thuộc tính). Sau đó kiểm tra tính nhất quán của dữ liệu đối với mỗi tập con này. Nếu tính nhất quán bị vi phạm, tập con thuộc tính tương ứng sẽ bị loại. Thủ tục tìm kiếm tiếp tục cho đến khi tìm được tập con bảo tồn sự nhất quán của dữ liệu hoặc khi tất cả các tập con thuộc tính đã được xem xét hết. Dễ thấy, vì FOCUS sử dụng tính nhất quán của dữ liệu làm tiêu chuẩn lựa chọn tập con thuộc tính nên nó sẽ rất nhạy cảm với nhiễu dữ liệu. Hơn nữa, do số tập con (lực lượng của tập lũy thừa) của tập các thuộc tính tăng theo hàm mũ của số thuộc tính, thuật toán FOCUS sẽ không thể áp dụng được khi kích thước của tập dữ liệu huấn luyện là tương đối lớn. Để khắc phục trở ngại này, thông thường người ta cho phép tiến hành việc tìm tập thuộc tính rút gọn với một ngưỡng tỷ lệ các đối tượng mâu thuẫn nhau cho phép nào đó. Khi đó, dòng (5) của tựa code trên đây sẽ được thay bằng lệnh kiểm tra điều kiện if cons . Chú ý rằng, số đếm các đối tượng mâu thuẫn nhau được định nghĩa là hiệu số giữa số tất cả các đối tượng mâu thuẫn nhau và số các đối tượng mâu thuẫn nhau có nhãn lớp xuất hiện nhiều nhất. Chẳng hạn, có n đối tượng mâu thuẫn nhau trong tập dữ liệu với 2 nhãn lớp là 1 và 2; nếu trong số n đối tượng mâu thuẫn nhau có c1 đối tượng nhận nhãn lớp 1, c2 đối tượng nhận nhãn lớp 2, c1 + c2 = n. Khi đó, nếu 1 2c c thì (thay cho n) số các đối tượng đối lập sẽ được tính Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 33 bằng n - c1 và tỷ lệ các đối tượng đối lập trong tập dữ liệu sẽ là 1n c N , trong đó N là số tất cả các đối tượng có trong tập dữ liệu. Áp dụng FOCUS cho tập dữ liệu ví dụ 2.2: Trước tiên FOCUS đánh giá tính nhất quán của dữ liệu theo từng thuộc tính riêng biệt , , , , ,a b c d e f , (các tập con thuộc tính có cỡ bằng 1). Không có thuộc tính nào trong số các thuộc tính này bảo tồn tính nhất quán của dữ liệu. Chẳng hạn, với thuộc tính f , có hai đối tượng mâu thuẫn nhau là 0 và 12. Tiếp tục vòng lặp thứ hai, FOCUS đánh giá độ nhất quán của dữ liệu theo mỗi tập con gồm hai thuộc tính , ,a b ,a c , ,a d , ,a e , ,a f , ,b c ,b d , ,b e , ,b f , ,c d , ,c e , ,c f , ,d e , ,d f , ,e f . Trong số các tập con này cũng không có tập con nào cho phép bảo tồn tính nhất quán của dữ liệu và do đó tất cả đều bị loại. Tiếp tục vòng lặp thứ ba, tìm được tập con cỡ 3 bảo tồn tính nhất quán của dữ liệu là tập , ,a d f . Với kết quả này, tập thuộc tính ban đầu có thể được rút gọn lại thành tập , ,a d f mà vẫn duy trì được tính nhất quán của tập dữ liệu. 3.1.3. Thuật toán LVF Khác với RELIEF và FOCUS, thuật toán LVF thực hiện việc sinh các tập con thuộc tính để lựa chọn bằng phương pháp chọn ngẫu nhiên nhờ thuật toán tạo số ngẫu nhiên Las Vegas. Thuật toán LVF là như sau: LVF(O, C, att , ). O: tập tất cả các các đối tượng; C: tập tất cả các thuộc tính điều kiện; att : số bước lặp của thuật toán; : ngưỡng tỷ lệ các đối tượng mâu thuẫn nhau; Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 34 R: Tập con thuộc tính tốt nhất hiện thời. (1) R ← C (2) for num = 1...att (3) S ← Tập con thuộc tính chọn ngẫu nhiên( ) (4) if |S|≤ |R| (5) if Độnhấtquán(S, O) ≤ (6) if |S| < |R| (7) R ← S; output R (8) else R ← R S (9) return R Đầu tiên, LVF coi toàn bộ tập thuộc tính điều kiện là tập thuộc tính tốt nhất. Tiếp đó, chọn ngẫu nhiên một tập con từ tập tất cả các thuộc tính điều kiện. Nếu tập con thuộc tính này có lực lượng nhỏ hơn tập con tốt nhất hiện thời và cho tỷ lệ các đối tượng mâu thuẫn nhau trong tập dữ liệu không vượt quá ngưỡng cho trước, nó sẽ được xem là tập con mới tốt nhất. Một khi có tập con tốt hơn được phát hiện, tập con này sẽ được LVF đưa ra dưới dạng kết quả tính toán tức thời. Nhược điểm của LVF là tiêu tốn thời gian nhiều hơn so với các thuật toán heuristic trong việc tìm kiếm tập con thuộc tính tối ưu. Ngoài ra, khi tập dữ liệu có kích thước khổng lồ, việc kiểm tra tính nhất quán của dữ liệu cũng tiêu tốn khá nhiều thời gian. Xét tập dữ liệu ví dụ 2.2: LVF chọn ngẫu nhiên một tập con thuộc tính từ 6 thuộc tính đã cho, chẳng hạn tập {a,b,c}. Đối với tập thuộc tính này, sẽ có 6 đối tượng không nhất quán, trong đó có 3 đối tượng mang nhãn lớp 1, 3 đối tượng mang nhãn lớp 2, vậy tỷ lệ các đối tượng không nhất quán được tính bằng (6-3)/12=1/4. Nếu tỷ lệ đối tượng không nhất quán cho phép = 0 thì tập Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 35 {a,b,c} bị loại. Tiếp tục quá trình tìm kiếm ngẫu nhiên, LVF sẽ cho kết quả tập con thuộc tính tối ưu cục bộ là , ,a d f . 3.1.4. Thuật toán EBR EBR cũng là thuật toán lựa chọn thuộc tính theo tiếp cận filter. Thuật toán này áp dụng chiến lược tìm kiếm heuristic dựa vào entropy giống như một số thuật toán học máy, chẳng hạn thuật giá trị toán xây dựng cây quyết định C4.5 của Quinlan. Có thể mô tả EBR như sau: EBR(C) C: tập tất cả các thuộc tính điều kiện; (1) A C (2) calculate ( / )H D x ; (3) choose A giving lowest value of ( / )H D A ; (4) R ← A ; (5) do (6) T ← R ; (7) ( )A C R (8) if / ( / )H D R A H D T (9) T R A ; (10) ;R T (11) until ( / ) ( / )H D R H D C ; (12) return R ; Tại bước đầu tiên, EBR kiểm tra toàn bộ tập dữ liệu, chọn thuộc tính cho lượng thông tin thu thêm (information gain) lớn nhất, điều này tương đương với việc tìm thuộc tính A cho entropy có điều kiện ( / )H D A nhỏ nhất. Entropy ( / )H D A xác định bởi công thức: Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 36 2 1 1 ( / ) ( ) ( / )log ( / ) m n j i j i j j i H D A P a P d a P d a trong đó, 1 2, , ... , ma a a là các giá trị của A , 1 2, , ... , nd d d là các giá trị của thuộc tính quyết định D trong tập dữ liệu. Các xác suất được ước lượng được ước lượng dựa vào tập dữ liệu. Chẳng han: 1 1( ) S P a N trong đó 1S là số các đối tượng có giá trị thuộc tính A bằng a1 , N là số tất cả các đối tượng có trong tập dữ liệu. Tại các bước tiếp theo, EBR tìm tập con cho entropy có điều kiện ( / )H D R A nhỏ nhất trong số các tập con thu được bằng cách thêm vào tập R đã tìm được ở bước trước một thuộc tính còn lại. Tương tự như trên, ta có: 1 2( / , , ... , )kH C A A A 1 2 1 2 2 1 2 1 1 ( , , ... , ) ( / , , ... , )log ( / , , ... , ) m n j j kj i j j kj i j j kj j i P a a a P c a a a P c a a a trong đó, ( 1 2, , ... ,j j kja a a ), ( 12 22 2, , ... , ka a a ), … , ( 1 2, , ... ,m m kma a a ) là các tổ hợp giá trị khác nhau của các thuộc tính 1 2, , ... , kA A A . Xét tập dữ liệu ví dụ 2.2. Trước tiên, EBR tính entropy của mỗi thuộc tính điều kiện, thu được: Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 37 Tập con Entropy a 0.8885861 b 0.9543363 c 0.9543363 d 0.8885860 e 0.8650087 f 0.6186034 Vì {f} có entropy nhỏ nhất, nó trở thành thuộc tính được chọn đầu tiên. Tại bước thứ hai, EBR tính entropy của tất cả các tập con gồm f và một thuộc tính khác: Tập con Entropy ,a f 0.42382884 ,b f 0.46153846 ,c f 0.55532930 ,d f 0.42382884 ,e f 0.40347020 Tại đây, ,e f là tập con được chọn. … . Quá trình lựa chọn tiếp tục cho đến bước thứ tư, khi entropy nhỏ nhất của tập con đạt đến giá trị 0 (entropy ( / , , , , . )H g a b c d e f của tập dữ liệu nhất quán 2.2). Tập con thuộc tính chọn được là , , ,a b e f . Khi đó tập dữ liệu có thể được rút gọn lại chỉ với bốn thuộc tính a, b, e, f mà vẫn bảo tồn được tính nhất quán. Có thể thấy tập con thuộc tính này gần trùng với tập con thuộc tính tối ưu tìm được bởi thuật toán FOCUS. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 38 EBF có độ phức tạp tính toán là 2(( ) / 2)O n n . Ưu điểm của thuật toán này là có thể làm việc với các tập dữ liệu kích thước lớn, không đòi hỏi người sử dụng phải quy định bất kỳ một giá trị ngưỡng nào. 3.1.5. Thuật toán SCRAP SCRAP (Selection Construction Ranking using Attribute Pattern) là một thuật toán nữa dựa trên phương pháp filter, thuật toán tìm tập con tối ưu bằng cách tìm kiếm tuần tự các thuộc tính theo khoảng cách từng đối tượng. Scrap xét tất cả các đối tượng cùng một lúc bằng cách tính khoảng cách từng đối tượng để từ đó đưa ra sự tăng hay giảm những trọng số của mỗi thuộc tính liên quan tới những khoảng cách này. Công thức tính khoảng cách giữa hai đối tượng được cho trong (1). Những thuộc tính có trọng số phù hợp sẽ được đưa vào tập con tối ưu. Giả mã của thuật toán như sau: SCRAP(O) O, tập tất cả các đối tượng; (1) A ←{}; Wi , Wi = 0; (2) T ← Đốitượngngẫunhiên(); PoC ←T (3) while O ≠ {} (4) O ← O − PoC; PoCnew ←NewPoC(PoC) (5) n = dist(PoC,PoCnew) (6) if n == 1 (7) i = Thuộctínhkhác(PoC,X ); A ←A {i} (8) N ← Lấylâncậngần nhất(PoC,n) (9) X N (10) if Nhãnlớp(X ) == Nhãnlớp(N) (11) O ←O − X (12) if dist(PoC,X )==1 (13) i = Thuộctínhkhác(PoC,X ); Wi = Wi − 1 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 39 (14) else if dist(PoC,X ) > 1 (15) Tăngnếunhiềuthuộctínhkhácnhau(X ,W ) (16) R ←A (17) Wi , if Wi > 0 then R ←R { i} Quá trình tìm kiếm tuần tự tiến hành bắt đầu từ một đối tượng ngẫu nhiên với trọng số của đối tượng này được gán là 0, nó trở thành một PoC ban đầu. Một đối tượng gần PoC ban đầu nhất và thuộc nhãn lớp khác sẽ trở thành một PoC kế tiếp. Từ hai PoC này sau đó sẽ xác định một đối tượng lân cận, đó là đối tượng có cùng nhãn lớp và gần nhất với PoC ban đầu đồng thời phải xa đối tượng PoC kế tiếp nhất. Nếu những đối tượng có cùng nhãn lớp và gần PoC nhất đồng thời chỉ khác duy nhất một thuộc tính thì trọng số của thuộc tính tương ứng đó sẽ giảm đi một giá trị và thuộc tính này được xem là một thuộc tính có trọng số phù hợp với tất cả các đối tượng, bất chấp trọng số cuối cùng của nó là như thế nào thì thuộc tính này cũng được đưa vào tập con tối ưu. Còn nếu có nhiều hơn một đặc trưng thay đổi thì những trọng số phù hợp được kết hợp lại với nhau bằng cách tăng trọng số lên một giá trị. Những đối tượng đã được xác định là lân cận sẽ bị loại bỏ. Thuật toán dừng khi tất cả các đối tượng đã được gán một đối tượng lân cận. Những thuộc tính có một trọng số phù hợp với tất cả các đối tượng hoặc có trọng số phù hợp (<0) sẽ được chọn là tập con thuộc tính cuối cùng. Xét với tập dữ liệu ở bảng ví dụ 3.1. Scrap đầu tiên chọn một đối tượng ngẫu nhiên, ở đây giả sử là đối tượng 1 và tiến hành tìm lân cận gần nhất của nó với một nhãn lớp khác. Trong trường hợp này đối tượng 1 là PoC đầu tiên còn đối tượng 12 là PoC kế tiếp với 2 thuộc tính không giống nhau là d và e. Những đối tượng có khoảng cách xa đối tượng 12 và cùng nhãn lớp với đối tượng 1 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 40 được gán là lân cận cho 2 PoC này, đó là đối tượng 5 với chỉ một đặc trưng b là khác. Với kết quả này trọng số của b được tăng thêm một giá trị. Đối tượng 12 bây giờ trở thành PoC mới và thuật toán tiếp tục. Đối tượng 4 sẽ trở thành lân cận gần nhất với một loại nhãn khác nhau và với chỉ một thuộc tính a là có giá trị khác nhau. Đây là thuộc tính dùng để thêm vào tập con tối ưu bất kể trọng số cuối cùng của nó. Thuật toán kết thúc kết quả thu được là tập con {a,b,c,d,e,f}, a là một thuộc tính có trọng số phù hợp với tất cả các đối tượng, các thuộc tính còn lại đều có một trọng số cụ thể. Như vậy thuật toán không giảm được kích thước của tập thuộc tính. Ví dụ trên dùng để minh họa một trong những yếu điểm lớn nhất của phương pháp tiếp cận này - nó thường xuyên chọn quá nhiều thuộc tính. Điều này do tình trạng những trọng số bị giảm. Nếu có nhiều hơn một thuộc tính giữa một PoC và một đối tượng cùng nhãn lớp thì những trọng số của đặc trưng còn lại sẽ không bị thay đổi. Hạn chế này có thể khắc phục được bằng cách giảm bớt những trọng số của những đặc trưng khi tìm thấy chúng. Với sự cải tiến hợp lý và chạy thuật toán trên tập dữ liệu thì sẽ thu được một tập con nhỏ hơn là {a,b,e,f}. Sự thay đổi khác có thể làm giảm mỗi số hạng của tỷ lệ trọng số; ví dụ cho 3 thuộc tính không thích hợp, trọng số của chúng sẽ được giảm 1/3. Hiện tại Scrap chỉ xử lý những giá trị nhỏ, mặc dù nó tương đối dễ mở rộng cho giá trị của những đặc trưng. 3.1.6. Lựa chọn nhóm Đây là thuật toán điển hình trong lựa chọn thuộc tính dựa theo phương pháp filter, giải thuật sẽ thực hiện việc thêm vào hay loại bỏ những thuộc tính riêng lẻ hoặc nhóm thuộc tính vào tập thuộc tính tối ưu cuối cùng. Gần đây, có Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 41 những nghiên cứu lợi ích tiềm ẩn của nhóm thuộc tính ở mỗi giai đoạn thực hiện của thuật toán. Chiến lược này có thể làm giảm bớt thời gian thực hiện việc tìm những tập con tối ưu phù hợp bằng cách lựa chọn vài đặc trưng ngay tức thời . Để thực hiện thuật toán, ban đầu một thuật toán phân cụm được sử dụng để tự động phân cụm các thuộc tính, ở đây sử dụng thuật toán phân cụm k- means. Tư tưởng phân cụm của k - means được tóm tắt dưới đây. Input: Số các cụm k và cơ sở dữ liệu chứa n đối tượng Thuật giải: gồm 4 bước Phân hoạch đối tượng thành k tập con ( cụm). Tính các điểm hạt giống centroid ( trung bình của các đối tượng trong cụm ) cho từng cụm trong phân hoạch hiện hành. Gán mỗi đối tượng cho cụm centroid gần nhất Quay về bước 2, chấm dứt khi không còn phép gán mới. Từ những cụm thuộc tính có được từ thuật toán k - mean này (mỗi cụm có thể có một hoặc nhiều hơn hai thuộc tính) sẽ không có cụm thuộc tính nào là tập thuộc tính tối ưu mà mỗi cụm được đánh giá theo một quy định đánh giá trước. Tổng quan của thuật toán có thể quan sát ở dưới. GFS(G, ). G, tập tất cả các nhóm; , quy định mức thực hiện tập con thuộc tính. (1) R ←{}; A ←{}; best =0 (2) while evaluate(R) < (3) for each group Gi (4) T ← mọi thuộc tính từ Gi (5) t = evaluate(R T ) Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 42 (6) if ( > best ) (7) A ←T (8) best = t (9) R ←R A (10) output R Thuật toán quy định một mức giới hạn đây là mức giới hạn dùng để quyết định các thuộc tính trong một cụm đang được đánh giá có thể được thêm vào tập con tối ưu hay không, nếu cụm được thêm vào thì giá trị đánh giá của cụm thuộc tính không được vượt quá này. Quá trình tiếp tục so cho đến khi đạt được một tập con tối ưu cuối cùng. Thuật toán này có thể sánh được với phương pháp lựa chọn đặc trưng riêng lẻ chuẩn nhưng có lợi hơn về rút gọn thời gian tính toán. 3.2. Các thuật toán theo cách tiếp cận wrapper 3.3.1 Thuật toán LVW LVW là thuật toán rút gọn thuộc tính kiểu wrapper, xây dựng dựa trên thuật toán LVF đã trình bày trong mục 3.1.3. Tựa code của nó là như sau: LVW(C, K, ε). C : tập tất cả các thuộc tính điều kiện; K : Ngưỡng cập nhật; ε : Ngưỡng sai số. (1) R ← C ; k = 0 ; (2) While ε chưa được cập nhật lần thứ K (3) T ← randomfeatureSubset( ); (4) learn( )t R ; (5) if if ( )t or ( and )t T R (6) output T ; (7) 1k k ; Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 43 (8) learn( )R ; Trước tiên LVW coi toàn bộ tập thuộc tính điều kiện là tập con tốt nhất. Sau đó lần lượt sinh các tập con một cách ngẫu nhiên và đánh giá chúng thông qua kết quả áp dụng một thuật học. Quá trình này tiếp tục cho đến khi giá trị sai số ε đã được cập nhật đến lần thứ K (điều kiện dừng quy định trước) mà vẫn không phát hiện được tập con nào tốt hơn. Cuối cùng, LVF thực hiện việc kiểm chứng đối với kết quả (tập con) thu được. Trong các tài liệu hiện hành, thuật học thường được sử dụng để đánh giá các tập con thuộc tính là thuật học luật phân lớp bằng cây quyết định C4.5 của Quinlan, do tính đơn giản và độ hiệu quả của nó. 3.3.2 Thuật toán NEURALNET NEURALNET cũng là thuật toán lựa chọn thuộc tính kiểu wrapper sử dụng mạng nơron. Thuật toán này áp dụng phương pháp tìm kiếm tập con tối ưu bằng cách loại dần. Lược đồ của NEURALNET là như sau: NEURALNET ( , )maxC . C : tập tất cả các thuộc tính điều kiện; max : ngưỡng sai số phân lớp cho phép đối với mạng. (1) R ← C ; εw = 0 ; (2) do (3) T ← R ; (4) x R (5) S R x ; (6) S = trainNet(S) ; (7) if S w (8) w S ; w x ; (9) R R w ; Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 44 (10) until R max ; (11) trainNet(T) ; NEURALNET sử dụng một mạng nơron 3 lớp và một hàm đánh giá sai số (bao gồm cả sai số phân lớp lẫn độ phức tạp của mạng) trong suốt quá trình lựa chọn tập con thuộc tính tối ưu. Đầu tiên, NEURALNET coi toàn bộ tập thuộc tính điều kiện ban đầu là tập con tốt nhất với giá trị hàm đánh giá bằng 0. Sau đó thực hiện một quá trình tìm kiếm lùi. Tại mỗi vòng lặp, mạng được huấn luyện với mỗi tập con thuộc tính thu được bằng cách bớt đi một thuộc tính khỏi tập tốt nhất hiện thời. Một thuộc tính sẽ bị loại bỏ vĩnh viễn khỏi tập hiện thời nếu việc loại bớt nó làm tăng ít nhất giá trị hàm đánh giá (sai số phân lớp và độ phức tạp của mạng). Quá trình lặp tiếp tục cho đến khi giá trị hàm đánh giá cập nhật lớn hơn mức ngưỡng cho phép. 3.3. Một số thuật toán khác 3.3.1. Thuật toán Genetic Các thuật toán genetic là các thuật toán rất hiệu quả cho việc lựa chọn nhanh các thuộc tính. Không giống các chiến lược tìm kiếm kinh điển chỉ dẫn đến một lời giải duy nhất, các thuật toán genetic cho ta nhiều tập con thuộc tính tối ưu hoặc gần tối ưu. Trong các thuật toán genetic, mỗi tập con thuộc tính được biểu diễn bằng một sâu nhị phân có độ dài bằng số thuộc tính trong tập dữ liệu ban đầu. Vị trí thứ j trong sâu nhị phân là 1 hoặc 0 tùy thuộc vào thuộc tính thứ j có mặt hay không có mặt trong tập con. Quy trình chung của các thuật toán genetic là như sau: Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 45 Hình 3.1.Lựa chọn thuộc tính bằng các thuật toán Genetic Đầu tiên, một quần thể các sâu nhị phân được tạo lập. Việc tạo ra quần thể đầu tiên này như thế nào, với kích thước bao nhiêu là vấn đề quan trọng. Khi đã có quần thể các tập con, thuật toán tiến hành áp dụng các toán tử genetic (lai ghép, đột biến). Các toán tử này cùng với các xác suất áp dụng chúng được xem xét lựa chọn một cách kỹ lưỡng. Sau khi áp dụng các toán tử một quần thể tập con mới sẽ được tạo ra. Có hai cách đánh giá các tập con thuộc tính trong quần thể: Nếu việc lựa chọn thuộc tính sử dụng tiếp cận filter thì độ phù hợp của mỗi tập con thuộc tính X được đánh giá thông qua một hàm tiêu chuẩn ( )J X . Giá trị ( )J X càng lớn tập X càng tốt. Hàm tiêu chuẩn ( )J X thường được sử dụng là độ đo entropy theo Shannon hoặc hàm đánh giá độ phụ thuộc theo lý thuyết tập thô. Đối với cách tiếp cận wrapper, mỗi tập con thuộc tính được đánh giá thông qua sai số phân lớp của thuật học được sử dụng. Sai số phân lớp càng nhỏ tập con tập con tương ứng càng tốt. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 46 Đối với cả hai cách tiếp cận filter và wrapper, để định hướng cho việc tìm tập con tối ưu có kích thước nhỏ nhất, người ta đưa thêm vào hàm đánh giá độ phù hợp tham số kích thước của tập con. Để dừng quá trình tiến hóa, một tiêu chuẩn dừng. Tiêu chuẩn dừng thường được sử dụng là số các thế hệ được sinh ra hoặc ngưỡng tối thiểu cho mức độ phù hợp của tập con được chọn. Nếu tiêu chuẩn dừng không thỏa mãn, các tập con thuộc tính sẽ lại tiếp tục được lựa chọn và quá trình mô tả trên đây sẽ lặp lại. Các chiến lược lựa chọn thường được áp dụng là chiến lược bánh xe roulette và chiến lược căn cứ vào thứ hạng. Với chiến lược lựa chọn bánh xe roulette, xác suất để một tập con được chọn tỷ lệ thuận với độ phù hợp của nó. Với chiến lược lựa chọn căn cứ vào thứ hạng, các tập con được sắp thứ tự theo độ phù hợp của chúng và xác suất để một tập con được chọn tỷ lệ thuận với thứ tự của nó trong danh sách xếp hạng. Cũng như mọi cách tiếp cận khác, các thuật toán genetic thường chỉ lựa chọn được tập con thuộc tính tối ưu cục bộ. Bên cạnh đó, do có nhiều thế hệ các tập con thuộc tính được tạo, việc đánh giá độ phù hợp của chúng sẽ tiêu tốn rất nhiều thời gian. 3.3.2. Lựa chọn thuộc tính thông qua rời rạc hóa dữ liệu Rời rạc hóa dữ liệu cũng là một khâu trong bước tiền xử lý. Rời rạc hóa dữ liệu là việc biến đổi các thuộc tính định lượng liên tục thành những thuộc tính rời rạc thỏa mãn một tiêu chuẩn quy định. Rời rạc hóa dữ liệu trước khi khai phá có ba lợi ích: Cho phép áp dụng các thuật toán khai phá hiệu quả hiện có, Làm giảm kích thước dữ liệu, tăng tốc độ tính toán, Làm tăng độ chính xác, tính dễ hiểu của các kết quả thu được. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 47 Ngoài các lợi ích trên, gần đây người ta còn sử dụng một số thuật toán rời rạc hóa vào việc giải quyết vấn đề lựa chọn thuộc tính trong khai phá dữ liệu và học máy. Mục này trình bày hai thuật toán rời rạc hóa như thế, đó là ChiMerge và Chi2. Chi2 là phát triển của KhiMerge. Cả hai thuật toán này đều là những thuật toán rời rạc hóa có giám sát (nghĩa là có sử dụng thông tin của thuộc tính quyết định (nhãn lớp). Để rời rạc hóa các thuộc tính, chúng áp dụng phương pháp kết nối từng bước các khoảng giá trị (từ dưới lên) sử dụng phép kiểm định Khi-bình-phương đối với giả thuyết về sự độc lập giữa thuộc tính nhãn lớp và mỗi cặp khoảng giá trị liền kề của thuộc tính. Khi quá trình rời rạc hóa kết thúc, nếu tất cả các giá trị của một thuộc tính nào đó được gộp lại thành một khoảng duy nhất thì thuộc tính đó sẽ bị loại khỏi tập con thuộc tính lựa chọn. Trước khi trình bày thuật toán ChiMerge và Chi2, ta trình bày khái niệm về bảng tiếp liên (contingency table) và phép kiểm định Khi-bình-phương. Bảng tiếp liên và phép kiểm định sự độc lập Khi-bình-phƣơng Trong thống kê toán học, để kiểm tra giả thuyết về sự độc lập của hai biến ngẫu nhiên X và Y (liên tục hay rời rạc) người ta đã đề xuất phép kiểm định Khi- bình-phương như sau: Chia miền giá trị của X và Y thành một số hữu hạn các khoảng. Nếu X hay Y chỉ nhận một số ít giá trị thì có thể coi mỗi giá trị là một khoảng. Đối với biến ngẫu nhiên liên tục nên chia miền giá trị của nó thành các khoảng có độ rộng bằng nhau. Giả sử có mẫu cỡ N về véc tơ ngẫu nhiên (X,Y). Gọi - r và s lần lượt là số khoảng chia miền giá trị của X và Y ; Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 48 - iA là biến cố X nhận giá trị trong khoảng thứ i, i = 1, 2, … , r ; - jB là biến cố Y nhận giá trị trong khoảng thứ j, j = 1, 2, … , s ; - i jn là số cá thể mẫu có giá trị X trong khoảng thứ i và giá trị Y trong khoảng thứ j, (tức i jn là tần số quan sát được của biến cố i jA B ) ; - . i j 1 s i j n n là số cá thể mẫu có giá trị X thuộc khoảng i (tức tần số quan sát của biến cố iA ) ; - . i j 1 r j i n n là số cá thể mẫu có giá trị Y thuộc khoảng j (tức tần số quan sát của biến cố jB ) ; Hiển nhiên, 1 1 r s i j i j n N . Các dữ liệu trên được sắp vào một bảng gọi là bảng tiếp liên (hay bảng chéo): Biến 1 2 . . . s Tổng 1 2 . . . r 11n 12n . . . 1sn 21n 21n . . . 2sn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1rn 1rn . . . r sn 1 .n 2.n . . . .rn Tổng . 1n . 2n . . . . sn N Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 49 Từ bảng dữ liệu trên thu được: - Tần số quan sát của biến cố i jA B là i jn , i = 1, 2, … , r ; j = 1, 2, … , s. - Ước lượng tần số lý thuyết các cá thể mẫu có giá trị X thuộc khoảng thứ i và giá trị Y thuộc khoảng thứ j khi giả thuyết về sự độc lập giữa X và Y đúng. Ước lượng đó là . . . .i j i jn n n n N N N N Để kiểm định giả thuyết 0H : X và Y độc lập với đối thuyết 1H : X và Y không độc lập, người ta sử dụng thống kê 2 sau đây: 2 . . 2 . .1 1 i j i jr s i ji j n n n N n n N (1) Có thể thấy 2 là số đo đánh giá mức độ sai khác giữa các tần số lý thuyết và tần số quan sát được của các biến cố i jA B khi X và Y là độc lập nhau. Người ta đã chứng minh rằng với cỡ mẫu N đủ lớn, 2 sẽ có phân phối tiệm cận Khi-bình-phương với ( 1)( 1)r s bậc tự do. Từ đó, suy ra quy tắc kiểm định gỉa thuyết 0H là như sau: - Chọn mức ý nghĩa (thường là 0,05 hoặc 0,1); Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 50 - Tính giá trị của thống kê 2 theo công thức (1); - Tra bảng phân phối Khi-bình-phương ( 1)( 1)r s bậc tự do, tìm phân vị (giá trị ngưỡng) 2 ứng với mức ý nghĩa đã cho; - Bác bỏ giả thuyết 0H nếu 2 2 , chấp nhận 0H trong trường hợp ngược lại 2 2 . 2 2 có nghĩa là với xác suất 1 có thể khẳng định hai biến ngẫu nhiên X và Y là độc lập nhau. Thuật toán ChiMerge Giả sử thuộc tính quyết định (nhãn lớp) trong bảng quyết định có k giá trị phân biệt. Thuật toán ChiMerge bao gồm các bước sau đây: 1. Chọn mức ý nghĩa (thường là 0,05 hoặc 0,1) ; 2. Sắp thứ tự dữ liệu của thuộc tính cần rời rạc hóa. Bắt đầu quá trình rời rạc hóa bằng cách coi mỗi giá trị là một khoảng ; 3. Với mỗi cặp khoảng liền kề, tính giá trị thống kê 2 theo công thức: 2 . . 2 2 . .1 1 i j i jk i ji j n n n N n n N (2) 4. Kết nối cặp khoảng liền kề cho giá trị 2 nhỏ nhất và thỏa mãn 2 2. (Giá trị ngưỡng 2 là phân vị mức của phân phối Khi- bình-phương với k – 1 bậc tự do, (tra được từ bảng phân phối Khi-bình- phương). Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 51 5. Lặp lại các bước 2-3 cho đến khi tất cả các giá 2 tính được đối với mọi cặp khoảng lớn hơn giá trị ngưỡng 2 . ChiMerge có độ phức tạp tính toán là 2O( )N trong đó N là số đối tượng có trong bảng quyết định. Tuy vậy, với một số thao tác tối ưu hóa có thể làm giảm độ phức tạp xuống O(N.logN). Thuật toán Chi2 Chi2 là thuật toán do Liu và Setino phát triển dựa trên nền thuật toán ChiMerge [ ]. Khó khăn gặp phải khi sử dụng ChiMerge là việc chọn giá trị thích hợp cho mức ý nghĩa . Để giải quyết khó khăn này, Liu và Setino đã cải tiến ChiMerge theo hai hướng: - Để cho thuật toán tự động xác định giá trị từ chính bản thân dữ liệu huấn luyện. Hơn thế, giá trị được tính toán riêng cho mỗi thuộc tính cần rời rạc hóa. - Lấy tỷ lệ dữ liệu không nhất quán làm tiêu chuẩn dừng. Thay vì cố định trước mức ý nghĩa , Chi2 cho phép tự động giảm dần giá trị này. Quá trình rời rạc hóa một thuộc tính nào đó sẽ tiếp tục cho đến khi tiêu chuẩn dừng thỏa mãn. Thuật toán Chi2 bao gồm hai pha. Pha 1: 1. Cho mức ý nghĩa giá trị ban đầu lớn (chẳng hạn bằng 0,5) ; 2. Sắp thứ tự dữ liệu theo thuộc tính rời rạc hóa ; 3. Bắt đầu quá trình rời rạc hóa bằng cách coi mỗi giá trị là một khoảng ; 4. Với mỗi cặp khoảng liền kề, tính giá trị thống kê 2 theo (2) ; Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 52 5. Kết nối thành một khoảng cặp khoảng liền kề cho giá trị 2 nhỏ nhất ; 6. Lặp lại các bước 2-4 cho đến khi không còn cặp khoảng liền kề nào có thể kết nối được (không có giá trị 2 nào nhỏ hơn ngưỡng 2 ) ; 7. Lặp lại các bước 2-5 cho mỗi thuộc tính cần rời rạc hóa ; 8. Giảm mức ý nghĩa ; 9. Lặp lại toàn bộ pha 1 cho đến khi tỷ lệ không nhất quán trong dữ liệu vượt mức quy định . Pha 2: 1. Đối với mỗi thuộc tính, cho mức ý nghĩa giá trị nhỏ nhất sau khi kết thúc pha 1. 2. Sắp thứ tự dữ liệu theo thuộc tính; 3. Với mỗi cặp khoảng liền kề, tính giá trị thống kê 2 theo (2); 4. Kết nối thành một khoảng cặp khoảng liền kề cho giá trị 2 nhỏ nhất ; 5. Lặp lại các bước 2-4 cho đến khi không còn cặp khoảng liền kề nào có thể kết nối được (không có giá trị 2 nào nhỏ hơn ngưỡng 2 ) ; 6. Kiểm tra tỷ lệ không nhất quán trong dữ liệu của thuộc tính. Nếu tỷ lệ này không vượt quá mức quy định, cho giảm mức ý nghĩa và tiếp tục quá trình rời rạc hóa. Trường hợp ngược lại, kết thúc phép rời rạc hóa thuộc tính; 7. Lặp lại các bước 2-7 đối với tất cả các thuộc tính còn có thể kết nối được cho đến khi không còn thuộc tính nào còn có thể tiếp tục kết nối. Pha thứ nhất của Chi2 là một mở rộng của ChiMerge. Thay vì xác định trước mức ý nghĩa , Chi2 cho phép tự động giảm dần giá trị này. Tỷ lệ dữ liệu Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 53 không nhất quán được sử dụng làm tiêu chuẩn dừng. Các cải tiến này làm cho Chi2 có thể xác định một cách tự động các giá trị ngưỡng mà vẫn bảo tồn được thông tin phân lớp của dữ liệu ban đầu. Pha thứ hai của Chi2 là pha tiếp tục cải thiện kết quả rời rạc hóa. Nếu các khoảng giá trị của một thuộc tính nào đó có thể tiếp tục kết nối (bằng cách cho giảm mức ý nghĩa) mà không làm cho tỷ lệ dữ liệu không nhất quán vượt qúa mức quy định, thì quá trình kết nối sẽ tiếp tục được thực hiện. Trong khi pha thứ nhất của Chi2 sử dụng mức ý nghĩa chung cho việc rời rạc hóa tất cả các thuộc tính, pha thứ hai sử dụng mức ý nghĩa khác nhau cho từng thuộc tính. 3.4. Kết luận chƣơng 3 Trong chương 3 này chúng tôi đã trình bày kết quả nghiên cứu một số thuật toán lựa chọn thuộc tính điển hình. Các thuật toán được trình bày theo ba nhóm chính: các thuật toán kiểu filter, các thuật toán kiểu wrapper và một số thuật toán khác. Các thuật toán này thường được sử dụng để lựa chọn thuộc tính giải quyết các vấn đề phân cụm và phân lớp trong khai phá dữ liệu. Mỗi thuật toán đều có tựa code, giải thích và được minh họa bằng ví dụ tính toán cụ thể. Độ phức tạp của một số thuật toán cũng đã được chỉ ra. Các thuật toán trình bày trong mục 3.3. là những thuật toán mới được đề xuất trong những năm gần đây. Đây là những thuật toán hiệu quả, thường được áp dụng nhất. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 54 KẾT LUẬN 1. Nội dung nghiên cứu và kết quả đạt được của luận văn Khai phá dữ liệu là một môn khoa học liên ngành: Cơ sở dữ liệu, học máy và thống kê toán học, nghiên cứu các kỹ thuật “đào núi tìm vàng” nhằm phát hiện những thông tin có giá trị, tiềm ẩn trong các CSDL lớn mà con người sở hữu ngày một nhiều trong những năm gần đây. Các kết quả nghiên cứu cùng với những ứng dụng thành công trong khai phá dữ liệu, khám phá tri thức cho thấy khai phá dữ liệu là một lĩnh vực khoa học tiềm năng, mang lại nhiều lợi ích, đồng thời có ưu thế hơn hẳn so với các công cụ phân tích dữ liệu truyền thống. Các CSDL cần khai phá thường có kích thước rất lớn, chẳng hạn các CSDL tin-sinh-học (Bioinformatics), CSDL đa phương tiện, CSDL giao tác, … . Các CSDL này thường chứa tới hàng ngàn thuộc tính, gây rất nhiều khó khăn cho việc khai phá, thậm chí còn làm cho nhiệm vụ khai phá trở nên bất khả thi. Vấn đề đặt ra là phải tìm cách rút gọn số thuộc tính. Rút gọn thuộc tính (còn gọi là rút gọn số chiều – Dimension reduction) là làm giảm số chiều của không gian thuộc tính, loại bỏ dữ liệu dư thừa, không liên quan. Rút gọn thuộc tính đóng vai trò quan trọng trong bước tiền xử lý dữ liệu cũng như trong quá trình khai phá. Thông qua việc lựa chọn những thuộc tính quan trọng chúng ta có thể rút gọn dữ liệu, tạo ra khả năng khai phá những cơ sở dữ liệu kích thước lớn, nâng cao hiệu quả tính toán, cũng như làm tăng độ chính xác của các kết quả khai phá được từ CSDL. Từ năm 1970 đến nay, rút gọn thuộc tính đã trở thành đề tài được quan tâm bởi nhiều nhà nghiên cứu thuộc các lĩnh vực nhận dạng thống kê, học máy, khai phá dữ liệu. Luận văn này trình bày những kết quả nghiên cứu của học viên về vấn đề rời rạc hóa trong khai phá dữ liệu. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 55 Chương 1 của luận văn trình bày khái quát về khai phá dữ liệu. Chương 2 và chương 3 là nội dung chính của luận văn. Trong chương 2 này, chúng tôi đã trình bày khái quát về nội dung, các phương pháp và quy trình giải quyết vấn đề lựa chọn thuộc tính. Một số ứng dụng quan trọng của lựa chọn thuộc tính cũng đã được bàn tới ở cuối chương 2. Chương 3 dành cho việc trình bày kết quả nghiên cứu một số thuật toán lựa chọn thuộc tính điển hình. Các thuật toán được trình bày theo ba nhóm chính: các thuật toán kiểu filter, các thuật toán kiểu wrapper và một số thuật toán khác. Mỗi thuật toán đều có tựa code, được giải thích và minh họa bằng ví dụ tính toán cụ thể. Độ phức tạp của một số thuật toán cũng đã được chỉ ra. 2. Hướng nghiên cứu tiếp theo Trên cơ sở các kết quả nghiên cứu trình bày trong luận văn, tôi nhận thấy có nhiều vấn đề có thể tiếp tục nghiên cứu. Cụ thể là: Nghiên cứu vấn đề lựa chọn thuộc tính theo tiếp cận lý thuyết tập thô, mạng nơron. Vấn đề lựa chọn thuộc tính cho từng nhiệm vụ khai phá dữ liệu cụ thể, chẳng hạn cho việc học luật quyết định bằng cây quyết định, cho việc xây dựng các hàm hồi quy, … . Nghiên cứu cài đặt các thuật toán bằng ngôn ngữ lập trình cụ thể, tính toán thực nghiệm trên các cơ sở dữ liệu lớn thu thập từ thực tiễn hoặc trên Internet. Trong quá trình thực hiện luận văn, tôi đã cố gắng tập trung tìm hiểu và tham khảo nhiều tài liệu liên quan. Tuy nhiên, do thời gian nghiên cứu và trình độ có hạn nên không tránh khỏi những thiếu sót. Tôi rất mong nhận được sự nhận xét, góp ý của các thầy cô giáo, bạn bè, đồng nghiệp và những ai quan tâm để luận văn được hoàn thiện hơn. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 56 Tài liệu tham khảo Tiếng Việt [1] Lý Hoàng Tú, Lý thuyết Xác suất thống kê. Nhà Xuất bản Khoa học và Kỹ thuật, Hà nội 2001. [2] Nguyễn Bình, Lý thuyết Thông tin. Học viện Công nghệ Bưu chính Viễn thông, Hà nội, 2006. [3] Nguyễn Thanh Tùng, Một tiêu chuẩn mới lựa chọn node xây dựng cây quyết định. Báo cáo tại Hội thảo quốc gia “Một số vấn đề chọn lọc của CNTT”, Huế, 8/2008. Tiếng Anh [1] Dash, M., Liu, H. ”Feature selection for classification”. Intelligent Data Analysis 1 pp 131-156 (1997). [2] Isabelle Guyon Andr Elisseeff, ”An Introduction to Variable and Feature Selection” Journal of Machine Learning Research 3 pp 1157-1182 (2003). [3] Aleks Jakulin and Ivan Bratko. Analyzing attribute dependencies. In PKDD, 2003. [4] C.E. Shannon, W. Weaver, The Mathematical Theory of Communication, University of Illinois Press, Urbana, IL, 1949. [6] Yu, L., Liu, H.: Efficient feature selection via analysis of relevance and redundancy. Journal of Machine Learning Research 5 (2004) 1205-1224 [7] C.H. Chen, Statistical Pattern Recognition, Spartan Books, Washington, DC, 1973. [8] A. L. Blum and P. Langley. Selection of relevant features and examples in machine learning. Artificial Intelligence, 97:245-271, 1997. [9] H. Almuallim and T. G. Dietterich. Learning boolean concepts in the presence of many irrelevant features. Artificial Intelligence, 69(1- 2):279-305, Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 57 1994. [10] M. A. Hall. Correlation-based feature selection for discrete and numeric class machine learning. In ICML, 2000. [11] L. Yu and H. Liu. Feature selection for highdimensional data: a fast correlation-based filter solution. In ICML, 2003. [12] Kohavi, R., John, G.H.: Wrappers for feature subset selection. Artificial Intelligence 97(1-2) (1997) 273-324. [14] Jakulin, A.: Attribute interactions in machine learning. Master’s thesis, University of Ljubljana, Faculty of Computer and Information Science (2003). [15] Yeung, R.W.: A new outlook on Shannon’s information measures. IEEE Transactions on Information Theory 37 (1991) 466-474. [16] Duch, W., Winiarski, T., Biesiada, J., Kachel, A.: Feature selection and ranking filters. In: International Conference on Artificial Neural Networks (ICANN) and International Con-ference on Neural Information Processing (ICONIP). (2003) 251-254. [18] Fleuret, F.: Fast binary feature selection with conditional mutual information. Journal of Machine Learning Research 5 (2004) 1531-1555. [19] C.L. Blake and C.J. Merz. UCI repository of machine learning databases, 1998. [20] Vapnik V, The Nature of Statistical Learning Theory, New York: Springer, 1995. [21] Ian H. Witten and Eibe Frank. Data mining: Practical machine learning tools and techniques with Java implementations. Morgan Kaufman, San Francisco, CA, USA, 2000. [23] Moore, A.W. and Lee, M.S., ”Efficient algorithms for minimizing cross validation error.” In: Proceedings of Eleventh International Conference on Machine Learning, Morgan Kaufmann, New Brunswick, New Jersey, 190-198, (1994).