Luận văn Áp dụng kỹ thuật tập thô và tập mờ trong phân tích dữ liệu bảo hiểm

17 CHUONG 2 , ~ ~ ~ L Y THUYET TAP THO. 2.1.H~THONG THONG TIN Me>th~th6ngthongtinIame>tbi~udi~ncuat~phQ'PduIi~udoIuangcachi~n tuqngv~tIy nhu:giQngnoi,vanhim,chu6ianh,cactin hi~uxu Iy trongcong nghi~p,v.v... Me>th~th6ngthongtinbaag6mb6nthanhph~n: S =(U,Q,V,f) Trongdo: - S:Iah~th6ngthongtin. - U: Iat~pvli tn,ldong,t~pxacdinhN d6ituqng{xl'X2'X3,...,XN},U khongIat~P" rong. - Q:t~pxacdinhcuanthue>ctinh{QpQ2,q3,...,qN}'QkhongIat~pr6ng. - V=UqEQVq,trongdo VqIami~ngiatri cuathue>ctinhq. - f: U xV ~ V Ia t~pcachamquy~tdinhhaycongQiIa hambi~udi~nthongtin saDcho f(x,Q) E Vqv6i mQi QE Q,x E U. Trong baa caDnay ta dung khai ni~m t~pvli tn,lco ngmaIa t~pvli tn,ldong. M6i be>(q,v), vai QE Q,VEVqduqcgQiIa me>tmotatrongme>th~th6ngthong tinS.H~th6ngthongtin clingduqcbi~udi~nb~ngme>tbangduIi~uxacdinh,trong d6cacce>tbi~udi~ndicthue>ctinh,cacdongbi~udi~ncacd6ituqngvam6iph~n tut?ice>tq dongx cogiatri Ia f(x,q).M6i dongtrongbangIame>tmotathongtin cuame>tvaid6ituqngtrongh~th6ngthongtinS. Bfttkyme>tt~phqpcacd6ituqngkhongr6ngX naoclingduqcgQiIame>tkhai ni~mtrongS.Me>tkhaini~mcoth~come>tY nghlara rang,chinhxac.Vi dvt~p hqpduIi~uv~dichqpd6ngbaahi~mnhanthQcoth~xacdinhkhanangditrihQ'P d6ngcuakhachhang.KhanangduytrihQ'Pd6ngcuakhachhangIame>tkhaini~m 10 dungd~xacdinhduQ'ct1l~IQ'inhu~ncuacongty.N~ukhanangduytrihQ'Pd6ng caDthihQ'pd6ngdosemangl(;liIQ'inhu~ncaDhanchocongty. Vi du2.1: Xett~phQ'pdfrli~udangiancuacachQ'Pd6ngbaahi~mnhanthQ duQ'cbi~udi~ntrangbang2.1: D6i tU'Q'ng Ban!!2.1:T~pdfrli~uhQ'Pd6ngbaahi~mnhanthQ(HDBH) u THANH TOANl MJ};NH-GIA CacthuQctinh DUY TJU Xl X2 X3 X4 X5 X6 Xl X8 3 6 6 6 12 12 12 12 Nh6 Trungbinh LOTI Trungbinh Nh6 Trungbinh Lan Nh6 '. SAN PHAM ASGD ASTL ASTV ASHT ASTL NNGH ASTV NNGH Hi~u_h,rc Huy Huy Huy Hi~u_h,rc Hi~u_h,rc Huy Huy (Thongtintrangbang2.1chimangtinh vi d1:1minhh(JachaLf; thuyitt4ptho) Chti thich: - THANH- TOAN:lahinhthucthanhtoancuakhachhang,co3 hinhthucthanh toimphibaahi~m:3:theo3thang1lfin;6:theo6thang1lfin;12:theo12thang 1Ifill. - Mf!;NH_GIA:lagiatri hQ'Pd6ngkhi daDh(;ln. - SANPHAM:m6ihQ'Pd6ngbaahi~mnhanthQcomQtsanphAmchinh. ASGD:sanphAmAn SinhGiaoD\lc ASTL: sanphAmAn SinhTichLfiy Trangbang2.1: ASTV: sanphAmAn SinhThinhVUQ'llg ASHT: sanphAmAn SinhHuu Tri NNGH: sanphAmNh~tNienGia H(;ln 19 - DUY_TRi: 1£1dQdoduytri hqpd6ngcuakhachhang,6 daychi tinhgiatri duy tri trongnamd~utiencuahqpd6ng,m\lCtieu1£1xacdinhsaumQtnamhQ'pd6ng conhi~uhJchaydffbi huy.Ti 1~duytri hqpd6ng1£1mQtti 1~quailtn,mgd6ivai caccongty baohi~mnhanthQ,ti 1~nay1£1dQdo ch~tluQ'ngkinh doanhcua congty. Trongh~th6ngthongtinS motab6i t~pduli~unayg6mcacthanhph~n: - T~pvutf\lbaog6m8d6ituQ'ng,U={Xl,X2,...,XS}m6id6ituQ'llg1£1mQtbi~u di~nthongtincuamQthqpd6ngbaohi~m. - M6i mQtd6ituQ'nghqpd6ngbaohi~mduQ'cbi~udi~nb&ngbQ4 thuQctinh Q={qI,Q2,Q],Q4}={THANH_TOAN,MENH_GIA, SAN_PHAM, DUY_TRi}, ta su d\lngcacgia tri rai r(,lc(s6va ky hi~u)d~bi~udi~ncack€t quaduytri hqp d6ng. - ~~pt~tca cac gia tri rai r(,lC(d(,lngs6) cua th~.Qctinh THANH ToAN 1£1 VTHANH]oAN={3,6, 12} - ThuQctinhthuhaiMENH- GIAcobagiatriraiWCkhongphaiki~us6nenmi~n giatri cuaMENH - GIA 1£1vMf!;NH_G1A={Nh6,Trung binh,Lan}. - ThuQctinhthubaSAN_PHAM conamgiatri rai r(,lCkhongphaiki~us6nen mi~ngia tri cua SAN PHAM 1£1VSANPHAM={ASGD,ASTL, ASTV, ASHT, NNGH}. - T~pcacgia tri rai r(,lccu6i clingcuathuQctinhDUY_TRi 1£1VDUY]Ri={Hi?u !z;rc,Huy}. Hai gia tri nay bi~udi~nthlJc t€ cua hqp d6ng 1£1hQ'pd6ng con hi~u IlJc haydffbi huy. - Giatri cuahamthongtinf(x,q)duQ'cth~hi~ntrongbang1,tath~yr&ngd6i tUQ'llgXI va thuQCtinh THANH- ToAN ham thong tin co gia tri 1£1 f(xj,THANH_ToAN) =3. - T~phqpcacd6itUQ'llg{xj,X5,xd coth~duQ'cxacdinhkhaini~mhQ'pd6ngco hi~uIlJctrongh~th6ngthongtintren. 20 2.2.QUAN H~TUONG DUONG GQiS=(U,Q,V,f) la mQth~th6ngthongtin,Ac Q la t~pconcuat~pthuQc tinhQ;x,yE U la cacd6ituQ'llgtrongh~th6ngthongtinS.Hai d6ituQ'ngx vay duQ'cgQila c6quanh?tlfongalfangtrent~pthuQctinhA trongS nSunhu:f(x,a) =f(y,a)mQiaEA Ky hieu:xAy:x quailh~tuangvaiy trent~pthuQctinhA. M6it~pconcacthuQctinhA xacdinhmQtquailh~tuangdUO-figtrongt~pvutr\l U.Quanh~tuo-ngdUO-figtrent~pthuQctinhA trongU duQ'cdinhnghlala: IND(A)={(x,y)EUx U: Va E A,f(x,a) =f(y,a)} N~nc~pd6i tUQ'llg(x,y)thuQcquailh~IND(A), ((x,y)E IND(A)) thi tan6ihai d6i tuQ'ngx vay tuo-ngdUO-figtrent~pA. Hay khongth~nh~nrax hayy nSuchi dungt~pthuQctinhA. Quanh~tuo-ngdUO-figIND(A) lamQtquailh~tuangdUO-fignhiphan,chiat~pvu tf\l U thanhhQcac lap tuo-ngduang{Xl,X2,...Xr}.T~pcuatfitca cac lap tuang duang{Xl,X2,...Xr}duQ'cXaCdinhb6'iquailh~tuangIND(A) trongU, t~ora SlJ phanho~chtrenU duQ'cky hi~ulaA*.T~pcuacaclap tuangdUO-figA* duQ'cgQila mQtphanlap (classification)vaduQ'ckY hi~ula U/IND(A). Cacd6ituQ'ngthuQcungmQtlapXi thikhongth~phanbi~tduQ'chaytuang duangnhau,nguQ'cl~ithikhongtuangdUO-figtrent~pthuQctinhA. Caclaptuo-ng dUO-figXi, i=1,2,3...,r cuaquailh~IND(A)duQ'cgQilacact(tpsacaptren-Atrong h~th6ngthongtinS. Ky hien:[xL ={yEU: xIND(A)yhayxAy} Trongd6: [xL la T(tpsa captren-A(haymQtlap tuo-ngduang)chuad6itUQ'llg x. Cac T(tpsa captren-AXi la cackh6ithuQccacphanho~chcuat~pvu tr\l U va bi~udi~nnh6mcacd6i tuQ'llgtuangdUO-fignh6nhfit,nenchungduQ'cgQila Tri thirccahim(basicknowledge). VaimQth~th6ngthongtinSchotruac,vamQt~pthuQctinhA~Q t~oraquail h~tuo-ngdUO-figIND(A). MQtbQAS=(U,IND(A))duQ'cgQila mQtkh6nggianxap 21 xi. MQiphepk€t cuacact!jpsa cdptren-AtrongAS duQ'cgQila t!jpxacatnh (definablesets)hayt!jptlnhtrongAS. Cact!jpsa cdptren-QduQ'cgQilacacnguyentu cuamQth~th6ngthongtinS. , -, * Kv hieD:DesA(X)bieudient!jpsacaptren-AvaiX EA duQ'cdinhnghIa: DesA (X) ={(a,b) :f(x,a) =b,'\IxE X,a E A} hay DesA(X) ={a=b: f(x,a) =b,'\IxE X,a E A} Vi du 2.2:Phantichl~icact~phQ'ptuangungvai h~th6ngthongtinHDBH trongbang1,giasur&ngchiquailtamk€t d€n haithuQctinhTHANH- ToANva MENH_GIA,bi~udi@nt~pthuQctinhA={THANH_TOAN,MENH_GIA}nhutrong bang2.2: Bang2.2: Dftli~uHUBHvait~pA={THANH_TOAN,MENH_GIA},A c Q u THANH TOAN 3 M1JNH-GIA Nh6 X4 6 6 Trungbinh Trungbinh Cae lOptuO'ngQuO'ng [x11A={xIi " [x2J A = [x41A = {X2,X4} Xl X2 .. X3 6 12 Lan [x31A = {X3} [x51A = [xii A = {X5, XS} Xs 12 12 Nh6 Nh6 X5 X7 12 Lan [x61A= {x6J [xi A = {X7} X6 Trungbinh Nhu trongvi d\l trenchungta thftyr&ngcacd6i tUQ'llgduQ'cchia lam6 nh6m khacnhauc6giatri b&ngnhautrenthuQctinhTHANH- ToANvaMENH- GIAtrong t~pA. Cacd6ituQ'ngcuaclingmQtnh6mthitfttcacacthuQctinhcuan6d~uc6 chungmQtgiatrioTrongvi d\ltac6caclaptuangduangsau: Xl = [xJ A = {Xl} X2 = [X2JA= [x41A= {X2,X4} X3 = [x31A= {X3} 22 X4 = [X5]A= [xiiA = {X5,XS} X5 = [xd A = {Xd X6 = [x7]A = {Xd Tath~yr~ngffiQt~pthuQctinhA=(THANH_TOAN,MR;NH_GIA}cQ t~onen ffiQtquailh~tuangduangIND(A)trent~tcacact~pchuacacd6itugngthuQcT~p vii tf\lU, hayphatbi~uquailh~IND(A)duaid~ng:IND(A)fa ttitcdm6imi}tcijp (Xi,X) trangS saachattitcdgiGtrj cuanotrangA fabringnhau. Trongvi d\ltren,cact~p{(X2,xz),(X2,X4),(X4,X4)}dugcxacdinhbai quailh~ tuangduangIND(A). T~pcuacacd6itugngduaihinhthuctuangduangnaydugc bi~udi€n duaid;;mglap: X2=[X2]A=[X4]A={X2,X4} Quanh~tuangduangIND(A)v~nd\lngt~pA d~tacht~pviitf\lU thanhcaclap tuangduang,caclap tuangduangla ffiQtphepphanlap U/IND(A)(phepphan ho~chA*cuaU) A *= {Xl, X2,00.'X6}={{Xl},{X2,X4},{X3}, {X5,Xs},{X6},{X7}} v ~yT(tpSO'ctip tren-A X EA * (ffiQt laptuangduang)c6th~gQilaDesA(X),vi d\l T(tpSO'ctipX2 = {X2,X4}chungta c6: ={(THANH_TOAN,6),(MR;NH_GIA,Trungbinh)} ={(THANH_TOAN=6), (MR;NH_GIA=Trungbinh)} M6i T(tpSO'ctiptren-AXi (i=1,2,oo.,6)(hayMQttri thuccaban)bi~udi€n ffiQtte baa (nh6ffi nh6 nh~tcac ph~ntu tuang duang) trong kh6ng gian x~p xi DesA(X2) AS=(U,IND(A)).Nhuv~yb~tkyffiQtphepketnaotrongcacT(tpSO'ctiptren-AdSu lat~pxacdinhtrongAS,vi d\l{{X2,X4}U {X5,xs}}={X2,X4,X5,xs}laffiQt~pxac dinh. Xettoanh~th6ngtrongbang2.1,t~tcacacT(tpSO'ctiptren-Q(caclaptuang duangdugcphanbaiIND(Q),cacnguyentu) trongS la: ~J,~d,~J,~J,~~,~d,~d,~d 23 Bfitky mQtphepk€t naocuaOOungnguyentu nayd~u1amQtt~pxacdinhtrong khonggianxfipxi AS=(U,IND(Q)),vi dtJOOU{{XIJ,{X2'X4}}={X],X2,X4}1amQtt~p xacdiOO. TrongtrucmghQ'ptachiphanho~chtrenthuQctiOOTHANH- ToAN.Phanho~ch A* (hay phan lap U/IND(A), tucmg(rug v6'i quail h~ tuOTIgdUOTIg IND(THANH_TOAN),phantrent~pthuQctiOOA={THANH_TOAN},thi tacoA* ={Xj={xIJ, X2={X2,X3, X4},X3={Xs,X6, Xl, Xs}}.CactljpcO'sa tren-Q(cac nguyentu)1a: * Q ={{xIJ, {X2},{X3},{X4},{xs},{X6},{Xl},{xs}} Xet Yj={Xj , Xs,X6},Y2={X2,X3,X4,Xl, xs}duQ'Cxemnhu cac lap dl)'avao chuyengiatrongU. d daychungtacoth~gankhaini~mHi?ullfc choYj vakhai ni~mHuychoY2 2.3.MA T~N KHA PHAN Thongthuemgvi~cphanbi~tcacd6ituqngthicfinthi€t han1agiatri cuacac thuQctiOOcuad6ituQ'ngvi baitoandi[ltra1achungtaphaidi phanlo~icacd6i tuqngkhongro rang.D~thl)'chi~nvi~cnaythimQth~th6ngthongtinduQ'cbi~u di~ndu6'id~ngmQtmatrljnkhiJphan.SkowronvaRauszer(1992)daduarahai khaini~m1amatrljnkhiJphanvahamkhiJphan,haikhaini~mnaygiupxayd1!llg hi~uquacacthu~toanlien quaild€n vi~crut gQncact~pcon cuacacthuQctinh trongh~th6ngthongtinchotru6'c.V6'ihaikhaini~mmlychungtacoth~1uutm Sl)' khacOOaucuacacthuQctiOOtrentUngci[lpd6i tuqngtrongmatrljnkhiJphan.Ma tr~nkhaphanco th~chi chuamQtvai dft li~ucuamQth~th6ngthongtin nhung phaigiu tfitca thongtin cfinthi€t khi cfinki~mtrat~pthuQctiOOt6i ti~ucuacac khaini~mduQ'cmotit. Cho S=(u,Q,V,j) lamQth~th6ngthongtin,t~pcacthuQctinhQ={aj,a2,"', an}vat~pviitftJU={Xj,X2,..., XN}.MQtmatr~nkhaphanM(Q)cuamQtHTTT S v6'it~pthuQctinhQ lamQtmatr~nvuongNxNchi~u,v6'idongvacQtxacdinhd6i tuQ'ngXi(i=l, 2, ...,N).M6iphfintumijcuamatr~nkhaphanlamQt~pcacthuQc L4 tinhd~nh~ndi~nduQ'cacd6ituqng.Vi v~ymatr~nkhaphancoth~duQ'cxac dinhnhusau: { 0 Xi ,Xj cunglOptuongduongtheoquanht:;IN~Q) mi,j ={aEQ:f(xi,a)=f(xj ,an, Xi,Xjkhac1optuongduongtheoquanht:;IN~Q) TrangdoXi,XjthuQcU. Ph~ntITmi,jchuatfitcacacthuQctinhmagiatri cua chunglakhacnhautrenhaid6ituQ'ngXivaXi'f)i~unayclingcoy nghlar~ngXi,Xj thuQcv~hailapkhacnhaucuamQtphanho?chduQ'cphatsinhtirIND(Q)(XivaXj bi~udi€n haikhaini~mkhacnhau).Matr~nkhaphanM(Q) lamatr~nd6ixungva mi,i=0v6i lii.Vi v~y,tachic~ntinhcacgiatricuatamgiacdu6inghlalaxetmi~n mi,jvai0 ::;;j< i ::;;N-I (N la s6d6ituQ'ngtrangh~th6ngthongtinS). Ham kha phanIs cua mQtHTTT S la mQtham Bool v6i n bi~nnhi phan a1,a2,..., an tUOTIgungv6i cacthuQctinhal, a2,...,anva duQ'cdinhnghla nhu sau: fAfiipa2,...,an)=/\(v (mij):1<s,j <S,m,mi,j"*0) Trang do: v (mij): n6i rai cuacac gia tri a saGcho a thuQcmi)' Vi du2.3:ChoT~pduli~uNHLPHA.NvaHTTT S=(U,Q,V,f) nhubang2.3: Ban22.3:T~pduli~uNHl_PHA.N CackY hi~ua, c, d, e,0 tUOTIgungtrangdu li~ubaahi~mcoy nghla(Ghi chit: cackYhi~ua, c,d,e,0 fadoh9CvienkYhi~uaddl bidudiln matr(inkhciphlin): - a:Gi6itinh;mi~ngiatri 1:Nam;0:Nu. - c:Coxetnghi~mykhoahaykhong;1:coxetnghi~m;0:khongcoxetnghi~m. U a c d e 0 Xl 0 1 1 1 1 X2 1 1 0 1 0 X] 1 0 0 1 1 X4 1 0 0 1 0 X5 1 0 0 0 0 X6 1 1 0 1 1 25 - d:SanphAmcochiaunhaysanphAmkh6ngchialai;1:sanphAmcochialai;0: sanphAmkh6ngchialai. - e: HQ'Pd6ngnamdfmhayhQ'Pd6ngt{titl)C;0: hQ'Pd6ngnamdfiutien;1:hQ'P d6ngtaitl)c. - 0:HQ'Pd6ngconhi~uhJchaykh6ng;I: hQ'pd6ngconhi~uhJc;0:hQ'pd6nghuy haymc1thi~uhJc. Matr~nkhaphanseduQ'cbi~udi~ndu6id~ng: Hinh2.1:Matr~nkhaphanbi~udi~nbangdftli~unhiphan2.3 Hamkhaphansela: Is(a,c,d,e,0)=c/\ e/\ 0 /\ /\ (av d) /\ (Cv e) /\ (CV 0) /\ (ev 0) /\ /\ (av c v d) /\ (av d v 0) /\ (c v ev 0) /\ /\ (avcvdvo)/\(avcvdvevo) 2.4.BANG QUYET DJNH MQts6HTTT coth~duQ'cxemnhulamQtbangquy~tdinhn~ut~pthuQctinhQ duQ'cphanthanhcact~priengbi~tnhau,cact~pnaygQilat~pthuQctinhdiSuki~n Cvat~pthuQctinhquy~tdinhD, v6i CuD =Q va enD =~ V~ybangquy~tdinhcuaHTTT SduQ'cdinhnghlanhusau: DT=(U,CuD,V,j) 1 2 3 4 5 6 1 2 ado 3 acd co 4 acdo c 0 5 acdeo ce eo e 6 ad 0 c co ceo 26 Trongd6: - C: t~pthuQctinhdi€u ki~n(khonglat~pr6ng,lacacgiatri d~uvela,cacmfiuca s6). - D: t~pthuQctinhquy€tdinh(khonglat~pr6ng,cacquy€tdinh,cachanhdQng, caclap) - V =UqECuDVq v6'iVqlami€n giatft cuathuQctinh q EQj - f :Ux(CuD) -+V lamQthamquy€tdinhsaDchof(x,q)thuQcVq,v6'im6iq thuQcQ vax thuQCV. MQtbangquy€tdinhduQ"cdinhnghlala (U,CuD) hayDTctrongd6C lat~p thuQctinhdi€u ki~n.T~pD tfmgquatc6 th~chuanhi€ut~pthuQctinhquy€tdinh. Tuynhien,v6'inhi~mV\lphfu1lap,t~pthuQctinhD thuOngchicomQthuQctinh quy€tdinhdC;lidi~nchocaclapkhacnhauCErCI,Cl,"', cd. Bangquy€t dinhgQila xac dinhn€u nhu mQigia tri cuat~pthuQctinhquy€t dinhduQ"cxacdinhduynhfitb6icacthuQctinhdi€u ki~n.BangthuQctinhgQila khongxacdinhn€unhuclingmQt~pthuQctinhdi€uki~nchotru6'c,thuQctinh Bane:2.4:Bangquy€tdinhcuaHTTT hQ"Pd6ngbaahi~m DAi CacthuQctinhdiu kin CacthuQctinh tm!ng quyt djnh C D U THANH TOAN ME;NH-GIA SAN PHAM DUY TRl X] 3 NbC> ASGD Hiu hJC Xl 6 Trungbinh ASTL Huy X] 6 Lan ASTV Huy X4 6 Trungbinh ASHT Huy X5 12 NbC> ASTL Hiu hIc X6 12 Trungbinh NNGH Hiu hJc X7 12 Lan ASTV Huy Xs 12 NbC> NNGH Huy 27 quy~tdinhconhi~ugiatrioCacbangquy~tdinhkhongxacdinhcoth~tachthanh hatbangconxacdinhvakhongxacdinhhoantoan.Bangquy~tdinhkhongxac dinhhoantoankhongth~chuabangconxacdinh. Vi du2.5:MQtbangquy~tdinhv~thongtinHDBH trongbang2.1 M6i d5ituQ'ngduQ'cmotabing mQtt~pcacdi~uki~n:C= {THANH- ToAN, MENH_GIA, SAN_PHAM}.Mi~n gia tri cua thuQctinh THANH_ToAN: VTHANH]oAN={3,6, 12}.Mi~n gia tri cuathuQctinhMENH - GIA: VMENH_G1A={Nho, Trungbinh,Lon}. Mi~ngia tri cuathuQctinh SAN_PHAM: VSAN]HAM={ASGD, ASTL,ASTV,ASHT, NNGH}.M6i d5ituQ'ngsethuQcv~mQttronghatIo~iHi?u IlfC hayHuy.T~pcacgiatri VDUY]Ri={Hi?uIlfC,Huy}cuathuQctinhquy~tdinhd dinh nghlat~pcackhatni~m{Hi?uIlfC,Huy}chungtamu5nh<)cdvatrenthuQctinhgia tricuac. 2.5.xAp xi T~PHQP,KHONGGIANxAp.xi MQts5t~pcon(lap)cuacacd5ituqngtrongh~th5ngthongtinkhongth~phan Io~iduQ'ckhichidvavaGthuQctinhcuachung.Svphanbi~tchungcoth~till thfty duQ'Ca mucdQxftpxi. Y tuangcuaT~pthoIatill d~ngxftpxi cuamQt~phqp binghatt~pconkhac,duQ'cg<)iIaTqpx6pxi trenvaTqpx6pxi dU'aichot~phqp c~ndinhnghla. Choh~th5ngthongtinS,t~pthuQctinhA cQ vaquailh~tuangduO'ngIND(A). MQtc~pcothutvAS = (U,IND(A))g<)iIaKh6nggianx6pxi cuah~th5ngthong tinS.ChoX c U (X IamQtkhatni~m),Tqpx6pxi dU'aidlfatren-AcuaX duQ'ckY hi~uIaAX vaTqp x6pxi trendlfatren-AcuaX duQ'ckYhi~uIa AX. Hait~pxftp xiAXva AX trongkhonggianxftpxiASduQ'cdinhnghlanhusau: * AX={XE U: [X]ACX} =u{YEA : YcX} - * AX= {XEU: [X]AnX;rljJ} =u{YEA : YnX;rljJ} ChungtaclingnoiringAX va AX IaT~pxftpxi trenvaT~pxftpxi dualcua khatni~mX trenkhonggianxftpxiAS.T~pxftpxi dualcuaX chinhIahqpcuatftt 28 Celcact~pthanhph~n,trongd6m6it~pthanhph~nd~uchuatrongX. Nhuv~yv6'i \1'xEAX thidInhienxEX.T~pxftpxi trencuaX chinhlahqptiltCelcact~pthanh ph~n,trongd6giaocuam6it~pthanhph~nv6'iX khacr6ng.Nhuv~yv6'ixE AX thixc6th~c6hayclingc6th~khongthu<)cv~X. Vimgbiendlfatren-Acuat~pX c U trongkhonggianxftpxi AS duQ'cdinhnghlanhu gall: BNA(X)=AX-4X BNA(X)congQila vungu6'cluqngcuaIND(A). V6'i \1'xEUva \1'xEBNA(X),thi khongth~xacdinhduQ'cxEXhaykhong.T~pxftpxi du6'icuaX laAX hi~nnhien duQ'cxacdinh,xftpxi trencuaX laAX clingduQ'cxacdinh,ducmgbienchinhla mi~nu6'cluQ'ng. u AX X BNA(X) ----- Ax Hinh 2. 2:M<)t~pthovakhonggianxftpxi AS. V6'ikhonggianxftpxi AS (AEQ) vam<)tt~pconXcU, chungtac6th~chiat~p vli tn)U thanhbami~nnhugall: l. 2. AX: vungkh~ngdinhtrenA,kyhi~ulit:POSA(X)cuakhaini~mX trongS. AX -AX :vungbientrenA,kyhi~ulit:BNA(X)cuakhaini~mX trongS. U - AX: vungphudinhtrellA,kYhi~ulit:NEGA(X)cuaXtrongS.3. - N~uAX=AX, tan6iXcU la T(1pchinhxactren-Atrongkhonggianxftpxi AS. Trongtruemghqpnay Vimgbientren-ABNA(X)=rp. 29 - N~uAX ~AX,tan6iXcV laT(tpxdpxi thotren-AtrongkhonggianxfipxiAS. Trongtruanghgpnay,BNA(X)~ t/J.Vimg bientren-AcuaT~pchinhxactren-A lat~pding. V6i T~pxfipxi trenvaT~pxfipxi du6icuat~pconcuaU chuacacd6itUQ'I1gX trent~pthuQctinhA, thid~dangki~mtrathoamancactinhchfitsau: 1. AXcXcAX 2. A t/J= A t/J= t/J 3. AU= AU= U 4. A(XuY)~AXuAY - -- 5. A(XuY)=AXuAY 6. A(Xn Y)=AX n AY 7. A (Xn Y)c A X nAY 8. A (-X) = - A(X) 9. A (-X) = - A(X) 10. AAX= AAX=AX- -- 11. A AX = AAX = AX Vi du2.6:Khaosatt~pdiI li~uHfJBH, v6iX={x],X5,X6}bi~udi~nkhaini~m Hi?ulvc,va t~pthuQcHnhA={THANH_TOAN}.B6'ivi X]={x]}chic6mQtd6i tUQ'I1gduynhfittrongX, chungtanh~nduQ'c: T~pxfipxi du6itrenA cuaX:AX =X]={x]} T~pxfipxi trentrenAcuaX: AX =X]uX3={x],X5,X6,X7,xs} Vimgbienla:BNA=AX- AX={X5'X6,X7,xs} T~PH(1PxAc DINH vA T~P H(1PKHONG xAc DINH TrongLy thuy~tt~ptho,t~pX c6th~xacdinhho~ckhongxacdinh.N~uAX =AX, tan6it~pXcV xacdinhdlJatren-A,kYhi~ulaA-Xacatnh.NguQ'cl'.li,X khongxacdinh,kyhi~uA-Khongxacatnh. N6icachkhac,t~px xacdinhn~unhuvai b"xEU,tac6th~xacdinhch~ch~nx thuQcX haykhong.Dod6,AX =AX vat~pbiencuaX 1£1t~pr6ng. MQiTl)pkh6ngxacainhX thuQcmQtrongcaclapsau: 1.N~uAX;z!:cjJvaAx;z!:UthiX 1aXacainhth6tren-AtrongS. 2.N~uAX ;z!:cjJvaAX = Uthi X 1£1Kh6ngxacainhngoaitren-AtrongS. 3.N~uAX =cjJva AX;z!:U thiX 1£1Kh6ngxacainhtrongtren-AtrongS. 4.N~uAX = cjJva AX = U thiX laKh6ngxacainhhoanloantren-AtrongS. Vi do2.7:KhaosatmQtHTTT S=,trongd6U={xj,...,Xll}vaAc Q v6'icaclaptUO'llgduO'llgnhusau: E]={x], X2} E2={x], X4} E]={X5,X6,Xl} E4={XS, X9} E5={xJO, Xll} Cact~p: X]={x],X4,xs,X9} Y]={X5J X6, Xl} Z]={X5, X6, Xl, X]O,Xll} 1£1cac t~p xac dinh. Cact~p: X2={x],X5,X6,Xl, Xs,X9,Xll} Y2={ X], X5, XJO, Xll} Z2={X],X2,X5,Xl} 1£1cact~pthokhongxacdinhvacact~px~pxi nhusau: AX2 =E]uE4={ X5,X6,Xl, Xs,X9} AX2=E] u E] u E4 U E5 = {X],X2,X5,X6,Xl, Xs,X9,XJO,Xll} 4Y2 = E5={XJOJXll} A Y2=E2 U E] U E5 = {x],X4,X5,X6,Xl, XJO,Xll} 4Z2 = E]={x], X2} AZ2= E] uE] = {X],X2,x5,X6,Xl} Caet~p: X3={XJ, X2,X3,XS,xs, XlO} Y3={XJ, X3, X4, X6, Xl, X9, XlO} Z3={X2, X4, X6, XS, X9, Xn} lavi d\lv€ eaet~pkh6ngxaedinhngoai.Caet~p x~pxi la: AX3 =EJ={xJ' X2} AX3=u AY3 =E2={X3'X4} A Yj=U AZ3 =E4={xs,X9} AZ3=u Caet~p: X4={xJ,X3,xs} Y4={X2,X4,X6,xs} Z4={X3,xs,xs}laeaet~pkh6ngxaedinhtrong.Caet~px~pxi la: AX4= ljJ AX4=EJ U E2 U E4 = {Xl,X2,X3,X4,xs, X9} AY4= ljJ A Y4=EJ uE2 uE3 uE4 = {Xl,X2,X3,X4,XS,X6,Xl, xs,X9} AZ4= ljJ AZ4=EJ U E2 U E3 = {X3,X4,XS,X6,Xl, xs, X9} Caet~p: Xs={Xj, X3,XS,xs, XlO} Ys={X2,X4,X6,X9,XlO} Zs={Xj,X4,Xl,xs, Xll}lavi d\lv€ eaet~pkh6ngxaedinhhoantoan. L....- 32. Vi do2.8:xetT~pdfrli~uSO Bane:2.5:T~pdfrli~uSO Cacky hi~up, q, r, StUO1lg(rugtrongdfrli~ubilOhi~mcoynghia(Ghichu:cac kYhi?up, q, r, S fadoh(JcvienkYhi?uadbidudiln): - p: Hinhthucthanhloan.0:thanhloantheo3thangmQtleln(hangqui);1:thanh loantheo6thangmQtleln(mlanam);2:thanhloantheo12thangmQtleln(hang nam). - q:Coxetnghi~mykhoahaykhong.1:coxetnghi~m;0:khongcoxetnghi~m. - r: HQ"Pd6ngdfitUngcovaykhong.0:hQ"Pd6ngchuacovay;1:hQ"Pd6ngdfi rungcovaydokhachhangyetiCelli;2:hQ'pd6ngdfitungcovayt\ldQng. - s:hQ"Pd6ngconhi~ul\lc haykhong.1:hQ"Pd6ngconhi~uh!c;0:hQ"Pd6nghuy haym~thi~ul\lc. KhilOsath~th6ngthongtintubang2.8.V6i A={p}va Yj= {X2,X4,xs}lamQtt~p xacdinhtho.B6i vi: 4Yj =X2={X4,xs} A Yj =X2uXj ={X2,X4,X6,xs} T~pY2={Xj,X2,Xi}lamQtt~pkhongxacdinhtrong.B6i vi : DBi ttrQ'ng CacthoQctinh U p q r s Xj 0 1 1 0 X2 2 1 0 1 Xj 0 0 0 1 X4 1 0 2 0 Xs 0 1 1 0 X6 2 1 0 1 X7 0 1 1 0 Xs 1 0 2 1 X9 0 0 0 1 33 AY2= ljJ A Y2=XlV X3 = {Xl,X2,X3,X5,X6,X7,X9} T~pY3={Xj,X2,X4,X6}lamQtt~pkhongxacdinhngoai.B6i vi: AY3 = X3={X2,X6} A Y3=XjuX2 uX3 = V T~pY4={Xj,X2,X4}khongxacdinhhoantoan.B6i vi: AY4 = ljJ A Y2=Xj uX2 uX3= U 2.6.DOCHiNHxAc CUAxAp xi T~ptho clingc~pphuangphapdinhlm;mg,mJCluQ'llgv€ ch~tluQ'llgcuaphep x~pxi t~phqpX EUtrongkhonggianx~pxiAS=(S,IND(A)),b~ngcachsird\mgt~t cacaclaptuang.~uangtrongquanh~tuangduangIND(A)v6'iAEQ.MQth~th6ng thongtinS=,A EQ vaX EU dilxacdinhduQ'cmQtkhonggianx~pxi AS=(U,IND(A)). DQchinhxaccuamQtx~pxi cuat~pd6itUQ'llgX trent~pthuQctinhA duQ'cdinh nghlanhusau: aA (X) =cardAXcardAX Di€u nayd~danghi~uduQ'cr~ngn~ut~pX duQ'cx~pxi chinhxactrongkhong gianx~pxi AS v6'iA EQ, thi aA(X)=1.N~uX duQ'cx~pxi khongchinhxacthi 0<aA (X) <1. D~chQnduQ'cdQchinhxaccuamQtx~pxi chungtadinhnghlanhusau: P A(X) =1 - a A(X) Va duQ'CgQila d;;mgtho cuat~pX. D~,mgtho la mQtkhaini~md6i l~pv6'idQ chinhxac,nobi~udi~nmucdQkhongchinhxaccuax~pxi chot~phqpX trong khong ianx~pxiAS=(U,IND(A)). DQchinhxacx~pxi aA(X)cocacthuQctinhsau: -" 1. IfA c:Q , X c:U, 05{a A(X)5{1 2. N~uaA(X)=1thiBNA(X)= fjJ(AX =AXva t?PX coth~xacdinhdlJatrenA) 3. N~uaA(X)<1thiBNA(X),rfjJ(t?PXkhongth~xacdinhd\l'atrenA) STjKHONGCHAc CHANvA HAM THANH VIEN THO CUA MOT T~P HQP Vi~cmotakhaini~mmah6coth~chuaducmgbaocacd6ituQ'ng.Tinhkhong ch~ch~ncolienquaild~ny tu6ngthanhvien- mQtph~ntucuat?Phgp.Tirngu canhcuaT?pthochungtacoth~dinhnghlamQt?Phamthanhviencoquailh~d~n khaini~mt?Ptho.Dinhnghlanaycoth~duQ'ckhaosatb~ngmQtdQdokhac.Ham thanhvienthocuamQtd6itugngx trongt?PX duQ'cdinhnghlanhusau: ,u\x) =card([xLnX) x card([xL) , A Trongdo 0~,u (x)~1x D~ctrungv€ dQdo SlJkhongch~cch~ncuad6i tugngx trent?PX v6'itri thuc duQ'cxacdinhtrongh~th6ngthongtinduQ'cdinhnghlanhusau: ( ) card([x]A n X) ,uxx = card(U) Chungtacoth~timraS\l'khacbi~tgiUahaithu?tngumah6vakhongch~c ch~n.Tinhmah6colienquaild~ncact?Pd6itugng(c~pdQkhaini~m),trongkhi d6tinhkhongch~ch~nthilienquaild~ncacthanhph~ncuat?Phgp.T?pthoda: chungminhr~ngthinhmah6duQ'cdinhnghladu6'id~ngkhongch~ch~n. Hamthanhviencuat?Pthocoth~duQ'csudvngd~dinhnghlax~pxi trenva x~pxi du6'icuamQt?PhgpvaduemgbiencuamQt?Phgp: M={XEU:,u1(x)=1} AX={XEU: ,u1(x»O} BNA(X)={XEU:O<,u1(x)<1} 35 Vi du 2.9:Tir t~pdfrli~uRUBB, v6i A={THANH_TOAN}velXI= (Xl,XS,xd, chungtatinhduQ'c: aA(Xl) = I{Xl}I =.!.=0.2 I{XI'XS,X6,X7'XS}I 5 2.7.PHEPxAp xi vA DOCHiNHxAc CUAPHANLOP Khaini~mt~px~pxi coth€ marQngchokhaini~mx~pxi phanho~chcuacac t~pd6ituQ'ng{Xl,X2,...,Xn}.ChoS=,A cQ, Y={XI,X2,...,Xn}v6i \?Xic U (1 ::::i::::n) leimQtphanlap (mQtphanho~ch,hayhQcuacact~pcon)trang U.HQcuacact~phgp Y= {Xl,X2, ... , Xn}duQ'cgQileimQtphanlap trangU cuaS, n~uXinXj=fJ v6i Ii i,j ::::n , i ;z!:j velU;=lXi =U .XiduQ'cgQileicac16pcuaY.V6i t~pthuQctinhtinhAct2thix~pxi trenvelx~pxi du6icuaphanho~chY trenh~ th6ngthongtinS,duQ'cki hi~uAYvelA YduQ'cdinhnghlanhusau: A Y = {AXI' AX2,...,AXn} - - - - A Y= {AXI, AX2,...,AXn} TrangdoA Y duQ'cgQileiVimgkhlmgatnhtren-Acuaphanho~chY BNA(l)= A Y - AY leiVimgbientren-Acuaphanho~chY, Vitngkhlingatnh tren-Acuaphanho~chY duQ'cxacdinhbaibi€u thucsau: POSA(l)=UX,ElAX; vaVimglfac Ilf(Jngtren-Acuaphanho~chY trongS lei: BNA(Y)=U BNA(XJ XiEl B6'ivi U =UX,ElAXi nenphanho~chY khongco Vitngphu atnhtren-Atrong h~th6ngthongtinS. Phanho~chY duQ'cgQileiXac atnhtren-An~umQilapXiEY d€u lacact~pXac atnhtren-A,nguQ'cl~iphanhQachY gQileiKhongxacatnhtren- A.Phanho~chY duQ'cgQileiXacatnhthotren-An~u3XiE Y,AXi ;z!:0. £)Qchinhxacphepx~pxi cuaphanho~chY b~ngt~pthuQctinhA duQ'cdinh nghlanhusau: 36 "n card(AX.) aA(Y)=L.J~=i = I I;=icard(AX;) Ch~tluQ'llgx~pxi cuaphanho~chY trent~pthuQctinhA duQ'cdinhnghlanhu sau: "n card(AX.) PA(Y)=L.J;=i - I card(U) Bi~udi~nti s6 cuat~tca cac d6i tUQ'llgduQ'cphan lo~idlJa trent~pthuQctinhA v&it~tcacacd6itUQ'llgtrongh~th6ngthongtin S. y tucmgv~dQchinhxaccuaphanlo~ichophepchungtadinhnghlahimth~nao dQchinhxaccuamQtphanho~chco th~x~pxi mQtphanho~chB* trent~pthuQc tinhBQ2 b~ngmQtphanho~chA* trent~pthuQctinhAQ2 coth~dinhnghlanhu sau: PA(B')=cardPOSA(B') card(U) trongdo: POSA(B')= U AX; X,ES' duQ'cgQilaVimgkh~ngdinhcuaphepphanhQachB* trent~pthuQctinhA, dInhien taco O~PA(B')~l, \7'A,BQ2. Vi do2.10:xetvi d\lv~HTTT cuaBHNTnhubang2.5: Cackyhi~up,q,r, stuO'nglingtrongduli~ubaahi~mcoy nghla: - p: hinhthlicthanhtoan;0: thanhtoanthee3 thangmQtlfin(hangqui); 1:thanh toanthee6thangmQtlfin(mranam);2:thangtoanthee12thangmQtlfin(hang nam). - q:Coxetnghi~mykhoahaykhong;1:coxetnghi~m;0:khongcoxetnghi~m. - r: hQ'pd6ngda:tungcoyaykhong;0:hqpd6ngchuacoyay;1:hqpd6ngda: tungcoyaydokhachhangyeticfiu;2:hqpd6ngda:tungcoyaytlJdQng. - s:hqpd6ngconhi~uIlJc haykhong.1:hqpd6ngconhi~uIlJc; 0:hqpd6ngbuy haym~thi~uIlJc. 37 Bang2.6:MQth~th6ngthongtinv6iphepphanlap Khaosat.?~th6ngthongtinill bang2.5.V6i A={p,q,r, s}(A=Q)vaffiQtphan ho(;lchY={fj, f2, f3},trongd6: fj={xj, X2,X3} f2={X4, X5, X6, Xl} f3={XS, X9} Cact~ptuangduangkhaosattrent~pthuQctinhA: Zj={Xj, X5,Xl} Z2={X2,X6} Z3={X3,X9} Z4={X4} Z5={XS} H~th6ngthongtinv6iphanho(;lchtrinhbaytrongbang2.5.DQchinhxaccua phanho(;lchaAen vachfttluQTIgphanho(;lchPAenduQ'Ctinhnhusau: d.Y ={Afj, Af2,Af3}={{},Z4,Z5}={{},{X4},{XS}} - - - A Y = {A fl. A f2, A f3} = {{ZjJZ2,Z3},{Zj,Z2,Z4},{Z3,Z5}} = {{Xl, X2, X3, X5, X6, Xl, X9},{Xj, X2, X4, X5, X6, Xl}, {X3'Xs, X9}} r u p q r s Xj 0 1 1 0 Yj X2 2 1 0 1 X3 0 0 0 1 X4 1 0 2 0 Y2 X5 0 1 1 0 X6 2 1 0 1 Xl 0 1 1 0 Y3 Xs 1 0 2 1 X9 0 0 0 1 0+1+1=0.125 aA(Y)=7+6+3 0+1+1 PACt)= 9 =0.222 2.8.PHEP PHAN LOP vA PHEP RUT GQN SlJ rheinlapduQ'cxemnhumQtti~ntrinhxu ly nh~mxacdinhmQtlapduynhftt mamQtd6ituQ'ngthuQcv~lapdo.Cacd6ituQ'ngcoth~duQ'crheinlo~iv~caclap dlJavaotunggiatri cuathuQctinhquy~tdinh.M6i lapcoth~duQ'cxacdinhdlJa trencacd~ctrungcuathuQctinhquy~tdinhtuangungcualapdo.SlJrheinlo~id6i tuQ'ngthanhcaclapd6ituQ'ngcoth~thlJchi~nduQ'chidlJavaomQts6itcacthuQc tinhtrongt~pthuQctinhcuah~th6ngthongtin.Thongthuangtrongvo s6cac thuQctinhcuad6itUQ'llgchicomQts61£1quailtr<;mgchom\!cdichrheinlo~icacd6i tuQ'ng.Tliy vaokhanangthichhQ'Pcuaconnguaivakhanangthongminhtrong. . rheinlo~ik~thQ'Pvaivi~cchQnllJadungcacd~ctrungquailtrQngnhfttcuacacd6i tuqng. MQts6thuQctinhtrongh~th6ngthongtinkhongquailtrQngcoth~duQ'cgiam bathaybi lo~itm mavftnkhonglammfttnhfrngthongtinrheinlapquailtrQng. Phuangphaptimrat~pthuQctinhnh6banbinhthuangvaiclingkhanangrheinlap gQi1£1PheprutgQnthuQctinh.Nhuv~ykh6iluQ'llgh~th6ngthongtinbandc1uco th~duQ'cgiamthanhmQth~th6ngthongtinvaiquymonh6ban. T~pthochophepchungtaxacdinhcacthuQctinhquailtrQngnhfttcuamQth~ th5ngthongtinchotruactheodungquaildi~mrheinlo~i.Chicc1nmQts6thuQctinh 1£1coth~duytri quailh~tuangduang.T~pt6i thi~ucacthuQctinhnhuv~ygQi1£1 ffiQtrutgQn.Phc1nchungcuacacrutgQngQi1£1Wi.Deiy1£1haikhaini~mcabansu d\lngtrongrutgQntrithuc. MN s6thuQctinhcoth~l~iph\!thuQcvaocacthuQctinhkhac.Vi~cthayd6i trenthuQctinhquailteimcoth~anhhuangd~ncacthuQctinhkhackhisud\!ngmQt s5phuangphapphituy~n.T~pthoxacdinhduQ'cmucdQph\!thuQcuacacthuQc tinhvaynghlacuachung.Trongm6iquailh~tuangduang,SlJph\!thuQccuacac l thuQctinhlamQtrongnhungd{tctrungquailtn;mgnh~td6iv6imQth~th6ngthong tin. ChoH~th6ngthongtinS =,v6iC lat~pthuQctiOOdi€u ki~n,D la t~pthuQctinhquy~tdinh,Q=CuD, AcC, chungtacoth~dinhnghlami€nkh~ng dinhcuat~pthuQctiOOAla POSA(D)trongquailh~tuangduangIND(D)nhusail: POSA(D) = u{AX IX E IND(D)} Mi€n kh~ngdinhPOSA(D)chuat~tcacacd6itUQ1lgtrongU, cacd6itUQ1lgnay co th~duQ"cphan10£;1ihoantoanthaOOcaclap phanbi~tdffduQ"cdiOOnghlatrong quailh~tuo-ngdUO-figIND(D), dl,1'avaothongtintrenquailh~tuo-ngdUO-figIND(A). MQtmi€n kh~ngdiOOco th~duQ"ct£;1ora b~nghai t~pthuQctiOOb~tki A, B EQ trongh~th6ngthongtinS.T~pconcacthuQctiOOBEQ dinhnghlaquailh~tuang duangIND(B) va phanhO£;1ChB*(U/IND(B)) d6i v6i t~pconA. MiJn khlingajnh tren-AcuaB dinhnghlaOOusail: POSA(B)= U AX; X;EB' Mi€n kh~ngdinhcuaB chuat~tcacacd6i tUQ1lgmadl,1'avaot~pthuQctiOOA, coth~phan10£;1ihoantoanthaOOcaclapphanbi~trongphanhO£;1ChB*. TapthoclingdinhnghladQph\)thuQcgiuacact~pthuQctinh.Kich thu6cMiJn khlingajnhtren-Acuaphanho£;1ChB duQ"csird\)ngd~diOOnghlamQtdQdov€ Sl,1' ph\)thuQccuat~pthuQctinhA vaB. (rA (B) ) rA(B)- card(POSA(B)) card(U) Chungtacoth~noir~ngt~pcacthuQctinhB ph\)thuQcvaot~pcacthuQctinhA v6imQtdQph\)thuQcb~ngrA (B) . Choh~th6ngthongtinS=, hait~pthuQctinhA,Be Q.T~pthuQc tinhB ph\)thuQcvaot~pthuQctiOOA trenS,kyhi~uA~B. N~uvachin~uqUailh~ tuangduangthoaIND(A)e IND(B).T~pthuQctiOOA vaB dQcl~ptrenS n~uva chin~u:ho{tckhongA~B ho{tckhongB~ A. T~pB ph\)thuQcvaot~pA trongh~ th6ngthongtinSv6ikdQduQ"cdiOOnghlanhusail: 4V A~B,O::; k::;1,if k =rA(B) TrongdorA(B)duQ'cmota6tren. N~uk=], t~pB ph\!thuQchofmtofmvitot~pA (ho~cB--+A), N~uk=0,t~pB dQcl~phoantoanv6i t~pA, Cactwangh<JPconll;lithi t~pB ph\!thuQcthovitoA. DQ do ynghiacuathuQctinh aEA trongt~pthuQctinhA d6i v6i phfinlOl;li B*(UIIND(B)) duQ'cxacdinhnhugall: card(POSA(B)) - card(POSA-{a}(B)) J-iA,B(a)= card(U) SlJ quailtn;mgcuathuQctinha trongt~pAQ2trenphfinhOl;lChg6cQ* tirh~ th6ngthongtinS duQ'cki hi~unhugall: J-iAa)=J-iA,Q(a) Chungtaseki€m tracactinhchfitcuat~pthu(>ctinhA trongmQth~th6ngthong tinS= nhugall: 1. T~pAQ2 hiph\!thuQctrongS n~uvachin~u3Bd saochoIND(B)=IND(A) (vid\!:aB(X)=aA(X))' 2. T~pAQ2 ladQcl~ptrongS n~uvachin~utIEd, IND(B)~IND(A),(nghiala, aB(X)<aA(X)). 3. T~pAct! lathiratrongSn~uvachin~uIND(Q-A)=IND(Q),(nghiala,aQ-A(X) =aQ(X)). 4. T~pAQ2la rutg<;mcuaQ trongSn~uvachin~uQ-A lathiratrongQ vaA ph\! thuQCtrongS. MQth~th6ngthongtincotheconhi€ucachrutgQnkhacnhau.Choh~th6ng thongtinS=. N~uAQ2 la mQtt~pthuQctinhrutgQnthih~th6ng thongtintUOTIg(rngS'= v6i t~pthuQctinhrutgQnA, S' gQilah~ th6ngthongtinrutgQn.Noi cachkhac,h~th6ngthongtinS' duQ'cxfiydlJllgtirh~ th6ngband~uS b~ngcachlol;lib6mQts6cQtlienquaild~ncacthuQctinhnao khongcotrongt~pthuQctinhrutgQnA. 41 Vi du2.11:Khaosatt~pdii'li~uHDBHtirbang2.1, - Chungta chQnhait~pthuQctinhconA={THANH_TOAN,MENH_GIA}va B={sAN_PHAM}. PhanhOi;lChA * (phanhOi;lChU/IND(A)), tuO'ngling v6i m6i quailh~tuO'ng duO'llgIND(THANH- TOAN)trent~pthuQctinhA: A * ={Yj= {Xl},Y2={X2,X4},Y3={X3},Y4={X5,XS}'Y5= {x6J,Y7={X7}}' PhanhOi;lchB* (phanhOi;lChU/IND(B))tuO'nglingv6i m6iquailh~tuO'ngduO'ng IND(THANH_TOAN),B*={X]={xiJ,X2={X2,X3,X4},X3={X5,X6,X7,xs}}. Mi~nkhlingainhtren-AcuaB tinhnhusau: POSA(B)= U AX =AXJ+AX2+AX3 XEB" = {xiJ+{X2'X3,X4}+{X5,X6,X7,xs} Vi v~~,rB(A)=r=1, chungtor~ngB ph\!thuQchoanto~nvaoA, A~ B. - ChQnhai t~pcon thuQctinh A={THANH_TOAN,MENH_GIA} va B= {sAN_P HAM}. PhanhOi;lchA * la: A *={Yj={xiJ,Y2={X2,X4},Y3={X3},Y4={X5,xs},Y5={X6}, Y6={X7}}' Phan hOi;lChB* (U/IND(B)) tuO'ng ling v6i quail h~ tuO'ng duO'llg IND(THANH_TOAN) tren t~p thuQc tinh B={SAN_PHAM}, B*={Xj={x]}, X2={X2,X5}'X3={X3,X7},X4={X4},X5={X6,XS}}' Mi~nkhlingainhtren-Acuat~pthuQctinhB la: POSA(B)=U AX =AX!+AX2+AX3+AX4+AXs XEB" = {xd+{}+{X3,X7}+{}+{X6} Vi v~y,rA(B)=~=0.5,chungtor~ngB ph\!thuQcvaoA v6idQph\!thuQc0.5, A o.s)B . 42 RUTGQNvA LaI CUAH:f:THONG THONG TIN T~pthut)ctinhtrongh~th6ngthongtinbandelucoth~duqcrutgQnthanhmt)t phfmho~chd~cbi~tA* tirt~pthut)ctinhA~. Conghlar~ngmt)th~th6ngthong tincoth~khongm~nhv6'iluqngthongtinduthiranay.N~uth\fchi~nphepphan laptrenh~th6ngthongtinnaythicoth~choramt)tk~tquacotinht6ngquathoa th~pkhiduqcthunghi~mtrencacd6ituqngitph6bi~n. D\fatrencactinhch~tv~S\fph\!thut)cgiuacacthut)ctinhtrongh~th6ngthong tin,chungtad~dangtimracacthut)ctinhduthira,b~ngcachlo~ib6cacthut)ctinh khongcolqi,mavfinkhonggiamdikhanangphanlo~itrenh~th6ngthongtinm6'i nay(h~th6ngthongtindilduqcrutgQn).D~khaithactrithuchi~uquatirh~th6ng thongtinchungtatimrat~pcacthut)ctinht6iUtiduchom\!cdichphanlo~ivad~t tinht6ngquatcaonh~t. Choh~th6ngthol)gtinSvat~pthut)ctinhconA~, mt)thut)ctinhqEA,gQila khaphantrent~pA n~uIND(A)=IND(A- (a})conghlala:quailh~tu<mgduang sinhratirt~pA vaA - {a}la gi6ngnhau.Nguqcl~i,thut)ctinha lab~tkhaphan tren-A.S\f xu~thi~ncuamt)tthut)ctinhkhaphankhongcM thi~nduqcsucm~nh phanlo~icuah~th6ngthongtinvakhongthayd6iquailh~ph\!thut)cuah~th6ng bandelu.Nguqcl~i,thut)ctinhb~tkhaphanmangthongtincelnthi~tv~mt)ts6d6i tuqngtrongh~th6ng. T~phqpt~tcacacthut)ctinhbfitkhaphantrongt~pA~ gQilaloi cuaA trenS, vakyhi~ulaCORE(A).T~pthut)ctinhloi cochuat~tcacacthut)ctinhkhongth~ lo~ikh6it~pA n~ub6chungdich~ch~nlamthayd6iphanho~chA*.T~plOicua 'A coth~lat~pr6ng. Chohait~pthut)ctinhA, B~ trenS.Mt)tthut)ctinha gQilakhaphantrenB trongt~pA n~uPOSA(B)=POSA-{a;(B).Nguqcl~i,thut)ctinha gQilab~tkhaphan trenB trongA. N~umQithut)ctinhcuaA lab~tkhaphanB, thiA b~tkhaphanv6'i B.T~pt~tcacacthut)ctinhb~tkhaphanB trenA gQila lOituangquailB cuaA ky hi~uCOREs(A): COREs(A)= (aEA: POSA(B);£POSA-{a;(B)} 43 T~pthuQctinhAQ2 gQila tI1Jcgiaon€u t~tcacacthuQctinhcuan6b~tkha phan.MQtt~pconthichhQ'PEcA duQ'cdinhnghlanhut~prutgQncuaA trenSn€u E lamQtn.rcgiaovabaatoankhaniingphanloc;ticuatapA. Dod6,t~prutgQncua A (RED(A)),dinhnghlanhusau: E =RED(A)(E c A, IND(E)=IND(A),E fam(Jtnrcgiao) E gQilamQtrutgQncuaA (nghlala:E=RED(A))n€u E la t~pthuQctinht6i thi~ukhaphant~tcacacd6itUQ'llgtrenS khaphanb6'itoanbQt~pA,A khongth~ rutgQnthemduQ'cnfra. T~tcacacrutgQn(hQcacrutgQn)cuaA, kY hi~uREd' (A).Giaocuat~tcacac t~prutgQncuaA gQila16icuaA: CORE(A)=n RED(A) TuO'11gtlJ chungtac6th~dinhnghladuQ'cquanh~rutgQnlienquandenhait~p thuQCtinhA,BQ2 trongS. T~pA gQila trlJcgiaoB (B-orthorgonal)n€u t~tcacac. thuQctinhcuaA lab~tkhaphanB (B-indispenable).B~tkyt~pcontI1JcgiaoB cua A gQilarutgQnB cuaA, vakYhi~ulaREDB(A): E =REDB(A)(E c A,POSE(B)=POSA(B),E trlfcgiaoB) N6icachkhac,EcA gQilamQtRutg9ntren-BcuaA trongSn€uE dQcl~pvaiB vaPOSdB)=POSA(B).N6icachkhac,E cA gQilaREDB(A)cuaA lat~pthuQctinh t6ithi~utrenA, khaphanvait~tcacacd6ituQ'ngtrenSb6'itoanbQt~pA vakhong th~rutgQnduQ'cnfra.TAtcacact~prutgQnB duQ'ckYhi~uREDBF(A).Giaot~tca cact~prutgQnB cuaA latUO'11gquan16iB cuaA: COREB(A)=n REDB(A) RUTGQN CUA PHAN HO~CH Y vA LOI CUA PHAN HO~CH Y Vi~cdinhnghlat~p16ivat~prutgQnclingc6th~thlJchi~nduQ'cb~ngcachhi~u theophanloc;tirent~pd6itUQ'llgU. Vai h~th6ngthongtincuamQtphanhoc;tch Y={Xj,X2,... Xn}vai ~cU (0 ::;i ::;n) nhu la mQtphanloc;ticuaU trenS, U~XI.=U .I=J 44 T~pthuQctinht6iti~uAcQ saochoch~tluQ'Ilgcuaphanlo~iPA(Y)=PQ(Y)gQi larutgQnphanho~chr, vaki hi~uREDr(Q). Noi cachkhac,t~pthuQctinhcont6ithi~uA dQcl~ptrenSvaA*=Q*.Nghlala, phanho~chA*vaQ* cuaU duQ'csinhb6'ihQt~tcacaclaptUO'llgduO'llgcuaquan h~b~tkhaphanIND(A)vaIND(Q)tuO'llgtmggi6ngnhau. H~th6ngthongtinS coth~conhi~urutgQnY. T~tcacacrutgQnr kyhi~u RED!(Q), nghlalamQiA ERED!(Q) PA0) =PQ(Y). Giaot~tcacact~prutgQncuar, coth~nh~nduQ'cacthuQctinhcoynghla nh~tchovi~cphanlo~itrongh~th6ng,gQila16icuaY: COREy(Q)= n A= n REDy(Q) AeRED{(Q) REDy(Q)eRED{(Q) Vi v~y,16ir lat~pthuQctinhchudnmakhongth~lo~ibo,n~ubochungdithi ch~ch~ngiamdich~tluQ'Ilgcuaphanlo~ir. Vi do2.12:Khaosath~th6ngthongtinHBBH.Cohaid~grutgQntrent~p di~uki~nC({THANH_TOAN,Mf!;NH_GIA,SANYHAM})v6'imQt~pquy~tdinh D({d})nhusau: B]={THANH_TOAN,Mf;NH_GIA} B2={THANH_TOAN,SAN_PHAM} L6i cuat~pthuQctinhCvaD duQ'cdinhnghlanhusau: CORED(C)=B]nB2 ={THANH_TOAN} Chungtacoth~noir~ngthuQctinh"THANH_ToAN" lathuQctinht6tnh~tviB] vaB2lahait~pthuQCtinhmacoth~phanlo~icacthuQctinhquy~tdinh. Vi~cchQnt~prutgQn,vi d\lB]={THANH_TOAN,Mf!;NH_GIA},chungtaco th~giam kich thu6'ctIT bangdfi' li~ug6c b~ngcach lo~i bo thuQctinh "SAN_PHAM'.Bang2.6chinhlabangrutgQnnhungv~nbaotoant6tcacthuQc tinhchoquandi~mphanlo~i. i L 45 Ban22.7:Bangquy~tdinhdiiduQ'crutgQnHDBH D6i ttrQ'ng CacthuQctinhdi~uki~n CacthuQctinhquy~t dinh u C THANH ToAN Mf:NH-GIA D DUY TRi Xl 3 6 Nh6 Trungbinh L6n Hi~uh,rc Huy Huy Xl Xl 6 6 Trungbinh Nh6 Trungbinh L6n Huy Hi~uh,rc X4 Xs 12 12 Hi~ul\lc Huy X6 X7 12 12 Nh6 :tIuy.Xs Vi du: Khaosath~th5ngthongtintirbang5,chungtacohait~prutgQn REDr= {{p,s},{q,r,s}} Vat~pnhancuaphanho~ch1: COREr(A) = {s} f)~tAi ={p,s}vaA2={q,r,s}.T~pxfipxi vachfitluqngcuaphanlo~inhusau: AIY={AI~,AIYz,AI~}={{},{x4},{Xg}}- - - - ~Y ={~~,~Yz,~~}={{},{X4},{Xg}}- - - - 0+1+1 poet)=PA(Y) =PA (Y) = =0.222- I 2 9 2.9.cAc LU~T QUYET DJNH MQttrongnhungungdvngquantrQngcuaT~ptholaduaranhUnglu~tquy~t dinhchovi~cphanlapcacd5ituqngtrongh~th5ngthongtinchotruac,ho~ctien d011nlapcuad5ituqngmaioSird\mgbangquy~tdinhg5chaybangquy~tdinhrut L-