BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI
---------------------------------------
Bùi Chí Thành
PHÁT TRIỂN THUẬT TOÁN KHAI PHÁ LUẬT KẾT HỢP
DỰA VÀO SỰ PHÂN LỚP DỮ LIỆU
Chuyên ngành: CÔNG NGHỆ THÔNG TIN
LUẬN VĂN THẠC SĨ KỸ THUẬT
NGƯỜI HƯỚNG DẪN KHOA HỌC
TS. NGUYỄN HỮU TRỌNG
HÀ NỘI – 2013
LỜI CẢM ƠN
Trước hết, tác giả muốn gửi lời cảm ơn đến người Thầy hướng dẫn khoa học
TS. Nguyễn Hữu Trọng - Trường Đại học Nha Trang đã làm một công việc tuyệt
vời. Mặc dù rất bận rộn với với tư cách là một nhà quản lý, một nhà nghiên cứu và
một giảng viên nhưng thầy luôn luôn dành thời gian để giúp đỡ, hỗ trợ tác giả hoàn
thành luận văn này.
Tác giả xin chân thành cảm ơn quý Thầy Cô Viện Công nghệ thông tin và
Truyền Thông – Trường Đại học Bách Khoa Hà Nội, quý Thầy cô Trường Đại học
Nha Trang, … bởi sự quan tâm giúp đỡ tận tâm trong quá trình học tập, nghiên cứu
cũng như trong quá trình hoàn thành luận văn.
Cuối cùng xin chân thành cảm ơn đến người vợ thân yêu, những người thân,
bạn bè và đồng nghiệp đã động viên, giúp đỡ trong suốt quá trình học tập và viết
luận văn.
Hà Nội, tháng 3 năm 2013
Bùi Chí Thành
2
LỜI CAM ĐOAN
Tôi xin cam đoan đây là công trình nghiên cứu của
tôi dưới sự hướng dẫn của TS Nguyễn Hữu Trọng.
Các số liệu, kết quả nêu trong luận án là trung thực và
chưa từng được ai công bố trong bất kỳ công trình
nào khác.
Hà Nội, ngày 15 tháng 3 năm 2013
Bùi Chí Thành
3
MỤC LỤC
DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT..........................................6
DANH MỤC CÁC BIỂU BẢNG .............................................................................7
DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ ..................................................................8
MỞ ĐẦU ....................................................................................................................9
CHƯƠNG 1. TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU .....................................11
1.1 MỞ ĐẦU .........................................................................................................11
1.2 CÁC MÔ HÌNH KHAI PHÁ DỮ LIỆU .........................................................14
1.2.1 Luật kết hợp ..............................................................................................14
1.2.2 Phân lớp dữ liệu ........................................................................................15
1.2.3 Phân nhóm dữ liệu ....................................................................................16
1.3 CÁC KHÁI NIỆM CƠ BẢN...........................................................................17
1.3.1 Cơ sở dữ liệu giao tác ...............................................................................17
1.3.2 Tính chất của tập thường xuyên ...............................................................20
1.4 KHAI PHÁ LUẬT KẾT HỢP.........................................................................21
1.4.1 Cách tiếp cận khai phá luật kết hợp ..........................................................21
1.4.2 Nhóm thuật toán duyệt theo chiều rộng....................................................23
1.4.3 Nhóm thuật toán duyệt theo chiều sâu......................................................29
1.4.4 Thuật toán Partition_P_Tree .....................................................................36
1.4.5 Thuật toán phân hoạch kép ......................................................................37
1.5 KẾT LUẬN .....................................................................................................39
CHƯƠNG 2. PHÁT TRIỂN THUẬT TOÁN KHAI PHÁ LUẬT KẾT HỢP
DỰA VÀO SỰ PHÂN LỚP DỮ LIỆU ..................................................................40
4
2.1 PHÂN LỚP DỮ LIỆU ...................................................................................40
2.1.1 Một số định nghĩa trên CSDL giao tác .....................................................40
2.1.2 Phân lớp CSDL giao tác ...........................................................................41
2.2 THUẬT TOÁN PHÂN LỚP DỮ LIỆU ..........................................................42
2.2.1 Mô tả bài toán ...........................................................................................42
2.2.2 Xử lý .........................................................................................................42
2.3 PHÁT TRIỂN THUẬT TOÁN TÌM TẬP THƯỜNG XUYÊN TRÊN CSDL
ĐÃ PHÂN LỚP .....................................................................................................45
2.3.1 Phát triển thuật toán xây dựng FP_Tree ...................................................45
2.3.2 Thuật toán Apriori ....................................................................................45
2.4 VÍ DỤ MINH HỌA .........................................................................................46
CHƯƠNG 3. XÂY DỰNG CHƯƠNG TRÌNH VÀ KẾT QUẢ THỬ NGHIỆM
...................................................................................................................................50
3.1 CẤU TRÚC DỮ LIỆU ....................................................................................50
3.2 CÁC THỦ TỤC CÀI ĐẶT .............................................................................51
3.3 KẾT QUẢ THỬ NGHIỆM .............................................................................57
3.4 ĐÁNH GIÁ THUẬT TOÁN ...........................................................................58
PHẦN KẾT LUẬN ..................................................................................................59
1. NHỮNG KẾT QUẢ ĐẠT ĐƯỢC ....................................................................59
2. HƯỚNG PHÁT TRIỂN ....................................................................................60
TÀI LIỆU THAM KHẢO ......................................................................................61
0.
5
DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT
Trong suốt luận văn này, các ký hiệu, chữ viết tắt dùng thống nhất:
Ký hiệu:
I = {x 1 , x 2 , …, x n }: Tập n mục dữ liệu.
T = {t 1 , t 2 , …, t m }: Cơ sở dữ liệu có m giao tác.
x j : Mục dữ liệu thứ j.
t i : Giao tác thứ i.
m: Số giao tác của một cơ sở dữ liệu giao tác.
n: Số mục dữ liệu của một cơ sở dữ liệu giao tác.
A, B, C, …: Tên của các mục dữ liệu trong cơ sở dữ liệu giao tác ví dụ.
X, Y: Là các tập con của tập mục dữ liệu I, X, Y ⊆ I.
S: Là tập con các giao tác của cơ sở dữ liệu giao tác T, S ⊆ T.
X = ABC thay cho X = {A, B, C} trong các ví dụ minh họa.
S = 1234 thay cho S = {t 1 , t 2 , t 3 , t 4 } trong các ví dụ minh họa.
S 0 , Minsup: Ngưỡng tối thiểu.
Supp(x i ) thay cho Supp({x i }).
∥X∥: Số phần tử của tập hợp X.
Subset(U) = {X | X ⊆ U}: Tập các tập con của U.
Viết tắt:
CSDL: Cơ sở dữ liệu.
DL: Dữ liệu.
MDL: Mục dữ liệu.
TT: Thuật toán.
6
DANH MỤC CÁC BIỂU BẢNG
Bảng 1.1 Biểu diễn ngang của cơ sở dữ liệu giao tác ...............................................18
Bảng 1.2 Biểu diễn dọc của cơ sở dữ liệu giao tác ...................................................18
Bảng 1.3 Ma trận giao tác của cơ sở dữ liệu giao tác cho ở bảng 1.1.......................19
Bảng 2.1 CSDL giao tác mẫu..................................................................................496
Bảng 2.2 CSDL đã được sắp xếp giảm dần của độ hỗ trợ ........................................47
Bảng 2.3 CSDL có trọng số rút gọn ..........................................................................48
Bảng 2.4 CSDL có trọng số được loại bỏ những mục không thường xuyên ............49
Bảng 2.5 CSDL có trọng số được rút gọn thỏa ngưỡng S 0 =2 ..................................49
Bảng 3.1 So sánh kết quả trước và sau khi phân lớp ................................................57
7
1.
DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ
Hình 1.1. Quá trình khám phá tri thức .............................................................12
Hình 1.2 Kiến trúc hệ thống khai phá dữ liệu ..................................................13
Hình 1.3 Cây quyết định...................................................................................16
Hình 1.4 Phân loại thực toán khai phá luật kết hợp .........................................23
Hình 1.5 Kết quả thuật toán AIS ......................................................................24
Hình 1.6 Kết quả thuật toán Apriori .................................................................26
Hình 1.7 Những biến đổi dữ liệu của FP_Tree ................................................30
Hình 1.8 FP_Tree của dữ liệu bảng 1.1 ............................................................31
Hình 1.9 Thành phần của FP_Tree...................................................................31
Hình 1.10 Cấu trúc cây SOTrieIT ....................................................................34
Hình 1.11 SOTrieIT của dữ liệu ở bảng 1.1 .....................................................35
Hình 2.1 Cây trọng số W_Tree ........................................................................42
Hình 2.2 Cây trọng số W_Tree dựa vào bảng 2.1 ............................................48
Hình 2.3 Cây FP_Tree trên CSDL có trọng số rút gọn ..................................489
2.
8
3.
MỞ ĐẦU
Thông tin được thu thập hầu như ở khắp mọi nơi trong cuộc sống của chúng ta
ở rất nhiều lĩnh vực đời sống xã hội, quản lý kinh tế, khoa học kỹ thuật, …và với sự
phát triển nhanh chóng các ứng dụng công nghệ thông tin và Internet đã tạo ra nhiều
cơ sở dữ liệu khổng lồ mức độ terabytes đến mức độ petabytes. Để khai thác hiệu
quả nguồn thông tin từ các cơ sở dữ liệu lớn hỗ trợ tiến trình ra quyết định, bên
cạnh các phương pháp khai thác thông tin truyền thống, các nhà nghiên cứu đã phát
triển các phương pháp, kỹ thuật và phần mềm mới hỗ trợ tiến trình khám phá, phân
tích tổng hợp thông tin.
Có nhiều kỹ thuật khai phá dữ liệu trong đó khai phá luật kết hợp là kỹ thuật
rất nổi tiếng. Bài toán khai phá luật kết hợp được giải theo hai bước chính: Bước
một, tìm tất cả các tập thường xuyên theo ngưỡng S 0 cho trước. Bước hai, dựa vào
các tập thường xuyên, tìm các luật kết hợp. Tất cả khó khăn của bài toán tập trung ở
bước một. Các nghiên cứu về khai phá luật kết hợp đều tập trung cải tiến tốc độ xử
lý, dung lượng bộ nhớ và số lần truy cập đĩa. Tốc độ xử lý phụ thuộc vào số giao tác
trong cơ sở dữ liệu giao tác.
Mục tiêu của luận văn là tìm hiểu một số thuật toán khai phá luật kết hợp, đề
xuất phương án phân lớp dữ liệu giao tác bằng cách thêm ”trọng số” cho mục dữ
liệu, rút gọn số giao tác trong cơ sở dữ liệu nhằm rút gọn không gian xử lý, lưu trữ.
Đưa ra thuật toán cải tiến thuật toán Apriori và FP_Growth để tìm tập thường xuyên
trên cơ sở dữ liệu đã phân lớp.
Bố cục của luận văn bao gồm phần mở đầu, ba chương nội dung, phần kết
luận và tài liệu tham khảo.
Chương 1 trình bày tổng quan về khai phá dữ liệu: Các mô hình khai phá dữ
liệu, các khái niệm cơ bản về khai phá luật kết hợp và một số thuật toán khai phá
luật kết hợp: Các thuật toán duyệt theo chiều rộng (AIS, Apriori, DIC), các thuật
9
toán duyệt theo chiều sâu (FP_Tree, RARM), thuật toán PARTITION_P_TREE,
thuật toán phân hoạch kép.
Đóng góp chính của luận văn được trình bày trong chương 2. Chương
này, tác giả đề xuất phương án phân lớp dữ liệu để rút gọn số giao tác trong
CSDL và phát triển 2 thuật toán (Apriori, Fp_Tree) trên cơ sở dữ liệu đã phân
lớp để tìm tập thường xuyên.
Chương 3. Xây dựng chương trình và kết quả thử nghiệm
Cuối cùng, phần kết luận nêu những đóng góp của luận văn, hướng phát triển
và những vấn đề quan tâm của tác giả.
10
4.
CHƯƠNG 1. TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU
1.1 MỞ ĐẦU
Khai phá dữ liệu – Data Mining là tiến trình khám phá tri thức tiềm ẩn trong
các cơ sở dữ liệu. Cụ thể hơn, đó là tiến trình trích lọc, sản sinh những tri thức hoặc
các mẫu tiềm ẩn, chưa biết nhưng hữu ích từ các cơ sở dữ liệu lớn. Khai phá dữ liệu
là tiến trình khái quát các sự kiện rời rạc trong dữ liệu thành các tri thức mang tính
khái quát, tính quy luật hỗ trợ tích cực cho các tiến trình ra quyết định.
Nguồn dữ liệu phục vụ cho khai phá dữ liệu có thể là các cơ sở dữ liệu lớn hay
các kho dữ liệu có hoặc không có cấu trúc. Có thể chia khai phá dữ liệu thành hai
dạng chính: khai phá dữ liệu theo hướng kiểm tra và khai phá dữ liệu theo hướng
khám phá. Trong khai phá dữ liệu theo hướng kiểm tra tính đúng đắn của giả thiết.
Khai phá dữ liệu theo hướng kiểm tra, người dùng đề xuất giả thiết. Khai phá dữ
liệu theo hướng kiểm tra bao gồm: truy vấn, báo cáo, phân tích đa chiều, phân tích
thống kê, … Ngược lại, khai phá dữ liệu theo hướng khám phá sẽ tìm kiếm các tri
thức tiềm ẩn trong cơ sở dữ liệu bằng cách tiến hành xem xét tất cả các giả thiết khả
dĩ. Do không gian tìm kiếm lớn, nên rất nhiều heuristic đã được đề xuất nhằm nâng
cao hiệu suất của các thuật giải tìm kiếm.
Tri thức rút ra có thể được dùng để:
- Giải thích dữ liệu: Cung cấp sự hiểu biết sâu sắc và rất hữu ích về hành
vi của các đối tượng, giúp cho các doanh nghiệp hiểu rõ hơn những khách
hàng của họ.
- Dự báo, dự đoán giá trị của những đối tượng mới như: Khuynh hướng mua
hàng của khách hàng, xác định rủi ro tín dụng đối với một khách hàng, định hướng
tập trung nguồn lực của doanh nghiệp.
Các bước của quá trình khai phá dữ liệu:
1. Tìm hiểu lĩnh vực của bài toán (ứng dụng): Các mục đích của bài toán, các
tri thức cụ thể của lĩnh vực
11
2. Tạo nên (thu thập) một tập dữ liệu phù hợp
3. Làm sạch và tiền xử lý dữ liệu
4. Giảm kích thước của dữ liệu, chuyển đổi dữ liệu: Xác định các thuộc tính
quan trọng, giảm số chiều, …
5. Lựa chọn chức năng khai phá dữ liệu: Tóm tắt hóa, phân loại/phân lớp, hồi
quy/dự đoán, kết hợp, phân cụm
6. Lựa chọn/phát triển các giải thuật khai phá dữ liệu phù hợp
7. Tiến hành quá trình khai phá dữ liệu
8. Đánh giá mẫu thu được và biểu diễn tri thức: Hiện thị hóa, chuyển đổi, bỏ
đi các mẫu dư thừa, …
9. Sử dụng các tri thức được khám phá
Khai phá dữ liệu đóng vai trò quan trọng trong quá trình khám phá tri thức,
được Han và Kamber [8] mô tả trong hình 1.1:
Hình 1.1. Quá trình khám phá tri thức
12
Kiến trúc hệ thống khai phá tri thức được Han và Kamber [8] mô tả trong hình 1.2:
Hình 1.2 Kiến trúc hệ thống khai phá dữ liệu
Quá trình khai phá dữ liệu trải qua ba bước:
Bước một: Lọc dữ liệu hay gọi là tiền xử lý. Khi dữ liệu được thu thập từ
nhiều nguồn khác nhau nên có thể có những sự sai sót, dư thừa và trùng lặp. Lọc dữ
liệu là cắt bỏ những dư thừa để dữ liệu được định dạng thống nhất. Dữ liệu sau khi
lọc và chỉnh sửa sẽ nhỏ hơn, xử lý nhanh chóng hơn.
Chẳng hạn, trong bài toán tìm quy luật mua hàng của khách hàng trong một
siêu thị, ta tìm xem một khách hàng thường cùng mua những mặt hàng nào để sắp
xếp những món hàng đó gần nhau. Từ dữ liệu nguồn do siêu thị cung cấp, có thể có
nhiều thuộc tính không cần thiết cho khai phá dữ liệu như: Mã khách hàng, nhà
cung cấp, đơn giá hàng, người bán hàng… Các thuộc tính này cần cho quản lý bán
hàng nhưng không cần cho khai phá dữ liệu, ta loại bỏ các thuộc tính này khỏi dữ
liệu trước khi khai phá dữ liệu.
13
Bước hai: Khai phá dữ liệu, là công việc chính, sử dụng các thuật toán khác
nhau để khai phá các kiến thức tiềm ẩn trong dữ liệu.
Bước ba: Hậu xử lý, là quá trình ước lượng kết quả khai phá theo yêu cầu
của người dùng. Nhiều kỹ thuật khai phá dữ liệu được ứng dụng cho một nguồn
dữ liệu, các kỹ thuật khác nhau cho các kết quả có thể khác nhau. Các kết quả
được ước lượng bởi những tiêu chí đánh giá nào đó, nếu cuối cùng kết quả
không thỏa mãn yêu cầu, chúng ta phải làm lại với kỹ thuật khác cho đến khi có
kết quả mong muốn.
1.2 CÁC MÔ HÌNH KHAI PHÁ DỮ LIỆU
Nói chung, có hai mô hình khai phá dữ liệu: Mô tả và suy diễn. Mô tả dữ liệu
là tổng kết hoặc diễn tả những đặc điểm chung của những thuộc tính dữ liệu trong
kho dữ liệu. Suy diễn là quá trình dựa trên dữ liệu hiện thời để dự đoán những quy
luật được phát hiện từ các mối liên hệ giữa các thuộc tính của dữ liệu. Có nhiều
cách khai phá dữ liệu được nghiên cứu, trong đó có ba cách được các nhà nghiên
cứu sử dụng nhiều nhất là: Luật kết hợp, phân lớp dữ liệu và phân nhóm dữ liệu.
1.2.1 Luật kết hợp
Khái niệm luật kết hợp được Agrawal và nhóm nghiên cứu đưa ra năm
1993[9]. Mục tiêu của luật kết hợp là tìm ra những mối tương quan giữa những mục
dữ liệu thường xuyên trong cơ sở dữ liệu được lưu trữ trong kho dữ liệu.
Ví dụ 1.1
Trong một hiệu sách lưu lại các phiếu mua sách, người ta phát hiện ra rằng:
Trong số những người mua quyển "Các khái niệm và kỹ thuật khai phá dữ liệu" thì
có 40% số người đó mua thêm quyển "Hệ quản trị cơ sở dữ liệu", và 25% mua
thêm quyển "Kho dữ liệu".
Trong ví dụ trên, hai luật kết hợp được tìm thấy:
-
Có 40% số người mua quyển "Các khái niệm và kỹ thuật khai phá dữ
liệu" thì đồng thời mua quyển "Hệ quản trị cơ sở dữ liệu".
14
-
Có 25% số người mua quyển "Các khái niệm và kỹ thuật khai phá dữ
liệu" thì đồng thời mua quyển "Kho dữ liệu".
Với những quy tắc được khám phá trên, ta có thể sắp xếp các quyển sách có
liên quan với nhau ở vị trí gần nhau để giúp cho người mua sách thuận tiện hơn.
Những quy tắc đó cũng giúp cho nhà sách có chiến lược kinh doanh tốt hơn.
Luật kết hợp được sử dụng rộng rãi trong nhiều lĩnh vực khác nhau như: Kinh
doanh, sản xuất, giao thông, viễn thông, giáo dục, quản lý thị trường, …
1.2.2 Phân lớp dữ liệu
Khái niệm phân lớp dữ liệu được Han và Kamber tổng kết năm 2000 trong [8].
Phân lớp dữ liệu là xây dựng một mô hình mà có thể chia các đối tượng thành
những lớp khác nhau để dự đoán giá trị bị mất tại một số thuộc tính của dữ liệu hay
tiên đoán giá trị của dữ liệu sẽ xuất hiện trong tương lai.
Quá trình phân lớp dữ liệu được thực hiện qua hai bước. Bước thứ nhất: Dựa
vào tập hợp dữ liệu huấn luyện, xây dựng một mô hình mô tả những đặc trưng của
những lớp dữ liệu hoặc những khái niệm, đây là quá trình học có giám sát, học theo
mẫu được cung cấp trước. Bước thứ hai: Từ những lớp dữ liệu hoặc những khái
niệm đã được xác định trước, dự đoán giá trị của những đối tượng quan tâm.
Một kỹ thuật phân lớp dữ liệu được Han và Kamber đưa ra là cây quyết định.
Mỗi nút của cây đại diện một quyết định dựa vào giá trị thuộc tính tương ứng. Kỹ thuật
này đã được nhiều tác giả nghiên cứu và đưa ra nhiều thuật toán: Murthy S. K. đã
nghiên cứu toàn diện về cây quyết định [10], phân lớp Bayes.
15
Một ví dụ tiêu biểu về cây quyết định:
Tuổi
<30
30-35
Sinh viên
Yes
>35
Giáo sư
Yes
No
Yes
No
Hình 1.3 Cây quyết định
Trong hình 1.3 là một cây quyết định cho lớp mua máy 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 tuổi và
nghề nghiệp của khách hàng. 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.
1.2.3 Phân nhóm dữ liệu
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, và nhóm những
đối tượng vào trong những lớp tương đương [8], để 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, 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 hàm đánh giá sự tương tự. Thông thường
những hàm định lượng như hàm đo khoảng cách, hàm xác định độ đo,… được xác
định bởi những chuyên gia trong lĩnh vực chuyên môn của mình.
16
Đ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 từng nhóm khách hàng một cách thuận lợi. Ví
dụ, dựa vào số tiền trong tài khoản, mục đích chi tiêu 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.
1.3 CÁC KHÁI NIỆM CƠ BẢN
1.3.1 Cơ sở dữ liệu giao tác
1.3.1.1 Định nghĩa 1.1
Cho I = {x 1, x 2 , …, x n} là tập hợp các mục dữ liệu. Mỗi x i ∈ I gọi là một mục dữ
liệu hay là một thuộc tính. Một tập con {x i1 , xi2 , …, x ik} ⊆ I được gọi là một giao tác
trên I. Đặt t i = {x i1 , x i2 , …, x ik}, t i gọi là định danh của giao tác {x i1 , x i2 , …, x ik}.
Một tập hợp gồm m định danh giao tác T = {t 1 , t 2 , …, t m }, với m bất kỳ được gọi là
một cơ sở dữ liệu giao tác trên I.
Mỗi tập con X ⊆ I với ‖X‖ = k được gọi là tập k-mục dữ liệu hay k-thuộc
tính của I (trong trường hợp không quan tâm đến số mục dữ liệu của X, ta gọi
tắt: X là tập mục dữ liệu), mỗi tập con S ⊆ T gọi là tập định danh giao tác. Để
thuận tiện trong các ví dụ, ta viết S = {t 1 , t 2 , t 3 }, XY thay cho X ∪ Y.
1.3.1.2 Biểu diễn cơ sở dữ liệu giao tác
Có hai cách biểu diễn tập cơ sở dữ liệu giao tác: Biểu diễn ngang và biểu diễn dọc.
Biểu diễn ngang: Một 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 giao tác (t id ) và một danh sách những mục dữ liệu trong giao
tác đó.
17
Ví dụ 1.2
Giao tác
Mục dữ liệu
t1
A, B, E
t2
B, D
t3
B, C
t4
A, B, D
t5
A, C
t6
B, C
t7
A, C
t8
A, B, C, E
t9
A, B, C
Bảng 1.1 Biểu diễn ngang của cơ sở dữ liệu giao tác
Biểu diễn dọc: Một cơ sở dữ liệu là một danh sách những mục dữ liệu, với
mỗi mục dữ liệu có một danh sách tất cả các định danh của các giao tác chứa mục
dữ liệu này.
Mục dữ liệu Định danh giao tác
A
t1, t4, t5, t7, t8, t9
B
t1, t2, t3, t4, t6, t8, t9
C
t3, t5, t6, t7, t8, t9
D
t2, t4
E
t1, t8
Bảng 1.2 Biểu diễn dọc của cơ sở dữ liệu giao tác
Ma trận giao tác: Cho một cơ sở dữ liệu giao tác T = {t1, t2, …, tm} trên
I = {x1, x2, …, xn}. Ma trận giao tác của T là ma trận M = (mij)mxn được định nghĩa:
1 khi x j ∈ t i
m ij =
0 khi x j ∉ t i
18
Ví dụ 1.3
Với cơ sở dữ liệu giao tác ở bảng 1.1 ta có ma trận giao tác là:
A
B
C
D
E
t1
1
1
0
0
1
t2
0
1
0
1
0
t3
0
1
1
0
0
t4
1
1
0
1
0
t5
1
0
1
0
0
t6
0
1
1
0
0
t7
1
0
1
0
0
t8
1
1
1
0
1
t9
1
1
1
0
0
Bảng 1.3 Ma trận giao tác của cơ sở dữ liệu giao tác cho ở bảng 1.1
1.3.1.3 Độ hỗ trợ (support)
Độ hỗ trợ của một tập mục dữ liệu X ⊆ I trong cơ sở dữ liệu giao tác T, ký
hiệu Supp(X) là tổng số các giao tác trong T chứa X.
Supp(X) = ∥{t ∈ T | X ⊆ t}∥.
Với cơ sở dữ liệu cho ở bảng 1.1 ta có:
Supp(A) = 6, Supp(B) = 7,
Supp(ABC) = 2,
Supp(DE) = 0.
1.2.1.4 Tập mục dữ liệu thường xuyên (frequent itemset)
Cho S 0 là một số nguyên, ta nói X là tập mục dữ liệu thường xuyên theo
ngưỡng S 0 (gọi tắt là tập thường xuyên) nếu Supp(X) ≥ S 0 .
Nếu X = {x i } và Supp(X) ≥ S 0 ta nói : x i là mục dữ liệu thường xuyên.
Với cơ sở dữ liệu giao tác cho ở bảng 1.1 ta có:
AB, AC, BC: là các tập thường xuyên theo ngưỡng S 0 = 4.
19
A, B, C: là các mục dữ liệu thường xuyên theo ngưỡng S 0 = 5.
1.2.1.5 Luật kết hợp (Association rule)
Một luật kết hợp trên cơ sở dữ liệu giao tác T là một biểu thức có dạng
X → Y, với X, Y ⊆ I và X ∩ Y = φ.
Độ hỗ trợ của luật kết hợp X → Y, được định nghĩa và ký hiệu:
Supp(X → Y) = Supp(XY).
Với cơ sở dữ liệu giao tác cho ở bảng 1.1 ta có:
Supp(A → B) = Supp(AB) = 4,
Supp(AB → C) = Supp(ABC) = 2,
Supp(AB → E) = Supp(ABE) = 2,
Supp(BC → E) = Supp(BCE) = 1.
Luật kết hợp f: X → Y trên T là luật thường xuyên theo ngưỡng S 0 nếu
Supp(X → Y) ≥ S 0 .
Với cơ sở dữ liệu giao tác cho ở bảng 1.1 ta có:
f: A → B là luật thường xuyên theo ngưỡng S 0 = 4 vì Supp(AB) = 4 ≥ 4
f: AB → C không là luật thường xuyên theo ngưỡng S0 = 4 vì Supp(ABC) = 2 < 4
Độ tin cậy (Confidence) của luật X → Y, được định nghĩa và ký hiệu:
p = Conf(X → Y) = Supp(XY) / Supp(X).
Với C 0 ∈ (0, 1] ta nói f: X → Y gọi là luật tin cậy (Confident rule) theo
ngưỡng S 0 và C 0 nếu f là luật thường xuyên theo ngưỡng S 0 và Conf(X → Y) ≥ C 0 .
Với cơ sở dữ liệu giao tác cho ở bảng 1.1 ta có:
f: A → B là luật tin cậy theo ngưỡng S 0 = 4 và C 0 = 0.5 vì Supp(AB) = 4 ≥ 4
và Conf(A → B) = Supp(AB) / Supp(A) = 4/7 = 0.55 > 0.5.
1.3.2 Tính chất của tập thường xuyên
Tính chất 1.1 Gọi Fre(T, S 0 , I) là tập tất cả các tập mục dữ liệu thường xuyên
theo ngưỡng S 0 của cơ sở dữ liệu giao tác T trên I. Ta có các tính chất sau:
20
- Xem thêm -