Nghiên cứu ứng dụng lý thuyết tập thô trong trích chọn dữ liệu

LINK DOWNLOAD MIỄN PHÍ TÀI LIỆU "Nghiên cứu ứng dụng lý thuyết tập thô trong trích chọn dữ liệu": http://123doc.vn/document/1040707-nghien-cuu-ung-dung-ly-thuyet-tap-tho-trong-trich-chon-du-lieu.htm

-3-

1.1.3. Các nhiệm vụ của phát hiện tri thức và khai phá
dữ liệu
- Phát triển sự hiểu biết của miền ứng dụng
- Tạo dữ liệu mục tiêu (dữ liệu đầu ra)
- Làm sạch dữ liệu tiền xử lý
- Rút gọn dữ liệu và dự báo
- Chọn nhiệm vụ khai phá dữ liệu
- Chọn phương pháp khai phá dữ liệu
- Khai phá dữ liệu để trích xuất các mẫu/mô hình
- Giải thích và đánh giá các mẫu/mô hình
1.1.4. Các thách thức của phát hiện tri thức
- Các cơ sở dữ liệu lớn.
- Dữ liệu nhiều chiều.
- Hiện tượng quá phù hợp (over – fitting).
- Đánh giá ý nghĩa thống kê.
- Dữ liệu động.
- Dữ liệu thiếu và nhiễu.
- Các quan hệ phức tạp giữa các trường.
- Khả năng biểu đạt của mẫu.
- Sự tương tác với người dùng và tri thức có sẵn.
- Tích hợp với các hệ thống khác.
1.2. Các phương pháp trích chọn dữ liệu
Để minh họa cho quá trình trích chọn dữ liệu tôi xin trình bày
ví dụ sau: Một tập dữ liệu hai chiều gồm 23 điểm mẫu. Mỗi điểm
biểu thị cho một khách hàng, trục hoành biểu thị thu nhập, trục tung
biểu thị tổng dư nợ. Dữ liệu được chia thành hai lớp: dấu x biểu thị
cho khách hàng bị vỡ nợ, dấu 0 biểu thị cho khách hàng có khả năng
trả nợ. “Nếu thu nhập < t đồng thì khách hàng vay sẽ bị vỡ nợ” như
mô tả hình 1.2.







S
ẽ vỡ nợ




 









0
0
0
0
0
0
0
0
0
0
0
0
Có kh
ả năng trả nợ

0
Thu nh
ập

N
ợ

Hình 1.2. Tập dữ liệu hai chiều
t
-4-

1.2.1. Cây quyết định
Cây quyết định mô tả tri thức dạng đơn giản nhằm phân loại
các đối tượng dữ liệu thành một số lớp nhất định. Các nút của cây
được gán nhãn là tên các thuộc tính, các cạnh được gán các giá trị có
thể của các thuộc tính, các lá mô tả các lớp khác nhau. Các đối tượng
được phân lớp theo các đường đi trên cây, qua các cạnh tương ứng
với các giá trị của thuộc tính của đối tượng tới lá.










Hình 1.3 mô tả một mẫu đầu ra có thể của quá trình khai phá
dữ liệu dùng phương pháp cây quyết định với tập dữ liệu khách hàng
xin vay vốn.
1.2.2. Phân cụm (Clustering)
Phân cụm hay nhóm là việc tìm ra các nhóm trong dữ liệu. Các
phương pháp phân cụm có thể phân thành hai loại:
- Phân cụm có thứ bậc: Mỗi điểm trong dữ liệu được xem như
một cụm riêng biệt được kết hợp một cách liên tiếp dựa vào các quan
hệ của nó với các dạng khác.
- Các phương pháp tối ưu hóa dựa trên hàm đối tượng: các
phương pháp này sử dụng một chỉ số hiệu năng để giúp cho việc phát
triển các phân chia tốt của các điểm dữ liệu.
1.2.3. Hồi quy (Regression)
Hồi quy là việc học một hàm ánh xạ từ một mẫu dữ liệu thành
một biến dự đoán có giá trị thực.
Hình 1.4 mô tả mẫu kết quả dự đoán tổng dư nợ của khách
hàng với phương pháp khai phá dữ liệu là hồi quy. Đường hồi quy
tuyến tính cho thấy rằng những khách hàng có thu nhập càng cao thì
tổng dư nợ càng lớn. Mẫu kết quả này không phù hợp với quy luật.

N
ợ <n

N
ợ >
=
n

Không cho vay
Không cho vay Cho vay
Thu nhập < t Thu nhập >= t
Hình 1.3
. Cây
quy
ết định

-5-










1.2.4. Mạng nơron (neural networks)
Mạng nơron là tiếp cận tính toán mới liên quan đến việc phát
triển các cấu trúc toán học với khả năng học. Phương pháp là kết quả
của việc nghiên cứu mô hình học của hệ thống thần kinh con người.
Một trong số những ưu điểm phải kể đến của mạng nơron là
khả năng tạo ra các mô hình dự đoán có độ chính xác cao, có thể áp
dụng được cho rất nhiều loại bài toán khác nhau, đáp ứng được
nhiệm vụ đặt ra của khai phá dữ liệu như phân loại, phân nhóm, mô
hình hóa, dự báo các sự kiện phụ thuộc vào thời gian, v.v…





1.2.5. Lý thuyết tập thô
Tập thô có quan điểm hoàn toàn khác với quan điểm truyền
thống về tập hợp, trong đó mọi tập hợp đều được định nghĩa duy nhất
bởi các phần tử của nó mà không cần biết bất kỳ thông tin nào về các
phần tử thuộc tập hợp. Rõ ràng có thể tồn tại một số đối tượng giống
nhau ở một số thông tin nào đó, và ta nói rằng chúng có quan hệ
không thể phân biệt được. Đây chính là quan hệ mấu chốt và chính là
điểm xuất phát của lý thuyết tập thô; biên giới của tập thô là không
rõ ràng, chúng ta phải xấp xỉ nó bằng các tập hợp khác nhau, nhằm
mục đích cuối cùng là trả lời được rằng một đối tượng nào đó thuộc
tập hợp hay không. Lý thuyết tập thô với các tiếp cận như vậy đã
được ứng dụng rất rộng rãi. Ở chương sau sẽ trình bày ở hơn về lý
thuyết tập thô.
Hình 1.4. Mẫu kết quả phân loại theo hồi quy
Thu nhập
N
ợ
Đường hồi quy
X
X
X
X
X
X
X
X
X
X
O
O
O
O
O
O
O O
O
O
D
ữ
li
ệu

Mô hình
mạng Neuron
M
ẫu chiết
xu
ất đ
ư
ợc

Hình 1.5. Sơ đồ quá trình khai phá dữ liệu bằng mạng nơron
-6-

CHƯƠNG 2: LÝ THUYẾT TẬP THÔ ỨNG DỤNG
TRONG KHAI PHÁ DỮ LIỆU
Lý thuyết tập thô rất hiệu quả trong khai phá dữ liệu, tìm kiếm
thông tin, hỗ trợ quyết định, máy học, các hệ cơ sở tri thức.
Lý thuyết tập thô phát huy tác dụng đối với tính không chắc
chắn và không chính xác của dữ liệu. Trong lý thuyết tập thô, mỗi
khái niệm không chính xác được thay thế bởi một cặp khái niệm
chính xác được gọi là xấp xỉ dưới (lower approximation) và xấp xỉ
trên (upper approximation). Xấp xỉ dưới gồm tất cả các đối tượng
chắc chắn có thể thuộc về khái niệm và xấp xỉ trên bao gồm tất cả
đối tượng có thể thuộc về khái niệm. Hiệu của xấp xỉ trên và dưới tạo
thành một khoảng ranh giới (boundary region) của khái niệm không
rõ ràng.
Lý thuyết tập thô (Pawlak, 1980) [20] và lý thuyết tập mờ
(Zadeh, 1965) [15] là những lý thuyết độc lập, nhưng có mối quan hệ
khăng khít với nhau và bổ sung cho nhau trong việc biểu diễn và xử
lý thông tin không chính xác, không đầy đủ. Trong lý thuyết tập mờ,
tính không chính xác được biểu hiện bởi một hàm thuộc, trong khi
cách tiếp cận tập thô lại dựa trên tính không phân biệt được và các
xấp xỉ.
2.1. Các hệ thống thông tin
2.1.1. Hệ thông tin
Hệ thông tin (information system) là tập hợp dữ liệu được biểu
diễn theo dạng bảng, trong đó mỗi dòng là một đối tượng, mỗi cột
biểu diễn một thuộc tính.
Xét hệ thông tin S là một bộ bốn S=<U, Q, V,f>
Trong đó:
U={x1,x2,x3,…,xn} là tập hữu hạn đối tượng
Q: Tập hữu hạn thuộc tính, Q=CD. C tập các thuộc tính điều
kiện, Q thuộc tính quyết định.



Qq
q
VV và V
q
là vùng xác định của thuộc tính q
f: U x Q  V là hàm tổng thể sao cho f(x,q)V
q
với mọi qQ
và xU. f được gọi là hàm thông tin
Ví dụ 2.1: Cho hệ thông tin T1
Bảng 2.1. Bảng thông tin T1
-7-

B
ệnh nhân

Đau đ
ầu

Đau cơ

S
ốt

Cúm

P1

Có

Không

Cao

Có

P2

Không

Có

Cao

Có

P3

Có

Có

R
ất cao

Có

P4

Không

Có

Bình th
ư
ờng

Không

P5

Có

Không

Cao

Không

P6

Không

Có

R
ất cao

Có

Tập đối tượng U={P1, P2, P3, P4, P5, P6}
Tập thuộc tính Q={Đau đầu, đau cơ, sốt, cúm}
Tập giá trị thuộc tính: V
đau đầu
= V
đau cơ
= V
cúm
={có, không};
V
sốt
={bình thường, cao, rất cao}
Hàm thông tin f: f(P1, đau đầu) = có; f(P1, đau cơ) = không;
f(P2,đau đầu)=Không; f(P2, sốt) = Cao,…
2.1.2. Hệ quyết định
Hệ thông tin S=<U, CD, V,f> được gọi là quyết định nếu và
chỉ nếu C  D; ngược lại, nó là không quyết.
Trong bảng thông tin T1 có thể xem là một hệ quyết định vì có
thuộc tính quyết định là cúm. Ta có thể rút ra luật như sau:
“Nếu đau đầu = có và đau cơ = không và sốt = cao thì cúm =
có”
Trong quá trình tạo tập luật sau này chúng ta thường chú trọng
đến việc rút gọn vế trái của luật.
2.2. Tính bất khả phân
2.2.1. Quan hệ tương đương
Quan hệ R trên tập X gọi là quan hệ tương đương nếu thỏa mãn
3 tính chất: Tính phản xạ, tính đối xứng, tính bắc cầu.
2.2.2. Lớp tương đương
Với mỗi phần tử x  X, ta định nghĩa lớp tương đương chứa x,
ký hiệu [x], là tập hợp tất cả những phần tử thuộc X và có quan hệ R
với x:
[x]={yX: yRx}
2.2.3. Quan hệ bất khả phân
Giả sử: S = <U, Q, V, f> là một hệ (bảng) thông tin
P  Q, X  U và x, y  U (x, y là hai đối tượng trong tập vũ
trụ U)
-8-

Quan hệ không thể phân biệt theo P (Indiscernibility relation),
ký hiệu IND(P) được định nghĩa như sau:
IND(P) = {(x, y)  U x U: f(x,q) = f(y,q)  qP}
Quan hệ không thể phân biệt là một quan hệ tương đương và
chia tập đối tượng U thành một họ các lớp tương đương. Họ này
được gọi là sự phân loại (classification) và ký hiệu U|IND(P) hay
U|P. Các đối tượng trong cùng một lớp tương đương là bất khả phân
biệt đối với P. Với xU, lớp tương đương (equivalence class) của x
trong quan hệ IND(P) được biểu diễn là I
p
.
Ví dụ 2.2:
Hệ thông tin T1 của bảng 2.1 ở ví dụ 2.1 có một số quan hệ
không thể phân biệt như sau:
IND{(Sốt)} = {(P1,P2), (P1,P5), (P2,P5), (P3,P6)}
U|IND({Sốt}) = {{P1, P2, P5}, {P3, P6}, {P4}}
Với P = {Đau đầu, sốt}
IND(P) = {(P1, P5)}
U|IND(P) = {{P1, P5}, {P2}, {P3}, {P4}, {P6}}
2.3. Xấp xỉ tập hợp
2.3.1. Không gian xấp xỉ
Cho hệ thông tin S = <U, Q, V, f> và P  Q
Một cặp có thứ tự PS = (U, IND(P)) được gọi là một không
gian xấp xỉ (approximation space)
Mô tả của tập P-cơ bản XU|P được định nghĩa:
Des
p
(X) = {(q,v): f(x,q) = v, xX, q  P}
2.3.2. Tập xấp xỉ
Cho hệ thông tin S = <U, Q, V, f>. PQ và X  U.
P – xấp xỉ dưới (P lower approximation) của X trong PS, ký
hiệu )(XP : )(XP = {xU; I
p
(x)  X}
Những phần tử của )(XP là và chỉ là những đối tượng xU
thuộc vào lớp tương đương sinh ra từ quan hệ không thể phân biệt
được I
p
chỉ nằm trong X.
P – xấp xỉ trên (P upper approximation) của X trong PS, ký
hiệu )(XP : )(XP =

Xx
p
xI

)(

-9-

Những phần tử )(XP là và chỉ là những đối tượng xU thuộc
vào lớp tương đương sinh ra từ quan hệ không thể phân biệt được,
chứa ít nhất một phần tử xX.
P-biên (P – boundary) của X trong S hay vùng không chắc
chắn (Doubtful region) được ký hiệu là Bn
p
(X) và tính như sau:
Bn
p
(X) = )(XP

- )(XP
Bn
p
(X) là tập các phần tử mà sử dụng tập thuộc tính P ta không
thể xác định chúng có thuộc vào X hay không.
2.3.3. Tập thô
Định nghĩa: Tập hợp X được gọi là tập thô nếu Bn
p
(X) là khác
rỗng
Ví dụ 2.3. Với bảng thông tin T1 (bảng 2.1)
Thuộc tính cúm = có. X = {P1, P2, P3, P6}
Với P = {Đau đầu, sốt}
U|IND(P) = {{P1, P5}, {P2}, {P3}, {P4}, {P6}}
)(XP
= {P2, P3, P6}
)(XP
= {P1, P2, P3, P5, P6}
Bnp(X) = {P1, P5} Tập thô
2.3.4. Các tính chất trên tập xấp xỉ
Cho hệ thông tin S = <U, Q, V, f>. P  Q và X  U.
1. )(XP  X  )(XP
2. )(

P

= )(

P = )(, UP

=U
3.
P
(XY) =
P
(X) 
P
(Y)
4. P (XY) = P (X)  P (Y)
…
2.3.5. Các loại tập thô
- Tập thô xác định: Tập thô X được gọi là tập thô xác định
nếu và chỉ nếu )(XP  và )(XP  U.
- Tập thô không xác định trong: Tập thô X được gọi là tập
thô không xác định trong nếu và chỉ nếu )(XP = và )(XP U.
-10-

-Tập thô không xác định ngoài: Tập thô X được gọi là tập
thô không xác định ngoài nếu và chỉ nếu )(XP  và )(XP =U.
- Tập thô không xác định: Tập thô X được gọi là tập thô
không xác định nếu và chỉ nếu )(XP = và )(XP =U.
2.3.6. Hệ số xấp xỉ
Hệ số chính xác (acuracy coefficient) là hệ số để đánh giá độ
chính xác của xấp xỉ (acuracy approximation). Tập thô có thể đặc
trưng hóa dưới hình thức số bằng hệ số phản ánh độ chính xác của
xấp xỉ ký hiệu 
p
(X): 
p
(X) =
)(
)(
XP
XP
(0  
p
(X)  1)
Trong đó |X| biểu diễn lực lượng (số phần tử) của tập X 
Nếu 
p
(X) = 1 thì X là tập rõ đối tượng với quan hệ P
Nếu 
p
(X) < 1 thì X là tập thô đối với P
2.4. Hàm thuộc thô
Cho PQ và XU, sử dụng khái niệm lớp tương đương,
ta có định nghĩa của hàm thuộc thô (rough membership
function) – Độ chắc chắn như sau:
)(
)(
)(
xI
xIX
x
p
p
p
x



, )(x
p
x

 [0, 1].
Hàm thuộc thô có một số tính chất:
1. )(x
p
x

=1 nếu và chỉ nếu x )(XP
2. )(x
p
x

=0 nếu và chỉ nếu x  )(XP


3. 0 < )(x
p
x

<1 nếu và chỉ nếu x  Bn
p
(X)
…
2.5. Tập thuộc tính thu gọn - Reduct
2.5.1 Rút gọn các thuộc tính – Reduct
Chỉ giữ lại những thuộc tính không làm ảnh hưởng đến quan hệ
bất khả phân và do đó không ảnh hưởng đến tập xấp xỉ. Những tập
thuộc tính như vậy gọi là tập thuộc tính thu gọn Reduct.
Cho hệ thông tin S = <U, Q, V, f>. PQ và X  U.
-11-

Tập con P’ của P là rút gọn của P (kí hiệu Red(P)) nếu P’ là
không phụ thuộc và I
P
=I
P
’ hoặc U|IND(P) = U|IND(P’)
Có thể có nhiều hơn một Y rút gọn của P trong bảng thông tin.
Tập chứa tất cả các thuộc tính không thể bỏ được trong P gọi là
Y_lõi (Y_Core).
CoreY(P)=

RedY(P)
Ví dụ 2.4: Với bảng 2.1 (bảng thông tin T1) trong ví dụ 2.1 ta
có thể tìm được các tập lõi là tập rút gọn như sau:
Red
Y
={{đau đầu, sốt},{đau cơ, sốt}}; Core
Y
={Sốt}
2.5.2. Ma trận khả phân (ma trận phân biệt)
Cho hệ thông tin S=<U,Q> với n đối tượng U={x
1
, x
2
, …, x
n
},
ma trận phân biệt (discernibility matrix) của S, ký hiệu M(S) là một
ma trận đối xứng n x n với các giá trị c
ij
được định nghĩa như sau:
(c
ij
) = {pQ: p(x
i
)  p(x
j
)} đối với i,j = 1, 2, …, n
Lõi có thể định nghĩa là hợp tất cả các tập một phần tử trong
ma trận phân biệt được:
CORE(Q) = {pQ: c
ij
={p} với i, j nào đó}
Cho Q’Q có thể dễ dàng thấy rằng Q’ là rút gọn của Q, nếu
Q’ là tập con cực tiểu của Q (đối với phép bao hàm) sao cho: Q’  c
  với mọi phần tử khác rỗng c trong M(S)
Ví dụ 2.6: Cho hệ thông tin S = (U, {a, b, c, d}) như bảng 2.3
từ đó xây dựng ma trận phân biệt, tìm các tập rút gọn và lõi.
Bảng 2.3. Bảng thông tin T2
U

a

b

c

d

x
1

0

1

2

0

x
2

1

2

0

2

x
3

1

0

1

0

x
4

2

1

0

1

x
5

1

1

0

2

Ma trận phân biệt được là đối xứng, do vậy ta chỉ cần xác định
các phần tử nằm dưới đường chéo chính của ma trận. Ma trận phân
biệt được với bảng 2.3 là như sau:
Bảng 2.4. Ma trận phân biệt biến đổi từ bảng 2.3
-12-

x
1
x
2
x
3
x
4
x
5

x
1

x
2
a, b, c, d
x
3
a, b, c b, c, d
x
4
a, c, d a, b, d a, b, c, d
x
5
a, c, d b b, c, d a,d
Từ bảng 2.4 và theo định nghĩa trên ta xác định được lõi chỉ
chứa thuộc tính b (vì Core(Q) = {b}, b  Q và c
52
= {b}) và có 2 tập
thuộc tính rút gọn {a, b} hoặc {b, d} trong hệ thông tin.
2.5.3. Hàm khả phân (hàm phân biệt)
Tất cả các rút gọn của một hệ thông tin có thể tìm được thông
qua hàm khả phân. Với hệ thông tin S = (U, Q) có ma trận phân biệt
M(S) = c
ij
với (c
ij
) = {pQ: p(x
i
)  p(x
j
)} và i,j = 1, 2, …, n. Hàm
phân biệt fs là một hàm Boolean của m biến Boolean a*
1
, a*
2
, …,a*
m

(ứng với các thuộc tính a
1
, a
2
, …, a
m
) được xây dựng dưới dạng
chuẩn tắc tuyển như sau:
fs(a*
1
, a*
2
, …,a*
m
) =  {  c
ij
| 1  j  i  n, c
ij
 }
Trong đó: c*
ij
= {a* | a  c
ij
}
Tập các đơn thức của fs xác định tập rút gọn của S.
Ví dụ 2.7: Theo ví dụ 2.6, ta đã xây dựng được ma trận phân
biệt, từ đó ta xác định được hàm phân biệt như sau
fs(a,b,c,d)=(abcd)(abc)(bcd)(acd)(abd)
(abcd)(acd)b(bcd) (ad)
Rút gọn hàm ta được:
fs(a,b,c,d)= b(ad) = (a  b) (b  d)
Hai tập thuộc tính rút gọn {a,b}; {b,d}
2.5.4. Hàm k-khả phân
Định nghĩa: Hàm k-khả phân là hàm số bool được tạo ra từ
việc chỉ xét các mối kết hợp trên một cột k trong ma trận khả phân
(thay vì tất cả các cột trong ma trận)
2.5.5. k-Reduct
Định nghĩa: Từ hàm k-khả phân ta tìm ra được các Recduct của
hệ thông tin S. Mỗi k-Reduct là tập thuộc tính tối tiểu để nhận ra