Đồ án Thuật toán phân cụm dữ liệu nửa giám sát

m dạy dỗ và giúp đỡ em trong suốt bốn năm học vừa qua và trong quá trình làm tốt nghiệp. Em xin trân trọng cảm ơn thầy Trần Hữu Nghị - Hiệu trưởng trường Đại Học Dân Lập Hải Phòng đã ủng hộ, động viên, và tạo mọi điều kiện tốt nhất để em có thể hoàn thành khoá học tại trường. Cuối cùng em xin gửi lời cảm ơn tới tất cả người thân cùng bạn bè đã động viên, giúp đỡ và đóng góp nhiều ý kiến quý báu cho em trong quá trình học tập cũng như khi làm tốt nghiệp. Hải Phòng, tháng7 năm 2007 Sinh viên Lưu Tuấn Lâm GIỚI THIỆU Trong vài thập niên gần đây, cùng với sự thay đổi và phát triển không ngừng của ngành công nghệ thông tin nói chung và trong các ngành công nghệ phần cứng, phân mềm, truyền thông và hệ thống các dữ liệu phục vụ trong các lĩnh vực kinh tế - xã hội nói riêng. Thì việc thu thập thông tin cũng như nhu cầu lưu trữ thông tin càng ngày càng lớn. Bên cạnh đó việc tin học hoá một cách ồ ạt và nhanh chóng các hoạt động sản xuất, kinh doanh cũng như nhiều lĩnh vực hoạt động khác đã tạo ra cho chúng ta một lượng dữ liệu lưu trữ khổng lồ. Hàng triệu Cơ sở dữ liệu đã được sử dụng trong các hoạt động sản xuất, kinh doanh, quản lí..., trong đó có nhiều Cơ sở dữ liệu cực lớn cỡ Gigabyte, thậm chí là Terabyte. Sự bùng nổ này đã dẫn tới một yêu cầu cấp thiết là cần có những kĩ thuật và công cụ mới để tự động chuyển đổi lượng dữ liệu khổng lồ kia thành các tri thức có ích. Từ đó, các kĩ thuật Khai phá dữ liệu đã trở thành một lĩnh vực thời sự của nền Công nghệ thông tin thế giới hiện nay. Một vấn đề được đặt ra là phải làm sao trích chọn được những thông tin có ý nghĩa từ tập dữ liệu lớn để từ đó có thể giải quyết được các yêu cầu của thực tế như trợ giúp ra quyết định, dự đoán, và Khai phá dữ liệu (Data mining) đã ra đời nhằm giải quyết các yêu cầu đó. Khai phá dữ liệu được định nghĩa là: quá trình trích xuất các thông tin có giá trị tiềm ẩn bên trong lượng lớn dữ liệu được lưu trữ trong các Cơ sở dữ liệu, kho dữ liệu Hiện nay, ngoài thuật ngữ khai phá dữ liệu, người ta còn dùng một số thuật ngữ khác có ý nghĩa tương tự như: khai phá tri thức từ Cơ sở dữ liệu (knowlegde mining from databases), trích lọc dữ liệu (knowlegde extraction), phân tích dữ liệu/mẫu (data/pattern analysis), khảo cổ dữ liệu (data archaeology), nạo vét dữ liệu (data dredging). Nhiều người coi khai phá dữ liệu và một thuật ngữ thông dụng khác là khám phá tri thức trong Cơ sở dữ liệu(Knowlegde Discovery in Databases – KDD) là như nhau. Tuy nhiên trên thực tế, khai phá dữ liệu chỉ là một bước thiết yếu trong quá trình Khám phá tri thức trong Cơ sở dữ liệu. Ngay từ những ngày đầu khi xuất hiện, Data mining đã trở thành một trong những xu hướng nghiên cứu phổ biến trong lĩnh vực học máy và công nghệ tri thức. Nhiều thành tựu nghiên cứu của Data mining đã được áp dụng trong thực tế. Data mining có nhiều hướng quan trọng và một trong các hướng đó là phân cụm dữ liệu (Data Clustering). Phân cụm dữ liệu là quá trính tìm kiếm để phân ra các cụm dữ liệu, các mẫu dữ liệu từ tập Cơ sở dữ liệu lớn. Phân cụm dữ liệu là một phương pháp học không giám sát. Trong những năm trở lại đây, do phương pháp phân cụm dữ liệu không giám sát còn nhiều nhược điểm vì vậy dựa trên học không giám sát và học có giám sát đã ra đời một phương pháp phân cụm dữ liệu mới đó là phương pháp phân cụm dữ liệu nửa giám sát. Phương pháp phân cụm nửa giám sát không phải là một phương pháp phân cụm hoàn thiện nhưng nó đã phần nào khắc phục được những hạn chế và phát huy ưu điểm của phương pháp phân cụm không giám sát. Do những ưu điểm, tầm quan trọng cũng như xu hướng phát triển của khám phá tri thức trong Cơ sở dữ liệu(Knowlegde Discovery in Databases – KDD). Và đây còn là một lĩnh vực mới lạ đồi với em, vì vậy em đã chọn đề tài Phân cụm dữ liệu nửa giám sát làm đề tài tốt nghiệp của mình. Em mong muốn có thể học hỏi và tìm hiểu sâu hơn về kỹ thuật khai phá dữ liệu, từ đó tạo cho bản thân những kiến thức cơ bản để sau này có thể đi sâu nghiên cứu và tìm hiểu về lĩnh vực KDD. Nội dung bài đồ án tốt nghiệp ngoài phần giới thiệu, kết luận, và tìa liệu than khảo gồm có 5 chương : Chương 1 : Giới thiệu tổng quan về Datamining Chương 2 : Giời thiệu về phân cụm dữ liệu và các kỹ thuật tiếp cận trong phân cụm dữ liệu. Chương 3 : Trình bày về một số phương pháp và thuật toán Phân cụm dữ liệu không giám sát Chương 4 : Trình bày một số thuật toán phân cụm dữ liệu nửa giám sát Chương 5 : Bài toán ứng dụng MỤC LỤC TỔNG QUAN VỀ DATA MINING Giới thiệu về khám phá tri thức Kỹ thuật khám phá tri thức trong cơ sở dữ liệu (Knowledge Discovery in Databases- KDD) có thể chia thành các bước thực hiện như sau [1]: Bước 1: Trích chọn dữ liệu: Ở bước này các dữ liệu liên quan trực tiếp đến nhiệm vụ của quá trình KDD sẽ được thu thập từ các nguồn dữ liệu ban đầu. Bước 2: Tiền xử lý dữ liệu: có nhiệm vụ làm sạch, loại bỏ nhiễu, rút gọn và rời rạc hóa dữ liệu. Bước 3: Biến đổi dữ liệu: nhằm chuẩn hóa và làm mịn dữ liệu để chuyển dữ liệu về dạng thuận lợi nhất phục vụ cho việc khai phá. Bước 4: Data mining: dùng các kỹ thuật phân tích để khai thác dữ liệu, trích chọn các mẫu thông tin cần thiết, Công đoạn này được xem là mất thời gian nhất và cũng là quan trọng nhất trong quá trình KDD. Bước 5: Đánh giá và biểu diễn tri thức: Các thông tin và mối liên hệ giữa chúng vừa khám phá trong công đoạn trước được biểu diễn dưới các dạng trực quan đồng thời được đánh giá theo những tiêu chí nhất định. Dữ liệu thô Trích chọn dữ liệu Tiền xử lý dữ liệu Biến đổi dữ liệu Data mining Đánh giá và biểu diễn Tri thức Dữ liệu Dữ liệu tiền xử lý Mẫu Hình 1: Quá trình khám phá tri thức trong CSDL Khai phá dữ liệu và các khái niệm liên quan Khái niệm khai phá dữ liệu Data mining là một quá trình tìm kiếm, chắt lọc các chi thức mới, tiềm ẩn, hữu dụng trong tập dữ liệu lớn. Các kỹ thuật tiếp cận trong khai phá cữ liệu Theo quan điểm của học máy, các kỹ thuật trong Data mining gồm: Học có giám sát (Supervised learning). Học không giám sát (Unsupervised learning). Học nửa giám sát (Semi-Supervised learning). Theo các lớp bài toán cần giải quyết, các kỹ thuật trong Data mining gồm: Phân lớp và dự đoán (Classification and Prediction). Luật kết hợp (Association rules). Phân tích chuỗi theo thời gian. Phân cụm (Clustering). Mô tả khái niệm. PHÂN CỤM DỮ LIỆU VÀ CÁC KỸ THUẬT TIẾP CẬN Khái quát về phân cụm dữ liệu Phân cụm dữ liệu là một kỹ thuật trong Data mining 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 và quan trọng trong tập dữ liệu lớn để từ đó cung cấp thông tin, tri thức cho việc ra quyết định. Các bước của một bài toán phân cụm dữ liệu gồm: 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 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 Các kiểu dữ liệu và độ đo tương tự Kiểu thuộc tính nhị phân: Thuộc tính nhị phân chỉ có hai giá trị là 0 va 1. Trong đó 0 có nghĩa là sai và 1 có nghĩa là đúng y:1 y:0 x: 1 a g a+g x: 0 d q d+q a+d g+q Nếu ta đặt x = a+g+d+q. Với x, y là đối tượng có tất cả thuộc tính đều ở dạng nhị phân.Trong đó a,g,d,q được hiểu như sau: a là tổng số các thuộc tính có giá trị là 1 trong cả hai đối tượng x, y g là tổng số các thuộc tính có giá trị 1 trong x và 0 trong y d là tổng số các thuộc tính có giá trị 0 trong x và 1 trong y q là tổng số các thuộc tính có giá trị là 0 trong cả hai đối tượng x, y Khi đó độ tương tự được cho như sau: Hệ số đối sánh đơn giản: , Ở đây x và y có vai trò như nhau, tức là chúng đối xứng và cùng trọng số. Hệ số Jacard: , công thức này được áp dụng trong trường hợp mà trọng số của các thuộc tính có giá trị 1 lớn hơn rất nhiều các thuộc tính có giá trị 0, như vậy các thuộc tính nhị phân ở đây không đối xứng. Kiểu thuộc tính khoảng (Interval) Dùng để đo các giá trị theo xấp xỉ tuyến tính. Độ đo phi tương tự của x và y được tính bằng các metric khoảng cách sau Khoảng cách Minkowski: Khoảng cách Euclide: , nó là trường hợp của khoảng cách Minkowski với q = 2. Khoảng cách Mahattan, nó là trường hợp của khoảng cách Minkowski với q = 1. Kiểu thuộc tính định danh (Nominal) Độ đo phi tương tự giữa hai đối tượng x và y được xác định qua công thức sau: , 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. Kiểu thuộc tính thứ tự (Ordinal) Độ đo phi tương tự được tính thông qua các bước sau: Gọi f là một thuộc tính, giá trị của f ứng với đối tượng thứ i là xif. Giả sử f có Mf trạng thái có thứ tự: 1,2,,Mf. Ta thay thế mỗi xif bởi giá trị tương ứng rif [1,Mf]. Vì mỗi thuộc tính f có thứ tự có số lượng các trạng thái khác nhau nên ta cần làm cho rif thuộc khoảng [0.0,1.0] để mỗi thuộc tính đều có cùng trọng số. Do đó rif được thay thế bởi Cuối cùng ta sử dụng công thức tính độ phi tương tự của thuộc tính khoảng với zif đại diện cho giá trị thuộc tính f của đối tượng thứ i Kiểu thuộc tính tỷ lệ (Ratio) Đây 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 Có nhiều cách để tính độ tương tự giữa các thuộc tính tỉ lệ. Một trong số đó là việc sử dụng công thức tính logarit để chuyển mỗi thuộc tính tỉ lệ xi về dạng thuộc tính khoảng yi = log(xi). Những kỹ thuật tiếp cận trong phân cụm dữ liệu Các kỹ phân cụm dữ liệu có thể phân loại theo các cách tiếp cận chính sau : Phân cụm phân hoạch Phương pháp phân cụm phân hoạch nhằm 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 dữ liệu 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. 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. Phân cụm dữ liệu 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 “dưới lên” (Bottom up) Phương pháp “trên xuống” (Top Down) Phân cụm dữ liệu 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 đó. Phân cụm dữ liệu dựa trên lưới Kỹ thuật phân cụm dựa trên mật độ không thích hợp với dữ liệu nhiều chiều, để giải quyết cho đòi hỏi này, người ta đã dử dụng phương pháp phân cụm dựa trên lưới. Đây là phương pháp dựa trên cấu trúc dữ liệu lưới để PCDL, phương pháp này chủ yếu tập trung áp dụng cho lớp dữ liệu không gian. Một thí dụ về cấu trúc dữ liệu lưới chứa các cell trong không gian : Phân cụm dữ liệu dựa trên mô hình Phương pháp này cố gắng khám phá các phép xấp xỉ tốt của các tham số mô hình sao cho khớp với dữ liệu một cách tốt nhất. Chúng có thể sử dụng chiến lược phân cụm phân hoạch hoặc chiến lược phân cụm phân cấp, dựa trên cấu trúc hoặc mô hình mà chúng giả định về tập dữ liệu và cách mà chúng tinh chỉnh các mô hình này để nhận dạng ra các phân hoạch. Phân cụm dữ liệu có ràng buộc Sự phát triển của phân cụm dữ liệu không gian trên CSDL lớn đã cung cấp nhiều công cụ tiện lợi cho việc phân tích thông tin địa lý, tuy nhiên hầu hết các thuật toán này cung cấp rất ít cách thức cho người dùng để xác định các ràng buộc trong thế giới thực cần phải được thoả mãn trong quá trình PCDL. PHÂN CỤM DỮ LIỆU KHÔNG GIÁM SÁT Phương pháp phân hoạch Thuật toán K-Means K-Means lặp lại nhiều lần quá trình bố trí lại vị trí của đối tượng dữ liệu để phân hoạch một tập dữ liệu thành K cụm và cực tiểu địa phương giá trị bình phương trung bình khoảng cách giữa các các đối tượng tới tâm cụm của nó. Cụ thể hơn, với tập dữ liệu , thuật toán K-Means tạo ra K phân hoạch của sao cho nếu đại diện cho K tâm thì hàm mục tiêu sau: được cực tiểu địa phương. Thuật toán: K-Means. Input: - Tập các đối tượng dữ liệu - Số lượng cụm: K Output: K phân hoạch tách rời: của sao cho hàm mục tiêu được tối ưu. Các bước: Khởi tạo các cụm: các tâm ban đầu được chọn ngẫu nhiên Lặp cho tới khi hội tụ Gán cụm: Gán mỗi đối tượng dữ liệu x vào cụm h* (tức là tập ) với h* = argmin Ước lượng tâm: t t+1 Thuật toán K-Prototypes Thuật toán k-prototypes mở rộng thuật toán k –means để làm việc với tập dữ liệu hỗn hợp giữa thuộc tính số và thuộc tính hạng mục. Thuật toán k-prototypes sử dụng các đối tượng mẫu (prototype) để biểu diễn cho các cụm thay vì sử dụng các đối tượng trọng tâm như trong thuật toán k-means. Các đối tượng dữ liệu lần lượt được phân phối cho các cụm dữ liệu sao cho chúng tương tự nhất với đối tượng mẫu tương ứng với cụm dữ liệu mà chúng được phân phối, sự tương tự ở đây được xác định bằng độ đo tương tự cho dữ liệu hỗn hợp. Thuật toán k- prototypes Input : Tập dữ liệu ban đầu X và số cụm k, Output : k đối tượng mẫu sao cho hàm tiêu chuẩn đạt giá trị tối thiểu Begin Khởi tạo k đối tượng mẫu ban đầu cho X, mỗi đối tượng mẫu đóng vai trò là tâm đại diện của mỗi cụm. Phân phối mỗi đối tượng trong X cho mỗi cụm sao cho chúng gần nhất với đối tượng mẫu trong cụm, đồng thời cập nhật lại đối tượng mẫu cho mỗi cụm. Sau khi tất cả các đối tượng đã được phân phối hết cho các cụm, kiểm tra lại độ tương tự của các đối tượng trong mỗi cụm với các đối tượng mẫu, nếu có một đối mẫu tương tự nhất với nó mà khác với đối tượng mẫu của cụm hiện thời thì di chuyển đối tượng đang xét này sang cụm tương ứng với đối tượng mẫu mà nó gần nhất và đồng thời cập nhật các đối tượng mẫu cho hai cụm này. Lặp bước 3 cho đến khi không có đối tượng nào thay đối sau khi đã kiểm tra toàn bộ các đối tượng. End. Thuật toán k-tâm Thuật toán k-tâm mở rộng thuật toán k –means để làm việc với tập dữ liệu hỗn hợp gồm: thuộc tính số, thuộc tính định danh và thuộc tính có thứ tự. Độ đo tương tự Giả sử DOM(Aj) là miền giá trị của thuộc tính Aj ta có các khái niệm: Thuộc tính đinh danh: Aj được gọi là thuộc tính định danh nếu DOM(Aj) là tập không có thứ tự tức là "a,b Î DOM(Aj) hoặc a=b hay a¹b. Thuộc tính số: Aj là thuộc tính số nếu DOM(Aj) là tập số thực. Thuộc tính có thứ tự: nếu DOM(Aj) là tập hữu hạn và có thứ tự hoàn toàn. Công thức tính khoảng cách giữa hai đối tượng Giả sử ta có x,yÎDOM(Aj), hàm dj(x,y) được xác định như sau: Nếu Aj là thuộc tính số thì dj được dj(x,y)=úx-yú (9) Nếu Aj là thuộc tính thứ tự và DOM(Aj) = với , ta lấy một hàm đơn điệu fj:DOM(Aj)→ [0,1] sao cho (Hàm này có thể là : ) . Khi đó dj(x,y)= │fj(x)-fj(y) │. (10) Nếu Aj là dữ liệu định danh thì dj(x,y)= (11) Vậy khoảng cách d(x,y) giữa hai đối tượng x = (x1,...,xn) và y = (y1,...,yn) được tính bởi công thức: (12) trong đó các dj(xj,yj) được tính theo các công thức (9-11) và rj là các trọng số dương cho bởi các chuyên gia. Với định nghĩa trên, ta luôn có thể xem các thuộc tính thứ tự có miền giá trị là đoạn [0,1] (các giá trị trên thuộc tính này của D là tập con) và nó cũng được xem là thuộc tính số khi không xảy ra nhầm lẫn. Tìm mode của tập dữ liệu Định lý : Nếu xem miền giá trị của các thuộc tính có thứ tự là đoạn [0,1] và mode của tập hợp xác định như đã nói ở trên thì với mọi tập dữ liệu hỗn hợp C , mode(C) cực tiểu hàm: E(x)= (13). trong đó x là phần tử của quan hệ r trên lược đồ quan hệ R={A1,...,An}. Thuật toán K-Tâm Thuật toán k-tâm phân cụm dữ liệu hỗn hợp là mở rộng thuật toán k-mean. Thuật toán được đặc tả như sau: Proceduce k-tâm Begin Chọn các trọng số , các hàm fj ,xác định k. Chọn k phần tử ban đầu của D làm tâm các cụm Xếp mỗi x D vào cụm Cj mà nó gần tâm nhất; For j=1,...,k do ; Repeat Phân bố lại cụm theo tâm mới// như k-mean; Cập nhật lại tâm cho các cụm // nhờ tính mode Until các cụm không đổi; Xác định các cụm End Đặc tả thủ tục k-tâm Nhận xét Khi thuật toán kết thúc, các đối tượng tâm có thể không thuộc tập X. Để tìm phần tử đại diện cho mỗi cụm, ta lấy phần tử thuộc cụm gần với tâm của nó nhất. PHÂN CỤM DỮ LIỆU NỬA GIÁM SÁT Phân cụm nửa giám sát là phương pháp sử dụng các thông tin bổ trợ để hướng dẫn cho quá trình phân cụm. Các thông tin bổ trợ có thể được cho dưới dạng tập các cặp ràng buộc hoặc một tập nhỏ một số dữ liệu được dán nhãn. Công việc xác định những tập ràng buộc hay những tập dữ liệu được dán nhãn được thực hiện bởi người phân cụm. Sau đây là một số thuật toán phân cụm dựa vào tập dữ liệu được dán nhãn. Thuật toán Seeded-KMeans Thuật toán Seeded-KMeans sử dụng các cụm giống Sh để khởi tạo cho thuật toán K-Means. Do vậy thay vì phải khởi tạo K cụm ngẫu nhiên chúng ta khởi tạo K cụm từ tập giống. Với tập giống là những phần tử đã được dán nhãn, do người thực hiện phân cụm xác định từ kinh nghiệm hoặc từ những tiêu chuẩn cụ thể đối với từng mục đích phân cụm. Thuật toán: Seeded-KMeans. Input: - Tập các đối tượng dữ liệu Số lượng cụm: K Tập giống Output: K phân hoạch tách rời: của sao cho hàm mục tiêu được tối ưu. Các bước: Khởi tạo các cụm: , với h = 1,...K; t¬0. 2 Lặp cho tới khi hội tụ 2.1 Gán cụm: Gán mỗi đối tượng dữ liệu x vào cụm h* (tức là tập ) với h* = argmin 2.2 Ước lượng tâm: t t+1 Thuật toán Constrained-KMeans Thuật toán Constrained-KMeans dùng các cụm giống như những ràng buộc để dẫn dắt quá trình phân cụm của K-Means. Nhưng trong các bước sau, mọi đối tượng thuộc tập giống S không được bố trí lại, mà chỉ có các đối tượng không thuộc tập giống mới được bố trí lại. Thuật toán: Constrained-KMeans. Input: - Tập các đối tượng dữ liệu Số lượng cụm: K Tập giống Output: K phân hoạch tách rời: của sao cho hàm mục tiêu được tối ưu. Các bước: Khởi tạo các cụm: , với h = 1,...K; t¬0. 2 Lặp cho tới khi hội tụ 2.1 Gán cụm: - Với mỗi , nếu thì gán x vào cụm h -Với mỗi gán x vào cụm h* , với h* = argmin 2.2 Ước lượng tâm: t t+1 * Nhận xét Các Thuật toán dựa trên tập giống Seeded-KMeans, Constrained-KMeans do Basu đề xuất vào năm 2002 và COP-KMeans do Wagstaff đề xuất năm 2001 là các thuật toán điển hình hiện nay về phân cụm nửa giám sát. Các thông tin bổ trợ đều do người dùng cung cấp. Vậy phân cụm nửa giám sát thực chất là quá trình kết hợp giữa người và máy để làm tăng chất lượng phân cụm. BÀI TOÁN ỨNG DỤNG Bài toán nhằm giải quyết vấn đề phân cụm dữ liệu với một cơ sở dữ liệu của một công ty kinh doanh bảo hiểm, nhằm đưa ra các nhóm hợp đồng boả hiểm của khách hàng có sự giống nhau là lớn nhất. Vấn đề đặt ra ở đây là số lượng hợp đồng bảo hiểm là rất lớn việc xác định mức độ rủi ro cho từng hợp đồng bảo hiểm mất rất nhiều thời gian vì không phải ai cũng có thể đánh giá được mức độ rủi ro từ những thông tin của khách hàng trong hợp đồng. Vì vậy cần đưa ra các mẫu để trợ giúp những nhân viên ít kinh nghiệm có thể xác định mức độ rủi ro cho từng hợp đồng bảo hiểm. Bước đầu phân loại các mức độ rủi ro cho các hợp đồng bảo hiểm. Việc xác định tính đúng đắn của nó cần có chuyên gia đánh giá lại, nhưng như vậy đã giảm đi rất nhiều công việc cho các chuyên gia. Bên cạnh đó còn giúp các nhân viên tư vấn khách hàng hướng khách hàng đến những sản phẩm bảo hiểm phù hợp với điều kiện của họ. Rủi ro hợp đồng bảo hiểm của khách hàng có nhiều mức, để xác định mức độ rủi ro của các hợp đồng bảo hiểm phải dựa trên nhiều thông tin: độ tuổi thu nhập, nghề nghiệp, tình trạng sức khỏe, và cả những thông tin về người thân của người tham gia bảo hiểm như có bệnh gì không, những thông tin này cũng rất quan trọng vì có một số bệnh nghiêm có tính di truyền và khả năng mắc bệnh của người tham gia bảo hiểm là có thể xảy ra. Bài toán Input: Tập n các hồ sơ mua bảo hiểm, gồm các thông tin về khách hàng mua và được bảo hiểm và các thông tin về việc mua bảo hiểm của khách hàng. Các thông tin này được coi là một tập dữ liệu hỗn hợp có các thuộc tính số thuộc tính thứ tự, và thuộc tính định danh. K mức độ rủi ro từ các thông tin khách hàng cung cấp theo ý kiến của các chuyên gia có kinh nghiệm. Output: Đưa ra k nhóm khách hàng có sự giống nhau là lớn nhất và dựa theo sự đánh giá của các chuyên gia để có thể đưa ra các mẫu khách hàng với các mức độ rủi ro tương ứng. Bảng sau gồm các thuộc tính dùng để đánh giá các mức độ rủi ro: Số TT Tên thuộc tính Kiểu thuộc tính Các giá trị có thể 1 Tuồi của người được bảo hiểm Số 1¸60 2 Nghề nghiệp của người được bảo hiểm Định danh 3 Loại nghề nghiệp của người được bảo hiểm Thứ tự 1: An toàn 2:Bình thường 3: Hơi nguy hiểm 4: Nguy hiểm 4 Thu nhập của người được bảo hiểm Số 5 Quan hệ với người được bảo hiểm Định danh 6 Bệnh của người được bảo hiểm Định danh 7 Tuồi của người mua bảo hiểm Số 1¸60 8 Nghề nghiệp của người mua bảo hiểm Định danh 9 Loại nghề nghiệp của người mua bảo hiểm Thứ tự 1: An toàn 2:Bình thường 3: Hơi nguy hiểm 4: Nguy hiểm 10 Thu nhập gia đình của người mua bảo hiểm Số 11 Bệnh của người mua bảo hiểm Định danh 12 Tên bảo hiểm đăng kí mua Định danh 13 Số tiền mua bảo hiểm Số 14 Số năm mua bảo hiểm Số 5¸60 (tùy từng bảo hiểm) Vì thuộc tính bệnh của khách thì có rất nhiều các bệnh khách nhau do đó trong chương trình ứng dụng để đơn giản em chuyển thuộc tính bệnh thành các cấp độ tình trạng của sức khỏe từ 1 đến 10 theo cấp độ nguy hiểm tăng dần 1: Hoàn toàn khỏe mạnh và tăng dần đến 10 là các bệnh nghiêm trọng ung thư, tiểu đường, bệnh về tim mạch. Với cấp độ 10 khách hàng sẽ khó có cơ hội mua bảo hiểm hoặc được mua nhưng với phí sẽ rất cao. Do đó thuộc tính bệnh sẽ được coi như thuộc tính có thứ tự trong chương trình ứng dụng Tương tự như vậy với thuộc tính nghề nghiệp, em xin bỏ thuộc tính nghề nghiệp, thay vào đó sẽ xét theo mức độ nguy hiểm của nghề nghiệp theo thuộc tính loại nghề nghiệp. Giao diện chương trình Giao diện khởi động Một số giao diện cập nhập Giao diện Phân cụm dữ liệu Cập nhập số cụm K Cập nhập tập giống Phân cụm dữ liệu Kết quả phân cụm KẾT LUẬN Data mining là một trong những lĩnh vực nghiên cứ mới, nhưng đồng thời nó cũng là một trong những xu hướng nghiên cứu ngày càng phổ biến. Do nhu cầu của thực tế, với sự phát triển của công nghệ máy tính, của các lĩnh vực kinh tế - xã hôi thì lượng thông tin lưu trữ ngày càng tăng, và nhu cầu khai thác thông tin, tri thức ngày càng lớn. Do đó việc đọc, nghiên cứu và phát triển phương pháp phân cụm dữ liệu đóng một vai trò rất quan trọng trong hoạt động của khoa học công nghệ máy tính, cũng như trong hoạt động thực tiễn. Trong bài báo cáo này tôi đã nêu lên những nét đặc trưng nhất trong lĩnh vực Data Mining bao gồm các vấn đề cần khám phá tri thức, các hướng tiếp cận nghiên cứu tiêu biểu, trong đó phân cụm dữ liệu là một phương pháp khám phá tri thức quan trọng trong Data Mining có nhiều ý nghĩa trong khoa học cũng như thực tiễn. Trong đó phân cụm dữ liệu nửa giám sát là một trong những hướng nghiên cứu mới được nhiều nhà khoa học quan tâm. Bài báo cáo đã nêu được một cách khái quát về data mining và phương pháp phân cụm không giám sát, từ đó phân tích chi tiết về phân cụm nửa giám sát. Trình bày ba thuật toán điển hình của phân cụm nửa giám sát đó là : COP-KMeans, Seeded-KMeans, Constrained-KMeans và trình bày thuật toán KMeans phân cấp mới được đề xuất của hai tác giả Việt Nam là : Hoàng Xuân Huấn và Nguyễn Trung Thông. Tóm lại phân cụm dữ liệu nói chung và phân cụm nửa hiám sát nói riêng đang ngày càng được quan tâm ở nước ta và trên thế giới. Ngày càng có nhiều thuật toán và tư tưởng mới về phân cụm dữ liệu ra đời. Phân cụm dữ liệu đã từng bước chứng minh được tầm quan trong cũng như vài trò của mình trong sự phát triển của công nghệ máy tính nói riêng và phát triển của thế giới nói chung. Trong quá trình thực tập do thời gian thưc tập và trình độ còn nhiều hạn chế lên chưa thể tìm hiểu chi tiết hơn về Phân cụm nửa giám sát. Tôi mong nhận được sự chỉ bảo của thầy cô và sự góp ý của bạn bè. TÀI LIỆU THAM KHẢO [1] Nguyễn Trung Thông. Phương pháp phân cụm nửa giám sát [ 2 ] KS. Nguyễn Anh Trung - Trung tâm Công nghệ Thông tin. Ứng dụng các kỹ thuật khai phá dữ liệu vào lĩnh vực viễn thông [3] Hoàng Hải Xanh – K9 đại học công nghệ - ĐHQGHN (Luận văn thạc sĩ) Một số kỹ thuật phân cụm dữ liệu trong Data Mining. [4] Hoàng Xuân Huấn, Nguyễn Thị Xuân Hương. Mở rộng thuật toán phân cụm k-mean cho dữ liệu hỗn hợp. Một số vấn đề chọn lọc của công nghệ thông tin, Hải phòng 25-27 tháng 8 năm 2005. [5] Basu, S., Banerjee, A., & Mooney, R. J. (2002). Semi-supervised clustering by seeding. In Proceedings of 19th International Conference on Machine Learning (ICML-2002), pp. 19–26. [6] Basu, S., Banerjee, A., & Mooney, R. J. (2003). Active semi-supervision for pairwise constrained clustering. Submitted for publication, available at ˜sugato/. [7] Basu Sugato (2004) Semi-supervised Clustering with Limited Background Knowledge. Proceedings of the Ninth AAAI/SIGART Doctoral Consortium, pp. 979-980, San Jose, CA, July 2004. [8] Blake, C. L., & Merz, C. J. (1998). UCI repository of machine learning databases. ˜mlearn/