Chương 1 đã trình bày tổng quan về dé tài cũng như sự cần thiết của website nghe nhạc trực tuyến. Tiến hành khảo sát các website tương tự trên thị trường đánh giá ưu, nhược diém từ đó đưa ra những giải pháp cũng như lựa chọn công nghệ, thuật toán cho đề tài. Nội dung chương tiếp theo sẽ trình bày về nguồn gốc, khái niệm về khai phá luật kêt hợp, ứng dung của thuật toán Apriori trong khai phá luật kêt hop. Nguyễn Thái Hoàng — B17DCCN264 17 Dé án tốt nghiệp CHƯƠNG 2: KHAI PHÁ LUẬT KÉT HỢP VÀ THUẬT TOÁN APRIORI Nội dung chương 2 sẽ bao gồm: - Giới thiệu về khai phá luật kết hợp.
- Giới thiệu về thuật toán Apriori. - Phuong pháp sinh luật kết hợp. - Ví dụ sử dụng thuật toán Apriori 2. Khai phá luật kết hợp 2.
Nguồn gốc Bài toán có nguồn sốc từ việc đi mua hàng tại các siêu thi [1], thông thường quan sát thay rằng khi một người mua mặt hàng này thì sẽ mua thêm những mặt hàng nhất định khác đi kèm với nó. Thực tế này được phát biểu thành bài toán về luật kết hợp như sau: Cho trước một tập các giao dịch, tìm các luật có thê tiên đoán sự xuât hiện của một mặt hàng này dựa trên sự xuât hiện của các mặt hàng khác trong giao dịch do. Xét một ví dụ về khai phá luật kết hop: các mặt hàng mua bán trong siêu thi của các giao dịch được thê hiện trong bang sau gôm hai cột, cột thứ nhat là mã của giao dịch, cột thứ hai là các mặt hàng mua trong lân giao dịch đó. TID Items Bread, Milk Bread, Diaper, Beer, Eggs Hình 2.
1 Ví dụ tập đữ liệu mua bán trong siêu thị [1]. Nguyễn Thái Hoàng — BI7DCCN264 18 Dé án tốt nghiệp Luật kết hợp quan sát được từ dữ liệu trong bảng bên gồm: {Diaper} -> {Beer}, {Milk, Bread} > {Eggs, Coke}, (Beer, Bread} > {Milk} Luật kết hop {Diaper} > {Beer} có nghĩa là nếu mua Diaper (ta giấy cho trẻ con) thì có nhiều khả năng là người đó sẽ mua thêm Beer (bia). Luật này thể hiện sự xảy ra đồng thời cả hai sự kiện mua tã giấy và mua bia chứ không phải là quan hệ nhân quả. Bài toán đặt ra cho khai phá dữ liệu ở đây là tìm ra tất cả những luật kết hợp kiểu như trên đối với một tập giao dịch cho trước.
Ứng dụng của luật kết hợp Được sử dụng trong bán đồ điện gia dụng, trả lời câu hỏi những sản phẩm gia dụng nao nên lưu trữ nhập kho cùng nhau? Được sử dụng trong việc gửi kèm thư quảng cáo trực tiếp các sản phẩm kèm theo việc bán sản phâm khác vì chúng ta biết được các sản phâm nào hay được bán cùng nhau. Được sử dụng trong khuyến mại bán hàng và quảng cáo tiếp thị. Các thuật ngữ khi sử dụng Itemset: Itemset là tập hợp của những item kí hiệu I={i1, I›,. in}, trong đó n là số lượng item [4].
Transaction: Transaction là một thành phần cơ sở đữ liệu mà nó bao gồm tập hợp các item. Transaction được ký hiệu là T và T © |. Mot Transaction chứa tap hợp các item T={11, iz,. Minimum support: Minimum support (minsup) co thé duoc xem nhu 1a một điều kiện giúp loại bỏ các tap không phô biến trong bat kỳ cơ sở dit liệu.
Thường sử dụng Minimum support cho mô hình tỷ lệ phần trăm [4]. Frequent itemset (tập phô biến): các Itemset đáp ứng các tiêu chí điều kiện minimum support thì được gọi là tập phổ biến. Nó được ký hiệu là Li trong d6ichi i-itemset [4]. Candidate itemset (ứng viên tập pho biến): ứng viên tập phổ biến là các item chỉ được xem xét xử lý.
Ứng viên tập phố biến là tất cả các kết hợp có thé có của tập phô biến. Nó thường được ký hiệu Ci trong đói chỉi-itemset [4]. Support: Độ hữu dung cua một luật có thể được đo với sự giúp đỡ của độ hỗ trợ [4]. Xem xét hai itemset A và B.
Dé tính toán support của A>B theo công thức như sau: (số lượng giao dich bao gồm cả A tà B) Supp(A->B)= Tổng số lượng giao dich Nguyễn Thái Hoàng — B17DCCN264 19 Dé án tốt nghiệp e Confidence: Confidence chỉ sự tin cậy của các luật. Thông số này cho phép chúng ta đếm mức độ thường xuyên một giao tác của tập phô biến phủ hợp với ý nghĩa cả phía cạnh bên trái với phía cạnh bên phải, các tập phổ biến không đáp ứng các điều kiện trên có thê được loại bỏ. Xem xét hai item A và B. Dé tính toán confidence của A>B theo công thức sau[4]: số lượng giao dich bao gồm cả A&B Conf(A->B) STGiao dich ——O— ee rr os r bao gồm chì A e Minimum Confidence: Minimum Confidence (minconf) chỉ độ tin cậy tối thiểu.
e Minsup và minconf gọi là các giá trị ngưỡng phải được xác định trước khi sinh các luật kết hợp [3]. Nhiệm vụ khai phá tìm luật kết hợp Cho trước một tập các giao dịch T, mục tiêu của khai phá luật kết hợp là tìm ra tat cả các luật có: độ hỗ trợ > ngưỡng minsup va độ tin cậy > ngưỡng minconf. Các luật có dang X — Y trong đó X, Y là 1 tập các item. Thuật toán apriori.
Nguyên tắc Apriori Nếu một tập các mặt hàng là thường xuyên thì tất cả các tập con của nó cũng là thường xuyên [1]. VX,Y:(XcY)>s(X)>s(Y) Nhờ có nguyên lý này, số lượng các ứng cử viên giảm đi đáng ké khi xác định được một tập mặt hàng nào đó không thỏa mãn là tập thường xuyên. Hình vẽ sau mô tả nguyên lý Apriori trong đó tập mặt hang {AB} được tìm thấy là không thường xuyên nên tất cả các tập mặt hàng mà nhận {AB} là tập con đều được cho là không thường xuyên và được cắt bỏ toàn bộ (phần được khoanh màu đỏ trong hình vẽ). Nguyễn Thái Hoàng — B17DCCN264 20 Dé án tốt nghiệp CE DE Duo tim thay / là không thường ⁄2S+»-2X_— ><— -“ XNỊ xuyên @ @ @ 1 2G S© ôe WA SL i V ` (ABŒD ABCE ABDE ` ` ACDE BCDE `.
S27 được cat bỏ đi ~~-~. 2 Mô tả cách thức hoạt động của nguyên tắc Apriori [1]. Thuật toán Apriori giảm số lượng ứng viên e Gan k=l e Sinh ra một tap mat hang với độ dài là 1 e Lap cho tới khi không còn tập mặt hang mới nao được xác định o Sinh ra các tập mặt hàng với (k+1) phan tử từ các tập mặt hàng với k phần tử. o Cắt bỏ những tập mặt hàng chứa tập con có độ dài k mà không phải là tập thường xuyên.
o_ Đếm số hỗ trợ của mỗi ứng viên bang cách quét toàn bộ cơ sở dữ liệu. o_ Loại bỏ những ứng viên không phải thường xuyên, chỉ dé lại những tập mặt hàng thường xuyên [1]. Phương pháp sinh luật kết hợp Sau khi tìm được các tập mặt hàng thường xuyên, nhiệm vụ tiếp theo là xác định luật kết hợp từ các tập mặt hàng thường xuyên đó. Bài toán được phát biểu như sau: Cho một tập các mặt hàng thường xuyên L, hãy tìm tất cả các tập con f không rỗng của L sao cho f > L _ f thỏa mãn yêu cầu về độ tin cậy nhỏ nhất [1].
Ta thấy sỐ lượng luật kết hợp khá lớn (cấp lũy thừa) nên có vấn đề về độ phúc tạp tính toán. Van đề đặt ra ở đây là làm thé nào dé sinh luật kết hợp từ các tập mặt hàng thường xuyên một cách có hiệu quả. Ta thấy độ tin cậy của các luật được sinh ra từ cùng một tập mặt hàng có thuộc tính đơn điệu. Nguyễn Thái Hoàng — B17DCCN264 21 Dé án tốt nghiệp Ví dụ L={A,B,C,D}: c(ABC > D) = c(AB > CD) > c(A > BCD) Chính vì vậy ta có thé áp dung kỹ thuật cắt cành (loại bỏ) dé giảm số lượng các luật sinh ra thỏa mãn yêu câu về độ tin cậy.
ABCD= >U y dưới yalee ` gel SẼ S ie ngưỡ 3 BCD=>A ` “. | ACD=>B ABD=>C ABC=>D / ` 1 CD=>AB BD=>AC BC=>AD \. AD=>BC AC=>BD AB=>CD \ \ \ ` op D=>ABC C=>ABD B=>ACD) ‘ A=>BCD Các luats _ am bicatdi ~~~ oe a il Hình 2. 3 Kĩ thuật cắt cành giảm số lượng luật sinh ra [1].
Ví dụ sử dụng thuật toán Apriori trong khai phá luật kết hop Giả sử có tập dữ liệu giao dịch như sau: Hình 2. 4 Ví dụ tập đữ liệu giao địch [3]. Nguyễn Thái Hoàng — BI7DCCN264 22 Dé án tốt nghiệp Thuật toán Apriori được thức hiện như hình sau: ID min-sup=2 “—=— | L " — Tid items litemsets| sup itemsets sup 1 A,C,D Cy, {A} 2 {A} 2 2 B,C,E 1°! scan > 2 3 Ly ; {B} 3 4 3 A,B,C,E C 3 {C} 3 BE Pin —Sep)—_ | {E}| 3| itamsets sup C;| itemsets sup C:|itemsets {A.C} 2 ma: {A,C} 2 | 2“scan | {AC} (.E) {CE) 2 {CE) Ne itemsets litemsets| sup \ ) | {A,B,C} |2" scan Ly , |itemsets| sup \ {B. Quá trình thực hiện thuật toán Apriori [3].
Ta có frequent itemsets I ={B,C,E}, với minconf = 80% ta có 2 luật kết hợp là{B,C} => {E} và {C,E} => {B} min-conf = 80% Confidence Hình 2. 6 Sinh luật kết hợp [3] 2. Két luan Chương 2 đã trình bày khái niệm về khai phá luật kết hợp, các thuật ngữ trong khai phá luật kết hợp, giới thiệu thuật toán Apriori, phương pháp sinh luật kết hợp, đồng thời đưa ra ví dụ sử dụng thuật toán Apriori trong khai phá luật kết hợp. Nội dung chương tiếp theo sẽ trình bày về mô tả và phân tích của hệ thống.
Nguyễn Thái Hoàng — BI7DCCN264 23 Dé án tốt nghiệp CHƯƠNG 3: ĐẶC TẢ VÀ PHÂN TÍCH HỆ THÓNG Nội dung chương 3 bao gồm: - Mô tả chỉ tiết hệ thống. - Phan tích hệ thống. Mô tả hệ thống Nội dung phần này trình bày về yêu cầu hệ thống bao gồm: mục đích, phạm vi, mô tả chung và mô tả nghiệp vụ. Mục dich Hệ thống được sử dung đê cung cấp 1 website nghe nhạc, tải nhạc trực tuyến nhằm phục vụ cho nhu cầu giải trí.
Hệ thống có một số chức năng nổi bật như: gợi ý bài hát, thanh toán trực tuyến, tự động cập nhật bảng xếp hạng. Phạm vi Về đối tượng sử dụng, hệ thống cho phép các đối tượng sau được sử dụng: e Quản trị viên: Người quản lý trang web. e Người nghe: Người tham gia nghe nhạc trên trang web. Chức năng hỗ trợ: e Người nghe: Tim kiếm bài hát, ca sĩ, danh sách phát, nhạc sĩ.
Xem danh sách bài hát, ca sĩ, danh sách phát, nhạc sĩ.