Giới thiệu dự án

Bối cảnh và vấn đề thực tiễn

Trong kỷ nguyên số hóa, sự phát triển vượt bậc của công nghệ thông tin đã thúc đẩy các doanh nghiệp và tổ chức thu thập, lưu trữ khối lượng dữ liệu khổng lồ từ các hoạt động nghiệp vụ hằng ngày. Theo các thống kê trong ngành khai phá dữ liệu (Data Mining), hơn 80% dữ liệu doanh nghiệp tích lũy tồn tại dưới dạng bán cấu trúc hoặc phi cấu trúc, ẩn chứa những quy luật hành vi chưa được khai thác. Đặc biệt trong các lĩnh vực như viễn thông, ngân hàng, thương mại điện tử và y tế, việc trích xuất các tri thức hữu ích để đưa ra quyết định kinh doanh chiến lược hoặc dự báo xu hướng tương lai đã trở thành yêu cầu sống còn.

Khóa luận tốt nghiệp "Nghiên cứu các thuật toán phân lớp dữ liệu dựa trên cây quyết định" (Đại học Công nghệ – Đại học Quốc gia Hà Nội) tập trung giải quyết bài toán phân lớp dữ liệu (Data Classification) – một trong những hướng tiếp cận trung tâm của khai phá dữ liệu và học máy (Machine Learning).

graph TD
    A[Cơ sở dữ liệu nghiệp vụ] --> B[Tiền xử lý & Làm sạch dữ liệu]
    B --> C[Tập dữ liệu đào tạo - Training Set]
    B --> D[Tập dữ liệu kiểm tra - Test Set]
    C --> E[Thuật toán sinh Cây quyết định]
    E --> F[Mô hình Cây quyết định / Tập luật If-Then]
    D --> G[Đánh giá độ chính xác - Holdout / Cross-Validation]
    F --> G
    G --> H[Phân lớp dữ liệu mới & Dự báo nghiệp vụ]

Vấn đề nghiên cứu cụ thể

  1. Nghẽn cổ chai bộ nhớ (Memory Bottleneck): Các thuật toán phân lớp truyền thống yêu cầu toàn bộ tập dữ liệu huấn luyện phải thường trú trong bộ nhớ chính (memory-resident), khiến hệ thống mất khả năng mở rộng khi đối mặt với các cơ sở dữ liệu viễn thông hàng triệu đến hàng tỷ bản ghi.
  2. Xử lý thuộc tính liên tục và giá trị thiếu (Continuous Attributes & Missing Values): Việc xác định ngưỡng phân chia tối ưu cho các thuộc tính số liên tục đòi hỏi chi phí sắp xếp dữ liệu lặp đi lặp lại rất lớn tại mỗi nút, đồng thời việc xử lý dữ liệu bị khuyết thiếu dễ dẫn đến sai lệch phân lớp.
  3. Hiện tượng quá vừa (Overfitting): Cây quyết định có xu hướng học quá chi tiết cả các đặc trưng nhiễu (noise) của tập dữ liệu huấn luyện, làm suy giảm nghiêm trọng độ chính xác dự đoán trên tập dữ liệu kiểm tra thực tế.

Mục tiêu của dự án

  1. Nghiên cứu hệ thống hóa nền tảng lý thuyết phân lớp dữ liệu và các phương pháp xây dựng cây quyết định dựa trên thuật toán nền tảng Hunt.
  2. Phân tích chuyên sâu, đối sánh cơ chế hoạt động, độ phức tạp và cấu trúc dữ liệu của hai thuật toán tiêu biểu: C4.5 (tối ưu cho tập dữ liệu vừa và nhỏ) và SPRINT (tối ưu cho tập dữ liệu cực lớn, hỗ trợ tính toán song song).
  3. Triển khai thực nghiệm mô hình phân lớp C4.5 (Release 8) trên bộ dữ liệu thực tế từ cổng thông tin dịch vụ (Web Portal) của Tổng công ty Bưu chính Viễn thông Việt Nam (VNPT) với 180.000 bản ghi.
  4. Đánh giá chi tiết hiệu năng thuật toán dựa trên các tham số: thời gian sinh cây, số lượng thuộc tính, kiểu dữ liệu (liên tục/rời rạc), số lượng lớp phân loại và đề xuất giải pháp cải tiến mô hình.

Hướng tiếp cận giải pháp

Khóa luận áp dụng phương pháp quy nạp chia để trị (Divide-and-Conquer) theo thuật toán Hunt:

  • Đối với thuật toán C4.5, hệ thống sử dụng độ đo Độ lợi thông tin (Information Gain) và Tỉ số độ lợi (Gain Ratio) dựa trên hàm Entropy để lựa chọn thuộc tính phân chia tối ưu, kết hợp kỹ thuật tỉa cành sau (post-pruning) và chuyển đổi cây sang tập luật sản xuất (production rules).
  • Đối với thuật toán SPRINT (Scalable PaRallelization INduction of decision Trees), hệ thống loại bỏ giới hạn bộ nhớ bằng cấu trúc danh sách thuộc tính thường trú trên đĩa (disk-resident attribute lists), tiền sắp xếp một lần (pre-sorting), sử dụng chỉ số Gini (Gini Index) và điều phối phân hoạch nút con thông qua bảng băm (Hash Table) chỉ mục bản ghi (RID).

Kết quả kỳ vọng và chỉ số đo lường

  • Độ chính xác phân lớp: Đạt tỷ lệ dự báo chính xác trên 85% trên tập dữ liệu kiểm tra độc lập (Test Set).
  • Tính khả thi của luật: Chuyển đổi thành công cấu trúc cây phức tạp thành tập luật $If-Then$ ngắn gọn, tối ưu hóa cho truy vấn SQL nghiệp vụ.
  • Khả năng mở rộng: Đánh giá định lượng mối tương quan tuyến tính giữa thời gian thực thi với số lượng bản ghi và số lượng thuộc tính.

Phạm vi và giới hạn nghiên cứu

  • Phạm vi: Tập trung vào các thuật toán phân lớp giám sát (Supervised Learning) dạng cây quyết định nhị phân và đa nhánh; thực nghiệm trực tiếp trên hệ thống máy chủ đơn và phân tích lý thuyết mô hình song song hóa.
  • Giới hạn: Nghiên cứu không bao gồm các bài toán dự đoán giá trị liên tục (Regression Trees) và chưa cài đặt thực tế mô hình SPRINT song song trên cụm phần cứng phân tán.

Phân tích và thiết kế giải pháp

Phân tích hiện trạng

Tiêu chí ID3 (Quinlan, 1979) C4.5 (Quinlan, 1993) SLIQ (Mehta et al., 1996) SPRINT (Shafer et al., 1996)
Cơ chế lưu trữ Memory-resident Memory-resident Hybrid (Class list in RAM, Attributes on Disk) Disk-resident (Attribute lists on Disk)
Tiêu chuẩn phân chia Information Gain Gain Ratio / Info Gain Gini Index Gini Index
Thuộc tính liên tục Không hỗ trợ trực tiếp Sắp xếp động tại mỗi nút Tiền sắp xếp một lần Tiền sắp xếp một lần
Xử lý giá trị thiếu Không hỗ trợ Phân phối theo trọng số Không hỗ trợ trực tiếp Bỏ qua hoặc gán trọng số
Cắt tỉa cây Không Cắt tỉa sau (Post-pruning) Cắt tỉa theo độ dài mô tả (MDL) Cắt tỉa theo độ dài mô tả (MDL)
Giới hạn dữ liệu $< 50.000$ bản ghi $\approx 100.000 - 500.000$ bản ghi $\approx 1.000.000$ bản ghi (giới hạn bởi RAM) Không giới hạn ($> 10^9$ bản ghi)
Khả năng song song Thấp Thấp Trung bình Rất cao (Shared-nothing / SMP)

Phân loại yêu cầu hệ thống (MoSCoW)

  • Must-have:
    • Khả năng đọc và phân tích cú pháp các tệp định nghĩa schema (.names), tệp dữ liệu huấn luyện (.data) và tệp kiểm tra (.test).
    • Đánh giá phân chia tối ưu dựa trên Information Gain / Gain Ratio đối với C4.5 và Gini Index đối với SPRINT.
    • Xử lý triệt để thuộc tính số thực liên tục và giá trị rỗng/nhiễu (?).
    • Cơ chế cắt tỉa cành để chống quá vừa và trích xuất luật $If-Then$.
  • Should-have:
    • Tiện ích ước lượng chéo $K$-fold cross-validation (xval.sh).
    • Hỗ trợ cả hai chế độ chạy đơn (Batch Mode) và thử nghiệm lặp (Interactive Mode).
  • Could-have:
    • Khả năng chuyển đổi cây quyết định thành các truy vấn SQL tự động.
    • Tối ưu cấu trúc bảng băm phân phối dữ liệu trong SPRINT để giảm chi phí I/O đĩa.
  • Won't-have:
    • Giao diện đồ họa người dùng (GUI) tương tác thời gian thực; hệ thống hoạt động hoàn toàn qua giao diện dòng lệnh (CLI).
graph LR
    subgraph SPRINT Architecture
        A[Raw Disk Data] --> B[Presorting Phase]
        B --> C[Attribute List 1: Age]
        B --> D[Attribute List 2: CarType]
        B --> E[Attribute List N: ...]
        C --> F[Histogram Evaluation / Gini Index]
        D --> F
        E --> F
        F --> G[Split Point Selection]
        G --> H[Hash Table Construction on RIDs]
        H --> I[Partitioning Attribute Lists to Child Nodes]
    end

Thiết kế hệ thống

Technology Stack và Môi trường thực thi

  • Ngôn ngữ phát triển: C (ANSI C89/C99 standard) cho hiệu năng xử lý bộ nhớ tối ưu.
  • Mã nguồn lõi: C4.5 Release 8 (J. Ross Quinlan, 1993/1996).
  • Môi trường vận hành: Server Linux Đại học Công nghệ (10.10), 02 bộ xử lý vật lý Intel Xeon 2.4GHz (tương đương 4 luồng logic qua Hyper-Threading), L2 Cache 512KB, 1GB RAM.
  • Tập lệnh tiện ích: C-Shell Script (csh), xval-prep, average.

Cấu trúc tệp dữ liệu và Thiết kế khuôn dạng

Mô hình chuẩn hóa dữ liệu phân lớp thông qua 3 tệp tin cấu hình độc lập:

  1. Tệp định nghĩa thuộc tính (filestem.names): 
    | Target class label definition
NOKIA, SAMSUNG, MOTOROLA, SIEMENS, SONY_ERICSSON.

| Attribute definitions
AGE: continuous.
GENDER: MALE, FEMALE.
REGION_ID: 1, 2, 3, 4, 5, 6, 7.
ACCESS_COUNT: continuous.
SERVICE_TYPE: RING_TONE, LOGO, SMS_PORTAL, NEWS.
  2. Tệp dữ liệu huấn luyện (filestem.data): Mỗi dòng tương ứng với một bộ giá trị phân tách bằng dấu phẩy; giá trị thiếu biểu diễn bằng ký tự ?. 
    24, MALE, 1, 15, RING_TONE, NOKIA
32, FEMALE, 3, ?, SMS_PORTAL, SAMSUNG
19, MALE, 1, 45, LOGO, MOTOROLA
  3. Tệp dữ liệu kiểm thử (filestem.test): Cấu trúc tương tự tệp .data, sử dụng để đánh giá độc lập độ chính xác dự báo.

Thiết kế cấu trúc dữ liệu SPRINT

Để đảm bảo khả năng mở rộng trên đĩa, SPRINT sử dụng cấu trúc bản ghi tách biệt:

  • Attribute List: Bộ ba (Attribute Value, Class Label, RID).
  • Histogram tại mỗi nút:
    • Thuộc tính liên tục: Hai mảng phân phối $C_{below}$ (chứa phân phối lớp các bản ghi $\le$ ngưỡng hiện tại) và $C_{above}$ (chứa phân phối lớp các bản ghi $>$ ngưỡng hiện tại).
    • Thuộc tính rời rạc: Ma trận đếm (Count Matrix) biểu diễn tần suất lớp tương ứng với từng giá trị danh mục.
  • Bảng băm phân chia (Split Hash Table): Ánh xạ trực tiếp từ RID sang mã định danh nút con (Left Child / Right Child).

Phương pháp luận và Cơ sở toán học

Cơ sở toán học thuật toán C4.5

flowchart TD
    Start([Bắt đầu: Tập dữ liệu S]) --> CheckPure{Tất cả bản ghi<br/>cùng một lớp?}
    CheckPure -- Đúng --> CreateLeaf[Tạo nút Lá mang nhãn lớp đó]
    CheckPure -- Sai --> CalcEntropy[Tính Entropy tổng thể I_S]
    CalcEntropy --> EvalAttr[Duyệt từng thuộc tính A]
    EvalAttr --> CalcGain[Tính Gain_Ratio S, A]
    CalcGain --> BestSplit[Chọn thuộc tính có Gain_Ratio lớn nhất]
    BestSplit --> SplitData[Phân chia tập S thành các tập con S_i]
    SplitData --> Recurse[Gọi đệ quy MakeTree S_i]
    Recurse --> PruneTree[Cắt tỉa cây Post-pruning]
    PruneTree --> GenRules[Trích xuất tập luật If-Then]
    GenRules --> End([Hoàn thành])

1. Độ đo Entropy và Độ lợi thông tin (Information Gain)

Giả sử tập huấn luyện $S$ chứa $|S|$ phần tử thuộc $k$ lớp phân loại $C_1, C_2, \dots, C_k$. Xác suất xuất hiện của lớp $C_j$ trong $S$ được xác định bởi: $$p_j = \frac{|C_j, S|}{|S|}$$

Chỉ số thông tin (Entropy) cần thiết để xác định lớp của một phần tử bất kỳ trong $S$ là: $$I(S) = -\sum_{j=1}^{k} p_j \log_2(p_j)$$

Khi tập dữ liệu $S$ được phân hoạch thành $v$ tập con $S_1, S_2, \dots, S_v$ dựa trên thuộc tính kiểm tra $A$, Entropy kỳ vọng sau phân hoạch là: $$E(A) = \sum_{i=1}^{v} \frac{|S_i|}{|S|} \times I(S_i)$$

Độ lợi thông tin thu được từ phép phân chia theo thuộc tính $A$: $$Gain(S, A) = I(S) - E(A) = I(S) - \sum_{i=1}^{v} \frac{|S_i|}{|S|} I(S_i)$$

2. Tỉ số độ lợi (Gain Ratio)

Để khắc phục nhược điểm của Information Gain (vốn có thiên hướng ưu tiên các thuộc tính có nhiều giá trị phân nhánh đơn lẻ), C4.5 áp dụng chuẩn hóa bằng thông tin tiềm năng phân hoạch (Split Info): $$SplitInfo(S, A) = -\sum_{i=1}^{v} \frac{|S_i|}{|S|} \log_2\left(\frac{|S_i|}{|S|}\right)$$ $$GainRatio(S, A) = \frac{Gain(S, A)}{SplitInfo(S, A)}$$

Thuộc tính $A^$ được lựa chọn làm nút phân chia tại mỗi bước là thuộc tính thỏa mãn: $$A^ = \arg\max_{A} GainRatio(S, A)$$

/* Pseudocode: C4.5 Core Partitioning Algorithm */
TreeNode* FormTree(DataTable* T) {
    if (AllRecordsSameClass(T)) {
        return CreateLeafNode(GetUniqueClass(T));
    }
    
    Attribute* best_attr = NULL;
    double max_gain_ratio = -1.0;
    double best_threshold = 0.0;
    
    for (int i = 0; i < T->num_attributes; i++) {
        Attribute* attr = &T->attributes[i];
        if (attr->is_continuous) {
            double threshold;
            double gr = EvaluateContinuousGainRatio(T, attr, &threshold);
            if (gr > max_gain_ratio) {
                max_gain_ratio = gr;
                best_attr = attr;
                best_threshold = threshold;
            }
        } else {
            double gr = EvaluateDiscreteGainRatio(T, attr);
            if (gr > max_gain_ratio) {
                max_gain_ratio = gr;
                best_attr = attr;
            }
        }
    }
    
    if (best_attr == NULL || max_gain_ratio <= 0.0) {
        return CreateLeafNode(GetMajorityClass(T));
    }
    
    TreeNode* node = CreateInternalNode(best_attr, best_threshold);
    DataTable** subsets = SplitDataTable(T, best_attr, best_threshold);
    
    for (int i = 0; i < node->num_children; i++) {
        if (subsets[i]->num_records == 0) {
            node->children[i] = CreateLeafNode(GetMajorityClass(T));
        } else {
            node->children[i] = FormTree(subsets[i]);
        }
    }
    return node;
}

Cơ sở toán học thuật toán SPRINT

Chỉ số Gini (Gini Index)

Đối với tập dữ liệu $S$ có $n$ lớp, chỉ số $Gini(S)$ đo lường độ không tinh khiết (Impurity): $$Gini(S) = 1 - \sum_{j=1}^{n} p_j^2$$

Khi $S$ được phân chia nhị phân thành 2 tập con $S_1$ (kích thước $n_1$) và $S_2$ (kích thước $n_2$), chỉ số phân chia $Gini_{split}$ được tính toán bằng: $$Gini_{split}(S) = \frac{n_1}{n} Gini(S_1) + \frac{n_2}{n} Gini(S_2)$$

SPRINT duyệt tuần tự danh sách thuộc tính liên tục đã tiền sắp xếp, cập nhật các bảng tần suất $C_{below}$ và $C_{above}$ để tính toán $Gini_{split}$ tại mỗi điểm chia mà không cần truy xuất lại dữ liệu gốc trên đĩa.

/* Pseudocode: SPRINT Continuous Attribute Evaluation */
void EvaluateContinuousSplit(AttributeList* attr_list, int total_records, double* best_gini, double* best_split_val) {
    Histogram C_below = InitHistogram(NUM_CLASSES, 0);
    Histogram C_above = ComputeClassDistribution(attr_list);
    
    *best_gini = 1.0;
    
    for (int i = 0; i < attr_list->length - 1; i++) {
        Record rec = attr_list->records[i];
        UpdateHistogramAdd(&C_below, rec.class_label);
        UpdateHistogramSubtract(&C_above, rec.class_label);
        
        if (attr_list->records[i].value != attr_list->records[i+1].value) {
            double split_val = (attr_list->records[i].value + attr_list->records[i+1].value) / 2.0;
            int n1 = i + 1;
            int n2 = total_records - n1;
            
            double gini_s1 = 1.0 - SumSquaredProbabilities(&C_below, n1);
            double gini_s2 = 1.0 - SumSquaredProbabilities(&C_above, n2);
            double gini_split = ((double)n1 / total_records) * gini_s1 + ((double)n2 / total_records) * gini_s2;
            
            if (gini_split < *best_gini) {
                *best_gini = gini_split;
                *best_split_val = split_val;
            }
        }
    }
}

Implementation và Kết quả thực nghiệm

Môi trường và Quy trình thực nghiệm

Quá trình đánh giá thực nghiệm được thực hiện trên Server 10.10 với 4 chương trình cốt lõi của C4.5 Release 8:

  1. c4.5: Sinh cây quyết định từ tệp .data.
  2. c4.5rules: Cắt tỉa và sinh bộ luật sản xuất $If-Then$.
  3. consult: Áp dụng cây quyết định để gán nhãn tập dữ liệu kiểm tra .test.
  4. consultr: Áp dụng tập luật sản xuất để phân lớp dữ liệu mới.
# Lệnh thực thi huấn luyện và đánh giá mô hình C4.5
$ ./Data/Classes/10-5/class -f portal_user -u >> ./Data/Classes/10-5/class.dt
$ ./c4.5rules -f portal_user >> ./Data/Classes/10-5/rules.out

Bộ dữ liệu thực nghiệm viễn thông

  • Tổng dung lượng: 180.000 bản ghi nhật ký người dùng dịch vụ Web Portal của VNPT.
  • Tập huấn luyện (Training Set): 120.000 bản ghi (chiếm 66,7%).
  • Tập kiểm tra (Test Set): 60.000 bản ghi (chiếm 33,3%).
  • Các bài toán phân lớp mục tiêu:
    1. Phân loại cấu hình giao diện người dùng (WEB_SETTING_ID) – Bộ dữ liệu 19 thuộc tính.
    2. Dự báo hãng thiết bị di động (PRODUCTER_ID) – Bộ dữ liệu 8 thuộc tính.
    3. Phân loại gói cước dịch vụ di động (MOBILE_SERVICE_ID) – Bộ dữ liệu 8 thuộc tính.
Decision Tree Sample Output:
--------------------------------
ACCESS_DURATION <= 120 :
|   DATA_VOLUME <= 500 : LOW_USAGE (1420.0/12.0)
|   DATA_VOLUME > 500 :
|   |   AGE <= 25 : TEEN_PROMO (850.0/5.0)
|   |   AGE > 25 : STANDARD (430.0/18.0)
ACCESS_DURATION > 120 :
|   SERVICE_TYPE = RING_TONE : VAS_HIGH (2100.0/45.0)
|   SERVICE_TYPE = NEWS : BUSINESS_PRO (980.0/8.0)

Generated Production Rules Sample:
--------------------------------
Rule 14:
    AGE > 22
    REGION_ID = 1
    ACCESS_COUNT > 30
    -> class NOKIA [94.2%]

Rule 27:
    SERVICE_TYPE = RING_TONE
    ACCESS_DURATION > 300
    -> class HIGH_ARPU [91.8%]

Đánh giá hiệu năng chi tiết

1. Mối phụ thuộc giữa thời gian sinh cây và kích thước tập dữ liệu huấn luyện

Số lượng bản ghi (Cases) Thời gian sinh cây (2 thuộc tính) Thời gian sinh cây (7 thuộc tính) Thời gian sinh cây (18 thuộc tính) Thời gian sinh tập luật (Rules)
10.000 0.22 s 0.85 s 2.41 s 4.12 s
30.000 0.71 s 2.64 s 7.58 s 15.30 s
60.000 1.48 s 5.42 s 15.92 s 42.85 s
90.000 2.31 s 8.29 s 24.15 s 86.40 s
120.000 3.15 s 11.20 s 33.45 s 148.90 s

Nhận xét chuyên sâu: Thời gian xây dựng cây quyết định tăng trưởng tuyến tính $O(m \cdot n \log n)$ theo kích thước tập huấn luyện. Tuy nhiên, thời gian sinh tập luật sản xuất (c4.5rules) tăng trưởng theo hàm phi tuyến (bậc 2 hoặc bậc 3) do giai đoạn cắt tỉa điều kiện luật phải duyệt tổ hợp trên toàn bộ tập dữ liệu.

2. Ảnh hưởng của bản chất thuộc tính đến hiệu năng xử lý

Đặc điểm thực nghiệm Tập thuộc tính rời rạc hoàn toàn Tập thuộc tính liên tục (Số thực) Mức độ chênh lệch (%)
Thời gian tính toán tiêu chuẩn phân chia 1.84 s 14.72 s Tăng 700%
Bộ nhớ tiêu thụ trung bình 4.2 MB 18.6 MB Tăng 342%
Độ sâu cây trung bình 6 tầng 14 tầng Tăng 133%

Nguyên nhân kỹ thuật: Thuộc tính liên tục đòi hỏi giải thuật QuickSort sắp xếp lại toàn bộ giá trị tại mỗi nút kiểm tra của cây, dẫn đến hiện tượng nghẽn I/O tính toán nếu dữ liệu không được tiền sắp xếp như trong mô hình SPRINT.

Đổi mới và Đóng góp khoa học

  1. So sánh toàn diện giữa C4.5 và SPRINT: Khóa luận làm rõ sự đối lập giữa hai chiến lược thiết kế: C4.5 tập trung tối ưu hóa độ nén cây và khả năng sinh luật cho tập dữ liệu trong RAM, trong khi SPRINT tái cấu trúc toàn bộ luồng dữ liệu thông qua Attribute Lists trên đĩa, loại bỏ hoàn toàn sự phụ thuộc vào dung lượng RAM vật lý.
graph TD
    subgraph Chiến lược Song song hóa Cây quyết định
        A[Thuật toán Tuần tự] --> B[Phương pháp Đồng bộ<br/>Synchronous]
        A --> C[Phương pháp Phân hoạch<br/>Partitioned]
        A --> D[Phương pháp Lai<br/>Hybrid Strategy]
        
        B -->|Đặc điểm| B1[Xử lý song song dữ liệu địa phương<br/>Chi phí truyền thông cao ở mức sâu]
        C -->|Đặc điểm| C1[Phân chia cây con cho từng CPU<br/>Khó cân bằng tải Load Imbalance]
        D -->|Quy tắc kích hoạt| D1["Chuyển chế độ khi:<br/>Σ(Giao tiếp) ≥ Chi phí chuyển + Cân bằng tải"]
    end

  1. Hệ thống hóa các phương pháp song song hóa thuật toán cây quyết định:

    • Xây dựng cây đồng bộ (Synchronous Tree Induction): Tất cả các bộ vi xử lý cùng tham gia phát triển một nút; không cần di chuyển dữ liệu lớn nhưng chịu chi phí đồng bộ thông điệp cao ở các tầng sâu của cây.
    • Xây dựng cây phân hoạch (Partitioned Tree Induction): Phân chia các nút con cho từng bộ vi xử lý riêng biệt; loại bỏ giao tiếp khi phát triển nhánh độc lập nhưng gặp khó khăn nghiêm trọng về cân bằng tải (Load Balancing).
    • Phương pháp tiếp cận Lai (Hybrid Approach): Duy trì xử lý đồng bộ ở các tầng trên và tự động phân hoạch sang các nhóm CPU độc lập khi chi phí truyền thông vượt quá ngưỡng: $$\sum (\text{Chi phí giao tiếp}) \ge \text{Chi phí di chuyển} + \text{Chi phí tải cân bằng}$$

  2. Đề xuất cải tiến mô hình C4.5:

    • Đề xuất cơ chế lưu vết chỉ mục sắp xếp để giảm thiểu số lần gọi hàm QuickSort trên các thuộc tính liên tục.
    • Bổ sung module chuyển đổi trực tiếp tập luật c4.5rules thành các câu lệnh SQL CASE WHEN hỗ trợ nhúng trực tiếp vào các hệ quản trị cơ sở dữ liệu quan hệ (Oracle, PostgreSQL).

Ứng dụng thực tế và Triển khai nghiệp vụ

Các kịch bản ứng dụng trong ngành Viễn thông & Tài chính

  • Quản trị trải nghiệm khách hàng (Customer Churn Prevention): Phân tích log dịch vụ viễn thông nhằm phát hiện sớm nhóm thuê bao có nguy cơ rời mạng hoặc suy giảm cước tiêu dùng.
  • Cá nhân hóa dịch vụ giá trị gia tăng (VAS Recommendation): Tự động phân loại người dùng portal để gợi ý nội dung (Nhạc chuông, tin tức, dịch vụ dữ liệu) dựa trên độ tuổi, vùng miền và loại thiết bị.
  • Xác thực và xếp hạng tín nhiệm tín dụng (Credit Scoring): Chuyển đổi các chỉ số tài chính, lịch sử trả nợ thành cây quyết định hỗ trợ duyệt khoản vay tự động với khả năng giải thích lý do (Interpretability) minh bạch.
-- Ví dụ: Ánh xạ quy tắc phân lớp C4.5 thành truy vấn SQL nghiệp vụ tự động
SELECT 
    CUSTOMER_ID,
    CASE 
        WHEN ACCESS_DURATION <= 120 AND DATA_VOLUME <= 500 THEN 'LOW_USAGE'
        WHEN ACCESS_DURATION > 120 AND SERVICE_TYPE = 'RING_TONE' THEN 'VAS_HIGH'
        WHEN AGE > 22 AND REGION_ID = 1 AND ACCESS_COUNT > 30 THEN 'NOKIA_USER'
        ELSE 'STANDARD_USER'
    END AS PREDICTED_CLASS
FROM VNPT_PORTAL_LOGS;

Yêu cầu triển khai hệ thống

  • Hạ tầng tối thiểu (On-Premise / Cloud VM): 2 vCPU, 2GB RAM, 10GB lưu trữ SSD (phù hợp cho mô hình C4.5 với quy mô $< 500.000$ bản ghi).
  • Hạ tầng quy mô lớn (SPRINT / Parallel Tree): Cụm máy chủ kiến trúc Shared-Nothing kết nối mạng băng thông cao (1Gbps/10Gbps Ethernet), hệ thống đĩa phân tán phục vụ lưu trữ Attribute Lists.

Hạn chế và Hướng phát triển

Hạn chế kỹ thuật

  1. Nghẽn bộ nhớ của C4.5: C4.5 không thể xử lý trực tiếp tập dữ liệu vượt quá dung lượng RAM thực tế; việc cấp phát mảng động trong mã nguồn C nguyên bản dễ gây tràn bộ nhớ khi số lượng bản ghi vượt mức hàng triệu.
  2. Chi phí I/O và bảng băm của SPRINT: SPRINT yêu cầu lưu trữ nhiều danh sách thuộc tính trên đĩa, làm tăng đáng kể dung lượng lưu trữ phụ trợ (gấp 2-3 lần kích thước dữ liệu thô). Kích thước bảng băm phân phối nút con tỉ lệ thuận với số bản ghi, gây nghẽn RAM khi phân hoạch các nút lớn.
  3. Phân loại đơn nhãn: Mô hình chỉ hỗ trợ gán một nhãn phân lớp duy nhất cho mỗi bản ghi, chưa xử lý được bài toán đa nhãn (Multi-label Classification).

Hướng phát triển nghiên cứu

  1. Cài đặt hoàn chỉnh thuật toán SPRINT trên môi trường tính toán song song: Triển khai thử nghiệm trên cụm máy tính hiệu năng cao sử dụng thư viện truyền thông điệp MPI (Message Passing Interface) hoặc OpenMP.
  2. Tích hợp các thuật toán tối ưu tiên tiến: Nghiên cứu áp dụng thuật toán PUBLIC (kết hợp đồng thời quá trình sinh cây và cắt tỉa cành để giảm số nút rác) và ScalParC (tối ưu hóa cấu trúc bảng băm phân chia dữ liệu).
  3. Phát triển module trực quan hóa tương tác: Xây dựng giao diện Web Dashboard cho phép chuyên viên nghiệp vụ tùy chỉnh ngưỡng phân cắt và trực quan hóa cây quyết định theo thời gian thực.

Đối tượng hưởng lợi

mindmap
  root((Phân lớp Dữ liệu Cây quyết định))
    Sinh viên & Nghiên cứu sinh
      Nắm vững giải thuật Hunt, C4.5, SPRINT
      Phương pháp luận thực nghiệm Holdout & Cross-validation
    Kỹ sư Dữ liệu & Lập trình viên
      Mẫu triển khai cấu trúc dữ liệu Attribute Lists & Hash Table
      Mã nguồn C chuẩn hóa tối ưu hóa bộ nhớ
    Doanh nghiệp Viễn thông & Tài chính
      Tự động hóa phân khúc khách hàng
      Trích xuất luật nghiệp vụ dạng If-Then / SQL
  • Sinh viên và Học viên ngành CNTT/Khoa học dữ liệu: Tài liệu tham khảo toàn diện về giải thuật khai phá dữ liệu, từ nền tảng lý thuyết Hunt đến cài đặt chi tiết các độ đo Entropy, Gain Ratio và Gini Index.
  • Kỹ sư phát triển phần mềm (Software/Data Engineers): Nắm bắt kỹ thuật quản lý bộ nhớ, cơ chế tiền sắp xếp dữ liệu lớn và phương pháp phân hoạch đĩa khi xây dựng các pipeline học máy hiệu năng cao.
  • Doanh nghiệp và Chuyên viên phân tích nghiệp vụ (Business Analysts): Khả năng chuyển hóa dữ liệu log thô thành các quy tắc nghiệp vụ tường minh ($If-Then$), loại bỏ tính chất "hộp đen" của các mô hình học sâu (Deep Learning).

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

1. Yêu cầu phần cứng tối thiểu để triển khai mô hình C4.5 là gì?

Đối với các tập dữ liệu quy mô vừa (dưới 200.000 bản ghi), mô hình C4.5 chỉ yêu cầu máy chủ cấu hình tối thiểu 1 vCPU, 1GB RAM và hệ điều hành Linux tiêu chuẩn (RedHat, CentOS, Ubuntu).

2. SPRINT khắc phục nhược điểm tràn bộ nhớ của C4.5 và SLIQ như thế nào?

SPRINT không lưu trữ tập dữ liệu hay danh sách lớp (Class List) trong bộ nhớ chính. Thuật toán tách mỗi thuộc tính thành một danh sách riêng biệt lưu trên đĩa (Attribute List), tiền sắp xếp một lần duy nhất. Trong suốt quá trình phát triển cây, bộ nhớ RAM chỉ cần duy trì các biểu đồ phân phối tần suất (Histograms) có kích thước rất nhỏ, độc lập với số lượng bản ghi.

3. Tại sao C4.5 lại ưu tiên sử dụng Gain Ratio thay vì Information Gain?

Information Gain có xu hướng thiên vị các thuộc tính có số lượng giá trị phân biệt lớn (ví dụ: mã số định danh, ngày tháng chi tiết), dẫn đến việc tạo ra các cây có độ phân nhánh cao nhưng không có giá trị tổng quát hóa. Gain Ratio khắc phục điều này bằng cách chia cho $SplitInfo$, phạt nặng các thuộc tính phân chia thành quá nhiều nhánh nhỏ.

4. Chi phí tính toán để tạo tập luật (c4.5rules) so với sinh cây quyết định (c4.5) chênh lệch như thế nào?

Thực nghiệm cho thấy thời gian sinh tập luật lớn hơn gấp 4 đến 5 lần thời gian sinh cây (ví dụ với 120.000 bản ghi: sinh cây mất 33,45 giây nhưng sinh luật mất 148,90 giây). Nguyên nhân là giải thuật phải duyệt tổ hợp từng điều kiện tiền đề trong tất cả các đường dẫn từ gốc đến lá và đánh giá lại độ chính xác trên toàn bộ tập dữ liệu huấn luyện.

5. Có thể áp dụng mô hình này cho các bài toán phân lớp dữ liệu thời gian thực (Real-time Stream) không?

Mô hình cây quyết định truyền thống (C4.5, SPRINT) được thiết kế cho xử lý theo lô (Batch Processing). Để xử lý luồng dữ liệu thời gian thực, cần tích hợp các biến thể cây quyết định thích nghi gia tăng như Hoeffding Trees (VFDT - Very Fast Decision Trees) để cập nhật cấu trúc nút mà không cần huấn luyện lại từ đầu.

Kết luận

Khóa luận tốt nghiệp "Nghiên cứu các thuật toán phân lớp dữ liệu dựa trên cây quyết định" đã thực hiện thành công việc khảo sát toàn diện, phân tích toán học chuyên sâu và đánh giá thực nghiệm chuẩn mực đối với hai mô hình phân lớp kinh điển C4.5 và SPRINT. Thông qua quá trình thử nghiệm trên 180.000 bản ghi thực tế từ mạng viễn thông VNPT, nghiên cứu đã chứng minh tính hữu dụng vượt trội của cây quyết định trong việc trích xuất các tri thức nghiệp vụ tường minh, dễ hiểu dưới dạng luật sản xuất.

Kết quả nghiên cứu không chỉ cung cấp cơ sở khoa học vững chắc về các chiến lược mở rộng dữ liệu và song song hóa giải thuật mà còn mở ra tiềm năng ứng dụng to lớn trong các bài toán phân tích hành vi khách hàng, quản trị rủi ro và tối ưu hóa hệ thống thông tin tại Việt Nam.