Đồ án Khai phá dữ liệu và phát hiện luật kết hợp trong cơ sở dữ liệu lớn

Việc chọn một thuộc tính để tách tập mẫu tương ứng với nút đang xét thường dựa trên entropy của thuộc tính đó. Muốn vậy cần có thông tin về phân bố của các lớp trong tập mẫu đang xét. Sau khi đã có thông tin này, mỗi thuộc tính sẽ được đánh giá theo một tiêu chuẩn tách nào đó. Có một số tiêu chuẩn thường được sử dụng như tiêu chuẩn gain (gain criterion), tiêu chuẩn tỉ số gain (gain ratio criterion), chỉ số gini (gini index). Hai tiêu chuẩn đầu có nguồn gốc từ lý thuyết thông tin còn tiêu chuẩn sau dựa vào xác suất. Để hiểu rõ hơn về tiêu chuẩn đánh giá phép thử, ta sẽ xét kĩ tiêu chuẩn gain và tiêu chuẩn tỉ số gain.

Entropy H(xi) của một tin xi của nguồn rời rạc : Chính là lượng tin ta đoán nhận là sẽ nhận được về một tin của nguồn đó, nó có độ lớn bằng độ đo tin tức của tin đó nhưng có ý nghĩa hoàn toàn khác.

H(xi) = - log(P(xi)) (3)

Entropy H(X) của nguồn rời rạc là entropy trung bình của từng tin trong nguồn đó và được tính như sau :