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

và các phƣơng pháp đã biết để tìm kiếm các mẫu trong dữ liệu, chọn ra các mẫu hữu ích. 5. Trình bày và đánh giá: Từ các mẫu khai phá đƣợc tiến hành đánh giá hoặc phiên dịch thành những tri thức hiểu đƣợc. Trình bày, đánh giá Tri thức Khai phá Chuyển đổi Tiền xử lý dữ liệu Trích chọn DL Các mẫu DL đã DL DL qua chuyển tiền xử đổi lý đã chọn Hình 1: Quá trình khám phá tri thức trong CSDL Trang 11 1.2. Khái niệm khai phá dữ liệu (Data mining) Data mining là một công đoạn, cũng là một khâu quan trọng nhất trong quá trình KDD. 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 nê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: Data mining là một quá trình tìm kiếm, chắt lọc các tri thức mới, tiềm ẩn, hữu dụng trong tập dữ liệu lớn. 1.3. Các phương pháp khai phá dữ liệu 1.3.1. Các nhiệm vụ của khai phá dữ liệu Một số nhiệm vụ của khai phá dữ liệu:  Phân lớp và dự đoán: Xếp đối tƣợng vào một trong các lớp đã biết trƣớc, dự báo giá trị có thể đúng của những dữ liệu bị thiếu hoặc sự phân bố của thuộc tính nào đó trong dữ liệu. Phân lớp còn đƣợc gọi là học có giám sát.  Luật thuộc tính: Tóm tắt những thuộc tính chung của tập dữ liệu nào đó trong cơ sở dữ liệu.  Luật kết hợp: Là dạng luật biểu diễn tri thức ở dạng tƣơng đối đơn giản. Giả sử có hai tập thuộc tính {A1, A2,…An} và {B1, B2,…Bm} thì luật kết hợp có dạng (A1 A2…An)  (B1 B2…Bm )  Khai thác mẫu tuần tự: Tƣơng tự nhƣ khai thác luật kết hợp nhƣng có thêm tính thứ tự và tính thời gian. Một luật mô tả mẫu tuần tự có dạng tiêu biểu X → Y phản ánh sự xuất hiện của biến cố X sẽ dẫn đến việc xuất hiện kế tiếp biến cố Y. Hƣớng tiếp cận này có tính dự báo cao. Trang 12  Phân cụm: Sắp xếp các đối tƣợng theo từng cụm (số lƣợng và tên của cụm chƣa đƣợc biết trƣớc). Các đối tƣợng đƣợc gom cụm sao cho mức độ tƣơng tự giữa các đối tƣợng trong cùng một cụm là lớn nhất và mức độ tƣơng tự giữa các đối tƣợng nằm trong các cụm khác nhau là nhỏ nhất. Phân cụm còn đƣợc gọi là học không có giám sát. 1.3.2. Phân loại Data mining đƣợc phân loại theo hai quan điểm sau: a. Theo quan điểm của học máy  Học có giám sát: 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: Là quá trình phân chia một tập dữ liệu thành các lớp hay cụm 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: 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. b. Theo các lớp bài toán cần giải quyết  Phân lớp và dự đoán: Đƣa mỗi đố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: 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. Trang 13  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. 1.4.  Ứng dụng của khai phá dữ liệu Bảo hiểm, tài chính và thị trường chứng khoán: Phân tích tình hình tài chính và dự báo giá của các loại cổ phiếu trong thị trƣờng chứng khoán. Danh mục vốn và giá, lãi suất, dữ liệu thẻ tín dụng, phát hiện gian lận.  Điều trị y học và chăm sóc y tế: Phân tích mối liên hệ giữa triệu chứng bệnh, chẩn đoán và phƣơng pháp điều trị (chế độ dinh dƣỡng, thuốc).  Sản xuất và chế biến: Qui trình, phƣơng pháp chế biến và xử lý sự cố.  Text mining & Web mining: Phân lớp văn bản và các trang web, tóm tắt văn bản.  Lĩnh vực khoa học: Quan sát thiên văn, dữ liệu gene, dữ liệu sinh vật học, tìm kiếm, so sánh các hệ gene và thông tin di truyền, mối liên hệ gene và một số bệnh di truyền.  Lĩnh vực viễn thông: Các ứng dụng Data mining đƣợc phát triển trong ngành viễn thông đƣợc chia thành 3 nhóm ứng dụng khác nhau là phát hiện gian lận, các ứng dụng hỗ trợ tiếp thị và quản lý khách hàng, cuối cùng là các ứng dụng về phát hiện và xử lý lỗi hệ thống mạng.  Lĩnh vực khác: Môi trƣờng, thể thao, âm nhạc,… Trang 14 Chương 2 PHÂN CỤM DỮ LIỆU VÀ CÁC THUẬT TOÁN ĐIỂN HÌNH 2.1. Khái niệm 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ó đối với 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: 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 đó, PCDL là quá trình phân chia một tập dữ liệu ban đầu thành các cụm dữ liệu, sao cho các đố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. 2.2. Các kiểu dữ liệu và độ đo tương tự 2.2.1. Phân loại kiểu dữ liệu dựa trên kích thước miền  Thuộc tính liên tục: Nếu miền giá trị là vô hạn không đếm đƣợc.  Thuộc tính rời rạc: Nếu miền giá trị là tập hữu hạn hoặc đếm đƣợc. 2.2.2. Phân loại kiểu dữ liệu dựa trên hệ đo Giả sử có hai đối tƣợng x, y và các thuộc tính xi, yi tƣơng ứng với thuộc tính thứ i của chúng. Chúng ta có các lớp kiểu dữ liệu nhƣ sau:  Thuộc tính định danh: Là dạng thuộc tính khái quát hóa 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ự, có nhiều Trang 15 hơn hai phần tử - nghĩa là nếu x và y là hai đối tƣợng thuộc tính thì chỉ có thể xác định là x ≠ y hoặc x = y.  Thuộc tính có thứ tự: Là thuộc tính định danh có thêm tính thứ tự, nhƣng chúng không đƣợc định lƣợng. Nếu x và y là hai thuộc tính thứ tự thì ta có thể xác định là x ≠ y hoặc x = y hoặc x > y hoặc x < y.  Thuộc tính khoảng: Nhằm để đ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 là đứng trƣớc hay đứng sau thuộc tính khác với một khoảng là bao nhiêu. Nếu xi > yi thì ta nói x cách y một khoảng xi  yi tƣơng ứng với thuộc tính thứ i  Thuộc tính tỷ lệ: Là thuộc tính khoảng cách nhƣng đƣợc xác định một cách tƣơng đối so với điểm mốc. Thí dụ nhƣ thuộc tính chiều cao hoặc cân nặng lấy giá trị 0 làm mốc. Ngƣời ta còn đặc biệt quan tâm đến dữ liệu không gian. Dữ liệu không gian có thể là dữ liệu liên tục hoặc rời rạc.  Dữ liệu không gian rời rạc: Có thể là một điểm trong không gian nhiều chiều và cho phép ta xác định đƣợc khoảng cách giữa các đối tƣợng dữ liệu trong không gian.  Dữ liệu không gian liên tục: Bao gồm một vùng trong không gian. 2.2.3. Phép đo độ tương tự, phi tương tự Khi các đặc tính của dữ liệu đƣợc xác định, ngƣời ta tìm cách thích hợp để xác định “khoảng cách” giữa các đối tƣợng. Đây 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ự” hoặc tính độ “phi tương tự” 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 các đối tƣợng càng lớn và ngƣợc lại. Ứng với mỗi kiểu dữ liệu thì có một hàm tính độ Trang 16