Tài liệu Nghiên cứu mô hình cải tiến kỹ thuật phân nhóm k means

ĐẠI HỌC ĐÀ NẴNG TRƯỜNG ĐẠI HỌC BÁCH KHOA LÂM THỊ HẬU NGHIÊN CỨU MÔ HÌNH CẢI TIẾN KỸ THUẬT PHÂN NHÓM K-MEANS LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH NGƯỜI HƯỚNG DẪN KHOA HỌC TS. NGUYỄN VĂN HIỆU Đà Nẵng – Năm 2018 ĐẠI HỌC ĐÀ NẴNG TRƯỜNG ĐẠI HỌC BÁCH KHOA LÂM THỊ HẬU NGHIÊN CỨU MÔ HÌNH CẢI TIẾN KỸ THUẬT PHÂN NHÓM K-MEANS Chuyên ngành: KHOA HỌC MÁY TÍNH Mã số: 60.48.01.01 LUẬN VĂN THẠC SĨ NGƯỜI HƯỚNG DẪN KHOA HỌC TS. NGUYỄN VĂN HIỆU Đà Nẵng – Năm 2018 ii LỜI CAM ĐOAN Tôi xin cam đoan: - Những nội dung trong luận văn này là do tôi thực hiện dưới sự hướng dẫn trực tiếp của TS. Nguyễn Văn Hiệu. - Mọi tham khảo dùng trong luận văn đều được trích dẫn rõ ràng và trung thực về tên tác giả, tên công trình, thời gian và địa điểm công bố. - Mọi sao chép không hợp lệ, vi phạm quy chế đào tạo tôi xin chịu hoàn toàn trách nhiệm. Tác giả luận văn Lâm Thị Hậu iii MỤC LỤC DANH MỤC CÁC KÍ HIỆU, CÁC TỪ VIẾT TẮT ........................................ vi DANH MỤC CÁC BẢNG BIỂU .................................................................... vii DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ......................................................... viii MỞ ĐẦU ........................................................................................................... 1 1. Lý do chọn đề tài ........................................................................................... 1 2. Mục tiêu và nhiệm vụ nghiên cứu ................................................................. 1 3. Đối tượng và phạm vi nghiên cứu ................................................................. 1 4. Phương pháp nghiên cứu ............................................................................... 2 5. Ý nghĩa khoa học và thực tiễn ....................................................................... 2 6. Cấu trúc của luận văn..................................................................................... 2 CHƯƠNG 1: TỔNG QUAN VỀ KỸ THUẬT PHÂN NHÓM ....................... 3 Giới thiệu về khai phá dữ liệu ................................................................. 3 Phân nhóm dữ liệu là gì? ......................................................................... 5 Kiểu dữ liệu đối tượng được phân nhóm................................................. 6 1.3.1. Các kiểu thuộc tính........................................................................ 8 1.3.2. Phép đo độ tương tự và độ không tương tự đối với các kiểu dữ liệu ....................................................................................................... 9 1.4. Quá trình phân nhóm dữ liệu ................................................................. 17 1.5. Các phương pháp phân nhóm dữ liệu phổ biến ..................................... 18 1.5.1. Phương pháp phân hoạch (Partitioning Methods) ..................... 18 1.5.2. Phương pháp phân cấp (Hierarchical Methods) ......................... 19 1.5.3. Phương pháp dựa trên mật độ (Density-Based Methods) ........... 20 1.5.4. Phương pháp dựa trên lưới (Gird-Based Methods) .................... 22 1.5.5. Phương pháp dựa trên mô hình xác suất (Model-Based Methods) ..................................................................................................... 24 1.6. Phương pháp đánh giá việc phân nhóm dữ liệu .................................... 26 1.7. Một số ứng dụng của phương pháp phân nhóm dữ liệu ........................ 27 1.8. Kết chương ............................................................................................ 28 CHƯƠNG 2: MÔ HÌNH ĐỀ XUẤT VỀ KỸ THUẬT PHÂN NHÓM ........ 29 1.1. 1.2. 1.3. 2.1. Mô hình K-means truyền thống............................................................. 29 2.1.1. Giới thiệu thuật toán K-means .................................................... 29 2.1.2. Thuật toán K-means .................................................................... 31 2.1.3. Minh họa thuật toán .................................................................... 32 iv 2.1.4. Ưu nhược điểm của thuật toán K-means..................................... 36 2.2. Lập trình song song MapReduce ........................................................... 37 2.2.1. Giới thiệu lập trình MapReduce .................................................. 37 2.2.2. Các mô hình sử dụng MapReduce vào kỹ thuật phân nhóm ...... 38 2.3. Mô hình đề xuất ..................................................................................... 41 2.3.1. Mô hình K-means cải tiến của Weizhong Zhao.......................... 41 2.3.2. Mô hình K-means cải tiến sử dụng phương pháp lấy mẫu ......... 42 2.4. Kết chương ............................................................................................ 49 CHƯƠNG 3: KẾT QUẢ THỬ NGHIỆM BÀI TOÁN THỰC TẾ VÀ ĐÁNH GIÁ ................................................................................................. 50 Môi trường và công cụ thử nghiệm ....................................................... 50 3.1.1. Giới thiệu Anaconda Navigator .................................................. 50 3.1.2. Ngôn ngữ lập trình Python .......................................................... 50 3.1.3. Công cụ Jupyter notebook........................................................... 50 3.2. Dữ liệu đầu vào của bài toán thử nghiệm .............................................. 51 3.2.1. Bộ dữ liệu thử nghiệm................................................................. 51 3.2.2. Phân chia dữ liệu đầu vào ứng dụng K-means MapReduce ....... 53 3.3. Kết quả thử nghiệm ............................................................................... 53 3.3.1. Bộ dữ liệu House ......................................................................... 53 3.3.2. Bộ dữ liệu Data_fake .................................................................. 54 3.4. Đánh giá chất lượng và tốc độ ............................................................... 55 3.4.1. Đánh giá chất lượng .................................................................... 55 3.4.2. Đánh giá tốc độ ........................................................................... 58 3.5. Kết chương ............................................................................................ 60 KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN ....................................................... 61 TÀI LIỆU THAM KHẢO ............................................................................... 62 3.1. v NGHIÊN CỨU MÔ HÌNH CẢI TIẾN KỸ THUẬT PHÂN NHÓM K-MEANS Học viên: Lâm Thị Hậu Chuyên ngành: Khoa học máy tính Mã số: ........................ Khóa: K34, Trường Đại học Bách khoa - ĐHĐN Tóm tắt - Ngày nay, với sự gia tăng vượt bậc của nguồn dữ liệu khổng lồ, nhu cầu cấp thiết làm thế nào để trích xuất các thông tin và tri thức hữu ích nhằm đem lại những lợi ích tốt nhất. Để giải quyết vấn đề, con người đã tiến hành khai phá nguồn dữ liệu này nhằm đánh giá các mẫu, rút trích các thông tin hữu ích, chưa biết, tiếm ẩn trong khối dữ liệu lớn. Quá trình khai phá dữ liệu gồm nhiều bước, trong đó phân nhóm là một kỹ thuật quan trọng của quá trình khai phá dữ liệu. Có nhiều kỹ thuật phân nhóm dữ liệu, trong đó K-means là một thuật toán phân nhóm kinh điển, đã và đang được ứng dụng trong nhiều lĩnh vực như: y học, sinh học, tìm kiếm Web, chăm sóc khách hàng, … Tuy nhiên, đối với những tập dữ liệu lớn, thuật toán K-means tốn nhiều thời gian và hiệu quả phân nhóm tùy thuộc vào khởi tạo trọng tâm ban đầu, vì vậy có rất nhiều phương pháp cải tiến thuật toán K-means đã được nghiên cứu và thực hiện. Trên cơ sở thuật toán K-means, tôi đã nghiên cứu mô hình cải tiến kỹ thuật phân nhóm K-means sử dụng phương pháp lấy mẫu kết hợp với lập trình song song MapReduce. Kết quả nghiên cứu của đề tài góp phần mở rộng lĩnh vực ứng dụng kỹ thuật phân nhóm trong việc khai phá nguồn thông tin khổng lồ để giải quyết các vấn đề trong thực tế. Từ khóa – phân nhóm dữ liệu, kỹ thuật phân nhóm, thuật toán K-means, cải tiến K-means sử dụng phương pháp lấy mẫu, K-means MapReduce. RESEARCH TECHNICAL IMPROVEMENT MODEL DIVISION OF K-MEANS GROUP Today, with the enormous increase in data availability, there is an urgent need to extract useful information and knowledge for the best benefit. In order to solve the problem, people have exploited this data source to evaluate the samples, extract useful information, unknown and hidden in large data blocks. Data mining involves many steps, where clustering is an important technique for data mining. There are many data classification techniques in which K-means is a classic clustering algorithm that has been applied in many fields such as medicine, biology, web search, customer care, ... However, for large data sets, the K-means algorithm takes time and the clustering efficiency depends on initial initialization, so there are many methods for improving the K-means algorithm. be studied and implemented. Based on the K-means algorithm, the thesis studied the improved model of K-means division using the sampling method in combination with the parallel mapreduction program. The research results of the thesis contribute to expanding the field of application of grouping techniques in exploring huge sources of information to solve problems in practice. Keywords - Data clustering, clustering techniques, K-means algorithm, Improving K-means using the sampling method, K-means MapReduce. vi DANH MỤC CÁC KÍ HIỆU, CÁC TỪ VIẾT TẮT STT Ký hiệu/ Viết tắt Diễn giải 1 sf Tính độ lệch trung bình của các thuộc tính 2 mf Giá trị trung bình của thuộc tính f 3 zif Độ đo được chuẩn hóa 4 d(i,j) Độ đo khoảng cách (không tương tự) giữa 2 đối tượng i và j 5 sim(i,j) Độ tương tự giữa 2 đối tượng i và j 6 xif Giá trị của thuộc tính f đối với đối tượng thứ i 7 rif Xếp hạng trong thuộc tính thứ f của đối tượng thứ i 8 CSDL Cơ sở dữ liệu 9 HDFS Hệ thống tập tin phân toán 10 DBI chỉ số Davies-Bouldin (DBI) của kỹ thuật đánh giá trong 11 EM Thuật toán tối ưu hóa kỳ vọng vii DANH MỤC CÁC BẢNG BIỂU Số hiệu bảng Tên bảng Trang 1.1 Ví dụ về các kiểu thuộc tính dữ liệu 11 1.2 Bảng sự kiện ngẫu nghiên của các thuộc tính nhị phân 13 1.3 Bảng thông tin bệnh nhân được mô tả bởi các thuộc tính nhị phân 14 2.1 Thông tin học sinh cần phân nhóm 32 2.2 Kết quả minh họa quá trình phân nhóm dữ liệu 36 2.3 CSDL1 và tọa độ trọng tâm ban đầu của CSDL1 44 2.4 CSDL2 và tọa độ trọng tâm ban đầu của CSDL2 44 2.5 CSDL3 và tọa độ trọng tâm ban đầu của CSDL3 45 2.6 Phân nhóm các đối tượng của CSDL1 và tính lại tọa độ tâm 45 2.7 Phân nhóm các đối tượng của CSDL2 và tính lại tọa độ tâm 46 2.8 Phân nhóm các đối tượng của CSDL3 và tính lại tọa độ tâm 47 2.9 Tập các đối tượng của CSDL mẫu 47 2.10 Tọa độ trọng tâm ban đầu của CSDL mẫu 48 2.11 Phân nhóm các đối tượng của CSDL mẫu vào k=3 nhóm 48 2.12 Phân nhóm các đối tượng của CSDL D 49 3.1 Thông tin thuộc tính bộ dữ liệu House 51 3.2 3.3 3.4 3.5 Chỉ số DB của K-means và SK-meansMR trên bộ dữ liệu House Chỉ số DB của K-means và SK-meansMR trên bộ dữ liệu Data_fake Thời gian chạy của K-means và SK-meansMR trên bộ dữ liệu House Thời gian chạy của K-means và SK-meansMR trên bộ dữ liệu Data_fake 56 57 58 59 viii DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ Số hiệu hình vẽ 1.1 1.2 1.3 1.4 1.5 1.6 1.7 1.8 2.1 2.2 2.3 2.4 2.5 2.6 2.7 2.8 2.9 3.1 3.2 3.3 3.4 3.5 3.6 3.7 3.8 3.9 3.10 3.11 3.12 3.13 Tên hình vẽ Trang Quy trình khai phá dữ liệu Mô hình phân nhóm dữ liệu Cách biểu diễn các nhóm trong CSDL Mô tả khoảng cách Euclidean và Mahata Quá trình phân nhóm của R. XU, D. Wunsch II. Survey Mô hình thuật toán phân cấp (thuật toán AGNES và DIANA) Mô hình tiếp cận mật độ và kết nối mật độ Mô hình phân nhóm dựa trên lưới (thuật toán STING) Sơ đồ thuật toán phân nhóm K-means Khởi tạo trọng tâm cho thuật toán K-means Tính lại tọa độ trọng tâm lần 1 Tính lại tọa độ trọng tâm lần 2 Mô hình lập trình MapReduce Mô hình MapReduce cho thuật toán DBSCAN Sơ đồ thuật toán PK-means Quá trình phân nhóm theo phương pháp SK-meansMR Sơ đồ thuật toán SK-meansMR Giao diện Jupyter Notebook Thông tin bộ dữ liệu House Thông tin bộ dữ liệu Data_fake Bộ dữ liệu House được phân chia làm đầu vào cho hàm Map Bộ dữ liệu Data_fake được phân chia làm đầu vào cho hàm Map Kết quả chạy thuật toán K-means với bộ dữ liệu House Kết quả chạy thuật toán SK-meansMR với bộ dữ liệu House Kết quả chạy thuật toán K-means với bộ dữ liệu Data_fake Kết quả chạy thuật toán SK-meansMR với bộ dữ liệu Data_fake Biểu đồ chất lượng phân nhóm K-means và SK-meansMR trên bộ dữ liệu House Biểu đồ chất lượng phân nhóm K-means và SK-meansMR trên bộ dữ liệu Data_fake Biểu đồ tốc độ của K-means và SK-meansMR trên bộ dữ liệu House Biểu đồ tốc độ của K-means và SK-meansMR trên bộ dữ liệu Data_fake 4 5 6 13 17 20 21 23 31 32 34 35 38 40 41 42 43 51 52 52 53 53 53 54 54 55 56 57 58 59 1 MỞ ĐẦU 1. Lý do chọn đề tài Những năm gần đây, sự tiến bộ vượt bậc của công nghệ thông tin cùng với sự phát triển kinh tế, xã hội và Internet đã tạo ra nguồn dữ liệu khổng lồ, đa dạng về thể loại và ngành nghề. Bên cạnh đó, thế giới đang trong xu thế toàn cầu hóa, các tổ chức chính phủ, y tế, giáo dục, thương mại, … đang phải đối mặt với nhiều khó khăn, thách thức, dẫn đến nhu cầu cấp thiết làm thế nào để trích xuất những thông tin, các tri thức hữu ích từ nguồn dữ liệu này, để vận dụng cải thiện hiệu quả hoạt động của hệ thống thông tin ban đầu nhằm đem lại lợi ích và mục đích tốt nhất. Giải pháp hữu hiệu để con người giải quyết các vấn đề nêu trên là khai phá khối lượng dữ liệu đang gia tăng chóng mặt này. Có nhiều kỹ thuật để khai phá dữ liệu như phân lớp, dự đoán, phân nhóm, luật kết hợp, ... Trong đó phân nhóm là một bước quan trọng trong khai phá dữ liệu. Kỹ thuật này đã, đang và sẽ có nhiều ứng dụng trong các lĩnh vực như thương mại điện tử, chăm sóc sức khỏe, ngân hàng, viễn thông, v.v…. Với mong muốn góp phần nghiên cứu và ứng dụng kỹ thuật phân nhóm vào việc khai phá dữ liệu để giải quyết các vấn đề thực tế, tôi quyết định chọn đề tài “Nghiên cứu mô hình cải tiến kỹ thuật phân nhóm K-means”. 2. Mục tiêu và nhiệm vụ nghiên cứu Mục tiêu: - Xây dựng được mô hình cải tiến kỹ thuật phân nhóm trên cơ sở phương pháp K-means; - Đánh giá được sự hiệu quả của phương pháp cải tiến so với phương pháp phân nhóm truyền thống; - Xây dựng thử nghiệm thành công mô hình cải tiến trên bộ dữ liệu thử. Nhiệm vụ: - Tìm hiểu về kỹ thuật phân nhóm; - Tìm hiểu mô hình lập trình song song MapReduce; - Tìm hiểu về dữ liệu thực tế (cụ thể các bài toán thực tế). 3. Đối tượng và phạm vi nghiên cứu Đối tượng nghiên cứu - Kỹ thuật phân nhóm dữ liệu tập trung vào kỹ thuật K-means; - Mô hình lập trình song song MapReduce. Phạm vi nghiên cứu - Các thuật toán của kỹ thuật phân nhóm dữ liệu; - Mô hình lập trình song song MapReduce. 2 - Các bài toán đặc trưng cho thuật toán phân nhóm với bộ dữ liệu thực nghiệm gồm có: Individual Household Electric Power Consumption (House) 9 thuộc tính, 2.049.280 điểm, kích thước 126 MB tải về tại UCI Machine Learning Repository http://archive.ics.uci.edu/ml/index.php và bộ dữ liệu tự tạo Data_fake 3 thuộc tính có số lượng 5.000.000 điểm, kích thước 144 MB. 4. Phương pháp nghiên cứu Nghiên cứu lý thuyết - Tìm hiểu lý thuyết về thuật toán phân nhóm dữ liệu K-means; - Tìm hiểu về mô hình lập trình song song MapReduce; - Tìm hiểu các bài toán thực tế. Nghiên cứu thực nghiệm - Xây dựng bộ dữ liệu thử nghiệm; - Xây dựng chương trình thực nghiệm để so sánh mô hình đề xuất và mô hình truyền thống. 5. Ý nghĩa khoa học và thực tiễn Về mặt khoa học: - Nghiên cứu, tìm hiểu kỹ thuật phân nhóm dữ liệu trên cơ sở thuật toán K-means để ứng dụng vào các bài toán thực tế; - Nghiên cứu hướng cải tiến K-means truyền thống kết hợp với lập trình song song. Về mặt thực tiễn: Kết quả nghiên cứu của đề tài góp phần mở rộng lĩnh vực ứng dụng kỹ thuật phân nhóm dữ liệu trong việc khai thác nguồn thông tin khổng lồ đang gia tăng mỗi ngày. 6. Cấu trúc của luận văn Sau phần mở đầu, nội dung chính của luận văn được chia thành 3 chương: Chương 1: Trình bày tổng quan về khai phá dữ liệu, phân nhóm dữ liệu và quá trình phân nhóm. Các phương pháp phân nhóm dữ liệu và ứng dụng, … Chương 2: Trình bày kỹ thuật phân nhóm theo mô hình K-means truyền thống, giới thiệu lập trình song song MapReduce và đề xuất mô hình K-means cải tiến sử dụng phương pháp lấy mẫu. Chương 3: Trình bày môi trường, công cụ và thử nghiệm bài toán với các bộ dữ liệu thực tế, so sánh đánh giá chất lượng và tốc độ của thuật toán K-means truyền thống và K-means cải tiến. Cuối cùng là phần đánh giá kết luận và hướng phát triển của đề tài. 3 CHƯƠNG 1: TỔNG QUAN VỀ KỸ THUẬT PHÂN NHÓM 1.1. Giới thiệu về khai phá dữ liệu Mọi người thường nói “Chúng ta đang sống trong thời đại thông tin” nhưng thực ra chúng ta đang sống trong thời đại dữ liệu. Bởi các Terabyte hoặc petabyte dữ liệu đổ vào các mạng máy tính, World Wide Web và các thiết bị lưu trữ dữ liệu khác nhau mỗi ngày từ xã hội, kinh doanh, khoa học kỹ thuật, y học và hầu như mọi khía cạnh khác của cuộc sống hàng ngày. Sự tăng trưởng bùng nổ của khối lượng dữ liệu này là kết quả của việc tin học hoá xã hội và sự phát triển nhanh chóng của các công cụ thu thập và lưu trữ dữ liệu. Danh sách các nguồn tạo ra lượng dữ liệu khổng lồ là vô tận. Cơ sở dữ liệu đang phát triển, có sẵn và rộng lớn này rất cần các công cụ mạnh mẽ và linh hoạt để tự động phát hiện thông tin có giá trị từ lượng dữ liệu khổng lồ và chuyển đổi dữ liệu đó thành kiến thức có tổ chức. Sự cần thiết này đã dẫn đến sự ra đời của khai phá dữ liệu (data mining). Khai phá dữ liệu là một bước trong quá trình khám phá tri thức, và là bước quan trọng phát hiện các thông tin có ích, tiềm ẩn chưa được biết trước trong cơ sở dữ liệu. Trong ngành công nghiệp, trong truyền thông và trong nghiên cứu, thuật ngữ khai phá dữ liệu thường được sử dụng để chỉ toàn bộ quá trình khám phá tri thức (khám phá tri thức từ dữ liệu). Từ đó, khai phá dữ liệu được định nghĩa là quá trình khám phá và đánh giá các mẫu, rút trích các thông tin hữu ích, chưa biết, tiếm ẩn trong khối dữ liệu lớn. Các nguồn dữ liệu có thể bao gồm cơ sở dữ liệu, kho dữ liệu, Web, kho lưu trữ thông tin khác hoặc dữ liệu được truyền trực tiếp vào hệ thống. ❖ Khai phá dữ liệu liên quan chặt chẽ đến các lĩnh vực: Thống kê (Statistics); Máy học (Machine Learning); Cơ sở dữ liệu (Databases); Trực quan hóa (Visualization) giúp dữ liệu dễ hiểu và dễ sử dụng. ❖ Các kỹ thuật sử dụng trong khai phá dữ liệu: - Phân lớp: Tìm các đặc trưng của lớp các đối tượng và sử dụng để phân lớp dữ liệu mới; - Dự đoán: Dự đoán dữ liệu tương lai dựa trên dữ liệu quá khứ; - Phân nhóm: Xác định các nhóm tiềm ẩn trong các tập đối tượng chưa được xếp lớp; - Luật kết hợp: Tìm các mẫu phổ biến từ dữ liệu và mối quan hệ của các đối tượng dữ liệu; - Mẫu tuần tự: Khám phá các mẫu tín hiệu phổ biến nhất từ dữ liệu các sự kiện; 4 - Nhà kho – OLAP: Xác định trật tự dữ liệu, cấu trúc lưu trữ phù hợp với tác vụ khai phá. ❖ Quy trình khai phá dữ liệu: Nghiên cứu lĩnh vực Tạo tập dữ liệu đầu vào Tiền xử lý/ làm sạch, mã hóa Rút gọn Chọn tác vụ khai thác dữ liệu Chọn các thuật giải khai thác dữ liệu Khai thác dữ liệu: Tìm kiếm tri thức Đánh giá mẫu tìm được Biểu diễn tri thức Sử dụng các tri thức vừa khám phá Hình 1.1 Quy trình khai phá dữ liệu ❖ Ứng dụng của khai phá dữ liệu: Khai phá dữ liệu được ứng dụng rộng rãi trong mọi lĩnh vực như: - Kinh doanh: Phân tích dữ liệu bán hàng và tiếp thị; Phân tích đầu tư; Chứng khoán; Xác định gian lận; … - Khoa học: Không gian; Sinh học; Địa lý; … - Sản xuất: Điều khiển và lập lịch; Quản trị mạng lưới; Phân tích kết quả thử nghiệm; … - Y học: Phát hiện bệnh lý; Sinh học; … 5 -…… Khai phá dữ liệu là lĩnh vực trẻ, năng động và đầy hứa hẹn. Với các lợi ích mang lại cho nhân loại khai phá dữ liệu đã, đang và sẽ tiếp tục có những bước tiến lớn trong hành trình của chúng ta từ thời đại dữ liệu đến thời đại thông tin sắp tới. 1.2. Phân nhóm dữ liệu là gì? Quá trình khai phá dữ liệu bao gồm nhiều bước, trong đó việc lựa chọn kỹ thuật phù hợp để thực hiện khai phá dữ liệu là quan trọng nhất. Đối với một số lĩnh vực cần tìm kiếm hoặc trích lọc tri thức trực tiếp từ cơ sở dữ liệu như phân đoạn thị trường, phân đoạn khách hàng, nhận dạng mẫu, xử lý ảnh, phân loại trang web,… thì phân nhóm dữ liệu là một kỹ thuật phù hợp để tiến hành khai phá dữ liệu. ❖ Định nghĩa Phân nhóm (clustering) là các qui trình tìm cách nhóm các đối tượng đã cho vào các nhóm (clusters), sao cho các đối tượng trong cùng 1 nhóm tương tự (similar) nhau và các đối tượng khác nhóm thì không tương tự (dissimilar) nhau. Phân nhóm Hình 1.2 Mô hình phân nhóm dữ liệu Cho cơ sở dữ liệu D={t1,t2,…,tn} và số nguyên k, phân nhóm là bài toán xác định ánh xạ f : D → {1,…,k} sao cho mỗi ti được gán vào một nhóm kj, 1 <= j <= k. Khác với bài toán phân lớp, các nhóm không được biết trước. Hay nói cách khác, phân nhóm là phương pháp học tập theo quan sát (learning from obversation) còn gọi là học không có thầy (unsupervised learning or automatic classfication) trong trí tuệ nhân tạo. 6 ❖ Mục đích Mục đích của phân nhóm là tìm ra bản chất bên trong của các nhóm dữ liệu nhằm thực hiện các mục tiêu như: trích xuất các thông tin hữu ích, giảm kích thước dữ liệu, phát hiện các giá trị ngoại lai, … ❖ Cách biểu diễn các nhóm - Các nhóm có thể phân chia bằng các đường ranh giới; - Các khối cầu; - Theo xác suất; - Hình cây; -… 1 2 3 I1 0.5 0.2 0.3 I2 … In Hình 1.3 Cách biểu diễn các nhóm trong CSDL Bài toán phân nhóm là quá trình phân chia một cơ sở dữ liệu (CSDL) thành những nhóm đối tượng dữ liệu phục vụ cho mục đích cụ thể của từng ứng dụng thực tế. Không có một kỹ thuật phân nhóm nào là tốt nhất và thích hợp cho tất cả mọi ứng dụng mà với mỗi ứng dụng khác nhau thì người sử dụng phải lựa chọn ra một thuật toán phân nhóm cụ thể thích ứng với ứng dụng đó. Kết quả đánh giá cho từng thuật toán cũng phụ thuộc vào những yêu cầu của từng ứng dụng. 1.3. Kiểu dữ liệu đối tượng được phân nhóm Dữ liệu đối tượng được phân nhóm thường diễn tả dưới dạng các biến hoặc thuộc tính. Các thuộc tính này là các tham số để giải quyết vấn đề phân nhóm và sự lựa chọn 7 chúng có tác động đáng kể đến kết quả phân nhóm. Phân loại các kiểu thuộc tính khác nhau là 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. Các thuật toán phân nhóm thường sử dụng một trong hai cấu trúc dữ liệu sau: Ma trận dữ liệu (Data matrix): Là mảng hai chiều gồm n hàng, p cột. Trong đó: n là số đối tượng (objects), p là số biến/thuộc tính (variables/attributes) của mỗi đối tượng. Mỗi hàng biểu diễn một đối tượng, các phần tử trong mỗi hàng chỉ giá trị thuộc tính tương ứng của đối tượng đó. Ma trận không tương tự (dissimilarity matrix): Là mảng hai chiều gồm n hàng, n cột. Trong đó phần tử d(i,j) chứa khoảng cách hay độ khác biệt giữa các đối tượng i và đối tượng j, d(i,j) là một số không âm, nếu d(i,j) xấp xỉ 0 thì hai đối tượng i và j là gần giống nhau, nếu d(i,j) càng lớn thì hai đối tượng i, j càng khác nhau, d(i,i) = 0 và d(i,j) = d(j,i), d(i,j) được tính tuỳ thuộc vào kiểu của các biến/thuộc tính. Phần lớn các thuật toán phân nhóm sử dụng cấu trúc ma trận không tương tự. Do vậy, nếu dữ liệu cần phân nhóm được tổ chức dưới dạng ma trận dữ liệu thì cần biến đổi về dạng ma trận không tương tự trước khi tiến hành phân nhóm. Cho một CSDL D chứa n đối tượng vector trong không gian p chiều; x, y, z là các đối tượng thuộc D: x= (x1, x2, … , xp); y= (y1, y2, … , yp); z= (z1, z2, … , zp) Trong đó xi , yi, zi với i=1,2, …,p là các thuộc tính tương ứng của các đối tượng x, y, z. Các thuộc tính này có các kiểu dữ liệu như sau: 8 1.3.1. Các kiểu thuộc tính ❖ Thuộc tính định danh/chuỗi (Norminal): Là thuộc tính lấy giá trị từ một tập không có thứ tự. Các giá trị của thuộc tính định danh là các kí hiệu hoặc tên của sự vật. Ví dụ màu tóc là thuộc tính định danh có các giá trị là đen, nâu, vàng nhạt, xám,… hoặc thuộc tính nghề nghiệp có các giá trị như giáo viên, bác sỹ, lập trình viên, nông dân, … ❖ Thuộc tính có thứ tự (Ordinal): Là thuộc tính định danh có các giá trị có thể có một thứ tự có ý nghĩa hoặc được xếp hạng trong số đó. Ví dụ các thuộc tính lấy giá trị số như: Age, Height,… hoặc thuộc tính Income lấy giá trị từ tập {low, medium, high}. ❖ Thuộc tính số (Numeric Attributes): Là một số lượng đo lường, đại diện cho số nguyên hoặc các giá trị thực. Các thuộc tính số có thể được tính bằng khoảng cách hoặc tỉ lệ. • Thuộc tính được tính bằng khoảng cách (Interval-scaled variables/attributes) còn gọi là thuộc tính khoảng: Là một tập giá trị mà các phần tử cách đều nhau (thường dùng làm các thang đo). Các thuộc tính khoảng cách được đo bằng một đơn vị có kích thước bằng nhau. Giá trị của các thuộc tính khoảng có thứ tự và có thể là dương, 0 hoặc âm. Do đó, ngoài việc cung cấp thứ hạng các giá trị, các thuộc tính như vậy cho phép chúng ta so sánh và xác định sự khác biệt giữa các giá trị cũng như giá trị trung bình, trung vị và yếu trung vị. Ví dụ: Thuộc tính nhiệt độ là thuộc tính khoảng cách. Giả sử chúng ta có giá trị nhiệt độ ngoài trời trong một số ngày khác nhau, trong đó mỗi ngày là một đối tượng. Bằng cách xếp thứ tự các giá trị, chúng ta có được một thứ hạng của các đối tượng về nhiệt độ. Ngoài ra, chúng ta có thể xác định sự khác biệt giữa các giá trị như nhiệt độ 200C cao hơn năm 5 độ so với nhiệt độ 150C. • Thuộc tính được tính bằng tỉ lệ (Ratio-Scaled Attributes) còn gọi là thuộc tính tỉ lệ: Thuộc tính tỉ lệ tương tự thuộc tính khoảng nhưng điểm khác biệt là được xác định một cách tương đối so với điểm mốc (0). Các phần tử thuộc kiểu dữ liệu này có thể so sánh như là bội số với nhau. Dữ liệu kiểu tỉ lệ có thể thực hiện các phép nhân, chia. Ví dụ: Thang đo nhiệt độ Kelvin (K) khác với nhiệt độ Celsius và Fahrenheit, có điểm mốc là 0 (00K = -273.150C). Thuộc tính trọng lượng, 10kg là hai lần 5 kg. Hoặc các ví dụ khác bao gồm các thuộc tính để đo chiều cao, vĩ độ và kinh độ, …, đếm số năm kinh nghiệm, đếm số lượng từ,… ❖ Thuộc tính nhị phân (Binary attributes): là một trường hợp đặc biệt của kiểu định danh. Tập các giá trị chỉ gồm có 2 giá trị (Y/N, 0/1, T/F). 9 ❖ Thuộc tính liên tục (Continuous-valued attributes): Miền giá trị của thuộc tính là vô hạn không đếm được, các giá trị là các số thực (ví dụ: các thuộc tính nhiệt độ, cường độ âm thanh,…) ❖ Thuộc tính rời rạc (Discrete-valued attributes): Miền giá trị của thuộc tính là tập hữu hạn. Bao gồm các thuộc tính có kiểu giá trị là các số nguyên và cả các thuộc tính nhị phân (ví dụ: Yes/No, True/False, On/Off, …) ❖ Thuộc tính có kiểu hỗn hợp (Attributes of mixed types) Cơ sở dữ liệu có thể chứa tất cả kiểu thuộc tính trên được gọi là kiểu hỗn hợp của thuộc tính. ❖ Ngoài ra còn có dữ liệu không gian có thể được coi là các tính năng được đặt trên hoặc được tham chiếu đến bề mặt của trái đất, như đường, suối, ranh giới chính trị, trường học, phân loại sử dụng đất, tài sản sở hữu tài sản, … Dữ liệu không gian là loại dữ liệu có thuộc tính số khái quát trong không gian nhiều chiều, mô tả các thông tin liên quan đến không gian, chứa đựng các đối tượng. Dữ liệu không gian có thể là dữ liệu liên tục hoặc rời rạc. 1.3.2. Phép đo độ tương tự và độ không tương tự đối với các kiểu dữ liệu Việc lựa chọn đơn vị đo cho các thuộc tính cũng ảnh hưởng đến chất lượng phân nhóm. Nếu đơn vị độ đo của một thuộc tính càng được chia nhỏ, thì khoảng cách xác định của thuộc tính đó càng lớn và ảnh hưởng nhiều hơn đến kết quả phân nhóm. Để tránh phụ thuộc vào việc lựa chọn đơn vị đo, dữ liệu cần được chuẩn hóa. Việc chuẩn hóa sẽ gán cho tất cả các thuộc tính một trọng số bằng nhau. Tuy nhiên, trong nhiều trường hợp người sử dụng có thể thay đổi trọng số cho các thuộc tính ưu tiên. Để chuẩn hóa các độ đo, một cách làm phổ biến là biến đổi các thuộc tính về dạng không có đơn vị đo. Giả sử đối với các thuộc tính f, ta thực hiện như sau: Tính độ lệch trung bình (Mean absolute deviation): (1.1) Trong đó x1f, …, xnf là giá trị thuộc tính f của n phần tử dữ liệu, và mf là giá trị trung bình của f, được tính như sau: (1.2) 10 Độ đo được chuẩn hóa (Z-score measurement): (1.3) Phép đo độ tương tự hoặc không tương tự là để đo sự giống nhau hoặc khác nhau giữa các cặp đối tượng dữ liệu, chúng thường được đo bằng khoảng cách giữa các đối tượng. Giá trị của hàm tính độ tương tự càng lớn thì sự giống nhau giữa các đối tượng càng lớn và ngược lại. Hàm tính độ không tương tự tỉ lệ nghịch với hàm tính độ tương tự. Tất cả các cách đo độ tương tự đều phụ thuộc vào kiểu thuộc tính mà con người phân tích. Các độ đo dưới đây được xác định trong không gian metric. Một không gian metric là một tập trong đó có xác định “khoảng cách” giữa từng cặp phần tử, với những tính chất thông thường của khoảng cách hình học. ❖ Đo độ tương tự cho các thuộc tính định danh Một thuộc tính định danh có thể có hai hoặc nhiều giá trị. Gọi M là số lượng các giá trị của một thuộc tính định danh. Các giá trị có thể được ký hiệu bởi các ký tự, ký hiệu, hoặc tập các số nguyên, chẳng hạn như 1, 2, ..., M. Độ không tương tự giữa hai đối tượng i và j được tính theo công thức: 𝒅(𝒊, 𝒋) = 𝒑−𝒎 𝒑 (1.4) Trong đó: - m là số thuộc tính định danh được so sánh có giá trị tương ứng trùng nhau của hai đối tượng i và j. - p là tổng số các thuộc tính định danh. - d(i,j) được đánh giá là 0 (= 0) nếu hai đối tượng i và j có giá trị thuộc tính định danh giống nhau và 1 (=1) nếu i và j có giá trị thuộc tính định danh khác nhau. Và độ tương tự của hai đối tượng i và j được tính theo công thức: 𝒔𝒊𝒎(𝒊, 𝒋) = 𝟏 − 𝒅(𝒊, 𝒋) = 𝒎 𝒑 (1.5) Ví dụ: Độ không tương tự của các thuộc tính định danh. Giả sử có dữ liệu mẫu trong Bảng 1.1, với Test-1 là thuộc tính định danh. Ma trận không tương tự được thể hiện như sau: 11 0 𝑑 (2,1) 0 [ ] 𝑑 (3,1) 𝑑(3,2) 0 𝑑 (4,1) 𝑑(4,2) 𝑑 (4,3) 0 Ở đây có một thuộc tính định danh nên p=1. Sau khi tính toán các d(i,j) theo công thức 1.4 ta có ma trận không tương tự như sau: 0 1 [ 1 0 0 1 1 0 1 ] 0 Từ ví dụ ta thấy d(4,1) = 0 nên chỉ có hai đối tượng 1 và 4 có thuộc tính định danh giống nhau. Các đối tượng còn lại khác nhau. Bảng 1.1 Ví dụ về các kiểu thuộc tính của dữ liệu Object Identifier 1 Test-1 (norminal) Code A Test-2 (ordinal) Excellent Test-3 (numeric) 45 2 Code B Fair 22 3 Code C Good 64 4 Code A Excellent 28  Thuộc tính định danh có thể mã hóa thành thuộc tính nhị phân bất đối xứng cho mỗi giá trị M. Cho một tập dữ liệu các đối tượng với thuộc tính định danh được đổi thành nhị phân có một giá trị đại diện được đặt là 1, các giá trị còn lại của thuộc tính được đặt là 0. Ví dụ: để mã hóa thuộc tính màu bản đồ, thuộc tính màu vàng được đặt là 1, ba thuộc tính còn lại đỏ, xanh, tím được đặt là 0. Khi đó độ đo khoảng cách cho các đối tượng này sẽ áp dụng độ đo khoảng cách của các thuộc tính nhị phân. ❖ Đo độ tương tự cho các thuộc tính có thứ tự Gọi M là tổng số các giá trị của thuộc tính có thứ tự (thuộc tính thứ f của đối tượng thứ i). Các giá trị được sắp xếp thứ tự 1, ..., Mf (Ví dụ: thuộc tính Incom có tập các giá trị là {flow, median, height} thì có M=3 và thứ tự sắp xếp là {1,2,3}). Độ không tương tự đối với thuộc tính f gồm các bước: 1. Giá trị của thuộc tính f đối với đối tượng thứ i là xif, và f có Mf các giá trị, được xếp thứ tự 1, ..., Mf. Thay thế mỗi xif bằng thứ hạng tương ứng của nó là rif, với rif ∈ {1, ..., Mf} (ví dụ giá trị flow được thay bằng 1, median được thay bằng 2,…).