Luận văn Khai phá dữ liệu web bằng kỹ thuật phân cụm

Khai phá dữ liệu Web bằng kỹ thuật phân cụm Hoàng Văn Dũng i BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI Hoàng Văn Dũng KHAI PHÁ DỮ LIỆU WEB BẰNG KỸ THUẬT PHÂN CỤM Luận văn thạc sỹ khoa học Hà Nội, 2007 Khai phá dữ liệu Web bằng kỹ thuật phân cụm Hoàng Văn Dũng ii MỤC LỤC MỤC LỤC ...................................................................................................... i DANH SÁCH CÁC HÌNH ............................................................................ v DANH SÁCH CÁC BẢNG BIỂU ............................................................... vi CÁC CỤM TỪ VIẾT TẮT.......................................................................... vii LỜI MỞ ĐẦU ................................................................................................ 1 Chương 1. TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU .................................. 3 1.1. Khai phá dữ liệu và phát hiện tri thức ......................................................... 3 1.1.1. Khai phá dữ liệu .................................................................................... 3 1.1.2. Quá trình khám phá tri thức .................................................................. 4 1.1.3. Khai phá dữ liệu và các lĩnh vực liên quan .......................................... 5 1.1.4. Các kỹ thuật áp dụng trong khai phá dữ liệu ........................................ 5 1.1.5. Những chức năng chính của khai phá dữ liệu ...................................... 7 1.1.6. Ứng dụng của khai phá dữ liệu ............................................................. 9 1.2. Kỹ thuật phân cụm trong khai phá dữ liệu ................................................ 10 1.2.1. Tổng quan về kỹ thuật phân cụm ........................................................ 10 1.2.2. Ứng dụng của phân cụm dữ liệu ......................................................... 13 1.2.3. Các yêu cầu đối với kỹ thuật phân cụm dữ liệu ................................. 13 1.2.4. Các kiểu dữ liệu và độ đo tương tự ..................................................... 15 1.2.4.1. Phân loại kiểu dữ liệu dựa trên kích thước miền ......................... 15 1.2.4.2. Phân loại kiểu dữ liệu dựa trên hệ đo .......................................... 15 1.2.4.3. Khái niệm và phép đo độ tương tự, phi tương tự........................ 17 1.3. Khai phá Web ............................................................................................ 20 1.3.1. Lợi ích của khai phá Web ................................................................... 20 1.3.2. Khai phá Web ..................................................................................... 21 1.3.3. Các kiểu dữ liệu Web .......................................................................... 22 1.4. Xử lý dữ liệu văn bản ứng dụng trong khai phá dữ liệu Web .................. 23 1.4.1. Dữ liệu văn bản ................................................................................... 23 1.4.2. Một số vấn đề trong xử lý dữ liệu văn bản ......................................... 23 1.4.2.1. Loại bỏ từ dừng ............................................................................ 24 1.4.2.2. Định luật Zipf ............................................................................... 25 1.4.3. Các mô hình biểu diễn dữ liệu văn bản .............................................. 26 1.4.3.1. Mô hình Boolean .......................................................................... 26 Khai phá dữ liệu Web bằng kỹ thuật phân cụm Hoàng Văn Dũng iii 1.4.3.2. Mô hình tần số ............................................................................. 27 1.5. Tổng kết chương 1 ..................................................................................... 30 Chương 2. MỘT SỐ KỸ THUẬT PHÂN CỤM DỮ LIỆU ....................... 31 2.1. Phân cụm phân hoạch ................................................................................ 31 2.1.1. Thuật toán k-means ............................................................................. 32 2.1.2. Thuật toán PAM .................................................................................. 34 2.1.3. Thuật toán CLARA ............................................................................. 38 2.1.4. Thuật toán CLARANS........................................................................ 39 2.2. Phân cụm phân cấp .................................................................................... 41 2.2.1. Thuật toán BIRCH .............................................................................. 42 2.2.2. Thuật toán CURE ................................................................................ 45 2.3. Phân cụm dựa trên mật độ ......................................................................... 47 2.3.1 Thuật toán DBSCAN ........................................................................... 47 2.3.2. Thuật toán OPTICS ............................................................................ 51 2.3.3. Thuật toán DENCLUE ....................................................................... 52 2.4. Phân cụm dựa trên lưới.............................................................................. 54 2.4.1 Thuật toán STING ............................................................................... 55 2.4.2 Thuật toán CLIQUE............................................................................. 56 2.5. Phân cụm dữ liệu dựa trên mô hình........................................................... 57 2.5.1. Thuật toán EM .................................................................................... 58 2.5.2. Thuật toán COBWEB ......................................................................... 59 2.6. Phân cụm dữ liệu mờ ................................................................................. 59 2.7. Tổng kết chương 2 ..................................................................................... 60 Chương 3. KHAI PHÁ DỮ LIỆU WEB ..................................................... 62 3.1. Khai phá nội dung Web ............................................................................. 62 3.1.1. Khai phá kết quả tìm kiếm .................................................................. 63 3.1.2. Khai phá văn bản Web ........................................................................ 63 3.1.2.1. Lựa chọn dữ liệu .......................................................................... 64 3.1.2.2. Tiền xử lý dữ liệu ......................................................................... 64 3.1.2.3. Biểu điễn văn bản ......................................................................... 65 3.1.2.4. Trích rút các từ đặc trưng ............................................................. 65 3.1.2.5. Khai phá văn bản ......................................................................... 66 3.1.3. Đánh giá chất lượng mẫu ................................................................ 68 Khai phá dữ liệu Web bằng kỹ thuật phân cụm Hoàng Văn Dũng iv 3.2. Khai phá theo sử dụng Web ...................................................................... 69 3.2.1. Ứng dụng của khai phá theo sử dụng Web ......................................... 70 3.2.2. Các kỹ thuật được sử dụng trong khai phá theo sử dụng Web ........... 71 3.2.3. Những vấn đề trong khai khá theo sử dụng Web. .............................. 71 3.2.3.1. Chứng thực phiên người dùng ..................................................... 71 3.2.3.2. Đăng nhập Web và xác định phiên chuyển hướng người dùng ... 72 3.2.3.3. Các vấn đề đối với việc xử lý Web log ........................................ 72 3.2.3.4. Phương pháp chứng thực phiên làm việc và truy cập Web ......... 73 3.2.4. Quá trình khai phá theo sử dụng Web ................................................ 73 3.2.4.1. Tiền xử lý dữ liệu ......................................................................... 73 3.2.4.2. Khai phá dữ liệu ........................................................................... 73 3.2.4.3. Phân tích đánh giá ........................................................................ 75 3.2.5. Ví dụ khai phá theo sử dụng Web ...................................................... 75 3.3. Khai phá cấu trúc Web .............................................................................. 77 3.3.1. Tiêu chuẩn đánh giá độ tương tự ........................................................ 79 3.3.2. Khai phá và quản lý cộng đồng Web .................................................. 80 3.3.2.1. Thuật toán PageRank ................................................................... 81 3.3.2.2. Phương pháp phân cụm nhờ thuật toán HITS ............................. 82 3.4. Áp dụng thuật toán phân cụm dữ liệu trong tìm kiếm và PCDL Web ...... 85 3.4.1. Hướng tiếp cận bằng kỹ thuật phân cụm ............................................ 85 3.4.2. Quá trình tìm kiếm và phần cụm tài liệu ............................................ 87 3.4.2.1. Tìm kiếm dữ liệu trên Web .......................................................... 87 3.4.2.2. Tiền xử lý dữ liệu ......................................................................... 88 3.4.2.3. Xây dựng từ điển .......................................................................... 89 3.4.2.4. Tách từ, số hóa văn bản và biểu diễn tài liệu ............................... 90 3.4.2.5. Phân cụm tài liệu .......................................................................... 90 3.4.6. Kết quả thực nghiệm ........................................................................... 92 3.5. Tổng kết chương 3 ..................................................................................... 93 KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN ................................................... 94 PHỤ LỤC ................................................................................................... 96 TÀI LIỆU THAM KHẢO ......................................................................... 102 Khai phá dữ liệu Web bằng kỹ thuật phân cụm Hoàng Văn Dũng v DANH SÁCH CÁC HÌNH Hình 1.1. Quá trình khám phá tri thức ........................................................... 4 Hình 1.2. Các lĩnh vực liên quan đến khám phá tri thức trong CSDL .......... 6 Hình 1.3. Trực quan hóa kết quả KPDL trong Oracle ................................ 10 Hình 1.4. Mô phỏng sự PCDL ..................................................................... 11 Hình 1.5. Phân loại dữ liệu Web.................................................................. 22 Hình 1.6. Lược đồ thống kê tần số của từ theo Định luật Zipf ................... 26 Hình 1.7. Các độ đo tương tự thường dùng ................................................. 29 Hình 2.1. Thuật toán k-means ..................................................................... 32 Hình 2.2. Hình dạng cụm dữ liệu được khám phá bởi k-means ................. 33 Hình 2.3. Trường hợp Cjmp=d(Oj,Om,2) – d(Oj, Om) không âm .................... 35 Hình 2.4. Trường hợp Cjmp= (Oj,Op)- d(Oj, Om) có thể âm hoặc dương ..... 36 Hình 2.5. Trường hợp Cjmp bằng không ....................................................... 36 Hình 2.6. Trường hợp Cjmp= (Oj,Op)- d(Oj, Om,2) luôn âm .......................... 37 Hình 2.7. Thuật toán PAM .......................................................................... 37 Hình 2.8. Thuật toán CLARA ..................................................................... 38 Hình 2.9. Thuật toán CLARANS ................................................................ 40 Hình 2.10. Các chiến lược phân cụm phân cấp ........................................... 42 Hình 2.11. Cây CF được sử dụng bởi thuật toán BIRCH ........................... 43 Hình 2.12. Thuật toán BIRCH ..................................................................... 44 Hình 2.13. Ví dụ về kết quả phân cụm bằng thuật toán BIRCH ................. 44 Hình 2.14. Các cụm dữ liệu được khám phá bởi CURE ............................. 45 Hình 2.15. Thuật toán CURE ...................................................................... 46 Hình 2.16. Một số hình dạng khám phá bởi phân cụm dưa trên mật độ ..... 47 Hình 2.17. Lân cận của P với ngưỡng Eps .................................................. 48 Hình 2.18. Mật độ - đến được trực tiếp ....................................................... 49 Hình 2.19. Mật độ đến được ........................................................................ 49 Hình 2.20. Mật độ liên thông ....................................................................... 49 Hình 2.21. Cụm và nhiễu ............................................................................. 50 Hình 2.22. Thuật toán DBSCAN ................................................................. 51 Hình 2.23. Thứ tự phân cụm các đối tượng theo OPTICS .......................... 52 Hình 2.24. DENCLUE với hàm phân phối Gaussian .................................. 53 Khai phá dữ liệu Web bằng kỹ thuật phân cụm Hoàng Văn Dũng vi Hình 2.25. Mô hình cấu trúc dữ liệu lưới .................................................... 55 Hình 2.26. Thuật toán CLIQUE .................................................................. 56 Hình 2.27. Quá trình nhận dạng các ô của CLIQUE ................................... 57 Hình 3.1. Phân loại khai phá Web ............................................................... 62 Hình 3.2. Quá trình khai phá văn bản Web ................................................. 64 Hình 3.3. Thuật toán phân lớp K-Nearest Neighbor ................................... 67 Hình 3.4. Thuật toán phân cụm phân cấp .................................................... 67 Hình 3.5. Thuật toán phân cụm phân hoạch ................................................ 68 Hình 3.6. Kiến trúc tổng quát của khai phá theo sử dụng Web .................. 70 Hình 3.7. Minh họa nội dung logs file ......................................................... 72 Hình 3.8. Phân tích người dùng truy cập Web ............................................ 77 Hình 3.9. Đồ thi liên kết Web ...................................................................... 78 Hình 3.10. Quan hệ trực tiếp giữa 2 trang ................................................... 79 Hình 3.11. Độ tương tự đồng trích dẫn ....................................................... 79 Hình 3.12. Độ tương tự chỉ mục .................................................................. 79 Hình 3.13. Cộng đồng Web ......................................................................... 80 Hình 3.14. Kết quả của thuật toán PageRank .............................................. 81 Hình 3.15. Đồ thị phân đôi của Hub và Authority ...................................... 82 Hình 3.16. Sự kết hợp giữa Hub và Authority ............................................ 83 Hình 3.17. Đồ thị Hub-Authority ................................................................ 84 Hình 3.18. Giá trị trọng số các Hub và Authority ....................................... 84 Hình 3.19. Thuật toán đánh trọng số cụm và trang ..................................... 86 Hình 3.20. Các bước phân cụm kết quả tìm kiếm trên Web ....................... 87 Hình 3.21. Thuật toán k-means trong phân cụm nội dung tài liệu Web ..... 91 DANH SÁCH CÁC BẢNG BIỂU Bảng 1.1. Bảng tham số thuộc tính nhị phân ............................................... 18 Bảng 1.2. Thống kê các từ tần số xuất hiện cao .......................................... 24 Bảng 3.1. Thống kê số người dùng tại các thời gian khác nhau ................. 76 Bảng 3.2. Bảng đo thời gian thực hiện thuật toán phân cụm ...................... 92 Khai phá dữ liệu Web bằng kỹ thuật phân cụm Hoàng Văn Dũng vii CÁC CỤM TỪ VIẾT TẮT STT Viết tắt Cụm từ tiếng Anh Cụm từ tiếng Việt 1 CNTT Information Technology Công nghệ thông tin 2 CSDL Database Cơ sở dữ liệu 3 KDD Knowledge Discovery in Database Khám phá tri thức trong cơ sở dữ liệu 4 KPDL Data mining Khai phá dữ liệu 5 KPVB Text Mining Khai phá văn bản 6 PCDL Data Clustering Phân cụm dữ liệu Khai phá dữ liệu Web bằng kỹ thuật phân cụm Hoàng Văn Dũng 1 LỜI MỞ ĐẦU Trong những năm gần đây cùng với phát triển nhanh chóng của khoa học kỹ thuật là sự bùng nỗ về tri thức. Kho dữ liệu, nguồn tri thức của nhân loại cũng trở nên đồ sộ, vô tận làm cho vấn đề khai thác các nguồn tri thức đó ngày càng trở nên nóng bỏng và đặt ra thách thức lớn cho nền công nghệ thông tin thế giới. Cùng với những tiến bộ vượt bậc của công nghệ thông tin là sự phát triển mạnh mẽ của mạng thông tin toàn cầu, nguồn dữ liệu Web trở thành kho dữ liệu khổng lồ. Nhu cầu về tìm kiếm và xử lý thông tin, cùng với yêu cầu về khả năng kịp thời khai thác chúng để mạng lại những năng suất và chất lượng cho công tác quản lý, hoạt động kinh doanh,… đã trở nên cấp thiết trong xã hội hiện đại. Nhưng vấn đề tìm kiếm và sử dụng nguồn tri thức đó như thế nào để phục vụ cho công việc của mình lại là một vấn đề khó khăn đối với người sử dụng. Để đáp ứng phần nào yêu cầu này, người ta đã xây dựng các công cụ tìm kiếm và xử lý thông tin nhằm giúp cho người dùng tìm kiếm được các thông tin cần thiết cho mình, nhưng với sự rộng lớn, đồ sộ của nguồn dữ liệu trên Internet đã làm cho người sử dụng cảm thấy khó khăn trước những kết quả tìm được. Với các phương pháp khai thác cơ sở dữ liệu truyền thống chưa đáp ứng được các yêu cầu đó. Để giải quyết vấn đề này, một hướng đi mới đó là nghiên cứu và áp dụng kỹ thuật khai phá dữ liệu và khám phá tri thức trong môi trường Web. Do đó, việc nghiên cứu các mô hình dữ liệu mới và áp dụng các phương pháp khai phá dữ liệu trong khai phá tài nguyên Web là một xu thế tất yếu vừa có ý nghĩa khoa học vừa mang ý nghĩa thực tiễn cao. Vì vậy, tác giả chọn đề tài “Khai phá dữ liệu Web bằng kỹ thuật phân cụm” để làm luận văn tốt nghiệp cho mình. Bố cục luận văn gồm 3 chương: Khai phá dữ liệu Web bằng kỹ thuật phân cụm Hoàng Văn Dũng 2 Chương 1 trình bày một cách tổng quan các kiến thức cơ bản về khai phá dữ liệu và khám phá tri thức, khai phá dữ liệu trong môi trường Web; một số vấn đề về biểu diễn và xử lý dữ liệu văn bản áp dụng trong khai phá dữ liệu Web. Chương 2 giới thiệu một số kỹ thuật phân cụm dữ liệu phổ biến và thường được sử dụng trong lĩnh vực khai phá dữ liệu và khám phá tri thức. Chương 3 trình bày một số hướng nghiên cứu trong khai phá dữ liệu Web như khai phá tài liệu Web, khai phá theo sử dụng Web, khai phá cấu trúc Web và tiếp cận theo hướng sử dụng các kỹ thuật phân cụm dữ liệu để giải quyết bài toán khai phá dữ liệu Web. Trong phần này cũng trình bày một mô hình áp dụng kỹ thuật phân cụm dữ liệu trong tìm kiếm và phân cụm tài liệu Web. Phần kết luận của luận văn tổng kết lại những vấn đề đã nghiên cứu, đánh giá kết quả nghiên cứu, hướng phát triển của đề tài. Phần phụ lục trình bày một số đoạn mã lệnh xử lý trong chương trình và một số giao diện trong chương trình mô phỏng. Khai phá dữ liệu Web bằng kỹ thuật phân cụm Hoàng Văn Dũng 3 Chương 1. TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU 1.1. Khai phá dữ liệu và phát hiện tri thức 1.1.1. Khai phá dữ liệu Cuối thập kỷ 80 của thế kỷ 20, sự phát triển rộng khắp của các CSDL đã tạo ra sự bùng nổ thông tin trên toàn cầu, vào thời gian này người ta bắt đầu đề cập đến khái niệm khủng hoảng trong việc phân tích dữ liệu tác nghiệp để cung cấp thông tin với yêu cầu chất lượng ngày càng cao cho người làm quyết định trong các tổ chức chính phủ, tài chính, thương mại, khoa học,… Đúng như John Naisbett đã cảnh báo “Chúng ta đang chìm ngập trong dữ liệu mà vẫn đói tri thức”. Lượng dữ liệu khổng lồ này thực sự là một nguồn tài nguyên có nhiều giá trị bởi thông tin là yếu tố then chốt phục vụ cho mọi hoạt động quản lý, kinh doanh, phát triển sản xuất và dịch vụ, … nó giúp người điều hành và quản lý có những hiểu biết về môi trường và tiến trình hoạt động của tổ chức mình trước khi ra quyết định để tác động đến quá trình hoạt động nhằm đạt được các mục tiêu một cách hiệu quả và bền vững. KPDL là một lĩnh vực mới được nghiên cứu, nhằm tự động khai thác thông tin, tri thức mới hữu ích, tiềm ẩn từ những CSDL lớn cho các đơn vị, tổ chức, doanh nghiệp,…. từ đó làm thúc đẩy khả năng sản xuất, kinh doanh, cạnh tranh cho các đơn vị, tổ chức này. Các kết quả nghiên cứu khoa học cùng những ứng dụng thành công trong KDD cho thấy KPDL là một lĩnh vực phát triển bền vững, mang lại nhiều lợi ích và có nhiều triển vọng, đồng thời có ưu thế hơn hẵn so với các công cụ tìm kiếm phân tích dữ liệu truyền thống. Hiện nay, KPDL đã ứng dụng ngày càng rộng rãi trong các lĩnh vực như thương mại, tài chính, y học, viễn thông, tin – sinh,…. Các kỹ thuật chính được áp dụng trong lĩnh vực KPDL phần lớn được thừa kế từ lĩnh vực CSDL, học máy, trí tuệ nhân tạo, lý thuyết thông tin, xác suất thống kê và tính toán hiệu năng cao,... Khai phá dữ liệu Web bằng kỹ thuật phân cụm Hoàng Văn Dũng 4 Như vậy ta có thể khái quát hóa khái niệm KPDL là một quá trình tìm kiếm, phát hiện các tri thức mới, hữu ích, tiềm ẩn trong CSDL lớn. KDD là mục tiêu chính của KPDL, do vậy hai khái niệm KPDL và KDD được các nhà khoa học trên hai lĩnh vực xem là tương đương với nhau. Thế nhưng nếu phân chia một cách chi tiết thì KPDL là một bước chính trong quá trình KDD. 1.1.2. Quá trình khám phá tri thức Quá trình khá phá tri thức có thể chia thành 5 bước như sau [10]: Hình 1.1. Quá trình khám phá tri thức Quá trình KPDL có thể phân thành các giai đoạn sau [10]: Trích chọn dữ liệu: Đây là bước trích chọn những tập dữ liệu cần được khai phá từ các tập dữ liệu lớn ban đầu theo một số tiêu chí nhất định. Tiền xử lý dữ liệu: Đây là bước làm sạch dữ liệu (xử lý những dữ liệu không đầy đủ, nhiễu, không nhất quán,...), rút gọn dữ liệu (sử dụng hàm nhóm và tính tổng, các phương pháp nén dữ liệu, sử dụng histograms, lấy mẫu,...), rời rạc hóa dữ liệu (rời rạc hóa dựa vào histograms, dựa vào entropy, dựa vào phân khoảng,...). Sau bước này, dữ liệu sẽ nhất quán, đầy đủ, được rút gọn và được rời rạc hóa. Biến đổi dữ liệu: Đây là bước chuẩn hóa và làm mịn dữ liệu để đưa dữ liệu về dạng thuận lợi nhất nhằm phục vụ quá trình khai phá ở bước sau. Các mẫu Tri thức Dữ liệu tiền xử lý Dữ liệu biến đổi Dữ liệu thô Dữ liệu lựa chọn Trích chọn Tiền xử lý Biến đổi Khai phá Đánh giá, biểu diễn Khai phá dữ liệu Web bằng kỹ thuật phân cụm Hoàng Văn Dũng 5 Khai phá dữ liệu: Đây là bước áp dụng những kỹ thuật phân tích (như các kỹ thuật của học máy) nhằm để khai thác dữ liệu, trích chọn được những mẫu thông tin, những mối liên hệ đặc biệt trong dữ liệu. Đây được xem là bước quan trọng và tốn nhiều thời gian nhất của toàn quá trình KDD. Đánh giá và biểu diễn tri thức: Những mẫu thông tin và mối liên hệ trong dữ liệu đã được khám phá ở bước trên được biến đổi và biểu diễn ở một dạng gần gũi với người sử dụng như đồ thị, cây, bảng biểu, luật,... Đồng thời bước này cũng đánh giá những tri thức khám phá được theo những tiêu chí nhất định. 1.1.3. Khai phá dữ liệu và các lĩnh vực liên quan KPDL là một lĩnh vực liên quan tới thống kê, học máy, CSDL, thuật toán, tính toán song song, thu nhận tri thức từ hệ chuyên gia và dữ liệu trừu tượng. Đặc trưng của hệ thống khám phá tri thức là nhờ vào các phương pháp, thuật toán và kỹ thuật từ những lĩnh vực khác nhau để KPDL. Lĩnh vực học máy và nhận dạng mẫu trong KDD nghiên cứu các lý thuyết và thuật toán của hệ thống để trích ra các mẫu và mô hình từ dữ liệu lớn. KDD tập trung vào việc mở rộng các lý thuyết và thuật toán cho các vấn đề tìm ra các mẫu đặc biệt (hữu ích hoặc có thể rút ra tri thức quan trọng) trong CSDL lớn. Ngoài ra, KDD có nhiều điểm chung với thống kê, đặc biệt là phân tích dữ liệu thăm dò (Exploratory Data Analysis - EDA). Hệ thống KDD thường gắn những thủ tục thống kê cho mô hình dữ liệu và tiến trình nhiễu trong khám phá tri thức nói chung. Một lĩnh vực liên quan khác là phân tích kho dữ liệu. Phương pháp phổ biến để phân tích kho dữ liệu là OLAP (On-Line Analytical Processing). Các công cụ OLAP tập trung vào phân tích dữ liệu đa chiều. 1.1.4. Các kỹ thuật áp dụng trong khai phá dữ liệu KDD là một lĩnh vực liên ngành, bao gồm: Tổ chức dữ liệu, học máy, trí tuệ nhân tạo và các khoa học khác. Sự kết hợp này có thể được diễn tả như sau: Khai phá dữ liệu Web bằng kỹ thuật phân cụm Hoàng Văn Dũng 6 Hình 1.2. Các lĩnh vực liên quan đến khám phá tri thức trong CSDL Đứng trên quan điểm của học máy, thì các kỹ thuật trong KPDL, bao gồm: Học có giám sát: Là quá trình gán nhãn lớp cho các phần tử trong CSDL dựa trên một tập các ví dụ huấn luyện và các thông tin về nhãn lớp đã biết. Học không có giám sát: Là quá trình phân chia một tập dữ liệu thành các lớp hay cụm dữ liệu tương tự nhau mà chưa biết trước các thông tin về lớp hay tập các ví dụ huấn luyện. Học nửa giám sát: Là quá trình phân chia một tập dữ liệu thành các lớp dựa trên một tập nhỏ các ví dụ huấn luyện và các thông tin về một số nhãn lớp đã biết trước. + Nếu căn cứ vào lớp các bài toán cần giải quyết, thì KPDL bao gồm các kỹ thuật áp dụng sau [10]: Phân lớp và dự báo: Xếp một đối tượng vào một trong những lớp đã biết trước. Ví dụ như phân lớp các dữ liệu bệnh nhân trong hồ sơ bệnh án. Hướng tiếp cận này thường sử dụng một số kỹ thuật của học máy như cây quyết định, mạng nơron nhân tạo,... Phân lớp và dự báo còn được gọi là học có giám sát. Luật kết hợp: Là dạng luật biểu diễn tri thức ở dạng khá đơn giản. Ví dụ: “60 % nữ giới vào siêu thị nếu mua phấn thì có tới 80% trong số họ sẽ mua thêm son”. Luật kết hợp được ứng dụng nhiều trong lĩnh vực kinh doanh, y học, tin- sinh, tài chính và thị trường chứng khoán,... Các lĩnh vực khoa học khác Tổ chức dữ liệu Học máy và trí tuệ nhân tạo Khai phá dữ liệu Web bằng kỹ thuật phân cụm Hoàng Văn Dũng 7 Phân tích chuỗi theo thời gian: Tương tự như khai phá luật kết hợp nhưng có thêm tính thứ tự và tính thời gian. Hướng tiếp cận này được ứng dụng nhiều trong lĩnh vực tài chính và thị trường chứng khoán vì nó có tính dự báo cao. Phân cụm: Xếp các đối tượng theo từng cụm dữ liệu tự nhiên. Phân cụm còn được gọi là học không có giám sát. Mô tả và tóm tắt khái niệm: Thiên về mô tả, tổng hợp và tóm tắt khái niệm, ví dụ như tóm tắt văn bản. Do KPDL được ứng dụng rộng rãi nên nó có thể làm việc với rất nhiều kiểu dữ liệu khác nhau. Sau đây là một số dạng dữ liệu điển hình: Dữ liệu quan hệ, dữ liệu đa chiều, dữ liệu dạng giao dịch, dữ liệu quan hệ - hướng đối tượng, dữ liệu không gian và thời gian, dữ liệu chuỗi thời gian, dữ liệu đa phương tiện, dữ liệu văn bản và Web,… 1.1.5. Những chức năng chính của khai phá dữ liệu Hai mục tiêu chính của KPDL là mô tả và dự báo. Dự báo là dùng một số biến hoặc trường trong CSDL để dự đoán ra các giá trị chưa biết hoặc sẽ có của các biến quan trọng khác. Việc mô tả tập trung vào tìm kiếm các mẫu mà con người có thể hiểu được để mô tả dữ liệu. Trong lĩnh vực KDD, mô tả được quan tâm nhiều hơn dự báo, nó ngược với các ứng dụng học máy và nhận dạng mẫu mà trong đó việc dự báo thường là mục tiêu chính. Trên cơ sở mục tiêu chính của KPDL, các chức năng chính của KDD gồm: Mô tả lớp và khái niệm: Dữ liệu có thể được kết hợp trong lớp và khái niệm. Thí dụ, trong kho dữ liệu bán hàng thiết bị tin học, các lớp mặt hàng bao gồm máy tính, máy in,…và khái niệm khách hàng bao gồm khách hàng mua sỉ và khách mua lẻ. Việc mô tả lớp và khái niệm là rất hữu ích cho giai đoạn tổng hợp, tóm lược và chính xác hoá. Mô tả lớp và khái niệm được bắt nguồn từ đặc trưng hoá dữ liệu và phân biệt dữ liệu. Đặc trưng hoá dữ liệu là quá trình tổng hợp những đặc tính hoặc các thành phần chung của một lớp dữ liệu mục tiêu. Phân biệt dữ liệu là so sánh lớp dữ liệu mục tiêu với những lớp dữ liệu đối chiếu Khai phá dữ liệu Web bằng kỹ thuật phân cụm Hoàng Văn Dũng 8 khác. Lớp dữ liệu mục tiêu và các lớp đối chiếu là do người dùng chỉ ra và tương ứng với các đối tượng dữ liệu nhận được nhờ truy vấn. Phân tích sự kết hợp: Phân tích sự kết hợp là khám phá các luật kết hợp thể hiện mối quan hệ giữa các thuộc tính giá trị mà ta nhận biết được nhờ tần suất xuất hiện cùng nhau của chúng. Các luật kết hợp có dạng YX  , tức là  nAA ....1 mBB  .....1 , trong đó Ai (i=1,..., n) và Bj (j=1,...,m) là các cặp thuộc tính giá trị. Luật kết hợp dạng YX  có thể được hiểu là “dữ liệu thoã mãn các điều kiện của X thì cũng sẽ thoả các điều kiện của Y”. Phân lớp và dự báo: Phân lớp là quá trình tìm kiếm một tập các mô hình hoặc chức năng mà nó mô tả và phân biệt nó với các lớp hoặc khái niệm khác. Các mô hình này nhằm mục đích dự báo về lớp của một số đối tượng. Việc xây dựng mô hình dựa trên sự phân tích một tập các dữ liệu được huấn luyện có nhiều dạng thể hiện mô hình như luật phân lớp (IF-THEN), cây quyết định, công thức toán học hay mạng nơron,... Sự phân lớp được sử dụng để dự đoán nhãn lớp của các đối tượng trong dữ liệu. Tuy nhiên trong nhiều ứng dụng, người ta mong muốn dự đoán những giá trị khuyết thiếu nào đó. Thông thường đó là trường hợp dự đoán các giá trị của dữ liệu kiểu số. Trước khi phân lớp và dự báo, có thể cần thực hiện phân tích thích hợp để xác định và loại bỏ các thuộc tính không tham gia vào quá trình phân lớp và dự báo. Phân cụm: Không giống như phân lớp và dự báo, phân cụm phân tích các đối tượng dữ liệu khi chưa biết nhãn của lớp. Nhìn chung, nhãn lớp không tồn tại trong suốt quá trình huấn luyện dữ liệu, nó phân cụm có thể được sử dụng để đưa ra nhãn của lớp. Sự phân cụm thực hiện nhóm các đối tượng dữ liệu theo nguyên tắc: Các đối tượng trong cùng một nhóm thì giống nhau hơn các đối tượng khác nhóm. Mỗi cụm được tạo thành có thể được xem như một lớp các đối tượng mà các luật được lấy ra từ đó. Dạng của cụm được hình thành theo một cấu trúc phân cấp của các lớp mà mỗi lớp là một nhóm các sự kiện tương tự nhau. Phân tích các đối tượng ngoài cuộc: Một CSDL có thể chứa các đối tượng không tuân theo mô hình dữ liệu. Các đối tượng như vậy gọi là đối tượng Khai phá dữ liệu Web bằng kỹ thuật phân cụm Hoàng Văn Dũng 9 ngoài cuộc. Hầu hết các phương pháp KPDL đều coi các đối tượng ngoài cuộc là nhiễu và loại bỏ chúng. Tuy nhiên trong một số ứng dụng, chẳng hạn như phát hiện nhiễu, thì sự kiện hiếm khi xảy ra lại được chú ý hơn những gì thường xuyên gặp phải. Sự phân tích dữ liệu ngoài cuộc được coi như là sự khai phá các đối tượng ngoài cuộc. Một số phương pháp được sử dụng để phát hiện đối tượng ngoài cuộc: sử dụng các test mang tính thống kê trên cơ sở một phân phối dữ liệu hay một mô hình xác suất cho dữ liệu, dùng các độ đo khoảng cách mà theo đó các đối tượng có một khoảng cách đáng kể đến cụm bất kì khác được coi là đối tượng ngoài cuộc, dùng các phương pháp dựa trên độ lệch để kiểm tra sự khác nhau trong những đặc trưng chính của các nhóm đối tượng. Phân tích sự tiến hoá: Phân tích sự tiến hoá thực hiện việc mô tả và mô hình hoá các qui luật hay khuynh hướng của những đối tượng mà hành vi của chúng thay đổi theo thời gian. Phân tích sự tiến hoá có thể bao gồm cả đặc trưng hoá, phân biệt, tìm luật kết hợp, phân lớp hay PCDL liên quan đến thời gian, phân tích dữ liệu theo chuỗi thời gian, so sánh mẫu theo chu kỳ và phân tích dữ liệu dựa trên độ tương tự. 1.1.6. Ứng dụng của khai phá dữ liệu KPDL là một lĩnh vực được quan tâm và ứng dụng rộng rãi. Một số ứng dụng điển hình trong KPDL có thể liệt kê như sau: Phân tích dữ liệu và hỗ trợ ra quyết định, điều trị y học, KPVB, khai phá Web, tin-sinh, tài chính và thị trường chứng khoán, bảo hiểm,... Thương mại: Như phân tích dữ liệu bán hàng và thị trường, phân tích đầu tư, phát hiện gian lận, chứng thực hóa khách hàng, dự báo xu hướng phát triển,... Thông tin sản xuất: Điều khiển, lập kế hoạch, hệ thống quản lý, phân tích thử nghiệm,... Thông tin khoa học: Dự báo thời tiết, bảo lụt, động đất, tin sinh học,... Hiện nay các hệ quản trị CSDL đã tích hợp những modul để KPDL như SQL Server, Oracle, đến năm 2007 Microsoft đã cung cấp sẵn công cụ KPDL tích hợp trong cả MS-Word, MS-Excel,.. Khai phá dữ liệu Web bằng kỹ thuật phân cụm Hoàng Văn Dũng 10 Hình 1.3. Trực quan hóa kết quả KPDL trong Oracle 1.2. Kỹ thuật phân cụm trong khai phá dữ liệu 1.2.1. Tổng quan về kỹ thuật phân cụm Mục đích chính của PCDL nhằm khám phá cấu trúc của mẫu dữ liệu để thành lập các nhóm dữ liệu từ tập dữ liệu lớn, theo đó nó cho phép người ta đi sâu vào phân tích và nghiên cứu cho từng cụm dữ liệu này nhằm khám phá và tìm kiếm các thông tin tiềm ẩn, hữu ích phục vụ cho việc ra quyết định. Ví dụ “nhóm các khách hàng trong CSDL ngân hàng có vốn các đầu tư vào bất động sản cao”… Như vậy, PCDL là một phương pháp xử lý thông tin quan trọng và phổ biến, nó nhằm khám phá mối liên hệ giữa các mẫu dữ liệu bằng cách tổ chức chúng thành các cụm. Ta có thể khái quát hóa khái niệm PCDL [10][19]: PCDL là một kỹ thuật trong KPDL, nhằm tìm kiếm, phát hiện các cụm, các mẫu dữ liệu tự nhiên, tiềm ẩn, quan trọng trong tập dữ liệu lớn từ đó cung cấp thông tin, tri thức hữu ích cho việc ra quyết định. Như vậy, PCDL là quá trình phân chia một tập dữ liệu ban đầu thành các cụm dữ liệu sao cho các phần tử trong một cụm "tương tự" với nhau và các phần tử trong các cụm khác nhau sẽ "phi tương tự" với nhau. Số các cụm dữ liệu được Khai phá dữ liệu Web bằng kỹ thuật phân cụm Hoàng Văn Dũng 11 phân ở đây có thể được xác định trước theo kinh nghiệm hoặc có thể được tự động xác định của phương pháp phân cụm. Độ tương tự được xác định dựa trên giá trị các thuộc tính mô tả đối tượng. Thông thường, phép đo khoảng cách thường được sử dụng để đánh giá độ tương tự hay phi tương tự. Ta có thể minh hoạ vấn đề phân cụm như hình sau đây: Hình 1.4. Mô phỏng sự PCDL Trong hình trên, sau khi phân cụm ta thu được bốn cụm trong đó các phần tử "tương tự" thì được xếp vào một cụm, các phần tử "phi tương tự" thì chúng thuộc về các cụm khác nhau. Trong PCDL khái niệm, hai hoặc nhiều đối tượng cùng được xếp vào một cụm nếu chúng có chung một định nghĩa về khái niệm hoặc chúng xấp xỉ với các khái niệm mô tả cho trước. Như vậy, PCDL không sử dụng độ đo “tương tự” như đã trình bày ở trên. Trong học máy, PCDL được xem là vấn đề học không có giám sát, vì nó phải giải quyết vấn đề tìm một cấu trúc trong tập hợp dữ liệu chưa biết trước các thông tin về lớp hay các thông tin về tập huấn luyện. Trong nhiều trường hợp, nếu phân lớp được xem là vấn đề học có giám sát thì PCDL là một bước trong phân lớp dữ liệu, PCDL sẽ khởi tạo các lớp cho phân lớp bằng cách xác định các nhãn cho các nhóm dữ liệu. Một vấn đề thường gặp trong PCDL là hầu hết các dữ liệu cần cho phân cụm đều có chứa dữ liệu "nhiễu" do quá trình thu thập thiếu chính xác hoặc thiếu đầy đủ, vì vậy cần phải xây dựng chiến lược cho bước tiền xử lý dữ liệu nhằm khắc phục hoặc loại bỏ "nhiễu" trước khi bước vào giai đoạn phân tích Khai phá dữ liệu Web bằng kỹ thuật phân cụm Hoàng Văn Dũng 12 PCDL. "Nhiễu" ở đây có thể là các đối tượng dữ liệu không chính xác hoặc các đối tượng dữ liệu khuyết thiếu thông tin về một số thuộc tính. Một trong các kỹ thuật xử lý nhiễu phổ biến là việc thay thế giá trị của các thuộc tính của đối tượng "nhiễu" bằng giá trị thuộc tính tương ứng của đối tượng dữ liệu gần nhất. Ngoài ra, dò tìm phần tử ngoại lai là một trong những hướng nghiên cứu quan trọng trong PCDL, chức năng của nó là xác định một nhóm nhỏ các đối tượng dữ liệu "khác thường" so với các dữ liệu khác trong CSDL - tức là các đối tượng dữ liệu không tuân theo các hành vi hoặc mô hình dữ liệu - nhằm tránh sự ảnh hưởng của chúng tới quá trình và kết quả của PCDL. Khám phá các phần tử ngoại lai đã được phát triển và ứng dụng trong viễn thông, dò tìm gian lận thương mại… Tóm lại, PCDL là một vấn đề khó vì người ta phải đi giải quyết các vấn đề con cơ bản như sau: - Biểu diễn dữ liệu. - Xây dựng hàm tính độ tương tự. - Xây dựng các tiêu chuẩn phân cụm. - Xây dựng mô hình cho cấu trúc cụm dữ liệu. - Xây dựng thuật toán phân cụm và xác lập các điều kiện khởi tạo. - Xây dựng các thủ tục biểu diễn và đánh giá kết quả phân cụm. Theo các nghiên cứu thì đến nay chưa có một phương pháp phân cụm tổng quát nào có thể giải quyết trọn vẹn cho tất cả các dạng cấu trúc cụm dữ liệu. Hơn nữa, các phương pháp phân cụm cần có cách thức biểu diễn cấu trúc các cụm dữ liệu khác nhau, với mỗi cách thức biểu diễn khác nhau sẽ có một thuật toán phân cụm phù hợp. PCDL đang là vấn đề mở và khó vì người ta cần phải đi giải quyết nhiều vấn đề cơ bản như đã đề cập ở trên một cách trọn vẹn và phù hợp với nhiều dạng dữ liệu khác nhau. Đặc biệt đối với dữ liệu hỗn hợp, đang ngày càng tăng trưởng không ngừng trong các hệ quản trị dữ liệu, đây cũng là một trong những thách thức lớn trong lĩnh vực KPDL trong những thập kỷ tiếp theo và đặc biệt là trong lĩnh vực KPDL Web. Khai phá dữ liệu Web bằng kỹ thuật phân cụm Hoàng Văn Dũng 13 1.2.2. Ứng dụng của phân cụm dữ liệu PCDL là một trong những công cụ chính của KPDL được ứng dụng trong nhiều lĩnh vực như thương mại và khoa học. Các kỹ thuật PCDL đã được áp dụng cho một số ứng dụng điển hình trong các lĩnh vực sau [10][19]: Thương mại: PCDL có thể giúp các thương nhân khám phá ra các nhóm khách hàng quan trọng có các đặc trưng tương đồng nhau và đặc tả họ từ các mẫu mua bán trong CSDL khách hàng. Sinh học: PCDL được sử dụng để xác định các loại sinh vật, phân loại các Gen với chức năng tương đồng và thu được các cấu trúc trong các mẫu. Phân tích dữ liệu không gian: Do sự đồ sộ của dữ liệu không gian như dữ liệu thu được từ các hình ảnh chụp từ vệ tinh, các thiết bị y học hoặc hệ thống thông tin địa lý (GIS), …làm cho người dùng rất khó để kiểm tra các dữ liệu không gian một cách chi tiết. PCDL có thể trợ giúp người dùng tự động phân tích và xử lý các dữ liêu không gian như nhận dạng và chiết xuất các đặc tính hoặc các mẫu dữ liệu quan tâm có thể tồn tại trong CSDL không gian. Lập quy hoạch đô thị: Nhận dạng các nhóm nhà theo kiểu và vị trí địa lý,… nhằm cung cấp thông tin cho quy hoạch đô thị. Nghiên cứu trái đất: Phân cụm để theo dõi các tâm động đất nhằm cung cấp thông tin cho nhận dạng các vùng nguy hiểm. Địa lý: Phân lớp các động vật, thực vật và đưa ra đặc trưng của chúng. Khai phá Web: PCDL có thể khám phá các nhóm tài liệu quan trọng, có nhiều ý nghĩa trong môi trường Web. Các lớp tài liệu này trợ giúp cho việc khám phá tri thức từ dữ liệu Web, khám phá ra các mẫu truy cập của khách hàng đặc biệt hay khám phá ra cộng đồng Web,… 1.2.3. Các yêu cầu đối với kỹ thuật phân cụm dữ liệu Việc xây dựng, lựa chọn một thuật toán phân cụm là bước then chốt cho việc giải quyết vấn đề phân cụm, sự lựa chọn này phụ thuộc vào đặc tính dữ liệu cần phân cụm, mục đích của ứng dụng thực tế hoặc xác định độ ưu tiên giữa chất lượng của các cụm hay tốc độ thực hiện thuật toán,… Khai phá dữ liệu Web bằng kỹ thuật phân cụm Hoàng Văn Dũng 14 Hầu hết các nghiên cứu và phát triển thuật toán PCDL đều nhằm thoả mãn các yêu cầu cơ bản sau [10][19]: Có khả năng mở rộng: Một số thuật toán có thể ứng dụng tốt cho tập dữ liệu nhỏ (khoảng 200 bản ghi dữ liệu) nhưng không hiệu quả khi áp dụng cho tập dữ liệu lớn (khoảng 1 triệu bản ghi). Thích nghi với các kiểu dữ liệu khác nhau: Thuật toán có thể áp dụng hiệu quả cho việc phân cụm các tập dữ liệu với nhiều kiểu dữ liệu khác nhau như dữ liệu kiểu số, kiểu nhị phân, dữ liệu định danh, hạng mục,... và thích nghi với kiểu dữ liệu hỗn hợp. Khám phá ra các cụm với hình thù bất kỳ: Do hầu hết các CSDL có chứa nhiều cụm dữ liệu với các hình thù khác nhau như: hình lõm, hình cầu, hình que,… Vì vậy, để khám phá được các cụm có tính tự nhiên thì các thuật toán phân cụm cần phải có khả năng khám phá ra các cụm dữ liệu có hình thù bất kỳ. Tối thiểu lượng tri thức cần cho xác định các tham số vào: Do các giá trị đầu vào thường ảnh hưởng rất lớn đến thuật toán phân cụm và rất phức tạp để xác định các giá trị vào thích hợp đối với các CSDL lớn. Ít nhạy cảm với thứ tự của dữ liệu vào: Cùng một tập dữ liệu, khi đưa vào xử lý cho thuật toán PCDL với các thứ tự vào của các đối tượng dữ liệu ở các lần thực hiện khác nhau thì không ảnh hưởng lớn đến kết quả phân cụm. Khả năng thích nghi với dữ liệu nhiễu cao: Hầu hết các dữ liệu phân cụm trong KPDL đều chứa đựng các dữ liệu lỗi, dữ liệu không đầy đủ, dữ liệu rác. Thuật toán phân cụm không những hiệu quả đối với các dữ liệu nhiễu mà còn tránh dẫn đến chất lượng phân cụm thấp do nhạy cảm với nhiễu. Ít nhạy cảm với các tham số đầu vào: Nghĩa là giá trị của các tham số đầu vào khác nhau ít gây ra các thay đổi lớn đối với kết quả phân cụm. Thích nghi với dữ liệu đa chiều: Thuật toán có khả năng áp dụng hiệu quả cho dữ liệu có số chiều khác nhau. Dễ hiểu, dễ cài đặt và khả thi. Các yêu cầu này đồng thời là các tiêu chí để đánh giá hiệu quả của các phương pháp PCDL, đây là những thách thức cho các nhà nghiên cứu trong lĩnh vực PCDL. Khai phá dữ liệu Web bằng kỹ thuật phân cụm Hoàng Văn Dũng 15 1.2.4. Các kiểu dữ liệu và độ đo tương tự Trong phần này ta phân tích các kiểu dữ liệu thường được sử dụng trong PCDL. Trong PCDL, các đối tượng dữ liệu cần phân tích có thể là con người, nhà cửa, tiền lương, các thực thể phần mềm,… Các đối tượng này thường được diễn tả dưới dạng các thuộc tính của nó. Các thuộc tính này là các tham số cần cho giải quyết vấn đề PCDL và sự lựa chọn chúng có tác động đáng kể đến các kết quả của phân cụm. Phân loại các kiểu thuộc tính khác nhau là một vấn đề cần giải quyết đối với hầu hết các tập dữ liệu nhằm cung cấp các phương tiện thuận lợi để nhận dạng sự khác nhau của các phần tử dữ liệu. Dưới đây là cách phân lớp dựa trên hai đặc trưng là: kích thước miền và hệ đo. 1.2.4.1. Phân loại kiểu dữ liệu dựa trên kích thước miền - Thuộc tính liên tục: Nếu miền giá trị của nó là vô hạn không đếm được, nghĩa là giữa hai giá trị tồn tại vô số giá trị khác. Thí dụ như các thuộc tính về màu, nhiệt độ hoặc cường độ âm thanh. - Thuộc tính rời rạc: Nếu miền giá trị của nó là tập hữu hạn hoặc đếm được. Thí dụ như các thuộc tính về số serial của một cuốn sách, số thành viên trong một gia đình,… 1.2.4.2. Phân loại kiểu dữ liệu dựa trên hệ đo Giả sử ta có hai đối tượng x, y và các thuộc tính xi, yi tương ứng với thuộc tính thứ i của chúng. Chúng ta có các lớp kiểu dữ liệu như sau: - Thuộc tính định danh: Dạng thuộc tính khái quát hoá của thuộc tính nhị phân, trong đó miền giá trị là rời rạc không phân biệt thứ tự và có nhiều hơn hai phần tử - nghĩa là nếu x và y là hai đối tượng thuộc tính thì chỉ có thể xác định là x  y hoặc x = y. Thí dụ như thuộc tính về nơi sinh. - Thuộc tính có thứ tự: Là thuộc tính định danh có thêm tính thứ tự, nhưng chúng không được định lượng. Nếu x và y là hai thuộc tính thứ tự thì ta có thể xác định là x  y hoặc x = y hoặc x > y hoặc x < y. Thí dụ như thuộc tính Huy chương của vận động viên thể thao. Khai phá dữ liệu Web bằng kỹ thuật phân cụm Hoàng Văn Dũng 16 - Thuộc tính khoảng: Nhằm để đo các giá trị theo xấp xỉ tuyến tính. Với thuộc tính khoảng, ta có thể xác định một thuộc tính là đứng trước hoặc đứng sau thuộc tính khác với một khoảng là bao nhiêu. Nếu xi > yi thì ta nói x cách y một khoảng |xi – yi| tương ứng với thuộc tính thứ i. Ví dụ: thuộc tính số Serial của một đầu sách trong thư viện hoặc thuộc tính số kênh trên truyền hình. - Thuộc tính tỉ lệ: Là thuộc tính khoảng nhưng được xác định một cách tương đối so với điểm mốc, thí dụ như thuộc tính chiều cao hoặc cân nặng lấy giá trị 0 làm mốc. Trong các thuộc tính dữ liệu trình bày ở trên, thuộc tính định danh và thuộc tính có thứ tự gọi chung là thuộc tính hạng mục, thuộc tính khoảng và thuộc tính tỉ lệ được gọi là thuộc tính số. Người ta còn đặc biệt quan tâm đến dữ liệu không gian. Đây là loại dữ liệu có các thuộc tính số khái quát trong không gian nhiều chiều, dữ liệu không gian mô tả các thông tin liên quan đến không gian chứa đựng các đối tượng, thí dụ như thông tin về hình học,… Dữ liệu không gian có thể là dữ liệu liên tục hoặc rời rạc: Dữ liệu không gian rời rạc: Có thể là một điểm trong không gian nhiều chiều và cho phép ta xác định được khoảng cách giữa các đối tượng dữ liệu trong không gian. Dữ liệu không gian liên tục: Bao gồm một vùng trong không gian. Thông thường, các thuộc tính số được đo bằng các đơn vị xác định như là Kilogams hoặc Centimeter. Tuy nhiên, các đơn vị đo có ảnh hưởng đến các kết quả phân cụm. Thí dụ như thay đổi độ đo cho thuộc tính cân nặng từ Kilogams sang Pound có thể mang lại các kết quả khác nhau trong phân cụm. Để khắc phục điều này người ta phải chuẩn hoá dữ liệu, tức là sử dụng các thuộc tính dữ liệu không phụ thuộc vào đơn vị đo. Thực hiện chuẩn hoá phụ thuộc vào ứng dụng và người dùng, thông thường chuẩn hoá dữ liệu được thực hiện bằng cách thay thế mỗi một thuộc tính bằng thuộc tính số hoặc thêm các trọng số cho các thuộc tính. Khai phá dữ liệu Web bằng kỹ thuật phân cụm Hoàng Văn Dũng 17 1.2.4.3. Khái niệm và phép đo độ tương tự, phi tương tự Khi các đặc tính của dữ liệu được xác định, người ta tìm cách thích hợp để xác định "khoảng cách" giữa các đối tượng (phép đo độ tương tự dữ liệu). Đây là các hàm để đo sự giống nhau giữa các cặp đối tượng dữ liệu, thông thường các hàm này hoặc là để tính độ tương tự hoặc là tính độ phi tương tự giữa các đối tượng dữ liệu. Giá trị của hàm tính độ đo tương tự càng lớn thì sự giống nhau giữa đối tượng càng lớn và ngược lại, còn hàm tính độ phi tương tự tỉ lệ nghịch với hàm tính độ tương tự. Độ tương tự hoặc độ phi tương tự có nhiều cách để xác định, chúng thường được đo bằng khoảng cách giữa các đối tượng. Tất cả các cách đo độ tương tự đều phụ thuộc vào kiểu thuộc tính mà ta phân tích. Thí dụ, đối với thuộc tính hạng mục người ta không sử dụng độ đo khoảng cách mà sử dụng một hướng hình học của dữ liệu. Tất cả các độ đo dưới đây được xác định trong không đo gian metric. Bất kỳ một metric nào cũng là một độ đo, nhưng điều ngược lại không đúng. Để tránh sự nhầm lẫn, thuật ngữ độ đo ở đây đề cập đến hàm tính độ tương tự hoặc độ phi tương tự. Một không gian metric là một tập trong đó có xác định các "khoảng cách" giữa từng cặp phần tử, với những tính chất thông thường của khoảng cách hình học. Nghĩa là, một tập X (các phần tử của nó có thể là những đối tượng bất kỳ) gồm các đối tượng dữ liệu trong CSDL D gọi là một không gian metric nếu với mỗi cặp phần tử x, y thuộc X đều xác định một số thực δ(x,y), được gọi là khoảng cách giữa x và y thoả mãn hệ tính chất sau: (i) δ(x, y) > 0 nếu x ≠ y; (ii) δ(x,y)= 0 nếu x = y; (iii) δ(x, y) = δ(y, x) với mọi x, y; (iv) δ(x, y) ≤ δ(x, z)+ δ(z,y). Hàm δ(x, y) được gọi là một metric của không gian. Các phần tử của X được gọi là các điểm của không gian này. Một số phép đo độ tương tự áp dụng đối với các kiểu dữ liệu khác nhau [10][17][27]: + Thuộc tính khoảng: Sau khi chuẩn hoá, độ đo phi tương tự của hai đối tượng dữ liệu x, y được xác định bằng các metric như sau: Khai phá dữ liệu Web bằng kỹ thuật phân cụm Hoàng Văn Dũng 18 Khoảng cách Minskowski: )||( 1 /1 ),(    n i q ii yx q yxd , với q là số nguyên dương. Khoảng cách Euclide:     n i yx iiyxd 1 2 )(),( , (trường hợp đặc biệt của khoảng cách Minskowski trong trường hợp q =2). Khoảng cách Manhattan:    n i ii yxyxd 1 ||),( , (trường hợp đặc biệt của khoảng cách Minskowski trong trường hợp q=1). Khoảng cách cực đại: ||),( 1 yxMax ii n i yxd   , đây là trường hợp của khoảng cách Minskowski trong trường hợp q. + Thuộc tính nhị phân: Trước hết ta có xây dựng bảng tham số sau: y: 1 y: 0 x: 1    +  x: 0    +  +   +   Bảng 1.1. Bảng tham số thuộc tính nhị phân Trong đó:  =  +  +  +  , các đối tượng x, y mà tất cả các thuộc tính của nó đều là nhị phân biểu thị bằng 0 và 1. Bảng trên cho ta các thông tin sau: -  là tổng số các thuộc tính có giá trị là 1 trong cả hai đối tượng x, y. -  là tổng số các giá trị thuộc tính có giá trị là 1 trong x và 0 trong y. -  là tổng số các giá trị thuộc tính có giá trị là 0 trong x và 1 trong y. -  là tổng số các giá trị thuộc tính có giá trị là 0 trong x và y. Các phép đo độ tương tự đối với dữ liệu thuộc tính nhị phân được định nghĩa như sau: - Hệ số đối sánh đơn giản:    ),( yxd , ở đây cả hai đối tượng x và y có vai trò như nhau, nghĩa là chúng đối xứng và có cùng trọng số. Bảng 1: Bảng ngẫu nhiên Khai phá dữ liệu Web bằng kỹ thuật phân cụm Hoàng Văn Dũng 19 - Hệ số Jacard:    ),( yxd , tham số này bỏ qua số các đối sánh giữa 0-0. Công thức tính này được sử dụng trong trường hợp mà trọng số của các thuộc tính có giá trị 1 của đối tượng dữ liệu có giá trị cao hơn nhiều so với các thuộc tính có giá trị 0, như vậy các thuộc tính nhị phân ở đây là không đối xứng. + Thuộc tính định danh: Độ đo phi tương tự giữa hai đối tượng x và y được định nghĩa như sau: p mp yxd  ),( , trong đó m là số thuộc tính đối sánh tương ứng trùng nhau và p là tổng số các thuộc tính. + Thuộc tính có thứ tự: Phép đo độ phi tương tự giữa các đối tượng dữ liệu với thuộc tính thứ tự được thực hiện như sau, ở đây ta giả sử i là thuộc tính thứ tự có Mi giá trị (Mi kích thước miền giá trị): Các trạng thái Mi được sắp thứ tự như sau: [1…Mi], ta có thể thay thế mỗi giá trị của thuộc tính bằng giá trị cùng loại ri, với ri  {1,…,Mi}. Mỗi một thuộc tính thứ tự có các miền giá trị khác nhau, vì vậy ta chuyển đổi chúng về cùng miền giá trị [0,1] bằng cách thực hiện phép biến đổi sau cho mỗi thuộc tính: 1 1 )( )(    M r z i j ij i , với i=1,..,Mi Sử dụng công thức tính độ phi tương tự của thuộc tính khoảng đối với các giá trị z j i )( , đây cũng chính là độ phi tương tự của thuộc tính có thứ tự. + Thuộc tính tỉ lệ: Có nhiều cách khác nhau để tính độ tương tự giữa các thuộc tính tỉ lệ. Một trong những số đó là sử dụng công thức tính logarit cho mỗi thuộc tính xi, thí dụ qi = log(xi), lúc này qi đóng vai trò như thuộc tính khoảng. Phép biến đổi logarit này thích hợp trong trường hợp các giá trị của thuộc tính là số mũ. Trong thực tế, khi tính độ đo tương tự dữ liệu, người ta chỉ xem xét một phần các thuộc tính đặc trưng đối với các kiểu dữ liệu hoặc đánh trọng số cho cho tất cả các thuộc tính dữ liệu. Trong một số trường hợp, người ta loại bỏ đơn vị đo của các thuộc tính dữ liệu bằng cách chuẩn hoá chúng hoặc gán trọng số Khai phá dữ liệu Web bằng kỹ thuật phân cụm Hoàng Văn Dũng 20 cho mỗi thuộc tính giá trị trung bình, độ lệch chuẩn. Các trọng số này có thể sử dụng trong các độ đo khoảng cách trên, thí dụ với mỗi thuộc tính dữ liệu đã được gán trọng số tương ứng wi ( ki 1 ), độ tương tự dữ liệu được xác định như sau:     n i i yxw iiyxd 1 2 )(),( . Người ta có thể chuyển đổi giữa các mô hình cho các kiểu dữ liệu trên, thí dụ dữ liệu kiểu hạng mục có thể chuyển đổi thành dữ liệu nhị phân và ngược lại. Nhưng giải pháp này rất tốt kém về chi phí tính toán, cần phải cân nhắc khi áp dụng cách thức này. Tuỳ từng trường hợp dữ liệu cụ thể mà người ta sử dụng các mô hình tính độ tương tự khác nhau. Việc xác định độ tương tự dữ liệu thích hợp, chính xác, đảm bảo khách quan là rất quan trọng và góp phần xây dựng thuật toán PCDL có hiệu quả cao trong việc đảm bảo chất lượng cũng như chi phí tính toán của thuật toán. 1.3. Khai phá Web 1.3.1. Lợi ích của khai phá Web Với sự phát triển nhanh chóng của thông tin trên www, KPDL Web đã từng bước trở nên quan trọng hơn trong lĩnh vực KPDL, người ta luôn hy vọng lấy được những tri thức hữu ích thông qua việc tìm kiếm, phân tích, tổng hợp, khai phá Web. Những tri thức hữu ích có thể giúp ta xây dựng nên những Web site hiệu quả để có thể phục vụ cho con người tốt hơn, đặc biệt trong lĩnh vực thương mại điện tử. Khám phá và phân tích những thông tin hữu ích trên www bằng cách sử dụng kỹ thuật KPDL đã trở thành một hướng quan trọng trong lĩnh vực khám phá tri thức. Khai phá Web bao gồm khai phá cấu trúc Web, khai phá nội dung Web và khai phá các mẫu truy cập Web. Sự phức tạp trong nội dung của các trang Web khác với các tài liệu văn bản truyền thống [16]. Chúng không đồng nhất về cấu trúc, hơn nữa nguồn thông tin Web thay đổi một cách nhanh chóng, không những về nội dung mà cả về cấu Khai phá dữ liệu Web bằng kỹ thuật phân cụm Hoàng Văn Dũng 21 trúc trang. Chẳng hạn như tin tức, thị trường chứng khoán, thông tin quảng cáo, trung tâm dịch vụ mạng,... Tất cả thông tin được thay đổi trên Web theo từng giai đoạn. Các liên kết trang và đường dẫn truy cập cũng luôn thay đổi. Khả năng gia tăng liên tục về số lượng người dùng, sự quan tâm tới Web cũng khác nhau, động cơ người dùng rất đa dạng và phong phú. Vậy làm thế nào để có thể tìm kiếm được thông tin mà người dùng cần? Làm thế nào để có được những trang Web chất lượng cao?... Những vấn đề này sẽ được thực hiện hiệu quả hơn bằng cách nghiên cứu các kỹ thuật KPDL áp dụng trong môi trường Web. Thứ nhất, ta sẽ quản lý các Web site thật tốt; thứ hai, khai phá những nội dung mà người dùng quan tâm; thứ ba, sẽ thực hiện phân tích các mẫu sử dụng Web. Dựa vào những vấn đề cơ bản trên, ta có thể có những phương pháp hiệu quả cao để cung cấp những thông tin hữu ích đối với người dùng Web và giúp người dùng sử dụng nguồn tài nguyên Web một cách hiệu quả. 1.3.2. Khai phá Web Có nhiều khái niệm khác nhau về khai phá Web, nhưng có thể tổng quát hóa như sau [5][30]: Khai phá Web là việc sử dụng các kỹ thuật KPDL để tự động hóa quá trình khám phá và trích rút những thông tin hữu ích từ các tài liệu, các dịch vụ và cấu trúc Web. Hay nói cách khác khai phá Web là việc thăm dò những thông tin quan trọng và những mẫu tiềm năng từ nội dung Web, từ thông tin truy cập Web, từ liên kết trang và từ nguồn tài nguyên thương mại điện tử bằng việc sử dụng các kỹ thuật KPDL, nó có thể giúp con người rút ra những tri thức, cải tiến việc thiết kế các Web site và phát triển thương mại điện tử tốt hơn. Lĩnh vực này đã thu hút được nhiều nhà khoa học quan tâm. Quá trình khai phá Web có thể chia thành các công việc nhỏ như sau: i. Tìm kiếm nguồn tài nguyên: Thực hiện tìm kiếm và lấy các tài liệu Web phục vụ cho việc khai phá. ii. Lựa chọn và tiền xử lý dữ liệu: Lựa chọn và tiền xử lý tự động các loại thông tin từ nguồn tài nguyên Web đã lấy về. Khai phá dữ liệu Web bằng kỹ thuật phân cụm Hoàng Văn Dũng 22 iii. Tổng hợp: Tự động khám phá các mẫu chung tại các Web site riêng lẽ cũng như nhiều Website với nhau. iv. Phân tích: Đánh giá, giải thích, biểu diễn các mẫu khai phá được. 1.3.3. Các kiểu dữ liệu Web Ta có thể khái quát bằng sơ đồ sau: Hình 1.5. Phân loại dữ liệu Web Các đối tượng của khai phá Web bao gồm [5][16]: Server logs, Web pages, Web hyperlink structures, dữ liệu thị trường trực tuyến và các thông tin khác. Web logs: Khi người dùng duyệt Web, dịch vụ sẽ phân ra 3 loại dữ liệu đăng nhập: sever logs, error logs, và cookie logs. Thông qua việc phân tích các tài liệu đăng nhập này ta có thể khám phá ra những thông tin truy cập. Web pages: Hầu hết các phương pháp KPDL Web được sử dụng trong Web pages là theo chuẩn HTML. Web hyperlink structure: Các trang Web được liên kết với nhau bằng các siêu liên kết, điều này rất quan trọng để khai phá thông tin. Do các siêu liên kết Web là nguồn tài nguyên rất xác thực. Dữ liệu thị trường trực tuyến: Như lưu trữ thông tin thương mại điện tử trong các site thương mại điện tử. Các thông tin khác: Chủ yếu bao gồm các đăng ký người dùng, nó có thể giúp cho việc khai phá tốt hơn. Web data Structure data Usage data User Profile data Content data Free Text HTML file XML file Multimedia Dynamic link Static link Dynamic content Khai phá dữ liệu Web bằng kỹ thuật phân cụm Hoàng Văn Dũng 23 1.4. Xử lý dữ liệu văn bản ứng dụng trong khai phá dữ liệu Web 1.4.1. Dữ liệu văn bản Trong các loại dữ liệu hiện nay thì văn bản là loại dữ liệu phổ biến nhất và nó có mặt khắp mọi nơi, đặc biệt là đối với dữ liệu trên Web. Do vậy, các bài toán xử lý văn bản đã được đặt ra từ rất sớm và hiện nay nó vẫn là vấn đề rất được nhiều nhà nghiên cứu quan tâm, một trong những bài toán đó là tìm kiếm và trích dẫn văn bản, biểu diễn và phân loại văn bản,…. CSDL văn bản có thể chia làm 2 loại chính [14][20]: + Dạng không có cấu trúc: Đây là những tài liệu văn bản thông thường mà ta đọc thường ngay trên các sách, báo, internet,… đây là dạng dữ liệu của ngôn ngữ tự nhiên của con người và nó không theo một khuôn mẫu định sẵn nào cả. + Dạng nữa cấu trúc: Đây là những văn bản được tổ chức dưới dạng cấu trúc lỏng, nhưng vẫn thể hiện nội dung chính của văn bản, như văn bản HTML, Email,.. 1.4.2. Một số vấn đề trong xử lý dữ liệu văn bản Mỗi văn bản được biểu diễn bằng một vector Boolean hoặc vector số. Những vector này được xét trong một không gian đa chiều, trong đó mỗi chiều tương ứng với một từ mục riêng biệt trong tập văn bản. Mỗi thành phần của vector được gán một hàm giá trị f, nó là một số chỉ mật độ tương ứng của chiều đó trong văn bản. Nếu thay đổi giá trị hàm f ta có thể tạo ra nhiều trọng số khác nhau. Một số vấn đề liên quan đến việc biểu diễn văn bản bằng mô hình không gian vector: + Không gian vector là một tập hợp bao gồm các từ. + Từ là một chuỗi các ký tự (chữ cái và chữ số); ngoại trừ các khoảng trống (space, tab), ký tự xuống dòng, dấu câu (như dấu chấm, phẩy, chấm phẩy, dấu cảm,...). Mặt khác, để đơn giản trong quá trình xử lý, ta không phân biệt chữ hoa và chữ thường (nếu chữ hoa thì chuyển về chữ thường). + Cắt bỏ từ: Trong nhiều ngôn ngữ, nhiều từ có cùng từ gốc hoặc là biến thể của từ gốc sang một từ khác. Việc sử dụng từ gốc làm giảm đáng kể số Khai phá dữ liệu Web bằng kỹ thuật phân cụm Hoàng Văn Dũng 24 lượng các từ trong văn bản (giảm số chiều của không gian), nhưng việc cắt bỏ các từ lại rất khó trong việc hiểu văn bản. Ngoài ra, để nâng cao chất lượng xử lý, một số công trình nghiên cứu đã đưa ra một số cải tiến thuật toán xem xét đến đặc tính ngữ cảnh của các từ bằng việc sử dụng các cụm từ/văn phạm chứ không chỉ xét các từ riêng lẽ [31]. Những cụm từ này có thể được xác định bằng cách xem xét tần số xuất hiện của cả cụm từ đó trong tài liệu. Bằng phương pháp biểu diễn không gian vector, ta có thể thấy rõ ràng là chiều của một vector sẽ rất lớn bởi số chiều của nó được xác định bằng số lượng các từ khác nhau trong tập hợp từ. Chẳng hạn, số lượng các từ có thể từ 103 đến 105 đối với các tập văn bản nhỏ. Vấn đề đặt ra là làm sao để giảm số chiều của vector mà vẫn đảm bảo việc xử lý văn bản đúng và chính xác, đặc biệt là trong môi trường www, ta sẽ xem xét đến một số phương pháp để giảm số chiều của vector. 1.4.2.1. Loại bỏ từ dừng Trước hết ta thấy trong ngôn ngữ tự nhiên có nhiều từ chỉ dùng để biểu diễn cấu trúc câu chứ không biểu đạt nội dung của nó. Như các giới từ, từ nối,... những từ như vậy xuất hiện nhiều trong các văn bản mà không liên quan gì tới chủ đề hoặc nội dung của văn bản. Do đó, ta có thể loại bỏ những từ đó để giảm số chiều của vector biểu diễn văn bản, những từ như vậy được gọi là những từ dừng. Sau đây là ví dụ về tần số xuất hiện cao của một số từ (tiếng Anh) trong 336,310 tài liệu gồm tổng cộng 125.720.891 từ, 508.209 từ riêng biệt. (thống kê của B. Croft, UMass) Bảng 1.2. Thống kê các từ tần số xuất hiện cao Khai phá dữ liệu Web bằng kỹ thuật phân cụm Hoàng Văn Dũng 25 1.4.2.2. Định luật Zipf Để giảm số chiều của vector biểu diễn văn bản hơn nữa ta dựa vào một quan sát sau: Nhiều từ trong văn bản xuất hiện rất ít lần, nếu mục tiêu của ta là xác định độ tương tự và sự khác nhau trong toàn bộ tập hợp các văn bản thì các từ xuất hiện một hoặc hai lần (tần số xuất hiện nhỏ) thì ảnh hưởng rất bé đến các văn bản. Tiền đề cho việc lý luận để loại bỏ những từ có tần suất nhỏ được đưa ra bởi Zipf năm 1949. Zipf phát biểu dưới dạng một quan sát nhưng ngay trong thời điểm đó, quan sat đó đã được gọi là định luật Zipf, mặc dù nó thực sự không phải là một định luật mà đúng hơn đó là một hiện tượng xấp xỉ toán học. Để mô tả định luật Zipf, ta gọi tổng số tần số xuất hiện của từ t trong tài liệu D là ft. Sau đó sắp xếp tất cả các từ trong tập hợp theo chiều giảm dần của tần số xuất hiện f và gọi thứ hạng của mỗi từ t là rt. Định luật Zipf được phát biểu dưới dạng công thức như sau: rt.ft  K (với K là một hằng số). Trong tiếng Anh, người ta thấy rằng hằng số K  N/10 trong đó N là số các từ trong văn bản. Ta có thể viết lại định luật Zipf như sau: rt  K/ ft Giả sử từ ti được sắp xếp ở vị trí thấp nhất với tần số xuất hiện là b nào đấy và từ tj cũng được sắp ở vị trí thấp kế tiếp với một tần số xuất hiện là b+1. Ta có thể thu được thứ hạng xấp xỉ của các từ này là rtiK/b và rtj  K/(b+1), trừ 2 biểu thức này cho nhau ta xấp xỉ đối với các từ riêng biệt có tần số xuất hiện là b. rti- rtj  K/b-K/(b+1) Ta xấp xỉ giá trị của từ trong tập hợp có thứ hạng cao nhất. Một cách tổng quát, một từ chỉ xuất hiện một lần trong tập hợp, ta có rmax=K. Xét phân bố của các từ duy nhất xuất hiện b lần trong tập hợp, chia 2 vế cho nhau ta được K/b. Do đó, định luật Zipf cho ta thấy sự phân bố đáng chú ý của các tự riêng biệt trong 1 tập hợp được hình thành bởi các từ xuất hiện ít nhất trong tập hợp. Năm 1958 Luhn đề xuất những từ “phổ biến” và “hiếm” và không cần thiết cho quá trình xử lý như sau. Khai phá dữ liệu Web bằng kỹ thuật phân cụm Hoàng Văn Dũng 26 Hình 1.6. Lược đồ thống kê tần số của từ theo Định luật Zipf 1.4.3. Các mô hình biểu diễn dữ liệu văn bản Trong các bài toán xử lý văn bản, ta thấy rằng vai trò của biểu diễn văn bản rất lớn, đặc biệt trong các bài toán tìm kiếm, phân cụm,… Theo các nghiên cứu về cách biểu diễn khác nhau trong xử lý văn bản thì cách biểu diễn tốt nhất là bằng các từ riêng biệt được rút ra từ tài liệu gốc và cách biểu diễn này ảnh hưởng tương đối nhỏ đối với kết quả. Các cách tiếp cận khác nhau sử dụng mô hình toán học khác nhau để tính toán, ở đây ta sẽ trình bày một số mô hình phổ biến và được đăng nhiều trong các bài báo gần đây [14][22]. 1.4.3.1. Mô hình Boolean Đây là mô hình biểu diễn vector với hàm f nhận giá trị rời rạc với duy nhất hai giá trị đúng/sai (true/false). Hàm f tương ứng với thuật ngữ ti sẽ cho giá trị đúng khi và chỉ khi ti xuất hiện trong tài liệu đó. Giả sử rằng có một CSDL gồm m văn bản, D={d1, d2, ..., dm}. Mỗi văn bản được biểu diễn dưới dạng một vector gồm n thuật ngữ T={t1, t2,...,tn}. Gọi W={wij} là ma trận trọng số, wij là giá trị trọng số của thuật ngữ ti trong tài liệu dj. Mô hình Boolean là mô hình đơn giản nhất, nó được xác định như sau: Vùng thấp vùng cao Vùng những từ mang ý nghĩa T ần s ố x u ất h iệ n Thứ hạng của từ r f Wij= 1 nếu ti  dj 0 nếu ti  dj Khai phá dữ liệu Web bằng kỹ thuật phân cụm Hoàng Văn Dũng 27 1.4.3.2. Mô hình tần số Mô hình này xác định giá trị trọng số các phần tử trong ma trận W(wij) các giá trị là các số dương dựa vào tần số xuất hiện của các từ trong tài liệu hoặc tần số xuất hiện của tài liệu trong CSDL. Có 2 phương pháp phổ biến: 1.4.3.2.1. Mô hình dựa trên tần số xuất hiện các từ Trong mô hình dưa trên tần số xuất hiện từ (TF-Term Frequency) giá trị của các từ được tính dựa vào số lần xuất hiện của nó trong tài liệu, gọi tfij là số lần xuất hiện của từ ti trong tài liệu dj, khi đó wij có thể được tính theo một trong các công thức sau [31]: - Wij = tfij - Wij = 1+log(tfij) - Wij = ijtf Với mô hình này, trọng số wij đồng biến với số lần xuất hiện của thuật ngữ ti trong tài liệu dj. Khi số lần xuất hiện thuật ngữ ti trong tài liệu dj càng lớn thì có nghĩa là dj càng phụ thuộc nhiều vào thuật ngữ ti, nói cách khác thuật ngữ ti mang nhiều thông tin hơn trong tài liệu dj. 1.4.3.2.2. Phương pháp dựa trên tần số văn bản nghịch đảo Trong mô hình dưa trên tần số văn bản nghịch đảo (IDF-Inverse Document Frequency) giá trị trọng số của từ được tính bằng công thức sau [31]: Trong đó, n là tổng số văn bản trong CSDL, hi là số văn bản chứa thuật ngữ ti. Trọng số wij trong công thức trên được tính dựa vào độ quan trọng của thuật ngữ ti trong tài liệu dj. Nếu ti xuất hiện càng ít trong các văn bản thì nó càng quan trọng, do đó nếu ti xuất hiện trong dj thì trọng số của nó càng lớn, nghĩa là nó càng quan trọng để phân biệt dj với các tài liệu khác và lượng thông tin của nó càng lớn. Wij= )log()log()log( i i hn h n  nếu ti  dj 0 nếu ngược lại (ti dj) Khai phá dữ liệu Web bằng kỹ thuật phân cụm Hoàng Văn Dũng 28 1.4.3.2.3. Mô hình kết hợp TF-IDF Trong mô hình TF-IDF [31], mỗi tài liệu dj được xét đến thể hiện bằng một đặc trưng của (t1, t2,.., tn) với ti là một từ/cụm từ trong dj. Thứ tự của ti dựa trên trọng số của mỗi từ. Các tham số có thể được thêm vào để tối ưu hóa quá trình thực hiện nhóm. Như vậy, thành phần trọng số được xác định bởi công thức sau, nó kết hợp giá trị trọng số tf và giá trị trọng số idf. Công thức tính trọng số TF-IDF là: Trong đó: tfij là tần số xuất hiện của ti trong tài liệu dj idfij là nghịch đảo tần số xuất hiện của ti trong tài liệu dj. hi là số các tài liệu mà ti xuất hiện trong CSDL. n là tổng số tài liệu trong CSDL. Từ công thức này, ta có thể thấy trọng số của mỗi phần tử là dựa trên nghịch đảo của tần số tài liệu trong CSDL mà ti và tần số xuất hiện của phần tử này trong tài liệu. Thông thường ta xây dựng một từ điển từ để lấy đi những từ rất phổ biến và những từ có tần số xuất hiện thấp. Ngoài ra ta phải lựa chọn m (Zemir sử dụng 500) phần tử có trọng số cao nhất như là những từ đặc trưng. Phương pháp này kết hợp được ưu điểm của cả 2 phương pháp trên. Trọng số wij được tính bằng tần số xuất hiện của thuật ngữ ti trong tài liệu dj và độ “hiếm” của thuật ngữ ti trong toàn bộ CSDL. Tùy theo ràng buộc cụ thể của bài toán mà ta sử dụng các mô hình biểu diễn văn bản cho phù hợp. Tính toán độ tương tự giữa 2 vector Xét 2 vector X={x1, x2,..., xm} và Y={y1, y2,..., ym}. )log()]log(1[ i ijijijij h n fidftfw  nếu ti  dj 0 nếu ngược lại (ti dj) Data set Wij= Khai phá dữ liệu Web bằng kỹ thuật phân cụm Hoàng Văn Dũng 29 Trong mô hình TF-IDF, ta có thể lựa chọn công thức nào đó để tính toán độ tương tự giữa các cặp tài liệu hoặc các cụm. Sau đây là các độ đo tương tự phổ biến [5][14][31]:        m i i m i i m i ii yx yx YXS 1 2 1 2 1 )(2 ),im(:Dice        m i ii m i i m i i m i ii yxyx yx YX 11 2 1 2 1 )( )( ),Sim(:Jaccard        m i i m i i m i ii yx yx YX 1 2 1 2 1 )( ),Sim(:Cosine ),min( )( ),Sim(: 1 2 1 2 1       m i i m i i m i ii yx yx YXOverlap    m i ii yxYXYX 1 2)(),Dis(),Sim(:Euclidean    m i ii yxYXYX 1 ||),Dis(),Sim(:Manhattan Hình 1.7. Các độ đo tương tự thường dùng Với xi và yj đại diện một cặp từ hoặc cụm từ trong tài liệu. Sử dụng các công thức này và với một ngưỡng thích hợp, ta có thể dễ dàng xác định mức độ tương tự của các tài liệu trong CSDL. Ý tưởng sử dụng mô hình TF-IDF để biểu diễn tài liệu có nhiều từ thông dụng giữa 2 tài liệu thì có nhiều khả năng chúng tương tự nhau. Kỹ thuật phân cụm phân cấp và phân cụm phân hoạch (k-means) là 2 kỹ thuật phân cụm thường được sử dụng cho phân cụm tài liệu với mô hình TF-IDF. Khai phá dữ liệu Web bằng kỹ thuật phân cụm Hoàng Văn Dũng 30 1.5. Tổng kết chương 1 Chương 1 trình bày những kiến thức cơ bản về khai phá dữ liệu và khám phá tri thức trong CSDL, các kỹ thuật áp dụng trong khai phá dữ liệu, những chức năng chính, ứng dụng của nó trong xã hội,... Chương này cũng trình bày một hướng nghiên cứu và ứng dụng trong khai phá dữ liệu là phân cụm dữ liệu, gồm tổng quan về kỹ thuật phân cụm, các ứng dụng của phân cụm, các yêu cầu đối với kỹ thuật phân cụm, các kiểu dữ liệu và độ đo tương tự,... Một hướng tiếp cận mới trong khai phá dữ liệu là khai phá dữ liệu trong môi trường Web. Phần này trình bày khái niệm và lợi ích của khai phá Web, một số mô hình biểu diễn và xử lý dữ liệu văn bản áp dụng trong khai phá Web như mô hình Boolean, mô hình tần số (TF), mô hình tần số nghịch đảo văn bản (IDF), mô hình kết hợp TF-IDF và các độ đo để xác định độ tương tự văn bản. Khai phá dữ liệu Web bằng kỹ thuật phân cụm Hoàng Văn Dũng 31 Chương 2. MỘT SỐ KỸ THUẬT PHÂN CỤM DỮ LIỆU Các kỹ thuật áp dụng để giải quyết vấn đề PCDL đều hướng tới hai mục tiêu chung: Chất lượng của các cụm khám phá được và tốc độ thực hiện của thuật toán. Tuy nhiên, các kỹ thuật PCDL có thể được phân loại thành một số loại cơ bản dưa trên các phương pháp tiếp cận như sau [10][19]: 2.1. Phân cụm phân hoạch Ý tưởng chính của kỹ thuật này là phân một tập dữ liệu có n phần tử cho trước thành k nhóm dữ liệu sao cho mỗi phần tử dữ liệu chỉ thuộc về một nhóm dữ liệu và mỗi nhóm dữ liệu có tối thiểu ít nhất một phần tử dữ liệu. Các thuật toán phân hoạch có độ phức tạp rất lớn khi xác định nghiệm tối ưu toàn cục cho vấn đề PCDL, vì nó phải tìm kiếm tất cả các cách phân hoạch có thể được. Chính vì vậy, trên thực tế người ta thường đi tìm giải pháp tối ưu cục bộ cho vấn đề này bằng cách sử dụng một hàm tiêu chuẩn để đánh giá chất lượng của các cụm cũng như để hướng dẫn cho quá trình tìm kiếm phân hoạch dữ liệu. Với chiến lược này, thông thường người ta bắt đầu khởi tạo một phân hoạch ban đầu cho tập dữ liệu theo phép ngẫu nhiên hoặc theo heuristic và liên tục tinh chỉnh nó cho đến khi thu được một phân hoạch mong muốn, thoả mãn các điều kiện ràng buộc cho trước. Các thuật toán phân cụm phân hoạch cố gắng cải tiến tiêu chuẩn phân cụm bằng cách tính các giá trị đo độ tương tự giữa các đối tượng dữ liệu và sắp xếp các giá trị này, sau đó thuật toán lựa chọn một giá trị trong dãy sắp xếp sao cho hàm tiêu chuẩn đạt giá trị tối thiểu. Như vậy, ý tưởng chính của thuật toán phân cụm phân hoạch tối ưu cục bộ là sử dụng chiến lược ăn tham để tìm kiếm nghiệm. Lớp các thuật toán phân cụm phân hoạch bao gồm các thuật toán đề xuất đầu tiên trong lĩnh vực KPDL cũng là các thuật toán được áp dụng nhiều trong thực tế như k-means, PAM, CLARA, CLARANS. Sau đây là một số thuật toán kinh điển được kế thừa sử dụng rộng rãi. Khai phá dữ liệu Web bằng kỹ thuật phân cụm Hoàng Văn Dũng 32 2.1.1. Thuật toán k-means Thuật toán phân cụm k-means do MacQueen đề xuất trong lĩnh vực thống kê năm 1967, mục đích của thuật toán k-means là sinh ra k cụm dữ liệu {C1, C2,…, Ck} từ một tập dữ liệu ban đầu gồm n đối tượng trong không gian d chiều Xi =(xi1, xi2, …,xid) ( ni ,1 ), sao cho hàm tiêu chuẩn:     k i x iC i mxE D 1 2 )( đạt giá trị tối thiểu. Trong đó: mi là trọng tâm của cụm Ci, D là khoảng cách giữa hai đối tượng. Trọng tâm của một cụm là một vector, trong đó giá trị của mỗi phần tử của nó là trung bình cộng các thành phần tương ứng của các đối tượng vector dữ liệu trong cụm đang xét. Tham số đầu vào của thuật toán là số cụm k, tập CSDL gồm n phần tử và tham số đầu ra của thuật toán là các trọng tâm của các cụm dữ liệu. Độ đo khoảng cách D giữa các đối tượng dữ liệu thường được sử dụng dụng là khoảng cách Euclide, bởi vì đây là mô hình khoảng cách dễ để lấy đạo hàm và xác định các cực trị tối thiểu. Hàm tiêu chuẩn và độ đo khoảng cách có thể được xác định cụ thể hơn tuỳ vào ứng dụng hoặc các quan điểm của người dùng. Thuật toán k-means bao gồm các bước cơ bản như sau: INPUT: Một CSDL gồm n đối tượng và số các cụm k. OUTPUT: Các cụm Ci (i=1,..,k) sao cho hàm tiêu chuẩn E đạt giá trị tối thiểu. Bước 1: Khởi tạo Chọn k đối tượng mj (j=1...k) là trọng tâm ban đầu của k cụm từ tập dữ liệu (việc lựa chọn này có thể là ngẫu nhiên hoặc theo kinh nghiệm). Bước 2: Tính toán khoảng cách Đối với mỗi đối tượng Xi (1  i  n) , tính toán khoảng cách từ nó tới mỗi trọng tâm mj với j=1,..,k, sau đó tìm trọng tâm gần nhất đối với mỗi đối tượng. Bước 3: Cập nhật lại trọng tâm Đối với mỗi j=1,..,k, cập nhật trọng tâm cụm mj bằng cách xác định trung bình cộng của các vector đối tượng dữ liệu. Bước 4: Điều kiện dừng Lặp các bước 2 và 3 cho đến khi các trọng tâm của cụm không thay đổi. Hình 2.1. Thuật toán k-means Khai phá dữ liệu Web bằng kỹ thuật phân cụm Hoàng Văn Dũng 33 Thuật toán k-means được chứng minh là hội tụ và có độ phức tạp tính toán là: O( T flop dkn  )( ). Trong đó: n là số đối tượng dữ liệu, k là số cụm dữ liệu, d là số chiều,  là số vòng lặp, T flop là thời gian để thực hiện một phép tính cơ sở như phép tính nhân, chia, …Như vậy, do k-means phân tích phân cụm đơn giản nên có thể áp dụng đối với tập dữ liệu lớn. Tuy nhiên, nhược điểm của k- means là chỉ áp dụng với dữ liệu có thuộc tính số và khám phá ra các cụm có dạng hình cầu, k-means còn rất nhạy cảm với nhiễu và các phần tử ngoại lai trong dữ liệu. Hình sau diễn tả môi phỏng về một số hình dạng cụm dữ liệu khám phá được bởi k-means: Hình 2.2. Hình dạng cụm dữ liệu được khám phá bởi k-means Hơn nữa, chất lượng PCDL của thuật toán k-means phụ thuộc nhiều vào các tham số đầu vào như: số cụm k và k trọng tâm khởi tạo ban đầu. Trong trường hợp, các trọng tâm khởi tạo ban đầu mà quá lệch so với các trọng tâm cụm tự nhiên thì kết quả phân cụm của k-means là rất thấp, nghĩa là các cụm dữ liệu được khám phá rất lệch so với các cụm trong thực tế. Trên thực tế người ta chưa có một giải pháp tối ưu nào để chọn các tham số đầu vào, giải pháp thường 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 1 0 0 1 2 3 4 5 6 7 8 9 0 1 0 K=2 Chọn k đối tượng trung tâm tùy ý Gán mỗi đối tượng vào các cụm Cập nhật lại trọng tâm 0 1 2 3 4 5 6 7 8 9 0 2 3 4 5 6 7 8 9 10 Cập nhật lại trọng tâm Gán lại các đối tượng Gán lại các đối tượng 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 Gán lại các đối tượng Khai phá dữ liệu Web bằng kỹ thuật phân cụm Hoàng Văn Dũng 34 được sử dụng nhất là thử nghiệm với các giá trị đầu vào k khác nhau rồi sau đó chọn giải pháp tốt nhất. Đến nay, đã có rất nhiều thuật toán kế thừa tư tưởng của thuật toán k-means áp dụng trong KPDL để giải quyết tập dữ liệu có kích thước rất lớn đang được áp dụng rất hiệu quả và phổ biến như thuật toán k-medoid, PAM, CLARA, CLARANS, k- prototypes, … 2.1.2. Thuật toán PAM Thuật toán PAM (Partitioning Around Medoids) được Kaufman và Rousseeuw đề xuất 1987, là thuật toán mở rộng của thuật toán k-means, nhằm có khả năng xử lý hiệu quả đối với dữ liệu nhiễu hoặc các phần tử ngoại lai. Thay vì sử dụng các trọng tâm như k-means, PAM sử dụng các đối tượng medoid để biểu diễn cho các cụm dữ liệu, một đối tượng medoid là đối tượng đặt tại vị trí trung tâm nhất bên trong của mỗi cụm. Vì vậy, các đối tượng medoid ít bị ảnh hưởng của các đối tượng ở rất xa trung tâm, trong khi đó các trọng tâm của thuật toán k-means lại rất bị tác động bởi các điểm xa trung tâm này. Ban đầu, PAM khởi tạo k đối tượng medoid và phân phối các đối tượng còn lại vào các cụm với các đối tượng medoid đại diện tương ứng sao cho chúng tương tự với đối tượng medoid trong cụm nhất. Để xác định các medoid, PAM bắt đầu bằng cách lựa chọn k đối tượng medoid bất kỳ. Sau mỗi bước thực hiện, PAM cố gắng hoán chuyển giữa đối tượng medoid Om và một đối tượng Op không phải là medoid, miễn là sự hoán chuyển này nhằm cải tiến chất lượng của phân cụm, quá trình này kết thúc khi chất lượng phân cụm không thay đổi. Chất lượng phân cụm được đánh giá thông qua hàm tiêu chuẩn, chất lượng phân cụm tốt nhất khi hàm tiêu chuẩn đạt giá trị tối thiểu. Để quyết định hoán chuyển hai đối tượng Om và Op hay không, thuật toán PAM sử dụng giá trị tổng chi phí hoán chuyển Cjmp làm căn cứ: - Om: Là đối tượng medoid hiện thời cần được thay thế Khai phá dữ liệu Web bằng kỹ thuật phân cụm Hoàng Văn Dũng 35 - Op: Là đối tượng medoid mới thay thế cho Om; - Oj: Là đối tượng dữ liệu (không phải là medoid) có thể được di chuyển sang cụm khác. - Om,2: Là đối tượng medoid hiện thời khác với Om mà gần đối tượng Oj nhất. Bốn trường hợp như mô tả trong thí dụ trên, PAM tính giá trị hoán đổi Cjmp cho tất cả các đối tượng Oj. Cjmp ở đây nhằm để làm căn cứ cho việc hoán chuyển giữa Om và Op. Trong mỗi trường hợp Cjmp được tính với 4 cách khác nhau như sau: - Trường hợp 1: Giả sử Oj hiện thời thuộc về cụm có đại diện là Om và Oj tương tự với Om,2 hơn Op (d(Oj, Op) d(Oj, Om,2)). Trong khi đó, Om,2 là đối tượng medoid tương tự xếp thứ 2 tới Oj trong số các medoid. Trong trường hợp này, ta thay thế Om bởi đối tượng medoid mới Op và Oj sẽ thuộc về cụm có đối tượng đại diện là Om,2. Vì vậy, giá trị hoán chuyển Cjmp được xác định như sau: Cjmp = d(Oj, Om,2) – d(Oj, Om). Giá trị Cjmp là không âm. Hình 2.3. Trường hợp Cjmp=d(Oj,Om,2) – d(Oj, Om) không âm - Trường hợp 2: Oj hiện thời thuộc về cụm có đại diện là Om, nhưng Oj ít tương tự với Om,2 so với Op (d(Oj,Op)< d(Oj,Om,2)). Nếu thay thế Om bởi Op thì Oj sẽ thuộc về cụm có đại diện là Op. Vì vậy, giá trị Cjmp được xác định như sau: Cjmp=(Oj,Op)- d(Oj, Om). Cjmp ở đây có thể là âm hoặc dương. 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 Op Om Om,2 Oj Khai phá dữ liệu Web bằng kỹ thuật phân cụm Hoàng Văn Dũng 36 Hình 2.4. Trường hợp Cjmp= (Oj,Op)- d(Oj, Om) có thể âm hoặc dương - Trường hợp 3: Giả sử Oj hiện thời không thuộc về cụm có đối tượng đại diện là Om mà thuộc về cụm có đại diện là Om,2. Mặt khác, giả sử Oj tương tự với Om,2 hơn so với Op, khi đó, nếu Om được thay thế bởi Op thì Oj vẫn sẽ ở lại trong cụm có đại diện là Om,2. Do đó: Cjmp= 0. Hình 2.5. Trường hợp Cjmp bằng không - Trường hợp 4: Oj hiện thời thuộc về cụm có đại diện là Om,2 nhưng Oj ít tương tự tới Om,2 hơn so với Op. Vì vậy, nếu ta thay thế Om bởi Op thì Oj sẽ chuyển từ cụm Om,2 sang cụm Op. Do đó, giá trị hoán chuyển Cjmp được xác định là: Cjmp= (Oj,Op)- d(Oj, Om,2). Cjmp ở đây luôn âm. 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 Om2 Om Op Oj 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 Oj Om Op Om2 Khai phá dữ liệu Web bằng kỹ thuật phân cụm Hoàng Văn Dũng 37 Hình 2.6. Trường hợp Cjmp= (Oj,Op)- d(Oj, Om,2) luôn âm - Kết hợp cả bốn trường hợp trên, tổng giá trị hoán chuyển Om bằng Op được xác định như sau: TCmp =  j jmpC . Thuật toán PAM gồm các bước thực hiện chính như sau: INPUT: Tập dữ liệu có n phần tử, số cụm k OUTPUT: k cụm dữ liệu sao cho chất lượng phân hoạch là tốt nhất. Bước 1: Chọn k đối tượng medoid bất kỳ; Bước 2: Tính TCmp cho tất cả các cặp đối tượng Om, Op. Trong đó Om là đối tượng medoid và Op là đối tượng không phải là modoid. Bước 3: Với mỗi cặp đối tượng Om và Op. Tính minOm, minOp, TCmp. Nếu TCmp là âm, thay thế Om bởi Op và quay lại bước 2. Nếu TCmp dương, chuyển sang bước 4. Bước 4: Với mỗi đối tượng không phải là medoid, xác định đối tượng medoid tương tự với nó nhất đồng thời gán nhãn cụm cho chúng. Hình 2.7. Thuật toán PAM Trong bước 2 và 3, có PAM phải duyệt tất cả k(n-k) cặp Om, Op. Với mỗi cặp, việc tính toán TCmp yêu cầu kiểm tra n-k đối tượng. Vì vậy, độ phức tạp tính toán của PAM là O(Ik(n-k)2), trong đó I là số vòng lặp. Như vậy, thuật toán PAM kém hiệu quả về thời gian tính toán khi giá trị của k và n là lớn. 0 1 2 3 4 5 6 7 8 9 1 0 0 1 2 3 4 5 6 7 8 9 1 0 Om2 Om Op Oj Khai phá dữ liệu Web bằng kỹ thuật phân cụm Hoàng Văn Dũng 38 2.1.3. Thuật toán CLARA CLARA (Clustering LARge Application) được Kaufman và Rousseeuw đề xuất năm 1990, thuật toán này nhằm khắc phục nhược điểm của thuật toán PAM trong trường hợp giá trị của k và n lớn. CLARA tiến hành trích mẫu cho tập dữ liệu có n phần tử và áp dụng thuật toán PAM cho mẫu này và tìm ra các các đối tượng medoid của mẫu này. Người ta thấy rằng, nếu mẫu dữ liệu được trích một cách ngẫu nhiên, thì các medoid của nó xấp xỉ với các medoid của toàn bộ tập dữ liệu ban đầu. Để tiến tới một xấp xỉ tốt hơn, CLARA đưa ra nhiều cách lấy mẫu rồi thực hiện phân cụm cho mỗi trường hợp này và tiến hành chọn kết quả phân cụm tốt nhất khi thực hiện phân cụm trên các mẫu này. Để cho chính xác, chất lượng của các cụm được đánh giá thông độ phi tương tự trung bình của toàn bộ các đối tượng dữ liệu trong tập đối tượng ban đầu. Kết quả thực nghiệm chỉ ra rằng, 5 mẫu dữ liệu có kích thước 40+2k cho các kết quả tốt. Các bước thực hiện của thuật toán CLARA như sau: INPUT: CSDL gồm n đối tượng, số cụm k. OUTPUT: k cụm dữ liệu 1. For i = 1 to 5 do Begin 2. Lấy một mẫu có 40 + 2k đối tượng dữ liệu ngẫu nhiên từ tập dữ liệu và áp dụng thuật toán PAM cho mẫu dữ liệu này nhằm để tìm các đối tượng medoid đại diện cho các cụm. 3. Đối với mỗi đối tượng Oj trong tập dữ liệu ban đầu, xác định đối tượng medoid tương tự nhất trong số k đối tượng medoid. 4. Tính độ phi tương tự trung bình cho phân hoạch các đối tượng dành ở bước trước, nếu giá trị này bé hơn giá trị tối thiểu hiện thời thì sử dụng giá trị này thay cho giá trị tối thiếu ở trạng thái trước, như vậy tập k đối tượng medoid xác định ở bước này là tốt nhất cho đến thời điểm hiện tại. End; Hình 2.8. Thuật toán CLARA Độ phức tạp tính toán của thuật toán là O(k(40+k)2 + k(n-k)), và CLARA có thể thực hiện đối với tập dữ liệu lớn. Chú ý đối với kỹ thuật tạo mẫu trong PCDL: kết quả phân cụm có thể không phụ thuộc vào tập dữ liệu khởi tạo nhưng nó chỉ đạt tối ưu cục bộ. Khai phá dữ liệu Web bằng kỹ thuật phân cụm Hoàng Văn Dũng 39 2.1.4. Thuật toán CLARANS Thuật toán CLARANS (A Clustering Algorithm based on RANdomized Search) được Ng & Han đề xuất năm 1994, nhằm để cải tiến chất lượng cũng như mở rộng áp dụng cho tập dữ liệu lớn. CLARANS là thuật toán PCDL kết hợp thuật toán PAM với chiến lược tìm kiếm kinh nghiệm mới. Ý tưởng cơ bản của CLARANS là không xem xét tất cả các khả năng có thể thay thế các đối tượng tâm medoids bởi một đối tượng khác, nó ngay lập tức thay thế các đối tượng medoid này nếu việc thay thế có tác động tốt đến chất lượng phân cụm chứ không cần xác định cách thay thể tối ưu nhất. Một phân hoạch cụm phát hiện được sau khi thay thế đối tượng trung tâm được gọi là một láng giềng của phân hoạch cụm trước đó. Số các láng giềng được hạn chế bởi tham số do người dùng đưa vào là Maxneighbor, quá trình lựa chọn các láng giềng này là hoàn toàn ngẫu nhiên. Tham số Numlocal cho phép người dùng xác định số vòng lặp tối ưu cục bộ được tìm kiếm. Không phải tất các láng giềng được duyệt mà chỉ có Maxneighbor số láng giềng được duyệt. Một số khái niệm sử dụng trong thuật toán CLARANS được định nghĩa như sau: Giả sử O là một tập có n đối tượng và M là tập các đối tượng medoid, NMM là tập các đối tượng không phải medoid. Các đối tượng dữ liệu sử dụng trong thuật toán CLARANS là các khối đa diện. Mỗi đối tượng được diễn tả bằng một tập các cạch, mỗi cạnh được xác định bằng 2 đỉnh. Giả sử P R3 là một tập tất cả các điểm. Nói chung, các đối tượng ở đây là các đối tượng dữ liệu không gian và ta định nghĩa tâm của một đối tượng chính là trung bình cộng toán học của tất cả các đỉnh hay còn gọi là trọng tâm: Center: O  P Giả sử dist là một hàm khoảng cách, khoảng cách thường được chọn ở đây là khoảng cách Euclid: dist: P x PR0 + Khai phá dữ liệu Web bằng kỹ thuật phân cụm Hoàng Văn Dũng 40 Hàm khoảng cách dist có thể mở rộng cho các điểm của khối đa diện thông qua hàm tâm: dist: O x OR0 + sao cho dist (oi, oj) = dist (center(oi), center(oj)) Mỗi đối tượng được gán cho một tâm medoid của cụm nếu khoảng cách từ trọng tâm của đối tượng đó tới tâm medoid của nó là nhỏ nhất. Vì vậy, ta định nghĩa một tâm medoid như sau: medoid: OM Sao cho medoid (o) = mi, mi M, mj M: dist (o, mi) dist (o, mj), oO. Cuối cùng, ta định nghĩa một cụm với medoid mi tương ứng là một tập con các đối tượng trong O với medoid(o) = mi. Giả sử C0 là tập tất cả các phân hoạch của O. Hàm tổng để đánh giá chất lượng một phân hoạch được định nghĩa như sau: total_distance: C0R0 + sao cho total_distance(c) = dist (o, mi) với mi M, cluster(mi). Thuật toán CLARANS có thể được diễn tả như sau [10][19]: INPUT: Tập dữ liệu gồm n đối tượng, số cụm k, O, dist, numlocal, maxneighbor; OUTPUT: k cụm dữ liệu; For i=1 to numlocal do Begin Khởi tạo ngẫu nhiên k medois j = 1; while j < maxneighbor do Begin Chọn ngẫu nhiên một láng giềng R của S. Tính toán độ phi tương tự về khoảng cách giữa 2 láng giềng S và R. Nếu R có chi phí thấp hơn thì hoán đối R cho S và j=1 ngược lại j++; End; Kiểm tra khoảng cách của phân hoạch S có nhỏ hơn khoảng cách nhỏ nhất không, nếu nhỏ hơn thì lấy giá trị này để cập nhật lại khoảng cách nhỏ nhất và phân hoạch S là phân hoạch tốt nhất tại thời điểm hiện tại. End. Hình 2.9. Thuật toán CLARANS Khai phá dữ liệu Web bằng kỹ thuật phân cụm Hoàng Văn Dũng 41 Như vậy, quá trình hoạt động của CLARANS tương tự với quá trình hoạt động của thuật toán CLARA. Tuy nhiên, ở giai đoạn lựa chọn các trung tâm medoid cụm dữ liệu, CLARANS lựa chọn một giải pháp tốt hơn bằng cách lấy ngẫu nhiên một đối tượng của k đối tượng trung tâm medoid của cụm và cố gắng thay thế nó với một đối tượng được chọn ngẫu nhiên trong (n-k) đối tượng còn lại, nếu không có giải pháp nào tốt hơn sau một số cố gắng lựa chọn ngẫu nhiên xác định, thuật toán dừng và cho kết quả phân cụm tối ưu cục bộ. Trong trường hợp xấu nhất, CLARANS so sánh một đối tượng với tất các đối tượng Medoid. Vì vậy, độ phức tạp tính toán của CLARANS là O(kn2), do vậy CLARANS không thích hợp với tập dữ liệu lớn. CLARANS có ưu điểm là không gian tìm kiếm không bị giới hạn như đối với CLARA và trong cùng một lượng thời gian thì chất lượng của các cụm phân được là lớn hơn so với CLARA. 2.2. Phân cụm phân cấp Phân cụm phân cấp sắp xếp một tập dữ liệu đã cho thành một cấu trúc có dạng hình cây, cây phân cấp này được xây dựng theo kỹ thuật đệ quy. Cây phân cụm có thể được xây dựng theo hai phương pháp tổng quát: phương pháp “trên xuống” (Top down) và phương pháp “dưới lên” (Bottom up). Phương pháp Bottom up: Phương pháp này bắt đầu với mỗi đối tượng được khởi tạo tương ứng với các cụm riêng biệt, sau đó tiến hành nhóm các đối tượng theo một độ đo tương tự (như khoảng cách giữa hai trung tâm của hai nhóm), quá trình này được thực hiện cho đến khi tất cả các nhóm được hòa nhập vào một nhóm (mức cao nhất của cây phân cấp) hoặc cho đến khi các điều kiện kết thúc thoả mãn. Như vậy, cách tiếp cận này sử dụng chiến lược ăn tham trong quá trình phân cụm. Phương pháp Top Down: Bắt đầu với trạng thái là tất cả các đối tượng được xếp trong cùng một cụm. Mỗi vòng lặp thành công, một cụm được tách thành các cụm nhỏ hơn theo giá trị của một phép đo độ tương tự nào đó cho đến khi mỗi đối tượng là một cụm hoặc cho đến khi điều kiện dừng thoả mãn. Cách tiếp cận này sử dụng chiến lược chia để trị trong quá trình phân cụm. Khai phá dữ liệu Web bằng kỹ thuật phân cụm Hoàng Văn Dũng 42 Sau đây là minh họa chiến lược phân cụm phân cấp bottom up và Top down. Hình 2.10. Các chiến lược phân cụm phân cấp Trong thực tế áp dụng, có nhiều trường hợp người ta kết hợp cả hai phương pháp phân cụm phân hoạch và phương phân cụm phân cấp, nghĩa là kết quả thu được của phương pháp phân cấp có thể cải tiến thông quan bước phân cụm phân hoạch. Phân cụm phân hoạch và phân cụm phân cấp là hai phương pháp PCDL cổ điển, hiện nay đã có nhiều thuật toán cải tiến dựa trên hai phương pháp này đã được áp dụng phổ biến trong KPDL. Một số thuật toán phân cụm phân cấp điển hình như CURE, BIRCH, Chemeleon, AGNES, DIANA,... 2.2.1. Thuật toán BIRCH BIRCH (Balanced Iterative Reducing and Clustering Using Hierarchies) do Tian Zhang, amakrishnan và Livny đề xuất năm 1996, là thuật toán phân cụm phân cấp sử dụng chiến lược Top down. Ý tưởng của thuật toán là không cần lưu toàn bộ các đối tượng dữ liệu của các cụm trong bộ nhớ mà chỉ lưu các đại lượng thống kê. Đối với mỗi cụm dữ liệu, BIRCH chỉ lưu một bộ ba (n, LS, SS), với n là số đối tượng trong cụm, LS là tổng các giá trị thuộc tính của các đối tượng trong cụm và SS là tổng bình phương các giá trị thuộc tính của các đối tượng trong cụm. Các bộ ba này được gọi là các đặc trưng của cụm CF=(n, LS, SS) (Cluster Features - CF) và được lưu giữ trong một cây được gọi là cây CF. Hình sau đây biểu thị một ví dụ về cây CF. Chúng ta thấy rằng, tất cả các nút Bước 0 Bước 1 Bước 2 Bước 3 Bước 4 b d c e a a b d e c d e a b c d e Bước 4 Bước 3 Bước 2 Bước 1 Bước 0 Bottom up Top Down Khai phá dữ liệu Web bằng kỹ thuật phân cụm Hoàng Văn Dũng 43 trong của cây lưu tổng các đặc trưng cụm CF của nút con, trong khi đó các nút lá lưu trữ các đặc trưng của các cụm dữ liệu. Hình 2.11. Cây CF được sử dụng bởi thuật toán BIRCH Cây CF là cây cân bằng, nhằm để lưu trữ các đặc trưng của cụm. Cây CF chứa các nút trong và nút lá. Nút trong lưu giữ tổng các đặc trưng cụm của các nút con của nó. Một cây CF được đặc trưng bởi hai tham số: - Yếu tố nhánh (B): Nhằm xác định số tối đa các nút con của mỗi nút trong của cây; - Ngưỡng (T): Khoảng cách tối đa giữa bất kỳ một cặp đối tượng trong nút lá của cây, khoảng cách này còn gọi là đường kính của các cụm con được lưu tại các nút lá. Hai tham số này có ảnh hưởng lớn đến kích thước của cây CF. Thuật toán BIRCH thực hiện qua giai đoạn sau: INPUT: CSDL gồm n đối tượng, ngưỡng T OUTPUT: k cụm dữ liệu Bước 1: Duyệt tất cả các đối tượng trong CSDL và xây dựng một cây CF khởi tạo. Một đối tượng được chèn vào nút lá gần nhất tạo thành cụm con. Nếu đường kính của cụm con này lớn hơn T thì nút lá được tách. Khi một đối tượng thích hợp được chèn CF1 child1 CF3 child3 CF2 child2 CF6 child6 CF1 child1 CF3 child3 CF2 child2 CF5 child5 CF1 CF2 CF6 prev next CF1 CF2 CF4 prev next B = 7 L = 6 Root Non-leaf node Leaf node Leaf node Khai phá dữ liệu Web bằng kỹ thuật phân cụm Hoàng Văn Dũng 44 vào nút lá, tất cả các nút trỏ tới gốc của cây được cập nhật với các thông tin cần thiết. Bước 2: Nếu cây CF hiện thời không có đủ bộ nhớ trong thì tiến hành xây dựng một cây CF nhỏ hơn bằng cách điều khiển bởi tham số T (vì tăng T sẽ làm hoà nhập một số các cụm con thành một cụm, điều này làm cho cây CF nhỏ hơn). Bước này không cần yêu cầu bắt đầu đọc dữ liệu lại từ đầu nhưng vẫn đảm bảo hiệu chỉnh cây dữ liệu nhỏ hơn. Bước 3: Thực hiện phân cụm: Các nút lá của cây CF lưu giữ các đại lượng thống kê của các cụm con. Trong bước này, BIRCH sử dụng các đại lượng thống kê này để áp dụng một số kỹ thuật phân cụm thí dụ như k-means và tạo ra một khởi tạo cho phân cụm. Bước 4: Phân phối lại các đối tượng dữ liệu bằng cách dùng các đối tượng trọng tâm cho các cụm đã được khám phá từ bước 3: Đây là một bước tuỳ chọn để duyệt lại tập dữ liệu và gán nhãn lại cho các đối tượng dữ liệu tới các trọng tâm gần nhất. Bước này nhằm để gán nhãn cho các dữ liệu khởi tạo và loại bỏ các đối tượng ngoại lai Hình 2.12. Thuật toán BIRCH Khi hòa nhập 2 cụm ta có CF=CF1+CF2= (n1+n2, LS1+LS2, SS1+SS2). Khoảng cách giữa các cụm có thể đo bằng khoảng cách Euclid, Manhatta,.... Ví dụ: ),LS(n,CF SS   , n là số đối tượng dữ liệu Hình 2.13. Ví dụ về kết quả phân cụm bằng thuật toán BIRCH Sử dụng cấu trúc cây CF làm cho thuật toán BIRCH có tốc độ thực hiện PCDL nhanh và có thể áp dụng đối với tập dữ liệu lớn, BIRCH đặc biệt hiệu quả khi áp dụng với tập dữ liệu tăng trưởng theo thời gian. BIRCH chỉ duyệt toàn bộ dữ liệu một lần với một lần quét thêm tuỳ chọn, nghĩa là độ phức tạp của nó là O(n) (n là số đối tượng dữ liệu). Nhược điểm của nó là chất lượng của các cụm được khám Khai phá dữ liệu Web bằng kỹ thuật phân cụm Hoàng Văn Dũng 45 phá không được tốt. Nếu BIRCH sử dụng khoảng cách Euclide, nó thực hiện tốt chỉ với các dữ liệu số. Mặt khác, tham số vào T có ảnh hưởng rất lớn tới kích thước và tính tự nhiên của cụm. Việc ép các đối tượng dữ liệu làm cho các đối tượng của một cụm có thể là đối tượng kết thúc của cụm khác, trong khi các đối tượng gần nhau có thể bị hút bởi các cụm khác nếu chúng được biểu diễn cho thuật toán theo một thứ tự khác. BIRCH không thích hợp với dữ liệu đa chiều. 2.2.2. Thuật toán CURE Việc chọn một cách biểu diễn cho các cụm có thể nâng cao chất lượng phân cụm. Thuật toán CURE (Clustering Using REpresentatives) được đề xuất bởi Sudipto Guha, Rajeev Rastogi và Kyuseok Shim năm 1998 [19] là thuật toán sử dụng chiến lược Bottom up của kỹ thuật phân cụm phân cấp. Thay vì sử dụng các trọng tâm hoặc các đối tượng tâm để biểu diễn cụm, CURE sử dụng nhiều đối tượng để diễn tả cho mỗi cụm dữ liệu. Các đối tượng đại diện cho cụm này ban đầu được lựa chọn rải rác đều ở các vị trí khác nhau, sau đó chúng được di chuyển bằng cách co lại theo một tỉ lệ nhất định. Tại mỗi bước của thuật toán, hai cụm có cặp đối tượng đại diện gần nhất sẽ được trộn lại thành một cụm. Với cách thức sử dụng nhiều hơn một điểm đại diện cho các cụm, CURE có thể khám phá được các cụm có các dạng hình thù và kích thước khác nhau trong CSDL lớn. Việc co các đối tượng đại diện lại có tác dụng làm giảm tác động của các phần tử ngoại lai. Vì vậy, CURE có khả năng xử lý đối với các phần tử ngoại lai. Hình sau thí dụ về các dạng và kích thước cụm dữ liệu được khám phá bởi CURE: Hình 2.14. Các cụm dữ liệu được khám phá bởi CURE Khai phá dữ liệu Web bằng kỹ thuật phân cụm Hoàng Văn Dũng 46 Để áp dụng với CSDL lớn, CURE sử dụng lấy mẫu ngẫu nhiên và phân hoạch. Mẫu dữ liệu được xác định ngẫu nhiên là phân hoạch đầu tiên, CURE tiến hành phân cụm trên mỗi phân hoạch. Quá trình này lặp lại cho đến khi ta thu được phân hoạch đủ tốt. Các cụm thu được sau đó lại được phân cụm nhằm để thu được các cụm con cần quan tâm. Thuật toán CURE được thực hiện qua các bước cơ bản như sau: Bước 1. Chọn một mẫu ngẫu nhiên từ tập dữ liệu ban đầu; Bước 2. Phân hoạch mẫu này thành nhiều nhóm dữ liệu có kích thước bằng nhau: Ý tưởng chính ở đây là phân hoạch mẫu thành p nhóm dữ liệu bằng nhau, kích thước của mỗi phân hoạch là n'/p (với n' là kích thước của mẫu); Bước 3. Phân cụm các điểm của mỗi nhóm: Ta thực hiện PCDL cho các nhóm cho đến khi mỗi nhóm được phân thành n'/(pq)cụm (với q>1); Bước 4. Loại bỏ các phần tử ngoại lai: Trước hết, khi các cụm được hình thành cho đến khi số các cụm giảm xuống một phần so với số các cụm ban đầu. Sau đó, trong trường hợp các phần tử ngoại lai được lấy mẫu cùng với quá trình pha khởi tạo mẫu dữ liệu, thuật toán sẽ tự động loại bỏ các nhóm nhỏ. Bước 5. Phân cụm các cụm không gian: Các đối tượng đại diện cho các cụm di chuyển về hướng trung tâm cụm, nghĩa là chúng được thay thế bởi các đối tượng gần trung tâm hơn. Bước 6. Đánh dấu dữ liệu với các nhãn tương ứng. Hình 2.15. Thuật toán CURE Độ phức tạp tính toán của thuật toán CURE là O(n2log(n)). CURE là thuật toán tin cậy trong việc khám phá các cụm với hình thù bất kỳ và có thể áp dụng tốt trên các tập dữ liệu hai chiều. Tuy nhiên, nó lại rất nhạy cảm với các tham số như là tham số các đối tượng đại diện, tham số co của các phần tử đại diện. Nhìn chung thì BIRCH tốt hơn so với CURE về độ phức tạp, nhưng kém về chất lượng phân cụm. Cả hai thuật toán này có thể xử lý các phần tử ngoại lai tốt. Khai phá dữ liệu Web bằng kỹ thuật phân cụm Hoàng Văn Dũng 47 2.3. Phân cụm dựa trên mật độ Phương pháp này nhóm các đối tượng theo hàm mật độ xác định. Mật độ được định nghĩa như là số các đối tượng lân cận của một đối tượng dữ liệu theo một ngưỡng nào đó. Trong cách tiếp cận này, khi một cụm dữ liệu đã xác định thì nó tiếp tục được phát triển thêm các đối tượng dữ liệu mới miễn là số các đối tượng lân cận của các đối tượng này phải lớn hơn một ngưỡng đã được xác định trước. Phương pháp phân cụm dựa vào mật độ của các đối tượng để xác định các cụm dữ liệu và có thể phát hiện ra các cụm dữ liệu với hình thù bất kỳ. Tuy vậy, việc xác định các tham số mật độ của thuật toán rất khó khăn, trong khi các tham số này lại có tác động rất lớn đến kết quả PCDL. Hình minh hoạ về các cụm dữ liệu với các hình thù khác nhau dựa trên mật độ được khám phá từ 3 CSDL khác nhau: Hình 2.16. Một số hình dạng khám phá bởi phân cụm dưa trên mật độ Các cụm có thể được xem như các vùng có mật độ cao, được tách ra bởi các vùng không có hoặc ít mật độ. Khái niệm mật độ ở đây được xem như là các số các đối tượng láng giềng. Một số thuật toán PCDL dựa trên mật độ điển hình như [2][3][13][20]: DBSCAN, OPTICS, DENCLUE, SNN,…. 2.3.1 Thuật toán DBSCAN Thuật toán phân cụm dựa trên mật độ thông dụng nhất là thuật toán DBSCAN (Density - Based Spatial Clustering of Applications with noise) do Ester, P. Kriegel và J. Sander đề xuất năm 1996. Thuật toán đi tìm các đối tượng CSDL 1 CSDL 2 CSDL 3 Khai phá dữ liệu Web bằng kỹ thuật phân cụm Hoàng Văn Dũng 48 mà có số đối tượng láng giềng lớn hơn một ngưỡng tối thiểu. Một cụm được xác định bằng tập tất cả các đối tượng liên thông mật độ với các láng giềng của nó. Thuật toán DBSCAN dựa trên các khái niệm mật độ có thể áp dụng cho các tập dữ liệu không gian lớn đa chiều. Sau đây là một số định nghĩa và bổ đề được sử dụng trong thuật toán DBSCAN. Định nghĩa 1: Các lân cận của một điểm P với ngưỡng Eps, ký hiệu NEps(p) được xác định như sau: NEps(p) = {q  D | khoảng cách Dist(p,q) ≤ Eps}, D là tập dữ liệu cho trước. Hình 2.17. Lân cận của P với ngưỡng Eps Một điểm p muốn nằm trong một cụm C nào đó thì NEps(p) phải có tối thiểu MinPts điểm. Theo định nghĩa trên, chỉ những điểm thực sự nằm trong cụm mới thoả mãn điều kiện là điểm thuộc vào cụm. Những điểm nằm ở biên của cụm thì không thoả mãn điều kiện đó, bởi vì thông thường thì lân cận với ngưỡng Eps của điểm biên thì bé hơn lân cận với ngưỡng cũng Eps của điểm nhân . Để tránh được điều này, ta có thể đưa ra một tiêu chuẩn khác để định nghĩa một điểm thuộc vào một cụm như sau: Nếu một điểm p muốn thuộc một cụm C phải tồn tại một điểm q mà p  NEps(q) và số điểm trong NEps(q) phải lớn hơn số điểm tối thiểu. Điều này có thể được định nghĩa một cách hình thức như sau: Định nghĩa 2: Mật độ - đến được