Thuận toán nhanh tính toán lập thuộc tính lõi của bảng quyết định đưa vào vùng dương

Bài báo này nhằm trình bày một thuật toán mới cho phép làm giảm độ phức tạp của thuật toán. Dựa vào vùng dương, chúng tôi định nghĩa ma trận phân biệt đơn giản hóa và tập lõi tương ứng.
Nội dung trích xuất từ tài liệu:
Thuận toán nhanh tính toán lập thuộc tính lõi của bảng quyết định đưa vào vùng dươngTạp chí KHOA HỌC & CÔNG NGHỆ52(4): 41 - 464 - 2009THUẬT TOÁN NHANH TÍNH TOÁN TẬP THUỘC TÍNH LÕICỦA BẢNG QUYẾT ĐỊNH DỰA VÀO VÙNG DƢƠNG–)Phạm Quang Dũng (Trường Cao đẳng Giao thông vận tải)Tóm tắtTính toán tập (thuộc tính) lõi của bảng quyết định là một nội dung nghiên cứu quan trọng của lýthuyết tập thô. Một số học giả đã xây dựng thuật toán tính toán tập lõi dựa vào vùng dương và sử dụng matrận phân biệt. Độ phức tạp của thuật toán này làO C U2. Bài báo này nhằm trình bày một thuật toánmới cho phép làm giảm độ phức tạp của thuật toán. Dựa vào vùng dương, chúng tôi định nghĩa ma trận phânbiệt đơn giản hóa và tập lõi tương ứng. Chúng tôi chứng minh rằng tập lõi này tương đương với tập lõi xácđịnh thông qua ma trận phân biệt nguyên thủy. Vì việc xác định phân hoạch U/C là chìa khóa để tính toánma trận phân biệt đơn giản hóa, một thuật toán nhanh tính U/C được thiết kế sử dụng thuật sắp thứ tự theocơ số. Độ phức tạp của thuật toán là O C U . Sử dụng thuật toán nhanh xác định U/C và ma trận phânbiệt đơn giản hóa, một thuật toán mới xác định tập lõi dựa vào vùng dương được xây dựng. Độ phức tạp củathuật toán mới này được giảm thiểu và làmax O C U p os U / C , O C U.Từ khóa: Tập thô, Vùng dương, Ma trận phân biệt đơn giản hóa, Tập lõi, Độ phức tạp.Mở đầuLý thuyết tập thô [1], do Pawlak đề xuất năm1982, là một công cụ toán học mới để xử lý thôngtin không chính xác, không chắc chắn hay tri thứcmờ. Đến nay, lý thuyết tập thô đã và đang đượcứng dụng rộng rãi trong nhiều lĩnh vực: trí tuệnhân tạo, nhận dạng mẫu, khai phá tri thức vàkhám phá thông minh các luật quyết định.Tính toán tập (thuộc tính) lõi của bảng quyếtđịnh là một nội dung nghiên cứu quan trọng của lýthuyết tập thô. Cho đến nay, nhiều tác giả đãnghiên cứu đưa ra các thuật toán khác nhau tínhtoán tập lõi, trong đó có các thuật toán dựa vàovùng dương và sử dụng ma trận phân biệt. Trong[3], Hu đã đề xuất một thuật toán tính toán tập lõidựa vào ma trận phân biệt với độ phức tạp là2O C U .Trong bài này, để giảm thiểu độ phức tạp củathuật toán tính toán tập lõi, trước tiên chúng tôiđưa ra định nghĩa về ma trận phân biệt đơn giảnhóa và định nghĩa tập lõi tương ứng. Chúng tôichứng minh rằng tập lõi này tương đương với tậplõi xác định thông qua ma trận phân biệt nguyênthủy. Vì việc xác định phân hoạch U/C là bướcchính trong quá trình tính toán ma trận phân biệtđơn giản hóa, một thuật toán nhanh tính U/C đượcthiết kế sử dụng thuật sắp thứ tự theo cơ số. Độphức tạp của thuật toán là O C U . Sử dụngthuật toán nhanh xác định U/C, ma trận phân biệtđơn giản hóa, một thuật toán mới xác định tập lõidựa vào vùng dương được xây dựng. Độ phức tạpcủa thuật toán mới này được giảm xuống làmax O C U p os U / C , O C U ,trong đó U pos là tập các đại diện của các lớptương đương sinh bởi phân hoạch U/C.I.Ma trận phân biệt đơn giản hóa dựa vào vùngdương.Định nghĩa 2.1. [1]. Bảng quyết định là một bộ tứS U , C , D,V , f , trong đó Ux1 , x2 ,..., xnc1 , c2 ,..., cr là tập cáclà tập các đối tượng, Cthuộc tính điều kiện, D là tập các thuộc tính quyếtVa , trong đó Va làđịnh, C D; Va C D thuộcmiềngiátrịcủatínha;f : U (C D) V là hàm thông tin cho biếtgiá trị của mỗi thuộc tính tại mỗi đối tượng, nghĩalà a C D, x U , f x, a Va .C D xác địnhMỗi tập con thuộc tính Pmột quan hệ nhị phân, gọi là quan hệ không phânbiệt IND P :IND Px, y U U | a P, f x, a f y, a (1)1Tạp chí KHOA HỌC & CÔNG NGHỆ52(4): 41 - 46Dễ thấy, IND P là quan hệ tương đương. Ta4 - 2009U U p os . Khi đóU p osxi1 , xi2 ,..., xit , U negS U , C , D,V , f được gọi là bảng quyết địnhký hiệu phân hoạch của U sinh bởi IND P làđơnU / IND P hoặc ngắn gọn hơn là U / P . MỗiU /Cx1 , x2 ,..., xmccUx1 , x2 ,..., xm vàtập conxy U| apP, f x , af y, atrong U / P là một lớp tương đương.Định nghĩa 2.2. [1]. Cho bảng quyết địnhS U , C , D,V , f , X U và tập con thuộctínhTậpR C D.R_ XRi | Ri U / R, Ri X được gọilà xấp xỉ dưới của X theo R.Định nghĩa 2.3. [1]. Cho bảng quyết địnhS U , C , D, V , fGiảsửU / D D1 , D2 ,..., Dk ,U / C C1 , C2 ,..., Cm . Tập POSc D xácđịnh theo công thức POSc DC _ DiDi U / Dđược gọi là vùng dương của D theo C. NếuPOSC D U thì S được gọi là bảng quyết địnhnhất quán, trường hợp ngược lại là không nhất quán.Địnhlý2.1.ChoSPOSCU ,DC , D,V , f,X U /CXbảngquyếttađịnhcóX /D 1.Chứng minh: Suy ra trực tiếp từ Định nghĩa 2.3.Định nghĩa 2.4. Cho bảng quyết địnhS U , C , D, V , f .GiảsửPOSC Dxi1  xi2  ...  xit(theocc cU vàĐịnh lý 2.1),trong đó xi1 , xi2 ,..., xits 1, 2,..., t .Kýhiệuxis / D 1giảnhóa.c,Định nghĩa 2.5. [4]. Cho bảng quyết địnhS U , C , D,V , f . Với thuộc tính c C , nếuPOSC D POSC c D thì c được gọi làkhông cần thiết trong S, ngư ...