- 聚类与集成算法
- 分类
- K-Means算法
- 集成
- 分类
- Adaboost算法
聚类是将集中具有相似特性的数据分类组织的过程，是一种无监督学习。
分类- 原型聚类：先对原型初始化，然后对原型进行迭代更新求解。
代表：K-Means、学习向量量化 (LVQ)，高斯混合聚类
- 层次聚类：对给定的数据集进行层次似的分解，直到某种条件满足为止，从而形成树形的聚类结构。
代表：AGNES (自底向上)，DIANA (自顶向下)。
- 密度聚类：从样本密度的角度来考察样本之间的可连接性，并基于可连接样本
不断扩展聚类簇。
代表：DBSCAN, OPTICS, DENCLUE
K-Means算法概述：先确定常数K，K即表示最终的聚类类别数（K个簇），首先随机选定初始点为质心，并通过计算每一个样本与质心之间的相似度（这里为欧式距离，使簇内具有较高的相似度，簇间的相似度较低），将样本点归为最相似的类中，接着重新计算每个类的质心，重复次过程，直到质心不再改变，最终确定每个样本所属的类别及每个类的质心。
步骤：
Step1：随机选取k个样本点作为类中心
Step2：将其他样本点根据其类中心，划分给最近的类
Step3：更新各类的均值向量，将其作为新的类中心
Step4：若所有类中心未发生改变，则停止；否则执行Step2
集成集成学习通过建立几个模型来解决单一预测问题。它的工作原理是生成多个分类器/模型，各自独立地学习和作出预测。这些预测最后结合成组合预测，因此优于任何一个单分类的做出预测。
分类序列化方法（串行）：个体学习器们的产生依赖彼此，比如当前学习器的产生依赖上一个学习器的参数，所以最终将单个学习器们组合形式可以看做是串行序列化方法,代表是Adaboost、GradientBoost、LPBoost。主要用于提高训练精度 （解决欠拟合，也可以说降低偏差）。
并行化方法：个体学习器间不存在强依赖关系、可并行化同时生产，代表是Bagging、Random Forest、Random Subspace。主要用于提高泛化性能（解决过拟合，也可以说降低方差）。
Adaboost算法AdaBoost（Adaptive Boosting 自适应增强）是一种迭代算法，在每一轮中加入一个新的弱分类器，直到达到某个预定的足够小的错误率。其核心思想是针对同一个训练集训练不同的分类器(弱分类器)，然后把这些弱分类器集合起来，构成一个更强的最终分类器(强分类器)。
Boosting算法的工作机制：首先从训练集中用初始权重训练出一个弱学习器1，根据弱学习器的学习误差率表现来更新训练样本的权重，使得之前弱学习器1学习误差率高的训练样本点的权重变高，使得这些误差率高的点再后面的弱学习器2中得到更多的重视。然后基于调整权重后的训练集来训练弱学习器2，如此重复进行，直到弱学习器数达到事先指定的数目T，最终将这T个弱学习器通过集合策略进行整合，得到最终的强学习器。
区分Boosting大家族的算法的要素：
- 如何计算学习误差率
- 如何得到弱学习器权重系数
- 如何更新样本权重
- 学习器的结合策略
Adaboost的做法：
- 通过提高那些在前一轮被弱分类器分错样例的权值，减小前一轮分对样本的权值，而误分的样本在后续受到更多的关注。
- 通过加法模型将弱分类器进行线性组合，比如AdaBoost通过加权多数表决的方式，即增大错误率小的分类器的权值，同时减小错误率较大的分类器的权值。
误差率： e k = P ( G k ( x i ) ≠ y i ) = ∑ i = 1 m ω k i I ( G k ( x i ) ≠ y i ) e_k=P(G_k(x_i)≠yi)=sum_{i=1}^{m}omega _{ki}I(G_k(x_i)≠y_i) ek=P(Gk(xi)=yi)=∑i=1mωkiI(Gk(xi)=yi)
I ( G k ( x i ) ≠ y i ) = { 0 i f G k ( x i ) = y i 1 i f G k ( x i ) ≠ y i I(G_k(x_i)≠y_i)=begin{cases}0quad if;G_k(x_i)=yi \1quad if; G_k(x_i)≠yiend{cases} I(Gk(xi)=yi)={0ifGk(xi)=yi1ifGk(xi)=yi
学习器的权重： α k = 1 2 l o g ( 1 − e k e k ) α_k=frac12log(frac{1-e_k}{e_k}) αk=21log(ek1−ek)
加权平均 f ( x ) = s i g n ( ∑ k = 1 K α k G k ( x ) ) f(x)=sign(sum_{k=1}^{K}alpha_kG_k(x)) f(x)=sign(∑k=1KαkGk(x))
