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