Bài tập | NEU OJ

Cho $n$ mẫu, mỗi mẫu có giá trị thuộc tính rời rạc $x_i$ và nhãn lớp $y_i$ . Information Gain khi chia theo thuộc tính $x$ :

$IG = H(y) - \sum_{v}\frac{|S_v|}{n}\,H(S_v)$

trong đó $S_v$ là tập các nhãn của những mẫu có $x=v$ , và $H$ là entropy ( $-\sum_c p_c\log_2 p_c$ , quy ước $0\log_2 0=0$ ). Hãy in $IG$ .

Định dạng đầu vào:
Dòng đầu: $n$ . $n$ dòng tiếp theo, mỗi dòng hai số nguyên $x_i$ $y_i$ .
Ràng buộc đầu vào:
$1 \le n \le 1000$ ; $x_i, y_i$ là số nguyên không âm.
Định dạng đầu ra:
Một số thực: information gain, làm tròn 2 chữ số thập phân.

solution