Số hóa bởi trung tâm học liệu
i
ĐẠ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
GS.TS Vũ Đức Thi. Xin bày tỏ lòng biết ơn chân thành và sâu sắc tới Thầy đã
quan tâm, nghiêm khắc và tạo mọi điều kiện để em có thể hoàn thành những
mục tiêu của đề tài.
Sau cùng, em xin kính chúc các Thầy Cô thật dồi dào sức khỏe, niềm
tin để tiếp tục thực hiện sứ mệnh cao đẹp của mình là truyền đạt kiến thức cho
thế hệ mai sau.
Em xin chân thành cảm ơn!
Thái Nguyên, ngày 15 tháng 9 năm 2013
Tác giả luận văn
Lê Thị Uyên
Số hóa bởi trung tâm học liệu
iii
MỤC LỤC
LỜI CAM ĐOAN i
LỜI CẢM ƠN ii
MỤC LỤC iii
DANH MỤC CÁC KÝ HIỆU VIẾT TẮT v
DANH MỤC HÌNH vi
CHƢƠNG 1: TỔNG QUAN 1
1.1. Khai phá dữ liệu 1
1.1.1. Kỹ thuật phân lớp dữ liệu 2
1.1.2. Một số kỹ thuật phân lớp phổ biến 2
1.1.3. Kỹ thuật phân nhóm dữ liệu 3
1.2. Khai phá luật quyết định 3
1.3. Lý thuyết tập thô 5
3.3. Đánh giá thuật toán 52
3.4. Kết luận chương 3 52
KẾT LUẬN 53
TÀI LIỆU THAM KHẢO 54 Số hóa bởi trung tâm học liệu
v
DANH MỤC CÁC KÝ HIỆU VIẾT TẮT
Ký hiệu
Ý nghĩa
BN
p
(X)
P – miền biên của X
P
X
P – Xấp xỉ trên của X
P
X
P – Xấp xỉ dưới của X
IND(P)
P – Quan hệ bất khả phân biệt
Sup(C
i
, D
j
)
Độ hỗ trợ của luật quyết định C
(t)
(C, D)
Ma trận Độ hỗ trợ tại thời điểm t của tất cả luật quyết
định C
i
D
j
Cov
(t)
(C, D)
Ma trận Độ phủ tại thời điểm t của tất cả luật quyết định
C
i
D
jSố hóa bởi trung tâm học liệu
vi
DANH MỤC HÌNH
Hình 2.1: Các bước cơ bản của thuật toán trích rút luật quyết định khi làm
thô/mịn các giá trị thuộc tính 26
Hình 3.1: Mối liên hệ giữa các lớp trong chương trình 41
Hình 3.2: Mối quan hệ các lớp trong DecisionRules 41
Hình 3.3: Mối quan hệ các lớp trong DecisionTable 41
Hình 3.4: Mối quan hệ các lớp trong SupportMatrix 42
Hình 3.5: Mối quan hệ trong lớp SqlHelper 43
Hình 3.6: Trong lớp Ultilities 43
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.
Số hóa bởi trung tâm học 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ữ
liệu và kỹ thuật phân nhóm dữ liệu.
1.1.1. Kỹ thuật phân lớp dữ liệu
Phân lớp dữ liệu là kỹ thuật nhằm xây dựng mô hình cho phép phân các
đối tượng vào lớp được biết trước nào đó. Kỹ thuật này phép dự đoán giá trị
bị thiếu của thuộc tính trong dữ liệu hay dự đoán giá trị của dữ liệu sẽ xuất
hiện trong tương lai. Phân lớp dữ liệu là kỹ thuật được xem là một trong
những kỹ thuật hay được dùng nhất trong học máy và khai phá dữ liệu.
Quá trình phân lớp dữ liệu được thực hiện qua hai bước. Thứ nhất dựa
vào tập hợp dữ liệu huấn luyện (các đối tượng dữ liệu đã được gán nhãn lớp)
để xây dựng một mô hình mô tả những đặc trưng của các lớp hoặc các khái
niệm tương ứng với lớp. Thứ hai dựa trên mô hình phân lớp dữ liệu hoặc mô
hình diễn giải và phân biệt các khái niệm đã được xác định để gán nhãn lớp
cho những đối tượng được quan tâm.
1.1.2. Một số kỹ thuật phân lớp phổ biến
Cây quyết định là một cấu trúc cây, trong đó mỗi nút trong của cây biểu
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.
Số hóa bởi trung tâm học liệu
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
tượng ra khỏi bảng dữ liệu dựa trên việc tính toán gia tăng ma trận độ chính xác
và ma trận độ phủ làm cơ sở để sinh các luật quyết định. Tuy nhiên nghiên cứu
này đã làm tiêu tốn nhiều thời gian tính và không gian bộ nhớ do phải cập nhật
và lưu trữ đối với cả ma trận độ phủ và ma trận độ chính xác.
Trong trường hợp thứ ba, tập các thuộc tính thay đổi đề nghị phương
pháp để cập nhật các xấp xỉ của khái niệm trong hệ thông tin không đầy đủ
dựa trên các quan hệ đặc trưng khi tập các thuộc tính thay đổi theo thời gian.
Ở trong nước, trong những năm gần đây đã có nhiều tác giả, nhóm tác
giả quan tâm, nghiên cứu, trình bày các giải pháp khác nhau nhằm giải quyết
có hiệu quả bài toán khai phá tri thức trên bảng dữ liệu động. Trong trường
hợp này, để sinh các luật kết hợp, thuật toán khai phá các luật kết hợp khi
bảng dữ liệu được gia tăng theo chiều dọc sẽ thực hiện việc phân hoạch dữ
liệu thành nhiều phần nhỏ tương ứng với các mục dữ liệu và lưu chúng ở bộ
nhớ ngoài, mỗi lần xử lý chỉ đưa một số tập phân hoạch vào bộ nhớ trong.
Đồng thời, cũng xem xét đến trường hợp bảng dữ liệu gia tăng theo chiều
1
a
1
a
3
U
a
1
A
2
a
3
x
1
1
1
1
x
7
2
2
2
x
2
1
2
1
x
8
2
3
3
x
6
2
2
1
x
12
3
3
3
Khi đó ta có:
Tập các đối tượng U = {x
1
, , x
12
}
Tập các thuộc tính A = {a1, a2, a
3
}
Số hóa bởi trung tâm học liệu
6
Tập các giá trị thuộc tính a A ta có V
a
= {1, 2, 3}
f(x
1
, a
được định nghĩa như sau:
[x]
p
= {y U: (x, y) IND(P)}
Từ định nghĩa này, chúng ta thấy rằng, hai đối tượng thuộc cùng một
lớp tương đương khi và chỉ khi chúng có giá trị giống nhau trên các thuộc tính
trong P. Do đó, để xác định các lớp tương đương, ta có thể sắp xếp các đối
tượng trong U theo một thứ tự tùy ý. Thông thường, chúng ta có thể sắp xếp
các đối tương theo thứ tự từ điển (trên các vector giá trị thuộc tính), ký hiệu là
<
p
. Trên cơ sở đó, ta có thể xác định các lớp tương đương bởi thuật toán sau:
Thuật toán 1.1 Xác định các lớp tương đương
Vào:
- Hệ thông tin IS = (U, A, V, f)
- Tập thuộc tính P A
Ra: Tập các lớp tương đương {X
1
p
,…, X
m
p
} của quan hệ IND(P)
a p
Số hóa bởi trung tâm học liệu
7
Phƣơng pháp:
Bước 1: Sắp xếp tập đối tượng trong U theo thứ tự từ điển <
p
p…
=
p
X
im
m
Trong đó 0 < m |U|, 0 < i
1
, … i
m
|U|, i
1
+ i
2
+ …+ i
m
= |U|
Bước 2: Đặt X
j
p
= {x
1
j
, x
2
j
, …, x
ij
j
1
1
X
7
2
2
2
x
2
1
2
1
X
8
2
3
3
x
3
1
2
1
X
9
2
3
3
x
4
1
, a
2
}, ta dễ dàng thu được một phân hoạch của U
được sinh bởi P là:
U/P = {{x
1
}, {x
2
, x
3
, x
4
, x
5
}, {x
6
, x
7
}, {x
8
, x
9
, x
10
}, {x
11
, x
12
}}
Định nghĩa 1.2
50
Yes
x
2
16 – 30
0
No
x
3
31 – 45
1 – 25
No
x
4
31 – 45
1 – 25
yes
x
5
45 – 60
26 – 49
No
x
6
16 – 30
26 – 49
Yes
x
7
46 – 60
, x
6
, x
7
}}
- Quan hệ bất khả phân biệt theo tuổi và số buổi là:
IND({Tuổi, số buổi})={{x
1
},{x
2
},{x
3
, x
4
},{x
5
, x
7
},{x
6
}};
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á
P
X được gọi là vùng P – biên của X, chứa các
đối tượng không thể phân lớp chắc chắn vào X theo P.
Tập U -
P
X được gọi là vùng P – ngoài của X, chứa các đối tượng
chắn chắn được phân lớp không thuộc về X.
Một tập được gọi là thô (rough) nếu vùng biên của nó khác rỗng, ngược
lại tập là rõ (crisp). Nghĩa là nếu BN
p
(X) = (tức
P
X -
P
X) thì X được gọi
là tập rõ, ngược lại nếu BN
p
(X) X được gọi là tập thô.
Dựa vào ý nghĩa các xấp xỉ dưới và xấp xỉ trên, ta định nghĩa bốn lớp
cơ bản của tập thô tương ứng với bốn mức độ mơ hồ như sau:
(1) X được gọi là P – định nghĩa được một cách thô nếu và chỉ nếu
P
X và
P
X U.
(2) X được gọi là P – không định nghĩa được một cách nội vi nếu và chỉ
nếu
P
X = và
P
XX
p
j
P
J
X
P
X = {x U: [x]
p
X } =
XX
p
j
P
J
X
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:
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:
P
(X) X
P
J
;
End;
Số hóa bởi trung tâm học liệu
11
Kết thúc
Dễ thấy, thuật toán 1.2 có độ phức tạp là O(K
U
log
U
), trong đó
P
A
=k
Ví dụ 1.3 Xét hệ thông tin trong bảng sau:
U
a
1
A
2
a
3
U
a
1
a
2
3
3
x
4
1
2
1
x
10
2
3
3
x
5
1
2
2
x
11
3
3
3
x
6
2
2
1
x
12
2
= {x
2
, x
3
, x
4
}, X
P
3
= {x
5
},
X
P
4
= {x
6
}. Suy ra:
P
X = X
P
3
= {x
5
};
P
(X) = {X
P
2
0
No
x
3
31 - 45
1 – 25
No
x
4
31 – 45
1 – 25
yes
x
5
45 – 60
26 – 49
No
x
6
16 – 30
26 – 49
Yes
x
7
46 – 60
26 – 49
No
Số hóa bởi trung tâm học liệu
12
};
P
(X) = {x
1
, x
3
, x
4
, x
6
}; PN
A
(X) = {x
3
, x
4
}, Ta
có: U/
P
(X) = {x
2
, x
5
, x
7
}
Như vậy lớp quyết định Thi_đậu là thô vì vùng biên khác rỗng. Một số tính chất của xấp xỉ tập hợp:
X
P
Y,
P
X
P
Y
6.
P
(X Y)
P
X
P
Y
7.
P
(X Y)
P
X
P
Y
8.
P
(U-X) = U -
P
X
yes
yes/no
no
{{x
(
P
X) =
P
(
P
X) = (
P
X)
11.
P
(
P
X) =
P
(
P
X) = (
P
X)
* Độ chính xác của tập thô:
Với
+ Nếu X là rõ so với P.
+ Nếu X là thô 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
Số hóa bởi trung tâm học liệu
14
D, trong đó C là tập các thuộc tính điều kiện, D là tập các thuộc tính quyết
định sao cho C D = , C D = A.
Bảng quyết định được ký hiệu là: DS = (U, C D, V, f) hoặc DS =
(U, C D)
Giả sử U/C = {C
1
, C
2
, , C
m
} và U/j gọi D = {D
1
,
D
2
, , D
n
} tương
ứng là các phân hoạch được sinh bởi tập các thuộc tính điều kiện C và tập các
thuộc tính quyết định D, i = 1, , m; j = 1, , n thì C
i
, D
j
tương ứng được
gọi là các lớp tương đương điều kiện và các lớp tương đương quyết định.
Một lớp tương đương điều kiện C
i
1
0
x
7
2
2
2
2
x
2
1
2
1
0
x
8
2
3
3
2
x
3
1
2
1
0
x
9
2
3
1
1
x
12
3
3
3
3
Trong đó C = {a
1
, a
2
, a
3
}, 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 = {C
1
, C
2
, , C
7
} với C
1
= {x
1
}, C
2
= {x
, x
12
};
U/D = {D
1
, D
2
, D
3
, D
4
} với D
1
= {x
1
, x
2
, x
3
, x
4
}, D
2
= {x
5
, x
6
},
Số hóa bởi trung tâm học liệu
trong bảng quyết định này:
Y : Điều kiện thỏa mãn
N :Điều kiện không thỏa mãn
- : Điều kiện hoặc hành động không áp dụng
X : Hành động được thực hiện
Ví dụ 1.6: Một ngân hàng sử dụng các nguyên tắc sau đây để phân loại
tài khoản ngân hàng mới mở:
a) Nếu người gửi tiền có tuổi >=21 và số tiền gửi >=100 thì đó là
TK loại A
b) Nếu người gửi tiền có tuổi <21 số tiền gửi >=100 thì đó là TK loại B
c) Nếu người gửi tiền có tuổi >=21 và số tiền gửi <100 thì đó là
TK loại C
d) Nếu người gửi tiền có tuổi <21 số tiền gửi <100 thì không mở
tài khoản
Số hóa bởi trung tâm học liệu
16
Để giải quyết bài toán này, nhân viên ngân hàng xây dựng bảng quyết
định như sau:
- Xác định các điều kiện: Có 2 điều kiện
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
Rule 1
Rule 2
-
-
-
A
2
:
Classify as B
-
X
-
-
A
3
: Classify as C
-
-
X
-
A
4
: Do not open
Account
-
-
-
X
1.3.7. Luật quyết định
j
, ký hiệu là des(X
i
), des(Y
j
) lần lượt là các mô
tả của các lớp tương đương ứng với X
i
, Y
j
. Một luật quyết định được xác định
bởi X
i
, Y
j
có dạng: Z
ij
: des(X
i
) des(Y
j
), ở đây X
i
U/C, Y
j
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ử X
i
j
) =
Yj
YjXi
Ở đây |.| là bản số hay lực lượng của một tập hợp. Hiển nhiên, ta có:
0 acc(X
i
, Y
j
) 1 và
n
j
acc
1
(X
i
, Y
j
) = 1
0 cov(X
i
, Y
j
) 1 và
m
i 1
cov
(X
i
j
và nếu Cov(X
i
, Y
j
) = 1 thì X
i
C
Y
j
.
Điều này có ý nghĩa là độ đo chính xác và độ đo độ phủ của luật còn có thể
được sử dụng để đo mức độ của xấp xỉ dưới và xấp xỉ trên của một khái niệm.
Định nghĩa 1.6: Cho bảng quyết định DS = (U, C D), X
i
U/C,
Y
j
U/D tương ứng là các lớp tương đương điều kiện, các lớp tương đương
quyết định được sinh bởi C, D, X
i
Y
j
là một luật quyết định trong
DS(i=1,…,m; j=1,…,n).
Nếu Acc(X
i
, Y
j
i
Y
j
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ố
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.
Copyright: Tài liệu đại học ©