🔙 Quay lại trang tải sách pdf ebook Giáo trình khai phá dữ liệu web Ebooks Nhóm Zalo HÀ QUANG THỤY (Chủ biên) PHAN XUÂN HIÉU - ĐOÀN SƠN - NGUYÊN TRÍ THÀNH NGUYÊN THU TRANG - NGUYỄN CẢM TÚ Giáo trình KHAI PHÁ DỮ LIỆU WEB ĐẠI HỌC TRÁI ÍvC u YỄK TRUNG TẮM HỌC LIỆU NHÀ x u At Bả n g iá o d ụ c v iệ t n a m Công ty cổ phần sách Đại học - Dạy nghề - Nhà xuất bản Giáo dục Việt Nam giữ quyền công bố tác phẩm. MỤC LỤC Trang LỜI GIỚI TH IỆU ....................................................................................................................3 Chương 1 MỘT SÔ NỘI DUNG c ơ BẢN VÉ KHAI PHÁ DỮ LIỆU ............................. 9 1.1. Khai phá dữ liệu và phát hiện tri thức trong cơ sờ dữ liệ u ...............9 1.2. Khai phá dử liệu và xử lý cơ sờ dữ liệu truyền th ố n g .................... 20 1.3. Một sô lĩnh vực ứng dụng khai phá dữ liệu điển hình......................22 1.4. Kiểu dữ liệu trong khai phá dữ liệu.....................................................24 1.5. Các bài toán khai phá dữ liệu điển h in h ............................................26 1.6. Tính liên ngành của khai phá dử liệu..................................................30 1.7. Khuynh hướng phát triển của khai phá dử liệ u ...............................33 Câu hỏi và bài tậ p .......................................................................................... 38 Chương 2 TỔNG QUAN VÊ KHAI PHÁ W E B .............................................................. 39 2.1 Giới thiệu về khai phá Text...................................................................39 2.2. Giới thiệu về khai phá W eb...................................................................48 2 3 Khai phá sự dụng W e b ......................................................................... 56 2.4 Khai phá cấu trúc W eb.......................................................................... 66 Câu hỏi và bài tâ p ..........................................................................................68 Chương 3. MOT s ổ KIÊN THỨC TOÁN HỌC CHO KHAI PHÁ DỪ LIỆU W E B.... 69 3.1. Mô hình đồ thị ..........................................................................................70 3.2. Học máy xác suất B ayes......................................................................79 3.3. Thuật toán Viterbi................................................................................... 88 Câu hỏi và bài tậ p .......................................................................................... 93 Chương 4 MỘT SỒ VÁN ĐẺ VẾ x ử LÝ NGỔN NGỮ TIẾNG VIỆT CHO KHAI PHÁ VÁN B Ả N .................................................................................... 94 4 1 Giới thiệu..................................................................................................94 4 2. Kho dữ liệu...............................................................................................96 4 3. Quan hệ ngữ nghĩa trong văn bản...................................................... 96 4 4 Xử lý ngôn ngữ tiếng V iệ t...................................................................104 4 5 Giới thiẹu mọt số nghiên cứu xừ lý tiéng Việt.................................119 Câu hỏi và bài tậ p ........................................................................................120 Chương 5 CÁC PHƯƠNG PHÁP BIẾU DIỄN VĂN BẢN .........................................121 5.1. Phân tích văn bản.................................................................................121 5.2. Các mô hình biểu diễn văn bản.........................................................125 5.3. Các phương pháp lựa chọn các từ trong biẻu diễn văn bản .... 129 5.4 Thu gọn đặc trưng biểu diên................................................. 132 5.5 Phương pháp biểu diễn trang W e b ..................................... 139 Câu hỏi và bài tậ p .........................................................................................142 Chương 6. HỆ THÔNG TÌM K IÊ M ................................................................................. 143 6.1. Tim kiếm trên W eb................................................................................143 6 2 Máy tìm kiếm ................................................. ...................................... 146 6 3. Cầu trúc và hoạt động của một máy tim kiếm ...................151 6 4 Crawling trang W e b ........................................................................ 153 6.5. Phân tích và đánh chỉ sô......................................................................167 6.6. Tính hạng trang W e b .................... 173 6.7. Máy tim kiém thực th ề ......... .............. '8 3 Câu hỏi vã bài tậ p ..................... ..........................185 Chương 7. PHÁN CỤM VĂN B Ả N .............................................................................. 186 7.1. Giới thiệu...................... ....................186 7.2. Thuật toán phân cụm k-means .....................191 7.3. Thuật toán phân cụm phân cấp từ dưới lê n ...................................... 197 7.4. Thuật toán phân hoạch từ trên xu ốn g ......... 201 7 5 Gán nhãn cho các cụm ........ ................. 202 7 6 Đánh giá thuật toán phân cụm "'. ...................... 204 7.7. Mô hlnh phân cụm kết quả tim kiém và gán nhãn cụm tiếng V iệ t......................................................................................... 211 Câu hòi và bàĩ tậ p ..................... .............................. 219 Chương 8. PHÂN LỚP VĂN BẢN.................................................................................. 220 8.1. Giới thiệu................................ ................................ 220 8.2. Một số thuật toán phân lứp có giám s á t............................................223 8.3. Học bán giám sát và một số thuật toán phân lớp bán giám sát .232 Càu hòi và bài tậ p ...........................................................................................241 Chương 9. TRÍCH CHỌN THÔNG TIN TRỂN W E B ................................................. 242 9.1. Giới thiệu...................................................................................................242 9.2. Các phương pháp trích chọn thông tin từ vãn bản Web phi cảu trú c .............................................................................................251 9.3. Các phương pháp trích chọn thõng tin chủ đè trên Web 267 Câu hỏi vá bài tậ p .......................................................................................... 274 Chương 10. W EB NGỮ N G H ĨA ........................................................................................275 10.1. Giới thiệu W eb ngữ nghĩa..................................................................275 10.2. Kiến trúc của W eb ngữ nghĩa...........................................................277 10.3. Các ngôn ngữ nền tảng cho W eb ngữ n ghĩa...............................280 10.4. Tiệm cận tới W eb ngữ nghĩa............................................................292 Câu hỏi và bài tậ p .......................................................................................... 299 TÀI LIỆU THAM KHẢO..........................................................................................................300 4 ........113 ..... tti ...- - l« • > J8 LỜI GIỚI THIỆU rỉ M\ Trong cuốn sách nổi tiếng "Data Mining - Concepts and Techniques® hai tác già Jiawei Han và Micheline Kamber nhận định rằng, tình tran; • r V « y ir « ít ..... 2111 "giàu về dữ liệu mà nghèo về thông tin" là một động lực phát triền lĩnh vựkhai phá dữ liệu và phát hiện tri thức trong cơ sờ dữ liệu (CSDL). Hoạt độn:nghiên cứu và triển khai xây dựng các hệ thống tự động nhận ra các mẫu cgiá trị, mới. hữu ích tiềm năng và hiếu được trong khối dữ liệu đồ sộ, nhằnbô sung tài nguyên tri thức cho con người là hết sức cần thiết và có ý nghĩ ' V . J J -JỈ tro n g q u á trìn h h ìn h th à n h v à p h á t triế n k in h tế tri th ứ c. " ■ r.a-iaiiát .25 Ngày nay, World Wide Web đã trở thành một kho tài nguyên dữ liệ* khống lồ về mọi lĩnh vực; kho tài nguyên dữ liệu này đang không ngùn; • = 24 tăng trường với tốc độ cao. K.ho tài nguyên dữ liệu Web tiềm ân nhiều mai .!( thông tin quý giá đối với hoạt động của cộng đồng nói chung và tirniỉ cá th nói riêng. Các hệ thống khai phá dữ liệu Web đã trờ thành các công cụ là “ cho tài nguyên Web "kho trời chung vô tận của riêng mình" (Cao Bá Quát í, thực sự phát huy hiệu quà tới cộng đồng và tới mỗi cá thê trong cộng đông Phù họp với sự phát triển cùa Web, hoạt động nghiên cứu và triền khai khai phá dữ liệu Web không ngừng được tăng trường, Hiệp hội các nh Ti ỊỊ khoa học về Phát hiện tri thức và Khai phá dữ liệu (The Association fo . J « v r* ■ - r:r: ĩ ' r ĩ - Computing Machinery's Special Interest Group on Knowledge Discoverand Data Mining, viết tăt là SIGKDD) đã tập hợp được nhiêu nhà khoa họctrong đó có nhiều nhà khoa học máy tính nôi tiêng thê giới. Từ năm 1995 tcnay, hoạt động điển hinh nhất của SIGKDD là tố chức Hội nghị Khoa họquốc tế thường niên ACM SIGKDD Conference on Knowledge Discover and Data Mining. K_hai phá dữ liệu Web đã trớ thành một trong những n dung nhận được nhiều quan tâm nhât tại ACM SIGKDD Conference o Knowledge Discovery and Data Mining và các hội nghị khoa học quốc lớn khác. Từ năm 2006, "Khai phủ dữ liệu Web" dã là một môn học tronChương trình đào tạo ngành Công nghệ thône tin (CNTT) và ngành thống thông tin (HTTT) tại Khoa Công nghệ Thông tin, Trường Đại hCông nghệ (ĐHCN), Đại học Quốc gia Hà Nội (ĐHQGHN). Giáo trìn Khai phá dữ liệu Web này được tập hợp và hoàn thiện từ nội dune các bgiáng trong thời gian vừa qua, nhăm cung cãp một tài liệu hoàn chinh phvụ hoạt độna giáng dạy và học tập môn học này tại Khoa CNTT. Trườn ĐHCN cả ờ bậc đại học và sau đại học. Các nội dung trong giáo trinh không chỉ đáp ứng yêu cầu đảo tạọ về lĩnh vực khoa học và công nghệ liên quan, mà còn cung câp một sô kiên thức và kỹ năng mờ rộng và chuvẻn sâu phục vụ nhu câu nghiên cứu và phát triển lĩnh vực khai phá dữ liệu Web không chi tại Trường ĐHCN mà còn ở các cơ sở đào tạo và nghiên cứu khác trong nước. Giáo trình gồm 10 chương, nội dung sơ bộ như sau: Chương 1 - Một số nội dung cơ bàn vể khai phá dữ liệu cun° cấp các kiên thức cơ bản nhât vê lĩnh vực khai phá dữ liệu và phát hiện tri thức trong các CSDL, nhăm giúp độc già nắm bắt được bàn chất cùa các khái niệm cơ bản trong khai phá dữ liệu, phân biệt các khái niệm này với một sô khái niệm liên quan và một số bài toán cơ bàn nhất và xu hướng phát triển của khai phá dữ liệu, phát hiện tri thức trong các CSDL. Chương 2 — Tổng quan về khai phá Web cung cấp các kiến thức cơ bản nhất về khai phá Text và khai phá Web, nhằm giúp độc giá nắm bắt được các nội dung cơ bàn của khai phá Text và khai phá Web. Chương này cũng trình bày cơ bàn về khai phá cấu trúc Web và khai phá sử dụng Web. Chương 3 - Một số kiến thức toán học cho khai phá dữ liệu Web nhăm mục tiêu cung cấp một số kiến thức nền tảng về toán học cho khai phá dữ liệu Web. Lý thuyết đồ thị và lý thuyết xác suất thâm nhập sâu rộng vào khai phá dữ liệu Web theo các góc độ mô hình, giải pháp và kỹ thuật có nguồn gốc từ bản chất tụ nhiên và xã hội cùa Web. Chương 4. Một số vấn đề về xử lý ngôn ngữ tiếng Việt cho khai phá văn ban cung cấp một số kiến thức nền tảng vê xử lý ngôn ngữ tự nhiên nói chung và xừ lý tiếng Việt nói riêng, cho phép nâng cao hiệu quà cùa các giài pháp khai phá Web tiếng Việt. Chương 5 - Các phương pháp biếu diễn văn bản trình bày bài toán các khuôn dạng biêu diễn dừ liệu cho các thuật toán khai phá dữ liệu. Chm/ng 6 - Hệ thong tìm kiếm, Chương 7 - Phân cụm văn bàn, Chương 8— Phán lớp Web, Chương 9 - Trích chọn thông tin trên IVeb trình bày về bốn bài toán chủ yếu của khai phá dữ liệu Web. Các khái niệm liên quan, các mô hinh biêu diễn, các thuật toán, các kv thuật và các phương pháp đánh giá hiệu quá được giới thiệu và phân tích. Chương 10 - Web ngữ nghĩa trình bày về Web ngữ nghĩa, thế hệ mới của Web gôm khái niệm, kiên trúc, các ngôn ngữ và quá trình tiệm cận tới Web ngữ nghĩa. Trong quá trinh bicn soạn giáo trinh này. chúng tôi được khai thác nguôn tài nguyên phong phú. bao gồm nhiều bài báo khoa học. các tiện ích và san phẩm phần mềm thuộc lĩnh vực khai phá Web. Đây là một thuận lợi 6 lớn về nguồn chất liệu biên soạn giáo trình. Nhóm tác giả xin bày tỏ lời cản ơn chân thành tới TS. Nguyễn Lê Minh, Nghiên cứu sinh Nguyễn Việ Cường hiện đang công tác tại Viện Khoa học và Công nghệ tiên tiên Nhậ Bản và Nghiên cứu sinh Đặng Thanh Hài hiện đang công tác tại Đại họ< Antwerp - Bị về việc cộng tác triển khai các hoạt động nghiên cứu liêr quan. Nhóm tác giả đánh giá cao và chân thành cám ơn tập thể cán bộ, sin? viên thuộc Phòng Thí nghiệm Công nghệ tri thức, Trường ĐHCN đã cộnị tác nghiên cứu, triển khai các đề tải KC.01.02/06-10, NCCB 203904 QC.07.13, QC.07.06. Giáo trình này là một sản phẩm của Phòng Th nghiệm Công nghệ tri thức, Bộ môn HTTT được hoàn thành nhân dịp 1( năm truyền thống của Trường ĐHCN (tháng 10/2009). Trong môi trường cùa một trường đại học định hướng nghiên cứu, các tác giả đã và đang nhậr đirợc sự tham gia đóng góp tích cực từ đội ngũ người học trong việc đàrr bảo tính cập nhật về nội dung và tính hiệu quà về cấu trúc của giáo trình Một số nghiên cứu của nhóm tác giả được trình bày trong giáo trình này \ì kết quả cộng tác nghiên cứu của chúng tôi với c ố Giáo sư Susurm Horiguchi tại Viện Khoa học & Công nghệ tiên tiến Nhật Bản và Đại học Tohoku. Nhóm tác giả cũng gặp một số khó khăn khi biên soạn giáo trình. Khc khăn thứ nhất là vấn đề lựa chọn thuật ngữ tiếng Việt. Đối với lĩnh vực kha phá Web, việc lựa chọn thuật ngữ tiếng Việt là rất khó khăn, vì đây là lĩnl vực nghiên cứu còn rất mới không chỉ ở Việt Nam mà còn trên thế giới. V vậy, ngay một số thuật ngữ tiếng Anh cũng có một vài phương án trình bà) và hiểu ngữ nghĩa. Khó khăn thứ hai là về tính hoàn thiện nội dung tronị giáo trình đối với một lĩnh vực nghiên cứu mới với nội dung rất phong phú Dù nhóm tác già đã cố gắng thu thập, nghiên cứu và tổng hợp, song giác trình khó tránh khòi khiếm khuyết. Chúng tôi rất mong nhận được các 3 kiến đóng góp từ các nhà khoa học, các giảng viên và người học để giát trình ngày càng thêm hoàn thiện. Mọi ý kiến đóng góp xin gửi về: Công ty CP Sách Đại học - Dạy nghề NXB Giáo dục Việt Nam, 25 Hàn Thuyên - Hà Nội. Hà Nội, tháng 9 năm 2009 CÁC TÁC GIẢ Chương 1 MỘT SỐ NỘI DUNG c ơ BẢN VÈ KHAI PHÁ Dữ LIỆU 1.1. Khai phá dữ liệu và phát hiện tri thức trong CO’ sở d ữ liệ u Theo J. Han và M. Kamber [HK.0106], quá trình tiến hoá của lĩnh vực công nghệ cơ sờ dữ liệu (CSDL) được mô tá như Hình 1.1, trong đó công nghệ khai phá dữ liệu (Data Mining) được coi là giai đoạn tiến hoá mới cúa công nghệ CSDL. Quá trình tiến hoá này được bắt dầu từ cuối những năm 1980 và không ngừng được phát triến về bề rộng và chiều sâu. Trước tiên, xét sơ bộ về mục đích nghiên cứu của lĩnh vực khai phá dữ liệu. Theo Fayyad và cộng sự [FPS96], việc nghiên cứu, phát triển lĩnh vực khai phá dữ liệu và phát hiện tri thức trong CSDL (Knowledge Discovery in Databases: KDD) nhằm giai quyết tình trạng "ngập trèm ihông tin mà thiếu thốn trì thức", số so liệu thống kê dưới dây được đưa ra vào năm 2006 [Pia06J dã minh chửng cho tình trạng "ngập tràn thông tin" là hiện nay tồn tại nhiều kho chứa dữ liệu đã trờ nên khống lồ mà hằng ngày dung lượng của chúng còn được tăng trưởng với tốc độ cao. v ề dữ liệu Web, diển hình là Alexa, sau 7 năm đã có 500TB (terabyte), Google đã lưu trữ hơn 4 tý trang Web với dung lượng nhiều trăm terabytes, IBM WebFoimtain với hơn 160TB, Internet Archive(l) xấp xi 300TB,... v ề CSDL, điến hình là Max Planck Institute fo r Meteorology có tới hơn 220TB, Yahoo! có hơn 100TB còn AT&T có gần 100TB(2). Theo ước lượng cùa u c Berkeley 2003 thi có tới 5 exabytes (5 triệu terabytes) dữ liệu mới được khới tạo trong năm 2002. Mục đích cúa việc thu thập và lưu trữ các kho chứa dữ liệu khống lồ được liệt kê ớ trên không ngoài mục đích khai phá dữ liệu, nhàm phát hiện các tri thức mới giúp ích cho hoạt động của con người trong tập họp dữ liệu. Chẳng hạn, từ một giải pháp phân lóp trong khai phá dữ liệu Web (Web Mining), có thố phát triển thành một thành phần của máy tìm kiếm (Search Encine) 111 http://www.archive.org. 121 http://www.wintercorp.com/VLDB/2005 TopTen Survey/TopTen Winners 2005.asp. s để khi một trang Web mới được tải về, máy tìm kiếm sẽ tự động phân nó vào một lớp trang Web đã đuợc xác định; viêc phân lớp đó sẽ tạo ra thuận lợi cho việc tìm kiếm về sau của nguời dùng. Trong tình trạng kích thước Web đã và đang có độ tăng trưởng cao, việc phân lớp tự động như vậy thực sự rất có ý nghĩa. Tập hợp dữ liệu và khởi tạo CSDL (tới cuôi nhGng nãm 1960) - Xừ lý tile thô sơ Hệ quản trị CSDL (nhũng năm 1970 vả những năm dầu 1980) - Hệ thống CSDL phân cấp vồ mạng -ỳ Hệ thống CSDL quan hệ - Cổng cụ mô hình dữ liệu: Mô hình quan hệ thục thê ... - Kỹ thuật đánh chĩ sô vả tô chức dữ liệu: cèy 0+, băm ... - Ngôn ngữ hòi SQL ... - Giao diện người dùng, nhập liệu và két xuèt - Xử lý truy van, tối ưu truy vằn - Quãn lý giao dịch: khôi phục, điêu khiên đông thời ... - Xử lý giao dịch trực tuyên (OLTP) : z : Hệ CSDL mở rộng (những năm giữa 1980 đến nay) - Mô hình dữ liệu mở rộng: quan hệ mở rộng, hướng đôi tượng, quan hệ - đôi tượng, suy luận - Định hướng úng dụng: không gian, thời gian, đa phương tiện, tích cực, khoa học, cơ sở tri thức Kho dữ liệu và k-hai phá dữ liệu (nhũng năm cuối 1980 đên nay) - Kho dữ liệu và công nghệ OLAP - Khai phá dữ liệu & phát hiện tri thức Hệ CSDL dựa trên Web (những năm 1990 đền nay) - Hệ CSDL dựa trên XML - Khai phá Web Thế hệ mới hệ thông tin tích hợp (200Q -) H in h 1.1. Tiến hoá công nghệ C S D L Lĩnh vực khai phá dữ liệu và phát hiện tri thức trong CSDL đã tập hợp các phương pháp, thuật toán và kỹ thuật từ nhiêu chuyên ngành nghiên cứu 10 khác nhau như thu nhận mẫu, CSDL, thống kê, trí tuệ nhân tạo, thu nhận tri thức trong hệ chuyên gia,... cùng hướng tới một mục tiêu thống nhất, trích lọc dược các "tri thức" từ dữ liệu trong các CSDL khổng lồ. Tính phong phú và đa dạng cùa lĩnh vực khai phá dữ liệu dẫn đến một thực trạng là, tồn tại các quan niệm khác nhau về chuyên ngành khoa học - công nghệ gần gũi nhất với lĩnh vực đó. Giáo trình này tán thành quan niệm của J. Han và M. Kamber, coi lĩnh vực khai phá dữ liệu là giai đoạn phát triển mới cùa công nghệ CSDL và có liên quan mật thiết với nhiều liên ngành. Như vậy, có thể gắn lĩnh vực này với chuyên ngành hệ thống thông tin. Ví dụ 1.1. (Frawley, Piatetski-Shapiro và Matheus [FPS96]) Hình 1.2 trình bày một N ‘ tập dữ liệu giả định về vay nợ ngân hàng, gồm 23 trường hợp được biểu diễn trong không gian hai chiều. Mỗi điểm trẽn đồ thị biều diễn một trường hợp vay nợ ngân hàng trong quá khứ. Trục hoành biếu diễn thu nhập, trục lung biêu diễn tổng nợ cá nhân của người đi vay (tiền thế chấp, tiền chi trả ô tô,...)- Dữ liệu được phân th àn h hai lớp: lớ p X gồm Thu nhập Hình 1.2. Tập dữ liệu có hai lớp X và o những người thiếu khá năng trà nợ ngân hàng, lóp o gồm những người có tinh trạng tốt. Khái niệm 1.1 [FPS96] Phát hiện tri thức trong cơ sớ dữ liệu (đôi khi còn được gọi là khai phá dữ liệu) là một quá trình không tầm thường nhận ra những mẫu có giá trị, mới, hữu ích tiềm năng và hiêu được trong dữ liệu. Là lĩnh vực nghiên cứu và triển khai được phát triển rất nhanh chóng, có phạm vi rất rộng lớn, lại được rất nhiều nhóm nghiên cứu tại nhiềi trường đại học, viện nghiên cứu, công ty ờ nhiều quốc gia trên thế giới quar tâm, cho nên tồn tại rất nhiều cách tiếp cận khác nhau đối với lĩnh vực phái hiện tri thức trong CSDL. Chính vi lý do đó, trong nhiêu tài liệu, như đã nó: ớ trên, các nhà khoa học đã dùng nhiều thuật ngữ khác nhau, mà các thuậi ngữ này dược coi là mang cùng nghĩa với KDD như chiết lọc tri thức (knowledge extraction), phát hiện thông tin (information discovery), thi hoạch thông tin (information harvesting), khai thác dữ liệu (data archaeology) ll xử lý mẫu dữ liệu (data pattem Processing),... Hơn nữa, trong nhiều trương hợp, hai khái niệm "Phái hiện tri thức trong cơ sờ dữ liệu" và "khai phá dữ liệu" còn được dùng thay thế nhau [FPS96]. Hai khái niệm khai phá dữ liệu và phát hiện tri thức trong các CSDL thường cặp đòi với nhau. J. Han và M. Kamber quan niệm rằng, cụm từ tiếng Anh "Data Mining" chưa diễn tả đầy đủ và toàn diện ý nghĩa của lĩnh vực nghiên cứu - triên khai mà nó mang tên. Một cách tương ứng trong tiếng Việt, cụm từ "khai phá dữ liệu" cũng được nhiều nhà khoa học Việt Nam băn khoăn vì cho răng, cụm từ này chưa bao hàm được hết nội dung ngữ nghĩa cần diễn ta. Tuy nhiên, tương ứng với cụm từ tiếng Anh "Data Mining" (mang nội dung được J. Han và M. Kamber xác định), trong giáo trình này chúng tôi chọn thuật ngữ tiếng Việt là "khai phá dữ liệu" vì thuật ngữ tiếng Việt đã trơ thành phồ biến trong các tài liệu tiếng Việt liên quan hiện nay. Nợ Không cho vay / o ° Cho vay Thu nhập H ình 1.3. Ngưỡng đơn T theo thu nhập đẻ phân lớp cho vay (Lưu ý, đường nghiêng rời nét cho quyẽt định tốt hơn) Một số thuật ngữ có trong khái niệm 1.1 ờ trên cần được giai thích là "dữ liệu, "mẫu", "có giá trị", "mới", "hữu ích", "hiểu được"..-- Dưới đây trinh bày một số giái thích sơ bộ về các khái niệm, nham làm tường minh thêm ngữ nghĩa của khái niệm KDD trong khái niệm 1.1. • Dữ liệu (chính xác hơn là tập dữ liệu) được hiểu như là một tập F 2Ôm lũru hạn các trường hợp (sự kiện). Theo nội dung cùa phát hiện tri thức trong các CSDL. dữ liệu phài bao gồm nhiều trường hợp. Trong ví dụ 1.1. F là tập hợp gôm 23 trường họp (bán ghi) với 3 trường thông tin (thuộc tinh) tương ứng chứa các giá trị vê sổ nợ, thu nhập và lình trạng vay nợ. Trona bài toán khai phá văn ban. tập dữ liệu F chính là tập họp các vãn bàn có thê có trong miên ứng dụng. I rong bài toán khai phá luật kết họp aiao dịch, tập I' bao gôm tât ca các giao dịch có thê có dược tronc miền áp dụna cua bài toán. ] 2 • Mau. Trong quá trình KDD, người ta sứ dụng một ngôn ngữ L đê biêu dicn các tập con các sụ kiện (dữ liệu) thuộc vào tập sự kiện F, theo đó môi biếu thức E trong ngôn ngữ L sẽ biểu diễn một tập con Fe tương ứng các sự kiện trong F. E được gọi là mẫu nếu nó đơn gian hơn (theo một ngữ cảnh nào dó) so với việc liệt kê các sự kiện thuộc Fe- Chang hạn, biêu thức "THUNHẶP < $t" (mô hình chứa một biến THƯNHẬP) trong mệnh đề "Nếu THUNHẬP < $t thì người vay nợ rơi vào tình trạng không thể chi trả" sẽ là một mẫu khi cho biến t nhận một giá trị thích hợp. Như trình bày bàng ' đồ thị tại Hình 1.3, khi biến t nhận một giá trị cụ thể T, mẫu này (biểu diễn mọi trường họp có THƯNHẬP < T) hiển nhiên là gọn hơn so với việc liệt kê 14 trường họp cụ thể. Tương tự, nếu F là tập các trang Web trong kho lưu trữ cùa một máy tìm kiếm (chàng hạn Google), thĩ mẫu "tài liệu có chứa từ cụm từ "Search Engine" sẽ biểu diễn một tập bao gồm một số lượng rất lớn các tài liệu Web có chứa cụm từ "Search Engine" đó. • Quá trình KDD thường bao gồm nhiều bước như chuấn bị dữ liệu, tìm kiếm mau, ước lượng tri thức, tinh chế sự tương tác nội tại sau khi chuyến dạng dữ liệu. Quá trình được thừa nhận là không tầm thường theo nghĩa là quá trình đó không chi nhiều bước, mà còn được thực hiện lặp, quan trọng hơn là quá trình đó bao hàm một mức độ tìm kiếm tự động. Chẳng hạn, trong Vi dụ 1.1, khi tính toán ý nghĩa về thu nhập của một người, nếu chí thông qua các tác động đơn giản mà chúng ta thu nhận được một kết luận nào đó có thể là hữu ích thì đừng vội cho rằng, dó đã là một khám phá (hoặc đừng cho rằng một tri thức đã được phát hiện). • Có giá trị: Mầu dược phát hiện cần phải có giá trị đối với các dữ liệu mới (xuất hiện trong tương lai) theo một mức độ chân thực nào đấy. Tính chất "có giá trị" được hiêu theo nghĩa liên quan tới một độ đo tính có giá trị (chân thực) là một hàm c ánh xạ một biếu thức thuộc ngôn ngữ biểu diễn mẫu L tới một không gian đo được (bộ phận hoặc toàn bộ) M o Một biểu thức E trong L biêu diễn một tập con F|f c F có thê được gán một độ đo chân thực c = C(E, F). Chẳng hạn, nếu đường biên xác định mẫu "THUNHẶP < $t" như chỉ dẫn trong Hình 1.3 được dịch sang phái (biến THUNHẬP nhận giá trị lớn hơn) thì độ chân thực của mẫu mới sẽ bị giảm xuống, bởi vì nó đã bao gói thêm các tình huống vay tốt lại bị đưa vào vùng không cho vay nợ. Tương tự. mẫu "Nếu a*THUNHẶP + b*NỢ < 0 (thuộc mô hình tuyến tính hai biến THƯNHẬP và NỢ trong a*THỰNHẬP + P*NỢ) thì người vay nợ rơi vào tình trạng không thê chi trá" biêu diễn một nửa mặt phẳng phía trên cúa đường rời nét trong Hình 1.3 sẽ cho độ chân thực cao hơn (hay được coi là "có giá trị hơn") so với mọi mẫu thuộc mô hình một biến "THUNHẶP < $t". 13 • Tính mới'. M ầu phải là mới trong một miền xem xét nào đó. ít nhất là hệ thông đang được xem xét. Tính mới có thế đo được khi quan tâm tới sự thay đôi trong dữ liệu (băng việc so sánh giá trị hiện tại với giá trị quá khứ hoặc giá trị kỳ vọng) hoặc tri thức (tri thức mới quan hệ như thế nào với các tri thức đã có). Tông quát, điều này có thể được đo bằng một hàm N(E. F), hoặc là độ đo vê tính mới, hoặc là độ đo kỳ vọng. • Hữu ích tiềm năng: Mầu cần có khả năng chì dẫn tới các tác động hữu dụng và được đo bởi một hàm tiện ích. Chàng hạn, hàm u ánh xạ các biêu thức trong L tới m ột không gian đo có thứ tự (bộ phận hoặc toàn bộ) Mu, theo đó u = Ư (E, F). Ví dụ, trong tập dữ liệu vay nợ, hàm này có thê là sự tăng hy vọng theo sự tăng lãi của nhà băng (tính theo đơn vị tiền tệ) kết hợp với quy tăc quyêt định được trình bày trong Hình 1.3. • Có thế hiếu được: M ột mục tiêu của KDD là tạo ra các mẫu mà con người hiếu chủng d ễ dàng hơn các dữ .liệu nền (dữ liệu sẵn có trong hệ thống). Có thể hiểu được là tiêu chí khó đo được một cách chính xác, cho nên thường tính chất "có thể hiểu được" được thay bằng một độ đo về sự dễ hiêu. Tồn tại m ột số độ đo về sự dễ hiểu, các độ đo như vậy được sắp xêp từ cú pháp (tức là cỡ của mẫu theo bit) tới ngữ nghĩa (tức là dễ dàng để con người nhận thức được theo m ột tác động nào đó). Bởi lý do đó, già định răng tính hiểu được là đo được bằng một hàm s ánh xạ biểu thức E trong L tới một không gian đo được có thứ tự (bộ phận hoặc toàn bộ) Ms; theo đó, s = S(E, F). • Độ hấp dẫn: M ột tiêu chí quan trọng được gọi là độ hấp dẫn, thường được coi như m ột độ đo tổng thể 'về mẫu là sự kết hợp của các-tiêu chí giá trị, mới, hữu ích và d ễ hiếu. M ột số hệ thống KDD thường sử dụng một hàm hấp dẫn dưới dạng hiển là i = I(E, F, c , N, u , S) thực hiện ánh xạ một biểu thức trong L vào m ột không gian đo được Mj. M ột số hệ thống KDD khác lại có thể xác định giá trị hấp dẫn của mẫu m ột cách trực tiêp thông qua thứ tự của các mẫu được phát hiện. Chọn Tiên xử lý Đôi dạng \ Khai phá dữ liêu iV Dữ liệu chuyến Trình diênV Mẩu Tri thức lưa Dữ liêu \ tIM- -Dữ liệu đích dan* Dữ liêu đã tiên xử lý Hình 1.4. Quá trinh phát hiện tri thức trong CSDL 14 T rong thực tiễn giải quyết các bài toán khai phá dữ liệu, người ta thư ờng chi quan tâm đến độ hấp dẫn, còn các độ đo khác được m ặc định coi là thành phần của độ hấp dẫn. Cụ thể là, khi thi hành m ột loại bài toán phát hiện tri thức cụ thể, m ột số độ đo tương ứng được tính toán nhằm xác định độ hấp dẫn của tri thức ("m ẫu", "luật") đang được xem xẻt. C hảng hạn, trong bài toán khai phá luật kết hợp, hai độ đo được xem xét đó là độ h ỗ trợ (xác định phạm vi ảnh hưởng của luật) và độ tin cậy (xác định tính tin cậy của luật) hợp thành độ hấp dẫn của luật kết họp đã được khai phá. T ương tự, trong bài toán phân lóp, người ta sử dụng hai độ đo cơ bản là độ hồi p hục (kha năng bao gói ví dụ đúng) và độ chính xác (khả năng chính xác khi xác định ví dụ đúng); đồng thời, m ột số độ đo m ang ý nghĩa kết họp từ hai độ đo này cũng được sừ dụng. • Tri thức. M ột m ẫu E e L được gọi là tri thức nếu như đối với m ột người sử dụng nào đó, chỉ ra được m ột ngưỡng i 6 M, m à độ hấp dẫn f ( E , F , c , N , U , S ) > i. Chú ý rằng, khái niệm "tri thức" trên không m ang m ột nghĩa tuyệt đối, m à phụ thuộc vào quan điểm của người sử dụng hệ thống K D D ("m ột lóp người sử dụng nào đó"). N hư m ột nội dung của sự kiện, nó chỉ là m ột định hướng cho người sử dụng và được xác dịnh bằng bất kỳ hàm và ngư ỡng nào được người sử dụng chọn. C hẳng hạn, trong bài toán khai phá luật kết họp, chúng ta chỉ quan tâm tới các "tập p h ô biến" là những tập có độ hỗ trợ vượt qua m ột ngư ỡng m insup nào đó. Hơn nữa, chi các luật kết hợp có độ tin cậy vượt quá ngư ỡng m in c o n f m ới được khai phá đê cung câp tri thức tới người sứ dụng. C ác ngư ỡng m insup và m in c o n f có thể được thay đổi theo lựa chọn của người sử dụng. M ột cách hình thức, thuyết m inh cụ thể của định nghĩa trên về "tri thức" là chọn ngư ỡng nào đó c Ễ M c (về tính "có giá tr ị,r), s e M s (về tính "có thế hiêu đư ợ c") v à u Ễ M u (về tính "hữu ích") và khi đó gọi m ẫu E là tri thức nếu và chi nếu: C (E , F) > c và S(E, F) > s và U(E, F) >u T hông qua việc đặt các ngưỡng thích hợp với m ục đích phát hiện tri thức, người sử dụng có thê nhân m ạnh m ột dự báo chính xác hoặc các m ẫu hữu ích (vư ợt qua m ột độ đo đánh giá nào đó) qua những độ đo liên quan. Rõ ràng là, tồn tại m ột không gian vô hạn cho phép ánh xạ I xác định "tri thức cần phát hiện". Q uyêt định như vậy là tự do đối với người sử dụng và được đặc trư ng đối với từng m iền ứng dụng. K en M cG aư y [G ar05] trình bày m ột nghiên cứu tổng quan về việc sứ dụng các độ đo hấp dẫn được dùng phổ biến trong phát hiện tri thức trong C SD L . C ó thê phàn chúng theo lớp độ đo hướng m ục tiêu, lớp độ đo hướng 15 chu đê và lớp độ đo cho luật kết hợp. Tác già nhận xét ràng, tồn tại rảt nhiêu các độ đo hướng chù đê đê đáp ứng miên rộng lớn các ứne dụng, và vì vậy rất thuận tiện đê chọn ra m ột độ đo phù hợp đối với m ột miên ứng dụng đã cho. N hững điều trình bày trên cho thấy vai trò cùa hệ thống K.DD cũng như vai trò của người sử dụng trong một phiên làm việc của m ình, tạo nên sự cộng tác giữa người sử dụng và hệ thống KDD. Trong sự cộng tác đó. hệ thông KDD tạo thuận tiện cho người sử dụng có cách thức linh hoạt dùng các ngưỡng đê được cung câp "tri thức" từ hệ thống phù hợp với những dự đoán chù quan của mình. Như vậy, có thể thấy rằng, cùng dùng m ột phản mêm KDD. song môi người sừ dụng lại có thể khai thác nó theo cách thức riêng cua mình. Theo B .K ovalerchuk và E.Vityaev [KV01], Friedm an đã tồng hợp một số quan niệm sau đây liên quan về khái niệm "khai phá dữ liệu": - Q uá trình không tầm thường để nhận biết từ dữ liệu ra các m ẫu có giá trị, m ới. hữu dụng và hiểu được (Fayyad); - Q uá trình trích lọc các thông tin chưa biết trước, có thê nhận thức được, có thề tác động được từ CSDL lớn và sừ dụng chúng đê tạo ra quyêt định công tác (Zekulin); - Tập các phương pháp được dùng trong quá trình phát hiện tri thức nhàm tường m inh các quan hệ và các m âu chưa biêt trước chửa trong dừ liệu (Ferruzza); - Quá trình hỗ trợ quyết định khi tìm kiếm những mẫu thông tin chưa biết và hữu ích từ CSDL lớn (Parsaye). Giáo trình này tiếp nhận quan điểm của Fayyad. Piatetsky-Shapiro, S m u h . như đã trinh bàv trong K hái niệm 1.1, chúng ta coi K.DD là m ột quá trinh bao gồm nhiều bước thực hiện, trong đó, khai phá dữ liệu là m ột bước thực hiện chính yếu. Cách hiểu như vậy đã quy định có sự phân biệt giữa hai khái niệm khai p h á dữ liệu và KDD. K h á i n iệm 1.2 (Fraw ley, Piatetski-Shapiro và M atheus [FPS96]) Khai p h á dữ liệu ¡à một bước trong quá trình Phút hiện tri thức trong cơ sơ dữ liệu, thi hành một thuật toán khai p h á dữ liệu đế tìm ra các m âu từ dữ liệu theo khuôn dạng thích hợp. Tương ứng với sơ đồ mô tả chi tiết quá trình KDD (H ình 1.5), các nhóm bước thực hiện sau đây được tiến hành trong quá trình phát hiện tri thức trona CSDL: (1) M ơ rộng hiẽu biết về miền ứng dụng, về các tri thức với độ ưu tiên thích họp và về mục đích của người dùng cuối. Có thề coi nội dung công việc này tương ứng với nội dune khảo sát bài toán trone quá trình xây dự ns m ột hệ thône thông tin nói chung. 16 K hởi tạo tập dữ liệu đích, tạo kho d ữ liệu: chọn tập dừ liệu "và/hoặc" hướng trọng tâm tới tập con các biên hoặc m âu dữ liệu m à trên đó công việc phát hiện tri thức được tiên hành. Tri thức m iền úng dụng có được thông qua việc m ớ rộng hiểu biết về m iên ứng dụng nói trên đóng vai trò là nên táng tri thức đê khởi tạo tập dừ liệu đích, kho dữ liệu. H ình 1.5. Mô tả chi tiết các bước trong quá trinh KDD (2) L àm sạch và tiền x ứ lý d ữ liệu : thực hiện các thao tác cơ sở như giải quyết thiếu vắng giá trị, loại bó nhiễu hoặc yếu tố ngoại lai, kết nối các thông tin cần thiết tới m ô hình hoặc loại bỏ nhiễu, quyết định chiến lược nhàm nắm bắt các trường dữ liệu (các thuộc tính), tính toán dãy thông tin thời gian và sự biến đổi được định trước. C hất lượng của hệ thống khai phá dữ liệu phụ thuộc vào chất lượng cùa dữ liệu đầu vào. M ục tiêu của làm sạch dữ liệu nhằm đảm bảo dữ liệu đầu vào có chất lượng tốt. Thu g ọ n và trình diễn dữ liệu có m ục tiêu tìm được các đặc trưng hữu ích nhăm trinh bày m ôi phụ thuộc dừ liệu theo m ục đích của bài toán. T hu gọn dừ liệu được thi hành về chiều ngang (giảm số lượng đối tượng), chiều dọc (giảm số lượng trường dừ liệu) hoặc cả hai nhàm làm cho kích thước dữ liệu được xử lý, tăng tốc độ hoạt động của hộ thống.’ Sư dụng các phương pháp thu gọn hoặc biến đổi chiiều nhằm rút gọn số lượng các biến cần quan tâm hoặc để tìm ra các mô 17 tả bất biến đối với dữ liệu nhàm trình diễn dữ liệu phù hợp nhất. Do khôi lượng dữ liệu trong bài toán KDD là rất lớn, nên việc thi hành bước này là rất cần thiết. K_hi thu gọn theo chiều ngang cần lưu ý là tập dữ liệu được chọn lựa sau khi thu gọn phái có tính đại diện cho tập toàn bộ d ữ liệu cùa miền ứng dụng. Việc chọn lựa dữ liệu vào xây dụ n g m ô hình khai phá dữ liệu (xây dự ng nhà kho dữ liệu) thông thư ờng cần được tiến hành theo m ột phư ơng pháp đam báo tính "ngâu nhiên" khi chọn lựa dữ liệu trong m iền ứng dụng. T ư ơng tự. khi thu gọn theo chiều dọc cần lưu ý các thuộc tính còn lại phài đảm bào tính đại diện cho đối tượng trong bài toán khai phá dữ liệu đang xem xét. T rong không ít bài toán khai phá dữ liệu, khi thu gọn theo chiều dọc lại nhận đuợc kết quả tốt hơn không chi vê thời gian và không gian, m à còn cà về chất lượng của bài toán khai phá dự liệu khi đạt được độ chính xác cao hơn vì đã loại bò được m ột sô thuộc tín h gây nhiễu. Phương pháp p h ầ n từ chính (P C A ) thường dược sử dụng trong bài toán thu gọn theo chiều dọc. (3) C họn bài toán khai p h á d ữ liệu: quyết định m ục tiêu của quá trình K D D là loại bài toán cụ thê nào, chăng hạn như phân lớp, hôi quy, phân đoạn,... C họn lựa các p h ư ơ n g p h á p khai p h á d ữ liệu: lựa chọn phư ơng pháp dùng để tìm m ẫu trong dữ liệu. N ội dung này bao gôm cà việc quyêt định các m ô hình và tham sô có thê được châp nhận và phương pháp khai phá dữ liệu phù hợp với tiêu chuẩn tổng thể của quá trình K D D . Thi hành thuật toán khai p h á d ữ liệu: tiến hành việc dò tìm các mẫu cần quan tâm dưới dạng trình bày riêng biệt, hoặc m ột tập các trình bày như quy tắc phân lớp, cây, hồi quy, phân đoạn,... T rong bước này, sự hỗ trợ của người dùng vẫn đóng m ột vai trò quan trọng. (4) G iai thích m ẫu đối với các m ẫu được khám phá, có thể quav về m ột cách họp lý tới bất kỳ bước nào từ bước đầu tiên tới bước thi hành thuật toán khai phá dữ liệu để thực hiện lặp. (5) H ợp nhất các tri thức đã được khám phá, kết hợp các tri thức này thành m ột hệ thống trình diễn hoặc được biên soạn dễ d àn e và kết xuất thành những thành phần hấp dẫn. K iểm tra và giải quyết xung đột đối với tri thức được trích chọn. T rong quá trình phát hiện tri thức trong các C SD L như m ô tà ơ trên có tham gia cua các kho dữ liệu (D ata W arehouse), nội dung về kho dữ liệu được giới thiệu ở phần sau. Hình 1.6. Kiến trúc điển hinh của hệ thống khai phá dữ liệu Kiến trúc một hệ thống khai phá dữ liệu: Kiến trúc điển hình của một hệ thống khai phá dữ liệu được trình bày trong hình 1.6 [HK0106], Trong kiến trúc hệ thống này, các nguồn dữ liệu cho các hệ thống khai phá dữ liệu bao gồm hoặc CSDL, hoặc Kho dữ liệu, hoặc World Wide Web, hoặc kho chứa dữ liệu kiểu bất kỳ khác, hoặc tồ họp các kiểu đã liệt kê nói trên. Cơ sở tri thức chứa các tri thức miền ứng dụng hiện có, được sử dụng trong thành phần hệ thống khai phá dữ liệu đế làm tăng tính hiệu quà của thầnh phần này. Một số tham số của thuật toán khai phá dữ liệu tương ứng sẽ được tinh chinh theo tri thức miền sẵn có từ cơ sở tri thức trong hệ thống. Cơ sở tri thức còn được sừ dụng trong việc đánh giá các mẫu đã khai phá đirợc, xem chúng có thực sự hấp dẫn hay không, trong đó có việc đối chứng mẫu mới với các tri thức đã có trong cơ sở tri thức. Neu mẫu khai phá được là thực sự hấp dẫn thì chúng được bổ sung vào cơ sở tri thức đề phục vụ cho hoạt động tiếp theo của hệ thông. Như vậy, nguôn tri thức bô sung vào cơ sở tri thức ở dây không chỉ từ lập luận lôgic theo các hệ toán lôgic để có tri thức mới không chi do con người hiêu biêt vê thê giới khách quan để bồ sung vào mà còn là tri thức được phát hiện một cách tự động từ nguồn dữ liệu. 19 1.2. Khai phá dữ liệu và xử lý CO’ sở dữ liệu truyền thống Như đậ giới thiệu, khai phá dữ liệu là một thế hệ phát triển men trong thời gian gần đây cùa công nghệ CSDL. Điều đó có nghĩa là, có mối quan hệ gân gũi giữa bài toán khai phá dữ liệu và bài toán xừ lý (tác nghiệp) CSDL truyên thông trong mối liên quan tới một đối tượng chung là CSDL. Tuy nhiên, hai bài toán này cũng có sự phân biệt. Dấu hiệu phân biệt đâu tiên giữa khai phá dữ liệu và xử lý CSDL truyền thống là đối tượng tác động của bài toán khai phá dữ liệu phài là các CSDL, các kho dữ liệu có dung lượng rât lớn; trong khi đó bài toán tác nghiệp CSDL truyền thống liên quan tới các CSDL với mọi kích thước. Thêm nữa, những nội dung dưới đây cung cấp thêm các thông tin bồ sung về bài toán khai phá dữ liệu [KV01]. Hệ quản trị CSDL truyền thống được định hướng việc tìm kiếm tới: - Ghi nhận riêng lè, chang hạn như cần tìm kiếm câu trà lòi cho truy vấn "Hãy hiển thị số tiền của Ỏng Nguyễn Vãn A có trong ngày 5 tháng Giêng nãm nay". Việc tìm kiếm các ghi nhận riêng lè thường được chi dân là xừ lý giao dịch trực tuyến (on-line transaction processing - OLTP). - Ghi nhận thống kẽ, chẳng hạn như đề trà lời câu hói "Có bao nhiêu nhà đầu tư nước ngoài mua cồ phiếu X trong tháng trước?". Việc tim kiêm ghi nhận thống kê thường được chi dẫn là hệ thống hỗ trợ quyêt định thông kê (stastical decision suppport system - DSS). - Ghi nhận về dữ liệu đa chiều, chăng hạn như đê đáp ứng yêu câu "Hiển thị mọi cổ phiếu trong CSDL với mệnh giá tăng". Việc tìm kiêm các ghi nhận dữ liệu đa chiêu thường được hiêu là cung câp, xừ lý. phân tích trực tuyến (on-line analytic processing - OLAP) và xừ lý phân tích trực tuyến quan hệ (relational OLAP - ROLAP). Để các loại truy vấn (như những truy vấn nói trên) đặt ra được vân đẽ cần giài quyết một cách đúng đắn, và qua đó tạo ra được các quyết định hữu ích thì cần phái công nhận đã tồn tại một già thiết về tri thức mien phức hợp "đầy đu" (sophisticated domain knowledge) mà các loại truy vấn nói trên được đưa ra dựa trên cơ sờ tri thức miền đó. Trong CSDL quan hệ. tập các phụ thuộc hàm. các luật suy diễn Armstrong là một bộ phận của tri thức miên ứng dụng nói trên. Tuy nhiên, với các CSDL lớn có dung lượna tới hàng trăm Gigabytes (GB) thi rất khó khăn đe công nhận một tri thức miền phức hợp đây đủ. Phương pháp khai phá dữ liệu hỗ trợ việc mờ rộng mục tiêu của CSDL truyền thống bàng cách cho phép tim kiếm các câu trà lời cho các truy \ ấn 20 tuy thô sơ, song lại quan trọng, có tác dụng cài tiến miền tri thức (trong trư ờ n g hợ p này tri thức m iên phức hợp được coi là ch ư a đ â y đ u) như: - C ác cổ p h iếu táng giá có đặc trư n g gì? - T ý giá us$ - D M ark có đặc trưng gì? - H y v ọ n g gì về cổ phiếu X trong tuần tiếp theo? - T ro n g th án g tiếp theo, sẽ có bao nhiêu đo àn viên công đo àn k h ô n g trả được nợ của họ? - N h ữ n g ngườ i m ua sàn phẩm Y có đặc trư n g gì? Hể thống quản tri CSDL Hê thống khai phá dữ liệu Kho dữ liêu (CSDL rất 1 ớn tâp trung, môt khuôn dang dữ liêu chung) D ata M a rt (CSDL chuyên biệt) D ata M a rt (CSDL chuyên biệt) Câu hỏi dưa trên,,ri thức miền pỉmc tap ỹ c a Quá trim tự động CỔ phiếu mà lợi nhuân âm có đăc trung Cảu hỏi khai phà dữ hệu Hãy hiển thị số tiển ỏng Smith trong ngày 5 tháng Giêng Cảu hỏi cụ thè, riềng biệt Có bao nhiêu nhà đẩu tư nước ngoài mua cồ phiếu X ừong tháng trước 9 Câu hỏĩ thông kê Hiển thi moi cổ phiếu trong CSDL tăng mênh giá ịjảu hỏì ROLAP Hình 1.7. Mối quan h ệ giữa h ệ thống CSDL và h ệ thống khai phá dử liệu Trả lời các truy vấn trên dường như là đã khám phá ra được các quy tấc (luật) tiềm ân trong dữ liệu và trên cơ sở các quy tăc đó mà đưa ra được các d ự báo. N h ữ n g q u y tăc đượ c khám phá là không tuyệt đối, k h ô n g m a n g tính "bất d i bắt d ịc h " m à có tín h chất "đa sổ trư ờ n g hợp là đ ú n g " và có the thay đối từ thời điềm này đến thời diêm khác. Chẳng hạn như, luật kết hợp "co đến 80% người nếu đã mua bịa thì cũng mua thêm mực hoặc lạc rang" được phát hiện cho thấy tại thời điếm đang xem xét phần dông người mua bia thi cũng mua thèm mực hoặc lạc rang. Có thê đến thời điềm nào đó khác trong tư ơ n g lai. khi m à thị h iêu cua người uống bia có sự thay đổi. theo đó họ se k h ô n g m ua m ự c hoặc lạc ran g nữ a thì trong C S D L giao d ịch sẽ k h ô n g tiềm ân "luật" nói trẽn nữa. 21 M6i quan he giua he thong quan tri CSDL vcri he thong khai pha du lieu dirge mo ta trong Hinh 1.7 [KV01], Nhu vay, trong khai pha dir lieu thi gia thiet da biet ve mot tri thirc mien phirc tap "day du" khong con let yen to cot loi, va qua trinh phat hien tri thirc co tac dung bo sung them cac tri thirc "mcri" vao mien tri thirc do. 1.3. Mot so ITnh v if c u>ng dung khai pha di> lieu d iin hinh Theo J. Han va M. Kamber [HK0106], ung dung cua KDD duoc chia thanh hai lap chinh. bao gom lop cac img dung phan tich du lieu - ho tro quyet dinh va lop cac llnh vurc img dung khac. Lap cac img dung trong phan tich dir lieu - hi5 tro quyit dinh bao gom cac img dung trong phan tich va quan ly thi trucmg, phan tich va quan ly rui ro, kham pha ngoai lai va cac mau khong hiru ich. Du lieu trong cac img dung nay la kha phong phu, co duoc tir cac giao dich the tin dung, nghien cuu doi song cong dong,... Bang 1.1. Xu the phat trien cua cac ITnh vu-c khai pha dCr lieu Y, trong đó X, Y là hai tập thuộc tính, v ề hình thức, luật kết hợp có dạng giống như phụ thuộc hàm trong CSDL quan hệ, tuy nhiên, nó không được định sẵn từ tri thức miền. Trong khai phá text và khai phá W eb tồn tại nhiều bài toán phát hiện quan hệ kết hợp, điển hình như bài toán phát hiện quan hệ ngữ nehĩa (chăng hạn như quan hệ nhân - quá, quan hệ toàn bộ - bộ phận, quan hệ chung - riêng,...) trong vãn bàn (hoặc trong tập văn bàn), bài toán phát hiện mối quan hệ giữa nội dung trang W eb người sử dụng đang quan tâm tới các trang W eb mà họ có thể sẽ hướng tới,... • Phân lớp Phân lớp (C lassification/C ategorization) thực hiện việc xây dựng (mô ta) các mỏ hinh (hàm ) dự báo, nhăm mô tà hoặc phát hiện các lớp hoặc khái niệm cho các dự báo tiếp theo. M ột số phương pháp điển hình là cây quyết định, luật phân lớp. m ạng neuron. Nội dung cùa phân lớp chính là m ột hàm ánh xạ các dữ liệu vào m ột trong m ột số lớp đã biết. Ví dụ, phân lớp m ột vãn bàn (bao gôm cà trang W eb) vào m ột trong m ột số lớp vãn bàn (trarm Web) đã biêt, phân lớp khuynh hướng trong thị trường tài chính, phát hiện tự động các đối tượng đáng quan tâm trong CSD L ành lớ n ,... Hình 1.8 mô 28 tà sơ bộ về bài toán phân lớp (thường được tương ứng với học có giám sát), theo đó đường ngang liền nét cho biết đã biêt thuộc tính lớp đôi với m ột tập hợp dữ liệu nào đó (tập dữ liệu học). Nội dung chi tiết hơn về bài toán phân lóp sẽ được trình bày chi tiết hơn trong C hương 7 - P hân lớp văn ban. • P hăn cụm Phân cụm (C lustering) thực hiện việc nhóm dữ liệu thành các "cụm " (có thể coi là các lớp m ới) đế có thể phát hiện được các m ẫu phân bố dữ liệu trong m iền úng dụng. Phân cụm là m ột bài toán m ô tả hướng tới việc nhận biết m ột tập hữu hạn các cụm hoặc các lớp đế m ô tả d ữ liệu. Các cụm (lớp) có thể tách rời nhau và toàn phần (tạo nên m ột phân hoạch cho tập dữ liệu), hoặc được trinh bày đẹp hcm nh ư phân lớp có thứ bậc hoặc có thể chồng lên nhau (giao nhau). Ví dụ, bài toán phát hiện các nhóm người tiêu dùng trong C SD L tiếp thị, hoặc nhận biết các loại quang phổ trong tập phép đo không gian hồng ngoại,... T hông thường, m ục tiêu định hướ ng của bài toán phân cụm là cực đại tính tương đồng giữ a các phần tứ trong m ỗi cụm và cực tiểu tính tương đồng giữa các phần tử thuộc các cụm khác nhau. T rong nhiều trư ờ ng hợp, phân cụm còn được gọi là học m ả y không giám sát (unsupervised learning) và phân lớp còn được gọi là học máy có giám sát (supervised learning). M ô hình học m áy (có giám sát và không giám sát) được trình bày trong H ình 1.8 [K V 01]. T rong m ột số ứng dụng, bài toán phân đoạn (segm entation) cần được giải quyết, v ề bản chất, phân đoạn là tổ hợp cùa phân cụm và phân lớp, trong đó phân cụm được tiến hành trước và sau đó là phân lớp. C hương 6 - P hân cụm văn bàn sẽ m ô tả chi tiết hon về bài to án phân cụm . • H ồ i qu y H ồi quy là m ột bài toán điến hình trong phân tích thống kê và d ự báo, trong đó tiến hành v iệc d ự đoán các giá trị của m ột hoặc m ột số biến phụ thuộc vào giá trị của m ột tập hợp các biến độc lập [H D 03], M ô hình hồi quy là khá thông dụn g trong dự báo dài hạn. T rong khai phá dữ liệu, bài toán hồi quy được quy về việc học m ột hàm ánh xạ dữ liệu nhàm xác định giá trị thực cùa m ột biến theo m ột số biến khác. T ình huống ứng dụng hồi quy rất đa dạng, chẳng hạn nh ư dự đoán số lượng sinh vật phát quang trong khu rù n g nhờ đo vi sóng các sensor từ xa, hoặc ước lượng xác suất người bệnh có thế chết theo kêt quà test triệu chứng, hoặc dự báo nhu cầu người tiêu d ùng đối với m ột sàn phâm m ới được coi như m ột hàm của quảng cáo tiêu dùng, hoặc dự báo chuôi thời gian m à các biến đầu vào được coi nh ư bản trễ thời gian của biến d ự b á o ,... 29 • Mô hình phụ thuộc Bài toán xây dựng mô hình phụ thuộc hướng tới việc tim ra một mô hình mô tả sự phụ thuộc có ý nghĩa giữa các biến. Mô hình phụ thuộc gôm hai mức: mức cấu trúc cùa mô hình mô tả (thường dưới dạne đồ thị), trong đó các biến là phụ thuộc bộ phận vào các biến khác; trong khi mức định lượng cùa mô hình mô tà sức mạnh cùa tính phụ thuộc khi sừ dụng việc đo tính theo giá trị số. Vi dụ, lưới phụ thuộc xác suất cằn đám bào tinh độc lập điều kiện nhằm định rõ diện mạo cấu trúc cùa mô hình và xác suât, hoặc tương quan đê mô tả sức mạnh của tính phụ thuộc. Phân tích khuynh hướng và tiến hoá cũng được coi thuộc vào loại khai phá mô hình phụ thuộc. Trong phân tích khuynh hướng và tiến hoá, các phương pháp phân tích xu thế, khai phá mẫu kế tiếp, phân tích dựa trêh tính tương tự ,... thường được áp dụng. • Phát hiện biến đối và độ lệch Tập trung vào việc phát hiện hầu hết sự thay đổi có ý nghĩa dưới dạng độ đo đã biết truớc hoặc giá trị chuẩn, cung cấp những tri thức về sự biến đổi và độ lệch cho người dùng. Bài toán phát hiện biến đổi và độ lệch còn được ứng dụng trong bước tiền xử lý trong quá trình phát hiện tri thức trong CSDL. Chính vì lý do đó, cần tránh suy nghĩ cho ràng, sự biến đôi và độ lệch mang ý nghĩa "không chính quy" mà phải quan niệm sự biến đôi và độ lệch đó (có the là bất thường) là một nội dung bàn chất của dữ liệu. Ngoài ra có thế kê tới bài toán phân tích định hướng mâu và một sô bài toán khai phá dữ liệu kiêu thông kê khác. 1.6. Tính liên ngành của khai phá dữ liệu KDD nhận được sự quan tâm đặc biệt cùa các nhà nghiên cứu trong các lĩnh vực học máy, thu nhận mẫu, CSDL, thống kê, trí tuệ nhân tạo, thu nhận tri thức đối với hệ chuyên gia được trình bày trong Hình 1.9 [HK0106]. Hệ thông KDD lôi cuốn các phương pháp, thuật toán và kỹ thuật từ các lĩnh vực rời rạc nhau này. Mục tiêu thống nhất là trích lọc tri thức từ dữ liệu trong ngữ cành các CSDL lớn. Một số lập luận trong phần trước [HK0106] đã chỉ dẫn ràng, khai phá dữ liệu là bước phát triển mới cùa công nghệ CSDL, vì vậy nhiều nội dung trong khai phá dữ liệu là gân gũi với CSDL. Đồng thời, một số các đặc điềm phân biệt giữa hệ thống CSDL truỵền thống với hệ thống khai phá dữ liệu cũng đã được thào luận, trong đó dấu hiệu phân biệt điền hình nhất giữa nội dung nghiên cứu là quan niệm vê một giá thiết sẵn có một tri thức miền ứng dụng đầy đủ. Tài nguyên dữ liệu đầu vào cho các hệ thống khai phá dữ liệu aồm có các CSDL. các kho dữ liệu và các loại nguôn chứa dữ liệu khác. Chính vì K 30 do dó, trung không ít trường hợp, lĩnh vực kho d ữ liệu (data w arehouse) dược coi là m ột bộ phận cùa lĩnh vực khai phá dữ liệu và phát hiện tri thức trong CSD L. Hình 1.9. Tinh đa/liên ngành cùa khai phá dữ liệu N hư đã được trình bày, quá trình phát hiện tri thức làm việc với tập họp 4ữ liệu lớn m à trong nhiều trường hợp tập dữ liệu trở nên khổng lồ. Phạm vi tác động to lớn và đa dạng đòi hỏi các thuật toán khai phá dữ liệu phải đúng đắn và hiệu quả; chính vì điều đó cho nên, rất nhiều thuật toán khai phá dữ liệu đã được đề xuất. X indong W u và cộng sự [W K Q 08] cung cấp m ột danh sách gôm m ười thuật toán khai phá dữ liệu nôi tiếng nhất, đó là các thuật toán C 4.5, Ấ:-Means, SV M , A priori, EM , PageR ank, A daB oost, ANN, N aive B ayes và CA RT. M ột số nội dung cơ bản nhất về các thuật toán này được giới thiệu trong các phần nội dung liên quan trong tài liệu này. Đối với các lĩnh vực học m áy và thu nhận m âu, sự đan xen với khai phá dữ liệu (và K D D ) trải theo các nghiên cứu về lý thuyết và thuật toán đối với các hệ thống trích lọc m ẫu và mô hình dữ liệu (chú yếu đối với các phương pháp khai phá dữ liệu). Các phương pháp học m áy giám sát (phân lớp), không giám sát (phân cụm ), bán giám sát (phân lóp và phân cụm ) đã rất phổ biến trong khai phá dữ liệu, nhàm lựa chọn m ô hình và xác định tham số m ô hình trong các hệ thống K.DD. T rọng tâm của K.DD đối với việc m ở rộng các lý thuyết và thuật toán học m áy hướng tới bài toán tìm ra các m ẫu đặc biệt (những m ẫu m à trong m ột số ngữ cảnh còn được gọi là tri thức hữu dụng hoặc hấp dẫn) trong các tập hợp dữ liệu có dung lượng lớn của thế giới thực. N hư vậy, khai phá dữ liệu m ờ rộng nội dung học m áy thông qua các công việc lựa chọn dữ liệu đầu vào, trình diễn m ẫu, đánh giá m ẫu đầu ra ... trong ngữ cảnh m iên dữ liệu cân xử lý có dưng lượng rất lớn. K D D cũng có rất nhiều điểm chung với chuyên ngành thống kẽ, đặc biệt là phân tích dữ liệu thăm dò (EDA : Exploratory D ata A nalysis) cũng nh ư dự báo [H D 03]. H ệ thông K D D thường găn kêt với các thù tục thống kê đặc biệt đôi với m ô hình dữ liệu và năm băt nhiễu trong m ột khung cảnh phát hiện tri thức tổng thể. Các phương pháp khai phá dữ liệu dựa theo 31 thống kê nhận được sự quan tâm đặc biệt. Tuy nhiên cần phân biệt g iữ a bài toán thông kê và bài toán khai phá dữ liệu. C hẳng hạn, trong bài toán kiêm định già thiêt thông kê [H H N 04], cho trước m ột già thiết thống kê và công việc cân tiên hành là kiêm tra xem tập hợp toàn bộ các d ữ liệu quan sát được có phù hợp với giả thiêt thông kê nói trên hay không, hay cũng vậy. gia thiêt thống kê có đúng trên toàn bộ dữ liệu quan sát được hay không. N êu kiêm định cho kết quà không phù họp, có nghĩa là già thiết thống kê là không đúng trên tập dữ liệu quan sát. N hư vậy, tính đúng đắn của già thiết th ố n g kê được xem xét trên tập toàn bộ các dữ liệu quan sát đ ã có. T rong trư ờ n g hợp bài toán học khai phá dữ liệu, m ô hình kết quà khai phá dữ liệu là không được xác định trước. M ô hình kết quà cần phài phù hợ p với tập toàn bộ dữ liệu của m iền ứng dụng m à không phải chi với tập dữ liệu qu an sát được (tập dữ liệu quan sát được chì là m ột bộ phận m à th ư ờ n g là rất nhò so với m iền dữ liệu của thế giới thực, xem H ình 1.8), do đó cần đàm bảo các tham số m ô hình không phụ thuộc vào cách chọn tập dữ liệu học. C hính vì lý do cốt lõi này m à bài toán học khai phá dữ liệu đòi hỏi đáp ứng yêu cầu là tập dữ liệu cần có tính "đại diện" cho toàn bộ dữ liệu trong m iền ứng dụng và tập d ữ liệu kiểm tra cần phải đượ c chọn m ột cách độc lập với tập dữ liệu học. M ột số dấu h iệu phân biệt khác về m ặt thuật ngữ cũng được lưu ý, chang hạn khai phá dữ liệu dùng các thu ật ng ữ b iến ra/biến m ục tiêu, thuật toán khai p h á d ữ liệu, thuộc lính/đặc trung, bàn ghi,... trong khi đó xừ lý thống kê dùng các thuật ng ữ tư ơ ng ứng là biến p h ụ th u ộ c , thù tục th o n g ké, biến g ìà i thích, qua n sát,... N h ư đã được khang định tại các phần trên là, không phải tất cà các m ẫu đều hữu dụng và hệ thống cần đư a ra các tiêu chí để lọc các m ẫu được coi là hấp dẫn nhất. Thông thường các hệ thống sừ dụng một ngưỡng hấp dẫn cực tiêu cho các m ẫu được coi là tri thức. C hảng hạn, trong bài to án phát hiện luật kết hợp, người ta chi giữ lại các luật vượt qua ngưỡ ng độ hỗ trợ tối thiêu và độ tin cậy tối thiểu. N gay cả trong trư ờng hợp đó, k hông phái m ọi "tri thức" được hệ th ố n g coi là "hữu dụng" đều hoàn to àn phù hợ p vó i người sử dụng. Bước trực quan h oá trong quá trình K D D hiển thị các tri thức được hệ thống phát hiện m ột cách trực quan nhất để tạo thuận lợi cho người sử dụng (thông qua tri thức v à kinh nghiệm ) lự a chọn ra các tri thức thực sự hữu dụng cho m ục đích ứng dụng của người sừ dụng. P hủi hiện m áy với m ục tiêu là phát hiện các luật kinh nghiệm từ quan sát và thừ nghiệm ; m ô hình nhân qua phát hiện các kết luận c j a m ô hình nhân quá từ dữ liệu là những lĩnh vực nghiên cứu có m ối liên hệ với nhau. 32 1.7. Khuynh hướng phát triển của khai phá dữ liệu Như đã dược giới thiệu, không nhũng trớ thành một lĩnh vực khoa học - công nghệ thời sự, mà khai phá dữ liệu vân đang được phát triên rât mạnh mẽ. Thuật ngữ khai phá dữ liệu cũng như lĩnh vực khai phá dữ liệu đã trờ nên nồi bật, và vì vậy, thuật ngữ data mining và thuật ngữ machine learning (một thuật ngữ có quan hệ mật thiết với khai phá dữ liệu) đã được ghi nhận vào danh sách tốp 20 thuật ngữ khoa học hàng đầu do trang Web R esearchedD(l) liệt kê. Hiệp hội các nhà khoa học vê Phát hiện tri thức vậ Khai phá dữ liệu (The Association for Com puting M achinery's Special Interest G roup on Knowledge Discovery and Data Mining, viết tắt là SIGK.DD) được thành lập và hoạt động. Ban điều hành của SIGKDD gồm một số nhà khoa học hàng đầu thế giới về lĩnh vực này, do Piatetsky - Shapiro(2) chủ trì. Từ năm 1995, hoạt động điển hình nhất cùa SIGKDD là tồ chức Hội nghị khoa học quốc tế thường niên ACM SIGK.DD Conference on Knowledge Discovery and Data Mining. Khuynh hướng phát triển cùa khai phá dữ liệu còn quan hệ mật thiết với khuynh hướng phát triển của khoa học máy tính. • Khuynh hướng p h á t triển cùa khoa học máy tính Trong [Hop07], John E. Hopcroft trình bày về khuynh hướng phát triển của khoa học máy tính. Ông đề cập tới một số yếu tố nổi bật sau đây cùa xã hội điện từ (e-society) trong tương lai tác động tới sự chuyển biến cùa khoa học máy tính: - Tính sẵn sàng máy tính cà theo không gian và cà theo thời gian; - Tính đáp ứng tốc độ xử lý đối với mọi nghiệp vụ văn phòng (soạn tháo văn bán, email, chat, bàng tính); - Tính tích hợp máy tính và truyền thông; - Tính sẵn sàng dữ liệu dạng số hoá; - Tính kết nối m ạng cùa mọi thiết bị. Trong nghiên cứu của minh. J. E. Hopcroft sừ dụng kết quả nghiên cứu về khai phá dữ liệu văn bàn của Rich Caruana cùng cộng sự [CJG06]. Bài toán mà Rích Caruana và cộng sự giải quyêt (được giới thiệu chi tiết hơn tại C hương 2) được mô tả sơ bộ như sau: Cho trước một tập hợp (khoảng 300000) tài liệu khoạ học (công trình nghiên cứu) cần phát hiện ra các chủ đề khoa học chũ chốt và qua đó dự báo được xu hướng nghiên cứu phát triển các chù đề khoa học mới thuộc lĩnh vực khoa học máy tính. Giải pháp ' n www.researcherid.com (2) http://www.kdnuggets.com/gps.html 33 tiến hành không cần khai thác các chi dẫn cùa các công trinh, nghĩa lá chi sư dụng nội dung các công trinh. I linh 1.10 mô tả một ket qua nghiên cứu cua Rich Caruana và cộng sự. theo dó phát hiện ra 13 cụm chu để và cung câp ý tương về xu hướng phát triển cùa 13 cụm chù dề nói trẽn. Từ kết qua nghiên cứu nói trên cùa Rich Caruana cùng cộng sự và một số công trinh liên quan khác, J. E. Hopcroft giới thiệu một số nội dung lý thuyết cần được quan tâm đê làm nên táng khoa học giái quyết các bài toán thi hành xã hội diện tứ như sau: - Lý thuyết, mô hinh và giải pháp tìm kiếm. Thứ nhất, câu hòi tim kicm đã có sự thay đôi về chất từ câu hỏi m ang tính cụ thể. thống kê sang câu hỏi m ang tính tư vân và đòi hói sự phân tích phức hợp như: "Với tôi. m ua ô tô loại nào lá thích hợp?", "Hãy xây dụng một lịch sử có chú giải về lý thuyết đồ thị", "Tôi nên vào trường đại học nào?", "Các lĩnh vực của khoa học máy tinh đã phát triển như thế nào?",.-- Thứ hai, không gian tim kiếm là rộng lớn và câu hói được đặt ra mọi lúc. mọi nơi. - M ạng và cam biến. Trong một môi trường có tinh sẵn sàng theo không gian và thời gian, hoạt động có tính ngẫu nhiên, giao tiếp với môi trường thông qua các cám biến và kêt nôi m ạng các mức thành phân (mức cam biến, mức m ạng các m ạng con, mức các thành phần lớn và cực lớn....) cần được mô hình hoá với các giải pháp tích hợp hiệu quà. Tem poral Cluster Histogram s: Results NIPS «-means clusters Percentage D isơ tuuon (KM3j 86 87 86 39 90 9 1 92 93 94 95 '96 97 96 99 '00 Year chip, circuit, analog, voltage, vlsi kernel, margin, svm. vc. xi bayesian. mixture, posterior, likelihood, em spike, spikes, firing, neuron, neurons neurons, neuron, synaptic, memory, firing david. michael. john. richard. chair policy, reinforcement, action, state, agent visual, eye, cells, motion, orientation units, node, training, noaes. tree code, codes, decoding, message, hints image, images, object, face, video recurrent, hidden, training, units, error speech, word, hmm, reccgn ton. mlp Hình 1.10. Tinh hinh phát triẻn một số nhỏm chủ đề trong khoa học máy tinh qua phân cụm tài liệu khoa học [CJG06] 34 - Xứ lý dữ liệu nhiều chiều đồ sộ và chứa nhiều nhiễu. Tính đồ sộ cùa dũ liệu nằm trong xu thế bùng nố thông tin như đã biêt. Dữ liệu cân có nhiều chiều đế bieu diễn sát thực hơn về thực tại. Tính ngẫu nhiên cùng với tính phức tạp cua hệ thống dẫn đến việc dữ liệu có thê có chứa nhiều nhiễu. - Mô hinh và giái pháp tích họp hệ thống và tài nguyên dữ liệu. Dù sừ dụng phương pháp xây dựng hệ thông nào (chức năng, đòi tượng, kêt hợp,...) thi cách tiêp cận dựa trên thành phân đã trớ thành cách tiêp cận chung, rất hữu hiệu, đặc biệt là đối với các hệ thông lớn. Một trong những mô hinh toán học điên hình nhât liên quan tới các nội dung lý thuyết nêu trên là đồ thị lớn. Một ví dụ đơn gián là đồ thị Web được dê cập trong các máy tim kiếm hiện nay đã có số đinh lên tới hàng tỳ nút. Tính sẵn sàng, mọi lúc, mọi nơi đòi hỏi mô hình hệ thống được thiết lập dưới dạng đồ thị sẽ có số nút rất lớn. Hơn nữa, các đồ thị lớn này cần là các đồ thị ngẫu nhiên. Lời giải cho các đồ thị lớn hiện nhận dược sự quan tâm đặc biệt. • Khuynh hướng ph át triến của khai pliá dữ liệu Trang Web http://w w w .kdnuggets.com/ do Piatetsky - Shapiro chú trì là một trong những trang Web điền hình về lĩnh vực khai phá dữ liệu và phát hiện tri thức trong CSDL. Nhiều thông tin cập nhật nhất về lĩnh vực dược thông báo tại trang W eb này, đặc biệt là các kết quá thăm dò, cung cấp một sô thông tin hữu ích liên quan tới khuynh hướng phát triển cua lĩnh vực khai phá dữ liệu. M ột số nội dung cụ thê về khuynh hướng nghiên cứu của khai phá dữ liệu được đề cập dưới dạng bài toán thách thức trong các hội nghị khoa học về khai phá dữ liệu, chăng hạn như [ASG06, Son07]. Theo J. Han và M. Kam ber IHK0106), xu hướng phát triền khai phá dữ liệu đã và đang là các nội dung nghicn cứu có tính thời sự, rất đa dạng và phong phú. Việc phát triển các phương pháp và hộ thống khai phá dữ liệu đủ sức m ạnh và hiệu quả, xây dựng các môi trường khai phá dữ liệu tương tác và tích hợp, thiêt kê các ngôn ngữ khai phá dữ liệu, áp dụng các kỹ thuật khai phá dữ liệu để giãi quyết các bài toán ứng dụng lớn là những bài toán quan trọng trong nghiên cứu và triển khai về khai phá dữ liệu. Trong [YW 06], Qiang Yang và Xindong Wu giới thiệu vê 10 bài toán thách thức trong lĩnh vực khai phá dữ liệu, đã và dang cuốn hút các xu hướng nghiên cứu và triền khai đối với lĩnh vực này. Từ các nghiên cứu tồng họp cùa J. Han, M. Kamber và Qiang Yang - X indong Wu. chúng ta có the thấy một số xu hướng phái triền nghiên cíĩu và triển khai điền hình nhất về khai phá dữ liệu như sau: - Phát triển một lý thuyết thống nhất về khai phá dữ liệu. Như đã được trình bày, lĩnh vực khai phá dữ liệu dược ứng dụng rộng rãi nhận dươc sư 35 quan tâm cua đông dao các nhà khoa học thuộc các lĩnh vực nehiên cứu rãi đa dạnii. vi vậ\ trinh dộ phát triên hiện thời cua mồi một nghiên cứu vê khai phá dữ liệu lại mang tính quá đặc thù. Rât nhiều kỹ thuật dược thiẽt kẽ cho các bài toán riêng le. chăng hạn như phân lớp hoặc phân cụm. mà không có một cơ sơ lý thuyết thống nhất. Dù chưa hình thành được một khung lý thuyết thốne nhất, sone nhiêu nghiên cứu về khai phá dữ liệu dựa trên lý thuyết xác suất, lý thuyết dô thị. lý thuyết tối ưu.... đã được tiên hành và thông qua đó. một số thành phản vê khung lý thuyết chunti đã dân được hình thành. Theo cách tiếp cận mô hình Internet và Web dựa trên lý thuyết xác suất. Pierre Baldi và cộng sự đã hệ thống hoá các phương pháp và thuật toán khai phá dữ liệu Web [BFS03], Dragomir R. Radev quan tâm tới tình hình nghiên cứu về mô hình đô thị Web thông qua việc ghi nhận các công trình nehiẽn cứu liên quan [Rad09]. Trong [Zhu08], Xiaojin Zhu cung câp một cái nhìn khái quát vê tinh hinh nghiên cứu học máy bán eiám sát. mà trong dó có một khôi lượna dán” kê các mô hình dựa trên lý thuyết đồ thị và lý thuyết xác suất. Một khung 1\' thuvêt thône nhât được hình thành làm nên tañe K thuvêt cho các bài toán khai phá dữ liệu đa dạng như phân cụm. phân lớp. luật kết hợp.... cũne như cho các cách tiếp cận khác nhau cua khai phá dữ liệu sẽ tạo tiền đề thúc đây các nuhiẻn cứu thuộc lĩnh vực này. Đông thời, khunc lý thuyết thống nhất được xây dựng cũng hỗ trợ hoạt động phát triên dài hạn cua khai phá dữ liệu. - Mớ rộng miên ứne dụne khai phá dữ liệu cà về bê rộne và chiêu sâu.Phát triẻn các ứnti dụn« khai phá dữ liệu được mờ rộng tới thưcmo mại diện tư. tiêp thị điện tư và trớ thành trào lưu trong dịch vụ bán lé; đông thời, được tãng cường sừ dụne trong nhiêu lĩnh vực khác như phân tích tài chính, viễn thông, sinh dược phẩm và các rmành khoa học khác. Xu thế trình độ kinh tê tri thức của xã hội neày cana được tăng cường là tiên đẽ cho việc mơ rộng miên ửne dụns cua khai phá dữ liệu. Theo hướng kẻt hợp với các lĩnh vực khoa học khác, có thê thấv xu thế đang phát triên mạnh mẽ các ứne dụng khai phá dữ liệu vào bài toán Y - Sinh học. Môi trường, An toàn. Toàn vẹn dữ liệu và nhiều bài toán khác. Chăng hạn. hiện nay lĩnh vực khai phá dữ liệu Web đã liên quan mật thiết với thông tin học thông qua độ đo W ebometrics (một dạna của BibHometrics và Informetrics trong thông tin học) [Payn08]. Đồna thời, xu hướng tích hợp khai phá dữ liệu từ các miên ứna dụng khác nhau ngàv càns trơ nên rồ nét. Theo xu hướne đó. xuât hiện các bài toán khai phá tri thức phức hợp từ các dữ liệu phức tạp mà các dữ liệu này đứợc biêu diễn dưới dạng đô thị hoặc dưới dạnii các quan hệ phức hợp. 36 - Phát trien các phương pháp khai phá dữ liệu có tính khá cỡ và tương tác. Sự tăng trướng khối lượng các dữ liệu có rát nhicu chiêu và dòng dữ liệu toc dộ cao. Phù hợp với sự bùng nô thông tin và nhu câu phát triên ứng dụng khai phá dữ liệu, việc đề xuất các thuật toán khai phá dữ liệu có chức năng tự tương tác và tưưng tác lẫn nhau đã có tính ban chất. T rong m ột sô ứng dụng, chăng hạn, trong khai phá text hoặc phân tích an toàn hệ thân kinh, số chiều cua dữ liệu lcn tới từ hàng trăm triệu tới hàng tý đặc trung. T rong m ột số ứng dụng khác, chẳng hạn. trong các bài toán nghiên cứu về thiên văn hoặc về m ạng m áy tính, dòng dữ liệu là rất lớn (có thê lên tới hàng trăm ! B tại thời điêm hiện nay). Công nghệ khai phá dữ liệu hiện tại vẫn quá chậm dế chú động dược dối với các dữ liệu lớn như vậy. M ặt khác, khai phá dữ liệu dựa trên ràng buộc lả m ột định hướng quan trọng nâng cao năng lực tống thè cua quá trình khai phá dữ liệu có sự tăng cường tương tác với người sứ dụng. - Phát trien các m ô hình và plurong pháp tích hựp khai phá dữ liệu vào các hộ thống C SD L . hệ thống kho dừ liệu và hệ thống C SD L W eb. Các hệ thốn li này đã trớ thành trào lưu cua các hộ thống xứ lý thông tin. C hăng hạn, bài toán tích hợp W eb với kho dữ liệu bao gôm nhiều nội dung cua khai phá nội dung W eb dê xây dựnu dược kho dữ liệu với nguôn dữ liệu giàu có cua Web. Van dề quan trọnii khi tích hợp khai phá dữ liệu ớ đây là phái đảm bao rằnu. các phục vụ khai phá dữ liệu được coi là các thành phần phân tích dữ liệu ban chất cua hệ thống cần phai được tích hợp m ột cách trơn tru với môi trườim xir lý thông tin. - C huấn hoá các ngôn ngừ khai phá dữ liệu cùng với các phươnu tiện chuân hoá khác làm thuận tiện hơn việc phát trien có tính hệ thống các eiái pháp khai phá dữ liệu, tính liên thao tác cua các hộ thống và chức năng khai phá dữ liệu phức hợp. M ột sô kết quá ở m ức sán phâm công nghệ điên hình theo hưứng này có OI.H DB (O bject Linking and Em bedding, D atabase) dùng cho khai phá dữ liệu của M icro so ft, PM M L (P redictive M odel M arkup L anguage) cua D ata M ining G roup (D M G ) và C R ISP-D M (C Ross Industry S ta n d a rd P rocess fo r D ata M ining) cua nhóm phát triền C R IS P - DM (http://w w vv.crisp-dm .org/). - Khai phá dừ liệu dộng, không cân bàng và nhạy cam về chi phí. M ô hình khai phá dữ liệu càn găn kêt với thời gian, vì dữ liệu là không tĩnh và thay dôi theo thòi gian. T heo cách thông thường, m ô hình được học cần phù hựp theo thời gian, khi có dữ liệu hiện thời cần học tiếp m ô hình cho các khai phá tiêp theo, cỏ nghĩa là m ô hình cũng có tính xu hướng. M ột khuynh hướng cua khai phá dữ liệu là m ô hình được xây dựng bao hàm được tính xu hirớnu càng nhiều càng tốt. T ương tự về khai phá dữ liệu dối với dữ liệu không cân bann, nhạy cam vè chi phí. 37 - K hai phá d ữ liệu tro n g m ột k hung cánh m ạn e. tro n g đó có các m ạn g x ã hội trên Internet ho ặc các m ạn g m áy tính (khai phá d ữ liệu tốc độ cao dôi với d ò n g d ữ liệu tốc độ cao). L iên qu an m ật th iết tới khai p h á d ữ liệu tro n g khung cánh mạng là các bài toán khai phá dữ liệu phân tán và khai phá dữ liệu đa tác tứ, cũ n g n h ư khai p h á d ữ liệu liên quan tới các q u á trình. - T ăn g c ư ờ n g tín h trự c q u an h o á tro n g khai p h á d ữ liệu là giai pháp hiệu quả, nhàm làm cho quá trình phát hiện tri thức từ tập đô sộ dữ liệu đư ợ c thi hàn h b à n g các bộ c ô n g cụ trự c q u an hoá v à dễ d àn g tích h ợ p đ ư ợ c với các th àn h ph ần khai p h á d ữ liệu. N h ữ n g nội d u n g đư ợ c trìn h bày trên đ ây về k h u y n h h ư ớ n g p hái trien cùa khai p h á d ữ liệu m in h ch ứ n g th êm ch o k h ăn g đ ịn h răng, lĩn h \ ực này đ ang p h át triề n rất m ạn h m ẽ. Câu hỏi và bài tập 1. Phân biệt bài toán quản trị CSDL tác nghiệp với bài toán khai phá dữ liệu. 2. Phân tích vai trò cùa cơ sờ tri thức trong một hệ thống khai phá dữ liệu (Hình 1 6). 3. Phân biệt bài toán khai phá dữ liệu với bài toán kiểm nghiệm giả thiết thống kê. 4. Han và Kamber [HK0106] quan niệm khai phá dữ liệu và phát hiện tri thức trong CSDL là bước phát triển mới của công nghệ CSDL. Hãy lập luận làm sáng tỏ quan niệm trẽn. 5. Trinh bày một số mẫu truy vấn trong hệ thống quản trị CSDL và hệ thống khai phá dữ liệu. Phân tích làm sáng tỏ các mẫu truy vấn trong hệ thống khai phá dữ liệu là phức tạp hơn mẫu truy vấn trong hệ thống quản trị CSDL 6. Hệ thống khai phá dử liệu có nhất thiết có nguồn đầu vào là kho dử liệu hay không? Phân tích một số lợi điểm khi hệ thống khai phá dữ liệu có nguồn dữ liệu đầu vào chỉ là các kho dữ liệu. 7. Phân tích về tính "không tầm thường" của quá trình phát hiện tri thức trong CSDL. 8. Phân biệt bài toán khai phá dữ liệu mô tả với bài toán khai phá dữ liệu dự báo. 9. Phân tích tầm quan trọng của khâu làm sach dữ liệu và tiền xử lý dữ liệu trong quá trình khai phá dữ liệu và trinh bày sơ bộ về nội dung của khâu này. 10. Phân tích về sự cần thiết phải tiến hành tính toán giá trị một số đô đo nào đó trong các bài toán khai phá dữ liệu. 38 Chương 2 TỒNG QUAN VÈ KHAI PHÁ WEB 2.1. Giới thiệu về khai phá Text Khai phá Tcxt được bắt nguồn từ các hoạt động xứ lv văn bán mà con người đã tiên hành thường xuyên và không ngừng trong suốt lịch sứ phát tricn cùa loài người kê từ khi xuất hiện chữ viết; đấy là các hoạt động như tóm tất văn bản, phát hiện nội dung nôi bật, khai thác nội dung cùa một tác phàm văn h ọ c,... Có thê lấy ví dụ như Truyện Kiều cua N guyền Du. dù dã có rất nhiều công trình nghiên cứu về Truyện Kiều đã được công bố: luv nhiên, các nghiên cứu về Truyện Kiều vẫn tiếp tục được tiến hành và có thêm nhiều phát hiện mới lý thú. Từ bán chất đa nghĩa, phi ngữ cành cùa ngôn ngữ tự nhiên, có thê nói răng, các bài toán xử lý văn bán là vô cùng, vô tận, dặc biệt trong hoàn cánh bùng nô văn bản điện tứ hiện nay. Đặc diêm này vừa là một thuận lợi lớn. song cùng vừa lại là một khó khăn không nho đối với các nghiên cứu về khai phá Te.xt. Hiện nay. 90% lượng tliônu tin hiện có là thông tin không cấu trúc; cả theo tỷ lệ phan trám và theo số lượng tuyệt dối thì lượng thône tin không cấu trúc đang tăng trướng hang ngày [Sch09|. Điều dó chứng tò rang, nguồn dữ liệu dầu vào của khai phá Text ngày càng được tăng lèn với tốc độ tăng trướng cao. Trước hết chúng ta tìm hiếu về khái niệm khai phá Text. Khác với tính phong phú về cách diễn đạt khái niệm khai phá dữ liệu, khái niệm khai phá Text lại nhặn được sự thống nhất cao. chẳng hạn như fAna01. W it06, Sch09|; điều dó cũng hết sức tự nhiên khi đã thừa nhận nội dung và ý nghĩa cùa khái niệm khai phá dữ liệu. Thông nhât như vậy được lý giai băng việc cộng đồng nghiên cứu đã thông nhât về cách hiêu ràng, khai phá Text là dạng khai phá dù' liệu trên dữ liệu Text. Trong giáo trinh này. cụm từ "khai phá dữ liệu văn ban" hay "khai phá văn ban" được hiêu là m ang nội dung của khái niệm "khai phá Text". 2.1.1. Khái niệm Khai phá T ext là quá trình trích chọn ra các tri thức mới. có ẹiá tri và lác dộng được đang tiêm ân trong các vãn bán đè sứ dụng các tri thức này vào việc tố chức thông tin tốt hơn nham hỗ trợ con người. 39 về bàn chất, khai phá Text là sự kết hợp giũa khai phá dữ liệu \ a xư lý ngôn ngữ tự nhiên (NLP: Natural Language Processing). Chinh \i lõ dó. nhiêu nghiên cứu thuộc lĩnh vực NLP được coi là thành phần cua khai phá Text và ngược lại, nhiều kết quá nghiên cứu về khai phá Text lại được coi là các sán phâm phát triên từ NLP1' 1. Một sô nội dune cơ ban nhát vê Nl.p và xứ lý tiếng Việt được trình bày trong Chương 4. 2.1.2. Quá trình khai phá Text Quá trình khai phá Text là cụ thê hoá quá trình khai phá dữ liệu nói chung đối với dữ liệu Text. Với giá thiết đã xác định được: (1 ) bài toán khai phá Text và (2) miền dữ liệu Text thuộc miền ứng dụng, quá trinh khai phá Text trải qua các bước như sau: - Thu thập dữ liệu Text thuộc miên ứng dụng, ơ bước này, có hai diêu cần đuợc lưu ý. Thứ nhất, chi cần thu thập dữ liệu Text thuộc miên ứng dụng mà không phái là tập tất cá các văn bán có thế có cua thè íiiới ihực. Chang hạn, trong bài toán khai phá Text cùa Rich Caruana cùnu cộnu sự [CJG06]. miền ứng dụng quy định ràng, tập dữ liệu chi là tập tât ca các công trình khoa học; còn trong bài toán khai phá dữ liệu Text thuộc lĩnh vực y tê và chăm sóc sức khóe thì chi cần quan lâm thu thập các văn ban vê y té và chăm sóc sức khóe. Thứ hai, yêu cầu cốt lõi cúa bước thu thập dữ liệu là lập dữ liệu Text thu thập được phài dại diện được cho toàn bộ dữ liệu 'I cxt thuộc miền ứng dụng. Cháng hạn. tập dữ liệu trang Web mà máy tim kiếm Google thu thập được cho là đại diện cho toàn bộ tập mọi traníi Web trên Internet; tính đại diện đó được đám báo bằng thuật toán thu thập traníi Web (thuật toán Crawling) cùa Google phù họp với mô hình sinh các trang Web trên Internet. Mô hình sinh trang Web. tính ngẫu nhiên cúa việc thu thập dữ liệu là các yếu tố cần được quan tâm trong thuật toán thu thập transi Web. Nên nhớ ràng, tập trang Web mà Gootile thu thập được (còn được uọi là được Google đánh chi số) dù rất đồ sộ, song không phái là toàn bộ mọi trang Web có thề có. - Biêu diễn dữ liệu Text thu thập được sang khuôn dạng phù hợp với bài toán khai phá Text. Chương 5 sẽ trinh bày một số phươim pháp biêu diên I ext. trong đó một số công cụ và tài nguyên thiết yếu cua Xư K nuôn ngữ tự nhiên sẽ được sử dụng. Biêu diễn dữ liệu Text càng phù hợp với bài toán khai phá lext. thì chất lưựnu cua kết qua khai phá Text can” dược nâng cao. - Lựa chọn tập dừ’ liệu dầu vào cho thuật toán khai phá dữ liệu. Tronu hâu hêt trường hợp. tập dừ liệu thuộc miên ứng dụnti đã thu thập dược là rất http://www.ics.mq.edu.au -swan summarization projects full.htm 40 lớn, và vi vậy, trong nhiều trường hợp là vượt quá khả năng xứ lý (về không gian, vè thời gian) đối với các thuật toán khai phá dữ liệu. Chính vì lý do đó. cân chọn ra từ tập dữ liệu thu thập được một tập con đế thực hiện bài toán khai phá dữ liệu. Các yếu tố đàm bảo tính đại diện của tập dữ liệu thu thập được cũng dược áp dụng trong các giải pháp lựa chọn tập dữ liệu đâu vào cho thuật toán khai phá dữ liệu. - Thực hiện thuật toán khai phá dữ liệu đối với tập dữ liệu đã được lựa chọn đố tìm ra các mẫu, các tri thức. Chăng hạn. dôi với bài toán phân lớp văn ban. mẫu (tri ihức) được tích hợp thành bộ phân lớp kết quả và bộ phân lớp này sẽ dược sứ dụng vào việc phân lớp đối với các văn ban mới. - Thực hiện việc khai thác sư dụng các mẫu. các tri thức nhận dược từ quá trình khai phá Text vào thực tiền hoạt động. 2.1.3. Đặc trưng của khai phá Text Dặc thù về doi tượng dữ liệu vãn bán tạo ra một số dặc điêm của khai phá Text là khác biệt so với khai phá dữ liệu thông thường. Báng 2.1 trình bày một số đối sánh về m ột sô dặc trưnu giữa khai phá Text với khai phá dữ liệu nói chung [AnaOl |. Qua nội dung trinh bày trong Bảntỉ 2.1. có thê thây khai phá Text là lĩnh vực khai phá dữ liệu được phát triên uẩn dây. có thị trường rộng lớn, dối tượng là các văn ban không có cấu trúc, với m ột sô mục tiêu và phương pháp đặc thù. Bàng 2.1. So sảnh đặc điềm khai phá dữ liệu với khai phá Text [Ana01] Dấu hiệu phản biệt Khai phá dử liệu Khai phá Text Đối tượng dữ liệu Dữ liệu số/phản loại Văn bản Cẩu trúc đối tượng CSDL quan hệ Text dạng tự do Mục tiêu Dự báo, đoán nhận Tim kiếm thông tin liên quan, hiéu ngữ nghĩa, phân lớp/ phán bố Phương pháp Học máy: DT, NN, GA, MBR Chỉ số, xử lý mạng nơron, ngôn ngữ, kién trúc Kích cỡ thị trướng Trảm nghin phân tích viên từ cống ty lởn và vừa Hàng triệu người dùng từ hãng và cả nhân rinh trạng Quảng bá từ năm 1994 Mới quảng bá từ năm 2000 2.1.4. Một số bài toán điển hình M ột số bài toán diền hình nhất trong khai phá Text là [L ew 9l, AnaOl ]: 41 - Tìm kiếm (Search and retrieval): Quá trình tìm kiếm văn ban theo yêu :ầu cua người dùng. Nội dung của bài toán này là chọn ra một tập con các văn ban trone kho chứa các văn ban đê hiên thị cho người dùnu toàn bộ hoặc bộ phận các văn bản đáp ứng yêu câu cùa người dùng. Tronu trường hợp toàn bộ các văn bản dã được tập hợp vào kho chứa (CSDL văn ban), thi bài toán chí bao gồm công việc lấy ra (Retrieval) từ CSDL các ván ban đáp ứng truy vấn; ngược lại cần phái tìm kiêm (Search) văn ban từ mọi rmuôn và lấy ra các vãn ban đáp ứng. Yêu câu cua người sứ dụng được thê hiện dưới dạng truy vấn, trong đó dạng đơn gián nhất là từ khoá (keyword hoặc term), hiếu theo nghĩa "hãy tìm ra các văn bán có chứa từ khoá nói trên". Truy vấn :ó thề được trình bày dưới dạng phức tạp là "bicu thức" tô hạp các đặc Irirng trinh bàv văn bán trong ứng dụng cụ thê. Các phương pháp tìm kiếm vãn ban điền hinh là dựa theo chi sô (như Hxcite. Altavista....), dựa trên kiến trúc (như Yahoo. Lycos. Megaputer theo nền kiến trúc), dựa theo phân tích nhị phân và gốc từ (như HotBot. dt-Search). dựa trẽn ngữ nghĩa và ngôn ngữ (như các sàn phâm cua Megaputer theo nền ngữ nghĩa và ngôn ngữ) [FF02. AnaOl. Sla02. YN99Ị. Máy tim kiếm (search engine) là một dạng dien hình về hệ thống tim kiếm trang Web. mà theo mỗi truy vấn cua người sứ dụng thi máy tìm kiêm sẽ chi ra một danh sách các văn bản (xếp giám dần theo độ quan trọn” ) đáp ứng truy vấn cua người sư dụng. Trưcmg họp đặc biệt khi mà truy van chi là từ khoá (hoặc mộl tập từ khoá). thì vãn bán kết quá tim ra chi cân chứa từ khoá (hay tập từ khoá) xuất hiện trong truy vấn. C h ư ơ n g 6 - Hệ thong lìm kiếm sẽ trình bàv chi tiết về máy tim kiếm. - Phân tích ngữ nghĩa (Semantic analysis): Quá trinh dưa ra cách "hiêu" về văn ban thông qua mối liên quan ngữ nghĩa cua văn ban \ới tập khái niệm cho trước [BI-S03. AnaOl. YN99], Một bài toán nền tanu cua phân tích ngữ nghĩa là phát hiện quan hệ ngữ nghĩa trong văn ban |Gir08]. - Phân cụm: Quá trình nhóm các văn ban trone một tập vãn ban thành các "cụm", trong dó nội dune các văn ban trong cùnu một cụm là "ũãn uùi" nhau theo một độ do nào đó [BBM02. AnaOl]. Chươne 7 - Plum cụm văn ban trinh bày chi tiết về bài toán phân cụm. - Phân lóp: Quá trinh tự dộng xếp văn bán vào một tronu một số lóp văn ban dã xác định từ trước. Các uiái pháp phân lóp tự dộrm văn ban thường dược thiêt kê dựa trên các phương pháp học máy (Cã\ qu\ct định. Bayes, k-nmrời láng ííicng gần nhất). Như dã dược giới thiệu, phân doạn là quá trình kết họp cua hai quá trình phân cụm và phàn lớp: trước tiên tien hành phân cụm. sau đó tiến hành phân lớp [AnaOl. Slat02]. Các nội dun” cư ban vê phân lóp văn ban dược trình bày trong Chưcnm 8 - Phân lớp vãn hon -P — Trích chọn đặc trưng (Feature extraction): Quá trình phát hiện và lưu trữ lại những thành phần ngôn ngữ cân quan tâm dược xuât hiện trong văn ban. Phát hiện từ mang nghĩa (term), cụm từ mang nghĩa (feature) xuât hiện trong văn bán, biểu diễn văn bán theo các thành phân mang nghĩa đó hoặc sư dụng chúng trong các CSDL Web dược coi là thuộc vào công việc trích chọn dặc trưng. Trong một số trường hợp, các đặc trưng chưa xác định trước, việc xác dịnh chúng đồng thời với việc phân tích nội dung văn bàn; tuy nhiên, trong một số trường hợp khác, các đặc trưng (như tên người, công việc,...) có thể dược xác dịnh trước, việc phân tích vãn ban cho phcp phát hiện sự xuất hiện (có tần số) các đặc trưng đó trong vãn ban [Slat02, Cha()3]. Cần phân biệt khái niệm trích chọn đặc trưng ở đây với khái niệm lựa chọn (rút gọn) đặc trưng trong biếu dien trang Web, trorm đó việc lựa chọn đặc trưng dược dịnh hưứrm vào việc rút gọn tập các đặc trưng đã cho nham giảm bớt độ phức tạp xứ lv trong khai phá Web. - Tóm tắt văn ban (D o c u m e n t Abstract/Summarization): Từ một văn bản nguồn, cần xây dựng một văn bán đích "ngắn hơn" mà vẫn giữ nguyên (về cơ bản) được ngữ nghĩa cua văn bản neuồn. Tóm tát văn ban còn dược quan niệm như "hiếu văn bàn" (Document Understanding). l'on tại hai dạng điển hình trong việc xây dựng văn bán tóm tat. Dạng dầu tiên (Abstract) là đơn gián hon. trong đó văn bán tóm tat gồm một số câu sẵn có cua văn ban nguồn, hay văn ban tóm tắt là văn bản nguồn loại bó di một số (có the nhiều/rất nhiều) câu. Dạng thứ hai (Summarization) phức tạp hơn. mỗi câu trong" văn ban tóm tăt được xây dựng từ việc kết hợp các cụm từ xuất hiện ớ một số câu trong văn bán nguồn. Thông thường các hộ thống sư dụng giải pháp kết hợp hai dạng này. Tóm tất da văn ban (multi - document summarization) giái quyết bài toán vân dề xây dựng một văn ban tóm lăt cho một tập hợp các văn bán là một bài toán thường gặp trong khai phá Web. chăng hạn như. sau khi phân cụm trang Web thi một ycu cầu dặt ra là mô tả tóm tắt nội dung các văn ban trong cụm này. Viện Quốc gia vồ Chuẩn hoá và Công nghệ Mỹ (The National Institute o i'Standards and Technology) rất quan tâm tới các hoạt động ntihiên cứu và triên khai về hiôu văn ban. 1 loạt dộng đicn hình cua cơ quan này là tô chức hội nghị khoa học quốc tê thường niên vê hiếu văn ban với tên gọi là D o c u m e n t Understanding Conference (DUC) trong giai doạn 2001 - 2007 và do tỏ chức và Text Analysis Conference (TAC) từ năm 2008 tới nay. Gần đây nhất, TAC 2009 W orkshop"’ được tồ chức trorm các nuày 16 - 17/11/2009 tại Gaithersburg. Maryland USA. Tại các hội nghfD U C và trung gian) hoặc có trong các CSDL khách hàng. rhc OpenNet Initiative (http: "WWW.opennetinitiative.net') 56 - Mó hình (thực thế) dữ liệu: người sử đụng, khung nhìn trang Web, file trang Web, trinh duyệt, phục vụ Web, phục vụ nội dung, phicn người sứ dụng, phiên phục vụ.... - 'nến xứ lý dữ liệu: dữ liệu cấu trúc, dữ liệu nội dung, xử lý văn bán, rút gọn dặc trưng và tiền xứ ]ý dữ liệu đối với mô hình dữ liệu. - Phút hiện mẫu: bài toán phát hiện mẫu ở đây bao gôm hâu hêt các bài toán khai phá dữ liệu điển hình là phân tích thông kê, phát hiện luật kết hợp, phân cụm, phân lớp, mẫu tuần tự và mô hình phụ thuộc. Vấn đề đầu tiên mang đặc thù cùa khai phá sừ dụng Web, các vấn đề còn lại đều mang nội dung chung của quá trình phát hiện tri thức. Nguồn tài nguyên dữ liệu bao gồm các file biên bán sứ dụng Web tại máy chú Web. tại máy khách và các vị trí trung gian (khai phá mẫu truy cập) và các CSDL người dùng. Như đã được giới thiệu, khai phá sứ dụng Web được phân thành khai phá mẫu truy cập và khai phá xu hướng cá nhân (hoặc cá nhân hoá việc sứ dụng Web). Nhiều ứng dụng khai phá Web đã tích họp hai loại khai phá sứ dụng Web này. 2.3.1. Phân tích mẫu truy nhập Web K.hác với bài toán phân tích xu hướng cá nhân trong khai phá sứ dụng Wob sẽ được trinh bày ỡ mục tiếp theo quan tâm tới cá nhân người dùng hoặc một nhóm người dùng; bài toán phân tích mẫu truy cập Web quan tâm den khai phá những mẫu có tính phố dụng cùa tập người dùng khi truy nhập Web. có thế coi tập người dùng là đối tượng phục vụ của bài toán phân tích mẫu truy nhập Web. Thông tin truy nhập cùa người dùng dược Web server ghi nhận lại Irong Web server log theo mẫu log chung (Common Log Format: CLF), hoặc mẫu log chung mở rộng (Extended CLF: ECLF). Thông tin được lưu giữ liên quan dến phiên truy nhập cùa người dùng, thường bao gồm các thông tin là địa chi IP cùa máy người dùng (cho biết tên máy chú người dùng), thời điếm bắt đầu truy nhập, nhu cầu người dùng (phương thức, dịa chi Web. giao thức), mã trạng thái đáp ứng yêu cầu (binh thường, truy nhập không hoàn chinh, không lim thây,...), kích thước dữ liệu truy nhập, chi dẫn về dịa chi URL đi tới yêu cầu này, công cụ truy nhập Web cùa người dùng. I linh 2.7 trình bày một sô bán ghi KCI.F và một sò trường dữ liệu log. Theo hướng tiếp cận này, hệ thông khai phá sứ dụng Web không đòi hòi thòng tin về người dùng. Nhu đã trinh bày ớ trên, dơn vị dữ liệu xác định một lần sử dung Web chinh là một phiên làm việc người dùng, dữ liệu về phiên làm việc dã được ghi trong logiĩle cua hệ thông. 57 f Address Usend T im e k ethod/ URL/ Protocol S i lis S c e Refen ; tr i 123 456 73 6 - - [2 M p f/1 9 9 3 03 04:41 -0500] 'G T A . h M HTTPM.0* 200 MD0 M o a lr t . l 14 (W ir9 5 .il 122.456 7a b ■ - Ị2 ỈM p r/1 » 3 :0 3 C 5 :3 4 -0500] \ 5 T B htmí HTTPM.D* 200 I2D 50 U o a b t t w r 123 455 73 9 - - [2^A p r/l9 93 :D 3 06:02 -0500] ? )S T /C flhbfV pl HTTP/1.0" 200 5DM 3 htmi U o z ila 'j »4 ( W ir « 1 12345e 73.9 - - [2 M p " 'W 3 :0 3 < » :5 8 -0500] 'G J A h W HTTPM.D* 200 3380 M ozila ilf 4 .Z W in N T 12345e .78 B - p U p r / IW S Q 3Ủ 742 -0500] "G T B hlm l HTTPM D* 200 2050 Ih tm l M o u la il! 4 2. W inNT) 12345S.73.B - - [2uA pr/1d98 0309-50 -0500] 'Q T C.htm lH TTP /1.0“ 200 1820 Ih tm l U o a la ịlf 4 2. W inNT ) 1 2345e 78.9 - - [2 M p f/i9 9 3 03 1D:D2-0500] "G T O h t n l H T T P /ID * 200 2270 : hcml U o o l* 3 4 (W in ö 5 1 1 23455 73 8 - [ 2 ^ / 1 9 9 8 . 0 3 10:45 -0500] 'G r r jt tr r t H T T P / 1 . 0 ' 2Ũ0 9430 í í t m M o a lí llẳ 4 2 .W inN T 1 2 3 4 5 6 7 8 8 • - [2ầvA pr/1993: D3 123 3 -0500] 'G T G h t n l HTTP/1 J}‘ 200 7220 ỉ html U o zila S 4 ( W r t 6 . ll 2 09 4 5 Í 7 3.2 ■ ■ [2 M p r / 1993 Q5 06:22 -0500] 'G ĨT A h r t HTTP/1.D* 200 3260 M o zila ß !4 (W rrS í.ll 2 00 45 6 73.3 - [2^A pr/1993:Q 506:ũ3 -0500] ^ ĨT D .M m lH T T P /1.0 " 200 1680 u tm l M o a U tt 14 (W in05.1) Hình 2.7. Một vi dụ vẻ mẫu log chung [CooOO] Từ dữ liệu được lưu aiữ tại Web server log (và các log khác), các nhà khai phá dữ liệu có thê khởi tạo các CSDL, các kho dữ liệu và tiên hành nhiêu bài toán khai phá dữ liệu như tim mối quan hệ nội dunu eiữa các trang Web (thôna qua mòi liên hệ aiữa địa chi URL tới và trana Web), thói quen truy nhập các vùng naười dùng, xu hướng truy nhập người dùng,... Như được trinh bày trong [Pia06]. ngoài phương thức sừ dụng các tiện ích cua hệ điêu hành đê phãn tich Weblog, khai phá sứ dụng Web còn sư dụnu một số công cụ hỗ trợ khác, chăng hạn như gawk, phiên bàn phần mềm tự do (GNU)"1 cua công cụ a\vk (mang tên những người thiết kế nó là Alfred V. Aho. Peter J. Weinberger và Brian w . Kemighan). Hình 2.8 trinh bày một kết qua phân tích W eblog [Pia06]. Mầu được khai phá từ logíile được sư dụne theo nhiêu phươne án và một phương án sừ dụng điên hinh là dẫn dăt online người sư dụng. Trẽn cơ sờ thành viên truy nhập hiện tại cua người dùng, căn cứ vào các luật truy cập (tri thức) đã được phát hiện, hệ thông dân dăt người dúna phù hợp với luật truy cặp (cũng được coi là phù hợp với tư duy hiện thời cùa rmười dùng). Renáta Iváncsy và István Vajk [1V06] nahiên cứu về khai phá mẫu tuần tự các logfile đôi với tập trana Web. dãy Irane Web và đồ thị Web. Hinh 2.9 trinh bày sơ đô khai phá sử dụng \\'eb phát hiện ba loại mẫu nói trẽn. Các tác gia sư dụng thuật toán Itemset Code đê khai phá tập trang \\'eb. thuật toán SM-Tree đê khai phá dãy trang Web và thuật toán PD-Tree đẽ khai phá đồ thị Web. h t t p : / / \ v \ v \ v . £ n u . o r e / s o f t \ v a r e / £ a \ v k / 58 CtMteWt «rftft Mut VtJion K l l i i k n n ' V S t v d i E n d i * 1 N O Ti s » w à E n d feu Ĩ 9 * * . s«ot ụ n ỉlíd K t t « l * , 0 % 2901 1 c « ri*đ » ? .î% 200 ĨIỈ0%9 i t n . 29« ► M l 1 .6 * « H t ợ v t in ơ í 7 0 % m I V * . ì í l l < * v 5 % m k p « n j-9 « , iW otỉ#/ v s % 4 « * » . l * 1614 2 ÎW Hern rc *n i H trtlO T r ĩ ü a a n n u Hinh 2.8. Kết quả phân tích nguồn truy nhập theo các quốc gia tới trang W eb KDnuggets, tuần 21-27/5/2006 [Pia06] LOG files Preprocessing Data cleaning I_Sesssion identification — cData conversion Frequent Frequent minsup Frequent Item set SequencesSubtree D iscovery Discovery Discovery Pattern _ L c A - - — — X < R ESULTS Analysis H inh 2.9. Sơ đồ khai phá mẫu tuần tự từ logfile [IV06] 59 lòn tại hường nghien cứu khai phá sừ dụng Web khôna chi quan tãm tới việc phát hiện các tri thức (điên hình là luật kết hợp) tiềm ân trong nội dung các trang Web được lưu giữ tạm thời tại Web server, m à còn cho phcp nhận diện được hành vi sứ dụng Web cúa người dùng. Thuật toán khai phá sứ dụng Web còn cần phải quan tâm tới một số vấn dề liên quan khác. Chăng hạn. cần thi hành các giải pháp lưu trữ các trang Web "một cách có lợi nhât" trong hoàn cảnh hạn chê về dune lượne bộ nhớ được quy định cho vùng W eb-cache. Một số giài pháp điều phối cachc như GDSize. GDSF, LFUDA, LRU,... được thi hành nhàm loại bo các trang Web "không hữu ích" ở vùng W eb-cache; các chiến lược nay hoạt động tương tự như các chiến lược loại bò trang bộ nhớ trong hệ điều hành. Nghiên cứu cùa Qiang Yang và Haining Henry Zhang [YZ03] khărm định, chiến lược caching GDSF (Greedy-Dual- Size-Frequency) có nhiều lợi thế. vi vậy là một phương án lựa chọn tốt. Một số kết quà khai phá sử dụng Web dược giới thiệu chi tiết trong [BerOO, M S99, Pia06, CooOO, BFS03], Trong [BFS03Ị, Pierre Baldi và cộrm sự đã trình bày các mô hình và nên tảng ứng xứ của người dùng trên Web. Loại mô hình điên hinh nhất là mô hình M arkov với giả thiết Markov bậc ]. Theo các tác giả, dữ liệu tại máy khách hàng, chăng hạn. hoạt động truy nhập Web của người dùng được các phân mềm máy khách ghi nhận cũng là nguồn tài nguyên rất có ích cho khai phá sừ dụng Web. Khai phá mẫu truy cập theo luật kết hợp: Loại mẫu điển hình nhất trong phân tích mẫu truy nhập Web là luật kết hợp. Phần này giới thiệu sơ bộ về luật kết hợp và thuật toán Aprioi khai phá luật kêt hợp. Thuật toán Apriori và các biến thế cùa nó được sư dụnu rộng rãi đê giải quyết bài toán phát hiện luật kết hợp từ logíìle. chăne hạn như [IV06. FL03. MD01 ]. • L u ậ t kết lìựp Cho một tập mục I = {i 1, 12,..., in}, mỗi phần tử thuộc I được eọi là một mục. Mục còn được gọi là thuộc tính và 1 cũng được gọi là tập các thuộc lính. Mỗi tập con trong I được gọi là một tập mục, số lượng các phần tư trong tập mục được gọi là độ dài cua tập mục. Cho một CSDI. uiao dịch D = {t|. t2„... tm}, trong đó mỗi tj là một eiao dịch và là một tập con thuộc I. Vê mặt thực tiên, môi giao dịch t| là một danh sách các mục (ten mặi hànu) trong giao dịch (phiếu giao dịch hàng). Ớ đây số lượng giao dịch (lực lượníi cúa D ký hiệu là |D| hoặc card(D)) là rất lớn. Cho X, Y là hai tập mục (hai tập con của I). Luật kết hợp được k\' hiệu là X -» Y. trone đó X n Y = 0 . thề hiện mối ràng buộc cua tập mục V theo tập mục X theo nghĩa "X kéo theo Y" ra sao vê sự xuất hiện tronu các tĩiao 60 dịch. Tập mục X được gọi là xuất hiện trong giao dịch t nếu như X C t, và có thê được diễn giải là "mọi tên mặt hàng trong X đêu xuât hiện trong phiếu giao dịch t". G iá trị của luật kết hợp X -> Y được thề hiện thông qua hai độ đo là độ hỗ trợ supp(X —> Y) và độ tin cậy conf(X —> Y): - Độ hỗ trợ của một tập mục X (ký hiệu supp (X)) được định nghĩa là: supp(X) = |{t e D: X C t}|/|D| - supp(X -> Y) = supp (XY) là tỷ lệ giao dịch có chứa (X u Y) trong tập D. - conf(X —> Y) = supp(X —» Y)/supp(X) là tỷ lệ tập giao dịch có chứa (X u Y) so với tập giao dịch có chứa X. Từ định nghĩa ta có: 0 < supp(X —> Y) < 1 và 0 < conf(X -» Y) < 1. Theo quan niệm xác suất, độ hỗ trợ là xác suất xuất hiện tập mục X u Y, còn độ tin cậy là xác suất có điều kiện xuất hiện Y khi đã xuất hiện X. Luật kết hợp X —> Y được coi là một "tri thức" ("m ẫu có giá trị") nếu xảy ra đồng thời supp(X —» Y) > m insup và conf(X -» Y) > m inconf với m insup và m inconf là hai ngưỡng cho trước. Tập mục X có độ hỗ trợ qua ngưỡng m insup (supp(X ) > m insup) được gọi là lập p h ổ biến. Mục tiêu cùa khai phá luật kết hợp là tìm ra tất cả các luật kết hợp có giá trị. Đe giải quyết bài toán trên, trước hết cần tìm ra mọi tập phổ biến, mỗi tập phổ biến đóng vai trò của tập XY trong luật kết hợp X -> Y. • T huật toán A p rio ri Thuật toán Apriori là m ột thuật toán điển hình tìm luật kết hợp [W KQ08]. Thuật toán dựa theo tính chất Apriori phát biểu rằng: "tập con bất kỳ của m ột tập phổ biến cũng là một tập phổ biến", tính chất này hiển nhiên đúng. Nội dung quan trọng nhât của thuật toán Apriori là tìm ra được tất cà các tập phồ biến có thề có trong D. Thuật toán hoạt động theo quy tắc quy hoạch động, nghĩa là từ các tập Fj = {Cị I Cj tập phô biên, |cj| = i} gồm mọi tập mục phổ biến có độ dài i với 1 < i < k, đi tìm tập F|;+1 gồm mọi tập mục phổ biên có độ dài k + 1. Trong thuật toán, các tên mục i|, i2, i„ (n = |D|) được sắp xếp theo một thứ tự cố định (thường được đánh chi số 1 2 n). Mô tà thuật toán Apriori như sau: Thuật toán Apriori [WKQ08]: Input: - Cơ sờ dữ liệu giao dịch D = {t 11 giao dịch} - Độ hỗ trợ tối thiểu minsup > 0 Output: - Tập hợp tát cả các tập phổ biến 61 0: mincount = minsup * |D|; 1 F, = {các tập phổ biến có độ dài 1} 2 for (k=1; Fk *0: k++) do begin Ck»i = apriori-gen (Fk)i II sinh mọi ứng viên độ dài k+1 3. for t e D do begin 4 Ct = {c e CR»1 I c e t}; //mọi ứng viên chứa trong t 5. for c e c, do 6 c.count ++; 7. 8 end 9 10 end Fk+1 =(C€ Ck-n I c.count > mincount}; 11. Answer VA Fk ; Thù tục con Apriori-gen có nhiệm vụ sinh ra các tập mục ứng viên có độ dài k + 1 từ Fk (các tập phô biến có độ dài k) được thi hành qua hai bước chính như sau: - B ư ớ c nối: S inh các tập m ục Rk»i là ứng v iên tập phô b iên có độ dài k + 1 bàng cách kết hợp hai tập phổ biến Pk và Qk có độ dài k v à trù n a nhau ớ k - 1 mục đầu tiên: = P k u Q k = { i i , i k - 1 , i k , i k } v ớ i p k = { i ị , Í2,..., ik-1, ik} v à Q k = { i | , Í2,..., ik-1, i k } trong đó ii < Ỉ2 <... < ik-1 ắ ik ắ ik - - Bước tia: Giữ lại tất cà các Rk+1 thoả mãn tính chất Apriori (VX c Rk-I và |X| = k => X e F|(), nghĩa là đã loại (tỉa) bớt đi mọi ứng viên Rk-1 khône đáp ứng tính chất này. Trong mỗi bước k, thuật toán Apriori đều phài duyệt CSDL D. Khởi động, duyệt D đề có được F]. Các bước k sau đó, duyệt D đế tính số lượng giao dịch t thoà mãn từng ứng viên c cùa Ck+1 (mỗi giao dịch t chi xem xét một lân cho mọi ứne viên c). Ket qua của thuật toán Apriori là tập F = F1 u F2 u... u Fk, trona đó k là số được xác định qua vòng lặp từ 2 đến 10 cùa thuật toán. Sau đó, Vc £ F cho c đóna vai trò như X ư Y cùa luật kết hợp (X —>Y) thực hiện việc tách c thành hai tập mục con rời nhau X và Y (c = X - Y) và tính độ tin cậy conf(X —>Y) = supp(c)/supp(X) = c.count/x.count. Ví dụ: Trone [IV06]. Renáta Iváncsv và István Vajk sử dụna các thuật toán biên thê từ Apriori đê phát hiện luật kêt họp và luật tuân tự tư dữ liệu tại lcmíìle (Hình 2.10). 62 opinion L m x &|W(j & rniçç & b u s ie s * & t>t>9 living L business i sports L fcfas & rnisc & bus>iri«&» & sporlfc ne*>s &tech *. ii^ng & business &spons nwi/s & lj»hg 4- business 8. bbs fronlpage ^ lech & hvin 9 A business i sports fro n lp a g a i. o p in io n g . h o n g L s p o r ts f>onip*ije & i«ch & opinion fck»ing frontpage &. lech & on-ar & business & sports nsws & rniçc 8< çportç & bbs news £■ i ech L or> air i bL/3ness i. spon s ney» & livrig & business 8. spcHs nfrws & buam ees & spone 1 bbs mise & Irring & iravd tech & li»ing &. sporls i. bbs loch L business £ sperfs £ bbs ne«vs & mise 8< lr»ng & business on-air £ business & sports & bbs ne*« & rech & miec & bbs on-air L mise i busness & sports tech & nuise ir w e i —> on-ar 90 2G% m fec local 2 .0 7 % -> frontpage 90 21% -> frontpage 2 .Û2% 90 my. frontpage -> fro ntp ag e spD rb fontp^g« æ æ * lo cal -> trontpage 1 .53% -> tontfiage BB.00%1 .72% »? tonipage 60 01% o n-air m rsc on-air •-> news B7.B7% o n -a r -^ tra n tp a g e 1 .59% nine B7 B1% -> nevrs 1 .51 % 67 60% o n -a r neArs •-> news B7 5£jy. ne’vn/s trcn tp a ge -> n&/vs 1 .49% -> t-orrtpagi 87 5694 -> frontpage 1 .46% B7 43% lo cal ner^s -> Kintpajje 87 ie% trontpage -> Trorrtpage b i£ in e 3s 1 .35% -> tonnage E6.7D% - p on-sit 1 .33% 06 55% n e w s sports -> frontpage E6.S2% n e w s bbs 1 23% tanlpago BE 4D% - > Vontpag* 1 .16% 66 22%heahh local “ > tanlpage EE 72% misc -> fro ntp ag e frcn tp a ge 1 .16% -> t-ontpage æ 10% - > tonlpage 1 .15% EE IE% o n -s ir -> local "> on-«*r œ œ % mrsc -> cn-air misc 1 .1 5 % teefi 8. IMng & business &. sports na*n L livng L sports & bbs -> tontpage -» tanlpago BB.DS% E6 99% frontpage frontpage livhg 1 .14% miic 1< business & sports fro n lp a g a £ -1o c h £ o p in io n L s p o r ts news & option & h «mg & spoils mise L business & travel - > frontpage f6.73% local -> frontpags -> frcntpage 1 .1 3 % —> nunc EB 7B% 1 .12 % -> tonlpage 66 69% heaHh -> m iac -> on-ar B5 Bfi% misc -» on-air -9 on-air 1 .10% news & rech & miec i busness mise L business & bbs -> Vorrtpage --> tonlpage 06 63% B5 57% lo ca l -> m isc -> local 1 .09% tech & lr new® ES 49% misc -» nev/s 1.06% local &nm«c tbueirese 1 spons now L opinion & business £ bbs -> frontpage tantpagg B5.43% BE 32% newB iv in g 1 .0 6 % news & mise & Irvng & sf>oit% n ï « £ on-an & businost L sports - > frontpage 66.19% on-air misc on-air misc 1 .00% f ra n lp a g u B5D1% a) b) Hinh 2.10. Kết quả phát hiện luật kết hợp và luật tuần tự từ logfile [IV06] 2.3.2. Phản tích xu hướng cá nhân Như đã giới thiệu, phân tích xu hướng cá nhân nhám tới tính cá nhân hoá, vỉ vậy dữ liệu cũng cần có tính cá nhân hoá, hoặc ở logfile ớ máy khách, hoặc ở CSDL khách hàng, hoặc dữ liệu thu nhận online với khách hàng. Phần này giới thiệu một số nội dung phân tích xu hướng cá nhân không có CSDL khách hàng và các hệ thống tư vấn khách hàng. • Pliân tícli x u hư ớ n g cá nhăn từ máy klìáclí Hình 2.11 trình bày hệ thống khai phá sử dụng Web có sử dụng dữ liệu người dùng ở máy khách cùa Tarmo Robal và Ahto Kalja [RK07]. Thông tin người dùng được các phàn mêm hệ thông tại máy khách được trích chọn và dữ liệu sử dụng hệ thống tư vấn cho từng người dùng cụ thề. Trong [ZHF05], Baoyao Zhou và cộng sự đề xuất hệ thống dựa theo logfile xây dựng các ontology sử dụng Web đế tư vấn người sử dụng hệ thống (Hình 2.12). 63 = £ LOG SYSTEM U sage Data C apruring D etection o f Locality W indow Size \Y W e b S i t e Data M illingRefined Topology Recommended Sub-Topology Tactical A daption Strategic A daption Hình 2.11. Sinh tư vấn dựa trên trích chọn tiểu sử người dùng [RK07] w*t> UUKN ___ Cwdpgy _<í Clierrt-íide O C w doflï ¿cc4tt Loot, ¿ S , Gwwra*on VMUugẽ Ing« lnt»m*t " ẫ ’ i - ưtei Semantic w<à> P*riaiafaÄOii w*b P r e p r e c Ê î i i f t g • 0 C ô í i i í r u d Ì A ộ C ô l * * o i4f > /ti rfd.iù-.ii Hình 2.12. Hệ thống khai phá sử dụng Web tư vấn hướng cá nhân: Kiến trúc hệ thống (trên) và sinh ontology sử dụng Web (dưới) [ZHF05] M ột Số thông tin hành vi người dùng cũng được m ột số hệ thốrm khai thác nhàm khai phá chuỗi hành vi của người dùng và từ đó có dự báo hành vi tiếp theo của người dùng để chuẩn bị sẵn các tài nguyên phù hợp với thao tác tiêp theo cua người dùng. 64 - n e n u n g vun ỉucn rg 1 lệ thống tư vấn khách hàng là một ứng dụng diến hình của khai phá Web Irong hoạt dộng tư vấn khách hàng. Trong hệ thống này, CSDL khách hàng lưu trữ về thông tin khách hàng đăng ký. Thông tin có được từ CSDL khách hàng cho phcp: - Kêl nối được các phiên làm việc cúa cùng một khách hàng và vì vậy, tạo thuận tiện trone việc kháo sát mỗi quan hệ khách hàng - mặt hàng. - Ket nối được nhóm khách hàng có cùng một (hoặc một nhóm) thuộc tính như giới, độ tuổi, nghề nghiệp, thu nhập,... Trong một số hệ thống, một sô thuộc tính mô tả thị hiếu của khách hàng cũng được đưa vào CSDL. Trong [BFS03], Pierre Baldi và cộng sự dành một chương trình bày về các mô hình và ứng dụng thương mại trên Web. Dữ liệu về khách hàng có tại máy phục vụ, tại máy khách hoặc tại các vị trí trung gian (chẳng hạn, tại vị trí cung cấp dịch vụ Internet như tại máy phục vụ proxy), ứ n g dụng điển hình là các hệ thống tư van khách hàng tự động. Lọc cộng tác là cách tiếp cận chính yếu nhất trong hệ thống, theo đó, hệ thống sứ dụng các chọn lựa của các cá nhân trong quá khứ đề dự báo sự chọn lựa mới và đưa ra một tư vấn mới. Hai mô hình lọc điến hình theo cách tiếp cận này được kháo sát, đó là mô hình lọc cộng tác người láng giềng gần nhất và mô hình lọc cộng tác d ự a trê n m ô h ìn h . Tư tường cùa mô hình lọc cộng tác người láng giềng gần nhất cũne rất đơn giản. Dối với một rmười dùng a, trước hết tìm ra tập các người dùng "tương tự với a" trong dữ liệu lọc, sau đó sử dụng chọn lựa đối với một thuộc tính cùa các người dùng tương đồng với a đế dự báo chọn lựa của người dùng a dối với thuộc tính đó. Trong mô hình lọc cộng tác người láng g iề n g g ầ n n h ấ t, c ầ n g ià i q u y ế t c ác bài to á n x ác đ ịn h trọ n g số tro n g p h ư ơ n g trình dự báo. thu gọn số chiều bài toán, tính toán và phân cụm. Trong mô hình lọc cộng tác dựa trên mô hình, trên cơ sở thừa kế các mẫu lựa chọn của người dùng trong quá khứ, cần xây dụng không trực tuyến một mô hình kỳ vọng về mối quan hệ giữa các mục hàng. Sau đó, mô hỉnh này được sử dụng trực tuyến đế dir báo sự chọn lựa cùa người dùng mới. Mô hình hướng tới yêu cầu tính toán thời gian thực, trong đó. với một mô hình dã dược xây dựng, thời gian dự báo không phụ thuộc vào số luợng khách hàng có trong CSDL. Mô hình lọc cộng tác dựa trê n m ô hình được phân loại thành mô hình mật độ kết nối và mô hình phân bố có điều kiện. Tồn tại một số mô hình trộn giữa lọc nội dung và lọc cộng tác. 65 2.4. Khai phá cấu trúc W eb Theo Pierre Baldi và cộng sự [BFS03], Internet được nhìn nhận dưới dạng đồ thị theo nhiều khung nhìn khác nhau. Theo khung nhìn s ật lý. đô thị có các đinh là các đối tượng vật lý thực sự và các cung là các đ ư ờ n e vật lý liên kêt các đình. T heo khung nhìn trừu tượng hơn, đồ thị có các đinh là các trang Internet và các cung là các liên kết giữa các đinh này. Dâv cũng là khung nhìn cùa KLhai phá cấu trúc W eb (vạ khai phá W eb). T rên Internet còn có nhiều hệ thống dược nhìn nhận dưới dạng đồ thị như m ạng địa chi e-m ail. m ạng blog, m ạng người dùng trong m ột diễn đàn. Khi quan niệm Internet là m ột xã hội ảo, thi mọi m ạng tồn tại trên Internet đều được coi là m ạng xã hội. Khai phá cấu trúc W eb sử dụng các kiến trúc liên kết W eb đề phát hiện được mô hình về cấu trúc liên kết của Web, dựa trên kiến trúc topo cùa các liên kết với mô tà hoặc không [Lee05, B FS03]. Khai phá cấu trúc W eb gồm hai loại cơ bàn, đó là khai phá đồ thị W eb và khai phá cấu trúc trang Web. 2.4.1. Khai phá đồ thị Web K hai phá đồ thị W eb là bài toán cơ bàn nhất và cũng điền hình nhấl trong khai phá cấu trúc W eb. Đồ thị W eb được coi như m ột ví dụ về mạng xã hội, m ột đôi tượng nghiên cứu hiện đang rât được quan tâm . N hãc lại, trong đô thị W eb thì trang W eb là đỉnh và m ột trang W eb có cune tới một trang W eb khác khi m à trong nội dung cùa nó có liên kết trở sang trang Web kia. Đồ thị W eb được xem xét dưới dạng có hướng hoặc vô hướng tuỳ thuộc vào bài toán được đặt ra. M ột bài toán kinh điển trong đồ thị W eb là bài toán T ính hạng (độ quan trọng) trang Web. Hạng trang Web được sử dụng trong nhiều tinh huống. C hăng hạn. hạng trang W eb được dùng để dẫn dắt đường đi trên W eb, những trang có hạng cao được dẫn dắt đi thăm trước. T rong m áy tìm kiếm, hạng trang W eb dẫn dắt thứ tự hiền thị kết quà tìm kiếm , theo đó. trän e Web có hạng cao hơn dược hiên thị trước trang Web có hạng thấp hơn. Tính hạng trang W eb có liên quan tới m ô hình sinh trang W eb trong hệ thống Web [Hav02. H op08, BFS03], Tính hạng còn được ứng dụng trong bài toán phát hiện địa chi mail sapm trong mạng e-mail, theo đó các địa chi e-mail có hạng thấp có khá năng cao là một địa chi spam. Pierre Baldi và cộng sự [BFS03] cung cấp m ột cái nhìn tổng quan về đồ thị Web cùng một số vấn đề cơ bàn nhất trong khai phá đồ thị Web. Trong giáo trình này, m ột số kiến thức cơ sờ toán học về đô thị W eb được trình bày ở Chương 3 và bài toán tính hạng trang W eb được trinh bày ờ C hươna 6 . 66 2.4.2. Khai phá cấu trúc trang Web Trang Web là một đối tượng dữ liệu bán giám sát. cấu trúc cùa trang Web tuân theo quy dịnh của ngôn ngữ dịnh dạng trang Web (chăng hạn. IITMI.). Khai phá cấu trúc trang Web thực hiện việc phát hiện các mẫu từ tập các kiến trúc trang Web. Đối tượng dữ liệu trong trường hợp này là khung trang Web gồm các đối tượng "thê" và cấu trúc giữa các thè này. Ket qua cùa khai phá cấu trúc trang Web được sứ dụng đê hỗ trợ các bài toán khai phá dữ liệu Web khác. Trong nhiều ứng dụng, khai phá cấu trúc trang Web dược kết họp cùng các loại khai phá Web khác, đặc biệt là khai phá nội dung trang Web. Dã có công trình nghiên cứu có giá trị vê khai phá cấu trúc trang Web, chăng hạn [ACM03, AM03, HA09, LGZ03, RGS04, WHW09], Davi de Castro Reis và cộng sự [RGS04] nghiên cứu về bài toán trích chọn lự động tin tức Irên Web theo cách tiếp cận khoáng cách cây. Các tác giá chọn cấu trúc dạng cây đê biêu diễn trang Web và sừ đụng độ đo chi phí chuyến đoi cây (Tree Edit Distance) dề đánh giá độ tương tự về cấu trúc cùa các trang Web. Với nền tảng là thuật toán RTDM (Restricted Top - Down Mapping), Davi de Castro Reis và cộng sự đề xuất mô hình trích chọn tin tức từ các công thông tin (portal) báo điện từ gồm các bước: (1) Dùng kỹ thuật phân cụm cấu trúc đẽ phân cụm các trang báo điện từ (độ đo khoáng cách giữa hai trang Web là chi phí chuyến đôi cây cấu trúc trang Web); (2) Sinh các mẫu trích chọn dưới dạng cây; (3) Đối sánh dữ liệu (kiểm tra đánh giá mẫu trích chọn) cũng dựa theo thuật toán RTMD, trong đó định giá cho các thao tác thay đỉnh (Vertex Replacement), chèn đinh (Vertex Insertion) và loại bỏ đinh (Vertex Removal); (4) Áp dụng mẫu để trích chọn tin tức. I lình 2.13 Irình bày sơ đè quá trình trích chọn tự động tin qua 4 bước nói trên. Mô hình trẽn đã được thi hành thành công trong sán phẩm Viennews "Cúc kênh báo điện lư trên Ihiêt bị điện thoại di động thông minh" dạt giải ba cuộc thi Trí tuệ Việt Nam năm 2006. Trong [AM03], Arvind Arasu và Hector Garcia-Molina cũng khai thác các khía cạnh tạo trang Web đế tìm ra các mẫu cùa các trang sách đươc trưng bày tại các công ty bán sách trực tuyến. L. Arllota và cộng sự [ACM03], Bing Liu và cộng sụ [LGZ03], p. s. Hiremath. Siddu p. Algur |l IA09|. Junfeng Wang và cộng sự [WHW09] đè xuất các mô hình khai phá cấu trúc trang Web có kết hợp với nội dung trang Web. 67 Toittmj ftps Clustering Extractor Generation 0 3 b* •4, - ' V ♦ o Q ứ Of ne pvrtm s Z l ■ca« ầf> _ ne patterns Data Labeling H inh 2.13. Các bước chính của mô hình trích chọn tự động tin trên W eb [RGS04] Câu hỏi và bài tập 1. Phân biệt sự khác nhau giữa bài toán khai phá dữ liệu thông thường, bài toán khai phá dữ liệu Text và khai phá dữ liệu Web. 2. Nêu các phương pháp khai phá dữ liệu Text và Web cũng như những ứng dụng của chúng trong thực tế. 3. Phân tích và cho ví dụ về ứng dụng thực tế của các bài toán khai phá Web. 68 Chương 3 MỘT SÓ KIÉN THỨC TOÁN HỌC CHO KHAI PHÁ Dữ LIỆU WEB Trong Chương 1 chúng ta đã nghiên cứu và khẳng định ràng, lĩnh vực khai phá dữ liệu vừa có tính ứng dụng thực tiễn cao, vừa đòi hói nền táng toán học mạnh. Dê cập vê nền tảng lý thuyêt cân cho sự phát triên ngành khoa học máy tính trong giai đoạn bùng no Internet, John E. H opcroít nhấn mạnh các nội dung về đồ thị ngẫu nhiên (Random Graph), chuyến dịch pha (Phase Transitions), các thành phần khồng lồ (Gian Com ponents), phân tích phố (Spcctral Analysis), hiện tượng thế giới nhó (Sm all-W orld phenom ena), đồ thị tăng trướng (grow n graphs) [H op07|. Có thể thấy lý thuyết đồ thị và lý thuyết xác suất đirợc John E. H opcroít coi như nền tảng kiến thức vững chắc cho việc nghiên cứu và phát triên lĩnh vực khoa học máy tính. Trong khai phá dữ liệu Web. lý thuyết dô thị và lý thuyêt xác suất còn mang một ý nghĩa lớn hơn, đặc biệt là dối với việc phát triên các mô hình và giai pháp khai phá dữ liệu W eb. Hầu hết các mô hình và giải pháp khai phá Web là trực tiếp, hoặc gián tiếp có nền tảng dựa trên lý thuyết đồ thị và lý thuyết xấc suất [BFS03. Zhu08. Rad09]. Mô hình dựa trên đồ thị xuất hiện trong nhiêu tình huống thuộc lĩnh vực khai phá dữ liệu W eb. Dơn gián và dễ nhận biết nhất chính là đồ thị Web với các dinh là các trang W eb và các cung là các siêu liên kết giữa các trang Web với nhau. C ùng với sự phát triên không ngừng của Internet và Web, các mô hình m ạng phức họp liên quan (dicn hình như mạng xã hội, mạng e-mail. m ạng block....) xuất hiện ngày càng nhiều. Trong nhiều năm qua, D ragom ir R. Radev ghi nhận danh mục các công trình khoa học được công bố liên quan tới mỏ hình dô thị trong khai phá Web trong các phiên bản "Bibliography W ebgraph Papers". Kct quá của tác giá cho thấy, số lượng các công trình nghiên cứu vê khai phá Web dược ghi nhận lần lượt là 496 (tháng 5/2005), 1212 (tháng 5/2007), 1361 (tháng 5/2008), 1457 (tháng 1/2009) và 1471 (tháng 8/2009). Nội dung cập nhật trong các phiên ban thống kê gần đây chu yếu là bô sung các công trình khoa học mới. Chúng tôi cho răng, tập hợp nội dung các văn bản thuộc các danh mục nói trên :ĩing chứa dựng các thông tin tiềm ấn, có giá trị về lĩnh vực nghiên cứu 69 Tương tự, trong "Semi-Supervised Learning Literature Survey". Xiaojin Zhu [Zhu081 khao sát và tập hợp danh mục các công trình nghiên cứu vê học bán giám sát. Các mô hình khai phá Web da dạng và phorm phu dược xây dựng dựa trên lý thuyết xác suất (diên hình là các mô hình dựa trên xác suất Bayes như mô hình Markov ấn, mô hình Entropy cực đại. mô hinh trường ngẫu nhiên có điêu kiện,...) cũng là một nội dung cơ ban tronu các danh mục. Khác với công việc mà Dragomir R. Radev tiến hành trong [Rad09] là chi lên danh mục các công trình liên quan. Xiaojin Zhu còn giới thiệu một số nội dung cơ bàn và đặc trưng về tiếp cận học bán eiám sát. Nội dung các phiên bản danh mục của Xiaojin Zhu cũng tiềm ân tri thức liên quan về học giám sát có thê khai phá được. Cuốn sách "Modeling the Internet and the Web: Probabilistic Methods and Algorithm s" của Pierre Baldi và cộng sự [BFS03] tone hợp nội dung các công trình nghiên cứu vê khai phá Web với cách tiếp cận các mô hinh và thuật toán dựa trên nên tàng của lý thuyêt xác suất. Các nội dung nền tàng toán học của khai phá Web, mà điền hình là lý thuyết đồ thị và lý thuyết xác suất đóng vai trò chu chốt cúa cuốn sách. Các kháo sát trên đây cho thây cá ba lĩnh vực nehiên cứu hợp thành Khai phá Web là Khai phá dữ liệu. Xừ lý ngôn ngữ tự nhiên và World Wide Web đều được mô hình hoá và sư dụng các giải pháp từ lý thuyết dô thị và lý thuyêt xác suất. Đây là hai nên tảng toán học chú yếu đê phát triên các mô hinh và là công cụ hiệu quá trong khai phá Web. Nguyên nhân làm cho hai nền tảng lý thuyết này chiếm vai trò quan trọng như vậy trorm khai phá dừ liệu Web xuất phát từ ban chất tự nhiên và xã hội của hệ thốnu Web. Mục này giới thiệu một sô kiên thức cơ bản nhất của hai lý thuvết nói trên liên quan tới khai phá dữ liệu Web. 3.1. Mô hình đồ thị 3.1.1. M ột số kiến thức cơ bản Lý thuyêt đô thị được ứng dụng rộng rãi trong khai phá W eb. tư việc áp dụng tronii mô hình hoá các dối tượng trong miên ứne dụng tới việc cai tiến các giai pháp khai phá Web. Phần này cung cấp một số nội duna cơ ban về lý thuyết đồ thị. Địnli Iigliĩa 3.1: Dồ thị toán học là một cặp G = < v . E>. trona đó V là tập các đinh (còn gọi là nút), còn E là tập các cung (còn gọi là cạnh). Một cách hình thức, trong đồ thị G = < v . E>: 70 - Tập V = {v} được gọi là tập đỉnh; - Tập E ç= V X V = {e = (u, v): u, V G V} được gọi là tập cung. Đối với cung e = (u, v) thì đỉnh u và đỉnh V được gọi là kê với cung e; hay cũng vậy, cung e là kề với đỉnh u và đỉnh V. Neu tập đình V là hữu hạn thì đồ thị được gọi là đồ thị hữu hạn; nếu mọi cặp (u, v) khồng có thứ tự thì gọi G là đo thị vô hướng; trong trường hợp ngược lại, gọi G là đồ thị có hướng. Cung (u, v) được gọi là đi ra từ u và đi vào tới V. Trong khai phá dữ liệu Web, chỉ có các đồ thị hữu hạn được quan tâm và chúng bao gồm cả hai loại có hướng và vô hướng. A ít Ç n F . F c; l ĩ 1 . 1 K I, M N í) i) I 0 0 0 1 0 0 1 0 1 0 0 0 1 0 íì 1 0 0 ữ 0 1 0 11 0 1 1 1 1 (J ] 0 LI 0 (I u 0 l ỉ) 1 1 0 I 0 ơ 0 0 0 0 0 1 0 0 0 1 0 0 D o (J (I L> 0 0 I 1 0 I 0 l 0 0 l 0 I 1 0 ơ 1 0 3 0 0 0 0 0 0 0 0 0 ũ 0 0 ị) I tl 0 ơ 0 0 0 1 1 0 11 0 1 0 0 1 I 0 0 ü l \ị o o Í] 0 I 0 1 0 0 0 0 1 [ ị 0 II 0 (I 0 0 0 1 0 1 0 0 0 0 0 0 0 1 0 b) ] [> u u l ỉ) H U I Cl D 0 ơ t 0 I [) 1 1 0 1 0 0 0 0 0 0 0 Q Hình 3.1. Biểu diễn hình học và ma trận kề của đồ thị Có một số phương pháp biêu diễn đô thị, trong đó phương pháp hình học là một phương pháp biêu diễn điên hình nhât. Trong biêu diễn hình học, mỗi đinh của đồ thị được biểu diễn bang một diem hình học và mỗi cung (u, v) được biểu diễn bằng đoạn nối từ đính u tới đinh V. Nếu đồ thị có hướng thì đoạn nối từ u tới V có chiều đi vào v; ngược lại, khi đồ thị không có hướng, nghĩa là cặp (u, v) cũng là cặp (v, u), thì doạn nôi (u, v) không có chiêu mũi tên. Hình 3.1 cho một ví dụ một đô thị vô hướng có 14 đinh {A, B, c , D, E, F, G, H, I, J, K, L, M, N} với tập họp các cung được biếu diễn hình học như Hình 3 .la. Biếu diễn hình học cho một cách nhìn trực quan về đồ thị, song không thế xử !ý tính toán được. Biêu diễn ma trận kề là một biếu diễn điển hình cua dồ thị để có thề xử lý được trong máy tính. Ma trận kề của đồ thị G có n đinh là một ma trận vuông có n chieu AG(n X n), trong đó các đinh được tương ứng từ trái qua phai (theo chiêu ngang) và từ trên xuống dưới (theo chiều dọc) với cùng một thứ tự. Nếu có cung đi từ u tới V thì phần tử A c ; ( u . V ) = 1; trong trường họp còn lại, A(j(u, v) = 0. Biểu diễn ma trận kề 71 của đồ thị ví dụ G đã cho được trình bày trong Hình 3.1 b. Chú ý ràng, ma trận kề của đồ thị vô hướng luôn là một ma trận đối xứng. Độ của m ột đinh là số cung kề với nó. Trong đồ thi có hướng, với mỗi đỉnh thì số lượng cung đi tới đinh được gọi là độ vào của đinh, còn số lượng cung đi ra từ đỉnh được gọi là độ ra của đỉnh. Đường đi là dãy các đinh, trong đó với mọi đinh (trừ đinh cuối cùng) đều tồn tại cung đi ra từ nó và đi tới đinh kế tiếp trong dãy. Trong đồ thị ờ Hình 3.1, dãy A G D CG D là đường đi với các cung lần lượt là (A, G), (G. D), (D, C), (C, G), (G, D), trong đó A là đinh đầu, còn D là đinh cuối. N ếu mọi đinh (ngoại trừ đinh đầu) của m ột đường đi mà không được gặp quá m ột lần trên đường đi thì gọi đường đi đó là đường đi đơn. Trong đồ thị ờ Hình 3.1, dãy AGDC là đường đi đơn với các cung lần lượt là (A, G), (G, D) và (D, C). M ột chu trình đơn là đường đi đơn với đỉnh đầu trùng với đinh cuối. Độ dài của m ột đường đi là số lượng cung xuất hiện trên đường đi đó. Giữa hai đỉnh u và V, đường đi có độ dài ngan nhất có đinh đầu là u và đinh cuối là V thì gọi là đường đi ngan nhất từ u tới V. K hoảng cách lý thuyết đồ thị giữa hai đinh là độ dài đường đi ngắn nhất giữa chúng. Đ ường đi ngắn nhất từ đỉnh u tới đinh V không là duy nhất, nhưng khoáng cách lý thuyết đồ th ị từ u tớ i V là d u y n h ấ t. M ột đồ thị được gọi là liên thông nếu với hai đinh u và V bất kỳ. luôn tồn tại đường đi đơn từ u tới V . Độ dài lớn nhất của tập các đường di đơn trong đồ thị là n - 1, trong đó n là số lượng đinh của đồ thị. Một đình V được gọi là đạt được từ một đinh u nếu tồn tại đường đi đơn đi từ u tới V. Đồ thị con của đồ thị G = (V, E) là đồ thị G' = (V , E'), trone đó tập V' là tập con các đinh trong V. còn E' là tập tất cả các cung thuộc E nối các đinh thuộc V'. Gọi đồ thị con G' là thành ph ầ n liên thông cùa G nếu G' là đô thị con liên thông cực dại theo nghĩa không tồn tại m ột đồ thị con liên thông của G m à chứa thực sự G'. Điêm cắt của m ột đồ thị là đỉnh V G V m à nếu bỏ đỉnh V đó đi cùng với mọi cung kê đinh V thì số lượng thành phần liên thông của đồ thị được tăng lên thực sự. Câu của đồ thị là m ột cung trong đồ thị m à bo cung đó đi thì so lượng các thành phần liên thông cúa đồ thị được tăng thực sự. Trong thực tế. nhiều bài toán quan Irọng trong khai phá W eb liên quan tới việc bài toán cùa đồ thị. Chẳng hạn. trong các hệ thông tìm kiếm trang W eb (Chương 6), bài toán tính hạng hay "độ quan trọng" cùa m ột trarm W eb dược xem xét trong đồ thị W eb có hướng. Trong đô thị W eb có hướnu. mỗi dính là một trang W eb, nếu như tồn tại liên kêt ngoài từ trang W eb u tới trang W eb V thì có m ột cung đi từ đinh u tới đinh V. Thuật toán tính hạng 72 trang nguyên thuý [PBM98Ị dưa về bài toán tìm một vector riêng của ma trận biêu diễn dồ thị Web. Trong trường hợp cần xem xét đồ thị Web có trọng số, thì các giá trị độ ra và độ vào của đinh được sứ dụng. 3.1.2. Đ ồ thị ngẫu nhiên Trong không ít nghiên cứu, đồ thị Web được xem xét như một đồ thị ngẫu nhiên. Tính ngầu nhiên trong đồ thị ngẫu nhiên cho phép mô hình hoá được biến dộng ngẫu nhiên cúa cả hệ thông Web. Đồ thị ngẫu nhiên được Paul Erdos và A llréd Rényi đề xuất vào năm 1959 [ER61]. Sự tiến hoá năm pha cua dồ thị ngẫu nhiên theo tỷ lệ giữa số lượng cung trên số lượng đinh có thê được áp dụng vào việc mô hình hoá sự biên động cùa đô thị Web. Phân này giới thiệu sơ bộ về đồ thị ngẫu nhiên như đã được đề cập trong các nghicn cứu về mô hình Web. Một sổ nội dung ơ đây có liên quan tới lý thuyết xác suất sẽ được giái thích trong mục 3.2. Cho trước hai số nguyên dương n và N, trong đó n là số lượng đỉnh và N là số lượng cung cúa các dồ thị ngẫu nhiên sẽ được xem xét. Dặt En, N = {Gn. N = : V = { V | , V , . . . , v „ > ; En, N £ V X V mà l-n . N| N}, có nghĩa là, En N là tập các đồ thị Gn. N có cùng tập đính V với n đinh v à các tập cung khác nhau En N vớ i N cung. Các đ ô thị G n. N phân từ của En. N là vô hướng, không có cung bội (Định nghĩa 3.1 đã ngâm định đô thị không có cung bội), không bị giăng. Với các ràng buộc nói trên, tông sô rn' fínìì cung nối có thế có giữa các đỉnh trong V là ^ 2 , và có uJ ^ N ) cách chọn các bộ N cung khác nhau trong tập | Vcung có thể. Như vậy, 1“ ,, N = fínìì ,2 , \ / l N J và nói chung thì đây là m ột số rất lớn. Địnli nghĩa 3.2(1 (Dồ thị ngẫu nhiên [KR61]): Đồ thị ngẫu nhiên G n N dược xác định như một phần tử cúa H„, N được chọn một cách ngẫu nhiên, trong dó các phần lư trong N là dồng khả năng dược chọn với xác suất l N Dịnh nghĩa 3.2b (Dỏ thị ngẫu nhiên theo quá trình ngẫu nhiên [ER61 Dồ thị ngẫu nhiên là một quá trinh thông kê ngâu nhiên với: 73 - Khi t = 1 : chọn cung ei từ n dinh của V; - Khi t = 2: chọn cung e2 từ với ei); 1 i i ị - I cung đông khà năng có thẻ có kêt nôi v 2 y- 1 cung đồng khả năng còn lại (khác - Khi t = k + 1 : chọn cung ek+1 từ v2y (khác với ei, e2,... £k); - k cung đồng khá năng còn lại - Ký hiệu Gn N là đồ thị chứa các đỉnh thuộc V và các cung ei, e2,..., ẽN Paul Erdos và Alfred Rényi chì ra rằng, hai định nghĩa nói trên là tương đương. Dịnh nghĩa thứ hai có ý nghĩa sừ dụng cao hơn khi mà sô hiệu cua các cung trong đồ thị ngẫu nhiên được tương ứng với thời điêm và điêu đó tạo thuận lợi cho việc nghiên cứu tỷ mí sự tiến hoá cùa đồ thị ngẫu nhiên, tức là làm sáng tó bước tiếp bước cấu trúc cùa En N khi N tăng lên. Điều đó giai thích được quá trinh tiến hoá của đồ thị ngẫu nhiên được sừ dụng như mô hinh về sự tiến hoá của rất nhiều hệ thống trong thế giới thực, thậm chí bao hàm cả sự phát triển các quan hệ xã hội. Ngày nay, quá trình tiên hoá cùa đồ thị ngẫu nhiên được sử dụng như một mô hinh biếu diễn tốt các đô thị. các mạng có trên hệ thống Internet. Nghiên cứu của Paul Erdos và Alfred Rényi [ER61] chứng tò rằng, khi sô đính n là một số nguyên dương khá lớn và cho số cung N tăng dân từ í _ \ tới . sự tiến hoá của G„ N trài qua 5 pha phân biệt rõ ràng, mỗi pha có V - / một sô tính chất đặc trưng riêng. Dó là các pha: (1) N(n) = 0(n); (2) N(n) a cn, với 0 < c < 1/2; (3) N(n) = cn. với c > 1/2; (4) N(n) = cn.loan. với c < 1/2; (5) N(n) » (n.logn)w(n). với w(n) —> 00 khi n —> 00. Tương ứng với mỗi một trong năm pha tiến hoá trên, đô thị ngẫu nhiên tuân theo một số phân bố xác suất như phân bố chuân. phân bố Poisson hoặc phân bố hàm mũ. 74 Dưới đây là một ví dụ minh hoạ sự biến động cùa đồ thị ngẫu nhiên theo sự biến động cùa xác suất p lựa chọn cung. Vi dụ 3.1. Minh hoạ hình ánh cua đồ thị ngẫu nhiên. Già thiêt ràng, có một số N rất lớn (N >> 1) cac nút đặt rái rác trên sàn nhà. Giả sử sử dụng một sợi dây buộc hai nút bất kỳ với xác suất p thành một cặp nút. Khi đó, tổng số cung là pN(N - l)/2 (Hình 3.2). Mục tiêu chính cúa lý thuyết đồ thị ngẫu nhiên là xác định tại liên kết nào xác suất p cùa một thuộc tính cụ thề cùa đồ thị sẽ xuất hiện gần như là nhiều nhất. p = o. 15 (c) p — 0.25 (d) Hình 3.2. Sự phát triển của một đồ thị ngẫu nhiên: (a) khời tạo 10 nút; (b) nối cặp nút với xác suất p = 0,1; (c) nổi các cặp nút với xác suất p = 0,15 và (d) nối cảc cặp nút với xác suất p = 0,25. Một diều khá đặc biệt dó là, các tính chất chính và quan trọng của các đồ thị ngẫu nhiên có thê xuất hiện khá đột ngột (tương tự như sự biến động khi chuyển pha). Chang hạn, nếu nâng một nút lên thì liệu sẽ có bao nhiêu nút bị nàng theo? Paul Erdos và Alfred Rényi chỉ ra rằng, nếu xác suất p lớn hơn một ngưỡng pc (pc ~ (lnN)/N) thì hâu hêt mọi nút trong đô thị ngẫu nhiên là được kết nối. điều này có nghĩa là nhặt được tất cá các nút bằng cách nâng một nút lên. Bậc trung binh cùa một đồ thị ngẫu nhiên là < k > = p(N -1 ) s pN . Gọi Lra„d là độ dài đường dẫn trung binh cùa mạng ngẫu nhiên. Bằng quan sát, có thề thấy sẽ có < k >L,“‘ các dinh trong đồ thị ngẫu nhiên có khoáng cách Lrand hoặc rất gần với đại lượng này. Do vậy, N ~< k >L'" ', điều này có nghĩa là l.rmll ~ In N / < k >. Sự gia tăng cùa hàm loga trong độ dài đường dẫn trung bình với độ lớn cùa dô thị là một ánh hướng phố biến của small-world (một thuộc tính trong mạng xã hội). Bởi vì InN tăng chậm hơn so với N. nó cho phép chiều dài trung binh phai khá nhò, thậm chí ngay cà trong một mạng khá lớn. Mặt khác, trong mạng ngẫu nhiên hoàn toàn (ví dụ mạng của những người bạn), xác suất mà hai nguời bất kỳ là bạn cùa nhau khônỉi lớn hơn xác suất hai người được chọn ngẫu nhiên trong mạng là bạn cùa nhau. Vi the. dộ phân cụm cua mô hình Paul Erdos và Alfred Rényi là 75 c = p =< k > / N « 1. Điều này có nghĩa là. mạne ngẫu nhiên trên diện rộng nói chun2 là không bị phân cụm. Trong thực tế. với N lớn. thuật toán cua Paul Erdos và Alfred Rényi sinh ra một mạng dồng nhất có các liên kết tuân theo phản phối Poisson (Hình 3.3). Phân bố hám mũ (Hình 3.4) cùne là mộl kha năng khi sô lượng cung đạt một giá trị rât lớn. H ình 3.3. Phân bố Poisson H ình 3.4. Phân bò hàm mũ Thôníi qua việc tông hợp kết qua níihicn cứu cua nhiỏu tác 2Ía. Picưe Baldi và cộne sự đã làm sáng tỏ về mối liên hệ giữa khái niệm đô thị ntiẫu nhiên với đồ thị Web. liên kết theo luật số lớn. mạng thế giới nho. các mô hình sinh đô thị Web và các mạna liên quan tren Internet [BFS03]. 3.1.3. Mạng xã hội Mạng x ã hội là m ạ n g c u a m ộ t n h ó m neười hoạt đ ộ n e và các mối quan hệ gan kết họ với nhau. Xhữnti người hoạt độníỉ tronti mạng có thê ià nhữnu cá nhân hoặc tập thê (các đơn vị như các phòng ban. các tỏ chức, các uia đình....). Nhữne neười này trao đôi tài nguvên với nhau và chính diêu đó đã aăn kêt họ lại với nhau trong một mạrm xã hội. Tài neu\ên ơ đâv bao eỏm dữ liệu, thôns tin. san phâm và các dịch vụ. hỗ trợ xã hội hoặc hỗ trợ tài chinh. Mỗi loại tài nguvên trao dôi được xem như một mỗi liên kết cua mạng xã hội và nhữníí cá nhân duv trì môi liên hệ này được Urcmíz ứna với việc duy trì một cuna. Sức bền cua cuna này được sẩp xếp từ veu đến mạnh phụ thuộc vào sô lượna và các kiêu cua rmuỏn tài nsuvên mà các thành viên trao đôi. mức độ thườne xuvên trao đôi và sự thân mật tron” quá trinh trao dõi uiữa họ. 76 Hình 3.5. Một mạng xã hội kiểu e-mail Nguồn: http://www.uvm.edu/~pdodds/teaching/courses/2008-01UVM-295/docs/2008- 01 UVM-295smallworldnetworks-slides-handout. pdf Các mối quan hệ trao đổi thường được tiến hành trong một số luợng dân số lựa chọn nhất định. Những nhà phân tích trong lĩnh vực mạng dựa vào các quan hệ giữa các thành viên của một cộng dồng, các hàng xóm, một nhóm hoặc một lớp đê hiêu cách thức các mạng xác định dân số hay các nhóm nhò bên trong một mạng lớn. Cách thức mà một người kết nối với một người khác thể hiện cấu trúc nền tảng của mạng, bao gồm những người thuôc và không thuộc vào một mạng và các kiểu trao đổi nào để xác định một mạng. Mạng này được duy trì bởi sự trao đôi của các tài nguyên đơn lẻ hay rất nhiều tài nguyên lớn tương ứng với các nút mạnh hay yếu. Ví dụ, các nhà phân tích có thê dò tìm sự trao đôi thông tin vê công việc của những người quen biết nhưng không mấy thân thiện, mối quan hệ trong dòng tộc hoặc mối quan hệ giữa những người công nhân. Các mạng xã hội được lần dấu bới những sự chuyên đôi này chi ra cách các nguôn tài nguyên di chuyến trong một mạng, cách mà các tác nhân xác định vị trí để tác động tới nguồn tài nguyên trao đôi và các kiểu của tài nguyên trao đồi rất quan trọng trong những môi trường khác nhau. 77 20 r H in h 3.6. T ầ n su ầt độ dài của ch uỗ i đẳy đủ [T M 69] Vấn đề nehiên cứu cấu trúc cùa mạng xã hội đã eây ra sự chú ý và quan tâm sâu sắc cua các nhà nghiên cứu trong nhiêu năm qua. Đâu tiên là thi nehiệm cua Stanley Milgram [TM69] được cuốn hút vào việc khám phá ra độ dài đường dẫn 2Íữa mọi neười trong một mạng xã hội trên diện rộng. Xuất phát điẽm từ câu hỏi "Xác suai biết lan nhau cua hai ngiỉời được chọn lừ mội quán thê lớn. chăng hạn như nước Mỹ, là bao nhiêu?". Kẻt qua thí nahiệm cua Stanley Mileram về phân bô tân suât độ dài chuỗi đâ\ đu (completed chain) được trinh bày trong Hình 3.6. trone đó trục hoanh chi độ dài cua chuồi đây đu (là số lượng các truy vân trực tiêp từ naưới khơi đâu tới neười đích). Độ dài trung binh của các chuỗi đâv đu là 5.2 và điêu đó có thê được giai thích là "cân dùne khoang 5.2 giao tiếp là một neười bát kv có thẻ aiao tiếp với một neười bất kỳ khác". Độ dài 5.2 là nhò. vì vậy từ kêt qua thí nshiệm dẫn đến một aia thuyết vê "thếgiới nho", tươna tự như cách nói quen thuộc cua neười Việt Nam là "qua đất tròn". Mặc dù thí nahiệm cua Stanlev Milgram với số lượng 279 người khời đầu (nhò) cùna với các gia thiêt đi kém trone thí nehiệm. sone eià thuvết về đườne kính nho cua các mạng xã hội vẫn còn có giá trị. Trên thực tế. người ta đã tim hiẻu được nhiêu m ạn2 xã hội thoa mãn eià thuvêt đườne kính nho của s. M ilsram. bao gôm các mạne cộne tác khoa học và đồ thị các cuộc eọi điện thoại.... Sự quan tâm nshiẻn cứu về mạne xã hội cua các nhà khoa học đã thu nhận được nhiêu phát minh khoa học mới về mạne xã hội trong nhiều thập ky qua. được mô hinh và phân tích băne các cône cụ của lý thuyết đô thị. Qua nhừne nehiên cứu nàv. người ta đã chứna minh được mạna xã hội thực 78