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

Sự phát triển nhanh chóng của công nghệ thông tin cùng sự gia tăng số lượng người dùng Internet toàn cầu đã dẫn đến sự bùng nổ của các kho dữ liệu số. Việc cập nhật liên tục và gia tăng quy mô dữ liệu đặt ra thách thức lớn trong việc khai thác, xử lý nguồn tài nguyên khổng lồ này thành các tri thức hữu ích phục vụ quản lý và hoạt động kinh doanh. Các công cụ tìm kiếm và phương pháp khai thác cơ sở dữ liệu truyền thống bộc lộ nhiều hạn chế khi đối diện với nguồn tài nguyên Web đa dạng và phi cấu trúc. Nghiên cứu và ứng dụng kỹ thuật khai phá dữ liệu (Data Mining) và khám phá tri thức trong cơ sở dữ liệu (Knowledge Discovery in Databases - KDD) trong môi trường Web trở thành một hướng tiếp cận cần thiết.

Đồ án tốt nghiệp "Kết hợp các phương pháp phân cụm trong khai phá dữ liệu Web" được thực hiện bởi sinh viên Cao Hữu Hải (Lớp CT1601, Ngành Công nghệ Thông tin, Trường Đại học Dân lập Hải Phòng) dưới sự hướng dẫn của ThS. Nguyễn Trịnh Đông, thực hiện từ ngày 03/10/2016 đến ngày 24/12/2016.

Đồ án đặt ra các mục tiêu và nhiệm vụ nghiên cứu cụ thể sau:

  1. Tìm hiểu tổng quan về khai phá dữ liệu và khai phá dữ liệu Web.
  2. Nghiên cứu các thuật toán phân cụm dữ liệu phổ biến (k-means, PAM, BIRCH, DBSCAN).
  3. Khảo sát việc áp dụng các thuật toán phân cụm trong bài toán tìm kiếm và phân cụm tài liệu Web.
  4. Đề xuất phương pháp xây dựng hệ thống phân cụm dữ liệu.
  5. Thử nghiệm mô hình phân cụm dữ liệu trên công cụ phần mềm Orange.

Đối tượng nghiên cứu của đồ án là các dạng dữ liệu Web (văn bản tự do, cấu trúc HTML, XML, nhật ký máy chủ và siêu liên kết) cùng các giải thuật phân cụm dữ liệu. Phạm vi nghiên cứu tập trung vào cơ sở toán học của các phép đo độ tương tự, quy trình xử lý văn bản Web và mô phỏng thực nghiệm phân cụm trên phần mềm chuyên dụng.

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

Khung lý thuyết và mô hình nghiên cứu

Đồ án tiếp cận quy trình khám phá tri thức trong cơ sở dữ liệu (KDD) gồm 5 giai đoạn:

  1. Trích chọn dữ liệu (Data Selection): Trích xuất tập dữ liệu mục tiêu từ cơ sở dữ liệu lớn ban đầu theo các tiêu chí xác định.
  2. Tiền xử lý dữ liệu (Data Preprocessing): Làm sạch dữ liệu (xử lý dữ liệu thiếu, loại bỏ dữ liệu sai lệch), rút gọn dữ liệu (dùng hàm nhóm, nén dữ liệu, lấy mẫu) và rời rạc hóa dữ liệu (dựa vào histogram, entropy).
  3. Biến đổi dữ liệu (Data Transformation): Chuẩn hóa và làm mịn dữ liệu để đưa về dạng khuôn mẫu thống nhất phục vụ tính toán.
  4. Khai phá dữ liệu (Data Mining): Áp dụng các thuật toán học máy, thống kê để trích xuất các mẫu và mối liên hệ tiềm ẩn.
  5. Đánh giá và biểu diễn tri thức (Pattern Evaluation and Knowledge Presentation): Biến đổi kết quả thành dạng trực quan (đồ thị, cây, bảng biểu, luật) và đánh giá độ hữu ích.

Trong hệ thống phân loại dữ liệu, đồ án phân định rõ hai nhóm thuộc tính dựa trên kích thước miền và hệ đo:

  • Theo kích thước miền: Thuộc tính liên tục (miền giá trị vô hạn không đếm được) và thuộc tính rời rạc (miền giá trị hữu hạn hoặc đếm được).
  • Theo hệ đo: Thuộc tính định danh (Nominal Scale), thuộc tính có thứ tự (Ordinal Scale), thuộc tính khoảng (Interval Scale) và thuộc tính tỉ lệ (Ratio Scale). Thuộc tính định danh và thứ tự thuộc nhóm thuộc tính hạng mục (Categorical); thuộc tính khoảng và tỉ lệ thuộc nhóm thuộc tính số (Numeric).

Không gian metric và các độ đo độ tương tự

Để đo lường khoảng cách giữa hai đối tượng $x$ và $y$ trong không gian metric thỏa mãn các tiên đề khoảng cách ($\delta(x,y) \ge 0$; $\delta(x,y) = 0 \Leftrightarrow x = y$; $\delta(x,y) = \delta(y,x)$; $\delta(x,y) \le \delta(x,z) + \delta(z,y)$), đồ án áp dụng các công thức:

Loại thuộc tính Tên độ đo khoảng cách / tương tự Công thức toán học
Thuộc tính khoảng / số Khoảng cách Minkowski $d(x, y) = \left(\sum_{i=1}^p |x_i - y_i|^q\right)^{\frac{1}{q}}$
Thuộc tính khoảng / số Khoảng cách Euclidean ($q = 2$) $d(x, y) = \sqrt{\sum_{i=1}^p (x_i - y_i)^2}$
Thuộc tính khoảng / số Khoảng cách Manhattan ($q = 1$) $d(x, y) = \sum_{i=1}^p |x_i - y_i|$
Thuộc tính khoảng / số Khoảng cách cực đại ($q \to \infty$) $d(x, y) = \max_{i=1}^p |x_i - y_i|$
Thuộc tính nhị phân đối xứng Hệ số đối sánh đơn giản $S_{xy} = \frac{a + d}{a + b + c + d}$
Thuộc tính nhị phân bất đối xứng Hệ số Jaccard $S_{xy} = \frac{a}{a + b + c}$
Thuộc tính định danh Độ phi tương tự $d(x, y) = \frac{p - m}{p}$ ($m$ là số thuộc tính trùng khớp, $p$ là tổng số thuộc tính)
Thuộc tính có thứ tự Chuẩn hóa miền $[0, 1]$ $z_{if} = \frac{r_{if} - 1}{M_i - 1}$ ($r_{if} \in {1, \dots, M_i}$)
Thuộc tính tỉ lệ Biến đổi logarit $q_i = \log(x_i)$

(Trong bảng tham số nhị phân: $a$ là số thuộc tính cùng bằng 1; $b$ là thuộc tính có giá trị 1 ở $x$ và 0 ở $y$; $c$ là thuộc tính có giá trị 0 ở $x$ và 1 ở $y$; $d$ là thuộc tính cùng bằng 0).

Biểu diễn văn bản và trích chọn đặc trưng

Để chuyển đổi văn bản Web sang mô hình không gian vector (Vector Space Model), đồ án sử dụng kỹ thuật tính trọng số TF-IDF:

  • Tần số xuất hiện của từ (TF - Term Frequency): $TF(t, d) = 1 + \log(tf)$ khi $tf > 0$ (với $tf$ là số lần xuất hiện của từ $t$ trong tài liệu $d$).
  • Nghịch đảo tần số tài liệu (IDF - Inverse Document Frequency): $IDF_t = \log\left(\frac{N}{df_t}\right)$ (với $N$ là tổng số tài liệu trong tập dữ liệu, $df_t$ là số lượng tài liệu có chứa từ $t$).
  • Giảm số chiều không gian vector thông qua việc loại bỏ từ dừng (Stop words) và áp dụng Định luật Zipf (Zipf's Law - 1949) cùng nguyên lý phân loại từ phổ biến / từ hiếm của Luhn (1958).

Phương pháp nghiên cứu và nguồn dữ liệu

Nghiên cứu sử dụng phương pháp phân tích - tổng hợp lý thuyết để so sánh các thuật toán phân cụm, kết hợp phương pháp mô hình hóa thực nghiệm trên phần mềm Orange. Nguồn dữ liệu kiểm chứng lý thuyết xử lý ngôn ngữ trích dẫn từ tập ngữ liệu 336.310 tài liệu tiếng Anh gồm 125.209 từ riêng biệt (trong đó từ dừng "The" có tần số xuất hiện 7.398.934 lần, chiếm tỉ lệ 5,8%).

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

Chương 1: Giới thiệu về khai phá dữ liệu Web

Chương 1 hệ thống hóa toàn diện các khái niệm cơ bản về khai phá dữ liệu và khai phá Web:

  • Khai phá dữ liệu và KDD: Trình bày định nghĩa KPDL là quá trình trích xuất tự động các mẫu tri thức tiềm ẩn từ các cơ sở dữ liệu lớn. Phân tích mối quan hệ liên ngành giữa KPDL với học máy, thống kê, cơ sở dữ liệu và tính toán song song. Hai mục tiêu cốt lõi của KPDL gồm mô tả (khám phá mẫu dữ liệu dễ hiểu) và dự báo (xác định giá trị chưa biết).
  • Các kỹ thuật và ứng dụng: Trình bày 5 kỹ thuật chính: phân lớp và dự báo (học có giám sát), luật kết hợp, phân tích chuỗi theo thời gian, phân cụm (học không giám sát), mô tả và tóm tắt khái niệm. Liệt kê các lĩnh vực ứng dụng: thương mại, thương mại điện tử, ngân hàng, bảo hiểm, viễn thông và y tế.
  • Phương pháp phân cụm dữ liệu: Nêu định nghĩa phân cụm là quá trình nhóm các đối tượng dữ liệu sao cho các phần tử trong cùng một cụm có độ tương tự cao nhất và khác biệt với các phần tử ở cụm khác. Đề xuất các phương pháp nhận diện phần tử ngoại lai (dựa trên khoảng cách, mô hình phân phối thống kê, độ khác biệt đặc trưng) và giải pháp xử lý nhiễu.
  • Yêu cầu đối với thuật toán phân cụm: Xác định 9 tiêu chí thiết kế: khả năng mở rộng với dữ liệu lớn, thích nghi nhiều kiểu dữ liệu, phát hiện cụm hình thù bất kỳ, tối thiểu hóa tham số đầu vào, ít nhạy cảm với thứ tự dữ liệu, chống chịu dữ liệu nhiễu cao, ít nhạy cảm với biến động tham số, xử lý dữ liệu đa chiều, tính khả thi và dễ cài đặt.
  • Xử lý dữ liệu văn bản Web: Phân loại dữ liệu Web thành văn bản tự do, HTML, XML, dữ liệu động, hình ảnh/video, liên kết tĩnh/động, dữ liệu nhật ký (Server logs) và đăng ký người dùng. Trình bày chi tiết kỹ thuật biểu diễn không gian vector, gộp từ đồng nghĩa, lọc từ dừng và đồ thị phân bố tần số từ vựng theo định luật Zipf.
+-------------------------------------------------------------------------+
|                        QUY TRÌNH KHÁM PHÁ TRI THỨC                      |
|                                                                         |
|  [Dữ liệu thô]                                                          |
|  [Dữ liệu lựa chọn]                                                     |
|  [Dữ liệu tiền xử lý]                                                   |
|  [Dữ liệu biến đổi]                                                     |
|  [Các mẫu tri thức]                                                     |
|  [Tri thức hoàn chỉnh]                                                  |
+-------------------------------------------------------------------------+

Chương 2: Một số kỹ thuật phân cụm dữ liệu

Chương 2 phân tích cấu trúc giải thuật, hàm mục tiêu, độ phức tạp tính toán và ưu nhược điểm của 4 thuật toán phân cụm phổ biến:

1. Thuật toán k-means (MacQueen, 1967)

  • Hàm tiêu chuẩn tối thiểu hóa: $$E = \sum_{i=1}^k \sum_{x \in C_i} D(x, m_i)^2$$ (trong đó $m_i$ là trọng tâm cụm $C_i$, $D$ là khoảng cách Euclidean).
  • Quy trình 4 bước:
    1. Khởi tạo: Chọn ngẫu nhiên hoặc theo kinh nghiệm $k$ đối tượng $m_j$ ($j=1 \dots k$) làm trọng tâm ban đầu.
    2. Tính khoảng cách: Tính khoảng cách từ mỗi đối tượng $x_i$ tới $k$ trọng tâm, gán $x_i$ vào cụm có trọng tâm gần nhất.
    3. Cập nhật trọng tâm: Tính lại tọa độ trọng tâm $m_j$ bằng trung bình cộng các vector đối tượng trong cụm.
    4. Điều kiện dừng: Lặp lại bước 2 và 3 cho đến khi vị trí các trọng tâm không còn thay đổi.
  • Độ phức tạp tính toán: $O(n \cdot k \cdot d \cdot \tau \cdot t)$ (với $n$ là số đối tượng, $k$ là số cụm, $d$ là số chiều, $\tau$ là số vòng lặp, $t$ là thời gian tính toán cơ sở).
  • Đánh giá: Thuật toán đơn giản, chạy nhanh trên tập dữ liệu lớn; tuy nhiên chỉ phù hợp với dữ liệu thuộc tính số và cụm hình cầu, rất nhạy cảm với nhiễu, điểm ngoại lai và việc chọn $k$ trọng tâm khởi tạo ban đầu.

2. Thuật toán PAM (Partitioning Around Medoids - Kaufman & Rousseeuw, 1987)

  • Cơ chế hoạt động: Sử dụng các đối tượng đại diện thực tế (medoid) thay cho trọng tâm trung bình toán học để tăng khả năng chống chịu nhiễu. Thuật toán đánh giá chi phí hoán chuyển $TC_{mp} = \sum_j C_{jmp}$ giữa medoid hiện thời $O_m$ và điểm không phải medoid $O_p$.
  • 4 trường hợp tính chi phí $C_{jmp}$:
    • Trường hợp 1: $O_j$ thuộc cụm $O_m$ và gần $O_p$ hơn medoid gần thứ hai $O_{m,2}$. Khi đó $C_{jmp} = d(O_j, O_p) - d(O_j, O_m)$ ($C_{jmp} \ge 0$).
    • Trường hợp 2: $O_j$ thuộc cụm $O_m$ nhưng gần $O_{m,2}$ hơn $O_p$. Khi đó $C_{jmp} = d(O_j, O_{m,2}) - d(O_j, O_m)$ ($C_{jmp}$ có thể âm hoặc dương).
    • Trường hợp 3: $O_j$ không thuộc cụm $O_m$ (thuộc cụm $O_{m,2}$) và $O_j$ gần $O_{m,2}$ hơn $O_p$. Khi đó $C_{jmp} = 0$.
    • Trường hợp 4: $O_j$ thuộc cụm $O_{m,2}$ nhưng $O_j$ gần $O_p$ hơn $O_{m,2}$. Khi đó $C_{jmp} = d(O_j, O_p) - d(O_j, O_{m,2})$ ($C_{jmp} < 0$).
  • Độ phức tạp tính toán: $O(i \cdot k \cdot (n-k)^2)$ (với $i$ là số vòng lặp). Thuật toán tốn kém tài nguyên tính toán khi $n$ và $k$ lớn.

3. Thuật toán BIRCH (Balanced Iterative Reducing and Clustering Using Hierarchies - Zhang, Ramakrishnan & Livny, 1996)

  • Cấu trúc lưu trữ: Thuật toán phân cụm phân cấp tiếp cận theo hướng Top-down, không lưu toàn bộ dữ liệu trong bộ nhớ mà chỉ lưu các đại lượng thống kê dưới dạng bộ ba đặc trưng cụm $CF = (n, LS, SS)$ (với $n$ là số đối tượng, $LS$ là tổng vector thuộc tính, $SS$ là tổng bình phương vector thuộc tính).
  • Cây CF (CF Tree): Cây cân bằng được kiểm soát bởi hai tham số: Yếu tố nhánh ($B$ - số nút con tối đa của nút trong) và Ngưỡng khoảng cách ($T$ - đường kính tối đa của cụm con lưu tại nút lá).
  • Độ phức tạp: Đạt mức tuyến tính $O(n)$, xử lý nhanh trên tập dữ liệu rất lớn và dữ liệu tăng trưởng động theo thời gian, nhưng bị giới hạn bởi chất lượng cụm không đồng đều và không phù hợp với dữ liệu đa chiều.

4. Thuật toán DBSCAN (Density Based Spatial Clustering of Applications with Noise - Ester et al.)

  • Cơ chế dựa trên mật độ: Sử dụng hai tham số toàn cục: Ngưỡng bán kính lân cận ($Eps$) và Số điểm lân cận tối thiểu ($MinPts$).
  • Hệ thống định nghĩa:
    • Lân cận của điểm $p$: $N_{Eps}(p) = {q \in D \mid Dist(p, q) \le Eps}$.
    • Điểm nhân (Core point): Điểm $p$ thỏa mãn $|N_{Eps}(p)| \ge MinPts$.
    • Mật độ - đến được trực tiếp (Directly Density-reachable): Điểm $p$ đến được trực tiếp từ $q$ nếu $p \in N_{Eps}(q)$ và $q$ là điểm nhân.
    • Mật độ - đến được (Density-reachable): Tồn tại chuỗi điểm $p_1, p_2, \dots, p_n$ với $p_1 = q, p_n = p$ sao cho $p_{i+1}$ đến được trực tiếp từ $p_i$.
    • Mật độ - liên thông (Density-connected): Tồn tại điểm $o$ sao cho cả $p$ và $q$ đều mật độ - đến được từ $o$.
    • Cụm và Nhiễu: Cụm là tập con cực đại thỏa mãn tính liên thông mật độ; các điểm không thuộc cụm nào được xác định là nhiễu.
  • Đặc điểm: Phát hiện được các cụm có hình thù bất kỳ, tự động lọc nhiễu và ít chịu tác động bởi thứ tự nạp dữ liệu.

Chương 3: Khai phá dữ liệu Web

Chương 3 phân tích ba nhánh nghiên cứu chính trong khai phá Web:

Nhánh khai phá Web Đối tượng xử lý chính Kỹ thuật và mục tiêu
Khai phá nội dung Web (Web Content Mining) Văn bản tự do, HTML, XML, dữ liệu đa phương tiện Khai phá kết quả tìm kiếm (đánh trọng số URL, lập chỉ mục), khai phá văn bản (trích rút tóm tắt, phân lớp Naive Bayes / KNN, phân cụm phân cấp và phân hoạch)
Khai phá cấu trúc Web (Web Structure Mining) Siêu liên kết (Hyperlinks), cấu trúc đồ thị Web Đo độ tương đồng trích dẫn, độ tương tự chỉ mục, quan hệ liên kết trực tiếp giữa các trang, phân tích và quản lý cộng đồng Web
Khai phá sử dụng Web (Web Usage Mining) Nhật ký máy chủ (Server logs), dữ liệu phiên duyệt Theo dõi mẫu truy cập của người dùng, phân tích hành vi duyệt Web nhằm cá nhân hóa dịch vụ và tối ưu hóa hệ thống

Trong bài toán phân cụm văn bản Web, chương phân tích hai kỹ thuật:

  • Phân cụm phân cấp (Hierarchical Clustering): Tiếp cận từ dưới lên bằng cách khởi tạo mỗi tài liệu là một cụm, liên tục gộp cặp cụm có độ tương tự cao nhất cho đến khi đạt cây phân cấp hoàn chỉnh. Phương pháp có độ chính xác cao nhưng độ phức tạp lớn khi tập dữ liệu mở rộng.
  • Phân cụm phân hoạch (Partitional Clustering): Phân chia tập tài liệu thành số lượng cụm xác định trước thông qua tối ưu hóa hàm mục tiêu, mang lại tốc độ xử lý nhanh và độ ổn định cao.

Thiết kế và triển khai mô hình thực nghiệm

Phần thực nghiệm của đồ án được triển khai trên công cụ khai phá dữ liệu Orange nhằm kiểm chứng khả năng phân nhóm dữ liệu Web thông qua các widget xử lý trực quan:

+-------------------------------------------------------------------------+
|                SƠ ĐỒ LUỒNG XỬ LÝ TRÊN PHẦN MỀM ORANGE                   |
|                                                                         |
|  [File Dữ liệu]                                                         |
|  [Data Table / Chuẩn hóa]                                               |
|  [Distance Metric] (Tính khoảng cách Euclidean)                         |
|  [Hierarchical Clustering]       [k-means Clustering]                   |
|  (Cây phân cấp dữ liệu)          (Phân hoạch k=8 cụm tối ưu)            |
|            [Data Table / Trực quan hóa]                                 |
+-------------------------------------------------------------------------+

Quy trình thiết lập mô hình thực nghiệm:

  1. Nạp và tiền xử lý dữ liệu: Dữ liệu được đưa vào mô hình thông qua widget tập tin, hiển thị trên bảng dữ liệu để kiểm tra cấu trúc thuộc tính.
  2. Chuẩn hóa dữ liệu: Áp dụng các phép biến đổi chuẩn hóa đưa các trường thuộc tính về cùng một miền giá trị đồng nhất để loại bỏ sai lệch do đơn vị đo.
  3. Tính toán ma trận khoảng cách: Sử dụng widget tính khoảng cách với độ đo Euclidean Distance để thiết lập ma trận phi tương tự giữa các đối tượng dữ liệu.
  4. Thực thi phân cụm phân cấp (Hierarchical Clustering): Dữ liệu sau khi tính khoảng cách được đưa vào widget Hierarchical Clustering để xây dựng sơ đồ hình cây (Dendrogram), biểu diễn quan hệ tương đồng giữa các phần tử dữ liệu.
  5. Thực thi thuật toán k-means: Thiết lập thuật toán phân cụm k-means trên tập dữ liệu đã chuẩn hóa. Kết quả đánh giá chỉ số tối ưu hóa trên phần mềm Orange xác định số lượng $k = 8$ cụm là cấu hình tối ưu nhất cho tập dữ liệu thử nghiệm.
  6. Trực quan hóa kết quả: Biểu diễn các nhóm dữ liệu sau phân cụm lên không gian tọa độ trực quan để phân tích sự phân bố của các phần tử và đánh giá mức độ tách biệt giữa các cụm.

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

Bảng tổng hợp so sánh đặc tính các giải thuật phân cụm

Thuật toán Loại tiếp cận Độ phức tạp tính toán Khả năng xử lý nhiễu Khám phá cụm hình thù bất kỳ Độ nhạy với dữ liệu lớn
k-means Phân hoạch (Partitional) $O(n \cdot k \cdot d \cdot \tau \cdot t)$ Kém (rất nhạy cảm với ngoại lai) Không (chỉ nhận diện cụm hình cầu) Rất tốt, áp dụng hiệu quả cho CSDL lớn
PAM Phân hoạch dựa trên Medoid $O(i \cdot k \cdot (n-k)^2)$ Tốt (ít bị ảnh hưởng bởi điểm biên) Hạn chế Kém khi $n$ và $k$ có giá trị lớn
BIRCH Phân cấp qua cây CF (Top-down) $O(n)$ Tốt (tự động loại bỏ ngoại lai ở lá) Kém (bị ảnh hưởng bởi ngưỡng $T$) Rất cao, tối ưu cho dữ liệu tăng trưởng động
DBSCAN Dựa trên mật độ (Density-based) Phụ thuộc cấu trúc chỉ mục không gian Rất tốt (tự động định danh điểm nhiễu) Rất tốt (nhận diện mọi hình dạng bất kỳ) Hiệu quả với cơ sở dữ liệu không gian lớn

Các kết quả chính đạt được:

  • Hệ thống hóa cơ sở lý thuyết: Trình bày hoàn chỉnh cơ sở toán học của các hệ đo khoảng cách (Minkowski, Euclidean, Manhattan, Jaccard), quy trình khám phá tri thức 5 bước và các mô hình biểu diễn văn bản (VSM, TF-IDF, Zipf's Law).
  • Phân tích so sánh giải thuật: Làm rõ cơ chế vận hành, điều kiện hội tụ, ưu nhược điểm và độ phức tạp tính toán của 4 giải thuật phân cụm kinh điển (k-means, PAM, BIRCH, DBSCAN).
  • Xây dựng quy trình xử lý dữ liệu Web: Thiết lập quy trình khai phá nội dung Web kết hợp lọc từ dừng, trích chọn đặc trưng TF-IDF và phân cụm tài liệu.
  • Thực nghiệm mô hình hóa: Triển khai thành công quy trình phân tích dữ liệu trên công cụ Orange, thực hiện tính toán khoảng cách Euclidean, phân cụm phân cấp và xác định tham số $k = 8$ cụm tối ưu đối với giải thuật k-means.

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

Hạn chế:

  • Nội dung đồ án tập trung chủ yếu vào nghiên cứu lý thuyết tổng quan và mô phỏng trên công cụ có sẵn (Orange), chưa tiến hành xây dựng một hệ thống phần mềm độc lập hoàn chỉnh với giao diện tương tác người dùng.
  • Thử nghiệm phân cụm văn bản Web chưa bao quát đầy đủ các đặc trưng phức tạp của văn bản tiếng Việt (như xử lý từ ghép, nhập nhằng ngữ nghĩa).
  • Chưa tiến hành đo lường hiệu năng định lượng chi tiết trên các tập dữ liệu Web thực tế quy mô lớn có cấu trúc liên kết động phức tạp.

Hướng nghiên cứu tiếp:

  • Nghiên cứu kết hợp các thuật toán phân cụm mật độ (DBSCAN) với phân cụm phân cấp nhằm nâng cao chất lượng phân nhóm trên các tập dữ liệu Web phi cấu trúc.
  • Xây dựng module tiền xử lý chuyên sâu cho tiếng Việt (tách từ, loại bỏ từ dừng tiếng Việt, chuẩn hóa từ đồng nghĩa) tích hợp vào mô hình không gian vector.
  • Phát triển ứng dụng thu thập và phân cụm tự động kết quả tìm kiếm thời gian thực từ các công cụ tìm kiếm trực tuyến.

Giá trị tham khảo

Đồ án là tài liệu tham khảo hữu ích cho sinh viên ngành Công nghệ Thông tin, Khoa học Máy tính, Hệ thống Thông tin trong các học phần Khai phá dữ liệu (Data Mining), Xử lý ngôn ngữ tự nhiên và Trích xuất thông tin Web.

Các nội dung có giá trị tham khảo chuyên sâu gồm:

  • Toàn bộ cơ sở công thức toán học về không gian metric, bảng tham số nhị phân và các hàm đo khoảng cách.
  • Phân tích chi tiết 4 trường hợp tính chi phí hoán chuyển medoid trong thuật toán PAM và hệ thống định nghĩa liên thông mật độ trong DBSCAN.
  • Quy trình chuẩn hóa dữ liệu, tính toán khoảng cách và cấu hình phân cụm trên phần mềm Orange.

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

1. Thuật toán k-means có những ưu điểm và hạn chế cơ bản nào khi áp dụng cho dữ liệu lớn?

Thuật toán k-means có ưu điểm là giải thuật đơn giản, tốc độ thực thi nhanh với độ phức tạp $O(n \cdot k \cdot d \cdot \tau \cdot t)$, cho phép áp dụng hiệu quả trên các tập dữ liệu lớn. Tuy nhiên, k-means có các hạn chế: chỉ áp dụng được với dữ liệu có thuộc tính số, chỉ phát hiện được các cụm có dạng hình cầu, rất nhạy cảm với dữ liệu nhiễu/phần tử ngoại lai, và chất lượng phân cụm phụ thuộc nhiều vào việc chọn số cụm $k$ cùng vị trí $k$ trọng tâm khởi tạo ban đầu.

2. Thuật toán PAM khắc phục nhược điểm nào của k-means và chi phí tính toán thay đổi ra sao?

Thuật toán PAM sử dụng các đối tượng thực tế (medoid) trong cụm làm đại diện thay vì dùng trọng tâm trung bình toán học như k-means, giúp thuật toán ít bị tác động bởi các phần tử ngoại lai và xử lý tốt dữ liệu nhiễu. Tuy nhiên, do phải duyệt và tính toán tổng chi phí hoán chuyển $TC_{mp}$ cho tất cả $k(n-k)$ cặp medoid và không medoid trong mỗi vòng lặp, độ phức tạp của PAM là $O(i \cdot k \cdot (n-k)^2)$, khiến thuật toán kém hiệu quả về thời gian khi số lượng phần tử $n$ và số cụm $k$ lớn.

3. Cấu trúc cây CF trong thuật toán BIRCH lưu trữ những thông số nào?

Thuật toán BIRCH không lưu toàn bộ dữ liệu trong bộ nhớ mà lưu trữ đại lượng thống kê dưới dạng bộ ba đặc trưng cụm $CF = (n, LS, SS)$, trong đó $n$ là số đối tượng dữ liệu trong cụm con, $LS$ là tổng các vector thuộc tính ($\sum_{i=1}^n X_i$), và $SS$ là tổng bình phương các vector thuộc tính ($\sum_{i=1}^n X_i^2$). Cây CF được kiểm soát bởi hai tham số là yếu tố nhánh $B$ (số nút con tối đa của nút trong) và ngưỡng khoảng cách $T$ (đường kính tối đa của cụm con tại nút lá).

4. Trong xử lý văn bản Web, định luật Zipf và việc loại bỏ từ dừng có vai trò gì?

Trong mô hình không gian vector, mỗi từ riêng biệt tương ứng với một chiều không gian, dẫn đến số chiều vector rất lớn. Việc loại bỏ từ dừng (các từ nối, giới từ xuất hiện nhiều nhưng không mang ý nghĩa chủ đề) và áp dụng định luật Zipf (loại bỏ các từ có tần số xuất hiện quá cao hoặc quá thấp theo nguyên lý của Luhn năm 1958) giúp giảm đáng kể số chiều của vector dữ liệu mà vẫn bảo đảm tính chính xác của nội dung văn bản cần xử lý.

5. Trong thực nghiệm trên phần mềm Orange, giải thuật k-means đạt kết quả tối ưu ở cấu hình bao nhiêu cụm?

Trong mô hình thực nghiệm với công cụ Orange được trình bày tại Chương 3 của đồ án, sau khi thực hiện các bước nạp dữ liệu, chuẩn hóa thuộc tính và đo khoảng cách bằng Euclidean Distance, giải thuật phân cụm k-means cho kết quả phân chia dữ liệu tối ưu nhất tại giá trị $k = 8$ cụm.

Kết luận

Đồ án tốt nghiệp "Kết hợp các phương pháp phân cụm trong khai phá dữ liệu Web" của tác giả Cao Hữu Hải đã hệ thống hóa toàn diện các kiến thức nền tảng về khai phá dữ liệu Web, không gian metric và các phương pháp biểu diễn văn bản TF-IDF. Công trình phân tích sâu cơ chế giải thuật, ưu nhược điểm và độ phức tạp của 4 thuật toán phân cụm tiêu biểu gồm k-means, PAM, BIRCH và DBSCAN. Đồng thời, đồ án đã triển khai thành công mô hình thực nghiệm trên phần mềm Orange, minh họa trực quan quy trình tính toán khoảng cách Euclidean, phân cụm phân cấp và xác định cấu hình phân cụm k-means tối ưu.