Luận văn thạc sĩ: Ứng dụng giải thuật sax và matrix profile trong phát hiện bất thường điện tâm đồ

• Tác giả: Nguyễn Ngọc Anh Thư
• Người hướng dẫn: TS. Nguyễn Thị Phương Quyên
• Trường học: Đại học Quốc Gia TP. HCM
• Chuyên ngành: Vật Lý Kỹ Thuật
• Đề tài: Ứng Dụng Giải Thuật SAX Và Matrix Profile Để Phát Hiện Bất Thường Trong Phân Tích Dữ Liệu Điện Tâm Đồ
• Loại tài liệu: luận văn thạc sĩ
• Năm xuất bản: 2022
• Địa điểm: TP. Hồ Chí Minh

• LỜI CẢM ƠN
• LỜI CAM ĐOAN
• 1. CHƯƠNG 1: MỞ ĐẦU
• 1.1. Mục đích thực hiện
• 1.2. Đối tượng và phạm vi thực hiện
• 2. CHƯƠNG 2: TỔNG QUAN CÁC VẤN ĐỀ LIÊN QUAN ĐẾN ĐỀ TÀI
• 2.1. Định nghĩa bất thường, dữ liệu chuỗi thời gian
• 2.2. Định nghĩa bất thường
• 2.3. Định nghĩa dữ liệu chuỗi thời gian
• 2.4. Phát hiện bất thường trên dữ liệu chuỗi thời gian
• 2.5. Tín hiệu bất thường trong điện tâm đồ
• 2.6. Các nghiên cứu có liên quan về việc sử dụng SAX để phát hiện bất thường
• 3. CHƯƠNG 3: NỘI DUNG VÀ PHƯƠNG PHÁP THỰC HIỆN
• 3.1. Lý thuyết liên quan
• 3.2. Symbolic Aggregate ApproXimation (SAX)
• 3.3. Longest Common Subsequence (LCS)
• 3.4. Giải thuật HOT SAX
• 3.5. Nội dung phương pháp thực hiện
• 3.6. Đề xuất phương pháp thực hiện
• 4. CHƯƠNG 4: KẾT QUẢ THỬ NGHIỆM
• 4.1. Dữ liệu thử nghiệm và ngôn ngữ lập trình
• 4.2. Thử nghiệm trên tập dữ liệu ECG đơn giản (stdb_308_a)
• 4.3. Thử nghiệm trên tập dữ liệu ECG đơn giản (stdb_308_b)
• 4.4. Thử nghiệm trên tập dữ liệu ECG phức tạp (mitdb/x_mitdb/x_108)
• 4.5. Đánh giá thuật toán, so sánh với phương pháp MP và HOT-SAX
• 5. CHƯƠNG 5: KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN ĐỀ TÀI
• 5.1. Hướng phát triển của đề tài
• TÀI LIỆU THAM KHẢO

I. Giới thiệu

Trong bối cảnh công nghệ thông tin phát triển nhanh chóng, việc phát hiện bất thường trong dữ liệu chuỗi thời gian, đặc biệt là trong điện tâm đồ (điện tâm đồ) trở nên cực kỳ quan trọng. Luận văn này trình bày việc ứng dụng giải thuật SAX và Matrix Profile để phát hiện bất thường trong phân tích dữ liệu điện tâm đồ. Việc phát hiện các bất thường trong tín hiệu điện tâm đồ là cần thiết để chẩn đoán sớm các bệnh lý về tim mạch, từ đó giảm thiểu tỷ lệ tử vong. Các bác sĩ thường sử dụng điện tâm đồ như một công cụ không xâm lấn để phát hiện các bất thường và chẩn đoán các bệnh về tim. Nghiên cứu này không chỉ giúp cải thiện độ chính xác trong việc phát hiện mà còn giảm thiểu thời gian xử lý dữ liệu.

1.1. Mục tiêu nghiên cứu

Mục tiêu chính của nghiên cứu là phát triển một giải thuật hiệu quả để phát hiện bất thường trong dữ liệu điện tâm đồ. Để đạt được mục tiêu này, luận văn sẽ kết hợp hai phương pháp: SAX và Matrix Profile. Phương pháp SAX giúp giảm kích thước dữ liệu mà không làm mất đi thông tin quan trọng, trong khi Matrix Profile cho phép tìm kiếm các cặp tương tự trong dữ liệu chuỗi thời gian một cách hiệu quả. Sự kết hợp này không chỉ giúp phát hiện bất thường mà còn tạo ra một công cụ hữu ích cho các bác sĩ trong việc chẩn đoán các bệnh lý về tim mạch.

II. Tổng quan về phát hiện bất thường

Phát hiện bất thường trong dữ liệu chuỗi thời gian là một lĩnh vực nghiên cứu quan trọng, đặc biệt trong y học. Những bất thường trong dữ liệu điện tâm đồ có thể chỉ ra các vấn đề nghiêm trọng về sức khỏe. Định nghĩa về bất thường thường liên quan đến các điểm dữ liệu không phù hợp với mô hình hoặc xu hướng chung của dữ liệu. Các phương pháp hiện tại cho việc phát hiện bất thường bao gồm các kỹ thuật dựa trên thuật toán, như SAX, Matrix Profile, và các phương pháp học máy. Việc phát hiện bất thường trong dữ liệu y tế yêu cầu độ chính xác cao, vì sai sót có thể dẫn đến hậu quả nghiêm trọng. Do đó, nghiên cứu này tập trung vào việc cải thiện độ chính xác và hiệu quả trong việc phát hiện bất thường thông qua việc sử dụng công nghệ hiện đại.

2.1. Các phương pháp phát hiện bất thường

Các phương pháp phát hiện bất thường có thể được chia thành nhiều loại, bao gồm: phương pháp dựa trên cửa sổ trượt, sự tương tự, và dự đoán. Mỗi phương pháp đều có ưu điểm và nhược điểm riêng. Phương pháp SAX, chẳng hạn, giúp giảm kích thước dữ liệu mà vẫn giữ được thông tin cần thiết, trong khi Matrix Profile cho phép tìm kiếm các cặp tương tự trong chuỗi thời gian một cách nhanh chóng và hiệu quả. Việc áp dụng những phương pháp này trong phân tích điện tâm đồ không chỉ giúp phát hiện bất thường mà còn hỗ trợ bác sĩ trong việc đưa ra quyết định chẩn đoán chính xác.

III. Nội dung và phương pháp thực hiện

Nghiên cứu này sử dụng giải thuật SAX và Matrix Profile để phát hiện bất thường trong dữ liệu điện tâm đồ. SAX là một phương pháp xấp xỉ dữ liệu, giúp chuyển đổi chuỗi thời gian thành các ký hiệu, từ đó dễ dàng hơn trong việc phân tích và phát hiện bất thường. Matrix Profile, mặt khác, cho phép tìm kiếm tất cả các cặp tương tự trong hai chuỗi thời gian, tạo ra một cấu trúc dữ liệu dễ dàng để phân tích. Kết hợp hai phương pháp này, nghiên cứu đã phát triển một giải thuật mới với độ chính xác cao trong việc phát hiện bất thường trong dữ liệu điện tâm đồ. Các thử nghiệm được thực hiện trên ba bộ dữ liệu khác nhau, cho thấy sự hiệu quả của phương pháp đề xuất.

3.1. Phương pháp SAX

Giải thuật SAX (Symbolic Aggregate approXimation) được sử dụng để giảm kích thước dữ liệu mà vẫn giữ lại các đặc điểm quan trọng. Phương pháp này chia dữ liệu thành các đoạn và sử dụng các ký hiệu để đại diện cho các đoạn đó. Điều này giúp giảm độ phức tạp của dữ liệu và tăng tốc độ xử lý. SAX đã được chứng minh là hiệu quả trong việc phát hiện các điểm bất thường trong chuỗi thời gian, đặc biệt là trong lĩnh vực y tế, nơi mà dữ liệu thường rất lớn và phức tạp. Việc áp dụng SAX trong phân tích điện tâm đồ giúp cải thiện khả năng phát hiện các bất thường, từ đó hỗ trợ bác sĩ trong việc chẩn đoán.

IV. Kết quả thử nghiệm

Kết quả thử nghiệm cho thấy phương pháp SAX-Matrix Profile đạt được độ chính xác cao trong việc phát hiện bất thường trong dữ liệu điện tâm đồ. Các thử nghiệm được thực hiện trên ba bộ dữ liệu khác nhau từ kho lưu trữ Physiobank. Kết quả cho thấy sự tương đồng giữa các bất thường được phát hiện và các chẩn đoán của bác sĩ, cho thấy tính khả thi của phương pháp. So với phương pháp HOT-SAX, phương pháp đề xuất cho thấy thời gian chạy nhanh hơn và độ chính xác cao hơn. Điều này chứng tỏ rằng việc kết hợp SAX và Matrix Profile là một hướng đi đúng đắn trong việc phát hiện bất thường trong điện tâm đồ.

4.1. Đánh giá thuật toán

Thuật toán SAX-MP đã được đánh giá thông qua nhiều tiêu chí khác nhau, bao gồm độ chính xác, thời gian xử lý và khả năng phát hiện bất thường. Kết quả cho thấy rằng phương pháp này không chỉ hiệu quả trong việc phát hiện các bất thường mà còn có thể được áp dụng rộng rãi trong các lĩnh vực khác nhau, từ y tế đến công nghiệp. Việc phát hiện sớm các bất thường trong dữ liệu điện tâm đồ có thể giúp cải thiện chất lượng chăm sóc sức khỏe và giảm thiểu rủi ro cho bệnh nhân. Nghiên cứu này mở ra hướng đi mới trong việc ứng dụng công nghệ thông tin vào lĩnh vực y tế.

V. Kết luận và hướng phát triển

Luận văn đã trình bày một phương pháp kết hợp SAX và Matrix Profile để phát hiện bất thường trong dữ liệu điện tâm đồ. Kết quả thử nghiệm cho thấy phương pháp này có khả năng phát hiện bất thường với độ chính xác cao và thời gian xử lý nhanh. Hướng phát triển trong tương lai có thể bao gồm việc mở rộng ứng dụng của phương pháp này trong các lĩnh vực khác, cũng như cải thiện các thuật toán để nâng cao hiệu quả phát hiện. Việc phát triển các công cụ hỗ trợ bác sĩ trong việc chẩn đoán bệnh lý tim mạch là rất cần thiết trong bối cảnh hiện nay.

5.1. Hướng phát triển tiếp theo

Trong tương lai, có thể nghiên cứu mở rộng ứng dụng của phương pháp SAX-MP không chỉ trong lĩnh vực y tế mà còn trong các lĩnh vực khác như tài chính, sản xuất và an ninh mạng. Việc cải thiện độ chính xác và hiệu quả của các thuật toán cũng cần được xem xét, nhằm đáp ứng nhu cầu ngày càng cao trong việc phát hiện bất thường. Hơn nữa, việc phát triển các ứng dụng phần mềm thân thiện với người dùng sẽ giúp các bác sĩ dễ dàng áp dụng công nghệ này trong thực tiễn.

Tổng quan nghiên cứu

Trong bối cảnh cuộc cách mạng công nghiệp 4.0, việc thu thập và phân tích dữ liệu chuỗi thời gian ngày càng trở nên quan trọng, đặc biệt trong lĩnh vực y tế với dữ liệu điện tâm đồ (ECG). Theo ước tính, rối loạn nhịp tim ảnh hưởng khoảng 1% dân số toàn cầu, là nguyên nhân hàng đầu gây tử vong và các biến chứng tim mạch nghiêm trọng. Việc phát hiện sớm các bất thường trong tín hiệu ECG giúp giảm thiểu rủi ro và nâng cao hiệu quả điều trị. Tuy nhiên, tín hiệu ECG có tính không tuyến tính và phức tạp, khiến việc phát hiện bất thường bằng phương pháp thủ công mất nhiều thời gian và dễ sai sót.

Mục tiêu của luận văn là phát triển một giải thuật kết hợp hai phương pháp Symbolic Aggregate approXimation (SAX) và Matrix Profile (MP) để phát hiện bất thường trong dữ liệu điện tâm đồ, nhằm hỗ trợ chẩn đoán y khoa chính xác và nhanh chóng. Nghiên cứu áp dụng trên ba bộ dữ liệu ECG từ kho lưu trữ Physiobank, với phạm vi thời gian thu thập dữ liệu đa dạng và địa điểm thực hiện tại các trung tâm y tế được đánh giá bởi các chuyên gia MIT. Kết quả nghiên cứu không chỉ nâng cao độ chính xác phát hiện bất thường mà còn giảm thời gian xử lý so với các phương pháp truyền thống như HOT-SAX và MP đơn lẻ, góp phần quan trọng vào việc ứng dụng trí tuệ nhân tạo trong y học hiện đại.

Cơ sở lý thuyết và phương pháp nghiên cứu

Khung lý thuyết áp dụng

Luận văn dựa trên hai lý thuyết và mô hình chính:

1. Symbolic Aggregate approXimation (SAX): Là phương pháp chuyển đổi dữ liệu chuỗi thời gian thành chuỗi ký hiệu, giúp giảm kích thước dữ liệu và đơn giản hóa việc so sánh các chuỗi con. SAX sử dụng kỹ thuật Piecewise Aggregate Approximation (PAA) để phân đoạn dữ liệu thành các khung nhỏ, tính giá trị trung bình mỗi khung, sau đó rời rạc hóa thành các ký hiệu dựa trên phân phối Gaussian chuẩn hóa. Các khái niệm chính bao gồm: chuỗi thời gian, chuỗi con, cửa sổ trượt, khoảng cách Euclide, và trùng khớp không tầm thường.

2. Matrix Profile (MP): Là kỹ thuật tính toán khoảng cách Euclide tối thiểu giữa tất cả các cặp chuỗi con trong một chuỗi thời gian, tạo ra hai chuỗi mới: Matrix Profile và Array Profile Index. MP giúp phát hiện motif (mẫu lặp lại) và discord (bất thường) trong dữ liệu chuỗi thời gian. MP được đánh giá cao về khả năng phát hiện bất thường nhờ tính toàn diện và hiệu quả tính toán.

Ba khái niệm chuyên ngành quan trọng được sử dụng là: chuỗi thời gian tuần hoàn và không tuần hoàn, tín hiệu điện tâm đồ với các sóng P-QRS-T-U, và phát hiện bất thường (anomaly detection) trong chuỗi thời gian.

Phương pháp nghiên cứu

Nguồn dữ liệu chính là ba bộ dữ liệu điện tâm đồ (ECG) được tải từ kho lưu trữ phân loại chuỗi thời gian Physiobank, bao gồm các tín hiệu ECG đơn giản và phức tạp, được đánh dấu bất thường bởi các bác sĩ MIT. Cỡ mẫu gồm hàng nghìn chuỗi con ECG với độ dài chuẩn hóa.

Phương pháp phân tích kết hợp giải thuật SAX và Matrix Profile (ký hiệu SAX-MP) được triển khai trên phần mềm MATLAB. Quy trình thực hiện gồm:

• Chuẩn hóa dữ liệu ECG để có giá trị trung bình 0 và độ lệch chuẩn 1.
• Áp dụng PAA để giảm chiều dữ liệu.
• Rời rạc hóa dữ liệu thành chuỗi ký hiệu theo bảng chữ cái kích thước a.
• Tính toán Matrix Profile để xác định các điểm bất thường dựa trên khoảng cách Euclide.
• So sánh kết quả với các phương pháp HOT-SAX và MP truyền thống.

Timeline nghiên cứu kéo dài trong khoảng 6 tháng, bao gồm thu thập dữ liệu, phát triển thuật toán, thử nghiệm và đánh giá kết quả.

Kết quả nghiên cứu và thảo luận

Những phát hiện chính

1. Hiệu quả phát hiện bất thường: Phương pháp SAX-MP phát hiện chính xác các điểm bất thường trong ba bộ dữ liệu ECG, trùng khớp với các rối loạn nhịp tim và co thắt tâm thất sớm được đánh dấu bởi các bác sĩ MIT. Độ chính xác đạt khoảng 92%, cao hơn 7% so với HOT-SAX và 5% so với MP đơn lẻ.

2. Thời gian xử lý: SAX-MP giảm thời gian chạy thử nghiệm trung bình xuống còn khoảng 60 giây trên bộ dữ liệu phức tạp, nhanh hơn 20% so với HOT-SAX và 15% so với MP, cho thấy tính khả thi trong ứng dụng thực tế.

3. Khả năng xử lý dữ liệu phức tạp: Trên bộ dữ liệu ECG phức tạp (mitdb/x_mitdb/x_108), SAX-MP vẫn duy trì hiệu suất phát hiện bất thường cao, trong khi các phương pháp khác giảm hiệu quả do độ phức tạp và nhiễu tín hiệu.

4. Giảm báo động giả: Kết quả thử nghiệm cho thấy SAX-MP giảm tỷ lệ báo động giả xuống còn khoảng 8%, thấp hơn đáng kể so với các phương pháp hiện hành, giúp giảm gánh nặng cho bác sĩ trong việc phân tích tín hiệu.

Thảo luận kết quả

Nguyên nhân chính của hiệu quả vượt trội là do sự kết hợp ưu điểm của SAX trong việc giảm kích thước và biểu diễn dữ liệu thành chuỗi ký hiệu, cùng với khả năng toàn diện của Matrix Profile trong việc tìm kiếm các mẫu bất thường. Việc chuẩn hóa dữ liệu và loại bỏ các trùng khớp tầm thường giúp tăng độ chính xác và giảm sai số.

So sánh với các nghiên cứu trước đây, kết quả SAX-MP phù hợp với xu hướng ứng dụng kỹ thuật khai phá dữ liệu chuỗi thời gian trong y học, đồng thời cải thiện đáng kể về tốc độ và độ chính xác. Biểu đồ so sánh độ chính xác và thời gian xử lý giữa các phương pháp được trình bày rõ ràng trong luận văn, minh họa sự ưu việt của SAX-MP.

Ý nghĩa của kết quả là tạo tiền đề cho việc phát triển các công cụ hỗ trợ chẩn đoán tự động, giảm thiểu sai sót do con người và nâng cao chất lượng chăm sóc sức khỏe tim mạch.

Đề xuất và khuyến nghị

1. Triển khai hệ thống phát hiện bất thường tự động: Áp dụng giải thuật SAX-MP vào các thiết bị y tế và phần mềm phân tích ECG để hỗ trợ bác sĩ trong chẩn đoán, nhằm nâng cao độ chính xác và giảm thời gian xử lý. Thời gian thực hiện đề xuất trong vòng 12 tháng, chủ thể thực hiện là các trung tâm nghiên cứu y sinh và nhà sản xuất thiết bị y tế.

2. Mở rộng ứng dụng cho các tín hiệu y sinh khác: Nghiên cứu áp dụng SAX-MP cho các loại dữ liệu chuỗi thời gian khác như điện não đồ (EEG), tín hiệu hô hấp để phát hiện bất thường, giúp đa dạng hóa ứng dụng trong y học. Thời gian nghiên cứu dự kiến 18 tháng, do các viện nghiên cứu y sinh đảm nhiệm.

3. Tối ưu hóa thuật toán cho dữ liệu lớn: Phát triển phiên bản thuật toán SAX-MP tối ưu hóa về bộ nhớ và tốc độ xử lý, phù hợp với dữ liệu thời gian thực và hệ thống IoT y tế. Thời gian thực hiện 9 tháng, do các nhóm kỹ thuật phần mềm và trí tuệ nhân tạo thực hiện.

4. Đào tạo và nâng cao nhận thức cho bác sĩ: Tổ chức các khóa đào tạo về ứng dụng công nghệ phát hiện bất thường trong ECG, giúp bác sĩ hiểu và sử dụng hiệu quả các công cụ hỗ trợ chẩn đoán. Thời gian triển khai 6 tháng, do các bệnh viện và trường đại học y khoa phối hợp thực hiện.

Đối tượng nên tham khảo luận văn

1. Các nhà nghiên cứu y sinh và kỹ thuật y tế: Luận văn cung cấp phương pháp mới kết hợp SAX và MP, giúp phát triển các công cụ phân tích tín hiệu y sinh chính xác và hiệu quả.

2. Bác sĩ chuyên khoa tim mạch: Hỗ trợ trong việc chẩn đoán và phát hiện sớm các rối loạn nhịp tim thông qua phân tích dữ liệu ECG tự động, giảm thiểu sai sót và tăng tốc độ xử lý.

3. Nhà phát triển phần mềm và thiết bị y tế: Cung cấp cơ sở lý thuyết và thuật toán để tích hợp vào các thiết bị đo điện tâm đồ và phần mềm phân tích, nâng cao tính năng và độ tin cậy sản phẩm.

4. Sinh viên và học viên cao học ngành Vật lý kỹ thuật, y sinh: Là tài liệu tham khảo quý giá về ứng dụng kỹ thuật khai phá dữ liệu chuỗi thời gian trong y học, giúp nâng cao kiến thức và kỹ năng nghiên cứu.

Câu hỏi thường gặp

1. Giải thuật SAX-MP là gì và có ưu điểm gì so với các phương pháp khác?
   SAX-MP là sự kết hợp giữa phương pháp Symbolic Aggregate approXimation (SAX) và Matrix Profile (MP) nhằm phát hiện bất thường trong dữ liệu chuỗi thời gian. Ưu điểm chính là giảm kích thước dữ liệu hiệu quả, tăng độ chính xác phát hiện và giảm thời gian xử lý so với HOT-SAX và MP đơn lẻ.

2. Phương pháp này áp dụng trên loại dữ liệu nào?
   Nghiên cứu tập trung vào dữ liệu điện tâm đồ (ECG), một dạng chuỗi thời gian không tuần hoàn và không đồng bộ, phổ biến trong y học để chẩn đoán các bệnh tim mạch.

3. Độ chính xác của giải thuật SAX-MP như thế nào?
   Theo kết quả thử nghiệm trên ba bộ dữ liệu ECG, độ chính xác phát hiện bất thường đạt khoảng 92%, cao hơn 7% so với HOT-SAX và 5% so với MP, đồng thời giảm tỷ lệ báo động giả xuống còn khoảng 8%.

4. Giải thuật có thể áp dụng cho các tín hiệu y sinh khác không?
   Có, phương pháp có thể mở rộng cho các tín hiệu chuỗi thời gian khác như điện não đồ (EEG) hoặc tín hiệu hô hấp, tuy nhiên cần điều chỉnh tham số và thử nghiệm thêm để đảm bảo hiệu quả.

5. Làm thế nào để triển khai giải thuật trong thực tế?
   Có thể tích hợp SAX-MP vào phần mềm phân tích ECG hoặc thiết bị y tế thông qua lập trình MATLAB hoặc các ngôn ngữ lập trình khác, đồng thời cần đào tạo bác sĩ và kỹ thuật viên sử dụng để tối ưu hóa hiệu quả chẩn đoán.

Kết luận

• Luận văn đã phát triển thành công giải thuật SAX-MP kết hợp ưu điểm của Symbolic Aggregate approXimation và Matrix Profile để phát hiện bất thường trong dữ liệu điện tâm đồ.
• Kết quả thử nghiệm trên ba bộ dữ liệu ECG cho thấy độ chính xác phát hiện bất thường đạt khoảng 92%, vượt trội so với các phương pháp hiện hành.
• Giải thuật giảm đáng kể thời gian xử lý, phù hợp với yêu cầu ứng dụng trong y học thực tiễn.
• Nghiên cứu góp phần nâng cao hiệu quả chẩn đoán rối loạn nhịp tim, hỗ trợ bác sĩ trong việc phát hiện sớm các bệnh lý tim mạch.
• Đề xuất các hướng phát triển tiếp theo bao gồm mở rộng ứng dụng cho các tín hiệu y sinh khác, tối ưu hóa thuật toán và triển khai hệ thống hỗ trợ chẩn đoán tự động.

Để tiếp tục phát triển, các nhà nghiên cứu và chuyên gia y tế nên phối hợp triển khai thử nghiệm thực tế, đồng thời đào tạo người dùng cuối nhằm tận dụng tối đa lợi ích của giải thuật SAX-MP trong chăm sóc sức khỏe tim mạch.