Đ 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ườimáy
In: Keyboard, Mouse, sensors, touchpad, touchable screen, speechrecognition, …
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 ư ệ ố