Tài liệu Phương pháp gia tăng rút gọn thuộc tính trong bảng quyết định thay đổi sử dụng khoảng cách - Nguyễn Long Giang
10 trang |
Chia sẻ: quangot475 | Lượt xem: 848 | Lượt tải: 0
Bạn đang xem nội dung tài liệu Phương pháp gia tăng rút gọn thuộc tính trong bảng quyết định thay đổi sử dụng khoảng cách - Nguyễn Long Giang, để tải tài liệu về máy bạn click vào nút DOWNLOAD ở trên
Nghiên cứu khoa học công nghệ
Tạp chí Nghiên cứu KH&CN Quân sự, Số 30, 04 - 2014 53
Ph¬ng ph¸p gi¸ t¨ng rót gän thuéc tÝnh
trong b¶ng quyÕt ®Þnh thay ®æi
sö dông kho¶ng c¸ch
NGUYỄN LONG GIANG*, VŨ VĂN HUÂN**
Tóm tắt: Trong hai thập kỷ trở lại đây, chủ đề nghiên cứu về rút gọn thuộc tính đã thu
hút đông đảo cộng đồng nghiên cứu về tập thô tham gia. Tuy nhiên, hầu hết các phương
pháp rút gọn thuộc tính đều thực hiện trên các bảng quyết định cố định, không thay đổi. Sử
dụng độ đo khoảng cách, trong bài báo này chúng tôi đề xuất các thuật toán tìm tập rút gọn
của bảng quyết định khi bổ sung và loại bỏ đối tượng. Vì không phải thực hiện lại thuật
toán trên toàn bộ tập đối tượng nên các thuật toán đề xuất giảm thiểu đáng kể độ phức tạp
về thời gian thực hiện.
Từ khóa: Tập thô, Bảng quyết định, Rút gọn thuộc tính, Tập rút gọn, Khoảng cách.
1. MỞ ĐẦU
Trong lý thuyết tập thô, chủ đề nghiên cứu về rút gọn thuộc tính đã và đang thu hút sự
quan tâm của đông đảo các nhà nghiên cứu [1]. Tuy nhiên, phần lớn 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 các bài toán 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 toán tìm tập rút gọn trên toàn bộ tập đối tượng, do đó chi phí
về thời gian thực hiện thuật toá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
[4,5,8,9]. Trong [4,5,9], 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 [8], 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 toán
entropy trong [8] còn phức tạp. Hơn nữa, các công trình trên chưa giải quyết đầy đủ các
trường hợp đối với bảng quyết định thay đổi với các trường hợp nêu trên.
Sử dụng độ đo khoảng cách trong công trình số [2], trong bài báo này chúng tôi đề xuất
hai thuật toán gia tăng tìm tập rút gọn của bảng quyết định trong trường hợp bổ sung và
loại bỏ đối tượng. Thuật toán đề xuất sử dụng độ đo khoảng cách nên giảm thiểu đáng kể
thời gian thực hiện so với các thuật toán sử dụng entropy Shannon trong [8].
Cấu trúc bài báo như sau. Phần 2 trình bày một số khái niệm cơ bản trong lý thuyết tập
thô. Phần 3 trình bày hai thuật toán tìm tập rút gọn sử dụng khoảng cách trong trường hợp
bổ sung và loại bỏ đối tượng. Phần 4 là kết luận và định hướng nghiên cứu tiếp theo.
2. CÁC KHÁI NIỆM CƠ BẢN
Phần này trình bày một số khái niệm cơ bản trong lý thuyết tập thô do Pawlak [7] đề
xuất. 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 a A xác định một ánh
xạ: : aa U V với aV là tập giá trị của thuộc tính a. Cho hệ thông tin ,IS U A , mỗi
tập thuộc tính P A xác định một quan hệ tương đương:
Kỹ thuật điện tử & Khoa học máy tính
N. L. Giang, V. V. Huân, “Phương pháp gia tăng rút gọn sử dụng khoảng cách.” 54
, ,IND P u v U U a P a u a v . Ký hiệu phân hoạch của U sinh bởi
quan hệ IND P là /U P và lớp tương đương chứa đối tượng u là
P
u , khi đó
,Pu v U u v IND P . Cho hệ thông tin ,IS U A . Với B A và X U ,
các tập BBX u U u X và BBX u U u X tương ứng gọi là B-
xấp xỉ dưới, B-xấp xỉ trên của X.
Bảng quyết định là một dạng đặc biệt của hệ thông tin, trong đó tập thuộc tính A bao gồm
hai tập con tách biệt nhau: tập các thuộc tính điều kiện C và tập các thuộc tính quyết định D.
Như vậy, bảng quyết định là một hệ thông tin ,DS U C D trong đó C D . Với
bảng quyết định ,DS U C D , ta gọi tập
/
( )
i
C i
D U D
POS D CD
là C-miền
dương của D. Dễ thấy ( )CPOS D là tập các đối tượng trong U được phân lớp đúng vào các lớp
quyết định của D nếu sử dụng tập thuộc tính điều kiện C. Bảng quyết định DS được gọi là nhất
quán khi và chỉ khi ( )CPOS D U , ngược lại DS là không nhất quán.
Rút gọn thuộc tính là lựa chọn tập con nhỏ nhất của tập thuộc tính điều kiện mà bảo toàn
thông tin phân lớp của bảng quyết định. Trong hai thập kỷ trở lại đây, nhiều phương pháp rút gọn
thuộc tính được công bố [1]. Mỗi phương pháp đều đưa ra một khái niệm về tập rút gọn và xây
dựng thuật toán heuristic tìm một tập rút gọn tốt nhất dựa trên tiêu chuẩn là chất lượng phân lớp
của thuộc tính. Các phương pháp điển hình được trình bày trong [1] là: phương pháp miền
dương, phương pháp sử dụng ma trận phân biệt, phương pháp sử dụng đại số quan hệ, phương
pháp sử dụng entropy thông tin, phương pháp sử dụng tính toán hạt, phương pháp sử dụng
khoảng cách (metric). Các nghiên cứu trong [1] cho thấy hầu hết các phương pháp rút gọn thuộc
tính đều thực hiện trên bảng quyết định cố định, không thay đổi. Dựa vào ý tưởng tính toán gia
tăng trong các công trình [4,5,9], phần tiếp theo chúng tôi trình bày phương pháp rút gọn
trong bảng quyết định thay đổi sử dụng khoảng cách trong hai trường hợp: bổ sung đối
tượng và loại bỏ đối tượng.
3. RÚT GỌN THUỘC TÍNH TRONG BẢNG QUYẾT ĐỊNH THAY ĐỔI
SỬ DỤNG KHOẢNG CÁCH
3.1. Khoảng cách giữa hai phân hoạch
Một khoảng cách trên tập hợp U là một ánh xạ : 0,d U U thỏa mãn các điều
kiện sau với mọi , ,x y z U [3]
1P , 0d x y , , 0d x y khi và chỉ khi x y .
2P , ,d x y d y x .
3P , , ,d x y d y z d x z .
Điều kiện P(3) được gọi là bất đẳng thức tam giác.
Trong công trình số [2], tác giả đã xây dựng công thức tính khoảng cách giữa hai phân
hoạch dựa trên độ đo entropy Liang [6].
Định nghĩa 1. [6] Cho bảng quyết định ,DS U C D với ,P Q C . Giả sử ta có
hai phân hoạch 1 2/ {P , ,...., }, mU P P P 1 2/ { , ,..., }nU Q Q Q Q . Entropy Liang có điều
kiện của Q khi đã biết P được định nghĩa bởi
Nghiên cứu khoa học công nghệ
Tạp chí Nghiên cứu KH&CN Quân sự, Số 30, 04 - 2014 55
1 1
( )
c c
n m
i ji j
i j
Q PQ P
E Q P
U U
với ,c ci i j jQ U Q P U P .
Mệnh đề 1. [2] Cho bảng quyết định ,DS U C D với ,P Q C . Giả sử
1 2/ { , ,..., }mK P U P P P P và 1 2/ { , ,..., }nK Q U Q Q Q Q . Khi đó
,d K P K Q E P Q E Q P .
là khoảng cách entropy giữa hai phân hoạch K P và K Q .
Mệnh đề 1 cho thấy công thức tính khoảng cách ,d K P K Q thỏa mãn điều kiện
bất đẳng thức tam giá P(3). Từ mệnh đề 1, chúng tôi xây dựng công thức tính khoảng cách
,d K B K B D như sau:
Mệnh đề 2. Cho bảng quyết định ,DS U C D với B C . Giả sử ta có hai phân
hoạch 1 2/ { , ,... }mK B U B X X X và 1 2/ { , ,..., }nK D U D Y Y Y . Khi đó:
2
1 1
1
,
n m
i j j i
i j
d K B K B D Y X X Y
U
Chứng minh. Với u U ta có
B D B D
u u u
, do đó các phần tử của phân
hoạch /U B D sẽ là i jY X khác rỗng với 1,...,i n và 1,...,j m . Từ đó ta có:
1 1 1 1
0
m n m ni j j i jj i j i j i ji j
j i j i
Y X X Y XX Y X Y X Y XY X
E BB D
U U U U
2
1 1 1 1
1n m n mi j j j i j
i j j i
i j i j
Y X C X Y X
E B D B Y X X Y
U U U
.
Do đó: 2
1 1
1
,
n m
i j j i
i j
d K B K B D Y X X Y
U
.
Định nghĩa 2. Cho bảng quyết định ,DS U C D và tập thuộc tính R C . Nếu
1) , ,d K R K R D d K C K C D
2) , ( , ) ( , )r R d K R r K R r D d K C K C D
thì R là một rút gọn của C dựa trên khoảng cách.
Phần tiếp theo, chúng tôi xây dựng công thức tính khoảng cách khi bổ sung và loại bỏ
đối tượng.
3.2. Công thức tính khoảng cách khi bổ sung một đối tượng mới
Cho bảng quyết định ,DS U C D với B C . Giả sử ta có hai phân hoạch
1 2/ { , ,... }mK B U B X X X và 1 2/ { , ,..., }nK D U D Y Y Y . Khoảng cách giữa
K B và K B D là ,Ud K B K B D .
Kỹ thuật điện tử & Khoa học máy tính
N. L. Giang, V. V. Huân, “Phương pháp gia tăng rút gọn sử dụng khoảng cách.” 56
Mệnh đề 3. Giả sử đối tượng x được bổ sung vào U , khi đó ta có:
1) Nếu jx X với mọi 1..j m và ix Y với mọi 1..i n thì
2
2
, ,
1
UU x
U
d K B K B D d K B K B D
U
2) Nếu jx X với mọi 1..j m và qx Y với q n thì
2
2
, ,
1
UU x
U
d K B K B D d K B K B D
U
3) Nếu px X với p m và ix Y với mọi 1..i n thì
22
1
, , 2
1
U pU x
d K B K B D U d K B K B D X
U
4) Nếu px X với p m và qx Y với q n thì
22
1
, , 2
1
U p qU x
d K B K B D U d K B K B D X Y
U
Chứng minh
1) Giả sử 1mX x , 1nY x . Ta có
1 1
2
1 1
1
,
1
n m
i j j iU x
i j
d K B K B D Y X X Y
U
1
1 1 1 12
1 1 1 1
1
1
n m m n
i j j i n j j n i m m i
i j j i
Y X X Y Y X X Y Y X X Y
U
2
2
,
1
U
U
d K B K B D
U
2) Giả sử 1mX x và qx Y với q n . Ta có:
1 1
2
1, 1 1
1
,
1
n m m
i j j i q j j qU x
i i q j j
d K B K B D Y X X Y Y x X X Y x
U
2
1, 1 1
1
1
n m m
i j j i q j j q
i i q j j
Y X X Y Y X X Y
U
2
2 2
1 1
1
,
1 1
n m
i j j i U
i j
U
Y X X Y d K B K B D
U U
3) Giả sử px X với p m và 1nY x . Ta có:
1 1
2
1 1, 1
1
,
1
n m n
i j j i i p p iU x
i j j p i
d K B K B D Y X X Y Y X x X x Y
U
2
1 1, 1
1
1
n m n
i j j i i p p i p
i j j p i
Y X X Y Y X x X x Y X x
U
Nghiên cứu khoa học công nghệ
Tạp chí Nghiên cứu KH&CN Quân sự, Số 30, 04 - 2014 57
22 2
1 1 1
1 1
, 2
1 1
n m n
i j j i i p p U p
i j i
Y X X Y Y X x X x U d K B K B D X
U U
4) Giả sử px X với p m và qx Y với q n . Ta có: ,U xd K B K B D
2 2
1, 1, 1,
1 1
1 1
n m m
i j j i q j j q
i i q j j p j j p
Y X X Y Y x X X Y x
U U
2 2
1,
1 1
1 1
n
q p p q i p p i
i i q
Y x X x X x Y x Y X x X x Y
U U
2 2 2
1 1 1,
1 1 1
1 1 1
n m n
i j j i p q i p
i j i i q
Y X X Y x X Y Y X x
U U U
221 ,
1
U p q q pU de K B K B D X Y U Y X
U
221 , 2
1
U p qU d K B K B D X Y
U
.
3.3. Công thức tính khoảng cách khi loại bỏ một đối tượng
Mệnh đề 4. Giả sử đối tượng x U bị loại khỏi U , khi đó ta có:
1) Nếu px X với p m và qx Y với q n thì
2
2
, ,
1
UU x
U
d K B K B D d K B K B D
U
2) Nếu px X với p m và qx Y với q n thì
2
2
, ,
1
UU x
U
d K B K B D d K B K B D
U
3) Nếu px X với p m và qx Y với q n thì
221, , 2 2
1
U pU x
d K B K B D U d K B K B D X
U
4) Nếu px X với p m và qx Y với q n thì
221, ,
1
U p q p q pU x
d K B K B D U d K B K B D X Y X Y X
U
Chứng minh
1) Giả sử mX x và nY x . Ta có
1 1
2
1 1
1
,
1
n m
i j j iU x
i j
d K B K B D Y X X Y
U
Kỹ thuật điện tử & Khoa học máy tính
N. L. Giang, V. V. Huân, “Phương pháp gia tăng rút gọn sử dụng khoảng cách.” 58
1
2
1 1 1 1
1
1
n m m n
i j j i n j j n i m m i
i j j i
Y X X Y Y X X Y Y X X Y
U
2
2
,
1
U
U
d K B K B D
U
2) Giả sử mX x và qx Y với q n . Ta có:
1 1
2
1, 1 1
1
,
1
n m m
i j j i q j j qU x
i i q j j
d K B K B D Y X X Y Y x X X Y x
U
2 2
1, 1 1 1 1
1 1
1 1
n m m n m
i j j i q j j q i j j i
i i q j j i j
Y X X Y Y X X Y Y X X Y
U U
2
2 ,
1
U
U
d K B K B D
U
3) Giả sử px X với p m và nY x . Ta có:
1 1
2
1 1, 1
1
,
1
n m n
i j j i i p p iU x
i j j p i
d K B K B D Y X X Y Y X x X x Y
U
2
1 1 1 1
1
1
n m n n
i j j i i p p i i p p i
i j i i
Y X X Y Y X X Y Y X x X x Y
U
1 1
2
1 1 1 1
1
1
1
n m n n
i j j i i p p i n p p n i p p i
i j i i
Y X X Y Y X X Y Y X X Y Y X X Y
U
22 2
1 1
1 1
2 2 , 2 2
1 1
n m
i j j i p U p
i j
Y X X Y X U d K B K B D X
U U
4) Giả sử px X với p m và qx Y với q n . Ta có: ,U xd K B K B D
2 2
1, 1, 1,
1 1
1 1
n m m
i j j i q j j q
i i q j j p j j p
Y X X Y Y x X X Y x
U U
2 2
1,
1 1
1 1
n
q p p q i p p i
i i q
Y x X x X x Y x Y X x X x Y
U U
2 2
1, 1, 1,
1 1
1 1
n m m
i j j i q j j q
i i q j j p j j p
Y X X Y Y X X Y
U U
2 2
1,
1 1
1 1
1 1
n
q p p q i p p i
i i q
Y X X Y Y X X Y
U U
221 ,
1
U p q p q pU d K B K B D X Y X Y X
U
Nghiên cứu khoa học công nghệ
Tạp chí Nghiên cứu KH&CN Quân sự, Số 30, 04 - 2014 59
3.4 Thuật toán tìm tập rút gọn khi bổ sung, loại bỏ đối tượng
Trước hết, chúng tôi xây dựng thuật toán gia tăng tìm tập rút gọn khi bổ sung một đối
tượng mới. Mệnh đề 5 sau đây là cơ sở để xây dựng thuật toán.
Mệnh đề 5. Cho bảng quyết định ,DS U C D với B C là một tập rút gọn của DS
dựa trên khoảng cách và x là đối tượng mới được bổ sung vào U. Giả sử ta có hai phân
hoạch 1 2/ { , ,... }mK B U B X X X , 1 2/ { , ,..., }nK C U C Y Y Y .
1) Nếu jx X với mọi 1..j m thì , ,U x U xd K B K B D d K C K C D
2) Nếu px X với p m và ix Y với mọi 1..i n thì
, ,U x U xd K B K B D d K C K C D
3) Nếu px X với p m và qx Y với q n thì
, ,U x U xd K B K B D d K C K C D
Chứng minh. Mục 1) và 2) được suy ra trực tiếp từ Mệnh đề 3 và Định nghĩa 2. Chúng tôi
chứng minh mục 3). Theo Mệnh đề 3 ta có:
221, , 2
1
U p rU x
d K B K B D U d K B K B D X D
U
với /rD U D , ,p rx X x D
221, , 2
1
U q rU x
d K C K C D U d K C K C D Y D
U
với ,q rx Y x D
Do B là tập rút gọn của DS nên , ,U Ud K B K B D d K C K C D , theo định
nghĩa ta có E D B E D C . Do B C nên q pY X . Nếu q pY X thì rõ ràng ta có
điều phải chứng minh. Nếu q pY X thì giả sử q p kY X X . Từ E D B E D C
theo [6] ta có ,p r k rX D X D hay ,p r q rX D Y D , do đó p rX D và
q rY D . Từ đó kết luận , ,U x U xd K B K B D d K C K C D .
Mệnh đề 5 cho thấy nếu x không thuộc một lớp tương đương nào trong /U B và /U C,
hoặc x đồng thời thuộc một lớp tương tương trong /U B và /U C thì các khoảng cách
,Ud K B K B D , ,Ud K C K C D được bảo toàn, nghĩa là không thay
đổi tập rút gọn. Từ đó chúng tôi xây dựng thuật toán tính gia tăng tập rút gọn như sau:
Thuật toán 1. Thuật toán gia tăng tìm tập rút gọn dựa trên khoảng cách
Đầu vào: Bảng quyết định ,DS U C D , tập rút gọn UR trên U và đối tượng
mới x.
Đầu ra: Tập rút gọn U xR trên U x .
1. Đặt UR R , tính 1 2/ { , ,... }mU R X X X ;
2. If , /p px X X U R then
3. Begin
4. Tính 1 2/ { , ,..., }nU C Y Y Y ;
Kỹ thuật điện tử & Khoa học máy tính
N. L. Giang, V. V. Huân, “Phương pháp gia tăng rút gọn sử dụng khoảng cách.” 60
5. If qx Y , 1..q n then
6. Begin
7. While , ,U x U xd K R K R D d K C K C D do
8. Begin
9. For a C R tính RSIG a ;
10. Chọn ma C R sao cho R m R
a C R
SIG a Max SIG a
;
11. mR R a ;
12. End;
13. End;
14. End;
15. For a R do
16. Begin
17. Tính ,U xd K R a K R a D ;
18. If , ,U x U xd K R a K R a D d K R K R D then R R a ;
19. End
20. Return R .
Theo [9], độ phức tạp để tính phân hoạch /U C là O C U , do đó độ phức tạp của
công thức tính gia tăng khoảng cách trong Mệnh đề 3 là
p q p qO C U m C U X Y O C U X Y . Độ phức tạp của vòng lặp
While từ dòng lệnh số 7 đến số 12 là p qO C C U X Y . Độ phức tạp của vòng lặp For
từ dòng lệnh số 15 đến 19 là p qO C C U X Y . Do đó, độ phức tạp của Thuât toán 1 là
2 p qO C U C X Y . Rõ ràng là p qX Y nhỏ hơn nhiều 2U nên độ phức tạp của Thuật
toán 1 tính gia tăng tập rút gọn nhỏ hơn nhiều thuật toán tính tập rút gọn bằng phương pháp truyền
thống [1].
Tương tự trường hợp bổ sung đối tượng mới, cơ sở xây dựng thuật toán tìm tập rút gọn
khi xóa một đối tượng là Mệnh đề 6 sau đây.
Mệnh đề 6. Cho bảng quyết định ,DS U C D với B C là một tập rút gọn của DS
dựa trên khoảng cách và x U . Giả sử 1 2/ { , ,... }mK B U B X X X ,
1 2/ { , ,..., }nK C U C Y Y Y .
1) Nếu jx X với mọi 1..j m thì
, ,U x U xd K B K B D d K C K C D
2) Nếu px X với p m và ix Y với mọi 1..i n thì
, ,U x U xd K B K B D d K C K C D
3) Nếu px X với p m và qx Y với q n thì
Nghiên cứu khoa học công nghệ
Tạp chí Nghiên cứu KH&CN Quân sự, Số 30, 04 - 2014 61
, ,U x U xd K B K B D d K C K C D
Sử dụng công thức tính khoảng cách khi loại bỏ một đối tượng trong Mệnh đề 4, Mệnh
đề 6 được chứng minh tương tự như Mệnh đề 5. Từ Mệnh đề 6, thuật toán tìm tập rút gọn
khi xóa một đối tượng được xây dựng tương tự như Thuật toán 1.
5. KẾT LUẬN
Trong bối cảnh các hệ cơ sở dữ liệu ngày càng lớn, thay đổi và cập nhật, việc đề xuất
các phương pháp hiệu quả nhằm tối ưu thời gian thực hiện các thuật toán tìm tập rút gọn là
mục tiêu của các nhà nghiên cứu. Dựa vào ý tưởng tính toán gia tăng, trong bài báo này
chúng tôi sử dụng độ đo khoảng cách để xây dựng hai thuật toán tìm tập rút gọn tương ứng
với hai trường hợp: bổ sung và loại bỏ đối tượng. Dựa vào hai thuật toán này, chúng tôi
hoàn toàn có thể xây dựng được thuật toán mở rộng để giải quyết trường hợp bổ sung tập
đối tượng hoặc loại bỏ tập đối tượng. Chúng tôi cũng chứng minh bằng lý thuyết độ phức
tạp thời gian của hai thuật toản nhỏ hơn độ phức tạp của thuật toán thực hiện theo phương
pháp truyền thống. Định hướng nghiên cứu tiếp theo của chúng tôi là sử dụng độ đo
khoảng cách đề xây dựng thuật toán tìm tập rút gọn trong trường hợp cập nhật các đối
tượng.
TÀI LIỆU THAM KHẢO
[1] Nguyễn Long Giang, “Nghiên cứu một số phương pháp khai phá dữ liệu theo
tiếp cận lý thuyết tập thô”, Luận án Tiến sĩ Toán học, Viện Công nghệ thông tin
(2012).
[2] Nguyễn Thanh Tùng,“Về một metric trên họ các phân hoạch của một tập hợp
hữu hạn”, Tạp chí Tin học và Điều khiển học, T.26, S.1 (2010), tr. 73-85.
[3] Deza M. M. and Deza E., “Encyclopedia of Distances”, Springer (2009).
[4] Guan L. H, “An incremental updating algorithm of attribute reduction set in
decision tables”, FSKD'09 Proceedings of the 6th international conference on
Fuzzy systems and knowledge discovery, Vol 2 (2009), pp. 421-425.
[5] Hu F., Wang G.Y., Huang H., Wu Y., “Incremental attribute reduction based
on elementary sets”, Proceedings of the 10th International Conference on Rough
Sets, Fuzzy Sets, Data Mining and Granular Computing, Regina, Canada
(2005), pp. 185-193.
[6] Liang J.Y, Chin K.S., Dang C.Y. and Richard C.M.YAM, “New method for
measuring uncertainty and fuzziness in rough set theory”, International Journal
of General Systems 31 (2002), pp. 331-342.
[7] Pawlak Z., Rough sets: Theoretical Aspects of Reasoning About Data, Kluwer
Aca-demic Publishers (1991).
[8] Wang F., Liang J. Y, Qian Y. H., “Attribute reduction: A dimension incremental
strategy”, Knowledge-Based Systems, Volume 39 (2013), pp. 95–108
[9] Zhang C. S, Jing Ruan J.,Tan Y. H., “An Improved Incremental Updating
Algorithm for Core Based on Positive Region, Journal of Computational
Information Systems“ 7: 9 (2011), pp. 3127-3133.
Kỹ thuật điện tử & Khoa học máy tính
N. L. Giang, V. V. Huân, “Phương pháp gia tăng rút gọn sử dụng khoảng cách.” 62
ABSTRACT
INCREMENTAL METHODS FOR ATTRIBUTE REDUCTION IN
DYNAMIC DECISION TABLES BASED ON DISTANCE.
In the last two decades, many attribute reduction methods in decision tables
have been developed. However, most of them can only be applicable to static
decision tables. In this paper, by using distance measure we propose algorithms for
attribute reduction in decision tables in two cases: adding objects, deleting objects.
By this approach, we show that the reduct of the dynamically-increasing decision
table do not recomputed, so this reduces significantly computational time and
memory space.
Keywords: Rough set, Decision table, Attribute reduction, Reduct, Distance.
Nhận bài ngày 11 tháng 12 năm 2013
Hoàn thiện ngày 04 tháng 02 năm 2014
Chấp nhận đăng ngày 10 tháng 03 năm 2014
Địa chỉ:
* Viện Công nghệ thông tin, Viện Hàn lâm Khoa học và Công nghệ Việt nam.
Email: nlgiang@ioit.ac.vn.
** Đại học Tài nguyên môi trường Hà Nội. Email: huanvn.tnmt@gmail.com.
Các file đính kèm theo tài liệu này:
- 09_53_62_8102_2149200.pdf