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

Số hóa bởi Trung tâm Học liệu

/>

2

LỜI CẢM ƠN
Lời cảm ơn trân trọng đầu tiên em muốn dành tới TS. Nguyễn
Long Giang, người thầy đã dìu dắt và hướng dẫn tơi trong suốt q trình làm
luận văn, sự chỉ bảo và định hướng của thầy giúp tôi tự tin nghiên cứu những
vấn đề mới và giải quyết bài toán một cách khoa học.
Em xin trân trọng cảm ơn Ban giám hiệu và các thầy cô Trường
Đại học Công nghệ Thông tin và Truyền thông, Đại học Thái nguyên đã tạo
các điều kiện cho chúng tôi được học tập và làm khóa luận một cách thuận
lợi.

Lời cảm ơn sâu sắc muốn được gửi tới các thầy giáo Viện Công nghệ
Thông tin - Viện hàn lâm khoa học và Công nghệ Việt Nam, những người
thầy đã dạy dỗ và mở ra cho chúng tôi thấy chân trời tri thức mới, hướng dẫn
chúng tôi cách khám phá và làm chủ công nghệ mới.
Xin được cảm ơn Trung tâm Quản lý Chất lượng – Trường Đại học
Công nghiệp Hà Nội đã tạo mọi điều kiện để tôi được đi học và hồn thành
tốt khố học
Mặc dù đã cố gắng rất nhiều, nhưng chắc chắn trong quá trình học tập
cũng như luận văn khơng khỏi những thiếu sót. Em rất mong được sự thơng
cảm và chỉ bảo tận tình của các thầy cô và các bạn.
Thái Nguyên, tháng …… năm 2014

Lê Trƣờng Giang

Số hóa bởi Trung tâm Học liệu

/>

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

Số hóa bởi Trung tâm Học liệu

/>

4

2.3. Thuật tốn tìm tập rút gọn sử dụng khoảng cách khi loại bỏ đối tượng........38
2.3.1. Cơng thức tính khoảng cách khi loại bỏ đối tượng........................ 38
2.3.2. Thuật tốn tìm tập rút gọn khi loại bỏ đối tượng ........................... 40
Chương 3. THỬ NGHIỆM VÀ ĐÁNH GIÁ KẾT QUẢ .......................................41
3.1. Bài tốn ................................................................................................................41
3.2. Phân tích, lựa chọn cơng cụ ...............................................................................42

3.2.1. Thuật tốn rút gọn thuộc tính sử dụng entropy Liang ................... 42
3.2.2. Mơ tả thuật tốn gia tăng tìm tập rút gọn khi bổ sung tập đối tượng .
....................................................................................................... 43
3.2.3. Lựa chọn công cụ cài đặt ............................................................... 44
3.3. Một số kết quả thử nghiệm ................................................................................44
3.3.1. Kết quả thử nghiệm thuật toán tìm tập rút gọn sử dụng khoảng cách
........................................................................................................ 44
3.3.2. Kết quả thử nghiệm thuật toán gia tăng rút gọn thuộc tính sử dụng
khoảng cách .............................................................................................. 47
KẾT LUẬN .........................................................................................................................................51
Tài liệu tham khảo ..............................................................................................................................52
Danh mục các cơng trình của tác giả ..............................................................................................54
Phụ lục...................................................................................................................................................55

Số hóa bởi Trung tâm Học liệu

/>

5

Danh mục các thuật ngữ
Thuật ngữ tiếng Việt

Thuật ngữ tiếng Anh

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

Số hóa bởi Trung tâm Học liệu

/>

6


Bảng các ký hiệu, từ viết tắt
Ký hiệu, từ viết tắt

Diễn giải

IS

Hệ thông tin

U , A,V , f

DS

U,C

D, V , f

Bảng quyết định

U

Số đối tượng

C

Số thuộc tính điều kiện trong bảng quyết định

A


Số thuộc tính trong hệ thơng tin

u a

Giá trị của đối tượng u tại thuộc tính a

IND B

Quan hệ B

u

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

B

không phân biệt

U/B

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


BN B X

B - miền biên của X

POS B D

B miền dương của D

RED C

Họ tất cả các tập rút gọn của bảng quyết định

CORE C

Tập lõi của bảng quyết định

K P

Tri thức sinh bởi tập thuộc tính P trong hệ thơng tin.

Số hóa bởi Trung tâm Học liệu

/>

7

Danh sách bảng
Bảng 1.1. Bảng thông tin về bệnh cúm .......................................................... 13
Bảng 1.2: Bảng quyết định về bệnh cúm ........................................................ 15
Bảng 1.3. Bảng quyết định về bệnh cúm......................................................... 18

Bảng 1.4. Ký hiệu các tập rút gọn của bảng quyết định ................................ 20
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

/>

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 tốn tìm tập con nhỏ nhất của tập thuộc tính
điều kiện mà bảo tồ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 tố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
thay đổi như vậy, chúng ta lại phải thực hiện lại các thuật tốn tìm tập rút gọn
trên tồn bộ tập đối tượng, do đó chi phí về thời gian thực hiện thuật tốn tìm
tập rút gọn sẽ rất lớn.
Trong mấy năm gần đây, một số cơng trình nghiên cứu đã xây dựng các
phương pháp gia tăng rút gọn thuộc tính trên bảng quyết định thay đổi dựa
trên các độ đo khác nhau [3, 4, 6, 10, 11, 12]. Trong [3, 4, 12], các tác giả đã
xây dựng phương pháp gia tăng tìm tập rút gọn dựa trên miền dương và ma
trận phân biệt khi bổ sung tập đối tượng mới. Trong [10], các tác giả đã xây
dựng các cơng thức tính các độ đo entropy (entropy Shannon, entropy Liang,
entropy kết hợp) khi bổ sung, loại bỏ các thuộc tính. Tuy nhiên, các cơng thức
tính tốn entropy trong [10] còn phức tạp. Về hướng tiếp cận rút gọn thuộc

Số hóa bởi Trung tâm Học liệu

/>

9

tính sử dụng độ đo khoảng cách được định nghĩa qua các khái niệm trong lý
thuyết tập thô, trong [1, 7] tác giả đã sử dụng độ đo khoảng cách Jaccard để
giải quyết bài tốn rút gọn thuộc tính trong bảng quyết đinh. Tuy nhiên, tác
giả trong [1, 7] mới giải quyết bài tốn rút gọn thuộc tính trong trường hợp
bảng quyết định cố định, không thay đổi.
Mục tiêu của luận văn là xây dựng phương pháp rút gọn thuộc tính
trong bảng quyết định thay đổi dựa vào độ đo khoảng cách trong hai trường
hợp: bổ sung đối tượng mới và loại bỏ đối tượng đã có.
Đối tƣợng nghiên cứu của luận văn là các bảng quyết định với dữ liệu

thay đổi khi bổ sung và loại bỏ các đối tượng.
Phạm vi nghiên cứu: Với công cụ là lý thuyết tập thô, đề tài tập trung
nghiên cứu phương pháp gia tăng tìm tập rút gọn của bảng quyết định khi bổ
sung và loại bỏ tập đối tượng.
Phƣơng pháp nghiên cứu của đề tài là nghiên cứu lý thuyết và nghiên
cứu thực nghiệm.
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 tốn hiệu quả.
Về nghiên cứu thực nghiệm: Cài đặt và thử nghiệm các thuật tốn, các
thuật tố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

/>

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 tố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 tố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 tố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 tốn lại tập rút gọn trên tồ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
triển tiếp theo của tác giả luận văn.

Số hóa bởi Trung tâm Học liệu

/>

11

Chƣơng 1. RÚT GỌN THUỘC TÍNH THEO TIẾP CẬN LÝ THUYẾT
TẬP THƠ
Chương này 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 đã công bố về các phương pháp 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ô, bao gồm: Tổng quan về
các phương pháp, phân nhóm các phương pháp và so sánh, đánh giá các
phương pháp. Chương này là kiến thức nền tảng để nghiên cứu phương pháp
rút gọn thuộc tính trong bảng quyết định thay đổi được trình bày ở chương 2.
1.1.

Các khái niệm cơ bản trong lý thuyết tập thô

1.1.1. Hệ thông tin và tập thô

Hệ thông tin là công cụ biểu diễn tri thức dưới dạng một bảng dữ liệu
gồm p cột ứng với p thuộc tính và n hàng ứng với n đối tượng. Một cách hình
thức, hệ thơng tin được định nghĩa là một bộ tứ IS

U , A,V , f trong đó U là

tập hữu hạn, khác rỗng các đối tượng; A là tập hữu hạn, khác rỗng các thuộc
tính; V

V

a

với Va là tập giá trị của thuộc tính a A ; f : U A

Va là hàm

a A

thông tin, a A, u U f u, a

Va .

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à
a u thay vì f u, a . Nếu B

A là một tập con các thuộc tính thì

b1 , b2 ,..., bk


ta ký hiệu bộ các giá trị bi u bởi B u . Như vậy, nếu u và v là hai đối tượng,
thì ta viết B u

B v nếu bi u

Xét hệ thông tin IS

bi v với mọi i 1,..., k .

U , A,V , f . Mỗi tập con các thuộc tính P

A xác

định một quan hệ hai ngơi trên U, ký hiệu là IND P , xác định bởi
IND P

u, v

U U

a P, a u

a v .

IND P là quan hệ P-không phân biệt được. Dễ thấy rằng IND P là một

quan hệ tương đương trên U. Nếu u, v
Số hóa bởi Trung tâm Học liệu

IND P thì hai đối tượng u và v không


/>

12

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 U / P . Ký hiệu lớp tương đương
trong
u

P

phân

tượng

u

là

u

P

,

khi

đó


IND P .

v U u, v

Cho hệ thơng tin IS
thuộc tính B

đối

hoạch U / P chứa

U , A,V , f

và tập đối tượng X

U . Với một tập

A cho trước, chúng ta có các lớp tương đương của phân hoạch

U / B , 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
của U / B (còn gọi là biểu diễn X bằng tri thức có sẵn B), người ta xấp xỉ X
bởi hợp của một số hữu hạn các lớp tương đương của U / B . Có hai cách xấp
xỉ tập đối tượng X thông qua tập thuộc tính B , được gọi là B-xấp xỉ dưới và
B-xấp xỉ trên của X, ký hiệu là lượt là BX và BX , được xác định như sau:
BX

u U u


B

X , BX

u U u

B

X

.

Tập BX bao gồm tất cả các phần tử của U chắc chắn thuộc vào X, cịn
tập BX bao gồm các phần tử của U có thể thuộc vào X dựa trên tập thuộc
tính B. Từ hai tập xấp xỉ nêu trên, ta định nghĩa các tập
BNB X

BX

BX : B-miền biên của X , U

BX : 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 /BY

Trong trường hợp BN B X

X , BX

 Y U /BY

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

/>

13

A , ta gọi B-miền dương của D là tập được xác định như sau

Với B, D

POS B ( D)




BX

X U /D

Rõ ràng POS B ( D ) là tập tất cả các đối tượng u sao cho với mọi v U mà
u B

v B

POS B ( D)

ta
u U u

đều
u

B

có
D

u D

v D

.

Nói


cách

khác,

.

Ví dụ 1.1. Xét hệ thơng tin biểu diễn các triệu chứng cúm của bệnh nhân cho ở
Bảng 1.1.
Bảng 1.1. Bảng thơng tin về bệnh cúm
U

Đau đầu

Thân nhiệt

Cảm cúm

u1

Có

Bình thường

Khơng

u2

Có


Cao

Có

u3

Có

Rất cao

Có

u4

Khơng

Bình thường

Khơng

u5

Khơng

Cao

Khơng

u6


Khơng

Rất cao

Có

u7

Khơng

Cao

Có

u8

Khơng

Rất cao

Khơng

Ta có: U / {Đau đầu} =

u1 , u2 , u3 , u4 , u5 , u6 , u7 , u8

U / {Thân nhiệt} =
U / {Cảm cúm} =

u1 , u4 , u2 , u5 , u7 , u3 , u6 , u8

u1 , u4 , u5 , u8 , u2 , u3 , u6 , u7

U / {Đau đầu, Cảm cúm} =

u1 , u2 , u3 , u4 , u5 , u8 , u6 , u7

Như vậy, các bệnh nhân u2 , u3 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

/>

14

u1 , u2 , u3 , u4 , u5 , u7 , u6 , u8

.

Đặt X {u u (Cảm cúm) = Có} = u2 , u3 , u6 , u7 . Khi đó:
BX

u2 , u3 và BX

u5 , u6 , u7 , u8 . Nếu đặt D = {Cảm cúm} thì

tập hợp BN B X
U/D


u2 , u3 , u5 , u6 , u7 , u8 . Như vậy, B-miền biên của X là

X1



POS B ( D)

u1 , u4 ; BX 2

u2 , u3 , u6 , u7 , BX 1

u1, u4 , u5 , u8 ; X 2

u2 , u3 ,

u1 , u2 , u3 , u4 .

BX

X U /D

Với các khái niệm của tập xấp xỉ đối với phân hoạch U / B , các tập thô
được chia thành bốn lớp cơ bản:
1) Tập X là B-xác định thô nếu BX

và BX U .

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 ngồi nếu BX

và BX U .

4) Tập X là B-khơng xác định hồn tồ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 C D

.

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 DS
Trong đó:

U

U ,C

D

u1 , u2 , u3 , u4 , u5

A= {Đau đầu, Đau cơ, Nhiệt độ, Cúm}.
Tập thuộc tính điều kiện C= {Đau đầu, Đau cơ, Nhiệt độ}

Số hóa bởi Trung tâm Học liệu

/>

15

Tập thuộc tính quyết định D={Cúm}
Bảng 1.2: Bảng quyết định về bệnh cúm
Đau đầu Đau cơ

U

Cúm


u1

Khơng

Có

Cao

Có

u2

Có

Khơng

Cao

Có

u3

Có

Có

Rất cao

Có


u4

Khơng

Có

u5

Có

Khơng

Cao

Khơng

u6

Khơng

Có

Rất cao

Có

Cho một bảng quyết định DS
U/D

Nhiệt độ


Bình thường Khơng

U ,C

D , giả sử U / C

X 1 , X 2 ,..., X n và

Y1 , Y2 ,..., Yn .

Một lớp X i U / C được gọi là nhất quán nếu
u (d )

v(d ), u, v

Xi, d

D , lúc này có thể viết u D

Một lớp Yi U / D được gọi là nhất quán nếu u (a)
lúc này có thể viết u A

Một bảng quyết định DS

nếu U / C  U / D thi DS

Xi D .

v( a ), u , v


Yi ,

a

C,

Yi A .

v A

là nhất quán, ngược lại DS

v D

U ,C

U,C

U ,C

D là nhất quán nếu mọi lớp X i U / C

D được gọi là không nhất quán. Dễ thấy

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.

Có thể thấy bảng quyết định là nhất quán khi và chỉ khi POSC ( D) U . Trong
trường hợp khơng nhất qn thì POSC ( D) U chỉ là tập con cực đại của U sao
cho phụ thuộc hàm C

D là đúng.

Số hóa bởi Trung tâm Học liệu

/>

16

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ô

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
Mục tiêu của rút gọn thuộc tính trong bảng quyết định theo tiếp cận tập
thơ là sử dụng cơng cụ tập thơ để tìm tập con nhỏ nhất của tập thuộc tính điều
kiện mà bảo tồn thơng tin phân lớp của bảng quyết định. Dựa vào tập rút
gọn thu được, việc sinh luật và phân lớp đạt hiệu quả cao nhất. Với một bảng
quyết định cho trước, độ phức tạp thời gian của thuật tốn tìm tất cả các tập
rút gọn là hàm mũ đối với số thuộc tính điều kiện. Tuy nhiên, trong các bài
tốn thực tế khơng địi hỏi tìm tất cả các tập rút gọn mà chỉ cần tìm được một
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 tố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 tốn này giảm thiểu đáng kể khối lượng tính tốn, nhờ đó
có thể áp dụng đối với các bài tố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

/>

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 tố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
kiện được phân thành ba nhóm: thuộc tính lõi (core attribute), thuộc tính rút
gọn (reductive attribute) và thuộc tính dư thừa (redundant attribute). Thuộc
tính lõi là thuộc tính khơng thể thiếu trong việc phân lớp chính xác tập dữ
liệu. Thuộc tính lõi xuất hiện trong tất cả các tập rút gọn của bảng quyết định.
Thuộc tính dư thừa là những thuộc tính mà việc loại bỏ chúng không ảnh
hưởng đến việc phân lớp tập dữ liệu, thuộc tính dư thừa khơng xuất hiện
trong bất kỳ tập rút gọn nào của bảng quyết định. Thuộc tính rút gọn là thuộc
tính xuất hiện trong một tập rút gọn nào đó của bảng quyết định.
Cho bảng quyết định DS

U,C

D,V , f . Thuộc tính c C được gọi là

không cần thiết (dispensable) trong DS dựa trên miền dương nếu
POSC D

POS(C

c )

D ; Ngược lại, c được gọi là cần thiết (indispensable).

Tập tất cả các thuộc tính cần thiết trong DS được gọi là tập lõi dựa trên miền
dương và được ký hiệu là CORE C . Khi đó, thuộc tính cần thiết chính là
thuộc tính lõi và thuộc tính khơng cần thiết là thuộc tính dư thừa hoặc thuộc
tính rút gọn.
Cho bảng quyết định DS


U , C D,V , f và tập thuộc tính R

Số hóa bởi Trung tâm Học liệu

C . Nếu

/>

18

1) POS R ( D) POSC ( D)
2) r R, POS R

r

( D)

POSC ( 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 đó CORE C



R.

R RED C


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 a R và a là thuộc tính dư thừa của DS nếu a C



R.

R RED C

Ví dụ 1.2. Xét bảng quyết định về bệnh cúm cho ở Bảng 1.2.
Bảng 1.3. Bảng quyết định về bệnh cúm
U

Mệt mỏi

Đau đầu

Đau cơ Thân nhiệt

Cảm
cúm

u1

Có

Có

Có


Bình thường Khơng

u2

Có

Có

Có

Cao

Có

u3

Có

Có

Có

Rất cao

Có

u4

Có


Khơng

Có

Bình thường Khơng

u5

Có

Khơng

Khơng

Cao

Khơng

u6

Có

Khơng

Có

Rất cao

Có


Bảng này có hai tập rút gọn là R1 = {Đau cơ, Thân nhiệt} và R2 = {Đau
đầu, Thân nhiệt}. Như vậy tập lõi là PCORE(C) = {Thân nhiệt} và Thân nhiệt
là thuộc lõi duy nhất. Các thuộc tính khơng cần thiết bao gồm:
 Thuộc tính Mệt mỏi là thuộc tính dư thừa vì khơng tham gia vào rút gọn nào
 Hai thuộc tính Đau đầu và Đau cơ là hai thuộc tính rút gọn vì đều có
mặt trong một tập rút gọn. Hai thuộc tính này đều khơng cần thiết theo nghĩa
là, từ bảng dữ liệu, có thể loại bỏ một trong hai thuộc tính này mà vẫn chuẩn
đốn đúng bệnh. Tức là

Số hóa bởi Trung tâm Học liệu

/>

19

POS{Đau cơ, Thân nhiệt}({Cảm cúm}) = POSC({Cảm cúm})
POS{Đau đầu, Thân nhiệt}({Cảm cúm}) = POSC({Cảm cúm}).
Với khái niệm tập rút gọn dựa trên miền dương, Pawlak cũng đưa ra khai
niệm độ quan trọng của thuộc tính dựa trên miền dương và xây dựng thuật
tốn heuristic tìm một tập rút gọn tốt nhất dựa trên miền dương.
2) Các phương pháp rút gọn thuộc tính khá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 tố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

/>

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
Ký hiệu

Mô tả

RP


Tập rút gọn dựa trên miền dương (Pawlak)

RH

Tập rút gọn dựa trên entropy Shannon.

RF

Tập rút gọn dựa trên các phép toán trong đại số quan hệ

RM

Tập rút gọn sử dụng metric

RE

Tập rút gọn dựa trên entropy Liang.

RK

Tập rút gọn dựa trên độ khác biệt của tri thức

RS

Tập rút gọn dựa trên ma trận phân biệt

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


RF

RH

RK

RE

RS

RM .

2) Với bảng quyết định khơng nhất qn, ta có RF

RK

RE

RH

RM và

RS . 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 RP .
Nhóm 2: Bao gồm RF , RH , RM
Nhóm 3: Bao gồm RK , RE , RS .

Số hóa bởi Trung tâm Học liệu


/>

21

Mối liên hệ giữa các tập rút gọn của các nhóm như sau:
Nếu RIII là một tập rút gọn thuộc Nhóm 3 thì tồn tại RII là một tập rút
gọn thuộc Nhóm 2 và RI là một tập rút gọn thuộc Nhóm 1 ( RP ) sao cho

RI

RII

RIII . Mối liên hệ này cho thấy tập rút gọn RP ít thuộc tính nhất,

các tập rút gọn RF , RH , RM nhiều thuộc tính hơn và các tập rút gọn RK , RE ,
RS 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.
1.2.3. Kết quả lựa chọn, so sánh, đánh giá các phƣơng pháp
Như đã trình bày trong mục 1.2.1, rút gọn thuộc tính trong bảng quyết
định là 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 khả
năng phân lớp của bảng quyết định. Theo tiêu chuẩn định lượng, rút gọn
thuộc tính trong bảng quyết định là 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 độ chắc chắn của tất cả các luật phân lớp vào các lớp
quyết định. Do đó, các phương pháp rút gọn thuộc tính được gọi là phù hợp
nếu tập rút gọn tìm được phải bảo tồn độ chắc chắn của tập luật quyết định
hay độ chắc chắn của bảng quyết định.
Để đánh giá các phương pháp rút gọn thuộc tính, các nhà nghiên cứu về
tập thơ thường sử dụng hai tiêu chuẩn: độ phức tạp thời gian của thuật tốn
tìm tập rút gọn và chất lượng phân lớp của tập rút gọn tốt nhất tìm được. Theo
kết quả thống kê, phần lớn độ phức tạp thời gian của các thuật tốn tìm tập rút

Số hóa bởi Trung tâm Học liệu

/>

22

gọn là như nhau (chỉ khác nhau về khối lượng tính tốn) nên các nghiên cứu
về tập thơ tập trung đánh giá chất lượng phân lớp của tập rút gọn tìm được.
Chất lượng phân lớp được đặc trưng bởi độ hỗ trợ của tập luật (độ hỗ trợ của
bảng quyết định) dựa trên tập rút gọn [9]. Tập rút gọn có chất lượng phân lớp
càng tốt thì độ hỗ trợ của tập luật dựa trên tập rút gọn càng cao (một luật phân
lớp trên tập rút gọn sẽ hỗ trợ cho nhiều đối tượng).
Trong [1], tác giả đã đề xuất độ chắc chắn
nhất quán g (consistency measure), độ hỗ trợ

(certainty measure), độ

(support measure) của bảng

quyết định và nghiên cứu sự thay đổi giá trị ba độ đo này trên các tập rút gọn
thu được của ba nhóm phương pháp đã trình bày ở trên. Luận văn mơ tả vắn

tắt các kết quả như sau:
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 tồ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 qn vì
đều bảo tồ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

/>

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 tồ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ợ
độ hỗ trợ

của tập luật trên tập rút gọn thuộc Nhóm 2 cao hơn

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

pháp thuộc Nhóm 2 hiệu quả hơn các phương pháp thuộc Nhóm 3 theo tiêu
chuẩn chất lượng phân lớp của tập rút gọn.
Từ các kết quả nghiên cứu đã công bố về các phương pháp rút gọn thuộc
tính trong bảng quyết định nêu trên, chương 2 của luận văn đề xuất phương
pháp rút gọn thuộc tính trong bảng quyết định sử dụng khoảng cách. Khoảng
cách trong luận văn sử dụng là cải tiến của khoảng cách Jaccard trong [1, 7].
Trên cơ sở đó, luận văn xây dựng các cơng thức tính khoảng cách khi bổ
sung, loại bỏ đối tượng và xây dựng phương pháp rút gọn sử dụng khoảng
cách trong hai trường hợp này.

Số hóa bởi Trung tâm Học liệu

/>

24

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

Phƣơng pháp rút gọn thuộc tính sử dụng khoảng cách


2.1.1. Khoảng cách giữa hai tập hợp hữu hạn
Một khoảng cách trên tập hợp U là một ánh xạ d : U U

thỏa

0,

mãn các điều kiện sau với mọi x, y, z U [2]
P 1 d x, y

0 , d x, y

P 2 d x, y

d y, x .

P 3 d x, y

d y, z

0 khi và chỉ khi x

y.

d x, z .

Định lý 2.1. Cho U là tập hữu hạn các đối tượng và P U là họ các tập con
của U. Với mọi X ,Y


P U , 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 X ,Y , Z P U ta có:
d X ,Y

Giả sử U
N chiều V X

d Y,Z

(3.1)

d X,Z

N và U
v1X , v2X ,..., vNX

u1 , u2 ,..., u N . Ta biểu diễn tập X


với vkX 1 nếu uk

X

và vkX

U bởi một véc tơ

0 trong trường hợp

ngược lại.
Đặt V XY V XV Y (tích trong của véc tơ V X và V Y ), khi đó d X , Y được biểu
diễn: d X , Y

V XX

V YY

2V XY , ta có:

d X ,Y

d Y,Z

V XX V YY

d X ,Y

d Y,Z


d X,Z

2V XY V YY V ZZ
2V YY

Số hóa bởi Trung tâm Học liệu

2V XY

2V YZ

2V YZ
2V XZ

(3.2)

/>

25

0 hoặc V YY V YZ V XY V XZ

Dễ thấy V Y V X V Y V Z

0 thỏa mãn vì

phần tử thứ k của V Y V X và V Y V Z là 0 và 1. Từ cơng thức 3.2 ta có:
d X ,Y

d X , Z (đpcm)


d Y,Z

2.1.2. Khoảng cách giữa hai tri thức và các tính chất
Từ khoảng cách giữa hai tập hợp hữu hạn được định nghĩa ở phần 2.1.1,
luận văn xây dựng khoảng cách giữa hai tri thức sinh bởi hai tập thuộc tính
trên bảng quyết định.
Cho bảng quyết định DS
K P

ui

P

D,V , f , mỗi tập thuộc tính P

U,C

C,

ui U được gọi là một tri thức (knowledge) của P trên U [1].

K P gồm U phần tử, mỗi phần tử là một khối trong phân hoạch U / P , 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à K U .
Định lý 2.2. Ánh xạ d : K U

K U
U


1

d K P ,K Q

U

xác định bởi

0,

ui

2

ui

P

Q

ui

P

ui

Q

P


và ui

Q

i 1

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

P

ui

Q

ui

ui

P

Q

khi
ui
ui


0 . Do đó, d J K P , K Q

và
P

ui

Q

ui

ui

P

U , nghĩa là K P

(P2)

Theo

Q

với ui U ta có

0 . dJ K P , K Q

chỉ
ui


P

ui

Q

ui

P

ui

Q

0

khi
ui

P

ui

Q

với

mọi

với


mọi

K Q .

định

nghĩa

d K P ,K Q

d K Q ,K P

K ( P), K (Q) K U .

Số hóa bởi Trung tâm Học liệu

/>