際際滷

際際滷Share a Scribd company logo

際際滷

T
tuongnm
1 of 30
X叩c 畛nh ph動董ng tr狸nh qu畛 畉o c畛a m畛t ti畛u hnh tinh 畛ng d畛ng c畛a 畉i s畛 tuy畉n t鱈nh trong l箪 thuy畉t 畛 th畛 Khai th叩c vn b畉n v thu h畛i th担ng tin H動畛ng 畛NG D畛NG C畛A 畉I S畛 TUY畉N TNH TRONG KHAI PH D畛 LI畛U m Thanh Ph動董ng, Ng担 M畉nh T動畛ng Ngy 26 th叩ng 12 nm 2012
X叩c 畛nh ph動董ng tr狸nh qu畛 畉o c畛a m畛t ti畛u hnh tinh 畛ng d畛ng c畛a 畉i s畛 tuy畉n t鱈nh trong l箪 thuy畉t 畛 th畛 Khai th叩c vn b畉n v thu h畛i th担ng tin H動畛ng N畛I DUNG C畛A SEMINAR 1 X叩c 畛nh ph動董ng tr狸nh c畛a m畛t qu畛 畉o. 2 畛ng d畛ng 畉i s畛 tuy畉n t鱈nh trong l箪 thuy畉t 畛 th畛. 3 畛ng d畛ng 畉i s畛 tuy畉n t鱈nh trong khai th叩c vn b畉n v thu h畛i th担ng tin. 4 M畛t s畛 h動畛ng nghi棚n c畛u.
X叩c 畛nh ph動董ng tr狸nh qu畛 畉o c畛a m畛t ti畛u hnh tinh 畛ng d畛ng c畛a 畉i s畛 tuy畉n t鱈nh trong l箪 thuy畉t 畛 th畛 Khai th叩c vn b畉n v thu h畛i th担ng tin H動畛ng Ph動董ng tr狸nh 動畛ng 動畛ng th畉ng i qua hai i畛m Cho 2 i畛m ph但n bi畛t trong m畉t ph畉ng A(x1 ; y1 ) v B(x2 ; y2 ) l . Khi 坦 s畉 t畛n t畉i m畛t 動畛ng th畉ng i qua 2 i畛m A, B c坦 ph動董ng tr狸nh ax + by + c = 0 (1) V狸 A(x1 ; y1 ) v B(x2 ; y2 ) thu畛c 動畛ng th畉ng n棚n n坦 th畛a m達n (1), suy ra ax1 + by1 + c = 0 (2) ax2 + by2 + c = 0 (3) H狸nh: 動畛ng th畉ng qua hai i畛m K畉t h畛p (1), (2), (3) ta 動畛c 錚 錚 ax + by + c = 0 錚 x y 1 ax1 + by1 + c = 0 x1 y1 1 =0 (4) x2 y2 1 錚 ax2 + by2 + c = 0 錚
X叩c 畛nh ph動董ng tr狸nh qu畛 畉o c畛a m畛t ti畛u hnh tinh 畛ng d畛ng c畛a 畉i s畛 tuy畉n t鱈nh trong l箪 thuy畉t 畛 th畛 Khai th叩c vn b畉n v thu h畛i th担ng tin H動畛ng Ph動董ng tr狸nh 動畛ng V鱈 d畛 T狸m ph動董ng tr狸nh 動畛ng th畉ng i qua hai i畛m (2; 1) v (3; 7). p d畛ng c担ng th畛c (4) ta c坦 x y 1 2 1 1 =0 3 7 1 V畉y ph動董ng tr狸nh 動畛ng th畉ng c畉n t狸m l 6x + y + 11 = 0
X叩c 畛nh ph動董ng tr狸nh qu畛 畉o c畛a m畛t ti畛u hnh tinh 畛ng d畛ng c畛a 畉i s畛 tuy畉n t鱈nh trong l箪 thuy畉t 畛 th畛 Khai th叩c vn b畉n v thu h畛i th担ng tin H動畛ng Ph動董ng tr狸nh 動畛ng tr嘆n 動畛ng tr嘆n i qua ba i畛m Cho 3 i畛m ph但n bi畛t trong m畉t ph畉ng A(x1 ; y1 ), B(x2 ; y2 ) v C (x3 ; y3 ) l . Khi 坦 s畉 t畛n t畉i m畛t 動畛ng tr嘆n i qua 3 i畛m A, B, C c坦 ph動董ng tr狸nh (x a)2 + (y b)2 = R 2 hay a1 x 2 + y 2 + a2 x + a3 y + a4 = 0 (5) V狸 A(x1 ; y1 ), B(x2 ; y2 ), C (x3 ; y3 ) thu畛c 動畛ng tr嘆n n棚n n坦 th畛a m達n (5), suy ra 2 2 a1 x1 + y1 + a2 x1 + a3 y1 + a4 = 0 (6) 2 2 a1 x2 + y2 + a2 x2 + a3 y2 + a4 = 0 (7) 2 2 H狸nh: 動畛ng tr嘆n qua ba i畛m a1 x3 + y3 + a2 x3 + a3 y3 + a4 = 0 (8)
X叩c 畛nh ph動董ng tr狸nh qu畛 畉o c畛a m畛t ti畛u hnh tinh 畛ng d畛ng c畛a 畉i s畛 tuy畉n t鱈nh trong l箪 thuy畉t 畛 th畛 Khai th叩c vn b畉n v thu h畛i th担ng tin H動畛ng Ph動董ng tr狸nh 動畛ng tr嘆n 動畛ng tr嘆n i qua ba i畛m K畉t h畛p (5), (6), (7), (8) ta 動畛c x2 + y2 x y 1 2 2 x1 + y1 x1 y1 1 2 2 =0 (9) x2 + y2 x2 y2 1 2 2 x3 + y3 x3 y3 1 Do 坦, v畛i m畛i i畛m (x; y ) n畉m tr棚n m畛t 動畛ng tr嘆n th狸 th畛a m達n 畛nh th畛c (9) v ng動畛c l畉i v畛i m畛i i畛m (x; y ) th畛a m達n 畛nh th畛c (9) 畛u n畉m tr棚n m畛t tr嘆n.
X叩c 畛nh ph動董ng tr狸nh qu畛 畉o c畛a m畛t ti畛u hnh tinh 畛ng d畛ng c畛a 畉i s畛 tuy畉n t鱈nh trong l箪 thuy畉t 畛 th畛 Khai th叩c vn b畉n v thu h畛i th担ng tin H動畛ng Ph動董ng tr狸nh 動畛ng tr嘆n V鱈 d畛 T狸m ph動董ng tr狸nh 動畛ng tr嘆n i qua ba i畛m (1; 7), (6; 2) v (4; 6). p d畛ng c担ng th畛c (9) ta c坦 x2 + y2 x y 1 50 1 7 1 =0 40 6 2 1 52 4 6 1 V畉y ph動董ng tr狸nh 動畛ng tr嘆n c畉n t狸m l 2 2 10 x 2 + y 2 20x 40y 200 = 0 hay (x 1) + (y 2) = 52
X叩c 畛nh ph動董ng tr狸nh qu畛 畉o c畛a m畛t ti畛u hnh tinh 畛ng d畛ng c畛a 畉i s畛 tuy畉n t鱈nh trong l箪 thuy畉t 畛 th畛 Khai th叩c vn b畉n v thu h畛i th担ng tin H動畛ng Ph動董ng tr狸nh 動畛ng Conic 動畛ng Conic i qua 5 i畛m Ph動董ng tr狸nh t畛ng qu叩t c畛a 動畛ng conic trong m畉t ph畉ng (Parabol, Hyperbol, ellip, c叩c suy bi畉n c畛a 動畛ng cong) a1 x 2 + a2 xy + a3 y 2 + a4 x + a5 y + a6 = 0 (10) Ph動董ng tr狸nh (10) c坦 6 h畛 s畛, ta c坦 th畛 gi畉m c嘆n 5 h畛 s畛 b畉ng c叩ch chia cho m畛t h畛 s畛 kh叩c 0 v nh動 v畉y 畛 畛 x叩c 畛nh 動畛c c叩c h畛 s畛 c畛a n坦 th担ng qua 5 i畛m ph但n bi畛t trong m畉t ph畉ng. T動董ng t畛 nh動 tr棚n ta c滴ng c坦 畛nh th畛c x叩c 畛nh ph動董ng tr狸nh c叩c 動畛ng conic l x2 xy y2 x y 1 2 2 x1 x1 y1 y1 x1 y1 1 2 2 x2 x2 y2 y2 x2 y2 1 2 2 =0 x3 x3 y3 y3 x3 y3 1 2 2 x4 x4 y4 y4 x4 y4 1 2 2 x5 x5 y5 y5 x5 y5 1 (11) H狸nh: 動畛ng conic qua 5 i畛m
X叩c 畛nh ph動董ng tr狸nh qu畛 畉o c畛a m畛t ti畛u hnh tinh 畛ng d畛ng c畛a 畉i s畛 tuy畉n t鱈nh trong l箪 thuy畉t 畛 th畛 Khai th叩c vn b畉n v thu h畛i th担ng tin H動畛ng Ph動董ng tr狸nh 動畛ng Conic Ph動董ng tr狸nh c畛a m畛t qu畛 畉o M畛t nh thi棚n vn ng動畛i mu畛n x叩c 畛nh qu畛 畉o c畛a m畛t ti畛u hnh tinh h畛 m畉t tr畛i ph畉i thi畉t l畉p m畛t h畛 th畛ng t畛a 畛 Cartesian trong m畉t ph畉ng qu畛 畉o v畛i m畉t tr畛i t畉i g畛c. 董n v畛 thi棚n vn o l動畛ng 動畛c s畛 d畛ng d畛c theo tr畛c (1 董n v畛 thi棚n vn = kho畉ng c叩ch c畛a tr叩i 畉t v畛i m畉t tr畛i = 93 tri畛u d畉m). Theo quy lu畉t c畛a Kepler, qu畛 畉o ph畉i l m畛t h狸nh elip, do 坦, c叩c nh thi棚n vn c坦 nm quan s叩t c叩c ti畛u hnh tinh t畉i nm th畛i i畛m kh叩c nhau v t狸m 動畛c nm i畛m d畛c theo qu畛 畉o (8, 025; 8, 310), (10, 170; 6, 365), (11, 202; 3, 212), (10, 736; 0, 375) v (9, 092; 2, 267) H狸nh: Qu畛 畉o c畛a ti畛u hnh tinh
X叩c 畛nh ph動董ng tr狸nh qu畛 畉o c畛a m畛t ti畛u hnh tinh 畛ng d畛ng c畛a 畉i s畛 tuy畉n t鱈nh trong l箪 thuy畉t 畛 th畛 Khai th叩c vn b畉n v thu h畛i th担ng tin H動畛ng Ph動董ng tr狸nh 動畛ng Conic Ph動董ng tr狸nh c畛a m畛t qu畛 畉o p d畛ng c担ng th畛c (11) ta c坦 ph動董ng tr狸nh c畛a qu畛 畉o l x2 xy y2 x y 1 66, 401 66, 688 69, 056 8, 025 8, 310 1 103, 429 64, 630 40, 386 10, 170 6, 355 1 =0 125, 485 35, 981 10, 317 11, 202 3, 212 1 115, 262 4, 026 0, 141 10, 735 0, 375 1 82, 664 20, 612 5, 139 9, 092 2, 267 1 V畉y ph動董ng tr狸nh qu畛 畉o c畛a ti畛u hnh t狸nh c畉n t狸m l 386, 802x 2 102, 895xy +446, 029y 2 2476, 443x1427, 998y 17109, 375 = 0
X叩c 畛nh ph動董ng tr狸nh qu畛 畉o c畛a m畛t ti畛u hnh tinh 畛ng d畛ng c畛a 畉i s畛 tuy畉n t鱈nh trong l箪 thuy畉t 畛 th畛 Khai th叩c vn b畉n v thu h畛i th担ng tin H動畛ng Ph動董ng tr狸nh m畉t ph畉ng Ph動董ng tr狸nh m畉t ph畉ng i qua 3 i畛m Ph動董ng tr狸nh m畉t ph畉ng qua 3 i畛m (x1 , y1 , z1 ), (x2 , y2 , z2 ), (x3 , y3 , z3 ) x叩c 畛nh b畉ng 畛nh th畛c x y z 1 x1 y1 z1 1 =0 (12) x2 y2 z2 1 x3 y3 z3 1 V鱈 d畛. Ph動董ng tr狸nh m畉t ph畉ng qua 3 i畛m (1, 1, 0) ; (2, 0, 1) ; (2, 9, 2) l x y z 1 1 1 0 1 = 0 hay 2x y + 3x 1 = 0 2 0 1 1 2 9 2 1
X叩c 畛nh ph動董ng tr狸nh qu畛 畉o c畛a m畛t ti畛u hnh tinh 畛ng d畛ng c畛a 畉i s畛 tuy畉n t鱈nh trong l箪 thuy畉t 畛 th畛 Khai th叩c vn b畉n v thu h畛i th担ng tin H動畛ng Ph動董ng tr狸nh m畉t c畉u Ph動董ng tr狸nh m畉t c畉u i qua 4 i畛m Ph動董ng tr狸nh m畉t c畉u qua 4 i畛m (x1 , y1 , z1 ), (x2 , y2 , z2 ), (x3 , y3 , z3 ), (x4 , y4 , z4 ) c坦 d畉ng x2 + y2 + z2 x y z 1 2 2 2 x1 + y1 + z1 x1 y1 z1 1 2 2 2 x2 + y2 + z2 x2 y2 z2 1 =0 (13) 2 2 2 x3 + y3 + z3 x3 y3 z3 1 2 2 2 x4 + y4 + z4 x4 y4 z4 1
X叩c 畛nh ph動董ng tr狸nh qu畛 畉o c畛a m畛t ti畛u hnh tinh 畛ng d畛ng c畛a 畉i s畛 tuy畉n t鱈nh trong l箪 thuy畉t 畛 th畛 Khai th叩c vn b畉n v thu h畛i th担ng tin H動畛ng Ph動董ng tr狸nh m畉t c畉u V鱈 d畛 Ph動董ng tr狸nh m畉t c畉u qua 4 i畛m (0, 3, 2) , (1, 1, 1) , (2, 1, 0) , (5, 1, 3) l x2 + y2 + z2 x y z 1 13 0 3 2 1 3 1 1 1 1 =0 5 2 1 0 1 35 5 1 3 1 hay x 2 + y 2 + z 2 4x 2y 6z + 5 = 0 hay 2 2 2 (x 2) + (y 1) + (z 3) = 9
X叩c 畛nh ph動董ng tr狸nh qu畛 畉o c畛a m畛t ti畛u hnh tinh 畛ng d畛ng c畛a 畉i s畛 tuy畉n t鱈nh trong l箪 thuy畉t 畛 th畛 Khai th叩c vn b畉n v thu h畛i th担ng tin H動畛ng M畛i quan h畛 trong gia 狸nh M畛i quan h畛 trong gia 狸nh V畛i m畛t 畛 th畛 c坦 h動畛ng g畛m n 畛nh P1 , P2 , ..., Pn , ta c坦 m畛t ma tr畉n M = [mij ]nn , g畛i l ma tr畉n 畛nh, trong 坦 1 n畉u Pi Pj mij = 0 v畛i c叩c tr動畛ng h畛p kh叩c Ma tr畉n 畛nh l 錚 錚 0 1 0 0 1 錚 0 0 1 1 0 錚 錚 錚 M=錚 0錚 0 0 1 0 錚 錚 錚 0 1 0 0 1 錚 0 1 1 0 0
X叩c 畛nh ph動董ng tr狸nh qu畛 畉o c畛a m畛t ti畛u hnh tinh 畛ng d畛ng c畛a 畉i s畛 tuy畉n t鱈nh trong l箪 thuy畉t 畛 th畛 Khai th叩c vn b畉n v thu h畛i th担ng tin H動畛ng M畛i quan h畛 trong gia 狸nh M畛i quan h畛 trong gia 狸nh M畛t gia 狸nh g畛m b畛, m畉, con g叩i v hai con trai. C叩c thnh vi棚n trong gia 狸nh c坦 t畉m 畉nh h動畛ng 畉n m畛i thnh vi棚n kh叩c nh動: m畉 c坦 t畉m 畉nh h動畛ng v畛i con g叩i v con trai l畛n tu畛i nh畉t; b畛 c坦 t畉m 畉nh h動畛ng v畛i hai con trai; con g叩i c坦 th畛 畉nh h動畛ng 畉n ng動畛i cha; 畛a con trai l畛n c坦 th畛 畉nh h動畛ng 畉n 畛a em 炭t; v 畛a em 炭t th狸 c坦 畉nh h動畛ng 畉n ng動畛i m畉. Ch炭ng ta c坦 th畛 m担 h狸nh m畛i quan h畛 gia 狸nh v畛i m畛t 畛 th畛 c坦 畛nh l nm thnh vi棚n trong gia 狸nh 坦. Ma tr畉n 畛nh l 錚M F D OS YS錚 M 0 0 1 1 0 F 錚 0 0 0 1 錚 1 錚 錚 D 錚 0 1 0 0 錚 0 錚 錚 OS 錚 0 0 0 0 1 錚 YS 1 0 0 0 0
X叩c 畛nh ph動董ng tr狸nh qu畛 畉o c畛a m畛t ti畛u hnh tinh 畛ng d畛ng c畛a 畉i s畛 tuy畉n t鱈nh trong l箪 thuy畉t 畛 th畛 Khai th叩c vn b畉n v thu h畛i th担ng tin H動畛ng M畛i quan h畛 trong gia 狸nh M畛i quan h畛 trong gia 狸nh Ma tr畉n 畛nh l 錚M F D OS YS錚 M 0 0 1 1 0 F 錚 0 0 0 1 錚 1 錚 錚 D 錚 0 1 0 0 錚 0 錚 錚 OS 錚 0 0 0 0 1 錚 YS 1 0 0 0 0 畛 但y ng動畛i cha kh担ng 畉nh h動畛ng tr畛c ti畉p 畉n ng動畛i m畉, nh動ng l畉i 畉nh h動畛ng 畉n con 炭t, ng動畛i 畉nh h動畛ng 畉n ng動畛i m畉 F YS M v ta c坦 k畉t n畛i 2 b動畛c t畛 F 畉n M. Nh狸n tr棚n h狸nh v畉 ta c坦 M D l k畉t n畛i 1 b動畛c , F OS YS M c坦 k畉t n畛i 3 b動畛c .
X叩c 畛nh ph動董ng tr狸nh qu畛 畉o c畛a m畛t ti畛u hnh tinh 畛ng d畛ng c畛a 畉i s畛 tuy畉n t鱈nh trong l箪 thuy畉t 畛 th畛 Khai th叩c vn b畉n v thu h畛i th担ng tin H動畛ng S畛 k畉t n畛i r b動畛c S畛 k畉t n畛i r b動畛c T畛 v鱈 d畛 tr棚n ta x但y d畛ng c担ng th畛c t狸m s畛 k畉t n畛i r b動畛c (r = 1, 2, ...) t畛 畛nh Pi t畛i 畛nh Pj c畛a m畛t 畛 th畛 c坦 h動畛ng. S畛 k畉t n畛i 1 b動畛c t畛 Pi t畛i Pj l mij , ta th畉y n坦 kh担ng c坦 ho畉c c坦 1 k畉t n畛i Pi Pj ph畛 thu畛c vo mij = 0 hay mij = 1. V畛i s畛 k畉t n畛i 2 b動畛c t畛 ma tr畉n 狸nh M ta t鱈nh M 2 , khi 坦 (2) mij = mi1 m1j + mi2 m2j + 揃 揃 揃 + min mnj N畉u mi1 = m1j = 1 th狸 c坦 m畛t k畉t n畛i 2 b動畛c t畛 Pi P1 Pj . N畉u mi1 = 0 ho畉c m1j = 0 th狸 kh担ng c坦 k畉t n畛i 2 b動畛c ny. V畉y Pi P1 Pj l m畛t k畉t n畛i 2 b動畛c khi v ch畛 khi mi1 m1j = 1. T動董ng t畛 v畛i Pi Pk Pj v畛i k = 1, 2, ... l m畛t k畉t n畛i 2 b動畛c khi v chi khi mik mkj = 1. T畛ng qu叩t ta c坦 k畉t qu畉 sau: 畛nh l箪 (r ) Cho M l ma tr畉n 畛nh c畛a m畛t 畛 th畛 c坦 h動畛ng v mij l ph畉n t畛 th畛 (r ) (i, j) c畛a M r . Khi 坦 mij l s畛 li棚n k畉t r b動畛c t畛 Pi t畛i Pj .
X叩c 畛nh ph動董ng tr狸nh qu畛 畉o c畛a m畛t ti畛u hnh tinh 畛ng d畛ng c畛a 畉i s畛 tuy畉n t鱈nh trong l箪 thuy畉t 畛 th畛 Khai th叩c vn b畉n v thu h畛i th担ng tin H動畛ng S畛 k畉t n畛i r b動畛c L畛 tr狸nh c畛a m叩y bay H狸nh tr棚n l b畉n 畛 l畛 tr狸nh c畛a m畛t h達ng hng kh担ng nh畛 ph畛c v畛 cho b畛n thnh ph畛 P1 , P2 , P3 , P4 D畛a vo b畉n 畛 l畛 tr狸nh, ta c坦 ma tr畉n 畛nh l 錚 錚 錚 錚 0 1 1 0 2 0 1 1 錚 1 0 1 0 錚 2 錚 1 1 1 1 錚 M=錚 錚 1 0 0 錚,M = 錚 錚 1 錚 錚 0 2 2 0 錚 0 1 1 0 2 0 1 1 錚 錚 1 3 3 1 3 錚 2 2 3 1 錚 M =錚 錚 4 0 2 錚 T畛 c叩c ma tr畉n ta th畉y 2 錚 1 3 3 1 m43 = 1 c坦 1 k畉t n畛i 1 b動畛c: P4 P3 (2) m43 = 1 c坦 1 k畉t n畛i 2 b動畛c: P4 P2 P3 (3) m43 = 3 c坦 3 k畉t n畛i 3 b動畛c: P4 P3 P4 P3 , P4 P2 P1 P3 , P4 P3 P1 P3
X叩c 畛nh ph動董ng tr狸nh qu畛 畉o c畛a m畛t ti畛u hnh tinh 畛ng d畛ng c畛a 畉i s畛 tuy畉n t鱈nh trong l箪 thuy畉t 畛 th畛 Khai th叩c vn b畉n v thu h畛i th担ng tin H動畛ng Clique c畛a 畛 th畛 Clique c畛a 畛 th畛 N畉u coi c叩c Pi l c叩c 畛nh c畛a m畛t 畛 th畛 c坦 h動畛ng v g畛i S = [sij ]nn , 1 n畉u Pi Pj trong 坦 sij = ta c坦 k畉t qu畉 sau: 0 v畛i c叩c tr動畛ng h畛p kh叩c 畛nh l箪 (3) Gi畉 s畛 sij l ph畉n t畛 th畛 (i, j) c畛a S 3 , khi 坦 畛nh Pi thu畛c c叩c Clique (3) n畉u v ch畛 n畉u sii = 0 V鱈 d畛 1: Gi畉 s畛 m畛t 畛 th畛 c坦 h動畛ng c坦 ma tr畉n 畛nh 錚 錚 錚 錚 錚 錚 0 1 1 1 0 1 0 1 0 3 0 2 錚 1 0 1 0 錚 錚 1 0 1 0 錚 3 錚 3 0 2 0 錚 M=錚 錚 0 1 0 1 錚獅S =錚 0 錚 錚 錚,S = 錚 錚 1 0 0 錚 錚 0 2 0 1 錚 1 0 0 0 1 0 0 0 2 0 1 0 Ta th畉y c叩c ph畉n t畛 n畉m tr棚n 動畛ng ch辿o ch鱈nh c畛a S 3 畛u b畉ng 0 n棚n 畛 th畛 kh担ng c坦 Clique.
X叩c 畛nh ph動董ng tr狸nh qu畛 畉o c畛a m畛t ti畛u hnh tinh 畛ng d畛ng c畛a 畉i s畛 tuy畉n t鱈nh trong l箪 thuy畉t 畛 th畛 Khai th叩c vn b畉n v thu h畛i th担ng tin H動畛ng Clique c畛a 畛 th畛 V鱈 d畛 2: Gi畉 s畛 m畛t 畛 th畛 c坦 h動畛ng c坦 ma tr畉n 畛nh 錚 錚 錚 錚 0 1 0 1 1 0 1 0 1 1 錚 1 0 0 1 0 錚 錚 1 0 0 1 0 錚 錚 錚 錚 錚 M=錚 1 1 0 1 0 錚財S =錚 錚 錚 錚 0 0 0 0 0 錚 錚 錚 1 1 0 0 0 錚 錚 1 1 0 0 0 錚 1 0 0 1 0 1 0 0 0 0 suy ra 錚 錚 2 4 0 4 3 錚 4 2 0 3 1 錚 3 錚 錚 S =錚 錚 0 0 0 0 0 錚 錚 錚 4 3 0 2 1 錚 3 1 0 1 0 (3) (3) (3) Ta c坦 s11 = 0, s22 = 0, s44 = 0, suy ra c叩c 畛nh P1 , P2 , P3 thu畛c Clique v 畛 thi ch畛 c坦 1 Clique l {P1 , P2 , P3 }.
X叩c 畛nh ph動董ng tr狸nh qu畛 畉o c畛a m畛t ti畛u hnh tinh 畛ng d畛ng c畛a 畉i s畛 tuy畉n t鱈nh trong l箪 thuy畉t 畛 th畛 Khai th叩c vn b畉n v thu h畛i th担ng tin H動畛ng B畉c c畛a m畛t 畛nh B畉c c畛a m畛t 畛nh Gi畉 s畛 5 畛i b坦ng 叩 g畉p nhau 炭ng m畛t l畉n v k畉t qu畉 動畛c th畛 hi畛n tr棚n 畛 th畛 c坦 h動畛ng Ma tr畉n 畛nh l 錚 錚 0 0 1 1 0 錚 錚 1 0 1 0 1 錚 錚 M=錚 錚 0 0 0 1 0 錚 錚 錚 0 1 0 0 0 錚 1 0 1 1 0 T狸m th畛 h畉ng c畛a 5 畛i b坦ng tr棚n? Vi畛c gi畉i bi to叩n tr棚n l vi畛c x畉p b畉c c畛a c叩c 畛nh tr棚n 畛 th畛 c坦 h動畛ng. Ta c坦 k畉t qu畉 sau:
X叩c 畛nh ph動董ng tr狸nh qu畛 畉o c畛a m畛t ti畛u hnh tinh 畛ng d畛ng c畛a 畉i s畛 tuy畉n t鱈nh trong l箪 thuy畉t 畛 th畛 Khai th叩c vn b畉n v thu h畛i th担ng tin H動畛ng B畉c c畛a m畛t 畛nh B畉c c畛a m畛t 畛nh 畛nh l箪 B畉c c畛a m畛t 畛nh trong 畛 th畛 c坦 h動畛ng l t畛ng s畛 c叩c k畉t n畛i 1 b動畛c v k畉t n畛i 2 b動畛c c畛a n坦 v畛i c叩c 畛nh kh叩c. Do 坦 b畉c c畛a 畛nhPi l t畛ng c叩c s畛 h畉ng 畛 hng th畛 i c畛a ma tr畉n A = M + M 2 . V畉y t畛 ma tr畉n M ta c坦 A=M + M2 = 錚 錚 錚 錚 錚 錚 0 0 1 1 0 0 1 0 1 0 0 1 1 2 0 錚 錚 1 0 1 0 1 錚 錚 1 0 錚 錚 2 3 0 錚 錚 錚 錚 2 0 3 3 1 錚 錚 =錚 錚 0 0 0 1 0 錚+錚 0 1 錚 錚 0 0 0 錚=錚 錚 錚 0 1 0 1 0 錚 錚 錚 0 1 0 0 0 錚 錚 1 0 1 0 1 錚 錚 1 1 1 0 1 錚 1 0 1 1 0 0 1 1 2 0 1 1 2 3 0 V畉y th畛 t畛 c叩c 畛i b坦ng l : Nh畉t 畛i 2, nh狸 畛i 5, ba c坦 2 畛i 4 v 1, cu畛i b畉ng l 畛i 3.
X叩c 畛nh ph動董ng tr狸nh qu畛 畉o c畛a m畛t ti畛u hnh tinh 畛ng d畛ng c畛a 畉i s畛 tuy畉n t鱈nh trong l箪 thuy畉t 畛 th畛 Khai th叩c vn b畉n v thu h畛i th担ng tin H動畛ng C叩c b動畛c ti畉n hnh v thu畉t to叩n Khai th叩c vn b畉n l g狸? C叩c ph動董ng ph叩p 畛 chi畉t xu畉t c叩c th担ng tin h畛u 鱈ch t畛 c董 s畛 d畛 li畛u l畛n v th動畛ng kh担ng 動畛c c畉u tr炭c. Thu h畛i th担ng tin. T狸m ki畉m trong c董 s畛 d畛 li畛u v畛i m畛t truy v畉n b畉ng m畛t b畛 t畛 kh坦a, t狸m 畛 t畉t c畉 c叩c ti li畛u c坦 li棚n quan. S畛 d畛ng c叩c c担ng c畛 c坦 s畉n (SAS Text Miner, Statistics Text-mining toolbox...)
X叩c 畛nh ph動董ng tr狸nh qu畛 畉o c畛a m畛t ti畛u hnh tinh 畛ng d畛ng c畛a 畉i s畛 tuy畉n t鱈nh trong l箪 thuy畉t 畛 th畛 Khai th叩c vn b畉n v thu h畛i th担ng tin H動畛ng C叩c b動畛c ti畉n hnh v thu畉t to叩n C叩c b動畛c th畛c hi畛n 1 Chu畉n b畛 ti li畛u. 2 X但y d畛ng ma tr畉n ti li畛u. 3 Truy v畉n d畛 li畛u b畉ng c叩ch o kho畉ng c叩ch. 4 N辿n d畛 li畛u b畉ng x畉p x畛 th畛 h畉ng th畉p : Thu畉t to叩n SVD (The Singular Value Decomposition). 5 X畉p h畉n v ph畉n h畛i.
X叩c 畛nh ph動董ng tr狸nh qu畛 畉o c畛a m畛t ti畛u hnh tinh 畛ng d畛ng c畛a 畉i s畛 tuy畉n t鱈nh trong l箪 thuy畉t 畛 th畛 Khai th叩c vn b畉n v thu h畛i th担ng tin H動畛ng V鱈 d畛 V鱈 d畛
X叩c 畛nh ph動董ng tr狸nh qu畛 畉o c畛a m畛t ti畛u hnh tinh 畛ng d畛ng c畛a 畉i s畛 tuy畉n t鱈nh trong l箪 thuy畉t 畛 th畛 Khai th叩c vn b畉n v thu h畛i th担ng tin H動畛ng V鱈 d畛 V鱈 d畛 Ma tr畉n ti li畛u 錚 錚 0 1 0 1 1 0 1 錚 錚 0 1 1 0 0 0 0 錚 錚 錚 錚 0 0 0 0 0 1 1 錚 錚 錚 錚 0 0 0 1 0 0 0 錚 錚 A=錚 錚 0 1 1 0 0 0 0 錚 錚 錚 錚 1 0 0 1 0 0 0 錚 錚 錚 錚 0 0 0 0 1 1 0 錚 錚 錚 0 0 1 1 0 0 0 錚 1 0 0 1 0 0 0 Trong 坦 Aij l t畉n s畛 tr畛ng s畛 c畛a thu畉t ng畛 th畛 i trong ti li畛u j.
X叩c 畛nh ph動董ng tr狸nh qu畛 畉o c畛a m畛t ti畛u hnh tinh 畛ng d畛ng c畛a 畉i s畛 tuy畉n t鱈nh trong l箪 thuy畉t 畛 th畛 Khai th叩c vn b畉n v thu h畛i th担ng tin H動畛ng V鱈 d畛 V鱈 d畛 Chu畉n h坦a ma tr畉n ti li畛u 錚 錚 0 0, 577 0 0, 447 0, 707 0 0, 707 錚 0 0, 577 0, 577 0 0 0 0 錚 錚 錚 錚 0 0 0 0 0 0, 707 0, 707 錚 錚 錚 錚 0 0 0 0, 447 0 0 0 錚 錚 錚 A= 錚 0 錚 0, 577 0, 577 0 0 0 0 錚 錚 錚 0, 707 0 0 0, 447 0 0 0 錚 錚 錚 錚 0 0 0 0 0, 707 0, 707 0 錚 錚 錚 錚 0 0 0, 577 0, 447 0 0 0 錚 0, 707 0 0 0, 447 0 0 0
X叩c 畛nh ph動董ng tr狸nh qu畛 畉o c畛a m畛t ti畛u hnh tinh 畛ng d畛ng c畛a 畉i s畛 tuy畉n t鱈nh trong l箪 thuy畉t 畛 th畛 Khai th叩c vn b畉n v thu h畛i th担ng tin H動畛ng V鱈 d畛 Truy v畉n Gi畉 s畛 c坦 m畛t truy v畉n vecto q, t狸m c叩c c畛t ai c畛a ma tr畉n A sao cho dist (q, ai ) tol (14) trong 坦 錚 錚 x y 錚 2, Chu畉n kho畉ng c叩ch Euclidean 錚 錚 xT y 錚 dist (q, ai ) = (15) 錚 1 cos (慮 (x, y )) = 1 x 2 y 2 錚 錚 錚 錚 arccos (慮 (x, y ))
X叩c 畛nh ph動董ng tr狸nh qu畛 畉o c畛a m畛t ti畛u hnh tinh 畛ng d畛ng c畛a 畉i s畛 tuy畉n t鱈nh trong l箪 thuy畉t 畛 th畛 Khai th叩c vn b畉n v thu h畛i th担ng tin H動畛ng V鱈 d畛 Truy v畉n: child home safety 錚 錚 錚 錚 0 0 錚 1 錚 錚 0, 577 錚 T畛 (14), (15) ta c坦 錚 錚 錚 錚 錚 0 錚 錚 0 錚 錚 錚 錚 錚 錚 0 錚 錚 0 錚 xT y 錚 錚 錚 錚 1 錚 , q = 錚 0, 577 錚 錚 cos (慮 (x, y )) = tol q=錚 錚 錚 錚 x 2 y 2 錚 0 錚 錚 0 錚 錚 錚 錚 錚 錚 0 錚 錚 0 錚 trong 坦 x = 1, y = 1 錚 錚 錚 錚 錚 1 錚 錚 0, 577 錚 0 0 Khi 坦 ta c坦 cosin c叩c c畛t c畛a A l qT A = 0 0, 667 1 0, 258 0 0 0 suy ra 1 cos (慮 (x, y )) c叩c c畛t c畛a A l 1 0, 333 0 0, 742 1 1 1 V畛i m畛c tol = 0, 5 ta c坦 hai ti li畛u 2, 3 th畛a m達n.
X叩c 畛nh ph動董ng tr狸nh qu畛 畉o c畛a m畛t ti畛u hnh tinh 畛ng d畛ng c畛a 畉i s畛 tuy畉n t鱈nh trong l箪 thuy畉t 畛 th畛 Khai th叩c vn b畉n v thu h畛i th担ng tin H動畛ng H動畛ng nghi棚n c畛u 1 畛ng d畛ng c畛a 畉i s畛 tuy畉n t鱈nh trong nh畉n d畉ng ch畛 vi畉t tay v畛i m畛t s畛 thu畉t to叩n TFIDF (TF = Term Frequency, IDF = Inverse Document Frequency), thu畉t to叩n SVD (Singular Value Decomposition). 2 M畛 r畛ng thu畉t to叩n SVD b畉ng t鱈ch Tensor.

More Related Content

際際滷

  • 1. X叩c 畛nh ph動董ng tr狸nh qu畛 畉o c畛a m畛t ti畛u hnh tinh 畛ng d畛ng c畛a 畉i s畛 tuy畉n t鱈nh trong l箪 thuy畉t 畛 th畛 Khai th叩c vn b畉n v thu h畛i th担ng tin H動畛ng 畛NG D畛NG C畛A 畉I S畛 TUY畉N TNH TRONG KHAI PH D畛 LI畛U m Thanh Ph動董ng, Ng担 M畉nh T動畛ng Ngy 26 th叩ng 12 nm 2012
  • 2. X叩c 畛nh ph動董ng tr狸nh qu畛 畉o c畛a m畛t ti畛u hnh tinh 畛ng d畛ng c畛a 畉i s畛 tuy畉n t鱈nh trong l箪 thuy畉t 畛 th畛 Khai th叩c vn b畉n v thu h畛i th担ng tin H動畛ng N畛I DUNG C畛A SEMINAR 1 X叩c 畛nh ph動董ng tr狸nh c畛a m畛t qu畛 畉o. 2 畛ng d畛ng 畉i s畛 tuy畉n t鱈nh trong l箪 thuy畉t 畛 th畛. 3 畛ng d畛ng 畉i s畛 tuy畉n t鱈nh trong khai th叩c vn b畉n v thu h畛i th担ng tin. 4 M畛t s畛 h動畛ng nghi棚n c畛u.
  • 3. X叩c 畛nh ph動董ng tr狸nh qu畛 畉o c畛a m畛t ti畛u hnh tinh 畛ng d畛ng c畛a 畉i s畛 tuy畉n t鱈nh trong l箪 thuy畉t 畛 th畛 Khai th叩c vn b畉n v thu h畛i th担ng tin H動畛ng Ph動董ng tr狸nh 動畛ng 動畛ng th畉ng i qua hai i畛m Cho 2 i畛m ph但n bi畛t trong m畉t ph畉ng A(x1 ; y1 ) v B(x2 ; y2 ) l . Khi 坦 s畉 t畛n t畉i m畛t 動畛ng th畉ng i qua 2 i畛m A, B c坦 ph動董ng tr狸nh ax + by + c = 0 (1) V狸 A(x1 ; y1 ) v B(x2 ; y2 ) thu畛c 動畛ng th畉ng n棚n n坦 th畛a m達n (1), suy ra ax1 + by1 + c = 0 (2) ax2 + by2 + c = 0 (3) H狸nh: 動畛ng th畉ng qua hai i畛m K畉t h畛p (1), (2), (3) ta 動畛c 錚 錚 ax + by + c = 0 錚 x y 1 ax1 + by1 + c = 0 x1 y1 1 =0 (4) x2 y2 1 錚 ax2 + by2 + c = 0 錚
  • 4. X叩c 畛nh ph動董ng tr狸nh qu畛 畉o c畛a m畛t ti畛u hnh tinh 畛ng d畛ng c畛a 畉i s畛 tuy畉n t鱈nh trong l箪 thuy畉t 畛 th畛 Khai th叩c vn b畉n v thu h畛i th担ng tin H動畛ng Ph動董ng tr狸nh 動畛ng V鱈 d畛 T狸m ph動董ng tr狸nh 動畛ng th畉ng i qua hai i畛m (2; 1) v (3; 7). p d畛ng c担ng th畛c (4) ta c坦 x y 1 2 1 1 =0 3 7 1 V畉y ph動董ng tr狸nh 動畛ng th畉ng c畉n t狸m l 6x + y + 11 = 0
  • 5. X叩c 畛nh ph動董ng tr狸nh qu畛 畉o c畛a m畛t ti畛u hnh tinh 畛ng d畛ng c畛a 畉i s畛 tuy畉n t鱈nh trong l箪 thuy畉t 畛 th畛 Khai th叩c vn b畉n v thu h畛i th担ng tin H動畛ng Ph動董ng tr狸nh 動畛ng tr嘆n 動畛ng tr嘆n i qua ba i畛m Cho 3 i畛m ph但n bi畛t trong m畉t ph畉ng A(x1 ; y1 ), B(x2 ; y2 ) v C (x3 ; y3 ) l . Khi 坦 s畉 t畛n t畉i m畛t 動畛ng tr嘆n i qua 3 i畛m A, B, C c坦 ph動董ng tr狸nh (x a)2 + (y b)2 = R 2 hay a1 x 2 + y 2 + a2 x + a3 y + a4 = 0 (5) V狸 A(x1 ; y1 ), B(x2 ; y2 ), C (x3 ; y3 ) thu畛c 動畛ng tr嘆n n棚n n坦 th畛a m達n (5), suy ra 2 2 a1 x1 + y1 + a2 x1 + a3 y1 + a4 = 0 (6) 2 2 a1 x2 + y2 + a2 x2 + a3 y2 + a4 = 0 (7) 2 2 H狸nh: 動畛ng tr嘆n qua ba i畛m a1 x3 + y3 + a2 x3 + a3 y3 + a4 = 0 (8)
  • 6. X叩c 畛nh ph動董ng tr狸nh qu畛 畉o c畛a m畛t ti畛u hnh tinh 畛ng d畛ng c畛a 畉i s畛 tuy畉n t鱈nh trong l箪 thuy畉t 畛 th畛 Khai th叩c vn b畉n v thu h畛i th担ng tin H動畛ng Ph動董ng tr狸nh 動畛ng tr嘆n 動畛ng tr嘆n i qua ba i畛m K畉t h畛p (5), (6), (7), (8) ta 動畛c x2 + y2 x y 1 2 2 x1 + y1 x1 y1 1 2 2 =0 (9) x2 + y2 x2 y2 1 2 2 x3 + y3 x3 y3 1 Do 坦, v畛i m畛i i畛m (x; y ) n畉m tr棚n m畛t 動畛ng tr嘆n th狸 th畛a m達n 畛nh th畛c (9) v ng動畛c l畉i v畛i m畛i i畛m (x; y ) th畛a m達n 畛nh th畛c (9) 畛u n畉m tr棚n m畛t tr嘆n.
  • 7. X叩c 畛nh ph動董ng tr狸nh qu畛 畉o c畛a m畛t ti畛u hnh tinh 畛ng d畛ng c畛a 畉i s畛 tuy畉n t鱈nh trong l箪 thuy畉t 畛 th畛 Khai th叩c vn b畉n v thu h畛i th担ng tin H動畛ng Ph動董ng tr狸nh 動畛ng tr嘆n V鱈 d畛 T狸m ph動董ng tr狸nh 動畛ng tr嘆n i qua ba i畛m (1; 7), (6; 2) v (4; 6). p d畛ng c担ng th畛c (9) ta c坦 x2 + y2 x y 1 50 1 7 1 =0 40 6 2 1 52 4 6 1 V畉y ph動董ng tr狸nh 動畛ng tr嘆n c畉n t狸m l 2 2 10 x 2 + y 2 20x 40y 200 = 0 hay (x 1) + (y 2) = 52
  • 8. X叩c 畛nh ph動董ng tr狸nh qu畛 畉o c畛a m畛t ti畛u hnh tinh 畛ng d畛ng c畛a 畉i s畛 tuy畉n t鱈nh trong l箪 thuy畉t 畛 th畛 Khai th叩c vn b畉n v thu h畛i th担ng tin H動畛ng Ph動董ng tr狸nh 動畛ng Conic 動畛ng Conic i qua 5 i畛m Ph動董ng tr狸nh t畛ng qu叩t c畛a 動畛ng conic trong m畉t ph畉ng (Parabol, Hyperbol, ellip, c叩c suy bi畉n c畛a 動畛ng cong) a1 x 2 + a2 xy + a3 y 2 + a4 x + a5 y + a6 = 0 (10) Ph動董ng tr狸nh (10) c坦 6 h畛 s畛, ta c坦 th畛 gi畉m c嘆n 5 h畛 s畛 b畉ng c叩ch chia cho m畛t h畛 s畛 kh叩c 0 v nh動 v畉y 畛 畛 x叩c 畛nh 動畛c c叩c h畛 s畛 c畛a n坦 th担ng qua 5 i畛m ph但n bi畛t trong m畉t ph畉ng. T動董ng t畛 nh動 tr棚n ta c滴ng c坦 畛nh th畛c x叩c 畛nh ph動董ng tr狸nh c叩c 動畛ng conic l x2 xy y2 x y 1 2 2 x1 x1 y1 y1 x1 y1 1 2 2 x2 x2 y2 y2 x2 y2 1 2 2 =0 x3 x3 y3 y3 x3 y3 1 2 2 x4 x4 y4 y4 x4 y4 1 2 2 x5 x5 y5 y5 x5 y5 1 (11) H狸nh: 動畛ng conic qua 5 i畛m
  • 9. X叩c 畛nh ph動董ng tr狸nh qu畛 畉o c畛a m畛t ti畛u hnh tinh 畛ng d畛ng c畛a 畉i s畛 tuy畉n t鱈nh trong l箪 thuy畉t 畛 th畛 Khai th叩c vn b畉n v thu h畛i th担ng tin H動畛ng Ph動董ng tr狸nh 動畛ng Conic Ph動董ng tr狸nh c畛a m畛t qu畛 畉o M畛t nh thi棚n vn ng動畛i mu畛n x叩c 畛nh qu畛 畉o c畛a m畛t ti畛u hnh tinh h畛 m畉t tr畛i ph畉i thi畉t l畉p m畛t h畛 th畛ng t畛a 畛 Cartesian trong m畉t ph畉ng qu畛 畉o v畛i m畉t tr畛i t畉i g畛c. 董n v畛 thi棚n vn o l動畛ng 動畛c s畛 d畛ng d畛c theo tr畛c (1 董n v畛 thi棚n vn = kho畉ng c叩ch c畛a tr叩i 畉t v畛i m畉t tr畛i = 93 tri畛u d畉m). Theo quy lu畉t c畛a Kepler, qu畛 畉o ph畉i l m畛t h狸nh elip, do 坦, c叩c nh thi棚n vn c坦 nm quan s叩t c叩c ti畛u hnh tinh t畉i nm th畛i i畛m kh叩c nhau v t狸m 動畛c nm i畛m d畛c theo qu畛 畉o (8, 025; 8, 310), (10, 170; 6, 365), (11, 202; 3, 212), (10, 736; 0, 375) v (9, 092; 2, 267) H狸nh: Qu畛 畉o c畛a ti畛u hnh tinh
  • 10. X叩c 畛nh ph動董ng tr狸nh qu畛 畉o c畛a m畛t ti畛u hnh tinh 畛ng d畛ng c畛a 畉i s畛 tuy畉n t鱈nh trong l箪 thuy畉t 畛 th畛 Khai th叩c vn b畉n v thu h畛i th担ng tin H動畛ng Ph動董ng tr狸nh 動畛ng Conic Ph動董ng tr狸nh c畛a m畛t qu畛 畉o p d畛ng c担ng th畛c (11) ta c坦 ph動董ng tr狸nh c畛a qu畛 畉o l x2 xy y2 x y 1 66, 401 66, 688 69, 056 8, 025 8, 310 1 103, 429 64, 630 40, 386 10, 170 6, 355 1 =0 125, 485 35, 981 10, 317 11, 202 3, 212 1 115, 262 4, 026 0, 141 10, 735 0, 375 1 82, 664 20, 612 5, 139 9, 092 2, 267 1 V畉y ph動董ng tr狸nh qu畛 畉o c畛a ti畛u hnh t狸nh c畉n t狸m l 386, 802x 2 102, 895xy +446, 029y 2 2476, 443x1427, 998y 17109, 375 = 0
  • 11. X叩c 畛nh ph動董ng tr狸nh qu畛 畉o c畛a m畛t ti畛u hnh tinh 畛ng d畛ng c畛a 畉i s畛 tuy畉n t鱈nh trong l箪 thuy畉t 畛 th畛 Khai th叩c vn b畉n v thu h畛i th担ng tin H動畛ng Ph動董ng tr狸nh m畉t ph畉ng Ph動董ng tr狸nh m畉t ph畉ng i qua 3 i畛m Ph動董ng tr狸nh m畉t ph畉ng qua 3 i畛m (x1 , y1 , z1 ), (x2 , y2 , z2 ), (x3 , y3 , z3 ) x叩c 畛nh b畉ng 畛nh th畛c x y z 1 x1 y1 z1 1 =0 (12) x2 y2 z2 1 x3 y3 z3 1 V鱈 d畛. Ph動董ng tr狸nh m畉t ph畉ng qua 3 i畛m (1, 1, 0) ; (2, 0, 1) ; (2, 9, 2) l x y z 1 1 1 0 1 = 0 hay 2x y + 3x 1 = 0 2 0 1 1 2 9 2 1
  • 12. X叩c 畛nh ph動董ng tr狸nh qu畛 畉o c畛a m畛t ti畛u hnh tinh 畛ng d畛ng c畛a 畉i s畛 tuy畉n t鱈nh trong l箪 thuy畉t 畛 th畛 Khai th叩c vn b畉n v thu h畛i th担ng tin H動畛ng Ph動董ng tr狸nh m畉t c畉u Ph動董ng tr狸nh m畉t c畉u i qua 4 i畛m Ph動董ng tr狸nh m畉t c畉u qua 4 i畛m (x1 , y1 , z1 ), (x2 , y2 , z2 ), (x3 , y3 , z3 ), (x4 , y4 , z4 ) c坦 d畉ng x2 + y2 + z2 x y z 1 2 2 2 x1 + y1 + z1 x1 y1 z1 1 2 2 2 x2 + y2 + z2 x2 y2 z2 1 =0 (13) 2 2 2 x3 + y3 + z3 x3 y3 z3 1 2 2 2 x4 + y4 + z4 x4 y4 z4 1
  • 13. X叩c 畛nh ph動董ng tr狸nh qu畛 畉o c畛a m畛t ti畛u hnh tinh 畛ng d畛ng c畛a 畉i s畛 tuy畉n t鱈nh trong l箪 thuy畉t 畛 th畛 Khai th叩c vn b畉n v thu h畛i th担ng tin H動畛ng Ph動董ng tr狸nh m畉t c畉u V鱈 d畛 Ph動董ng tr狸nh m畉t c畉u qua 4 i畛m (0, 3, 2) , (1, 1, 1) , (2, 1, 0) , (5, 1, 3) l x2 + y2 + z2 x y z 1 13 0 3 2 1 3 1 1 1 1 =0 5 2 1 0 1 35 5 1 3 1 hay x 2 + y 2 + z 2 4x 2y 6z + 5 = 0 hay 2 2 2 (x 2) + (y 1) + (z 3) = 9
  • 14. X叩c 畛nh ph動董ng tr狸nh qu畛 畉o c畛a m畛t ti畛u hnh tinh 畛ng d畛ng c畛a 畉i s畛 tuy畉n t鱈nh trong l箪 thuy畉t 畛 th畛 Khai th叩c vn b畉n v thu h畛i th担ng tin H動畛ng M畛i quan h畛 trong gia 狸nh M畛i quan h畛 trong gia 狸nh V畛i m畛t 畛 th畛 c坦 h動畛ng g畛m n 畛nh P1 , P2 , ..., Pn , ta c坦 m畛t ma tr畉n M = [mij ]nn , g畛i l ma tr畉n 畛nh, trong 坦 1 n畉u Pi Pj mij = 0 v畛i c叩c tr動畛ng h畛p kh叩c Ma tr畉n 畛nh l 錚 錚 0 1 0 0 1 錚 0 0 1 1 0 錚 錚 錚 M=錚 0錚 0 0 1 0 錚 錚 錚 0 1 0 0 1 錚 0 1 1 0 0
  • 15. X叩c 畛nh ph動董ng tr狸nh qu畛 畉o c畛a m畛t ti畛u hnh tinh 畛ng d畛ng c畛a 畉i s畛 tuy畉n t鱈nh trong l箪 thuy畉t 畛 th畛 Khai th叩c vn b畉n v thu h畛i th担ng tin H動畛ng M畛i quan h畛 trong gia 狸nh M畛i quan h畛 trong gia 狸nh M畛t gia 狸nh g畛m b畛, m畉, con g叩i v hai con trai. C叩c thnh vi棚n trong gia 狸nh c坦 t畉m 畉nh h動畛ng 畉n m畛i thnh vi棚n kh叩c nh動: m畉 c坦 t畉m 畉nh h動畛ng v畛i con g叩i v con trai l畛n tu畛i nh畉t; b畛 c坦 t畉m 畉nh h動畛ng v畛i hai con trai; con g叩i c坦 th畛 畉nh h動畛ng 畉n ng動畛i cha; 畛a con trai l畛n c坦 th畛 畉nh h動畛ng 畉n 畛a em 炭t; v 畛a em 炭t th狸 c坦 畉nh h動畛ng 畉n ng動畛i m畉. Ch炭ng ta c坦 th畛 m担 h狸nh m畛i quan h畛 gia 狸nh v畛i m畛t 畛 th畛 c坦 畛nh l nm thnh vi棚n trong gia 狸nh 坦. Ma tr畉n 畛nh l 錚M F D OS YS錚 M 0 0 1 1 0 F 錚 0 0 0 1 錚 1 錚 錚 D 錚 0 1 0 0 錚 0 錚 錚 OS 錚 0 0 0 0 1 錚 YS 1 0 0 0 0
  • 16. X叩c 畛nh ph動董ng tr狸nh qu畛 畉o c畛a m畛t ti畛u hnh tinh 畛ng d畛ng c畛a 畉i s畛 tuy畉n t鱈nh trong l箪 thuy畉t 畛 th畛 Khai th叩c vn b畉n v thu h畛i th担ng tin H動畛ng M畛i quan h畛 trong gia 狸nh M畛i quan h畛 trong gia 狸nh Ma tr畉n 畛nh l 錚M F D OS YS錚 M 0 0 1 1 0 F 錚 0 0 0 1 錚 1 錚 錚 D 錚 0 1 0 0 錚 0 錚 錚 OS 錚 0 0 0 0 1 錚 YS 1 0 0 0 0 畛 但y ng動畛i cha kh担ng 畉nh h動畛ng tr畛c ti畉p 畉n ng動畛i m畉, nh動ng l畉i 畉nh h動畛ng 畉n con 炭t, ng動畛i 畉nh h動畛ng 畉n ng動畛i m畉 F YS M v ta c坦 k畉t n畛i 2 b動畛c t畛 F 畉n M. Nh狸n tr棚n h狸nh v畉 ta c坦 M D l k畉t n畛i 1 b動畛c , F OS YS M c坦 k畉t n畛i 3 b動畛c .
  • 17. X叩c 畛nh ph動董ng tr狸nh qu畛 畉o c畛a m畛t ti畛u hnh tinh 畛ng d畛ng c畛a 畉i s畛 tuy畉n t鱈nh trong l箪 thuy畉t 畛 th畛 Khai th叩c vn b畉n v thu h畛i th担ng tin H動畛ng S畛 k畉t n畛i r b動畛c S畛 k畉t n畛i r b動畛c T畛 v鱈 d畛 tr棚n ta x但y d畛ng c担ng th畛c t狸m s畛 k畉t n畛i r b動畛c (r = 1, 2, ...) t畛 畛nh Pi t畛i 畛nh Pj c畛a m畛t 畛 th畛 c坦 h動畛ng. S畛 k畉t n畛i 1 b動畛c t畛 Pi t畛i Pj l mij , ta th畉y n坦 kh担ng c坦 ho畉c c坦 1 k畉t n畛i Pi Pj ph畛 thu畛c vo mij = 0 hay mij = 1. V畛i s畛 k畉t n畛i 2 b動畛c t畛 ma tr畉n 狸nh M ta t鱈nh M 2 , khi 坦 (2) mij = mi1 m1j + mi2 m2j + 揃 揃 揃 + min mnj N畉u mi1 = m1j = 1 th狸 c坦 m畛t k畉t n畛i 2 b動畛c t畛 Pi P1 Pj . N畉u mi1 = 0 ho畉c m1j = 0 th狸 kh担ng c坦 k畉t n畛i 2 b動畛c ny. V畉y Pi P1 Pj l m畛t k畉t n畛i 2 b動畛c khi v ch畛 khi mi1 m1j = 1. T動董ng t畛 v畛i Pi Pk Pj v畛i k = 1, 2, ... l m畛t k畉t n畛i 2 b動畛c khi v chi khi mik mkj = 1. T畛ng qu叩t ta c坦 k畉t qu畉 sau: 畛nh l箪 (r ) Cho M l ma tr畉n 畛nh c畛a m畛t 畛 th畛 c坦 h動畛ng v mij l ph畉n t畛 th畛 (r ) (i, j) c畛a M r . Khi 坦 mij l s畛 li棚n k畉t r b動畛c t畛 Pi t畛i Pj .
  • 18. X叩c 畛nh ph動董ng tr狸nh qu畛 畉o c畛a m畛t ti畛u hnh tinh 畛ng d畛ng c畛a 畉i s畛 tuy畉n t鱈nh trong l箪 thuy畉t 畛 th畛 Khai th叩c vn b畉n v thu h畛i th担ng tin H動畛ng S畛 k畉t n畛i r b動畛c L畛 tr狸nh c畛a m叩y bay H狸nh tr棚n l b畉n 畛 l畛 tr狸nh c畛a m畛t h達ng hng kh担ng nh畛 ph畛c v畛 cho b畛n thnh ph畛 P1 , P2 , P3 , P4 D畛a vo b畉n 畛 l畛 tr狸nh, ta c坦 ma tr畉n 畛nh l 錚 錚 錚 錚 0 1 1 0 2 0 1 1 錚 1 0 1 0 錚 2 錚 1 1 1 1 錚 M=錚 錚 1 0 0 錚,M = 錚 錚 1 錚 錚 0 2 2 0 錚 0 1 1 0 2 0 1 1 錚 錚 1 3 3 1 3 錚 2 2 3 1 錚 M =錚 錚 4 0 2 錚 T畛 c叩c ma tr畉n ta th畉y 2 錚 1 3 3 1 m43 = 1 c坦 1 k畉t n畛i 1 b動畛c: P4 P3 (2) m43 = 1 c坦 1 k畉t n畛i 2 b動畛c: P4 P2 P3 (3) m43 = 3 c坦 3 k畉t n畛i 3 b動畛c: P4 P3 P4 P3 , P4 P2 P1 P3 , P4 P3 P1 P3
  • 19. X叩c 畛nh ph動董ng tr狸nh qu畛 畉o c畛a m畛t ti畛u hnh tinh 畛ng d畛ng c畛a 畉i s畛 tuy畉n t鱈nh trong l箪 thuy畉t 畛 th畛 Khai th叩c vn b畉n v thu h畛i th担ng tin H動畛ng Clique c畛a 畛 th畛 Clique c畛a 畛 th畛 N畉u coi c叩c Pi l c叩c 畛nh c畛a m畛t 畛 th畛 c坦 h動畛ng v g畛i S = [sij ]nn , 1 n畉u Pi Pj trong 坦 sij = ta c坦 k畉t qu畉 sau: 0 v畛i c叩c tr動畛ng h畛p kh叩c 畛nh l箪 (3) Gi畉 s畛 sij l ph畉n t畛 th畛 (i, j) c畛a S 3 , khi 坦 畛nh Pi thu畛c c叩c Clique (3) n畉u v ch畛 n畉u sii = 0 V鱈 d畛 1: Gi畉 s畛 m畛t 畛 th畛 c坦 h動畛ng c坦 ma tr畉n 畛nh 錚 錚 錚 錚 錚 錚 0 1 1 1 0 1 0 1 0 3 0 2 錚 1 0 1 0 錚 錚 1 0 1 0 錚 3 錚 3 0 2 0 錚 M=錚 錚 0 1 0 1 錚獅S =錚 0 錚 錚 錚,S = 錚 錚 1 0 0 錚 錚 0 2 0 1 錚 1 0 0 0 1 0 0 0 2 0 1 0 Ta th畉y c叩c ph畉n t畛 n畉m tr棚n 動畛ng ch辿o ch鱈nh c畛a S 3 畛u b畉ng 0 n棚n 畛 th畛 kh担ng c坦 Clique.
  • 20. X叩c 畛nh ph動董ng tr狸nh qu畛 畉o c畛a m畛t ti畛u hnh tinh 畛ng d畛ng c畛a 畉i s畛 tuy畉n t鱈nh trong l箪 thuy畉t 畛 th畛 Khai th叩c vn b畉n v thu h畛i th担ng tin H動畛ng Clique c畛a 畛 th畛 V鱈 d畛 2: Gi畉 s畛 m畛t 畛 th畛 c坦 h動畛ng c坦 ma tr畉n 畛nh 錚 錚 錚 錚 0 1 0 1 1 0 1 0 1 1 錚 1 0 0 1 0 錚 錚 1 0 0 1 0 錚 錚 錚 錚 錚 M=錚 1 1 0 1 0 錚財S =錚 錚 錚 錚 0 0 0 0 0 錚 錚 錚 1 1 0 0 0 錚 錚 1 1 0 0 0 錚 1 0 0 1 0 1 0 0 0 0 suy ra 錚 錚 2 4 0 4 3 錚 4 2 0 3 1 錚 3 錚 錚 S =錚 錚 0 0 0 0 0 錚 錚 錚 4 3 0 2 1 錚 3 1 0 1 0 (3) (3) (3) Ta c坦 s11 = 0, s22 = 0, s44 = 0, suy ra c叩c 畛nh P1 , P2 , P3 thu畛c Clique v 畛 thi ch畛 c坦 1 Clique l {P1 , P2 , P3 }.
  • 21. X叩c 畛nh ph動董ng tr狸nh qu畛 畉o c畛a m畛t ti畛u hnh tinh 畛ng d畛ng c畛a 畉i s畛 tuy畉n t鱈nh trong l箪 thuy畉t 畛 th畛 Khai th叩c vn b畉n v thu h畛i th担ng tin H動畛ng B畉c c畛a m畛t 畛nh B畉c c畛a m畛t 畛nh Gi畉 s畛 5 畛i b坦ng 叩 g畉p nhau 炭ng m畛t l畉n v k畉t qu畉 動畛c th畛 hi畛n tr棚n 畛 th畛 c坦 h動畛ng Ma tr畉n 畛nh l 錚 錚 0 0 1 1 0 錚 錚 1 0 1 0 1 錚 錚 M=錚 錚 0 0 0 1 0 錚 錚 錚 0 1 0 0 0 錚 1 0 1 1 0 T狸m th畛 h畉ng c畛a 5 畛i b坦ng tr棚n? Vi畛c gi畉i bi to叩n tr棚n l vi畛c x畉p b畉c c畛a c叩c 畛nh tr棚n 畛 th畛 c坦 h動畛ng. Ta c坦 k畉t qu畉 sau:
  • 22. X叩c 畛nh ph動董ng tr狸nh qu畛 畉o c畛a m畛t ti畛u hnh tinh 畛ng d畛ng c畛a 畉i s畛 tuy畉n t鱈nh trong l箪 thuy畉t 畛 th畛 Khai th叩c vn b畉n v thu h畛i th担ng tin H動畛ng B畉c c畛a m畛t 畛nh B畉c c畛a m畛t 畛nh 畛nh l箪 B畉c c畛a m畛t 畛nh trong 畛 th畛 c坦 h動畛ng l t畛ng s畛 c叩c k畉t n畛i 1 b動畛c v k畉t n畛i 2 b動畛c c畛a n坦 v畛i c叩c 畛nh kh叩c. Do 坦 b畉c c畛a 畛nhPi l t畛ng c叩c s畛 h畉ng 畛 hng th畛 i c畛a ma tr畉n A = M + M 2 . V畉y t畛 ma tr畉n M ta c坦 A=M + M2 = 錚 錚 錚 錚 錚 錚 0 0 1 1 0 0 1 0 1 0 0 1 1 2 0 錚 錚 1 0 1 0 1 錚 錚 1 0 錚 錚 2 3 0 錚 錚 錚 錚 2 0 3 3 1 錚 錚 =錚 錚 0 0 0 1 0 錚+錚 0 1 錚 錚 0 0 0 錚=錚 錚 錚 0 1 0 1 0 錚 錚 錚 0 1 0 0 0 錚 錚 1 0 1 0 1 錚 錚 1 1 1 0 1 錚 1 0 1 1 0 0 1 1 2 0 1 1 2 3 0 V畉y th畛 t畛 c叩c 畛i b坦ng l : Nh畉t 畛i 2, nh狸 畛i 5, ba c坦 2 畛i 4 v 1, cu畛i b畉ng l 畛i 3.
  • 23. X叩c 畛nh ph動董ng tr狸nh qu畛 畉o c畛a m畛t ti畛u hnh tinh 畛ng d畛ng c畛a 畉i s畛 tuy畉n t鱈nh trong l箪 thuy畉t 畛 th畛 Khai th叩c vn b畉n v thu h畛i th担ng tin H動畛ng C叩c b動畛c ti畉n hnh v thu畉t to叩n Khai th叩c vn b畉n l g狸? C叩c ph動董ng ph叩p 畛 chi畉t xu畉t c叩c th担ng tin h畛u 鱈ch t畛 c董 s畛 d畛 li畛u l畛n v th動畛ng kh担ng 動畛c c畉u tr炭c. Thu h畛i th担ng tin. T狸m ki畉m trong c董 s畛 d畛 li畛u v畛i m畛t truy v畉n b畉ng m畛t b畛 t畛 kh坦a, t狸m 畛 t畉t c畉 c叩c ti li畛u c坦 li棚n quan. S畛 d畛ng c叩c c担ng c畛 c坦 s畉n (SAS Text Miner, Statistics Text-mining toolbox...)
  • 24. X叩c 畛nh ph動董ng tr狸nh qu畛 畉o c畛a m畛t ti畛u hnh tinh 畛ng d畛ng c畛a 畉i s畛 tuy畉n t鱈nh trong l箪 thuy畉t 畛 th畛 Khai th叩c vn b畉n v thu h畛i th担ng tin H動畛ng C叩c b動畛c ti畉n hnh v thu畉t to叩n C叩c b動畛c th畛c hi畛n 1 Chu畉n b畛 ti li畛u. 2 X但y d畛ng ma tr畉n ti li畛u. 3 Truy v畉n d畛 li畛u b畉ng c叩ch o kho畉ng c叩ch. 4 N辿n d畛 li畛u b畉ng x畉p x畛 th畛 h畉ng th畉p : Thu畉t to叩n SVD (The Singular Value Decomposition). 5 X畉p h畉n v ph畉n h畛i.
  • 25. X叩c 畛nh ph動董ng tr狸nh qu畛 畉o c畛a m畛t ti畛u hnh tinh 畛ng d畛ng c畛a 畉i s畛 tuy畉n t鱈nh trong l箪 thuy畉t 畛 th畛 Khai th叩c vn b畉n v thu h畛i th担ng tin H動畛ng V鱈 d畛 V鱈 d畛
  • 26. X叩c 畛nh ph動董ng tr狸nh qu畛 畉o c畛a m畛t ti畛u hnh tinh 畛ng d畛ng c畛a 畉i s畛 tuy畉n t鱈nh trong l箪 thuy畉t 畛 th畛 Khai th叩c vn b畉n v thu h畛i th担ng tin H動畛ng V鱈 d畛 V鱈 d畛 Ma tr畉n ti li畛u 錚 錚 0 1 0 1 1 0 1 錚 錚 0 1 1 0 0 0 0 錚 錚 錚 錚 0 0 0 0 0 1 1 錚 錚 錚 錚 0 0 0 1 0 0 0 錚 錚 A=錚 錚 0 1 1 0 0 0 0 錚 錚 錚 錚 1 0 0 1 0 0 0 錚 錚 錚 錚 0 0 0 0 1 1 0 錚 錚 錚 0 0 1 1 0 0 0 錚 1 0 0 1 0 0 0 Trong 坦 Aij l t畉n s畛 tr畛ng s畛 c畛a thu畉t ng畛 th畛 i trong ti li畛u j.
  • 27. X叩c 畛nh ph動董ng tr狸nh qu畛 畉o c畛a m畛t ti畛u hnh tinh 畛ng d畛ng c畛a 畉i s畛 tuy畉n t鱈nh trong l箪 thuy畉t 畛 th畛 Khai th叩c vn b畉n v thu h畛i th担ng tin H動畛ng V鱈 d畛 V鱈 d畛 Chu畉n h坦a ma tr畉n ti li畛u 錚 錚 0 0, 577 0 0, 447 0, 707 0 0, 707 錚 0 0, 577 0, 577 0 0 0 0 錚 錚 錚 錚 0 0 0 0 0 0, 707 0, 707 錚 錚 錚 錚 0 0 0 0, 447 0 0 0 錚 錚 錚 A= 錚 0 錚 0, 577 0, 577 0 0 0 0 錚 錚 錚 0, 707 0 0 0, 447 0 0 0 錚 錚 錚 錚 0 0 0 0 0, 707 0, 707 0 錚 錚 錚 錚 0 0 0, 577 0, 447 0 0 0 錚 0, 707 0 0 0, 447 0 0 0
  • 28. X叩c 畛nh ph動董ng tr狸nh qu畛 畉o c畛a m畛t ti畛u hnh tinh 畛ng d畛ng c畛a 畉i s畛 tuy畉n t鱈nh trong l箪 thuy畉t 畛 th畛 Khai th叩c vn b畉n v thu h畛i th担ng tin H動畛ng V鱈 d畛 Truy v畉n Gi畉 s畛 c坦 m畛t truy v畉n vecto q, t狸m c叩c c畛t ai c畛a ma tr畉n A sao cho dist (q, ai ) tol (14) trong 坦 錚 錚 x y 錚 2, Chu畉n kho畉ng c叩ch Euclidean 錚 錚 xT y 錚 dist (q, ai ) = (15) 錚 1 cos (慮 (x, y )) = 1 x 2 y 2 錚 錚 錚 錚 arccos (慮 (x, y ))
  • 29. X叩c 畛nh ph動董ng tr狸nh qu畛 畉o c畛a m畛t ti畛u hnh tinh 畛ng d畛ng c畛a 畉i s畛 tuy畉n t鱈nh trong l箪 thuy畉t 畛 th畛 Khai th叩c vn b畉n v thu h畛i th担ng tin H動畛ng V鱈 d畛 Truy v畉n: child home safety 錚 錚 錚 錚 0 0 錚 1 錚 錚 0, 577 錚 T畛 (14), (15) ta c坦 錚 錚 錚 錚 錚 0 錚 錚 0 錚 錚 錚 錚 錚 錚 0 錚 錚 0 錚 xT y 錚 錚 錚 錚 1 錚 , q = 錚 0, 577 錚 錚 cos (慮 (x, y )) = tol q=錚 錚 錚 錚 x 2 y 2 錚 0 錚 錚 0 錚 錚 錚 錚 錚 錚 0 錚 錚 0 錚 trong 坦 x = 1, y = 1 錚 錚 錚 錚 錚 1 錚 錚 0, 577 錚 0 0 Khi 坦 ta c坦 cosin c叩c c畛t c畛a A l qT A = 0 0, 667 1 0, 258 0 0 0 suy ra 1 cos (慮 (x, y )) c叩c c畛t c畛a A l 1 0, 333 0 0, 742 1 1 1 V畛i m畛c tol = 0, 5 ta c坦 hai ti li畛u 2, 3 th畛a m達n.
  • 30. X叩c 畛nh ph動董ng tr狸nh qu畛 畉o c畛a m畛t ti畛u hnh tinh 畛ng d畛ng c畛a 畉i s畛 tuy畉n t鱈nh trong l箪 thuy畉t 畛 th畛 Khai th叩c vn b畉n v thu h畛i th担ng tin H動畛ng H動畛ng nghi棚n c畛u 1 畛ng d畛ng c畛a 畉i s畛 tuy畉n t鱈nh trong nh畉n d畉ng ch畛 vi畉t tay v畛i m畛t s畛 thu畉t to叩n TFIDF (TF = Term Frequency, IDF = Inverse Document Frequency), thu畉t to叩n SVD (Singular Value Decomposition). 2 M畛 r畛ng thu畉t to叩n SVD b畉ng t鱈ch Tensor.