Bài giảng Nhập môn khai phá dữ liệu - Chương 3: Hiểu bài toán, hiểu dữ liệu và tiền xử lý dữ liệu - Hà Quang Thụy

ọi điện 
 thoại.
 ◼ Các mức phức hợp của tích hợp thành khối dữ liệu
 ◼ Giảm thêm kích thước dữ liệu
 ◼ Tham khảo mức thích hợp
 ◼ Sử dụng trình diễn nhỏ nhất đủ để giải bài toán
 ◼ Nên sử dụng dữ liệu khối lập phương khi trả lời câu hỏi 
 tổng hợp thông tin
July 12, 2021 64
 Lựa chọn đặc trưng
 ◼ Khái niệm
 ◼ Lựa chọn tập nhỏ nhất đặc trưng mà phân bố xác suất các 
 lớp khác nhau cho giá trị gần như phân bổ vốn có các giá trị 
 các đặc trưng
 ◼ Kỳ vọng
 ➢ Tăng tốc độ thực thi
 ➢ Tăng chất lượng mẫu? các đặc trưng “nhiễu”
 ➢ Hoặc cả hai mục tiêu trên
 ◼ Phương pháp
 ◼ Heuristic (# mũ phép chọn) :Chọn tiến/lùi
 ◼ Kết hợp chon tiến/lùi lên trước và loại bỏ lạc hậu.
 ◼ Rút gọn bằng cây quyết định
 ◼ Hai tiếp cận điển hình 
 ➢ Tiếp cận lọc
 ➢ Tiếp cận bao gói
July 12, 2021 65
 Ví dụ đặc trưng: Bài toán rời bỏ dịch vụ
Công ty điện thoại di động: các thuộc tính như liệt kê
“Lớp” liên quan tới leave (rời bỏ) 66
 Rời bỏ dịch vụ
Độ quan trọng các thuộc tính: Tiến hành lại sau mỗi bước
 67
 Tiếp cận tổng quát: lọc
◼ Tiếp cận lọc
 ➢ Đầu vào: Không gian tập các tập đặc trưng
 ➢ Đầu ra: Tập con đặc trưng tốt nhất
 ➢ Phương pháp
 ➢ Dò tìm “cải tiến” bộ đặc trưng: Thuật toán tối ưu hóa
 ➢ Đánh giá chất lượng mô hình: độc lập với thuật toán học máy
 68
 Tiếp cận bao gói tổng quát
◼ Tiếp cận bao gói
 ➢ Đầu vào: Không gian tập các tập đặc trưng
 ➢ Đầu ra: Tập con đặc trưng tốt nhất
 ➢ Phương pháp
 ➢ Dò tìm “cải tiến” bộ đặc trưng: Thuật toán tối ưu hóa
 ➢ Đánh giá chất lượng mô hình: Dùng chính thuật toán học để
 đánh giá
 69
 Tiếp cận bao gói tổng quát
Ngoc-Anh Thi Le, Thi-Oanh Ngo, Huyen-Trang Thi Lai, Hoang-Quynh Le, Hai-Chau
 Nguyen, Quang-Thuy Ha. An Experimental Study on Cholera Modeling in
 Hanoi. ACIIDS (2) 2016: 230-240
 70
Rút gọn đặc trưng theo cây quyết định
 Tập thuộc tính khởi tạo:
 {A1, A2, A3, A4, A5, A6}
 A4 ?
 A1? A6?
 Class 1 Class 2 Class 1 Class 2
 > Tập thuộc tinh rút gọn: {A1, A4, A6}
July 12, 2021 71
 Phân lớp cây quyết định
◼ Đồ thị dạng cây
◼ Đỉnh trong là một hàm test
◼ Các nhánh tương ứng với kết quả kiểm tra tại 
 đỉnh trong
◼ Các lá là các nhãn, hoặc các lớp.
◼ Xem Chương 5
Phân lớp cây quyết định
 Phân lớp cây quyết định
◼ Xây dựng cây quyết định: 
 ◼ Xây dựng cây quyết định
 ◼ Phương pháp top-down
 ◼ Cắt tỉa cây (pruning)
 ◼ Phương pháp bottom-up: xác định và loại bỏ những 
 nhánh rườm rà tăng độ chính xác khi phân lớp 
 những đối tượng mới
◼ Sử dụng cây quyết định: phân lớp các đối tượng 
 chưa được gán nhãn
 Nén dữ liệu (Data Compression)
 ◼ Nén xâu văn bản
 ◼ Tồn tại lý thuyết phong phú và thuật toán điển hình
 ◼ Mạnh: Không tốn thất điển hình
 ◼ Yếu: chỉ các thao tác hạn hẹp mà không mở rộng
 ◼ Nén Audio/video
 ◼ Nén tổn thất điển hình, với tinh lọc cải tiến
 ◼ Vài trường hợp mảnh tín hiệu nhỏ được tái hợp không 
 cần dựng toàn bộ
 ◼ Chuỗi thời gian mà không là audio
 ◼ Ngắn điển hình và thay đổi chậm theo thời gian
July 12, 2021 76
Nén dữ liệu (Data Compression)
 Original Data Compressed 
 Data
 lossless
 Original Data
 Approximated 
July 12, 2021 77
 Chuyển dạng sóng
 ◼ Wavelet Transformation
 ◼ Biến dạng sóng rời rạc (Discrete wavelet transform:DWT): 
 XL tín hiệu tuyến tính, phân tích đa giải pháp
 ◼ Xấp xỉ nén: chỉ lưu một mảnh nhỏ các hệ số sóng lớn nhất
 ◼ Tương tự như biến đổi rời rạc Fourier (DFT), nhưng nén 
 tổn thất tốt hơn, bản địa hóa trong không gian
 ◼ Phương pháp:
 ◼ Độ dài, L, buộc là số nguyên lũy thừa 2 (đệm thêm các chữ số 0, 
 khi cần)
 ◼ Mỗi phép biến đổi có 2 chức năng: làm mịn, phân tách
 ◼ Áp dụng cho các cặp DL, kết quả theo 2 tập DL độ dài L/2
 ◼ Áp dụng đệ quy hai chức năng đến độ dài mong muốn
 Haar2 Daubechie4
July 12, 2021 78
 DWT cho nén ảnh
 ◼ Image
 Low Pass High Pass
 Low Pass High Pass
 Low Pass High Pass
July 12, 2021 79
 Trích xuất đặc trưng PCA
 ◼ Phân tích thành phần chính (Principal Component 
 Analysis)
 ◼ Cho N vector dữ liệu k-chiều, tìm c (<= k) vector trực 
 giao tốt nhất để trình diễn dữ liệu.
 ◼ Tập dữ liệu gốc được rút gọn thành N vector dữ liệu c 
 chiều: c thành phần chính (chiều được rút gọn). 
 ◼ Mỗi vector dữ liệu là tổ hợp tuyến tính của các vector 
 thành phần chính.
 ◼ Chỉ áp dụng cho dữ liệu số.
 ◼ Dùng khi số chiều vector lớn.
July 12, 2021 80
 Phân tích thành phần chính
 X2
 Y1
 Y2
 X1
July 12, 2021 81
 Rút gọn kích thước số
 ◼ Phương pháp tham số
 ◼ Giả sử dữ liệu phù hợp với mô hình nào đó, ước lượng 
 tham số mô hình, lưu chỉ các tham số, và không lưu dữ 
 liệu (ngoại trừ các ngoại lai có thể có)
 ◼ Mô hình tuyến tính loga (Log-linear models): lấy giá trị 
 tại một điểm trong không gian M-chiều như là tích của 
 các không gian con thích hợp
 ◼ Phương pháp không tham số
 ◼ Không giả thiết mô hình
 ◼ Tập hợp chính: biểu đồ (histograms), phân cụm 
 (clustering), lấy mẫu (sampling)
July 12, 2021 82
 Mô hình hồi quy tuyến tính và logarit
 ◼ Hồ quy tuyến tính: DL được mô hình hóa phù hợp với 1 
 đường thẳng
 ◼ Thường dùng phương pháp bình phương tối thiểu để 
 khớp với đường
 ◼ Hồ quy đa chiều: Cho một biến đích Y được mô hình hóa 
 như ột hàm tuyến tính của vector đặc trưng đa chiều
 ◼ Mô hình tuyến tính loga: rời rạc hóa xấp xỉ các phân bố 
 xác suất đa chiều
July 12, 2021 83
 Phân tích MH hồi quy tuyến tính và logarit 
◼ Hồi quy tuyến tính: Y = +  X
 ◼ Hai tham số, và  đặc trưng cho đường và được xấp 
 xỉ qua dữ liệu đã nắm bắt được.
 ◼ Sử dụng chiến lược BP tối thiếu tới các giá trị đã biết 
 Y1, Y2, , X1, X2, .
◼ Hồi quy đa chiều: Y = b0 + b1 X1 + b2 X2.
 ◼ Nhiều hàm không tuyến tính được chuyển dạng như 
 trên.
◼ Mô hình tuyến tính loga:
 ◼ Bảng đa chiều của xác suất tích nối được xấp xỉ bởi 
 tích của các bảng bậc thấp hơn
 ◼ Xác suất: p(a, b, c, d) = ab acad bcd
 Lược đồ
 ◼ Histograms 40
 ◼ Kỹ thuật rút gọn dữ liệu 35
 phổ biến
 30
 ◼ Phân dữ liệu vào các 
 thùng và giữ trunh bình 25
 (tổng) của mỗi thùng
 20
 ◼ Có thể được dựng tối 
 ưu hóa theo 1 chiều khi 15
 dùng quy hoạch động 10
 ◼ Có quan hệ tới bài toán 
 lượng tử hóa. 5
 0
 10000 30000 50000 70000 90000
July 12, 2021 85
 Phân cụm
 ◼ Phân tập DL thành các cụm, và chỉ cần lưu trữ đại diện 
 của cụm
 ◼ Có thể rất hiệu quả nếu DL là được phân cụm mà 
 không chứa dữ liệu “bẩn”
 ◼ Có thể phân cụm phân cấp và được lưu trữ trong cấu 
 trúc cây chỉ số đa chiều
 ◼ Tồn tài nhiều lựa chọn cho xác định phân cụm và thuật 
 toán phân cụm
July 12, 2021 86
 Lấy mẫu dữ liệu
 ◼ Sampling
 ◼ Cho phép một thuật toán khai phá chạy theo độ phức tạp 
 tựa tuyến tính theo cỡ của DL
 ◼ Lựa chọn một tập con trình diễn dữ liệu
 ◼ Lấy mẫu ngẫu nhiên đơn giản có hiệu quả rất tồi nếu có 
 DL lệch
 ◼ Phát triển các phương pháp lấy mẫu thích nghi
 ◼ Lấy mẫu phân tầng: 
 ◼ Xấp xỉ theo phần trăm của mỗi lớp (hoặc bộ phận 
 nhận diện được theo quan tâm) trong CSDL tổng thể
 ◼ Sử dụng kết hợp với dữ liệu lệch
 ◼ Lẫy mẫu có thể không rút gọn được CSDL.
July 12, 2021 87
 Lấy mẫu ngẫu nhiên độc lập
 Luca Martino, David Luengo, Joaquín Míguez. Independent Random 
 Sampling Methods. Springer International, 2018
July 12, 2021 88
 Rút gọn mẫu
 ◼ Simple Random Sampling (SRS)
 ◼ SRS with replacement (SRSWR)
 ➢ Chọn một phần tử dữ liệu đưa vào mẫu
 ➢ Loại bỏ phần tử dữ liệu đó ra khỏi tập dữ liệu
 ➢ Lặp tiếp cho đến khi có n phần tử dữ liệu
 ➢ Các phần tử dữ liệu giống nhau có thể được chọn nhiều lần
 ◼ SRS without replacement (SRSWOR)
 ➢ Chọn một phần tử và không bị loại bỏ. Các mẫu DL phân biệt
 ◼ Ví dụ: Chọn mẫu 2 (n) phần tử từ tập 4 dữ liệu
July 12, 2021 89
 Rút gọn mẫu
 Raw Data Mẫu cụm/phân tầng
July 12, 2021 90
 Rút gọn phân cấp
 ◼ Dùng cấu trúc đa phân giải với các mức độ khác nhau của 
 rút gọn
 ◼ Phân cụm phân cấp thường được thi hành song có khuynh 
 hướng xác định phân vùng DL hớn là “phân cụm”
 ◼ Phương pháp tham số thường không tuân theo trình bày 
 phân cấp
 ◼ Tích hợp phân cấp
 ◼ Một cây chỉ số được chia phân cấp một tập DL thành các 
 vùng bởi miền giá trị của một vài thuộc tính
 ◼ Mỗi vùng được coi như một thùng
 ◼ Như vậy, cây chỉ số với tích hợp lưu trữ mỗi nút là một sơ 
 đồ phân cấp
July 12, 2021 91
 Rời rạc hóa
 ◼ Ba kiểu thuộc tính:
 ◼ Định danh — giá trị từ một tập không có thứ tự
 ◼ Thứ tự — giá trị từ một tập được sắp
 ◼ Liên tục — số thực
 ◼ Rời rạc hóa: 
 ◼ Chia miền thuộc tính liên tục thành các đoạn
 ◼ Một vài thuật toán phân lớp chỉ chấp nhận thuộc tính 
 phân loại.
 ◼ Rút gọn cỡ DL bằng rời rạc hóa
 ◼ Chuẩn bị cho phân tích tiếp theo
July 12, 2021 92
 Rời rạc hóa và kiến trúc khái niệm
 ◼ Rời rạc hóa
 ◼ Rút gọn số lượng giá trị của thuộc tính liên tục bằng 
 cách chia miền giá trị của thuộc tính thành các đoạn. 
 Nhãn đoạn sau đó được dùng để thay thế giá trị thực.
 ◼ Phân cấp khái niệm
 ◼ Rút gọn DL bằng tập hợp và thay thế các khái niệm 
 mức thấp (như giá trị số của thuộc tính tuổi) bằng 
 khái niệm ở mức cao hơn (như trẻ, trung niên, hoặc 
 già)
July 12, 2021 93
 Rời rạc hóa & kiến trúc khái niệm DL số
 ◼ Phân thùng (xem làm trơn khử nhiễu)
 ◼ Phân tích sơ đồ (đã giới thiệu)
 ◼ Phân tích cụm (đã giới thiệu)
 ◼ Rời rạc hóa dựa theo Entropy
 ◼ Phân đoạn bằng phân chia tự nhiên
July 12, 2021 94
 Rời rạc hóa dựa trên Entropy
 ◼ Cho tập ví dụ S, nếu S được chia thành 2 đoạn S1 và S2 
 dùng biên T, thì entropy sau khi phân đoạn là
 | | | |
 E(S,T) = S1 Ent( ) + S2 Ent( )
 |S| S1 |S| S2
 ◼ Biên làm cực tiểu hàm entropy trên tất cả các biên được 
 chọn như một rời rạc hóa nhị phân.
 ◼ Quá trình đệ quy tới các vùng cho tới khi đạt điều kiện 
 dừng nào đó, như
 Ent(S) − E(T,S) 
 ◼ Thực nghiệm chỉ ra rằng cho phép rút gọn cỡ DL và tăng 
 độ chính xác phân lớp
July 12, 2021 95
 Phân đoạn bằng phân hoạch tự nhiên
 ◼ Quy tắc đơn giản 3-4-5 được dùng để phân đoạn dữ liệu số 
 thành các đoạn tương đối thống nhất, “tự nhiên”.
 ◼ Hướng tới số giá trị khác biệt ở vùng quan trọng nhất
 ◼ Nếu 3, 6, 7 hoặc 9 giá trị khác biệt thì chia miền thành 
 3 đoạn tương đương.
 ◼ Nếu phủ 2, 4, hoặc 8 giá trị phân biệt thì chia thành 4.
 ◼ Nếu phủ 1, 5, hoặc 10 giá trị phân biệt thì chia thành 5.
July 12, 2021 96
 Ví dụ luật 3-4-5
 count
 Step 1: -$351 -$159 profit $1,838 $4,700
 Min Low (i.e, 5%-tile) High(i.e, 95%-0 tile) Max
 Step 2: msd=1,000 Low=-$1,000 High=$2,000
 (-$1,000 - $2,000)
 Step 3:
 (-$1,000 - 0) (0 -$ 1,000) ($1,000 - $2,000)
 (-$4000 -$5,000)
 Step 4:
 ($2,000 - $5, 000)
 (-$400 - 0) (0 - $1,000) ($1,000 - $2, 000)
 (0 -
 ($1,000 -
 $200)
 (-$400 - $1,200) ($2,000 -
 -$300)
 ($200 - $3,000)
 ($1,200 -
 $400)
 (-$300 - $1,400)
 ($3,000 -
 -$200)
 ($400 - ($1,400 - $4,000)
 (-$200 - $600) $1,600) ($4,000 -
 -$100) ($600 - ($1,600 - $5,000)
 ($1,800 -
 $800) ($800 - $1,800)
 (-$100 - $1,000) $2,000)
 0)
July 12, 2021 97
 Sinh kiến trúc khái niệm dữ liệu phân loại
 ◼ Đặc tả một thứ tự bộ phận giá trị thuộc tính theo mức 
 sơ đồ do người dùng hoặc chuyên gias
 ◼ street<city<state<country
 ◼ Đặc tả thành cấu trúc phân cấp nhờ nhóm dữ liệu
 ◼ {Urbana, Champaign, Chicago}<Illinois
 ◼ Đặc tả theo tập các thuộc tính. 
 ◼ Tự động sắp xếp một phần bằng cách phân tích số 
 lượng các giá trị khác biệt
 ◼ Như, street < city <state < country
 ◼ Đặc tả một phần thứ tự bộ phận
 ◼ Như, chỉ street < city mà không có cái khác
July 12, 2021 98
 Sinh kiến trúc khái niệm tự động
 ◼ Một vài kiến trúc khái niệm có thể được sinh tự động dựa 
 trên phân tích số lượng các giá trị phân biệt theo thuộc 
 tính của tập DL đã cho
 ◼ Thuộc tính có giá trị phân biệt nhất được đặt ở cấp độ 
 phân cấp thấp nhất
 ◼ Lưu ý: Ngoài trừ, các ngày trong tuần, tháng, quý, năm
 country 15 giá trị phân biệt
 province_or_ state 65 giá trị phân biệt
 city 3567 giá trị phân biệt
 street 674,339 giá trị phân biệt
July 12, 2021 99
 Thách thức dữ liệu: thiếu dữ liệu
 ◼ Thiếu dữ liệu học
 ◼ Con người học: cần ít dữ 
 liệu mẫu, có thể một ví dụ 
 nhiều lần
 ◼ Học máy cho khai phá dữ 
 liệu cần đủ lượng dữ liệu
 ◼ Ví dụ: xử lý ngôn 
 Memory-based
 ngữ tự nhiên phức chính Độ xác kiểmthử 
 Winnow
 tạp (kiểm tra cú Perceptron
 pháp) Naïve Bayes
 ◼ Với lượng đủ dữ liệu liên 
 Đơn vị: triệu từ
 quan (1 tỷ từ), các thuật 
 toán có hiệu năng gần như 
 nhau
July 12, 2021 100
 Thách thức: dữ liệu không đại diện
 ◼ Đặt vấn đề
 ◼ Dữ liệu mẫu đại diện miền ứng dụng: Dữ liệu học, dữ liệu đánh giá 
 đại diện; hoạt động tốt cho dữ liệu mới. Lấy mẫu dữ liệu
 ◼ Dữ liệu màu xanh: nhiều, không đại diện; đường đánh giá rời nét
 ◼ Thêm ít dữ liệu đỏ: có tính đại diện; đường liền nét, chính xác hơn
 Thu nhập quốc dân theo đầu người
 Mức độ hạnh phúc hạnh độ Mức 
 Thu nhập quốc dân theo đầu người
July 12, 2021 101
 Thách thức dữ liệu khác
 ◼ Chất lượng dữ liệu kém
 ◼ Dữ liệu chứa lỗi, ngoại lệ, nhiễu
 ◼ Phần công sức lớn trong KPDL
 ◼ Bước tiền xử lý dữ liệu ở Chương này
 ◼ Đặc trưng không liên quan
 ◼ Có đủ đặc trưng liên quan và không quá nhiều 
 đặc trưng không liên quan
 ◼ Lựa chọn đặc trưng
 ◼ Trích xuất đặc trưng
 ◼ Bổ sung dữ liệu nhằm bổ sung đặc trưng liên quan
July 12, 2021 102
 Thách thức mô hình: quá khớp DL học
 ◼ Khái niệm
 ◼ Mô hình quá tốt với dữ liệu mẫu song không khái quát tốt
 ◼ Giải pháp
 ◼ Đơn giản hóa mô hình: (i) giảm tham số mô hình, (ii) giảm số 
 đặc trưng (chiều) dữ liệu, (iii) hạn chế phạm vi mô hình
 ◼ Thu thập thêm dữ liệu đào tạo
 ◼ Giảm nhiễu dữ liệu (sửa lỗi dữ liệu, xóa ngoại lệ)
 ◼ Chính quy hóa mô hình: khống chế siêu tham số
July 12, 2021 103
 Cùng tập dữ liệu: quá khớp và không khớp
 Quá khớp: Chính quy hóa tham số mô hình
 Khống chế miền giá trị tham số để giảm số lượng tham số
July 12, 2021 104
 Thách thức mô hình: không khớp DL học
 ◼ Không khớp dữ liệu học
 ◼ Đối ngẫu với quá khớp: độ chính xác mô hình thấp
 ◼ Nâng bậc mô hình: bổ sung tham số
 ◼ Nâng cấp làm tốt đặc trưng dữ liệu
 ◼ Giảm ràng buộc đối với các tham số mô hình
July 12, 2021 105
 Thách thức mô hình: dùng một kỹ thuật
 ◼ Giới thiệu
 ▪ “Đưa cho một cậu bé một chiếc búa, cả thế giới chỉ là cái
 đinh”
 ▪ Nhiều người quen sử dụng một công cụ. Cần bộ công cụ
 ◼ Ví dụ
 ▪ Ít nhất so sánh phương pháp lựa chọn với phương pháp thông 
 thường base-line
 ▪ Nghiên cứu bài đăng tạp chí về mạng nơron: chỉ 17% tránh 
 được hai sai lầm 1 và 2
 ▪ Không sử dụng phương pháp khác → đổ lỗi cho thuật toán
 ▪ Lưu ý: Không có một mô hình cụ thể làm việc với sự khác biệt 
 lớn
 ▪ Tốt nhất: Nên sử dụng một bộ công cụ đầy đủ (Chỉ thêm có 5-
 10% nỗ lực).
July 12, 2021 106
 Không có một phương pháp tốt nhất
 ◼ Ví dụ về hiệu quả tương đối
 ▪ 5 thuật toán với 6 bộ dữ liệu: lỗi xấu nhất mỗi thuật toán > 0.6
 ▪ (John Elder, Elder Research & Stephen Lee, U. Idaho, 1997)
July 12, 2021 107
 Giải pháp: kết hợp nhiều kỹ thuật
 Về cơ bản, mọi phương pháp kết hợp thiện hiệu suất: lỗi cao 
 nhất 0.4
July 12, 2021 108