Khai Phá Dữ Liệu Với Thuật Toán Apriori (Phần 1) - Quanghuy

Mở đầu

Trong lĩnh vực phá dữ liệu (Data mining) việc trích chọn ra được những thông tin cần thiết là rất quan trọng. Bài toán được áp dụng khi ta có một tập dữ liệu lớn về một đối tượng X nào đó mà ta đang quan tâm, muốn khảo sát, nhưng ta không biết làm thế nào để trích chọn ra thông tin quan trọng. Giả sử ta có tập dữ liệu về thông tin mua bán, hay hoá đơn bán hàng của siêu thị, từ đó ta có thể biết được những nhóm sản phẩm nào được mua nhiều nhất, hay ta có được dữ liệu của tất cả những comment của một diễn đàn, mà họ đang quan tâm về một sản phẩm X nào đó, ta có thể biết được họ đang tâm đến những đặc trưng gì về sản phẩm. Và tất nhiên, nếu ta đọc hết những lượng dữ liệu đó thì ta cũng có thể có được thông tin ta muốn, nhưng nếu lượng dữ liệu đó quá lớn thì thực sự ta đang phí thời gian, hãy để việc đó cho máy tính xử lý, việc của ta là tìm cách để máy tính làm được điều đó. Có rất nhiều thuật toán giúp ta thực hiện, nhưng hôm nay mình sẽ giới thiệu về thuật toán Apriori dựa trên luật kết hợp (Association Rule)

Luật kết hợp (Association Rule)

Phần đầu tiên, mình sẽ giới thiệu về luật kết hợp trong khai phá dữ liệu, luật kết hợp nhằm mục đích để tìm ra mối quan hệ giữa các đối tượng với nhau trong khối lượng lớn dữ liệu. Luật kết hợp có thể mô tả như sau:

Giả sử ta có một tập các dữ liệu, mỗi dữ liệu như một record trong database. Ví dụ: ta coi mỗi một đánh giá của người dùng cho sản phẩm X nào đó là một record, hoặc mỗi một hoá đơn mua hàng gồm n các sản phầm được mua là một record. Nhưng đối với luật kết hợp, ta gọi mỗi record là một transaction T. Ta có :

T = { t1, t2, t3, …} gọi là một tập các dữ liệu giao dịch ( transaction database )

Với mỗi một giao dịch T thường có một tập các thuộc tính item I. Ví dụ: mỗi một hoá đơn thường có một tập các mặt hàng như nước ngọt, giấy ăn, bàn chải, dầu gội, … mỗi mặt hàng ta coi là một item. Mỗi một comment về một sản phẩm X đang đề cập đến nhiều đặc trưng của X, mỗi một đặc trưng đó là một item i. Item chính là thông tin mà ta mong muốn có được trong mỗi Transaction. Ta có:

I = {i1, i2, i3, i4, …} gọi là các item của mỗi giao dịch T ( item set )

Và mục đich của luật kết hợp chính là tìm ra sự tương quan, dự kết hợp giữa các tập item đó với nhau. Luật kết hợp này có dạng X => Y. Ta có thể hiểu là nếu X xuất hiện thì Y cũng sẽ xuất hiện. Ví dụ: Trong hoá đơn mua hàng có X = { điện thoại, tai nghe } , Y = { sạc dự phòng, ốp điện thoại }, vậy nên ta có thể hiểu là, nếu người mua hàng mua điện thoại và tai nghe thì họ cũng hay mua sạc dự phòng và ốp điện thoại, chúng hay xuất hiện với nhau.

X được xem là biến độc lập (Independent variable) còn Y được xem là biến phụ thuộc (Dependent variable)

Độ hỗ trợ (Support)

Độ hỗ trợ (Support) của luật kết hợp X => Y là tần suất của giao dịch chứa tất cả các items trong cả hai tập X và Y. Ví dụ, support của luật X =>Y là 5% có nghĩa là  5% các giao dịch X và Y được mua cùng nhau.

Công thức để tính support của luật X =>Y như sau:

support( X -> Y) = P( X ∪ Y ) = n(X ∪ Y) / N 

n(X ∪ Y): số lần xuất hiện đồng thời X và Y

N: tổng số các giao dịch

Độ tin cây (Confidence)

Độ tin cậy (Confidence) của luật kết hợp X => Y là xác suất xảy ra Y khi đã biết X. Ví dụ độ tin cậy của luật kết hợp { điện thoại, tai nghe } => { sạc dự phòng, ốp điện thoại } là 80% có nghĩa là 80% khách hàng mua { điện thoại, tai nghe } thì cũng mua { sạc dự phòng, ốp điện thoại }.

Công thức để tính độ tin cậy của luật kết hợp X => là xác suất có điều kiện Y khi đã biết X như sau :

confidence( X -> Y) = P( X | Y ) = n(X ∪ Y) / n(X)

n(X ∪ Y) : số lần xuất hiện đồng thời X và Y

n(X): tổng số các giao dịch chứa X

Áp dụng các luật kết hợp

Ta thường áp dụng 2 tiêu chí: minimum support (min_sup) và  minimum confidence (min_conf)

Các luật thỏa mãn có support và confidence thỏa mãn (lớn hơn hoặc bằng)  cả Minimum support và Minimum confidence gọi là các luật mạnh (Strong Role)

Minimum support và Minimum confidence gọi là các giá trị ngưỡng (threshold) và phải xác định trước khi sinh các luật kết hợp.

Một itemsets mà tần suất xuất hiện của nó >= min_sup goi là frequent itemsets

Một số loại luật kết hợp

• Binary association rules (luật kết hợp nhị phân)
• Quantitative association rules (luật kết hợp định lượng):
• Fuzzy association rules (Luật kết hợp mờ)

Thuật toán phổ biến nhất tìm các luật kết hợp là Apriori sử dụng Binary association rules.

( Phần 2 )

Các tài liệu tham khảo

http://bis.net.vn/forums/t/389.aspx

Hu, M., and Liu, B. 2004. Mining Opinion Features in Customer Reviews. To appear in AAAI’04, 2004

Liu, B., Hsu, W., Ma, Y. 1998. Integrating Classification and Association Rule Mining. KDD’98, 1998.  

Minqing Hu and Bing Liu. Mining and Summarizing Customer Reviews, Department of Computer Science University of Illinois at Chicago

Share this:

• X
• More

• Facebook

Like Loading...