Tài liệu Phân cụm dữ liệu và ứng dụng trong công tác tái bảo hiểm luận văn ths. công nghệ thông tin 1 01 10

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Trần Thanh Sơn PHÂN CỤM DỮ LIỆU VÀ ỨNG DỤNG TRONG CÔNG TÁC TÁI BẢO HIỂM LUẬN VĂN THẠC SĨ Hà Nội - 2006 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Trần Thanh Sơn PHÂN CỤM DỮ LIỆU VÀ ỨNG DỤNG TRONG CÔNG TÁC TÁI BẢO HIỂM Ngành: Công nghệ thông tin Mã số: 1.01.10 LUẬN VĂN THẠC SĨ NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS.TS. VŨ ĐỨC THI Hà Nội - 2006 Phân cụm dữ liệu và ứng dụng trong công tác Tái bảo hiểm MỤC LỤC MỤC LỤC ................................................................................................ 1 DANH SÁCH HÌNH VẼ........................................................................... 3 DANH SÁCH BẢNG BIỂU ..................................................................... 4 BẢNG TỪ VIẾT TẮT .............................................................................. 4 TỪ KHOÁ ................................................................................................ 4 MỞ ĐẦU .................................................................................................. 6 CHƢƠNG 1: TỔNG QUAN VỀ DATA MINING .................................... 9 1.1 Giới thiệu chung .............................................................................................. 9 1.2 KPDL là gì? .................................................................................................... 9 1.3 Quá trình khám phá tri thức trong CSDL ................................................... 10 1.4 Các kỹ thuật áp dụng trong KPDL .............................................................. 11 1.4.1 Các kỹ thuật tiếp cận trong KPDL ..................................................................... 11 1.4.2 Các dạng dữ liệu có thể khai phá ...................................................................... 13 1.5 Ứng dụng của KPDL .................................................................................... 13 1.6 Phân cụm dữ liệu và ứng dụng ..................................................................... 13 CHƢƠNG 2: PHÂN CỤM DỮ LIỆU VÀ CÁC TIẾP CẬN ................... 14 2.1 Vấn đề phân cụm dữ liệu .............................................................................. 14 2.2 Các ứng dụng của phân cụm dữ liệu ............................................................ 16 2.3 Các kiểu dữ liệu và độ đo tƣơng tự .............................................................. 17 2.3.1 Phân loại các kiểu dữ liệu dựa trên kích thước miền ......................................... 17 2.3.2 Phân loại các kiểu dữ liệu dựa trên hệ đo.......................................................... 18 2.3.3 Khái niệm về tương tự và phi tương tự .............................................................. 19 2.4 Những kỹ thuật tiếp cận trong phân cụm dữ liệu ...................................... 23 2.4.1 Phân cụm phân hoạch ....................................................................................... 23 2.4.2 Phân cụm dữ liệu phân cấp .............................................................................. 24 2.4.3 Phân cụm dữ liệu dựa trên mật độ..................................................................... 25 2.4.4 Phân cụm dữ liệu dựa trên lưới ......................................................................... 26 2.4.5 Phân cụm dữ liệu dựa trên mô hình ................................................................... 27 2.4.6 Phân cụm dữ liệu có ràng buộc ........................................................................ 27 2.5 Các yêu cầu cần thiết cho tạo dựng kỹ thuật PCDL ................................... 28 CHƢƠNG 3: CÁC THUẬT TOÁN PHÂN CỤM DỮ LIỆU ĐIỂN HÌNH31 3.1 Họ các thuật toán phân hoạch ...................................................................... 31 3.1.1 Thuật toán k-means ........................................................................................... 31 3.1.2 Thuật toán PAM ................................................................................................ 34 3.1.3 Thuật toán CLARA ............................................................................................ 38 3.1.4 Thuật toán CLARANS ....................................................................................... 39 3.1.5 Nhận xét chung về họ các thuật toán phân hoạch .............................................. 42 3.2 Các thuật toán phân cụm phân cấp ............................................................. 43 3.2.1 Thuật toán BIRCH ............................................................................................ 43 3.2.2 Thuật toán CURE.............................................................................................. 45 3.3 Các thuật toán phân cụm dựa trên mật độ .................................................. 47 1 Phân cụm dữ liệu và ứng dụng trong công tác Tái bảo hiểm 3.3.1 Thuật toán DBSCAN ......................................................................................... 47 3.3.2 Thuật toán OPTICS ........................................................................................... 52 3.3.3. Thuật toán DENCLUE ..................................................................................... 53 3.4 Một số thuật toán phân cụm dữ liệu đặc thù ............................................... 55 3.4.1 Thuật toán STING ............................................................................................. 55 3.4.2 Thuật toán CLIQUE .......................................................................................... 56 3.4.3 Thuật toán EM .................................................................................................. 56 CHƢƠNG 4: PHÂN CỤM DỮ LIỆU MỜ ............................................. 59 4.1 Vấn đề phân cụm mờ .................................................................................... 59 4.2. Thuật toán FCM .......................................................................................... 60 4.2.1 Hàm tiêu chuẩn ................................................................................................. 60 4.2.2 Thuật toán FCM................................................................................................ 61 4.3 Thuật toán  FCM ........................................................................................ 64 4.3.1 Hàm tiêu chuẩn ................................................................................................. 64 4.3.2 Thụât toán  FCM ............................................................................................ 66 CHƢƠNG 5: PHÂN CỤM SONG SONG TRÊN TẬP DỮ LIỆU HỖN HỢP ........................................................................................................ 69 5. 1. Giới thiệu ..................................................................................................... 69 5.2. Mô hình dữ liệu có kiểu hỗn hợp giữa thuộc tính số và thuộc tính hạng mục ...................................................................................................................... 69 5.2.1 Các miền thuộc tính .......................................................................................... 69 5.2.2 Các đối tượng có kiểu hỗn hợp .......................................................................... 70 5. 3 Cơ sở toán học cho thuật toán k - prototypes ............................................. 71 5.3.1. Hàm tiêu chuẩn ................................................................................................ 71 5.3.2. Độ đo sự tương tự ............................................................................................ 73 5.4 Thuật toán k- prototypes .............................................................................. 74 5.5 Nhận xét chung về phƣơng pháp k-prototypes ............................................ 82 KẾT LUẬN ............................................................................................. 83 1. Các kết quả đạt đƣợc trong luận văn ............................................................. 83 2. Hƣớng nghiên cứu tiếp theo ........................................................................... 84 PHỤ LỤC................................................................................................ 85 1. 2. 3. Đặt bài toán .................................................................................................. 85 Thiết kế chƣơng trình .................................................................................. 86 Một số module chính của chƣơng trình ...................................................... 91 TÀI LIỆU THAM KHẢO ....................................................................... 98 2 Phân cụm dữ liệu và ứng dụng trong công tác Tái bảo hiểm DANH SÁCH HÌNH VẼ Hình 1 - Các bƣớc thực hiện trong quá trình khám phá tri thức ............................................................. 11 Hình 2: Các lĩnh vực liên quan đến Khám phá tri thức trong CSDL ....................................................... 11 Hình 3: Mô phỏng vấn đề PCDL ............................................................................................................... 14 Hình 4 : Các chiến lƣợc phân cụm phân cấp............................................................................................. 25 Hình 5: Một số hình dạng cụm dữ liệu khám phá đƣợc bởi kỹ thuật PCDL dựa trên mật độ................. 26 Hình 6: Mô hình cấu trúc dữ liệu lƣới....................................................................................................... 27 Hình 7: Các bƣớc thực hiện của thuật toán k-means ............................................................................... 32 Hình 8: Thuật toán k-means chi tiết ......................................................................................................... 33 Hình 9: Thí dụ về một số hình dạng cụm dữ liệu đƣợc khám phá bởi k-means ..................................... 34 Hình 10: Thí dụ về các khả năng thay thế các đối tƣợng tâm medoid ...................................................... 36 Hình 11: Các bƣớc thực hiện của thuật toán PAM .................................................................................. 37 Hình 12: Các bƣớc thực hiện của thuật toán CLARA ............................................................................. 39 Hình 14: Cây CF đƣợc sử dụng bởi thuật toán BIRCH............................................................................ 44 Hình 15 : Các bƣớc thực hiện cơ bản của thuật toán BIRCH .................................................................. 45 Hình 16: Các cụm dữ liệu đƣợc khám phá bởi CURE .............................................................................. 46 Hình 17 : Các bƣớc thực hiện cơ bản của thuật toán CURE .................................................................... 47 Hình 18: Thuật toán DBSCAN .................................................................................................................. 52 Hình 19: Thứ tự phân cụm của các đối tƣợng của OPTICS ..................................................................... 53 Hình 20: DENCLUE với hàm phân phối Gaussian................................................................................... 54 Hình 21: Thuật toán FCM ......................................................................................................................... 62 Hình 22: Mô phỏng về tập dữ liệu đơn chiều ............................................................................................ 62 Hình 23: Hàm thuộc với trọng tâm của cụm A trong k-means ................................................................. 63 Hình 24: Hàm thuộc với trọng tâm của cụm A trong FCM ...................................................................... 63 Hình 25: Các cụm khám phá đƣợc bởi thuật toán phân cụm mờ ............................................................. 64 Hình 26: Thuật toán  FCM ..................................................................................................................... 66 Hình 27: Sự tác động của  trong phân cụm .......................................................................................... 73 t Hình 28: Các bƣớc thực hiện cơ bản của thuật toán k-prototypes ........................................................... 76 Hình 29: Thuật toán k-prototypes chi tiết ................................................................................................. 78 Hình 30: Quá trình hội tụ của thuật toán k-prototypes ............................................................................ 80 3 Phân cụm dữ liệu và ứng dụng trong công tác Tái bảo hiểm DANH SÁCH BẢNG BIỂU Bảng 1: Bảng tham số ................................................................................................................................ 21 Bảng 2: Tổng kết các thuật toán phân cụm .............................................................................................. 58 Bảng 3: Kết quả thực nghiệm của thuật toán  FCM .............................................................................. 68 Bảng 4: Dữ liệu có thuộc tính hỗn hợp ...................................................................................................... 70 Bảng 5: Bảng kết quả thực hiện theo độ lớn của dữ liệu........................................................................... 81 Bảng 6: Bảng kết quả thực hiện số cụm thu đƣợc ..................................................................................... 81 BẢNG TỪ VIẾT TẮT Từ hoặc cụm từ Từ viết tắt Từ tiếng Anh Cơ sở dữ liệu CSDL Database Phân cụm dữ liệu PCDL Data Clustering Công nghệ thông tin CNTT Information Technology Khám phá tri thức KDD Khai phá dữ liệu KPDL Knowledge Discovery in Database Data Mining TỪ KHOÁ Data mining, phân cụm dữ liệu, dữ liệu hỗn hợp, phân cụm mờ, phân cụm song song. 4 Phân cụm dữ liệu và ứng dụng trong công tác Tái bảo hiểm LỜI CẢM ƠN Trƣớc tiên, tôi xin tỏ lòng biết ơn sâu sắc tới thầy giáo PGS.TS Vũ Đức Thi ngƣời hƣớng dẫn khoa học đã chỉ bảo tận tình và truyền thụ cho tôi kiến thức, nguồn cảm hứng nghiên cứu giúp tôi hoàn thành luận văn này. Tôi xin bày tỏ lòng biết ơn đến các thầy giáo trong trƣờng Đại học Công nghệ: TS. Hà Quang Thuỵ, PGS.TS Đỗ Đức Giáo, PGS.TS Trịnh Nhật Tiến, PGS.TS Nguyễn Văn Vị, TS Nguyễn Tuệ, …đã trực tiếp giảng dạy, góp ý chuyên môn, động viên tôi trong suốt khoá học. Cuối cùng tôi xin bày tỏ lòng biết ơn đến gia đình, và các bạn bè đã chia sẻ và động viên tôi hoàn thành luận văn. Học viên Trần Thanh Sơn 5 Phân cụm dữ liệu và ứng dụng trong công tác Tái bảo hiểm MỞ ĐẦU Trong những năm gần đây, dƣới tác động mạnh mẽ của các tiến bộ trong công nghệ phần cứng và truyền thông, các hệ thống dữ liệu phục vụ cho các lĩnh vực kinh tế - xã hội đã phát triển bùng nổ, lƣợng dữ liệu đƣợc tạo ra ngày càng lớn. Sự phong phú về dữ liệu, thông tin cùng với khả năng khai thác một cách tối ƣu đã mang lại cho công tác quản lý, hoạt động kinh doanh,…những hiệu quả thực sự rõ rệt. Cùng với sự phát triển các lĩnh vực hoạt động đó, đặc biệt trong lĩnh vực ra quyết định thì yêu cầu về thông tin, dữ liệu ngày càng đòi hỏi cao hơn, ngƣời quyết định không những cần dữ liệu mà còn cần có thêm nhiều hiểu biết, nhiều tri thức để hỗ trợ cho việc ra quyết định của mình. Cho đến những năm 90 của thế kỷ trƣớc, nhu cầu khám phá tri thức mới thực sự bùng nổ, theo đó hàng loạt các lĩnh vực nghiên cứu về tổ chức các kho dữ liệu và kho thông tin, các hệ trợ giúp quyết định, các thuật toán nhận dạng mẫu và phân lớp mẫu, …và đặc biệt là Khai phá dữ liệu (Data Mining KPDL) ra đời. Từ khi ra đời, KPDL đã trở thành một trong những hƣớng nghiên cứu phổ biến trong lĩnh vực khoa học máy tính và công nghệ tri thức kết hợp với CSDL, thống kê, học máy và những lĩnh vực có liên quan để trích chọn những thông tin giá trị và tri thức hữu ích trong tập hợp dữ liệu lớn. Nhiều kết quả nghiên cứu, ứng dụng của KPDL trong các lĩnh vực khoa học, kinh tế, xã hội. KPDL bao hàm nhiều hƣớng nghiên cứu quan trọng, một trong số đó là phân cụm dữ liệu (Data Clustering PCDL). PCDL là quá trình tìm kiếm và phát hiện ra các cụm hoặc các mẫu dữ liệu tự nhiên trong cơ sở dữ liệu lớn. Các kỹ thuật chính đƣợc áp dụng trong phân cụm dữ liệu phần lớn đƣợc kế thừa từ lĩnh vực thống kê, học máy, nhận dạng, lƣợng hoá, ... Đến nay, đã có nhiều ứng dụng phân cụm dữ liệu cho việc giải quyết các vấn đề trong các lĩnh vực nhƣ tài chính, thông tin địa lý, sinh học, nhận dạng ảnh, …Trong thời gian gần đây, trong lĩnh vực PCDL, ngƣời ta tập trung chủ yếu vào nghiên cứu, phân tích các mô hình dữ liệu phức tạp nhƣ dữ liệu văn bản, Web, hình ảnh,…và đặc biệt là mô hình dữ liệu hỗn hợp để áp dụng chúng trong PCDL. Trong bối cảnh nƣớc ta đang đẩy mạnh phát triển, hội nhập kinh tế với thế giới thì nhu cầu về tự động khám phá tri thức từ các dữ liệu sẵn có nhằm tăng năng 6 Phân cụm dữ liệu và ứng dụng trong công tác Tái bảo hiểm lực cạnh tranh của các ngành kinh tế là cực kỳ cần thiết và cấp bách. Hơn nữa, KPDL là lĩnh vực rộng nên trong luận văn này tôi chọn đề tài nghiên cứu: "Phân cụm dữ liệu và ứng dụng trong công tác Tái bảo hiểm" cho luận văn của mình. Đây là một trong các nội dung quan trọng trong KPDL và là hƣớng nghiên cứu có nhiều triển vọng. Luận văn trình bày một số vấn đề về KPDL và tập trung khảo cứu hệ thống các họ thuật toán PCDL, bao gồm các cách tiếp cận và đặc điểm ứng dụng. Ngoài phần mở đầu và kết luận, cấu trúc nội dung của luận văn bao gồm có 5 chƣơng : Chương 1: trình bày tổng quan về lĩnh vực KPDL và một số khái niệm liên quan, đồng thời chỉ ra các giai đoạn thực hiện trong quá trình khám phá tri thức. Phần tiếp theo của chƣơng là trình bày ngắn gọn, có hệ thống về các kỹ thuật, các dạng dữ liệu thƣờng đƣợc sử dụng trong KPDL. Chương 2: giới thiệu về Phân cụm dữ liệu, đây là một hƣớng tiếp cận chính trong KPDL. Trong đó, đi sâu phân tích chi tiết các vấn đề cơ bản trong PCDL và ý nghĩa của PCDL, đặc điểm của các kiểu dữ liệu cơ bản thƣờng sử dụng trong PCDL nhƣ: dữ liệu có thuộc tính hạng mục (Categorical), dữ liệu có thuộc tính số,… Các khái niệm về “tương tự” và “phi tương tự” cũng đƣợc trình bày trong chƣơng này. Phần cuối của chƣơng trình bày vắn tắt, tổng kết về các đặc trƣng của các phƣơng pháp PCDL đƣợc sử dụng phổ biến nhƣ: Phương pháp phân cụm phân hoạch, phương pháp phân cụm phân cấp, phương pháp phân cụm dựa trên mật độ,…đồng thời nêu các kỹ thuật đánh giá kết quả PCDL. Chương 3: trình bày các phân tích, đánh giá các họ các thuật toán PCDL điển hình và chỉ ra các ƣu điểm, nhƣợc điểm của chúng cũng nhƣ các yêu cầu đặt ra cho việc tạo dụng thuật toán PCDL. Chương 4: trình bày các khảo cứu về áp dụng các kỹ thuật mờ trong PCDL và chứng minh tính hiệu quả của nó trong giải quyết với một lớp bài toán trong PCDL. Nội dung cụ thể của chƣơng này là trình bày về thuật toán FCM, đây là một thuật toán phân cụm mờ dựa trên lƣợc đồ của thuật toán k-means. Thuật toán mở rộng của FCM là  FCM đƣợc đề xuất nhằm khắc phục cho các nhƣợc điểm của thuật toán FCM là nhƣ nhạy cảm với các phần tử nhiễu (noise) và các phần tử ngoại lai trong 7 Phân cụm dữ liệu và ứng dụng trong công tác Tái bảo hiểm dữ liệu (outlier). Phần cuối của chƣơng nêu ra một số các kết quả thực nghiệm cho các thuật toán phân cụm mờ đã trình bày ở trên. Chương 5: trình bày về khảo cứu của thuật toán PCDL k-prototypes áp dụng tập dữ liệu có kiểu hỗn hợp giữa thuộc tính số và thuộc tính hạng mục Phần kết luận, phần này trình bày tóm tắt về các nội dung thực hiện trong luận văn này, đồng thời đƣa ra những vấn đề nghiên cứu tiếp theo cho tƣơng lai. Phần phụ lục trình bày thử nghiệm khai phá dữ liệu “Tái bảo hiểm” bằng phƣơng pháp phân cụm dữ liệu. 8 Phân cụm dữ liệu và ứng dụng trong công tác Tái bảo hiểm CHƢƠNG 1: TỔNG QUAN VỀ DATA MINING 1.1 Giới thiệu chung Những năm 60 của thế kỷ trƣớc, ngƣời ta đã bắt đầu sử dụng các công cụ tin học để tổ chức và khai thác các CSDL. Cùng với sự phát triển vƣợt bậc của các công nghệ điện tử và truyền thông, khả năng thu thập và lƣu trữ và xử lý dữ liệu cho các hệ thống tin học không ngừng đƣợc nâng cao, theo đó, lƣợng thông tin đƣợc lƣu trữ trên các thiết bị nhƣ đĩa từ, băng từ, đĩa CD-ROM,... không ngừng tăng lên. 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 trong 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 những ngƣời điều hành và quản lý có 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 xuất hiện, nhằm tự động khai thác những thông tin, những tri thức có tính tiềm ẩn, hữu ích 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ả khoa học cùng những ứng dụng thành công trong khám phá tri thức, 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ụ 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, điều trị y học, viễn thông, tin - sinh,... 1.2 KPDL là gì? KPDL là một hƣớng nghiên cứu mới ra đời hơn một thập niên trở lại đây, các kỹ thuật chính đƣợc áp dụng trong lĩnh vực này 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. Do sự phát triển nhanh của KPDL về phạm vi áp dụng và các phƣơng pháp tìm kiếm tri thức, nên đã có nhiều quan điểm khác nhau về KPDL. Tuy nhiên, ở một mức trừu tƣợng nhất định, chúng ta định nghĩa KPDL nhƣ sau [11][23]: 9 Phân cụm dữ liệu và ứng dụng trong công tác Tái bảo hiểm Định nghĩa: KPDL là một quá trình tìm kiếm, phát hiện các tri thức mới, tiềm ẩn, hữu dụng trong CSDL lớn. Khám phá tri thức trong CSDL (Knowledge Discovery in Databases - 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 đƣợ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.3 Quá trình khám phá tri thức trong CSDL Khám phá tri thức trong CSDL, KDD, là lĩnh vực liên quan đến các ngành nhƣ: thống kê, học máy, CSDL, thuật toán, trực quan hóa dữ liệu, tính toán song song và hiệu năng cao,… Quá trình KDD có thể phân thành các giai đoạn sau [5][11]:  Trích chọn dữ liệu: 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 (databases, data warehouses, data repositories) ban đầu theo một số tiêu chí nhất định.  Tiền xử lý dữ liệu: là bƣớc làm sạch dữ liệu (xử lý với dữ liệu không đầy đủ, dữ liệu nhiễu, dữ liệu không nhất quán,.v.v.), 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, .v.v.), 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, .v.v.). 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ụ cho các kỹ thuật khai phá ở bƣớc sau.  KPDL: đây là bƣớc áp dụng những kỹ thuật phân tích (phần nhiều là 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 chuyển dạng và biểu diễn ở một 10 Phân cụm dữ liệu và ứng dụng trong công tác Tái bảo hiểm dạng gần gũi với ngƣời sử dụng nhƣ đồ thị, cây, bảng biểu, luật, .v.v. Đồ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. Các giai đoạn trong KDD đƣợc thể hiện trực quan nhƣ hình 1 dƣới đây: Dữ liệu thô Trích chọn dữ liệu Tri thức Dữ liệu Biểu diễn tri thức Tiền xử lý dữ liệu Đánh giá và giải thích Dữ liệu Tiền xử lý Các mẫu Biến đổi dữ liệu Data Mining Hình 1 - Các bƣớc thực hiện trong quá trình khám phá tri thức 1.4 Các kỹ thuật áp dụng trong KPDL 1.4.1 Các kỹ thuật tiếp cận trong KPDL Khám phá tri thức trong CSDL 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ƣ trong hình 2 dƣới đây: Các lĩnh vực khoa học khác Học máy và trí tuệ nhân tạo Tổ chức dữ liệu Hình 2: Các lĩnh vực liên quan đến Khám phá tri thức trong CSDL Nếu đứng trên quan điểm của học máy (Machine Learning), thì các kỹ thuật trong KPDL bao gồm: 11 Phân cụm dữ liệu và ứng dụng trong công tác Tái bảo hiểm  Học có giám sát (Supervised learning): 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 (Unsupervised learning): là quá trình phân chia một tập dữ liệu thành các lớp hay là cụm (clustering) 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 (Semi - Supervised learning): 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à một số 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 [11][23]:  Phân lớp và dự đoán (classification and prediction): xếp một đối tƣợng vào một trong những lớp đã biết trƣớc. Ví dụ: phân lớp các bệnh nhân với dữ liệu 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 (decision tree), mạng nơ ron nhân tạo (neural network), .v.v. Phân lớp và dự đoán còn đƣợc gọi là học có giám sát.  Luật kết hợp (association rules): 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, .v.v.  Phân tích chuỗi theo thời gian (sequential/temporal patterns): 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 (clustering/segmentation): 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 (unsupervised learning).  Mô tả khái niệm (concept description and summarization): thiên về mô tả, tổng hợp và tóm tắt khái niệm. Ví dụ: tóm tắt văn bản. 12 Phân cụm dữ liệu và ứng dụng trong công tác Tái bảo hiểm 1.4.2 Các dạng dữ liệu có thể khai phá 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 [11][23]: CSDL quan hệ, CSDL đa chiều (multidimensional structures, data warehouses), CSDL dạng giao dịch, CSDL 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, CSDL đa phương tiện, dữ liệu Text và Web, … 1.5 Ứng dụng của KPDL 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, Text mining & Web mining, tin-sinh (bio-informatics), tài chính và thị trường chứng khoán, bảo hiểm (insurance), .v.v. 1.6 Phân cụm dữ liệu và ứng dụng Phân cụm dữ liệu nhằm mục đích chính là 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 đó, 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 ra quyết định. Một vài ví dụ về ý nghĩa thực tiễn của phân cụm dữ liệu nhƣ sau: "Khám phá ra các vị trí địa lý thuận lợi cho việc xây dựng các kho hàng phục vụ mua bàn hàng của một công ty thương mại" hoặc "Xác định các cụm ảnh như ảnh của các loài động vật như loài thú, chim,… trong tập CSDL ảnh về động vật nhằm phục vụ cho việc tìm kiếm ảnh" hoặc “xác định các nhóm người bệnh nhằm cung cấp thông tin cho việc phân phối các thuốc điều trị trong y tế ”, hoặc “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 tƣơng tự. Hiện nay, các kỹ thuật phân cụm đã đƣợc ứng dụng rộng rãi trong các ứng dụng nhƣ: nhận dạng mẫu, xử lý ảnh, nghiên cứu thị trƣờng, trực quan hoá,... Trong nội dung tiếp theo, luận văn sẽ đề cập đến vấn đề PCDL, đây là một hƣớng nghiên cứu quan trọng trong lĩnh vực KPDL và là nội dung tìm hiểu, nghiên cứu trọng tâm của luận văn. 13 Phân cụm dữ liệu và ứng dụng trong công tác Tái bảo hiểm CHƢƠNG 2: PHÂN CỤM DỮ LIỆU VÀ CÁC TIẾP CẬN 2.1 Vấn đề phân cụm dữ liệu Phân cụm dữ liệu là một lĩnh vực liên ngành và đang còn đƣợc phát triển mạnh mẽ nhƣ thống kê, học máy, nhận dạng, KPDL, … Ở một mức cơ bản nhất, ngƣời ta đã đƣa ra định nghĩa PCDL nhƣ sau [11][12]: "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 tâm trong tập dữ liệu lớn, từ đó cung cấp thông tin, tri thức hữu ích cho 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ự" (similar) với nhau và các phần tử trong các cụm khác nhau sẽ "phi tƣơng tự" (dissimilar) với nhau. Số các cụm dữ liệu đƣợc 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. Chúng ta có thể minh hoạ vấn đề phân cụm nhƣ hình 3 sau đây: Hình 3: Mô phỏng vấn đề PCDL Trong hình trên, sau khi phân cụm chúng ta thu đƣợc bốn cụm trong đó các phần tử "gần nhau" hay là "tương tự" thì đƣợc xếp vào một cụm, trong khi đó các phần tử "xa nhau" hay là "phi tương tự" thì chúng thuộc về các cụm khác nhau. Trong PCDL khái niệm (Concept Clustering) thì hai hoặc 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 14 Phân cụm dữ liệu và ứng dụng trong công tác Tái bảo hiểm hoặc chúng xấp xỉ với các khái niệm mô tả cho trƣớc, nhƣ vậy, ở đây PCDL không sử dụng khái niệm “tương tự” nhƣ đã trình bày ở trên. Trong học máy, phân cụm dữ liệu đƣợc xem là vấn đề học không có giám sát, vì nó phải đi giải quyết vấn đề tìm một cấu trúc trong tập hợp các dữ liệu chƣa biết biết trƣớc các thông tin về lớp hay các thông tin về tập ví dụ huấn luyện. Trong nhiều trƣờng hợp, khi phân lớp (classification) đƣợc xem vấn đề học có giám sát thì phân cụm dữ liệu là một bƣớc trong phân lớp dữ liệu, trong đó 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" (noise) 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 phân cụm dữ liệu. "Nhiễu" ở đây có thể là các đối tƣợng dữ liệu không không chính xác, hoặc là 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 (outlier) là một trong những hƣớng nghiên cứu quan trọng trong PCDL cũng nhƣ trong KPDL, 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 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 và trong làm sạch dữ liệu, .v.v. Tóm lại, phân cụm là một vấn đề khó, vì rằng ngƣời ta phải đi giải quyết các vấn đề con cơ bản nhƣ sau: 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à các xác lập các điều kiện khởi tạo. 15 Phân cụm dữ liệu và ứng dụng trong công tác Tái bảo hiểm 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, đế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ủa các cụm dữ liệu, với mỗi cách thức biểu diễn khác nhau sẽ có tƣơng ứng một thuật toán phân cụm phù hợp. PCDL đang là vấn đề mở và khó, vì rằng 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 là đối với các 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. 2.2 Các ứ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 ứ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 [11][17]: Thương mại: trong 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: trong 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ị. 16 Phân cụm dữ liệu và ứng dụng trong công tác Tái bảo hiểm 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 và thực vật và đƣa ra đặc trƣng của chúng. Web Mining: 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,… 2.3 Các kiểu dữ liệu và độ đo tƣơng tự Trong phần này chúng 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, cái nhà, 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 đặc tính hay còn gọi là thuộc tính của nó. Các thuộc tính này là các tham số 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 khái niệm 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 (Domain Size) và hệ đo (Measurement Scale) [11][17]. Cho một CSDL D chứa n đối tƣợng trong không gian k chiều trong đó x, y, z là các đối tƣợng thuộc D: x=(x1,x2,..,xk); y=(y1,y2,..,yk); z=(z1,z2,..,zk), trong đó xi, yi, zi với i  1, k là các đặc trƣng hoặc thuộc tính tƣơng ứng của các đối tƣợng x, y, z. Vì vậy, hai khái niệm “các kiểu dữ liệu” và “các kiểu thuộc tính dữ liệu” đƣợc xem là tƣơng đƣơng với nhau, nhƣ vậy, chúng ta sẽ có các kiểu dữ liệu sau: 2.3.1 Phân loại các kiểu dữ liệu dựa trên kích thước miền Thuộc tính liên tục (Continuous Attribute): 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. 17 Phân cụm dữ liệu và ứng dụng trong công tác Tái bảo hiểm Thuộc tính rời rạc (DiscretteAttribute): nếu miền giá trị của nó là tập hữu hạn, đế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, … Lớp các thuộc tính nhị phân là trƣờng hợp đặc biệt của thuộc tính rời rạc mà miền giá trị của nó chỉ có 2 phần tử đƣợc diễn tả nhƣ: Yes/No hoặc Nam/Nữ, False/True,… 2.3.2 Phân loại các kiểu dữ liệu dựa trên hệ đo Giả sử rằng chúng ta có hai đối tƣợng x, y và các thuộc tính x i, 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 (nominal Scale): đây là 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 hoặc thuộc tính các đội bóng chơi cho giải vô địch quốc gia Việt Nam. Thuộc tính có thứ tự (Ordinal Scale): 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 xyi thì ta nói x cách y một khoảng x i – yi tƣơng ứng với thuộc tính thứ i. Một thí dụ về thuộc tính khoảng nhƣ 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ệ (Ratio Scale): 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 điểm 0 làm mốc. 18