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
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN
THÔNG
PHẠM ĐỨC QUANG KHAI PHÁ LUẬT KẾT HỢP CÓ TRỌNG SỐ
TRONG CƠ SỞ DỮ LIỆU LỚN LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH
Chuyên ngành: KHOA HỌC MÁY TÍNH
Mã số: 60.48.01
LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH
Hƣớng dẫn khoa học: PGS.TS. NGUYỄN THANH TÙNG THÁI NGUYÊN 2012 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên LỜI CÁM ƠN
Trước hết em xin gửi lời cám ơn chân thành đến toàn thể các thầy cô
giáo Viện Công nghệ thông tin - Viện Khoa học và Công nghệ Việt Nam và
Trường Đại học Công nghệ thông tin và Truyền thông - Đại học Thái nguyên
đã dạy dỗ chúng em trong suốt quá trình học tập chương trình cao học tại
trường.
Đặc biệt em xin bày tỏ lòng biết ơn sâu sắc tới PGS.TS. Nguyễn Thanh
Lời cảm ơn
Lời cam đoan
Mục lục i
Danh mục các từ, các ký hiệu viết tắt iv
Danh mục các bảng v
LỜI MỞ ĐẦU 1
Chƣơng 1. KHÁI QUÁT VỀ KHAI PHÁ DỮ LIỆU VÀ BÀI TOÁN KHAI
PHÁ TẬP MỤC THƢỜNG XUYÊN 3
1.1. Khai phá dữ liệu 3
1.2. Khai phá luật kết hợp 8
1.2.1. Cơ sở dữ liệu giao tác 8
1.2.2. Phát biểu bài toán khai phá luật kết hợp 10
1.2.3. Thuật toán Apriori khám phá tập mục thường xuyên 12
1.3. Mở rộng bài toán khai phá tập mục thường xuyên 18
1.4. Kết luận chương 19
Chƣơng 2. KHAI PHÁ LUẬT KẾT HỢP CÓ TRỌNG SỐ 20
2.1. Mở đầu 20
2.2. Khai phá luật kết hợp có trọng số không chuẩn hóa 21
2.2.1. Mô hình bài toán 21
2.2.2. Thuật toán MINWAL(O) khai phá tập mục thường xuyên có trọng
số 24
2.2.2.1. Cơ sở toán học 24
2.2.2.2. Thuật toán MINWAL(O) 27
2.3. Khai phá luật kết hợp có trọng số chuẩn hóa 34
2.3.1. Mô hình bài toán 34
2.3.2. Thuật toán MINWAL(W) khai phá tập mục thường xuyên có trọng
số chuẩn hóa 37
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
: Tập tất cả M mục dữ liệu của cơ sở dữ liệu giao tác.
, , ,
N
DT T T T
12
: Cơ sở dữ liệu DT gồm N giao tác
X, Y, : Các tập con của tập tất cả các mục trong cơ sở dữ liệu giao tác.
X = abc thay cho
,,X a b c
trong các ví dụ.
()SC X
: Số đếm hỗ trợ tập mục X (hay số giao tác chứa tập mục X).
sup(X) : Độ hỗ trợ của tập mục X.
Wsup(X) : Độ hỗ trợ có trọng số của tập mục X.
NWsup(X) : Độ hỗ trợ có trọng số chuẩn hóa của tập mục X.
minsup : Ngưỡng độ hỗ trợ tối thiểu.
wminsup : Ngưỡng độ hỗ trợ có trọng số tối thiểu.
nwminsup : Ngưỡng độ hỗ trợ có trọng số chuẩn hóa tối thiểu.
sup( )XY
: Độ hỗ trợ của luật kết hợp
XY
.
()conf X Y
: Độ tin cậy của luật kết hợp
XY
.
A
: Lực lượng (bản số) của tập hợp A.
LỜI MỞ ĐẦU
Khai phá luật kết hợp là một kỹ thuật quan trọng, có nhiều ứng dụng của
khai phá dữ liệu. Mô hình đầu tiên (mô hình nhị phân) của bài toán khai phá
luật kết hợp được đề xuất bởi Agrawal và cộng sự vào năm 1993, trong công
trình nghiên cứu phát hiện các mối quan hệ (luật kết hợp) giữa các mặt hàng
(mục dữ liệu - items) trong cơ sở dữ liệu giao tác của các siêu thị [4, 5]. Sau
công trình kinh điển này, vấn đề khai phá luật kết hợp trong cơ sở dữ liệu
(CSDL) giao tác được rất nhiều nhà nghiên cứu lý thuyết và ứng dụng quan
tâm. Nhiều thuật toán mới, hiệu quả khai phá luật kết hợp, cũng như mô hình
mở rộng bài toán đã được các nhà nghiên cứu đề xuất [8, 9].
Mô hình nhị phân của bài toán khai phá luật kết hợp có một số hạn chế,
không đáp ứng được những đòi hỏi khác nhau của người sử dụng. Một trong
những hạn chế là trong mô hình này tất cả các mục dữ liệu được xử lý như
nhau (xuất hiện hay không xuất hiện trong một giao tác), nhưng trên thực tế
chúng có tầm quan trọng khác nhau. Nhằm khắc phục hạn chế này người ta đã
đề xuất mô hình bài toán khai phá luật kết hợp có trọng số, trong đó các mục
dữ liệu được gán cho các trọng số khác nhau tùy theo mức độ quan trọng của
chúng trong việc mang lại lợi nhuận kinh doanh [3, 7, 8, 18].
Những năm gần đây, khai phá luật kết hợp có trọng số đã trở thành một
đề tài hấp dẫn, một nội dung quan trọng của khai phá dữ liệu, thu hút sự quan
tâm của nhiều nhà nghiên cứu và ứng dụng.
Đề tài luận văn của học viên nhằm nghiên cứu bài toán, các thuật toán và
tìm hiểu khả năng ứng dụng kỹ thuật khai phá luật kết hợp có trọng số từ các
CSDL lớn.
Nội dung chính của luận văn gồm 3 chương:
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
Chương 1 trình bày khái quát về khai phá dữ liệu, tóm tắt quá trình khai
phá, các kỹ thuật, các ứng dụng và những thách thức; bài toán khai phá luật
Khai phá dữ liệu là một lĩnh vực khoa học mới xuất hiện, nhằm tự động
hóa khai thác những thông tin, tri thức hữu ích, tiềm ẩn trong các cơ sở dữ
liệu (CSDL) lớn cho các tổ chức, doanh nghiệp, từ đó thúc đẩy khả năng
sản xuất, kinh doanh, cạnh tranh của tổ chức, doanh nghiệp này. Các kết quả
nghiên cứu cùng với những ứng dụng thành công trong khám phá tri thức cho
thấy khai phá dữ liệu là một lĩnh vực khoa học tiềm năng, mang lại nhiều lợi
ích, đồng thời có những ưu thế hơn hẳn so với các công cụ phân tích dữ liệu
truyền thống.
Tuy mới ra đời khoảng 20 năm, nhưng khai phá dữ liệu là lĩnh vực khoa
học phát triển vô cùng nhanh chóng. Do sự phát triển nhanh chóng cả về
phạm vi áp dụng lẫn các phương pháp tìm kiếm tri thức, đã có nhiều quan
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
điểm khác nhau về khai phá dữ liệu. Tuy nhiên, ở một mức độ trừu tượng
nhất định, chúng ta định nghĩa khai phá dữ liệu như sau [9]:
Khai phá dữ liệu là quá trình tìm kiếm, phát hiện các tri thức mới, hữu
ích tiềm ẩn trong cơ sở dữ liệu lớn.
Khám phá tri thức trong CSDL (Knowledge Discovery in Databases –
KDD) là mục tiêu chính của khai phá dữ liệu, do vậy hai khái niệm khai phá
dữ liệu và KDD được các nhà khoa học xem là tương đương nhau. Thế
nhưng, nếu phân chia một cách chi tiết thì khai phá dữ liệu là một bước chính
trong quá trình KDD.
Khám phá tri thức trong CSDL là lĩnh vực liên quan đến nhiều ngành
như: Lý thuyết CSDL, xác suất, thống kê, lý thuyết thông tin, học máy, thuật
toán, trí tuệ nhân tạo, tính toán song song và hiệu năng cao, Các kỹ thuật
chính áp dụng trong khám phá tri thức phần lớn được thừa kế từ các ngành
này.
Quá trình khám phá tri thức có thể phân thành các công đoạn sau [9]:
Lựa chọn dữ liệu: Là bước tuyển chọn những tập dữ liệu cần được
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
tự nhau dựa trên một tập dữ liệu không có giám sát (unsupervised
data set), tức là tập các ví dụ huấn luyện chỉ chứa thông tin về các
thuộc tính mà không có thông tin về nhãn lớp của các đối tượng.
Học nửa giám sát (Semi-Supervised Learning): Là quá trình học luật
phân chia một tập các đối tượng thành các lớp dựa trên một tập nhỏ
các ví dụ huấn luyện chứa thông tin về các thuộc tính và nhãn lớp
của một số đối tượng.
Nếu căn cứ vào nhiệm vụ cần giải quyết, thì khai phá dữ liệu bao gồm
các kỹ thuật sau:
Phân lớp và dự đoán (classification and prediction): Là việc xếp các
đối tượng vào những lớp đã biết trước. Ví dụ, phân lớp các loài thực
vật, phân lớp các bệnh nhân, Hướng tiếp cận này thường sử dụng
một số kỹ thuật của học máy như cây quyết định (decision tree),
mạng nơ-ron nhân tạo (neural network),
Phân cụm (clustering/segmentation): Là việc xếp các đối tượng
theo từng cụm tự nhiên.
Luật kết hợp (association rules): Là việc phát hiện các luật biểu
diễn tri thức dưới dạng đơn giản. Ví dụ: “70% nữ giới vào siêu thị
mua phấn thì có tới 80% trong số họ cũng mua thêm son”.
Phân tích hồi quy (regression analysis): Là việc học một hàm ánh
xạ một bộ dữ liệu thành một giá trị thực của đại lượng cần dự đoán.
Bài toán phân tích hồi quy tương tự như bài toán phân lớp, điểm
khác nhau là ở chỗ đại lượng cần dự đoán là liên tục chứ không phải
rời rạc như nhãn lớp.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
Phân tích các mẫu theo thời gian (sequential/temporal patterns):
không còn phù hợp.
- Dữ liệu bị thiếu hoặc nhiễu.
- Quan hệ phức tạp giữa các thuộc tính.
- Giao tiếp với người sử dụng và kết hợp với các tri thức đã có.
- Tích hợp với các hệ thống khác.
1.2. Khai phá luật kết hợp
Khai phá luật kết hợp đóng vai trò quan trọng trong khai phá dữ liệu.
Khai phá luật kết hợp là phát hiện những mối quan hệ giữa các mục dữ liệu.
Mô hình bài toán khai phá luật kết hợp đầu tiên được giới thiệu bởi Agrawal
và cộng sự vào năm 1993 khi phân tích cơ sở dữ liệu bán hàng của siêu thị [4,
5]. Đến nay, bài toán trong mô hình đầu tiên này được gọi là bài toán khai
phá luật kết hợp nhị phân (hay bài toán khai phá luật kết hợp cơ bản), vì ở
đây chỉ quan tâm đến sự xuất hiện hay không xuất hiện của các tập mục trong
các giao tác.
Trước khi phát biểu bài toán khai phá luật kết hợp, ta định nghĩa CSDL
giao tác và các dạng biểu diễn.
1.2.1. Cơ sở dữ liệu giao tác
Định nghĩa 1.1. Cho tập các mục (item)
12
, , ,
M
I i i i
. Một giao tác
(transaction) T là một tập con của I,
TI
. Cơ sở dữ liệu giao tác là tập các
giao tác DB ={ T
1
, T
B,C,D
T
3
A, B, D
T
4
A, C, D
T
5
C, D
Bảng 1.2: Biểu diễn dọc của cơ sở dữ liệu giao tác
Mục dữ liệu
Định danh giao tác
A
T
1
, T
6
, T
7
, T
8
, T
9
, T
10
B
T
1
, T
4
, T
5
Ma trận giao tác: Cơ sở dữ liệu giao tác
12
, , ,
N
DB T T T
trên tập
các mục
12
, , ,
M
I i i i
được biểu diễn bởi ma trận nhị phân
()
pq N M
Mm
ở đó:
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên khi
khi
T
2
0
1
1
1
T
3
1
1
0
1
T
4
1
0
1
1
T
5
0
0
1
1
1.2.2. Phát biểu bài toán khai phá luật kết hợp
Dưới đây, để cho tiện, luật kết hợp nhị phân sẽ được gọi vắn tắt là luật
kết hợp.
Định nghĩa 1.2. Cho CSDL giao tác DT với tập tất cả các mục I. Một luật kết
hợp là một biểu thức dạng
Định nghĩa 1.4. Cho tập mục
XI
và ngưỡng hỗ trợ tối thiểu (minimum
support)
0,1minsup
. X được gọi là tập mục thường xuyên (frequent
itemset) với độ hỗ trợ tối thiểu minsup nếu
sup( )X minsup
, ngược lại X gọi
là tập mục không thường xuyên.
Ngưỡng hỗ trợ tối thiểu minsup là giá trị cho trước bởi người sử dụng.
Định nghĩa 1.5. Độ hỗ trợ của một luật kết hợp
XY
, ký hiệu là
sup(
XY
), 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 xuất hiện
đồng thời của X và Y trong một giao tác, tức là
()P X Y
.
Ta có:
luật kết hợp được phát biểu như sau.
Cho cơ sở dữ liệu giao tác DT, ngưỡng độ hỗ trợ tối thiểu minsup và
ngưỡng độ tin cậy tối thiểu minconf. Hãy tìm tất cả các luật kết hợp
XY
trong DT thỏa mãn đồng thời hai điều kiện:
sup( )X Y minsup
,
conf X Y minconf
.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
Bài toán khai phá luật kết hợp được chia thành hai bài toán con. Bài toán
thứ nhất là tìm tất cả các tập mục thoả mãn độ hỗ trợ tối thiểu, tức là tìm tất cả
các tập mục thường xuyên. Bài toán thứ hai là sinh ra các luật kết hợp từ các
tập mục thường xuyên đã tìm được thoả mãn độ tin cậy tối thiểu.
Bài toán thứ hai được giải quyết như sau: Giả sử đã tìm được X là tập
mục thường xuyên, ta sinh ra các luật kết hợp bằng cách với
YX
, kiểm
tra độ tin cậy của luật
\X Y Y
có thoả mãn độ tin cậy tối thiểu không.
Việc giải quyết bài toán thứ hai như trên là khá đơ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 phát hiện các tập mục thường xuyên.
1.2.3 Thuật toán Apriori khám phá tập mục thƣờng xuyên
Apriori là thuật toán đầu tiên dành cho việc khai phá tập mục thường
xuyên do Agrawal và cộng sự đề xuất. Apriori thuộc nhóm thuật toán sinh
ứng viên. Tuy có một số nhược điểm nhưng cho tới nay nó vẫn là thuật toán
cơ bản nhất. Ý tưởng của thuật toán Apriori là nền tảng cho việc phát triển
nhiều thuật toán khai pháp tập mục thường xuyên sau công trình của Agrawal
và cộng sự.
Một cách cụ thể, thuật toán Apriori được mô tả như sau [4, 5].
Ký hiệu:
Ký hiệu
Ý nghĩa
L
k
Tập các k-tập mục thường xuyên (với độ hỗ trợ tối thiểu
minsup). Mỗi phần tử của tập này có 2 trường:
i) Tập mục (itemset)
ii) Số đếm hỗ trợ (support count)
C
k
Tập các k-tập mục ứng viên (các tập mục thường xuyên
tiềm năng). Mỗi phần tử của tập này có 2 trường:
i) Tập mục (itemset)
ii) Số đếm hỗ trợ (count) Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
Cơ sở của thuật toán Apriori là tính chất Apriori của tập mục thường
xuyên: 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
được nối nếu chúng có
(k-2) mục dữ liệu đầu bằng nhau, mục dữ liệu thứ (k-1) của l
1
“nhỏ hơn” mục
dữ liệu thứ (k-1) của l
2
(theo thứ tự từ điển):
l l l l l k l k l k l k
1 2 1 2 1 2 1 2
1 1 2 2 2 2 1 1
Tập mục nhận được sau kết nối l
1
với l
2
là: l
1
[1] l
1
[2]… l
1
[k-2] l
(1) Tìm các 1- tập mục thường xuyên, nhận được L
1
;
(2) For
;card( ) ;
k
k L k
1
22
do begin
(3) C
k
= apriori_gen(L
k-1
,minsup); // Sinh tập ứng viên mới từ
k1
L
;
(4) For (each
T DB
) do begin
(5) C = subset(C
k
,T); // Các tập mục ứng viên chứa trong T ;
(6) For (each
cC
L
k-1
) do
(2) For (each (k-1)-tập mục l
2
L
k-1
do
(3) if (l
1
[1] = l
2
[1]) and (l
1
[2] = l
2
[2]) and … and (l
1
[k-2] = l
2
[k-2])
and (l
1
[k-2] = l
2
[k-2]) and (l
L
k-1
) then
(7) delete c
i
from C
k
;
(8) Return C
k
;
Ví dụ minh hoạ thuật toán Apriori
Ta minh hoạ thực hiện thuật toán Apriori trên cơ sở dữ liệu cho trong
bảng 1.4 với minsup = 0.05, tức số đếm hỗ trợ tối thiểu bằng 2. Bảng 1.4: Cơ sở dữ liệu giao tác minh hoạ thực hiện thuật toán Apriori.
TID
Các mục dữ liệu
T
1
A, C, D
T
2
B, C, E
T
3
A, B, C, E
T
2
được C
3
:
Copyright: Tài liệu đại học ©