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

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.
Nội dung trích xuất từ 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 Nghiên cứu khoa học công nghệ 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ạ: a : U  Va với Va 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: Tạp chí Nghiên cứu KH&CN Quân sự, Số 30, 04 - 2014 53  Kỹ thuật điện tử & Khoa học máy tính   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à u P , khi đó u P  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 BX  u  U u B  X  và BX  u  U u B  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 POSC ( D)    CD  Di U / D i là C-miền dương của D. Dễ thấy POSC ( 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 POSC ( 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 kh ...