Tóm tắt Luận án Tiến sĩ Toán học: 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

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

Chuyên ngành: Cơ sở toán học cho tin học Mã số: 62.46.01.10

TÓM TẮT NLUẬN ÁN TIẾN SĨ TOÁN HỌC

HÀ NỘI - 2016

Công trình được hoàn thành tại: Học viện Khoa học và Công nghệ - Viện Hàn lâm Khoa học và Công nghệ Việt Nam

Người hướng dẫn khoa học 1: GS.TS Vũ Đức Thi Người hướng dẫn khoa học 2: PGS.TS Ngô Quốc Tạo

Phản biện 1: … Phản biện 2: … Phản biện 3: ….

Luận án sẽ được bảo vệ trước Hội đồng chấm luận án tiến sĩ, họp tại Học viện Khoa học và Công nghệ - Viện Hàn lâm Khoa học và Công nghệ Việt Nam vào hồi … giờ .. ’, ngày … tháng … năm 2016

Có thể tìm hiểu luận án tại: - Thư viện Học viện Khoa học và Công nghệ - Thư viện Quốc gia Việt Nam

MỞ ĐẦU

1. Tính cấp thiết của luận án

Lý thuyết tập thô do Pawlak đề xuất vào những năm đầu thập niên tám mươi của thế kỷ hai mươi được xem là công cụ hữu hiệu để giải quyết các bài toán phân lớp, phát hiện luật…chứa dữ liệu không đầy đủ, không chắc chắn. 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. Trên bảng quyết định không đầy đủ, Kryszkiewicz đã 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 trích lọc luật trực tiếp không qua bước xử lý giá trị thiếu. 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 trong những năm gần đây là: phương pháp dựa trên miền dương, phương pháp sử dụng hàm quyết định suy rộng, phương pháp sử dụng lượng thông tin, phương pháp sử dụng metric, phương pháp sử dụng hàm phân bố (distribution reduct), phương pháp sử dụng hàm ấn định (assignment reduct), phương pháp sử dụng ma trận phân biệt, phương pháp sử dụng ma trận dung sai. 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 luận án đặt ra các vấn đề cần nghiên cứu như sau:

 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ác công bố đã chỉ ra tập rút gọn của phương pháp dựa trên miền dương, tập rút gọn của phương pháp sử dụng hàm quyết định suy rộng, tập rút gọn sử dụng hàm phân bố, phương pháp sử dụng hàm ấn định, là có định nghĩa độ đo tương đương nhau. Tuy nhiên trên bảng quyết định không nhất quán, các tập rút gọn của các phương pháp là khác nhau và theo tài liệu hiện có mà tác giả biết thì chưa có nghiên cứu liên quan đến việc so sánh các 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.

 Việc so sánh, đánh giá các phương pháp rút gọn thuộc tính thường dựa trên hai tiêu chuẩn: độ phức tạp thời gian của thuật toán heuristic tìm tập rút gọn và khả năng phân lớp của tập rút gọn. Từ việc tổng kết các phương pháp rút gọn thuộc tính, tác giả thấy rằng nếu cùng sử dụng một đơn vị tính toán cơ sở trong tập thô dung sai (lực lượng các lớp dung sai) thì độ phức tạp thời gian các thuật toán heuristic của các phương pháp là gần như nhau (độ phức tạp thời gian đa thức). Do đó, việc so sánh, đánh giá các phương pháp đều sử dụng tiêu chuẩn khả năng phân lớp (độ hỗ trợ của tập luật) của tập rút gọn. Về mặt định tính, tập rút gọn bảo toàn khả năng phân lớp của bảng quyết định. Về mặt định lượng, tập rút gọn bảo

2 toàn độ chắc chắn của tập luật quyết định. Tập rút gọn của phương pháp nào có độ hỗ trợ của tập luật cao (luật quyết định phủ nhiều đối tượng) thì có khả năng phân lớp cao. Do đó, khả năng phân lớp được tính bằng độ hỗ trợ của tập luật. Các tác giả đã đưa ra độ chắc chắn, độ nhất quán và độ hỗ trợ của tập luật quyết định trên bảng quyết định không đầy đủ. Tuy nhiên, các tác giả chưa nghiên cứu sự thay đổi của các độ đo này trên các tập rút gọn của các phương pháp rút gọn thuộc tính, do đó các độ đo này không đánh giá được khả năng phân lớp của tập rút gọn và đòi hỏi phải có độ 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.

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

2. Mục tiêu nghiên cứu của luận án

1) Trong bảng quyết định nhất quán, các công bố đã chỉ ra tập rút gọn của phương pháp trên là tương đương nhau. Tuy nhiên trên bảng quyết định không nhất quán, các tập rút gọn của các phương pháp là khác nhau và theo tài liệu hiện có mà tác giả biết thì chưa có nghiên cứu liên quan đến việc so sánh các tập rút gọn để so sánh, đánh giá các phương pháp rút gọn.

2) Việc so sánh, đánh giá các phương pháp rút gọn thuộc tính thường dựa trên hai tiêu chuẩn: độ phức tạp thời gian của thuật toán heuristic tìm tập rút gọn và khả năng phân lớp của tập rút gọn. Tác giả thấy rằng nếu cùng sử dụng một đơn vị tính toán cơ sở trong tập thô dung sai thì độ phức tạp thời gian các thuật toán heuristic của các phương pháp là như nhau (độ phức tạp thời gian đa thức). Do đó, việc so sánh, đánh giá các phương pháp đều sử dụng tiêu chuẩn khả năng phân lớp của tập rút gọn(độ hỗ trợ của tập luật). Về mặt định tính, tập rút gọn bảo toàn khả năng phân lớp của bảng quyết định. Về mặt định lượng, tập rút gọn bảo toàn độ chắc chắn của tập luật quyết định. Tập rút gọn của phương pháp nào có độ hỗ trợ của tập luật cao thì có khả năng phân lớp cao. Do đó, khả năng phân lớp được tính bằng độ hỗ trợ của tập luật. Trong các nghiên cứu trước, các tác giả đã đưa ra độ chắc chắn, độ nhất quán và độ hỗ trợ của tập luật quyết định trên bảng quyết định không đầy đủ. Tuy nhiên, các tác giả chưa nghiên cứu sự thay đổi của các độ đo này trên các tập rút gọn của các phương pháp rút gọn thuộc tính, do đó các độ đo này không đánh giá

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.

3 được khả năng phân lớp của tập rút gọn và đòi hỏi phải có độ 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. Các nội dung nghiên cứu chính của luận án

Chương 1 trình bày các khái niệm cơ bản về mô hình tập thô dung sai

dựa trên quan hệ dung sai trong hệ thông tin không đầy đủ

Chương 2 trình bày hai kết quả chính. Thứ nhất là 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 kết quả nghiên cứu mối liên hệ giữa các tập rút gọn. Thứ hai là đề xuất các độ đo mới đánh giá hiệu năng tập luật quyết định và nghiên cứu sự thay đổi giá trị các độ đo này trên các tập rút gọn nhằm so sánh, đánh giá các nhóm phương pháp rút gọn thuộc tính trên tiêu chuẩn khả năng phân lớp của tập rút gọn (độ hỗ trợ).

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), 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.

Chương 1. CÁC KHÁI NIỆM CƠ BẢN

Chương này trình bày một số khái niệm cơ bản trong mô hình tập thô

mở rộng dựa trên quan hệ dung sai, trên các hệ thông tin không đầy đủ.

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

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 với Va là tập giá trị của thuộc tính a A

a A

xác định một ánh xạ: .

a U : V a

a A

u U

Với hệ thông tin

sao cho

và

 IS U A



  a u

chứa , nếu tồn tại giá trị thiếu (missing value) thì IS được gọi là hệ thông tin không đầy đủ,

, 

 IIS U A 



, 4 trái lại IS được gọi là hệ thông tin đầy đủ. Ta biểu diễn giá trị thiếu được ký hiệu là ‘*’ và hệ thông tin không đầy đủ là

1.2. Mô hình tập thô dung sai

Xét hệ thông tin không đầy đủ

, với tập thuộc tính

 IIS U A 



định nghĩa một quan hệ nhị phân trên U như sau:

P , A

 SIM P



  u v U U a P a u



  a v

  a u

  a v

 

 '*'

Quan hệ



 SIM P



 

 SIM P



a P 

không phải là quan hệ tương đương vì chúng có tính là một phản xạ, đối xứng nhưng không có tính bắc cầu. Do đó, quan hệ dung sai (tolerance relation), hay quan hệ tương tự (similarity  relation) trên U. Ta có,   SIM a



, , '*'          

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

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 với tính điều kiện và tập thuộc tính quyết định. Tức là





C D  

DS U C D ,  

với giả thiết

Xét bảng quyết định



  d u

u U

c C

  và

DS U C D , u U d D ,    

  c u

 sao cho

 IDS U C D



,  

đầy thiếu giá trị thì DS được đủ giá trị, nếu tồn tại gọi là bảng quyết định không đầy đủ, trái lại DS được gọi là bảng quyết định với đầy đủ. Ta biểu diễn bảng quyết định không đầy đủ là . Không mất tính chất tổng quát, giả thiết D chỉ gồm một thuộc

d D , '*'  V d

 d

  tính quyết định duy nhất

1.4. Tập rút gọn và tập lõi

 IIS U A 

a , thiết (dispensable)



là không cần    a 

/ A 

Định nghĩa 1.2 Cho hệ thông tin không đầy đủ . Ta nói rằng  tính thuộc trong A nếu ; ngược lại, a được gọi là cần thiết (indispensable)  U SIM A U SIM A /  trong A. Tập tất cả các thuộc tính cần thiết trong A được gọi là tập lõi của A. Khi đó, thuộc tính cần thiết chính là thuộc tính lõi.

Định nghĩa 1.3 Cho hệ thông tin không đầy đủ

 và với mọi

. Tập thuộc tính ,

 U SIM R U SIM A 



 IIS U A  



R / / A r R



là một tập rút gọn của A nếu   U SIM R

   r

Hiển nhiên, A có nhiều tập rút gọn. Khi đó, tập lõi của A là giao của tất

cả các tập rút gọn của A.

U SIM A / /  

Kết luận chương 1

Chương 1 đã trình bày một số khái niệm cơ bản trong mô hình tập thô dung sai do Kryszkiewicz đề xuất và một số khái niệm cơ bản về tập rút gọn và tập lõi trong hệ thông tin không đầy đủ và bảng quyết định không đầy đủ. Các khái niệm này được sử dụng trong chương 2 và chương 3 của luận án.

Chương 2. PHÂN NHÓM VÀ ĐÁNH GIÁ CÁC PHƯƠNG PHÁP RÚT GỌN THUỘC TÍNH TRONG BẢNG QUYẾT ĐỊNH KHÔNG ĐẦY ĐỦ

2.1. Mở đầu

Chương này trình bày các kết quả nghiên cứu sau đây:

1) Phân nhóm các phương pháp rút gọn thuộc tính trong bảng quyết định không đầy đủ dựa vào nghiên cứu mối liên hệ giữa các khái niệm tập rút gọn.

2) Đánh giá các phương pháp rút gọn thuộc tính dựa vào nghiên cứu sự thay đổi các độ đo đánh giá hiệu năng tập luật quyết định trên các khái niệm tập rút gọn.

2.2. Phân nhóm các phương pháp rút gọn thuộc tính

Tiêu chí phân nhóm là: các phương pháp có tập rút gọn như nhau được phân thành một nhóm. Các kết quả trong phần này đã được tác giả công bố trong tài liệu [1].

2.2.1. Các khái niệm tập rút gọn trong bảng quyết định không đầy đủ

TMR

Kryszkiewicz M và các cộng sự đã đư ra khái niệm tập rút gọn của ), Zuqiang Meng và các cộng sự IDS dựa trên hàm quyết định suy rộng ( ), Huang B và các đưa ra khái niệm về tập rút gọn dựa trên miền dương ( cộng sự đưa ra khái niệm về tập rút gọn dựa trên lượng thông tin ). Tác giả trước đã đưa ra khái niệm về tập rút (information quantity)( IR ), Huasheng ZOU và cộng sự đưa ra khái niệm tập gọn dựa trên metric( ). Công trình trước tác giả đưa ra rút gọn dựa trên ma trận phân biệt( ), ngoài ra, trong các khái niệm tập rút gọn dựa trên ma trận dung sai( công trình khác, các tác giả đưa ra khái niệm tập rút gọn phân bố (distribution reduct)(

), tập rút gọn ấn định (assignment reduct)(

R

R

Kết quả nghiên cứu về mối liên hệ giữa các khái niệm tập rút gọn như

R

1) Nếu bảng quyết định nhất quán, các tác giả đã chỉ ra

là như nhau về định nghĩa độ đo.

2) Nếu bảng quyết định không nhất quán, Renpu Li và cộng sự đã là như nhau về định nghĩa độ đo. Huasheng ZOU và

và

R R R

chứng minh cộng sự đã chứng minh

và

như nhau về định nghĩa độ đo.

R R

R

2.2.2. Mối liên hệ giữa các khái niệm tập rút gọn

,

TMR



 IDS U A  khi

  d  và

và chỉ

. A khi

  d K A K A

  d

   d K R K R









, ,   



Mệnh đề 2.1. Cho bảng quyết định không đầy đủ  Khi    I R d

     I A d

đó 



R A

Mệnh đề 2.2. Cho bảng quyết định không đầy đủ

 IDS U A 

   d IDS. Khi

và đó

của

sai

n n 

 

khi và chỉ khi

với mọi

  d

  d K A K A



trận 

là ma  

dung  

, ,      R m i j

 TM m   i j     d K R K R . i jm  

2.2.3. Mối liên hệ giữa

và

R



và

  d



R A

u U

POS POS    

Mệnh đề 2.3. Cho bảng quyết định không đầy đủ Nếu

với mọi

thì

  u

  d







 IDS U A  

2.2.4. Mối liên hệ giữa

và



và

 IDS U A  ,

u U



 

  

R

, ,   

Mệnh đề 2.4. Cho bảng quyết định không đầy đủ thì Nếu

  d   u

  u

  d K A K A

  d K R K R

  d







R A .

2.2.5. Mối liên hệ giữa

và

R R



và

  d

 IDS U A 



u U

 

 



R A

u U ,   

Mệnh đề 2.5. Cho bảng quyết định không đầy đủ thì Nếu

  u

 A  R

2.2.6. Phân nhóm các phương pháp rút gọn thuộc tính

, R R

Nếu bảng quyết định nhất quán, các tập rút gọn ,

là như nhau.

TMR

Nếu bảng quyết định không nhất quán, mối liên hệ giữa các tập rút gọn

trong các nhóm như sau:

, RRR

R



,  MRRR





R



 Nếu

là một tập rút gọn thuộc Nhóm 3 thì tồn tại một tập rút gọn thuộc Nhóm 1 sao cho

thuộc Nhóm 2 và một tập rút gọn

2R R 1

 Nếu

là một tập rút gọn thuộc Nhóm 4 thì tồn tại một tập rút gọn thuộc Nhóm 1 sao cho

thuộc Nhóm 2 và một tập rút gọn

  R 2 R 3

2R R 1

  R 2 R 4

2.3. Đánh giá các phương pháp rút gọn thuộc tính

Chúng tôi đề xuất các độ đo mới và nghiên cứu sự thay đổi giá trị các độ đo đề xuất trên các tập rút gọn nhằm đánh giá các phương pháp rút gọn thuộc tính. Các kết quả trong phần này đã được tác giả công bố trong tài liệu [2].

2.3.1. Luật quyết định và các độ đo đánh giá hiệu năng

Yuhua Qian và các cộng sự, đã đưa ra độ chắc chắn, độ nhất quán và độ hỗ trợ của tập luật trong bảng quyết định không đầy đủ dựa trên khái niệm khối đồng nhất cực đại. Điểm hạn chế lớn nhất của công trình này là các tác giả chưa đánh giá được sự thay đổi giá trị của các độ đo này trên các tập rút gọn.

2.3.2. Đề xuất các độ đo mới đánh giá hiệu năng tập luật quyết định

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

với



  d

 u 1,...,

 IDS U A 



1..

n j ,

1..

RULE







tập luật

với

và .



   U SIM A Y U d i , ,





 S u A i





 des Y



  Z Z des S u ij i



, U   u n

Độ chắc chắn của IDS được định nghĩa



Y IDS

.

 



1 

  S u A i  S u A i

1    N 1 n  

Độ nhất quán

của IDS được định nghĩa



 



1 

  S u A i  S u A i

Y IDS   n 1 1   N n 1 1  1   

Độ hỗ trợ

của IDS được định nghĩa







 u i n

1 

là số luật quyết định (số lớp quyết định) sinh bởi lớp dung

sai

Ký hiệu . 

 S u A i

S Y  IDS  1 n m   n



Mệnh đề 2.6. Cho hai bảng quyết định không đầy đủ

IDS





RULE







và

, ,



 IDS U A  







 U B ,

   d

 des Y



  Z Z des S u i

n 1..



. Nếu

thì

 

 

 



với  

 S u A i '

   d    U SIM A Y U d , '

  

IDS IDS IDS IDS B A

, 



j 

1.. m '

IDS IDS  

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

, 

Mệnh đề 2.7. Cho hai bảng quyết định không đầy đủ

và

  d

 IDS U A 



  d

 U B ,



a) Nếu IDS nhất quán và B là một tập rút gọn miền dương (

) thì

IDS  

 



 







 



 







b) Nếu IDS không nhất quán và B là một tập rút gọn miền dương (

) PR

thì

IDS IDS 1 IDS IDS 1 IDS IDS    

 



 







 



 







Như vậy, tập rút gọn miền dương (

) làm giảm độ chắc chắn, giảm độ nhất quán và tăng độ hỗ trợ của tập luật đối với bảng quyết định không đầy đủ không nhất quán.

IDS IDS IDS IDS IDS IDS  

, 

Mệnh đề 2.8. Cho hai bảng quyết định không đầy đủ

  d

 IDS U A 



và . Nếu B là một tập rút gọn dựa trên hàm quyết định suy



 U B , IDS  rộng (

  d  ) thì

R

 



 







 



 







) bảo toàn

IDS IDS IDS IDS IDS IDS  

Như vậy, tập rút gọn dựa trên hàm quyết định suy rộng ( độ chắc chắn, độ nhất quán và tăng độ hỗ trợ của tập luật quyết định.

R



Mệnh đề 2.9. Cho hai bảng quyết định không đầy đủ

và

 IDS U A ,  . Nếu B là một tập rút gọn dựa trên khoảng cách (

   d ) thì

  d

 U B ,



IDS  

 



 







 



 







IDS IDS IDS IDS IDS IDS  

, 

Mệnh đề 2.10. Cho hai bảng quyết định không đầy đủ

và

  d

 IDS U A 



. Nếu B là một tập rút gọn phân bố (

) thì

  d

 U B ,



IDS   R

 



 







 



 







IDS IDS IDS IDS IDS IDS  

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

Bảng 2.5. Kết quả thử nghiệm sự thay đổi các độ đo đánh giá hiệu năng 1













Thuật toán POSBAR Thuật toán GDBAR U C STT Bộ số liệu R R

Hepatitis.data 155 0.909 0.819 0.598 0.909 0.819 0.504 3 3 19 1

Lung-cancer.data 32 1 0.814 1 0.814 4 4 56 1 1 2

Automobile.data 205 0.825 0.702 0.708 0.915 0.781 0.624 6 4 25 3

Anneal.data 798 0.804 0.713 0.586 0.852 0.755 0.503 7 6 38 4

435 15 1 0.616 15 1 0.616 16 1 1 5

Congressional Voting Records

Credit Approval 690 15 3 0.716 0.708 0.786 5 0.884 0.802 0.615 6

Bảng 2.6. Kết quả thử nghiệm sự thay đổi các độ đo đánh giá hiệu năng 2













Thuật toán MBAR Thuật toán DFBAR U C STT Bộ số liệu R R

Hepatitis.data 155 0.909 0.819 0.415 0.909 0.819 0.402 5 4 19 1

Lung-cancer.data 32 1 0.814 4 1 0.814 4 56 1 1 2

Automobile.data 205 0.915 0.781 0.518 0.915 0.781 0.518 8 8 25 3

Anneal.data 798 0.852 0.755 0.426 0.852 0.755 0.406 10 9 38 4

435 15 1 0.616 15 1 0.616 16 1 1 5

Congressional Voting Records

Hình 2.1 sau đây biểu diễn sự thay đổi của độ hỗ trợ  trên 6 bộ số liệu được chọn đối với các thuật toán: Thuật toán POSBAR, Thuật toán GDBAR, Thuật toán MBAR, Thuật toán DFBAR.

Credit Approval 690 15 7 0.884 0.802 0.487 6 0.884 0.802 0.512 6

Hình 2.1. Sự thay đổi độ hỗ trợ  trên các tập rút gọn

2.3.5. Lựa chọn, đánh giá các phương pháp rút gọn thuộc tính

1) Lựa chọn nhóm phương pháp phù hợp

1) Tập rút gọn

, tập rút gọn

và tập rút gọn

đều

bảo toàn độ chắc chắn của tập luật đối với bảng quyết định không đầy đủ nhất quán.

2) Tập rút gọn

làm giảm độ chắc chắc của tập luật đối với bảng

quyết định không đầy đủ không nhất quán

3) Tập rút gọn

, tập rút gọn

và tập rút gọn

đều bảo toàn độ

R R

chắc chắn của tập luật đối với bảng quyết định không đầy đủ không nhất quán.

R R

2) Đánh giá các phương pháp

Với bảng quyết định không đầy đủ nhất quán, các tập rút gọn tốt nhất của bốn nhóm phương pháp là như nhau nên chúng có chất lượng phân lớp như nhau. Với bảng quyết định không nhất quán, chúng tôi đánh giá ba nhóm phương pháp phù hợp (Nhóm 2, Nhóm 3, Nhóm 4) dựa trên tiêu chuẩn chất lượng phân lớp tập rút gọn của nhóm phương pháp.

Giả sử

là một tập rút gọn tốt nhất của các phương pháp thuộc

esDB t

Nhóm 3 (

tìm được bởi thuật toán heuristic sử dụng khoảng cách,

esDB t

lượng thông tin hay ma trận dung sai). Theo kết quả nghiên cứu về mỗi liên hệ giữa các tập rút gọn đã trình bày, tồn tại một tập rút gọn dựa trên hàm quyết định suy rộng

tối thiểu hơn

sao cho

(

esDB t

R R R   R R

Giả sử

là một tập rút gọn tốt nhất của các phương pháp thuộc

esB tR

Nhóm 2 (

tìm được bởi thuật toán heuristic sử dụng hàm quyết định

esB tR

suy rộng, tập rút gọn ấn định hay ma trận phân biệt). Ta có hai trường hợp.

- Nếu

chính là

, nghĩa là

) thì

(

tối thiểu

esB tR

DB t es

esB tR



esB tR

R R   es B t R

hơn

cao hơn

esDB t

esB tR

R R  . Theo Mệnh đề 2.6, độ hỗ trợ của tập luật dựa trên

độ hỗ trợ của tập luật dựa trên

, hay

có chất lượng phân lớp tốt

esDB t

esB tR

hơn

.esDB t R

- Nếu

khác

thì

có chất lượng phân lớp tốt hơn

esB tR

nên

esDB t

R R R có chất lượng phân lớp tốt nhất. Mặt khác, do R tốt hơn

về chất lượng phân lớp. Do đó,

tốt hơn

esDB t

esB tR

Do đó, trong cả hai trường hợp

có chất lượng phân lớp tốt hơn

R R R   về chất lượng phân lớp.

esB tR . Từ đó kết luận các phương pháp thuộc Nhóm 2 hiệu quả hơn các

esDB t

phương pháp thuộc Nhóm 3 theo tiêu chuẩn đánh giá chất lượng phân lớp của tập rút gọn.

Tương tự như trên ta có 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 4 theo tiêu chuẩn đánh giá chất lượng phân lớp của tập rút gọn.

Các phương pháp thuộc Nhóm 3 không so sánh được với các phương không có mối quan

pháp thuộc Nhóm 4 do tập rút gọn

và tập rút gọn

hệ.

R

2.4. Kết luận chương 2

Chương 2 luận án đã thực hiện các nội dung nghiên cứu sau:

(1) Phân nhóm các phương pháp rút gọn thuộc tính trong bảng quyết định không đầy đủ không nhất quán dựa vào kết quả nghiên cứu mối liên hệ giữa các khái niệm tập rút gọn, mối liên hệ giữa các tập rút gọn của các nhóm phương pháp. Dựa trên tập rút gọn, các phương pháp được phân ), Nhóm 2 (tập rút thành bốn nhóm: Nhóm 1 (Tập rút gọn miền dương

gọn dựa trên hàm quyết định suy rộng

, tập rút gọn ấn định

, tập rút

gọn dựa trên ma trận phân biệt

), Nhóm 3 (tập rút gọn dựa trên lượng

thông tin

, tập rút gọn dựa trên ma trận dung sai

, tập rút gọn dựa trên

TMR

R R

khoảng cách

), Nhóm 4 (Tập rút gọn phân bố

). Kết quả này được

công bố trong công trình [1].

(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ợ). Nghiên cứu sự thay đổi giá trị các độ đo đề xuất trên các tập rút gọn của bốn nhóm phương pháp. Trên cơ sở đó, lựa chọn và đánh giá các phương pháp rút gọn thuộc tính dựa trên tiêu chuẩn chất lượng phân lớp của tập rút gọn. Kết quả này được công bố trong công trình [2].

R

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 ĐỦ

3.1. Mở đầu

Trong chương này, trước hết chúng tôi giải quyết bài toán rút gọn dữ liệu bằng đề xuất phương pháp chọn tập đối tượng đại diện. Sau đó, chúng tôi đề xuất phương pháp sử dụng lượng thông tin mở rộng và phương pháp sử dụng hàm quan hệ. Chúng tôi chứng minh rằng cả 2 phương pháp này đều thuộc Nhóm 2 (theo phân nhóm phương pháp đã trình bày ở Chương 2).

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

Chọn tập đối tượng đại diện cho hệ thông tin không đầy đủ

3.2.1. Thuật toán 3.1. Chọn tập đối tượng đại diện của hệ thông tin không đầy đủ.

với

 IIS U A 





 u 1,...,

, U  u n

ma

A ,...,

AU  ,

với

;PU

IIS U  U P 

tính

với

 

a i

iA ..1 m ,    u U  ai U a / i

    u



    u

a i

   u

a i

v U S   

Uu

/ AU  ...   

Đầu vào: Hệ thông tin không đầy đủ  a 1 Đầu ra: Hệ thông tin không đầy đủ đại diện Bước 1: Đặt Bước 2: Với mỗi       v S   Bước 3: Tính u

  u

  u



  i u

a 1

m  i 1 

/ A 

k 1..



 X

   u với

và

kX

,..., 

k 1..

với  u i 1 i 

 u i l , đặt

;

 1 u i

U U  :P 

Giả sử AU / ,..., Bước 4: Với mọi Bước 5: Return

IIS  X  , / AUX i  , ; AU  ,

Chọn tập đối tượng đại diện cho bảng quyết định không đầy đủ

3.2.2. Thuật toán 3.2. Chọn tập đối tượng đại diện của bảng quyết định không đầy đủ.

, 

Đầu vào: Bảng quyết định không đầy đủ

với

 IDS U A 

   d



 a 1

ma

U A ,...,  u n

IDS  

 1,..., u Đầu ra: Bảng quyết định không đầy đủ đại diện

với

 U A , p

   d

;

PU  

U

tính

với

 

a i

iA ..1 m  ,   u U  ai U a / i

    u



    u

a i

   u

a i

v U S   

Uu

Bước 1: Đặt Bước 2: Với mỗi  Bước 3: Tính

với

/ AU   ...  

     v S   u

  u

   u

  u



a 1

  i u

m  i 1 

/ A 

 X

;

k 1..



Giả sử / AU ,..., Bước 4: Với mỗi

, thực hiện lặp các bước 4.1 và 4.2

kX / AUX i  ,

như sau:



Bước 4.1. Tính

với

. Giả sử

  d

   v X d u   i

   d v

X 

    u u ,...,



   Y d  1

j 1

j o

/ j  /i và Y l

   u . l 1..  , đặt

;

U U Y X / l 1.. 

 u X   với ,   d

 u

1

:P 

IDS   Y X ,..., Bước 4.2. Với mỗi Bước 5: Return  ;   u   U A , p j    d

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

3.3.1. Độ đo lượng thông tin mở rộng

AU  ,

Cho hệ thông tin đầy đủ

, với

, giả sử

 u 1

nu

IS U ,..., 

là phân hoạch sinh bởi tập thuộc tính

. Khi đó, lượng

 P 1

kP

UPEI  ,

, được tính

thông tin mở rộng của P trên tập đối tượng U, ký hiệu là bằng tổng khoảng cách Jaccard trung bình giữa tập U và như sau:

A / PU ,..., P 

 EI P U





1 

(3.1)

, 1 1     1   1 k 1 k P i U 1 k U P  i U P  i            

3.3.2. Xây dựng lượng thông tin mở rộng có điều kiện

 , AU

d  

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

và

với

 u 1

nu

IDS U ,...,  







ta có

là một phủ của U. Khi đó, ta xây

n

  , iUuuS i

A / SIMU P ..1 P    

 d

information quantity) của tập thuộc tính P đối với thuộc tính

, ký hiệu

là

, là trung bình cộng các lượng thông tin mở rộng thành phần

    CEI P d

 d

của thuộc tính

trên các tập đối tượng

. Giả sử



 p uS

i

14 dựng lượng thông tin mở rộng có điều kiện (conditional extended

    EI d S u i



, P

  d /

với

là số lớp tương đương của phân hoạch



i pk

 uS p

    EI d S u , i



Khi đó ta có:

1   1 P k i

(3.2)



    EI d S u , i



    CEI P d



1 

1    1   1 n 1 n 1 n 1 i k P 1 i k P      

 , AU

d  

và

, với

 u 1

nu

IDS U ,...,  





ta có

là một phủ của U. ta xây dựng

Cho bảng quyết định không đầy đủ n   , iUuuS i

 d

, ký hiệu là

lượng thông tin mở rộng có điều kiện của tập thuộc tính P và thuộc tính   , là trung bình cộng các lượng thông quyết định   CEI P d

 d

tin mở rộng thành phần của thuộc tính

trên các tập đối tượng

 p uS

i

A / SIMU ..1 P P    

Giả sử

với

là số lớp tương đương của



i pk

    EI d S u i



    EI d S u , i



  d /

phân hoạch

. Khi đó ta có:

 uS p

1   , P 1 P k i

(3.2)



    EI d S u , i



    CEI P d



1 

1    1   1 n 1 n 1 n 1 i k P 1 i k P      

3.3.3. Rút gọn thuộc tính sử dụng lượng thông tin mở rộng có điều

kiện

 , AU

d  

và tập

IDS  



Định nghĩa 3.1. Cho bảng quyết định không đầy đủ thuộc tính A     CEI R d

. Nếu     CEI A d

  r

 r R CEI R



    d

    CEI A d

thì R là một tập rút gọn của A dựa trên lượng thông tin mở rộng có điều kiện.

,    

 , AU

d  

. Độ quan trọng của thuộc tính b đối với tập thuộc tính B được

IDS A   B 

Định nghĩa 3.2. Cho bảng quyết định không đầy đủ và BAb  định nghĩa bởi:

  SIG b B

    CEI B d

 CEI B

     d b

  

Thuật toán 3.3 (Thuật toán EIQBAR). Thuật toán heuristic tìm một tập rút gọn sử dụng lượng thông tin mở rộng có điều kiện.

d  

 , AU

;R

Đầu vào: Bảng quyết định không đầy đủ Đầu ra: Một tập rút gọn 1. 2. Tính lượng thông tin mở rộng có điều kiện

và

;

    CEI A d

IDS  

    CEI R d // Thêm vào R các thuộc tính có độ quan trọng lớn nhất   3. While   CEI A d

    CEI R d



RAa 

tính

;

4. Begin For 5.

  SIG a R

 CEI R

     d a

  

    CEI R d  a



 SIG

a  

Chọn

sao cho

;

SIG RA   am Max RAa 

;

Tính

;

ma      CEI R d

doRa 

For each Begin

RR 

9. End; //Loại bỏ các thuộc tính dư thừa trong R nếu có 10. 11. 12. Tính

;



 a

then

;

13.

    CEI R d

      CEI R d a      d a

 CEI R

End; Return

14. 15.

 a

  RR  

Xét vòng lặp While từ dòng lệnh 3 đến 9, để tính vì

ta cần phải SIGR đã được tính ở bước trước, nghĩa

tính phải tính

 CEI R

     d a



  d /

là cần phải tính

. Theo Zhang và các

    CEI R d và phân hoạch

i



  u

cộng sự [9], độ phức tạp để tính

khi

đã được

  u với mọi

S S  R

 R uS

i

  u

Uui  S  R

  d /

tính là

, độ phức tạp để tính phân hoạch

với mọi

là



2UO 

  u

S Uui 

 a

. Do đó, độ phức tạp thời gian để tính tất cả các

ở dòng lệnh

2UO  số 5 là:

SIGR



 1







 ... 1 *



 / 2 *

 O A U



A A U A * A U       

với

là số thuộc tính điều kiện và

là số đối tượng. Độ phức tạp thời

A U

 2/1

 1



gian để chọn thuộc tính có độ quan trọng lớn nhất ở dòng lệnh số 6 là: 2 . Do đó, độ phức tạp thời gian của vòng

 AO

. Tương tự, độ phức tạp của vòng lặp For từ dòng

lặp While là

A * 1 A A   

. Vì vậy, độ phức tạp thời gian của Thuật

...   2 UAO

2

toán EIQBAR là

 2 UAO 2

 2 UAO

A 2 lệnh số 10 đến 14 là

3.3.4. Thử nghiệm và đánh giá kết quả

Chúng tôi chọn thuật toán MBAR tìm tập rút gọn của bảng quyết định không đầy đủ sử dụng metric để so sánh với thuật toán sử dụng lượng thông tin mở rộng đề xuất (Thuật toán EIQBAR) về thời gian thực hiện và kết quả thực hiện.

Bảng 3.4. Kết quả thực hiện thuật toán MBAR và Thuật toán EIQBAR

Thuật toán

MBAR

EIQBAR

U C

STT

Bộ số liệu

t

1.296 3

1.29

155

Hepatitis.data

0.171 4

0.17

Lung-cancer.data

1.687 6

1.68

205

Automobile.data

179

178

798

Anneal.data

435

Congressional Voting Records

16.7

16.73

690

Credit Approval

15.7

15.68

R R

17 Bảng 3.5. Tập rút gọn của thuật toán MBAR và Thuật toán EIQBAR

Tập rút gọn của

STT

Tập dữ liệu

Thuật toán MBAR

Thuật toán EIQBAR

Hepatitis.data

{1, 2, 4, 17}

{1, 2, 17}

Lung-cancer.data

{3, 4, 9, 43}

Automobile.data

{1, 8, 9, 13, 14, 20, 21, 24}

{1, 4, 13, 14, 20, 21}

Anneal.data

{1, 3, 4, 5, 8, 9, 33, 34, 35}

{1, 3, 4, 5, 8, 9, 34}

Congressional

{1, 2, 3, 4, 5, 7, 8, 9, 10, 11,

{1, 2, 3, 4, 5, 7, 8, 9,

Voting Records

12, 13, 14, 15, 16}

10, 11, 12, 13, 14, 15,

16}

Credit Approval

{1, 2, 3, 4, 5, 6, 8}

{1, 3, 4, 5, 8}

Kết quả thực hiện của hai thuật toán về tập rút gọn và tính toán giá trị

các độ chắc chắn , độ nhất quán , độ hỗ trợ  được mô tả ở Bảng 3.6 sau

đây:

Bảng 3.6. Kết quả tính toán độ chắc chắn, độ nhất quán và độ hỗ trợ trên các

tập rút gọn

Thuật toán EIQBAR

Thuật toán MBAR

U C

Bộ số liệu













R R

S T T

1 Hepatitis.data

155

0.909 0.819 0.504 4

0.909 0.819 0.415

Lung-cancer.data

0.814 4

0.814

3 Automobile.data

0.915 0.781 0.624 8

0.915 0.781 0.518

205

4 Anneal.data

0.852 0.755 0.503 9

0.852 0.755 0.426

798

435

15 1

0.616 15

0.616

Congressional Voting Records

Credit Approval

690

0.884 0.802 0.615 7

0.884 0.802 0.487

Hình 3.1 biễu diễn sự thay đổi độ hỗ trợ  trên hai tập rút gọn của hai

thuật toán EIQBAR và MBAR.

0.900

0.800

0.700

0.600

0.500

0.400

0.300

0.200

0.100

Thuật toán EIQBAR Thuật toán MBAR

0.000

A nneal.data

H epatitis.data

Credit A pproval

A uto m obile.data

Lung-cancer.data

C. V oting R ecords

Hình 3.1. Sự thay đổi độ hỗ trợ  trên hai tập rút gọn của thuật toán EIQBAR,

MBAR.

1) Kết quả thử nghiệm từ Bảng 3.4 và Bảng 3.5 cho thấy:

 Trên các bộ số liệu Lung-cancer.data, Congressional Voting Records,

tập rút gọn thu được bởi Thuật toán EIQBAR và Thuật toán MBAR là như

nhau. Tuy nhiên, với các bộ số liệu còn lại, tập rút gọn thu được bởi Thuật

toán EIQBAR tối thiểu hơn tập rút gọn thu được bởi Thuật toán MBAR.

Điều này cũng phù hợp với kết quả nghiên cứu về lý thuyết.

 Thời gian thực hiện Thuật toán EIQBAR và Thuật toán MBAR về cơ

bản là tương đương nhau.

2) Kết quả thử nghiệm từ Bảng 3.6 và Hình 3.1 cho thấy:

 Độ chắc chắn , độ nhất quán  của hai tập rút gọn thu được bởi hai

thuật toán EIQBAR và MBAR trên 6 bộ dữ liệu thử nghiệm là bằng nhau.

 Độ hỗ trợ của tập rút gọn thu được bởi Thuật toán EIQBAR cao hơn

độ hỗ trợ của tập rút gọn thu được bởi Thuật toán MBAR.

Phần tiếp theo, chúng tôi trình bày phương pháp rút gọn thuộc tính sử

dụng hàm quan hệ được xây dựng trên ma trận quan hệ. Phương pháp đề

xuất này cũng thuộc Nhóm 2.

3.4. Phương pháp rút gọn thuộc tính sử dụng hàm quan hệ

Trong phần này chúng tôi xây dựng thuật toán heuristic tìm một tập rút gọn tốt nhất sử dụng hàm quan hệ. Các kết quả trong phần này đã được tác giả công bố trong công bố [4].

3.4.1. Ma trận quan hệ và hàm quan hệ



Định nghĩa 3.3. Cho bảng quyết định không đầy đủ

với

  d

 IDS U A 

IDS

. Ma trận quan hệ của

trên tập thuộc chính

 , ký hiệu

, là ma trận vuông cấp n, mỗi phần tử có giá trị 0 hoặc 1, được

R R U n

R ij

và nxn định nghĩa như sau:

A  m M  R

 u

(1)

nếu

 ud



ijm

i

1R 

 u

(2)

nếu

 ud



ijm

i

0R 

" " X  Y 

Định nghĩa 3.4. Cho hai ma trận

và

. Hai quan hệ

và



 R ijx

R ijy

mxn

được định nghĩa như sau:

" "

(1)

khi và chỉ khi

R x  ij

R ij

X Y y i 1, 2,..., m j 1, 2,..., n  

(2)

khi và chỉ khi

R x  ij

R ij

X Y y i 1, 2,..., m j 1, 2,..., n  



R A

Định nghĩa 3.5. Cho hệ quyết định không đầy đủ

, với

  d

IDS

và

là ma trận quan hệ của

  IDS U A  trên tập thuộc tính

. Khi đó,

 m

R ij

nxn

R M  R

IDS

RDIS 

hàm quan hệ của

trên

, ký hiệu là

, được định nghĩa như sau:

 RDIS

với

R ijm

  

1 

1 n , 1 n i   j  

3.4.2. Rút gọn thuộc tính sử dụng hàm quan hệ



Định nghĩa 3.6. Cho bảng quyết định không đầy đủ

. Nếu

  d

 IDS U A 



thỏa mãn:

R A

 RDIS



(1)



' R

(2)



IDS

thì R được gọi là một tập rút gọn của

dựa trên hàm quan hệ.

Ta thấy rằng tập rút gọn sử dụng hàm quan hệ tương đương với tập rút gọn sử dựa trên hàm quyết định suy rộng. Do đó, phương pháp rút gọn thuộc tính sử dụng hàm quan hệ thuộc Nhóm 2

R ADIS ) (  ( ADIS )  RDIS



R A

Định nghĩa 3.7. Cho bảng quyết định không đầy đủ

  d

 IDS U A 



RAa 

. Độ quan trọng của thuộc tính

đối với tập thuộc tính

và được định nghĩa bởi

R a

  a

 RDIS

   a

RDIS 

   SIG out R



R A

Định nghĩa 3.8. Cho hệ quyết định không đầy đủ

và

  d

 IDS U A 



. Độ quan trọng của thuộc tính

trong tập thuộc tính

được định

Ra  nghĩa bởi

R a

  a

 RDIS



 RDIS

a  

  0a

 a

và

Từ đó ta có

Do đó,

và

   SIG in R

 a

SIG out R SIG out R SIG in R SIG in R

được   0a tính bởi lượng thay đổi hàm quan hệ khi thêm thuộc tính a vào R hoặc loại càng lớn thì lượng thay đổi này càng lớn, , bỏ a khỏi R và  a hay thuộc tính a càng quan trọng và ngược lại.

SIG out R SIG in R

Thuật toán 3.4.(RBAR) Thuật toán heuristic tìm một tập rút gọn tốt nhất sử dụng hàm quan hệ.



  d



 IDS U A 

R  

;

 RDIS



RAa 



;



   a

( ADIS ) 

  out SIG a R  a

SIG RA  

Đầu vào: Bảng quyết định không đầy đủ Đầu ra: Một tập rút gọn 1. // Thêm dần vào R các thuộc tính có độ quan trọng lớn nhất; 2.While 3.Begin 4. 5.

For each Chọn

tính sao cho

 DIS R  a ;  

  SIG

out R

 DIS R  Max RAa 

;



m a

R R  

then

;

 DIS R

  a



  a



R R   

6. 7.End; //Loại bỏ các thuộc tính dư thừa trong R nếu có; 8.For each a R  9. If DIS R  ;R 10. Return Giả sử

ADIS 

là

độ phức tạp để tính

, do đó độ phức tạp tính

là số đối tượng. Dễ thấy rằng .

là

là số thuộc tính điều kiện và  O kn

2

 O kn

2







Xét vòng lặp While từ dòng lệnh 2 đến dòng lệnh 7, độ phức tạp để tính . Độ phức tạp tất cả các

là

 1   





 SIG a R

 ... 1 *

  1 / 2 *



 thời gian để chọn

tính có độ quan

lớn nhất

  3 2 kn O k n trọng

... 1



   





là . Do đó, độ phức tạp của vòng lặp While là



 1



 1 / 2

thuộc 2  O k

. Tương tự, độ phức tạp của vòng lặp For là

. Vì vậy, độ

 3 2 O k n



 2 2 O k n



phức tạp của Thuật toán GDMBAR là

 3 2 O k n



3.4.3. Thử nghiệm và đánh giá kết quả

Bảng 3.5. Kết quả thực hiện thuật toán MBAR,

Thuật toán EIQBAR và Thuật toán RBAR

Thuật toán

MBAR

EIQBAR

RBAR

U C

STT

Bộ số liệu

t

1.296

1.29

1.56

Hepatitis.data

155

0.171

0.17

0.98

Lung-cancer.data

1.687

1.68

1.92

Automobile.data

205

179

178

196

Anneal.data

798

16.7

16.73

18.45

Congressional

435

Voting Records

Credit Approval

690

15.7

15.68

17.02

R R R

Bảng 3.6. Tập rút gọn của thuật toán MBAR,

Thuật toán EIQBAR và Thuật toán RBAR

STT Tập dữ liệu

Tập rút gọn của

MBAR

EIQBAR

RBAR

Hepatitis.data

{1, 2, 4, 17}

{1, 2, 17}

Lung-cancer.data

{3, 4, 9, 43}

Automobile.data

{1, 8, 9, 13, 14, 20,

{1, 4, 13, 14, 20,

21, 24}

21}

Anneal.data

{1, 3, 4, 5, 8, 9, 33,

{1, 3, 4, 5, 8, 9,

34, 35}

34}

Congressional

{1, 2, 3, 4, 5, 7, 8, 9,

{1, 2, 3, 4, 5, 7, 8,

Voting Records

10, 11, 12, 13, 14,

9, 10, 11, 12, 13,

15, 16}

14, 15, 16}

Credit Approval

{1, 2, 3, 4, 5, 6, 8}

{1, 3, 4, 5, 8}

Kết quả thử nghiệm cho thấy:

 Trên cả 6 bộ dữ liệu, tập rút gọn thu được bởi Thuật toán EIQBAR và

Thuật toán RBAR là như nhau. Điều này phù hợp với nghiên cứu lý thuyết,

phương pháp rút gọn thuộc tính sử dụng lượng thông tin mở rộng (Thuật

toán EIQBAR) và phương pháp rút gọn thuộc tính sử dụng hàm quan hệ

(Thuật toán RBAR) đều thuộc Nhóm 2.

 Trên các bộ số liệu nhất quán Lung-cancer.data, Congressional Voting

Records, tập rút gọn thu được bởi Thuật toán RBAR và Thuật toán MBAR

là như nhau. Tuy nhiên, với các bộ số liệu còn lại, tập rút gọn thu được bởi

MBAR. Điều này cũng phù hợp với kết quả nghiên cứu về lý thuyết.

 Thời gian thực hiện Thuật toán EIQBAR và Thuật toán MBAR về cơ

bản là tương đương nhau. Tuy nhiên, thời gian thực hiện của Thuật toán

RBAR lớn hơn thời gian thực hiện của Thuật toán EIQBAR. Bởi vì, độ

phức tạp thời gian của Thuật toán RBAR cao hơn so với Thuật toán

EIQBAR. Sở dĩ cao hơn là vì Thuật toán EIQBAR sử dụng công thức cải

tiến tính

với mọi

khi

đã được tính ở bước trước [17].

23 Thuật toán RBAR tối thiểu hơn tập rút gọn thu được bởi Thuật toán

 R uS

i

  u

Còn Thuật toán 3.4 tính ma trận phân biệt mở rộng trực tiếp từ các lớp

Uui  S  R

dung sai

với mọi

 R uS

i

Uui 

3.5. Kết luận chương 3

Chương 3 luận án đã thực hiện các nội dung nghiên cứu sau:

(1) Theo hướng tiếp cận rút gọn dữ liệu, chương 3 đề xuất kỹ thuật chọn tập đối tượng đại diện cho bài toán rút gọn thuộc tính trong hệ thông tin không đầy đủ và bảng quyết định không đầy đủ nhằm giảm thiểu thời gian thực hiện các thuật toán tìm tập rút gọn trên các bảng quyết định có dung lượng dữ liệu lớn. Kết quả này được công bố trong công trình [3].

(2) Đề xuất phương pháp rút gọn thuộc tính sử dụng lượng thông tin mở rộng và chứng minh phương pháp đề xuất thuộc Nhóm 2 (trong phân nhóm các phương pháp rút gọn thuộc tính được trình bày ở Chương 2). Kết quả này được công bố trong công trình [5].

(3) Đề xuất phương pháp rút gọn thuộc tính sử dụng hàm quan hệ và chứng minh phương pháp đề xuất cũng thuộc Nhóm 2 (trong phân nhóm các phương pháp rút gọn thuộc tính được trình bày ở Chương 2). Kết quả này được công bố trong công trình [4].

Các kết quả nghiên cứu này góp phần làm phong phú thêm về hướng nghiên cứu các phương pháp rút gọn thuộc tính trong bảng quyết định không đầy đủ.

KẾT LUẬN

1) Những kết quả chính của luận án:

Luận án tập trung giải quyết bài toán rút gọn thuộc tính trong bảng quyết định không đầy đủ ở bước tiền xử lý dữ liệu với các kết quả chính như sau:

(1) Phân nhóm các phương pháp rút gọn thuộc tính trên nguyên tắc: các phương pháp có định nghĩa độ đo tương đương nhau được phân vào một nhóm. Luận án chỉ ra các phương pháp rút gọn thuộc tính được phân thành bốn nhóm: Nhóm 1, Nhóm 2, Nhóm 3, Nhóm 4. Luận án cũng nghiên cứu mối liên hệ giữa các tập rút gọn của các nhóm phương pháp. Kết quả này được công bố trong công trình [1]

(2) Đề xuất các độ đo mới đánh giá hiệu năng tập luật quyết. Nghiên cứu sự thay đổi giá trị các độ đo đề xuất trên các tập rút gọn. Trên cơ sở đó, lựa chọn và đánh giá các phương pháp rút gọn thuộc tính trong các nhóm dựa trên tiêu chuẩn khả năng phân lớp của tập rút gọn. Kết quả này được công bố trong công trình [2]

(3) Theo hướng tiếp cận rút gọn dữ liệu, luận án đề xuất kỹ thuật chọn tập đố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 thời gian thực hiện các thuật toán tìm tập rút gọn trên các bảng quyết định có dung lượng dữ liệu lớn. Kết quả này được công bố trong công trình [3]

(4) Đề 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. Chứng minh phương pháp đề xuất sử dụng lượng thông tin mở rộng thuộc Nhóm 2. Kết quả này được công bố trong công trình [5]

(5) Đề xuất phương pháp mới rút gọn thuộc tính sử dụng hàm quan hệ. Chứng minh phương pháp đề xuất sử dụng hàm quan hệ cũng thuộc Nhóm 2. Kết quả này được công bố trong công trình [4].

2) Hướng phát triển của luận án:

Tiếp tục nghiên cứu và giải quyết bài toán rút gọn thuộc tính trong trường hợp bổ sung và loại bỏ tập đối tượng, tập thuộc tính theo hướng tiếp cận tính toán gia tăng bằng nhiều độ đo khác nhau nhằm tìm kiếm phương pháp hiệu quả.

DANH MỤC CÁC CÔNG TRÌNH CỦA TÁC GIẢ

CT1 Nguyen Long Giang, Vu Van Dinh, Relationships Among the Concepts of Reduct in Incomplete Decision Tables, Frontiers in Artificial Intelligence and Applications (FAIA), Volume 252: Advanced Methods and Technologies for Agent and Multi-Agent Systems, IOS Press, 2013, pp. 417-426.

CT2 Nguyễn Long Giang, Vũ Văn Định, Nghiên cứu sự thay đổi giá trị các độ đo đánh giá hiệu năng tập luật quyết định trên các tập rút gọn của bảng quyết định không đầy đủ, Kỷ yếu Hội nghị khoa học Công nghệ Quốc gia lần thứ VI - Nghiên cứu cơ bản và ứng dụng CNTT - FAIR6, Huế, 20-21/06/2013, Tr. 394-402.

CT3 Nguyễn Long Giang, Vũ Văn Định, “Chọn tập đối tượng đại diện cho bài toán rút gọn thuộc tính trong hệ thông tin không đầy đủ”, Kỷ yếu Hội nghị khoa học Công nghệ Quốc gia lần thứ VII - Nghiên cứu cơ bản và ứng dụng CNTT - FAIR7, Thái Nguyên, 20-21/06/2014, Tr. 51-59.

CT4 Vu Van Dinh, Nguyen Long Giang, Duc Thi Vu, Generalized Discernibility Function based Attribute Reduction in Incomplete Decision Systems, Serdica Journal of Computing 7 (2013), Institute of Mathematics and Informatics, Bulgarian Academy of Sciences, No 4, 2013, pp. 375-388.

CT5 Vũ Văn Định, Vũ Đức Thi, Ngô Quốc Tạo, Nguyễn Long Giang, “Phương pháp rút gọn thuộc tính trong bảng quyết định không đầy đủ sử dụng khoảng cách phân hoạch”, Chuyên san các công trình nghiên cứu, phát triển và ứng dụng CNTT-TT, Tạp chí Công nghệ thông tin &Truyền thông (Accepted).