đặt vấn đề, mục tiêu của đề tài, giới hạn của đề tài, tổng kết chương. Chương 2: Tổng quan về lĩnh vực nghiên cứu, nêu các khái niệm, định nghĩa, cơ sở khoa học, các công trình nghiên cứu liên quan, các phương pháp nghiên cứu và nhận xét ưu khuyết điểm của các phương pháp. Chương 3: Đề xuất phương pháp khai thác Top-rank-k tập phổ biến được đánh trọng. Chương 4: Trình bày về thực nghiệm bao gồm môi trường thực nghiệm, cơ sở dữ liệu thực nghiêm, đánh giá các kết quả thu được.
Chương 5: Trình bày các kết quả đạt được của luận văn, nhận xét ưu khuyết điểm và hướng phát triển của đề tài. 3 CHƯƠNG 2: TỔNG QUAN CÁC LĨNH VỰC NGHIÊN CỨU VÀ CƠ SỞ LÝ THUYẾT 2. Các khái niệm, định nghĩa Khai thác dữ liệu là một công cụ giúp khai thác những thông tin hữu ích từ những kho dữ liệu được tích trữ trong suốt quá trình hoạt động của một công ty, tổ chức nào đó. Khai thác dữ liệu được dùng để mô tả quá trình tìm kiếm, chắt lọc và khai phá tri thức trong cơ sở dữ liệu hay chỉ việc tìm kiếm một tập hợp nhỏ có giá trị từ một số lượng lớn các dữ liệu thô.
Quá trình này bao gồm tập hợp nhiều kỹ thuật được sử dụng trong tiến trình khám phá tri thức để tự động khai thác và chỉ ra sự khác biệt giữa các mối quan hệ và các mẫu chưa biết bên trong dữ liệu. Khai thác luật kết hợp là một phần quan trọng trong quá trình khám phá tri thức trong dữ liệu (KDD) [2]. Khai thác luật kết hợp được sử dụng để xác định mối quan hệ giữa các sản phẩm trong cơ sở dữ liệu giao dịch và điều này dẫn đến việc nó chỉ quan tâm đến việc khách hàng có mua hay không mua sản phẩm nào đó. Thực tế, mỗi một sản phẩm có thể có giá trị khác nhau.
Tương tự mỗi item trong cơ sở dữ liệu giao dịch cũng có trọng số khác nhau tùy thuộc từng cơ sở dữ liệu cụ thể. Vì vậy việc khai thác trên loại dữ liệu này mang tính thực tiễn cao. Năm 1998, Ramkumar, Ranka và Tsur [4] cũng như Cai, Fu, Cheng và Kwong [3] đã đề xuất một mô hình để mô tả các khái niệm về việc khai thác luật kết hợp có trọng số và dựa trên giải thuật Apriori để tìm ra các tập phổ biến được đánh trọng. Từ đó nhiều kỹ thuật khai thác luật kết hợp có trọng số được đề xuất như: Wang, Yang, và Yu [6] và Tao, Murtagh, và Farid [5].
Tổng quan về khai thác luật kết hợp Trong lĩnh vực khai thác dữ liệu, mục đích của luật kết hợp (Association Rule - AR) là tìm ra các mối quan hệ giữa các đối tượng trong khối lượng lớn dữ liệu. Nội dung cơ bản của luật kết hợp được tóm tắt như dưới đây. Cho cơ sở dữ liệu gồm các giao dịch T là tập các giao dịchT = {t1, t2, …, tn}. Cho I = {i1,i2,…,im} là một tập các item.
Mỗi tập con trong I được gọi một itemset, số lượng các phần tử trong một itemset được gọi là kích thước của một itemset. 4 Mục đích của luật kết hợp là tìm ra sự kết hợp (association) hay tương quan (correlation) giữa các items. Cho X, Y là các itemset, trong đó X và Y là hai tập không giao nhau khác rỗng. Một luật kết hợp được ký hiệu là ⟶ , thể hiện mối ràng buộc của tập Y với tập X theo nghĩa là sự xuất hiện của tập X sẽ kéo theo sự xuất hiện của tập Y trong các giao dịch, có thể hiểu rằng những người mua các mặt hàng trong tập X cũng thường mua các mặt hàng trong tập Y.
Ví dụ, nếu X = {Táo, Chuối} và Y = {Anh Đào, Sầu Riêng} và ta có luật kết hợp XY thì chúng ta có thể nói rằng những người mua Táo và Chuối thì cũng thường mua Anh Đào và Sầu Riêng. Tập X được gọi là xuất hiện trong giao dịch t nếu như nó là tập con của t. Độ hỗ trợ và độ tin cậy là hai tham số dùng để đo lường luật kết hợp. Thuật toán phổ biến nhất tìm các luật kết hợp là Apriori sử dụng các luật kết hợp nhị phân.1: Độ hỗ trợ Độ hỗ trợ (Sup) của luật kết hợp ⟶ là tần suất giao dịch chứa tất cả các item trong cả hai tập X và Y.
Ví dụ: độ hỗ trợ của luật ⟶ là 40%, có nghĩa là 40% các giao dịch X và Y được mua cùng nhau. Công thức: ( ∪ ) ( ⟶ )= ( ∪ )= Trong đó n( ∪ ) là số giao dịch có chứa cả X lẫn Y vàN là tổng số giao dịchtrong CSDL.2: Độ tin cậy (Conf) là xác suất xảy ra khi Y đã biết X. Ví dụ độ tin cậy của {Táo}⟶{Chuối} là 80% có nghĩa là 80% khách hàng mua {Táo} cũng mua {Chuối}. Công thức: ( ∪ ) ( ⟶ )= ( | )= ( ) Để thu được các luật kết hợp, ta thường áp dụng 2 tiêu chí: độ hỗ trợ tối thiểu minsup và độ tin cậy tối thiểu minconf là hai giá trị ngưỡng tối thiểu cho trước.
5 Luật kết hợp ⟶ được coi là một mẫu có giá trị nếu xảy ra đồng thời ( ⟶ )≥ và ( ⟶ ) ≥. Một tập X có độ hỗ trợ vượt quá ngưỡng minsup được gọi là một tập phổ biến.3: Lớp tương đương Cho X ⊆ I, ta định nghĩa hàm p(X,k)= X[1,k] gồm k phần tử đầu của X và quan hệ tương đương dựa vào tiền tố sau: , ⊆ , ≡ , ( , )= ( , ) Tập hợp tất cả itemset có cùng tiền tố là X gọi là lớp tương đương, và được ký hiệu là [X]. Kết nối Galois Cho quan hệ hai ngôi ⊆ × chứa CSDL cần khai thác, trong đó I là tập các danh mục còn T là tập các giao tác. Ta định nghĩa hai ánh xạ giữa P(I) và P(T) như sau: I.
Dựa theo Galois [9] ta có các tính chất sau: (i). Phương pháp Apriori Khai thác tập phổ biến được đề xuất bởi Agrawal và các đồng sự năm 1993 [3] là một phương thức dành cho doanh nghiệp để phân tích giỏ hàng, nhằm mục đích tìm ra những quy luật trong việc mua sắm của khách hàng, siêu thị, v.v… Thuật toán Apriori là thuật toán sinh ứng viên được đề xuất bởi Agrawal và Srikant vào năm 1994 [2]. Tư tưởng chính của thuật toán Apriori là: - Tìm ra tất cả các tập phổ biến có thể có trong cơ sở dữ liệu: k-itemset (tập danh mục gồm k phẩn tử) được dùng để tìm (k+1)-itemset. 6 - Đầu tiên tìm 1-itemset (ký hiệu L1).
L2 được dùng để tìm L3 (3-itemset) và tiếp tục cho đến khi không có k-itemset được tìm thấy. - Từ phổ biến sinh ra các luật kết hợp mạnh (các luật kết hợp thỏa mãn minsup và minconf) Thuật toán Apriori dùng cách tiếp cận lặp được biết đến như tìm kiếm theo mức, với các tập có kích thước là k gọi là k-itemset được dùng để thăm dò các tập có kích thước k+1 gọi là (k+1)-itemset.1: Mọi tập con của tập phổ biến đều phổ biến, nghĩa là ∀ ⊆ , có nghĩa là nếu ( )≥ thì ( )≥ .2: Mọi tập cha của tập không phổ biến đều không phổ biến, nghĩa là ∀ ⊇ , nếu ( )< thì ( )< Các bước của giải thuật Apriori: Bước 1: Tính độ hỗ trợ cho mỗi item có kích thước là 1, sau đó lọc ra các item thỏa mãn yêu cầu minsup và đặt nó là tập L 1: 1-itemset là tập kết quả tìm được. Chọn L 1 là tập hạt giống. Bước 2: Bắt đầu từ tập hạt giống 1-itemset là tập phổ biến có kích thước là 1 đã tìm được ở trên, phát sinh ra các tập phổ biến có kích thước là 2 gọi là các tập ứng viên (C) và tính độ hỗ trợ cho mỗi tập (C) này, từ đó chọn ra các tập phổ biến thỏa yêu cầu và đặt nó là tập L 2: 2-itemset được dùng làm tập hạt giống cho bước kế tiếp.
Bước 3: Lặp lại bước 2, từ việc tiến hành chọn tập hạt giống có kích thước l là l-itemset để tìm ra các tập ứng viên có kích thước là (l+1)-itemset, quá trình này sẽ kết thúc khi không còn tìm được tập phổ biến nào thỏa yêu cầu minsup. 7 Giải thuật Apriori: Đầu vào: Tập các giao dịch D, ngưỡng hỗ trợ tối thiểu cminsup Đầu ra: L các tập phổ biến có trong D. Phương thức: Apriori() { Gọi C k Tập các ứng viên có kích thước k L k Các tập phổ biến có kích thước k L 1 = { các tập phổ biến có kích thước là 1 thỏa cminsup}; for ( k = 1; L k!= ∅; k++ ) { C k + 1 = Apriori_gen(F k) // Các ứng viên được tạo ra từ F k for each t in D { Ct = { ∈ | ⊆ } for ∈ { c. ≥ } } return ⋃ } Thuật toán Apriori sử dụng độ hỗ trợ tối thiểu dưới dạng số đếm (cminsup- minsup count) để loại bỏ các ứng viên.
Giá trị cminsup do người dùng đưa ra. Hàm Apriori_gen có nhiệm vụ sinh ra các tập itemset có kích thước k + 1 từ tập hạt giống có kích thước là k trong tập L k. Thủ tục này được thực thi bằng cách nối (join) các tập item có chung các tiền tố (prefix) và sau đó áp dụng tính chất 1.1 để loại bỏ các tập không thỏa mãn: 8 Bước nối: sinh ra các tập L k+1 là ứng viên của tập phổ biến có kích thước k+1 bằng cách kết hợp tập phổ biến P k và Qk có kích thước k và trùng nhau ở k-1 tập đầu tiên. Ví dụ ta có: +1 = + = { , ,…, , } với Với = { , ,…, , } và = { , ,…, , } trong đó ≤ ≤ ⋯ ≤ ≤ ≤ Bước tỉa: Giữ lại tất cả các ứng viên L k+1 thỏa thỏa mãn tính chất Apriori (tính chất 1.1) tức là mọi tập con có kích thước k của nó đều là tập phổ biến (∀ X ⊆ L k+1 và |X| = k thì X ∈ F k).
Ta có cơ sở dữ liệu D gồm 4 giao dịch với các tập item sau: Bảng 2.1 Cơ sở dữ liệu các giao dịch D Transaction Item 1 A, B, D, E 2 B, C, E 3 A, B, D, E 4 A, B, C, E 5 A, B, C, D, E 6 B, C, D Áp dụng giải thuật Apriori, cho CSDL giao dịch D với ngưỡng minsup = 0.4 Bước 1: Quét CSDL Dđể xác định độ hỗ trợ cho các tập phổ biến có kích thước là 1.