1

BỘ GIÁO DỤC VÀ ĐÀO TẠO

VIỆN HÀN LÂM KHOA HỌC
VÀ CÔNG NGHỆ VIỆT NAM

HỌC VIỆN KHOA HỌC VÀ CÔNG NGHỆ
-----------------------------

VŨ VĂN ĐỊNH

RÚT GỌN THUỘC TÍNH TRONG BẢNG QUYẾT ĐỊNH
KHÔNG ĐẦY ĐỦ THEO TIẾP CẬN TẬP THÔ DUNG SAI

LUẬN ÁN TIẾN SỸ TOÁN HỌC

HÀ NỘI – 2016


2

VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM
HỌC VIỆN KHOA HỌC VÀ CÔNG NGHỆ
……..….***…………

VŨ VĂN ĐỊNH

RÚT GỌN THUỘC TÍNH TRONG
BẢNG QUYẾT ĐỊNH KHÔNG ĐẦY ĐỦ THEO
TIẾP CẬN TẬP THÔ DUNG SAI

không ngại gian khó tận tình giúp đỡ và hướng dẫn tôi trong suốt quá trình
nghiên cứu và hoàn thành luận án.
Tôi xin chân thành cảm ơn đến Ban lãnh đạo Viện Công nghệ thông tin
thuộc Viện Hàn lâm Khoa học và Công nghệ Việt Nam, Học viện Khoa học và
Công nghệ thuộc Viện Hàn lâm Khoa học và Công nghệ Việt Nam, Phòng
quản lý đào tạo, các phòng ban chức năng và tập thể các Nhà khoa học của
Viện Công nghệ thông tin và Học viện Khoa học và Công nghệ đã giúp đỡ tôi
trong suốt quá trình học tập và nghiên cứu.
Tôi xin được bày tỏ lòng biết ơn đến Ban giám hiệu, lãnh đạo các đơn vị
Trường Đại học Điện lực đã hỗ trợ, tạo điều kiện tốt nhất cho tôi trong suốt
quá trình thực hiện luận án.
Tôi xin chân thành cảm ơn tới lãnh đạo và các đồng nghiệp tại Khoa
Công nghệ thông tin, Phòng Khảo thí và Đảm bảo chất lượng giáo dục
trường Đại học Điện lực đã động viên giúp đỡ tôi trong thời gian tôi học tập
và nghiên cứu.
Cuối cùng tôi bày tỏ lòng biết ơn đến gia đình và người thân của tôi,
những người luôn sát cánh bên tôi để động viên, giúp đỡ tôi vượt qua khó
khăn để hoàn thành luận án.


3

MỤC LỤC
LỜI CAM ĐOAN.............................................................................................................................1
LỜI CẢM ƠN....................................................................................................................................2
MỤC LỤC ..........................................................................................................................................3
DANH MỤC CÁC THUẬT NGỮ...............................................................................................6
BẢNG CÁC KÝ HIỆU, TỪ VIẾT TẮT.....................................................................................7
DANH MỤC HÌNH, BẢNG..........................................................................................................8
MỞ ĐẦU.............................................................................................................................................9

2.2.4 Mối liên hệ giữa RD và R .............................................................41
2.2.5 Mối liên hệ giữa R và R .............................................................44
2.2.6 Đề xuất phân nhóm các phương pháp rút gọn thuộc tính .............45
2.3. Đánh giá các phương pháp rút gọn thuộc tính................................................48
2.3.1. Luật quyết định và các độ đo đánh giá hiệu năng .........................48
2.3.2. Đề xuất các độ đo mới đánh giá hiệu năng tập luật quyết định ....54
2.3.3. Nghiên cứu sự thay đổi giá trị các độ đo đề xuất trên các tập rút
gọn

........................................................................................................57

2.3.4. Thử nghiệm sự thay đổi giá trị các độ đo đề xuất trên các tập rút
gọn

........................................................................................................60

2.3.5. Lựa chọn, đánh giá các phương pháp rút gọn thuộc tính..............65
2.4. Kết luận chương 2 ............................................................................................67
CHƯƠNG 3. ĐỀ XUẤT CÁC PHƯƠNG PHÁP RÚT GỌN THUỘC TÍNH TRONG
BẢNG QUYẾT ĐỊNH KHÔNG ĐẦY ĐỦ.............................................................................68
3.1. Mở đầu ..............................................................................................................68
3.2. Chọn tập đối tượng đại diện cho bài toán rút gọn thuộc tính.........................68
3.2.1. Chọn tập đối tượng đại diện cho hệ thông tin không đầy đủ.........69
3.2.2. Chọn tập đối tượng đại diện cho bảng quyết định không đầy đủ ..73
3.3. Phương pháp rút gọn thuộc tính sử dụng lượng thông tin mở rộng có điều
kiện ...........................................................................................................................78


5



Quan hệ dung sai

Tolerance Relation

Tập thô dung sai

Tolerance Rough Set

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


IIS  U , A

Hệ thông tin không đầy đủ

IDS  U , A  d 

Bảng quyết định không đầy đủ

U

Số đối tượng

A

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

u a

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

SIM  A

Quan hệ dung sai trên tập thuộc tính A

SA u 

Lớp dung sai của đối tượng u trên tập thuộc tính A

U/A


I B /d 

Lượng thông tin của tập thuộc tính B đối với thuộc
tính quyết định d





CEI R d 

Lượng thông tin mở rộng của tập thuộc tính R đối
với thuộc tính quyết định d

MC A

Họ các khối đồng nhất cực đại trên tập A

DIS R 

Hàm quan hệ của IDS trên R


8

DANH MỤC HÌNH, BẢNG
Hình 1.1. Mối quan hệ giữa các tập rút gọn .................................................46
Hình 2.1. Sự thay đổi độ hỗ trợ  trên các tập rút gọn..................................64
Hình 3.1. Sự thay đổi độ hỗ trợ  trên hai tập rút gọn của hai thuật toán

bước của quá trình khai phá dữ liệu và khám phá tri thức, bao gồm tiền xử lý
số liệu, khai phá dữ liệu và đánh giá kết quả thu được. Rút gọn thuộc tính và
trích lọc luật quyết định (luật phân lớp) là hai ứng dụng chính của lý thuyết
tập thô trong khai phá dữ liệu. Rút gọn thuộc tính thuộc giai đoạn tiền xử lý
dữ liệu còn trích lọc luật thuộc giai đoạn khai phá dữ liệu. Mục tiêu của rút
gọn thuộc tính là loại bỏ các thuộc tính dư thừa nhằm tìm tập con nhỏ nhất
của tập thuộc tính điều kiện (tập rút gọn) mà bảo toàn thông tin phân lớp của
bảng quyết định. Dựa trên 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.
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ô
của Pawlak [31] là chủ đề nghiên cứu sôi động trong hai thập kỷ qua. Cho đến
nay, có rất nhiều phương pháp rút gọn thuộc tính đã được đề xuất bởi các
nhóm nghiên cứu theo các hướng tiếp cận khác nhau như: hướng tiếp cận dựa
trên miền dương, hướng tiếp cận dựa trên ma trận, hướng tiếp cận dựa trên độ
đo entropy, hướng tiếp cận tính toán hạt, hướng tiếp cận dựa trên độ đo
khoảng cách... Phương pháp rút gọn thuộc tính dựa trên miền dương do
Pawlak [48] đề xuất, phương pháp này đã xây dựng thuật toán tính miền
dương POS C D  . Về sau, các công bố trong [31][49][11][25] đã tiếp tục cải
tiến thuật toán này. Phương pháp rút gọn thuộc tính sử dụng các phép toán
trong đại số quan hệ do Hu Xiaohua và các cộng sự [14] đưa ra, phương pháp
này xây dựng thuật toán tìm tập lõi và tập rút gọn của bảng quyết định. Tuy
nhiên khái niệm tập lõi có nhược điểm và đã được tác giả trong luận án [1]


10

khắc phục. Phương pháp rút gọn thuộc tính sử dụng ma trận phân biệt do
Skowron [8] đề xuất được xây dựng trên khái niệm ma trận phân biệt, hàm
phân biệt. Phương pháp này cũng đã được Ye Dong Yi và các cộng sự [51]
khắc phục nhược điểm tìm tập rút gọn và tập lõi trong bảng quyết định không

Trong các bài toán thực tế, các bảng quyết định thường thiếu giá trị trên
miền giá trị thuộc tính, gọi là các bảng quyết định không đầy đủ. Trên bảng
quyết định không đầy đủ, Kryszkiewicz [18] đã mở rộng quan hệ tương
đương trong lý thuyết tập thô truyền thống thành quan hệ dung sai và đề xuất
mô hình tập thô dung sai nhằm giải quyết bài toán rút gọn thuộc tính và trích
lọc luật trực tiếp không qua bước xử lý giá trị thiếu. Giống như các phương
pháp rút gọn thuộc tính trong bảng quyết định đầy đủ theo tiếp cận lý thuyết
tập thô truyền thống được trình bày trong luận án [2], các phương pháp rút gọn
thuộc tính trong bảng quyết định không đầy đủ theo tiếp cận mô hình tập thô
dung sai đã công bố là các phương pháp heuristic, đều thực hiện các bước sau
đây:
1) Đưa ra khái niệm tập rút gọn dựa trên độ đo được xây dựng.
2) Đưa ra khái niệm độ quan trọng của thuộc tính, đặc trưng cho khả năng
đóng góp của thuộc tính vào việc phân lớp tập đối tượng. Thuộc tính có độ
quan trọng càng lớn thì khả năng đóng góp vào việc phân lớp đối tượng càng
nhiều và ngược lại.
3) 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á là độ quan trọng của thuộc tính (khả năng phân lớp của thuộc
tính)
Trong mấy năm gần đây các phương pháp rút gọn thuộc tính trong bảng
quyết định không đầy đủ theo tiếp cận tập thô dung sai đã được các nhà khoa
học quan tâm nghiên cứu và đã thu được một số kết quả đáng kể. Các phương
pháp điển hình có thể kể đến là: Kryszkiewicz [18] định nghĩa tập rút gọn dựa
trên hàm quyết định suy rộng và đề xuất phương pháp rút gọn thuộc tính sử


12

dụng hàm quyết định suy rộng. Zuqiang Meng và các cộng sự [56] đưa ra
khái niệm về tập rút gọn dựa trên miền dương và đề xuất phương pháp rút gọn

công bố [37], [56] đã chỉ ra tập rút gọn dựa trên miền dương [56], tập rút gọn
dựa trên hàm quyết định suy rộng [18], tập rút gọn dựa trên hàm phân bố, tập
rút gọn dựa trên hàm ấn định [37], [55] là có định nghĩa độ đo tương đương
nhau. Trong bảng quyết định không nhất quán, Renpu Li và cộng sự [37] đã
chứng minh tập rút gọn dựa trên miền dương, tập rút gọn dựa trên hàm ấn
định là có định nghĩa độ đo tương đương nhau. Huasheng ZOU và cộng sự [17]
đã chứng minh tập rút gọn dựa trên hàm quyết định suy rộng, tập rút gọn dựa
trên ma trận phân biệt là có định nghĩa độ đo tương đương nhau. Tuy nhiên,
theo tài liệu hiện có thì cho đến nay chưa có nghiên cứu tổng thể về mối liên hệ
đầy đủ giữa các khái niệm tập rút gọn, từ đó có một bức tranh tổng thể về mối
liên hệ giữa các khái niệm tập rút gọn, là 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.
Về vấn đề thứ hai, Yuhua Qian và các cộng sự [33] đã xây dựng các độ đo
đánh giá hiệu năng của tập luật quyết định, tuy nhiên các độ đo này các tác
giả đã xây dựng dựa trên khối đồng nhất cực đại, nhưng các phương pháp trên
được định nghĩa dựa trên quan hệ dung sai, do đó không thể sử dụng các độ
đo của Yuhua Qian và các cộng sự [33] để đánh giá các phương pháp rút gọn
thuộc tính và đòi hỏi phải xây dựng các độ đo mới.
Trên cơ sở tổng kết các nghiên cứu liên quan đến các phương pháp rút
gọn thuộc tính và các độ đo đánh giá hiệu năng tập luật quyết định dựa trên
các tập rút gọn theo tiếp cận tập thô dung sai như đã trình bày ở trên, luận án
đặt ra các vấn đề cần nghiên cứu như sau:
1) Có thể nói rằng tập rút gọn chính là kết quả của một phương pháp rút
gọn thuộc tính. Trong bảng quyết định nhất quán, công bố [37], [56]
đã chỉ ra tập rút gọn của phương pháp dựa trên miền dương [56], tập


14

rút gọn của phương pháp sử dụng hàm quyết định suy rộng [18], tập

độ chắc chắn, độ hỗ trợ mới để đánh giá khả năng phân lớp của tập
rút gọn, làm cơ sở để so sánh, đánh giá các phương pháp rút gọn
thuộc tính.
3) Hướng nghiên cứu rút gọn thuộc tính đã đạt được một số kết quả
nhất định. Tuy nhiên, việc nghiên cứu và tìm kiếm các phương pháp
mới vẫn đòi hỏi nhiều nỗ lực nghiên cứu nhằm phong phú thêm các
phương pháp rút gọn thuộc tính. Trên cơ sở đó, lựa chọn các phương
pháp phù hợp để giải quyết các bài toán trong thực tiễn.
Từ các vấn đề cần nghiên cứu đã trình bày ở trên, mục tiêu nghiên cứu
của luận án là so sánh, đánh giá các phương pháp rút gọn thuộc tính đã công
bố, trên cơ sở đó đề xuất các phương pháp mới.
Với mục tiêu trên, nội dung nghiên cứu của luận án là:
1) Nghiên cứu mối liên hệ giữa các tập rút gọn nhằm: phân nhóm các
phương pháp rút gọn thuộc tính đã công bố theo nguyên tắc: các tập
rút gọn của các phương pháp có định nghĩa độ đo tương đương nhau
được phân thành một nhóm; mối quan hệ giữa các tập rút gọn của các
nhóm phương pháp.
2) Đề xuất các độ đo mới đánh giá hiệu năng tập luật quyết định (độ
chắc chắn, độ nhất quán, độ hỗ trợ) và nghiên cứu sự thay đổi các độ
đo này trên các tập rút gọn của các nhóm phương pháp nhằm đánh
giá các phương pháp theo tiêu chuẩn khả năng phân lớp của tập rút
gọn. Tập rút gọn của phương pháp nào có khả năng phân lớp tốt nhất,
kém nhất...
3) Đề xuất hai phương pháp mới rút gọn thuộc tính trong bảng quyết
định không đầy đủ: phương pháp sử dụng hàm quan hệ và phương


16

pháp sử dụng lượng thông tin mở rộng. So sánh, đánh giá phương

Chương 3 trình bày ba kết quả chính. Thứ nhất là chọn tập tối tượng đại
diện cho bài toán rút gọn thuộc tính nhằm giảm thiểu số đối tượng (dữ liệu),
tăng tính hiệu quả của các thuật toán rút gọn thuộc tính. Thứ hai là đề xuất
phương pháp mới rút gọn thuộc tính sử dụng hàm quan hệ và so sánh, thử
nghiệm phương pháp với các phương pháp đã có trên các bộ số liệu UCI. Thứ
ba là đề xuất phương pháp mới rút gọn thuộc tính sử dụng lượng thông tin mở
rộng và so sánh, thử nghiệm phương pháp với các phương pháp đã có trên các
bộ số liệu UCI.
Cuối cùng, phần kết luận nêu những đóng góp của luận án, hướng phát
triển tiếp theo và các vấn đề khác mà tác giả quan tâm.


18

CHƯƠNG 1. MỘT SỐ KIẾN THỨC CƠ SỞ
Chương này trình bày một số khái niệm cơ bản về hệ thông tin và mô
hình tập thô truyền thống của Pawlak[31], mô hình tập thô mở rộng dựa trên
quan hệ dung sai do Kryszkiewicz [18] đề xuất, gọi là mô hình tập thô dung
sai, trên các hệ thông tin không đầy đủ, bao gồm: hệ thông tin không đầy đủ,
quan hệ dung sai, các tập xấp xỉ dựa trên quan hệ dung sai, bảng quyết định
không đầy đủ. Chương này cũng trình bày một số khái niệm về tập rút gọn
của các phương pháp rút gọn thuộc tính đã công bố làm cơ sở cho nghiên cứu
về mối liên hệ giữa các khái niệm tập rút gọn ở Chương 2.
1.1.

Hệ thông tin và mô hình tập thô truyền thống

1.1.1. Hệ thông tin
Hệ thông tin là một cặp IS  U , A 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. Mỗi thuộc tính

Cho hệ thông tin IS  U , A và tập đối tượng X  U . Với một tập thuộc
tính B  A cho trước, chúng ta 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à Bxấ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
BN B  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 / B Y  X  , BX   Y  U / B Y  X   .

Trong trường hợp BN B  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).
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


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


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} =

u , u  , u , u , u  , u , u , u 
1

4

2

5

7

3

6

8

u , u , u , u  , u , u , u , u 
1

4

5

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

u1 , u2 , u3  , u4  , u5 , u7  , u6 , u8  .
Đặt X  {u u (Cảm cúm) = Có} = u2 , u3 , u6 , u7  . Khi đó:


21

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

tập hợp BN B  X   u5 , u6 , u7 , u8  . Nếu đặt D = {Cảm cúm} thì
U / D   X 1  u1, u4 , u5 , u8  ; X 2  u2 , u3 , u6 , u7  , BX 1  u1 , u4  ; BX 2  u2 , u3  ,

POS B ( D) 

  BX   u , u , u , u  .
1

2

3

4

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:

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.
Định nghĩa 1.1. [31] (Tập lõi dựa trên miền dương) Cho bảng quyết
định DS  (U , C  D) . 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à
PCORE  C  . Khi đó, thuộc tính cần thiết chính là thuộc tính lõi.
Định nghĩa 1.2. [31] (Tập rút gọn dựa trên miền dương) Cho bảng quyết
định DS  (U , C  D) và tập thuộc tính R  C . Nếu
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
PRED  C  là họ tất cả các tập rút gọn Pawlak của C.
Khi đó PCORE  C  



RPRED  C 

R.


23

1.2.