Đề xuất cải tiến lược đồ độ đo trong lý thuyết tập thô

Chia sẻ: Liễu Yêu Yêu | Ngày: | Loại File: PDF | Số trang:2

Thêm vào BST

Báo xấu

23
lượt xem 4
download

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

Bài viết "Đề xuất cải tiến lược đồ độ đo trong lý thuyết tập thô" nhằm 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. Mời các bạn cùng tham khảo!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Đề xuất cải tiến lược đồ độ đo trong lý thuyết tập thô

Hội nghị Quốc gia lần thứ 25 về Điện tử, Truyền thông và Công nghệ Thông tin (REV-ECIT2022) Đề Xuất Cải Tiến Lược Đồ Độ Đo Trong Lý Thuyết Tập Thô Nguyễn Đức Toàn, Vũ Quang Hưng và Ngô Thị Oanh Viện Công Nghệ Thông Tin, Học Viện Phụ Nữ Việt Nam Email: toannd@vwa.edu.vn, hungvq@vwa.edu.vn và oanh.ngo@vwa.edu.vn Abstract – Phương pháp giảm bớt thuộc tính là một Giả sử 𝑈 = {𝑆𝐴 (𝑥1 ), 𝑆𝐴 (𝑥2 ), … 𝑆𝐴 (𝑥𝑛 ) } và 𝑈 = 𝑆𝐼𝑀 (𝐴) {𝑏} bước rất quan trọng trong khai phá dữ liệu nói chung 𝑈 𝑈 và trong bảng quyết định không đầy đủ nói riêng. {(𝑉1 ), (𝑉2 ), … (𝑉𝑚 ) }. với 𝑆𝐴 (𝑢𝑖 ) ϵ ; 𝑉𝑗 ϵ và 𝑆𝐼𝑀 (𝐴) {𝑏} Nghiên cứu gần đây đưa ra một số giá trị thuộc tính 𝑆𝐴 (𝑢𝑖 )  𝑉𝑗 ≠ . cho bảng quyết định không đầy đủ trong lý thuyết tập Ký hiệu 𝑑𝑒𝑠 (𝑆𝐴 (𝑢𝑖 )) 𝑣à 𝑑𝑒𝑠(𝑉𝑗 ) lần lượt là các mô tả của thô nhằm tìm ra phương pháp hiệu quả nhất. Trong lớp dung sai 𝑆𝐴 (𝑢𝑖 ) và lớp tương đương 𝑉𝑗 . 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 𝑍𝑖𝑗 : 𝑑𝑒𝑠 (𝑆𝐴 (𝑢𝑖 )) → 𝑑𝑒𝑠(𝑉𝑗 ) (1) định không đầy đủ và chứng minh tính đúng đắn của 𝑉𝑗 (2)  𝑍𝑖𝑗 = 𝑆𝐴 (𝑢𝑖 )  các độ đo đề xuất. 𝑆𝐴 (𝑢𝑖 ) Keywords – Độ đo, bảng quyết định không đầy đủ, Giảm |𝑆 (𝑢𝑖 )  𝑉𝑗 | bớt thuộc tính. 𝑠(𝑍𝑖𝑗 ) = 𝐴 (3) |𝑈| I. GIỚI THIỆU |𝑆 (𝑢𝑖 )  𝑉𝑗 | (𝑍𝑖𝑗 ) = 𝐴 (4) Trong lý thuyết tập thô, lựa chọn một số tính năng quan |𝑉𝑗 | trọng để quyết định có giảm bớt hay không là hết sức cần Giả sử: thiết. Giảm bớt các đối tượng là một quá trình để tìm tập 𝑈 (5) 𝐹= = {(𝑉1 ), (𝑉2 ), … (𝑉𝑚 ) } hợp con tối ưu của các thuộc tính, giữ lại những thuộc tính {𝑏} quan trọng để đưa ra những quyết định chính xác nhất. Hầu là một phân lớp của 𝑈 theo b, độ chính xác của phân lớp F hết các thuật toán giảm bớt các đối tượng đều dựa vào theo 𝐴, ký hiệu là  𝐴  𝐹 , [4]: thông tin được thu thập từ miền dương [1]. Giảm bớt các ∑ 𝑉𝑖 ϵ 𝑈 |𝐴𝑉𝑖 | thuộc tính dựa trên lý thuyết tập thô có chứa dữ liêụ về các  𝐴  𝐹 = {𝑏} (6) đối tượng đặc trưng bởi tập hợp các thuộc tính hữu hạn. ∑ 𝑈 |𝐴𝑉𝑖 | 𝑉 ϵ 𝑖 Đối với một hệ thống thông tin, nếu các thuộc tính điều {𝑏} kiện và thuộc tính quyết định là khác nhau, thì nó được gọi Giả sử : IDS = {(𝑈, 𝐴  {𝑏})} với 𝑈 = {𝑥1 , 𝑥2 , … , 𝑥𝑛 } và là một hệ thống quyết định. Trong thực tế, có nhiều cách tập luật 𝑅𝑒𝑑 giảm bớt cho một bảng quyết định, tuy nhiên mức giảm tối 𝑅𝑒𝑑 = 𝑍𝑖𝑗 |𝑍𝑖𝑗 :𝑑𝑒𝑠 (𝑋𝑖 ) → 𝑑𝑒𝑠(𝑉𝑗 ) với (7) 𝑈 thiểu là NP-hard [2]. Do đó, có nhiều tác giả đề xuất những 𝑋𝑖  𝑀𝐶𝐴 ; 𝑉𝑗  , 𝑖 = 1 … 𝑛, 𝑗 = {𝑏} phương pháp khác nhau để làm giảm thuộc tính trong lý 1 … 𝑚. thuyết tập thô như: dựa trên miền dương, dựa trên ma trận, Khi đó: dựa trên độ đo entropy, tính toán hạt, dựa trên độ đo khoảng cách... Độ chắc chắn  của IDS: 𝑚 𝑁𝑖 Trong bài báo này, tác giả đưa ra cải tiến độ đo trong lý 1 1 |𝑋𝑖  𝑉𝑗 | 𝛼𝐼𝐷𝑆 = ∑ ∑ (8) thuyết tập thô cho bảng quyết định không đầy đủ, nhằm 𝑚 𝑁𝑖 |𝑋𝑖 | đánh giá các phương pháp theo tiêu chuẩn khả năng phân 𝑖=1 𝑗=1 lớp của tập rút gọn. Độ nhất quán 𝛽 của IDS: 𝑚 𝑁𝑖 Cấu trúc bài báo như sau: Phần I Giới thiệu; Phần II: Cơ 1 4 sở toán học; Phần III: Cải tiến độ đo để nâng cao hiệu năng 𝛽𝐼𝐷𝑆 = ∑ [1 − ∑|𝑋𝑖  𝑉𝑗 | 𝜇(𝑍𝑖𝑗 )(1 − 𝜇(𝑍𝑖𝑗 ))] (9) 𝑚 |𝑋𝑖 | trong bảng quyết định không đầy đủ. Phần IV: Kết luận và 𝑖=1 𝑗=1 tài liệu tham khảo. Độ hỗ trợ 𝛾 của IDS: 𝑛 𝑁𝑗 II. CƠ SỞ TOÁN HỌC |𝑉𝑗 | |𝑋𝑘  𝑉𝑗 | 𝛾𝐼𝐷𝑆 = ∑ ∑ Trong lý thuyết tập thô và các khái niệm trong bài báo có 𝑁𝑖 |𝑈| |𝑈| 𝑗=1 𝑘=1 thể tham khảo tại [3]. Cho bảng quyết định không đầy đủ 𝐼𝐷𝑆 = {(𝑈, 𝐴  {𝑏})} với 𝑈 = {𝑥1 , 𝑥2 , … , 𝑥𝑛 }. ISBN 978-604-80-7468-5 421
Hội nghị Quốc gia lần thứ 25 về Điện tử, Truyền thông và Công nghệ Thông tin (REV-ECIT2022) III. ĐỀ XUẤT CẢI TIẾN LƯỢC ĐỒ ĐỘ ĐO Do đó: TRONG LÝ THUYẾT TẬP THÔ  𝐼𝐷𝑆 ≥  𝐼𝐷𝑆 ′  (Điều phải chứng minh). Giả sử ta có : 𝐼𝐷𝑆 = {(𝑈, 𝐴  {𝑏})} với 𝑈 = {𝑛1 , 𝑛2 , … , 𝑛𝑛 } và tập luật 𝑅𝑒𝑑 3.2.2 Độ nhất quán 𝛽 của IDS: Ta có: 𝑅𝑒𝑑 = 𝔍𝑖𝑗 |𝔍𝑖𝑗 :𝑑𝑒𝑠 (𝔑𝑖 ) → 𝑑𝑒𝑠(𝔙𝑗 ) 𝑛 𝑁𝑖 với: 𝔑𝑖  𝔐𝐶𝐴 ; 1 1 |𝑆𝐴 (𝑢𝑖 ) 𝑉𝑗 | 1 𝑈 𝛽𝐼𝐷𝑆 = ∑[ ∑ ]− 𝔙𝑗  {𝑏} , 𝑖 = 1 … 𝑛, 𝑗 = 1 … 𝑚. 𝑛−1 𝑁𝑖 |𝑆𝐴 (𝑢𝑖 )| 𝑛−1 𝑖=1 𝑗=1 3.1 Cải tiến các độ đo 1 1 𝑛 1 - Độ chắc chắn  của IDS: = (∑ − ) 𝑛 𝑁𝑖 𝑛−1 𝑁𝑖 (𝐴) 𝑛 − 1 𝑖=1 1 1 |𝑆𝐴 (𝑢𝑖 ) 𝑉𝑗 | 𝑛 𝛼𝐼𝐷𝑆 = ∑ ∑ (11) 1 1 1 𝑛 𝑁𝑖 |𝑆𝐴 (𝑢𝑖 )| ≥ (∑ − ) 𝑖=1 𝑗=1 𝑛−1 𝑁𝑖 (𝐴) 𝑛 − 1 - Độ nhất quán 𝛽 của IDS: 𝑖=1 𝑁𝑖 (𝐵) 𝑛 1 1 1 |𝑆𝐵 (𝑢𝑖 ) 𝑉𝑗 | 𝑛 𝑁𝑖 = (∑ − ) ∑( 1 1 |𝑆𝐴 (𝑢𝑖 ) 𝑉𝑗 | 1 𝑛−1 𝑁𝑖 (𝐵) 𝑛 − 1 |𝑆𝐵 (𝑢𝑖 )| 𝛽𝐼𝐷𝑆 = ∑[ ∑ ]− (12) 𝑖=1 𝑗=1 𝑛−1 𝑁𝑖 |𝑆𝐴 (𝑢𝑖 )| 𝑛−1 1 𝑖=1 𝑗=1 − ) = 𝛽 𝐼𝐷𝑆 ′  𝑛−1 Do đó: - Độ hỗ trợ 𝛾 của IDS: 𝑛 𝑚 𝛽 𝐼𝐷𝑆 ≥ 𝛽 𝐼𝐷𝑆 ′  (Điều phải chứng minh). 1 |𝑆𝐴 (𝑢𝑖 ) 𝑉𝑗 | 𝛾𝐼𝐷𝑆 = ∑ ∑ (13) 𝑛 𝑛 3.2.3 Độ hỗ trợ 𝛾 của IDS: 𝑖=1 𝑗=1 𝑛 𝑚 Ký hiệu 𝑁𝑖 là số luật quyết định (số lớp quyết định) sinh 1 |𝑆𝐴 (𝑢𝑖 ) 𝑉𝑗 | 𝛾𝐼𝐷𝑆 = ∑ ∑ bởi lớp dung sai 𝑆𝐴 𝑢𝑖  . 𝑛 𝑛 𝑖=1 𝑗=1 Ta có: Nếu B  A thì 𝑆𝐴 (𝑢𝑖 )  𝑆𝐵 (𝑢𝑖 ) với mọi 𝑢𝑖  𝑈. -  𝐼𝐷𝑆 đạt giá trị lớn nhất là 1 nếu 𝜇(𝔍𝑖𝑗 ) = 1 với Ta có 𝑆𝐴 (𝑢𝑖 )  𝑉𝑗  𝑆𝐵 (𝑢𝑖 ) 𝑉𝑗 với mọi 𝑢𝑖  𝑈, ∀ 𝔍𝑖𝑗  𝑅𝑒𝑑, nghĩa là 𝐼𝐷𝑆 nhất quán, 𝑈 1 𝑉𝑗   |𝑆𝐴 (𝑢𝑖 ) 𝑉𝑗 | ≤ |𝑆𝐵 (𝑢𝑖 ) 𝑉𝑗 | -  𝐼𝐷𝑆 nhỏ nhất là : nếu 𝑁𝑖  𝑛 , nghĩa là 𝑚  𝑈 và {𝑏} 𝑛 𝑚 𝑛 𝑆𝐴 (𝑢𝑖 ) = 𝑈 với mọi 𝑢𝑖  𝑈 . 1 |𝑆𝐴 (𝑢𝑖 ) 𝑉𝑗 |  ∑∑ -  𝐼𝐷𝑆 đạt giá trị lớn nhất là 1 khi  𝐼𝐷𝑆 đạt giá trị lớn 𝑛 𝑛 𝑖=1 𝑗=1 nhất là 1 𝑛 𝑚 1 1 |𝑆𝐵 (𝑢𝑖 ) 𝑉𝑗 | -  𝐼𝐷𝑆 nhỏ nhất là 0 khi  𝐼𝐷𝑆) đạt giá trị nhỏ nhất là ≤ ∑∑ 𝑛 𝑛 𝑛 -  𝐼𝐷𝑆 đạt giá trị lớn nhất là 1 nếu 𝑆𝐴 (𝑢𝑖 ) = 𝑈 với mọi 𝑖=1 𝑗=1 𝑢𝑖  𝑈.  𝛾 𝐼𝐷𝑆 ≤ 𝛾𝐼𝐷𝑆 ′  (Điều phải chứng minh) 1 -  𝐼𝐷𝑆 nhỏ nhất là nếu 𝑆𝐴 (𝑢𝑖 )𝑢𝑖  với mọi 𝑢𝑖  𝑈. 𝑛 3.2 Chứng minh tính đúng đắn độ đo đề xuất IV. KẾT LUẬN Giả sử : 𝐼𝐷𝑆 = {(𝑈, 𝐴  {𝑏})}, 𝐼𝐷𝑆 ′ = {(𝑈, 𝐵  {𝑏})}, với Trong bài báo này, tác giả đã đưa ra cải tiến một số độ đo 𝑈 = {𝑥1 , 𝑥2 , … , 𝑥𝑛 } và tập luật 𝑅𝑒𝑑 và chứng minh tính đúng đắn của độ đo cải tiến, từ đó có 𝑅𝑒𝑑 = 𝔍𝑖𝑗 |𝔍𝑖𝑗 :𝑑𝑒𝑠 (𝔑𝑖 ) → 𝑑𝑒𝑠(𝔙𝑗 ) thể lựa chọn nhóm phương pháp cho phù hợp và tiến thành 𝑈 𝑈 với 𝑆𝐴 (𝑢𝑖 )  ; 𝔙𝑗  , thử nghiệm đánh giá sự thay đổi của các độ đo cải tiến trên 𝑆𝐼𝑀 (𝐴) {𝑏} bảng quyết định không đầy đủ. Trên cơ sở đó, lựa chọn và 𝑖 = 1 … 𝑛, 𝑗 = 1 … 𝑚. đánh giá các phương pháp giảm bớt thuộc tính dựa trên tiêu chuẩn độ hỗ trợ của tập luật. Nếu B  A thì  𝐼𝐷𝑆 ≥  𝐼𝐷𝑆 ′  ; 𝛽 𝐼𝐷𝑆 ≥ Định hướng tiếp theo là tiến hành thử nghiệm trên tập rút 𝛽 𝐼𝐷𝑆 ′  ; 𝛾 𝐼𝐷𝑆 ≤ 𝛾𝐼𝐷𝑆 ′  gọn miền dương, tập rút gọn dựa trên hàm quyết định suy 3.2.1 Độ chắc chắn  của IDS rộng, tập rút gọn dựa trên khoảng cách hoặc tập rút gọn Giả sử 𝑁𝑖 (𝐴), 𝑁𝑖 (𝐵) tương ứng là số luật quyết định sinh phân bố… bởi lớp dung sai: 𝑆𝐴 (𝑢𝑖 ) và 𝑆𝐵 (𝑢𝑖 ). Nếu B  A thì 𝑆𝐴 (𝑢𝑖 )  𝑆𝐵 (𝑢𝑖 ) với mọi 𝑢𝑖  𝑈. TÀI LIỆU THAM KHẢO Cho nên ta có thể suy ra: 𝑁𝑖 (𝐴) ≤ 𝑁𝑖 (𝐵). [1] Y.H. Qian, J.Y. Liang, W. Pedrycz, C.Y. Dang, (2011), “An Từ đó ta có: efficient accelerator for attribute reduction from incomplete data in 𝑛 𝑁𝑖 𝑛 rough set framework”, Pattern Recogn, pp 1658–1670. 1 1 |𝑆𝐴 (𝑢𝑖 ) 𝑉𝑗 | 1 1 [2] A. Skowron, C. Rauszer, (1992), The discernibility matrices and 𝛼𝐼𝐷𝑆 = ∑ ∑ = ∑ functions in information systems, Intelligent Decision Support. 𝑛 𝑁𝑖 |𝑆𝐴 (𝑢𝑖 )| 𝑛 𝑁𝑖 (𝐴) 𝑖=1 𝑗=1 𝑖=1 [3] Y.H. Qian, J.Y. Liang, W. Pedrycz, C.Y. Dang, (2010), “Positive 𝑛 approximation: an accelerator for attribute reduction in rough set 1 1 theory”, Artif. Intell, pp 597–618. ≥ ∑ 𝑛 𝑁𝑖 (𝐴) [4] Y. Leung, D.Y. Li, (2003), “Maximal consistent block technique 𝑖=1 for rule acquisition in incomplete information systems”, Information Sciences 153 pp85–106. 𝑛 𝑁𝑖 (𝐵) [5] Liang J.Y. and Qian Y.H. (2008), “Information granules and 1 1 |𝑆𝐵 (𝑢𝑖 ) 𝑉𝑗 | = ∑ ∑ =  𝐼𝐷𝑆 ′  entropy theory in information systems”, Information Sciences, Vol. 𝑛 𝑁𝑖 (𝐵) |𝑆𝐵 (𝑢𝑖 )| 𝑖=1 𝑗=1 51, pp. 1-18 ISBN 978-604-80-7468-5 422