Data Minig --- Classification(supervised learning)

一、决策树：tree construction & tree pruning

a.ID3算法

Gain(A)=Entropy(S) - Σ(Sv/S)*Entropy(Sv)

b.C4.5算法

GainRatio(A)=Gain(A)/SplitInfo(A)

SplitInfo(A)=-Σ(Sv/S)log(Sv/S)

c.Gini Index算法

定义Gini系数如下：

若将数据分成两个子集，则分割后的Gini系数为：

提供最小的Gini_split就被选为分割的标准。

二、朴素贝叶斯分类

p(c|x1…xn)=p(c)*p(x1|c)…*p(xn|c)/Σp(c)*p(x1|c)…*p(xn|c)

三、BP神经网络

BP神经网络模型如下，其目的是根据实际的输入（输入正传）与输出数据更新模型的权系数（误差反传），BP神经网络结构如下：

对噪声容错强，很适合连续值的输入输出，缺点是训练时间长且确定隐层神经元个数需要经验知识。

四、k近邻

欧式距离：L=norm(x-x')

距离测试点最近的K个点所属的类即测试点的类别。

五、集成学习：BaggingBoosting

a.Bagging算法（bootstrap）

for t=1…T

    s'为从给定训练集s中的随机抽样（有放回）

    在s'上训练弱学习器，得到第t轮的预测函数ht

end

对未知样本x分类时，每个弱分类器ht得到一个结果，得票最高的就是x的类别。

b.Boosting算法

初始分布：D1(i)=1/N

for t=1…T

    计算弱分类器在分布Dt上的误差：et=P(ht(xi)!=yi)

    更新弱分类器的权重：αt=(1/2)*ln((1-et)/et)

    更新训练样本分布：Dt+1(i) = Dt(i)exp(-αt*yi*h(xi))/Zt = Dt/2et 或 Dt/2(1-et)

end

强分类器：H(x)=sign(Σαt*ht)

六、分类准确度

confusion matrix

accuracy=(t-pos+t-neg)/(pos+neg)