Nghiên cứu một số giải pháp đẩy nhanh tốc độ tính toán tập phổ biến, tìm luật kết hợp
Đại Học Quốc Gia TPHCM
Trường Đại Học Công Nghệ Thông Tin
***
ĐỒ ÁN MÔN HỌC
KHAI PHÁ DỮ LIỆU VÀ KHO DỮ LIỆU
NGHIÊN CỨU MỘT SỐ GIẢI
PHÁP ĐẨY NHANH TỐC ĐỘ
TÍNH TOÁN TẬP PHỔ BIẾN,
TÌM LUẬT KẾT HỢP
Giảng viên Phụ trách: PGS.TS. Đỗ Phúc
Học viên thực hiện: Nguyễn Đình Tấn
Mã số học viên: CH1101039
Thành Phố Hồ Chí Minh – 11/2012
Trang 1
Nghiên cứu một số giải pháp đẩy nhanh tốc độ tính toán tập phổ biến, tìm luật kết hợp
MỤC LỤC
LỜI MỞ ĐẦU 5
CHƯƠNG 1: TỔNG QUAN 6
1.1Nội dung thực hiện 6
1.2Dự kiến kết quả đạt được 6
CHƯƠNG 2: PHÂN TÍCH CÁC THUẬT GIẢI KHAI THÁC LUẬT KẾT HỢP
6
2.1Giới thiệu 6
2.1.1Luật kết hợp 6
2.1.2Nội dung trình bày trong phần này 8
2.1.3Các nghiên cứu liên quan 8
2.2Các nguyên lý cơ bản 9
2.2.1Mô tả bài toán 9
2.2.2Duyệt không gian tìm kiếm 10
2.2.3Xác định các Itemset Support 13
3.4.2Thuật giải Perfect Hashing and Pruning 33
3.5Phát sinh luật từ các tập phổ biến 37
3.5.1Cải tiến 6 - Giảm số lượng các luật được phát sinh & cần phải kiểm tra
38
3.5.2Cải tiến 6’ – Tránh phát sinh các luật không có ý nghĩa 39
3.5.3Một số kỹ thuật khác trong việc tối ưu hóa chi phí tính độ confident 41
CHƯƠNG 4: CÀI ĐẶT THỬ NGHIỆM 41
Trang 3
Nghiên cứu một số giải pháp đẩy nhanh tốc độ tính toán tập phổ biến, tìm luật kết hợp
4.1Môi trường cài đặt ứng dụng 41
4.2Cài đặt thử nghiệm 41
4.2.1Bài toán tìm tập phổ biến 41
4.2.2Bài toán tìm luật kết hợp 44
CHƯƠNG 5: KẾT LUẬN 45
Tài liệu tham khảo 46
Phụ Lục 46
LỜI MỞ ĐẦU
Trang 4
Nghiên cứu một số giải pháp đẩy nhanh tốc độ tính toán tập phổ biến, tìm luật kết hợp
Ngày nay, khi công cụ thu thập dữ liệu tự động và công nghệ lưu trữ dữ liệu ngày
càng hoàn thiện giúp con người tạo lập và quản lý một lượng dữ liệu khổng lồ
trong các cơ sở dữ liệu thì nhu cầu nắm bắt dữ liệu, trích rút thông tin trở thành
cấp thiết và có ý nghĩa to lớn.
Một trong những nhu cầu trích rút thông tin có ý nghĩa từ kho dữ liệu lớn là tính
toán tập phổ biến và tìm ra các luật kết hợp từ dữ liệu mua hàng như ở các siêu
thị, qua đó biết được xu hướng của thị trường. Từ đó có những chương trình và
chiến lược nhập hàng, bố trí mặt hàng phù hợp.
Tuy nhiên, việc tìm ra được các luật kết hợp trong một kho dữ liệu khổng lồ là
việc không dễ dàng, cần nhiều thời gian và tốc độ xử lý của máy tính cao. Do đó,
chung. Chúng ta cũng khảo sát một cách kỹ lưỡng các ưu khuyết điểm của các
giải thuật.
2.1 Giới thiệu
2.1.1 Luật kết hợp
Từ khi nó được giới thiệu từ năm 1993. Bài toán khai thác luật kết hợp nhận
được rất nhiều sự quan tâm của nhiều nhà khoa học. Ngày nay việc khai thác
Trang 6
Nghiên cứu một số giải pháp đẩy nhanh tốc độ tính toán tập phổ biến, tìm luật kết hợp
các luật như thế vẫn là một trong những phương pháp khai thác mẫu phổ
biến nhất trong việc khám phá tri thức và khai thác dữ liệu (KDD:
Knowledge Discovery and Data Mining).
Một cách ngắn gọn, một luật kết hợp là một biểu thức có dạng:
YX
⇒
, trong
đó
X
và
Y
là tập các trường gọi là item. Ý nghĩa của các luật kết hợp khá dễ
nhận thấy: Cho trước một cơ sở dữ liệu có
D
là tập các giao tác - trong đó
mỗi giao tác
DT ∈
là tập các item - khi đó
YX
⇒
diễn đạt ý nghĩa rằng bất
cứ khi nào giao tác
chiếm một tỷ lệ vô cùng nhỏ. Các nghiên cứu liên quan đến vấn đề thứ hai
hầu hết chú trọng vào việc giúp người dùng duyệt tập luật, và việc phát triển
các độ đo chất lượng của luật.
Trang 7
Nghiên cứu một số giải pháp đẩy nhanh tốc độ tính toán tập phổ biến, tìm luật kết hợp
2.1.2 Nội dung trình bày trong phần này
Trong bài này, chúng ta đề cập đến khía cạnh giải thuật của việc khai thác
luật kết hợp. Trên thực tế, rất nhiều giải thuật hiệu quả dùng cho việc khai
thác luật kết hợp đã được phát triển trong những năm gần đây. Ở đây, ta đã
thực hiện một cuộc khảo sát các ý tưởng cơ sở của khai thác luật kết hợp:
• Đưa ra những chiến lược cơ bản và mô tả chi tiết các chiến lược này.
• Kết quả này được sử dụng để hệ thống hóa và giới thiệu những cách tiếp
cận phổ biến hiện nay.
• Thêm vào đó, chúng ta cũng đưa ra những nguyên lý chung và sự khác
biệt giữa các giải thuật.
• Cuối cùng, chúng ta sẽ hoàn chỉnh một cách khái quát bằng cách so sánh
các giải thuật có liên quan đến tính hiệu quả. Sự so sánh này dựa trên
những xem xét lý thuyết và thực nghiệm cụ thể. Kết luận với một tóm tắt
ngắn về kết quả đạt được.
2.1.3 Các nghiên cứu liên quan
Các nghiên cứu được giới hạn trong phạm vi “bài toán luật kết hợp cổ điển”.
Đó là việc khai thác tất cả các luật tồn tại trong cơ sở dữ liệu D đối với các
ngưỡng tối thiểu trên một số độ đo chất lượng. Trong trường hợp này, D bao
gồm các dữ liệu market-basket, tức là các giao tác chứa trung bình 10-20
item trên tổng số 1000-100000 item.
Mặc dù “bài toán cổ điển” vẫn còn là một đề tài cho các nghiên cứu sâu hơn
nhưng trong những năm gần đây nhiều giải thuật dùng cho những công việc
đặc thù đã được phát triển. Trước hết, có rất nhiều hướng tiếp cận để nâng
cao các luật kết hợp. Ví dụ như: luật kết hợp số lượng (quantitative AR), luật
kết hợp tổng quát (generalized AR), và trong một phạm vi nào đó về mẫu
Như đã đề cập trước, khó khăn lớn nhất trong khai thác các luật kết hợp
chính là số lượng khổng lồ các luật cần phải xem xét về mặt lý thuyết. Trên
thực tế, số lượng luật tăng theo lũy thừa của |I|. Thực tế chứng minh là không
cần phải khai thác hết tất cả các luật này nên các tập luật thường được giới
hạn bởi các ngưỡng tối thiểu trên các độ hỗ trợ (minsupp) và độ tin cậy
(minconf). Giới hạn này cho phép ta chia bài toán thành 2 phần riêng biệt:
Một tập phần tử X là phổ biến nếu supp(X) ≥ minsupp. Khi, F = {X⊆I| X
Trang 9
Nghiên cứu một số giải pháp đẩy nhanh tốc độ tính toán tập phổ biến, tìm luật kết hợp
liên tục}, tập hợp tất cả các itemset cùng với các giá trị support của chúng
xác định, suy ra các luật kế hợp cần thiết là hiển nhiên: Với mỗi X∈F, kiểm
tra độ tin cậy của tất cả các luật X\Y ⇒ Y, Y ⊆ X, ∅≠Y≠X và bỏ những luật
không thỏa minconf. Theo định nghĩa trên, nó đủ để biết tất cả các giá trị hỗ
trợ của các tập con của X để tính độ tin cậy của mỗi luật. Tri thức về các giá
trị hỗ trợ của tất cả các tập con của X được bảo đảm bằng thuộc tính chặn
dưới đóng (downward closure property) của tập item thỏa ngưỡng minsupp:
Tất cả các tập con của một tập phổ biến cũng phổ biến.
Với lý thuyết này, thao tác khai thác luật kết hợp có thể chuyển thành bài
toán tìm tất cả các tập phổ biến với một ngưỡng tối thiểu minsupp cho trước.
Phần còn lại của nghiên cứu và hầu hết các tài liệu về khai thác luật kết hợp
cũng nhằm giải quyết vấn đề này.
2.2.2 Duyệt không gian tìm kiếm
Như đã giải thích trên đây, ta phải tìm tất cả các itemset thỏa ngưỡng
minsupp. Với các ứng dụng thực tiễn, việc duyệt tất cả các tập con của I sẽ
hoàn toàn thất bại vì không gian tìm kiếm quá lớn. Trên thực tế, sự tăng
tuyến tính số lượng các item vẫn kéo theo sự tăng theo cấp lũy thừa các
itemset cần xem xét. Với trường hợp đặc biệt I ={1,2,3,4}, ta có thể biểu diễn
không gian tìm kiếm thành một lưới như trong hình 1.
Trang 10
Nghiên cứu một số giải pháp đẩy nhanh tốc độ tính toán tập phổ biến, tìm luật kết hợp
Hình 2: Cây cho tập I = {1,2,3,4}
Cùng với tính chặn dưới của itemset thỏa ngưỡng minsupp, điều này suy ra:
Nếu lớp cha E’ của lớp E không có tối thiểu hai tập phổ biến thì E cũng phải
không chứa bất kỳ một tập phổ biến nào. Nếu gặp một lớp E’ như vậy trong
quá trình duyệt cây từ trên xuống thì ta đã tiến đến đường biên phân chia
giữa tập phổ biến và không phổ biến. Ta không cần phải tìm tiếp phần sau
đường biên này, tức là ta đã loại bỏ E và các lớp con của E trong không gian
tìm kiếm.
Thủ tục tiếp theo cho phép ta giới hạn một cách có hiệu quả số lượng các
itemset cần phải duyệt. Ta chỉ cần xác định các support values của các
itemset mà ta đã duyệt qua trong quá trình tìm kiếm đường biên giữa tập phổ
biến và tập không phổ biến. Cuối cùng, chiến lược thực sự để tìm đường biên
Trang 12
Nghiên cứu một số giải pháp đẩy nhanh tốc độ tính toán tập phổ biến, tìm luật kết hợp
là do lựa chọn của chúng ta. Các hướng tiếp cận phổ biến hiện nay sử dụng
cả tìm kiếm ưu tiên bề rộng (BFS) lẫn tìm kiếm ưu tiên chiều sâu (DFS). Với
BFS, giá trị hỗ trợ của tất cả (k-1)-itemset được xác định trước khi tính giá trị
hỗ trợ của k-itemset. Ngược lại, DFS duyệt đệ quy theo cấu trúc cây mô tả ở
trên.
2.2.3 Xác định các Itemset Support
Trong phần này, một itemset có khả năng là phổ biến và ta cần phải xác định
độ hỗ trợ của nó trong quá trình duyệt dàn, được gọi là một itemset ứng viên.
Một hướng tiếp cận phổ biến để xác định giá trị hỗ trợ của một itemset là
đếm các thể hiện của nó trong cơ sở dữ liệu. Với mục đích đó, một biến đếm
(counter) được tạo ra và khởi tạo bằng 0 cho mỗi itemset đang duyệt. Sau đó,
quét qua tất cả các giao tác và khi tìm được một ứng viên là tập con của một
giao tác thì tăng biến đếm của nó lên. Thông thường, tập con tạo ra và bảng
tìm kiếm ứng viên được tích hợp và cài đặt bằng một hashtree hay một cấu
trúc dữ liệu tương tự. Tóm lại, không phải tất cả các tập con của mỗi giao tác
đều được tạo ra mà chỉ những giao tác có chứa trong các ứng viên hoặc có
bày tính chặn dưới của itemset thỏa ngưỡng minsupp. Giải thuật Apriori tạo
ra việc sử dụng các tính chất này bằng việc tỉa bớt những ứng viên thuộc tập
không phổ biến trước khi tính độ phổ biến của chúng. Cách tối ưu có thể
thực hiện được vì các giải thuật tìm kiếm ưu tiên theo chiều rộng (BFS) bảo
đảm rằng các giá trị hỗ trợ của các tập của một ứng viên đều được biết trước.
Giải thuật Apriori đếm tất cả các ứng viên có k phần tử trong một lần đọc cơ
sở dữ liệu. Phần cốt lõi của bài toán là xác định các ứng viên trong mỗi giao
tác. Để thực hiện được mục đích này cần biết một cấu trúc gọi là hashtree.
Các item trong mỗi giao tác được dùng để đi lần xuống trong cấu trúc
hashtree. Bất cứ khi nào tới được nút lá của nó, nghĩa là ta đã tìm được một
tập các ứng viên có cùng tiền tố được chứa trong giao tác đó. Sau đó các ứng
viên này sẽ được thực hiện tìm kiếm trong giao tác mà nó đã được mã hóa
trước thành ma trận bit. Trong trường hợp thành công biến đếm các ứng viên
trong cây được tăng lên.
Giải thuật AprioriTID là phần mở rộng theo hướng tiếp cận cơ bản của giải
thuật Apriori. Thay vì dựa vào cơ sở dữ liệu thô giải thuật AprioriTID biểu
diễn bên trong mỗi giao tác bởi các ứng viên hiện hành. Giải thuật
AprioriHybrid kết hợp cả hai hướng tiếp cận trên. Ngoài ra còn có một số
các giải thuật tựa Apriori(TID), chúng được định hướng để cài trực tiếp trong
SQL.
Giải thuật DIC là một biến thể khác nữa của giải thuật Apriori. Giải thuật
DIC làm giảm đi khoảng phân biệt nghiêm ngặt giữa việc đếm và việc phát
sinh các ứng viên. Bất kỳ ứng viên nào tới được ngưỡng minsupp, thì giải
thuật DIC bắt đầu phát sinh thêm các ứng viên dựa vào nó. Để thực hiện điều
này giải thuật DIC dùng một prefix-tree (cây tiền tố). Ngược với hashtree,
mỗi nút (nút lá hoặc nút trong) của prefix-tree được gán một ứng viên xác
định trong tập phổ biến. Cách sử dụng cũng ngược với hashtree, bất cứ khi
Trang 15
Nghiên cứu một số giải pháp đẩy nhanh tốc độ tính toán tập phổ biến, tìm luật kết hợp
nào tới được một nút ta có thể khẳng định rằng tập item đã kết hợp với nút
hướng tiếp cận của DFS, FP-growth không theo nút của cây, mà đi trực tiếp
xuống một số phần của tập item trong không gian tìm kiếm. Trong bước thứ
hai, FP-growth dùng FP-tree để dẫn xuất tất cả các giá trị hỗ trợ của tất cả
các tập phổ biến.
2.3.5 DFS và giao tập hợp của các biến nhận dạng
Trong giải thuật Eclat được trình bày, nó kết hợp đi theo DFS với phần giao
của tidlist. Khi dùng DFS nó đủ để giữ tidlist trên đường đi từ gốc xuống lớp
hiện tại đang xét trong bộ nhớ. Do đó, việc phân chia cơ sở dữ liệu theo cách
tiếp cận của giải thuật Partition không cần thiết nữa.
Giải thuật Eclat dùng cách tối ưu bằng việc thực hiện “giao nhanh” (fast
intersection). Bất cứ khi nào thực hiện giao hai tidlist thì ta chỉ được một
tidlist kết quả nếu có các thành phần thỏa minsupp. Nói cách khác, ta nên bỏ
đi mỗi phần giao khi nó chắc chắn rằng sẽ không đạt được ngưỡng này. Giải
thuật Eclat nguyên thủy chỉ phát sinh tập phổ biến có kích thước lớn hơn
hoặc bằng 3. Sau đó đã được cải tiến để khai thác tập phổ biến có kích thước
từ 1 đến 2 bằng cách gọi nó trên lớp có chứa 1-itemset với các tidlist của
chúng.
2.4 So sánh các giải thuật
Trong phần này ta so sánh các giải thuật và giải thích các điểm khác biệt
trong việc thực thi.
2.4.1 So sánh việc đếm các thể hiện với việc thực hiện giao tập hợp
Câu hỏi được đặt ra liên quan đến thời gian thực thi của giải thuật là liệu việc
đếm các thể hiện hay việc thực hiện giao các tidlist có tốc độ thực thi nhanh
Trang 17
Nghiên cứu một số giải pháp đẩy nhanh tốc độ tính toán tập phổ biến, tìm luật kết hợp
hơn. Ưu điểm của việc đếm là chỉ xét những ứng viên xuất hiện trong giao
tác gây ra. Ngược lại, giao tập hợp cần ít nhất qua tất cả tid của tid nhỏ hơn
của hai tidlist, ngay cả khi ứng viên không có trong cơ sở dữ liệu. Nhưng
việc giao cũng có các lợi ích của nó. Thao tác đếm ngầm hiểu là tìm kiếm
các ứng viên trong các giao tác. Tất nhiên điều này có thể phải trả giá khá đắt
Đó là thời gian dùng để phát sinh các ứng viên, loại bớt những ứng viên
không cần thiết. Do đó, bước loại bớt ứng viên của giải thuật Apriori giúp
làm giảm đi số lượng ứng viên cần được đếm, điều này sẽ làm cho giải thuật
chạy nhanh hơn và tổng chi phí giảm đi một cách đáng kể.
CHƯƠNG 3: PHÂN TÍCH, ĐỀ XUẤT CÁC CHI TIẾT CẢI
TIẾN
3.1
Tạo danh sách các ứng viên C
k
từ tập F
k-1
Việc áp dụng nguyên lý Apriori sẽ cho chúng ta thuật giải duyệt theo chiều
rộng (BFS – breadth first search). Từ tập F
k-1
ở bước trước, chúng ta sẽ phải
phát sinh tập ứng cử viên C
k
, rồi mới đưa các ứng cử viên thỏa độ support >
minSupp vào F
k
. Chúng ta vẫn cần bổ sung một số cải tiến cho giải thuật gốc
này để có thể chạy được trong thời gian và bộ nhớ trong hợp lý với cơ sở dữ
liệu có lực lượng |I| lớn hoặc có số lượng transaction |O| khổng lồ.
Trang 19
Nghiên cứu một số giải pháp đẩy nhanh tốc độ tính toán tập phổ biến, tìm luật kết hợp
3.1.1
Cách xây dựng một ứng viên c
∈
C
k
∈
F
k
– thứ tự trong F
k
Mô tả:
Cho tập I gồm { i
1
, i
2
, …, i
N-1
, i
N
}
f ∈ F
k
gồm k item được mô tả là { i
a(1)
, i
a(2)
, …, i
a(k-1)
, i
a(k)
}
trong đó a(1) < a(2) < … < a(k-1) < a(k).
Cách lưu trữ này cho phép ta định nghĩa được một thứ tự f < f’ như sau:
f < f’ nếu ∃l ( a(l) < a’(l) ∧ ∀j<l, a(j) = a’(j) )
trong đó f ∈ F
chỉ cần tổ hợp từ hai tập phổ biến (k-1 phần tử) đầu tiên (nhỏ nhất) trong các
tập con k-1 phần tử của c.
Nếu ứng viên c được mô tả là { i
a(1)
, i
a(2)
, …, i
a(k-2)
, i
a(k-1)
, i
a(k)
} thì hai tập con
phổ biến k-1 phần tử sẽ là f
1
= { i
a(1)
, i
a(2)
, …, i
a(k-2)
, i
a(k-1)
} và f
2
= { i
a(1)
, i
a(2)
, …,
f
1
<f
2
∧ a(k-1)≠a’(k-1) ∧ ∀j<k-1, a(j)=a’(j)
và kết quả
c = f
1
⊕ f
2
= { i
a(1)
, i
a(2)
, , i
a(k-2)
, i
a(k-1)
, i
a’(k-1)
}
trong đó f
1
∈ F
k-1
gồm k item được mô tả là { i
a(1)
, i
a(2)
, …, i
1
, f
2
đầu tiên được
duyệt cũng chính là hai tập phổ biến k-1 phần tử nhỏ nhất phát sinh ra ứng cử
viên c.
Trang 21
i
a(1)
i
a(2)
… i
a(k-1)
i
a(1)
i
a(2)
… i
a’(k-1)
f
1
f
2
i
a(1)
i
a(2)
… i
a(k-1)
i
a’(k-1)
} được tạo từ phép f
1
⊕ f
2
, ta chỉ bổ
sung c vào tập C
k
nếu
∀j<k-2, c\i
a(j)
∈F
k-1
trong đó f
1
∈ F
k-1
gồm k item được mô tả là { i
a(1)
, i
a(2)
, …, i
a(k-1)
},
f
2
∈ F
k
gồm k item được mô tả là { i
a’(1)
được lưu trữ có thứ tự (do bản chất của quá trình phát sinh c)
và bản thân f cũng được tổ chức lưu trữ có thứ tự các item I, việc kiểm tra
c\i
a(j)
∈ F
k
(được thực hiện k-2 lần trên mỗi ứng cử viên C
k
) sẽ không tốn quá
nhiều chi phí và chi phí này sẽ nhỏ hơn nhiều so với chi phí đọc cơ sở dữ liệu
lớn để tính độ support.
Do số lần cần kiểm tra lại độ support phụ thuộc vào các số lượng các tập phổ
biến ở mỗi mức k cũng như số transaction |O| trong cơ sở dữ liệu nên cải tiến
này có ý nghĩa cho cả hai trường hợp cơ sở dữ liệu lớn có nhiều item |I| lẫn
cơ sở dữ liệu có nhiều transaction |O|.
3.2.2 Cải tiến 3 – Giảm số lần đọc cơ sở dữ liệu
Trong quá trình áp dụng nguyên lý Aprior để tính độ support cho các ứng
viên c để xem có nên đưa vào tập F
k
không, chúng ta phải quét (đọc) toàn bộ
cơ sở dữ liệu để kiểm chứng độ support có thỏa so với minSupp. Đối với các
cơ sở dữ liệu có kích thước lớn, nhất là đối với các hệ cơ sở dữ liệu phân tán,
chi phí cho mỗi lần đọc cơ sở dữ liệu như vậy trở nên quá đắt một cách
không đáng có.
Với cách giải quyết bài toán theo hướng tiếp cận levelwise, nếu chúng ta để ý
sẽ thấy việc kiểm tra một phần tử c có thuộc F
k
không cho chúng ta thông tin
gì trong việc kiểm tra một phần tử c’ có thuộc F
k
bớt số lần đọc cơ sở dữ liệu trong một lần quét cơ sở dữ liệu.
Với cải tiến này, số lần phải quét qua cơ sở dữ liệu không còn phụ thuộc vào
số lượng các tập phổ biến sẽ được phát sinh mà chỉ phụ thuộc vào số lớp
được phát sinh và chiếu (nghĩa là bằng với số item trong một tập phổ biến).
3.2.3 Cải tiến 3’ – Loại bỏ sớm các ứng viên không thỏa độ support
Xét đến bài toán tìm luật kết hợp trong trường hợp cần tìm một luật có độ
phổ biến cao, ta thấy rằng có thể áp dụng kỹ thuật bù để loại bỏ sớm những c
Trang 24
{ 1 } { 2 } { 3 } {4}
{ 2, 3 } { 2, 4 } { 3, 4 }
L
1
– F
k-1
t
1
t
2
…
t
N
L
2
– C
k
{ 1, 2 } { 1, 3 } { 1, 4 }
scan
project
Nghiên cứu một số giải pháp đẩy nhanh tốc độ tính toán tập phổ biến, tìm luật kết hợp
∉ F
k
, ta nhanh chóng loại bỏ c khỏi C
k
và không cần xét đến.
Việc đếm luôn cả các trường hợp không support đã giúp chúng ta nhanh
chóng loại bỏ các ứng viên quá kém. Cải tiến này thật sự có ý nghĩa trong
trường hợp số lượng item |I| lớn nhưng chỉ có rất ít trong chúng thật sự là tập
phổ biến. Điều này cũng phù hợp với thực tế, nhất là trong các cơ sở dữ liệu
bán hàng với nhiều mặt hàng như các siêu thị.
Trang 25
Copyright: Tài liệu đại học ©