Tìm kiếm
Đang tải khung tìm kiếm
Kết quả 1 đến 1 của 1

    TIẾN SĨ Khai phá dữ liệu chuỗi thời gian dựa vào rút trích đặc trưng bằng phương pháp điểm giữa và kỹ thuật xén

    D
    dream dream Đang Ngoại tuyến (18524 tài liệu)
    .:: Cộng Tác Viên ::.
  1. Gửi tài liệu
  2. Bình luận
  3. Chia sẻ
  4. Thông tin
  5. Công cụ
  6. Khai phá dữ liệu chuỗi thời gian dựa vào rút trích đặc trưng bằng phương pháp điểm giữa và kỹ thuật xén

    1

    1. Giới thiệu.
    1.1. Tổng quan về đề tài.
    Một chuỗi thời gian (time series) là một chuỗi các điểm dữ
    liệu được đo theo từng khoảng thời gian liền nhau theo một tần
    suất thời gian thống nhất.
    Một chuỗi thời gian dạng luồng (streaming time series) C
    là một chuỗi các giá trị thực c 1 , c 2 , , trong đó các giá trị mới
    tới một cách liên tục và được nối vào cuối chuỗi C theo thứ tự
    thời gian.
    Những khó khăn và thách thức khi nghiên cứu về dữ liệu
    chuỗi thời gian: (1) dữ liệu thường rất lớn, (2) phụ thuộc nhiều
    vào yếu tố chủ quan của người dùng và tập dữ liệu khi đánh
    giá mức độ tương tự giữa các chuỗi, (3) dữ liệu không đồng
    nhất.
    1.2. Động cơ, mục tiêu, đối tượng và phạm vi nghiên cứu.
    Dữ liệu chuỗi thời gian được sử dụng phổ biến trong rất
    nhiều lĩnh vực. Kết quả khảo sát nêu trong bài báo của Yang
    và Wu (2006) “10 challenging problems in Data Mining
    Research” cho thấy hướng nghiên cứu về khai phá dữ liệu
    chuỗi thời gian là một trong 10 hướng nghiên cứu sẽ là quan
    trọng và thách thức nhất.
    Vì dữ liệu chuỗi thời gian thường rất lớn, những giải thuật
    khai phá chuỗi thời gian phải thỏa mãn hai tính chất: chúng
    phải hữu hiệu (tức có độ phức tạp tính toán thấp) và đảm bảo
    đưa lại kết quả đúng. Đây là một thách thức đã thúc đẩy chúng
    tôi thực hiện nghiên cứu về lĩnh vực này.
    Mục tiêu của luận án là đề xuất cách tiếp cận mới cho một
    số bài toán khai phá dữ liệu chuỗi thời gian. Đối tượng nghiên
    cứu là dữ liệu chuỗi thời gian với chuỗi thời gian được định
    nghĩa là một chuỗi các số thực X = x 1 , x 2 , x 3 , x n , trong đó x i là
    giá trị đo được ở thời điểm thứ i. Phạm vi nghiên cứu của luận
    án bao gồm nghiên cứu bốn bài toán quan trọng trong khai phá
    dữ liệu chuỗi thời gian, đó là: tìm kiếm tương tự, gom cụm,
    phát hiện motif và dự báo trên dữ liệu chuỗi thời gian, trong
    đó tìm kiếm tương tự là bài toán nền tảng. 2

    1.3. Nhiệm vụ và hướng tiếp cận của luận án.
    Hướng tiếp cận chung thường được sử dụng cho các bài
    toán trong khai phá dữ liệu chuỗi thời gian là thực hiện chúng
    trong không gian thu giảm (không gian đặc trưng) của dữ liệu.
    Các nội dung nghiên cứu trong luận án cũng được định hướng
    đi theo cách tiếp cận này.
    Nhiệm vụ của luận án là: (1) đề xuất một phương pháp thu
    giảm số chiều mới thỏa điều kiện chặn dưới và có thể kết hợp
    với một cấu trúc chỉ mục đa chiều hỗ trợ việc tìm kiếm tương
    tự hữu hiệu, (2) ứng dụng phương pháp đề xuất vào bài toán
    phát hiện motif theo hướng tiếp cận xấp xỉ, (3) ứng dụng
    phương pháp đề xuất vào bài toán gom cụm theo phương pháp
    gom cụm có thời gian thưc thi tùy chọn, (4) ứng dụng phương
    pháp đề xuất vào bài toán tìm kiếm tương tự trên chuỗi thời
    gian dạng luồng và (5) ứng dụng phương pháp thu giảm số
    chiều đã đề xuất vào bài toán dự báo dữ liệu chuỗi thời gian có
    tính xu hướng hoặc mùa.
    2. Cơ sở lý thuyết và các công trình liên quan.
    2.1. Các độ đo tương tự.
    Trong các bài toán về khai phá dữ liệu chuỗi thời gian, để
    so sánh hai chuỗi người ta sử dụng các độ đo tương tự. Hai độ
    đo tương tự thường được sử dụng trong lĩnh vực này là độ đo
    Euclid và xoắn thời gian động (Dynamic Time Warping).
    2.2. Thu giảm số chiều chuỗi thời gian.
    Thu giảm số chiều là phương pháp biểu diễn chuỗi thời
    gian n chiều X = {x 1 , x 2 , , x n } thành chuỗi thời gian có N
    chiều Y = {y 1 , y 2 , , y N } với N << n, sao cho vẫn giữ được các
    đặc trưng cần quan tâm của chuỗi thời gian ban đầu. Do khi
    thu giảm số chiều dữ liệu sẽ gây ra mất mát thông tin, nên khi
    thực hiện trên dữ liệu xấp xỉ có thể xảy ra lỗi tìm sót và/hoặc
    lỗi tìm sai. Để đảm bảo có kết quả chính xác, lỗi tìm sót không
    được phép xảy ra. Để đảm bảo điều này, độ đo tương tự trong
    không gian thu giảm phải là chặn dưới của độ đo tương tự
    trong không gian gốc (điều kiện chặn dưới). Để việc tìm kiếm
    trong không gian đặc trưng đạt hiệu quả, phương pháp thu 3

    giảm số chiều cần có tính khả chỉ mục và chi phí hậu kiểm
    thấp. Để chi phí hậu kiểm thấp, lỗi tìm sai phải càng ít càng
    tốt.
    Nhiều phương pháp thu giảm số chiều dựa vào rút trích đặc
    trưng đã được đề xuất và sử dụng. Tuy nhiên có không ít
    phương pháp thu giảm số chiều mắc phải hai nhược điểm quan
    trọng: một số phương pháp thu giảm số chiều không chứng
    minh được bằng toán học thỏa mãn điều kiện chặn dưới (ví dụ
    như các phương pháp dựa vào điểm quan trọng) và một số
    phương pháp khác không đề xuất được cấu trúc chỉ mục thích
    hợp đi kèm để hỗ trợ việc tìm kiếm tương tự hữu hiệu (ví dụ
    như phương pháp xén dữ liệu).
    2.3. Rời rạc hóa chuỗi thời gian.
    Rời rạc hóa (discretization) chuỗi thời gian là quá trình
    biến đổi chuỗi thời gian thành một chuỗi các ký tự. Phương
    pháp rời rạc hóa tiêu biểu là phương pháp xấp xỉ gộp ký hiệu
    hóa (Symbolic Aggregate approXimation - SAX) và các biến
    thể của nó như phương pháp xấp xỉ gộp ký hiệu hóa mở rộng
    (Extended SAX - ESAX), phương pháp xấp xỉ gộp ký hiệu có
    thể được lập chỉ mục (Indexable SAX - ISAX).
    2.4. Cấu trúc chỉ mục.
    Việc sử dụng cấu trúc lập chỉ mục cho phép chúng ta tìm
    kiếm các chuỗi con một cách nhanh chóng và hiệu quả. Các
    cấu trúc chỉ mục đa chiều tiêu biểu như: R-tree và các biến thể
    của nó, chỉ mục đường chân trời (Skyline).
    Chỉ mục đường chân trời sử dụng vùng bao đường chân
    trời. Bằng thực nghiệm, các tác giả đã cho thấy vùng bao
    đường chân trời biểu diễn các chuỗi thời gian chính xác hơn so
    với vùng bao chữ nhật nhỏ nhất và không xảy ra tình trạng phủ
    lấp (overlap).
    2.5. Tìm kiếm tương tự trên chuỗi thời gian.
    Bài toán tìm kiếm tương tự trên dữ liệu chuỗi thời gian
    được phân làm hai loại: so trùng toàn chuỗi và so trùng chuỗi
    con. Trong so trùng toàn chuỗi, các chuỗi thời gian được giả 4

    định là có chiều dài bằng nhau. Bài toán so trùng chuỗi con là
    tìm các chuỗi con trong một chuỗi thời gian tương tự với chuỗi
    truy vấn. Đây là bài toán cơ bản và là một thành phần quan
    trọng của nhiều bài toán khác trong khai phá dữ liệu chuỗi thời
    gian.
    2.6. Tìm kiếm tương tự trên chuỗi thời gian dạng luồng.
    Trong bài toán này, các luồng dữ liệu liên tục được cập
    nhật khi có các điểm dữ liệu mới tới theo thời gian thực. Đó là
    một thách thức khi nghiên cứu về bài toán này do chi phí tính
    toán lại thu giảm số chiều và cập nhật chỉ mục tăng. Thời gian
    qua, nhiều phương pháp đã được đề xuất cho bài toán này như:
    các phương pháp dựa trên dự báo, phương pháp dựa trên độ đo
    có trọng số, phương pháp dựa trên cách tính gia tăng và cập
    nhật chỉ mục trì hoãn.
    2.7. Phát hiện motif trên chuỗi thời gian.
    Motif trong chuỗi thời gian là mẫu xuất hiện với tần suất
    cao nhất. Từ khi được hình thức hóa vào năm 2002, phát hiện
    motif trong dữ liệu chuỗi thời gian đã và đang được dùng để
    giải quyết các bài toán trong nhiều lĩnh vực ứng dụng khác
    nhau. Trong số nhiều giải thuật đã được giới thiệu, phép chiếu
    ngẫu nhiên đã được sử dụng rộng rãi để phát hiện motif trong
    chuỗi thời gian từ khi nó được giới thiệu và có thể được dùng
    để phát hiện tất cả motif với xác xuất cao sau một số lần lặp
    thích hợp ngay cả trong trường hợp có nhiễu.
    2.8. Gom cụm dữ liệu chuỗi thời gian.
    Gom cụm là sự phân chia các đối tượng dữ liệu vào các
    nhóm sao cho độ đo tương tự giữa các đối tượng trong cùng
    nhóm là nhỏ nhất và giữa các đối tượng trong các nhóm khác
    nhau là lớn nhất. Mỗi nhóm được gọi là một cụm (cluster).
    Mặc dù đã có nhiều công trình nghiên cứu về gom cụm dữ
    liệu thường, hầu hết các giải thuật gom cụm đã có trong lĩnh
    vực khai phá dữ liệu và học máy đã không làm việc hiệu quả
    với dữ liệu chuỗi thời gian do những tính chất đặc thù của loại
    dữ liệu này. Những tính chất đặc thù đó là (i) số chiều khá cao, (ii) tính tương quan cao của các đặc trưng được rút trích từ dữ
    liệu và (iii) dữ liệu có thể bị nhiễu. Những tính chất này đặt ra
    một thách thức cho việc gom cụm dữ liệu chuỗi thời gian. Hai
    giải thuật thường được sử dụng để gom cụm dữ liệu chuỗi thời
    gian là k-Means và I-k-Means.

    Xem Thêm: Khai phá dữ liệu chuỗi thời gian dựa vào rút trích đặc trưng bằng phương pháp điểm giữa và kỹ thuật xén
    Nội dung trên chỉ thể hiện một phần hoặc nhiều phần trích dẫn. Để có thể xem đầy đủ, chi tiết và đúng định dạng tài liệu, bạn vui lòng tải tài liệu. Hy vọng tài liệu Khai phá dữ liệu chuỗi thời gian dựa vào rút trích đặc trưng bằng phương pháp điểm giữa và kỹ thuật xén sẽ giúp ích cho bạn.
    #1
  7. Đang tải dữ liệu...

    Chia sẻ link hay nhận ngay tiền thưởng
    Vui lòng Tải xuống để xem tài liệu đầy đủ.

    Gửi bình luận

    ♥ Tải tài liệu

social Thư Viện Tài Liệu
Tài liệu mới

Từ khóa được tìm kiếm

dac trung cua du lieu thoi gian

Quyền viết bài

  • Bạn Không thể gửi Chủ đề mới
  • Bạn Không thể Gửi trả lời
  • Bạn Không thể Gửi file đính kèm
  • Bạn Không thể Sửa bài viết của mình
  •  
DMCA.com Protection Status