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

Đồ án tốt nghiệp Đại học hệ chính quy Thuật toán Phân cụm dữ liệu nửa giám sát LỜI CẢM ƠN Trước hết, em xin chân thành gửi lời cảm ơn sâu sắc đến cô giáo ThS.Nguyễn Thị Xuân Hƣơng , người đã tận tình hướng dẫn và tạo mọi điều kiện cho em trong quá trình làm tốt nghiệp. Em xin chân thành cảm ơn các thầy cô giáo trong khoa Công Nghệ Thông Tin Trường Đại Học Dân Lập Hải Phòng đã quan 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 châ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 4 năm đại học vừa qua. Cuối cùng em xin gửi lời cảm ơn chân thành tới tất cả những 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 Lưu Tuấn Lâm – CT702 1 Đồ án tốt nghiệp Đại học hệ chính quy Thuật toán Phân cụm dữ liệu nửa giám sát MỤC ĐÍCH CỦA ĐỀ TÀI Công việc đọc và tìm hiểu đề tài nhằm những muc đích sau đây:  Tìm hiểu qua về khai phá dữ liệu (Data mining).  Tìm hiểu qua về một số thuật toán phân cụm dữ liệu không giám sát  Trên lền tảng lý thuyết về khai phá dữ liệu và một số thuật toán phân cụm không giám sát tiến tới đi sâu vào tìm hiểu, phân tích, đánh giá một số thuật toán của phương pháp phân cụm dữ liệu nửa giám sát.( Thuật toán Seeded-Kmeans và Constrained-Kmeans)  Xây dựng một chương trình demo, mô phỏng hoạt động của phương pháp phân cụm dữ liệu nửa giám sát. Lưu Tuấn Lâm – CT702 2 Đồ án tốt nghiệp Đại học hệ chính quy Thuật toán Phân cụm dữ liệu nửa giám sát 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 tính 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. Lưu Tuấn Lâm – CT702 3 Đồ án tốt nghiệp Đại học hệ chính quy Thuật toán Phân cụm dữ liệu nửa giám sát MỤC LỤC LỜI CẢM ƠN ..................................................................................................................... 1 MỤC ĐÍCH CỦA ĐỀ TÀI ................................................................................................. 2 GIỚI THIỆU ....................................................................................................................... 3 Chƣơng 1 : TỔNG QUAN VỀ DATA MINING ............................................................. 6 1.1 Giới thiệu về khám phá tri thức.............................................................................. 6 1.2 Khai phá dữ liệu và các khái niệm liên quan ........................................................ 7 1.2.1 Khái niệm khai phá dữ liệu .................................................................................. 7 1.2.2 Các kỹ thuật tiếp cận trong khai phá cữ liệu ........................................................ 8 Chƣơng 2 : PHÂN CỤM DỮ LIỆU VÀ CÁC TIẾP CẬN ............................................. 9 2.1 Khái quát về phân cụm dữ liệu ............................................................................... 9 2.2 Các kiểu dữ liệu và độ đo tƣơng tự ...................................................................... 10 2.3 Những kỹ thuật tiếp cận trong phân cụm dữ liệu ............................................... 13 2.3.1 Phân cụm phân hoạch ........................................................................................ 13 2.3.2 Phân cụm dữ liệu phân cấp ............................................................................... 13 2.3.3 Phân cụm dữ liệu dựa trên mật độ ..................................................................... 14 2.3.4 Phân cụm dữ liệu dựa trên lưới .......................................................................... 15 2.3.5 Phân cụm dữ liệu dựa trên mô hình ................................................................... 16 2.3.6 Phân cụm dữ liệu có ràng buộc ......................................................................... 16 2.4 Một số ứng dụng của phân cụm dữ liệu ............................................................... 17 Chƣơng 3 : PHÂN CỤM DỮ LIỆU KHÔNG GIÁM SÁT ......................................... 19 3.1 Phƣơng pháp phân hoạch ...................................................................................... 19 3.1.1 Thuật toán K-Means........................................................................................... 19 3.1.2 Thuật toán K-Medoids ....................................................................................... 20 3.2 Phƣơng pháp phân cấp .......................................................................................... 21 3.2.1 Thuật toán CURE ............................................................................................... 22 3.2.2 Thuật toán BIRCH ............................................................................................. 23 3.3 Thuật toán k-tâm: .................................................................................................. 25 3.3.1 Cơ sở toán học của thuật toán k-tâm .................................................................. 25 3.3.2 Các đối tượng có kiểu hỗn hợp .......................................................................... 25 3.3.3 Độ đo tương tự ................................................................................................... 26 3.3.4 Công thức tính khoảng cách giữa hai đối tượng ................................................ 26 3.3.5 Thuật toán K-Tâm .............................................................................................. 27 Chƣơng 4 : PHÂN CỤM DỮ LIỆU NỬA GIÁM SÁT ................................................. 29 4.1 Thuật toán COP-KMeans...................................................................................... 29 4.2 Phân cụm nửa giám sát dựa trên tập tập dữ liệu đƣợc dán nhãn ..................... 30 4.2.1 Thuật toán Seeded-KMeans ............................................................................... 31 4.2.2 Thuật toán Constrained-KMeans ....................................................................... 32 4.3 Thuật toán K-Means phân cấp ............................................................................. 33 Chƣơng 5 : GIỚI THIỆU VỀ NGÔN NGỮ VB 6.0 ...................................................... 37 5.1 Cấu trúc một đề án (Project)................................................................................. 37 5.2 Một số các điều khiển ............................................................................................. 38 5.3 Mô hình truy cập cơ sở dữ liệu bằng ADO .......................................................... 38 5.4 Trình thiết kế môi trƣờng dữ liệu ( Data Environment ) ................................... 40 5.5 Các phƣơng thức của Recordset trong Command ............................................. 41 Chƣơng 6 : BÀI TOÁN ỨNG DỤNG ............................................................................. 43 Lưu Tuấn Lâm – CT702 4 Đồ án tốt nghiệp Đại học hệ chính quy Thuật toán Phân cụm dữ liệu nửa giám sát 6.1 Bài toán ................................................................................................................... 44 6.2 Các thông tin về các loại bảo hiểm nhân thọ ....................................................... 46 6.3 Cài đặt thuật toán Phân cụm nửa giám sát vời dữ liệu hốn hợp ....................... 47 6.4 Các hàm thủ tục chính khi thực hiện thuật toán ................................................ 48 6.4.1 Hàm khởi tạo tâm từ Tập giống ......................................................................... 48 6.4.2 Các hàm tính khoảng cách ................................................................................. 49 6.4.3 thuật toán Constrained-Kmeans ......................................................................... 51 6.5 Giao diện chƣơng trình .......................................................................................... 55 KẾT LUẬN ....................................................................................................................... 60 Tài liệu tham khảo ............................................................................................................ 61 Lưu Tuấn Lâm – CT702 5 Đồ án tốt nghiệp Đại học hệ chính quy Thuật toán Phân cụm dữ liệu nửa giám sát Chương 1 : TỔNG QUAN VỀ DATA MINING 1.1 Giới thiệu về khám phá tri thức Trong vài chục năm gần đây cùng với sự phát triển mạnh mẽ của kỹ thuật công nghệ cũng như nhu cầu lưu trữ thông tin dẫn đến trữ lượng dữ liệu được lưu trữ không ngừng tăng theo. Những cơ sở dữ liệu rất lớn ra đời, có những cơ sở dữ liệu lên đến cỡ Gigabyte và thậm chí cả Terabyte. Nếu bạn có trong tay một kho cơ sở dữ liệu cũng có nghĩa bạn có trong tay một kho tri thức.Nhưng vấn đề đặt ra là làm thế nào bạn có thể trích lọc được những thông tin, tri thức từ một kho dữ liệu với rất nhiều thông tin về các lĩnh vực khác nhau. Để giải quyết vấn đề đó thì kỹ thuật khám phá tri thức trong cơ sở dữ liệu (Knowledge Discovery in Databases- KDD) đã ra đời.Khám phá tri thức trong cơ sở dữ liệu (KDD) là lĩnh vực liên quan đến các ngành như: xác suất thống kê, học máy, trực quan hóa dữ liệu, tính toán song song,…Trong đó quá trình 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. Lưu Tuấn Lâm – CT702 6 Đồ án tốt nghiệp Đại học hệ chính quy Thuật toán Phân cụm dữ liệu nửa giám sát Dữ liệu thô Tri thức Trích chọn dữ liệu Đánh giá và biểu diễn Dữ liệu Mẫu Tiền xử lý dữ liệu Dữ liệu tiền xử lý Biến đổi dữ liệu Data mining Hình 1: Quá trình khám phá tri thức trong CSDL 1.2 Khai phá dữ liệu và các khái niệm liên quan Data mning là một công đoạn trong quá trình khám phá tri thức trong cơ sở dữ liệu. Và Data mining cũng là một khâu quan trọng nhất trong quá trình khám phá tri thức trong cơ sở dữ liệu. Nhiệm vụ của Data mining là khai thác thông tin, tri thức có tính tiềm ẩn và hữu ích trong tập Cơ sở dữ liệu lớn nhằm cung cấp thông tin cần thiết cho các lĩnh vực sản xuất, khinh doanh, và nghiên cứu,… Các kết quả nghiên cứu cùng với những ứng dụng thành công của việc khai phá tri thức cho thấy Data mining là một lĩnh vực đầy tiềm năng và bền vững. Data mining đã giả được bài toàn khó đó là làm thế nào để có thể trích lọc được các thông tin, tri thức hữu ích từ một tập Cơ sở dữ liệu lớn. và khẳng định sự ưu việt của mình so với các công cụ phân tích dữu liệu truyền thông. Hiện nay, Data mining đã được ứng dụng ngày càng rộng dãi trong nhiều 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,… Khi đọc đến đây bạn có thể nhầm lẫn rằng hai khái niệm Data mining và khám phá tri thức trong cơ sở dữ liệu (KDD) là như nhau. Nhưng thực ra KDD là mục tiêu của Data mining. Và Data mining là một bước quan trọng và mang tính quyết định của quá trình KDD. 1.2.1 Khái niệm khai phá dữ liệu Do sự phát triển mạnh mẽ của Data mining về phạm vi các lĩnh vực ứng dụng trong thực tế và các phương pháp tìm kiếm lên có rất nhiều khài niệm khác nhau về Data mining. Ở đây em xin nêu ra một định nghĩa gắn gọn và dễ hiểu về Data mining như sau [1]: 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. Lưu Tuấn Lâm – CT702 7 Đồ án tốt nghiệp Đại học hệ chính quy Thuật toán Phân cụm dữ liệu nửa giám sát 1.2.2 Các kỹ thuật tiếp cận trong khai phá cữ liệu Các kỹ thuật áp dụng trong Data mining phần lớn được kế thừa từ các lĩnh vực như: Cơ sở dữ liệu (Database), Học máy (Machine learning), Trí tuệ nhân tạo, Xác suất thống kê,… vì vậy ta có hai hướng tiếp cận sau đây: 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): Là quá trình gán nhãn lớp cho các đối tượng trong tập dữ liệu dựa trên một bộ các đối tượng huấn luyện và các thông tin về nhãn lớp đã biết.  Học không 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 cụm (cluster) dữ liệu tương tự nhau mà chưa biết trước các thông tin về nhãn lớp.  Học nửa giám sát (Semi-Supervised learning): Là quá trình chia một tập dữ liệu thành các lớp con dựa trên một số thông tin bổ trợ cho trước. 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): đưa một đối tượng vào một trong các lớp đã biết trước. 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. Một luật kết hợp được mô tả như sau: Nếu a thì b với xác suất p  Phân tích chuỗi theo thời gian: giống như khai phá luật kết hợp nhưng có thêm tính thứ tự và thời gian  Phân cụm (Clustering): Nhóm các đối tượng thành từng cụm dữ liệu. Đây là phương pháp học không giám sát.  Mô tả khái niệm: 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. Lưu Tuấn Lâm – CT702 8 Đồ án tốt nghiệp Đại học hệ chính quy Thuật toán Phân cụm dữ liệu nửa giám sát Chương 2 : PHÂN CỤM DỮ LIỆU VÀ CÁC TIẾP CẬN 2.1 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 phát triển mạnh mẽ trong nhiều năm trở lại đây do các ứng dụng và lợi ích to lớn của nó trong các lĩnh vực trong thực tế. Ở một mức cơ bản nhất người ta định nghĩa phân cụm dữ liệu như sau [1]: 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. Do đó, phân cụm dữ liệu 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 đối tượng trong một cụm thì “tương tự” nhau và các đối tượng trong các cụm khác nhau thì “phi tương tự” với nhau. Số cụm dữ liệu được xác định bằng kinh nghiệm hoặc bằng một số phương pháp phân cụm. Sau khi xác định các đặc tính của dữ liệu, người ta đi tìm cách thích hợp để xác định "khoảng cách" giữa các đối tượng, hay là phép đo tương tự dữ liệu. Đây chính 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ự (Similar) hoặc là tính độ phi tương tự (Dissimilar) 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ự. Trong quá trình phân cụm dữ liệu thì vấn đề trở ngại lớn nhất đó là nhiễu (noise). Nhiễu xuất hiện do trong quá trình thu thấp thông tin, dữ liệu thiếu chính xác hoặc không đầy đủ. Vì vậy chúng ta cần phải khử nhiễu trong quá trình tiến hành phân cụm dữ liệu. 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 Lưu Tuấn Lâm – CT702 9 Đồ án tốt nghiệp Đại học hệ chính quy Thuật toán Phân cụm dữ liệu nửa giám sát 2.2 Các kiểu dữ liệu và độ đo tƣơng tự Sau đây là các kiểu của dữ liệu, và ứng với mỗi kiểu dữ liệu thì có một hàm tính độ đo tương tự để xác định khoảng cách giữa 2 phân tử của cùng một kiểu dữ liệu. Tất cả các độ đo đều được xác định trong không gian metric. Bất kỳ một metric nào cũng là một độ đo nhưng ngược lại thì không đúng. Độ đo ở đây có thể là tương tự hoặc phi tương tự. Một tập dữ liệu X là không gian metric nếu:  với mỗi cặp x,y thuộc X đều xác định được một số thực d(x,y) theo một quy tắc nào đó và được gọi là khoảng cách của x,y.  Quy tắc đó phải thoả mãn các tính chất sau: a) d(x,y) > 0 nếu x ≠ y b) d(x,y) = 0 nếu x = y c) d(x,y) = d(y,x) d) d(x,y) <= d(x,z) + d(z,y) Sau đây là các kiểu thuộc tính dữ liệu phổ biến :  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   + x: 0   + + + Ví du: thuộc tính hút thuốc của bệnh lao phổi, 0 sẽ ứng vơi bệnh nhân không hút thuốc, 1 sẽ ứng với bệnh nhân có hút thuốc. Nếu ta đặt  = +++. Với x, y là đối tượng có tất cả thuộc tính đều ở dạng nhị phân.Trong đó ,,, được hiểu như 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ưu Tuấn Lâm – CT702 10 Đồ án tốt nghiệp Đại học hệ chính quy Thuật toán Phân cụm dữ liệu nửa giám sát  là tổng số các thuộc tính có giá trị 1 trong x và 0 trong y  là tổng số các thuộc tính có giá trị 0 trong x và 1 trong y  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: 1. Hệ số đối sánh đơn giản: d ( x, y )    , Ở đây x và y có vai  trò như nhau, tức là chúng đối xứng và cùng trọng số. 2. Hệ số Jacard: d ( x, y)   , 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, với thuộc tính khoảng ta có thể xác định một thuộc tính đướng trước hoặc đứng sau một thuộc tính khác với khoảng là bao nhiêu. Nếu xi > yi thì ta nói x cách y một khoảng là xi-yi ứng với thuộc tính thứ i. Độ đo phi tương tự của x và y được tính bằng các metric khoảng cách sau n 1. Khoảng cách Minkowski: d ( x, y)  ( xi  yi )1/ q , q  N * q i 1 n 2. Khoảng cách Euclide: d ( x, y)  ( xi  yi )1/ 2 , nó là trường 2 i 1 hợp của khoảng cách Minkowski với q = 2. n 3. Khoảng cách Mahattan d ( x, y)  ( xi  yi ) , nó là trường hợp i 1 của khoảng cách Minkowski với q = 1.  Kiểu thuộc tính định danh (Nominal) Đây là dạng tổng quat 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ự. Nếu x và y là hai thuộc tính định danh thì ta có thể xác định x = y hoặc x ≠ y Lưu Tuấn Lâm – CT702 11 Đồ án tốt nghiệp Đại học hệ chính quy Thuật toán Phân cụm dữ liệu nửa giám sát Ví dụ: thuộc tính nơi sinh, quê quán của một sinh viên trong cơ sở dữ liệu sinh viên. Độ đo phi tương tự giữa hai đối tượng x và y được xác định qua công thức sau: d ( x, y )  pm , trong đó m là số thuộc tính đối sánh tương ứng trùng nhau p và p là tổng số các thuộc tính.  Kiểu thuộc tính thứ tự (Ordinal) Là thuộc tính định danh có 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 có thứ tự thì ta có thể xác định x = y hoặc x ≠ y hoặc x > y hoặc x < y. Ví dụ : thuộc tính xếp hạng kết quả thi đấu của một cuộc đua ôtô. Độ đo phi tương tự được tính thông qua các bước sau: 1. 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]. 2. 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 zif  rif  1 M f 1 3. 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 Ví dụ : thuộc tính chiều cao của một người, lấy điểm mốc là mặt đất chỗ người đó đang đứng, và chiều cao của điểm mốc là 0. 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 i = log(xi). Lưu Tuấn Lâm – CT702 12 Đồ án tốt nghiệp Đại học hệ chính quy Thuật toán Phân cụm dữ liệu nửa giám sát 2.3 Những kỹ thuật tiếp cận trong phân cụm dữ liệu Các kỹ thuật áp dụng để giải quyết vấn đề phân cụm dữ liệu đề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. Hiện nay, 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 : 2.3.1 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, do 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 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 (Greedy) để tìm kiếm nghiệm. Một số thuật toán phân cụm phân hoạch điển hình như k-means, PAM, CLARA, CLARANS,…sẽ được trình bày chi tiết ở chương sau. 2.3.2 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 trên xuống (Top down) và phương pháp dưới lên (Bottum up).  Phƣơng pháp “dƣới lên” (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 Lưu Tuấn Lâm – CT702 13 Đồ án tốt nghiệp Đại học hệ chính quy Thuật toán Phân cụm dữ liệu nửa giám sát thỏa 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 “trên xuống” (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 thỏa 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. Một số thuật toán phân cụm phân cấp điển hình như CURE, BIRCH, …sẽ được trình bày chi tiết ở trong chương sau. 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 Data Mining. 2.3.3 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 đó. 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 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ả phân cụm dữ liệu. Hình 5 dưới đây là một 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. Lưu Tuấn Lâm – CT702 14 Đồ án tốt nghiệp Đại học hệ chính quy CSDL 1 Thuật toán Phân cụm dữ liệu nửa giám sát CSDL 2 CSDL 3 Hình 2 : 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 độ Một số thuật toán PCDL dựa trên mật độ điển hình như DBSCAN, OPTICS, DENCLUE, …sẽ được trình bày chi tiết trong chương tiếp theo. 2.3.4 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. Thí dụ như dữ liệu được biểu diễn dưới dạng cấu trúc hình học của đối tượng trong không gian cùng với các quan hệ, các thuộc tính, các hoạt động của chúng. Mục tiêu của phương pháp này là lượng hoá tập dữ liệu thành các ô (Cell), các cell này tạo thành cấu trúc dữ liệu lưới, sau đó các thao tác PCDL làm việc với các đối tượng trong từng Cell này. Cách tiếp cận dựa trên lưới này không di chuyển các đối tượng trong các cell mà xây dựng nhiều mức phân cấp của nhóm các đối tượng trong một cell. Trong ngữ cảnh này, phương pháp này gần giống với phương pháp phân cụm phân cấp nhưng chỉ có điều chúng không trộn các Cell. Do vậy các cụm không dựa trên độ đo khoảng cách (hay còn gọi là độ đo tương tự đối với các dữ liệu không gian) mà nó được quyết định bởi một tham số xác định trước. Ưu điểm của phương pháp PCDL dựa trên lưới là thời gian xử lý nhanh và độc lập với số đối tượng dữ liệu trong tập dữ liệu ban đầu, thay vào đó là chúng phụ thuộc vào số cell trong mỗi chiều của không gian lưới. Một thí dụ về cấu trúc dữ liệu lưới chứa các cell trong không gian như hình 6 sau : Lưu Tuấn Lâm – CT702 15 Đồ án tốt nghiệp Đại học hệ chính quy Thuật toán Phân cụm dữ liệu nửa giám sát 1st layer Tầng 1 1st level (top level) could Mức 1 (mức cao nhất ) có thể chỉ have chứaonly một one Cellcell. . . . . .......... (i-1)th level Cell mứcAi-1cell cóofthể tương ứng corresponds to 4 với 4 cell của mức i cells of ith level. . . . . . (i-1)th layer Tầng i-1 Tầng i .......... ith layer Hình 3 : Mô hình cấu trúc dữ liệu lƣới Một số thuật toán PCDL dựa trên cấu trúc lưới điển hình như : STING, WAVECluster, CLIQUE,… 2.3.5 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ương pháp PCDL dựa trên mô hình cố gắng khớp giữa dữ liệu với mô hình toán học, nó dựa trên giả định rằng dữ liệu được tạo ra bằng hỗn hợp phân phối xác suất cơ bản. Các thuật toán phân cụm dựa trên mô hình có hai tiếp cận chính : Mô hình thống kê và Mạng Nơ ron. Phương pháp này gần giống với phương pháp dựa trên mật độ, bởi vì chúng phát triển các cụm riêng biệt nhằm cải tiến các mô hình đã được xác định trước đó, nhưng đôi khi nó không bắt đầu với một số cụm cố định và không sử dụng cùng một khái niệm mật độ cho các cụm. 2.3.6 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 Lưu Tuấn Lâm – CT702 16 Đồ án tốt nghiệp Đại học hệ chính quy Thuật toán Phân cụm dữ liệu nửa giám sát gian hiệu quả hơn, các nghiên cứu bổ sung cần được thực hiện để cung cấp cho người dùng khả năng kết hợp các ràng buộc trong thuật toán phân cụm. Thực tế, các phương pháp trên đã và đang được phát triển và áp dụng nhiều trong PCDL. Đến nay, đã có một số nhánh nghiên cứu được phát triển trên cơ sở của các phương pháp tiếp cận trong PCDL đã trình bày ở trên như sau : Phân cụm thống kê : Dựa trên các khái niệm phân tích thống kê, nhánh nghiên cứu này sử dụng các độ đo tương tự để phân hoạch các đối tượng, nhưng chúng chỉ áp dụng cho các dữ liệu có thuộc tính số. Phân cụm khái niệm : Các kỹ thuật phân cụm được phát triển áp dụng cho dữ liệu hạng mục, chúng phân cụm các đối tượng theo các khái niệm mà chúng xử lý. Phân cụm mờ : Sử dụng kỹ thuật mờ để PCDL, trong đó một đối tượng dữ liệu có thể thuộc vào nhiều cụm dữ liệu khác nhau. Các thuật toán thuộc loại này chỉ ra lược đồ phân cụm thích hợp với tất cả hoạt động đời sống hàng ngày, chúng chỉ xử lý các dữ liệu thực không chắc chắn. Thuật toán phân cụm mờ quan trọng nhất là thuật toán FCM (Fuzzy c-means) . Phân cụm mạng Kohonen : loại phân cụm này dựa trên khái niệm của các mạng nơ ron. Mạng Kohnen có tầng nơ ron vào và các tầng nơ ron ra. Mỗi nơ ron của tầng vào tương ứng với mỗi thuộc tính của bản ghi, mỗi một nơ ron vào kết nối với tất cả các nơ ron của tầng ra. Mỗi liên kết được gắn liền với một trọng số nhằm xác định vị trí của nơ ron ra tương ứng. Tóm lại, các kỹ thuật PCDL trình bày ở trên đã được sử dụng rộng rãi trong thực tế, thế nhưng hầu hết chúng chỉ nhằm áp dụng cho tập dữ liệu với cùng một kiểu thuộc tính. Vì vậy, việc PCDL trên tập dữ liệu có kiểu hỗn hợp là một vấn đề đặt ra trong Data Mining trong giai đoạn hiện nay. Phần nội dung tiếp theo của luận văn sẽ trình bày tóm lược về các yêu cầu cơ bản làm tiêu chí cho việc lựa chọn, đánh giá kết quả cho các phương pháp phân cụm PCDL. 2.4 Một số ứng dụng của phân cụm dữ liệu Phân cụm dữ liệu được ứng dụng vào rất nhiều lĩnh vực như thương mại, sinh học, phân tích dữ liệu không gian, lập quy hoạch đô thị, nghiên cứu trái đất, địa lý, Web,… Lưu Tuấn Lâm – CT702 17 Đồ án tốt nghiệp Đại học hệ chính quy Thuật toán Phân cụm dữ liệu nửa giám sát Trong thương mại, phân cụm có thể giúp các thương gia tìm kiếm ra các nhóm khách hàng quan trọng cũng như phân loại khách hàng thành từng nhóm khách hàng để từ đó có chiến lược kinh doanh hợp lý. Trong sinh học, phân cụm được dùng để xác định các loài sinh vật cũng như khám phá ra các kiểu gene quý hiếm. Trong phân tích dữ liệu không gian: Do sự đồ sộ của dữ liệu không gian như các hình ảnh vệ tinh hoặc hệ thống thông tin địa lý ,… làm cho người dùng khó khăn trong phân tích và xử lý chúng. Phân cụm có thể giúp chúng ta tự động nhận dạng và chiết xuất các đặc tính trong cơ sở dữ liệu không gian. Trong lập quy hoạch đô thị, phân cụm giúp cho việc nhận dạng cá nhóm nhà theo kiến trúc và vị trí địa lý để lập quy hoạch đô thị hợp lý. Trong nghiên cứu trái đất, phân cụm hỗ trợ việc theo dõi các biến động của trái đất như núi lửa, động đất,… để đưa ra cảnh báo cho chúng ta. Lưu Tuấn Lâm – CT702 18 Đồ án tốt nghiệp Đại học hệ chính quy Thuật toán Phân cụm dữ liệu nửa giám sát Chương 3 : PHÂN CỤM DỮ LIỆU KHÔNG GIÁM SÁT Do sự phát triển không ngừng của phương pháp phân cụm dữ liệu lên hiện nay có rất nhiều phương pháp phân cụm dữ liệu khác nhau. Các thuật toán phân cụm dữ liệu được chia thành các nhóm sau đây :  Phương pháp phân hoạch (pratition),  Phương pháp phân cấp (hierarchical),  Phương pháp dựa trên mật độ (density-based),  Phương pháp dựa trên lưới (grid-based)  Phương pháp dựa trên mô hình (model-based). Trong phạm vi tìm hiểu của đề tài này, em xin trình bày hai phương pháp phân cụm phân hoạch và phân cụm phân cấp, làm cơ sở để trình bày một số phương pháp phân cụm nửa giám sát. 3.1 Phƣơng pháp phân hoạch Trong phân cụm phân hoạch, bài toán đặt ra như sau:cho X   xi i 1 là tập N N đối tượng dữ liệu ta muốn phân cụm, trong đó xi d . Thuật toán phân cụm có nhiệm vụ chia nhỏ tập dữ liệu thành K phân hoạch ( K là giá trị cho trước) mà mỗi phân hoạch đại diện cho một cụm. Các cụm được hình thành trên cơ sở làm tối ưu giá trị hàm mục tiêu (thường là hàm đo độ tương tự) để sao cho các đối tượng trong một cụm là tương tự nhau trong khi các đối tượng trong các cụm khác nhau thì phi tương tự nhau. Có rất nhiều thuật toán phân cụm phân hoạch như : K-Means, K-Medoids, PAM (Partition Around Medoids), CLARA (Clustering Large Applications), CLARANS (Clustering Large Applications based on RAndomized Search), CLASA (Clustering Large Applications based on Simulated Annealing).Ở đây em xin trình bày về hai thuật toán K-Means và K-Medoids. Trong K-Means mỗi cụm được đại diện bởi giá trị tâm (mean) của các đối tượng trong cụm đó. Trong K-Medoids mỗi cụm được đại diện bởi một trong các đối tượng gần tâm cụm nhất. 3.1.1 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 Lưu Tuấn Lâm – CT702 19 Đồ án tốt nghiệp Đại học hệ chính quy Thuật toán Phân cụm dữ liệu nửa giám sát 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 X   xi i 1 , xi d thuật toán K-Means tạo ra K phân hoạch  X h h1 của X K N sao cho nếu h h1 đại diện cho K tâm thì hàm mục tiêu sau: K K Ekmeans   x X || xi  h ||2 i h 1 (1) được cực tiểu địa phương. h Thuật toán: K-Means. Input: - Tập các đối tượng dữ liệu - Số lượng cụm: K X  x1 ,..., xN  , xi d X Output: K phân hoạch tách rời:  h h1 của K X sao cho hàm mục tiêu được tối ưu. Các bƣớc: 1.   Khởi tạo các cụm: các tâm ban đầu (0) K h h 1 được chọn ngẫu nhiên 2. 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 X  K ( t 1) * h h 1 (t ) 2 ) với h* = argmin || x  h || Ước lượng tâm: t  t+1 h(t 1)  1 | X h(t 1) |  xX h( t 1) x Đánh giá thuật toán K-Means Ƣu điểm: K-Means [1] là có độ phức tạp tính toán nhỏ O(NKt). Nhƣợc điểm: K-Means không có khả năng tìm ra các cụm không lồi hoặc các cụm có hình dạng phức tạp. K-Means không khắc phục được nhiễu và giá trị K được xác định bởi người dùng. 3.1.2 Thuật toán K-Medoids Thuật toán K-Medoids có khả năng khắc phục được nhiễu bằng cách chọn đối tượng ở gần tâm cụm nhất làm đại diện cho cụm đó (medoid). Thuật toán K-Medoids được thực hiện qua các bước sau: Lưu Tuấn Lâm – CT702 20