机器学习第一次作业

一）
（1）
曲线C_1的AUC=0.6875
曲线C_2的AUC=0.625
（2）
分类器C_1的混淆矩阵为
预测结果为正例
预测结果为反例
正例
3
1
反例
2
2
F_1=\frac{2}{\frac 1 R +\frac 1 P}=\frac 2 3
分类器C_2的混淆矩阵为
预测结果为正例
预测结果为反例
正例
3
1
反例
4
0
F_1=\frac 6 {11}
（3）
只需注意到：
1-l_{rank}=\frac{1}{m^+m^-}\sum_{x^-\in D^-}\sum_{x^+\in D^+}\left(1-I(f(x^+)[InvalidCharacterError: "F((X^-)-\FRAC" did not match the Name production]
1-l_{rank}=\frac{1}{m^+m^-}\sum_{x^-\in D^-}\sum_{x^+\in D^+}\left(I(f(x^+)>f((x^-)+\frac 1 2I(f(x^+)=f(x^-)\right)
当D是样本全体时，1-l_{rank} 恰好为ROC曲线下方的面积，即AUC=1-l_{rank}
二）
（1）似然函数作为目标函数，等价于极小化经验误差，即对于给定的一个样本，其真实分类为Y^* ，则其经验误差为R(Y|X)=\sum_{Y\ne Y^*}P(Y|X)
=1-P(Y^*|X) ；对于全体样本，其总体经验误差就是R(h)=\sum_{X}(1-P(h(X)|X)) ，目标就是找到合适的h，即对每一个X进行合适的分类，
以求对于全体样本而言总体经验误差最小化。
对有限个样本达到这个目标，其目标函数为\max_{h}\sum_{i=1}^m P(h(X_i)|X_i)
而对于每个i,h(X_i)=Y=(h_1(X_i),...,h_n(X_i)),P(h(X_i)|X_i)=\prod_{j=1}^n P(h_j(X_i)|X_i)
从而对数似然函数可以有以下形式：L(\beta)=\sum_{i=1}^m\sum_{j=1}^n\ln P(y_j^i|X_i)
最大化对数似然函数等价于最小化函数LL(\beta)=\sum_{i=1}^m\sum_{j=1}^n -y_j^i\beta^T\hat X_i+\ln(1+e^{\beta^T\hat X_i}) ，这就是对数形式的似然函数
（2）对数形式的似然函数梯度为
\nabla LL(\beta)=\sum_{i=1}^m\sum_{j=1}^n (-y_j^i+\frac{e^{\beta^T\hat X_i}}{1+e^{\beta^T\hat X_i}})\cdot \hat X_i
三）
（1）可以实现
f=1
/
/ y=1
/
[]
/ \
/ \ y=0
/ x=1 \
/ f=0
[]
\ f=0
\ x=0 /
\ /y=1
\ /
[]
\
\ y=0
\
f=1
（2）
a)
Gini_{index}(D,X)=\frac{|D^{x=1}|}{|D|}Gini(D^{x=1})+\frac{|D^{x=0}|}{|D|}Gine(D^{x=0}) =\frac{1}{2}\times \frac{1}{2}+\frac 1 2\times \frac 1 2=\frac 1 2
Gini_{index}(D,Y)=\frac{|D^{y=1}|}{|D|}Gini(D^{y=1})+\frac{|D^{y=0}|}{|D|}Gine(D^{y=0}) =\frac 1 2
Gini_{index}(D,Z)=\frac{|D^{z=1}|}{|D|}Gini(D^{z=1})+\frac{|D^{z=0}|}{|D|}Gine(D^{z=0}) =\frac 3 4\times \frac 4 9 +\frac 1 2\times 0=\frac 1 3
属性Z的基尼指数最小，所以选择Z划分
b)
Z=0的样本全部属于同一类，因此这个节点标记为叶节点，类别标记为f=0
c)
Gini_index(D^{Z=1},X)=\frac{|D^{Z=1,X=1}|}{|D^{Z=1}|}Gini(D^{Z=1,X=1})+\frac{|D^{Z=1,X=0}|}{|D^{Z=1}|}Gini(D^{Z=1,X=0}) =\frac 1 2\times \frac 4 9+\frac 1 2\times \frac 4 9 =\frac 4 9
Gini_index(D^{Z=1},Y)=\frac{|D^{Z=1,Y=1}|}{|D^{Z=1}|}Gini(D^{Z=1,Y=1})+\frac{|D^{Z=1,Y=0}|}{|D^{Z=1}|}Gini(D^{Z=1,Y=0}) =\frac 1 2\times \frac 4 9+\frac 1 2\times \frac 4 9 =\frac 4 9
属性X和Y的基尼指数一样，所以按照字母表顺序选择属性X
d)
选择属性Y，在这个节点的样本中，Y=0则f=1，Y=1则f=0，则按照此规则可得到两个叶节点
e)
选择属性Y，在这个节点的样本中，Y=0则f=0，Y=1则f=1，则按照此规则可得到两个叶节点
[f=0]
/
/Y=1
/
[d)]
/ \
/ X=1 \Y=0
/ \
[c)] [f=1]
/ \ [f=1]
/ \ X=0 /
/ Z=1 \ /Y=1
/ [e)]
[a)] \Y=0
\ \
\ Z=0 [f=0]
\
\
[b),f=0]