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

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 tôi đề 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. Đặ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ư: 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. 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 hoặc 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. 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 hoặc 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, dự đ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]: Knowledge Pattern Discovery Transformed Data Cleansed Preprocessed Preparated Data Target Data Gathering Data Mining Selection Transformation Cleansing Pre-processing Preparation Envalution of Rule Internet,... 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 hoặc 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 hoặc 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 phải ư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. 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: 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 hoặc bằng minsup. 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 hoặc bằng mincof. [1] 3.2 Tính ứng dụng Luật kết hợp có ứng dụng trong nhiều lĩnh vực khác nhau của đời sống như: khoa học, hoạt động kinh doanh, tiếp thị, thương mại, phân tích thị trường chứng khoán, tài chính và đầu tư,... Ứng dụng luật kết hợp phải chỉ rõ các đặc điểm về: nguồn gốc, điều kiện áp dụng, phạm vi ứng dụng, mục đích ứng dụng. Những đặc điểm này được thể hiện bằng mô hình sau: Yêu cầu sử dụng Tham chiếu tập luật R Lựa chọn luật Ứng dụng Hình 2. Mô hình ứng dụng luật Trong đó: Yêu cầu sử dụng là phạm vi tính ứng dụng của tập luật ví dụ như về khoa học, kinh doanh, tiếp thị, thương mại, phân tích thi trường chứng khoán,..v.v. Tham chiếu đến tập luật R, ở giai đoạn này các tập luật được tham chiếu tại đây là các tập luật được sinh ra từ cơ sở dữ liệu chứa tác nhân yêu cầu sử dụng. Lựa chọn luật, ở bước này chúng ta tiến hành lọc các luật hữu ích nhất phục vụ cho phạm vi sử dụng. Ứng dụng, đây là kết quả mong đợi nhất từ khi bắt đầu khai thác cho đến khi thi hành luật. Mô hình ứng dụng luật đã làm sáng tỏ tính ứng dụng của việc khai thác luật kết hợp trong cơ sở dữ liệu. Thực tế, ứng dụng của khai thác luật kết hợp trong cơ sở dữ liệu giao dịch là một phạm trù của DataMining nên ứng dụng của nó rất rộng lớn, nhất là trong sự phát triển của xã hội hiện nay. Tóm lại, 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 là việc ứng dụng các tập luật tìm thấy trong đó nhằm vào những mục đích cụ thể và đạt được kết quả tốt. Phát triển giải pháp hiệu quả tính ứng dụng Để phát triển giải pháp hiệu quả tính ứng dụng trong cơ sở dữ liệu giao dịch thì trước hết chúng ta phải phát triển giải pháp hiệu quả trong khai thác luật kết hợp. Thực vậy, ứng dụng có kết quả tốt chỉ khi luật khai thác được có giá trị và vận dụng thi hành đúng mục đích. 4.1 Phát triển giải pháp hiệu quả trong khai thác luật kết hợp Bài toán luật kết hợp Cho một tập các giá trị I, một cơ sở dữ liệu giao dịch D, ngưỡng độ hỗ trợ tối thiểu minsup, ngưỡng độ tin cậy mincof, tìm các luật kết hợp dạng X Y trên D thoả mãn điều kiện Support(X Y) >= minsup và Confidence(X Y) >= mincof. Tiến trình khai thác luật kết hợp Xác định các tập mục lớn Việc xác định các tập mục lớn gồm có hai bước chính sau đây: Xác định các tập ứng cử viên (Ck). Xác định các tập mục lớn (L) dựa vào tập ứng cử viên Để xác định tập ứng cử viên, ta thực hiện các bước sau đây: Tìm các tập ứng cử viên một mục. Quét CSDL D để xác định độ hỗ trợ của các tập ứng cử viên. Trong vòng đầu tiên, các tập ứng cử viên cũng chính là tất cả các mục có trong CSDL. Tại vòng thứ k (k>1), các tập ứng cử viên được xác định dựa vào các tập mục lớn đã xác định tại vòng k – 1, sử dụng hàm Apriori-gen() [2,3,7]. Sau khi đã xác định được các tập ứng cử viên, thuật toán quét từng giao dịch trong CSDL để tính độ hỗ trợ của các tập ứng cử viên. Quá trình xác định các tập mục sẽ kết thúc khi không xác định được thêm tập mục lớn nào nữa. Nội dung hàm Apriori-gen(). Hàm Apriori-gen() thực hiện hai bước [2]: Bước đầu tiên, Lk – 1 được kết nối với chính nó thu được Ck. Bước thứ hai, Apriori_gen() xoá tất cả các tập mục từ kết quả kết nối mà có một số tập con (k – 1) không có trong Lk – 1. Sau đó nó trả về tập mục lớn kích thước k còn lại. Sinh các luật kết hợp từ tập mục lớn: Việc phát hiện các tập mục lớn là rất tốn kém về mặt tính toán. Tuy nhiên, ngay khi tìm được tất cả các tập mục lớn (l L), ta có thể dễ dàng sinh ra các luật kết hợp có thể có bằng các bước như sau: Tìm tất cả các tập con không rỗng x, của tập mục lớn l L. Với mỗi tập con x tìm được, ta xuất ra luật dạng x (l - x) nếu tỷ lệ Support(l)/Support(x)>= mincof ( %). Thủ tục sinh ra các tập con. Đầu vào: Tập mục lớn Lk Đầu ra: Tập luật thoả mãn điều kiện độ tin cậy >=mincof và độ hỗ trợ >=minsup Phương pháp: Forall Lk, k>=2 do Call Genrules(Lk, Lk); Procedure Genrules(Lk: large k-itemset, am: large m-itemset) A={(m-1)-itemset am-1| am-1am} Forall am-1A do begin Conf = Support(Lk)/Support(am-1) If (Conf >= mincof) then begin Output the rule am-1(Lk – am-1) với confidence = mincof and support = support(Lk) If (m-1>1) then Call Genrules(Lk,am-1); End; End; Giải pháp hiệu quả Trong các phần trên, đã trình bày tiến trình cơ bản để khai thác các luật kết hợp trong CSDL, song vấn đề cần phải quan tâm nghiên cứu là tăng hiệu quả của thuật toán trong trường hợp: “ Số lượng tập ứng cử viên được tìm thấy là rất lớn” Trong phạm vi nghiên cứu của bài này, sẽ đưa ra một giải pháp mới để giải quyết vấn đề đã nêu. Tỉa các ứng cử viên: Việc tỉa các ứng cử viên nhằm mục đích bỏ đi các tập ứng cử viên không cần thiết, rút gọn số lượng của tập các tập ứng cử viên. Sau đây, sẽ trình bày kỹ thuật “tỉa” các ứng cử viên không cần thiết. Kỹ thuật này có tinh chất: Các mục trong tập ứng cử viên được sắp xếp theo thứ tự. Nội dung kỹ thuật: Forall itesets c Ck do Forall (k – 1)–subsets s of c do If (s Lk – 1) then Delete c from Ck Dựa vào đây, ta có thể tỉa được các tập ứng cử viên, từ đó có thể giới hạn miền tìm kiếm của nó trên tất cả các tập mục. 4.2 Phát triển giải pháp hiệu quả tính ứng dụng Trong phần 4.1, đã trình bày tiến trình khai phá luật kết hợp và giải pháp hiệu quả cho việc tạo ra các luật kết hợp. Tuy đã giảm được một số lượng rất lớn các luật không mong muốn, song một vấn đề nẩy sinh vẫn phải tiếp tục nghiên cứu nhằm tăng hiệu quả sử dụng kết quả khai thác đó là: Khi tồn tại tập luật dạng X Y có độ tin cậy (ck) thì luôn tồn tại tập luật dạng Y X có độ tin cậy (ck+1). Như vậy, luật dạng Y X thường không cần thiết vì người sử dụng đã ngầm hiểu. Cách thức vận dụng tập luật chưa rõ.[4,5,6] Trong phạm vi nghiên cứu này, chúng tôi đưa ra một giải pháp mới để giải quyết hai vấn đề nêu trên. Tỉa tập luật dạng Y X Việc tỉa các tập luật dạng Y X nhằm mục đích bỏ đi các luật không có giá tri hoặc người sử dụng đã biết trước luật đó, đồng thời rút gọn được các tập luật. Kỹ thuật tỉa này sử dụng độ tin cậy của tập luật tìm thấy. Kết quả khai thác sinh ra tập luật thường được lưu trữ vào một cơ sở dữ liệu nào đó như Access, Excel, Paradox, v.v. Kỹ thuật tỉa nhằm loại bỏ các tập luật có độ tin cậy ck+1 < ck. Nội dung kỹ thuật: Forall rulsets r Ri do If ck < ck-1 then Delete r from Ri Căn cứ vào đây, chúng ta có thể tỉa các tập luật không mong muốn để giới hạn phạm vi tìm kiếm các tập luật nhằm tăng tính ứng dụng của nó một cách nhanh chóng trên những phạm vi ứng dụng khác nhau. Tối ưu hoá tính ứng dụng tập luật Để tối ưu hoá tính ứng dụng các tập luật (Ri), trình tự ứng dụng luật có thể mô tả theo các bước cơ bản như hình vẽ 3. Nhận và phân loại tập luật Xác nhận tính chất luật Vận dụng thi hành kết quả 1 2 3 Hình 3. Các bước cơ bản của ứng dụng luật. Bước 1 “Nhận và phân loại tập luật” sẽ lấy kết quả của quá trình khai thác luật kết hợp từ cơ sở dữ liệu giao dịch sau khi đã loại bỏ những luật không có giá trị, đồng thời tiến hành phân loại các luật này theo chủ đề (luật một mục, luật hai mục,...) và lưu vào cơ sở dữ liệu. Bước 2 “Xác định tính chất luật”, sau khi đã phân loại luật ta tiến hành xác định tính chất luật. Việc xác định này sẽ làm rõ mục đích ứng dụng luật trong giao dịch. Bước 3 “Vận dụng thi hành kết quả” cho ta biết cách thức thi hành luật trong giao dịch để kết hợp giữa mục nào sẽ thu được kết quả tốt. Bước này, nói lên ý nghĩa kết hợp các mục trên giao dịch có tính quan trọng như thế nào khi thực thi một kế hoạch hoạt động nào đó. Như vậy, mô hình các bước cơ bản của ứng dụng luật góp phần không nhỏ trong khi sử dụng luật nhằm giảm thời gian tìm kiếm và tăng khả năng thi hành luật. Việc xác định tính chất luật có tính quyết định hình thành kết hợp tập mục trong mỗi giao dịch. Vì thế, khai thác luật kết hợp được ứng dụng rất thành công trong cơ sở dữ liệu giao dịch. Một giải pháp mô phỏng việc tinh lọc, xem xét đặc điểm luật phục vụ cho ứng dụng được nghiên cứu và phản ảnh trong hình 4. Trong vòng lặp đầu tiên (k=n), tập luật được xác định tính chất là tập luật thứ n trong R (toàn bộ tập luật). Nội dung xác định tập luật gồm: “tiền đề”, “kết luận”, “độ tin cậy”, “độ hỗ trợ”. Tiếp theo kiểm tra tính chất luật này. Nếu luật kiểm tra thoả mãn chuẩn đề ra thì ghi nhận đặc tính sử dụng cho nó, ngược lại xoá luật ri ra khỏi R, lưu kết quả và thực hiện vòng lặp tiếp theo. Giải pháp kết thúc khi đã kiểm tra xong toàn bộ tập luật R. (k=0). Ghi nhận tính chất ứng dụng là một bước rất quan trọng quyết định tối ưu tính ứng dụng. Vì thế, trong bước này sẽ được xây dựng các “Chuẩn” đánh giá nghiêm ngặt. Chuẩn này dựa trên những nguyên tắc riêng, nhất định của phạm vi ứng dụng luật. Các hàm chuẩn này sẽ được tiến hành cài đặt và thử nghiệm trong môi trường cơ sở dữ liệu giao dịch. Thoả mãn(TM) Không TM Đúng k = n Bắt đầu Xem xét tính chất luật k = k - 1 Xác định tính chất mỗi luật trong toàn bộ tập luật Tỉa bỏ luật ri Ghi nhận tính chất ứng dụng Kết thúc k > 0 Sai Hình 4. Lưu đồ giải pháp mô phỏng xác nhận đặc điểm luật Kết quả giải pháp sẽ tăng tính ứng dụng của luật trong cơ sở dữ liệu giao dịch. Tập luật đã được xác nhận đặc tính sẽ có tính ứng dụng linh hoạt, chủ động hơn khi ứng dụng. Như vậy, 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 đề cập đến phạm vi ứng dụng luật kết hợp trên các giao dịch là rất quan trọng. Khai thác mối quan hệ giữa các mục trong phiên giao dịch sẽ là hữu ích khi chúng ta tiến hành khai thác một cách có thứ tự, có mục đích rõ ràng. Giải pháp này góp phần chỉ rõ hơn những thông tin có trong các phiên giao dich để từ đó giúp cho lãnh đạo có kế hoạch hoạt động, sản xuất kinh doanh trong các năm tiếp theo. 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 giải quyết tốt cách thức thi hành, ứng dụng thông tin quan trọng trên các phiên giao dịch. Dựa vào tính ứng dụng này có thể có giải pháp tốt đối với nền kinh tế thị trường hiện tại cũng như trong tương lai. Ví dụ minh hoạ khai thác - Ứng dụng luật Thực tế, hệ thống thu ngân tại Siêu Thị Đà Nẵng đã sử dụng công nghệ mã vạch để thanh toán cho khách hàng. Dữ liệu giao dịch mỗi khách hàng được lưu trữ trong phần mềm cơ sở dữ liệu của máy tính đặt tại các quầy thu ngân. Hiện nay dữ liệu này đã trở nên rất nhiều qua các phiên giao dịch, việc sử dụng DataMining để khai phá các dữ liệu hiện có là một việc rất cần thiết cho hoạt động kinh doanh trong Siêu Thị. Như vậy, nhiệm vụ của khai thác dữ liệu là phải tìm được mối liên hệ giữa các mặt hàng trong giao dịch đó. Mối quan hệ này có dạng X => Y, đây chính là các tri thức chiết xuất được trong khi khai thác với độ hỗ trợ cho trước (minsupt), độ tin cậy cho trước (minconf). Các tri thức chiết xuất được sẽ giúp cho hoạt động kinh doanh trong Siêu Thị được tốt hơn từ đó có thể hoạch định kế hoạch sản xuất kinh doanh trong những năm tiếp theo. Bảng 1 trình bày cơ sở dữ liệu các giao dịch tại quầy thu ngân của Siêu Thị. Bảng 1. Cơ sở dữ liệu giao dịch Sau khi đã xác định được các tập mục lớn và độ hỗ trợ, ta tiến hành sinh các luật kết hợp bằng cách sử dụng thủ tục sinh các tập con của tập mục lớn. Các luật kết hợp thu được trong trường hợp này bao gồm các luật dạng Y X như đã đề cập ở trên. Bảng 2 mô tả nội dung toàn bộ tập luật khai thác được trong cơ sở dữ liệu giao dịch với minsup =10% và mincof =30%. Các luật ở đây chỉ nói lên mối quan hệ giữa các mục trong các phiên giao dịch, chứ chưa đề cập đến tính ứng dụng của nó. Bảng 2 sau đây trình bày nội dung tập luật thu được trước khi tỉa. Bảng 2. Nội dung tập luật thu được trước khi tỉa Như vậy, kết quả khai thác cho thấy các luật thu được có dạng Y X và cách thức vận dụng các luật nào là chưa rõ. Các tri thức chiết xuất dạng này thường không cần thiết và gây nên lãng phí không gian nhớ. Ứng dụng giải pháp hiệu quả tính ứng dụng tỉa bỏ các luật dạng Y X, kết quả thu được chỉ còn các luật dạng X Y thể hiện trong bảng 3. Các tri thức thu được sau khi tỉa là các tri thức đáng tin cậy cho lãnh đạo. Bảng 3. Nội dung tập luật thu được sau khi tỉa Thực vậy, số lượng các luật thu được trong giải pháp này gồm các luật có giá trị cao. Đây cũng chính là những tri thức chiết xuất được trong quá trình khai thác. Vấn đề đặt ra là phải ứng dụng hiệu quả các luật này vào trong sản xuất kinh doanh cũng như cuộc sống dựa vào đặc điểm và tính chất ứng dụng luật ứng với mỗi luật trong tập luật. Để giải quyết vấn đề này ta sử dụng giải pháp tối ưu hoá tính ứng dụng luật. Việc sử dụng hàm đánh giá để xem xét về tiền đề, kết quả của luật đạt được trong tập luật, đây là một giai đoạn mang tính tư duy nhưng nó rất quan trọng khi ta ứng dụng trong thực tế. Từ khi xác định đến khi ghi nhận tính ứng dụng cho mỗi luật đây là quá trình tốn kém nhiều thời gian, song kết quả đạt được sẽ hữu ích cho lãnh đạo trong khi hoạch định kế hoạch sản xuất, kinh doanh trong thời gian sắp tới. Tính ứng dụng các tri thức chiết xuất được sẽ giúp cho lãnh đạo Siêu Thi trong việc bố trí, sắp xếp, kinh doanh những mặt hàng nào tại các quầy nào, tổ chức sắp sếp các quầy gần nhau như thế nào để có doanh thu trong các phiên giao dịch là lớn nhất. Ngoài ra, có thể áp dụng tri thức này để dự đoán số lượng các mặt hàng được bán chạy nhất trong thời gian sắp tới. Tổng hợp các tri thức này lãnh đạo có thể lên kế hoạch hoạt động, sản xuất, kinh doanh một cách thuận tiên hơn nhằm giảm bớt thời gian thống kê, tìm hiểu thị trường,v.v... Như vậy, 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 đã giải quyết được hai vấn đề tồn đọng đã nêu ở phần trên. Kết quả của khai thác sẽ được lưu trữ trong các cơ sở dữ liệu tri thức để phục vụ cho mục đích xây dựng các hệ chuyên gia về sau này. Kết luận Nội dung nghiên cứu trong đề tài, các tác giả đã đưa ra một giải pháp từ việc thu gom dữ liệu trên các phiên giao dịch, trên thương trường,... rồi tiến hành khai thác xử lý chúng để chiết xuất ra các tri thức cần thiết. Các tri thức cần thiết này lại được tối ưu hoá và đem vào sử dụng một cách hiệu quả trên các phiên giao dịch trong những lần tiếp theo. Đề tài đã đi sâu vào tính ứng dụng, đưa ra cách thức xử lý thi hành các tri thức được chiết xuất một cách hiệu quả. Nghiên cứu này đã đưa ra một cách nhìn tổng quan về quy trình khai phá dữ liệu từ các nguồn dữ liệu khác nhau đến việc ứng dụng các tri thức đã chiết xuất vào thực tế cuộc sống. Một ví dụ minh hoạ ứng dụng đã làm rõ cách nhìn này. Nghiên cứu thiên về tính ứng dụng trong cơ sở dữ liệu giao dịch, song việc nghiên cứu sẽ được tiếp tục phát triển trên các cơ sở dữ liệu khác nhằm mục đích tìm ra một quy luật ứng dụng cho các tri thức đã chiết xuất. TÀI LIỆU THAM KHẢO Rekesh Arawal, Ramakrishnan Srikant*; Fast Algorithms for Mining Association, IBM Almadem Research Center 650 Harry Road, San Jose, CA 95120. Rekesh Agrawal, Tomasz Imielinski, and Arun N.Swami; Mining Association Rules Between Sets of Items in Large Databases, Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data, pp. 207-216, Washington, D.C., May 1993. Ming-Syan Chen, Jiawei*, Philip S. Yu; Data Mining: An Overview from Database Perspective; Elect. Eng. Department National Taiwan Univ. IBM T.J. Watson Res. Ctr. P.O.Box 704 Yorktown, NY 10598, U.S.A. Anthony K.H. Tung1, Hongjun Lu2, Jiawei Han1, Ling Feng3; Breaking the Barrier of Transactions: Mining Tnter-Transaction Association Rules; 1Simon Fraser University, BritishvColumbia, Canada {khtung, han}@cs.sfu.ca; 2The Honh Kong University of Science an Technology, Hong Kong, China, luhj@cs.ust.hk; 3The Hong Kong Polytectnic University, Hong Kong, China. cslfeng@comp.polyu.edu.kh Karthich Rajamani, Alan Cox, Bala Iyer, Atul Chadla; Effcient Mining for Association Rules with Relational Database Systems; Dept. of Elec. And Comp. Engg., Rice University, karthich@rice.edu; Dept of Computer Science, Rice University, alc@rice.edu; IBM Santa Teresa Labs balaiyer@us.ibm.com; IBM Santa Teresa Labs achadha@us.ibm.com Byung-Hoon Park and Hillol Kargupta; Distributed Data Mining: Algoriths, Sestems… – Department of Computer Science and Electrical Engineering Universty of Margland Baltimore County 1000 Hillol Cricle Baltimore, MD 21250. Data Mining Algorithms Journal, 2002.