Tài liệu Ứng dụng lý thuyết giàn giao trong khai thác dữ liệu

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC CÔNG NGHỆ TP. HCM --------------- PHẠM VĂN KHANH ỨNG DỤNG LÝ THUYẾT GIÀN GIAO TRONG KHAI THÁC DỮ LIỆU LUẬN VĂN THẠC SỸ Chuyên ngành: Công nghệ Thông tin Mã số ngành: 60480201 TP. HỒ CHÍ MINH, tháng 09 năm 2014 BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC CÔNG NGHỆ TP. HCM --------------- PHẠM VĂN KHANH ỨNG DỤNG LÝ THUYẾT GIÀN GIAO TRONG KHAI THÁC DỮ LIỆU LUẬN VĂN THẠC SỸ Chuyên ngành: Công nghệ Thông tin Mã số ngành: 60480201 CÁN BỘ HƯỚNG DẪN KHOA HỌC: PGS TSKH NGUYỄN XUÂN HUY TP. HỒ CHÍ MINH, tháng 09 năm 2014 i LỜI CAM ĐOAN Tôi xin cam đoan đây là công trình nghiên cứu của riêng tôi. Các số liệu, kết quả nêu trong Luận văn là trung thực và chưa từng được ai công bố trong bất kỳ công trình nào khác. Tôi xin cam đoan rằng mọi sự giúp đỡ cho việc thực hiện Luận văn này đã được cảm ơn và các thông tin trích dẫn trong Luận văn đã được chỉ rõ nguồn gốc. Học viên thực hiện Luận văn Phạm Văn Khanh ii LỜI CẢM ƠN Trong suốt quá trình học tập và hoàn thành luận văn này, tôi đã nhận được sự hướng dẫn, giúp đỡ quý báu của quý thầy cô, gia đình, bạn bè và đồng nghiệp. Với lòng kính trọng và biết ơn sâu sắc tôi xin được bày tỏ lời cảm ơn chân thành tới: Khoa Công Nghệ Thông Tin, Phòng quản lý khoa học - Đào tạo sau đại học trường Đại Học Công Nghệ Thành Phố Hồ Chí Minh đã tạo mọi điều kiện thuận lợi giúp đỡ tôi trong quá trình học tập và hoàn thành luận văn này. Thầy hướng dẫn Phó giáo sư - Tiến sĩ Khoa học Nguyễn Xuân Huy, thầy đã truyền đạt những kiến thức rất bổ ích cho tôi trong quá trình học tập, đã hết lòng tạo điều kiện cũng như giúp đỡ tôi trong quá trình hoàn thành luận văn này. Phó giáo sư - Tiến sĩ Lê Hoài Bắc, thầy đã truyền đạt những kiến thức rất bổ ích cho tôi trong quá trình học tập, thầy đã hết lòng giúp đỡ và cung cấp cho tôi những tài liệu nghiên cứu cần thiết liên quan đến luận văn này. Thầy Cao Tùng Anh, thầy đã hết lòng giúp đỡ, chỉ bảo, động viên và tạo mọi điều kiện thuận lợi cho tôi trong suốt quá trình học tập và hoàn thành luận văn này. Toàn thể quý thầy cô đã nhiệt tình giảng dạy và truyền đạt những kiến thức bổ ích cho tôi trong suốt khóa học vừa qua. Cuối cùng xin cảm ơn đến tất cả những người thân trong gia đình, bạn bè và đồng nghiệp đã giúp đỡ tôi trong suối quá trình học tập và thực hiện luận văn này. Phạm Văn Khanh iii MỤC LỤC  MỞ ĐẦU ................................................................................................................ 1 Chương 1. TỔNG QUAN VỀ KHÁM PHÁ TRI THỨC VÀ KHAI THÁC DỮ LIỆU....................................................................................................................... 4 1.1. Khám phá tri thức và khai thác dữ liệu ............................................................ 4 1.2. Quá trình khám phá tri thức .......................................................................... 6 1.3. Quá trình khai thác dữ liệu ........................................................................... 8 1.4. Các phương pháp khai thác dữ liệu ............................................................... 9 1.5. Các lĩnh vực ứng dụng thực tiễn của khai thác dữ liệu ................................ 10 1.6. Các phương pháp, và kỹ thuật áp dụng trong khai thác dữ liệu ................... 11 1.7. Các thách thức – khó khăn trong khám phá tri thức và khai thác dữ liệu ..... 13 1.8. Khai thác tập phổ biến, luật kết hợp và tương quan .................................... 15 1.8.1. Bài toán kinh điển dẫn đến việc khai thác luật kết hợp ........................ 15 1.8.2. Tập phổ biến và luật kết hợp ............................................................... 18 1.8.3. Các phương pháp khai thác tập phổ biến ............................................. 19 1.9. Khai thác dữ liệu bảo đảm tính riêng tư ...................................................... 26 1.9.1. Bài toán khai thác dữ liệu bảo đảm tính riêng tư .................................. 26 1.9.2. Phân loại các phương pháp PPDM ...................................................... 27 1.9.3. Các phương pháp giấu dữ liệu nhạy cảm ............................................. 30 1.9.3.1. Làm xáo trộn (Perturbation) ........................................................ 30 1.9.3.2 Ngăn chặn (Blocking) .................................................................. 30 1.9.3.3 Gom hoặc trộn (Aggregation / Merging) ...................................... 30 1.9.3.4. Đổi chỗ (Swapping) .................................................................... 30 1.9.3.5. Lấy mẫu ....................................................................................... 32 Chương 2. ÁNH XẠ ĐÓNG VÀ GIÀN GIAO ÁNH XẠ ĐÓNG ...................... 37 2.1. Ánh xạ đóng ............................................................................................... 37 2.1.1. Các khái niệm và tính chất ánh xạ đóng .......................................... 37 iv 2.1.2. Phép hạn chế của ánh xạ đóng ......................................................... 39 2.2. Các phép toán hội và hợp thành trên ánh xạ đóng ...................................... 39 2.2.1. Phép toán hội .................................................................................. 40 2.2.2. Phép hợp thành các ánh xạ đóng ..................................................... 40 2.3. Giàn giao ánh xạ đóng ................................................................................ 45 2.3.1. Điểm bất động................................................................................. 45 2.3.2. Giàn giao ánh xạ đóng..................................................................... 45 Chương 3. ẨN CÁC TẬP MỤC NHẠY CẢM ................................................... 49 3.1. Giàn giao AXĐ và bài toán ẩn tập mục nhạy cảm ....................................... 49 3.2. Phát biểu bài toán ....................................................................................... 50 3.3. Giàn giao .................................................................................................... 52 3.4. Các tính chất của tập mục thường xuyên..................................................... 53 3.5. Thuật toán ẩn tập mục nhạy cảm ................................................................ 56 3.6. Ví dụ minh họa cho thuật toán .................................................................... 57 Chương 4. CHƯƠNG TRÌNH THỰC NGHIỆM .............................................. 61 4.1. Giới thiệu ................................................................................................... 61 4.2. Các chức năng chính của chương trình ....................................................... 62 KẾT LUẬT .......................................................................................................... 66 TÀI LIỆU THAM KHẢO ................................................................................... 68 v DANH MỤC CÁC KÝ HIỆU, CHỮ CÁI VIẾT TẮT  KPDL Khai thác dữ liệu KPTT Khám phá tri thức PPDM (Privacy Data Mining) Preserving Khai thác dữ liệu đảm bảo tính riêng tư AXĐ Ánh xạ đóng CSDL Cơ sở dữ liệu LĐQH Lược đồ quan hệ PTH Phụ thuộc hàm  Thuộc  Không thuộc  Là tập con  Chứa tập con \ Phép trừ tập hợp  Phép giao tập hợp  Phép hợp tập hợp  Tương đương  Khác  Với mọi LS(f) Tập các vế trái của luật sinh f RS(f) Tập các vế phải của luật sinh f  Tập rỗng vi DANH MỤC CÁC BẢNG  Bảng 1.1. Dấu dữ liệu bằng phương pháp đổi chỗ ............................................... 36 Bảng 3.1. Bảng trị T và các tập mục thường xuyên theo ngưỡng 4 ..................... 56 Bảng 3.2. Các tập mục thường xuyên theo ngưỡng 4 .......................................... 62 Bảng 3.3. Sửa giá trị của E trong các bộ chứa ADE ............................................ 64 Bảng 3.4. Sửa giá trị của E trong các bộ chứa ABE ............................................ 65 vii DANH MỤC CÁC HÌNH MINH HOẠ  Hình 1.1. Quá trình khám phá tri thức ................................................................ 12 Hình 1.2. Quá trình khai thác dữ liệu .................................................................. 14 Hình 2.1. Ví dụ thuật toán Apriori ...................................................................... 29 Hình 2.2. Ví dụ thuật toán Apriori ...................................................................... 30 Hình 3.1. Đồ thị của giàn các tập mục thường xuyên P ....................................... 58 Hình 3.2. Giàn giao đầy đủ của Poset(ABE) ...................................................... 59 Hình 4.1 Giao diện chính chương trình.............................................................. 63 Hình 4.2 Giao diện chương trình khi tính độ hỗ trợ của tất cả các tập mục ........ 64 Hình 4.3 Giao diện chương trình khi tìm tất cả tập mục thường xuyên .............. 65 Hình 4.4 Giao diện chương trình hiển thị các tập mục thường xuyên mới.......... 66 1 MỞ ĐẦU Ngày nay, dữ liệu chứa thông tin của người dùng được lưu trữ lại thông qua rất nhiều hoạt động hằng ngày như giao dịch, mua hàng, khám bệnh, tìm kiếm thông tin, truy cập web,… Các dữ liệu này đóng vai trò ngày càng quan trọng trong sự phát triển của xã hội như làm đầu vào cho quá trình phân tích tìm ra các thông tin hữu ích cho các hệ hỗ trợ ra quyết định, phát hiện dịch bệnh hay hoạch định kế hoạch kinh doanh,… Tuy nhiên, các thông tin hữu ích chỉ có thể được rút trích từ tập dữ liệu rất lớn trong quá trình thu thập dữ liệu lớn từ đầu rất khó khăn. Chính vì vậy, chia sẻ dữ liệu đóng vai trò rất quan trọng trong quá trình phát triển xã hội. Tuy nhiên, chia sẽ dữ liệu có thể vô tình làm tiết lộ thông tin nhạy cảm của người dùng gây nguy hại cho các cá nhân, tổ chức trong xã hội. Một vấn đề thường gặp là khi cung cấp dữ liệu cho các trung tâm khai thác tri thức, một số cơ sở, cá nhân không muốn công bố các luật vi phạm đến tính riêng tư của cá nhân hoặc doanh nghiệp. Thí dụ, nếu X là tập mục về thương hiệu xe máy Honda, Y là tập mục về số vụ tai nạn xe máy thì việc công bố tương quan giữa X và Y sẽ mang đến sự bất lợi cho việc kinh doanh xe máy Honda. Các tập mục X và Y như trên được gọi là các tập mục nhạy cảm. Một lẽ đương nhiên là cơ sở cung cấp dữ liệu sẽ phải loại bỏ hai tập mục nhạy cảm X và Y khỏi danh mục cần cung cấp. Tuy nhiên, việc làm này đôi khi lại vi phạm luật về cung cấp thông tin. Giải pháp thứ hai thường được các cơ sở lách luật chọn là vẫn công bố đầy đủ các tập mục nhưng tìm cách sửa tần suất xuất hiện của các tập mục nhạy cảm xuống dưới ngưỡng thường xuyên . Khi đó các tập mục nhạy cảm sẽ trở thành các tập mục không thường xuyên và do đó chúng không thể trở thành các thành phần trong bất kỳ luật nào. Giải pháp thứ hai này được gọi là ẩn các tập mục nhạy cảm (và thường xuyên). Vậy, hướng nghiên cứu của luận văn là cần thiết cho trường hợp cần bảo vệ bí mật và tính riêng tư của các tình huống hợp pháp, đồng thời có thể phát hiện giả mạo, lách luật trong các tình huống cần ngăn chặn. 2 Luận văn đề xuất một tiếp cận cho bài toán ẩn các tập mục nhạy cảm. Vận dụng lý thuyết giàn giao ta có thể xác định một cận trên đúng và một cận dưới đúng đối với một tập mục nhạy cảm cho trước. Hướng tiếp cận này có những điểm mới sau đây. Thứ nhất, chứng minh rằng họ các tập mục thường xuyên tạo thành một giàn giao. Thứ hai, nhờ vận dụng các tính chất của giàn giao đã chỉ ra rằng có thể vận dụng lý thuyết đồ thị để xác định các tập mục gây ảnh hưởng và các tập mục chịu ảnh hưởng trực tiếp khi sửa giao tác trên tập mục nhạy cảm cần ẩn do đó làm giảm thời gian truy xuất các giao tác và không gây ra các hiệu ứng phụ theo nghĩa là ẩn nhầm các tập mục khác. Bố cục luận văn Ngoài các phần Mở đầu, Mục lục, Danh mục các ký hiệu, chữ cái viết tắt, Danh mục bảng, Danh mục hình, Kết luận, Tài liệu tham khảo. Luận văn chia làm 4 chương. Chương 1: Tổng quan về khám phá tri thức và khai thác dữ liệu Chương này giới thiệu tổng quát về quá trình khám phá tri thức nói chung và khai thác dữ liệu nói riêng. Các phương pháp, lĩnh vực, các hướng tiếp cận trong khai thác dữ liệu. Giới thiệu các khái niệm về mẫu phổ biến, luật kết hợp và các mối tương quan, các phương pháp khai thác tập phổ biến. Chương 2: Sử dụng giàn giao trong ẩn các tập mục nhạy cảm Chương này trình bày một số khái niệm và tính chất cơ bản của ánh xạ đóng, vai trò của AXĐ trong việc ứng dụng giải quyết các bài toán về khai thác dữ liệu. Trình bày về lý thuyết giàn giao và ứng dụng lý thuyết giàn giao trong thuật toán ẩn các tập mục nhạy cảm. Chương 3: Ẩn các tập mục nhạy cảm Chương này mô tả chi tiết bài toán ẩn các tập mục nhạy cảm, đi sâu vào việc giải quyết bài toán. 3 Chương 4. Chương trình thực nghiệm Chương này đưa ra đề xuất phương pháp cài đặt thuật toán với ứng dụng là CSDL thực tế. So sánh kết quả đạt được với những công trình nghiên cứu liên quan, đưa ra hướng cải tiến của đề tài. 4 Chương 1 TỔNG QUAN VỀ KỸ THUẬT KHÁM PHÁ TRI THỨC VÀ KHAI THÁC DỮ LIỆU 1.1. Khám phá tri thức và khai thác dữ liệu Trong thời đại công nghệ thông tin như hiện nay, các công nghệ lưu trữ dữ liệu ngày càng phát triển tạo điều kiện cho các đơn vị thu thập dữ liệu ngày một thuận tiện. Với hàng triệu cơ sở dữ liệu đã được lưu trữ và sử dụng trong các hoạt động sản xuất, kinh doanh, quản lí..., trong số đó có nhiều cơ sở dữ liệu rất lớn cỡ Gigabyte, thậm chí là Terabyte. Sự bùng nổ này đã làm cho các phương pháp quản trị và khai thác cơ sở dữ liệu truyền thống ngày càng không đáp ứng được thực tế dẫn tới một yêu cầu cấp thiết là cần có những kỹ thuật và công cụ mới để tự động chuyển đổi lượng dữ liệu khổng lồ kia thành các tri thức có ích đó là kỹ thuật phát hiện tri thức và khai thác dữ liệu (KDD - Knowledge Discovery and Data mining). Thông thường, chúng ta coi dữ liệu như là một chuỗi các bits, hoặc các số và các ký hiệu hay là các “đối tượng” với 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. Các bits thường được sử dụng để đo thông tin, và xem nó như là dữ liệu đã được loại bỏ phần tử thừa, lặp lại, và rút gọn tới mức tối thiểu để đặc trưng một cách cơ bản cho dữ liệu. Tri thức được xem như là các thông tin tích hợp, bao gồm các sự kiện và mối quan hệ giữa chúng, đã được nhận thức, khám phá, hoặc nghiên cứu. Nói cách khác, tri thức có thể được coi là dữ liệu ở mức độ cao của sự trừu tượng và tổng quát. Khám phá tri thức là quá trình tìm ra những tri thức, đó là những mẫu tiềm ẩn, trước đó chưa biết và là thông tin hữu ích đáng tin cậy. Còn khai thác dữ liệu (KPDL) là một bước quan trọng trong quá trình khám phá tri thức, sử dụng các thuật toán KPDL chuyên dùng với một số qui định về hiệu quả tính toán chấp nhận được để chiết xuất ra các mẫu hoặc các mô hình có ích trong dữ liệu. Nói một cách khác, mục đích của khám phá tri thức và KPDL chính là tìm ra các mẫu hoặc mô 5 hình đang tồn tại trong các cơ sở dữ liệu (CSDL) nhưng vẫn còn bị che khuất bởi hàng núi dữ liệu. Khám phá tri thức từ CSDL là một quá trình sử dụng các phương pháp và công cụ tin học, trong đó con người là trung tâm của quá trình. Do đó, con người cần phải có kiến thức cơ bản về lĩnh vực cần khám phá để có thể chọn được tập con dữ liệu tốt, từ đó phát hiện các mẫu phù hợp với mục tiêu đề ra. Đó chính là tri thức, được rút ra từ CSDL, thường để phục vụ cho việc giải quyết một loạt nhiệm vụ nhất định trong một lĩnh vực nhất định. Tuy vậy, quá trình khám phá tri thức mang tính chất hướng nhiệm vụ vì không phải là mọi tri thức tìm được đều có thể áp dụng được vào thực tế. Để có được những thông tin quý báu chúng ta phải tìm ra các mẫu có trong tập CSDL trước. Việc đánh giá các mẫu được tìm thấy cũng là một điều thú vị và tất yếu có tính chất quyết định đến sự sử dụng hay không sử dụng chúng. Đầu ra của một chương trình là khám phá những mẫu có ích được gọi là tri thức. Tri thức được khám phá có các đặc điểm chính: - Kiến thức cao cấp: Ngày càng có nhiều câu hỏi mang tính chất định tính cần phải trả lời dựa trên một khối lượng dữ liệu khổng lồ đã có. Quá trình để tìm ra kiến thức như vậy không phải từ những phương pháp thống kê cổ điển mà nó được đúc kết từ các kinh nghiệm đã có, được thể hiện trong dữ liệu, những kết quả đó có thể lĩnh hội được. - Độ chính xác: Dù cho những mẫu khai thác thật sự có trong CSDL hay không thì việc đo lường trị giá của chúng là bắt buộc phải có. Chúng ta sẽ chỉ sử dụng những mẫu nào có độ chính xác càng cao thì hiệu quả công việc đạt được càng lớn, những mẫu có độ chính xác chưa được xác định rõ ràng hoặc không cao thì không nên sử ụng chúng. - Tính hấp dẫn: Khám phá tri thức được coi là lý thú vì nó có thể vạch ra các xu hướng một cách hoàn thiện. Đó là những điều mới lạ hay những quy trình tiềm năng, hữu ích ẩn chứa từ trong dữ liệu trước đó. 6 - Tính hiệu quả: thời gian chạy của thuật toán khám phá tri thức trên CSDL lớn có thể dự tính và chấp nhận được. Dữ liệu là tập hợp những bộ thông tin chính xác và quá trình khám phá tri thức được xem là sự loại bỏ các dư thừa, được rút gọn tới mức tối thiểu chỉ để lại các đặc trưng cơ bản cho dữ liệu. Tri thức được tìm thấy 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ệ trong chúng. Các mối quan hệ này có thể được hiểu ra, có thể được phát hiện, hoặc có thể được học. Nếu khám phá tri thức là toàn bộ quá trình chiết xuất tri thức từ các CSDL thì KPDL là giai đoạn chủ yếu của quá trình đó. KPDL là một quá trình phát hiện các mẫu mới, thường bao gồm việc thử tìm mô hình phù hợp với tập dữ liệu và tìm kiếm các mẫu từ tập dữ liệu theo mô hình đó. Sử dụng các kỹ thuật và các khái niệm của các lĩnh vực đã được nghiên cứu từ trước như: học máy, nhận dạng, thống kê, hồi quy, xếp loại, phân nhóm, các mô hình đồ thị, các mạng Bayes,… Nói cách khác, mục tiêu của khai thác dữ liệu là tìm kiếm các mẫu hoặc mô hình tồn tại trong cơ sở dữ liệu nhưng ẩn trong khối lượng lớn dữ liệu. 1.2. Quá trình khám phá tri thức Hình 1.1. Quá trình khám phá tri thức 7 Bắt đầu của quá trình là kho dữ liệu thô và kết thúc với tri thức được chiết xuất ra. Về lý thuyết thì có vẻ rất đơn giản nhưng thực sự đây là một quá trình rất khó khăn gặp phải rất 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, v.v... Quá trình khám phá trí thức tiến hành qua 6 giai đoạn sau đây: 1. Gom dữ liệu: Tập hợp dữ liệu là bước đầu tiên trong quá trình khai thác dữ liệu. Đây là bước được khai thác trong một cơ sở dữ liệu, một kho dữ liệu và thậm chí các dữ liệu từ các nguồn ứng dụng Web. 2. Trích lọc dữ liệu: Ở giai đọan này dữ liệu được lựa chọn hoặc phân chia theo một số tiêu chuẩn nào đó phục vụ mục đích khai thác, ví dụ chọn tất cả những em học sinh có điểm Trung bình học kỳ lớn hơn 8.0 và có giới tính nữ. 3. Làm sạch, tiền xử lý và chuẩn bị trước dữ liệu: Giai đoạn thứ ba này là giai đoạn hay bị sao lãng, nhưng thực tế nó là một bước rất quan trọng trong quá trình khai thác dữ liệu. Một số lỗi thường mắc phải trong khi gom dữ liệu là tính không đủ chặt chẽ, logic. Vì vậy, dữ liệu thường chứa các giá trị vô nghĩa và không có khả năng kết nối dữ liệu. Ví dụ: Điểm Trung bình = 12.4. Giai đoạn này sẽ tiến hành xử lý những dạng dữ liệu không chặt chẽ nói trên. Những dữ liệu dạng này được xem như thông tin dư thừa, không có giá trị. Bởi vậy, đây là một quá trình rất quan trọng vì dữ liệu này nếu không được “làm sạch – tiền xử lý – chuẩn bị trước” thì sẽ gây nên những kết quả sai lệch nghiêm trọng. 4. Chuyển đổi dữ liệu: Tiếp theo là giai đoạn chuyển đổi dữ liệu, dữ liệu đưa ra có thể sử dụng và điều khiển được bởi việc tổ chức lại nó, tức là dữ liệu sẽ được chuyển đổi về dạng phù hợp cho việc khai thác bằng cách thực hiện các thao tác nhóm hoặc tập hợp. 5. Khai thác dữ liệu: Đây là bước mang tính tư duy trong khai thác dữ liệu. Ở giai đoạn này nhiều thuật toán khác nhau đã được sử dụng để trích ra các mẫu 8 từ dữ liệu. Thuật toán thường dùng là nguyên tắc phân loại, nguyên tắc kết, v.v... 6. Đánh giá các luật và biểu diễn tri thức: Ở giai đoạn này, các mẫu dữ liệu được chiết xuất ra bởi phần mềm khai thác dữ liệu. Không phải bất cứ mẫu dữ liệu nào cũng đều hữu ích, đôi khi nó còn bị sai lệch. Vì vậy, cần phải ưu tiên những tiêu chuẩn đánh giá để chiết xuất ra các tri thức cần chiết xuất ra. Đánh giá sự hữu ích của các mẫu biểu diễn tri thức dựa trên một số phép đo. Sau đó sử dụng các kỹ thuật trình diễn và trực quan hóa dữ liệu để biểu diễn tri thức khai thác được cho người sử dụng. Trên đây là 6 giai đoạn của quá trình khám phá tri thức, trong đó giai đoạn 5khai thác dữ liệu (hay còn gọi đó là Data Mining) là giai đoạn được quan tâm nhiều nhất. 1.3. Quá trình khai thác dữ liệu Khai thác dữ liệu (KPDL) là một giai đoạn quan trọng trong quá trình khám phá tri thức (KPTT). Về bản chất, nó là giai đoạn duy nhất tìm ra được thông tin mới, thông tin tiềm ẩn có trong CSDL chủ yếu phục vụ cho mô tả và dự đoán. Mô tả dữ liệu là tổng kết hoặc diễn tả những đặc điểm chung của những thuộc tính dữ liệu trong kho dữ liệu mà con người có thể hiểu được. Dự đoán là dựa trên những dữ liệu hiện thời để dự đoán những quy luật được phát hiện từ các mối liên hệ giữa các thuộc tính của dữ liệu trên cơ sở đó chiết xuất ra các mẫu, dự đoán được những giá trị chưa biết hoặc những giá trị tương lai của các biến quan tâm. Quá trình KPDL bao gồm các bước chính được thể hiện như hình 1.2 sau: 9 Xác định 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. Thu thập và tiền xử lý dữ liệu: Thu thập các dữ liệu liên quan và tiền xử lý chúng sao cho thuật toán KPDL có thể hiểu được. Đây là một quá trình rất khó khăn, có thể gặp phải rất nhiều các vướng mắc như: dữ liệu phải được sao ra nhiều bản (nếu được chiết xuất vào các tệp), quản lý tập các dữ liệu, phải lặp đi lặp lại nhiều lần toàn bộ quá trình (nếu có mô hình dữ liệu thay đổi), v.v… Thuật toán khai thác dữ liệu: Lựa chọn thuật toán KPDL và thực hiện việc KPDL để tìm được các mẫu có ý nghĩa, các mẫu này được biểu diễn dưới dạng luật kết hợp, cây quyết định… tương ứng với ý nghĩa của nó. 1.4. Các phương pháp khai thác dữ liệu Với hai mục đích khai thác dữ liệu là Mô tả và Dự đoán, người ta thường sử dụng các phương pháp sau cho khai thác dữ liệu: - Luật kết hợp (association rules) - Phân lớp (Classfication) - Hồi qui (Regression) - Trực quan hóa (Visualiztion) - Phân cụm (Clustering) - Tổng hợp (Summarization) - Mô hình ràng buộc (Dependency modeling) - Biểu diễn mô hình (Model Evaluation) - Phân tích sự phát triển và độ lệch (Evolution and deviation analyst) - Phương pháp tìm kiếm (Search Method) 10 Có nhiều phương pháp khai thác dữ liệu được nghiên cứu ở trên, trong đó có ba phương pháp được các nhà nghiên cứu sử dụng nhiều nhất đó là: Luật kết hợp, Phân lớp dữ liệu và phân cụm dữ liệu. 1.5. Các lĩnh vực ứng dụng thực tiễn của KPDL Ở thập kỷ 90 của thế kỷ XX, người ta coi khai thác dữ liệu là quá trình phân tích cơ sở dữ liệu nhằm phát hiện ra các thông tin mới và giá trị, thường thể hiện dưới dạng các mối quan hệ chưa biết đến giữa các biến số. Những phát hiện này được sử dụng nhằm tăng thêm tính hiệu quả của doanh nghiệp trong khi phải cạnh tranh trên thương trường. Nhờ phân tích các dữ liệu liên quan đến khách hàng, doanh nghiệp có khả năng dự báo trước một số hành vi ứng xử của khách hàng. Những năm gần đây, người ta quan niệm khai thác dữ liệu (Đôi khi còn dùng thuật ngữ khám phá dữ liệu hay phát hiện tri thức) là một quá trình phân tích dữ liệu từ các viễn cảnh khác nhau và rút ra các thông tin bổ ích – những thông tin có thể dùng để tăng lợi nhuận, cắt giảm chi phí hoặc cả hai mục đích. Phần mềm khai thác dữ liệu là một công cụ phân tích dùng để phân tích dữ liệu. Nó cho phép người sử dụng phân tích dữ liệu theo nhiều góc nhìn khác nhau, phân loại dữ liệu theo những quan điểm riêng biệt và tổng kết các mối quan hệ đã được bóc tách. Xét về khía cạnh kỹ thuật, khai thác dữ liệu là một quá trình tìm kiếm các mối tương quan giữa các mẫu ẩn chứa trong hàng chục trường dữ liệu của một cơ sở dữ liệu quan hệ cỡ lớn. Hiện nay, kỹ thuật khai thác dữ liệu đang được áp dụng một cách rộng rãi trong rất nhiều lĩnh vực kinh doanh và đời sống khác nhau như: - Thương mại: Phân tích dữ liệu bán hàng và thị trường, phân tích đầu tư, quyết định cho vay, phát hiện gian lận, … - Thông tin sản xuất: Điều khiển và lập kế hoạch, hệ thống quản lý, phân tích kết quả thử nghiệm, … 11 - Thông tin khoa học: Dự báo thời tiết, CSDL sinh học: Ngân hàng gen, … khoa học địa lý: dự báo động đất,… - Trong y tế, marketing, ngân hàng, viễn thông, du lịch, internet…Giáo dục... 1.6. Các phương pháp, và kỹ thuật áp dụng trong KPDL Các kỹ thuật KPDL được chia làm 2 nhóm chính: - Kỹ thuật khai thác dữ liệu mô tả: Có nhiệm vụ mô tả về các tính chất hoặc các đặc tính chung của dữ liệu trong cơ sở dữ liệu hiện có. Các kỹ thuật này gồm có: Phân cụm (clustering), tóm tắt (summerization), trực quan hóa (visualiztation), phân tích sự phát triển và độ lệch (evolution and deviation analyst), phân tích luật kết hợp (association rules)… - Kỹ thuật khai thác dữ liệu dự đoán: Có nhiệm vụ đưa ra các dự đoán dựa vào các suy diễn trên dữ liệu hiện thời. Các kỹ thuật này gồm có: Phân lớp (classification), hồi quy (regression)… Tuy nhiên, chỉ có một số phương pháp thông dụng nhất là: Phân cụm dữ liệu, phân lớp dữ liệu, phương pháp hồi quy và khai thác luật kết hợp. a. Phân cụm dữ liệu: Mục tiêu chính của phương pháp phân cụm dữ liệu là nhóm các đối tượng tương tự nhau trong tập dữ liệu vào các cụm sao cho các đối tượng thuộc cùng một lớp là tương đồng còn các đối tượng thuộc các cụm khác nhau sẽ không tương đồng. Phân cụm dữ liệu là một ví dụ của phương pháp học không có thầy. Không giống như phân lớp dữ liệu, phân cụm dữ liệu không đòi hỏi phải định nghĩa trước các mẫu dữ liệu huấn luyện. Vì thế có thể coi phân cụm dữ liệu là một cách học bằng quan sát (learning by observation), trong khi phân lớp dữ liệu là học bằng ví dụ (learning by example). Trong phương pháp này bạn không thể biết kết quả các cụm thu được sẽ thế nào khi bắt đầu quá trình. Vì vậy, thông thường cần có một chuyên gia về lĩnh vực đó để đánh giá các cụm thu được. Phân cụm dữ liệu được sử dụng nhiều trong các ứng dụng về phân đoạn thị trường,