0
ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
LUẬN VĂN THẠC SỸ
PHÁT HIỆN LUẬT KẾT HỢP NHIỀU CHIỀU
MỜ TỪ CƠ SỞ DỮ LIỆU ĐỊNH LƯỢNG
Học viên: Nguyễn Thị Thanh Huyền
Người hướng dẫn khoa học: Ts. Đỗ Văn Thành 4/2006
1
MỤC LỤC
Chương 3 PHÁT HIỆN LUẬT KẾT NHIỀU CHIỀU MỜ 74
3.1. Giới thiệu 74
3.2. Phân loại CSDL nhiều chiều 78
3.3. Phát hiện luật kết hợp từ CSDL nhiều chiều loại 2 81
3.3.1. Các khái niệm cơ bản 81
3.3.2. Phát hiện luật kết hợp nhiều chiều mờ từ CSDL nhiều chiều mờ loại 2
86
3.4. Phát hiện luật kết hợp từ CSDL tác vụ nhiều chiều loại 3 90
3.4.1. Chuyển CSDL nhiều chiều loại 3 về CSDL nhiều chiều mới 90
3.4.2. Các khái niệm cơ bản 95
3.4.3. Phát hiện luật kết hợp nhiều chiều mờ từ CSDL nhiều chiều mờ loại 3
97
Kết luận 97
KẾT LUẬN 100
TÀI LIỆU THAM KHẢO 102
3
Bảng từ viết tắt
Từ hoặc cụm từ
Viết
tắt
Tiếng anh
Cơ sở dữ liệu CSDL Database
Kho dữ liệu DW Data Warehouse
Xử lý phân tích trực tuyến OLAP OnLine Analystical Processing
Xử lý giao dịch trực tuyến OLTP Online Transaction Processing
Hệ thống ứng dụng tác nghiệp OAS Operational Application System
nhỏ 74
Bảng 16: sử dụng phương pháp rời rạc thuộc tính định lượng có giá trị số.75
Bảng 17: CSDL định lượng 77
Bảng 18: CSDL mờ 78
5
Bảng 19: CSDL nhiều chiều loại 2 79
Bảng 20: CSDL nhiều chiều loại 3 80
Bảng 21: CSDL nhiều chiều loại 4 80
Bảng 22: CSDL nhiều chiều mờ loại 2 83
Bảng 23:CSDL nhiều chiều mờ loại 2 mở rộng 84
Bảng 24:Bảng kí hiệu sử dụng trong thuật toán phát hiện luật kết hợp nhiều
chiều mờ 86
Bảng 25: tập mục dữ liệu mờ mở rộng phổ biến có độ dài bằng 1 88
Bảng 26: tập mục dữ liệu mở rộng mờ phổ biến có độ dài là 2 89
Bảng 27: CSDL tác vụ nhiều chiều mờ loại 3 94
6
Danh mục hình vẽ
Hình 1: Luồng dữ liệu trong một tổ chức 12
Hình 2: Tích hợp dữ liệu 15
Hình 3: Tích hợp dữ liệu 15
Hình 4: Tính thời gian của dữ liệu 17
Hình 5: Khối dữ liệu 3-D thể hiện cho dữ liệu của bảng 2 21
Hình 6: Sơ đồ hình sao của DW bán hàng của Công ty Điện tử 23
Hình 7: Sơ đồ hình bông tuyết của DW bán hàng của Công ty Điện tử 24
Hình 8: Sơ đồ hình chòm sao sự kiện của DW bán hàng của Công ty Điện tử
ng kỹ thuật chia khoảng giá trị các thuộc tính
trong CSDL định lượng và đưa nó về CSDL nhị phân rồi ứng dụng thuật toán
phát hiện luật kết hợp từ CSDL nhị phân đã biết hoặc là sử dụng lý thuyết tập
mờ để chuyển CSDL định lượng thành CSDL mờ và cải tiến phát triển thuật
toán phát hiện luật kết hợp nhị phân cho phù hợp. Cách tiếp cận sau cùng
đang được quan tâm nhiều vì nó kh
ắc phục được nhược điểm “thiếu tự nhiên”
và “quá cồng kềnh” của cách tiếp cận chia khoảng giá trị thuộc tính trong
CSDL định lượng. Luật kết hợp được phát hiện khi đó được gọi là luật kết
hợp mờ.
Tương tự như vậy để phát hiện luật kết hợp từ CSDL nhiều chiều (hay
Kho dữ liệu – Dataware house) trước hết người ta cũng xây d
ựng các phương
pháp nhằm phát hiện luật kết hợp từ các cơ sở dữ liệu nhiều chiều nhị phân và
nó được gọi là luật kết hợp nhiều chiều. Đến nay vấn đề phát hiện luật kết hợp
nhiều chiều cơ bản đã được giải quyết, trong khi các kết quả nghiên cứu đề
8
xuất phương pháp phát hiện luật kết hợp từ cơ sở dữ liệu nhiều chiều định
lượng còn rất hạn chế.
Luận văn này liên quan đến những vấn đề phát hiện luật kết hợp từ
CSDL nhiều chiều định lượng theo cách tiếp cận đang được quan tâm sử dụng
nhằm phát hiện luật kết hợp mờ từ cơ sở
dữ liệu định lượng.
Cụ thể mục đích của luận văn này là:
Về mặt lý thuyết: luận văn trình bày một cách tổng quan một số vấn đề
về kho dữ liệu, phát hiện luật kết hợp từ CSDL nhị phân, phát hiện luật kết
hợp nhiều chiều từ CSDL định lượng và đề xuất kỹ thuật phát hiện luật kết
h
ợp nhiều chiều mờ từ các CSDL nhiều chiều định lượng bằng cách mờ hoá
chiều của CSDL.
hạn chế trong việc giải quyết đề tài luận văn cùng với hướng phát triển tiếp
theo.
Tôi xin bày tỏ lòng kính trọng và biết ơn sâu sắc tới thầy Đỗ Văn
Thành - Trung tâm Thông Tin và Dự báo KT-XH Quốc Gia đã tận tình hướng
dẫn và giúp đỡ tôi hoàn thành bản luận văn.
Tôi cũng xin cảm ơn các thầy cô khoa Công nghệ Thông tin, Trường
Đại học Công Nghệ - Đại học Quốc Gia Hà Nội đã giúp tôi hoàn thành khoá
học.
10
Chương 1 TỔNG QUAN VỀ CƠ SỞ DỮ LIỆU NHIỀU CHIỀU
1.1 Tại sao phải xây dựng kho dữ liệu?
Nhân loại đang sống trong thời đại của nền kinh tế tri thức. Mọi hoạt
động của con người muốn đạt hiệu quả cao, giành được thắng lợi trong thế
cạnh tranh gay gắt thì nhất thiết phải có những phương pháp để có được
những thông tin, tri thức có chất lượng cần thiết một cách nhanh chóng và kịp
thời. Thông tin có thể có được ở mọi nơi, mọi thời điể
m và tồn tại ở nhiều
dạng khác nhau: âm thanh, hình ảnh, văn bản
Việc áp dụng công nghệ thông tin vào thực tiễn sản xuất kinh doanh đã
mang lại những hiệu quả và lợi ích to lớn. Công nghệ ngày càng được phát
triển, hoàn thiện hơn để đáp ứng những yêu cầu ngày càng cao của thực tế
nghiên cứu, quản lý sản xuất và kinh doanh. Sự mở rộng qui mô áp dụng từ
những ứng dụng
đơn lẻ đến các hệ thống thông tin cỡ lớn đã dẫn đến những
thành công vượt bậc trong kinh doanh. Các hệ thống thông tin từ chỗ chỉ giải
quyết những xử lý công việc hàng ngày đã tiến tới đáp ứng được những yêu
cầu ở mức độ cao hơn. Các nhà quản lý điều hành có thể biết được công việc
đang diễn ra như thế nào. Tuy nhiên việc xây dựng một h
ệ thống như thế vấp
tin và một thành phần dữ liệu có thể tồn tại ở nhiều nguồn khác nhau
Giải pháp cho tất cả các vấn đề tồn tại nêu trên chính là xây dựng một
kho dữ liệu (Data Warehouse).
1.2 Khái niệm kho dữ liệu – Data Warehouse
Định nghĩa: Kho dữ liệu (Data Warehouse - DW) được hiểu là bộ dữ
liệu có giá trị lịch sử, theo chuỗi thời gian, được tích hợp và định hướng vào
từng chủ đề nhằm hỗ trợ quá trình ra quyết định trong quản lý .[4]
Kho dữ liệu thường rất lớn tới hàng trăm GigaByte hay thậm chí hàng
Terabyte.
12
Kho dữ liệu được xây dựng để thuận lợi cho việc truy cập dữ liệu theo
nhiều nguồn được phát triển dựa trên nhiều hệ quản trị CSDL khác nhau sao
cho có thể kết hợp được cả những ứng dụng của các công nghệ hiện đại và kế
thừa được từ những hệ thống đã có sẵn từ trước. Dữ liệu phát sinh từ các hoạt
động hàng ngày và
được thu thập xử lí để phục vụ công việc kinh doanh cụ
thể của một tổ chức thường được gọi là dữ liệu tác nghiệp (operational data)
và hoạt động thu thập xử lí loại dữ liệu này được gọi là xử lí giao dịch trực
tuyến (On_line Transaction Processing - OLPT). Ngược lại, kho dữ liệu phục
vụ cho việc phân tích với kết quả mang tính thông tin cao. Các hệ thống thông
tin thu thập xử lí dữ liệu lo
ại này còn được gọi là hệ xử lí phân tích trực tuyến
(On_Line Analytical Processing - OLAP).
Nói cách khác, kho dữ liệu là một tập hợp các CSDL rất lớn tới hàng
trăm Gigabyte hay thậm chí hàng Tera byte dữ liệu từ nhiều phân hệ của hệ
thống, lưu trữ và phân tích phục vụ cho việc cung cấp các dịch vụ thông tin
liên quan tới các hoạt động sản xuất, kinh doanh một tổ chức, cơ quan hay
doanh nghiệp.
Dòng dữ liệu trong m
3. Phục vụ phân tích phát hiện tri thức mới từ dữ liệu:
a. Hỗ trợ để các nhân viên của tổ chức thực hiện tốt, hiệ
u quả công
việc của mình như: có những quyết định hợp lý, nhanh và chính
xác.
4. Hỗ trợ tổ chức xây dựng chiến lược, kế hoạch hoạt động sản xuất,
kinh doanh hiệu quả.
Để đạt được những yêu cầu trên, khi xây dựng DW cần chú ý:
• Nâng cao chất lượng dữ liệu bằng các phương pháp làm sạch và tinh
lọc dữ liệu theo những hướng chủ đề nhất
định
• Tổng hợp và kết hợp dữ liệu
• Đồng bộ hoá các nguồn dữ liệu với DW
• Phân định và đồng nhất các hệ quản trị cơ sở dữ liệu tác nghiệp như
là các công cụ chuẩn để phục vụ cho DW.
• Quản lí siêu dữ liệu
• Cung cấp thông tin được tích hợp, tóm tắt hoặc được liên kết, tổ chức
theo các chủ
đề
14
• DW được sử dụng trong các hệ thống hỗ trợ quyết định (Decision
suport system - DSS), hỗ trợ cho các truy vấn đặc biệt.
1.4 Đặc điểm của kho dữ liệu
Kho dữ liệu (DW) có những tính chất cơ bản sau [3],[4]:
1.4.1. Tính tích hợp (Integration)
Dữ liệu trong DW được tổ chức theo nhiều cách khác nhau sao cho phù
hợp với các qui ước đặt tên, thống nhất về số đo, cơ cấu mã hoá và cấu trúc
vật lý của dữ liệu, v.v. Một DW là một khung nhìn thông tin mức toàn doanh
nghiệp, thống nhất các khung nhìn khác nhau thành một khung nhìn theo một
Lê Anh Tuấn
132 - Cầu Giấy
Mở tài khoản năm 1995
Tích hợp
và biến đổi
Khách hàng
Lê Anh Tuấn
Nam
132 - Cầu Giấy
Khách hàng từ năm 1992
Sự tích hợp Appl. A: m, f m, f
Appl. B: 0, 1
Appl. C: male, female
Appl. A: pipeline cm cm
Appl. B: pipeline inch (2,54 cm)
Appl. C: pipeline yard (0.914 cm)
Hình 2: Tích hợp dữ liệu
của một chủ điểm trong một giai đoạn, do vậy cho phép khôi phục lại lịch sử
và so sánh một cách chính xác các giai đoạn khác nhau. Yếu tố thời gian đóng
vai trò như một phần của khoá để bảo đảm tính đơn nhất và cung cấp đặc
trưng về thời gian cho dữ liệu.
Dữ
liệu trong OAS cần phải chính xác ở chính thời điểm truy cập, còn ở
DW chỉ cần có hiệu lực trong khoảng thời gian nào đó, trong khoảng 5 đến 10
năm hoặc lâu hơn. Dữ liệu của CSDL tác nghiệp thường sau một khoảng thời
gian nhất định sẽ trở thành dữ liệu lịch sử và chúng sẽ được chuyển vào kho
dữ liệu. Đó chính là những dữ liệu hợp lý về nh
ững chủ điểm cần lưu trữ.
17
CSDL tác nghiệp DW
Dữ liệu kinh doanh: ảnh chụp dữ liệu:
+ Thời gian ngắn 30-60 ngày + Thời gian dài: 5 đến 10 năm
+ Có thể có yếu tố thời gian hoặc
không
+ Luôn có yếu tố thời gian
+ Dữ liệu có th
ể
cập nhật + Khi dữ liệu được chụp lại thì
không cập nhật được
Hình 4: Tính thời gian của dữ liệu
1.4.4. Dữ liệu có tính ổn định (nonvolatility)
Dữ liệu trong DW là dữ liệu chỉ đọc và chỉ có thể được kiểm tra, không
được sửa đổi bởi người sử dụng đầu cuối. Nó chỉ cho phép thực hiện hai thao
tác cơ bản:
như tình hình bán của mỗi mặt hàng trong từng tháng, các chi nhánh và vị trí
ở đó những mặt này đã được bán, Mỗi chiều có thể có một bảng liên kết
nhằm mô tả rõ hơn về nó được gọi là bả
ng chiều. Chẳng hạn bảng chiều đối
với chiều mat_hang có thể chứa các thuộc tính như ten_mat_hang, chi_nhanh
và kieu. Các bảng chiều do người sử dụng xác định hoặc cũng có thể được
sinh ra hoặc được bổ sung một cách tự động dựa trên các phân bố dữ liệu.
Các tiêu chuẩn đánh giá: Phân loại và tính toán
Một điểm nhiều chiều trong không gian khối dữ liệu đượ
c xác định bởi
bộ giá trị của chiều. Ví dụ (thoi_gian = “Q
1
”, mat_hang = “GTGĐ”, vi_tri =
“Hà nội”). Một tiêu chuẩn đánh giá khối dữ liệu là một hàm số có thể được
19
đánh giá tại các điểm thuộc không gian khối dữ liệu (hàm số đó được gọi là
hàm tích hợp). Một giá trị đánh giá được tính toán đối với một điểm cho trước
bằng cách tích hợp dữ liệu ứng với bộ giá trị chiều tương ứng xác định điểm
đã cho.
Các tiêu chuẩn đánh giá được tổ chức theo 3 chiến lược tuỳ thuộc vào kiểu
mà hàm tích h
ợp sử dụng.
Phân bố (distribute): Hàm tích hợp là hàm phân bố nếu nó có thể được tính
theo cách như sau: giả sử dữ liệu được chia thành n tập, việc tính toán của
hàm này trên mỗi tập như vậy sẽ cho một giá trị tích hợp; nếu giá trị của hàm
tại n giá trị tích hợp đó giống như kết quả của việc áp dụng hàm đó trên toàn
bộ tập dữ liệu chưa được phân chia. Ví dụ
các hàm min(), max(), count() đều
là những hàm phân bố.
Tiêu chuẩn đánh giá là phân bố nếu nó nhận được bằng việc ứng dụng một
Vi_ tri = “Hà nội”
Kieu
Thời gian (Quý) Giải trí gia đình Máy tính Điện thoại Thiết bị bảo vệ
Q
1
Q
2
Q
3
Q
4
605
680
812
917
825
952
1023
1038
14
31
30
38
400
512
501
580
B
ảng 1: Dữ liệu bán hàng của Công ty Điện tử theo 2 chiều thoi_gian và
501
580
554
450
430
580
705
560
650
780
10
16
25
30
150
230
258
300
1087
1130
1034
1142
968
800
789
805
38
41
42
54
ộ
i
GTGD
825
925
1023
1038
14
31
30
38
400
512
501
580
ĐN
HCM
150
258
1087 968 38
980
230
300
ĐTTB
554
925
10
705
967
872
Tinh
Nuoc
Hình 6: Sơ đồ hình sao của DW bán hàng của Công ty Điện tử
Như vậy trong sơ đồ hình sao, mỗi chiều được biểu diễn bởi chỉ một
bảng và mỗi bảng chứa một tập các thuộc tính.
b.Sơ đồ bông tuyết: có thể được xem là một biến thể của sơ đồ hình sao.
Trong sơ đồ bông tuyết các bảng chiều được chuẩn hoá. Điều này cho phép sơ
đồ bông tuyết có thể giảm được dư thừa dữ li
ệu tốt hơn sơ đồ hình sao, tuy
nhiên cấu trúc bông tuyết có thể làm giảm tính hiệu quả của việc thực hiện
các truy vấn.
Ví dụ: Hình 7 ở dưới mô tả sơ đồ bông tuyết của DW Bán hàng của Công ty
Điện tử. Trong sơ đồ này Bảng sự kiện là tương tự như Bảng sự kiện trong sơ
đồ hình sao. Sự khác nhau chủ yếu của 2 sơ đồ nêu trên là ở các bảng chi
ều.
Chẳng hạn bảng chiều mat_hang trong sơ đồ hình sao được chuẩn hoá trong
sơ đồ bông tuyết thành 2 bảng chiều Mat_hang và Nha_cung_cap.
Ma_TG
Ma_mat_hang
ma_vi_tri
Tong_so_ban
So_mat_hang_banMa_mat_hang
Ten_mat_hang
Loai_hang
Ten_nha_cung_cap
bảng chiều thoi_gian
Ma_mathang
Ten_mat_hang
Loai_hang
Ma_nha_cung_cap
bảng chiều thoi_gian
bảng chiều vi_tri
bảng chiều mat_hang
bảng sự kiện
Ma_nha_cung_cap
Ten_nha_cung_cap
bảng chiều nha_cung_cap
Copyright: Tài liệu đại học ©