Phương pháp luận kết hợp và ứng dụng

Ký hiệu supp(XY) Supp(XY)= |{ T D: T X Y}| | |D    Khi chúng ta nói rằng độ hỗ trợ của một luật là 50%, có nghĩa là coc 50% tổng số bản ghi chứa X  Y. Như vậy, độ hỗ trợ mang ý nghĩa thống kê của luật. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 27 Trong một số trường hợp, chúng ta chỉ quan tâm đến những luật có độ hỗ trợ cao (Ví dụ như luật kết hợp xét trong cửa hàng tạp phẩm). Nhưng cũng có trường hợp, mặc dù độ hỗ trợ của luật thấp, ta vẫn cần quan tâm (ví dụ luật kết hợp liên quan đến nguyên nhân gây ra sự đứt liên lạc ở các tổng đài điện thoại) Định nghĩa: Độ tin cậy Định nghĩa 2.3: Độ tin cậy của một luật kết hợp XY là tỷ lệ giữa số lượng các bản ghi trong D chứa X  Y với số bản ghi trong D có chứa tập hợp X. Ký hiệu độ tin cậy của một luật là conf(r). Ta có 0  conf(r)  1 Nhận xét: Độ hỗ trợ và độ tin cậy có xác suất sau: Supp(XY)=P(X  Y) Conf (XY) = P(Y/X)=supp(X  Y)/supp(X) Có thể định nghĩa độ tin cậy như sau: Định nghĩa 2.4: Độ tin cậy của một luật kết hợp XY là tỷ lệ giữa số lượng các bản ghi của tập hợp chứa X  Y, so với tổng số các bản ghi chứa X. Nói rằng độ tin cậy của một luật là 90%, có nghĩa là có tới 90% số bản ghi chứa X chứa luôn cả Y. Hay nói theo ngôn ngữ xác suất là: “ Xác suất có điều kiện để sảy ra sự kiện Y đạt 85%”. Điều kiện ở đây chính là: “Xảy ra sự kiện X”. Như vậy, độ tin cậy của luật thể hiện sự tương quan (correlation) gữa X và Y. Độ tin cậy đo sức nặng của luật, và người ta hầu như chỉ quan tâm đến những luật có độ tin cậy cao. Một luật kết hợp đi tìm các nguyên nhân dẫn tới hỏng hóc của hệ thống tổng đài, hay đề cập đến những mặt hàng thường hay được khách hàng mua kèm với mặt hàng chính mà độ tin cậy thấp sẽ không có ích cho công tác quản lý. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 28 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ác luật có độ 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. Ví dụ: Khi phân tích giỏ hàng của người mua hàng trong một siêu thị ta được luật kiểu như: 85% khách hàng mua sữa thì cũng mua bánh mì, 30% thì mua cả hai thứ. Trong đó: “mua sữa” là tiền đề còn “mua bánh mì ” là kết luận của luật. Con số 30% là độ hỗ trợ của luật còn 80% là độ tin cậy của luật. Chúng ta nhận thấy rằng tri thức đem lại bởi luật kết hợp dạng trên có sự khác biệt rất nhiều so với những thông tin thu được từ các câu lệnh truy vấn dữ liệu thông thường như SQL. Đó là những tri thức, những mối liên hệ chưa biết trước và mang tính dự báo đang tiềm ẩn trong dữ liệu. Những tri thức này không đơn giản là kết quả của phép nhóm, tính tổng hay sắp xếp mà là của một quá trình tính toán khá phức tạp. Định nghĩa: Tập hợp Định nghĩa 2.5: Tập hợp X được gọi là tập hợp thường xuyên (Frenquent itemset) nếu có supp(X)  minsup, với minsup là ngưỡng độ hỗ trợ cho trước. Kí hiệu các tập này là FI Tính chất 2.1: Giả sử A,B  I là hai tập hợp với AB thì supp(A)  supp(B) Như vậy, những bản ghi nào chứa tập hợp B thì cũng chứa tập hợp A Tính chất 2.2: Giả sử A, B là hai tập hợp, A,B  I, nếu B là tập hợp thường xuyên và AB thì A cũng là tập hợp thường xuyên. Thật vậy, nếu B là tập hợp thường xuyên thì supp(B)  minsup, mọi tập hợp A là con của tập hợp B đều là tập hợp thường xuyên trong cơ sở dữ liệu D vì supp(A)  supp(B) (Tính chất 2.1) Tính chất 2.3: Giả sử A, B là hai tập hợp, A  B và A là tập hợp không thường xuyên thì B cũng là tập hợp không thường xuyên Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 29 Định nghĩa 2.6: Một tập mục X được gọi là đóng (closed) nếu không có tập cha nào của X có cùng độ hỗ trợ với nó, tức là không tồn tại một tập mục X’ nào mà X’X và t(X) = t(X’) (với t(x) và t(X’) tương ứng là tập các giao chứa tập mục X và X’). Ký hiệu tập phổ biến đóng là FCI. Định nghĩa 2.7: Nếu X là phổ biến và không tập cha nào của X là phổ biến, ta nói rằng X là một tập phổ biến lớn nhất (maximally frequent itemset). Ký hiệu tập tất cả các tập phổ biến lớm nhất là MFI. Dễ thấy MFI  FCI  FI. Khai phá luật kết hợp là công việc phát hiện ra (tìm ra, khám phá, phát hiện) các luật kết hợp thỏa mãn các ngưỡng độ hỗ trợ () và ngưỡng độ tin cậy () cho trước. Bài toán khai phá luật kết hợp được chia thành hai bài toán nhỏ, hay như người ta thường nói, việc giải bài toán trải qua hai pha: Pha 1: Tìm tất cả các tập phổ biến (tìm FI) trong CSDL T. Pha 2: Sử dụng tập FI tìm được ở pha 1 để sinh ra các luật tin cậy (interesting rules). Ý tưởng chung là nếu gọi ABCD và AB là các tập mục phổ biến, thì chúng ta có thể xác định luật AB  CD với tỷ lệ độ tin cậy: conf = supp( ) supp( ) ABCD AB Nếu conf  minconf thì luật được giữ lại (và thỏa mãn độ hỗ trợ tối thiểu vì ABCD là phổ biến). Trong thực tế, hầu hết thời gian của quá trình khai thác luật kết hợp là thực hiện ở pha 1. Nhưng khi có những mẫu rất dài (mẫu chứa nhiều mục) xuất hiện trong dữ liệu, việc sinh ra toàn bộ các tập phổ biến (FI) hay các tập đóng (FCI) là không thực tế. Hơn nữa, có nhiều ứng dụng mà chỉ cần sinh tập phổ biến lớn nhất (MFI) là đủ, như khám phá mẫu tổ hợp trong các ứng dụng sinh học. Có rất nhiều nghiên cứu về các phương pháp sinh tất cả các tập phổ biến và tập phổ biến lớn nhất một cách có hiệu quả. Khi các mẫu phổ biến Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 30 (frequent patterm) dài có từ 15 đến 20 items) thì tập FI, thậm chí cả tập FCI trở nên rất lớn và hầu hết các phương pháp truyền thống phải đếm quá nhiều tập mục mới có thể thực hiện được. Các thuật toán dựa trên thuật toán Apriori – đếm tất cả 2k tập con của mỗi k- itemsets mà chúng quét qua, và do đó không thích hợp với các itemsets dài được. Các phương pháp khác sử dụng “lookaheads” để giảm số lượng tập mục được đếm. Tuy nhiên, hầu hết các thuật toán này đều sử dụng tìm kiếm theo chiều rộng, ví dụ: tìm tất cả các k – itemsets trước khi tính đến các (k+1) – itemsets. Cách làm này hạn chế hiệu quả của lookaheads, vì các mẫu phổ biến dài hơn mà hữu ích vẫn chưa được tìm ra. Thuật toán 1 – Thuật toán cơ bản: Input: I, D, ,  Output: Các luật kết hợp thỏa mãn ngưỡng độ hỗ trợ , ngưỡng độ tin cậy . Algorithm: 1) Tìm tất cả các tập hợp các tính chất có độ hỗ trợ không nhỏ hơn ngưỡng . 2) Từ các tập hợp mới tìm ra, tạo ra các luật kết hợp có độ tin cậy không nhỏ hơn . Ví dụ minh họa: Xét 4 mặt hàng (tính chất) trong một cửa hàng thực phẩm với CSDL các giao dịch thuộc loại nhỏ, chỉ có 4 giao dịch (giỏ mua hàng), cho trong các bảng sau: Giao dịch Mua hàng gì? T1 Bánh mì, Bơ, Trứng T2 Bơ, Trứng, Sữa T3 Bơ T4 Bánh mì, Bơ Bảng 2.1. Giao dịch mua hàng Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 31 Cho trước 2 ngưỡng  = 40% và  = 60% Ta tính độ hỗ trợ của các tập hợp các tính chất. Tập hợp Tập các bản ghi Tỷ lệ Độ hỗ trợ Vượt ngưỡng độ hỗ trợ 40% Bánh mì {1,4} 2/4 50% Đúng Bơ {1,2,3,4} 4/4 100% Đúng Trứng {1,2} 2/4 50% Đúng Sữa {2} 1/4 25% Sai Bánh mì, Bơ {1,4} 2/4 50% Đúng Bánh mì, Trứng {1} 1/4 25% Sai Bánh mì, Sữa {} 0/4 0% Sai Bơ, Trứng {1,2} 2/4 50% Đúng Bơ, Sữa {2} 1/4 25% Sai Trứng, Sữa {2} 1/4 25% Sai Bánh mì, Bơ, Trứng {1} 1/4 25% Sai Bánh mì, Bơ, Sữa {} 0/4 0% Sai Bánh mì, Trứng, Sữa {} 0/4 0% Sai Bơ, Trứng, Sữa {2} 1/4 25% Sai Bánh mì, Bơ, Trứng, Sữa {} 0/4 0% Sai Bảng 2.2. Tính độ hỗ trợ cho các tập hợp chứa các mặt hàng Luật kết hợp Tỷ lệ Độ tin cậy Vượt ngưỡng độ tin cậy 60% Bánh mì  Bơ 2/4 50% Sai Bơ  Bánh mì 2/2 100% Đúng Bơ  Trứng 2/2 100% Đúng Trứng  Bơ 2/4 50% Sai Bảng 2.3. Các luật kết hợp và độ tin cậy của chúng Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 32 Agrawal đã chỉ ra việc duyệt các tập hợp các tính chất để tính ra ngưỡng độ hỗ trợ của chúng và đánh giá có vượt ngưỡng  cho trước hay không, tốn rất nhiều thời gian tính toán (độ phức tạp hàm mũ). Còn một khi đã xác định xong các tập hợp thỏa mãn điều kiện trên (gọi là các tập hợp xuất hiện thường xuyên) thì việc KPLKH đỡ tốn thời gian hơn. Agrawal đề nghị một thuật toán như sau. Thuật toán 2- Tìm luật kết hợp khi đã biết các tập hợp thƣờng xuyên): Input: I, D, , , S Output: Các luật kết hợp thỏa mãn ngưỡng độ hỗ trợ , ngưỡng độ tin cậy . Algorithm: 1) Lấy ra một tập xuất hiện –thường xuyên S S, và một tập con X  S. 2) Xét luật kết hợp có dạng X  (S X), đánh giá độ tin cậy của nó xem có nhỏ hơn  hay không. Thực chất, tập hợp S mà ta xét đóng vai trò của tập hợp giao S = X Y, và do X  (S – X) = , nên coi như Y= S – X. Các thuật toán xoay quanh KPLKH chủ yếu nêu ra các giải pháp để đẩy nhanh việc thực hiện mục 1 của Thuật toán 1. Chương sau ta điểm qua một số thuật toán. 2.3. Một số hƣớng tiếp cận trong khai phá luật kết hợp Lĩnh vực khai thác luật kết hợp cho đến nay đã được nghiên cứu và phát triển theo nhiều hướng khác nhau. Có những đề xuất nhằm cải tiến thuật toán, có đề xuất tìm kiếm những luật có ý nghĩa hơn v.v… và có một số hướng chính sau đây: - Luật kết hợp nhị phân (Binary association rule): là hướng nghiên cứu đầu tiên của luật kết hợp. Theo dạng luật kết hợp này thì các items chỉ được quan tâm là có hay không xuất hiện trong cơ sở dữ liệu giao tác Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 33 (Transaction database) chứ không quan tâm về mức độ hay tần xuất xuất hiện. Thuật toán tiêu biểu nhất của khai phá dạng luật này là thuật toán Apriori. - Luật kết hợp có thuộc tính số và thuộc tính hạng mục (Quantitative and categorial association rule): các cơ sở dữ liệu thực tế thường có các thuộc tính đa dạng (như nhị phân, số, mục (categorial)...) chứ không nhất quán ở một dạng nào cả. Vì vậy để khai phá luật kết hợp với các cơ sở dữ liệu này các nhà nghiên cứu đề xuất một số phương pháp rời rạc hóa nhằm chuyển dạng luật này về dạng nhị phân để có thể áp dụng các thuật toán đã có. - Luật kết hợp tiếp cận theo hướng tập thô (mining association rule base on rough set): tìm kiếm luật kết hợp dựa trên lí thuyết tập thô. - Luật kết hợp nhiều mức (multi-level association ruls): với cách tiếp cận luật kết hợp thế này sẽ tìm kiếm thêm những luật có dạng: mua máy tính PC  mua hệ điều hành Window AND mua phần mềm văn phòng Microsoft Office,… - Luật kết hợp mờ (fuzzy association rule): Với những khó khăn gặp phải khi rời rạc hóa các thuộc tính số, các nhà nghiên cứu đề xuất luật kết hợp mờ khắc phục hạn chế đó và chuyển luật kết hợp về một dạng gần gũi hơn. - Luật kết hợp với thuộc tính được đánh trọng số (association rules with weighted items): Các thuộc tính trong cơ sở dữ liệu thường không có vai trò như nhau. Có một số thuộc tính quan trọng và được chú trọng hơn các thuộc tính khác. Vì vậy trong quá trình tìm kiếm luật các thuộc tính được đánh trọng số theo mức độ xác định nào đó. Nhờ vậy ta thu được những luật “hiếm” (tức là có độ hỗ trợ thấp nhưng mang nghiều ý nghĩa). Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 34 - Khai thác luật kết hợp song song (parallel mining of association rule): Nhu cầu song song hóa và xử lý phân tán là cần thiết vì kích thước dữ liệu ngày càng lớn nên đòi hỏi tốc độ xử lý phải được đảm bảo. Trên đây là những biến thể của khai phá luật kết hợp cho phép ta tìm kiếm luật kết hợp một cách linh hoạt trong những cơ sở dữ liệu lớn. Bên cạnh đó các nhà nghiên cứu còn chú trọng đề xuất các thuật toán nhằm tăng tốc quá trình tìm kiếm luật kết hợp trong cơ sở dữ liệu. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 35 Chƣơng 3 MỘT SỐ THUẬT TOÁN PHÁT HIỆN LUẬT KẾT HỢP 3.1. Thuật toán AIS Thuật toán do Agrwal đề nghị năm 1993. Thuật toán này chú trọng khai phá luật kết hợp có dạng X Y, với Y là tập hợp chỉ bao gồm 1 tính chất (tập hợp 1 phần tử). Thuật toán tìm cách xây dựng dần dần các tập ứng cử viên cho “chức vụ” tập hợp xuất hiện  – thường xuyên. Với cách đánh số thứ tự từ điển cho từng tính chất, việc bổ sung phần tử cho tập ứng cử viên tránh được trùng lặp, do vậy tiết kiệm tối đa thời gian tính toán. Số lượng các tập ứng cử viên quá nhiều có thể gây ra hiện tượng tràn bộ nhớ. Thuật toán đề nghị một phương án quản lý bộ nhớ hợp lý đề phòng trường hợp này: không cho phép các ứng cử viên chiếm bộ nhớ, mà ghi thẳng chúng vào đĩa ở chế đồ thường trực (disk-resident). Dưới đây là nội dung chủ yếu của Thuật toán AIS: Input: CSDL D, minsup Output: các tập mục phổ biến 1. L1 = { các tập mục phổ biến}; 2. for (k=2; Luật kết hợpk-1   ; k++ ) do begin 3. Ck = ; 4. forall các giao dịch t  D do begin 5. Lt = Subset(Lk-1,t); // các tập mục phổ biến thuộc Lk-1 chứa trong giao dịch t 6. forall các tập mục phổ biến lt  Lt B do begin 7. Ct = tăng thêm một mục có trong giao dịch t; 8. forall các ứng cử viên c  Ct do 9. if (c  Ck) then add tăng biến đếm của c thêm 1 cho mục tương ứng của Ck Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 36 else add c và Ck và tăng biến đếm tương ứng thêm 1; 10. End 11. Lk = { c  Ck | c.count  minsup} 12. End 13. Trả lời = k Lk ; Thuật toán được áp dụng tỏ ra thành công cho cơ sở dữ liệu của các công ty bán lẻ hàng hóa và đã tìm ra các luật kết hợp đề cập đến mối quan hệ giữa hành vi ứng xử mua hàng của khách hàng với 63 gian hàng của công ty, sau khi nghiên cứu 46.873 giao dịch mua hàng. 3.2. Thuật toán SETM Thuật toán do Houtsma đề nghị năm 1995. Thuật toán này cũng sử dụng kỹ thuật bổ sung dần dần từng phần tử (từ tập hợp 1 phần tử) nhằm tìm kiếm các tập hợp ứng cử viên. Một cải tiến đáng kể là Thuật toán đề nghị lưu lại cả ID của giao dịch cùng với tập hợp ứng cử viên. Agrawal đã chỉ ra, Thuật toán này không những không có phương án quản lý bộ nhớ mà nó còn giả định nhét toàn bộ tập hợp ứng cử viên của bước trước vào bộ nhớ để bước sau tiện bề sử dụng. Sarawagi đã chỉ ra Thuật toán này không hiệu quả. Thuật toán SETM được mô tả hình thức như sau: Input: CSDL D, minsup Output: Các tập mục phổ biến 1. L1 = {các tập mục phổ biến}; 2. L1’={các tập mục phổ biến cùng các TID của nó được sắp xếp theo TID}; 3. for (k=2; Luật kết hợpk-1   ; k++ ) do begin 4. Ck = ; 5. forall các giao dịch t  D do begin Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 37 6. Lt = (l  L’k-1 | l.TID = t.TID); // các tập có (k - l) mục phổ biến trong giao dịch t 7. forall các tập mục phổ biến lt  Lt do begin 8. Ct = tăng lt thêm một mục có trong giao dịch t; //Các ứng cử viên có trong t 9. C’k +={| c  Ct}; 10. end 11. end 12. Sort C’k theo các tập mục; 13. delete các mục c  C’k có c.count<minsup đưa vào L’k ; 14. Lk ={ | l  Lk'}; //kết hợp với bước 13 15. Sort L’k theo TID; 16. end 17. Trả lời = k Lk ; 3.3. Thuật toán Apriori Thuật toán do Agrawal đề nghị năm 1994, được Cheung đánh giá mang tính chất lịch sử trong lĩnh vực KPLKH, vì đã vượt xa tầm của các thuật toán quen thuộc trong lĩnh vực này. Thuật toán dựa trên một nhận xét khá đơn giản là bất kỳ tập hợp con nào của tập xuất hiện  – thường xuyên cũng là tập xuất hiện  – thường xuyên. Do đó, trong quá trình đi tìm các tập ứng cử viên, nó chỉ cần dùng đến các tập ứng cử viên vừa xuất hiện ở bước ngay trước đó, chứ không cần dùng đến tất cả các tập ứng cử viên (cho đến thời điểm đó). Nhờ vậy, bộ nhớ được giải phóng đáng kể. 1/ Bước 1: cho trước ngưỡng độ hỗ trợ 0    1. Tìm tất cả các mặt hàng xuất hiện  – thường xuyên. Để ý rằng, một siêu thị có thể có tới 100.000 mặt hàng. Tập hợp tìm được ký hiệu là L1. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 38 2/ Bước 2: Ta tiến hành ghép đôi các phần tử của L1 (không cần để ý đến thứ tự), được tập C2, tạp gọi là tập các ứng cử viên có 2 phần tử. Sở dĩ chỉ gọi là “ứng cử viên”, vì chưa chắc chúng đã là  – thường xuyên. Sau khi kiểm tra (dùng định nghĩa), ta lọc ra được các tập hợp  – thường xuyên có 2 phần tử. Ký hiệu tập hợp này là L2. 3/ Bước 3: Với chứ ý đã nêu (về tính chất tăng dần của các tập hợp  – thường xuyên ), ta tiến hành tìm các ứng cử viên có 3 phần tử (lấy từ L1). Gọi nó là tập C3. Lưu ý là nếu {A, B, C} muốn là “ứng cử viên” thì các tập 2 phần tử {A, B},{B,C},{C, A } đều phải là  – thường xuyên, tức là chúng đều là phần tử của tập L2. Ta đi “kiểm tra tư cách đại biểu” trong tập C3 và lọc ra được tập các tập hợp  – thường xuyên có 3 phần tử. Tập hợp này được ký hiệu là L3. 4/ Bước 4: Ta tiến hành tìm các ứng cử viên có n phần tử. Gọi tập của chúng là tập Cn và từ đây, lọc ra Ln là tập tập các tập hợp  – thường xuyên có n phẩn tử. Thuật toán này có giúp ích được gì, ta cùng nhau xem xét ví dụ sau: Câu lệnh SQL sau đây tạo cặp, xử lý 10 triệu giỏ mua hàng, mỗi giỏ mua hàng trung bình có 10 mặt hàng, với giả thiết siêu thị có khoảng 100.000 mặt hàng: SELECT b1.item b2.item COUNT(*) FROM Baskets b1, Baskets b2 WHERE b1.BID = b2.BID AND b1.item <b2. item GROUP BY b1.item , b2. item HAVING COUNT(*) >= s; Câu lệnh WHERE đảm bảo các cặp ghép không bị đúp 2 lần (vì ta không cần để ý đến tứ tự các phần tử). Câu lệnh HAVING đả bảo các tập hợp chọn ra là  – thường xuyên. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 39 Nhận xét: Khi ghép Baskets với chính nó, mỗi giỏ ta có 45 cách chế ra các cặp ứng viên [do (10*9)/2=45], và do có 10 triệu giỏ mua hàng, nên ta phải xét 45x10 7 trường hợp để lọc ra các cặp  – thường xuyên. Trong khi đó nếu sử dụng Thuật toán Apriori, trước hết ta giảm được đáng kể kích thước của Baskets, vì ở bước 1 ta đi tìm các phần tử (mặt hàng) xuất hiện  – thường xuyên. SELECT * FROM Baskets GROUP BY item HAVING COUNT (*) >= s; Sự giảm kích thước của Baskets chưa phải là điểm cốt yếu. Điểm cốt yếu là khi ta kết hợp để tìm cặp, ta sẽ giảm được bình phương lần. Cốt lõi của thuật toán Apriori là hàm apriori_gen() do Agrawal đề nghị năm 1994. Hàm này hoạt động theo 2 bước, bước 1- tập hợp Lk-1 tự kết nối (join) với chính nó để tạo ra tập ứng cử viên Ck. Sau đó hàm apriori_gen() loại bỏ các tập hợp có một hợp con (k-1) phần tử không nằm trong Lk-1 (vì chúng không thể là tập hợp xuất hiện  – thường xuyên, theo như nhận xét ban đầu). Method: apriori_gen() [Agrwal1994] Input: Lớp các tập hợp xuất hiện  – thường xuyên có (k-1) phần tử, ký hiệu là Lk-1 Output: Lớp các tập hợp xuất hiện  – thường xuyên có k phần tử, ký hiệu là Luật kết hợp // Bước tự kết nối Ii = Items i Insert into Ck Select p.I1, p.I2,…, p.Ik-1, q.Ik-1 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 40 From Lk-1 is p, Lk-1 is q Where p.I1 = q.I1 and….and p.Ik-2 = q.Ik-2 and p.Ik-1 < q.Ik-1 //Bước tỉa bớt Forall itemsets c Ck do Forall (k-1)- subsets s of c do If (s is not of Lk-1) then Delete c from Ck Hàm sau đây có nhiệm vụ rà soát từng tính chất và đo đếm xem giá đỡ của nó bằng bao nhiêu. Nói cách khác, ở bước đầu tiên Agrawal dùng hàm count() để tìm ra các tập hợp xuất hiện  – thường xuyên có 1 phần tử. Function count(C:a set of itemsets, D: database) begin for each transaction T  D =  Di do begin forall subsets x T do if x  C then x.count++; end end Dưới đây là toàn bộ Thuật toán Apriori Thuật toán 3- Apriori [Agrawal1994] Input: I, D,  Output: L Algorithm: //Apriori Algorithm prposed by Agrawal R., Srikant, R. [Agrawal1994] //procedure LargeItemsets 1) C1: = I; // Tập ứng cử viên có 1 phần tử 2) Sinh ra L1 bằng cách tính tần số xuất hiện của mặt hàng trong các giao dịch; Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 41 3) for (k=2; Lk-1  ; k++) do begin //Tạo ra các tập ứng cử viên // Các tập ứng cử viên có k phần tử được sinh ra từ các tập (k-1)- phần tử xuất hiện  – thường xuyên. 4) Ck = apriori-gen( Lk-1 ); // Tính độ hỗ trợ cho Ck 5) Count (Ck, D) 6) Lk = {c  Ck| c.count  } 7) end 8) L:= k Lk Bảng 3.1 dưới đây minh họa áp dụng thuật toán cho ví dụ 2 ( =40%) Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 42 C1 C1 L1 Tập 1 phần tử {Bánh mì} {Bơ} {Trứng} {Sữa} Quét toàn bộ CSDL để tính độ hỗ trợ Tập hợp {Bánh mì} {Bơ} {Trứng} {Sữa} Độ hỗ trợ 50% 100% 50% 25% Tập hợp {Bánh mì} {Bơ} {Trứng} Độ tin cậy 50% 100% 50% C2 C2 L2 Tập 2 phần tử {Bánh mì, Bơ} {Bánh mì, Trứng} {Bơ, Trứng} Tập hợp {Bánh mì, Bơ} {Bánh mì, Trứng} {Bơ, Trứng} Độ hỗ trợ 50% 25% 50% Tập hợp {Bánh mì, Bơ} {Bơ, Trứng} Độ tin cậy 50% 50% C3 Quét toàn bộ CSDL để tính độ hỗ trợ C3 L3 Tập 3 phần tử  Tập hợp Độ hỗ trợ  Tập hợp Độ tin cậy  Bảng 3.1. Dùng thuật toán Apriori tính ra các tập hợp xuất hiện  – thường xuyên Bản thân Agrawal đưa ra nhận xét: thuật toán Apriori hiệu quả hơn so với AIS và SETM. Trong một ví dụ minh họa, ở bước thứ tư, thuật toán Apriori lược bỏ hết, chỉ còn giữ lại một tập ứng cử viên duy nhất, trong khi cả hai thuật toán kia vẫn đề nghị tới 5 ứng cử viên. Do đó, để đạt được kết quả như Apriori, hai thuật toán kia chắc chắn phải cần đến những tính toán bổ trợ. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 43 Thuật toán Apriori cải tiến cũng giải quyết 2 tình huống “xấu”, đó là khi Ck hoặc Lk-1 to quá, không chứa đủ trong bộ nhớ tính toán. Khi đó, cần tu chỉnh lại hàm apriori_gen() một chút. *Thuật toán Apriori nhị phân: Thuật toán Apriori nhị phân sử dụng các vector bit cho các thuộc tính, vector nhị phân n chiều ứng với n giao tác trong cơ sở dữ liệu. Có thể biểu diễn cơ sở dữ liệu bằng một ma trận nhị phân trong đó dòng thứ I tương ứng với giao tác (bản ghi) ti và cột thứ j tương ứng với mục (thuộc tính ) ij. Ma trận biểu diễn cơ sở dữ liệu ví dụ cho bảng dưới: TID A B C D E 1 1 1 0 1 1 2 0 1 1 0 1 3 1 1 0 1 1 4 1 1 1 0 1 5 1 1 1 1 1 6 0 1 1 1 0 Bảng 3.2. Ma trận biểu diễn cơ sở dữ liệu Các vector biểu diễn nhị phân cho các tập 1 thuộc tính có dạng sau: {A} Vector {B} Vector {C} Vector {D} Vector {E} Vector 1 1 0 1 1 0 1 1 0 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 1 0 1 1 1 0 Bảng 3.3. Vector biểu diễn nhị phân cho tập 1 thuộc tính Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 44 Các vector biểu diễn nhị phân cho các tập 2 thuộc tính có dạng sau: {A,B} {A,C} {A,D} {A,E} {B,C} {B,D} {B,E} {C,D} {C,E} {D,E} 1 0 1 1 0 1 1 0 0 1 0 0 0 0 1 0 1 0 1 0 1 0 1 1 0 1 1 0 0 1 1 1 0 0 1 0 1 0 1 0 1 1 1 1 1 1 1 1 1 1 0 0 0 0 1 1 0 1 0 0 Bảng 3.4. Vector biểu diễn nhị phân cho các tập 2 thuộc tính Các vector biểu diễn cho thấy {A,C}, {C,D} có độ hỗ trợ 33% nhỏ hơn độ hỗ trợ tối thiểu MinSupp=50% (cho trước) nên bị loại. Các vector biểu diễn nhị phân cho các tập 3 thuộc tính có dạng: {A,B,D} {A,B,E} {B,C, E} {B,D,E} 1 1 0 1 0 0 1 0 1 1 0 1 0 1 1 0 1 1 1 1 0 0 0 0 Bảng 3.5. Vector biểu diễn nhị phân cho các tập 3 thuộc tính Các vector biểu diễn nhị phân cho các tập 4 thuộc tính có dạng: {A,B,C,D} {A,B,C,E} {A,C,D,E} {B,C,D,E} 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 1 1 0 0 0 0 Bảng 3.6. Vector biểu diễn nhị phân cho các tập 4 thuộc tính Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 45 3.4. Thuật toán Apriori-TID Thuật toán Apriori-TID là phần mở rộng theo hướng tiếp cận cơ bản của thuật toán Apriori. Thay vì dựa vào cơ sở dữ liệu thô thuật toán Apriori- TID biểu diễn bên trong mỗi giao dịch bởi các candidate hiện hành. Như ta đã thấy, thuật toán Apriori đòi hỏi phải quét toàn bộ cơ sở dữ liệu để tính độ hỗ trợ cho các tập hợp ứng cử viên ở mỗi bước. Đây là một sự lãng phí lớn. Dựa trên tư tưởng ước đoán và đánh giá độ hỗ trợ, Agrawal đề nghị cải tiến Apriori theo hướng chỉ phải quét cơ sở dữ liệu lần đầu tiên, sau đó tính độ hỗ trợ cho các tập hợp 1 phần tử. Từ bước thứ hai trở đi, Thuật toán Apriori-TID nhờ lưu trữ song song cả ID của giao dịch và các ứng cử viên, có thể đánh giá, ước lượng độ hỗ trợ mà khỏi phải quét lại toàn bộ cơ sở dữ liệu. Nội dung thuật toán Apriori-TID Input: Tập các giao dịch D, minsup Output: Tập Answer gồm các tập mục thường xuyên trên D Method: L1= {large 1 – itemset}; 1C = database D; for (k=2; Lk-1  ; k++) do begin ;kC  For all entries t  1kC  do begin //Xác định các candidate itemset //được chứa trong giao dịch với định danh t.TID  1 c (c-c[k]) t.set_of_itemset (c-c[k-1]) t.set_of_itemset ;kC C     Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 46 For all candidates c Ct do c.count++; if (C1) then tt.TID,Ck kC C    end Luật kết hợp= {c  Ck | c.count  minsup}; end Answer = k Lk Sự khác nhau giữa Apriori và AprioriTID là: cơ sở dữ liệu không được sử dụng để đếm các support sau lần đầu tiên quét qua cơ sở dữ liệu. Vì sau lần quét đầu tiên các 1-itemset đã được sinh (các L1), các L1 này được dùng để lọc ra các giao dịch của cơ sở dữ liệu bất kỳ item nào là không phổ biến và những giao dịch trong 1C chỉ chứa những item không phổ biến. Kết quả đó được đưa vào 2C và sử dụng lần quét đó. Vì vậy kích thước của 2C là khá nhỏ hơn so với 1C . Sự giống nhau của hai thuật toán này là đều sử dụng bước cắt tỉa trong hàm Apriori_gen() 3.5.Thuật toán Apriori-Hybrid Thuật toán Apriori-Hybrid được coi như kết hợp giữa Thuật toán Apriori và thuật toán Apriori-TID. Trong thuật toán Apriori-Hybrid, được sử dụng khi tổ chức lặp và chuyển sang Apriori-TID khi đã chắc chắn rằng tập kC đã vào bộ nhớ chính. Thuật toán Apriori-Hybrid được coi là tốt hơn so với Apriori và AprioriTID. Nhờ có nhận xét tinh tế là thuật toán Apriori chạy khá nhanh ở những bước đầu tiên, còn thuật toán Apriori-TID chạy nhanh ở những bước sau (và đáng buồn là chạy khá chậm ở những bước đầu tiên), Agrawal đề nghị phương án lai ghép: không nhất thiết phải chạy tất cả các bước cùng một thuật Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 47 toán giống nhau. Những bước đầu tiên, ông cho chạy thuật toán Apriori, sau đó khi tập các ứng cử viên khá lớn, sắp chứa đầy trong bộ nhớ tính toán, mới dùng thuật toán Apriori-TID. Srikant đưa ra thêm một nhận xét: thời gian chuyển từ thuật toán Apriori sang thuật toán Apriori-TID tương đối “đắt” (tốn kém), và thuật toán lai ghép Apriori-Hybrid chỉ tỏ ra hiệu quả khi sự chuyển mạch này diễn ra ở gần cuối quá trình tìm kiếm tập xuất hiện  – thường xuyên. 3.6. Thuật toán FP_growth Như ta đã biết thuật toán Apriori là một bước đột phá về khai thác các tập mục thường xuyên bằng cách sử dụng kỹ thuật tỉa để rút gọn kích thước của các tập mục ứng cử. Tuy nhiên, trong trường hợp số tập mục nhiều, tập mục dài hoặc ngưỡng độ hỗ trợ nhỏ thì thuật toán gặp phải hai chi phí lớn: - Sinh ra số lượng khổng lồ các tập mục ứng cử. Ví dụ nếu có 104 tập mcụ 1- mục thường xuyên thì sẽ sinh ra hơn 107 tập mục 2- mục ứng cử và thực hiện kiểm tra xem tập mục nào thường xuyên. Hơn nữa, để phát hiện ra các tập mục thường xuyên có kích thước n, thuật toán phải kiểm tra 2n-2 các tập mục thường xuyên tiềm ẩn. - Phải duyệt qua cơ sở dữ liệu nhiều lần. Số lần duyệt cơ sở dữ liệu của thuật toán Apriori bằng độ dài của tập mục thường xuyên dài nhất tìm được. Trong trường hợp tập mục thường xuyên dài và cơ sở dữ liệu lớn thì không thể thực hiện được. Thuật toán Apriori phù hợp với cơ sở dữ liệu thưa, còn với cơ sở dữ liệu dạy thì thuật toán kém hiệu quả. Để khắc phục những chi phí lớn của thuật toán Apriori năm 2000 Jiawei Han, Jian pei và Yiwen Yin đã đưa ra thuật toán mới được gọi là FP_growth để tìm tập mục thường xuyên bằng cách không sinh các tập mục ứng cử từ các tập mục thường xuyên trước mà vẫn hiệu quả bằng cách sử dụng ba kỹ thuật sau: Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 48 Thứ nhất, thuật toán sử dụng cấu trúc cây mẫu thường xuyên FP_Tree để nén dữ liệu. Cấu trúc FP_Tree là mở rộng của cấu trúc cây prefix. Những nút trong cây là các mục có độ dài là 1, được gán nhãn bởi tên mục và được sắp xếp theo tần suất xuất hiện của các mục để các mục có số lần xuất hiện nhiều thì sẽ chia sẻ nhiều hơn. Thứ hai, khai thác phát triển từng đoạn mẫu dựa trên FP_Tree, bắt đầu từ mẫu thường xuyên có kích thước 1 và chỉ kiểm tra trên cơ sở mẫu phụ thuộc (conditional pattern base), khởi tạo FP_Tree của mẫu phụ thuộc, thực hiện khai thác đệ quy trên cây này. Mẫu kết quả nhận được qua việc kết nối mẫu hậu tố với mẫu mới được sinh ra từ FP_Tree phụ thuộc. Thứ ba, dùng kỹ thuật tìm kiếm phân hoạch không gian tìm kiếm và chia để trị để chia nhiệm vụ khai thác thành những nhiệm vụ nhỏ hơn và giới hạn lại các mẫu làm giảm không gian tìm kiếm. Cây mẫu thường xuyên Cây mẫu thường xuyên là cây có cấu trúc được định nghĩa như sau: Định nghĩa: FP_Tree bao gồm nút gốc có nhãn “Null”, tập các cây non prefix như là cây con của nút gốc và một bảng tiêu đề các mục thường xuyên. Mỗi nút của cây con prefix có 3 trường: Item_name, count, nút liên kết (node link); với item_name là nhãn của nút, count là số giao tác mà mục này xuất hiện, node_link dùng để liên kết với nút tiếp theo trong cây nếu có cùng Item_name hay Null nếu không có. Mỗi lối vào trong bảng tiêu đề có hai trường: Item_name và node_link, node_link trỏ tới nút đầu tiên trong FP_Tree có chứa nhãn Item_name. Ví dụ: Cho cơ sở dữ liệu với các giao tác và các mục thường xuyên trong mỗi giao tác được sắp xếp giảm dần theo độ hỗ trợ (minsup = 3/5) được thể hiện trong bảng sau: Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 49 TID Các mục trong giao tác Các mục thường xuyên được sắp xếp T100 f, a, c, d, g, i, m, p f, c, a, m, p T200 a, b, c, f, l, m, o f, c, a, b, m T300 b, f, h, j, o f, b T400 b, c, k, s, p c, b, p T500 a, f, c, l, p, m, n f, c, a, m, p Bảng 3.7.Các giao tác cơ sở dữ liệu Từ định nghĩa trên chúng ta có thuật toán xây dựng cây mẫu thường xuyên FP_Tree như sau: Thuật toán xây dựng cây FP_Tree Input: cơ sở dữ liệu và ngưỡng độ hỗ trợ minsup Output: Cây mẫu thường xuyên FP_Tree Method: Bước 1: Duyệt qua cơ sở dữ liệu để đếm số lần xuất hiện của các mục trong giao tác và xác định mục thường xuyên và độ hỗ trợ của chúng, sắp xếp các mục thường xuyên giảm dần theo độ hỗ trợ, ta được danh sách các mục được sắp xếp L. Bước 2: Xây dựng FP_Tree. Đầu tiên tạo nút gốc, sau đó với mỗi giao tác t chọn và sắp xếp các mục thường xuyên theo thứ tự trong danh sách L, thực hiện thêm vào cây FP_Tree bằng cách gọi hàm insert_tree(p|T), thay đổi trường count cho phù hợp. Ví dụ: Với cơ sở dữ liệu trình bày trong bảng 2.2 ta có: Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 50 Hình 3.8. Một cây mẫu thường xuyên Duyệt qua cơ sở dữ liệu để tìm tập mục thường xuyên và sắp xếp giảm dần theo độ hỗ trợ: Mục Số lần xuất hiện F 4 C 4 A 3 B 3 M 3 P 3 Khởi tạo cây T, gốc có nhãn Null Duyệt qua cơ sở dữ liệu lần thứ hai, với mỗi giao tác loại bỏ các mục không thường xuyên, các mục còn lại sắp xếp giảm dần theo số lần xuất hiện, dãy các mục phổ biến đó được thêm vào cây và thay đổi số đếm cho phù hợp. Quá trình xây dựng cây được thể hiện như trong hình 3.6 Header table Item Head of node_link f c a b m p f:4 c:3 a:3 m:1 p:2 Root c:1 b:1 p:1 b:1 b:1 m:2 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 51 Hình 3.9. Quá trình xây dựng FP_Tree c:1 Root f:1 a:1 m:1 p:1 T100 fcamp T200 fcabm Root f:2 c:2 a:2 m:1 p:1 b:1 m:1 T300 fb Root f:3 c:2 p:1 a:2 m:1 b:1 m:1 T400 cbb Root c:2 f:2 p:1 a:2 m:1 b:1 m:1 c:1 a:1 p:1 b:1 Root c:3 f:4 p:2 a:3 m:2 b:1 m:1 c:1 a:1 p:1 b:1 T500 fcamp Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 52 Kết quả thu được FP_Tree đầy đủ như sau: Hình 3.10. Cây FP_Tree của cơ sở dữ liệu trong bảng 2.2 Thủ tục thêm các mục thường xuyên vào cây FP_Tree: Procedure Insert_Tree(string[p|P], Tree T) //Trong đó p là mục đầu tiên của dãy và P là phần còn lại của dãy {If cây T có nút con N mà N.Item_name = p Then N.count++ Else Tạo nút mới N; N.Item_name:= p; N.count:=1; Thay đổi nút liên kết cho p; If p then Insert_Tree (p,N): } Khai thác tập mục thƣờng xuyên Sau khi xây dựng xong cây FP_Tree cho cơ sở dữ liệu việc tìm các tập mục thường xuyên chỉ thực hiện trên FP_Tree mà không cần duyệt cơ sở dữ liệu. Item Head of Node_link f c a b m p Root f:4 c:3 a:3 m:2 p:2 m:1 b:1 b:1 p:1 b:1 c:1 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 53 Tính chất: Khi tìm các mẫu có chứa mục ai chỉ cần tính toán cho các nút của cây con tiền tố P của ai số lần xuất hiện của các nút trong đường dẫn tiền tố bằng số lần xuất hiện của nút ai. Thuật toán FP_Growth được thực hiện như sau: Bắt đầu từ dưới lên trên của bảng header và cây, mỗi mục A dùng nút liên kết để duyệt qua tất cả các nút trên cây mà xuất hiện A, với mỗi nút N có n.Item_name = A tìm tất cả các đường dẫn của các nút N đó xuất phát từ gốc của cây tới nút N. Từ các đường dẫn đó ta xây dựng cây mẫu (partten tree) phụ thuộc cho A. Sau đó tìm các mục thường xuyên có chứa A từ cây mẫu phụ thuộc này. Ví dụ lần lượt xét mục theo thứ tự từ dưới lên p, m, .., f như sau: Xuất phát từ mục p:chiếu vào cây FP_Tree hình 3.7 ta có hai đường dẫn có chứa p là: f:4, c:3, a:3, m:2, p:2 và c:1, b:1, p:1. Theo các đường dẫn trên ta có tập mục fcam và xuất hiện 2 lần cùng với p, cb xuất hiện 1 lần cùng với p. Số lần xuất hiện của mục p là 2+1= 3 lần. Vì vậy ta tìm các mục thường xuyên có chứa p mà có cùng tần suất xuất hiện như p. Từ đó ta có hai tiền đường dẫn của p là: {(f:2, c:2, a:2, m:2)}, {(c:1, b:1)} và là cơ sở mẫu phụ thuộc. Khởi tạo cây mẫu thường xuyên trên cơ sở mẫu phụ thuộc ta được FP_Tree phụ thuộc và thực hiên khai thác đệ quy trên cây này ta thu được kết quả, trong cây này chỉ có một nhánh (c:3) nên ta chỉ có tập mục thường xuyên (cp) thỏa mãn ngưỡng minsup=3/5. Mục m có tần suất xuất hiện là 3, có hai đường dẫn có chứa mục m là (f:4, c:3, a:3, m:2) và (f:4, c:3, b:1, m:1) (Ta không cần xét mục p vì tất cả các tập mục thường xuyên có chứa p đã được tìm thấy khi xử lý với mục p) Từ hai đường dẫn trên ta có hai cơ sở mẫu phụ thuộc {(f:2, c:2, a:2), f:1, c:1, a:1, b:1}. Khởi tạo cây điều kiện trên đó ta được một đường dẫn đơn sau đó thực hiện khai thác đệ quy trên cây mẫu thường xuyên này. Hình 3.8 thể hiện quá trình khai thác các tập mục thường xuyên. Bắt đầu thực hiện khai thác lần lượt với các nút có nhãn a, c, f thu được một tập mục thường xuyên am, cm, fm, Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 54 tiếp đến thực hiện với mẫu thường xuyên (am:3) là thu được tập mục cam, fam và fcm. Thực hiện với được fcam. Như vậy với đường dẫn đơn thì kết quả khai thác có thể là tổ hợp của tất cả các mục trong đường dẫn. Hình 3.11. Các FP_Tree phụ thuộc Cơ sở mẫu phụ thuộc của m (f:2, c:2, a:2) (f:1, c:2, a:1, b:1) Bảng tiêu đề Mục Head of node link f c a FP_Tree phụ thuộc của m FP_Tree tổng quát Cơ sở mẫu phụ thuộc của “cam”(f:3) FP_Tree phụ thuộc của “cam”(f:3) Cơ sở mẫu phụ thuộc của “am”: (f:3, c:3) FP_Tree phụ thuộc của “am” Cơ sở mẫu phụ thuộc của “cm”(f:3) FP_Tree phụ thuộc của “cm”(f:3) Root m:1 f:4 c:3 a:3 c:4 b:1 f:4 m:2 p:2 b:1 f:4 f:3 Root c:2 a:2 f:3 Root c:3 f:3 Root f:3 Root Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 55 Thuật toán FP_Growth Procedue FP_Growth(tree, ) { If (cây chứa một đường đơn P) then For mỗi tổ hợp (kí hiệu ) của các nút trong đường dẫn P Do Sinh mẫu   với support = độ hỗ trợ nhỏ nhất của các nút trong  Else For mỗi ai trong header của cây Do { Sinh mẫu  =i   support= i .support Tìm cơ sở mẫu phụ thuộc của  và khởi tạo cây FP_Tree phụ thuộc Tree If Tree   Then FP_Growth(Tree, ) } Thuật toán FP_growth hiệu quả ở chỗ là chỉ duyệt qua cơ sở dữ liệu hai lần để xác định các mục thường xuyên và tạo cây FP_Tree. Nhờ sử dụng cấu trúc FP_Tree mà trong quá trình khai thác các mẫu thường xuyên không cần phải duyệt lại cơ sở dữ liệu mà chỉ cần xuất phát từ các mục ai trong bảng tiêu đề, sinh ra những cơ sở mẫu phụ thuộc, những ai đã được xử lý thì sẽ không xem xét trong xử lý các ai sau đó. Thuật toán phân hoạch không gian tìm kiếm để thu nhỏ không gian tìm kiếm, dùng phương pháp chia để trị để phân rã ra thành những nhiệm vụ nhỏ tạo nên hiệu quả. Sắp xếp các mục giảm dần theo tần suất xuất hiện của các mục dẫn đến các mục thường xuyên hơn thì được chia sẻ nhiều hơn. Thuật toán phù hợp với cả dữ liệu thưa, dày và mẫu dài. Đồng thời thuật toán cũng loại bỏ ngay những mục không phổ biến từ đầu. 3.7. Thuật toán PARTITION [Savasere 95] Thuật toán Partition dùng kỹ thuật tìm kiếm theo bề rộng và giao tập hợp của các biến nhận dạng (TID-List Intersection). Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 56 Thuật toán Partition là thuật toán tựa Apriori dùng tập giao để xác định giá trị support. Như đã trình bày ở trên thuật toán Apriori xác định giá trị support của tất cả các k-1 candidate trước khi tính k candidate. Vấn đề đặt ra là thuật toán Partition muốn dùng TIDList của tập phổ biến (k- 1)-item để phát sinh ra IDList của k candidate. Một điều hiển nhiên là kích thước phát sinh của các kết quả trên sẽ vượt quá giới hạn của bộ nhớ vật lý của máy tính thông thường một cách dễ dàng. Để giải quyết vấn đề này thuật toán Partition chia cơ sở dữ liệu thành nhiều phần và chúng được xử lý độc lập nhau. Kích thước của mỗi phần được chọn như cách thức của TIDList được lưu trên bộ nhớ chính. Sau khi đã xác định tập hổ biến cho mỗi phần của cơ sở dữ liệu, cần phải có motọ tao tác duyệt lại toàn bộ cơ sở dữ liệu để đảm bảo rằng tập phổ biến cục bộ cũng là tập phổ biến toàn cục. Thuật toán Partition làm giảm số lần quét dữ liệu [18]. Nó chia cơ sở dữ liệu thành những phần nhỏ và mỗi phần này được lưu trử trên bộ nhớ chính, giả sử các phàn này là D 1 , D 2 ,…., Dp . Trong lần quét đầu tiên, nó tìm large-itemset đại phương trong mỗi Di (1  i  p), với large-itemset địa phương Li có thể tìm được bằng cách sử dụng một thuật toán Level-wise chẳng hạn như Apriori. Từ mỗi phần có thể điều chỉnh bộ nhớ. Trong lần quét thứ hai, trong mỗi phần nó đếm các candidate-itemset. Input: I, , D1 , D2 ,…., Dp . Output: L Algorithm: //Tìm các tập xuất hiện  – thường xuyên trong từng lần phân hoạch 1) for I from 1 to p do 2) Li = Apriori (I, D i ,  ); //Li là các tập xuất hiện  – thường xuyên trong D i // Ghép các tập con lại để tạo ra tập ứng cử viên 3) C= i Li 4) count (C,D)= i D i ; Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 57 5) return L= {x | x C, x.count   x|D|}; Thuật toán này tỏ ra hiệu quả khi phân bố dữ liệu trong cơ sở dữ liệu bị lệch. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 58 Chƣơng 4 KHAI THÁC LUẬT KẾT HỢP TRONG BÀI TOÁN QUẢN LÝ THIẾT BỊ TRƢỜNG THPT CHU VĂN AN- THÁI NGUYÊN 4.1. Phát biểu bài toán Trường THPT Chu Văn An – Tỉnh Thái Nguyên là trường THPT đầu tiên được Bộ Giáo dục Đào tạo công nhận trường đạt chuẩn Quốc gia giai đoạn 2001- 2010 của tỉnh Thái Nguyên, và là trường số 16 trên toàn quốc đạt chuẩn tại thời điểm đó (năm 2003). Hiện nay trường là đơn vị đi đầu trong các trường THPT ứng dụng có hiệu quả Công nghệ thông tin và truyền thông trong việc quản lý và giảng dạy. Để có được những thành tích đáng trân trọng đó chính là nhờ vào đội ngũ giáo viên 100% đạt chuẩn và cơ sở vật chất hiện đại của Nhà trường. Ngoài cơ sở vật chất (lớp học, bàn, ghế…) như các trường khác thì trường THPT Chu Văn An còn quản lý 150 bộ máy vi tính, 27 máy chiếu projector, 9 máy in, ...Trong đó 100% các lớp học đều được trang bị đầy đủ máy tính và máy chiếu. Với số lượng trang thiết bị hiện đại nhiều đến như vậy thì vấn đề quản lý được toàn bộ các trang thiết bị, đồ dùng trong trường bằng sổ sách quả là một công việc hết sức nặng nhọc dành cho người quản lý. Để giảm bớt khó khăn đó cần có một chương trình quản lý trang thiết bị nhằm hỗ trợ cho người quản lý trong công việc của mình ví dụ như: lựa chọn thiết bị, đồ dùng cần mua: mua những thiết bị gì liên quan? mua số lượng bao nhiêu? khi cần thay thế thì có những nhóm thiết bị gì để tránh lãng phí? Diện tích phòng thực hành là 70m2 thì cần có thiết bị gì?... Việc ứng dụng khai thác luật kết hợp trong quản lý trang thiết bị giúp người quản lý nắm bắt được đặc thù trang thiết bị của từng loại phòng, danh sách các thiết bị hay liên quan tới nhau, từ đó khi cần mua sắm hay sửa chữa thay thế người quản lý sẽ có được công cụ hỗ trợ đắc lực giúp đưa ra nhanh quyết định. Chương trình này được cài đặt bằng thuật toán Apriori nhị phân bởi như đã biết, thuật toán Apriori nhị phân dựa trên một nhận xét khá đơn giản là bất kỳ tập con nào của tập xuất hiện –thường xuyên cũng là tập xuất hiện –thường xuyên. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 59 Do đó, trong quá trình đi tìm các tập ứng cử viên, nó chỉ cần dùng đến các tập ứng cử viên vừa xuất hiện ở bước ngay trước đó, chứ không cần tất cả các tập ứng cử viên (cho đến thời điểm đó). Nhờ vậy, bộ nhớ được giải phóng đáng kể. 4.2. Cơ sở dữ liệu của bài toán - Bảng danh mục các phòng cần quản lý thiết bị Hình 4.1.Bảng danh mục các phòng Cấu trúc và ví dụ dữ liệu của bảng như sau: + Maphong: Ghi mã phòng + Loaiphong: Ghi loại phòng là phòng họp, phòng học hay phòng thực hành… + Tenphong: Ghi tên cụ thể của phòng Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 60 + Nha: Ghi tên dãy nhà của phòng + Tang: Ghi tên tầng - Bảng thống kê chi tiết các thiết bị trong phòng Hình 4.2.Bảng thống kê chi tiết các thiết bị trong phòng + Trường Maphong: Ghi mã phòng + Các trường còn lại là tên của các thiết bị cần quản lý như: Attomat, Ampli, Banhs (bàn học sinh), DieuHoa (điều hoà),....và dữ liệu ghi số lượng của thiết bị đó. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 61 4.3. Rời rạc các thuộc tính gốc để tạo thành các thuộc tính nhị phân Hình 4.3.Bảng đăng ký tên thuộc tính rời rạc Bảng gồm các trường + Mã TT gốc: ghi mã thuộc tính gốc + Mã TT rời rạc: ghi mã thuộc tính được tách ra (rời rạc) từ thuộc tính gốc. Một thuộc tính gốc được tách thành n thuộc tính kiểu nhị phân (thuộc tính mà dữ liệu có giá trị 0 hoặc 1). Ví dụ: thuộc tính gốc là Auttomat thì ta tạo thành ba thuộc tính At1, At2 và At3. Nếu số lượng Attomat <=2 thì trường At1=1, còn các trường At2, At3 sẽ = 0 Nếu số lượng Attomat >=3 và < 6 thì At2=1, còn At1, At3 sẽ = 0 Nếu số lượng Attomat >=6 thì trường At3=1, còn At1, At2 sẽ =0 Cụ thể, nếu trường Attomat có giá trị là 1, 3, 4 thì trường At1, At2 và At3 có giá trị như hình sau: Attomat At1 At2 At3 1  1 0 0 3 0 1 0 4 0 1 0 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 62 Tương tự ta rời rạc cho các trường lưu trữ các thiết bị khác như: rèm cửa, máy tính điều hoà,… 4.4. Cơ sở dữ liệu dạng nhị phân Sau khi biến đổi bảng dữ liệu gốc chi tiết tên và số lượng các thiết bị của các phòng trong cơ quan thành bảng dữ liệu dạng nhị phân, ta được bảng dữ liệu nhị phân như sau: Hình 4.4.Bảng cơ sở dữ liệu dạng nhị phân 4.5. Kết quả khai thác luật kết hợp bằng thuật toán Apriori Với độ hỗ trợ (Min Support) = 0.65, độ tin cậy (Min Confidence) = 0.7 Tổng số giao tác = 18 Tổng số thuộc tính = 35 Tổng số tập phổ biến là 32 tập Tổng số luật là 180 luật Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 63 4.6. Kết quả khai thác cơ sở dữ liệu quản lý thiết bị Trƣờng THPT Chu Văn An – Thái Nguyên Kết quả khai thác luật kết hợp trên cơ sở dữ liệu thống kê phòng: có 100 giao tác tương ứng với thông ting 100 phòng và có 43 thuộc tính. Độ hỗ trợ tối thiểu Minsupp Độ tin cậy tối thiểu Min confidence Thời gian thực hiện Tổng số tập phổ biến Tổng số luật 60 0,7 5 phút 29 giây 63 602 50 0,7 6 phút 12 giây 126 1932 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 64 KẾT LUẬN Có thể nói rằng, khai phá dữ liệu là một trong những kỹ thuật quan trọng, mang tính thời sự không chỉ đối với Việt Nam mà còn của cả nền CNTT thế giới hiện nay. Sự bùng nổ thông tin, dữ liệu toàn cầu, trên mọi mặt của đời sống xã hội cùng với sự phát triển và ứng dụng ngày càng rộng rãi của công nghệ thông tin trong mọi lĩnh vực đã khiến cho nhu cầu xử lý những khối dữ liệu khổng lồ để kết xuất ra những thông tin, tri thức hữu ích cho người sử dụng một cách tự động, nhanh chóng và chính xác trở thành nhân tố quan trọng hàng đầu cho mọi thành công của các cơ quan, tổ chức và cá nhân trên thế giới. Khai phá dữ liệu đang được áp dụng một cách rộng rãi trong nhiều lĩnh vực kinh doanh và đời sống khác nhau: marketing, tài chính, ngân hàng và bảo hiểm, khoa học, y tế, an ninh, internet… Rất nhiều tổ chức và công ty lớn trên thế giới đã áp dụng kỹ thuật khai phá dữ liệu vào các hoạt động sản xuất kinh doanh của mình và thu được những lợi ích to lớn. Một trong những phương pháp quan trọng và cơ bản nhất của kỹ thuật khai phá dữ liệu mà đề tài đi sâu tìm hiểu là khai phá luật kết hợp. Mục tiêu của phương pháp này là phát hiện và đưa ra các mối liên hệ giữa các giá trị dữ liệu trong cơ sở dữ liệu. Mẫu đầu ra của giải thuật khai phá dữ liệu là luật kết hợp tìm được. Phương pháp này được sử dụng rất hiệu quả trong các lĩnh vực như maketing có chủ đích, phân tích quyết định, quản lý kinh doanh, phân tích giá thị trường … Trong khoảng thời gian không dài song đề tài đã tổng kết các kiến thức cơ bản nhất của phương pháp khai phá luật kết hợp. Có thể coi đề tài là một tài liệu tham khảo khá đầy đủ, rõ ràng về các kiến thức cơ bản trong phương pháp phát hiện luật kết hợp. Đồng thời, từ việc tìm hiểu về các kỹ thuật khai phá dữ liệu; các vấn đề liên quan đến khai phá luật kết hợp nhằm phát hiện và đưa ra các mối liên hệ giữa các giá trị dữ liệu trong CSDL đề tài đã áp dụng chúng vào bài toán thử nghiệm quản lý trang thiết bị đồ dùng của trường THPT Chu Văn An – Tỉnh Thái Nguyên dựa trên thuật toán Apriori. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 65 Hƣớng phát triển của luận văn: Một trong những công việc quan trọng của khai phá luật kết hợp là tìm tất cả các tập phổ biến trong cơ sở dữ liệu, nên trong thời gian tới luận văn sẽ mở rộng nghiên cứu theo hướng: ứng dụng thuật toán song song áp dụng cho bài toán khai phá luật kết hợp mờ, là luật kết hợp trên các tập thuộc tính mờ. Thuật toán song song chia đều cơ sở dữ liệu và tập ứng viên cho các bộ vi xử lý và các tập ứng viên sau khi chia cho từng bộ sử lý là hoàn toàn độc lập với nhau mục đích cải thiện chi phí tìm luật kết hợp mờ và thời gian hoá dữ liệu. Tiếp tục hoàn thiện hệ thống quản lý trang thiết bị và có thể ứng dụng thêm vào trong các lĩnh vực khác như đào tạo, ngân hàng, siêu thị. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 66 TÀI LIỆU THAM KHẢO [1] Lê Hoài Bắc (2002), Bài giảng về khám phá tri thức và khai thác dữ liệu – tìm luật kết hợp theo mục đích người dùng, Đại học Quốc gia TP. Hồ Chí Minh. [2] Đỗ Phúc (2002), Nghiên cứu và phát triển một số thuật giải, mô hình ứng dụng khai thác dữ liệu (data mining). Luận án tiến sĩ toán học, Đại học Quốc gia TP. Hồ Chí Minh. [3] Rakesh Agrawal, Tomasz Imielinski, and Arun Swami (1993), “Mining association rules between sets of items in large database”, In proc of the ACM SIGMOD Conference on Management of Data, Washington, D.C. [4] Rakesh Agrawal, Ramakrishnan Srikant (1996), “Mining Quantilative Association in Large Rilation Table”, In proc of the ACM SIGMOD Conference on Management of Data, Montreal, Canada. [5] Usama M.Fayyad, Gregory Piatetsky-Shapiro (1996), Advances in knowledge discovery and data mining, AAAI press/the MIT press. [6] Krzystof J.Cios, and Witold Perdrycz and Roman W.Swiniarski (1998), Data Mining Methods for Knowledge Discovery, Kluwer Acsdemic Publicshers, Boston/Dordrecht/London. [7] R. Agrawal and R. Srikant (1994). Fast algorithms for mining association rules. The International Conference on Very Large Databases, pages 487–499. [8] D.Phuc, H. Kiem (2000), Discovering the binary and fuzzy association rules from database, In proc of Int’l ConfAfss2000, Tsukuba, Japan, pp 981-986. [9] R. Agrawal and R. Srikant (1995). Mining sequential patterns. In P. S. Yu and A. L. P. Chen, editors, Proc. 11th Int. Conf. Data Engineering, ICDE. [10] N. F.Ayan, A. U. Tansel, and M. E. Arkun (1999). An efficient algorithm to update large itemsets with early pruning. In Knowledge Discovery and Data Mining. [11] John Wang (Idea Group Publishing) (2003). Data Mining: Opportunities and Challenges . Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 67 [12] Jiawei Han and Micheline Kamber 2002, Data Mining: Concepts and Techniques, University of Illinois, Morgan Kaufmann Publishers. [13] N Pqaquier et al (1999), Discovering frequent closed item sets for association rules, In proc of the 7 th intl conference ICDT’99, pp 398-410, Israel. [14] Osmar R.Zaiane, Mohammad EI-Haij, and PaulLu (200), Fast paralled Association Rule Mining without Cadidacy Generation, University of Alberta, Edmonton, Alberta, Canada.