1. Khái niệm về phân lớp

·        Phân lớp dữ liệu có thể coi là quá trình “học” một mô hình (model) mà mô hình này dùng để mô tả các lớp dữ liệu khác nhau. Các lớpdữ liệu ở đây đã được xác định trước.

·        Khác với phân cụm, phân lớp được xem là một quá trình “học có giám sát” (supervised learning). Sau khi được xây dựng, mô hình phân lớp có thể được sử dụng để phân lớp các dữ liệu mới.

·        Mỗi bản ghi trong tập dữ liệu học có một thuộc tính gọi là nhãn lớp (class label) để chỉ ra bản ghi đó thuộc lớp nào.

2. Độ đo trong phân lớp

a. Thông tin được kỳ vọng

·        Giả sử thuộc tính phân lớp (class label/attribute) có n giá trị khác nhau: v1, v2,…, vn (như vậy có n lớp).

·        Tập dữ liệu học S gồm s mẫu (bản ghi). Ký hiệu si là số mẫu thuộcvề lớp có nhãn vi.

·        Thông tin được kỳ vọng (expected information) để phân lớp s mẫu là:

Viết công thức ra nhé !!!

b. Entropy của thuộc tính

·        Giả sử thuộc tính A có m giá trị khác nhau: v1, v2,…, vm và được sử dụng như là thuộc tính kiểm tra để phân nhánh trong cây quyết định.

·        Thuộc tính A chia tập mẫu học thành m tập con S1, S2,…, Sm. Trong đó các mẫu thuộc Si sẽ có thuộc tính A mang giá trị vi.

·        Một tập con Sicó thể chứa các mẫu thuộc về một lớp bất kỳ. Số lượng mẫu trong tập Si

·        thuộc về lớp j (có nhãn vj) ký hiệu là sji.

·        Entropy của thuộc tính A:

Viết công thức ra nhé !!!

c. Độ lợi thông tin

·        Độ đo quan trọng sử dụng trong phân lớp dữ liệu là độ lợi thông tin (information gain) được xây dựng dựa trên khái niệm Entropy của thông tin.

·        Mục tiêu: Tối thiểu hóa lượng thông tin cần thiết để phân lớp các các mẫu dữ liệu (tối thiểu hóa số lượng các điều kiện kiểm tra cần thiết để phân lớp một bản ghi mới).

·        Độ lợi thông tin ứng với thuộc tính A:

Viết công thức ra nhé 

3. Nội dung giải thuật xây dựng cây quyết định

a. Mô hình phân lớp cây quyết định

Mô hình phân lớp thường được biểu diễn dưới dạng cây quyết định (decision tree) hoặc dưới dạng một tập các luật phân lớp.

Cây quyết định là hình thức biểu diễn trực quan cho các mô tả lớp. Hay nói cách khác, đó là một hình thức biểu diễn của các luật phânlớp (classification rules).

Các luật có thể được xác định bằng cách đi từ nút gốc đến nút lá của cây quyết định.

b. Thuật toán

Input: Tập dữ liệu học Recoreds gồm m bản ghi R1, R2,…, Rm.

Tập thuộc tính Attributes gồm m thuộc tính A1, A2,…, An.

Output: Mô hình cây quyết định.

procedure Build_tree(Records, Attributes)

begin

Tạo nút N;

if (tất cả các bản ghi thuộc về một lớp Cinào đó) then

begin

N.Label = Ci;

return N;

end;

if (Attributes = ⍉) then

begin

Tìm lớp Cj mà phần lớn các bản ghi r ∈ Records thuộc về lớp đó.

N.Label = Cj;

return N;

end;

Chọn Ai ∈ Attribute sao cho Gain(Ai)→max;

N.Label = Ai;

for each giá trị vi đã biết của Ai do

begin

Thêm một nhánh mới vào nút N ứng với Ai = vj;

Sj = Tập con của Records có Ai = vj;

if (Sj = ⍉) then

Thêm một nút lá L với nhãn là lớp mà phần lớp các bản ghi r ∈ Records thuộc về lớp đó;

return L;

else

Thêm vào nút được trả về bởi Build_Tree(Sj, Attribute \{Ai});

end ;

end;