Tài liệu Phân cụm dữ liệu và ứng dụng phân cụm học sinh trường trung học cơ sở chu văn an

i LỜI CAM ĐOAN Tác giả Trịnh Anh Tuấn xin cam kết rằng nội dung của Luận văn này chưa được nộp cho bất kỳ một chương trình cấp bằng cao học nào cũng như bất kỳ một chương trình đào tạo cấp bằng nào khác. Ngoài ra, tác giả cũng xin cam kết Luận văn thạc sĩ này là nỗ lực riêng của cá nhân tác giả. Các kết quả, phân tích, kết luận trong Luận văn thạc sĩ này (ngoài các phần được trích dẫn) đều là kết quả làm việc của cá nhân tác giả. Thái Nguyên, tháng 6 năm 2016 Tác Giả Trịnh Anh Tuấn ii LỜI CẢM ƠN Để hoàn thành được luận văn này, trước hết tôi xin gửi lời cảm ơn sâu sắc nhất tới TS. Nguyễn Long Giang, Viện Công nghệ thông tin - Viện Hàn lâm Khoa học và Công nghệ Việt Nam đã tận tình hướng dẫn, chỉ bảo, định hướng, đóng góp những ý kiến quý báu trong suốt quá trình thực hiện luận văn. Tôi xin chân thành cảm ơn các thầy, cô giáo trong Bộ môn Khoa học máy tính, Khoa Công nghệ thông tin, Phòng Đào tạo Sau đại học - Nghiên cứu Khoa học, Trường Đại học Công nghệ thông tin và truyền thông Thái Nguyên đã tạo mọi điều kiện tốt nhất để tôi hoàn thành khóa học. Xin cám ơn đồng nghiệp tại trường Trung học cơ sở Chu Văn An thành phố Thái Nguyên đã trợ giúp rất nhiều trong thời gian qua. Trong quá trình thực hiện Luận văn, mặc dù đã cố gắng hết mình, song chắc chắn luận văn của em vẫn còn nhiều thiếu sót. Em rất mong nhận được sự chỉ bảo vào đóng góp tận tình của các thầy cô để luận văn của em được hoàn thiện hơn. Thái Nguyên, tháng 6 năm 2016 Tác Giả Trịnh Anh Tuấn iii MỤC LỤC LỜI CAM ĐOAN ........................................................................................................................................i LỜI CẢM ƠN................................................................................................................................................ii MỤC LỤC.....................................................................................................................................................iii DANH MỤC CÁC BẢNG........................................................................................................................vi DANH MỤC CÁC HÌNH.........................................................................................................................vii MỞ ĐẦU ........................................................................................................................................................1 1.1. Sự cần thiết lựa chọn đề tài ............................................................................................ 1 1.2. Mục tiêu đề tài................................................................................................................ 2 1.3. Đối tượng và phạm vi nghiên cứu ................................................................................. 2 1.4. Phương pháp nghiên cứu ............................................................................................... 3 1.5. Cấu trúc của luận văn..................................................................................................... 3 Chương 1. TỔNG QUAN............................................................................................................................4 1.1. Quá trình khám phá tri thức ........................................................................................... 4 1.2. Khai phá dữ liệu ............................................................................................................. 5 1.2.1. Khái niệm khai phá dữ liệu............................................................................. 5 1.2.2. Các kỹ thuật khai phá dữ liệu ......................................................................... 6 1.3. Phân cụm dữ liệu............................................................................................................ 8 1.3.1. Khái niệm về phân cụm dữ liệu ...................................................................... 8 1.3.2. Một số vấn đề trong phân cụm dữ liệu ............................................................ 9 1.3.3. Mục tiêu của phân cụm dữ liệu..................................................................... 10 1.3.4. Các bước cơ bản trong phân cụm dữ liệu ..................................................... 10 1.3.5. Yêu cầu của phân cụm dữ liệu ...................................................................... 11 1.3.6. Ứng dụng của phân cụm dữ liệu ................................................................... 12 1.4. Kết luận chương ........................................................................................................... 13 Chương 2. CÁC PHƯƠNG PHÁP PHÂN CỤM DỮ LIỆU.............................................................14 2.1. Kiểu dữ liệu .................................................................................................................. 14 2.1.1. Phân loại kiểu dữ liệu dựa trên kích thước miền ........................................... 14 2.1.2. Phân loại kiểu dữ liệu dựa trên hệ đo ........................................................... 14 2.2. Phép đo độ tương tự và phép đo khoảng cách ............................................................ 16 iv 2.2.1. Khái niệm tương tự và không tương tự ......................................................... 16 2.2.2. Phép đo khoảng cách ................................................................................... 17 2.3. Phương pháp phân cụm phân hoạch ........................................................................... 18 2.3.1. Giới thiệu phương pháp ............................................................................... 18 2.3.2. Thuật toán K-MEANS................................................................................... 19 2.3.3. Thuật toán PAM ........................................................................................... 21 2.4. Phương pháp phân cụm phân cấp................................................................................ 24 2.4.1. Giới thiệu phương pháp ............................................................................... 24 2.4.2. Thuật toán HERACHICAL ........................................................................... 25 2.4.3. Thuật toán BIRCH ....................................................................................... 28 2.5. Phương pháp phân dựa trên mật độ............................................................................. 31 2.5.1. Giới thiệu phương pháp ............................................................................... 31 2.5.2. Thuật toán DBSCAN .................................................................................... 32 2.6. Phương pháp phân cụm dựa trên lưới ......................................................................... 36 2.6.1. Giới thiệu phương pháp ............................................................................... 36 2.6.2. Thuật toán STING ........................................................................................ 37 2.7. Kết luận chương ........................................................................................................... 40 Chương 3. PHÂN CỤM KẾT QUẢ HỌC TẬP TẠI TRƯỜNG TRUNG HỌC CƠ SỞ CHU VĂN AN .......................................................................................................................................................41 3.1. Bài toán phân cụm kết quả học tập của học sinh tại trường trung học cơ sở Chu Văn An…………………………………………………………………………………….41 3.1.1. Giới thiệu trường Trung học cơ sở Chu Văn An ........................................... 41 3.1.2. Bảng dữ liệu kết quả học tập của học sinh.................................................... 42 3.1.3. Bài toán phân cụm kết quả học tập của học sinh .......................................... 43 3.2. Lựa chọn phương pháp, công cụ ................................................................................. 44 3.2.1. Lựa chọn ngôn ngữ R thực hiện phân cụm.................................................... 44 3.2.2. Các bước thực hiện phân cụm bằng ngôn ngữ R........................................... 46 3.3. Kết quả phân cụm bằng thuật toán K-means .............................................................. 48 3.3.1. Phân cụm học sinh dựa trên kết quả học tập ................................................ 48 3.3.2. Phân cụm học sinh dựa trên điểm trung bình các môn.................................. 52 3.3.3. Phân cụm dựa trên điểm trung bình môn toán và môn văn ........................... 53 v 3.4. Kết luận chương ........................................................................................................... 54 KẾT LUẬN ..................................................................................................................................................55 TÀI LIỆU THAM KHẢO.........................................................................................................................57 vi DANH MỤC CÁC BẢNG Bảng 3.1. Bảng dữ liệu kết quả học tập của học sinh ....................................................... 43 Bảng 3.2. Phân cụm theo kết quả học tập ........................................................................ 48 Bảng 3.3. Thống kê phân cụm theo địa bàn hành chính ................................................... 49 Bảng 3.4. Thống kê phân cụm theo hoàn cảnh gia đình ................................................... 50 Bảng 3.5. Thống kê phân cụm theo dân tộc ..................................................................... 51 Bảng 3.6. Thống kê phân cụm theo giới tính ................................................................... 52 Bảng 3.7. Phân cụm theo điểm trung bình môn toán ........................................................ 52 Bảng 3.8. Phân cụm theo điểm trung bình môn văn ......................................................... 53 vii DANH MỤC CÁC HÌNH Hình 1.1. Quá trình khám phá tri thức............................................................................... 4 Hình 1.2. Quy trình phân cụm .......................................................................................... 8 Hình 2.1. Khởi tạo các đối tượng medoid ....................................................................... 22 Hình 2.2. Cây CF được dùng trong thuật toán BIRCH .................................................... 29 Hình 2.3. Ý tưởng của thuật toán phân cụm phân cấp. .................................................... 31 Hình 2.4. Lân cận với ngưỡng  của điểm p. ................................................................... 32 Hình 2.5. Mật độ liên lạc ................................................................................................ 33 Hình 2.6. Mật độ liên thông ............................................................................................ 34 Hình 2.7. Các mức ô lưới khác nhau trong quá trình truy vấn ......................................... 38 Hình 3. 1. Website của trường Trung học cơ sở Chu Văn An ........................................... 41 Hình 3.2. Cơ cấu tổ chức của trường Trung học cơ sở Chu Văn An ................................. 42 Hình 3.3. Thống kê số học sinh theo điểm toán................................................................ 47 Hình 3.4. Kết quả phân cụm ............................................................................................ 48 1 MỞ ĐẦU 1.1. Sự cần thiết lựa chọn đề tài Sự phát triển của nhanh chóng các ứng dụng công nghệ thông tin và Internet vào nhiều lĩnh vực đời sống xã hội, quản lý kinh tế, khoa học kỹ thuật... trong mấy năm gần đây đã tạo ra nhiều cơ sở dữ liệu khổng lồ. Để khai thác hiệu quả nguồn thông tin từ các cơ sở dữ liệu khổng lồ đó nhằm mục đích dự báo, hỗ trợ ra quyết định, bên cạnh các phương pháp khai thác thông tin truyền thống, các nhà nghiên cứu đã phát triển các phương pháp, kỹ thuật và phần mềm mới hỗ trợ tiến trình khám phá, phân tích, tổng hợp thông tin, lĩnh vực này được gọi là khai phá dữ liệu và khám phá tri thức (Data mining and Knowledge discovery) Khai phá dữ liệu và khám phá tri thức là một lĩnh vực quan trọng của ngành Công nghệ thông tin với mục tiêu là tìm kiếm các tri thức có ích, cần thiết, tiềm ẩn và chưa được biết trước trong cơ sở dữ liệu lớn. Đây là lĩnh vực đã và đang thu hút đông đảo các nhà khoa học trên thế giới và trong nước tham gia nghiên cứu. Khai phá dữ liệu có thể xem là nhiệm vụ quan trọng trong quá trình khám phá tri thức từ cơ sở dữ liệu, bao gồm ba bước chính: thu thập và tiền xử lý dữ liệu; lựa chọn các thuật toán khai phá dữ liệu; đánh giá kết quả và biểu diễn tri thức. Các bài toán quan trọng trong khai phá dữ liệu bao gồm: phân lớp (classification); hồi quy (regression); phân cụm (clustering); khai phá luật kết hợp (rule association)… Các kỹ thuật, công cụ sử dụng trong khai phá dữ liệu bao gồm: cây quyết định; mạng nơron nhân tạo; thuật toán di truyền; các kỹ thuật phân lớp, phân cụm; các phương pháp trong thống kê như phân tích tương quan, phân tích phương sai, hồi quy đơn biến, đa biến... Khai phá dữ liệu có nhiều ứng dụng trong các lĩnh vực khác nhau của đời sống như: phân tích, dự báo trong kinh tế, tài chính; chuẩn đoán bệnh trong y tế; tin sinh học; hỗ trợ quá trình sản xuất, kinh doanh... Phân cụm (clustering) là bài toán có vai trò quan trọng trong khai phá dữ liệu và có nhiều ứng dụng trong thực tiễn. Mục tiêu của phương pháp phân cụm dữ liệu là quá trình nhóm các đối tượng tương tự nhau trong cơ sở dữ liệu vào các cụm sao cho các đối tượng trong cùng một cụm là tương đồng, còn các đối tượng thuộc các 2 cụm khác nhau sẽ không tương đồng. Điểm mạnh của phân cụm dữ liệu là đưa ra được những cấu trúc có ích hoặc những cụm các đối tượng tìm thấy trực tiếp từ dữ liệu mà không cần bất kì một tri thức cơ sở nào. Giống như cách tiếp cận học máy, phân cụm dữ liệu được hiểu như là phương pháp học không có thầy (unsupervised learning). Không giống như phân lớp dữ liệu, phân cụm dữ liệu không đòi hỏi phải định nghĩa trước các mẫu dữ liệu huấn luyện. Vì thế, có thể coi phân cụm dữ liệu là một cách học bằng quan sát (learning by observation), trong khi phân lớp dữ liệu là học bằng ví dụ (learning by example). Trong phương pháp này sẽ không thể biết kết quả các cụm thu được sẽ như thế nào khi bắt đầu quá trình. Vì vậy, cần có một chuyên gia để đánh giá các cụm thu được. Phân cụm dữ liệu được sử dụng nhiều trong các ứng dụng về phân đoạn thị trường, phân đoạn khách hàng, nhận dạng mẫu, phân loại trang Web, phân loại, đánh giá học sinh, sinh viên trong các trường học… Ngoài ra, phân cụm dữ liệu còn có thể được sử dụng như một bước tiền xử lí cho các thuật toán khai phá dữ liệu khác. Là một người công tác trong lĩnh vực giáo dục phổ thông, với mong muốn áp dụng các kiến thức đã học về các phương pháp phân cụm vào bài toán thực tiễn là phân cụm học sinh của trường Trung học cơ sở Chu Văn An, thành phố Thái Nguyên dựa vào kết quả học tập, tác giả luận văn chọn đề tài: “Phân cụm dữ liệu và ứng dụng phân cụm học sinh trường Trung học cơ sở Chu Văn An”. 1.2. Mục tiêu đề tài Nắm bắt được một cách tổng thể các phương pháp phân cụm trong khai phá dữ liệu. Trên cơ sở đó, áp dụng các kỹ thuật phân cụm vào giải quyết bài toán thực tiễn tại địa phương nơi tác giả làm việc là phân cụm kết quả học tập của học sinh trường Trung học cơ sở Chu Văn An, thành phố Thái Nguyên. 1.3. Đối tượng và phạm vi nghiên cứu Đối tượng nghiên cứu của đề tài là các phương pháp phân cụm dữ liệu trong khai phá dữ liệu và cơ sở dữ liệu về kết quả học tập của học sinh trường Trung học cơ sở Chu Văn An, thành phố Thái Nguyên. 3 Phạm vi nghiên cứu của đề tài là áp dụng một số phương pháp phân cụm vào việc giải quyết bài toán phân cụm kết quả học tập của học sinh trường Trung học cơ sở Chu Văn An, thành phố Thái Nguyên. 1.4. Phương pháp nghiên cứu Phương pháp nghiên cứu của luận văn là nghiên cứu lý thuyết và nghiên cứu thực nghiệm. Về nghiên cứu lý thuyết, luận văn đã tổng hợp các kết quả nghiên cứu về các phương pháp phân cụm dữ liệu trong khai phá dữ liệu. Về nghiên cứu thực nghiệm, luận văn cài đặt và thử nghiệm một số thuật toán phân cụm trên dữ liệu học sinh của trường Trung học cơ sở Chu Văn An. 1.5. Cấu trúc của luận văn Cấu trúc luận văn gồm: mở đầu, ba chương chính, kết luận và tài liệu tham khảo. Phần mở đầu: Lý do chọn đề tài và bố cục luận văn Chương 1: Giới thiệu tổng quan về khai phá dữ liệu và phân cụm dữ liệu. Chương 2: Trình bày một số phương pháp và thuật toán phân cụm dữ liệu, bao gồm phân cụm phân hoạch, phân cụm phân cấp, phân cụm dựa trên mật độ, phân cụm dựa trên lưới, phân cụm dựa trên mô hình, phân cụm mờ… Chương 3: Trình bày kết quả thử nghiệm một số thuật toán phân cụm để giải quyết bài toán phân cụm học sinh trường Trung học cơ sở Chu Văn An, bao gồm phát biểu bài toán, lựa chọn thuật toán, công cụ phát triển (lập trình, cơ sở dữ liệu), đánh giá kết quả thử nghiệm. Phần kết luận: Tóm tắt các kết quả đạt được và hướng phát triển tiếp của đề tài. 4 Chương 1. TỔNG QUAN Chương này giới thiệu tổng quan về quá trình khám phá tri thức từ dữ liệu, khai phá dữ liệu và bài toán phân cụm trong khai phá dữ liệu. 1.1. Quá trình khám phá tri thức Cùng với sự phát triển vượt bậc của các công nghệ điện tử và truyền thông đã làm cho khả năng thu thập, lưu trữ và xử lý dữ liệu cho các hệ thống tin học không ngừng nâng cao. Bên cạnh đó, việc tin học hoá nhiều lĩnh vực của cuộc sống đã tạo ra cho chúng ta một kho dữ liệu khổng lồ. Quá trình khám phá tri thức trong Cơ sở dữ liệu (Knowledge Discovery in Databases) đang là một vấn đề thời sự của nền công nghệ thông tin thế giới hiện nay. Nó được ứng dụng vào nhiều lớp bài toán thực tế khác nhau và thu được nhiều thành quả to lớn. Khám phá tri thức trong cơ sở dữ liệu là một quá trình nhận biết đúng đắn, mới, hữu ích và cuối cùng là có thể hiểu được mẫu hoặc mô hình trong dữ liệu. Quá trình khám phá tri thức có thể bao gồm các bước như Hình 1.1 [7] Dữ liệu thô Tri thức Trích chọn dữ liệu Tiền xử lý dữ liệu Biến đổi dữ liệu Đánh giá và giải thích Khai phá dữ liệu Hình 1.1. Quá trình khám phá tri thức - Trích chọn dữ liệu: Là bước trích chọn những tập dữ liệu cần được khai phá từ tập dữ liệu lớn ban đầu theo một tiêu chí nhất định. Đây là bước quan trọng để rút ra những tri thức hữu ích và chọn phương pháp khai phá dữ liệu phù hợp với mục đích ứng dụng và bản chất dữ liệu. - Tiền xử lý dữ liệu: Là bước làm sạch dữ liệu: lựa chọn dữ liệu nguồn, loại bỏ các dữ liệu nhiễu hoặc ngoại lai, xử lý các giá trị không đầy đủ, biến đổi và rút gọn dữ liệu, sửa các lỗi mang tính hệ thống, tập hợp các thông tin cần 5 thiết để mô hình hoặc tính toán nhiễu, quyết định các chiến lược xử lý các trường dữ liệu bị lỗi. Sau bước này dữ liệu sẽ nhất quán, đầy đủ, được rút gọn và được rời rạc hoá. - Biến đổi dữ liệu: Đây là bước chuẩn hoá và làm mịn dữ liệu để đưa dữ liệu về dạng thuận lợi nhất nhằm phục vụ cho kỹ thuật khai phá ở bước sau. - Khai phá dữ liệu: Áp dụng các kỹ thuật phân tích nhằm để khai thác dữ liệu, trích chọn các mẫu ẩn hoặc mô hình trong dữ liệu. Một mô hình có thể xem như là một biểu diễn tổng thể của cấu trúc nhằm tóm lược các thành phần mang tính hệ thống có trong dữ liệu hoặc mô tả dữ liệu phát sinh. Ngược lại, một mẫu là một cấu trúc cục bộ có khi chỉ liên quan tới một nhóm các biến và một số trường hợp. - Đánh giá và biểu diễn tri thức: Những mẫu thông tin và mối liên hệ trong dữ liệu đã được khám phá ở bước trên được chuyển dạng và được biểu diễn ở một dạng gần gũi với người sử dụng, đồng thời đánh giá những tri thức khám phá được theo những tiêu chí nhất định. Đặc biệt là làm sáng tỏ các mô tả và dự đoán, hai mục tiêu chính của các hệ thống khám phá trong thực tế. Kinh nghiệm cho thấy rằng các mẫu hoặc mô hình phát hiện được từ các dữ liệu không phải lúc nào cũng đáng quan tâm và có thể trực tiếp sử dụng được ngay, quy trình khám phá tri thức được lặp đi lặp lại có điều chỉnh theo các tri thức phát hiện được. Để đánh giá được các luật áp dụng trong quy trình khám phá tri thức, dữ liệu thường được chia thành hai tập, huấn luyện trên tập thứ nhất và kiểm chứng trên tập thứ hai. Có thể lặp lại quy trình này với một số lần với các phần chia khác nhau, sau đó lấy trung bình các kết quả để ước lượng các luật thi hành. 1.2. Khai phá dữ liệu 1.2.1. Khái niệm khai phá dữ liệu Khai phá dữ liệu (Data mining) là quá trình tìm kiếm, phát hiện các tri thức mới, tiềm ẩn, hữu dụng trong các cơ sở dữ liệu lớn, các kho dữ liệu...Các kết quả 6 khoa học cùng những thành công trong khám phá tri thức cho thấy khai phá dữ liệu là một lĩnh vực mang lại nhiều lợi ích và có triển vọng, có ưu thế hơn hẳn so với các công cụ phân tích dữ liệu truyền thống. Khai phá dữ liệu là một lĩnh vực có liên quan đến rất nhiều ngành khoa học khác như: Hệ cơ sở dữ liệu, thống kê, học máy, trực quan hoá.Tuỳ vào cách tiếp cận được sử dụng thì khai phá dữ liệu còn áp dụng một số kỹ thuật khác như mạng nơron, lý thuyết tập thô hoặc tập mờ, biểu diễn tri thức .So với các phương pháp này, khai phá dữ liệu có một số ưu thế rõ rệt. So với phương pháp học máy, khai phá dữ liệu có thể sử dụng dữ liệu có nhiều nhiễu, dữ liệu không đầy đủ hoặc biến đổi liên tục. Trong khi đó, phương pháp học máy đòi hỏi tập dữ liệu phải đầy đủ, ít biến động và không quá lớn. Phương pháp hệ chuyên gia, các ví dụ của chuyên gia thường phải đòi hỏi chất lượng cao hơn nhiều so với dữ liệu trong cơ sở dữ liệu. Phương pháp thống kê là một trong những nền tảng lý thuyết của khai phá dữ liệu nhưng khai phá dữ liệu đã khắc phục được một số tồn tại của phương pháp thống kê như: Các phương pháp thống kê chuẩn không phù hợp với các kiểu dữ liệu có cấu trúc trong rất nhiều kiểu cơ sở dữ liệu, nó hoạt động hoàn toàn theo dữ liệu, nó không sử dụng tri thức sẵn có của lĩnh vực, kết quả phân tích của thống kê rất nhiều và khó có thể làm rõ được, phương pháp thống kê cần có sự hướng dẫn của người dùng để xác định phân tích dữ liệu như thế nào và ở đâu. Với những ưu điểm đó, khai phá dữ liệu đang được áp dụng vào nhiều lĩnh vực như tài chính, ngân hàng, bảo hiểm, y tế, an ninh, internet.. .Các công ty phần mềm lớn trên thế giới cũng đã rất quan tâm chú trọng việc nghiên cứu và phát triển các kỹ thuật khai phá dữ liệu: Oracle tích hợp các công cụ khai phá dữ liệu vào bộ Oracle9i, IBM phát triển khai phá dữ liệu với các ứng dụng như Intelligence Miner…[5]. 1.2.2. Các kỹ thuật khai phá dữ liệu Nếu đứng trên quan điểm của học máy (Machine learning) thì kỹ thuật khai phá dữ liệu bao gồm: 7 - Học có giám sát (supervised learning): là quá trình gán nhãn lớp cho các phần tử trong cơ sở dữ liệu dựa trên một tập các ví dụ huấn luyện và các thông tin về nhãn lớp đã biết. Đây là một kỹ thuật của ngành học máy để xây dựng một hàm từ dữ liệu huấn luyện. Dữ liệu huấn luyện bao gồm các cặp gồm đối tượng đầu vào và đầu ra mong muốn. Đầu ra của một hàm có thể là một giá trị liên tục (gọi là hồi qui), hay có thể là dự đoán một nhãn phân loại cho một đối tượng đầu vào (gọi là phân loại). Nhiệm vụ của chương trình học có giám sát là dự đoán giá trị của hàm cho một đối tượng bất kì là đầu vào hợp lệ, sau khi đã xem xét một số ví dụ huấn luyện (các cặp đầu vào và đầu ra tương ứng). Để đạt được điều này, chương trình học phải tổng quát hóa từ các dữ liệu sẵn có để dự đoán được những tình huống chưa gặp phải theo một cách “hợp lý”. - Học không có giám sát (unsupervised learning): là quá trình phân chia một tập dữ liệu thành các lớp hay là cụm (clustering) dữ liệu tương tự nhau mà chưa biết trước các thông tin về lớp một phương pháp của ngành học máy nhằm tìm ra một mô hình mà phù hợp với các quan sát. Nó khác biệt với học có giám sát ở chỗ là đầu ra đúng tương ứng cho mỗi đầu vào là không biết trước. Trong học không có giám sát, một tập dữ liệu đầu vào được thu thập. Học không có giám sát thường đối xử với các đối tượng đầu vào như là một tập các biến ngẫu nhiên. Sau đó, một mô hình mật độ kết hợp sẽ được xây dựng cho tập dữ liệu đó [4]. - Học nửa giám sát (semi-supervised learning): là quá trình phân chia một tập dữ liệu thành các lớp dựa trên một tập dữ liệu nhỏ các ví dụ huấn luyện và một số các thông tin về một số nhãn lớp đã biết trước. Nếu căn cứ vào lớp các bài toán cần giải quyết thì kỹ thuật khai phá dữ liệu gồm các kỹ thuật sau: - Kỹ thuật khai phá dữ liệu mô tả: Có nhiệm vụ mô tả về các tính chất hoặc các đặc tính chung của dữ liệu trong cơ sở dữ liệu hiện có. Các kỹ thuật loại này gồm có: Phân cụm (Clustering), tóm tắt (Summarization), trực quan hoá 8 (Visualization), phân tích sự phát triển và độ lệch (Evolution and deviation analysis), phân tích luật kết hợp (Association rules),... - Kỹ thuật khai phá dữ liệu dự đoán: Có nhiệm vụ đưa ra các dự đoán dựa vào các suy diễn trên dữ liệu hiện tại. Các kỹ thuật loại này gồm có: Phân lớp (Classification), hồi quy (Regression),... 1.3. Phân cụm dữ liệu 1.3.1. Khái niệm về phân cụm dữ liệu Phân cụm dữ liệu (PCDL) là một kỹ thuật trong khai phá dữ liệu nhằm tìm kiếm, phát hiện các cụm, các mẫu dữ liệu tự nhiên tiềm ẩn, quan tâm trong tập dữ liệu lớn, từ đó cung cấp thông tin hữu ích cho việc ra quyết định. Như vậy phân cụm dữ liệu là kỹ thuật sử dụng quan sát đối tượng để nhóm các đối tượng thành các cụm hoặc chia một tập dữ liệu ban đầu thành các cụm sao cho: - Các đối tượng trong cùng một cụm là giống nhau hoặc gần giống nhau được xác định bằng độ tương tự. Hay nói một cách khác, các đối tượng trong cùng một cụm là tương tự với nhau. - Các đối tượng thuộc các cụm khác nhau sẽ không tương tự (phi tương tự) với nhau. Vậy có thể hiểu một cách đơn giản là “Phân cụm là quá trình tổ chức các đối tượng thành các nhóm sao cho các đối tượng trong cùng một nhóm là tương tự với nhau”. Quy trình này được thể hiện như Hình 1.2. Thuật toán N đối tượng Phân cụm Hình 1.2. Quy trình phân cụm K nhóm 9 Số các cụm được xác định tuỳ thuộc vào phương pháp phân cụm. Các thuật toán phân cụm tìm các nhóm chứa đối tượng tương tự nhau. Hai hay nhiều đối tượng được xếp vào cùng một cụm nếu chúng có chung một định nghĩa về khái niệm hoặc chúng xấp xỉ với các khái niệm được mô tả trước. Một cụm là các đối tượng có thể xem như là một nhóm trong nhiều ứng dụng. Mặt khác, phân cụm là học bằng quan sát hơn là học bằng ví dụ nên còn được gọi là học không giám sát. Hầu hết các nhiệm vụ chính của khai phá dữ liệu, bắt đầu ở ngoài với một tập huấn luyện chưa phân lớp và thử phát triển một mô hình có khả năng dự đoán một bản ghi mới sẽ được phân lớp như thế nào. Trong phân cụm, không có dữ liệu được phân lớp trước và không có sự phân biệt giữa các biến độc lập và biến phụ thuộc. Trong học máy, phân cụm là một vấn đề quan trọng của học không có giám sát, vì nó phải đi giải quyết vấn đề tìm một cấu trúc trong tập hợp các dữ liệu chưa biết trước thông tin về lớp hay thông tin về tập ví dụ huấn luyện. Trong nhiều trường hợp, khi phân lớp được xem là vấn đề học có giám sát thì phân cụm dữ liệu là một bước trong phân lớp dữ liệu, trong đó phân cụm sẽ khởi tạo các lớp cho phân lớp bằng cách xác định các nhãn cho các nhóm dữ liệu [14, 15]. 1.3.2. Một số vấn đề trong phân cụm dữ liệu - Xử lý nhiễu: Hầu hết các dữ liệu sử dụng để phân cụm đều bị nhiễu do quá trình thu thập thiếu chính xác hay thiếu đầy đủ. Vì vậy cần phải xây dựng chiến lược cho bước tiền xử lý dữ liệu nhằm khắc phục hoặc loại bỏ nhiễu trước khi chuyển sang giai đoạn phân tích cụm dữ liệu. Dữ liệu bị nhiễu là dữ liệu không chính xác hay là dữ liệu khuyết thiếu thông tin về một số thuộc tính. Một trong các kỹ thuật xử lý nhiễu hiện nay là việc thay thế giá trị các thuộc tính của đối tượng nhiễu bằng các giá trị thuộc tính tương ứng. 10 - Dò tìm phần tử ngoại lai: Phần tử ngoại lai là một nhóm nhỏ các đối tượng dữ liệu khác thường so với các dữ liệu trong cơ sở dữ liệu. Loại bỏ những dữ liệu kiểu này để tránh ảnh hưởng đến kết quả phân cụm. - Phân cụm đang là vấn đề mở và khó: Vì phân cụm đang phải giải quyết nhiều vấn đề cơ bản như: 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 các 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. Hiện nay, chưa có một phương pháp phân cụm tổng quát nào có thể giải quyết trọn vẹn cho tất cả các dạng cấu trúc dữ liệu. Với những loại dữ liệu hỗn hợp thì việc phân cụm càng trở nên khó khăn và đây đang là một trong những thách thức lớn trong lĩnh vực khai phá dữ liệu. 1.3.3. Mục tiêu của phân cụm dữ liệu Mục tiêu của phân cụm là xác định được bản chất nhóm trong tập dữ liệu chưa có nhãn. Nhưng để có thể quyết định được cái gì tạo thành một cụm tốt. Nó đòi hỏi người sử dụng phải đưa ra một số tiêu chuẩn mà theo cách đó kết quả phân cụm sẽ đáp ứng được yêu cầu. Ví dụ như quan tâm đến việc tìm đại diện cho các nhóm đồng nhất (rút gọn dữ liệu), tìm kiếm các nhóm hữu ích và phù hợp (các lớp dữ liệu hữu ích), tìm kiếm các đối tượng khác thường (dò tìm phần tử ngoại lai)... 1.3.4. Các bước cơ bản trong phân cụm dữ liệu - Chọn lựa đặc trưng: các đặc trưng phải được chọn lựa một cách hợp lý để có thể mã hoá nhiều nhất thông tin liên quan đến công việc quan tâm. Mục tiêu chính là phải giảm thiểu sự dư thừa thông tin giữa các đặc trưng. Các đặc trưng cần được tiền xử lý trước khi dùng chúng trong các bước sau. - Chọn độ đo gần gũi: đây là một độ đo chỉ ra mức độ tương tự hay không tương tự giữa hai vectơ đặc trưng. Phải đảm bảo rằng tất cả các vectơ đặc trưng góp phần như nhau trong việc tính toán độ đo gần gũi và không có đặc 11 trưng nào át hẳn đặc trưng nào, điều này được đảm bảo bởi quá trình tiền xử lý. - Tiêu chuẩn phân cụm: điều này phụ thuộc vào sự giải thích của chuyên gia cho thuật ngữ “dễ nhận thấy” dựa vào loại của các cụm được chuyên gia cho rằng đang ẩn giấu dưới tập dữ liệu. Chẳng hạn, một cụm loại chặt của véctơ đặc trưng trong không gian n chiều có thể dễ nhận thấy theo một tiêu chuẩn, trong khi một cụm loại “dài và mỏng” lại có thể được dễ nhận thấy bởi một tiêu chuẩn khác. Tiêu chuẩn phân loại có thể được diễn đạt bởi hàm chi phí hay một vài loại quy tắc khác. - Thuật toán phân loại: cần lựa chọn một sơ đồ thuật toán riêng biệt nhằm làm sáng tỏ cấu trúc phân cụm của tập dữ liệu. - Công nhận kết quả: khi đã có kết quả phân loại thì ta phải kiểm tra tính đúng đắn của nó. Điều này thường được thực hiện bởi việc dùng các kiểm định phù hợp. - Giải thích kết quả: trong nhiều trường hợp, chuyên gia trong lĩnh vực ứng dụng phải kết hợp kết quả phân loại với những bằng chứng thực nghiệm và phân tích để đưa ra các kết luận đúng đắn. Trong một số trường hợp, nên có cả bước phân tích khuynh hướng phân cụm, trong bước này có các kiểm định khác nhau để chỉ ra tập dữ liệu có hay không một cấu trúc phân cụm. Ví dụ như tập dữ liệu của ta có thể hoàn toàn ngẫu nhiên vì vậy mọi cố gắng phân cụm đều là vô nghĩa. Các lựa chọn khác nhau của các đặc trưng, độ đo gần gũi, tiêu chuẩn phân cụm có thể dẫn tới các kết quả phân cụm khác nhau. 1.3.5. Yêu cầu của phân cụm dữ liệu Thuật toán phân cụm phải thoả mãn một số yêu cầu sau: - Có khả năng mở rộng: Một số thuật toán có thể áp dụng tốt với tập dữ liệu nhỏ nhưng lại không hiệu quả khi áp dụng cho tập dữ liệu lớn. - Thích nghi với các kiểu thuộc tính khác nhau của dữ liệu. 12 - Khám phá các cụm với hình thù bất kỳ: Hầu hết các cơ sở dữ liệu có chứa các cụm dữ liệu với các hình thù khác nhau như hình lõm, hình cầu,... - Tối thiểu lượng tri thức cần cho xác định các tham số đầu vào: Các giá trị đầu vào thường rất ảnh hưởng đến thuật toán phân cụm và rất phức tạp để xác định các giá trị đầu vào thích hợp đối với các cơ sở dữ liệu lớn. - Khả năng thích nghi với các dữ liệu nhiễu hoặc ngoại lai. - Ít nhạy cảm với thứ tự của dữ liệu vào: Cùng một tập dữ liệu khi đưa vào phân nhóm với các thứ tự khác nhau thì không ảnh hưởng đến kết quả phân cụm. - Thích nghi với dữ liệu đa chiều: Thuật toán áp dụng hiệu quả cho dữ liệu với số chiều khác nhau. - Dễ hiểu và dễ sử dụng. 1.3.6. Ứng dụng của phân cụm dữ liệu Phân cụm là một công cụ quan trọng trong một số ứng dụng sau: - Giảm dữ liệu: Từ một số lượng lớn dữ liệu, phân cụm sẽ nhóm các dữ liệu này thành cụm dữ liệu nhỏ dễ nhận thấy sau đó xử lý mỗi cụm như một đối tượng đơn. - Rút ra các giả thuyết: Các giả thuyết này có liên quan đến tính tự nhiên của dữ liệu phải được kiểm tra bởi việc dùng một số tập dữ liệu khác. - Kiểm định giả thuyết: Phân cụm để xét xem có tồn tại một cụm nào đó trong tập dữ liệu thoả mãn các giả thiết đã cho hay không. - Dự đoán dựa trên các cụm: Trước hết ta phải phân cụm một tập dữ liệu thành các cụm mang đặc điểm của các dạng mà nó chứa. Sau đó, khi có một dạng mới chưa biết xác định xem nó có khả năng thuộc về cụm nào nhất và dự đoán được một số đặc điểm của dạng này nhờ các đặc trưng chung của cả cụm. Trong thực tế, phân cụm được áp dụng vào nhiều lĩnh vực khác nhau như: - Tìm kiếm dữ liệu trên mạng: kết quả được phân thành các cụm tuỳ theo độ tương tự với dữ liệu cần tìm. 13 - Marketing: trợ giúp cán bộ thị trường phát hiện được những phân đoạn thị trường để có chiến lược, sản phẩm hợp lý đối với các phân đoạn đó. - Phân loại khách hàng sử dụng các sản phẩm của Ngân hàng và các ngành tài chính, bảo hiểm... - Lập bản đồ thành phố theo nhóm các loại nhà ở, giá trị tài sản hay vị trí địa lý. Phân cụm đang là một vấn đề thời sự của ngành công nghệ thông tin thế giới hiện tại. Ngoài các ứng dụng phổ biến đã được biết tới, thời gian gần đây, phân cụm dữ liệu đã mở rộng phạm vi ứng dụng. Các kỹ thuật phân cụm đã được sử dụng trong các lĩnh vực như: Nhận dạng mẫu, so sánh, phân lớp,.. .Kỹ thuật phân cụm là sự kết hợp từ nhiều phương pháp khác nhau như: Toán, vật lý, thống kê, khoa học máy tính, trí tuệ nhân tạo, cơ sở dữ liệu [7]. Hiện nay, phân cụm dữ liệu đã được nhiều công ty phần mềm nổi tiếng trên thế giới tích hợp vào bộ công cụ trong sản phẩm của mình. 1.4. Kết luận chương Chương 1 trình bày tổng quan về quá trình phát hiện tri thức từ cơ sở dữ liệu và khái niệm về khai phá dữ liệu. Chương này cũng trình bày các khái niệm cơ bản về bài toán phân cụm dữ liệu và các ứng dụng của phân cụm dữ liệu trong các bài toán thực tế. Các khái niệm được trình bày trong Chương 1 là kiến thức nền tảng cho các phương pháp phân cụm dữ liệu được trình bày trong Chương 2.