Bài giảng Khai phá dữ liệu (Data mining) - Chương 2: Các vấn đề tiền xử lý dữ liệu

Chương 2: Các vấn đề tiền xử lý dữ liệu 1 Nội dung  Tổng quan về giai đoạn tiền xử lý dữ liệu  Tóm tắt mô tả về dữ liệu  Làm sạch dữ liệu  Tích hợp dữ liệu  Biến đổi dữ liệu  Thu giảm dữ liệu  Rời rạc hóa dữ liệu  Tạo cây phân cấp ý niệm  Tóm tắt 2 Tổng quan về giai đoạn tiền xử lý dữ liệu  Giai đoạn tiền xử lý dữ liệu: - Các kỹ thuật datamining đều thực hiện trên các cơ sở dữ liệu, nguồn dữ liệu lớn. Đó là kết quả của quá trình ghi chép liên tục thông tin phản ánh hoạt động của con người, các quá trình tự nhiên - Các dữ liệu lưu trữ hoàn toàn là dưới dạng thô, chưa sẵn sàng cho việc phát hiện, khám phá thông tin ẩn chứa trong đó. Do vậy chúng cần phải qua giai đoạn tiền xử lý dữ liệu trước khi tiến hành bất kỳ một phân tích nào. 3 Tổng quan về giai đoạn tiền xử lý dữ liệu  Chất lượng dữ liệu (data quality) - Tính chính xác (accuracy): giá trị được ghi nhận đúng với giá trị thực. - Tính hiện hành (currency/timeliness): giá trị được ghi nhận không bị lỗi thời. - Tính toàn vẹn (completeness): tất cả các giá trị dành cho một biến/thuộc tính đều được ghi nhận. - Tính nhất quán (consistency): tất cả giá trị dữ liệu đều được biểu diễn như nhau trong tất cả các trường hợp. 4 Tổng quan về giai đoạn tiền xử lý dữ liệu 5 Data Cleaning Data Integration Data Sources Data Warehouse Task-relevant Data Selection/Transformation Data Mining Pattern Evaluation/ Presentation Patterns Tổng quan về giai đoạn tiền xử lý dữ liệu 6 Tổng quan về giai đoạn tiền xử lý dữ liệu  Các kỹ thuật tiền xử lý dữ liệu - Làm sạch dữ liệu (data cleaning/cleansing) - Tích hợp dữ liệu (data integration) - Biến đổi dữ liệu (data transformation) - Thu giảm dữ liệu (data reduction) 7 Tóm tắt mô tả về dữ liệu 8  Các kiểu dữ liệu Tóm tắt mô tả về dữ liệu  Xác định các thuộc tính (properties) tiêu biểu của dữ liệu về xu hướng chính (central tendency) và sự phân tán (dispersion) của dữ liệu - Các độ đo về xu hướng chính: mean, median, mode, midrange - Các độ đo về sự phân tán: quartiles, interquartile range (IQR), variance  Làm nổi bật các giá trị dữ liệu nên được xem như nhiễu (noise) hoặc phần tử biên (outliers), cung cấp cái nhìn tổng quan về dữ liệu 9 Tóm tắt mô tả về dữ liệu  Các độ đo về xu hướng chính của dữ liệu - Mean - Weighted arithmetic mean - Median - Mode: giá trị xuất hiện thường xuyên nhất trong tập dữ liệu - Midrange: giá trị trung bình của các giá trị lớn nhất và nhỏ nhất trong tập dữ liệu 10         evenNifxx oddNifx Median NN N 2/)( 12/2/ 2/ Tóm tắt mô tả về dữ liệu  Ví dụ: Mean: Giả sử chúng ta có các giá trị sau về lương (tính theo đơn vị nghìn đôla) theo thứ tự tăng dần như sau: 30, 36, 47, 50, 52, 52, 56, 60, 63, 70, 70, 110  Tính giá trị trung bình của các lương trên? 11 Tóm tắt mô tả về dữ liệu  Ví dụ: Median: Giả sử chúng ta có các giá trị sau về lương (tính theo đơn vị nghìn đôla) theo thứ tự tăng dần như sau: 30, 36, 47, 50, 52, 52, 56, 60, 63, 70, 70, 110  Tính median của các lương trên? - Dữ liệu trên được sắp xếp tăng dần, giá trị middlemost là 52 và 56. Do vậy median= (52+56)/2= 108/2= 54. 12 Tóm tắt mô tả về dữ liệu  Ví dụ: Mode, Midrange: Giả sử chúng ta có các giá trị sau về lương (tính theo đơn vị nghìn đôla) theo thứ tự tăng dần như sau: 30, 36, 47, 50, 52, 52, 56, 60, 63, 70, 70, 110  Mode, Midrange của các lương trên?  Mode là $52,000 và $70,000  Midrange= 13 Tóm tắt mô tả về dữ liệu  Các độ đo về sự phân tán của dữ liệu - Quartiles  The first quartile (Q1): the 25th percentile  The second quartile (Q2): the 50th percentile (median)  The third quartile (Q3): the 75th percentile - Interquartile Range (IQR) = Q3 – Q1  Outliers (the most extreme observations): giá trị nằm cách trên Q3 hay dưới Q1 một khoảng 1.5xIQR - Variance 14 Tóm tắt mô tả về dữ liệu  Ví dụ: Q1, Q2, Q3, IRQ: Giả sử chúng ta có các giá trị sau về lương (tính theo đơn vị nghìn đôla) theo thứ tự tăng dần như sau: 30, 36, 47, 50, 52, 52, 56, 60, 63, 70, 70, 110  Q1= 47$, Q3=63$, IRQ= 63-47=16$ 15 Tóm tắt mô tả về dữ liệu  Ví dụ: Variance and standard deviation: Giả sử chúng ta có các giá trị sau về lương (tính theo đơn vị nghìn đôla) theo thứ tự tăng dần như sau: 30, 36, 47, 50, 52, 52, 56, 60, 63, 70, 70, 110 16 Tóm tắt mô tả về dữ liệu 17 Q1 Q2 Q3 Tóm tắt mô tả về sự phân bố dữ liệu gồm năm trị số quan trọng: median, Q1, Q3, trị lớn nhất, và trị nhỏ nhất (theo thứ tự: Minimum, Q1, Median, Q3, Maximum). Tóm tắt mô tả về dữ liệu  Boxplots và Outliers - Boxplot là cách để biểu diễn sự phân tán dữ liệu - Boxplot được biểu diễn bởi 5 giá trị Minimum, Q1, Median, Q3, Maximum như sau: Chiều dài của box là interquartile range. Median được đánh dấu bởi đường gạch trong box. Hai gạch ngoài box là whiskers là the smallest (Minimum) và largest (Maximum) 18 Outliers (the most extreme observatio ns): giá trị nằm cách trên Q3 hay dưới Q1 một khoảng 1.5xIQR Làm sạch dữ liệu (data cleaning/cleansing):  Thiếu giá trị - Hãy xem xét một kho dữ liệu bán hàng và quản lý khách hàng. Trong đó có thể có một hoặc nhiều giá trị mà khó có thể thu thập được ví dụ như thu nhập của khách hàng. Vậy làm cách nào để chúng ta có được các thông tin đó? 19 Làm sạch dữ liệu (data cleaning/cleansing):  Thiếu giá trị - Hãy xem xét các phương pháp sau:  Bỏ qua các bộ  Điền vào các giá trị thiếu bằng tay  Sử dụng các giá trị quy ước để điền vào cho giá trị thiếu  Sử dụng các thuộc tính có nghĩa là để điền vào cho giá trị thiếu  Sử dụng các giá trị của các bộ cùng thể loại để thay thế cho giá trị thiếu  Sử dụng giá trị có tỉ lệ xuất hiện cao để điền vào cho các giá trị thiếu 20 Làm sạch dữ liệu (data cleaning/cleansing):  Thiếu giá trị - Bỏ qua các bộ: điều này thường được thực hiện khi thông tin nhãn dữ liệu bị mất. Phương pháp này không phải lúc nào cũng hiệu quả trừ khi các bộ có chứa một số thuộc tính không thực sự quan trọng. - Điền vào các giá trị thiếu bằng tay: phương pháp này thường tốn thời gian và có thể không khả thi cho một tập dữ liệu nguồn lớn với nhiều giá trị bị thiếu. - Sử dụng các giá trị quy ước để điền vào cho giá trị thiếu: Thay thế các giá trị thuộc tính thiếu bởi cùng một hằng số quy ước, chẳng hạn như một nhãn ghi giá trị “Không biết” hoặc “∞”. Tuy vậy điều này cũng có thể khiến cho chương trình khai phá dữ liệu hiểu nhầm trong một số trường hợp và đưa ra các kết luận không hợp lý. 21 Làm sạch dữ liệu (data cleaning/cleansing):  Thiếu giá trị - Sử dụng các thuộc tính có nghĩa là để điền vào cho giá trị thiếu: Ví dụ, ta biết thu nhập bình quân đầu người của một khu vực là 800.000đ, giá trị này có thể được dùng thể thay thế cho giá trị thu nhập bị thiếu của khách hàng trong khu vực đó. - Sử dụng các giá trị của các bộ cùng thể loại để thay thế cho giá trị thiếu: Ví dụ, nếu khách hàng A thuộc cùng nhóm phân loại theo rủi ro tín dụng với một khách hàng B khác trong khi đó khách hàng này có thông tin thu nhập bình quân. Ta có thể sử dụng giá trị đó để điền vào cho giá trị thu nhập bình quân của khách hàng A . - Sử dụng giá trị có tỉ lệ xuất hiện cao để điền vào cho các giá trị thiếu: Điều này có thể xác định bằng phương pháp hồi quy, các công cụ suy luận dựa trên lý thuyết Bayesian hay cây quyết định 22 Làm sạch dữ liệu (data cleaning/cleansing):  Dữ liệu nhiễu - Nhiễu dữ liệu là một lỗi ngẫu nhiên hay do biến động của các biến trong quá trình thực hiện, hoặc sự ghi chép nhầm lẫn không được kiểm soát - Ví dụ cho thuộc tính như giá cả, làm cách nào để có thể làm mịn thuộc tính này để loại bỏ dữ liệu nhiễu. Hãy xem xét các kỹ thuật làm mịn sau:  Binning  Hồi quy  Nhóm cụm 23 Làm sạch dữ liệu (data cleaning/cleansing): 24 Làm sạch dữ liệu (data cleaning/cleansing):  Dữ liệu nhiễu - Binning: Làm mịn một giá trị dữ liệu được xác định thông qua các giá trị xung quanh nó. - Ví dụ, các giá trị giá cả được sắp xếp trước sau đó phân thành các dải khác nhau có cùng kích thước 3 (tức mỗi “Bin” chứa 3 giá trị). - Khi làm mịn trung vị trong mỗi bin, các giá trị sẽ được thay thế bằng giá trị trung bình các giá trị có trong bin - Làm mịn biên: các giá trị nhỏ nhất và lớn nhất được xác định và dùng làm danh giới của bin. Các giá trị còn lại của bin sẽ được thay thế bằng một trong hai giá trị trên tùy thuộc vào độ lệch giữa giá trị ban đầu với các giá trị biên đó. - Ví dụ, bin 1 có các giá trị 4, 8, 15 với giá trị trung bình là 9. Do vậy nếu làm mịn trung vị các giá trị ban đầu sẽ được thay thế bằng 9. Còn nếu làm mịn biên giá trị 8 ở gần giá trị 4 hơn nên nó được thay thế bằng 4. 25 Làm sạch dữ liệu (data cleaning/cleansing):  Dữ liệu nhiễu - Hồi quy: Phương pháp thường dùng là hồi quy tuyến tính, để tìm ra được một mối quan hệ tốt nhất giữa hai thuộc tính (hoặc các biến), từ đó một thuộc tính có thể dùng để dự đoán thuộc tính khác. - Hồi quy tuyến tính đa điểm là một sự mở rộng của phương pháp trên, trong đó có nhiều hơn hai thuộc tính được xem xét, và các dữ liệu tính ra thuộc về một miền đa chiều. 26 x y y = x + 1 X1 Y1 Y1’  Dữ liệu nhiễu - Phân tích cụm (cluster analysis): Các giá trị tương tự nhau được tổ chức thành các nhóm hay “cụm" trực quan. Các giá trị rơi ra bên ngoài các nhóm này sẽ được xem xét để làm mịn. 27 Làm sạch dữ liệu (data cleaning/cleansing):  Xử lý dữ liệu không nhất quán - Định nghĩa của dữ liệu không nhất quán  Dữ liệu được ghi nhận khác nhau cho cùng một đối tượng/thực thể  discrepancies from inconsistent data representations  2004/12/25 và 25/12/2004  Dữ liệu được ghi nhận không phản ánh đúng ngữ nghĩa cho các đối tượng/thực thể  Ràng buộc khóa ngoại - Nguyên nhân  Sự không nhất quán trong các qui ước đặt tên hay mã dữ liệu  Định dạng không nhất quán của các vùng nhập liệu  Thiết bị ghi nhận dữ liệu, 28 Làm sạch dữ liệu (data cleaning/cleansing):  Xử lý dữ liệu không nhất quán (inconsistent data) - Giải pháp  Tận dụng siêu dữ liệu, ràng buộc dữ liệu, sự kiểm tra của nhà phân tích dữ liệu cho việc nhận diện  Điều chỉnh dữ liệu không nhất quán bằng tay  Các giải pháp biến đổi/chuẩn hóa dữ liệu tự động 29 Làm sạch dữ liệu (data cleaning/cleansing):  Trong nhiều bài toán phân tích, chúng ta phải đồng ý rằng nguồn dữ liệu dùng để phân tích không thống nhất. Để có thể phân tích được, các dữ liệu này cần phải được tích hợp, kết hợp thành một kho dữ liệu thống nhất.  Về dạng thức, các nguồn dữ liệu có thể được lưu trữ rất đa dạng từ: các cơ sở dữ liệu phổ dụng, các tập tin flat- file, các dữ liệu khối .  Vấn đề đặt ra là làm thế nào có thể tích hợp chúng mà vẫn đảm bảo tính tương đương của thông tin giữa các nguồn 30 Tích hợp dữ liệu (data integration)  Ví dụ: làm thế nào mà người phân tích dữ liệu hoặc máy tính chắc chắn rằng thuộc tính id của khách hàng trong một cơ sở dữ liệu A và số hiệu cust trong một flat-file là các thuộc tính giống nhau về tính chất?  Việc tích hợp luôn cần các thông tin diễn tả tính chất của mỗi thuộc tính (siêu dữ liệu) như: tên, ý nghĩa, kiểu dữ liệu, miền xác định, các quy tắc xử lý giá trị rỗng, bằng không . Các siêu dữ liệu sẽ được sử dụng để giúp chuyển đổi các dữ liệu. Do vậy bước này cũng liên quan đến quá trình làm sạch dữ liệu. 31 Tích hợp dữ liệu (data integration)  Dư thừa dữ liệu: - Đây cũng là một vấn đề quan trọng, ví dụ như thuộc tính doanh thu hàng năm có thể là dư thừa nếu như nó có thể được suy diễn từ các thuộc tính hoặc tập thuộc tính khác. 32 Tích hợp dữ liệu (data integration)  Dư thừa dữ liệu: - Phát hiện dư thừa: phân tích tương quan (correlation analysis)  Dựa trên dữ liệu hiện có, kiểm tra khả năng dẫn ra một thuộc tính B từ thuộc tính A.  Đối với các thuộc tính rời rạc (categorical/discrete attributes), đánh giá tương quan giữa hai thuộc tính với phép kiểm thử chi-square (2).  Đối với các thuộc tính số (numerical attributes), đánh giá tương quan giữa hai thuộc tính với các hệ số tương quan bằng cách sử dụng correlation coefficient và covariance 33 Tích hợp dữ liệu (data integration)  Phân tích tương quan giữa hai thuộc tính rời rạc A và B - A có c giá trị phân biệt, a1, a2, , ac. - B có r giá trị phân biệt, b1, b2, , br. - oij: số lượng đối tượng (tuples) quan sát được có trị thuộc tính A là ai và trị thuộc tính B là bj. - eij: số lượng đối tượng (tuples) mong đợi có trị thuộc tính A là ai và trị thuộc tính B là bj. - count(A=ai): số lượng đối tượng có trị thuộc tính A là ai. - count(B=bj): số lượng đối tượng có trị thuộc tính B là bj. 34 Tích hợp dữ liệu (data integration)  Phân tích tương quan giữa hai thuộc tính rời rạc A và B - Phép kiểm thống kê chi-square kiểm tra giả thuyết liệu A và B có độc lập với nhau dựa trên một mức quan trọng (significance level) với bậc tự do (degree of freedom).  Nếu giả thuyết bị loại bỏ thì A và B có sự liên hệ với nhau dựa trên thống kê. - Bậc tự do (degree of freedom): (r-1)*(c-1)  Tra bảng phân bố chi-square để xác định giá trị 2.  Nếu giá trị tính toán được lớn hơn hay bằng trị tra bảng được thì hai thuộc tính A và B độc lập nhau (giả thuyết đúng). 35 Tích hợp dữ liệu (data integration)  Phân tích tương quan giữa hai thuộc tính rời rạc A và B - Ví dụ: phân tích tương quan của các thuộc tính sử dụng phương pháp 2 - Giả sử có một nhóm 1500 người được khảo sát. Giới tính của họ được ghi nhận sau đó họ sẽ được hỏi về thể loại sách yêu thích thuộc hai dạng hư cấu và viễn tưởng. Như vậy ở đây có hai thuộc tính “giới tính” và “sở thích đọc”. Số lần xuất hiện (observed frequencies) của các trường hợp được cho trong bảng sau: (các số trong ngoặc là expected frequencies) 36 Tích hợp dữ liệu (data integration)  Phân tích tương quan giữa hai thuộc tính rời rạc A và B  Vậy chúng ta tính được 37 Tích hợp dữ liệu (data integration)  Phân tích tương quan giữa hai thuộc tính rời rạc A và B  Từ bảng dữ liệu cho thấy bậc tự do (r-1)(c-1) = (2-1)(2- 1) = 1. Với 1 bậc tự do, giá trị cần để bác bỏ giả thiết này ở mức 0.001 là 10.828. Và với giá trị tính được như trên 507.93 > 10.828 nên chúng ta có thể bát bỏ giả thuyết sở thích đọc là độc lập với giới tính. Và kết luận rằng: hai thuộc tính này có một quan hệ tương quan khá mạnh trong nhóm người được khảo sát. 38 Tích hợp dữ liệu (data integration)  Phân tích tương quan giữa hai thuộc tính số A và B (Correlation coefficient) Trong đó: - N là số bộ - ai và bi là các giá trị của thuộc tính A và B tại bộ thứ i - và là giá trị trung bình tương ứng của A và B - σA và σB biểu diễn độ lệch chuẩn của A và B - là tổng của tích AB (với mỗi bộ, giá trị của thuộc tính A được nhân với giá trị của thuộc tính b trong bộ đó) - Lưu ý rằng: -1<=r A,B <= +1 39 Tích hợp dữ liệu (data integration) A B  Dư thừa dữ liệu:  Nếu r A,B lớn hơn 0, thì A và B có khả năng có mối liên hệ tương quan với nhau, nghĩa là nếu giá trị A tăng thì giá trị của B cũng tăng lên. Giá trị này càng cao thì mối quan hệ càng chặt chẽ. Và hệ quả là nếu giá trị đủ cao thì một trong hai thuộc tính A (hoặc B) có thể được loại bỏ.  Nếu r A,B bằng 0 thì A và B là độc lập với nhau và giữa chúng không có mối quan hệ nào.  Nếu r A,B nhỏ hơn 0 thì A và B có mối quan hệ tương quan nghịch, khi đó nếu một thuộc tính tăng thì giá trị của thuộc tính kia giảm đi. 40 Tích hợp dữ liệu (data integration)  Dư thừa dữ liệu:  Chú ý rằng, nếu giữa A và B có mối quan hệ tương quan thì không có nghĩa chúng có mối quan hệ nhân quả, nghĩa là A hoặc B biến đổi là do sự tác động từ thuộc tính kia.  Ví dụ có thể xem xét mối quan hệ tương quan giữa số bệnh viện và số vụ tai nạn ô tô ở một địa phương. Hai thuộc tính này thực sự không có quan hệ nhân quả trực tiếp mà chúng quan hệ nhân quả với một thuộc tính thứ 3 là dân số 41 Tích hợp dữ liệu (data integration) 42  Phân tích tương quan giữa hai thuộc tính số A và B (Covariance)  Covariance tương tự với correlation  Covariance giữa A và B được định nghĩa như sau: Tích hợp dữ liệu (data integration) Correlation coefficient:  It can be simplified in computation as  Suppose two stocks A and B have the following values in one week: (2, 5), (3, 8), (5, 10), (4, 11), (6, 14).  Question: If the stocks are affected by the same industry trends, will their prices rise or fall together? - E(A) = (2 + 3 + 5 + 4 + 6)/ 5 = 20/5 = 4 - E(B) = (5 + 8 + 10 + 11 + 14) /5 = 48/5 = 9.6 - Cov(A,B) = (2×5+3×8+5×10+4×11+6×14)/5 − 4 × 9.6 = 4  Thus, A and B rise together since Cov(A, B) > 0. Tích hợp dữ liệu (data integration) Ví dụ: Covariance 44  Phân tích tương quan giữa hai thuộc tính số A và B Tích hợp dữ liệu (data integration) A B A B A B A B A B  Vấn đề mâu thuẫn giá trị dữ liệu - Cho cùng một thực thể thật, các giá trị thuộc tính đến từ các nguồn dữ liệu khác nhau có thể khác nhau về cách biểu diễn (representation), đo lường (scaling), và mã hóa (encoding).  Representation: “2004/12/25” với “25/12/2004”.  Scaling: thuộc tính weight trong các hệ thống đo khác nhau với các đơn vị đo khác nhau, thuộc tính price trong các hệ thống tiền tệ khác nhau với các đơn vị tiền tệ khác nhau.  Encoding: “yes” và “no” với “1” và “0”. 45 Tích hợp dữ liệu (data integration) Biến đổi dữ liệu (data transformation)  Trong phần này các dữ liệu sẽ được biến đổi sang các dạng phù hợp cho việc khai phá dữ liệu. Các phương pháp thường thấy như: - Làm mịn: Phương pháp này loại bỏ các trường hợp nhiễu khỏi dữ liệu ví dụ như các phương pháp binning, hồi quy, nhóm cụm. - Tổng hợp: trong đó tổng hợp hoặc tập hợp các hành động được áp dụng trên dữ liệu. Ví dụ thấy rằng doanh số bán hàng hàng ngày có thể được tổng hợp để tính toán hàng tháng và hàng năm. Bước này thường được sử dụng để xây dựng một khối dữ liệu cho việc phân tích 46 Biến đổi dữ liệu (data transformation)  Trong phần này các dữ liệu sẽ được biến đổi sang các dạng phù hợp cho việc khai phá dữ liệu. Các phương pháp thường thấy như: - Khái quát hóa dữ liệu: trong đó các dữ liệu mức thấp hoặc thô được thay thế bằng các khái niệm ở mức cao hơn thông qua kiến trúc khái niệm. - Ví dụ, các thuộc tính phân loại ví dụ như “Đường phố” có thể khái quát hóa lên mức cao hơn thành “Thành phố” hay “Quốc gia”. Tương tự như vậy các giá trị số, như tuổi có thể được ánh xạ lên khái niệm cao hơn như “Trẻ”, “Trung niên”, “Có tuổi” 47 Biến đổi dữ liệu (data transformation)  Trong phần này các dữ liệu sẽ được biến đổi sang các dạng phù hợp cho việc khai phá dữ liệu. Các phương pháp thường thấy như: - Chuẩn hóa: trong đó các dữ liệu của thuộc tính được quy về các khoảng giá trị nhỏ hơn ví dụ như từ -1.0 đến 1.0, hoặc từ 0.0 đến 1.0 - Xác định thêm thuộc tính, trong đó các thuộc tính mới sẽ được thêm vào nguồn dữ liệu để giúp cho quá trình khai phá. 48  Chuẩn hóa: - Một thuộc tính được chuẩn hóa bằng cách ánh xạ một cách có tỉ lệ dữ liệu về một khoảng xác định ví dụ như 0.0 đến 1.0. - Chuẩn hóa là một phần hữu ích của thuật toán phân lớp trong mạng noron, hoặc thuật toán tính toán độ lệch sử dụng trong việc phân lớp hay nhóm cụm các phần tử liền kề. Chúng ta sẽ xem xét ba phương pháp:  min-max  z-score  Normalization by decimal scaling 49 Biến đổi dữ liệu (data transformation)  Chuẩn hóa Min-Max: - Thực hiện một biến đổi tuyến tính trên dữ liệu ban đầu. Giả sử rằng minA và maxA là giá trị tối thiểu và tối đa của thuộc tính A. Chuẩn hóa min-max sẽ ánh xạ giá trị v của thuộc tính A thành v’ trong khoảng [new_minA, new_maxA] bằng cách tính toán : 50 Biến đổi dữ liệu (data transformation)  Chuẩn hóa Min-Max: - Ví dụ: Giả sử giá trị nhỏ nhất và lớn nhất cho thuộc tính “thu nhập bình quân” là 500.000 và 4.500.000. Chúng ta muốn ánh xạ giá trị 2.500.000 về khoảng [0.0, 1.0] sử dụng chuẩn hóa min-max. Giá trị mới thu được là 51 Biến đổi dữ liệu (data transformation)  Chuẩn hóa z-score: - Với phương pháp này, các giá trị của một thuộc tính A được chuẩn hóa dựa vào độ lệch tiêu chuẩn và trung bình của A. Một giá trị v của thuộc tính A được ánh xạ thành v’ như sau: - Với ví dụ phía trên: Giả sử thu nhập bình quân có độ lệch tiêu chuẩn và trung bình là: 500.000 và 1.000.000. Sử dụng phương pháp z-score thì giá trị 2.500.000 được ánh xạ thành 52 Biến đổi dữ liệu (data transformation)  Chuẩn hóa thay đổi số chữ số phần thập phân (decimal scale): - Phương pháp này sẽ di chuyển dấu phân cách phần thập phân của các giá trị của thuộc tính A. - Số chữ số sau dấu phân cách phần thập phân được xác định phụ thuộc vào giá trị tuyệt đối lớn nhất có thể có của thuộc tính A. Khi đó giá trị v sẽ được ánh xạ thành v’ bằng cách tính: 53 Biến đổi dữ liệu (data transformation)  Chuẩn hóa thay đổi số chữ số phần thập phân (decimal scale): - Trong đó j là giá trị nguyên nhỏ nhất thỏa mãn Max(|v’|) < 1 - Ví dụ: Giả sử rằng các giá trị của thuộc tính A được ghi nhận nằm trong khoảng -968 đến 917. Giá trị tuyệt đối lớn nhất của miền là 986. Để thực hiện chuẩn hóa theo phương pháp ánh xạ này, trước đó chúng ta mang các giá trị chia cho 1.000 (j = 3). Như vậy giá trị -986 sẽ chuyển thành -0.986 và 917 được chuyển thành 0.917 54 Biến đổi dữ liệu (data transformation)  Việc khai phá dữ liệu luôn được tiến hành trên các kho dữ liệu khổng lồ và phức tạp.  Các kỹ thuật khai phá khi áp dụng trên chúng luôn tốn thời gian cũng như tài nguyên của máy tính.  Do vậy đòi hỏi chúng cần được thu giảm trước khi áp dụng các kỹ thuật khai phá. 55 Thu giảm dữ liệu (data reduction):  Một số chiến lược thu giảm dữ liệu như sau: - Tổng hợp khối dữ liệu (data cube aggregation) - Thu giảm chiều (dimensionality reduction)  Chọn một số thuộc tính (attribute subset selection)  Chuyển dạng sóng (Wavelet Transformation)  Phân tích thành phần chính (Principal Component Analysis ) - Thu giảm lượng (numerosity reduction) - Nén dữ liệu - Rời rạc hóa (discretization) - Tạo phân cấp ý niệm (concept hierarchy generation) 56 Thu giảm dữ liệu (data reduction):  Tổng hợp khối dữ liệu (data cube aggregation): Hãy xem xét dữ liệu bán hàng của một đơn vị, các dữ liệu đó được tổ chức báo cáo theo hàng quý cho các năm từ 2008 đến 2010. Tuy nhiên việc khai phá dữ liệu lại quan tâm hơn đến các báo cáo bán hàng theo năm chứ không phải theo từng quý. Do đó các dữ liệu nên được tổng hợp thành báo cáo tổng về tình hình bán hàng theo năm hơn là theo quý 57 Sum() cube: Sale Thu giảm dữ liệu (data reduction):  Tổng hợp khối dữ liệu(data cube aggregation) - Phân cấp khái niệm có thể tồn tại ở mỗi thuộc tính, nó cho phép phân tích dữ liệu ở nhiều mức trừu tượng. - Ví dụ: phân cấp chi nhánh cho phép các chi nhánh được nhóm lại theo từng vùng dựa trên địa chỉ. Khối dữ liệu cho phép truy cập nhanh đến các dữ liệu đã tính toán, tổng hợp do vậy nó khá phù hợp với các quá trình khái phá. 58 Thu giảm dữ liệu (data reduction):  Tổng hợp khối dữ liệu(data cube aggregation) - Các khối dữ liệu được tạo ở mức trừu tượng thấp thường được gọi là cuboid. Các cuboid tương ứng với một tập thực thể nào đó ví dụ như người bán hàng, khách hàng. Các khối này cung cấp nhiều thông tin hữu dụng cho quá trình phân tích. Khối dữ liệu ở mức trừu tượng cao gọi là apex cuboid, trong hình trên thể hiện dữ liệu bán hàng cho cả 3 năm, tất cả các loại mặt hàng và các chi nhánh. Khối dữ liệu được tạo từ nhiều mức trừu tượng thường được gọi là cuboids, do vậy khối dữ liệu thường được gọi bằng tên khác là lưới cuboids. 59 Thu giảm dữ liệu (data reduction):  Chọn một số thuộc tính: - Nguồn dữ liệu dùng phân tích có thể chứa hàng trăm thuộc tính, rất nhiều trong số đó có thể không cần cho việc phân tích hoặc chúng là dư thừa. - Ví dụ: nếu nhiệm vụ phân tích chỉ liên quan đến việc phân loại khách hàng xem họ có hoặc không muốn mua một đĩa nhạc mới hay không. Khi đó thuộc tính điện thoại của khách hàng là không cần thiết khi so với các thuộc tính như độ tuổi, sở thích âm nhạc 60 Thu giảm dữ liệu (data reduction):  Chọn một số thuộc tính: - Mặc dù vậy việc lựa chọn thuộc tính nào cần quan tâm là một việc khó khăn và mất thời gian đặt biệt khi các đặc tính của dữ liệu là không rõ ràng. Giữ các thuộc tính cần, bỏ các thuộc tính không hữu ích cũng sẽ có thể gây nhầm lẫn, và sai lệch kết quả của các thuật toán khai phá dữ liệu. - Phương pháp này rút gọn kích thước dữ liệu bằng cách loại bỏ các thuộc tính không hữu ích hoặc dư thừa (hoặc loại bỏ các chiều). Mục đích chính là tìm ra tập thuộc tính nhỏ nhất sao cho khi áp dụng các phương pháp khai phá dữ liệu thì kết quả thu được là gần sát nhất với kết quả khi sử dụng tất cả các thuộc tính. 61 Thu giảm dữ liệu (data reduction):  Chọn một số thuộc tính - Vậy làm cách nào để tìm ra một tập thuộc tính con đủ tốt từ tập thuộc tính ban đầu. - Với N thuộc tính chúng ta sẽ có 2n tập thuộc tính con. Việc phát sinh và xem xét hết các tập này là khá tốn công sức cũng như tài nguyên, đặc biệt khi N và số các lớp dữ liệu tăng lên. - Do vậy cần có các phương pháp khác, một trong số đó là phương pháp tìm kiếm tham lam, nó sẽ duyệt qua không gian thuộc tính và tìm kiếm các lựa chọn tốt nhất vào thời điểm xét. 62 Thu giảm dữ liệu (data reduction):  Chọn một số thuộc tính 63 Thu giảm dữ liệu (data reduction):  Chọn một số thuộc tính - Các kỹ thuật lựa chọn thường dùng như:  Lựa chọn tăng dần: Xuất phát từ một tập rỗng các thuộc tính, các thuộc tính tốt nhất mỗi khi xác định được sẽ được thêm vào tập này. Lặp lại bước trên cho đến khi không thêm được thuộc tính nào nữa.  Loại bớt: Xuất phát từ tập có đầy đủ các thuộc tính. Ở mỗi bước loại ra các thuộc tính tồi nhất.  Kết hợp giữa phương pháp loại bớt và lựa chọn tăng dần bằng cách tại mỗi bước ngoài việc lựa chọn thêm các thuộc tính tốt nhất đưa vào tập thì cũng đồng thời loại bỏ đi các thuộc tính tồi nhất khỏi tập đang xét.  Cây quyết định: Khi sử dụng, cây được xây dựng từ nguồn dữ liệu ban đầu. Tất cả các thuộc tính không xuất hiện trên cây được coi là không hữu ích. Tập các thuộc tính có trên cây sẽ là tập thuộc tính rút gọn 64 Thu giảm dữ liệu (data reduction):  Chọn một số thuộc tính: - Việc lựa chọn ra thuộc tính tốt (xấu) được xác định thông qua các phép kiểm thống kê, trong đó giả sử rằng thuộc tính đang xét là độc lập với các thuộc tính khác hoặc phương pháp đánh giá thuộc tính sử dụng độ đo thông tin thường được dùng trong việc xây dựng cây quyết định phân lớp 65 Thu giảm dữ liệu (data reduction):  Biến đổi wavelet (wavelet transforms) - Discrete wavelet transform (DWT) là kỹ thuật xử lý tín hiệu dạng linear mà khi áp dụng với vector dữ liệu X, chuyển vector đó thành 1 vector khác dạng số X’: wavelet coefficients. Hai vector này có cùng độ dài. - Khi áp dụng kỹ thuật này để thu giảm dữ liệu, chúng ta giả sử rằng mỗi bộ như là 1 vector dữ liệu n- chiều là X = (x1, x2, , x3) 66 Thu giảm dữ liệu (data reduction):  Biến đổi wavelet (wavelet transforms) - Dữ liệu được chuyển đổi thành dạng sóng có thể bị cắt bỏ bớt. - Phép tính xấp xỉ nén của dữ liệu: chỉ lưu một mảnh nhỏ các hệ số sóng lớn nhất của wavelet coefficients - DWT thì tương tự như Discrete Fourier transform (DFT), nhưng nén tổn thất tốt hơn, có nghĩa là cùng số lượng coefficient được giữ lại trong DWT và DFT của 1 vector cho sẵn, thì DWT sẽ cho ra kết quả xấp xỉ chính xác so với dữ liệu ban đầu hơn. 67 Thu giảm dữ liệu (data reduction):  Biến đổi wavelet (wavelet transforms) - Do vậy, đối với một phép xấp xỉ tương đương, DWT yêu cầu nhiều bộ nhớ hơn so với DFT. - Chuyển đổi Wavelet có thể được áp dụng trong không gian đa chiều chẳng hạn như khối dữ liệu (data cube). - Chuyển đổi Wavelet cho kết quả tốt đối với dữ liệu thưa thớt hay bị lệch và với dữ liệu với các thuộc tính có thứ tự. - Chuyển đổi Wavelet có nhiều ứng dụng trong thực tế: nén ảnh, computer vision,, phân tích dữ liệu chuỗi thời gian, làm sạch dữ liệu 68 Thu giảm dữ liệu (data reduction): 69 DWT cho nén ảnh Image Low Pass High Pass Low Pass High Pass Low Pass High Pass Thu giảm dữ liệu (data reduction):  Biến đổi wavelet (wavelet transforms) - Do vậy, đối với một phép xấp xỉ tương đương, DWT yêu cầu nhiều bộ nhớ hơn so với DFT. - Chuyển đổi Wavelet có thể được áp dụng trong không gian đa chiều chẳng hạn như khối dữ liệu (data cube). - Chuyển đổi Wavelet cho kết quả tốt đối với dữ liệu thưa thớt hay bị lệch và với dữ liệu với các thuộc tính có thứ tự. - Chuyển đổi Wavelet có nhiều ứng dụng trong thực tế: nén ảnh, computer vision, phân tích dữ liệu chuỗi thời gian, làm sạch dữ liệu 70 Thu giảm dữ liệu (data reduction):  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ố 71 Thu giảm dữ liệu (data reduction):  Phân tích thành phần chính (Principal Component Analysis ) - Dùng khi số chiều vector lớn. - Có thể sử dụng với các dữ liệu thưa thớt hay bị lệch. - Có thể áp dụng cho các thuộc tính có thứ tự và không thứ tự - So với chuyển đổi wavelet, PCA có khuynh hướng tốt hơn đối với dữ liệu thưa thớt, trong khi đó chuyển đổi wavelet thích hợp hơn đối với dữ liệu đa chiều. 72 Thu giảm dữ liệu (data reduction):  Phân tích thành phần chính (Principal Component Analysis )  Y1, Y2 là thành phần chính ban đầu được ánh xạ sang X1, X2 Thu giảm dữ liệu (data reduction): X1 X2 Y1 Y2  Thu giảm lượng (numerosity reduction) - Các kỹ thuật giảm lượng dữ liệu bằng các dạng biểu diễn dữ liệu thay thế. - Các phương pháp có thông số (parametric): mô hình ước lượng dữ liệu  các thông số được lưu trữ thay cho dữ liệu thật  Hồi quy - Các phương pháp phi thông số (nonparametric): lưu trữ các biểu diễn thu giảm của dữ liệu  Histogram, Clustering, Sampling 74 Thu giảm dữ liệu (data reduction):  Histogram - Chia dữ liệu thành các buckets và lưu giá trị trung bình(tổng) vào mỗi bucket - Partitioning rules:  Equal-width: equal bucket range  Equal-frequency (or equal-depth) 75 Thu giảm dữ liệu (data reduction): 0 5 10 15 20 25 30 35 40 10000 30000 50000 70000 90000  Clustering - Phân chia dữ liệu vào các nhóm và lưu biểu diễn của nhóm Thu giảm dữ liệu (data reduction):  Sampling (With or without Replacement) - Dùng tập ngẫu nhiên nhỏ hơn để thay tập dữ liệu lớn - Phương pháp lấy mẫu ngẫu nhiên không thay thế (SRSWOR) - Phương pháp lấy mẫu ngẫu nhiên có thay thế (SRSWR) - Phương pháp lấy mẫu theo nhóm/cấp (Cluster or Stratified Sampling) 77 Thu giảm dữ liệu (data reduction): Raw Data  Sampling (Cluster or Stratified Sampling) 78 Thu giảm dữ liệu (data reduction): Raw Data Cluster/Stratified Sample 79  Nén dữ liệu (data compression) - String compression - Audio/video compression - Time sequence is not audio - Dimensionality and numerosity reduction may also be considered as forms of data compression Thu giảm dữ liệu (data reduction): 80 Nén dữ liệu (data compression) Original Data Compressed Data lossless Original Data Approximated Thu giảm dữ liệu (data reduction): Rời rạc hóa dữ liệu  Giảm số lượng giá trị của một thuộc tính liên tục (continuous attribute) bằng các chia miền trị thuộc tính thành các khoảng (intervals)  Các nhãn (labels) được gán cho các khoảng (intervals) này và được dùng thay giá trị thực của thuộc tính  Các trị thuộc tính có thể được phân hoạch theo một phân cấp (hierarchical) hay ở nhiều mức phân giải khác nhau (multiresolution) 81 Rời rạc hóa dữ liệu  Rời rạc hóa dữ liệu cho các thuộc tính số (numeric attributes) - Các phân cấp ý niệm được dùng để thu giảm dữ liệu bằng việc thu thập và thay thế các ý niệm cấp thấp bởi các ý niệm cấp cao. - Các phân cấp ý niệm được xây dựng tự động dựa trên việc phân tích phân bố dữ liệu. - Chi tiết của thuộc tính sẽ bị mất. - Dữ liệu đạt được có ý nghĩa và dễ được diễn dịch hơn, đòi hỏi ít không gian lưu trữ hơn. 82 Rời rạc hóa dữ liệu  Các phương pháp rời rạc hóa dữ liệu cho các thuộc tính số - Binning - Histogram analysis - Interval merging by 2 analysis - Cluster analysis - Entropy-based discretization - Discretization by “natural/intuitive partitioning” 83 Tạo cây phân cấp ý niệm  Dữ liệu phân loại (categorical data) - Dữ liệu rời rạc (discrete data) - Miền trị thuộc tính phân loại (categorical attribute)  Số giá trị phân biệt hữu hạn  Không có thứ tự giữa các giá trị  Tạo phân cấp ý niệm cho dữ liệu rời rạc 84 Tạo cây phân cấp ý niệm  Các phương pháp tạo phân cấp ý niệm cho dữ liệu rời rạc (categorical/discrete data) - Đặc tả thứ tự riêng phần (partial ordering)/thứ tự toàn phần (total ordering) của các thuộc tính tường minh ở mức lược đồ bởi người sử dụng hoặc chuyên gia:  street < city < state < country - Đặc tả một phần phân cấp bằng cách nhóm dữ liệu tường minh:  {Urbana, Champaign, Chicago} < Illinois 85 Tạo cây phân cấp ý niệm  Các phương pháp tạo phân cấp ý niệm cho dữ liệu rời rạc (categorical/discrete data) - Đặc tả chỉ một tập riêng phần các thuộc tính (partial set of attributes)  E.g., only street < city, not others - Tạo phân cấp tự động (hay các mức thuộc tính) bằng cách phân tích số lượng các giá trị phân biệt  E.g., for a set of attributes: {street, city, state, country} 86 Tóm tắt  Dữ liệu thực tế: không đầy đủ (incomplete/missing), nhiễu (noisy), không nhất quán (inconsistent)  Quá trình tiền xử lý dữ liệu - Làm sạch dữ liệu: xử lý dữ liệu bị thiếu, làm trơn dữ liệu nhiễu, nhận dạng các phần tử biên, hiệu chỉnh dữ liệu không nhất quán - Tích hợp dữ liệu: vấn đề nhận dạng thực thể, vấn đề dư thừa, vấn đề mâu thuẫn giá trị dữ liệu - Biến đổi dữ liệu: làm trơn dữ liệu, kết hợp dữ liệu, tổng quát hóa, chuẩn hóa, xây dựng thuộc tính/đặc tính - Thu giảm dữ liệu: kết hợp khối dữ liệu, chọn một số thuộc tính, thu giảm chiều, rời rạc hóa và tạo phân cấp ý niệm 87 Tóm tắt  Rời rạc hóa dữ liệu - Thu giảm số trị của một thuộc tính liên tục (continuous attribute) bằng cách chia miền trị thành các khoảng (interval) có dán nhãn. Các nhãn này được dùng thay cho các giá trị thực. - Tiến hành theo hai cách: trên xuống (top down) và dưới lên (bottom up), có giám sát (supervised) và không có giám sát (unsupervised). - Tạo phân hoạch phân cấp/đa phân giải (multiresolution) trên các trị thuộc tính  phân cấp ý niệm cho thuộc tính số (numerical attribute)  Tạo cây phân cấp ý niệm - Hỗ trợ khai phá dữ liệu ở nhiều mức trừu trượng - Cho thuộc tính số (numerical attributes): binning, histogram analysis, entropy- based discretization, 2-merging, cluster analysis, discretization by intuitive partitioning - Cho thuộc tính phân loại/rời rạc (categorical/discrete attributes): chỉ định tường minh bởi người sử dụng hay chuyên gia, nhóm dữ liệu tường minh, dựa trên số lượng trị phân biệt (khác nhau) của mỗi thuộc tính 88