Thuật toán Apriori trong data mining

Thuật toán Apriori trong data mining

Rate this post

Thuật toán Apriori đang nói về thuật toán được sử dụng để tìm hiểu các quy tắc kết hợp giữa các đối tượng trong data mining. Nó có nghĩa là hai hoặc nhiều đối tượng có liên quan với nhau như thế nào. Nói cách khác, chúng ta có thể nói rằng thuật toán apriori là một quy tắc kết hợp nghiêng về phân tích rằng những người đã mua sản phẩm A cũng đã mua sản phẩm B.

Các bài viết liên quan:

Mục tiêu chính của thuật toán apriori là tạo quy tắc kết hợp giữa các đối tượng khác nhau. Quy tắc kết hợp mô tả cách hai hoặc nhiều đối tượng có liên quan với nhau. Thuật toán Apriori còn được gọi là khai thác mẫu thường xuyên. Nói chung, bạn vận hành thuật toán Apriori trên cơ sở dữ liệu bao gồm một số lượng lớn các giao dịch. Hãy hiểu thuật toán apriori với sự trợ giúp của một ví dụ; giả sử bạn đến Big Bazar và mua các sản phẩm khác nhau. Nó giúp khách hàng mua sản phẩm của họ một cách dễ dàng và tăng hiệu suất bán hàng của Big Bazar. Trong hướng dẫn này, chúng ta sẽ thảo luận về thuật toán apriori với các ví dụ.

Giới thiệu

Chúng tôi lấy một ví dụ để hiểu rõ hơn về khái niệm này. Bạn hẳn đã nhận thấy rằng người bán hàng ở cửa hàng Pizza làm một combo gồm bánh pizza, nước ngọt và bánh mì. Anh ấy cũng giảm giá cho những khách hàng của họ mua những combo này. Bạn có bao giờ nghĩ tại sao anh ấy lại làm như vậy không? Ông cho rằng khách hàng mua pizza cũng mua nước ngọt và bánh mì. Tuy nhiên, bằng cách làm combo, anh ấy đã làm cho khách hàng dễ dàng. Đồng thời, anh ta cũng tăng hiệu suất bán hàng của mình.

Tương tự, bạn đến Big Bazar, và bạn sẽ thấy bánh quy, khoai tây chiên và Sôcôla được gói lại với nhau. Nó cho thấy rằng người bán hàng tạo sự thoải mái cho khách hàng khi mua những sản phẩm này ở cùng một địa điểm.

Hai ví dụ trên là những ví dụ điển hình nhất về Quy tắc kết hợp trong Khai thác dữ liệu. Nó giúp chúng ta tìm hiểu khái niệm về thuật toán apriori.

Thuật toán Apriori là gì?

Apriori là thuật toán sử dụng khai thác các tập đối tượng trong dữ liệu có mối quan hệ liên quan với nhau. 

Ví dụ, các mặt hàng của khách hàng nhưng tại một siêu thị thì thuật toán Apriori giúp khách hàng mua sản phẩm của họ một cách dễ dàng và tăng hiệu suất bán hàng của cửa hàng cụ thể.

Các thành phần của thuật toán Apriori

Ba thành phần đã cho bao gồm thuật toán apriori.

  • Support
  • Confidence
  • Lift 

Hãy lấy một ví dụ để hiểu khái niệm này.

Chúng tôi đã thảo luận ở trên; bạn cần một cơ sở dữ liệu khổng lồ chứa một lượng lớn giao dịch. Giả sử bạn có 4000 khách hàng giao dịch trong Big Bazar. Bạn phải tính toán Hỗ trợ, Độ tin cậy và Mức tăng cho hai sản phẩm và bạn có thể nói là Bánh quy và Sô cô la. Điều này là do khách hàng thường xuyên mua hai mặt hàng này cùng nhau.

Trong số 4000 giao dịch, 400 giao dịch chứa Bánh quy, trong khi 600 giao dịch chứa Sô cô la và 600 giao dịch này bao gồm 200 giao dịch bao gồm Bánh quy và sô cô la. Sử dụng dữ liệu này, chúng tôi sẽ tìm ra sự hỗ trợ, sự tự tin và mức tăng.

Support

Hỗ trợ đề cập đến mức độ phổ biến mặc định của bất kỳ sản phẩm nào. Bạn nhận thấy hỗ trợ là thương số của phép chia số lượng giao dịch bao gồm sản phẩm đó cho tổng số giao dịch. Do đó, chúng tôi nhận được

Support (Biscuits) = ( Các transaction liên quan đến bánh quy) / (tổng transactions) = 400/4000 = 10 percent.

Confidence

Sự tin cậy đề cập đến khả năng khách hàng đã mua cả bánh quy và sôcôla cùng nhau. Vì vậy, bạn cần chia số lượng giao dịch bao gồm cả bánh quy và sôcôla cho tổng số giao dịch để lấy độ tin cậy.

Confidence = (giao dịch của biscuits và Chocolate) / (Tổng số giao dịch liên quan đến Biscuits) = 200/400 = 50 percent.

Có nghĩa là 50% khách hàng mua bánh quy cũng đã mua sôcôla.

Lift 

Hãy xem xét ví dụ trên; tăng đề cập đến việc tăng tỷ lệ bán sôcôla khi bạn bán bánh quy. Các phương trình toán học của lực nâng được đưa ra dưới đây.

Lift  = (Confidence  ( biscuits – Chocolate ) / Support (Biscuits) )= 50/10 = 5

Điều đó có nghĩa là xác suất để mọi người mua cả bánh quy và sôcôla cùng nhau gấp 5 lần so với xác suất mua một mình bánh quy. Nếu giá trị thang máy thấp hơn một, điều đó đòi hỏi mọi người không có khả năng mua cả hai mặt hàng cùng nhau. Giá trị càng lớn thì càng tốt.

Thuật toán Apriori hoạt động như thế nào trong Khai thác dữ liệu?

Chúng tôi sẽ hiểu thuật toán này với sự trợ giúp của một ví dụ

Hãy xem xét một kịch bản Big Bazar trong đó bộ sản phẩm là P = {Rice, Pulse, Oil, Milk, Apple}. Cơ sở dữ liệu bao gồm sáu giao dịch trong đó 1 đại diện cho sự hiện diện của sản phẩm và 0 đại diện cho sự vắng mặt của sản phẩm.

Thuật toán Apriori trong data mining

Thuật toán Apriori đưa ra các giả định

Tất cả các tập con của một tập phổ biến phải thường xuyên.

Các tập hợp con của một tập hợp mục không thường xuyên phải không thường xuyên.

Sửa một ngưỡng hỗ trợ ld. Trong trường hợp của chúng tôi, chúng tôi đã cố định nó ở mức 50 phần trăm.

Bước 1

Lập bảng tần suất của tất cả các sản phẩm xuất hiện trong tất cả các giao dịch. Bây giờ, hãy rút ngắn bảng tần suất để chỉ thêm những sản phẩm có ngưỡng hỗ trợ trên 50 phần trăm. Chúng tôi tìm bảng tần số đã cho.

Thuật toán Apriori trong data mining

Bảng trên chỉ ra các sản phẩm được khách hàng mua thường xuyên.

Bước 2

Tạo các cặp sản phẩm như RP, RO, RM, PO, PM, OM. Bạn sẽ nhận được bảng tần số đã cho.

Thuật toán Apriori trong data mining

Bước 3

Thực hiện cùng ngưỡng hỗ trợ 50 phần trăm và xem xét các sản phẩm cao hơn 50 phần trăm. Trong trường hợp của chúng tôi, nó nhiều hơn 3

Do đó, chúng tôi nhận được RP, RO, PO và PM

Bước 4

Bây giờ, hãy tìm bộ ba sản phẩm mà khách hàng mua cùng nhau. Chúng tôi nhận được sự kết hợp đã cho.

RP và RO cho RPO

PO và PM cung cấp POM

Bước 5

Tính tần số của hai tập phổ, và bạn sẽ nhận được bảng tần số đã cho.

Thuật toán Apriori trong data mining

Nếu bạn thực hiện giả định ngưỡng, bạn có thể tìm ra rằng bộ ba sản phẩm của khách hàng là RPO.

Chúng tôi đã xem xét một ví dụ dễ dàng để thảo luận về thuật toán apriori trong khai thác dữ liệu. Trong thực tế, bạn tìm thấy hàng ngàn sự kết hợp như vậy.

Làm thế nào để nâng cao hiệu quả của Thuật toán Apriori?

Có nhiều phương pháp khác nhau được sử dụng để tăng hiệu quả của thuật toán Apriori

Đếm tập hợp vật phẩm dựa trên băm

Trong đếm tập vật phẩm dựa trên băm, bạn cần loại trừ tập hợp k có số lượng nhóm băm tương đương ít hơn ngưỡng là tập hợp vật phẩm không thường xuyên.

Giảm giao dịch

Khi giảm giao dịch, một giao dịch không liên quan đến bất kỳ tập vật phẩm X thường xuyên nào sẽ không có giá trị trong các lần quét tiếp theo.

Thuật toán Apriori trong khai thác dữ liệu

Chúng ta đã thảo luận về một ví dụ về thuật toán apriori liên quan đến việc tạo tập phổ biến. Thuật toán Apriori có nhiều ứng dụng trong khai thác dữ liệu.

Các yêu cầu chính để tìm các quy tắc kết hợp trong khai thác dữ liệu được đưa ra dưới đây.

Sử dụng Brute Force

Phân tích tất cả các quy tắc và tìm mức hỗ trợ và mức độ tin cậy cho quy tắc riêng lẻ. Sau đó, loại bỏ các giá trị nhỏ hơn ngưỡng hỗ trợ và mức độ tin cậy.

Phương pháp tiếp cận hai bước

Phương pháp tiếp cận hai bước là một lựa chọn tốt hơn để tìm các quy tắc kết hợp so với phương pháp Brute Force.

Bước 1

Trong bài viết này, chúng ta đã thảo luận về cách tạo bảng tần suất và tính toán các tập hợp vật phẩm có giá trị hỗ trợ lớn hơn giá trị của ngưỡng hỗ trợ.

Bước 2

Để tạo các quy tắc kết hợp, bạn cần sử dụng một phân vùng nhị phân của các tập phổ biến. Bạn cần chọn những người có mức độ tin cậy cao nhất.

Trong ví dụ trên, bạn có thể thấy rằng kết hợp RPO là tập phổ biến. Bây giờ, chúng tôi tìm hiểu tất cả các quy tắc sử dụng RPO.

RP-O, RO-P, PO-R, O-RP, P-RO, R-PO

Bạn có thể thấy rằng có sáu cách kết hợp khác nhau. Do đó, nếu bạn có n phần tử, sẽ có 2n – 2 quy tắc kết hợp ứng cử viên.

Ưu điểm của thuật toán Apriori

  • Nó được sử dụng để tính toán các tập phổ biến lớn.
  • Đơn giản để hiểu và áp dụng.
  • Nhược điểm của thuật toán Apriori
  • Thuật toán Apriori là một phương pháp tốn kém để tìm hỗ trợ vì phép tính phải chuyển qua toàn bộ cơ sở dữ liệu.

Đôi khi, bạn cần một số lượng lớn các quy tắc ứng cử viên, vì vậy nó trở nên tốn kém hơn về mặt tính toán.

Leave a Reply