0
ĐẠI HỌC THÁI NGUYÊN
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
VÀ TRUYỀN THÔNG
LÊ XUÂN LƢỢNG
PHÁT HIỆN LUẬT KẾT HỢP ỨNG DỤNG TRONG
CƠ SỞ DỮ LIỆU QUẢN LÝ SINH VIÊN
Chuyên nghà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
Ngƣời hƣớng dẫn khoa học: TS Vũ Mạnh Xuân
THÁI NGUYÊN - 2011
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
i
LỜI CAM ĐOAN
Tôi xin cam đoan toàn bộ nội dung trong Luận văn hoàn toàn theo đúng
nội dung đề cương cũng như nội dung mà cán bộ hướng dẫn giao cho. Nội
dung luận văn, các phần trích lục các tài liệu hoàn toàn chính xác. Nếu có sai
sót tôi hoàn toàn chịu trách nhiệm.
Tác giả luận văn
Lê Xuân Lượng
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
ii
MỤC LỤC
Lời cam đoan .................................................................................................................. i
Mục lục
...............................................................................................................ii
Danh mục các chữ viết tắt ....................................................................................... iv
Danh mục các bảng ................................................................................................... v
Danh mục các hình vẽ ............................................................................................. vi
MỞ ĐẦU
............................................................................................................................ 1
Chƣơng 1. TỔNG QUAN VỀ CƠ SỞ DỮ LIỆU VÀ KHAI PHÁ
DỮ LIỆU........................................................................................................ 3
1.1. Một số khái niệm về cơ sở dữ liệu ........................................................ 3
1.1.1. Cơ sở dữ liệu ................................................................................... 3
1.1.2. Hệ quản trị cơ sở dữ liệu ................................................................. 4
1.2. Tổ chức và khai thác cơ sở dữ liệu truyền thống ................................... 5
1.3. Kho dữ liệu ............................................................................................ 6
1.3.1. Đinh nghĩa kho dữ liệu.................................................................... 6
1.3.2. Cấu trúc của kho dữ liệu ................................................................. 7
1.3.3. Mục đích của việc xây dựng kho dữ liệu ........................................ 9
1.4. Khai phá dữ liệu ................................................................................... 11
1.4.1. Khái niệm ...................................................................................... 11
1.4.2. Các bước của quá trình phát hiện tri thức ..................................... 11
1.4.3. Một số phương pháp khai phá dữ liệu ......................................... 13
1.4.3.1. Phương pháp suy diễn và quy nạp ......................................... 13
1.4.3.2. Cây quyết định và luật ........................................................... 14
1.4.3.3. Phân nhóm và phân đoạn ....................................................... 16
1.4.3.4. Phương pháp ứng dụng K-láng giềng gần ............................. 16
1.4.3.5. Các phương pháp dựa trên mẫu ............................................. 17
1.4.3.6. Phát hiện các luật kết hợp ...................................................... 17
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
iii
1.4.4. Nhiệm vụ chính của khai phá dữ liệu ........................................... 19
1.4.5. Những khó khăn trong nghiên cứu khai phá dữ liệu .................... 21
1.4.6. Một số ứng dụng khai phá dữ liệu ................................................ 24
Chƣơng 2. PHÁT HIỆN LUẬT KẾT HỢP .............................................................. 25
2.1. Các khái niệm và tính chất của luật kết hợp ........................................ 25
2.1.1. Một số khái niệm .......................................................................... 25
2.1.2. Thuật toán cơ bản .......................................................................... 28
2.1.3. Tính chất của luật kết hợp và tập mục phổ biến ........................... 32
2.1.4. Một số hướng tiếp cận trong khai phá luật kết hợp ...................... 33
2.2. Một số thuật toán phát hiện luật kết hợp .............................................. 35
2.2.1. Thuật toán AIS .............................................................................. 35
2.2.2. Thuật toán SETM .......................................................................... 36
2.2.3. Thuật toán Apriori ......................................................................... 38
2.2.4. Thuật toán Apriori-TID................................................................. 44
2.2.5. Thuật toán Apriori-Hybrid ............................................................ 46
2.2.6. Thuật toán PARTITION ............................................................... 47
2.2.7. Sinh các luật kết hợp từ tập mục phổ biến ................................... 48
Chƣơng 3. ỨNG DỤNG PHÁT HIỆN LUẬT KẾT HỢP KHAI PHÁ
DỮ LIỆU QUẢN LÝ SINH VIÊN....................................................... 52
3.1. Đặt vấn đề ............................................................................................ 52
3.2. Xây dựng chương trình demo thuật toán Apriori ứng dụng phát
hiện luận kết hợp trong CSDL quản lý sinh viên ......................... 54
3.2.1. Các bước tiến hành khai phá dữ liệu quản lý sinh viên ................ 54
3.2.2. Xây dựng bảng cơ sở dữ liệu để khai phá ..................................... 54
3.2.3. Chương trình demo ....................................................................... 57
3.2.4. Một số kết quả thử nghiệm ........................................................... 58
KẾT LUẬN .......................................................................................................................... 64
TÀI LIỆU THAM KHẢO ............................................................................................... 65
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
iv
DANH MỤC CÁC CHỮ VIẾT TẮT
Ký hiệu
Diễn giải
supp:
Độ hỗ trợ (support)
conf:
Độ tin cậy (confidence)
minsup: Ngưỡng độ hỗ trợ tối thiểu
mincof:
Ngưỡng độ tin cậy tối thiểu
SQL:
Structured Query Language
KDD:
Kownledge Discovery in Database
FI:
Frenquent Itemset
MFI:
Maximally Frequent Itemset
CSDL:
Cơ sở dữ liệu
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
v
DANH MỤC CÁC BẢNG
Bảng 2.1. Giao dịch mua hàng ........................................................................ 30
Bảng 2.2. Tính độ hỗ trợ cho các tập hợp chứa các mặt hàng ........................ 30
Bảng 2.3. Các luật kết hợp và độ tin cậy của chúng ....................................... 31
Bảng 2.4. Ma trận biểu diễn cơ sở dữ liệu ...................................................... 43
Bảng 2.5. Vector biểu diễn nhị phân cho tập 1 thuộc tính .............................. 43
Bảng 2.6. Vector biểu diễn nhị phân cho các tập 2 thuộc tính ....................... 43
Bảng 2.7. Vector biểu diễn nhị phân cho các tập 3 thuộc tính ....................... 44
Bảng 2.8. Vector biểu diễn nhị phân cho các tập 4 thuộc tính ....................... 44
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
vi
DANH MỤC CÁC HÌNH VẼ
Hình 1.1. Cấu trúc kho dữ liệu .......................................................................... 8
Hình 1.2. Quy trình phát hiện tri thức ............................................................. 12
Hình 1.3. Mẫu kết quả với phương pháp cây quyết định ................................ 15
Hình 3.1. Sơ đồ khai phá dữ liệu quản lý sinh viên ........................................ 54
Hình 3.2. Bảng cơ sở dữ liệu khai phá ............................................................ 56
Hinh 3.3. Giao diện chính của chương trình demo ......................................... 57
Hình 3.4. Giao diện “Thao tác với CSDL” ..................................................... 58
Hình 3.5. Kết quả khai phá lần thứ 1 .............................................................. 59
Hình 3.6. Kết quả thử nghiệm lần thứ 2.......................................................... 60
Hình 3.7. Kết quả thử nghiệm lần thứ 3.......................................................... 61
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
1
MỞ ĐẦU
Một trong những ứng dụng quan trọng nhất của công nghệ thông tin
trong đời sống là giúp giải quyết các bài toán quản lý. Kể từ khi máy tính điện
tử trở thành một công cụ lao động quan trọng thì một trong những nhu cầu
đầu tiên là lưu trữ, tìm kiếm và xử lý số liệu thống kê. Đến nay, các cơ sở dữ
liệu đã trở nên khổng lồ và người ta mong muốn kho dữ liệu đó cần được khai
thác hiệu quả hơn trên nhiều bình diện. Trong những năm gần đây, khai phá
dữ liệu (Data mining) đã trở thành một trong những hướng nghiên cứu lớn
nhất của lĩnh vực khoa học máy tính và công nghệ thông tin. Khai phá dữ liệu
đang được áp dụng một cách rộng rãi trong nhiều lĩnh vực kinh doanh và đời
sống khác nhau: marketing, tài chính, ngân hàng và bảo hiểm, khoa học, y tế,
an ninh, internet…
Việc khai phá dữ liệu từ kho dữ liệu có nhiều hướng tiếp cận. Các bài
toán chủ yếu trong khai thác dữ liệu là: Khai thác chuỗi, khai thác web, đặc
biệt là việc phát hiện luật kết hợp (association rules mining) và việc gom cụm
(clustering), phân lớp (classification) dữ liệu,... Trong đó, phát hiện luật kết
hợp là một trong những nội dung quan trọng của khai phá dữ liệu và là một
lĩnh vực nghiên cứu nhiều triển vọng với khả năng ứng dụng cao vào thực tế.
Vì tất cả nhưng lí do trên mà tôi đã chọn đề tài luận văn: “Phát hiện luật
kết hợp ứng dụng trong cơ sở dữ liệu quản lý sinh viên” làm chủ đề nghiên
cứu của mình.
Mục đích của luận văn là nghiên cứu những vấn đề cơ bản về phát hiện
luật kết hợp, một số thuật toán khai phá dữ liệu đã được giới thiệu. Trên cơ sở
đó áp dụng vào một bài toán cụ thể là cài đặt chương trình phát hiện luật kết
hợp từ cơ sở dữ liệu quản lý sinh viên nhằm rút ra những kết luận hữu ích cho
quá trình đào tạo và quản lý sinh viên.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
2
Với mục tiêu đó, luận văn được trình bày trong 3 chương:
Chương 1: Tổng quan về cơ sở dữ liệu và khai phá dữ liệu
Chương 2: Phát hiện luật kết hợp
Chương 3: Phát hiện luật kết hợp trong cơ sở dữ liệu quản lý sinh viên
Ngoài phần tổng hợp những kiến thức về khai phá dữ liệu, các thuật
toán phát hiện luật kết hợp, luận văn cũng đã trình bày kết quả thử nghiệm
qua một bài toán cụ thể để minh họa.
Để có được kết quả này tôi đã nhận được sự quan tâm, động viên, giúp
đỡ rất nhiều của các Thầy giáo, Cô giáo trong Khoa Công nghệ thông tin Đại học Thái Nguyên cũng như của bạn bè, đồng nghiệp, đặc biệt là sự chỉ
bảo tận tình của TS. Vũ Mạnh Xuân và sự nỗ lực của bản thân, đến nay tôi
đã hoàn thành đề tài.
Tuy nhiên trong quá trình làm việc, mặc dù đã cố gắng, nỗ lực hết sức
nhưng không thể tránh khỏi thiếu sót, em kính mong nhận được sự chỉ bảo
của các thầy cô để đề tài được hoàn thiện hơn.
Tôi xin chân thành cảm ơn !
Thái Nguyên, ngày 29 tháng 09 năm 2011
Học viên
Lê Xuân Lượng
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
3
Chƣơng 1
TỔNG QUAN VỀ CƠ SỞ DỮ LIỆU VÀ KHAI PHÁ DỮ LIỆU
Chương này trình bày những nét khái quát về cơ sở dữ liệu, kho dữ liệu
và một số phương pháp khai phá dữ liệu.
1.1. Một số khái niệm về cơ sở dữ liệu (CSDL)
1.1.1. Cơ sở dữ liệu
Cơ sở dữ liệu (Database) là một hệ thống các thông tin có cấu trúc được
lưu trữ trên các thiết bị lưu trữ thông tin thứ cấp (như băng từ, đĩa từ ...) để có
thể thỏa mãn yêu cầu khai thác thông tin đồng thời của nhiều người sử dụng
hay nhiều chương trình ứng dụng với nhiều mục đích khác nhau.
Như vậy đặc trưng của cơ sở dữ liệu là:
- Giảm sự trùng lặp thông tin xuống mức thấp nhất và do đó bảo đảm
được tính nhất quán và toàn vẹn dữ liệu.
- Đảm bảo dữ liệu có thể được truy xuất theo nhiều cách khác nhau.
- Khả năng chia sẻ thông tin cho nhiều người sử dụng và nhiều ứng
dụng khác nhau.
Các loại cơ sở dữ liệu [2]
- Cơ sở dữ liệu dạng file: dữ liệu được lưu trữ dưới dạng các file có thể
là text, ascii, *.dbf. Tiêu biểu cho cơ sở dữ liệu dạng file là *.mbd Foxpro
- Cơ sở dữ liệu quan hệ: dữ liệu được lưu trữ trong các bảng dữ liệu gọi là
các thực thể, giữa các thực thể này có mối liên hệ với nhau gọi là các quan hệ,
mỗi quan hệ có các thuộc tính, trong đó có một thuộc tính là khóa chính. Các hệ
quản trị hỗ trợ cơ sở dữ liệu quan hệ như: MS SQL server, Oracle, MySQL...
- Cơ sở dữ liệu hướng đối tượng: dữ liệu cũng được lưu trữ trong các
bản dữ liệu nhưng các bảng có bổ sung thêm các tính năng hướng đối tượng
như lưu trữ thêm các hành vi, nhằm thể hiện hành vi của đối tượng. Mỗi bảng
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
4
xem như một lớp dữ liệu, một dòng dữ liệu trong bảng là một đối tượng. Các hệ
quản trị có hỗ trợ cơ sở dữ liệu quan hệ như: MS SQL server, Oracle, Postgres.
- Cơ sở dữ liệu bán cấu trúc: dữ liệu được lưu dưới dạng XML, với định
dạng này thông tin mô tả về đối tượng thể hiện trong các tag. Đây là cơ sở dữ
liệu có nhiều ưu điểm do lưu trữ được hầu hết các loại dữ liệu khác nhau nên cơ
sở dữ liệu bán cấu trúc là hướng mới trong nghiên cứu và ứng dụng.
Với sự giúp sức của công nghệ thông tin và truyền thông còn người đã
tạo ra những hệ thống thông tin được tổ chức dưới dạng CSDL ở tất cả các
ngành nghề lĩnh vực trong xã hội, phục vụ nhiều mục đích khác nhau như: Hệ
thống thông tin địa lý GIS, hệ thống thông tin tài chính, ngân hàng, quản lý
kinh doanh, quản lý điều hành… Các thông tin có tổ chức này được quản lý,
khai thác qua một hệ thống phần mềm khai thác hoặc Hệ quản trị cơ sở dữ liệu
1.1.2. Hệ quản trị cơ sở dữ liệu
Hệ quản trị cơ sở dữ liệu (Database Management System): là phần mềm
hay hệ thống được thiết kế để quản trị một cơ sở dữ liệu. Cụ thể, các chương
trình thuộc loại này hỗ trợ khả năng lưu trữ, sửa chữa, xóa và tìm kiếm thông
tin trong một cơ sở dữ liệu (CSDL). Có rất nhiều loại hệ quản trị CSDL khác
nhau: từ phần mềm nhỏ chạy trên máy tính cá nhân cho đến những hệ quản trị
phức tạp chạy trên một hoặc nhiều siêu máy tính.
Qua nhiều năm phát triển, hệ quản trị CSDL ngày nay rất phong phú và
đa dạng được xây dựng trên các mô hình dữ liệu khác nhau như:
- Mô hình cơ sở dữ liệu quan hệ
- Mô hình CSDL phân tán
- Mô hình CSDL hướng đối tượng
- Mô hình CSDL suy diễn…
Tuy nhiên, đa số hệ quản trị CSDL trên thị trường đều có một đặc điểm
chung là sử dụng ngôn ngữ truy vấn theo cấu trúc mà tiếng Anh gọi là Structured
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
5
Query Language (SQL). Các hệ quản trị CSDL phổ biến được nhiều người biết
đến là MySQL, Oracle, PostgreSQL, SQL Server, DB2, Infomix,... Phần lớn
các hệ quản trị CSDL kể trên hoạt động tốt trên nhiều hệ điều hành khác nhau
như Linux, Unix và MacOS ngoại trừ SQL Server của Microsoft chỉ chạy trên
hệ điều hành Windows.
1.2. Tổ chức và khai thác cơ sở dữ liệu truyền thống
Việc dùng các phương tiện tin học để tổ chức và khai thác các cơ sở dữ
liệu đã được phát triển từ những năm 60. Từ đó cho đến nay, rất nhiều cơ sở
dữ liệu đã được tổ chức, phát triển và khai thác ở mọi quy mô và ở khắp các
lĩnh vực hoạt động của con người và xã hội. Theo như đánh giá cho thấy,
lượng thông tin trên thế giới cứ sau 20 tháng lại tăng gấp đôi. Kích thước và
số lượng cơ sở dữ liệu thậm chí còn tăng nhanh hơn. Năm 1989, tổng số cơ sở
dữ liệu trên thế giới vào khoảng 5 triệu, hầu hết đều là các cơ sở dữ liệu cỡ
nhỏ được phát triển trên DBaseIII. Với sự phát triển mạnh mẽ của công nghệ
điện tử tạo ra các bộ nhớ có dung lượng lớn, bộ xử lý tốc độ cao cùng với các
hệ thống mạng viễn thông, người ta đã xây dựng các hệ thống thông tin nhằm
tự động hóa mọi hoạt động kinh doanh của mình. Điều này đã tạo ra một dòng
dữ liệu tăng lên không ngừng vì ngay từ các giao dịch đơn giản nhất như một
cuộc gọi điện thoại, kiểm tra sức khỏe, sử dụng thẻ tín dụng,… đều được ghi
vào trong máy tính. Cho đến nay, con số ày đã trở nên khổng lồ, bao gồm các
cơ sở dữ liệu cực lớn cỡ gigabytes và thậm chí terabytes lưu trữ các dữ liệu
kinh doanh, ví dụ như dữ liệu thông tin khách hàng, dữ liệu lịch sử các giao
dịch, dữ liệu bán hàng, dữ liệu các tài khoản, các khoản vay, sử dụng vốn,…
Nhiều hệ quản trị cơ sở dữ liệu mạnh với các công cụ phong phú và thuận tiện
đã giúp con người khai thác có hiệu quả các nguồn tài nguyên dữ liệu. Mô
hình cơ sở dữ liệu quan hệ và ngôn ngữ vấn đáp chuẩn (SQL) đã có vai trò hết
sức quan trọng trong việc tổ chức và khai thác các cơ sở dữ liệu đó. Cho đến
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
6
nay, không một tổ chức nào là không sử dụng các hệ quản trị cơ sở dữ liệu và
các hệ công cụ báo cáo, ngôn ngữ hỏi đáp nhằm khai thác các cơ sở dữ liệu
phục vụ cho hoạt động tác nghiệp của mình.
1.3. Kho dữ liệu (data warehouse)
Cùng với việc tăng không ngừng khối lượng dữ liệu, các hệ thống
thông tin cũng được chuyên môn hóa, phân chia theo các lĩnh vực ứng dụng
như: Quản lý, sản xuất, tài chính, buôn bán thị trường,... Như vậy, bên cạnh
chức năng khai thác dữ liệu có tính chất tác nghiệp, sự thành công trong mọi
lĩnh vực không còn là năng suất của các hệ thống thông tin nữa mà là tính linh
hoạt và sẵn sàng đáp lại những yêu cầu trong thực tế, CSDL cần đem lại
những “tri thức” hơn là chính những dữ liệu đó. Các quyết định cần phải có
càng nhanh càng tốt và phải chính xác dựa trên những dữ liệu sẵn có trong khi
khối lượng dữ liệu cứ sau 20 tháng lại tăng gấp đôi làm ảnh hưởng đến thời
gian ra quyết định cũng như khả năng hiểu hết được nội dung dữ liệu. Lúc
này các mô hình CSDL truyền thống và ngôn ngữ SQL đã cho thấy không có
khả năng thực hiện công việc này. Để lấy được những thông tin có tính “tri
thức” trong khối dữ liệu khổng lồ này, người ta đã đi tìm những kỹ thuật có
khả năng hợp nhất các dữ liệu từ các hệ thống giao dịch khác nhau, chuyển
đổi thành một tập hợp các cơ sở dữ liệu ổn định, có chất lượng, chỉ được sử
dụng riêng cho một vài mục đích nào đó. Các kỹ thuật đó được gọi chung là
kỹ thuật tạo kho dữ liệu (data warehousing) và môi trường các dữ liệu đó
được gọi là các kho dữ liệu.
1.3.1. Đinh nghĩa kho dữ liệu
Kho dữ liệu là một môi trường có cấu trúc các hệ thống thông tin, cung
cấp cho người dùng các thông tin khó có thể truy nhập hoặc biểu diễn trong
các CSDL tác nghiệp truyền thống, nhằm mục đích hỗ trợ việc ra quyết định
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
7
mang tính lịch sử hoặc hiện tại. Theo W.H.Inmon, có thể định nghĩa kho dữ
liệu như sau: “Một kho dữ liệu là một tập hợp dữ liệu tích hợp hướng chủ đề
có tính ổn định, thay đổi theo thời gian nhằm hỗ trợ cho việc ra quyết định.
Nói cách khác, một kho dữ liệu bao gồm:
- Một hoặc nhiều công cụ để chiết xuất dữ liệu từ bất kỳ dạng cấu trúc
dữ liệu nào.
- Cơ sở dữ liệu tích hợp hướng chủ đề ổn định được tổng hợp từ các dữ
liệu bằng cách lập bảng dữ liệu của dữ liệu.”
Một kho dữ liệu có thể được coi là một hệ thống thông tin với những
thuộc tính sau:
- Là một cơ sở dữ liệu được thiết kế có nhiệm vụ phân tích, sử dụng các
dữ liệu từ các ứng dụng khác nhau.
- Hỗ trợ cho một số người dùng có liên quan với các thông tin liên quan.
- Là dữ liệu chỉ đọc.
- Nội dung của nó được cập nhật thường xuyên theo cách thêm thông tin.
- Chứa các dữ liệu lịch sử và hiện tại để cung cấp các xu hướng thông tin.
- Chứa các bảng dữ liệu có kích thước lớn.
- Một câu hỏi thường trả về một tập kết quả liên quan đến toàn bộ bảng
và các liên kết nhiều bảng.
1.3.2. Cấu trúc của kho dữ liệu
Cấu trúc kho dữ liệu được xây dựng dựa trên hệ quản trị CSDL quan
hệ, có chức năng giống như một kho lưu trữ thông tin trung tâm. Trong đó, dữ
liệu tác nghiệp và phần xử lý được tách riêng khỏi quá trình xử lý kho dữ liệu.
Kho lưu trữ trung tâm được bao quanh bởi các thành phần được thiết kế để
làm cho kho dữ liệu có thể hoạt động, quản lý và truy nhập được từ người
dùng đầu cuối cũng như từ các nguồn dữ liệu [10].
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
8
Hệ thống phân
phối thông tin
Các công cụ hỏi
đáp, báo cáo
MetaData
Các công cụ
OLAP
Chiết xuất dữ liệu
Làm sạch dữ liệu
Nạp dữ liệu.
Data
Mart
Các công cụ
khai phá dữ
liệu
Kho dữ liệu
trong DBMS
Dữ liệu
nguồn
Các công cụ trợ giúp
và các ứng dụng
Hình 1.1. Cấu trúc kho dữ liệu
Như trên Hình 1.1 cho thấy, kho dữ liệu bao gồm 7 thành phần:
- Dữ liệu nguồn (là các ứng dụng tác nghiệp hoặc các kho dữ liệu tác
nghiệp) và các công cụ chiết xuất, làm sạch và chuyển đổi dữ liệu.
- Kho dữ liệu về dữ liệu (MetaData)
- Các kỹ thuật xây kho
- Kho dữ liệu thông minh hay dữ liệu theo chủ đề (Data marts): là nơi
các dữ liệu được khoanh vùng theo chủ đề đến một giới hạn nào đó và có thể
được thay đổi cho phù hợp với nhu cầu của từng bộ phận người dùng. Với các
kho dữ liệu này, cũng có thể xây dựng một kho dữ liệu theo cách tiếp cận
từng giai đoạn kế tiếp, nghĩa là với một tập hợp các kho dữ liệu thông minh,
ta tạo ra một kho dữ liệu; ngược lại, một kho dữ liệu có thể được phân tích
thành nhiều kho dữ liệu thông minh.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
9
- Các công cụ vấn đáp (query), báo cáo (reporting), phân tích trực tiếp
(OLAP) và khai phá dữ liệu (data mining). Đây chính là các cách khai thác
kho dữ liệu để đem lại những “tri thức” hơn là đem lại chính những dữ liệu
thô. Điểm mạnh và yếu của các kỹ thuật này ta sẽ phân tích kỹ hơn ở những
phần sau.
- Quản trị kho dữ liệu.
- Hệ thống phân phối thông tin.
1.3.3. Mục đích của việc xây dựng kho dữ liệu
Mục tiêu chính của kho dữ liệu nhằm đáp ứng các tiêu chuẩn cơ bản:
- Phải có khả năng đáp ứng mọi yêu cầu về thông tin của người sử dụng.
- 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, ví dự như: có những quyết định hợp lý, nhanh và bán được nhiều
hàng hơn, năng suất cao hơn, thu được lợi nhuận cao hơn,…
- Giúp cho tổ chức xác đinh, quản lý và điều hành các dự án, các nghiệp
vụ một các hiệu quả và chính xác.
- Tích hợp dữ liệu và siêu dữ liệu từ nhiều nguồn khác nhau.
Muốn đạt được những yêu cầu trên thì kho dữ liệu phải:
- Tăng chất lượng dữ liệu bằng các phương pháp làm sạch và tinh lọc.
- Tổng hợp và kết nối dữ liệu
- Đồng bộ hoá các nguồn dữ liệu với kho dữ liệu.
- Phân định và đồng nhất các hệ quản trị CSDL tác nghiệp như là các công
cụ chuẩn để phục vụ cho kho dữ liệu.
- Quản lí siêu dữ liệu (metadata)
- Cung cấp thông tin tích hợp, tóm tắt hoặc được liên kết, tổ chức theo các
chủ đề.
Một số lợi ích của việc xây dựng kho dữ liệu trong nhiều lĩnh vực có
thể kể đến như sau:
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
10
* Đối với quản lý nhà nước:
- Giúp các nhà lãnh đạo đưa ra những quyết định mang tính chiến lược
để phát triển kinh tế xã hội.
- Giúp người lãnh đạo quản lý, chỉ đạo một cách chính xác và kịp thời.
- Định hướng phát triển kinh tế xã hội mang tính chiến lược.
* Đối với doanh nghiệp:
- Lợi ích tiềm ẩn trong đầu tư.
- Lợi nhuận trong cạnh tranh.
- Tăng tính hiệu quả trong việc đưa ra quyết định đầu tư tài chính.
* Đối với nghiên cứu khoa học:
Tìm ra các quy luật tự nhiên, vật lý, sinh học, tội phạm học... từ những
dữ liệu thống kê, thu thập qua điều tra khảo sát.
* Đối với việc đào tạo và phát triển nguồn nhân lực:
- Tìm ra su hướng phát triển của tương lại
- Tìm ra nhu cầu của việc học tập, sở trường của từng học viên để có kế
hoạch, chiến lược bố trí giảng viên, tổ chức lớp học,...
- Định hướng đào tạo
Tuy nhiên kho dữ liệu mới chỉ là cách khai thác với kỹ thuật cao để đưa
ra các dữ liệu tinh và chính xác hơn chứ chưa đưa ra được dữ liệu “tri thức”.
Hơn nữa, kích thước quá lớn và tính chất phức tạp của kho dữ liệu làm cho nó
rất khó có thể được sử dụng cho những mục đích như đưa ra các giả tuyết từ
các thông tin mà chương trình ứng dụng cung cấp.
Trước đây, kỹ thuật học máy thường được sử dụng để tìm ra những giả
thuyết từ các thông tin dữ liệu thu thập được. Tuy nhiên, thực nghiệm cho
thấy chúng thể hiện khả năng rất kém khi áp dụng với các tập dữ liệu lớn
trong kho dữ liệu này. Phương pháp thống kê tuy ra đời đã lâu nhưng không
có gì cải tiến để phù hợp với sự phát triển của dữ liệu. Đây chính là lý do tại
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
11
sao một khối lượng lớn dữ liệu vẫn chưa được khai thác và thậm chí được lưu
trữ chủ yếu trong các kho dữ liệu không trực tuyến (off-line). Điều này tạo
nên một lỗ hổng lớn trong việc hỗ trợ phân tích và tìm hiểu dữ liệu, tạo ra
khoảng cách giữa việc tạo ra dữ liệu và việc khai thác các dữ liệu đó.Trong
khi đó, càng ngày người ta càng nhận thấy rằng, nếu được phân tích thông
minh thì dữ liệu sẽ là một nguồn tài nguyên quý giá trong cạnh tranh trên
thương trường.
Giới tin học đã đáp ứng lại những thách thức trong thực tiễn cũng như
trong nghiên cứu khoa học bằng cách đã đưa ra một phương pháp mới đáp
ứng cả nhu cầu trong khoa học cũng như trong hoạt động thực tiễn. Đó chính
là công nghệ Khai phá dữ liệu (data mining).
1.4. Khai phá dữ liệu
1.4.1. Khái niệm
Khai phá dữ liệu là một khái niệm ra đời vào những năn cuối của thập
kỷ 80. Nó bao hàm một loạt các kỹ thuật nhằm phát hiện ra các thông tin có
giá trị tiềm ẩn trong các tập dữ liệu lớn (các kho dữ liệu). Về bản chất, khai
phá dữ liệu liên quan đến việc phân tích các dữ liệu và sử dụng các kỹ thuật
để tìm ra các mẫu hình có tính chính quy (regularities) trong tập dữ liệu.
Năm 1989, Fayyad, Piatestsky-Shapiro và Smyth đã dùng khái niệm
Phát hiện tri thức trong cơ sở dữ liệu (Kownledge Discovery in Database KDD) để chỉ toàn bộ quá trình phát hiện các tri thức có ích từ các tập dữ liệu
lớn. Trong đó, khai phá dữ liệu là một bước đặc biệt trong toàn bộ quá trình,
sử dụng các giải thuật đặc biệt để chiết xuất ra các mẫu (pattern) (hay các mô
hình) từ dữ liệu.
1.4.2. Các bước của quá trình phát hiện tri thức (KDD)
Quy trình phát hiện tri thức thường tuân theo các bước sau: [4]
Bước thứ nhất: Hình thành và xác định bài toán. Bước này tìm hiểu
lĩnh vực ứng dụng từ đó hình thành bài toán, xác định các nhiệm vụ cần phải
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
12
hoàn thành. Điều này sẽ quyết định cho việc rút ra được các tri thức hữu ích
và cho phép chọn các phương pháp khai phá dữ liệu thích hợp với mục đích
ứng dụng và bản chất của dữ liệu
Bước thứ hai: Thu thập và tiền xử lý dữ liệu: Tiến hành thu thập và xử
lý thô, còn được gọi là tiền xử lý dữ liệu nhằm loại bỏ nhiễu (làm sạch dữ
liệu), xử lý việc thiếu dữ liệu (làm giàu dữ liệu), biến đổi dữ liệu và rút gọn
dữ liệu nếu cần thiết, bước này thường chiếm nhiều thời gian nhất trong toàn
bộ qui trình phát hiện tri thức do dữ liệu được lấy từ nhiều nguồn khác nhau,
không đồng nhất… có thể gây ra các nhầm lẫn. Sau bước này, dữ liệu sẽ nhất
quán, đầy đủ, được rút gọn và rời rạc hoá.
Hình thành và
Định nghĩa bài toán
Thu thập và
Tiền xử lý dữ liệu
Khai phá dữ liệu
Rút ra các tri thức
Phân tích và kiểm định
kết quả
Sử dụng các tri thức
phát hiện đƣợc
Hình 1.2. Quy trình phát hiện tri thức
Bước thứ ba: Khai phá dữ liệu, rút ra các tri thức: Trích ra các mẫu
hoặc/ và các mô hình ẩn dưới các dữ liệu. Giai đoạn này rất quan trọng, bao
gồm các công đoạn như: chức năng, nhiệm vụ và mục đích của khai phá dữ
liệu, dùng phương pháp khai phá nào? Thông thường, các bài toán khai phá
dữ liệu bao gồm: các bài toán mang tính mô tả - đưa ra tính chất chung nhất
của dữ liệu, các bài toán dự báo - bao gồm cả việc phát hiện các suy diễn dựa
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
13
trên dữ liệu hiện có. Tuỳ theo bài toán xác định được mà ta lựa chọn các
phương pháp khai phá dữ liệu cho phù hợp.
Bước thứ tư: Sử dụng các tri thức phát hiện được, đặc biệt là làm sáng
tỏ các mô tả và dự đoán.
Các bước trên có thể lặp đi lặp lại một số lần, kết quả thu được có thể
được lấy trung bình trên tất cả các lần thực hiện. Các kết quả của quá trình
phát hiện tri thức có thể được đưa và ứng dụng trong các lĩnh vực khác nhau.
Do các kết quả có thể là các dự đoán hoặc các mô tả nên chúng có thể được
đưa vào các hệ thống hỗ trợ ra quyết định nhằm tự động hoá quá trình này.
Tóm lại: KDD là một quá trình kết xuất ra tri thức từ kho dữ liệu mà
trong đó khai phá dữ liệu là công đoạn quan trọng nhất.
1.4.3. Một số phương pháp khai phá dữ liệu [4]
Khai phá dữ liệu là lĩnh vực mà con người luôn tìm cách đạt được mục
đích sử dụng thông tin của mình. Quá trình khai phá dữ liệu là quá trình phát
hiện mẫu, trong đó phương pháp khai phá dữ liệu để tìm kiếm các mẫu
đáng quan tâm theo dạng xác định. Có thể kể ra đây một vài phương pháp như:
Sử dụng công cụ truy vấn, xây dựng cây quyết định, dựa theo khoảng cách
(K-láng giềng gần), giá trị trung bình, phát hiện luật kết hợp,… Các phương
pháp trên có thể được phỏng theo và được tích hợp vào các hệ thống lai để
khai phá dữ liệu theo thống kê trong nhiều năm nghiên cứu. Tuy nhiên, với dữ
liệu rất lớn trong kho dữ liệu thì các phương pháp này cũng đối diện với thách
thức về mặt hiệu quả và quy mô.
1.4.3.1. Phương pháp suy diễn và quy nạp
Một cơ sở dữ liệu là một kho thông tin nhưng các thông tin quan trọng
hơn cũng có thể được suy diễn từ kho thông tin đó. Có hai kỹ thuật chính để
thực hiện việc này là suy diễn và quy nạp.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
- Xem thêm -