Nhập môn Học máy Khai phá liệu (IT3190) Nguyễn Nhật Quang quang.nguyennhat@hust.edu.vn Trường Đại học Bách Khoa Hà Nội Viện Công nghệ thông tin truyền thông Năm học 2020-2021 Nội dung môn học: ◼ Giới thiệu Học máy Khai phá liệu ◼ Tiền xử lý liệu ◼ Đánh giá hiệu hệ thống ◼ Hồi quy ◼ Phân cụm ◼ Phân lớp ◼ Phát luật kết hợp Nhập môn Học máy Khai phá liệu – Introduction to Machine learning and Data mining Tập liệu ◼ ◼ Một tập liệu (dataset) tập hợp đối tượng (objects) thuộc tính chúng Mỗi thuộc tính (attribute) mơ tả đặc điểm đối tượng ❑ ◼ Các thuộc tính Vd: Các thuộc tính Refund, Marital Status, Taxable Income, Cheat Một tập giá trị thuộc tính mơ tả đối tượng ❑ Khái niệm “đối tượng” tham chiếu đến với tên gọi khác: ghi (record), điểm liệu (data point), trường hợp (case), mẫu (sample), thực thể (entity), ví dụ (instance) Các đối tượng Nhập mơn Học máy Khai phá liệu – Introduction to Machine learning and Data mining Tid Refund Marital Status Taxable Income Cheat Yes Single 125K No No Married 100K No No Single 70K No Yes Married 120K No No Divorced 95K Yes No Married No Yes Divorced 220K No No Single 85K Yes No Married 75K No 10 No Single 90K Yes 60K 10 (Tan, Steinbach, Kumar Introduction to Data Mining) Các kiểu tập liệu ◼ Bản ghi (Record) Có trật tự (Ordered) ❑ ❑ ❑ ❑ Dữ liệu không gian (vd: đồ) Dữ liệu thời gian (vd: time-series data) Dữ liệu chuỗi (vd: chuỗi giao dịch) Dữ liệu chuỗi di truyền (genetic sequence data) season ◼ timeout ❑ lost ❑ World Wide Web Mạng thông tin, mạng xã hội Các cấu trúc phân tử (Molecular structures) wi n ❑ game Đồ thị (Graph) score ◼ ball ❑ play ❑ coach ❑ Các ghi csdl quan hệ Ma trận liệu Biểu diễn văn (document) Dữ liệu giao dịch team ❑ Document 2 Document 0 0 Document 0 2 TID Items Bread, Coke, Milk Beer, Bread Beer, Coke, Diaper, Milk Beer, Bread, Diaper, Milk Coke, Diaper, Milk Nhập môn Học máy Khai phá liệu – Introduction to Machine learning and Data mining (Han, Kamber - Data Mining: Concepts and Techniques) Các kiểu giá trị thuộc tính ◼ Kiểu định danh/chuỗi (norminal): khơng có thứ tự ❑ ❑ ◼ Kiểu nhị phân (binary): trường hợp đặc biệt kiểu định danh ❑ ◼ Lấy giá trị từ tập khơng có thứ tự giá trị (định danh) Vd: Các thuộc tính như: Name, Profession, … Tập giá trị gồm có giá trị (Y/N, 0/1, T/F) Kiểu có thứ tự (ordinal): ❑ ❑ ❑ Lấy giá trị từ tập có thứ tự giá trị Vd1: Các thuộc tính lấy giá trị số như: Age, Height,… Vd2: Thuộc tính Income lấy giá trị từ tập {low, medium, high} Nhập môn Học máy Khai phá liệu – Introduction to Machine learning and Data mining Kiểu thuộc tính rời rạc vs liên tục ◼ Kiểu thuộc tính rời rạc (Discrete-valued attributes) ❑ ❑ ❑ ◼ Tập giá trị tập hữu hạn Bao gồm thuộc tính có kiểu giá trị số nguyên Bao gồm thuộc tính nhị phân (binary attributes) Kiểu thuộc tính liên tục (Continuous-valued attributes) ❑ Các giá trị số thực (real numbers) Nhập môn Học máy Khai phá liệu – Introduction to Machine learning and Data mining Các đặc tính mơ tả liệu ◼ Mục đích: Để hiểu rõ liệu có (chiều hướng chính/trung tâm, biến thiên, phân bố) ◼ Sự phân bố liệu (Data dispersion) ❑ Giá trị cực tiểu/cực đại (min/max) ❑ Giá trị xuất nhiều (mode) ❑ Giá trị trung bình (mean) ❑ Giá trị trung vị (median) ❑ Sự biến thiên (variance) độ lệch chuẩn (standard deviation) ❑ Các ngoại lai (outliers) Nhập môn Học máy Khai phá liệu – Introduction to Machine learning and Data mining Hiển thị hóa liệu (Data visualization) ◼ Biểu diễn liệu phương pháp hiển thị đồ họa, giúp hiểu rõ đặc điểm liệu ◼ Cung cấp nhìn định tính tập liệu lớn ◼ Có thể mẫu, xu hướng, cấu trúc, bất thường, quan hệ liệu ◼ Hỗ trợ xác định vùng liệu quan trọng tham số phù hợp cho phân tích định lượng ◼ Trong số trường hợp, cung cấp chứng minh trực quan biểu diễn (tri thức) thu Nhập môn Học máy Khai phá liệu – Introduction to Machine learning and Data mining Dữ liệu cân đối vs lệch ◼ Giá trị trung bình, giá trị trung vị, giá trị xuất nhiều ❑ ❑ Dữ liệu cân đối Dữ liệu lệch Nhập môn Học máy Khai phá liệu – (Han, Kamber - Data Mining: Introduction to Machine learning and Data miningConcepts and Techniques) Biểu đồ histogram ◼ Biểu đồ histogram cách biểu diễn dựa đồ thị ◼ Được sử dụng phổ biến ◼ Hiển thị mô tả thống kê xuất (counts/frequencies) theo thuộc tính Nhập môn Học máy Khai phá liệu – Introduction to Machine learning and Data mining (Han, Kamber - Data Mining: Concepts and Techniques) 10 Thuộc tính thiếu giá trị: Các giải pháp ◼ Bỏ qua ghi có thuộc tính thiếu giá trị ❑ ❑ ◼ ◼ Thường áp dụng toán phân lớp (classification) Không hiệu quả, tỷ lệ % giá trị thiếu thuộc tính (rất) khác Một số người đảm nhiệm việc kiểm tra gán giá trị thuộc tính cịn thiếu (manually filling): cơng việc tẻ nhạt + chi phí cao Gán giá trị tự động máy tính ❑ ❑ ❑ ❑ Một giá trị (hằng) mặc định Giá trị trung bình thuộc tính Giá trị trung bình thuộc tính đó, xét tất ví dụ (các ghi) thuộc lớp (class) với ghi Giá trị xảy – dựa phương pháp xác suất (vd: công thức Bayes) Nhập môn Học máy Khai phá liệu – Introduction to Machine learning and Data mining 17 Dữ liệu chứa nhiễu ◼ Nhiễu: Lỗi ngẫu nhiên giá trị thuộc tính ◼ Các giá trị thuộc tính bị lỗi (nhiễu) vì: ❑ Lỗi thiết bị thu thập liệu ❑ Các lỗi nhập liệu ❑ Lỗi trình truyền liệu ❑ Sự mâu thuẫn (không quán) quy ước tên (thuộc tính/biến) Nhập mơn Học máy Khai phá liệu – Introduction to Machine learning and Data mining 18 Dữ liệu chứa nhiễu: Các giải pháp ◼ Phân khoảng (Binning) ❑ ❑ ◼ Hồi quy (Regression) ❑ ◼ Gắn liệu với hàm hồi quy (regression function) Phân cụm (Clustering) ❑ ◼ Sắp xếp liệu, phân chia thành khoảng (bins) có tần số xuất giá trị (frequency) Sau đó, khoảng liệu biểu diễn trung bình(mean), trung vị (median), giới hạn…của giá trị khoảng Phát loại bỏ ngoại lai (sau xác định cụm) Kết hợp máy tính kiểm tra người ❑ ❑ Máy tính tự động phát giá trị nghi ngờ (là nhiễu/lỗi) Các giá trị nghi ngờ người kiểm tra lại Nhập môn Học máy Khai phá liệu – Introduction to Machine learning and Data mining 19 Phân khoảng (Binning) ◼ Phân chia với độ rộng (khoảng cách) ❑ ❑ ❑ ◼ Chia khoảng giá trị thành N khoảng với kích thước (độ rộng) Nếu mini maxi giá trị lớn nhỏ thuộc tính, kích thước (độ rộng) khoảng = (maxi - mini)/N Không phù hợp tập liệu lệch (skewed data), có chứa ngoại lai (outliers) – khoảng chứa (hoặc số) ngoại lai Phân chia với độ sâu (tần suất xuất hiện) ❑ ❑ Chia khoảng giá trị thành N khoảng (không thiết nhau), cho khoảng chứa xấp xỉ số lượng (tần xuất xuất hiện) ví dụ Hiệu cách phân chia với độ rộng (khoảng cách) Nhập môn Học máy Khai phá liệu – Introduction to Machine learning and Data mining 20 Phân khoảng (Binning) – Ví dụ ◼ Sắp xếp giá trị thuộc tính Price: 4, 8, 9, 15, 21, 21, 24, 25, 26, 28, 29, 34 ◼ Phân chia thành khoảng với độ sâu (tần xuất xuất hiện) ❑ ❑ ❑ ◼ Bin 1: 4, 8, 9, 15 Bin 2: 21, 21, 24, 25 Bin 3: 26, 28, 29, 34 Biểu diễn khoảng liệu giá trị trung bình ❑ ❑ ❑ Bin 1: 9, 9, 9, Bin 2: 23, 23, 23, 23 Bin 3: 29, 29, 29, 29 Nhập môn Học máy Khai phá liệu – Introduction to Machine learning and Data mining 21 Hồi quy (Regression) y Y1 y=x+1 Y1’ X1 x (Han, Kamber - Data Mining: Concepts and Techniques) Nhập môn Học máy Khai phá liệu – Introduction to Machine learning and Data mining 22 Phân tích cụm (Cluster analysis) (Han, Kamber - Data Mining: Concepts and Techniques) Nhập môn Học máy Khai phá liệu – Introduction to Machine learning and Data mining 23 Tích hợp liệu ◼ Tích hợp liệu (Data integration) ❑ ◼ Tích hợp mức mơ hình (Schema integration) ❑ ❑ ◼ Tích hợp metadata từ nguồn khác Vd: A.cust-id  B.customID Vấn đề xác định thực thể (để tránh dư thừa liệu) ❑ ❑ ◼ Kết hợp liệu từ nhiều nguồn vào kho liệu thống Cần xác định thực thể (identities) thực tế từ nhiều nguồn liệu Vd: Bill Clinton  B Clinton Phát xử lý mâu thuẫn giá trị liệu ❑ Đối với thực thể thực tế, giá trị thuộc tính từ nhiều nguồn khác lại khác Các lý có thể: ◼ Các cách biểu diễn khác ◼ Mức đánh giá, độ đo (scales) khác – Vd: hệ đo lường mét vs hệ đo lường Anh Nhập môn Học máy Khai phá liệu – Introduction to Machine learning and Data mining 24 Tích hợp liệu: Xử lý dư thừa liệu ◼ Dư thừa liệu (redundant data) thường xuyên xảy ra, tích hợp liệu từ nhiều nguồn (vd: từ nhiều csdl) ❑ ❑ Định danh đối tượng: Cùng thuộc tính (hay đối tượng) mang tên (định danh) khác csdl khác Dữ liệu suy được: Một thuộc tính bảng thuộc tính suy (derived attribute) bảng khác – Vd: “Annual Revenue” “Monthly Revenue” ◼ Các thuộc tính dư thừa phát phân tích tương quan (Correlation analysis): Pearson, Cosine, chi-square ◼ Yêu cầu chung q trình tích hợp liệu: Giảm thiểu (tránh tốt nhất) dư thừa mâu thuẫn ❑ Giúp cải thiện tốc độ trình khai phá liệu, nâng cao chất lượng kết (tri thức) thu Nhập môn Học máy Khai phá liệu – Introduction to Machine learning and Data mining 25 Biến đổi liệu (1) ◼ Biến đổi liệu (Data transformation) ❑ ◼ Việc chuyển (ánh xạ) toàn tập giá trị thuộc tính sang tập giá trị thay thế, cho giá trị cũ tương ứng với giá trị Các phương pháp biến đổi liệu ❑ ❑ ❑ ❑ ❑ Làm trơn (Smoothing): Loại bỏ nhiễu/lỗi khỏi liệu Kết hợp (Aggregation): Sự tóm tắt liệu, xây dựng khối liệu (data cubes) Khái quát hóa (Generalization): Xây dựng phân cấp khái niệm (concept hierarchies) Chuẩn hóa (Normalization): Đưa giá trị khoảng định ◼ Chuẩn hóa min-max ◼ Chuẩn hóa z-score ◼ Chuẩn hóa thang chia 10 Xây dựng (tạo nên) thuộc tính dựa thuộc tính ban đầu Nhập môn Học máy Khai phá liệu – Introduction to Machine learning and Data mining 26 Biến đổi liệu (2) ◼ Chuẩn hóa min-max: thành khoảng [new_mini, new_maxi] v ◼ new v old − mini = (new _ maxi − new _ mini ) + new _ mini maxi − mini Chuẩn hóa z-score ❑ μi, σi: giá trị trung bình độ lệch chuẩn thuộc tính i v new = ◼ v old −  i i Chuẩn hóa thang chia 10 v ❑ new v old = j 10 j giá trị số nguyên nhỏ cho: max({vnew}) < Nhập môn Học máy Khai phá liệu – Introduction to Machine learning and Data mining 27 Giảm bớt liệu ◼ Tại cần phải giảm bớt liệu? ❑ ❑ ◼ Giảm bớt liệu (Data reduction) ❑ ◼ Một kho (tập) liệu lớn chứa lượng liệu lên đến terabytes Do đó, q trình khai phá liệu chạy lâu (rất thời gian) toàn tập liệu Để thu biểu diễn thu gọn (giảm bớt); sinh (hoặc xấp xỉ) kết phân tích (khai phá) với tập liệu ban đầu Các chiến lược giảm bớt liệu ❑ ❑ Giảm số chiều (Dimensionality reduction): Loại bỏ bớt thuộc tính khơng (ít) quan trọng Giảm lượng liệu (Data/Numerosity reduction) ◼ Kết hợp khối liệu (Data cube aggregation) ◼ Nén liệu (Data compression) ◼ Hồi quy (Regression) ◼ Rời rạc hóa (Discretization) Nhập môn Học máy Khai phá liệu – Introduction to Machine learning and Data mining 28 Giảm số chiều ◼ Ảnh hưởng tiêu cực số chiều (số thuộc tính) lớn ❑ ❑ ◼ Giảm số chiều (Dimensionality reduction) giúp: ❑ ❑ ❑ ❑ ◼ Khi số chiều tăng, liệu trở nên thưa thớt (more sparse) Mật độ khoảng cách điểm (quan trọng việc phân cụm, phát ngoại lai) trở nên có ý nghĩa Tránh (giảm bớt) ảnh hưởng tiêu cực số chiều lớn Loại bỏ thuộc tính khơng liên quan, giảm nhiễu/lỗi Giảm chi phí thời gian nhớ cần cho trình khai phá liệu Cho phép hiển thị hóa (visualize) liệu cách dễ dàng hiệu Một số ví dụ điển hình kỹ thuật giảm số chiều: ❑ ❑ Phân tích thành phần (Principal component analysis) Lựa chọn tập thuộc tính (Feature subset selection) Nhập môn Học máy Khai phá liệu – Introduction to Machine learning and Data mining 29 Lấy mẫu liệu ◼ Lấy mẫu liệu (Data sampling) phương pháp quan trọng việc lựa chọn liệu ◼ Việc lấy mẫu liệu cần thiết u cầu thu thập xử lý tồn tập liệu lớn đòi hỏi chi phí cao tốn thời gian ◼ Các nguyên tắc quan trọng việc lấy mẫu liệu ❑ ❑ Sử dụng mẫu (sample) có tác dụng gần sử dụng toàn tập liệu, mẫu đại diện cho tập liệu Một mẫu gọi đại diện cho tập liệu, mẫu có (xấp xỉ) đặc tính tập liệu Nhập môn Học máy Khai phá liệu – Introduction to Machine learning and Data mining 30 Các phương pháp lấy mẫu liệu ◼ Lấy mẫu ngẫu nhiên (Simple random sampling) ❑ ◼ Lấy mẫu không thay (Sampling without replacement) ❑ ◼ Khi ví dụ (bản ghi) lấy mẫu, loại khỏi tập liệu ban đầu (sẽ chọn thêm lần nữa) Lấy mẫu có thay (Samping with replacement) ❑ ◼ Mỗi ví dụ (bản ghi) lựa chọn với giá trị xác suất Khi ví dụ (bản ghi) lấy mẫu, khơng bị loại khỏi tập liệu ban đầu (có thể chọn nhiều lần) Lấy mẫu phân tầng (Stratified sampling) ❑ ❑ Phân chia tập liệu thành phần (partitions) Lấy ngẫu nhiên ví dụ từ phần Nhập mơn Học máy Khai phá liệu – Introduction to Machine learning and Data mining 31