ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG

LÊ THỊ UYÊN

KHAI PHÁ LUẬT QUYẾT ĐỊNH TRÊN BẢNG DỮ
LIỆU CÓ THUỘC TÍNH THAY ĐỔI
Chuyên ngành: Khoa học máy tính
Mã số: 60.48.01.01

LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH

Người hướng dẫn khoa học: GS.TS VŨ ĐỨC THI

THÁI NGUYÊN - 2013


i

LỜI CAM ĐOAN
Tôi xin cam đoan rằng đây là công trình nghiên cứu của tôi, có sự hỗ
trợ từ Giáo viên hướng dẫn là GS.TS Vũ Đức Thi. Các nội dung nghiên cứu
và kết quả trong đề tài này là trung thực và chưa từng được ai công bố trong
bất cứ công trình nghiên cứu nào trước đây. Những số liệu trong các bảng
biểu phục vụ cho việc phân tích, nhận xét, đánh giá được chính tác giả thu
thập từ các nguồn khác nhau có ghi trong phần tài liệu tham khảo. Ngoài ra,
đề tài còn sử dụng một số nhận xét, đánh giá cũng như số liệu của các tác giả,
cơ quan tổ chức khác, và cũng được thể hiện trong phần tài liệu tham khảo.
Nếu sai tôi xin hoàn toàn chịu trách nhiệm.
Thái Nguyên, ngày 15 tháng 9 năm 2013
Tác giả luận văn

DANH MỤC CÁC KÝ HIỆU VIẾT TẮT
Ký hiệu

Ý nghĩa

BNp(X)

P – miền biên của X

PX

P – Xấp xỉ trên của X

PX

P – Xấp xỉ dưới của X

IND(P)

P – Quan hệ bất khả phân biệt

Sup(Ci, Dj)

Độ hỗ trợ của luật quyết định Ci → Dj

Cov(Ci, Dj)

Độ phủ của luật quyết định Ci → Dj

Acc(Ci, Dj)

trọng riêng. Khai phá dữ liệu (DM) là một pha quan trọng trong toàn bộ tiến
trình khai phá tri thức, sử dụng các thuật toán đặc biệt để chiết xuất các mẫu
từ dữ liệu. Về bản chất đây là giai đoạn duy nhất để rút trích và tìm ra được
các mẫu, các mô hình, các tri thức tiềm ẩn có trong cơ sở dữ liệu phục vụ cho
việc mô tả và dự đoán.
Quá trình khai phá dữ liệu trải qua ba bước:
Bước một: Lọc dữ liệu (giai đoạn tiền xử lý). Khi dữ liệu được thu thập
từ nhiều nguồn khác nhau, nên sẽ có những sự sai sót, dư thừa và trùng lặp.
Lọc dữ liệu nhằm loại bỏ những dư thừa để có được dữ liệu ở định dạng
thống nhất. Dữ liệu sau khi lọc và chỉnh sửa sẽ gọn hơn, do vậy có thể xử lý
nhanh chóng hơn.
Ví dụ, trong bài toán tìm quy luật mua hàng của khách hàng trong một
siêu thị, ta cần phải xem khách hàng thường cùng mua những mặt hàng nào,
dựa trên đó ta sẽ sắp xếp những món hàng để thuận tiện cho việc mua hàng
của khách hàng. Từ dữ liệu nguồn do siêu thị cung cấp, có thể có nhiều thuộc
tính không cần thiết cho khai phá dữ liệu như: Mã khách hàng, nhà cung cấp,
đơn giá hàng, người bán hàng, … Các dữ liệu này cần cho quản lý bán hàng
nhưng không cần cho khai phá dữ liệu, vì vậy có thể loại bỏ các thuộc tính
này trước khi tiến hành công việc khai phá dữ liệu.
Bước hai: Khai phá dữ liệu (là công việc chính) sử dụng các thuật toán
khác nhau để khai phá các tri thức tiềm ẩn trong dữ liệu.


2
Bước ba (giai đoạn hậu xử lý) là quá trình đánh giá kết quả khai phá
theo yêu cầu của người dùng. Các kỹ thuật khai phá dữ liệu khác nhau được
đánh giá theo các quy tắc, trong số các kết quả thỏa mãn yêu cầu đánh giá,
giữ lại kết quả phù hợp nhất với yêu cầu của người sử dụng.
Có nhiều kỹ thuật khai phá dữ liệu được nghiên cứu, trong đó có hai kỹ
thuật được các nhà nghiên cứu sử dụng nhiều nhất là: Kỹ thuật phân lớp dữ

Các đối tượng trong một lớp tương đồng nhau, nhưng độ tương đồng của
chúng phải lớn hơn độ tương đồng với các đối tượng trong các lớp khác.
Trong phân nhóm, không đòi hỏi biết được số lớp cần cấu tạo ra. Mặt khác,
với kỹ thuật này, các đối tượng được nhóm lại trong cùng một lớp dựa vào sự
giống nhau của chúng, được xác định bởi những đặc trưng giống nhau. Thông
thường, người ta sử dụng sự giống nhau định lượng dưới dạng khoảng cách.
Độ đo giống nhau có thể xác định dựa trên ý kiến chuyên gia trong lĩnh vực.
1.2. Khai phá luật quyết định
Khai phá các luật quyết định là quá trình xác định những luật quyết
định trên bảng quyết định cho trước, phục vụ cho việc phân lớp của các đối
tượng mới. Khai phá luật quyết định đã được nhiều chuyên gia trong và ngoài
nước quan tâm trên cả hai phương diện lý thuyết và ứng dụng, các nghiên cứu
này chủ yếu xem xét trên các bảng dữ liệu tĩnh.
Trong thực tế, dữ liệu thường xuyên thay đổi theo thời gian. Đã có một
số nghiên cứu về các khía cạnh khác nhau để cập nhật tri thức trên các bảng
dữ liệu động, tập trung chủ yếu vào ba trường hợp sau đây:
+ Tập các giá trị thuộc tính thay đổi trong khi tập các đối tượng và tập
các thuộc tính không đổi.
+ Tập các đối tượng thay đổi trong khi tập các thuộc tính và tập các giá
trị thuộc tính không đổi.


4
+ Tập các thuộc tính thay đổi trong khi tập các đối tượng và tập các giá
trị thuộc tính không đổi.
Trong trường hợp thứ nhất, chưa đề cập đến vấn đề cập nhật các xấp xỉ
với nhiều lớp quyết định, đồng thời vấn đề làm thế nào để sinh các luật quyết
định cũng chưa được xem xét.
Trong trường hợp thứ hai, Năm 2009 một người tên Liu đã trình bày mô
hình và thuật toán để phát hiện các luật quyết định khi bổ sung và loại bỏ đối

thông tin. Một cách hình thức ta có thể định nghĩa hệ thông tin như sau:
Hệ thông tin là một bộ bốn IS = (U, A, V, f ) trong đó U là tập hữu hạn,
khác rỗng các đối tượng gọi là tập vũ trụ, A là tập hữu hạn khác rỗng các
thuộc tính. V là tập các giá trị thuộc tính, f: U × A → V là hàm thông tin sao
cho ∀ x ∈ U, ∀ a ∈ A Ta có f(x,a) ∈ Va (là tập giá trị của thuộc tính a).
Ta gọi f(x,a) là giá trị của đối tượng x trên thuộc tính a, tập X ≠ Φ , X
⊆ U gọi là một khái niệm trong IS.

Nếu V chứa giá trị thiếu ở ít nhất một thuộc tính a

∈A

thì hệ thông tin

IS được gọi là hệ thông tin không đầy đủ. Trái lại, IS gọi là hệ thông tin đầy
đủ hay đơn giản gọi là hệ thông tin.
Ví dụ 1.1: Cho hệ thông tin được biểu diễn trong bảng sau:
U
x1
x2
x3
x4
x5
x6
Khi đó ta có:

a1
1
1
1

2
2
2
3
3

A2
2
3
3
3
3
3

a3
2
3
3
3
3
3

Tập các đối tượng U = {x1, ...., x12}
Tập các thuộc tính A = {a1, a2, a3}
Tập các giá trị thuộc tính ∀ a ∈ A ta có Va = {1, 2, 3}
f(x1, a1) = 1; f(x2, a2) = 2.. tương ứng là các giá trị của các đối tượng x 1,
x2 trên các thuộc tính a1, a2,...
1.3.2. Quan hệ bất khả phân biệt




7
Bước 2: Đặt Xjp = {x1j, x2j, …, xijj} ở đó j = 1, 2, …, m. Khi đó, các tập
X1p, …, Xmp là các lớp tương đương của quan hệ IND(P)
Kết thúc:
Vì thuật toán sắp xếp các đối tượng trên một thuộc tính có độ phức tạp
O(|U|log|U|), khi đó với |P| ≤ |A| = k thì thuật toán 1.1 có độ phức tạp là O(k|
U|log|U|).
Ví dụ 1.2: Xét hệ thông tin cho ở bảng sau:
U
x1
x2
x3
x4
x5
x6

a1
1
1
1
1
1
2

A2
1
2
2
2

3
3
3
3

a3
2
3
3
3
3
3

Giả sử, chọn P = {a1, a2}, ta dễ dàng thu được một phân hoạch của U
được sinh bởi P là:
U/P = {{x1}, {x2, x3, x4, x5}, {x6, x7}, {x8, x9, x10}, {x11, x12}}
Định nghĩa 1.2

Cho hệ thông tin IS = (U, A, V, f), P, Q ⊆ A là tập các thuộc tính, U/P

= {P1, …, Pm}, U/Q = {Q1, …, Qn} là các phân hoạch được sinh bởi P, Q, ta
nói Q thô hơn P hoặc mịn hơn Q khi và chỉ khi ∀ Pi ∈ U/P, ∃ Qj ∈ U/Q (i=
1, ..., m; j = 1, …, n) sao cho Pi ⊆ Qj
Ví dụ về Quan hệ bất khả phân biệt:

x1
x2
x3
x4
x5


8

- Quan hệ bất khả phân biệt theo tuổi là:
IND({Tuổi})= {{x1, x2, x6},{x3, x4},{x5, x7};
- Quan hệ bất khả phân biệt theo số buổi là:
IND({số buổi})={{x1},{x2},{x3, x4},{x5, x6, x7}}
- Quan hệ bất khả phân biệt theo tuổi và số buổi là:
IND({Tuổi, số buổi})={{x1},{x2},{x3, x4},{x5, x7},{x6}};
1.3.3. Xấp xỉ tập hợp
Trong lý thuyết tập thô, bất cứ khái niệm không rõ ràng nào đều được
thay bằng một cặp khái niệm không chính xác gọi là xấp xỉ dưới và xấp xỉ
trên của khái niệm không rõ ràng. Xấp xỉ dưới gồm tất cả các đối tượng chắc
chắn thuộc về khái niệm, xấp xỉ trên bao gồm tất cả các đối tượng có thể
thuộc về khái niệm.
* Mục đích:
- Chỉ ra được khách hàng nào có thuộc tính quyết định có giá trị dương.
- Chỉ ra được khách hàng nào có thuộc tính quyết định không có giá
trị dương.
- Những khách hàng nào thuộc vào vùng biên giữa các trường hợp
chắc chắn.
1.3.4. Ứng dụng của tập thô (reduct)
+ Dùng để khắc phục hiện tượng dữ liệu dùng để KPDL bị nhiễu
+ Rút gọn dữ liệu (khử dữ liệu thừa)
+ Tạo luật quyết định
+ Nhận diện phụ thuộc riêng phần và toàn phần của các thuộc tính
Các khái niệm này được định nghĩa cụ thể như sau:
Định nghĩa 1.3: Cho hệ thông tin IS = (U, A, V, f), P ⊆ A là tập các
thuộc tính, X ⊆ U là tập các đối tượng, khi đó các tập P X = {x ∈ U: [ x ] p ⊆




X jp

X JP ⊆ X

P X = {x ∈ U: [x]p ∩ X ≠ φ } =



X JP ∩ X

X jp
≠φ

Trên cơ sở đó, chúng ta có thể tính P – xấp xỉ dưới và P – xấp xỉ trên
của X bởi thuật toán sau đây:


10
Thuật toán 1.2: Xác định xấp xỉ dưới, xấp xỉ trên
Vào:
Hệ thông tin IS = (U, A, V, f)
Tập thuộc tính P ⊆ A
Tập đối tượng X ⊆ U.
Ra:
P – xấp xỉ dưới và P – xấp xỉ trên của X.
Phương pháp:
Bước 1: Xác định các lớp tương đương X 1P , ..., X mP của quan hệ
IND(P);

2
2
2
2

a3
1
1
1
1
2
1

U
x7
x8
x9
x10
x11
x12

a1
2
2
2
2
3
3

Giả sử, chọn P = {a1, a2, a3}, X = {x3, x4, x5}

x2
16 – 30
0
No
x3
31 - 45
1 – 25
No
x4
31 – 45
1 – 25
yes
x5
45 – 60
26 – 49
No
x6
16 – 30
26 – 49
Yes
x7
46 – 60
26 – 49
No
Gọi tập các đối tượng X = {x|thi đậu(x) = Yes}  X = {x1, x4, x6} và P
= {Độ tuổi, số buổi}
Quan hệ bất khả phân biệt theo Độ tuổi và số buổi là:
IND({Độ_tuổi, số_buổi}) = {{x1}; {x2}; {x3,x4}; {x5; x7}; {x6}}
Suy ra: P X = {x1, x6}; P (X) = {x1, x3, x4, x6}; PNA(X) = {x3, x4}, Ta
có: U/ P (X) = {x2, x5, x7}

11. P ( P X) = P ( P X) = ( P X)
* Độ chính xác của tập thô:
αP (X ) =

| P( X ) |
| P( X ) |

Với

0 ≤ α P ≤ 1.

+ Nếu

α P ( X ) = 1,

+ Nếu

α P ( X ) < 1, X là thô so với P.

X là rõ so với P.

1.3.5. Bảng quyết định
Bảng quyết định (Decision Table) là công cụ hỗ trợ ra quyết định khi
có nhiều lựa chọn được đưa ra và có nhiều điều kiện tác động lên lựa chọn.
Bảng quyết định được sử dụng phổ biến trong rất nhiều lĩnh vực như phân
tích kinh doanh, quản lý, chăm sóc khách hàng… bởi tính đơn giản và hiệu
quả. Một bảng quyết định gồm 4 phần như sau:
Condition statements
Action statements


U
x1
x2
x3
x4
x5
x6

a1
1
1
1
1
1
2

A2
1
2
2
2
2
2

A3
1
1
1
1
2

3
3
3

a3
2
3
3
3
3
3

d
2
2
2
2
3
3


14
Trong đó C = {a1, a2, a3}, D = {d} tương ứng là tập các thuộc tính điều
kiện và tập các thuộc tính quyết định.
Ta có: U/C = {C1, C2, ..., C7} với C1 = {x1}, C2 = {x2, x3, x4}, C3 = {x5},
C4 = {x6}, C5 = {x7}, C6 = {x8, x9, x10}, C7 = {x11, x12};
U/D = {D1, D2, D3, D4} với D1 = {x1, x2, x3, x4}, D2 = {x5, x6},
D3 = {x7, x8, x9, x10}, D4 = {x11, x12}. Khi đó, ta dễ dàng thấy rằng bảng
quyết định (hay viết tắt DS) là bảng quyết định nhất quán.
1.3.6. Các bước để xây dựng bảng quyết định

C1: Age>=21
C2: Deposit>=100
- Xác định hành động:
+ Phân loại các tài khoản mới mở là A,B,C hoặc không mở TK
+ Xác định các kết hợp (Rules): Có 2 điều kiện và mỗi điều kiện có 2
giá trị (Y/N) nên có tất cả là 4 kết hợp.
- Ta có bảng quyết định như sau:
CONDITIONS
C1: Age>=21
C2: Deposit>=100

Rule 1
Y
Y

Rule 2
N
Y

Rule 3
Y
N

Rule 4
N
N

ACTIONS
A1: Classify as A
A2: Classify as B

thường được biểu diễn dưới dạng các luật kết hợp. Độ hỗ trợ và độ tin cậy


16
là hai độ đo mức độ quan tâm của luật và tương ứng, chúng phản ánh tính
hữu ích và tính chắc chắn của các luật đã được khám phá. Các luật kết
hợp được xem là luật có ý nghĩa nếu chúng thỏa mãn đồng thời cả ngưỡng
độ hỗ trợ tối thiểu và ngưỡng độ tin cậy tối thiểu. Các ngưỡng như vậy có
thể được thiết lập bởi người sử dụng hoặc các chuyên gia. Mặt khác, độ
chính xác và độ phủ được sử dụng để đánh giá mức độ đầy đủ và cần thiết
của luật.
Định nghĩa 1.4: Cho bảng quyết định DS = (U, C ∪ D), giả sử U/C =
{X1, X2,…, Xm} và U/D = {Y1, Y2, …, Yn} tương ứng là các phân hoạch được
sinh bởi C, D. Nếu X i ∩ Yj ≠ φ , ký hiệu là des(Xi), des(Yj) lần lượt là các mô
tả của các lớp tương đương ứng với X i, Yj. Một luật quyết định được xác định
bởi Xi , Yj có dạng: Zij: des(Xi) → des(Yj), ở đây Xi ∈ U/C, Yj ∈ U/D, (i = 1,
….,m; j = 1, …., n).
Định nghĩa 1.5: Cho bảng quyết định DS = (U, C ∪ D). Giả sử Xi ∈
U/C, Yj ∈ U/D (i = 1,…, m; j = 1, …, n) tương ứng là các lớp tương đương
điều kiện và các lớp tương đương quyết định được sinh bởi C, D. Độ hỗ trợ,
độ chính xác và độ phủ của luật quyết định des(X i) → des(Yj) tương ứng
được định nghĩa như sau:
Độ hỗ trợ (support): sup(Xi, Yj) = |Xi ∩ Yj|
Xi ∩ Yj

Độ chính xác (Accuracy): acc(Xi, Yj) =
Độ phủ (Coverage): Cov(Xi, Yj) =

Xi


định được sinh bởi C, D, X i → Yj là một luật quyết định trong DS(i=1,…,m;
j=1,…,n).
Nếu Acc(X i, Yj) = 1 thì X i → Yj được gọi là luật quyết định chắc
chắn; Nếu 0 < Acc(X i, Yj) < 1 thì X i → Yj được gọi là luật quyết định
không chắc chắn.
Định nghĩa 1.7: Giả sử X i ∈ U/C; Yj ∈ U/D (i = 1,..., m; j = 1,...,n)
tương ứng là các lớp tương đương điều kiện và các lớp tương đương quyết
định, nếu Acc(X i, Yj) ≥ α và Cov(X i, Yj) ≥ γ thì ta gọi luật X i → Yj là luật
quyết định có ý nghĩa, trong đó α , γ là hai ngưỡng cho trước, với α , γ ∈
(0,1).
Nói chung, ta thường chọn luật quyết định có độ chính xác và độ phủ
cao, điều này cũng giống như việc chọn các ngưỡng độ hỗ trợ và ngưỡng độ
tin cậy trong khai phá các luật kết hợp.
Hiển nhiên, với các ngưỡng độ chính xác và độ phủ khác nhau, số
lượng luật quyết định có ý nghĩa nhận được sẽ khác nhau. Dễ thấy, số


18
lượng các luật quyết định có ý nghĩa sẽ ít đi khi ta tăng giá trị của α , γ và
ngược lại.
1.4. So sánh kỹ thuật phân lớp dựa trên luật kết hợp và phân lớp dựa
trên luật tập thô
- Kỹ thuật phân lớp dựa trên luật kết hợp được phát triển trên cơ sở sửa
đổi thuật toán khai phá luật kết hợp Apriori. Bao gồm:
+ Thứ nhất: Sinh tập mục thường xuyên, thực hiện việc phát hiện tất cả
các tập mục có chứa thuộc tính tương ứng với thuộc tính mục tiêu. Giả sử D
là tập dữ liệu huấn luyện với thuộc tính mục tiêu Z. Thì kỹ thuật phân lớp dựa
trên luật kết hợp sẽ sinh một danh sách các ứng viên C k (tất cả các ứng viên
trong Ck phải thỏa mãn ngưỡng độ hỗ trợ tối thiểu cho trước).
+ Thứ hai: Sinh luật, thực hiện việc kiểm tra mục cuối cùng của các tập