Tài liệu Xây dựng tập thuộc tính rút gọn theo cách tiếp cận tập thô

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐH CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG ------------------- TRẦN THU PHƯƠNG XÂY DỰNG TẬP THUỘC TÍNH RÚT GỌN THEO CÁCH TIẾP CẬN TẬP THÔ LUẬN VĂN THẠC SỸ KHOA HỌC MÁY TÍNH Chuyên ngành : Khoa học máy tính Mã số : 60 48 01 Thái Nguyên, năm 2011 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn XÂY DỰNG TẬP THUỘC TÍNH RÚT GỌN THEO CÁCH TIẾP CẬN TẬP THÔ 1 LỜI CẢM ƠN Để hoàn tất một luận văn Thạc sĩ yêu cầu sự tập trung, sự cố gắng và độc lập nghiên cứu. Bản thân tôi sau những năm tháng học tập vất vả và nghiên cứu cũng đã cố gắng để hoàn thành được luận văn này. Tôi luôn ghi nhận những sự đóng góp giúp đỡ nhiệt tình của những người bên cạnh mình, sự ủng hộ, sự hỗ trợ của bố mẹ, bạn bè giúp tôi có thêm động lực để hoàn thành khóa luận tốt nghiệp, nhân đây tôi muốn gửi lời cảm ơn nhất tới họ. Lời cảm ơn trân trọng đầu tiên tôi muốn dành tới GS.TS Vũ Đức Thi, người thầy đã dìu dắt và hướng dẫn tôi trong suốt quá trình làm luận văn, sự chỉ bảo và định hướng của thầy giúp tôi tự tin nghiên cứu những vấn đề mới và giải quyết bài toán một cách khoa học. Tôi xin trân trọng cảm ơn Ban giám hiệu Trường Đại học Công nghệ Thông tin và Truyền thông, Đại học Thái nguyên; Trường Dự bị Đại học Dân tộc Sầm Sơn, Thanh Hóa đã tạo các điều kiện cho chúng tôi được học tập và làm khóa luận một cách thuận lợi. Lời cảm ơn sâu sắc muốn được gửi tới các thầy giáo Viện Công nghệ Thông tin - Viện khoa học Việt Nam, những người thầy đã dạy dỗ và mở ra cho chúng tôi thấy chân trời tri thức mới, hướng dẫn chúng tôi cách khám phá và làm chủ công nghệ mới. Tôi muốn gửi lời cảm ơn chân thành đến tập thể lớp CHK8B-KHMT đã cùng tôi đi qua những tháng ngày miệt mài học tập, cùng chia sẻ những niềm vui, nỗi buồn, động viên tôi đi qua những khó khăn, để tôi vững bước vượt qua những vất vả, quyết tâm hoàn thành luận văn này. Tôi xin trân trọng cảm ơn bố mẹ, người thân, bạn bè, đồng nghiệp, những người đã mang tới tất cả niềm tin, định hướng và theo dõi tôi trong suốt chặng đường đời. Nâng đỡ và đến bên tôi những giây phút khó khăn nhất của cuộc sống. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn XÂY DỰNG TẬP THUỘC TÍNH RÚT GỌN THEO CÁCH TIẾP CẬN TẬP THÔ 2 Tuy nhiên do thời gian có hạn, mặc dù đã nỗ lực cố gắng hết mình nhưng chắc rằng luận văn khó tránh khỏi những thiếu sót. Rất mong được sự chỉ bảo, góp ý tận tình của Quý thầy cô và các bạn. Thanh Hóa, tháng 9 năm 2011 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn XÂY DỰNG TẬP THUỘC TÍNH RÚT GỌN THEO CÁCH TIẾP CẬN TẬP THÔ 3 MỤC LỤC LỜI CẢM ƠN .....................................................................................................1 DANH MỤC HÌNH VẼ ....................................................................................5 DANH MỤC BẢNG BIỂU................................................................................6 DANH MỤC TỪ VIẾT TẮT .............................................................................7 LỜI MỞ ĐẦU ....................................................................................................8 CHƢƠNG 1: TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU VÀ .........................10 LÝ THUYẾT TẬP THÔ ..................................................................................10 1. 1 Khai phá dữ liệu ...........................................................................................10 1.1.1 Khai phá tri thức ......................................................................................10 1.1.2 Khai phá dữ liệu ......................................................................................12 1.1.2.1 Một số khía cạnh khai phá chủ yếu ..................................................13 1.1.2.2 Một số kỹ thuật Khai phá dữ liệu .....................................................14 1.2 Lý thuyết tập thô ...........................................................................................18 1.2.1 Giới thiệu về tập thô ................................................................................18 1.2.2 Bảng quyết định .......................................................................................20 1.3 Kết luận chƣơng 1 .........................................................................................22 CHƢƠNG 2. XÂY DỰNG TẬP THUỘC TÍNH RÚT GỌN ..........................24 THEO CÁCH TIẾP CẬN TẬP THÔ .............................................................24 2.1 Luật và quá trình khám phá Luật trong Bảng quyết định. ......................24 2.1.1 Định nghĩa về luật và các đặc trưng. .......................................................24 2.1.2. Khám phá luật bởi bảng phân bố tổng quát dựa trên tập thô và thuật toán tối ưu hoá các luật .............................................................................................25 2.2. Vấn đề rời rạc hoá dựa trên lý thuyết tập thô ..........................................26 2.2.1. Các định nghĩa ........................................................................................27 2.2.2. Vấn đề rời rạc hoá dựa trên lý thuyết tập thô .........................................29 2.3 Một số thuật toán sử dụng lý thuyết tập thô ..............................................31 2.3.1. Thuật toán lựa chọn thuộc tính sử dụng tập thô theo phương pháp đánh giá kinh nghiệm. ...............................................................................................31 2.3.2. Thuật toán tìm tập rút gọn dựa vào cặp số phân biệt được ....................35 2.3.3. Thuật toán sử dụng các phép toán đại số ...............................................36 2.3.4 Thuật toán tìm lõi của bảng quyết định ...................................................39 2.3.5. Thuật toán tìm tập rút gọn theo xấp xỉ ngoài .........................................39 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn XÂY DỰNG TẬP THUỘC TÍNH RÚT GỌN THEO CÁCH TIẾP CẬN TẬP THÔ 4 2.3.6. Thuật toán tìm tập rút gọn theo xấp xỉ trong ..........................................40 2.4 Một số thuật toán lập nhóm văn bản ..........................................................42 2.4.1. Thuật toán K – means ............................................................................42 2.4.2. Thuật toán lập nhóm theo cây phân cấp .................................................42 2.4.3. Xác định các thuật đại diện cho nhóm ...................................................44 2.4.4. Độ tương tự giữa văn bản và nhóm văn bản ..........................................44 2.5 Kết luận chƣơng 2 .........................................................................................44 CHƢƠNG 3. SỬ DỤNG MỘT THUẬT TOÁN ĐỂ TÌM TẬP THUỘC TÍNH RÚT GỌN THEO CÁCH TIẾP CẬN TẬP THÔ PHỤC VỤ .................................45 BÀI TOÁN TRA CỨU THÔNG TIN ..............................................................45 3.1 Tra cứu thông tin ..........................................................................................45 3.2 Tra cứu thông tin văn bản ...........................................................................46 3.2.1 Tra cứu thông tin văn bản ........................................................................46 3.2.2 Xử lý hệ thống thông tin văn bản ............................................................47 3.2.3 Một số kỹ thuật tra cứu thông tin văn bản ...............................................48 3.3 Phƣơng pháp tra cứu thông tin áp dụng lý thuyết tập thô .......................50 3.3.1 Xây dựng tập văn bản ..............................................................................50 3.3.2 Gán trọng số cho thuật ngữ bởi dung sai xấp xỉ ......................................50 3.3.3 Phân cụm văn bản ....................................................................................52 3.3.4 Biểu diễn đặc trưng các cụm ...................................................................53 3.3.5 Độ tương tự giữa văn bản và cụm ...........................................................54 3.4 Kết luận chƣơng 3 .........................................................................................54 CHƢƠNG 4. XÂY DỰNG HỆ THỐNG VÀ THỬ NGHIỆM .......................55 4.1 Môi trƣờng và nền tảng phát triển ..............................................................55 4.2 Một số giao diện của hệ thống .....................................................................55 4.2.1 Xây dựng cơ sở dữ liệu............................................................................55 4.2.2 Giao diện của hệ thống ............................................................................56 4.2.2.1 Phương pháp xây dựng kho dữ liệu .................................................56 4.2.2.2 Một số giao diện ...............................................................................57 4.3 Kết luận chƣơng 4 .........................................................................................58 KẾT LUẬN ......................................................................................................59 TÀI LIỆU THAM KHẢO ................................................................................60 PHỤ LỤC : DANH SÁCH CÁC TỪ DỪNG, TỪ TẦM THƢỜNG ..............63 PHỤ LỤC TỪ DỪNG, TỪ TẦM THƢỜNG..................................................64 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn XÂY DỰNG TẬP THUỘC TÍNH RÚT GỌN THEO CÁCH TIẾP CẬN TẬP THÔ 5 DANH MỤC HÌNH VẼ Hình 1.1: Mô hình mô tả quá trình khai phá tri thức ...................................11 Hình 3.1 Nguyên lý tra cứu thông tin.............................................................45 Hình 3.2 Mô hình hệ thống tra cứu thông tin văn bản. ................................47 Hình 3.3 Các bƣớc mô tả xây dựng hệ thống. ...............................................48 Hình 3.4 Mô hình bài toán tra cứu thông tin áp dụng lý thuyết tập thô. .....50 Hình 3.5 Thuật toán phân cụm văn bản. .......................................................53 Hình 3.6 Tìm thuật ngữ đại diện cho cụm. ....................................................54 Hình 4.1 Bảng thông tin tài liệu. ....................................................................55 Hình 4.2. Bảng lƣu trữ thông tin các lĩnh vực. .............................................55 Hình 4.3 Bảng lƣu trữ thông tin ngôn ngữ....................................................56 Hình 4.4. Bảng thông tin từ chủ đề. ...............................................................56 Hình 4.5 Giao diện trang chủ hệ thống tra cứu. ...........................................57 Hình 4.6. Kết quả tra cứu của hệ thống. ........................................................58 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn XÂY DỰNG TẬP THUỘC TÍNH RÚT GỌN THEO CÁCH TIẾP CẬN TẬP THÔ 6 DANH MỤC BẢNG BIỂU Bảng 1.1 Bảng hệ thống thông tin về bệnh cúm. ...........................................22 Bảng 1.2 Bảng rút gọn thứ nhất của hệ thống bệnh cúm (R1) .....................22 Bảng 1.3 Bảng rút gọn thứ hai của hệ thống bệnh cúm (R2) .......................22 Bảng 2.1 Bảng thông tin mô tả các đối tƣợng ...............................................34 Bảng 2.2. Khởi tạo ban đầu ............................................................................34 Bảng 2.3 Chọn {a} ...........................................................................................34 Bảng 2.4 Chọn {b} ...........................................................................................35 Bảng 2.5 Chọn {d} ...........................................................................................35 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn XÂY DỰNG TẬP THUỘC TÍNH RÚT GỌN THEO CÁCH TIẾP CẬN TẬP THÔ 7 DANH MỤC TỪ VIẾT TẮT STT Chữ viết tắt Mô tả 1 KDD Knowledge Data Development 2 CSDL Cơ sở dữ liệu 3 SVM Support Vector Machine 4 DM Data Mining Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn XÂY DỰNG TẬP THUỘC TÍNH RÚT GỌN THEO CÁCH TIẾP CẬN TẬP THÔ 8 LỜI MỞ ĐẦU 1. Tính cấp thiết của đề tài Cùng với sự phát triển của khoa học kỹ thuật và việc ứng dụng công nghệ thông tin trong nhiều lĩnh vực của đời sống, kinh tế xã hội trong nhiều năm qua cũng đồng nghĩa với lượng dữ liệu đã được các cơ quan thu thập và lưu trữ ngày một tích luỹ nhiều lên, loài người đã và đang lưu trữ một lượng thông tin vô cùng rộng lớn. Tuy nhiên, việc khai thác nguồn dữ liệu này vẫn còn là một bài toán khó cho những người làm khoa học. Trên thực tế, đã có khá nhiều hệ thống thực hiện công việc này theo những phương pháp khác nhau, tuy chưa đạt được hiệu quả tối ưu nhưng cũng phần nào đáp ứng được các yêu cầu thông tin cho người sử dụng. Mỗi phương pháp khác nhau đều thể hiện được những điểm mạnh riêng của nó và việc lựa chọn phương pháp nào phụ thuộc vào những mục đích, yêu cầu và tiêu chí riêng đặt ra. Để khai thác có hiệu quả nguồn thông tin từ các cơ sở dữ liệu khổng lồ trên, yêu cầu đặt ra là cần phải có những phương pháp tổ chức, khai thác dữ liệu nhanh, tự động và chính xác để chuyển đổi kho dữ liệu khổng lồ này thành những tri thức có ích, có ứng dụng thực tiễn cao. Từ đó các kỹ thuật khai phá dữ liệu (Data Mining) và kỹ thuật khám phá, phát hiện tri thức (Knowledge Discovery) trở thành một lĩnh vực được đặc biệt quan tâm trong lĩnh vực công nghệ thông tin. Kỹ thuật khai phá tri thức và khai phá dữ liệu đã và đang được nghiên cứu, phát triển trong nhiều lĩnh vực khác nhau như y tế, giáo dục, kinh tế...Đây cũng là lĩnh vực liên quan đến nhiều ngành học như hệ cơ sở dữ liệu, trực quan hoá với nhiều cách tiếp cận, sử dụng các kỹ thuật khác nhau như mạng nơron, lý thuyết tập thô, biểu diễn tri thức...Nhằm mục đích tìm hiểu, nghiên cứu một phần nào đó của việc sử dụng kỹ thuật khai phá tri thức, khai phá dữ liệu trong thực tiễn. Tôi mạnh dạn chọn đề tài “Xây dựng tập thuộc tính rút gọn theo cách tiếp cận tập thô”, từ đó sử dụng một thuật toán để tìm tập rút gọn phục vụ bài toán: Tra cứu thông tin. 2. Mục tiêu của đề tài Mục tiêu của đề tài là nghiên cứu lý thuyết tập thô và tập rút gọn, từ đó áp dụng trong Bài toán: Tra cứu thông tin trên Web. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn XÂY DỰNG TẬP THUỘC TÍNH RÚT GỌN THEO CÁCH TIẾP CẬN TẬP THÔ 9 3. Đóng góp của đề tài Đề tài đã nghiên cứu tập thô ở khía cạnh lý thuyết áp dụng trực tiếp vào bài toán: Tra cứu thông tin, đề tài đã có các đóng góp cụ thể sau: - Nghiên cứu phương pháp tra cứu thông tin áp dụng lý thuyết tập thô. - Xây dựng tập dữ liệu phục vụ cho thử nghiệm. - Xây dựng được hệ thống tra cứu thông tin trên web áp dụng lý thuyết tập thô. 4. Bố cục của luận văn Luận văn được bố cục thành 4 chương chi tiết như sau: - Chương 1: Tổng quan về khai phá dữ liệu và lý thuyết tập thô. - Chương 2: Trình bày một số phương pháp xây dựng tập thuộc tính rút gọn. - Chương 3: Phương pháp xây dựng hệ thống tra cứu thông tin áp dụng lý thuyết tập thô - Chương 4: Xây dựng hệ thống và thử nghiệm. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn XÂY DỰNG TẬP THUỘC TÍNH RÚT GỌN THEO CÁCH TIẾP CẬN TẬP THÔ 10 CHƢƠNG 1: TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU VÀ LÝ THUYẾT TẬP THÔ 1. 1 Khai phá dữ liệu 1.1.1 Khai phá tri thức Trước sự phát triển không ngừng của công nghệ thông tin và đặt biệt là internet vào nhiều lĩnh vực của đời sống xã hội, khoa học kỹ thuật và kinh tế dẫn đến những kho dữ liệu đã lưu trữ một lượng dữ liệu khổng lồ. Trong lượng dữ liệu khổng lồ đó ẩn chứa giá trị nhất định. Tuy nhiên, trước đây người ta vẫn thường sử dụng những phương pháp thủ công mà rất khó khăn để khai phá chúng, chọn lọc ra những thông tin hữu ích. Cùng với sự phát triển của kỹ thuật máy tính và kỹ thuật thông tin, thông tin ngày càng được phát triển mạnh mẽ, đã vượt qua mọi khả năng phân tích thủ công của con người, cho dù hệ thống kho dữ liệu có thể nâng cao khả năng tìm kiếm, thống kê… nhưng không thể phát hiện được những mối quan hệ và những quy luật nằm bên trong dữ liệu, đồng thời cũng không thể căn cứ vào những phương pháp phân tích truyền thống được nữa. Trong một biển dữ liệu khổng lồ, làm thế nào để lấy được những thông tin có giá trị, có tri thức, đã trở thành một nhiệm vụ vô cùng quan trọng, con người mong muốn loại bỏ những dữ liệu thô để chắt lọc những dữ liệu tinh. Kỹ thuật phát hiện tri thức và khai phá dữ liệu bắt nguồn từ đây. Khai phá tri thức trong các cơ sở dữ liệu (KDD-Knowledge Data Development) là quá trình phát hiện những tri thức tiềm ẩn, không biết trước, và có ích trong cơ sở dữ liệu. Đây là quá trình tự động rút trích, tìm kiếm các “tri thức” bị che giấu trong một tập hợp “dữ liệu” rất lớn thông qua các mẫu, mô hình trong khối dữ liệu. Quá trình khai phá tri thức thường được áp dụng để giải quyết một loạt các yêu cầu nhằm phục vụ những mục đích nhất định và mang tính chất hướng nhiệm vụ, không phải là phát hiện mọi tri thức mà phát hiện những tri thức phục vụ tốt một nhiệm vụ đề ra. Vì vậy, quá trình phát hiện tri thức là một hoạt động tương tác giữa một người sử dụng hoặc một chuyên gia phân tích với các công cụ tin học. Các ngôn ngữ thường dùng để biểu diễn tri thức trong quá trình phát hiện tri thức từ các cơ sở dữ liệu là các khung, các cây và đồ thị, các luật, các công thức logic mệnh Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn XÂY DỰNG TẬP THUỘC TÍNH RÚT GỌN THEO CÁCH TIẾP CẬN TẬP THÔ 11 đề…Tri thức được rút ra có thể được dùng cho các mục đích cung cấp các hiểu biết sâu sắc và hữu ích về hành vi của các đối tượng (giải thích dữ liệu) hay dự đoán giá trị của những đối tượng mới (dự báo). Phương pháp này thường giúp con người tạo ra các quyết định hoặc giải quyết hiện tượng quan sát được. Tri thức ở đây có thể được hiểu là một biểu thức trong một ngôn ngữ nào đó diễn tả một hoặc nhiều mối quan hệ giữa các thuộc tính trong các dữ liệu đó, hay tri thức chính là các thông tin tích hợp, bao gồm các sự kiện và các mối quan hệ giữa chúng. Vậy tri thức được xem như là dữ liệu ở mức trừu tượng hoá và tổng quát hoá cao, còn dữ liệu là thông tin về một nhóm đối tượng nào đó, thông thường nó được coi như là một dãy các bit, hoặc các số, các ký hiệu mang một ý nghĩa nào đó khi được gửi cho một chương trình dưới một dạng nhất định. Quá trình khai phá tri thức nhằm mục đích rút ra được tri thức mới sau một số bước từ những cơ sở dữ liệu trong thực tế. Tiến trình của nó bao gồm các bước chính như sau: Hình 1.1: Mô hình mô tả quá trình khai phá tri thức Bước 1: Xác định và định nghĩa vấn đề: - Tìm hiểu lĩnh vực ứng dụng và nhiệm vụ đề ra, xác định các tri thức đã có và các mục tiêu của người sử dụng. - Tạo và chọn lựa cơ sở dữ liệu. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn XÂY DỰNG TẬP THUỘC TÍNH RÚT GỌN THEO CÁCH TIẾP CẬN TẬP THÔ 12 Bước này quyết định cho việc chọn lọc, rút trích được các tri thức hữu ích và cần thiết từ cơ sở dữ liệu và cho phép chọn các phương pháp khai phá dữ liệu thích hợp với mục đích ứng dụng và bản chất của dữ liệu. Bước 2: Thu thập và tiền xử lý dữ liệu - Xử lý và làm sạch dữ liệu trước: Bỏ đi các dữ liệu tạp (nhiễu) bao gồm các dữ liệu không cần thiết, các lỗi và các dạng không bình thường. Xử lý việc thiếu hay mất mát dữ liệu, chuyển đổi dữ liệu phù hợp. - Rút gọn kích thước dữ liệu nhận được: Nhận ra các thuộc tính hữu ích cho quá trình phát hiện tri thức. Bước này thường chiếm nhiều thời gian nhất trong toàn bộ qui trình phát hiện tri thức. Bước 3: Khai phá dữ liệu: - Chọn nhiệm vụ khai phá dữ liệu. - Lựa chọn các phương pháp khai phá dữ liệu. - Khai phá dữ liệu để rút ra các mẫu, các mô hình. 1.1.2 Khai phá dữ liệu Khai phá dữ liệu (DM-Data Mining) là một khái niệm ra đời vào cuối những năm 80 của thế kỷ 20, từ những năm 90 nó bắt đầu khởi phát, cho tới thế kỷ 21, rất nhiều các khái niệm gần đúng với nó ví dụ KDD (Knowledge Data Development), phân tích dữ liệu, data fusion, data warehouse… Trong lúc này, một lĩnh vực nằm trong ngành trí tuệ nhân tạo là học máy đang không ngừng phát triển. Học máy làm nâng cao tính năng của những chương trình máy tính, thu nhận được từ nhiều ngành khoa học khác nhau bao gồm: trí tuệ nhân tạo, xác suất thống kê, tâm lý học, triết học…rồi căn cứ vào những mô hình học khác nhau để đưa ra phương pháp học, ví dụ: học không giám sát, học có giám sát, mạng neural và di truyền… Tóm lại, Data Mining là việc tiến hành xử lý, khai phá từ trong kho dữ liệu lớn, không hoàn chỉnh, nhiều nhiễu, mơ hồ, để trích rút ra những thông tin có giá trị, có tri thức. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn XÂY DỰNG TẬP THUỘC TÍNH RÚT GỌN THEO CÁCH TIẾP CẬN TẬP THÔ 13 Khai phá dữ liệu là quá trình tìm kiếm, khám phá dưới nhiều góc độ khác nhau nhằm phát hiện các mối liên hệ, quan hệ giữa các dữ kiện, đối tượng bên trong cơ sở dữ liệu, kết quả của việc khai phá là xác định các mẫu hay các mô hình tồn tại bên trong nhưng chúng nằm ẩn ở các cơ sở dữ liệu. Về bản chất, nó là giai đoạn duy nhất rút trích và tìm ra được các mẫu, các mô hình hay thông tin mới, tri thức tiềm ẩn có trong cơ sở dữ liệu chủ yếu phục vụ cho mô tả và dự đoán. Đây là giai đoạn quan trọng nhất trong quá trình phát hiện ra tri thức từ cơ sở dữ liệu, các tri thức này hỗ trợ trong việc ra quyết định, điều hành trong khoa học và kinh doanh, nó là quá trình rất khó khăn, gặp phải nhiều vướng mắc như: quản lý các tệp dữ liệu, phải lặp đi lặp lại toàn bộ quá trình. 1.1.2.1 Một số khía cạnh khai phá chủ yếu * Phân tích kết hợp (Association Analysic) Khai phá luật kết hợp do Rakesh Apwal và cộng sự cùng đưa ra. Giá trị giữa 2 biến hoặc từ hai biến trở lên tồn tại một tính quy luật được gọi là kết hợp. Luật kết hợp dữ liệu là một vấn đề khá quan trọng trong kho dữ liệu, để nhằm phát hiện ra tri thức. Phân tích kết hợp được phân thành kết hợp đơn giản, kết hợp time-series và kết hợp nhân quả. Mục đích của phân tích kết hợp là tìm ra mạng kết hợp tiềm ẩn trong kho dữ liệu. * Phân lớp (Clustering) Phân lớp là căn cứ vào tính chất của dữ liệu để phân thành từng lớp khác nhau. Trong một lớp dữ liệu có nhiều đặc tính tương thích, phân lớp là căn cứ vào các đặc trưng khái quát của dữ liệu để phân chúng thành từng lớp khác nhau, ví dụ như căn cứ vào mô hình phân bố của dữ liệu, quan hệ giữa các thuộc tính của dữ liệu. * Phân loại (Classification) Phân loại là tìm ra khái niệm miêu tả của một lớp nào đó, nó đại diện cho chỉnh thể tin tức của dữ liệu, rồi dựa vào hàm miêu tả, đồng thời dùng hàm mô tả này để miêu tả mô hình dữ liệu. Thông thường, dùng mô hình cây quyết định để biểu thị. Phân loại là lợi dụng việc huấn luyện tập dữ liệu thông qua một số các thuật toán nhất định để đạt được quy tắc phân loại. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn XÂY DỰNG TẬP THUỘC TÍNH RÚT GỌN THEO CÁCH TIẾP CẬN TẬP THÔ 14 * Dự đoán (Predication) Dự đoán là lợi dụng lịch sử của dữ liệu để tìm ra được quy luật biến hóa, xây dựng mô hình, đồng thời từ mô hình đó để áp dụng vào loại dữ liệu trong tương lai để tiến hành khẳng định. Khẳng định quan tâm tới độ tinh và tính chuẩn xác, thông thường dùng phương sai của khẳng định để đo lường. * Mô hình chuỗi thời gian (Time-Series) Time-series chỉ sự thông qua sự tuần tự của thời gian tìm kiếm những mô hình phát sinh. Tựa như hồi quy, nó cũng dùng để nhận biết giá trị tương lai của dữ liệu. * Độ lệch (Deviation) Trong độ lệch bao gồm rất nhiều tri thức, trong kho dữ liệu, dữ liệu tồn tại những khác biệt, phát hiện những khác biệt trong kho dữ liệu là rất quan trọng. Độ lệch giữa kết quả quan sát được, giữa giá trị trả về theo tính toán và kết quả thực tế. 1.1.2.2 Một số kỹ thuật Khai phá dữ liệu Các kỹ thuật của DM bao gồm học máy, trí tuệ nhân tạo và thống kê học. Trí tuệ nhân tạo được áp dụng trong học máy thông qua các giải pháp của trí tuệ nhân tạo để nâng cao hiệu quả học, giải quyết những vấn đề khoa học và kỹ thuật còn tồn tại. Dưới đây là một số phương thức mà khai phá dữ liệu thường dùng: * Mạng neural nhân tạo (Artificial Neural Networks) Mạng neural là một trong những kỹ thuật được ứng dụng rất phổ biến hiện nay, nó là cách tiếp cận tính toán mới liên quan đến việc phát triển các cấu trúc toán học dựa trên nền tảng toán học vững vàng. Các phương pháp là kết quả của việc nghiên cứu mô hình của hệ thống thần kinh con người. Mạng neural có thể đưa ra ý nghĩa từ các dữ liệu phức tạp hoặc không chính xác và có thể sử dụng để truy xuất các mẫu và phát hiện ra các xu hướng quá phức tạp mà con người cũng như các kỹ thuật máy tính khác không thể phát hiện được. Mạng neural mô tả kết cấu của bộ não người. Cơ sở của nó là mô hình MP và phương pháp học Hebb. Nó có 3 mô hình mạng thần kinh chính: (1). Mạng lan truyền tiến (mô hình học không giám sát). Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn XÂY DỰNG TẬP THUỘC TÍNH RÚT GỌN THEO CÁCH TIẾP CẬN TẬP THÔ 15 (2). Mạng lan truyền ngược (giống mô hình mạng Hopfield). (3). Mạng tự tổ chức như mô hình ART, Koholon (thường dùng trong trường hợp phân cụm, phân lớp…) Tư tưởng của phương pháp này được bắt đầu bằng việc cho một tập dữ liệu, gọi là tập dữ liệu huấn luyện, mạng sẽ tự động điều chỉnh (học) qua từng lớp trong mạng và cho ra kết quả, quá trình huấn luyện được lặp đi lặp lại nhiều lần. Sau khi mạng học thành công thì nó được xem như là một chuyên gia trong lĩnh vực thông tin. Mạng neural là khả năng tạo ra các mô hình dự đoán có độ chính xác cao, có thể phát hiện ra các xu hướng phức tạp mà các kỹ thuật thông thường khác khó có thể phát hiện ra được. Vì vậy, phương pháp này được ứng dụng rộng rãi và áp dụng cho rất nhiều các loại bài toán khác nhau, đáp ứng được các nhiệm vụ đặt ra của khai phá dữ liệu như phân lớp, phân nhóm, mô hình hoá, dự báo các sự kiện phụ thuộc vào thời gian… Tuy nhiên kỹ thuật này cũng có một số mặt hạn chế như: Vấn đề huấn luyện của mạng cần mất nhiều thời gian, nhiều dữ liệu, nhiều lần thử nghiệm và công phu, mà trong môi trường cạnh tranh và hội nhập thì ngoài yếu tố chính xác còn phải nhanh, kịp thời thì mới có hiệu quả, bên cạnh đó việc chọn và xây dựng các hàm tính toán cho mạng phù hợp với yêu cầu bài toán là vấn đề không hề đơn giản, việc chọn và xây dựng mô hình cho mạng, việc lựa chọn thời điểm để kết thúc việc huấn luyện của mạng cũng gặp phải những vấn đề khó khăn. * Phƣơng pháp di truyền (Genetic Algorithms) Giải thuật di truyền là áp dụng quá trình tiến hóa của sinh vật, do yếu tố cấu thành: (1). Lựa chọn (Selection): Lựa chọn cá thể trong một quần thể để lai ghép. (2). Lai ghép (Crossover): Là quá trình lựa chọn 2 cá thể độc lập để lai ghép. (3). Biến dị (Mutation): Là quá trình biến dị trên từng cá thể (ví dụ 0 biến 1, 1 biến 0…) để tạo ra một cá thể mới. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn XÂY DỰNG TẬP THUỘC TÍNH RÚT GỌN THEO CÁCH TIẾP CẬN TẬP THÔ 16 Giải thuật di truyền thường dùng để sản sinh ra cá thể tốt hơn ở đời sau nhằm thỏa mãn một giá trị nào đó, thông qua quá trình di truyền, lai ghép, biến dị. Giải thuật này thường dùng trong tính toán và phân loại học máy. * Tập mờ (Fuzzy Set) Lý thuyết tập mờ là một phương pháp tiện lợi trong việc xử lý và biểu diễn các dạng dữ liệu không xác định. Tập mờ không chỉ sử dụng trong việc biểu diễn và xử lý các dạng dữ liệu không toàn vẹn, không xác định mà còn sử dụng rất tốt trong việc xử lý và phát triển các dạng cấu trúc mô hình dữ liệu không xác định, nó có tính năng linh hoạt hơn nhiều so với những phương pháp truyền thống. * Hệ thống miễn dịch nhân tạo(Artificial Immune System) Hệ thống miễn dịch nhân tạo mô phỏng hệ thống miễn dịch sinh vật. Trong nó bao gồm mạng neural, thuật giải di truyền, hệ thống tổ kiến,…Nó được coi như một mô hình tiến hóa cấp cao, có khả năng kháng trừ các tác nhân khác và bảo trì sự ổn định. Các khái niệm liên quan tới AIS:miễn dịch (Immunity), kháng thể (Antibody), kháng nguyên (Antigen), Self and Non-Self, tế bào miễn dịch, tế bào B, tế bào T… * Cây quyết định (Decision Trees) Cây quyết định là một mô tả tri thức dạng đơn giản nhằm phân đối tượng dữ liệu thành một số lớp nhất định, hoặc các giá trị của các đối tượng dữ liệu chưa được biết sẽ được dự đoán, dự báo, là phương pháp dùng trong bài toán phân đoạn dữ liệu theo một tiêu chuẩn nào đó dựa trên mức độ khác nhau của thuộc tính. Trong khai phá dữ liệu, kỹ thuật này là một công cụ mạnh và hiệu quả trong việc phân lớp và dự báo. Tri thức được rút ra trong kỹ thuật này thường được mô tả dưới dạng tường minh, đơn giản, trực quan dễ hiểu đối với người sử dụng. Tuy nhiên, nó đòi hỏi một không gian nhất định, để mô tả tri thức trong một phạm vi mà con người có thể hiểu được. Cây quyết định là sử dụng những thông tin lập luận để tìm kiếm những đặc trưng trong lượng thông tin lớn để tạo thành các điểm. Trên thực tế, người ta thường sử dụng và ảnh hưởng nhiều nhất bởi cây quyết định do Qiulan nghiên cứu và phương pháp ID3. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn XÂY DỰNG TẬP THUỘC TÍNH RÚT GỌN THEO CÁCH TIẾP CẬN TẬP THÔ 17 Các nút của cây được gắn nhãn là tên các thuộc tính, các lá miêu tả các lớp khác nhau. Các đối tượng được phân theo lớp các đường đi trên cây, qua các cạnh tương ứng với giá trị thuộc tính của đối tượng lá. Hình 1.2: Mô tả cây quyết định Trong hình 1.2 là cây quyết định cho việc chơi bóng đá của một số câu lạc bộ, cho biết các câu lạc bộ sẽ thi đấu hay không thi đấu. Mỗi nút lá đại diện một lớp mà việc đánh giá trận đấu bóng sẽ diễn ra hay không (có hay không). Sau khi mô hình này được xây dựng chúng ta có thể dự đoán việc có thể diễn ra trận đấu hay không dựa vào những thuộc tính như thời tiết bên ngoài trời, độ ẩm, gió. Cây quyết định có thể ứng dụng rộng rãi trong nhiều lĩnh vực và hoạt động của đời sống con người. * Tạo luật Các luật được tạo ra nhằm suy diễn một số mẫu dữ liệu có ý nghĩa về mặt thống kê. Các luật có dạng Nếu P thì Q , với P là mệnh đề đúng với một phần dữ liệu trong cơ sở dữ liệu, Q là mệnh đề dự đoán. * Tập thô (Rough Set) Thông qua những tri thức đã hiểu để tiến hành phân hoạch, mỗi một phân hoạch là một tập được gọi là khái niệm, tư tưởng chủ yếu là lợi dụng kho tri thức đã biết, để áp dụng vào trong một kho tri thức chưa toàn vẹn, chưa xác định để tiến hành phân hoạch và xử lý. Lý thuyết tập thô lần đầu tiên được đề xuất bởi Z.Pawiak và nhanh chóng được xem như là công cụ xử lý các thông tin mơ hồ và không chắc chắn. Phương Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn XÂY DỰNG TẬP THUỘC TÍNH RÚT GỌN THEO CÁCH TIẾP CẬN TẬP THÔ 18 pháp này đóng vai trò hết sức quan trọng trong trí tuệ nhân tạo và các ngành khoa học khác liên quan đến nhận thức, đặc biệt là lĩnh vực máy học, thu nhận tri thức, phân tích quyết định, phát hiện và khám phá tri thức từ cơ sở dữ liệu, các hệ chuyên gia, hệ hỗ trợ quyết định, lập luận dựa trên quy nạp và nhận dạng. Lý thuyết tập thô dựa trên giả thiết rằng để định nghĩa một tập hợp chúng ta cần phải có thông tin về mọi đối tượng trong tập vũ trụ. Ví dụ, nếu các đối tượng là các bệnh nhân bị một bệnh nhất định thì các triệu chứng của bệnh tạo thành thông tin của bệnh nhân. Như vậy, tập thô có quan điểm hoàn toàn khác với quan điểm truyền thống của tập hợp, trong đó mọi tập hợp đều được định nghĩa duy nhất bởi các phần tử của nó mà không cần biết bất kỳ thông tin nào của các phần tử thuộc tập hợp. Rõ ràng có thể tồn tại một số đối tượng giống nhau ở một số thông tin nào đó, và ta nói rằng chúng có quan hệ không phân biệt được. Đây chính là quan hệ mấu chốt và chính là điểm xuất phát của lý thuyết tập thô: biên giới của tập thô là không rõ ràng, chúng ta phải xấp xỉ nó bằng các tập hợp khác, nhằm mục đích cuối cùng là trả lời được rằng một đối tượng nào đó thuộc tập hợp hay không. Lý thuyết tập thô với cách tiếp cận như vậy đã được ứng dụng rất rộng rãi. 1.2 Lý thuyết tập thô 1.2.1 Giới thiệu về tập thô Khai phá tri thức là phương pháp giúp con người trích dẫn tri thức từ lượng lớn dữ liệu, phương pháp này thường giúp con người tạo ra quyết định hoặc giải thích các hiện tượng quan sát được. Phương pháp khai phá tri thức và công cụ khai phá dữ liệu đang ngày càng được quan tâm và sử dụng rộng rãi trong nhiều lĩnh vực. Phương pháp khai phá tri thức thường được bắt đầu bằng việc lấy mẫu, chọn lọc thuộc tính và trừu tượng hóa, biến đổi và rút gọn kích thước, trích dẫn dữ liệu, mô hình hóa hiện tượng vật lý, thường sử dụng các thuật toán từ những giả thiết về dữ liệu cho trước. Có rất nhiều kỹ thuật khai phá dữ liệu, mỗi kỹ thuật có những đặc điểm riêng phù hợp với một lớp các bài toán, với các dạng dữ liệu và miền dữ liệu nhất định. Một trong số những kỹ thuật đó là khai phá tri thức theo cách tiếp cận tập thô. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn XÂY DỰNG TẬP THUỘC TÍNH RÚT GỌN THEO CÁCH TIẾP CẬN TẬP THÔ 19 Định nghĩa tập thô: Cho cơ sở tri thức K= (U, ), X  U, R là một quan hệ tương đương trên U. - X là có thể xác định trên R (R–definable): Nếu X là hợp của một số các phạm trù sơ cấp trên R, được gọi là tập xác định, ngược lại X được gọi là tập thô (tập không xác định trên R–Undefinable). - Tập X  U được gọi là xác định trong cơ sở tri thức K nếu tồn tại một quan hệ tương đương R  IND(K) sao cho X là tập xác định trên R. - X  U được gọi là tập thô trong K nếu X là tập thô trên với mọi R  IND(K). * Lý thuyết tập Thô: Lý thuyết tập thô được đề xuất và giới thiệu bởi giáo sư Zdzislaw PawLak vào những năm 80 của thế kỷ XX và nhanh chóng được xem như là công cụ xử lý các thông tin mơ hồ và không chắc chắn, nó là một trong những phương pháp đang được nhiều nhà khoa học nghiên cứu và sử dụng trong quá trình khai phá tri thức từ dữ liệu. Phương pháp này đóng vai trò hết sức quan trọng trong trí tuệ nhân tạo và các ngành khoa học khác liên quan đến nhận thức, đặc biệt là lĩnh vực máy học, thu nhận tri thức, phân tích quyết định, phát hiện và khám phá tri thức từ cơ sở dữ liệu, các hệ chuyên gia, hệ hỗ trợ quyết định, lập luận dựa trên quy nạp và nhận dạng. Hệ thống thông tin được đưa ra bởi PawLak đại diện cho tri thức và quan hệ của dữ liệu. Lý thuyết tập thô được sử dụng trong nhiều giai đoạn khác nhau của tiến trình xử lý thông tin như: - Tổ chức bảng quyết định đại diện cho hệ thống thông tin. - Tính toán xấp xỉ trên và xấp xỉ dưới của tập hợp. - Phân tích tri thức. - Tính toán mức độ quan trọng của một thuộc tính. - Tìm thuật toán quyết định từ tập luật sinh. - Xác định và ước lượng sự phụ thuộc của tập thuộc tính. - Tính định tập tối thiểu các thuộc tính từ rút gọn. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn