Số hóa bởi Trung tâm Học liệu
LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH NGƢỜI HƢỚNG DẪN KHOA HỌC
TS. NGUYỄN HUY ĐỨC
Thái Nguyên - 2014
Số hóa bởi Trung tâm Học liệu
i
LỜI CẢM ƠN
Lời đầu tiên tôi xin gửi lời cảm ơn chân thành và biết ơn sâu sắc tới TS.
Nguyễn Huy Đức – Trường Cao đẳng Sư phạm Trung ương, người đã chỉ bảo và
hướng dẫn tận tình cho tôi trong suốt quá trình nghiên cứu khoa học và thực hiện
luận văn này.
Tôi xin chân thành cảm ơn sự dạy bảo, giúp đỡ, tạo điều kiện và khuyến
khích tôi trong quá trình học tập và nghiên cứu của các thầy cô giáo của Viện Công
nghệ Thông tin, Trường Đại học Công nghệ Thông tin và Truyền thông – Đại học
Thái Nguyên.
Và cuối cùng, tôi xin gửi lời cảm ơn tới gia đình, người thân và bạn bè –
những người luôn ở bên tôi những lúc khó khăn nhất, luôn động viên tôi, khuyến
khích tôi trong cuộc sống và trong công việc.
Thái Nguyên, ngày 12 tháng 03 năm 2014
Tác giả Nguyễn Hồng Sâm
Số hóa bởi Trung tâm Học liệu
iii
MỤC LỤC
Trang phụ bìa Trang
LỜI CẢM ƠN i
LỜI CAM ĐOAN ii
MỤC LỤC iii
DANH MỤC CÁC KÝ HIỆU VÀ CÁC CHỮ VIẾT TẮT v
DANH MỤC CÁC BẢNG vi
DANH MỤC HÌNH VẼ vii
LỜI MỞ ĐẦU 1
CHƢƠNG 1: TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU VÀ KHAI PHÁ TẬP
MỤC THƢỜNG XUYÊN 3
1.1. Khái niệm về khai phá tri thức và khai phá dữ liệu 3
1.2. Kiến trúc của hệ thống khai phá dữ liệu 4
1.3. Quá trình khai phá dữ liệu 5
1.4. Một số kỹ thuật khai phá dữ liệu 6
1.5. Các cơ sở dữ liệu phục vụ cho khai phá dữ liệu 9
3.1. Bài toán phát hiện nhóm các mặt hàng có lợi nhuận cao 56
3.2. Mô tả dữ liệu 56
3.3. Xây dựng chương trình 60
3.4. Thực nghiệm khai phá tìm tập mục lợi ích cao 60
3.5. Kết quả thực nghiệm 61
KẾT LUẬN 62
TÀI LIỆU THAM KHẢO 63
Tiếng Việt 63
Tiếng Anh 63
PHỤ LỤC 65 Số hóa bởi Trung tâm Học liệu
v
DANH MỤC CÁC KÝ HIỆU VÀ CÁC CHỮ VIẾT TẮT
Trong luận văn này, dùng thống nhất các ký hiệu và chữ viết tắt sau:
Các ký hiệu:
I = {i
1
, i
2
,…, i
n
}: Tập n mục dữ liệu.
DB = {T
1
, T
2
Số hóa bởi Trung tâm Học liệu
vi
DANH MỤC CÁC BẢNG
Bảng 1.1: Biểu diễn ngang của cơ sở dữ liệu giao tác. 13
Bảng 1.2: Biểu diễn dọc của cơ sở dữ liệu giao tác. 13
Bảng 1.3: Ma trận giao tác của cơ sở dữ liệu cho ở bảng 1.1. 14
Bảng 1.4: Cơ sở dữ liệu giao tác minh họa thực hiện thuật toán Apriori. 20
Bảng 1.5: Cơ sở dữ liệu giao tác minh họa thực hiện thuật toán COFI-tree. 22
Bảng 1.6: Các mục dữ liệu và độ hỗ trợ 23
Bảng 1.7: Các mục dữ liệu thường xuyên đã sắp thứ tự. 23
Bảng 1.8: Các mục dữ liệu trong giao tác sắp xếp giảm dần theo độ hỗ trợ. 23
Bảng 2.1: Cơ sở dữ liệu giao tác. 30
Bảng 2.2: Bảng lợi ích. 30
Bảng 2.3: Lợi ích các giao tác của cơ sở dữ liệu bảng 2.1 và bảng 2.2. 36
Bảng 2.4: Lợi ích TWU của các mục dữ liệu 36
Bảng 2.5: Các mục dữ liệu có lợi ích TWU c . 36
Bảng 2.6: Các mục dữ liệu trong giao tác sắp giảm dần theo lợi ích TWU. 37
Bảng 2.7: Lợi ích các tập mục ứng viên 43
Bảng 2.8: Cơ sở dữ liệu ví dụ cho thuật toán UP-Growth 52
Bảng 2.9: Bảng lợi ích của CSDL bảng 2.8 53
Bảng 2.10: Các giao tác được sắp lại các mục dữ liệu theo TWU giảm dần 53
Bảng 3.1: Dữ liệu đã trích chọn để khai phá 57
Bảng 3.2: Bảng lợi ích các mặt hàng 58
Hình 2.5: Cây C-COUI-tree sau khi lưu mẫu CBE và CE. 40
Hình 2.6: Cây C-COUI-tree sau khi xây dựng xong. 40
Hình 2.7: Cây D-COUI-tree. 41
Hình 2.8: Cây B-COUI-tree. 41
Hình 2.9: Các bước khai phá cây D-COUI-Tree. 42
Hình 2.10: Cây TWUI-tree có các mục dữ liệu sắp tăng dần theo trật tự từ điển của
cơ sở dữ liệu bảng 2.1 và bảng 2.2. 49
Hình 2.11: Cây TWUI-tree có các mục dữ liệu sắp giảm dần theo số lần xuất hiện
của chúng trong cơ sở dữ liệu bảng 2.1 và bảng 2.2. 49
Hình 2.12: Cây TWUI-tree có các mục dữ liệu sắp giảm dần theo TWU của chúng
trong cơ sở dữ liệu bảng 2.1 và bảng 2.2. 50
Hình 2.13: Cây
TWUI-tree
của CSDL bảng 2.8 với minutil = 40 54
Hình 2.14: Cây UP-tree của CSDL bảng 2.8 với minutil = 40 54
Hình 3.1: Dữ liệu đã mã hóa chuẩn bị cho khai phá 59
Hình 3.2: Dữ liệu mã hóa của bảng 3.2 59
Hình 3.3: Giao diện chương trình 60
Hình 3.4: Giao diện kết quả khai phá 61
Số hóa bởi Trung tâm Học liệu
1
LỜI MỞ ĐẦU
Khai phá tập mục thường xuyên đóng vai trò quan trọng trong nhiều nhiệm
vụ khai phá dữ liệu. Khai phá tập mục thường xuyên xuất hiện như là bài toán con
của nhiều lĩnh vực khai phá dữ liệu như khám phá luật kết hợp, khám phá mẫu tuần
tự,… Bài toán khai phá luật kết hợp do Agrawal, T.Imielinski và A. N. Swami đề
xuất và nghiên cứu lần đầu vào năm 1993 với mục tiêu là phát hiện các tập mục
thường xuyên, từ đó tạo các luật kết hợp. Trong mô hình của bài toán này, giá trị
luận văn: “ KHAI PHÁ TẬP MỤC LỢI ÍCH CAO SỬ DỤNG CẤU TRÚC
CÂY TIỀN TỐ”
Nội dung luận văn gồm 3 chương:
Chương 1: Tổng quan về khai phá dữ liệu và khai phá tập mục thường xuyên.
Chương 2: Khai phá tập mục lợi ích cao sử dụng cấu trúc cây tiền tố.
Chương 3: Chương trình thực nghiệm và ứng dụng.
Số hóa bởi Trung tâm Học liệu
3
CHƢƠNG 1: TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU VÀ KHAI PHÁ
TẬP MỤC THƢỜNG XUYÊN
1.1. Khái niệm về khai phá tri thức và khai phá dữ liệu
KPDL là việc rút trích tri thức một cách tự động và hiệu quả từ một khối dữ
liệu lớn. Tri thức đó thường ở dạng các mẫu có tính chất không tầm thường, không
tường minh (ẩn), chưa được biết đến và có tiềm năng mang lại lợi ích. Có một số
nhà nghiên cứu còn gọi KPDL là phát hiện tri thức trong cơ sở dữ liệu (Knowledge
Discovery in Database – KDD). Ở đây chúng ta có thể coi KPDL là cốt lõi của quá
trình phát hiện tri thức. Quá trình phát hiện tri thức gồm các bước [3], [6]:
Bƣớc 1: Trích chọn dữ liệu (data selection): Là bước trích chọn những tập
dữ liệu cần được khai phá từ các tập dữ liệu lớn (databases, data ware houses).
Bƣớc 2: Tiền xử lý dữ liệu (data preprocessing): Là bước làm sạch dữ liệu
(xử lý dữ liệu không đầy đủ, dữ liệu nhiễu, dữ liệu không nhất quán,…v.v), rút gọn
dữ liệu (sử dụng các phương pháp thu gọn dữ liệu, histograms, lấy mẫu…v.v), rời
rạc hóa dữ liệu (dựa vào histograms, entropy, phân khoảng, v.v). Sau bước này, dữ
liệu sẽ nhất quán, đầy đủ, được rút gọn và được rời rạc hóa.
Bƣớc 3: Biến đổi dữ liệu (data transformation): Là bước chuẩn hóa và làm
mịn dữ liệu để đưa dữ liệu về dạng thuận lợi nhất nhằm phục vụ cho các kỹ thuật
khai thác ở bước sau.
Bƣớc 4: Khai phá dữ liệu (data mining): Đây là bước quan trọng và tốn
Giao diện đồ họa cho người dùng
(Graphical user interface)
Đánh giá mẫu
(Pattern evaluation)
Máy khai phá dữ liệu
(Data mining engine)
Máy chủ CSDL hay kho dữ liệu
(Database or Ware house Server)
Cơ sở dữ liệu
Kho dữ liệu
Các lưu trữ
thông tin khác
Làm sạch; tích hợp dữ liệu; lọc
Cơ sở
tri thức
(Knowledge-base)
Số hóa bởi Trung tâm Học liệu
5 Giải thuật
khai phá DL
Thống kê
tóm tắt
Dữ liệu
trực tiếp
Thu thập và
tiền xử lý DL
Xác định dữ
liệu liên quan
Xác định
nhiệm vụ
Mẫu
Số hóa bởi Trung tâm Học liệu
6
Hình 1.3: Quá trình KPDL
+ Xác định nhiệm vụ: Xác định chính xác vấn đề cần giải quyết.
+ Xác định các dữ liệu liên quan dùng để xây dựng giải pháp.
+ Thu thập các dữ liệu có liên quan và xử lý chúng thành dạng sao cho giải
thuật khai phá dữ liệu có thể hiểu được. Ở đây có thể gặp một số vấn đề: dữ liệu
phải được sao ra nhiều bản (nếu được chiết suất vào các tệp), quản lý tập các tệp dữ
liệu, phải lặp đi lặp lại nhiều lần toàn bộ quá trình (nếu mô hình dữ liệu thay đổi
v.v…).
+ Chọn thuật toán khai phá dữ liệu thích hợp và thực hiện việc khai phá dữ
Một ví dụ tiêu biểu về cây quyết định:
Hình 1.4: Cây quyết định
Trong hình 1.4 là một cây quyết định cho lớp mua laptop, chỉ ra một khách
hàng sẽ mua hay không mua một laptop. Mỗi nút lá đại diện một lớp mà đánh giá
mua laptop là Yes hay No. Sau khi mô hình này được xây dựng, chúng ta có thể dự
đoán việc có thể mua một laptop hay không dựa vào những thuộc tính khách hàng
mới là tuổi và nghề nghiệp. Cây quyết định có thể ứng dụng rộng rãi trong nhiều
hoạt động của đời sống thực.
Phân nhóm dữ liệu [6]
Phân nhóm là kỹ thuật khai phá dữ liệu tương tự như phân lớp dữ liệu. Tuy
nhiên, sự phân nhóm dữ liệu là quá trình học không được giám sát, là quá trình
nhóm những đối tượng vào trong những lớp tương đương, đến những đối tượng
trong một nhóm là tương đương nhau, chúng phải khác với những đối tượng trong
những nhóm khác. Trong phân lớp dữ liệu, một bản ghi thuộc về lớp nào là phải xác
định trước, trong khi phân nhóm không xác định trước. Trong phân nhóm, những
đối tượng được nhóm lại cùng nhau dựa vào sự giống nhau của chúng. Sự giống
nhau giữa những đối tượng được xác định bởi những chức năng giống nhau. Thông
thường những sự giống về định lượng như khoảng cách hoặc độ đo khác được xác
định bởi những chuyên gia trong lĩnh vực của mình.
TID
Số hóa bởi Trung tâm Học liệu
8
Hình 1.5: Mẫu kết quả của nhiệm vụ phân cụm dữ liệu
Đa số các ứng dụng phân nhóm được sử dụng trong sự phân chia thị trường.
Với sự phân nhóm khách hàng vào trong từng nhóm, những doanh nghiệp có thể
cung cấp những dịch vụ khác nhau tới nhóm khách hàng một cách thuận lợi. Ví dụ,
dựa vào chi tiêu, số tiền trong tài khoản và việc rút tiền của khách hàng, một ngân
hàng có thể xếp những khách hàng vào những nhóm khác nhau. Với mỗi nhóm,
ngân hàng có thể cho vay những khoản tiền tương ứng cho việc mua nhà, mua xe,…
Trong trường hợp này ngân hàng có thể cung cấp những dịch vụ tốt hơn và cũng
chắc chắn rằng tất cả các khoản tiền cho vay đều có thể thu hồi được. Ta có thể
tham khảo một khảo sát toàn diện về kỹ thuật và thuật toán phân nhóm trong.
Hồi qui (Regression): Là việc học một hàm ánh xạ từ một tập dữ liệu thành một
biến dự đoán có giá trị thực. Nhiệm vụ hồi qui tương tự như phân lớp, điểm khác
nhau chính là ở chỗ thuộc tính để dự báo là liên tục chứ không rời rạc [6]. Việc dự
báo các giá trị số thường được làm bởi các phương pháp thống kê cổ điển chẳng hạn
như hồi qui tuyến tính. Tuy nhiên, phương pháp mô hình hóa cũng được sử dụng
[6].
Mức cấu trúc của mô hình (thường dưới dạng đồ thị) xác định các biến phụ thuộc
cục bộ vào các biến khác; Mức định lượng của mô hình xác định mức độ phụ
thuộc của biến [6]. Những phụ thuộc này thường được biểu thị dưới dạng luật.
Quan hệ phụ thuộc cũng có thể biểu diễn dưới dạng mạng tin cậy [6]. Đó là
đồ thị có hướng không có dạng chu trình, các nút biểu diễn thuộc tính và trọng số
chỉ liên kết phụ thuộc giữa các nút đó.
Phát hiện sự thay đổi và độ lệch (change and deviation dectection): Nhiệm vụ này
tập trung vào khám phá những thay đổi có ý nghĩa trong dữ liệu dựa vào các giá trị
chuẩn hay độ đo đã biết trước, phát hiện độ lệch đáng kể giữa nội dung của tập con
dữ liệu và nội dung mong đợi. Hai mô hình độ lệch thường dùng là lệch theo thời
gian và lệch theo nhóm. Độ lệch theo thời gian là sự thay đổi có nghĩa của dữ liệu
theo thời gian. Độ lệch theo nhóm là sự khác nhau giữa dữ liệu trong hai tập con dữ
liệu, tính cả trường hợp tập con của đối tượng này thuộc tập con kia, nghĩa là xác
định dữ liệu trong một nhóm con của đối tượng có khác nhau đáng kể so với toàn
bộ đối tượng [6].
1.5. Các cơ sở dữ liệu phục vụ cho khai phá dữ liệu
Dựa vào những kiểu dữ liệu mà kỹ thuật khai phá áp dụng, có thể chia dữ
liệu thành các loại khác nhau.
Cơ sở dữ liệu quan hệ
Đến nay, hầu hết dữ liệu được lưu giữ dưới dạng cơ sở dữ liệu quan hệ. Cơ
sở dữ liệu quan hệ là một nguồn tài nguyên lớn nhất chứa những đối tượng mà
chúng ta cần khai phá. Cơ sở dữ liệu quan hệ có cấu trúc cao, dữ liệu được mô tả
bởi một tập những thuộc tính và lưu trong những bảng. Khai phá dữ liệu trên cơ sở
dữ liệu quan hệ chủ yếu tập trung khai phá mẫu. Ví dụ, trong cơ sở dữ liệu của một
Số hóa bởi Trung tâm Học liệu
10
ngân hàng, ta có thể tìm được những khách hàng có mức chi tiêu cao, ta có thể phân
loại những khách hàng này dựa vào quá trình chi tiêu của họ. Cũng với việc phân
Số hóa bởi Trung tâm Học liệu
11
Số lượng trang web đang bùng nổ trên thế giới, web có mặt ở khắp mọi nơi,
duyệt web đã là nhu cầu của mọi tầng lớp trong xã hội. Thông tin trên web đang
phát triển với tốc độ rất cao, khai phá thông tin trên web (web mining) đã trở thành
một lĩnh vực nghiên cứu chính của khai phá dữ liệu, được các nhà nghiên cứu đặc
biệt quan tâm. Khai phá dữ liệu web thông thường được chia thành ba phạm trù
chính: Khai phá cách dùng web (web usage mining), khai phá cấu trúc web (web
structure mining) và khai phá nội dung web (web content mining).
Khai phá cách dùng web tập trung vào việc khai phá thông tin của người truy
cập web. Với những thông tin này người khai phá dữ liệu có thể cung cấp những
thông tin hữu ích cho người dùng và các nhà kinh doanh.
1.6. Một số ứng dụng của khai phá dữ liệu
KPDL được vận dụng trong nhiều lĩnh vực khác nhau nhằm khai thác nguồn
dữ liệu phong phú được lưu trữ trong các hệ thống thông tin. Tuỳ theo bản chất của
từng lĩnh vực, việc vận dụng KPDL có những cách tiếp cận khác nhau.
KPDL được vận dụng có hiệu quả để giải quyết các bài toán phức tạp trong
những ngành đòi hỏi kỹ thuật cao như: tìm kiếm mỏ dầu từ ảnh viễn thám, xác định
vùng gãy trong ảnh địa chất để dự đoán thiên tai, cảnh báo hỏng hóc trong các hệ
thống sản xuất.
Phân nhóm và dự đoán là những kỹ thuật rất cần thiết cho việc quy hoạch và
phát triển hệ thống quản lý và sản xuất trong thực tế như: dự đoán tái sử dụng điện
năng cho các công ty cung cấp điện, lưu lượng viễn thông cho các công ty điện
thoại, mức độ tiêu thụ sản phẩm cho các nhà sản xuất, giá trị của sản phẩm trên thị
trường cho các công ty tài chính hay phân nhóm khách hàng tiềm năng.
Ngoài ra KPDL còn được áp dụng trong việc giải quyết các vấn đề xã hội
như: phát hiện tội phạm hay tăng cường an ninh xã hội và mang lại những hiệu quả
thiết thực cho các hoạt động trong đời sống hàng ngày.
Một số ứng dụng cụ thể nhƣ sau [3], [6]:
phá luật kết hợp, bài toán đầu tiên dẫn đến bài toán khai phá tập mục thường xuyên.
1.7.1.1. Cơ sở dữ liệu giao tác
Định nghĩa 1.1: Cho tập các mục (item)
n
iiiI , ,,
21
. Một giao tác
(transaction) T là một tập con của I, T I. Cơ sở dữ liệu giao tác là một tập các giao
tác
m
TTTDB , ,,
21
. Mỗi giao tác được gán một định danh TID. Một tập mục con
X I, gồm k mục phân biệt được gọi là một k-tập mục. Giao tác T gọi là chứa tập
mục X nếu X T.
Biểu diễn cơ sở dữ liệu giao tác: Cơ sở dữ liệu giao tác thường được biểu
diễn ở dạng biểu diễn ngang, biểu diễn dọc và biểu diễn bởi ma trận giao tác.
Số hóa bởi Trung tâm Học liệu
13
Biểu diễn ngang: Cơ sở dữ liệu là một danh sách các giao tác. Mỗi giao tác
có một định danh TID và một danh sách các mục dữ liệu trong giao tác đó. Ví dụ 1.1:
Bảng 1.1: Biểu diễn ngang của cơ sở dữ liệu giao tác.
TID
Mục dữ liệu
T1
C
T1, T2, T4, T5, T6, T7, T8, T11
D
T1, T2, T3, T4, T5
E
T9, T10
F
T4, T7
Ma trận giao tác: Cơ sở dữ liệu giao tác
12
, , ,
m
DB T T T
trên tập các mục (item)
12
, , ,
n
I i i i
được biểu diễn bởi ma trận nhị phân
( ) ,
pq m n
Mm
ở đó:
Số hóa bởi Trung tâm Học liệu
14
1
0
1
1
0
0
T3
1
1
0
1
0
0
T4
0
0
1
1
0
1
T5
0
0
1
1
0
0
T6
1
0
1
0
T11
1
1
1
0
0
0
1.7.1.2. Tập mục thƣờng xuyên và luật kết hợp
Định nghĩa 1.2: Cho tập mục
.XI
Ta gọi độ hỗ trợ (Support) của X trong cơ sở
dữ liệu giao tác
,DB
ký hiệu
sup( ),X
là tỷ lệ phần trăm các giao tác chứa
X
trên
tổng số các giao tác trong
,DB
tức là:
DB
XTDBT
X
}
)sup(
Ta có:
1)sup(0 X
với mọi tập mục
Luật kết hợp có hai thông số quan trọng là độ hỗ trợ và độ tin cậy.
Số hóa bởi Trung tâm Học liệu
15
Định nghĩa 1.5: Độ hỗ trợ (Support) của một luật kết hợp X→Y, ký hiệu là
sup(X→Y), là độ hỗ trợ của tập mục
,XY
sup( ) sup( ).X Y X Y
Như vậy độ hỗ trợ của luật kết hợp
XY
chính là xác suất
()P X Y
của sự
xuất hiện đồng thời của
X
và
Y
trong một giao tác.
Ta có:
1)sup(0 YX
.
Định nghĩa 1.6: Độ tin cậy (Confidence) của một luật
,XY
ký hiệu
( ),conf X Y
là tỷ lệ phần trăm giữa số giao tác chứa
XY
và số giao tác chứa
X
YX
và ta có
0 ( ) 1.conf X Y
Các luật thỏa mãn cả hai ngưỡng độ hỗ trợ tối thiểu (minsup) và độ tin cậy
tối thiểu (minconf), tức thỏa mãn
sup( )XY
minsup và
()conf X Y
minconf,
được gọi là luật kết hợp mạnh.
Tính chất cơ bản của tập mục thƣờng xuyên:
Cho cơ sở dữ liệu giao tác
DB
và ngưỡng độ hỗ trợ tối thiểu minsup. Các tập
mục thường xuyên có các tính chất sau:
(1) Nếu
YX,
là các tập mục và
YX
thì
sup( ) sup( ).XY
(2) Nếu một tập mục là không thường xuyên thì mọi tập cha của nó của nó
cũng không thường xuyên.
(3) Nếu một tập mục là thường xuyên thì mọi tập con khác rỗng của nó cũng
là tập mục thường xuyên.
Tính chất (3) được gọi là tính chất Apriori, tính chất này là cơ sở để rút gọn
,YX
kiểm tra độ tin
cậy của luật
\X Y Y
có thỏa mãn độ tin cậy tối thiểu không. Bài toán thứ hai này
đơn giản, mọi khó khăn nằm ở bài toán thứ nhất, hầu hết các nghiên cứu về luật kết
hợp đều tập trung giải quyết bài toán thứ nhất là tìm các tập mục thường xuyên.
1.7.2. Cách tiếp cận khai phá tập mục thƣờng xuyên
Các nghiên cứu về khai phá tập mục thường xuyên tập trung vào tìm các
thuật toán mới hoặc đề xuất giải pháp nâng cao hiệu quả các thuật toán đã có. Phần
này sẽ trình bày khái quát các kỹ thuật chính để khai phá tập mục thường xuyên.
Bài toán khai phá tập mục thường xuyên có thể chia thành hai bài toán nhỏ:
tìm các tập mục ứng viên và tìm các tập mục thường xuyên. Tập mục ứng viên là
tập mục mà ta hy vọng nó là tập mục thường xuyên, phải tính độ hỗ trợ của nó để
kiểm tra. Tập mục thường xuyên là tập mục có độ hỗ trợ lớn hơn hoặc bằng ngưỡng
hỗ trợ tối thiểu cho trước. Đã có rất nhiều thuật toán tìm tập mục thường xuyên
được công bố, ta có thể phân chúng theo hai tiêu chí sau:
- Phương pháp duyệt qua không gian tìm kiếm.
- Phương pháp xác định độ hỗ trợ của tập mục.
Phương pháp duyệt qua không gian tìm kiếm được phân chia thành hai cách:
duyệt theo chiều rộng (Breadth First Search – BFS) và duyệt theo chiều sâu (Depth
First Search – DFS).
Duyệt theo chiều rộng là duyệt qua cơ sở dữ liệu gốc để tính độ hỗ trợ của tất
cả các tập mục ứng viên có (k-1) mục trước khi tính độ hỗ trợ của các tập mục ứng
viên có k mục. Với cơ sở dữ liệu có n mục dữ liệu, lần gặp thứ k phải kiểm tra độ
hỗ trợ của tất cả
)!(!
!
knk
n
Hình 1.7: Phân loại các thuật toán khai phá tập mục thường xuyên.
Phần tiếp sau mô tả chi tiết nội dung hai thuật toán tiêu biểu và là cơ sở để
phát triển các thuật toán mới trong luận văn: Thuật toán Apriori tiêu biểu cho
phương pháp sinh ra các tập mục ứng viên và kiểm tra độ hỗ trợ của chúng; Thuật
toán FP-growth, đại diện cho phương pháp không sinh ra tập mục ứng viên, cơ sở
dữ liệu được nén lên cấu trúc cây, sau đó khai phá bằng cách phát triển dần các mẫu
trên cây này.
1.7.3. Một số thuật toán điển hình tìm tập mục thƣờng xuyên
1.7.3.1. Thuật toán Apriori
Apriori là thuật toán khai phá tập mục thường xuyên do R. Agrawal và R.
Srikant đề xuất vào năm 1993 [4]. Ý tưởng của thuật toán Apriori còn là nền tảng
cho việc phát triển nhiều thuật toán khai phá tập mục thường xuyên khác về sau.
Ý tưởng chính của thuật toán như sau: sinh ra các tập mục ứng viên từ các
tập mục thường xuyên ở bước trước, sử dụng kỹ thuật “tỉa” để bỏ đi những tập mục
ứng viên không thoả mãn ngưỡng hỗ trợ cho trước. Cơ sở của kỹ thuật này là tính
chất Apriori: Bất kỳ tập con nào của tập mục thường xuyên cũng phải là tập mục
thường xuyên. Vì vậy các tập mục ứng viên gồm k mục có thể được sinh ra bằng
BFS
BFS
Đếm
Copyright: Tài liệu đại học ©