Luận văn thạc sĩ về nhận dạng mô típ trong dữ liệu chuỗi thời gian hình ảnh

Nghiên cứu chuyên sâu Nhận dạng mô típ trong chuỗi thời gian hình ảnh - Luận văn thạc sĩ Khoa học máy tính, phương pháp luận hiện đại, kết quả ứng

• Tác giả: Trần Công Thanh
• Người hướng dẫn: TS. Bùi Hoài Thắng
• Trường học: Đại học Quốc gia Thành phố Hồ Chí Minh
• Chuyên ngành: Khoa học máy tính
• Đề tài: Nhận dạng mô típ trong chuỗi thời gian hình ảnh
• Loại tài liệu: luận văn thạc sĩ
• Năm xuất bản: 2011
• Địa điểm: Thành phố Hồ Chí Minh

Tóm tắt

I. Tổng quan về nhận dạng mô típ trong chuỗi thời gian hình ảnh

Nhận dạng mô típ trong chuỗi thời gian hình ảnh là một lĩnh vực nghiên cứu quan trọng trong khoa học máy tính. Nó liên quan đến việc tìm kiếm các mẫu lặp lại trong dữ liệu hình ảnh theo thời gian. Các ứng dụng của nó rất đa dạng, từ khảo cổ học đến sinh học. Việc hiểu rõ về chuỗi thời gian và cách thức hoạt động của nó là rất cần thiết để phát triển các giải pháp hiệu quả.

1.1. Định nghĩa chuỗi thời gian hình ảnh

Chuỗi thời gian hình ảnh là tập hợp các hình ảnh được ghi nhận theo thời gian. Mỗi hình ảnh trong chuỗi có thể được xem như một điểm dữ liệu trong không gian thời gian. Việc phân tích chuỗi thời gian hình ảnh giúp nhận diện các mô típ và xu hướng trong dữ liệu.

1.2. Tầm quan trọng của nhận dạng mô típ

Nhận dạng mô típ có vai trò quan trọng trong nhiều lĩnh vực, bao gồm khảo cổ học và sinh học. Nó giúp xác định mối quan hệ giữa các mẫu hình ảnh và hỗ trợ trong việc phân tích dữ liệu lớn.

II. Thách thức trong nhận dạng mô típ hình ảnh

Việc nhận dạng mô típ trong chuỗi thời gian hình ảnh gặp phải nhiều thách thức. Các vấn đề như khối lượng dữ liệu lớn, sự không đồng nhất trong dữ liệu và yếu tố chủ quan trong quá trình thu thập dữ liệu đều ảnh hưởng đến độ chính xác của các thuật toán nhận dạng.

2.1. Khối lượng dữ liệu lớn

Chuỗi thời gian hình ảnh thường chứa một lượng lớn dữ liệu, điều này gây khó khăn trong việc xử lý và phân tích. Các kỹ thuật thu giảm số chiều và rời rạc hóa là cần thiết để giảm thiểu khối lượng dữ liệu.

2.2. Sự không đồng nhất trong dữ liệu

Dữ liệu hình ảnh có thể được thu thập từ nhiều nguồn khác nhau, dẫn đến sự không đồng nhất. Điều này có thể làm giảm tính chính xác của các thuật toán nhận dạng mô típ.

III. Phương pháp rời rạc hóa trong nhận dạng mô típ

Phương pháp rời rạc hóa là một trong những kỹ thuật quan trọng trong nhận dạng mô típ. Hai phương pháp chính được nghiên cứu là SAX và ESAX. Mỗi phương pháp có những ưu điểm và nhược điểm riêng, ảnh hưởng đến hiệu quả của việc nhận dạng mô típ.

3.1. Kỹ thuật SAX

SAX (Symbolic Aggregate approXimation) là một phương pháp rời rạc hóa dữ liệu chuỗi thời gian. Nó giúp giảm số chiều của dữ liệu mà vẫn giữ lại các thông tin quan trọng. Tuy nhiên, SAX có thể mất đi một số mẫu thức quan trọng trong dữ liệu.

3.2. Kỹ thuật ESAX

ESAX (Extended SAX) là một cải tiến của SAX, cho phép giữ lại nhiều thông tin hơn bằng cách thêm vào các giá trị cực trị của mỗi phân đoạn. Điều này giúp cải thiện độ chính xác trong việc nhận dạng mô típ.

IV. Ứng dụng thực tiễn của nhận dạng mô típ

Nhận dạng mô típ trong chuỗi thời gian hình ảnh có nhiều ứng dụng thực tiễn. Từ khảo cổ học đến sinh học, các mô típ hình ảnh giúp xác định mối quan hệ giữa các mẫu và hỗ trợ trong việc phân tích dữ liệu lớn.

4.1. Ứng dụng trong khảo cổ học

Trong khảo cổ học, việc tìm kiếm các mô típ hình ảnh giúp xác định mối quan hệ giữa các khu vực và thời kỳ khác nhau. Điều này có thể cung cấp thông tin quý giá về lịch sử và văn hóa.

4.2. Ứng dụng trong sinh học

Trong sinh học, nhận dạng mô típ giúp phân tích hình ảnh của các loài vật và xác định mối quan hệ tiến hóa giữa chúng. Điều này hỗ trợ trong việc nghiên cứu và bảo tồn các loài.

V. Kết luận và tương lai của nhận dạng mô típ

Nhận dạng mô típ trong chuỗi thời gian hình ảnh là một lĩnh vực nghiên cứu đầy tiềm năng. Với sự phát triển của công nghệ và các thuật toán mới, khả năng nhận dạng mô típ sẽ ngày càng chính xác và hiệu quả hơn. Tương lai của lĩnh vực này hứa hẹn sẽ mang lại nhiều ứng dụng thực tiễn hơn nữa.

5.1. Xu hướng phát triển

Các nghiên cứu trong tương lai sẽ tập trung vào việc cải thiện độ chính xác và hiệu suất của các thuật toán nhận dạng mô típ. Việc áp dụng trí tuệ nhân tạo và học máy sẽ mở ra nhiều cơ hội mới.

5.2. Thách thức trong tương lai

Mặc dù có nhiều tiềm năng, nhưng nhận dạng mô típ vẫn đối mặt với nhiều thách thức, bao gồm việc xử lý dữ liệu lớn và sự không đồng nhất trong dữ liệu. Giải quyết những vấn đề này sẽ là chìa khóa cho sự phát triển của lĩnh vực này.

Trích đoạn nội dung tài liệu

Chương 1: Giới thiệu đề tài ký hiệu hoá a, huấn luyện giải thuật để tìm ra trị trung bình (average) của ma trận đụng độ (collision matrix) trong giải thuật chiếu ngẫu nhiên-Random-Projection. Tiếp theo, luận văn đã thực nghiệm giải thuật nhận dạng mô-típ trên các tập dữ liệu chuỗi thời gian hình ảnh. Kết quả thực nghiệm cho thấy giải thuật nhận dạng mô-típ khi dùng phương pháp rời rạc hoá hoá ESAX (cả hai cách xoay RT1,RT2) thường thời gian thực thi nhanh hơn, và độ chính xác cao hơn khi giải thuật dùng phương pháp rời rạc hoá SAX. Hiện thực của hệ thống sẽ được trình bày cụ thể trong các chương tiếp theo trong luận văn.

Cấu trúc luận văn: Các chương tiếp theo trong luận văn được tổ chức như sau:  Chương 2: Các công trình liên quan. Trong chương này đề cập đến các công trình liên quan đến bài toán nhận dạng mô-típ, như: các kỹ thuật thu giảm số chiều, kỹ thuật rời rạc hoá, giải thuật nhận dạng mô-típ …  Chương 3: Cơ sở lý thuyết, nêu lên các lý thuyết được sử dụng trong luận văn: kỹ thuật thu giảm số chiều PAA, kỹ thuật SAX , ESAX , giải thuật chiếu ngẫu nhiên-Random-Projection …  Chương 4: Nội dung nghiên cứu, là các vấn đề khi nhận dạng mô-típ hình ảnh trong luận văn cần giải quyết, cũng như khi hiện thực chương trình.  Chương 5: Thực nghiệm, chương này trình bày các kết quả thực nghiệm trên một số tập dữ liệu chuỗi thời gian hình ảnh đã được thực hiện trong luận văn.  Chương 6: Kết luận, chương này nêu những nhận xét, kết luận, các đóng góp và hướng phát triển luận văn.

Luận Văn Thạc Sĩ – Trần Công Thanh 8 Nhận dạng mô-típ trong dữ liệu chuỗi thời gian hình ảnh Chương 2: Các công trình liên quan CHƯƠNG 2: CÁC CÔNG TRÌNH LIÊN QUAN Trong chương này, luận văn trình bày về các công trình liên quan đến đề tài như các kỹ thuật thu giảm số chiều, các phương pháp rời rạc hoá, giải thuật nhận dạng mô-típ …. Trong số các bài toán khai phá dữ liệu chuỗi thời gian như phân lớp, gom cụm, trực quan hoá chuỗi thời gian….,bài toán phát hiện mô-típ trong tập dữ liệu chuỗi thời gian cũng thu hút nhiều sự quan tâm của các nhà nghiên cứu [4][6][14][20]…, và bài toán này cũng hỗ trợ cho các vấn đề gom cụm, phân lớp, tìm luật kết hợp, trực quan hoá … trong cơ sở dữ liệu chuỗi thời gian. Đầu tiên hỗ trợ cho bài toán tìm mô-típ là các độ đo tương tự: độ đo Euclidean, độ đo xoắn thời gian động - (Dynamic Time Warping - DTW), độ đo chuỗi con chung dài nhất (Longest Common Subsequence - LCS)… Tùy theo từng ứng dụng, mục đích khác nhau mà người dùng chọn các độ đo phù hợp. Kích thước chuỗi thời gian nói chung và chuỗi thời gian hình ảnh nói riêng thường rất lớn nên các kỹ thuật thu giảm số chiều(dimensional reduction), rời rạc hoá (discretization) … được đề xuất nhằm làm giảm tài nguyên tính toán, cũng như tài nguyên lưu trữ khi làm việc với dữ liệu chuỗi thời gian.

Thứ hai là các kỹ thuật thu giảm số chiều dựa vào đặc trưng: • Các phép biến đổi trong miền tần số như phép biến đổi Fourier – Discrete Fourier Transform (DFT), phép biến đổi Wavelet – Discrete Wavelet Transform (DWT), phép phân rã trị kỳ dị - Singlular Value Decomposition (SVD)… • Các phép biến đổi xấp xỉ từng đoạn như phương pháp xấp xỉ hằng số từng đoạn thích nghi (Adaptive Piecewise Constant Approximation – APCA) mà cụ thể là kỹ thuật xấp xỉ gộp từng đoạn – PAA ( Piecewise Aggregate Approximation) [8]. Luận Văn Thạc Sĩ – Trần Công Thanh 9 Nhận dạng mô-típ trong dữ liệu chuỗi thời gian hình ảnh Chương 2: Các công trình liên quan • Các phương pháp biến đổi dựa vào điểm quan trọng. Thứ ba là kỹ thuật rời rạc hoá dữ liệu như cụ thể là kỹ thuật xấp xỉ gộp ký hiệu hoá – SAX (Symbolic Aggregate approXimation) [15], phương pháp xấp xỉ gộp ký hiệu hoá mở rộng Extended SAX(Extension of Symbolic Aggregate approXimation ) [16]… Quan trọng là các giải thuật tìm kiếm mô-típ như giải thuật Brute-Force nhận dạng mô-típ, giải thuật EMMA được Lin cùng các cộng sự đề xuất 2002[14], giải thuật chiếu ngẫu nhiên – Random Projections được Buhler và Tompa đề xuất 2001[4] … Các ký hiệu sử dụng trong luận văn được trình bày trong bảng 2. Các kỹ thuật thu giảm số chiều dựa vào đặc trưng: Kỹ thuật thu giảm số chiều là kỹ thuật biến đổi dữ liệu chuỗi thời gian thành những đường cơ bản đã được định nghĩa trước, chuyển chuỗi thời gian T=t 1 ,.t n thành chuỗi C = c 1 ,… c w từ đó người dùng có thể lưu trữ và xử lý trên chuỗi có w giá trị.

Từ C khi phục hồi về T sẽ bị sai số, giá trị sai số tỉ lệ nghịch vào thông số w, nếu w càng lớn thì giá trị sai số càng nhỏ và ngược lại. Các phương pháp biến đổi trên miền tần số: 2. Phương pháp biến đổi Fourier rời rạc: Phương pháp biến đổi rời rạc Fourier (Discrete Fourier Tranform) – DFT do R. Agrawal và cộng sự đề nghị[1][2].

Trong phương pháp biến đổi Fourier thì đường dữ liệu ban đầu được biểu diễn bởi các đường căn bản. Nhưng đường căn bản trong trường hợp này là đường sin và cosin.1) Ngoài khả năng nén dữ liệu, với cách tính khoảng cách dựa trên khoảng cách Euclidean thì phương pháp Fourier cho phép so sánh gián tiếp 2 chuỗi X, Y thông qua khoảng cách của 2 chuỗi X f , Y f đã được biến đổi. Sở dĩ phép biến đổi Fourier rời rạc có tính chất trên là vì: Luận Văn Thạc Sĩ – Trần Công Thanh 10 Nhận dạng mô-típ trong dữ liệu chuỗi thời gian hình ảnh Chương 2: Các công trình liên quan D(X, Y) ≥ α D(X f , Y f ) (trong đó α là hằng số) Vì vậy, phương pháp biến đổi Fourier đã được sử dụng trong nhiều ứng dụng và một số phương pháp lập chỉ mục như F-index, ST-index …. Ưu điểm của phương pháp DFT là thích hợp với các loại đường biểu diễn dữ liệu khác nhau và giải thuật để biến đổi dữ liệu.

Tuy nhiên, nhược điểm lớn nhất của phương pháp là rất khó giải quyết nếu các chuỗi thời gian có chiều dài khác nhau, và phương pháp có độ phức tạp O(nlgn). Ký Ý nghĩa hiệu C một chuỗi thời gian C = c 1 , c 2 , …. c n C Chuỗi xấp xỉ gộp từng đoạn – PAA của chuỗi thời gian C = c1 , c2 … cw Chuỗi biểu diễn ký tự SAX của chuỗi thời gian S Chuỗi ESAX của chuỗi thời gian S = s11 , s21 , s31 , s12 , s22 , s32 ,., s1w , s2w , s3w w Số chiều thu giảm - Số đoạn trong chuỗi PAA của chuỗi thời gian a Kích thước tập ký tự dùng để biểu diễn SAX hay ESAX ( dùng {a,b,c}, thì a = 3). Các ký hiệu dùng trong luận văn .2 Phương pháp biến đổi wavelet rời rạc : Phương pháp thu giảm số chiều bằng biến đổi Wavelet rời rạc( Discrete Wavelet Transform) – DWT do K.

Phương pháp DWT cũng giống phương pháp DFT, tuy nhiên đường cơ bản của nó không phải là đường lượng giác sin hay cosin mà là đường Haar. Đường Haar được định nghĩa theo các công thức ψ ij như sau: Luận Văn Thạc Sĩ – Trần Công Thanh 11 Nhận dạng mô-típ trong dữ liệu chuỗi thời gian hình ảnh Chương 2: Các công trình liên quan ψ if ψ (2 j x − i ) = (2.5 < t < 1 0 các trường hợp khác Ngoài sử dụng đường Haar, phương pháp Wavelet có thể sử dụng các đường cơ bản khác như đường Daubechies, Coiflet, Symmlet…Tuy nhiên, Haar Wavalet đã được sử dụng nhiều trong khai phá dữ liệu chuỗi thời gian và lập chỉ mục. Phương pháp biến đổi Wavelet rời rạc rất hiệu quả bởi vì nó mã hoá đơn giản và nhanh. Độ phức tạp của việc mã hoá này là tuyến tính.

Một ưu điểm của phương pháp Wavelet là nó hỗ trợ nhiều mức phân giải. Tuy nhiên nhược điểm là chiều dài chuỗi dữ liệu ban đầu của nó phải là một số lũy thừa hai và chiều dài của chuỗi con truy vấn cũng nên là số lũy thừa của hai thì giải thuật mới thực hiện hiệu quả. Các kỹ thuật xấp xỉ tuyến tính từng đoạn : Phương pháp xấp xỉ tuyến tính từng đoạn - PLA: Phương pháp xấp xỉ gộp từng đoạn – PLA (Piecewise Linear Approximation) do E. Keogh và cộng sự đề nghị năm 2001[10][11].

Phương pháp này rất đơn giản, các tác giả tuần tự xấp xỉ k giá trị liền kề nhau thành một đoạn thẳng tuyến tính. Quá trình cứ tiếp tục như vậy từ trái sang phải. Kết quả cuối cùng là đoạn thẳng có thể liên tục hoặc rời nhau. Ưu điểm của cách biểu diễn này là thời gian tính toán tuyến tính, trực quan và cách biểu diễn của nó hỗ trợ nhiều độ đo khoảng cách.

Nhược điểm lớn nhất là chưa có cách lập chỉ mục hiệu quả cho cách biểu diễn này. Luận Văn Thạc Sĩ – Trần Công Thanh 12 Nhận dạng mô-típ trong dữ liệu chuỗi thời gian hình ảnh Chương 2: Các công trình liên quan Kỹ thuật xấp xỉ gộp từng đoạn - PAA: Keogh và các cộng sự, 2000 [8] đã đề nghị kỹ thuật thu giảm chiều là kỹ thuật xấp xỉ gộp từng đoạn - PAA ( Piecewise Aggregate Approximation). Cho chuỗi thời gian C = c 1 , c 2 , …. c n có chiều dài n được chuyển vào không gian w chiều ( 1≤ w ≤ n) thành vector C = c1 , c2 … cw thành phần thứ i sẽ được tính theo công thức sau: ni w w ci = ∑ cj n j= n ( i −1)+1 (2.3) w Thành phần thứ i của vector C là trung bình cộng của k phần tử liên tiếp từ phần tử thứ (k ( i - 1) + 1)  ki của chuỗi thời gian C với tỉ số nén k = n w Nếu w bằng n thì chuỗi PAA bằng đúng chuỗi chuỗi thời gian gốc, nếu w bằng 1 thì chuỗi biểu diễn PAA chỉ còn là một giá trị trung bình cộng của chuỗi thời gian gốc.

Cho một chuỗi thời gian có tám phần tử muốn thu giảm về hai phần tử như hình 2. Chuỗi thời gian X = (-1,-2,-1,0,2,1,1,0) n =|X| =8 2 2 Tính PAA: X = ( ( (−1 + −2 + −1 + 0) ),( (2 + 1 + 1 + 0) )) w = X =2 8 8 X =(-1,1) Biểu diễn PAA của chuỗi thời gian có thể trực quan hoá là sự kết tuyến tính của các hàm vuông như hình 2.