TỔNG QUAN VỀ KHAI PHÁ LUẬT KẾT HỢP

Tình huống ứng dụng

Phân tích giỏ hàng (Basket Analysis): Xác định các sản phẩm thường được mua cùng nhau trong một giao dịch. Ví dụ: khách hàng mua bia thường mua tã lót cùng lúc vào cuối tuần.

Hệ thống gợi ý (Recommendation): Dựa trên lịch sử mua hàng hoặc hành vi của người dùng tương tự để đề xuất sản phẩm/nội dung phù hợp.

Các ứng dụng khác:

• Thiết kế catalog và bố trí hàng hóa trong siêu thị.

• Cross-marketing – khuyến mãi chéo giữa các sản phẩm.

• Phân loại và phân cụm dựa trên các mẫu phổ biến (frequent patterns).

• Phân tích rủi ro trong tài chính, y tế, an ninh mạng.

Quy trình khai phá luật kết hợp

1. Tiền xử lý (Pre-processing): Làm sạch dữ liệu, chuyển đổi về dạng giao dịch.

2. Khai phá (Mining): Tìm các tập phổ biến và sinh luật kết hợp.

3. Hậu xử lý (Post-processing): Lọc, đánh giá và trình bày kết quả cho người dùng.

CÁC KHÁI NIỆM CƠ BẢN

Định nghĩa nền tảng

• Item (mục): Một đối tượng quan tâm, ví dụ: một sản phẩm, một từ khóa.

• Tập items (Itemset): Tập hợp gồm một hoặc nhiều item. k-itemset là itemset có đúng \(k\) item.

• \(J = \{I_1, I_2, \ldots, I_m\}\): Tập tất cả \(m\) item trong tập dữ liệu.

• Giao dịch (Transaction): Một bản ghi trong tập dữ liệu giao dịch; là một tập các item thuộc cùng một giao dịch. Mỗi giao dịch \(T\) thỏa \(T \subseteq J\).

• Tập dữ liệu giao dịch \(D\): Tập hợp tất cả các giao dịch.

Kết hợp và luật kết hợp

• Kết hợp (Association): Sự xuất hiện đồng thời của các item trong cùng một giao dịch.

• Luật kết hợp (Association rule): \(A \Rightarrow B\), với \(A\) và \(B\) là các itemset (\(A \cap B = \emptyset\)), biểu diễn rằng khi \(A\) xuất hiện thì \(B\) có xu hướng xuất hiện.

Support (Độ phổ biến)

Support đo lường tần suất xuất hiện của một itemset trong tập dữ liệu: \[\text{support}(A) = \frac{|\{T \in D \mid A \subseteq T\}|}{|D|}\]

Với luật \(A \Rightarrow B\): \[\text{support}(A \Rightarrow B) = \text{support}(A \cup B) = \frac{|\{T \in D \mid A \cup B \subseteq T\}|}{|D|}\]

Ngưỡng support tối thiểu (MinSup): giá trị support tối thiểu do người dùng định nghĩa để xác định tập phổ biến.

Confidence (Độ tin cậy)

Confidence đo lường xác suất có điều kiện – tần suất \(B\) xuất hiện khi \(A\) đã xuất hiện: \[\text{confidence}(A \Rightarrow B) = P(B \mid A) = \frac{\text{support}(A \cup B)}{\text{support}(A)}\]

Ngưỡng confidence tối thiểu (MinConf): giá trị confidence tối thiểu do người dùng định nghĩa.

Tập phổ biến và luật kết hợp mạnh

• Tập phổ biến (Frequent itemset): Itemset \(A\) thỏa \(\text{support}(A) \geq \text{MinSup}\).

• Luật kết hợp mạnh (Strong association rule): Luật \(A \Rightarrow B\) thỏa đồng thời: \[\text{support}(A \Rightarrow B) \geq \text{MinSup} \quad \text{và} \quad \text{confidence}(A \Rightarrow B) \geq \text{MinConf}\]

Ví dụ minh họa

Xét tập dữ liệu 9 giao dịch, với các item \(\{I1, I2, I3, I4, I5\}\). Nếu \(\text{MinSup} = 2/9\) và itemset \(\{I1, I2\}\) xuất hiện trong 4 giao dịch: \[\text{support}(\{I1,I2\}) = \frac{4}{9} \approx 44\% \geq \text{MinSup}\] Luật \(I1 \Rightarrow I2\) có confidence: \[\text{confidence}(I1 \Rightarrow I2) = \frac{\text{support}(\{I1,I2\})}{\text{support}(\{I1\})} = \frac{4/9}{6/9} = \frac{4}{6} \approx 66.7\%\]

PHÂN LOẠI LUẬT KẾT HỢP

• Boolean vs. Quantitative:

  • Boolean: Biểu diễn sự xuất hiện/vắng mặt của item. Ví dụ: Computer \(\Rightarrow\) Financial_SW [sup=50%, conf=60%].

  • Quantitative: Liên quan đến các thuộc tính định lượng. Ví dụ: Age(X,"30..39") \(\Rightarrow\) Buys(X, "TV") [sup=50%, conf=60%].

• Single-dimensional vs. Multidimensional:

  • Single-dimensional: Chỉ liên quan đến một chiều dữ liệu (ví dụ: buys).

  • Multidimensional: Liên quan đến nhiều chiều (ví dụ: age, income, buys).

• Single-level vs. Multilevel:

  • Single-level: Tất cả item ở cùng mức trừu tượng.

  • Multilevel: Item ở nhiều mức trừu tượng khác nhau (ví dụ: laptop và computer là hai mức của cùng một khái niệm).

• Association rule vs. Correlation rule: Luật kết hợp chỉ dựa trên support/confidence; luật tương quan bổ sung thêm các độ đo thống kê (lift, \(\chi^2\), …).

BIỂU DIỄN LUẬT KẾT HỢP

Dạng chuẩn của luật kết hợp: \[A \Rightarrow B \quad [\text{support} = s\%, \; \text{confidence} = c\%]\] trong đó:

• \(A, B\) là các tập phổ biến (frequent itemsets), \(A \cap B = \emptyset\).

• \(\text{support}(A \Rightarrow B) = \text{support}(A \cup B) \geq \text{MinSup}\).

• \(\text{confidence}(A \Rightarrow B) = \dfrac{\text{support}(A \cup B)}{\text{support}(A)} \geq \text{MinConf}\).

KHAI PHÁ TẬP PHỔ BIẾN – HAI BƯỚC

Khai phá luật kết hợp gồm hai bước chính:

1. Bước 1 – Tìm tập phổ biến: Tìm tất cả itemset có support \(\geq\) MinSup. Đây là bước tốn kém nhất về tính toán.

2. Bước 2 – Sinh luật kết hợp: Từ mỗi tập phổ biến \(L\), sinh tất cả các luật \(A \Rightarrow (L \setminus A)\) thỏa MinConf.

THUẬT TOÁN APRIORI

Ý tưởng và tính chất Apriori

Apriori (Agrawal & Srikant, VLDB 1994) khai phá tập phổ biến bằng cách tận dụng tính chất Apriori (Apriori property):

Hệ quả (Anti-monotone property): Nếu \(X\) không phải tập phổ biến thì \(X \cup Y\) (với \(Y\) bất kỳ) cũng không phải tập phổ biến. Tính chất này cho phép cắt tỉa không gian tìm kiếm hiệu quả.

Pseudo-code của Apriori

Ck: tập ứng viên k-itemset
Lk: tập phổ biến k-itemset

L1 = {frequent 1-itemsets};
k = 1;
while (Lk != empty) {
    k++;
    Ck = apriori_gen(Lk-1);      // sinh ứng viên từ Lk-1
    for each transaction t in D {
        Ct = subset(Ck, t);       // ứng viên chứa trong t
        for each candidate c in Ct
            c.count++;            // tăng bộ đếm
    }
    Lk = {c in Ck | c.count >= min_sup_count};
}
return Union(Lk);

Sinh tập ứng viên (apriori_gen)

Gồm hai bước:

Bước 1 – Self-joining (tự nối): Từ \(L_{k-1}\), nối hai itemset có \(k-2\) item đầu giống nhau:

INSERT INTO Ck
SELECT p.item1, ..., p.itemk-1, q.itemk-1
FROM   Lk-1 p, Lk-1 q
WHERE  p.item1=q.item1, ..., p.itemk-2=q.itemk-2,
       p.itemk-1 < q.itemk-1

Bước 2 – Pruning (cắt tỉa): Loại bỏ ứng viên \(c \in C_k\) nếu bất kỳ \((k-1)\)-subset nào của \(c\) không có trong \(L_{k-1}\).

Ví dụ minh họa Apriori

Tập dữ liệu \(D\) gồm 4 giao dịch, MinSup = 2:

Vòng lặp 1: \(C_1 = \{\{1\},\{2\},\{3\},\{4\},\{5\}\}\). Sau khi quét \(D\): \(L_1 = \{\{1\}^2, \{2\}^3, \{3\}^3, \{5\}^3\}\) (loại \(\{4\}\) vì sup=1 < 2).

Vòng lặp 2: Tự nối \(L_1\) sinh \(C_2\). Sau khi quét: \(L_2 = \{\{1,3\}^2, \{2,3\}^2, \{2,5\}^3, \{3,5\}^2\}\).

Vòng lặp 3: Sinh \(C_3 = \{\{2,3,5\}\}\) (các ứng viên khác bị cắt tỉa). Sau quét: \(L_3 = \{\{2,3,5\}^2\}\).

Vòng lặp 4: \(C_4 = \emptyset \Rightarrow\) dừng.

Đặc điểm và hạn chế của Apriori

• Ưu điểm: Dễ hiểu, tận dụng tính chất Apriori để cắt tỉa không gian tìm kiếm.

• Hạn chế:

  • Quét toàn bộ tập dữ liệu nhiều lần (mỗi cấp độ \(k\) quét một lần).

  • Sinh ra số lượng lớn tập ứng viên, tốn bộ nhớ.

  • Không hiệu quả với tập dữ liệu lớn hoặc MinSup thấp.

THUẬT TOÁN FP-GROWTH

FP-Growth (Han, Pei, Yin – SIGMOD 2000) khai phá tập phổ biến không sinh tập ứng viên, sử dụng cấu trúc FP-tree (Frequent Pattern tree).

Ý tưởng chính:

1. Xây dựng FP-tree: Nén tập dữ liệu vào một cây tiền tố (prefix tree). Chỉ cần quét dữ liệu 2 lần.

2. Khai phá FP-tree: Phân tích từng nhánh của cây theo phương pháp “divide and conquer” để tìm tập phổ biến mà không sinh ứng viên.

Ưu điểm so với Apriori:

• Không sinh tập ứng viên \(\Rightarrow\) giảm đáng kể bộ nhớ.

• Chỉ quét dữ liệu 2 lần \(\Rightarrow\) hiệu quả hơn với tập dữ liệu lớn.

• Hiệu quả với MinSup thấp.

KHAI PHÁ LUẬT KẾT HỢP TỪ TẬP PHỔ BIẾN

Từ mỗi tập phổ biến \(L\) (với \(|L| \geq 2\)), sinh tất cả các luật \(A \Rightarrow (L \setminus A)\) (\(A \neq \emptyset\)) và giữ lại những luật thỏa MinConf.

Tính chất đơn điệu của confidence: Với luật \(A \Rightarrow (L \setminus A)\), nếu luật không thỏa MinConf thì bất kỳ luật nào có vế trái là tập con của \(A\) cũng không thỏa. Tính chất này cho phép cắt tỉa bước sinh luật.

Ví dụ: Từ \(L_3 = \{2, 3, 5\}\) (sup = 2), sinh các luật:

• \(\{2,3\} \Rightarrow \{5\}\): conf = \(2/2 = 100\%\)

• \(\{2,5\} \Rightarrow \{3\}\): conf = \(2/3 = 66.7\%\)

• \(\{3,5\} \Rightarrow \{2\}\): conf = \(2/2 = 100\%\)

• \(\{2\} \Rightarrow \{3,5\}\): conf = \(2/3 = 66.7\%\)

• \(\{3\} \Rightarrow \{2,5\}\): conf = \(2/3 = 66.7\%\)

• \(\{5\} \Rightarrow \{2,3\}\): conf = \(2/3 = 66.7\%\)

KHAI PHÁ CÓ RÀNG BUỘC (CONSTRAINT-BASED MINING)

Trong thực tế, người dùng chỉ quan tâm đến một tập con các luật thỏa mãn điều kiện cụ thể. Các loại ràng buộc:

• Knowledge type constraint: Chỉ khai phá loại luật nhất định (ví dụ: chỉ luật Boolean).

• Data constraint: Giới hạn trên tập item cụ thể (ví dụ: chỉ sản phẩm điện tử).

• Dimension/level constraint: Giới hạn chiều dữ liệu hoặc mức trừu tượng.

• Rule constraint: Ràng buộc trực tiếp trên cấu trúc luật (ví dụ: vế trái chứa ít nhất 2 item).

• Interestingness constraint: Ràng buộc trên support, confidence hoặc các độ đo khác.

Ràng buộc anti-monotone (như support) có thể dùng để cắt tỉa sớm trong quá trình khai phá.

PHÂN TÍCH TƯƠNG QUAN (CORRELATION ANALYSIS)

Luật kết hợp mạnh (thỏa MinSup và MinConf) chưa chắc đã biểu diễn quan hệ nhân quả hoặc tương quan thực sự. Cần bổ sung thêm các độ đo tương quan:

Lift (Độ nâng)

\[\text{lift}(A \Rightarrow B) = \frac{\text{confidence}(A \Rightarrow B)}{\text{support}(B)} = \frac{\text{support}(A \cup B)}{\text{support}(A) \cdot \text{support}(B)}\]

• \(\text{lift} > 1\): \(A\) và \(B\) tương quan thuận (positively correlated).

• \(\text{lift} = 1\): \(A\) và \(B\) độc lập (independent).

• \(\text{lift} < 1\): \(A\) và \(B\) tương quan nghịch (negatively correlated).

Độ đo \(\chi^2\) (Chi-square)

\[\chi^2 = \sum \frac{(O - E)^2}{E}\] trong đó \(O\) là tần suất quan sát, \(E\) là tần suất kỳ vọng. Nếu \(\chi^2 = 0\): hai item độc lập; \(\chi^2 > 0\): có tương quan.

Cosine similarity

\[\text{cosine}(A, B) = \frac{\text{support}(A \cup B)}{\sqrt{\text{support}(A) \cdot \text{support}(B)}}\]

TÓM TẮT

• Luật kết hợp \(A \Rightarrow B\) được đặc trưng bởi support và confidence.

• Khai phá gồm 2 bước: (1) tìm tập phổ biến; (2) sinh luật từ tập phổ biến.

• Apriori: Khai phá tập phổ biến dựa trên tính chất anti-monotone; quét dữ liệu nhiều lần.

• FP-Growth: Không sinh ứng viên, chỉ quét dữ liệu 2 lần; hiệu quả hơn Apriori.

• Luật kết hợp mạnh chưa đủ; cần bổ sung lift, \(\chi^2\) để đánh giá tương quan thực sự.

• Ràng buộc giúp người dùng tập trung vào các luật có ý nghĩa thực tiễn.

CÂU HỎI TỰ LUẬN

1. Khai phá luật kết hợp (association rule mining) là gì? Trình bày quy trình 3 bước của khai phá luật kết hợp và cho ví dụ ứng dụng trong thực tiễn.

2. Giải thích các khái niệm: item, itemset, k-itemset, transaction, tập dữ liệu giao dịch. Cho ví dụ minh họa với một tập dữ liệu giao dịch cụ thể.

3. Định nghĩa support và confidence của một luật kết hợp \(A \Rightarrow B\). Viết công thức và giải thích ý nghĩa của từng độ đo.

4. Tập phổ biến (frequent itemset) và luật kết hợp mạnh (strong association rule) được định nghĩa như thế nào? Tại sao cần cả hai điều kiện MinSup và MinConf?

5. Trình bày tính chất Apriori (Apriori property) và tính anti-monotone. Tính chất này được sử dụng như thế nào để giảm không gian tìm kiếm trong thuật toán Apriori?

6. Mô tả chi tiết các bước của thuật toán Apriori. Giải thích bước sinh tập ứng viên (apriori_gen) bao gồm self-joining và pruning. Minh họa bằng ví dụ.

7. Với tập dữ liệu \(D\) gồm các giao dịch: T1={A,B,C}, T2={A,C}, T3={A,D}, T4={B,E,F}, T5={A,B,C}. Với MinSup = 2, hãy thực hiện vòng lặp đầu tiên của Apriori: tìm \(C_1\) và \(L_1\).

8. So sánh Apriori và FP-Growth về: số lần quét dữ liệu, việc sinh tập ứng viên, bộ nhớ sử dụng và hiệu quả khi MinSup thấp.

9. FP-tree là gì? Trình bày ý tưởng xây dựng FP-tree và cách FP-Growth khai phá tập phổ biến từ FP-tree mà không sinh tập ứng viên.

10. Từ một tập phổ biến \(L = \{A, B, C\}\), hãy liệt kê tất cả các luật kết hợp có thể sinh ra. Giải thích cách áp dụng MinConf để lọc các luật không đủ điều kiện.

11. Phân biệt luật kết hợp Boolean và luật kết hợp định lượng (quantitative). Cho ví dụ cụ thể cho mỗi loại.

12. Giải thích sự khác biệt giữa luật kết hợp đơn chiều (single-dimensional) và đa chiều (multidimensional). Luật đa chiều hữu ích trong tình huống nào?

13. Luật kết hợp đa mức (multilevel association rule) khác với luật đơn mức như thế nào? Ưu điểm của khai phá đa mức là gì? Thách thức nào phát sinh khi khai phá đa mức?

14. Trình bày các loại ràng buộc (constraints) trong khai phá luật kết hợp dựa trên ràng buộc. Ràng buộc anti-monotone khác với ràng buộc thông thường như thế nào?

15. Lift được định nghĩa như thế nào? Giải thích ý nghĩa của lift \(> 1\), lift \(= 1\) và lift \(< 1\). Tại sao lift quan trọng hơn chỉ dùng confidence?

16. Một luật kết hợp mạnh (thỏa MinSup và MinConf) có thể không có ý nghĩa thực sự không? Giải thích bằng ví dụ cụ thể và nêu cách khắc phục dùng lift hoặc \(\chi^2\).

17. Trình bày độ đo \(\chi^2\) (chi-square) trong phân tích tương quan. Khi nào \(\chi^2 = 0\) và điều đó có nghĩa gì?

18. Giải thích cosine similarity trong đánh giá luật kết hợp. So sánh cosine similarity với lift về ưu và nhược điểm.

19. Nêu và phân tích các hạn chế của thuật toán Apriori. Đề xuất ít nhất hai hướng cải tiến Apriori để tăng hiệu quả.

20. Khai phá luật kết hợp gồm hai bước: tìm tập phổ biến và sinh luật. Tại sao bước tìm tập phổ biến được coi là bước tốn kém nhất? Phân tích độ phức tạp tính toán của bước này.

CÂU HỎI TRẮC NGHIỆM

1. Khai phá luật kết hợp thuộc loại bài toán nào trong khai phá dữ liệu?

   1. Học có giám sát (supervised learning).

   2. Học không giám sát (unsupervised learning).

   3. Học bán giám sát (semi-supervised learning).

   4. Học tăng cường (reinforcement learning).

2. Phân tích giỏ hàng (basket analysis) trong khai phá luật kết hợp nhằm mục đích:

   1. Phân nhóm khách hàng theo hành vi mua hàng.

   2. Phát hiện các sản phẩm thường được mua cùng nhau trong một giao dịch.

   3. Dự đoán giá sản phẩm trong tương lai.

   4. Phân loại khách hàng theo thu nhập.

3. Một k-itemset là:

   1. Một giao dịch chứa đúng \(k\) item.

   2. Một tập hợp gồm đúng \(k\) item.

   3. Một luật có \(k\) item ở vế trái.

   4. Một tập phổ biến xuất hiện ít nhất \(k\) lần.

4. Support của luật \(A \Rightarrow B\) được tính bằng:

   1. \(P(A \mid B)\)

   2. \(P(A \cup B)\)

   3. \(P(B \mid A)\)

   4. \(P(A) \cdot P(B)\)

5. Confidence của luật \(A \Rightarrow B\) được tính bằng:

   1. \(\dfrac{\text{support}(A \cup B)}{\text{support}(A)}\)

   2. \(\dfrac{\text{support}(A)}{\text{support}(B)}\)

   3. \(\dfrac{\text{support}(A \cup B)}{|D|}\)

   4. \(\text{support}(A) + \text{support}(B)\)

6. Một itemset được gọi là tập phổ biến (frequent itemset) khi:

   1. support \(\geq\) MinConf.

   2. confidence \(\geq\) MinSup.

   3. support \(\geq\) MinSup.

   4. lift \(\geq 1\).

7. Một luật \(A \Rightarrow B\) được gọi là luật kết hợp mạnh khi:

   1. support \(\geq\) MinSup hoặc confidence \(\geq\) MinConf.

   2. support \(\geq\) MinSup và confidence \(\geq\) MinConf.

   3. lift \(> 1\) và confidence \(\geq\) MinConf.

   4. support \(\geq\) MinSup và lift \(> 1\).

8. Nếu support(\(\{A,B\}\)) = 0.4 và support(\(\{A\}\)) = 0.5, thì confidence(\(A \Rightarrow B\)) bằng:

   1. 0.2

   2. 0.4

   3. 0.8

   4. 0.9

9. Tính chất Apriori (Apriori property) phát biểu rằng:

   1. Mọi superset của tập phổ biến đều là tập phổ biến.

   2. Mọi tập con của tập phổ biến đều là tập phổ biến.

   3. Mọi tập con của tập phổ biến đều không phổ biến.

   4. Chỉ itemset có đúng 1 phần tử mới là tập phổ biến.

10. Tính anti-monotone của Apriori nói rằng:

    1. Nếu \(X\) phổ biến thì \(X \cup Y\) cũng phổ biến.

    2. Nếu \(X\) không phổ biến thì \(X \cup Y\) cũng không phổ biến.

    3. Support tăng khi kích thước itemset tăng.

    4. Confidence không thể giảm khi thêm item vào vế trái.

11. Bước self-joining trong sinh tập ứng viên \(C_k\) từ \(L_{k-1}\) thực hiện:

    1. Loại bỏ ứng viên có subset không phổ biến.

    2. Nối hai itemset trong \(L_{k-1}\) có \(k-2\) item đầu giống nhau.

    3. Đếm support của tất cả ứng viên trong \(C_k\).

    4. Lọc ứng viên có support \(<\) MinSup.

12. Bước pruning trong sinh tập ứng viên \(C_k\) thực hiện:

    1. Nối các itemset trong \(L_{k-1}\).

    2. Đếm support của từng ứng viên.

    3. Loại bỏ ứng viên \(c \in C_k\) nếu có \((k-1)\)-subset của \(c\) không thuộc \(L_{k-1}\).

    4. Sinh ra tất cả \((k+1)\)-itemset từ \(C_k\).

13. Độ phức tạp của Apriori liên quan đến số lần quét tập dữ liệu là:

    1. 1 lần (một lần quét duy nhất).

    2. 2 lần.

    3. Bằng độ dài tập phổ biến dài nhất (\(k_{\max}\) lần).

    4. \(n\) lần với \(n\) là số giao dịch.

14. Với \(L_3 = \{abc, abd, acd, ace, bcd\}\), sau bước self-joining, tập ứng viên \(C_4\) ban đầu (trước pruning) gồm:

    1. \(\{abcd\}\)

    2. \(\{abcd, acde\}\)

    3. \(\{abcd, abce, abde\}\)

    4. \(\{abcde\}\)

15. Sau bước pruning trên \(C_4 = \{abcd, acde\}\) (với \(L_3\) như câu 14), kết quả là:

    1. \(C_4 = \{abcd, acde\}\) (không đổi).

    2. \(C_4 = \{abcd\}\) vì \(acde\) bị loại do \(ade \notin L_3\).

    3. \(C_4 = \emptyset\) vì cả hai đều bị loại.

    4. \(C_4 = \{acde\}\) vì \(abcd\) bị loại.

16. FP-Growth khác Apriori ở điểm quan trọng nào?

    1. FP-Growth cần xác định số cụm \(k\) trước.

    2. FP-Growth không sinh tập ứng viên và chỉ quét dữ liệu 2 lần.

    3. FP-Growth chỉ hoạt động với dữ liệu nhị phân.

    4. FP-Growth cần MinConf nhưng không cần MinSup.

17. FP-tree (Frequent Pattern tree) được sử dụng trong FP-Growth để:

    1. Lưu trữ danh sách tất cả tập ứng viên.

    2. Nén tập dữ liệu vào cấu trúc cây tiền tố, tránh sinh ứng viên.

    3. Biểu diễn dendrogram trong phân cụm.

    4. Tính toán confidence nhanh hơn.

18. Từ tập phổ biến \(L = \{A, B, C\}\) (sup = 3), support(\(\{A,B\}\)) = 3. Confidence(\(\{A,B\} \Rightarrow \{C\}\)) bằng:

    1. \(3/9 = 33\%\)

    2. \(3/3 = 100\%\)

    3. \(3/5 = 60\%\)

    4. Không tính được từ thông tin đã cho.

19. Khi sinh luật từ tập phổ biến, tính đơn điệu của confidence cho phép:

    1. Tính confidence mà không cần quét dữ liệu thêm.

    2. Cắt tỉa các luật có vế trái là tập cha của một luật không đủ MinConf.

    3. Tự động xác định giá trị MinConf tối ưu.

    4. Đảm bảo mọi luật sinh ra đều thỏa MinConf.

20. Luật “Age(X, “30..39”) \(\Rightarrow\) Buys(X, “TV”)” thuộc loại:

    1. Luật kết hợp Boolean đơn chiều.

    2. Luật kết hợp định lượng đa chiều.

    3. Luật kết hợp Boolean đa mức.

    4. Luật kết hợp tương quan.

21. Luật kết hợp đa mức (multilevel) có đặc điểm:

    1. Chỉ liên quan đến một chiều dữ liệu.

    2. Liên quan đến item ở nhiều mức trừu tượng khác nhau.

    3. Chỉ áp dụng với dữ liệu định lượng.

    4. Không cần MinSup để khai phá.

22. Ràng buộc anti-monotone trong khai phá có ràng buộc có nghĩa là:

    1. Ràng buộc làm tăng số lượng luật tìm thấy.

    2. Nếu một itemset vi phạm ràng buộc thì superset của nó cũng vi phạm, cho phép cắt tỉa sớm.

    3. Ràng buộc chỉ áp dụng cho vế phải của luật.

    4. Ràng buộc không ảnh hưởng đến hiệu quả khai phá.

23. Lift của luật \(A \Rightarrow B\) được tính bằng:

    1. \(\dfrac{\text{support}(A \cup B)}{\text{support}(A) \cdot \text{support}(B)}\)

    2. \(\dfrac{\text{confidence}(A \Rightarrow B)}{\text{support}(A)}\)

    3. \(\text{support}(A \cup B) - \text{support}(A) \cdot \text{support}(B)\)

    4. \(\dfrac{\text{support}(A)}{\text{support}(B)}\)

24. Nếu lift\((A \Rightarrow B) = 1\) thì:

    1. \(A\) và \(B\) tương quan thuận.

    2. \(A\) và \(B\) tương quan nghịch.

    3. \(A\) và \(B\) độc lập với nhau.

    4. Luật \(A \Rightarrow B\) không phải luật mạnh.

25. Nếu lift\((A \Rightarrow B) < 1\) thì:

    1. \(A\) và \(B\) tương quan thuận.

    2. \(A\) và \(B\) tương quan nghịch.

    3. \(A\) và \(B\) độc lập.

    4. Confidence của luật bằng 0.

26. Độ đo \(\chi^2 = 0\) trong phân tích tương quan có nghĩa là:

    1. Hai item hoàn toàn phụ thuộc nhau.

    2. Hai item hoàn toàn độc lập với nhau.

    3. Support của cả hai item bằng 0.

    4. Luật không thỏa MinConf.

27. Lý do chính cần bổ sung lift hoặc \(\chi^2\) bên cạnh support và confidence là:

    1. Để tính toán nhanh hơn.

    2. Luật kết hợp mạnh có thể biểu diễn quan hệ không có ý nghĩa thực hoặc tương quan nghịch.

    3. Để giảm số lượng tập ứng viên.

    4. Để tự động chọn MinSup và MinConf tối ưu.

28. Trong Apriori, \(C_k\) ký hiệu cho:

    1. Tập phổ biến k-itemset.

    2. Tập ứng viên k-itemset.

    3. Tập giao dịch có độ dài \(k\).

    4. Số lần quét dữ liệu thứ \(k\).

29. Trong Apriori, \(L_k\) ký hiệu cho:

    1. Tập ứng viên k-itemset.

    2. Tập phổ biến k-itemset (sau khi lọc theo MinSup).

    3. Tập giao dịch có ít nhất \(k\) item.

    4. Tập luật kết hợp có vế trái là k-itemset.

30. Khai phá luật kết hợp gồm hai bước; bước nào tốn kém nhất về tính toán?

    1. Bước 2: sinh luật từ tập phổ biến.

    2. Bước 1: tìm tất cả tập phổ biến.

    3. Cả hai bước có độ phức tạp như nhau.

    4. Bước tiền xử lý dữ liệu.

31. MinSup càng thấp thì:

    1. Số tập phổ biến càng ít.

    2. Số tập phổ biến càng nhiều, tính toán càng tốn kém.

    3. Thuật toán Apriori càng nhanh.

    4. Không ảnh hưởng đến số tập phổ biến.

32. Với tập dữ liệu \(D\) (4 giao dịch), MinSup = 2. Item {4} xuất hiện trong 1 giao dịch. Item {4} có phải tập phổ biến không?

    1. Có, vì support = 1/4 > 0.

    2. Không, vì support = 1 < MinSup = 2 (tính theo count).

    3. Có, nếu confidence \(\geq\) MinConf.

    4. Không đủ thông tin để kết luận.

33. Giả sử \(\{A, B\}\) không phổ biến. Theo tính chất anti-monotone, \(\{A, B, C\}\):

    1. Có thể phổ biến hoặc không.

    2. Chắc chắn phổ biến vì có thêm item \(C\).

    3. Chắc chắn không phổ biến.

    4. Phổ biến nếu \(\{C\}\) phổ biến.

34. Số lượng luật có thể sinh ra từ tập phổ biến \(L\) có \(n\) item là:

    1. \(n\)

    2. \(2^n - 2\)

    3. \(n^2\)

    4. \(n!\)

35. Cosine similarity trong đánh giá luật kết hợp được tính bằng:

    1. \(\dfrac{\text{support}(A \cup B)}{\text{support}(A) + \text{support}(B)}\)

    2. \(\dfrac{\text{support}(A \cup B)}{\sqrt{\text{support}(A) \cdot \text{support}(B)}}\)

    3. \(\dfrac{\text{confidence}(A \Rightarrow B)}{\text{confidence}(B \Rightarrow A)}\)

    4. \(\sqrt{\text{support}(A) \cdot \text{support}(B)}\)

36. Trong khai phá luật kết hợp dựa trên ràng buộc, ràng buộc nào sau đây là anti-monotone?

    1. Luật phải có ít nhất 3 item ở vế trái (min-constraint).

    2. Tổng giá trị item \(\leq\) 100 (sum-constraint).

    3. Support \(\geq\) MinSup.

    4. Confidence \(\geq\) MinConf.

37. Tại sao FP-Growth hiệu quả hơn Apriori với MinSup thấp?

    1. FP-Growth không cần MinSup.

    2. Khi MinSup thấp, số tập phổ biến lớn \(\Rightarrow\) Apriori sinh rất nhiều ứng viên; FP-Growth tránh được điều này.

    3. FP-Growth quét dữ liệu ít hơn 1 lần so với Apriori.

    4. FP-Growth chỉ hoạt động khi MinSup \(< 10\%\).

38. Khai phá luật kết hợp đa mức thường phải đối mặt với thách thức:

    1. Cần chọn \(k\) cụm trước khi khai phá.

    2. Cần định nghĩa MinSup khác nhau cho từng mức trừu tượng.

    3. Không thể áp dụng tính chất Apriori.

    4. Luôn sinh ra quá ít luật ở mức chi tiết.

ĐÁP ÁN

Câu hỏi tự luận – Hướng dẫn trả lời

Câu hỏi trắc nghiệm – Đáp án

Giải thích đáp án trắc nghiệm