intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE

Nghiên cứu cải tiến một số độ đo trong lý thuyết tập thô cho bảng quyết định không đầy đủ

Chia sẻ: ViPutrajaya2711 ViPutrajaya2711 | Ngày: | Loại File: PDF | Số trang:5

20
lượt xem
2
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Trong bài viết này, tác giả cải tiến một số độ đo nhằm nâng cao hiệu năng trong lý thuyết tập thô cho bảng quyết định không đầy đủ và chứng minh tính đúng đắn của các độ đo đề xuất.

Chủ đề:
Lưu

Nội dung Text: Nghiên cứu cải tiến một số độ đo trong lý thuyết tập thô cho bảng quyết định không đầy đủ

  1. ISSN: 1859-2171 TNU Journal of Science and Technology 225(06): 200 - 204 e-ISSN: 2615-9562 NGHIÊN CỨU CẢI TIẾN MỘT SỐ ĐỘ ĐO TRONG LÝ THUYẾT TẬP THÔ CHO BẢNG QUYẾT ĐỊNH KHÔNG ĐẦY ĐỦ Nguyễn Anh Tuấn Trường Cao đẳng Vĩnh Phúc TÓM TẮT Các phương pháp giảm bớt thuộc tính đều sử dụng các độ đo qua các lớp dung sai, như phương pháp sử dụng độ đo lượng thông tin (information quantity). Để giải quyết bài toán giảm bớt thuộc tính trực tiếp trên các bảng quyết định không đầy đủ và đánh giá sự thay đổi giá trị độ chắc chắn, độ nhất quán, độ hỗ trợ. Các độ đo này gặp khó khăn trong việc đánh giá tính hiệu quả (về khả năng phân lớp hay độ hỗ trợ của tập luật)... Trong bài báo này, tác giả cải tiến một số độ đo nhằm nâng cao hiệu năng trong lý thuyết tập thô cho bảng quyết định không đầy đủ và chứng minh tính đúng đắn của các độ đo đề xuất. Từ khóa: Lý thuyết tập thô, Độ đo, bảng quyết định không đầy đủ, nâng cao hiệu năng, Giảm bớt thuộc tính. Ngày nhận bài: 23/12/2019; Ngày hoàn thiện: 13/5/2020; Ngày đăng: 20/5/2020 RESEARCH ON IMPROVING SOME MEASUREMENTS IN CRUDE THEORETICAL OF INCOMPLETE DECISION TABLES Nguyen Anh Tuan Vinh Phuc College ABSTRACT Attribute reduction methods uses measurements by tolerance layers, such as the measurement of information quantity. To solve the problem of reducing attributes directly on the incomplete decision tables and assessing changes in the value of certainty, consistency, support. These measures have difficulty in assessing the effectiveness (in terms of the ability to classify or support the law set) ...In this paper, the author improved some measurements to improve performance in the crude theoretical for incomplete decision tables and proved the validity of the proposed measurements. Keywords: Tolerance Rough Set, measurements, incomplete decision tables, improve performance, attribute reduction. Received: 23/12/2019; Revised: 13/5/2020; Published: 20/5/2020 Email: tuanna573@gmail.com 200 http://jst.tnu.edu.vn; Email: jst@tnu.edu.vn
  2. Nguyễn Anh Tuấn Tạp chí KHOA HỌC & CÔNG NGHỆ ĐHTN 225(06): 200 - 204 1. Giới thiệu đánh giá các phương pháp theo tiêu chuẩn Trong lý thuyết tập thô, lựa chọn một số tính khả năng phân lớp của tập rút gọn. năng quan trọng để quyết định có giảm bớt Cấu trúc bài báo như sau: Phần I Giới thiệu; hay không là hết sức cần thiết. Giảm bớt các Phần II: Cơ sở toán học; Phần III: Cải tiến độ đối tượng là một quá trình để tìm tập hợp con đo để nâng cao hiệu năng trong bảng quyết tối ưu của các thuộc tính, giữ lại những thuộc định không đầy đủ. Phần IV: Kết luận và tài tính quan trọng để đưa ra những quyết định liệu tham khảo. chính xác nhất. Hầu hết các thuật toán giảm 2. Cơ sở toán học bớt các đối tượng đều dựa vào thông tin được 2.1.Định nghĩa hệ thông tin[5] thu thập từ miền dương [1]. Các phương pháp giảm bớt thuộc tính đều sử dụng các độ đo Hệ thông tin là 𝐼𝑆 = (𝑈, 𝐴) trong đó 𝑈 là tập qua các lớp dung sai, như phương pháp sử hữu hạn, khác rỗng các đối tượng; 𝐴 là tập dụng độ đo lượng thông tin [2]. Giảm bớt các hữu hạn, khác rỗng các thuộc tính. Với mọi thuộc tính dựa trên lý thuyết tập thô có chứa 𝑢  𝑈 , 𝑎  𝐴 ký hiệu giá trị thuộc tính 𝑎 tại dữ liệu về các đối tượng đặc trưng bởi tập hợp đối tượng 𝑢 là 𝑎 (𝑢) thay vì (𝑢, 𝑎). các thuộc tính hữu hạn. Đối với một hệ thống Nếu 𝐵 = {𝑏1 , 𝑏2 , … , 𝑏𝑛 }  A là một tập con thông tin, nếu các thuộc tính điều kiện và các thuộc tính thì ký hiệu bộ các giá trị 𝑏𝑖 (𝑢) thuộc tính quyết định là khác nhau, thì nó bởi 𝐵(𝑢). được gọi là một hệ thống quyết định. Như vậy, nếu 𝑢 và 𝑣 là hai đối tượng, thì Mục đích của việc giảm bớt các thuộc tính là 𝐵 (𝑢) = 𝐵 (𝑣) nếu 𝑏𝑖 (𝑢) = 𝑏𝑖 (𝑣) với mọi loại bỏ các thuộc tính dư thừa nhằm nâng cao =1, . . ., 𝑛. tính hiệu quả của các thuật toán. J. Dai và các Xét hệ thông tin 𝐼𝑆 = (𝑈, 𝐴). Mỗi tập con các cộng sự [3] xây dựng độ đo lượng thông tin thuộc tính 𝑃  𝐴 xác định một quan hệ hai tăng thêm mờ (fuzzy gain ratio) dựa trên ngôi trên 𝑈, ký hiệu là 𝐼𝑁𝐷 (𝑃) , xác định entropy mờ và xây dựng thuật toán bởi: GAIN_RATION_AS_FRS tìm tập giảm bớt 𝐼𝑁𝐷 (𝑃) = (𝑢 𝑣) 𝑈  𝑈|𝑎  𝑃 , 𝑎 (𝑢) = sử dụng lượng thông tin tăng thêm mờ. Thực 𝑎 (𝑣). nghiệm trên một số bộ dữ liệu mẫu cho thấy, 𝐼𝑁𝐷 (𝑃) là quan hệ P- không phân biệt được. độ chính xác phân lớp của các thuật toán Thấy rằng 𝐼𝑁𝐷 (𝑃) là một quan hệ tương FSCE, GAIN_RATION_AS_FRS cao hơn độ đương trên 𝑈. Nếu (𝑢, 𝑣)  𝐼𝑁𝐷 (𝑃) thì hai chính xác của các thuật toán sử dụng Entropy, đối tượng 𝑢 và 𝑣 không phân biệt được bởi lượng thông tin tăng thêm (gain ratio) theo các thuộc tính trong P. Quan hệ tương đương tiếp cận thô truyền thống. 𝐼𝑁𝐷 (𝑃) xác định một phân hoạch trên 𝑈, ký Trong thực tế, có nhiều cách giảm bớt cho hiệu là 𝑈 /𝐼𝑁𝐷 (𝑃) hay 𝑈 /𝑃 . Ký hiệu lớp một bảng quyết định, tuy nhiên mức giảm tối tương đương trong phân hoạch 𝑈 /𝑃 chứa đối thiểu là NP-hard [4]. Do đó, có nhiều tác giả tượng 𝑢 là [𝑢]𝑝 , khi đó: [𝑢]𝑝 = {𝑣 𝑈 |(𝑢, 𝑣) đề xuất những phương pháp khác nhau để làm  𝐼𝑁𝐷 (𝑃). giảm thuộc tính trong lý thuyết tập thô như: 2.2 Đặt bài toán dựa trên miền dương, dựa trên ma trận, dựa Cho bảng quyết định không đầy đủ 𝐼𝐷𝑆 = trên độ đo entropy, tính toán hạt, dựa trên độ {(𝑈, 𝐴  {𝑏})}, với 𝑈 = {𝑥1 , 𝑥2 , … , 𝑥𝑛 }. đo khoảng cách... 𝑈 Giả sử = {𝑆𝐴 (𝑥1 ), 𝑆𝐴 (𝑥2 ), … 𝑆𝐴 (𝑥𝑛 ) } Trong bài báo này, tác giả nghiên cứu cải tiến 𝑆𝐼𝑀 (𝐴) 𝑈 cải tiến một số độ đo trong lý thuyết tập thô và {𝑏} = {(𝑉1 ), (𝑉2 ), … (𝑉𝑚 ) }. với cho bảng quyết định không đầy đủ, nhằm http://jst.tnu.edu.vn; Email: jst@tnu.edu.vn 201
  3. Nguyễn Anh Tuấn Tạp chí KHOA HỌC & CÔNG NGHỆ ĐHTN 225(06): 200 - 204 𝑈 𝑆𝐴 (𝑢𝑖 ) ϵ ; |𝑆𝐴 (𝑢𝑖 )  𝑉𝑗 | (4) 𝑆𝐼𝑀 (𝐴) (𝑍𝑖𝑗 ) = 𝑉𝑗 ϵ 𝑈 và 𝑆𝐴 (𝑢𝑖 )  𝑉𝑗 ≠ . |𝑉𝑗 | {𝑏} Ký hiệu 𝑑𝑒𝑠 (𝑆𝐴 (𝑢𝑖 )) 𝑣à 𝑑𝑒𝑠(𝑉𝑗 ) lần lượt là Giả sử: các mô tả của lớp dung sai 𝑆𝐴 (𝑢𝑖 ) và lớp 𝑈 (5) 𝐹= tương đương 𝑉𝑗 . {𝑏} = {(𝑉1 ), (𝑉2 ), … (𝑉𝑚 ) } 𝑍𝑖𝑗 : 𝑑𝑒𝑠 (𝑆𝐴 (𝑢𝑖 )) → 𝑑𝑒𝑠(𝑉𝑗 ) (1) là một phân lớp của 𝑈 theo b, độ chính xác của 𝑉𝑗 (2)  𝑍𝑖𝑗 = 𝑆𝐴 (𝑢𝑖 )  phân lớp F theo 𝐴, ký hiệu là  𝐴 ( 𝐹) , [6]: 𝑆𝐴 (𝑢𝑖 ) ∑𝑉 𝑈 |𝐴𝑉𝑖 | |𝑆 (𝑢𝑖 )  𝑉𝑗 | 𝑖 ϵ {𝑏} 𝑠(𝑍𝑖𝑗 ) = 𝐴  𝐴 ( 𝐹) = (6) |𝑈| (3) ∑𝑉 𝑈 |𝐴𝑉𝑖 | 𝑖 ϵ {𝑏} Giả sử : IDS = {(𝑈, 𝐴  {𝑏})} với 𝑈 = {𝑥1 , 𝑥2 , … , 𝑥𝑛 } và tập luật 𝑅𝑒𝑑 𝑈 𝑅𝑒𝑑 = 𝑍𝑖𝑗 |𝑍𝑖𝑗 :𝑑𝑒𝑠 (𝑋𝑖 ) → 𝑑𝑒𝑠(𝑉𝑗 ) với 𝑋𝑖  𝑀𝐶𝐴 ; 𝑉𝑗  {𝑏} , 𝑖 = 1 … 𝑛, 𝑗 = 1 … 𝑚. (7) Khi đó: Độ chắc chắn  của IDS: 𝑚 𝑁𝑖 1 1 |𝑋𝑖  𝑉𝑗 | 𝛼(𝐼𝐷𝑆) = ∑ ∑ (8) 𝑚 𝑁𝑖 |𝑋𝑖 | 𝑖=1 𝑗=1 Độ nhất quán 𝛽 của IDS: 𝑚 𝑁𝑖 1 4 𝛽(𝐼𝐷𝑆) = ∑ [1 − ∑|𝑋𝑖  𝑉𝑗 | 𝜇(𝑍𝑖𝑗 )(1 − 𝜇(𝑍𝑖𝑗 ))] (9) 𝑚 |𝑋𝑖 | 𝑖=1 𝑗=1 Độ hỗ trợ 𝛾 của IDS: 𝑛 𝑁𝑗 |𝑉𝑗 | |𝑋𝑘  𝑉𝑗 | 𝛾(𝐼𝐷𝑆) = ∑ ∑ (10) 𝑁𝑖 |𝑈| |𝑈| 𝑗=1 𝑘=1 3. Cải tiến độ đo trong lý thuyết tập thô cho bảng quyết định không đầy đủ Giả sử ta có : 𝐼𝐷𝑆 = {(𝑈, 𝐴  {𝑏})} với 𝑈 = {𝑥1 , 𝑥2 , … , 𝑥𝑛 } và tập luật 𝑅𝑒𝑑 𝑈 𝑅𝑒𝑑 = 𝑍𝑖𝑗 |𝑍𝑖𝑗 :𝑑𝑒𝑠 (𝑋𝑖 ) → 𝑑𝑒𝑠(𝑉𝑗 ) với 𝑋𝑖  𝑀𝐶𝐴 ; 𝑉𝑗  {𝑏} , 𝑖 = 1 … 𝑛, 𝑗 = 1 … 𝑚. 3.1. Cải tiến các độ đo Độ chắc chắn  của IDS: 𝑛 𝑁𝑖 1 1 |𝑆𝐴 (𝑢𝑖 ) 𝑉𝑗 | 𝛼(𝐼𝐷𝑆) = ∑ ∑ (11) 𝑛 𝑁𝑖 |𝑆𝐴 (𝑢𝑖 )| 𝑖=1 𝑗=1 Độ nhất quán 𝛽 của IDS: 202 http://jst.tnu.edu.vn; Email: jst@tnu.edu.vn
  4. Nguyễn Anh Tuấn Tạp chí KHOA HỌC & CÔNG NGHỆ ĐHTN 225(06): 200 - 204 𝑛 𝑁𝑖 1 1 |𝑆𝐴 (𝑢𝑖 ) 𝑉𝑗 | 1 𝛽(𝐼𝐷𝑆) = ∑[ ∑ ]− (12) 𝑛−1 𝑁𝑖 |𝑆𝐴 (𝑢𝑖 )| 𝑛−1 𝑖=1 𝑗=1 Độ hỗ trợ 𝛾 của IDS: 𝑛 𝑚 1 |𝑆𝐴 (𝑢𝑖 ) 𝑉𝑗 | 𝛾(𝐼𝐷𝑆) = ∑ ∑ (13) 𝑛 𝑛 𝑖=1 𝑗=1 Ký hiệu 𝑁𝑖 là số luật quyết định (số lớp quyết định) sinh bởi lớp dung sai 𝑆𝐴 (𝑢𝑖 ) . Ta có:  (𝐼𝐷𝑆) đạt giá trị lớn nhất là 1 nếu 𝜇(𝑍𝑖𝑗 ) = 1 với ∀ 𝑍𝑖𝑗  𝑅𝑒𝑑, nghĩa là 𝐼𝐷𝑆 nhất 1 quán, và  (𝐼𝐷𝑆) nhỏ nhất là : nếu 𝑁𝑖 = 𝑛 , nghĩa là 𝑚 = 𝑈 và 𝑆𝐴 (𝑢𝑖 ) = 𝑈 với mọi 𝑢𝑖  𝑈 . 𝑛  (𝐼𝐷𝑆) đạt giá trị lớn nhất là 1 khi  (𝐼𝐷𝑆 đạt giá trị lớn nhất là 1 và  (𝐼𝐷𝑆 nhỏ nhất là 0 khi 1  (𝐼𝐷𝑆) đạt giá trị nhỏ nhất là 𝑛 . 1  (𝐼𝐷𝑆) đạt giá trị lớn nhất là 1 nếu 𝑆𝐴 (𝑢𝑖 ) = 𝑈 với mọi 𝑢𝑖  𝑈.  (𝐼𝐷𝑆) nhỏ nhất là 𝑛 nếu 𝑆𝐴 (𝑢𝑖 )=𝑢𝑖  với mọi 𝑢𝑖  𝑈. 3.2. Chứng minh tính đúng đắn độ đo đề xuất Giả sử : 𝐼𝐷𝑆 = {(𝑈, 𝐴  {𝑏})}, 𝐼𝐷𝑆 ′ = {(𝑈, 𝐵  {𝑏})}, với 𝑈 = {𝑥1 , 𝑥2 , … , 𝑥𝑛 } và tập luật 𝑅𝑒𝑑 𝑅𝑒𝑑 = 𝑍𝑖𝑗 |𝑍𝑖𝑗 :𝑑𝑒𝑠 (𝑆𝐴 (𝑢𝑖 )) → 𝑑𝑒𝑠(𝑉𝑗 ) 𝑈 𝑈 với 𝑆𝐴 (𝑢𝑖 ) 𝑆𝐼𝑀 (𝐴) ; 𝑉𝑗  {𝑏} , 𝑖 = 1 … 𝑛, 𝑗 = 1 … 𝑚. Nếu B  A thì  (𝐼𝐷𝑆) ≥  (𝐼𝐷𝑆 ′ ) ; 𝛽 (𝐼𝐷𝑆) ≥ 𝛽 (𝐼𝐷𝑆 ′ ) ; 𝛾 (𝐼𝐷𝑆) ≤ 𝛾(𝐼𝐷𝑆 ′ ) + Độ chắc chắn  của IDS Giả sử 𝑁𝑖 (𝐴), 𝑁𝑖 (𝐵) tương ứng là số luật quyết định sinh bởi lớp dung sai: 𝑆𝐴 (𝑢𝑖 ) và 𝑆𝐵 (𝑢𝑖 ). Nếu B  A thì 𝑆𝐴 (𝑢𝑖 )  𝑆𝐵 (𝑢𝑖 ) với mọi 𝑢𝑖  𝑈. Cho nên ta có thể suy ra: 𝑁𝑖 (𝐴) ≤ 𝑁𝑖 (𝐵). Từ đó ta có: 𝑛 𝑁𝑖 𝑛 1 1 |𝑆𝐴 (𝑢𝑖 ) 𝑉𝑗 | 1 1 𝛼(𝐼𝐷𝑆) = ∑ ∑ = ∑ 𝑛 𝑁𝑖 |𝑆𝐴 (𝑢𝑖 )| 𝑛 𝑁𝑖 (𝐴) 𝑖=1 𝑗=1 𝑖=1 𝑛 1 1 ≥ ∑ 𝑛 𝑁𝑖 (𝐴) 𝑖=1 𝑛 𝑁𝑖 (𝐵) 1 1 |𝑆𝐵 (𝑢𝑖 ) 𝑉𝑗 | = ∑ ∑ =  (𝐼𝐷𝑆 ′ ) 𝑛 𝑁𝑖 (𝐵) |𝑆𝐵 (𝑢𝑖 )| 𝑖=1 𝑗=1 Do đó:  (𝐼𝐷𝑆) ≥  (𝐼𝐷𝑆 ′ ) (Điều phải chứng minh) + Độ nhất quán 𝛽 của IDS: Ta có: http://jst.tnu.edu.vn; Email: jst@tnu.edu.vn 203
  5. Nguyễn Anh Tuấn Tạp chí KHOA HỌC & CÔNG NGHỆ ĐHTN 225(06): 200 - 204 𝑛 𝑁𝑖 1 1 |𝑆𝐴 (𝑢𝑖 ) 𝑉𝑗 | 1 𝛽(𝐼𝐷𝑆) = ∑[ ∑ ]− 𝑛−1 𝑁𝑖 |𝑆𝐴 (𝑢𝑖 )| 𝑛−1 𝑖=1 𝑗=1 𝑛 𝑛 1 1 1 1 1 1 = (∑ − ) ≥ (∑ − ) 𝑛−1 𝑁𝑖 (𝐴) 𝑛 − 1 𝑛−1 𝑁𝑖 (𝐴) 𝑛 − 1 𝑖=1 𝑖=1 𝑛 𝑁𝑖 (𝐵) 1 1 1 |𝑆𝐵 (𝑢𝑖 ) 𝑉𝑗 | 1 = (∑ − ) ∑( − ) 𝑛−1 𝑁𝑖 (𝐵) 𝑛−1 |𝑆 (𝑢 𝐵 𝑖 )| 𝑛−1 𝑖=1 𝑗=1 = 𝛽 (𝐼𝐷𝑆 ′ ) Do đó: 𝛽 (𝐼𝐷𝑆) ≥ 𝛽 (𝐼𝐷𝑆 ′ ) (Điều phải chứng minh) + Độ hỗ trợ 𝛾 của IDS: 𝑛 𝑚 1 |𝑆𝐴 (𝑢𝑖 ) 𝑉𝑗 | 𝛾(𝐼𝐷𝑆) = ∑ ∑ 𝑛 𝑛 𝑖=1 𝑗=1 Nếu B  A thì 𝑆𝐴 (𝑢𝑖 )  𝑆𝐵 (𝑢𝑖 ) với mọi 𝑢𝑖  𝑈. 𝑈 Ta có 𝑆𝐴 (𝑢𝑖 )  𝑉𝑗  𝑆𝐵 (𝑢𝑖 ) 𝑉𝑗 với mọi 𝑢𝑖  𝑈, 𝑉𝑗  {𝑏}  |𝑆𝐴 (𝑢𝑖 ) 𝑉𝑗 | ≤ |𝑆𝐵 (𝑢𝑖 ) 𝑉𝑗 | 𝑛 𝑚 𝑛 𝑚 1 |𝑆𝐴 (𝑢𝑖 ) 𝑉𝑗 | 1 |𝑆𝐵 (𝑢𝑖 ) 𝑉𝑗 |  ∑∑ ≤ ∑∑ 𝑛 𝑛 𝑛 𝑛 𝑖=1 𝑗=1 𝑖=1 𝑗=1  𝛾 (𝐼𝐷𝑆) ≤ 𝛾(𝐼𝐷𝑆 ′ ) Điều phải chứng minh 4. Kết luận [2]. J. Y. Liang and Y. H. Qian, “Information granules and entropy theory in information Trong bài báo này, tác giả đã nghiên cứu cải systems,” Information Sciences, vol. 51, pp. tiến một số độ đo và chứng minh tính đúng 1-18, 2008. đắn, từ đó có thể lựa chọn nhóm phương pháp [3]. J. Dai, and Q. Xu, “Attribute selection base on cho phù hợp và tiến thành thử nghiệm đánh information gain ratio in fuzzy rough set giá sự thay đổi của các độ đo cải tiến trên theory with application to tumor classification,” Applied Soft Computing, vol. bảng quyết định không đầy đủ. Trên cơ sở đó, 13, no. 2013, pp. 211-211, 2013. lựa chọn và đánh giá các phương pháp giảm [4]. A. Skowron, and C. Rauszer, The bớt thuộc tính dựa trên tiêu chuẩn độ hỗ trợ discernibility matrices and functions in của tập luật. information systems. Intelligent Decision Support, 1992. [5]. Y. Leung, and D. Y. Li, “Maximal consistent TÀI LIỆU THAM KHẢO/ REFERENCES block technique for rule acquisition in [1]. Y. H. Qian, J. Y. Liang, W. Pedrycz, and C. incomplete information systems,” Information Y. Dang, “Positive approximation: an Sciences, vol. 153, pp. 85-106, 2003. accelerator for attribute reduction in rough set [6]. J. Y. Liang and Y. H. Qian, “Information theory,” Artif. Intell, vol. 174, pp. 597-618, granules and entropy theory in information systems,” Information Sciences, vol. 51, pp. 2010. 1-18, 2008. 204 http://jst.tnu.edu.vn; Email: jst@tnu.edu.vn
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

 

Đồng bộ tài khoản
2=>2