- LUẬN VĂN THẠC SỸ KHOA HỌC NGÀNH: CÔNG NGHỆ THÔNG TIN NGHIÊN CỨU VÀ ÁP DỤNG MỘT SỐ KỸ THUẬT KHAI PHÁ DỮ LIỆU VỚI CƠ SỞ DỮ LIỆU NGÀNH THUẾ VIỆT NAM NGUYỄN THU TRÀ Hà Nội 2006 Hà Nội 2006 2 MỤC LỤC DANH MỤC CÁC KÝ HIỆU VÀ CÁC CHỮ VIẾT TẮT DANH MỤC CÁC BẢNG DANH MỤC CÁC HÌNH VẼ MỞ đẦU CHƯƠNG 1. - KHAI PHÁ DỮ LIỆU . - Tổng quan khai phá dữ liệu Dữ liệu. - 14 1.1.2 Tiền xử lý dữ liệu. - 16 1.1.3 Mô hình khai phá dữ liệu. - Các chức năng cơ bản khai phá dữ liệu Phân lớp (Classification. - 34 1.2.4 Khai phá luật kết hợp. - MỘT SỐ THUẬT TOÁN KHAI PHÁ DỮ LIỆU . - Thuật toán khai phá luật kết hợp Thuật toán Apriori. - ÁP DỤNG KHAI PHÁ TRÊN CSDL NGÀNH THUẾ..72 3.1. - Lựa chọn công cụ khai phá Lựa chọn công cụ. - Thử nghiệm khai phá luật kết hợp . - KẾT LUẬN HƯỚNG NGHIÊN CỨU TIẾP THEO TÀI LIỆU THAM KHẢO PHỤ LỤC DANH MỤC CÁC KÝ HIỆU VÀ CÁC CHỮ VIẾT TẮT Ký hiệu, chữ viết tắt Ý nghĩa Association Rules Các luật kết hợp Candidate itemset Một itemset trong tập Ck ựược sử dụng ựể sinh ra các large itemset Ck Tập các candidate k-itemset ở giai ựoạn thứ k Confidence độ chắc chắn của luật kết hợp = support(X∪Y)/support(X) phản ánh khả năng giao dịch hỗ trợ X thì cũng hỗ trợ Y CSDL Cơ sở dữ liệu DM Data mining Ờ Khai phá dữ liệu DW Data warehouse Ờ Kho dữ liệu đTNT đối tượng nộp thuế, chỉ tới các cá nhân hoặc tổ chức nộp thuế Frequent/large itemset Một itemset có ựộ hỗ trợ (support. - ngưỡng ựộ hỗ trợ tối thiểu ID Identifier Item Một phần tử của itemset Itemset Tập của các item k-itemset Một itemset có ựộ dài k Lk Tập các Large itemset ở giai ựoạn thứ k ODM Oracle Data Mining Ờ 1 công cụ khai phá dữ liệu TID Unique Transaction Identifier Transaction Giao dịch 5 DANH MỤC CÁC BẢNG Bảng 1.1: CSDL ựơn giản gồm các vắ dụ huấn luyện Bảng 1.2 Mô hình CSDL giao dịch ựơn giản Bảng 2.1 Cơ sở dữ liệu giao dịch T Bảng 2.2 Bảng các sản phẩm khai phá dữ liệu DANH MỤC CÁC HÌNH VẼ Hình 1.1 Quá trình khám phá tri thức Hình 1.2 Khuôn dạng ựơn bản ghi và ựa bản ghi Hình 1.3: Cây quyết ựịnh ựơn giản với các tests trên các thuộc tắnh X và Y.22 Hình 1.4: Sự phân lớp một mẫu mới dựa trên mô hình cây quyết ựịnh Hình 1.5 Cây quyết ựịnh cuối cùng cho CSDL T ựã nêu trong bảng Hình 1.6 Cây quyết ựịnh ở dạng giả code cho CSDL T (bảng Hình 1.7 Hồi qui tuyến tắnh Hình 1.8 Gộp nhóm theo phương pháp k-means (điểm ựánh dấu + là tâm) 36 Hình 1.9 Phân hoạch vun ựống hoặc tách dần Hình 1.10 Bước lặp ựầu tiên của thuật toán Apriori cho CSDL DB Hình 1.11 Lần lặp thứ 2 của thuật toán Apriori cho CSDL DB Hình 1.12 Lần lặp thứ 3 của thuật toán Apriori cho CSDL DB Hình 2.1 Thuật toán Apriori Hình 2.2 Thuật toán AprioriTid Hình 2.3 Vắ dụ Hình 2.4: Thời gian thực hiện cho mỗi lần duyệt của Apriori và AprioriTid 52 Hình 2.5: Một vắ dụ của cây phân cấp khái niệm cho khai phá các frequent itemsets nhiều mức Hình 2.6: FP-tree cho CSDL T trong bảng Hình 2.7 Thuật toán PHP Hình 2.8 Bộ nhớ với 2 lần duyệt của thuật toán PCY Hình 2.9 Sử dụng bộ nhớ cho các bảng băm nhiều chặng Hình 3.1 Công sức cần cho mỗi giai ựoạn khai phá dữ liệu Hình 3.2 Các bước khai phá luật kết hợp trên CSDL ngành Thuế Hình 3.3 Nhánh cây phân cấp ngành nghề Hình 3.4 Các luật khai phá từ ODM (ựộ dài luật Hình 3.5 Các luật khai phá từ ODM (ựộ dài luật Hình 3.6 Cây quyết ựịnh dùng ODM Ờ Bài toán phân tắch tỷ suất Hình 3.7 Cây quyết ựịnh dùng See5 Ờ Bài toán phân tắch tỷ suất Hình 3.8 Cây quyết ựịnh dùng ODM Ờ Bài toán xét số liệu một năm Hình 3.9 Cây quyết ựịnh dùng See5 Ờ Bài toán phân tắch trong năm MỞ đẦU Thời ựại phát triển mạnh của Internet, Intranet, Data warehouse, cùng với sự phát triển nhanh về công nghệ lưu trữ ựã tạo ựiều kiện cho các doanh nghiệp, các tổ chức thu thập và sở hữu ựược khối lượng thông tin khổng lồ. - Hàng triệu CSDL ựã ựược dùng trong quản trị kinh doanh, quản lý chắnh phủ, quản lý dữ liệu khoa học và nhiều ứng dụng khác. - Câu ỘSự lớn mạnh của các CSDL dẫn ựến sự cần thiết phải có các kỹ thuật và các công cụ mới ựể thực hiện chuyển ựổi tự ựộng dữ liệu một cách thông minh thành thông tin và tri thức hữu ắchỢ [10] ựã trở thành ựặt vấn ựề của nhiều bài viết về khai phá thông tin và tri thức từ các CSDL lớn. - Với mong muốn bước ựầu áp dụng kỹ thuật khai phá dữ liệu trên CSDL ngành Thuế, luận văn ựã tập trung nghiên cứu về các kỹ thuật khai phá dữ liệu và tiến hành khai phá thử nghiệm trên CSDL ngành Thuế. - Khả năng mở rộng tri thức có ắch ẩn trong dữ liệu ựể ựưa ra những hành ựộng cần thiết dựa trên tri thức ựó ựang trở nên ngày càng quan trọng trong thế giới cạnh tranh hiện nay. - Toàn bộ quá trình dùng các phương pháp luận dựa trên tắnh toán, bao gồm các kỹ thuật mới ựể phát hiện ra tri thức từ dữ liệu ựược gọi là khai phá dữ liệu (data mining). - [9] Khai phá dữ liệu là sự tìm kiếm thông tin mới, có giá trị và không tầm thường trong một khối lượng dữ liệu lớn. - Hai mục ựắch chắnh của khai phá dữ liệu là ựể dự ựoán (prediction) và mô tả (description). - Dự ựoán bao gồm việc dùng một vài biến hoặc trường trong tập dữ liệu ựể dự ựoán các giá trị tương lai hoặc chưa biết của các biến cần quan tâm. - Còn mô tả tập trung vào việc tìm ra các mẫu mô tả dữ liệu mà con người có thể hiểu ựược/ biên dịch ựược. - Có thể ựưa các hoạt ựộng khai phá dữ liệu vào một trong hai loại sau. - Khai phá dữ liệu dự báo, tạo ra mô hình của hệ thống ựược mô tả bởi tập dữ liệu cho trước, hoặc Khai phá dữ liệu mô tả, với việc tạo ra thông tin mới, không tầm thường dựa trên tập dữ liệu có sẵn. - Một số chức năng khai phá dữ liệu chắnh như. - Tìm ra các ựặc ựiểm khái quát hoá, tổng kết, các ựặc ựiểm khác nhau trong dữ liệu. - Phân tắch nhóm (Cluster analysis): Chưa biết nhãn lớp, thực hiện nhóm dữ liệu thành các lớp mới dựa trên nguyên tắc cực ựại hoá sự tương tự trong cùng lớp và cực tiểu hoá sự khác tương tự giữa các lớp khác nhau. - Phân tắch xu hướng và sự phát triển Khai phá dữ liệu là một trong những lĩnh vực phát triển nhanh nhất trong công nghiệp máy tắnh. - Một trong những lớn mạnh nhất của khai phá dữ liệu là sự ảnh hưởng trong phạm vi rộng của các phương pháp luận và các kỹ thuật ựược ứng dụng ựối với một loạt các bài toán, các lĩnh vực. - Trong kinh doanh, khai phá dữ liệu có thể ựược dùng ựể khám phá ra những xu hướng mua sắm mới, kế hoạch cho các chiến lược ựầu tư, và phát hiện những sự tiêu dùng không chắnh ựáng từ hệ thống kế toán. - Các kỹ thuật khai phá dữ liệu có thể ựược áp dụng ựối với các bài toán thiết kế lại quy trình kinh doanh, trong ựó mục ựắch là ựể hiểu ựược các tương tác và quan hệ trong thông lệ kinh doanh và các tổ chức kinh doanh. - Nhiều ựơn vị thi hành luật, các ựơn vị ựiều tra ựặc biệt, có nhiệm vụ tìm ra các hành ựộng không trung thực và phát hiện ra các xu hướng phạm tội, cũng ựã sử dụng khai phá dữ liệu một cách thành công. - Các kỹ thuật khai phá dữ liệu cũng có thể ựược dùng trong các tổ chức tình báo nơi lưu giữ nhiều nguồn dữ liệu lớn liên quan ựến các hoạt ựộng, các vấn ựề về an ninh quốc gia. - Với mục ựắch nghiên cứu một số phương pháp khai phá dữ liệu và thử nghiệm khai phá trên CSDL ngành Thuế, luận văn ựược trình bày với các phần sau: Chương 1 Ờ Khai phá dữ liệu: Tìm hiểu các chức năng khai phá dữ liệu. - Chương 2 Ờ Một số thuật toán khai phá dữ liệu. - Nghiên cứu trên hai kiểu khai phá: Khai phá luật kết hợp - một kỹ thuật thông dụng trong học không giám sát. - Chương 3 Ờ Áp dụng khai phá trên CSDL ngành Thuế: Thử nghiệm khai phá luật kết hợp và phân lớp trên CSDL ngành Thuế 11 Chương 4 Ờ Kết luận và những kết quả ựạt ựược Cuối cùng là một số hướng nghiên cứu tiếp theo. - KHAI PHÁ DỮ LIỆU 1.1. - Tổng quan khai phá dữ liệu Khai phá dữ liệu có nguồn gốc từ các phương pháp riêng biệt, 2 dạng quan trọng nhất là thống kê và học máy. - [9] Có thể có ựịnh nghĩa về Khai phá dữ liệu như sau: Khai phá dữ liệu là quá trình phát hiện các mô hình, các tổng kết khác nhau và các giá trị ựược lấy từ tập dữ liệu cho trước. - Các kỹ năng phân tắch của con người là không ựầy ựủ do: Kắch thước và chiều của dữ liệu. - tốc ựộ tăng trưởng của dữ liệu là rất lớn. - Tất cả những ựiều ựó chắnh là những nguyên nhân thúc ựẩy Khai phá dữ liệu phát triển. - 13 Quá trình khám phá tri thức: Trước tiên, phân biệt giữa các thuật ngữ Ộmô hình (model)Ợ và Ộmẫu (pattern)Ợ dùng trong khai phá dữ liệu. - Mô hình là một cấu trúc Ộquy mô lớnỢ, có thể là tổng kết các quan hệ qua nhiều trường hợp (case) (ựôi khi là tất cả các trường hợp), trong khi mẫu là một cấu trúc cục bộ, thoả mãn bởi một số ắt trường hợp hoặc trong một miền nhỏ của không gian dữ liệu. - Trong khai phá dữ liệu, một mẫu ựơn giản là một mô hình cục bộ. - Khai phá dữ liệu - Lựa chọn dữ liệu: Xác ựịnh các tập dữ liệu ựắch và các trường liên quan - Làm sạch dữ liệu: Xoá bỏ nhiễu, tiền xử lý. - Giảm bớt dữ liệu và chuyển ựổi dữ liệu: Tìm ra những ựặc trưng hữu dụng, giảm bớt các chiều hoặc các biến, biểu diễn lại các ựại lượng bất biến - Lựa chọn chức năng khai phá dữ liệu: Tổng kết, phân lớp, Hồi qui, kết hợp, phân nhóm. - Lựa chọn thuật toán khai phá. - Thực hiện khai phá dữ liệu (Data Mining): Tìm kiếm các mẫu quan tâm - đánh giá các mẫu và biểu diễn tri thức 14 Hình 1.1 Quá trình khám phá tri thức 3. - Triển khai và tắch hợp vào các qui trình nghiệp vụ 1.1.1 Dữ liệu Do có nhiều kiểu dữ liệu, các CSDL sử dụng trong các ứng dụng cũng khác nhau, nên người dùng luôn mong ựợi một hệ thống khai phá dữ liệu có thể ựiều khiển ựược tất cả các loại dữ liệu. - Thực tế CSDL có sẵn thường là CSDL quan hệ và hệ thống khai phá dữ liệu cũng thực hiện hiệu quả việc khai phá tri thức trên dữ liệu quan hệ. - Với những CSDL của ứng dụng chứa các kiểu dữ liệu phức tạp, như dữ liệu hypertext và multimedia, dữ liệu tạm và không gian (spatial), dữ liệu kế thừa (legacy)Ầ thường phải có các hệ thống khai phá dữ liệu riêng biệt xây dựng ựể khai phá cho các kiểu dữ liệu cụ thể. - 15 Dữ liệu ựược khai phá có thể là dữ liệu có cấu trúc, hoặc không có cấu trúc. - Mỗi bản ghi dữ liệu ựược coi như một trường hợp hoặc một vắ dụ (case/example). - Dữ liệu không có cấu trúc có thể áp dụng các thuật toán khai phá dữ liệu thường là dữ liệu kiểu Text. - Khuôn dạng bảng của dữ liệu có thể thuộc hai loại. - Dữ liệu dạng ựơn bản ghi (còn gọi là kiểu không giao dịch), ựây là các bảng dữ liệu quan hệ thông thường. - Dữ liệu dạng ựa bản ghi (còn gọi là kiểu giao dịch), ựược dùng cho dữ liệu với nhiều thuộc tắnh. - Dữ liệu ựơn bản ghi không ựòi hỏi cung cấp khoá ựể xác ựịnh duy nhất mỗi bản ghi. - Hình 1.2 Khuôn dạng ựơn bản ghi và ựa bản ghi 1.1.2 Tiền xử lý dữ liệu Dữ liệu ựược chọn lọc sẽ phải qua bước tiền xử lý trước khi tiến hành khai phá phát hiện tri thức. - Bước thu thập và tiền xử lý dữ liệu là bước rất phức tạp. - Trong quá trình khai phá dữ liệu, nhiều khi phải thực hiện liên kết/tắch hợp dữ liệu từ rất nhiều nguồn khác nhau. - Các hệ thống sẵn có ựược thiết kế với những mục ựắch và ựối tượng phục vụ khác nhau, khi tập hợp dữ liệu từ những hệ thống này ựể phục vụ khai phá dữ liệu, hiện tượng dư thừa là rất phổ biến, ngoài ra còn có thể xảy ra xung ựột gây mấy dữ liệu, dữ liệu không ựồng nhất, không chắnh xác. - Rõ ràng yêu cầu chọn lọc và làm sạch dữ liệu là rất cần thiết. - Nếu ựầu vào của quá trình khai phá là dữ liệu trong DW thì sẽ rất thuận tiện, vì dữ liệu này ựã ựược làm sạch, nhất quán và có tắnh chất hướng chủ ựể. - 17 Tuy nhiên nhiều khi vẫn phải có thêm một số bước tiền xử lý ựể ựưa dữ liệu về ựúng dạng cần thiết. - Ngoài một số xử lý thông thường như: biến ựổi, tập hợp dữ liệu từ nhiều nguồn về một kho chung, xử lý ựể ựảm bảo nhất quán dữ liệu (khử các trường hợp lặp, thống nhất cách ký hiệu, chuyển ựổi về khuôn dạng thống nhất (ựơn vị tiền tệ, ngày tháng. - Một số xử lý ựặc biệt cần chú ý trong bước tiền xử lý dữ liệu: Xử lý với dữ liệu thiếu (missing data): Thường thì khi khai phá dữ liệu không ựòi hỏi NSD phải xử lý các giá trị thiếu bằng cách thức ựặc biệt nào. - Khi khai phá, thuật toán khai phá sẽ bỏ qua các giá trị thiếu. - Sự có mặt của outliers có thể có ảnh hưởng ựáng kể trong các mô hình khai phá dữ liệu. - Outliers ảnh hưởng ựến khai phá dữ liệu trong bước tiền xử lý dữ liệu hoặc là khi nó ựược thực hiện bởi NSD hoặc tự ựộng trong khi xây dựng mô hình. - Binning: Một vài thuật toán khai phá dữ liệu có thể có lợi nhờ việc binning với cả hai loại dữ liệu number và categorical. - 1.1.3 Mô hình khai phá dữ liệu Mô hình khai phá dữ liệu là một mô tả về một khắa cạnh cụ thể của một tập dữ liệu. - Một mô hình khai phá dữ liệu có thể ựược mô tả ở 2 mức. - Các mô hình khai phá dữ liệu dựa trên 2 kiểu học: có giám sát và không giám sát (ựôi khi ựược nói ựến như là học trực tiếp và không trực tiếp Ờ directed and undirected learning) [11]. - Các hàm học không giám sát ựược dùng ựể tìm ra cấu trúc bên trong, các quan hệ hoặc tắnh giống nhau trong nội dung dữ liệu nhưng không có lớp hay nhãn nào ựược gán ưu tiên. - Tương ứng có 2 loại mô hình khai phá dữ liệu. - Các chức năng cơ bản khai phá dữ liệu 1.2.1 Phân lớp (Classification) Trong bài toán phân lớp, ta có dữ liệu lịch sử (các vắ dụ ựược gán nhãn - thuộc lớp nào) và các dữ liệu mới chưa ựược gán nhãn. - Giá trị của thuộc tắnh ựắch chắnh là nhãn của lớp. - Mục ựắch của việc phân lớp là xây dựng mô hình dựa vào dữ liệu lịch sử ựể dự báo chắnh xác nhãn (lớp) của các vắ dụ không gán nhãn. - Các thuật toán phân lớp khác nhau dùng các kỹ thuật khác nhau cho việc tìm các quan hệ giữa các giá trị của thuộc tắnh dự báo và các giá trị của thuộc tắnh ựắch trong dữ liệu huấn luyện. - Mô hình phân lớp có thể ựược dùng trên bộ dữ liệu kiểm thử/dữ liệu ựánh giá với mục ựắch so sánh các giá trị dự báo với các câu trả lời ựã biết. - Áp dụng mô hình phân lớp ựối với dữ liệu mới ựược gọi là sử dụng mô hình, và dữ liệu ựược gọi là dữ liệu sử dụng hay dữ liệu trung tâm (apply data or scoring data). - Việc sử dụng dữ liệu thường ựược gọi là Ổscoring the dataỖ. - dữ liệu cho mỗi trường hợp có thể bao gồm một số thuộc tắnh mô tả thói quen tiêu dùng của khách hàng, thu nhập, các thuộc tắnh nhân khẩu học,Ầ đây là những thuộc tắnh dự báo. - Dữ liệu huấn luyện sẽ ựược dùng ựể xây dựng mô hình dùng cho dự báo các trường hợp mới sau này (dự báo khách hàng mới có khả năng chi trả nợ không). - Nếu 21 mô hình dự báo YES và giá trị thực tế là YES, giá trị của phân lớp sai là $0. - Nếu mô hình dự báo YES và giá trị thực tế là NO, giá trị của phân lớp sai là $5. - chỉ số cột tương ứng với các giá trị dự báo. - Các thuật toán khác, như Naive Bayes (dự báo xác suất), dùng ma trận chi phắ trong khi tìm kết quả trên dữ liệu thật ựể ựưa ra giải pháp chi phắ ắt nhất. - Sử dụng mô hình (Phân lớp) Áp dụng mô hình cho tập dữ liệu kiểm thử với các lớp ựã xác ựịnh ựể kiểm tra và ựánh giá ựộ 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 ựể phân lớp cho các dữ liệu mới. - Như vậy có 3 tập dữ liệu có cấu trúc và các thuộc tắnh dự ựoán giống nhau: Tập huấn luyện và tập kiểm thử ựã biết lớp. - 22 1.2.1.2 Phân lớp bằng học cây quyết ựịnh Cây quyết ựịnh Phương pháp hiệu quả ựặc biệt cho việc tạo ra các bộ phân lớp từ dữ liệu là sinh ra cây quyết ựịnh. - Có một thuật toán cho việc tắnh toán giá trị ngưỡng tối ưu Z. - Các mẫu học ựầu tiên ựược sắp xếp trên các giá trị của thuộc tắnh Y ựang ựược xem xét. - Lý thuyết Bayees Cho X là dữ liệu vắ dụ của một lớp chưa biết. - Mỗi dữ liệu vắ dụ ựược biểu diễn bằng một vecto X=(x1
Xem thử không khả dụng, vui lòng xem tại trang nguồn hoặc xem
Tóm tắt