聚类Clustering

非监督学习

；

注：非监督学习的训练数据是没有标签的，目的是发现数据之间的内存规律；

聚类

；

；

注：聚类的使用场景1-简化计算：如推荐系统，通常大的平台的用户数据上亿，如果根据每个人的数据去计算的话中，计算量太大，此时可以将原始数据进行分组，然后对分组后的聚类中心进行推荐计算；

场景2-从统计角度去除离群点，离群点通常不在任何一个簇中；

场景3：可视化更好，能更好的理解数据；

常用聚类算法

；

注：基于连接的聚类算法是指：以样本之间的边接为主，样本之间的连接会构成一个网络(图)；

；

；

；

；

注：因对数据做中心化后，相关系数等于余弦系数，通常使用中，余弦系数的使用会更多；

；

K-means聚类

；

；

；

注：K值的确定取决于聚类的度量标准，监督学中心一般是取决于交叉验证；

；

注：此时的中心点是随机的，然后对每个样本计算到各个中心点的距离，取距离最近的中心点，并将该样本分到该中心点的簇里；

；

注：步骤4中，对已经分好各类数据(此时中心点为随机的)，计算每个类的均值，并将该均值做为新的中心点；

K-means的缺点：步骤4中，均值点可能是并不样本点，同样，步骤1中随机的点也可能并不是样本点；

；

；

注：如迭代的图示：一般情况下经过几次迭代，数据会很快收敛；

；

；

注：此时，最小化均值时，超参数有两个，因此不能同时优化；所有要用到坐标下降，即先固定一个参数，优化另一个，然后再反过来；

；

注：坐标下降可以看成是梯度下降的简化版本，坐标下降可以证明其会收敛到一个局部最小值；

；

注：上图中为局部最优，全局最优时，应该是左边为一类，右上和右下为其它两类；

； 

； 

注：左上的问题原因：给定的K值不对，左上应该有3类，但K值设置的为2，要给定K值也是该算法的缺点之一；

右上的问题原因：K-means计算的样本点到中心的距离，该范围在二维空间上是一个圆，在三维空间上是一个球形，因此，对上右上的数据会分不对；

左下的问题原因：三个类别的方差不一样，紫色的方差小，数据很密集，黄色的方差大，数据之间相对松散，此时用k-means的话，会将本应该是黄色的一部分磁本点分到紫色分类里，因此如果类别之间的方差相差太大的话，k-means也处理不了，k-means算法中，假设的条件是每类的方差是一样的；

右下的问题原因：数据没有做归一化处理，各个类别间的样本数差异太大，此时计算的均值就不准确了；

；

注：聚类可以用于图像分割，将图像中的每个像素看成一个样本点，每上样本点的特征为RGB三个维度的数值，然后做聚类就可以分割出图层；

原始图像(第一张)，因为RGB每个维都是8比特(2的8次方，256色)，所以总共是24比特；

；

注：K-means聚类在数据为球形，且球的大小差不多(协方差差不多)时，能取得最好的效果；在分类结果上，K-means和混和高斯模型几乎一样；

硬分类：某一个样本属于某一个类；软分类：某一个样本点，属于各类的概率，然后分类概率最高的那个分类；

K-means算法在数据压缩中称为向量量化(Vector Quantization)，也有叫LBG算法；

; 

注：中值为将样本点进行排序，然后取中间的那个样本点；

L2距离对噪声敏感的解释：L2距离是样本点减去均值的平方，因此会放大噪声；

; 

; 

注：K-means的损失函数不是一个归一化的度理，即数值之间没有可比性，如某一组数据的聚类效果为100，另一组为120，不能说100就一定比120好；

; 

注：蓝色标出的参数为K-means特有的参数；

; 

注：当样本数较多时，可以用Mini Batch K-Means算法，该算法可以减少计算时间，但结果的质量会降低一点；

上图中第三张显示的是K-means和MiniBatchKMeans分类后，结果上的差异点，即红色的那些点，这些差异点一般位于分类的边界，这些点不一这说K-means的结果就是一定是对的；

同理，梯度下降在数据量较多时，也要换成随机梯度下降； 

层次聚类(Hierarchical Clustering)

层次聚类的好处：

;

;

;

注：层次聚类中度量的是两个类之间的关系，K-means中度量的是样本之间的关系；

;

;

注：最大距离法中，结果会被噪声影响，因此要删除这些值之后再聚类；

;

注：极值很容易受噪声影响，类平均距离法被认为是较好的系统聚类法；

; 

注：ward linkage方差最小，各类大小最平均，但该算法的距离是欧式距离，不能用相似度来度量，average linkage则可以；

注：连接约束是：上图左中没有连接约束，卷中最外面的蓝色和里层的蓝色样本点被分到了一类，加了连接约束后，像这种空间隔离的样本点就不会被分到一类，即使样本点之间的距离很近，如上图右；

连接约束的缺点：连接约束会增加一个连接矩阵，带来额外的计算负担； 

;

;

注：层次聚类的缺点：1）运算量较大，不适用于大规模的数据；2） 一旦完成一个步骤，就不能撤销或修正；

吸引子传播算法(AP算法-Affinity Propagation)

;

注：计算复杂度中，N是样本数，T是迭代次数；AP算法应用场景：视频进度分割；

;

注：作为输入的相相似矩阵是由，样本之间的相似度的值构成的矩阵；其中，对角线上的元素叫preference(喜好程度)，该值越小，说明以该点作为中心聚类时，聚类数主会相对较少；

;

注：阻尼因子是为了避免在迭代(用上一次的结果去计算本次的结果)的过程中数值的震荡；

基于密度聚类方法

；

(Density-Based Spatial Clustering of Applications with Noise)

;

; 

注：直接密度可达要求样本点在一个球内，密度可达要求样本点在两个球内，密度相连要求样本点在三个球内；

各聚类算法总结

关于超参数的确定

机器学习模型中，超参数的确定前，需要先确定评价该模型性能的指标，然后再根据该指标的意义下去寻找合适的参数；

聚类性能评估

外部评价指标(有参考结果)：

注：N11和N00都表示分类正确的情况；ARI越大越好；

注：对于修正后的ARI，对随机类别结果的期望要用超几何分布来求；

(Adjusted Mutual Information)

注：越大越好；

注：越大越好；

内部评价指标(无参考)：

注：a(i)为类内散度，为类间散度；

注：类间散度为类中心之间的距离和；值越大越好；