Tài liệu Khai phá dữ liệu luật kết hợp mờ và ứng dụng cho bài toán khai phá dữ liệu cước internet

ĐẠI HỌC QUỐC GIA HÀ NỘI T RƯ Ờ NG Đ Ạ• I HỌ • C CÔNG NGHỆ • Pham Thi • H oa Nam • KHAI PHÁ DỮ LIỆU LUẬT KẾT HỢP MỜ VÀ ỨNG DỤNG CHO BÀI TOÁN KHAI PHÁ D ử LIỆU CƯỚC INTERNET Ngành : Công nghệ thông tin Ma số: 1.01.10 LUẬN VĂN THẠC s ĩ NGƯỜI HƯỚNG DÃN KHOA HỌC: PGS.TS. NGUYỄN THANH THUY Hà Nội - 2007 MỤC LỤC LỜI CẢM Ơ N ....................................................................................................................................3 MỞ ĐẦU ....................................................... ..........................................................7 Chương 1. TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU........................................................7 1.1 Khái niệm cơ bản......................................................................................................... 7 1.1.1 Mục tiêu của khai phá dữ liệu.............................................................................. 7 1.1.2 Định nghĩa khai phá dữ liệu..................................................................................8 1.1.3 Các dạng dữ liệu có thể khai phá dữ liệu.[l][3]................................................. 8 1.1.4 Quá trình khai phá dữ liệu....................................................................................9 1.1.4.1 Các bước chính trong quá trình khai phá......................................................9 1.1.4.2 Các thành phần của giải thuật khai p h á........................................................9 1.1.4.3 Hướng tiếp cận cơ bàn và kỹ thuật áp dụng trong quá trình khai phá.... 10 1.1.4.4 ứng dụng của khai phá dữ liệu................................................................... 11 1.2 Phương pháp khai phá dữ liệu...................................................................................12 1.2.1 Một số phương pháp khai phá dữ liệu phổ biến. [1][3]....................................12 1.2.1.1 Cây quyết định và luật................................................................................. 12 1.2.1.2 Phương pháp suy diễn và quy nạp...............................................................12 1.2.1.3 Phát hiện các luật kết hợ p............................................................................13 1.2.1.4 Phân nhóm và phân đoạn.............................................................................14 1.2.1.5 M ạngnơron.................................................................................................. 15 1.2.1.6 Giải thuật di truyền.......................................................................................16 1.2.2 Phân loại các hệ thống khai phá dữ liệu.............................................................16 1.2.3 Những vấn đề quan tâm trong hệ thống khai phá dữ liệu và lựa chọn các kỹ thuật khai phá.................................................................................................................... 17 Chương 2. KHAI PHÁ DỮ LIỆU BẢNG LUẬT KẾT HỢP............................................20 2.1 Ý nghĩa của ỉuật kết hợp[5].......................................................................................20 2.2 Phát biểu bài toán [1][5]............................................................................................ 21 2.3 Một số khái niệm cơ bản và các pha thực hiện.[3][4][5]........................................ 22 2.4 Một số tính chất của tập mục phổ biến và luật kết hợ p.......................................... 24 2.4.1 Một số tính chật của tập mục phổ biến.............................................................24 2.4.2 Một số tính chất của luật kết hợ p..................................................................... 25 2.4.3 Cácloại luật kết họp. [5][6][8].......................................................................... 26 2.5 Các thuật toán khai phá dữ liệu nhờ luật kết hợp....................................................27 2.5.1 Khai phá luật kết hợp nhị phân đơn chiều tò cơ sở dữ liệu tác v ụ ................... 27 2.5.1.1 Thuật toán Apriori tìm tập mục phổ biến sử dụng phương pháp sinh các ứng cử [5] 27 2.5.1.2 Nâng cao hiệu quả thuật toán Apriori [7][8][9]...... .................................. 33 2.5.1.3 Thuật toán sinh các luật kết hợp tò tập mục phổ biến............................... 35 2.5.1.4 Khai phá tập mục phổ biến không sinh ứng cử [3 ]....................................38 2.5.2 Khai phá luật ket hợp định lượng. [6].................................................................44 2.5.3 Khai phá luật kết hợp đa mức [6]....................................................................... 45 2.5.3.1 Luật kết họp đa m ức..................... .............................................................. 45 2.5.3.2 Các cách tiep cận khai phá luật kết hợp đa m ức........................................ 45 2.5.4 Khai phá luật kết hợp đóng.................................................................................46 2.5.4.1 Tập mục phổ biến đóng............................................................................... 47 2.5.4.2 Sinh luật!...................................................................................................... 50 1 2.5.4.3 Thuật toán CHARM [8].............................................................................51 Chương 3. KHAI PHÁ DỮ LIỆU BANG LUẬT KÉT HỢP M Ờ ..........................54 3.1 Khái niệm về tập mờ (Fuzzy Sets), logic mờ và hệ mờ.........................................54 3.1.1 Tập mờ [2],.................... . ........................... ...................................................54 3.1.2 Các phép toán cơ bản trên tập mờ [2]...............................................................56 3.1.2.1 Phép phủ định............................................................................................ 56 3.1.2.2 Phép hội ...’................................................................................................. 56 3.1.2.3 Phép tuyển..................................................................................................57 3.1.2.4 Luật De Morgan........................................................................................57 3.1.2.5 Phép kéo theo............................................................................................ 57 3.1.3 Áp dụng tập mờ để rời rạc hóa dữ liệu và các ưu điểm.................................. 58 3.2 Các luật kết hợp mờ [3] [11].................. ................................................................ 59 3.3 Các thuật toán khai phá luật kết hợp mờ................................................................. 63 3.4 Luật kết hợp mờ ở dạng phủ định............................................................................68 3.5 Luật kết hợp mờ với thuộc tính được đánh trọng số[5][6][11]..............................68 3.6 Tìm các luật thật sự có ích [3].................................................................................69 3.6.1 Phương pháp dùng quy luật loại bỏ luật thừa.................................................. 69 3.6.2 Phương pháp tìm luật đơn giản........................................................................70 3.6.3 Phương pháp tìm luật mới lạ dựa trên tri thức đã biết....................................70 3.6.4 Chuyển iuật kết hợp mờ về luật kết hợp thuộc tính s ố ...................................72 Chương 4. ỨNG DỤNG LUẬT KẾT HỢP MỜ CHO BÀI TOÁN KHAI PHÁ DỮ LIỆU CƯỚC INTERNET....... ................. ........................................................................... 74 4.1 Nguồn dữ liệu cuớc Internet....................................................................................74 4.2 Cài đặt hệ thống khai phá dữ liệu cước Internet..................................................... 75 4.2.1 Các bước tiến hành xây dựng hệ thống khai phá dữ liệu cước Internet........75 4.2.2 Giao diện hệ thống khai phá dữ liệu cước Internet......................................... 80 4.2.2.1 Hệ thống hàm chuẩn..................................................................................80 4.2.2.2 Mờ hoá dữ liệu và sinh luật kết hợp m ờ ................................................... 81 4.2.2.3 Tìm luật có ích........................................................................................... 87 KẾT LUẬN................... ....................................................................................................... 89 2 LỜI CẢM ƠN Đầu tiên tôi xin gửi lời cảm ơn sâu sắc nhất đến thầy giáo, cán bộ hướng dẫn khoa học PGS.TS Nguyễn Thanh Thủy, người đã truyền cho tôi cảm hứng về đề tài, về phương pháp nghiên cứu khoa học, đã giảng dạy, chỉ bảo hướng dẫn tận tình trong suốt thòi gian qua. Tôi xin bầy tỏ lòng biết ơn sâu sắc đến tất cả các thầy cô giáo ở Trường Đại học Công nghệ, Viện công nghệ thông tin đã giảng dạy, truyền đạt cho tôi các kiến thức trong suốt 3 năm qua. Cuối cùng tôi xin chân thành cảm ơn các bạn học viên lớp K10T3, các đồng nghiệp, gia đình đã giúp đỡ, động viên tôi trong suốt thời gian qua. Hà nội, ngày 23 tháng 10 năm 2007 Học viên I Pham Thi• Hoa Nam • 3 DANH MỤC CÁC HÌNH VẼ, ĐÒ THỊ Ví dụ cây FP-tree với minsup=20%............................................................. Mô hình vận hành hệ thống (theo quy trình đấu nối và khai thác dịch vụ) Mô hình tổng quan hệ thống khai phá dữ liệu:............................................ Mô hình cơ sở dữ liệu quan hệ....................................................................... Loại hàm thuộc............................................................................................... Hàm thuộc và tham sổ cho mỗi hàm thuộc.................................................. Tập mờ và thuộc tính gốc của n ó .................................................................. Giao diện thực hiện Mờ hoá dữ liệu và cơ sở dữ liệu cước gốc............... Cơ sở dữ liệu sau khi thực hiện mờ hoá....................................................... Sinh tập phổ biến sử dụng toán tử T-norm - Tích đại sổ ............................ Sinh tập phổ biến sử dụng toán tử T-norm - Phép lấy min........................ Sinh tập phổ biến sử dụng toán tử T-norm - Tích bị chặn.......................... Sinh tập phổ biến sử dụng toán tử T-norm - Tích Drastic.......................... Sinh tập phổ biến sử dụng toán tử T-norm - Phép giao.............................. Sinh tập các luật mờ từ tập phổ biến............................................................. Diễn giải luật................................................................................................... Sinh tập luật bằng luật phủ đ ịn h ................................................................... 40 74 77 79 80 80 81 81 82 82 83 83 84 .84 85 .85 Sinh luật kết hợp với các thuộc tính được đánh trọng số.......................... 86 86 Tìm luạt mới lạ dựa trên tri thức đã biết....................................................... Tìm luật đom giản........................................................................................... Loại bỏ luật thừ a............................................................................................. 87 .87 88 4 M Ở ĐẦU Trong những năm gần đây, một trong những vấn đề chính được các nhà khoa học quan tâm nghiên cứu là khai phá dữ liệu mà nội dung chủ yếu là phát hiện thông tin có tính trí tuệ trong kho tàng dữ liệu, bởi tính ứng dụng cao trong thực tiễn cuộc sống. Khai phá dữ liệu thường đi đôi với phát hiện tri thức. Trong sự phát triển mạnh mẽ của công nghệ máy tính điện tử, nhất là việc ứng dụng phổ biến trong lĩnh vực quản lý, lĩnh vực hoạt động cần có nhiều thông tin và tri thức. Trong sự phát triển của xã hội mà yếu tố khoa học công nghệ có tính quyết định nhu cầu như vậy trở nên ngày càng to lớn và dẫn đến việc tràn ngập các thông tin và những nhà quản lý đứng trước tĩnh trạng phải đối mặt với việc lụt “thông tin”. Ví dụ Hệ thống vệ tinh cùa NASA trung bình mỗi giờ phải tạo ra 50 Gb dữ liệu ảnh, thị trường giao dịch chứng khoán thực hiện khoảng 20 triệu giao dịch dữ liệu mỗi ngày,... Chính vì vậy các nhà khoa học cho rằng chúng ta đang sổng trong xã hội giàu thông tin nhưng nghèo tri thức. Vì thế đòi hỏi phải nghiên cứu phát triển các phương pháp khai phá, phát hiện ra những thông tin, tri thức hữu ích bị che giấu trong đống “dữ liệu” để phục vụ các công việc của nhà quản lý, các chuyên gia, chuyên viên. M ục tiêu của bài toán khai phá dữ liệu là tìm ra thông tin, tri thức (những mối quan hệ hay sự phụ thuộc giữa các đại lượng (các biến) trong kho tàng dữ liệu (về một lĩnh vực nào đó). Chúng ta dễ dàng nhận thấy, mỗi con người dù là người nước nào đều tư duy bằng ngôn ngữ và như vậy tri thức trong đầu mỗi người đều được biểu thị qua ngôn ngữ. Vì ngôn ngữ hàm chứa các thông tin mờ cho nên việc ứng dụng phương pháp luận mờ ừong việc biểu diễn, xử lý, xây dựng các hệ tri thức là tự nhiên và như vậy mới thực sự đi vào giải quyết vấn đề một cách bản chất. Chính vì vậy các mô hình mờ (fuzzy) được sừ dụng để mô phỏng, phản ánh, giải quyết các bài toán liên quan đến khía cạnh định tính của tri thức. 5 Luật kết hợp mờ là một trong những phương pháp khai phá dữ liệu có hiệu quả và có tính ứng dụng cao Hướng nghiên cứu “Khai phá dữ liệu bằng luật kết hợp mờ” được xây dựng và tổng hợp các nội dung dựa trên một số nghiên cứu chủ yếu trong lĩnh vực khai phá dữ liệu bằng luật kết họp mờ trong những năm gần đây ở một số hội nghị quốc tế, một số bài báo được công bố trên các tạp chí chuyên ngành, trên Internet. Nội dung luận văn gồm các chương sau: Chương 1: Tổng quan về khai phá dữ liệu Chương này trình bày khái quát về khai phá dữ liệu, các phương pháp khai phá, các lĩnh vực ứng dụng Chương 2: Khai phá dữ liệu bằng luật kết họp Chương này trình bày các phương pháp khai phá dữ liệu bằng luật kết hợp từ thuật toán cơ bản đến các thuật toán cải tiến. Đồng thời cũng trình bày một số vấn đề cơ bản của luật kết họp đa mức, định lượng, đóng. Chương 3: Khai phá dữ liệu bằng luật kết hợp mờ Chương này trình bày khái niệm về tập mờ, các phép toán cơ bản trên tập mờ, các luật kết hợp mờ, cách tìm kiếm các luật thực sự có ích. Chương 4: ứ n g dụng luật kết hợp mờ cho bài toán khai phá dữ liệu cước Internet Trong chương này trình bày bài toán, xác định nhiệm vụ khai phá dữ liệu, phân tích và thiết kế các môđul, giao diện chương trình. Chương trình được xây dựng với mục đích thử nghiệm để đánh giá kết quả. 6 C h ư ơ n g 1. TỔNG QUAN VÈ KHAI PHÁ D Ữ LIỆU 1.1 Khái niêm cơ bản 1.1.1 Mục tiêu của khai phá dữ liệu Trong những thập niên gần đây, lượng thông tin được lun trữ trên các thiết bị không ngừng tăng lên. Sự tích lũy dữ liệu này xảy ra với một tốc độ bùng nổ. Người ta dự đoán rằng, lượng thông tin trên toàn cầu tăng khoảng gấp đôi sau hai năm đồng thời số lượng cũng như kích cỡ của cơ sở dữ liệu cũng tăng lên nhanh chóng. Trong lĩnh vực kinh doanh, những nhà quản lý đang ngập trong dữ liệu nhưng việc tìm ra tri thức và thông tin hữu ích thì lại rất khó. Lượng dữ liệu khổng lồ này thực sự đã trở thành nguồn tài nguyên rất giá trị bởi thông tin là yểu tố then chốt trong mọi hoạt động thương mại vì thông tin ừ ợ giúp người điều hành và nhà quản lý có cái nhìn sâu sắc, chính xác, khách quan trước khi ra quyết định. Việc khai thác những thông tin tiềm ẩn mang tính dự đoán từ những cơ sở dữ liệu lớn là mục tiêu chính của khai phá dữ liệu - một hướng tiếp cận mới với khả năng giúp các đơn vị, tổ chức chú trọng vào những thông tin có giá trị, ý nghĩa từ những tập bợp dữ liệu lớn mang tính lịch sử. Những công cụ khai phá dữ liệu có thể dự đoán những xu hướng tương lai do đó cho phép các tổ chức, doanh nghiệp ra những quyết định kịp thời được định hướng bởi tri thức mà khai phá dữ liệu đem lại. Sự phân tích dữ liệu một cách tự động và mang tính dự báo của khai phá dữ liệu khiến nó có ưu thế hơn hẳn so với sự phân tích thông thường dựa trên những sự kiện trong quá khứ của các hệ hỗ trợ ra quyết định truyền thống trước đây. Công cụ khai phá dữ liệu cũng có thể trả lời câu hỏi trong lĩnh vực kinh doanh mà trước đây được xem là tốn nhiều thời gian để xử lý. Với tất cả các ưu thế trên, khai phá dữ liệu đã chứng tỏ được tính hữu dụng của nó trong môi trường kinh doanh, quản lý phức tạp ngày nay. Giờ đây khai phá dữ liệu đã và đang trở thành một trong những hướng nghiên cứu chính của lĩnh vực khoa học máy tính và công nghệ tri thức. Phạm vi ứng dụng ban đầu của khai phá dữ liệu chỉ là trong lĩnh vực thương mại và tài chính. Nhưng ngày nay, khai phá dữ 7 liệu đã được ứng dụng rộng rãi trong các lĩnh vực khác như: sinh học, y học, viễn thông, giáo dục, ngân hàng,... 1.1.2 Định nghĩa khai phá dữ liệu Có thể hiểu sơ lược rằng khai phá dữ liệu là quá trình tìm kiếm thông tin hữu ích, tiềm ẩn và mang tính dự báo trong các cơ sở dữ liệu lớn. Như vậy, quá trình này còn có thể được gọi là khám phá tri thức. Nhiều nhà khoa học đồng ý với nhau rằng hai thuật ngữ khám phá tri thức và khám phá dữ liệu là tương đương với nhau và có thể thay thế cho nhau. Vì họ lý giải rằng mục đích chính của quá trình khám phá tri thức là thông tin có ích, nhưng đối tượng mà chúng ta xừ lý rất nhiều trong quả trình đó lại chính là dữ liệu. Mặt khác, khi chia các bước trong quá trình khám phá tri thức, nhiều nhà khoa học khác cho rằng khám phá dữ liệu chỉ là một bước trong quá trình khám phá tri thức. 1.1.3 Các dạng dữ liệu có thể khai phá dữ Iiệu.[l][3] Có nhiều dạng dữ liệu khác nhau có thể áp dụng được các phương pháp khai phá dữ liệu. Sau đây liệt kê một số loại cơ sở dữ liệu phổ biến: Cơ sở dữ liệu quan hệ (relational database): là các cơ sở dữ liệu tác nghiệp được tổ chức theo mô hình dữ liệu quan hệ. Hầu hết các hệ quản trị cơ sở dữ liệu đều hỗ trợ dạng cơ sở dữ liệu này như: Oracle, IBM DB2, MS SQL Server, MS Access,... Cơ sở dữ liệu đa chiều (multimension structures, data warehouses, data mart): là kho dữ liệu được tập hợp, chọn lọc từ nhiều nguồn dữ liệu khác nhau. Dạng dữ liệu này mang tính lịch sử (tức là có tình thời gian) và chủ yếu phục vụ cho quá trình phân tích cũng như khai phá tri thức nhằm hỗ trợ cho việc ra quyết định. Cơ sở dữ liệu dạng giao dịch (transactional databases): là dạng cơ sở dữ liệu tác nghiệp nhưng các bản ghi thường là các giao dịch. Dạng dữ liệu này thường phổ biến trong lĩnh vực thương mại và ngân hàng. Cơ sở dữ liệu quan hệ - hướng đổi tượng (object-relational databases’): là dạng cơ sở dữ liệu lai giữa hai mô hình quan hệ và hướng đối tượng. 8 C ơ s ở d ữ liệu không gian vù thời gian (spatial, tem poral a n d tim e-series data): là dạng dữ liệu có tích hợp thuộc tính về không gian (ví dụ như dữ liệu về bản đồ) hoặc thời gian (ví dụ như dữ liệu về thị trường chứng khoán). Cơ sở dữ liệu đa phương tiện (multimedia databases): là dạng dữ liệu âm thanh (audio), hình ảnh (image), phim ảnh (video), Text và W W W ,...Dạng dữ liệu này hiện đang rất phổ biến trên Internet. 1.1.4 Quá trình khai phá dữ liệu 1.1.4.1 Các bước chính trong quá trình khai phá Quá trình khai phá dữ liệu thực hiện các bước chính sau: Xác đinh nhiệm vụ: Xác định chính xác các vấn đề cần giải quyết. Xác định các dữ liệu liên quan : dùng để xây dựng giải pháp giải quyết nhiệm vụ bài toán. Thu nhập các dữ liệu có liên quan với nhau và xừ lý chúng thành dạng nào đỏ sao cho giải thuật khai phá dữ liệu có thể hiểu được. Chọn thuật toán khai phá dữ liệu thích hợp và thực hiện việc khai phá nhằm tìm được các mẫu có ý nghĩa dưới dạng biểu diễn tương ứng với các ý nghĩa đó. 1.1.4.2 Các thành phần của giải thuật khai phá Quá trình khai phá dữ liệu là quá trình phát triển mẫu trong đó giải thuật khai phá dữ liệu tìm kiếm mẫu đáng quan tâm theo dạng xác định các luật, cây phân lớp, hồi quy, phân nhóm ,.. .Giải thuật khai phá dữ liệu gồm 3 thành phần chính: Biểu diễn mô hình. Mô hình được biểu diễn bằng một ngôn ngữ sao cho có thể khai phá được. Nấu mô hình có sự mô tả hạn chế thì sẽ không thể học được hoặc sẽ không thể có các mẫu tạo ra. Nếu diễn tả mô hình càng lớn thì càng làm tăng mức độ nguy hiểm do bị học quá nhiều và làm giảm đi khả năng dự đoán các dữ liệu chưa biết. Hơn nữa, việc tìm kiếm sẽ càng trờ nên phức tạp hơn và việc giải thích mô hình cũng khó khăn hơn. 9 Đánh giá mô hình: Đánh giá xem một mẫu có đáp ứng được các tiêu chuẩn của quá trình phát hiện ừi thức hay không. Việc đánh giá mô hình được thực hiện thông qua kiểm fra dữ liệu, đổi với nhiệm vụ dự đoán thì việc đánh giá mô hình ngoài kiểm tra dữ liệu còn dựa trên độ chính xác dự đoán mà việc đánh giá độ chính xác dự đoán dựa trên đánh giá chéo. Tìm kiểm mô hình'. Bao gồm 2 thành phần: tìm kiếm tham số và tìm kiểm mô hình. Tìm kiếm tham số: Giải thuật cần tìm các tham số để tối ưu hóa các tiêu chuẩn đánh giá mô hình với các dữ liệu quan sát được và với một miêu tả mô hình đã định. Tìm kiếm mô hình: Quá trình này xảy ra giống như một vòng lặp qua phương pháp tìm kiếm tham số. Khi miêu tả, mô hình bị thay đổi tạo nên một họ các mô hình thì với mỗi một miêu tả mô hình phương pháp tìm kiếm tham số được áp dụng để đánh giá chất lượng mô hình. Các phương pháp tìm kiếm mô hình thường sử dụng các kỹ thuật tìm kiếm kinh nghiệm bởi kích thước của không gian các mô hĩnh có thể ngăn cản các tìm kiếm tổng thể. 1.1.4.3 Hướng tiếp cận cơ bản và kỹ thuật áp dụng trong quá trình khai phá Vấn đề khai phá dữ liệu có thể được phân chia theo lớp các hướng tiếp cận chính sau: Phân lớp và dự đoản (classification & prediction): xếp một đối tượng vào một trong những lớp đã biết. Ví dụ: phân lớp vùng địa lý theo dữ liệu thời tiết. Đối với hướng tiếp cận này thường áp dụng một số kỹ thuật như học máy (machine learning), cây quyết định (decision tree), mạng nơron (nơron network),.,..Hay lớp bài toán này còn được gọi là học có giám sát (supervised learning). Phân cụm (clustering/segmentation): sắp xếp các đối tượng theo từng cụm nhưng số lượng và tên các cụm chưa biết trước. Lớp bài toán phân cụm còn được gọi là học không giám sát (unsupervised learning) 10 Luật kết hợp (association rules)-, là dạng luật biểu diễn tri thức ở dạng khá đơn giản. Ví dụ: “80% sinh viên đăng ký học Cơ sở dữ liệu thì có tới 70% trong số họ đăng ký học Phân tích thiết kế hệ thống thông tin”. Hướng tiếp cận này được ứng dụng nhiều trong lĩnh vực kinh doanh, y học, tin sinh học, giáo dục,... Khám phá chuỗi theo thời gian (sequential / temporal patterns): Cũng tương tự như khai phá dữ liệu bằng luật kết hợp nhưng có thêm tính thứ tự và tính thời gian. Hướng tiếp cận này được ứng dụng nhiều trong lĩnh vực tài chính và thị trường chứng khoán bởi chúng có tính dự đoán cao. Mô tả khái niệm (concept description & summarization)', lớp bài toán này thiên về mô tả, tổng hợp và tóm tắt khái niệm. Ví dụ: tóm tắt văn bản. 1.1.4.4 ứ n g dụng của khai phá dữ liệu Khai phá dữ liệu là một lĩnh vực mới phát triển nhưng thu hút được nhiều nhà nghiên cứu nhờ vào những ứng dụng thực tiễn của nó. Sau đây là một số lĩnh vực ứng dụng điển hình: Phân tích dữ liệu và hỗ írợ ra quyết định Sinh học: tìm kiếm, đối sánh các hệ gen và thông tin di truyền, mối liên hệ giữa một số gene và một số bệnh di truyền,... Tài chính và thị trường chứng khoán: Phân tích tình hình tài chính và dự báo giá của các cổ phiếu. Bảo hiểm, Giáo dục Điều trị trong y học: Mối liên hệ giữa triệu chứng, chuẩn đoán và phương pháp điều trị. Phân lớp văn bản, tóm tắt văn bản và phân lớp các trang Web. 11 1.2 Phương pháp khai phá d ữ liệu 1.2.1 Một số phương pháp khai phá dữ liệu phổ biến. [1][3] 1.2.1.1 Cây quyết định và luật Cây quyết định'. Cây quyết định là một phương pháp mô tả tri thức dạng đơn giản nhằm phân các đổi tượng dữ liệu thành một số lớp nhất định. Các nút của cây được gán nhãn là tên các thuộc tính, các cạnh được gán các giá ứị có thể của 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 lóp theo các đường đi trên cây, qua các cạnh tương ứng với giá trị của các thuộc tính của đối tượng tới Tạo luật: Các luật được tạo ra nhằm suy diễn cho một số mẫu dữ liệu có ý nghĩa về mật thổng kê. Các iuật có dạng nếu p thì Q, trong đó p là mệnh đề đúng với một phần dữ liệu trong cơ sở dữ liệu và Q là mệnh đề dự đoán. Cây quyết định là phương pháp dùng trong các bài toá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. Cây quyết định và luật có ưu điểm là hình thức miêu tả đom giản, mô hình suy diễn khá dễ hiểu đối với người sử dụng. Tuy nhiên, giói hạn của nó là miêu tả cây và luật chỉ có thể biểu diễn được một số dạng chức năng và vì vậy giới hạn cả về độ chính xác của mô hình. 1.2.1.2 Phương pháp suy diễn và quy nạp Phương pháp suy diễn: Rút ra thông tin là kết quả logic từ các thông tin nằm trong cơ sở dữ liệu dựa trên các quan hệ trong dữ liệu. Phương pháp suy diễn dựa trên các sự kiện chính xác để suy ra các tri thức mới từ các thông tin cũ. Mầu chiết suất được bằng cách sử dụng phương pháp này thường là các luật suy diễn. Phương pháp quy nạp: Các thông tin được suy ra tò cơ sở dữ liệu bằng cách nó tự tìm kiếm, tạo mẫu và sinh ra tri thức chứ không bắt đầu với các tri thức đã biết trước. 12 1.2.1.3 Phát hiện các luật kết họp Các luật kết họrp là một dạng biểu diễn tri thức, hay chính xác là dạng mẫu của hình thành tri thức. Phương pháp này nhằm phát hiện ra các luật kết hợp giữa các thành phần dữ liệu trong cơ sờ dữ liệu. Một đầu ra của giải thuật khai phá dữ liệu là tập các luật kết hợp tìm được. Cho một lược đồ R = {A!,A2,...,Ap} với các thuộc tính có miền giá trị {0,1} và một quan hệ r trên R. Ta gọi một luật kết hợp trên quan hệ r được mô tả như sau: X => B với X c R v à B 6 R\x. Cho W c R , đặt s(W,r) là tần sổ xuất hiện của w trong r được tính bằng tỉ lệ của các hàng trong r có giá trị 1 tại mỗi cột. Khi đó ta định nghĩa tần số xuất hiện và độ tin cậy của luật X => B trong r như sau: Tần số xuất hiện ơ = s(X u {B},r) Độ tin cậy 0 =s(X u {B},r) \ s(X,r) Với X gồm nhiều thuộc tính và B là giá trị không cố định. Nhiệm vụ của việc phát hiện các luật kết hợp là phải tìm tất cả các luật X => B sao cho tần số xuất hiện của luật không nhỏ hơn ngưỡng ơ cho trước và độ tin cậy của luật không nhỏ hơn ngưỡng 0 cho trước. Khi thiết kế dữ liệu dùng cho kỹ thuật kết hợp cần lưu ý để giảm thiểu số lượng các thuộc tính đầu vào bởi không gian tìm kiếm các luật sẽ tăng theo hàm mũ của số lượng các thuộc tính đầu vào. Giải thuật tìm các luật kết hợp được bắt đầu bằng việc tìm tất cả các tập thường xuyên xuất hiện. Tập thường xuyên xuất hiện lớn hơn ngưỡng tần số được xác định trước. Các luật kết hợp sẽ được tạo ra bằng cách ghép dần các tập thuộc tính dựa trên mức độ thường xuyên. Ví dụ: Phân tích cơ sở dữ liệu bán hàng nhận được thông tin về những khách mua các mặt hàng máy tính có khuynh hướng mua phần mềm kế toán trong cùng lần mua được mô tả bởi luật kết họp như sau: 13 “Neu mua máy tính thì mua phần mềm kế toán ” [Độ hỗ trợ: 30%, Độ tin cậy: 65%] Phương pháp này có ưu thể cơ bản là đơn giản và dễ hiểu đối với con người. Ở ví dụ trên độ hỗ trợ 30% có nghĩa là: 30% của tất cả các giao dịch được phân tích thì chi ra rằng máy tính và phần mềm kế toán được mua cùng nhau. Còn độ tin cậy 65% có nghĩa là: 65% các khách hàng mua máy tính thì cũng mua phần mềm. Đặc biệt, các luật kết hợp được coi là đáng quan tâm nếu chúng thoả mãn cả hai ngưỡng độ hỗ trợ cực tiểu và độ tin cậy cực tiểu. Những ngưỡng này thường do người dùng hoặc các chuyên gia trong lĩnh vực xác định. Nhược điểm cơ bản của phương pháp này là việc tăng nhanh chóng khối lượng tính toán và các thông số. Tuy nhiên với sự phát triển nhanh chóng và mạnh mẽ của phần cứng thì vấn đề này cũng được khắc phục. 1.2.1.4 Phân nhóm và phân đoạn Kỹ thuật phân nhóm và phân đoạn là những kỹ thuật phân chia dữ liệu sao cho mỗi phần hoặc mỗi nhóm giống nhau theo một tiêu chuẩn nào đó. Mối quan hệ thành viên của các nhóm có thể dựa trên mức độ giống nhau của các thành viên và từ đó xây dựng nên các luật ràng buộc giữa các thành viên trong nhóm. Một kỹ thuật phân nhóm khác là xây dựng nên các hàm đánh giá các thuộc tính của các thành phần như là hàm của các tham số của các thành phần. Kỹ thuật này được gọi là kỹ thuật phân hoạch tối ưu. Ví dụ: một trong những ứng dụng của kỹ thuật phân nhóm theo độ giống nhau là cơ sở dữ liệu khách hàng để phân nhóm khách hàng theo các tham số và các nhóm thuế có được khi thiết lập biểu thuế bảo hiểm. Mau đầu ra của quá trình khai phá dữ liệu sừ dụng kỹ thuật này là các tập mẫu chứa dữ liệu có chung những tính chất nào đó được phân tách từ cơ sở dữ liệu. Khi các mẫu được thiết lập, chúng có thể được sử dụng để tái tạo các tập dữ liệu dễ hiểu 14 hơn, đồng thời cũng cung cấp các nhóm dữ liệu cho các hoạt động cũng như công việc phân tích. Đối với cơ sở dữ liệu lớn, việc lấy ra các nhóm này là rất quan trọng. 1.2.1.5 Mạng nơron Mạng nơron là một phương pháp khai phá dữ liệu phát triển trên cấu trúc toán học với khả năng học trên mô hình hệ thần kinh con người. Mạng nơron 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ể được sừ dụng để chiết suất các mẫu và phát hiện 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ột trong những ưu điểm phải kể đến các mạng nơron là khả năng tạo ra các mô hình dự đoán do có độ chính xác cao, có thể áp dụng được cho nhiều các bài toán khác nhau đáp ứng 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,... Mau chiết suất bằng mạng nơron được thể hiện ở các nút đầu của mạng. Mạng nơron sử dụng các hàm số chứ không sử dụng các hàm biểu tượng để tính mức tích cực của các nút đầu ra và cập nhật các trọng số của nó. Đặc điểm của mạng nơron là không cần gia công dữ liệu nhiều trước khi bắt đầu quá trình học như các kỹ thuật khác. Tuy nhiên để có thể sử dụng mạng nơron có hiệu quả cần phải xác định các yếu tố khi thiết kế mạng như: Kiến trúc mạng là gì? Hàm học cần thực hiện? Mạng cần bao nhiêu nút? Khi nào thì việc học dừng? Ngoài ra còn có rất nhiều bước quan trọng cần phải làm để tiền xử lý dữ liệu trước khi đưa vào mạng nơron để mạng có thể hiểu được. 15 Mạng nơron được đóng gói với những thông tin trợ giúp của các chuyên gia đáng tin cậy và được họ bảo đảm các mô hình này làm việc tốt. Sau khi học, mạng có thể được coi là một chuyên gia trong lĩnh vực thông tin mà nó vừa được học. 1.2.1.6 Giải thuật di truyền Đây là phương pháp không chỉ phục vụ phát hiện tri thức mà còn phục vụ rất nhiều bài toán khác. Ví dụ bài toán tối ưu hoá hoặc lập lịch. Tư tường của thuật toán là áp dụng quy luật của sự chọn lọc tự nhiên. Người ta mô phỏng tập họp dữ liệu ban đầu bằng ký tự nhị phân và gọi là những quần thể khởi tạo. Bằng các thao tác lai ghép, đột biến chúng ta biến đổi quần thể gene trong quần thể là không thay đổi. Một hàm thích nghi được xây dựng để xác định mức độ thích nghi của quần thể theo các giai đoạn. Quá trình tiến hoá làm cho các quần thể thích nghi ngày càng cao. v ề mặt lý thuyết giải thuật di truyền cho ta lời giải tối ưu toàn cục (Khác với phương pháp mạng nơron). Tuy nhiên, người ta cũng hạn chế lời giải với một mức độ thích nghi nào đó đề hạn chế số lượng các bước xây dựng quần thể. Nói theo nghĩa rộng thì giải thuật di truyền mô phỏng lại hệ thống tiến hoá trong tự nhiên, chính xác hơn là các giải thuật chỉ ra tập các cá thể được hình thành, được ước lượng và biến đổi như thế nào. Ví dụ như xác định xem làm thế nào để lựa chọn các cá thể tạo giống và lựa chọn các cá thể nào để loại bỏ. Giải thuật di truyền là một giải thuật tối ưu hoá, nó được sử dụng rất rộng rãi trong việc tối ưu hoá các kỹ thuật khai phá dữ liệu trong đó có kỹ thuật mạng nơron. Sự liên hệ của nó với các giải thuật khai phá dữ liệu là ở chỗ tối ưu hoá là cần thiết để xác định các giá trị tham số nào tạo ra các luật tốt nhất. 1.2.2 Phân loại các hệ thống khai phá dữ liệu Phân loại khai thác dữ liệu dựa trên các tiêu chí khác nhau Phân loại dựa trên kiểu dữ liệu được khai thác: Cơ sở dữ liệu quan hệ, kho dữ liệu, cơ sở dữ liệu giao tác, cơ sở dữ liệu hướng đối tượng, cơ sở dữ liệu không gian, cơ sở dữ liệu đa phương tiện, cơ sở dữ liệu văn bản,... 16 Phân loại dựa trên dạng tri thức được khám phá: tóm tắt và mô tả, luật kết hợp, phân lớp, phân cụm, khai phá chuỗi,... Phân loại dựa trên lĩnh vực được áp dụng: Thương mại, viễn thông, tài chính, y học, web,... Phân loại dựa trên kỹ thuật được áp dụng: Phân tích trực tuyến (Online Analytial Processing - OLAP), học máy (cây quyết định, mạng nơron nhân tạo, K-Means, giải thích di truyền, máy vector hỗ trợ - SVM, tập thô, tập mờ,...). Thông thường sử dụng tập mờ là thích hợp cho việc tìm ra và hiểu được sự liên quan của các mô hình dữ liệu chưa đầy đủ, tạp nhiễu, thông tin hỗn tạp và tác động của con người, và tò đó có thể cung cấp giải pháp xấp xỉ nhanh hơn. Mạng nơron có khả năng tổng quát, không giới hạn, mạnh và học tốt trong môi trường dữ liệu giàu (data - rich), thuật toán di truyền cung cấp khả năng tìm các thuật toán để chọn mẫu từ các dữ liệu hỗn tạp dựa trên một số hàm tiêu chuẩn/ mục tiêu thường dùng. Tập thô thì phù hợp cho tìm ra các mẫu khác nhau của tình trạng không rõ ràng trong dữ liệu. Một số yêu cầu khai thác dữ liệu cần phải áp dụng phương pháp tính toán mềm (Tính toán mềm là sự kết hợp của các phương pháp logic mờ, thuật toán di truyền) 1.2.3 Những vấn đề quan tâm trong hệ thống khai phá dữ liệu và lựa chọn các kỹ thuật khai phả Một số hướng nghiên cứu của khai thác dữ liệu hiện nay: OLAM (Online Analytical Mining): Là sự tích hợp giữa cơ sở dữ liệu, kho dữ liệu, và khai thác dữ liệu. Một số hệ cơ sở dữ liệu như Oracle. MS SQL Server đã tích hợp tính năng xây dựng kho dữ liệu và phân tích trực tuyến (OLAP). Những tính năng này được hỗ trợ dưới dạng các công cụ đi kèm và người sử dụng phải mua nếu cần sừ dụng. Các nhà nghiên cứu trong lĩnh vực cơ sở dữ liệu còn muốn có thêm sự tích hợp giữa cơ sở dữ liệu, kho dữ liệu, và khai thác dữ liệu. Khám phá được nhiều tri thức khác nhau từ các kiểu dữ liệu khác nhau. Tính chính xác và hiệu quả, khả năng mở rộng và tích hcrp, xử lý dữ liệu bị nhiễu không đầy đủ và tính có ích của tri thức được khám phá. vấn đề song song hóa và phân tán quá trình khai Đ A I H O C Q U O C GI.A HA NÕI 17 thác dữ liệu. Vấn đề ngôn ngữ truy vấn trong Khai thác dữ liệu phải cung cấp cho người sử dụng một ngôn ngữ thuận tiện, gần gũi tương tự như SQL trong Cơ sờ dữ liệu quan hệ. Biểu diễn các tri thức khai thác được sao cho trực quan và gần gũi với người sử dụng để người sử dụng tri thức có hiệu quả hơn. Hiện nay người ta vẫn chưa đưa ra được một tiêu chuẩn nào trong việc quyết định sử dụng phương pháp nào vào trong trường hợp nào thì hiệu quả. Hầu hết các kỹ thuật khai phá dữ liệu đều là mới trong các lĩnh vực. Hơn nữa lại có rất nhiều kỹ thuật được sử dụng cho nhiều bài toán khác nhau. Vì vậy câu hỏi dùng kỹ thuật nào để khai phá không phải là đơn giản. M ỗi phương pháp đều có những điểm mạnh và điểm yếu riêng của nó, nhưng đa số các điểm yếu đều có thể khắc phục được. Vậy phải làm thế nào để áp dụng kỹ thuật một cách đơn giản nhất, dễ sử dụng, để không cảm thấy sự phức tạp vốn có của kỹ thuật đó và vấn đề là tất cả các mẫu tìm được đều đáng quan tâm? Đây chính là vấn đề quan trọng đối với một hệ thống khai phá dữ liệu. Hệ thống khai phá có thể sinh ra hàng nghìn mà thậm chí có thể hàng triệu mẫu hoặc luật, do vậy với câu hỏi trên thì câu trả lời là: Chỉ có một phần nhỏ trong các mẫu hay các luật là đảng quan tâm và hữu ích với người sử dụng. Có một vài câu hỏi thường đặt ra đối vófi một hệ thống khai phá dữ liệu là: Cái gì tạo ra các m ẫu quan tâm? Hệ thống khai phá có thể sinh ra được tất cả các mẫu quan tâm không? Hệ thống khai phá có thể chỉ sinh các mẫu quan tâm không? Để trả lời các câu hỏi này ta nên quan tâm đến sự gợi ý sau: Đổi với câu hỏi 1: M au đáng quan tâm nếu: Dễ hiểu đối với con người, hợp lệ hoặc dữ liệu được kiểm tra với độ chắc chắn nào đó, có khả năng có ích, mới lạ. M au cũng là đáng quan tâm nếu nó là giả thiết hợp lệ được người dùng xác nhận. Mầu quan tâm luôn chứa đựng tri thức. 18 Có vài độ đo cho các mẫu quan tâm. Nó dựa trên cấu trúc của mẫu đã khai phá và thống kê chúng. Chẳng hạn độ đo của luật kết hợp dạng X —> Y là độ hỗ trợ và độ tin cậy của luật. Cụ thể người ta định nghĩa là xác suất P(X u Y) và xác suất P(X/Y). N hìn chung các độ đo này được người dùng điều khiển. Đổi với câu hỏi thứ 2: Có thể tạo ra được tất cả các mẫu đáng quan tâm không? Vấn đề này liên quan đến tính hoàn thiện của thuật toán khai phá. Nó thường không thực hiện được và không có khả năng đối với các hệ thống khai phá dữ liệu để sinh ra tất các các mẫu có thể có, có thể tồn tại. Thay cho điều đó người ta tập trung vào mục tiêu tìm kiếm. Ví dụ với Khai phá bằng luật kết hợp, người ta sử dụng các độ đo có thể đảm bảo khai phá trọn vẹn, có nghĩa là xác định trước ngưỡng độ hỗ trợ và độ tin cậy nhỏ nhất thì có thể tìm được. Đối với câu hỏi thứ 3: Hệ thống khai phá có thể chỉ sinh ra các mẫu cần quan tâm không? Đây chính là vấn đề tối ưu trong khai phá dữ liệu, v ấ n đề này là thách thức rất lớn đối với các nhà khoa học trong lĩnh vực khai phá dữ liệu. 19