Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
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

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
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

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
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

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
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 -

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
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ý

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
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

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
8

Chiết xuất dữ liệu
Làm sạch dữ liệu
Nạp dữ liệu.

MetaData Kho dữ liệu
trong DBMS Data
Mart
Hệ thống phân
phối thông tin
Các công cụ hỏi
đáp, báo cáo
Các công cụ
OLAP
Các công cụ
khai phá dữ

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
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

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
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 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ữ

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
14
- Phương pháp suy diễn: Nhằm rút ra thông tin là kết quả logic của các
thông tin trong cơ sở dữ liệu. Ví dụ như toán tử liên kết áp dụng cho bảng
quan hệ, bảng đầu chứa thông tin về các nhân viên và phòng ban, bảng thứ hai
chứa các thông tin về các phòng ban và các trưởng phòng. Như vậy sẽ suy ra
được mối quan hệ giữa các nhân viên và các trưởng phòng. Phương pháp suy
diễn dựa trên các sự kiện chính xác để suy ra các tri thức mới từ các thông tin
cũ. Mẫu chiết xuất được bằng cách sử dụng phương pháp này thường là các
luật suy diễn. Với tập dữ liệu khách hàng vay vốn ở trên, ta có mẫu chiết xuất
được với ngưỡng thu nhập t là một luật như sau: “Nếu thu nhập của khách
hàng lớn hơn t đồng thì khách hàng có khả năng trả nợ”.
- Phương pháp quy nạp: phương pháp quy nạp suy ra các thông tin
được sinh ra từ cơ sở dữ liệu. Có nghĩa là nó tự tìm kiếm, tạo mẫu và sinh ra
tri thức chứ không phải bắt đầu với các tri thức đã biết trước. Các thông tin
mà phương pháp này đem lại là các thông tin hay các tri thức cấp cao diễn tả
về các đối tượng trong cơ sở dữ liệu. Phương pháp này liên quan đến việc tìm

Đối với quy mô lớn, người ta dựa trên các phương pháp đánh giá mô
hình theo xác suất với các mức độ mô hình phức tạp khác nhau. Các phương
pháp tìm kiếm “tham lam”, liên quan đến việc tăng và rút gọn các luật và các
cấu trúc cây, chủ yếu được sử dụng để khai thác không gian siêu mũ (super-
exponential space) của các mô hình. Cây và luật chủ yếu được sử dụng cho
việc mô hình hóa dự đoán, phân lớp (Apte & Hong; Fayyad, Djorgovski, &
Wei) và hồi quy. Chúng cũng có thể được áp dụng cho việc tóm tắt và mô
hình hóa các mô tả (Agrawal et al.).
Không cho
vay
Cho vay
Không cho
vay
Nợ < n
Nợ > n
Thu nhập < t
Thu nhập > t

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
16
1.4.3.3. Phân nhóm và phân đoạn
Kỹ thuật phân nhóm và phân đoạn là những kỹ thuật phân chia dữ liệu
sao cho mỗi phần hoặc mỗi nhóm giống nhau theo một tiêu chuẩn nào đó.
Mối quan hệ thành viên của các nhóm có thể dựa trên mức độ giống nhau của
các thành viên và từ đó xây dựng nên các luật ràng buộc giữa các thành viên
trong nhóm. Một kỹ thuật phân nhóm khác là xây dựng nên các hàm đánh giá
các thuộc tính của các thành phần như là hàm của các tham số của các thành
phần. Phương pháp này được gọi là phương pháp phân hoạch tối ưu (optimal
partitioning). Một ví dụ của phương pháp phân nhóm theo độ giống nhau là
cơ sở dữ liệu khách hàng, ứng dụng của phương pháp tối ưu ví dụ như phân

liệu. Hạn chế đó có thể được khắc phục bằng kỹ thuật cây quyết định.
1.4.3.5. Các phương pháp dựa trên mẫu [9]
Sử dụng các mẫu mô tả từ cơ sở dữ liệu để tạo nên một mô hình dự
đoán các mẫu mới bằng cách rút ra những thuộc tính tương tự như các mẫu đã
biết trong mô hình. Các kỹ thuật bao gồm phân lớp theo láng giềng gần nhất,
các giải thuật hồi quy (Dasarathy 1991) và các hệ thống suy diễn dựa trên tình
huống (case-based reasoning) (Kolodner 1993).
Khuyết điểm của các kỹ thuật này là cần phải xác định được khoảng
cách, độ đo giống nhau giữa các mẫu. Mô hình thường được đánh giá bằng
phương pháp đánh giá chéo trên các lỗi dự đoán (Weiss & Kulikowski, 1991).
“Tham số” của mô hình được đánh giá có thể bao gồm một số láng giềng
dùng để dự đoán và số đo khoảng cách. Giống như phương pháp hồi quy phi
tuyến, các phương pháp này khá mạnh trong việc đánh giá xấp xỉ các thuộc
tính, nhưng lại rất khó hiểu vì mô hình không được định dạng rõ ràng mà tiềm
ẩn trong dữ liệu.
1.4.3.6. Phát hiện các luật kết hợp
Phương pháp này nhằm phát hiện ra các luật kết hợp giữa các thành
phần dữ liệu trong cơ sở dữ liệu. Mẫu đầu ra của giải thuật khai phá dữ liệu là

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
18
tập luật kết hợp tìm được. Ta có thể lấy một ví dụ đơn giản về luật kết hợp
như sau: sự kết hợp giữa hai thành phần A và B có nghĩa là sự xuất hiện của
A trong bản ghi kéo theo sự xuất hiện của B trong cùng bản ghi đó: A  B.
Cho một lược đồ R={A
1
,…, A
p
} các thuộc tính với miền giá trị {0,1},
và một quan hệ r trên R. Một luật jết hợp trên r được mô tả dưới dạng XB