Hey

Machine Learning notes

聚类相关知识

聚类

相似度/距离计算方法
1. 闵可夫斯基距离/欧式距离
2. Jaccard相似系数适合于集合运算
3. 余弦相似度
4. 相关系数（是线性的）也可以作为相似度度量
5. Person相似系数
6. 相对熵（K-L距离）不对称
7. Hellinger距离对称的，满足三角不等式、非负距离的

K-means算法

改进：

K-Mediods聚类（使用中位数代替k-means中位数）
二分k-Means聚类方法
K-Means++算法在选择聚类中心的改进
Mini-batch-K-Means随机聚类算法随机体现到更新中心随机部分样本

K-means算法对初值是敏感的

有时候可以通过数据的映射（比如聚类等），然后聚类可以得到更好的效果

当方差不相等的数据，数量不相等k-means聚类的效果不一定好

K-means使用平方误差作为目标函数时的梯度就是聚类更新时每个类别均值作为新的聚类中心，这个也可以理解为什么K-Means聚类中心随机初始化的中心是不同的，因为梯度下降可能处于不同的局部最优解

K-Mean使用范围：得到的类型为圆形的聚类形状，默认的是高斯分布或混合高斯模型

K-Means聚类参数的关键在于K值得选取：可以使用交叉验证进行选择，选择类似损失图得进行选择拐点出

优点：可以处理大数据集，当数据集符合高斯分布效果较好

缺点：需要给出k值，而且对初值很敏感，不同得初值得到不同得结果，不适合非凸形状得睡觉，而且对噪声和孤立点数据很敏感

Canopy算法

聚类得衡量指标

均一性一个簇只包含一个类别得样本，则满足均一性

from sklearn import metrics
  y = [0, 0, 0, 1, 1, 1]
  y_hat = [0, 0, 1, 1, 2, 2]
  h = metrics.homogeneity_score(y, y_hat)
  c = metrics.completeness_score(y, y_hat)
  print u'同一性(Homogeneity)：', h
  print u'完整性(Completeness)：', c
  v2 = 2 * c * h / (c + h)
  v = metrics.v_measure_score(y, y_hat)
  print u'V-Measure：', v2, v

完整性同类别样本被归类到相同得簇中，则满足完整性
V-measure 均一性和完整性得加权平均
ARI
AMI
轮廓系数（可以不知道真正的类别）

层次聚类

凝聚的层次聚类 AGNES算法
分裂的层次聚类 DIANA 算法

层次聚类更像是决策树

密度聚类 DBSCAN

只要样本点的密度大于阈值，则将该样本添加到最近的簇中

该算法能够克服基于距离算法只能发现“类圆”的聚类的缺点，而且在一定程度允许噪声

密度最大值聚类

可以进一步得到更好的效果，而且对于噪音可以有更好的效果，而且可以得到聚类的边界的

AP算法调参

根据相似度来进行聚类的算法

AP算法的基本思想：将全部样本看成网格的节点，然后通过网格各条边的消息传递计算出各样本的聚类中心。聚类过程中，共有两种消息在各个节点间传递，分别是吸引度（responsibility）和归属度（availability）。Ap算法通过迭代过程不断更新每一个点的吸引读和归属度值，直到产生m个高质量的Exemplar(类似与质心)，同时将其余的数据点分配到相应的聚类中。

在实际计算应用中，最重要的两个参数（也是需要手动指定）是Preference和Damping factor。前者定了聚类数量的多少，值越大聚类数量越多；后者控制算法收敛效果。

谱聚类

随机游走拉布拉斯矩阵求解

优点就是可以求解非凸的类型数据和嵌套的圆形数据，谱聚类也是需要给定K

值的

谱聚类是可以做图像的分割的

标签传递算法

对于部分样本的标记给定，而大多数样本的标记未知的情形，是半监督学习问题LPA

MeanShift聚类

算法原理：有一个点x，它的周围有很多个点xi我们计算点x移动到每个点xi所需要的偏移量之和，求平均，就得到平均偏移量（该偏移量的方向是周围点分布密集的方向）该偏移量是包含大小和方向的，然后点x就往平均偏移量方向移动，在以此为新的起点不断地迭代直到满足一定地条件结束。

meanshift在图像处理中地聚类，跟踪中的应用。

与K-means算法不同的是，Meanshift算法可以自动决定类别的数目

与K-means算法一样的是，两者都使用集合内数据点的均值进行中心点的移动