Luận án Học máy, học máy mô tả phức: thuật toán và vấn đề rút gọn lỗi

thÝch hîp t¨ng lªn. Nh− vËy, c¸ch tiÕp cËn m« h×nh phøc thùc sù tèt khi cã nhiÒu liªn kÕt t¨ng lªn. Ali K. & Pazzani M. [5] kÕt luËn r»ng, nh©n tè c¬ b¶n trong viÖc gi¶i thÝch ph−¬ng sai cña gi¶m lçi lµ xu h−íng cña c¸c m« h×nh ®−îc häc ®Ó t¹o ra c¸c lçi t−¬ng quan. MÆt kh¸c, c¸c t¸c gi¶ ®· cè g¾ng t¨ng sè l−îng cña c¸c liªn kÕt ®èi víi mçi tËp hîp d÷ liÖu b»ng c¸ch bæ sung thªm mét sè thuéc tÝnh kh«ng thÝch hîp cho víi mçi tËp hîp d÷ liÖu. §iÒu nµy lµm t¨ng sè l−îng cña c¸c liªn kÕt t¨ng lªn ®−îc biÕt vµ còng t¹o ra sù gi¶m lçi m¹nh h¬n. L−¬ng Song V©n Häc m¸y, häc m¸y m« t¶ phøc: thuËt to¸n vµ vÊn ®Ò rót gän lçi -64- Ch−¬ng 4. thuËt to¸n t×m kiÕm vµ ph©n líp trong c¬ së d÷ liÖu full-text IV.1. c¬ së d÷ liÖu full-text IV.1.1 Kh¸i niÖm vÒ c¬ së d÷ liÖu full-text C¸c m« h×nh d÷ liÖu ®iÓn h×nh lµ m« h×nh ph©n cÊp, m« h×nh m¹ng vµ m« h×nh quan hÖ ®−îc biÕt nh− nh÷ng m« h×nh d÷ liÖu cã cÊu tróc: d÷ liÖu trong hÖ thèng ®−îc liªn kÕt nhau theo mçi cÊu tróc t−¬ng øng. CÊu tróc hÖ thèng cho biÕt mèi liªn hÖ lÉn nhau gi÷a c¸c ®èi t−îng trong ph¹m vi xem xÐt. Ch¼ng h¹n, trong m« h×nh quan hÖ, th«ng tin vÒ c¸c ®èi t−îng d÷ liÖu ®−îc tr×nh bµy d−íi d¹ng b¶ng, c¸c ®èi t−îng d÷ liÖu cã sù t−¬ng øng ®ång nhÊt nhau theo c¸c tr−êng th«ng tin chung cho b¶ng. Tuy nhiªn, ®èi víi nhiÒu hÖ thèng th«ng tin, kh«ng ph¶i lu«n lu«n biÓu diÔn ®−îc toµn bé d÷ liÖu theo nh÷ng cÊu tróc ®· cã. Ch¼ng h¹n, kh«ng thÓ x©y dùng ®−îc mét cÊu tróc nh»m biÓu diÔn ®èi t−îng th«ng tin v¨n b¶n, h×nh ¶nh. D¹ng th«ng tin nh− vËy ®−îc gäi lµ th«ng tin phi cÊu tróc; nã cã thÓ lµ mét h×nh vÏ, mét v¨n b¶n, d÷ liÖu multimedia v.v. C¬ së d÷ liÖu qu¶n lý th«ng tin phi cÊu tróc ®−îc gäi lµ c¬ së d÷ liÖu phi cÊu tróc. Th«ng th−êng, th«ng tin trong mét c¬ së d÷ liÖu phi cÊu tróc bao gåm hai phÇn: phÇn cã cÊu tróc chøa ®ùng th«ng tin chung nhÊt vÒ toµn bé ®èi t−îng (do t×m ®−îc cÊu tróc biÓu diÔn chóng) vµ phÇn phi cÊu tróc chøa ®ùng th«ng tin riªng vÒ tõng ®èi t−îng. D÷ liÖu d¹ng full-text lµ mét d¹ng d÷ liÖu phi cÊu tróc víi th«ng tin v¨n b¶n d¹ng text. Mçi v¨n b¶n chøa th«ng tin vÒ mét vÊn ®Ò nµo ®ã ®−îc thÓ hiÖn qua néi dung cña tÊt c¶ c¸c tõ cÊu thµnh v¨n b¶n ®ã vµ c¸ch liªn kÕt c¸c tõ nµy. ý nghÜa cña mét tõ trong v¨n b¶n kh«ng cè ®Þnh mµ tïy thuéc vµo tõng ng÷ c¶nh: ng÷ c¶nh kh¸c nhau sÏ cho ý nghÜa kh¸c nhau. C¸c tõ trong v¨n b¶n l¹i ®−îc liªn kÕt víi nhau bëi ng«n ng÷ tr×nh bµy ®ã. §Ó cã thÓ hiÓu ®−îc nghÜa cña v¨n b¶n kh«ng nh÷ng cÇn ph¶i hiÓu ®−îc néi dung cña c¸c tõ mµ cßn ph¶i n¾m L−¬ng Song V©n Häc m¸y, häc m¸y m« t¶ phøc: thuËt to¸n vµ vÊn ®Ò rót gän lçi -65- ®−îc ng÷ ph¸p cña ng«n ng÷ ®ã. §iÒu nµy ®èi víi con ng−êi lµ kh¸ ®¬n gi¶n bëi chÝnh hä t¹o ra ng«n ng÷ vµ c¸c v¨n b¶n ®ã ®Ó tr×nh bµy vÊn ®Ò. Tuy nhiªn viÖc lËp tr×nh ®Ó lµm cho m¸y tÝnh hiÓu ®−îc néi dung cña mét v¨n b¶n khi tiÕp nhËn v¨n b¶n ®ã th× l¹i lµ mét vÊn ®Ò hÕt søc phøc t¹p. HÖ c¬ së d÷ liÖu Full-text qu¶n lý c¸c v¨n b¶n Full-text vµ tæ chøc t×m kiÕm theo néi dung (liªn quan ®Õn phÇn phi cÊu tróc cña hÖ thèng). Ng−êi sö dông ®−a ra néi dung cÇn t×m vµ hÖ thèng sÏ tr¶ l¹i c¸c v¨n b¶n cã néi dung liªn quan. Nh− vËy hÖ thèng ph¶i n¾m b¾t ®−îc néi dung cña mäi v¨n b¶n, hay t−¬ng øng, hÖ c¬ së d÷ liÖu Full-text ph¶i cã mét hÖ thèng ®o¸n nhËn ®−îc ng«n ng÷ diÔn ®¹t v¨n b¶n ®ã. HÖ thèng nµy lµ riªng biÖt ®èi víi mçi ng«n ng÷ vµ thùc hiÖn ®−îc ®iÒu nµy lµ hÕt søc khã kh¨n vµ tèn kÐm. Mét c¸ch lµm kh¸c ®Ó n¾m b¾t néi dung cña v¨n b¶n lµ th«ng qua viÖc n¾m b¾t c¸c tõ vµ côm tõ trong v¨n b¶n ®ã theo h−íng suy nghÜ lµ c¸c tõ trong v¨n b¶n còng ph¶n ¸nh phÇn nµo ý nghÜa cña néi dung v¨n b¶n. C¸ch nµy kÐm chÝnh x¸c h¬n nh−ng cã ®é phøc t¹p võa ph¶i ®Ó cã thÓ gi¶i quyÕt ®−îc mµ Ýt tèn kÐm h¬n vÒ thêi gian còng nh− vÒ c«ng søc. Trong mçi ng«n ng÷, sè c¸c tõ cã nghÜa lµ h÷u h¹n, v× vËy, thay v× ph¶i qu¶n lý toµn bé néi dung v¨n b¶n, ng−êi ta chØ qu¶n lý c¸c tõ cã nghÜa ®−îc dïng ®Ó thÓ hiÖn néi dung v¨n b¶n ®ã. §Æc biÖt, nÕu nh− hÖ thèng qu¶n lý c¸c v¨n b¶n liªn quan ®Õn mét lÜnh vùc ho¹t ®éng riªng biÖt th× danh s¸ch c¸c tõ cÇn qu¶n lý ®−îc giíi h¹n theo c¸c tõ cã nghÜa thuéc lÜnh vùc ho¹t ®éng riªng biÖt ®ã vµ v× vËy, kÝch th−íc th«ng tin qu¶n lý sÏ nhá. Néi dung cÇn t×m còng ®−îc thÓ hiÖn th«ng qua c¸c tõ hoÆc côm tõ. VÒ mÆt thùc tÕ, do tÝnh dÔ thùc hiÖn, ng−êi ta hay dïng c¸ch nµy ®Ó x©y dùng hÖ CSDL full-text vµ ®ang t×m c¸ch c¶i tiÕn chóng ®Ó ®¹t ®−îc kÕt qu¶ tèt h¬n. Ngoµi chøc n¨ng qu¶n lý vµ t×m kiÕm c¸c v¨n b¶n theo néi dung, hÖ CSDL full-text cÇn cã chøc n¨ng ph©n líp c¸c v¨n b¶n theo mét sè mÉu ®· ®Þnh s½n (®−îc gäi lµ catalog v¨n b¶n, mçi líp ®−îc gäi lµ mét catalog). Dùa trªn mét sè líp v¨n b¶n ®· ®−îc ®Þnh s½n theo c¸c v¨n b¶n mÉu cña tõng líp v¨n b¶n, thuËt L−¬ng Song V©n Häc m¸y, häc m¸y m« t¶ phøc: thuËt to¸n vµ vÊn ®Ò rót gän lçi -66- to¸n ph©n líp sÏ ®−îc thùc hiÖn khi hÖ thèng cã thªm mét v¨n b¶n míi. KÕt hîp hai thuËt to¸n ph©n líp vµ t×m kiÕm sÏ cho t¸c dông thu hÑp lÜnh vùc t×m kiÕm v¨n b¶n vµ do ®ã, viÖc t×m kiÕm sÏ chÝnh x¸c h¬n. Ng−êi dïng sÏ nhËn ®−îc c¸c v¨n b¶n trong ph¹m vi catalog ®· chän ra vµ nh− vËy tr¸nh ®−îc t×nh tr¹ng viÖc t×m kiÕm ph¶i x¶y ra trªn toµn bé d÷ liÖu cña hÖ thèng. IV.1.2. C¸c néi dung c¬ b¶n cña mét c¬ së d÷ liÖu full-text a/ L−u tr÷ v¨n b¶n V¨n b¶n lµ ®èi t−îng qu¶n lý chÝnh cña hÖ thèng. B¶n th©n c¸c v¨n b¶n ch¾c ch¾n ph¶i ®−îc l−u gi÷ t¹i mét n¬i nµo ®ã ë bªn trong hoÆc bªn ngoµi hÖ thèng vµ c¸c th«ng tin vÒ chóng ®−îc qu¶n lý tuú thuéc vµo thuËt to¸n l−u tr÷ vµ t×m kiÕm. Cã hai c¸ch l−u tr÷ v¨n b¶n sau ®©y: L−u tr÷ trùc tiÕp C¸c v¨n b¶n ®−îc l−u tr÷ trùc tiÕp trong cét cña mét b¶ng nh− lµ mét tr−êng cña b¶ng ®ã. Khi ®ã mét v¨n b¶n gåm c¸c thuéc tÝnh sau: • Kho¸ (m·) v¨n b¶n • Néi dung v¨n b¶n: l−u trùc tiÕp néi dung cña v¨n b¶n. Theo c¸ch nµy, v¨n b¶n thùc chÊt lµ mét tr−êng cã kiÓu TEXT trong mét b¶ng. Ch¼ng h¹n, néi dung v¨n b¶n ®−îc chØ dÉn tõ tr−êng memo trong file d÷ liÖu cña FOXPRO lµ mét biÕn d¹ng cña c¸ch nµy. • C¸c th«ng tin kh¸c vÒ v¨n b¶n nh− ngµy truy nhËp, ®é dµi cña v¨n b¶n. C¸c th«ng tin nµy kh«ng cã t¸c dông trong qu¸ tr×nh t×m kiÕm theo néi dung mµ chØ bæ sung cho ng−êi dïng mét sè th«ng tin vÒ mét v¨n b¶n x¸c ®Þnh. L−u tr÷ gi¸n tiÕp V¨n b¶n kh«ng ®−îc l−u tr÷ trùc tiÕp bªn trong CSDL mµ ®−îc l−u t¹i mét n¬i nµo ®ã ë bªn ngoµi CSDL. ViÖc qu¶n lý c¸c v¨n b¶n sÏ th«ng qua ®Þa chØ cña nã. §Þa chØ cã thÓ lµ: • §−êng dÉn ®Õn mét file L−¬ng Song V©n Häc m¸y, häc m¸y m« t¶ phøc: thuËt to¸n vµ vÊn ®Ò rót gän lçi -67- • §Þa chØ URL trá ®Õn mét trang Web • §−êng dÉn ®Õn mét tr−êng d¹ng Text trong mét CSDL kh¸c. NÕu d÷ liÖu ®−îc l−u vµo mét file th× ph¶i chó ý ®Õn kh¶ n¨ng truy cËp ®Õn file ®ã, ®Þa chØ sÏ gåm: • Tªn file • N¬i ®Æt file: ph¶i ®Æt t¹i n¬i mµ ch−¬ng tr×nh thùc hiÖn cã thÓ truy cËp ®Õn ®−îc. Th«ng th−êng ng−êi ta hay sö dông theo ph−¬ng ph¸p l−u tr÷ ngoµi v× khi ®ã, mét mÆt, kh«ng bÞ h¹n chÕ vÒ ®é dµi v¨n b¶n l−u tr÷, vµ mÆt kh¸c, cho phÐp më réng ph¹m vi l−u tr÷ v¨n b¶n trªn m¹ng tïy ý. Trong c¸ch thøc nµy, th«ng tin vÒ mét v¨n b¶n gåm: • M· v¨n b¶n, • Con trá trá ®Õn n¬i chøa v¨n b¶n hay th«ng tin vÒ ®Þa chØ cña mét file, • C¸c th«ng tin vÒ néi dung v¨n b¶n ®Ó cã thÓ tiÕn hµnh t×m kiÕm chóng, • Ngoµi ra cßn cã mét sè th«ng tin phô vÒ v¨n b¶n ®ã nh− ngµy truy cËp gÇn nhÊt, ®é dµi v¨n b¶n, lo¹i v¨n b¶n .. . b/ C©u hái t×m kiÕm C©u hái t×m kiÕm lµ bÊt kú c©u hái nµo mµ hÖ thèng cho phÐp ng−êi sö dông ®−a ra nh»m thÓ hiÖn yªu cÇu t×m kiÕm v¨n b¶n vµ ®iÒu nµy lµ kh¸ réng r·i. Cã nhiÒu c¸ch ®−a ra c©u hái tuú thuéc vµo c¸ch t×m kiÕm cña hÖ thèng vµ yªu cÇu cña ng−êi dïng. T×m kiÕm theo c¸c tõ hoÆc côm tõ C©u hái t×m kiÕm ®−îc tr×nh bµy qua c¸c tõ hoÆc côm tõ ®−îc liªn kÕt bëi c¸c phÐp to¸n logic nh»m diÔn t¶ ®−îc néi dung cña v¨n b¶n. §¬n gi¶n nhÊt cã thÓ lµ ®−a ra mét tõ hoÆc côm tõ vµ yªu cÇu tr¶ l¹i c¸c v¨n b¶n cã chøa tõ hoÆc côm tõ ®ã cïng víi sè lÇn xuÊt hiÖn chóng trong v¨n b¶n. Phøc t¹p h¬n, dïng c¸c phÐp to¸n l«gic ®Ó biÓu diÔn c¸c tõ cã thÓ liªn quan ®Õn nhau vµ cã ¶nh h−ëng kh¸c nhau ®Õn néi dung cÇn t×m. L−¬ng Song V©n Häc m¸y, häc m¸y m« t¶ phøc: thuËt to¸n vµ vÊn ®Ò rót gän lçi -68- Ch¼ng h¹n, cã thÓ ®Æt ra yªu cÇu t×m kiÕm nh− sau: T×m v¨n b¶n cã chøa c¸c tõ ‘ruéng ®Êt’, ‘luËt’,‘®Êt ®ai’,‘§iÒu’ nh−ng kh«ng chøa tõ ‘thuÕ’ vµ tõ ‘c¸ nh©n’. Ngoµi ra cã thÓ ®−a ra c¸c yªu cÇu bæ sung kh¸c nh−: • Kho¶ng c¸ch gi÷a c¸c tõ cÇn t×m cã thÓ liªn quan ®Õn néi dung v¨n b¶n. Ch¼ng h¹n, ®−a ra yªu cÇu: T×m v¨n b¶n cã chøa c¸c tõ ‘thu’ vµ tõ ‘nhËp’, nÕu hai tõ nµy gÇn nhau th× møc ®é liªn quan cña v¨n b¶n t×m ®−îc lµ cµng cao. Khi ®ã v¨n b¶n cã chøa c©u ‘thu nhËp’ ®−îc ®¸nh gi¸ lµ cã ®é chÝnh x¸c cao h¬n v¨n b¶n cã chøa c©u ‘thu vµ nhËp’. • C©u hái ®−a vµo cã thÓ ë d¹ng më réng hoÆc ®−îc thÓ hiÖn b»ng c¸ch dïng mét ký tù ®Æc biÖt thay cho mét tõ hoÆc mét nhãm tõ. Ch¼ng h¹n, ®−a ra yªu cÇu: T×m v¨n b¶n cã chøa nhãm ký tù lµ an* hoÆc thuy*. Cã thÓ cho phÐp ®−a ra c©u hái d¹ng nµy, tuy nhiªn nÕu nh− viÖc t×m kiÕm lµ theo néi dung th× c©u hái trªn hoµn toµn kh«ng cã ý nghÜa g× c¶. §èi víi tr−êng hîp nµy, hÖ thèng ph¶i tham kh¶o vµ thao t¸c trªn c¸c tõ kho¸ tho¶ m·n yªu cÇu trªn. T×m kiÕm theo chñ ®Ò C©u hái t×m kiÕm theo néi dung cña v¨n b¶n cÇn t×m. Yªu cÇu tr−íc ®ã c¸c v¨n b¶n ph¶i ®−îc x¸c ®inh bëi mét néi dung theo mét c¸ch nµo ®ã (nhËp b»ng tay hoÆc ph©n tÝch có ph¸p..). C©u hái ®−a vµo còng cã thÓ ®−îc ph©n tÝch có ph¸p ®−a ra mét chñ ®Ò t−¬ng øng. PhÐp t×m kiÕm sÏ ®−îc tiÕn hµnh trªn c¸c b¶ng index cña c¸c chñ ®Ò v¨n b¶n vµ chñ ®Ò c©u hái. C¸c c©u hái ®−a vµo ®−îc l−u tr÷ trong mét b¶ng. HÖ thèng sÏ qu¶n lý mét d·y c¸c yªu cÇu nµy trong b¶ng vµ gi¶i quyÕt chóng theo mét c¸ch tuÇn tù. c/ B¶ng kÕt qu¶ L−¬ng Song V©n Häc m¸y, häc m¸y m« t¶ phøc: thuËt to¸n vµ vÊn ®Ò rót gän lçi -69- B¶ng kÕt qu¶ lµ b¶ng l−u tr÷ toµn bé c¸c kÕt qu¶ t×m ®−îc trong qu¸ tr×nh t×m kiÕm vµ ph©n líp v¨n b¶n. KÕt qu¶ trong b¶ng kh«ng ph¶i lµ cè ®Þnh mµ chØ cã gi¸ trÞ ®èi víi tõng c©u hái, t¹i mét thêi ®iÓm nhÊt ®Þnh. Tuú thuéc vµo mçi ph−¬ng ph¸p xö lý mµ th«ng tin trong b¶ng kÕt qu¶ lµ kh¸c nhau. V.1.3. C¸c m« h×nh qu¶n lý vµ l−u tr÷ th«ng tin v¨n b¶n a/ M« h×nh logic Theo m« h×nh nµy, c¸c tõ cã nghÜa trong v¨n b¶n ®−îc g¸n chØ sè (index), vµ ng−êi ta qu¶n lý néi dung cña v¨n b¶n theo c¸c chØ sè ®ã. C¸c luËt l−u tr÷ vµ t×m kiÕm ViÖc x©y dùng hÖ thèng theo m« h×nh nµy ®−îc thùc hiÖn nh− sau: • Mçi v¨n b¶n ®Òu ®−îc chØ sè hãa theo luËt: - Thèng kª c¸c tõ cã nghÜa trong c¸c v¨n b¶n, ®ã lµ nh÷ng tõ mang th«ng tin chÝnh vÒ c¸c v¨n b¶n l−u gi÷. - ChØ sè ho¸ c¸c v¨n b¶n ®−a vµo theo danh s¸ch c¸c tõ kho¸ nãi trªn. øng víi mçi tõ kho¸ trong danh s¸ch sÏ l−u vÞ trÝ xuÊt hiÖn nã trong tõng v¨n b¶n vµ tªn v¨n b¶n mµ tån taÞ tõ kho¸ ®ã. • C©u hái t×m kiÕm ®−îc tr×nh bµy d−íi d¹ng logic tøc lµ gåm mét d·y c¸c phÐp to¸n l«gic (AND, OR, NOT ...) thùc hiÖn trªn c¸c tõ hoÆc côm tõ. VÝ dô vÒ c©u hái: T×m v¨n b¶n trong ®ã cã chøa tõ “hÖ thèng” vµ tõ “CSDL” nh−ng kh«ng chøa tõ “quan hÖ” ViÖc t×m kiÕm sÏ dùa vµo b¶ng chØ sè ®· t¹o ra vµ tr¶ l¹i kÕt qu¶ lµ c¸c v¨n b¶n tho¶ m·n toµn bé c¸c ®iÒu kiÖn trªn. ¦u vµ nh−îc ®iÓm • ¦u ®iÓm - T×m kiÕm nhanh vµ ®¬n gi¶n. Thùc vËy gi¶ sö cÇn t×m kiÕm tõ “mÑ”. HÖ thèng sÏ duyÖt trªn b¶ng chØ sè ®Ó trá ®Õn chØ sè t−¬ng øng nÕu nh− tõ “mÑ” tån t¹i trong hÖ thèng. ViÖc t×m L−¬ng Song V©n Häc m¸y, häc m¸y m« t¶ phøc: thuËt to¸n vµ vÊn ®Ò rót gän lçi -70- kiÕm nµy kh¸ nhanh vµ ®¬n gi¶n khi tr−íc ®ã ta ®· s¾p xÕp b¶ng chØ sè theo vÇn ch÷ c¸i. PhÐp t×m kiÕm trªn sÏ cã ®é phøc t¹p cÊp nlog2n (víi n lµ sè tõ ®−îc chØ sè ho¸ trong b¶ng chØ sè). T−¬ng øng víi chØ sè trªn sÏ cho ta biÕt c¸c v¨n b¶n chøa nã. Nh− vËy nÕu viÖc t×m kiÕm liªn quan ®Õn k tõ th× sè c¸c phÐp to¸n cÇn thùc hiÖn sÏ lµ k*n*log2n víi n lµ sè v¨n b¶n ®ang cã. - C©u hái vÒ c¸c tõ t×m kiÕm lµ linh ho¹t. Cã thÓ dïng c¸c ký tù ®Æc biÖt trong c©u hái t×m kiÕm mµ kh«ng lµm ¶nh h−ëng ®Õn ®é phøc t¹p cña phÐp t×m kiÕm. VÝ dô tõ “bè%” sÏ tr¶ l¹i tÊt c¶ c¸c v¨n b¶n cã chøa nh÷ng tõ nh− “bè”, “bèn”, “bèng”, “bèt”.. lµ c¸c tõ ®−îc b¾t ®Çu b»ng tõ “bè”. Ký tù “%” ®−îc gäi lµ kÝ tù thay thÕ. Ngoµi ra b»ng c¸c phÐp to¸n logic c¸c tõ cÇn t×m cã thÓ ®−îc tæ chøc thµnh c¸c c©u hái mét c¸ch linh ho¹t. VÝ dô tõ cÇn t×m lµ [vî, vîi, v−¬ng], dÊu [.] sÏ thÓ hiÖn viÖc t×m kiÕm trªn mét trong sè nhiÒu tõ trong nhãm. §©y thùc ra lµ mét c¸ch thÓ hiÖn linh ho¹t phÐp to¸n OR trong ®¹i sè logic thay v× ph¶i viÕt lµ t×m v¨n b¶n cã chøa hoÆc tõ “vî” hoÆc tõ “vîi” hoÆc tõ “v−¬ng”.. • Nh−îc ®iÓm - Ng−êi t×m kiÕm ph¶i cã chuyªn m«n trong lÜnh vùc m×nh t×m kiÕm. Thùc vËy, do c©u hái ®−a vµo d−íi d¹ng logic nªn kÕt qu¶ tr¶ l¹i còng cã gi¸ trÞ Boolean, mét sè v¨n b¶n sÏ ®−îc tr¶ l¹i khi tho¶ m·n mäi ®iÒu kiÖn ®−a vµo. Nh− vËy, muèn t×m ®−îc v¨n b¶n theo néi dung th× ng−êi t×m kiÕm ph¶i biÕt chÝnh x¸c vÒ c¸c tõ ng÷ cã trong v¨n b¶n ®ã vµ mèi quan hÖ gi÷a chóng, g©y khã kh¨n cho viÖc t×m kiÕm. - ViÖc chØ sè hãa v¨n b¶n lµ phøc t¹p vµ tèn nhiÒu thêi gian. - Tèn nhiÒu kh«ng gian l−u tr÷ c¸c b¶ng chØ sè. - C¸c v¨n b¶n ®−îc t×m kh«ng thÓ s¾p xÕp theo ®é chÝnh x¸c cña chóng. Do gi¸ trÞ tr¶ l¹i lµ toµn bé c¸c v¨n b¶n tho¶ m·n ®iÒu kiÖn nªn sè v¨n b¶n tr¶ l¹i kh«ng biÕt tr−íc víi sè l−îng cã thÓ lµ rÊt nhiÒu. MÆt kh¸c l¹i kh«ng cã mét tiªu chuÈn nµo ®Ó ®¸nh gi¸ chÊt l−îng ®é liªn quan cña c¸c v¨n b¶n tr¶ L−¬ng Song V©n Häc m¸y, häc m¸y m« t¶ phøc: thuËt to¸n vµ vÊn ®Ò rót gän lçi -71- l¹i víi c©u hái ®Æt ra trong khi nh÷ng ng−êi t×m kiÕm th−êng xuyªn muèn tr¶ l¹i sè c¸c v¨n b¶n cã gi¸ trÞ lµ Ýt nhÊt víi ®é liªn quan lµ lín nhÊt. §iÒu nµy vÉn cã thÓ gi¶i quyÕt ®−îc b»ng c¸ch l−u c¸c chØ sè trong qu¸ tr×nh chØ sè hãa nh−ng rÊt phøc t¹p trong viÖc truy xuÊt vµ tÝnh to¸n sè liÖu. - C¸c b¶ng chØ sè kh«ng linh ho¹t. Khi c¸c tõ kho¸ trong b¶ng thay ®æi (thªm, xo¸..) th× chØ sè cña c¸c v¨n b¶n còng ph¶i thay ®æi theo. b/ M« h×nh ph©n tÝch có ph¸p ThuËt to¸n l−u tr÷ vµ t×m kiÕm ViÖc x©y dùng hÖ thèng theo m« h×nh nµy ph¶i tu©n theo c¸c luËt sau: • Mçi v¨n b¶n ®Òu ph¶i ®−îc ph©n tÝch có ph¸p vµ tr¶ l¹i th«ng tin chi tiÕt vÒ chñ ®Ò cña v¨n b¶n ®ã. Chñ ®Ò cña c¸c v¨n b¶n ®−îc t¹o ra ë nhiÒu møc trõu t−îng kh¸c nhau phô thuéc vµo møc ®é chi tiÕt néi dung v¨n b¶n cña yªu cÇu ng−êi dïng. • C¸c v¨n b¶n ®−îc qu¶n lý th«ng qua c¸c chñ ®Ò nµy ®Ó cã thÓ t×m kiÕm ®−îc khi cã yªu cÇu. • C©u hái t×m kiÕm sÏ dùa trªn c¸c chñ ®Ò trªn, nh− vËy tr−íc ®ã sÏ tiÕn hµnh chØ sè hãa theo chñ ®Ò. • C¸ch chØ sè hãa theo chñ ®Ò gièng nh− khi chØ sè ho¸ theo v¨n b¶n nh−ng chØ sè hãa trªn toµn bé c¸c tõ cã trong chñ ®Ò ®ã. • C©u hái ®−a vµo còng cã thÓ ®−îc ph©n tÝch có ph¸p ®Ó tr¶ l¹i mét chñ ®Ò vµ t×m kiÕm trªn chñ ®Ò ®ã. Nh− vËy bé phËn xö lý chÝnh ®èi víi mét hÖ CSDL x©y dùng theo m« h×nh nµy chÝnh lµ hÖ thèng ph©n tÝch có ph¸p vµ ®o¸n nhËn néi dung v¨n b¶n. §¸nh gi¸ chung vÒ ph−¬ng ph¸p ChÊt l−îng cña hÖ thèng theo ph−¬ng ph¸p nµy hoµn toµn phô thuéc vµo chÊt l−îng cña hÖ thèng ph©n tÝch có ph¸p vµ ®o¸n nhËn néi dung v¨n b¶n. Trªn L−¬ng Song V©n Häc m¸y, häc m¸y m« t¶ phøc: thuËt to¸n vµ vÊn ®Ò rót gän lçi -72- thùc tÕ viÖc x©y dùng hÖ thèng nµy lµ rÊt phøc t¹p, phô thuéc vµo ®Æc ®iÓm cña tõng ng«n ng÷, vµ ®a sè vÉn ch−a ®¹t ®−îc ®é chÝnh x¸c cao. Tuy nhiªn, khi ®· cã chñ ®Ò th× viÖc t×m kiÕm theo ph−¬ng ph¸p nµy l¹i kh¸ hiÖu qu¶ do t×m kiÕm nhanh vµ chÝnh x¸c. MÆt kh¸c, ®èi víi nh÷ng ng«n ng÷ ®¬n gi¶n vÒ mÆt ng÷ ph¸p th× viÖc ph©n tÝch trªn lµ cã thÓ ®¹t ®−îc møc ®é chÝnh x¸c cao vµ chÊp nhËn ®−îc. c/ M« h×nh vector M« h×nh vector sÏ ®−îc tr×nh bµy chi tiÕt trong phÇn sau (môc IV.2.1). Trong m« h×nh nµy, viÖc l−u tr÷ vµ t×m kiÕm dùa theo sù xuÊt hiÖn c¸c tõ cã nghÜa trong c©u hái vµ c¸c tµi liÖu t−¬ng øng. M« h×nh sö dông mét vector vÒ sù xuÊt hiÖn c¸c tõ cã nghÜa trong v¨n b¶n ®Ó biÓu diÔn v¨n b¶n vµ hÖ thèng t×m kiÕm dùa trªn viÖc xem xÐt c¸c vector nµy. C¸c v¨n b¶n ®−îc l−u tr÷ ngoµi, viÖc hái vµ t×m kiÕm theo néi dung ®−îc thùc hiÖn theo c¸c tõ. IV.2. thuËt to¸n t×m kiÕm vµ Ph©n líp trong c¬ së d÷ liÖu full-text theo m« h×nh vector c¶i tiÕn M« h×nh vector lµ m« h×nh tæ chøc qu¶n lý, t×m kiÕm c¸c tµi liÖu Full-text theo c¸c tõ vµ côm tõ. Nã cho phÐp ng−êi dïng t×m ra ®−îc nh÷ng tµi liÖu cÇn thiÕt khi nhËp vµo mét sè tõ hoÆc côm tõ. HÖ thèng sÏ ®−a ra danh s¸ch c¸c tµi liÖu cã chøa c¸c tõ ®ã. §Æc ®iÓm næi bËt cña m« h×nh nµy lµ c¸c tµi liÖu l−u tr÷ vµ c©u hái t×m kiÕm ®Òu biÓu diÔn d−íi d¹ng mét vector. ViÖc t×m kiÕm tµi liÖu ®−îc thùc hiÖn trªn hÖ thèng c¸c vector. Trong phÇn nµy chóng ta tr×nh bµy chi tiÕt vÒ m« h×nh vector víi mét sè c¶i tiÕn nhá cña chóng ta, thuËt to¸n t×m kiÕm vµ mét sè thuËt to¸n ph©n líp dùa trªn m« h×nh ®· c¶i tiÕn ®ã. IV.2.1. M« h×nh vector c¶i tiÕn vµ thuËt to¸n t×m kiÕm a/ ThuËt to¸n l−u tr÷ L−¬ng Song V©n Häc m¸y, häc m¸y m« t¶ phøc: thuËt to¸n vµ vÊn ®Ò rót gän lçi -73- Gi¶ sö D= {d1, d2, d3, ... , dn ...} lµ tËp hîp c¸c v¨n b¶n mµ hÖ thèng cÇn qu¶n lý, trong ®ã di lµ c¸c v¨n b¶n mang th«ng tin thuéc lÜnh vùc cÇn quan t©m. T = {t1, t2, t3 , ... , tm} lµ tËp hîp h÷u h¹n c¸c tõ cã nghÜa trong lÜnh vùc ®ang ®−îc quan t©m cã trong c¸c v¨n b¶n vµ ®−îc gäi lµ c¸c tõ kho¸. HÖ thèng biÓu diÔn néi dung cña v¨n b¶n th«ng qua viÖc kiÓm tra sù cã mÆt cña mçi tõ kho¸ trong v¨n b¶n b»ng c¸ch thùc hiÖn mét ¸nh x¹ F tõ D vµo V trong ®ã V lµ tËp hîp c¸c vector cã m thµnh phÇn (m lµ sè l−îng tõ khãa trong hÖ thèng). F: D→V Víi mçi v¨n b¶n d thuéc tËp hîp D, F(d) sÏ x¸c ®Þnh mét vector v: v(d) = (v1, v2, ..., vm) trong ®ã vi gi¸ trÞ ph¶n ¸nh sù xuÊt hiÖn cña tõ khãa ti trong v¨n b¶n d, vi lµ 0 - khi kh«ng xuÊt hiÖn hoÆc 1 - khi cã xuÊt hiÖn (kh«ng kÓ lµ xuÊt hiÖn bao nhiªu lÇn). Nh− vËy, thµnh phÇn trong vector v ®−îc x¸c ®Þnh theo luËt sau: • NÕu ti cã mÆt trong d ta cã vi = 1, • NÕu ti kh«ng cã mÆt trong d ta cã vi = 0 VÝ dô, víi D = {d1,d2} trong ®ã: d1 lµ “Céng hoµ, x· héi, chñ nghÜa, ViÖt Nam” d2 lµ “§éc lËp, tù do, h¹nh phóc” T= {Céng hoµ, ®éc lËp, tù do, chñ nghÜa, b¶o thñ, ®¶ng} ta cã v(d1) = (1,0,0,1,0,0) vµ v(d2) = (0,1,1,0,0,0) C©u hái t×m kiÕm Q thuéc d¹ng t×m kiÕm theo tõ vµ ®−îc ®−a vµo d−íi d¹ng liÖt kª sù xuÊt hiÖn c¸c tõ trong ng«n ng÷ ®· cho (kh«ng nhÊt thiÕt lµ tõ khãa) cã liªn quan ®Õn néi dung v¨n b¶n cÇn t×m, Q = {q1, q2, ..., qk}. Ta còng lÊy F(Q) gièng nh− ®· lµm víi v¨n b¶n d, kÕt qu¶ ®−îc mét vector P = (p1, p2, ... , pm) Víi mçi v¨n b¶n d, ®Æt L−¬ng Song V©n Häc m¸y, häc m¸y m« t¶ phøc: thuËt to¸n vµ vÊn ®Ò rót gän lçi -74- A(d) = P * v(d) = vp i m i i * 1 ∑ = (4.1) Khi ®ã, hÖ sè A(d) ®−îc coi lµ møc ®é liªn quan cña v¨n b¶n d ®èi víi néi dung cÇn t×m. VÝ dô, gi¶ sö Q = {§¶ng, b¶o thñ, chiÕm, ®a sè, phiÕu bÇu} th× P = (0, 0, 0, 0, 1, 1). Ta cã mét sè nhËn xÐt sau ®©y: • A=0 khi: - Víi mäi i, pi=0 hay c¸c tõ trong c©u hái kh«ng cã mÆt trong tËp tõ khãa. - Víi mäi j, vj = 0 hay c¸c tõ kho¸ kh«ng cã mÆt trong v¨n b¶n cÇn l−u tr÷, - Víi mäi j, vj*pj=0 hay mäi tõ cã trong c©u hái t×m kiÕm ®Òu kh«ng cã trong v¨n b¶n d. • A>0 khi tån t¹i j tho¶ m·n vj*pj ≠ 0 hay còng vËy, tån t¹i Ýt nhÊt mét tõ kho¸ võa cã mÆt trong v¨n b¶n d võa cã mÆt trong c©u hái t×m kiÕm. • A = m khi mäi tõ khãa trong tõ ®iÓn ®Òu xuÊt hiÖn trong v¨n b¶n d. Theo c¸ch tÝnh trªn khi ®−a vµo mét c©u hái q, víi mçi v¨n b¶n d, sÏ cho t−¬ng øng mét gi¸ trÞ A(d). NÕu A(d) cµng lín th× cã thÓ quan niÖm r»ng ®é liªn quan cña v¨n b¶n víi c©u hái cµng nhiÒu. Trong c¸c hÖ thèng thùc tÕ, kh«ng lµm gi¶m tæng qu¸t ta lu«n gi¶ thiÕt lµ trong v¨n b¶n hay c©u hái cã Ýt nhÊt mét tõ khãa. ThuËt to¸n t×m kiÕm theo c©u hái Q (c©u hái Q ®−îc tr×nh bµy qua vector P) ®−îc m« t¶ nh− sau: - Víi mäi d ∈ D, tÝnh gi¸ trÞ A(d) = P * v(d) , - S¾p xÕp c¸c gi¸ trÞ A(d) theo thø tù gi¶m dÇn, - HiÖn néi dung c¸c v¨n b¶n d theo thø tù gi¶m dÇn ®· cã cho ®Õn khi tháa m·n yªu cÇu ng−êi dïng. b/ M« h×nh vector c¶i tiÕn L−¬ng Song V©n Häc m¸y, häc m¸y m« t¶ phøc: thuËt to¸n vµ vÊn ®Ò rót gän lçi -75- ViÖc c¶i tiÕn m« h×nh vector trong phÇn nµy lµ sù ph¸t triÓn mét sè c¶i tiÕn ®· ®−îc ®Ò cËp trong [4]. C¶i tiÕn theo h−íng tõ ®ång nghÜa vµ sè lÇn xuÊt hiÖn Mét ®iÒu cã tÝnh phæ biÕn lµ trong mäi ng«n ng÷ tù nhiªn lu«n tån t¹i nh÷ng tõ ®ång nghÜa, ch¼ng h¹n, trong tiÕng ViÖt c¸c tõ “an d−ìng”, “an trÝ” cã cïng mét nghÜa lµ víi tõ "nghØ". Nh− vËy, cïng mét vÊn ®Ò cã thÓ dïng nhiÒu tõ kh¸c nhau ®Ó biÓu ®¹t ý nghÜa cña nã. Trong khi ®ã néi dung trong c¸c c©u hái th«ng th−êng chØ ®−îc diÔn ®¹t b»ng mét tõ duy nhÊt. Do vËy, trong qu¸ tr×nh t×m kiÕm nÕu nh− hÖ thèng ®−îc tæ chøc kh«ng tèt th× sÏ chØ t×m kiÕm ®−îc c¸c tµi liÖu cã chøa c¸c tõ ®−îc ®−a ra trong c©u hái mµ kh«ng t×m ®−îc c¸c tµi liÖu cã cïng néi dung víi c¸c c¸ch thÓ hiÖn kh¸c. C¸c tõ thuéc nhãm tõ ®ång nghÜa ®Òu thuéc tËp c¸c tõ cã nghÜa ®· ®−îc liÖt kª khi thiÕt kÕ hÖ thèng. Trong mét nhãm c¸c tõ ®ång nghÜa, mÆc dï cïng biÓu ®¹t mét néi dung nh−ng vai trß cña c¸c tõ cã thÓ sÏ kh¸c nhau do c¸c lý do sau: Víi néi dung ®ã, tõ nµy hay ®−îc sö dông h¬n tõ kia. Ch¼ng h¹n, c¸c tõ trong nhãm ®ång nghÜa (nghØ, an d−ìng, an trÝ) th× tõ “nghØ” ®−îc sö dông nhiÒu h¬n lµ “an d−ìng” hay “an trÝ”. Chóng ta chän trong nhãm tõ ®ång nghÜa mét tõ ®−îc sö dông nhiÒu nhÊt lµm tõ ®¹i diÖn vµ chØ tõ ®¹i diÖn xuÊt hiÖn trong b¶ng tõ khãa T. Mét b¶ng tra cøu vÒ c¸c tõ ®ång nghÜa liªn quan ®Õn mét tõ kho¸ ®−îc bæ sung trong thuËt to¸n. Mét tõ khãa víi nhãm ®ång nghÜa chØ cã tõ khãa ®ã gäi lµ tõ ®¬n nghÜa. Sau khi ®· ph©n tÝch nh− trªn, ta cã thÓ biÓu diÔn hÖ sè cña c¸c tõ trong nhãm tõ ®ång nghÜa trªn nh− sau (mäi tõ ®¹i diÖn cã hÖ sè 10): Tõ “nghØ” cã hÖ sè = 10 Tõ “an d−ìng” cã hÖ sè = 9 Tõ “an trÝ” cã hÖ sè = 8. ViÖc thèng kª c¸c tõ ®ång nghÜa vµ ®¸nh gi¸ vÒ hÖ sè cña c¸c tõ ®ång nghÜa trong nhãm lµ mét viÖc kh¸ phøc t¹p ®ßi hái ph¶i cã kiÕn thøc vÒ ng÷ nghÜa cu¶ tõ trong ng«n ng÷. V× vËy c¸c nhãm tõ ®ång nghÜa trong hÖ thèng cÇn L−¬ng Song V©n Häc m¸y, häc m¸y m« t¶ phøc: thuËt to¸n vµ vÊn ®Ò rót gän lçi -76- ph¶i th«ng qua viÖc ®¸nh gi¸ tõ c¸c nhµ ng«n ng÷ häc. Khi hÖ thèng cho phÐp nhËp l¹i hoÆc bæ sung c¸c nhãm tõ ®ång nghÜa ®Ó cã thÓ lµm t¨ng ®é chÝnh x¸c th× hiÖu qu¶ hÖ thèng sÏ t¨ng. Mét néi dung cÇn quan t©m lµ sè lÇn xuÊt hiÖn cña tõ kho¸ (cïng c¸c tõ ®ång nghÜa víi nã) trong v¨n b¶n. Mét c¸ch ®Æt vÊn ®Ò kh¸ hîp lý lµ nÕu v¨n b¶n D gÆp nhiÒu tõ kho¸ nµo ®ã h¬n v¨n b¶n D' th× D cã thÓ mang nghÜa cña tõ khãa ®ã nhiÒu h¬n v¨n b¶n D'. ChÝnh v× lÏ ®ã, cïng víi gi¶i ph¸p tõ ®ång nghÜa, chóng ta nhÊn m¹nh thªm sè lÇn xuÊt hiÖn tõ khãa trong v¨n b¶n. Nh÷ng néi dung tr×nh bµy d−íi ®©y thÓ hiÖn c¸c c¸ch ®Æt vÊn ®Ò trªn. §Æt tËp mäi tõ cã nghÜa T* = T ∪ {tõ ®ång nghÜa} vµ hµm h: T* → N (sè nguyªn d−¬ng) trong ®ã, ∀t∈T*: h(t) chÝnh lµ hÖ sè cña tõ t. ViÖc t×m kiÕm vµ m· ho¸ sÏ ®−îc tiÕn hµnh trªn hÖ thèng c¸c tõ khãa. Trong b¶ng vector m· ho¸, mçi tõ ®ång nghÜa sÏ ®−îc ®¹i diÖn bëi mét m· nhãm duy nhÊt, nh− vËy sÏ gi¶m ®−îc ®é dµi vector m· ho¸ ®ång thêi gi¶m ®−îc c¸c phÐp tÝnh cÇn thiÕt trong qu¸ tr×nh t×m kiÕm. Khi m· ho¸ tµi liÖu (nhê ¸nh x¹ F), c¸ch tÝnh gi¸ trÞ vector cña mét tõ ®ång nghÜa còng kh¸c so víi c¸ch tÝnh gi¸ trÞ vector cña mét tõ ®¬n nghÜa vµ ®−îc tÝnh theo c¸ch d−íi ®©y. Víi v¨n b¶n d, F(d) = v = (v1, v2, ..., vm) ®−îc tÝnh nh− sau: vi = ∑ ∩∈ dTt th * )( Víi c©u hái Q = {q1, q2, ..., qk} thuËt to¸n thiÕt lËp vector P = (p1, p2, ... , pm) theo ¸nh x¹ tõ qi tíi tõ khãa t−¬ng øng (nÕu cã). Nh− vËy nÕu qi lµ tõ khãa tj (hoÆc tõ ®ång nghÜa víi tj) th× pj = 1 cßn ng−îc l¹i pj = 0. Vµ nh− vËy, hÖ sè liªn quan A = P * v theo c«ng thøc (4.1) cho phÐp lµm t¨ng ®é chÝnh x¸c cña hÖ thèng. Mét vÊn ®Ò ®¸ng quan t©m song kh«ng xem xÐt trong hÖ thèng cña chóng ta lµ vÇn ®Ò ®a nghÜa cña hÖ thèng tõ cã nghÜa. §©y lµ mét néi dung rÊt lý thó ®ßi hái nhiÒu c«ng søc nghiªn cøu. L−¬ng Song V©n Häc m¸y, häc m¸y m« t¶ phøc: thuËt to¸n vµ vÊn ®Ò rót gän lçi -77- C¶i tiÕn theo h−íng g¸n träng sè cho c¸c tõ thuéc c©u hái C©u hái ®−a vµo d−íi d¹ng Q = {q1, q2, ..., qk} trong ®ã mçi tõ qi l¹i cã mét hÖ sè ci thÓ hiÖn tÇm quan träng kh¸c nhau cña c¸c tõ trong c©u hái. ¸nh x¹ Q thµnh vector P (p1, p2, ..., pm) th× gi¸ trÞ cña pi ®−îc tÝnh theo c¸c träng sè nµy, tøc lµ nÕu qi lµ tõ khãa tj (hoÆc tõ ®ång nghÜa víi tj) th× pj = ci (träng sè cña qi) cßn ng−îc l¹i pj = 0. HÖ sè liªn quan A = P * v theo c«ng thøc (4.1) còng thÓ hiÖn ®−îc träng sè cña c¸c tõ trong c©u hái Q. c/ §¸nh gi¸ vÒ c¸c −u nh−îc ®iÓm cña thuËt to¸n • ¦u ®iÓm - C¸c v¨n b¶n tr¶ l¹i cã thÓ ®−îc s¾p xÕp theo møc ®é liªn quan ®Õn néi dung yªu cÇu do trong phÐp thö mçi v¨n b¶n ®Òu tr¶ l¹i chØ sè ®¸nh gi¸ ®é liªn quan cña nã ®Õn néi dung yªu cÇu. - ViÖc ®−a ra c¸c c©u hái t×m kiÕm lµ dÔ dµng vµ kh«ng yªu cÇu ng−êi t×m kiÕm cã tr×nh ®é chuyªn m«n cao vÒ vÊn ®Ò ®ã. - TiÕn hµnh l−u tr÷ vµ t×m kiÕm ®¬n gi¶n h¬n ph−¬ng ph¸p logic. - Ng−êi t×m kiÕm cã thÓ tù ®−a ra sè c¸c v¨n b¶n tr¶ l¹i cã møc ®é chÝnh x¸c cao nhÊt. - M« h×nh l−u tr÷ vµ t×m kiÕm vector lµ phï hîp víi thuËt to¸n ph©n líp v¨n b¶n (®−îc tr×nh bµy chi tiÕt trong phÇn IV.2.2-IV.2.4) võa cã t¸c dông trong viÖc ph©n lo¹i v¨n b¶n l¹i cã ý nghÜa hçi trî cho bµi to¸n t×m kiÕm v¨n b¶n. • Nh−îc ®iÓm - ViÖc t×m kiÕm tiÕn hµnh kh¸ chËm khi hÖ thèng c¸c tõ kho¸ lµ lín do ph¶i tÝnh to¸n trªn toµn bé c¸c vector cña c¸c v¨n b¶n. L−¬ng Song V©n Häc m¸y, häc m¸y m« t¶ phøc: thuËt to¸n vµ vÊn ®Ò rót gän lçi -78- Khi biÓu diÔn c¸c vector víi c¸c hÖ sè lµ sè tù nhiªn lµm t¨ng møc ®é chÝnh x¸c cña phÐp t×m kiÕm nh−ng sÏ lµm gi¶m tèc ®é tÝnh to¸n ®i rÊt nhiÒu do c¸c phÐp nh©n vector ph¶i tiÕn hµnh trªn c¸c sè tù nhiªn hoÆc sè thùc, h¬n n÷a viÖc l−u tr÷ c¸c vector sÏ phøc t¹p vµ tèn kÐm. - HÖ thèng kh«ng linh ho¹t khi l−u tr÷ c¸c tõ kho¸. ChØ cÇn mét thay ®æi rÊt nhá trong b¶ng tõ kho¸ sÏ kÐo theo hoÆc lµ vector ho¸ l¹i toµn bé c¸c v¨n b¶n l−u tr÷ hoÆc sÏ bá qua c¸c tõ cã nghÜa bæ sung trong c¸c v¨n b¶n ®−îc m· ho¸ tr−íc ®ã. Tuy nhiªn víi nh÷ng −u ®iÓm nhÊt ®Þnh, sù sai sè nhá nµy cã thÓ ®−îc bá qua do hiÖn t¹i sè c¸c tõ cã nghÜa ®−îc m· ho¸ ®· kh¸ ®Çy ®ñ tr−íc khi tiÕn hµnh m· ho¸ c¸c v¨n b¶n. V× vËy, ph−¬ng ph¸p vector vÉn ®−îc quan t©m vµ sö dông. d/ VÒ tèc ®é thùc hiÖn ch−¬ng tr×nh Tèc ®é thùc hiÖn ch−¬ng tr×nh ®−îc ®¸nh gi¸ qua tèc ®é trong qu¸ tr×nh chÕ biÕn, l−u tr÷ tµi liÖu vµ tèc ®é t×m kiÕm tµi liÖu. Tµi liÖu tr−íc khi l−u tr÷ trong hÖ thèng sÏ ®−îc m· ho¸ thµnh c¸c vector b»ng c¸ch duyÖt tõng tõ trong tµi liÖu. Víi mét sè l−îng lín c¸c tõ kho¸ ®ång thêi sè c¸c tõ ng÷ trong mét tµi liÖu lµ nhiÒu th× qu¸ tr×nh nµy diÔn ra kh¸ chËm. ViÖc t×m kiÕm tµi liÖu diÔn ra gåm hai qu¸ tr×nh: qu¸ tr×nh m· ho¸ c©u hái vµ qu¸ tr×nh thao t¸c trªn c¸c vector. Do sè l−îng tõ trong c©u hái ®−a vµo th«ng th−êng lµ Ýt nªn thêi gian m· ho¸ c©u hái t−¬ng ®èi nhá. Trong khi ®ã thêi gian dµnh cho c¸c thao t¸c trªn c¸c vector phô thuéc hoµn toµn vµo ®é dµi c¸c vector hay sè l−îng c¸c phÐp tÝnh gi÷a c©u hái víi c¸c vector m· ho¸ cña tµi liÖu. HÖ thèng x©y dùng theo ph−¬ng ph¸p vector ph¶i qu¶n lý c¸c tõ cã nghÜa trong tµi liÖu. Sè l−îng c¸c tõ cã nghÜa ®−îc qu¶n lý trong hÖ thèng phô thuéc vµo yªu cÇu ®èi víi hÖ thèng ®ã. §Ó h¹n chÕ c¸c phÐp tÝnh trong giai ®o¹n nµy ta cã thÓ gi¶m ®é dµi cña vector m· ho¸ c¸c tµi liÖu b»ng viÖc tõ khãa ®¹i diÖn cho mçi nhãm tõ ®ång nghÜa. L−¬ng Song V©n Häc m¸y, häc m¸y m« t¶ phøc: thuËt to¸n vµ vÊn ®Ò rót gän lçi -79- IV.2.2. ThuËt to¸n ph©n líp Bayes thø nhÊt T−¬ng øng víi c¸ch thøc mµ Dunja Mladenic' ®· tr×nh bµy trong [11], kÕt hîp víi m« h×nh vector trªn ®©y, chóng ta sö dông thuËt to¸n ph©n líp Bayes ®Ó ph©n líp mét tµi liÖu theo n nhãm tµi liÖu ®· ®Þnh tr−íc. ThuËt ng÷ "catalog" t−¬ng øng víi thuËt ng÷ "nhãm" trong bµi to¸n ph©n líp. Khi ¸p dông thuËt to¸n ph©n líp Bayes, viÖc x¸c ®Þnh x¸c suÊt tiªn nghiÖm vµ x¸c suÊt hËu nghiÖm hîp lý lµ mét vÊn ®Ò cã tÝnh cèt lâi. Tån t¹i hai bé ph©n líp Bayes ®Ó gi¶i quyÕt bµi to¸n ph©n líp tµi liÖu nãi trªn. Trong phÇn nµy, chóng ta nghiªn cøu bé ph©n líp Bayes thø nhÊt. Trong c¸c thuËt to¸n ph©n líp d−íi ®©y, sö dông m« h×nh vector ®Ó biÓu diÔn c¸c tµi liÖu. Ngoµi c¸c tham sè c¬ b¶n cña m« h×nh vector, hÖ thèng cßn cÇn thªm c¸c tham sè sau ®©y: • TËp hîp n catalog {C1, C2, ..., Cn} trong ®ã mçi catalog Ci cã mét sè tµi liÖu mÉu chØ dÉn vÒ catalog ®ã. Trong m« h×nh nµy, th«ng tin vÒ mét catalog chØ cã ®−îc tõ nhãm c¸c tµi liÖu mÉu t−¬ng øng víi nã. ViÖc chän tµi liÖu mÉu vµo mÉu catalog dùa theo kinh nghiÖm cña c¸c chuyªn gia. • X¸c suÊt P(Ci): x¸c suÊt ®−îc g¸n cho c¸c catalog Ci. Gi¸ trÞ nµy mang ý nghÜa lµ tµi liÖu ®−îc ph©n kh«ng ®Òu vµo c¸c catalog. §iÒu nµy b¾t nguån tõ thùc tÕ lµ sè l−îng c¸c tµi liÖu trong c¸c catalog lµ kh«ng ®Òu nhau. Do vËy, tõng catalog sÏ ®−îc g¸n mét gi¸ trÞ P(Ci). Catalog nµo cã gi¸ trÞ P(Ci) lín chøng tá sè l−îng c¸c tµi liÖu trong nã lµ nhiÒu. §©y lµ mét trong c¸c gi¸ trÞ cã ¶nh h−ëng ®Õn ®é chÝnh x¸c cña bé ph©n líp. • Ng−ìng CtgTshi ®Ó kiÓm tra xem tµi liÖu Doc ®· cho cã ®óng thuéc vµo catalog Ci ®ã hay kh«ng, mçi catalog cã mét ng−ìng riªng. Víi mçi líp catalog C, sau khi thùc hiÖn ph©n líp, hÖ thèng sÏ sinh ra mét gi¸ trÞ t−¬ng øng P(C/Doc) - ®©y lµ x¸c suÊt ®Ó ph©n tµi liÖu Doc thuéc vµo C. L−¬ng Song V©n Häc m¸y, häc m¸y m« t¶ phøc: thuËt to¸n vµ vÊn ®Ò rót gän lçi -80- Tµi liÖu Doc sÏ ®−îc coi lµ thuéc vµo C nÕu P(C/Doc) ≥ CtgTsh t−¬ng øng, ng−îc l¹i, khi (P(C/Doc) < CtgTsh) th× tµi liÖu Doc kh«ng thuéc vµo catalog C. KÕt qu¶ lµ hÖ thèng sinh ra c¸c x¸c suÊt P(Ci/Doc) vµ cuèi cïng sÏ quyÕt ®Þnh xem tµi liÖu Doc ®· cho thuéc vµo catalog nµo. C¸c x¸c suÊt P(Ci/Doc) ®−îc gäi lµ x¸c suÊt hËu nghiÖm. Gi¸ trÞ P(C/Doc) - x¸c suÊt tµi liÖu Doc thuéc vµo catalog C ®−îc tÝnh to¸n dùa vµo c«ng thøc sau: ∑ ∏ ∏ = ∈ ∈ × × = n i TF DocFTF ili DocFTF j TF l l j j CFPCP CFPCP DocCP 1 ),( ),( )()( )()( )( (4.2) vµ ∑ = + += n i i j j CFTFT CFTF CFP 1 ),( ),(1 )( (4.3) Trong ®ã: • Fj lµ tõ thø j trong tËp tõ khãa. • TF(Fj, C) lµ tÇn suÊt cña tõ Fj trong tµi liÖu Doc. • TF(Fj, C) lµ tÇn suÊt cña tõ Fj trong Catalog C. • | T | lµ sè l−îng c¸c tõ cã trong tËp tõ khãa T. • P(Fj, C) lµ x¸c suÊt cã ®iÒu kiÖn ®Ó tõ Fj cã mÆt trong tµi liÖu cña Catalog C. • n lµ sè l−îng Catalog cã trong hÖ thèng. Trong c«ng thøc (4.3) x¸c suÊt P(Fj/C) ®−îc tÝnh sö dông −íc l−îng x¸c suÊt Laplace. §Ó tr¸nh tr−êng hîp tÇn suÊt cña tõ Fj trong Catalog C b»ng 0 - tøc lµ tõ Fj kh«ng cã trong Catalog C th× tö sè ®−îc céng thªm 1. L−¬ng Song V©n Häc m¸y, häc m¸y m« t¶ phøc: thuËt to¸n vµ vÊn ®Ò rót gän lçi -81- Tuy nhiªn cã mét ®iÒu quan träng ®Ó lµm gi¶m sù phøc t¹p trong tÝnh to¸n vµ lµm gi¶m bít thêi gian tÝnh to¸n trong c«ng thøc (4.2) ta ®Ó ý thÊy r»ng: Kh«ng ph¶i tµi liÖu Doc ®· cho ®Òu chøa tÊt c¶ c¸c tõ trong tËp tõ khãa T. Do ®ã, TF(Fj , Doc) =0 khi tõ khãa Fj thuéc T nh−ng kh«ng thuéc tµi liÖu Doc. Vµ kÕt qu¶ lµ kÐo theo lµ P(Fj|C) TF(Fj,Doc)=1 t¹i tõ khãa Fj ®ã. Vµ nh− vËy ta cã thÓ bá qua tõ khãa Fj nµy mµ kh«ng lµm ¶nh h−ëng ®Õn c«ng thøc (4.2). Vµ c«ng thøc cuèi cïng cña c«ng thøc (4.2) ®−îc viÕt l¹i nh− sau: ( ) ( ) ( )P C Doc P C P F C P C P F C j TF F Doc F Doc i n i l i TF F Doc F Doc j j l l = × × ∈ = ∈ ∏ ∑ ∏ ( ) ( ) ( , ) ( , ) 1 (4.2’) vµ t−¬ng tù (4.3) ®−îc viÕt l¹i nh− sau: ( ) ∑ = + += n i i j j CFTFT CFTF CFP 1 ),( ),(1 (4.3’) víi Fj ∈Doc. Nh− vËy, bé ph©n líp kh«ng ph¶i duyÖt toµn bé tËp tõ khãa T mµ chØ ph¶i duyÖt trªn Vector cña tµi liÖu Doc. Mét ®iÒu ®¸ng chó ý n÷a lµ: C¸c gi¸ trÞ P(Ci) vµ c¸c ng−ìng CtgTshi lµ c¸c gi¸ trÞ ®−îc x¸c ®Þnh tr−íc th«ng qua nh÷ng ph©n tÝch tõ thùc tÕ. ViÖc x¸c ®Þnh c¸c tham sè nµy cµng chÝnh x¸c th× cµng lµm t¨ng ®é tin cËy cña bé ph©n líp. §Ó hiÓu râ h¬n sù ho¹t ®éng cña bé ph©n líp, ta xem xÐt vÝ dô 4.1 sau ®©y. VÝ dô 4.1 Gi¶ sö cã hai Catalog C1 vµ C2 cã c¸c tham sè nh− sau: Tham sè C1 C2 P(C) 0.5 0.5 Ng−ìng 0.75 0.6 Sè l−îng c¸c tõ khãa trong tËp tõ khãa T (tøc | T |) |µ 75. L−¬ng Song V©n Häc m¸y, häc m¸y m« t¶ phøc: thuËt to¸n vµ vÊn ®Ò rót gän lçi -82- HÖ thèng tõ khãa riªng cña c¸c Catalog (tøc lµ c¸c tõ xuÊt hiÖn cña c¸c tõ trong c¸c Catalog) C1 vµ C2 lµ nh− sau: Catalog C1 Catalog C2 Tõ khãa TÇn suÊt Tõ khãa TÇn suÊt X· héi 10 X· héi 15 Chñ nghÜa 20 T− b¶n 30 Céng hoµ 15 ViÖt Nam 30 Tµi liÖu Doc cã néi dung: “X· héi chñ nghÜa”. Vector cña tµi liÖu nµy lµ: ((X· héi,1), (Chñ nghÜa, 1)); Nh− vËy ta cã c¸c gi¸ trÞ tÝnh to¸n nh− sau: Víi Catalog C1: P(X· héi | C1)= 11/110; P(Chñ nghÜa | C1)= 21/110; Víi Catalog C2: P(X· héi | C2)= 16/90; P(Chñ nghÜa | C2)= 1/90; ( ) i n i l i TF F Doc F Doc P C P F C l l= ∈ ∑ ∏× 1 ( ) ( , ) = 0.6464; P(C1 | Doc) = 0.914; P(C2 | Doc) = 0.156; Nh− vËy P(C1 | Doc)= 0.914 > 0.75; do ®ã nã ®−îc ph©n vµo trong Catalog C1. Cßn P(C2 | Doc) = 0.156 < 0.6 do ®ã nã kh«ng ®−îc ph©n vµo trong Catalog C2. Bé ph©n líp ®· ph©n tµi liÖu Doc ®· cho vµo trong catalog C1 víi ®é chÝnh x¸c lµ 0.914%. Nh− vËy c¸c tµi liÖu tuy ®−îc ph©n vµo cïng mét catalog nh−ng L−¬ng Song V©n Häc m¸y, häc m¸y m« t¶ phøc: thuËt to¸n vµ vÊn ®Ò rót gän lçi -83- cã thÓ cã c¸c gi¸ trÞ P(C |Doc) hoµn toµn kh¸c nhau, gi¸ trÞ nµy cña chóng cµng cao th× ®é chÝnh x¸c cña nã cµng cao. IV.2.3. ThuËt to¸n ph©n líp Bayes thø hai Bé ph©n líp thø hai còng cã qu¸ tr×nh ho¹t ®éng hoµn toµn gièng bé ph©n líp Bayes thø nhÊt. Tuy nhiªn, c¸ch biÓu diÔn tµi liÖu Doc vµ c¸c tÝnh gi¸ trÞ P(C | Doc) lµ kh¸c víi bé ph©n líp thø nhÊt. C¸c th«ng tin sau còng ®−îc ®ßi hái: • TËp tõ khãa T – Cã ý nghÜa gièng nh− bé ph©n líp Bayes thø nhÊt. • X¸c suÊt P(Ci) – Cã ý nghÜa gièng nh− trªn. • C¸c ng−ìng CtgTsh i - Cã ý nghÜa gièng nh− trªn. Doc còng biÓu diÔn d−íi d¹ng mét vector, nh−ng kÝch th−íc cña vector nµy b»ng kÝch th−íc cña tËp tõ khãa T. Mçi thµnh phÇn cña vector sÏ gåm tõ khãa Fi vµ gi¸ trÞ 1 hoÆc 0 thÓ hiÖn tõ khãa Fi ®ã xuÊt hiÖn hay kh«ng xuÊt hiÖn trong tµi liÖu Doc. §iÒu nµy cã nghÜa lµ ®Ó tÝnh to¸n gi¸ trÞ P(C | Doc) th× bé ph©n líp nµy ph¶i ho¹t ®éng trªn toµn bé tËp tõ khãa T. C«ng thøc tÝnh to¸n gi¸ trÞ P(C | Doc) ®−îc m« t¶ d−íi ®©y: ( ) ( ) ( )∏∑ ∏ ∈= ∈ × × = TF ili n i TF j l j CFDocPCP CFDocPCP DocCP )()( )()( 1 (4.4) vµ ( ) ( )P Doc F C N Doc F C Dcj j ( ) ( )= + + 1 2 (4.5) Trong ®ã: • P(Doc(Fj) | C) lµ x¸c suÊt cã ®iÒu kiÖn ®Ó tõ khãa Fj trong líp C cã cïng gi¸ trÞ nh− trong tµi liÖu Doc, vµ ®−îc tÝnh to¸n sö dông c«ng thøc −íc l−îng x¸c suÊt Laplace nh− trong c«ng thøc (4.5). L−¬ng Song V©n Häc m¸y, häc m¸y m« t¶ phøc: thuËt to¸n vµ vÊn ®Ò rót gän lçi -84- • N(Doc(Fj) | C) lµ sè l−îng c¸c tµi liÖu thuéc catalog C cã cïng gi¸ trÞ cña tõ Fj víi tµi liÖu Doc. Tøc lµ, sè l−îng c¸c tµi liÖu thuéc catalog C cïng cã hoÆc cïng kh«ng cã tõ khãa Fj. • | Dc | lµ tæng sè c¸c tµi liÖu cã trong catalog C. Trong c«ng thøc (4.5) së dÜ cã sè 1 ë trªn tö sè lµ ®Ó tr¸nh tr−êng hîp N(Doc(Fj)|C)=0, cßn sè 2 ë mÉu lµ hai tr¹ng th¸i gi¸ trÞ cña tõ (xuÊt hiÖn hoÆc kh«ng xuÊt hiÖn trong tµi liÖu). Qu¸ tr×nh cßn l¹i hoµn toµn t−¬ng tù nh− bé ph©n líp Bayes thø nhÊt. Tøc lµ, so s¸nh P(C | Doc) víi ng−ìng CtgTsh ®Ó quyÕt ®Þnh tµi liÖu Doc cã thuéc vµo Catalog C hay kh«ng. VÝ dô 4.2 Gi¶ sö cã 2 Catalog C1 vµ C2 nh− sau: Catalog C1 C2 X¸c suÊt 0.5 0.5 Ng−ìng 0.7 0.6 Vµ Catalog C1 cã c¸c tµi liÖu: 1. Häc tèt ph¶i häc vµ häc. 2. Vµ häc m·i m·i m·i. 3. §· häc ph¶i häc. Cßn Catalog C2 cã c¸c tµi liÖu: 1. Sèng ®Ñp sèng m·i. 2. §Ñp nhÊt lµ sèng ®Ñp. 3. Cuéc sèng lµ ®Ñp. Tµi liÖu Doc cÇn ph©n líp lµ: “M·i ph¶i häc”. TËp tõ khãa T lµ: [ Häc, Tèt, Ph¶i, Vµ, M·i, §·, Sèng, §Ñp, Lµ, NhÊt]. TÝnh to¸n c¸c gi¸ trÞ cho Catalog C1 nh− sau: C¸c gi¸ trÞ cña catalog C1 C¸c gi¸ trÞ cña catalog C2 | Dc1 |=3 | Dc2 |=3 L−¬ng Song V©n Häc m¸y, häc m¸y m« t¶ phøc: thuËt to¸n vµ vÊn ®Ò rót gän lçi -85- N(Häc | C1)= 3; (Sè c¸c tµi liÖu trong Catalog C1 cã chøa tõ Häc- gièng nh− trong tµi liÖu Doc). N(Häc | C2)= 0; (Sè c¸c tµi liÖu trong Catalog C2 cã chøa tõ Häc- gièng nh− trong tµi liÖu Doc). N(Vµ | C1)=1; (Sè c¸c tµi liÖu trong Catalog C1 kh«ng chøa tõ Vµ- gièng nh− trong tµi liÖu Doc). N(Vµ | C2)= 3; (Sè c¸c tµi liÖu trong Catalog C2 kh«ng chøa tõ Vµ- gièng nh− trong tµi liÖu Doc). N(Ph¶i | C1)= 2 N(Ph¶i | C2)= 0 N(Tèt | C1)= 2 N(Tèt | C2)= 3 N(M·i | C1)=1 N(M·i | C2)=1 N(§· | C1)=2 N(§· | C2)=3 N(Sèng | C1)=3 N(Sèng | C2)=0 N(§Ñp | C1)=3 N(§Ñp | C2)=0 N(Lµ | C1)=3 N(Lµ | C2)=1 N(NhÊt | C1)=3 N(NhÊt | C1)=2 ( )∏ ∈ × TF j j CFDocPCP 11 )()( = 55296/510; ( )∏ ∈ × TF j j CFDocPCP 22 )()( =384/510; ( )∏∑ ∈= × TF ili n i l CFDocPCP )()( 1 =55680/510; VËy P(C1 | Doc)=0.993; P(C2 | Doc)=0.016; Do P(C1 | Doc)= 0.993 > 0.7 nªn tµi liÖu Doc ®−îc ph©n vµo trong Catalog C1; P(C2 | Doc)= 0.016 < 0.6 nªn tµi liÖu Doc kh«ng ®−îc ph©n vµo trong Catalog C2. ViÖc chän ng−ìng ph©n líp Nh− ®· tr×nh bµy trong ch−¬ng 1, c¸ch chän c¸c ng−ìng CtgTshi lµ ph¶i phï hîp. VÒ mÆt lÝ thuyÕt th× chän ng−ìng CtgTshi cµng cao th× khi ph©n tµi liÖu L−¬ng Song V©n Häc m¸y, häc m¸y m« t¶ phøc: thuËt to¸n vµ vÊn ®Ò rót gän lçi -86- vµo líp C ®ßi hái ph¶i cã x¸c suÊt P(C|Doc) lín h¬n ng−ìng vµ khi ®ã x¸c suÊt ®ã ph¶i cao vµ v× vËy, ®é chÝnh x¸c còng cao theo. Tuy nhiªn, nÕu chän c¸c ng−ìng qu¸ cao, th× cã thÓ x¶y ra tr−êng hîp mäi gi¸ trÞ P(Ci | Doc) ®Òu kh«ng v−ît qua ®−îc c¸c ng−ìng CtgTshi. §iÒu ®ã cã nghÜa r»ng tµi liÖu Doc kh«ng ®−îc ph©n vµo Catalog nµo c¶. VÝ dô 4.3 Gi¶ sö cã 3 Catalog C1, C2 vµ C3 lÇn l−ît cã c¸c ng−ìng lµ 0.7; 0.6; 0.5. Mét tµi liÖu Doc sau khi ®−îc tÝnh to¸n cho kÕt qu¶ nh− sau: P(C1 | Doc)=0.6; P(C2 | Doc)=0.3; P(C3 | Doc)=0.1; Khi ®ã tµi liÖu Doc sÏ kh«ng ®−îc ph©n vµo Catalog nµo trong 3 Catalog C1, C2, C3. Ng−îc l¹i, nÕu chän ng−ìng nhá qu¸ th× dÉn ®Õn t×nh huèng sau: • Thø nhÊt lµ vÒ ®é chÝnh x¸c cña tµi liÖu ®−îc ph©n lµ nhá. • Thø hai cã kh¶ n¨ng x¶y ra mét tµi liÖu cã thÓ ®−îc ph©n vµo nhiÒu nhãm cïng mét lóc. VÝ dô 4.4 Cã 3 Catalog nh− trªn nh−ng cã c¸c ng−ìng lµ 0.4; 0.5; 0.3; Vµ cã P(C1 | Doc)=0.5; P(C2 | Doc)=0.1; P(C3 | Doc)=0.4; Nh− vËy, tµi liÖu cïng mét lóc ®−îc ph©n vµo trong hai Catalog C1 vµ C3. §Ó chän ®−îc ng−ìng phï hîp th× c¸ch tèt nhÊt lµ sù kÕt hîp gi÷a ng−êi vµ m¸y. §iÒu nµy ®−îc thùc hiÖn b»ng c¸ch ta lÊy mét tµi liÖu ®· biÕt tr−íc ®−îc néi dung cña nã n»m ë trong Catalog nµo. Sau ®ã cho m¸y tù t×m ra c¸c P(Ci | Doc) vµ ph©n c¸c tµi liÖu ®ã vµo c¸c Catalog dùa trªn c¸c ng−ìng cò ®· cã. NÕu ta thÊy chóng ®−îc ph©n ®óng theo nh− kÕt qu¶ nh− ®· biÕt tr−íc th× gi÷ nguyªn l¹i c¸c ng−ìng cò. Ng−îc l¹i nÕu hÖ thèng ph©n kh«ng ®óng víi dù kiÕn th× tuú theo t×nh huèng cô thÓ mµ cã thÓ t¨ng hoÆc gi¶m c¸c ng−ìng cò nÕu thÊy cÇn thiÕt. IV.2.4. ThuËt to¸n ph©n líp "k_ng−êi l¸ng giÒng gÇn nhÊt" L−¬ng Song V©n Häc m¸y, häc m¸y m« t¶ phøc: thuËt to¸n vµ vÊn ®Ò rót gän lçi -87- Nh− ®· tr×nh bµy trong ch−¬ng 1, ®èi víi c¬ së d÷ liÖu full-text theo m« h×nh vector trªn ®©y, sù ho¹t ®éng cña thuËt to¸n kh«ng phô thuéc vµo tËp tõ khãa. Nãi c¸ch kh¸c, nã kh«ng dùa vµo tËp tõ khãa. Tuy nhiªn, thuËt to¸n vÉn sö dông c¸c ng−ìng Ctgtshi, vµ nã còng tuÇn tù ®i theo c¸c b−íc nh− ®· nãi ë trªn. Sù ho¹t ®éng cña nã lµ dùa vµo k tµi liÖu (lÊy ngÉu nhiªn) trong hÖ thèng, vµ tÝnh P(C/Doc) dùa vµo sù gièng nhau cña tµi liÖu Doc ®· cho víi k tµi liÖu ®−îc chän. Trong thuËt ng÷ "k ng−êi l¸ng giÒng gÇn nhÊt", chÝnh lµ chØ k tµi liÖu ®−îc chän. Cô thÓ c«ng thøc tÝnh P(C/ Doc) nh− sau: ( ) ( )( )∑ ∑ ∑ = = = × × = n i k l lil k l ll DCPDDocSm DCPDDocSm DocCP 1 1 1 ),( ),( (4.6) Trong ®ã: • k lµ sè l−îng tµi liÖu ®−îc chän ®Ó so s¸nh • n lµ sè catalog • P (Ci | Dl) cã gi¸ trÞ 1 hoÆc 0, chØ ra tµi liÖu Dl cã thuéc vµo catalog Ci hay kh«ng, së dÜ cã gi¸ trÞ nµy lµ bëi t¹i mét tµi liÖu cã thÓ ®−îc ph©n vµo nhiÒu h¬n mét catalog . • Sm (Doc, Dl) x¸c ®Þnh møc ®é gièng nhau cña tµi liÖu ®· cho Doc víi tµi liÖu ®−îc chän Dl. Nã ®−îc tÝnh b»ng cos cña gãc gi÷a hai vect¬ biÓu diÔn tµi liÖu Doc vµ tµi liÖu Dl theo c«ng thøc sau ®©y: Sm Doc D Cos Doc D X Y Sqrt X Yl l i ii j llj ( , ) ( , ) * ( ) = = ∑ ∑∑ 2 2 (4.7) Trong ®ã c¸c biÓu diÔn tµi liÖu hoµn toµn t−¬ng tù víi c¸ch biÓu diÔn cña bé phËn líp Bayes thø nhÊt. Tøc lµ nã gåm c¸c tõ khãa Fi vµ c¸c tÇn sè Xi t−¬ng øng. Trong c«ng thøc (4.7): • Xi lµ tÇn suÊt cña c¸c tõ trong tµi liÖu Doc. L−¬ng Song V©n Häc m¸y, häc m¸y m« t¶ phøc: thuËt to¸n vµ vÊn ®Ò rót gän lçi -88- • Yi lµ tÇn suÊt cña c¸c tõ trong tµi liÖu Dl. • Σi Xi *Yi lµ tæng cña c¸c tÝch c¸c tÇn suÊt cña c¸c tõ gièng nhau gi÷a hai tµi liÖu Doc vµ Dl. • Σj X2j lµ tæng b×nh ph−¬ng tÇn suÊt c¸c tõ cã trong tµi liÖu Doc. • Σl Y2l lµ tæng b×nh ph−¬ng tÇn suÊt c¸c tõ cã trong tµi liÖu Dl. • Sqrt(Σj X2j Σl Y2l) lµ c¨n bËc hai cña Σj X2j Σl Y2l . Ch¼ng h¹n, tµi liÖu Doc lµ ((Hµ Néi , 2) , (ViÖt nam , 3) , (céng hoµ ,1) , (chñ nghÜa,4)) Cßn tµi liÖu Dl lµ: ((Céng hoµ ,2) , (X· héi , 5) , (Chñ nghÜa , 3) , (ViÖt nam, 1)) Khi ®ã: Cos(Doc,Dl)=(2*1+3*4+3*1)/ sqrt((2 2 +32+12+42)*(22 +52+32+12)) =0.497 Qu¸ tr×nh cßn l¹i hoµn toµn t−¬ng tù nh− c¸c bé phËn líp ë trªn. Tøc lµ nã còng so s¸nh gi¸ trÞ P(C | Doc) víi ng−ìng CtgTsh cña Catalog C ®Ó xem nã cã thuéc vµo trong Catalog ®ã kh«ng. VÝ dô 4.5 nh− ®−îc tr×nh bµy d−íi ®©y m« t¶ ho¹t ®éng cña thuËt to¸n. VÝ dô 4.5 Gi¶ sö cã 2 catalog C1vµ C2 víi c¸c ng−ìng t−¬ng øng lµ 0.67 vµ 0.6. Tµi liÖu Doc cÇn ®−îc ph©n líp lµ: “Chñ nghÜa x· héi”. C¸c tµi liÖu ®−îc chän ra ®Ó so s¸nh lµ: 1. “ Céng hoµ x· héi chñ nghÜa ViÖt Nam” thuéc catalog C1. 2. “ X· héi x· héi chñ nghÜa” thuéc C1. 3. “ Chñ nghÜa ®Õ quèc, x· héi t− b¶n” thuéc catalog C2. Qu¸ tr×nh tÝnh to¸n diÔn ra nh− sau: C¸c vector biÓu diÔn c¸c tµi liÖu lµ: • D1 = ((céng hoµ,1), (x· héi, 1), (chñ nghÜa, 1), (ViÖt Nam, 1)). • D2 = ((X· héi, 2), (chñ nghÜa, 1)). L−¬ng Song V©n Häc m¸y, häc m¸y m« t¶ phøc: thuËt to¸n vµ vÊn ®Ò rót gän lçi -89- • D3 = ((x· héi, 1), (chñ nghÜa, 1), (§Õ quèc, 1), (t− b¶n, 1)). • Doc = ((x· héi, 1), (chñ nghÜa, 1)). • Cos (Doc, D1)= 0.716; • Cos (Doc, D2) = 0.949; • Cos (Doc, D3) = 0.716; • ( )Sm Doc D P C Dl i l l k i n ( , ) × == ∑∑ 11 = 2.362; Vµ: • P(C1 | Doc) = 0.70; • P(C2 | Doc) = 0.30; KÕt qu¶ cuèi cïng lµ: P(C1 | Doc)=0.7 > 0.67 nªn tµi liÖu Doc ®−îc ph©n vµo trong Catalog C1. Ng−îc l¹i, P(C2 | Doc)=0.3 < 0.6 nªn tµi liÖu Doc kh«ng ®−îc ph©n vµo trong Catalog C2. Chó ý vÒ n©ng cao chÊt l−îng thuËt to¸n ViÖc x¸c ®Þnh k sè l−îng tµi liÖu mÉu vµ c¸ch chän nh÷ng tµi liÖu mÉu nµo ®Ó tÝnh to¸n c¸c kho¶ng c¸ch nãi trªn cã ý nghÜa quan träng ®èi víi chÊt l−îng cña thuËt to¸n. Mét trong nh÷ng c¸ch hiÖu qu¶ lµ dùa theo kinh nghiÖm vµ sù kÕt hîp gi÷a ng−êi vµ m¸y. L−¬ng Song V©n Häc m¸y, häc m¸y m« t¶ phøc: thuËt to¸n vµ vÊn ®Ò rót gän lçi -90- PhÇn kÕt luËn LuËn v¨n ®· xem xÐt mét sè néi dung trong m« h×nh häc m¸y cã gi¸m s¸t. Häc m¸y lµ mét lÜnh vùc ®−îc coi lµ liªn quan mËt thiÕt ®Õn c«ng nghÖ tri thøc. Tïy thuéc vµo l−îng th«ng tin ®· cã ®Ó ph©n lo¹i häc m¸y thµnh häc m¸y kh«ng gi¸m s¸t vµ häc m¸y cã gi¸m s¸t. Bµi to¸n häc m¸y cã gi¸m s¸t ®· cã nhiÒu kÕt qu¶ trong khi ®ã bµi to¸n häc m¸y kh«ng gi¸m s¸t l¹i cßn rÊt Ýt kÕt qu¶. Trong häc m¸y cã gi¸m s¸t, ®· cã nhiÒu thuËt to¸n gi¶i quyÕt c«ng viÖc ph©n líp ®èi t−îng trong ®ã ®iÓn h×nh nhÊt cã thÓ kÓ ®Õn c¸c thuËt to¸n Bayes, thuËt to¸n k-ng−êi l¸ng giÒng gÇn nhÊt, thuËt to¸n c©y quyÕt ®Þnh v.v. Trong m« h×nh häc m¸y m« t¶ phøc, mçi kh¸i niÖm t−¬ng øng mét tËp c¸c luËt vµ d÷ liÖu ®−îc xem xÐt kh«ng chØ tõng tËp hîp d÷ liÖu ®¬n lÎ mµ cßn ®−îc xem xÐt theo nhiÒu tËp hîp d÷ liÖu. NhiÒu c«ng tr×nh nghiªn cøu cho thÊy, m« h×nh häc m¸y m« t¶ phøc cho kÕt qu¶ häc m¸y chÝnh x¸c h¬n so víi m« h×nh ®¬n t−¬ng øng. Bµi to¸n häc m¸y ®−îc gÆp trong nhiÒu lÜnh vùc kh¸c nhau trong c«ng nghÖ tri thøc vµ mét sè d¹ng cña häc m¸y còng ®−îc t×m thÊy trong c¬ së d÷ liÖu full-text. Bµi to¸n ph©n líp tµi liÖu trong c¬ së d÷ liÖu full- text lµ mét bµi to¸n kh¸ phæ biÕn: Cã thÓ sö dông mét sè thuËt to¸n häc m¸y cã gi¸m s¸t theo m« h×nh vector cña c¬ së d÷ liÖu full-text. LuËn v¨n ®· thùc hiÖn ®−îc mét sè néi dung chÝnh nh− sau: - Tr×nh bµy ®−îc mét c¸ch nh×n nhËn tæng quan vÒ bµi to¸n häc m¸y, ph©n lo¹i bµi to¸n häc m¸y vµ mét sè thuËt to¸n chÝnh. Néi dung tæng quan nµy ®−îc tËp hîp tõ nhiÒu nguån tµi liÖu kh¸c nhau, ë trong n−íc còng nh− ngoµi n−íc. - Tr×nh bµy ®−îc nh÷ng néi dung c¬ b¶n vÒ häc m¸y m« t¶ phøc. LuËn v¨n ®· tr×nh bµy nh÷ng nÐt c¬ b¶n nhÊt vÒ c¸c m« h×nh häc m¸y m« t¶ phøc nh− FOIL, FOCL, HYDRA, HYDRA-MM. KÕt qu¶ cña néi dung nµy ®−îc L−¬ng Song V©n Häc m¸y, häc m¸y m« t¶ phøc: thuËt to¸n vµ vÊn ®Ò rót gän lçi -91- tËp hîp chñ yÕu tõ nhiÒu c«ng tr×nh nghiªn cøu cña nhãm häc m¸y t¹i tr−êng §¹i häc Tæng hîp California, Ivrin. - Tr×nh bµy néi dung c¬ b¶n vÒ c¬ së d÷ liÖu full-text. LuËn v¨n ph¸t triÓn ®Ò xuÊt c¶i tiÕn m« h×nh vector, bao gåm viÖc xem xÐt tÇn suÊt xuÊt hiÖn c¸c tõ khãa trong tµi liÖu còng nh− vÊn ®Ò tõ ®ång nghÜa. LuËn v¨n còng tr×nh bµy mét sè thuËt to¸n ph©n líp tµi liÖu ®èi víi c¬ së d÷ liÖu full-text. Mét sè kÕt qu¶ c¶i tiÕn ë ®©y tuy cã gi¸ trÞ ch−a cao song thùc sù ®−îc ph¸t triÓn bëi chÝnh luËn v¨n trªn c¬ së cña [5, 13]. Do cßn cã h¹n chÕ vÒ ®iÒu kiÖn, vÒ kh¶ n¨ng triÓn khai trªn m¸y tÝnh nªn luËn v¨n cßn cã khiÕm khuyÕt lµ ch−a thÓ hiÖn ®−îc mét cµi ®Æt cô thÓ c¶ vÒ bµi to¸n häc m¸y m« t¶ phøc lÉn bµi to¸n t×m kiÕm vµ ph©n líp trong c¬ së d÷ liÖu full-text. C¸c thuËt to¸n häc m¸y ®−îc gÆp kh¸ phæ biÕn trong c¸c qu¸ tr×nh kh¸m ph¸ trÝ thøc trong c¸c c¬ së d÷ liÖu (KDD: Knowledge Discovery in Databases) vµ ®©y lµ lÜnh vùc ®Þnh h−íng nghiªn cøu tiÕp cña luËn v¨n. L−¬ng Song V©n Häc m¸y, häc m¸y m« t¶ phøc: thuËt to¸n vµ vÊn ®Ò rót gän lçi -92- Tµi liÖu tham kh¶o Tµi liÖu tiÕng ViÖt 1. Hå Tó B¶o. Mét sè kÕt qu¶ nghiªn cøu vÒ c«ng nghÖ tri thøc. B¸o c¸o Héi nghÞ Khoa häc ViÖn C«ng nghÖ Th«ng tin. Hµ Néi 5&6-12-1996, trang 18- 25. 2. Hå Tó B¶o. Häc tù ®éng kh«ng gi¸m s¸t trªn dµn Galois víi d÷ liÖu thay ®æi. B¸o c¸o Héi nghÞ Khoa häc ViÖn C«ng nghÖ Th«ng tin. Hµ Néi 5&6-12- 1996, trang 27-36. 3. Hµ Quang Thôy. TËp th« trong b¶ng quyÕt ®Þnh. T¹p chÝ Khoa häc §¹i häc Quèc gia Hµ Néi. TËp 12. Sè 4-1996, trang 9-14. 4. NguyÔn ThÞ V©n. X©y dùng c¬ së d÷ liÖu Full-Text. LuËn v¨n tèt nghiÖp §¹i häc, Khoa CNTT, 1998. Tµi liÖu tiÕng Anh 5. Ali K. & Pazzani M.. Error Reduction through Learning Multiple Descriptions Machine Learning, 24:3, 1996. 6. Ali K., Brunk C. & Pazzani M.. Learning Multiple Relational Rule-based Models. In "Preliminary Papers of the 5th International Workshop on Artificial Intelligence and Statistics". Fort Lauderdale, FL, 1995. 7. Ali K. & Pazzani M.. HYDRA-MM: Learning Multiple Descriptions to Improve Classification Accuracy. International Journal on Artificial Intelligence Tools, 4, 1995. 8. Ali K., Brunk C. & Pazzani M. On Learning Multiple Descriptions of a Concept. In Proceedings of the Sixth International Conference on Tools with Artificial Intelligence. New Orleans, LA: IEEE Press, 1994. L−¬ng Song V©n Häc m¸y, häc m¸y m« t¶ phøc: thuËt to¸n vµ vÊn ®Ò rót gän lçi -93- 9. Bay S. D. Combining Nearest Neighbor Classifiers Through Multiple Feature Subsets. Proceedings of the International Conference on Machine Learning. Morgan Kaufmann Publishers. Madison, Wisc., 1998. 10. Billsus D. & Pazzani M. Learning probabilistic user models. In workshop notes of Machine Learning for User Modeling, Sixth International Conference on User Modeling, Chia Laguna, Sardinia, 2-5 June 1997. 11. Bruce Moxon. Defining Data mining. DBMS Data Warehouse Supplement, August 1996. 12. Domingos P. Knowledge Acquisition from Examples Via Multiple Models. Proceedings of the Fourteenth International Conference on Machine Learning, 1997. Nashville, TN: Morgan Kaufmann. 13. Dunja Mladenic'. Machine Learning on non-homogeneous, distbuted text data (Chapter 3. Document representation and learning algorithms). Doctoral dissertation. University of Ljubljana, Slovenia. 1998. 14. Hume T. & Pzzani M. Learning Sets of Related Concepts: A Shared Task Model. Proceedings of the Sixteen Annual Conference of the Cognitive Science Society. Pittsburgh, PA: Lawrence Erlbaum, 1995. 15. Merz C. & Pazzani M. Handling Redundancy in Ensembles of Learned Models Using Principal Components. AAAI Workshop on Integrating Multiple Models, 1997. 16. Pazzani M. & Billsus D. Learning and Revising User Profiles: The identification of interesting web sites. Machine Learning 27, 313-331, 1997. 17. Shankle W. S., Datta P., Pazzani M. & Michael D. Improving dementia screening tests with machine learning methods. Alzheimer's Research, June, 1996, vol. 2 no. 3. L−¬ng Song V©n Häc m¸y, häc m¸y m« t¶ phøc: thuËt to¸n vµ vÊn ®Ò rót gän lçi -94- 19. Peter Cheeseman, John Stutz. Bayesian Classification (AutoClass): Theory and Results. Advances in Knowledge Discovery and Data Mining. AAAI Press / The MIT Press 1996. 153-180. 20. Pazzani M., Kibler D. The Utility of Knowledge in Inductive Learning. Machine Learning, 9 , 54-97, 1992.