Luận văn Thạc sĩ Hệ thống thông tin: Nghiên cứu một số thuật toán gia tăng lựa chọn thuộc tính trên bảng quyết định động theo tiếp cận tập mờ sử dụng lát cắt α

BO CONG THVdNG TRUONG D~I .HQC CONG NGH1¢P HA N LOI CAM DOAN Toi la Tr~n Phi Lire, hoc vien cao hoc lop Cao hoc h~ thong thong tin kh6a 12. Toi cam dean rang d~ an thac sl mang tua d~ "Nghien ciru mot s6 thuat toan gia tang hra chon thuoc tinh tren bang quyet dinh dong theo tiep can t~p ma sir dung lat cit a" dUQ'C trinh bay diroi day la Cong trinh nghien CU'U CUa chinh toi duoi sir huong d~n cua TS. Dang Trong Hop. Cac noi dung nghien CU'U va k~t qua trong d~ tai nay la trung thirc va chira tung duce ai cong b6 trong bfit cu cong trinh nghien ciru nae tnroc day. Nhirng s6 lieu trong CaC bang bi~U phuc V\1 Cho viec phan tich, nhan xet, danh gia dUQ'C chinh tac gia thu thap tu cac nguon khac nhau c6 ghi trong phan tai lieu tham khao. Toi cam doan rang khong co bfit ky vi pham nao d6i voi cac quy dinh dao due nghien ciru khoa hoc trong qua trinh thuc hien luan an. Cac tai lieu tham khao duoc trich d~n dung nguon g6c va duce sir dung mot each hop ly. Toi hi~u ro rang neu phat hien bfit ky sai s6t, vi pham hoac gian l?n nao trong d~ an cua minh, toi se chiu trach nhiem tnroc phap luat va c6 th~ bi xem xet lai v~ bang c~p da dat duoc, Toi vi~t cam doan nay va toi hoan toan chiu trach nhiem v~ tinh chinh xac Va trung thirc Cua Cong trinh nghien CUU nay. Ha Noi, ngay ..... thong ..... ndm 2024 Tac gia 11 Ml}C Ll}C ' LOI CAM DOAN I MVC LVC 11 DANH MVC c~c KY_HitU, cAc CHU VIET TAT III DANH MV c H~NH '\::E ··········:····································································· IV DANH MVC CAC BANG BIEU ? 1 v MO DAU 1 CHUONG I. TONG QUAN VE LY THUYET T~P THO, T~P THO MO VA. cAc UNG DVNG TRONG BA.I TOAN RUT GQN THU(>C TiNH .. 5 1.1. LY THUYET TAP THO, TAP THO Md .......•.......................................... 5 1.1.1. Khar,. rnem co b?an ve tap tho .................................................•.................. ... "' " " 5 b°" r• ). •A A A , 1.1.2. Khai niem CO' an Ve tap tho mo •••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••• 8 1.2. MOT so PHUONG PHAP RUT GON THUOC TINH D1/A TR.EN LY THlJYET TAP THO VA MO RONG 11 1.2.1. Phuong phap rut gon thuoc tinh theo tiSp C?Il t?p tho 14 1.2.2. Phuong phap rut gon thuoc tinh theo tiSp can t?p ma 24 CHUONG II. LY THUYET T~P MO MUC A VA. M(>T SO THU~T TOAN GIA TANG RUT G()N THU(>C TINH 30 2.1. MOT so KHAI NI$M BAN co 30 2.2. THUAT TOAN RUT GON THUOC TINH TR.EN BANG QUYET DlNH CO DlNlf 31 2.3. THUAT TOAN GIA TA.NG FIFTER TIM TAP RUT GON KHI BO SUNG TAP DOI TVQNG 34 2.4. THUAT TOAN GIA TA.NG FIFTER TIM TAP RUT GON KHI LOA.I BO TAP DOI TVQNG 37 2.5. THUAT TOAN GIA TA.NG FILTER TIM TAP RUT GON KHI BO SUNG TAP THUOC TiNH 41 2.6. THUAT TOAN GIA TA.NG FILTER TIM TAP RUT GON KHI LOA.I BO TAP THUOC TiNH 44 CHUONG 3. QUA TRINH THVC NGHitM VA KET QUA .47 3 .1. So sanh cac thuat toan tren bang quyet dinh khi b6 sung t?p d6i tuong .. 4 7 3.2. So sanh cac thuat toan tren bang quyet dinh khi 109-i bo t?p d6i nrong .... 54 ~ - KET LU~N 59 TAI LI~U THAM KHA0 60 ' - ? lll DANH MVC cAc KY H1¢u, cAc CHU VIET TAT Vi~t t~t Tieng Anh Tieng Vi~t RGTT Attribute reduction Rut gon thuoc tinh BQD Decision table Bang quyet dinh TDT Object set T~p d6i tirong TTM The rough fuzzy set T~p tho ma TRG The reduced set T~p rut gon DS Decision system\ Decision table H~ thong quyet dinh IS Information system H~ thong thong tin IV DANH MQC HINH VE Hinh 1.1 : Quy trinh RGTT 13 Hinh 3 .1: Quy trinh thuc nghiem cac thuat toan gia tang bf> sung d6i nrong . 48 Hinh 3.2: D9 chinh xac phan lap cua cac thuat toan 50 Hinh 3.3: Kich thuoc t?P rut gon cua cac thuat toan 51 Hinh 3.4: Quy trinh thir nghiem cac thuat toan gia tang loai bo d6i tuong 55 Hinh 3.5: D9 chinh xac phan lap cua cac thuat toan IF_FDAR_DELOBJ_a .58 Hinh 3.6: Kich thuoc t?p rut gon cua cac thuat toan IF_FDAR_DELOBJ_a .58 v DANH MVC cA.c BANG BIEU Bang 1.1: Bang quyet dinh dfry du 8 Bang 3 .1: Cac b(> du lieu su dung trong thir nghiem .4 7 Bang 3.2: KSt qua xir ly cua FDAR, GFS va F_FDBAR_a tren [uori] .49 Bang 3.3: KSt qua xu ly cua FDAR_AO, GFS va F_FDBAR_a _A0 52 Bang 3.4: Cac b(> du lieu SU dung trong thir nghiem 54 Bang 3.5: KSt qua xir ly cua FDAR, GFS va IF_FDAR_DELOBJ_atren u .. 55 Bang 3.6: KSt qua xir ly cua FDAR_DO, GFS va IF_FDAR_DELOBJ_a _DO ......................................................................................................................... 56 1 MODA.U I. S\f c~n thi~t tri~n khai d~ tai Lua chon thuoc tinh la mot buoc trong qua trinh tiSn xtr ly du lieu nh~m loai bo cac thuoc tinh du thira, khong c~n thiet ds tang tinh cts hiSu cho lu?t va hieu qua cho cac mo hinh phan lap. Tren thS gioi, cac nghien ciru vs lira chon thuoc tinh hien nay dang tro nen dt soi dong. Mot trong nhirng each tiSp C?n co thS noi toi la cac phirong phap rut gon thuoc theo huong tiep can cua ly thuyet t?p tho [l]. Tuy nhien, cac phuong phap ROTT theo huong tiep C?n nay chi thirc hien duce tren cac BQB co miSn gia tri roi rac. f)f>i voi cac BQB co misn gia tri sf>, cac phuong phap nay phai chia thanh nhieu khoang tuong irng voi cac gia tri phan loai. Viec khong thuc hien buoc roi rac hoa du lieu co thS d~n dSn mat mat thong tin quan trong tren cac BQB va gay ra su suy giam vs hieu qua cua cac mo hinh phan loai. BS giai quyet v&n dS nay, Dubois va d6ng nghiep [2] da dS xuat mot mo hinh gon tnrc tiep tren BQB gf>c voi miSn gia tri sf>, ma khong c~n thuc hien buoc roi rac hoa du lieu. Mo hinh nay duce goi la mo hinh TTM (fuzzy rough set). Theo cac phan tich vS TTM, cac nha nghien ciru da xay dung nhiSu phuong phap ROTT tnrc tiep tren BQB goc co mien gia tri sf> sir dung nhieu d(> do khac nhau. V oi BQB cf> dinh, cac phuong phap di Sn hinh la SU dung ham thuoc ma [3, 4], mien duong ma [5, 6], entropy thong tin ma [7, 8], khoang each ma [9, 10] va mot sf> phuong phap khac [11, 12, 13]. KSt qua thuc nghiem trong cac cong bf> neu tren cho thay, cac thuat toan tim TRO theo tiSp C?ll TTM nang cao d(> chinh xac phan lap so voi cac thuat toan theo tiep can tap tho truyen thong. Tuy nhien, Hung va cac cong su trong [14] trinh bay, cac phuong phap ROTT theo tiep can TTM khong hieu qua khi XU ly tren cac BQB nhieu va khong nh&t quan. Ngoai ra, trong XU thS bung n6 cua du li~u, cac BQB c6 sf> tinh ch&t vo cung 16n. Han nua, cac BQB thay d6i lien t\!C, b6 sung v6i cac truang hqp nhu tang them hay bat di TBT. Vi d\l di Sn hinh nhu bai toan ch:ln doan b~nh trong linh Vl.fC y tS, ch:ln doan cac tri~u chung lam 2 sang dua tren dt nhiSu cac chi s6 xet nghiem. S6 hrong benh nhan lien tuc gia tang theo thoi gian d~n toi qua trinh xay dung cac mo hinh phan lop nham h6 tro bac si trong viec chan doan g?p rftt nhieu kh6 khan. Do V?Y, dS dua ra mot mo hinh phan lop co loi, vftn dS d?t ra la phai giai quyet bai toan RGTT tren cac BQD Ion va co sir di dong vS d6i tuong, Tu nhtrng kh6 khan va thach thirc da neu, dS tai "N ghien CU'U m 3 . can t?p tho va cac mo hinh mo rong khi mang dSn mot cong cu htru hieu trong viec tim kiSm cac t?p con thuoc tinh tren cac BQD, d?C biet la cac BQD co tinh nhieu, khong nhat quan va c6 sir b6 sung ding nhu loai bo TDT theo thoi gian. DS tai nay duoc nh6m nghien ciru trinh bay dua tren CO' SO' cua nhiSu nghien ciru truce day, kSt hop voi cac thuc nghiern ds danh gia va so sanh tren nhiSu thuat toan nh~m chirng minh tinh hieu qua tu cac phuong phap ds xuat. IV. Phuong phap nghien CU'U ciia d~ tai Cdch' tiip c{m DS tai ban d~u se nghien ciru mot s6 cac phuong phap RGTT theo huong tiSp can t?p tho va t~p ma nh~m tim ra cac uu nhuoc diem cua m6i phuong phap. TiSp theo, dS tai Se dS xu§.t mot sf> thuat toan gia tang theo huong tiep can t?p ma SU dung lat cit a c6 kha nang cai thien hieu nang phan lop tren cac b9 du lieu c6 tinh nhicu va thoi gian XU ly trong tnrong hop BQD them va loai bo TDT. Cu6i cung, dS tai ding lam r6 nhtrng uu diem cua nhfrng phuong phap ds xuat thong qua qua trinh phan tich va danh gia cac kSt qua thuc nghiem khi so sanh voi cac phirong phap khac nhau tren cac b9 du lieu tieu chuan. Cdc phuong phdp nghien cteu - Nghien ciru ly thuyet: + Nghien ciru tu tong quan toi chuyen sau cac ly thuyet nen tang dS tu d6 tiSp c?n dSn nhfrng Iy thuyet nang cao. + Thu thap, tong hop, danh gia va rut ra cac kSt luan ciing nhu huong phat trien tren cac kSt qua da duoc cong bf> vs RGTT tren BQD. + DS xuat, cai tiSn va clnrng minh cac dinh nghia, menh dS SU dung cho cac phuong phap dS xuat mot each chat che. - Nghien ciru thuc nghiem: + Cai d?t thuat toan tren cac b9 du lieu co d9 tin C?Y cao voi kich thuoc tu trung binh dSn Ian nham danh gia va so sanh kSt qua da dugc cong bt> tren cac t~p chi chuyen nganh c6 uy tin. 4 + Ap dung kSt qua dat duce d~ xay dung chuong trinh co tinh irng dung cao. v. K~t c~u ciia n 5 CHUONG 1. TONG QUAN VE LY THUYET T~P THO, T~P THO MO v A cAc UNG DVNG TRONG BA.I TOAN RUT GQN THUQC TiNH 1.1. LY THUYET T~P THO, T~P THO MO 1.1.1. Khai ni~m CO' ban V~ tip tho V ao d§.u nhirng nam 1980, nha logic hoc Zdzisaw Pawlak dira ra ly thuyet t?p tho [ 1] va qua sir phat trien cfing nhir chtrng minh tren mot nen tang toan hoc vfrng chic, no da duce coi la cong cu hieu qua dS giai quyet cac bai toan vS mo ta sir phu thuoc gitra cac thuoc tinh, danh gia d(> quan trong cua cac thuoc tinh, phat hien luat thu duoc va nhan dang. Cho toi nay da co d.t nhiSu huong ti@p can dua tren ly thuyet t?p tho dUQ'C ap dung thanh Cong trong linh V\l'C khai pha du lieu va may hoc nhu sinh lu?t quyet dinh hay trich chon dac tnrng. Dua tren sir phat triSn cua ly thuyet t?p tho truyen thong ma cac mo hinh t?p tho mo rong ngay cang duce irng dung rong rfii cts giai quyet cac bai toan phan tich, khai pha du lieu, d?C biet la cac bai toan tren mot kh6i hrong du lieu 16n, chira dung cac thong tin ma h6, khong chic chin ma diSn hinh la cac h~ thong tin dfry du (Information System - IS) hay cac h~ thong tin khong dfry du (Incomplete Information System - IIS). H~ thong tin giup ich r§.t Ion cho viec hru trfr va XU' ly thong tin. Tuy nhien, vi mot ly do nao do trong qua trinh C?P nhat ma thong tin hru trfr CO cac thuoc tinh du thua Va tao ra sir kho khan trong viec khai pha tri thirc. H~ thong tin la cong cu biSu di~n tri thirc duoi dang mot bang du lieu g6m p CQt irng voi p thuoc tinh va n hang irng voi n d6i tuong, M9t each hinh tlurc, h~ thong tin diroc dinh nghia nhir sau: Dinh nghia 1. H¢ thong tin la mot bo tu aU(JC bidu diln duoi dang IS = (U, A, V, f), trong do Ula tdp hint han, khac r6ng cac tlc5i tuong; A la tdp hiiu han, khac r6ng cac thuoc tinh; V =U Va vai Va la tdp gia tri cua thuoc tinh a E A; f: U x A~ Va la ham thong tin, Va EA, u EU, f(u, a) E Va. DS don gian, voi moi a E A, u E U, ta ky hieu gia tri thuoc tinh a tai d6i tuong u la a (u) thay vi f (u, a). N@u B = {bi, b2, ... , bk} c A la mot t?p con 6 cac thuoc tinh thi ta ky hieu b(> cac gia tri bi(u) boi B(u). Nhtr V?Y, nSu u va v la hai d6i tuong thi ta viSt B(u) = B(v) neu bi (u) = bi(v) voi moi i = 1, ... , k. Xet mot h~ thong tin IS = (U, A, V, f), nSu ton tai u E U va a E A sao cho a(u) thieu gia tri (missing value) thi IS duce goi la h~ thong tin khong d§.y du, nguoc lai IS duce goi la h~ thong tin d§.y du. M6i t?p con cac thuoc tinh B c A xac dinh mot quan h~ hai ngoi tren U, ky hieu la Rs va duce xac dinh boi: Rs = {(u, v) E U x Ulv'a EB, a(u) = a(v)} (1.1) Rs la quan h~ B-khong phan biet diroc. Ro rang, Rs la mot quan h~ tuong duong tren u. NSu (u, v)E Rs thi hai d6i tuong u va v khong phan biet duoc boi cac thuoc tinh trong B. Quan h~ tuong duong Rs se xac dinh mot phan hoach tren U, ky hieu la U!Rs hay dS don gian la U/B. M6i phan tu cua phan hoach UIB diroc goi la mot lap tuong duong chira d6i nrong u E U va diroc ky hieu la [u]s, khi d6: [u]s = {v E Ul(u, v) E Rs} (1.2) :Djnh nghia 2. Cho hi thong tin IS = (U, A, V, f) va P, Q c A, khi do ta , co: 1. Phan hoach UIP va U/Q GU(/c goi la nhu nhau (viit la UIP = U/Q), khi va chi khi Vu E U, [u]p = [u]Q· 2. Phan hach U/Pmin hon phdn hoach UIQ (viet la UIP ~ U/Q) khi va chi chi Vu E U, [u]p c [u]Q. Xet h~ thong tin IS= (U,A, V,f) va TDT XE U. V6i mot t?P thuoc tinh B c A cho tnroc se xac dinh duce cac lap tuong duong cua phan hoach UIB. Khi do, mot TDT X ding c6 thS diroc bieu di Sn thong qua lap tuong duong nay. Trong ly thuyet t?p tho, dS biSu diSn x thong qua cac lap nrong duong cua x c U, nguoi ta x§.p xi Xboi hop cua mot s6 hfru han cac lap tuong duong trong U/B. C6 hai each x§.p xi TDT X thong qua t?p thuoc tinh B, duoc goi la B-xftp xi duoi va B-xfip xi tren cua.Y, ky hieu 1§.n hrot la BX va BX, duoc xac dinh nhir sau: 7 BX= {u E Ul[u]s c X} (1.3) BX= {u E Ul[u]s nx * 8 Bang 1.1: Bang quyit djnh afzy du u C1 C2 C3 C4 D U1 0.8 0.6 1 0 0 U2 0.8 0 0.2 .8 0 1 U1 0.6 0.8 0.6 0.4 0 U4 0 0.6 0 1 1 1.1.2. Khai niem CO' ban V~ t~p tho mo' Ly thuyet TTM (fuzzy rough set) do Dubois va cac cong sir [2-3] dS xu~t la SlJ kSt hop cua ly thuyet tap tho va ly thuyet t?p ma nhim x~p xi cac t?p ma dira tren mot QHTDM (fuzzy equivalence relation) duce xac dinh tren mien gia tri thuoc tinh. VS ban chat, cac QHTDM diroc ma rong tu cac quan h? tuong duong ma bao cao da trinh bay trong phan tnroc. Dinh nghia 3. Cho BQEJ DS = (U, C u D), mot quan hi R xac dinh tren miJn gia tri thuoc tinh aU'()'C goi la QHTEJMneu thoa man cac diJu kien sau voi moi u, v, t E U. I. Tinh phan xa: R(u, u) = 1. 2. Tinh d sup {min (R(u, t), R(t, v) )}. tEU M~nh d~ 1. Cho BQEJ DS = (U, C u D)va mot QHTEJM R. Ky hieu Rp, RQ tuong ung la C(lC quan h¢ R xac dinh tren tdp thuoc tinh P, Q c C. Khi do, voi moi u, v E U, ta co: 1. Rp = RQ ¢:::> Rp(u,v) = RQ(u,v) 2. RPnQ =RpURQ =max{Rp(u,v),RQ(u,v)}. 3. RPuQ = Rp n RQ = min{Rp(u, v), RQ(u, v) }. 4. Rp c RQ ¢:::> Rp(u, v) < RQ(u, v). 9 Dinh nghia 4. Cho BQEJ DS = (U, CUD) voi U = {ui, u2, ... , un}va .Rp la QHTEJM xac dinh tren tdp thuoc tinh P c C. Khi do, ma trdn tuong duong ma biiu diln .Rp, ky hieu la M( Rp) = [Pi} ]nxm' aU:9'C dinh nghia nhu: sau: ···· · · Pzn Pini ... .. . ··· Pnn voi Pii = RP ( u., Uj) la gia tri quan hi giiia hai a6i tuong u, va Uj tren tdp thuoc tinh P,PiJ E [0,1], iu, u1 E U,1 < i.j < n. Nhir V?Y, ta co th@ nhan thay rang gia tri cua cac phan tu trong ma tran tuong duong ma M(Rp) phu thuoc vao QHTDM .Rp duce chon, Mat khac, ma tran tuong duong ma la nen tang dS xay dung cac d . 10 YP = Rp = {[ui]P f_ = {[u1]p, ~ t-1 [u;Jp, .. ·, [un]P} (1.9) trong do, [ui]P = til U1 I Piz Uz I ••• , Pin} Un la mot tdp ma dong vai tro la mot lap tuong duong ma cua a6i tuong u, E U. V oi lop tuong duong ma [Ui] p, ham thuoc cua tfit ca cac d6i tuong u, E u duce xac dinh boi µ[ui]P ( uJ) = µRp ( u., Uj) = Rp ( ui, uJ) va Ive hrong cua lop tirong duong ma [ui]P duce tinh boi [U:]p = I I LJ=l Pij· Vi di} 2. Xet BQFJ trong vi du 1, voi mot QHTFJMtren m6i thuoc tinh a EC duce xac dinh boi c6ng thuc R{a}(u, v) = 1 - la(u) - a(v)I, khi do theo dinh nghia 4, ma trdn tuong duong ma CUa thuoc tinh Cl la: 1.0 1.0 0.8 0.21 M (R {ci} ) = 1.0 0.8 1.0 0.8 0.8 1.0 0.2 0.4 1 0.2 0.2 0.4 1.0 'T'heo ininh ng hi. 5, [~] {c} = {-,-,-,- 1., za u1 1 1 0.8 0.2} l'a l op tuong auong ma ' ;/: ' 1 U1 Uz U3 U4 cua a6i tuong UJ va luc luong cua [u1J{ci} = 1 + 1 + 0.8 + 0.2 = 3. Phdn hoach ma cua quan he ma R{cd la Y{cd = {[u1JfciJ, [u2Jrc1}, [u3J{c1}, [u4J{ci1}· Dinh nghia 6. ChoX la mot tdp ma tren U va Rp la mot QHTFJM tren tdp thuoc tinh P c C. Khi do, tdp xdp xi duai ma P Xva tdp xdp xi tren ma PX cua X la cac tdp ma va co ham thuoc cua cac a6i tuong U E U duac xac dinh nhu sau: µE.g(u) = inf max ( 1 - µ[u] (v), µg(v)) (1.10) vEU P µpg(u) = supmin(µ[u] P (v),µg(v)) vEU (1.11) Cap (f X =PX) duoc goi la TTM. D~ thay, mot t?p r5 XE U ciing duoc bieu 11 xi diroi va t?p ma x~p xi tren. Trong ly thuyet t?p tho truyen thong, khai niern miSn duong duoc dinh nghia la hop cua t~t ca cac t?p x~p xi duoi. Trong ly thuyet TTM, mien duong ma duce dinh nghia nhu sau. Djnh nghia 7. Cho BQEJ DS = (U, CUD), Rp va RD tuong tmg la hai QHTEJMxac dinh tren P c C va D. Khi do, mien duong ma cua tdp thuoc tinh aidu kien D voi tdp thuoc tinh P, duoc Icy hieu la PO Sp (D)va c6 ham thuoc cua m6i abi tuong U E U duirc xac dinh nhu: sau: µPasp (D)(u) = supµpg(u) u - (1.12) uE~ Ro D~ thay POSp(D) la mot t?p ma va duoc ma rong tu khai niem miSn duong ma tu ly thuyet t?p tho truyen thong. Dua tren khai niem nay, chung toi dinh nghia d9 phu thuoc cua mot t?p con thuoc tinh nhu sau. Djnh nghia 8. Cho BQEJ DS = (U, Cu D), Rpva RD tuong ung la hai QHTEJM xac djnh tren P c C va D. D(> phu thuoc cua tdp thuoc tinh P voi tdp thuoc tinh quyet dinh D duac dinh nghia nhu: sau: = IPOSp(D)I = LuEU µPOSp(D/u) YP CD) IUI IUI (l.I3) 1.2. MOT . SO PHUONG PHA.P RUT GON THUOC TiNH DUA . . . TREN LY THUYET T4P THO vA MO Rt loi cua dfr lieu gf>c. Qua trinh nay thuong duoc thuc hien d~ tang tinh hieu qua cua viec XU ly va phan tich dtr lieu, giam chi phi tinh toan va lam cho dtr lieu d~ dang quan ly hon. Cac ky thuat RGTT chia lam hai nh6m: Lira chon thuoc tinh (LCTT) va bien d6i thuoc tinh (BDTT). LCTT la trich chon mot t?p con t6i uu (theo mot nghTa nao do) tu t?p thuoc tinh nguyen thuy. BDTT 12 la thtrc hien viec chuyen d6i cac thuoc tinh ban d~u thanh mot t?P cac thuoc tinh moi voi kich thuoc it hon sao cho bao toan duce thong tin a mire t6i da. Cac cong trinh nghien ciru vS RGTT thuong t?p trung vao nghien ciru cac ky thuat LCTT. LCTT la qua trinh chon ra mot t?p con c6 kich thuoc IBI tu tap g6c clnra ICI thuoc tinh (BCC), sao cho khong gian thuoc tinh duoc thu gon mot each t6i uu dua tren mot tieu chuan cu th{ Viec tim ra t?p con thuoc tinh t6i iru tlnrong la mot vftn dS kho; thuc tS, n6 thuoc vao lap bai toan NP-kh6. Thong thuong, mot thuat toan hra chon thuoc tinh bao gem bon khau ca ban. ( 1) Khai tao tap con; (2) Phan tich t?p con; (3 ) x« dieu kien dung; ( 4) Danh gia kSt qua. T?O l?p t?p con thuoc tinh la qua trinh lien tuc tim kiSm nham tao ra cac t?P con dS danh gia va lua chon. Gia SU t?p du lieu ban d~u chira ICI thuoc tinh, V6i ICI thuoc tinh nay, tong s6 t?p con c6 thS duce tao ra la 21CI- Do d6, viec tim ra t?P con t6i iru tu tftt ca cac t?p con nay la rftt kh6 khan. Mot phuong phap ph6 biSn dS tim kiern t?p con thuoc tinh t6i iru la tao ra tung t?p con dS so sanh, M6i t?p con duce tao ra se duce danh gia dua tren mot tieu chuan nhat dinh va so sanh voi t?p con t6t nhat da duce chon tnroc do. NSu t?p con moi nay cai thien, n6 se thay thS t?p con cii. Qua trinh tim kiSm t?p con thuoc tinh t6i uu se dung khi mot trong b6n diSu kien sau xay ra: ( 1) Da thu duoc s6 thuoc tinh dua tren 1 tieu chu~n. (2) S6 buoc l~p duce dinh nghia trong qua trinh kSt thuc, (3) Viec b6 sung vao hay luge bo mot thuoc tinh nao do khong lam cho kSt qua tbt hon. (4) Da thu duce tap con t6t nhat theo tieu chuan danh gia. Cuoi cung, t?p con t6t nhftt phai duce xac minh thong qua viec thuc hien cac phep kiSm dinh, so sanh kSt qua khai pha vai t?p thu(>c tinh "t6t nhftt" nay 13 va t?P thuoc tinh ban d:lu tren cac t?p dir lieu khac nhau. Qua trinh lua chon thuoc tinh duce bi Su di Sn nhu hinh sau (Hinh 1.1 ). Hien nay, co hai phuong phap chinh dS tiSp can bai toan lua chon thuoc tinh: L9c (filter) va Dong g6i (wrapper), m6i phuong phap nay d~u co muc tieu rieng v~ viec giam s6 hrong thuoc tinh hoac nang cao d(> chinh xac cua mo hinh phan loai, Phuong phap loc thuc hien viec hra chon thuoc tinh doc l?p voi cac thuat toan khai pha SU dung sau nay. Cac thuoc tinh duoc chon dua trend(> quan trong cua chung trong viec mo ta dfr lieu. Phuong phap nay c6 uu diem la thoi gian tinh toan nhanh, nhung nhuoc diSm la khong SU dung thong tin nhan lap cua cac bo dfr lieu, do d6 de) chinh xac khong cao.Ngiroc lai, phirong phap d6ng g6i thuc hien bang each ap dung ngay ky thuat khai pha cu thS voi TRG thuoc tinh, d(> chinh xac cua kSt qua duce SU dung lam tieu chuin dS lua chon cac t?p con thuoc tinh. Hp tlmQC tinh Tt1o~p t~p ·Banh gia t~p dmqctiuh ---• tbufc tinh con 41f4}'CTI)O Tdpccn phuhqp Sai Dung Banh gia t~p ritg9nkit qua Hinh 1.1: Quy trinh. RGTT 14 1.2.1. Phuong phap rut g9n thu{>ctinh theo ti~p c~n t~p tho Cho dSn nay co d.t nhiSu cac phirong phap RGTT trong BQD d~y du theo tiep can ly thuyet t~p tho truyen thong, cac phuong phap diSn hinh duce trinh bay nhu sau: - Phuong phap RGTT dua tren mi~n duong: KS tu khi Pawlak dua ra dinh nghia TRG dua tren mien duong, cac cong trinh nghien ciru da xay dung thuat toan tinh miSn duong, Dua tren diSu do, ta phat trien mot thuat toan c1S tim TRG dua tren mien duong, Cu thS, mot rut gon duce dinh nghia nhu sau: Dinh nghia 9. Cho BQD DS = (U, CUD), mot tdp B c C duce goi la mot TRG cua C dua tren miJn duong ntefu thoa man: I. POS8(D) = POSc(D) 2. Vb EB, POS8\{b/D) ::f::. POS8(D) l>jnh nghia 10. Cho BQD DS = (U, C u D) va mot tdp B c C. Khi c16 a(} quan trong cua thuoc ti nh b E C duoc tfnh theo cong thuc sau: SIG(b, B) = Ya (D) - Ys\{b}(D) (1.14) Ro rang, d(> c~n thiSt cua thuoc tinh theo Dinh nghia 10 co tinh don dieu, Sµ thay d6i trong ham phu thuoc cang cao thi thuoc tinh cang quan trong. Do do, khi xay dung thuoc tinh, cac thuat toan se sir dung dinh nghia nay cts xay dung mot chuoi cac thuoc tinh irng vien cho TRG. Dua tren Dinh nghia 9 va 10, Hoa va cac cong sir tai [4] da sir dung phirong phap silp xep nhanh (Quicksort) cts siip xep cac ctf>i nrong theo tinh phu hop va xay dung thuat toan tinh mi Sn duong. Xu va cac cong sir trong [ 5] sir dung phuong phap silp xSp theo ca s6 (Radix-sort) dS xay dung thuat toan tinh miSn duong. Dua tren tinh don dieu thong qua tinh c~n thiet cua du lieu duce trinh bay trong Dinh nghia 10 va hai tinh ch§.t cua TRG tu Dinh nghia 9, Shu va cac cong sir trong [6] da xay dung thuat toan loc GFS dS tim kiSm cac thuoc tinh quan trong tren BQD. Cac biroc cua thuat toan GFS duce trinh bay trong ma gia 1. Dua tren thuat