Cơ sở lý thuyết Phân cụm dữ liệu

Chia sẻ: Tuan Anh | Ngày: | Loại File: DOCX | Số trang:3

Thêm vào BST

Báo xấu

209
lượt xem 21
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Giới thiệu về phân cụm dữ liệu ở 1 mức cơ bản nhất, ta có khái niệm về phân cụm như sau:“ PCDL là 1 kỹ thuật trong DM 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 dữ liệu lớn , từ đó cung cấp thông tin, tri thức hữa ích cho ra quyết định”.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Cơ sở lý thuyết Phân cụm dữ liệu

Chương 1 CƠ SỞ LÝ THUYẾT 1.1 tổng quan về phân cụm dữ liệu 1.1.1. giới thiệu về phân cụm dữ liệu ở 1 mức cơ bản nhất, ta có khái niệm về phân cụm như sau: “ PCDL là 1 kỹ thuật trong DM 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 dữ liệu lớn , từ đó cung cấp thông tin, tri thức hữa ích cho ra quyết định”. Như vậy, PC là quá trình phân chia 1 tập dữ liệu ban đầu thành các cụm dữ liệu sao cho các phần tử trong 1 cụm “tương tự ” với nhau và các phần tử trong các cụm khác nhau sẽ “phi tương tự” với nhau,Số cụm dữ liệu có thể xác định trước theo kinh nghiệm hoặc có thể tự động xác định của phương pháp phân cụm. Trong học máy, PCDL được xem là vấn đề học ko có giám sát, vì nó phải đi giải quyết vấn đề tìm 1 cấu trúc trong tập hợp cá dữ liệu chưa biết trước thông tin về các lớp hay các 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 vấn đề học có giám sát thì PCDL là 1 bước trong phân lớp dữ liệu, trong đó PCDL sẽ khởi tạo các lớp cho phân lớp bằng các xác định các nhãn cho nhóm dữ liệu. Một vần đề thường gặp trong PCDL,đó là hầu hết các dữ liệu cần PC đều có chứa dl “nhiễu” do quá trình thu thập thiếu chính xác hoặc thiếu đầy đủ, vì vậy 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 bước vào giai đoạn phân cụm dữ liệu.”Nhiễu ” ở đây có thể là các đối tượng dữ liệu không chính xác hoặc là dữ liệu khuyết thiếu thông tin về 1 số thuộc tính.Một trong các kỹ thuật xử lý nhiễu phổ biến là việc thay thế giá trị của các thuộc tính của đối tượng “nhiễu” bằng giá trị thuộc tính tương ứng của đối tượng dữ liệu gần nhất Ngoài ra, dò tìm phần tử ngoại lai (Outlier) là một trong những hướng nghiên cứu quan trọng trong Phân cụm dữ liệu, cũng như trong Data Mining, chức năng của nó là xác định 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 CSDL - tức là các đối tượng dữ liệu không tuân theo các hành vi hoặc mô hình dữ liệu - nhằm tránh sự ảnh hưởng của chúng tới kết quả của Phân cụm dữ liệu. Tóm lại, phân cụm dữ liệu nhằm lắm giữ lượng thông tin khổng lồ, vì xử lý mọi thông tin như một thực thể đơn lẻ là không thể. Vì vậy chúng ta phân loại các thực thể thành các nhóm, mỗi nhóm được đặc trưng bởi các thuộc tính chung của tất cả các thực thể mà nó chứa. Các bước cơ bản để phân cụm gồm có: • Chọn lựa các đặc trưng: các đặc trưng được chọn lựa một cách hợp lý để có thể “mã hoá” nhiều thông tin liên quan đến phân cụm dữ liệu. 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. • Tiêu chuẩn phân cụm: tùy theo từng tập dữ liệu tạo ra các cụm khác nhau mà chúng ta có tiêu chuẩn phân cụm khác nhau. Chẳng hạn, một cụm loại chặt (compact) của các véc tơ đặc trưng trong không gian l-chiều có thể dễ nhận thấy theo một tiêu chuẩn, trong khi một cụm “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í • Thuật toán phân cụm: sử dụng các giải thuật phân cụm khác nhau nhằm sáng t ỏ cấu trúc 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 quả đú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, t rong 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, 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. Do đó việc lựa chọn một cách hợp lý nhất, hoàn toàn dựa vào kiến thức và kinh nghiệm của chuyên gia. Theo các nghiên cứu, đến nay chưa có một phương pháp phân cụm tổn g 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 cụm dữ liệu. Hơn nữa, các phương pháp phân cụm cần có cách thức biểu diễn cấu trúc của các cụ m dữ liệu, với mỗi cách thức biểu diễn khác nhau sẽ có tương ứng một thuật toán phân cụm phù hợp. Phân cụm dữ liệu đang là vấn đề mở và khó, vì cần phải đi giải quyế t nhiều vấn đề cơ bản như đã đề cập ở trên một cách trọn vẹn và phù hợp với nhiều dạng dữ liệu khác nhau, đặc biệt là đối với các dữ liệu hỗn hợp, đang ngày càng tăng trưởng không ngừng trong các hệ quản trị dữ liệu, đây cũng là một trong những thách thức lớn trong lĩnh vực Data Mining trong những thập kỷ tiếp theo. 1.1.2 Các ứng dụng của PCDL Phân cụm rất quan trọng trong một số ứng dụng, sau đây là một số ứng dụng của nó: • Giảm dữ liệu: Giả sử ta có một lượng lớn dữ liệu (N). Phân cụm sẽ nhóm các
dữ liệu này thành C cụm dữ liệu dễ nhận thấy và C