Khai phá dữ liệu phát hiện luật kết hợp và Ứng dụng đối với kho dữ liệu của ngân hàng
1
ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
NGUYỄN THỊ THU TRANG
KHAI PHÁ DỮ LIỆU PHÁT HIỆN LUẬT KẾT HỢP
VÀ ỨNG DỤNG ĐỐI VỚI KHO DỮ LIỆU CỦA NGÂN HÀNG
LUẬN VĂN THẠC SĨ
Mã số: 60 48 10
LUẬN VĂN THẠC SĨ NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS. TS. VŨ ĐỨC THI Hà Nội - 2008 Khai phá dữ liệu phát hiện luật kết hợp và Ứng dụng đối với kho dữ liệu của ngân hàng
1
MỤC LỤC
MỞ ĐẦU 7
Chương 1: KHO DỮ LIỆU VÀ PHÂN TÍCH DỮ LIỆU TRỰC TUYẾN 8
1.1. Hệ thống xử lý giao dịch trực tuyến (OLTP) 8
1.2. Kho dữ liệu (Data warehouse) 8
1.3. Hệ thống phân tích dữ liệu trực tuyến (OLAP) 10
1.3.1. Giới thiệu 10
1.3.2. Mô hình tổ chức dữ liệu (Data model) 13
1.3.2.1. Lược đồ hình sao (Star schema) 14
1.3.2.2. Lược đồ bông tuyết (Snowflake schema) 15
Chương 2: KHAI PHÁ DỮ LIỆU PHÁT HIỆN LUẬT KẾT HỢP 17
2.1. Giới thiệu 17
3.3. Đánh giá 53
KẾT LUẬN 55
TÀI LIỆU THAM KHẢO 57
Danh sách tài liệu tham khảo tiếng Việt 57
Danh sách tài liệu tham khảo tiếng Anh 57
Danh sách Websites tham khảo 58
Khai phá dữ liệu phát hiện luật kết hợp và Ứng dụng đối với kho dữ liệu của ngân hàng
3
DANH SÁCH CÁC BẢNG TRONG LUẬN VĂN
Bảng 2.1: Ví dụ một CSDL giao dịch. 18
Bảng 2.2: Ví dụ về các tập mục phổ biến. 19
Bảng 2.3: Các luật kết hợp được sinh từ tập mục phổ biến ACW 20
Bảng 2.4: Ví dụ CSDL giao dịch bán hàng. 23
Bảng 2.5: Thuật toán Apriori. 29
Bảng 2.6: Cơ sở dữ liệu minh hoạ thuật toán Apriori. 30
Bảng 2.7: Minh hoạ CSDL thống kê tài khoản giao dịch. 33
Bảng 2.8: Tiêu chí rời rạc hoá CSDL thống kê TKGD 34
Bảng 2.9: CSDL thống kê TKGD sau khi rời rạc hoá. 34
Bảng 2.10: Pivot-table ứng với CSDL thống kê TKGD. 35
Bảng 2.11: Thuật toán tìm tập mục phổ biến từ Data-cube của Hua Zhu 36
Bảng 2.12: Thuật toán DataCubeSimpleGenFrequentItemsets. 38
Bảng 2.13: Thuật toán sinh luật kết hợp từ tập mục phổ biến. 40
Bảng 2.14: Thủ tục GenRules. 40
Bảng 2.15: Thuật toán DataCubeSimpleMining 41
Bảng 3.1: Đoạn mã thực hiện chuẩn hoá dữ liệu. 46
Khai phá dữ liệu phát hiện luật kết hợp và Ứng dụng đối với kho dữ liệu của ngân hàng
5
KÝ HIỆU VÀ TỪ VIẾT TẮT
Stt
Ký hiệu viết tắt
Nghĩa tiếng Việt
Nghĩa tiếng Anh
1
CSDL
Cơ sở dữ liệu
Database
2
HQTCSDL
Hệ quản trị cơ sở dữ liệu
Database Management System
3
KPDL
Khai phá dữ liệu
Data Mining
4
KDD
Khai phá tri thức
Knowledge Discovery in Database
Decision-making support
system
Hệ hỗ trợ quyết định
8
Dimension table
Bảng chiều dữ liệu
9
Fact table
Bảng giá trị chi tiết
10
Frequent items set
Tập mục phổ biến
11
KDD
Knowledge Discovery in Database
Khai phá tri thức
12
OLAP
On-Line Analytical Processing
Hệ thống Phân tích dữ liệu trực tuyến
13
OLTP
On-Line Transaction Processing
Hệ thống xử lý giao dịch trực tuyến
14
Star schema
Lược đồ hình sao
15
Snowflake schema
Lược đồ bông tuyết
̀
ca
́
c tô
̉
chư
́
c ,
doanh nghiê
̣
p tìm hi ểu, nghiên cứu, thử nghiệm, phát triển và kết quả đã thu đư ợc những
thành công lớn đặc biệt trong lĩnh vực Ngân hàng và Tài chính trên những Kho dữ liệu
khổng lồ. Tuy nhiên ở nước ta, các nhà quản trị thậm chí còn chưa biết làm sao tổ chức dữ
liệu của mình thành một Kho dữ liệu, họ mới chỉ dừng lại ở việc trích rút được những báo
cáo đơn giản đáp ứng các nghiệp vụ hàng ngày, chưa có khái niệm về Kho dữ liệu, về
phân tích OLAP, chứ chưa nói đến là Khai phá dữ liệu từ Kho dữ liệu đó. Chính vì vậy đề
tài tập trung vào vấn đề rất thực tiễn này: Khai phá dữ liệu phát hiện luật kết hợp và
Ứng dụng đối với Kho dữ liệu của ngân hàng.
Luận văn được tổ chức thành 3 chương:
Chương 1: Kho dữ liệu và Phân tích dữ liệu trực tuyến
Trình bày những nét khái quát nhất về Kho dữ liệu (Data warehouse) và Phân tích
dữ liệu trực tuyến (OLAP).
Chương 2: Khai phá dữ liệu phát hiện luật kết hợp
Trình bày các vấn đề chung, cơ bản nhất về Luật kết hợp, giải thuật kinh điển
Apriori và Khai phá luật kết hợp dựa trên OLAP.
Chương 3: Xây dựng ứng dụng minh hoạ
Triển khai ứng dụng minh hoạ đối với Kho dữ liệu Ngân hàng.
Data warehouse (Kho dữ liệu) được đề xuất bởi W.H.Inmon vào đầu những năm 1990,
là nơi lưu trữ thông tin tích hợp từ nhiều nguồn (Multi-sources), hướng chủ đề (Subject-
oriented), mang tính lịch sử (Time-variant), ổn định (Nonvolatile), hỗ trợ truy vấn
(Query), phân tích (Analyse) thông tin và trợ giúp ra quyết định (Decision-making
support) [105].
Qua khái niệm trên ta thấy dữ liệu và thông tin sẽ được trích rút từ nhiều nguồn khác
nhau với các định dạng khác nhau. Nếu người sử dụng muốn thực hiện các truy vấn, hệ
thống sẽ chỉ thực hiện tìm kiếm dữ liệu tại Data warehouse một cách thống nhất thay vì Khai phá dữ liệu phát hiện luật kết hợp và Ứng dụng đối với kho dữ liệu của ngân hàng
9
tìm kiếm trên các CSDL (Cơ sở dữ liệu) nguồn bằng các công cụ chuyên biệt tương ứng,
từ đó tiết kiệm nhiều thời gian xử lý của người sử dụng.
Hình 1.1: Kiến trúc tiêu biểu của Data warehouse.
Hệ thống Data warehouse gồm có 3 thành phần chính sau:
1. Các CSDL nguồn: Dữ liệu thô sẽ được tập hợp từ nhiều nơi: bên trong, bên ngoài, tự
có, đi mua, dữ liệu di sản lịch sử hay dữ liệu hoạt động hiện tại (Operational
database), các dữ liệu này và mọi sự thay đổi của chúng sẽ được quản lý bởi một
phân hệ giám sát đặc biệt (Monitor / Wrapper modules).
Ở đây, dữ liệu được tập hợp từ rất nhiều nguồn: bản thân doanh nghiệp, bên ngoài doanh
nghiệp, thậm chí là đi mua, được lưu trữ trên rất nhiều loại khuôn dạng: Oracle, DB2,
SQL Server, Microsoft Access, , thậm chí là Microsoft Excel file hay Text file. Tất cả
dữ liệu này và mọi sự thay đổi của chúng sẽ được quản lý bởi phân hệ Monitor / Wrapper.
2. Lõi của Data warehouse: Tại đây, dữ liệu sẽ được tổng hợp từ các nguồn dữ liệu trên,
chuyển đổi về khuôn dạng chuẩn, xong việc truy vấn và đặc biệt là việc phân tích thông
tin trên một khối lượng dữ liệu khổng lồ đòi hỏi phải có những công cụ đặc biệt.
Kỹ thuật OLAP (OnLine Analytical Processing: Xử lý phân tích dữ liệu trực tuyến)
được hiểu là một tập hợp những những kỹ thuật được phát triển để phân tích dữ liệu trong
Data warehouse [102] đáp ứng được các tiêu chí: Trực tuyến (Online), nhanh chóng, trực
quan và hiệu quả đối với phân tích dữ liệu đa chiều. OLAP thực hiện một quá trình tạo ra
và quản lý dữ liệu đa chiều phục vụ cho phân tích một cách trực quan, nó cho phép truy
vấn trên một CSDL khổng lồ một cách nhanh chóng và hiệu quả đáng kể so với kỹ thuật
truy vấn kinh điển bằng SQL trên CSDL quan hệ. Để thực hiện được điều đó, OLAP-
engine (cơ chế OLAP) phải thực hiện tính toán trước các toán tử nhóm (Aggregation
operator) đồng thời tổ chức lại dữ liệu và kết quả tính toán dưới dạng các Khối dữ liệu đa
chiều (Data-cube). Khai phá dữ liệu phát hiện luật kết hợp và Ứng dụng đối với kho dữ liệu của ngân hàng
11
Việc thực hiện OLAP bao gồm 3 giai đoạn:
- Truy vấn dữ liệu từ Data warehouse.
- Xây dựng Data-cube.
- Phân tích trực tuyến dựa trên Data-cube.
Khái niệm Data-cube (Khối dữ liệu đa chiều) lần đầu tiên được đề xuất bởi J. Gray và các
cộng sự [101], nó bao gồm các chiều dữ liệu và các thước đo, cho phép người sử dụng
nhìn vào dữ liệu được lưu trữ trong Data warehouse qua nhiều góc độ và nhiều chiều dữ
liệu. Ví dụ, chúng ta cùng xem xét một Data-cube có 3 chiều dữ liệu Product, Supplier,
Customer và 1 thước đo là SalesTotal qua hình sau: Hình 1.2: Minh hoạ Data-cube.
c1
c2
c3
*
p1
56
4
50
110
p2
11
8
1
20
*
67
12
51
130 c1
c2
c3
*
p1
44
4
48
81
s1
s2
*
Sales(*,*,*)
Sales(p1,*,s2) Khai phá dữ liệu phát hiện luật kết hợp và Ứng dụng đối với kho dữ liệu của ngân hàng
13 Hình 1.4: Các thao tác cơ bản trong OLAP.
1.3.2. Mô hình tổ chức dữ liệu (Data model)
Hầu hết các hệ quản trị CSDL hiện nay là CSDL quan hệ và ở các dạng chuẩn hoá
nhất định (3NF hoặc cao hơn), tuy nhiên nếu sử dụng trực tiếp CSDL quan hệ để phân
tích trực tuyến sẽ gặp rất nhiều khó khăn, đặc biệt là về tốc độ. Để có thể phân tích trực
tuyến, dữ liệu cần thiết phải được tính toán trước (chấp nhận dư thừa) và tổ chức lại dưới
dạng đặc biệt. Hầu hết Data warehouse hiện nay đều lưu trữ dữ liệu theo mô hình dữ liệu
đa chiều (Multidimensional data model) dạng lược đồ hình sao (Star schema) hoặc dạng
lược đồ bông tuyết (Snowflake schema).
Khai phá dữ liệu phát hiện luật kết hợp và Ứng dụng đối với kho dữ liệu của ngân hàng
14
1.3.2.1. Lược đồ hình sao (Star schema)
Mô hình Star schema (Lược đồ hình sao) được đề xuất bởi R. Kimball [108], là mô
Hình 1.7: Lược đồ bông tuyết (Snowflake schema).
Điểm khác nhau giúp phân biệt Snowflake schema và Star schema đó là: tại mô hình Star
schema mọi Dimension table đều ở dạng trực tiếp quan hệ với Fact table, còn trong mô
hình Snowflake schema sẽ tồn tại một số Dimension table không quan hệ trực tiếp với
Fact table mà quan hệ với nhau ở dạng chuẩn hoá (Normalized form) nhằm giảm dư thừa
dữ liệu. Ưu điểm của mô hình Snowflake schema là dữ liệu tại các Dimension table chuẩn
hoá không bị dư thừa do đó việc duy trì (maintain) và lưu trữ dữ liệu dễ dàng hơn. Tuy
nhiên mô hình Star schema chấp nhận phi chuẩn, chấp nhận dư thừa, thực hiện tích hợp
luôn quan hệ phân cấp chỉ trong 1 bảng nên sẽ không phải thực hiện các toán tử Join trong
SQL để kết hợp các bảng liên quan khi duyệt chiều dữ liệu tương ứng, vì vậy trong thực tế
mô hình Star schema được sử dụng phổ biến hơn so với mô hình Snowflake schema. Khai phá dữ liệu phát hiện luật kết hợp và Ứng dụng đối với kho dữ liệu của ngân hàng
17
Chương 2: KHAI PHÁ DỮ LIỆU PHÁT HIỆN LUẬT KẾT HỢP
2.1. Giới thiệu
KPDL (Data Mining) là quá trình tìm kiếm, phát hiện các tri thức tiềm ẩn và hữu dụng
trong CDSL nhất định. Trong đó tri thức được ngầm hiểu là các thông tin mang tính chất
quy luật và hữu ích đối với người sử dụng. Các hướng tiếp cận trong KPDL có thể được
phân chia theo chức năng hay lớp các bài toán khác nhau, dưới đây là một số hướng tiếp
cận chính:
+ Phân lớp và Dự đoán (Classification and Prediction): xếp một đối tượng vào một
trong những lớp đã biết trước. Ví dụ: phân lớp các bệnh nhân theo dữ liệu trong hồ sơ
và hoa để tặng bạn gái anh ta. Người bán hàng chắc đến 90% rằng nếu khách hàng là
nam giới mua quà lưu niệm mua cả hoa thì người được tặng là bạn gái anh ta.”
Ở đây vế trái (tiền đề - antecedent) của luật là “mua bia”, “nam giới, mua quà lưu
niệm và hoa”, còn “mua lạc” và “tặng bạn gái” là vế phải (mệnh đề kết luận -
consequent) của luật.
Các số 10%, 12% được gọi là độ hỗ trợ của luật (Support – số phần trăm các giao dịch
chứa cả về phải và vế trái của luật).
Các số 70%, 90% được gọi là độ tin cậy của luật (Confidence – số phần trăm giao dịch
thoả mãn vế trái thì cũng thoả mãn vế phải).
Chúng ta thấy rằng tri thức đem lại bởi những luật kết hợp ở dạng trên có sự khác biệt cơ
bản so với thông tin thu được từ các câu lệnh truy vấn dữ liệu thông thường. Đó thường là
những tri thức, những mối liên hệ chưa được biết trước và mang tính dự báo đang tiềm ẩn
trong dữ liệu. Những tri thức này không chỉ đơn giản là kết quả của các phép nhóm, tính
tổng hay sắp xếp mà là kết quả của quá trình tính toán phức tạp và tốn nhiều thời gian.
2.1.1.2. Các định nghĩa cơ bản
Cho tập các mục I = {i
1
, i
2
, …, i
n
} và tập các giao dịch T = {t
1
, t
2
, …, t
m
}. Trong đó
+ i
C
D
W
3
A
C
T
W
4
A
C
D
W
5
A
C
D
T
W
6
C
D
T
Bảng 2.2: Ví dụ về các tập mục phổ biến.
Các tập mục phổ biến
Tần suất
Độ hỗ trợ
C
6
100%
W, CW
5
83%
A, D, T, AC, AW, CD, CT, ACW
4
67%
AT, DW, TW, ACT, ATW, CDW, CTW, ACTW
3
50%
+ Luật kết hợp (Association Rule): Luật kết hợp có dạng: r: X => Y (s, c), với X, Y là
các tập mục thoả mãn điều kiện X
Y = Ø, X là tiền đề, Y là kết quả của luật, s là độ hỗ trợ
(Support), c là độ tin cậy (Confidence) của luật trong đó:
+ s(r) = s(X => Y) = s(X
Y).
+ c(r) = c(X => Y) = s(X
Y) / s(X).
minconf.
Hầu hết các thuật toán được đề xuất để khai phá luật kết hợp thường chia bài toán
thành 2 pha:
+ Pha 1: Tìm tất cả các tập mục phổ biến từ CSDL tức là tìm tất cả các tập mục X thoả
mãn s(X)
minsup. Đây là pha tốn khá nhiều thời gian của CPU và thời gian vào ra ổ đĩa.
+ Pha 2: Sinh các luật tin cậy từ các tập phổ biến đã tìm thấy ở pha 1. Pha này tương
đối đơn giản và tốn ít thời gian hơn so với pha trên. Nếu X là một tập mục phổ biến thì
luật kết hợp được sinh từ X có dạng r: X\Y => Y, với Y
X, Y
Ø và c(r)
minconf.
Ví dụ: Xét tập mục ACW trong Error! Reference source not found. có độ hỗ trợ s =
67% và với minconf = 70% thì ta có thể sinh các luật kết hợp sau đây:
Bảng 2.3: Các luật kết hợp được sinh từ tập mục phổ biến ACW.
Luật kết hợp
Thoả mãn minconf
70%
A
%100
CW
Cụ thể: Nếu X
Y và sup(X) < minsup thì sup(Y) < minsup.
+ Tính chất 3: Mọi tập con của một tập phổ biến cũng là tập phổ biến.
Cụ thể: Nếu X
Y và sup(Y) > minsup thì sup(X) > minsup.
2. Một số tính chất của luật kết hợp
+ Tính chất 1: Không hợp các luật kết hợp.
Giả sử có hai luật kết hợp mạnh X => Z và Y => Z thì X
Y => Z chưa chắc đã là
luật kết hợp mạnh. Tương tự nếu có X => Y và X => Z thì X => Y
Z chưa chắc mạnh.
Thật vậy xét: I = {x, y, z}, T = {xz, yz, xy, xyz}, minsup = 50%, minconf = 60%.
Dễ thấy x => z (50%, 67%), y => z (50%, 67%), x => y (50%, 67%) là mạnh.
Còn xy => z (25%, 50%) và x => yz (25%, 33%) không mạnh. Khai phá dữ liệu phát hiện luật kết hợp và Ứng dụng đối với kho dữ liệu của ngân hàng
21
+ Tính chất 2: Không tách luật kết hợp.
Giả sử có luật kết hợp mạnh X
Y => Z thì X => Z và Y => Z chưa chắc đã là luật
kết hợp mạnh.
Thật vậy xét: I = {x, y, z, t}, T = {xt, yt, xyz}, minsup = 30%, minconf = 60%.
minconf
mà hiển nhiên sup(X
Y)
sup(X
Y
Z) nên (*) đã được chứng minh.
Tương tự X => Z cũng là luật kết hợp mạnh.
+ Tính chất 3: Các luật kết hợp không có tính chất bắc cầu.
Giả sử có các luật kết hợp mạnh X => Y và Y => Z thì X => Z chưa chắc đã là luật kết
hợp mạnh.
Thật vậy xét: I = {x, y, z}, T = {xy, yz}, minsup = 30%, minconf = 60%.
Dễ thấy x => y (50%, 100%) và y => z (50%, 100%) đều mạnh.
Còn x => z (0%, 0%) không mạnh.
+ Tính chất 4: Nếu luật A => (L \ A) không thoả mãn độ tin cậy cực tiểu (minconf) thì
luật B => (L \ B) cũng không thoả mãn, trong đó B
A
L, B
Ø.
Thật vậy conf(B => (L \ B)) = sup(L) / sup(B)
2.1.3. Luật kết hợp định lượng
// Quantitative assosiation rule.
Đối với loại này, ta không chỉ quan tâm tới sự có mặt hay không của các mục trong
giao dịch mà còn quan tâm tới định lượng của từng mục trong luật.
Ví dụ: “Mua bia 2-5 chai => Mua lạc 5-10 gói”,
“Tuổi 20-30, Mua quà $5-$10, Mua hoa $3-$8 => Tặng bạn gái thân”,
Để phát hiện ra luật kết hợp định lượng ta phải thực hiện các bước sau:
+ Tiền xử lý: Thực hiện rời rạc hoá chuyển đổi các thuộc tính số và thuộc tính phân
loại thành các thuộc tính nhị phân để có thể sử dụng được các thuật toán khai phá luật kết
hợp nhị phân. Điểm quan trọng của bước này là phải xác định các khoảng thuộc tính số
sao cho phù hợp, bởi việc làm này ảnh hưởng tới quá trình khai phá dữ liệu. Có nhiều
công trình nghiên cứu và nhiều thuật toán để chia khoảng các thuộc tính số sao cho phù
hợp [004].
+ Khai phá: Thực hiện khai phá trên CSDL nhị phân.
+ Hậu xử lý: Chuyển các luật nhị phân sang các luật định lượng tương ứng với các
khoảng rời rạc hoá.
2.1.4. Luật kết hợp đơn chiều
// Single-dimension assiociation rule.
Đối với loại này, các luật chỉ tham chiếu đến 1 chiều hay 1 thuộc tính của dữ liệu.
Vì vậy nó còn có một tên khác là Intra-dimension association rule.
Ví dụ: “Mua bia => Mua lạc”, “Mua quà, Mua hoa => Mua thiếp”,
Ở đây chỉ đề cập tới 1 chiều đó là Mua và ta có thể viết lại luật dưới dạng sau:
Mua(X, “bia”) => Mua(X, “lạc”),
Mua(X, “quà”) ^ Mua(X, “hoa”) => Mua(X, “thiếp”),
Trong đó X là biến biểu diễn khách hàng.
2.1.5. Luật kết hợp đa chiều
// Multi-dimension assiociation rule.
Đối với loại này, các luật có thể tham chiếu đến nhiều hơn 1 chiều của dữ liệu.
1
Máy tính để bàn IBM, Máy in HP màu.
2
Phần mềm bảng tính Excel, Hệ quản trị CSDL MySQL.
3
Chuột Mitsumi, Bàn phím Mitsumi.
4
Máy tính để bàn HP, Hệ quản trị CSDL MySQL.
5
Máy tính để bàn Fujitsu, Máy tính xách tay Toshiba.
Bảng trên cho biết các giao dịch của một cửa hàng bán máy tính: định danh giao dịch
TID và các mục bán được tương ứng. Khái niệm phân cấp cho các mục chỉ ra trong hình
sau (Theo chiều mũi tên, khi độ sâu tăng mức trừu tượng giảm dần):
Copyright: Tài liệu đại học ©