H CNTT Tp HCM

Seminar C s Tri Thc

LI NOI AU
Nhng o th la mot khai niem manh hu ch cho nhng nhiem vu khac nhau trong khoa hoc va ky thuat. Trong nhng ng dung nh s nhan dang va s phuc hoi thong tin, oi tng ong dang la mot van e quan trong. Neu nhng o th c s dung cho s bieu dien oi tng, roi la van e cua viec xac nh s giong nhau cua nhng oi tng quay vao trong van e cua s so sanh o th. Mot trong nhieu dang thc so sanh o th chung nhat bao gom o th va s do tm o th con ong dang, s trch ra o th con chung cc ai va dung sai o th. Mot so giai phap cho tat ca nhng nhiem vu nay a c e xng trong tai lieu, nhng moi th hng chu o phc tap tnh toan cao cua s so sanh o th von co. Mot van e bo sung xuat hien trong nhng ng dung ay mot o th au vao se c so sanh phu hp vi ti o th n khac trong toan bo c s d lieu cua nhng o th so sanh di mot dang thc a cho. Neu c s d lieu ln, s so sanh tuan t cua o th au vao vi moi o th t c s d lieu viec s dung nhng cach tiep can truyen thong tr nen khong the lam c. Hai chien lc c ban a c phat trien. Chien lc th nhat nham muc tieu xac nh vai tro thanh vien trong mot loai cua o th au vao da tren mot cay quyet nh phan loai cac mau. Chien lc th hai da tren y kien ve phep phan loai. Phep phan loai nay ch xac nh mot o th mau au vao co thuoc ve mot loai nao o hay khong? Trong seminar nay, s so sanh cua nhng o th au vao vi c s d lieu cua nhng o th c hoc. Nhng dang thc lay lai khac nhau, tc la la ong dang o th, ong dang o th con, va dung sai o th, s so sanh c xem xet. Cach HV: Nguyen Thai Nho MSHV: CH0401036 Trang 1

H CNTT Tp HCM

Seminar C s Tri Thc

tiep can theo uoi c da tren so sanh nhng vector ac trng a c rut t nhng o th. Y tng se s dung nhng ac tnh ma co the c tnh toan nhanh t mot o th. a ra mot so tiem nang ln cua nhng ac tnh nh vay. S so sanh cac vector at trng cua o th, quan trong la tiet kiem thi gian trong tnh toan co the thc hien nhanh hn trong nhng o th phc tap lam noi bat s trch ra va nhanh ngang, quyet nh so sanh ti mot o th ay u.

HV: Nguyen Thai Nho MSHV: CH0401036

Trang 2

H CNTT Tp HCM

Seminar C s Tri Thc

MUC LUC
LI NOI AU.................................................................................1 MUC LUC...........................................................................................3 TONG QUAN......................................................................................4 I.1 Gii thieu....................................................................................4 C S LY THUYET VA PHNG PHAP NGHIEN CU...........7 II.1 LY THUYET O TH.................................................................7 II.2 GIAI THUAT TM KIEM NHANH CAY....................................11 II.3 Chuan tach:.............................................................................13 II.4 Phep m rong Rainforest cho tap d lieu ln:................16 NOI DUNG NGHIEN CU VA KET QUA.................................18 III.1 S DUNG O TH D LIEU CO CHON LOC NHNG VECTORS AT TRNG.....................................................................18 III.2 CAY QUYET NH CUA O TH LOC C S D LIEU .......................................................................................................... 21 KET QUA TH NGHIEM.............................................................34 IV.1 TAP D LIEU O TH.........................................................34 IV.2 C S D LIEU O TH LOC NGHIEN CU THC HIEN .......................................................................................................... 35 IV.3 LOC BANG CAY QUYET NH..............................................36 KET LUAN VA KIEN NGH........................................................40 V.1 Nhng ket luan......................................................................40 V.2 Hng phat trien...................................................................47 TAI LIEUTHAM KHAO..................................................................50

HV: Nguyen Thai Nho MSHV: CH0401036

Trang 3

H CNTT Tp HCM

Seminar C s Tri Thc

Chng I

TONG QUAN
I.1 Gii thieu
I.1.1 Nhng o th va o th thch ng o th la mot cong cu manh va pho thong rong rai c dung trong x ly thong tin. Nhieu phng phap cho s phan tch o th a c phat trien va tr nen quan trong trong tin hoc va ky thuat. Nhng khai niem chuan trong s thch ng o th bao gom ong dang o th, o th con ong dang va o th con chung toi ai. Mot cach tiep can khac o s giong nhau cua hai o th la bien phap khoang cach da vao o th con toi ai chung cua g1 va g2. Trong lnh vc o th con chung toi ai, s do tm nhng bien phap nay ang phat trien pho bien. Mot bien phap khoang cach o th c a vao o th con chung toi ai cua hai o th c trnh bay. Bien phap nay co hai thuoc tnh thu v va la ac trng loi cuon cho nhng ng dung khac nhau. au tien, no la mot thc o va nh vay thch hp cho s anh gia giong nhau, lien quan en vai oi tng. Hai la, no khong can bat ky gia tr c ieu chnh nao c ch ro bi ngi s dung. Nhng quan he gia khoang cach ieu chnh cua hai o th va o th con chung toi ai a c trnh bay. ieu o cho thay rang: Khai niem cua khoang cach o th con chung toi ai la mot trng hp ac biet cua o th ieu chnh khoang cach di nhng gia tr ieu chnh ac biet. Do o, nhng giai thuat trc ay c phat trien cho s do tm o th con chung toi ai co the c dung cho viec ieu

HV: Nguyen Thai Nho MSHV: CH0401036

Trang 4

H CNTT Tp HCM Seminar C s Tri Thc chnh khoang cach va ngc lai c xem xet ieu chnh gia tr. Mot s nghien cu nghiem khac hn ve anh hng cua nhng gia tr ieu chnh tren s thch ng toi u cua hai o th. Mot trong ket qua chnh la bat ky giao iem nao o, anh xa cua hai o th toi u di mot ham gia tr ac biet, nhng gia tr o tng ng. o th con chung toi thieu cua hai o th, mot khai niem kep mi oi mi oi vi o th con chung toi ai. No c cho thay rang khai niem nay co mot so thuoc tnh ac trng thu v cho nh ngha cua s giong nhau cua o th. Hn na, nhng khai niem cua o th con chung toi ai va o th con chung toi thieu c ket hp e dan xuat ra mot o th o khoang cach da vao o th con chung toi thieu. I.1.2 S dung cay quyet nh va c s d lieu Trong nhieu ng dung, ac biet la van e nhan dang va phan loai d lieu, phan phc tap ay la cac cap cua o th tang va that s no khong ch la mot cap ma con la so sanh lan nhau, cac phan o th chong lai vi nhau da vao d lieu cua o th. Viec them cac thanh phan vao c s d lieu c so sanh theo tng tien trnh. ieu nay giam i s phc tap cac cap o th. Messmer va Bunke co muc ch la tach ri cau truc ben trong phan thap nhat cua o th. Cac d lieu mau cua o th c tach ri nhau va chung nhau tng phan la tiep theo co th bac theo cau truc mang. Muc ch cua ho la tien en da tren c s cau truc cay lien ke nhau va cho van e cua o th. Ca hai phan gan nh tr nen te hn trong viec tiet kiem bo nh, ieu nay khong thch hp khi c s d lieu o th ln. Shapiro va Haralick e ngh cho viec to chc lai o th, bang y ngha ma o th theo sau no co moi quan he giong nhau va co s quan he lan nhau ai dien cho mot HV: Nguyen Thai Nho MSHV: CH0401036 Trang 5

H CNTT Tp HCM Seminar C s Tri Thc o th. S to chc cho mot o th trong y tng chung nhau cua gan nh la e xuat bi Senguota va Boyer. Lopresty va Wilfong tiep tuc theo y tng cua o th nham phat hien ra s that. Mat du thch hp cho ieu kien cua no e so sanh mot so ln cua cac o th so sanh lien mang. Ho tien en phan lien ket da tren c ban la ai tien e khong thch hp cho d lieu cua o th theo phep ang cau va viec thc hien dung th cho mo hnh. Ket qua, van e truy cap so lieu ln cua o th th van la van e khong giai quyet c mang rong . Trong luan Seminar nay da tren ky thuat may hoc s dung cho van e o. Tap trung vao viec phat trien, hoan tat cac bai test ky thuat nhng phan ky thuat. Khi s dung c s d lieu o th ln. Nhng cap o th tng thch hay bao gom nhng phan tng t vi nhau, bao gom ca phan o th va phan thap cua viec lien ket cac o th. Ca hai phan t ben trong va cac phan the hien loi cho tng cap. Theo y tng nham giam kch thc cua d lieu trong c s d lieu, ta s dung o th e n gian van e nay. Sau khi cac thanh phan a c gom nhom chnh xac cac cap o th a c s dung e lam lai cac phan d lieu cua o th, do o d lieu lu tr c nhieu nhng kch thc c giam di ang ke. Giai thuat cay quyet nh em lai thanh cong tren nhng vector at trng, mot lp c phan bo can gan ti nhng vector thuoc tnh ai dien cho nhng o th. Trong cong viec nay, viec huan luyen mau ai dien cho mot lp c phan bo. Lp cua mot mau huan luyen la ong nhat vi the hien mau cua chnh no t ay c s d lieu cua n mau huan luyen o ton tai n lp trong tap huan luyen nh. Muc tieu cua s la chon nay la an nh s phan bo cac lp la ac biet khong vt qua cay quyet nh HV: Nguyen Thai Nho MSHV: CH0401036 Trang 6

H CNTT Tp HCM

Seminar C s Tri Thc

Chng II

C S LY THUYET VA PHNG PHAP NGHIEN CU

II.1 LY THUYET O TH
o th la mot cong cu mo ta cau truc d lieu manh me va bao quat. No c s dung rong rai trong cac lnh vc khoa hoc ky thuat, cu the la ky thuat nhan dang at trng vat the thong qua cau truc. Khi vat the c mo ta bang o th, van e so sanh cac vat the khac nhau co the xem nh s tm kiem nhng iem tng ong gia cac o th mo ta nhng vat the o. Do o bai toan nhan dang va phan loai tr thanh viec oi chieu cac o th. Ky thuat nhan dang ac trng bang o th la mot y tng thu v v that chat o th la s mo ta hnh thai bao quat. Tuy nhien viec so sanh cac o th oi hoi mot lng tnh toan khong lo do tieu ton kha nhieu thi gian va dung lng may. II.1.1 nh ngha va chu thch: o th la mot tap hp cac iem va ng nh ngha chnh thc nh sau: a . nh ngha 1: Graph Mot o th gom 6 thanh phan G=(V,E,,,LV,LE) Trong o V: Tap hp cac nh cua o th E VxV : Tap hp cac canh : V LV : Nhan cua nh : ELE: Nhan cua canh LV: Tap hp nhan nh HV: Nguyen Thai Nho MSHV: CH0401036 Trang 7

H CNTT Tp HCM LE: Tap hp nhan canh thuoc tnh cua no b . nh ngha 2: o th con

Seminar C s Tri Thc

o th c nh ngha dung e tham chieu en

Mot o th con gs = (Vs , Es , s , s , LV , LE ) cua o th g, gs g, co 6 cach, ay VS V, ES E (VS x VS), S(v) = (v) v VS va S(e) = (e) e ES. c . nh ngha 3: o th ong dang Mot ham song anh u : VV la mot o th ong dang t o th g=(V,E,, , LV, LE ) t mot o th g= (V,E,,, LV, LE) neu: (v) = (u(v)) v V Bat ky cac canh e = (v1, v2) E o ton tai canh e = (u(v1), u(v2)) E sao cho (e) = (e); cho bat ky e = (v1, v2) E o ton tai e = u-1(v1), u-1(v2) E sao cho (e) = (e). d . nh ngha 4: o th con ong dang Mot ham n anh u : VV la mot o th con ong

dang t g en g neu o ton tai mot o th con gS gsao cho u la mot o th ong dang t g en gS .

e . nh ngha 5: o th con chung toi ai Cho hai o th g1 = (V1, E1, 1, 1, LV , LE ) va g2 = (V2, E2, 2, 2, LV , LE ) mot o th con chung c nh ngha nh o th g = (V , E, a, b, LV , LE ) sao cho mot o th con ong dang HV: Nguyen Thai Nho MSHV: CH0401036 Trang 8

H CNTT Tp HCM Seminar C s Tri Thc ton tai t g en g1 nh t g en g2 . Mot o th con chung g cua g1 va g2 c goi la o th con chung toi ai, neu khong ton tai o th con chung khac cua g1 va g2 vi nhieu nut hn so vi g.

f . nh ngha 6: o th con chung toi thieu Cho hai o th g1 = (V1, E1, 1, 1, LV , LE ) va g2 = (V2, E2, 2, 2, LV , LE ) o th con chung nh ngha nh o th g = (V , E, , , LV , LE ) nh la o th con ong dang ton tai t g1 en g ro nh t g2 en g. Mot o th con chung g cua g1 va g2 c goi la o th con chung toi thieu, neu khong ton tai o th con chung cua g1 va g2 nhng nut t hn so vi g. g . nh ngha 7: Hieu chnh loi trong o th ghep Cho vao g1 = (V1, E1 , 1 , 1 , LV , LE ) va g2 = (V2 , E2 , 2 , 2 , LV , LE ) la nhng o th. Hieu chnh loi trong o th ghep 1(ecgm) t g1 en g2 la mot ham song anh : V1 V2, V1 V1 va V2 V2. Nut uV1 c cho la thay the b nut vV2 neu f (u) = v . Neu 1(u) = 2 (f(u)) e s thay the c goi la phep the ong nhat. Cach khac no c goi la phep the khong ong nhat. Hn na bat ky nut nao t V 1 V1 c xoa t g1, va bat ky nut nao t V2V2 a vao
1

vi

HV: Nguyen Thai Nho MSHV: CH0401036

Hieu chnh loi trong o th ghep

Trang 9

H CNTT Tp HCM Seminar C s Tri Thc g2 di f . Tiep theo g1 va g2 bieu th nhng o th con cua g1 va g2 c em lai bi nhng tap hp V1 va V2, tng ng. Anh xa f trc tiep tac ong tren moi nut g1 va g2.V du Nhng nut c thay the, xoa , hay them vao, nh mo ta tren. ong thi anh xa f gian tiep tac ong tren cac canh

h . nh ngha 8: Gia tr cua mot o th so sanh hieu chnh loi Gia tr cua mot ecgm f : V1 V2 t mot o th g1 = (V1,E1,1,1,LV,LE) ti mot o th g2 = (V2,E2,2,2,LV,LE) c cho bi

c( s) =

V 1V 1 V1 ces (e) + e ced (e) + e cELi (e) eE s E t Ed

u u

ns

(u ) + c( s ) =

c (u ) + c (u ) +
nd u

V 2 V 2

nd

Trong o: cns(u) la gia tr cua viec thay the iem u V1 bang f(u) V2, cnd(u) la gia tr cua viec xoa iem u V1 V1 t g1, cni(u) la gia tr cua viec chen iem u V2 V2 trong g2, ces(e) la gia tr cua viec the canh e, ced(e) la gia tr cua viec xoa canh e, cei(e) la gia tr cua viec chen them canh e, va Es, Ed, va Ei la viec at nhng canh o bang viec thay the, xoa, va chen them, tng ng. Tat ca nhng so o eu la nhng so thc va khong am. HV: Nguyen Thai Nho MSHV: CH0401036 Trang 10

H CNTT Tp HCM Seminar C s Tri Thc Chu y nhng tap hp Es, Ed va Ei c bao ham bi anh xa f. Mot gia tr ac biet c at cho cns, cnd, , cei phu hp vi nh ngha tren c goi la mot ham gia tr. i . nh ngha 9: Toi u hieu chnh loi o th so sanh / khoang cach hieu chnh Gia s f la mot ecgm t o th g1 en mot o th g2 di mot ham gia tr ac biet. Chung ta goi f la mot ecgm toi u neu o khong ton tai ecgm khac f t g1 en g2 vi c(f) < c(f). Gia tr cua mot ecgm toi u t mot o th g1 en mot o th g2 c goi la khoang cach hieu chnh cua g1 va g2, va c bieu th bi d(g1,g2). Chu y rang moi ecgm ham cha mot chuoi cac thao tac chnh sa, th du nh chen, xoa, thay the. oc cho bi cong thc sau:
( g1 , g 2 ) = 1
mcs( g1 , g 2 ) max( g1 , g 2 )

ac biet, ieu nay co ngha (g1,g2) la mot thc o. Hn na, viec gia thiet mot lp nhat nh cua nhng ham gia tr cho hieu chnh o th co the thay c khoang cach tng oi vi khoang cach hieu chnh o th

II.2 GIAI THUAT TM KIEM NHANH CAY

Muc ch cua phan nay la loc c s d lieu cua o th da tren vector at trng va khai thac nhng d lieu cua cac vector at trng nay bang phng phap tm kiem nhanh cay. Phng phap tm kiem nhanh cay la phng phap phan loai hu dung cho nhng phan tch bang may cac tap mau huan luyen. Phan nay trnh bay co ong lai ly thuyet phng phap HV: Nguyen Thai Nho MSHV: CH0401036 Trang 11

H CNTT Tp HCM Seminar C s Tri Thc tm kiem nhanh cay, Phan tiep theo se trnh bay ve phng phap phan loai nhanh cay. Trnh bay nhng kien thc c ban ve phng phap suy dien va phan loai cua phng phap nhanh cay. Cac phng phap tm kiem nhanh cay da tren nhng tieu chuan phan tach va trnh bay cach suy dien m rong cho tap d lieu ln hn. Thong thng phng phap tm kiem nhanh cay bao gom hai bc c ban: Suy dien nhanh cay Phan loai

II.2.2 Phan loai bang Phng phap tm kiem nhanh cay: Chc nang cua phng phap phan loai tm kiem nhanh cay thong thng co the chia thanh hai bc: suy dien nhanh cay( phan tch d lieu) va phan loai cac mau khong xac nh. Trong bc chuan b, cau truc cay c suy dien da tren tap mau huan luyen. T cay nay, cac mau khong xac nh se c phan loai. Phan nay mo ta tong quat hai bc tren. a . Phep suy dien nhanh cay tong quat:
1. function suydien ( Nut v , Tap T ) { # Trong T , moi at trng hp le fi co trng, # Do o T co the chia thanh nfi tap con theo fi co the tm at trng chia s # T dc chia thanh nfbest tap con da tren ac trng tot nhat fbest va phep # suy dien c lap lai cho tng nut 2. If (nfbest > 0) then 3. 4. Tao nfbest c1, . . . , cnfbest of v Dung fbest chia T thanh T1, . . . , Tnfbest # tot nhat fbest da tren T va chuan chia nfi gia tr at

HV: Nguyen Thai Nho MSHV: CH0401036

Trang 12

H CNTT Tp HCM
5. 6. 7. 8. fi 9. } done For i = 1 to nfbest do suydien ( ci ,Ti )

Seminar C s Tri Thc

b . Phan loai: Nh a noi, phng phap phan loai nhanh cay dung e phan loai cac mau khong xac nh nhan lp. Nhng mau nay c nh tnh bi vector at trng tng ng vi no trong tap mau. Trong bc phan loai, cay quyet nh c tuan t xet theo hang ngang theo cac nhanh cay tng ng vi gia tr at trng cua vector mau au vao. Sau qua trnh nay, mau au vao c gan nhan lp co so lan lap lai cao nhat tren cac nut la.

II.3 Chuan tach:

II.3.1 Chuan li ch: Theo chuan C4.5, tap con c thiet lap da tren tieu chuan li ch ly thuyet. Co ngha la tai moi nut tren cay quyet nh, tap d lieu T c chia thanh cac tap con Ti da tren at trng toi ai thong tin li ch. oi vi mot mau trong tap T, xac suat mau thuoc lp c co the c c lng nh sau:

S dung xac suat cua tat ca cac lp c1ck thong tin cua tap d lieu c c lng bi hang so Entropy:
E (T ) = P (ci )ldP (ci ) (3.2)
i =1 k

Neu at trng f c chon va tap d lieu c chia thanh cac tap con theo tat ca cac gia tr co the cua T, hang so Entropy cua phep tach co the c the hien bang HV: Nguyen Thai Nho MSHV: CH0401036 Trang 13

H CNTT Tp HCM Seminar C s Tri Thc tong trong cua hang so Entropy cua cac tap con T 1Tn nh sau:
B(T , f ) =
i =1 n

Ti E (Ti ) (3.3) T

Trong phng trnh (3.3) f ch at trng c chon va n la so lng cac gia tr co the cua at trng o. Trong cua Hang so Entropy E(Ti) cua cac tap con Ti c lng da tren so lng mau trong Ti(|Ti|) trong moi quan he vi so lng mau trong T. Hang so Entropy B cua phep chia la ln khi va ch khi tap con Ti cha nhng mau cua cac tap khac nhau. Theo phat bieu nay, vi moi at trng f thong tin co c bi phep chia T theo nhng gia tr ra co the c tnh nh sau:
G (T , f ) = E (T ) B (T , f ) (3.4)

Chuan li ch c thiet ke da tren y tng la phep suy dien nhanh cay co the b dng khi thong tin li ch thap hn mot ngng gia tr nhat nh. Hang so Entropy cua mot tap cac o th vi nhng xac suat cho trc c nh ngha nh sau
E (T ) = Pi ld ( pi )
i =1 n

Vi pi la xac suat cua oi tng ci, do o pi = P(ci)2 . Ap dung s n gian hoa trnh bay tren gia s tat ca o th la tng ng nhau. E co the viet thanh:
n 1 1 1 E (T ) = ld ( ) = ld ( ) = ld (n) n n i =1 n

Cam tnh, hang so Entropy c lng co bao nhieu quyet nh xay ra cho en khi mot o th c xac nh. Hang so Entropy cang ln, so quyet nh cang nhieu va do o cay quyet nh cang dai. T goc nhn cua nut cha, hang so Entropy cua cac nut con can phai c toi thieu. Do o, chuan chia la tong cac hang so Entropy cua tap cac nut con. Vi tap Ti, cua nut con si ai lng nay cho nh sau: HV: Nguyen Thai Nho MSHV: CH0401036 Trang 14

H CNTT Tp HCM
Esum (T1...M ) =
i =1 M

Seminar C s Tri Thc

Ti E (Ti ) T

Vi |Ti| la bac ln cua tap oi tng tai nut con si, E(Ti) la hang so Entropy cua tap nay. M la so lng cac nut con cua nut cha. Ro rang rang chuan li ch va trong hang so Entropy co anh hng ln en nhng ac iem san sinh ra cac tap con Ti cua tap ban au T Nhn chung, nhng cach nh vay khong c mong i trong phep phan loai v no se lam bo phan loai ch phu hp vi d lieu huan luyen do o ngan khong cho phan loai nhng d lieu cha biet. Noi mot cach n gian, phan loai cac mau cha biet la khong the. e khac phuc han che nay, ngi ta a ra chuan ty so li ch. II.3.2 Chuan ty so li ch: Han che cua chuan li ch co the khac phuc c bang phep bnh thng hoa, hieu chnh gia tr li ch cua nhng tr ra bang chnh kch thc cua nhng tr nay. Han che cua chuan li ch G(T,f) la no a bo qua kch thc cua cac tap con Ti cua T. Do o, nhng phep chia khong mong muon co the tranh c neu hang so Entropy cua kch thc cua cac tap con c tch hp vao trong chuan chia. Thong tin cua phep chia co the c tnh tng t nh thong tin lp(xem pt (3.2)):
S (T , f ) =
i =1 n

Ti Ti ld T T

(3.5)

Da vao S(T,f) co the nh ngha chuan ty so li ch. Ty so li ch chnh la chuan li ch G(T,f) c e cap tren, c bnh thng hoa bi thong tin cua phep chia cua tap d lieu S(T,f):
G ' (T , f ) = G (T , f ) (3.6) S (T , f )

HV: Nguyen Thai Nho MSHV: CH0401036

Trang 15

H CNTT Tp HCM Seminar C s Tri Thc S dung chuan ty so li ch, nhng han che cua chuan li ch co the tranh c. Do o, cay quyet nh tao ra t chuan li ch se can bang hn va la bo phan loai on nh hn.

II.4 Phep m rong Rainforest cho tap d lieu ln:

Hau het cac phep suy dien cay eu rat ton bo nh, v tap d lieu phai c lu trong bo nh trong qua trnh suy dien cay. Mac du bo nh ngay cang c m rong, tuy nhien, cac ng dung hien nay eu co tap d lieu ln hn rat nhieu so vi bo nh chnh. Co vai nghien cu giai quyet van e nay. Nhng cach thong thng la phan manh d lieu e cac tap con va vi bo nh. Phan manh cac vector at trng hay hieu chnh mau cua tap d lieu tai moi nut cay. Phan manh tap d lieu thanh cac tap con trc khi thc hien phep suy dien se lam cho ket qua phan loai xau i. Phng phap phan manh ngc lai van am bao toan tap d lieu va vi bo nh tai mot thi iem. Hieu chnh mau cua tap d lieu tai moi diem tren cay cung gia thuyet mau cua toan tap tai nut goc se san sinh ra mot mau hieu qua trong qua trnh suy dien. Nghien cu phan tch nhng van e nay va e ngh cach giai quyet c thc hien bi Gehrke et. al. trong Rainforest. Rainforest mo ta sn nhng ng dung trong hau het cac phep suy dien nhanh cay s dung ngay nay vi tap d lieu ln. Phep suy dien cay m rong:
1. Function suydien (Nut v , Tap T ) { 2. # trong T , moi at trng hp le fi co nfi gia tr at trng, 3. # do o T co the chia thanh nfi tap con theo fi 4. Moi at trng fi hp le trong T do 5. 7. evaluateSplit (AVC-Set of fi ,T ) done 6. If ( isBetterFeature (fi ) ) then fbest = fi

HV: Nguyen Thai Nho MSHV: CH0401036

Trang 16

H CNTT Tp HCM
9. nhat fbest

Seminar C s Tri Thc

# T dc chia thanh nfbest tap con da tren dac trng tot

10. # va phep suy dien c lap lai cho tng nut 11. If (nfbest > 0) then 12. tao nfbest con c1, . . . , cn f best of v 13. Dung fbest chia T thanh T1, . . . , Tn f best 14. for i = 1 to nfbest do 15. 16. done 17. fi 18 } suydien (ci ,Ti )

HV: Nguyen Thai Nho MSHV: CH0401036

Trang 17

H CNTT Tp HCM

Seminar C s Tri Thc

Chng III

NOI DUNG NGHIEN CU VA KET QUA

III.1 S DUNG O TH D LIEU CO CHON LOC NHNG VECTORS AT TRNG
S chon loc o th c s d lieu da vao cac vector at trng c e xng trong Seminar nay c thiet ke vi mot dang thc thch ng nh a cho (ong dang o th, s thch ng ong dang o th hay loi o th con). No c phat trien cua s chon loc vector at trng, ngoai ra no con c xem nh la mot ng c vien khong hoan thanh dang thc thch hp khi c so sanh ti mot o th ban au a cho. Tat nhien, o co s ton tai s a dang gan nh loc. Cach trc tiep nhat e thc hien mot bo loc tuan t ,so sanh o th ban au vi moi o th trong c s d lieu s dung giai thuat thch ng o th a cho. Tuy nhien, t s thch ng o th noi chung tnh toan rat cao( nhiem vu cua viec phu hp vi hai o th thong thng yeu cau thi gian va nhng tai nguyen cua bo nh, cua nut va nhng canh co lien quan vi nhau) nh la sc manh cua ngi loc nhng lai khong phu hop vi nhng c s d lieu ln hn. Cach tiep can c e ra trong Seminar nay c da vao at trng cua nhng vector F c rut ra t databasegraphs t nhng mau ban au. Y tng se tranh mac theo nhieu tuan t, u ban lnh bang viec so sanh nhng vector at trng c rut t nhng o th. C s da tren hieu qua cua s so sanh, nhng o th them hay loai bo t s ong cng o la ket qua cua giai thuat loc.

HV: Nguyen Thai Nho MSHV: CH0401036

Trang 18

H CNTT Tp HCM Seminar C s Tri Thc Chng trnh nay cho khai niem cua nhng at trng o th va nhng vector at trng o th co the c s dung nh the nao, lam quen vi nhng o th so sanh dang thc thch ng khac nhau. Da vao s so sanh vector at trng, loc tuan t rat n gian c gii thieu. III.1.1 Nhng at trng o th Muc tieu cua Seminar nay c c lng nhng he thong loc c s d lieu o th da vao ky thuat khai mo d lieu, s dng phng phap cay quyet nh. ac biet chu y se phat trien va c lng nhng he thong cho ba dang thc thch ng o th : ong dang o th ong dang o th con S thch ng dung sai o th

S giai quyet nhng phng phap cay phan loai nhng oi tng (trong nhng trng hp o th) c da vao at trng vector s trnh bay cua nhng oi tng. T ay, trong s nghien cu nay, nhng o th can c ai dien cho nh nhng vector at trng. T nhng vector c s dung cho muc ch cua s loc c s d lieu, nhng tnh nang phai phu hp hai yeu cau sau: S trch ra nhanh t nhng o th mau Net noi bat cao

Nh a noi trc o, s chon loc cua nhng at trng o th c han che bi nhng s gii han anh gia t bac phc tap tnh toan. Da vao nhng han che nay, theo kieu cua nhng at trng (hoac cac at tnh) c nh ngha trong Seminar nay: f1(g) : So nh trong o th g f5(n,g) : So nh bac trong n Trang 19

HV: Nguyen Thai Nho MSHV: CH0401036

H CNTT Tp HCM

Seminar C s Tri Thc trong bac th g

f2(a,g) : So nh nhan a trong f6(n,g) : So nh bac ngoai n o th g trong bac th g 3 f (a,g) : Slng canh vao nh f7(n,a,g) : So nh bac trong n nhan a trong th g co nhan a trong g 4 f (a,g) : Slng canh ra cua f8(n,a,g) : So nh bac ngoai nh nhan a trong th g n cua nhan a trong g

Hnh 5.1 III.1.2 Thuat toan loc Vector at trng

Ham khoang cach c thuc ay da vao o th con chung toi ai cua hai o th. Nh vay so lng at trng f2(a,g) phu thuoc vao kch thc cua LV. Da vao at trng nay e anh gia ve kch thc toi ai cua mcs cua hai o th g1, g2. Hn na gia thiet, khong co s mat mat cua tnh tong quat, tat ca nhng nut tren o th hoan toan c gan nhan. So lng nut | mcs(g1,g2) | trong o th con chung toi ai cua g1, g2 c cho bi

mcs ( g1 , g 2 )

aLV

(a,mcs ( g1 , g 2 )) 5.2

HV: Nguyen Thai Nho MSHV: CH0401036

Trang 20

H CNTT Tp HCM Seminar C s Tri Thc III.1.3 Thuat toan locVector at trng m rong

III.2 CAY QUYET NH CUA O TH LOC C S D LIEU

Muc ch cua cong viec nay nham giam bt kch thc cua mot c s d lieu o th oi vi mot mau o th. Nhieu moi lien he ve cac ky thuat khac nhau c a ra nham giam bt s phc tap cho viec so sanh o th trong trng hp nhng c s d lieu ln. Trong Seminar nay, mot giai thuat loc c e xng. Muc ch e loai tr mot so ln o th trong c s d lieu bi mot so cach th nhanh s dung duy nhat cac at trng n gian cua o th. III.2.1 Loc Cay Quyet nh Nh a c trnh bay, nhng cay quyet nh giam sat viec huan luyen cac phng phap ky thuat . Ap dung nhng phng phap cay quyet nh vao viec loc c s d lieu o th thong qua cac vector at trng, c s d lieu o th c xem xet huan luyen nh cho giai thuat cay quyet nh. Trong c s d lieu, ban than nhng o th ai dien bi nhng vector at trng. Giai thuat cay quyet nh em lai thanh cong tren nhng vector at trng, mot lp c phan bo can gan ti nhng vector thuoc tnh ai dien cho nhng o th. Trong cong viec nay, viec huan luyen mau ai dien cho mot lp c phan bo. Lp cua mot mau huan luyen la ong nhat vi the hien HV: Nguyen Thai Nho MSHV: CH0401036 Trang 21

H CNTT Tp HCM Seminar C s Tri Thc mau cua chnh no t ay c s d lieu cua n mau huan luyen o ton tai n lp trong tap huan luyen nh. Muc tieu cua s la chon nay la an nh s phan bo cac lp la ac biet la khong vt qua cay quyet nh. III.2.2 o th ong dang cay quyet nh Mot co mot cach tiep can n gian so vi cac vector at trng oi vi o th ong dang a c gii thieu. Van e chnh vi ieu nay, cach tiep can la o ton tai mot so ln at trng se c kiem tra. Phng phap c gii thieu trong muc co gang giam bt so lng cac at trng c kiem tra en mot tap con nho, da vao ky thuat cay quyet nh, c s d lieu o th c phan tch xac nh nhng at trng manh nhat tru t nhng oi tng c s d lieu. III.2.3 o th nhanh Mot cay quyet nh ai dien cho c s d lieu cua nhng mo hnh o th C c xay dng, ieu kien can thiet e a vao o th g ong dang vi o th mo hnh gi tat ca nhng at trng c lay t g co nhng gia tr ong nhat vi nhng at trng tng ng c rut t gi x ly nh sau. Trc tien, nhng at trng giong nhau c rut t nhng o th trong c s d lieu c rut t viec nhap lieu vao o th. Roi gia tr cua cac at trng c rut t viec nhap lieu o th c dung cho nhanh cay quyet nh

HV: Nguyen Thai Nho MSHV: CH0401036

Trang 22

H CNTT Tp HCM

Seminar C s Tri Thc

Ch co 2 van e xay ra. Van e au tien la nut la c hoan thanh. Trong ieu nay ket hp nhng o th vi nut la xay ra viec so sanh ti nhng o th nhap vao. Toan bo nhng o th nay c kiem tra lai tng ng vi nhap lieu o th cho o th ong dang s dung mot giai thuat theo quy c. Van e th hai la nut la khong hoan thanh. Trong trng hp nay khong co nhng o th trong c s d lieu no co the ang cau ti o th c nhap vao HV: Nguyen Thai Nho MSHV: CH0401036 Trang 23

H CNTT Tp HCM

Seminar C s Tri Thc

III.2.4 o th con ong dang cay quyet nh Nhn vao o th ong dang, ieu kien can thiet cho 2 o th g1 va g2 ang cau la no ong nhat nhng gia tr ac trng. Tuy nhien o th con ong dang, co moi tng quan khong n gian, danh sach cua nhng at trng c gii thieu co hai kieu at trng c ban: Nhng at trng khong cha ng cac thong tin tren cac bac cua cac nut trong o th {f 1, f2, f3, f4} Nhng at trng cha ng cac thong tin tren cac bac cua cac nut trong o th {f 5 , f6 , f7 , f8 } a . Nghien cu sieu o th: cac mau c nhap vao c can nhac ky lng e ang cau ti o th con trong nhng o th trong c s d lieu. b . Nghien cu o th con: c s d lieu cha ng nhng o th co kha nang ang cau ti o th con trong cac mau nhap vao. Trong nhng giai thch sau ay, tieu iem la tap hp trong trong tam th hai la cac mau nhap vao la o th con va c s d lieu o th la nhng o th con(nghien cu o th con). Tuy nhien, nghien cu o th con c lam mot cach tng t

HV: Nguyen Thai Nho MSHV: CH0401036

Trang 24

H CNTT Tp HCM Seminar C s Tri Thc Mot lan na viec phuc hoi lai phan trong tam c xac nh, phan cac d lieu co the c loc theo trong ca hai cach sau: c . Bang cach s dung o th ong dang cay quyet nh thay oi ng ngang cua giai thuat. d . e quyet nh cho cau truc mi cua cay quyet nh, s dung nhng mo hnh toan hoc c mo ta oan au tien. III.2.5 Gii thieu phan cay ong dang cua o th Viec loc da tren mieu ta cau truc cay c mieu ta yeu cau rang cac at trng cac vector at trng trong cac nh dang rieng le. Do o khong u e gii thieu giai thuat cua chnh no. Muc ch s dung lai o th ong dang va cay quyet nh. Y ngha cua cach tiep can nay la viec s dung lai o th ong dang, cay quyet nh phong theo giai thuat ng ngang v vay theo cung vi no la tat ca cac nut ke tha hp ly cua cac nut ben trong. So vi o th ong dang i qua no III.2.6 Cay o th ong dang ng ngang Cac ng ngang ong dang c ton tai en van e la tm trong phan di cua o th trong cac d lieu co the theo sau la cac ng ngang rat kho tien hanh a . Co nhieu giao iem chung b . Nhng tr so tnh chat khong xay ra trong phan d lieu co cung mau o th va phai can nhac ky trong khi cac ng ngang cua cay co the xay ra trong d lieu. V vay, oi vi cac ng ngang co hai trng hp co the xay ra. Neu cay quyet nh khong ton tai trong cac giao iem ben trong cua o th co gia tr cua tnh chat theo sau, HV: Nguyen Thai Nho MSHV: CH0401036 Trang 25

H CNTT Tp HCM Seminar C s Tri Thc cac ng ngang cua toan hoc phai di chuyen phan trc en cac giao iem nay va tat ca cac giao iem co s hien dien phan nho co tnh chat gia tr nho cua no. Mat khac, neu co phan ton tai ma khong co cac phan giao iem cua toan hoc phai theo sau tat ca cac giao iem ai dien cac tnh chat co phan gia tr nho. Neu khong co phan cac giao iem ton tai th cac ng ngang phai dng lai. III.2.7 Cay o th con ong dang Nhanh ngang Cay quyet nh dan xuat c mo ta tren co the c dung e khoi phuc nhng ng vien cua o th con ong dang kha d cua mot o th mau a cho trong cach sau ay. au tien, nhng at trng giong nhau c rut ra t c s d lieu o th va s dung em lai cay quyet nh c rut t o th au vao. Roi, giai thuat nhanh ngang i theo sau nhng nhanh cay ma co gia tr at trng bang nhng gia tr c rut t o th mau. Ch co 2 kha nang co the xay ra cua thu tuc nhanh ngang cay quyet nh. Kha nang au tien la mot nut la at c. Trong trng hp nay, nhng o th c lien quan en nut la la co the so sanh ti o th au vao. Toan bo nhng o th phai c kiem tra tr lai khi co o th au vao. III.2.8 Loc ket hp c thuc ay bi nhng khai niem c dung trong nhieu s ket hp cua ngi phan loai, mot cach tiep can th ba cho viec loc o th con co the dan xuat. Y tng cha khoa trong nhieu ket hp cua ngi phan loai la neu ngi phan loai C1 ang phan loai rat chnh xac nhng trng hp nhat nh trong khi ngi khac thc hien kem hn cho nhng trng hp nay. C1 co the cap bac vt ra ngoai nhng s HV: Nguyen Thai Nho MSHV: CH0401036 Trang 26

H CNTT Tp HCM Seminar C s Tri Thc yeu kem cua ngi phan loai khac. Ngc lai, nhng ngi phan loai khac co the sa cha s yeu kem cua C1 Chap nhan nguyen ly nay mot co the ket hp hai phng phap loc o th con trc o c gii thieu. Trong cach tiep can nay c sat nhap e thanh cong tuy nhien, nhng cay quyet nh ac biet can c kiem tra nhng at trng khac. Tai ni bat au cua cay cam ng, tap hp o th phan ln tng t trong nhng nut cay, ca hai c gii thieu nhng cach tiep can co kha nang nhan biet nhng at trng nh nhau hay t nhat tng t nhieu at trng manh nhat cho nhng nut. III.2.9 Nhng loi co the bo qua cua cay quyet nh Trong muc nay no c giai thch khai niem cua s so sanh vector at trng cho viec c lng o th con chung toi ai co the c s dung nh the nao trong s ket hp vi nhng cay quyet nh Nhng phng phap cay quyet nh cam ng tng t vi nhng phng phap trc ay cho nhng cay ong dang o th. Nhanh ngang qua cay quyet nh tuy nhien can c sa oi sao cho vai nhanh c i theo sau trung nhau trong khi viec theo doi co the ch nh cung nh gia tr at trng khong the ch nh. Da vao nhng phng phap an nh nay va cac phng trnh tren. Mot c lng tren kch thc toi ai cua o th con chung toi ai kha d. co the xay dng mot giai thuat nhanh ngang quyet nh e loc ra tat ca nhng o th trong c s d lieu vi mot khoang cach ln hn so vi ngng a cho o th

HV: Nguyen Thai Nho MSHV: CH0401036

Trang 27

H CNTT Tp HCM

Seminar C s Tri Thc

e cho cay quyet nh tr nen hu chnh la s thch ng o th error-tolerant theo sau III.2.10 Cay quyet nh dan xuat error-tolerant Thu tuc cay dan xuat tng t oi vi thu tuc cam ng cho nhng cay o th ong dang. Ch co hai s khac nhau se c xem xet khi gay ra error-tolerant decision trees. Cai sai au tien la cho loi error-tolerant decision trees, no ac biet cho moi o th co kch thc ngang nhau se lam cho no de dang hn cho nhanh ngang giai thuat e theo doi nhng nut con lai se c gan cho nhng o th c s d lieu. T ay, at trng au tien c kiem tra trong cau truc error-tolerant cay quyet nh la at trng
f1

so lng nhng

nut trong mot o th. Th hai, trong khi ma nhng cay ong danh o th khong co s han che c lam tren nhng at trng se c s dung, v error-tolerant decision trees ch co duy nhat 1 kieu
f
2

(a, g)

co the c ap dung,
g

(a, g)

bieu th so lng nh trong o th

vi nhan. Cau truc

cay quyet nh van c s dung bi kieu nhanh ngang nay va se c tham chieu ti nh cau truc cay n gian t gi tr i Trong thi gian i qua nhanh ngang, mot mau au vao co the cha ng thong tin bo sung trong nhng at trng o th khong phai san co trong c s d lieu o th. T ay HV: Nguyen Thai Nho MSHV: CH0401036 Trang 28

H CNTT Tp HCM Seminar C s Tri Thc nhng at trng khong co kha nang phan biet nhng o th cho c s d lieu co the hu ch loc nhng mau khong c nhan biet cho o th. e tnh toan cho trng hp nay, mot cau truc cay m rong c gii thieu. Sau cam ng cua cau truc cay n gian nh c mo ta tren, nhng at trng con lai la tng ng du no khong cha ng bat ky thong tin nao a ra ngoai cua nhng c s d lieu. Muc ch la nhng at trng nay se c kiem tra trong thi gian nhanh ngang qua va thong tin toi ai a cho trong c s d lieu va o th mau c lng. Cau truc cay nay se c tham chieu ti nh cau truc cay m rong. Mot s minh hoa cua cau truc cay rong ln va c n gian hoa. Chu y rang ca hai cay co at trng cau tao
f1

c kiem tra au tien e am bao nhng o th co kch thc nh nau trong moi cay. Cung chu y rang cau truc cay m rong, nhng at trng bo sung c kiem tra dan en nhng nut cay bo sung (c anh dau o) III.2.11 Decision Tree Traversal Nhng cay quyet ng tng ng nh c mo ta tren co the khong c s dung e khoi phuc nhng ng c vien o th co the khac nhieu hn so vi mot khoang cach o th la ngng xac nh t au a vao mau o th. Gia thiet moi o th trong c s d lieu bang nhau ve size 1 Hn na, gia thuyet C kch thc oi hoi la mcs nh mo ta trong muc 5.4 nh ta c biet, y tng chung se gi so lng nhng nut gan ti co the c mcs. Trong thi gian nhanh ngang qua, kiem tra cac nut cay hien co ai dien cho so nut c gan vi mot mcs kha d. Tng t, moi nhanh c i theo sau ai dien cho mot mcs theo gia thuyet gia nhng o th c s d lieu va mau au vao. e lam ieu nay, three counter can:

HV: Nguyen Thai Nho MSHV: CH0401036

Trang 29

H CNTT Tp HCM

Seminar C s Tri Thc

nmcs: So lng nhng nut c gan o vi mot mcs kha d trong nhanh hien thi. Counter em nay c khi tao vi ch so 0 ( viec bat a nhanh ngang qua cay, khong co nhng nut gan oi vi mcs)

ndr: So lng nhng nut gan oi vi mot mcs kha d trong nhanh hien thi. Counter c khi tao vi ch so 0( viec bat au nhanh cay ngang, khong co nhng nut c gan oi vi mcs)

nsr : So lng nhng nut con lai trong o th mau trong nhanh hien thi. Nhng counter c khi tao vi kch thc cua o th mau, tng t ti ndr .

au tien moi at trng kieu xac nh c rut t o th au vao. Giai thuat xac nh c rut t o th au vao. Giai thuat nhanh ngang di theo sau moi nhanh cay co the trung nhau

HV: Nguyen Thai Nho MSHV: CH0401036

Trang 30

H CNTT Tp HCM

Seminar C s Tri Thc

Trong thi gian i qua cua mot nhanh, nhng gia tr at trng c so sanh gia c s d lieu va mau au vao. Gia thuyet at trng c kiem tra mot nhanh ac biet c bieu th bi f (a, g) Mau au vao c bieu th bi gs va tng t. Nhanh cua tap hp o th bi Gdb (T o khi ma f (a, Gdb ) ai dien cho gia tr cua nhng o th c s d lieu). Roi nhng counter c cap nhat trong cach sau ay
f s db nmcs = nmcs + min (a,g ),f (a, G )
db ndr= ndr f (a,G ) s nsr= nsr f (a,g )

f (a, gs ))

ai dien cho gia tr at trng cua mau trong

Hnh 6.8 minh hoa mot bc nhanh ngang va nhng s an nh counter tng ng. at trng c kiem tra tren minh hoa nhanh la so lng nhng nut c gan mot nhan A. Mau au vao cha ng hai nut nh nhau trong khi ma nhng o th c s d lieu cha ng ba nut. o la viec xoa e nhn thay hai nut co the c gan oi vi mcs co the at c, t ay nmcs co the la o ln bang hai. ong thi, ba nut a c c lng cho nhng o th c s d lieu va co the c loai bo t nhng nut con lai e c gan. Tng t, hai nut co the c loai bo t nhng nut con lai cua o th mau. Thu tuc nay la mot cach e quy c tiep tuc cho en mot trong so ket thuc sau ay vi nhng ieu kien : HV: Nguyen Thai Nho MSHV: CH0401036 Trang 31

H CNTT Tp HCM Seminar C s Tri Thc failure: (nmcs + ndr < c ) (nmcs + nsr < c ) ( nhng nut khong u co the c gan oi vi mot mcs kha d ) success: nmcs c ( u nut a c gan ) success: cmot nut la at en va khong co bat ky nut nao trong so nhng ieu kien ket thuc khac xuat hien. Moi nut c at en vi mot ieu kien iem tan cung thanh cong c gan o vi mot tap ket qua. Nhng o th c cha ng trong nhng nut nay la nhng ng vir6n co the co va nh mot he qua can c kiem tra vi mot o th tieu chuan khoang cach. III.2.12 Conclusions Trong chng nay, ong gop chnh cua Seminar nay, ap dung nhng phng phap quyet nh vao viec loc vector at trng, a c gii thieu. No a cho thay o ton tai mot so s khac nhau c ban se c sem xet khi s dung nhng phng phap quyet nh cho viec loc c s d lieu thay v sap xep viec phan loai (muc 6.1). Da vao nhng ieu kien can thiet ve khai niem c ban cua viec loc c s d lieu da vao cac at trng cua vector c thch nghi e cho phep ng dung phng phap ky thuat. Nhng cach tiep can viec loc cay quyet nh khac nhau cho ba dang thch ng o th a c gii thieu. a . ang cau o th - Graph isomorphism (phan 6.2) b . ang cau o th con -Subgraph isomorphism (phan 6.3) c . o th khoang dung loi - Error-tolerant graph matching No c ch ra rang o th ong dang cho cay quyet nh c m rong. o th con ong dang co vai van e a HV: Nguyen Thai Nho MSHV: CH0401036 Trang 32

H CNTT Tp HCM Seminar C s Tri Thc c xac nh vai gi en vai xach tiep can e giai quyet van e. Vi Error-tolerant decision trees, co hai cach tiep can co dan xuat tiep tuc ac c s trnh bay khac Trong phan tiep theo, nhng phng phap dan xuat bang th nghiem c c lng. au tien, nhng cach tiep can loc vector at trng cha c th nghiem se c c lng . Roi, li ch at c bi nhng ng dung cua nhng phng phap cay quyet nh c minh hoa

HV: Nguyen Thai Nho MSHV: CH0401036

Trang 33

H CNTT Tp HCM

Seminar C s Tri Thc

Chng IV

KET QUA TH NGHIEM

IV.1 TAP D LIEU O TH
e kiem tra nhng phng phap loc, mot s a dang cua nhng c s d lieu cua nhng kieu o th khac nhau a tao ra hay tap hp nhng cach giai quyet cua cong viec. Noi chung, nhng kieu o th a hoc co the c phan loai trong hai lp khac nhau: a . o th phat sinh (nhng o th nhan tao, th du bi mot may phat o th), b . Nhng o th a c khai can (nhng o th c rut t cau truc d lieu thc te, nhng o th ke lien vung). Lp cua nhng o th phat sinh gom co nhng o th c tao ra bi may phat o th. Nhng o th trong lp nay khong da vao d lieu cau truc khac. ung hn, chung c tao ra da vao nhng tham so ngi dung a cho. Nhng kieu v du cua o th nay la nhng o th ngau nhien hoac o th hoa tr giap gii. Nhng o th khai can la nhng o th rut t cau truc d lieu hien hu, nh nhng anh so hoac nhng tai lieu. Chu y rang chnh cau truc d lieu nam ben di co the c tao ra bi mot may phat nao o (mot hnh anh dan xuat ra bi mot cong cu da vao nhng ng phap nh nhng hnh anh Pol-Gen s dung trong Seminar nay) hoac no co the la mot anh chup nhanh thc te (mot hnh anh c chup bi camera). Tat nhien, phu thuoc vao cau truc d lieu va oi hoi ng dung, nhieu kieu o th co the c rut ra. HV: Nguyen Thai Nho MSHV: CH0401036 Trang 34

H CNTT Tp HCM

Seminar C s Tri Thc

Hnh 7.1: Tap hp d lieu o th Tong quan cua so lieu o th s dung tong Seminar nay a c cho trong hnh 7.1. Trong muc tiep theo, mot li gii thieu ngan gon ti nhng kieu o th phat sinh a cho. Sau o, trong muc 7.2, nhieu o th da vao c s d lieu thc te c trnh bay.

IV.2 C S D LIEU O TH LOC NGHIE N CU THC HI EN

IV.2.1 S Loc Vector at trng Nhng ket luan Trong chng nay s lc vect c tnh a c hc. u tien , S phoi hp. (cho) s lc c s d liu (ca) s chn lc (ca) nhng c tnh c to built k lng. No a c ch ra rng mi c tnh t c mt cao saliency, nh vy co kh nng ng nht hoa (nhn ra) hay nhng s lng nhng th l rieng bit. Hn na, No co th c nhn thy ma khi s dng trong s kt hp, . ca saliency a co th thm ch ang gia tng. Khong k s phoi hp (ca) nhng kiu c tnh, s lc vect c tnh (cho) tt c.

HV: Nguyen Thai Nho MSHV: CH0401036

Trang 35

H CNTT Tp HCM

Seminar C s Tri Thc

S lng nhng s th Trung bnh lm cho mt li , nhng th ngu nhien s dng li.s anh gia vect c tnh error-tolerant mt khong cach (ca) Mt cach ang
d

= 0.1 va

= 0.2

xut nhng dng thc

thch ng a c loc k lng. k c ci thin nu nhng vect c tnh c phan tch bng vic ap dung k thut khai thac d liu. Trong phn sau c nh gi v ng dng k thut khai m d liu, kt hp vi vector at trng c lam ni bt.

IV.3 LOC BANG CAY QUYET NH

Trong qua trnh sang loc c s d lieu co the c thc hien rat tot bang cach so sanh cac vector ac trng. Tuy nhien phan a c trnh bay tren cung ch ra rang, qua trnh sang loc nay co the at c ket qua tot hn na neu cac vector ac trng c phan tch bang nhng ky thuat trong khai khoang d lieu (Data mining). Phan nay tap trung tm HV: Nguyen Thai Nho MSHV: CH0401036 Trang 36

H CNTT Tp HCM Seminar C s Tri Thc hieu viec ap dung nhng phng phap suy dien bang cay quyet nh cho viec tien x ly cac vector ac trng c trch ra trc o. Trong phan sau, chung ta phan tch bai toan oi chieu ong dang o th. Va cac ong dang o th con se c trnh bay sau o. Sau cung, ta thc hien phep so sanh cac vector ac trng co chap nhan loi. Muc 10.3 se trnh bay cac ket qua at c. Phng phap loc bang o th c thc hien tren cung dang o th vi cac phng loc vector ac trng. Trong suot qua trnh thc hien th nghiem, chung ta tap trung phan tch 2 kha canh khac nhau cua 1 bo loc cay quyet nh, moi kha canh se c phan tch bang cac tap o th khac nhau. Tap o th au tien la nhng c s d lieu o th giong vi tap o th a c trnh bay trc ay trong phan anh gia cac vector ac trng. o la: cac o th ngau nhien, bounded valence, va cac dang o th li (mesh graph). Moi c s d lieu bao gom 1000 o th khac nhau. Moi o th c cho la ch ong dang vi chnh no (isomorphic). Tap d lieu nay c dung e phan tch bac ln cua 1 cum (cum size) va so trac nghiem (tests) c thc hien trong suot qua trnh do tm tren cay theo 2 tieu ch phan chia la t le gain va gia tr hang so Entropy. Tap d lieu th hai bao gom nhng o th c mo ta (ban ve viec anh s thch hp cua cac loai ac trng). Tap d lieu nay se uc dung e trac nghiem kha nang cua cac phng phap loc tren mot tap c s d lieu ln hn trong khi van am bao c cac ket qua tot cho: (1) cac trac nghiem (test made) va (2) kch thc cua tap li giai. Trong nhng th nghiem au tien, kch thc cum va so trac nghiem c o da tren c s d lieu o th va chien lc suy dien c chon trc o. e co the anh gia bac hieu qua cua phng phap e ra, ta xay dng cac cay quyet nh HV: Nguyen Thai Nho MSHV: CH0401036 Trang 37

H CNTT Tp HCM Seminar C s Tri Thc t nhng c s d lieu o th va moi tieu chuan phan chia (split-criterion) (co 2 tieu ch cho viec phan chia o la: t le gain va gia tr hang so Entropy). Sau o, mot vai o th c lay ra mot cach ngau nhien t tap c s d lieu, vector ac trng cua chung c rut ra va cay quyet nh tng ng vi o th o c s dung. Gia tr cua kch thc tap ng vien (cung co ngha la kch thc cum) va so trac nghiem c tao ra (test made) se c tnh sau o. Cac ket qua c minh hoa tren Tnh hieu qua cua bo loc ong dang o th khong ch phu thuoc vao kch thc tap ket qua, ma con phu thuoc vao so trac nghiem c tao ra e at c nhng ket qua nay. ieu nay nam trong d oan, bi v muc tieu cua hang so Entropy la u tien nhng ac trng ma co khuynh hng tao ra nhieu nh con (successor node) tren cay quyet nh. Trong khi o, t le gain co gang chuan hoa hieu ng o (e at c s tong quat nhat, yeu to can thiet cho bai toan phan loai). Hieu ng nay tr nen hien nhien hn khi ta phan tch s van hanh cua phng phap trong trng hp xau . Tuy nhien, neu ng t quan iem cua viec xay dng bo loc c s d lieu, ta se bo qua s khac nhau ve so trac nghiem c tao ra.

HV: Nguyen Thai Nho MSHV: CH0401036

Trang 38

H CNTT Tp HCM

Seminar C s Tri Thc

Kch thc cum cua cac cay quyet nh c xay dng theo 2 tieu chuan: t le gain va ai lng hang so Entropy

HV: Nguyen Thai Nho MSHV: CH0401036

Trang 39

H CNTT Tp HCM

Seminar C s Tri Thc

Chng V

KET LUAN VA KIEN NGH

V.1 Nhng ket luan
Seminar nay a ra van e lam the nao e x ly nhng c s d lieu cua nhng o th tng trng cho cau truc d lieu. Nhng o th va o th ghep la phng phap pho bien trong viec nhan dang. Tuy nhien, noi chung o th ghep cung la phng phap tnh toan ton kem. Ngoai ra viec so sanh tng cap o th, mau nghep au vao ti toan bo c s d lieu a c quan tam hn trong nhng nam gan ay. Khi chia c s d lieu cua nhng o th, hn na kch thc cua c s d lieu tang len cung vi oi hoi viec tnh toan len toan bo cac cach ghep. Vai phng phap a c e xng trong tai lieu e giai quyet he so nay, tuy vay hau het cac phng phap nay khong thch hp cho cac c s d lieu ln. Trong Seminar nay, cau truc loc c s d lieu co kha nang giai quyet nhng c s d lieu ln cua nhng o th a c e cap. Trong viec loc c s d lieu viec phuc hoi lai c s d lieu tuy thuoc vao hai bc: V.1.1 Loc c s d lieu Trong bc au tien, toan boviec loc c s d lieu da vao mot dang ghep a cho va mot o th au vao a cho. Bc loc giam bt kch thc ban au cua c s d lieu cho phep ch co duy nhat 1 tap con cua toan bo c s d lieu e x ly trong bc ghep chnh xac.

HV: Nguyen Thai Nho MSHV: CH0401036

Trang 40

H CNTT Tp HCM Seminar C s Tri Thc V.1.2 Ghep chnh xac da tren ket qua loc Tap con c tra lai bi bc loc sau o phng phap s dung giai thuat ghep o th phu hp cho viec phoi hp ghep. Moi o th trong tap con rut gon phu hp da vao o th au vao cho viec s dung quy c giai thuat ghep. Nhng o th ghep c them vao toan bo ket qua cua phng phap phuc hoi d lieu, ngoai tr nonmaching graph. Seminar nay e xuat viec ap dung tiep thu cacbo may ky thuat vao viec thc hien cac bc loc cua phng phap phuc hoi c s d lieu. e xuat cac cau truc a c anh gia tap trung vao viec loc c s d lieu. Quan he gia phng phap loc c s d lieu va giai thuat ghep S phu hp cua viec trnh bay ac tnh o th Loc o th vect ac tnh Loc quyet nh Tiep theo sau, viec thu c nhng ket qua a c rut gon se c tom tat va nhng ket luan c rut ra cac topic tren. V.1.3 S o loc c s d lieu e at c nhng hieu biet chung trong da ter6n viec a ra viec phuc hoi cau truc c s d lieu (viec loc theo viec ghep tuan t c phat trien ay u) viec nghien cu a gop phan anh gia cac quan he gia viec thc hien loc va thc hien giai thuat ghep chnh xac. Trong nghien cu nay a ch ra viec ch i co the xay ra t s loc co the anh gia so sanh viec thc hien loc va HV: Nguyen Thai Nho MSHV: CH0401036 Trang 41

H CNTT Tp HCM Seminar C s Tri Thc thc hien non-maching(khong ghep) ap dung giai thuat ghep. Ta co the nhan thay rang khi so sanh hieu qua cua loc c s d lieu o th, trai lai nhng co gang nghien cu ngay nay ve veic thc hien ghep cua mot giai thuat ghep o th la nhan to noi troi nhng tr khi viec thc hien non-maching cua mot giai thuat giong vay. Trong qua trnh nghien cu, mot so giai thuat nh tang toan bo kch thc c s d lieu, kch thc cua c s d lieu sau khi loc, so lan ghep trong c s d lieu va thi gian can cho viec loc a c xac nh anh hng en he so cua o th ghep. Vai trng hp c a ra viec pho bien giai thuat ghep o th vi nhng giai thuat khac phu thuoc vao trng hp phuc hoi c s d lieu. Trong Seminar nay, ngoai viec xem xet chung nhng moi quan he gia nhng giai thuat loc c s d lieu va o th ghep, nhng phng phap loc c s d lieu khac nhau a c khao sat. oi vi nhng phng phap nay, ba giai thuat ghep a c xem xet viec loc c s d lieu. Graph isomorphism Subgraph isomorphism Error-tolerant graph matching

Da tren c s nhng giai thuat ghep, loc c s d lieu s dung nhng vect ac tnh va nhng cay quyet nh a c c lng. Nhng ac tnh o th trong giai oan au cua cong viec, nhng ac tnh o th thch hp a c nh ngha oi vi nhng rang buoc khac nhau trong viec loc. Nhng ac tnh o th thch hp khi can th co the de dang c rut ra trong viec duy tr bac cao cua saliency

HV: Nguyen Thai Nho MSHV: CH0401036

Trang 42

H CNTT Tp HCM Seminar C s Tri Thc Nhng ac tnh c s dung trong tnh huong cua cong viec a c la chon da vao o phc tap mc thap cua viec tnh toan e bao dam viec rut ra nhanh. Trong nhng th nghiem a ch ra la chung co 1 bac cao cua saliency (muc 9.1) va bi vay no rat thch hp cho viec loc c s d lieu. Hn na, no cung cho thay rang nhng s ket hp cua nhng ac tnh hoan thien bac saliency trong khi viec gi rut ra cac gia tr khong oi. V.1.4 Loc vect ac tnh Khi da vao nhng kieu ac tnh dan xuat, nhng phng phap loc vect n gian a c e xng. e anh gia hieu qua cua loc c s d lieu da vao ac tnh nhng vect tiep theo nhng phng phap so sanh vect cho tat ca nhng s o ghep c xem xet va phat trien. oi vi o th ong dang, mot phng phap trc tiep e so sanh v tr vect ac tnh co trang thai bang nhau c ap dung. No cho thay rang, cung phng phap so sanh co the c s dung cho o th con neu viec trnh bay ac tnh hp ly. oi vi viec hieu chnh loi trong o th ghep, mot phng phap phc tap hn c thc hien tren mot tap con cua nhng ac tnh c gii thieu va phat trien. Da vao s bien oi cua tap con tra lai nhng phng phap c lng tren kch thc cc ai gia viec so sanh hai o th. Theo anh gia nay kch thc cua o th con chung cc ai gii han thap hn cua khoang cach gia hai o th co the c cho. No cho thay rang loc vect ac tnh giam mot cach ang ke so lng nhng o th se c kiem tra oi vi moi giai thuat ghep. T ay, ch duy nhat 1 phan rat nho cua c s d lieu o th nguyen ban can phai tra qua mot giai thuat ghep phat trien ay u (muc 9.2). Bi vay co the noi rang loc c s d lieu HV: Nguyen Thai Nho MSHV: CH0401036 Trang 43

H CNTT Tp HCM Seminar C s Tri Thc c da vao nhng vect ac tnh la phng phap thch hp oi vi viec giam hieu qua. Ngoai hieu qua loc chi oi hoi tnh toan cua viec loc vect ac tnh cung a c o. Quan sat no ta thay rang s phu thuoc vao kieu o th mot cac tng oi ln nhng vect ac tnh a ra nhng oi hoi tnh toan cao cho viec so sanh nhng vect ac tnh. e giam bt nhng oi hoi nay trong khi viec bao quan ky thuat khai thac d lieu e giam hieu qua a c ap dung. Loc cay quyet nh e giam bt o tnh toan phc tap cua nhng phng phap loc vect, nhng phng phap cay quyet nh c ap dung. Nh mot bc x ly c bo sung, ngoai viec trch ra nhng vect ac tnh tren nhng c s d lieu o th, nhng vect ac tnh c phan tch s dung ky thuat cay quyet nh c biet t khai thac d lieu. Ket qua cua bc x ly nay la cau truc cay e phan loai nhng ac tnh se c kiem tra theo kha nang mo ta nam di tap o th. Tng t viec loc vect ac tnh, nhng cau truc cay khac nhau can thiet cho viec dan xuat cho bat ky s o o th ghep nao. Khi thc thien, nhng ac tnh can c trch t o th mau au vao a cho va cay quyet nh ngang qua. Thu tuc nhanh ngang tra lai mot tap o th c kiem tra da vao o th au vao vi giai thuat ghep ay u. Noi chung no cho thay rang ap dung phng phap cay quyet nh giam mot cach ang ke so lng nhng lan kiem tra trong khi e am bao viec giam hieu qua cua phng phap loc vect. oi vi o th ong dang va xem xet c s d lieu cho thay rang viec loc noi chung se loai tr hn 99% nhng o th trong c s d lieu (muc 10.1). Ket qua nay at c da tren hai kieu c s d lieu o th c anh gia, viec phat sinh nhng o th cung nh nhng c s d lieu nhieu c s d lieu thc. oi vi o th con ong dang, hai phng phap loc HV: Nguyen Thai Nho MSHV: CH0401036 Trang 44

H CNTT Tp HCM Seminar C s Tri Thc c e cap. Da vao nhng cay quyet nh c dung cho viec loc o th ong dang, mot thu tuc nhanh ac biet a c phat trien cho phep loc o th con ong dang vi nhng ng vien i qua cay o th ong dang. S bien oi thu tuc nhanh boc lo nhng tnh toan nho overhead trong thi gian nhanh qua. e giam bt overhead mot phng phap th hai a c phat trien, phong theo cau truc cay quyet nh trong khi s dung giai thuat nhanh tng ng s dung oi vi loc o th ong dang. T bo viec giam tnh toan overhead la mot yeu cau tang bo nh cua cau truc cay. Tat nhien, viec loc ca hai o th con ong dang hieu qua khong cao nh viec thc hien loc o th ong dang (muc 10.2). Ta thay rang viec yeu cau tang kch thc bo nh phong theo cau truc cay qua cao e cung cap mot ket qua loc thch hp (muc 10.2.2). Cay dan xuat n gian khong kiem tra ay u cac ac tnh e khao sat nhng c s d lieu vi o th au vao. Va la, nhng ket qua nay a c xac nhan giong nh nhieu c s d lieu o th thc. oi vi viec phong theo giai thuat nhanh trong mat khac viec thc hien giam c s d lieu o th c thc hien tot hn (muc 10.2.1). Da tren viec phat sinh nhieu dataset thc ket qua nhng tap ng vien ay nho hn ang ke so vi kch thc c s d lieu nguyen ban. Phng phap loc cay quyet nh c ap dung vao giai thuat ghep th ba, o th ghep error-tolerant. Trong Seminar nay, hai cau truc cay quyet nh cho phep loc nhng c s d lieu cua nhng o th oi vi nhng ng vien vi ngng khoang cach a c phat trien. Ca hai cau truc cay, n gian cung nh cau truc cay m rong da vao cung nguyen ly nhanh ngang. Nhng tnh toan sai lam khac nhau trong gia thiet ve tnh bo sung cua nhng ac tnh c tm thay ben di c s d lieu. oi vi cau HV: Nguyen Thai Nho MSHV: CH0401036 Trang 45

H CNTT Tp HCM Seminar C s Tri Thc truc cay n gian viec gia thiet a so nhng ac tnh xuat hien trong nhng mau au vao cung xuat hien trong nhng nhng c s d lieu o th. T ay, mot cau truc cay n gian c phat trien ni cay dan xuat dng lai khi mot so nut hoan thanh. Cau truc cay m rong gia thiet rang mot phan ln nhng ac tnh cua nhng mau au vao khong xuat hien trong c s d lieu. Vay th, dan xuat cua so t nut la c tiep tuc cho en khong co nhng ac tnh e lai cho phep dan xuat c xem xet tron ven cua au vao va o th c s d lieu o th trong nhanh ngang. Ca hai phng phap nay a c kiem tra ky da tren viec phat sinh nhieu c s d lieu o th thc (muc 10.3). Noi chung, no a ch ra (nh mong i) oi vi cum size a ra cau truc cay tot hn so vi cay n gian. Mac khac, no da tren viec a ra cau truc cay boc lo tnh toan overhead ang ke so sanh vi cau truc cay n gian. Trong khi viec phat sinh nhng tap d lieu o th (graph datasets) no da tren overhead noi chung la e tang hieu qua loc, oi vi nhieu c s d lieu thc khong c xac nhan. That ra, nhng c s d lieu thc s c xem xet, kch thc va phan phoi cua nhan alphabet, va bi vay thong tin cha ng trong no co tac ong quan trong da tren viec n gian la chong lai cau truc cay m rong. Viec tong hp no co the c nhn thay viec x ly nhng c s d lieu ln cua nhng o th quan trong trong viec nhan dang. Ta co the thay rang co gia tr tnh toan von co cao hn oi vi van e nay. Tuy nhien, phng phap phat trien trong Seminar nay, ap dung loc vect ac tnh trong viec ket hp vi phng phap cay quyet nh, a c a ra thch hp mc o cao i vi bai tap nay.

HV: Nguyen Thai Nho MSHV: CH0401036

Trang 46

H CNTT Tp HCM

Seminar C s Tri Thc

V.2 Hng phat trien

Da tren cong viec c lam trong Seminar nay co mot so van e se c xem xet cho cong viec tng lai. Tnh trang hien thi cua cong viec ang tien trien tiep tuc vi ba chien lc: M rong phng phap khai thac d lieu cho nhng so lieu cau truc o th o th Phng thc c phat trien trong Seminar nay mot giai oan no can chuyen mon hoa neu no s dung nhng mau ch so hoa. Cho en luc nay, ch vai c s d lieu cua nhng mau san co e dung trong fromat graph. Tuy nhien, viec thu thap nhieu d lieu tot thch hp ai dien cho o th. Document data (web hay tai lieu giay) a thanh cong trong viec ai dien va phan loai s dung nhng o th nh cau truc c d lieu. Nhng trng hp ch so hoa co the bao gom nhng kha nang tm kiem tai lieu tot hn (tm kiem tren mang, desktop search, ). Tam quan trong cua no tang dan theo s tien trien trong viec so hoa plan data, nh la street maps, building So lng ln nhng d lieu nh vay can c phan tch va bao quan bang nhieu cach. Nhng phng phap o th c s c e cap trong Seminar nay la tat nhien, thch hp va phng phap tot e lam viec nay. Vi tnh pho bien ngay cang tang cua nhng o th trong viec nhan dang s dung nhng o th co nhiem vu phan loai cung tang len ang ke. Nhng tap d lieu ln ang c so hoa va ai dien cho nhng o th. Nhng v du d lieu nh vay bao gom nhng tai lieu mang, tai lieu giay, nhng o hoa kien truc, biometric data. gan ay nhng o th ap dung thanh cong xem xet nhng he thong phan mem hay trong viec phan tch he thong. HV: Nguyen Thai Nho MSHV: CH0401036 Trang 47 S phat trien mot ng dung c s d lieu

H CNTT Tp HCM Seminar C s Tri Thc Viec cung cap framework trong Seminar nay co the c dung e phan tch viec thu thap so lieu o th e khoi phuc hay xac nh nhng quan he s hieu biet khong ro rang vao lan quan sat au tien. Hn na, thong qua viec cung cap framework, d lieu co the c phan tch oi vi mot dang giai thuat ghep o th. Nhng bc au trong hng dan nay a c phat trien bi ngi phan loai bi viec trnh bay nhng dau van tay cua c s d lieu NIST 4 (trong phu luc A) nhng nhng cai khac th bao gom de dang hn na. Nhieu tap d lieu co the c phan tch trong phng phap nay, mac du he thong khong nham chu yeu ti kieu ng dung nay. Phat trien he thong trong Seminar nay loc nhng c s d lieu cua nhng o th co the c coi la mot he thong nguyen mau. Mot thach thc thu v la s phat trien mot ng dung da vao nguyen mau. Co vai e tai can c a vao phng phap nay. Mot nhiem vu quan trong la viec phan hoa t ong cua nhng nhan c gan vao nhng nut o th. Van e c quan tam ay la tang cng viec quan tam en kien thc ve tnh trang thiet b la s phan hoa cua viec duy tr nhng thuoc tnh gan ay. Nhieu ky thuat yeu cau khai thac d lieu gia tr nhng ac tnh ac biet. Nhng cach khac xay dng mo hnh chnh xac hn khi ng dung vao nhng thuoc tnh rieng biet. V vay nghien cu trong lnh vc nay a tr nen pho bien hn. Trong khi he thong c e cap trong Seminar nay giam bt nhng nhan rieng biet tren nhng nut cua o th c x ly, th module quyet nh trong he thong co y ngha quan trong hn. Mot van e quan trong khac trong topic nay la viec phat trien mot ng dung t nguyen mau la s hp nhat vao trong he thong c s d lieu chung. Cho en ngay nay, he thong co kha nang nhng vect ac tnh khai thac d lieu, phan biet nhng ac tnh manh hn vi moi cai khac. Nhng co HV: Nguyen Thai Nho MSHV: CH0401036 Trang 48

H CNTT Tp HCM Seminar C s Tri Thc gang nho duy nhat c lam trong viec nghien cu tren d lieu con lai co the c s dung nh the nao vi nhng he thong c s d lieu truyen thong. Tuy nhien, mot ng dung c s d lieu o th thanh cong ang ke trong no lc e thong nhat (va viec co the thuc ay) viec quan tam en c s d lieu nh a c biet t cong nghiep. Hn na, trong he thong nguyen mau ch co mot c che c lng khong chnh xac, nhng cong cu ghep pho bien can c ton hp trong viec phat trien ay cac ng dung. nhng bc tren nhu cau toi thieu cho phuc hoi he thong c s d lieu ay u. Bat au t ieu nay , co mot s a dang rong cua nhng nhiem vu co the tiep nhan. Vi viec tang cng kha nang tnh toan cua phan cng ngay nay, co the bat au khai thac kha nang cua cac he thong nh vay se dan en nhng giai phap linh hoat hn vi viec ton tai nhng ky thuat khac c s dung ngay nay.

HV: Nguyen Thai Nho MSHV: CH0401036

Trang 49

H CNTT Tp HCM

Seminar C s Tri Thc

TAI LIEUTHAM KHAO

[1] J. Llads and G. Snchez. Graph matching versus graph parsing in graphics recognition. Int. Journal of Pattern Recognition and Artificial Intelligence, 18(3):455-475, 2004. [2] A. Schenker, M. Last, H. Bunke, and A. Kandel. Classification of web documents using graph matching. Int. Journal of Pattern Recognition and Artificial Intelligence, 18(3):475-496, 2004. [3] A. Schenker, M. Last, H. Bunke, and A. Kandel. Comparison of distance measures for graph-based cuming of documents. In E. Hancock and M. Vento, editors, Proc. 4th IAPR Int. Workshop on Graph Based Representations in Pattern Recognition, volume 2726 of LNCS,pages 202-213. Springer, 2003. [4] T. Caelli and S. Kosinov. Inexact graph matching using eigensubspace projection cuming. Int. Journal of Pattern Recognition and Artificial Intelligence, 18(3):329-355, 2004. [5] R. Wilson and E.R. Hancock. Levenshtein distance for graph spectral features. In J. Kittler, M. Petrou, and M. Nixon, editors, Proc. 17th Int. Conference on Pattern Recognition, volume 2, pages 489-492, 2004. [6] A. Robles-Kelly and E.R. Hancock. Graph edit distance from spectral seriation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 27(3):365-378, 2005. [7] T. Caelli and S. Kosinov. An eigenspace projection cuming IEEE Transactions on Pattern method for inexact graph matching. [8]

Analysis and Machine Intelligence, 26(4):515-519, 2004. H. Lodhi, C. Saunders, J. Shawe-Tayler, N. Cristianini, and C. Machine Learning, Watkins. Text classification using string kernels. 2:419-444,2002. [9] M. Neuhaus and H. Bunke. A graph matching based approach to fingerprint classification using directional variance. In Proc. Audio- and Video-based Biometric Person Authentication 2005. Springer, 2005. accepted for publication. HV: Nguyen Thai Nho MSHV: CH0401036 Trang 50

H CNTT Tp HCM Seminar C s Tri Thc [10] N. Yager and A. Amin. Fingerprint classification: A review. Pattern Analysis and Applications, 7(1):77-93, 2004. [11] D. Conte, P. Foggia, C. Sansone, and M. Vento. Thirty years of graph matching in pattern recognition. Int. Journal of Pattern Recognition and Artificial Intelligence, 18(3):265-298, 2004. [12] M.A. Van Wyk and B.J. Van Wyk. A learning-based framework for graph matching. Int. Journal of Pattern Recognition and Artificial Intelligence, 18(3):355-375, 2004. [13] H. Bunke, C. Irniger, and M. Neuhaus. Analysis and Processing ICIAP, 2005. to appear. [14] C. Irniger and H. Bunke. Decision trees for error-tolerant graph database filtering. In L. Brun and M. Vento, editors, Proc. 5th IAPR Int. Workshop on Graph Based Representations in Pattern Recognition, volume 3434 of LNCS, pages 301-312. Springer, 2005. [15] C. Irniger and H. Bunke. Decision tree structures for graph database filtering. In A. et al. Fred, editor, Structural, Syntactic, and Statistical Pattern Recognition, Proc. Joint IAPR Int. Workshops SSPR and SPR, volume 3138 of LNCS, pages 66-75. Springer, 2004. [16] C. Irniger and H. Bunke. Graph database filtering using decision trees. In J. Kittler, M. Petrou, and M. Nixon, editors, Proc. 17th Int. Conference on Pattern Recognition, volume 3, pages 383-388, 2004. Graph matching - new challenges and potential solutions. In Proc. 13th Int. Conf. Image

HV: Nguyen Thai Nho MSHV: CH0401036

Trang 51