Bối cảnh và vấn đề nghiên cứu

Trong bối cảnh bùng nổ thông tin hiện nay, khối lượng dữ liệu khổng lồ được tạo ra mỗi giây trên môi trường Internet đóng vai trò quyết định đến chiến lược và hoạt động của các tổ chức, doanh nghiệp. Tuy nhiên, dữ liệu thu thập từ nhiều nguồn dị nguyên thường chứa nhiều sai lệch, trùng lặp, nhiễu hoặc không nhất quán. Việc trích xuất tri thức từ dữ liệu "bẩn" sẽ dẫn đến các kết quả dự báo sai lầm. Do đó, làm sạch dữ liệu (Data Cleansing) và phát hiện các điểm dữ liệu bất thường (Anomaly Detection) là bước tiền xử lý bắt buộc trước khi tiến hành phân tích chuyên sâu.

Đề tài khóa luận tốt nghiệp "OPENK: DATA CLEANSING SYSTEM – A CLUSTERING-BASED APPROACH FOR DETECTING DATA ANOMALIES" được thực hiện bởi sinh viên Nguyễn Đình Khương (MSSV: 1752306, Lớp KHM2, Khoa Khoa học và Kỹ thuật Máy tính, Trường Đại học Bách Khoa – ĐHQG TP.HCM) dưới sự hướng dẫn của PGS. Đặng Trần Khánh, nhằm giải quyết các nhiệm vụ và mục tiêu nghiên cứu cụ thể:

  1. Khảo sát yêu cầu, phân tích, thiết kế và hiện thực hóa hệ thống làm sạch dữ liệu hoạt động trên nền tảng ứng dụng web (Web App Platform).
  2. Nghiên cứu các thuật toán đo độ tương đồng chuỗi dựa trên phép biến đổi (Edit-based similarity) kết hợp các phương pháp phân cụm (Clustering methods), thiết kế giải pháp phát hiện và gom cụm các dị biệt dữ liệu.
  3. Nghiên cứu, đánh giá và đối sánh với các hệ thống làm sạch dữ liệu liên quan gồm OpenRefine (Google Refine), BigDansing, NADEEF và công cụ xác thực dữ liệu Cerberus.
  4. Ứng dụng các thuật toán phân cụm cụ thể: K-láng giềng gần nhất - K-NN (Levenshtein Distance, Damerau-Levenshtein Distance, Hamming Distance), độ đo tương đồng Similarity (Jaro, Jaro-Winkler Similarity) và va chạm khóa - Key Collision (Fingerprint, N-gram Fingerprint).
  5. Xây dựng thư viện API phục vụ cộng đồng lập trình viên và tích hợp cơ chế trực quan hóa dữ liệu (Visualization) cho người dùng.
  6. Thử nghiệm và đánh giá hiệu năng hệ thống trên các tập dữ liệu thực nghiệm.

Phạm vi nghiên cứu của đề tài được triển khai từ ngày 02/02/2021 đến ngày 26/07/2021, tập trung vào việc phát hiện và xử lý bất thường dữ liệu dạng văn bản (textual data anomalies) ở cấp độ cú pháp trên hai bộ dữ liệu kiểm thử: tập dữ liệu hàng không (Airlines dataset) và tập dữ liệu bất động sản thu thập từ trang batdongsan.com.vn.

Cơ sở lý thuyết và phương pháp

Khóa luận xây dựng nền tảng lý thuyết dựa trên các nghiên cứu về phát hiện bất thường dữ liệu và các kỹ thuật đo độ tương đồng chuỗi phục vụ phân cụm:

1. Khái niệm phát hiện bất thường dữ liệu (Data Anomalies Detection)

Phát hiện bất thường (hay phát hiện ngoại lai - outlier detection) là quá trình nhận diện các quan sát hiếm gặp, có sai khác đáng kể so với phần lớn dữ liệu còn lại. Các phương pháp phát hiện bất thường truyền thống gồm:

  • Học không giám sát (Unsupervised), có giám sát (Supervised) và bán giám sát (Semi-supervised).
  • Các mô hình liên quan: One-class SVM, mờ (Fuzzy logic), luật kết hợp (Association rules), Hidden Markov Models (HMMs), Autoencoders / Variational Autoencoders, và mạng LSTM.
  • Trong khóa luận này, tác giả tập trung vào phương pháp tiếp cận không giám sát dựa trên phân cụm (Clustering-based approach) để gom nhóm các chuỗi văn bản tương đồng nhưng có lỗi chính tả, khác biệt dấu câu hoặc định dạng.

2. Các nhóm thuật toán phân cụm chuỗi

Khóa luận phân loại và ứng dụng ba nhóm phương pháp phân cụm chính:

Nhóm phương pháp Thuật toán / Độ đo Cơ chế hoạt động & Công thức cốt lõi
Key Collision (Va chạm khóa) Fingerprint Chuẩn hóa chuỗi qua 7 bước tuần tự: xóa khoảng trắng đầu/cuối $\rightarrow$ chuyển chữ thường $\rightarrow$ xóa dấu câu và ký tự điều khiển $\rightarrow$ chuẩn hóa ký tự Latin mở rộng về ASCII $\rightarrow$ tách từ $\rightarrow$ sắp xếp và lọc trùng token $\rightarrow$ ghép lại thành khóa đại diện.
N-gram Fingerprint Chuyển chữ thường $\rightarrow$ xóa dấu câu, khoảng trắng $\rightarrow$ trích xuất các n-gram có độ dài $n$ (mặc định $n=1$ hoặc $n=2$) $\rightarrow$ chuẩn hóa ASCII $\rightarrow$ sắp xếp, loại trùng $\rightarrow$ ghép lại thành chuỗi khóa.
K-Nearest Neighbors (kNN) Hamming Distance Đo số lượng vị trí khác biệt giữa hai chuỗi có cùng chiều dài: tính toán số phép thay thế tối thiểu. Độ phức tạp thời gian trung bình: $\mathcal{O}(n)$.
Levenshtein Distance Tính số thao tác tối thiểu (chèn, xóa, thay thế) để biến đổi chuỗi $a$ thành chuỗi $b$. Ma trận tính toán $Lev[n+1, m+1]$ với độ phức tạp $\mathcal{O}(m \times n)$.
Damerau-Levenshtein Mở rộng từ Levenshtein Distance bằng cách bổ sung thêm thao tác hoán vị (transposition) giữa hai ký tự liền kề.
Similarity Measurement Jaro Similarity Đo độ tương đồng giữa hai chuỗi dựa trên số lượng ký tự trùng khớp $m$ trong phạm vi cho phép và số lượng phép hoán vị $t$: $sim_j = \frac{1}{3}\left(\frac{m}{|s_1|} + \frac{m}{|s_2|} + \frac{m-t}{m}\right)$.
Jaro-Winkler Similarity Bổ sung trọng số ưu tiên cho tiền tố chung độ dài $l$ ($l \le 4$), hệ số tỉ lệ chuẩn $p = 0.1$: $sim_w = sim_j + lp(1 - sim_j)$. Khoảng giá trị $[0, 1]$, trong đó 1 là trùng khớp hoàn toàn. Khoảng cách Jaro-Winkler được xác định bởi $d_w = 1 - sim_w$.

3. Phương pháp nghiên cứu thực nghiệm

  • Thiết kế và xây dựng hệ thống phần mềm: Lập trình hướng đối tượng, kiến trúc phân lớp xử lý luồng dữ liệu (Pipeline Architecture).
  • Phân tích đối sánh: So sánh kiến trúc và quy trình xử lý với các hệ thống BigDansing (sử dụng UDF Detect/GenFix trên môi trường phân tán), NADEEF (biên dịch luật đa hình và sửa lỗi toàn diện) và OpenRefine (làm sạch dữ liệu tương tác).

Thiết kế và triển khai hệ thống OpenK

Hệ thống OpenK được thiết kế và triển khai dưới dạng ứng dụng web hoàn chỉnh, cho phép người dùng thao tác trực tiếp với dữ liệu cục bộ và dữ liệu đám mây.

1. Kiến trúc hệ thống và các thành phần chính

Kiến trúc tổng thể của OpenK bao gồm ba khối chức năng chính:

  • Bộ chuyển đổi định dạng (Format Converter): Nhận dữ liệu đầu vào không đồng nhất ở các định dạng CSV, TSV, JSON, XLSX hoặc từ đường dẫn URL, thực hiện chuyển đổi qua lại giữa các định dạng để phục vụ xử lý tiếp theo.
  • Thành phần làm sạch dữ liệu (Data Cleanser): Nạp dữ liệu vào bảng hiển thị (Table Viewer) thông qua cấu trúc DataFrame, hỗ trợ các thao tác quản trị dữ liệu: CRUD (Create, Read, Update, Delete), lọc từ khóa (Text filter / Trim table), sắp xếp cột (Column Sorter) theo bảng chữ cái hoặc giá trị số, phân trang (Paging) và phân tách dữ liệu (Faceting).
  • Toán tử phân cụm (Clustering Operator): Khối xử lý trung tâm chứa các thuật toán Key Collision, kNN và Similarity. Cho phép gom nhóm các dị biệt và hiển thị các nút gộp (Merged nodes) để người dùng xác nhận thay đổi.
Luồng xử lý dữ liệu:
                                                    [Clustering Operator]
                                                    (kNN / Similarity / Key Collision)

2. Công nghệ và môi trường triển khai

  • Ngôn ngữ & Nền tảng: Python, môi trường Windows.
  • Backend Framework: Flask (chạy cục bộ tại localhost:5000), định tuyến WSGI và cung cấp API library.
  • Template Engine: Jinja (truyền và hiển thị biến dữ liệu từ Flask sang giao diện người dùng).
  • Frontend: HTML, CSS, JavaScript (xây dựng giao diện bảng tương tác, điều hướng, ẩn/hiện cột, thanh công cụ).
  • Xử lý dữ liệu: Thư viện Pandas (sử dụng cấu trúc DataFrame để thao tác và làm sạch bảng dữ liệu lớn), NumPy (hỗ trợ tính toán ma trận và mảng đa chiều).
  • Kết nối cơ sở dữ liệu: Hỗ trợ nạp tệp cục bộ và kết nối trực tiếp đến hệ cơ sở dữ liệu đám mây Azure Cosmos DB.

3. Cấu trúc mã nguồn và Hiện thực hóa hàm

Mã nguồn hệ thống tập trung tại các tệp chính: app.py, clustering.py và các mẫu giao diện data.html, convert.html, index.html.

  • Hệ thống định tuyến (Routing System) trong app.py:

    • route("/"): Điều hướng về trang chủ index.html.
    • route("/convert", methods=['GET', 'POST']): Tiếp nhận tệp tải lên và chuyển đổi định dạng.
    • route("/upload", methods=['GET', 'POST']): Giao diện tải tệp từ máy tính hoặc nhập khóa kết nối cơ sở dữ liệu Azure Cosmos DB.
    • route("/data", methods=['GET', 'POST']): Hiển thị bảng dữ liệu data.html, thực thi các thao tác lọc, sắp xếp, phân trang và kích hoạt phân cụm.

  • Các lớp xử lý thuật toán trong clustering.py:

    • Lớp KNN: Hàm khởi tạo __init__(self, group, radius) nhận nhóm dữ liệu và bán kính khoảng cách $k$. Cung cấp 3 phương thức: levenshtein(self), damerau(self) và hamming(self). Vòng lặp duyệt qua các phần tử duy nhất, tính khoảng cách giữa từng cặp chuỗi và gom vào cụm nếu khoảng cách $\le radius$.
    • Lớp Similarity: Hàm khởi tạo __init__(self, group, threshold) nhận ngưỡng tương đồng từ 0 đến 1. Gồm 5 phương thức: jaro(self), jaro_winkler(self), levenshtein_sim(self), damerau_sim(self) và number_sim(self). Các cặp chuỗi có độ tương đồng $\ge threshold$ sẽ được đưa vào cùng cụm.
    • Lớp Fingerprinter: Hàm khởi tạo __init__(self, string) xử lý tiền xử lý chuỗi: thay thế dấu câu bằng khoảng trắng, chuyển mã UTF-8 Latinh hóa và tạo khóa đại diện qua thuật toán Fingerprint hoặc N-gram Fingerprint (tham số $n$ mặc định bằng 1).

Nội dung chính theo từng chương

Chapter 1: Introduction

Chương 1 trình bày tổng quan về phát biểu bài toán (Problem Statement), khẳng định tầm quan trọng của việc làm sạch dữ liệu đối với việc ra quyết định trong doanh nghiệp. Xác định mục tiêu chính (Objectives) là xây dựng hệ thống OpenK kèm bộ thư viện API và vạch rõ phạm vi nghiên cứu (Scope) xoay quanh các thuật toán đo độ tương đồng chuỗi, các công cụ Pandas, NumPy, OpenRefine, Cerberus và cấu trúc tổng thể của bản thuyết minh khóa luận.

Chapter 2: Theoretical Background

Chương 2 phân tích cơ sở lý thuyết và tổng quan các công trình liên quan:

  • Giới thiệu các hệ thống làm sạch dữ liệu lớn BigDansing, hệ thống NADEEF, công cụ OpenRefine và thư viện Cerberus.
  • Định nghĩa bài toán phát hiện bất thường dữ liệu, phân loại các kỹ thuật học máy hiện có.
  • Trình bày chi tiết toán học và thuật toán của các phương pháp phân cụm: Phương pháp va chạm khóa (Fingerprint, N-gram Fingerprint), phương pháp k-láng giềng gần nhất (Hamming, Levenshtein, Damerau-Levenshtein Distance) và phương pháp đo độ tương đồng (Jaro, Jaro-Winkler Similarity).

Chapter 3: Methodologies and Design

Chương 3 mô tả kiến trúc tổng thể và thiết kế chi tiết của OpenK:

  • Phân tích chi tiết 3 thành phần cốt lõi: Converter, Data Cleanser và Clustering Operator.
  • Xây dựng sơ đồ hoạt động (Activity Diagram) thể hiện luồng thực thi phát hiện bất thường từ bước nạp dữ liệu, tạo dự án, thực hiện CRUD, lọc từ khóa, sắp xếp cột đến phân cụm và lưu dữ liệu đã làm sạch.
  • Thiết lập sơ đồ Use-case và đặc tả chi tiết các ca sử dụng của tác tử người dùng (User: nạp/xem dữ liệu, tìm kiếm từ khóa, ẩn cột, phân trang, xuất dữ liệu) và tác tử phân cụm chạy ngầm (Cluster data agent: quản lý cụm, phân cụm bằng kNN, Similarity, Key Collision).
  • Phân tích kiến trúc của BigDansing (RuleEngine, RepairAlgorithm) và NADEEF (Rule collector, Detection & cleaning core, Metadata management, Dashboard) để so sánh giải pháp thiết kế.

Chapter 4: System Implementation

Chương 4 tập trung vào chi tiết hiện thực hóa phần mềm:

  • Trình bày công nghệ sử dụng: Flask, Jinja, HTML/CSS/JavaScript, Pandas DataFrame, NumPy.
  • Thiết lập sơ đồ định tuyến hệ thống (/, /convert, /upload, /data).
  • Chi tiết hóa lưu đồ thuật toán và mã nguồn của các lớp KNN, Similarity, Fingerprinter trong tệp clustering.py.
  • Thiết kế giao diện kết nối nguồn dữ liệu cục bộ và dịch vụ Azure Cosmos DB.

Chapter 5: System Evaluation

Chương 5 tiến hành đánh giá hệ thống thông qua các tiêu chí đo lường thực nghiệm:

  • Đo lường thời gian nạp và trực quan hóa tập dữ liệu đầu vào (Loading & visualizing time).
  • Đo lường thời gian phát hiện và phân cụm dữ liệu bất thường (Detecting & clustering time).
  • Đánh giá tỷ lệ lỗi (Error percentage) trong quá trình phân cụm khi đối sánh trực tiếp giữa OpenK và OpenRefine trên các tập dữ liệu thử nghiệm.

Chapter 6: Thesis Denouement

Chương 6 tổng kết các kết quả đạt được của khóa luận:

  • Đánh giá ý nghĩa khoa học và thực tiễn của hệ thống làm sạch dữ liệu OpenK.
  • Nhìn nhận các đóng góp về mặt thuật toán, công cụ trực quan hóa và thư viện API cho cộng đồng phát triển phần mềm.
  • Đề xuất các định hướng phát triển và hoàn thiện hệ thống trong tương lai.

Kết quả và đóng góp

1. Kết quả đạt được

  • Hiện thực hóa thành công phần mềm OpenK: Xây dựng ứng dụng web hoàn chỉnh có khả năng nhập dữ liệu từ nhiều định dạng (CSV, TSV, JSON, XLSX) và tích hợp kết nối trực tiếp với dịch vụ cơ sở dữ liệu đám mây Azure Cosmos DB.
  • Tích hợp đa dạng thuật toán phân cụm: Triển khai đầy đủ các thuật toán Key Collision (Fingerprint, N-gram Fingerprint), kNN (Hamming, Levenshtein, Damerau-Levenshtein) và Similarity (Jaro, Jaro-Winkler) trên cùng một giao diện tương tác.
  • Cung cấp công cụ trực quan hóa và API: Hỗ trợ giao diện thao tác dữ liệu dạng bảng (phân trang, lọc từ khóa, sắp xếp cột, ẩn/hiện cột, xuất dữ liệu) và đề xuất thư viện API bằng Flask phục vụ tái sử dụng mã nguồn.
  • Thử nghiệm trên dữ liệu thực tế: Kiểm thử hệ thống trên tập dữ liệu hàng không (Airlines dataset) và tập dữ liệu bất động sản cào từ trang batdongsan.com.vn.

2. Đánh giá từ Hội đồng chấm bảo vệ

  • Giảng viên hướng dẫn (PGS. Đặng Trần Khánh): Đánh giá đồ án đạt mức Xuất sắc (Điểm: 10/10). Đánh giá cao việc sinh viên đã nghiên cứu sâu các thư viện Python (Pandas, NumPy, JSON), khảo sát các công cụ OpenRefine, Cerberus, hiện thực hóa thành công công cụ làm sạch dữ liệu, trực quan hóa và xây dựng thư viện API.
  • Giảng viên phản biện (TS. Phan Trọng Nhân): Đánh giá đồ án đạt loại Giỏi (Điểm: 9/10). Ghi nhận hệ thống đã ứng dụng các công nghệ hiện đại (Flask, Jinja, Pandas, NumPy), kết nối được với tệp tin và DBMS đám mây, đồng thời thực hiện các thực nghiệm cơ bản về thời gian nạp, thời gian chạy và tỉ lệ lỗi.

Hạn chế và hướng nghiên cứu tiếp

Theo nhận xét của người phản biện (TS. Phan Trọng Nhân) và nội dung tổng kết của khóa luận, hệ thống còn tồn tại một số hạn chế kỹ thuật:

  1. Bản chất của phát hiện bất thường qua phân cụm cú pháp: Phương pháp phân cụm chuỗi chủ yếu dựa trên mặt chữ (syntactic level) nên chưa phản ánh trọn vẹn bất thường ngữ nghĩa; hệ thống có thể xem hai văn bản khác nghĩa nhau là dị biệt bất thường trong cùng một nhóm.
  2. Hạn chế trong đánh giá thực nghiệm: Các thử nghiệm và so sánh giữa OpenK và OpenRefine còn đơn giản, tập trung nhiều vào thời gian xử lý (loading time, running time) hơn là đánh giá độ chính xác chuyên sâu của bài toán phát hiện bất thường.
  3. Tính linh hoạt và thiết lập tham số: Hệ thống chưa linh hoạt để mở rộng thêm các thuật toán mới. Người dùng gặp khó khăn trong việc lựa chọn các giá trị tham số tối ưu (như tham số bán kính $k$, ngưỡng tương đồng $threshold$, hoặc giới hạn số lượng bản ghi tải từ cơ sở dữ liệu Azure Cosmos DB).

Hướng phát triển tiếp theo: Nâng cấp khả năng xử lý ngữ nghĩa của văn bản, tối ưu hóa thuật toán lựa chọn tham số tự động và mở rộng kiến trúc cho phép tích hợp thêm nhiều thuật toán làm sạch dữ liệu mới.

Giá trị tham khảo

Khóa luận là tài liệu tham khảo hữu ích cho sinh viên và kỹ sư thuộc các chuyên ngành Khoa học Máy tính, Kỹ thuật Phần mềm và Hệ thống Thông tin:

  • Tham khảo thuật toán xử lý chuỗi: Cung cấp công thức toán học, ma trận tính toán và mã nguồn Python chi tiết của các thuật toán Levenshtein, Damerau-Levenshtein, Hamming, Jaro, Jaro-Winkler và Fingerprint.
  • Tham khảo thiết kế hệ thống làm sạch dữ liệu: Phù hợp cho các đề tài phát triển ứng dụng web xử lý dữ liệu với Flask, Pandas DataFrame, cơ chế quản lý dự án làm sạch dữ liệu và kết nối cơ sở dữ liệu đám mây Azure Cosmos DB.
  • Tài liệu nghiên cứu so sánh: Cung cấp góc nhìn tổng hợp về kiến trúc của các hệ thống làm sạch dữ liệu lớn như BigDansing, NADEEF và OpenRefine.

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

1. Hệ thống OpenK hỗ trợ nạp những định dạng dữ liệu nào?

OpenK hỗ trợ nạp dữ liệu từ các định dạng tệp cục bộ gồm CSV, TSV, JSON, XLSX, qua đường dẫn URL và kết nối trực tiếp đến cơ sở dữ liệu đám mây Azure Cosmos DB thông qua khóa kết nối (database key).

2. Sự khác biệt giữa thuật toán Fingerprint và N-gram Fingerprint trong OpenK là gì?

Thuật toán Fingerprint chuẩn hóa toàn bộ chuỗi ký tự (xóa khoảng trắng, bỏ dấu câu, chuyển về mã ASCII, tách từ, lọc trùng và sắp xếp thứ tự từ). Trong khi đó, N-gram Fingerprint trích xuất các đoạn ký tự liền kề có độ dài $n$ (mặc định $n=1$ hoặc $n=2$), loại bỏ trùng lặp và sắp xếp lại, giúp gom cụm hiệu quả các từ bị sai lỗi chính tả hoặc lỗi dính/cách khoảng trắng (ví dụ: "lookout" và "look out").

3. Trong lớp Similarity, khoảng cách Jaro-Winkler được tính toán như thế nào?

Trong lớp Similarity, độ tương đồng Jaro-Winkler ($sim_w$) được tính bằng công thức $sim_w = sim_j + lp(1 - sim_j)$ với $sim_j$ là độ tương đồng Jaro, $l$ là độ dài tiền tố chung tối đa 4 ký tự, và hệ số $p=0.1$. Giá trị $sim_w$ nằm trong đoạn $[0, 1]$. Khoảng cách Jaro-Winkler được xác định bằng phép nghịch đảo $d_w = 1 - sim_w$.

4. Người phản biện đã chỉ ra những điểm hạn chế chính nào của khóa luận?

TS. Phan Trọng Nhân chỉ ra ba hạn chế chính: (1) Phương pháp phân cụm chưa thực sự tách bạch được bản chất của dữ liệu dị biệt; (2) Thực nghiệm đánh giá còn đơn giản, thiên về thời gian chạy hơn là độ chính xác; (3) Hệ thống chưa linh hoạt để bổ sung thuật toán mới và người dùng gặp khó khăn khi chọn giá trị tham số (như tham số $k$ hoặc giới hạn bản ghi nạp từ Azure).

Kết luận

Khóa luận tốt nghiệp của sinh viên Nguyễn Đình Khương đã hoàn thành việc thiết kế và hiện thực hóa hệ thống làm sạch dữ liệu OpenK chạy trên nền tảng web ứng dụng Flask, Pandas và JavaScript. Đề tài đã tích hợp thành công ba nhóm thuật toán phân cụm chuỗi văn bản gồm Key Collision, K-NN và Similarity Measurement để nhận diện và xử lý các dị biệt dữ liệu. Đồ án được Hội đồng bảo vệ đánh giá cao về tính ứng dụng thực tiễn với kết quả điểm số xuất sắc (10/10 từ GVHD và 9/10 từ GVPB), đồng thời mở ra các định hướng hoàn thiện về mặt ngữ nghĩa và tối ưu hóa tham số cho các hệ thống làm sạch dữ liệu sau này.