Giảm kích thước dữ liệu trong Data mining

Hãy tưởng tượng rằng bạn đã chọn dữ liệu từ kho dữ liệu AllElectronics để phân tích. Bộ dữ liệu có thể sẽ rất lớn! Việc phân tích và khai thác dữ liệu phức tạp trên một lượng lớn dữ liệu có thể mất nhiều thời gian, khiến việc phân tích như vậy trở nên không thực tế hoặc không khả thi.

Các kỹ thuật giảm thiểu dữ liệu có thể được áp dụng để thu được sự trình bày giảm bớt của tập dữ liệu có dung lượng nhỏ hơn nhiều, nhưng vẫn duy trì chặt chẽ tính toàn vẹn của dữ liệu gốc. Nghĩa là, việc khai thác trên tập dữ liệu đã rút gọn sẽ hiệu quả hơn nhưng tạo ra các kết quả phân tích giống nhau (hoặc gần như giống nhau). Trong phần này, trước tiên chúng tôi trình bày tổng quan về các chiến lược giảm thiểu dữ liệu, tiếp theo là xem xét kỹ hơn các kỹ thuật riêng lẻ.

Tổng quan về chiến lược giảm dữ liệu

Các chiến lược giảm dữ liệu bao gồm giảm kích thước, giảm số lượng và nén dữ liệu.

Giảm thứ nguyên là quá trình giảm số lượng các biến hoặc thuộc tính ngẫu nhiên đang được xem xét. Các phương pháp giảm kích thước bao gồm biến đổi wavelet và phân tích các thành phần chính, biến đổi hoặc chiếu dữ liệu gốc lên một không gian nhỏ hơn. Lựa chọn tập con thuộc tính là một phương pháp giảm kích thước trong đó các thuộc tính hoặc thứ nguyên không liên quan, có liên quan yếu hoặc dư thừa được phát hiện và loại bỏ.

Kỹ thuật giảm số lượng thay thế khối lượng dữ liệu ban đầu bằng các hình thức biểu diễn dữ liệu thay thế, nhỏ hơn. Các kỹ thuật này có thể là tham số hoặc phi tham số. Đối với các phương pháp tham số, một mô hình được sử dụng để ước tính dữ liệu, do đó thường chỉ các tham số dữ liệu cần được lưu trữ, thay vì dữ liệu thực tế. (Ngoài ra cũng có thể được lưu trữ.) Các mô hình hồi quy và log-tuyến tính là các ví dụ. Các phương pháp phi tham số để lưu trữ các đại diện đã giảm của dữ liệu bao gồm tổng thể, phân cụm, lấy mẫu và tổng hợp khối dữ liệu.

Trong quá trình nén dữ liệu, các phép biến đổi được áp dụng để thu được phần biểu diễn thu nhỏ hoặc “tổng hợp” của dữ liệu gốc. Nếu dữ liệu gốc có thể được tái tạo từ dữ liệu nén mà không bị mất thông tin, thì việc giảm dữ liệu được gọi là mất dữ liệu. Thay vào đó, nếu chúng ta chỉ có thể tạo lại một phần gần đúng của dữ liệu ban đầu, thì việc giảm dữ liệu được gọi là mất mát. Có một số thuật toán không mất dữ liệu cho kết hợp chuỗi; tuy nhiên, chúng thường chỉ cho phép thao tác dữ liệu hạn chế. Các kỹ thuật giảm kích thước và giảm số lượng cũng có thể được coi là các hình thức nén dữ liệu.

Có nhiều cách khác để tổ chức các phương pháp giảm thiểu dữ liệu. Thời gian tương ứng dành cho việc giảm dữ liệu không được lớn hơn hoặc “xóa” đi thời gian được tiết kiệm bằng cách khai thác trên kích thước tập dữ liệu giảm.

Biến đổi Wavelet

Phép biến đổi wavelet rời rạc (DWT) là một kỹ thuật xử lý tín hiệu tuyến tính, khi được áp dụng cho vectơ dữ liệu X, biến đổi nó thành một vectơ khác về số, X_r, của các hệ số wavelet. Hai vectơ có cùng độ dài. Khi áp dụng công nghệ này để giảm dữ liệu, chúng tôi coi mỗi bộ như một vectơ dữ liệu n chiều, nghĩa là, X (x₁, x₂,.., X_n), mô tả n phép đo được thực hiện trên bộ từ n thuộc tính cơ sở dữ liệu.

“Làm thế nào kỹ thuật này có thể hữu ích cho việc giảm dữ liệu nếu dữ liệu được biến đổi wavelet có cùng độ dài với dữ liệu ban đầu?” Tính hữu ích nằm ở chỗ dữ liệu được chuyển đổi wavelet có thể được cắt bớt. Dữ liệu gần đúng đã nén có thể được giữ lại bằng cách chỉ lưu trữ một phần nhỏ của hệ số wavelet mạnh nhất. Ví dụ: tất cả các hệ số wavelet lớn hơn một số ngưỡng do người dùng chỉ định có thể được giữ lại. Tất cả các hệ số khác được đặt thành 0. Do đó, việc biểu diễn dữ liệu kết quả rất thưa thớt, do đó các hoạt động có thể tận dụng sự thưa thớt dữ liệu tương tự rất nhanh nếu được thực hiện trong không gian wavelet. Kỹ thuật này cũng hoạt động để loại bỏ nhiễu mà không làm mịn các tính năng chính của dữ liệu, tạo hiệu quả cho dữ liệu.

Trong ký hiệu của chúng tôi, bất kỳ biến nào đại diện cho một vectơ được hiển thị bằng phông chữ in nghiêng đậm; các phép đo mô tả vectơ cũng được hiển thị bằng cách làm sạch phông chữ nghiêng. Với một tập hợp các hệ số, một số liệu gần đúng của dữ liệu ban đầu có thể được xây dựng bằng cách áp dụng nghịch đảo của DWT được sử dụng.

DWT có liên quan chặt chẽ với phép biến đổi Fourier rời rạc (DFT), một kỹ thuật xử lý tín hiệu liên quan đến sin và cosin. Tuy nhiên, nói chung, DWT đạt được khả năng nén tổn hao tốt hơn. Có nghĩa là, nếu cùng một số hệ số được giữ lại cho một DWT và một DFT của một vectơ dữ liệu nhất định, thì phiên bản DWT sẽ cung cấp một giá trị gần đúng chính xác hơn của dữ liệu gốc. Do đó, đối với một giá trị gần đúng tương đương, DWT yêu cầu ít không gian hơn DFT. Không giống như DFT, wavelet khá bản địa hóa trong không gian, góp phần bảo tồn chi tiết cục bộ.

Chỉ có một DFT, nhưng có một số họ DWT. Quy trình chung để áp dụng phép biến đổi wavelet rời rạc sử dụng thuật toán kim tự tháp phân cấp làm giảm một nửa dữ liệu ở mỗi lần lặp, dẫn đến tốc độ tính toán nhanh. Phương pháp như sau:

• Độ dài, L, của vectơ dữ liệu đầu vào phải là lũy thừa số nguyên của 2. Điều kiện này có thể được đáp ứng bằng cách đệm vectơ dữ liệu bằng các số không khi cần thiết (L ≥ n).
• Mỗi phép biến đổi liên quan đến việc áp dụng hai hàm. Cách đầu tiên áp dụng một số dữ liệu mượt mà, chẳng hạn như tổng hoặc trung bình có trọng số. Thứ hai thực hiện sự khác biệt có trọng số, hoạt động để làm nổi bật các tính năng chi tiết của dữ liệu.
• Hai hàm được áp dụng cho các cặp điểm dữ liệu trong X, nghĩa là cho tất cả các cặp số đo (x_2i, x_{2i + 1}). Điều này dẫn đến hai tập dữ liệu có độ dài L / 2. Nói chung, chúng đại diện cho phiên bản tần số thấp hoặc mịn của dữ liệu đầu vào và nội dung tần số cao của nó, tương ứng.
• Hai hàm được áp dụng đệ quy cho các tập dữ liệu thu được trong vòng lặp trước đó, cho đến khi các tập dữ liệu kết quả thu được có độ dài 2.
• Các giá trị được chọn từ các tập dữ liệu thu được trong các lần lặp trước đó được chỉ định là hệ số wavelet của dữ liệu được biến đổi.

Ví dụ về họ wavelet. Số bên cạnh tên wavelet là số khoảnh khắc biến mất của wavelet. Đây là một tập hợp các mối quan hệ toán học mà các hệ số phải thỏa mãn và có liên quan đến số lượng các hệ số.

Tương tự, một phép nhân ma trận có thể được áp dụng cho dữ liệu đầu vào để thu được các hệ số wavelet, trong đó ma trận được sử dụng phụ thuộc vào DWT đã cho. Ma trận phải là trực chuẩn, có nghĩa là các cột là vectơ đơn vị và là trực giao lẫn nhau, do đó nghịch đảo của ma trận chỉ là chuyển vị của nó. Mặc dù chúng ta không có chỗ để thảo luận ở đây, nhưng thuộc tính này cho phép xây dựng lại dữ liệu từ các tập dữ liệu khác biệt trơn tru và mượt mà. Bằng cách tính toán ma trận được sử dụng thành tích của một vài ma trận thưa thớt, kết quả là thuật toán “DWT nhanh” có độ phức tạp là O (n) đối với vectơ đầu vào có độ dài n.

Các phép biến đổi Wavelet có thể được áp dụng cho dữ liệu đa chiều như một khối dữ liệu. Điều này được thực hiện trước tiên bằng cách áp dụng phép biến đổi cho chiều thứ nhất, sau đó đến chiều thứ hai, v.v. Độ phức tạp tính toán liên quan là tuyến tính đối với số ô trong khối lập phương. Các phép biến đổi Wavelet cho kết quả tốt trên dữ liệu thưa thớt hoặc lệch và trên dữ liệu có các thuộc tính có thứ tự. Nén mất dữ liệu bằng wavelet được cho là tốt hơn so với nén JPEG, tiêu chuẩn thương mại hiện tại. Các phép biến đổi Wavelet có nhiều ứng dụng trong thế giới thực, bao gồm nén hình ảnh dấu vân tay, thị giác máy tính, phân tích dữ liệu chuỗi thời gian và làm sạch dữ liệu.

Phân tích các thành phần chính

Trong tiểu mục này, chúng tôi cung cấp một giới thiệu trực quan về phân tích các thành phần chính như một phương pháp giảm thiểu số lượng. Phần giải thích lý thuyết chi tiết nằm ngoài phạm vi của cuốn sách này. Để có thêm tài liệu tham khảo, vui lòng xem ghi chú thư mục (Phần 3.8) ở cuối chương này.

Giả sử rằng dữ liệu được giảm bớt bao gồm các bộ giá trị hoặc vectơ dữ liệu được mô tả bởi n thuộc tính hoặc thứ nguyên. Phân tích các thành phần chính (PCA; còn được gọi là phương pháp Karhunen-Loeve, hoặc K-L,) tìm kiếm k vectơ trực giao n-chiều có thể được sử dụng tốt nhất để biểu diễn dữ liệu, trong đó k n. Do đó, dữ liệu ban đầu được chiếu vào một không gian nhỏ hơn nhiều, dẫn đến giảm kích thước. Không giống như lựa chọn tập hợp con thuộc tính (Phần 3.4.4), làm giảm kích thước tập thuộc tính bằng cách giữ lại một tập con của tập thuộc tính ban đầu, PCA “kết hợp” bản chất của các thuộc tính bằng cách tạo một tập hợp các biến thay thế, nhỏ hơn. Dữ liệu ban đầu sau đó có thể được chiếu vào tập hợp nhỏ hơn này. PCA thường tiết lộ các mối quan hệ mà trước đây không bị nghi ngờ và do đó cho phép các diễn giải mà thông thường sẽ không dẫn đến kết quả.

Quy trình cơ bản như sau:

• Dữ liệu đầu vào được chuẩn hóa để mỗi thuộc tính nằm trong cùng một phạm vi. Bước này giúp đảm bảo rằng các thuộc tính có miền lớn sẽ không lấn át các thuộc tính có miền nhỏ hơn.
• PCA tính k vectơ trực chuẩn cung cấp cơ sở cho dữ liệu đầu vào chuẩn hóa. Đây là các vectơ đơn vị mà mỗi điểm theo phương vuông góc với các vectơ khác. Các vectơ này được gọi là các thành phần chính. Dữ liệu đầu vào là sự kết hợp tuyến tính của các thành phần chính.
• Các thành phần chính được sắp xếp theo thứ tự giảm dần “ý nghĩa” hoặc sức mạnh. Các thành phần chính về cơ bản đóng vai trò như một tập hợp các trục mới cho dữ liệu, cung cấp thông tin quan trọng về phương sai. Nghĩa là, các trục được sắp xếp sao cho trục đầu tiên hiển thị phương sai nhiều nhất trong số dữ liệu, trục thứ hai hiển thị phương sai cao nhất tiếp theo, v.v. Ví dụ, Hình 3.5 cho thấy hai thành phần cơ bản đầu tiên, Y1 và Y2, cho tập dữ liệu đã cho ban đầu được ánh xạ tới các trục X1 và X2. Thông tin này giúp xác định các nhóm hoặc mẫu trong dữ liệu.

Phân tích thành phần chính. Y₁ và Y₂ là hai thành phần chính đầu tiên cho dữ liệu đã cho.

• Bởi vì các thành phần được sắp xếp theo thứ tự giảm dần về “mức độ quan trọng”, kích thước dữ liệu có thể được giảm xuống bằng cách loại bỏ các thành phần yếu hơn, tức là những thành phần có mức chênh lệch thấp. Sử dụng các thành phần chính mạnh nhất, có thể tạo lại một số liệu gần đúng tốt của dữ liệu gốc.

PCA có thể được áp dụng cho các thuộc tính có thứ tự và không có thứ tự, đồng thời có thể xử lý dữ liệu thưa thớt và dữ liệu lệch. Dữ liệu đa chiều của nhiều hơn hai chiều có thể được xử lý bằng cách giảm vấn đề thành hai chiều. Các thành phần chính có thể được sử dụng làm đầu vào cho nhiều hồi quy và phân tích cụm. So với các dạng biến đổi wavelet, PCA có xu hướng xử lý dữ liệu thưa thớt tốt hơn, trong khi các phép biến đổi wavelet phù hợp hơn với dữ liệu có kích thước lớn.

Lựa chọn tập con thuộc tính

Các tập dữ liệu để phân tích có thể chứa hàng trăm thuộc tính, nhiều thuộc tính trong số đó có thể không phù hợp với nhiệm vụ khai thác hoặc dư thừa. Ví dụ: nếu nhiệm vụ là phân loại khách hàng dựa trên việc họ có khả năng mua một đĩa CD mới phổ biến tại AllElectronics hay không khi được thông báo về một đợt giảm giá, thì các thuộc tính như số điện thoại của khách hàng có thể không liên quan, không giống như các thuộc tính như tuổi hoặc gu âm nhạc. Mặc dù chuyên gia miền có thể chọn ra một số thuộc tính hữu ích, nhưng đây có thể là một nhiệm vụ khó khăn và tốn thời gian, đặc biệt là khi hành vi của dữ liệu không được biết rõ. (Do đó, một lý do đằng sau phân tích của nó!) Bỏ qua các thuộc tính có liên quan hoặc giữ các thuộc tính không liên quan có thể gây bất lợi, gây nhầm lẫn cho thuật toán khai thác được sử dụng. Điều này có thể dẫn đến việc phát hiện ra các mẫu có chất lượng kém. Ngoài ra, khối lượng bổ sung của các thuộc tính không liên quan hoặc dư thừa có thể làm chậm quá trình khai thác.

Lựa chọn tập hợp con thuộc tính làm giảm kích thước tập dữ liệu bằng cách loại bỏ các thuộc tính (hoặc thứ nguyên) không liên quan hoặc dư thừa. Mục tiêu của lựa chọn tập hợp con thuộc tính là tìm một tập hợp tối thiểu các thuộc tính sao cho phân phối xác suất kết quả của các lớp dữ liệu càng gần càng tốt với phân phối ban đầu thu được bằng cách sử dụng tất cả các thuộc tính. Khai thác trên một nhóm thuộc tính giảm có một lợi ích bổ sung: Nó làm giảm số lượng thuộc tính xuất hiện trong các mẫu được phát hiện, giúp làm cho các mẫu dễ hiểu hơn.

“Làm cách nào để chúng tôi có thể tìm thấy một tập hợp con‘ tốt ’của các thuộc tính ban đầu?” Đối với n thuộc tính, có thể có 2n tập hợp con. Việc tìm kiếm toàn diện cho tập con tối ưu của các thuộc tính có thể rất tốn kém, đặc biệt là khi n và số lượng các lớp dữ liệu tăng lên. Do đó, các phương pháp heuristic khám phá không gian tìm kiếm thu gọn thường được sử dụng để lựa chọn tập con thuộc tính. Các phương thức này thường tham lam ở chỗ, trong khi tìm kiếm trong không gian thuộc tính, chúng luôn làm cho những gì có vẻ là lựa chọn tốt nhất tại thời điểm đó. Chiến lược của họ là đưa ra một lựa chọn tối ưu cục bộ với hy vọng rằng điều này sẽ dẫn đến một giải pháp tối ưu trên toàn cầu. Các phương pháp tham lam như vậy có hiệu quả trong thực tế và có thể gần ước tính một giải pháp tối ưu.

Các thuộc tính “tốt nhất” (và “kém nhất”) thường được xác định bằng cách sử dụng các thử nghiệm có ý nghĩa thống kê, giả định rằng các thuộc tính độc lập với nhau. Nhiều biện pháp đánh giá thuộc tính khác có thể được sử dụng như thước đo thu thập thông tin được sử dụng trong việc xây dựng cây quyết định để phân loại.

Phương thức tham lam (heuristic) để lựa chọn tập hợp con thuộc tính

• Lựa chọn chuyển tiếp theo từng bước: Quy trình bắt đầu với một tập hợp rỗng các thuộc tính là tập hợp giảm. Các thuộc tính ban đầu tốt nhất được xác định và thêm vào tập hợp đã rút gọn. Ở mỗi bước hoặc lần lặp tiếp theo, các thuộc tính gốc tốt nhất còn lại sẽ được thêm vào tập hợp.
• Loại bỏ ngược từng bước: Quy trình bắt đầu với tập hợp đầy đủ các thuộc tính. Ở mỗi bước, nó loại bỏ thuộc tính xấu nhất còn lại trong tập hợp.
• Kết hợp lựa chọn tiến và loại bỏ lùi: Phương pháp chọn lọc lùi từng bước và chọn lọc lùi có thể được kết hợp để ở mỗi bước, thủ tục chọn thuộc tính tốt nhất và loại bỏ thuộc tính xấu nhất trong số các thuộc tính còn lại.
• Quy nạp cây quyết định: Các thuật toán cây quyết định (ví dụ: ID3, C4.5 và CART) ban đầu được dùng để phân loại. Quy nạp cây quyết định xây dựng một cấu trúc giống như lưu đồ trong đó mỗi nút bên trong (không phải trang chính) biểu thị một bài kiểm tra trên một thuộc tính, mỗi nhánh tương ứng với một kết quả của bài kiểm tra và mỗi nút bên ngoài (lá) biểu thị một dự đoán lớp. Tại mỗi nút, thuật toán chọn thuộc tính “tốt nhất” để phân vùng dữ liệu thành các lớp riêng lẻ.

Khi quy nạp cây quyết định được sử dụng để lựa chọn tập hợp con thuộc tính, cây sẽ được cấu trúc từ dữ liệu đã cho. Tất cả các thuộc tính không xuất hiện trong cây được coi là không liên quan. Tập hợp các thuộc tính xuất hiện trong cây tạo thành tập hợp con rút gọn của các thuộc tính.

Các tiêu chí dừng cho các phương pháp có thể khác nhau. Quy trình có thể sử dụng một ngưỡng trên thước đo được sử dụng để xác định thời điểm dừng quá trình lựa chọn thuộc tính.

Trong một số trường hợp, chúng tôi có thể muốn tạo các thuộc tính mới dựa trên các thuộc tính khác. Cấu trúc thuộc tính6 như vậy có thể giúp cải thiện độ chính xác và hiểu biết về cấu trúc trong dữ liệu chiều cao. Ví dụ: chúng ta có thể muốn thêm vùng thuộc tính dựa trên chiều cao và chiều rộng của thuộc tính. Bằng cách kết hợp các thuộc tính, cấu trúc thuộc tính có thể loại bỏ thông tin còn thiếu về mối quan hệ giữa các thuộc tính dữ liệu có thể hữu ích cho việc khám phá kiến thức.

Mô hình hồi quy và log-tuyến tính: Giảm dữ liệu tham số

Các mô hình hồi quy và log-tuyến tính có thể được sử dụng để tính gần đúng dữ liệu đã cho. Trong hồi quy tuyến tính (đơn giản), dữ liệu được mô hình hóa để vừa với một đường thẳng. Ví dụ, một biến ngẫu nhiên, y (được gọi là biến phản hồi), có thể được mô hình hóa dưới dạng hàm tuyến tính của một biến ngẫu nhiên khác, x (được gọi là biến dự đoán), với phương trình:

y = wx + b

trong đó phương sai của y được giả định là không đổi. Trong bối cảnh khai thác dữ liệu, x và y là các thuộc tính cơ sở dữ liệu số. Các hệ số, w và b (được gọi là hệ số hồi quy), xác định độ dốc của đường thẳng và giao điểm y, tương ứng. Các hệ số này có thể được giải bằng phương pháp bình phương nhỏ nhất, phương pháp này giảm thiểu sai số giữa dòng thực tế phân tách dữ liệu và ước lượng của dòng. Hồi quy nhiều tuyến tính là một phần mở rộng của hồi quy tuyến tính (đơn giản), cho phép một biến phản hồi, y, được mô hình hóa dưới dạng một hàm tuyến tính của hai hoặc nhiều biến dự báo.

Mô hình tuyến tính lôgic gần đúng với các phân phối xác suất đa chiều rời rạc. Cho một tập hợp các bộ giá trị n chiều (ví dụ: được mô tả bởi n thuộc tính), chúng ta có thể coi mỗi bộ giá trị là một điểm trong không gian n chiều. Mô hình tuyến tính log có thể được sử dụng để ước tính xác suất của mỗi điểm trong không gian đa chiều đối với một tập hợp các thuộc tính được phân loại, dựa trên một tập hợp con nhỏ hơn của các kết hợp chiều. Điều này cho phép không gian dữ liệu có chiều cao hơn được xây dựng từ không gian có chiều thấp hơn. Do đó, mô hình tuyến tính log cũng hữu ích cho việc giảm kích thước (vì các điểm có chiều thấp hơn cùng nhau thường chiếm ít không gian hơn các điểm dữ liệu ban đầu) và làm mịn dữ liệu (vì các ước tính tổng hợp trong không gian chiều thấp hơn ít phải chịu các biến thể lấy mẫu hơn ước tính trong không gian chiều cao hơn).

Cả hai mô hình hồi quy và log-tuyến tính đều có thể được sử dụng trên dữ liệu thưa thớt, mặc dù ứng dụng của chúng có thể bị hạn chế. Mặc dù cả hai phương pháp đều có thể xử lý dữ liệu sai lệch, nhưng hồi quy hoạt động rất tốt. Hồi quy có thể chuyên sâu về mặt tính toán khi áp dụng cho dữ liệu chiều cao, trong khi mô hình log-tuyến tính cho thấy khả năng mở rộng tốt cho tối đa 10 thứ nguyên hoặc lâu hơn.

Một số gói phần mềm tồn tại để giải quyết các vấn đề hồi quy. Ví dụ bao gồm SAS (www.sas.com), SPSS (www.spss.com) và S-Plus (www.insightful.com). Một tài nguyên hữu ích khác là cuốn sáchNumerical Recipes in C, của Press, Teukolsky, Vetterling và Flannery, và mã nguồn liên quan của nó.

Biểu đồ

Biểu đồ sử dụng binning để phân phối dữ liệu gần đúng và là một hình thức giảm dữ liệu phổ biến. Biểu đồ đã được giới thiệu trong Phần 2.2.3. Biểu đồ cho một thuộc tính, A, phân vùng phân phối dữ liệu của A thành các tập con rời rạc, được gọi là nhóm hoặc thùng. Nếu mỗi nhóm chỉ đại diện cho một cặp thuộc tính-giá trị / tần suất duy nhất, các nhóm được gọi là nhóm singleton. Thông thường, các nhóm thay vào đó đại diện cho các phạm vi liên tục cho thuộc tính đã cho.

Ví dụ: Biểu đồ. Dữ liệu sau đây là danh sách giá AllElectronics cho các mặt hàng thường được bán (làm tròn đến đô la gần nhất). Các số đã được sắp xếp: 1, 1, 5, 5, 5, 5, 5, 8, 8, 10, 10, 10, 10, 12, 14, 14, 14, 15, 15, 15, 15, 15, 15, 18, 18, 18, 18, 18, 18, 18, 18, 20, 20, 20, 20, 20, 20, 20, 21, 21, 21, 21, 25, 25, 25, 25, 25, 28, 28, 30, 30, 30.

Hình dưới đây cho thấy một biểu đồ cho dữ liệu bằng cách sử dụng các nhóm singleton. Để giảm thêm dữ liệu, thông thường mỗi nhóm biểu thị một phạm vi giá trị liên tục cho thuộc tính đã cho. Trong Hình 3.8, mỗi nhóm đại diện cho một phạm vi giá $10 khác nhau.

Biểu đồ về giá sử dụng nhóm singleton — mỗi nhóm đại diện cho một cặp giá – giá trị / tần suất.

Biểu đồ có hiệu quả cao trong việc ước tính cả dữ liệu thưa thớt và dày đặc, cũng như dữ liệu có độ lệch cao và đồng nhất. Các biểu đồ được mô tả trước đây cho các thuộc tính đơn lẻ có thể được mở rộng cho nhiều thuộc tính. Biểu đồ đa chiều có thể xác định sự phụ thuộc giữa các thuộc tính. Các biểu đồ này đã được phát hiện có hiệu quả trong việc ước tính dữ liệu với tối đa năm thuộc tính. Cần có nhiều nghiên cứu hơn về hiệu quả của biểu đồ đa chiều đối với các chiều cao.

Singleton rất hữu ích để lưu trữ các giá trị ngoại lai tần số cao.

Phân cụm

Kỹ thuật phân cụm coi các bộ dữ liệu là các đối tượng. Chúng phân vùng các đối tượng thành các nhóm hoặc cụm, để các đối tượng trong một cụm là “tương tự” với nhau và “tương tự” với các đối tượng trong các cụm khác. Sự giống nhau thường được định nghĩa về mức độ “gần” của các đối tượng trong không gian, dựa trên một hàm khoảng cách. “Chất lượng” của một cụm có thể được biểu thị bằng đường kính của nó, khoảng cách tối đa giữa hai đối tượng bất kỳ trong cụm. Khoảng cách trung tâm là một thước đo thay thế cho chất lượng cụm và được định nghĩa là khoảng cách trung bình của mỗi đối tượng cụm từ trung tâm cụm (biểu thị “đối tượng trung bình” hoặc điểm trung bình trong không gian cho cụm). 

Trong giảm dữ liệu, các đại diện cụm của dữ liệu được sử dụng để thay thế dữ liệu thực tế. Hiệu quả của kỹ thuật này phụ thuộc vào bản chất của dữ liệu. Nó hiệu quả hơn nhiều đối với dữ liệu có thể được tổ chức thành các cụm riêng biệt hơn là đối với dữ liệu bị bôi nhọ.

Có nhiều biện pháp để xác định cụm và chất lượng cụm.

Lấy mẫu

Lấy mẫu có thể được sử dụng như một kỹ thuật giảm dữ liệu vì nó cho phép một tập dữ liệu lớn được biểu diễn bằng một mẫu dữ liệu ngẫu nhiên nhỏ hơn nhiều (hoặc tập con). Giả sử rằng một tập dữ liệu lớn, D, chứa N bộ giá trị. Hãy xem xét các cách phổ biến nhất mà chúng ta có thể lấy mẫu D để giảm dữ liệu.

• Mẫu ngẫu nhiên đơn giản không có thay thế (SRSWOR) có kích thước s: Mẫu này được tạo ra bằng cách vẽ s trong số N bộ từ D (s <N), trong đó xác suất để vẽ bất kỳ bộ nào trong D là 1 / N, nghĩa là, tất cả các bộ đều là có khả năng được lấy mẫu như nhau.
• Mẫu ngẫu nhiên đơn giản có thay thế (SRSWR) có kích thước s: Điều này tương tự như SRSWOR, ngoại trừ mỗi lần một bộ được rút ra từ D, nó được ghi lại và sau đó được thay thế. Có nghĩa là, sau khi một tuple được rút ra, nó được đặt trở lại D để nó có thể được vẽ lại.
• Mẫu cụm: Nếu các bộ giá trị trong D được nhóm thành M “cụm” rời rạc lẫn nhau thì có thể thu được SRS của các cụm s, trong đó s <M. Ví dụ, các bộ giá trị trong cơ sở dữ liệu thường được truy xuất một trang tại một thời điểm, vì vậy rằng mỗi trang có thể được coi là một cụm. Biểu diễn dữ liệu giảm có thể thu được bằng cách áp dụng SRSWOR cho các trang, dẫn đến một mẫu cụm của các bộ giá trị. Các tiêu chí phân nhóm khác bao gồm ngữ nghĩa phong phú cũng có thể được khám phá. Ví dụ, trong cơ sở dữ liệu không gian, chúng tôi có thể chọn xác định các cụm về mặt địa lý dựa trên mức độ gần nhau của các khu vực khác nhau.
• Mẫu phân tầng: Nếu D được chia thành các phần rời rạc lẫn nhau được gọi là địa tầng, thì một mẫu phân tầng của D được tạo ra bằng cách thu được SRS ở mỗi tầng. Điều này giúp đảm bảo mẫu đại diện, đặc biệt khi dữ liệu bị lệch. Ví dụ, một mẫu phân tầng có thể được lấy từ dữ liệu khách hàng, trong đó phân tầng được tạo cho từng nhóm tuổi khác nhau. Bằng cách này, nhóm tuổi có số lượng khách hàng nhỏ nhất sẽ chắc chắn được đại diện.

Một ưu điểm của việc lấy mẫu để giảm dữ liệu là chi phí lấy mẫu tỷ lệ với kích thước của mẫu, s, trái ngược với N, kích thước tập dữ liệu. Do đó, độ phức tạp của việc lấy mẫu có khả năng ảnh hưởng đến kích thước của dữ liệu. Các kỹ thuật rút gọn dữ liệu khác có thể yêu cầu ít nhất một lần chuyển hoàn toàn qua D. Đối với kích thước mẫu cố định, độ phức tạp của việc lấy mẫu chỉ tăng tuyến tính khi số thứ nguyên dữ liệu, n, tăng lên, trong khi các kỹ thuật sử dụng biểu đồ, chẳng hạn, tăng theo cấp số nhân ở n.

Khi được áp dụng để giảm dữ liệu, lấy mẫu thường được sử dụng nhất để ước tính câu trả lời cho một truy vấn tổng hợp. Có thể (sử dụng định lý giới hạn trung tâm) để xác định cỡ mẫu đủ để ước lượng một hàm đã cho trong một mức độ sai số xác định. Kích thước mẫu này, s, có thể cực kỳ nhỏ so với N. Lấy mẫu là một lựa chọn tự nhiên để cải tiến dần tập hợp dữ liệu đã giảm. Một tập hợp như vậy có thể được tinh chỉnh thêm bằng cách tăng kích thước mẫu.

Tổng hợp khối dữ liệu

Hãy tưởng tượng rằng bạn đã thu thập dữ liệu để phân tích. Những dữ liệu này bao gồm doanh số bán hàng của AllElectronics mỗi quý, trong các năm 2008 đến 2010. Tuy nhiên, bạn quan tâm đến doanh số hàng năm (tổng mỗi năm), hơn là tổng mỗi quý. Do đó, dữ liệu có thể được tổng hợp để dữ liệu kết quả tóm tắt tổng doanh số bán hàng mỗi năm thay vì mỗi quý. Sự tổng hợp này được minh họa trong Hình 25. Tập dữ liệu kết quả có khối lượng nhỏ hơn, không làm mất thông tin cần thiết cho nhiệm vụ phân tích.

Các khối dữ liệu được thảo luận chi tiết trong Chương truowccs về kho dữ liệu và công nghệ khối dữ liệu. Chúng tôi giới thiệu ngắn gọn một số khái niệm ở đây. Các khối dữ liệu lưu trữ thông tin tổng hợp đa chiều. Ví dụ, Hình 26  cho thấy một khối dữ liệu để phân tích đa chiều dữ liệu bán hàng liên quan đến doanh số hàng năm trên mỗi loại mặt hàng cho mỗi chi nhánh của AllElectronics. Mỗi ô chứa một giá trị dữ liệu tổng hợp, tương ứng với điểm dữ liệu trong không gian đa chiều. (Để dễ đọc, chỉ một số giá trị ô được hiển thị.) Phân cấp khái niệm có thể tồn tại cho mỗi thuộc tính, cho phép phân tích dữ liệu ở nhiều mức trừu tượng. Ví dụ, một hệ thống phân cấp cho chi nhánh có thể cho phép các chi nhánh được nhóm thành các vùng, dựa trên địa chỉ của chúng. Các khối dữ liệu cung cấp khả năng truy cập nhanh vào dữ liệu tóm tắt, được tính toán trước, do đó mang lại lợi ích cho quá trình xử lý phân tích trực tuyến cũng như khai thác dữ liệu.

Dữ liệu bán hàng cho một nhánh nhất định của AllElectronics trong các năm từ 2008 đến 2010. Ở bên trái, doanh số bán hàng được hiển thị theo quý. Ở bên phải, dữ liệu được tổng hợp để cung cấp doanh số hàng năm.

Một khối dữ liệu để bán hàng tại AllElectronics.

Hình khối được tạo ra ở mức trừu tượng thấp nhất được gọi là hình khối cơ sở. Hình khối cơ sở phải tương ứng với một thực thể quan tâm như doanh số bán hàng hoặc thương hiệu. Nói cách khác, mức thấp nhất phải có thể sử dụng được hoặc hữu ích cho việc phân tích. Hình lập phương ở mức trừu tượng cao nhất là hình lập phương đỉnh. Đối với dữ liệu bán hàng trong Hình 26, khối chóp sẽ cho một tổng số tổng doanh số bán hàng trong cả ba năm, cho tất cả các loại mặt hàng và cho tất cả các chi nhánh. Các khối dữ liệu được tạo cho các mức độ trừu tượng khác nhau thường được gọi là khối lập phương, do đó khối dữ liệu có thể đề cập đến một mạng các khối lập phương thay thế. Mỗi mức trừu tượng cao hơn sẽ làm giảm thêm kích thước dữ liệu kết quả. Khi trả lời các yêu cầu khai thác dữ liệu, nên sử dụng khối lập phương nhỏ nhất có liên quan đến nhiệm vụ đã cho. Vấn đề này cũng được đề cập trong Chương 4.