Bài giảng Kho dữ liệu và khai phá dữ liệu - Chương 2: Tiền xử lý dữ liệu

iệu: Chương 23Chapter 2: Tiền xử lý dữ liệuHiểu dữ liệu và chuẩn bị dữ liệuVai trò của tiền xử lý dữ liệuLàm sạch dữ liệuTích hợp và chuyển dạng dữ liệuRút gọn dữ liệuRời rạc và sinh kiến trúc khái niệm08 September 2021Kho dữ liệu và khai phá dữ liệu: Chương 24Những vấn đề cơ bản để hiểu dữ liệuCách thu thập được dữ liệu cần thiết để mô hình hóa: Data AcquisitionCách kết hợp dữ liệu tìm được từ các nguồn dữ liệu khác nhau Data Integeation.Mô tả dữ liệuData DescriptionĐánh giá chất lượng (độ sạch) của dữ liệuData Assessment08 September 2021Kho dữ liệu và khai phá dữ liệu: Chương 25Thu thập dữ liệuCách thu thập dữ liệu cần thiết để mô hình hóa Data Acquisition: Trích chọn dữ liệu theo câu hỏi từ CSDL tới tập tin phẳngNgôn ngữ hỏi bậc cao truy nhập trực tiếp CSDLKết nối mức thấp để truy nhập trực tiếp CSDLLoại bỏ ràng buộc không gian/thời gian khi di chuyển khối lượng lớn dữ liệuHỗ trợ việc quản lý và bảo quản dữ liệu tập trung hóaRút gọn sự tăng không cần thiết của dữ liệuTạo điều kiện quản trị dữ liệu tốt hơn để đáp ứng mối quan tâm đúng đắn08 September 2021Kho dữ liệu và khai phá dữ liệu: Chương 26Tích hợp dữ liệuCách kết hợp dữ liệu tìm được từ các nguồn dữ liệu khác nhau Data Integeation.08 September 2021Kho dữ liệu và khai phá dữ liệu: Chương 27Mô tả dữ liệuGiá trị kỳ vọng (mean)Xu hướng trung tâm của tập dữ liệuĐộ lệch chuẩn (Standard deviation)Phân bố dữ liệu xung quanh kỳ vọngCực tiểu (Minimum)Giá trị nhỏ nhấtCực đại (Maximum)Giá trị lớn nhấtBảng tần suất (Frequency tables)Phân bố tần suất giá trị của các biếnLược đồ (Histograms)Cung cấp kỹ thuật đồ họa biểu diễn tần số giá trị của một biến08 September 2021Kho dữ liệu và khai phá dữ liệu: Chương 28Mô tả dữ liệu, so sánh với phân bố chuẩn(chủ yếu trong miền [0,10])08 September 2021Kho dữ liệu và khai phá dữ liệu: Chương 29Đánh giá và lập hồ sơ dữ liệuĐánh giá dữ liệuĐịnh vị một vấn đề trong dữ liệu cần giải quyết: Tìm ra và quyết định cách nắm bắt vấn đềMô tả dữ liệu sẽ làm hiện rõ một số vấn đềKiểm toán dữ liệu: lập hồ sơ dữ liệu và phân tích ảnh hưởng của dữ liệu chất lượng kém.Lập hồ sơ dữ liệu (cơ sở căn cứ: phân bố dữ liệu)Tâm của dữ liệuCác ngoại lai tiềm năng bất kỳSố lượng và phân bố các khoảng trong trong mọi trường hợpBất cứ dữ liệu đáng ngờ, như mã thiếu (miscodes), dữ liệu học, dữ liệu test, hoặc chỉ đơn giản dữ liệu rácNhững phát hiện nên được trình bày dưới dạng các báo cáo và liẹt kế như các mốc quan trọng của kế hoạch08 September 2021Kho dữ liệu và khai phá dữ liệu: Chương 210Những vấn đề cơ bản để chuẩn bị dữ liệuCách thức làm sạch dữ liệu:Data CleaningCách thức diễn giải dữ liệu:Data TransformationCách thức nắm bắt giá trị thiếu: Data ImputationTrọng số của các trường hợp:Data Weighting and BalancingXử lý dữ liệu ngoại lai và không mong muốn khác:Data FilteringCách thức nắm bắt dữ liệu thời gian/chuỗi thời gian:Data AbstractionCách thức rút gọn dữ liệu để dùng: Data ReductionBản ghi : Data SamplingBiến: Dimensionality ReductionGiá trị: Data DiscretizationCách thức tạo biến mới: Data Derivation08 September 2021Kho dữ liệu và khai phá dữ liệu: Chương 211Chapter 2: Tiền xử lý dữ liệuHiểu dữ liệu và chuẩn bị dữ liệuVai trò của tiền xử lý dữ liệuLàm sạch dữ liệuTích hợp và chuyển dạng dữ liệuRút gọn dữ liệuRời rạc và sinh kiến trúc khái niệm08 September 2021Kho dữ liệu và khai phá dữ liệu: Chương 212Tính quan trọng của tiền xử lýKhông có dữ liệu tốt, không thể có kết quả khai phá tốt!Quyết định chất lượng phải dựa trên dữ liệu chất lượngChẳng hạn, dữ liệu bội hay thiếu là nguyên nhân thống không chính xác, thậm chí gây hiểu nhầm.Kho dữ liệu cần tích hợp nhất quán của dữ liệu chất lượngPhân lớn công việc xây dựng một kho dữ liệu là trích chọn, làm sạch và chuyển đổi dữ liệu —Bill Inmon .Dữ liệu có chất lượng cao nếu như phù hợp với mục đích sử dụng trong điều hành, ra quyết định, và lập kế hoạch08 September 2021Kho dữ liệu và khai phá dữ liệu: Chương 213Độ đo đa chiều chất lượng dữ liệuMulti-Dimensional Measure of Data QualityKhung đa chiều cấp nhận tốt:Độ chính xác (Accuracy)Tính đầy đủ (Completeness)Tính nhất quán (Consistency)Tính kịp thời (Timeliness)Độ tin cậy (Believability)Giá trị gia tăng (Value added)Biểu diễn được (Interpretability)Tiếp cận được (Accessibility)Phân loại bề rộng (Broad categories):Bản chất (intrinsic), ngữ cảnh (contextual),trình diễn (representational), và tiếp cận được (accessibility).08 September 2021Kho dữ liệu và khai phá dữ liệu: Chương 214Major Tasks in Data PreprocessingLàm sạch dữ liệuĐiền giá trị thiếu, làm trơn dữ liệu nhiễu, định danh hoặc xóa ngoại lai, và khử tính không nhất quánTích hợp dữ liệuTích hợp CSDL, khối dữ liệu hoặc tập tin phứcChuyển dạng dữ liệuChuẩn hóa và tổng hợpRút gọn dữ liệuThu được trình bày thu gọn về kích thước những sản xuất cùng hoặc tương tự kết quả phân tíchRời rạc hóa dữ liệuBộ phận đặc biệt của rút gọn dữ liệu (rút gọn miền giá trị) nhưng có độ quan trọng riêng, đặc biệt với dữ liệu số08 September 2021Kho dữ liệu và khai phá dữ liệu: Chương 215Các thành phần của tiền xử lý dữ liệu (Bảng 2.1)08 September 2021Kho dữ liệu và khai phá dữ liệu: Chương 216Chapter 2: Tiền xử lý dữ liệuHiểu dữ liệu và chuẩn bị dữ liệuVai trò của tiền xử lý dữ liệuLàm sạch dữ liệuTích hợp và chuyển dạng dữ liệuRút gọn dữ liệuRời rạc và sinh kiến trúc khái niệm08 September 2021Kho dữ liệu và khai phá dữ liệu: Chương 217Làm sạch dữ liệuLà quá trình xác định tính không chính xác, không đầy đủ/tính bất hợp lý của dữ liệuchỉnh sửa các sai sót và thiếu sót được phát hiện nâng cao chất lượng dữ liệu.Quá trình bao gồmkiểm tra định dạng, tính đầy đủ, tính hợp lý, miền giới hạn,xem xét dữ liệu để xác định ngoại lai (địa lý, thống kê, thời gian hay môi trường) hoặc các lỗi khác,đánh giá dữ liệu của các chuyên gia miền chủ đề.Quá trình thường dẫn đến loại bỏ, lập tài liệu và kiểm tra liên tiếp và hiệu chỉnh đúng bản ghi nghi ngờ.Kiểm tra xác nhận có thể được tiến hành nhằm đạt tính phù hợp với các chuẩn áp dụng, các quy luật, và quy tắc.08 September 2021Kho dữ liệu và khai phá dữ liệu: Chương 218Nguồn dữ liệu đơn: mức sơ đồ (Ví dụ)08 September 2021Kho dữ liệu và khai phá dữ liệu: Chương 219Nguồn dữ liệu đơn: mức thể hiện (Ví dụ)08 September 2021Kho dữ liệu và khai phá dữ liệu: Chương 220Nguồn dữ liệu phức: mức sơ đồ và thể hiện (Ví dụ)08 September 2021Kho dữ liệu và khai phá dữ liệu: Chương 221Làm sạch dữ liệuNguyên lý chất lượng dữ liệu cần được áp dụng ở mọi giai đoạn quá trình quản lý dữ liệu (nắm giữ, số hóa, lưu trữ, phân tích, trình bày và sử dụng). hai vấn đề cốt lõi để cải thiện chất lượng - phòng ngừa và chỉnh sửa Phòng ngừa liên quan chặt chẽ với thu thập và nhập dữ liệu vào CSDL.Tăng cường phòng ngừa lỗi, vẫn/tồn tại sai sót trong bộ dữ liệu lớn (Maletic và Marcus 2000) và không thể bỏ qua việc xác nhận và sửa chữa dữ liệuVai trò quan trọng“là một trong ba bài toán lớn nhất của kho dữ liệu”—Ralph Kimball“là bài toán “number one” trong kho dữ liệu”—DCI khảo sátCác bài toán thuộc làm sạch dữ liệuXử lý giá trị thiếuDữ liệu nhiễu: định danh ngoại lai và làm trơn.Chỉnh sửa dữ liệu không nhất quánGiải quyết tính dư thừa tạo ra sau tích hợp dữ liệu.08 September 2021Kho dữ liệu và khai phá dữ liệu: Chương 222Xử lý thiếu giá trịBỏ qua bản ghi có giá trị thiếu:Thường làm khi thiếu nhãn phân lớp (giả sử bài toán phân lớp)không hiểu quả khi tỷ lệ số giá trị thiếu lớn (bán giám sát)Điền giá trị thiếu bằng tay: tẻ nhạt tính khả thiĐiền giá trị thiếu tự động:Hằng toàn cục: chẳng hạn như“chưa biết”, có phải một lớp mới Trung bình giá trị thuộc tính các bản ghi hiện cóTrung bình giá trị thuộc tính các bản ghi cùng lớp: tinh hơnGiá trị khả năng nhất: dựa trên suy luận như công thức Bayes hoặc cây quyết định08 September 2021Kho dữ liệu và khai phá dữ liệu: Chương 223Dữ liệu nhiễuNhiễu: Lỗi ngẫu nhiênBiến dạng của một biến đo đượcGiá trị không chính xác doLỗi do thiết bị thu thập dữ liệuVấn đề nhập dữ liệu: người dùng hoặc máy có thể saiVấn đề truyền dữ liệu: sai từ thiết bị gửi/nhận/truyềnHạn chế của công nghệ: ví dụ, phần mềm có thể xử lý không đúngThiết nhất quán khi đặt tên: cũng một tên song cách viết khác nhauCác vấn đề dữ liệu khác yêu cầu làm sạch dữ liệuBộ bản ghiDữ liệu không đầy đủDữ liệu không nhất quán08 September 2021Kho dữ liệu và khai phá dữ liệu: Chương 224Nắm bắt dữ liệu nhiễu(Handle Noisy Data)Phương pháp đóng thùng (Binning):Sắp dữ liệu tăng và chia “đều” vào các thùngLàm trơn: theo trung bình, theo trung tuyến, theo biênPhân cụm (Clustering)Phát hiện và loại bỏ ngoại lai (outliers)Kết hợp kiểm tra máy tính và con ngườiPhát hiện giá trị nghi ngờ để con người kiểm tra (chẳng hạn, đối phó với ngoại lai có thể)Hồi quyLàm trơn: ghép dữ liệu theo các hàm hồi quy08 September 2021Kho dữ liệu và khai phá dữ liệu: Chương 225Phương pháp rời rạc hóa đơn giản (Simple Discretization Methods: Binning)Phân hoạch cân bẳng bề rộng Equal-width (distance) partitioning:Chia miền giá trị: N đoạn dài như nhau: uniform gridMiền giá trị từ A (nhỏ nhất) tới B (lớn nhất) ->W = (B –A)/N.Đơn giản nhất song bị định hướng theo ngoại lai.Không xử lý tốt khi dữ liệu không cân bằng (đều).Phân hoạch cân bằng theo chiều sâu Equal-depth (frequency) partitioning:Chia miền xác định thành N đoạn “đều nhau về số lượng”, các đoạn có xấp xỉ số ví dụ mẫu.Khả cỡ dữ liệu: tốt.Việc quản lý các thuộc tính lớp: có thể “khôn khéo”.08 September 2021Kho dữ liệu và khai phá dữ liệu: Chương 226Phương pháp xếp thùng làm trơn dữ liệu (Binning Methods for Data Smoothing)* Dữ liệu được xếp theo giá: 4, 8, 9, 15, 21, 21, 24, 25, 26, 28, 29, 34* Chia thùng theo chiều sâu: - Bin 1: 4, 8, 9, 15 - Bin 2: 21, 21, 24, 25 - Bin 3: 26, 28, 29, 34* Làm trơn thùng theo trung bình: - Bin 1: 9, 9, 9, 9 - Bin 2: 23, 23, 23, 23 - Bin 3: 29, 29, 29, 29* Làm trơn thùng theo biên: - Bin 1: 4, 4, 4, 15 - Bin 2: 21, 21, 25, 25 - Bin 3: 26, 26, 26, 3408 September 2021Kho dữ liệu và khai phá dữ liệu: Chương 227Phân tích cụm (Cluster Analysis)BÀI TOÁN PHÂN CỤMBài toánTập đối tượng D = {d}Phân tách D thành các cụmCác đối tượng trong một cụm: “tương tự” nhau (gần nhau)Đối tượng hai cụm: “không tương tự” nhau (xa nhau)Đo “tương tự” (gần) nhau ?Tiên đề phân cụm: Nếu người dùng lựa chọn một đối tượng d thì họ cũng lựa chọn các đối tượng cùng cụm với dĐưa ra một số độ đo “tương tự” theo biểu diễn đối tượngKhai thác “cách chọn lựa” của người dùngDạy bộ phân cumXây dựng độ đo tương đồngKhai thác thông tin bổ sungSố lượng cụm cho trước, số lượng cụm không cho trướcYÊU CẦU PHÂN CỤMTính phù hợpTạo cụm cần đảm bảo tính phân biệtCung cấp sự phân biệt cụm phù hợp với yêu cầu người dùng với các cụm không phù hợp khác.Tổng hợp phải dễ đọcCung cấp mô tả ngắn gọn và chính xác của các cụmTính đa hìnhĐối tượng nhiều chủ đềTránh hạn chế một đối tượng chỉ thuộc về một cụm.Sử dụng các mẩu thông tinPhương pháp phải tạo cụm “tốt”: chỉ dùng mẩu thông tin có đượcTránh phải chờ đợi hệ thống tải toàn bộ các đối tượng.MỘT SỐ PHƯƠNG PHÁP PHÂN CỤM ĐIỂN HÌNH Phân hoạchPhân hoạch tập thành các tập conĐánh giá theo các tiêu chíTối ưu chung, k-meanPhân cấpSử dụng ma trận khoảng cáchXây dựng kiến trúc phân cấp: từ dưới lên (AGNES) - từ trên xuống (DIANA)Dựa theo mật độDựa trên hàm mật độ các đối tượngLân cận, bán kính lân cận, số điểm tối thiểu ở một lân cậnMỘT SỐ PHƯƠNG PHÁP PHÂN CỤM ĐIỂN HÌNH Dựa theo lướiXây dựng cấu trúc lưới đa chiều: miền dữ liệu được chia thành hộp các cấpSelf Organization Matrix (SOM)Dựa trên mô hìnhGiả định một loại mô hình biểu diễn các cụmXác định tham số mô hình cho phép đặt tốt nhất tập cần phân cụm vàoĐỘ ĐO TRONG PHÂN CỤM WEB Độ đo tương đồngTồn tại một số độ đo, căn cứ vàoBiểu diễn đối tượng: d=(d1, d2, , dn) vectorMột số độ đo điển hình khoảng cách Minkowski (q=2: Khoảng cách Ơcơlit)độ đo tương tự (gần nhau): cosin hai vectơ hoặc đại lượng CoordLevel (q,d) vector bảnPHƯƠNG PHÁP LUẬN PHÂN CỤMTiếp cận theo phân hoạchPhân hoạch tập D thành k tập con {Di}Số lượng cụm k cho trước / không cho trướcMục tiêu phân hoạchHoặc cực tiểu tổng khoảng cách nội bộ tập conHoặc cực đại tổng tương tự nội bộ tập conKhối lượng tính toán“Nội bộ một tập con”: toàn bộ khoảng cách ? Khối lượng lớnThông qua đối tượng đại diện: Tính theo đối tượng đại diệnĐối tượng đại diện được thay đổiPHƯƠNG PHÁP LUẬN PHÂN CỤMTiếp cận theo hình họcQuy chiếu không gian nhiều chiều về hai chiềuPhương pháp self-organizing mapPhân bố các đối tượng không gian gốc vào không gian hai chiềuTiếp cận theo mô hình sinh và thống kêĐộ đo tương tự (khoảng cách) được người dùng cung cấpSinh ra một phân bố ngẫu nhiên các đối tượng theo độ đo đã choPHÂN HOẠCH BOTTOM-UP HACPhân cụm tích lũy (Agglomerative)Tên gọi khácbottom-up agglomerativehierarchical agglomerative clustering (HAC)Sử dụng biểu diễn vectơThuật toán (G: ký hiệu cho tập các cụm đối tượng hiện có)Khởi động: Gán mỗi đối tượng d thành một cụm {d}Trong khi |G| > 1 thực hiện lặpVới hai cụm  và  thuộc G là “gần nhau” theo độ đoĐặt  =   Loại bỏ  và  khỏi GBổ sung  vào G“hai cụm gần nhau”Độ đo nội bộ của cụm : s() tổng số hạng s(d,q): độ đo cosinGần nhau  và : cực đại min và max gần nhau các cặp phần tử. Lưu ý thời gian tính toán: tính tăng của thuật toánPHÂN HOẠCH TOP-DOWN VÀ BOTTOM-UP(xây dựng dendrogram) THUẬT TOÁN K-MEANGiới thiệuDạng cứng: theo trọng tâm của mỗi cụmTheo phần tử đại diện cho mỗi cụmĐối tượng: d=(d1, d2, , dn)Nội dung k-mean cứngKhởi động: Chọn tùy ý các vectơ trọng tâm cho các cụm c*/ Trong khi điều kiện “làm tốt hơn” vẫn cònVới mọi đối tượng dTìm cụm c có trọng tâm gần d nhấtGán d vào cụm cVới mọi cụm cTính toán lại trọng tâm theo theo các đối tượng thuộc nó /*Điều kiện “làm tốt hơn”Không/chuyển ít đối tượng từ cụm này sang cụm khácHoặc sự thay đổi ítThời gian thực hiệnThuật toán k-mean mềm liên quan chọn vectơ đại diện cụm08 September 2021Kho dữ liệu và khai phá dữ liệu: Chương 238Hồi quy (Regression)xyy = x + 1X1Y1Y1’08 September 2021Kho dữ liệu và khai phá dữ liệu: Chương 239Chapter 2: Tiền xử lý dữ liệuHiểu dữ liệu và chuẩn bị dữ liệuVai trò của tiền xử lý dữ liệuLàm sạch dữ liệuTích hợp và chuyển dạng dữ liệuRút gọn dữ liệuRời rạc và sinh kiến trúc khái niệm08 September 2021Kho dữ liệu và khai phá dữ liệu: Chương 240Tích hợp dữ liệuTích hợp dữ liệu (Data integration): Kết hợp dữ liệu từ nhiều nguồn thành một nguồn lưu trữ chungTích hợp sơ đồTích hợp sieu dữ liệu từ các nguồn khác nhauVấn đề định danh thực thế: xác định thực thể thực tế từ nguồn dữ liệu phức, chẳng hạn, A.cust-id  B.cust-#Phát hiện và giải quyết vấn đề thiết nhất quá dữ liệuCùng một thực thể thực sự: giá trị thuộc tính các nguồn khác nhau là khác nhauNguyên nhân: trình bày khác nhau, cỡ khác nhau, chẳng hạn, đơn vị quốc tế khác với Anh quốc08 September 2021Kho dữ liệu và khai phá dữ liệu: Chương 241Nắm bắt dư thừa trong tích hợp dữ liệu (Handling Redundancy in Data Integration)Dư thừa dữ liệu: thường có khi tích hợp từ nhiều nguồn khác nhauMột thuộc tính có nhiều tên khác nhau ở các CSDL khác nhauMột thuộc tính: thuộc tính “nguồn gốc” trong CSDL khác, chẳng hạn, doanh thu hàng nămDữ liệu dư thừa có thể đwocj phát hiện khi phân tích tương quanTích hợp cẩn trọng dữ liệu nguồn phức giúp giảm/tránh dư thừa, thiếu nhất quán và tăng hiệu quả tốc độ và chất lượng08 September 2021Kho dữ liệu và khai phá dữ liệu: Chương 242Chuyển dạng dữ liệuLàm trơn (Smoothing): loại bỏ nhiễu từ dữ liệuTổng hợp (Aggregation): tóm tắt, xây dựng khối dữ liệuTổng quát hóa (Generalization): leo kiến trúc khái niệmChuẩn hóa (Normalization): thu nhỏ vào miền nhỏ, riêngChuẩn hóa min-maxChuẩn hóa z-scoreChuẩn hóa tỷ lệ thập phânXây dựng thuộc tính/đặc trưngThuộc tính mới được xây dựng từ các thuộc tính đã có08 September 2021Kho dữ liệu và khai phá dữ liệu: Chương 243Chuyển đổi dữ liệu: Chuẩn hóaChuẩn hóa min-maxChuẩn hóa z-scoreChuẩn hóa tỷ lệ thập phânj : số nguyên nhỏ nhất mà Max(| |)Tập thuộc tinh rút gọn: {A1, A4, A6}Phân lớp cây quyết địnhĐồ thị dạng câyĐỉnh trong là một hàm testCác nhánh tương ứng với kết quả kiểm tra tại đỉnh trongCác lá là các nhãn, hoặc các lớp.Phân lớp cây quyết địnhPhân lớp cây quyết địnhPhân lớp cây quyết địnhXây dựng cây quyết định: Xây dựng cây quyết địnhPhương pháp top-downCắ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ớiSử dụng cây quyết định: phân lớp các đối tượng chưa được gán nhãn08 September 2021Kho dữ liệu và khai phá dữ liệu: Chương 253Phương pháp chọn đặc trưng HeuristicCó 2d tập con đặc trưng từ d đặc trưngMột vài phương pháp chọn dadực trưng heuristic:Các đặc trưng tốtnhất theo giả thiết độc lập đặc trưng: chọn từ kiểm thử điển hình.Lựa chọn đặc trưng khôn ngoan từng bước tốt nhất: Các thuộc tính đơn tốt nhất được chọn đầu tiênTiếp đó, chọn tốt nhất tiếp theo theo điều kiện đã chọn tốt nhất trước đó, ...Loại bỏ đặc trưng khôn ngoan từng bước:Loại bỏ lặp các đặc trưng tồi nhấtKết hợp lựa chọn và loại bỏ tốt nhất:Nhánh và phạm vi tối ưu:Sử dụng loại bỏ đặc trưng và tùy chọn08 September 2021Kho dữ liệu và khai phá dữ liệu: Chương 254Nén dữ liệu (Data Compression)Nén xâu (String compression)Tồn tại lý thuyết đầy đủ và thuật toán điều chỉnh tốtMất mát thông thườngCho phép lượng hạn chế thao tác không cần mở rộngNén Audio/videoNén mất mát điển hình, với tinh chế tiến bộĐôi khi các đoạn nhỏ tín hiệu có thể xây dựng lại mà không cần xây dựng lại toàn bộDãy thời gian không phải là audioNgắn điển hình và chậm theo thời gian08 September 2021Kho dữ liệu và khai phá dữ liệu: Chương 255Nén dữ liệu (Data Compression)Dữ liệu thực (Original Data)DL được nénCompressed DataĐỡ mất mátlosslessDữ liệu thực được xấp xỉOriginal DataApproximated Mất mát - lossy08 September 2021Kho dữ liệu và khai phá dữ liệu: Chương 256Chuyển dạng sóng (Wavelet Transformation)Discrete wavelet transform (DWT): linear signal processing, multiresolutional analysisCompressed approximation: store only a small fraction of the strongest of the wavelet coefficientsSimilar to discrete Fourier transform (DFT), but better lossy compression, localized in spaceMethod:Length, L, must be an integer power of 2 (padding with 0s, when necessary)Each transform has 2 functions: smoothing, differenceApplies to pairs of data, resulting in two set of data of length L/2Applies two functions recursively, until reaches the desired length Haar2Daubechie408 September 2021Kho dữ liệu và khai phá dữ liệu: Chương 257DWT cho nén ảnhImage Low Pass High Pass Low Pass High PassLow Pass High Pass08 September 2021Kho dữ liệu và khai phá dữ liệu: Chương 258Cho 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.Phân tích thành phần chính (Principal Component Analysis )08 September 2021Kho dữ liệu và khai phá dữ liệu: Chương 259X1X2Y1Y2Phân tích thành phần chính (PCA)08 September 2021Kho dữ liệu và khai phá dữ liệu: Chương 260Rút gọn kích thước sốPhương pháp tham sốAssume the data fits some model, estimate model parameters, store only the parameters, and discard the data (except possible outliers)Log-linear models: obtain value at a point in m-D space as the product on appropriate marginal subspaces Non-parametric methods Do not assume modelsMajor families: histograms, clustering, sampling 08 September 2021Kho dữ liệu và khai phá dữ liệu: Chương 261Hồi quy và mô hình logarit tuyến tínhLinear regression: Data are modeled to fit a straight lineOften uses the least-square method to fit the lineMultiple regression: allows a response variable Y to be modeled as a linear function of multidimensional feature vectorLog-linear model: approximates discrete multidimensional probability distributionsKho dữ liệu và khai phá dữ liệu: Chương 2Linear regression: Y =  +  XTwo parameters ,  and  specify the line and are to be estimated by using the data at hand.using the least squares criterion to the known values of Y1, Y2, , X1, X2, .Multiple regression: Y = b0 + b1 X1 + b2 X2.Many nonlinear functions can be transformed into the above.Log-linear models:The multi-way table of joint probabilities is approximated by a product of lower-order tables.Probability: p(a, b, c, d) = ab acad bcdPhân tích hồi quy và mô hình logarit tuyến tính08 September 2021Kho dữ liệu và khai phá dữ liệu: Chương 263Lược đồ (Histograms)A popular data reduction techniqueDivide data into buckets and store average (sum) for each bucketCan be constructed optimally in one dimension using dynamic programmingRelated to quantization problems.08 September 2021Kho dữ liệu và khai phá dữ liệu: Chương 264Phân cụmPartition data set into clusters, and one can store cluster representation onlyCan be very effective if data is clustered but not if data is “smeared”Can have hierarchical clustering and be stored in multi-dimensional index tree structuresThere are many choices of clustering definitions and clustering algorithms08 September 2021Kho dữ liệu và khai phá dữ liệu: Chương 265Rút gọn mẫu (Sampling)Allow a mining algorithm to run in complexity that is potentially sub-linear to the size of the dataChoose a representative subset of the dataSimple random sampling may have very poor performance in the presence of skewDevelop adaptive sampling methodsStratified sampling: Approximate the percentage of each class (or subpopulation of interest) in the overall database Used in conjunction with skewed dataSampling may not reduce database I/Os (page at a time).08 September 2021Kho dữ liệu và khai phá dữ liệu: Chương 266Rút gọn mẫu (Sampling)SRSWOR(simple random sample without replacement)SRSWRRaw Data08 September 2021Kho dữ liệu và khai phá dữ liệu: Chương 267Rút gọn mẫu (Sampling)Raw Data Cluster/Stratified Sample08 September 2021Kho dữ liệu và khai phá dữ liệu: Chương 268Rút gọn phân cấpUse multi-resolution structure with different degrees of reductionHierarchical clustering is often performed but tends to define partitions of data sets rather than “clusters”Parametric methods are usually not amenable to hierarchical representationHierarchical aggregation An index tree hierarchically divides a data set into partitions by value range of some attributesEach partition can be considered as a bucketThus an index tree with aggregates stored at each node is a hierarchical histogram08 September 2021Kho dữ liệu và khai phá dữ liệu: Chương 269Chapter 2: Tiền xử lý dữ liệuHiểu dữ liệu và chuẩn bị dữ liệuVai trò của tiền xử lý dữ liệuLàm sạch dữ liệuTích hợp và chuyển dạng dữ liệuRút gọn dữ liệuRời rạc và sinh kiến trúc khái niệm08 September 2021Kho dữ liệu và khai phá dữ liệu: Chương 270Rời rạc hóaThree types of attributes:Nominal — values from an unordered setOrdinal — values from an ordered setContinuous — real numbersDiscretization: divide the range of a continuous attribute into intervalsSome classification algorithms only accept categorical attributes.Reduce data size by discretizationPrepare for further analysis08 September 2021Kho dữ liệu và khai phá dữ liệu: Chương 271Rời rạc hóa và kiến trúc khái niệmDiscretization reduce the number of values for a given continuous attribute by dividing the range of the attribute into intervals. Interval labels can then be used to replace actual data valuesConcept hierarchies reduce the data by collecting and replacing low level concepts (such as numeric values for the attribute age) by higher level concepts (such as young, middle-aged, or senior)08 September 2021Kho dữ liệu và khai phá dữ liệu: Chương 272Rời rạc hóa và kiến trúc khái niệm với dữ liệu sốBinning (see sections before)Histogram analysis (see sections before)Clustering analysis (see sections before)Entropy-based discretizationSegmentation by natural partitioning08 September 2021Kho dữ liệu và khai phá dữ liệu: Chương 273Rời rạc hóa dựa trên EntropyGiven a set of samples S, if S is partitioned into two intervals S1 and S2 using boundary T, the entropy after partitioning isThe boundary that minimizes the entropy function over all possible boundaries is selected as a binary discretization.The process is recursively applied to partitions obtained until some stopping criterion is met, e.g.,Experiments show that it may reduce data size and improve classification accuracy08 September 2021Kho dữ liệu và khai phá dữ liệu: Chương 274Phân đoạn bằng phân hoạch tự nhiênQuy 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ấtNế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.08 September 2021Kho dữ liệu và khai phá dữ liệu: Chương 275Ví dụ luật 3-4-5(-$4000 -$5,000)(-$400 - 0)(-$400 - -$300)(-$300 - -$200)(-$200 - -$100)(-$100 - 0)(0 - $1,000)(0 - $200)($200 - $400)($400 - $600)($600 - $800)($800 - $1,000)($2,000 - $5, 000)($2,000 - $3,000)($3,000 - $4,000)($4,000 - $5,000)($1,000 - $2, 000)($1,000 - $1,200)($1,200 - $1,400)($1,400 - $1,600