Đăng ký Đăng nhập
Trang chủ Một số thử nghiệm khai phá dữ liệu trong cơ sở dữ liệu oracle...

Tài liệu Một số thử nghiệm khai phá dữ liệu trong cơ sở dữ liệu oracle

.PDF
97
106
61

Mô tả:

ĐẠI HỌC QUỐC GIA HÀ NỘI KHOA CÔNG NGHỆ ĐINH THỊ KIM DUNG MỘT SỐ THỬ NGHIỆM KHAI PHÁ DỮ LIỆU TRONG CƠ SỞ DỮ LIỆU ORACLE CHUYÊN NGÀNH: CÔNG NGHỆ THÔNG TIN MÃ SỐ: 1.01.10 LUẬN VĂN THẠC SĨ Người hướng dẫn khoa học: TS ĐỖ VIỆT NGA HÀ NỘI - 2004 2 MỤC LỤC BẢNG KÝ HIỆU CÁC TỪ VIẾT TẮT ..................................................................... 4 MỞ ĐẦU .............................................................................................................. 5 CHƢƠNG I. PHÁT HIỆN TRI THỨC VÀ KHAI PHÁ DỮ LIỆU. ........................ 7 I.1. TỔNG QUAN KHAI PHÁ DỮ LIỆU ............................................................. 7 I.1.1. I.1.2. I.1.3. I.1.4. I.1.5. I.1.6. Khai phá dữ liệu là gì? ..................................................................... 7 Tiến trình phát triển - Tại sao? ........................................................ 8 Các chức năng khai phá dữ liệu - Các loại mẫu có thể khai phá. ... 10 Khai phá dữ liệu trên các loại dữ liệu nào? .................................... 13 Quá trình phát hiện tri thức - KDD................................................. 15 Các thách thức và giải pháp cơ bản. ............................................... 17 I.2. TIỀN XỬ LÝ DỮ LIỆU CHO KHAI PHÁ ..................................................... 18 I.2.1. I.2.2. I.2.3. I.2.4. Các nhiệm vụ chính của tiền xử lý .................................................. 19 Làm sạch dữ liệu ............................................................................ 19 Giảm bớt dữ liệu ............................................................................. 20 Chuyển dữ liệu thành dạng có thể khai phá được............................ 21 I.3. CÁC THỂ HIỆN, BIỂU DIỄN KẾT QỦA KHAI PHÁ. .................................. 21 I.4. KIẾN TRÚC CƠ BẢN HỆ THỐNG KHAI PHÁ DỮ LIỆU ........................... 22 CHƢƠNG II. CÁC CHỨC NĂNG CƠ BẢN KHAI PHÁ DỮ LIỆU ................... 24 II.1. KHAI PHÁ LUẬT KẾT HỢP ......................................................................... 24 II.1.1. II.1.2. II.1.3. II.1.4. II.1.5. II.1.6. II.1.7. Các khái niệm luật kết hợp. ............................................................ 24 Các loại khai phá luật kết hợp ........................................................ 25 Khai phá luật kết hợp Boolean đơn chiều ....................................... 26 Cải thiện thuật toán ........................................................................ 28 Khai phá luật nhiều mức ................................................................. 30 Khai phá luật nhiều chiều ............................................................... 30 Đánh giá phân tích luật kết hợp ...................................................... 31 II.2. PHÂN LỚP..................................................................................................... 31 II.2.1. II.2.2. II.2.3. II.2.4. II.2.5. II.2.6. Phân lớp ......................................................................................... 32 Phân lớp - một quá trình hai bước .................................................. 32 Xây dựng các tập dữ liệu ................................................................ 32 Phân lớp bằng học cây quyết định. ................................................. 33 Phân lớp Bayees ............................................................................. 37 Phân lớp bằng mạng Nơron. ........................................................... 39 II.3. KHAI PHÁ DỮ LIỆU VỚI GỘP NHÓM ....................................................... 44 II.3.1. II.3.2. II.3.3. II.3.4. Phân tích gộp nhóm ........................................................................ 44 Các phương pháp phân hoạch ........................................................ 45 Các phương pháp phân cấp ............................................................ 46 Đánh giá......................................................................................... 47 CHƢƠNG III. CÔNG CỤ KHAI PHÁ DỮ LIỆU ODM ORACLE DATA MINING ....................................................... 49 Một số thử nghiệm khai phá dữ liệu trong CSDL Oracle 3 III.1. CÁC THUẬT TOÁN ODM KHAI PHÁ DỮ LIỆU ........................................ 49 III.1.1. III.1.2. III.1.3. III.1.4. III.1.5. III.1.6. III.1.7. Thuật toán Adapter Bayes Network - ABN ...................................... 49 Thuật toán Naive Bayes - NB .......................................................... 50 Thuật toán Apriori .......................................................................... 50 Thuật toán dự báo biến đổi Predictor Variance .............................. 50 Thuật toán k-means nâng cao ......................................................... 50 Thuật toán O-Cluster ...................................................................... 51 Sử dụng các chức năng và lựa chọn thuật toán ............................... 51 III.2. CÁC BƢỚC KHAI PHÁ DỮ LIỆU ................................................................ 52 III.2.1. Xây dựng mô hình ........................................................................... 52 III.2.2. Kiểm thử mô hình ........................................................................... 52 III.2.3. Áp dụng - ghi điểm mô hình - Scoring............................................. 53 III.3. CÁC THÀNH PHẦN CỦA ODM .................................................................. 53 III.3.1. Data Mining Server DMS ............................................................... 53 III.3.2. Oracle9i Data Mining API.............................................................. 53 III.3.3. Các đối tượng trong ODM .............................................................. 53 III.4. THỰC HIỆN CÁC BƢỚC KHAI PHÁ DỮ LIỆU TRONG ODM .................. 55 III.4.1. Các bước chuẩn bị .......................................................................... 55 III.4.2. Xây dựng mô hình ........................................................................... 56 III.4.3. Ghi điểm dữ liệu bằng mô hình ....................................................... 57 CHƢƠNG IV. SỬ DỤNG ODM KHAI PHÁ DỮ LIỆU. ................................... 59 IV.1. MỘT SỐ ĐỊNH HƢỚNG KHAI PHÁ DỮ LIỆU TRONG CÁC CSDL .......... 59 IV.1.1. Hệ thống CSDL ngành Thuế ........................................................... 59 IV.1.2. Hệ thống CSDL Bảo hiểm nhân thọ ................................................ 63 IV.2. XÂY DỰNG CÔNG CỤ HỖ TRỢ ................................................................. 68 IV.2.1. Xây dựng các tiện ích xử lý dữ liệu ................................................. 68 IV.2.2. Xây dựng các giao diện hỗ trợ khai phá dữ liệu .............................. 72 IV.3. TIẾN HÀNH MỘT SỐ THỬ NGHIỆM KHAI PHÁ DỮ LIỆU ...................... 77 IV.3.1. IV.3.2. IV.3.3. IV.3.4. IV.3.5. Mô tả các thử nghiệm ..................................................................... 77 Phân lớp ......................................................................................... 79 Luật kết hợp.................................................................................... 82 Gộp nhóm ....................................................................................... 83 Khai phá luật kết hợp trong CSDL Bảo Việt ................................... 84 KẾT LUẬN .............................................................................................................. 86 TÀI LIỆU THAM KHẢO .......................................................................................... 88 PHỤ LỤC .............................................................................................................. 90 Một số thử nghiệm khai phá dữ liệu trong CSDL Oracle 4 BẢNG KÝ HIỆU CÁC TỪ VIẾT TẮT Từ Tiếng Anh Tiếng Việt CSDL Database Cơ sở dữ liệu DW Data Warehouse Kho dữ liệu KDD Knowledge Data Discovery Phát hiện tri thức dữ liệu DM Data Mining Khai phá dữ liệu ODM Oracle Data Mining Công cụ khai phá dữ liệu DMS Data Mining Server Máy chủ khai phá dữ liệu Một số thử nghiệm khai phá dữ liệu trong CSDL Oracle 5 MỞ ĐẦU Tiềm năng phát sinh và thu thập dữ liệu trong vòng vài thập kỷ qua đã tăng một cách nhanh chóng. Xu hƣớng máy tính hoá của các doanh nghiệp, các tổ chức, các giao dịch chính phủ cùng với sự phát triển của các công cụ thu thập dữ liệu nhƣ sử dụng mã vạch, máy quét văn bản, hình ảnh đến các thiết bị quan sát vệ tinh từ xa, sử dụng rộng rãi World Wide Web ... đã làm thế giới ngập trong hàng núi dữ liệu. Qua rất nhiều năm, dữ liệu đang bị chôn vùi vào lịch sử. Có thể nói chúng ta đang rất “giầu dữ liệu” nhƣng vẫn “nghèo thông tin” bởi vì chƣa có các công cụ phân tích tự động và hữu hiệu hỗ trợ cho con ngƣời nhận thức đƣợc dữ liệu. Lỗ hổng giữa dữ liệu và thông tin đã thúc đẩy sự phát triển công nghệ mới trợ giúp thông minh biến dữ liệu thành tri thức và thông tin có ích, đó là công cụ khai phá dữ liệu. Với công cụ này sẽ làm cho dữ liệu chết trở thành mỏ vàng tri thức. Việc khai phá và tìm kiếm tri thức tiềm tàng từ khối lƣợng dữ liệu khổng lồ đã có nhằm phục vụ cho những nhu cầu sử dụng thông tin cao hơn nhƣ trong các hệ chuyên gia hay hỗ trợ quyết định. Công đoạn khai phá tri thức đƣợc thực hiện qua các quá trình thu thập, tinh lọc dữ liệu để tìm các mẫu hình tri thức (pattern) có ý nghĩa sử dụng rất nhiều kỹ thuật nhƣ học máy, nhận dạng, thống kê, phân loại, mạng nơ-ron, các giải thuật di truyền .. Có thể nói khai phá dữ liệu là một lĩnh vực đa chỉ tiêu từ các công nghệ CSDL, trí tuệ nhân tạo, học máy, truy cập thông tin đến các tính toán hiệu năng cao… Luận văn này tập trung giới thiệu, đánh giá một số công nghệ, phƣơng pháp cơ bản khai phá dữ liệu trong các CSDL lớn và kho dữ liệu. Trên cơ sở đó, sử dụng và đánh giá đƣợc các công cụ hỗ trợ khai phá dữ liệu Oracle. Đó là nền tảng cơ bản hƣớng tới thử nghiệm khai phá dữ liệu trong một số kho dữ liệu thực với hy vọng thu nhận đƣợc các mô hình, quy luật có ý nghĩa và giá trị cao. Một động cơ thúc đẩy thử nghiệm khai phá dữ liệu nhằm xem xét, đánh giá rút kinh nghiệm việc xây dựng thiết kế CSDL tác nghiệp và kho dữ liệu sao cho tích luỹ đƣợc dữ liệu có tri thức. Luận văn bao gồm 4 chƣơng: Một số thử nghiệm khai phá dữ liệu trong CSDL Oracle 6 Chương I: Giới thiệu tổng quan các khái niệm cơ bản, xu hƣớng phát triển tất yếu các thách thức và các giải pháp của khai phá dữ liệu. Các bƣớc tiến hành, các nhiệm vụ và các phƣơng pháp đƣợc liệt kê trong chƣơng này hỗ trợ các kiến thức cơ bản cho công cuộc khai phá tri thức từ CSDL và kho dữ liệu. Chương II: Giới thiệu các chức năng, thuật toán của công cụ khai phá dữ liệu. Trên cơ sở đó so sánh đánh giá để gợi ý các lựa chọn hƣớng đi, công cụ và kỹ thuật khi tiến hành khai phá dữ liệu. Chƣơng này nhằm mô tả một bức tranh tổng thể cách tiếp cận các phƣơng pháp theo góc độ đơn giản hoá tối đa và tăng tính thực thi cho giải pháp khai phá dữ liệu. Nội dung chƣơng này sẽ là cơ sở nền tảng kỹ thuật để cài đặt các công cụ và thực thi khai phá dữ liệu. Đó là các mô tả thuật toán, kỹ thuật cải thiện hiệu năng, đánh giá so sánh các nhiệm vụ khai phá dữ liệu nhƣ Luật kết hợp, Phân lớp, Gộp nhóm với các thuật toán dựa trên các phƣơng pháp xác suất, thống kê, mạng nơron.… Chương III: Giới thiệu và đánh giá cách sử dụng ODM - công cụ hỗ trợ khai phá dữ liệu của Oracle đƣợc tích hợp trong hệ quản trị CSDL Oracle 9i. Một số nhiệm vụ và chức năng trong ODM đã đƣợc cải tiến từ các phƣơng pháp cơ bản khai phá dữ liệu. ODM đã cung cấp giao diện lập trình ứng dụng nhƣ các đối tƣợng, packages cho phép thực hiện khai phá dữ liệu trong CSDL Orale. Các giao diện API đƣợc viết và thực thi trên nền Java. Chƣơng này cũng mô tả trình tự thực hiện các bƣớc sử dụng ODM thực hiện khai phá dữ liệu. Chương IV: Trên cơ sở sử dụng công cụ ODM, xây dựng một số giao diện trợ giúp ngƣời dùng khai phá dữ liệu trên CSDL Oracle. Chƣơng này cũng đề cập một số nhu cầu khai phá dữ liệu trên kho dữ liệu ngành bảo hiểm và thuế dựa trên một số tri thức nghiệp vụ khi tham gia xây dựng ứng dụng tác nghiệp cho các ngành này. Mô tả tiến hành thử nghiệm khai phá trên một số dữ liệu giả định và dữ liệu của các lĩnh vực bảo hiểm và thuế. Việc áp dụng có tính chất thử nghiệm theo khía cạnh kỹ thuật và hiểu biết nghiệp vụ tích luỹ đƣợc trong quá trình triển khai ứng dụng. Tuy nhiên, để có đƣợc các kết quả thật sự có giá trị đòi hỏi cần có sự đầu tƣ, Một số thử nghiệm khai phá dữ liệu trong CSDL Oracle 7 tham gia trực tiếp của chính các chuyên gia chuyên ngành.. Em xin chân thành cám ơn TS. Đỗ Việt Nga, các thầy giáo của trƣờng Đại học Quốc gia, các thầy, các đồng nghiệp ở Viện CNTT và các bạn cùng lớp đã có nhiều ý kiến quý báu giúp em hoàn thành luận văn. PHÁT HIỆN TRI THỨC VÀ KHAI PHÁ DỮ LIỆU. I.1. Tổng quan khai phá dữ liệu I.1.1. Khai phá dữ liệu là gì? Về bản chất vật lý dữ liệu chỉ là các con số, hay một chuỗi các ký tự mà chúng ta thƣờng thu lƣợm hàng ngày hay còn gọi là giá trị của phép đo. Thông tin thể hiện các đặc trƣng của dữ liệu và cần có kiến thức liên quan đến dữ liệu để nhận biết đƣợc thông tin - thông tin = dữ liệu + kiến thức. Tri thức đƣợc trích lọc từ thông tin bao gồm các sự kiện và các quan hệ giữa chúng để có thể hiểu đƣợc, hoặc học đƣợc. Tri thức đƣợc xem là dữ liệu trừu tƣợng và tổng quát mức cao - tri thức = thông tin + suy luận. [2] Dữ liệu Income Debt Hình Error! No text of specified style in document.-1 Dữ liệu, thông tin và tri thức Ngày nay, dữ liệu cần phải mang lại nhiều “tri thức” hơn là bản thân dữ liệu để có thể hỗ trợ các quyết định chính sách, chiến lƣợc, giúp các tổ chức hoạt động Một số thử nghiệm khai phá dữ liệu trong CSDL Oracle 8 hiệu quả và tốt nhất. Quá trình tìm những thông tin có giá trị, những xu hƣớng phát triển và những yếu tố tác động lên chúng chính là quá trình phát hiện tri thức từ CSDL (Knowledge Discovery). Khai phá dữ liệu là một tập các kỹ thuật được sử dụng để tự động khai thác và tìm ra các mối quan hệ lẫn nhau của dữ liệu trong một tập dữ liệu rất lớn và phức tạp, tìm ra những mẫu tiềm ẩn trong tập dữ liệu đó [2] . Khai phá dữ liệu (Data mining) với định nghĩa đầy đủ là “khai phá tri thức từ dữ liệu” và đƣợc hiểu đơn giản nhƣ là sự trích lọc, đào mỏ tri thức từ dữ liệu. Đó chính là quá trình tìm kiếm những bụi vàng từ các khối quặng thô dữ liệu khổng lồ hay còn ví nhƣ quá trình “đãi cát tìm vàng”. I.1.2. Tiến trình phát triển - Tại sao? Tạo lập và thu thập dữ liệu Xử lý file (Khoảng 1960) Cỏc hệ thống quản trị CSDL (1970-1980) - Cỏc hệ thống CSDL phõn cấp và mạng - Cỏc hệ thống CSDL quan hệ - Mụ hỡnh húa dữ liệu- Mụ hỡnh quan hệ thực thể - Cỏc kỹ thuật tổ chức và Index dữ liệu. - Ngụn ngữ truy vấn SQL - Cỏc giao diện: Form và Report - Cỏc xử lý truy vấn và tối ưu truy vấn - Quản lý giao dịch: khụi phục, điều khiển tương tranh... - Cỏc xử lý giao dịch trực tuyến OLTP CSDL nõng cao (1980-nay) Cỏc mụ hỡnh DL: quan hệ mở rộng, hƣớng đối tƣợng, quan hệ đối tƣợng, suy diễn. Định hướng ứng dụng: Khụng gian, thời gian, đa phƣơng tiện, cơ sở tri thức, ... Kho DL và khai phỏ DL (1980) Kho DL và cụng nghệ OLAP Khai phỏ DL, phỏt hiện tri thức Cỏc hệ thống CSDL Webbased (1990- nay) Cỏc hệ thống CSDL XMLbased. Web mining Thế hệ mới của cỏc hệ thống tớch hợp thụng tin (2000....) Một số thử nghiệm khai phá dữ liệu trong CSDL Oracle 9 Hình Error! No text of specified style in document.-2 Tiến trình phát triển công nghiệp CSDL Khai phá dữ liệu đƣợc xem nhƣ là xu hƣớng tất yếu của ngành công nghiệp thông tin. Con đƣờng phát triển cơ sở dữ liệu gồm các quá trình: Tạo lập, thu thập dữ liệu, quản trị dữ liệu (lƣu trữ và truy cập), phân tích và hiểu biết dữ liệu [11] Tiến trình phát triển của CSDL bắt đầu từ nhu cầu thu thập, xử lý số liệu tính toán đơn giản, tiến tới việc quản lý dữ liệu chặt chẽ và sử dụng rộng rãi hơn, tạo ra các CSDL khổng lồ của nhiều Quốc gia và hỗ trợ các hoạt động tác nghiệp trong nhiều ngành. Để lấy đƣợc những thông tin có giá trị, cần tới các kỹ thuật có khả năng hợp nhất dữ liệu từ những CSDL này chuyển vào kho dữ liệu có tính ổn định, thống nhất và khái quát cao. Các kỹ thuật đó đƣợc gọi là Datawarehousing với môi trƣờng hoạt động Datawarehouse. Công nghệ kho dữ liệu bao gồm các kỹ thuật làm sạch, tích hợp dữ liệu và xử lý phân tích trực tuyến OLAP trên các dữ liệu tổng hợp, tích gộp, hợp nhất cho phép quan sát thông tin theo nhiều chiều, nhiều góc độ. Tuy nhiên, chỉ có Datawarehouse thì chƣa đủ để có tri thức. Mặc dù OLAP hỗ trợ phân tích đa chiều và hỗ trợ quyết định nhƣng vẫn thiếu công cụ phân tích thông tin theo mức độ sâu hơn nhƣ phân lớp dữ liệu, gộp nhóm, đƣa ra các giả thiết mới và đặc trƣng hoá dữ liệu. Đó là mục đích của các công cụ phân tích khai phá dữ liệu. Khai phá dữ liệu với các phân tích sâu hơn, tự động hơn sẽ hỗ trợ ngƣời quản lý tìm ra các khách hàng thích hợp, sáng suốt trong việc định hƣớng thị trƣờng, phát triển chiến lƣợc giá cả, điều chỉnh các kiểu loại mặt hàng trên cơ sở phân tích nhu cầu (mẫu, mô hình) của khách hàng thƣờng xuyên…. Khai phá dữ liệu đã và đang nhận đƣợc sự quan tâm rộng rãi của đông đảo giới khoa học và kinh doanh vì một số lý do chính sau đây: Số lƣợng và kích cỡ các CSDL của nhiều doanh nghiệp hiện nay đang tăng lên với một tốc độ đáng kinh ngạc. Các CSDL cỡ Terabyte (1024 GB) thậm chí Petabyte (1024 Terabyte) một thời đƣợc coi là không thể có, thì nay đang trở Một số thử nghiệm khai phá dữ liệu trong CSDL Oracle 10 thành thực tế trong nhiều lĩnh vực nhƣ: tiếp thị, bán hàng, tài chính, y tế, bảo hiểm, sinh học phân tử ... Các doanh nghiệp nhận ra có rất nhiều kiến thức có giá trị ẩn chứa trong dữ liệu mà khi phát hiện ra có thể đem lại sức cạnh tranh đáng kể cho doanh nghiệp. Xuất hiện một số công nghệ hỗ trợ thực thi khai phá dữ liệu trên các CSDL lớn. I.1.3. Các chức năng khai phá dữ liệu - Các loại mẫu có thể khai phá. Khai phá dữ liệu là giai đoạn chủ yếu của quá trình Phát hiện tri thức. Đó là những thông tin có giá trị nhƣ các mẫu hình (pattern/model) của dữ liệu. Công đoạn khai phá tri thức đƣợc thực hiện sau các quá trình thu thập và tinh lọc dữ liệu và chỉ tìm các mẫu hình có ý nghĩa trên tập dữ liệu có hy vọng chứ không phải là trên toàn bộ CSDL nhƣ các phƣơng pháp thống kê trƣớc đây. [4] Các nhiệm vụ khai phá dữ liệu tùy theo dạng kiến thức ngƣời dùng muốn tìm kiếm có thể chia thành hai loại chính là Mô tả (Description) và Dự báo (Prediction) [10] với ý nghĩa nhƣ sau: Nhiệm vụ Ý nghĩa Các phân tích Mô tả Đặc trƣng hóa các tính chất chung và cung cấp Description khung nhìn tổng quát của dữ liệu trong CSDL. - Luật kết hợp Gộp nhóm Dự báo Prediction Phân lớp Dự báo Thực hiện suy luận trên dữ liệu hiện tại để dự báo dữ liệu tƣơng lai. Bảng 1. Các loại nhiệm vụ khai phá dữ liệu 1. Phân tích kết hợp. Chức năng khai phá luật kết hợp: Nhằm phát hiện các luật kết hợp, chỉ ra các điều kiện một tập dữ liệu xuất hiện cùng nhau. Một luật kết hợp thƣờng có dạng X Y đƣợc diễn giải là: Bộ dữ liệu trong CSDL thỏa mãn điều kiện X thì cũng có thể thỏa mãn điều kiện Y. Các luật kết hợp thƣờng dùng để tìm ra các quan hệ hoặc tƣơng quan của các bộ dữ liệu cho các phân Một số thử nghiệm khai phá dữ liệu trong CSDL Oracle 11 tích thị trƣờng kinh doanh. Một luật kết hợp điển hình là đánh giá khả năng có thể. Ví dụ nhƣ ”70% ngƣời mua máy tính có thể sẽ mua phần mềm trò chơi”. Hình Error! No text of specified style in document.-3 Giao dịch mua hàng Thông thƣờng, các luật kết hợp đƣợc dùng để phát hiện xu hƣớng kinh doanh trên cơ sở phân tích các giao dịch khách hàng. Ngày nay, có thể sử dụng trong thƣ ơng mại điện tử để dự đoán truy cập trang Web nhƣ: Sau khi khai thác nhật ký truy cập đã phát hiện luật kết hợp thú vị là: Nếu ngƣời sử dụng truy cập trang Web A và B thì có cơ hội 80% ngƣời đó sẽ vào trang Web C trong cùng phiên làm việc. Trang C có thể hoặc không có liên kết trực tiếp từ trang A hoặc B. Điều này dẫn tới nên tạo ra liên kết đến trang C từ A hoặc B. 2. Phân lớp và dự báo Phân lớp là quá trình tìm một tập các mô hình (hoặc các hàm) mô tả phân biệt các lớp dữ liệu và sử dụng mô hình để dự báo lớp cho các đối tƣợng mới. Hàm phân lớp là một ánh xạ (phân loại) từ một mẫu dữ liệu vào một trong các lớp đã biết. Ví dụ, có thể xây dựng một mô hình mẫu chẩn đoán bệnh dựa trên các triệu chứng bệnh nhân cũ để khám cho các bệnh nhân mới. [5] Hình Error! No text of specified style in document.-4 Ví dụ mạng nơ ron phân lớp bệnh nhân Mỗi đối tƣợng, ví dụ có thể có nhiều thuộc tính và đa số là các thuộc tính để dự đoán (predictor) và có một thuộc tính nhận kết quả lớp gọi là thuộc tính đích. Đây là một dạng học trực tiếp - có thầy. Mô hình thu đƣợc dựa trên tập các dữ liệu Một số thử nghiệm khai phá dữ liệu trong CSDL Oracle 12 huấn luyện - là tập dữ liệu đã biết lớp. Kết quả của mô hình có thể biểu diễn theo các dạng khác nhau nhƣ: luật, cây quyết định, công thức toán học, hoặc mạng nơron... Dự báo: Đƣợc xem là quá trình xây dựng và sử dụng một mô hình để ƣớc định lớp cuả các trƣờng hợp chƣa biết lớp. Phân lớp và hồi quy là hai loại chính của bài toán dự báo. Trong đó phân lớp đƣợc sử dụng để dự báo các lớp có giá trị tên hoặc rời rạc, còn hồi quy để dự báo cho các Nợ giá trị liên tục hoặc có thứ tự. Một ví dụ khác: Có hai lớp “Cho vay” và “Không cho vay”. Với mỗi khách hàng đến vay có thể xác định một điểm tƣơng ứng trên đồ thị “thu nhập – nợ”. Những ngƣời có thể hoàn trả đƣợc tiền cho ngân hàng đƣợc ký hiệu là “o”, những ngƣời phá sản đƣợc ký hiệu là “x”. Khai phá dữ liệu nhằm xác định một ánh xạ tuyến tính trên đồ thị này để quyết định có haykhông cho vay với mỗi khách hàng theo các tình trạng Nợ và Thu nhập của họ [2]. Thu nhập Nợ Hình Error! No text of specified style in document.-5 Phân lớp khách hàng 3. Phân tích gộp nhóm Phân tích gộp nhóm là quá trình xác định lớp các đối tƣợng theo thuộc tính của chúng. Các đối tƣợng đƣợc gộp nhóm sao cho các phần tử trong cùng nhóm là giống nhau nhất (theo một tiêu chuẩn nào đó), các phần tử khác nhóm giống nhau ít nhất.Ví dụ: một công ty có thể phân loại khách hàng của mình thành nhiều nhóm khác nhau dựa trên các thuộc tính nhƣ tuổi, thu nhập, khả năng, trình độ,… [11] Một số thử nghiệm khai phá dữ liệu trong CSDL Oracle 13 Hình Error! No text of specified style in document.-6. Các phần tử được gộp nhóm Các đặc tính chung của các khách hàng trong cùng một loại sẽ đƣợc dùng để mô tả nhóm khách hàng đó. Khác với phân lớp và dự đoán, chức năng gộp nhóm sẽ tự tìm ra các lớp bằng cách phân hoạch các dữ liệu hợp thành các nhóm. Các mô hình gộp nhóm là kết quả của quá trình chƣa biết trƣớc giá trị thuộc tính đích. Khi các nhóm tìm đƣợc, mỗi nhóm đƣợc xem là một lớp và có thể thực hiện phân lớp đƣợc bằng cách sử dụng tên nhóm nhƣ tên lớp. I.1.4. Khai phá dữ liệu trên các loại dữ liệu nào? 1. Cơ sở dữ liệu quan hệ Các CSDL quan hệ là một trong những kho chứa phổ biến, giàu thông tin nhất và là dạng dữ liệu chủ yếu để nghiên cứu khai phá dữ liệu. Một số CSDL trong thƣơng mại có thể ứng dụng khai phá dữ liệu với triển vọng cho nhiều thành công nhƣ : [3] Các CSDL tiếp thị: Đây là lĩnh vực mà Datamining thu đƣợc thành công nhiều nhất. Bằng cách khai thác các CSDL về khách hàng đƣợc tích luỹ trong nhiều năm sẽ có thể rút ra đƣợc các mẫu hình và khuynh hƣớng phát triển. Mô tả lƣợc sử khách hàng đƣợc xây dựng để có chiến lƣợc tiếp thị hiệu quả hơn. Các CSDL bán lẻ: Ghi lại các thông tin giao dịch bán hàng, DM có thể thu đƣợc những mô hình về cách mua hàng của ngƣời tiêu dùng để mở các chiến dịch bán hàng, đóng gói hàng phù hợp. CSDL thị trƣờng chứng khoán: Bằng việc tìm kiếm mẫu hình và khuynh hƣớng phát triển trong dữ liệu thị trƣờng chứng khoán, có thể hạn chế thất bại bằng những quyết định chính xác hơn trong việc lựa chọn cổ phiếu nào mà tiềm năng là sẽ thu đƣợc lợi cao. CSDL về những khiếu nại của khách hàng: Đƣợc phân tích để dò tìm lỗi trong bảo hiểm, chi phí y tế, khai báo thu nhập để đóng thuế. Một số thử nghiệm khai phá dữ liệu trong CSDL Oracle 14 2. Kho dữ liệu Kho dữ liệu chứa thông tin thu thập từ rất nhiều nguồn, đƣợc lƣu trữ trong một lƣợc đồ hợp nhất. Kho dữ liệu đƣợc tổ chức theo các chủ đề và cung cấp tính lịch sử, tổng hợp cao với cấu trúc vật lý là CSDL quan hệ hoặc khối dữ liệu nhiều chiều. Kho dữ liệu là môi trƣờng tốt nhất cho khai phá dữ liệu hoạt động hiệu quả. [11] Hình Error! No text of specified style in document.-7 Mô hình nhiều tầng của Data warehouse 5. CSDL không gian CSDL không gian chứa các thông tin có quan hệ về mặt không gian nhƣ CSDL địa lý, CSDL ảnh vệ tinh và y học... Dữ liệu đƣợc biểu diễn theo dạng mã vạch, chứa bản đồ bit n-chiều hoặc bản đồ các điểm pixel. Bản đồ có thể đƣợc biểu diễn thành dạng véctơ trong đó đƣờng phố, cầu, toà nhà, hồ.. đƣợc biểu diễn nhƣ phép hợp các cấu trúc hình học cơ bản nhƣ điểm, đƣờng, đa giác... Khai phá dữ liệu có thể phát hiện mẫu bằng cách mô tả đặc trƣng của ngôi nhà gần một vị trí nào đó nhƣ công viên chẳng hạn. Nói chung, các khối dữ liệu không gian có thể tổ chức thành cấu trúc đa chiều và phân cấp. 6. CSDL văn bản CSDL văn bản chứa các mô tả từ nhƣ các câu, đoạn. Có nhiều CSDL văn bản có Một số thử nghiệm khai phá dữ liệu trong CSDL Oracle 15 tính phi cấu trúc nhƣ các trang Web hoặc nửa cấu trúc nhƣ các message mail, trang XML.. Để phát hiện các đặc tả chung của các lớp đối tƣợng, từ khoá, nội dung liên quan, đối tƣợng văn bản... các phƣơng pháp khai phá dữ liệu cần tích hợp với các kỹ thuật lấy thông tin và xây dựng từ điển, từ điển đồng nghĩa... 7. Dữ liệu Web Dữ liệu World Wide Web cung cấp các dịch vụ thông tin trực tuyến toàn cầu là cơ hội phong phú với nhiều thách thức mới cho khai phá dữ liệu. Khai phá dữ liệu Web với các mục đích cơ bản nhƣ: Khai phá nội dung Web để phát hiện ra các tri thức từ nội dung các trang Web. Khai phá cấu trúc Web: phát hiện mô hình nền tảng cấu trúc liên kết. Khai phá sử dụng Web: Phát hiện thông tin từ các phiên làm việc truy nhập của ngƣời dùng. Khi nắm bắt đƣợc các mẫu tra cứu trang có thể sắp xếp lại các liên kết và đƣa các quảng cáo vào những trang mà ngƣời dùng thƣờng quan tâm. [11]. I.1.5. Quá trình phát hiện tri thức - KDD Quá trình phát hiện tri thức bao gồm các bƣớc cơ bản sau [4]: Bước 1 - Nhận thức lĩnh vực ứng dụng: Xác định nhiệm vụ, yêu cầu mục đích ngƣời dùng. Bƣớc này sẽ làm sáng tỏ yêu cầu trích lọc thông tin và để lựa chọn các phƣơng pháp thích hợp theo mục đích bài toán và bản chất dữ liệu. Bước 2 - Tập hợp và tiền xử lý dữ liệu : Lựa chọn nguồn dữ liệu, xoá bớt các dữ liệu tạp, xử lý dữ liệu thiếu, mất, chuyển dạng, rời rạc hoá và giảm bớt dữ liệu. Bƣớc này cần nhiều thời gian nhất trong tiến trình KDD với các nhiệm vụ: Tạo lập dữ liệu đích: Lựa chọn dữ liệu hoặc tập trung vào các dữ liệu điển hình cho thực hiện khai phá. Tiền xử lý dữ liệu: Để một giải thuật DM làm việc trên toàn bộ CSDL sẽ rất cồng kềnh, kém hiệu quả vì vậy cần phải loại bớt các dữ liệu dƣ thừa, Một số thử nghiệm khai phá dữ liệu trong CSDL Oracle 16 không phù hợp và không nhất quán, bổ sung thêm các dữ liệu thiếu, hiệu chỉnh dữ liệu không chính xác ... Bước 3- Khai phá dữ liệu: Trích lọc mẫu ẩn giấu trong dữ liệu. Các lớp phƣơng pháp chính khai phá dữ liệu là dự báo và hồi quy, phân loại, tổng quát hoá nhƣ tìm quan hệ giữa các trƣờng, các luật kết hợp ... Bƣớc này có các nhiệm vụ: Chọn mục đích khai phá dữ liệu: Quyết định mục đích của quá trình KDD là phân lớp, hồi quy, hay gộp nhóm... Chọn các phƣơng pháp khai phá: Lựa chọn các phƣơng pháp sử dụng để tìm kiếm mẫu trong dữ liệu, quyết định các mô hình, tham số tƣơng ứng theo các dạng biểu diễn đƣợc nhƣ: Các luật, cây phân lớp, gộp nhóm … Bước 4 - Hậu xử lý: Diễn giải tri thức khám phá thành các mô tả và dự báo. Kiểm tra, diễn giải và đánh giá mẫu hình để có các mô hình tốt. Không phải mọi mẫu hình từ dữ liệu đều có ích hoặc sử dụng trực tiếp đƣợc. Một phƣơng pháp chuẩn là thƣờng chia dữ liệu thành 2 tập: Một tập huấn luyện và một tập để kiểm thử. Mỗi tập có thể lặp quá trình một số lần với các kiểu phân tách khác nhau sau đó đánh giá kết quả. Đơn giản hoá các luật, loại bỏ một số điều kiện hoặc luật để cho ngƣời dùng dễ hiểu, trích lọc các luật đáng quan tâm, có giá trị. Bước cuối cùng là sử dụng tri thức trong thực tế theo các cách khác nhau. Một số thử nghiệm khai phá dữ liệu trong CSDL Oracle 17 Hình Error! No text of specified style in document.-8 Quá trình khai phá dữ liệu I.1.6. Các thách thức và giải pháp cơ bản. 1. Thách thức: Cơ sở dữ liệu cực lớn: Các CSDL với hàng trăm trƣờng và bảng, hàng triệu bản ghi, chiếm nhiều gigabyte và terabyte. Kích thước chiều lớn: Tập dữ liệu lớn có nhiều thuộc tính và biến nên số chiều của bài toán tăng làm cho không gian tìm kiếm mẫu tăng cực kỳ nhanh. Nếu giả sử có 3 thuộc tính, mỗi thuộc tính có 2 giá trị thì số các bản ghi là 23=8 và số mẫu (pattern) sẽ là 3*3*3=27. Nếu có p thuộc tính, mỗi thuộc tính có d giá trị thì số mẫu dữ liệu là dp [5] Biến động dữ liệu và tri thức Sự thay đổi nhanh chóng dữ liệu làm cho các mẫu đã phát hiện trƣớc đây có thể không còn đúng. Hơn nữa các độ đo biến trong các CSDL ứng dụng có thể thay đổi, bị xoá, hoặc tăng lên theo độ đo mới. Các giải pháp có thể là các phƣơng pháp gia tăng để cập Một số thử nghiệm khai phá dữ liệu trong CSDL Oracle 18 nhật các mẫu. Thiếu dữ liệu và dữ liệu tạp: Đây là vấn đề có thể nói rất khó khăn cho việc khai phá dữ liệu. Thông thƣờng các hệ tác nghiệp chỉ quan tâm đến các dữ liệu cần để giải quyết các họat động tác nghiệp hàng ngày, các dữ liệu khác chƣa chú trọng thu thập hoặc ngƣời thao tác không nhập vào, nếu họ cảm thấy chƣa dùng để làm gì. Hầu hết các thiết kế dữ liệu trong các hệ tác nghiệp về Thuế cũng nhƣ Bảo hiểm các số liệu về tài chính, tài sản, thu nhập, vốn, doanh số, hoặc khai báo chi tiết tình trạng sức khỏe thƣờng đƣợc bỏ qua mặc dù các thiết kế dữ liệu cũng nhƣ các Form nhập liệu đều đã đƣợc cài đặt. 2. Một số giải pháp Có thuật toán hiệu quả và đủ mềm dẻo để tăng bộ nhớ. Lấy ví dụ mẫu : Chọn lọc các bộ dữ liệu đặc trƣng và tốt nhất. Giảm chiều: Chọn lọc các thuộc tính thích hợp cho mục đích khai phá. Tận dụng các xử lý song song: Hiện nay, do giá thành các thiết bị phần cứng không cao lắm, có thể áp dụng các giải pháp song song cho việc khai phá dữ liệu: Phân chia nhiệm vụ, dữ liệu cho nhiều bộ xử lý thực hiện đồng thời. Hình Error! No text of specified style in document.-9 Khai phá dữ liệu phân tán và song song Một số thử nghiệm khai phá dữ liệu trong CSDL Oracle 19 I.2. Tiền xử lý dữ liệu cho khai phá I.2.1. Các nhiệm vụ chính của tiền xử lý Các CSDL thế giới thực đƣợc thu thập từ nhiều nguồn và rất lớn do đó thƣờng bị thiếu, mất hoặc chứa nhiều dữ liệu tạp và không nhất quán. Do đó dữ liệu cần đƣợc tiền xử lý để nâng cao chất lƣợng dữ liệu và đảm bảo cho kết quả, cải thiện hiệu quả và dễ dàng khai phá. Các kỹ thuật tiền xử lý dữ liệu nhƣ: Làm sạch dữ liệu, bỏ bớt dữ liệu tạp, hiệu chỉnh sai lệch, tích hợp thành một kho dữ liệu thống nhất và chuẩn hoá thành các dạng có thể áp dụng khai phá đƣợc. Hình Error! No text of specified style in document.-1 Các nhiệm vụ tiền xử lý dữ liệu I.2.2. Làm sạch dữ liệu Mục đích của công đoạn làm sạch dữ liệu là đảm bảo chất lƣợng dữ liệu bằng các kỹ thuật sau đây: 1. Xử lý dữ liệu bị mất, thiếu Bỏ qua một số bộ dữ liệu không quan trọng. Thay thế các giá trị thiếu bằng các hằng tổng thể. Sử dụng các thuộc tính trung bình để lấp đầy giá trị thiếu. Sử dụng các thuộc tính có xác suất lớn nhất. 2. Xử lý dữ liệu tạp Dữ liệu tạp là những dữ liệu có lỗi ngẫu nhiên hoặc quá khác nhau về giá trị Một số thử nghiệm khai phá dữ liệu trong CSDL Oracle 20 thuộc tính, do sai sót của các thiết bị thu thập dữ liệu, do tính không nhất quán trong việc đặt tên, nhập dữ liệu. Có thể sử dụng các kỹ thuật làm mịn nhƣ: Chia lô: Với các dữ liệu sắp xếp đƣợc có thể phân chia dữ liệu (bằng cách so sánh, tham khảo các giá trị „láng giềng‟) thành các lô theo các kỹ thuật nhƣ: Đều - các lô có số các phần tử nhƣ nhau, Trung bình - các phần tử trong lô lấy giá trị trung bình của lô, Biên - các giá trị đƣợc tính theo giá trị gần biên. [11] Ví dụ tập dữ liệu: 8, 9, 15, 21, 21, 24, 25, 28, 34 Bảng 2. Ví dụ chia lô dữ liệu Lô 1 Chia đều Giá trị TB (8,9,15) (8+9+15)/3 =9 Lô 2 (21,21,24) (21+21+24)/3=22 (22,22,22) (21,24) (21,21,24) Lô 3 (25,28,34) (25+28+34)/3=29 (29,29,29) (25,34) (25,25,34) Chia TB (9,9,9) (min,max) (8,15) Biên (8,8,15) Kết hợp tính toán và đánh giá của con ngƣời: Phát hiện các giá trị nghi ngờ ví dụ nhƣ: các kiểm tra dữ liệu lƣơng vƣợt quá một giá trị max có thể.... Hồi quy : Làm mịn dữ liệu bằng cách điều chỉnh theo các hàm hồi quy. I.2.3. Giảm bớt dữ liệu Tính tổng gộp trong cấu trúc dữ liệu hình khối (cube). Ví dụ dữ liệu thể hiện chi tiết theo thời gian có thể đƣợc tổng gộp thành các mức năm, tháng, Hình Error! No text of specified quý... style in document.-2. Lấy dữ liệu tổng quát Tóm tắt, tổng quát hoá Một tập dữ liệu có mục đích giống nhau đƣợc tóm tắt và chiết xuất, tạo nên một tập nhỏ hơn, cung cấp một khung nhìn tổng quát về dữ liệu. Một bảng tóm tắt có thể đƣợc tổng quát thành những cấp độ trừu tƣợng khác nhau, dƣới những Một số thử nghiệm khai phá dữ liệu trong CSDL Oracle
- Xem thêm -

Tài liệu liên quan