Biểu diễn dữ liệu cho khai phá dữ liệu chuỗi thời gian: Phương pháp tiếp cận miền thời gian

Chia sẻ: Nguathienthan2 Nguathienthan2 | Ngày: | Loại File: PDF | Số trang:8

Thêm vào BST

Báo xấu

1
lượt xem 0
download

Biểu diễn dữ liệu cho khai phá dữ liệu chuỗi thời gian: Phương pháp tiếp cận miền thời gian

Mô tả tài liệu

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Trong hầu hết khai phá dữ liệu chuỗi thời gian, cần yêu cầu nhiều hình thức khác nhau cho việc biểu diễn dữ liệu hoặc xử lý dữ liệu vì những đặc tính độc đáo của chuỗi thời gian, ví dụ như nhiều chiều (số lượng điểm dữ liệu), sự xuất hiện của nhiễu ngẫu nhiên và mối quan hệ phi tuyến tính của các phần tử dữ liệu. Do đó, bất kỳ phương pháp biểu diễn dữ liệu nào cũng đều nhằm mục đích giảm đáng kể dữ liệu đến một kích thước có thể quản lý, đồng thời vẫn giữ được các đặc tính quan trọng của dữ liệu ban đầu và sức mạnh với nhiễu ngẫu nhiên. Hơn nữa, việc lựa chọn phương pháp biểu diễn dữ liệu phù hợp có thể dẫn đến khai phá dữ liệu có ý nghĩa. Nhiều phương pháp biểu diễn cấp cao của dữ liệu theo chuỗi thời gian được dựa trên phương pháp tiếp cận miền thời gian. Các phương pháp này xử lý trực tiếp dữ liệu ban đầu trong miền thời gian và hiểu được bản chất của dữ liệu theo thời gian. Phương pháp này dựa trên một số ý tưởng chính của phương pháp xấp xỉ từng đoạn, biểu diễn dữ liệu bằng cách xác định các điểm quan trọng, và biểu diễn ký hiệu hóa đã được sử dụng rộng rãi trong các lĩnh vực khác nhau.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Biểu diễn dữ liệu cho khai phá dữ liệu chuỗi thời gian: Phương pháp tiếp cận miền thời gian

Biểu diễn dữ liệu… Thống kê Quốc tế và Hội nhập BIỂU DIỄN DỮ LIỆU KHAI PHÁ DỮ LIỆU CHUỖI THỜI GIAN: PHƯƠNG PHÁP TIẾP CẬN MIỀN THỜI GIAN Seunghye J. Wilson, Phòng Thống kê, Đại học George Mason, Mỹ Tóm tắt: Trong hầu hết khai phá dữ liệu chuỗi thời gian, cần yêu cầu nhiều hình thức khác nhau cho việc biểu diễn dữ liệu hoặc xử lý dữ liệu vì những đặc tính độc đáo của chuỗi thời gian, ví dụ như nhiều chiều (số lượng điểm dữ liệu), sự xuất hiện của nhiễu ngẫu nhiên và mối quan hệ phi tuyến tính của các phần tử dữ liệu. Do đó, bất kỳ phương pháp biểu diễn dữ liệu nào cũng đều nhằm mục đích giảm đáng kể dữ liệu đến một kích thước có thể quản lý, đồng thời vẫn giữ được các đặc tính quan trọng của dữ liệu ban đầu và sức mạnh với nhiễu ngẫu nhiên. Hơn nữa, việc lựa chọn phương pháp biểu diễn dữ liệu phù hợp có thể dẫn đến khai phá dữ liệu có ý nghĩa. Nhiều phương pháp biểu diễn cấp cao của dữ liệu theo chuỗi thời gian được dựa trên phương pháp tiếp cận miền thời gian. Các phương pháp này xử lý trực tiếp dữ liệu ban đầu trong miền thời gian và hiểu được bản chất của dữ liệu theo thời gian. Phương pháp này dựa trên một số ý tưởng chính của phương pháp xấp xỉ từng đoạn, biểu diễn dữ liệu bằng cách xác định các điểm quan trọng, và biểu diễn ký hiệu hóa đã được sử dụng rộng rãi trong các lĩnh vực khác nhau. Từ khoá: Khai phá dữ liệu chuỗi thời gian, xử lý dữ liệu, giảm dữ liệu, biểu diễn dữ liệu cấp cao, phương pháp tiếp cận miền thời gian. 1. Giới thiệu thước có thể quản lý hoặc xấp xỉ dữ liệu bằng cách loại bỏ nhiễu ngẫu nhiên. Tuy nhiên, dữ Chuỗi thời gian là một dạng dữ liệu liệu bị giảm đi phải bảo toàn các tính năng quan trọng trong các lĩnh vực khác nhau của quan trọng của toàn bộ dữ liệu ban đầu. ngành công nghiệp và nghiên cứu. Trong những thập kỷ gần đây, việc khai phá dữ liệu Phương pháp tiếp cận miền thời gian theo chuỗi thời gian đã được quan tâm và để biểu diễn dữ liệu đặc biệt hữu ích để hiểu phát triển bùng nổ. Tuy nhiên, thật khó để được bản chất của dữ liệu theo thời gian. áp dụng kỹ thuật khai phá để lấy dữ liệu trực Chúng tóm tắt dữ liệu ban đầu bằng cách tiếp vì những đặc tính độc đáo của chuỗi thời ước lượng các khoảng giá trị, xác định các gian như: Khối lượng dữ liệu lớn, sự có mặt điểm tới hạn, hoặc chuyển đổi dữ liệu số của nhiễu ngẫu nhiên, và các mối quan hệ thành các biến rời rạc. Phương pháp xấp xỉ phi tuyến tính của các phần tử dữ liệu. Kết từng đoạn là một trong những phương pháp quả là, việc biểu diễn dữ liệu chỉ ở dạng đơn tiếp cận miền thời gian phổ biến nhất. Các giản hóa, hoặc xử lý dữ liệu là một bước thiết phương pháp này biểu diễn dữ liệu ban đầu yếu trong việc khai phá dữ liệu theo chuỗi dựa trên các khoảng thời gian không chồng thời gian. Mục đích chính của việc biểu diễn chéo. Kết quả trình bày dữ liệu theo phương dữ liệu là giảm dữ liệu đến một kích pháp xấp xỉ từng đoạn có thể là một dãy các SỐ 05 – 2017 35
Thống kê Quốc tế và Hội nhập Biểu diễn dữ liệu… đoạn thẳng liên tục hay rời rạc, hoặc các giá các đa thức tự hồi quy và chuyển động trung trị biểu diễn của tất cả các khoảng với chiều bình. Các mô hình này thường phụ thuộc vào dài giảm đáng kể. Phương pháp tiếp cận phổ các giả định cụ thể và đủ số lượng các điểm biến khác để biểu diễn dữ liệu là xác định các dữ liệu, nhưng trở nên không chính xác khi điểm quan trọng để bảo vệ các điểm tới hạn kích thước dữ liệu tăng lên sẽ không đúng góp phần tiết lộ các tính năng quan trọng, với các điều kiện giả định trong thực tế. chẳng hạn như hình dạng tổng thể hoặc xu Khi kích thước tăng lên, phương pháp hướng thay đổi các điểm dữ liệu ban đầu. xấp xỉ từng đoạn, chẳng hạn như với đa thức Gần đây, khi sự quan tâm đến việc khai phá từng đoạn và hàm spline, thường có hiệu quả dữ liệu có khối lượng lớn, gọi là “dữ liệu lớn” hơn. Thật vậy, nhiều phương pháp biểu diễn tiếp tục tăng lên, các phương pháp biểu diễn chuỗi thời gian dựa trên phương pháp xấp xỉ dữ liệu bằng cách biến đổi chuỗi thời gian số từng đoạn do dữ liệu chuỗi thời gian thường sang các biến hoặc ký hiệu rời rạc sẽ trở nên được đặc trưng bởi kích thước lớn và sự hiện phổ biến hơn. Phương pháp biểu diễn ký hiệu diện của nhiễu ngẫu nhiên. Theo phương hóa là chuyển đổi ký hiệu cho phép không pháp xấp xỉ từng đoạn, tất cả các điểm dữ chỉ giảm dữ liệu mà còn tính toán hiệu quả liệu được chia thành một số phân đoạn và sử dụng không gian bộ nhớ để lưu trữ dữ không chồng chéo để xây dựng một mô hình liệu vì yêu cầu ít dung lượng hơn cho dữ liệu cục bộ μi(t) (bi - 1 ≤ t
Biểu diễn dữ liệu… Thống kê Quốc tế và Hội nhập Vì lý do này, xử lý trực tuyến thường được Sự lựa chọn công thức của mô hình cục dùng trong việc khai phá luồng dữ liệu lớn. bộ cho các phân đoạn có thể được xác định bởi một số giá trị mang tính đại diện hoặc bởi 3. Biểu diễn dữ liệu chuỗi thời gian một mô hình tham số. Một mô hình cục bộ Xấp xỉ từng đoạn đơn giản là giá trị trung bình. Sử dụng giá trị Một cách tiếp cận đơn giản và phổ biến trung bình, dữ liệu ban đầu được biểu diễn để biểu diễn dữ liệu là xấp xỉ từng đoạn. dưới dạng các hàm hằng số hoặc các hàm Nhìn chung, các thuật toán xấp xỉ chia toàn bậc thang. Đường tuyến tính và các mô hình bộ tập dữ liệu vào một số khoảng không đa thức cũng có thể được sử dụng cùng với chồng chéo theo thời gian và đặt các mô xu hướng của từng đoạn dữ liệu tổng hợp. hình cục bộ vào các khoảng đó. Theo công Thay vì sử dụng số trung bình, tổng các biến thức, X = {xt|t = 1, 2, ..., N}, trong đó t là thiên[1] hoặc sự biến động có thể được sử chỉ số thời gian, toàn bộ tập dữ liệu được dụng làm giá trị mang tính đại diện của các chia thành các tập con (k
Thống kê Quốc tế và Hội nhập Biểu diễn dữ liệệu… Các phân đoạn m chiều dài bằngng nhau, được gọi là các khung, được chuyển n đ đổi thành các giá trị trung bình của dữ liệuu bên Trong đó: cvi là giá trị trung bình của c trong, và vector của các giá trị trung bình dữ liệu trong phân đoạn i; và cri là điểm m đầu đ này biểu diễn độ giảm của C. Do đó, dữ ữ liệu nút bên phải của phân đoạn i với chiều u dài được trình bày giống với dữ liệu ban đầ ầu khi của phân đoạn i là cri − cri − 1, i = 1, …, n. m = N, và giá trị trung bình của dữ liệuu ban Tính năng tổng các biến thể phân đoạn đo đầu đạt được khi m = 1. Số phân đoạn n m có thể là tham số do người dùng xác định. nh. Do Trong khai phá dữ liệu chuỗi thờii gian, đó nó linh hoạt để điều chỉnh mức độ phân nhiều biện pháp tương tự được đề xuấtt dựa d loại của dữ liệu bị giảm. Trong công thứcc (3), trên cơ sở đo độ khoảng ng cách Euclide. Thông chúng ta giả sử m là một hệ số của a N. Trong thường, tiêu chuẩn hoá dữ liệu đượcc yêu cầu c trường hợp m không phải là một hệ số củ ủa N, trước khi áp dụngng phương pháp tương tự t chiều dài của một chuỗi thời gian nhấtt đ định giữa dữ liệu chuỗi thời gian từ khoảng ng cách sẽ lớn hơn hoặc nhỏ hơn N, xem Keogh cùng Euclide là nhạy cảm với nhiễuu và quy mô dọc d [1] các cộng sự [2], Chakrabarti và Mehrotra[4]. của dữ liệu. Lee cùng các cộng sự đề nghị ng tổng hợp các biến thể (SSV). Phương pháp Phương pháp xấp xỉ hằng số ttừng này được phát triển dựa trên ý tưởng tổ ổng đoạn thích nghi của biến thể là bất biến theo chuyển n dịch d Phương pháp xấp xỉ hằng số từng ng đo đoạn chiều dọc của dữ liệu. Trước hết,t, so sánh tập t [5] thích nghi (APCA ) giống ng như phương pháp dữ liệu chuỗi thời gian đượcc chia thành các PAA là xấp xỉ dữ liệu ban đầu u thành nh những phân đoạn n với chiều dài bằng nhau và sau đoạn thẳng nằm m ngang. Tuy nhiên, phương đó tổng các biến thể cho tất cả các phân pháp này khác với PAA là các đoạn ở PAA có đoạn được tính toán. Cụ thể, thuậtt toán tạo t kích thước bằng nhau, còn ở APCA thì kích ra n phân đoạn (n
Biểu diễn dữ liệu… Thống kê Quốc tế và Hội nhập Xác định các điểm tới hạn theo thứ tự dựa trên khoảng cách vuông góc hoặc thẳng đứng từ đường thẳng giữa hai Mặc dù xấp xỉ từng đoạn thể hiện dữ điểm quan trọng trước đó. Đặc biệt, với chuỗi liệu bằng cách gắn các mô hình cục bộ hoặc thời gian x1, x2, ..., xn, điểm đầu tiên x1 và thu thập số liệu thống kê của các phân đoạn, điểm cuối cùng xn ; P1 là PIP thứ nhất và P2 việc biểu diễn dữ liệu bằng cách xác định các là PIP thứ hai. Sau đó, PIP thứ ba, là P3 được điểm tới hạn tập trung vào việc chọn một tập xác định dựa trên khoảng cách vuông góc hợp các điểm từ toàn bộ tập dữ liệu. Các hoặc thẳng đứng từ đường thẳng giữa P1 và điểm dữ liệu đã chọn này góp phần quan P2. Đó là, các điểm ở khoảng cách tối đa từ trọng vào việc bảo toàn các tính năng của dữ liệu ban đầu. Mặc dù 'tầm quan trọng' của P P là P3. Các điểm trong khoảng cách tối đa các điểm có thể được xác định tùy thuộc vào từ P P và P P được xác định là PIP thứ tư, tính năng mà người dùng muốn tìm từ dữ P4. Tương tự, để tìm PIP thứ k, Pk, thuật toán liệu, nhiều cách tiếp cận để giảm dữ liệu tìm kiếm điểm trong khoảng cách tối đa từ k- trong miền thời gian cố gắng tìm ra các điểm 2 đường thẳng giữa các PIP lân cận cho đến góp phần tạo nên hình dạng của dữ liệu ban khi nó xác định một số PIP được xác định đầu, ví dụ khi một cú nhảy hoặc rơi đột ngột trước đó. Cách tiếp cận này rõ ràng là xử lý xảy ra. Nếu tất cả các điểm dữ liệu là có sẵn hàng loạt vì tất cả các điểm dữ liệu được yêu trước khi xử lý, chúng ta có thể phân tích cấu cầu tại thời điểm phân tích để xác định các trúc dữ liệu tổng thể và chọn các điểm quan PIP thứ nhất và thứ hai, x1 và xn. trọng liên tục cho toàn bộ tập dữ liệu theo Nén bằng cách trích xuất các cực trị các tiêu chí quan trọng (xử lý hàng loạt). Nếu Với ý tưởng rằng giá trị cực tiểu và giá không, chúng ta có thể áp dụng các tiêu chí trị cực đại cục bộ có thể tốt cho những điểm này cho một nhóm các điểm dữ liệu tuần tự, quan trọng ảnh hưởng đến hình dạng của dữ vì dữ liệu mới được cập nhật để xác định các liệu, Fink và Gandhi đề xuất nén hiệu quả điểm quan trọng (xử lý trực tuyến). Hai ví dụ bằng cách điều tra cực trị (minima và sau đây là phương pháp biểu diễn dữ liệu maxima). Trong số tất cả các điểm cực trị, bằng cách xác định các điểm tới hạn bằng xử thuật toán chọn các điểm tới hạn góp phần lý hàng loạt và trực tuyến. tạo ra một mức độ dao động lớn hơn và loại Ví dụ: Xác định các điểm tới hạn bỏ các điểm dữ liệu còn lại. “Mức độ quan Các điểm tới hạn[6] trọng” của cực trị được xác định bởi một tham số ngưỡng R>0, là một mức độ dao Một số điểm dữ liệu trong chuỗi thời động “quan trọng” tối thiểu. Ví dụ, cho một gian có thể ảnh hưởng nhiều hơn đến hình chuỗi thời gian xi, ..., xj và R>0, x k (i
Thống kê Quốc tế và Hội nhập Biểu diễn dữ liệệu… Thuật toán này có thể được sử dụng ng không liệu cũng như tiết kiệm không gian bộ nhớ ớ và chỉ cho việc xử lý hàng loạtt mà còn cho xxử lý tính toán hiệu quả hơn trong khi kích thướcthư trực tuyến để lập chỉ mục nhanh. của dữ liệu ban đầu không thay đổii theo phương pháp cũ. Hai ví dụ tiếp theo mô tả t Biểu diễn dữ liệu ký hiệu hóa chi tiết về biểu diễn dữ liệu ký hiệu hóa. Một cách tiếp cận phổ biến n khác cho Ví dụ: Biểu diễn ký hiệu hóa[8] việc biểu diễn chuỗi thời gian là chuyển n đ đổi dữ liệu số thành một số hữu hạn các biế ến rời Mô tả hình dạng chữ cái rạc, thường là các biến ký hiệu. Chuyển n đđổi Mô tả hình dạng chữ cái (SDA[8]) được đư các giá trị số thành các chuỗi giúp tiếtt ki kiệm đề xuất cho việc tìm kiếm tương đốii trong cơ không gian bộ nhớ và cho phép tính toán sở dữ liệu chuỗi thời gian lớn. n. Phương pháp nhanh. Phương pháp thứ nhất đơn giả ản là này biến đổi sự khác biệt giữa hai điểm m lân biểu diễn dữ liệu ký hiệu hóa trong mộ ột dải cận, xi và xi + 1, đó là d i  xi 1  xi , đến n một m giá trị nhất định. Cho một chuỗi thờii gian X  xi xi  R, i  1,..., N , nó đượcc ánh xxạ tập hợp các chữ cái hữu hạn. Ví dụ,, nó sử s dụng a, u, s, d, và e tương ứng vớii các biến bi tới chuỗi ký hiệu S  si si  C , i  1,..., N  , tăng cao, tăng nhẹ, ổn định, giảm nhẹ,, và trong đó C là tập hợp các ký hiệu. u. MMột giảm nhiều. Các điểm cắt, lvalue (cận n dưới) dư phương pháp phổ biến khác là làm rời rạ ạc dữ và hvalue (cận trên), để xác định mộtt giá trị tr liệu từng đoạn và sau đó chuyển đổii nhnhững ký hiệu cho mỗi di được lấy dựa trên sự phân dữ liệu từng đoạn vào chuỗi. Tức là, dữ ữ liệu bố của di. Do đó, kiến thức về di là cần n thiết thi biểu diễn bao gồm hai bước: Đầu u tiên là xxấp để tìm điểm cắt tốii ưu. SDA không phù hợp h xỉ từng đoạn và sau đó, chuyển đổii các d dữ với dữ liệu nhiễu vì sự khác biệt di bị ả ảnh liệu thu được từ bước đầu u tiên thành các ký hưởng lớn bởi các nhiễu ngẫu nhiên và kết k hiệu. Phương pháp thứ hai cho phép giảm md dữ quả là không nắm bắt được hình dạng ng chung [9] của dữ liệu ban đầu . 40 SỐ 05 – 2017 201
Biểu diễn dữ liệu… Thống kê Quốc tế và Hội nhập Hình 1 biểu diễn chuỗi thời gian theo phương pháp PAA, PIPs, và SAX. Kích thước của dữ liệu gốc đã được giảm từ N = 200 xuống n = 10 bằng phương pháp PAA và SAX, và còn n=11 bởi phương pháp PIP. nhiều phương pháp đã được đề xuất, không Xấp xỉ gộp ký hiệu hóa có phương pháp nào vượt trội hoàn toàn so Xấp xỉ gộp ký hiệu hóa (SAX[10]) biểu với tất cả những phương pháp khác. Thay diễn dữ liệu chuỗi thời gian qua hai bước. vào đó, các tính năng mà người sử dụng Trước hết, SAX sử dụng dữ liệu bình thường muốn truy cập dữ liệu, nên được xem xét để để biểu diễn bởi PAA, và sau đó các hệ số chọn một phương pháp biểu diễn dữ liệu thu được từ PAA được chuyển thành các thích hợp. Hình 1 minh họa biểu diễn chuỗi chuỗi chữ cái. Do đó, cần phải có hai tham số thời gian bằng ba phương pháp khác nhau. để biểu diễn SAX: Số ký hiệu (kích thước chữ Việc biểu diễn nguồn dữ liệu là một cái) và kích thước của dữ liệu bị giảm (chiều thách thức vì quy mô và tốc độ của nó, tuy dài của dữ liệu bị giảm). Cho chuỗi thời gian nhiên lĩnh vực đầy hứa hẹn vì sự quan tâm C = {c1, ..., cN}, hệ số của dữ liệu giảm đến “dữ liệu lớn” tiếp tục tăng lên trong thời C  c1 ,..., cn  (n
Dự thảo Quyết định… Nghiên cứu – Trao đổi 18.5 Độ dài của dãy số thời gian 18.6 Giải thích rõ các trường hợp ngắt quãng số liệu trong dãy số thời gian Có khung dữ liệu đặc tả thống kê và tài liệu hướng dẫn biên soạn dữ liệu 19.1 đặc tả thống kê Công bố và phổ biến số liệu thống kê kèm theo dữ liệu đặc tả thống kê 19.2 tương ứng hoặc có chỉ dẫn đến dữ liệu đặc tả thống kê 19. Quản lý dữ liệu đặc tả Xây dựng và cập nhật thường xuyên cơ sở dữ liệu đặc tả thống kê dùng 19.3 thống kê chung Công chức, viên chức được đào tạo, bồi dưỡng thường xuyên về quản lý 19.4 và sử dụng dữ liệu đặc tả thống kê 19.5 Tỷ lệ đầy đủ của dữ liệu đặc tả thống kê ------------------------------------------------------- Tiếp theo trang 41 3. Yi B, Faloutsos C, Lập chỉ mục chuỗi 8. André-Jönsson H, Dushan ZB, Sử thời gian nhanh cho các chỉ tiêu tùy ý trong dụng tệp chữ ký để truy vấn dữ liệu theo Kỷ yếu của Hội nghị quốc tế lần thứ 26 về Cơ chuỗi thời gian, New York:Springer, 1977, sở dữ liệu rất lớn, San Francisco, Morgan 211–220; Kaufmann Publishers Inc, 2000, VLDB’00: 9. Lin J, Keogh E, Wei L, Lonardi , Trải 385–394; nghiệm SAX: Một biểu diễn biểu tượng cho 4. Chakrabarti K, Mehrotra S, Cây chuỗi thời gian trong Khai phá dữ liệu và hybrid: một cấu trúc chỉ mục cho không gian Khám phá kiến thức, tập 15, New York: đặc trưng trong Kỷ yếu Hội thảo quốc tế về Kỹ Springer; 2007, 107–144; thuật dữ liệu lần thứ 15, IEEE, 1999, 440-447; 10. Lin J, Keogh E, Wei L, Lonardi S, 5. Keogh E, Chakrabarti K, Pazzani M, Chiu B. Một biểu diễn biểu tượng chuỗi thời Mehrotra S, Giảm kích thước thích ứng cục gian, có liên quan đến thuật toán phát trực bộ để lập chỉ mục các cơ sở dữ liệu chuỗi tuyến trong Kỷ yếu hội thảo ACM SIGMOD thời gian lớn, ACM SIGMOD Record 2001, lần thứ 8 về các vấn đề nghiên cứu trong 30:151–162; khai phá dữ liệu và khám phá kiến thức, 6. Chung F, Fu T, Luk R, Ng V, Sự kết ACM, 2003. hợp chuỗi thời gian linh hoạt dựa trên các Thái Học (lược dịch) điểm tới hạn trong Hội thảo quốc tế về Hội Nguồn: Data representation for time thảo Trí thức nhân tạo về học hỏi từ dữ liệu series data mining: time domain approaches, tạm thời và không gian, 2001, 1–7; http://onlinelibrary.wiley.com/doi/10.1002/wi 7. Fink E, Gandhi H, Sự nén của chuỗi cs.1392/epdf thời gian bằng cách trích xuất các extrema lớn, J Exp Theor Artif Intell 2011, 23:255–270; SỐ 05 – 2017 13