ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
CHƢƠNG TRÌNH ĐÀO TẠO THẠC SĨ CNTT QUA MẠNG
________________ BÀI THU HOẠCH MÔN HỌC
KHAI PHÁ DỮ LIỆU VÀ KHO DỮ LIỆU
ĐỀ TÀI: LUẬT KẾT HỢP Giảng viên hướng dẫn: PGS.TS Đỗ Phúc
Học viên thực hiện: Lƣơng Trí Quân
MSHV: CH1101125 TP. HCM, năm 2012
Bài thu hoạch môn học: Khai phá dữ liệu và kho dữ liệu


Lương Trí Quân Trang 3

II. Thuật toán SETM 29
III. Thuật toán Apriori 30
IV. Thuật toán Apriori-TID 38
V. Thuật toán Apriori-Hybrid 39
VI. Thuật toán PARTITION [Savasere 95] 40
CÀI ĐẶT CHƢƠNG TRÌNH TÌM LUẬT KẾT HỢP THEO THUẬT TOÁN APRIORI 41 Bài thu hoạch môn học: Khai phá dữ liệu và kho dữ liệu

Lương Trí Quân Trang 4

MỞ ĐẦU

Trong những năm gần đây, sự phát triển mạnh mẽ của công nghệ thông tin đã làm cho
khả năng thu thập và lưu trữ thông tin của các hệ thống thông tin tăng nhanh một cách
nhanh chóng. Bên cạnh đó, việc tin học hóa một cách ồ ạt và nhanh chóng các hoạt động
sản xuất, kinh doanh cũng như nhiều lĩnh vực hoạt động khác đã tạo ra cho chúng ta một
lượng dữ liệu cần lưu trữ khổng lồ. Hàng triệu cơ sở dữ liệu đã được sử dụng trong các
hoạt động sản xuất, kinh doanh, quản lý…, trong đó có nhiều cơ sở dữ liệu cực lớn tính
bằng đơn vị Gigabyte, Terabyte.
Sự bùng nổ này đã dẫn tới một yêu cầu cấp thiết là cần có những kỹ thuật và công cụ mới
để tự động chuyển đổi lượng dữ liệu khổng lồ kia thành các tri thức có ích. Từ đó, các kỹ
thuật khai phá dữ liệu đã trở thành một lĩnh vực thời sự của nền CNTT thế giới hiện nay
nói chung và Việt Nam nói riêng. Khai phá dữ liệu đang được áp dụng một cách rộng rãi
trong nhiều lĩnh vực kinh doanh và đời sống khác nhau: marketing, tài chính, ngân hàng,
bảo hiểm, khoa học, y tế, an ninh, internet… Rất nhiều tổ chức và công ty lớn trên thế
giới đã áp dụng kỹ thuật khai phá dữ liệu vào các hoạt động sản xuất kinh doanh của

Kỹ thuật phát hiện tri thức và khai phá dữ liệu (KDD - Knowledge Discovery and Data
Mining).
Thông thường chúng ta coi dữ liệu như một dãy các bit, hoặc các số và các ký hiệu,
hoặc các “đối tượng” với một ý nghĩa nào đó khi được gửi cho một chương trình dưới
một dạng nhất định. Chúng ta sử dụng các bit để đo lường các thông tin và xem nó như là
các dữ liệu đã được lọc bỏ các dư thừa, được rút gọn tới mức tối thiểu để đặc trưng một
cách cơ bản cho dữ liệu. Chúng ta có thể xem tri thức như là các thông tin tích hợp, bao
gồm các sự kiện và các mối quan hệ giữa chúng. Các mối quan hệ này có thể được hiểu
Bài thu hoạch môn học: Khai phá dữ liệu và kho dữ liệu

Lương Trí Quân Trang 6

ra, có thể được phát hiện, hoặc có thể được học. Nói cách khác, tri thức có thể được coi là
dữ liệu có độ trừu tượng và tổ chức cao.
Phát hiện tri thức trong các cơ sở dữ liệu là một qui trình nhận biết các mẫu hoặc các
mô hình trong dữ liệu với các tính năng: hợp thức, mới, khả ích, và có thể hiểu được.
Còn khai thác dữ liệu là một bước trong qui trình phát hiện tri thức gồm có các thuật
toán khai thác dữ liệu chuyên dùng dưới một số qui định về hiệu quả tính toán chấp nhận
được để tìm ra các mẫu hoặc các mô hình trong dữ liệu. Nói một cách khác, mục đích của
phát hiện tri thức và khai phá dữ liệu chính là tìm ra các mẫu và/hoặc các mô hình đang
tồn tại trong các cơ sở dữ liệu nhưng vẫn còn bị che khuất bởi hàng “núi” dữ liệu.
Nhiều người coi khai phá dữ liệu và khám phá tri thức trong cơ sở dữ liệu là như
nhau. Tuy nhiên trên thực tế, khai phá dữ liệu chỉ là một bước thiết yếu trong quá trình
phát hiện tri thức trong cơ sở dữ liệu.
II. Một số quan niệm về khai phá dữ liệu

Khai phá dữ liệu là tập hợp các thuật toán nhằm chiết xuất những thông tin có
ích từ kho dữ liệu khổng lồ.
Khai phá dữ liệu được định nghĩa như một quá trình phát hiện mẫu trong dữ
liệu. Quá trình này có thể là tự động hay bán tự động, song phần nhiều là bán

Điều mà khai phá dữ liệu có thể làm rất tốt là phát hiện ra những giả thuyết mạnh
trước khi sử dụng những công cụ tính toán thống kê. Mô hình dự báo sử dụng kỹ thuật
phân cụm (Clustering) để chia nhóm các sự vật, sự kiện sau đó rút ra các luật nhằm tìm ra
đặc trưng cho mỗi nhóm và cuối cùng đề nghị một mô hình. Ví dụ, những bạn đọc đăng
ký dài hạn của một tạp chí có thể phân nhóm dựa theo nhiều tiêu chí khác nhau (lứa tuổi,
giới tính, thu nhập…), sau đó tạp chí căn cứ vào đặc trưng riêng của từng nhóm để đề
ra mức phí thu trong năm sao cho phù hợp nhất.
Từ đó chúng ta thấy, những nhiệm vụ cơ bản nhất của khai phá dữ liệu là:
Phân cụm, phân loại, phân nhóm, phân lớp: Có nhiệm vụ là trả lời câu hỏi: Một
dữ liệu mới thu thập sẽ thuộc về nhóm nào? Quá trình này thường được thực hiện
một cách tự động.
Khai phá luật kết hợp: Có nhiệm vụ là phát hiện ra những mối quan hệ giống
nhâu của các bản ghi giao dịch. Luật kết hợp X=>Y có dạng tổng quát là: Nếu một
giao dịch đã sở hữu các tính chất X thì đồng thời nó cũng sở hữu các tính chất
Y.Ở một mức độ nào đó, khai phá luật kết hợp được hiểu theo nghĩa: Biết trước
các tính chât X, vậy các tính chất Y là những tính chất nào?
Bài thu hoạch môn học: Khai phá dữ liệu và kho dữ liệu

Lương Trí Quân Trang 8

Lập mô hình dự báo: Bao gồm hai nhiệm vụ hoặc là phân nhóm dư liệu vào một
hay nhiều lớp dữ liệu đã xác định từ trước, hoặc là sử dụng các trường đã cho
trong một cơ sở dữ liệu để dự báo sự xuất hiện (hoặc không xuất hiện) của các
trường hợp khác.
Phân tích đối tƣợng ngoài cuộc: Một cơ sở dữ liệu có thể có thể chứa các đối
tượng không tuân theo mô hình dữ liệu. Các đối tượng dữ liệu như vậy gọi là các
đối tượng ngoài cuộc. Hầu hết các phương pháp khai phá dữ liệu đều coi các đối
tượng ngoài cuộc là nhiễu và loại bỏ chúng. Tuy nhiên trong một số ứng dụng,
chẳng hạn như phát hiện nhiễu thì sự kiện hiếm khi xảy ra lại được chú ý hơn
những gì thường xuyên gặp phải. Sự phân tích dữ liệu ngoài cuộc được coi như là

không thích hợp.
 Bƣớc 2: Tích hợp dữ liệu (Data integration): Tích hợp dữ liệu từ các nguồn
khác nhau.
 Bƣớc 3: Chọn dữ liệu (Data Selection): Chọn những dữ liệu liên quan trực tiếp
đến nhiệm vụ.
 Bƣớc 4: Chuyển đổi dữ liệu (Data Transformation): Chuyển dữ liệu về những
dạng phù hợp cho việc khai phá.
 Bƣớc 5: Khai phá dữ liệu (Data mining): Các kỹ thuật được áp dụng để trích
xuất thông tin có ích hoặc các mẫu điển hình trong dữ liệu.
 Bƣớc 6: Đánh giá mẫu (Pattern evaluation): Đánh giá mẫu hoặc tri thức đã thu
được.
 Bƣớc 7: Trình diễn dữ liệu (Knowledge Presentation): Biểu diễn những tri thức
khai phá được cho người sử dụng.
Quá trình phát hiện tri thức từ cơ sở dữ liệu đƣợc diễn tả qua mô hình sau:

Mô hình trên mô tả 5 giai đoạn trong quá trình khám phá tri thức từ cơ sở dữ liệu. Mặc dù
có 5 giai đoạn như trên xong quá trình khám phá tri thức từ cơ sở dữ liệu là một quá trình
tương tác và lặp di lặp lại theo chu trình liên tục kiểu xoáy trôn ốc, trong đó lần lặp sau
hoàn chỉnh hơn lần lặp trước. Ngoài ra, giai đoạn sau lại dựa trên kết quả thu được của
giai đoạn trước theo kiểu thác nước. Đây là một quá trình biện chứng mang tính chất khoa
học của lĩnh vực phát hiện tri thức và là phương pháp luận trong việc xây dựng các hệ
thống phát hiện tri thức.
1. Giai đoạn xác định vấn đề:
Bài thu hoạch môn học: Khai phá dữ liệu và kho dữ liệu

Lương Trí Quân Trang 10

Đây là một quá trình mang tính định tính với mục đích xác định được lĩnh vực yêu
cầu phát hiện tri thức và xây dựng bài toán tổng kết. Trong thực tế, các cơ sở dữ
liệu được chuyên môn hóa và phân chia theo các lĩnh vực khác nhau như sản


thay đổi một số thông tin cá nhân gây ra và tạo sự lầm tưởng có nhiều
khách hàng khác nhau.
(ii) Xử lý các giá trị khuyết: Tính không đầy đủ của dữ liệu có thể gây ra
hiện tượng dữ liệu chứa các giá trị khuyết. Đây là hiện tượng khá phổ biến.
Thông thường, người ta có thể lựa chọn các phương pháp khác nhau để thực
hiện việc xử lý các giá trị khuyết như: bỏ qua các bộ có giá trị khuyết, điểm
bổ sung bằng tay, dùng một hằng chung để điền vào giá trị khuyết, dùng
giá trị trung bình của mọi bản ghi cùng lớp hoặc dùng các giá trị mà tần suất
xuất hiện lớn.
(iii) Xử lý nhiễu và các ngoại lệ: Thông thường, nhiễu dữ liệu có thể
là nhiễu ngẫu nhiên hoặc các giá trị bất thường. Để làm sạch nhiễu, người ta
có thể sử dụng phương pháp làm trơn nhiễu hoặc dùng các giải thuật phát
hiện ra các ngoại lệ để xử lý.
c. Làm giàu dữ liệu: Việc thu thập dữ liệu đôi khi không đảm bảo tính đầy đủ
của dữ liệu. Một số thông tin quan trọng có thể thiếu hoặc không đầy đủ.
Chẳng hạn, dữ liệu về khách hàng lấy từ một nguồn bên ngoài không có hoặc
không đầy đủ thông tin về thu nhập. Nếu thông tin về thu nhập là quan trọng
trong quá trình khai thác dữ liệu để phân tích hành vi khách hàng thì rõ ràng là
ta không thể chấp nhận đưa các dữ liệu khuyết thiếu vào được.
Quá trình làm giàu bao cũng bao gồm việc tích hợp và chuyển đổi dữ liệu. Các
dữ liệu từ nhiều nguồn khác nhau được tích hợp thành một kho thống nhất. Các
khuôn dạng khác nhau của dữ liệu cũng được quy đổi, tính toán lại để đưa về
một kiểu thống nhất, tiện cho quá trình phân tích. Đôi khi, một số thuộc tính
mới có thể được xây dựng dựa trên các thuộc tính cũ.
d. Mã hóa: Các phương pháp dùng để chọn lọc, làm sạch, làm giàu dữ liệu sẽ
được mã hóa dưới dạng các thủ tục, chương trình hay tiện ích nhằm tự động
hóa việc kết xuất, biến đổi và di chuyển dữ liệu. Các hệ thống con đó có thể
được thực thi định kỳ làm tươi dữ liệu phục vụ cho việc phân tích.
3. Khai thác dữ liệu

thức từ số lượng lớn dữ liệu lưu trữ trong các cơ sở dữ liệu,kho dữ liệu hoặc các nơi lưu
trữ khác. Bước này có thể tương tác lẫn nhau giữa người sử dụng hoặc cơ sở tri thức,
những mẫu đáng quan tâm được đưa cho người dùng hoặc lưu trữ như là tri thức mới
trong cơ sở tri thức.
Bài thu hoạch môn học: Khai phá dữ liệu và kho dữ liệu

Lương Trí Quân Trang 13 Kiến trúc của hệ thống khai phá dữ liệu
Kiến trúc của hệ thống khai phá dữ liệu có các thành phần như sau:
 Cơ sở dữ liệu, kho dữ liệu: Đó là một hoặc tuyển tập các cơ sở dữ liệu, kho dữ liệu
… Các kỹ thuật làm sạch dữ liệu, tích hợp, lọc dữ liệu có thể thực hiện trên dữ liệu
 Cơ sở dữ liệu hoặc kho dữ liệu phục vụ: Là kết quả lấy dữ liệu có liên quan trên
cơ sở khai phá dữ liệu của người dùng.
 Cơ sở tri thức: Đó là lĩnh vực tri thức được sử dụng để hướng dẫn việc tìm hoặc
đánh giá các mẫu kết quả thu được
 Mô tả khai phá dữ liệu: Bao gồm tập các module chức năng để thực hiện các nhiệm
vụ mô tả đặc điểm, kết hợp, phân lớp, phân cụm dữ liệu…
 Đánh giá mẫu: Thành phần này sử dụng các độ đo và tương tác với module khai phá
dữ liệu để tập trung vào tìm các mẫu quan tâm.
 Giao diện ngƣời dùng: Đây là module giữa người dùng và hệ thống khai phá dữ
liệu. Cho phép người dùng tương tác với hệ thống trên cơ sở những truy vấn hay tác vụ,
cung cấp thông tin cho việc tìm kiếm.
VII. Các kỹ thuật khai phá dữ liệu

Kĩ thuật khai phá dữ liệu được chia thành hai nhóm chính:
Bài thu hoạch môn học: Khai phá dữ liệu và kho dữ liệu

Lương Trí Quân Trang 14

liệu. Quá trình phân lớp dữ liệu thường gồm hai bước: Xây dựng mô hình và sử
dụng mô hình để phân lớp dữ liệu.
Bài thu hoạch môn học: Khai phá dữ liệu và kho dữ liệu

Lương Trí Quân Trang 15

 Bƣớc 1: Một mô hình sẽ được xây dựng dựa trên việc phân tích các mẫu dữ liệu
sẵn có. Mỗi mẫu tương ứng với một lớp, được quyết định bởi một thuộc tính gọi là
thuộc tính lớp. Các lớp dữ liệu này còn được gọi là lớp dữ liệu huấn luyện
(training data set). Các nhãn lớp của tập dữ liệu huấn luyện đều phải được xác định
trước khi xây dựng mô hình.
 Bƣớc 2: Sử dụng mô hình để phân lớp dữ liệu. Trước hết, chúng ta phải tính độ
chính xác của mô hình. Nếu độ chính xác là chấp nhận được, mô hình sẽ được sử
dụng để dự đoán nhãn lớp cho các mẫu dữ liệu khác trong tương lai. Một ví dụ về
việc sử dụng phương pháp phân lớp trong khai phá dữ liệu là ứng dụng phân lớp
các xu hướng trong thị trường tài chính và ứng dụng tự động xác định các đối
tượng đáng quan tâm trong cơ sở dữ liệu ảnh lớn.
3. Phƣơng pháp hồi quy

Phương pháp hồi quy khác với phân lớp dữ liệu ở chỗ: Hồi quy dùng để dự đoán
về các giá trị liên tục còn phân lớp dữ liệu chỉ dùng để dự đoán về các giá trị rời
rạc.
Hồi quy là một hàm học ánh xạ mục dữ liệu thành một biến dự đoán có giá trị
thực. Có rất nhiều ứng dụng khai phá dữ liệu với nhiệm vụ hồi quy, chẳng hạn như
khả năng đánh giá tử vong của bệnh nhân khi biết các kết quả xét nghiệm; chẩn
đoán, dự đoán nhu cầu tiêu thụ một sản phẩm mới bằng một hàm chi tiêu quảng
cáo.
4. Khai phá luật kết hợp

Mục tiêu của phương pháp này là phát hiện và đưa ra các mối liên hệ giữa

ngữ khám phá dữ liệu hay phát hiện tri thức) là một quá trình phân tích dữ liệu từ các
viễn cảnh khác nhau và rút ra các thông tin bổ ích – những thông tin có thể dùng để
tăng lợi nhuận, cắt giảm chi phí hoặc cả hai mục đích. Phần mềm khai phá dữ liệu là
một công cụ phân tích dùng để phân tích dữ liệu. Nó cho phép người sử dụng phân
tích dữ liệu theo nhiều góc nhìn khác nhau, phân loại dữ liệu thao những quan điểm
riêng biệt và tổng kết các mối quan hệ đã được bóc tách. Xét về khía cạnh kỹ thuật,
khai phá dữ liệu là một quá trình tìm kiếm các mối tương quan giữa các mẫu ẩn chứa
trong hàng chục trường dữ liệu của một cơ sở dữ liệu quan hệ cỡ lớn.
Hiện nay, kỹ thuật khai phá dữ liệu đang được áp dụng một cách rộng rãi trong rất
nhiều lĩnh vực kinh doanh và đời sống khác nhau như:
 Thƣơng mại: Phân tích dữ liệu bán hàng và thị trường, phân tích đầu tư,
quyết định cho vay, phát hiện gian lận, …
Bài thu hoạch môn học: Khai phá dữ liệu và kho dữ liệu

Lương Trí Quân Trang 17

 Thông tin sản xuất: Điều khiển và lập kế hoạch, hệ thống quản lý, phân tích
kết quả thử nghiệm, …
 Thông tin khoa học: Dự báo thời tiết, CSDL sinh học: Ngân hàng gen, …
khoa học địa lý: dự báo động đất, …
 Trong y tế, marketing, ngân hàng, viễn thông, du lịch, internet…
Thông qua việc khai phá dữ liệu, phát hiện tri thức đã thu được các kết qủa đáng giá.
Điều đó được chứng minh bằng thực tế: Chẩn đoán bệnh trong y tế dựa trên kết quả xét
nghiệm đã giúp cho bảo hiểm y tế phát hiện ra nhiều trường hợp xét nghiệm không hợp
lý, tiết kiệm được nhiều kinh phí mỗi năm; trong dịch vụ viễn thông đã phát hiện ra
những nhóm người thường xuyên gọi cho nhau bằng mobile và thu lợi hàng triệu USD;
IBM Suft-Aid đã áp dụng khai phá dữ liệu vào phân tích các lần đăng nhập Web vào các
trang liên quan đến thị trường để phát hiện sở thích khách hàng, từ đó đánh giá hiệu quả
của việc tiếp thị qua Web và cải thiện hoạt động của các Website; trang Web mua bán qua
mạng Amazon cũng tăng doanh thu nhờ áp dụng khai phá dữ liệu trong việc phân tích sở

tâm hiện tại của việc khai thác. Bên cạnh đó, tính ứng dụng của một thuộc tính đối với
một tập con của cơ sở dữ liệu cũng là một vấn đề đôi khi cũng liên quan dến độ phù hợp.
 Các giá trị bị thiếu: Sự có mặt hay vắng mặt của giá trị các thuộc tính dữ liệu
phù hợp có thể ảnh hưởng đến việc khai phá dữ liệu. Trong hệ thống tương tác, sự thiếu
vắng dữ liệu quan tọng có thể dẫn tới yêu cầu cho giá trị của nó hoặc kiểm tra để xác định
giá trị của nó. Hoặc cũng có thể sự vắng mặt của dữ liệu được coi như một điều kiện,
thuộc tính bị mất có thể được xem như một giá trị trung gian và gía trị không biết.
 Các trƣờng dữ liệu bị thiếu: Một quan sát không đầy đủ cơ sở dữ liệu có thể
làm cho dữ liệu có giá trị bị xem như có lỗi. Việc quan sát cơ sở dữ liệu phải phát hiện
được toàn bộ các thuộc tính có thể dùng để thuật toán khai phá dữ liệu có thể áp dụng để
giải quyết bài toán. Giả sử ta có các thuộc tính để phân biệt các tình huống đáng quan
tâm. Nếu chúng không làm được điều đó thì có nghĩa là đã có lỗi trong dữ liệu. Đây cũng
là vấn đề thường xảy ra trong cơ sở dữ liệu kinh doanh. Các thuộc tính quan trọng có thể
sẽ bị thiếu dữ liệu không được chuẩn bị.
 Khả năng biểu đạt mẫu: Trong rất nhiều ứng dụng, điều quan trọng là những
điều khai thác được phải càng dễ hiểu với con người càng tốt. Vì vậy, các giải pháp
thường bao gồm việc diễn tả dưới dạng đồ họa, xây dựng cấu trúc luật với các đồ thị có
hướng, biểu diễn bằng ngôn ngữ tự nhiên và kỹ thuật khác nhằm biểu diễn các tri thức và
dữ liệu.
 Sự tƣơng tác với ngƣời sử dụng các tri thức sẵn có: Rất nhiều công cụ và
phương pháp khai phá dữ liệu không thực sự tương tác với người dùng và không dễ dàng
Bài thu hoạch môn học: Khai phá dữ liệu và kho dữ liệu

Lương Trí Quân Trang 19

kết hợp cùng với các tri thức đã biết trước đó. Việc sử sụng tri thức miền là rất quan trọng
trong khai phá dữ liệu. Đã có nhiều biện pháp nhằm khắc phục vấn đề này như sử dụng
cơ sở dữ liệu suy diễn để phát hiện tri thức, những tri thức này sau đó được sử dụng để
hướng dẫn cho việc tìm kiếm khai phá dữ liệu hoặc sử dụng sự phân bố xác suất dữ liệu
trước đó như một dạng mã hóa tri thức có sẵn.

xuyên, pha hai là tìm luật.
II. Luật kết hợp
Bài thu hoạch môn học: Khai phá dữ liệu và kho dữ liệu

Lương Trí Quân Trang 21
1. Độ hỗ trợ
a. Định nghĩa 1
Độ hỗ trợ của một tập hợp X trong cơ sở dữ liệu D là tỷ số giữa các bản ghi T
D có chứa tập X và tổng số bản ghi trong D (hay là phần trăm của các bản
ghi trong D có chứa tập hợp X), ký hiệu là support(X) hay supp(X) (support sẽ
tự sinh ra khi cài thuật toán)

b. Định nghĩa 2

Độ hỗ trợ của một luật kết hợp XY là tỷ lệ giữa số lượng các bản ghi chứa
tập hợp X Y, so với tổng số các bản ghi trong D
Ký hiệu supp(XY)

Khi chúng ta nói rằng độ hỗ trợ của một luật là 50%, có nghĩa là có 50% tổng
số bản ghi chứa X Y. Như vậy, độ hỗ trợ mang ý nghĩa thống kê của luật.
Trong một số trường hợp, chúng ta chỉ quan tâm đến những luật có độ hỗ trợ
cao (Ví dụ như luật kết hợp xét trong cửa hàng tạp phẩm). Nhưng cũng có
Bài thu hoạch môn học: Khai phá dữ liệu và kho dữ liệu

Lương Trí Quân Trang 22

trường hợp, mặc dù độ hỗ trợ của luật thấp, ta vẫn cần quan tâm (ví dụ luật kết

3. Tập hợp

Nếu conf ≥ minconf thì luật được giữ lại (và thỏa mãn độ hỗ trợ tối thiểu vì ABCD
là phổ biến). Trong thực tế, hầu hết thời gian của quá trình khai thác luật kết hợp là
thực hiện ở pha 1. Nhưng khi có những mẫu rất dài (mẫu chứa nhiều mục) xuất hiện
trong dữ liệu, việc sinh ra toàn bộ các tập phổ biến (FI) hay các tập đóng (FCI) là không
thực tế. Hơn nữa, có nhiều ứng dụng mà chỉ cần sinh tập phổ biến lớn nhất (MFI) là đủ,
như khám phá mẫu tổ hợp trong các ứng dụng sinh học.
Có rất nhiều nghiên cứu về các phương pháp sinh tất cả các tập phổ biến và tập
phổ biến lớn nhất một cách có hiệu quả. Khi các mẫu phổ biến (frequent patterm) dài có
từ 15 đến 20 items) thì tập FI, thậm chí cả tập FCI trở nên rất lớn và hầu hết các phương
pháp truyền thống phải đếm quá nhiều tập mục mới có thể thực hiện được. Các thuật
toán dựa trên thuật toán Apriori – đếm tất cả 2
k
tập con của mỗi k- itemsets mà chúng
quét qua và do đó không thích hợp với các itemsets dài được. Các phương pháp khác sử
dụng “lookaheads” để giảm số lượng tập mục được đếm. Tuy nhiên, hầu hết các thuật
toán này đều sử dụng tìm kiếm theo chiều rộng, ví dụ: tìm tất cả các k – itemsets trước
Bài thu hoạch môn học: Khai phá dữ liệu và kho dữ liệu

Lương Trí Quân Trang 24

khi tính đến các (k+1) – itemsets. Cách làm này hạn chế hiệu quả của lookaheads vì các
mẫu phổ biến dài hơn mà hữu ích vẫn chưa được tìm ra.
Thuật toán cơ bản:
Giao dịch mua hàng