Nghiên cứu một số thuật toán tìm luật kết hợp trong khai phá dữ liệu và ứng dụng

- HOÀNG MINH GIANG NGHIÊN CỨU MỘT SỐ THUẬT TOÁN TÌM LUẬT KẾT HỢP TRONG KHAI PHÁ DỮ LIỆU VÀ ỨNG DỤNG Chuyên ngành: ĐẢM BẢO TOÁN HỌC CHO MÁY TÍNH VÀ CÁC HỆ THỐNG TÍNH TOÁN LUẬN VĂN THẠC SỸ ĐẢM BẢO TOÁN HỌC CHO MÁY TÍNH VÀ CÁC HỆ THỐNG TÍNH TOÁN NGƯỜI HƯỚNG DẪN KHOA HỌC: GS.TSKH BÙI CÔNG CƯỜNG Hà Nội, 2005 LỜI CẢM ƠN Tác giả xin bày tỏ lòng biết ơn chân thành đối với TSKH Bùi Công Cường (Viện Toán học) về sự tận tình hướng dẫn thực hiện luận văn này.
- 2 Chương 1 Sơ lược các phương pháp tiếp cận trong khai phá dữ liệu.
- Mục tiêu của khai phá dữ liệu.
- Các bước chính trong việc khai phá dữ liệu.
- Các kỹ thuật khai phá dữ liệu.
- Phương pháp xây dựng cây quyết định.
- Mô hình mạng Nơron nhân tạo.
- Phân vùng dữ liệu (Cluster Analysis.
- Khai phá dữ liệu bằng phương pháp Bayes.
- Những phương pháp khác.
- 28 Chương 2 Các thuật toán khai phá luật kết hợp.
- Khai phá luật kết hợp.
- 56 Chương 3 Cài đặt mềm khai phá luật kết hợp.
- Cài đặt các thuật toán khai phá luật kết hợp.
- Giao diện lấy dữ liệu.
- Vai trò của khai phá dữ liệu và luật kết hợp trong thực tiễn.
- 98 5 MỞ ĐẦU Ngày nay, nhất là từ những năm trên thế giới đã xuất hiện rất nhiều các kho dữ liệu lớn và do vậy khai phá dữ liệu là sự phát triển tất yếu trong quá trình phát hiện các tri thức và thông tin (mang lại hữu ích nào đó) từ các cơ sở dữ liệu nói trên.
- Khai phá dữ liệu (data mining) được hiểu là quá trình tìm kiếm những thông tin, tri thức có ích, tiềm ẩn và mang tính dự đoán trong các cơ sở dữ liệu lớn.
- Dữ liệu như nêu ở đây tồn tại rất đa dạng và dưới nhiều hình thức, chẳng hạn dữ liệu văn bản, các bản ghi trong cơ sở dữ liệu quan hệ, dữ liệu ảnh, dữ liệu âm thanh...Và với mỗi kiểu dữ liệu ấy lại đòi hỏi kỹ thuật xử lý phù hợp để có thể lấy ra được các thông tin có giá trị.
- Có rất nhiều phương pháp tiếp cận trong khai phá dữ liệu, nhưng trong khuôn khổ của luận văn này chỉ liệt kê một vài phương pháp và sau đó nêu tổng quan phương pháp khai phá dữ liệu bằng các luật kết hợp (Association rules).
- Nhiệm vụ chính của luận văn là tìm hiểu một số thuật toán khai phá luật kết hợp đồng thời cài đặt phần mềm khai phá luật dựa trên các thuật toán này với cơ sở dữ liệu ORACLE.
- Chương 1: Sơ lược các phương pháp tiếp cận trong khai phá dữ liệu • Chương 2: Các thuật toán khai phá luật kết hợp • Chương 3: Cài đặt phần mềm khai phá luật kết hợp • Chương 4: Kết luận Một lần nữa tác giả xin bày tỏ sự biết ơn thày giáo, GS, TSKH Bùi Công Cường (Viện Toán học) và các thày giáo khoa Toán ứng dụng, Đại học Bách khoa Hà nội đã hướng dẫn và giúp đỡ trong quá trình thực hiện luận văn này.
- 6 Chương 1 Sơ lược các phương pháp tiếp cận trong khai phá dữ liệu Chương 1 đề cập đến các nội dung chính sau đây ▪ Các mục tiêu chính của khai phá dữ liệu ▪ Các bước chính trong việc khai phá dữ liệu ▪ Các kỹ thuật khai phá dữ liệu.
- Phương pháp xây dựng cây quyết định ✓ Mô hình mạng Nơron nhân tạo ✓ Phân vùng dữ liệu ✓ Khai phá dữ liệu bằng phương pháp Bayes ✓ Những phương pháp khác 1.1.
- Mục tiêu của khai phá dữ liệu Đồng thời với việc sử dụng máy tính phổ biến hiện nay thì một lượng khổng lồ thông tin và dữ liệu được trao đổi và lưu trữ từng ngày .
- Bất kỳ một doanh nghiệp, một tổ chức nào cũng đều có hệ thống máy tính để thu thập, lưu trữ và xử lý dữ liệu.
- Một khi dữ liệu càng nhiều thì việc quản lý càng khó khăn, việc xử lý cũng thêm phức tạp và việc phân tích dữ liệu càng mất nhiều thời gian hơn, tốn kém hơn..
- Bối cảnh hiện nay là nhu cầu hiểu được những thông tin trong khối lượng dữ liệu đồ sộ đã trở thành tất yếu đối và phổ biến với mọi lĩnh vực như: thương mại, kinh doanh, công nghệ, khoa học, chính trị… Khai phá dữ liệu (data mining) được định nghĩa là quá trình tìm kiếm những thông tin, tri thức có ích, tiềm ẩn và mang tính dự đoán hoặc mô tả trong các cơ sở dữ liệu lớn.
- Người ta còn dùng thuật ngữ khám phá tri thức trong cơ sở dữ liệu (Knowledge Discovery in Database- KDD) như là cách gọi khác của khai phá dữ liệu.
- 7 Khai phá dữ liệu có hai mục tiêu chính là dự đoán (prediction) và mô tả kết quả (description).
- Dự đoán liên quan đến việc xây dựng mô hình bằng cách sử dụng mốt số trường (field) hay các biến (variable) trong các tập dữ liệu (data set) để đưa ra các các giá trị của các biến khác.
- Còn mô tả thì trái lại, là tập trung vào tìm cách đưa ra các mẫu, các biểu thức, công thức để biểu diễn dữ liệu theo cách mà con người có thể dễ dàng tiếp nhận được, hiểu được.
- Các mục tiêu của các hoạt động dự đoán (prediction) và mô tả (description) như nói ở trên có thể đạt được bằng cách sử dụng các kỹ thuật khai phá dữ liệu cụ thể như.
- Phân lớp dữ liệu (classification): là một kỹ thuật tìm ra hàm học dự đoán (predective learning function) để từ đó phân các phần tử của tập dữ liệu mẫu vào các lớp đã định nghĩa sẵn và tiêu biểu cho cách này là phương pháp xây dựng cây quyết định • Hồi quy (regression): là một kỹ thuật dự đoán bằng cách nội suy hoặc ngoại suy giá trị của biến trong tương lai trên cơ sở các giá trị đã thu thập được trong quá khứ.
- chẳng hạn như: mô hình mạng Nơron nhân tạo.
- Phân vùng dữ liệu (clustering): một kỹ thuật dự đoán phổ biến bằng cách phân chia dữ liệu thành các loại (categories) hoặc các vùng.
- Điểm khác biệt giữa phân vùng dữ liệu và phân lớp dữ liệu là các lớp trong phân lớp dữ liệu là đã được định nghĩa trước, biết trước và đã có tên gọi.
- Mô hình hoá các phụ thuộc (dependency modeling): là một kỹ thuật dự đoán bằng cách tìm ra các phụ thuộc quan trọng giữa các biến hoặc các giá trị trong các tập dữ liệu.
- Các bước chính trong việc khai phá dữ liệu Khai phá dữ liệu là một quá trình phức tạp, nhưng có thể chia thành các bước chính sau đây: Hình 1.1 Các bước chính trong khai phá dữ liệu • Bước 1: phát biểu bài toán và đưa ra các giả thiết Ở bước này cần xác định và khoanh vùng phạm vi các biến, xác định các biến độc lập và biến phụ thuộc.
- Để làm điều đó phải có sự kết hợp giữa hiểu biết lĩnh vực đang nghiên cứu cụ thể (application domain) và các mô hình khai phá dữ liệu.
- Phát biểu bài toán (State problem) Thu thập dữ liệu (Collecting Data) Tiền xử lý dữ liệu (preprocessing) Sử dụng và đánh giá mô hình Thông dịch và biểu diễn các kết quả 9 • Bước 2: thu thập dữ liệu Bước này sẽ xác định cách tạo ra hay lấy dữ liệu về.
- Điều đáng lưu ý là dữ liệu thu thập được và dữ liệu dùng để kiểm tra mô hình phải là từ một nguồn mà ra (để đảm bảo là cùng một hàm phân bố dữ liệu), nếu không, sự thành công của hệ thống là rất thấp.
- Bước 3: tiền xử lý dữ liệu Dữ liệu thu thập được từ bước 2 thường là từ kho dữ liệu, cửa hàng dữ liệu (data warehouse, data mart), từ các hệ cơ sở dữ liệu với các định dạng khác nhau…thậm chí có thể mâu thuẫn nhau, do đó việc tiền xử lý dữ liệu cũng rất quan trọng và thường trải qua 2 quá trình con sau: Quá trình lọc (outlier detection) là loại bỏ những dữ liệu không đảm bảo ràng buộc (inconsistent) hoặc không quan tâm, hoặc là những thông tin nhiễu… Quá trình mã hoá (encoding), tinh chỉnh (scaling) và lựa chọn ra các dữ liệu mẫu, điển hình (selecting feature).
- Chẳng hạn, một biến với domain trong khoảng từ [0,1] và một biến với domain trong khoảng sẽ có các trọng số khác nhau, ảnh hưởng khác nhau đối với các thuật toán, các phương pháp được lựa chọn.
- Bước 4: đánh giá mô hình Việc lựa chọn và cài đặt các kỹ thuật khai phá dữ liệu là nhiệm vụ chính ở bước này.
- Các kỹ thuật khai phá dữ liệu Trong phần 1.1 đã nêu mục tiêu của khai phá dữ liệu, ở đây sẽ trình bày một số phương pháp tiếp cận chính trong việc khai phá dữ liệu.
- Phương pháp xây dựng cây quyết định (dùng trong phân lớp dữ liệu – classification.
- Mô hình mạng Nơron nhân tạo (dùng trong phương pháp hồi quy) 10 • Phương pháp phân vùng dữ liệu • Mô hình xác suất Bayes (dùng trong mô hình hoá các phụ thuộc - dependency modeling.
- Phương pháp xây dựng cây quyết định Cây quyết định là một công cụ rất phổ biến trong việc ứng dụng để phân lớp dữ liệu (classification).
- Thông thường các phương pháp xây dựng cây quyết định là luyện có giám sát (supervised learning ) dựa trên một tập mẫu vào-ra (input-output).
- Các phương pháp này thường tiến hành tìm kiếm theo chiến thuật trên-xuống (top-down) để lấy ra lời giải trong một phần không gian tìm kiếm.
- Một cây quyết định bao gồm nhiều nút (nơi kiểm tra các thuộc tính).
- Một cây quyết định đơn giản để phân loại mẫu với hai thuộc tính vào X và Y được mô tả như dưới đây.
- Hình 1.2 Ví dụ cây quyết định đơn giản với 2 thuộc tính 11 Và như vậy mỗi nút con (của mỗi nhánh đó) là một tập con tương ứng với phân hoạch này.
- Một thuộc tính được chọn để tiến hành phân hoạch toàn bộ mẫu.
- Với mỗi giá trị của thuộc tính, một nhánh cây được xây dựng và mỗi tập con của tập mẫu mà có cùng giá trị của thuộc tính này sẽ được chuyển đến nút tương ứng vừa được tạo nên cuối mỗi nhánh này.
- Vấn đề quan trọng của thuật toán là chọn thuộc tính nào tại mỗi nút.
- Việc chọn thuộc tính trong ID3 sẽ dựa trên việc cực tiểu độ đo Entropy thông tin.
- Trong ID3 việc chọn thuộc tính nào là dựa trên giả thiết là độ phức tạp của cây quyết định liên quan mạnh đến lượng thông tin mang lại bởi giá trị của thuộc tính đã cho.
- Trên cơ sở đó người ta thấy rằng việc chọn thuộc tính A tại một nút nào đó phải làm cực đại hàm Gain(a,S) được định nghĩa như sau avaluesvvvSEntropySSSEntropySagain (1.1) Trong đó.
- tập các giá trị có thể có của thuộc tính A trong tập dữ liệu S (là tập mẫu con tại nút đang xét.
- Ta có thể coi p(A.
- function ID3 input: R: tập các thuộc tính không phải là các thuộc tính mục tiêu (còn gọi là thuộc tính vào – input attribute) C: tập các thuộc tính mục tiêu (còn gọilà thuộc tính ra – output attribute) S: tập dữ liệu mẫu cần được phân chia thành các lớp bởi cây quyết định output.
- Cây quyết định BEGIN (1) IF S = {rỗng} THEN return {cây với 1 nút đơn có giá trị = Failure}.
- (2) IF S chứa các bản ghi với các thuộc tính mục tiêu Ci có cùng một giá trị như nhau A THEN return {cây với 1 nút đơn có giá trị = giá trị A}.
- 13 (3) IF R = {rỗng} THEN return {cây với 1 nút đơn có giá trị = giá trị xuất hiện với tần số lớn nhất trong các giá trị quan sát ở các thuộc tính C của các bản ghi của S.
- Trong trường hợp này, có thể dữ liệu sẽ không được phân lớp.
- SaGainSAGainRa Giả sử tiếp: {aj | j = 1,2,..,m} là các giá trị của thuộc tính A.
- (6) Với mỗi j=1,2,..,m, {Sj là tập các bản ghi trong S sao cho thuộc tính A của bản ghi đó có giá trị = aj.
- Thuật toán ID3 duyệt qua tất cả các thuộc tính của tập dữ liệu mẫu S sau đó tìm ra các thuộc tính thích hợp nhất dùng để phân lớp tập dữ liệu mẫu S.
- Nếu thuộc tính A được chọn ra phân lớp S một cách tốt rồi thì thuật toán sẽ dừng lại, trái lại, thuật toán sẽ duyệt đệ quy trên m-tập con của tập dữ liệu S (m bằng các giá trị có thể có của thuộc tính A) để tìm các thuộc tính tốt hơn cho việc phân lớp tiếp theo.
- Với giải thuật ID3 trình bày ở trên, có thể mở rộng các nhánh cây quyết định đến một mức thích hợp để phân lớp tập dữ liệu mẫu S.
- Vấn đề tiếp theo của giải thuật ID3 đó là chúng ta phải rời rạc hoá miền giá trị của các thuộc tính.
- Ngoài ra, không phải lúc nào giá trị của các thuộc tính cũng được xác định rõ.
- Và khi đó việc tính giá trị của hàm Entropy(S) sẽ gặp phải khó khăn.
- Vấn đề thiếu giá trị của thuộc tính có thể được giải quyết bằng cách gán các giá trị bị thiếu đó bằng giá trị xuất hiện với tần số nhiều nhất hoặc có thể coi giá trị thiếu đó bằng NULL và gán một xác suất cho việc giá trị NULL đó xảy ra.
- Các luật (quy tắc) được tạo ra khi phân lớp dễ hiểu đối với người sử dụng • Công việc tính toán không nhiều • Chỉ rõ thuộc tính nào là quan trọng nhất đối với việc phân lớp.
- Một nơron nhân tạo có thể coi là mô hình đơn giản của nơron sinh học có 4 phần: đầu vào, bộ tổng, hàm truyền, đầu ra.
- 15 Hình 1.3 Mô hình một nơron nhân tạo Mỗi đầu vào xi được gắn với một hệ số nhân w.
- Bộ tổng tính tổng các đầu vào của nơron với các trọng số và thêm hệ số ngưỡng để tạo ra giá trị n (net input).
- Đầu tiên là các giá trị đưa vào cho lớp thứ nhất (input

Xem thử không khả dụng, vui lòng xem tại trang nguồn
hoặc xem Tóm tắt