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

Sự phát triển nhanh chóng của mạng Internet, giao thức TCP/IP và dịch vụ World Wide Web đã tạo ra một môi trường trao đổi thông tin sâu rộng trên phạm vi toàn cầu. Tại mỗi quốc gia, các nhà cung cấp dịch vụ mạng tiếp nhận số lượng tên miền đăng ký gia tăng liên tục mỗi ngày. Mỗi tên miền được thiết lập với nội dung và mục đích sử dụng khác nhau, dẫn tới sự tích lũy của những khối dữ liệu khổng lồ tại các đơn vị quản lý hạ tầng mạng. Nguồn dữ liệu này tiềm ẩn những thông tin có giá trị về thói quen truy cập, nhu cầu dịch vụ của người dùng và các xu hướng phát triển kinh tế - xã hội.

Tuy nhiên, các phương pháp quản trị và truy vấn cơ sở dữ liệu truyền thống (như SQL) chỉ đáp ứng được việc tìm kiếm thông tin bề mặt, không thể bóc tách được các tri thức ẩn sâu cũng như các quy luật dự báo tương lai. Trước thực trạng đó, tác giả lựa chọn đề tài "Áp dụng một số thuật toán khai phá dữ liệu trong quản lý địa chỉ Internet" nhằm nghiên cứu ứng dụng các thuật toán khai phá dữ liệu vào bài toán phân tích, quản lý tài nguyên địa chỉ mạng.

Mục tiêu chung của đề tài là áp dụng một số thuật toán khai phá dữ liệu, trọng tâm là phân cụm dữ liệu, phục vụ cho công tác quản lý địa chỉ Internet. Nhiệm vụ nghiên cứu được văn bản giao gồm 4 nội dung cụ thể:

  1. Tìm hiểu các phương pháp phân cụm dữ liệu.
  2. Tìm hiểu một số phương pháp tạo các luật cơ bản và các giải thuật liên quan.
  3. Đề ra phương pháp xây dựng hệ thống.
  4. Thử nghiệm với các công cụ để giải quyết bài toán.

Đối tượng nghiên cứu của đồ án bao gồm: các thuật toán khai phá dữ liệu (đặc biệt là nhóm giải thuật phân cụm phân hoạch như K-Means, K-Medoids/PAM, CLARA, CLARANS), hệ thống không gian địa chỉ Internet (giao thức IPv4, IPv6) và hệ thống phân giải tên miền (DNS).

Phạm vi nghiên cứu:

  • Không gian: Đề tài khảo cứu các tiêu chuẩn quản lý địa chỉ Internet quốc tế (IANA, ICANN) và hệ thống quản lý tên miền tại Việt Nam do Trung tâm Internet Việt Nam (VNNIC) vận hành; dữ liệu thử nghiệm tập trung vào thông tin tên miền đã đăng ký.
  • Thời gian: Đồ án tốt nghiệp hệ đào tạo liên thông ngành Công nghệ thông tin (khóa học CTL901), được giao nhiệm vụ từ ngày 03 tháng 10 năm 2016 và hoàn thành vào tháng 12 năm 2016 tại Trường Đại học Dân lập Hải Phòng.

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

Đồ án xây dựng trên nền tảng lý thuyết khai phá dữ liệu (Data Mining) và tiến trình khám phá tri thức trong cơ sở dữ liệu (KDD). Tác giả xác định tiến trình khám phá tri thức gồm 6 giai đoạn:

  • Lựa chọn dữ liệu (Data selection).
  • Xóa bỏ dữ liệu không cần thiết / Làm sạch (Cleaning).
  • Làm giàu dữ liệu (Enrichment).
  • Chuẩn hóa và mã hóa (Coding and normalization).
  • Khám phá tri thức (Data mining).
  • Báo cáo kết quả (Reporting).

Trong khâu xử lý và chuẩn hóa dữ liệu, văn bản trình bày hai kỹ thuật: chuẩn hóa toàn cục (chuẩn hóa các biến trên toàn bộ tập dữ liệu) và chuẩn hóa trong cụm (chuẩn hóa lặp lại dựa trên kết quả phân cụm ban đầu). Để giảm số chiều cho các tập dữ liệu lớn, văn bản phân tích các kỹ thuật biến đổi:

  • Phân tích thành phần chính (PCA): Giảm số chiều dữ liệu nhưng giữ lại tối đa phương sai của các biến gốc.
  • Phân tách giá trị riêng (SVD - Singular Value Decomposition): Kỹ thuật tính toán ma trận xấp xỉ tuyến tính ứng dụng trong nén dữ liệu.
  • Phép biến đổi Karhunen-Loève (KL): Tối ưu hóa việc kết hợp tuyến tính các biến sao cho tổng khoảng cách bình phương (SSD) đạt giá trị tối thiểu.

Về phương diện hạ tầng mạng và cơ sở pháp lý, nghiên cứu căn cứ vào:

  • Cấu trúc địa chỉ IPv4 (32-bit, chia thành 4 octet, 5 lớp A, B, C, D, E; công nghệ NAT giải quyết cạn kiệt địa chỉ).
  • Cấu trúc địa chỉ IPv6 (128-bit, 8 nhóm số hecxa; các dải địa chỉ Global Unicast, Link-Local, Unique Local, Loopback; các giải pháp chuyển đổi Dual-stack, Tunneling, Translation).
  • Hệ thống tên miền (DNS) đóng vai trò chuyển đổi tên miền dạng ký tự sang địa chỉ IP dạng số.
  • Thể chế quản lý: Quản lý toàn cầu bởi ICANN và IANA; quản lý quốc gia tại Việt Nam bởi Trung tâm Internet Việt Nam (VNNIC) căn cứ theo Quyết định số 02/2008/QĐ-BTTTT ngày 05/03/2008 của Bộ trưởng Bộ Thông tin và Truyền thông.

Về phương pháp nghiên cứu, đề tài sử dụng phương pháp phân cụm dữ liệu (Clustering) thuộc nhóm học không giám sát (unsupervised learning). Văn bản khảo sát hai cấu trúc biểu diễn dữ liệu cơ bản:

  • Ma trận dữ liệu (Object-by-variable): Kích thước $n \times p$ ($n$ đối tượng, $p$ thuộc tính).
  • Ma trận phi tương đồng (Dissimilarity matrix): Kích thước $n \times n$, biểu diễn khoảng cách $d(i,j)$ giữa từng cặp đối tượng.

Các công thức khoảng cách toán học được thiết lập cho từng loại thuộc tính:

  • Khoảng cách Minkowski: $d(x,y) = (\sum_{i=1}^n |x_i - y_i|^q)^{1/q}$.
  • Khoảng cách Euclidean ($q=2$): $d(x,y) = \sqrt{\sum_{i=1}^n (x_i - y_i)^2}$.
  • Khoảng cách Manhattan ($q=1$): $d(x,y) = \sum_{i=1}^n |x_i - y_i|$.
  • Khoảng cách Chebychev ($q=\infty$): $d(x,y) = \max_i |x_i - y_i|$.
  • Độ lệch tuyệt đối trung bình dùng để chuẩn hóa thuộc tính: $s_f = \frac{1}{n} \sum_{i=1}^n |x_{if} - m_f|$.
  • Đối với dữ liệu nhị phân: Sử dụng hệ số đối sánh đơn giản và hệ số Jaccard ($d(x,y) = \frac{b+c}{a+b+c}$).

Văn bản phân nhóm các phương pháp phân cụm thành 4 trường phái chính: phương pháp phân hoạch (K-Means, PAM, CLARA, CLARANS), phương pháp phân cấp (AGNES, DIANA, CURE, BIRCH, CHAMELEON), phương pháp dựa trên mật độ (DBSCAN, OPTICS, DENCLUE, DBCLASD) và phương pháp dựa trên lưới (Grid-based).

Thiết kế và triển khai

Căn cứ vào nhiệm vụ thiết kế tốt nghiệp, tác giả đã xây dựng một phần mềm quản lý dữ liệu tên miền tích hợp các chức năng thử nghiệm thuật toán khai phá dữ liệu. Kiến trúc và quy trình vận hành của ứng dụng được thể hiện qua các khối chức năng cụ thể:

Khối chức năng Mô tả chi tiết theo tài liệu
Thiết lập kết nối cơ sở dữ liệu Cho phép cấu hình các tham số kết nối nguồn dữ liệu phục vụ lưu trữ thông tin tên miền và địa chỉ IP.
Giao diện xác thực Cung cấp màn hình đăng nhập hệ thống nhằm kiểm soát quyền truy cập của người quản trị.
Giao diện chính hệ thống Hiển thị các phân hệ điều hướng quản trị sau khi xác thực thành công.
Cập nhật dữ liệu bảng Hỗ trợ nhập liệu, chỉnh sửa, lưu trữ các bản ghi về tên miền đăng ký và địa chỉ mạng tương ứng.
Tìm kiếm thông tin Tra cứu nhanh thông tin địa chỉ Internet, tên miền và các thuộc tính quản trị liên quan.
Mô-đun khai phá thuật toán Thực thi thuật toán K-Means và K-Medoids (PAM) trên tập dữ liệu đã lưu để phân nhóm đối tượng.

Chương trình được thiết kế nhằm mô phỏng và kiểm nghiệm hoạt động của hai thuật toán phân hoạch K-Means và K-Medoids đối với dữ liệu quản lý Internet, cho phép quan sát sự hình thành của các cụm sau các bước tính toán khoảng cách và cập nhật tâm.

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

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

Chương mở đầu tập trung hệ thống hóa các định nghĩa, phạm vi và thách thức của khai phá dữ liệu, đồng thời trình bày tổng quan về hệ thống địa chỉ Internet:

  • Khái niệm và ứng dụng: Định nghĩa khai phá dữ liệu là việc kết hợp hệ chuyên gia, máy học và cơ sở dữ liệu để rút trích tri thức. Ứng dụng trải rộng trong thương mại (tiếp thị, tín dụng, chống gian lận), sản xuất (quản trị mạng, điều khiển), khoa học (dự báo thời tiết, sinh học) và thông tin cá nhân.
  • Các thách thức kỹ thuật: Tác giả chỉ ra 6 khó khăn gồm: cơ sở dữ liệu cực lớn (mức terabyte), dữ liệu nhiễu hoặc thiếu, số chiều dữ liệu lớn, sự thay đổi của tri thức theo thời gian, quan hệ ràng buộc phức tạp giữa các trường dữ liệu.
  • Tiến trình KDD và tiền xử lý: Mô tả chi tiết 6 bước khám phá tri thức; phân tích các kỹ thuật giảm chiều dữ liệu gồm phân tích thành phần chính (PCA), phân tách giá trị riêng (SVD) và phép biến đổi Karhunen-Loève (KL).
  • Hạ tầng địa chỉ Internet: Khảo cứu cấu trúc địa chỉ IPv4 (32 bits, phân chia các lớp A, B, C, D, E; vai trò của NAT) và IPv6 (128 bits, 8 octet hecxa; giải pháp khắc phục cạn kiệt tài nguyên mạng và hỗ trợ định tuyến, bảo mật, di động).
  • Hệ thống DNS và thể chế quản trị: Cơ chế chuyển đổi tên miền sang IP; vai trò của IANA, ICANN trên trường quốc tế và thẩm quyền quản lý tài nguyên tên miền .vn, địa chỉ IP, số hiệu mạng (ASN) của Trung tâm Internet Việt Nam (VNNIC) theo Quyết định số 02/2008/QĐ-BTTTT.

Chương 2: Các thuật toán trong khai phá dữ liệu

Chương này đi sâu vào cơ sở toán học của bài toán phân cụm dữ liệu (Clustering):

  • Yêu cầu thuật toán: Đòi hỏi thuật toán phải có thời gian chạy tuyến tính theo kích thước dữ liệu, chịu được dữ liệu nhiễu, xác định được cụm có hình dạng bất kỳ, tối thiểu hóa tham số đầu vào và độc lập với thứ tự nạp dữ liệu.
  • Phân loại kiểu dữ liệu và độ đo: Phân tích các loại thuộc tính (liên tục, rời rạc, định danh, có thứ tự, khoảng, tỷ lệ, nhị phân, dữ liệu không gian) cùng các hệ đo khoảng cách tương ứng (Minkowski, Euclidean, Manhattan, Chebychev, Jaccard).
  • Tổng quan các trường phái phân cụm: So sánh ưu - nhược điểm của 4 phương pháp: phân hoạch (Partitioning), phân cấp (Hierarchical - tiếp cận Bottom-Up và Top-Down), dựa trên mật độ (Density-based) và dựa trên lưới (Grid-based).
  • Thuật toán K-Means: Trình bày chi tiết giải thuật từng bước và thực hiện ví dụ minh họa bằng tính toán số học trên tập dữ liệu gồm 4 mẫu thuốc ($A, B, C, D$) với 2 đặc trưng (trọng lượng $X$ và độ pH $Y$):
    • Dữ liệu đầu vào: $A(1, 1)$, $B(2, 1)$, $C(4, 3)$, $D(5, 4)$; thiết lập số cụm $K=2$.
    • Khởi tạo tâm: Chọn $c_1 = A(1, 1)$ và $c_2 = B(2, 1)$.
    • Vòng lặp 1: Tính khoảng cách Euclidean từ các điểm đến $c_1, c_2$ (ví dụ: khoảng cách từ $C(4,3)$ đến $c_1$ là $3.61$, đến $c_2$ là $2.83$). Phân chia cụm: Nhóm 1 chứa ${A}$, Nhóm 2 chứa ${B, C, D}$.
    • Cập nhật tâm: Nhóm 1 giữ nguyên $c_1(1, 1)$; tính lại tọa độ tâm nhóm 2 theo trung bình cộng các điểm $B, C, D$.
    • Tiếp tục lặp các bước tính lại khoảng cách và gán cụm cho đến khi vị trí các tâm hội tụ hoàn toàn.
  • Khái quát các thuật toán liên quan: Giới thiệu nguyên lý của thuật toán K-Medoids (PAM), CLARA và CLARANS trong xử lý các tập dữ liệu lớn.

Chương 3: Thử nghiệm hệ thống

Chương cuối cùng trình bày việc triển khai thực tế trên công cụ phần mềm:

  • Cấu hình hệ thống: Trình bày giao diện thiết lập kết nối cơ sở dữ liệu để truy xuất kho bản ghi địa chỉ mạng.
  • Giao diện người dùng: Cung cấp quy trình đăng nhập, màn hình quản trị chính sau khi đăng nhập.
  • Quản lý dữ liệu: Thao tác trên giao diện cập nhật bảng tên miền đăng ký và giao diện tra cứu/tìm kiếm thông tin tên miền.
  • Thực nghiệm phân cụm: Vận hành mô-đun chạy thuật toán K-Means và K-Medoids (PAM) trên giao diện phần mềm để kiểm tra khả năng phân nhóm dữ liệu quản lý Internet.

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

Nghiên cứu đã tổng hợp và hiện thực hóa các nội dung chính sau:

Nhóm nội dung Kết quả cụ thể đạt được
Cơ sở lý thuyết Hệ thống hóa 6 giai đoạn KDD, các kỹ thuật biến đổi dữ liệu (PCA, SVD, KL) và cấu trúc địa chỉ mạng IPv4, IPv6, cơ chế DNS.
Mô hình toán học Thiết lập các công thức đo khoảng cách đối với nhiều kiểu dữ liệu; phân tích ưu khuyết điểm của 4 phương pháp phân cụm lớn.
Minh họa giải thuật Thực hiện đầy đủ 8 bước tính toán số học của K-Means trên ma trận thực nghiệm với $K=2$, minh chứng quá trình cập nhật tâm và hội tụ.
Ứng dụng thực nghiệm Xây dựng phần mềm hoàn chỉnh gồm các chức năng kết nối cơ sở dữ liệu, quản lý cập nhật tên miền, tìm kiếm và chạy thuật toán K-Means, K-Medoids.

Về mặt giải pháp, đồ án đề xuất việc ứng dụng phân cụm dữ liệu như một giải pháp thay thế cho các truy vấn SQL đơn thuần, giúp các đơn vị quản lý mạng phát hiện các mẫu hành vi truy cập và xu hướng đăng ký tên miền của người dùng.

Về đóng góp học thuật và thực tiễn, đồ án đã kết hợp việc phân tích hạ tầng công nghệ mạng (IPv4, IPv6) gắn liền với căn cứ pháp lý quản lý Internet tại Việt Nam (thẩm quyền của VNNIC theo Quyết định 02/2008/QĐ-BTTTT), đồng thời hiện thực hóa thuật toán phân cụm lý thuyết thành chương trình giao diện có thể thử nghiệm trực quan.

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

Hạn chế của nghiên cứu:

  • Theo phân tích lý thuyết của tác giả trong đồ án, phương pháp phân hoạch (K-Means) bộc lộ nhược điểm là bắt buộc phải xác định trước số cụm $k$, chỉ phát hiện được các cụm có dạng đa giác lồi, không nhận diện được các cụm có hình dạng lồng nhau hoặc dạng lõm.
  • Thuật toán nhạy cảm với dữ liệu nhiễu và các điểm ngoại lai xa tâm; sự hiện diện của các điểm này có thể làm sai lệch vị trí tâm cụm.
  • Phạm vi thử nghiệm phần mềm trong chương 3 dừng lại ở mức độ minh họa chức năng, chưa có dữ liệu đánh giá thực tế trên các kho dữ liệu quy mô lớn (mức terabyte) của nhà mạng.

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

  • Dựa trên phạm vi và các nội dung đã khảo sát, hướng mở rộng tự nhiên của đề tài là nghiên cứu tích hợp các giải thuật phân cụm dựa trên mật độ (như DBSCAN, OPTICS) để khắc phục nhược điểm lọc nhiễu và tìm cụm có hình dáng bất kỳ.
  • Thử nghiệm trên các tập dữ liệu lưu lượng mạng và nhật ký truy cập thực tế với số chiều lớn hơn.

Giá trị tham khảo

Tài liệu này có giá trị tham khảo hữu ích cho:

  • Sinh viên, học viên ngành Công nghệ thông tin, Hệ thống thông tin hoặc Khoa học dữ liệu đang làm đồ án tốt nghiệp hoặc tiểu luận về đề tài Khai phá dữ liệu (Data Mining) và Học máy (Machine Learning).
  • Cán bộ kỹ thuật và quản trị mạng quan tâm đến việc kết hợp giữa công tác quản lý tài nguyên địa chỉ Internet (IP, DNS) với các công cụ phân tích tri thức tự động.

Phần nội dung đáng tham khảo nhất trong tài liệu là Chương 2, nơi tác giả tổng hợp có hệ thống các công thức toán học về độ đo khoảng cách cho từng kiểu thuộc tính và các bước tính toán chi tiết từng bước lặp của thuật toán K-Means. Bên cạnh đó, phần khảo cứu thể chế quản lý Internet của VNNIC tại Chương 1 cung cấp tài liệu tham khảo tốt về khía cạnh pháp lý - tổ chức quản lý mạng tại Việt Nam.

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

1. Tiến trình khám phá tri thức (KDD) trong đồ án gồm mấy bước và việc khai phá thực sự diễn ra ở bước nào?
Tiến trình gồm 6 bước: Lựa chọn dữ liệu (data selection), Xóa bỏ dữ liệu không cần thiết (cleaning), Làm giàu dữ liệu (enrichment), Chuẩn hóa và mã hóa (coding and normalization), Khám phá tri thức (data mining) và Báo cáo kết quả (reporting). Văn bản khẳng định việc khai phá tri thức thực sự chỉ bắt đầu từ bước thứ 5.

2. Đơn vị nào quản lý tài nguyên Internet tại Việt Nam và căn cứ theo văn bản pháp lý nào được nêu trong đồ án?
Trung tâm Internet Việt Nam (VNNIC) - đơn vị trực thuộc Bộ Thông tin và Truyền thông (thành lập ngày 28/04/2000) chịu trách nhiệm quản lý tên miền và địa chỉ Internet. Chức năng, nhiệm vụ của VNNIC được quy định cụ thể theo Quyết định số 02/2008/QĐ-BTTTT do Bộ trưởng Bộ Thông tin và Truyền thông Lê Doãn Hợp ban hành ngày 05/03/2008.

3. Theo đồ án, địa chỉ IPv6 có những ưu điểm gì nổi bật so với IPv4?
IPv6 có không gian địa chỉ 128-bit (cho phép tăng lên $2^{128}$ địa chỉ so với khoảng 4,3 tỷ của IPv4), khôi phục nguyên lý kết nối đầu cuối - đầu cuối, loại bỏ công nghệ NAT, hỗ trợ tự động cấu hình không cần DHCP thủ công, định tuyến phân cấp tốt hơn, hỗ trợ Multicast, nâng cao tính năng bảo mật và tối ưu hóa cho các thiết bị di động.

4. Vì sao phương pháp phân cụm phân hoạch (K-Means) không phù hợp với các cụm dữ liệu có hình dạng phức tạp?
Do các cụm trong phương pháp phân hoạch được đại diện bởi tâm cụm và các điểm dữ liệu được gán dựa trên khoảng cách tới tâm, phương pháp này chỉ có thể tìm ra các cụm có hình dạng đa giác lồi. Nó không thể nhận diện các cụm có dạng lõm, lồng nhau hoặc phủ lên nhau, đồng thời dễ bị lệch tâm khi dữ liệu có nhiều phần tử nhiễu hoặc điểm ngoại lai.

5. Trong ví dụ minh họa thuật toán K-Means ở Chương 2, tác giả đã sử dụng tập dữ liệu thực nghiệm nào?
Tác giả sử dụng tập dữ liệu gồm 4 loại thuốc ($A, B, C, D$) với 2 biến định lượng: đặc trưng $X$ (chỉ số trọng lượng - weight index) và đặc trưng $Y$ (độ pH). Tọa độ của 4 đối tượng lần lượt là $A(1, 1)$, $B(2, 1)$, $C(4, 3)$, $D(5, 4)$ và được phân chia thành $K=2$ nhóm.

Kết luận

Đồ án tốt nghiệp của sinh viên Nguyễn Văn Tuyên đã hệ thống hóa toàn diện cơ sở lý thuyết về quy trình khám phá tri thức, các mô hình toán học đo khoảng cách và các giải thuật phân cụm dữ liệu điển hình. Nghiên cứu đã liên kết kiến thức lý thuyết về khai phá dữ liệu với bài toán thực tiễn về hạ tầng mạng Internet (IPv4, IPv6, DNS) và khung pháp lý quản lý tài nguyên mạng tại Việt Nam. Đồng thời, tác giả đã hiện thực hóa thuật toán K-Means thông qua các bước tính toán số học cụ thể và xây dựng thành công phần mềm thử nghiệm quản lý dữ liệu tên miền trên giao diện người dùng.