Download miễn phí luận văn
NGHIÊN CỨU TÍNH ỨNG DỤNG CỦA KHAI THÁC
LUẬT KẾT HỢP TRONG CƠ SỞ DỮ LIỆU GIAO DỊCH
RESEARCH ON THE APPLICATION OF ASSOCIATION RULES IN TRANSACTION DATABASE
TRƯƠNG NGỌC CHÂU – PHAN VĂN DŨNG
Trường Đại học Bách Khoa, Đại học Đà Nẵng
TÓM TẮT
Hiện tại, đã có một số ứng dụng kết quả của việc khai thác luật kết hợp trong cơ sở dữ liệu. Tuy nhiên, chưa có nhiều nghiên cứu nói lên tính ứng dụng của nó, các nghiên cứu chỉ mang tính đơn thể, tự phát và chưa có một giải pháp tổng quát nào vì phạm vi sử dụng kết quả của việc khai thác là rất đa dạng và phong phú. Trong bài báo này, chúng tui đề xuất một giải pháp tổng quát cho tính ứng dụng của việc khai thác luật kết hợp trong cơ sở dữ liệu giao dịch.
ABSTRACT
Currently, there have been application results of the utilization of the association rules in database. However, there have not been many studies on the practical applications because they are isolated and fail to put forward the overall solutions due to the diverse application areas of the research results. In this research, we propose a particular solution to utilize the association rules in transaction database.
1. Đặt vấn đề
Trong kỹ nguyên Internet, Intranets, Warehouses, đã mở ra nhiều cơ hội cho những nhà doanh nghiệp trong việc thu thập và xử lý thông tin. Hơn nữa, các công nghệ lưu trữ và phục hồi dữ liệu phát triển một cách nhanh chóng vì thế cơ sở dữ liệu ở các cơ quan, doanh nghiệp, đơn vị ngày càng nhiều thông tin tiềm ẩn phong phú và đa dạng.
Cơ sở dữ liệu trong các doanh nghiệp thì dữ liệu giao dịch đóng một vai trò rất quan trọng cho việc hoạch định kế hoạch kinh doanh trên thương trường vào những năm tiếp theo. Hiện tại, việc sử dụng các dữ liệu này tuy đã đạt được một số kết quả nhất định song vẫn còn một số vấn đề tồn đọng như:
1. Dựa hoàn toàn vào dữ liệu, không sử dụng tri thức có sẳn về lĩnh vực, kết quả phân tích khó có thể làm rõ được.
2. Phải có sự hướng dẫn của người dùng để xác định phân tích dữ liệu như thế nào và ở đâu.
Trong điều kiện và yêu cầu của thương trường, đòi hỏi phải có những phương pháp nhanh, phù hợp, tự động, chính xác và có hiệu quả để lấy được thông tin có giá trị. Các tri thức chiết xuất được từ cơ sở dữ liệu trên sẽ là một nguồn tài liệu hỗ trợ cho lãnh đạo trong việc lên kế hoạch hoạt động hay 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 giao dịch là một vấn đề đang được quan tâm đặc biệt trong bài viết này.
Mục đích của việc nghiên cứu là xây dựng một giải pháp hiệu quả tính ứng dụng luật kết hợp trong việc ra quyết định của cơ quan doanh nghiệp dựa trên cơ sở dữ liệu giao dịch.
2. Khai phá dữ liệu
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ỹ 1980. Nó là quá trình khám phá thông tin ẩn được tìm thấy trong các cơ sở dữ liệu và có thể xem như là một bước trong quá trình khám phá tri thức. Data Mining là giai đoạn quan trọng nhất trong tiến trình khai phá tri thức từ cơ sở dữ liệu, các tri thức này hỗ trợ trong việc ra quyết định trong khoa học và kinh doanh.
Để hình dung vấn đề này ta có thể sử dụng một ví dụ đơn giản như sau: Khai phá dữ liệu được ví như tìm một cây kim trong đống cỏ khô. Trong ví dụ này, cây kim là một mảnh nhỏ tri thức hay một thông tin có giá trị và đống cỏ khô là một kho cơ sở dữ liệu rộng lớn. Như vậy, những thông tin có giá trị tiềm ẩn trong kho cơ sở dữ liệu sẽ được chiết xuất ra và sử dụng một cách hữu ích nhờ khai phá dữ liệu. Chức năng khai phá dữ liệu gồm có gộp nhóm phân loại, dự báo, đoán và phân tích các liên kết. Năm 1989 Fayyad, Smyth và Piatestsky-Shapiro đã dùng khái niệm Phát hiện tri thức từ cơ sở dữ liệu (Knowledge Discovery in Database-KDD). Trong đó, khai phá dữ liệu là một giai đoạn rất đặc biệt trong toàn bộ quá trình, nó sử dụng các kỹ thuật để tìm ra các mẫu từ dữ liệu.
Quá trình khai phá dữ liệu sẽ tiến hành qua 6 giai đoạn như hình 1[8]:
Hình 1. Quá trình khai phá dữ liệu
Bắt đầu của quá trình là kho dữ liệu thô và kết thúc với tri thức được chiết xuất ra. Về lý thuyết thì có vẽ rất đơn giản nhưng thực sự đây là một quá trình rất khó khăn gặp phải rất nhiều vướng mắc như: quản lý các tập dữ liệu, phải lặp đi lặp lại toàn bộ quá trình,.v.v.
2.1 Gom dữ liệu (Gathering)
Tập hợp dữ liệu là bước đầu tiên trong quá trình khai phá dữ liệu. Đây là bước được khai thác trong một cơ sở dữ liệu, một kho dữ liệu và thậm chí các dữ liệu từ các nguồn ứng dụng Web.
2.2 Trích lọc dữ liệu (Selection)
Ở giai đoạn này dữ liệu được lựa chọn hay phân chia theo một số tiêu chuẩn nào đó, ví dụ chọn tất cả những người có tuổi đời từ 25 – 35 và có trình độ đại học.
2.3 Làm sạch, tiền xử lý và chuẩn bị trước dữ liệu (Cleansing, Pre-processing and Preparation)
Giai đoan thứ ba này là giai đoạn hay bị sao lãng, nhưng thực tế nó là một bước rất quan trọng trong quá trình khai phá dữ liệu. Một số lỗi thường mắc phải trong khi gom dữ liệu là tính không đủ chặt chẻ, logíc. Vì vậy, dữ liệu thường chứa các giá trị vô nghĩa và không có khả năng kết nối dữ liệu. Ví dụ: tuổi = 673. Giai đoạn này sẽ tiến hành xử lý những dạng dữ liệu không chặt chẽ nói trên. Những dữ liệu dạng này được xem như thông tin dư thừa, không có giá trị. Bởi vậy, đây là một quá trình rất quan trọng vì dữ liệu này nếu không được “làm sạch - tiền xử lý - chuẩn bị trước” thì sẽ gây nên những kết quả sai lệch nghiêm trọng.
2.4 Chuyển đổi dữ liệu (Transformation)
Tiếp theo là giai đoạn chuyển đổi dữ liệu, dữ liệu đưa ra có thể sử dụng và điều khiển được bởi việc tổ chức lại nó. Dữ liệu đã được chuyển đổi phù hợp với mục đích khai thác.
2.5 Phát hiện và trích mẫu dữ liệu (Pattern Extraction and Discovery)
Đây là bước mang tính tư duy trong khai phá dữ liệu. Ở giai đoạn này nhiều thuật toán khác nhau đã được sử dụng để trích ra các mẫu từ dữ liệu. Thuật toán thường dùng là nguyên tắc phân loại, nguyên tắc kết hợp hay các mô hình dữ liệu tuần tự,. v.v.
2.6 Đánh giá kết quả mẫu (Evaluation of Result)
Đây là giai đoạn cuối trong quá trình khai phá dữ liệu. Ở giai đoạn này, các mẫu dữ liệu được chiết xuất ra bởi phần mềm khai phá dữ liệu. Không phải bất cứ mẫu dữ liệu nào cũng đều hữu ích, đôi khi nó còn bị sai lệch. Vì vậy, cần ưu tiên những tiêu chuẩn đánh giá để chiết xuất ra các tri thức (Knowlege) cần chiết xuất ra.
Trên đây là 6 giai đoạn trong quá trình khai phá dữ liệu, trong đó giai đoạn 5 là giai đoạn được quan tâm nhiều nhất hay còn gọi đó là Data Mining.
3. Luật kết hợp trong cơ sở dữ liệu – tính ứng dụng
3.1 Luật kết hợp trong cơ sở dữ liệu
Gọi I = {I1, I2,..., Im} là tập m thuộc tính riêng biệt, mỗi thuộc tính gọi là một mục. Gọi D là một cơ sở dữ liệu, trong đó mỗi bản ghi T là một giao dịch và chứa các tập mục, T I.
Định nghĩa 1: Một luật kết hợp là một quan hệ có dạng X Y, trong đó X, Y I là các tập mục gọi là itemsets, và . Ở đây, X được gọi là tiền đề, Y là mệnh đề kết quả.
Hai thông số quan trọng của luật kết hợp là độ hỗ trợ (s) và độ tin cậy (c).
Định nghĩa 2: Độ hỗ trợ (support) của luật kết hợp X Y là tỷ lệ phần trăm các bản ghi với tổng số các giao dịch có trong cơ sở dữ liệu.
Định nghĩa 3: Đối với một số giao dịch được đưa ra, độ tin cậy (confidence) là tỷ lệ của số giao dịch có chứa với số giao dịch có chứa X. Đơn vị tính %.
Việc khai thác các luật kết hợp từ cơ sở dữ liệu chính là việc tìm tất cả các luật có độ hỗ trợ và độ tin cậy lớn hơn ngưỡng của độ hỗ trợ và độ tin cậy do người sử dụng xác định trước. Các ngưỡng của độ hỗ trợ và độ tin cậy được ký hiệu là minsup và mincof.
Việc khai thác các luật kết hợp có thể được phân tích thành hai vấn đề sau đây:
1. Tìm tất cả các tập mục thường xuyên xảy ra mà có độ hỗ trợ lớn hơn hay bằng minsup.
2. Tạo ra các luật mong muốn sử dụng các tập mục lớn mà có độ tin cậy lớn hơn hay bằng mincof. [1]
Do Drive thay đổi chính sách, nên một số link cũ yêu cầu duyệt download. các bạn chỉ cần làm theo hướng dẫn.
Password giải nén nếu cần: ket-noi.com | Bấm trực tiếp vào Link để tải:
NGHIÊN CỨU TÍNH ỨNG DỤNG CỦA KHAI THÁC
LUẬT KẾT HỢP TRONG CƠ SỞ DỮ LIỆU GIAO DỊCH
RESEARCH ON THE APPLICATION OF ASSOCIATION RULES IN TRANSACTION DATABASE
TRƯƠNG NGỌC CHÂU – PHAN VĂN DŨNG
Trường Đại học Bách Khoa, Đại học Đà Nẵng
TÓM TẮT
Hiện tại, đã có một số ứng dụng kết quả của việc khai thác luật kết hợp trong cơ sở dữ liệu. Tuy nhiên, chưa có nhiều nghiên cứu nói lên tính ứng dụng của nó, các nghiên cứu chỉ mang tính đơn thể, tự phát và chưa có một giải pháp tổng quát nào vì phạm vi sử dụng kết quả của việc khai thác là rất đa dạng và phong phú. Trong bài báo này, chúng tui đề xuất một giải pháp tổng quát cho tính ứng dụng của việc khai thác luật kết hợp trong cơ sở dữ liệu giao dịch.
ABSTRACT
Currently, there have been application results of the utilization of the association rules in database. However, there have not been many studies on the practical applications because they are isolated and fail to put forward the overall solutions due to the diverse application areas of the research results. In this research, we propose a particular solution to utilize the association rules in transaction database.
1. Đặt vấn đề
Trong kỹ nguyên Internet, Intranets, Warehouses, đã mở ra nhiều cơ hội cho những nhà doanh nghiệp trong việc thu thập và xử lý thông tin. Hơn nữa, các công nghệ lưu trữ và phục hồi dữ liệu phát triển một cách nhanh chóng vì thế cơ sở dữ liệu ở các cơ quan, doanh nghiệp, đơn vị ngày càng nhiều thông tin tiềm ẩn phong phú và đa dạng.
Cơ sở dữ liệu trong các doanh nghiệp thì dữ liệu giao dịch đóng một vai trò rất quan trọng cho việc hoạch định kế hoạch kinh doanh trên thương trường vào những năm tiếp theo. Hiện tại, việc sử dụng các dữ liệu này tuy đã đạt được một số kết quả nhất định song vẫn còn một số vấn đề tồn đọng như:
1. Dựa hoàn toàn vào dữ liệu, không sử dụng tri thức có sẳn về lĩnh vực, kết quả phân tích khó có thể làm rõ được.
2. Phải có sự hướng dẫn của người dùng để xác định phân tích dữ liệu như thế nào và ở đâu.
Trong điều kiện và yêu cầu của thương trường, đòi hỏi phải có những phương pháp nhanh, phù hợp, tự động, chính xác và có hiệu quả để lấy được thông tin có giá trị. Các tri thức chiết xuất được từ cơ sở dữ liệu trên sẽ là một nguồn tài liệu hỗ trợ cho lãnh đạo trong việc lên kế hoạch hoạt động hay 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 giao dịch là một vấn đề đang được quan tâm đặc biệt trong bài viết này.
Mục đích của việc nghiên cứu là xây dựng một giải pháp hiệu quả tính ứng dụng luật kết hợp trong việc ra quyết định của cơ quan doanh nghiệp dựa trên cơ sở dữ liệu giao dịch.
2. Khai phá dữ liệu
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ỹ 1980. Nó là quá trình khám phá thông tin ẩn được tìm thấy trong các cơ sở dữ liệu và có thể xem như là một bước trong quá trình khám phá tri thức. Data Mining là giai đoạn quan trọng nhất trong tiến trình khai phá tri thức từ cơ sở dữ liệu, các tri thức này hỗ trợ trong việc ra quyết định trong khoa học và kinh doanh.
Để hình dung vấn đề này ta có thể sử dụng một ví dụ đơn giản như sau: Khai phá dữ liệu được ví như tìm một cây kim trong đống cỏ khô. Trong ví dụ này, cây kim là một mảnh nhỏ tri thức hay một thông tin có giá trị và đống cỏ khô là một kho cơ sở dữ liệu rộng lớn. Như vậy, những thông tin có giá trị tiềm ẩn trong kho cơ sở dữ liệu sẽ được chiết xuất ra và sử dụng một cách hữu ích nhờ khai phá dữ liệu. Chức năng khai phá dữ liệu gồm có gộp nhóm phân loại, dự báo, đoán và phân tích các liên kết. Năm 1989 Fayyad, Smyth và Piatestsky-Shapiro đã dùng khái niệm Phát hiện tri thức từ cơ sở dữ liệu (Knowledge Discovery in Database-KDD). Trong đó, khai phá dữ liệu là một giai đoạn rất đặc biệt trong toàn bộ quá trình, nó sử dụng các kỹ thuật để tìm ra các mẫu từ dữ liệu.
Quá trình khai phá dữ liệu sẽ tiến hành qua 6 giai đoạn như hình 1[8]:
Hình 1. Quá trình khai phá dữ liệu
Bắt đầu của quá trình là kho dữ liệu thô và kết thúc với tri thức được chiết xuất ra. Về lý thuyết thì có vẽ rất đơn giản nhưng thực sự đây là một quá trình rất khó khăn gặp phải rất nhiều vướng mắc như: quản lý các tập dữ liệu, phải lặp đi lặp lại toàn bộ quá trình,.v.v.
2.1 Gom dữ liệu (Gathering)
Tập hợp dữ liệu là bước đầu tiên trong quá trình khai phá dữ liệu. Đây là bước được khai thác trong một cơ sở dữ liệu, một kho dữ liệu và thậm chí các dữ liệu từ các nguồn ứng dụng Web.
2.2 Trích lọc dữ liệu (Selection)
Ở giai đoạn này dữ liệu được lựa chọn hay phân chia theo một số tiêu chuẩn nào đó, ví dụ chọn tất cả những người có tuổi đời từ 25 – 35 và có trình độ đại học.
2.3 Làm sạch, tiền xử lý và chuẩn bị trước dữ liệu (Cleansing, Pre-processing and Preparation)
Giai đoan thứ ba này là giai đoạn hay bị sao lãng, nhưng thực tế nó là một bước rất quan trọng trong quá trình khai phá dữ liệu. Một số lỗi thường mắc phải trong khi gom dữ liệu là tính không đủ chặt chẻ, logíc. Vì vậy, dữ liệu thường chứa các giá trị vô nghĩa và không có khả năng kết nối dữ liệu. Ví dụ: tuổi = 673. Giai đoạn này sẽ tiến hành xử lý những dạng dữ liệu không chặt chẽ nói trên. Những dữ liệu dạng này được xem như thông tin dư thừa, không có giá trị. Bởi vậy, đây là một quá trình rất quan trọng vì dữ liệu này nếu không được “làm sạch - tiền xử lý - chuẩn bị trước” thì sẽ gây nên những kết quả sai lệch nghiêm trọng.
2.4 Chuyển đổi dữ liệu (Transformation)
Tiếp theo là giai đoạn chuyển đổi dữ liệu, dữ liệu đưa ra có thể sử dụng và điều khiển được bởi việc tổ chức lại nó. Dữ liệu đã được chuyển đổi phù hợp với mục đích khai thác.
2.5 Phát hiện và trích mẫu dữ liệu (Pattern Extraction and Discovery)
Đây là bước mang tính tư duy trong khai phá dữ liệu. Ở giai đoạn này nhiều thuật toán khác nhau đã được sử dụng để trích ra các mẫu từ dữ liệu. Thuật toán thường dùng là nguyên tắc phân loại, nguyên tắc kết hợp hay các mô hình dữ liệu tuần tự,. v.v.
2.6 Đánh giá kết quả mẫu (Evaluation of Result)
Đây là giai đoạn cuối trong quá trình khai phá dữ liệu. Ở giai đoạn này, các mẫu dữ liệu được chiết xuất ra bởi phần mềm khai phá dữ liệu. Không phải bất cứ mẫu dữ liệu nào cũng đều hữu ích, đôi khi nó còn bị sai lệch. Vì vậy, cần ưu tiên những tiêu chuẩn đánh giá để chiết xuất ra các tri thức (Knowlege) cần chiết xuất ra.
Trên đây là 6 giai đoạn trong quá trình khai phá dữ liệu, trong đó giai đoạn 5 là giai đoạn được quan tâm nhiều nhất hay còn gọi đó là Data Mining.
3. Luật kết hợp trong cơ sở dữ liệu – tính ứng dụng
3.1 Luật kết hợp trong cơ sở dữ liệu
Gọi I = {I1, I2,..., Im} là tập m thuộc tính riêng biệt, mỗi thuộc tính gọi là một mục. Gọi D là một cơ sở dữ liệu, trong đó mỗi bản ghi T là một giao dịch và chứa các tập mục, T I.
Định nghĩa 1: Một luật kết hợp là một quan hệ có dạng X Y, trong đó X, Y I là các tập mục gọi là itemsets, và . Ở đây, X được gọi là tiền đề, Y là mệnh đề kết quả.
Hai thông số quan trọng của luật kết hợp là độ hỗ trợ (s) và độ tin cậy (c).
Định nghĩa 2: Độ hỗ trợ (support) của luật kết hợp X Y là tỷ lệ phần trăm các bản ghi với tổng số các giao dịch có trong cơ sở dữ liệu.
Định nghĩa 3: Đối với một số giao dịch được đưa ra, độ tin cậy (confidence) là tỷ lệ của số giao dịch có chứa với số giao dịch có chứa X. Đơn vị tính %.
Việc khai thác các luật kết hợp từ cơ sở dữ liệu chính là việc tìm tất cả các luật có độ hỗ trợ và độ tin cậy lớn hơn ngưỡng của độ hỗ trợ và độ tin cậy do người sử dụng xác định trước. Các ngưỡng của độ hỗ trợ và độ tin cậy được ký hiệu là minsup và mincof.
Việc khai thác các luật kết hợp có thể được phân tích thành hai vấn đề sau đây:
1. Tìm tất cả các tập mục thường xuyên xảy ra mà có độ hỗ trợ lớn hơn hay bằng minsup.
2. Tạo ra các luật mong muốn sử dụng các tập mục lớn mà có độ tin cậy lớn hơn hay bằng mincof. [1]
Do Drive thay đổi chính sách, nên một số link cũ yêu cầu duyệt download. các bạn chỉ cần làm theo hướng dẫn.
Password giải nén nếu cần: ket-noi.com | Bấm trực tiếp vào Link để tải:
You must be registered for see links