.. ĐẠI HỌC THÁI NGUYÊN TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG TRẦN THỊ THU TRANG KHAI PHÁ LUẬT KẾT HỢP TỪ DỮ LIỆU CHUỖI THỜI GIAN LUẬN VĂN THẠC SĨ: KHOA HỌC MÁY TÍNH Thái Nguyên - 2012 ii LỜI CAM ĐOAN Tôi xin cam đoan luận văn “Khai phá luật kết hợp từ dữ liệu chuỗi thời gian” là công trình nghiên cứu của riêng tôi dƣới sự hƣớng dẫn của PGS.TS. Bùi Thế Hồng. Toàn bộ phần mềm do chính tôi lập trình và kiểm thử. Tôi xin chịu trách nhiệm về lời cam đoan của mình. Các số liệu và thông tin sử dụng trong luận văn này hoàn toàn là trung thực. Tác giả Trần Thị Thu Trang iii MỤC LỤC MỤC LỤC ......................................................................................................... ii DANH MỤC HÌNH VẼ ................................................................................... iv DANH MỤC CÁC BẢNG................................................................................ v DANH MỤC CÁC KÝ HIỆU, CÁC TỪ VIẾT TẮT ..................................... vi MỞ ĐẦU ........................................................................................................... 1 CHƢƠNG 1: KHÁI QUÁT VỀ KHAI PHÁ DỮ LIỆU VÀ CHUỖI THỜI GIAN ................................................................................................................. 3 1.1. Khai phá dữ liệu ..................................................................................... 3 1.1.1. Khai phá dữ liệu là gì? ..................................................................... 3 1.1.2. Nhiệm vụ của khai phá dữ liệu ........................................................ 3 1.1.3. Triển khai việc khai phá dữ liệu ...................................................... 5 1.1.4. Một số ứng dụng khai phá dữ liệu ................................................... 6 1.1.5. Quá trình phát hiện tri thức trong cơ sở dữ liệu .............................. 7 1.1.6. Các kỹ thuật khai phá dữ liệu ........................................................ 99 1.2. Dữ liệu chuỗi thời gian ......................................................................... 14 1.2.1. Khái niệm....................................................................................... 14 1.2.2. Tiền xử lý dữ liệu chuỗi thời gian ................................................. 17 CHƢƠNG 2: KHAI PHÁ LUẬT KẾT HỢP TỪ DỮ LIỆU CHUỖI THỜI GIAN ............................................................................................................... 20 2.1. Luật kết hợp trong khai phá dữ liệu ................................................... 20 2.1.1. Khái niệm luật kết hợp ................................................................ 20 2.1.2. Lý thuyết về luật kết hợp .............................................................. 21 2.2. Khai phá luật kết hợp ......................................................................... 27 iv 2.2.1. Khai phá luật kết hợp từ cơ sở dữ liệu........................................... 27 2.2.2. Khai phá luật kết hợp từ dữ liệu chuỗi thời gian ........................... 28 2.3. Thuật toán khai phá luật kết hợp từ dữ liệu chuỗi thời gian ................ 30 2.3.1. Thuật toán khai phá luật kết hợp từ dữ liệu thƣờng ...................... 30 2.3.2. Thuật toán khai phá luật kết hợp từ dữ liệu chuỗi thời gian ......... 40 CHƢƠNG 3: XÂY DỰNG CHƢƠNG TRÌNH THỬ NGHIỆM................... 53 3.1. Phát biểu bài toán ................................................................................. 53 3.2. Xây dựng chƣơng trình......................................................................... 54 KẾT LUẬN ..................................................................................................... 63 TÀI LIỆU THAM KHẢO ............................................................................... 64 v DANH MỤC HÌNH VẼ Hình 1.1. Quá trình phát hiện tri thức trong cơ sở dữ liệu ................................ 8 Hình 1.2. Đồ thị thể hiện thành phần xu hƣớng dài hạn ................................. 15 Hình1.3. Đồ thị thể hiện thành phần mùa ....................................................... 16 Hình 1.4. Đồ thị thể hiện thành phần chu kỳ .................................................. 16 Hình 1.5. Trung bình trƣợt hàm mũ ................................................................ 17 Hình 2.1. Một cây mẫu thƣờng xuyên ............................................................. 39 Hình 2.2. FP-Tree và CFP-Tree ...................................................................... 42 Hình 2.3: Các khoản mục đƣợc ánh xạ ........................................................... 44 Hình 2.4: Ví dụ cây CFP-Tree ........................................................................ 45 Hình 3.1. Bảng cơ sở dữ liệu........................................................................... 55 Hình 3.2. Giao diện chính của chƣơng trình ................................................... 56 Hình 3.3. Thực hiện chọn CSDL .................................................................... 56 Hình 3.4. Thực hiện xóa CSDL ...................................................................... 57 Hình 3.5. Tìm tập phổ biến dựa trên thuật toán CFPmine .............................. 58 Hình 3.6. Thực hiện lệnh Reset ....................................................................... 59 Hình 3.7. Chọn dữ liệu cho thuật toán tìm luật kết hợp.................................. 60 Hình 3.8. Thực hiện xóa cơ sở dữ liệu ............................................................ 60 Hình 3.9. Thực hiện luật kết hợp .................................................................... 61 Hình 3.10. Thực hiện lệnh Reset ..................................................................... 62 vi DANH MỤC CÁC BẢNG Bảng 2.1. Ma trận biểu diễn cơ sở dữ liệu .................................................. 3535 Bảng 2.2. Vector biểu diễn nhị phân cho tập 1 thuộc tính .............................. 35 Bảng 2.3. Vector biểu diễn nhị phân cho các tập 2 thuộc tính ........................ 36 Bảng 2.4. Vector biểu diễn nhị phân cho các tập 3 thuộc tính ........................ 36 Bảng 2.5. Vector biểu diễn nhị phân cho các tập 4 thuộc tính ........................ 36 Bảng 2.6. Các giao tác cơ sở dữ liệu .………………………………………38 Bảng 2.7. Khoản mục và số lần xuất hiện trong cơ sở dữ liệu ....................... 40 vii DANH MỤC CÁC KÝ HIỆU, CÁC TỪ VIẾT TẮT Các từ viết tắt Nghĩa tiếng anh Nghĩa tiếng việt FI Frequent Itemset Tập mục thƣờng xuyên Tập mục thƣờng xuyên FCI Frequent Closed Itemset đóng Maximally Frequent Tập mục thƣờng xuyên MFI Itemset lớn nhất CSDL Cơ sở dữ liệu FP-Tree Frequent Pattern Tree Cây mẫu thƣờng xuyên Compressed Frequent Cây mẫu thƣờng xuyên CFP-Tree Pattern Tree nén Inter-Transaction Khai phá luật kết hợp liên ITARM Association Rules Mining giao dịch 1 MỞ ĐẦU Ngày nay, cuộc cách mạng của kỹ thuật số cho phép số hóa thông tin dễ dàng và chi phí lƣu trữ thấp.Với sự phát triển của phần mềm, phần cứng và trang bị nhanh hệ thống máy tính trong kinh doanh. Số lƣợng dữ liệu khổng lồ đƣợc tập trung và lƣu trữ trong cơ sở dữ liệu. Dữ liệu sau khi phục vụ cho một mục đích nào đó đƣợc lƣu lại trong kho dữ liệu và theo ngày tháng khối lƣợng dữ liệu đƣợc lƣu trữ ngày càng lớn. Trong khối lƣợng dữ liệu to lớn này có rất nhiều thông tin có ích mang tính tổng quát, thông tin có tính quy luật vẫn còn đang tiềm ẩn mà chúng ta chƣa biết. Từ khối lƣợng dữ liệu rất lớn cần có những công cụ tự động rút các thông tin và kiến thức có ích. Một hƣớng tiếp cận có khả năng giúp các công ty khai thác các thông tin có nhiều ý nghĩa từ các tập dữ liệu lớn đó là khai phá dữ liệu. Với sự bùng nổ và phát triển của công nghệ thông tin đã mang lại nhiều hiệu quả đối với khoa học cũng nhƣ các hoạt động thực tế, trong đó khai phá dữ liệu là một trong những lĩnh vực mang lại hiệu quả thiết thực cho con ngƣời. Khai phá dữ liệu đã giúp ngƣời sử dụng thu đƣợc những tri thức hữu ích từ những cơ sở dữ liệu hoặc các kho dữ liệu khổng lồ khác. Luận văn đề cập đến các khái niệm và vấn đề cơ bản trong khai phá luật kết hợp từ dữ liệu chuỗi thời gian đƣợc áp dụng trong cơ sở dữ liệu bán hàng. Luận văn cấu trúc gồm 3 chƣơng: Chƣơng 1: Trong chƣơng 1 tìm hiểu khái quát về khai phá dữ liệu và dữ liệu chuỗi thời gian và phƣơng pháp tiền xử lý dữ liệu chuỗi thời gian. Chƣơng 2: Trong chƣơng 2 sẽ tìm hiểu phƣơng pháp khai phá dữ liệu từ chuỗi thời gian qua thuật toán ITARM dựa trên cấu trúc cây CFPTree. 2 Chƣơng 3: Trong chƣơng 3 tiến hành cài đặt thuật toán ở chƣơng 2 và cài đặt ứng dụng của thuật toán trên cơ sở dữ liệu bán hàng. Luận văn này đƣợc hoàn thành dƣới sự hƣớng dẫn tận tình của PGS.TS Bùi Thế Hồng, em xin bày tỏ lòng biết ơn chân thành của mình đối với thầy. Em xin chân thành cảm ơn các thầy, cô giáo Viện Công nghệ thông tin, Trƣờng Đại học Công nghệ thông tin và Truyền thông - Đại học Thái Nguyên đã tham gia giảng dạy, giúp đỡ em trong suốt qúa trình học tập nâng cao trình độ kiến thức. Tuy nhiên vì điều kiện thời gian và khả năng có hạn nên luận văn không thể tránh khỏi những thiếu sót. Em kính mong các thầy cô giáo và các bạn đóng góp ý kiến để đề tài đƣợc hoàn thiện hơn. 3 CHƢƠNG 1: KHÁI QUÁT VỀ KHAI PHÁ DỮ LIỆU VÀ CHUỖI THỜI GIAN 1.1. Khai phá dữ liệu 1.1.1. Khai phá dữ liệu là gì? Khai phá dữ liệu là một khái niệm ra đời vào những năm cuối của thập kỷ 80. Nó bao hàm một loạt các kỹ thuật nhằm phát hiện ra các thông tin có giá trị tiềm ẩn trong các tập dữ liệu lớn(các kho dữ liệu). Về bản chất, khai phá dữ liệu liên quan đến việc phân tích các dữ liệu và sử dụng các kỹ thuật để tìm ra các mẫu hình có tính chính quy trong tập dữ liệu. Năm 1989, Fayyad, Piatestsky-Shapiro và Smyth đã dùng khái niệm Phát hiện tri thức trong cơ sở dữ liệu để chỉ toàn bộ quá trình phát hiện các tri thức có ích từ các tập dữ liệu lớn. Trong đó, khai phá dữ liệu là một bƣớc đặc biệt trong toàn bộ quá trình, sử dụng các giải thuật đặc biệt để chiết xuất ra các mẫu (hay các mô hình) từ dữ liệu. Ở một mức độ trừu tƣợng nhất định có thể định nghĩa về khai phá dữ liệu: Khai phá dữ liệu là một quá trình tìm kiếm, phát hiện các tri thức mới, tiềm ẩn, hữu dụng trong cơ sở dữ liệu lớn. Khám phá tri thức là mục tiêu chính của khai phá dữ liệu, do vậy hai khái niệm đó đƣợc xem nhƣ hai lĩnh vực tƣơng đƣơng nhau. Nhƣng, nếu phân chia một cách tách bạch thì khai phá dữ liệu là một bƣớc chính trong quá trình khám phá tri thức. 1.1.2. Nhiệm vụ của khai phá dữ liệu Các bài toán liên quan đến khai phá dữ liệu 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 khai phá dữ liệu 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. Một 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 4 nhiên ở công đoạn cuối cùng, việc phân tích kết quả sau khi đã khai phá dữ liệu vẫn luôn là công việc của con ngƣời. Do là một lĩnh vực đa ngành, khai phá dữ liệu 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, marketing, toán học, vận trù học, nhận dạng mẫu, tính toán thống kê … Điều mà khai phá dữ liệu 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 để 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. Chúng ta thấy những nhiệm vụ cơ bản nhất của khai phá dữ liệu 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ết hợ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. 5 - 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 khai phá dữ liệu đều coi các đố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.1.3. Triển khai việc khai phá dữ liệu Một nhóm các tác giả đề nghị triển khai quá trình khai phá dữ liệu theo 5 bƣớc: Bƣớc 1: Xác định rõ mục tiêu thƣơng mại cần khai phá. Bƣớc 2: Chuẩn bị dữ liệu (Thu thập, tiền xử lý, chuyển đổi khuôn dạng dữ liệu nếu thấy cần thiết) Bƣớc 3: Khai phá dữ liệu (Chọn thuật toán thích hợp) Bƣớc 4: Phân tích kết quả thu đƣợc (Xem có gì thú vị không?) 6 Bƣớc 5: Tiêu hóa các tri thức thu lƣợm đƣợc (Nhằm đề ra kế hoạch khai thác các thông tin mới) Một tác giả khác cũng nói tới quy trình 5 bƣớc của khai phá dữ liệu, với quan điểm gần giống nhƣ trên: 1. Chiết xuất, biến đổi và nạp dữ liệu vào hệ thống kho dữ liệu. 2. Lƣu trữ và quản trị dữ liệu trong một cơ sở dữ liệu nhiều chiều 3. Xác định mục tiêu cần khai phá (Sử dụng các công cụ phân tích về mặt tác nghiệp) 4. Sử dụng các phần mềm phân tích dữ liệu để khai phá dữ liệu 5. Thể hiện kết quả khai phá dƣới khuôn dạng hữu ích hay bảng biểu, đồ thị. 1.1.4. Một số ứng dụng khai phá dữ liệu Ở thập kỷ 90 của thế kỷ XX, ngƣời ta coi khai phá 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 phá 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 phá 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 phá dữ liệu là 7 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 phá 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, … - Thông tin khoa học: dự báo thời tiết, cơ sở dữ liệu 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… Và những gì thu đƣợc thật đáng giá. Điều đó đƣợc chứng minh bằng thực tế: Chẩn đoán bệnh trong y tế dựa trên kết quả xét nghiệm đã giúp cho bảo hiểm y tế phát hiện ra nhiều trƣờng hợp xét nghiệm không hợp lý, tiết kiệm đƣợc nhiều kinh phí mỗi năm; trong dịch vụ viễn thông đã phát hiện ra những nhóm ngƣời thƣờng xuyên gọi cho nhau bằng mobile và thu lợi hàng triệu USD; hay áp dụng khai phá dữ liệu vào phân tích các lần đăng nhập Web vào các trang liên quan đến thị trƣờng để phát hiện sở thích khách hàng, từ đó đánh giá hiệu quả của việc tiếp thị qua Web và cải thiện hoạt động của các Website. 1.1.5. Quá trình phát hiện tri thức trong cơ sở dữ liệu Khám phá tri thức trong cơ sở dữ liệu là lĩnh vực liên quan đến các ngành nhƣ: thống kê, học máy, cơ sở dữ liệu , thuật toán, trực quan hoá dữ liệu, tính toán song song và hiệu năng cao,… Mục đích của quá trình phát hiện tri thức là rút ra tri thức từ dữ liệu trong cơ sở dữ liệu lớn. Quá trình phát hiện tri thức trong cơ sở dữ liệu là quá 8 trình gồm nhiều giai đoạn và lặp lại, mà trong đó sự lặp lại có thể xuất hiện ở bất cứ bƣớc nào. Quá trình đó có thể đƣợc mô tả theo hình sau: Hình 1.1. Quá trình phát hiện tri thức trong cơ sở dữ liệu Bước thứ nhất: Hình thành, xác định và định nghĩa bài toán. Là tìm hiểu lĩnh vực ứng dụng từ đó hình thành bài toán, xác định các nhiệm vụ cần phải hoàn thành. Bƣớc này sẽ quyết định cho việc rút ra đƣợc các tri thức hữu ích và cho phép chọn các phƣơng pháp khai phá dữ liệu thích hợp với mục đích ứng dụng và bản chất của dữ liệu. Bước thứ hai: Thu thập và tiền xử lý dữ liệu. Là thu thập và xử lý thô, còn đƣợc gọi là tiền xử lý dữ liệu nhằm loại bỏ nhiễu (làm sạch dữ liệu), xử lý việc thiếu dữ liệu (làm giàu dữ liệu), biến đổi dữ liệu và rút gọn dữ liệu nếu cần thiết, bƣớc này thƣờng chiếm nhiều thời gian nhất trong toàn bộ qui trình phát hiện tri thức. Do dữ liệu đƣợc lấy từ nhiều nguồn khác nhau, không đồng nhất, … có thể gây ra các nhầm lẫn. Sau bƣớc này, dữ liệu sẽ nhất quán, đầy đủ, đƣợc rút gọn và rời rạc hoá. Bước thứ ba: Khai phá dữ liệu rút ra các tri thức, hay nói cách khác là trích ra các mẫu hoặc/và các mô hình ẩn dƣới các dữ liệu. Giai đoạn này rất quan trọng, bao gồm các công đoạn nhƣ: chức năng, nhiệm vụ và mục đích của khai phá dữ liệu, dùng phƣơng pháp khai phá nào? Thông thƣờng, 9 các bài toán khai phá dữ liệu bao gồm: các bài toán mang tính mô tả - đƣa ra tính chất chung nhất của dữ liệu, các bài toán dự báo - bao gồm cả việc phát hiện các suy diễn dựa trên dữ liệu hiện có. 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. Bước thứ tư: Sử dụng các tri thức phát hiện đƣợc. Là hiểu tri thức đã tìm đƣợc, đặc biệt là làm sáng tỏ các mô tả và dự đoán. Các bƣớc trên có thể lặp đi lặp lại một số lần, kết quả thu đƣợc có thể đƣợc lấy trung bình trên tất cả các lần thực hiện. Các kết quả của quá trình phát hiện tri thức có thể đƣợc đƣa và ứng dụng trong các lĩnh vực khác nhau. Do các kết quả có thể là các dự đoán 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 hoá quá trình này. Tóm lại: Khai phá tri thức là một quá trình kết xuất ra tri thức từ kho dữ liệu mà trong đó khai phá dữ liệu là công đoạn quan trọng nhất. 1.1.6. Các kỹ thuật khai phá dữ liệu Thƣờng đƣợc chia thành hai nhóm chính: - Kỹ thuật khai phá 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 phá 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 (regession)… 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 phá luật kết hợp. 1.1.6.1. 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 10 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, trong khi phân lớp dữ liệu là học bằng ví dụ. 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, phân đoạn khách hàng, nhận dạng mẫu, phân loại trang Web… Ngoài ra phân cụm dữ liệu còn có thể đƣợc sử dụng nhƣ một bƣớc tiền xử lý cho các thuật toán khai phá dữ liệu khác. 1.1.6.2. Phân lớp dữ liệu: Mục tiêu của phƣơng pháp phân lớp dữ liệu là dự đoán nhãn lớp cho các mẫu dữ liệu. Quá trình phân lớp 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 lớp dữ liệu. - Bƣớc 1: Một mô hình sẽ đƣợc xây dựng dựa trên việc phân tích các mẫu dữ liệu sẵn có. Mỗi mẫu tƣơng ứng với một lớp, đƣợc quyết định bởi một thuộc tính gọi là thuộc tính lớp. Các lớp dữ liệu này còn đƣợc gọi là lớ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. - Bƣớc 2: Sử dụng mô hình để phân lớp 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. Ví dụ về việc sử dụng phƣơng pháp phân lớp trong khai phá dữ liệu 11 là ứng dụng phân lớp các xu hƣớng trong thị trƣờng tài chính và ứng dụng tự động xác định các đối tƣợng đáng quan tâm trong cơ sở dữ liệu ảnh lớn. 1.1.6.3. Phƣơng pháp hồi quy: Phƣơng pháp hồi quy khác với phân lớp dữ liệu ở chỗ: Hồi quy dùng để dự đoán về các giá trị liên tục còn phân lớp 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 khai phá dữ liệu 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.1.6.4. Khai phá luật kết hợp: Mục tiêu của phƣơng pháp này là phát hiện và đƣa ra các mối liên hệ giữa các giá trị dữ liệu trong cơ sở dữ liệu. Mẫu đầu ra của giải thuật khai phá dữ liệu là luật kết hợp tìm đƣợc. Chẳng hạn, phân tích cơ sở dữ liệu bán hàng nhận đƣợc thông tin về những khách hàng mua máy tính có khuynh hƣớng mua phần mềm quản lý tài chính trong cùng lần mua đƣợc miêu tả trong luật kết hợp sau: “Máy tính=>Phần mềm quản lý tài chính” (Độ hỗ trợ: 2%, độ tin cậy: 60%) Độ hỗ trợ và độ tin cậy là hai độ đo của sự đáng quan tâm của luật. Chúng phản ánh sự hữu ích và sự tin cậy của luật đã khám phá. Độ hỗ trợ 2% có nghĩa là 2% của tất cả các vụ đang phân tích chỉ ra rằng máy tính và phần mềm quản lý tài chính là đã đƣợc mua cùng nhau. Còn độ tin cậy 60% có nghĩa là: 60% các khách hàng mua máy tính cũng mua phần mềm. Khai phá luật kết hợp đƣợc thực hiện qua hai bƣớc: Bƣớc 1: Tìm tất cả các tập mục phổ biến, một tập mục phổ biến đƣợc xác định qua tính hỗ trợ và thỏa mãn độ hỗ trợ cực tiểu. 12 Bƣớc 2: Sinh ra các luật kết hợp mạnh từ tập mục phổ biến, các luật phải thỏa mãn độ hỗ trợ cực tiểu và độ tin cậy cực tiểu. Phƣơng pháp này đƣợc sử dụng rất hiệu quả trong các lĩnh vực nhƣ maketing có chủ đích, phân tích quyết định, quản lý kinh doanh, phân tích giá thị trƣờng … 1.1.7. Những khó khăn trong khai phá dữ liệu Việc nghiên cứu và ứng dụng kỹ thuật khai phá dữ liệu gặp nhiều khó khăn, nhƣng không phải là không giải quyết đƣợc mà chúng cần đƣợc tìm hiểu để có thể phát triển tốt hơn. Những khó khăn phát sinh trong khai phá dữ liệu chính là dữ liệu trong thực tế thƣờng động, không đầy đủ, lớn và bị nhiễu. Trong trƣờng hợp khác, ngƣời ta không biết cơ sở dữ liệu có chứa thông tin cần thiết cho việc khai thác hay không và làm thế nào để giải quyết sự dƣ thừa thông tin không thích hợp này. - Dữ liệu lớn: Hiện nay các cơ sở dữ liệu với hàng trăm trƣờng và bảng, hàng triệu bản ghi với kích thƣớc rất lớn, có thể lên đến GB. Các phƣơng pháp giải quyết hiện nay là đƣa ra một ngƣỡng cho cơ sở dữ liệu, lấy mẫu, các phƣơng pháp tính xấp xỉ, xử lí song song. - Kích thƣớc lớn: không chỉ có số lƣợng bản ghi mà số các trƣờng trong cơ sở dữ liệu cũng nhiều. Vì vậy mà kích thƣớc của bài toán trở nên lớn làm tăng không gian tìm kiếm. Hơn nữa, nó cũng làm tăng khả năng một thuật toán khai phá dữ liệu có thể tìm thấy các mẫu giả. Biện pháp khắc phục là làm giảm kích thƣớc tác động của bài toán và sử dụng các tri thức biết trƣớc để xác định các biến không phù hợp. - Dữ liệu động: Đặc điểm cơ bản của hầu hết các cơ sở dữ liệu là nội dung của chúng thay đổi liên tục. Chẳng hạn nhƣ các biến trong cơ sở dữ liệu của ứng dụng đã cho chũng có thể bị thay đổi, bị xóa hoặc là tăng lên theo thời gian. Dữ liệu có thể thay đổi theo thời gian và việc khai phá dữ liệu 13 bị ảnh hƣởng bởi thời điểm quan sát dữ liệu, do đó có thể làm cho mẫu khai thác đƣợc trƣớc đó mất giá trị. Vấn đề này đƣợc giải quyết bằng giải pháp tăng trƣởng để nâng cấp các mẫu và coi những thay đổi nhƣ là cơ hội để khai thác bằng cách sử dụng nó để tìm kiếm các mẫu bị thay đổi. - Các trƣờng dữ liệu không phù hợp: Một đặc điểm quan trọng khác là tính không thích hợp của dữ liệu – nghĩa là mục dữ liệu trở thành không thích hợp với trọng tâm hiện tại của việc khai thác. Bên cạnh đó, tính ứng dụng của một thuộc tính đối với một tập con của cơ sở dữ liệu cũng là một vấn đề đôi khi cũng liên quan đến độ phù hợp. - Các giá trị bị thiếu: Sự có mặt hay vắng mặt của giá trị các thuộc tính dữ liệu phù hợp có thể ảnh hƣởng đến việc khai phá dữ liệu. Trong hệ thống tƣơng tác, sự thiếu vắng dữ liệu quan trọng có thể dẫn tới yêu cầu cho giá trị của nó hoặc kiểm tra để xác định giá trị của nó. Hoặc cũng có thể sự vắng mặt của dữ liệu đƣợc coi nhƣ một điều kiện, thuộc tính bị mất có thể đƣợc xem nhƣ một giá trị trung gian và giá trị không biết. - Các trƣờng dữ liệu bị thiếu: Một quan sát không đầy đủ cơ sở dữ liệu có thể làm cho dữ liệu có giá trị bị xem nhƣ có lỗi. Việc quan sát cơ sở dữ liệu phải phát hiện đƣợc toàn bộ các thuộc tính có thể dùng để thuật toán khai phá dữ liệu có thể áp dụng để giải quyết bài toán. Giả sử ta có các thuộc tính để phân biệt các tình huống đáng quan tâm. Nếu chúng không làm đƣợc điều đó thì có nghĩa là đã có lỗi trong dữ liệu. Đây cũng là vấn đề thƣờng xảy ra trong cơ sở dữ liệu kinh doanh. Các thuộc tính quan trọng có thể sẽ bị thiếu dữ liệu không đƣợc chuẩn bị. - Quá phù hợp: Khi một thuật toán tìm kiếm tham số tốt nhất cho một mô thình nào đó sử dụng một tập dữ liệu hữu hạn, nó có thể sẽ bị tình trạng “quá độ” dữ liệu (nghĩa là tìm kiếm quá mức cần thiết gây ra hiện tƣợng chỉ phù hợp với dữ liệu đó mà không có khả năng đáp ứng cho các dữ