Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

ĐẠI HỌC THÁI NGUYÊN
KHOA CÔNG NGHỆ THÔNG TIN

LÊ THỊ VIỆT HOA

KHAI PHÁ DỮ LIỆU VÀ THUẬT TOÁN KHAI PHÁ
LUẬT KẾT HỢP SONG SONG Chuyên ngành: KHOA HỌC MÁY TÍNH
Mã số : 60.48.01
LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
LỜI CAM ĐOAN

Tôi xin cam đoan đề tài khoa học “Khai phá dữ liệu và thuật toán khai
phá luật kết hợp song song” này là công trình nghiên cứu của bản thân tôi.
Các số liệu và kết quả nghiên cứu nêu trong luận văn này là trung thực, được
các tác giả cho phép sử dụng và các tài liệu tham khảo như đã trình bày trong
luận văn. Tôi xin chịu trách nhiệm về luận văn của mình.


1.5.
Các cơ sở dữ liệu phục vụ cho khai phá dữ liệu
10
1.6.
Các phương pháp chính trong khai phá dữ liệu
11
1.7.
Các ứng dụng của khai phá dữ liệu
13
1.8
. Khai phá dữ liệu và các lĩnh vực liên quan
14
1.9.
Các thách thức trong phát hiện tri thức và khai phá dữ liệu
15
1.10.
Kết luận chương 1
16
Chương 2: KHAI PHÁ LUẬT KẾT HỢP TRONG CƠ SỞ DỮ LIỆU
17
2.1.
Mở đầu
17
2.2
Luật kết hợp
18
2.2.1
Các khái niệm cơ bản
18
2.2.2.


50
3.1.
Nguyên lý thiết kế thuật toán song song
50
3.2. Hư ớng tiếp cận chính trong thiết kế thuật toán khai phá luật kết hợp song song
51
3.2.1.
Mô hình song song dữ liệu
51
3.2.2.
Mô hình song song thao tác
51
3.3.
Một số thuật toán khai phá luật kết hợp song song
52
3.3.1 Thuật toán Count Distribution (CD)
52
3.3.2. Thuật toán Data Distribution (DD)
54
3.3.3. Thuật toán Candidate Distribution
58
3.3.4. Thuật toán song song Fp-Growth
60
3.3.5 Thuật toán song song Eclat
65
3.4. Phân tích, đánh giá và so sánh việc thực hiện thuật toán
71
3.4.1. Phân tích và đánh giá thuật toán song song
71

D
Cơ sở dữ liệu giao dịch
D
i
Phần thứ i của cơ sở dữ liệu D
Item
Mục
Itemset
Tập mục
I
Tập các mục
KDD
Phát hiện tri thức trong cơ sở dữ liệu (Knowledge Discovery
in Database)
CSDL
Cơ sở dữ liệu (Database)
k-itemset
Tập mục gồm k mục
L
k
Tập các k-itemset phổ biến
MPI
Truyền thông điệp
minconf
Ngưỡng tin cậy tối thiểu
minsup
Ngưỡng hỗ trợ tối thiểu
OLAP
Phân tích trực tuyến
OLTP

Bảng 2.1.b. Tập giao dịch D của cửa hàng 33
Hình 3.1. Mô hình song song dữ liệu
51
Hình 3.2. Mô hình song song thao tác 52
Hình 3.3. Sơ đồ thuật toán Count Distribution
52
Hình 3.4. Phát hi ện các tập mục phổ biến bởi thuật toán song song CD 54
Hình 3.5. Sơ đồ mô tả thuật toán Data Distribution 55
Hình 3.6: Sơ đồ luồng thuật toán Data Distribution
56
Hình 3.7: Phát hi ện các tập mục phổ biến bởi thuật toán song song DD 57
Hình 3.8: Các phân hoạch CSDL và các FP-Tree cục bộ ban đầu 61
Bảng 3.1: Các mẫu điều kiện cơ sở và các FP-Tree điều kiện cơ sở 62
Hình 3.9: Quá trình sinh tập phổ biến bởi 2 bộ xử lý P
1
và P
2
63
Hình 3.10: Quá trình chuyển đổi CSDL theo chiều dọc 70

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
1

MỞ ĐẦU
Với sự bùng nổ và phát triển của công nghệ thông tin đã mang lại nhiều
hiệu quả đối với khoa học cũng như các hoạt động thực tế, trong đó khai phá dữ
liệu là một lĩnh vực mang lại hiệu quả thiết thực cho con người. Khai phá dữ
liệu đã giúp người sử dụng thu được những tri thức hữu ích từ những cơ sở dữ
liệu hoặc các kho dữ liệu khổng lồ khác.
Cơ sở dữ liệu trong các đơn vị, tổ chức kinh doanh, quản lý khoa học

song song hiệu quả cho luật kết hợp.
Phương pháp nghiên cứu của luận văn là tổng hợp các kết quả dự a trên
các bài báo khoa học trong một số hội thảo quốc tế và các bài báo chuyên
ngành, từ đó trình bày các vấn đề khai phá dữ liệu và xây dựng một số thuật
toán khai phá luật kết hợp song song.
Nội dung luận văn được trình bày trong 3 chương và phần kết luận
Chương 1: Tổng quan về khai phá dữ liệu: Giới thiệu tổng quan về quá
trình khai phá dữ liệu, kho dữ liệu và khai phá dữ liệu; kiến trúc của một hệ
thống khai phá dữ liệu; Nhiệm vụ chính và các phương pháp khai phá dữ liệu.
Chương 2: Khai phá luật kết hợp song song: Chương này trì nh bày tổng
quan về luật kết hợp; phát biểu bài toán khai phá dữ liệu, phát hiện luật kết hợp;
các khái niệm cơ bản luật kết hợp và các phương pháp khai phá luật kết hợp;
khai phá luật kết hợp với một số khái niệm mở rộng.
Chương 3: Một số phương pháp khai phá luật kết hợp song song và phân
tích đánh giá các thuật toán song song .

Thái Nguyên 01 tháng 10 năm 2008
Tác giả
Lê Thị Việt Hoa

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
3
dùng.
• Cơ sở tri thức (Knowledge-base): Đây là miền tri thức dùng để tìm kiếm
hay đánh giá độ quan trọng của các mẫu kết quả thu được. Tri thức này có thể
bao gồm một sự phân cấp khái niệm dùng để tổ chức các thuộc tính hay các giá
trị thuộc tính ở các mức trừu tượng khác nhau.
• Máy khai phá dữ liệu (Data mining engine): là một hệ thống khai phá
dữ liệu cần phải có một tập các Modul chức năng để thực hiện công việc, chẳng
hạn như kết hợp, phân lớp, phân cụm.
• Modul đánh giá mẫu ( Pattern evaluation): Bộ phận tương tác với các
Modul khai phá dữ liệu để tập trung vào việc duyệt tìm các mẫu đáng được quan
tâm. Nó có thể dùng các ngưỡng về độ quan tâm để lọc mẫu đã khám phá được.
Cũng có thể Modul đánh giá mẫu được tích hợp vào Modul khai phá dữ liệu,
tùy theo cách cài đặt của phương pháp khai phá dữ liệu được dùng.
• Giao diện đồ họa cho người dùng (Graphical user interface) Bộ phận
này cho phép người dùng giao tiếp với hệ thống khai phá dữ liệu. Thông qua
giao diện này người dùng tương tác với hệ thống bằng cách đặc tả một yêu cầu
khai phá hay một nhiệm vụ, c ung cấp thông tin trợ giúp cho việc tìm kiếm và
thực hiện khai phá thăm dò trên các kết quả khai phá trung gian. Ngoài ra bộ
phận này còn cho phép người dùng xem các lược đồ CSDL, lược đồ kho dữ liệu,
các đánh giá mẫu và hiển thị các mẫu trong các khuôn dạng khác nhau.
1.3. Các giai đoạn của quá trình khai phá dữ liệu
Các thuật toán khai phá dữ liệu thường được mô tả như những chương
trình hoạt động trực tiếp trên tệp dữ liệu. Với các phương pháp học máy và
thống kê trước đây, bước đầu tiên là thuật toán thường nạp toàn bộ tệp (file) dữ
liệu vào trong bộ nhớ. Khi chuyển sang các ứng dụng công nghiệp liên quan đến
việc khai phá các kho dữ liệu lớn, mô hình này không thể đáp ứng được. Không
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
5

chỉ bởi nó không thể nạp hết dữ liệu vào trong bộ nhớ mà còn khó có thể chiết

nhiệm
vụ
Xác
định dữ
liệu liên
quan
Thu thập
và tiền
xử lý dữ
liệu
Giải thuật
khai phá
dữ liệu
DL trực
tiếp
Thống kê tóm tắt
Mẫu
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
6

Bước ba: Sau 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 cho các kết quả có thể khác nhau. Các kết quả được ước lượng
bởi những quy tắc 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.4. Một số kỹ thuật khai phá dữ liệu
Mục đích của khai phá dữ liệu là chiết xuất ra các tri thức có lợi cho kinh
doanh hay cho nghiên cứu khoa học… Do đó, ta có thể xem mục đích của khai
phá dữ liệu sẽ là mô tả các sự kiện và dự đoán. Các mẫu khai phá dữ liệu phát
hiện được nhằm vào mục đích này. Dự đoán liên quan đến việc sử dụng các biến 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 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 [13, 24]
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ữn g đố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 nhau 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.
Tuổi
30-35

>35

Yes
Sinh viên
Hình 1.4: 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 [13,
23]. 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ểm 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 [13, 24]. +
+
+
+ +
+
+

0
0 0
0
0
0
0
0
0
0
0 0
0 0
Hình 1.5: Mẫu kết quả của nhiệm vụ hồi quy

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
9

Ứng dụng của hồi quy là rất nhiều, ví dụ: dự đoán số lượng sinh vật phát
quang hiện thời trong khi rừng bằng cách dò tìm vi sóng bằng thiết bị cảm biến
từ xa; dự đoán khả năng tử vong của bệnh nhân khi biết các kết quả xét nghiệm
chuẩ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… hình 1.5 chỉ ra mẫu kết quả hồi quy tuyến tính đơn giản, ở đây tổng
số nợ được điều chỉnh cho phù hợp giống như một hàm thu nhập tuyến tính.
Việc điều chỉnh này là không đáng kết bởi vì chỉ tồn tại một tương quan yếu
giữa hai biến.
Tổng hợp (summarization): Là công việc liên quan đến các phương pháp tìm
kiếm một mô tả cô đọng cho tập con dữ liệu [23, 24]. Các kỹ thuật tổng hợp
thường được áp dụng trong việc phân tích dữ liệu có tính thăm dò và báo cáo tự
động.
Mô hình hóa phụ thuộc (dependency modeling): Là việc tìm kiếm mô hình mô
tả các phụ thuộc quan trọng giữa các biến. Mô hình phụ thuộc tồn tại ở hai mức:

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 tích những mục chi tiêu của khách hàng, chúng ta có thể
cung cấp một số thông tin của khách hàng đến những doanh nghiệp khác. Giả sử
rằng một khách hàng chi mỗi tháng 500 đô la cho thời trang, nếu được phép,
ngân hàng có thể cung cấp thông tin về khách hàng này cho những cửa hàng
thời trang.
Cơ sở dữ liệu giao tác
Cơ sở dữ liệu giao tác là tập hợp những bản ghi giao dịch, trong đa số các
trường hợp chúng là những bản ghi các dữ liệu hoạt động của doanh nghiệp, tổ
chức. Với tính phổ biến của máy tính và thương mại điện tử, ngày nay có rất
nhiều cơ sở dữ liệu giao tác. Khai phá dữ liệu trên cơ sở dữ liệu giao tác tập
trung vào khai phá luật kết hợp, tìm mối tương quan giữa những mục dữ liệu
của bản ghi giao dịch. Nghiên cứu sâu về cơ sở dữ liệu giao tác được mô tả chi
tiết ở phần sau.
Cơ sở dữ liệu không gian
Cơ sở dữ liệu không gian bao gồm hai phần: Phần thứ nhất là dữ liệu
quan hệ hay giao tác, phần thứ hai là thông tin định vị hoặc thông tin địa lý.
Những luật kết hợp trên cơ sở dữ liệu không gian mô tả mối quan hệ giữa các
đặc trưng trong cơ sở dữ liệu không gian. Dạng của luật kết hợp không gian có
dạng X ⇒ Y, với X, Y là tập hợp những vị từ không gian. Những thuật toán
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
11

khai phá luật kết hợp không gian tương tự như khai phá luật kết hợp nhưng thêm
những vị từ về không gian.
Cơ sở dữ liệu có yếu tố thời gian
Giống như cơ sở dữ liệu không gian, cơ sở dữ liệu có yếu tố thời gian bao
gồm hai phần: Phần thứ nhất là dữ liệu quan hệ hay giao tác, phần thứ hai là
thông tin về thời gian xuất hiện dữ liệu ở phần thứ nhất. Những luật kết hợp có
yếu tố thời gian có nhiều thông tin hơn những luật kết hợp cơ bản. Ví dụ, từ luật

được biết trước). Các đối tượng được gom cụm sao cho mức độ tương tự giữa
các đối tượng trong cùng một cụm là lớn nhất và mức độ tương tự giữa các đối
tượng nằm trong các cụm khác nhau là nhỏ nhất. Lớp bài toán phân cụm còn
được gọi là học không giám sát hạy học không thầy.
• Luật kết hợp (Association rules)
Luật kết hợp là dạng luật biểu diễn tri thức ở dạng khá đơn giản. 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 các giá trị dữ
liệu trong cơ sở dữ liệu. Mẫu đầu của giải thuật khai phá dữ liệu là tập luật kết
hợp tìm được.
Ví dụ về luật kết hợp: Một cửa hàng bán văn phòng phẩm đăng thông tin
quảng cáo mỗi tuần trên một tờ báo địa phương. Khi một mặt hàng, chẳng hạn
như mực in đã được chỉ định bán giảm giá, người bán hàng xác định các mặt
hàng khác nào sẽ được mua cùng lúc với mực in. Họ thấy rằng giấy A4 và mực
in được khách hàng mua cùng chiếm 30% và kẹp giấy được mua kèm với mực
in là 40%. Dựa vào các mối quan hệ này, người bán hàng bày bán giấy A4 và
kẹp giấy gần với mặt hàng mực in khi bán giảm giá. Họ cũng quyết định không
đưa các mặt hàng này vào danh sách các mặt hàng giảm giá. Các hành động này
nhằm mục đích tăng thêm toàn bộ khối lượng hàng bán ra bởi việc bán các mặt
hàng mua mực in.
Có 2 luật kết hợp được đề cập ở ví dụ trên. Luật thứ nhất là: “30% khách
hàng mua mực in lẫn giấy A4 ”. Luật thứ hai là: “40% khách hàng khi mua mực
in thì cũng mua kẹ p giấy”. Các luậ t kết hợp này thường được sử dụng bởi các
cửa hàng bán lẻ để phân tích các giao dịch của cửa hàng. Đối với người quan lý
kinh doanh, các luậ t kết hợp được phát hiện có thể được dùng trong chiến dịch
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
13

quảng cáo, tiếp thị, quản lý hàng tồn kho và dự trữ hàng. Các luật kết hợp cũng
được sử dụng cho các ứng dụng khác như dự đoán lỗi, cho các mạng điện thoại
bằng việc xác định các sự kiện xuất hiện trước đó.


Hình 1.6: Một số lĩnh vực liên quan đến khai phá dữ liệu
Phát hiện tri thức và khai phá dữ liệu được coi là trung tâm của nhiều
ngành khoa học, nó liên quan đến rất nhiều ngành, nhiều lĩnh vực khác nhau
như tài chính, ngân hàng, thương mại, y tế, giáo dục, thống kê, máy móc, trí tuệ
nhân tạo, cơ sở dữ liệu, thuật toán học, tính toán song song, thu nhận tri thức
trong các hệ chuyên gia, quan sát dữ liệu.
Lĩnh vực học máy và nhận dạng mẫu là giống nhau trong khai phá dữ liệu
nghiên cứu các lý thuyết và thuật toán của hệ thống trích ra các mẫu và mô hình
dữ liệu. Khai phá dữ liệu tập trung vào việc mở rộng các lý thuyết và thuật toán
cho các vấn đề về tìm ra các mẫu đặc biệt, đây được coi là những mẫu hữu ích
hoặc tri thức quan trọng tập dữ liệu lớn.
Đặc biệt, phát hiện tri thức và khai phá dữ liệu rất gần gũi với lĩnh vực
thống kê, sử dụng các phương pháp thống kê để mô hình dữ liệu và phát hiện
các mẫu, luật…, kho dữ liệu và các công cụ xử lý trực tuyến (OLAP – online
analytical processing) tập trung vào phân tích dữ liệu đa chiều, tốt hơn SQL
trong tính toán và phân tích thống kê đa chiều cũng liên quan chặt chẽ đến khai
phá dữ liệu.
Đặc trưng của hệ thống khai phá dữ liệu là nhờ vào các phương pháp
thuật toán và kỹ thuật từ những lĩnh vực khác nhau, nhằm mục đích cuối cùng là
trích ra tri thức từ dữ liệu trong CSDL khổng lồ.
Khai phá dữ liệu
Cơ sở dữ liệu
Thương mại

lượng tới hàng gigabyte, terabyte; số các thuộc tính trong CSDL có thể rất nhiều
và đa dạng. Để giải quyết vấn đề này, người ta thường đưa ra một ngưỡng nào
đó cho CSDL bằng các cách như chiết xuất mẫu, xấp xỉ hoặc xử lý song song.
Trong CSDL khi mà số các thuộc tính là rất lớn , cùng với số lượng lớn
các bản ghi sẽ dẫn đến kích thước độ phức tạp của bài toán tăng lên. Vì vậy,
không gian tìm kiếm, không gian trạng thái gia tăng, n hiều mẫu hay mô hình
thừa, trùng lặp phát sinh nhiều luật thừa, đây được coi là vấn đề nan giải trong
quá trình khai phá dữ liệu. Nhằm giải quyết được những vấn đề trên , phải sử
dụng một số các tri thức đã biết trước để loại bỏ và trích lọc ra những dữ liệu
thích hợp với yêu cầu của bài toán.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
16

Vấn đề dữ liệu bị thay đổi phụ thuộc theo thời gian, có nghĩa là dữ liệu bị
ảnh hưởng và phụ thuộc vào thời điểm quan sát, lấy mẫu, thời điểm khai phá.
Kết quả đạt được sau khai phá cũng gây không ít khó khăn cho khai phá dữ liệu,
như các mẫu được khai phá ở bước trước, có thể không còn giá trị hay vô nghĩa
đối với thời điểm sử dụng, hoặc có thể làm nhiễu hay phát sinh hiệu ứng phụ
làm sai lệch kết quả. Để khắc phục được vấn đề này cần phải chuẩn hóa, cải
tiến, nâng cấp các mẫu, các mô hình và có thể xem các thay đổi này là mục đích
của khai phá và tìm kiếm các mẫu bị thay đổi.
Thuộc tính không phù hợp, các bộ giá trị không đầy đủ, bị thiếu giá trị
trong các miền thuộc tính đã làm ảnh hưởng rất lớn trong khai phá dữ liệu .
Trong quá trình khai phá dữ liệu, khi các hệ thống tương tác với nhau phụ thuộc
nhau mà thiếu vắng một vài giá trị nào đó , sẽ dẫn đến các mẫu không được
chính xác, bị thiếu, không đầy đủ. Để giải quyết cho vấn đề này, người ta coi sự
thiếu vắng của các dữ liệu này là giá trị ẩn, chưa biết và có thể được tiên đoán
bằng một số phương pháp nào đó.
Quan hệ phức tạp giữa các thuộc tính trong CSDL cũng là vấn đề cần
được quan tâm. Những bộ thuộc tính có cấu trúc, phân lớp phức tạp, có mối liên

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, tìm được hai luật kết hợp:
- 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".
- 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, …
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
18

Luật kết hợp cho biết phạm vi mà trong đó, sự xuất hiện của tập các thuộc
tính A nào đó trong các bản ghi của CSDL D sẽ kéo theo sự xuất hiện của tập
các thuộc tính khác B, cũng trong những bản ghi đó, có dạng A ⇒ B. Mỗi luật
kết hợp được đặc trưng bởi một cặp tỷ lệ đó, là độ hỗ trợ và độ tin cậy. Thông
tin mà luậ t kết hợp mang lại là rất to lớn và hỗ trợ đáng kể cho quá trình ra
quyết định trong kinh doanh cũng như trong nghiên cứu khoa học.
2.2 Luật kết hợp
2.2.1 Các khái niệm cơ bản [18, 22]
Đặt: I = {i
1
,…,i
n

tập không đáng quan tâm. Trong các trình bày sau này, ta sử dụng những cụm từ