Số hóa bởi Trung tâm Học liệu
ĐẠI HỌC THÁI
NGUYÊN
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG
BÙI VĂN THẮNG
LUẬT KẾT HỢP MỜ VÀ ỨNG DỤNG
ĐỐI VỚI MỘT SỐ BÀI TOÁN DỰ BÁO
LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH
LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH
HƢỚNG DẪN KHOA HỌC: TS. VŨ VINH QUANG
THÁI NGUYÊN - 2014
ii
Số hóa bởi Trung tâm Học liệu LỜI CAM ĐOAN
Tôi xin cam đoan đây là công trình nghiên cứu của riêng tôi dưới sự hướng dẫn
trực tiếp của TS. Vũ Vinh Quang.
Mọi trích dẫn sử dụng trong báo cáo này đều được ghi rõ nguồn tài liệu tham
khảo theo đúng qui định.
Mọi sao chép không hợp lệ, vi phạm quy chế đào tạo, hay gian trá, tôi xin chịu
hoàn toàn trách nhiệm.
Thái Nguyên, ngày27tháng8năm 2014
Tác giả Bùi Văn Thắng
1.4.2. Một số thuật toán cơ bản 15
1.5. Logic mờ 23
1.5.1. Định nghĩa tập mờ 23
1.5.2. Độ cao, miền xác định và miền tin cậy của tập mờ 25
1.5.3. Các phép toán logic trên tập mờ 26
1.5.4. Biến ngôn ngữ và giá trị của nó 27
1.6. Kết luận 28 Số hóa bởi Trung tâm Học liệu CHƢƠNG 2. KHAI PHÁ LUẬT KẾT HỢP MỜ 30
2.1. Rời rạc hóa thuộc tính dựa vào tập mờ 30
2.1.1. Luật kết hợp với thuộc tính số 30
2.1.2. Các phương pháp rời rạc hóa 30
2.2. Luật kết hợp mờ 33
2.2.1. Rời rạc hóa thuộc tính mờ 33
2.2.2. Luật kết hợp mờ 35
2.3. Thuật toán khai phá luật kết hợp mờ dựa trên thuật toán Apriori 37
2.4. Khai phá luật kết hợp mờ dựa trên thuật toán Fp-Growth 40
2.4.1. Thuật toán xây dựng cây CUFP-Tree 40
2.4.2. Thuật toán tìm tập phổ biến FP-Growth dựa trên cậy CUFP-Tree 41
2.5. Ví dụ thử nghiệm 42
2.5.1. Xây dựng cây CUFP-Tree 42
2.5.2. Thuật toán tìm tập phổ biến 45
2.6. Kết luận 46
CHƢƠNG 3. ỨNG DỤNG KHAI PHÁ DỮ LIỆU TRONG MÔ HÌNH DỰ
BÁO 48
3.1. Mô hình một số bài toán dự báo 48
iv
Số hóa bởi Trung tâm Học liệu DANH MỤC BẢNG
Bảng 1.1: Cơ sở dữ liệu giao tác 11
Bảng 1.2: Kết quả thuật toán Apriori 16
Bảng 1.3: Những biến đổi dữ liệu của FP-Growth 19
Bảng 2.1: CSDL thống kế dân số của 10 gia đình [21] 31
Bảng 2.2: Rời rạc hóa thuộc tính số rời rạc hữu hạn hoặc thuộc tính hạng mục 31
Bảng 2.3: Rời rạc hóa thuộc tính số“Tuổi" 32
Bảng 2.4: Bảng các ký hiệu sử dụng trong thuật toán khai phá luật kết hợp mờ 38
Bảng 2.5: Bảng các ký hiệu sử dụng trong thuật toán 40
Bảng 2.6: Cơ sở dữ liệu mờ 42
Bảng 2.7: Kết quả sau khi thực hiện Bước 1 42
Bảng 2.8: Header_Table 43
Bảng 2.9: CSDL mờ sau khi đã cập nhật 43
Bảng 2.10: Tập phổ biến 46
Bảng 3.1: Giao tác ví dụ trong CSDL FAM95 56
Bảng 3.2: CSDL giao tác Bảng 3.1 sau khi mờ hóa 57 v
Số hóa bởi Trung tâm Học liệu MỞ ĐẦU
1. Đặt vấn đề
Khai phá dữ liệu là một lĩnh vực nghiên cứu quan trọng trong lý thuyết về cơ sở
dữ liệu, có nhiều ứng dụng trong đời sống xã hội. Mục đích chính là nhằm phát hiện
những thông tin mới, các luật mới từ cơ sở dữ liệu đã có hay một cách tổng quát hơn là
từ các kho dữ liệu. Rất nhiều lĩnh vực ứng dụng trong thực tiễn đều sử dụng công cụ
khai phát dữ liệu và tìm kiếm tri thức. Trong lý thuyết về khai phá dữ liệu, khai phá
luật kết hợp đang được quan tâm nghiên cứu nhiều trên thế giới. Một số hướng nghiên
cứu đã và đang được các chuyên gia công nghệ thông tin tập chung nghiên cứu là:
nghiên cứu thiết kế các hệ mờ cho các ứng dụng cụ thể như hệ trợ giúp quyết định, hệ
điều khiển dựa trên hệ tri thức luật, hệ phân loại dựa trên hệ tri thức luật, hệ phân loại
dựa trên lập luận dựa trên hệ luật ứng dụng trong các lĩnh vực như: kinh doanh, thị
trường chứng khoán và dự đoán thị trường, công nghệ sinh học, giáo dục và đào tạo,…
Một số hƣớng nghiên cứu trong khai phá dữ liệu
- Luật kết hợp nhị phân: Đây là hướng nghiên cứu đầu tiên của luật kết hợp.
Thuật toán tiêu biểu là Apriori.
- Luật kết hợp có thuộc tính số và thuộc tính hạng mục: Nghiên cứu các hệ
CSDL có thuộc tính số hoặc thuộc tính hạng mục bằng cách rời rạc hóa dữ
liệu cho thuộc tính số để chuyển chúng về thuộc tính nhị phân.
- Luật kết hợp mờ: Phương pháp rời rạc hóa dữ liệu có thuộc tính số và thuộc
tính hạng mục gặp phải vấn đề“điểm biên gãy”. Để khắc phục điều này, các
nhà nghiên cứu đề xuất sử dụng lý thuyết tập mờ và xây dựng các luật kết hợp
dạng mờ.
- Luật kết hợp có trọng số: Sử dụng phương pháp tính độ hỗ trợ cho các tập
mục dựa trên trọng số của các tập mục.
Ngoài ra, còn một số hướng nghiên cứu: khai phá luật kết hợp song song, khai
phá luật kết hợp nhiều mức, luật kết hợp tiếp cận theo hướng tập thô,…
Luận văn tập trung nghiên cứu vào khai phá Luật kết hợp mờ và ứng dụng đối
Chương 1: Một số kiến thức cơ bản về khai phá dữ liệu
Chương 2: Khai phá luật kết hợp mờ
Chương 3: Ứng dụng khai phá dữ liệu trong mô hình dự báo
Kết luận
Tài liệu tham khảo
3
Số hóa bởi Trung tâm Học liệu CHƢƠNG 1. MỘT SỐ KIẾN THỨC CƠ BẢN VỀ KHAI PHÁ DỮ LIỆU
1.1. Khái niệm cơ bản về khai phá dữ liệu
1.1.1. Giới thiệu
Khai phá dữ liệu (data mining) là quá trình khám phá các tri thức mới và các tri
thức có ích ở dạng tiềm năng trong nguồn dữ liệu đã có. Đây là quá trình cốt lõi trong
khai phá tri thức từ CSDL.
Hình 1.1.Quá trình khai phá tri thức trong CSDL
Quá trình khai phá dữ liệu trải qua 3 bước chính sau:
Bƣớc 1: Chuẩn bị dữ liệu
Do dữ liệu được thu thập từ nhiều nguồn khác nhau nên có thể có những sai sót,
dư thừa và trùng lặp. Vì vậy bước chuẩn bị dữ liệu là bước rất quan trọng. Dữ liệu sau
bước chuẩn bị này sẽ nhỏ hơn, xử lý nhanh hơn. Chuẩn bị dữ liệu bao gồm các công
đoạn sau:
- Lọc dữ liệu (Data cleaning): Loại bỏ dữ liệu nhiễu, dữ liệu không thích hợp.
- Tích hợp dữ liệu (Data integration): Tích hợp dữ liệu từ các nguồn khác nhau.
Dữ liệu
thực
Kho dữ
liệu
Lọc và
cũng đều là mẫu hữu ích, đôi khi nó còn bị sai lệch. Vì vậy cần phải có những tiêu
chuẩn đánh giá phù hợp để trích xuất ra các tri thức thực sự có ích. Bước nàybao gồm
2 công đoạn:
- Đánh giá mẫu (Pattern evaluation): Đánh giá mẫu hoặc tri thức đã thu được.
- Biểu diễn tri thức (Knowledge Presentation): Biểu diễn những tri thức khai phá
được để người sử dụng dễ hiểu.
Đây là quá trình mang tính định tính với mục đích phát hiện tri thức và xây dựng
bài toán tổng kết.
Những khó khăn cần giải quyết trong bài toán KPDL là lượng dữ liệu lớn, kích
thước dữ liệu lớn, dữ liệu động và luôn tăng trưởng, các trường dữ liệu không phù hợp,
các giá trị bị thiếu, các trường dữ liệu bị thiếu,…
1.1.2. Khái niệm khai phá dữ liệu
Lĩnh vực KPDL và KDD đã cuốn hút các phương pháp, thuật toán và kỹthuật từ
nhiều chuyên ngành nghiên cứu khác nhau như học máy, thu nhận mẫu, CSDL, thống
kê, trí tuệ nhân tạo, thu nhận tri thức trong hệ chuyên gia,… nhằmhướng tới cùng một
mục tiêu thống nhất là trích lọc ra được các tri thức từ dữ liệu trong các CSDL khổng
lồ. Tính phong phú và đa dạng đó đã dẫn đến một thực trạng là tồn tại một số quan
niệm khác nhau về lĩnh vực nghiên cứu gần gũi nhất với lĩnh vực này - KDD. Với
5
Số hóa bởi Trung tâm Học liệu những gì đã trình bày ở trên, chúng ta có thể hiểu một cách sơ lược rằng KPDL là quá
trình tìm kiếm những thông tin (tri thức) hữu ích, tiềm ẩn và mang tính dự báo trong
các tập dữ liệu lớn. Như vậy, chúng ta nên gọi quá trình này là phát hiện tri thức. Tuy
nhiên các nhà khoa học trong lĩnh vực này đồng ý với nhau rằng hai thuật ngữ trên là
tương đương và có thể thay thế cho nhau. Họ lý giải rằng, mục đích chính của quá
trình phát hiện tri thức là thông tin và tri thức có ích, nhưng đối tượng mà chúng ta
phải xử lý rất nhiều trong suốt quá trình đó lại chính là dữ liệu.
là hướng nghiên cứu đầu tiên của luật kết hợp. Hầu hết các nghiên cứu ở thời kỳ đầu
về luật kết hợp đều liên quan đến luật kết hợp nhị phân. Trong dạng luật kết hợp này,
các mục (thuộc tính) chỉ được quan tâm là có hay không xuất hiện trong giao dịch của
CSDL chứ không quan tâm về “mức độ” xuất hiện. Có nghĩa là việc mua 20 chai bia
và 1 chai bia được xem là giống nhau. Thuật toán tiêu biểu nhất khai phá dạng luật này
là thuật toán Apriori và các biến thể của nó[4]. Đây là dạng luật đơn giản và như sau
này ta biết các dạng luật khác cũng có thể chuyển về dạng luật này bằng một số
phương pháp như rời rạc hóa, mờ hóa, … Một ví dụ về dạng luật này: “Mua bánh mì =
'yes' AND mua đường= 'yes' => mua sữa = 'yes'AND mua bơ = 'yes', với độ hỗ trợ
20% và độ tin cậy 80%”.
- Luật kết hợp có thuộc tính số và thuộc tính hạng mục (quantitative and
categorical association rule): Các thuộc tính của các CSDL thực tế có kiểu rất đa dạng
(nhị phân - binary, số - quantitative, hạng mục - categorical, …). Để phát hiện luật kết
hợp với các thuộc tính này, các nhà nghiên cứu đã đề xuất một số phương pháp rời rạc
hóa nhằm chuyển dạng luật này vềdạng nhị phân để có thể áp dụng các thuật toán đã
có[16].
- Luật kết hợp mờ (fuzzy association rule): Với những hạn chế còn gặp phải
trong quá trình rời rạc hóa các thuộc tính số (quantitative attributes), các nhà nghiên
cứu đã đề xuất luật kết hợp mờ nhằm khắc phục những hạn chếtrên và chuyển luật kết
hợp về một dạng tự nhiên hơn, gần gũi hơn với người sử dụng. Một ví dụ về dạng luật
này:“Ho khan = 'yes' AND sốt cao AND đau cơ = 'yes' AND khó thở ='yes' => Bị
nhiễm SARS = 'yes', với độ hỗ trợ 4% và độ tin cậy 85%”. Trong luật trên, điều kiện
sốt cao ở vế trái của luật là một thuộc tính đã được mờ hóa.
- Luật kết hợp nhiều mức (multi-level association rules): Ngoài các dạng luật
trên, các nhà nghiên cứu còn đề xuất một hướng nghiên cứu nữa về luật kết hợp là luật
kết hợp nhiều mức. Với cách tiếp cận này, người ta sẽ tìm kiếm thêm những luật có
dạng“Mua máy tính PC => Mua hệ điều hành AND mua phần mềm tiện ích văn
7
Số hóa bởi Trung tâm Học liệu
bảo. Có rất nhiều thuật toán song song khác nhau đã được đề xuất, chúng có thể phụ
thuộc hoặc độc lập với cấu hình phần cứng.
8
Số hóa bởi Trung tâm Học liệu - Luật kết hợp tiếp cận theo hướng tập thô (mining association rules based on
rough set): Tìm kiếm luật kết hợp dựa trên lý thuyết tập thô.
Ngoài ra, còn một số hướng nghiên cứu khác về khai phá luật kết hợp như: Khai
phá luật kết hợp trực tuyến, khai phá luật kết hợp được kết nối trực tuyến đến các kho
dữ liệu đa chiều (multidimensional data, data warehouse) thông qua công nghệ OLAP
(Online Analysis Processing), MOLAP (Multidimensional OLAP), ROLAP
(Relational OLAP), ADO (ActiveX Data Object) for OLAP,…
1.2.2. Các dạng dữ liệu có thể khai phá
Do KPDL được ứng dụng rộng rãi nên nó có thể làm việc với rất nhiều kiểu dữ
liệu khác nhau. Sau đây là một số kiểu dữ liệu điển hình.
- CSDL quan hệ (relational databases).
- CSDL đa chiều (multidimensional structures, data warehouses).
- CSDL dạng giao dịch (transactional databases).
- CSDL quan hệ - hướng đối tượng (object-relational databases).
- Dữ liệu không gian và thời gian (spatial and temporal data).
- Dữ liệu chuỗi thời gian (time-series data).
- CSDL đa phương tiện (multimedia databases) như âm thanh (audio), hình ảnh
(image), phim ảnh (video), …
- Dữ liệu Text và Web (text database & www).
1.3. Nhiệm vụ chính của khai phá dữ liệu
Rõ ràng rằng mục đích của khai phá dữ liệu là các tri thức chiết xuất được sẽ
được sử dụng cho lợi ích cạnh tranh trên thương trường và các lợi ích trong nghiên cứu
khoa học.Do đó, ta có thể coi mục đích chính của khai thác dữ liệu sẽ là mô tả và dự
1.3.3. Khai phá luật kết hợp (Association rule)
Trong lĩnh vực Data Mining, mục đích của luật kết hợp (Association Rule - AR)
là tìm ra các mối quan hệ giữa các đối tượng trong khối lượng lớn dữ liệu. Nội dung cơ
bản của luật kết hợp sẽ được trình bày kỹ hơn trong phần sau.
1.3.4. Gom nhóm (Clustering)
Là việc mô tả chung để tìm ra các tập xác định các nhóm hay các loại để mô tả
dữ liệu. Các nhóm có thể tách riêng nhau hoặc phân cấp hoặc gối lên nhau. Có nghĩa là
một dữ liệu có thể vừa thuộc nhóm này, vừa thuộc nhóm kia. Các ứng dụng khai phá
dữ liệu có nhiệm vụ gom nhóm như: Phát hiện tập các khách hàng có phản ứng giống
10
Số hóa bởi Trung tâm Học liệu nhau trong cơ sở dữ liệu tiếp thị, xác định các loại quang phổ từ các phương pháp đo
tia hồng ngoại.
1.3.5. Tổng hợp (Summarization)
Nhiệm vụ tổng hợp là việc sản sinh ra các mô tả đặc trưng cho một lớp. Các mô
tả này là một kiểu tổng hợp, tóm tắt mô tả các đặc tính chung của tất cả các bộ dữ liệu
thuộc một lớp.
Các mô tả đặc trưng thể hiện dưới dạng các luật thường có khuôn dạng:“Nếu
một bộ dữ liệu thuộc về một lớp đã chỉ ra trong tiền đề, thì bộ dữ liệu đó có tất cả các
thuộc tính đã nêu trong kết luận”. Những luật này có những đặc trưng khác biệt so với
các luật phân lớp. Luật phát hiện đặc trưng cho một lớp chỉ được sản sinh khi các bộ
dữ liệu thuộc về lớp đó.
1.3.6. Mô hình ràng buộc (Dependency modeling)
Bao gồm việc tìm kiếm một mô hình mô tả sự phụ thuộc đáng kể giữa các biến.
Các mô hình phụ thuộc tồn tại dưới hai mức: Mức cấu trúc của mô hình xác định các
biến nào là phụ thuộc cục bộ với nhau, mức định lượng của một mô hình xác định độ
mạnh của sự phụ thuộc theo một thước đo nào đó.
t
2
B, D
t
3
B, C
t
4
A, B, D
t
5
A, C
t
6
B, C
t
7
A, C
t
8
A, B, C, E
t
9
bản ghi chứa tập hợp , so với tổng số các bản ghi trong D - Ký hiệu supp(X Y)
(1.2)
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 . 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ó 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 hợp liên quan đến
nguyên nhân gây ra sự đứt liên lạc ở các tổng đài điện thoại).
Độ tin cậy:
Định nghĩa 1.3: Độ tin cậy của một luật kết hợp là tỷ lệ giữa số lượng các
bản ghi trong D chứa với số bản ghi trong D có chứa tập hợp X. Ký hiệu độ tin
cậy của một luật là conf(r). Ta có .
Nhận xét: Độ hỗ trợ và độ tin cậy có xác suất sau: Có thể định nghĩa độ tin cậy như sau:
Định nghĩa 1.4: Độ tin cậy 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 của tập hợp chứa X Y, so với tổng số các bản ghi chứa X.
13
Số hóa bởi Trung tâm Học liệu Nói rằng độ tin cậy của một luật là 90%, có nghĩa là có tới 90% số bản ghi chứa
X chứa luôn cả Y. Hay nói theo ngôn ngữ xác suất là: “Xác suất có điều kiện để xảy ra
sự kiện Y đạt 85%”. Điều kiện ở đây chính là: “Xảy ra sự kiện X”.
Như vậy, độ tin cậy của luật thể hiện sự tương quan (correlation) giữa X và Y.
Độ tin cậy đo mức độ tin cậy của luật, và người ta hầu như chỉ quan tâm đến những
luật có độ tin cậy cao. Ví dụ, một luật kết hợp đi tìm các nguyên nhân dẫn tới hỏng hóc
Tính chất 1.3: Giả sử A, B là hai tập hợp, và A là tập hợp không thường
xuyên thì B cũng là tập hợp không thường xuyên.
Định nghĩa 1.6: Một tập mục X được gọi là đóng (closed) nếu không có tập cha
nào của X có cùng độ hỗ trợ với nó, tức là không tồn tại một tập mục X' nào mà
và t(X) = t(X') (với t(X) và t(X') tương ứng là tập các giao chứa tập mục X và
X'). Ký hiệu tập phổ biến đóng là FCI.
Định nghĩa 1.7: Nếu X là phổ biến và không tập cha nào của X là phổ biến, ta
nói rằng X là một tập phổ biến lớn nhất (maximally frequent itemset). Ký hiệu tập tất
cả các tập phổ biến lớn nhất là MFI. Dễ thấy .
Khai phá luật kết hợp là công việc phát hiện ra (tìm ra, khám phá, phát hiện) các
luật kết hợp thỏa mãn các ngưỡng độ hỗ trợ ( ) và ngưỡng độ tin cậy ( ) cho trước.
Bài toán khai phá luật kết hợp được chia thành hai bài toán nhỏ, còn gọi là hai pha:
Pha 1: Tìm tất cả các tập phổ biến (tìm FI) trong CSDL T.
Pha 2: Sử dụng tập FI tìm được ở pha 1 để sinh ra các luật tin cậy (interesting
rules). Ý tưởng chung là nếu gọi ABCD và AB là các tập mục phổ biến, thì chúng ta
có thể xác định luật AB CD với tỷ lệ độ tin cậy:
(1.3)
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 pattern) dài
15
Số hóa bởi Trung tâm Học liệu
- Bƣớc 2: Gọi C
k
là tập các tập ứng viênkItemset, L
k
là tập các tập thường xuyên
k Itemset. Quá trình tìm tập L
k
trải qua ba công đoạn nhỏ:
16
Số hóa bởi Trung tâm Học liệu a) C'
k
là tập các tập k Itemset có được bằng cách hợp từng hai tập k-1 Itemset
thường xuyên trong L
k-1
có k-2 mục dữ liệu đầu tiên giống nhau, mục thứ k-1 khác
nhau (Bảng 1.2.c, Bảng 1.2.f).
b) Tìm tập ứng viên C
k
bằng cách loại bỏ những tập trong C
'
k
có chứa một tập
con k-1 Itemset nhưng không là tập k-1 Itemset thường xuyên (Bảng 1.2.d, Bảng
1.2.g).
c) Ứng với mỗi tập ứng viên trong C
k
B
C
6
C
D
2
D
E
2
E
G
1
Bƣớc 2:
- Lần lặp thứ nhất: Mọi tập trong C'
2
đều có tập con một mục dữ liệu là phần tử
của L
1
nên C
2
= C'
2
. Như vậy, tại bước này chưa sử dụng lợi ích của thuật toán Apriori.
A, D
1
A,E
A, E
A, E
2
B,C
17
Số hóa bởi Trung tâm Học liệu B, C
B, C
4
B,D
B,D
B,D
2
B,E
B,E
được tính bằng cách loại bỏ trong C
'
3
các tập {A, C, E}, {B, C, D}, {B, C, E}, {B, D,
E} do lần lượt chứa các tập con {C, E}, {C, D}, {C, E}, {D, E} không thuộc L
2
(không
là tập thường xuyên).
g) C'
3h) C
3i) L
3
3 Itemset
3 Itemset
Support
3 Itemset
A, B, C
A, B, C
2
- Lần lặp thứ 3: C'
4
= {{A,B,C,E}}, chứa {A, C, E} không là tập thường xuyên
C
4
= L
4
= . Ngừng lặp.
Thuật toán Apriori phát sinh số lượng lớn tập ứng viên. Có quá nhiều lần duyệt
toàn bộ CSDL để tính độ hỗ trợ của các mục dữ liệu. Thuật toán không thể giải được
khi số mục dữ liệu lớn. Dựa vào thuật toán Apriori, nhiều thuật toán mới được thiết kế
với những sửa đổi hoặc cải tiến. Nói chung có hai cách tiếp cận: một là sẽ giảm bớt số
lần duyệt qua toàn bộ CSDL, hai là thay thế toàn bộ CSDL với chỉ một bộ phận của nó
dựa vào tập mục dữ liệu thường xuyên hiện thời. Cách tiếp cận khác là dùng kỹ thuật
xén bớt để làm cho số tập ứng viên nhỏ đi.
1.4.2.2. Thuật toán Partition
Năm 1995, Ashok Savasere và đồng nghiệp ở Viện tính toán trường Đại học kỹ
thuật Georgia, Atlanta, Hoa Kỳ đề xuất thuật toán Partition để phân dữ liệu thành
nhiều phần nhỏ, mỗi phần có thể đưa vào bộ nhớ trong để xử lý [6].
Copyright: Tài liệu đại học ©