zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Công Nghệ Thông Tin

» Kỹ thuật lập trình

, luật kết hợp, khai phá luật kết hợp-Các kỹ thuật phân nhóm

Chia sẻ: Trần Ngọc Phương | Ngày: | Loại File: PDF | Số trang:35

Báo xấu

154
lượt xem 40
download

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

Học có giám sát (Supervised learning) Tập dữ liệu (dataset) bao gồm các ví dụ, mà mỗi ví dụ được gắn kèm với một nhãn lớp/giá trị đầu ra mong muốn. Mục đích là học (xấp xỉ) một giả thiết (vd: một phân lớp, một hàm mục tiêu,...) phù hợp với tập dữ liệu hiện có. Giả thiết học được (learned hypothesis) sau đó sẽ được dùng để phân lớp/dự đoán đối với các ví dụ mới.

Chủ đề:

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

Lưu

Nội dung Text: , luật kết hợp, khai phá luật kết hợp-Các kỹ thuật phân nhóm

Khai Phá Dữ Liệu Nguyễn Nhật Quang quangnn-fit@mail.hut.edu.vn Viện Công nghệ Thông tin và Truyền thông Trường Đại học Bách Khoa Hà Nội Năm học 2010-2011
Nội dung môn học: Giới thiệu về Khai phá dữ liệu Giới thiệu về công cụ WEKA Tiền xử lý dữ liệu Phát hiện các luật kết hợp Các kỹ thuật phân lớp và dự đoán thu phân và Các kỹ thuật phân nhóm Phân nhóm dựa trên chia cắt (k-Means) nhóm trên chia (k Phân nhóm dựa trên tích tụ phân cấp (HAC) Khai Phá Dữ Liệu 2
Học có vs. không có giám sát Học có giám sát (Supervised learning) Tập dữ liệu (dataset) bao gồm các ví dụ, mà mỗi ví dụ được gắn li (dataset) bao các ví mà ví đượ kèm với một nhãn lớp/giá trị đầu ra mong muốn Mục đích là học (xấp xỉ) một giả thiết (vd: một phân lớp, một hàm mục tiêu,...) phù hợp với tập dữ liệu hiện có tiêu phù li hi có Giả thiết học được (learned hypothesis) sau đó sẽ được dùng để phân lớp/dự đoán đối với các ví dụ mới Học không có giám sát (Unsupervised learning) Tập dữ liệu (dataset) bao gồm các ví dụ, mà mỗi ví dụ không có thông tin thông tin về nhãn lớp/giá trị đầu ra mong muốn nhãn tr đầ ra mong mu Mục đích là tìm ra (học) các nhóm/các cấu trúc/các quan hệ tồn tại trong tập dữ liệu hiện có Khai Phá Dữ Liệu 3
Phân nhóm Phân nhóm/cụm (Clustering) là phương pháp học không có giám sát đượ có giám sát được sử dụng phổ biến nhất ph bi nh Tồn tại các phương pháp học không có giám sát khác, ví dụ: Lọc cộng tác (Collaborative filtering), Khai phá luật kết hợp (Association rule mining) (Association rule mining), ... Học phân nhóm Đầu vào: một tập dữ liệu không có nhãn (các ví dụ không có nhãn vào: li không có nhãn (các ví không có nhãn lớp/giá trị đầu ra mong muốn) Đầu ra: các nhóm (cụm) của các ví dụ Một nhóm (cluster) là một tập các ví dụ Tương tự với nhau (theo một ý nghĩa, đánh giá nào đó) Khác biệt với các ví dụ thuộc các nhóm khác bi các ví thu các nhóm khác Khai Phá Dữ Liệu 4
Phân nhóm – Ví dụ Một ví dụ về phân nhóm – trong đó, các ví dụ được phân chia thành 3 nhóm [Liu, 2006] Khai Phá Dữ Liệu 5
Phân nhóm – Các thành phần Hàm tính khoảng cách (độ tương tự, độ khác biệt) Giải thuật phân nhóm • Phân nhóm dựa trên chia cắt (Partition-based clustering) • Phân nhóm dựa trên tích tụ phân cấp (Hierarchical clustering) clustering) • Bản đồ tự tổ thức (Self-organizing map – SOM) • Các mô hình hỗn hợp (Mixture models) •… Đánh giá chất lượng phân nhóm (Clustering quality) quality) • Khoảng cách/sự khác biệt giữa các nhóm → Cần được cực đại hóa • Khoảng cách/dự khác biệt bên trong một nhóm → Cần được cực tiểu hóa Khai Phá Dữ Liệu 6
Phân nhóm k-Means Là phương pháp phổ biến nhất trong các phương pháp phân nhóm phân nhóm dựa trên chia cắt (partition-based clustering) trên chia (partition clustering) Tập dữ liệu D={x1,x2,…,xr} •xi là một ví dụ (một vectơ trong một không gian n chiều) ví (m vect trong không gian Giải thuật k-means phân chia (partitions) tập dữ liệu thành thành k nhóm • Mỗi nhóm (cluster) có một điểm trung tâm, được gọi là centroid •k (tổng số các nhóm thu được) là một giá trị được xác định trước các nhóm thu đượ là giá tr đượ xác đị tr (vd: được chỉ định bởi người thiết kế hệ thống phân nhóm) Khai Phá Dữ Liệu 7
k-Means – Các bước chính Với một giá trị k được xác định trước • Bước 1. Chọn ngẫu nhiên k ví dụ (được gọi là các hạt Ch là nhân – seeds) để sử dụng làm các điểm trung tâm ban đầu (initial centroids) của k nhóm • Bước 2. Đối với mỗi ví dụ, gán nó vào nhóm (trong số k nhóm) có điểm trung tâm (centroid) gần ví dụ đó nhất • Bước 3. Đối với mỗi nhóm, tính toán lại điểm trung tâm (centroid) của nó dựa trên tất cả các ví dụ thuộc vào nhóm nhóm đó • Bước 4. Dừng lại nếu điều kiện hội tụ (convergence criterion đượ th mãn; criterion) được thỏa mãn; nếu không, quay lại Bước 2 không, quay Khai Phá Dữ Liệu 8
k-means(D, k) D: The dataset The dataset k: The number of clusters Randomly select k instances in D as the initial centroids select in the initial centroids while not CONVERGENCE for each instance x∈D Compute the distance from x to each centroid Assign x to the cluster whose centroid is closest to x end for for each cluster Re-compute its centroid based on its own instances end while return {The k clusters} Khai Phá Dữ Liệu 9
Điều kiện hội tụ Quá trình phân nhóm kết thúc, nếu: • Không có (hoặc có không đáng kể) việc gán lại các ví dụ vào các có (ho có không vi gán các ví vào các nhóm khác, hoặc • Không có (hoặc có không đáng kể) thay đổi về các điểm trung tâm (centroids) của các nhóm, hoặc • Giảm không đáng kể về tổng lỗi phân nhóm: k Error = ∑ ∑ d (x, m i ) 2 i =1 x∈Ci Ci: Nhóm thứ i mi: Điểm trung tâm (centroid) của nhóm Ci d(x, mi): Khoảng cách (khác biệt) giữa ví dụ x và điểm trung tâm mi Khai Phá Dữ Liệu 10
k-Means – Minh họa (1) [Liu, 2006] Khai Phá Dữ Liệu 11
k-Means – Minh họa (2) [Liu, 2006] Khai Phá Dữ Liệu 12
Điểm trung tâm, Hàm khoảng cách Xác định điểm trung tâm: Điểm trung bình (Mean centroid) 1 ∑x mi = Ci x∈Ci • (vectơ) mi là điểm trung tâm (centroid) của nhóm Ci • |Ci| kích thước của nhóm Ci (tổng số ví dụ trong Ci) Hàm kho Hàm khoảng cách: Euclidean distance cách: Euclidean distance (x1 − mi1 )2 + (x2 − mi 2 )2 + ... + (xn − min )2 d ( x, m i ) = x − m i = • (vectơ) mi là điểm trung tâm (centroid) của nhóm Ci • d(x,mi) là khoảng cách giữa ví dụ x và điểm trung tâm mi Khai Phá Dữ Liệu 13
k-Means – Các ưu điểm Đơn giản • Rất dễ cài đặt đặ • Rất dễ hiểu Hi Hiệu quả • Độ phức tạp về thời gian ~ O(r.k.t) r: Tổng số các ví dụ (kích thước của tập dữ liệu) các ví (kích th li k: Tổng số nhóm thu được t: Tổng số bước lặp (của quá trình phân nhóm) • Nếu cả 2 giá trị k và t đều nhỏ, thì giải thuật k-means được xem như là có độ phức tạp ở mức tuyến tính k-means là giải thuật phân nhóm được dùng phổ biến nhất là gi thu phân nhóm đượ dùng ph bi nh Khai Phá Dữ Liệu 14
k-Means – Các nhược điểm (1) Giá trị k (số nhóm thu được) phải được xác định trước Giải thuật k-means cần xác định cách tính điểm trung bình (centroid) của một nhóm • Đối với các thuộc tính định danh (nominal attributes), giá trị trung ố bình có thể được xác định là giá trị phổ biến nhất Gi thu Giải thuật k-means nhạy cảm (gặp lỗi) với các ví dụ nh (g các ví ngoại lai (outliers) • Các ví dụ ngoại lai là các ví dụ (rất) khác biệt với tất các ví dụ khác • Các ví dụ ngoại lai có thể do lỗi trong quá trình thu thập/lưu dữ liệu • Các ví dụ ngoại lai có các giá trị thuộc tính (rất) khác biệt với các giá trị thuộc tính của các ví dụ khác Khai Phá Dữ Liệu 15
k-Means – Các ví dụ ngoại lai [Liu, 2006] Khai Phá Dữ Liệu 16
Giải quyết vấn đề ngoại lai • Giải pháp 1. Trong quá trình phân nhóm, cần loại bỏ một số các ví dụ quá khác biệt với (cách xa) các điểm trung tâm (centroids) so với các ví dụ khác Để chắc chắn (không loại nhầm), theo dõi các ví dụ ngoại lai ─ (outliers) qua (outliers) qua một vài (thay vì chỉ 1) bước lặp phân nhóm, trước vài (thay vì ch 1) phân nhóm tr khi quyết định loại bỏ • Giải pháp 2. Thực hiện việc lấy mẫu ngẫu nhiên (a random sampling) Do quá trình lấy mẫu chỉ lựa chọn một tập con nhỏ của tập dữ ─ li ban đầ nên kh liệu ban đầu, nên khả năng một ngoại lai (outlier) được chọn là ngo lai (outlier) đượ ch là rất nhỏ Gán các ví dụ còn lại của tập dữ liệu vào các nhóm tùy theo đánh ─ giá giá về khoảng cách (hoặc độ tương tự) kho cách (ho độ Khai Phá Dữ Liệu 17
k-Means – Các nhược điểm (2) Giải thuật k-means phụ thuộc vào việc chọn các điểm trung tâm ban đầu (initial centroids) 1st centroid 2nd centroid [Liu, 2006] Khai Phá Dữ Liệu 18
k-Means – Các hạt nhân ban đầu (1) Sử dụng các hạt nhân (seeds) khác nhau → Kết quả tốt hơn! • Thực hiện giải thuật k-means nhiều lần, mỗi lần bắt đầu với một tập (khác hi gi thu nhi đầ (khác lần trước) các hạt nhân được chọn ngẫu nhiên [Liu, 2006] Khai Phá Dữ Liệu 19
k-Means – Các hạt nhân ban đầu (2) Lựa chọn ngẫu nhiên hạt nhân thứ 1 (m1) Lựa chọn hạt nhân thứ 2 (m2) càng xa càng tốt so với hạt nhân thứ 1 … Lựa chọn hạt nhân thứ i (mi) càng xa càng tốt so với hạt nhân nhân gần nhất trong số {m1, m2, … , mi-1} nh trong ... Khai Phá Dữ Liệu 20

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.