Tài liệu Phương pháp luật kết hợp trong khai phá dữ liệu

1 LỜI CẢM ƠN Luận văn này được hoàn thành với sự hướng dẫn của GS.TS Vũ Đức Thi – Viện Công nghệ thông tin. Trước tiên tôi xin chân thành bày tỏ lòng biết ơn sâu sắc tới GS.TS Vũ Đức Thi, người đã tận tình hướng dẫn, động viên giúp đỡ tôi trong suốt thời gian thực hiện luận văn. Tôi cũng xin chân thành cảm ơn các thầy cô trong Viện Công nghệ thông tin, Trường Đại học Sư phạm Hà Nội 2, tạo điều kiện thuận lợi cho tôi hoàn thành tốt khóa học. Xin chân thành cảm ơn các anh, các chị và các bạn học viên lớp Cao học K15KHMT- Trường Đại học sư phạm Hà Nội 2 đã luôn động viên, giúp đỡ và nhiệt tình chia sẻ với tôi những kinh nghiệm học tập, công tác trong suốt khoá học. Cuối cùng, tôi xin gửi lời cảm ơn sâu sắc đến gia đình, người thân, bạn bè đã động viên, khuyến khích và hỗ trợ cần thiết để tôi hoàn thành luận văn này. Mặc dù rất cố gắng, song luận văn này không thể tránh khỏi những thiếu sót, kính mong được sự chỉ dẫn của các quý thầy cô và các bạn. Hà Nội, ngày 5 tháng 12 năm 2013 Người viết Phù Xuân Vĩnh 2 LỜI CAM ĐOAN Tôi xin cam đoan rằng số liệu và kết quả nghiên cứu trong luận văn này là trung thực và không trùng lặp với các đề tài khác. Tôi cũng 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à Nội, ngày 05 tháng 12 năm 2013 Người cam đoan Phù Xuân Vĩnh 3 MỤC LỤC TRANG PHỤ BÌA TRANG LỜI CẢM ƠN ..................................................................................................................................... 1 LỜI CAM ĐOAN ............................................................................................................................... 2 MỤC LỤC........................................................................................................................................... 3 BẢNG KÝ HIỆU CHỮ VIẾT TẮT.................................................................................................... 4 DANH MỤC CÁC BẢNG ................................................................................................................. 5 DANH MỤC CÁC HÌNH ................................................................................................................... 6 MỞ ĐẦU............................................................................................................................................. 7 CHƯƠNG 1. TỔNG QUAN VỀ PHÁT HIỆN TRI THỨC VÀ KHAI PHÁ DỮ LIỆU ..... 9 1.1. Phát hiện tri thức và khai phá dữ liệu ..................................................................... 9 1.2. Quá trình phát hiện tri thức từ cơ sở dữ liệu ........................................................... 9 1.2.1. Xác định vấn đề ................................................................................................ 11 1.2.2. Thu thập và tiền xử lý dữ liệu ............................................................................ 11 1.2.3. Khai phá dữ liệu ................................................................................................ 13 1.2.4. Minh họa và đánh giá ........................................................................................ 14 1.2.5. Đưa kết quả vào thực tế ..................................................................................... 14 1.3. Khai phá dữ liệu................................................................................................... 14 1.3.1. Các định nghĩa về khai phá dữ liệu .................................................................... 14 1.3.2. Nhiệm vụ của khai phá dữ liệu .......................................................................... 15 1.3.3. Một số ứng dụng khai phá dữ liệu ..................................................................... 17 1.3.4. Các kỹ thuật khai phá dữ liệu ............................................................................ 17 1.3.5. Kiến trúc của hệ thống khai phá dữ liệu ............................................................. 22 1.4. Tổng kết chương .................................................................................................. 23 CHƯƠNG 2. LUẬT KẾT HỢP TRONG KHAI PHÁ DỮ LIỆU ..................................... 24 2.1. Bài toán kinh điển dẫn đến việc khai phá luật kết hợp ........................................... 24 2.2. Định nghĩa về luật kết hợp .................................................................................... 25 2.3. Một số hướng tiếp cận trong khai phá luật kết hợp ................................................ 32 2.4. Một số thuật toán phát hiện luật kết hợp ................................................................ 33 2.4.1. Thuật toán Apriori ............................................................................................. 33 2.4.2. Thuật toán Apriori-TID ..................................................................................... 39 2.4.3. Thuật toán Apriori-Hybrid................................................................................. 41 2.5. Tổng kết chương ................................................................................................... 33 CHƯƠNG 3. KHAI PHÁ TẬP MỤC CỔ PHẦN CAO TRONG CƠ SỞ DỮ LIỆU…....43 3.1. Tổng quan về khai phá tập mục cổ phần cao ......................................................... 43 3.2. Một số định nghĩa khai phá tập mục cổ phần cao .................................................. 44 3.3.Thuật toán FSM .................................................................................................... 48 3.4.Thuật toán AFSM ................................................................................................. 51 3.5. Đánh giá thuật toán AFSM ................................................................................... 61 3.6. Xây dựng chương trình kha phá tập mục cổ phần cao theo thuật toán AFSM ....... 62 3.6.1. Đặt vấn đề.......................................................................................................... 62 3.6.2. Cấu trúc dữ liệu ................................................................................................. 62 3.6.3. Cấu trúc của chương trình .................................................................................. 64 3.6.4. Hướng dẫn sử dụng chương trình ....................................................................... 64 3.6.5. Kết quả thử nghiệm ............................................................................................ 66 3.7. Kết luận chương ................................................................................................... 71 PHẦN KẾT LUẬN ......................................................................................................... 72 TÀI LIỆU THAM KHẢO ............................................................................................... 73 4 BẢNG KÝ HIỆU CHỮ VIẾT TẮT STT Ký hiệu viết tắt Giải thích 1 ABBM: Algorithm Based on Boolean Matrix Thuật toán dựa trên ma trận Boolean 2 CSDL Cơ sở dữ liệu 3 DBMS Hệ quản trị cơ sở dữ liệu 4 IR (Information Retrieval) Truy xuất thông tin 5 Khai phá dữ liệu 8 KPDL OODBMS Object Oriented Management System RDBMS Ralational Management System I = {i1 , i2 ,..., in } 9 DB = {T1 , T2 ,..., Tm } Cơ sở dữ liệu có m giao tác Cơ sở dữ liệu giao tác con của DB, db 10 db ⊆ DB 11 ip Mục dữ liệu thứ p 12 Tq 13 n 14 m 15 A,B,C….. Giao tác thứ q Số mục dữ liệu một cơ sở dữ liệu giao tác Số giao tác của một cơ sở dữ liệu giao tác Tên các mục dữ liệu trong cơ sở dữ liệu giao tác 16 minsup Ngưỡng độ hỗ trợ 17 minshare Ngưỡng cổ phần tối thiểu 18 minconf Ngưỡng độ tin cậy tối thiểu 19 │X│ Số phần tử của tập hợp X 6 7 Database Hệ quản trị cơ sở dữ liệu hướng đối tượng Database Hệ quản trị cơ sở dữ liệu quan hệ Tập n mục dữ liệu 5 DANH MỤC CÁC BẢNG Bảng 2.1. Giao dịch mua hàng Bảng 2.2. Tính độ hỗ trợ cho các tập hợp chứa các mặt hàng Bảng 2.3. Các luật kết hợp và độ tin cậy của chúng Bảng 2.4. Dùng thuật toán Apriori tính ra các tập hợp xuất hiện σ–thường xuyên Bảng 2.5. Ma trận biểu diễn cơ sở dữ liệu Bảng 2.6. Vector biểu diễn nhị phân cho tập 1 thuộc tính Bảng 2.7. Vector biểu diễn nhị phân cho các tập 2 thuộc tính Bảng 2.8. Vector biểu diễn nhị phân cho các tập 3 thuộc tính Bảng 2.9. Vector biểu diễn nhị phân cho các tập 4 thuộc tính Bảng 3.1. Cơ sở dữ liệu ví dụ Bảng 3.2. Giá trị lmv và cổ phần của các mục dữ liệu trong CSDL bảng 3.1. Bảng 3.3. Các tập mục cổ phần cao của CSDL bảng 3.1 Bảng 3.4.CSDL minh hoạ ngữ nghĩa của tập mục cổ phần cao Bảng 3.5a. CSDL minh hoạ có trường hợp hai hàm tới hạn bằng nhau Bảng 3.5b. CSDL minh hoạ có trường hợp hai hàm tới hạn luôn bằng nhau Bảng 3.6. Giá trị hai hàm tới hạn khi k=1 Bảng 3.7. Các giá trị lmv và hàm tới hạn với k=1 Bảng 3.8. Các giá trị lmv và hàm tới hạn với k=2 Bảng 3.9. Các giá trị lmv và hàm tới hạn với k=3 Bảng 3.10. Các tập mục cổ phần cao của CSDL bảng 3.1 6 DANH MỤC CÁC HÌNH Hình 1.1. Quy trình phát hiện tri thức từ cơ sở dữ liệu Hình 1.2. Tập dữ liệu với hai lớp: có và không có khả năng trả nợ Hình 1.3. Phân loại của các dữ liệu vay nợ trong hai miền lớp Hình 1.4. Phân cụm tập dữ liệu cho vay thành 3 cụm Hình 1.5. Kiến trúc điển hình của một hệ thống khai phá dữ liệu Hình 3.1. Minh họa bảng dữ liệu giao tác có số lượng Hình 3.2. Cấu trúc file nhập dữ liệu mẫu minh họa. Hình 3.3. Giao diện chương trình XAMPP Hình 3.4. Giao diện chính của chương trình Hình 3.5. Giao diện màn hình chọn file dữ liệu Hình 3.6. Giao diện màn hình nhập file dữ liệu Hình 3.7. Giao diện màn hình nhập ngưỡng cổ phần tối thiểu Hình 3.8. Giao diện màn hình nhập ngưỡng cổ phần không đúng Hình 3.9. Giao diện màn hình ghi lại file kết quả 7 MỞ ĐẦU 1. Lý do chọn đề tài Khai phá dữ liệu là một lĩnh vực quan trọng của ngành CNTT. Khai phá luật kết hợp là một kỹ thuật quan trọng của khai phá dữ liệu. Tri thức chiết xuất được từ CSDL là nguồn tài liệu hỗ trợ cho lãnh đạo trong việc lên kế hoạch hoạt động hoặc trong việc ra quyết định sản xuất kinh doanh. Vì vậy, tính ứng dụng của khai thác luật kết hợp từ cơ sở dữ liệu là một vấn đề đang được quan tâm. Khai phá dữ liệu là giai đoạn quan trọng trong tiến trình khai thác tri thức từ cơ sở dữ liệu, các tri thức này hỗ trợ cho việc ra quyết định trong khoa học và kinh doanh. Khai phá dữ liệu đang được áp dụng một cách rộng rãi trong nhiều lĩnh vực kinh doanh và đời sống khác nhau: Tài chính, ngân hàng, bảo hiểm, khoa học, y tế… Rất nhiều tổ chức và công ty lớn trên thế giới đã áp dụng kỹ thuật khai phá dữ liệu vào các hoạt động sản xuất kinh doanh của mình và thu được những lợi ích to lớn. Mục đích nghiên cứu của đề tài là tìm hiểu các kỹ thuật khai phá dữ liệu; các vấn đề liên quan đến luật kết hợp và tập mục cổ phần cao, nhằm phát hiện và đưa ra các mối liên quan giữa các giá trị dữ liệu trong cơ sở dữ liệu. Áp dụng và cài đặt được một chương trình khai phá tập mục cổ phần cao theo thuật toán AFSM (Advanced Fast Share Measure) . Với những lý do trình bày ở trên, tôi mạnh dạn chọn đề tài luận văn thạc sĩ của mình là: “ Phương pháp luật kết hợp trong khai phá dữ liệu ” 2. Mục đích nghiên cứu 8 - Tìm hiểu về các kỹ thuật khai phá dữ liệu, các vấn đề liên quan đến khai phá luật kết hợp nhằm phát hiện đưa ra các mối liên hệ giữa các giá trị dữ liệu trong cơ sở dữ liệu. - Tìm hiểu bài toán khai phá tập mục cổ phần cao và cơ sở lý thuyết của thuật toán FSM và AFSM từ đó đưa ra thực nghiệm tìm tất cả các tập mục cổ phần cao theo thuật toán AFSM (Advanced Fast Share Measure). 3. Nhiệm vụ nghiên cứu - Nghiên cứu tổng quan về khai phá dữ liệu, luật kết hợp trong cơ sở dữ liệu. - Nghiên cứu các bài toán, thuật toán luật kết hợp và khai phá tập mục cổ phần cao trong khai phá dữ liệu. 4. Đối tượng và phạm vi nghiên cứu - Nghiên cứu một số kỹ thuật khai phá dữ liệu sử dụng luật kết hợp. - Nghiên cứu thuật toán luật kết hợp trong khai phá dữ liệu - Nghiên cứu bài toán khai phá tập mục cổ phần cao theo thuật toán AFSM 5. Dự kiến đóng góp mới Đề tài khi hoàn thành sẽ giải quyết một phần quan trọng của bài toán tìm luật kết hợp và khai phá tập mục cổ phần cao. Đây là cơ sở để có thể phát triển ứng dụng áp dụng trong thực tế ở tất cả các lĩnh vực kinh doanh (bài toán bán hàng trong siêu thị), Tài chính, ngân hàng, bảo hiểm… hiện nay. 6. Phương pháp nghiên cứu - Nghiên cứu tài liệu, tìm hiểu các thông tin trên Internet về các kỹ thuật liên quan. - Sử dụng thử nghiệm công cụ có sẵn để hiểu rõ bản chất vấn đề, sau đó xây dựng chương trình demo. 9 CHƯƠNG 1. TỔNG QUAN VỀ PHÁT HIỆN TRI THỨC VÀ KHAI PHÁ DỮ LIỆU 1.1. Phát hiện tri thức và khai phá dữ liệu Sự phát triển mạnh mẽ của công nghệ thông tin làm cho khả năng thu thập và xử lý thông tin của các hệ thống thông tin tăng một cách nhanh chóng. Số liệu thống kê đưa ra vào năm 2006 cho thấy tình trạng “ngập tràn thông tin mà thiếu thốn tri thức” hiện nay, tồn tại nhiều kho chứa dữ liệu khổng lồ có dung lượng tăng trưởng với tốc độ cao. Hàng triệu cơ sở dữ liệu đã được sử dụng trong các hoạt động sản xuất, kinh doanh, quản lý..., trong đó có nhiều cơ sở dữ liệu cực lớn cỡ Gigabyte, thậm chí là Terabyte. Ví dụ điển hình là Yahoo! có hơn 100TB, Google đã lưu trữ hơn 4 tỷ trang Web với dung lượng nhiều trăm TB; Alexa sau 7 năm đã có 500 TB. [6] Việc thu thập và lưu trữ các kho chứa dữ liệu khổng lồ được liệt kê trên đây 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ồ thành các tri thức có ích. Do vậy, khai phá dữ liệu (KPDL) nhằm phát hiện các tri thức mới giúp ích cho hoạt động của con người đã trở thành một lĩnh vực quan trọng của ngành Công nghệ thông tin. 1.2. Quá trình phát hiện tri thức từ cơ sở dữ liệu Thông tin là một khái niệm trừu tượng, được thể hiện dưới nhiều dạng thức khác nhau. Thông tin có thể được phát sinh, lưu trữ, biến đổi trong những vật mang tin (gọi là giá). Dữ liệu là sự biểu diễn thông tin và được thể hiện bằng các tín hiệu vật lý. Dữ liệu là một dãy các bit, các số và các ký hiệu, hoặc các “đối tượng” có 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. Sử dụng các bit để đo lường các thông tin và xem nó như là các dữ liệu đã được lọc bỏ các dư thừa, được rút gọn tới mức tối thiểu để đặc trưng một 10 cách cơ bản cho dữ liệu. Có thể xem tri thức 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. 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ói cách khác, tri thức có thể được coi là dữ liệu có độ trừu tượng và tổ chức cao.[6] Phát hiện tri thức trong các cơ sở dữ liệu là một quy trình nhận biết các mẫu hoặc các mô hình trong dữ liệu với các tính năng: hợp thức, mới, khả ích, và có thể hiểu được. Khai phá dữ liệu là một bước trong quy trình phát hiện tri thức gồm có các thuật toán khai phá dữ liệu chuyên dùng dưới một số quy định về hiệu quả tính toán chấp nhận được để tìm ra các mẫu hoặc các mô hình trong dữ liệu. Nói một cách khác, mục đích của phát hiện tri thức và KPDL là tìm ra các mẫu và các mô hình đang tồn tại trong các cơ sở dữ liệu nhưng vẫn còn bị che khuất bởi hàng “núi” dữ liệu. Quá trình phát hiện tri thức được mô tả tóm tắt trên Hình 1.1: Hình 1.1. Quy trình phát hiện tri thức từ cơ sở dữ liệu - Làm sạch dữ liệu (Data cleaning): Loại bỏ dữ liệu nhiễu hoặc dữ liệu không thích hợp. 11 - Tích hợp dữ liệu (Data integration): Tích hợp dữ liệu từ các nguồn khác nhau. - Chọn dữ liệu (Data Selection): Chọn những dữ liệu liên quan trực tiếp đến nhiệm vụ. - Chuyển đổi dữ liệu (Data Transformation): Chuyển dữ liệu về những dạng phù hợp cho việc khai phá. - KPDL (Data mining): Các kỹ thuật được áp dụng để trích xuất thông tin có ích hoặc các mẫu điển hình trong dữ liệu. - Đánh giá mẫu (Pattern evaluation): Đánh giá mẫu hoặc tri thức đã thu được. -Trình diễn dữ liệu (Knowledge Presentation): Biểu diễn những tri thức khai phá được cho người sử dụng. Nhiều người coi KPDL và khám phá tri thức trong cơ sở dữ liệu là như nhau. Tuy nhiên trên thực tế, KPDL là một bước trong quá trình phát hiện tri thức trong cơ sở dữ liệu, thi hành một thuật toán KPDL để tìm ra các mẫu từ dữ liệu theo khuôn dạng thích hợp. 1.2.1. Xác định vấn đề Là một quá trình mang tính định tính với mục đích xác định được lĩnh vực yêu cầu phát hiện tri thức và xây dựng bài toán tổng kết. Trong thực tế, các cơ sở dữ liệu được chuyên môn hóa và phân chia theo các lĩnh vực khác nhau như sản phẩm, kinh doanh, tài chính, … Với mỗi tri thức phát hiện được có thể có giá trị trong lĩnh vực này nhưng lại không mang nhiều ý nghĩa đối với một lĩnh vực khác. Vì vậy mà việc xác định lĩnh vực và định nghĩa bài toán giúp định hướng cho giai đoạn tiếp theo thu thập và tiền xử lý dữ liệu. 1.2.2. Thu thập và tiền xử lý dữ liệu Các cơ sở dữ liệu thu được thường chứa rất nhiều thuộc tính nhưng lại không đầy đủ, không thuần nhất, có nhiều lỗi và các giá trị đặc biệt. Vì vậy, giai đoạn thu thập và tiền xử lý dữ liệu trở nên rất quan trọng trong quá trình 12 phát hiện tri thức từ cơ sở dữ liệu. Có thể nói rằng giai đoạn này chiếm từ 70% đến 80% giá thành trong toàn bộ bài toán. Người ta chia giai đoạn thu thập và tiền xử lý dữ liệu thành các công đoạn như: lựa chọn dữ liệu, làm sạch, làm giàu, mã hóa dữ liệu. Các công đoạn được thực hiện theo trình tự đưa ra được một cơ sở dữ liệu thích hợp cho các giai đoạn sau. Tuy nhiên, tùy từng dữ liệu cụ thể mà quá trình trên được điều chỉnh cho phù hợp vì người ta đưa ra một phương pháp cho mọi loại dữ liệu. - Chọn lọc dữ liệu: Đây là bước chọn lọc các dữ liệu có liên quan trong các nguồn dữ liệu khác nhau. Các thông tin được chọn lọc sao cho có chứa nhiều thông tin liên quan tới lĩnh vực cần phát hiện tri thức đã xác định trong giai đoạn xác định vấn đề. - Làm sạch dữ liệu: Dữ liệu thực tế, đặc biệt dữ liệu lấy từ nhiều nguồn khác nhau thường không đồng nhất. Do đó cần có biện pháp xử lý để đưa về một cơ sở dữ liệu thống nhất phục vụ cho khai thác. Nhiệm vụ làm sạch dữ liệu thường bao gồm: Điều hòa dữ liệu: Nhằm giảm bớt tính không nhất quán do dữ liệu lấy từ nhiều nguồn khác nhau. Phương pháp thông thường là khử các trường hợp trùng lặp dữ liệu và thống nhất các ký hiệu. Chẳng hạn, một khách hàng có thể có nhiều bản ghi do việc nhập sai tên hoặc do quá trình thay đổi một số thông tin cá nhân gây ra và tạo sự lầm tưởng có nhiều khách hàng khác nhau. Xử lý các giá trị khuyết: Tính không đầy đủ của dữ liệu có thể gây ra hiện tượng dữ liệu chứa các giá trị khuyết. Đây là hiện tượng khá phổ biến. Thông thường, người ta có thể lựa chọn các phương pháp khác nhau để thực hiện việc xử lý các giá trị khuyết như: bỏ qua các bộ có giá trị khuyết, điểm bổ sung bằng tay, dùng một hằng chung để điền 13 vào giá trị khuyết, dùng giá trị trung bình của mọi bản ghi cùng lớp hoặc dùng các giá trị mà tần suất xuất hiện lớn. Xử lý nhiễu và các ngoại lệ: Thông thường, nhiễu dữ liệu có thể là nhiễu ngẫu nhiên hoặc các giá trị bất thường. Để làm sạch nhiễu, người ta có thể sử dụng phương pháp làm trơn nhiễu hoặc dùng các giải thuật phát hiện ra các ngoại lệ để xử lý. Làm giàu dữ liệu: Việc thu thập dữ liệu đôi khi không đảm bảo tính đầy đủ của dữ liệu. Một số thông tin quan trọng có thể thiếu hoặc không đầy đủ. Chẳng hạn, dữ liệu về khách hàng lấy từ một nguồn bên ngoài không có hoặc không đầy đủ thông tin về thu nhập. Nếu thông tin về thu nhập là quan trọng trong quá trình khai phá dữ liệu để phân tích hành vi khách hàng thì không thể chấp nhận đưa các dữ liệu khuyết thiếu vào được. Quá trình làm giàu dư liệu cũng bao gồm việc tích hợp và chuyển đổi dữ liệu. Các dữ liệu từ nhiều nguồn khác nhau được tích hợp thành một kho thống nhất. Các khuôn dạng khác nhau của dữ liệu cũng được quy đổi, tính toán lại để đưa về một kiểu thống nhất, tiện cho quá trình phân tích. Đôi khi, một số thuộc tính mới có thể được xây dựng dựa trên các thuộc tính cũ. - Mã hóa: Các phương pháp dùng để chọn lọc, làm sạch, làm giàu dữ liệu sẽ được mã hóa dưới dạng các thủ tục, chương trình hay tiện ích nhằm tự động hóa việc kết xuất, biến đổi và di chuyển dữ liệu. Các hệ thống con đó có thể được thực thi định kỳ làm tươi dữ liệu phục vụ cho việc phân tích. [6] 1.2.3. Khai phá dữ liệu Giai đoạn khai phá dữ liệu được bắt đầu sau khi dữ liệu đã được thu thập và tiến hành xử lý. Trong giai đoạn này, công việc chủ yếu là xác định được bài toán khai phá dữ liệu, tiến hành lựa chọn phương pháp khai thác phù hợp với dữ liệu có được và tách ra các tri thức cần thiết. 14 Thông thường, các bài toán khai phá dữ liệu bao gồm: các bài toán mang tính chất mô tả - đưa ra những tính chất chung nhất của các dữ liệu, các bài toán khai thác dự báo – bao gồm cả việc thực hiện các suy diễn trên dữ liệu. Tùy theo bài toán xác định được mà ta lựa chọn các phương pháp khai phá dữ liệu cho phù hợp. 1.2.4. Minh họa và đánh giá Các tri thức phát hiện từ cơ sở dữ liệu cần được tổng hợp dưới dạng các báo cáo phục vụ cho các mục đích hỗ trợ quyết định khác nhau. Do nhiều phương pháp khai thác có thể được áp dụng nên các kết quả có mức độ tốt/xấu khác nhau. Việc đánh giá các kết quả thu được là cần thiết, giúp tạo cơ sở cho những quyết định chiến lược. Thông thường chúng được tổng hợp, so sánh bằng các biểu đồ và được kiểm nghiệm, tin học hóa. Công việc này thường là của các chuyên gia, các nhà phân tích và quyết định. 1.2.5. Đưa kết quả vào thực tế Các kết quả của quá trình phát hiện tri thức có thể được đưa vào ứng dụng trong những lĩnh vực khác nhau. Do các kết quả có thể là các dự báo hoặc các mô tả nên chúng có thể được đưa vào các hệ thống hỗ trợ ra quyết định nhằm tự động hóa quá trình này. Quá trình phát hiện tri thức có thể được tiến hành theo các bước trên. Ngoài ra trong quá trình khai thác người ta có thể thực hiện các cải tiến, nâng cấp cho phù hợp.[6] 1.3. Khai phá dữ liệu 1.3.1. Các định nghĩa về khai phá dữ liệu Khai phá dữ liệu được dung để mô tả quá trình phát hiện tri thức trong cơ sở dữ liệu. Qúa trình này kết xuất ra các tri thức tiềm ẩn từ dữ liệu giúp dự bóa trong kinh doanh, các hoạt động sản xuất, … Khai phá dữ liệu làm giảm chi phí về thời gian so với các phương pháp truyên thống trước kia (Ví dụ như 15 phương pháp thống kê). Sau đây là các định nghĩa mang tính mô tả của nhiều tác giả: - Định nghĩa của Ferruzza: Khai phá dữ liệu là tập hợp các phương pháp được dung trong tiến trình khám phá tri thức để chỉ ra sự khác biệt các mối quan hệ và các mẫu chưa biết bên trong dữ liệu. - Định nghĩa của Parsaye: Khai phá dữ liệu là quá trình trợ giúp quyết định, trong đó chúng ta tìm kiếm mẫu thông tin chưa biết và bất ngờ trong cơ sở dữ liệu lớn. - Định nghĩa của Fayyad: Khai phá dữ liệu là quá trình nhận biết các mẫu hoặc các mô hình trong dữ liệu với các tính chất: Đúng đắn, mới, khả ích và có thể hiểu được. - Định nghĩa Zekulin: Quá trình trích lọc các thông tin chưa biết trước, có thể nhận thức được, có thể tác động được từ CSDL lớn và sử dụng chúng để tạo ra quyết định công tác. KPDL là một bước trong quá trình khám phá tri thức bao gồm các thuật toán KPDL chuyên dùng dưới một số quy định về hiệu quả tính toán chấp nhận được để tìm ra các mẫu và các mô hình trong dữ liệu. Do vậy, mục đích của khám phá tri thức và KPDL là tìm ra các mẫu hoặc mô hình đang tồn tại trong các cơ sở dữ liệu nhưng vẫn còn bị khuất bởi số lượng dữ liệu khổng lồ. [6] 1.3.2. Nhiệm vụ của khai phá dữ liệu Các bài toán liên quan đến KPDL về bản chất là các bài toán thống kê. Điểm khác biệt giữa các kỹ thuật KPDL và các công cụ phục vụ tính toán thống kê mà chúng ta đã biết là ở khối lượng cần tính toán. Khi dữ liệu đã trở nên khổng lồ thì những khâu như: thu thập dữ liệu, tiền xử lý và xử lý dữ liệu đều đòi hỏi phải được tự động hóa. Tuy nhiên ở công đoạn cuối cùng, việc phân tích kết quả sau khi đã KPDL vẫn luôn là công việc của con người. 16 Do là một lĩnh vực đa ngành, KPDL thu hút các lĩnh vực khoa học khác như trí tuệ nhân tạo, cơ sở dữ liệu, hiển thị dữ liệu, marketing, toán học, vận trù học, tin sinh học, nhận dạng mẫu, tính toán thống kê … Điều mà KPDL có thể làm rất tốt là phát hiện ra những giả thuyết mạnh trước khi sử dụng những công cụ tính toán thống kê. Mô hình dự báo sử dụng kỹ thuật phân cụm (Crustering) để chia nhóm các sự vật, sự kiện sau đó rút ra các luật nhằm tìm ra đặc trưng cho mỗi nhóm và cuối cùng đề nghị một mô hình. Ví dụ, những bạn đọc đăng ký dài hạn của một tạp chí có thể phân nhóm dựa theo nhiều tiêu chí khác nhau (lứa tuổi, giới tính, thu nhập…), sau đó tạp chí căn cứ vào đặc trưng riêng của từng nhóm để đề ra mức phí thu trong năm sao cho phù hợp nhất. Những nhiệm vụ cơ bản nhất của KPDL là: - Phân cụm, phân loại, phân nhóm, phân lớp. Nhiệm vụ là trả lời câu hỏi: Một dữ liệu mới thu thập sẽ thuộc về nhóm nào? Quá trình này thường được thực hiện một cách tự động. - Khai phá luật kết hợp. Nhiệm vụ là phát hiện ra những mối quan hệ giống nhau của các bản ghi giao dịch. Luật kết hợp X=>Y có dạng tổng quát là: Nếu một giao dịch đã sở hữu các tính chất X thì đồng thời nó cũng sở hữu các tính chất Y, ở một mức độ nào đó. Khai phá luật kế thợp được hiểu theo nghĩa: Biết trước các tính chất X, vậy các tính chất Y là những tính chất nào? - Lập mô hình dự báo, bao gồm hai nhiệm vụ: Hoặc là phân nhóm dư liệu vào một hay nhiều lớp dữ liệu đã xác định từ trước, hoặc là sử dụng các trường đã cho trong một cơ sở dữ liệu để dự báo sự xuất hiện (hoặc không xuất hiện) của các trường hợp khác. - Phân tích đối tượng ngoài cuộc: Một cơ sở dữ liệu có thể có thể chứa các đối tượng không tuân theo mô hình dữ liệu. Các đối tượng dữ liệu như vậy gọi là các đối tượng ngoài cuộc. Hầu hết các phương pháp KPDL đều coi các 17 đối tượng ngoài cuộc là nhiễu và loại bỏ chúng. Tuy nhiên trong một số ứng dụng, chẳng hạn như phát hiện nhiễu thì sự kiện hiếm khi xảy ra lại được chú ý hơn những gì thường xuyên gặp phải. Sự phân tích dữ liệu ngoài cuộc được coi như là phai phá các đối tượng ngoài cuộc. Một số phương pháp được ứng dụng để phát hiện đối tượng ngoài cuộc: Sử dụng các hình thức kiểm tra mang tính thống kê trên cơ sở một phân phối dữ liệu hay một mô hình xác suất cho dữ liệu, dùng các độ đo khoảng cách mà theo đó các đối tượng có một khoảng cách đáng kể đến cụm bất kỳ khác được coi là đối tượng ngoài cuộc, dùng các phương pháp dựa trên độ lệch để kiểm tra sự khác nhau trong những đặc trưng chính của các nhóm đối tượng. - Phân tích sự tiến hóa: Phân tích sự tiến hóa thực hiện việc mô tả và mô hình hóa các quy luật hay khuynh hướng của những đối tượng mà ứng xử của chúng thay đổi theo thời gian. Phân tích sự tiến hóa có thể bao gồm cả đặc trưng hóa, phân biệt, tìm luật kết hợp, phân lớp hay phân cụm dữ liệu liên quan đến thời gian, phân tích dữ liệu theo chuỗi thời gian, so sánh mẫu theo chu kỳ và phân tích dữ liệu dựa trên tính tương tự. 1.3.3. Một số ứng dụng khai phá dữ liệu Hiện nay, kỹ thuật KPDL đ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à thi 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, … - 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… 1.3.4. Các kỹ thuật khai phá dữ liệu 18 Hình 1.2. biểu diễn một tập dữ liệu giả hai chiều bao gồm 23 trường hợp. Mỗi một điểm trên hình đại diện cho một người vay tiền ngân hàng tại một thời điểm trong quá khứ. Dữ liệu được phân loại thành hai lớp: những người không có khả năng trả nợ và những người tình trạng vay nợ đang ở trạng thái tốt. Hai mục đích chính của KPDL trong thực tế là dự đoán và mô tả. Hình 1.2. Tập dữ liệu với hai lớp: có và không có khả năng trả nợ 1.3.4.1 Khai phá dữ liệu dự đoán Nhiệm vụ của KPDL dự đoán là đưa ra các dự đoán dựa vào các suy diễn trên cơ sở dữ liệu hiện thời. Nó sử dụng các biễn hay các trường trong cơ sở dữ liệu để dự đoán các giá trị không biết hay các giá trị tương lai. Bao gồm các kỹ thuật: Phân loại (Classification); Hồi qui (Regression) Phân loại : Mục tiêu của phương pháp phân loại dữ liệu là dự đoán nhãn lớp cho các mẫu dữ liệu. Quá trình phân loại dữ liệu thường gồm hai bước: xây dựng mô hình và sử dụng mô hình để phân loại dữ liệu. 19 Bước 1: Xây dựng mô hình dựa trên việc phân tích các mẫu dữ liệu cho trước. Mỗi mẫu thuộc về một lớp, được xác định bởi một thuộc tính gọi là thuộc tính lớp. Các mẫu dữ liệu này còn được gọi là tập dữ liệu huấn luyện. Các nhãn lớp của tập dữ liệu huấn luyện đều phải được xác định trước khi xây dựng mô hình, vì vậy phương pháp này được gọi là học có giám sát. Bước 2: Sử dụng mô hình để phân loại dữ liệu. Trước hết chúng ta phải tính độ chính xác của mô hình. Nếu độ chính xác là chấp nhận được, mô hình sẽ được sử dụng để dự đoán nhãn lớp cho các mẫu dữ liệu khác trong tương lai. Hay nói các khác, phân loại là học một hàm ánh xạ một mục dữ liệu vào trong số các lớp cho trước. Hình 1.3. cho thấy sự phân loại của các dữ liệu vay nợ trong hai miền lớp. Ngân hàng có thể sử dụng các miền phân loại để tự động quyết định liệu những người vay nợ trong tương lai có nên cho vay hay không. Hình 1.3. Phân loại của các dữ liệu vay nợ trong hai miền lớp Hồi quy : 20 Phương pháp hối quy khác với phương pháp phân loại dữ liệu ở chỗ, hồi qui dùng để dự đoán về các giá trị liên tục còn phân loại dữ liệu chỉ dùng để dự đoán về các giá trị rời rạc. Hồi quy là một hàm học ánh xạ mục dữ liệu thành một biến dự đoán có giá trị thực. Có rất nhiều ứng dụng KPDL với nhiệm vụ hồi quy, chẳng hạn như khả năng đánh giá tử vong của bệnh nhân khi biết các kết quả xét nghiệm; chẩn đoán, dự đoán nhu cầu tiêu thụ một sản phẩm mới bằng một hàm chi tiêu quảng cáo. 1.3.4.2. Khai phá dữ liệu mô tả Kỹ thuật này 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 CSDL hiện có. Bao gồm các kỹ thuật: Phân cụm; Khai phá luật kết hợp... Phân cụm : 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 một cụm 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 giám sát. Phân cụm dữ liệu đòi hỏi phải định nghĩa trước các dữ liệu huấn luyện. 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, phân đoạn khách hàng, nhận dạng mẫu, phân loại trang Web... Hình 1.4. cho thấy sự phân cụm tập dữ liệu cho vay vào trong 3 cụm: Lưu ý rằng các cụm chồng lên nhau cho phép các điểm dữ liệu thuộc về nhiều hơn một cụm.