Đ i H c Qu c gia TPHCM ố ạ ọ

Công ngh tri th c ệ và ng d ng

GS.TSKH. Hoàng Ki mế

N i dung môn h c ộ ọ

M đ u: Gi

i thi u t ng quan

ở ầ

ệ ổ

Ph n I: Qu n lý tri th c (knowledge management)

Ch

ngươ 1: Ti p nh n, bi u di n tri th c

ế

Ch

ngươ 2: T i u hóa CSTT ố ư

Ph n II: Các h CSTT (knowledge-based systems)

Ch

ngươ 3: Bên trong m t h CSTT

ộ ệ

Ch

ngươ 4: Phân lo i các h CSTT ạ

Ch

ngươ 5: M t s h đi n hình

ộ ố ệ ể

ỏ ữ ệ

Ph n III: Khai m d li u và khám phá tri th c (Data mining and Knowledge Discovery)

Ch

ngươ 6: Máy h c & khám phá tri th c.

Ch

ngươ 7: Khai m d li u.

ỏ ữ ệ

T ng k t: Tóm t t, gi

ế

ổ ậ i thi u m t s công trình n i b t

ộ ố

Mở đầu: Giới thiệu tổng quan

Công nghệ tri thức là gì ?

ể ữ

ư

philosophical,

 Công ngh tri th c (Knowledge ứ Engineering): có th xem là m t ể nhánh nghiên c u c a trí tu nhân ứ ủ t o, phân tích tri th c lĩnh v c và ứ ạ chuy n nó thành nh ng mô hình tính toán đ a vào máy tính đ ph c ể ụ v nh ng nhu c u c n thi ế . (John t ầ ầ ụ ữ F.Sowa. Knowledge representation: and Logical, Computational Foundations. Copyright @2000 by Brooks/Cole. A division of Thomson Learning)

Công ngh tri th c là gì ? (tt) ứ ệ

ươ

ữ ứ

ữ ư ệ

ệ ơ ở ế ị ứ

 Công ngh tri th c (Knowledge Engineering): là các ph ng ệ ứ c nh ng k s tri th c (knowledge engineers) pháp, k thu t đ ậ ượ ỹ ỹ ư dùng đ xây d ng nh ng h th ng thông minh nh : h chuyên ệ ố ự ể gia, h c s tri th c, h h tr quy t đ nh, etc. (Dr Dickson ệ ổ ợ Lukose. Department of Mathematics, Statistics and Computer Science - The University of New England. Dr Rob Kremer Department of Computer Science The University of Calgary Calgary, Alberta, T2N 1N4 Canada. Courses: KNOWLEDGE ENGINEERING, PART A: Knowledge Representation. July 1996)

ươ ng pháp, k thu t dùng ỹ ậ ứ ữ ệ

 Công ngh tri th c là nh ng ph đ : ể

ậ ế

ễ ệ ơ ở ự

 Ti p nh n, bi u di n tri th c. ứ ể  Xây d ng các h c s tri th c ứ  Khám phá tri th cứ

Khoa h c tri th c (knowledge science) ứ ọ

Vai trò c a công ngh tri th c ứ ủ ệ

ớ ự ệ

ỉ ả ườ ườ ữ

ng, ng ơ ệ ườ

 Cùng v i s phát tri n nhanh chóng, v công nghi p máy tính, nhu c u c a ng ườ ầ ủ tính ngày m t cao h n: không ch gi ơ ộ l u tr , tính toán bình th ư tính có kh năng thông minh h n, có th gi ả nh con ng ừ bi t b c c a ngành ượ ậ ủ i dùng đ i v i máy ố ớ i quy t nh ng công vi c ữ ế i dùng còn mong đ i máy ợ i quy t v n đ ề ể ả ế ấ đó trí tu nhân t o nói chung và đ c ư ặ ạ t là công ngh tri th c ra đ i và phát tri n ể ứ ệ i. Và t ệ ờ

ế ứ ứ

 Công ngh tri th c đóng vai trò h t s c quan tr ng trong ệ vi c phát tri n Công ngh thông tin, nâng cao s h u d ng ể ệ c a máy tính, giúp con ng ủ ọ ự ữ i g n gũi v i máy tính h n. ơ ệ ườ ầ ớ

ệ ứ ề ầ

ọ ự ẩ ể ọ ể

 Công ngh tri th c còn góp ph n thúc đ y nhi u ngành khoa h c khác phát tri n, kh năng phát tri n khoa h c d a ả trên tri th c liên ngành ứ

…

ARTIFICIAL INTELLIGENCE

ROBOTICS

NATURAL LANGUAGE  PROCESSING

KNOWLEDGE ­ BASED  SYSTEMS

EXPERT SYSTEMS

MACHINE LEARNING

Các lĩnh v c trong thông minh nhân t o (AI) ự ạ

Áp d ng các khái ni m c a AI vào máy tính ủ ụ ệ

KNOWLEDGE BASE

INFERENCING CAPABILITY

fi Inputs (questions, fi problems, ..) fi

fi fi fi

Outputs (answers, solutions, ..)

ộ ụ

ọ ủ

ườ

ế ố ơ ả

 M t trong nh ng m c tiêu quan ữ tr ng c a lĩnh v c nghiên c u này ứ ự là làm cho máy tính có kh năng ả i quy t v n đ ti p nh n, gi ề ấ ế ậ gi ng nh con ng i, th m chí ậ ư i (máy tính IBM h n c con ng ườ Deep Blue đã chi n th ng vua c ờ ế Kasparov).

ướ ứ ệ ể ứ H ng nghiên c u, phát tri n công ngh tri th c

MÁY TÍNH

KHAI THÁC DỮ LIỆU,  KHÁM PHÁ TRI THỨC

TIẾP NHẬN, BIỂU DIỄN,  TỐI ƯU HÓA CSTT

CÁC HỆ  CƠ SỞ TRI THỨC

inputs Outputs

bao g m ti p nh n, bi u di n và ậ

ế

 Qu n lý tri th c (knowledge management): t ứ ố ư

i u hóa c s tri th c… ơ ở

ệ ơ ở

tìm hi u c u trúc bên ấ ứ phân lo i các h c s tri th c, và m t s h ộ ố ệ

ệ ơ ở

ể ứ

 Các h c s tri th c (knowledge-based systems): trong c a m t h c s tri th c, ộ ệ ơ ở c s tri th c đi n hình. ể ứ ơ ở

ỏ ữ ệ ề

ỏ ữ ệ

ươ

 khai m d li u, khám phá tri th c (Data mining, knowledge discovery): ứ nghiên c u v ph ng pháp, k thu t đ khai m d li u và khám phá tri ậ ể ứ th c. ứ

Đ a tri th c vào máy tính ư ứ

(cid:219) i u hóa ậ ể ễ ố ư • Nh n th c ứ ậ

Ti p nh n, bi u di n và t ế c s tri th c ứ ơ ở

(cid:219) • Suy lu nậ Đ ng c suy di n ễ ơ ộ

(cid:219) Ph n ng, tr l • Ph n ng ả ứ ả ứ i ả ờ

(cid:219) “B x lý tình c m” ? • Tình c mả ộ ử ả

Qu n lý tri th c: Ti p nh n tri th c ứ ứ ế ả ậ

Có th chia thành 2 cách đ ti p nh n tri th c nh sau: ể ế ứ ư ể ậ

 Th đ ng ụ ộ

- Gián ti p: nh ng tri th c kinh đi n. ứ ữ ế ể

ự ế ứ ể ệ

-Tr c ti p: nh ng tri th c kinh nghi m (không kinh đi n) do ữ “chuyên gia lĩnh v c” đ a ra. ự ư

 Ch đ ng ủ ộ

ữ ệ ố ứ

ố ớ ả ự ứ ể ễ

- Đ i v i nh ng tri th c ti m n, không rõ ràng h th ng ề ẩ phân tích, suy di n, khám phá đ có thêm tri th c ph i t m i ớ

Qu n lý tri th c: Ti p nh n tri th c ứ ứ ế ả ậ

 Giao tiếp người­máy

In: Keyboard, Mouse, sensors, touch­pad,  touchable screen, speech­recognition, …

Out: text, graphics, voice, …

Con người

Bộ xử lý ngôn  ngữ tự nhiên

Qu n lý tri th c: Bi u di n tri th c ứ ứ ể ễ ả

ươ ng pháp bi u di n tri ể ễ

 Ph th cứ

Logic m nh đ & logic v t ị ừ ệ ề

H lu t d n ệ ậ ẫ

Đ i t ố ượ ng-thu c tính-giá tr ị ộ

M ng ng nghĩa ữ ạ

Frame

Script

…

Qu n lý tri th c: T i u c s tri th c ứ ố ư ơ ở ứ ả

T i sao t i u c s tri th c ? ạ ố ư ơ ở ứ

ề ẫ ắ

ứ ậ ậ

 V n đ mâu thu n, trùng l p, d th a n y sinh khi tri th c ứ ấ c ti p nh n và bi u di n trong c s tri th c. Vì v y đòi h i đ ỏ ượ ế chúng ta ph i có ph ư ừ ả ơ ở i u c s tri th c. ể ố ư ơ ở ễ ể ng pháp đ t ươ ứ ả

ng ộ ẽ ể ươ

 Tùy thu c vào cách bi u di n tri th c, chúng ta s có ph ứ ễ i u c s tri th c. pháp thích h p đ t ợ ể ố ư ơ ở ứ

ạ ỏ ậ ừ ề

Ví d :ụ đi n hình cho v n đ này là bài toán lo i b lu t th a ấ trong c s tri th c lu t. ể ơ ở ứ ậ

T ng quan h c s tri th c ứ ệ ơ ở ổ

Tri th cứ

C s tri th c ứ

ơ ở

Ti p nh n ậ ế tri th cứ

(s ki n, lu t, …)

ự ệ

Vùng nh ớ làm vi cệ

Gi i thích ả Đ ng c suy di n ơ ễ ộ

Tìm ki mế

Đi u khi n ề ể

B x lý ộ ử ngôn ng ữ t nhiên ự

Các h c s tri th c: đóng, m , k t h p ứ ở ế ợ ệ ơ ở

ứ ượ ữ

là nh ng h c s tri th c đ ệ ơ ở ự ứ ộ ố ầ

ạ ộ ữ ố

 H c s tri th c đóng: c ệ ơ ở xây d ng v i m t s “tri th c lĩnh v c” ban đ u, và ch ớ ỉ ứ ự nh ng tri th c đó mà thôi trong su t quá trình ho t đ ng ứ hay su t th i gian s ng c a nó. ủ ố ờ ố

ữ ườ ệ ơ ở ữ ị ứ ả

Ví d :ụ nh ng h c s tri th c v kinh d ch, nh ng h gi i ả ữ ệ ứ ề i quy t v n ng là nh ng h c s tri th c gi toán, th ế ấ ệ ơ ở đ … ề

Các h c s tri th c: đóng, m , k t h p (tt) ở ế ợ ệ ơ ở ứ

ứ ở là nh ng h c s tri th c tiên ti n ứ

ệ ơ ở ứ ả

H c s tri th c m : ế ữ h n, nó có kh năng b sung tri th c trong quá trình ho t ạ ổ đ ng, khám phá. ệ ơ ở ơ ộ

ổ ứ

ứ ữ

ệ ả ậ ứ ổ ề ữ ị

ầ ữ ệ ơ ở ớ ẩ ứ

i toán cho phép b sung tri th c trong Ví d :ụ Nh ng h gi ữ quá trình suy lu n (tri th c ban đ u là nh ng tiên đ và m t ộ s đ nh lý, tri th c b sung là nh ng đ nh lý m i, nh ng tri ố ị th c heurictis, …); nh ng h c s tri th c ch n đoán, d ự ứ ữ báo ch ng h n: h ch n đoán y khoa MYCIN và EMYCIN, ệ ẩ ạ nh ng h d báo th i ti ệ ự t, khí h u, đ ng đ t, … ộ ờ ế ữ ấ ậ

Các h c s tri th c: đóng, m , k t h p (tt) ở ế ợ ệ ơ ở ứ

ệ ơ ở ự ế ợ ồ

ứ ế ợ ệ ở ệ ế ợ

ớ ộ ệ ữ ệ ữ

ng phát tri n m nh d a trên tri th c ườ ự ứ ể ạ

H c s tri th c k t h p: bao g m s k t h p gi a h ữ ệ đóng và h m , h k t h p gi a CSTT và CSDL, h k t h p ệ ế ợ ữ gi a h CSTT này v i m t h CSTT khác, … Nh ng h c s ệ ơ ở tri th c k t h p th ứ ế ợ liên ngành.

ữ ế ị ệ ỗ ợ ờ ố

ụ ọ

vi áp d ng v i đ i s ng; kinh ử ọ ớ ờ ố ệ ẩ ị ớ ữ ử ị

Ví d :ụ nh ng h h tr ra quy t đ nh trong đ i s ng, kinh tế và khoa h c; (kinh d ch, t d ch, t ụ báo dòi h i tri th c liên ngành; … ứ vi áp d ng v i y h c; …); nh ng h ch n đoán, d ự ỏ

ng pháp bi u Các h c s tri th c: phân lo i theo ph ứ ệ ơ ở ạ ươ ể

di n tri th c ứ ễ

ng pháp bi u di n tri th c mà chúng ta có ươ ể ứ ễ

Tùy thu c vào ph ộ th phân lo i các h c s tri th c ứ ệ ơ ở ể ạ

H c s tri th c d a trên logic m nh đ và logic v t ệ ơ ở ứ ự ị ừ ệ ề

H c s tri th c d a trên lu t d n ứ ự ệ ơ ở ậ ẫ

H c s tri th c d a trên đ i t ng ệ ơ ở ứ ự ố ượ

H c s tri th c d a trên Frame ệ ơ ở ứ ự

ứ ự ệ ơ ở ữ ạ

ng pháp bi u di n đã nêu ộ ố ươ ể ễ

H c s tri th c d a trên m ng ng nghĩa … H CSTT k t h p m t s ph ế ợ ệ trên.

Các h c s tri th c: phân lo i theo ng d ng ệ ơ ở ứ ụ ứ ạ

ng là h có tính ch t đóng, ấ ườ ệ

i quy t v n đ : th ế ấ ề ệ

i toán, thu t gi i V ng H o, thu t ệ ả ậ ả ươ ạ ậ

H gi ệ ả nh ng đôi khi cũng có h mang tính m . ở ư Ví d :ụ Nh ng h gi ữ i Robinson, … gi ả

ng là các h mang tính k t h p ế ị ệ ỗ ợ ườ ệ

ứ ọ ố ượ ế ợ ng s ử

H h tr quy t đ nh: th (CSDL + tri th c ngành + hàm toán h c + ..), đ i t d ng là các nhà lãnh đ o. ụ ạ

ữ ệ ố

ế ệ ệ ụ ả

ệ ố ữ ệ ấ ả

Ví d :ụ nh ng h th ng đánh giá doanh nghi p (tình hình tài chính, k t qu kinh doanh, qui trình nghi p v , qui trình s n ả xu t, tính chuyên nghi p trong qu n lý, …), nh ng h th ng l p k ho ch (planning), … ậ ế ạ

Các h c s tri th c: phân lo i theo ng d ng (tt) ệ ơ ở ứ ứ ụ ạ

ng cũng gi ng nh ư ố

ệ ự ữ ườ ế ị ớ ạ

ẩ ẩ

ứ ự

H d báo, ch n đoán: th ẩ nh ng h h tr ra quy t đ nh v i tính ngo i ệ ỗ ợ suy cao h n.ơ Ví d :ụ Bài toán ch n đoán h ng hóc xe, ch n ỏ ng ch ng khoán, đoán y khoa, d báo th tr ị ườ th i ti t … ờ ế

ệ ề ệ ề ắ

ể ữ

ườ

H đi u khi n: là nh ng h đi u khi n có g n ữ ể v i CSTT. Nh ng h th ng này th ng ng ườ ứ ệ ố ớ d ng trong công nghi p, trong đi u khi n t ể ự ụ ề ệ ng là nh ng h th ng th i gian đ ng hóa, th ờ ệ ố ữ ộ th c (real-time systems). M t s h th ng này có ộ ố ệ ố ự s d ng k t h p lý thuy t m đ x lý. ờ ể ử ế ử ụ ế ợ

c v i b đi u ơ ướ ớ ộ ề

Ví d :ụ Máy gi t, Máy b m n ặ khi n m , … ờ ể

Máy h c và khám phá tri th c ứ ọ

ế

ứ ề ẩ ữ

Th nào là khám phá tri th c (knowledge discovery) ? ứ  Khám phá tri th c là tìm ra nh ng tri th c ti m n, nh ng tri th c m i (không ph i là nh ng tri th c kinh đi n, kinh nghi m, …) ữ ệ ứ ả ữ ứ ứ ớ ể

Th a d li u, thông tin nh ng thi u tri th c. ừ ữ ệ ư ứ ế

Tri thức

Thông tin

Mức độ  trừu  tượng

Dữ liệu

Số lượng

Máy h c và khám phá tri th c (tt) ứ ọ

Ví d :ụ Trong toán h cọ

 D li u: 1, 1, 2, 3, 5, 8, 13, 21, 34, … ữ ệ

c bi u di n b ng công th c sau: U ể ượ ễ ằ ứ ể

n =

M i liên h này có th đ ệ ố Un-1 + Un-2

(cid:222) Công th c tìm ra ứ ở trên chính là tri th c ứ

Ví d :ụ Trong v t lýậ

Công th c: U = IxR là tri th c rút ra t th c nghi m ứ ứ ừ ự ệ

ư ừ ồ ồ ắ ấ

Ví d :ụ Chu n chu n bay th p thì m a, bay cao thì n ng, bay v a thì râm

(cid:222) L i nh n xét trên là tri th c rút ra t ứ ờ ậ ừ kinh nghi m đ i s ng. ệ ờ ố

Máy h c và khám phá tri th c (tt) ứ ọ

Th nào là máy h c (Learning Machine) ? ọ ế

ng trình máy tính có kh năng t hoàn thi n ươ ả ự ệ

 Máy tính hay ch t “kinh nghi m”. ừ ệ

ọ ườ

 Máy h c còn có nghĩa là vi c mô hình hóa môi tr ng xung ệ quanh hay kh năng m t ch ng trình máy tính sinh ra m t c u ộ ấ ươ ộ ả trúc d li u m i khác v i c u trúc hi n có. Ch ng h n vi c tìm ệ ẳ ớ ấ ớ ệ t p d li u đ u vào. ra nh ng lu t ừ ậ ữ ệ ầ ậ If…then… t ữ ệ ữ

(Krzysztof J. Cios, Witold Pedrycz, Roman W. Swiniarski. Data Mining Methods for Knowledge Discovery. Kluwer Academic Publishers, 1998)

Máy h c và khám phá tri th c (tt) ứ ọ

ng pháp máy h c: ươ ọ có nhi u quan đi m phân ể ề

Phân lo i các ph ạ lo i khác nhau ạ

Phân lo i thô: ạ

 H c giám sát (supervised learning) ọ

 H c không giám sát (unsupervised learning) ọ

: “c p đ h c” & “cách ti p ạ ẩ ấ ộ ọ ế

Phân lo i theo 2 tiêu chu n cùng lúc c n”ậ

ấ ộ ọ C p đ h c:

 H c v t (Rote learning) ọ ẹ

 H c theo gi i thích (by explanation) ọ ả

 H c theo ví d , tr ng h p (by examples, cases) ụ ườ ọ ợ

 H c khám phá (by discovering) ọ

Máy h c và khám phá tri th c (tt) ứ ọ

Cách ti p c n: ế ậ

 Ti p c n th ng kê ế ậ ố

 Ti p c n toán t logic ế ậ ử

ế ậ ọ ạ

 Ti p c n hình h c (phân ho ch không gian, xây d ng cây đ nh danh, …) ị ự

 Ti p c n m ng Neural ế ậ ạ

 Ti p c n khai m d li u ỏ ữ ệ ế ậ

…

Nhà kho d li u và khai m d li u ỏ ữ ệ ữ ệ

ạ ứ

T o DATA WAREHOUSE = Bi n đ i d li u thành tri th c . y m tr ti n trình ra quy t đ nh ễ ế ổ ữ ệ ế ị ợ ế

D li u ữ ệ

Khoa h cọ

Giáo d cụ

Công nghệ T o Data Warehouse ạ

Data  warehouse

Kinh doanh

Th tr ng ị ườ

ợ Th i ti t ờ ế

Tri th c y m tr ra ứ ễ quy t đ nh ế ị

Nhà kho d li u và khai m d li u (tt) ỏ ữ ệ ữ ệ

DatawareHouse = Business Information + Decision Making

(IBM BPEC’96 Conference, San Diego, USA)

ự ổ ủ ớ ượ ễ ả ị

ộ ủ ườ ạ ầ

ự ộ ộ

t quá kh năng di n d ch và i, phát sinh yêu c u sáng t o các công c k ụ ỹ đ ng t cho ti n trình ra quy t ớ ể ạ ứ ữ ụ ỗ ợ ố ế ế

S bùng n c a các CSDL l n v lĩnh h i c a con ng thu t m i đ phân tích d li u m t cách thông minh và t ậ ữ ệ nh m t o ra tri th c h u d ng h tr t ằ đ nh. ị

(Usama, Data Mining and Knowledge Discovery, 1995)

Nhà kho d li u và khai m d li u (tt) ỏ ữ ệ ữ ệ

M t s bài toán đi n hình v data mining ộ ố ể ề

Bài toán khám phá lu t k t h p ậ ế ợ

Bài toán nh n d ng m u ậ ạ ẫ

Bài toán phân lo i d li u ạ ữ ệ

Bài toán gom nhóm d li u ữ ệ

Bài toán l p mô hình ậ

Bài toán d báoự

ơ ở

ế

[1] GS.TSKH Hoàng Ki m. Bài gi ng cao h c môn h c c s tri th c và ng d ng. ĐHKHTN-TPHCM.

ế

[2] GS.TSKH Hoàng Ki m.Th vi n nh ng báo cáo khoa h c, bài thu ho ch môn c s ơ ở tri th c và ng d ng. Các l p cao h c thu c khoa CNTT- ĐHKHTN. TPHCM.

ư ệ ọ

ữ ộ

ệ ơ ở

ế

[3] GS.TSKH Hoàng Ki m, TS. Đ Văn Nh n, Th.sĩ Đ Phúc. Giáo trình Các h c s tri ơ th c. Đ i H c Qu c Gia TPHCM – 2002.

ế

[4] GS.TSKH Hoàng Ki m, Th.sĩ Đinh Nguy n Anh Dũng. Giáo trình Trí tu nhân t o. Đ i H c Qu c Gia TPHCM – 2002.

[5] John F.Sowa. Knowledge representation: Logical, Philosophical, and Computational Foundations. Copyright @ 2000 by Brooks/Cole. A division of Thomson Learning.

[6] Adrian A.Hopgood. Knowledge-based systems for Engineers and Scientists. The Open University – CRC Press. Boca-Raton Ann-Arbor London Tokyo 1998.

[7] Sharon Wood. Planning and decision making in dynamic domains.Ellis Horwood Series in Artificial Intelligence - 1998.

[8] Krzysztof J. Cios, Witold Pedrycz, Roman W. Swiniarski. Data Mining Methods for Knowledge Discovery. Kluwer Academic Publishers, 1998

[9] Citeseer - Scientific Literature Digital Library. Artificial Intelligence- http://citeseer.nj.nec.com/ArtificialIntelligence/ - 2003

Tài li u tham kh o ệ ả

ộ ố

ượ

M t s nghiên c u đang đ c quan tâm v AI http://citeseer.nj.nec.com/ArtificialIntelligence/

- Expert Systems : http://citeseer.nj.nec.com/ArtificialIntelligence/ExpertSystems/ - Knowledge Representation: http://citeseer.nj.nec.com/ArtificialIntelligence/KnowledgeRepresentation/ - Natural Language Processing: http://citeseer.nj.nec.com/ArtificialIntelligence/NaturalLanguageProcessing/ - Optimization: http://citeseer.nj.nec.com/ArtificialIntelligence/Optimization/ - Planning: http://citeseer.nj.nec.com/ArtificialIntelligence/Planning/ - Robotics: http://citeseer.nj.nec.com/ArtificialIntelligence/Robotics/

Th vi n s Citeseer ư ệ ố