Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/

1
ĐẠI HỌC THÁI NGUYÊN
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN & TRUYỀN THÔNG

LÊ TRƢỜNG GIANG

PHƢƠNG PHÁP GIA TĂNG RÚT GỌN THUỘC TÍNH
TRONG BẢNG QUYẾT ĐỊNH SỬ DỤNG ĐỘ ĐO KHOẢNG CÁCH

LUẬN VĂN THẠC SĨ KỸ THUẬT

Thái Nguyên - 2014



3
MỤC LỤC
MỤC LỤC 3
Danh mục các thuật ngữ 5
Bảng các ký hiệu, từ viết tắt 6
Danh sách bảng 7
MỞ ĐẦU 8
Chương 1. RÚT GỌN THUỘC TÍNH THEO TIẾP CẬN LÝ THUYẾT TẬP THÔ 11
1.1. Các khái niệm cơ bản trong lý thuyết tập thô 11
1.1.1. Hệ thông tin và tập thô 11
1.1.2. Bảng quyết định 14
1.2. Rút gọn thuộc tính trong bảng quyết định theo tiếp cận lý thuyết tập thô 16
1.2.1. Tổng kết về các phương pháp rút gọn thuộc tính trong bảng quyết
định 16
1.2.2. Kết quả phân nhóm các phương pháp rút gọn thuộc tính dựa vào
tập rút gọn 20
1.2.3. Kết quả lựa chọn, so sánh, đánh giá các phương pháp 21
Chương 2. RÚT GỌN THUỘC TÍNH TRONG BẢNG QUYẾT ĐỊNH THAY
ĐỔI SỬ DỤNG KHOẢNG CÁCH 24
2.1. Phương pháp rút gọn thuộc tính sử dụng khoảng cách 24
2.1.1. Khoảng cách giữa hai tập hợp hữu hạn 24
2.1.2. Khoảng cách giữa hai tri thức và các tính chất 25
2.1.3. Tập rút gọn của bảng quyết định dựa trên khoảng cách 28
2.1.4. Thuật toán tìm tập rút gọn sử dụng khoảng cách 29
2.2. Thuật toán gia tăng tìm tập rút gọn sử dụng khoảng cách khi bổ sung đối
tượng 33
2.2.1. Công thức gia tăng tính khoảng cách khi bổ sung đối tượng 33
2.2.2. Thuật toán gia tăng tìm tập rút gọn khi bổ sung đối tượng 35


Tập thô
Rough Set
Hệ thông tin
Information System
Bảng quyết định
Decision Table
Bảng quyết định nhất quán
Consistent Decision Table
Bảng quyết định không nhất quán
Inconsistent Decision Table
Quan hệ không phân biệt được
Indiscernibility Relation
Xấp xỉ dưới
Lower Approximation
Xấp xỉ trên
Upper Approximation
Rút gọn thuộc tính
Attribute Reduction
Tập rút gọn
Reduct
Tập lõi
Core
Ma trận phân biệt
Indiscernibility Matrix
Hàm phân biệt
Indiscernibility Function
Luật quyết định
Decision Rule
Khoảng cách
Distance


Quan hệ
B
không phân biệt
B
u

Lớp tương đương chứa
u
của quan hệ
IND B

/UB

Phân hoạch của
U
sinh bởi tập thuộc tính
B
.
BX

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

BX

B
xấp xỉ trên của
X

Bảng 2.1. Bảng quyết định minh họa thuật toán tìm tập rút gọn 31
Bảng 3.1. Kết quả thực hiện Thuật toán NEBAR và Thuật toán DBAR 45
Bảng 3.2. Tập rút gọn của Thuật toán NEBAR và Thuật toán DBAR 45
Bảng 3.3. Kết quả thực hiện Thuật toán NEBAK và Thuật toán DBAK 46
trên các bộ số liệu lớn 46
Bảng 3.4. 04 bộ số liệu thử nghiệm 47
Bảng 3.5. Kết quả thực hiện thuật toán DBAR trên bộ số liệu ban đầu 48
Bảng 3.6. Kết quả thực hiện thuật toán DBAR và thuật toán gia tăng
OSIDBAR 49 Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/

8
MỞ ĐẦU
Lựa chọn thuộc tính, còn gọi là trích chọn đặc trưng, là một trong những
bài toán quan trọng trong khai phá dữ liệu và học máy. Lựa chọn thuộc tính
sử dụng lý thuyết tập thô [9] được gọi là rút gọn thuộc tính. Rút gọn thuộc
tính trong bảng quyết định là bài toán tìm tập con nhỏ nhất của tập thuộc tính
điều kiện mà bảo toàn thông tin phân lớp của bảng quyết định, gọi là tập rút
gọn. Trong hai thập kỷ trở lại đây, chủ đề nghiên cứu về rút gọn thuộc tính
theo tiếp cận lý thuyết tập thô đã thu hút đông đảo cộng đồng nghiên cứu về
tập thô tham gia [1]. Có rất nhiều phương pháp rút gọn thuộc tính khác nhau
đã được đề xuất sử dụng các độ đo khác nhau như miền dương, ma trận phân
biệt, các độ đo entropy trong lý thuyết thông tin, các độ đo trong tính toán hạt,
độ đo khoảng cách. Tuy nhiên, hầu hết các nghiên cứu về rút gọn thuộc tính
đều được thực hiện trên các bảng quyết định với tập đối tượng và tập thuộc
tính cố định, không thay đổi. Trong thực tế, các bảng quyết định luôn bị cập
nhật và thay đổi với các trường hợp: bổ sung hoặc loại bỏ tập đối tượng, bổ
sung hoặc loại bỏ tập thuộc tính, cập nhật tập đối tượng đã tồn tại. Mỗi khi

Về nghiên cứu lý thuyết: Nghiên cứu các kết quả đã công bố và xây
dựng các công thức tính toán gia tăng khi bổ sung và loại bỏ đối tượng, trên
cơ sở đó đề xuất các thuật toán hiệu quả.
Về nghiên cứu thực nghiệm: Cài đặt và thử nghiệm các thuật toán, các
thuật toán gia tăng tìm tập rút gọn sử dụng khoảng cách trên các bộ số liệu
mẫu lấy từ kho dữ liệu UCI [14] nhằm đánh giá tính hiệu quả của phương
pháp gia tăng so với phương pháp truyền thống.
Bố cục của luận văn gồm phần mở đầu, ba chương nội dung, phần kết
luận và các mục tài liệu tham khảo.
Chương 1: Trình bày một số khái niệm cơ bản trong lý thuyết tập thô và
các kết quả nghiên cứu về các phương pháp rút gọn thuộc tính trong bảng

Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/

10
quyết định theo tiếp cận heuristic, các kết quả nghiên cứu về phân nhóm, so
sánh và đánh giá các phương pháp.
Chương 2: Trình bày các bước xây dựng phương pháp rút gọn thuộc tính
sử dụng độ đo khoảng cách, bao gồm định nghĩa độ đo khoảng cách, định
nghĩa tập rút gọn và độ quan trọng của thuộc tính dựa trên khoảng cách và
thuật toán heuristic tìm một tập rút gọn tốt nhất sử dụng khoảng cách. Trên cơ
sở đó, chương 2 trình bày nội dung chính là xây dựng thuật toán tìm tập rút
gọn của bảng quyết định thay đổi trong trường hợp bổ sung và loại bỏ đối
tượng theo hướng tiếp cận tính toán gia tăng.
Chương 3: Trình bày kết quả thử nghiệm và đánh giá các thuật toán tìm
tập rút gọn theo hướng tiếp cận gia tăng trong trường hợp bổ sung và loại bỏ
đối tượng. So sánh kết quả thực hiện so với các phương pháp truyền thống là
tính toán lại tập rút gọn trên toàn bộ tập đối tượng để thấy rõ tính hiệu quả của
phương pháp gia tăng.
Phần kết luận: Tóm tắt kết quả đạt được của luận văn và hướng phát

aA
;
:
a
f U A V
là hàm
thông tin,
,a A u U

,
a
f u a V
.
Với mọi
,u U a A
, ta ký hiệu giá trị thuộc tính a tại đối tượng u là
au
thay vì
,f u a
. Nếu
12
, , ,
k
B b b b A
là một tập con các thuộc tính thì
ta ký hiệu bộ các giá trị
i
bu
bởi
Bu

phân biệt được bởi các thuộc tính trong P. Quan hệ tương đương
IND P
xác định
một phân hoạch trên U, ký hiệu là
/U IND P
hay
/UP
. Ký hiệu lớp tương đương
trong phân hoạch
/UP
chứa đối tượng u là
P
u
, khi đó
,
P
u v U u v IND P
.
Cho hệ thông tin
,,,IS U A V f
và tập đối tượng
XU
. Với một tập
thuộc tính
BA
cho trước, chúng ta có các lớp tương đương của phân hoạch
/UB
, thế thì một tập đối tượng X có thể biểu diễn thông qua các lớp tương
đương này như thế nào?
Trong lý thuyết tập thô, để biểu diễn X thông qua các lớp tương đương

: B-miền ngoài của X.
B-miền biên của X là tập chứa các đối tượng có thể thuộc hoặc không
thuộc X, còn B-miền ngoài của X chứa các đối tượng chắc chắn không thuộc
X. Sử dụng các lớp của phân hoạch U/B, các xấp xỉ dưới và trên của X có thể
viết lại
/BX Y U B Y X
,
/.BX Y U B Y X

Trong trường hợp
B
BN X
thì X được gọi là tập chính xác (exact
set), ngược lại X được gọi là tập thô (rough set).

Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/

13
Với
,B D A
, ta gọi B-miền dương của D là tập được xác định như sau
/
()
B
X U D
POS D BX


Rõ ràng
()


Có
Cao
Có
u
3

Có
Rất cao
Có
u
4

Không
Bình thường
Không
u
5

Không
Cao
Không
u
6

Không
Rất cao
Có
u
7

{Đau đầu, Cảm cúm} =
1 2 3 4 5 8 6 7
, , , , , , ,u u u u u u u u

Như vậy, các bệnh nhân
23
,uu
không phân biệt được về đau đầu và cảm
cúm, nhưng phân biệt được về thân nhiệt.
Các lớp không phân biệt được bởi B = {Đau đầu, Thân nhiệt} là:

Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/

14
1 2 3 4 5 7 6 8
, , , , , , ,u u u u u u u u
.
Đặt
{X u u
(Cảm cúm) = Có} =
2 3 6 7
, , ,u u u u
. Khi đó:
23
,BX u u
và
2 3 5 6 7 8
, , , , , .BX u u u u u u
Như vậy, B-miền biên của X là
tập hợp

.
2) Tập X là B-không xác định trong nếu
BX
và
BX U
.
3) Tập X là B-không xác định ngoài nếu
BX
và
BX U
.
4) Tập X là B-không xác định hoàn toàn nếu
BX
và
BX U
.
1.1.2. Bảng quyết định
Một lớp đặc biệt của các hệ thông tin có vai trò quan trọng trong nhiều
ứng dụng là bảng quyết định. Bảng quyết định là một hệ thông tin DS với tập
thuộc tính A được chia thành hai tập khác rỗng rời nhau C và D , lần lượt
được gọi là tập thuộc tính điều kiện và tập thuộc tính quyết định. Tức là
, , ,DS U C D V f
với
CD
.
Ví dụ 1.3:
Hệ thống thông tin
,,,IS U A V f
biểu diễn cơ sở tri thức về bệnh cúm
được thể hiện trong bảng 1.4 là một bảng quyết định

Không
Cao
Có
u
3

Có
Có
Rất cao
Có
u
4

Không
Có
Bình thường
Không
u
5

Có
Không
Cao
Không
u
6

Không
Có
Rất cao

Y U D
được gọi là nhất quán nếu
( ) ( ), , ,
i
u a v a u v Y a C
,
lúc này có thể viết
i
u A v A Y A
.
Một bảng quyết định
,DS U C D
là nhất quán nếu mọi lớp
/
i
X U C

là nhất quán, ngược lại
,DS U C D
được gọi là không nhất quán. Dễ thấy
nếu
//U C U D
thi
,DS U C D
là nhất quán.
Tương tự, nếu
//U D U C
thì
,DS U C D
là nhất quán ngược.

tập rút gọn tốt nhất theo một tiêu chuẩn đánh giá đặt ra. Do đó, các phương
pháp rút gọn thuộc tính sử dụng cận tập thô đều thực hiện theo hướng tiếp
cận heuristic. Các phương pháp này đều có các điểm chung như sau:
- Đưa ra khái niệm tập rút gọn của phương pháp dựa trên một độ đo
được chọn. Các phương pháp khác nhau có độ đo khác nhau, điển hình là các
độ đo trong tính toán hạt (granunal computing), độ đo entropy, độ đo khoảng
cách, sử dụng ma trận…
- Đưa ra khái niệm độ quan trọng của thuộc tính đặc trưng cho chất
lượng phân lớp của thuộc tính dựa trên độ đo được chọn.
- Xây dựng một thuật toán heuristic tìm một tập rút gọn tốt nhất theo
tiêu chuẩn đánh giá độ quan trọng của thuộc tính (chất lượng phân lớp của
thuộc tính). Thuật toán này giảm thiểu đáng kể khối lượng tính toán, nhờ đó
có thể áp dụng đối với các bài toán có dữ liệu lớn. Các thuật toán heuristic
này thường được xây dựng theo hai hướng tiếp cận khác nhau: hướng tiếp
cận từ dưới lên (bottom-up) và hướng tiếp cận từ trên xuống (top-down). Ý
tưởng chung của hướng tiếp cận từ dưới lên (bottom-up) là xuất phát từ tập

Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/

17
tập lõi, bổ sung dần dần các thuộc tính có độ quan trọng lớn nhất vào tập lõi
cho đến khi thu được tập rút gọn. Ý tưởng chung của hướng tiếp cận từ trên
xuống (top-down) xuất phát từ tập thuộc tính điều kiện ban đầu, loại bỏ dần
các thuộc tính có độ quan trọng nhỏ nhất cho đến khi thu được tập rút gọn.
Cả hai hướng tiếp cận này đều đòi hỏi phải sắp xếp danh sách các thuộc tính
theo thứ tự giảm dần hoặc tăng dần của độ quan trọng tại mỗi bước lặp.
1) Phương pháp rút gọn thuộc tính dựa trên miền dương
Trong lý thuyết tập thô truyền thống, Pawlak [9] đã đưa ra khái niệm tập
rút gọn của bảng quyết định dựa trên miền dương và xây dựng thuật toán tìm
tập rút gọn dựa trên miền dương. Trong bảng quyết định, các thuộc tính điều


Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/

18
1)
( ) ( )
RC
POS D POS D

2)
, ( ) ( )
C
Rr
r R POS D POS D

thì R là một tập rút gọn của C dựa trên miền dương.
Tập rút gọn định nghĩa như trên còn gọi là tập rút gọn Pawlak. Ký hiệu
RED C
là họ tất cả các tập rút gọn Pawlak của C. Khi đó
R RED C
CORE C R

.
Khi đó, a là thuộc tính rút gọn của DS nếu tồn tại một tập rút gọn
R RED C

sao cho
aR
và a là thuộc tính dư thừa của DS nếu
R RED C


Có
Có
Có
Rất cao
Có
u
4

Có
Không
Có
Bình thường
Không
u
5

Có
Không
Không
Cao
Không
u
6

Có
Không
Có
Rất cao
Có

Rút gọn thuộc tính trong lý thuyết tập thô là chủ đề nghiên cứu khá sôi
động trong mấy năm gần đây. Các kết quả nghiên cứu về rút gọn thuộc tính
trong lý thuyết tập thô được trình bày khá đầy đủ và cập nhật trong [1]. Các
phương pháp rút gọn thuộc tính điển hình được tổng kết và công bố trong [1]
bao gồm:
1) Phương pháp miền dương tìm tập rút gọn dựa trên miền dương (tập
rút gọn nguyên thủy theo định nghĩa của Pawlak).
2) Phương pháp sử dụng ma trận phân biệt và hàm phân biệt của
Skowron tìm tập rút gọn dựa trên ma trận phân biệt.
3) Phương pháp sử dụng entropy Shannon tìm tập rút gọn dựa trên
entropy Shannon.
4) Phương pháp sử dụng các phép toán trong đại số quan hệ tìm tập rút
gọn
5) Phương pháp sử dụng tính toán hạt tìm tập rút gọn dựa trên độ khác
biệt của tri thức.
6) Phương pháp sử dụng entropy Liang tìm tập rút gọn dựa trên entropy
Liang.
7) Phương pháp sử dụng metric được xây dựng dựa trên khoảng cách
Jaccard.

Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/

20
1.2.2. Kết quả phân nhóm các phƣơng pháp rút gọn thuộc tính dựa vào
tập rút gọn
Trong [1], tác giả đã tổng kết và công bố mối liên hệ giữa các tập rút gọn
của các phương pháp rút gọn thuộc tính, trên cơ sở đó phân nhóm các phương
pháp rút gọn thuộc tính dựa vào tập rút gọn. Để thuận tiện cho việc trình bày,
luận văn ký hiệu các tập rút gọn theo Bảng 1.3 dưới đây:
Bảng 1.4. Ký hiệu các tập rút gọn của bảng quyết định

Trong [1], tác giả đã tổng kết và công bố mối liên hệ giữa các tập rút gọn
như sau:
1) Với bảng quyết định nhất quán, các tập rút gọn nêu trên là như nhau,
nghĩa là
P F H K E S M
R R R R R R R
.
2) Với bảng quyết định không nhất quán, ta có
F H M
R R R
và
K E S
R R R
. Nghĩa là, các tập rút gọn được phân thành 3 nhóm:
Nhóm 1: Bao gồm
P
R
.
Nhóm 2: Bao gồm
F
R
,
H
R
,
M
R

Nhóm 3: Bao gồm
K

. Mối liên hệ này cho thấy tập rút gọn
P
R
ít thuộc tính nhất,
các tập rút gọn
F
R
,
H
R
,
M
R
nhiều thuộc tính hơn và các tập rút gọn
K
R
,
E
R
,
S
R
nhiều thuộc tính nhất.
Từ mối liên hệ giữa các tập rút gọn, các phương pháp rút gọn thuộc tính
cũng được phân thành 3 nhóm tương ứng:
Nhóm 1: Bao gồm phương pháp tìm tập rút gọn Pawlak.
Nhóm 2: Bao gồm phương pháp sử dụng entropy Shannon, phương pháp
sử dụng các phép toán trong đại số quan hệ và phương pháp sử dụng metric.
Nhóm 3: Bao gồm phương pháp sử dụng entropy Liang, phương pháp sử
dụng ma trận phân biệt, phương pháp sử dụng độ khác biệt của tri thức.

Nếu bảng quyết định nhất quán, các tập rút gọn bảo toàn độ chắc chắn,
độ nhất quán bằng 1 và tăng độ hỗ trợ của tập luật quyết định.
Nếu bảng quyết định không nhất quán:
1) Tập rút gọn của các phương pháp thuộc Nhóm 1 (tập rút gọn miền
dương) làm giảm độ chắc chắn, độ nhất quán và tăng độ hỗ trợ của tập luật
quyết định.
2) Tập rút gọn của các phương pháp thuộc Nhóm 2 bảo toàn độ chắc
chắn, độ nhất quán và tăng độ hỗ trợ của tập luật quyết định.
3) Tập rút gọn của các phương pháp thuộc Nhóm 3 bảo toàn độ chắc
chắn, độ nhất quán và tăng độ hỗ trợ của tập luật quyết định.
Từ kết quả nghiên cứu về sự thay đổi giá trị độ chắc chắn, độ nhất quán,
độ hỗ trợ trên ba tập rút gọn của ba nhóm phương pháp nêu trên, tác giả [1] đã
đưa ra kết quả về sự lựa chọn các phương pháp phù hợp như sau:
1) Tất cả các phương pháp đều phù hợp với bảng quyết định nhất quán vì
đều bảo toàn độ chắc chắn của tập luật quyết định bằng 1.

Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/

23
2) Với bảng quyết định không nhất quán, tập rút gọn Pawlak làm giảm
độ chắc chắc của tập luật, do đó các phương pháp thuộc Nhóm 1 (tìm tập rút
gọn Pawlak) không phù hợp. Các phương pháp thuộc Nhóm 2 và Nhóm 3 phù
hợp vì tập rút gọn bảo toàn độ chắc chắn của tập luật.
Với các phương pháp phù hợp, từ kết quả nghiên cứu về sự thay đổi giá
trị các độ đo đánh giá hiệu năng tập luật quyết định và kết quả nghiên cứu về
mối liên hệ giữa các tập rút gọn, tác giả [1] đã chứng minh tập rút gọn tốt nhất
tìm được bởi các phương pháp thuộc Nhóm 2 có chất lượng phân lớp tốt hơn
tập rút gọn tốt nhất tìm được bởi các phương pháp thuộc Nhóm 3. Điều này
cũng có nghĩa độ hỗ trợ của tập luật trên tập rút gọn thuộc Nhóm 2 cao hơn
độ hỗ trợ của tập luật trên tập rút gọn thuộc Nhóm 3, nghĩa là các phương

khi và chỉ khi
xy
.
2P
,,d x y d y x
.
3P
, , ,d x y d y z d x z
.
Định lý 2.1. Cho U là tập hữu hạn các đối tượng và
UP
là họ các tập con
của U. Với mọi
, UXY P
, biểu thức:
,d X Y X Y X Y

là một khoảng cách giữa tập X và tập Y.
Chứng minh. Hiển nhiên,
,d X Y
thỏa mãn điều kiện (P1) và (P2). Do
đó, ta cần chứng minh điều kiện (P3) (bất đẳng thức tam giác), nghĩa là với
mọi
,, UX Y Z P
ta có:
, , ,d X Y d Y Z d X Z
(3.1)
Giả sử
UN
và

V V V
(tích trong của véc tơ
X
V
và
Y
V
), khi đó
,d X Y
được biểu
diễn:
,2
XX YY XY
d X Y V V V
, ta có:
, , 2 2
XX YY XY YY ZZ YZ
d X Y d Y Z V V V V V V

, , , 2 2 2 2
YY XY YZ XZ
d X Y d Y Z d X Z V V V V
(3.2)

Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/

25
Dễ thấy
0
Y X Y Z

U
phần tử, mỗi phần tử là một khối trong phân hoạch
/UP
, còn
được gọi là một hạt tri thức (knowledge granule). Ký hiệu họ tất cả các tri
thức trên U là
UK
.
Định lý 2.2. Ánh xạ
: 0,d U UKK
xác định bởi
2
1
1
,
U
i i i i
P Q P Q
i
d K P K Q u u u u
U

là một khoảng cách giữa
KP
và
KQ
.
Chứng minh
(P1) Áp dụng Định lý 3.1 với hai tập hợp
i

, nghĩa là
K P K Q
.
(P2) Theo định nghĩa
,,d K P K Q d K Q K P
với mọi
( ), ( )K P K Q UK
.